[Issue 13279] [dmd-2.066-rc2] Invalidated state of DList with linearRemove

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13279

monarchdodra at gmail.com changed:

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

--- Comment #3 from monarchdodra at gmail.com ---
(In reply to Kenji Hara from comment #2)
> The assert was introduced in:
> https://github.com/D-Programming-Language/phobos/pull/1954
> 
> However, as far as I see, the code modifies dlist during its iteration. By
> the modification, original range would be invalid and the assertion detects
> "invalid state".

Aye. This triggered a new check that verifies the integrity of the range more
thoroughly than before, rather than just letting dangerous state slide.

The issue is not just that the code modifies the range it is iterating on, but
more specifically, removing the very node it is currently on.

When the node gets removed, it is now also unlinked, so when the foreach calls
"pop" on the removed node, it finds nothing.

While we *could* have this keep working by simply letting removed nodes still
reference their neighbors:
1. We have shown this produces strange iteration behavior sometimes.
2. It makes the assumption that nodes are GC-allocated, and that the unlinked
node isn't destroyed.

But yeah, overall, doing a "foreach" over a container while removing certain of
its elements is a *terrible* idea. C++ books have entire tutorial chapters on
how to do this, and it applies here perfectly well to D.

Not to mention, that code has linear complexity. In any case, something like
this should be more correct (not tested):

//----
DList.Range removeOne(T)(ref DList!T list, T elem)
{
   auto toRemove = list[].find(elem).take(1);
   return list.linearRemove(toRemove);
}

void main()
{
    DList!int list;
    list.insert(1);
    list.insert(2);

    for (auto r = list[] ; !r.empty ; )
    {
        if(r.front == 1)
            r = removeOne(list, elem);
        else
            r.popFront();
    }
}
//----

Or better yet:
//----
DList!T.Range removeOne(T)(ref DList!T list, DList!T.R toRemove )
{
   return list.linearRemove(toRemove.take(1));
}

void main()
{
    DList!int list;
    list.insert(1);
    list.insert(2);

    for (auto r = list[] ; !r.empty ; )
    {
        if(r.front == 1)
            r = removeOne(list, r);
        else
            r.popFront();
    }
}
//----

OK to close this as Invalid?

--