Type inference/resolution error in the presence of Pointee::Metadata in recursive data-structure

[matthieu-m]

The following code causes the latest nightly (2023-05-16) to choke, it can also be seen on the playground.

#![feature(ptr_metadata)]

use core::ptr::Pointee;

struct TypedHandle<E: ?Sized> {
    metadata: <E as Pointee>::Metadata,
}

type NodeHandle<T> = TypedHandle<Node<T>>;

struct Node<T> {
    element: T,
    next: NodeHandle<T>,
    prev: NodeHandle<T>,
}

Credits to Chayim Friedman for this reduced example.

And the compiler, much confused it appears, spits out the following error:

error[[E0284]](https://doc.rust-lang.org/nightly/error_codes/E0284.html): type annotations needed
  --> src/lib.rs:13:11
   |
13 |     next: NodeHandle<T>,
   |           ^^^^^^^^^^^^^ cannot infer type
   |
   = note: cannot satisfy `<Node<T> as Pointee>::Metadata == _`
note: required because it appears within the type `TypedHandle<Node<T>>`
  --> src/lib.rs:5:8
   |
5  | struct TypedHandle<E: ?Sized> {
   |        ^^^^^^^^^^^
   = note: only the last field of a struct may have a dynamically sized type
   = help: change the field's type to have a statically known size
help: borrowed types always have a statically known size
   |
13 |     next: &NodeHandle<T>,
   |           +
help: the `Box` type always has a statically known size and allocates its contents in the heap
   |
13 |     next: Box<NodeHandle<T>>,
   |           ++++             +

The compiler accepts the code:

• If the metadata is stored in a NonNull<E> in TypedHandle.
• If the ?Sized bound is removed from E in TypedHandle.
• If the where NodeHandle<T>: Sized bound is added on Node.

Given the messages, and the fixes, it appears that the compiler fails to realize that <E as Pointee>::Metadata is always Sized, regardless of whether E is Sized or not, even though Metadata is necessarily Sized since its bounds do not specify ?Sized. This in turn would lead the compiler to expect that TypedHandle may be unsized, and thus reject any code where it is not the last field of a struct.

[matthieu-m]

A slightly trimmed example leads to a shorter error message:

#![feature(ptr_metadata)]

use core::ptr::Pointee;

struct Node<T> {
    element: T,
    next: <Node<T> as Pointee>::Metadata,
    prev: <Node<T> as Pointee>::Metadata,
}

Error message:

error[[E0284]](https://doc.rust-lang.org/nightly/error_codes/E0284.html): type annotations needed
 --> src/lib.rs:7:11
  |
7 |     next: <Node<T> as Pointee>::Metadata,
  |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot infer type
  |
  = note: cannot satisfy `<Node<T> as Pointee>::Metadata == _`

[lukas-code]

Regressed in #92248, cc @compiler-errors.

Changing the struct's tail makes the error go away:

#![feature(ptr_metadata)]

use core::ptr::Pointee;

struct Node<T> {
    element: T,
    next: <Node<T> as Pointee>::Metadata,
    prev: <Node<T> as Pointee>::Metadata,
    _tail: (),
}

bisect results

found 4 bors merge commits in the specified range
  commit[0] 2022-01-09: Auto merge of #92534 - Aaron1011:hash-hir, r=petrochenkov
  commit[1] 2022-01-10: Auto merge of #92278 - Aaron1011:fix-fingerprint-caching, r=michaelwoerister
  commit[2] 2022-01-10: Auto merge of #87487 - lambinoo:I-64762_unreachable_pub_lint, r=petrochenkov
  commit[3] 2022-01-10: Auto merge of #92719 - matthiaskrgr:rollup-tc7oqys, r=matthiaskrgr
ERROR: no CI builds available between 092e1c9d23158d81be27bb6f71bdd0c6282478fb and 89b9f7b284aacc5f8613438b80e4dd7bdd10549e within last 167 days

[compiler-errors]

Yeah, this is basically a cycle that the current trait solver is not smart enough to solve. The struct must be sized for the tail of the struct to resolve (to ()), but the struct is only sized if we can resolve that tail (since we, unfortunately, don't currently resolve the item bounds on the type).

I'm not sure if this is worth fixing with the current trait solver, since it can be worked around as you said above by adding a dummy struct tail that you know is sized, like _tail: ().

For what it's worth, it works in the new trait solver (-Ztrait-solver=next) since that's a bit more forgiving about paths that end up in ambiguity.

[matthieu-m]

@compiler-errors I certainly have no problem waiting for the new trait solver, though I fear other people hitting this roadblock may be similarly confused.

Do you think it would be worth investing a bit on the diagnostic side in the meantime? If the diagnostics could suggest the work-around, it would make it much more reasonable to just keep it as is for now.

Of course, this all depends how soon the new trait solver is slated to come through. If it'll be there in a release or two, it's pointless to invest in the current situation. If it'll be another year before it's there, I think it'd be worthwhile.

[jyn514]

I've heard from @BoxyUwU that it's at least 6 months away and probably closer to a year and a half.

[jyn514]

@compiler-errors @BoxyUwU is there a label for issues that are fixed with -Ztrait-solver=next? if not, I think it makes sense to add one.