1 //! Error reporting. For now very stupid and simplistic.
2
3 use collections::{set, Set};
4 use grammar::repr::*;
5 use itertools::Itertools;
6 use lr1::core::*;
7 use lr1::example::{Example, ExampleStyles, ExampleSymbol};
8 use lr1::first::FirstSets;
9 use lr1::lookahead::{Token, TokenSet};
10 use lr1::trace::Tracer;
11 use message::builder::{BodyCharacter, Builder, Character, MessageBuilder};
12 use message::Message;
13 use tls::Tls;
14
15 #[cfg(test)]
16 mod test;
17
report_error(grammar: &Grammar, error: &LR1TableConstructionError) -> Vec<Message>18 pub fn report_error(grammar: &Grammar, error: &LR1TableConstructionError) -> Vec<Message> {
19 let mut cx = ErrorReportingCx::new(grammar, &error.states, &error.conflicts);
20 cx.report_errors()
21 }
22
23 struct ErrorReportingCx<'cx, 'grammar: 'cx> {
24 grammar: &'grammar Grammar,
25 first_sets: FirstSets,
26 states: &'cx [LR1State<'grammar>],
27 conflicts: &'cx [LR1Conflict<'grammar>],
28 }
29
30 #[derive(Debug)]
31 enum ConflictClassification {
32 /// The grammar is ambiguous. This means we have two examples of
33 /// precisely the same set of symbols which can be reduced in two
34 /// distinct ways.
35 Ambiguity { action: Example, reduce: Example },
36
37 /// The grammar is ambiguous, and moreover it looks like a
38 /// precedence error. This means that the reduction is to a
39 /// nonterminal `T` and the shift is some symbol sandwiched
40 /// between two instances of `T`.
41 Precedence {
42 shift: Example,
43 reduce: Example,
44 nonterminal: NonterminalString,
45 },
46
47 /// Suggest inlining `nonterminal`. Makes sense if there are two
48 /// levels in the reduction tree in both examples, and the suffix
49 /// after the inner reduction is the same in all cases.
50 SuggestInline {
51 shift: Example,
52 reduce: Example,
53 nonterminal: NonterminalString,
54 },
55
56 /// Like the previous, but suggest replacing `nonterminal` with
57 /// `symbol?`. Makes sense if the thing to be inlined consists of
58 /// two alternatives, `X = symbol | ()`.
59 SuggestQuestion {
60 shift: Example,
61 reduce: Example,
62 nonterminal: NonterminalString,
63 symbol: Symbol,
64 },
65
66 /// Can't say much beyond that a conflict occurred.
67 InsufficientLookahead { action: Example, reduce: Example },
68
69 /// Really can't say *ANYTHING*.
70 Naive,
71 }
72
73 type TokenConflict<'grammar> = Conflict<'grammar, Token>;
74
75 impl<'cx, 'grammar> ErrorReportingCx<'cx, 'grammar> {
new( grammar: &'grammar Grammar, states: &'cx [LR1State<'grammar>], conflicts: &'cx [LR1Conflict<'grammar>], ) -> Self76 fn new(
77 grammar: &'grammar Grammar,
78 states: &'cx [LR1State<'grammar>],
79 conflicts: &'cx [LR1Conflict<'grammar>],
80 ) -> Self {
81 ErrorReportingCx {
82 grammar: grammar,
83 first_sets: FirstSets::new(grammar),
84 states: states,
85 conflicts: conflicts,
86 }
87 }
88
report_errors(&mut self) -> Vec<Message>89 fn report_errors(&mut self) -> Vec<Message> {
90 token_conflicts(self.conflicts)
91 .iter()
92 .map(|conflict| self.report_error(conflict))
93 .collect()
94 }
95
report_error(&mut self, conflict: &TokenConflict<'grammar>) -> Message96 fn report_error(&mut self, conflict: &TokenConflict<'grammar>) -> Message {
97 match self.classify(conflict) {
98 ConflictClassification::Ambiguity { action, reduce } => {
99 self.report_error_ambiguity(conflict, action, reduce)
100 }
101 ConflictClassification::Precedence {
102 shift,
103 reduce,
104 nonterminal,
105 } => self.report_error_precedence(conflict, shift, reduce, nonterminal),
106 ConflictClassification::SuggestInline {
107 shift,
108 reduce,
109 nonterminal,
110 } => self.report_error_suggest_inline(conflict, shift, reduce, nonterminal),
111 ConflictClassification::SuggestQuestion {
112 shift,
113 reduce,
114 nonterminal,
115 symbol,
116 } => self.report_error_suggest_question(conflict, shift, reduce, nonterminal, symbol),
117 ConflictClassification::InsufficientLookahead { action, reduce } => {
118 self.report_error_insufficient_lookahead(conflict, action, reduce)
119 }
120 ConflictClassification::Naive => self.report_error_naive(conflict),
121 }
122 }
123
report_error_ambiguity_core( &self, conflict: &TokenConflict<'grammar>, shift: Example, reduce: Example, ) -> Builder<BodyCharacter>124 fn report_error_ambiguity_core(
125 &self,
126 conflict: &TokenConflict<'grammar>,
127 shift: Example,
128 reduce: Example,
129 ) -> Builder<BodyCharacter> {
130 let styles = ExampleStyles::ambig();
131 MessageBuilder::new(conflict.production.span)
132 .heading()
133 .text("Ambiguous grammar detected")
134 .end()
135 .body()
136 .begin_lines()
137 .wrap_text("The following symbols can be reduced in two ways:")
138 .push(reduce.to_symbol_list(reduce.symbols.len(), styles))
139 .end()
140 .begin_lines()
141 .wrap_text("They could be reduced like so:")
142 .push(reduce.into_picture(styles))
143 .end()
144 .begin_lines()
145 .wrap_text("Alternatively, they could be reduced like so:")
146 .push(shift.into_picture(styles))
147 .end()
148 }
149
report_error_ambiguity( &self, conflict: &TokenConflict<'grammar>, shift: Example, reduce: Example, ) -> Message150 fn report_error_ambiguity(
151 &self,
152 conflict: &TokenConflict<'grammar>,
153 shift: Example,
154 reduce: Example,
155 ) -> Message {
156 self.report_error_ambiguity_core(conflict, shift, reduce)
157 .wrap_text(
158 "LALRPOP does not yet support ambiguous grammars. \
159 See the LALRPOP manual for advice on \
160 making your grammar unambiguous.",
161 )
162 .end()
163 .end()
164 }
165
report_error_precedence( &self, conflict: &TokenConflict<'grammar>, shift: Example, reduce: Example, nonterminal: NonterminalString, ) -> Message166 fn report_error_precedence(
167 &self,
168 conflict: &TokenConflict<'grammar>,
169 shift: Example,
170 reduce: Example,
171 nonterminal: NonterminalString,
172 ) -> Message {
173 self.report_error_ambiguity_core(conflict, shift, reduce)
174 .begin_wrap()
175 .text("Hint:")
176 .styled(Tls::session().hint_text)
177 .text("This looks like a precedence error related to")
178 .push(nonterminal)
179 .verbatimed()
180 .punctuated(".")
181 .text("See the LALRPOP manual for advice on encoding precedence.")
182 .end()
183 .end()
184 .end()
185 }
186
report_error_not_lr1_core( &self, conflict: &TokenConflict<'grammar>, action: Example, reduce: Example, ) -> Builder<BodyCharacter>187 fn report_error_not_lr1_core(
188 &self,
189 conflict: &TokenConflict<'grammar>,
190 action: Example,
191 reduce: Example,
192 ) -> Builder<BodyCharacter> {
193 let styles = ExampleStyles::new();
194 let builder = MessageBuilder::new(conflict.production.span)
195 .heading()
196 .text("Local ambiguity detected")
197 .end()
198 .body();
199
200 let builder = builder
201 .begin_lines()
202 .begin_wrap()
203 .text("The problem arises after having observed the following symbols")
204 .text("in the input:")
205 .end()
206 .push(if action.cursor >= reduce.cursor {
207 action.to_symbol_list(action.cursor, styles)
208 } else {
209 reduce.to_symbol_list(reduce.cursor, styles)
210 })
211 .begin_wrap();
212
213 let builder = match conflict.lookahead {
214 Token::Terminal(ref term) => builder
215 .text("At that point, if the next token is a")
216 .push(term.clone())
217 .verbatimed()
218 .styled(Tls::session().cursor_symbol)
219 .punctuated(","),
220 Token::Error => builder.text("If an error has been found,"),
221 Token::EOF => builder.text("If the end of the input is reached,"),
222 };
223
224 let builder = builder
225 .text("then the parser can proceed in two different ways.")
226 .end()
227 .end();
228
229 let builder = self.describe_reduce(builder, styles, conflict.production, reduce, "First");
230
231 match conflict.action {
232 Action::Shift(ref lookahead, _) => {
233 self.describe_shift(builder, styles, lookahead.clone(), action, "Alternatively")
234 }
235 Action::Reduce(production) => {
236 self.describe_reduce(builder, styles, production, action, "Alternatively")
237 }
238 }
239 }
240
describe_shift<C: Character>( &self, builder: Builder<C>, styles: ExampleStyles, lookahead: TerminalString, example: Example, intro_word: &str, ) -> Builder<C>241 fn describe_shift<C: Character>(
242 &self,
243 builder: Builder<C>,
244 styles: ExampleStyles,
245 lookahead: TerminalString,
246 example: Example,
247 intro_word: &str,
248 ) -> Builder<C> {
249 // A shift example looks like:
250 //
251 // ...p1 ...p2 (*) L ...s2 ...s1
252 // | | | |
253 // | +-NT1-----------+ |
254 // | |
255 // | ... |
256 // | |
257 // +-NT2-----------------------+
258
259 let nt1 = example.reductions[0].nonterminal.clone();
260
261 builder
262 .begin_lines()
263 .begin_wrap()
264 .text(intro_word)
265 .punctuated(",")
266 .text("the parser could shift the")
267 .push(lookahead)
268 .verbatimed()
269 .text("token and later use it to construct a")
270 .push(nt1)
271 .verbatimed()
272 .punctuated(".")
273 .text("This might then yield a parse tree like")
274 .end()
275 .push(example.into_picture(styles))
276 .end()
277 }
278
describe_reduce<C: Character>( &self, builder: Builder<C>, styles: ExampleStyles, production: &Production, example: Example, intro_word: &str, ) -> Builder<C>279 fn describe_reduce<C: Character>(
280 &self,
281 builder: Builder<C>,
282 styles: ExampleStyles,
283 production: &Production,
284 example: Example,
285 intro_word: &str,
286 ) -> Builder<C> {
287 builder
288 .begin_lines()
289 .begin_wrap()
290 .text(intro_word)
291 .punctuated(",")
292 .text("the parser could execute the production at")
293 .push(production.span)
294 .punctuated(",")
295 .text("which would consume the top")
296 .text(production.symbols.len())
297 .text("token(s) from the stack")
298 .text("and produce a")
299 .push(production.nonterminal.clone())
300 .verbatimed()
301 .punctuated(".")
302 .text("This might then yield a parse tree like")
303 .end()
304 .push(example.into_picture(styles))
305 .end()
306 }
307
report_error_suggest_inline( &self, conflict: &TokenConflict<'grammar>, shift: Example, reduce: Example, nonterminal: NonterminalString, ) -> Message308 fn report_error_suggest_inline(
309 &self,
310 conflict: &TokenConflict<'grammar>,
311 shift: Example,
312 reduce: Example,
313 nonterminal: NonterminalString,
314 ) -> Message {
315 let builder = self.report_error_not_lr1_core(conflict, shift, reduce);
316
317 builder
318 .begin_wrap()
319 .text("Hint:")
320 .styled(Tls::session().hint_text)
321 .text("It appears you could resolve this problem by adding")
322 .text("the annotation `#[inline]` to the definition of")
323 .push(nonterminal)
324 .verbatimed()
325 .punctuated(".")
326 .text("For more information, see the section on inlining")
327 .text("in the LALRPOP manual.")
328 .end()
329 .end()
330 .end()
331 }
332
report_error_suggest_question( &self, conflict: &TokenConflict<'grammar>, shift: Example, reduce: Example, nonterminal: NonterminalString, symbol: Symbol, ) -> Message333 fn report_error_suggest_question(
334 &self,
335 conflict: &TokenConflict<'grammar>,
336 shift: Example,
337 reduce: Example,
338 nonterminal: NonterminalString,
339 symbol: Symbol,
340 ) -> Message {
341 let builder = self.report_error_not_lr1_core(conflict, shift, reduce);
342
343 builder
344 .begin_wrap()
345 .text("Hint:")
346 .styled(Tls::session().hint_text)
347 .text("It appears you could resolve this problem by replacing")
348 .text("uses of")
349 .push(nonterminal.clone())
350 .verbatimed()
351 .text("with")
352 .text(symbol) // intentionally disable coloring here, looks better
353 .adjacent_text("`", "?`")
354 .text(
355 "(or, alternatively, by adding the annotation `#[inline]` \
356 to the definition of",
357 )
358 .push(nonterminal)
359 .punctuated(").")
360 .text("For more information, see the section on inlining")
361 .text("in the LALROP manual.")
362 .end()
363 .end()
364 .end()
365 }
366
report_error_insufficient_lookahead( &self, conflict: &TokenConflict<'grammar>, action: Example, reduce: Example, ) -> Message367 fn report_error_insufficient_lookahead(
368 &self,
369 conflict: &TokenConflict<'grammar>,
370 action: Example,
371 reduce: Example,
372 ) -> Message {
373 // The reduce example will look something like:
374 //
375 //
376 // ...p1 ...p2 (*) L ...s2 ...s1
377 // | | | |
378 // | +-NT1-----------+ |
379 // | | | |
380 // | +-...-----------+ |
381 // | | | |
382 // | +-NTn-----------+ |
383 // | |
384 // +-NTn+1---------------------+
385 //
386 // To solve the conflict, essentially, the user needs to
387 // modify the grammar so that `NTn` does not appear with `L`
388 // in its follow-set. How to guide them in this?
389
390 let builder = self.report_error_not_lr1_core(conflict, action, reduce);
391
392 builder
393 .wrap_text(
394 "See the LALRPOP manual for advice on \
395 making your grammar LR(1).",
396 )
397 .end()
398 .end()
399 }
400
401 /// Naive error reporting. This is a fallback path which (I think)
402 /// never actually executes.
report_error_naive(&self, conflict: &TokenConflict<'grammar>) -> Message403 fn report_error_naive(&self, conflict: &TokenConflict<'grammar>) -> Message {
404 let mut builder = MessageBuilder::new(conflict.production.span)
405 .heading()
406 .text("Conflict detected")
407 .end()
408 .body()
409 .begin_lines()
410 .wrap_text("when in this state:")
411 .indented();
412 for item in self.states[conflict.state.0].items.vec.iter() {
413 builder = builder.text(format!("{:?}", item));
414 }
415 let mut builder = builder
416 .end()
417 .begin_wrap()
418 .text(format!("and looking at a token `{:?}`", conflict.lookahead))
419 .text("we can reduce to a")
420 .push(conflict.production.nonterminal.clone())
421 .verbatimed();
422 builder = match conflict.action {
423 Action::Shift(..) => builder.text("but we can also shift"),
424 Action::Reduce(prod) => builder
425 .text("but we can also reduce to a")
426 .text(prod.nonterminal.clone())
427 .verbatimed(),
428 };
429 builder.end().end().end()
430 }
431
classify(&mut self, conflict: &TokenConflict<'grammar>) -> ConflictClassification432 fn classify(&mut self, conflict: &TokenConflict<'grammar>) -> ConflictClassification {
433 // Find examples from the conflicting action (either a shift
434 // or a reduce).
435 let mut action_examples = match conflict.action {
436 Action::Shift(..) => self.shift_examples(conflict),
437 Action::Reduce(production) => {
438 self.reduce_examples(conflict.state, production, conflict.lookahead.clone())
439 }
440 };
441
442 // Find examples from the conflicting reduce.
443 let mut reduce_examples = self.reduce_examples(
444 conflict.state,
445 conflict.production,
446 conflict.lookahead.clone(),
447 );
448
449 // Prefer shorter examples to longer ones.
450 action_examples.sort_by(|e, f| e.symbols.len().cmp(&f.symbols.len()));
451 reduce_examples.sort_by(|e, f| e.symbols.len().cmp(&f.symbols.len()));
452
453 // This really shouldn't happen, but if we've failed to come
454 // up with examples, then report a "naive" error.
455 if action_examples.is_empty() || reduce_examples.is_empty() {
456 return ConflictClassification::Naive;
457 }
458
459 if let Some(classification) =
460 self.try_classify_ambiguity(conflict, &action_examples, &reduce_examples)
461 {
462 return classification;
463 }
464
465 if let Some(classification) =
466 self.try_classify_question(conflict, &action_examples, &reduce_examples)
467 {
468 return classification;
469 }
470
471 if let Some(classification) =
472 self.try_classify_inline(conflict, &action_examples, &reduce_examples)
473 {
474 return classification;
475 }
476
477 // Give up. Just grab an example from each and pair them up.
478 // If there aren't even two examples, something's pretty
479 // bogus, but we'll just call it naive.
480 action_examples
481 .into_iter()
482 .zip(reduce_examples)
483 .next()
484 .map(
485 |(action, reduce)| ConflictClassification::InsufficientLookahead {
486 action: action,
487 reduce: reduce,
488 },
489 )
490 .unwrap_or(ConflictClassification::Naive)
491 }
492
try_classify_ambiguity( &self, conflict: &TokenConflict<'grammar>, action_examples: &[Example], reduce_examples: &[Example], ) -> Option<ConflictClassification>493 fn try_classify_ambiguity(
494 &self,
495 conflict: &TokenConflict<'grammar>,
496 action_examples: &[Example],
497 reduce_examples: &[Example],
498 ) -> Option<ConflictClassification> {
499 action_examples
500 .iter()
501 .cartesian_product(reduce_examples)
502 .filter(|&(action, reduce)| action.symbols == reduce.symbols)
503 .filter(|&(action, reduce)| action.cursor == reduce.cursor)
504 .map(|(action, reduce)| {
505 // Consider whether to call this a precedence
506 // error. We do this if we are stuck between reducing
507 // `T = T S T` and shifting `S`.
508 if let Action::Shift(ref term, _) = conflict.action {
509 let nt = &conflict.production.nonterminal;
510 if conflict.production.symbols.len() == 3
511 && conflict.production.symbols[0] == Symbol::Nonterminal(nt.clone())
512 && conflict.production.symbols[1] == Symbol::Terminal(term.clone())
513 && conflict.production.symbols[2] == Symbol::Nonterminal(nt.clone())
514 {
515 return ConflictClassification::Precedence {
516 shift: action.clone(),
517 reduce: reduce.clone(),
518 nonterminal: nt.clone(),
519 };
520 }
521 }
522 ConflictClassification::Ambiguity {
523 action: action.clone(),
524 reduce: reduce.clone(),
525 }
526 })
527 .next()
528 }
529
try_classify_question( &self, conflict: &TokenConflict<'grammar>, action_examples: &[Example], reduce_examples: &[Example], ) -> Option<ConflictClassification>530 fn try_classify_question(
531 &self,
532 conflict: &TokenConflict<'grammar>,
533 action_examples: &[Example],
534 reduce_examples: &[Example],
535 ) -> Option<ConflictClassification> {
536 // If we get a shift/reduce conflict and the reduce
537 // is of a nonterminal like:
538 //
539 // T = { () | U }
540 //
541 // then suggest replacing T with U?. I'm being a bit lenient
542 // here since I do not KNOW that it will help, but it often
543 // does, and it's better style anyhow.
544
545 if let Action::Reduce(_) = conflict.action {
546 return None;
547 }
548
549 debug!(
550 "try_classify_question: action_examples={:?}",
551 action_examples
552 );
553 debug!(
554 "try_classify_question: reduce_examples={:?}",
555 reduce_examples
556 );
557
558 let nt = &conflict.production.nonterminal;
559 let nt_productions = self.grammar.productions_for(nt);
560 if nt_productions.len() == 2 {
561 for &(i, j) in &[(0, 1), (1, 0)] {
562 if nt_productions[i].symbols.is_empty() && nt_productions[j].symbols.len() == 1 {
563 return Some(ConflictClassification::SuggestQuestion {
564 shift: action_examples[0].clone(),
565 reduce: reduce_examples[0].clone(),
566 nonterminal: nt.clone(),
567 symbol: nt_productions[j].symbols[0].clone(),
568 });
569 }
570 }
571 }
572
573 None
574 }
575
try_classify_inline( &self, conflict: &TokenConflict<'grammar>, action_examples: &[Example], reduce_examples: &[Example], ) -> Option<ConflictClassification>576 fn try_classify_inline(
577 &self,
578 conflict: &TokenConflict<'grammar>,
579 action_examples: &[Example],
580 reduce_examples: &[Example],
581 ) -> Option<ConflictClassification> {
582 // Inlining can help resolve a shift/reduce conflict because
583 // it defers the need to reduce. In particular, if we inlined
584 // all the reductions up until the last one, then we would be
585 // able to *shift* the lookahead instead of having to reduce.
586 // This can be helpful if we can see that shifting would let
587 // us delay reducing until the lookahead diverges.
588
589 // Only applicable to shift/reduce:
590 if let Action::Reduce(_) = conflict.action {
591 return None;
592 }
593
594 // FIXME: The logic here finds the first example where inline
595 // would help; but maybe we want to restrict it to cases
596 // where inlining would help *all* the examples...?
597
598 action_examples
599 .iter()
600 .cartesian_product(reduce_examples)
601 .filter_map(|(shift, reduce)| {
602 if self.try_classify_inline_example(shift, reduce) {
603 let nt = &reduce.reductions[0].nonterminal;
604 Some(ConflictClassification::SuggestInline {
605 shift: shift.clone(),
606 reduce: reduce.clone(),
607 nonterminal: nt.clone(),
608 })
609 } else {
610 None
611 }
612 })
613 .next()
614 }
615
try_classify_inline_example<'ex>(&self, shift: &Example, reduce: &Example) -> bool616 fn try_classify_inline_example<'ex>(&self, shift: &Example, reduce: &Example) -> bool {
617 debug!("try_classify_inline_example({:?}, {:?})", shift, reduce);
618
619 // In the case of shift, the example will look like
620 //
621 // ```
622 // ... ... (*) L ...s1 ...
623 // | | | |
624 // | +-R0----------+ |
625 // | ... |
626 // +-Rn------------------+
627 // ```
628 //
629 // We want to extract the symbols ...s1: these are the
630 // things we are able to shift before being forced to
631 // make our next hard decision (to reduce R0 or not).
632 let shift_upcoming = &shift.symbols[shift.cursor + 1..shift.reductions[0].end];
633 debug!(
634 "try_classify_inline_example: shift_upcoming={:?}",
635 shift_upcoming
636 );
637
638 // For the reduce, the example might look like
639 //
640 // ```
641 // ... ... (*) ...s ...
642 // | | | | |
643 // | | +-R0-+ |
644 // | | ... | |
645 // | +--Ri--+ |
646 // | ... |
647 // +-R(i+1)----------+
648 // ```
649 //
650 // where Ri is the last reduction that requires
651 // shifting no additional symbols. In this case, if we
652 // inlined R0...Ri, then we know we can shift L.
653 let r0_end = reduce.reductions[0].end;
654 let i = reduce.reductions.iter().position(|r| r.end != r0_end);
655 let i = match i {
656 Some(v) => v,
657 None => return false,
658 };
659 let ri = &reduce.reductions[i];
660 let reduce_upcoming = &reduce.symbols[r0_end..ri.end];
661 debug!(
662 "try_classify_inline_example: reduce_upcoming={:?} i={:?}",
663 reduce_upcoming, i
664 );
665
666 // For now, we only suggest inlining a single nonterminal,
667 // mostly because I am too lazy to weak the suggestion struct
668 // and error messages (but the rest of the code below doesn't
669 // make this assumption for the most part).
670 if i != 1 {
671 return false;
672 }
673
674 // Make sure that all the things we are suggesting inlining
675 // are distinct so that we are not introducing a cycle.
676 let mut duplicates = set();
677 if reduce.reductions[0..i + 1]
678 .iter()
679 .any(|r| !duplicates.insert(r.nonterminal.clone()))
680 {
681 return false;
682 }
683
684 // Compare the two suffixes to see whether they
685 // diverge at some point.
686 shift_upcoming
687 .iter()
688 .zip(reduce_upcoming)
689 .filter_map(|(shift_sym, reduce_sym)| match (shift_sym, reduce_sym) {
690 (&ExampleSymbol::Symbol(ref shift_sym), &ExampleSymbol::Symbol(ref reduce_sym)) => {
691 if shift_sym == reduce_sym {
692 // same symbol on both; we'll be able to shift them
693 None
694 } else {
695 // different symbols: for this to work, must
696 // have disjoint first sets. Note that we
697 // consider a suffix matching epsilon to be
698 // potentially overlapping, though we could
699 // supply the actual lookahead for more precision.
700 let shift_first = self.first_sets.first0(&[shift_sym.clone()]);
701 let reduce_first = self.first_sets.first0(&[reduce_sym.clone()]);
702 if shift_first.is_disjoint(&reduce_first) {
703 Some(true)
704 } else {
705 Some(false)
706 }
707 }
708 }
709 _ => {
710 // we don't expect to encounter any
711 // epsilons, I don't think, because those
712 // only occur with an empty reduce at the
713 // top level
714 Some(false)
715 }
716 })
717 .next()
718 .unwrap_or(false)
719 }
720
shift_examples(&self, conflict: &TokenConflict<'grammar>) -> Vec<Example>721 fn shift_examples(&self, conflict: &TokenConflict<'grammar>) -> Vec<Example> {
722 log!(Tls::session(), Verbose, "Gathering shift examples");
723 let state = &self.states[conflict.state.0];
724 let conflicting_items = self.conflicting_shift_items(state, conflict);
725 conflicting_items
726 .into_iter()
727 .flat_map(|item| {
728 let tracer = Tracer::new(&self.first_sets, self.states);
729 let shift_trace = tracer.backtrace_shift(conflict.state, item);
730 let local_examples: Vec<Example> = shift_trace.lr0_examples(item).collect();
731 local_examples
732 })
733 .collect()
734 }
735
reduce_examples( &self, state: StateIndex, production: &'grammar Production, lookahead: Token, ) -> Vec<Example>736 fn reduce_examples(
737 &self,
738 state: StateIndex,
739 production: &'grammar Production,
740 lookahead: Token,
741 ) -> Vec<Example> {
742 log!(Tls::session(), Verbose, "Gathering reduce examples");
743 let item = Item {
744 production: production,
745 index: production.symbols.len(),
746 lookahead: TokenSet::from(lookahead),
747 };
748 let tracer = Tracer::new(&self.first_sets, self.states);
749 let reduce_trace = tracer.backtrace_reduce(state, item.to_lr0());
750 reduce_trace.lr1_examples(&self.first_sets, &item).collect()
751 }
752
conflicting_shift_items( &self, state: &LR1State<'grammar>, conflict: &TokenConflict<'grammar>, ) -> Set<LR0Item<'grammar>>753 fn conflicting_shift_items(
754 &self,
755 state: &LR1State<'grammar>,
756 conflict: &TokenConflict<'grammar>,
757 ) -> Set<LR0Item<'grammar>> {
758 // Lookahead must be a terminal, not EOF.
759 // Find an item J like `Bar = ... (*) L ...`.
760 let lookahead = Symbol::Terminal(conflict.lookahead.unwrap_terminal().clone());
761 state
762 .items
763 .vec
764 .iter()
765 .filter(|i| i.can_shift())
766 .filter(|i| i.production.symbols[i.index] == lookahead)
767 .map(|i| i.to_lr0())
768 .collect()
769 }
770 }
771
token_conflicts<'grammar>( conflicts: &[Conflict<'grammar, TokenSet>], ) -> Vec<TokenConflict<'grammar>>772 fn token_conflicts<'grammar>(
773 conflicts: &[Conflict<'grammar, TokenSet>],
774 ) -> Vec<TokenConflict<'grammar>> {
775 conflicts
776 .iter()
777 .flat_map(|conflict| {
778 conflict.lookahead.iter().map(move |token| Conflict {
779 state: conflict.state,
780 lookahead: token,
781 production: conflict.production,
782 action: conflict.action.clone(),
783 })
784 })
785 .collect()
786 }
787
788 //fn choose_example<'grammar>(states: &[State<'grammar>],
789 // lookahead: Token,
790 // conflict: &TokenConflict<'grammar>)
791 //{
792 // // Whenever we have a conflict in state S, there is always:
793 // // - a given lookahead L that permits some reduction, due to
794 // // an item I like `Foo = ... (*) [L]`
795 // // - another action that conflicts with R1.
796 // //
797 // // The backtrace code can give context to this item `I`, but the
798 // // problem is that it often results in many different contexts,
799 // // and we need to try and narrow those down to the one that will
800 // // help the user understand the problem.
801 // //
802 // // For that, we turn to the conflicting action, which can either be
803 // // a shift or reduce. Let's consider those two cases.
804 // //
805 // // ### Shift
806 // //
807 // // If the conflicting action is a shift, then there is at least
808 // // one item J in the state S like `Bar = ... (*) L ...`. We can
809 // // produce a backtrace from J and enumerate examples. We want to
810 // // find a pair of examples from I and J that share a common
811 // // prefix.
812 // //
813 // // ### Reduce
814 // //
815 // // If the conflicting action is a reduce, then there is at least
816 // // one item J in S like `Bar = ... (*) [L]`. We can produce a
817 // // backtrace for J and then search for an example that shares a
818 // // common prefix.
819 //
820 //}
821 //
822 //fn conflicting_item<'grammar>(state: &State<'grammar>,
823 // lookahead: Token,
824 // conflict: &TokenConflict<'grammar>)
825 // -> Item<'grammar>
826 //{
827 // match conflict.action {
828 // Action::Shift(_) => {
829 // }
830 // Action::Reduce(production) => {
831 // // Must be at least some other item J in S like `Bar = ... (*) [L]`.
832 // state.items.vec.iter()
833 // .filter(|i| i.can_reduce())
834 // .filter(|i| i.lookahead == lookahead)
835 // .filter(|i| i.production == production)
836 // .cloned()
837 // .next()
838 // .unwrap()
839 // }
840 // }
841 //}
842