Eagerly check for ambiguity in macro parsing by bal-e · Pull Request #158976 · rust-lang/rust

bal-e · 2026-07-08T21:09:55Z

This PR implements an important step leading up to the BFS->DFS change: it makes ambiguity detection (as occurs when parsing meta-variables and reaching EOF) eager. Rather than accumulating the bb_mps and eof_mps lists, then checking that a single valid parse exists, this PR introduces a check_for_ambiguity() method that gets called as soon as the relevant MatcherLoc is observed. check_for_ambiguity() immediately drains cur_mps instead of waiting for the outer loop to do so, and evaluates the mps within a "checking for ambiguity" context.

This change was complicated by the fact that bb_mps was relied on for error messages; it was passed along to Tracker::ambiguity(). The same is true for next_mps. The first few commits of this PR (after pending rebases) add state to Tracker so that it can compute the relevant diagnostic information independently of bb_mps.

This PR complicates the control flow around parse_tt_inner() in subtle ways. I'm not super happy about it, but I think it will become easier to understand again once a DFS approach is implemented.

~~This PR contains #158894 and #158974. I'll rebase on top of main once they're both merged.~~

Best reviewed commit-by-commit.

r? @nnethercote

rustbot · 2026-07-08T21:09:58Z

The parser was modified, potentially altering the grammar of (stable) Rust
which would be a breaking change.

cc @fmease

rustbot · 2026-07-08T21:10:01Z

Thanks for the pull request, and welcome! The Rust Project is excited to review your changes, and you should hear from @nnethercote (or someone else) some time within the next two weeks.

Please see the contribution instructions for more information. Namely, in order to ensure the minimum review times lag, PR authors and assigned reviewers should ensure that the review label (S-waiting-on-review and S-waiting-on-author) stays updated, invoking these commands when appropriate:

@rustbot author: the review is finished, PR author should check the comments and take action accordingly
@rustbot review: the author is ready for a review, this PR will be queued again in the reviewer's queue

The code that calls `parser.bump()` or parses a non-terminal is moved from `parse_tt()` to `parse_tt_inner()`. This makes it possible to move the non-terminal parsing code even further, to `match_one()`. I marked the comment in the moved code as a `FIXME` because it reads like one. This makes `parse_tt()` look quite redundant, but once the full switch to DFS is made, I think it will handle some back-tracking logic. `tests/ui/macros` pass.

This will be used in the next commit to reference `MatcherLoc`s by index so that they can be compared and hashed efficiently.

Right now, if an ambiguity error occurs, `TtParser::{next,bb}_mps` are relied on to extract information for diagnostics. This hinders movement to depth-first traversal. This commit allows the `Tracker` to compute `{next,bb}_mps` information without relying on `TtParser` to work in a breadth-first way. This information is recorded in a `HashSet`, mixing data from `next_mps` and `bb_mps`. It *could* have been a `Vec` that gets cleared after a `Parser::bump()` / non-terminal parse, but that be incompatible with depth-first traversal in `TtParser`.

`CollectTrackerAndEmitter` can compute this data from `Tracker::matched_one()`. The collected data coalesces non-terminal `MatcherLoc`s with others, so `partition()` is used to separate them. The data is retrieved from a `HashSet`, but because the results are sorted, everything is deterministic. This removes some pressure on `TtParser` to use breadth-first traversal. `tests/ui/macros` pass.

When a meta-variable `MatcherLoc` is discovered, it would be nice to parse it immediately; but right now, it gets added to `bb_mps` and has to wait until everything in `cur_mps` is processed so `TtParser` can check for ambiguity. This commit adds an eager ambiguity checking step when a meta-variable `MatcherLoc` is being processed. This is a subtle but important change in the semantics of `match_one()`; it can now modify `cur_mps`, and effectively work from `parse_tt_inner()`. This is the first major step towards depth-first traversal.

The same infrastructure for checking for ambiguity for `MetaVarDecl` can also be used for processing `Eof`! This has several benefits: - `eof_mps` is removed and no longer needs to be passed around. - The two calls to `Tracker::failure()` are unified; specifically "reached EOF but no successful parses" and "ran out of mps". - The two calls to `TtParser::ambiguity_error()` are unified: specifically "multiple successful parses at EOF" and "multiple `MatcherLoc`s at a non-terminal parsing point". These unifications further motivate the original unification of the errors in `Tracker`, and show that the different kinds of merged errors *did* deserve to be grouped together semantically. `tests/ui/macros` pass.

