Range predicates are not restrictive enough to justify assumptions made in Phobos code

[dlangBugzillaToGithub]

timon.gehr reported this on 2013-03-14T15:22:16Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=9724

CC List

• hsteoh
• monarchdodra

Description

DMD/Phobos 2.062:

Eg. the following breaks most of std.range, and most of std.algorithm could likely be broken too, but I am too lazy to investigate.

import std.range, std.algorithm;

struct TrollFace{
    @property string front()const{ return "troll"; }
    @property string back()const{ return "face"; }
    @property bool empty()const{ return true; }
    void popFront()const{ }
    void popBack()const{ }
    @property inout(TrollFace) save()inout{ return this; }
    auto opIndex(size_t index){ return front; }
    @property size_t length()inout{ return 0; }
    int* x;
}
struct TrollierFace{
    TrollFace face;
    alias face this;
    @disable this(this);
    @property inout(TrollierFace) save()inout{ return inout(TrollierFace)(face); }
}

void main(){
    immutable TrollFace a,b,c;
    a.retro();
    a.stride(2);
    chain(a,b,c);
    roundRobin(a,b,c);
    a.radial();
    a.radial(0);
    a.take(2);
    (immutable(TrollierFace)()).takeExactly(2);
    (immutable(TrollierFace)()).takeOne();
    (immutable(TrollierFace)()).takeNone();
    (immutable(TrollierFace)()).drop(2);
    (immutable(TrollierFace)()).dropExactly(0);
    (immutable(TrollierFace)()).dropOne();
    (immutable(TrollierFace)()).repeat();
    a.cycle();
    a.zip(b);
    lockstep((immutable(TrollierFace)()),b);
    a.frontTransversal();
    a.transversal(0);
    a.indexed([0]);
    a.chunks(5);
    a.filter!(a=>true);
    a.map!(a=>a);
    // ... (and so on)
}

[dlangBugzillaToGithub]

monarchdodra commented on 2013-03-15T04:16:33Z

Predicates? Did you mean "traits" or "restrictions" ?

Either way, I don't think that's the problem, as TrollFace (and immutable TrollFace) are both 100% legit Ranges.

The problem lies in the implementation that attempts to be immutable aware, and tries to cast away immutability via copying. Which it can't.

The solution is to simply strip range of all its unqual code.

[dlangBugzillaToGithub]

timon.gehr commented on 2013-03-15T04:54:07Z

(In reply to comment #1)
> Predicates? Did you mean "traits" or "restrictions" ?

They are predicates, mappings from types to bool.

>
> Either way, I don't think that's the problem, as TrollFace (and immutable
> TrollFace) are both 100% legit Ranges.
> 
> The problem lies in the implementation that attempts to be immutable aware, and
> tries to cast away immutability via copying. Which it can't.
> 
> The solution is to simply strip range of all its unqual code.

I think TrollierFace will still break many of them.

[dlangBugzillaToGithub]

monarchdodra commented on 2013-03-15T06:21:39Z

(In reply to comment #2)
> (In reply to comment #1)
> > Predicates? Did you mean "traits" or "restrictions" ?
> 
> They are predicates, mappings from types to bool.

Ah OK, I was confused, given the term is often used in algorithms for a specific context.

> > Either way, I don't think that's the problem, as TrollFace (and immutable
> > TrollFace) are both 100% legit Ranges.
> > 
> > The problem lies in the implementation that attempts to be immutable aware, and
> > tries to cast away immutability via copying. Which it can't.
> > 
> > The solution is to simply strip range of all its unqual code.
> 
> I think TrollierFace will still break many of them.

Hum. My testing shows that once you "fix" the ranges, then the code mostly just fails at the call side, since all these functions take by value. But had they taken by ref, then the error would be inside the implementation, so good catch.

I think there is a bug in isForwardRange. It should test at the very least that the result of save can be used to instantiate a new Range (eg: R r2 = r.save;). If we don't have this, then being able to call save is mostly pretty irrelevant...

...either that, or too restrictive to be useful anyways.

I had a fix prepared for another un-related bug in isForwardRange, so I'll also do this.