www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - More tricky range semantics

reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
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
Jan 15 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/15/15 12:53 PM, H. S. Teoh via Digitalmars-d wrote:

 Passing a range to a
 function may invalidate it unless you use .save.  Therefore, one should
 *always*  use .save.


That's right. To simplify the problem space we might decree that forward 
(or better) ranges with reference semantics are not allowed. -- Andrei
Jan 15 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Jan 15, 2015 at 03:24:29PM -0800, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 1/15/15 12:53 PM, H. S. Teoh via Digitalmars-d wrote:

Passing a range to a function may invalidate it unless you use .save.
Therefore, one should *always*  use .save.


 
 That's right. To simplify the problem space we might decree that
 forward (or better) ranges with reference semantics are not allowed.
 -- Andrei


That's not workable. It instantly makes InputRangeObject useless.

InputRangeObject is required in situations where run-time polymorphism
of ranges is needed, for example, if a particular function must return
one of multiple possible range types depending on a runtime parameter.
Simple example:

	auto wrapMyRange(R)(R range) {
		if (someRuntimeCondition) {
			return range.map!(a => a*2);
		} else {
			return range.map!(a => a*2 + 1)
				    .filter!(a > 10);
		}
	}

This code doesn't compile, of course, because the return types of map()
and filter() are incompatible. The only current way to make it work is
to wrap the return value in an InputRangeObject:

	auto wrapMyRange(R)(R range) {
		if (someRuntimeCondition) {
			return inputRangeObject(range.map!(a => a*2));
		} else {
			return inputRangeObject(range.map!(a => a*2 + 1)
				.filter!(a > 10));
		}
	}

This works because inputRangeObject returns an instance of a subclass of
InputRangeObject, which serves as the common return type. The concrete
type is specialized for the actual type being wrapped; in this case
either the return type of map(), or the return type of filter(). Note
that methods like .save, .popBack, etc., are forwarded, so the returned
range retains forward or higher range functionality. This is, of course,
necessary, since otherwise you couldn't do anything with the returned
wrapped range except iterate over it once.

Forcing reference type ranges to be non-forward completely breaks this
important use case. The only way to work around it would be to wrap the
class object in a struct wrapper that calls .save in its postblit --
which introduces a prohibitive performance overhead.


T

-- 
Let's not fight disease by killing the patient. -- Sean 'Shaleh' Perry
Jan 15 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/15/15 4:46 PM, H. S. Teoh via Digitalmars-d wrote:

 On Thu, Jan 15, 2015 at 03:24:29PM -0800, Andrei Alexandrescu via
Digitalmars-d wrote:

 On 1/15/15 12:53 PM, H. S. Teoh via Digitalmars-d wrote:

 Passing a range to a function may invalidate it unless you use .save.
 Therefore, one should *always*  use .save.


 That's right. To simplify the problem space we might decree that
 forward (or better) ranges with reference semantics are not allowed.
 -- Andrei


 That's not workable. It instantly makes InputRangeObject useless.


Indeed. That said we could achieve polymorphism with value objects; it's 
just more complicated. I agree it's a tricky matter. -- Andrei
Jan 15 2015
prev sibling next sibling parent reply Joseph Rushton Wakeling via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 16/01/15 00:24, Andrei Alexandrescu via Digitalmars-d wrote:

 That's right. To simplify the problem space we might decree that forward (or
 better) ranges with reference semantics are not allowed. -- Andrei


That would seem to place significant restrictions on the ability to define 
effective random number generators and related functionality ... ?
Jan 15 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/15/15 4:58 PM, Joseph Rushton Wakeling via Digitalmars-d wrote:

 On 16/01/15 00:24, Andrei Alexandrescu via Digitalmars-d wrote:

 That's right. To simplify the problem space we might decree that
 forward (or
 better) ranges with reference semantics are not allowed. -- Andrei


 That would seem to place significant restrictions on the ability to
 define effective random number generators and related functionality ... ?


Agreed. Pseudo-random generators are an interesting kind of range 
because they are forward yet do not iterate a "real" container. -- Andrei
Jan 15 2015
next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Jan 15, 2015 at 05:52:45PM -0800, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 1/15/15 4:58 PM, Joseph Rushton Wakeling via Digitalmars-d wrote:

On 16/01/15 00:24, Andrei Alexandrescu via Digitalmars-d wrote:

