www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Tricky semantics of ranges & potentially numerous Phobos bugs

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
In an effort to locate the suspected Phobos bug that I ran into in my
new Cartesian product implementation, I looked over the code for
std.algorithm joiner more carefully, and noticed the following:

Given a range of ranges ror, it assigns ror.front to a struct member and
then calls ror.popFront() immediately. Then as the user calls the joined
range's popFront, it successively pops its local copy of ror.front until
it's empty, whereupon it assigns the new ror.front to the local copy
again, and so on.

While this works for array of arrays, it *doesn't* work for ranges that
overwrite ror.front when ror.popFront() is called.  For example, it
wouldn't work for stdin.byLine(), because the underlying buffer it
reused. Here's the proof:

Code:
	// Filename: test2.d
	import std.algorithm;
	import std.stdio;
	void main() {
		auto lines = stdin.byLine();
		writeln(lines.joiner);
	}

Compile & test:

	# Compile
	dmd test2.d

	# Echo three lines, "abc", "def", and "ghi", and feed it to
	# the program.
	(echo abc; echo def; echo ghi) | ./test2

	# This is the output:
	defghighi

As you can see, the output is mangled, because byLine() has reused the
line buffer before joiner.Result got to it.

Long story short: saving a local copy of range.front and then calling
range.popFront() may _invalidate_ the copy. So basically, either you
need a forward range and use .save to keep track of old values of
range.front, or you have to refrain from calling popFront() until you're
well and truly done with the current value of .front. While not
respecting this will work with many common ranges, it will also fail in
subtle ways when given other ranges.

The scary thing is, I see similar code like this all over Phobos. Does
this mean that most of std.algorithm may need to be revised to address
this issue? At the very least, it would seem that a code audit is in
order to weed out this particular issue.

:-/


T

-- 
A linguistics professor was lecturing to his class one day. "In
English," he said, "A double negative forms a positive. In some
languages, though, such as Russian, a double negative is still a
negative. However, there is no language wherein a double positive can
form a negative."
A voice from the back of the room piped up, "Yeah, yeah."
Oct 15 2012
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Oct 16, 2012 at 07:28:38PM +0200, Jonathan M Davis wrote:
 On Tuesday, October 16, 2012 10:13:57 H. S. Teoh wrote:

[...]
 ByLine is perfectly valid range insofar as you realize that it's
 likely to go completely south if you use it in any way that could
 involve keeping front around after popFront has been called, which
 means that anything which relies on keeping front around isn't going
 to work. So, it's a range, but it's essentially an unsafe one (though
 I'm not sure that it's an un- safe one).
 
 So, it's fine that ByLine is a range as long as we're willing to put
 up with it not working with a lot of range-based functions because of
 its abnormal behavior. But I don't think that it's at all reasonable
 for range-based functions in general to not be able to rely on front
 returning the same type every time or on its value disappearing or
 becoming invalid in some way after a call to popFront. That's
 completely untenable IMHO.

I think a better solution is to somehow differentiate between ranges whose .front value is permanent (arrays), and ranges whose .front values are transient (e.g. byLine, but we shouldn't single it out because there are other occasions where you may *want* to have a range that doesn't call .dup every time -- say a range over all permutations of an array that modifies the array in-place). Perhaps mark ranges with an .isTransient property (which can be an enum so it doesn't waste any space), and range-based functions that require non-transient ranges will refuse to work with a transient range. Or alternatively, switch to a different implementation that takes transience into account (which may be slower, etc., but the important thing is to do it right -- after all, D's motto is safe by default, unsafe if you ask for it).
 Ranges _can_ define semantics which violate that, but they have to
 make it clear that they do so that programmers using them realize that
 they may not work right with a lot of range-based functions (which
 potentially makes it so that it they really shouldn't have been ranges
 in the first place).

