Repository: rust
Issue: Exponential time complexity when type checking code with equality constraints
Labels: A-type-system,I-compiletime,T-compiler,S-has-mcve,T-types,C-optimization

Given this significantly reduced example of real-world code,

```rust
#![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
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          |

</details>

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.