www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How to correctly handle immutable ranges

reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
Here's a few facts:

(assume R is any range type)

1. All immutable(R) cannot be iterated using popFront (obviously).

2. Most immutable(R) cannot be iterated using foreach. The 
exception is immutable(T[]), which can.

3. In theory, immutable(R) could be iterated if it had immutable 
opIndex and length. However, to return a subrange you also need 
immutable opSlice. foreach does not use this.

4. When passed into a function, top-level immutable is removed 
for arrays and pointers, but no other type (can someone tell me 
why?).


Now, suppose I want to write a simple function that looks for a 
subrange in a range of ranges. Here's what I would probably write 
(ignoring custom predicates, optimisations etc.)

RoR findSubrange(RoR, R)(RoR ror, R r)
     if (isInputRange!RoR &&
         isInputRange!(ElementType!RoR) &&
         isInputRange!R)
{
	for (; !ror.empty; ror.popFront())
		if (equal(ror.front, r))
			break;
	return ror;
}

This function has a few problems:

A. If you pass an immutable array for ror, the top-level 
immutable will be stripped, giving you a mutable ror. Great. 
However, only the top level immutable is stripped. If the 
subranges are immutable then they will stay immutable and the 
second line of the template constraint will fail.

B. If you change the second line to 
isInputRange!(Unqual!(ElementType!RoR)) then you will correctly 
accept immutable arrays, but you also end up accepting ranges of 
other immutable ranges, which in general are not iterable, so the 
call to equal will fail.

C. If you change the second line to isIterable!(ElementType!RoR) 
then it will fail when the element type has opApply. Also, equal 
only requires isInputRange, so whether or not it fails depends on 
whether equal uses popFront or not (it doesn't for arrays, but it 
could...)

D. If RoR is any sort of wrapper around arrays (e.g. 
map!"a"(ror)) then it will fail because top level immutable is 
not stripped. In theory, you could iterate the map over array by 
using opIndex, length, and return a slice, but that would require 
a lot of duplication of code.


My questions are:

1. First, why is top-level immutable stripped for arrays and 
pointers but not other types?
2. How should you handle the special case of ranges of immutable 
arrays in a consistent manner?
3. How should you handle the alternate iteration method with 
opIndex/length/opSlice?

Cheers,
Peter
Dec 31 2012
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 31 December 2012 at 13:31:44 UTC, Peter Alexander 
wrote:

 My questions are:

 1. First, why is top-level immutable stripped for arrays and 
 pointers but not other types?
 2. How should you handle the special case of ranges of 
 immutable arrays in a consistent manner?
 3. How should you handle the alternate iteration method with 
 opIndex/length/opSlice?

 Cheers,
 Peter


1. I'd say: Just because it can: If you pass in "immutable(T[])", 
then it is 100% safe to declare that that copy is a 
"immutable(T)[]". Ditto for pointers.

The same can't be said about ranges: a "immutable(Range!T)" might 
not safely copyable as a "Range!(immutable(T))"

