gearley/forest/
traverse.rs

1use std::iter;
2use std::borrow::Borrow;
3
4use bit_vec::BitVec;
5use cfg::symbol::Symbol;
6
7use grammar::InternalGrammar;
8use super::Bocage;
9use super::node::{NodeHandle, Node, Iter, Tag};
10use super::node::Node::*;
11
12pub use self::HandleVariant::*;
13
14impl<G> Bocage<G> {
15    // Once node liveness is marked, you may traverse the nodes.
16    pub fn traverse(&self) -> Traverse<G> {
17        Traverse {
18            bocage: self,
19            graph_iter: self.graph.iter_from(NodeHandle(0)),
20            liveness: &self.gc.liveness,
21            factor_stack: vec![],
22            factor_traversal: vec![],
23        }
24    }
25}
26
27pub struct Traverse<'f, G> {
28    bocage: &'f Bocage<G>,
29    // main iterators
30    graph_iter: Iter<'f>,
31    liveness: &'f BitVec,
32    // Space for unrolling factors
33    factor_stack: Vec<(Symbol, NodeHandle)>,
34    // Scratch space for traversal
35    factor_traversal: Vec<NodeHandle>,
36}
37
38impl<'f, G> Traverse<'f, G>
39    where G: Borrow<InternalGrammar>,
40{
41    pub fn next_node<'t>(&'t mut self) -> Option<TraversalHandle<'f, 't, G>> {
42        while let Some(node) = self.graph_iter.peek() {
43            let iter = self.graph_iter;
44            let alive = self.liveness[self.graph_iter.handle.usize()];
45            println!("next_node @{:?} {:?} {}", self.graph_iter.handle, node, alive);
46            self.graph_iter.next();
47            if !alive {
48                continue;
49            }
50            match node {
51                Product { action, .. } => {
52                    if self.bocage.is_transparent(action) {
53                        continue;
54                    }
55                    let products = iter.take(1);
56                    return Some(TraversalHandle {
57                        iter,
58                        symbol: self.bocage.grammar.borrow().get_lhs(action),
59                        item: SumHandle(Products {
60                            products,
61                            traverse: self,
62                        }),
63                    });
64                }
65                Sum { nonterminal: symbol, count } => {
66                    let products = self.graph_iter.take(count as usize);
67                    for _ in 0..count {
68                        let p = self.graph_iter.handle;
69                        let n = self.graph_iter.next();
70                        println!("next_node product @{:?} {:?}", p, n);
71                    }
72                    return Some(TraversalHandle {
73                        iter,
74                        symbol,
75                        item: SumHandle(Products {
76                            products,
77                            traverse: self,
78                        }),
79                    });
80                }
81                NullingLeaf { symbol } => {
82                    return Some(TraversalHandle {
83                        iter,
84                        symbol,
85                        item: NullingHandle,
86                    });
87                }
88                Evaluated { symbol, .. } => {
89                    return Some(TraversalHandle {
90                        iter,
91                        symbol,
92                        item: LeafHandle,
93                    });
94                }
95            }
96        }
97        None
98    }
99
100    fn unfold_factors(&mut self, left: NodeHandle, right: Option<NodeHandle>) {
101        self.factor_stack.clear();
102        self.enqueue_for_unfold(left, right);
103        while let Some(node) = self.pop_for_unfold() {
104            match node {
105                (Product { left_factor, right_factor, .. }, _) => {
106                    self.enqueue_for_unfold(left_factor, right_factor);
107                }
108                (Evaluated { symbol }, handle) => {
109                    self.factor_stack.push((symbol, handle));
110                }
111                _ => unreachable!()
112            }
113        }
114    }
115
116    fn enqueue_for_unfold(&mut self, left: NodeHandle, right: Option<NodeHandle>) {
117        if let Some(right) = right {
118            self.factor_traversal.push(right);
119        }
120        self.factor_traversal.push(left);
121    }
122
123    fn pop_for_unfold(&mut self) -> Option<(Node, NodeHandle)> {
124        self.factor_traversal.pop().map(|handle| {
125            (self.bocage.graph.get(handle), handle)
126        })
127    }
128}
129
130pub struct TraversalHandle<'f, 't, G> {
131    pub(crate) iter: Iter<'f>,
132    pub symbol: Symbol,
133    pub item: HandleVariant<'f, 't, G>,
134}
135
136pub enum HandleVariant<'f, 't, G> {
137    SumHandle(Products<'f, 't, G>),
138    NullingHandle,
139    LeafHandle,
140}
141
142pub struct Products<'f, 't, G> {
143    products: iter::Take<Iter<'f>>,
144    traverse: &'t mut Traverse<'f, G>,
145}
146
147pub struct ProductHandle<'t> {
148    pub action: u32,
149    pub factors: &'t [(Symbol, NodeHandle)],
150}
151
152impl<'f, 't, G> Products<'f, 't, G>
153    where G: Borrow<InternalGrammar>,
154{
155    pub fn next_product<'p>(&'p mut self) -> Option<ProductHandle> {
156        while let Some(node) = self.products.next() {
157            match node {
158                Product { left_factor, right_factor, action } => {
159                    let origin = self.traverse.bocage.grammar.borrow().external_origin(action);
160                    if let Some(action) = origin {
161                        self.traverse.unfold_factors(left_factor, right_factor);
162                        return Some(ProductHandle {
163                            action,
164                            factors: &self.traverse.factor_stack[..],
165                        });
166                    }
167                }
168                _ => unreachable!()
169            }
170        }
171        None
172    }
173}
174
175impl<'f, 't, G> TraversalHandle<'f, 't, G> {
176    pub fn end_evaluation(&self) {
177        self.iter.vec[self.iter.handle.usize()].set(Tag::SmallLeafTag.to_u16());
178    }
179
180    pub fn handle(&self) -> NodeHandle {
181        self.iter.handle
182    }
183}
gearley/forest/traverse.rs

gearley/forest/
traverse.rs
