Cannot derive `Facet` for recursive types

[mkeeter]

It looks like we can't derive Facet for a recursive type:

#[derive(Facet)]
pub struct Recursive {
    next: Option<std::sync::Arc<Recursive>>,
}

This produces a long error message, which begins:

error[E0391]: cycle detected when simplifying constant for the type system `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE`
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
   |

...and continues:

The rest of the message

  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires caching mir of `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE` for CTFE...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires elaborating drops for `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires simplifying constant for the type system `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE::promoted[0]`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires const-evaluating + checking `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE::promoted[0]`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires optimizing promoted MIR for `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires simplifying constant for the type system `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE::{constant#0}`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires const-evaluating + checking `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE::{constant#0}`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires simplifying constant for the type system `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE::{constant#0}::{constant#0}`...
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
note: ...which requires const-evaluating + checking `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE::{constant#0}::{constant#0}`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/macros.rs:5:5
   |
5  |     TField::SHAPE
   |     ^^^^^^^^^^^^^
note: ...which requires simplifying constant for the type system `facet_core::_trait::impls::option_impl::<impl facet_core::_trait::Facet for core::option::Option<T>>::SHAPE`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/option_impl.rs:6:5
   |
6  |     const SHAPE: &'static Shape = &const {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating + checking `facet_core::_trait::impls::option_impl::<impl facet_core::_trait::Facet for core::option::Option<T>>::SHAPE`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/option_impl.rs:6:36
   |
6  |       const SHAPE: &'static Shape = &const {
   |  ____________________________________^
7  | |         Shape::builder()
8  | |             .id(ConstTypeId::of::<Self>())
9  | |             .layout(Layout::new::<Self>())
...  |
45 | |             .build()
46 | |     };
   | |_____^
note: ...which requires simplifying constant for the type system `facet_core::_trait::impls::option_impl::<impl facet_core::_trait::Facet for core::option::Option<T>>::SHAPE::{constant#0}`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/option_impl.rs:6:42
   |
6  |       const SHAPE: &'static Shape = &const {
   |  __________________________________________^
7  | |         Shape::builder()
8  | |             .id(ConstTypeId::of::<Self>())
9  | |             .layout(Layout::new::<Self>())
...  |
45 | |             .build()
46 | |     };
   | |_____^
note: ...which requires const-evaluating + checking `facet_core::_trait::impls::option_impl::<impl facet_core::_trait::Facet for core::option::Option<T>>::SHAPE::{constant#0}`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/option_impl.rs:12:24
   |
12 |                     .t(T::SHAPE)
   |                        ^^^^^^^^
note: ...which requires simplifying constant for the type system `facet_core::_trait::impls::smart_pointer_impls::<impl facet_core::_trait::Facet for alloc::sync::Arc<T>>::SHAPE`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/smart_pointer_impls.rs:10:5
   |
10 |     const SHAPE: &'static crate::Shape = &const {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating + checking `facet_core::_trait::impls::smart_pointer_impls::<impl facet_core::_trait::Facet for alloc::sync::Arc<T>>::SHAPE`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/smart_pointer_impls.rs:10:43
   |
10 |       const SHAPE: &'static crate::Shape = &const {
   |  ___________________________________________^
11 | |         crate::Shape::builder()
12 | |             .id(ConstTypeId::of::<Self>())
13 | |             .layout(Layout::new::<Self>())
...  |
40 | |             .build()
41 | |     };
   | |_____^
note: ...which requires simplifying constant for the type system `facet_core::_trait::impls::smart_pointer_impls::<impl facet_core::_trait::Facet for alloc::sync::Arc<T>>::SHAPE::{constant#0}`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/smart_pointer_impls.rs:10:49
   |
10 |       const SHAPE: &'static crate::Shape = &const {
   |  _________________________________________________^
11 | |         crate::Shape::builder()
12 | |             .id(ConstTypeId::of::<Self>())
13 | |             .layout(Layout::new::<Self>())
...  |
40 | |             .build()
41 | |     };
   | |_____^
note: ...which requires const-evaluating + checking `facet_core::_trait::impls::smart_pointer_impls::<impl facet_core::_trait::Facet for alloc::sync::Arc<T>>::SHAPE::{constant#0}`...
  --> /Users/mkeeter/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/facet-core-0.5.3/src/_trait/impls/smart_pointer_impls.rs:16:24
   |
16 |                     .t(T::SHAPE)
   |                        ^^^^^^^^
   = note: ...which again requires simplifying constant for the type system `shapes::<impl at fidget/src/shapes/mod.rs:24:10: 24:15>::SHAPE`, completing the cycle
note: cycle used when evaluating initializer of static `shapes::RECURSIVE_A_SHAPE`
  --> fidget/src/shapes/mod.rs:24:10
   |
24 | #[derive(Facet)]
   |          ^^^^^
   = 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
   = note: this error originates in the derive macro `Facet` (in Nightly builds, run with -Z macro-backtrace for more info)

