diff options
author | Aleksey Kladov <[email protected]> | 2018-08-07 16:28:30 +0100 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2018-08-07 16:36:33 +0100 |
commit | 2fb854ccdae6f1f12b60441e5c3b283bdc81fb0a (patch) | |
tree | ed4f31d31473a2faf8e014907960f855b96cca22 /src/algo | |
parent | a04473e2bb95483e84404c57426ee9ed21fa5d6b (diff) |
:tada: extend selection
Diffstat (limited to 'src/algo')
-rw-r--r-- | src/algo/mod.rs | 122 | ||||
-rw-r--r-- | src/algo/search.rs | 136 |
2 files changed, 258 insertions, 0 deletions
diff --git a/src/algo/mod.rs b/src/algo/mod.rs index c1644d16d..d2de70fd4 100644 --- a/src/algo/mod.rs +++ b/src/algo/mod.rs | |||
@@ -1 +1,123 @@ | |||
1 | pub mod walk; | 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 | } | ||
diff --git a/src/algo/search.rs b/src/algo/search.rs new file mode 100644 index 000000000..46404f537 --- /dev/null +++ b/src/algo/search.rs | |||
@@ -0,0 +1,136 @@ | |||
1 | use {Node, NodeType, TextUnit, TextRange}; | ||
2 | use ::visitor::{visitor, process_subtree_bottom_up}; | ||
3 | |||
4 | pub fn child_of_type(node: Node, ty: NodeType) -> Option<Node> { | ||
5 | node.children().find(|n| n.ty() == ty) | ||
6 | } | ||
7 | |||
8 | pub fn children_of_type<'f>(node: Node<'f>, ty: NodeType) -> Box<Iterator<Item=Node<'f>> + 'f> { | ||
9 | Box::new(node.children().filter(move |n| n.ty() == ty)) | ||
10 | } | ||
11 | |||
12 | pub fn subtree<'f>(node: Node<'f>) -> Box<Iterator<Item=Node<'f>> + 'f> { | ||
13 | Box::new(node.children().flat_map(subtree).chain(::std::iter::once(node))) | ||
14 | } | ||
15 | |||
16 | pub fn descendants_of_type<'f>(node: Node<'f>, ty: NodeType) -> Vec<Node<'f>> { | ||
17 | process_subtree_bottom_up( | ||
18 | node, | ||
19 | visitor(Vec::new()) | ||
20 | .visit_nodes(&[ty], |node, nodes| nodes.push(node)) | ||
21 | ) | ||
22 | } | ||
23 | |||
24 | pub fn child_of_type_exn(node: Node, ty: NodeType) -> Node { | ||
25 | child_of_type(node, ty).unwrap_or_else(|| { | ||
26 | panic!("No child of type {:?} for {:?}\ | ||
27 | ----\ | ||
28 | {}\ | ||
29 | ----", ty, node.ty(), node.text()) | ||
30 | }) | ||
31 | } | ||
32 | |||
33 | |||
34 | pub fn ancestors(node: Node) -> Ancestors { | ||
35 | Ancestors(Some(node)) | ||
36 | } | ||
37 | |||
38 | pub struct Ancestors<'f>(Option<Node<'f>>); | ||
39 | |||
40 | impl<'f> Iterator for Ancestors<'f> { | ||
41 | type Item = Node<'f>; | ||
42 | |||
43 | fn next(&mut self) -> Option<Self::Item> { | ||
44 | let current = self.0; | ||
45 | self.0 = current.and_then(|n| n.parent()); | ||
46 | current | ||
47 | } | ||
48 | } | ||
49 | |||
50 | pub fn is_leaf(node: Node) -> bool { | ||
51 | node.children().next().is_none() && !node.range().is_empty() | ||
52 | } | ||
53 | |||
54 | |||
55 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] | ||
56 | pub enum Direction { | ||
57 | Left, Right | ||
58 | } | ||
59 | |||
60 | pub fn sibling(node: Node, dir: Direction) -> Option<Node> { | ||
61 | let (parent, idx) = child_position(node)?; | ||
62 | let idx = match dir { | ||
63 | Direction::Left => idx.checked_sub(1)?, | ||
64 | Direction::Right => idx + 1, | ||
65 | }; | ||
66 | parent.children().nth(idx) | ||
67 | } | ||
68 | |||
69 | pub mod ast { | ||
70 | use {Node, AstNode, TextUnit, AstChildren}; | ||
71 | use visitor::{visitor, process_subtree_bottom_up}; | ||
72 | use super::{ancestors, find_leaf_at_offset, LeafAtOffset}; | ||
73 | |||
74 | pub fn ancestor<'f, T: AstNode<'f>>(node: Node<'f>) -> Option<T> { | ||
75 | ancestors(node) | ||
76 | .filter_map(T::wrap) | ||
77 | .next() | ||
78 | } | ||
79 | |||
80 | pub fn ancestor_exn<'f, T: AstNode<'f>>(node: Node<'f>) -> T { | ||
81 | ancestor(node).unwrap() | ||
82 | } | ||
83 | |||
84 | pub fn children_of_type<'f, N: AstNode<'f>>(node: Node<'f>) -> AstChildren<N> { | ||
85 | AstChildren::new(node.children()) | ||
86 | } | ||
87 | |||
88 | pub fn descendants_of_type<'f, N: AstNode<'f>>(node: Node<'f>) -> Vec<N> { | ||
89 | process_subtree_bottom_up( | ||
90 | node, | ||
91 | visitor(Vec::new()) | ||
92 | .visit::<N, _>(|node, acc| acc.push(node)) | ||
93 | ) | ||
94 | } | ||
95 | |||
96 | pub fn node_at_offset<'f, T: AstNode<'f>>(node: Node<'f>, offset: TextUnit) -> Option<T> { | ||
97 | match find_leaf_at_offset(node, offset) { | ||
98 | LeafAtOffset::None => None, | ||
99 | LeafAtOffset::Single(node) => ancestor(node), | ||
100 | LeafAtOffset::Between(left, right) => ancestor(left).or_else(|| ancestor(right)), | ||
101 | } | ||
102 | } | ||
103 | } | ||
104 | |||
105 | pub mod traversal { | ||
106 | use {Node}; | ||
107 | |||
108 | pub fn bottom_up<'f, F: FnMut(Node<'f>)>(node: Node<'f>, mut f: F) | ||
109 | { | ||
110 | go(node, &mut f); | ||
111 | |||
112 | fn go<'f, F: FnMut(Node<'f>)>(node: Node<'f>, f: &mut F) { | ||
113 | for child in node.children() { | ||
114 | go(child, f) | ||
115 | } | ||
116 | f(node); | ||
117 | } | ||
118 | } | ||
119 | } | ||
120 | |||
121 | fn child_position(child: Node) -> Option<(Node, usize)> { | ||
122 | child.parent() | ||
123 | .map(|parent| { | ||
124 | (parent, parent.children().position(|n| n == child).unwrap()) | ||
125 | }) | ||
126 | } | ||
127 | |||
128 | fn common_ancestor<'f>(n1: Node<'f>, n2: Node<'f>) -> Node<'f> { | ||
129 | for p in ancestors(n1) { | ||
130 | if ancestors(n2).any(|a| a == p) { | ||
131 | return p; | ||
132 | } | ||
133 | } | ||
134 | panic!("Can't find common ancestor of {:?} and {:?}", n1, n2) | ||
135 | } | ||
136 | |||