cfgrammar/yacc/
grammar.rs

1#![allow(clippy::derive_partial_eq_without_eq)]
2use std::{cell::RefCell, collections::HashMap, fmt::Write, str::FromStr};
3
4#[cfg(feature = "bincode")]
5use bincode::{Decode, Encode};
6use num_traits::{AsPrimitive, PrimInt, Unsigned};
7#[cfg(feature = "serde")]
8use serde::{Deserialize, Serialize};
9use vob::Vob;
10
11use super::{
12    ast,
13    firsts::YaccFirsts,
14    follows::YaccFollows,
15    parser::{YaccGrammarError, YaccGrammarResult},
16    YaccKind,
17};
18use crate::{PIdx, RIdx, SIdx, Span, Symbol, TIdx};
19
20const START_RULE: &str = "^";
21const IMPLICIT_RULE: &str = "~";
22const IMPLICIT_START_RULE: &str = "^~";
23
24pub type PrecedenceLevel = u64;
25#[derive(Clone, Copy, Debug, PartialEq)]
26#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
27#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
28pub struct Precedence {
29    pub level: PrecedenceLevel,
30    pub kind: AssocKind,
31}
32
33#[derive(Clone, Copy, Debug, PartialEq)]
34#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
35#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
36pub enum AssocKind {
37    Left,
38    Right,
39    Nonassoc,
40}
41
42/// Representation of a `YaccGrammar`. See the [top-level documentation](../../index.html) for the
43/// guarantees this struct makes about rules, tokens, productions, and symbols.
44#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
45#[cfg_attr(feature = "bincode", derive(Encode))]
46pub struct YaccGrammar<StorageT = u32> {
47    /// How many rules does this grammar have?
48    rules_len: RIdx<StorageT>,
49    /// A mapping from `RIdx` -> `(Span, String)`.
50    rule_names: Box<[(String, Span)]>,
51    /// A mapping from `TIdx` -> `Option<(Span, String)>`. Every user-specified token will have a name,
52    /// but tokens inserted by cfgrammar (e.g. the EOF token) won't.
53    token_names: Box<[Option<(Span, String)>]>,
54    /// A mapping from `TIdx` -> `Option<Precedence>`
55    token_precs: Box<[Option<Precedence>]>,
56    /// A mapping from `TIdx` -> `Option<String>` for the %epp declaration, giving pretty-printed
57    /// versions of token names that can be presented to the user in case of an error. Every
58    /// user-specified token will have a name that can be presented to the user (if a token doesn't
59    /// have an %epp entry, the token name will be used in lieu), but tokens inserted by cfgrammar
60    /// (e.g. the EOF token) won't.
61    token_epp: Box<[Option<String>]>,
62    /// How many tokens does this grammar have?
63    tokens_len: TIdx<StorageT>,
64    /// The offset of the EOF token.
65    eof_token_idx: TIdx<StorageT>,
66    /// How many productions does this grammar have?
67    prods_len: PIdx<StorageT>,
68    /// Which production is the sole production of the start rule?
69    start_prod: PIdx<StorageT>,
70    /// A list of all productions.
71    prods: Box<[Box<[Symbol<StorageT>]>]>,
72    /// A mapping from rules to their productions. Note that 1) the order of rules is identical to
73    /// that of `rule_names` 2) every rule will have at least 1 production 3) productions
74    /// are not necessarily stored sequentially.
75    rules_prods: Box<[Box<[PIdx<StorageT>]>]>,
76    /// A mapping from productions to their corresponding rule indexes.
77    prods_rules: Box<[RIdx<StorageT>]>,
78    /// The precedence of each production.
79    prod_precs: Box<[Option<Precedence>]>,
80    /// The index of the rule added for implicit tokens, if they were specified; otherwise
81    /// `None`.
82    implicit_rule: Option<RIdx<StorageT>>,
83    /// User defined Rust programs which can be called within actions
84    actions: Box<[Option<String>]>,
85    /// A `(name, type)` pair defining an extra parameter to pass to action functions.
86    parse_param: Option<(String, String)>,
87    /// Lifetimes for `param_args`
88    programs: Option<String>,
89    /// The actiontypes of rules (one per rule).
90    actiontypes: Box<[Option<String>]>,
91    /// Tokens marked as %avoid_insert (if any).
92    avoid_insert: Option<Vob>,
93    /// How many shift/reduce conflicts the grammar author expected (if any).
94    expect: Option<usize>,
95    /// How many reduce/reduce conflicts the grammar author expected (if any).
96    expectrr: Option<usize>,
97}
98
99// The implementations of `Decode` and `BorrowDecode`
100// Contain a modified copy of the output of `cargo expand` of the derivation:
101// #[cfg_attr(feature = "bincode", derive(Decode))]
102//
103// The current version of bincode has bugs in it's derive macro implementation
104// https://github.com/bincode-org/bincode/issues/763
105// https://github.com/bincode-org/bincode/issues/646
106//
107// Once those are fixed, we can replace this with derive.
108
109#[cfg(feature = "bincode")]
110impl<StorageT, __Context> Decode<__Context> for YaccGrammar<StorageT>
111where
112    StorageT: Decode<__Context> + 'static,
113{
114    fn decode<__D: bincode::de::Decoder<Context = __Context>>(
115        decoder: &mut __D,
116    ) -> Result<Self, bincode::error::DecodeError> {
117        Ok(Self {
118            rules_len: Decode::decode(decoder)?,
119            rule_names: Decode::decode(decoder)?,
120            token_names: Decode::decode(decoder)?,
121            token_precs: Decode::decode(decoder)?,
122            token_epp: Decode::decode(decoder)?,
123            tokens_len: Decode::decode(decoder)?,
124            eof_token_idx: Decode::decode(decoder)?,
125            prods_len: Decode::decode(decoder)?,
126            start_prod: Decode::decode(decoder)?,
127            prods: Decode::decode(decoder)?,
128            rules_prods: Decode::decode(decoder)?,
129            prods_rules: Decode::decode(decoder)?,
130            prod_precs: Decode::decode(decoder)?,
131            implicit_rule: Decode::decode(decoder)?,
132            actions: Decode::decode(decoder)?,
133            parse_param: Decode::decode(decoder)?,
134            programs: Decode::decode(decoder)?,
135            actiontypes: Decode::decode(decoder)?,
136            avoid_insert: Decode::decode(decoder)?,
137            expect: Decode::decode(decoder)?,
138            expectrr: Decode::decode(decoder)?,
139        })
140    }
141}
142
143// Eventually this should just be provided through:
144// #[cfg_attr(feature = "bincode", derive(Decode))]
145//
146// See comment at the corresponding bincode::Decode impl.
147#[cfg(feature = "bincode")]
148impl<'__de, StorageT, __Context> bincode::BorrowDecode<'__de, __Context> for YaccGrammar<StorageT>
149where
150    StorageT: bincode::de::BorrowDecode<'__de, __Context> + '__de,
151{
152    fn borrow_decode<__D: ::bincode::de::BorrowDecoder<'__de, Context = __Context>>(
153        decoder: &mut __D,
154    ) -> Result<Self, bincode::error::DecodeError> {
155        Ok(Self {
156            rules_len: bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
157            rule_names: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
158            token_names: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
159            token_precs: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
160            token_epp: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
161            tokens_len: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
162            eof_token_idx: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
163            prods_len: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
164            start_prod: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
165            prods: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
166            rules_prods: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
167            prods_rules: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
168            prod_precs: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
169            implicit_rule: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
170            actions: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
171            parse_param: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
172            programs: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
173            actiontypes: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
174            avoid_insert: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
175            expect: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
176            expectrr: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
177        })
178    }
179}
180
181// Internally, we assume that a grammar's start rule has a single production. Since we manually
182// create the start rule ourselves (without relying on user input), this is a safe assumption.
183
184impl YaccGrammar<u32> {
185    pub fn new(yk: YaccKind, s: &str) -> YaccGrammarResult<Self> {
186        YaccGrammar::new_with_storaget(yk, s)
187    }
188}
189
190impl<StorageT: 'static + PrimInt + Unsigned> FromStr for YaccGrammar<StorageT>
191where
192    usize: AsPrimitive<StorageT>,
193{
194    type Err = Vec<YaccGrammarError>;
195    fn from_str(s: &str) -> YaccGrammarResult<Self> {
196        let ast_validation = ast::ASTWithValidityInfo::from_str(s)?;
197        Self::new_from_ast_with_validity_info(&ast_validation)
198    }
199}
200
201impl<StorageT: 'static + PrimInt + Unsigned> YaccGrammar<StorageT>
202where
203    usize: AsPrimitive<StorageT>,
204{
205    /// Takes as input a Yacc grammar of [`YaccKind`](enum.YaccKind.html) as a `String` `s` and returns a
206    /// [`YaccGrammar`](grammar/struct.YaccGrammar.html) (or
207    /// ([`YaccGrammarError`](grammar/enum.YaccGrammarError.html) on error).
208    ///
209    /// As we're compiling the `YaccGrammar`, we add a new start rule (which we'll refer to as `^`,
210    /// though the actual name is a fresh name that is guaranteed to be unique) that references the
211    /// user defined start rule.
212    pub fn new_with_storaget(yk: YaccKind, s: &str) -> YaccGrammarResult<Self> {
213        let ast_validation = ast::ASTWithValidityInfo::new(yk, s);
214        Self::new_from_ast_with_validity_info(&ast_validation)
215    }
216
217    pub fn new_from_ast_with_validity_info(
218        ast_validation: &ast::ASTWithValidityInfo,
219    ) -> YaccGrammarResult<Self> {
220        if !ast_validation.is_valid() {
221            return Err(ast_validation.errors().to_owned());
222        }
223        let ast = ast_validation.ast();
224        // Check that StorageT is big enough to hold RIdx/PIdx/SIdx/TIdx values; after these
225        // checks we can guarantee that things like RIdx(ast.rules.len().as_()) are safe.
226        if ast.rules.len() > num_traits::cast(StorageT::max_value()).unwrap() {
227            panic!("StorageT is not big enough to store this grammar's rules.");
228        }
229        if ast.tokens.len() > num_traits::cast(StorageT::max_value()).unwrap() {
230            panic!("StorageT is not big enough to store this grammar's tokens.");
231        }
232        if ast.prods.len() > num_traits::cast(StorageT::max_value()).unwrap() {
233            panic!("StorageT is not big enough to store this grammar's productions.");
234        }
235        for p in &ast.prods {
236            if p.symbols.len() > num_traits::cast(StorageT::max_value()).unwrap() {
237                panic!("StorageT is not big enough to store the symbols of at least one of this grammar's productions.");
238            }
239        }
240
241        let mut rule_names: Vec<(String, Span)> = Vec::with_capacity(ast.rules.len() + 1);
242
243        // Generate a guaranteed unique start rule name. We simply keep making the string longer
244        // until we've hit something unique (at the very worst, this will require looping for as
245        // many times as there are rules). We use the same technique later for unique end
246        // token and whitespace names.
247        let mut start_rule = START_RULE.to_string();
248        while ast.rules.get(&start_rule).is_some() {
249            start_rule += START_RULE;
250        }
251        rule_names.push((start_rule.clone(), Span::new(0, 0)));
252
253        let implicit_rule;
254        let implicit_start_rule;
255        match ast_validation.yacc_kind() {
256            YaccKind::Original(_) | YaccKind::Grmtools => {
257                implicit_rule = None;
258                implicit_start_rule = None;
259            }
260            YaccKind::Eco => {
261                if ast.implicit_tokens.is_some() {
262                    let mut n1 = IMPLICIT_RULE.to_string();
263                    while ast.rules.get(&n1).is_some() {
264                        n1 += IMPLICIT_RULE;
265                    }
266                    rule_names.push((n1.clone(), Span::new(0, 0)));
267                    implicit_rule = Some(n1);
268                    let mut n2 = IMPLICIT_START_RULE.to_string();
269                    while ast.rules.get(&n2).is_some() {
270                        n2 += IMPLICIT_START_RULE;
271                    }
272                    rule_names.push((n2.clone(), Span::new(0, 0)));
273                    implicit_start_rule = Some(n2);
274                } else {
275                    implicit_rule = None;
276                    implicit_start_rule = None;
277                }
278            }
279        };
280
281        for (
282            k,
283            ast::Rule {
284                name: (_, name_span),
285                ..
286            },
287        ) in &ast.rules
288        {
289            rule_names.push((k.clone(), *name_span));
290        }
291        let mut rules_prods: Vec<Vec<PIdx<StorageT>>> = Vec::with_capacity(rule_names.len());
292        let mut rule_map = HashMap::<String, RIdx<StorageT>>::new();
293        for (i, (v, _)) in rule_names.iter().enumerate() {
294            rules_prods.push(Vec::new());
295            rule_map.insert(v.clone(), RIdx(i.as_()));
296        }
297
298        let mut token_names: Vec<Option<(Span, String)>> = Vec::with_capacity(ast.tokens.len() + 1);
299        let mut token_precs: Vec<Option<Precedence>> = Vec::with_capacity(ast.tokens.len() + 1);
300        let mut token_epp: Vec<Option<String>> = Vec::with_capacity(ast.tokens.len() + 1);
301        for (i, k) in ast.tokens.iter().enumerate() {
302            token_names.push(Some((ast.spans[i], k.clone())));
303            token_precs.push(ast.precs.get(k).map(|(prec, _)| prec).cloned());
304            token_epp.push(Some(
305                ast.epp.get(k).map(|(_, (s, _))| s).unwrap_or(k).clone(),
306            ));
307        }
308        let eof_token_idx = TIdx(token_names.len().as_());
309        token_names.push(None);
310        token_precs.push(None);
311        token_epp.push(None);
312        let mut token_map = HashMap::<String, TIdx<StorageT>>::new();
313        for (i, v) in token_names.iter().enumerate() {
314            if let Some((_, n)) = v.as_ref() {
315                token_map.insert(n.clone(), TIdx(i.as_()));
316            }
317        }
318
319        // In order to avoid fiddling about with production indices from the AST, we simply map
320        // tem 1:1 to grammar indices. That means that any new productions are added to the *end*
321        // of the list of productions.
322        let mut prods = vec![None; ast.prods.len()];
323        let mut prod_precs: Vec<Option<Option<Precedence>>> = vec![None; ast.prods.len()];
324        let mut prods_rules = vec![None; ast.prods.len()];
325        let mut actions = vec![None; ast.prods.len()];
326        let mut actiontypes = vec![None; rule_names.len()];
327        let (start_name, _) = ast.start.as_ref().unwrap();
328        for (astrulename, _) in &rule_names {
329            let ridx = rule_map[astrulename];
330            if astrulename == &start_rule {
331                // Add the special start rule which has a single production which references a
332                // single rule.
333                rules_prods[usize::from(ridx)].push(PIdx(prods.len().as_()));
334                let start_prod = match implicit_start_rule {
335                    None => {
336                        // Add ^: S;
337                        vec![Symbol::Rule(rule_map[start_name])]
338                    }
339                    Some(ref s) => {
340                        // An implicit rule has been specified, so the special start rule
341                        // needs to reference the intermediate start rule required. Therefore add:
342                        //   ^: ^~;
343                        vec![Symbol::Rule(rule_map[s])]
344                    }
345                };
346                prods.push(Some(start_prod));
347                prod_precs.push(Some(None));
348                prods_rules.push(Some(ridx));
349                actions.push(None);
350                continue;
351            } else if implicit_start_rule.as_ref() == Some(astrulename) {
352                // Add the intermediate start rule (handling implicit tokens at the beginning of
353                // the file):
354                //   ^~: ~ S;
355                rules_prods[usize::from(rule_map[astrulename])].push(PIdx(prods.len().as_()));
356                prods.push(Some(vec![
357                    Symbol::Rule(rule_map[implicit_rule.as_ref().unwrap()]),
358                    Symbol::Rule(rule_map[start_name]),
359                ]));
360                prod_precs.push(Some(None));
361                prods_rules.push(Some(ridx));
362                continue;
363            } else if implicit_rule.as_ref() == Some(astrulename) {
364                // Add the implicit rule: ~: "IMPLICIT_TOKEN_1" ~ | ... | "IMPLICIT_TOKEN_N" ~ | ;
365                let implicit_prods = &mut rules_prods[usize::from(rule_map[astrulename])];
366                // Add a production for each implicit token
367                for (t, _) in ast.implicit_tokens.as_ref().unwrap().iter() {
368                    implicit_prods.push(PIdx(prods.len().as_()));
369                    prods.push(Some(vec![Symbol::Token(token_map[t]), Symbol::Rule(ridx)]));
370                    prod_precs.push(Some(None));
371                    prods_rules.push(Some(ridx));
372                }
373                // Add an empty production
374                implicit_prods.push(PIdx(prods.len().as_()));
375                prods.push(Some(vec![]));
376                prod_precs.push(Some(None));
377                prods_rules.push(Some(ridx));
378                continue;
379            } else {
380                actiontypes[usize::from(ridx)] = ast.rules[astrulename].actiont.clone();
381            }
382
383            let rule = &mut rules_prods[usize::from(ridx)];
384            for &pidx in &ast.rules[astrulename].pidxs {
385                let astprod = &ast.prods[pidx];
386                let mut prod = Vec::with_capacity(astprod.symbols.len());
387                for astsym in &astprod.symbols {
388                    match *astsym {
389                        ast::Symbol::Rule(ref n, _) => {
390                            prod.push(Symbol::Rule(rule_map[n]));
391                        }
392                        ast::Symbol::Token(ref n, _) => {
393                            prod.push(Symbol::Token(token_map[n]));
394                            if let Some(implicit_rule) = &implicit_rule {
395                                prod.push(Symbol::Rule(rule_map[implicit_rule]));
396                            }
397                        }
398                    };
399                }
400                let mut prec = None;
401                if let Some(ref n) = astprod.precedence {
402                    prec = Some(ast.precs[n]);
403                } else {
404                    for astsym in astprod.symbols.iter().rev() {
405                        if let ast::Symbol::Token(ref n, _) = *astsym {
406                            if let Some(p) = ast.precs.get(n) {
407                                prec = Some(*p);
408                            }
409                            break;
410                        }
411                    }
412                }
413                (*rule).push(PIdx(pidx.as_()));
414                prods[pidx] = Some(prod);
415                prod_precs[pidx] = Some(prec.map(|(prec, _)| prec));
416                prods_rules[pidx] = Some(ridx);
417                if let Some(ref s) = astprod.action {
418                    actions[pidx] = Some(s.clone());
419                }
420            }
421        }
422
423        let avoid_insert = if let Some(ai) = &ast.avoid_insert {
424            let mut aiv = Vob::from_elem(false, token_names.len());
425            for n in ai.keys() {
426                aiv.set(usize::from(token_map[n]), true);
427            }
428            Some(aiv)
429        } else {
430            None
431        };
432
433        assert!(!token_names.is_empty());
434        assert!(!rule_names.is_empty());
435        Ok(YaccGrammar {
436            rules_len: RIdx(rule_names.len().as_()),
437            rule_names: rule_names.into_boxed_slice(),
438            tokens_len: TIdx(token_names.len().as_()),
439            eof_token_idx,
440            token_names: token_names.into_boxed_slice(),
441            token_precs: token_precs.into_boxed_slice(),
442            token_epp: token_epp.into_boxed_slice(),
443            prods_len: PIdx(prods.len().as_()),
444            start_prod: rules_prods[usize::from(rule_map[&start_rule])][0],
445            rules_prods: rules_prods
446                .iter()
447                .map(|x| x.iter().copied().collect())
448                .collect(),
449            prods_rules: prods_rules.into_iter().map(Option::unwrap).collect(),
450            prods: prods
451                .into_iter()
452                .map(|x| x.unwrap().into_boxed_slice())
453                .collect(),
454            prod_precs: prod_precs.into_iter().map(Option::unwrap).collect(),
455            implicit_rule: implicit_rule.map(|x| rule_map[&x]),
456            actions: actions.into_boxed_slice(),
457            parse_param: ast.parse_param.clone(),
458            programs: ast.programs.clone(),
459            avoid_insert,
460            actiontypes: actiontypes.into_boxed_slice(),
461            expect: ast.expect.map(|(n, _)| n),
462            expectrr: ast.expectrr.map(|(n, _)| n),
463        })
464    }
465
466    /// How many productions does this grammar have?
467    pub fn prods_len(&self) -> PIdx<StorageT> {
468        self.prods_len
469    }
470
471    /// Return an iterator which produces (in order from `0..self.prods_len()`) all this
472    /// grammar's valid `PIdx`s.
473    pub fn iter_pidxs(&self) -> impl Iterator<Item = PIdx<StorageT>> {
474        // We can use as_ safely, because we know that we're only generating integers from
475        // 0..self.rules_len() and, since rules_len() returns an RIdx<StorageT>, then by
476        // definition the integers we're creating fit within StorageT.
477        Box::new((0..usize::from(self.prods_len())).map(|x| PIdx(x.as_())))
478    }
479
480    /// Get the sequence of symbols for production `pidx`. Panics if `pidx` doesn't exist.
481    pub fn prod(&self, pidx: PIdx<StorageT>) -> &[Symbol<StorageT>] {
482        &self.prods[usize::from(pidx)]
483    }
484
485    /// How many symbols does production `pidx` have? Panics if `pidx` doesn't exist.
486    pub fn prod_len(&self, pidx: PIdx<StorageT>) -> SIdx<StorageT> {
487        // Since we've already checked that StorageT can store all the symbols for every production
488        // in the grammar, the call to as_ is safe.
489        SIdx(self.prods[usize::from(pidx)].len().as_())
490    }
491
492    /// Return the rule index of the production `pidx`. Panics if `pidx` doesn't exist.
493    pub fn prod_to_rule(&self, pidx: PIdx<StorageT>) -> RIdx<StorageT> {
494        self.prods_rules[usize::from(pidx)]
495    }
496
497    /// Return the precedence of production `pidx` (where `None` indicates "no precedence specified").
498    /// Panics if `pidx` doesn't exist.
499    pub fn prod_precedence(&self, pidx: PIdx<StorageT>) -> Option<Precedence> {
500        self.prod_precs[usize::from(pidx)]
501    }
502
503    /// Return the production index of the start rule's sole production (for Yacc grammars the
504    /// start rule is defined to have precisely one production).
505    pub fn start_prod(&self) -> PIdx<StorageT> {
506        self.start_prod
507    }
508
509    /// How many rules does this grammar have?
510    pub fn rules_len(&self) -> RIdx<StorageT> {
511        self.rules_len
512    }
513
514    /// Return an iterator which produces (in order from `0..self.rules_len()`) all this
515    /// grammar's valid `RIdx`s.
516    pub fn iter_rules(&self) -> impl Iterator<Item = RIdx<StorageT>> {
517        // We can use as_ safely, because we know that we're only generating integers from
518        // 0..self.rules_len() and, since rules_len() returns an RIdx<StorageT>, then by
519        // definition the integers we're creating fit within StorageT.
520        Box::new((0..usize::from(self.rules_len())).map(|x| RIdx(x.as_())))
521    }
522
523    /// Return the productions for rule `ridx`. Panics if `ridx` doesn't exist.
524    pub fn rule_to_prods(&self, ridx: RIdx<StorageT>) -> &[PIdx<StorageT>] {
525        &self.rules_prods[usize::from(ridx)]
526    }
527
528    /// Return the name of rule `ridx`. Panics if `ridx` doesn't exist.
529    #[deprecated(since = "0.13.0", note = "Please use rule_name_str instead")]
530    pub fn rule_name(&self, ridx: RIdx<StorageT>) -> &str {
531        self.rule_name_str(ridx)
532    }
533
534    /// Return the name of rule `ridx`. Panics if `ridx` doesn't exist.
535    pub fn rule_name_str(&self, ridx: RIdx<StorageT>) -> &str {
536        let (name, _) = &self.rule_names[usize::from(ridx)];
537        name.as_str()
538    }
539
540    /// Return the span of rule `ridx`. Panics if `ridx` doesn't exist.
541    pub fn rule_name_span(&self, ridx: RIdx<StorageT>) -> Span {
542        let (_, span) = self.rule_names[usize::from(ridx)];
543        span
544    }
545
546    /// Return the `RIdx` of the implict rule if it exists, or `None` otherwise.
547    pub fn implicit_rule(&self) -> Option<RIdx<StorageT>> {
548        self.implicit_rule
549    }
550
551    /// Return the index of the rule named `n` or `None` if it doesn't exist.
552    pub fn rule_idx(&self, n: &str) -> Option<RIdx<StorageT>> {
553        self.rule_names
554            .iter()
555            .position(|(x, _)| x == n)
556            // The call to as_() is safe because rule_names is guaranteed to be
557            // small enough to fit into StorageT
558            .map(|x| RIdx(x.as_()))
559    }
560
561    /// What is the index of the start rule? Note that cfgrammar will have inserted at least one
562    /// rule "above" the user's start rule.
563    pub fn start_rule_idx(&self) -> RIdx<StorageT> {
564        self.prod_to_rule(self.start_prod)
565    }
566
567    /// How many tokens does this grammar have?
568    pub fn tokens_len(&self) -> TIdx<StorageT> {
569        self.tokens_len
570    }
571
572    /// Return an iterator which produces (in order from `0..self.tokens_len()`) all this
573    /// grammar's valid `TIdx`s.
574    pub fn iter_tidxs(&self) -> impl Iterator<Item = TIdx<StorageT>> {
575        // We can use as_ safely, because we know that we're only generating integers from
576        // 0..self.rules_len() and, since rules_len() returns an TIdx<StorageT>, then by
577        // definition the integers we're creating fit within StorageT.
578        Box::new((0..usize::from(self.tokens_len())).map(|x| TIdx(x.as_())))
579    }
580
581    /// Return the index of the end token.
582    pub fn eof_token_idx(&self) -> TIdx<StorageT> {
583        self.eof_token_idx
584    }
585
586    /// Return the name of token `tidx` (where `None` indicates "the rule has no name"). Panics if
587    /// `tidx` doesn't exist.
588    pub fn token_name(&self, tidx: TIdx<StorageT>) -> Option<&str> {
589        self.token_names[usize::from(tidx)]
590            .as_ref()
591            .map(|(_, x)| x.as_str())
592    }
593
594    /// Return the precedence of token `tidx` (where `None` indicates "no precedence specified").
595    /// Panics if `tidx` doesn't exist.
596    pub fn token_precedence(&self, tidx: TIdx<StorageT>) -> Option<Precedence> {
597        self.token_precs[usize::from(tidx)]
598    }
599
600    /// Return the %epp entry for token `tidx` (where `None` indicates "the token has no
601    /// pretty-printed value"). Panics if `tidx` doesn't exist.
602    pub fn token_epp(&self, tidx: TIdx<StorageT>) -> Option<&str> {
603        self.token_epp[usize::from(tidx)].as_deref()
604    }
605
606    /// Return the span for token given by `tidx` if one exists.
607    /// If `None`, the token is either implicit and not derived from a token
608    /// in the source, otherwise the `YaccGrammar` itself may not derived from a
609    /// textual source in which case the token may be explicit but still lack spans
610    /// from its construction.
611    pub fn token_span(&self, tidx: TIdx<StorageT>) -> Option<Span> {
612        self.token_names[usize::from(tidx)]
613            .as_ref()
614            .map(|(span, _)| *span)
615    }
616
617    /// Get the action for production `pidx`. Panics if `pidx` doesn't exist.
618    pub fn action(&self, pidx: PIdx<StorageT>) -> &Option<String> {
619        &self.actions[usize::from(pidx)]
620    }
621
622    pub fn actiontype(&self, ridx: RIdx<StorageT>) -> &Option<String> {
623        &self.actiontypes[usize::from(ridx)]
624    }
625
626    pub fn parse_param(&self) -> &Option<(String, String)> {
627        &self.parse_param
628    }
629
630    /// Get the programs part of the grammar
631    pub fn programs(&self) -> &Option<String> {
632        &self.programs
633    }
634
635    /// Returns a map from names to `TIdx`s of all tokens that a lexer will need to generate valid
636    /// inputs from this grammar.
637    pub fn tokens_map(&self) -> HashMap<&str, TIdx<StorageT>> {
638        let mut m = HashMap::with_capacity(usize::from(self.tokens_len) - 1);
639        for tidx in self.iter_tidxs() {
640            if let Some((_, n)) = self.token_names[usize::from(tidx)].as_ref() {
641                m.insert(&**n, tidx);
642            }
643        }
644        m
645    }
646
647    /// Return the index of the token named `n` or `None` if it doesn't exist.
648    pub fn token_idx(&self, n: &str) -> Option<TIdx<StorageT>> {
649        self.token_names
650            .iter()
651            .position(|x| x.as_ref().is_some_and(|(_, x)| x == n))
652            // The call to as_() is safe because token_names is guaranteed to be small
653            // enough to fit into StorageT
654            .map(|x| TIdx(x.as_()))
655    }
656
657    /// Is the token `tidx` marked as `%avoid_insert`?
658    pub fn avoid_insert(&self, tidx: TIdx<StorageT>) -> bool {
659        if let Some(ai) = &self.avoid_insert {
660            ai.get(usize::from(tidx)).unwrap()
661        } else {
662            false
663        }
664    }
665
666    // How many shift/reduce conflicts were expected?
667    pub fn expect(&self) -> Option<usize> {
668        self.expect
669    }
670
671    // How many reduce/reduce conflicts were expected?
672    pub fn expectrr(&self) -> Option<usize> {
673        self.expectrr
674    }
675
676    /// Is there a path from the `from` rule to the `to` rule? Note that recursive rules
677    /// return `true` for a path from themselves to themselves.
678    pub fn has_path(&self, from: RIdx<StorageT>, to: RIdx<StorageT>) -> bool {
679        let mut seen = vec![];
680        seen.resize(usize::from(self.rules_len()), false);
681        let mut todo = vec![];
682        todo.resize(usize::from(self.rules_len()), false);
683        todo[usize::from(from)] = true;
684        loop {
685            let mut empty = true;
686            for ridx in self.iter_rules() {
687                if !todo[usize::from(ridx)] {
688                    continue;
689                }
690                seen[usize::from(ridx)] = true;
691                todo[usize::from(ridx)] = false;
692                empty = false;
693                for pidx in self.rule_to_prods(ridx).iter() {
694                    for sym in self.prod(*pidx) {
695                        if let Symbol::Rule(p_ridx) = *sym {
696                            if p_ridx == to {
697                                return true;
698                            }
699                            if !seen[usize::from(p_ridx)] {
700                                todo[usize::from(p_ridx)] = true;
701                            }
702                        }
703                    }
704                }
705            }
706            if empty {
707                return false;
708            }
709        }
710    }
711
712    /// Returns the string representation of a given production `pidx`.
713    pub fn pp_prod(&self, pidx: PIdx<StorageT>) -> String {
714        let mut sprod = String::new();
715        let ridx = self.prod_to_rule(pidx);
716        sprod.push_str(self.rule_name_str(ridx));
717        sprod.push(':');
718        for sym in self.prod(pidx) {
719            let s = match sym {
720                Symbol::Token(tidx) => self.token_name(*tidx).unwrap(),
721                Symbol::Rule(ridx) => self.rule_name_str(*ridx),
722            };
723            write!(sprod, " \"{}\"", s).ok();
724        }
725        sprod
726    }
727
728    /// Return a `SentenceGenerator` which can then generate minimal sentences for any rule
729    /// based on the user-defined `token_cost` function which gives the associated cost for
730    /// generating each token (where the cost must be greater than 0). Note that multiple
731    /// tokens can have the same score. The simplest cost function is thus `|_| 1`.
732    pub fn sentence_generator<F>(&self, token_cost: F) -> SentenceGenerator<StorageT>
733    where
734        F: Fn(TIdx<StorageT>) -> u8,
735    {
736        SentenceGenerator::new(self, token_cost)
737    }
738
739    /// Return a `YaccFirsts` struct for this grammar.
740    pub fn firsts(&self) -> YaccFirsts<StorageT> {
741        YaccFirsts::new(self)
742    }
743
744    /// Return a `YaccFirsts` struct for this grammar.
745    pub fn follows(&self) -> YaccFollows<StorageT> {
746        YaccFollows::new(self)
747    }
748}
749
750/// A `SentenceGenerator` can generate minimal sentences for any given rule. e.g. for the
751/// grammar:
752///
753/// ```text
754/// %start A
755/// %%
756/// A: A B | ;
757/// B: C | D;
758/// C: 'x' B | 'x';
759/// D: 'y' B | 'y' 'z';
760/// ```
761///
762/// the following are valid minimal sentences:
763///
764/// ```text
765/// A: []
766/// B: [x]
767/// C: [x]
768/// D: [y, x] or [y, z]
769/// ```
770pub struct SentenceGenerator<'a, StorageT> {
771    grm: &'a YaccGrammar<StorageT>,
772    rule_min_costs: RefCell<Option<Vec<u16>>>,
773    rule_max_costs: RefCell<Option<Vec<u16>>>,
774    token_costs: Vec<u8>,
775}
776
777impl<'a, StorageT: 'static + PrimInt + Unsigned> SentenceGenerator<'a, StorageT>
778where
779    usize: AsPrimitive<StorageT>,
780{
781    fn new<F>(grm: &'a YaccGrammar<StorageT>, token_cost: F) -> Self
782    where
783        F: Fn(TIdx<StorageT>) -> u8,
784    {
785        let mut token_costs = Vec::with_capacity(usize::from(grm.tokens_len()));
786        for tidx in grm.iter_tidxs() {
787            token_costs.push(token_cost(tidx));
788        }
789        SentenceGenerator {
790            grm,
791            token_costs,
792            rule_min_costs: RefCell::new(None),
793            rule_max_costs: RefCell::new(None),
794        }
795    }
796
797    /// What is the cost of a minimal sentence for the rule `ridx`? Note that, unlike
798    /// `min_sentence`, this function does not actually *build* a sentence and it is thus much
799    /// faster.
800    pub fn min_sentence_cost(&self, ridx: RIdx<StorageT>) -> u16 {
801        self.rule_min_costs
802            .borrow_mut()
803            .get_or_insert_with(|| rule_min_costs(self.grm, &self.token_costs))[usize::from(ridx)]
804    }
805
806    /// What is the cost of a maximal sentence for the rule `ridx`? Rules which can generate
807    /// sentences of unbounded length return None; rules which can only generate maximal strings of
808    /// a finite length return a `Some(u16)`.
809    pub fn max_sentence_cost(&self, ridx: RIdx<StorageT>) -> Option<u16> {
810        let v = self
811            .rule_max_costs
812            .borrow_mut()
813            .get_or_insert_with(|| rule_max_costs(self.grm, &self.token_costs))[usize::from(ridx)];
814        if v == u16::MAX {
815            None
816        } else {
817            Some(v)
818        }
819    }
820
821    /// Non-deterministically return a minimal sentence from the set of minimal sentences for the
822    /// rule `ridx`.
823    pub fn min_sentence(&self, ridx: RIdx<StorageT>) -> Vec<TIdx<StorageT>> {
824        let cheapest_prod = |p_ridx: RIdx<StorageT>| -> PIdx<StorageT> {
825            let mut low_sc = None;
826            let mut low_idx = None;
827            for &pidx in self.grm.rule_to_prods(p_ridx).iter() {
828                let mut sc = 0;
829                for sym in self.grm.prod(pidx).iter() {
830                    sc += match *sym {
831                        Symbol::Rule(i) => self.min_sentence_cost(i),
832                        Symbol::Token(i) => u16::from(self.token_costs[usize::from(i)]),
833                    };
834                }
835                if low_sc.is_none() || Some(sc) < low_sc {
836                    low_sc = Some(sc);
837                    low_idx = Some(pidx);
838                }
839            }
840            low_idx.unwrap()
841        };
842
843        let mut s = vec![];
844        let mut st = vec![(cheapest_prod(ridx), 0)];
845        while let Some((pidx, sym_idx)) = st.pop() {
846            let prod = self.grm.prod(pidx);
847            for (sidx, sym) in prod.iter().enumerate().skip(sym_idx) {
848                match sym {
849                    Symbol::Rule(s_ridx) => {
850                        st.push((pidx, sidx + 1));
851                        st.push((cheapest_prod(*s_ridx), 0));
852                    }
853                    Symbol::Token(s_tidx) => {
854                        s.push(*s_tidx);
855                    }
856                }
857            }
858        }
859        s
860    }
861
862    /// Return (in arbitrary order) all the minimal sentences for the rule `ridx`.
863    pub fn min_sentences(&self, ridx: RIdx<StorageT>) -> Vec<Vec<TIdx<StorageT>>> {
864        let cheapest_prods = |p_ridx: RIdx<StorageT>| -> Vec<PIdx<StorageT>> {
865            let mut low_sc = None;
866            let mut low_idxs = vec![];
867            for &pidx in self.grm.rule_to_prods(p_ridx).iter() {
868                let mut sc = 0;
869                for sym in self.grm.prod(pidx).iter() {
870                    sc += match *sym {
871                        Symbol::Rule(s_ridx) => self.min_sentence_cost(s_ridx),
872                        Symbol::Token(s_tidx) => u16::from(self.token_costs[usize::from(s_tidx)]),
873                    };
874                }
875                if low_sc.is_none() || Some(sc) <= low_sc {
876                    if Some(sc) < low_sc {
877                        low_idxs.clear();
878                    }
879                    low_sc = Some(sc);
880                    low_idxs.push(pidx);
881                }
882            }
883            low_idxs
884        };
885
886        let mut sts = Vec::new(); // Output sentences
887        for pidx in cheapest_prods(ridx) {
888            let prod = self.grm.prod(pidx);
889            if prod.is_empty() {
890                sts.push(vec![]);
891                continue;
892            }
893
894            // We construct the minimal sentences in two phases.
895            //
896            // First, for each symbol in the production, we gather all the possible minimal
897            // sentences for it. If, for the grammar:
898            //   X: 'a' Y
899            //   Y: 'b' | 'c'
900            // we ask for the minimal sentences of X's only production we'll end up with a vec of
901            // vecs as follows:
902            //   [[['a']], [['b'], ['c']]]
903
904            let mut ms = Vec::with_capacity(prod.len());
905            for sym in prod {
906                match *sym {
907                    Symbol::Rule(s_ridx) => ms.push(self.min_sentences(s_ridx)),
908                    Symbol::Token(s_tidx) => ms.push(vec![vec![s_tidx]]),
909                }
910            }
911
912            // Second, we need to generate all combinations of the gathered sentences. We do this
913            // by writing our own simple numeric incrementing scheme. If we rewrite the list from
914            // above as follows:
915            //
916            //      0 1 <- call this axis "i"
917            //   0: a b
918            //   1:   c
919            //   ^
920            //   |
921            //   call this axis "todo"
922            //
923            // this hopefully becomes easier to see. Let's call the list "ms": the combinations we
924            // need to generate are thus:
925            //
926            //   ms[0][0] + ms[1][0]  (i.e. 'ab')
927            //   ms[0][0] + ms[1][1]  (i.e. 'ac')
928            //
929            // The easiest way to model this is to have a list (todo) with each entry starting at
930            // 0. After each iteration around the loop (i) we add 1 to the last todo column's
931            // entry: if that spills over the length of the corresponding ms entry, then we reset
932            // that column to zero, and try adding 1 to the previous column (as many times as
933            // needed). If the first column spills, then we're done. This is basically normal
934            // arithmetic but with each digit having an arbitrary base.
935
936            let mut todo = vec![0; prod.len()];
937            let mut cur = Vec::new();
938            'b: loop {
939                for i in 0..todo.len() {
940                    cur.extend(&ms[i][todo[i]]);
941                }
942                sts.push(std::mem::take(&mut cur));
943
944                let mut j = todo.len() - 1;
945                loop {
946                    if todo[j] + 1 == ms[j].len() {
947                        if j == 0 {
948                            break 'b;
949                        }
950                        todo[j] = 0;
951                        j -= 1;
952                    } else {
953                        todo[j] += 1;
954                        break;
955                    }
956                }
957            }
958        }
959        sts
960    }
961}
962
963/// Return the cost of a minimal string for each rule in this grammar. The cost of a
964/// token is specified by the user-defined `token_cost` function.
965#[allow(clippy::unnecessary_unwrap)]
966fn rule_min_costs<StorageT: 'static + PrimInt + Unsigned>(
967    grm: &YaccGrammar<StorageT>,
968    token_costs: &[u8],
969) -> Vec<u16>
970where
971    usize: AsPrimitive<StorageT>,
972{
973    // We use a simple(ish) fixed-point algorithm to determine costs. We maintain two lists
974    // "costs" and "done". An integer costs[i] starts at 0 and monotonically increments
975    // until done[i] is true, at which point costs[i] value is fixed. We also use the done
976    // list as a simple "todo" list: whilst there is at least one false value in done, there is
977    // still work to do.
978    //
979    // On each iteration of the loop, we examine each rule in the todo list to see if
980    // we can get a better idea of its true cost. Some are trivial:
981    //   * A rule with an empty production immediately has a cost of 0.
982    //   * Rules whose productions don't reference any rules (i.e. only contain tokens) can be
983    //     immediately given a cost by calculating the lowest-cost production.
984    // However if a rule A references another rule B, we may need to wait until
985    // we've fully analysed B before we can cost A. This might seem to cause problems with
986    // recursive rules, so we introduce the concept of "incomplete costs" i.e. if a production
987    // references a rule we can work out its minimum possible cost simply by counting
988    // the production's token costs. Since rules can have a mix of complete and
989    // incomplete productions, this is sometimes enough to allow us to assign a final cost to
990    // a rule (if the lowest complete production's cost is lower than or equal to all
991    // the lowest incomplete production's cost). This allows us to make progress, since it
992    // means that we can iteratively improve our knowledge of a token's minimum cost:
993    // eventually we will reach a point where we can determine it definitively.
994
995    let mut costs = vec![0; usize::from(grm.rules_len())];
996    let mut done = vec![false; usize::from(grm.rules_len())];
997    loop {
998        let mut all_done = true;
999        for i in 0..done.len() {
1000            if done[i] {
1001                continue;
1002            }
1003            all_done = false;
1004            let mut ls_cmplt = None; // lowest completed cost
1005            let mut ls_noncmplt = None; // lowest non-completed cost
1006
1007            // The call to as_() is guaranteed safe because done.len() == grm.rules_len(), and
1008            // we guarantee that grm.rules_len() can fit in StorageT.
1009            for pidx in grm.rule_to_prods(RIdx(i.as_())).iter() {
1010                let mut c: u16 = 0; // production cost
1011                let mut cmplt = true;
1012                for sym in grm.prod(*pidx) {
1013                    let sc = match *sym {
1014                        Symbol::Token(tidx) => u16::from(token_costs[usize::from(tidx)]),
1015                        Symbol::Rule(ridx) => {
1016                            if !done[usize::from(ridx)] {
1017                                cmplt = false;
1018                            }
1019                            costs[usize::from(ridx)]
1020                        }
1021                    };
1022                    c = c
1023                        .checked_add(sc)
1024                        .expect("Overflow occurred when calculating rule costs");
1025                }
1026                if cmplt && (ls_cmplt.is_none() || Some(c) < ls_cmplt) {
1027                    ls_cmplt = Some(c);
1028                } else if !cmplt && (ls_noncmplt.is_none() || Some(c) < ls_noncmplt) {
1029                    ls_noncmplt = Some(c);
1030                }
1031            }
1032            if ls_cmplt.is_some() && (ls_noncmplt.is_none() || ls_cmplt < ls_noncmplt) {
1033                debug_assert!(ls_cmplt.unwrap() >= costs[i]);
1034                costs[i] = ls_cmplt.unwrap();
1035                done[i] = true;
1036            } else if let Some(ls_noncmplt) = ls_noncmplt {
1037                debug_assert!(ls_noncmplt >= costs[i]);
1038                costs[i] = ls_noncmplt;
1039            }
1040        }
1041        if all_done {
1042            debug_assert!(done.iter().all(|x| *x));
1043            break;
1044        }
1045    }
1046    costs
1047}
1048
1049/// Return the cost of the maximal string for each rule in this grammar (u32::max_val()
1050/// representing "this rule can generate strings of infinite length"). The cost of a
1051/// token is specified by the user-defined `token_cost` function.
1052#[allow(clippy::unnecessary_unwrap)]
1053fn rule_max_costs<StorageT: 'static + PrimInt + Unsigned>(
1054    grm: &YaccGrammar<StorageT>,
1055    token_costs: &[u8],
1056) -> Vec<u16>
1057where
1058    usize: AsPrimitive<StorageT>,
1059{
1060    let mut done = vec![false; usize::from(grm.rules_len())];
1061    let mut costs = vec![0; usize::from(grm.rules_len())];
1062
1063    // First mark all recursive rules.
1064    for ridx in grm.iter_rules() {
1065        // Calling has_path so frequently is not exactly efficient...
1066        if grm.has_path(ridx, ridx) {
1067            costs[usize::from(ridx)] = u16::MAX;
1068            done[usize::from(ridx)] = true;
1069        }
1070    }
1071
1072    loop {
1073        let mut all_done = true;
1074        for i in 0..done.len() {
1075            if done[i] {
1076                continue;
1077            }
1078            all_done = false;
1079            let mut hs_cmplt = None; // highest completed cost
1080            let mut hs_noncmplt = None; // highest non-completed cost
1081
1082            // The call to as_() is guaranteed safe because done.len() == grm.rules_len(), and
1083            // we guarantee that grm.rules_len() can fit in StorageT.
1084            'a: for pidx in grm.rule_to_prods(RIdx(i.as_())).iter() {
1085                let mut c: u16 = 0; // production cost
1086                let mut cmplt = true;
1087                for sym in grm.prod(*pidx) {
1088                    let sc = match *sym {
1089                        Symbol::Token(s_tidx) => u16::from(token_costs[usize::from(s_tidx)]),
1090                        Symbol::Rule(s_ridx) => {
1091                            if costs[usize::from(s_ridx)] == u16::MAX {
1092                                // As soon as we find reference to an infinite rule, we
1093                                // can stop looking.
1094                                hs_cmplt = Some(u16::MAX);
1095                                break 'a;
1096                            }
1097                            if !done[usize::from(s_ridx)] {
1098                                cmplt = false;
1099                            }
1100                            costs[usize::from(s_ridx)]
1101                        }
1102                    };
1103                    c = c
1104                        .checked_add(sc)
1105                        .expect("Overflow occurred when calculating rule costs");
1106                    if c == u16::MAX {
1107                        panic!("Unable to represent cost in 64 bits.");
1108                    }
1109                }
1110                if cmplt && (hs_cmplt.is_none() || Some(c) > hs_cmplt) {
1111                    hs_cmplt = Some(c);
1112                } else if !cmplt && (hs_noncmplt.is_none() || Some(c) > hs_noncmplt) {
1113                    hs_noncmplt = Some(c);
1114                }
1115            }
1116            if hs_cmplt.is_some() && (hs_noncmplt.is_none() || hs_cmplt > hs_noncmplt) {
1117                debug_assert!(hs_cmplt.unwrap() >= costs[i]);
1118                costs[i] = hs_cmplt.unwrap();
1119                done[i] = true;
1120            } else if let Some(hs_noncmplt) = hs_noncmplt {
1121                debug_assert!(hs_noncmplt >= costs[i]);
1122                costs[i] = hs_noncmplt;
1123            }
1124        }
1125        if all_done {
1126            debug_assert!(done.iter().all(|x| *x));
1127            break;
1128        }
1129    }
1130    costs
1131}
1132
1133#[cfg(test)]
1134mod test {
1135    use super::{
1136        super::{AssocKind, Precedence, YaccGrammar, YaccKind, YaccOriginalActionKind},
1137        rule_max_costs, rule_min_costs, IMPLICIT_RULE, IMPLICIT_START_RULE,
1138    };
1139    use crate::{PIdx, RIdx, Span, Symbol, TIdx};
1140    use std::collections::HashMap;
1141    use std::str::FromStr;
1142
1143    macro_rules! bslice {
1144        () => (
1145            ::Vec::new().into_boxed_slice()
1146        );
1147        ($elem:expr; $n:expr) => (
1148            ::vec::from_elem($elem, $n).into_boxed_slice()
1149        );
1150        ($($x:expr),+ $(,)?) => (
1151            <[_]>::into_vec(
1152                Box::new([$($x),+])
1153            ).into_boxed_slice()
1154        );
1155    }
1156
1157    #[test]
1158    fn test_minimal() {
1159        let grm = YaccGrammar::new(
1160            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1161            "%start R %token T %% R: 'T';",
1162        )
1163        .unwrap();
1164
1165        assert_eq!(grm.start_prod, PIdx(1));
1166        assert_eq!(grm.implicit_rule(), None);
1167        grm.rule_idx("^").unwrap();
1168        grm.rule_idx("R").unwrap();
1169        grm.token_idx("T").unwrap();
1170
1171        assert_eq!(&*grm.rules_prods, &[bslice![PIdx(1)], bslice![PIdx(0)]]);
1172        let start_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("^").unwrap())][0]);
1173        assert_eq!(*start_prod, [Symbol::Rule(grm.rule_idx("R").unwrap())]);
1174        let r_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("R").unwrap())][0]);
1175        assert_eq!(*r_prod, [Symbol::Token(grm.token_idx("T").unwrap())]);
1176        assert_eq!(&*grm.prods_rules, &[RIdx(1), RIdx(0)]);
1177
1178        assert_eq!(
1179            grm.tokens_map(),
1180            [("T", TIdx(0))]
1181                .iter()
1182                .cloned()
1183                .collect::<HashMap<&str, TIdx<_>>>()
1184        );
1185        assert_eq!(grm.iter_rules().collect::<Vec<_>>(), vec![RIdx(0), RIdx(1)]);
1186    }
1187
1188    #[test]
1189    fn test_rule_ref() {
1190        let grm = YaccGrammar::new(
1191            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1192            "%start R %token T %% R : S; S: 'T';",
1193        )
1194        .unwrap();
1195
1196        grm.rule_idx("^").unwrap();
1197        grm.rule_idx("R").unwrap();
1198        grm.rule_idx("S").unwrap();
1199        grm.token_idx("T").unwrap();
1200        assert!(grm.token_name(grm.eof_token_idx()).is_none());
1201
1202        assert_eq!(
1203            &*grm.rules_prods,
1204            &[bslice![PIdx(2)], bslice![PIdx(0)], bslice![PIdx(1)]]
1205        );
1206        let start_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("^").unwrap())][0]);
1207        assert_eq!(*start_prod, [Symbol::Rule(grm.rule_idx("R").unwrap())]);
1208        let r_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("R").unwrap())][0]);
1209        assert_eq!(r_prod.len(), 1);
1210        assert_eq!(r_prod[0], Symbol::Rule(grm.rule_idx("S").unwrap()));
1211        let s_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("S").unwrap())][0]);
1212        assert_eq!(s_prod.len(), 1);
1213        assert_eq!(s_prod[0], Symbol::Token(grm.token_idx("T").unwrap()));
1214    }
1215
1216    #[test]
1217    #[rustfmt::skip]
1218    fn test_long_prod() {
1219        let grm = YaccGrammar::new(
1220            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1221            "%start R %token T1 T2 %% R : S 'T1' S; S: 'T2';"
1222        ).unwrap();
1223
1224        grm.rule_idx("^").unwrap();
1225        grm.rule_idx("R").unwrap();
1226        grm.rule_idx("S").unwrap();
1227        grm.token_idx("T1").unwrap();
1228        grm.token_idx("T2").unwrap();
1229
1230        assert_eq!(&*grm.rules_prods, &[bslice![PIdx(2)],
1231                                         bslice![PIdx(0)],
1232                                         bslice![PIdx(1)]]);
1233        assert_eq!(&*grm.prods_rules, &[RIdx(1),
1234                                         RIdx(2),
1235                                         RIdx(0)]);
1236        let start_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("^").unwrap())][0]);
1237        assert_eq!(*start_prod, [Symbol::Rule(grm.rule_idx("R").unwrap())]);
1238        let r_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("R").unwrap())][0]);
1239        assert_eq!(r_prod.len(), 3);
1240        assert_eq!(r_prod[0], Symbol::Rule(grm.rule_idx("S").unwrap()));
1241        assert_eq!(r_prod[1], Symbol::Token(grm.token_idx("T1").unwrap()));
1242        assert_eq!(r_prod[2], Symbol::Rule(grm.rule_idx("S").unwrap()));
1243        let s_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("S").unwrap())][0]);
1244        assert_eq!(s_prod.len(), 1);
1245        assert_eq!(s_prod[0], Symbol::Token(grm.token_idx("T2").unwrap()));
1246    }
1247
1248    #[test]
1249    fn test_prods_rules() {
1250        let grm = YaccGrammar::new(
1251            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1252            "
1253            %start A
1254            %%
1255            A: B
1256             | C;
1257            B: 'x';
1258            C: 'y'
1259             | 'z';
1260          ",
1261        )
1262        .unwrap();
1263
1264        assert_eq!(
1265            &*grm.prods_rules,
1266            &[RIdx(1), RIdx(1), RIdx(2), RIdx(3), RIdx(3), RIdx(0)]
1267        );
1268    }
1269
1270    #[test]
1271    #[rustfmt::skip]
1272    fn test_left_right_nonassoc_precs() {
1273        let grm = YaccGrammar::new(
1274            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1275            "
1276            %start Expr
1277            %right '='
1278            %left '+' '-'
1279            %left '/'
1280            %left '*'
1281            %nonassoc '~'
1282            %%
1283            Expr : Expr '=' Expr
1284                 | Expr '+' Expr
1285                 | Expr '-' Expr
1286                 | Expr '/' Expr
1287                 | Expr '*' Expr
1288                 | Expr '~' Expr
1289                 | 'id' ;
1290          ").unwrap();
1291
1292        assert_eq!(grm.prod_precs.len(), 8);
1293        assert_eq!(grm.prod_precs[0].unwrap(), Precedence{level: 0, kind: AssocKind::Right});
1294        assert_eq!(grm.prod_precs[1].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1295        assert_eq!(grm.prod_precs[2].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1296        assert_eq!(grm.prod_precs[3].unwrap(), Precedence{level: 2, kind: AssocKind::Left});
1297        assert_eq!(grm.prod_precs[4].unwrap(), Precedence{level: 3, kind: AssocKind::Left});
1298        assert_eq!(grm.prod_precs[5].unwrap(), Precedence{level: 4, kind: AssocKind::Nonassoc});
1299        assert!(grm.prod_precs[6].is_none());
1300        assert_eq!(grm.prod_precs[7], None);
1301    }
1302
1303    #[test]
1304    #[rustfmt::skip]
1305    fn test_prec_override() {
1306        let grm = YaccGrammar::new(
1307            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1308            "
1309            %start expr
1310            %left '+' '-'
1311            %left '*' '/'
1312            %%
1313            expr : expr '+' expr
1314                 | expr '-' expr
1315                 | expr '*' expr
1316                 | expr '/' expr
1317                 | '-'  expr %prec '*'
1318                 | 'id' ;
1319        "
1320        ).unwrap();
1321        assert_eq!(grm.prod_precs.len(), 7);
1322        assert_eq!(grm.prod_precs[0].unwrap(), Precedence{level: 0, kind: AssocKind::Left});
1323        assert_eq!(grm.prod_precs[1].unwrap(), Precedence{level: 0, kind: AssocKind::Left});
1324        assert_eq!(grm.prod_precs[2].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1325        assert_eq!(grm.prod_precs[3].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1326        assert_eq!(grm.prod_precs[4].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1327        assert!(grm.prod_precs[5].is_none());
1328        assert_eq!(grm.prod_precs[6], None);
1329    }
1330
1331    #[test]
1332    #[rustfmt::skip]
1333    fn test_implicit_tokens_rewrite() {
1334        let grm = YaccGrammar::new(
1335            YaccKind::Eco,
1336            "
1337          %implicit_tokens ws1 ws2
1338          %start S
1339          %%
1340          S: 'a' | T;
1341          T: 'c' |;
1342          "
1343        ).unwrap();
1344
1345        // Check that the above grammar has been rewritten to:
1346        //   ^ : ^~;
1347        //   ^~: ~ S;
1348        //   ~ : ws1 | ws2 | ;
1349        //   S : 'a' ~ | T;
1350        //   T : 'c' ~ | ;
1351
1352        assert_eq!(grm.prod_precs.len(), 9);
1353
1354        let itfs_rule_idx = grm.rule_idx(IMPLICIT_START_RULE).unwrap();
1355        assert_eq!(grm.rules_prods[usize::from(itfs_rule_idx)].len(), 1);
1356
1357        let itfs_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(itfs_rule_idx)][0])];
1358        assert_eq!(itfs_prod1.len(), 2);
1359        assert_eq!(itfs_prod1[0], Symbol::Rule(grm.rule_idx(IMPLICIT_RULE).unwrap()));
1360        assert_eq!(itfs_prod1[1], Symbol::Rule(grm.rule_idx("S").unwrap()));
1361
1362        let s_rule_idx = grm.rule_idx("S").unwrap();
1363        assert_eq!(grm.rules_prods[usize::from(s_rule_idx)].len(), 2);
1364
1365        let s_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(s_rule_idx)][0])];
1366        assert_eq!(s_prod1.len(), 2);
1367        assert_eq!(s_prod1[0], Symbol::Token(grm.token_idx("a").unwrap()));
1368        assert_eq!(s_prod1[1], Symbol::Rule(grm.rule_idx(IMPLICIT_RULE).unwrap()));
1369
1370        let s_prod2 = &grm.prods[usize::from(grm.rules_prods[usize::from(s_rule_idx)][1])];
1371        assert_eq!(s_prod2.len(), 1);
1372        assert_eq!(s_prod2[0], Symbol::Rule(grm.rule_idx("T").unwrap()));
1373
1374        let t_rule_idx = grm.rule_idx("T").unwrap();
1375        assert_eq!(grm.rules_prods[usize::from(s_rule_idx)].len(), 2);
1376
1377        let t_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(t_rule_idx)][0])];
1378        assert_eq!(t_prod1.len(), 2);
1379        assert_eq!(t_prod1[0], Symbol::Token(grm.token_idx("c").unwrap()));
1380        assert_eq!(t_prod1[1], Symbol::Rule(grm.rule_idx(IMPLICIT_RULE).unwrap()));
1381
1382        let t_prod2 = &grm.prods[usize::from(grm.rules_prods[usize::from(t_rule_idx)][1])];
1383        assert_eq!(t_prod2.len(), 0);
1384
1385        assert_eq!(Some(grm.rule_idx(IMPLICIT_RULE).unwrap()), grm.implicit_rule());
1386        let i_rule_idx = grm.rule_idx(IMPLICIT_RULE).unwrap();
1387        assert_eq!(grm.rules_prods[usize::from(i_rule_idx)].len(), 3);
1388        let i_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(i_rule_idx)][0])];
1389        let i_prod2 = &grm.prods[usize::from(grm.rules_prods[usize::from(i_rule_idx)][1])];
1390        assert_eq!(i_prod1.len(), 2);
1391        assert_eq!(i_prod2.len(), 2);
1392        // We don't know what order the implicit rule will contain our tokens in,
1393        // hence the awkward dance below.
1394        let cnd1 = bslice![
1395            Symbol::Token(grm.token_idx("ws1").unwrap()),
1396            Symbol::Rule(grm.implicit_rule().unwrap()),
1397        ];
1398        let cnd2 = bslice![
1399            Symbol::Token(grm.token_idx("ws2").unwrap()),
1400            Symbol::Rule(grm.implicit_rule().unwrap()),
1401        ];
1402        assert!((*i_prod1 == cnd1 && *i_prod2 == cnd2) || (*i_prod1 == cnd2 && *i_prod2 == cnd1));
1403        let i_prod3 = &grm.prods[usize::from(grm.rules_prods[usize::from(i_rule_idx)][2])];
1404        assert_eq!(i_prod3.len(), 0);
1405    }
1406
1407    #[test]
1408    #[rustfmt::skip]
1409    fn test_has_path() {
1410        let grm = YaccGrammar::new(
1411            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1412            "
1413            %start A
1414            %%
1415            A: B;
1416            B: B 'x' | C;
1417            C: C 'y' | ;
1418          "
1419        ).unwrap();
1420
1421        let a_ridx = grm.rule_idx("A").unwrap();
1422        let b_ridx = grm.rule_idx("B").unwrap();
1423        let c_ridx = grm.rule_idx("C").unwrap();
1424        assert!(grm.has_path(a_ridx, b_ridx));
1425        assert!(grm.has_path(a_ridx, c_ridx));
1426        assert!(grm.has_path(b_ridx, b_ridx));
1427        assert!(grm.has_path(b_ridx, c_ridx));
1428        assert!(grm.has_path(c_ridx, c_ridx));
1429        assert!(!grm.has_path(a_ridx, a_ridx));
1430        assert!(!grm.has_path(b_ridx, a_ridx));
1431        assert!(!grm.has_path(c_ridx, a_ridx));
1432    }
1433
1434    #[test]
1435    #[rustfmt::skip]
1436    fn test_rule_min_costs() {
1437        let grm = YaccGrammar::new(
1438            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1439            "
1440            %start A
1441            %%
1442            A: A B | ;
1443            B: C | D | E;
1444            C: 'x' B | 'x';
1445            D: 'y' B | 'y' 'z';
1446            E: 'x' A | 'x' 'y';
1447          "
1448        ).unwrap();
1449
1450        let scores = rule_min_costs(&grm, &[1, 1, 1]);
1451        assert_eq!(scores[usize::from(grm.rule_idx("A").unwrap())], 0);
1452        assert_eq!(scores[usize::from(grm.rule_idx("B").unwrap())], 1);
1453        assert_eq!(scores[usize::from(grm.rule_idx("C").unwrap())], 1);
1454        assert_eq!(scores[usize::from(grm.rule_idx("D").unwrap())], 2);
1455        assert_eq!(scores[usize::from(grm.rule_idx("E").unwrap())], 1);
1456    }
1457
1458    #[test]
1459    fn test_min_sentences() {
1460        let grm = YaccGrammar::new(
1461            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1462            "
1463            %start A
1464            %%
1465            A: A B | ;
1466            B: C | D;
1467            C: 'x' B | 'x';
1468            D: 'y' B | 'y' 'z';
1469          ",
1470        )
1471        .unwrap();
1472
1473        let sg = grm.sentence_generator(|_| 1);
1474
1475        let find = |nt_name: &str, str_cnds: Vec<Vec<&str>>| {
1476            let cnds = str_cnds
1477                .iter()
1478                .map(|x| {
1479                    x.iter()
1480                        .map(|y| grm.token_idx(y).unwrap())
1481                        .collect::<Vec<_>>()
1482                })
1483                .collect::<Vec<_>>();
1484
1485            let ms = sg.min_sentence(grm.rule_idx(nt_name).unwrap());
1486            if !cnds.iter().any(|x| x == &ms) {
1487                panic!("{:?} doesn't have any matches in {:?}", ms, str_cnds);
1488            }
1489
1490            let min_sts = sg.min_sentences(grm.rule_idx(nt_name).unwrap());
1491            assert_eq!(cnds.len(), min_sts.len());
1492            for ms in min_sts {
1493                if !cnds.iter().any(|x| x == &ms) {
1494                    panic!("{:?} doesn't have any matches in {:?}", ms, str_cnds);
1495                }
1496            }
1497        };
1498
1499        find("A", vec![vec![]]);
1500        find("B", vec![vec!["x"]]);
1501        find("C", vec![vec!["x"]]);
1502        find("D", vec![vec!["y", "x"], vec!["y", "z"]]);
1503    }
1504
1505    #[test]
1506    #[rustfmt::skip]
1507    fn test_rule_max_costs1() {
1508        let grm = YaccGrammar::new(
1509            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1510            "
1511            %start A
1512            %%
1513            A: A B | ;
1514            B: C | D | E;
1515            C: 'x' B | 'x';
1516            D: 'y' B | 'y' 'z';
1517            E: 'x' A | 'x' 'y';
1518          "
1519        ).unwrap();
1520
1521        let scores = rule_max_costs(&grm, &[1, 1, 1]);
1522        assert_eq!(scores[usize::from(grm.rule_idx("A").unwrap())], u16::MAX);
1523        assert_eq!(scores[usize::from(grm.rule_idx("B").unwrap())], u16::MAX);
1524        assert_eq!(scores[usize::from(grm.rule_idx("C").unwrap())], u16::MAX);
1525        assert_eq!(scores[usize::from(grm.rule_idx("D").unwrap())], u16::MAX);
1526        assert_eq!(scores[usize::from(grm.rule_idx("E").unwrap())], u16::MAX);
1527    }
1528
1529    #[test]
1530    #[rustfmt::skip]
1531    fn test_rule_max_costs2() {
1532        let grm = YaccGrammar::new(
1533            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1534            "
1535            %start A
1536            %%
1537            A: A B | B;
1538            B: C | D;
1539            C: 'x' 'y' | 'x';
1540            D: 'y' 'x' | 'y' 'x' 'z';
1541          "
1542        ).unwrap();
1543
1544        let scores = rule_max_costs(&grm, &[1, 1, 1]);
1545        assert_eq!(scores[usize::from(grm.rule_idx("A").unwrap())], u16::MAX);
1546        assert_eq!(scores[usize::from(grm.rule_idx("B").unwrap())], 3);
1547        assert_eq!(scores[usize::from(grm.rule_idx("C").unwrap())], 2);
1548        assert_eq!(scores[usize::from(grm.rule_idx("D").unwrap())], 3);
1549    }
1550
1551    #[test]
1552    fn test_out_of_order_productions() {
1553        // Example taken from p54 of Locally least-cost error repair in LR parsers, Carl Cerecke
1554        let grm = YaccGrammar::new(
1555            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1556            "
1557            %start S
1558            %%
1559            S: A 'c' 'd'
1560             | B 'c' 'e';
1561            A: 'a';
1562            B: 'a'
1563             | 'b';
1564            A: 'b';
1565            ",
1566        )
1567        .unwrap();
1568
1569        assert_eq!(
1570            &*grm.prods_rules,
1571            &[
1572                RIdx(1),
1573                RIdx(1),
1574                RIdx(2),
1575                RIdx(3),
1576                RIdx(3),
1577                RIdx(2),
1578                RIdx(0)
1579            ]
1580        );
1581    }
1582
1583    #[test]
1584    fn test_token_spans() {
1585        let src = "%%\nAB: 'a' | 'foo';";
1586        let grm =
1587            YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
1588        let token_map = grm.tokens_map();
1589        let a_tidx = token_map.get("a");
1590        let foo_tidx = token_map.get("foo");
1591        let a_span = grm.token_span(*a_tidx.unwrap()).unwrap();
1592        let foo_span = grm.token_span(*foo_tidx.unwrap()).unwrap();
1593        let ab_span = grm.rule_name_span(grm.rule_idx("AB").unwrap());
1594        assert_eq!(a_span, Span::new(8, 9));
1595        assert_eq!(foo_span, Span::new(14, 17));
1596        assert_eq!(ab_span, Span::new(3, 5));
1597        assert_eq!(&src[a_span.start()..a_span.end()], "a");
1598        assert_eq!(&src[foo_span.start()..foo_span.end()], "foo");
1599        assert_eq!(&src[ab_span.start()..ab_span.end()], "AB");
1600    }
1601
1602    #[test]
1603    fn token_span_issue296() {
1604        let src = "%%
1605                   S: | AB;
1606                   A: 'a' 'b';
1607                   B: 'b' 'c';
1608                   AB: A AB | B ';' AB;
1609                   %%
1610                   ";
1611        let grm =
1612            YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
1613        let token_map = grm.tokens_map();
1614        let c_tidx = token_map.get("c").unwrap();
1615        assert_eq!(grm.token_name(*c_tidx), Some("c"));
1616        let c_span = grm.token_span(*c_tidx).unwrap();
1617        assert_eq!(&src[c_span.start()..c_span.end()], "c");
1618    }
1619
1620    #[test]
1621    fn test_grmtools_section_yacckinds() {
1622        let srcs = [
1623            "%grmtools{yacckind: Original(NoAction)}
1624                 %%
1625                 Start: ;",
1626            "%grmtools{yacckind: YaccKind::Original(GenericParseTree)}
1627                 %%
1628                 Start: ;",
1629            "%grmtools{yacckind: YaccKind::Original(yaccoriginalactionkind::useraction)}
1630                 %actiontype ()
1631                 %%
1632                 Start: ;",
1633            "%grmtools{yacckind: Original(YACCOriginalActionKind::NoAction)}
1634                 %%
1635                 Start: ;",
1636            "%grmtools{yacckind: YaccKind::Grmtools}
1637                 %%
1638                 Start -> () : ;",
1639        ];
1640        for src in srcs {
1641            YaccGrammar::<u32>::from_str(src).unwrap();
1642        }
1643    }
1644
1645    #[test]
1646    fn test_grmtools_section_invalid_yacckinds() {
1647        let srcs = [
1648            "%grmtools{yacckind: Foo}",
1649            "%grmtools{yacckind: YaccKind::Foo}",
1650            "%grmtools{yacckindof: YaccKind::Grmtools}",
1651            "%grmtools{yacckindof: Grmtools}",
1652            "%grmtools{yacckindof: YaccKindFoo::Foo}",
1653            "%grmtools{yacckind: Foo::Grmtools}",
1654            "%grmtools{yacckind: YaccKind::Original}",
1655            "%grmtools{yacckind: YaccKind::OriginalFoo}",
1656            "%grmtools{yacckind: YaccKind::Original()}",
1657            "%grmtools{yacckind: YaccKind::Original(Foo)}",
1658            "%grmtools{yacckind: YaccKind::Original(YaccOriginalActionKind)}",
1659            "%grmtools{yacckind: YaccKind::Original(YaccOriginalActionKind::Foo)}",
1660            "%grmtools{yacckind: YaccKind::Original(Foo::NoActions)}",
1661            "%grmtools{yacckind: YaccKind::Original(Foo::NoActionsBar)}",
1662        ];
1663
1664        for src in srcs {
1665            let s = format!("{}\n%%\nStart();\n", src);
1666            assert!(YaccGrammar::<u32>::from_str(&s).is_err());
1667        }
1668    }
1669
1670    #[test]
1671    fn test_grmtools_section_commas() {
1672        // We can't actually test much here, because
1673        // We don't have a second value to test.
1674        //
1675        // `RecoveryKind` seemed like an option for an additional value to allow,
1676        // but that is part of `lrpar` which cfgrammar doesn't depend upon.
1677        let src = r#"
1678                %grmtools{
1679                    yacckind: YaccKind::Grmtools,
1680                }
1681                %%
1682                Start -> () : ;
1683            "#;
1684        YaccGrammar::<u32>::from_str(src).unwrap();
1685        let src = r#"
1686                %grmtools{
1687                    yacckind: YaccKind::Grmtools
1688                }
1689                %%
1690                Start -> () : ;
1691            "#;
1692        YaccGrammar::<u32>::from_str(src).unwrap();
1693    }
1694}