If `parse_tt_inner()` -> `match_one()` -> `check_for_ambiguity()` detects ambiguity, it will clear `cur_mps`, which guarantees that the next thing to happen will be the check for ambiguity. This commit brings the ambiguity detection closer to the building of the ambiguity error by moving that code directly into `check_for_ambiguity()` (which now returns a `ParseResult`).

rustbot · 2026-07-12T21:02:28Z

This PR was rebased onto a different main commit. Here's a range-diff highlighting what actually changed.

Rebasing is a normal part of keeping PRs up to date, so no action is needed—this note is just to help reviewers.

bal-e · 2026-07-12T21:02:48Z

can we get a perf run?

nnethercote · 2026-07-13T06:29:34Z

@bors try @rust-timer queue

Eagerly check for ambiguity in macro parsing

rust-bors · 2026-07-13T08:36:27Z

☀️ Try build successful (CI)
Build commit: d51d067 (d51d067aabdad5fe98376e54ab46f42ecefba878)
Base parent: 48c2cee (48c2cee70232ecc3a6a8e285b2e15620b39f82a7)

rust-timer · 2026-07-13T09:34:03Z

Finished benchmarking commit (d51d067): comparison URL.

Overall result: ❌✅ regressions and improvements - please read:

Benchmarking means the PR may be perf-sensitive. It's automatically marked not fit for rolling up. Overriding is possible but disadvised: it risks changing compiler perf.

Next, please: If you can, justify the regressions found in this try perf run in writing along with @rustbot label: +perf-regression-triaged. If not, fix the regressions and do another perf run. Neutral or positive results will clear the label automatically.

@bors rollup=never rustc-perf
@rustbot label: -S-waiting-on-perf +perf-regression

Instruction count

Our most reliable metric. Used to determine the overall result above. However, even this metric can be noisy.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	0.3%	[0.2%, 0.4%]	8
Improvements ✅ (primary)	-0.9%	[-2.3%, -0.3%]	30
Improvements ✅ (secondary)	-0.6%	[-0.9%, -0.4%]	6
All ❌✅ (primary)	-0.9%	[-2.3%, -0.3%]	30

Max RSS (memory usage)

