aboutsummaryrefslogtreecommitdiff
path: root/src/algo
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2018-08-10 20:33:29 +0100
committerAleksey Kladov <[email protected]>2018-08-10 20:33:29 +0100
commit7c67612b8a894187fa3b64725531a5459f9211bf (patch)
tree9e2a536efa0c880d921fd8d4d74423afc9451fd4 /src/algo
parent26262aaf05983c5b7f41cc438e287523268fe1eb (diff)
organizize
Diffstat (limited to 'src/algo')
-rw-r--r--src/algo/mod.rs123
-rw-r--r--src/algo/search.rs136
-rw-r--r--src/algo/walk.rs45
3 files changed, 0 insertions, 304 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}
diff --git a/src/algo/search.rs b/src/algo/search.rs
deleted file mode 100644
index 46404f537..000000000
--- a/src/algo/search.rs
+++ /dev/null
@@ -1,136 +0,0 @@
1use {Node, NodeType, TextUnit, TextRange};
2use ::visitor::{visitor, process_subtree_bottom_up};
3
4pub fn child_of_type(node: Node, ty: NodeType) -> Option<Node> {
5 node.children().find(|n| n.ty() == ty)
6}
7
8pub 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
12pub 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
16pub 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
24pub 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
34pub fn ancestors(node: Node) -> Ancestors {
35 Ancestors(Some(node))
36}
37
38pub struct Ancestors<'f>(Option<Node<'f>>);
39
40impl<'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
50pub 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)]
56pub enum Direction {
57 Left, Right
58}
59
60pub 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
69pub 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
105pub 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
121fn 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
128fn 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
diff --git a/src/algo/walk.rs b/src/algo/walk.rs
deleted file mode 100644
index a50ec2a09..000000000
--- a/src/algo/walk.rs
+++ /dev/null
@@ -1,45 +0,0 @@
1use SyntaxNodeRef;
2
3pub fn preorder<'a>(root: SyntaxNodeRef<'a>) -> impl Iterator<Item = SyntaxNodeRef<'a>> {
4 walk(root).filter_map(|event| match event {
5 WalkEvent::Enter(node) => Some(node),
6 WalkEvent::Exit(_) => None,
7 })
8}
9
10#[derive(Debug, Copy, Clone)]
11pub enum WalkEvent<'a> {
12 Enter(SyntaxNodeRef<'a>),
13 Exit(SyntaxNodeRef<'a>),
14}
15
16pub fn walk<'a>(root: SyntaxNodeRef<'a>) -> impl Iterator<Item = WalkEvent<'a>> {
17 let mut done = false;
18 ::itertools::unfold(WalkEvent::Enter(root), move |pos| {
19 if done {
20 return None;
21 }
22 let res = *pos;
23 *pos = match *pos {
24 WalkEvent::Enter(node) => match node.first_child() {
25 Some(child) => WalkEvent::Enter(child),
26 None => WalkEvent::Exit(node),
27 },
28 WalkEvent::Exit(node) => {
29 if node == root {
30 done = true;
31 WalkEvent::Exit(node)
32 } else {
33 match node.next_sibling() {
34 Some(sibling) => WalkEvent::Enter(sibling),
35 None => match node.parent() {
36 Some(node) => WalkEvent::Exit(node),
37 None => WalkEvent::Exit(node),
38 },
39 }
40 }
41 }
42 };
43 Some(res)
44 })
45}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 16:07:29 +0000