rustc hangs with gordian knot of trait bounds

[alex]

Given the following code, rustc hangs:

mod asn1 {
    pub trait Asn1Writable: Sized {}
    pub trait SimpleAsn1Writable: Sized {}

    impl<T: SimpleAsn1Writable> Asn1Writable for T {}
    impl<T: SimpleAsn1Writable> SimpleAsn1Writable for &T {}
    impl<T: SimpleAsn1Writable> SimpleAsn1Writable for Box<T> {}

    impl<T: Asn1Writable> Asn1Writable for Option<T> {}

    pub trait Asn1DefinedByWritable: Sized {}
}

mod common {
    use crate::asn1;

    pub struct AlgorithmIdentifier<'a> {
        pub params: AlgorithmParameters<'a>,
    }

    impl<'a> asn1::SimpleAsn1Writable for AlgorithmIdentifier<'a> where
        AlgorithmParameters<'a>: asn1::Asn1DefinedByWritable
    {
    }

    pub enum AlgorithmParameters<'a> {
        Sha1,
        Pbkdf2(PBKDF2Params<'a>),
    }

    impl<'a> asn1::Asn1DefinedByWritable for AlgorithmParameters<'a>
    where
        PBES2Params<'a>: asn1::Asn1Writable,
        PBKDF2Params<'a>: asn1::Asn1Writable,
    {
    }

    pub const PSS_SHA1_HASH_ALG: AlgorithmIdentifier<'_> = AlgorithmIdentifier {
        params: AlgorithmParameters::Sha1,
    };

    pub struct RsaPssParameters<'a> {
        pub hash_algorithm: AlgorithmIdentifier<'a>,
    }

    impl<'a> asn1::SimpleAsn1Writable for RsaPssParameters<'a> {}

    pub struct PBES2Params<'a> {
        pub key_derivation_func: Box<AlgorithmIdentifier<'a>>,
    }

    impl<'a> asn1::SimpleAsn1Writable for PBES2Params<'a> where
        Box<AlgorithmIdentifier<'a>>: asn1::Asn1Writable
    {
    }

    pub struct PBKDF2Params<'a> {
        pub salt: &'a [u8],
    }

    impl<'a> asn1::SimpleAsn1Writable for PBKDF2Params<'a> where
        Box<AlgorithmIdentifier<'a>>: asn1::Asn1Writable
    {
    }
}

pub fn write_element<T: asn1::Asn1Writable>(val: &T) {
    todo!()
}

pub fn f(p: &common::RsaPssParameters<'_>) {
    write_element(&Some(&p.hash_algorithm));
}

fn main() {}

/t/q ❯❯❯ rustc src/main.rs
[no amount of patience is enough]

This is minimized from https://github.com/pyca/cryptography and https://github.com/alex/rust-asn1.

Meta

rustc --version --verbose:

rustc 1.82.0 (f6e511eec 2024-10-15)
binary: rustc
commit-hash: f6e511eec7342f59a25f7c0534f1dbea00d01b14
commit-date: 2024-10-15
host: aarch64-apple-darwin
release: 1.82.0
LLVM version: 19.1.1

[alex]

Well, this is embarrassing. After waiting longer than I ever have before (several minutes), it does finally error with:

error[E0275]: overflow evaluating the requirement `AlgorithmIdentifier<'_>: Sized`

I'm not sure if this is worth tracking as a "the compiler is way too slow", or if it's better closed as a degenerate case.

[compiler-errors]

Next solver gives a result immediately (also an overflow), for the record.

[alex]

That's great! So I guess there's three possibilities:

1. Close now, there's nothing meaningful to track.
2. Leave open to track "erroring faster", which can be closed when the next solver ships.
3. Leave open to track "this code should compile successfully", which can be closed when the solver can handle the cyclic horrors I have discovered.

This seems like its primarily a question for the rustc maintainers. Obviously I have a desire for it to work, but erroring cleanly is an A+ start :-)

[alex]

FWIW, the thing that led to this code was an implementation of perfect derives.

https://smallcultfollowing.com/babysteps/blog/2022/04/12/implied-bounds-and-perfect-derive/#making-perfect-derive-sound-was-tricky-but-we-can-do-it-now notes seems to indicate fundamental conceptual blockers to cyclic trait matching have been addressed, but doesn't go so far as to say they actually work :-)

[compiler-errors]

@alex: They do not work. The blog post says:

For now, though, let’s just assume we can do it soundly.

That is, the blog post is assuming theoretical support for a general trait solver feature called coinduction that we do not have. You should something between (2.) and (3.) -- it should not hang, but also I don't expect it to be successful soon (or at all, depending on how the code is written -- I didn't spend too much time actually manually reasoning the impls here are valid).

[alex]

Thanks