Repository: rust
Issue: Extreme usage of impl traits leads to excessive rustc memory
Labels: A-trait-system,I-compiletime,T-compiler,I-compilemem,C-bug,T-types

I've been working on a parser combinator for a project in rust. I have a background in F#, so have a tendency to think about currying and partial application, which are a natural fit for this type of problem, but not necessarily rust.

After spending some time getting everything working I built something that seems to work quite well. Until you use it...

Here is the full code https://github.com/neildanson/ngl/tree/types.

The important part is this


```rust
pub trait Parser<'a, Output>: Clone {
    fn parse(&self, input: ContinuationState<'a>) -> ParseResult<'a, Output>;
}

#[derive(Debug, Clone)]
struct ClosureParser<'a, Output, F, C>
where
    F: Fn(ContinuationState<'a>, C) -> ParseResult<'a, Output>,
{
    parser: F,
    captures: C,
    _phantom: std::marker::PhantomData<&'a Output>,
}
```

Where using it starts to look like this


```rust
fn pchar_impl<'a>(c: char, input: ContinuationState<'a>) -> ParseResult<char> {
    let mut chars = input.remaining.chars();
    match chars.next() {
        Some(letter) if letter == c => {
            let new_line = if letter == '\n' { 1 } else { 0 };
            let parser_state = input.advance(1, new_line);
            Ok((Token::new(c, input.position, 1), parser_state))
        }
        Some(letter) => Err(Error::new(
            c.to_string(),
            letter.to_string(),
            input.position,
            input.line_number,
            input.line_position,
        )),
        None => Err(Error::new(
            c.to_string(),
            "".to_string(),
            input.position,
            input.line_number,
            input.line_position,
        )),
    }
}
```

and 


```rust
pub fn pchar<'a>(value: char) -> impl Parser<'a, Output = char> {
    ClosureParser::new(move |input, value| pchar_impl(value, input), value)
}
```

If you were to pull that branch, the tests would pass and the benchmarks would run - great!
But it you try to build or run the project - you'll need some coffee and a lot of RAM. On my 5950X it will just about compile after about 15 minutes and sitting on over 100GB RAM (I have 128Gb).

If you extend the commented out from line 40 onwards in [main.rs](https://github.com/neildanson/ngl/blob/types/src/main.rs), the compile comes down to around 10s.

I expected to see this happen: 

Either a successful  compile or fail (and this is the vague hand wavey part) in a reasonable amount of time.

Instead, this happened: 

The code compiles eventually, after using over 100GB RAM to do so (my Mac doesn't have so much ram, so swaps). This seems extreme for an 800 LOC project. 

Adding in 1 more line from the example causes failure. If I had to _guess_ somewhere there is something quadratic going on. 

Whilst I am sure my code is technically correct (it does compile after all), I am not convinced it is _reasonable_ and may be using a language feature to extremes never predicted. 

### Meta

`rustc --version --verbose`:
```
On M1 Pro

rustc 1.73.0-nightly (7bd81ee19 2023-07-13)
binary: rustc
commit-hash: 7bd81ee1902c049691d0a1f03be5558bee51d100
commit-date: 2023-07-13
host: aarch64-apple-darwin
release: 1.73.0-nightly
LLVM version: 16.0.5


On Windows 11
rustc 1.73.0-nightly (903e279f4 2023-07-18)
binary: rustc
commit-hash: 903e279f468590fa3425f8aff7f3d61a5a873dbb
commit-date: 2023-07-18
host: x86_64-pc-windows-msvc
release: 1.73.0-nightly
LLVM version: 16.0.5


```