Degradation from rustc 1.71.0 -> 1.79.0 ("infinite space" compile error not recognized anymore)

[Asqiir]

Behaviour in rust version 1.79.0 (the bug)

I found a program that does

• successfully finish cargo check
• but does never build (it takes up as much space as it can get, and then inevitably crash)

on rust version 1.79.0:

rustc 1.79.0 (129f3b996 2024-06-10)
binary: rustc
commit-hash: 129f3b9964af4d4a709d1383930ade12dfe7c081
commit-date: 2024-06-10
host: x86_64-unknown-linux-gnu
release: 1.79.0
LLVM version: 18.1.7

Behaviour in rust version 1.71.0 (before the degradation)

On rust version 1.71.0 this program failed the cargo check and build, which is the expected behaviour imo.

The minimum working example

use std::io::{self, BufRead};

fn main() -> Result<(), io::Error> {
  let stdin = io::stdin(); // We get `Stdin` here.
  let mut iterate_in = stdin.lock().lines();

  // that's how to run a single request for a number alone in a line
  let count = iterate_in.next().unwrap().unwrap().to_string().parse::<usize>().unwrap();

  let mut rects = vec![];
  for _ in 0..count {
    let vecline = iterate_in.next()
      .unwrap()
      .unwrap()
      .split_whitespace()
      .map(|s| s.parse::<u32>().unwrap()-1)
      .collect();

    let el = (rects[0],rects[1],rects[2],rects[3]);
    rects.push(el);
  }

  if let Some(solution) = rects.to_string() {
    for s in solution {
      println!("{} {}", s.0+1, s.1+1);
    }
  }

  Ok(())
}

[tgross35]

Looks like this happened between 1.77 and 1.78 https://rust.godbolt.org/z/4Wcfa3zaa, still happens on nightly. The lint "cyclic type of infinite size" stopped catching this problem (recursive type between the tuple and the vector).

Seems like something @compiler-errors might be able to ID

successfully finish cargo check

To be clear - it completes but there are errors, right?

[tgross35]

#119989 maybe?

[Asqiir]

To be clear - it completes but there are errors, right?

In 1.79.0:
If it finishes (which it not always does, and I am not sure why) there are no errors.

In 1.71.0:
It finishes quickly but with an error (error about the code it checks, not of the check itself).

[lcnr]

imagine changing the the assignment of el to let el = (rects[0],); (a tuple with 1 element).

The type of rects is Vec<?elem>. The type of el is (?sup,) where ?elem is a subtype of ?sup. This gets stored as a Subtype(?elem, ?sup) obligation.
in rects.push(el) we then apply yet another subtyping relation: (?sup,) is a subtype of ?elem.

This ends up generalizing ?elem to (?subofsup,) and then emitting a Subtype(?subofsup, sup) obligation.

We now have two obligations Subtype((?subofsup,), ?sup) and Subtype(?subofsup, ?sup). Evaluating the subtype obligation which has the tuple ends up generalzing the other side, and then adds another Subtype obligation. This goes on forever, wrapping the original ?elem with yet another tuple each time.

If you have a tuple with one element you quickly get an overflow error. Once you have more than this you have an exponential blowup of obligations and get a hang instead.

[lcnr]

This feels sadly somewhat unavoidable to me unless we readd sub_relations.

I am already considering to do so in general, but tracking them in the FnCtxt instead, i.e. only in the outer context during type inference. This means this information exclusively flows out of the 'core' type system and means we don't need to provide the existing sub_relations as inputs to it. edit: this may not be enough to solve this concrete issue as the hang could happen inside of the trait solver

We removed them as they previously impacted the trait solver without being part of the cache key, resulting in caching bugs whose fix would have otherwise resulted in a significant performance penalty.

[lqd]

#119989 maybe?

(To confirm, it does indeed bisect to this PR, as was evident in lcnr's analysis about sub_relations)