crates/mbe/src/expander/matcher.rs

   1 //! An NFA-based parser, which is porting from rustc mbe parsing code
   2 //!
   3 //! See <https://github.com/rust-lang/rust/blob/70b18bc2cbac4712020019f5bf57c00905373205/compiler/rustc_expand/src/mbe/macro_parser.rs>
   4 //! Here is a quick intro to how the parser works, copied from rustc:
   5 //!
   6 //! A 'position' is a dot in the middle of a matcher, usually represented as a
   7 //! dot. For example `· a $( a )* a b` is a position, as is `a $( · a )* a b`.
   8 //!
   9 //! The parser walks through the input a character at a time, maintaining a list
  10 //! of threads consistent with the current position in the input string: `cur_items`.
  11 //!
  12 //! As it processes them, it fills up `eof_items` with threads that would be valid if
  13 //! the macro invocation is now over, `bb_items` with threads that are waiting on
  14 //! a Rust non-terminal like `$e:expr`, and `next_items` with threads that are waiting
  15 //! on a particular token. Most of the logic concerns moving the · through the
  16 //! repetitions indicated by Kleene stars. The rules for moving the · without
  17 //! consuming any input are called epsilon transitions. It only advances or calls
  18 //! out to the real Rust parser when no `cur_items` threads remain.
  19 //!
  20 //! Example:
  21 //!
  22 //! ```text, ignore
  23 //! Start parsing a a a a b against [· a $( a )* a b].
  24 //!
  25 //! Remaining input: a a a a b
  26 //! next: [· a $( a )* a b]
  27 //!
  28 //! - - - Advance over an a. - - -
  29 //!
  30 //! Remaining input: a a a b
  31 //! cur: [a · $( a )* a b]
  32 //! Descend/Skip (first item).
  33 //! next: [a $( · a )* a b]  [a $( a )* · a b].
  34 //!
  35 //! - - - Advance over an a. - - -
  36 //!
  37 //! Remaining input: a a b
  38 //! cur: [a $( a · )* a b]  [a $( a )* a · b]
  39 //! Follow epsilon transition: Finish/Repeat (first item)
  40 //! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
  41 //!
  42 //! - - - Advance over an a. - - - (this looks exactly like the last step)
  43 //!
  44 //! Remaining input: a b
  45 //! cur: [a $( a · )* a b]  [a $( a )* a · b]
  46 //! Follow epsilon transition: Finish/Repeat (first item)
  47 //! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
  48 //!
  49 //! - - - Advance over an a. - - - (this looks exactly like the last step)
  50 //!
  51 //! Remaining input: b
  52 //! cur: [a $( a · )* a b]  [a $( a )* a · b]
  53 //! Follow epsilon transition: Finish/Repeat (first item)
  54 //! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
  55 //!
  56 //! - - - Advance over a b. - - -
  57 //!
  58 //! Remaining input: ''
  59 //! eof: [a $( a )* a b ·]
  60 //! ```
  61
  62 use std::rc::Rc;
  63
  64 use crate::{
  65     expander::{Binding, Bindings, Fragment},
  66     parser::{Op, RepeatKind, Separator},
  67     tt_iter::TtIter,
  68     ExpandError, MetaTemplate,
  69 };
  70
  71 use super::ExpandResult;
  72 use parser::ParserEntryPoint::*;
  73 use smallvec::{smallvec, SmallVec};
  74 use syntax::SmolStr;
  75
  76 impl Bindings {
  77     fn push_optional(&mut self, name: &SmolStr) {
  78         // FIXME: Do we have a better way to represent an empty token ?
  79         // Insert an empty subtree for empty token
  80         let tt = tt::Subtree::default().into();
  81         self.inner.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt)));
  82     }
  83
  84     fn push_empty(&mut self, name: &SmolStr) {
  85         self.inner.insert(name.clone(), Binding::Empty);
  86     }
  87
  88     fn bindings(&self) -> impl Iterator<Item = &Binding> {
  89         self.inner.values()
  90     }
  91 }
  92
  93 macro_rules! err {
  94     () => {
  95         ExpandError::BindingError(format!(""))
  96     };
  97     ($($tt:tt)*) => {
  98         ExpandError::BindingError(format!($($tt)*))
  99     };
 100 }
 101
 102 #[derive(Clone, Debug, Default, PartialEq, Eq)]
 103 pub(super) struct Match {
 104     pub(super) bindings: Bindings,
 105     /// We currently just keep the first error and count the rest to compare matches.
 106     pub(super) err: Option<ExpandError>,
 107     pub(super) err_count: usize,
 108     /// How many top-level token trees were left to match.
 109     pub(super) unmatched_tts: usize,
 110     /// The number of bound variables
 111     pub(super) bound_count: usize,
 112 }
 113
 114 impl Match {
 115     fn add_err(&mut self, err: ExpandError) {
 116         let prev_err = self.err.take();
 117         self.err = prev_err.or(Some(err));
 118         self.err_count += 1;
 119     }
 120 }
 121
 122 /// Matching errors are added to the `Match`.
 123 pub(super) fn match_(pattern: &MetaTemplate, input: &tt::Subtree) -> Match {
 124     let mut res = match_loop(pattern, input);
 125     res.bound_count = count(res.bindings.bindings());
 126     return res;
 127
 128     fn count<'a>(bindings: impl Iterator<Item = &'a Binding>) -> usize {
 129         bindings
 130             .map(|it| match it {
 131                 Binding::Fragment(_) => 1,
 132                 Binding::Empty => 1,
 133                 Binding::Nested(it) => count(it.iter()),
 134             })
 135             .sum()
 136     }
 137 }
 138
 139 #[derive(Debug, Clone)]
 140 enum BindingKind {
 141     Empty(SmolStr),
 142     Optional(SmolStr),
 143     Fragment(SmolStr, Fragment),
 144     Nested(usize, usize),
 145 }
 146
 147 #[derive(Debug, Clone)]
 148 struct BindingsIdx(usize, usize);
 149
 150 #[derive(Debug, Clone)]
 151 enum LinkNode<T> {
 152     Node(T),
 153     Parent { idx: usize, len: usize },
 154 }
 155
 156 #[derive(Default)]
 157 struct BindingsBuilder {
 158     nodes: Vec<Vec<LinkNode<Rc<BindingKind>>>>,
 159     nested: Vec<Vec<LinkNode<usize>>>,
 160 }
 161
 162 impl BindingsBuilder {
 163     fn alloc(&mut self) -> BindingsIdx {
 164         let idx = self.nodes.len();
 165         self.nodes.push(Vec::new());
 166         let nidx = self.nested.len();
 167         self.nested.push(Vec::new());
 168         BindingsIdx(idx, nidx)
 169     }
 170
 171     fn copy(&mut self, bindings: &BindingsIdx) -> BindingsIdx {
 172         let idx = copy_parent(bindings.0, &mut self.nodes);
 173         let nidx = copy_parent(bindings.1, &mut self.nested);
 174         return BindingsIdx(idx, nidx);
 175
 176         fn copy_parent<T>(idx: usize, target: &mut Vec<Vec<LinkNode<T>>>) -> usize
 177         where
 178             T: Clone,
 179         {
 180             let new_idx = target.len();
 181             let len = target[idx].len();
 182             if len < 4 {
 183                 target.push(target[idx].clone())
 184             } else {
 185                 target.push(vec![LinkNode::Parent { idx, len }]);
 186             }
 187             new_idx
 188         }
 189     }
 190
 191     fn push_empty(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
 192         self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Empty(var.clone()))));
 193     }
 194
 195     fn push_optional(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
 196         self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Optional(var.clone()))));
 197     }
 198
 199     fn push_fragment(&mut self, idx: &mut BindingsIdx, var: &SmolStr, fragment: Fragment) {
 200         self.nodes[idx.0]
 201             .push(LinkNode::Node(Rc::new(BindingKind::Fragment(var.clone(), fragment))));
 202     }
 203
 204     fn push_nested(&mut self, parent: &mut BindingsIdx, child: &BindingsIdx) {
 205         let BindingsIdx(idx, nidx) = self.copy(child);
 206         self.nodes[parent.0].push(LinkNode::Node(Rc::new(BindingKind::Nested(idx, nidx))));
 207     }
 208
 209     fn push_default(&mut self, idx: &mut BindingsIdx) {
 210         self.nested[idx.1].push(LinkNode::Node(idx.0));
 211         let new_idx = self.nodes.len();
 212         self.nodes.push(Vec::new());
 213         idx.0 = new_idx;
 214     }
 215
 216     fn build(self, idx: &BindingsIdx) -> Bindings {
 217         let mut bindings = Bindings::default();
 218         self.build_inner(&mut bindings, &self.nodes[idx.0]);
 219         bindings
 220     }
 221
 222     fn build_inner(&self, bindings: &mut Bindings, link_nodes: &[LinkNode<Rc<BindingKind>>]) {
 223         let mut nodes = Vec::new();
 224         self.collect_nodes(link_nodes, &mut nodes);
 225
 226         for cmd in nodes {
 227             match &**cmd {
 228                 BindingKind::Empty(name) => {
 229                     bindings.push_empty(name);
 230                 }
 231                 BindingKind::Optional(name) => {
 232                     bindings.push_optional(name);
 233                 }
 234                 BindingKind::Fragment(name, fragment) => {
 235                     bindings.inner.insert(name.clone(), Binding::Fragment(fragment.clone()));
 236                 }
 237                 BindingKind::Nested(idx, nested_idx) => {
 238                     let mut nested_nodes = Vec::new();
 239                     self.collect_nested(*idx, *nested_idx, &mut nested_nodes);
 240
 241                     for (idx, iter) in nested_nodes.into_iter().enumerate() {
 242                         for (key, value) in &iter.inner {
 243                             let bindings = bindings
 244                                 .inner
 245                                 .entry(key.clone())
 246                                 .or_insert_with(|| Binding::Nested(Vec::new()));
 247
 248                             if let Binding::Nested(it) = bindings {
 249                                 // insert empty nested bindings before this one
 250                                 while it.len() < idx {
 251                                     it.push(Binding::Nested(Vec::new()));
 252                                 }
 253                                 it.push(value.clone());
 254                             }
 255                         }
 256                     }
 257                 }
 258             }
 259         }
 260     }
 261
 262     fn collect_nested_ref<'a>(
 263         &'a self,
 264         id: usize,
 265         len: usize,
 266         nested_refs: &mut Vec<&'a Vec<LinkNode<Rc<BindingKind>>>>,
 267     ) {
 268         self.nested[id].iter().take(len).for_each(|it| match it {
 269             LinkNode::Node(id) => nested_refs.push(&self.nodes[*id]),
 270             LinkNode::Parent { idx, len } => self.collect_nested_ref(*idx, *len, nested_refs),
 271         });
 272     }
 273
 274     fn collect_nested(&self, idx: usize, nested_idx: usize, nested: &mut Vec<Bindings>) {
 275         let last = &self.nodes[idx];
 276         let mut nested_refs = Vec::new();
 277         self.nested[nested_idx].iter().for_each(|it| match *it {
 278             LinkNode::Node(idx) => nested_refs.push(&self.nodes[idx]),
 279             LinkNode::Parent { idx, len } => self.collect_nested_ref(idx, len, &mut nested_refs),
 280         });
 281         nested_refs.push(last);
 282
 283         nested_refs.into_iter().for_each(|iter| {
 284             let mut child_bindings = Bindings::default();
 285             self.build_inner(&mut child_bindings, iter);
 286             nested.push(child_bindings)
 287         })
 288     }
 289
 290     fn collect_nodes_ref<'a>(
 291         &'a self,
 292         id: usize,
 293         len: usize,
 294         nodes: &mut Vec<&'a Rc<BindingKind>>,
 295     ) {
 296         self.nodes[id].iter().take(len).for_each(|it| match it {
 297             LinkNode::Node(it) => nodes.push(it),
 298             LinkNode::Parent { idx, len } => self.collect_nodes_ref(*idx, *len, nodes),
 299         });
 300     }
 301
 302     fn collect_nodes<'a>(
 303         &'a self,
 304         link_nodes: &'a [LinkNode<Rc<BindingKind>>],
 305         nodes: &mut Vec<&'a Rc<BindingKind>>,
 306     ) {
 307         link_nodes.iter().for_each(|it| match it {
 308             LinkNode::Node(it) => nodes.push(it),
 309             LinkNode::Parent { idx, len } => self.collect_nodes_ref(*idx, *len, nodes),
 310         });
 311     }
 312 }
 313
 314 #[derive(Debug, Clone)]
 315 struct MatchState<'t> {
 316     /// The position of the "dot" in this matcher
 317     dot: OpDelimitedIter<'t>,
 318
 319     /// Token subtree stack
 320     /// When matching against matchers with nested delimited submatchers (e.g., `pat ( pat ( .. )
 321     /// pat ) pat`), we need to keep track of the matchers we are descending into. This stack does
 322     /// that where the bottom of the stack is the outermost matcher.
 323     stack: SmallVec<[OpDelimitedIter<'t>; 4]>,
 324
 325     /// The "parent" matcher position if we are in a repetition. That is, the matcher position just
 326     /// before we enter the repetition.
 327     up: Option<Box<MatchState<'t>>>,
 328
 329     /// The separator if we are in a repetition.
 330     sep: Option<Separator>,
 331
 332     /// The KleeneOp of this sequence if we are in a repetition.
 333     sep_kind: Option<RepeatKind>,
 334
 335     /// Number of tokens of seperator parsed
 336     sep_parsed: Option<usize>,
 337
 338     /// Matched meta variables bindings
 339     bindings: BindingsIdx,
 340
 341     /// Cached result of meta variable parsing
 342     meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>,
 343
 344     /// Is error occuried in this state, will `poised` to "parent"
 345     is_error: bool,
 346 }
 347
 348 /// Process the matcher positions of `cur_items` until it is empty. In the process, this will
 349 /// produce more items in `next_items`, `eof_items`, and `bb_items`.
 350 ///
 351 /// For more info about the how this happens, see the module-level doc comments and the inline
 352 /// comments of this function.
 353 ///
 354 /// # Parameters
 355 ///
 356 /// - `src`: the current token of the parser.
 357 /// - `stack`: the "parent" frames of the token tree
 358 /// - `res`: the match result to store errors
 359 /// - `cur_items`: the set of current items to be processed. This should be empty by the end of a
 360 ///   successful execution of this function.
 361 /// - `next_items`: the set of newly generated items. These are used to replenish `cur_items` in
 362 ///   the function `parse`.
 363 /// - `eof_items`: the set of items that would be valid if this was the EOF.
 364 /// - `bb_items`: the set of items that are waiting for the black-box parser.
 365 /// - `error_items`: the set of items in errors, used for error-resilient parsing
 366 fn match_loop_inner<'t>(
 367     src: TtIter<'t>,
 368     stack: &[TtIter<'t>],
 369     res: &mut Match,
 370     bindings_builder: &mut BindingsBuilder,
 371     cur_items: &mut SmallVec<[MatchState<'t>; 1]>,
 372     bb_items: &mut SmallVec<[MatchState<'t>; 1]>,
 373     next_items: &mut Vec<MatchState<'t>>,
 374     eof_items: &mut SmallVec<[MatchState<'t>; 1]>,
 375     error_items: &mut SmallVec<[MatchState<'t>; 1]>,
 376 ) {
 377     macro_rules! try_push {
 378         ($items: expr, $it:expr) => {
 379             if $it.is_error {
 380                 error_items.push($it);
 381             } else {
 382                 $items.push($it);
 383             }
 384         };
 385     }
 386
 387     while let Some(mut item) = cur_items.pop() {
 388         while item.dot.is_eof() {
 389             match item.stack.pop() {
 390                 Some(frame) => {
 391                     item.dot = frame;
 392                     item.dot.next();
 393                 }
 394                 None => break,
 395             }
 396         }
 397         let op = match item.dot.peek() {
 398             None => {
 399                 // We are at or past the end of the matcher of `item`.
 400                 if item.up.is_some() {
 401                     if item.sep_parsed.is_none() {
 402                         // Get the `up` matcher
 403                         let mut new_pos = *item.up.clone().unwrap();
 404                         new_pos.bindings = bindings_builder.copy(&new_pos.bindings);
 405                         // Add matches from this repetition to the `matches` of `up`
 406                         bindings_builder.push_nested(&mut new_pos.bindings, &item.bindings);
 407
 408                         // Move the "dot" past the repetition in `up`
 409                         new_pos.dot.next();
 410                         new_pos.is_error = new_pos.is_error || item.is_error;
 411                         cur_items.push(new_pos);
 412                     }
 413
 414                     // Check if we need a separator.
 415                     // We check the separator one by one
 416                     let sep_idx = *item.sep_parsed.as_ref().unwrap_or(&0);
 417                     let sep_len = item.sep.as_ref().map_or(0, Separator::tt_count);
 418                     if item.sep.is_some() && sep_idx != sep_len {
 419                         let sep = item.sep.as_ref().unwrap();
 420                         if src.clone().expect_separator(sep, sep_idx) {
 421                             item.dot.next();
 422                             item.sep_parsed = Some(sep_idx + 1);
 423                             try_push!(next_items, item);
 424                         }
 425                     }
 426                     // We don't need a separator. Move the "dot" back to the beginning of the matcher
 427                     // and try to match again UNLESS we are only allowed to have _one_ repetition.
 428                     else if item.sep_kind != Some(RepeatKind::ZeroOrOne) {
 429                         item.dot = item.dot.reset();
 430                         item.sep_parsed = None;
 431                         bindings_builder.push_default(&mut item.bindings);
 432                         cur_items.push(item);
 433                     }
 434                 } else {
 435                     // If we are not in a repetition, then being at the end of a matcher means that we have
 436                     // reached the potential end of the input.
 437                     try_push!(eof_items, item);
 438                 }
 439                 continue;
 440             }
 441             Some(it) => it,
 442         };
 443
 444         // We are in the middle of a matcher.
 445         match op {
 446             OpDelimited::Op(Op::Repeat { tokens, kind, separator }) => {
 447                 if matches!(kind, RepeatKind::ZeroOrMore | RepeatKind::ZeroOrOne) {
 448                     let mut new_item = item.clone();
 449                     new_item.bindings = bindings_builder.copy(&new_item.bindings);
 450                     new_item.dot.next();
 451                     let mut vars = Vec::new();
 452                     collect_vars(&mut vars, tokens);
 453                     for var in vars {
 454                         bindings_builder.push_empty(&mut new_item.bindings, &var);
 455                     }
 456                     cur_items.push(new_item);
 457                 }
 458                 cur_items.push(MatchState {
 459                     dot: tokens.iter_delimited(None),
 460                     stack: Default::default(),
 461                     up: Some(Box::new(item)),
 462                     sep: separator.clone(),
 463                     sep_kind: Some(*kind),
 464                     sep_parsed: None,
 465                     bindings: bindings_builder.alloc(),
 466                     meta_result: None,
 467                     is_error: false,
 468                 })
 469             }
 470             OpDelimited::Op(Op::Subtree { tokens, delimiter }) => {
 471                 if let Ok(subtree) = src.clone().expect_subtree() {
 472                     if subtree.delimiter_kind() == delimiter.map(|it| it.kind) {
 473                         item.stack.push(item.dot);
 474                         item.dot = tokens.iter_delimited(delimiter.as_ref());
 475                         cur_items.push(item);
 476                     }
 477                 }
 478             }
 479             OpDelimited::Op(Op::Var { kind, name, .. }) => {
 480                 if let Some(kind) = kind {
 481                     let mut fork = src.clone();
 482                     let match_res = match_meta_var(kind.as_str(), &mut fork);
 483                     match match_res.err {
 484                         None => {
 485                             // Some meta variables are optional (e.g. vis)
 486                             if match_res.value.is_some() {
 487                                 item.meta_result = Some((fork, match_res));
 488                                 try_push!(bb_items, item);
 489                             } else {
 490                                 bindings_builder.push_optional(&mut item.bindings, name);
 491                                 item.dot.next();
 492                                 cur_items.push(item);
 493                             }
 494                         }
 495                         Some(err) => {
 496                             res.add_err(err);
 497                             if let Some(fragment) = match_res.value {
 498                                 bindings_builder.push_fragment(&mut item.bindings, name, fragment);
 499                             }
 500                             item.is_error = true;
 501                             error_items.push(item);
 502                         }
 503                     }
 504                 }
 505             }
 506             OpDelimited::Op(Op::Leaf(leaf)) => {
 507                 if let Err(err) = match_leaf(leaf, &mut src.clone()) {
 508                     res.add_err(err);
 509                     item.is_error = true;
 510                 } else {
 511                     item.dot.next();
 512                 }
 513                 try_push!(next_items, item);
 514             }
 515             OpDelimited::Open => {
 516                 if matches!(src.clone().next(), Some(tt::TokenTree::Subtree(..))) {
 517                     item.dot.next();
 518                     try_push!(next_items, item);
 519                 }
 520             }
 521             OpDelimited::Close => {
 522                 let is_delim_closed = src.peek_n(0).is_none() && !stack.is_empty();
 523                 if is_delim_closed {
 524                     item.dot.next();
 525                     try_push!(next_items, item);
 526                 }
 527             }
 528         }
 529     }
 530 }
 531
 532 fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
 533     let mut src = TtIter::new(src);
 534     let mut stack: SmallVec<[TtIter; 1]> = SmallVec::new();
 535     let mut res = Match::default();
 536     let mut error_recover_item = None;
 537
 538     let mut bindings_builder = BindingsBuilder::default();
 539
 540     let mut cur_items = smallvec![MatchState {
 541         dot: pattern.iter_delimited(None),
 542         stack: Default::default(),
 543         up: None,
 544         sep: None,
 545         sep_kind: None,
 546         sep_parsed: None,
 547         bindings: bindings_builder.alloc(),
 548         is_error: false,
 549         meta_result: None,
 550     }];
 551
 552     let mut next_items = vec![];
 553
 554     loop {
 555         let mut bb_items = SmallVec::new();
 556         let mut eof_items = SmallVec::new();
 557         let mut error_items = SmallVec::new();
 558
 559         stdx::always!(next_items.is_empty());
 560
 561         match_loop_inner(
 562             src.clone(),
 563             &stack,
 564             &mut res,
 565             &mut bindings_builder,
 566             &mut cur_items,
 567             &mut bb_items,
 568             &mut next_items,
 569             &mut eof_items,
 570             &mut error_items,
 571         );
 572         stdx::always!(cur_items.is_empty());
 573
 574         if !error_items.is_empty() {
 575             error_recover_item = error_items.pop().map(|it| it.bindings);
 576         } else if !eof_items.is_empty() {
 577             error_recover_item = Some(eof_items[0].bindings.clone());
 578         }
 579
 580         // We need to do some post processing after the `match_loop_inner`.
 581         // If we reached the EOF, check that there is EXACTLY ONE possible matcher. Otherwise,
 582         // either the parse is ambiguous (which should never happen) or there is a syntax error.
 583         if src.peek_n(0).is_none() && stack.is_empty() {
 584             if eof_items.len() == 1 {
 585                 // remove all errors, because it is the correct answer !
 586                 res = Match::default();
 587                 res.bindings = bindings_builder.build(&eof_items[0].bindings);
 588             } else {
 589                 // Error recovery
 590                 if let Some(item) = error_recover_item {
 591                     res.bindings = bindings_builder.build(&item);
 592                 }
 593                 res.add_err(ExpandError::UnexpectedToken);
 594             }
 595             return res;
 596         }
 597
 598         // If there are no possible next positions AND we aren't waiting for the black-box parser,
 599         // then there is a syntax error.
 600         //
 601         // Another possibility is that we need to call out to parse some rust nonterminal
 602         // (black-box) parser. However, if there is not EXACTLY ONE of these, something is wrong.
 603         if (bb_items.is_empty() && next_items.is_empty())
 604             || (!bb_items.is_empty() && !next_items.is_empty())
 605             || bb_items.len() > 1
 606         {
 607             res.unmatched_tts += src.len();
 608             while let Some(it) = stack.pop() {
 609                 src = it;
 610                 res.unmatched_tts += src.len();
 611             }
 612             res.add_err(err!("leftover tokens"));
 613
 614             if let Some(error_reover_item) = error_recover_item {
 615                 res.bindings = bindings_builder.build(&error_reover_item);
 616             }
 617             return res;
 618         }
 619         // Dump all possible `next_items` into `cur_items` for the next iteration.
 620         else if !next_items.is_empty() {
 621             // Now process the next token
 622             cur_items.extend(next_items.drain(..));
 623
 624             match src.next() {
 625                 Some(tt::TokenTree::Subtree(subtree)) => {
 626                     stack.push(src.clone());
 627                     src = TtIter::new(subtree);
 628                 }
 629                 None if !stack.is_empty() => src = stack.pop().unwrap(),
 630                 _ => (),
 631             }
 632         }
 633         // Finally, we have the case where we need to call the black-box parser to get some
 634         // nonterminal.
 635         else {
 636             stdx::always!(bb_items.len() == 1);
 637             let mut item = bb_items.pop().unwrap();
 638
 639             if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() {
 640                 let (iter, match_res) = item.meta_result.take().unwrap();
 641                 match match_res.value {
 642                     Some(fragment) => {
 643                         bindings_builder.push_fragment(&mut item.bindings, name, fragment);
 644                     }
 645                     None if match_res.err.is_none() => {
 646                         bindings_builder.push_optional(&mut item.bindings, name);
 647                     }
 648                     None => {}
 649                 }
 650                 if let Some(err) = match_res.err {
 651                     res.add_err(err);
 652                 }
 653                 src = iter.clone();
 654                 item.dot.next();
 655             } else {
 656                 unreachable!()
 657             }
 658             cur_items.push(item);
 659         }
 660         stdx::always!(!cur_items.is_empty());
 661     }
 662 }
 663
 664 fn match_leaf(lhs: &tt::Leaf, src: &mut TtIter) -> Result<(), ExpandError> {
 665     let rhs = match src.expect_leaf() {
 666         Ok(l) => l,
 667         Err(()) => {
 668             return Err(err!("expected leaf: `{}`", lhs));
 669         }
 670     };
 671     match (lhs, rhs) {
 672         (
 673             tt::Leaf::Punct(tt::Punct { char: lhs, .. }),
 674             tt::Leaf::Punct(tt::Punct { char: rhs, .. }),
 675         ) if lhs == rhs => (),
 676         (
 677             tt::Leaf::Ident(tt::Ident { text: lhs, .. }),
 678             tt::Leaf::Ident(tt::Ident { text: rhs, .. }),
 679         ) if lhs == rhs => (),
 680         (
 681             tt::Leaf::Literal(tt::Literal { text: lhs, .. }),
 682             tt::Leaf::Literal(tt::Literal { text: rhs, .. }),
 683         ) if lhs == rhs => (),
 684         _ => {
 685             return Err(ExpandError::UnexpectedToken);
 686         }
 687     }
 688
 689     Ok(())
 690 }
 691
 692 fn match_meta_var(kind: &str, input: &mut TtIter) -> ExpandResult<Option<Fragment>> {
 693     let fragment = match kind {
 694         "path" => Path,
 695         "expr" => Expr,
 696         "ty" => Type,
 697         "pat" | "pat_param" => Pattern, // FIXME: edition2021
 698         "stmt" => Statement,
 699         "block" => Block,
 700         "meta" => MetaItem,
 701         "item" => Item,
 702         _ => {
 703             let tt_result = match kind {
 704                 "ident" => input
 705                     .expect_ident()
 706                     .map(|ident| Some(tt::Leaf::from(ident.clone()).into()))
 707                     .map_err(|()| err!("expected ident")),
 708                 "tt" => input.expect_tt().map(Some).map_err(|()| err!()),
 709                 "lifetime" => {
 710                     input.expect_lifetime().map(Some).map_err(|()| err!("expected lifetime"))
 711                 }
 712                 "literal" => {
 713                     let neg = input.eat_char('-');
 714                     input
 715                         .expect_literal()
 716                         .map(|literal| {
 717                             let lit = literal.clone();
 718                             match neg {
 719                                 None => Some(lit.into()),
 720                                 Some(neg) => Some(tt::TokenTree::Subtree(tt::Subtree {
 721                                     delimiter: None,
 722                                     token_trees: vec![neg, lit.into()],
 723                                 })),
 724                             }
 725                         })
 726                         .map_err(|()| err!())
 727                 }
 728                 // `vis` is optional
 729                 "vis" => Ok(input.eat_vis()),
 730                 _ => Err(ExpandError::UnexpectedToken),
 731             };
 732             return tt_result.map(|it| it.map(Fragment::Tokens)).into();
 733         }
 734     };
 735     let result = input.expect_fragment(fragment);
 736     result.map(|tt| if kind == "expr" { tt.map(Fragment::Expr) } else { tt.map(Fragment::Tokens) })
 737 }
 738
 739 fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &MetaTemplate) {
 740     for op in pattern.iter() {
 741         match op {
 742             Op::Var { name, .. } => buf.push(name.clone()),
 743             Op::Leaf(_) => (),
 744             Op::Subtree { tokens, .. } => collect_vars(buf, tokens),
 745             Op::Repeat { tokens, .. } => collect_vars(buf, tokens),
 746         }
 747     }
 748 }
 749
 750 impl MetaTemplate {
 751     fn iter_delimited<'a>(&'a self, delimited: Option<&'a tt::Delimiter>) -> OpDelimitedIter<'a> {
 752         OpDelimitedIter { inner: &self.0, idx: 0, delimited }
 753     }
 754 }
 755
 756 #[derive(Debug, Clone, Copy)]
 757 enum OpDelimited<'a> {
 758     Op(&'a Op),
 759     Open,
 760     Close,
 761 }
 762
 763 #[derive(Debug, Clone, Copy)]
 764 struct OpDelimitedIter<'a> {
 765     inner: &'a [Op],
 766     delimited: Option<&'a tt::Delimiter>,
 767     idx: usize,
 768 }
 769
 770 impl<'a> OpDelimitedIter<'a> {
 771     fn is_eof(&self) -> bool {
 772         let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
 773         self.idx >= len
 774     }
 775
 776     fn peek(&self) -> Option<OpDelimited<'a>> {
 777         match self.delimited {
 778             None => self.inner.get(self.idx).map(OpDelimited::Op),
 779             Some(_) => match self.idx {
 780                 0 => Some(OpDelimited::Open),
 781                 i if i == self.inner.len() + 1 => Some(OpDelimited::Close),
 782                 i => self.inner.get(i - 1).map(OpDelimited::Op),
 783             },
 784         }
 785     }
 786
 787     fn reset(&self) -> Self {
 788         Self { inner: self.inner, idx: 0, delimited: self.delimited }
 789     }
 790 }
 791
 792 impl<'a> Iterator for OpDelimitedIter<'a> {
 793     type Item = OpDelimited<'a>;
 794
 795     fn next(&mut self) -> Option<Self::Item> {
 796         let res = self.peek();
 797         self.idx += 1;
 798         res
 799     }
 800
 801     fn size_hint(&self) -> (usize, Option<usize>) {
 802         let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
 803         let remain = len.saturating_sub(self.idx);
 804         (remain, Some(remain))
 805     }
 806 }
 807
 808 impl<'a> TtIter<'a> {
 809     fn expect_separator(&mut self, separator: &Separator, idx: usize) -> bool {
 810         let mut fork = self.clone();
 811         let ok = match separator {
 812             Separator::Ident(lhs) if idx == 0 => match fork.expect_ident_or_underscore() {
 813                 Ok(rhs) => rhs.text == lhs.text,
 814                 Err(_) => false,
 815             },
 816             Separator::Literal(lhs) if idx == 0 => match fork.expect_literal() {
 817                 Ok(rhs) => match rhs {
 818                     tt::Leaf::Literal(rhs) => rhs.text == lhs.text,
 819                     tt::Leaf::Ident(rhs) => rhs.text == lhs.text,
 820                     tt::Leaf::Punct(_) => false,
 821                 },
 822                 Err(_) => false,
 823             },
 824             Separator::Puncts(lhss) if idx < lhss.len() => match fork.expect_punct() {
 825                 Ok(rhs) => rhs.char == lhss[idx].char,
 826                 Err(_) => false,
 827             },
 828             _ => false,
 829         };
 830         if ok {
 831             *self = fork;
 832         }
 833         ok
 834     }
 835
 836     fn expect_tt(&mut self) -> Result<tt::TokenTree, ()> {
 837         match self.peek_n(0) {
 838             Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) if punct.char == '\'' => {
 839                 return self.expect_lifetime();
 840             }
 841             _ => (),
 842         }
 843
 844         let tt = self.next().ok_or(())?.clone();
 845         let punct = match tt {
 846             tt::TokenTree::Leaf(tt::Leaf::Punct(punct)) if punct.spacing == tt::Spacing::Joint => {
 847                 punct
 848             }
 849             _ => return Ok(tt),
 850         };
 851
 852         let (second, third) = match (self.peek_n(0), self.peek_n(1)) {
 853             (
 854                 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))),
 855                 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p3))),
 856             ) if p2.spacing == tt::Spacing::Joint => (p2.char, Some(p3.char)),
 857             (Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))), _) => (p2.char, None),
 858             _ => return Ok(tt),
 859         };
 860
 861         match (punct.char, second, third) {
 862             ('.', '.', Some('.' | '=')) | ('<', '<', Some('=')) | ('>', '>', Some('=')) => {
 863                 let tt2 = self.next().unwrap().clone();
 864                 let tt3 = self.next().unwrap().clone();
 865                 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2, tt3] }.into())
 866             }
 867             ('-' | '!' | '*' | '/' | '&' | '%' | '^' | '+' | '<' | '=' | '>' | '|', '=', _)
 868             | ('-' | '=' | '>', '>', _)
 869             | (':', ':', _)
 870             | ('.', '.', _)
 871             | ('&', '&', _)
 872             | ('<', '<', _)
 873             | ('|', '|', _) => {
 874                 let tt2 = self.next().unwrap().clone();
 875                 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2] }.into())
 876             }
 877             _ => Ok(tt),
 878         }
 879     }
 880
 881     fn expect_lifetime(&mut self) -> Result<tt::TokenTree, ()> {
 882         let punct = self.expect_punct()?;
 883         if punct.char != '\'' {
 884             return Err(());
 885         }
 886         let ident = self.expect_ident_or_underscore()?;
 887
 888         Ok(tt::Subtree {
 889             delimiter: None,
 890             token_trees: vec![
 891                 tt::Leaf::Punct(*punct).into(),
 892                 tt::Leaf::Ident(ident.clone()).into(),
 893             ],
 894         }
 895         .into())
 896     }
 897
 898     fn eat_vis(&mut self) -> Option<tt::TokenTree> {
 899         self.expect_fragment(Visibility).value
 900     }
 901
 902     fn eat_char(&mut self, c: char) -> Option<tt::TokenTree> {
 903         let mut fork = self.clone();
 904         match fork.expect_char(c) {
 905             Ok(_) => {
 906                 let tt = self.next().cloned();
 907                 *self = fork;
 908                 tt
 909             }
 910             Err(_) => None,
 911         }
 912     }
 913 }