9 files changed, 305 insertions, 27 deletions

diff --git a/crates/syntax/src/algo.rs b/crates/syntax/src/algo.rs
index b13252eec..82ebf9037 100644
--- a/crates/syntax/src/algo.rs
+++ b/crates/syntax/src/algo.rs
@@ -4,7 +4,6 @@ use std::{
     fmt,
     hash::BuildHasherDefault,
     ops::{self, RangeInclusive},
-    ptr,
 };
 
 use indexmap::IndexMap;
@@ -27,7 +26,7 @@ pub fn ancestors_at_offset(
     offset: TextSize,
 ) -> impl Iterator<Item = SyntaxNode> {
     node.token_at_offset(offset)
-        .map(|token| token.parent().ancestors())
+        .map(|token| token.ancestors())
         .kmerge_by(|node1, node2| node1.text_range().len() < node2.text_range().len())
 }
 
@@ -171,7 +170,7 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
             && lhs.text_range().len() == rhs.text_range().len()
             && match (&lhs, &rhs) {
                 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => {
-                    ptr::eq(lhs.green(), rhs.green()) || lhs.text() == rhs.text()
+                    lhs == rhs || lhs.text() == rhs.text()
                 }
                 (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => lhs.text() == rhs.text(),
                 _ => false,
@@ -280,9 +279,10 @@ fn _insert_children(
         to_green_element(element)
     });
 
-    let mut old_children = parent.green().children().map(|it| match it {
-        NodeOrToken::Token(it) => NodeOrToken::Token(it.clone()),
-        NodeOrToken::Node(it) => NodeOrToken::Node(it.clone()),
+    let parent_green = parent.green();
+    let mut old_children = parent_green.children().map(|it| match it {
+        NodeOrToken::Token(it) => NodeOrToken::Token(it.to_owned()),
+        NodeOrToken::Node(it) => NodeOrToken::Node(it.to_owned()),
     });
 
     let new_children = match &position {
@@ -319,9 +319,10 @@ fn _replace_children(
 ) -> SyntaxNode {
     let start = position_of_child(parent, to_delete.start().clone());
     let end = position_of_child(parent, to_delete.end().clone());
-    let mut old_children = parent.green().children().map(|it| match it {
-        NodeOrToken::Token(it) => NodeOrToken::Token(it.clone()),
-        NodeOrToken::Node(it) => NodeOrToken::Node(it.clone()),
+    let parent_green = parent.green();
+    let mut old_children = parent_green.children().map(|it| match it {
+        NodeOrToken::Token(it) => NodeOrToken::Token(it.to_owned()),
+        NodeOrToken::Node(it) => NodeOrToken::Node(it.to_owned()),
     });
 
     let before = old_children.by_ref().take(start).collect::<Vec<_>>();
@@ -487,9 +488,9 @@ impl<'a> SyntaxRewriter<'a> {
     /// Returns `None` when there are no replacements.
     pub fn rewrite_root(&self) -> Option<SyntaxNode> {
         let _p = profile::span("rewrite_root");
-        fn element_to_node_or_parent(element: &SyntaxElement) -> SyntaxNode {
+        fn element_to_node_or_parent(element: &SyntaxElement) -> Option<SyntaxNode> {
             match element {
-                SyntaxElement::Node(it) => it.clone(),
+                SyntaxElement::Node(it) => Some(it.clone()),
                 SyntaxElement::Token(it) => it.parent(),
             }
         }
@@ -497,9 +498,9 @@ impl<'a> SyntaxRewriter<'a> {
         assert!(self.f.is_none());
         self.replacements
             .keys()
-            .map(element_to_node_or_parent)
-            .chain(self.insertions.keys().map(|pos| match pos {
-                InsertPos::FirstChildOf(it) => it.clone(),
+            .filter_map(element_to_node_or_parent)
+            .chain(self.insertions.keys().filter_map(|pos| match pos {
+                InsertPos::FirstChildOf(it) => Some(it.clone()),
                 InsertPos::After(it) => element_to_node_or_parent(it),
             }))
             // If we only have one replacement/insertion, we must return its parent node, since `rewrite` does
@@ -552,7 +553,7 @@ impl<'a> SyntaxRewriter<'a> {
             };
         } else {
             match element {
-                NodeOrToken::Token(it) => acc.push(NodeOrToken::Token(it.green().clone())),
+                NodeOrToken::Token(it) => acc.push(NodeOrToken::Token(it.green().to_owned())),
                 NodeOrToken::Node(it) => {
                     acc.push(NodeOrToken::Node(self.rewrite_children(it)));
                 }
@@ -567,7 +568,7 @@ impl<'a> SyntaxRewriter<'a> {
 fn element_to_green(element: SyntaxElement) -> NodeOrToken<rowan::GreenNode, rowan::GreenToken> {
     match element {
         NodeOrToken::Node(it) => NodeOrToken::Node(it.green().to_owned()),
-        NodeOrToken::Token(it) => NodeOrToken::Token(it.green().clone()),
+        NodeOrToken::Token(it) => NodeOrToken::Token(it.green().to_owned()),
     }
 }
 
@@ -625,7 +626,7 @@ fn position_of_child(parent: &SyntaxNode, child: SyntaxElement) -> usize {
 fn to_green_element(element: SyntaxElement) -> NodeOrToken<rowan::GreenNode, rowan::GreenToken> {
     match element {
         NodeOrToken::Node(it) => it.green().to_owned().into(),
-        NodeOrToken::Token(it) => it.green().clone().into(),
+        NodeOrToken::Token(it) => it.green().to_owned().into(),
     }
 }
 
diff --git a/crates/syntax/src/ast.rs b/crates/syntax/src/ast.rs
index b3a24d39d..19261686c 100644
--- a/crates/syntax/src/ast.rs
+++ b/crates/syntax/src/ast.rs
@@ -6,6 +6,7 @@ mod token_ext;
 mod node_ext;
 mod expr_ext;
 pub mod edit;
+pub mod edit_in_place;
 pub mod make;
 
 use std::marker::PhantomData;
@@ -40,6 +41,12 @@ pub trait AstNode {
         Self: Sized;
 
     fn syntax(&self) -> &SyntaxNode;
+    fn clone_for_update(&self) -> Self
+    where
+        Self: Sized,
+    {
+        Self::cast(self.syntax().clone_for_update()).unwrap()
+    }
 }
 
 /// Like `AstNode`, but wraps tokens rather than interior nodes.
diff --git a/crates/syntax/src/ast/edit_in_place.rs b/crates/syntax/src/ast/edit_in_place.rs
new file mode 100644
index 000000000..449b058fb
--- /dev/null
+++ b/crates/syntax/src/ast/edit_in_place.rs
@@ -0,0 +1,129 @@
+//! Structural editing for ast.
+
+use std::iter::empty;
+
+use ast::{edit::AstNodeEdit, make, GenericParamsOwner, WhereClause};
+use parser::T;
+
+use crate::{
+    ast,
+    ted::{self, Position},
+    AstNode, Direction, SyntaxElement,
+};
+
+use super::NameOwner;
+
+pub trait GenericParamsOwnerEdit: ast::GenericParamsOwner + AstNodeEdit {
+    fn get_or_create_where_clause(&self) -> ast::WhereClause;
+}
+
+impl GenericParamsOwnerEdit for ast::Fn {
+    fn get_or_create_where_clause(&self) -> WhereClause {
+        if self.where_clause().is_none() {
+            let position = if let Some(ty) = self.ret_type() {
+                Position::after(ty.syntax().clone())
+            } else if let Some(param_list) = self.param_list() {
+                Position::after(param_list.syntax().clone())
+            } else {
+                Position::last_child_of(self.syntax().clone())
+            };
+            create_where_clause(position)
+        }
+        self.where_clause().unwrap()
+    }
+}
+
+impl GenericParamsOwnerEdit for ast::Impl {
+    fn get_or_create_where_clause(&self) -> WhereClause {
+        if self.where_clause().is_none() {
+            let position = if let Some(items) = self.assoc_item_list() {
+                Position::before(items.syntax().clone())
+            } else {
+                Position::last_child_of(self.syntax().clone())
+            };
+            create_where_clause(position)
+        }
+        self.where_clause().unwrap()
+    }
+}
+
+impl GenericParamsOwnerEdit for ast::Trait {
+    fn get_or_create_where_clause(&self) -> WhereClause {
+        if self.where_clause().is_none() {
+            let position = if let Some(items) = self.assoc_item_list() {
+                Position::before(items.syntax().clone())
+            } else {
+                Position::last_child_of(self.syntax().clone())
+            };
+            create_where_clause(position)
+        }
+        self.where_clause().unwrap()
+    }
+}
+
+impl GenericParamsOwnerEdit for ast::Struct {
+    fn get_or_create_where_clause(&self) -> WhereClause {
+        if self.where_clause().is_none() {
+            let tfl = self.field_list().and_then(|fl| match fl {
+                ast::FieldList::RecordFieldList(_) => None,
+                ast::FieldList::TupleFieldList(it) => Some(it),
+            });
+            let position = if let Some(tfl) = tfl {
+                Position::after(tfl.syntax().clone())
+            } else if let Some(gpl) = self.generic_param_list() {
+                Position::after(gpl.syntax().clone())
+            } else if let Some(name) = self.name() {
+                Position::after(name.syntax().clone())
+            } else {
+                Position::last_child_of(self.syntax().clone())
+            };
+            create_where_clause(position)
+        }
+        self.where_clause().unwrap()
+    }
+}
+
+impl GenericParamsOwnerEdit for ast::Enum {
+    fn get_or_create_where_clause(&self) -> WhereClause {
+        if self.where_clause().is_none() {
+            let position = if let Some(gpl) = self.generic_param_list() {
+                Position::after(gpl.syntax().clone())
+            } else if let Some(name) = self.name() {
+                Position::after(name.syntax().clone())
+            } else {
+                Position::last_child_of(self.syntax().clone())
+            };
+            create_where_clause(position)
+        }
+        self.where_clause().unwrap()
+    }
+}
+
+fn create_where_clause(position: Position) {
+    let where_clause: SyntaxElement =
+        make::where_clause(empty()).clone_for_update().syntax().clone().into();
+    ted::insert(position, where_clause);
+}
+
+impl ast::WhereClause {
+    pub fn add_predicate(&self, predicate: ast::WherePred) {
+        if let Some(pred) = self.predicates().last() {
+            if !pred.syntax().siblings_with_tokens(Direction::Next).any(|it| it.kind() == T![,]) {
+                ted::append_child_raw(self.syntax().clone(), make::token(T![,]));
+            }
+        }
+        ted::append_child(self.syntax().clone(), predicate.syntax().clone())
+    }
+}
+
+impl ast::TypeBoundList {
+    pub fn remove(&self) {
+        if let Some(colon) =
+            self.syntax().siblings_with_tokens(Direction::Prev).find(|it| it.kind() == T![:])
+        {
+            ted::remove_all(colon..=self.syntax().clone().into())
+        } else {
+            ted::remove(self.syntax().clone())
+        }
+    }
+}
diff --git a/crates/syntax/src/ast/generated/nodes.rs b/crates/syntax/src/ast/generated/nodes.rs
index 064931aec..6097178b6 100644
--- a/crates/syntax/src/ast/generated/nodes.rs
+++ b/crates/syntax/src/ast/generated/nodes.rs
@@ -1336,6 +1336,7 @@ pub enum Expr {
     Literal(Literal),
     LoopExpr(LoopExpr),
     MacroCall(MacroCall),
+    MacroStmts(MacroStmts),
     MatchExpr(MatchExpr),
     MethodCallExpr(MethodCallExpr),
     ParenExpr(ParenExpr),
@@ -3034,6 +3035,9 @@ impl From<LoopExpr> for Expr {
 impl From<MacroCall> for Expr {
     fn from(node: MacroCall) -> Expr { Expr::MacroCall(node) }
 }
+impl From<MacroStmts> for Expr {
+    fn from(node: MacroStmts) -> Expr { Expr::MacroStmts(node) }
+}
 impl From<MatchExpr> for Expr {
     fn from(node: MatchExpr) -> Expr { Expr::MatchExpr(node) }
 }
@@ -3078,8 +3082,8 @@ impl AstNode for Expr {
         match kind {
             ARRAY_EXPR | AWAIT_EXPR | BIN_EXPR | BLOCK_EXPR | BOX_EXPR | BREAK_EXPR | CALL_EXPR
             | CAST_EXPR | CLOSURE_EXPR | CONTINUE_EXPR | EFFECT_EXPR | FIELD_EXPR | FOR_EXPR
-            | IF_EXPR | INDEX_EXPR | LITERAL | LOOP_EXPR | MACRO_CALL | MATCH_EXPR
-            | METHOD_CALL_EXPR | PAREN_EXPR | PATH_EXPR | PREFIX_EXPR | RANGE_EXPR
+            | IF_EXPR | INDEX_EXPR | LITERAL | LOOP_EXPR | MACRO_CALL | MACRO_STMTS
+            | MATCH_EXPR | METHOD_CALL_EXPR | PAREN_EXPR | PATH_EXPR | PREFIX_EXPR | RANGE_EXPR
             | RECORD_EXPR | REF_EXPR | RETURN_EXPR | TRY_EXPR | TUPLE_EXPR | WHILE_EXPR
             | YIELD_EXPR => true,
             _ => false,
@@ -3105,6 +3109,7 @@ impl AstNode for Expr {
             LITERAL => Expr::Literal(Literal { syntax }),
             LOOP_EXPR => Expr::LoopExpr(LoopExpr { syntax }),
             MACRO_CALL => Expr::MacroCall(MacroCall { syntax }),
+            MACRO_STMTS => Expr::MacroStmts(MacroStmts { syntax }),
             MATCH_EXPR => Expr::MatchExpr(MatchExpr { syntax }),
             METHOD_CALL_EXPR => Expr::MethodCallExpr(MethodCallExpr { syntax }),
             PAREN_EXPR => Expr::ParenExpr(ParenExpr { syntax }),
@@ -3142,6 +3147,7 @@ impl AstNode for Expr {
             Expr::Literal(it) => &it.syntax,
             Expr::LoopExpr(it) => &it.syntax,
             Expr::MacroCall(it) => &it.syntax,
+            Expr::MacroStmts(it) => &it.syntax,
             Expr::MatchExpr(it) => &it.syntax,
             Expr::MethodCallExpr(it) => &it.syntax,
             Expr::ParenExpr(it) => &it.syntax,
diff --git a/crates/syntax/src/ast/make.rs b/crates/syntax/src/ast/make.rs
index 05a6b0b25..810c8d4c8 100644
--- a/crates/syntax/src/ast/make.rs
+++ b/crates/syntax/src/ast/make.rs
@@ -174,6 +174,11 @@ pub fn block_expr(
 pub fn expr_unit() -> ast::Expr {
     expr_from_text("()")
 }
+pub fn expr_literal(text: &str) -> ast::Literal {
+    assert_eq!(text.trim(), text);
+    ast_from_text(&format!("fn f() {{ let _ = {}; }}", text))
+}
+
 pub fn expr_empty_block() -> ast::Expr {
     expr_from_text("{}")
 }
@@ -390,6 +395,7 @@ pub fn token(kind: SyntaxKind) -> SyntaxToken {
     tokens::SOURCE_FILE
         .tree()
         .syntax()
+        .clone_for_update()
         .descendants_with_tokens()
         .filter_map(|it| it.into_token())
         .find(|it| it.kind() == kind)
@@ -544,6 +550,7 @@ pub mod tokens {
         SOURCE_FILE
             .tree()
             .syntax()
+            .clone_for_update()
             .descendants_with_tokens()
             .filter_map(|it| it.into_token())
             .find(|it| it.kind() == WHITESPACE && it.text() == " ")
@@ -569,13 +576,16 @@ pub mod tokens {
     }
 
     pub fn single_newline() -> SyntaxToken {
-        SOURCE_FILE
+        let res = SOURCE_FILE
             .tree()
             .syntax()
+            .clone_for_update()
             .descendants_with_tokens()
             .filter_map(|it| it.into_token())
             .find(|it| it.kind() == WHITESPACE && it.text() == "\n")
-            .unwrap()
+            .unwrap();
+        res.detach();
+        res
     }
 
     pub fn blank_line() -> SyntaxToken {
diff --git a/crates/syntax/src/ast/node_ext.rs b/crates/syntax/src/ast/node_ext.rs
index 52ac97c84..0b0d39a75 100644
--- a/crates/syntax/src/ast/node_ext.rs
+++ b/crates/syntax/src/ast/node_ext.rs
@@ -34,7 +34,9 @@ impl ast::NameRef {
 }
 
 fn text_of_first_token(node: &SyntaxNode) -> &str {
-    node.green().children().next().and_then(|it| it.into_token()).unwrap().text()
+    let t =
+        node.green().children().next().and_then(|it| it.into_token()).unwrap().text().to_string();
+    Box::leak(Box::new(t))
 }
 
 pub enum Macro {
diff --git a/crates/syntax/src/lib.rs b/crates/syntax/src/lib.rs
index 09e212e8c..2a5c61171 100644
--- a/crates/syntax/src/lib.rs
+++ b/crates/syntax/src/lib.rs
@@ -38,6 +38,7 @@ pub mod ast;
 #[doc(hidden)]
 pub mod fuzz;
 pub mod utils;
+pub mod ted;
 
 use std::{marker::PhantomData, sync::Arc};
 
diff --git a/crates/syntax/src/parsing/reparsing.rs b/crates/syntax/src/parsing/reparsing.rs
index 3d637bf91..4ad50ab72 100644
--- a/crates/syntax/src/parsing/reparsing.rs
+++ b/crates/syntax/src/parsing/reparsing.rs
@@ -124,11 +124,7 @@ fn is_contextual_kw(text: &str) -> bool {
 fn find_reparsable_node(node: &SyntaxNode, range: TextRange) -> Option<(SyntaxNode, Reparser)> {
     let node = node.covering_element(range);
 
-    let mut ancestors = match node {
-        NodeOrToken::Token(it) => it.parent().ancestors(),
-        NodeOrToken::Node(it) => it.ancestors(),
-    };
-    ancestors.find_map(|node| {
+    node.ancestors().find_map(|node| {
         let first_child = node.first_child_or_token().map(|it| it.kind());
         let parent = node.parent().map(|it| it.kind());
         Reparser::for_node(node.kind(), first_child, parent).map(|r| (node, r))
diff --git a/crates/syntax/src/ted.rs b/crates/syntax/src/ted.rs
new file mode 100644
index 000000000..76f950ef9
--- /dev/null
+++ b/crates/syntax/src/ted.rs
@@ -0,0 +1,126 @@
+//! Primitive tree editor, ed for trees.
+//!
+//! The `_raw`-suffixed functions insert elements as is, unsuffixed versions fix
+//! up elements around the edges.
+use std::ops::RangeInclusive;
+
+use parser::T;
+
+use crate::{ast::make, SyntaxElement, SyntaxKind, SyntaxNode, SyntaxToken};
+
+#[derive(Debug)]
+pub struct Position {
+    repr: PositionRepr,
+}
+
+#[derive(Debug)]
+enum PositionRepr {
+    FirstChild(SyntaxNode),
+    After(SyntaxElement),
+}
+
+impl Position {
+    pub fn after(elem: impl Into<SyntaxElement>) -> Position {
+        let repr = PositionRepr::After(elem.into());
+        Position { repr }
+    }
+    pub fn before(elem: impl Into<SyntaxElement>) -> Position {
+        let elem = elem.into();
+        let repr = match elem.prev_sibling_or_token() {
+            Some(it) => PositionRepr::After(it),
+            None => PositionRepr::FirstChild(elem.parent().unwrap()),
+        };
+        Position { repr }
+    }
+    pub fn first_child_of(node: impl Into<SyntaxNode>) -> Position {
+        let repr = PositionRepr::FirstChild(node.into());
+        Position { repr }
+    }
+    pub fn last_child_of(node: impl Into<SyntaxNode>) -> Position {
+        let node = node.into();
+        let repr = match node.last_child_or_token() {
+            Some(it) => PositionRepr::After(it),
+            None => PositionRepr::FirstChild(node),
+        };
+        Position { repr }
+    }
+}
+
+pub fn insert(position: Position, elem: impl Into<SyntaxElement>) {
+    insert_all(position, vec![elem.into()])
+}
+pub fn insert_raw(position: Position, elem: impl Into<SyntaxElement>) {
+    insert_all_raw(position, vec![elem.into()])
+}
+pub fn insert_all(position: Position, mut elements: Vec<SyntaxElement>) {
+    if let Some(first) = elements.first() {
+        if let Some(ws) = ws_before(&position, first) {
+            elements.insert(0, ws.into())
+        }
+    }
+    if let Some(last) = elements.last() {
+        if let Some(ws) = ws_after(&position, last) {
+            elements.push(ws.into())
+        }
+    }
+    insert_all_raw(position, elements)
+}
+pub fn insert_all_raw(position: Position, elements: Vec<SyntaxElement>) {
+    let (parent, index) = match position.repr {
+        PositionRepr::FirstChild(parent) => (parent, 0),
+        PositionRepr::After(child) => (child.parent().unwrap(), child.index() + 1),
+    };
+    parent.splice_children(index..index, elements);
+}
+
+pub fn remove(elem: impl Into<SyntaxElement>) {
+    let elem = elem.into();
+    remove_all(elem.clone()..=elem)
+}
+pub fn remove_all(range: RangeInclusive<SyntaxElement>) {
+    replace_all(range, Vec::new())
+}
+
+pub fn replace(old: impl Into<SyntaxElement>, new: impl Into<SyntaxElement>) {
+    let old = old.into();
+    replace_all(old.clone()..=old, vec![new.into()])
+}
+pub fn replace_all(range: RangeInclusive<SyntaxElement>, new: Vec<SyntaxElement>) {
+    let start = range.start().index();
+    let end = range.end().index();
+    let parent = range.start().parent().unwrap();
+    parent.splice_children(start..end + 1, new)
+}
+
+pub fn append_child(node: impl Into<SyntaxNode>, child: impl Into<SyntaxElement>) {
+    let position = Position::last_child_of(node);
+    insert(position, child)
+}
+pub fn append_child_raw(node: impl Into<SyntaxNode>, child: impl Into<SyntaxElement>) {
+    let position = Position::last_child_of(node);
+    insert_raw(position, child)
+}
+
+fn ws_before(position: &Position, new: &SyntaxElement) -> Option<SyntaxToken> {
+    let prev = match &position.repr {
+        PositionRepr::FirstChild(_) => return None,
+        PositionRepr::After(it) => it,
+    };
+    ws_between(prev, new)
+}
+fn ws_after(position: &Position, new: &SyntaxElement) -> Option<SyntaxToken> {
+    let next = match &position.repr {
+        PositionRepr::FirstChild(parent) => parent.first_child_or_token()?,
+        PositionRepr::After(sibling) => sibling.next_sibling_or_token()?,
+    };
+    ws_between(new, &next)
+}
+fn ws_between(left: &SyntaxElement, right: &SyntaxElement) -> Option<SyntaxToken> {
+    if left.kind() == SyntaxKind::WHITESPACE || right.kind() == SyntaxKind::WHITESPACE {
+        return None;
+    }
+    if right.kind() == T![;] || right.kind() == T![,] {
+        return None;
+    }
+    Some(make::tokens::single_space().into())
+}