Previous Entry Share Next Entry
Migrating to Ranges
anime
he_the_great

This post is more of an advanced topic for D programmers. If you're coming from another language and want to get started with Ranges then read up on them in "Programming in D" or TDPL and the Docs. This is looking like it will need to be two parts.

If you're like me, you'll end up writing a function like this:

dlang
void foo(Range)(Range r) if(isInputRange!Range) { //...

Usually I'm working with the specific data type so throwing on a good ElementType check would be a good idea. Generally this function ends up being called something like this:

dlang
    int[] data; // ...
    foo(data);

If you're familiar with D then one of things you'll know is that I've just given my function the most powerful range in the language. Just look at the list of capabilities an array gives you.

dlang
import std.range;

void main(string[] args) {
    static assert(isInputRange!(int[]));
    static assert(isForwardRange!(int[]));
    static assert(isBidirectionalRange!(int[]));
    static assert(isRandomAccessRange!(int[]));
    static assert(hasMobileElements!(int[]));
    static assert(hasSwappableElements!(int[]));
    static assert(hasAssignableElements!(int[]));
    static assert(hasLvalueElements!(int[]));
    static assert(hasLength!(int[]));
    static assert(hasSlicing!(int[]));
}

These fancy little things make for some unfortunate difficulties. Because a template constraint will reject types which don't meet the condition, but no further checks are done inside the body of the function (similar to Concepts-Lite C++ is adopting). This means foo() could perform any and all array operations and all that testing I'm doing isn't giving me any benefit since I'm not restricting my type to a bear minimum.

When dealing with input/forward ranges, writing a simple wrapper isn't very hard, there's probably a number of them in Phobos already. Other ranges I'd say aren't nearly as common. Lets take a look at what wrapping these types is like.

std.range provides a number of interfaces for the different Range types, lets completely ignore those. The interfaces in std.range have more methods than needed to implement the basic types. So I'll define my own.

dlang
import std.range;

interface InputRange(E) {
    @property E front();
    void popFront();
    @property bool empty();
}
interface ForwardRange(E) : InputRange!E {
    @property ForwardRange!E save();
}
interface BidirectionalRange(E) : ForwardRange!(E) {
    override @property BidirectionalRange!E save();
    @property E back();
    void popBack();
}
interface HasLength(E) : InputRange!(E) {
    @property size_t length();
}
interface RandomAccess(E) : BidirectionalRange!(E), HasLength!(E) {
    override @property RandomAccess!E save();
    E opIndex(size_t);
    override @property size_t length();
    alias length opDollar;
}
interface HasSlicing(E) : ForwardRange!(E), HasLength!(E) {
    HasSlicing!E opSlice(size_tsize_t);
}

Next up I need a range which can play the role of an array almost as good as an array.

dlang
class FullPower(E) : RandomAccess!E, HasSlicing!E {
    E[] r;

    @property bool empty() {
        return r.empty;
    }

    @property E front() {
        return r.front;
    }

    @property FullPower save() {
        auto a = new FullPower();
        a.r = r;
        return a;
    }

    @property size_t length() {
        return r.length;
    }

    void popFront() {
        r.popFront();
    }

    FullPower opSlice(size_t lhs, size_t rhs) {
        auto a = new FullPower();
        a.r = r[lhs..rhs];
        return a;
    }

    @property E back() {
        return r.back;
    }

    void popBack() {
        r.back;
    }

    E opIndex(size_t i) {
        return r[i];
    }

    size_t opDollar() {
        return r.length;
    }
}

Not the must fun to write, but as awesome as meta programming is, this was a faster approach. It has some problems that I'll get to.

FullPower inherits from both RandomAccess and HasSlicing. This is required due to the requiremnts of these types. A ForwardRange and a slice return the same type. RandomAccessRange covers BidirectionalRange and ForwardRange for this requirement.

Next is to do some testing. When we have an InputRange, we don't want to to work as a ForwardRange/RandomAccessRange/etc. Each range type should fulfil its roles and not those of others. I'll go over each verify function individually.

dlang
void main(string[] args) {
    auto r = new FullPower!int();
    verifyAll(r);
    import std.typecons;
    auto r1 = wrap!(InputRange!int)(r);
    verifyInputRange(r1);
    auto r2 = wrap!(ForwardRange!int)(r);
    verifyForwardRange(r2);
    auto r3 = wrap!(BidirectionalRange!int)(r);
    verifyBidirectionalRange(r3);
    auto r4 = wrap!(HasLength!int)(r);
    verifyHasLengthRange(r4);
    auto r5 = wrap!(HasSlicing!int)(r);
    verifyHasSlicingRange(r5);
}

The 2.064 compiler will include a new function for "wrapping" a type. The basic idea is that when a type fulfills the requirements of an interface, the wrap function will provide a type which of that interface type. Either creating a new type with the proper inheritance, or casting. Nothing to special here, these end up just casting to a base type (didn't get to take advantage of the structural typing like I'd hoped).

dlang
auto verifyAll(R)(R t) {
     static assert(isInputRange!(R));
     static assert(isForwardRange!(R));
     static assert(isBidirectionalRange!(R));
     static assert(isRandomAccessRange!(R));
     static assert(hasMobileElements!(R));
     static assert(hasLength!(R));
     static assert(hasSlicing!(R));
     //static assert(hasLvalueElements!(R));
     //static assert(hasSwappableElements!(R));
     //static assert(hasAssignableElements!(R));
}

To start off we want to verify that everything arrays can do, FullPower can do better. Unfortunately it fails to fulfill the requirement for hasLvalueElements (funny thing, swappable and assignable come from having LvalueElements...). This was because a ForwardRange doesn't have Lvalue elements causing a conflict for the declaration of front(). Thus these checks are out, and we can't use this type if they're needed.

dlang
auto verifyInputRange(R)(R t) {
     static assert(isInputRange!(R));

     static assert(!isForwardRange!(R));
     static assert(!isBidirectionalRange!(R));
     static assert(!isRandomAccessRange!(R));
     static assert(!hasLength!(R));
     static assert(!hasSlicing!(R));
     //static assert(!hasMobileElements!(R));
}

An InputRange has only has three functions, this leads to a requirement that it doesn't have any other functions. Apparently it has mobile elements, something in std.range is probably providing the move primitives for the range, but I didn't check why this test fails.

dlang
auto verifyForwardRange(R)(R t) {
     static assert(isInputRange!(R));
     static assert(isForwardRange!(R));

     static assert(!isBidirectionalRange!(R));
     static assert(!isRandomAccessRange!(R));
     static assert(!hasLength!(R));
     static assert(!hasSlicing!(R));
}

The Forward Range fulfills its end of the bargain (minus those checks already failing.

dlang
auto verifyBidirectionalRange(R)(R t) {
     static assert(isInputRange!(R));
     static assert(isForwardRange!(R));
     static assert(isBidirectionalRange!(R));

     static assert(!isRandomAccessRange!(R));
     static assert(!hasLength!(R));
     static assert(!hasSlicing!(R));
}

A Bidirectional Range is also a Forward Range, but it doesn't need a length or slicing.

dlang
auto verifyHasLengthRange(R)(R t) {
     static assert(isInputRange!(R));
     static assert(hasLength!(R));

     static assert(!isForwardRange!(R));
     static assert(!isBidirectionalRange!(R));
     static assert(!isRandomAccessRange!(R));
     static assert(!hasSlicing!(R));
}

hasLength doesn't require any range primitives, but since this is about ranges I'm checking that it is only an InputRange. Otherwise another interface will need to be created to handle ForwardRanges with length and so on.

dlang
auto verifyHasSlicingRange(R)(R t) {
     static assert(isInputRange!(R));
     //static assert(isForwardRange!(R));
     static assert(hasLength!(R));
     //static assert(hasSlicing!(R));

     static assert(!isBidirectionalRange!(R));
     static assert(!isRandomAccessRange!(R));
}

Slicing requires many things to be true. And unfortunately all the important parts fail. At this point I don't know why.

Conclusion

Wrapping ranges in the general case is not straight forward. This approach gets very close but has one major drawback aside from the failures in the verification functions.

A function accepting a range may desire an assortment of properties. For example it may be desired to take a Bidirectional Range which also provides a length. This approach would require a new interface to accomplish that combination (and other similar combinations).

This specific approach is fairly close, but may just be too close for its own good. Since it fails in some seemingly minor edge cases it can lead to trouble when you think those cases aren't being used.


?

Log in