src/tools/rust-analyzer/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 smallvec::{smallvec, SmallVec};
  65 use syntax::SmolStr;
  66
  67 use crate::{
  68     expander::{Binding, Bindings, ExpandResult, Fragment},
  69     parser::{MetaVarKind, Op, RepeatKind, Separator},
  70     tt,
  71     tt_iter::TtIter,
  72     ExpandError, MetaTemplate, ValueResult,
  73 };
  74
  75 impl Bindings {
  76     fn push_optional(&mut self, name: &SmolStr) {
  77         // FIXME: Do we have a better way to represent an empty token ?
  78         // Insert an empty subtree for empty token
  79         let tt =
  80             tt::Subtree { delimiter: tt::Delimiter::unspecified(), token_trees: vec![] }.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 #[derive(Clone, Debug, Default, PartialEq, Eq)]
  94 pub(super) struct Match {
  95     pub(super) bindings: Bindings,
  96     /// We currently just keep the first error and count the rest to compare matches.
  97     pub(super) err: Option<ExpandError>,
  98     pub(super) err_count: usize,
  99     /// How many top-level token trees were left to match.
 100     pub(super) unmatched_tts: usize,
 101     /// The number of bound variables
 102     pub(super) bound_count: usize,
 103 }
 104
 105 impl Match {
 106     fn add_err(&mut self, err: ExpandError) {
 107         let prev_err = self.err.take();
 108         self.err = prev_err.or(Some(err));
 109         self.err_count += 1;
 110     }
 111 }
 112
 113 /// Matching errors are added to the `Match`.
 114 pub(super) fn match_(pattern: &MetaTemplate, input: &tt::Subtree) -> Match {
 115     let mut res = match_loop(pattern, input);
 116     res.bound_count = count(res.bindings.bindings());
 117     return res;
 118
 119     fn count<'a>(bindings: impl Iterator<Item = &'a Binding>) -> usize {
 120         bindings
 121             .map(|it| match it {
 122                 Binding::Fragment(_) => 1,
 123                 Binding::Empty => 1,
 124                 Binding::Missing(_) => 1,
 125                 Binding::Nested(it) => count(it.iter()),
 126             })
 127             .sum()
 128     }
 129 }
 130
 131 #[derive(Debug, Clone)]
 132 enum BindingKind {
 133     Empty(SmolStr),
 134     Optional(SmolStr),
 135     Fragment(SmolStr, Fragment),
 136     Missing(SmolStr, MetaVarKind),
 137     Nested(usize, usize),
 138 }
 139
 140 #[derive(Debug, Clone)]
 141 struct BindingsIdx(usize, usize);
 142
 143 #[derive(Debug, Clone)]
 144 enum LinkNode<T> {
 145     Node(T),
 146     Parent { idx: usize, len: usize },
 147 }
 148
 149 #[derive(Default)]
 150 struct BindingsBuilder {
 151     nodes: Vec<Vec<LinkNode<Rc<BindingKind>>>>,
 152     nested: Vec<Vec<LinkNode<usize>>>,
 153 }
 154
 155 impl BindingsBuilder {
 156     fn alloc(&mut self) -> BindingsIdx {
 157         let idx = self.nodes.len();
 158         self.nodes.push(Vec::new());
 159         let nidx = self.nested.len();
 160         self.nested.push(Vec::new());
 161         BindingsIdx(idx, nidx)
 162     }
 163
 164     fn copy(&mut self, bindings: &BindingsIdx) -> BindingsIdx {
 165         let idx = copy_parent(bindings.0, &mut self.nodes);
 166         let nidx = copy_parent(bindings.1, &mut self.nested);
 167         return BindingsIdx(idx, nidx);
 168
 169         fn copy_parent<T>(idx: usize, target: &mut Vec<Vec<LinkNode<T>>>) -> usize
 170         where
 171             T: Clone,
 172         {
 173             let new_idx = target.len();
 174             let len = target[idx].len();
 175             if len < 4 {
 176                 target.push(target[idx].clone())
 177             } else {
 178                 target.push(vec![LinkNode::Parent { idx, len }]);
 179             }
 180             new_idx
 181         }
 182     }
 183
 184     fn push_empty(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
 185         self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Empty(var.clone()))));
 186     }
 187
 188     fn push_optional(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
 189         self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Optional(var.clone()))));
 190     }
 191
 192     fn push_fragment(&mut self, idx: &mut BindingsIdx, var: &SmolStr, fragment: Fragment) {
 193         self.nodes[idx.0]
 194             .push(LinkNode::Node(Rc::new(BindingKind::Fragment(var.clone(), fragment))));
 195     }
 196
 197     fn push_missing(&mut self, idx: &mut BindingsIdx, var: &SmolStr, kind: MetaVarKind) {
 198         self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Missing(var.clone(), kind))));
 199     }
 200
 201     fn push_nested(&mut self, parent: &mut BindingsIdx, child: &BindingsIdx) {
 202         let BindingsIdx(idx, nidx) = self.copy(child);
 203         self.nodes[parent.0].push(LinkNode::Node(Rc::new(BindingKind::Nested(idx, nidx))));
 204     }
 205
 206     fn push_default(&mut self, idx: &mut BindingsIdx) {
 207         self.nested[idx.1].push(LinkNode::Node(idx.0));
 208         let new_idx = self.nodes.len();
 209         self.nodes.push(Vec::new());
 210         idx.0 = new_idx;
 211     }
 212
 213     fn build(self, idx: &BindingsIdx) -> Bindings {
 214         self.build_inner(&self.nodes[idx.0])
 215     }
 216
 217     fn build_inner(&self, link_nodes: &[LinkNode<Rc<BindingKind>>]) -> Bindings {
 218         let mut bindings = Bindings::default();
 219         let mut nodes = Vec::new();
 220         self.collect_nodes(link_nodes, &mut nodes);
 221
 222         for cmd in nodes {
 223             match cmd {
 224                 BindingKind::Empty(name) => {
 225                     bindings.push_empty(name);
 226                 }
 227                 BindingKind::Optional(name) => {
 228                     bindings.push_optional(name);
 229                 }
 230                 BindingKind::Fragment(name, fragment) => {
 231                     bindings.inner.insert(name.clone(), Binding::Fragment(fragment.clone()));
 232                 }
 233                 BindingKind::Missing(name, kind) => {
 234                     bindings.inner.insert(name.clone(), Binding::Missing(*kind));
 235                 }
 236                 BindingKind::Nested(idx, nested_idx) => {
 237                     let mut nested_nodes = Vec::new();
 238                     self.collect_nested(*idx, *nested_idx, &mut nested_nodes);
 239
 240                     for (idx, iter) in nested_nodes.into_iter().enumerate() {
 241                         for (key, value) in &iter.inner {
 242                             let bindings = bindings
 243                                 .inner
 244                                 .entry(key.clone())
 245                                 .or_insert_with(|| Binding::Nested(Vec::new()));
 246
 247                             if let Binding::Nested(it) = bindings {
 248                                 // insert empty nested bindings before this one
 249                                 while it.len() < idx {
 250                                     it.push(Binding::Nested(Vec::new()));
 251                                 }
 252                                 it.push(value.clone());
 253                             }
 254                         }
 255                     }
 256                 }
 257             }
 258         }
 259
 260         bindings
 261     }
 262
 263     fn collect_nested_ref<'a>(
 264         &'a self,
 265         id: usize,
 266         len: usize,
 267         nested_refs: &mut Vec<&'a [LinkNode<Rc<BindingKind>>]>,
 268     ) {
 269         self.nested[id].iter().take(len).for_each(|it| match it {
 270             LinkNode::Node(id) => nested_refs.push(&self.nodes[*id]),
 271             LinkNode::Parent { idx, len } => self.collect_nested_ref(*idx, *len, nested_refs),
 272         });
 273     }
 274
 275     fn collect_nested(&self, idx: usize, nested_idx: usize, nested: &mut Vec<Bindings>) {
 276         let last = &self.nodes[idx];
 277         let mut nested_refs: Vec<&[_]> = Vec::new();
 278         self.nested[nested_idx].iter().for_each(|it| match *it {
 279             LinkNode::Node(idx) => nested_refs.push(&self.nodes[idx]),
 280             LinkNode::Parent { idx, len } => self.collect_nested_ref(idx, len, &mut nested_refs),
 281         });
 282         nested_refs.push(last);
 283         nested.extend(nested_refs.into_iter().map(|iter| self.build_inner(iter)));
 284     }
 285
 286     fn collect_nodes_ref<'a>(&'a self, id: usize, len: usize, nodes: &mut Vec<&'a BindingKind>) {
 287         self.nodes[id].iter().take(len).for_each(|it| match it {
 288             LinkNode::Node(it) => nodes.push(it),
 289             LinkNode::Parent { idx, len } => self.collect_nodes_ref(*idx, *len, nodes),
 290         });
 291     }
 292
 293     fn collect_nodes<'a>(
 294         &'a self,
 295         link_nodes: &'a [LinkNode<Rc<BindingKind>>],
 296         nodes: &mut Vec<&'a BindingKind>,
 297     ) {
 298         link_nodes.iter().for_each(|it| match it {
 299             LinkNode::Node(it) => nodes.push(it),
 300             LinkNode::Parent { idx, len } => self.collect_nodes_ref(*idx, *len, nodes),
 301         });
 302     }
 303 }
 304
 305 #[derive(Debug, Clone)]
 306 struct MatchState<'t> {
 307     /// The position of the "dot" in this matcher
 308     dot: OpDelimitedIter<'t>,
 309
 310     /// Token subtree stack
 311     /// When matching against matchers with nested delimited submatchers (e.g., `pat ( pat ( .. )
 312     /// pat ) pat`), we need to keep track of the matchers we are descending into. This stack does
 313     /// that where the bottom of the stack is the outermost matcher.
 314     stack: SmallVec<[OpDelimitedIter<'t>; 4]>,
 315
 316     /// The "parent" matcher position if we are in a repetition. That is, the matcher position just
 317     /// before we enter the repetition.
 318     up: Option<Box<MatchState<'t>>>,
 319
 320     /// The separator if we are in a repetition.
 321     sep: Option<Separator>,
 322
 323     /// The KleeneOp of this sequence if we are in a repetition.
 324     sep_kind: Option<RepeatKind>,
 325
 326     /// Whether we already matched separator token.
 327     sep_matched: bool,
 328
 329     /// Matched meta variables bindings
 330     bindings: BindingsIdx,
 331
 332     /// Cached result of meta variable parsing
 333     meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>,
 334
 335     /// Is error occuried in this state, will `poised` to "parent"
 336     is_error: bool,
 337 }
 338
 339 /// Process the matcher positions of `cur_items` until it is empty. In the process, this will
 340 /// produce more items in `next_items`, `eof_items`, and `bb_items`.
 341 ///
 342 /// For more info about the how this happens, see the module-level doc comments and the inline
 343 /// comments of this function.
 344 ///
 345 /// # Parameters
 346 ///
 347 /// - `src`: the current token of the parser.
 348 /// - `stack`: the "parent" frames of the token tree
 349 /// - `res`: the match result to store errors
 350 /// - `cur_items`: the set of current items to be processed. This should be empty by the end of a
 351 ///   successful execution of this function.
 352 /// - `next_items`: the set of newly generated items. These are used to replenish `cur_items` in
 353 ///   the function `parse`.
 354 /// - `eof_items`: the set of items that would be valid if this was the EOF.
 355 /// - `bb_items`: the set of items that are waiting for the black-box parser.
 356 /// - `error_items`: the set of items in errors, used for error-resilient parsing
 357 fn match_loop_inner<'t>(
 358     src: TtIter<'t>,
 359     stack: &[TtIter<'t>],
 360     res: &mut Match,
 361     bindings_builder: &mut BindingsBuilder,
 362     cur_items: &mut SmallVec<[MatchState<'t>; 1]>,
 363     bb_items: &mut SmallVec<[MatchState<'t>; 1]>,
 364     next_items: &mut Vec<MatchState<'t>>,
 365     eof_items: &mut SmallVec<[MatchState<'t>; 1]>,
 366     error_items: &mut SmallVec<[MatchState<'t>; 1]>,
 367 ) {
 368     macro_rules! try_push {
 369         ($items: expr, $it:expr) => {
 370             if $it.is_error {
 371                 error_items.push($it);
 372             } else {
 373                 $items.push($it);
 374             }
 375         };
 376     }
 377
 378     while let Some(mut item) = cur_items.pop() {
 379         while item.dot.is_eof() {
 380             match item.stack.pop() {
 381                 Some(frame) => {
 382                     item.dot = frame;
 383                     item.dot.next();
 384                 }
 385                 None => break,
 386             }
 387         }
 388         let op = match item.dot.peek() {
 389             None => {
 390                 // We are at or past the end of the matcher of `item`.
 391                 if let Some(up) = &item.up {
 392                     if !item.sep_matched {
 393                         // Get the `up` matcher
 394                         let mut new_pos = (**up).clone();
 395                         new_pos.bindings = bindings_builder.copy(&new_pos.bindings);
 396                         // Add matches from this repetition to the `matches` of `up`
 397                         bindings_builder.push_nested(&mut new_pos.bindings, &item.bindings);
 398
 399                         // Move the "dot" past the repetition in `up`
 400                         new_pos.dot.next();
 401                         new_pos.is_error = new_pos.is_error || item.is_error;
 402                         cur_items.push(new_pos);
 403                     }
 404
 405                     // Check if we need a separator.
 406                     if item.sep.is_some() && !item.sep_matched {
 407                         let sep = item.sep.as_ref().unwrap();
 408                         let mut fork = src.clone();
 409                         if fork.expect_separator(sep) {
 410                             // HACK: here we use `meta_result` to pass `TtIter` back to caller because
 411                             // it might have been advanced multiple times. `ValueResult` is
 412                             // insignificant.
 413                             item.meta_result = Some((fork, ValueResult::ok(None)));
 414                             item.dot.next();
 415                             // item.sep_parsed = Some(sep_len);
 416                             item.sep_matched = true;
 417                             try_push!(next_items, item);
 418                         }
 419                     }
 420                     // We don't need a separator. Move the "dot" back to the beginning of the matcher
 421                     // and try to match again UNLESS we are only allowed to have _one_ repetition.
 422                     else if item.sep_kind != Some(RepeatKind::ZeroOrOne) {
 423                         item.dot = item.dot.reset();
 424                         item.sep_matched = false;
 425                         bindings_builder.push_default(&mut item.bindings);
 426                         cur_items.push(item);
 427                     }
 428                 } else {
 429                     // If we are not in a repetition, then being at the end of a matcher means that we have
 430                     // reached the potential end of the input.
 431                     try_push!(eof_items, item);
 432                 }
 433                 continue;
 434             }
 435             Some(it) => it,
 436         };
 437
 438         // We are in the middle of a matcher.
 439         match op {
 440             OpDelimited::Op(Op::Repeat { tokens, kind, separator }) => {
 441                 if matches!(kind, RepeatKind::ZeroOrMore | RepeatKind::ZeroOrOne) {
 442                     let mut new_item = item.clone();
 443                     new_item.bindings = bindings_builder.copy(&new_item.bindings);
 444                     new_item.dot.next();
 445                     collect_vars(
 446                         &mut |s| {
 447                             bindings_builder.push_empty(&mut new_item.bindings, &s);
 448                         },
 449                         tokens,
 450                     );
 451                     cur_items.push(new_item);
 452                 }
 453                 cur_items.push(MatchState {
 454                     dot: tokens.iter_delimited(None),
 455                     stack: Default::default(),
 456                     up: Some(Box::new(item)),
 457                     sep: separator.clone(),
 458                     sep_kind: Some(*kind),
 459                     sep_matched: false,
 460                     bindings: bindings_builder.alloc(),
 461                     meta_result: None,
 462                     is_error: false,
 463                 })
 464             }
 465             OpDelimited::Op(Op::Subtree { tokens, delimiter }) => {
 466                 if let Ok(subtree) = src.clone().expect_subtree() {
 467                     if subtree.delimiter.kind == delimiter.kind {
 468                         item.stack.push(item.dot);
 469                         item.dot = tokens.iter_delimited(Some(delimiter));
 470                         cur_items.push(item);
 471                     }
 472                 }
 473             }
 474             OpDelimited::Op(Op::Var { kind, name, .. }) => {
 475                 if let &Some(kind) = kind {
 476                     let mut fork = src.clone();
 477                     let match_res = match_meta_var(kind, &mut fork);
 478                     match match_res.err {
 479                         None => {
 480                             // Some meta variables are optional (e.g. vis)
 481                             if match_res.value.is_some() {
 482                                 item.meta_result = Some((fork, match_res));
 483                                 try_push!(bb_items, item);
 484                             } else {
 485                                 bindings_builder.push_optional(&mut item.bindings, name);
 486                                 item.dot.next();
 487                                 cur_items.push(item);
 488                             }
 489                         }
 490                         Some(err) => {
 491                             res.add_err(err);
 492                             match match_res.value {
 493                                 Some(fragment) => bindings_builder.push_fragment(
 494                                     &mut item.bindings,
 495                                     name,
 496                                     fragment,
 497                                 ),
 498                                 None => {
 499                                     bindings_builder.push_missing(&mut item.bindings, name, kind)
 500                                 }
 501                             }
 502                             item.is_error = true;
 503                             error_items.push(item);
 504                         }
 505                     }
 506                 }
 507             }
 508             OpDelimited::Op(Op::Literal(lhs)) => {
 509                 if let Ok(rhs) = src.clone().expect_leaf() {
 510                     if matches!(rhs, tt::Leaf::Literal(it) if it.text == lhs.text) {
 511                         item.dot.next();
 512                     } else {
 513                         res.add_err(ExpandError::UnexpectedToken);
 514                         item.is_error = true;
 515                     }
 516                 } else {
 517                     res.add_err(ExpandError::binding_error(format!("expected literal: `{lhs}`")));
 518                     item.is_error = true;
 519                 }
 520                 try_push!(next_items, item);
 521             }
 522             OpDelimited::Op(Op::Ident(lhs)) => {
 523                 if let Ok(rhs) = src.clone().expect_leaf() {
 524                     if matches!(rhs, tt::Leaf::Ident(it) if it.text == lhs.text) {
 525                         item.dot.next();
 526                     } else {
 527                         res.add_err(ExpandError::UnexpectedToken);
 528                         item.is_error = true;
 529                     }
 530                 } else {
 531                     res.add_err(ExpandError::binding_error(format!("expected ident: `{lhs}`")));
 532                     item.is_error = true;
 533                 }
 534                 try_push!(next_items, item);
 535             }
 536             OpDelimited::Op(Op::Punct(lhs)) => {
 537                 let mut fork = src.clone();
 538                 let error = if let Ok(rhs) = fork.expect_glued_punct() {
 539                     let first_is_single_quote = rhs[0].char == '\'';
 540                     let lhs = lhs.iter().map(|it| it.char);
 541                     let rhs = rhs.iter().map(|it| it.char);
 542                     if lhs.clone().eq(rhs) {
 543                         // HACK: here we use `meta_result` to pass `TtIter` back to caller because
 544                         // it might have been advanced multiple times. `ValueResult` is
 545                         // insignificant.
 546                         item.meta_result = Some((fork, ValueResult::ok(None)));
 547                         item.dot.next();
 548                         next_items.push(item);
 549                         continue;
 550                     }
 551
 552                     if first_is_single_quote {
 553                         // If the first punct token is a single quote, that's a part of a lifetime
 554                         // ident, not a punct.
 555                         ExpandError::UnexpectedToken
 556                     } else {
 557                         let lhs: SmolStr = lhs.collect();
 558                         ExpandError::binding_error(format!("expected punct: `{lhs}`"))
 559                     }
 560                 } else {
 561                     ExpandError::UnexpectedToken
 562                 };
 563
 564                 res.add_err(error);
 565                 item.is_error = true;
 566                 error_items.push(item);
 567             }
 568             OpDelimited::Op(Op::Ignore { .. } | Op::Index { .. }) => {}
 569             OpDelimited::Open => {
 570                 if matches!(src.peek_n(0), Some(tt::TokenTree::Subtree(..))) {
 571                     item.dot.next();
 572                     try_push!(next_items, item);
 573                 }
 574             }
 575             OpDelimited::Close => {
 576                 let is_delim_closed = src.peek_n(0).is_none() && !stack.is_empty();
 577                 if is_delim_closed {
 578                     item.dot.next();
 579                     try_push!(next_items, item);
 580                 }
 581             }
 582         }
 583     }
 584 }
 585
 586 fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
 587     let mut src = TtIter::new(src);
 588     let mut stack: SmallVec<[TtIter<'_>; 1]> = SmallVec::new();
 589     let mut res = Match::default();
 590     let mut error_recover_item = None;
 591
 592     let mut bindings_builder = BindingsBuilder::default();
 593
 594     let mut cur_items = smallvec![MatchState {
 595         dot: pattern.iter_delimited(None),
 596         stack: Default::default(),
 597         up: None,
 598         sep: None,
 599         sep_kind: None,
 600         sep_matched: false,
 601         bindings: bindings_builder.alloc(),
 602         is_error: false,
 603         meta_result: None,
 604     }];
 605
 606     let mut next_items = vec![];
 607
 608     loop {
 609         let mut bb_items = SmallVec::new();
 610         let mut eof_items = SmallVec::new();
 611         let mut error_items = SmallVec::new();
 612
 613         stdx::always!(next_items.is_empty());
 614
 615         match_loop_inner(
 616             src.clone(),
 617             &stack,
 618             &mut res,
 619             &mut bindings_builder,
 620             &mut cur_items,
 621             &mut bb_items,
 622             &mut next_items,
 623             &mut eof_items,
 624             &mut error_items,
 625         );
 626         stdx::always!(cur_items.is_empty());
 627
 628         if !error_items.is_empty() {
 629             error_recover_item = error_items.pop().map(|it| it.bindings);
 630         } else if let [state, ..] = &*eof_items {
 631             error_recover_item = Some(state.bindings.clone());
 632         }
 633
 634         // We need to do some post processing after the `match_loop_inner`.
 635         // If we reached the EOF, check that there is EXACTLY ONE possible matcher. Otherwise,
 636         // either the parse is ambiguous (which should never happen) or there is a syntax error.
 637         if src.peek_n(0).is_none() && stack.is_empty() {
 638             if let [state] = &*eof_items {
 639                 // remove all errors, because it is the correct answer !
 640                 res = Match::default();
 641                 res.bindings = bindings_builder.build(&state.bindings);
 642             } else {
 643                 // Error recovery
 644                 if let Some(item) = error_recover_item {
 645                     res.bindings = bindings_builder.build(&item);
 646                 }
 647                 res.add_err(ExpandError::UnexpectedToken);
 648             }
 649             return res;
 650         }
 651
 652         // If there are no possible next positions AND we aren't waiting for the black-box parser,
 653         // then there is a syntax error.
 654         //
 655         // Another possibility is that we need to call out to parse some rust nonterminal
 656         // (black-box) parser. However, if there is not EXACTLY ONE of these, something is wrong.
 657         let has_leftover_tokens = (bb_items.is_empty() && next_items.is_empty())
 658             || !(bb_items.is_empty() || next_items.is_empty())
 659             || bb_items.len() > 1;
 660         if has_leftover_tokens {
 661             res.unmatched_tts += src.len();
 662             while let Some(it) = stack.pop() {
 663                 src = it;
 664                 res.unmatched_tts += src.len();
 665             }
 666             res.add_err(ExpandError::LeftoverTokens);
 667
 668             if let Some(error_recover_item) = error_recover_item {
 669                 res.bindings = bindings_builder.build(&error_recover_item);
 670             }
 671             return res;
 672         }
 673         // Dump all possible `next_items` into `cur_items` for the next iteration.
 674         else if !next_items.is_empty() {
 675             if let Some((iter, _)) = next_items[0].meta_result.take() {
 676                 // We've matched a possibly "glued" punct. The matched punct (hence
 677                 // `meta_result` also) must be the same for all items.
 678                 // FIXME: If there are multiple items, it's definitely redundant (and it's hacky!
 679                 // `meta_result` isn't supposed to be used this way).
 680
 681                 // We already bumped, so no need to call `.next()` like in the other branch.
 682                 src = iter;
 683                 for item in next_items.iter_mut() {
 684                     item.meta_result = None;
 685                 }
 686             } else {
 687                 match src.next() {
 688                     Some(tt::TokenTree::Subtree(subtree)) => {
 689                         stack.push(src.clone());
 690                         src = TtIter::new(subtree);
 691                     }
 692                     None => {
 693                         if let Some(iter) = stack.pop() {
 694                             src = iter;
 695                         }
 696                     }
 697                     _ => (),
 698                 }
 699             }
 700             // Now process the next token
 701             cur_items.extend(next_items.drain(..));
 702         }
 703         // Finally, we have the case where we need to call the black-box parser to get some
 704         // nonterminal.
 705         else {
 706             stdx::always!(bb_items.len() == 1);
 707             let mut item = bb_items.pop().unwrap();
 708
 709             if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() {
 710                 let (iter, match_res) = item.meta_result.take().unwrap();
 711                 match match_res.value {
 712                     Some(fragment) => {
 713                         bindings_builder.push_fragment(&mut item.bindings, name, fragment);
 714                     }
 715                     None if match_res.err.is_none() => {
 716                         bindings_builder.push_optional(&mut item.bindings, name);
 717                     }
 718                     None => {}
 719                 }
 720                 if let Some(err) = match_res.err {
 721                     res.add_err(err);
 722                 }
 723                 src = iter.clone();
 724                 item.dot.next();
 725             } else {
 726                 unreachable!()
 727             }
 728             cur_items.push(item);
 729         }
 730         stdx::always!(!cur_items.is_empty());
 731     }
 732 }
 733
 734 fn match_meta_var(kind: MetaVarKind, input: &mut TtIter<'_>) -> ExpandResult<Option<Fragment>> {
 735     let fragment = match kind {
 736         MetaVarKind::Path => parser::PrefixEntryPoint::Path,
 737         MetaVarKind::Ty => parser::PrefixEntryPoint::Ty,
 738         // FIXME: These two should actually behave differently depending on the edition.
 739         //
 740         // https://doc.rust-lang.org/edition-guide/rust-2021/or-patterns-macro-rules.html
 741         MetaVarKind::Pat | MetaVarKind::PatParam => parser::PrefixEntryPoint::Pat,
 742         MetaVarKind::Stmt => parser::PrefixEntryPoint::Stmt,
 743         MetaVarKind::Block => parser::PrefixEntryPoint::Block,
 744         MetaVarKind::Meta => parser::PrefixEntryPoint::MetaItem,
 745         MetaVarKind::Item => parser::PrefixEntryPoint::Item,
 746         MetaVarKind::Vis => parser::PrefixEntryPoint::Vis,
 747         MetaVarKind::Expr => {
 748             // `expr` should not match underscores, let expressions, or inline const. The latter
 749             // two are for [backwards compatibility][0].
 750             // HACK: Macro expansion should not be done using "rollback and try another alternative".
 751             // rustc [explicitly checks the next token][1].
 752             // [0]: https://github.com/rust-lang/rust/issues/86730
 753             // [1]: https://github.com/rust-lang/rust/blob/f0c4da499/compiler/rustc_expand/src/mbe/macro_parser.rs#L576
 754             match input.peek_n(0) {
 755                 Some(tt::TokenTree::Leaf(tt::Leaf::Ident(it)))
 756                     if it.text == "_" || it.text == "let" || it.text == "const" =>
 757                 {
 758                     return ExpandResult::only_err(ExpandError::NoMatchingRule)
 759                 }
 760                 _ => {}
 761             };
 762             return input
 763                 .expect_fragment(parser::PrefixEntryPoint::Expr)
 764                 .map(|tt| tt.map(Fragment::Expr));
 765         }
 766         _ => {
 767             let tt_result = match kind {
 768                 MetaVarKind::Ident => input
 769                     .expect_ident()
 770                     .map(|ident| tt::Leaf::from(ident.clone()).into())
 771                     .map_err(|()| ExpandError::binding_error("expected ident")),
 772                 MetaVarKind::Tt => input
 773                     .expect_tt()
 774                     .map_err(|()| ExpandError::binding_error("expected token tree")),
 775                 MetaVarKind::Lifetime => input
 776                     .expect_lifetime()
 777                     .map_err(|()| ExpandError::binding_error("expected lifetime")),
 778                 MetaVarKind::Literal => {
 779                     let neg = input.eat_char('-');
 780                     input
 781                         .expect_literal()
 782                         .map(|literal| {
 783                             let lit = literal.clone();
 784                             match neg {
 785                                 None => lit.into(),
 786                                 Some(neg) => tt::TokenTree::Subtree(tt::Subtree {
 787                                     delimiter: tt::Delimiter::unspecified(),
 788                                     token_trees: vec![neg, lit.into()],
 789                                 }),
 790                             }
 791                         })
 792                         .map_err(|()| ExpandError::binding_error("expected literal"))
 793                 }
 794                 _ => Err(ExpandError::UnexpectedToken),
 795             };
 796             return tt_result.map(|it| Some(Fragment::Tokens(it))).into();
 797         }
 798     };
 799     input.expect_fragment(fragment).map(|it| it.map(Fragment::Tokens))
 800 }
 801
 802 fn collect_vars(collector_fun: &mut impl FnMut(SmolStr), pattern: &MetaTemplate) {
 803     for op in pattern.iter() {
 804         match op {
 805             Op::Var { name, .. } => collector_fun(name.clone()),
 806             Op::Subtree { tokens, .. } => collect_vars(collector_fun, tokens),
 807             Op::Repeat { tokens, .. } => collect_vars(collector_fun, tokens),
 808             Op::Ignore { .. } | Op::Index { .. } | Op::Literal(_) | Op::Ident(_) | Op::Punct(_) => {
 809             }
 810         }
 811     }
 812 }
 813 impl MetaTemplate {
 814     fn iter_delimited<'a>(&'a self, delimited: Option<&'a tt::Delimiter>) -> OpDelimitedIter<'a> {
 815         OpDelimitedIter {
 816             inner: &self.0,
 817             idx: 0,
 818             delimited: delimited.unwrap_or(&tt::Delimiter::UNSPECIFIED),
 819         }
 820     }
 821 }
 822
 823 #[derive(Debug, Clone, Copy)]
 824 enum OpDelimited<'a> {
 825     Op(&'a Op),
 826     Open,
 827     Close,
 828 }
 829
 830 #[derive(Debug, Clone, Copy)]
 831 struct OpDelimitedIter<'a> {
 832     inner: &'a [Op],
 833     delimited: &'a tt::Delimiter,
 834     idx: usize,
 835 }
 836
 837 impl<'a> OpDelimitedIter<'a> {
 838     fn is_eof(&self) -> bool {
 839         let len = self.inner.len()
 840             + if self.delimited.kind != tt::DelimiterKind::Invisible { 2 } else { 0 };
 841         self.idx >= len
 842     }
 843
 844     fn peek(&self) -> Option<OpDelimited<'a>> {
 845         match self.delimited.kind {
 846             tt::DelimiterKind::Invisible => self.inner.get(self.idx).map(OpDelimited::Op),
 847             _ => match self.idx {
 848                 0 => Some(OpDelimited::Open),
 849                 i if i == self.inner.len() + 1 => Some(OpDelimited::Close),
 850                 i => self.inner.get(i - 1).map(OpDelimited::Op),
 851             },
 852         }
 853     }
 854
 855     fn reset(&self) -> Self {
 856         Self { inner: self.inner, idx: 0, delimited: self.delimited }
 857     }
 858 }
 859
 860 impl<'a> Iterator for OpDelimitedIter<'a> {
 861     type Item = OpDelimited<'a>;
 862
 863     fn next(&mut self) -> Option<Self::Item> {
 864         let res = self.peek();
 865         self.idx += 1;
 866         res
 867     }
 868
 869     fn size_hint(&self) -> (usize, Option<usize>) {
 870         let len = self.inner.len()
 871             + if self.delimited.kind != tt::DelimiterKind::Invisible { 2 } else { 0 };
 872         let remain = len.saturating_sub(self.idx);
 873         (remain, Some(remain))
 874     }
 875 }
 876
 877 impl<'a> TtIter<'a> {
 878     fn expect_separator(&mut self, separator: &Separator) -> bool {
 879         let mut fork = self.clone();
 880         let ok = match separator {
 881             Separator::Ident(lhs) => match fork.expect_ident_or_underscore() {
 882                 Ok(rhs) => rhs.text == lhs.text,
 883                 Err(_) => false,
 884             },
 885             Separator::Literal(lhs) => match fork.expect_literal() {
 886                 Ok(rhs) => match rhs {
 887                     tt::Leaf::Literal(rhs) => rhs.text == lhs.text,
 888                     tt::Leaf::Ident(rhs) => rhs.text == lhs.text,
 889                     tt::Leaf::Punct(_) => false,
 890                 },
 891                 Err(_) => false,
 892             },
 893             Separator::Puncts(lhs) => match fork.expect_glued_punct() {
 894                 Ok(rhs) => {
 895                     let lhs = lhs.iter().map(|it| it.char);
 896                     let rhs = rhs.iter().map(|it| it.char);
 897                     lhs.eq(rhs)
 898                 }
 899                 Err(_) => false,
 900             },
 901         };
 902         if ok {
 903             *self = fork;
 904         }
 905         ok
 906     }
 907
 908     fn expect_tt(&mut self) -> Result<tt::TokenTree, ()> {
 909         if let Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) = self.peek_n(0) {
 910             if punct.char == '\'' {
 911                 self.expect_lifetime()
 912             } else {
 913                 let puncts = self.expect_glued_punct()?;
 914                 let token_trees = puncts.into_iter().map(|p| tt::Leaf::Punct(p).into()).collect();
 915                 Ok(tt::TokenTree::Subtree(tt::Subtree {
 916                     delimiter: tt::Delimiter::unspecified(),
 917                     token_trees,
 918                 }))
 919             }
 920         } else {
 921             self.next().ok_or(()).cloned()
 922         }
 923     }
 924
 925     fn expect_lifetime(&mut self) -> Result<tt::TokenTree, ()> {
 926         let punct = self.expect_single_punct()?;
 927         if punct.char != '\'' {
 928             return Err(());
 929         }
 930         let ident = self.expect_ident_or_underscore()?;
 931
 932         Ok(tt::Subtree {
 933             delimiter: tt::Delimiter::unspecified(),
 934             token_trees: vec![
 935                 tt::Leaf::Punct(*punct).into(),
 936                 tt::Leaf::Ident(ident.clone()).into(),
 937             ],
 938         }
 939         .into())
 940     }
 941
 942     fn eat_char(&mut self, c: char) -> Option<tt::TokenTree> {
 943         let mut fork = self.clone();
 944         match fork.expect_char(c) {
 945             Ok(_) => {
 946                 let tt = self.next().cloned();
 947                 *self = fork;
 948                 tt
 949             }
 950             Err(_) => None,
 951         }
 952     }
 953 }