[Issue 19823] std.algorithm.iteration.filter's popFront doesn't always pop the first element like it's supposed to

[d-bugmail at puremagic.com]

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

shove <shove at 163.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |shove at 163.com

--- Comment #4 from shove <shove at 163.com> ---
(In reply to Jonathan M Davis from comment #3)
> dropOne isn't actually the problem at all. Rather, it looks like the problem
> is with either `Filter`'s `popFront` or with the code that dmd is
> generating. This reduced test case has the same problem:
> 
>     void main()
>     {
>         import std.algorithm.comparison : equal;
>         import std.algorithm.iteration : filter;
> 
>         auto arr = [1, 2, 3, 4];
> 
>         auto result = arr.filter!(a => a != 1)();
>         assert(result.save.equal([2, 3, 4]));
> 
>         result.popFront();
>         assert(result.equal([3, 4]));
>     }
> 
> 
> For some reason, `popFront` is not doing anything with this particular
> example, and the second assertion fails. Rather if the result is printed
> after `popFront`, it's equivalent to [2, 3, 4], and changing the second
> assertion to
> 
>     assert(result.equal([2, 3, 4]));
> 
> makes it pass. So, clearly, `popFront` is doing nothing for some reason.

You're right, drop, dropOne... have no design or coding problems. The problem
is struct FilterResult of std.algorithm.iteration.d:


...
private struct FilterResult(alias pred, Range)
{
    alias R = Unqual!Range;
    R _input;
    private bool _primed;

    private void prime()
    {
        if (_primed) return;
        while (!_input.empty && !pred(_input.front))
        {
            _input.popFront();
        }
        _primed = true;
    }

    this(R r)
    {
        _input = r;
    }

    private this(R r, bool primed)
    {
        _input = r;
        _primed = primed;
    }

    auto opSlice() { return this; }

    static if (isInfinite!Range)
    {
        enum bool empty = false;
    }
    else
    {
        @property bool empty() { prime; return _input.empty; }
    }

    //void popFront()
    //{
    //    do
    //    {
    //        _input.popFront();
    //    } while (!_input.empty && !pred(_input.front));
    //    _primed = true;
    //}

    // Modify it to read as follows:
    void popFront()
    {
        prime;
        do
        {
            _input.popFront();
        } while (!_input.empty && !pred(_input.front));
    }

    @property auto ref front()
    {
        prime;
        assert(!empty, "Attempting to fetch the front of an empty filter.");
        return _input.front;
    }

    static if (isForwardRange!R)
    {
        @property auto save()
        {
            return typeof(this)(_input.save, _primed);
        }
    }
}
...

In this way, dropOne can work properly. But the scope of influence here is too
wide, there are too many APIs, classes and templates in Phobos that use filter.
If it's not necessary, it's better not to change it.

I'd like to hear your further advice. Thank you!

--