I think this approach of what amounts to guessing which ranges are safe/unsafe with which functions is what's untenable. We all know that people don't read documentation, or at least, not thoroughly. Something like this is too easy to miss, and bugs will slip into code unnoticed for a long time, and then explode in your face. It's unsafe by default, which goes against D's philosophy. I think the problem is better addressed by an .isTransient property that can be selected by templates at compile-time. I agree that requiring *every* range function to expect .front to mutate upon calling .popFront() is unreasonable, but *some* functions *can* be written in a way that they will still work. Marking ranges with transient .front values will allow functions that *can* take transient ranges do so, while leaving other functions accepting only non-transient ranges. That way, if somebody tries to pass a transient range to a template that only works with a non-transient range, they will know at compile-time instead of getting a nasty surprise later on.
 So what is (or should be) the semantic design of ranges? Let's work
 out a precise definition so that we have something to build on.

As far as front (or back) goes, range-based functions should be able to rely on 1. front returning the exact same value on every call until popFront has been called (though there's no guarantee that front won't have to be recalculated on each call, so assigning the result of front to a local variable is advisable for efficiency if front must be used multiple times before a call to popFront). 2. the result of front continuing to be valid and unchanged after popFront has been called if it was assigned to a variable. Any range is free to violate this, but because range-based functions are free to rely on it, such ranges risk not working correctly with many range-based functions and must be used with caution.

[...] I don't like the idea that some ranges _may_ or _may not_ work with some functions. That's just too unreliable, and it's too easy to make mistakes. Let's put in an isTransient property on the unsafe ranges and let the templates' signature constraints enforce passing the right kind of range. On Tue, Oct 16, 2012 at 10:58:23AM -0700, David Gileadi wrote: [...]
 As a D dabbler, it seems wrong to me that a built-in range like
 byLine, which is often used in example code, should have weird side
 effects with the built-in methods in std.algorithm.  IMO this needs to
 be fixed one way or another, and a mere documentation change is likely
 not enough for casual D users.

I agree. We should add an isTransient property to at least the built-in ranges in Phobos, so that at least those ranges will always work properly (or complain loudly at compile-time if passed to the wrong function). User-defined ranges need to be marked too, but that is up to the user. I don't think this part can be statically checked (unless you want to enforce it using the type system by making non-transient ranges return immutable from .front -- but that may be impractical in some cases). So this has to be documented, and users will have the option of marking their own ranges and get the benefit of compile-time compatibility checks. But at the very least, the Phobos ranges must always work correctly, or refuse to work at compile-time. Leaving things up to convention (via documentation) is not a good idea. T -- ASCII stupid question, getty stupid ANSI.
Oct 16 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/16/12 3:07 PM, H. S. Teoh wrote:
 Perhaps mark ranges with an .isTransient property

isTransient!R is exactly the same thing as isInputRange!R && !isForwardRange!R. Andrei
Oct 17 2012
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 17 October 2012 at 17:15:14 UTC, Andrei
Alexandrescu wrote:
 On 10/16/12 3:07 PM, H. S. Teoh wrote:
 Perhaps mark ranges with an .isTransient property

isTransient!R is exactly the same thing as isInputRange!R && !isForwardRange!R. Andrei

Technically, (isTransient!R) is just a subset of (isInputRange!R && !isForwardRange!R) "byDChar" (if it existed), would be a perfectly valid non-transient input only range.
Oct 17 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/17/12 1:29 PM, monarch_dodra wrote:
 On Wednesday, 17 October 2012 at 17:15:14 UTC, Andrei
 Alexandrescu wrote:
 On 10/16/12 3:07 PM, H. S. Teoh wrote:
 Perhaps mark ranges with an .isTransient property

isTransient!R is exactly the same thing as isInputRange!R && !isForwardRange!R. Andrei

Technically, (isTransient!R) is just a subset of (isInputRange!R && !isForwardRange!R) "byDChar" (if it existed), would be a perfectly valid non-transient input only range.

Depends on implementation - popFront may actually wipe the character. Andrei
Oct 17 2012
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 17 October 2012 at 18:13:42 UTC, Andrei 
Alexandrescu wrote:
 On 10/17/12 1:29 PM, monarch_dodra wrote:
 On Wednesday, 17 October 2012 at 17:15:14 UTC, Andrei
 Alexandrescu wrote:
 On 10/16/12 3:07 PM, H. S. Teoh wrote:
 Perhaps mark ranges with an .isTransient property

isTransient!R is exactly the same thing as isInputRange!R && !isForwardRange!R. Andrei

