View mode: basic / threaded / horizontal-split · Log in · Help
October 02, 2012
"IndexType" for ranges
If you've ever worked on a template that needs to index a range, 
you may have run into this problem: What is the type you should 
use to index an RA range?

The problem may not sound like much, but it is a royal pain in 
the ass when trying to write "wrapper ranges", such as 
std.algorithm.map.

Shoot to low, and you may en up failing to compile code such as 
"r[r.length - 1]", because r.length is of type ulong, making the 
implicit down-cast illegal.

Shoot to high, and the implementation itself will fail to compile:
auto opIndex(ulong n)
    return r[n]; //cannot cast ulong to size_t

You might think "just use typeof(length)" BUT:
*you aren't even guaranteed that "typeof(length)" will be 
correct! Certain ranges, such as iota, will return a length 
usually of type uint, but be indexed with ulong... :/
*Infinite ranges don't have length...

--------
I'd like to propose a trait called "IndexType" or "IndexingType". 
This trait would be defined as "A type that can be used to safely 
index (or slice) a range".

Here is how I would define and implement this trait:
"If R is a RandomAccessRange, then IndexType is the type used by 
opIndex".

Simple enough, and I got it done and working locally, but there 
are 2 issues I'd like to share and inquire here:

*First, if R also verifies hasLength, then writing "r[r.length]" 
should be a compile time legality: The type returned by Length 
must fit inside opIndex. This might sound obvious, but this 
restriction is .
**I propose adding this extra restriction to isRandomAccess: "if 
the range verifies $(D hasLength), then it must also be 
index-able by the type returned by length"

*Second, the idea is that IndexType should *also* be useable to 
slice a range. Because of this, I'd like to add two extra 
restrictions to isSliceable:
**A sliceable range must also be indexable(RA). A range that is 
sliceable but not indexeable is kind of retarded anyways, since 
you can index doing r[n, n+1].front;
**Given that R must be indexable, the type used to index the 
range must be compatible with slicing.

--------
These are not big changes I'm proposing, but they *may* break 
some existing ranges. Those ranges are arguably retarded, and 
these changes would enforce correctness, but they'd break none 
the less. I'd like some feedback if you think this trait is worth 
pushing?

--------

For illustration, here are three examples:
//--------
struct S1
{
  //Other primitives here...
  @property ushort length();
  auto opIndex(uint);
  auto opSlice(ulong, ulong);
}
struct S2
{
  //Other primitives here...
  @property ulong length();
  auto opIndex(ushort);
}
struct S3
{
  //Other primitives here...
  @property ushort length();
  auto opIndex(ulong);
  auto opSlice(ushort, ushort);
}
//--------
Here:
*S1 would have a "IndexType" equal to uint. S1 would be a 
RandomAccessRange and verify isSliceable.
*S2 would NOT be a random access range, because its length can't 
index it.
*S3 would be a RandomAccess. it's IndexType would be ulong. It 
would not verify "hasSlicing" because it can't be sliced using 
IndexType.
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra wrote:
> If you've ever worked on a template that needs to index a 
> range, you may have run into this problem: What is the type you 
> should use to index an RA range?

Forgive my ignorance. What's wrong with size_t?
October 02, 2012
Re: "IndexType" for ranges
On 2012-10-02, 18:09, Peter Alexander wrote:

> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra wrote:
>> If you've ever worked on a template that needs to index a range, you  
>> may have run into this problem: What is the type you should use to  
>> index an RA range?
>
> Forgive my ignorance. What's wrong with size_t?

