1#![allow(clippy::derive_partial_eq_without_eq)]
2use std::{cell::RefCell, collections::HashMap, fmt::Write, str::FromStr};
3
4#[cfg(feature = "bincode")]
5use bincode::{Decode, Encode};
6use num_traits::{AsPrimitive, PrimInt, Unsigned};
7#[cfg(feature = "serde")]
8use serde::{Deserialize, Serialize};
9use vob::Vob;
10
11use super::{
12 ast,
13 firsts::YaccFirsts,
14 follows::YaccFollows,
15 parser::{YaccGrammarError, YaccGrammarResult},
16 YaccKind,
17};
18use crate::{PIdx, RIdx, SIdx, Span, Symbol, TIdx};
19
20const START_RULE: &str = "^";
21const IMPLICIT_RULE: &str = "~";
22const IMPLICIT_START_RULE: &str = "^~";
23
24pub type PrecedenceLevel = u64;
25#[derive(Clone, Copy, Debug, PartialEq)]
26#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
27#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
28pub struct Precedence {
29 pub level: PrecedenceLevel,
30 pub kind: AssocKind,
31}
32
33#[derive(Clone, Copy, Debug, PartialEq)]
34#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
35#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
36pub enum AssocKind {
37 Left,
38 Right,
39 Nonassoc,
40}
41
42#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
45#[cfg_attr(feature = "bincode", derive(Encode))]
46pub struct YaccGrammar<StorageT = u32> {
47 rules_len: RIdx<StorageT>,
49 rule_names: Box<[(String, Span)]>,
51 token_names: Box<[Option<(Span, String)>]>,
54 token_precs: Box<[Option<Precedence>]>,
56 token_epp: Box<[Option<String>]>,
62 tokens_len: TIdx<StorageT>,
64 eof_token_idx: TIdx<StorageT>,
66 prods_len: PIdx<StorageT>,
68 start_prod: PIdx<StorageT>,
70 prods: Box<[Box<[Symbol<StorageT>]>]>,
72 rules_prods: Box<[Box<[PIdx<StorageT>]>]>,
76 prods_rules: Box<[RIdx<StorageT>]>,
78 prod_precs: Box<[Option<Precedence>]>,
80 implicit_rule: Option<RIdx<StorageT>>,
83 actions: Box<[Option<String>]>,
85 parse_param: Option<(String, String)>,
87 programs: Option<String>,
89 actiontypes: Box<[Option<String>]>,
91 avoid_insert: Option<Vob>,
93 expect: Option<usize>,
95 expectrr: Option<usize>,
97}
98
99#[cfg(feature = "bincode")]
110impl<StorageT, __Context> Decode<__Context> for YaccGrammar<StorageT>
111where
112 StorageT: Decode<__Context> + 'static,
113{
114 fn decode<__D: bincode::de::Decoder<Context = __Context>>(
115 decoder: &mut __D,
116 ) -> Result<Self, bincode::error::DecodeError> {
117 Ok(Self {
118 rules_len: Decode::decode(decoder)?,
119 rule_names: Decode::decode(decoder)?,
120 token_names: Decode::decode(decoder)?,
121 token_precs: Decode::decode(decoder)?,
122 token_epp: Decode::decode(decoder)?,
123 tokens_len: Decode::decode(decoder)?,
124 eof_token_idx: Decode::decode(decoder)?,
125 prods_len: Decode::decode(decoder)?,
126 start_prod: Decode::decode(decoder)?,
127 prods: Decode::decode(decoder)?,
128 rules_prods: Decode::decode(decoder)?,
129 prods_rules: Decode::decode(decoder)?,
130 prod_precs: Decode::decode(decoder)?,
131 implicit_rule: Decode::decode(decoder)?,
132 actions: Decode::decode(decoder)?,
133 parse_param: Decode::decode(decoder)?,
134 programs: Decode::decode(decoder)?,
135 actiontypes: Decode::decode(decoder)?,
136 avoid_insert: Decode::decode(decoder)?,
137 expect: Decode::decode(decoder)?,
138 expectrr: Decode::decode(decoder)?,
139 })
140 }
141}
142
143#[cfg(feature = "bincode")]
148impl<'__de, StorageT, __Context> bincode::BorrowDecode<'__de, __Context> for YaccGrammar<StorageT>
149where
150 StorageT: bincode::de::BorrowDecode<'__de, __Context> + '__de,
151{
152 fn borrow_decode<__D: ::bincode::de::BorrowDecoder<'__de, Context = __Context>>(
153 decoder: &mut __D,
154 ) -> Result<Self, bincode::error::DecodeError> {
155 Ok(Self {
156 rules_len: bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
157 rule_names: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
158 token_names: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
159 token_precs: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
160 token_epp: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
161 tokens_len: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
162 eof_token_idx: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
163 prods_len: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
164 start_prod: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
165 prods: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
166 rules_prods: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
167 prods_rules: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
168 prod_precs: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
169 implicit_rule: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
170 actions: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
171 parse_param: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
172 programs: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
173 actiontypes: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
174 avoid_insert: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
175 expect: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
176 expectrr: ::bincode::BorrowDecode::<'_, __Context>::borrow_decode(decoder)?,
177 })
178 }
179}
180
181impl YaccGrammar<u32> {
185 pub fn new(yk: YaccKind, s: &str) -> YaccGrammarResult<Self> {
186 YaccGrammar::new_with_storaget(yk, s)
187 }
188}
189
190impl<StorageT: 'static + PrimInt + Unsigned> FromStr for YaccGrammar<StorageT>
191where
192 usize: AsPrimitive<StorageT>,
193{
194 type Err = Vec<YaccGrammarError>;
195 fn from_str(s: &str) -> YaccGrammarResult<Self> {
196 let ast_validation = ast::ASTWithValidityInfo::from_str(s)?;
197 Self::new_from_ast_with_validity_info(&ast_validation)
198 }
199}
200
201impl<StorageT: 'static + PrimInt + Unsigned> YaccGrammar<StorageT>
202where
203 usize: AsPrimitive<StorageT>,
204{
205 pub fn new_with_storaget(yk: YaccKind, s: &str) -> YaccGrammarResult<Self> {
213 let ast_validation = ast::ASTWithValidityInfo::new(yk, s);
214 Self::new_from_ast_with_validity_info(&ast_validation)
215 }
216
217 pub fn new_from_ast_with_validity_info(
218 ast_validation: &ast::ASTWithValidityInfo,
219 ) -> YaccGrammarResult<Self> {
220 if !ast_validation.is_valid() {
221 return Err(ast_validation.errors().to_owned());
222 }
223 let ast = ast_validation.ast();
224 if ast.rules.len() > num_traits::cast(StorageT::max_value()).unwrap() {
227 panic!("StorageT is not big enough to store this grammar's rules.");
228 }
229 if ast.tokens.len() > num_traits::cast(StorageT::max_value()).unwrap() {
230 panic!("StorageT is not big enough to store this grammar's tokens.");
231 }
232 if ast.prods.len() > num_traits::cast(StorageT::max_value()).unwrap() {
233 panic!("StorageT is not big enough to store this grammar's productions.");
234 }
235 for p in &ast.prods {
236 if p.symbols.len() > num_traits::cast(StorageT::max_value()).unwrap() {
237 panic!("StorageT is not big enough to store the symbols of at least one of this grammar's productions.");
238 }
239 }
240
241 let mut rule_names: Vec<(String, Span)> = Vec::with_capacity(ast.rules.len() + 1);
242
243 let mut start_rule = START_RULE.to_string();
248 while ast.rules.get(&start_rule).is_some() {
249 start_rule += START_RULE;
250 }
251 rule_names.push((start_rule.clone(), Span::new(0, 0)));
252
253 let implicit_rule;
254 let implicit_start_rule;
255 match ast_validation.yacc_kind() {
256 YaccKind::Original(_) | YaccKind::Grmtools => {
257 implicit_rule = None;
258 implicit_start_rule = None;
259 }
260 YaccKind::Eco => {
261 if ast.implicit_tokens.is_some() {
262 let mut n1 = IMPLICIT_RULE.to_string();
263 while ast.rules.get(&n1).is_some() {
264 n1 += IMPLICIT_RULE;
265 }
266 rule_names.push((n1.clone(), Span::new(0, 0)));
267 implicit_rule = Some(n1);
268 let mut n2 = IMPLICIT_START_RULE.to_string();
269 while ast.rules.get(&n2).is_some() {
270 n2 += IMPLICIT_START_RULE;
271 }
272 rule_names.push((n2.clone(), Span::new(0, 0)));
273 implicit_start_rule = Some(n2);
274 } else {
275 implicit_rule = None;
276 implicit_start_rule = None;
277 }
278 }
279 };
280
281 for (
282 k,
283 ast::Rule {
284 name: (_, name_span),
285 ..
286 },
287 ) in &ast.rules
288 {
289 rule_names.push((k.clone(), *name_span));
290 }
291 let mut rules_prods: Vec<Vec<PIdx<StorageT>>> = Vec::with_capacity(rule_names.len());
292 let mut rule_map = HashMap::<String, RIdx<StorageT>>::new();
293 for (i, (v, _)) in rule_names.iter().enumerate() {
294 rules_prods.push(Vec::new());
295 rule_map.insert(v.clone(), RIdx(i.as_()));
296 }
297
298 let mut token_names: Vec<Option<(Span, String)>> = Vec::with_capacity(ast.tokens.len() + 1);
299 let mut token_precs: Vec<Option<Precedence>> = Vec::with_capacity(ast.tokens.len() + 1);
300 let mut token_epp: Vec<Option<String>> = Vec::with_capacity(ast.tokens.len() + 1);
301 for (i, k) in ast.tokens.iter().enumerate() {
302 token_names.push(Some((ast.spans[i], k.clone())));
303 token_precs.push(ast.precs.get(k).map(|(prec, _)| prec).cloned());
304 token_epp.push(Some(
305 ast.epp.get(k).map(|(_, (s, _))| s).unwrap_or(k).clone(),
306 ));
307 }
308 let eof_token_idx = TIdx(token_names.len().as_());
309 token_names.push(None);
310 token_precs.push(None);
311 token_epp.push(None);
312 let mut token_map = HashMap::<String, TIdx<StorageT>>::new();
313 for (i, v) in token_names.iter().enumerate() {
314 if let Some((_, n)) = v.as_ref() {
315 token_map.insert(n.clone(), TIdx(i.as_()));
316 }
317 }
318
319 let mut prods = vec![None; ast.prods.len()];
323 let mut prod_precs: Vec<Option<Option<Precedence>>> = vec![None; ast.prods.len()];
324 let mut prods_rules = vec![None; ast.prods.len()];
325 let mut actions = vec![None; ast.prods.len()];
326 let mut actiontypes = vec![None; rule_names.len()];
327 let (start_name, _) = ast.start.as_ref().unwrap();
328 for (astrulename, _) in &rule_names {
329 let ridx = rule_map[astrulename];
330 if astrulename == &start_rule {
331 rules_prods[usize::from(ridx)].push(PIdx(prods.len().as_()));
334 let start_prod = match implicit_start_rule {
335 None => {
336 vec![Symbol::Rule(rule_map[start_name])]
338 }
339 Some(ref s) => {
340 vec![Symbol::Rule(rule_map[s])]
344 }
345 };
346 prods.push(Some(start_prod));
347 prod_precs.push(Some(None));
348 prods_rules.push(Some(ridx));
349 actions.push(None);
350 continue;
351 } else if implicit_start_rule.as_ref() == Some(astrulename) {
352 rules_prods[usize::from(rule_map[astrulename])].push(PIdx(prods.len().as_()));
356 prods.push(Some(vec![
357 Symbol::Rule(rule_map[implicit_rule.as_ref().unwrap()]),
358 Symbol::Rule(rule_map[start_name]),
359 ]));
360 prod_precs.push(Some(None));
361 prods_rules.push(Some(ridx));
362 continue;
363 } else if implicit_rule.as_ref() == Some(astrulename) {
364 let implicit_prods = &mut rules_prods[usize::from(rule_map[astrulename])];
366 for (t, _) in ast.implicit_tokens.as_ref().unwrap().iter() {
368 implicit_prods.push(PIdx(prods.len().as_()));
369 prods.push(Some(vec![Symbol::Token(token_map[t]), Symbol::Rule(ridx)]));
370 prod_precs.push(Some(None));
371 prods_rules.push(Some(ridx));
372 }
373 implicit_prods.push(PIdx(prods.len().as_()));
375 prods.push(Some(vec![]));
376 prod_precs.push(Some(None));
377 prods_rules.push(Some(ridx));
378 continue;
379 } else {
380 actiontypes[usize::from(ridx)] = ast.rules[astrulename].actiont.clone();
381 }
382
383 let rule = &mut rules_prods[usize::from(ridx)];
384 for &pidx in &ast.rules[astrulename].pidxs {
385 let astprod = &ast.prods[pidx];
386 let mut prod = Vec::with_capacity(astprod.symbols.len());
387 for astsym in &astprod.symbols {
388 match *astsym {
389 ast::Symbol::Rule(ref n, _) => {
390 prod.push(Symbol::Rule(rule_map[n]));
391 }
392 ast::Symbol::Token(ref n, _) => {
393 prod.push(Symbol::Token(token_map[n]));
394 if let Some(implicit_rule) = &implicit_rule {
395 prod.push(Symbol::Rule(rule_map[implicit_rule]));
396 }
397 }
398 };
399 }
400 let mut prec = None;
401 if let Some(ref n) = astprod.precedence {
402 prec = Some(ast.precs[n]);
403 } else {
404 for astsym in astprod.symbols.iter().rev() {
405 if let ast::Symbol::Token(ref n, _) = *astsym {
406 if let Some(p) = ast.precs.get(n) {
407 prec = Some(*p);
408 }
409 break;
410 }
411 }
412 }
413 (*rule).push(PIdx(pidx.as_()));
414 prods[pidx] = Some(prod);
415 prod_precs[pidx] = Some(prec.map(|(prec, _)| prec));
416 prods_rules[pidx] = Some(ridx);
417 if let Some(ref s) = astprod.action {
418 actions[pidx] = Some(s.clone());
419 }
420 }
421 }
422
423 let avoid_insert = if let Some(ai) = &ast.avoid_insert {
424 let mut aiv = Vob::from_elem(false, token_names.len());
425 for n in ai.keys() {
426 aiv.set(usize::from(token_map[n]), true);
427 }
428 Some(aiv)
429 } else {
430 None
431 };
432
433 assert!(!token_names.is_empty());
434 assert!(!rule_names.is_empty());
435 Ok(YaccGrammar {
436 rules_len: RIdx(rule_names.len().as_()),
437 rule_names: rule_names.into_boxed_slice(),
438 tokens_len: TIdx(token_names.len().as_()),
439 eof_token_idx,
440 token_names: token_names.into_boxed_slice(),
441 token_precs: token_precs.into_boxed_slice(),
442 token_epp: token_epp.into_boxed_slice(),
443 prods_len: PIdx(prods.len().as_()),
444 start_prod: rules_prods[usize::from(rule_map[&start_rule])][0],
445 rules_prods: rules_prods
446 .iter()
447 .map(|x| x.iter().copied().collect())
448 .collect(),
449 prods_rules: prods_rules.into_iter().map(Option::unwrap).collect(),
450 prods: prods
451 .into_iter()
452 .map(|x| x.unwrap().into_boxed_slice())
453 .collect(),
454 prod_precs: prod_precs.into_iter().map(Option::unwrap).collect(),
455 implicit_rule: implicit_rule.map(|x| rule_map[&x]),
456 actions: actions.into_boxed_slice(),
457 parse_param: ast.parse_param.clone(),
458 programs: ast.programs.clone(),
459 avoid_insert,
460 actiontypes: actiontypes.into_boxed_slice(),
461 expect: ast.expect.map(|(n, _)| n),
462 expectrr: ast.expectrr.map(|(n, _)| n),
463 })
464 }
465
466 pub fn prods_len(&self) -> PIdx<StorageT> {
468 self.prods_len
469 }
470
471 pub fn iter_pidxs(&self) -> impl Iterator<Item = PIdx<StorageT>> {
474 Box::new((0..usize::from(self.prods_len())).map(|x| PIdx(x.as_())))
478 }
479
480 pub fn prod(&self, pidx: PIdx<StorageT>) -> &[Symbol<StorageT>] {
482 &self.prods[usize::from(pidx)]
483 }
484
485 pub fn prod_len(&self, pidx: PIdx<StorageT>) -> SIdx<StorageT> {
487 SIdx(self.prods[usize::from(pidx)].len().as_())
490 }
491
492 pub fn prod_to_rule(&self, pidx: PIdx<StorageT>) -> RIdx<StorageT> {
494 self.prods_rules[usize::from(pidx)]
495 }
496
497 pub fn prod_precedence(&self, pidx: PIdx<StorageT>) -> Option<Precedence> {
500 self.prod_precs[usize::from(pidx)]
501 }
502
503 pub fn start_prod(&self) -> PIdx<StorageT> {
506 self.start_prod
507 }
508
509 pub fn rules_len(&self) -> RIdx<StorageT> {
511 self.rules_len
512 }
513
514 pub fn iter_rules(&self) -> impl Iterator<Item = RIdx<StorageT>> {
517 Box::new((0..usize::from(self.rules_len())).map(|x| RIdx(x.as_())))
521 }
522
523 pub fn rule_to_prods(&self, ridx: RIdx<StorageT>) -> &[PIdx<StorageT>] {
525 &self.rules_prods[usize::from(ridx)]
526 }
527
528 #[deprecated(since = "0.13.0", note = "Please use rule_name_str instead")]
530 pub fn rule_name(&self, ridx: RIdx<StorageT>) -> &str {
531 self.rule_name_str(ridx)
532 }
533
534 pub fn rule_name_str(&self, ridx: RIdx<StorageT>) -> &str {
536 let (name, _) = &self.rule_names[usize::from(ridx)];
537 name.as_str()
538 }
539
540 pub fn rule_name_span(&self, ridx: RIdx<StorageT>) -> Span {
542 let (_, span) = self.rule_names[usize::from(ridx)];
543 span
544 }
545
546 pub fn implicit_rule(&self) -> Option<RIdx<StorageT>> {
548 self.implicit_rule
549 }
550
551 pub fn rule_idx(&self, n: &str) -> Option<RIdx<StorageT>> {
553 self.rule_names
554 .iter()
555 .position(|(x, _)| x == n)
556 .map(|x| RIdx(x.as_()))
559 }
560
561 pub fn start_rule_idx(&self) -> RIdx<StorageT> {
564 self.prod_to_rule(self.start_prod)
565 }
566
567 pub fn tokens_len(&self) -> TIdx<StorageT> {
569 self.tokens_len
570 }
571
572 pub fn iter_tidxs(&self) -> impl Iterator<Item = TIdx<StorageT>> {
575 Box::new((0..usize::from(self.tokens_len())).map(|x| TIdx(x.as_())))
579 }
580
581 pub fn eof_token_idx(&self) -> TIdx<StorageT> {
583 self.eof_token_idx
584 }
585
586 pub fn token_name(&self, tidx: TIdx<StorageT>) -> Option<&str> {
589 self.token_names[usize::from(tidx)]
590 .as_ref()
591 .map(|(_, x)| x.as_str())
592 }
593
594 pub fn token_precedence(&self, tidx: TIdx<StorageT>) -> Option<Precedence> {
597 self.token_precs[usize::from(tidx)]
598 }
599
600 pub fn token_epp(&self, tidx: TIdx<StorageT>) -> Option<&str> {
603 self.token_epp[usize::from(tidx)].as_deref()
604 }
605
606 pub fn token_span(&self, tidx: TIdx<StorageT>) -> Option<Span> {
612 self.token_names[usize::from(tidx)]
613 .as_ref()
614 .map(|(span, _)| *span)
615 }
616
617 pub fn action(&self, pidx: PIdx<StorageT>) -> &Option<String> {
619 &self.actions[usize::from(pidx)]
620 }
621
622 pub fn actiontype(&self, ridx: RIdx<StorageT>) -> &Option<String> {
623 &self.actiontypes[usize::from(ridx)]
624 }
625
626 pub fn parse_param(&self) -> &Option<(String, String)> {
627 &self.parse_param
628 }
629
630 pub fn programs(&self) -> &Option<String> {
632 &self.programs
633 }
634
635 pub fn tokens_map(&self) -> HashMap<&str, TIdx<StorageT>> {
638 let mut m = HashMap::with_capacity(usize::from(self.tokens_len) - 1);
639 for tidx in self.iter_tidxs() {
640 if let Some((_, n)) = self.token_names[usize::from(tidx)].as_ref() {
641 m.insert(&**n, tidx);
642 }
643 }
644 m
645 }
646
647 pub fn token_idx(&self, n: &str) -> Option<TIdx<StorageT>> {
649 self.token_names
650 .iter()
651 .position(|x| x.as_ref().is_some_and(|(_, x)| x == n))
652 .map(|x| TIdx(x.as_()))
655 }
656
657 pub fn avoid_insert(&self, tidx: TIdx<StorageT>) -> bool {
659 if let Some(ai) = &self.avoid_insert {
660 ai.get(usize::from(tidx)).unwrap()
661 } else {
662 false
663 }
664 }
665
666 pub fn expect(&self) -> Option<usize> {
668 self.expect
669 }
670
671 pub fn expectrr(&self) -> Option<usize> {
673 self.expectrr
674 }
675
676 pub fn has_path(&self, from: RIdx<StorageT>, to: RIdx<StorageT>) -> bool {
679 let mut seen = vec![];
680 seen.resize(usize::from(self.rules_len()), false);
681 let mut todo = vec![];
682 todo.resize(usize::from(self.rules_len()), false);
683 todo[usize::from(from)] = true;
684 loop {
685 let mut empty = true;
686 for ridx in self.iter_rules() {
687 if !todo[usize::from(ridx)] {
688 continue;
689 }
690 seen[usize::from(ridx)] = true;
691 todo[usize::from(ridx)] = false;
692 empty = false;
693 for pidx in self.rule_to_prods(ridx).iter() {
694 for sym in self.prod(*pidx) {
695 if let Symbol::Rule(p_ridx) = *sym {
696 if p_ridx == to {
697 return true;
698 }
699 if !seen[usize::from(p_ridx)] {
700 todo[usize::from(p_ridx)] = true;
701 }
702 }
703 }
704 }
705 }
706 if empty {
707 return false;
708 }
709 }
710 }
711
712 pub fn pp_prod(&self, pidx: PIdx<StorageT>) -> String {
714 let mut sprod = String::new();
715 let ridx = self.prod_to_rule(pidx);
716 sprod.push_str(self.rule_name_str(ridx));
717 sprod.push(':');
718 for sym in self.prod(pidx) {
719 let s = match sym {
720 Symbol::Token(tidx) => self.token_name(*tidx).unwrap(),
721 Symbol::Rule(ridx) => self.rule_name_str(*ridx),
722 };
723 write!(sprod, " \"{}\"", s).ok();
724 }
725 sprod
726 }
727
728 pub fn sentence_generator<F>(&self, token_cost: F) -> SentenceGenerator<StorageT>
733 where
734 F: Fn(TIdx<StorageT>) -> u8,
735 {
736 SentenceGenerator::new(self, token_cost)
737 }
738
739 pub fn firsts(&self) -> YaccFirsts<StorageT> {
741 YaccFirsts::new(self)
742 }
743
744 pub fn follows(&self) -> YaccFollows<StorageT> {
746 YaccFollows::new(self)
747 }
748}
749
750pub struct SentenceGenerator<'a, StorageT> {
771 grm: &'a YaccGrammar<StorageT>,
772 rule_min_costs: RefCell<Option<Vec<u16>>>,
773 rule_max_costs: RefCell<Option<Vec<u16>>>,
774 token_costs: Vec<u8>,
775}
776
777impl<'a, StorageT: 'static + PrimInt + Unsigned> SentenceGenerator<'a, StorageT>
778where
779 usize: AsPrimitive<StorageT>,
780{
781 fn new<F>(grm: &'a YaccGrammar<StorageT>, token_cost: F) -> Self
782 where
783 F: Fn(TIdx<StorageT>) -> u8,
784 {
785 let mut token_costs = Vec::with_capacity(usize::from(grm.tokens_len()));
786 for tidx in grm.iter_tidxs() {
787 token_costs.push(token_cost(tidx));
788 }
789 SentenceGenerator {
790 grm,
791 token_costs,
792 rule_min_costs: RefCell::new(None),
793 rule_max_costs: RefCell::new(None),
794 }
795 }
796
797 pub fn min_sentence_cost(&self, ridx: RIdx<StorageT>) -> u16 {
801 self.rule_min_costs
802 .borrow_mut()
803 .get_or_insert_with(|| rule_min_costs(self.grm, &self.token_costs))[usize::from(ridx)]
804 }
805
806 pub fn max_sentence_cost(&self, ridx: RIdx<StorageT>) -> Option<u16> {
810 let v = self
811 .rule_max_costs
812 .borrow_mut()
813 .get_or_insert_with(|| rule_max_costs(self.grm, &self.token_costs))[usize::from(ridx)];
814 if v == u16::MAX {
815 None
816 } else {
817 Some(v)
818 }
819 }
820
821 pub fn min_sentence(&self, ridx: RIdx<StorageT>) -> Vec<TIdx<StorageT>> {
824 let cheapest_prod = |p_ridx: RIdx<StorageT>| -> PIdx<StorageT> {
825 let mut low_sc = None;
826 let mut low_idx = None;
827 for &pidx in self.grm.rule_to_prods(p_ridx).iter() {
828 let mut sc = 0;
829 for sym in self.grm.prod(pidx).iter() {
830 sc += match *sym {
831 Symbol::Rule(i) => self.min_sentence_cost(i),
832 Symbol::Token(i) => u16::from(self.token_costs[usize::from(i)]),
833 };
834 }
835 if low_sc.is_none() || Some(sc) < low_sc {
836 low_sc = Some(sc);
837 low_idx = Some(pidx);
838 }
839 }
840 low_idx.unwrap()
841 };
842
843 let mut s = vec![];
844 let mut st = vec![(cheapest_prod(ridx), 0)];
845 while let Some((pidx, sym_idx)) = st.pop() {
846 let prod = self.grm.prod(pidx);
847 for (sidx, sym) in prod.iter().enumerate().skip(sym_idx) {
848 match sym {
849 Symbol::Rule(s_ridx) => {
850 st.push((pidx, sidx + 1));
851 st.push((cheapest_prod(*s_ridx), 0));
852 }
853 Symbol::Token(s_tidx) => {
854 s.push(*s_tidx);
855 }
856 }
857 }
858 }
859 s
860 }
861
862 pub fn min_sentences(&self, ridx: RIdx<StorageT>) -> Vec<Vec<TIdx<StorageT>>> {
864 let cheapest_prods = |p_ridx: RIdx<StorageT>| -> Vec<PIdx<StorageT>> {
865 let mut low_sc = None;
866 let mut low_idxs = vec![];
867 for &pidx in self.grm.rule_to_prods(p_ridx).iter() {
868 let mut sc = 0;
869 for sym in self.grm.prod(pidx).iter() {
870 sc += match *sym {
871 Symbol::Rule(s_ridx) => self.min_sentence_cost(s_ridx),
872 Symbol::Token(s_tidx) => u16::from(self.token_costs[usize::from(s_tidx)]),
873 };
874 }
875 if low_sc.is_none() || Some(sc) <= low_sc {
876 if Some(sc) < low_sc {
877 low_idxs.clear();
878 }
879 low_sc = Some(sc);
880 low_idxs.push(pidx);
881 }
882 }
883 low_idxs
884 };
885
886 let mut sts = Vec::new(); for pidx in cheapest_prods(ridx) {
888 let prod = self.grm.prod(pidx);
889 if prod.is_empty() {
890 sts.push(vec![]);
891 continue;
892 }
893
894 let mut ms = Vec::with_capacity(prod.len());
905 for sym in prod {
906 match *sym {
907 Symbol::Rule(s_ridx) => ms.push(self.min_sentences(s_ridx)),
908 Symbol::Token(s_tidx) => ms.push(vec![vec![s_tidx]]),
909 }
910 }
911
912 let mut todo = vec![0; prod.len()];
937 let mut cur = Vec::new();
938 'b: loop {
939 for i in 0..todo.len() {
940 cur.extend(&ms[i][todo[i]]);
941 }
942 sts.push(std::mem::take(&mut cur));
943
944 let mut j = todo.len() - 1;
945 loop {
946 if todo[j] + 1 == ms[j].len() {
947 if j == 0 {
948 break 'b;
949 }
950 todo[j] = 0;
951 j -= 1;
952 } else {
953 todo[j] += 1;
954 break;
955 }
956 }
957 }
958 }
959 sts
960 }
961}
962
963#[allow(clippy::unnecessary_unwrap)]
966fn rule_min_costs<StorageT: 'static + PrimInt + Unsigned>(
967 grm: &YaccGrammar<StorageT>,
968 token_costs: &[u8],
969) -> Vec<u16>
970where
971 usize: AsPrimitive<StorageT>,
972{
973 let mut costs = vec![0; usize::from(grm.rules_len())];
996 let mut done = vec![false; usize::from(grm.rules_len())];
997 loop {
998 let mut all_done = true;
999 for i in 0..done.len() {
1000 if done[i] {
1001 continue;
1002 }
1003 all_done = false;
1004 let mut ls_cmplt = None; let mut ls_noncmplt = None; for pidx in grm.rule_to_prods(RIdx(i.as_())).iter() {
1010 let mut c: u16 = 0; let mut cmplt = true;
1012 for sym in grm.prod(*pidx) {
1013 let sc = match *sym {
1014 Symbol::Token(tidx) => u16::from(token_costs[usize::from(tidx)]),
1015 Symbol::Rule(ridx) => {
1016 if !done[usize::from(ridx)] {
1017 cmplt = false;
1018 }
1019 costs[usize::from(ridx)]
1020 }
1021 };
1022 c = c
1023 .checked_add(sc)
1024 .expect("Overflow occurred when calculating rule costs");
1025 }
1026 if cmplt && (ls_cmplt.is_none() || Some(c) < ls_cmplt) {
1027 ls_cmplt = Some(c);
1028 } else if !cmplt && (ls_noncmplt.is_none() || Some(c) < ls_noncmplt) {
1029 ls_noncmplt = Some(c);
1030 }
1031 }
1032 if ls_cmplt.is_some() && (ls_noncmplt.is_none() || ls_cmplt < ls_noncmplt) {
1033 debug_assert!(ls_cmplt.unwrap() >= costs[i]);
1034 costs[i] = ls_cmplt.unwrap();
1035 done[i] = true;
1036 } else if let Some(ls_noncmplt) = ls_noncmplt {
1037 debug_assert!(ls_noncmplt >= costs[i]);
1038 costs[i] = ls_noncmplt;
1039 }
1040 }
1041 if all_done {
1042 debug_assert!(done.iter().all(|x| *x));
1043 break;
1044 }
1045 }
1046 costs
1047}
1048
1049#[allow(clippy::unnecessary_unwrap)]
1053fn rule_max_costs<StorageT: 'static + PrimInt + Unsigned>(
1054 grm: &YaccGrammar<StorageT>,
1055 token_costs: &[u8],
1056) -> Vec<u16>
1057where
1058 usize: AsPrimitive<StorageT>,
1059{
1060 let mut done = vec![false; usize::from(grm.rules_len())];
1061 let mut costs = vec![0; usize::from(grm.rules_len())];
1062
1063 for ridx in grm.iter_rules() {
1065 if grm.has_path(ridx, ridx) {
1067 costs[usize::from(ridx)] = u16::MAX;
1068 done[usize::from(ridx)] = true;
1069 }
1070 }
1071
1072 loop {
1073 let mut all_done = true;
1074 for i in 0..done.len() {
1075 if done[i] {
1076 continue;
1077 }
1078 all_done = false;
1079 let mut hs_cmplt = None; let mut hs_noncmplt = None; 'a: for pidx in grm.rule_to_prods(RIdx(i.as_())).iter() {
1085 let mut c: u16 = 0; let mut cmplt = true;
1087 for sym in grm.prod(*pidx) {
1088 let sc = match *sym {
1089 Symbol::Token(s_tidx) => u16::from(token_costs[usize::from(s_tidx)]),
1090 Symbol::Rule(s_ridx) => {
1091 if costs[usize::from(s_ridx)] == u16::MAX {
1092 hs_cmplt = Some(u16::MAX);
1095 break 'a;
1096 }
1097 if !done[usize::from(s_ridx)] {
1098 cmplt = false;
1099 }
1100 costs[usize::from(s_ridx)]
1101 }
1102 };
1103 c = c
1104 .checked_add(sc)
1105 .expect("Overflow occurred when calculating rule costs");
1106 if c == u16::MAX {
1107 panic!("Unable to represent cost in 64 bits.");
1108 }
1109 }
1110 if cmplt && (hs_cmplt.is_none() || Some(c) > hs_cmplt) {
1111 hs_cmplt = Some(c);
1112 } else if !cmplt && (hs_noncmplt.is_none() || Some(c) > hs_noncmplt) {
1113 hs_noncmplt = Some(c);
1114 }
1115 }
1116 if hs_cmplt.is_some() && (hs_noncmplt.is_none() || hs_cmplt > hs_noncmplt) {
1117 debug_assert!(hs_cmplt.unwrap() >= costs[i]);
1118 costs[i] = hs_cmplt.unwrap();
1119 done[i] = true;
1120 } else if let Some(hs_noncmplt) = hs_noncmplt {
1121 debug_assert!(hs_noncmplt >= costs[i]);
1122 costs[i] = hs_noncmplt;
1123 }
1124 }
1125 if all_done {
1126 debug_assert!(done.iter().all(|x| *x));
1127 break;
1128 }
1129 }
1130 costs
1131}
1132
1133#[cfg(test)]
1134mod test {
1135 use super::{
1136 super::{AssocKind, Precedence, YaccGrammar, YaccKind, YaccOriginalActionKind},
1137 rule_max_costs, rule_min_costs, IMPLICIT_RULE, IMPLICIT_START_RULE,
1138 };
1139 use crate::{PIdx, RIdx, Span, Symbol, TIdx};
1140 use std::collections::HashMap;
1141 use std::str::FromStr;
1142
1143 macro_rules! bslice {
1144 () => (
1145 ::Vec::new().into_boxed_slice()
1146 );
1147 ($elem:expr; $n:expr) => (
1148 ::vec::from_elem($elem, $n).into_boxed_slice()
1149 );
1150 ($($x:expr),+ $(,)?) => (
1151 <[_]>::into_vec(
1152 Box::new([$($x),+])
1153 ).into_boxed_slice()
1154 );
1155 }
1156
1157 #[test]
1158 fn test_minimal() {
1159 let grm = YaccGrammar::new(
1160 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1161 "%start R %token T %% R: 'T';",
1162 )
1163 .unwrap();
1164
1165 assert_eq!(grm.start_prod, PIdx(1));
1166 assert_eq!(grm.implicit_rule(), None);
1167 grm.rule_idx("^").unwrap();
1168 grm.rule_idx("R").unwrap();
1169 grm.token_idx("T").unwrap();
1170
1171 assert_eq!(&*grm.rules_prods, &[bslice![PIdx(1)], bslice![PIdx(0)]]);
1172 let start_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("^").unwrap())][0]);
1173 assert_eq!(*start_prod, [Symbol::Rule(grm.rule_idx("R").unwrap())]);
1174 let r_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("R").unwrap())][0]);
1175 assert_eq!(*r_prod, [Symbol::Token(grm.token_idx("T").unwrap())]);
1176 assert_eq!(&*grm.prods_rules, &[RIdx(1), RIdx(0)]);
1177
1178 assert_eq!(
1179 grm.tokens_map(),
1180 [("T", TIdx(0))]
1181 .iter()
1182 .cloned()
1183 .collect::<HashMap<&str, TIdx<_>>>()
1184 );
1185 assert_eq!(grm.iter_rules().collect::<Vec<_>>(), vec![RIdx(0), RIdx(1)]);
1186 }
1187
1188 #[test]
1189 fn test_rule_ref() {
1190 let grm = YaccGrammar::new(
1191 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1192 "%start R %token T %% R : S; S: 'T';",
1193 )
1194 .unwrap();
1195
1196 grm.rule_idx("^").unwrap();
1197 grm.rule_idx("R").unwrap();
1198 grm.rule_idx("S").unwrap();
1199 grm.token_idx("T").unwrap();
1200 assert!(grm.token_name(grm.eof_token_idx()).is_none());
1201
1202 assert_eq!(
1203 &*grm.rules_prods,
1204 &[bslice![PIdx(2)], bslice![PIdx(0)], bslice![PIdx(1)]]
1205 );
1206 let start_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("^").unwrap())][0]);
1207 assert_eq!(*start_prod, [Symbol::Rule(grm.rule_idx("R").unwrap())]);
1208 let r_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("R").unwrap())][0]);
1209 assert_eq!(r_prod.len(), 1);
1210 assert_eq!(r_prod[0], Symbol::Rule(grm.rule_idx("S").unwrap()));
1211 let s_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("S").unwrap())][0]);
1212 assert_eq!(s_prod.len(), 1);
1213 assert_eq!(s_prod[0], Symbol::Token(grm.token_idx("T").unwrap()));
1214 }
1215
1216 #[test]
1217 #[rustfmt::skip]
1218 fn test_long_prod() {
1219 let grm = YaccGrammar::new(
1220 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1221 "%start R %token T1 T2 %% R : S 'T1' S; S: 'T2';"
1222 ).unwrap();
1223
1224 grm.rule_idx("^").unwrap();
1225 grm.rule_idx("R").unwrap();
1226 grm.rule_idx("S").unwrap();
1227 grm.token_idx("T1").unwrap();
1228 grm.token_idx("T2").unwrap();
1229
1230 assert_eq!(&*grm.rules_prods, &[bslice![PIdx(2)],
1231 bslice![PIdx(0)],
1232 bslice![PIdx(1)]]);
1233 assert_eq!(&*grm.prods_rules, &[RIdx(1),
1234 RIdx(2),
1235 RIdx(0)]);
1236 let start_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("^").unwrap())][0]);
1237 assert_eq!(*start_prod, [Symbol::Rule(grm.rule_idx("R").unwrap())]);
1238 let r_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("R").unwrap())][0]);
1239 assert_eq!(r_prod.len(), 3);
1240 assert_eq!(r_prod[0], Symbol::Rule(grm.rule_idx("S").unwrap()));
1241 assert_eq!(r_prod[1], Symbol::Token(grm.token_idx("T1").unwrap()));
1242 assert_eq!(r_prod[2], Symbol::Rule(grm.rule_idx("S").unwrap()));
1243 let s_prod = grm.prod(grm.rules_prods[usize::from(grm.rule_idx("S").unwrap())][0]);
1244 assert_eq!(s_prod.len(), 1);
1245 assert_eq!(s_prod[0], Symbol::Token(grm.token_idx("T2").unwrap()));
1246 }
1247
1248 #[test]
1249 fn test_prods_rules() {
1250 let grm = YaccGrammar::new(
1251 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1252 "
1253 %start A
1254 %%
1255 A: B
1256 | C;
1257 B: 'x';
1258 C: 'y'
1259 | 'z';
1260 ",
1261 )
1262 .unwrap();
1263
1264 assert_eq!(
1265 &*grm.prods_rules,
1266 &[RIdx(1), RIdx(1), RIdx(2), RIdx(3), RIdx(3), RIdx(0)]
1267 );
1268 }
1269
1270 #[test]
1271 #[rustfmt::skip]
1272 fn test_left_right_nonassoc_precs() {
1273 let grm = YaccGrammar::new(
1274 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1275 "
1276 %start Expr
1277 %right '='
1278 %left '+' '-'
1279 %left '/'
1280 %left '*'
1281 %nonassoc '~'
1282 %%
1283 Expr : Expr '=' Expr
1284 | Expr '+' Expr
1285 | Expr '-' Expr
1286 | Expr '/' Expr
1287 | Expr '*' Expr
1288 | Expr '~' Expr
1289 | 'id' ;
1290 ").unwrap();
1291
1292 assert_eq!(grm.prod_precs.len(), 8);
1293 assert_eq!(grm.prod_precs[0].unwrap(), Precedence{level: 0, kind: AssocKind::Right});
1294 assert_eq!(grm.prod_precs[1].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1295 assert_eq!(grm.prod_precs[2].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1296 assert_eq!(grm.prod_precs[3].unwrap(), Precedence{level: 2, kind: AssocKind::Left});
1297 assert_eq!(grm.prod_precs[4].unwrap(), Precedence{level: 3, kind: AssocKind::Left});
1298 assert_eq!(grm.prod_precs[5].unwrap(), Precedence{level: 4, kind: AssocKind::Nonassoc});
1299 assert!(grm.prod_precs[6].is_none());
1300 assert_eq!(grm.prod_precs[7], None);
1301 }
1302
1303 #[test]
1304 #[rustfmt::skip]
1305 fn test_prec_override() {
1306 let grm = YaccGrammar::new(
1307 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1308 "
1309 %start expr
1310 %left '+' '-'
1311 %left '*' '/'
1312 %%
1313 expr : expr '+' expr
1314 | expr '-' expr
1315 | expr '*' expr
1316 | expr '/' expr
1317 | '-' expr %prec '*'
1318 | 'id' ;
1319 "
1320 ).unwrap();
1321 assert_eq!(grm.prod_precs.len(), 7);
1322 assert_eq!(grm.prod_precs[0].unwrap(), Precedence{level: 0, kind: AssocKind::Left});
1323 assert_eq!(grm.prod_precs[1].unwrap(), Precedence{level: 0, kind: AssocKind::Left});
1324 assert_eq!(grm.prod_precs[2].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1325 assert_eq!(grm.prod_precs[3].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1326 assert_eq!(grm.prod_precs[4].unwrap(), Precedence{level: 1, kind: AssocKind::Left});
1327 assert!(grm.prod_precs[5].is_none());
1328 assert_eq!(grm.prod_precs[6], None);
1329 }
1330
1331 #[test]
1332 #[rustfmt::skip]
1333 fn test_implicit_tokens_rewrite() {
1334 let grm = YaccGrammar::new(
1335 YaccKind::Eco,
1336 "
1337 %implicit_tokens ws1 ws2
1338 %start S
1339 %%
1340 S: 'a' | T;
1341 T: 'c' |;
1342 "
1343 ).unwrap();
1344
1345 assert_eq!(grm.prod_precs.len(), 9);
1353
1354 let itfs_rule_idx = grm.rule_idx(IMPLICIT_START_RULE).unwrap();
1355 assert_eq!(grm.rules_prods[usize::from(itfs_rule_idx)].len(), 1);
1356
1357 let itfs_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(itfs_rule_idx)][0])];
1358 assert_eq!(itfs_prod1.len(), 2);
1359 assert_eq!(itfs_prod1[0], Symbol::Rule(grm.rule_idx(IMPLICIT_RULE).unwrap()));
1360 assert_eq!(itfs_prod1[1], Symbol::Rule(grm.rule_idx("S").unwrap()));
1361
1362 let s_rule_idx = grm.rule_idx("S").unwrap();
1363 assert_eq!(grm.rules_prods[usize::from(s_rule_idx)].len(), 2);
1364
1365 let s_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(s_rule_idx)][0])];
1366 assert_eq!(s_prod1.len(), 2);
1367 assert_eq!(s_prod1[0], Symbol::Token(grm.token_idx("a").unwrap()));
1368 assert_eq!(s_prod1[1], Symbol::Rule(grm.rule_idx(IMPLICIT_RULE).unwrap()));
1369
1370 let s_prod2 = &grm.prods[usize::from(grm.rules_prods[usize::from(s_rule_idx)][1])];
1371 assert_eq!(s_prod2.len(), 1);
1372 assert_eq!(s_prod2[0], Symbol::Rule(grm.rule_idx("T").unwrap()));
1373
1374 let t_rule_idx = grm.rule_idx("T").unwrap();
1375 assert_eq!(grm.rules_prods[usize::from(s_rule_idx)].len(), 2);
1376
1377 let t_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(t_rule_idx)][0])];
1378 assert_eq!(t_prod1.len(), 2);
1379 assert_eq!(t_prod1[0], Symbol::Token(grm.token_idx("c").unwrap()));
1380 assert_eq!(t_prod1[1], Symbol::Rule(grm.rule_idx(IMPLICIT_RULE).unwrap()));
1381
1382 let t_prod2 = &grm.prods[usize::from(grm.rules_prods[usize::from(t_rule_idx)][1])];
1383 assert_eq!(t_prod2.len(), 0);
1384
1385 assert_eq!(Some(grm.rule_idx(IMPLICIT_RULE).unwrap()), grm.implicit_rule());
1386 let i_rule_idx = grm.rule_idx(IMPLICIT_RULE).unwrap();
1387 assert_eq!(grm.rules_prods[usize::from(i_rule_idx)].len(), 3);
1388 let i_prod1 = &grm.prods[usize::from(grm.rules_prods[usize::from(i_rule_idx)][0])];
1389 let i_prod2 = &grm.prods[usize::from(grm.rules_prods[usize::from(i_rule_idx)][1])];
1390 assert_eq!(i_prod1.len(), 2);
1391 assert_eq!(i_prod2.len(), 2);
1392 let cnd1 = bslice![
1395 Symbol::Token(grm.token_idx("ws1").unwrap()),
1396 Symbol::Rule(grm.implicit_rule().unwrap()),
1397 ];
1398 let cnd2 = bslice![
1399 Symbol::Token(grm.token_idx("ws2").unwrap()),
1400 Symbol::Rule(grm.implicit_rule().unwrap()),
1401 ];
1402 assert!((*i_prod1 == cnd1 && *i_prod2 == cnd2) || (*i_prod1 == cnd2 && *i_prod2 == cnd1));
1403 let i_prod3 = &grm.prods[usize::from(grm.rules_prods[usize::from(i_rule_idx)][2])];
1404 assert_eq!(i_prod3.len(), 0);
1405 }
1406
1407 #[test]
1408 #[rustfmt::skip]
1409 fn test_has_path() {
1410 let grm = YaccGrammar::new(
1411 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1412 "
1413 %start A
1414 %%
1415 A: B;
1416 B: B 'x' | C;
1417 C: C 'y' | ;
1418 "
1419 ).unwrap();
1420
1421 let a_ridx = grm.rule_idx("A").unwrap();
1422 let b_ridx = grm.rule_idx("B").unwrap();
1423 let c_ridx = grm.rule_idx("C").unwrap();
1424 assert!(grm.has_path(a_ridx, b_ridx));
1425 assert!(grm.has_path(a_ridx, c_ridx));
1426 assert!(grm.has_path(b_ridx, b_ridx));
1427 assert!(grm.has_path(b_ridx, c_ridx));
1428 assert!(grm.has_path(c_ridx, c_ridx));
1429 assert!(!grm.has_path(a_ridx, a_ridx));
1430 assert!(!grm.has_path(b_ridx, a_ridx));
1431 assert!(!grm.has_path(c_ridx, a_ridx));
1432 }
1433
1434 #[test]
1435 #[rustfmt::skip]
1436 fn test_rule_min_costs() {
1437 let grm = YaccGrammar::new(
1438 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1439 "
1440 %start A
1441 %%
1442 A: A B | ;
1443 B: C | D | E;
1444 C: 'x' B | 'x';
1445 D: 'y' B | 'y' 'z';
1446 E: 'x' A | 'x' 'y';
1447 "
1448 ).unwrap();
1449
1450 let scores = rule_min_costs(&grm, &[1, 1, 1]);
1451 assert_eq!(scores[usize::from(grm.rule_idx("A").unwrap())], 0);
1452 assert_eq!(scores[usize::from(grm.rule_idx("B").unwrap())], 1);
1453 assert_eq!(scores[usize::from(grm.rule_idx("C").unwrap())], 1);
1454 assert_eq!(scores[usize::from(grm.rule_idx("D").unwrap())], 2);
1455 assert_eq!(scores[usize::from(grm.rule_idx("E").unwrap())], 1);
1456 }
1457
1458 #[test]
1459 fn test_min_sentences() {
1460 let grm = YaccGrammar::new(
1461 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1462 "
1463 %start A
1464 %%
1465 A: A B | ;
1466 B: C | D;
1467 C: 'x' B | 'x';
1468 D: 'y' B | 'y' 'z';
1469 ",
1470 )
1471 .unwrap();
1472
1473 let sg = grm.sentence_generator(|_| 1);
1474
1475 let find = |nt_name: &str, str_cnds: Vec<Vec<&str>>| {
1476 let cnds = str_cnds
1477 .iter()
1478 .map(|x| {
1479 x.iter()
1480 .map(|y| grm.token_idx(y).unwrap())
1481 .collect::<Vec<_>>()
1482 })
1483 .collect::<Vec<_>>();
1484
1485 let ms = sg.min_sentence(grm.rule_idx(nt_name).unwrap());
1486 if !cnds.iter().any(|x| x == &ms) {
1487 panic!("{:?} doesn't have any matches in {:?}", ms, str_cnds);
1488 }
1489
1490 let min_sts = sg.min_sentences(grm.rule_idx(nt_name).unwrap());
1491 assert_eq!(cnds.len(), min_sts.len());
1492 for ms in min_sts {
1493 if !cnds.iter().any(|x| x == &ms) {
1494 panic!("{:?} doesn't have any matches in {:?}", ms, str_cnds);
1495 }
1496 }
1497 };
1498
1499 find("A", vec![vec![]]);
1500 find("B", vec![vec!["x"]]);
1501 find("C", vec![vec!["x"]]);
1502 find("D", vec![vec!["y", "x"], vec!["y", "z"]]);
1503 }
1504
1505 #[test]
1506 #[rustfmt::skip]
1507 fn test_rule_max_costs1() {
1508 let grm = YaccGrammar::new(
1509 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1510 "
1511 %start A
1512 %%
1513 A: A B | ;
1514 B: C | D | E;
1515 C: 'x' B | 'x';
1516 D: 'y' B | 'y' 'z';
1517 E: 'x' A | 'x' 'y';
1518 "
1519 ).unwrap();
1520
1521 let scores = rule_max_costs(&grm, &[1, 1, 1]);
1522 assert_eq!(scores[usize::from(grm.rule_idx("A").unwrap())], u16::MAX);
1523 assert_eq!(scores[usize::from(grm.rule_idx("B").unwrap())], u16::MAX);
1524 assert_eq!(scores[usize::from(grm.rule_idx("C").unwrap())], u16::MAX);
1525 assert_eq!(scores[usize::from(grm.rule_idx("D").unwrap())], u16::MAX);
1526 assert_eq!(scores[usize::from(grm.rule_idx("E").unwrap())], u16::MAX);
1527 }
1528
1529 #[test]
1530 #[rustfmt::skip]
1531 fn test_rule_max_costs2() {
1532 let grm = YaccGrammar::new(
1533 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1534 "
1535 %start A
1536 %%
1537 A: A B | B;
1538 B: C | D;
1539 C: 'x' 'y' | 'x';
1540 D: 'y' 'x' | 'y' 'x' 'z';
1541 "
1542 ).unwrap();
1543
1544 let scores = rule_max_costs(&grm, &[1, 1, 1]);
1545 assert_eq!(scores[usize::from(grm.rule_idx("A").unwrap())], u16::MAX);
1546 assert_eq!(scores[usize::from(grm.rule_idx("B").unwrap())], 3);
1547 assert_eq!(scores[usize::from(grm.rule_idx("C").unwrap())], 2);
1548 assert_eq!(scores[usize::from(grm.rule_idx("D").unwrap())], 3);
1549 }
1550
1551 #[test]
1552 fn test_out_of_order_productions() {
1553 let grm = YaccGrammar::new(
1555 YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
1556 "
1557 %start S
1558 %%
1559 S: A 'c' 'd'
1560 | B 'c' 'e';
1561 A: 'a';
1562 B: 'a'
1563 | 'b';
1564 A: 'b';
1565 ",
1566 )
1567 .unwrap();
1568
1569 assert_eq!(
1570 &*grm.prods_rules,
1571 &[
1572 RIdx(1),
1573 RIdx(1),
1574 RIdx(2),
1575 RIdx(3),
1576 RIdx(3),
1577 RIdx(2),
1578 RIdx(0)
1579 ]
1580 );
1581 }
1582
1583 #[test]
1584 fn test_token_spans() {
1585 let src = "%%\nAB: 'a' | 'foo';";
1586 let grm =
1587 YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
1588 let token_map = grm.tokens_map();
1589 let a_tidx = token_map.get("a");
1590 let foo_tidx = token_map.get("foo");
1591 let a_span = grm.token_span(*a_tidx.unwrap()).unwrap();
1592 let foo_span = grm.token_span(*foo_tidx.unwrap()).unwrap();
1593 let ab_span = grm.rule_name_span(grm.rule_idx("AB").unwrap());
1594 assert_eq!(a_span, Span::new(8, 9));
1595 assert_eq!(foo_span, Span::new(14, 17));
1596 assert_eq!(ab_span, Span::new(3, 5));
1597 assert_eq!(&src[a_span.start()..a_span.end()], "a");
1598 assert_eq!(&src[foo_span.start()..foo_span.end()], "foo");
1599 assert_eq!(&src[ab_span.start()..ab_span.end()], "AB");
1600 }
1601
1602 #[test]
1603 fn token_span_issue296() {
1604 let src = "%%
1605 S: | AB;
1606 A: 'a' 'b';
1607 B: 'b' 'c';
1608 AB: A AB | B ';' AB;
1609 %%
1610 ";
1611 let grm =
1612 YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::NoAction), src).unwrap();
1613 let token_map = grm.tokens_map();
1614 let c_tidx = token_map.get("c").unwrap();
1615 assert_eq!(grm.token_name(*c_tidx), Some("c"));
1616 let c_span = grm.token_span(*c_tidx).unwrap();
1617 assert_eq!(&src[c_span.start()..c_span.end()], "c");
1618 }
1619
1620 #[test]
1621 fn test_grmtools_section_yacckinds() {
1622 let srcs = [
1623 "%grmtools{yacckind: Original(NoAction)}
1624 %%
1625 Start: ;",
1626 "%grmtools{yacckind: YaccKind::Original(GenericParseTree)}
1627 %%
1628 Start: ;",
1629 "%grmtools{yacckind: YaccKind::Original(yaccoriginalactionkind::useraction)}
1630 %actiontype ()
1631 %%
1632 Start: ;",
1633 "%grmtools{yacckind: Original(YACCOriginalActionKind::NoAction)}
1634 %%
1635 Start: ;",
1636 "%grmtools{yacckind: YaccKind::Grmtools}
1637 %%
1638 Start -> () : ;",
1639 ];
1640 for src in srcs {
1641 YaccGrammar::<u32>::from_str(src).unwrap();
1642 }
1643 }
1644
1645 #[test]
1646 fn test_grmtools_section_invalid_yacckinds() {
1647 let srcs = [
1648 "%grmtools{yacckind: Foo}",
1649 "%grmtools{yacckind: YaccKind::Foo}",
1650 "%grmtools{yacckindof: YaccKind::Grmtools}",
1651 "%grmtools{yacckindof: Grmtools}",
1652 "%grmtools{yacckindof: YaccKindFoo::Foo}",
1653 "%grmtools{yacckind: Foo::Grmtools}",
1654 "%grmtools{yacckind: YaccKind::Original}",
1655 "%grmtools{yacckind: YaccKind::OriginalFoo}",
1656 "%grmtools{yacckind: YaccKind::Original()}",
1657 "%grmtools{yacckind: YaccKind::Original(Foo)}",
1658 "%grmtools{yacckind: YaccKind::Original(YaccOriginalActionKind)}",
1659 "%grmtools{yacckind: YaccKind::Original(YaccOriginalActionKind::Foo)}",
1660 "%grmtools{yacckind: YaccKind::Original(Foo::NoActions)}",
1661 "%grmtools{yacckind: YaccKind::Original(Foo::NoActionsBar)}",
1662 ];
1663
1664 for src in srcs {
1665 let s = format!("{}\n%%\nStart();\n", src);
1666 assert!(YaccGrammar::<u32>::from_str(&s).is_err());
1667 }
1668 }
1669
1670 #[test]
1671 fn test_grmtools_section_commas() {
1672 let src = r#"
1678 %grmtools{
1679 yacckind: YaccKind::Grmtools,
1680 }
1681 %%
1682 Start -> () : ;
1683 "#;
1684 YaccGrammar::<u32>::from_str(src).unwrap();
1685 let src = r#"
1686 %grmtools{
1687 yacckind: YaccKind::Grmtools
1688 }
1689 %%
1690 Start -> () : ;
1691 "#;
1692 YaccGrammar::<u32>::from_str(src).unwrap();
1693 }
1694}