www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8905] New: DList.Range: Internal error, inconsistent state

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8905

           Summary: DList.Range: Internal error, inconsistent state
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: ellery-newcomer utulsa.edu



16:00:24 PDT ---
The code:

import std.container;
import std.algorithm;
import std.stdio;

void main() {
    DList!int list = make!(DList!int)(1,2,3,4);
    auto range = list[];
    list.stableRemoveBack();
    list.stableInsertBack(7);
    writeln(list[]);
    writeln(range);
}

The fireworks:

core.exception.AssertError /usr/include/dmd-d/std/container.d(1573):
DList.Range: Internal error, inconsistent state

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 28 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8905


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra gmail.com





 The code:
 
 import std.container;
 import std.algorithm;
 import std.stdio;
 
 void main() {
     DList!int list = make!(DList!int)(1,2,3,4);
     auto range = list[];
     list.stableRemoveBack();
     list.stableInsertBack(7);
     writeln(list[]);
     writeln(range);
 }
 
 The fireworks:
 
 core.exception.AssertError /usr/include/dmd-d/std/container.d(1573):
 DList.Range: Internal error, inconsistent state


I inserted that assert in the code.

I think the code is invalid, that is not how "stable" is meant to be used. It
just means that the insert will not modify the order of the *other* elements in
the list.

The documentation states otherwise, but in this case, I think it is the
documentation that is wrong.

When you first call "stableRemoveBack", the range becomes invalidated. That is
what the assert is telling you.

Case in point, in DMD 2.060, without the assert, look at what happens when you
do this:

//----
import std.range;
import std.container;
import std.algorithm;
import std.stdio;

void main() {
   DList!int list = make!(DList!int)(1,2,3,4);
   auto range = list[];
   list.stableRemoveBack();
   list.stableInsertBack(7);
   writeln(range);
   writeln(range.retro());
}
//----
[1, 2, 3, 7]
[4, 3, 2, 1]
//----

Notice the '7' when iterating forward, but the 4 when iterating backwards: The
tip of the range's front is not the tail: The range got "cut" on the call to
"stableRemoveBack" and that is why the range is not happy.

I don't think there is *ANY* way to ever make this work, and I'd suggest either
of:
*Re-writing the documentation.
*Removing the function if the documentation is correct.

--------
EDIT: ACTUALLY, one of the first things I'll propose is to reword the assert:
It makes it sound like an implementation error, when it is actually a user
error. How about: "Logic Error: The DList.range chain has been cut."

I know it might not make that much sense, but it is what is happening, and the
message *is* better. BTW, this thread might make sense of what is happening:

http://forum.dlang.org/thread/gjhclwsuqyhrimdeoaec forum.dlang.org

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 29 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8905




17:21:16 PDT ---


 
 I think the code is invalid, that is not how "stable" is meant to be used. It
 just means that the insert will not modify the order of the *other* elements in
 the list.
 
 The documentation states otherwise, but in this case, I think it is the
 documentation that is wrong.
 
 When you first call "stableRemoveBack", the range becomes invalidated. That is
 what the assert is telling you.


And as you noted above, this violates the current semantics of
stableRemoveBack.

I am wondering if stableRemoveBack is intended for immutable data structures or
something. It certainly doesn't seem implementable for anything in
std.container.


 I don't think there is *ANY* way to ever make this work, and I'd suggest either
 of:
 *Re-writing the documentation.
 *Removing the function if the documentation is correct.
 


I don't think so, either, and I agree with the recommendation.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 29 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8905








 I don't think there is *ANY* way to ever make this work, and I'd suggest either
 of:
 *Re-writing the documentation.
 *Removing the function if the documentation is correct.
 


 
 I don't think so, either, and I agree with the recommendation.


Wait, thinking about it, technically, it could actually work, if the original
range then produced :"[1, 2, 3, 4, 7]".

The thing is that such semantics are un-natural. It would correspond to my
notion of "a Dlist is just a view into a chain of nodes". The problem is that I
*still* don't know if that would be the intended behavior...

BTW, here is a fun bug related to said "view of chain" behavior:

//----
import std.container;
import std.stdio;

void main()
{
    auto list = make!(DList!int)(1,2,3,4,5);
    auto r = list[];
    list.stableRemoveBack();
    list.stableRemoveFront();
    list.stableRemove(list[]);
    writeln("My empty list: ", list[]);
    writeln("My original slice: ", r);
}
//----
My empty list: [2, 3, 4]
My original slice: [1, 5]
//----

Fixing this is doable, but it makes the implementation *very* complicated
(standard dlist assumptions don't hold anymore). Not to mention it allows for
some *very* weird semantics. Not worth it, IMO.

I'd have suggested that DList be changed to have a simpler reference semantic
(all Dlist share a common payload), with explicit destruction of removed nodes
(and invalidation of ranges that index them). EG: The DList we all know and
love...

But seeing how much feedback I've received, I'm not sure I feel like pushing
for this one >:(

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8905






 [SNIP]


Actually, I remember that I had corrected all these bugs, but had never gotten
around to committing them... I'll do it then.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 30 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8905








 [SNIP]


 
 Actually, I remember that I had corrected all these bugs, but had never gotten
 around to committing them... I'll do it then.


https://github.com/D-Programming-Language/phobos/pull/910

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 01 2012