Typechecking does not scale well for deeply nested types

[Marwes]

Currently trying to write a parser combinator library and ideally I would like to have everything statically dispatched which means that the types created can become very deeply nested. There are ways around this of course but I would still not expect the compiler to hang for so long. Sadly I can't come up with a nice small example since simply creating a generic struct (struct A<X, Y>(X, Y);) and nesting it deeply does not seem to be affected.

56s 1138 characters long type

parser-combinators::parser::Map<parser-combinators::parser::Skip<parser-combinators::parser::With<parser-combinators::parser::StringP<'_, _>, parser-combinators::parser::Map<parser-combinators::parser::SepBy<parser-combinators::parser::And<parser-combinators::parser::Skip<parser-combinators::parser::Map<parser-combinators::parser::Skip<parser-combinators::parser::With<parser-combinators::parser::StringP<'_, _>, parser-combinators::parser::Chars<parser-combinators::parser::Satisfy<_, closure[main.rs:16:24: 16:70]>>>, parser-combinators::parser::StringP<'_, _>>, closure[main.rs:18:14: 18:31], collections::string::String>, parser-combinators::parser::StringP<'_, _>>, fn(parser-combinators::primitives::State<_>) -> core::result::Result<(Value, parser-combinators::primitives::State<_>), parser-combinators::primitives::ParseError>>, parser-combinators::parser::StringP<'_, _>>, closure[main.rs:23:14: 23:45], std::collections::hash::map::HashMap<collections::string::String, Value>>>, parser-combinators::parser::StringP<'_, _>>, fn(std::collections::hash::map::HashMap<collections::string::String, Value>) -> Value {Object}, Value>

200s 1264 characters long type (should just be one more type nested)

parser-combinators::parser::Map<parser-combinators::parser::Skip<parser-combinators::parser::With<parser-combinators::parser::StringP<'_, _>, parser-combinators::parser::Map<parser-combinators::parser::SepBy<parser-combinators::parser::And<parser-combinators::parser::Skip<parser-combinators::parser::Map<parser-combinators::parser::With<parser-combinators::parser::Many<parser-combinators::parser::Satisfy<_, fn(char) -> bool>>, parser-combinators::parser::Skip<parser-combinators::parser::With<parser-combinators::parser::StringP<'_, _>, parser-combinators::parser::Chars<parser-combinators::parser::Satisfy<_, closure[main.rs:17:24: 17:70]>>>, parser-combinators::parser::StringP<'_, _>>>, closure[main.rs:19:14: 19:31], collections::string::String>, parser-combinators::parser::StringP<'_, _>>, fn(parser-combinators::primitives::State<_>) -> core::result::Result<(Value, parser-combinators::primitives::State<_>), parser-combinators::primitives::ParseError>>, parser-combinators::parser::StringP<'_, _>>, closure[main.rs:24:14: 24:45], std::collections::hash::map::HashMap<collections::string::String, Value>>>, parser-combinators::parser::StringP<'_, _>>, fn(std::collections::hash::map::HashMap<collections::string::String, Value>) -> Value {Object}, Value>

Code compiled using https://github.com/Marwes/parser-combinators

extern crate "parser-combinators" as parser_combinators;
use parser_combinators::*;
use parser_combinators::primitives::{State, Stream};
use std::collections::HashMap;

enum Value {
    Number(f64),
    String(String),
    Bool(bool),
    Null,
    Object(HashMap<String, Value>),
    Array(Vec<Value>)
}
fn value<I: Stream<Item=char>>(input: State<I>) -> ParseResult<Value, I> {
    let char = satisfy(|c| "\"\\".chars().find(|x| *x == c).is_none());
    let json_string = between(string("\""), string("\""), chars(char))
        .map(|s| s.to_string());
    let field = json_string
        .skip(string(":"))
        .and(value as fn (_) -> _);
    let fields = sep_by(field, string(","))
        .map(|vec| vec.into_iter().collect());
    let mut object: () = between(string("{"), string("}"), fields)
        .map(Value::Object);
    object
        .parse_state(input)
}


fn main() {
}

[Marwes]

Did some investigating into the cause of this and since I do not think I have the knowledge to fix this I will simply share what I have found so far (this is all done on windows).

I compiled rustc with debug information and profiled the execution of the program above which showed that the time was mostly spent inside the instantiate function in combine.rs.

Furthermore by turning on logging for this crate led to me seeing a lot of lines like these:

DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#26t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#591t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#560t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#166t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#166t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#166t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#166t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#602t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#602t)
DEBUG:rustc::middle::infer::equate: eq.tys(I, I)
DEBUG:rustc::middle::infer::combine: instantiate(a_ty=I dir=EqTo b_vid=_#602t)

And I just happens to be what I used to name the type parameter for the value above! Indeed if the function is simply specialized the program will compile within a reasonable amount of time.

fn value(input: State<&str>) -> ParseResult<Value, &str> {

Hopefully this will point someone more knowledgeable into the right direction.

[Marwes]

Probably related to #23069

[hawkw]

👍

[Marwes]

Closing as this specific performance problem was fixed in #32062.