Increase in compilation times with newest beta & nightly

[fengalin]

Description

I hit an important increase in compilation times on beta & nightly with a
particular configuration using combine-3.8.1 since the recent version updates
in the Rust toolchains.

I tried building an example without combine in order to submit it to rustc
but it turns out not to be trivial. I ran into this as a side effect in CI and
can't spend much time investigating ATM, sorry.

From the CI logs I have at hand, the issue was not present as of:
rustc 1.41.0-nightly (fdc001156 2019-12-02).

Reduced example

Here is an example with which I was able to reproduce the issue:

use combine::byte::hex_digit;
use combine::{choice, token};
use combine::{ParseError, Parser, RangeStream};

fn parse<'a, I: 'a>() -> impl Parser<Input = I, Output = u8>
where
    I: RangeStream<Item = u8, Range = &'a [u8]>,
    I::Error: ParseError<I::Item, I::Range, I::Position>,
{
    choice!(
        token(b'A').map(|_| 1),
        token(b'B').map(|_| 2),
        token(b'C').map(|_| 3),
        token(b'D').map(|_| 4),
        token(b'E').map(|_| 5),
        token(b'F').map(|_| 6),
        token(b'G').map(|_| 7),
        token(b'H').map(|_| 8),
        token(b'I').map(|_| 9),
        token(b'J').map(|_| 10),
        token(b'K').map(|_| 11),
        token(b'L').map(|_| 12),
        token(b'M').map(|_| 13),
        token(b'N').map(|_| 14),
        token(b'O').map(|_| 15),
        token(b'P').map(|_| 16),
        token(b'Q').map(|_| 17),
//        token(b'R').map(|_| 18)
        (hex_digit(), hex_digit()).map(|(u, l)| {
            let val = (u << 4) | l;
            val
        })
    )
    .message("while parsing")
}

Toolchain versions

The toolchain used for these tests are those available as of 2019/12/20:

• stable: rustc 1.40.0 (73528e339 2019-12-16)
• beta: rustc 1.41.0-beta.1 (eb3f7c2d3 2019-12-17)
• nightly: rustc 1.42.0-nightly (0de96d37f 2019-12-19)

Compilation times

For each test, cargo clean was run before building in debug mode.

With message(..)

Configuration	stable	beta	nightly
15 tokens	12.79s	26.83s	25.38s
17 tokens	12.69s	2m 20s	2m 20s
18 tokens	12.89s	6m 50s	6m 55s
17 tokens + (hex_digit, hex_digit)	12.84s	15m 57s	16m 54s

Without message(..)

"Interestingly", removing the .message(..) line reduces compilation times
significantly.

Configuration	stable	beta	nightly
15 tokens	12.67s	19.89s	16.14s
18 tokens	12.67s	4m 11s	2m 34s
17 tokens + (hex_digit, hex_digit)	12.78s	5m 00s	4m 35s

[sdroege]

I think this should be reported to https://github.com/rust-lang/rust/ . It's a serious regression in the compiler, not in combine. I'm sure there's something in combine that can be optimized too, but initially the problem is the compiler :)

[fengalin]

Sure, will report there now.

[fengalin]

This is being handled by the compiler team. Sorry for the noise.