Transience of .front in input vs. forward ranges

[H. S. Teoh]

On Tue, Nov 06, 2012 at 02:03:45AM +0100, Jonathan M Davis wrote:
[...]
> The only solutions that I see at this point are
> 
> 1. Exclude transience completely.
> 
> 2. Mark ranges as transient in some way and force algorithms to take
> this new trait into account.
> 
> 3. Insist that input ranges have transient fronts (save perhaps when
> it can be statically verified that they aren't based on front's type)
> and that anything requiring a non-transient front require forward
> ranges.
> 
> 4. Make all ranges non-transient but provide a way to get at a
> transient version of it and force algorithms to take this new property
> into account.
> 
> All 4 solutions have problems. They just have different problems.
[...]

Hmm. Another idea just occurred to me. The basic problem here is that we
are conflating two kinds of values, transient and persistent, under a
single name .front. What if we explicitly name them? Say, .copyFront for
the non-transient value and .refFront for the transient value (the
names are unimportant right now, let's consider the semantics of it).

Then an algorithm like std.array.array can be written something like
this:

	auto array(R)(R range) {
		auto a = appender!(ElementType!R)();
		while (!range.empty) {
			// Self-documenting: we expect to get a
			// persistent copy of the front value.
			a.put(range.copyFront);
			range.popFront();
		}
		return a.data;
	}

OTOH, an algorithm that is agnostic to transience, like find(), can be
written something like this:

	R find(R,S)(R haystack, S needle) {
		while (!haystack.empty) {
			// Self-documenting: we don't expect a
			// persistent front value.
			if (haystack.refFront == needle)
				return haystack;
			haystack.popFront();
		}
		return haystack;
	}

Of course, this immediately breaks many ranges, because they only have a
single .front currently. Which is bad. So we make use of UFCS:

	@property auto copyFront(R)(R range) {
		// Not sure how to do this yet, the idea is that
		// copyFront should be default.
		return range.front;
	}
	@property auto refFront(R)(R range) {
		// By default, .refFront is the same as copyFront.
		return range.copyFront;
	}

ByLine can then do this:

	struct ByLine {
		char[] buf;

		@property auto copyFront() {
			return buf.dup;
		}
		@property auto refFront() {
			return buf;
		}
	}

I haven't worked out all the details yet, but this is the gist of it.
While it's still not perfect, it is a slight improvement over the
.transient proposal in that no new range types are involved.

There is still the issue of naming: I chose .copyFront and .refFront
just for illustration purposes. I'm thinking probably we can make .front
== .copyFront, so that it will automatically work with (almost) all
current ranges, which should be non-transient. UFCS saves us from having
to implement .refFront for everything except actual transient ranges,
which should be only a few rare cases.

Of course, this has the disadvantage of needing to update existing
algorithms to use .refFront or .copyFront where appropriate -- but then,
we have to do that anyway if we're going to support transient ranges at
all.

Maybe somebody can improve on this idea?


T

-- 
Long, long ago, the ancient Chinese invented a device that lets them see through walls. It was called the "window".