Thread overview
std.container: SList linearRemove confusion
Oct 07, 2010
Johannes Pfau
Oct 07, 2010
Johannes Pfau
October 07, 2010
Hi,
I'm currently trying to replace the array in my signal implementation
with the SList from std.container. I need to remove elements from the
list, but I can't seem to get it right.
According to the documentation, I expect linearRemove to remove the
contents of the passed range, but linearRemove always removes all
elements in the range and _after the range_ .
For linearRemove(Range r) it seems to be expected? At least the code
obviously behaves like that:
http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1251
-------------------------------------------------------------------------
auto n = findNode(_root, r._head); //find beginning of range in list
n._next = null;               //ignore all elements after that element
return Range(null);
-------------------------------------------------------------------------
Is this really the expected behavior for linearRemove?

The linearRemove(Take!Range r) version doesn't work either, but this
time I'm sure it's a bug: it seems to happen if I use a Take!Range with
the first element being the SList root node. looking at the code:
http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1270
-------------------------------------------------------------------------
Range linearRemove(Take!Range r)
{
    auto orig = r.original;
    // We have something to remove here
    if (orig._head == _root)
    {
        // remove straight from the head of the list
        for (; !orig.empty; orig.popFront())          <----- _why
orig.empty and orig.popFront? should be r.empty and r.popFront_
        {
            removeFront();
        }
        return this[];
    }
    [...]
}
-------------------------------------------------------------------------
Testcase
-------------------------------------------------------------------------
import std.container;
import std.range;
import std.algorithm;

void main()
{
    auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    auto r = s[];
    auto r1 = take(r, 4);
    assert(equal(r1, [1, 2, 3, 4]));
    auto r2 = s.linearRemove(r1);
    assert(s == SList!int()); //passes - should fail!
    assert(s == SList!int(5, 6, 7, 8, 9, 10)); //fails
}
-------------------------------------------------------------------------

I guess I should file a bug report, but this really is a showstopper for me. Is there any way to get this fixed faster? The fix is really trivial.

-- 
Johannes Pfau
October 07, 2010
On Thu, 07 Oct 2010 12:44:48 -0400, Johannes Pfau <spam@example.com> wrote:

> Hi,
> I'm currently trying to replace the array in my signal implementation
> with the SList from std.container. I need to remove elements from the
> list, but I can't seem to get it right.
> According to the documentation, I expect linearRemove to remove the
> contents of the passed range, but linearRemove always removes all
> elements in the range and _after the range_ .
> For linearRemove(Range r) it seems to be expected? At least the code
> obviously behaves like that:
> http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1251
> -------------------------------------------------------------------------
> auto n = findNode(_root, r._head); //find beginning of range in list
> n._next = null;               //ignore all elements after that element
> return Range(null);
> -------------------------------------------------------------------------
> Is this really the expected behavior for linearRemove?

Yes, an SList range is terminated by a null pointer, so there is no limit to how far it will iterate.

Try to construct an SList range (without using Take) that doesn't iterate the rest of the list.

> The linearRemove(Take!Range r) version doesn't work either, but this
> time I'm sure it's a bug: it seems to happen if I use a Take!Range with
> the first element being the SList root node. looking at the code:
> http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1270
> -------------------------------------------------------------------------
> Range linearRemove(Take!Range r)
> {
>     auto orig = r.original;
>     // We have something to remove here
>     if (orig._head == _root)
>     {
>         // remove straight from the head of the list
>         for (; !orig.empty; orig.popFront())          <----- _why
> orig.empty and orig.popFront? should be r.empty and r.popFront_
>         {
>             removeFront();
>         }
>         return this[];
>     }
>     [...]
> }

Yes, I think you are right.

>
> I guess I should file a bug report, but this really is a showstopper for
> me. Is there any way to get this fixed faster? The fix is really trivial.

Yes, fix it in your local copy :)  It is a seldom used construct, so there should be no real compiled code in Phobos that will be affected.  Just change the source and everything will be good.

But do also file a bug please.

-Steve
October 07, 2010
On 07.10.2010 19:09, Steven Schveighoffer wrote:
> On Thu, 07 Oct 2010 12:44:48 -0400, Johannes Pfau <spam@example.com> wrote:
>> Is this really the expected behavior for linearRemove?
> 
> Yes, an SList range is terminated by a null pointer, so there is no limit to how far it will iterate.
> 
> Try to construct an SList range (without using Take) that doesn't
> iterate the rest of the list.

OK, that makes sense.
> 
> Yes, fix it in your local copy :)  It is a seldom used construct, so there should be no real compiled code in Phobos that will be affected. Just change the source and everything will be good.

OK I've done that. works great now.
> But do also file a bug please.

Done: http://d.puremagic.com/issues/show_bug.cgi?id=5011
> -Steve

Thanks for your help!
-- 
Johannes Pfau