cfgrammar/yacc/
ast.rs

1use std::{
2    collections::{HashMap, HashSet},
3    error::Error,
4    fmt,
5    str::FromStr,
6};
7
8use indexmap::{IndexMap, IndexSet};
9
10use super::{
11    Precedence, YaccGrammarError, YaccGrammarErrorKind, YaccGrammarWarning, YaccGrammarWarningKind,
12    YaccKind, parser::YaccParser,
13};
14
15use crate::{
16    Span,
17    header::{GrmtoolsSectionParser, HeaderError, HeaderErrorKind, HeaderValue},
18    yacc::YaccOriginalActionKind,
19};
20
21/// Any error from the Yacc parser returns an instance of this struct.
22#[derive(Debug, PartialEq, Eq, Clone)]
23pub struct ASTModificationError {
24    kind: YaccGrammarErrorKind,
25}
26
27impl Error for ASTModificationError {}
28
29impl fmt::Display for ASTModificationError {
30    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
31        write!(f, "{}", self.kind)
32    }
33}
34
35/// Contains a `GrammarAST` structure produced from a grammar source file.
36/// As well as any errors which occurred during the construction of the AST.
37#[derive(Debug, Clone)]
38#[cfg_attr(test, derive(PartialEq))]
39pub struct ASTWithValidityInfo {
40    yacc_kind: YaccKind,
41    ast: GrammarAST,
42    errs: Vec<YaccGrammarError>,
43}
44
45impl ASTWithValidityInfo {
46    /// Parses a source file into an AST, returning an ast and any errors that were
47    /// encountered during the construction of it.  The `ASTWithValidityInfo` can be
48    /// then unused to construct a `YaccGrammar`, which will either produce an
49    /// `Ok(YaccGrammar)` or an `Err` which includes these errors.
50    ///
51    /// This function ignores the `%grmtools` section entirely, assuming that the caller has
52    /// already extracted the `YaccKind` if any.
53    pub fn new(yacc_kind: YaccKind, s: &str) -> Self {
54        let mut errs = Vec::new();
55        let ast = {
56            let mut yp = YaccParser::new(yacc_kind, s);
57            yp.parse().map_err(|e| errs.extend(e)).ok();
58            let mut ast = yp.build();
59            ast.complete_and_validate(Some(yacc_kind))
60                .map_err(|e| errs.push(e))
61                .ok();
62            ast
63        };
64        ASTWithValidityInfo {
65            ast,
66            errs,
67            yacc_kind,
68        }
69    }
70
71    /// Returns a `GrammarAST` constructed as the result of parsing a source file.
72    /// When errors have occurred and `is_valid` returns false, this AST is the
73    /// subset of the source file which parsed correctly while not encountering
74    /// any errors. As such even when an AST is not valid, it will return an AST.
75    pub fn ast(&self) -> &GrammarAST {
76        &self.ast
77    }
78
79    /// Returns whether any errors where encountered during the
80    /// parsing and validation of the AST during it's construction.
81    pub fn is_valid(&self) -> bool {
82        self.errors().is_empty()
83    }
84
85    /// Returns the `YaccKind` that was used to parse the `GrammarAST`.
86    pub fn yacc_kind(&self) -> YaccKind {
87        self.yacc_kind
88    }
89
90    /// Returns all errors which were encountered during AST construction.
91    pub fn errors(&self) -> &[YaccGrammarError] {
92        self.errs.as_slice()
93    }
94
95    pub fn clone_and_change_start_rule(&self, rule: Rule) -> Result<Self, ASTModificationError> {
96        if self.ast.get_rule(&rule.name.0).is_some() {
97            let mut ret = self.clone();
98            // The `Span`of the `start` field and the `name` field typically differ
99            // in that `start` is the parameter of a `%start` declaration, while
100            // `name` refers to the definition site of the rule itself.
101            //
102            // Lacking a better `Span` we use the definition site, for the `%start` rule here.
103            ret.ast.start = Some(rule.name);
104            Ok(ret)
105        } else {
106            Err(ASTModificationError {
107                kind: YaccGrammarErrorKind::InvalidStartRule(rule.name.0),
108            })
109        }
110    }
111}
112
113impl FromStr for ASTWithValidityInfo {
114    type Err = Vec<YaccGrammarError>;
115    /// Parses the `%grmtools section` expecting it to contain a `yacckind` entry.
116    fn from_str(src: &str) -> Result<Self, Vec<YaccGrammarError>> {
117        let mut errs = Vec::new();
118        let (header, _) = GrmtoolsSectionParser::new(src, true)
119            .parse()
120            .map_err(|mut errs| errs.drain(..).map(|e| e.into()).collect::<Vec<_>>())?;
121        if let Some(HeaderValue(_, yk_val)) = header.get("yacckind") {
122            let yacc_kind = YaccKind::try_from(yk_val).map_err(|e| vec![e.into()])?;
123            let ast = {
124                // We don't want to strip off the header so that span's will be correct.
125                let mut yp = YaccParser::new(yacc_kind, src);
126                yp.parse().map_err(|e| errs.extend(e)).ok();
127                let mut ast = yp.build();
128                ast.complete_and_validate(Some(yacc_kind))
129                    .map_err(|e| errs.push(e))
130                    .ok();
131                ast
132            };
133            Ok(ASTWithValidityInfo {
134                ast,
135                errs,
136                yacc_kind,
137            })
138        } else {
139            Err(vec![
140                HeaderError {
141                    kind: HeaderErrorKind::InvalidEntry("yacckind"),
142                    locations: vec![Span::new(0, 0)],
143                }
144                .into(),
145            ])
146        }
147    }
148}
149
150/// An AST representing a grammar. Typically these will only be constructed through [`ASTWithValidityInfo`] struct.
151#[derive(Debug, Clone)]
152#[cfg_attr(test, derive(PartialEq))]
153#[non_exhaustive]
154pub struct GrammarAST {
155    pub start: Option<(String, Span)>,
156    // map from a rule name to indexes into `prods`
157    pub rules: IndexMap<String, Rule>,
158    pub prods: Vec<Production>,
159    // A set of indexes into `tokens` for all tokens in `%token` directives.
160    // e.g. given a `%token a` and a token "b" not specified in any `%token` directive
161    // we have `self.tokens.get_index_of("a") ∈ self.token_directives`. However for
162    // token "b" we have `self.tokens.get_index_of("b") ∉ self.token_directives`.
163    pub token_directives: HashSet<usize>,
164    pub tokens: IndexSet<String>,
165    pub spans: Vec<Span>,
166    pub precs: HashMap<String, (Precedence, Span)>,
167    pub avoid_insert: Option<HashMap<String, Span>>,
168    pub implicit_tokens: Option<HashMap<String, Span>>,
169    // Error pretty-printers,
170    // The first span of the value is the span of the key,
171    // The second span in the value, is the span of the values string.
172    pub epp: HashMap<String, (Span, (String, Span))>,
173    pub expect: Option<(usize, Span)>,
174    pub expectrr: Option<(usize, Span)>,
175    pub parse_param: Option<(String, String)>,
176    pub parse_generics: Option<String>,
177    pub programs: Option<String>,
178    // The set of symbol names that, if unused in a
179    // grammar, will not cause a warning or error.
180    pub expect_unused: Vec<Symbol>,
181}
182
183#[derive(Debug, Clone)]
184#[cfg_attr(test, derive(Eq, PartialEq))]
185pub struct Rule {
186    pub name: (String, Span),
187    pub pidxs: Vec<usize>, // index into GrammarAST.prod
188    pub actiont: Option<String>,
189}
190
191#[derive(Debug, Clone)]
192#[cfg_attr(test, derive(Eq, PartialEq))]
193pub struct Production {
194    pub symbols: Vec<Symbol>,
195    pub precedence: Option<String>,
196    pub action: Option<(String, Span)>,
197    pub prod_span: Span,
198}
199
200#[derive(Clone, Debug)]
201#[cfg_attr(test, derive(Eq, PartialEq))]
202pub enum Symbol {
203    Rule(String, Span),
204    Token(String, Span),
205}
206
207/// Specifies an index into a `GrammarAst.tokens` or a `GrammarAST.rules`.
208/// Unlike `cfgrammar::Symbol` it is not parameterized by a `StorageT`.
209#[derive(Eq, PartialEq, Debug, Copy, Clone)]
210pub(crate) enum SymbolIdx {
211    Rule(usize),
212    Token(usize),
213}
214
215impl SymbolIdx {
216    pub(crate) fn symbol(self, ast: &GrammarAST) -> Symbol {
217        match self {
218            SymbolIdx::Rule(idx) => {
219                let (rule_name, rule_span) = &ast.rules[idx].name;
220                Symbol::Rule(rule_name.clone(), *rule_span)
221            }
222            SymbolIdx::Token(idx) => {
223                let tok = &ast.tokens[idx];
224                Symbol::Token(tok.clone(), ast.spans[idx])
225            }
226        }
227    }
228}
229impl fmt::Display for Symbol {
230    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
231        match *self {
232            Symbol::Rule(ref s, _) => write!(f, "{}", s),
233            Symbol::Token(ref s, _) => write!(f, "{}", s),
234        }
235    }
236}
237
238impl GrammarAST {
239    pub(crate) fn new() -> GrammarAST {
240        GrammarAST {
241            start: None,
242            rules: IndexMap::new(), // Using an IndexMap means that we retain the order
243            // of rules as they're found in the input file.
244            prods: Vec::new(),
245            spans: Vec::new(),
246            tokens: IndexSet::new(),
247            token_directives: HashSet::new(),
248            precs: HashMap::new(),
249            avoid_insert: None,
250            implicit_tokens: None,
251            epp: HashMap::new(),
252            expect: None,
253            expectrr: None,
254            parse_param: None,
255            parse_generics: None,
256            programs: None,
257            expect_unused: Vec::new(),
258        }
259    }
260
261    pub fn add_rule(&mut self, (name, name_span): (String, Span), actiont: Option<String>) {
262        self.rules.insert(
263            name.clone(),
264            Rule {
265                name: (name, name_span),
266                pidxs: Vec::new(),
267                actiont,
268            },
269        );
270    }
271
272    pub fn add_prod(
273        &mut self,
274        rule_name: String,
275        symbols: Vec<Symbol>,
276        precedence: Option<String>,
277        action: Option<(String, Span)>,
278        prod_span: Span,
279    ) {
280        self.rules[&rule_name].pidxs.push(self.prods.len());
281        self.prods.push(Production {
282            symbols,
283            precedence,
284            action,
285            prod_span,
286        });
287    }
288
289    #[deprecated(since = "0.10.2", note = "Please use set_programs instead")]
290    pub fn add_programs(&mut self, s: String) {
291        self.set_programs(s);
292    }
293
294    pub fn set_programs(&mut self, s: String) {
295        self.programs = Some(s)
296    }
297
298    pub fn get_rule(&self, key: &str) -> Option<&Rule> {
299        self.rules.get(key)
300    }
301
302    pub fn has_token(&self, s: &str) -> bool {
303        self.tokens.contains(s)
304    }
305
306    /// After the AST has been populated, perform any final operations, and validate the grammar
307    /// checking that:
308    ///   1) The start rule references a rule in the grammar
309    ///   2) Every rule reference references a rule in the grammar
310    ///   3) Every token reference references a declared token
311    ///   4) If a production has a precedence token, then it references a declared token
312    ///   5) Every token declared with %epp matches a known token
313    ///   6) If `yacc_kind` is specified, perform any kind specific validation.
314    ///      * If the kind requires an action type, check that each rule has one
315    ///      * That each production has action code
316    ///      * That `$` variables referred to in action code are recognised.
317    pub(crate) fn complete_and_validate(
318        &mut self,
319        yacc_kind: Option<YaccKind>,
320    ) -> Result<(), YaccGrammarError> {
321        let kind_requires_action_checks = matches!(
322            yacc_kind,
323            Some(YaccKind::Original(YaccOriginalActionKind::UserAction)) | Some(YaccKind::Grmtools)
324        );
325
326        match self.start {
327            None => {
328                return Err(YaccGrammarError {
329                    kind: YaccGrammarErrorKind::NoStartRule,
330                    spans: vec![Span::new(0, 0)],
331                });
332            }
333            Some((ref s, span)) => {
334                if !self.rules.contains_key(s) {
335                    return Err(YaccGrammarError {
336                        kind: YaccGrammarErrorKind::InvalidStartRule(s.clone()),
337                        spans: vec![span],
338                    });
339                }
340            }
341        }
342        for rule in self.rules.values() {
343            if kind_requires_action_checks && rule.actiont.is_none() {
344                return Err(YaccGrammarError {
345                    kind: YaccGrammarErrorKind::MissingActionType,
346                    spans: vec![rule.name.1],
347                });
348            }
349            for &pidx in &rule.pidxs {
350                let prod = &self.prods[pidx];
351                if kind_requires_action_checks {
352                    if let Some((action_code, action_span)) = prod.action.as_ref() {
353                        let mut last = 0;
354                        while let Some(off) = action_code[last..].find('$') {
355                            if !(action_code[last + off..].starts_with("$$")
356                                || action_code[last + off..].starts_with("$lexer")
357                                || action_code[last + off..].starts_with("$span")
358                                || (last + off + 1 < action_code.len()
359                                    && action_code[last + off + 1..]
360                                        .starts_with(|c: char| c.is_numeric())))
361                            {
362                                // Starting from the `$` find the end of a variable name, otherwise default to the span of the `$`
363                                let m = crate::yacc::parser::RE_NAME
364                                    .find(&action_code[last + off + 1..]);
365                                let var_start_pos = action_span.start() + last + off;
366                                let var_end_pos = m
367                                    .map(|m| var_start_pos + 1 + m.end())
368                                    .unwrap_or(var_start_pos + 1);
369                                return Err(YaccGrammarError {
370                                    kind: YaccGrammarErrorKind::UnrecognisedActionVariable,
371                                    spans: vec![Span::new(var_start_pos, var_end_pos)],
372                                });
373                            } else {
374                                last = last + off + 2;
375                            }
376                        }
377                    } else {
378                        return Err(YaccGrammarError {
379                            kind: YaccGrammarErrorKind::MissingActionCode,
380                            spans: vec![prod.prod_span],
381                        });
382                    }
383                }
384
385                if let Some(ref n) = prod.precedence {
386                    if !self.tokens.contains(n) {
387                        return Err(YaccGrammarError {
388                            kind: YaccGrammarErrorKind::UnknownToken(n.clone()),
389                            spans: vec![Span::new(0, 0)],
390                        });
391                    }
392                    if !self.precs.contains_key(n) {
393                        return Err(YaccGrammarError {
394                            kind: YaccGrammarErrorKind::NoPrecForToken(n.clone()),
395                            spans: vec![Span::new(0, 0)],
396                        });
397                    }
398                }
399                for sym in &prod.symbols {
400                    match *sym {
401                        Symbol::Rule(ref name, span) => {
402                            if !self.rules.contains_key(name) {
403                                return Err(YaccGrammarError {
404                                    kind: YaccGrammarErrorKind::UnknownRuleRef(name.clone()),
405                                    spans: vec![span],
406                                });
407                            }
408                        }
409                        Symbol::Token(ref name, span) => {
410                            if !self.tokens.contains(name) {
411                                return Err(YaccGrammarError {
412                                    kind: YaccGrammarErrorKind::UnknownToken(name.clone()),
413                                    spans: vec![span],
414                                });
415                            }
416                        }
417                    }
418                }
419            }
420        }
421
422        for (k, (sp, _)) in self.epp.iter() {
423            if self.tokens.contains(k) {
424                continue;
425            }
426            if let Some(ref it) = self.implicit_tokens
427                && it.contains_key(k)
428            {
429                continue;
430            }
431            return Err(YaccGrammarError {
432                kind: YaccGrammarErrorKind::UnknownEPP(k.clone()),
433                spans: vec![*sp],
434            });
435        }
436
437        for sym in &self.expect_unused {
438            match sym {
439                Symbol::Rule(sym_name, sym_span) => {
440                    if self.get_rule(sym_name).is_none() {
441                        return Err(YaccGrammarError {
442                            kind: YaccGrammarErrorKind::UnknownRuleRef(sym_name.clone()),
443                            spans: vec![*sym_span],
444                        });
445                    }
446                }
447                Symbol::Token(sym_name, sym_span) => {
448                    if !self.has_token(sym_name) {
449                        return Err(YaccGrammarError {
450                            kind: YaccGrammarErrorKind::UnknownToken(sym_name.clone()),
451                            spans: vec![*sym_span],
452                        });
453                    }
454                }
455            }
456        }
457        Ok(())
458    }
459
460    pub fn warnings(&self) -> Vec<YaccGrammarWarning> {
461        self.unused_symbols()
462            .map(|symidx| {
463                let (kind, span) = match symidx.symbol(self) {
464                    Symbol::Rule(_, span) => (YaccGrammarWarningKind::UnusedRule, span),
465                    Symbol::Token(_, span) => (YaccGrammarWarningKind::UnusedToken, span),
466                };
467                YaccGrammarWarning {
468                    kind,
469                    spans: vec![span],
470                }
471            })
472            .collect()
473    }
474
475    /// Return the indices of unexpectedly unused rules (relative to ast.rules)
476    /// and tokens (relative to ast.tokens) as `SymbolIdx`s.
477    pub(crate) fn unused_symbols(&self) -> impl Iterator<Item = SymbolIdx> + '_ {
478        let start_rule_name = self.start.as_ref().map(|(name, _)| name.clone());
479        let start_rule = self
480            .rules
481            .iter()
482            .find(|(rule_name, _)| start_rule_name.as_ref() == Some(rule_name));
483        let mut seen_rules = HashSet::new();
484        let mut seen_tokens = HashSet::new();
485        let mut expected_unused_tokens = HashSet::new();
486        let mut expected_unused_rules = HashSet::new();
487        for sym in &self.expect_unused {
488            match sym {
489                Symbol::Rule(sym_name, _) => {
490                    expected_unused_rules.insert(sym_name);
491                }
492                Symbol::Token(sym_name, _) => {
493                    expected_unused_tokens.insert(sym_name);
494                }
495            }
496        }
497        if let Some(implicit_tokens) = self.implicit_tokens.as_ref() {
498            expected_unused_tokens.extend(implicit_tokens.keys())
499        }
500        if let Some((start_name, start_rule)) = start_rule {
501            let mut todo = Vec::new();
502            todo.extend(start_rule.pidxs.iter().copied());
503            seen_rules.insert(start_name);
504
505            while let Some(pidx) = todo.pop() {
506                let prod = &self.prods[pidx];
507                for sym in &prod.symbols {
508                    match sym {
509                        Symbol::Rule(name, _) => {
510                            if seen_rules.insert(name)
511                                && let Some(rule) = self.rules.get(name)
512                            {
513                                todo.extend(&rule.pidxs);
514                            }
515                        }
516                        Symbol::Token(name, _) => {
517                            seen_tokens.insert(name);
518                        }
519                    };
520                }
521            }
522        }
523        self.rules
524            .iter()
525            .enumerate()
526            .filter_map(move |(rule_id, (rule_name, _))| {
527                if expected_unused_rules.contains(rule_name) || seen_rules.contains(rule_name) {
528                    None
529                } else {
530                    Some(SymbolIdx::Rule(rule_id))
531                }
532            })
533            .chain(
534                self.tokens
535                    .iter()
536                    .enumerate()
537                    .filter_map(move |(tok_idx, tok)| {
538                        if expected_unused_tokens.contains(tok) || seen_tokens.contains(tok) {
539                            None
540                        } else {
541                            Some(SymbolIdx::Token(tok_idx))
542                        }
543                    }),
544            )
545    }
546}
547
548#[cfg(test)]
549mod test {
550    use super::{
551        super::{AssocKind, Precedence},
552        GrammarAST, Span, Symbol, YaccGrammarError, YaccGrammarErrorKind,
553    };
554
555    fn rule(n: &str) -> Symbol {
556        Symbol::Rule(n.to_string(), Span::new(0, 0))
557    }
558
559    fn token(n: &str) -> Symbol {
560        Symbol::Token(n.to_string(), Span::new(0, 0))
561    }
562
563    #[test]
564    fn test_empty_grammar() {
565        let mut grm = GrammarAST::new();
566        match grm.complete_and_validate(None) {
567            Err(YaccGrammarError {
568                kind: YaccGrammarErrorKind::NoStartRule,
569                ..
570            }) => (),
571            _ => panic!("Validation error"),
572        }
573    }
574
575    #[test]
576    fn test_invalid_start_rule() {
577        let mut grm = GrammarAST::new();
578        let empty_span = Span::new(0, 0);
579        grm.start = Some(("A".to_string(), empty_span));
580        grm.add_rule(("B".to_string(), empty_span), None);
581        grm.add_prod("B".to_string(), vec![], None, None, empty_span);
582        match grm.complete_and_validate(None) {
583            Err(YaccGrammarError {
584                kind: YaccGrammarErrorKind::InvalidStartRule(_),
585                ..
586            }) => (),
587            _ => panic!("Validation error"),
588        }
589    }
590
591    #[test]
592    fn test_valid_start_rule() {
593        let mut grm = GrammarAST::new();
594        let empty_span = Span::new(0, 0);
595        grm.start = Some(("A".to_string(), empty_span));
596        grm.add_rule(("A".to_string(), empty_span), None);
597        grm.add_prod("A".to_string(), vec![], None, None, empty_span);
598        assert!(grm.complete_and_validate(None).is_ok());
599    }
600
601    #[test]
602    fn test_valid_rule_ref() {
603        let mut grm = GrammarAST::new();
604        let empty_span = Span::new(0, 0);
605        grm.start = Some(("A".to_string(), empty_span));
606        grm.add_rule(("A".to_string(), empty_span), None);
607        grm.add_rule(("B".to_string(), empty_span), None);
608        grm.add_prod("A".to_string(), vec![rule("B")], None, None, empty_span);
609        grm.add_prod("B".to_string(), vec![], None, None, empty_span);
610        assert!(grm.complete_and_validate(None).is_ok());
611    }
612
613    #[test]
614    fn test_invalid_rule_ref() {
615        let mut grm = GrammarAST::new();
616        let empty_span = Span::new(0, 0);
617        grm.start = Some(("A".to_string(), empty_span));
618        grm.add_rule(("A".to_string(), empty_span), None);
619        grm.add_prod("A".to_string(), vec![rule("B")], None, None, empty_span);
620        match grm.complete_and_validate(None) {
621            Err(YaccGrammarError {
622                kind: YaccGrammarErrorKind::UnknownRuleRef(_),
623                ..
624            }) => (),
625            _ => panic!("Validation error"),
626        }
627    }
628
629    #[test]
630    fn test_valid_token_ref() {
631        let mut grm = GrammarAST::new();
632        let empty_span = Span::new(0, 0);
633        grm.tokens.insert("b".to_string());
634        grm.start = Some(("A".to_string(), empty_span));
635        grm.add_rule(("A".to_string(), empty_span), None);
636        grm.add_prod("A".to_string(), vec![token("b")], None, None, empty_span);
637        assert!(grm.complete_and_validate(None).is_ok());
638    }
639
640    #[test]
641    fn test_redefine_rules_as_tokens() {
642        // for now we won't support the YACC feature that allows
643        // to redefine rules as tokens by adding them to '%token'
644        let mut grm = GrammarAST::new();
645        let empty_span = Span::new(0, 0);
646        grm.tokens.insert("b".to_string());
647        grm.start = Some(("A".to_string(), empty_span));
648        grm.add_rule(("A".to_string(), empty_span), None);
649        grm.add_prod("A".to_string(), vec![rule("b")], None, None, empty_span);
650        assert!(grm.complete_and_validate(None).is_err());
651    }
652
653    #[test]
654    fn test_invalid_token_ref() {
655        let mut grm = GrammarAST::new();
656        let empty_span = Span::new(0, 0);
657        grm.start = Some(("A".to_string(), empty_span));
658        grm.add_rule(("A".to_string(), empty_span), None);
659        grm.add_prod("A".to_string(), vec![token("b")], None, None, empty_span);
660        match grm.complete_and_validate(None) {
661            Err(YaccGrammarError {
662                kind: YaccGrammarErrorKind::UnknownToken(_),
663                ..
664            }) => (),
665            _ => panic!("Validation error"),
666        }
667    }
668
669    #[test]
670    fn test_invalid_rule_forgotten_token() {
671        let mut grm = GrammarAST::new();
672        let empty_span = Span::new(0, 0);
673        grm.start = Some(("A".to_string(), empty_span));
674        grm.add_rule(("A".to_string(), empty_span), None);
675        grm.add_prod(
676            "A".to_string(),
677            vec![rule("b"), token("b")],
678            None,
679            None,
680            Span::new(0, 2),
681        );
682        match grm.complete_and_validate(None) {
683            Err(YaccGrammarError {
684                kind: YaccGrammarErrorKind::UnknownRuleRef(_),
685                ..
686            }) => (),
687            _ => panic!("Validation error"),
688        }
689    }
690
691    #[test]
692    fn test_invalid_epp() {
693        let mut grm = GrammarAST::new();
694        let empty_span = Span::new(2, 3);
695        grm.start = Some(("A".to_string(), empty_span));
696        grm.add_rule(("A".to_string(), empty_span), None);
697        grm.add_prod("A".to_string(), vec![], None, None, empty_span);
698        grm.epp
699            .insert("k".to_owned(), (empty_span, ("v".to_owned(), empty_span)));
700        match grm.complete_and_validate(None) {
701            Err(YaccGrammarError {
702                kind: YaccGrammarErrorKind::UnknownEPP(_),
703                spans,
704            }) if spans.len() == 1 && spans[0] == Span::new(2, 3) => (),
705            _ => panic!("Validation error"),
706        }
707    }
708
709    #[test]
710    fn test_precedence_override() {
711        let mut grm = GrammarAST::new();
712        let empty_span = Span::new(0, 0);
713        grm.precs.insert(
714            "b".to_string(),
715            (
716                Precedence {
717                    level: 1,
718                    kind: AssocKind::Left,
719                },
720                Span::new(0, 0),
721            ),
722        );
723        grm.start = Some(("A".to_string(), empty_span));
724        grm.tokens.insert("b".to_string());
725        grm.add_rule(("A".to_string(), empty_span), None);
726        grm.add_prod(
727            "A".to_string(),
728            vec![token("b")],
729            Some("b".to_string()),
730            None,
731            empty_span,
732        );
733        assert!(grm.complete_and_validate(None).is_ok());
734    }
735
736    #[test]
737    fn test_invalid_precedence_override() {
738        let mut grm = GrammarAST::new();
739        let empty_span = Span::new(0, 0);
740        grm.start = Some(("A".to_string(), empty_span));
741        grm.add_rule(("A".to_string(), empty_span), None);
742        grm.add_prod(
743            "A".to_string(),
744            vec![token("b")],
745            Some("b".to_string()),
746            None,
747            empty_span,
748        );
749        match grm.complete_and_validate(None) {
750            Err(YaccGrammarError {
751                kind: YaccGrammarErrorKind::UnknownToken(_),
752                ..
753            }) => (),
754            _ => panic!("Validation error"),
755        }
756        grm.tokens.insert("b".to_string());
757        match grm.complete_and_validate(None) {
758            Err(YaccGrammarError {
759                kind: YaccGrammarErrorKind::NoPrecForToken(_),
760                ..
761            }) => (),
762            _ => panic!("Validation error"),
763        }
764    }
765
766    #[test]
767    fn test_ast_unused_symbols() {
768        let mut grm = GrammarAST::new();
769        let empty_span = Span::new(0, 0);
770        grm.start = Some(("A".to_string(), empty_span));
771        grm.add_rule(("A".to_string(), empty_span), None);
772        grm.add_prod("A".to_string(), vec![], None, None, empty_span);
773        grm.tokens.insert("b".to_string());
774        grm.spans.push(Span::new(4, 5));
775        grm.add_rule(("B".to_string(), Span::new(1, 2)), None);
776        grm.add_prod("B".to_string(), vec![token("b")], None, None, empty_span);
777
778        assert_eq!(
779            grm.unused_symbols()
780                .map(|sym_idx| sym_idx.symbol(&grm))
781                .collect::<Vec<Symbol>>()
782                .as_slice(),
783            &[
784                Symbol::Rule("B".to_string(), Span::new(1, 2)),
785                Symbol::Token("b".to_string(), Span::new(4, 5))
786            ]
787        )
788    }
789
790    #[test]
791    fn token_rule_confusion_issue_557() {
792        use super::*;
793        let ast_validity = ASTWithValidityInfo::new(
794            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
795            r#"
796            %start start
797            %%
798            start: "a" a;
799            a: "c";"#,
800        );
801        assert!(
802            ast_validity.ast().prods[0]
803                .symbols
804                .contains(&Symbol::Rule("a".to_string(), Span::new(64, 65)))
805        );
806        let ast_validity = ASTWithValidityInfo::new(
807            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
808            r#"
809            %start start
810            %%
811            start: "a" x;
812            x: "c";"#,
813        );
814        assert!(
815            ast_validity.ast().prods[0]
816                .symbols
817                .contains(&Symbol::Rule("x".to_string(), Span::new(64, 65)))
818        );
819        let ast_validity = ASTWithValidityInfo::new(
820            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
821            r#"
822        %start start
823        %token a
824        %%
825        start: "a" a;
826        "#,
827        );
828        assert_eq!(
829            ast_validity.ast().prods[0].symbols,
830            [
831                Symbol::Token("a".to_string(), Span::new(66, 67)),
832                Symbol::Token("a".to_string(), Span::new(69, 70))
833            ]
834        );
835    }
836
837    #[test]
838    fn test_token_directives() {
839        use super::*;
840
841        // Testing that `%token a` after `%left "a"` still ends up in
842        let ast_validity = ASTWithValidityInfo::new(
843            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
844            r#"
845                %left "a"
846                %token a
847                %start start
848                %%
849                start: "a" a "b";
850                "#,
851        );
852        assert!(
853            ast_validity
854                .ast()
855                .token_directives
856                .contains(&ast_validity.ast().tokens.get_index_of("a").unwrap())
857        );
858        assert!(
859            !ast_validity
860                .ast()
861                .token_directives
862                .contains(&ast_validity.ast().tokens.get_index_of("b").unwrap())
863        );
864    }
865
866    #[test]
867    fn clone_ast_changing_start_rule() {
868        use super::*;
869        let y_src = r#"
870        %start AStart
871        %token A B C
872        %%
873        AStart: A ':' BStart ';';
874        BStart: B ',' C | C ',' B;
875        "#;
876
877        let astart_ast_validity =
878            ASTWithValidityInfo::new(YaccKind::Original(YaccOriginalActionKind::NoAction), y_src);
879        let bstart_rule = astart_ast_validity.ast().get_rule("BStart").unwrap();
880        let bstart_ast_validity = astart_ast_validity
881            .clone_and_change_start_rule(bstart_rule.clone())
882            .unwrap();
883        assert!(astart_ast_validity.is_valid());
884        assert!(bstart_ast_validity.is_valid());
885        assert_eq!(
886            bstart_ast_validity.ast().start.as_ref(),
887            Some(&bstart_rule.name)
888        );
889    }
890
891    #[test]
892    fn test_missing_actiont() {
893        use super::*;
894        let ast_validity = ASTWithValidityInfo::new(
895            YaccKind::Original(YaccOriginalActionKind::UserAction),
896            r#"
897%token a
898%%
899start: "a";
900"#,
901        );
902        assert_eq!(
903            ast_validity.errors(),
904            vec![YaccGrammarError {
905                kind: YaccGrammarErrorKind::MissingActionType,
906                spans: vec![Span::new(13, 18)],
907            }]
908        );
909
910        let ast_validity = ASTWithValidityInfo::new(
911            YaccKind::Original(YaccOriginalActionKind::UserAction),
912            r#"
913%actiontype ()
914%token a
915%%
916start: "a" { };
917"#,
918        );
919        assert!(ast_validity.errors().is_empty());
920
921        let mut grm = GrammarAST::new();
922        let empty_span = Span::new(0, 0);
923        let rule_span = Span::new(255, 255);
924        grm.start = Some(("A".to_string(), empty_span));
925        grm.add_rule(("A".to_string(), rule_span), None);
926        grm.add_prod("A".to_string(), vec![], None, None, empty_span);
927        assert_eq!(
928            grm.complete_and_validate(Some(YaccKind::Grmtools)),
929            Err(YaccGrammarError {
930                kind: YaccGrammarErrorKind::MissingActionType,
931                spans: vec![rule_span],
932            })
933        );
934    }
935
936    #[test]
937    fn test_unrecognized_action_variable() {
938        use super::*;
939        let ast_validity = ASTWithValidityInfo::new(
940            YaccKind::Grmtools,
941            r#"
942%token a
943%%
944start -> () : "a" { $foo; };
945"#,
946        );
947        assert_eq!(
948            ast_validity.errors(),
949            vec![YaccGrammarError {
950                kind: YaccGrammarErrorKind::UnrecognisedActionVariable,
951                spans: vec![Span::new(33, 37)],
952            }]
953        );
954
955        let ast_validity = ASTWithValidityInfo::new(
956            YaccKind::Grmtools,
957            r#"
958%token a
959%%
960start -> () : "a" {$};
961"#,
962        );
963        assert_eq!(
964            ast_validity.errors(),
965            vec![YaccGrammarError {
966                kind: YaccGrammarErrorKind::UnrecognisedActionVariable,
967                spans: vec![Span::new(32, 33)],
968            }]
969        );
970
971        let ast_validity = ASTWithValidityInfo::new(
972            YaccKind::Grmtools,
973            r#"
974%token a
975%%
976start -> () : "a" {$;;;; };
977"#,
978        );
979        assert_eq!(
980            ast_validity.errors(),
981            vec![YaccGrammarError {
982                kind: YaccGrammarErrorKind::UnrecognisedActionVariable,
983                spans: vec![Span::new(32, 33)],
984            }]
985        );
986    }
987}
cfgrammar/yacc/ast.rs

cfgrammar/yacc/
ast.rs
