aboutsummaryrefslogtreecommitdiff
path: root/src/algo/mod.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/algo/mod.rs')
-rw-r--r--src/algo/mod.rs123
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 @@
1pub mod walk;
2
3use {SyntaxNodeRef, TextUnit, TextRange};
4
5pub 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)]
40pub enum LeafAtOffset<'a> {
41 None,
42 Single(SyntaxNodeRef<'a>),
43 Between(SyntaxNodeRef<'a>, SyntaxNodeRef<'a>)
44}
45
46impl<'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
64impl<'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
77pub 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
90fn 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
99pub fn ancestors<'a>(node: SyntaxNodeRef<'a>) -> impl Iterator<Item=SyntaxNodeRef<'a>> {
100 Ancestors(Some(node))
101}
102
103#[derive(Debug)]
104struct Ancestors<'a>(Option<SyntaxNodeRef<'a>>);
105
106impl<'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
117fn contains_offset_nonstrict(range: TextRange, offset: TextUnit) -> bool {
118 range.start() <= offset && offset <= range.end()
119}
120
121fn is_subrange(range: TextRange, subrange: TextRange) -> bool {
122 range.start() <= subrange.start() && subrange.end() <= range.end()
123}