That's right. To simplify the problem space we might decree that
forward (or better) ranges with reference semantics are not allowed.
-- Andrei


That would seem to place significant restrictions on the ability to
define effective random number generators and related functionality
... ?


 
 Agreed. Pseudo-random generators are an interesting kind of range
 because they are forward yet do not iterate a "real" container. --
 Andrei


I've been wondering about that. Must ranges have an "underlying"
container? Or are they allowed to be more abstract entities that
basically function as generators, producing data on demand? (This
distinction is also somewhat related to transient ranges, in that the
difference between providing a "view" of some static underlying data vs.
computing something on-the-fly in a buffer that gets reused, could serve
as a deciding factor on how to deal with transient ranges.)

My feeling is that allowing the latter is much more powerful, and more
encompassing. Constructs like iota() and recurrence() belong to the
latter category, for example, and they do provide forward range like
functionality -- or they *could*, if they don't already, as it would be
trivial to implement. Allowing generating functions to be ranges also
allows one to plug in programmatic data generators as data sources in
UFCS chains, without needing to deal with an artificial distinction
between "view of underlying data" ranges and "generated-on-the-fly"
ranges.

In this sense, an RNG could be thought of as a complex variant of
recurrence(), except with a far more complicated generating expression
than what one would normally use with recurrence(). If recurrence()
qualifies as a range (and a forward range, no less), then an RNG ought
to qualify too.


T

-- 
Those who don't understand Unix are condemned to reinvent it, poorly.
Jan 15 2015
prev sibling parent Joseph Rushton Wakeling via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 16/01/15 07:38, H. S. Teoh via Digitalmars-d wrote:

 I've been wondering about that. Must ranges have an "underlying"
 container? Or are they allowed to be more abstract entities that
 basically function as generators, producing data on demand? (This
 distinction is also somewhat related to transient ranges, in that the
 difference between providing a "view" of some static underlying data vs.
 computing something on-the-fly in a buffer that gets reused, could serve
 as a deciding factor on how to deal with transient ranges.)


This is almost a surprising question for me, because I've taken it for granted 
for so long that one of the most powerful tools they offer is lazily-generated 
data that is not based on underlying storage.  The examples you cite (iota, 
recurrence) are good examples, RNGs are another.


 In this sense, an RNG could be thought of as a complex variant of
 recurrence(), except with a far more complicated generating expression
 than what one would normally use with recurrence(). If recurrence()
 qualifies as a range (and a forward range, no less), then an RNG ought
 to qualify too.


Yes, theoretically you can envision a pseudo-RNG as being defined by a state 
variable, and a pure function that transforms this into a new state variable. 
And then those individual states can be mapped to the individual variates in 
different ways, depending on the type of variate you want to generate.

The practical range implementation obfuscates this a bit (helpfully) by 
encapsulating the state (which in practice we update via mutation), and 
implementing a particular state-to-random-variate method in .front, resulting
in 
the desired effect of a range whose elements are the individual random variates 
you care about.
Jan 16 2015
prev sibling parent reply "Dicebot" <public dicebot.lv> writes:
On Friday, 16 January 2015 at 00:58:34 UTC, Joseph Rushton 
Wakeling via Digitalmars-d wrote:

 On 16/01/15 00:24, Andrei Alexandrescu via Digitalmars-d wrote:

 That's right. To simplify the problem space we might decree 
 that forward (or
 better) ranges with reference semantics are not allowed. -- 
 Andrei


 That would seem to place significant restrictions on the 
 ability to define effective random number generators and 
 related functionality ... ?


Why RNG would be a forward range as opposed to just input range?
Jan 16 2015
parent reply "Dicebot" <public dicebot.lv> writes:
On Friday, 16 January 2015 at 14:58:09 UTC, Dicebot wrote:

 On Friday, 16 January 2015 at 00:58:34 UTC, Joseph Rushton 
 Wakeling via Digitalmars-d wrote:

 On 16/01/15 00:24, Andrei Alexandrescu via Digitalmars-d wrote:

 That's right. To simplify the problem space we might decree 
 that forward (or
 better) ranges with reference semantics are not allowed. -- 
 Andrei


 That would seem to place significant restrictions on the 
 ability to define effective random number generators and 
 related functionality ... ?


 Why RNG would be a forward range as opposed to just input range?


