LinkedList implementation violates aliasing rules

[Amanieu]

The nodes in LinkedList look like this:

struct Node<T> {
    next: Option<Box<Node<T>>>,
    prev: Option<Shared<Node<T>>>,
    value: T,
}

Box uses Unique, which requires that it "the referent of the pointer should not be modified without a unique path to the Unique reference". This effectively means that Unique doesn't allow aliases, but this rule violated by the prev pointer which point to the same node as a Unique.

While Rust currently doesn't give noalias semantics to Unique, this is planned in the future and will silently break LinkedList.

[eefriedman]

The declaration of Box in liballoc is basically informational at the moment; we don't actually use it for anything. So actually the problem is worse than it looks: we already mark Box<T> pointers noalias (but only if you pass one directly to a function... so it's sort of a similar situation to Ref<T> where it would break if we used noalias markings more aggressively).

It's not completely clear whether this particular use of unsafe will be considered undefined behavior under the new memory model (see rust-lang/rfcs#1643), but it's likely it will.

[nikomatsakis]

I agree with @eefriedman that this usage is likely to turn out to be a problem -- because it uses Box. It's not obvious to me whether Unique ought to be "meaningful" to the Rust compiler in any sense. In any case, I believe the reason that Unique has that wording about uniqueness is because it implements Send, which is not a problem here, so perhaps it is the wording that is wrong (it's one way to make things thread-safe, but not the only way).

[alexcrichton]

triage: P-medium

Not actively causing breakage today, but we're likely to want to revisit this soon