More tricky range semantics

[H. S. Teoh via Digitalmars-d]

Just noticed this little gotcha today: suppose we have a forward range
R, and an algorithm that wraps around R that looks something like this:

	struct WrapperRange {
		R src;
		bool stoppingCondition;
		this(R _src) {
			src = _src;
			stoppingCondition = someCondition(src.front);
		}
		@property bool empty() { return stoppingCondition; }
		@property auto front() { return src.front; }
		void popFront() {
			src.popFront();
			if (!src.empty && someCondition(src.front))
				stoppingCondition = true;
		}
		@property auto save() {
			typeof(this) copy = this;
			copy.src = src.save;
			return copy;
		}
	}

Basically, the wrapper iterates over R with some stopping condition that
may cause it to end earlier than the actual end of R.

Now consider this innocuous-looking code:

	unittest {
		R r = ... /* get an instance of R */;
		auto wrapper = WrapperRange(r);

		// check that the contents of wrapper is what we expect
		assert(wrapper.equal(expectedData));

		// erhm... check the contents of wrapper again, just to
		// be doubly sure?
		assert(wrapper.equal(expectedData)); // <-- line 10
	}

You may laugh at line 10, marked above... but don't be so quick to laugh
just yet. Consider now if R is a reference type. What would happen?
Let's trace the steps:

- The "R r = ..." line is nothing unexpected: since R is a by-reference
  type, r simply stores a reference to the actual instance of R. Nothing
  surprising.

- The "auto wrapper" line creates an instance of WrapperRange -- which
  is by-value, btw, this will become important later -- and assigns to
  .src the reference to that instance of R.

- The next line calls equal() on wrapper, to verify that its contents
  are what we're expecting. This passes a copy of wrapper to equal(),
  because wrapper is a by-value type. But since R is a reference type,
  as equal() iterates over the copy of wrapper, the underlying R range
  is being popped.

  This has 2 consequences:

  1) When equal() returns, the original copy of wrapper no longer points
  to the same place in r as before, because equal() has popped the
  underlying instance of R.

  2) Furthermore, since equal() iterates over the entire wrapped range,
  .stoppingCondition is now true. However, this only affected the local
  copy of wrapper in equal(). This means that after equal() returns, the
  unittest's original copy of wrapper is now in an inconsistent state:
  r has reached an element for which someCondition() is true, but this
  is not reflected in wrapper, which still thinks it's in the original
  position in r as before the call to equal().

As a result, the assert on line 10 will fail.

This situation is quite counterintuitive. One would expect that either:

(i) wrapper has value semantics, meaning that passing it to equal()
would not consume it; or,

(ii) wrapper has reference semantics, meaning that passing it to equal()
would empty it.

However, what actually happens is that wrapper is left in an
inconsistent state upon returning from equal() that is neither (i) nor
(ii). The kicker is that this resulted from code that followed the range
API to the letter. No hidden loophole in the range API was exploited. No
tricky hacks were used that might have caused problems.

So what's the moral of the story?

a) At least as things currently stand, passing (wrapper) ranges around
may exhibit "undefined" behaviour, like the above. Passing a range to a
function may invalidate it unless you use .save.  Therefore, one should
*always* use .save. (If we had passed wrapper.save to equal() instead,
this problem would not have happened.) This applies even if the wrapper
range is a by-value type. Or should we say, *especially* when it's a
by-value type?

b) One may argue that WrapperRange ought to .save the underlying range
in its postblit... but what if the only thing we wanted to do was to
call equal() on wrapper and nothing else? In that case, we'd be
incurring needless overhead of .save'ing the range when we didn't care
whether it got consumed.

c) This issue is already latent in almost *all* Phobos algorithms.  We
only haven't discovered it yet because most people just use arrays for
ranges. But all it takes is for somebody to start using
std.range.inputRangeObject (and there are cases where this is
necessary), and this problem will surface.  Anytime you mix by-value and
by-reference ranges, be ready for problems of this sort to arise.


Yep, range semantics just got even trickier. (And we thought transient
ranges were bad...)


T

-- 
"Computer Science is no more about computers than astronomy is about telescopes." -- E.W. Dijkstra