2. I *might* start by providing "??? opSlice(void) const", which, 
when present, would allow extracting a "Range!(immutable(T))" 
from a "immutable(T)[]". It wouldn't help *much*, so no generic 
code could exploit this (as it wouldn't be required).

3. No idea.

--------
That said, some might question  the entire concept of an 
"immutable range". a "range of immutables" makes sense, the other 
way around: less so (IMO).

As for the special case of RoIR: If the top level R exposes its 
elements by ref, then it would be just plain wrong to strip the 
immutability of the underlying ranges. You could only legally 
iterate on *copies* of the subranges, but not the ranges 
themselves. This just brings us back to the problem of top level 
Immutable Ranges: IMO, RoIR is not really a special case compared 
to simple IR (outside of the slice of slice case, I guess).
Dec 31 2012
parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Monday, 31 December 2012 at 14:24:53 UTC, monarch_dodra wrote:

 The same can't be said about ranges: a "immutable(Range!T)" 
 might not safely copyable as a "Range!(immutable(T))"


Hmm, are you sure? Can you give an example? Surely if Range is a 
struct and everything is copied then it can all change from 
mutable to immutable (using a postblit where necessary).

Maybe we just need copy constructors for this to work around the 
const issue with postblit.



 3. No idea.


There is one way you could work around it in a generic manner, 
but involves a bit of boilerplate:

auto iterable(R)(R r)
{
	struct Iterable
	{
		this(R range) { _range = range; }

		static if (isInputRange!R)
		{
			alias _range this;
			alias _range result;
		}
		else static if (isRandomAccess!R && hasLength!R && hasSlicing!R)
		{
			 property auto front() { return _range[_index]; }
			 property bool empty() const { return _index == _range.length; 
}
			void popFront() { ++_index; }
			 property auto save() { return this; }
			 property R result() { return _range[_index..$]; }
			private size_t _index = 0;
		}

		private R _range;
	}
	return Iterable(r);
}

You just have to use iterable everywhere instead of the range, 
and then use .result to get back to the original range type. e.g.

RoR findSubrange(RoR, R)(RoR ror, R r)
{
         auto _ror = iterable(ror);
         auto _r = iterable(r);
	for (; !_ror.empty; _ror.popFront())
		if (equal(iterable(_ror.front), _r))
			break;
	return _ror.result;
}

Warning: code is totally untested, but should give the gist of 
the idea.



 That said, some might question  the entire concept of an 
 "immutable range". a "range of immutables" makes sense, the 
 other way around: less so (IMO).


I kind of agree, but unfortunately immutable arrays are iterable, 
and arrays are the most common range, so we really need to 
support them.
Dec 31 2012
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 31 December 2012 at 14:58:03 UTC, Peter Alexander 
wrote:

 On Monday, 31 December 2012 at 14:24:53 UTC, monarch_dodra 
 wrote:

 The same can't be said about ranges: a "immutable(Range!T)" 
 might not safely copyable as a "Range!(immutable(T))"


 Hmm, are you sure? Can you give an example?


Yes, any (well, most) reference type range will fail the 
conversion. For example:

import std.array;

//---
struct ShallowRange(T)
{
   T[]* payload;

   T front() const {return (*payload).front;}
   void popFront(){(*payload).popFront;}
   bool empty() const {return (*payload).empty;}
}

ShallowRange!T shallowRange(T)(ref T[] data)
{
   return ShallowRange!T(&data);
}

immutable(ShallowRange!T) immutableShallowRange(T)(ref 
immutable(T[]) data)
{
   return cast(immutable(ShallowRange!T)) 
ShallowRange!T(cast(T[]*)&data);
}

void main()
{
   immutable(int)[] slice  = [1, 2, 3];
   immutable(int[]) iSlice = [1, 2, 3];

   ShallowRange!(immutable(int)) range  = shallowRange(slice);
   immutable(ShallowRange!int)   iRange = 
immutableShallowRange(iSlice);
}
//---

Here, I have a slice of immutables (slice) and an immutable slice 
(iSlice), which I place in a range of immutables, and an 
immutable range (respectivelly).

If you cast my immutable range to a range of immutables, and then 
attempt to iterate over it, you are going to modify my immutable 
iSlice...


  Surely if Range is  a struct...


I'm not well versed in how classes and immutability work 
(especially when discussing the immutability of the class object 
itself, vs the class + class reference).

But yeah, keep in mind a range can be implemented as a class.


 ... and everything is copied then it can all change from 
 mutable to immutable (using a postblit where necessary).

 Maybe we just need copy constructors for this to work around 
 the const issue with postblit.


I think this is a language wide issue (well, concept). A range 
really is no different from any other object, and you really 
can't know what will happen when you copy them.

As a general rule, even via CC, you can't assume the result of 
copying a "immutable(S!T)" (or "immutable(S!(immutable(T))") will 
be a "S!(immutable(T)".

--------
But back to the original problem, I just think one shouldn't be 
able to call a const object a range. A "Range" is mutable by 
nature. Any attempt to pass one to an algorithm should fail (IMO).

I've yet to see anybody try to manipulate const ranges anyways 
(which probably isn't a coincidence), though someone one prove me 
wrong/disagree.

We just have a really special case regarding const slices. Even 
then, the only reason you can "iterate them" is because the 
compiler is implicitly copying a mutable slice behind the scenes. 
The const slice itself, technically, really isn't iterable 
(AFAIK)...

I think the slices' behavior twists our view of what to expect 
from the rest of our ranges.
Dec 31 2012
parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Monday, 31 December 2012 at 16:29:27 UTC, monarch_dodra wrote:

 But back to the original problem, I just think one shouldn't be 
 able to call a const object a range. A "Range" is mutable by 
 nature. Any attempt to pass one to an algorithm should fail 
 (IMO).


This will break a lot of existing code.

This currently works:

immutable int[] a = [1, 2, 3];
auto b = array(a);

std.array.array is one of the few functions that uses 
std.traits.isIterable, so it works for immutable slices.



 We just have a really special case regarding const slices. Even 
 then, the only reason you can "iterate them" is because the 
 compiler is implicitly copying a mutable slice behind the 
 scenes. The const slice itself, technically, really isn't 
 iterable (AFAIK)...


It could also iterate the indices:

immutable int[] a = [1, 2, 3];
foreach (i; 0..a.length)
     foo(a[i]);

Nothing illegal about that.

The specific issue I'm looking at is the joining of an immutable 
array of arrays. It should be allowed, because they can be 
iterated. In fact, if you just remove the template constraints 
from std.array.join then it works.
Dec 31 2012
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 31 December 2012 at 17:11:01 UTC, Peter Alexander 
wrote:

 On Monday, 31 December 2012 at 16:29:27 UTC, monarch_dodra 
 wrote:

 But back to the original problem, I just think one shouldn't 
 be able to call a const object a range. A "Range" is mutable 
 by nature. Any attempt to pass one to an algorithm should fail 
 (IMO).


 This will break a lot of existing code.

 This currently works:

 immutable int[] a = [1, 2, 3];
 auto b = array(a);

 std.array.array is one of the few functions that uses 
 std.traits.isIterable, so it works for immutable slices.


Yes, but technically, the passed object is "immutable(int)[]", 
which *is* a range, so that has nothing to do with isIterable.

But you do bring up a good point. All too often we settle for 
InputRange when we can have Iterable.

That said, it does come with its own problems, such as:
* Figuring out the iteration type?
* Iterate by ref, or by value?
* Difficult to handle "special first step" cases...

Last but not least, I was told by Andrei not too long ago (while 
working on reduce) that "opApply" objects where *not* supported 
by std.algorithm. I was even told to remove existing code that 
supported it.


 We just have a really special case regarding const slices. 
 Even then, the only reason you can "iterate them" is because 
 the compiler is implicitly copying a mutable slice behind the 
 scenes. The const slice itself, technically, really isn't 
 iterable (AFAIK)...


 It could also iterate the indices:

 immutable int[] a = [1, 2, 3];
 foreach (i; 0..a.length)
     foo(a[i]);

 Nothing illegal about that.

 The specific issue I'm looking at is the joining of an 
 immutable array of arrays. It should be allowed, because they 
 can be iterated. In fact, if you just remove the template 
 constraints from std.array.join then it works.


Well, the reason it works is not that they can be iterated, but 
that the constness of the subslices is stripped when passed to 
Appender.Put (which, btw, accepts InputRanges, but Iterables). 
Really, this is more luck than an "isIterable" thing.

--------
But you do bring up the issue of giving more love to iterables.

If you want to add support to joiner, you *may* have to start 
with adding support for it for appender though. I'm unsure: 
Appender doesn't accept Iterables, but the free standing put 
does, so it might be able to individually call 
Appender.put(element). Not sure... if it works... or is 
efficient...

In any case, I think it'd be wrong to special case support for 
Range of Immutable Array. At best, the type Immutable Array is 
iterable, but not a range. Trying to change that would (IMO) warp 
the language.
Dec 31 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, December 31, 2012 15:58:02 Peter Alexander wrote:

 On Monday, 31 December 2012 at 14:24:53 UTC, monarch_dodra wrote:

 The same can't be said about ranges: a "immutable(Range!T)"
 might not safely copyable as a "Range!(immutable(T))"


 
 Hmm, are you sure? Can you give an example? Surely if Range is a
 struct and everything is copied then it can all change from
 mutable to immutable (using a postblit where necessary).


immutable(Range!T) and Range!(immutable(T)) are completely different types. 
They may come from the same template, but they're different instantiations of 
that template, and there's no guarantee that they have any relation to each 
other. In a pathalogical case, you could have something like

struct S(T)
{
 static if(is(T == immutable))
 {
 double d;
 int foo() { return 7; }
 }
 else
 {
 int i;
 string s = "hello";
 bool maybe;

 double bar(int i) { return i * 1.1; }
 void baz() { writeln(i); }
 }
}

So, the compiler can't assume that immutable(Range!T) and Range!(immutable(T)) 
have any real relation with one another.

Ideally, that problem could be solved by declaring an overload of opSlice 
which returned a tail-const version of the range, but that poses difficulties 
due to circular dependencies when one template instantiation refers to 
another. The circular dependency problem might be solvable with a static if 
though. I'd have to play around with it more to figure out the details. It's a 
bit of a thorny problem, and I've had issues with it in the past.

But if a tail-const opSlice can be done, then if you need a tail-const version 
of a range, you can just slice the range to get it, which is what happens with 
arrays. It's just that with them, it's done automatically. If the opSlice stuff 
got sorted out well enough though, and it was generally accepted how to define 
a tail-const opSlice, then it might be reasonable for the compiler to use that 
where appropriate, giving ranges the same tail-const abilities as arrays.

- Jonathan M Davis
Jan 02 2013