Tracking issue (ish) for some declarative macro optimizations

[bal-e]

This is sort of like a tracking issue, but specifically for the optimizations I am making (or plan to make) to rustc's macros-by-example implementation. I'm using it to maintain a public list of my ideas on this topic and link together the relevant PRs.

@nnethercote is reviewing these PRs, I'm really grateful for all his help :)

Depth-first traversal for macro parsing (ongoing)

Until now, macro parsing uses a breadth-first traversal strategy for exploring possibly ambiguous parse trees. I believe a depth-first approach would play better with the CPU, e.g. for branch prediction, as well as unlocking bigger optimizations (e.g. it would allow the Rc<Vec<NamedMatch>> in each MatcherPos to be amortized).

Work started 2026-05-22.

• Polish some macro parsing code #158577 (code cleanup, minor perf wins)
• Make the ordering of non-terminal binds in ambiguity error messages deterministic #158894 (hid implementation details from error messages)
• Preparatory changes for macro parsing BFS->DFS #158974 (code cleanup, outsized perf wins)
• Eagerly check for ambiguity in macro parsing #158976 (use a DFS approach in some cases; nice perf wins)
• Postpone emission of non-terminal parsing errors to diagnostics.rs
• Use depth-first traversal for macro parsing #159808
• Use recursive descent (up to a limit?) to evaluate Kleene stars

Overall results:

• Nice perf wins, even in preparatory PRs.
• Made user-visible details (e.g. ordering within error messages) independent of implementation details.
• Added more internal documentation.
• Conceptually unified two kinds of ambiguity detection (meta-variables and EOF).
• Removed some unreachable paths.
• Moved more diagnostic code to diagnostics.rs.

Others

Note: these are ideas / proposals, and not all of them might pan out.

• Convert ParseNtResult into TokenStream earlier #159366
• Reuse existing TokenStream allocations when transcribing meta-variables
• Introduce a Matcher type to hold and extend &[MatcherLoc]
• Remove MatcherLoc::Delimited
• Strip doc-comment MatcherLoc::Tokens when building MatcherLocs (for now)
• Optimize memory layout of MatcherLoc
• Propose supporting doc-comment tokens in matchers (might need a FCW)
• Assign meta-variables fixed IDs across parsing and transcribing
• Use Vec instead of HashMap in NamedMatches
• Flatten the recursive Vecs in NamedMatch
• Amortize MatcherPos::matches
• Reuse allocations by caching TtParser in thread-local storage
• Try replacing Cow<Parser<'_>> with an explicit fast path
• Replace mbe::TokenStream with an auxiliary table
• Add a pseudo-metavar for $($x:tt)* to speed up tt-munchers
• Add benchmarks that directly call expand_macro()

[bal-e]

@rustbot label -needs-triage +C-tracking-issue +C-optimization +A-macros
@rustbot claim