Technically, (isTransient!R) is just a subset of (isInputRange!R && !isForwardRange!R) "byDChar" (if it existed), would be a perfectly valid non-transient input only range.

Depends on implementation - popFront may actually wipe the character. Andrei

"byDChar" (if it existed), *could* be a perfectly valid non-transient input only range, if the implementation returns the character by value. :)
Oct 17 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, October 17, 2012 13:15:12 Andrei Alexandrescu wrote:
 On 10/16/12 3:07 PM, H. S. Teoh wrote:
 Perhaps mark ranges with an .isTransient property

isTransient!R is exactly the same thing as isInputRange!R && !isForwardRange!R.

In what way? There is nothing anywhere that states that an input range's front could be invalidated upon a call to popFront. There's nothing inherent in the fact that range can't be saved that makes it so that front must be invalidated upon a call to popFront. You could easily define an input range of bytes over a file where front is perfectly valid after a call to popFront, because it's a value type. You could also define ByLine so that its front is perfectly valid after a call to popFront. It's just that it requires that a new buffer be allocated instead of reusing the buffer. That has nothing to do with the fact that its incapable of copying its state such that you could have multiple copies of it being iterated over separately. I don't see anything in the concept or definition of input ranges which implies that front would be invalidated by a call to popFront. I'm increasingly convinced that input ranges which are not forward ranges are useless for pretty much anything other than foreach. Far too much requires that you be able to save the current state - and most stuff _inherently_ requires it such that it's not simply a question of implementing the function differently. And adding even further restrictions on input ranges just makes it worse. It actually wouldn't hurt my feelings one whit if we got rid of the idea of input ranges entirely. It's perfectly possible to implement ranges like ByLine as forward ranges. It just requires a bit more work. But they'd be _way_ more useful if they were. In my experience the only time that you don't need to dup what ByLine or ByChunk gives you is when all you need is foreach, and if that's really the case, then opApply can be used for foreach, and ByLine and ByChunk can be defined in ways that actually allow them to not only not invalidate the result of previous front calls but to actually be full-on forward ranges, making them actually useful for things beyond foreach. Regardless, there's nothing in how input ranges are currently defined which indicates that front would ever be invalidated for _any_ type of range, and ByLine and ByChunk are pretty much the only ranges I've ever seen which invalidate previous calls to front. So, I don't see how you could think that they're anything but abnormal. And if you really want to argue that whether front can be invalidated or not is somehow part of the difference between an input range and a forward range, then the documentation on that needs to make that _very_ clear, and it's going to be that much worse to deal with input ranges which aren't forward ranges. - Jonathan M Davis
Oct 17 2012
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 17 October 2012 at 19:56:08 UTC, Jonathan M Davis 
wrote:
 [SNIP]
 I'm increasingly convinced that input ranges which are not 
 forward ranges are
 useless for pretty much anything other than foreach.
 [SNIP]
 - Jonathan M Davis

That's already a pretty big usage :) The thing is you just can't "do" anything with them, but that *is* the design. Just read them once to place them into another container. The fact they interface with, say "array", or "appender", or copy, makes the interface convenient. The fact that byLine will choke on a call to "array", IMO, has nothing to do with it being a forward range.
Oct 18 2012
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Oct 17, 2012 at 12:55:56PM -0700, Jonathan M Davis wrote:
[...]
 I'm increasingly convinced that input ranges which are not forward
 ranges are useless for pretty much anything other than foreach. Far
 too much requires that you be able to save the current state - and
 most stuff _inherently_ requires it such that it's not simply a
 question of implementing the function differently.

It's perfectly possible to implement joiner, chain, find, count, cmp, equal, until, filter, map, reduce, without assuming that the value returned by .front is persistent. Just to name a few. In fact, it's even possible to implement cartesianProduct in which one of the ranges is an input range. I'd hardly call that useless.
 And adding even further restrictions on input ranges just makes it
 worse. It actually wouldn't hurt my feelings one whit if we got rid of
 the idea of input ranges entirely.

The motivating example for input ranges, at least according to TDPL, is find(). There's nothing about find() that precludes non-forward input ranges. A lot would be missing from the usefulness of ranges if we were forced to only use forward ranges. [...]
 Regardless, there's nothing in how input ranges are currently defined
 which indicates that front would ever be invalidated for _any_ type of
 range, and ByLine and ByChunk are pretty much the only ranges I've
 ever seen which invalidate previous calls to front. So, I don't see
 how you could think that they're anything but abnormal.

