antlr4rust/
tree.rs

1//! General AST
2use std::any::Any;
3use std::borrow::Borrow;
4
5use std::fmt::{Debug, Formatter};
6use std::iter::from_fn;
7use std::marker::PhantomData;
8use std::ops::Deref;
9use std::rc::Rc;
10
11use crate::char_stream::InputData;
12use crate::int_stream::EOF;
13use crate::interval_set::Interval;
14use crate::parser::ParserNodeType;
15use crate::parser_rule_context::ParserRuleContext;
16use crate::recognizer::Recognizer;
17use crate::rule_context::{CustomRuleContext, RuleContext};
18use crate::token::Token;
19use crate::token_factory::TokenFactory;
20use crate::{interval_set, trees, CoerceTo};
21use std::mem;
22
23//todo try to make in more generic
24#[allow(missing_docs)]
25pub trait Tree<'input>: RuleContext<'input> {
26    fn get_parent(&self) -> Option<Rc<<Self::Ctx as ParserNodeType<'input>>::Type>> {
27        None
28    }
29    fn has_parent(&self) -> bool {
30        false
31    }
32    fn get_payload(&self) -> Box<dyn Any> {
33        unimplemented!()
34    }
35    fn get_child(&self, _i: usize) -> Option<Rc<<Self::Ctx as ParserNodeType<'input>>::Type>> {
36        None
37    }
38    fn get_child_count(&self) -> usize {
39        0
40    }
41    fn get_children<'a>(
42        &'a self,
43    ) -> Box<dyn Iterator<Item = Rc<<Self::Ctx as ParserNodeType<'input>>::Type>> + 'a>
44    where
45        'input: 'a,
46    {
47        let mut index = 0;
48        let iter = from_fn(move || {
49            if index < self.get_child_count() {
50                index += 1;
51                self.get_child(index - 1)
52            } else {
53                None
54            }
55        });
56
57        Box::new(iter)
58    }
59    // fn get_children_full(&self) -> &RefCell<Vec<Rc<<Self::Ctx as ParserNodeType<'input, Self::TF>>::Type>>> { unimplemented!() }
60}
61
62/// Tree that knows about underlying text
63pub trait ParseTree<'input>: Tree<'input> {
64    /// Return an {@link Interval} indicating the index in the
65    /// {@link TokenStream} of the first and last token associated with this
66    /// subtree. If this node is a leaf, then the interval represents a single
67    /// token and has interval i..i for token index i.
68    fn get_source_interval(&self) -> Interval {
69        interval_set::INVALID
70    }
71
72    /// Return combined text of this AST node.
73    /// To create resulting string it does traverse whole subtree,
74    /// also it includes only tokens added to the parse tree
75    ///
76    /// Since tokens on hidden channels (e.g. whitespace or comments) are not
77    ///	added to the parse trees, they will not appear in the output of this
78    ///	method.
79    fn get_text(&self) -> String {
80        String::new()
81    }
82
83    /// Print out a whole tree, not just a node, in LISP format
84    /// (root child1 .. childN). Print just a node if this is a leaf.
85    /// We have to know the recognizer so we can get rule names.
86    fn to_string_tree(
87        &self,
88        r: &dyn Recognizer<'input, TF = Self::TF, Node = Self::Ctx>,
89    ) -> String {
90        trees::string_tree(self, r.get_rule_names())
91    }
92}
93
94/// text of the node.
95/// Already implemented for all rule contexts
96// pub trait NodeText {
97//     fn get_node_text(&self, rule_names: &[&str]) -> String;
98// }
99//
100// impl<T> NodeText for T {
101//     default fn get_node_text(&self, _rule_names: &[&str]) -> String { "<unknown>".to_owned() }
102// }
103//
104// impl<'input, T: CustomRuleContext<'input>> NodeText for T {
105//     default fn get_node_text(&self, rule_names: &[&str]) -> String {
106//         let rule_index = self.get_rule_index();
107//         let rule_name = rule_names[rule_index];
108//         let alt_number = self.get_alt_number();
109//         if alt_number != INVALID_ALT {
110//             return format!("{}:{}", rule_name, alt_number);
111//         }
112//         return rule_name.to_owned();
113//     }
114// }
115
116#[doc(hidden)]
117#[derive(Debug)]
118pub struct NoError;
119
120#[doc(hidden)]
121#[derive(Debug)]
122pub struct IsError;
123
124/// Generic leaf AST node
125pub struct LeafNode<'input, Node: ParserNodeType<'input>, T: 'static> {
126    /// Token, this leaf consist of
127    pub symbol: <Node::TF as TokenFactory<'input>>::Tok,
128    iserror: PhantomData<T>,
129}
130better_any::tid! { impl <'input, Node, T:'static> TidAble<'input> for LeafNode<'input, Node, T> where Node:ParserNodeType<'input> }
131
132impl<'input, Node: ParserNodeType<'input>, T: 'static> CustomRuleContext<'input>
133    for LeafNode<'input, Node, T>
134{
135    type TF = Node::TF;
136    type Ctx = Node;
137
138    fn get_rule_index(&self) -> usize {
139        usize::max_value()
140    }
141
142    fn get_node_text(&self, rule_names: &[&str]) -> String {
143        self.symbol.borrow().get_text().to_display()
144    }
145}
146
147impl<'input, Node: ParserNodeType<'input>, T: 'static> ParserRuleContext<'input>
148    for LeafNode<'input, Node, T>
149{
150}
151
152impl<'input, Node: ParserNodeType<'input>, T: 'static> Tree<'input> for LeafNode<'input, Node, T> {}
153
154impl<'input, Node: ParserNodeType<'input>, T: 'static> RuleContext<'input>
155    for LeafNode<'input, Node, T>
156{
157}
158
159// impl<'input, Node: ParserNodeType<'input>, T: 'static> NodeText for LeafNode<'input, Node, T> {
160//     fn get_node_text(&self, _rule_names: &[&str]) -> String {
161//         self.symbol.borrow().get_text().to_display()
162//     }
163// }
164
165impl<'input, Node: ParserNodeType<'input>, T: 'static> ParseTree<'input>
166    for LeafNode<'input, Node, T>
167{
168    fn get_source_interval(&self) -> Interval {
169        let i = self.symbol.borrow().get_token_index();
170        Interval { a: i, b: i }
171    }
172
173    fn get_text(&self) -> String {
174        self.symbol.borrow().get_text().to_display()
175    }
176}
177
178impl<'input, Node: ParserNodeType<'input>, T: 'static> Debug for LeafNode<'input, Node, T> {
179    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
180        if self.symbol.borrow().get_token_type() == EOF {
181            f.write_str("<EOF>")
182        } else {
183            let a = self.symbol.borrow().get_text().to_display();
184            f.write_str(&a)
185        }
186    }
187}
188
189impl<'input, Node: ParserNodeType<'input>, T: 'static> LeafNode<'input, Node, T> {
190    /// creates new leaf node
191    pub fn new(symbol: <Node::TF as TokenFactory<'input>>::Tok) -> Self {
192        Self {
193            symbol,
194            iserror: Default::default(),
195        }
196    }
197}
198
199/// non-error AST leaf node
200pub type TerminalNode<'input, NodeType> = LeafNode<'input, NodeType, NoError>;
201
202impl<'input, Node: ParserNodeType<'input>, Listener: ParseTreeListener<'input, Node> + ?Sized>
203    Listenable<Listener> for TerminalNode<'input, Node>
204{
205    fn enter(&self, listener: &mut Listener) {
206        listener.visit_terminal(self)
207    }
208
209    fn exit(&self, _listener: &mut Listener) {
210        // do nothing
211    }
212}
213
214impl<'input, Node: ParserNodeType<'input>, Visitor: ParseTreeVisitor<'input, Node> + ?Sized>
215    Visitable<Visitor> for TerminalNode<'input, Node>
216{
217    fn accept(&self, visitor: &mut Visitor) {
218        visitor.visit_terminal(self)
219    }
220}
221
222/// # Error Leaf
223/// Created for each token created or consumed during recovery
224pub type ErrorNode<'input, NodeType> = LeafNode<'input, NodeType, IsError>;
225
226impl<'input, Node: ParserNodeType<'input>, Listener: ParseTreeListener<'input, Node> + ?Sized>
227    Listenable<Listener> for ErrorNode<'input, Node>
228{
229    fn enter(&self, listener: &mut Listener) {
230        listener.visit_error_node(self)
231    }
232
233    fn exit(&self, _listener: &mut Listener) {
234        // do nothing
235    }
236}
237
238impl<'input, Node: ParserNodeType<'input>, Visitor: ParseTreeVisitor<'input, Node> + ?Sized>
239    Visitable<Visitor> for ErrorNode<'input, Node>
240{
241    fn accept(&self, visitor: &mut Visitor) {
242        visitor.visit_error_node(self)
243    }
244}
245
246pub trait ParseTreeVisitorCompat<'input>: VisitChildren<'input, Self::Node> {
247    type Node: ParserNodeType<'input>;
248    type Return: Default;
249
250    /// Temporary storage for `ParseTreeVisitor` blanket implementation to work
251    ///
252    /// If you have `()` as a return value
253    /// either use `YourGrammarParseTreeVisitor` directly
254    /// or make
255    /// ```rust
256    /// Box::leak(Box::new(()))
257    /// # ;
258    /// ```
259    /// as an implementation of that method so that there is no need to create dummy field in your visitor
260    fn temp_result(&mut self) -> &mut Self::Return;
261
262    fn visit(&mut self, node: &<Self::Node as ParserNodeType<'input>>::Type) -> Self::Return {
263        self.visit_node(node);
264        mem::take(self.temp_result())
265    }
266
267    /// Called on terminal(leaf) node
268    fn visit_terminal(&mut self, _node: &TerminalNode<'input, Self::Node>) -> Self::Return {
269        Self::Return::default()
270    }
271    /// Called on error node
272    fn visit_error_node(&mut self, _node: &ErrorNode<'input, Self::Node>) -> Self::Return {
273        Self::Return::default()
274    }
275
276    fn visit_children(
277        &mut self,
278        node: &<Self::Node as ParserNodeType<'input>>::Type,
279    ) -> Self::Return {
280        let mut result = Self::Return::default();
281        for node in node.get_children() {
282            if !self.should_visit_next_child(&node, &result) {
283                break;
284            }
285
286            let child_result = self.visit(&node);
287            result = self.aggregate_results(result, child_result);
288        }
289        result
290    }
291
292    fn aggregate_results(&self, aggregate: Self::Return, next: Self::Return) -> Self::Return {
293        next
294    }
295
296    fn should_visit_next_child(
297        &self,
298        node: &<Self::Node as ParserNodeType<'input>>::Type,
299        current: &Self::Return,
300    ) -> bool {
301        true
302    }
303}
304
305// struct VisitorAdapter<'input, T: ParseTreeVisitorCompat<'input>> {
306//     visitor: T,
307//     pub curr_value: T::Return,
308//     _pd: PhantomData<&'input str>,
309// }
310
311impl<'input, Node, T> ParseTreeVisitor<'input, Node> for T
312where
313    Node: ParserNodeType<'input>,
314    Node::Type: VisitableDyn<Self>,
315    T: ParseTreeVisitorCompat<'input, Node = Node>,
316{
317    fn visit_terminal(&mut self, node: &TerminalNode<'input, Node>) {
318        let result = <Self as ParseTreeVisitorCompat>::visit_terminal(self, node);
319        *<Self as ParseTreeVisitorCompat>::temp_result(self) = result;
320    }
321
322    fn visit_error_node(&mut self, node: &ErrorNode<'input, Node>) {
323        let result = <Self as ParseTreeVisitorCompat>::visit_error_node(self, node);
324        *<Self as ParseTreeVisitorCompat>::temp_result(self) = result;
325    }
326
327    fn visit_children(&mut self, node: &Node::Type) {
328        let result = <Self as ParseTreeVisitorCompat>::visit_children(self, node);
329        *<Self as ParseTreeVisitorCompat>::temp_result(self) = result;
330    }
331}
332
333/// Base interface for visiting over syntax tree
334pub trait ParseTreeVisitor<'input, Node: ParserNodeType<'input>>:
335    VisitChildren<'input, Node>
336{
337    /// Basically alias for `node.accept(self)` in visitor implementation
338    /// just to make api closer to java
339
340    /// Called on terminal(leaf) node
341    fn visit_terminal(&mut self, _node: &TerminalNode<'input, Node>) {}
342    /// Called on error node
343    fn visit_error_node(&mut self, _node: &ErrorNode<'input, Node>) {}
344    /// Implement this only if you want to change children visiting algorithm
345    fn visit_children(&mut self, node: &Node::Type) {
346        node.get_children()
347            .for_each(|child| self.visit_node(&child))
348    }
349}
350
351/// Workaround for default recursive children visiting
352///
353/// Already blanket implemented for all visitors.
354/// To override it you would need to implement `ParseTreeVisitor::visit_children`
355pub trait VisitChildren<'input, Node: ParserNodeType<'input>> {
356    // fn visit_children_inner(&mut self, node: &Node::Type);
357    fn visit_node(&mut self, node: &Node::Type);
358}
359
360impl<'input, Node, T> VisitChildren<'input, Node> for T
361where
362    Node: ParserNodeType<'input>,
363    T: ParseTreeVisitor<'input, Node> + ?Sized,
364    // for<'a> &'a mut Self: CoerceUnsized<&'a mut Node::Visitor>,
365    Node::Type: VisitableDyn<T>,
366{
367    // #[inline(always)]
368    // fn visit_children_inner(&mut self, node: &Node::Type) {
369    //     // node.accept_children(self)
370    //
371    // }
372
373    fn visit_node(&mut self, node: &Node::Type) {
374        node.accept_dyn(self)
375    }
376}
377
378/// Types that can accept particular visitor
379/// ** Usually implemented only in generated parser **
380pub trait Visitable<Vis: ?Sized> {
381    /// Calls corresponding visit callback on visitor`Vis`
382    fn accept(&self, _visitor: &mut Vis) {
383        unreachable!("should have been properly implemented by generated context when reachable")
384    }
385}
386
387// workaround trait for accepting sized visitor on rule context trait object
388#[doc(hidden)]
389pub trait VisitableDyn<Vis: ?Sized> {
390    fn accept_dyn(&self, _visitor: &mut Vis) {
391        unreachable!("should have been properly implemented by generated context when reachable")
392    }
393}
394
395/// Base parse listener interface
396pub trait ParseTreeListener<'input, Node: ParserNodeType<'input>> {
397    /// Called when parser creates terminal node
398    fn visit_terminal(&mut self, _node: &TerminalNode<'input, Node>) {}
399    /// Called when parser creates error node
400    fn visit_error_node(&mut self, _node: &ErrorNode<'input, Node>) {}
401    /// Called when parser enters any rule node
402    fn enter_every_rule(&mut self, _ctx: &Node::Type) {}
403    /// Called when parser exits any rule node
404    fn exit_every_rule(&mut self, _ctx: &Node::Type) {}
405}
406
407/// Types that can accept particular listener
408/// ** Usually implemented only in generated parser **
409pub trait Listenable<T: ?Sized> {
410    /// Calls corresponding enter callback on listener `T`
411    fn enter(&self, _listener: &mut T) {}
412    /// Calls corresponding exit callback on listener `T`
413    fn exit(&self, _listener: &mut T) {}
414}
415
416// #[inline]
417// pub fn temp_to_trait<Z,TraitObject>(mut input: Z, f:impl FnOnce(&mut TraitObject)) -> Z where &mut Z:CoerceUnsized<&mut TraitObject>{
418//     let a = &mut input as &mut TraitObject;
419//     f(a)
420// }
421
422/// Helper struct to accept parse listener on already generated tree
423#[derive(Debug)]
424pub struct ParseTreeWalker<'input, 'a, Node, T = dyn ParseTreeListener<'input, Node> + 'a>(
425    PhantomData<fn(&'a T) -> &'input Node::Type>,
426)
427where
428    Node: ParserNodeType<'input>,
429    T: ParseTreeListener<'input, Node> + ?Sized;
430
431impl<'input, 'a, Node, T> ParseTreeWalker<'input, 'a, Node, T>
432where
433    Node: ParserNodeType<'input>,
434    T: ParseTreeListener<'input, Node> + 'a + ?Sized,
435    Node::Type: Listenable<T>,
436{
437    /// Walks recursively over tree `t` with `listener`
438    pub fn walk<Listener, Ctx>(mut listener: Box<Listener>, t: &Ctx) -> Box<Listener>
439    where
440        // for<'x> &'x mut Listener: CoerceUnsized<&'x mut T>,
441        // for<'x> &'x Ctx: CoerceUnsized<&'x Node::Type>,
442        Listener: CoerceTo<T>,
443        Ctx: CoerceTo<Node::Type>,
444    {
445        // let mut listener = listener as Box<T>;
446        Self::walk_inner(listener.as_mut().coerce_mut_to(), t.coerce_ref_to());
447
448        // just cast back
449        // unsafe { Box::<Listener>::from_raw(Box::into_raw(listener) as *mut _) }
450        listener
451    }
452
453    fn walk_inner(listener: &mut T, t: &Node::Type) {
454        t.enter(listener);
455
456        for child in t.get_children() {
457            Self::walk_inner(listener, child.deref())
458        }
459
460        t.exit(listener);
461    }
462}
antlr4rust/tree.rs

antlr4rust/
tree.rs
