On Monday, June 18, 2012 10:06:44 Matthias Walter wrote:
> Hi,
> 
> last week I realized that a const version of std.container.Array.opSlice() is missing. Now I looked at the code and I think that it is a general design problem.
> 
> The docs state that "c.Range" is "The primary range type associated with the container.". I think we really always need two Range types (one for const view and one for non-const view) by design.
> 
> I'd propose to always add a bool template parameter (maybe isConst?) to the range since most of the write-functionality can be "removed" by a static if statement in order to make the range read-only.
> 
> Any suggestions?

Yeah, it'll probably have to be templated. C++ already has to do something similar with iterators and const_iterators. But since you don't normally use the type of a range explicitly, it shouldn't be a big deal. The one downside that might pose a problem though is that if someone _does_ use the type explicitly, their code will break if the type gets templated. We could make a second type (ConstRange?) for the iterating over a const Array, but I'd be tempted to just templatize the thing and let it break any code that it breaks. std.container is already likely to break stuff to at least some extent when the custom allocators get added anyway. I suppose that we could just rename the type and then create an alias for the current type

struct ArrayRange(bool isConst) {...}
alias ArrayRange!false Range;
alias ArrayRange!true ConstRange;

but that might be overkill. I don't know. Regardless, it _is_ likely that the range type will have to be templatized to fix the problem. Ranges and range- based functions in general need to be cleaned up a bit to deal with const, since the way that they're designed doesn't work with const very well, and we need to make it work. I think that it _can_ work, but it takes more effort to do so.

- Jonathan M Davis

On 06/18/2012 01:08 PM, Jonathan M Davis wrote:
> On Monday, June 18, 2012 10:06:44 Matthias Walter wrote:
>> Hi,
>> 
>> last week I realized that a const version of std.container.Array.opSlice() is missing. Now I looked at the code and I think that it is a general design problem.
>> 
>> The docs state that "c.Range" is "The primary range type associated with the container.". I think we really always need two Range types (one for const view and one for non-const view) by design.
>> 
>> I'd propose to always add a bool template parameter (maybe isConst?) to the range since most of the write-functionality can be "removed" by a static if statement in order to make the range read-only.
>> 
>> Any suggestions?
> 
> Yeah, it'll probably have to be templated. C++ already has to do something similar with iterators and const_iterators. But since you don't normally use the type of a range explicitly, it shouldn't be a big deal. The one downside that might pose a problem though is that if someone _does_ use the type explicitly, their code will break if the type gets templated. We could make a second type (ConstRange?) for the iterating over a const Array, but I'd be tempted to just templatize the thing and let it break any code that it breaks. std.container is already likely to break stuff to at least some extent when the custom allocators get added anyway. I suppose that we could just rename the type and then create an alias for the current type
> 
> struct ArrayRange(bool isConst) {...} alias ArrayRange!false
> Range; alias ArrayRange!true ConstRange;
> 
> but that might be overkill. I don't know. Regardless, it _is_ likely that the range type will have to be templatized to fix the problem. Ranges and range- based functions in general need to be cleaned up a bit to deal with const, since the way that they're designed doesn't work with const very well, and we need to make it work. I think that it _can_ work, but it takes more effort to do so.

I fully agree with all that. In order to migrate older code we may make isConst have a default value of false.

Best regards,

Matthias

Jonathan M Davis , dans le message (digitalmars.D:170054), a écrit :
>> I'd propose to always add a bool template parameter (maybe isConst?) to the range since most of the write-functionality can be "removed" by a static if statement in order to make the range read-only.
>> 
>> Any suggestions?

Boolean parameters are very obscure.
How do you guess what is the meaning of false in:
Range!false;

Range!IsConst.no would be better.

> struct ArrayRange(bool isConst) {...}
> alias ArrayRange!false Range;
> alias ArrayRange!true ConstRange;

Range and ConstRange seems a good thing to have, just like c++ containers have iterator and const_iterator.

On 06/19/2012 02:54 PM, Christophe Travert wrote:
> Jonathan M Davis , dans le message (digitalmars.D:170054), a écrit :
>>> I'd propose to always add a bool template parameter (maybe isConst?) to
>>> the range since most of the write-functionality can be "removed" by a
>>> static if statement in order to make the range read-only.
>>>
>>> Any suggestions?
>
> Boolean parameters are very obscure.
> How do you guess what is the meaning of false in:
> Range!false;
>
> Range!IsConst.no would be better.
>
>> struct ArrayRange(bool isConst) {...}
>> alias ArrayRange!false Range;
>> alias ArrayRange!true ConstRange;
>
> Range and ConstRange seems a good thing to have, just like c++
> containers have iterator and const_iterator.
>

Something along these lines seems to be a superior design:

struct ArrayRange(T){ ... }

class Array(T){
    ...
    ArrayRange!T opSlice(){ ... }
    ArrayRange!(const(T)) opSlice()const{ ... }
    ArrayRange!(immutable(T)) opSlice()immutable{ ... }
    ...
}

(Where the opSlice functions can be generated automatically.)

