www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8061] New: std.algorithm.joiner breaks when used with InputRangeObject

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061

           Summary: std.algorithm.joiner breaks when used with
                    InputRangeObject
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: nyphbl8d gmail.com


--- Comment #0 from William Moore <nyphbl8d gmail.com> 2012-05-07 15:37:10 PDT
---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 07 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #1 from William Moore <nyphbl8d gmail.com> 2012-05-08 14:44:42 PDT
---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 08 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061


Jonathan M Davis <jmdavisProg gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmdavisProg gmx.com


--- Comment #2 from Jonathan M Davis <jmdavisProg gmx.com> 2012-05-09 02:43:39
PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 09 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061


hsteoh quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hsteoh quickfur.ath.cx


--- Comment #3 from hsteoh quickfur.ath.cx 2012-10-10 09:15:48 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 10 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #4 from hsteoh quickfur.ath.cx 2012-10-10 09:17:06 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 10 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #5 from hsteoh quickfur.ath.cx 2012-12-19 22:34:41 PST ---
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).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 19 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #6 from hsteoh quickfur.ath.cx 2012-12-20 08:07:24 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 20 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #7 from William Moore <nyphbl8d gmail.com> 2012-12-20 08:52:32 PST
---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 20 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra gmail.com


--- Comment #8 from monarchdodra gmail.com 2012-12-20 09:08:37 PST ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 20 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #9 from hsteoh quickfur.ath.cx 2012-12-20 09:44:44 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 20 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #10 from hsteoh quickfur.ath.cx 2012-12-20 10:07:42 PST ---
https://github.com/D-Programming-Language/phobos/pull/1019

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 20 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #11 from github-bugzilla puremagic.com 2012-12-23 18:23:22 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 23 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061


hsteoh quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 24 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061



--- Comment #12 from hsteoh quickfur.ath.cx 2012-12-24 13:52:10 PST ---
Verified fixed in git head phobos 03a6e295fadd7c563a60069be0be3ada1c234666

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 24 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8061


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla digitalmars.com


--- Comment #13 from Walter Bright <bugzilla digitalmars.com> 2012-12-24
20:21:52 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 24 2012