aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--crates/syntax/Cargo.toml3
-rw-r--r--crates/syntax/src/algo.rs328
2 files changed, 327 insertions, 4 deletions
diff --git a/crates/syntax/Cargo.toml b/crates/syntax/Cargo.toml
index 8c0b0abbb..aa39ce554 100644
--- a/crates/syntax/Cargo.toml
+++ b/crates/syntax/Cargo.toml
@@ -27,10 +27,9 @@ serde = { version = "1.0.106", features = ["derive"] }
27stdx = { path = "../stdx", version = "0.0.0" } 27stdx = { path = "../stdx", version = "0.0.0" }
28text_edit = { path = "../text_edit", version = "0.0.0" } 28text_edit = { path = "../text_edit", version = "0.0.0" }
29parser = { path = "../parser", version = "0.0.0" } 29parser = { path = "../parser", version = "0.0.0" }
30test_utils = { path = "../test_utils" }
30 31
31[dev-dependencies] 32[dev-dependencies]
32walkdir = "2.3.1" 33walkdir = "2.3.1"
33rayon = "1" 34rayon = "1"
34expect-test = "1.0" 35expect-test = "1.0"
35
36test_utils = { path = "../test_utils" }
diff --git a/crates/syntax/src/algo.rs b/crates/syntax/src/algo.rs
index f53875f28..4f9a7a6e8 100644
--- a/crates/syntax/src/algo.rs
+++ b/crates/syntax/src/algo.rs
@@ -9,6 +9,7 @@ use std::{
9use indexmap::IndexMap; 9use indexmap::IndexMap;
10use itertools::Itertools; 10use itertools::Itertools;
11use rustc_hash::FxHashMap; 11use rustc_hash::FxHashMap;
12use test_utils::mark;
12use text_edit::TextEditBuilder; 13use text_edit::TextEditBuilder;
13 14
14use crate::{ 15use crate::{
@@ -110,6 +111,7 @@ pub enum InsertPosition<T> {
110 111
111type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<rustc_hash::FxHasher>>; 112type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<rustc_hash::FxHasher>>;
112 113
114#[derive(Debug)]
113pub struct TreeDiff { 115pub struct TreeDiff {
114 replacements: FxHashMap<SyntaxElement, SyntaxElement>, 116 replacements: FxHashMap<SyntaxElement, SyntaxElement>,
115 deletions: Vec<SyntaxElement>, 117 deletions: Vec<SyntaxElement>,
@@ -149,8 +151,7 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
149 }; 151 };
150 let (from, to) = (from.clone().into(), to.clone().into()); 152 let (from, to) = (from.clone().into(), to.clone().into());
151 153
152 // FIXME: this is both horrible inefficient and gives larger than 154 // FIXME: this is horrible inefficient. I bet there's a cool algorithm to diff trees properly.
153 // necessary diff. I bet there's a cool algorithm to diff trees properly.
154 if !syntax_element_eq(&from, &to) { 155 if !syntax_element_eq(&from, &to) {
155 go(&mut diff, from, to); 156 go(&mut diff, from, to);
156 } 157 }
@@ -172,6 +173,7 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
172 let (lhs, rhs) = match lhs.as_node().zip(rhs.as_node()) { 173 let (lhs, rhs) = match lhs.as_node().zip(rhs.as_node()) {
173 Some((lhs, rhs)) => (lhs, rhs), 174 Some((lhs, rhs)) => (lhs, rhs),
174 _ => { 175 _ => {
176 mark::hit!(diff_node_token_replace);
175 diff.replacements.insert(lhs, rhs); 177 diff.replacements.insert(lhs, rhs);
176 return; 178 return;
177 } 179 }
@@ -186,16 +188,19 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
186 (None, None) => break, 188 (None, None) => break,
187 (None, Some(element)) => match last_lhs.clone() { 189 (None, Some(element)) => match last_lhs.clone() {
188 Some(prev) => { 190 Some(prev) => {
191 mark::hit!(diff_insert);
189 diff.insertions.entry(prev).or_insert_with(Vec::new).push(element); 192 diff.insertions.entry(prev).or_insert_with(Vec::new).push(element);
190 } 193 }
191 // first iteration, this means we got no anchor element to insert after 194 // first iteration, this means we got no anchor element to insert after
192 // therefor replace the parent node instead 195 // therefor replace the parent node instead
193 None => { 196 None => {
197 mark::hit!(diff_replace_parent);
194 diff.replacements.insert(lhs.clone().into(), rhs.clone().into()); 198 diff.replacements.insert(lhs.clone().into(), rhs.clone().into());
195 break; 199 break;
196 } 200 }
197 }, 201 },
198 (Some(element), None) => { 202 (Some(element), None) => {
203 mark::hit!(diff_delete);
199 diff.deletions.push(element); 204 diff.deletions.push(element);
200 } 205 }
201 (Some(ref lhs_ele), Some(ref rhs_ele)) if syntax_element_eq(lhs_ele, rhs_ele) => {} 206 (Some(ref lhs_ele), Some(ref rhs_ele)) if syntax_element_eq(lhs_ele, rhs_ele) => {}
@@ -445,3 +450,322 @@ fn to_green_element(element: SyntaxElement) -> NodeOrToken<rowan::GreenNode, row
445 NodeOrToken::Token(it) => it.green().clone().into(), 450 NodeOrToken::Token(it) => it.green().clone().into(),
446 } 451 }
447} 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}