aboutsummaryrefslogtreecommitdiff
path: root/crates/syntax/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/syntax/src')
-rw-r--r--crates/syntax/src/algo.rs417
1 files changed, 391 insertions, 26 deletions
diff --git a/crates/syntax/src/algo.rs b/crates/syntax/src/algo.rs
index ea199f9b8..4f9a7a6e8 100644
--- a/crates/syntax/src/algo.rs
+++ b/crates/syntax/src/algo.rs
@@ -2,11 +2,14 @@
2 2
3use std::{ 3use std::{
4 fmt, 4 fmt,
5 hash::BuildHasherDefault,
5 ops::{self, RangeInclusive}, 6 ops::{self, RangeInclusive},
6}; 7};
7 8
9use indexmap::IndexMap;
8use itertools::Itertools; 10use itertools::Itertools;
9use rustc_hash::FxHashMap; 11use rustc_hash::FxHashMap;
12use test_utils::mark;
10use text_edit::TextEditBuilder; 13use text_edit::TextEditBuilder;
11 14
12use crate::{ 15use crate::{
@@ -106,42 +109,56 @@ pub enum InsertPosition<T> {
106 After(T), 109 After(T),
107} 110}
108 111
112type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<rustc_hash::FxHasher>>;
113
114#[derive(Debug)]
109pub struct TreeDiff { 115pub struct TreeDiff {
110 replacements: FxHashMap<SyntaxElement, SyntaxElement>, 116 replacements: FxHashMap<SyntaxElement, SyntaxElement>,
117 deletions: Vec<SyntaxElement>,
118 // the vec as well as the indexmap are both here to preserve order
119 insertions: FxIndexMap<SyntaxElement, Vec<SyntaxElement>>,
111} 120}
112 121
113impl TreeDiff { 122impl TreeDiff {
114 pub fn into_text_edit(&self, builder: &mut TextEditBuilder) { 123 pub fn into_text_edit(&self, builder: &mut TextEditBuilder) {
124 for (anchor, to) in self.insertions.iter() {
125 to.iter().for_each(|to| builder.insert(anchor.text_range().end(), to.to_string()));
126 }
115 for (from, to) in self.replacements.iter() { 127 for (from, to) in self.replacements.iter() {
116 builder.replace(from.text_range(), to.to_string()) 128 builder.replace(from.text_range(), to.to_string())
117 } 129 }
130 for text_range in self.deletions.iter().map(SyntaxElement::text_range) {
131 builder.delete(text_range);
132 }
118 } 133 }
119 134
120 pub fn is_empty(&self) -> bool { 135 pub fn is_empty(&self) -> bool {
121 self.replacements.is_empty() 136 self.replacements.is_empty() && self.deletions.is_empty() && self.insertions.is_empty()
122 } 137 }
123} 138}
124 139
125/// Finds minimal the diff, which, applied to `from`, will result in `to`. 140/// Finds minimal the diff, which, applied to `from`, will result in `to`.
126/// 141///
127/// Specifically, returns a map whose keys are descendants of `from` and values 142/// Specifically, returns a structure that consists of a replacements, insertions and deletions
128/// are descendants of `to`, such that `replace_descendants(from, map) == to`. 143/// such that applying this map on `from` will result in `to`.
129/// 144///
130/// A trivial solution is a singleton map `{ from: to }`, but this function 145/// This function tries to find a fine-grained diff.
131/// tries to find a more fine-grained diff.
132pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff { 146pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
133 let mut buf = FxHashMap::default(); 147 let mut diff = TreeDiff {
134 // FIXME: this is both horrible inefficient and gives larger than 148 replacements: FxHashMap::default(),
135 // necessary diff. I bet there's a cool algorithm to diff trees properly. 149 insertions: FxIndexMap::default(),
136 go(&mut buf, from.clone().into(), to.clone().into()); 150 deletions: Vec::new(),
137 return TreeDiff { replacements: buf }; 151 };
138 152 let (from, to) = (from.clone().into(), to.clone().into());
139 fn go( 153
140 buf: &mut FxHashMap<SyntaxElement, SyntaxElement>, 154 // FIXME: this is horrible inefficient. I bet there's a cool algorithm to diff trees properly.
141 lhs: SyntaxElement, 155 if !syntax_element_eq(&from, &to) {
142 rhs: SyntaxElement, 156 go(&mut diff, from, to);
143 ) { 157 }
144 if lhs.kind() == rhs.kind() 158 return diff;
159
160 fn syntax_element_eq(lhs: &SyntaxElement, rhs: &SyntaxElement) -> bool {
161 lhs.kind() == rhs.kind()
145 && lhs.text_range().len() == rhs.text_range().len() 162 && lhs.text_range().len() == rhs.text_range().len()
146 && match (&lhs, &rhs) { 163 && match (&lhs, &rhs) {
147 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => { 164 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => {
@@ -150,18 +167,47 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
150 (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => lhs.text() == rhs.text(), 167 (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => lhs.text() == rhs.text(),
151 _ => false, 168 _ => false,
152 } 169 }
153 { 170 }
154 return; 171
155 } 172 fn go(diff: &mut TreeDiff, lhs: SyntaxElement, rhs: SyntaxElement) {
156 if let (Some(lhs), Some(rhs)) = (lhs.as_node(), rhs.as_node()) { 173 let (lhs, rhs) = match lhs.as_node().zip(rhs.as_node()) {
157 if lhs.children_with_tokens().count() == rhs.children_with_tokens().count() { 174 Some((lhs, rhs)) => (lhs, rhs),
158 for (lhs, rhs) in lhs.children_with_tokens().zip(rhs.children_with_tokens()) { 175 _ => {
159 go(buf, lhs, rhs) 176 mark::hit!(diff_node_token_replace);
160 } 177 diff.replacements.insert(lhs, rhs);
161 return; 178 return;
162 } 179 }
180 };
181
182 let mut rhs_children = rhs.children_with_tokens();
183 let mut lhs_children = lhs.children_with_tokens();
184 let mut last_lhs = None;
185 loop {
186 let lhs_child = lhs_children.next();
187 match (lhs_child.clone(), rhs_children.next()) {
188 (None, None) => break,
189 (None, Some(element)) => match last_lhs.clone() {
190 Some(prev) => {
191 mark::hit!(diff_insert);
192 diff.insertions.entry(prev).or_insert_with(Vec::new).push(element);
193 }
194 // first iteration, this means we got no anchor element to insert after
195 // therefor replace the parent node instead
196 None => {
197 mark::hit!(diff_replace_parent);
198 diff.replacements.insert(lhs.clone().into(), rhs.clone().into());
199 break;
200 }
201 },
202 (Some(element), None) => {
203 mark::hit!(diff_delete);
204 diff.deletions.push(element);
205 }
206 (Some(ref lhs_ele), Some(ref rhs_ele)) if syntax_element_eq(lhs_ele, rhs_ele) => {}
207 (Some(lhs_ele), Some(rhs_ele)) => go(diff, lhs_ele, rhs_ele),
208 }
209 last_lhs = lhs_child.or(last_lhs);
163 } 210 }
164 buf.insert(lhs, rhs);
165 } 211 }
166} 212}
167 213
@@ -404,3 +450,322 @@ fn to_green_element(element: SyntaxElement) -> NodeOrToken<rowan::GreenNode, row
404 NodeOrToken::Token(it) => it.green().clone().into(), 450 NodeOrToken::Token(it) => it.green().clone().into(),
405 } 451 }
406} 452}
453
454#[cfg(test)]
455mod tests {
456 use expect_test::{expect, Expect};
457 use itertools::Itertools;
458 use parser::SyntaxKind;
459 use test_utils::mark;
460 use text_edit::TextEdit;
461
462 use crate::{AstNode, SyntaxElement};
463
464 #[test]
465 fn replace_node_token() {
466 mark::check!(diff_node_token_replace);
467 check_diff(
468 r#"use node;"#,
469 r#"ident"#,
470 expect![[r#"
471 insertions:
472
473
474
475 replacements:
476
477 Line 0: Token([email protected] "use") -> ident
478
479 deletions:
480
481 Line 1: " "
482 Line 1: node
483 Line 1: ;
484 "#]],
485 );
486 }
487
488 #[test]
489 fn insert() {
490 mark::check!(diff_insert);
491 check_diff(
492 r#"use foo;"#,
493 r#"use foo;
494use bar;"#,
495 expect![[r#"
496 insertions:
497
498 Line 0: Node([email protected])
499 -> "\n"
500 -> use bar;
501
502 replacements:
503
504
505
506 deletions:
507
508
509 "#]],
510 );
511 }
512
513 #[test]
514 fn replace_parent() {
515 mark::check!(diff_replace_parent);
516 check_diff(
517 r#""#,
518 r#"use foo::bar;"#,
519 expect![[r#"
520 insertions:
521
522
523
524 replacements:
525
526 Line 0: Node([email protected]) -> use foo::bar;
527
528 deletions:
529
530
531 "#]],
532 );
533 }
534
535 #[test]
536 fn delete() {
537 mark::check!(diff_delete);
538 check_diff(
539 r#"use foo;
540 use bar;"#,
541 r#"use foo;"#,
542 expect![[r#"
543 insertions:
544
545
546
547 replacements:
548
549
550
551 deletions:
552
553 Line 1: "\n "
554 Line 2: use bar;
555 "#]],
556 );
557 }
558
559 #[test]
560 fn insert_use() {
561 check_diff(
562 r#"
563use expect_test::{expect, Expect};
564
565use crate::AstNode;
566"#,
567 r#"
568use expect_test::{expect, Expect};
569use text_edit::TextEdit;
570
571use crate::AstNode;
572"#,
573 expect![[r#"
574 insertions:
575
576 Line 4: Token([email protected] "\n")
577 -> use crate::AstNode;
578 -> "\n"
579
580 replacements:
581
582 Line 2: Token([email protected] "\n\n") -> "\n"
583 Line 4: Token([email protected] "crate") -> text_edit
584 Line 4: Token([email protected] "AstNode") -> TextEdit
585 Line 4: Token([email protected] "\n") -> "\n\n"
586
587 deletions:
588
589
590 "#]],
591 )
592 }
593
594 #[test]
595 fn remove_use() {
596 check_diff(
597 r#"
598use expect_test::{expect, Expect};
599use text_edit::TextEdit;
600
601use crate::AstNode;
602"#,
603 r#"
604use expect_test::{expect, Expect};
605
606use crate::AstNode;
607"#,
608 expect![[r#"
609 insertions:
610
611
612
613 replacements:
614
615 Line 2: Token([email protected] "\n") -> "\n\n"
616 Line 3: Node([email protected]) -> crate
617 Line 3: Token([email protected] "TextEdit") -> AstNode
618 Line 3: Token([email protected] "\n\n") -> "\n"
619
620 deletions:
621
622 Line 4: use crate::AstNode;
623 Line 5: "\n"
624 "#]],
625 )
626 }
627
628 #[test]
629 fn merge_use() {
630 check_diff(
631 r#"
632use std::{
633 fmt,
634 hash::BuildHasherDefault,
635 ops::{self, RangeInclusive},
636};
637"#,
638 r#"
639use std::fmt;
640use std::hash::BuildHasherDefault;
641use std::ops::{self, RangeInclusive};
642"#,
643 expect![[r#"
644 insertions:
645
646 Line 2: Node([email protected])
647 -> ::
648 -> fmt
649 Line 6: Token([email protected] "\n")
650 -> use std::hash::BuildHasherDefault;
651 -> "\n"
652 -> use std::ops::{self, RangeInclusive};
653 -> "\n"
654
655 replacements:
656
657 Line 2: Token([email protected] "std") -> std
658
659 deletions:
660
661 Line 2: ::
662 Line 2: {
663 fmt,
664 hash::BuildHasherDefault,
665 ops::{self, RangeInclusive},
666 }
667 "#]],
668 )
669 }
670
671 #[test]
672 fn early_return_assist() {
673 check_diff(
674 r#"
675fn main() {
676 if let Ok(x) = Err(92) {
677 foo(x);
678 }
679}
680 "#,
681 r#"
682fn main() {
683 let x = match Err(92) {
684 Ok(it) => it,
685 _ => return,
686 };
687 foo(x);
688}
689 "#,
690 expect![[r#"
691 insertions:
692
693 Line 3: Node([email protected])
694 -> " "
695 -> match Err(92) {
696 Ok(it) => it,
697 _ => return,
698 }
699 -> ;
700 Line 5: Token([email protected] "}")
701 -> "\n"
702 -> }
703
704 replacements:
705
706 Line 3: Token([email protected] "if") -> let
707 Line 3: Token([email protected] "let") -> x
708 Line 3: Node([email protected]) -> =
709 Line 5: Token([email protected] "\n") -> "\n "
710 Line 5: Token([email protected] "}") -> foo(x);
711
712 deletions:
713
714 Line 3: " "
715 Line 3: Ok(x)
716 Line 3: " "
717 Line 3: =
718 Line 3: " "
719 Line 3: Err(92)
720 "#]],
721 )
722 }
723
724 fn check_diff(from: &str, to: &str, expected_diff: Expect) {
725 let from_node = crate::SourceFile::parse(from).tree().syntax().clone();
726 let to_node = crate::SourceFile::parse(to).tree().syntax().clone();
727 let diff = super::diff(&from_node, &to_node);
728
729 let line_number =
730 |syn: &SyntaxElement| from[..syn.text_range().start().into()].lines().count();
731
732 let fmt_syntax = |syn: &SyntaxElement| match syn.kind() {
733 SyntaxKind::WHITESPACE => format!("{:?}", syn.to_string()),
734 _ => format!("{}", syn),
735 };
736
737 let insertions = diff.insertions.iter().format_with("\n", |(k, v), f| {
738 f(&format!(
739 "Line {}: {:?}\n-> {}",
740 line_number(k),
741 k,
742 v.iter().format_with("\n-> ", |v, f| f(&fmt_syntax(v)))
743 ))
744 });
745
746 let replacements = diff
747 .replacements
748 .iter()
749 .sorted_by_key(|(syntax, _)| syntax.text_range().start())
750 .format_with("\n", |(k, v), f| {
751 f(&format!("Line {}: {:?} -> {}", line_number(k), k, fmt_syntax(v)))
752 });
753
754 let deletions = diff
755 .deletions
756 .iter()
757 .format_with("\n", |v, f| f(&format!("Line {}: {}", line_number(v), &fmt_syntax(v))));
758
759 let actual = format!(
760 "insertions:\n\n{}\n\nreplacements:\n\n{}\n\ndeletions:\n\n{}\n",
761 insertions, replacements, deletions
762 );
763 expected_diff.assert_eq(&actual);
764
765 let mut from = from.to_owned();
766 let mut text_edit = TextEdit::builder();
767 diff.into_text_edit(&mut text_edit);
768 text_edit.finish().apply(&mut from);
769 assert_eq!(&*from, to, "diff did not turn `from` to `to`");
770 }
771}