cfgrammar/yacc/
parser.rs

1// Note: this is the parser for both YaccKind::Original(YaccOriginalActionKind::GenericParseTree) and YaccKind::Eco yacc kinds.
2
3use num_traits::PrimInt;
4use regex::Regex;
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Serialize};
7use std::{
8    collections::{HashMap, hash_map::Entry},
9    error::Error,
10    fmt,
11    str::FromStr,
12    sync::LazyLock,
13};
14#[cfg(feature = "wincode")]
15use wincode::{SchemaRead, SchemaWrite};
16
17use crate::{
18    Span, Spanned,
19    header::{GrmtoolsSectionParser, HeaderErrorKind},
20};
21
22pub type YaccGrammarResult<T> = Result<T, Vec<YaccGrammarError>>;
23
24use super::{
25    AssocKind, Precedence, YaccKind,
26    ast::{GrammarAST, Symbol},
27};
28
29/// The various different possible Yacc parser errors.
30#[derive(Debug, PartialEq, Eq, Clone)]
31#[non_exhaustive]
32pub enum YaccGrammarErrorKind {
33    IllegalInteger,
34    IllegalName,
35    IllegalString,
36    IncompleteRule,
37    IncompleteComment,
38    IncompleteAction,
39    MissingActionCode,
40    MissingActionType,
41    MissingColon,
42    MissingRightArrow,
43    MismatchedBrace,
44    NonEmptyProduction,
45    PrematureEnd,
46    ProductionNotTerminated,
47    ProgramsNotSupported,
48    UnknownDeclaration,
49    PrecNotFollowedByToken,
50    DuplicatePrecedence,
51    DuplicateAvoidInsertDeclaration,
52    DuplicateImplicitTokensDeclaration,
53    DuplicateExpectDeclaration,
54    DuplicateExpectRRDeclaration,
55    DuplicateStartDeclaration,
56    DuplicateActiontypeDeclaration,
57    DuplicateEPP,
58    ReachedEOL,
59    InvalidString,
60    NoStartRule,
61    UnknownSymbol,
62    UnrecognisedActionVariable,
63    InvalidStartRule(String),
64    UnknownRuleRef(String),
65    UnknownToken(String),
66    NoPrecForToken(String),
67    UnknownEPP(String),
68    ExpectedInput(char),
69    InvalidYaccKind,
70    Header(HeaderErrorKind, SpansKind),
71}
72
73/// Any error from the Yacc parser returns an instance of this struct.
74#[derive(Debug, PartialEq, Eq, Clone)]
75pub struct YaccGrammarError {
76    /// Uniquely identifies each error.
77    pub(crate) kind: YaccGrammarErrorKind,
78    /// Always contains at least 1 span.
79    ///
80    /// Refer to [SpansKind] via [spanskind](Self::spanskind)
81    /// For meaning and interpretation of spans and their ordering.
82    pub(crate) spans: Vec<Span>,
83}
84
85impl Error for YaccGrammarError {}
86
87impl fmt::Display for YaccGrammarError {
88    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
89        write!(f, "{}", self.kind)
90    }
91}
92
93impl fmt::Display for YaccGrammarErrorKind {
94    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
95        let s = match self {
96            YaccGrammarErrorKind::ExpectedInput(c) => &format!("Expected input '{c}'"),
97            YaccGrammarErrorKind::IllegalInteger => "Illegal integer",
98            YaccGrammarErrorKind::IllegalName => "Illegal name",
99            YaccGrammarErrorKind::IllegalString => "Illegal string",
100            YaccGrammarErrorKind::IncompleteRule => "Incomplete rule",
101            YaccGrammarErrorKind::IncompleteComment => "Incomplete comment",
102            YaccGrammarErrorKind::IncompleteAction => "Incomplete action",
103            YaccGrammarErrorKind::MissingActionCode => "Production is missing action code",
104            YaccGrammarErrorKind::MissingActionType => "Missing action type",
105            YaccGrammarErrorKind::MissingColon => "Missing ':'",
106            YaccGrammarErrorKind::MissingRightArrow => "Missing '->'",
107            YaccGrammarErrorKind::MismatchedBrace => "Mismatched brace",
108            YaccGrammarErrorKind::NonEmptyProduction => "%empty used in non-empty production",
109            YaccGrammarErrorKind::PrematureEnd => "File ends prematurely",
110            YaccGrammarErrorKind::ProductionNotTerminated => "Production not terminated correctly",
111            YaccGrammarErrorKind::ProgramsNotSupported => "Programs not currently supported",
112            YaccGrammarErrorKind::UnknownDeclaration => "Unknown declaration",
113            YaccGrammarErrorKind::DuplicatePrecedence => "Token has multiple precedences specified",
114            YaccGrammarErrorKind::PrecNotFollowedByToken => "%prec not followed by token name",
115            YaccGrammarErrorKind::UnrecognisedActionVariable => {
116                "Unrecognised action variable following '$'"
117            }
118            YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration => {
119                "Duplicated %avoid_insert declaration"
120            }
121            YaccGrammarErrorKind::DuplicateExpectDeclaration => "Duplicated %expect declaration",
122            YaccGrammarErrorKind::DuplicateExpectRRDeclaration => {
123                "Duplicate %expect-rr declaration"
124            }
125            YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration => {
126                "Duplicated %implicit_tokens declaration"
127            }
128            YaccGrammarErrorKind::DuplicateStartDeclaration => "Duplicated %start declaration",
129            YaccGrammarErrorKind::DuplicateActiontypeDeclaration => {
130                "Duplicate %actiontype declaration"
131            }
132            YaccGrammarErrorKind::DuplicateEPP => "Duplicate %epp declaration for this token",
133            YaccGrammarErrorKind::ReachedEOL => {
134                "Reached end of line without finding expected content"
135            }
136            YaccGrammarErrorKind::InvalidString => "Invalid string",
137            YaccGrammarErrorKind::NoStartRule => return write!(f, "No start rule specified"),
138            YaccGrammarErrorKind::UnknownSymbol => "Unknown symbol, expected a rule or token",
139            YaccGrammarErrorKind::InvalidStartRule(name) => {
140                return write!(f, "Start rule '{}' does not appear in grammar", name);
141            }
142            YaccGrammarErrorKind::UnknownRuleRef(name) => {
143                return write!(f, "Unknown reference to rule '{}'", name);
144            }
145            YaccGrammarErrorKind::UnknownToken(name) => {
146                return write!(f, "Unknown token '{}'", name);
147            }
148            YaccGrammarErrorKind::NoPrecForToken(name) => {
149                return write!(
150                    f,
151                    "Token '{}' used in %prec has no precedence attached",
152                    name
153                );
154            }
155            YaccGrammarErrorKind::UnknownEPP(name) => {
156                return write!(
157                    f,
158                    "Token '{}' in %epp declaration is not referenced in the grammar",
159                    name
160                );
161            }
162            YaccGrammarErrorKind::InvalidYaccKind => "Invalid yacc kind",
163            YaccGrammarErrorKind::Header(hk, _) => &format!("Error in '%grmtools' {}", hk),
164        };
165        write!(f, "{}", s)
166    }
167}
168
169/// The various different possible Yacc parser errors.
170#[derive(Debug, PartialEq, Eq, Clone)]
171#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
172#[cfg_attr(feature = "wincode", derive(SchemaRead, SchemaWrite))]
173#[non_exhaustive]
174pub enum YaccGrammarWarningKind {
175    UnusedRule,
176    UnusedToken,
177}
178
179/// Any Warning from the Yacc parser returns an instance of this struct.
180#[derive(Debug, PartialEq, Eq, Clone)]
181#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
182#[cfg_attr(feature = "wincode", derive(SchemaRead, SchemaWrite))]
183pub struct YaccGrammarWarning {
184    /// The specific kind of warning.
185    pub(crate) kind: YaccGrammarWarningKind,
186    /// Always contains at least 1 span.
187    ///
188    /// Refer to [SpansKind] via [spanskind](Self::spanskind)
189    /// For meaning and interpretation of spans and their ordering.
190    pub(crate) spans: Vec<Span>,
191}
192
193impl fmt::Display for YaccGrammarWarning {
194    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
195        write!(f, "{}", self.kind)
196    }
197}
198
199impl fmt::Display for YaccGrammarWarningKind {
200    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
201        let s = match self {
202            YaccGrammarWarningKind::UnusedRule => "Unused rule",
203            YaccGrammarWarningKind::UnusedToken => "Unused token",
204        };
205        write!(f, "{}", s)
206    }
207}
208
209impl Spanned for YaccGrammarWarning {
210    /// Returns the spans associated with the error, always containing at least 1 span.
211    ///
212    /// Refer to [SpansKind] via [spanskind](Self::spanskind)
213    /// for the meaning and interpretation of spans and their ordering.
214    fn spans(&self) -> &[Span] {
215        self.spans.as_slice()
216    }
217
218    /// Returns the [SpansKind] associated with this error.
219    fn spanskind(&self) -> SpansKind {
220        match self.kind {
221            YaccGrammarWarningKind::UnusedRule | YaccGrammarWarningKind::UnusedToken => {
222                SpansKind::Error
223            }
224        }
225    }
226}
227
228/// Indicates how to interpret the spans of an error.
229#[derive(Debug, PartialEq, Eq, Copy, Clone)]
230#[non_exhaustive]
231pub enum SpansKind {
232    /// The first span is the first occurrence, and a span for each subsequent occurrence.
233    DuplicationError,
234    /// Contains a single span at the site of the error.
235    Error,
236}
237
238impl Spanned for YaccGrammarError {
239    /// Returns the spans associated with the error, always containing at least 1 span.
240    ///
241    /// Refer to [SpansKind] via [spanskind](Self::spanskind)
242    /// for the meaning and interpretation of spans and their ordering.
243    fn spans(&self) -> &[Span] {
244        self.spans.as_slice()
245    }
246
247    /// Returns the [SpansKind] associated with this error.
248    fn spanskind(&self) -> SpansKind {
249        match self.kind {
250            YaccGrammarErrorKind::IllegalInteger
251            | YaccGrammarErrorKind::IllegalName
252            | YaccGrammarErrorKind::IllegalString
253            | YaccGrammarErrorKind::IncompleteRule
254            | YaccGrammarErrorKind::IncompleteComment
255            | YaccGrammarErrorKind::IncompleteAction
256            | YaccGrammarErrorKind::MissingActionCode
257            | YaccGrammarErrorKind::MissingActionType
258            | YaccGrammarErrorKind::MissingColon
259            | YaccGrammarErrorKind::MissingRightArrow
260            | YaccGrammarErrorKind::MismatchedBrace
261            | YaccGrammarErrorKind::NonEmptyProduction
262            | YaccGrammarErrorKind::PrematureEnd
263            | YaccGrammarErrorKind::ProductionNotTerminated
264            | YaccGrammarErrorKind::PrecNotFollowedByToken
265            | YaccGrammarErrorKind::ProgramsNotSupported
266            | YaccGrammarErrorKind::UnknownDeclaration
267            | YaccGrammarErrorKind::ReachedEOL
268            | YaccGrammarErrorKind::InvalidString
269            | YaccGrammarErrorKind::NoStartRule
270            | YaccGrammarErrorKind::UnknownSymbol
271            | YaccGrammarErrorKind::UnrecognisedActionVariable
272            | YaccGrammarErrorKind::InvalidStartRule(_)
273            | YaccGrammarErrorKind::UnknownRuleRef(_)
274            | YaccGrammarErrorKind::UnknownToken(_)
275            | YaccGrammarErrorKind::NoPrecForToken(_)
276            | YaccGrammarErrorKind::InvalidYaccKind
277            | YaccGrammarErrorKind::ExpectedInput(_)
278            | YaccGrammarErrorKind::UnknownEPP(_) => SpansKind::Error,
279            YaccGrammarErrorKind::DuplicatePrecedence
280            | YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration
281            | YaccGrammarErrorKind::DuplicateExpectDeclaration
282            | YaccGrammarErrorKind::DuplicateExpectRRDeclaration
283            | YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration
284            | YaccGrammarErrorKind::DuplicateStartDeclaration
285            | YaccGrammarErrorKind::DuplicateActiontypeDeclaration
286            | YaccGrammarErrorKind::DuplicateEPP => SpansKind::DuplicationError,
287            YaccGrammarErrorKind::Header(_, spanskind) => spanskind,
288        }
289    }
290}
291
292pub(crate) struct YaccParser<'a> {
293    yacc_kind: YaccKind,
294    src: &'a str,
295    num_newlines: usize,
296    ast: GrammarAST,
297    global_actiontype: Option<(String, Span)>,
298}
299
300pub(crate) static RE_NAME: LazyLock<Regex> =
301    LazyLock::new(|| Regex::new(r"^[a-zA-Z_.][a-zA-Z0-9_.]*").unwrap());
302static RE_TOKEN: LazyLock<Regex> =
303    LazyLock::new(|| Regex::new("^(?:(\".+?\")|('.+?')|([a-zA-Z_][a-zA-Z_0-9]*))").unwrap());
304
305fn add_duplicate_occurrence(
306    errs: &mut Vec<YaccGrammarError>,
307    kind: YaccGrammarErrorKind,
308    orig_span: Span,
309    dup_span: Span,
310) {
311    if !errs.iter_mut().any(|e| {
312        if e.kind == kind && e.spans[0] == orig_span {
313            e.spans.push(dup_span);
314            true
315        } else {
316            false
317        }
318    }) {
319        errs.push(YaccGrammarError {
320            kind,
321            spans: vec![orig_span, dup_span],
322        });
323    }
324}
325
326/// The actual parser is intended to be entirely opaque from outside users.
327impl YaccParser<'_> {
328    pub(crate) fn new(yacc_kind: YaccKind, src: &str) -> YaccParser<'_> {
329        YaccParser {
330            yacc_kind,
331            src,
332            num_newlines: 0,
333            ast: GrammarAST::new(),
334            global_actiontype: None,
335        }
336    }
337
338    pub(crate) fn parse(&mut self) -> YaccGrammarResult<usize> {
339        let mut errs = Vec::new();
340        let (_, pos) = GrmtoolsSectionParser::new(self.src, false)
341            .parse()
342            .map_err(|mut errs| errs.drain(..).map(|e| e.into()).collect::<Vec<_>>())?;
343        // We pass around an index into the *bytes* of self.src. We guarantee that at all times
344        // this points to the beginning of a UTF-8 character (since multibyte characters exist, not
345        // every byte within the string is also a valid character).
346        let mut result = self.parse_declarations(pos, &mut errs);
347        result = self.parse_rules(match result {
348            Ok(i) => i,
349            Err(e) => {
350                errs.push(e);
351                return Err(errs);
352            }
353        });
354        result = self.parse_programs(
355            match result {
356                Ok(i) => i,
357                Err(e) => {
358                    errs.push(e);
359                    return Err(errs);
360                }
361            },
362            &mut errs,
363        );
364        match result {
365            Ok(i) if errs.is_empty() => Ok(i),
366            Err(e) => {
367                errs.push(e);
368                Err(errs)
369            }
370            _ => Err(errs),
371        }
372    }
373
374    pub(crate) fn build(self) -> GrammarAST {
375        self.ast
376    }
377
378    fn parse_declarations(
379        &mut self,
380        mut i: usize,
381        errs: &mut Vec<YaccGrammarError>,
382    ) -> Result<usize, YaccGrammarError> {
383        i = self.parse_ws(i, true)?;
384        let mut prec_level = 0;
385        while i < self.src.len() {
386            if self.lookahead_is("%%", i).is_some() {
387                return Ok(i);
388            }
389            if let Some(j) = self.lookahead_is("%token", i) {
390                i = self.parse_ws(j, false)?;
391                while i < self.src.len() && self.lookahead_is("%", i).is_none() {
392                    let (j, n, span, _) = self.parse_token(i)?;
393                    let (idx, new_tok) = self.ast.tokens.insert_full(n);
394                    if new_tok {
395                        self.ast.spans.push(span);
396                    }
397                    self.ast.token_directives.insert(idx);
398                    i = self.parse_ws(j, true)?;
399                }
400                continue;
401            }
402            if let YaccKind::Original(_) = self.yacc_kind
403                && let Some(j) = self.lookahead_is("%actiontype", i)
404            {
405                i = self.parse_ws(j, false)?;
406                let (j, n) = self.parse_to_eol(i)?;
407                let span = Span::new(i, j);
408                if let Some((_, orig_span)) = self.global_actiontype {
409                    add_duplicate_occurrence(
410                        errs,
411                        YaccGrammarErrorKind::DuplicateActiontypeDeclaration,
412                        orig_span,
413                        span,
414                    );
415                } else {
416                    self.global_actiontype = Some((n, span));
417                }
418                i = self.parse_ws(j, true)?;
419                continue;
420            }
421            if let Some(j) = self.lookahead_is("%start", i) {
422                i = self.parse_ws(j, false)?;
423                let (j, n) = self.parse_name(i)?;
424                let span = Span::new(i, j);
425                if let Some((_, orig_span)) = self.ast.start {
426                    add_duplicate_occurrence(
427                        errs,
428                        YaccGrammarErrorKind::DuplicateStartDeclaration,
429                        orig_span,
430                        span,
431                    );
432                } else {
433                    self.ast.start = Some((n, span));
434                }
435                i = self.parse_ws(j, true)?;
436                continue;
437            }
438            if let Some(j) = self.lookahead_is("%epp", i) {
439                i = self.parse_ws(j, false)?;
440                let (j, n, _, _) = self.parse_token(i)?;
441                let span = Span::new(i, j);
442                i = self.parse_ws(j, false)?;
443                let (j, v) = self.parse_string(i)?;
444                let vspan = Span::new(i, j);
445                match self.ast.epp.entry(n) {
446                    Entry::Occupied(orig) => {
447                        let (orig_span, _) = orig.get();
448                        add_duplicate_occurrence(
449                            errs,
450                            YaccGrammarErrorKind::DuplicateEPP,
451                            *orig_span,
452                            span,
453                        )
454                    }
455                    Entry::Vacant(epp) => {
456                        epp.insert((span, (v, vspan)));
457                    }
458                }
459                i = self.parse_ws(j, true)?;
460                continue;
461            }
462            if let Some(j) = self.lookahead_is("%expect-rr", i) {
463                i = self.parse_ws(j, false)?;
464                let (j, n) = self.parse_int(i)?;
465                let span = Span::new(i, j);
466                if let Some((_, orig_span)) = self.ast.expectrr {
467                    add_duplicate_occurrence(
468                        errs,
469                        YaccGrammarErrorKind::DuplicateExpectRRDeclaration,
470                        orig_span,
471                        span,
472                    );
473                } else {
474                    self.ast.expectrr = Some((n, span));
475                }
476                i = self.parse_ws(j, true)?;
477                continue;
478            }
479            if let Some(j) = self.lookahead_is("%expect-unused", i) {
480                i = self.parse_ws(j, false)?;
481                while i < self.src.len() && self.lookahead_is("%", i).is_none() {
482                    let j = match self.parse_name(i) {
483                        Ok((j, n)) => {
484                            self.ast
485                                .expect_unused
486                                .push(Symbol::Rule(n, Span::new(i, j)));
487                            j
488                        }
489                        Err(_) => match self.parse_token(i) {
490                            Ok((j, n, span, _)) => {
491                                self.ast.expect_unused.push(Symbol::Token(n, span));
492                                j
493                            }
494                            Err(_) => {
495                                return Err(self.mk_error(YaccGrammarErrorKind::UnknownSymbol, i));
496                            }
497                        },
498                    };
499                    i = self.parse_ws(j, true)?;
500                }
501                continue;
502            }
503            if let Some(j) = self.lookahead_is("%expect", i) {
504                i = self.parse_ws(j, false)?;
505                let (j, n) = self.parse_int(i)?;
506                let span = Span::new(i, j);
507                if let Some((_, orig_span)) = self.ast.expect {
508                    add_duplicate_occurrence(
509                        errs,
510                        YaccGrammarErrorKind::DuplicateExpectDeclaration,
511                        orig_span,
512                        span,
513                    );
514                } else {
515                    self.ast.expect = Some((n, span));
516                }
517                i = self.parse_ws(j, true)?;
518                continue;
519            }
520            if let Some(j) = self.lookahead_is("%avoid_insert", i) {
521                i = self.parse_ws(j, false)?;
522                let num_newlines = self.num_newlines;
523                if self.ast.avoid_insert.is_none() {
524                    self.ast.avoid_insert = Some(HashMap::new());
525                }
526                while j < self.src.len() && self.num_newlines == num_newlines {
527                    let (j, n, span, _) = self.parse_token(i)?;
528                    if self.ast.tokens.insert(n.clone()) {
529                        self.ast.spans.push(span);
530                    }
531
532                    match self.ast.avoid_insert.as_mut().unwrap().entry(n) {
533                        Entry::Occupied(occupied) => {
534                            add_duplicate_occurrence(
535                                errs,
536                                YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration,
537                                *occupied.get(),
538                                span,
539                            );
540                        }
541                        Entry::Vacant(vacant) => {
542                            vacant.insert(span);
543                        }
544                    }
545                    i = self.parse_ws(j, true)?;
546                }
547                continue;
548            }
549            if let Some(j) = self.lookahead_is("%parse-param", i) {
550                i = self.parse_ws(j, false)?;
551                let (j, name) = self.parse_to_single_colon(i)?;
552                match self.lookahead_is(":", j) {
553                    Some(j) => i = self.parse_ws(j, false)?,
554                    None => {
555                        return Err(self.mk_error(YaccGrammarErrorKind::MissingColon, j));
556                    }
557                }
558                let (j, ty) = self.parse_to_eol(i)?;
559                self.ast.parse_param = Some((name, ty));
560                i = self.parse_ws(j, true)?;
561                continue;
562            }
563            if let Some(j) = self.lookahead_is("%parse-generics", i) {
564                i = self.parse_ws(j, false)?;
565                let (j, ty) = self.parse_to_eol(i)?;
566                self.ast.parse_generics = Some(ty);
567                i = self.parse_ws(j, true)?;
568                continue;
569            }
570            if let YaccKind::Eco = self.yacc_kind
571                && let Some(j) = self.lookahead_is("%implicit_tokens", i)
572            {
573                i = self.parse_ws(j, false)?;
574                let num_newlines = self.num_newlines;
575                if self.ast.implicit_tokens.is_none() {
576                    self.ast.implicit_tokens = Some(HashMap::new());
577                }
578                while j < self.src.len() && self.num_newlines == num_newlines {
579                    let (j, n, span, _) = self.parse_token(i)?;
580                    if self.ast.tokens.insert(n.clone()) {
581                        self.ast.spans.push(span);
582                    }
583                    match self.ast.implicit_tokens.as_mut().unwrap().entry(n) {
584                        Entry::Occupied(entry) => {
585                            let orig_span = *entry.get();
586                            add_duplicate_occurrence(
587                                errs,
588                                YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration,
589                                orig_span,
590                                span,
591                            );
592                        }
593                        Entry::Vacant(entry) => {
594                            entry.insert(span);
595                        }
596                    }
597                    i = self.parse_ws(j, true)?;
598                }
599                continue;
600            }
601            {
602                let k;
603                let kind;
604                if let Some(j) = self.lookahead_is("%left", i) {
605                    kind = AssocKind::Left;
606                    k = j;
607                } else if let Some(j) = self.lookahead_is("%right", i) {
608                    kind = AssocKind::Right;
609                    k = j;
610                } else if let Some(j) = self.lookahead_is("%nonassoc", i) {
611                    kind = AssocKind::Nonassoc;
612                    k = j;
613                } else {
614                    return Err(self.mk_error(YaccGrammarErrorKind::UnknownDeclaration, i));
615                }
616
617                i = self.parse_ws(k, false)?;
618                let num_newlines = self.num_newlines;
619                while i < self.src.len() && num_newlines == self.num_newlines {
620                    let (j, n, span, _) = self.parse_token(i)?;
621                    match self.ast.precs.entry(n) {
622                        Entry::Occupied(orig) => {
623                            let (_, orig_span) = orig.get();
624                            add_duplicate_occurrence(
625                                errs,
626                                YaccGrammarErrorKind::DuplicatePrecedence,
627                                *orig_span,
628                                span,
629                            );
630                        }
631                        Entry::Vacant(entry) => {
632                            let prec = Precedence {
633                                level: prec_level,
634                                kind,
635                            };
636                            entry.insert((prec, span));
637                        }
638                    }
639
640                    i = self.parse_ws(j, true)?;
641                }
642                prec_level += 1;
643            }
644        }
645        debug_assert!(i == self.src.len());
646        Err(self.mk_error(YaccGrammarErrorKind::PrematureEnd, i))
647    }
648
649    fn parse_rules(&mut self, mut i: usize) -> Result<usize, YaccGrammarError> {
650        // self.parse_declarations should have left the input at '%%'
651        i = self.lookahead_is("%%", i).unwrap();
652        i = self.parse_ws(i, true)?;
653        while i < self.src.len() && self.lookahead_is("%%", i).is_none() {
654            i = self.parse_rule(i)?;
655            i = self.parse_ws(i, true)?;
656        }
657        Ok(i)
658    }
659
660    fn parse_rule(&mut self, mut i: usize) -> Result<usize, YaccGrammarError> {
661        let (j, rn) = self.parse_name(i)?;
662        let span = Span::new(i, j);
663        if self.ast.start.is_none() {
664            self.ast.start = Some((rn.clone(), span));
665        }
666        match self.yacc_kind {
667            YaccKind::Original(_) | YaccKind::Eco => {
668                if self.ast.get_rule(&rn).is_none() {
669                    self.ast.add_rule(
670                        (rn.clone(), span),
671                        self.global_actiontype.clone().map(|(s, _)| s),
672                    );
673                }
674                i = j;
675            }
676            YaccKind::Grmtools => {
677                i = self.parse_ws(j, true)?;
678                if let Some(j) = self.lookahead_is("->", i) {
679                    i = j;
680                } else {
681                    return Err(self.mk_error(YaccGrammarErrorKind::MissingRightArrow, i));
682                }
683                i = self.parse_ws(i, true)?;
684                let (j, actiont) = self.parse_to_single_colon(i)?;
685                if self.ast.get_rule(&rn).is_none() {
686                    self.ast.add_rule((rn.clone(), span), Some(actiont));
687                }
688                i = j;
689            }
690        }
691        i = self.parse_ws(i, true)?;
692        match self.lookahead_is(":", i) {
693            Some(j) => i = j,
694            None => {
695                return Err(self.mk_error(YaccGrammarErrorKind::MissingColon, i));
696            }
697        }
698        let mut syms = Vec::new();
699        let mut prec = None;
700        let mut action = None;
701        i = self.parse_ws(i, true)?;
702        let mut pos_prod_start = i;
703        let mut pos_prod_end = None;
704        while i < self.src.len() {
705            if let Some(j) = self.lookahead_is("|", i) {
706                self.ast.add_prod(
707                    rn.clone(),
708                    syms,
709                    prec,
710                    action,
711                    Span::new(pos_prod_start, pos_prod_end.take().unwrap_or(i)),
712                );
713                syms = Vec::new();
714                prec = None;
715                action = None;
716                i = self.parse_ws(j, true)?;
717                pos_prod_start = i;
718                continue;
719            } else if let Some(j) = self.lookahead_is(";", i) {
720                self.ast.add_prod(
721                    rn,
722                    syms,
723                    prec,
724                    action,
725                    Span::new(pos_prod_start, pos_prod_end.take().unwrap_or(i)),
726                );
727                return Ok(j);
728            }
729
730            if self.lookahead_is("\"", i).is_some() || self.lookahead_is("'", i).is_some() {
731                let (j, sym, span, _) = self.parse_token(i)?;
732                pos_prod_end = Some(j);
733                i = self.parse_ws(j, true)?;
734                if self.ast.tokens.insert(sym.clone()) {
735                    self.ast.spans.push(span);
736                }
737                syms.push(Symbol::Token(sym, span));
738            } else if let Some(j) = self.lookahead_is("%prec", i) {
739                i = self.parse_ws(j, true)?;
740                let (k, sym, span, _) = self.parse_token(i)?;
741                if self.ast.tokens.insert(sym.clone()) {
742                    self.ast.spans.push(span);
743                }
744                prec = Some(sym);
745                pos_prod_end = Some(k);
746                i = k;
747            } else if self.lookahead_is("{", i).is_some() {
748                let pos_action_start = i + 1;
749                pos_prod_end = Some(i);
750                // With j the location of the right brace, i the location of the left brace.
751                let (j, a) = self.parse_action(i)?;
752                i = self.parse_ws(j, true)?;
753                let action_span = Span::new(pos_action_start, pos_action_start + a.len());
754                action = Some((a, action_span));
755
756                if !(self.lookahead_is("|", i).is_some() || self.lookahead_is(";", i).is_some()) {
757                    return Err(self.mk_error(YaccGrammarErrorKind::ProductionNotTerminated, i));
758                }
759            } else if let Some(j) = self.lookahead_is("%empty", i) {
760                let k = self.parse_ws(j, true)?;
761                // %empty could be followed by all sorts of weird syntax errors: all we try and do
762                // is say "does this production look like it's finished" and trust that the other
763                // errors will be caught by other parts of the parser.
764                if !syms.is_empty()
765                    | !(self.lookahead_is("|", k).is_some()
766                        || self.lookahead_is(";", k).is_some()
767                        || self.lookahead_is("{", k).is_some()
768                        || self.lookahead_is("%prec", k).is_some())
769                {
770                    return Err(self.mk_error(YaccGrammarErrorKind::NonEmptyProduction, i));
771                }
772                pos_prod_end = Some(j);
773                i = k;
774            } else {
775                let (j, sym, span, quoted) = self.parse_token(i)?;
776                pos_prod_end = Some(j);
777                if self
778                    .ast
779                    .tokens
780                    .get_index_of(&sym)
781                    .is_some_and(|idx| quoted || self.ast.token_directives.contains(&idx))
782                {
783                    syms.push(Symbol::Token(sym, span));
784                } else {
785                    syms.push(Symbol::Rule(sym, span));
786                }
787                i = j;
788            }
789            i = self.parse_ws(i, true)?;
790        }
791        Err(self.mk_error(YaccGrammarErrorKind::IncompleteRule, i))
792    }
793
794    fn parse_name(&self, i: usize) -> Result<(usize, String), YaccGrammarError> {
795        match RE_NAME.find(&self.src[i..]) {
796            Some(m) => {
797                assert_eq!(m.start(), 0);
798                Ok((i + m.end(), self.src[i..i + m.end()].to_string()))
799            }
800            None => Err(self.mk_error(YaccGrammarErrorKind::IllegalName, i)),
801        }
802    }
803
804    fn parse_token(&self, i: usize) -> Result<(usize, String, Span, bool), YaccGrammarError> {
805        match RE_TOKEN.find(&self.src[i..]) {
806            Some(m) => {
807                assert!(m.start() == 0 && m.end() > 0);
808                match self.src[i..].chars().next().unwrap() {
809                    '"' | '\'' => {
810                        debug_assert!('"'.len_utf8() == 1 && '\''.len_utf8() == 1);
811                        let start_cidx = i + 1;
812                        let end_cidx = i + m.end() - 1;
813                        Ok((
814                            i + m.end(),
815                            self.src[start_cidx..end_cidx].to_string(),
816                            Span::new(start_cidx, end_cidx),
817                            true,
818                        ))
819                    }
820                    _ => Ok((
821                        i + m.end(),
822                        self.src[i..i + m.end()].to_string(),
823                        Span::new(i, i + m.end()),
824                        false,
825                    )),
826                }
827            }
828            None => Err(self.mk_error(YaccGrammarErrorKind::IllegalString, i)),
829        }
830    }
831
832    fn parse_action(&mut self, i: usize) -> Result<(usize, String), YaccGrammarError> {
833        debug_assert!(self.lookahead_is("{", i).is_some());
834        let mut j = i;
835        let mut c = 0; // Count braces
836        while j < self.src.len() {
837            let ch = self.src[j..].chars().next().unwrap();
838            match ch {
839                '{' => c += 1,
840                '}' if c == 1 => {
841                    c = 0;
842                    break;
843                }
844                '}' => c -= 1,
845                '\n' | '\r' => {
846                    self.num_newlines += 1;
847                }
848                _ => (),
849            };
850            j += ch.len_utf8();
851        }
852        if c > 0 {
853            Err(self.mk_error(YaccGrammarErrorKind::IncompleteAction, i))
854        } else {
855            debug_assert!(self.lookahead_is("}", j).is_some());
856            let s = self.src[i + '{'.len_utf8()..j].to_string();
857            Ok((j + '}'.len_utf8(), s))
858        }
859    }
860
861    fn parse_programs(
862        &mut self,
863        mut i: usize,
864        _: &mut Vec<YaccGrammarError>,
865    ) -> Result<usize, YaccGrammarError> {
866        if let Some(j) = self.lookahead_is("%%", i) {
867            i = self.parse_ws(j, true)?;
868            let prog = self.src[i..].to_string();
869            i += prog.len();
870            self.ast.set_programs(prog);
871        }
872        Ok(i)
873    }
874
875    /// Parse up to (but do not include) the end of line (or, if it comes sooner, the end of file).
876    fn parse_to_eol(&mut self, i: usize) -> Result<(usize, String), YaccGrammarError> {
877        let mut j = i;
878        while j < self.src.len() {
879            let c = self.src[j..].chars().next().unwrap();
880            match c {
881                '\n' | '\r' => break,
882                _ => j += c.len_utf8(),
883            }
884        }
885        Ok((j, self.src[i..j].to_string()))
886    }
887
888    /// Parse up to (but do not include) a single colon (double colons are allowed so that strings
889    /// like `a::b::c:` treat `a::b::c` as a single name. Errors if EOL encountered.
890    fn parse_to_single_colon(&mut self, i: usize) -> Result<(usize, String), YaccGrammarError> {
891        let mut j = i;
892        while j < self.src.len() {
893            let c = self.src[j..].chars().next().unwrap();
894            match c {
895                ':' => {
896                    let k = j + ':'.len_utf8();
897                    if k == self.src.len() || !self.src[k..].starts_with(':') {
898                        return Ok((j, self.src[i..j].trim().to_string()));
899                    }
900                    j += 2 * ':'.len_utf8();
901                }
902                '\n' | '\r' => {
903                    self.num_newlines += 1;
904                    j += c.len_utf8();
905                }
906                _ => j += c.len_utf8(),
907            }
908        }
909        Err(self.mk_error(YaccGrammarErrorKind::ReachedEOL, j))
910    }
911
912    /// Parse a quoted string, allowing escape characters.
913    fn parse_int<T: FromStr + PrimInt>(
914        &mut self,
915        i: usize,
916    ) -> Result<(usize, T), YaccGrammarError> {
917        let mut j = i;
918        while j < self.src.len() {
919            let c = self.src[j..].chars().next().unwrap();
920            match c {
921                '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => j += 1,
922                _ => break,
923            }
924        }
925        match self.src[i..j].parse::<T>() {
926            Ok(x) => Ok((j, x)),
927            Err(_) => Err(self.mk_error(YaccGrammarErrorKind::IllegalInteger, i)),
928        }
929    }
930
931    /// Parse a quoted string, allowing escape characters.
932    fn parse_string(&mut self, mut i: usize) -> Result<(usize, String), YaccGrammarError> {
933        let qc = if self.lookahead_is("'", i).is_some() {
934            '\''
935        } else if self.lookahead_is("\"", i).is_some() {
936            '"'
937        } else {
938            return Err(self.mk_error(YaccGrammarErrorKind::InvalidString, i));
939        };
940
941        debug_assert!('"'.len_utf8() == 1 && '\''.len_utf8() == 1);
942        // Because we can encounter escape characters, we can't simply match text and slurp it into
943        // a String in one go (otherwise we'd include the escape characters). Conceptually we have
944        // to build the String up byte by byte, skipping escape characters, but that's slow.
945        // Instead we append chunks of the string up to (but excluding) escape characters.
946        let mut s = String::new();
947        i += 1;
948        let mut j = i;
949        while j < self.src.len() {
950            let c = self.src[j..].chars().next().unwrap();
951            match c {
952                '\n' | '\r' => {
953                    return Err(self.mk_error(YaccGrammarErrorKind::InvalidString, j));
954                }
955                x if x == qc => {
956                    s.push_str(&self.src[i..j]);
957                    return Ok((j + 1, s));
958                }
959                '\\' => {
960                    debug_assert!('\\'.len_utf8() == 1);
961                    match self.src[j + 1..].chars().next() {
962                        Some(c) if c == '\'' || c == '"' => {
963                            s.push_str(&self.src[i..j]);
964                            i = j + 1;
965                            j += 2;
966                        }
967                        _ => {
968                            return Err(self.mk_error(YaccGrammarErrorKind::InvalidString, j));
969                        }
970                    }
971                }
972                _ => j += c.len_utf8(),
973            }
974        }
975        Err(self.mk_error(YaccGrammarErrorKind::InvalidString, j))
976    }
977
978    /// Skip whitespace from `i` onwards. If `inc_newlines` is `false`, will return `Err` if a
979    /// newline is encountered; otherwise newlines are consumed and skipped.
980    fn parse_ws(&mut self, mut i: usize, inc_newlines: bool) -> Result<usize, YaccGrammarError> {
981        while i < self.src.len() {
982            let c = self.src[i..].chars().next().unwrap();
983            match c {
984                ' ' | '\t' => i += c.len_utf8(),
985                '\n' | '\r' => {
986                    if !inc_newlines {
987                        return Err(self.mk_error(YaccGrammarErrorKind::ReachedEOL, i));
988                    }
989                    self.num_newlines += 1;
990                    i += c.len_utf8();
991                }
992                '/' => {
993                    if i + c.len_utf8() == self.src.len() {
994                        break;
995                    } else {
996                        let j = i + c.len_utf8();
997                        let c = self.src[j..].chars().next().unwrap();
998                        match c {
999                            '/' => {
1000                                i = j + c.len_utf8();
1001                                for c in self.src[i..].chars() {
1002                                    i += c.len_utf8();
1003                                    if c == '\n' || c == '\r' {
1004                                        self.num_newlines += 1;
1005                                        break;
1006                                    }
1007                                }
1008                            }
1009                            '*' => {
1010                                // This is complicated by the fact that we need to deal with
1011                                // unclosed comments (i.e. '/*' without a corresponding '*/').
1012                                let mut k = j + c.len_utf8();
1013                                let mut found = false;
1014                                while k < self.src.len() {
1015                                    let c = self.src[k..].chars().next().unwrap();
1016                                    k += c.len_utf8();
1017                                    match c {
1018                                        '\n' | '\r' => {
1019                                            if !inc_newlines {
1020                                                return Err(self.mk_error(
1021                                                    YaccGrammarErrorKind::ReachedEOL,
1022                                                    i,
1023                                                ));
1024                                            }
1025                                            self.num_newlines += 1;
1026                                        }
1027                                        '*' => (),
1028                                        _ => continue,
1029                                    }
1030                                    if k < self.src.len() {
1031                                        let c = self.src[k..].chars().next().unwrap();
1032                                        if c == '/' {
1033                                            i = k + c.len_utf8();
1034                                            found = true;
1035                                            break;
1036                                        }
1037                                    }
1038                                }
1039                                if !found {
1040                                    return Err(
1041                                        self.mk_error(YaccGrammarErrorKind::IncompleteComment, i)
1042                                    );
1043                                }
1044                            }
1045                            _ => break,
1046                        }
1047                    }
1048                }
1049                _ => break,
1050            }
1051        }
1052        Ok(i)
1053    }
1054
1055    fn lookahead_is(&self, s: &'static str, i: usize) -> Option<usize> {
1056        if self.src[i..].starts_with(s) {
1057            Some(i + s.len())
1058        } else {
1059            None
1060        }
1061    }
1062
1063    fn mk_error(&self, k: YaccGrammarErrorKind, off: usize) -> YaccGrammarError {
1064        let span = Span::new(off, off);
1065        YaccGrammarError {
1066            kind: k,
1067            spans: vec![span],
1068        }
1069    }
1070}
1071
1072#[cfg(test)]
1073mod test {
1074    use super::{
1075        super::{
1076            AssocKind, Precedence, YaccKind, YaccOriginalActionKind,
1077            ast::{GrammarAST, Production, Symbol},
1078        },
1079        Span, Spanned, YaccGrammarError, YaccGrammarErrorKind, YaccParser,
1080    };
1081    use std::collections::HashSet;
1082
1083    fn parse(yacc_kind: YaccKind, s: &str) -> Result<GrammarAST, Vec<YaccGrammarError>> {
1084        let mut yp = YaccParser::new(yacc_kind, s);
1085        yp.parse()?;
1086        Ok(yp.build())
1087    }
1088
1089    fn rule(n: &str) -> Symbol {
1090        Symbol::Rule(n.to_string(), Span::new(0, 0))
1091    }
1092
1093    fn rule_span(n: &str, span: Span) -> Symbol {
1094        Symbol::Rule(n.to_string(), span)
1095    }
1096
1097    fn token(n: &str) -> Symbol {
1098        Symbol::Token(n.to_string(), Span::new(0, 0))
1099    }
1100    fn token_span(n: &str, span: Span) -> Symbol {
1101        Symbol::Token(n.to_string(), span)
1102    }
1103
1104    fn line_of_offset(s: &str, off: usize) -> usize {
1105        s[..off].lines().count()
1106    }
1107
1108    macro_rules! line_col {
1109        ($src:ident, $span: expr) => {{
1110            let mut line_cache = crate::newlinecache::NewlineCache::new();
1111            line_cache.feed(&$src);
1112            line_cache
1113                .byte_to_line_num_and_col_num(&$src, $span.start())
1114                .unwrap()
1115        }};
1116    }
1117
1118    trait ErrorsHelper {
1119        fn expect_error_at_line(self, src: &str, kind: YaccGrammarErrorKind, line: usize);
1120        fn expect_error_at_line_col(
1121            self,
1122            src: &str,
1123            kind: YaccGrammarErrorKind,
1124            line: usize,
1125            col: usize,
1126        );
1127        fn expect_error_at_lines_cols(
1128            self,
1129            src: &str,
1130            kind: YaccGrammarErrorKind,
1131            lines_cols: &mut dyn Iterator<Item = (usize, usize)>,
1132        );
1133        fn expect_multiple_errors(
1134            self,
1135            src: &str,
1136            expected: &mut dyn Iterator<Item = (YaccGrammarErrorKind, Vec<(usize, usize)>)>,
1137        );
1138    }
1139
1140    impl ErrorsHelper for Result<GrammarAST, Vec<YaccGrammarError>> {
1141        #[track_caller]
1142        fn expect_error_at_line(self, src: &str, kind: YaccGrammarErrorKind, line: usize) {
1143            let errs = self
1144                .as_ref()
1145                .map_err(Vec::as_slice)
1146                .expect_err("Parsed ok while expecting error");
1147            assert_eq!(errs.len(), 1);
1148            let e = &errs[0];
1149            assert_eq!(e.kind, kind);
1150            assert_eq!(line_of_offset(src, e.spans()[0].start()), line);
1151            assert_eq!(e.spans.len(), 1);
1152        }
1153
1154        #[track_caller]
1155        fn expect_error_at_line_col(
1156            self,
1157            src: &str,
1158            kind: YaccGrammarErrorKind,
1159            line: usize,
1160            col: usize,
1161        ) {
1162            self.expect_error_at_lines_cols(src, kind, &mut std::iter::once((line, col)))
1163        }
1164
1165        #[track_caller]
1166        fn expect_error_at_lines_cols(
1167            self,
1168            src: &str,
1169            kind: YaccGrammarErrorKind,
1170            lines_cols: &mut dyn Iterator<Item = (usize, usize)>,
1171        ) {
1172            let errs = self
1173                .as_ref()
1174                .map_err(Vec::as_slice)
1175                .expect_err("Parsed ok while expecting error");
1176            assert_eq!(errs.len(), 1);
1177            let e = &errs[0];
1178            assert_eq!(e.kind, kind);
1179            assert_eq!(
1180                e.spans()
1181                    .iter()
1182                    .map(|span| line_col!(src, span))
1183                    .collect::<Vec<(usize, usize)>>(),
1184                lines_cols.collect::<Vec<(usize, usize)>>()
1185            );
1186            // Check that it is valid to slice.
1187            for span in e.spans() {
1188                let _ = &src[span.start()..span.end()];
1189            }
1190        }
1191
1192        #[track_caller]
1193        fn expect_multiple_errors(
1194            self,
1195            src: &str,
1196            expected: &mut dyn Iterator<Item = (YaccGrammarErrorKind, Vec<(usize, usize)>)>,
1197        ) {
1198            let errs = self.expect_err("Parsed ok while expecting error");
1199            for e in &errs {
1200                // Check that it is valid to slice the source with the spans.
1201                for span in e.spans() {
1202                    let _ = &src[span.start()..span.end()];
1203                }
1204            }
1205
1206            assert_eq!(
1207                errs.iter()
1208                    .map(|e| {
1209                        (
1210                            e.kind.clone(),
1211                            e.spans()
1212                                .iter()
1213                                .map(|span| line_col!(src, span))
1214                                .collect::<Vec<_>>(),
1215                        )
1216                    })
1217                    .collect::<Vec<_>>(),
1218                expected.collect::<Vec<_>>()
1219            );
1220        }
1221    }
1222
1223    #[test]
1224    fn test_helper_fn() {
1225        assert_eq!(Symbol::Token("A".to_string(), Span::new(0, 0)), token("A"));
1226    }
1227
1228    #[test]
1229    fn test_symbol_eq() {
1230        assert_eq!(rule("A"), rule("A"));
1231        assert_ne!(rule("A"), rule("B"));
1232        assert_ne!(rule("A"), token("A"));
1233    }
1234
1235    #[test]
1236    fn test_rule() {
1237        let src = "
1238            %%
1239            A : 'a';
1240        "
1241        .to_string();
1242        let grm = parse(
1243            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1244            &src,
1245        )
1246        .unwrap();
1247        assert_eq!(grm.get_rule("A").unwrap().pidxs, vec![0]);
1248        let a_span = Span::new(33, 34);
1249        assert_eq!(
1250            grm.prods[grm.get_rule("A").unwrap().pidxs[0]],
1251            Production {
1252                symbols: vec![token_span("a", a_span)],
1253                precedence: None,
1254                action: None,
1255                prod_span: Span::new(32, 35),
1256            }
1257        );
1258        assert_eq!(&src[a_span.start()..a_span.end()], "a");
1259    }
1260
1261    #[test]
1262    fn test_rule_production_simple() {
1263        let src = "
1264            %%
1265            A : 'a';
1266            A : 'b';
1267        "
1268        .to_string();
1269        let grm = parse(
1270            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1271            &src,
1272        )
1273        .unwrap();
1274        let a_span = Span::new(33, 34);
1275        assert_eq!(
1276            grm.prods[grm.get_rule("A").unwrap().pidxs[0]],
1277            Production {
1278                symbols: vec![token_span("a", a_span)],
1279                precedence: None,
1280                action: None,
1281                prod_span: Span::new(32, 35),
1282            }
1283        );
1284        assert_eq!(&src[a_span.start()..a_span.end()], "a");
1285        let b_span = Span::new(54, 55);
1286        assert_eq!(
1287            grm.prods[grm.get_rule("A").unwrap().pidxs[1]],
1288            Production {
1289                symbols: vec![token_span("b", Span::new(54, 55))],
1290                precedence: None,
1291                action: None,
1292                prod_span: Span::new(53, 56),
1293            }
1294        );
1295        assert_eq!(&src[b_span.start()..b_span.end()], "b");
1296    }
1297
1298    #[test]
1299    fn test_rule_empty() {
1300        let src = "
1301            %%
1302            A : ;
1303            B : 'b' | ;
1304            C : | 'c';
1305        "
1306        .to_string();
1307        let grm = parse(
1308            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1309            &src,
1310        )
1311        .unwrap();
1312
1313        assert_eq!(
1314            grm.prods[grm.get_rule("A").unwrap().pidxs[0]],
1315            Production {
1316                symbols: vec![],
1317                precedence: None,
1318                action: None,
1319                prod_span: Span::new(32, 32),
1320            }
1321        );
1322
1323        let b_span = Span::new(51, 52);
1324        assert_eq!(
1325            grm.prods[grm.get_rule("B").unwrap().pidxs[0]],
1326            Production {
1327                symbols: vec![token_span("b", b_span)],
1328                precedence: None,
1329                action: None,
1330                prod_span: Span::new(50, 53),
1331            }
1332        );
1333        assert_eq!(&src[b_span.start()..b_span.end()], "b");
1334        assert_eq!(
1335            grm.prods[grm.get_rule("B").unwrap().pidxs[1]],
1336            Production {
1337                symbols: vec![],
1338                precedence: None,
1339                action: None,
1340                prod_span: Span::new(56, 56),
1341            }
1342        );
1343
1344        assert_eq!(
1345            grm.prods[grm.get_rule("C").unwrap().pidxs[0]],
1346            Production {
1347                symbols: vec![],
1348                precedence: None,
1349                action: None,
1350                prod_span: Span::new(74, 74),
1351            }
1352        );
1353        let c_span = Span::new(77, 78);
1354        assert_eq!(
1355            grm.prods[grm.get_rule("C").unwrap().pidxs[1]],
1356            Production {
1357                symbols: vec![token_span("c", c_span)],
1358                precedence: None,
1359                action: None,
1360                prod_span: Span::new(76, 79),
1361            }
1362        );
1363        assert_eq!(&src[c_span.start()..c_span.end()], "c");
1364    }
1365
1366    #[test]
1367    fn test_empty_program() {
1368        let src = "%%\nA : 'a';\n%%".to_string();
1369        parse(
1370            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1371            &src,
1372        )
1373        .unwrap();
1374    }
1375
1376    #[test]
1377    fn test_multiple_symbols() {
1378        let src = "%%\nA : 'a' B;".to_string();
1379        let grm = parse(
1380            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1381            &src,
1382        )
1383        .unwrap();
1384        let a_span = Span::new(8, 9);
1385        let b_span = Span::new(11, 12);
1386        assert_eq!(
1387            grm.prods[grm.get_rule("A").unwrap().pidxs[0]],
1388            Production {
1389                symbols: vec![token_span("a", a_span), rule_span("B", b_span)],
1390                precedence: None,
1391                action: None,
1392                prod_span: Span::new(7, 12),
1393            }
1394        );
1395        assert_eq!(&src[a_span.start()..a_span.end()], "a");
1396        assert_eq!(&src[b_span.start()..b_span.end()], "B");
1397    }
1398
1399    #[test]
1400    fn test_token_types() {
1401        let src = "%%\nA : 'a' \"b\";".to_string();
1402        let grm = parse(
1403            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1404            &src,
1405        )
1406        .unwrap();
1407        let a_span = Span::new(8, 9);
1408        let b_span = Span::new(12, 13);
1409        assert_eq!(
1410            grm.prods[grm.get_rule("A").unwrap().pidxs[0]],
1411            Production {
1412                symbols: vec![token_span("a", a_span), token_span("b", b_span)],
1413                precedence: None,
1414                action: None,
1415                prod_span: Span::new(7, 14),
1416            }
1417        );
1418        assert_eq!(&src[a_span.start()..a_span.end()], "a");
1419        assert_eq!(&src[b_span.start()..b_span.end()], "b");
1420    }
1421
1422    #[test]
1423    fn test_declaration_start() {
1424        let src = "%start   A\n%%\nA : a;".to_string();
1425        let grm = parse(
1426            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1427            &src,
1428        )
1429        .unwrap();
1430        assert_eq!(grm.start.unwrap(), ("A".to_string(), Span::new(9, 10)));
1431    }
1432
1433    #[test]
1434    fn test_declaration_token() {
1435        let src = "%token   a\n%%\nA : a;".to_string();
1436        let grm = parse(
1437            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1438            &src,
1439        )
1440        .unwrap();
1441        assert!(grm.has_token("a"));
1442    }
1443
1444    #[test]
1445    fn test_declaration_token_literal() {
1446        let src = "%token   'a'\n%%\nA : 'a';".to_string();
1447        let grm = parse(
1448            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1449            &src,
1450        )
1451        .unwrap();
1452        assert!(grm.has_token("a"));
1453    }
1454
1455    #[test]
1456    fn test_declaration_tokens() {
1457        let src = "%token   a b c 'd'\n%%\nA : a;".to_string();
1458        let grm = parse(
1459            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1460            &src,
1461        )
1462        .unwrap();
1463        assert!(grm.has_token("a"));
1464        assert!(grm.has_token("b"));
1465        assert!(grm.has_token("c"));
1466    }
1467
1468    #[test]
1469    fn test_auto_add_tokens() {
1470        let src = "%%\nA : 'a';".to_string();
1471        let grm = parse(
1472            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1473            &src,
1474        )
1475        .unwrap();
1476        assert!(grm.has_token("a"));
1477    }
1478
1479    #[test]
1480    fn test_token_non_literal() {
1481        let src = "%token T %%\nA : T;".to_string();
1482        let grm = parse(
1483            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1484            &src,
1485        )
1486        .unwrap();
1487        assert!(grm.has_token("T"));
1488        let t_span = Span::new(16, 17);
1489        assert_eq!(
1490            grm.prods[grm.get_rule("A").unwrap().pidxs[0]],
1491            Production {
1492                symbols: vec![token_span("T", t_span)],
1493                precedence: None,
1494                action: None,
1495                prod_span: t_span,
1496            }
1497        );
1498        assert_eq!(&src[t_span.start()..t_span.end() + 1], "T;");
1499    }
1500
1501    #[test]
1502    fn test_token_unicode() {
1503        let src = "%token '❤' %%\nA : '❤';".to_string();
1504        let grm = parse(
1505            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1506            &src,
1507        )
1508        .unwrap();
1509        assert!(grm.has_token("❤"));
1510    }
1511
1512    #[test]
1513    fn test_unicode_err1() {
1514        let src = "%token '❤' ❤;".to_string();
1515        parse(
1516            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1517            &src,
1518        )
1519        .expect_error_at_line_col(&src, YaccGrammarErrorKind::IllegalString, 1, 12);
1520    }
1521
1522    #[test]
1523    fn test_unicode_err2() {
1524        let src = "%token '❤'\n%%\nA : '❤' | ❤;".to_string();
1525        parse(
1526            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1527            &src,
1528        )
1529        .expect_error_at_line_col(&src, YaccGrammarErrorKind::IllegalString, 3, 11);
1530    }
1531
1532    #[test]
1533    fn test_missing_end_quote() {
1534        let src = "%epp X \"f\\".to_string();
1535        parse(
1536            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1537            &src,
1538        )
1539        .expect_error_at_line_col(&src, YaccGrammarErrorKind::InvalidString, 1, 10);
1540    }
1541
1542    #[test]
1543    fn test_simple_decl_fail() {
1544        let src = "%fail x\n%%\nA : a".to_string();
1545        parse(
1546            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1547            &src,
1548        )
1549        .expect_error_at_line_col(&src, YaccGrammarErrorKind::UnknownDeclaration, 1, 1);
1550    }
1551
1552    #[test]
1553    fn test_empty() {
1554        let src = "".to_string();
1555        parse(
1556            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1557            &src,
1558        )
1559        .expect_error_at_line_col("", YaccGrammarErrorKind::PrematureEnd, 1, 1);
1560    }
1561
1562    #[test]
1563    fn test_incomplete_rule1() {
1564        let src = "%%A:".to_string();
1565        parse(
1566            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1567            &src,
1568        )
1569        .expect_error_at_line_col(&src, YaccGrammarErrorKind::IncompleteRule, 1, 5);
1570    }
1571
1572    #[test]
1573    fn test_line_col_report1() {
1574        let src = "%%
1575A:"
1576        .to_string();
1577        parse(
1578            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1579            &src,
1580        )
1581        .expect_error_at_line_col(&src, YaccGrammarErrorKind::IncompleteRule, 2, 3);
1582    }
1583
1584    #[test]
1585    fn test_line_col_report2() {
1586        let src = "%%
1587A:
1588"
1589        .to_string();
1590        parse(
1591            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1592            &src,
1593        )
1594        .expect_error_at_line_col(&src, YaccGrammarErrorKind::IncompleteRule, 3, 1);
1595    }
1596
1597    #[test]
1598    fn test_line_col_report3() {
1599        let src = "
1600
1601        %woo"
1602            .to_string();
1603        parse(
1604            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1605            &src,
1606        )
1607        .expect_error_at_line_col(&src, YaccGrammarErrorKind::UnknownDeclaration, 3, 9);
1608    }
1609
1610    #[test]
1611    fn test_missing_colon() {
1612        let src = "%%A x;".to_string();
1613        parse(
1614            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1615            &src,
1616        )
1617        .expect_error_at_line_col(&src, YaccGrammarErrorKind::MissingColon, 1, 5);
1618    }
1619
1620    #[test]
1621    fn test_premature_end() {
1622        let src = "%token x".to_string();
1623        parse(
1624            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1625            &src,
1626        )
1627        .expect_error_at_line_col(&src, YaccGrammarErrorKind::PrematureEnd, 1, 9);
1628    }
1629
1630    #[test]
1631    fn test_premature_end_multibyte() {
1632        let src = "%actiontype 🦀".to_string();
1633        parse(
1634            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1635            &src,
1636        )
1637        .expect_error_at_line_col(&src, YaccGrammarErrorKind::PrematureEnd, 1, 14);
1638        let src = "%parse-param c:🦀".to_string();
1639        parse(
1640            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1641            &src,
1642        )
1643        .expect_error_at_line_col(&src, YaccGrammarErrorKind::PrematureEnd, 1, 17);
1644        let src = "// 🦀".to_string();
1645        parse(
1646            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1647            &src,
1648        )
1649        .expect_error_at_line_col(&src, YaccGrammarErrorKind::PrematureEnd, 1, 5);
1650    }
1651
1652    #[test]
1653    fn test_same_line() {
1654        let src = "%token
1655x"
1656        .to_string();
1657        parse(
1658            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1659            &src,
1660        )
1661        .expect_error_at_line_col(&src, YaccGrammarErrorKind::ReachedEOL, 1, 7);
1662    }
1663
1664    #[test]
1665    fn test_unknown_declaration() {
1666        let src = "%woo".to_string();
1667        parse(
1668            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1669            &src,
1670        )
1671        .expect_error_at_line_col(&src, YaccGrammarErrorKind::UnknownDeclaration, 1, 1);
1672    }
1673
1674    #[test]
1675    fn test_grmtools_format() {
1676        let src = "
1677          %start A
1678          %%
1679          A -> T: 'b';
1680          B -> Result<(), T>: 'c';
1681          C -> ::std::result::Result<(), T>: 'd';
1682          "
1683        .to_string();
1684        let grm = parse(YaccKind::Grmtools, &src).unwrap();
1685        assert_eq!(grm.rules["A"].actiont, Some("T".to_string()));
1686        assert_eq!(grm.rules["B"].actiont, Some("Result<(), T>".to_string()));
1687        assert_eq!(
1688            grm.rules["C"].actiont,
1689            Some("::std::result::Result<(), T>".to_string())
1690        );
1691    }
1692
1693    #[test]
1694    #[rustfmt::skip]
1695    fn test_precs() {
1696        let src = "
1697          %left '+' '-'
1698          %left '*'
1699          %right '/'
1700          %right '^'
1701          %nonassoc '~'
1702          %%
1703          ".to_string();
1704        let grm = parse(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), &src).unwrap();
1705        assert_eq!(grm.precs.len(), 6);
1706        assert_eq!(grm.precs["+"], (Precedence{level: 0, kind: AssocKind::Left}, Span::new(18, 19)));
1707        assert_eq!(grm.precs["-"], (Precedence{level: 0, kind: AssocKind::Left}, Span::new(22, 23)));
1708        assert_eq!(grm.precs["*"], (Precedence{level: 1, kind: AssocKind::Left}, Span::new(42, 43)));
1709        assert_eq!(grm.precs["/"], (Precedence{level: 2, kind: AssocKind::Right}, Span::new(63, 64)));
1710        assert_eq!(grm.precs["^"], (Precedence{level: 3, kind: AssocKind::Right}, Span::new(84, 85)));
1711        assert_eq!(grm.precs["~"], (Precedence{level: 4, kind: AssocKind::Nonassoc}, Span::new(108, 109)));
1712    }
1713
1714    #[test]
1715    fn test_dup_precs() {
1716        #[rustfmt::skip]
1717        let srcs = [
1718            ("
1719          %left 'x'
1720          %left 'x'
1721          %%
1722          ", ((2, 18), (3, 18))),
1723            ("
1724          %left 'x'
1725          %right 'x'
1726          %%
1727          ", ((2, 18), (3, 19))),
1728            ("
1729          %right 'x'
1730          %right 'x'
1731          %%
1732          ", ((2, 19), (3, 19))),
1733            ("
1734          %nonassoc 'x'
1735          %nonassoc 'x'
1736          %%
1737          ", ((2, 22), (3, 22))),
1738            ("
1739          %left 'x'
1740          %nonassoc 'x'
1741          %%
1742          ", ((2, 18), (3, 22))),
1743            ("
1744          %right 'x'
1745          %nonassoc 'x'
1746          %%
1747          ", ((2, 19), (3, 22)))
1748        ];
1749        for (src, (expected_origin, expected_dup)) in srcs.iter() {
1750            parse(
1751                YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1752                src,
1753            )
1754            .expect_error_at_lines_cols(
1755                src,
1756                YaccGrammarErrorKind::DuplicatePrecedence,
1757                &mut [*expected_origin, *expected_dup].into_iter(),
1758            );
1759        }
1760    }
1761
1762    #[test]
1763    fn test_multiple_dup_precs() {
1764        let src = "
1765          %left 'x'
1766          %left 'x'
1767          %right 'x'
1768          %nonassoc 'x'
1769          %left 'y'
1770          %nonassoc 'y'
1771          %right 'y'
1772          %%";
1773
1774        parse(
1775            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1776            src,
1777        )
1778        .expect_multiple_errors(
1779            src,
1780            &mut [
1781                (
1782                    YaccGrammarErrorKind::DuplicatePrecedence,
1783                    vec![(2, 18), (3, 18), (4, 19), (5, 22)],
1784                ),
1785                (
1786                    YaccGrammarErrorKind::DuplicatePrecedence,
1787                    vec![(6, 18), (7, 22), (8, 19)],
1788                ),
1789            ]
1790            .into_iter(),
1791        );
1792    }
1793
1794    #[test]
1795    #[rustfmt::skip]
1796    fn test_prec_override() {
1797        // Taken from the Yacc manual
1798        let src = "
1799            %left '+' '-'
1800            %left '*' '/'
1801            %%
1802            expr : expr '+' expr
1803                 | expr '-' expr
1804                 | expr '*' expr
1805                 | expr '/' expr
1806                 | '-'  expr %prec '*'
1807                 | NAME ;
1808        ";
1809        let grm = parse(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), src).unwrap();
1810        assert_eq!(grm.precs.len(), 4);
1811        assert_eq!(grm.prods[grm.rules["expr"].pidxs[0]].precedence, None);
1812        assert_eq!(grm.prods[grm.rules["expr"].pidxs[3]].symbols.len(), 3);
1813        assert_eq!(grm.prods[grm.rules["expr"].pidxs[4]].symbols.len(), 2);
1814        assert_eq!(grm.prods[grm.rules["expr"].pidxs[4]].precedence, Some("*".to_string()));
1815    }
1816
1817    #[test]
1818    fn test_prec_empty() {
1819        let src = "
1820        %%
1821        expr : 'a'
1822             | %empty %prec 'a';
1823        ";
1824        let grm = parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
1825        assert_eq!(
1826            grm.prods[grm.rules["expr"].pidxs[1]].precedence,
1827            Some("a".to_string())
1828        );
1829    }
1830
1831    #[test]
1832    fn test_bad_prec_overrides() {
1833        let src = "
1834        %%
1835        S: 'A' %prec ;
1836        ";
1837        parse(
1838            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1839            src,
1840        )
1841        .expect_error_at_line(src, YaccGrammarErrorKind::IllegalString, 3);
1842    }
1843
1844    #[test]
1845    fn test_parse_avoid_insert() {
1846        let ast = parse(
1847            YaccKind::Eco,
1848            "
1849          %avoid_insert ws1 ws2
1850          %start R
1851          %%
1852          R: 'a';
1853          ",
1854        )
1855        .unwrap();
1856        assert_eq!(
1857            ast.avoid_insert,
1858            Some(
1859                [
1860                    ("ws1".to_string(), Span::new(25, 28)),
1861                    ("ws2".to_string(), Span::new(29, 32))
1862                ]
1863                .iter()
1864                .cloned()
1865                .collect()
1866            )
1867        );
1868        assert!(ast.tokens.get("ws1").is_some());
1869        assert!(ast.tokens.get("ws2").is_some());
1870    }
1871
1872    #[test]
1873    fn test_multiple_avoid_insert() {
1874        let ast = parse(
1875            YaccKind::Eco,
1876            "
1877          %avoid_insert X
1878          %avoid_insert Y
1879          %%
1880          ",
1881        )
1882        .unwrap();
1883        assert_eq!(
1884            ast.avoid_insert,
1885            Some(
1886                [
1887                    ("X".to_string(), Span::new(25, 26)),
1888                    ("Y".to_string(), Span::new(51, 52))
1889                ]
1890                .iter()
1891                .cloned()
1892                .collect()
1893            )
1894        );
1895    }
1896
1897    #[test]
1898    fn test_duplicate_avoid_insert() {
1899        let src = "
1900          %avoid_insert X Y
1901          %avoid_insert Y
1902          %%
1903          ";
1904        parse(YaccKind::Eco, src).expect_error_at_lines_cols(
1905            src,
1906            YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration,
1907            &mut [(2usize, 27usize), (3, 25)].into_iter(),
1908        );
1909    }
1910
1911    #[test]
1912    fn test_duplicate_avoid_insert2() {
1913        let src = "
1914        %avoid_insert X
1915        %avoid_insert Y Y
1916        %%
1917        ";
1918        parse(YaccKind::Eco, src).expect_error_at_lines_cols(
1919            src,
1920            YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration,
1921            &mut [(3, 23), (3, 25)].into_iter(),
1922        );
1923    }
1924
1925    #[test]
1926    fn test_multiple_duplicate_avoid_insert() {
1927        let src = "
1928        %avoid_insert X
1929        %avoid_insert Y Y X
1930        %%
1931        ";
1932        parse(YaccKind::Eco, src).expect_multiple_errors(
1933            src,
1934            &mut [
1935                (
1936                    YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration,
1937                    vec![(3, 23), (3, 25)],
1938                ),
1939                (
1940                    YaccGrammarErrorKind::DuplicateAvoidInsertDeclaration,
1941                    vec![(2, 23), (3, 27)],
1942                ),
1943            ]
1944            .into_iter(),
1945        );
1946    }
1947
1948    #[test]
1949    fn test_no_implicit_tokens_in_original_yacc() {
1950        let src = "
1951        %implicit_tokens X
1952        %%
1953        ";
1954        parse(
1955            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1956            src,
1957        )
1958        .expect_error_at_line(src, YaccGrammarErrorKind::UnknownDeclaration, 2);
1959    }
1960
1961    #[test]
1962    fn test_parse_implicit_tokens() {
1963        let ast = parse(
1964            YaccKind::Eco,
1965            "
1966          %implicit_tokens ws1 ws2
1967          %start R
1968          %%
1969          R: 'a';
1970          ",
1971        )
1972        .unwrap();
1973        assert_eq!(
1974            ast.implicit_tokens,
1975            Some(
1976                [
1977                    ("ws1".to_string(), Span::new(28, 31)),
1978                    ("ws2".to_string(), Span::new(32, 35))
1979                ]
1980                .iter()
1981                .cloned()
1982                .collect()
1983            )
1984        );
1985        assert!(ast.tokens.get("ws1").is_some());
1986        assert!(ast.tokens.get("ws2").is_some());
1987    }
1988
1989    #[test]
1990    fn test_multiple_implicit_tokens() {
1991        let ast = parse(
1992            YaccKind::Eco,
1993            "
1994          %implicit_tokens X
1995          %implicit_tokens Y
1996          %%
1997          ",
1998        )
1999        .unwrap();
2000        assert_eq!(
2001            ast.implicit_tokens,
2002            Some(
2003                [
2004                    ("X".to_string(), Span::new(28, 29)),
2005                    ("Y".to_string(), Span::new(57, 58))
2006                ]
2007                .iter()
2008                .cloned()
2009                .collect()
2010            )
2011        );
2012    }
2013
2014    #[test]
2015    fn test_duplicate_implicit_tokens() {
2016        let src = "
2017        %implicit_tokens X
2018        %implicit_tokens X Y
2019        %%
2020        ";
2021        parse(YaccKind::Eco, src).expect_error_at_lines_cols(
2022            src,
2023            YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration,
2024            &mut [(2, 26), (3, 26)].into_iter(),
2025        );
2026    }
2027
2028    #[test]
2029    fn test_duplicate_implicit_tokens2() {
2030        let src = "
2031        %implicit_tokens X X
2032        %implicit_tokens Y
2033        %%
2034        ";
2035        parse(YaccKind::Eco, src).expect_error_at_lines_cols(
2036            src,
2037            YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration,
2038            &mut [(2, 26), (2, 28)].into_iter(),
2039        );
2040    }
2041
2042    #[test]
2043    fn test_multiple_duplicate_implicit_tokens_and_invalid_rule() {
2044        let src = "
2045        %implicit_tokens X
2046        %implicit_tokens X Y
2047        %implicit_tokens Y
2048        %%
2049        IncompleteRule: ";
2050        parse(YaccKind::Eco, src).expect_multiple_errors(
2051            src,
2052            &mut [
2053                (
2054                    YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration,
2055                    vec![(2, 26), (3, 26)],
2056                ),
2057                (
2058                    YaccGrammarErrorKind::DuplicateImplicitTokensDeclaration,
2059                    vec![(3, 28), (4, 26)],
2060                ),
2061                (YaccGrammarErrorKind::IncompleteRule, vec![(6, 25)]),
2062            ]
2063            .into_iter(),
2064        );
2065    }
2066
2067    #[test]
2068    #[rustfmt::skip]
2069    fn test_parse_epp() {
2070        let ast = parse(
2071            YaccKind::Eco,
2072            r#"
2073          %epp A "a"
2074          %epp B 'a'
2075          %epp C '"'
2076          %epp D "'"
2077          %epp E "\""
2078          %epp F '\''
2079          %epp G "a\"b"
2080          %%
2081          R: 'A';
2082          "#,
2083        )
2084        .unwrap();
2085        assert_eq!(ast.epp.len(), 7);
2086        assert_eq!(ast.epp["A"], (Span::new(16, 17),   ("a".to_string(),   Span::new(18, 21))));
2087        assert_eq!(ast.epp["B"], (Span::new(37, 38),   ("a".to_string(),   Span::new(39, 42))));
2088        assert_eq!(ast.epp["C"], (Span::new(58, 59),   ("\"".to_string(),  Span::new(60, 63))));
2089        assert_eq!(ast.epp["D"], (Span::new(79, 80),   ("'".to_string(),   Span::new(81, 84))));
2090        assert_eq!(ast.epp["E"], (Span::new(100, 101), ("\"".to_string(),  Span::new(102, 106))));
2091        assert_eq!(ast.epp["F"], (Span::new(122, 123), ("'".to_string(),   Span::new(124, 128))));
2092        assert_eq!(ast.epp["G"], (Span::new(144, 145), ("a\"b".to_string(),Span::new(146, 152))));
2093    }
2094
2095    #[test]
2096    fn test_duplicate_epp() {
2097        let src = "
2098        %epp A \"a\"
2099        %epp A \"a\"
2100        %epp A \"a\"
2101        %%
2102        ";
2103        parse(YaccKind::Eco, src).expect_error_at_lines_cols(
2104            src,
2105            YaccGrammarErrorKind::DuplicateEPP,
2106            &mut [(2, 14), (3, 14), (4, 14)].into_iter(),
2107        );
2108    }
2109
2110    #[test]
2111    fn test_multiple_duplicate_epp() {
2112        let src = "
2113        %epp A \"a1\"
2114        %epp A \"a2\"
2115        %epp A \"a3\"
2116        %epp B \"b1\"
2117        %epp B \"b2\"
2118        %epp B \"b3\"
2119        %%
2120        ";
2121        parse(YaccKind::Eco, src).expect_multiple_errors(
2122            src,
2123            &mut [
2124                (
2125                    YaccGrammarErrorKind::DuplicateEPP,
2126                    vec![(2, 14), (3, 14), (4, 14)],
2127                ),
2128                (
2129                    YaccGrammarErrorKind::DuplicateEPP,
2130                    vec![(5, 14), (6, 14), (7, 14)],
2131                ),
2132            ]
2133            .into_iter(),
2134        );
2135    }
2136
2137    #[test]
2138    fn test_broken_string() {
2139        let src = "
2140          %epp A \"a
2141          %%
2142          ";
2143        parse(YaccKind::Eco, src).expect_error_at_line(src, YaccGrammarErrorKind::InvalidString, 2);
2144
2145        let src = "
2146        %epp A \"a";
2147        parse(YaccKind::Eco, src).expect_error_at_line(src, YaccGrammarErrorKind::InvalidString, 2);
2148    }
2149
2150    #[test]
2151    fn test_duplicate_start() {
2152        let src = "
2153          %start X
2154          %start X
2155          %%
2156          ";
2157        parse(YaccKind::Eco, src).expect_error_at_lines_cols(
2158            src,
2159            YaccGrammarErrorKind::DuplicateStartDeclaration,
2160            &mut [(2, 18), (3, 18)].into_iter(),
2161        );
2162    }
2163
2164    #[test]
2165    fn test_duplicate_start_premature_end() {
2166        let src = "
2167          %start X
2168          %start X";
2169        parse(YaccKind::Eco, src).expect_multiple_errors(
2170            src,
2171            &mut [
2172                (
2173                    YaccGrammarErrorKind::DuplicateStartDeclaration,
2174                    vec![(2, 18), (3, 18)],
2175                ),
2176                (YaccGrammarErrorKind::PrematureEnd, vec![(3, 19)]),
2177            ]
2178            .into_iter(),
2179        );
2180    }
2181
2182    #[test]
2183    fn test_duplicate_expect() {
2184        let src = "
2185          %expect 1
2186          %expect 2
2187          %expect 3
2188          %%
2189          ";
2190        parse(
2191            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2192            src,
2193        )
2194        .expect_error_at_lines_cols(
2195            src,
2196            YaccGrammarErrorKind::DuplicateExpectDeclaration,
2197            &mut [(2, 19), (3, 19), (4, 19)].into_iter(),
2198        )
2199    }
2200
2201    #[test]
2202    fn test_duplicate_expect_and_missing_colon() {
2203        let src = "
2204          %expect 1
2205          %expect 2
2206          %expect 3
2207          %%
2208          A ;";
2209        parse(
2210            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2211            src,
2212        )
2213        .expect_multiple_errors(
2214            src,
2215            &mut [
2216                (
2217                    YaccGrammarErrorKind::DuplicateExpectDeclaration,
2218                    vec![(2, 19), (3, 19), (4, 19)],
2219                ),
2220                (YaccGrammarErrorKind::MissingColon, vec![(6, 13)]),
2221            ]
2222            .into_iter(),
2223        )
2224    }
2225
2226    #[test]
2227    fn test_duplicate_expectrr() {
2228        let src = "
2229          %expect-rr 1
2230          %expect-rr 2
2231          %expect-rr 3
2232          %%
2233          ";
2234        parse(
2235            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2236            src,
2237        )
2238        .expect_error_at_lines_cols(
2239            src,
2240            YaccGrammarErrorKind::DuplicateExpectRRDeclaration,
2241            &mut [(2, 22), (3, 22), (4, 22)].into_iter(),
2242        );
2243    }
2244
2245    #[test]
2246    fn test_duplicate_expectrr_illegal_name() {
2247        let src = "
2248          %expect-rr 1
2249          %expect-rr 2
2250          %expect-rr 3
2251          %%
2252          +IllegalRuleName+:;";
2253        parse(
2254            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2255            src,
2256        )
2257        .expect_multiple_errors(
2258            src,
2259            &mut [
2260                (
2261                    YaccGrammarErrorKind::DuplicateExpectRRDeclaration,
2262                    vec![(2, 22), (3, 22), (4, 22)],
2263                ),
2264                (YaccGrammarErrorKind::IllegalName, vec![(6, 11)]),
2265            ]
2266            .into_iter(),
2267        );
2268    }
2269
2270    #[test]
2271    fn test_implicit_start() {
2272        let ast = parse(
2273            YaccKind::Eco,
2274            "
2275          %%
2276          R: ;
2277          R2: ;
2278          R3: ;
2279          ",
2280        )
2281        .unwrap();
2282        assert_eq!(ast.start, Some(("R".to_string(), Span::new(24, 25))));
2283    }
2284
2285    #[test]
2286    fn test_action() {
2287        let grm = parse(
2288            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2289            "
2290          %%
2291          A: 'a' B { println!(\"test\"); }
2292           ;
2293          B: 'b' 'c' { add($1, $2); }
2294           | 'd'
2295           ;
2296          D: 'd' {}
2297           ;
2298          ",
2299        )
2300        .unwrap();
2301        let action_str = " println!(\"test\"); ".to_string();
2302        assert_eq!(
2303            grm.prods[grm.rules["A"].pidxs[0]].action,
2304            Some((action_str.clone(), Span::new(34, 34 + action_str.len())))
2305        );
2306        let action_str = " add($1, $2); ".to_string();
2307        assert_eq!(
2308            grm.prods[grm.rules["B"].pidxs[0]].action,
2309            Some((action_str.clone(), Span::new(90, 90 + action_str.len())))
2310        );
2311        assert_eq!(grm.prods[grm.rules["B"].pidxs[1]].action, None);
2312    }
2313
2314    #[test]
2315    fn test_action_ends_in_multibyte() {
2316        let grm = parse(
2317            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2318            "%%A: '_' {(); // 🦀};",
2319        )
2320        .unwrap();
2321        let action_str = "(); // 🦀".to_string();
2322        assert_eq!(
2323            grm.prods[grm.rules["A"].pidxs[0]].action,
2324            Some((action_str.clone(), Span::new(10, 10 + action_str.len())))
2325        );
2326    }
2327
2328    #[test]
2329    fn test_programs() {
2330        let grm = parse(
2331            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2332            "
2333         %%
2334         A: 'a';
2335         %%
2336         fn foo() {}",
2337        )
2338        .unwrap();
2339        assert_eq!(grm.programs, Some("fn foo() {}".to_string()));
2340    }
2341
2342    #[test]
2343    fn test_actions_with_newlines() {
2344        let src = "
2345        %%
2346        A: 'a' { foo();
2347                 bar(); }
2348        ;
2349        B: b';";
2350        parse(
2351            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2352            src,
2353        )
2354        .expect_error_at_line(src, YaccGrammarErrorKind::IllegalString, 6);
2355    }
2356
2357    #[test]
2358    fn test_comments() {
2359        let src = "
2360            // A valid comment
2361            %token   a
2362            /* Another valid comment */
2363            %%\n
2364            A : a;";
2365        let grm = parse(
2366            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2367            src,
2368        )
2369        .unwrap();
2370        assert!(grm.has_token("a"));
2371
2372        let src = "
2373        /* An invalid comment * /
2374        %token   a
2375        %%\n
2376        A : a;";
2377        parse(
2378            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2379            src,
2380        )
2381        .expect_error_at_line(src, YaccGrammarErrorKind::IncompleteComment, 2);
2382
2383        let src = "
2384        %token   a
2385        %%
2386        /* A valid
2387         * multi-line comment
2388         */
2389        /* An invalid comment * /
2390        A : a;";
2391        parse(
2392            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2393            src,
2394        )
2395        .expect_error_at_line(src, YaccGrammarErrorKind::IncompleteComment, 7);
2396
2397        let src = "
2398        %token   a
2399        %%
2400        // Valid comment
2401        A : a";
2402        parse(
2403            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2404            src,
2405        )
2406        .expect_error_at_line(src, YaccGrammarErrorKind::IncompleteRule, 5);
2407    }
2408
2409    #[test]
2410    fn test_action_type() {
2411        let grm = parse(
2412            YaccKind::Original(YaccOriginalActionKind::UserAction),
2413            "
2414         %actiontype T
2415         %%
2416         A: 'a';
2417         %%
2418         fn foo() {}",
2419        )
2420        .unwrap();
2421        assert_eq!(grm.rules["A"].actiont, Some("T".to_string()));
2422    }
2423
2424    #[test]
2425    fn test_only_one_type() {
2426        let src = "
2427         %actiontype T1
2428         %actiontype T2
2429         %actiontype T3
2430         %%
2431         A: 'a';";
2432        parse(
2433            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2434            src,
2435        )
2436        .expect_error_at_lines_cols(
2437            src,
2438            YaccGrammarErrorKind::DuplicateActiontypeDeclaration,
2439            &mut [(2, 22), (3, 22), (4, 22)].into_iter(),
2440        );
2441    }
2442
2443    #[test]
2444    fn test_duplicate_actiontype_and_premature_end() {
2445        let src = "
2446         %actiontype T1
2447         %actiontype T2
2448         %actiontype T3";
2449        parse(
2450            YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
2451            src,
2452        )
2453        .expect_multiple_errors(
2454            src,
2455            &mut [
2456                (
2457                    YaccGrammarErrorKind::DuplicateActiontypeDeclaration,
2458                    vec![(2, 22), (3, 22), (4, 22)],
2459                ),
2460                (YaccGrammarErrorKind::PrematureEnd, vec![(4, 24)]),
2461            ]
2462            .into_iter(),
2463        )
2464    }
2465
2466    #[test]
2467    fn test_parse_param() {
2468        let src = "
2469          %parse-param a::b: (u64, u64)
2470          %%
2471          A: 'a';
2472         ";
2473        let grm = parse(YaccKind::Original(YaccOriginalActionKind::UserAction), src).unwrap();
2474
2475        assert_eq!(
2476            grm.parse_param,
2477            Some(("a::b".to_owned(), "(u64, u64)".to_owned()))
2478        );
2479    }
2480
2481    #[test]
2482    fn test_parse_generics() {
2483        let src = "
2484          %parse-generics 'a, K, V
2485          %%
2486          A: 'a';
2487         ";
2488        let grm = parse(YaccKind::Original(YaccOriginalActionKind::UserAction), src).unwrap();
2489
2490        assert_eq!(grm.parse_generics, Some("'a, K, V".to_owned()));
2491    }
2492
2493    #[test]
2494    fn test_duplicate_rule() {
2495        let ast = parse(
2496            YaccKind::Grmtools,
2497            "%token A B D
2498%%
2499Expr -> () : %empty | A;
2500Expr -> () : B | 'C';
2501Expr -> () : D;
2502",
2503        )
2504        .unwrap();
2505        let expr_rule = ast.get_rule("Expr").unwrap();
2506        let mut prod_names = HashSet::new();
2507        for pidx in &expr_rule.pidxs {
2508            for sym in &ast.prods[*pidx].symbols {
2509                let name = match sym {
2510                    Symbol::Token(name, _) | Symbol::Rule(name, _) => name.clone(),
2511                };
2512                prod_names.insert(name);
2513            }
2514        }
2515        assert_eq!(ast.prods.len(), 5);
2516        assert_eq!(
2517            prod_names,
2518            HashSet::from_iter(["A", "B", "C", "D"].map(|s| s.to_owned()))
2519        );
2520    }
2521
2522    #[test]
2523    fn test_duplicate_start_and_missing_arrow() {
2524        let src = "%start A
2525%start A
2526%start A
2527%%
2528A -> () : 'a1';
2529B";
2530        parse(YaccKind::Grmtools, src).expect_multiple_errors(
2531            src,
2532            &mut [
2533                (
2534                    YaccGrammarErrorKind::DuplicateStartDeclaration,
2535                    vec![(1, 8), (2, 8), (3, 8)],
2536                ),
2537                (YaccGrammarErrorKind::MissingRightArrow, vec![(6, 2)]),
2538            ]
2539            .into_iter(),
2540        )
2541    }
2542
2543    #[test]
2544    fn test_routines_multiple_errors() {
2545        let mut src = String::from(
2546            "
2547        %start A
2548        %start B
2549        %expect 1
2550        %expect 2
2551        %%
2552        A -> () : 'a';
2553        %%
2554        ",
2555        );
2556        let mut expected_errs = vec![
2557            (
2558                YaccGrammarErrorKind::DuplicateStartDeclaration,
2559                vec![(2, 16), (3, 16)],
2560            ),
2561            (
2562                YaccGrammarErrorKind::DuplicateExpectDeclaration,
2563                vec![(4, 17), (5, 17)],
2564            ),
2565        ];
2566        parse(YaccKind::Grmtools, &src)
2567            .expect_multiple_errors(&src, &mut expected_errs.clone().into_iter());
2568
2569        src.push_str(
2570            "
2571                /* Incomplete comment
2572        ",
2573        );
2574        expected_errs.push((YaccGrammarErrorKind::IncompleteComment, vec![(10, 17)]));
2575        parse(YaccKind::Grmtools, &src)
2576            .expect_multiple_errors(&src, &mut expected_errs.clone().into_iter());
2577    }
2578
2579    #[test]
2580    fn test_expect_unused() {
2581        let src = r#"
2582        %expect-unused A 'b' "c"
2583        %%
2584        A: ;
2585        "#;
2586        let grm = parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
2587        assert!(
2588            grm.expect_unused
2589                .contains(&Symbol::Rule("A".to_string(), Span::new(24, 25)))
2590        );
2591        assert!(
2592            grm.expect_unused
2593                .contains(&Symbol::Token("b".to_string(), Span::new(27, 28)))
2594        );
2595        assert!(
2596            grm.expect_unused
2597                .contains(&Symbol::Token("c".to_string(), Span::new(31, 32)))
2598        );
2599    }
2600
2601    #[test]
2602    fn test_bad_expect_unused() {
2603        let src = "
2604        %expect-unused %
2605        %%
2606        A: ;
2607        ";
2608        parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).expect_error_at_line_col(
2609            src,
2610            YaccGrammarErrorKind::UnknownDeclaration,
2611            2,
2612            24,
2613        );
2614    }
2615
2616    #[test]
2617    fn test_unused_symbols() {
2618        let ast = parse(
2619            YaccKind::Original(YaccOriginalActionKind::NoAction),
2620            "
2621        %expect-unused UnusedAllowed 'b'
2622        %token a b
2623        %start Start
2624        %%
2625        Unused: ;
2626        Start: ;
2627        UnusedAllowed: ;
2628        ",
2629        )
2630        .unwrap();
2631
2632        assert_eq!(
2633            ast.unused_symbols()
2634                .map(|sym_idx| { sym_idx.symbol(&ast) })
2635                .collect::<Vec<Symbol>>()
2636                .as_slice(),
2637            &[
2638                Symbol::Rule("Unused".to_string(), Span::new(101, 107)),
2639                Symbol::Token("a".to_string(), Span::new(57, 58))
2640            ]
2641        );
2642
2643        let ast = parse(
2644            YaccKind::Original(YaccOriginalActionKind::NoAction),
2645            "
2646        %start A
2647        %%
2648        A: ;
2649        Rec: Rec | ;
2650        ",
2651        )
2652        .unwrap();
2653        assert_eq!(
2654            ast.unused_symbols()
2655                .map(|sym_idx| sym_idx.symbol(&ast))
2656                .collect::<Vec<Symbol>>()
2657                .as_slice(),
2658            &[Symbol::Rule("Rec".to_string(), Span::new(50, 53))]
2659        );
2660
2661        let ast = parse(
2662            YaccKind::Original(YaccOriginalActionKind::NoAction),
2663            "
2664        %%
2665        A: 'a' | 'z' ;
2666        B: 'a' | 'c' ;
2667        ",
2668        )
2669        .unwrap();
2670        // Check that we warn on B and 'c' but not 'a'
2671        assert_eq!(
2672            ast.unused_symbols()
2673                .map(|sym_idx| sym_idx.symbol(&ast))
2674                .collect::<Vec<Symbol>>()
2675                .as_slice(),
2676            &[
2677                Symbol::Rule("B".to_string(), Span::new(43, 44)),
2678                Symbol::Token("c".to_string(), Span::new(53, 54))
2679            ]
2680        );
2681    }
2682
2683    #[test]
2684    fn test_percent_empty() {
2685        parse(
2686            YaccKind::Original(YaccOriginalActionKind::NoAction),
2687            r#"
2688        %token a
2689        %start A
2690        %%
2691        A: %empty | "a";
2692        "#,
2693        )
2694        .unwrap();
2695
2696        let src = r#"
2697        %token a b
2698        %start A
2699        %%
2700        A: "a" | %empty | "b";
2701        B: %empty | "b";
2702        "#;
2703        parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
2704
2705        let src = r#"
2706        %token a
2707        %start A
2708        %%
2709        A: %empty "a";
2710        "#;
2711        parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).expect_error_at_line_col(
2712            src,
2713            YaccGrammarErrorKind::NonEmptyProduction,
2714            5,
2715            12,
2716        );
2717
2718        let src = r#"
2719        %token a
2720        %start A
2721        %%
2722        A: "a" %empty;
2723        "#;
2724        parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).expect_error_at_line_col(
2725            src,
2726            YaccGrammarErrorKind::NonEmptyProduction,
2727            5,
2728            16,
2729        );
2730    }
2731
2732    #[test]
2733    fn test_action_successor() {
2734        let src = "
2735        %%
2736        A: B {} B;
2737        B: ;
2738        ";
2739        parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).expect_error_at_line_col(
2740            src,
2741            YaccGrammarErrorKind::ProductionNotTerminated,
2742            3,
2743            17,
2744        );
2745
2746        let src = "
2747        %%
2748        A: B B {};
2749        B: {} ;
2750        ";
2751        parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
2752    }
2753
2754    #[test]
2755    fn test_empty_production_spans_issue_473() {
2756        let empty_prod_conflicts = [
2757            (
2758                "%start Expr
2759%%
2760Expr: %empty | Factor;
2761Factor: ')' Expr ')';
2762",
2763                (0, Span::new(21, 27)),
2764            ),
2765            (
2766                "%start Expr
2767%%
2768Expr: | Factor;
2769Factor: ')' Expr ')';
2770",
2771                (0, Span::new(21, 21)),
2772            ),
2773            (
2774                "%start Expr
2775%%
2776Expr:| Factor;
2777Factor: ')' Expr ')';
2778",
2779                (0, Span::new(20, 20)),
2780            ),
2781            (
2782                "%start Expr
2783%%
2784Expr: Factor | %empty;
2785Factor: ')' Expr ')';
2786",
2787                (1, Span::new(30, 36)),
2788            ),
2789            (
2790                "%start Expr
2791%%
2792Expr: Factor | ;
2793Factor: ')' Expr ')';
2794",
2795                (1, Span::new(30, 30)),
2796            ),
2797            (
2798                "%start Expr
2799%%
2800Expr: Factor|;
2801Factor: ')' Expr ')';
2802",
2803                (1, Span::new(28, 28)),
2804            ),
2805        ];
2806
2807        for (i, (src, (empty_pidx, empty_span))) in empty_prod_conflicts.iter().enumerate() {
2808            eprintln!("{}", i);
2809            let ast = parse(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
2810            assert_eq!(
2811                ast.prods[ast.get_rule("Expr").unwrap().pidxs[*empty_pidx]],
2812                Production {
2813                    symbols: vec![],
2814                    precedence: None,
2815                    action: None,
2816                    prod_span: *empty_span,
2817                }
2818            );
2819        }
2820    }
2821}
cfgrammar/yacc/parser.rs

cfgrammar/yacc/
parser.rs