On one hand, this makes sense – the SHAPE would have to be recursive – but on the other hand, this is an unfortunate limitation!

[fasterthanlime]

I mean, given that the shape is const/static... I don't see why it wouldn't be able to be recursive.

But that is a question for the compiler team, I suppose.

One way to work around that, and one way I've worked around that in the past, is to break the recursion with a function. So instead of having a static reference to a shape when recursing, you have a function that returns a shape. Of course, that makes it harder/impossible to explore shapes in const fn contexts, but because that is already kind of not very useful because we cannot have even just equality comparison in const fn. I believe it might be worth looking into.

In fact, I used to have a shape descriptor trait that was just a function that returns a shape.

So I'm thinking let's take the pragmatic approach and allow more things at runtime and describing more shapes.

cc @oli-obk

[oli-obk]

Such cycles can only be avoided for static items, not for consts, but associated statics are not a concept we have. Maybe try inserting a static item and only referencing that instead of returning a reference from the const

[fasterthanlime]

Maybe try inserting a static item and only referencing that

You mean:

const SHAPE: Shape = const {
  static SHAPE: Shape = Shape {
     some_deep_field: &SHAPE,
  };
  &SHAPE
}

?

[oli-obk]

yes

struct Shape {
    some_deep_field: &'static Shape
}

const SHAPE: &Shape = {
  static HELPER: Shape = Shape {
     some_deep_field: SHAPE,
  };
  &HELPER
};

[oli-obk]

oh huh

error[E0391]: cycle detected when simplifying constant for the type system `SHAPE`
 --> src/lib.rs:5:1
  |
5 | const SHAPE: &Shape = {
  | ^^^^^^^^^^^^^^^^^^^
  |
note: ...which requires const-evaluating + checking `SHAPE`...
 --> src/lib.rs:5:1
  |
5 | const SHAPE: &Shape = {
  | ^^^^^^^^^^^^^^^^^^^
note: ...which requires evaluating initializer of static `SHAPE::HELPER`...
 --> src/lib.rs:7:23
  |
7 |      some_deep_field: SHAPE,
  |                       ^^^^^
  = note: ...which again requires simplifying constant for the type system `SHAPE`, completing the cycle
  = note: cycle used when running analysis passes on this crate
  = 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

[fasterthanlime]

Ok, well:

#[derive(Debug)]
struct ShapeLike {
    next: Option<&'static ShapeLike>,
}

static EMPTY_TUPLE_SHAPE: ShapeLike = {
    ShapeLike {
        next: Some(&EMPTY_TUPLE_SHAPE),
    }
};

impl FacetLike for () {
    const SHAPE_LIKE: &'static ShapeLike = &EMPTY_TUPLE_SHAPE;
}

trait FacetLike {
    const SHAPE_LIKE: &'static ShapeLike;
}

#[test]
fn cyclic_shape() {
    let shape = &EMPTY_TUPLE_SHAPE;
    assert!(shape.next.is_some());

    eprintln!("ShapeLike2: {:?}", <()>::SHAPE_LIKE);
}

me(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike { next: Some(ShapeLike
thread 'cyclic_shape' has overflowed its stack
fatal runtime error: stack overflow

  Cancelling due to test failure
────────────
     Summary [   0.016s] 1 test run: 0 passed, 1 failed, 30 skipped
     SIGABRT [   0.012s] facet::cycle cyclic_shape
error: test run failed

facet2 on  main [!+] via 🦀 v1.86.0

[oli-obk]

XD well, unfortunately that is somewhat to be expected, not sure what to do about that. The compiler avoids that by not storing the nested type information directly, but to use an id scheme to fetch the field information of Adts from a map

[fasterthanlime]

yeah yep. The problem with the static comes when generic type parameters come:

[oli-obk]

ah we solved recursive types and broke generic types 💀

[fasterthanlime]

ah we solved recursive types and broke generic types 💀

me looks at rust-lang/rfcs#3490 and cries

[oli-obk]

that wouldn't help here. the generic parameter just isn't available in the static.

[fasterthanlime]

Well, so, the only workable solution on stable (and for the near future) is to just do indirection like in:

#[derive(Debug)]
struct ShapeLike {
    next: Option<fn() -> &'static ShapeLike>,
}

impl FacetLike for () {
    const SHAPE_LIKE: &'static ShapeLike = &const {
        ShapeLike {
            next: Some(|| Self::SHAPE_LIKE),
        }
    };
}

impl<T: FacetLike> FacetLike for Vec<T> {
    const SHAPE_LIKE: &'static ShapeLike = &ShapeLike {
        next: Some(|| T::SHAPE_LIKE),
    };
}

trait FacetLike {
    const SHAPE_LIKE: &'static ShapeLike;
}

#[test]
fn cyclic_shape() {
    assert!(<()>::SHAPE_LIKE.next.is_some());
}

I'm asking about const fn in trait because, if trait() was a const fn... then this would be less of a big deal? Or am I mistaken and it wouldn't work anyway because shape doesn't have a receiver?