Bug 8061 – std.algorithm.joiner breaks when used with InputRangeObject

When joining InputRangeObject-wrapped values, joiner fails to iterate past the first Range provided in the RangeofRanges. Example: import std.range:joiner,ElementType,InputRange,inputRangeObject; import std.conv:to; import std.stdio:writefln; void main() { auto r = joiner([inputRangeObject("ab"), inputRangeObject("cd")]); writefln("%s", to!string(r)); } When this is run, the only output is "ab", not "abcd" as expected. It's entirely possible that it's std.conv.to that's causing the problem as well. I haven't dug deep enough into Phobos to know for sure.

This appears to be a result of the inner ranges not being .saved properly when the joiner is .saved, the outer range is an array, and the inner ranges are not pass-by-value types. Joiner probably needs to be aware of and handle array-like outer ranges better.

Hmmm. Well, joiner takes a range of _input ranges_, not forward ranges, so it _can't_ use save on the inner ranges (though it does define save if the input ranges happen to be forward ranges). This assertion passes: assert(equal(joiner([inputRangeObject("ab"), inputRangeObject("cd")]), "abcd")); So, it would seem that the problem is in std.conv.to. It's probably assuming that passing the range results in a copy (since it does with most ranges). Truth be told, most range-based functions in Phobos aren't properly tested to make sure that they work with ranges which are input ranges rather than forward ranges or that they work with forward ranges which aren't copied when being passed to functions.

Wait, if an inner range is not a forward range, then .save is invalid, because if you call .save at one point, then advance the origin range, the inner ranges may have been invalidated, so the .save'd range is invalid. So .save should only be defined if both the outer range and the inner ranges are forward ranges, IMO.

By "inner ranges will be invalidated" I meant, "inner ranges will be consumed", so the .save'd copy of the range isn't actually a saved position in the original range.

Found cause of problem: in std.format.formatRange(), there's a static if block that reads: ... else static if (isForwardRange!T && !isInfinite!T) auto len = walkLength(val.save); If this line is artificially modified to set len to some fixed value (say, the length of the joined string), then the OP's code works. This implies that val.save did not *really* save the range; it returned a copy that, when consumed, also consumes the original range. Digging deeper into the joiner code, the criteria for the joined range to be a forward range is if the range of ranges passed to joiner is both itself a forward range, and its subranges are also forward ranges. In theory, if these two conditions were really true, then the joined range should be a valid forward range. So this indicates that the problem lies with the array of InputRangeObjects passed to joiner. And here we discover the root of the problem: std.array.save, which defines .save for built-in arrays, always just returns the array, whereas the correct implementation would be to call .save on all array elements (if they are forward ranges).

Correction: Andrei said on the forum that the definition of .save does not guarantee that inner ranges are saved. So std.array.save is correct. The problem is with std.algorithm.joiner: just because both outer and inner ranges are forward ranges, does NOT mean that the .save'd copy of the outer range preserves the state of the inner ranges (in fact, it does not, in the general case). std.range.FrontTransversal and std.range.Transversal also suffer from this wrong assumption.

The core of this issue is that "auto a = b;" is *SOMETIMES* equivalent to "auto a = b.save;". This is what made me run away from ranges screaming. Assignment can mean two entirely different things and affects passing ranges as parameters as well. The easiest way to avoid this problem is to only pass ranges by ref and only assign a range when calling .save explicitly.

(In reply to comment #6) > std.range.FrontTransversal and std.range.Transversal also suffer from this > wrong assumption. In this case, [Front]Transversal never actually iterate nor mutates the underlying ranges, so I'd say the save is valid. As a matter of fact, I'd argue that while the argument "name" is RoR, the actual iteration scheme is "Range of stuff that happens to be ranges": Eg: While it is a RoR, the *iteration* scheme stops at R. The underlying ranges are just elements. The only way for save to not work in this situation is outside modification but: a) This is true for ALL wrappers ranges anyways b) Given the "Range of stuff" vision, you can view the underlying ranges as elements whose modifications *should* be visible, even after a save. That said, you bring a valid point, and I think _all_ RoR interfaces should be reviewed.

In the case of [Front]Transversal, you're right, we only iterate across the fronts of the elements in the range, so we never pop those elements ourselves. So I guess it's OK. But yeah, we need to review all the RoR code to make sure everything is OK. I think std.array.join may also suffer from the same problem, I'll have to check.

Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/7ff2fcec063790184aac1d3aa08a09112da79763 Fix issue 8061. We cannot assume that RoR.save will also .save the state of its subranges; so the only way we can correctly export a .save method in the joined range is if we also .save its subranges as we traverse over them. https://github.com/D-Programming-Language/phobos/commit/99bece7a49a4e33e468397bff5c94c1a96551c33 Merge pull request #1019 from quickfur/joiner_save Fix issue 8061.

Verified fixed in git head phobos 03a6e295fadd7c563a60069be0be3ada1c234666

There was also this memory corruption bug I just fixed. https://github.com/D-Programming-Language/phobos/commit/ef0bed7d157afe5be5a69e17d5f30ffd309be527 The problem was an interior pointer to the [128] array, which, when the struct got copied, resulted in a pointer to a stack object that went out of scope.