rustc hangs when compiling `varisat` (`-Znext-solver`)

[lcnr]

Not sure if I should file a separate issue or not. Here is the minimized reproducer we saw in rust-lang/cargo's CI failure with the crate varisat:

/tmp/repro.rs

---cargo
[package]
edition = "2024"

[dependencies]
varisat = "=0.2.2"
---

fn main() {
    let _solver = varisat::Solver::new();
}

And run it

# this got stuck
cargo +nightly-2026-08-22 -Zscript check --manifest-path /tmp/repro.rs

# this succeeded
env RUSTFLAGS="-Znext-solver=coherence" cargo +nightly-2026-08-22 -Zscript check --manifest-path /tmp/repro.rs

# this succeeded
cargo +nightly-2026-08-21 -Zscript check --manifest-path /tmp/repro.rs

# this got stuck
env RUSTFLAGS="-Znext-solver=globally" cargo +nightly-2026-08-21 -Zscript check --manifest-path /tmp/repro.rs

Originally posted by @weihanglo in #160895

[lcnr]

minimized with the help of an LLM. The following matches the exponential blowup here. Using 14 compiles rather quickly and then it goes to nowhere :>

trait HasTarget { type Target; }
trait PartialRef<'a>: HasTarget + Sized { fn make(_: Self::Target) -> Self { loop {} } }

struct Ref<'a, T>(&'a mut T);
impl<'a, T> HasTarget for Ref<'a, T> { type Target = T; }
impl<'a, 'b: 'a, T> PartialRef<'a> for Ref<'b, T> {}

struct Mut<T: HasTarget>(T);
impl<'a, T: PartialRef<'a>> HasTarget for Mut<T> where T::Target: Sized { type Target = T::Target; }
impl<'a, T: PartialRef<'a>> PartialRef<'a> for Mut<T> where T::Target: Sized {}

macro_rules! mut_wraps {
    ($inner:ty;) => { $inner };
    ($inner:ty; $next:tt $($rest:tt)*) => {
        Mut<mut_wraps!($inner; $($rest)*)>
    };
}

type Deep<'a> = mut_wraps!(Ref<'a, ()>; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21);

fn make<'a>(value: ()) -> Deep<'a> { <Deep<'a> as PartialRef<'a>>::make(value) }
fn main() {}

The source of that issue is https://github.com/jix/varisat/blob/33e876937c5d22305664e9ae5601484b25cec23f/varisat/src/context.rs#L57-L97, see the result of cargo expand https://gist.github.com/lcnr/654105a549d9efbc72461815d38abf05

[lcnr]

What's happening here is that proving Mut<Mut<T>>: PartialRef<'a> requires

• Mut<T>: PartialRef<'a>
• <Mut<T> as HasTarget>::Target: Sized

Normalizing <Mut<T> as HasTarget>::Target requires proving T: PartialRef<'unconstrained> and also uses <T as HasTarget>::Target. 'unconstrained remains unconstrained because impl<'a, 'b: 'a, T> PartialRef<'a> for Ref<'b, T> only constrains 'a to be shorter than 'b, not 'b itself.

so there are two nested goals per step which require proving HasTarget. Each such nested goal adds a different 'unconstrained itself and then recurs. That means for a recursion depth of N we get ~2^N unconstrained regions which only have to be outlived by the 'a from the innermost Ref<'a, ()>

[lcnr]

Fixing this on our end is kind of dubious. We could deduplicate inference variables which are only named by outlives constraints, but that's non-trivial and I also don't think we should even support this necessarily 🤔

For now opened jix/partial_ref#6, which is an easier fix. We should at least warn on such impls :<

[weihanglo]

Thanks for the swift diagnosis!

Just FYI that this hit us in a test that is not essential (comparing Cargo dep solver with an SAT solver). We may be able to move away or temporarily disable the test.

[lcnr]

Released as partial_ref 0.3.4. the hang should now be gone. gonna keep this open until tracking the fact that there is a compile-time regression here somewhere else

[Shelim]

Is there a way to just crash compilation or halt with any error message? My compilation of varisat with old partial_ref run continuously, wasting more and more RAM, up to 63 GB before exhausting PC resources. If left unintended it can easily crash other PC services, not to mention burning cloud resources.

[lcnr]

Is there a way to just crash compilation or halt with any error message? My compilation of varisat with old partial_ref run continuously, wasting more and more RAM, up to 63 GB before exhausting PC resources. If left unintended it can easily crash other PC services, not to mention burning cloud resources.

Does feel generally desirable. There are OOM killers which handle processes taking too much memory more gracefully than most OS. I don't know whether there's something we can do on the rustc side. We could do something hacky to detect such cases and may generally fix the underlying issue. I guess

• we generally don't want rustc to hang/take an exponential amount of memory and want to fix the underlying issue (also the case here)
• doing so in all cases is incredibly hard and hacky fixes tend to accidentally prevent correct code
• changing rustc to handle such bugs itself more gracefully is probably quite challenging, but I am not an expert here