To specify : the way I see it you either want PRNG to be a 
forward range and that fits with value semantics. Or you want 
reference semantics and it naturally becomes input range.
Jan 16 2015
parent reply "Joseph Rushton Wakeling" <joseph.wakeling sociomantic.com> writes:
On Friday, 16 January 2015 at 14:59:10 UTC, Dicebot wrote:

 To specify : the way I see it you either want PRNG to be a 
 forward range and that fits with value semantics. Or you want 
 reference semantics and it naturally becomes input range.


Here's the problem with value semantics.  This is a real problem 
with actual Phobos code right now.

////////////////////////////////////////////////////
import std.random, std.range, std.stdio;

void main()
{
     // Create RNG instance with unpredictable seed
     auto rng = Random(unpredictableSeed);

     // Generate sample of 3 numbers from sequence
     // 0, 1, ..., 9 using rng as source of randomness
     // and write to console
     iota(0, 10).randomSample(3, rng).writeln;

     // Do again.  We'd expect a different result
     // but actually we get just the same
     iota(0, 10).randomSample(3, rng).writeln;
}
////////////////////////////////////////////////////

Note that because randomSample generated a wrapper range 
(RandomSample), we can't simply pass the RNG by ref.  It's copied 
(and because RNGs are currently value types, it's copied by 
value).

Note also that the above is a problem whether or not Random is a 
forward or input range.

What's needed here is for the source of randomness to be updated 
whenever it's used, so that you don't get unintended correlations 
like this.  Reference types give this, but it shouldn't be 
necessary to interfere with the forward-range status of the RNG, 
which depends entirely on whether it's a deterministic pseudo-RNG 
or not.

Conversely, suppose that we have some function that takes a 
forward range as input and uses the ability to repeat the 
sequence.  Here's a naive example:

void foo (FRange) (FRange range)
     if (isForwardRange!FRange)
{
     foreach (i; 0 .. 10)
     {
         // silly example :-P
         auto r = range.save;
         r.take(10).writeln;
     }
}

This is a problematic design if FRange is a reference type, 
because (by design) if the values in it are used, they should be 
consumed.  So e.g. if you were passing a reference-type RNG to a 
function that does this, you'd like to guarantee that (i) the 
function is able to use the ability to repeat the sequence, but 
(ii) consumes from the original exactly once.

If you don't get that, you will wind up with unintended 
correlations in your use of random numbers.
Jan 16 2015
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Friday, 16 January 2015 at 16:12:23 UTC, Joseph Rushton 
Wakeling wrote:

 void foo (FRange) (FRange range)
     if (isForwardRange!FRange)
 {
     foreach (i; 0 .. 10)
     {
         // silly example :-P
         auto r = range.save;
         r.take(10).writeln;
     }
 }

 This is a problematic design if FRange is a reference type, 
 because (by design) if the values in it are used, they should 
 be consumed.  So e.g. if you were passing a reference-type RNG 
 to a function that does this, you'd like to guarantee that (i) 
 the function is able to use the ability to repeat the sequence, 
 but (ii) consumes from the original exactly once.

 If you don't get that, you will wind up with unintended 
 correlations in your use of random numbers.


While the first example is indeed problematic, this one actually 
is not. If this does not print the same 10 numbers every time, 
your save method is wrong.
Regardless of being a reference type or not it has to clone the 
RNG state or it doesn't do its job.
Jan 16 2015
parent reply "Joseph Rushton Wakeling" <joseph.wakeling sociomantic.com> writes:
On Friday, 16 January 2015 at 17:09:47 UTC, Tobias Pankrath wrote:

 While the first example is indeed problematic, this one 
 actually is not. If this does not print the same 10 numbers 
 every time, your save method is wrong.
 Regardless of being a reference type or not it has to clone the 
 RNG state or it doesn't do its job.


I think you've misunderstood what I was getting at, probably 
because I didn't explain myself well.

Obviously it's correct that the second function example should 
print out the same thing 10 times.  However, what is wrong is 
that at the end of that function, the source range -- if a 
reference type -- should itself have been popFront'ed a 
sufficient number of times, but it hasn't been.

That's a design fault in the function implementation, which 
doesn't take into account the desirable behaviour (for the 
caller) if the range given to the function is a reference type.
Jan 16 2015
next sibling parent "Joseph Rushton Wakeling" <joseph.wakeling sociomantic.com> writes:
On Friday, 16 January 2015 at 17:13:33 UTC, Joseph Rushton 
Wakeling wrote:

 I think you've misunderstood what I was getting at, probably 
 because I didn't explain myself well.


