D-Programming-Language/phobos — pull request #953 by monarchdodra (2012-11-16 14:45:06+00:00)
Title: DList: Classic semantics

This pull request mostly undoes any documentation I had done in:
https://github.com/D-Programming-Language/phobos/pull/910

These semantics were weird as hell. I still have no idea if they were even intended. It is better to steer right away from that sooner rather than later.

Now, DList behaves as *everyone* would expect: reference semantics. Also, lazy initialization. This breaks virtually nothing. Anything it *does* break was (IMO) unsound.

Here, the changes were purposefully kept minimal, but there is still room for a ton of improvements. (which I plan to get to).

----
The implementation uses a derivative of the circular buffer approach: circular buffer is not possible in D, because pointers to self are illegal. Instead, it uses two sentinel nodes. This approach has 3 advantages.
* Avoids creating a "payload" that, itself, just contains a second indirection to the nodes.
* The implementations are now trivially simple:
`insertBeforeNode(value)`: 1 line
`insertBeforeNode(Range)`: 8 lines (was about 30)
`remove(Range)`: 5 lines (was 40)
* When we will add splice (which I plan to do), a range can be excised from a list, without actually having to access the list's internals. This means the ranges will not actually need to know who owned them.

Overall, this new approach gives the implementation a (much needed) breath of fresh air in terms of complexity

----
Things that changed:
* All forms of `stableRemoveX` were marked as deprecated, since they weren't actually stable. If it "seemed" like it was stable, it's because the range was corrupted...
* What *was* added though is that any range that is "wholly " removed is still valid, but just not "owned" by the list anymore...
* A more assertive approach to range invalidation, to detect logic errors. Faster.

Things that have been added
* Comparison and assignement to null. This breaks nothing, since it is new semantics.

Bit more minor `~=` bugfix.