Exponential time complexity when type checking code with equality constraints

[jhpratt]

Given this significantly reduced example of real-world code,

#![allow(unused_variables, dead_code, clippy::empty_loop)]

struct ParsedItem<'a, T> {
    value: T,
    remaining: &'a [u8],
}

trait Parser<'a>: Sized {
    type Output;
    type Error;

    fn parse(self, input: &'a [u8]) -> Result<ParsedItem<'a, Self::Output>, Self::Error> {
        loop {}
    }

    fn map<F, NewOutput>(self, f: F) -> Map<Self, F>
    where
        F: Fn(Self::Output) -> NewOutput + Copy,
    {
        loop {}
    }

    fn or_unify<P2>(self, other: P2) -> OrUnify<Self, P2>
    where
        P2: Parser<'a, Output = Self::Output, Error = Self::Error>,
    {
        loop {}
    }
}

struct Verbatim<'a>(&'a [u8]);

impl<'a, 'b> Parser<'a> for Verbatim<'b> {
    type Output = &'b [u8];
    type Error = ();
}

struct OrUnify<P1, P2> {
    p1: P1,
    p2: P2,
}

impl<'a, P1, P2> Parser<'a> for OrUnify<P1, P2>
where
    P1: Parser<'a>,
    P2: Parser<'a, Output = P1::Output, Error = P1::Error>,
{
    type Output = P1::Output;
    type Error = P1::Error;
}

struct Map<P, F> {
    parser: P,
    f: F,
}

impl<'a, P, F, NewOutput> Parser<'a> for Map<P, F>
where
    P: Parser<'a>,
    F: Fn(P::Output) -> NewOutput + Copy,
{
    type Output = NewOutput;
    type Error = P::Error;
}

pub fn parse_week_number(input: &[u8]) {
    #[cfg(not(feature = "slowdown"))]
    let _ = Verbatim(b"Jan")
        .map(|_| 1u8)
        .or_unify(Verbatim(b"Feb").map(|_| 2))
        .or_unify(Verbatim(b"Mar").map(|_| 3))
        .parse(input);

    #[cfg(feature = "slowdown")]
    let _ = Verbatim(b"Jan")
        .map(|_| 1u8)
        .or_unify(Verbatim(b"Feb").map(|_| 2))
        .or_unify(Verbatim(b"Mar").map(|_| 3))
        .or_unify(Verbatim(b"Apr").map(|_| 4))
        .or_unify(Verbatim(b"May").map(|_| 5))
        .or_unify(Verbatim(b"Jun").map(|_| 6))
        .or_unify(Verbatim(b"Jul").map(|_| 7))
        .or_unify(Verbatim(b"Aug").map(|_| 8))
        .or_unify(Verbatim(b"Sep").map(|_| 9))
        // .or_unify(Verbatim(b"Oct").map(|_| 10))
        // .or_unify(Verbatim(b"Nov").map(|_| 11))
        // .or_unify(Verbatim(b"Dec").map(|_| 12))
        .parse(input);
}

compiling with the larger number of chained methods (i.e. with #[cfg(feature = "slowdown")]) results in apparent exponential (correlation = 0.992) time complexity for cargo check. The code as written takes approximately 9-10 seconds to type check on my laptop. Uncommenting two of the three lines that are presently commented out took 7m51s (471 seconds) for the same.

Checking with -Znext-solver improves the situation quite a bit, but the behavior still seems to be exponential.

Removing the equality constraints from or_unify avoids the pathological case entirely. I suspect this is a starting point for investigating a possible fix.

diff --git a/src/lib.rs b/src/lib.rs
index 712a079..693a5a0 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -22,7 +22,7 @@ trait Parser<'a>: Sized {

     fn or_unify<P2>(self, other: P2) -> OrUnify<Self, P2>
     where
-        P2: Parser<'a, Output = Self::Output, Error = Self::Error>,
+        P2: Parser<'a>,
     {
         loop {}
     }
@@ -43,7 +43,7 @@ struct OrUnify<P1, P2> {
 impl<'a, P1, P2> Parser<'a> for OrUnify<P1, P2>
 where
     P1: Parser<'a>,
-    P2: Parser<'a, Output = P1::Output, Error = P1::Error>,
+    P2: Parser<'a>,
 {
     type Output = P1::Output;
     type Error = P1::Error;

Difference using -Zself-profile (nearly all rows elided for brevity, plus most changes are just noise)

Item	Self Time	Self Time Change	Time	Time Change	Item count	Cache hits	Blocked time	Incremental load time	Incremental hashing time
typeck	-3.848198128s	-99.81%	-3.941711228s	-99.78%	-2	+0	+0ns	+31.12µs	-15.217µs
normalize_canonicalized_projection_ty	-3.656869016s	-99.89%	-3.656883736s	-99.89%	-21	+0	+0ns	+0ns	-13.504285ms
type_op_prove_predicate	-3.170638403s	-99.88%	-3.170657974s	-99.88%	-16	+0	+0ns	+0ns	-13.335546ms
codegen_select_candidate	-879.739365ms	-99.91%	-879.721645ms	-99.91%	-2	+0	+0ns	+6.442µs	-19.687µs
evaluate_obligation	-93.317948ms	-99.11%	-93.282306ms	-98.89%	-18	+0	+0ns	+0ns	-8.917µs
free_global_ctxt	-64.501655ms	-97.11%	-62.313864ms	-93.79%	+0	+0	+0ns	+0ns	+0ns
try_normalize_generic_arg_after_erasing_regions	-54.38067ms	-99.89%	-1.842779579s	-99.86%	-5	+0	+0ns	+0ns	-5.841µs
type_op_normalize_fn_sig	-48.7221ms	-99.76%	-1.369293326s	-99.89%	+0	+0	+0ns	+0ns	-3.114µs
type_op_normalize_clause	-11.183646ms	-99.22%	-559.088233ms	-99.98%	-16	+0	+0ns	+0ns	-27.737µs
mir_borrowck	-8.154685ms	-83.52%	-5.107647653s	-99.85%	-3	+0	+0ns	+671ns	-10.507µs

Total cpu time: -11.830756846s

Item	Artifact Size Change
object_file	48 bytes
work_product_index	0 bytes
codegen_unit_size_estimate	0 bytes
cgu_instructions	0 bytes
linked_artifact	-32 bytes
crate_metadata	-77 bytes
query_cache	-480 bytes
dep_graph	-5683 bytes

Without performing a thorough check, I checked the time to type check on both 1.65 and 1.40 with similar results. Given that, this behavior has been around for 4+ years at a minimum.

[theemathas]

Minimized example, producing the exponential time behavior, albeit apparently at a slower growth.

#![allow(unused_variables, dead_code)]

trait SomeTrait<'a> {
    type Output;
}

fn get_some_trait<'a>(_x: impl SomeTrait<'a>) {}

fn wrap<T: SomeTrait<'static, Output = u8>>(x: T) -> Wrapped<T> {
    Wrapped(x)
}

struct Thing;

impl SomeTrait<'static> for Thing {
    type Output = u8;
}

struct Wrapped<P>(P);

impl<'a, P: SomeTrait<'a, Output = u8>> SomeTrait<'a> for Wrapped<P> {
    type Output = P::Output;
}

pub fn parse_week_number() {
    let _ =
        get_some_trait(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        wrap(
        Thing
        ))))))))))))))));
}