There's a concrete example of the problem I can demonstrate from 
some Phobos functionality, but off the top of my head I can't 
remember what it is.  I'll try and look it up when I get home 
later this evening.

The essence is that, as a caller, I have this problem:

     auto range = SomeReferenceTypeForwardRange(whatever);

     foo(range); // prints one set of 10 values

     foo(range); // should print different set of 10 values
                 // but won't because foo()'s implementation
                 // doesn't take into account possibility of
                 // reference type input
Jan 16 2015
prev sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Friday, 16 January 2015 at 17:13:33 UTC, Joseph Rushton 
Wakeling wrote:

 On Friday, 16 January 2015 at 17:09:47 UTC, Tobias Pankrath 
 wrote:

 While the first example is indeed problematic, this one 
 actually is not. If this does not print the same 10 numbers 
 every time, your save method is wrong.
 Regardless of being a reference type or not it has to clone 
 the RNG state or it doesn't do its job.


 I think you've misunderstood what I was getting at, probably 
 because I didn't explain myself well.

 Obviously it's correct that the second function example should 
 print out the same thing 10 times.  However, what is wrong is 
 that at the end of that function, the source range -- if a 
 reference type -- should itself have been popFront'ed a 
 sufficient number of times, but it hasn't been.

 That's a design fault in the function implementation, which 
 doesn't take into account the desirable behaviour (for the 
 caller) if the range given to the function is a reference type.


Ah, now I understand you. Since copy-construction is undefined 
for ForwardRanges, you cannot guarantee this. Things would be 
better, if we had required that this(this) does the same as .save 
or must be  disabled.

Than it would be clear that you either had to use a reference or 
a pointer as argument to the function.
Jan 16 2015
parent reply "Joseph Rushton Wakeling" <joseph.wakeling sociomantic.com> writes:
On Friday, 16 January 2015 at 17:22:42 UTC, Tobias Pankrath wrote:

 Ah, now I understand you. Since copy-construction is undefined 
 for ForwardRanges, you cannot guarantee this. Things would be 
 better, if we had required that this(this) does the same as 
 .save or must be  disabled.


I'm not sure I follow what you mean by this ... ?


 Than it would be clear that you either had to use a reference 
 or a pointer as argument to the function.


I don't see how that would affect the undesirable behaviour of 
the implementation.
Jan 16 2015
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Friday, 16 January 2015 at 18:12:03 UTC, Joseph Rushton 
Wakeling wrote:

 On Friday, 16 January 2015 at 17:22:42 UTC, Tobias Pankrath 
 wrote:

 Ah, now I understand you. Since copy-construction is undefined 
 for ForwardRanges, you cannot guarantee this. Things would be 
 better, if we had required that this(this) does the same as 
 .save or must be  disabled.


 I'm not sure I follow what you mean by this ... ?


