Review Phobos algorithms and make them transient-safe where possible

[dlangBugzillaToGithub]

hsteoh reported this on 2013-01-01T12:09:55Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=9253

CC List

• monarchdodra

Description

This bug is to have a central place to keep the list of Phobos algorithms found to be transient-incompatible but could potentially be made transient-compatible, so that the list doesn't get lost in the dust of forum history.

- std.algorithm.reduce (when no seed is given)
- std.algorithm.joiner (both variants have been fixed in git HEAD)
- std.algorithm.group
- std.algorithm.minCount
- std.algorithm.minPos (takes forward range; should use .save)
- std.algorithm.Levenshtein (takes forward range; should use .save)
- std.algorithm.makeIndex (takes forward range; should use .save)
- std.algorithm.splitter (takes slices without checking for isSlicable)
- std.algorithm.topNCopy
- std.algorithm.NWayUnion
- std.array.array (probably not fixable)
- std.array.insertInPlace (probably not fixable)
- std.array.join (copies input range; may not be fixable)
- std.stdio.writeln & friends (need more testing, there are some deep bits that fail with transient ranges)

While the whole transience issue hasn't been decided yet, Andrei has agreed that those algorithms that *can* be made transience-compatible, should be. The fate of the rest will be determined when this issue has been decided on.

[dlangBugzillaToGithub]

monarchdodra commented on 2013-01-01T13:05:23Z

(In reply to comment #0)
> - std.algorithm.splitter (takes slices without checking for isSlicable)

For the record, I'm on splitter. I had a pull ready, but closed it for further improvements.

[dlangBugzillaToGithub]

monarchdodra commented on 2013-01-14T13:30:18Z

(In reply to comment #0)
> This bug is to have a central place to keep the list of Phobos algorithms found
> to be transient-incompatible but could potentially be made
> transient-compatible, so that the list doesn't get lost in the dust of forum
> history.
> 
> - std.algorithm.reduce (when no seed is given)
> - std.algorithm.joiner (both variants have been fixed in git HEAD)
> - std.algorithm.group
> - std.algorithm.minCount
> - std.algorithm.minPos (takes forward range; should use .save)
> - std.algorithm.Levenshtein (takes forward range; should use .save)
> - std.algorithm.makeIndex (takes forward range; should use .save)
> - std.algorithm.splitter (takes slices without checking for isSlicable)
> - std.algorithm.topNCopy
> - std.algorithm.NWayUnion
> - std.array.array (probably not fixable)
> - std.array.insertInPlace (probably not fixable)
> - std.array.join (copies input range; may not be fixable)
> - std.stdio.writeln & friends (need more testing, there are some deep bits that
> fail with transient ranges)
> 
> While the whole transience issue hasn't been decided yet, Andrei has agreed
> that those algorithms that *can* be made transience-compatible, should be. The
> fate of the rest will be determined when this issue has been decided on.

I just fixed minPos to use safe, and it should now be transient safe. No unittest though (yet) to prevent future breakage.

I'm fixing minCount: It will be transient safe for forward ranges. Input ranges will the thoroughly unsafe though, with no possibility of workaround.

[dlangBugzillaToGithub]

hsteoh commented on 2013-01-14T21:44:56Z

Yeah, some algorithms will have to be transient-unsafe, because it will either introduce unacceptable overhead, or it's plain impossible due to the nature of the algorithm. These cases will just have to be left as-is.

[dlangBugzillaToGithub]

b2.temp commented on 2017-08-26T17:39:08Z

It looks like a failed initiative, not maintained since > 4 years.
Since summer 2016 and the initiative to put annotations on all the unittest it's easier to locate the candidates.

[dlangBugzillaToGithub]

hsteoh commented on 2017-08-31T21:13:47Z

There must be some misunderstanding here.  What has annotations got to do with transient ranges?

Transient ranges, as referred to in this bug, are ranges where .front may mutate once .popFront is called, thereby making it invalid for code to cache .front by assigning to a local variable and referring to the variable later after .popFront is called.  AFAIK there are no annotations that can be used for this.

Many algorithms that currently break with transient ranges actually *can* be re-implemented in a way that doesn't break, and without undue overhead.  Tracking these algorithms is the purpose of this issue.