Exponential trait selection when compiling a crate using combine 4

[Marwes]

Originally reported in Marwes/combine#284 . It appears that the changes made between version 3 and 4 in https://github.com/Marwes/combine . Made trait selection exponential in some cases. The main change that I would suspect causing this is that combine-3 had Input as an associated type whereas combine-4 uses a type parameter.

The following minimized repo reproduces the slowdown, removing a few arguments from the choice! macro makes it compile quickly https://github.com/Marwes/combine-slow-compile . The commit before master contains a version with combine-3 which compiles instantaneously (after dependencies are compiled). (diff Marwes/combine-slow-compile@21cf38a)

[sdroege]

The E-needs-mcve label seems wrong, there's a minimal testcase linked in the initial description :)

[sdroege]

This is btw the same function as in #67454, just that with combine 3 this works fine again now while with combine 4 it exposes the same behaviour

[jonas-schievink]

I tagged it needs-MCVE because the reproduction above still pulls in 2 dependencies. It would be helpful to get it down to a single file.

[Marwes]

Minimized, add more token parsers to get more of a slowdown.

use std::marker::PhantomData;

pub trait Parser<Input> {
    type Output;

    fn or<P2>(self, p: P2) -> Or<Self, P2>
    where
        Self: Sized,
        P2: Parser<Input, Output = Self::Output>,
    {
        Or(self, p)
    }
}

#[macro_export]
macro_rules! choice {
    ($first : expr) => {
        $first
    };
    ($first : expr, $($rest : expr),+) => {
        $first.or(choice!($($rest),+))
    }
}

pub struct Or<P1, P2>(P1, P2);
impl<Input, P1, P2> Parser<Input> for Or<P1, P2>
where
    P1: Parser<Input, Output = P2::Output>,
    P2: Parser<Input>,
{
    type Output = P2::Output;
}

pub struct P<I, O>(PhantomData<fn(I) -> O>);
impl<Input, O> Parser<Input> for P<Input, O> {
    type Output = O;
}

pub fn token<I>(_: u8) -> impl Parser<I, Output = u8> {
    P(PhantomData)
}

fn mcc_payload_item<I>() -> impl Parser<I, Output = u8> {
    choice!(
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G')
    )
}

fn main() {}

[nnethercote]

This was fixed by #67471, which reverted the regressing code from #66405.

[Marwes]

No, this isn't fixed by #67471 . This is a separate issue (even if the reproductions are really similar).