Results (primary -0.7%, secondary 0.7%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	1.2%	[1.2%, 1.2%]	1
Regressions ❌ (secondary)	3.6%	[1.0%, 10.9%]	5
Improvements ✅ (primary)	-2.6%	[-2.6%, -2.6%]	1
Improvements ✅ (secondary)	-4.1%	[-5.0%, -3.2%]	3
All ❌✅ (primary)	-0.7%	[-2.6%, 1.2%]	2

Cycles

Results (primary -1.9%, secondary -4.6%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	-	-	0
Improvements ✅ (primary)	-1.9%	[-2.1%, -1.7%]	2
Improvements ✅ (secondary)	-4.6%	[-6.2%, -2.2%]	3
All ❌✅ (primary)	-1.9%	[-2.1%, -1.7%]	2

Binary size

This perf run didn't have relevant results for this metric.

Bootstrap: 490.231s -> 487.546s (-0.55%)
Artifact size: 391.34 MiB -> 389.33 MiB (-0.51%)

bal-e · 2026-07-13T12:28:40Z

The perf results seem quite reasonable (small but widespread improvements in instruction count, limited but nice improvements in cycle count) ... shall I set +perf-regression-triaged?

nnethercote · 2026-07-13T13:26:04Z

Perf improvements outweigh regressions.

@rustbot label: +perf-regression-triaged

nnethercote · 2026-07-14T11:19:32Z

@bors r+

rust-bors · 2026-07-14T11:19:35Z

📌 Commit a1b7471 has been approved by nnethercote

It is now in the queue for this repository.

rust-bors · 2026-07-15T00:04:41Z

☀️ Test successful - CI
Approved by: nnethercote
Duration: 3h 26m 36s
Pushing 2f5253f to main...

github-actions · 2026-07-15T00:07:49Z

What is this?

This is an experimental post-merge analysis report that shows differences in test outcomes between the merged PR and its parent PR.

Comparing da80ed0 (parent) -> 2f5253f (this PR)

Test differences

Show 4 test diffs

4 doctest diffs were found. These are ignored, as they are noisy.

Test dashboard

Run

cargo run --manifest-path src/ci/citool/Cargo.toml -- \
    test-dashboard 2f5253f0087ee60faab7dbe7c9002163c605ac7e --output-dir test-dashboard

And then open test-dashboard/index.html in your browser to see an overview of all executed tests.

Job duration changes

i686-msvc-2: 1h 32m -> 2h 7m (+37.1%)
i686-msvc-1: 3h 3m -> 2h 8m (-30.1%)
dist-powerpc64le-linux-gnu: 1h 14m -> 1h 36m (+29.4%)
x86_64-gnu-gcc-core-tests: 12m 35s -> 9m 3s (-28.1%)
dist-apple-various: 1h 25m -> 1h 49m (+27.5%)
armhf-gnu: 1h 31m -> 1h 6m (-27.3%)
x86_64-msvc-ext3: 1h 49m -> 1h 20m (-26.3%)
dist-arm-linux-musl: 1h 17m -> 1h 36m (+24.0%)
x86_64-gnu-llvm-21-3: 1h 50m -> 1h 25m (-22.6%)
x86_64-msvc-2: 2h 35m -> 2h (-22.4%)

How to interpret the job duration changes?

Job durations can vary a lot, based on the actual runner instance
that executed the job, system noise, invalidated caches, etc. The table above is provided
mostly for t-infra members, for simpler debugging of potential CI slow-downs.

rust-timer · 2026-07-15T00:45:53Z

Finished benchmarking commit (2f5253f): comparison URL.

Overall result: ❌✅ regressions and improvements - please read:

Our benchmarks found a performance regression caused by this PR.
This might be an actual regression, but it can also be just noise.

Next Steps:

If the regression was expected or you think it can be justified,
please write a comment with sufficient written justification, and add
@rustbot label: +perf-regression-triaged to it, to mark the regression as triaged.
If you think that you know of a way to resolve the regression, try to create
a new PR with a fix for the regression.
If you do not understand the regression or you think that it is just noise,
you can ask the @rust-lang/wg-compiler-performance working group for help (members of this group
were already notified of this PR).

@rustbot label: +perf-regression
cc @rust-lang/wg-compiler-performance

Instruction count

Our most reliable metric. Used to determine the overall result above. However, even this metric can be noisy.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	0.3%	[0.2%, 0.4%]	10
Improvements ✅ (primary)	-0.9%	[-2.3%, -0.3%]	29
Improvements ✅ (secondary)	-0.6%	[-0.9%, -0.4%]	5
All ❌✅ (primary)	-0.9%	[-2.3%, -0.3%]	29

Max RSS (memory usage)

Results (primary 3.2%, secondary 11.3%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	5.9%	[5.2%, 6.5%]	2
Regressions ❌ (secondary)	11.3%	[11.3%, 11.3%]	1
Improvements ✅ (primary)	-2.2%	[-2.2%, -2.2%]	1
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	3.2%	[-2.2%, 6.5%]	3

Cycles

Results (primary -2.2%, secondary 3.6%)

A less reliable metric. May be of interest, but not used to determine the overall result above.

	mean	range	count
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	15.7%	[15.7%, 15.7%]	1
Improvements ✅ (primary)	-2.2%	[-2.2%, -2.2%]	1
Improvements ✅ (secondary)	-2.5%	[-2.9%, -2.1%]	2
All ❌✅ (primary)	-2.2%	[-2.2%, -2.2%]	1

Binary size

This perf run didn't have relevant results for this metric.

Bootstrap: 491.202s -> 490.821s (-0.08%)
Artifact size: 389.32 MiB -> 389.41 MiB (0.02%)

nnethercote · 2026-07-15T02:30:18Z

tt-muncher and html5ever are the two benchmarks that are usually most affected by declarative macro changes, so it's surprising to see them go in opposite directions. But the wins here (on real-world benchmarks) significantly outweigh the losses (on a stress test).

@rustbot label: +perf-regression-triaged

bal-e · 2026-07-15T15:16:59Z

Perhaps I can add some context: it seems tt-muncher involves parsing lots of meta-variables, while html5ever mostly tries parsing fixed tokens. This PR is a net win but adds a little bit of overhead when lots of meta-variables are being parsed (each one hits the ambiguity check). I plan to add more optimizations for meta-variables, so I expect tt-muncher to improve more than html5ever in my next PRs.

nnethercote · 2026-07-15T23:28:05Z

Makes sense, thanks for the explanation. I seem to remember html5ever has one enormous macro with a zillion rules that involve no metavars.

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Jul 8, 2026

rustbot assigned nnethercote Jul 8, 2026

This comment has been minimized.

Sign in to view

bal-e force-pushed the eager-ambig-detection branch from 1db582c to 392aa10 Compare July 8, 2026 21:11

This comment has been minimized.

Sign in to view

arya dradjica added 11 commits July 12, 2026 23:02

Add &[MatcherLoc] to Tracker::prepare()

5fecb9b

This will be used in the next commit to reference `MatcherLoc`s by index so that they can be compared and hashed efficiently.

Inline non-terminal parsing into match_one()

474ddc6

Remove bb_mps

e06eea9

Factor out some ambiguity-checking boilerplate

d5c0b2a

Inline TtParser::ambiguity_error()

479cf9a

bal-e force-pushed the eager-ambig-detection branch from 392aa10 to a1b7471 Compare July 12, 2026 21:02

This comment has been minimized.

Sign in to view

rustbot added the S-waiting-on-perf Status: Waiting on a perf run to be completed. label Jul 13, 2026

This comment has been minimized.

Sign in to view

rust-bors Bot pushed a commit that referenced this pull request Jul 13, 2026

Auto merge of #158976 - bal-e:eager-ambig-detection, r=<try>

d51d067

Eagerly check for ambiguity in macro parsing

This comment has been minimized.

Sign in to view

rustbot added perf-regression Performance regression. and removed S-waiting-on-perf Status: Waiting on a perf run to be completed. labels Jul 13, 2026

rustbot added the perf-regression-triaged The performance regression has been triaged. label Jul 13, 2026

rust-bors Bot added S-waiting-on-bors Status: Waiting on bors to run and complete tests. Bors will change the label on completion. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Jul 14, 2026

This comment has been minimized.

Sign in to view

rust-bors Bot added merged-by-bors This PR was explicitly merged by bors. and removed S-waiting-on-bors Status: Waiting on bors to run and complete tests. Bors will change the label on completion. labels Jul 15, 2026

rust-bors Bot merged commit 2f5253f into rust-lang:main Jul 15, 2026
15 checks passed

rustbot added this to the 1.99.0 milestone Jul 15, 2026

bal-e deleted the eager-ambig-detection branch July 15, 2026 15:07

bal-e mentioned this pull request Jul 24, 2026

Use depth-first traversal for macro parsing #159808

Open

Uh oh!

Uh oh!

Conversation

bal-e commented Jul 8, 2026 • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rustbot commented Jul 8, 2026

Uh oh!

rustbot commented Jul 8, 2026

Uh oh!

This comment has been minimized.

This comment has been minimized.

rustbot commented Jul 12, 2026

Uh oh!

bal-e commented Jul 12, 2026

Uh oh!

nnethercote commented Jul 13, 2026

Uh oh!

This comment has been minimized.

This comment has been minimized.

rust-bors Bot commented Jul 13, 2026

Uh oh!

This comment has been minimized.

rust-timer commented Jul 13, 2026

Overall result: ❌✅ regressions and improvements - please read:

Uh oh!

bal-e commented Jul 13, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nnethercote commented Jul 13, 2026

Uh oh!

nnethercote commented Jul 14, 2026

Uh oh!

rust-bors Bot commented Jul 14, 2026

Uh oh!

This comment has been minimized.

rust-bors Bot commented Jul 15, 2026

Uh oh!

Uh oh!

github-actions Bot commented Jul 15, 2026

Test differences

Job duration changes

Uh oh!

rust-timer commented Jul 15, 2026

Overall result: ❌✅ regressions and improvements - please read:

Uh oh!

nnethercote commented Jul 15, 2026

Uh oh!

bal-e commented Jul 15, 2026

Uh oh!

nnethercote commented Jul 15, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

bal-e commented Jul 8, 2026 •

edited by rustbot

Loading

bal-e commented Jul 13, 2026 •

edited

Loading