On Tuesday, October 16, 2012 06:40:54 H. S. Teoh wrote:
> Notice in the second output range, that the third element is [20, 203] instead of [100, 203], and thereafter a bunch of elements are skipped, and things just start going haywire after that.
> 
> The only difference between the two is that the first is computed within main(), and the second is returned from a function call. Does this mean that it's unsafe to return composed ranges from functions?

No. I don't know what's going on, but it sounds like there's a bug somewhere.

> I'm trying to
> think what might be going wrong. Could it be that the composed ranges
> are stack-allocated temporaries that go out of scope upon returning from
> the function, so the returned range is actually accessing invalid
> memory? (That is a really scary thought.)

If you have a range over static array, then yes, you will have serious issues if you return a range over it, because the data is going away, but that's not going to happen with a struct or class. The class would be safely on the heap, and the struct will get appropriately copied. But one area that could get hairy if dmd is buggy is if you're using delegates which access the stack frame. It's supposed to work just fine, but it requires that a closure be allocated so that the state of the stack frame is saved (and is therefore valid after the function call has completed). So, things could definitely go funny if there are any bugs in there.

I have no idea what's going wrong for you here (I'd have to spend time studying exactly what your code is doing), but there's either a bug in your code or a compiler bug which is causing you problems, because aside from slices of static arrays, it's perfectly safe to return stack-allocated stuff functions - including several layers of ranges.

- Jonathan M Davis

On Tuesday, 16 October 2012 at 17:17:36 UTC, Jonathan M Davis
wrote:
> On Tuesday, October 16, 2012 06:40:54 H. S. Teoh wrote:
>> Notice in the second output range, that the third element is [20, 203]
>> instead of [100, 203], and thereafter a bunch of elements are skipped,
>> and things just start going haywire after that.
>> 
>> The only difference between the two is that the first is computed within
>> main(), and the second is returned from a function call. Does this mean
>> that it's unsafe to return composed ranges from functions?
>
> No. I don't know what's going on, but it sounds like there's a bug somewhere.
>
>> I'm trying to
>> think what might be going wrong. Could it be that the composed ranges
>> are stack-allocated temporaries that go out of scope upon returning from
>> the function, so the returned range is actually accessing invalid
>> memory? (That is a really scary thought.)
>
> If you have a range over static array, then yes, you will have serious issues
> if you return a range over it, because the data is going away, but that's not
> going to happen with a struct or class. The class would be safely on the heap,
> and the struct will get appropriately copied. But one area that could get
> hairy if dmd is buggy is if you're using delegates which access the stack
> frame. It's supposed to work just fine, but it requires that a closure be
> allocated so that the state of the stack frame is saved (and is therefore
> valid after the function call has completed). So, things could definitely go
> funny if there are any bugs in there.
>
> I have no idea what's going wrong for you here (I'd have to spend time
> studying exactly what your code is doing), but there's either a bug in your
> code or a compiler bug which is causing you problems, because aside from
> slices of static arrays, it's perfectly safe to return stack-allocated stuff
> functions - including several layers of ranges.
>
> - Jonathan M Davis

No idea either, but I'll volunteer to investigate ;)

I agree with Jonathan though, sounds like a bug somewhere. There
is no reason for your code to fail.

I'll post back if I find anything.

On Tue, Oct 16, 2012 at 08:44:56PM +0200, monarch_dodra wrote:
> On Tuesday, 16 October 2012 at 17:17:36 UTC, Jonathan M Davis wrote:
> >On Tuesday, October 16, 2012 06:40:54 H. S. Teoh wrote:
> >>Notice in the second output range, that the third element is [20, 203] instead of [100, 203], and thereafter a bunch of elements are skipped, and things just start going haywire after that.
> >>
> >>The only difference between the two is that the first is computed within main(), and the second is returned from a function call. Does this mean that it's unsafe to return composed ranges from functions?
> >
> >No. I don't know what's going on, but it sounds like there's a bug somewhere.
> >
> >>I'm trying to think what might be going wrong. Could it be that the composed ranges are stack-allocated temporaries that go out of scope upon returning from the function, so the returned range is actually accessing invalid memory? (That is a really scary thought.)
> >
> >If you have a range over static array, then yes, you will have serious issues if you return a range over it, because the data is going away, but that's not going to happen with a struct or class. The class would be safely on the heap, and the struct will get appropriately copied. But one area that could get hairy if dmd is buggy is if you're using delegates which access the stack frame. It's supposed to work just fine, but it requires that a closure be allocated so that the state of the stack frame is saved (and is therefore valid after the function call has completed). So, things could definitely go funny if there are any bugs in there.

Hmm. There *is* a delegate being passed to map(). Would that cause problems? Theoretically it shouldn't, but as you said, if dmd isn't handling it correctly that could cause problems.


> >I have no idea what's going wrong for you here (I'd have to spend time studying exactly what your code is doing), but there's either a bug in your code or a compiler bug which is causing you problems, because aside from slices of static arrays, it's perfectly safe to return stack-allocated stuff functions - including several layers of ranges.

I'm at a loss as to where the bug in my code could be, since I have two identical copies of the same code, one works, and the other doesn't, and the only difference between them is that one is returning a range from a separate function.


[...]
> No idea either, but I'll volunteer to investigate ;)
> 
> I agree with Jonathan though, sounds like a bug somewhere. There is no reason for your code to fail.
> 
> I'll post back if I find anything.

