diff options
Diffstat (limited to 'src/algo/mod.rs')
-rw-r--r-- | src/algo/mod.rs | 123 |
1 files changed, 0 insertions, 123 deletions
diff --git a/src/algo/mod.rs b/src/algo/mod.rs deleted file mode 100644 index d2de70fd4..000000000 --- a/src/algo/mod.rs +++ /dev/null | |||
@@ -1,123 +0,0 @@ | |||
1 | pub mod walk; | ||
2 | |||
3 | use {SyntaxNodeRef, TextUnit, TextRange}; | ||
4 | |||
5 | pub fn find_leaf_at_offset(node: SyntaxNodeRef, offset: TextUnit) -> LeafAtOffset { | ||
6 | let range = node.range(); | ||
7 | assert!( | ||
8 | contains_offset_nonstrict(range, offset), | ||
9 | "Bad offset: range {:?} offset {:?}", range, offset | ||
10 | ); | ||
11 | if range.is_empty() { | ||
12 | return LeafAtOffset::None; | ||
13 | } | ||
14 | |||
15 | if node.is_leaf() { | ||
16 | return LeafAtOffset::Single(node); | ||
17 | } | ||
18 | |||
19 | let mut children = node.children() | ||
20 | .filter(|child| { | ||
21 | let child_range = child.range(); | ||
22 | !child_range.is_empty() && contains_offset_nonstrict(child_range, offset) | ||
23 | }); | ||
24 | |||
25 | let left = children.next().unwrap(); | ||
26 | let right = children.next(); | ||
27 | assert!(children.next().is_none()); | ||
28 | return if let Some(right) = right { | ||
29 | match (find_leaf_at_offset(left, offset), find_leaf_at_offset(right, offset)) { | ||
30 | (LeafAtOffset::Single(left), LeafAtOffset::Single(right)) => | ||
31 | LeafAtOffset::Between(left, right), | ||
32 | _ => unreachable!() | ||
33 | } | ||
34 | } else { | ||
35 | find_leaf_at_offset(left, offset) | ||
36 | }; | ||
37 | } | ||
38 | |||
39 | #[derive(Clone, Copy, Debug)] | ||
40 | pub enum LeafAtOffset<'a> { | ||
41 | None, | ||
42 | Single(SyntaxNodeRef<'a>), | ||
43 | Between(SyntaxNodeRef<'a>, SyntaxNodeRef<'a>) | ||
44 | } | ||
45 | |||
46 | impl<'a> LeafAtOffset<'a> { | ||
47 | pub fn right_biased(self) -> Option<SyntaxNodeRef<'a>> { | ||
48 | match self { | ||
49 | LeafAtOffset::None => None, | ||
50 | LeafAtOffset::Single(node) => Some(node), | ||
51 | LeafAtOffset::Between(_, right) => Some(right) | ||
52 | } | ||
53 | } | ||
54 | |||
55 | pub fn left_biased(self) -> Option<SyntaxNodeRef<'a>> { | ||
56 | match self { | ||
57 | LeafAtOffset::None => None, | ||
58 | LeafAtOffset::Single(node) => Some(node), | ||
59 | LeafAtOffset::Between(left, _) => Some(left) | ||
60 | } | ||
61 | } | ||
62 | } | ||
63 | |||
64 | impl<'f> Iterator for LeafAtOffset<'f> { | ||
65 | type Item = SyntaxNodeRef<'f>; | ||
66 | |||
67 | fn next(&mut self) -> Option<SyntaxNodeRef<'f>> { | ||
68 | match *self { | ||
69 | LeafAtOffset::None => None, | ||
70 | LeafAtOffset::Single(node) => { *self = LeafAtOffset::None; Some(node) } | ||
71 | LeafAtOffset::Between(left, right) => { *self = LeafAtOffset::Single(right); Some(left) } | ||
72 | } | ||
73 | } | ||
74 | } | ||
75 | |||
76 | |||
77 | pub fn find_covering_node(root: SyntaxNodeRef, range: TextRange) -> SyntaxNodeRef { | ||
78 | assert!(is_subrange(root.range(), range)); | ||
79 | let (left, right) = match ( | ||
80 | find_leaf_at_offset(root, range.start()).right_biased(), | ||
81 | find_leaf_at_offset(root, range.end()).left_biased() | ||
82 | ) { | ||
83 | (Some(l), Some(r)) => (l, r), | ||
84 | _ => return root | ||
85 | }; | ||
86 | |||
87 | common_ancestor(left, right) | ||
88 | } | ||
89 | |||
90 | fn common_ancestor<'a>(n1: SyntaxNodeRef<'a>, n2: SyntaxNodeRef<'a>) -> SyntaxNodeRef<'a> { | ||
91 | for p in ancestors(n1) { | ||
92 | if ancestors(n2).any(|a| a == p) { | ||
93 | return p; | ||
94 | } | ||
95 | } | ||
96 | panic!("Can't find common ancestor of {:?} and {:?}", n1, n2) | ||
97 | } | ||
98 | |||
99 | pub fn ancestors<'a>(node: SyntaxNodeRef<'a>) -> impl Iterator<Item=SyntaxNodeRef<'a>> { | ||
100 | Ancestors(Some(node)) | ||
101 | } | ||
102 | |||
103 | #[derive(Debug)] | ||
104 | struct Ancestors<'a>(Option<SyntaxNodeRef<'a>>); | ||
105 | |||
106 | impl<'a> Iterator for Ancestors<'a> { | ||
107 | type Item = SyntaxNodeRef<'a>; | ||
108 | |||
109 | fn next(&mut self) -> Option<Self::Item> { | ||
110 | self.0.take().map(|n| { | ||
111 | self.0 = n.parent(); | ||
112 | n | ||
113 | }) | ||
114 | } | ||
115 | } | ||
116 | |||
117 | fn contains_offset_nonstrict(range: TextRange, offset: TextUnit) -> bool { | ||
118 | range.start() <= offset && offset <= range.end() | ||
119 | } | ||
120 | |||
121 | fn is_subrange(range: TextRange, subrange: TextRange) -> bool { | ||
122 | range.start() <= subrange.start() && subrange.end() <= range.end() | ||
123 | } | ||