[phobos] is*Range + Qualified Types

[Andrei Alexandrescu]

So the crux of the matter is not operating on constant ranges (which I 
believe we can safely drop), but obtaining non-constant ranges from 
constant containers.

The idea that we could use a symbolic name for the qualifier is, I 
think, workable, but Walter has resisted it on account of exacerbated 
complexity in the implementation. We should explore other means for the 
time being.

Right now a typical container implementation goes like this:

struct Container(T)
{
     ...
     struct Range { ... }
     Range opSlice() { ... }
}

A container might define several ranges, but c[] yields the container's 
primary, most prominent range. Now if we have a const Container!Widget 
object, we need to find an idiomatic way to extract a range from it. 
Here's some code that compiles and runs as expected:

#!/bin/env rdmd
import std.stdio;

struct Container(T)
{
     static struct Node { T payload; Node * next; }
     Node * root;
     struct Range(N) {
         private N * n;
         @property T front() { return n.payload; }
         @property bool empty() { return n is null; }
         void popFront() { n = n.next; }
     }
     Range!Node opSlice() {
         return typeof(return)(root);
     }
     Range!(const Node) opSlice() const {
         return typeof(return)(root);
     }
}

void main() {
     Container!int c1;
     c1.root = new c1.Node;
     c1.root.payload = 5;
     c1.root.next = new c1.Node;
     c1.root.next.payload = 7;
     foreach (i; c1[]) writeln(i);

     foo(c1);
}

void foo(const Container!int c1) {
     foreach (i; c1[]) writeln(i);
}

The basic idea is that the qualifier is propagated from the container to 
the range together with the type of the representation held inside the 
range.

I'm not sure how generalizable this is, but it's a start. There is also 
the remaining nagging issue of duplicating the line

         return typeof(return)(root);

which in other cases might expand to more lines.

Any thoughts would be appreciated.


Andrei

On 8/12/10 7:52 CDT, Steve Schveighoffer wrote:
> ----- Original Message ----
>
>> From: Shin Fujishiro<rsinfu at gmail.com>
>>
>> David Simcha<dsimcha at gmail.com>  wrote:
>>> I'm  looking to go on a major debugging spree and make std.range work
>>> with  const ranges.  For example, the following should work:
>>>
>>>   import std.range, std.algorithm;
>>>
>>> void main() {
>>>        const foo = map!"a ^^ 2"([1,2,3,4,5]);
>>>        auto myRetro = retro(foo);
>>> }
>>
>> Could you elaborate  why?
>>
>> Ranges with const elements must be common; but what's the point  of
>> const ranges?  Const random access ranges are usable, but other  const
>> ranges seem to be useless since popFront and popBack can't be  const.
>
> This seems to point at a larger issue.
>
> With the de-facto range T[], we get an implicit cast to a range of const
> elements, const(T)[].
>
> But we cannot get this with any user-defined type.  I think we will need to
> address this eventually.  It's one of the main reasons dcollections is not
> const-aware, because I don't want to create several types of ranges/cursors, and
> then all the duplicated functions that go with it.  I'd rather use inout and
> have it designate the return type.
>
> I think Janice proposed something a long long time ago that allowed a template
> parameter to represent a const factor of a type, a-la:
>
> SList(V)
> {
>      struct node
>      {
>         V value;
>         node *next;
>      }
>      node *head;
>
>      struct range(const C)
>      {
>          C(node)* cur;
>          @property C(V) front() {return cur.value;}
>          void popFront() {next = cur.next;}
>          @property bool empty() {return next !is null;}
>      }
>
>      range!(inout) opSlice() inout {range!(inout) result;  result.cur = head;
> return result;}
> }
>
> So basically, the way it works is C is substituted for a const factor (const,
> immutable, or nothing).  And more importantly, the compiler allows implicit
> conversion from a range!(???) to a range!(const).  Also, we can apply inout
> rules.  (Note, I don't know what to put as a const parameter for mutable, since
> that's not a keyword, hence the ???).
>
> Does this seem complex?  Yes.  But it's not as complex/hard to read/hard to
> implement as 3 copies of all functions with 3 different range types.  It's akin
> to the savings/clarity of inout.
>
> What I'm unsure about is if we need to do it this way.  I don't like using a
> user-defined parameter as the const factor, it makes it #1 hard to read, and #2
> every person's const factor symbol may be different.  Most likely, you will have
> one const template parameter.  Do we need to support multiple parameters?  inout
> avoids requiring templates, because the code generation is identical.  Can we do
> something similar to inout?
>
> We're going to need something like this to avoid rediculous code repetition for
> any type that uses custom range types.  Essentially what we need to duplicate is
> the "apply const only to one member" feature of builtin arrays.
>
> -Steve
>
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos