Extreme usage of impl traits leads to excessive rustc memory usage

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 GitHub - neildanson/ngl at types.

The important part is this

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

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

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, the compile comes down to around 10s.

You'd think the compiler must be doing a lot in that time - and I'm sure it is, but the difference between the 2 exes (on windows) - 1kb. So it's not spending its time generating code!

I'm currently rethinking the approach, but I'd love feedback on quite why rustc is soooo unhappy with me!

Type/trait constraint solving is hard. Clever engineering allows most reasonable code to pass compilation in very reasonable time, but technically, a lot of stuff in type checking/inference is still combinatorial/exponential/O(lots). You might just have been unfortunate enough to hit an edge case that happens to trigger such a slow path.

You might want to file an issue and include your reproducer. Some compile-mem blowups are accidental and can be fixed on the compiler side.

1 Like

I was originally going to raise an issue, but while I’m sure my code is correct, I’m not sure how reasonable it is. Thought I’d use this as a litmus test

Will raise an issue later today.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.