derive(DataSize) fails to compile on recursive data structures

[SimonSapin]

enum example:

#[derive(DataSize)]
enum Expression {
    Constant(u32),
    Negation(Box<Self>),
    // ...
}

Output on rustc 1.66.0-nightly (0ca356586 2022-10-06), almost the same as on 1.64.0:

error[E0275]: overflow evaluating the requirement `Expression: DataSize`
 --> src/lib.rs:3:10
  |
3 | #[derive(DataSize)]
  |          ^^^^^^^^
  |
  = note: required because of the requirements on the impl of `DataSize` for `Box<Expression>`
  = help: see issue #48214
  = note: this error originates in the derive macro `DataSize` (in Nightly builds, run with -Z macro-backtrace for more info)

For more information about this error, try `rustc --explain E0275`.

struct example:

use datasize::DataSize;

#[derive(DataSize)]
struct BinaryTree {
    data: u32, // or something
    left: Option<Box<Self>>,
    right: Option<Box<Self>>,
}

error[E0391]: cycle detected when elaborating drops for `<impl at src/lib.rs:3:10: 3:18>::IS_DYNAMIC`
   --> src/lib.rs:3:10
    |
3   | #[derive(DataSize)]
    |          ^^^^^^^^
    |
note: ...which requires const-evaluating + checking `<core::option::Option<T> as datasize::DataSize>::IS_DYNAMIC`...
   --> /Users/simon/.cargo/registry/src/github.com-1ecc6299db9ec823/datasize-0.2.10/src/lib.rs:423:5
    |
423 |     const IS_DYNAMIC: bool = (T::IS_DYNAMIC || T::STATIC_HEAP_SIZE > 0);
    |     ^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating + checking `<core::option::Option<T> as datasize::DataSize>::IS_DYNAMIC`...
   --> /Users/simon/.cargo/registry/src/github.com-1ecc6299db9ec823/datasize-0.2.10/src/lib.rs:423:5
    |
423 |     const IS_DYNAMIC: bool = (T::IS_DYNAMIC || T::STATIC_HEAP_SIZE > 0);
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating + checking `datasize::std::<impl datasize::DataSize for alloc::boxed::Box<T>>::IS_DYNAMIC`...
   --> /Users/simon/.cargo/registry/src/github.com-1ecc6299db9ec823/datasize-0.2.10/src/std.rs:24:5
    |
24  |     const IS_DYNAMIC: bool = T::IS_DYNAMIC;
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating + checking `<impl at src/lib.rs:3:10: 3:18>::IS_DYNAMIC`...
   --> src/lib.rs:3:10
    |
3   | #[derive(DataSize)]
    |          ^^^^^^^^
note: ...which requires caching mir of `<impl at src/lib.rs:3:10: 3:18>::IS_DYNAMIC` for CTFE...
   --> src/lib.rs:3:10
    |
3   | #[derive(DataSize)]
    |          ^^^^^^^^
    = note: ...which again requires elaborating drops for `<impl at src/lib.rs:3:10: 3:18>::IS_DYNAMIC`, completing the cycle
    = note: cycle used when running analysis passes on this crate
    = note: this error originates in the derive macro `DataSize` (in Nightly builds, run with -Z macro-backtrace for more info)

For more information about this error, try `rustc --explain E0391`.

[marc-casperlabs]

Good point, I think this needs an explicit check for recursion to break.

It's also a bit of a footgun, since recursive types have to be walked one-by-one, in general the goal of the crate is to avoid these as much as possible as to not accidentally introduce a lot of resource usage simply by connecting memory usage metrics :/

I'll have to see if I can figure out something.

[SimonSapin]

Some data structures are inherently tree-shaped. Even if traversing them has non-trivial cost it may still be useful in an off-by-default code path to helps debug memory usage issues.