Token tree parsing is inefficient in cases of nested macros

[paulstansifer]

In a case like this:

m!{ 4 + m!{ 2+ 3 } }

...the body of the innermost invocation gets parsed as a token tree n times, where n is the nesting depth of the macros.

What should happen is the parser should tell the lexer "I'm looking for a token tree; you don't happen to be operating on a token tree already by any chance?". string_readers will say "No", and tt_readers will say "Why yes; here's the whole next subtree." In parse.rs, parse_token_tree will use this information similarly to the way that the the maybe_whole! macro works.

[pnkfelix]

Bug triage 2013jun24. This is still a problem. It is relatively easy to make examples that illustrate the issue described here, such as play-tt-parse1.rs on this gist, which takes much more time (~30x) to compile than play-tt-parse2.rs (which has the same number of occurrences of m!).

One distinction worth making is whether the reparsing occurs solely (if repeatedly) on source code inputs, or if it also happens when recursively expanding the output of a macro expansion. I was sufficiently curious about this that I made a couple more examples (also linked on the gist above) that construct the large syntax trees (one that matches the size of play-tt-parse1.rs, and another that exhibits exponential growth. The impression I got from that experiment is that the syntax, once handled solely by the expander alone, is being treated reasonably efficiently. So the n repeated parsings that paul wrote in the description is just for source code inputs, not for the results of macro expansions, which is good (in terms of providing hope that this problem is not as likely to mysteriously blow up in one's face without knowing why).

[emberian]

I don't have anything to add except some updated timing:

[12:53:46]/tmp/5850380> time rustc play-tt-parse1.rs 
rustc play-tt-parse1.rs  0.49s user 0.07s system 100% cpu 0.555 total
[12:54:08]/tmp/5850380> time rustc play-tt-parse2.rs 
rustc play-tt-parse2.rs  0.87s user 0.10s system 100% cpu 0.973 total
[12:54:15]/tmp/5850380> time rustc play-tt-parse3.rs 
rustc play-tt-parse3.rs  100.19s user 27.74s system 99% cpu 2:07.93 total
[12:56:32]/tmp/5850380> time rustc play-tt-parse4.rs 
rustc play-tt-parse4.rs  2.51s user 0.96s system 100% cpu 3.468 total

[pnkfelix]

Accepted for P-low.

[steveklabnik]

Triage: the gist is out of date fairly badly, after doing the easy updates I'm getting

play-tt-parse1.rs:2:6: 2:14 error: `$e1:expr` is followed by `@`, which is not allowed for `expr` fragments
play-tt-parse1.rs:2     ($e1:expr @ $e2:expr) => ({ $e1 })
                         ^~~~~~~~

[emberian]

@steveklabnik should be able to replace the @ with => everywhere to update it.

@steveklabnik I don't think this occurs anymore, unless I messed something up when getting it to compile. Using this updated version:

$ time rustc play-tt-parse1.rs 

real    0m0.204s
user    0m0.172s
sys     0m0.024s

On the latest nightly, rustc 1.5.0-nightly (e0e2627 2015-10-27).

[steveklabnik]

@Toby-s thanks!

Anyone else, if this is still happening, please let us know.

[paulstansifer]

Nice!