D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 12566 - Give DList true reference semantics
Summary: Give DList true reference semantics
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P1 enhancement
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-04-12 21:25 UTC by monarchdodra
Modified: 2014-05-31 10:51 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description monarchdodra 2014-04-12 21:25:08 UTC
DList currently uses some weird semantics. It is neither value nor reference semantics. The behavior is documented, but the documentation is the result of what I think was a buggy behavior to begin with.

Issues with the current behavior include:
1. It's surprising. I think *everyone* simply expects reference semantics (or wants value semantics). But they know what to *expect*. Currently, they don't get what they expect:
//----
    auto a = DList!size_t(1, 2, 3);
    auto b = a; //Deep copy? Shallow copy?
    b.removeBack();
    assert(!equal(a[], b[])); //different
    assert(!(a is b)); //different
    assert(equal(a[], [1, 2, 3])); //a was unchanged.

    b.insertBack(3); //Put 3 back in.
    writeln(a[]); //prints [1, 2, 3, 3]
    assert(equal(a[], [1, 2, 3])); //fails. a was changed.
//----
Unless you actually *wrote* DList, I don't think you could really understand *why* this is happening.

2. Data is *never* released: No matter how many time you call "removeBack" or "removeFront", the nodes are never actually excised from the chain. This can lead to a "leak" in the sense that dead data is actually still referenced by live pointers. This program will crawl to a stall and halt:
    auto d = DList!size_t(1, 1);
    foreach (k; 0 .. size_t.max - 1)
    {
        if (k%100_000 == 0) writeln(k);
        d.removeBack();
        d.insertBack(k);
    }

3. It's inefficient and buggy. *trivial* use cases are *still* failing:
//----
  auto dl2 = DList!int([2,7]);
  dl2.removeFront();
  assert(dl2[].walkLength == 1);
  dl2.removeBack();
  assert(dl2.empty, "not empty?!"); //Fails
//----