aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLukas Wirth <[email protected]>2020-10-26 14:40:08 +0000
committerLukas Wirth <[email protected]>2020-10-26 15:03:37 +0000
commit750ab54573908774d81be82979bc1d328c43c35e (patch)
tree7538a2bc2b547c8348eb87956d2e69d6bb9005e6
parent1a84cadc88e23fead7435384bfd986dc08081509 (diff)
Do insertion lookahead in algo::diff
-rw-r--r--crates/ide/src/diagnostics.rs2
-rw-r--r--crates/syntax/src/algo.rs160
2 files changed, 121 insertions, 41 deletions
diff --git a/crates/ide/src/diagnostics.rs b/crates/ide/src/diagnostics.rs
index d0ee58858..1c7f02763 100644
--- a/crates/ide/src/diagnostics.rs
+++ b/crates/ide/src/diagnostics.rs
@@ -613,7 +613,7 @@ fn main() {
613pub struct Foo { pub a: i32, pub b: i32 } 613pub struct Foo { pub a: i32, pub b: i32 }
614"#, 614"#,
615 r#" 615 r#"
616fn some(, b: ()} {} 616fn some(, b: ()) {}
617fn items() {} 617fn items() {}
618fn here() {} 618fn here() {}
619 619
diff --git a/crates/syntax/src/algo.rs b/crates/syntax/src/algo.rs
index 065035fe6..9dc7182bd 100644
--- a/crates/syntax/src/algo.rs
+++ b/crates/syntax/src/algo.rs
@@ -137,7 +137,7 @@ impl TreeDiff {
137 } 137 }
138} 138}
139 139
140/// Finds minimal the diff, which, applied to `from`, will result in `to`. 140/// Finds a (potentially minimal) diff, which, applied to `from`, will result in `to`.
141/// 141///
142/// Specifically, returns a structure that consists of a replacements, insertions and deletions 142/// Specifically, returns a structure that consists of a replacements, insertions and deletions
143/// such that applying this map on `from` will result in `to`. 143/// such that applying this map on `from` will result in `to`.
@@ -151,7 +151,6 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
151 }; 151 };
152 let (from, to) = (from.clone().into(), to.clone().into()); 152 let (from, to) = (from.clone().into(), to.clone().into());
153 153
154 // FIXME: this is horrible inefficient. I bet there's a cool algorithm to diff trees properly.
155 if !syntax_element_eq(&from, &to) { 154 if !syntax_element_eq(&from, &to) {
156 go(&mut diff, from, to); 155 go(&mut diff, from, to);
157 } 156 }
@@ -169,6 +168,7 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
169 } 168 }
170 } 169 }
171 170
171 // FIXME: this is horrible inefficient. I bet there's a cool algorithm to diff trees properly.
172 fn go(diff: &mut TreeDiff, lhs: SyntaxElement, rhs: SyntaxElement) { 172 fn go(diff: &mut TreeDiff, lhs: SyntaxElement, rhs: SyntaxElement) {
173 let (lhs, rhs) = match lhs.as_node().zip(rhs.as_node()) { 173 let (lhs, rhs) = match lhs.as_node().zip(rhs.as_node()) {
174 Some((lhs, rhs)) => (lhs, rhs), 174 Some((lhs, rhs)) => (lhs, rhs),
@@ -179,6 +179,8 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
179 } 179 }
180 }; 180 };
181 181
182 let mut look_ahead_scratch = Vec::default();
183
182 let mut rhs_children = rhs.children_with_tokens(); 184 let mut rhs_children = rhs.children_with_tokens();
183 let mut lhs_children = lhs.children_with_tokens(); 185 let mut lhs_children = lhs.children_with_tokens();
184 let mut last_lhs = None; 186 let mut last_lhs = None;
@@ -204,7 +206,31 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
204 diff.deletions.push(element); 206 diff.deletions.push(element);
205 } 207 }
206 (Some(ref lhs_ele), Some(ref rhs_ele)) if syntax_element_eq(lhs_ele, rhs_ele) => {} 208 (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), 209 (Some(lhs_ele), Some(rhs_ele)) => {
210 // nodes differ, look for lhs_ele in rhs, if its found we can mark everything up
211 // until that element as insertions. This is important to keep the diff minimal
212 // in regards to insertions that have been actually done, this is important for
213 // use insertions as we do not want to replace the entire module node.
214 look_ahead_scratch.push(rhs_ele.clone());
215 let mut rhs_children_clone = rhs_children.clone();
216 let mut insert = false;
217 while let Some(rhs_child) = rhs_children_clone.next() {
218 if syntax_element_eq(&lhs_ele, &rhs_child) {
219 mark::hit!(diff_insertions);
220 insert = true;
221 break;
222 } else {
223 look_ahead_scratch.push(rhs_child);
224 }
225 }
226 let drain = look_ahead_scratch.drain(..);
227 if let Some(prev) = last_lhs.clone().filter(|_| insert) {
228 diff.insertions.entry(prev).or_insert_with(Vec::new).extend(drain);
229 rhs_children = rhs_children_clone;
230 } else {
231 go(diff, lhs_ele, rhs_ele)
232 }
233 }
208 } 234 }
209 last_lhs = lhs_child.or(last_lhs); 235 last_lhs = lhs_child.or(last_lhs);
210 } 236 }
@@ -292,7 +318,6 @@ fn _replace_children(
292#[derive(Debug, PartialEq, Eq, Hash)] 318#[derive(Debug, PartialEq, Eq, Hash)]
293enum InsertPos { 319enum InsertPos {
294 FirstChildOf(SyntaxNode), 320 FirstChildOf(SyntaxNode),
295 // Before(SyntaxElement),
296 After(SyntaxElement), 321 After(SyntaxElement),
297} 322}
298 323
@@ -603,18 +628,44 @@ mod tests {
603 } 628 }
604 629
605 #[test] 630 #[test]
606 fn insert() { 631 fn replace_parent() {
632 mark::check!(diff_replace_parent);
633 check_diff(
634 r#""#,
635 r#"use foo::bar;"#,
636 expect![[r#"
637 insertions:
638
639
640
641 replacements:
642
643 Line 0: Node([email protected]) -> use foo::bar;
644
645 deletions:
646
647
648 "#]],
649 );
650 }
651
652 #[test]
653 fn insert_last() {
607 mark::check!(diff_insert); 654 mark::check!(diff_insert);
608 check_diff( 655 check_diff(
609 r#"use foo;"#, 656 r#"
610 r#"use foo; 657use foo;
611use bar;"#, 658use bar;"#,
659 r#"
660use foo;
661use bar;
662use baz;"#,
612 expect![[r#" 663 expect![[r#"
613 insertions: 664 insertions:
614 665
615 Line 0: Node([email protected]) 666 Line 2: Node(USE@10..18)
616 -> "\n" 667 -> "\n"
617 -> use bar; 668 -> use baz;
618 669
619 replacements: 670 replacements:
620 671
@@ -628,29 +679,63 @@ use bar;"#,
628 } 679 }
629 680
630 #[test] 681 #[test]
631 fn replace_parent() { 682 fn insert_middle() {
632 mark::check!(diff_replace_parent);
633 check_diff( 683 check_diff(
634 r#""#, 684 r#"
635 r#"use foo::bar;"#, 685use foo;
686use baz;"#,
687 r#"
688use foo;
689use bar;
690use baz;"#,
636 expect![[r#" 691 expect![[r#"
637 insertions: 692 insertions:
638 693
694 Line 2: Token([email protected] "\n")
695 -> use bar;
696 -> "\n"
697
698 replacements:
699
700
701
702 deletions:
703
704
705 "#]],
706 )
707 }
708
709 #[test]
710 fn insert_first() {
711 check_diff(
712 r#"
713use bar;
714use baz;"#,
715 r#"
716use foo;
717use bar;
718use baz;"#,
719 expect![[r#"
720 insertions:
639 721
722 Line 0: Token([email protected] "\n")
723 -> use foo;
724 -> "\n"
640 725
641 replacements: 726 replacements:
642 727
643 Line 0: Node([email protected]) -> use foo::bar; 728
644 729
645 deletions: 730 deletions:
646 731
647 732
648 "#]], 733 "#]],
649 ); 734 )
650 } 735 }
651 736
652 #[test] 737 #[test]
653 fn delete() { 738 fn delete_last() {
654 mark::check!(diff_delete); 739 mark::check!(diff_delete);
655 check_diff( 740 check_diff(
656 r#"use foo; 741 r#"use foo;
@@ -674,52 +759,50 @@ use bar;"#,
674 } 759 }
675 760
676 #[test] 761 #[test]
677 fn insert_use() { 762 fn delete_middle() {
763 mark::check!(diff_insertions);
678 check_diff( 764 check_diff(
679 r#" 765 r#"
680use expect_test::{expect, Expect}; 766use expect_test::{expect, Expect};
767use text_edit::TextEdit;
681 768
682use crate::AstNode; 769use crate::AstNode;
683"#, 770"#,
684 r#" 771 r#"
685use expect_test::{expect, Expect}; 772use expect_test::{expect, Expect};
686use text_edit::TextEdit;
687 773
688use crate::AstNode; 774use crate::AstNode;
689"#, 775"#,
690 expect![[r#" 776 expect![[r#"
691 insertions: 777 insertions:
692 778
693 Line 4: Token([email protected] "\n") 779 Line 1: Node([email protected])
780 -> "\n\n"
694 -> use crate::AstNode; 781 -> use crate::AstNode;
695 -> "\n"
696 782
697 replacements: 783 replacements:
698 784
699 Line 2: Token([email protected] "\n\n") -> "\n"
700 Line 4: Token([email protected] "crate") -> text_edit
701 Line 4: Token([email protected] "AstNode") -> TextEdit
702 Line 4: Token([email protected] "\n") -> "\n\n"
703 785
704 deletions:
705 786
787 deletions:
706 788
789 Line 2: use text_edit::TextEdit;
790 Line 3: "\n\n"
791 Line 4: use crate::AstNode;
792 Line 5: "\n"
707 "#]], 793 "#]],
708 ) 794 )
709 } 795 }
710 796
711 #[test] 797 #[test]
712 fn remove_use() { 798 fn delete_first() {
713 check_diff( 799 check_diff(
714 r#" 800 r#"
715use expect_test::{expect, Expect};
716use text_edit::TextEdit; 801use text_edit::TextEdit;
717 802
718use crate::AstNode; 803use crate::AstNode;
719"#, 804"#,
720 r#" 805 r#"
721use expect_test::{expect, Expect};
722
723use crate::AstNode; 806use crate::AstNode;
724"#, 807"#,
725 expect![[r#" 808 expect![[r#"
@@ -729,15 +812,14 @@ use crate::AstNode;
729 812
730 replacements: 813 replacements:
731 814
732 Line 2: Token([email protected] "\n") -> "\n\n" 815 Line 2: Node([email protected]) -> crate
733 Line 3: Node([email protected]) -> crate 816 Line 2: Token([email protected] "TextEdit") -> AstNode
734 Line 3: Token([email protected] "TextEdit") -> AstNode 817 Line 2: Token([email protected] "\n\n") -> "\n"
735 Line 3: Token([email protected] "\n\n") -> "\n"
736 818
737 deletions: 819 deletions:
738 820
739 Line 4: use crate::AstNode; 821 Line 3: use crate::AstNode;
740 Line 5: "\n" 822 Line 4: "\n"
741 "#]], 823 "#]],
742 ) 824 )
743 } 825 }
@@ -814,17 +896,15 @@ fn main() {
814 _ => return, 896 _ => return,
815 } 897 }
816 -> ; 898 -> ;
817 Line 5: Token(R_CURLY@64..65 "}") 899 Line 3: Node(IF_EXPR@17..63)
818 -> "\n" 900 -> "\n "
819 -> } 901 -> foo(x);
820 902
821 replacements: 903 replacements:
822 904
823 Line 3: Token([email protected] "if") -> let 905 Line 3: Token([email protected] "if") -> let
824 Line 3: Token([email protected] "let") -> x 906 Line 3: Token([email protected] "let") -> x
825 Line 3: Node([email protected]) -> = 907 Line 3: Node([email protected]) -> =
826 Line 5: Token([email protected] "\n") -> "\n "
827 Line 5: Token([email protected] "}") -> foo(x);
828 908
829 deletions: 909 deletions:
830 910