On 06/19/2012 04:04 PM, Timon Gehr wrote:
> On 06/19/2012 02:54 PM, Christophe Travert wrote:
>> Jonathan M Davis , dans le message (digitalmars.D:170054), a écrit :
>>>> I'd propose to always add a bool template parameter (maybe isConst?) to the range since most of the write-functionality can be "removed" by a static if statement in order to make the range read-only.
>>>>
>>>> Any suggestions?
>>
>> Boolean parameters are very obscure.
>> How do you guess what is the meaning of false in:
>> Range!false;
>>
>> Range!IsConst.no would be better.
>>
>>> struct ArrayRange(bool isConst) {...}
>>> alias ArrayRange!false Range;
>>> alias ArrayRange!true ConstRange;
>>
>> Range and ConstRange seems a good thing to have, just like c++ containers have iterator and const_iterator.
>>
> 
> Something along these lines seems to be a superior design:
> 
> struct ArrayRange(T){ ... }
> 
> class Array(T){
>     ...
>     ArrayRange!T opSlice(){ ... }
>     ArrayRange!(const(T)) opSlice()const{ ... }
>     ArrayRange!(immutable(T)) opSlice()immutable{ ... }
>     ...
> }
> 
> (Where the opSlice functions can be generated automatically.)

I like the design. I looked at the actual implementation of std.container.Array and realized the following problem:

The payload is stored in a RefCounted object. The range returned by opSlice() const must obviously somehow access the payload. By documentation of RefCounted, "no references to the payload should be escaped outside the RefCounted object." which implies that we need to create a copy of the RefCounted variable to have proper access.

On the other hand, given the constness of opSlice() we only have access to a const version of the RefCounted variable which cannot be used to create another reference since the reference counter is const as well.

So how can a ConstRange be implemented *somehow*?

Matthias

On 06/20/2012 12:29 PM, Matthias Walter wrote:
> On 06/19/2012 04:04 PM, Timon Gehr wrote:
>> On 06/19/2012 02:54 PM, Christophe Travert wrote:
>>> Jonathan M Davis , dans le message (digitalmars.D:170054), a écrit :
>>>>> I'd propose to always add a bool template parameter (maybe isConst?) to
>>>>> the range since most of the write-functionality can be "removed" by a
>>>>> static if statement in order to make the range read-only.
>>>>>
>>>>> Any suggestions?
>>>
>>> Boolean parameters are very obscure.
>>> How do you guess what is the meaning of false in:
>>> Range!false;
>>>
>>> Range!IsConst.no would be better.
>>>
>>>> struct ArrayRange(bool isConst) {...}
>>>> alias ArrayRange!false Range;
>>>> alias ArrayRange!true ConstRange;
>>>
>>> Range and ConstRange seems a good thing to have, just like c++
>>> containers have iterator and const_iterator.
>>>
>>
>> Something along these lines seems to be a superior design:
>>
>> struct ArrayRange(T){ ... }
>>
>> class Array(T){
>>      ...
>>      ArrayRange!T opSlice(){ ... }
>>      ArrayRange!(const(T)) opSlice()const{ ... }
>>      ArrayRange!(immutable(T)) opSlice()immutable{ ... }
>>      ...
>> }
>>
>> (Where the opSlice functions can be generated automatically.)
>
> I like the design. I looked at the actual implementation of
> std.container.Array and realized the following problem:
>
> The payload is stored in a RefCounted object. The range returned by
> opSlice() const must obviously somehow access the payload. By
> documentation of RefCounted, "no references to the payload should be
> escaped outside the RefCounted object." which implies that we need to
> create a copy of the RefCounted variable to have proper access.
>
> On the other hand, given the constness of opSlice() we only have access
> to a const version of the RefCounted variable which cannot be used to
> create another reference since the reference counter is const as well.
>
> So how can a ConstRange be implemented *somehow*?
>
> Matthias

Escape the payload anyway and document that the range is invalid after the container has been destroyed.

But I question the usefulness of having a const or immutable RefCounted object at all.

Maybe it is better to have something like this:

struct ArrayRange(T){
    ArrayRange!(const(StripImmutable!T)) constView() const { ... };
    alias constView this;
}

class Array(T){
    ArrayRange!T opSlice(){ ... }
}

On Wednesday, June 20, 2012 13:38:31 Timon Gehr wrote:
> Escape the payload anyway and document that the range is invalid after the container has been destroyed.

That's a given anyway. Ranges from containers are _always_ invalid after the container that they come from is gone. They can also become invalid for a variety of operations on the container. That's why we have the stableX functions. So, there may be serious problems with a range over a const Array, but the invalidation of its range when the Array goes away is not one of them.

- Jonathan M Davis

On 06/20/2012 06:03 PM, Jonathan M Davis wrote:
> On Wednesday, June 20, 2012 13:38:31 Timon Gehr wrote:
>> Escape the payload anyway and document that the range is invalid after
>> the container has been destroyed.
>
> That's a given anyway. Ranges from containers are _always_ invalid after the
> container that they come from is gone. They can also become invalid for a
> variety of operations on the container. That's why we have the stableX
> functions. So, there may be serious problems with a range over a const Array,
> but the invalidation of its range when the Array goes away is not one of them.
>
> - Jonathan M Davis

I mean invalid as in "failure to respect the invalidity of the range
results in memory corruption". Therefore, such a design couldn't be
used from @safe code.

On 6/20/12 11:03 AM, Jonathan M Davis wrote:
> On Wednesday, June 20, 2012 13:38:31 Timon Gehr wrote:
>> Escape the payload anyway and document that the range is invalid after
>> the container has been destroyed.
>
> That's a given anyway. Ranges from containers are _always_ invalid after the
> container that they come from is gone. They can also become invalid for a
> variety of operations on the container. That's why we have the stableX
> functions. So, there may be serious problems with a range over a const Array,
> but the invalidation of its range when the Array goes away is not one of them.

Actually supporting orphan ranges has been discussed and may make sense.

Andrei