Thanks! This problem has been bugging me (har har) all through last
night and this morning.


T

-- 
"Real programmers can write assembly code in any language. :-)" -- Larry Wall

On Tue, Oct 16, 2012 at 08:44:56PM +0200, monarch_dodra wrote: [...]
> No idea either, but I'll volunteer to investigate ;)
> 
> I agree with Jonathan though, sounds like a bug somewhere. There is no reason for your code to fail.
> 
> I'll post back if I find anything.

Another data point: if I move the .joiner call out of cprod() into
main(), then there is no problem. Could it be that something in joiner
is breaking somehow, when returned from a function?


T

-- 
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.

> Hmm. There *is* a delegate being passed to map(). Would that cause
> problems? Theoretically it shouldn't, but as you said, if dmd isn't
> handling it correctly that could cause problems.

I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8) and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it should be if the memory for the variables that the delegate uses was allocated on the heap?

On Tuesday, October 16, 2012 12:15:01 H. S. Teoh wrote:
> I'm at a loss as to where the bug in my code could be, since I have two identical copies of the same code, one works, and the other doesn't, and the only difference between them is that one is returning a range from a separate function.

You'd probably have to reduce your code piece by piece until it starts acting the same in both cases and then try and determine the smallest example possible using that. Then it could become fairly clear whether it's a library bug or a compiler bug. But narrowing it down is likely to be rather unpleasant regardless.

- Jonathan M Davis

On Tuesday, 16 October 2012 at 19:31:18 UTC, H. S. Teoh wrote:
> On Tue, Oct 16, 2012 at 08:44:56PM +0200, monarch_dodra wrote:
> [...]
>> No idea either, but I'll volunteer to investigate ;)
>> 
>> I agree with Jonathan though, sounds like a bug somewhere. There
>> is no reason for your code to fail.
>> 
>> I'll post back if I find anything.
>
> Another data point: if I move the .joiner call out of cprod() into
> main(), then there is no problem. Could it be that something in joiner
> is breaking somehow, when returned from a function?
>
>
> T

I don't know, but if I change the code to this:

auto cprod(R1,R2)(R1 A, R2 B) {
    // This part is exactly the same as in main(), below. So
    // in theory, it should work exactly the same way.
    auto mapper = (typeof(tuple(cast(size_t) 0, A.front, B.front)) a) => chain(
                    zip(repeat(a[1]), B.save.take(a[0])),
                    zip(A.save.take(a[0]+1), repeat(a[2])));

    auto r = zip(sequence!"n"(cast(size_t)0), A.save, B.save)
        .map!mapper()
        .joiner;

    // But something goes wrong here: is it because the
    // above composed ranges are stack-allocated temporaries
    // that go out of scope upon return?
    return r;
}

It works too.

On Tue, Oct 16, 2012 at 12:33:20PM -0700, H. S. Teoh wrote: [...]
> Another data point: if I move the .joiner call out of cprod() into
> main(), then there is no problem. Could it be that something in joiner
> is breaking somehow, when returned from a function?
[...]

I found a reduced case:

	import std.algorithm;
	import std.range;
	import std.stdio;

	auto boo() {
		auto C = [2];
		return
			[1,1]
			.map!((a) => C)
			.joiner
		;
	}

	void main() {
		auto C = [2];
		writeln(
			[1,1]
			.map!((a) => C)
			.joiner
		.take(12));

		writeln("====");

		writeln(boo().take(12));
	}

Excuse the odd formatting, I wanted to make sure the [1,1,1].map!(...)
parts are line-for-line identical between boo() and main().

This example segfaults in the last writeln. Commenting out .joiner makes the segfault go away. Reducing [1,1] to a 1-element array makes the problem go away. Replacing C with [1] makes the problem go away. Removing map!(...) and replacing it with something involving C makes the problem go away. Deleting the .take(12) outputs a whole mass of garbage values and then segfaults.

So it seems like there is some kind of bad interaction between map and joiner. Maybe as jethro said, it's wrong code produced by dmd for the delegate passed to map? It seems to be dependent on the reference to the local variable C, which seems to imply a corrupted (or just out-of-scope?) delegate context.


T

-- 
The best way to destroy a cause is to defend it poorly.

On 10/16/2012 09:47 PM, jerro wrote:
>> Hmm. There *is* a delegate being passed to map(). Would that cause
>> problems? Theoretically it shouldn't, but as you said, if dmd isn't
>> handling it correctly that could cause problems.
>
> I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8)
> and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it
> should be if the memory for the variables that the delegate uses was
> allocated on the heap?
>

It should certainly allocate a closure. However, we don't want hidden
allocations in Phobos, so an alternate implementation strategy that
captures the input by value would be preferable anyway.
The bug should be reported in each case.

On Wednesday, October 17, 2012 00:04:49 Timon Gehr wrote:
> On 10/16/2012 09:47 PM, jerro wrote:
> >> Hmm. There *is* a delegate being passed to map(). Would that cause problems? Theoretically it shouldn't, but as you said, if dmd isn't handling it correctly that could cause problems.
> > 
> > I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8) and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it should be if the memory for the variables that the delegate uses was allocated on the heap?
> 
> It should certainly allocate a closure. However, we don't want hidden
> allocations in Phobos, so an alternate implementation strategy that
> captures the input by value would be preferable anyway.
> The bug should be reported in each case.

The allocation of closures is pretty much inevitable when we have delegates and/or non-static Voldemort types.

- Jonathan M Davis