I can think of quite a few situations in which it's useful to not assume that the return value of .front is persistent, which I've already mentioned before: in-place array permutation, reused buffers for complex computations, etc..
 And if you really want to argue that whether front can be invalidated
 or not is somehow part of the difference between an input range and a
 forward range, then the documentation on that needs to make that
 _very_ clear, and it's going to be that much worse to deal with input
 ranges which aren't forward ranges.

[...] I think I'm not so sure about Andrei's lumping input ranges with persistent return values from .front together with forward ranges. Some algorithms, like findAdjacent, do not need a forward range, but they do need a persistent .front. I do not like the idea of artificially limiting the scope of findAdjacent just because you can't assume input ranges' .front returns a persistent value. Like somebody else mentioned, whether .front is transient or not is orthogonal to whether the range is an input range or a forward range. There can be ranges whose .front is persistent, but they can't be forward ranges for practical reasons. T -- Having a smoking section in a restaurant is like having a peeing section in a swimming pool. -- Edward Burr
Oct 17 2012
parent reply Don Clugston <dac nospam.com> writes:
On 17/10/12 23:41, H. S. Teoh wrote:
 On Wed, Oct 17, 2012 at 12:55:56PM -0700, Jonathan M Davis wrote:
 [...]
 I'm increasingly convinced that input ranges which are not forward
 ranges are useless for pretty much anything other than foreach. Far
 too much requires that you be able to save the current state - and
 most stuff _inherently_ requires it such that it's not simply a
 question of implementing the function differently.

It's perfectly possible to implement joiner, chain, find, count, cmp, equal, until, filter, map, reduce, without assuming that the value returned by .front is persistent. Just to name a few. In fact, it's even possible to implement cartesianProduct in which one of the ranges is an input range. I'd hardly call that useless.
 And adding even further restrictions on input ranges just makes it
 worse. It actually wouldn't hurt my feelings one whit if we got rid of
 the idea of input ranges entirely.

The motivating example for input ranges, at least according to TDPL, is find(). There's nothing about find() that precludes non-forward input ranges. A lot would be missing from the usefulness of ranges if we were forced to only use forward ranges. [...]
 Regardless, there's nothing in how input ranges are currently defined
 which indicates that front would ever be invalidated for _any_ type of
 range, and ByLine and ByChunk are pretty much the only ranges I've
 ever seen which invalidate previous calls to front. So, I don't see
 how you could think that they're anything but abnormal.

I can think of quite a few situations in which it's useful to not assume that the return value of .front is persistent, which I've already mentioned before: in-place array permutation, reused buffers for complex computations, etc..
 And if you really want to argue that whether front can be invalidated
 or not is somehow part of the difference between an input range and a
 forward range, then the documentation on that needs to make that
 _very_ clear, and it's going to be that much worse to deal with input
 ranges which aren't forward ranges.

[...] I think I'm not so sure about Andrei's lumping input ranges with persistent return values from .front together with forward ranges. Some algorithms, like findAdjacent, do not need a forward range, but they do need a persistent .front. I do not like the idea of artificially limiting the scope of findAdjacent just because you can't assume input ranges' .front returns a persistent value. Like somebody else mentioned, whether .front is transient or not is orthogonal to whether the range is an input range or a forward range. There can be ranges whose .front is persistent, but they can't be forward ranges for practical reasons.

Is it actually orthogonal? Is it possible for a forward range to be transient? Or is it an intermediate concept? TransientInputRange -> NonTransientInputRange -> ForwardRange
Oct 18 2012
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 18 October 2012 at 07:09:04 UTC, Don Clugston wrote:
 On 17/10/12 23:41, H. S. Teoh wrote:

 Is it actually orthogonal? Is it possible for a forward range 
 to be transient?

 Or is it an intermediate concept?
 TransientInputRange -> NonTransientInputRange -> ForwardRange

