D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 3877 - std.range.chain do not manage infinite ranges correctly
Summary: std.range.chain do not manage infinite ranges correctly
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P2 minor
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-03-04 06:51 UTC by Philippe Sigaud
Modified: 2015-06-09 01:27 UTC (History)
2 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description Philippe Sigaud 2010-03-04 06:51:21 UTC
std.range.chain opIndex and opIndexAssign do not work for infinite ranges:

---
import std.range;

void main() {
    auto c = chain([0,1,2][], cycle([4,5,6][]), [7,8,9][]); // infinite range inside
    auto c7 = c[7]; // Error, no property .length for cycle([4,5,6][])
}

Here is a fix for this:
(no improvement to opSlice there. It should be possible: verify if all ranges before the first infinite have a length and slice on them + the infinite range.)
---
struct ChainImpl(R...)
{
private:
    alias CommonType!(staticMap!(.ElementType, R)) RvalueElementType;
    template sameET(A)
    {
        enum sameET = is(.ElementType!(A) == RvalueElementType);
    }
    enum bool allSameType = allSatisfy!(sameET, R);

public:
    Tuple!(R) _input;
    // This doesn't work yet
    static if (allSameType)
        alias ref RvalueElementType ElementType;
    else
        alias RvalueElementType ElementType;

    this(R input)
    {
        foreach (i, v; input)
        {
            _input.field[i] = v;
        }
    }

    bool empty()
    {
        foreach (i, Unused; R)
        {
            if (!_input.field[i].empty) return false;
        }
        return true;
    }

    void popFront()
    {
        foreach (i, Unused; R)
        {
            if (_input.field[i].empty) continue;
            _input.field[i].popFront;
            return;
        }
    }

    //@@@BUG 2597@@@
    //auto front()
    //@@@AWKWARD!!!@@@
    mixin(
        (allSameType ? "ref " : "")~
        q{ElementType front()
            {
                foreach (i, Unused; R)
                {
                    if (_input.field[i].empty) continue;
                    return _input.field[i].front;
                }
                assert(false);
            }
        });

    static if (allSatisfy!(isBidirectionalRange, R))
    {
        mixin(
            (allSameType ? "ref " : "")~
            q{ElementType back()
                {
                    foreach_reverse (i, Unused; R)
                    {
                        if (_input.field[i].empty) continue;
                        return _input.field[i].back;
                    }
                    assert(false);
                }
            });

        void popBack()
        {
            foreach_reverse (i, Unused; R)
            {
                if (_input.field[i].empty) continue;
                _input.field[i].popBack;
                return;
            }
        }
    }

    static if (allSatisfy!(hasLength, R))
        size_t length()
        {
            size_t result;
            foreach (i, Unused; R)
            {
                result += _input.field[i].length;
            }
            return result;
        }

    static if (allSatisfy!(isRandomAccessRange, R))
    {
        mixin(
            (allSameType ? "ref " : "")~
            q{ElementType opIndex(uint index)
                {
                    foreach (i, Type; R)
                    {
                        static if (hasLength!Type) {
                            immutable length = _input.field[i].length;
                            if (index < length) return _input.field[i][index];
                            index -= length;
                        }
                        else {
                            static if (isInfinite!Type) {
                                return _input.field[i][index];
                            }
                        }
                    }
                    assert(false);
                }
            });

        static if (allSameType && allSatisfy!(hasAssignableElements, R)) void opIndexAssign(ElementType v, uint index)
        {
            foreach (i, Type; R)
            {
                static if (hasLength!Type) {
                    immutable length = _input.field[i].length;
                    if (index < length)
                    {
                        _input.field[i][index] = v;
                        return;
                    }
                    index -= length;
                }
                else {
                    static if (isInfinite!Type) {
                        _input.field[i][index] = v;
                        return;
                    }
                }
            }
            assert(false);
        }
    }

    static if (allSatisfy!(hasLength, R) && allSatisfy!(hasSlicing, R))
        ChainImpl opSlice(size_t begin, size_t end)
        {
            auto result = this;
            foreach (i, Unused; R)
            {
                immutable len = result._input.field[i].length;
                if (len < begin)
                {
                    result._input.field[i] = result._input.field[i]
                        [len .. len];
                    begin -= len;
                }
                else
                {
                    result._input.field[i] = result._input.field[i]
                        [begin .. len];
                    break;
                }
            }
            auto cut = length;
            cut = cut <= end ? 0 : cut - end;
            foreach_reverse (i, Unused; R)
            {
                immutable len = result._input.field[i].length;
                if (cut > len)
                {
                    result._input.field[i] = result._input.field[i]
                        [0 .. 0];
                    cut -= len;
                }
                else
                {
                    result._input.field[i] = result._input.field[i]
                        [0 .. len - cut];
                    break;
                }
            }
            return result;
        }
}
Comment 1 Trass3r 2010-07-29 17:12:19 UTC
Note: It's better to post a diff. Makes it easier to figure out what the actual fix is.
Comment 2 Philippe Sigaud 2010-07-30 02:24:29 UTC
(In reply to comment #1)
> Note: It's better to post a diff. Makes it easier to figure out what the actual
> fix is.

Well, has I said in the text, opIndex and opIndexAssign do not work. The proposed change is in the opIndex and opIndexAssign code, the static if (hasLength) and static if (isInfinite) part.

I don't have access to a diff tool right now and wasn't using the Phobos svn repository in march.


Philippe
Comment 3 David Simcha 2010-08-16 20:03:50 UTC
Fixed SVN.