aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2018-07-30 21:45:10 +0100
committerAleksey Kladov <[email protected]>2018-07-30 21:45:10 +0100
commitaea86d154ec5adde6adb05088a50f01380ffb8bf (patch)
treefd10ec3e5379e24e40f3eff78cb1e035f4bb5c89 /src
parent70b337292117a9bb90e85056dcb4069f8bbc6c0a (diff)
stackless traversal
Diffstat (limited to 'src')
-rw-r--r--src/algo/mod.rs1
-rw-r--r--src/algo/walk.rs46
-rw-r--r--src/ast.rs13
-rw-r--r--src/lib.rs2
-rw-r--r--src/utils.rs2
-rw-r--r--src/yellow/red.rs3
-rw-r--r--src/yellow/syntax.rs28
7 files changed, 81 insertions, 14 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 @@
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)]
11enum WalkEvent<'a> {
12 Enter(SyntaxNodeRef<'a>),
13 Exit(SyntaxNodeRef<'a>),
14}
15
16fn 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
diff --git a/src/ast.rs b/src/ast.rs
index 3a9287466..b513eb13e 100644
--- a/src/ast.rs
+++ b/src/ast.rs
@@ -1,5 +1,5 @@
1use std::sync::Arc; 1use std::sync::Arc;
2use {SyntaxNode, TreeRoot, SyntaxRoot, SyntaxNodeRef}; 2use {SyntaxNode, TreeRoot, SyntaxRoot};
3 3
4#[derive(Debug)] 4#[derive(Debug)]
5pub struct File<R: TreeRoot = Arc<SyntaxRoot>> { 5pub struct File<R: TreeRoot = Arc<SyntaxRoot>> {
@@ -16,15 +16,4 @@ impl<R: TreeRoot> File<R> {
16 pub fn syntax(&self) -> SyntaxNode<R> { 16 pub fn syntax(&self) -> SyntaxNode<R> {
17 self.syntax.clone() 17 self.syntax.clone()
18 } 18 }
19
20 pub fn for_each_node(&self, mut f: impl FnMut(SyntaxNodeRef)) {
21 let syntax = self.syntax();
22 let syntax = syntax.borrow();
23 go(syntax, &mut f);
24
25 fn go(syntax: SyntaxNodeRef, f: &mut FnMut(SyntaxNodeRef)) {
26 f(syntax);
27 syntax.children().into_iter().for_each(f)
28 }
29 }
30} 19}
diff --git a/src/lib.rs b/src/lib.rs
index 3a8e6fa64..9049beb29 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -22,6 +22,7 @@
22 22
23extern crate text_unit; 23extern crate text_unit;
24extern crate unicode_xid; 24extern crate unicode_xid;
25extern crate itertools;
25 26
26mod lexer; 27mod lexer;
27mod parser; 28mod parser;
@@ -30,6 +31,7 @@ mod yellow;
30/// Utilities for simple uses of the parser. 31/// Utilities for simple uses of the parser.
31pub mod utils; 32pub mod utils;
32pub mod ast; 33pub mod ast;
34pub mod algo;
33 35
34pub use { 36pub use {
35 lexer::{tokenize, Token}, 37 lexer::{tokenize, Token},
diff --git a/src/utils.rs b/src/utils.rs
index 20991659a..826a7d60b 100644
--- a/src/utils.rs
+++ b/src/utils.rs
@@ -3,7 +3,7 @@ use {SyntaxError, SyntaxNode, SyntaxNodeRef};
3 3
4/// Parse a file and create a string representation of the resulting parse tree. 4/// Parse a file and create a string representation of the resulting parse tree.
5pub fn dump_tree(syntax: &SyntaxNode) -> String { 5pub fn dump_tree(syntax: &SyntaxNode) -> String {
6 let syntax = syntax.borrow(); 6 let syntax = syntax.as_ref();
7 let mut errors: BTreeSet<_> = syntax.root.errors.iter().cloned().collect(); 7 let mut errors: BTreeSet<_> = syntax.root.errors.iter().cloned().collect();
8 let mut result = String::new(); 8 let mut result = String::new();
9 go(syntax, &mut result, 0, &mut errors); 9 go(syntax, &mut result, 0, &mut errors);
diff --git a/src/yellow/red.rs b/src/yellow/red.rs
index bffb72510..8329ec5b2 100644
--- a/src/yellow/red.rs
+++ b/src/yellow/red.rs
@@ -84,4 +84,7 @@ impl RedNode {
84 pub(crate) fn parent(&self) -> Option<ptr::NonNull<RedNode>> { 84 pub(crate) fn parent(&self) -> Option<ptr::NonNull<RedNode>> {
85 Some(self.parent.as_ref()?.parent) 85 Some(self.parent.as_ref()?.parent)
86 } 86 }
87 pub(crate) fn index_in_parent(&self) -> Option<usize> {
88 Some(self.parent.as_ref()?.index_in_parent)
89 }
87} 90}
diff --git a/src/yellow/syntax.rs b/src/yellow/syntax.rs
index 5c31a3f35..65ce647c7 100644
--- a/src/yellow/syntax.rs
+++ b/src/yellow/syntax.rs
@@ -18,6 +18,15 @@ pub struct SyntaxNode<R: TreeRoot = Arc<SyntaxRoot>> {
18 red: ptr::NonNull<RedNode>, 18 red: ptr::NonNull<RedNode>,
19} 19}
20 20
21impl <R1: TreeRoot, R2: TreeRoot> PartialEq<SyntaxNode<R1>> for SyntaxNode<R2> {
22 fn eq(&self, other: &SyntaxNode<R1>) -> bool {
23 self.red == other.red
24 }
25}
26
27impl <R: TreeRoot> Eq for SyntaxNode<R> {
28}
29
21pub type SyntaxNodeRef<'a> = SyntaxNode<&'a SyntaxRoot>; 30pub type SyntaxNodeRef<'a> = SyntaxNode<&'a SyntaxRoot>;
22 31
23#[derive(Debug)] 32#[derive(Debug)]
@@ -53,7 +62,7 @@ impl SyntaxNode<Arc<SyntaxRoot>> {
53} 62}
54 63
55impl<R: TreeRoot> SyntaxNode<R> { 64impl<R: TreeRoot> SyntaxNode<R> {
56 pub fn borrow<'a>(&'a self) -> SyntaxNode<&'a SyntaxRoot> { 65 pub fn as_ref<'a>(&'a self) -> SyntaxNode<&'a SyntaxRoot> {
57 SyntaxNode { 66 SyntaxNode {
58 root: &*self.root, 67 root: &*self.root,
59 red: ptr::NonNull::clone(&self.red), 68 red: ptr::NonNull::clone(&self.red),
@@ -92,6 +101,23 @@ impl<R: TreeRoot> SyntaxNode<R> {
92 }) 101 })
93 } 102 }
94 103
104 pub fn first_child(&self) -> Option<SyntaxNode<R>> {
105 self.children().next()
106 }
107
108 pub fn next_sibling(&self) -> Option<SyntaxNode<R>> {
109 let red = self.red();
110 let parent = self.parent()?;
111 let next_sibling_idx = red.index_in_parent()? + 1;
112 if next_sibling_idx == red.n_children() {
113 return None;
114 }
115 Some(SyntaxNode {
116 root: self.root.clone(),
117 red: parent.red().nth_child(next_sibling_idx),
118 })
119 }
120
95 fn red(&self) -> &RedNode { 121 fn red(&self) -> &RedNode {
96 unsafe { self.red.as_ref() } 122 unsafe { self.red.as_ref() }
97 } 123 }