diff options
author | Aleksey Kladov <[email protected]> | 2018-07-30 21:45:10 +0100 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2018-07-30 21:45:10 +0100 |
commit | aea86d154ec5adde6adb05088a50f01380ffb8bf (patch) | |
tree | fd10ec3e5379e24e40f3eff78cb1e035f4bb5c89 /src/algo | |
parent | 70b337292117a9bb90e85056dcb4069f8bbc6c0a (diff) |
stackless traversal
Diffstat (limited to 'src/algo')
-rw-r--r-- | src/algo/mod.rs | 1 | ||||
-rw-r--r-- | src/algo/walk.rs | 46 |
2 files changed, 47 insertions, 0 deletions
diff --git a/src/algo/mod.rs b/src/algo/mod.rs new file mode 100644 index 000000000..c1644d16d --- /dev/null +++ b/src/algo/mod.rs | |||
@@ -0,0 +1 @@ | |||
pub mod walk; | |||
diff --git a/src/algo/walk.rs b/src/algo/walk.rs new file mode 100644 index 000000000..86dd82cc9 --- /dev/null +++ b/src/algo/walk.rs | |||
@@ -0,0 +1,46 @@ | |||
1 | use SyntaxNodeRef; | ||
2 | |||
3 | pub 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)] | ||
11 | enum WalkEvent<'a> { | ||
12 | Enter(SyntaxNodeRef<'a>), | ||
13 | Exit(SyntaxNodeRef<'a>), | ||
14 | } | ||
15 | |||
16 | 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 | } | ||
46 | |||