That not all ranges use it? If the range uses int, short, byte
(I wonder why they'd do it, though), using size_t will not even
compile.

-- 
Simen
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, 2 October 2012 at 16:09:16 UTC, Peter Alexander wrote:
> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra wrote:
>> If you've ever worked on a template that needs to index a 
>> range, you may have run into this problem: What is the type 
>> you should use to index an RA range?
>
> Forgive my ignorance. What's wrong with size_t?

This is what happens when you use size_t:

//----
import std.range;
import std.algorithm;

struct ZeroToTen
{
    ushort first = 0;
    ushort last = 10;
    @property bool empty(){return first == last;}
    @property ushort front(){return first;}
    void popFront(){++first;}
    @property ushort back(){return last;}
    void popBack(){--last;}
    @property ZeroToTen save(){return this;}
    @property ushort length(){return cast(ushort)(last - first);}
    ushort opIndex(ushort n){return cast(ushort)(first + n);}
}

void main()
{
    ZeroToTen ztt;

    static assert(hasLength!ZeroToTen);      //OK: normal
    static assert(isRandomAccess!ZeroToTen); //Ok... But I don't 
like where this is going...

    auto r = assumeSorted(ztt); //DERP!
}
//----
\src\phobos\std\range.d(6909): Error: function 
main.ZeroToTen.opIndex (ushort n) is not callable using argument 
types (uint)
\src\phobos\std\range.d(6909): Error: cannot implicitly convert 
expression (i) of type uint to ushort
\src\phobos\std\range.d(7346): Error: template instance 
std.range.SortedRange!(ZeroToTen,"a < b") error instantiating
//----
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, 2 October 2012 at 16:29:28 UTC, Simen Kjaeraas wrote:
> On 2012-10-02, 18:09, Peter Alexander wrote:
>
>> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra 
>> wrote:
>>> If you've ever worked on a template that needs to index a 
>>> range, you may have run into this problem: What is the type 
>>> you should use to index an RA range?
>>
>> Forgive my ignorance. What's wrong with size_t?
>
> That not all ranges use it? If the range uses int, short, byte
> (I wonder why they'd do it, though), using size_t will not even
> compile.

That's kind of my point. Unless there's a compelling reason not 
to, I'd suggest we standardise on size_t indexing (and length) 
and avoid this issue altogether.

C++ containers have a size_type typedef. No one uses it.

Let's keep things simple instead of complicating things for the 
sake of unwanted "flexibility".
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, 2 October 2012 at 16:44:48 UTC, monarch_dodra wrote:
> On Tuesday, 2 October 2012 at 16:09:16 UTC, Peter Alexander 
> wrote:
>> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra 
>> wrote:
>>> If you've ever worked on a template that needs to index a 
>>> range, you may have run into this problem: What is the type 
>>> you should use to index an RA range?
>>
>> Forgive my ignorance. What's wrong with size_t?
>
> This is what happens when you use size_t:
>

http://dpaste.dzfl.pl/d95ccb14

On a side note, SortedRange is pretty bold at assuming the range 
is slice-able. Gonna fix that.
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, 2 October 2012 at 16:44:48 UTC, monarch_dodra wrote:
> On Tuesday, 2 October 2012 at 16:09:16 UTC, Peter Alexander 
> wrote:
>> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra 
>> wrote:
>>> If you've ever worked on a template that needs to index a 
>>> range, you may have run into this problem: What is the type 
>>> you should use to index an RA range?
>>
>> Forgive my ignorance. What's wrong with size_t?
>
> This is what happens when you use size_t:
>
> [snip]

Then don't create ranges that use ushort for indexing and length. 
There's no need to.

To be clear, I'm suggesting that all random access ranges should 
use size_t, and they will not be random access ranges if they use 
anything else. Unless someone can give a compelling reason not to 
do this, I cannot see anything but benefits.
October 02, 2012
Re: "IndexType" for ranges
monarch_dodra wrote:
> On Tuesday, 2 October 2012 at 16:09:16 UTC, Peter Alexander wrote:
>> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra wrote:
>>> If you've ever worked on a template that needs to index a range, you
>>> may have run into this problem: What is the type you should use to
>>> index an RA range?
>>
>> Forgive my ignorance. What's wrong with size_t?
>
> This is what happens when you use size_t:
>
> //----
> import std.range;
> import std.algorithm;
>
> struct ZeroToTen
> {
>      ushort first = 0;
>      ushort last = 10;
>      @property bool empty(){return first == last;}
>      @property ushort front(){return first;}
>      void popFront(){++first;}
>      @property ushort back(){return last;}
>      void popBack(){--last;}
>      @property ZeroToTen save(){return this;}
>      @property ushort length(){return cast(ushort)(last - first);}
>      ushort opIndex(ushort n){return cast(ushort)(first + n);}
> }

Why not use size_t or ulong as parameter? This way all smaller types 
will be implicitly converted.

       ushort opIndex(size_t n){return cast(ushort)(first + n);}
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, October 02, 2012 18:45:50 Peter Alexander wrote:
> On Tuesday, 2 October 2012 at 16:29:28 UTC, Simen Kjaeraas wrote:
> > On 2012-10-02, 18:09, Peter Alexander wrote:
> >> On Tuesday, 2 October 2012 at 13:17:45 UTC, monarch_dodra
> >> 
> >> wrote:
> >>> If you've ever worked on a template that needs to index a
> >>> range, you may have run into this problem: What is the type
> >>> you should use to index an RA range?
> >> 
> >> Forgive my ignorance. What's wrong with size_t?
> > 
> > That not all ranges use it? If the range uses int, short, byte
> > (I wonder why they'd do it, though), using size_t will not even
> > compile.
> 
> That's kind of my point. Unless there's a compelling reason not
> to, I'd suggest we standardise on size_t indexing (and length)
> and avoid this issue altogether.
> 
> C++ containers have a size_type typedef. No one uses it.
> 
> Let's keep things simple instead of complicating things for the
> sake of unwanted "flexibility".

In general, all ranges _should_ use size_t for both length and indexing, but 
for a few range types in Phobos specifically use ulong (e.g. IIRC iota does in 
order to work properly with ranges or long and ulong on 32-bit systems). I see 
_zero_ reason to support lengths or indices smaller than size_t. Types that do 
that are badly designed IMHO. But we already have a precedent that you can't 
always assume size_t (at least for length - I'm not sure about indices - but 
if length can be specifically ulong and the type is random access, then its 
indices will need to be ulong), so unfortunately, the situation is not so 
simple that you can always assume size_t (even you should arguably be able 
to).

- Jonathan M Davis
October 02, 2012
Re: "IndexType" for ranges
On Tuesday, 2 October 2012 at 16:48:34 UTC, Peter Alexander wrote:
> Then don't create ranges that use ushort for indexing and 
> length. There's no need to.
>
> To be clear, I'm suggesting that all random access ranges 
> should use size_t, and they will not be random access ranges if 
> they use anything else. Unless someone can give a compelling 
> reason not to do this, I cannot see anything but benefits.

I don't know, forcing an implementer on size_t is pretty 
gratuitous. Why can't he be free to choose his own index type?

Besides, you'll still run into the problem for ranges that use 
ulong, such as iota.

Then what about ranges that use ulong? As those wrong too? What 
about iota? Wrong?

//----
import std.range;
import std.algorithm;

void main()
{
    auto r = assumeSorted(iota(0L, 1L)); //Still DERP!
}
//----
src\phobos\std\range.d(6925): Error: cannot implicitly convert 
expression (this._input.length()) of type ulong to uint
src\phobos\std\range.d(7346): Error: template instance 
std.range.SortedRange!(Result,"a < b") error instantiating
//----

And this time, you can't blame me for doing fishy code, it's all 
in phobos.

The end problem is this.

//----
struct S(R)
{
    //...
    auto opIndex(some_type n)
    {
        return r[r];
    }
}
//----
Regardless of what you do, you will encounter problems at the 
"boundaries" or S.opIndex. Either for calling it, because 
some_type is too small, either for implementing it, because 
some_type is too big.

The fact that both uint, ulong and size_t are valid indexers for 
range means ANYTHING in Phobos can break.

The trait I'm proposing should enable support for uint, ulong and 
size_t, and every other type as an added bonus.
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home