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