If you pass a forward range of type T (something that passes 
isForwardRange!T) to a function you have no guarantees on what 
will happen. It could be:

     • compilation failure
     • reference semantics (changes are reflected outside the 
function
     • value semantics (no change are reflected outside the 
function)

The implementer of the range can choose one. Although I tried it 
now, and  disable this(this) does prevent isForwardRange!T to 
pass. I don't know if that changed recently or is just out of 
line with the documentation/specification.
Jan 16 2015
parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Jan 16, 2015 at 06:34:08PM +0000, Tobias Pankrath via Digitalmars-d
wrote:

 On Friday, 16 January 2015 at 18:12:03 UTC, Joseph Rushton Wakeling wrote:

On Friday, 16 January 2015 at 17:22:42 UTC, Tobias Pankrath wrote:

Ah, now I understand you. Since copy-construction is undefined for
ForwardRanges, you cannot guarantee this. Things would be better, if
we had required that this(this) does the same as .save or must be
 disabled.


I'm not sure I follow what you mean by this ... ?


 
 If you pass a forward range of type T (something that passes
 isForwardRange!T) to a function you have no guarantees on what will
 happen.  It could be:
 
     • compilation failure
     • reference semantics (changes are reflected outside the function
     • value semantics (no change are reflected outside the function)


* The range is left in an inconsistent state. :-)



 The implementer of the range can choose one. Although I tried it now,
 and  disable this(this) does prevent isForwardRange!T to pass. I don't
 know if that changed recently or is just out of line with the
 documentation/specification.


IIRC, this is because the test checks if it's possible to assign the
range to a local variable. This is quite widely used in Phobos;  disable
this(this) would make the range unusable with a *lot* of Phobos
algorithms. In fact, pretty much *all* wrapper algorithms that have to
assign the range to a field in the wrapper range.

Besides, I think this approach doesn't really address the root of the
problem, which is that the semantics of assigning a range (without using
.save) is not specified by the range API. Yet code like `auto r =
range;` is used all over the place in Phobos code, with various hidden
assumptions about what '=' does, which may or may not correspond with
reality.

Ultimately, this is also the root cause of the transient range problem:
the range API did not specify the semantics of `auto x = range.front;`.
It's simply assumed that this copies the value of range.front... which,
in a sense, it does, but what's hidden behind the '=' can be very
complex semantics that breaks the algorithm's assumptions. In this case,
it breaks because when range.front is a reference to a buffer reused by
popFront, this causes the unexpected result that calling popFront also
changes x. Had the range API specified the expected behaviour of
assigning .front to a variable, this problem would not have arisen, or
at least the possible problems would have been anticipated, instead of
transience coming to bite us from behind when we least expect it.


T

-- 
I think the conspiracy theorists are out to get us...
Jan 16 2015
prev sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Jan 16, 2015 at 01:58:15AM +0100, Joseph Rushton Wakeling via
Digitalmars-d wrote:

 On 16/01/15 00:24, Andrei Alexandrescu via Digitalmars-d wrote:

That's right. To simplify the problem space we might decree that
forward (or better) ranges with reference semantics are not allowed.
-- Andrei


 
 That would seem to place significant restrictions on the ability to
 define effective random number generators and related functionality
 ... ?


Not to mention, I just realized that while the example I used relied on
the interaction between reference and value types, a similar problem
exists with just value types alone. Using the same wrapper range I
posted, suppose now that R is not a reference type range, but an input
(non-forward) range, and that .save is not implemented. Then consider
this code:

	unittest {
		auto r = R(...);
		auto wrapped = WrapperRange(r);

		assert(wrapped.equal(expectedData));
		bool b = wrapped.empty;
	}

Quiz: what's the value of b?

.

.

.

Go on, guess. :-)

.

.

.

Yup, b == false. Now guess what happens if you then access
wrapped.front?

Well, that depends. If someCondition became true before r was exhausted,
then wrapped.front would return a value that shouldn't be in the wrapped
range, because it breaks the invariant that WrapperRange is supposed to
stop when someCondition becomes true. However, if someCondition didn't
become true and r was exhausted, accessing wrapped.front will call
.front on an empty input range, which is UB. If you're lucky, you'll hit
an assert; otherwise, anything could happen, like dereferencing a
dangling pointer, reading invalid memory, etc..

So actually, my previous statement was not broad enough: this problem
happens not just with reference type ranges; it happens with
non-reference input ranges too!


T

-- 
If it breaks, you get to keep both pieces. -- Software disclaimer notice
Jan 15 2015
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/15/15 12:53 PM, H. S. Teoh via Digitalmars-d wrote:

 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.


There's a distinction here. Input non-forward ranges can be considered 
"reference" because popFront()ing any copy is tantamount to 
popFront()int any other copy. -- Andrei
Jan 15 2015
parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Jan 15, 2015 at 03:25:38PM -0800, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 1/15/15 12:53 PM, H. S. Teoh via Digitalmars-d wrote:

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.


 
 There's a distinction here. Input non-forward ranges can be considered
 "reference" because popFront()ing any copy is tantamount to
 popFront()int any other copy. -- Andrei


I hope you realize that inputRangeObject, in spite of its name, does
forward methods of the higher ranges (.save, .popBack, etc.), right?

Besides, conflating reference types with non-forward input ranges will
cripple ranges built not only from class objects, but from *any* type
(even structs) that exhibit reference semantics. One particular poignant
example is your proposed groupBy replacement, which uses RefCounted,
which has reference semantics. :-) We wouldn't want to be breaking that
now, would we?

(On the flip side, perhaps now you might finally see some justification
for my hesitation about implementing groupBy with reference
semantics...)


T

-- 
Let's eat some disquits while we format the biskettes.
Jan 15 2015
prev sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
 Yep, range semantics just got even trickier. (And we thought 
 transient
 ranges were bad...)


 T


This is related: https://issues.dlang.org/show_bug.cgi?id=11951
Jan 16 2015