On Thursday, December 20, 2012 12:48:10 H. S. Teoh wrote:
> I noticed that in some places in Phobos range-related code, there's an assumption that the following code works:
> 
> auto someRangeFunction(R)(R range) {
> ...
> R helperRange = range;
> ...
> helperRange = R.init;
> assert(helperRange.empty);
> ...
> }
> 
> Exercise for the reader: spot the bug.
> 
> Hint: what if R is an InputRangeObject?

takeNone should be used to empty a range - though whether you get the same type depends on the range (e.g. you'll get the result of takeExactly(range, 0) for an InputRangeObject). And it works the way that it does precisely because there's no guarantee that R.init is even usable. For instance, you can't use init with Voldemort types (which is the main reason that I seriously question the wisdom of Voldemort types at this point). However, any range which is a struct whose init value _isn't_ empty is wrong. We should be be able to rely on that at least.

- Jonathan M Davis

On Thu, Dec 20, 2012 at 09:58:22PM +0100, Jonathan M Davis wrote:
> On Thursday, December 20, 2012 12:48:10 H. S. Teoh wrote:
> > I noticed that in some places in Phobos range-related code, there's an assumption that the following code works:
> > 
> > auto someRangeFunction(R)(R range) {
> > ...
> > R helperRange = range;
> > ...
> > helperRange = R.init;
> > assert(helperRange.empty);
> > ...
> > }
> > 
> > Exercise for the reader: spot the bug.
> > 
> > Hint: what if R is an InputRangeObject?
> 
> takeNone should be used to empty a range - though whether you get the same type depends on the range (e.g. you'll get the result of takeExactly(range, 0) for an InputRangeObject). And it works the way that it does precisely because there's no guarantee that R.init is even usable. For instance, you can't use init with Voldemort types (which is the main reason that I seriously question the wisdom of Voldemort types at this point).

But .init isn't merely used when you explicitly invoke it. It's the default value of struct fields, for example (see below).


> However, any range which is a struct whose init value _isn't_ empty is wrong. We should be be able to rely on that at least.
[...]

No we can't. For example:

	auto someRangeFunction(RoR)(RoR ror) {
		struct Helper {
			RoR _ror;
			ElementType!R _current;

			this(RoR r) {
				_ror = r;
				assert(_current.empty);
			}
		}
		return Helper(ror);
	}

If RoR is an array of class objects, the assert line will segfault because _current.init is null. Conceptually speaking, I agree that a null object is an empty range, but in code, .empty is undefined because you can't invoke a method through a null reference.


T

-- 
ASCII stupid question, getty stupid ANSI.

On Thursday, December 20, 2012 13:08:46 H. S. Teoh wrote:
> > However, any range which is a struct whose init value _isn't_ empty is wrong. We should be be able to rely on that at least.
> 
> [...]
> 
> No we can't. For example:
> 
> auto someRangeFunction(RoR)(RoR ror) {
> struct Helper {
> RoR _ror;
> ElementType!R _current;
> 
> this(RoR r) {
> _ror = r;
> assert(_current.empty);
> }
> }
> return Helper(ror);
> }
> 
> If RoR is an array of class objects, the assert line will segfault because _current.init is null. Conceptually speaking, I agree that a null object is an empty range, but in code, .empty is undefined because you can't invoke a method through a null reference.

If _current is an array, then it won't segfault. A null array returns true for empty. Only classes have problems with null.

But regardless, my point is that Range.init.empty must be true _for structs_. A struct range should be written such that its init value is empty. That's not true for classes, because they'll be null.

Your assertion should pass as long as the type of _current is a struct.

If you want to get an empty range from an existing range, then use takeNone. If it returns the same type (which it tries to do but can't always do - e.g. with non-sliceable ranges which are classes or non-sliceable Voldemort types), then you can reassign it to the original. If it doesn't, then there's no generic way to get an empty range of the same type from that range other than calling popFront until it's empty (which is obviously ineffecient in the finite case and impossible in the infinite case).

- Jonathan M Davis

On Thu, Dec 20, 2012 at 11:04:05PM +0100, Jonathan M Davis wrote:
> On Thursday, December 20, 2012 13:08:46 H. S. Teoh wrote:
> > > However, any range which is a struct whose init value _isn't_ empty is wrong. We should be be able to rely on that at least.
> > 
> > [...]
> > 
> > No we can't. For example:
> > 
> > auto someRangeFunction(RoR)(RoR ror) {
> > struct Helper {
> > RoR _ror;
> > ElementType!R _current;
> > 
> > this(RoR r) {
> > _ror = r;
> > assert(_current.empty);
> > }
> > }
> > return Helper(ror);
> > }
> > 
> > If RoR is an array of class objects, the assert line will segfault because _current.init is null. Conceptually speaking, I agree that a null object is an empty range, but in code, .empty is undefined because you can't invoke a method through a null reference.
> 
> If _current is an array, then it won't segfault. A null array returns true for empty. Only classes have problems with null.

Right.


> But regardless, my point is that Range.init.empty must be true _for structs_.  A struct range should be written such that its init value is empty. That's not true for classes, because they'll be null.
> 
> Your assertion should pass as long as the type of _current is a struct.

The problem with generic code is that you can't assume this. The type could be literally _anything_ (as long as it conforms to the range API). Unless you protect it with static ifs or something similar, of course.


> If you want to get an empty range from an existing range, then use takeNone.  If it returns the same type (which it tries to do but can't always do - e.g.  with non-sliceable ranges which are classes or non-sliceable Voldemort types), then you can reassign it to the original. If it doesn't, then there's no generic way to get an empty range of the same type from that range other than calling popFront until it's empty (which is obviously ineffecient in the finite case and impossible in the infinite case).
[...]

Which is why I'm leaning towards rewriting algorithms so that they don't rely on ranges being emptiable. (Like you said, it's easy to have a range class that's infinite, in which case there is no empty state for ranges of that type at all -- .empty is an enum set to false.) I find that the code often becomes cleaner when written in a way that minimizes extraneous assumptions. It's harder to write, for sure, but I think it's more rewarding in the end.

Anyway, coming back to takeNone: in many cases takeNone won't return the exact same type as the original range, so code like this won't work anymore:

	auto myRangeFunc(R)(R range) {
		struct Wrapper {
			R _src;
			R _helper;

			this(R src) {
				_src = src;
				...

				// Works:
				_helper = _src;
				...

				// Won't work: R != typeof(takeNone!R)
				// in general.
				_helper = takeNone(src);
			}
		}
	}

To allow both _helper=_src and _helper=takeNone(src) to work, one would have to make _helper a wrapper type that can be assigned both R and typeof(takeNone!R). Is this possible with the current implementation of takeNone? I glanced at the code briefly but couldn't tell for sure.


T

-- 
Marketing: the art of convincing people to pay for what they didn't need before which you can't deliver after.

On Thursday, December 20, 2012 14:35:15 H. S. Teoh wrote:
> On Thu, Dec 20, 2012 at 11:04:05PM +0100, Jonathan M Davis wrote:
> > But regardless, my point is that Range.init.empty must be true _for structs_. A struct range should be written such that its init value is empty. That's not true for classes, because they'll be null.
> > 
> > Your assertion should pass as long as the type of _current is a struct.
> 
> The problem with generic code is that you can't assume this. The type could be literally _anything_ (as long as it conforms to the range API). Unless you protect it with static ifs or something similar, of course.

Yes. That's why you use takeNone instead of the range's init property. And if you have to reassign the empty range to the original, then you'll need a template constraint which only accepts ranges which return the same type for takeNone.

> > If you want to get an empty range from an existing range, then use takeNone. If it returns the same type (which it tries to do but can't always do - e.g. with non-sliceable ranges which are classes or non-sliceable Voldemort types), then you can reassign it to the original. If it doesn't, then there's no generic way to get an empty range of the same type from that range other than calling popFront until it's empty (which is obviously ineffecient in the finite case and impossible in the infinite case).
> 
> [...]
> 
> Which is why I'm leaning towards rewriting algorithms so that they don't rely on ranges being emptiable. (Like you said, it's easy to have a range class that's infinite, in which case there is no empty state for ranges of that type at all -- .empty is an enum set to false.) I find that the code often becomes cleaner when written in a way that minimizes extraneous assumptions. It's harder to write, for sure, but I think it's more rewarding in the end.

It should be fairly rare that algorithms have to make a range empty. I've run into cases where it was outright required, but I don't think that std.algorithm has many such cases (if any), though it may have some places where it can take advantage of takeNone for optimizations where possible (e.g. find does that in one of its overloads).

> Anyway, coming back to takeNone: in many cases takeNone won't return the exact same type as the original range, so code like this won't work anymore:
> 
> auto myRangeFunc(R)(R range) {
> struct Wrapper {
> R _src;
> R _helper;
> 
> this(R src) {
> _src = src;
> ...
> 
> // Works:
> _helper = _src;
> ...
> 
> // Won't work: R != typeof(takeNone!R)
> // in general.
> _helper = takeNone(src);
> }
> }
> }
> 
> To allow both _helper=_src and _helper=takeNone(src) to work, one would have to make _helper a wrapper type that can be assigned both R and typeof(takeNone!R). Is this possible with the current implementation of takeNone? I glanced at the code briefly but couldn't tell for sure.

That would depend on the type of _helper. If takeNone can't return the same type, it'll return takeExactly(range, 0). So, if the type of _helper is assignable from takeExactly, then sure. Or, if UFCS is used, then _helper could have a takeNone function on it which was able to return an empty range of the same type.

In general though, code can't assume that takeNone returns the same type. It will have to test for it if it needs that. But there's no way around that unfortunately.

- Jonathan M Davis

On Thursday, 20 December 2012 at 21:10:24 UTC, H. S. Teoh wrote:
> But .init isn't merely used when you explicitly invoke it. It's the
> default value of struct fields, for example (see below).
>
>
> No we can't. For example:
>
> 	auto someRangeFunction(RoR)(RoR ror) {
> 		struct Helper {
> 			RoR _ror;
> 			ElementType!R _current;
>
> 			this(RoR r) {
> 				_ror = r;
> 				assert(_current.empty);
> 			}
> 		}
> 		return Helper(ror);
> 	}
>
> If RoR is an array of class objects, the assert line will segfault
> because _current.init is null. Conceptually speaking, I agree that a
> null object is an empty range, but in code, .empty is undefined because
> you can't invoke a method through a null reference.
>
>
> T

Note, assumption that structs and allocated classes at runtime are default in accordance with their T.init can be easily broken. Also they can default to different values across runtime of program.

import std.stdio;

class A { int x = 5; }

struct S { int x = 5; A a; }

struct Z { S s; }

void main()
{
	assert(S.init==S(5, null)); writeln(S.init); // S(5, null)
	A a = new A;
	assert(a.x != 5); writeln(a.x); // may pass and print anything
	S* s1 = new S;
	assert(s1.x != 5 && s1.a && s1.a.x != 5); //may pass
	writeln(s1.x, s1.a, s1.a.x); // may be anything
	S s2;
	assert(s2.x != 5 && s2.a && s2.a.x != 5); //also may pass
	writeln(s2.x, s2.a, s2.a.x); // may default to anything
	Z z;
	writeln(z); //also can have arbitrly values
}