Save just means the range can save its position. If it is returning via a buffer, Forward of not, it is going to be transient. Take this forward range, that returns the strings "A", "B" and "C" ad infinitum: //---- enum _ABC = "ABC"; struct ABC { char[1] buf = _ABC[0]; size_t i; enum empty = false; property char[] front(){return buf;} void popFront() { ++i; buf[0] = _ABC[i%3]; } property ABC save() { return this; } } //---- This is a perfectly valid range, which you can save, but the returned string is transient: //---- void main() { ABC abc; writeln("Printing 10 elements: "); abc.take(10).writeln('\n'); writeln("Duplicating range"); auto abc2 = abc.save; abc.popFront; foreach(v; zip(abc, abc2).take(5)) write("[", v[0], ", ", v[1], "]"); writeln('\n'); writeln("Prnting two consecutive elements:"); auto first = abc.front; abc.popFront(); auto second = abc.front; writeln("[", first, ", ", second, "]"); } //---- Produces: //---- Printing 10 elements: ["A", "B", "C", "A", "B", "C", "A", "B", "C", "A"] Duplicating range [B, A][C, B][A, C][B, A][C, B] Prnting two consecutive elements: [C, C] //---- As you can see, you can perfectly iterate. You can perfectly save the range. The saved range can be used to backtrack. But if you attempt to store two consecutive fronts, things don't go well. The same holds true for a Random Access range BTW. Iteration and transient-ness of returned value are orthogonal concepts
Oct 18 2012
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Oct 18, 2012 at 09:09:03AM +0200, Don Clugston wrote:
 On 17/10/12 23:41, H. S. Teoh wrote:

[...]
I think I'm not so sure about Andrei's lumping input ranges with
persistent return values from .front together with forward ranges.
Some algorithms, like findAdjacent, do not need a forward range, but
they do need a persistent .front. I do not like the idea of
artificially limiting the scope of findAdjacent just because you
can't assume input ranges' .front returns a persistent value. Like
somebody else mentioned, whether .front is transient or not is
orthogonal to whether the range is an input range or a forward range.
There can be ranges whose .front is persistent, but they can't be
forward ranges for practical reasons.

Is it actually orthogonal? Is it possible for a forward range to be transient?

[...] What about a range over all permutations of an array, that modifies the array in-place? It can be a forward range by having .save copy the current state of the array, but .front is transient nonetheless. T -- Life is too short to run proprietary software. -- Bdale Garbee
Oct 18 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/16/12 1:09 AM, H. S. Teoh wrote:
 The scary thing is, I see similar code like this all over Phobos. Does
 this mean that most of std.algorithm may need to be revised to address
 this issue? At the very least, it would seem that a code audit is in
 order to weed out this particular issue.

Such issues do happen, are relatively rare, and are virtually untested because there's been no unittests with a deliberately "bad" input range. Although of course we do need to add the appropriate fixes and unittests, I'm not worried about it at all systemically. Andrei
Oct 17 2012
parent reply "David Nadlinger" <see klickverbot.at> writes:
On Wednesday, 17 October 2012 at 15:14:44 UTC, Andrei 
Alexandrescu wrote:
 Such issues do happen, are relatively rare, and are virtually 
 untested because there's been no unittests with a deliberately 
 "bad" input range. Although of course we do need to add the 
 appropriate fixes and unittests, I'm not worried about it at 
 all systemically.

If an abstraction encourages use in a way which leads to hard-to-detect logic bugs that do not occur with the most common test cases, this is _exactly_ the thing we should be worried about! David
Oct 17 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/17/12 12:57 PM, David Nadlinger wrote:
 On Wednesday, 17 October 2012 at 15:14:44 UTC, Andrei Alexandrescu wrote:
 Such issues do happen, are relatively rare, and are virtually untested
 because there's been no unittests with a deliberately "bad" input
 range. Although of course we do need to add the appropriate fixes and
 unittests, I'm not worried about it at all systemically.

If an abstraction encourages use in a way which leads to hard-to-detect logic bugs that do not occur with the most common test cases, this is _exactly_ the thing we should be worried about!

When I designed input ranges vs. forward ranges there were long discussion on how to distinguish them. If you have a better design it would probably not influence the state of the affair, but it would be a good discussion to have. FWIW I can already think of a couple but all rely on UFCS. Andrei
Oct 17 2012