"cycle detected when building an abstract representation..." issue

[fubupc]

This is a problem when implementing a bitfield macro in Rust.

pub trait Bits {
    const BITS: usize; // How many bits this field has

    type Underlying; // Minimum underlying uint (u8, u16, ...) to store this field

    fn from_arbint(from: arbitrary_int::UInt<Self::Underlying, { Self::BITS }>) -> Self;
}

This code uses an arbitrary precision integer library: arbitrary-int. Trait Bits is used to describe:

• How many bits this field has.
• Minimum underlying uint type to store this field, like u8, u16, .. etc.
• How to convert an arbitrary_int::UInt<T, BITS> to this field.
  For example, for a bool type:

impl Bits for bool {
    const BITS: usize = 1;

    type Underlying = u8;

    fn from_arbint(from: arbitrary_int::UInt<Self::Underlying, { Self::BITS }>) -> Self {
        from.value() == 1
    }
}

For array type it becomes a bit more complicated:

// Used to calculate the minimun uint type to store bits 
pub trait CalcUint {
    type Uint;
}
impl CalcUint for [(); 1] {
    type Uint = u8;
}
...
impl CalcUint for [(); 9] {
    type Uint = u16;
}
...

impl<T, const N: usize> Bits for [T; N]
where
    T: Bits + Default + Copy,
    [(); T::BITS * N]: CalcUint,
{
    const BITS: usize = T::BITS * N;

    type Underlying = <[(); T::BITS * N] as CalcUint>::Uint;

    fn from_arbint(from: arbitrary_int::UInt<Self::Underlying, { Self::BITS }>) -> Self {
        todo!()
    }
}

Then the compiler report error at { Self::BITS } in from_arbint:

error[E0391]: cycle detected when building an abstract representation for `<impl at src/lib.rs:53:1: 56:33>::from_arbint::{constant#0}`
  --> src/lib.rs:62:64
   |
62 |     fn from_arbint(from: arbitrary_int::UInt<Self::Underlying, { Self::BITS }>) -> Self {
   |                                                                ^^^^^^^^^^^^^^
   |
note: ...which requires building THIR for `<impl at src/lib.rs:53:1: 56:33>::from_arbint::{constant#0}`...
  --> src/lib.rs:62:64
   |
62 |     fn from_arbint(from: arbitrary_int::UInt<Self::Underlying, { Self::BITS }>) -> Self {
   |                                                                ^^^^^^^^^^^^^^
note: ...which requires type-checking `<impl at src/lib.rs:53:1: 56:33>::from_arbint::{constant#0}`...
  --> src/lib.rs:62:72
   |
62 |     fn from_arbint(from: arbitrary_int::UInt<Self::Underlying, { Self::BITS }>) -> Self {
   |                                                                        ^^^^
   = note: ...which requires evaluating trait selection obligation `[T; N]: Bits`...
   = note: ...which again requires building an abstract representation for `<impl at src/lib.rs:53:1: 56:33>::from_arbint::{constant#0}`, completing the cycle
note: cycle used when checking that `<impl at src/lib.rs:53:1: 56:33>` is well-formed
  --> src/lib.rs:53:1
   |
53 | / impl<T, const N: usize> Bits for [T; N]
54 | | where
55 | |     T: Bits + Default + Copy,
56 | |     [(); T::BITS * N]: CalcUint,
   | |________________________________^
   = note: see https://rustc-dev-guide.rust-lang.org/overview.html#queries and https://rustc-dev-guide.rust-lang.org/query.html for more information

Can someone help to explain why is this happening and how to fix it? Thanks!

PS: For complete code: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=a893e99e95aa2a964fa49546a9fbdaaa .
NOTE: The playground does not support random 3rd party library(?), so one need to copy code to local for test/debug.

[lcnr]

the root cause here is #36 / rust-lang/rust#79356

generic constants in where-bounds are unfortunately very hard to support without getting cycles. I can't given you any tips to fix this apart from trying to remove the generic constants in where-clauses which is probably not useful 😁

[fubupc]

@lcnr Thank you for your response! However, I'm afraid I didn't quite grasp the ideas in those issues.

In the first example:

// check-pass
#![feature(generic_const_exprs)]
#![allow(incomplete_features)]

struct Foo<T>(T);

fn test() where [u8; {
    let _: Foo<[u8; 3 + 4]>;
    3
}]: Sized {}

The cycle happens while typechecking the outer array length.

Outer array here means [u8; {...}]? Then the where-clause [u8; {...}]: Sized requires {let _: Foo<[u8; 3+4]>; 3} to be sized? And then?

This happens because Foo<[u8; 3 + 4]> requires [u8; 3 + 4] to be sized.

Is this because Foo's definition struct Foo<T>(T) implied T: sized?

While trying to fulfill this we see the [u8; ...]: Sized bound in the param_env and try to unify these two. This causes us to evaluate both constants which once again relies on typechecking them.

I'm completely lost here ..

In the second example:

#![feature(generic_const_exprs)]

trait Foo {
    const N: usize;
}

struct Num<const N: usize>
where
    [(); <Self as Foo>::N]: ;

impl<const N: usize> Foo for Num<N> {
    const N: usize = N - 1;
}

Is this how the cycle formed?

1. where-clause [(); <Self as Foo>::N] of Num's definition requires Self: Foo
2. Self is just Num<N> (with where-clause)
3. evaluation of where-clause in (2) brings back to (1)