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".
Comment #3 by monarchdodra — 2014-08-11T11:44:39Z
(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?
Comment #4 by k.hara.pg — 2014-08-11T12:09:48Z
Thank you for good replying, @monarchdodra.
> OK to close this as Invalid?
I'll do it.
Comment #5 by NCrashed — 2014-08-11T12:51:47Z
Thank you a lot, @monarchdodra! I was part of legacy code and the main idea was "don't touch while it works!". Modifying collection while iterating over is really horrible idea.
Thus my list does much more deletion operations than addition ones, I simply fills new list with remaining elements and swaps two lists at the end of iteration.
Invalid.