aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2018-11-06 17:56:32 +0000
committerAleksey Kladov <[email protected]>2018-11-06 17:56:32 +0000
commitdafe747dcc069084fc8bc771c5dcf72e7cb9ec23 (patch)
tree7b17ad511518a23b06bb0b68e05b5b6c4aae4c76
parentd1b242262a6617b22140bddd0bed23115c260e74 (diff)
upstream basic tree algorithms to rowan
-rw-r--r--Cargo.lock6
-rw-r--r--crates/ra_syntax/Cargo.toml2
-rw-r--r--crates/ra_syntax/src/algo/mod.rs113
-rw-r--r--crates/ra_syntax/src/yellow/mod.rs2
4 files changed, 13 insertions, 110 deletions
diff --git a/Cargo.lock b/Cargo.lock
index fd1fb5ea5..80fbda23c 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -674,7 +674,7 @@ dependencies = [
674 "drop_bomb 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)", 674 "drop_bomb 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)",
675 "itertools 0.7.8 (registry+https://github.com/rust-lang/crates.io-index)", 675 "itertools 0.7.8 (registry+https://github.com/rust-lang/crates.io-index)",
676 "parking_lot 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)", 676 "parking_lot 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)",
677 "rowan 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", 677 "rowan 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
678 "test_utils 0.1.0", 678 "test_utils 0.1.0",
679 "text_unit 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)", 679 "text_unit 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
680 "unicode-xid 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", 680 "unicode-xid 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -795,7 +795,7 @@ dependencies = [
795 795
796[[package]] 796[[package]]
797name = "rowan" 797name = "rowan"
798version = "0.1.1" 798version = "0.1.2"
799source = "registry+https://github.com/rust-lang/crates.io-index" 799source = "registry+https://github.com/rust-lang/crates.io-index"
800dependencies = [ 800dependencies = [
801 "parking_lot 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)", 801 "parking_lot 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1346,7 +1346,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
1346"checksum relative-path 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0e7790c7f1cc73d831d28dc5a7deb316a006e7848e6a7f467cdb10a0a9e0fb1c" 1346"checksum relative-path 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0e7790c7f1cc73d831d28dc5a7deb316a006e7848e6a7f467cdb10a0a9e0fb1c"
1347"checksum remove_dir_all 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "3488ba1b9a2084d38645c4c08276a1752dcbf2c7130d74f1569681ad5d2799c5" 1347"checksum remove_dir_all 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "3488ba1b9a2084d38645c4c08276a1752dcbf2c7130d74f1569681ad5d2799c5"
1348"checksum ron 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c48677d8a9247a4e0d1f3f9cb4b0a8e29167fdc3c04f383a5e669cd7a960ae0f" 1348"checksum ron 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c48677d8a9247a4e0d1f3f9cb4b0a8e29167fdc3c04f383a5e669cd7a960ae0f"
1349"checksum rowan 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "4bb1f952404091f61bfea7cd09c564090a0fcee3d22223f98084e8756e01c04d" 1349"checksum rowan 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "795b1c830f5335e89f93415315518e9727307308c44c1e5adebe8a38f856c334"
1350"checksum rustc-demangle 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "bcfe5b13211b4d78e5c2cadfebd7769197d95c639c35a50057eb4c05de811395" 1350"checksum rustc-demangle 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "bcfe5b13211b4d78e5c2cadfebd7769197d95c639c35a50057eb4c05de811395"
1351"checksum rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7540fc8b0c49f096ee9c961cda096467dce8084bec6bdca2fc83895fd9b28cb8" 1351"checksum rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7540fc8b0c49f096ee9c961cda096467dce8084bec6bdca2fc83895fd9b28cb8"
1352"checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a" 1352"checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a"
diff --git a/crates/ra_syntax/Cargo.toml b/crates/ra_syntax/Cargo.toml
index de4b25e67..97d259570 100644
--- a/crates/ra_syntax/Cargo.toml
+++ b/crates/ra_syntax/Cargo.toml
@@ -12,7 +12,7 @@ unicode-xid = "0.1.0"
12itertools = "0.7.8" 12itertools = "0.7.8"
13drop_bomb = "0.1.4" 13drop_bomb = "0.1.4"
14parking_lot = "0.6.0" 14parking_lot = "0.6.0"
15rowan = "0.1.1" 15rowan = "0.1.2"
16text_unit = "0.1.5" 16text_unit = "0.1.5"
17 17
18[dev-dependencies] 18[dev-dependencies]
diff --git a/crates/ra_syntax/src/algo/mod.rs b/crates/ra_syntax/src/algo/mod.rs
index faf5a6211..4b3548ea9 100644
--- a/crates/ra_syntax/src/algo/mod.rs
+++ b/crates/ra_syntax/src/algo/mod.rs
@@ -1,116 +1,19 @@
1pub mod visit; 1pub mod visit;
2// pub mod walk;
3 2
4use crate::{text_utils::contains_offset_nonstrict, SyntaxNodeRef, TextRange, TextUnit}; 3use crate::{SyntaxNode, SyntaxNodeRef, TextRange, TextUnit};
5 4
6pub fn find_leaf_at_offset(node: SyntaxNodeRef, offset: TextUnit) -> LeafAtOffset { 5pub use rowan::LeafAtOffset;
7 let range = node.range();
8 assert!(
9 contains_offset_nonstrict(range, offset),
10 "Bad offset: range {:?} offset {:?}",
11 range,
12 offset
13 );
14 if range.is_empty() {
15 return LeafAtOffset::None;
16 }
17
18 if node.is_leaf() {
19 return LeafAtOffset::Single(node);
20 }
21
22 let mut children = node.children().filter(|child| {
23 let child_range = child.range();
24 !child_range.is_empty() && contains_offset_nonstrict(child_range, offset)
25 });
26
27 let left = children.next().unwrap();
28 let right = children.next();
29 assert!(children.next().is_none());
30
31 if let Some(right) = right {
32 match (
33 find_leaf_at_offset(left, offset),
34 find_leaf_at_offset(right, offset),
35 ) {
36 (LeafAtOffset::Single(left), LeafAtOffset::Single(right)) => {
37 LeafAtOffset::Between(left, right)
38 }
39 _ => unreachable!(),
40 }
41 } else {
42 find_leaf_at_offset(left, offset)
43 }
44}
45
46#[derive(Clone, Debug)]
47pub enum LeafAtOffset<'a> {
48 None,
49 Single(SyntaxNodeRef<'a>),
50 Between(SyntaxNodeRef<'a>, SyntaxNodeRef<'a>),
51}
52 6
53impl<'a> LeafAtOffset<'a> { 7pub fn find_leaf_at_offset(node: SyntaxNodeRef, offset: TextUnit) -> LeafAtOffset<SyntaxNodeRef> {
54 pub fn right_biased(self) -> Option<SyntaxNodeRef<'a>> { 8 match node.0.leaf_at_offset(offset) {
55 match self { 9 LeafAtOffset::None => LeafAtOffset::None,
56 LeafAtOffset::None => None, 10 LeafAtOffset::Single(n) => LeafAtOffset::Single(SyntaxNode(n)),
57 LeafAtOffset::Single(node) => Some(node), 11 LeafAtOffset::Between(l, r) => LeafAtOffset::Between(SyntaxNode(l), SyntaxNode(r)),
58 LeafAtOffset::Between(_, right) => Some(right),
59 }
60 }
61
62 pub fn left_biased(self) -> Option<SyntaxNodeRef<'a>> {
63 match self {
64 LeafAtOffset::None => None,
65 LeafAtOffset::Single(node) => Some(node),
66 LeafAtOffset::Between(left, _) => Some(left),
67 }
68 }
69}
70
71impl<'f> Iterator for LeafAtOffset<'f> {
72 type Item = SyntaxNodeRef<'f>;
73
74 fn next(&mut self) -> Option<SyntaxNodeRef<'f>> {
75 match *self {
76 LeafAtOffset::None => None,
77 LeafAtOffset::Single(node) => {
78 *self = LeafAtOffset::None;
79 Some(node)
80 }
81 LeafAtOffset::Between(left, right) => {
82 *self = LeafAtOffset::Single(right);
83 Some(left)
84 }
85 }
86 } 12 }
87} 13}
88 14
89pub fn find_covering_node(root: SyntaxNodeRef, range: TextRange) -> SyntaxNodeRef { 15pub fn find_covering_node(root: SyntaxNodeRef, range: TextRange) -> SyntaxNodeRef {
90 assert!( 16 SyntaxNode(root.0.covering_node(range))
91 range.is_subrange(&root.range()),
92 "node range: {:?}, target range: {:?}",
93 root.range(),
94 range,
95 );
96 let (left, right) = match (
97 find_leaf_at_offset(root, range.start()).right_biased(),
98 find_leaf_at_offset(root, range.end()).left_biased(),
99 ) {
100 (Some(l), Some(r)) => (l, r),
101 _ => return root,
102 };
103
104 common_ancestor(left, right)
105}
106
107fn common_ancestor<'a>(n1: SyntaxNodeRef<'a>, n2: SyntaxNodeRef<'a>) -> SyntaxNodeRef<'a> {
108 for p in n1.ancestors() {
109 if n2.ancestors().any(|a| a == p) {
110 return p;
111 }
112 }
113 panic!("Can't find common ancestor of {:?} and {:?}", n1, n2)
114} 17}
115 18
116pub fn generate<T>(seed: Option<T>, step: impl Fn(&T) -> Option<T>) -> impl Iterator<Item = T> { 19pub fn generate<T>(seed: Option<T>, step: impl Fn(&T) -> Option<T>) -> impl Iterator<Item = T> {
diff --git a/crates/ra_syntax/src/yellow/mod.rs b/crates/ra_syntax/src/yellow/mod.rs
index 6da948648..cacd89dc8 100644
--- a/crates/ra_syntax/src/yellow/mod.rs
+++ b/crates/ra_syntax/src/yellow/mod.rs
@@ -27,7 +27,7 @@ pub type RefRoot<'a> = ::rowan::RefRoot<'a, RaTypes>;
27pub type GreenNode = ::rowan::GreenNode<RaTypes>; 27pub type GreenNode = ::rowan::GreenNode<RaTypes>;
28 28
29#[derive(Clone, Copy)] 29#[derive(Clone, Copy)]
30pub struct SyntaxNode<R: TreeRoot<RaTypes> = OwnedRoot>(::rowan::SyntaxNode<RaTypes, R>); 30pub struct SyntaxNode<R: TreeRoot<RaTypes> = OwnedRoot>(pub(crate) ::rowan::SyntaxNode<RaTypes, R>);
31pub type SyntaxNodeRef<'a> = SyntaxNode<RefRoot<'a>>; 31pub type SyntaxNodeRef<'a> = SyntaxNode<RefRoot<'a>>;
32 32
33impl<R1, R2> PartialEq<SyntaxNode<R1>> for SyntaxNode<R2> 33impl<R1, R2> PartialEq<SyntaxNode<R1>> for SyntaxNode<R2>