Comment #0 by jrdemail2000-dlang — 2018-12-31T09:00:24Z
std.algorithm.chunkBy will trigger an assertion error in std.algorithm.merge when merge is used with reference ranges. The failure is due to a call to front on an empty range, the empty range being the implementation merge. Tested with DMD 2.083.
-------- Sample program: case1.d --------
import std.algorithm : merge;
import std.stdio;
import std.range;
class InputRangeClass(R)
{
R data;
this(R _data) pure @safe nothrow
{
data = _data;
}
@property bool empty() pure @safe nothrow
{
return data.empty;
}
@property auto front() pure @safe nothrow
{
return data.front;
}
void popFront() pure @safe nothrow
{
data.popFront();
}
}
auto inputRangeClass(R)(R range)
{
return new InputRangeClass!R(range);
}
struct InputRangeStruct(R)
{
R data;
this(R _data) pure @safe nothrow
{
data = _data;
}
@property bool empty() pure @safe nothrow
{
return data.empty;
}
@property auto front() pure @safe nothrow
{
return data.front;
}
void popFront() pure @safe nothrow
{
data.popFront();
}
}
auto inputRangeStruct(R)(R range)
{
return InputRangeStruct!R(range);
}
void main(string[] args)
{
import std.algorithm : chunkBy, fold, map, merge;
auto data1 = [2, 3, 5];
auto data2 = [2, 4, 5];
auto data3 = [1, 2, 4, 5];
/* This succeeds. */
auto x = merge(data1, data2, data3);
writeln(x.chunkBy!((a, b) => (a == b)));
auto y1 = data1.inputRangeStruct;
auto y2 = data2.inputRangeStruct;
auto y3 = data3.inputRangeStruct;
/* A value range. This suceeds. */
auto y = merge(y1, y2, y3);
writeln(y.chunkBy!((a, b) => (a == b)));
auto z1 = data1.inputRangeClass;
auto z2 = data2.inputRangeClass;
auto z3 = data3.inputRangeClass;
/* A reference range. This fails. */
auto z = merge(z1, z2, z3);
writeln(z.chunkBy!((a, b) => (a == b)));
}
---------------------------------
The run:
$ dmd case1.d
$ ./case1
[[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]]
[[1], [2, 2, 2], [3], [4, 4], [5, 5, 5]]
core.exception.AssertError@/Library/D/dmd/src/phobos/std/algorithm/sorting.d(1123): Assertion failure
----------------
??:? _d_assertp [0x220b121]
??:? pure nothrow @property @safe int std.algorithm.sorting.Merge!("a < b", case1.InputRangeClass!(int[]).InputRangeClass, case1.InputRangeClass!(int[]).InputRangeClass, case1.InputRangeClass!(int[]).InputRangeClass).Merge.front() [0x21fd636]
... many more lines of stack trace ...
??:? _Dmain [0x21ec767]
[[1], [2, 2, 2], [4], [5]
Comment #1 by jrdemail2000-dlang — 2019-01-02T10:26:35Z
This is not specific to merge. Here is an example using roundRobin. The reference input range form fails, the value input range works fine. Only the reference input range is shown.
----- case2.d -----
import std.stdio;
import std.range;
import std.algorithm : chunkBy;
class InputRangeClass(R)
{
R data;
this(R _data) pure @safe nothrow { data = _data; }
@property bool empty() pure @safe nothrow { return data.empty; }
@property auto front() pure @safe nothrow { return data.front; }
void popFront() pure @safe nothrow { data.popFront(); }
}
auto inputRangeClass(R)(R range) { return new InputRangeClass!R(range); }
void main(string[] args)
{
auto x1 = [0, 1, 3, 6];
auto x2 = [0, 2, 4, 6, 7];
auto x3 = [1, 2, 4, 6, 8, 8, 9];
auto x =
roundRobin(x1.inputRangeClass, x2.inputRangeClass, x3.inputRangeClass)
.chunkBy!((a, b) => a == b);
writeln(x);
}
-------------------------------
$ dmd case2.d
$ ./case2
core.exception.AssertError@/Users/jondegenhardt/devtools/dmd2-2.083.1/osx/bin/../../src/phobos/std/range/package.d(1779): Attempting to fetch the front of an empty roundRobin
----------------
??:? _d_assert_msg [0xa7e51a2]
??:? pure nothrow @property @safe int std.range.roundRobin!(case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass).roundRobin(case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass).Result.front() [0xa7cc5c0]
??:? pure nothrow @safe void std.algorithm.iteration.ChunkByImpl!(case2.main(immutable(char)[][]).__lambda2, std.range.roundRobin!(case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass).roundRobin(case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass, case2.InputRangeClass!(int[]).InputRangeClass).Result).ChunkByImpl.popFront() [0xa7ccc9f]
... More lines ...
??:? _Dmain [0xa7cc30f]
[[0, 0], [1], [3], [6] $
Comment #2 by jrdemail2000-dlang — 2019-01-03T07:54:50Z
Another example, this one involving multiwayMerge.
-------- case3.d ---------
import std.stdio;
import std.range;
import std.algorithm : chunkBy, multiwayMerge;
auto inputRangeStruct(R)(R range) { return InputRangeStruct!R(range); }
void main(string[] args)
{
auto x1 = [0, 1, 3, 6];
auto x2 = [0, 2, 4, 6, 7];
auto x3 = [1, 2, 4, 6, 8, 8, 9];
auto x4 = [1, 3, 5, 6];
auto y = [x1, x2, x3, x4]
.multiwayMerge
.chunkBy!((a, b) => a == b);
writeln(y);
}
---------------------------
This fails similarly to the other cases.
$ dmd case3.d
jondegenhardt@mac:merge_groupby$ ./case3
core.exception.AssertError@/Users/jondegenhardt/devtools/dmd2-2.083.1/osx/bin/../../src/phobos/std/range/primitives.d(2219): Attempting to popFront() past the end of an array of int
----------------
??:? _d_assert_msg [0xea781fe]
??:? pure nothrow @nogc @safe void std.range.primitives.popFront!(int).popFront(ref int[]) [0xea5ee5e]
??:? pure void std.algorithm.setops.MultiwayMerge!("a < b", int[][]).MultiwayMerge.popFront() [0xea5c623]
??:? pure void std.algorithm.iteration.ChunkByChunkImpl!(case3.main(immutable(char)[][]).__lambda2, std.algorithm.setops.MultiwayMerge!("a < b", int[][]).MultiwayMerge).ChunkByChunkImpl.popFront() [0xea5f494]
... more lines of stack trace ...
??:? _Dmain [0xea5c44d]
[[0, 0], [1, 1, 1], [2, 2], [3, 3], [4, 4], [5], [6, 6, 6, 6], [7$
Comment #3 by jrdemail2000-dlang — 2019-01-03T08:06:38Z
One more:
------ case4.d ------
import std.stdio;
import std.range;
import std.algorithm : chunkBy, fold, map;
import std.container.binaryheap;
void main(string[] args)
{
auto x = [3, 1, 0, 6, 0, 2, 4, 7, 6, 8, 8, 4, 1, 2, 9, 5, 3, 1, 6];
auto y = x
.heapify!"a > b"
.chunkBy!((a, b) => a == b)
.map!(c => c.fold!((a, b) => a + b));
writeln(y);
}
------------------------
The above will fail with assert errors similar to the others. However, the following are fine:
a) Removing the '.map!(c => c.fold...' line.
b) Adding a '.array' step after 'heapify.
The run:
$ dmd case4.d
$ ./case4
core.exception.AssertError@/Users/jondegenhardt/devtools/dmd2-2.083.1/osx/bin/../../src/phobos/std/algorithm/iteration.d(598): Attempting to popFront an empty map.
----------------
??:? _d_assert_msg [0xc3c548e]
??:? pure @safe void std.algorithm.iteration.MapResult!(case4.main(immutable(char)[][]).__lambda3, std.algorithm.iteration.ChunkByImpl!(case4.main(immutable(char)[][]).__lambda2, std.container.binaryheap.BinaryHeap!(int[], "a > b").BinaryHeap).ChunkByImpl).MapResult.popFront() [0xc3ace89]
... more lines ...
??:? _Dmain [0xc3aa1e9]
[0, 3, 4, 6, 8, 5, 18, 7, 16, 9$
Comment #4 by jrdemail2000-dlang — 2019-01-03T08:15:41Z
A bit more explanation - I encountered problems with chunkBy when writing an merge and aggregation of sorted files. Basically, an external merge sort, except also combining equivalent key entries and aggregating values associated with the keys. This is essentially a merge-chunkby-map/fold operation, except with a custom merge operation.
The examples in this report are cases I found while trying to identify a simpler sample case. These samples still don't show all the behaviors I encountered, but they should be enough to motivate the issues.
Comment #5 by jrdemail2000-dlang — 2019-01-22T19:14:12Z
It turns out that chunkBy has several issues with non-forward input ranges. I am working on a PR to address them.
Comment #6 by jrdemail2000-dlang — 2019-01-26T18:37:56Z