type S = Option<Box<S>>; should compile

[lihz6]

It seems a compiler bug to me. I tried this code:

type S = Option<Box<S>>;

I expected it could compile, but instead:

lihz:linkedlist lihzhang$ cargo build
   Compiling linkedlist v0.1.0 (/Users/lihzhang/Documents/com.github/linkedlist)
error[E0391]: cycle detected when processing `S`
 --> src/lib.rs:1:21
  |
1 | type S = Option<Box<S>>;
  |                     ^
  |
  = note: ...which again requires processing `S`, completing the cycle
note: cycle used when collecting item types in top-level module
 --> src/lib.rs:1:1
  |
1 | type S = Option<Box<S>>;
  | ^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0391`.
error: Could not compile `linkedlist`.

To learn more, run the command again with --verbose.

However, the equivalent code as following compiles fine:

enum S {
    T(Option<Box<S>>),
}

[hellow554]

Why do you think it should be possible? What is the difference to type S = S? This is a cycle, do you agree? So, type S = Option<S> is a cycle as well? And the same goes for type S = Option<Box<S>>. All of these three examples are cycles.

Why does enum S { T(Box<S>) } work? Because it is an indirection. Box isn't the same size as S, but it is "a pointer" to S. If you go to the playground and try it yourself, the compiler will tell you what's wrong.

error[E0072]: recursive type `S` has infinite size
 --> src/lib.rs:1:1
  |
1 | enum S {
  | ^^^^^^ recursive type has infinite size
2 |     T(S)
  |       - recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `S` representable

[Centril]

This is working as intended; the issue is not indirection however but rather that type aliases are aliases and so when the compiler is working out what S is it has to compute the type expression Option<Box<S>> which requires working out what S is so you have to compute Option<Box<S>>, and so we have a cycle.

This is different from enums and structs in that these introduce essentially a fixpoint:

struct S = μ S. Option<Box<S>>;

which works fine because S in Option<Box<S>> refers to the bound variable S and so we have no cycles.

See https://en.wikipedia.org/wiki/Recursive_data_type for more information.

---

We should perhaps recognize this case and say something about type aliases not behaving like data types suggesting an enum or struct instead. cc @oli-obk @estebank

[estebank]

Current output:

error[[E0391]](https://doc.rust-lang.org/stable/error_codes/E0391.html): cycle detected when expanding type alias `S`
 --> src/lib.rs:1:21
  |
1 | type S = Option<Box<S>>;
  |                     ^
  |
  = note: ...which immediately requires expanding type alias `S` again
  = note: type aliases cannot be recursive
  = help: consider using a struct, enum, or union instead to break the cycle
  = help: see <https://doc.rust-lang.org/reference/types.html#recursive-types> for more information
note: cycle used when collecting item types in top-level module
 --> src/lib.rs:1:1
  |
1 | type S = Option<Box<S>>;
  | ^^^^^^^^^^^^^^^^^^^^^^^^