Tricky semantics of ranges & potentially numerous Phobos bugs

[Jonathan M Davis]

On Tuesday, October 16, 2012 06:30:53 H. S. Teoh wrote:
> On Mon, Oct 15, 2012 at 10:59:26PM -0700, Jonathan M Davis wrote:
> > On Monday, October 15, 2012 22:48:15 Jonathan M Davis wrote:
> > > So, I don't really know what the right answer is, but I _really_
> > > don't like the idea of having to worry about the result of front
> > > changing after a call to popFront in every single function that ever
> > > uses front. In the general case, I just don't see how that's
> > > tenable. I'd _much_ rather that it be up to the programmer using
> > > abnormal ranges such as ByLine to use them correctly.
> > 
> > And actually, it seems to me that issues like this make it look like
> > it was a mistake to make ranges like ByLine ranges in the first place.
> > They should have just defined opApply so that they'd work nicely in
> > foreach but not with range- based functions. They're clearly not going
> > to work with a _lot_ of range-based functions.
> 
> [...]
> 
> But nothing about the definition of a range, as currently defined in
> std.range, guarantees that whatever value was returned by .front is
> still valid after popFront() is called.
> 
> I'm not saying that this should be the "correct" behaviour, but the
> current definition does not prohibit a range from, say, reusing an array
> to compute its next element. For example, one may have a range that
> returns the permutations of a given array, in which popFront() permutes
> the elements in-place. In this case, .front will become invalid once
> popFront() is called. Many of the current range-based functions will not
> work correctly in this case.
> 
> Of course, it's arguable whether such ranges should be admissible, but
> as far as the current definition goes, I don't see anything that states
> otherwise. If we don't make such things clear, then we're bound to run
> into pathological cases where bugs will creep in because of unstated
> assumptions in the code.

There's only so much that the compiler can check for you. Sure, we could say 
in the docs that front must still be valid after a call to popFront (and 
perhaps we should), but there's no way to validate that.

There's also no way to validate that front always returns the same value, or 
that popFront actually pops a value, or that it pops only one value, etc. 
Pretty much _all_ that we can verify with template constraints is function 
signatures. So, we can _never_ fully restrict range types to exactly what 
would be considered correct.

So, if we have expectations about how ranges should/must work, then that 
should be in the docs somewhere, but the definition of a range from the 
compiler's perspective can only ever be defined by eponymous templates which 
can't possibly verify correct behavior, meaning that something like ByLine 
will always be permitted even if it doesn't work, because it breaks the 
semantic design of ranges.

- Jonathan M Davis