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

antlr_rust_sleagon/
tree.rs
