Bug 8334 – find cannot handle close match at end of haystack in needle isn't bi-directional
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P2
Component
phobos
Product
D
Version
D2
Platform
All
OS
All
Creation time
2012-07-01T15:08:00Z
Last change time
2015-06-09T05:15:00Z
Assigned to
issues.dlang
Creator
issues.dlang
Comments
Comment #0 by issues.dlang — 2012-07-01T15:08:02Z
This code
import std.array;
import std.algorithm;
void main()
{
auto haystack = [1, 2, 3, 4, 1, 9, 12, 42];
auto needle = filter!"true"([12, 42, 27]);
assert(find(haystack, needle).empty);
}
results in this
[email protected](3255): Range violation
----------------
./q(_d_array_bounds+0x26) [0x436112]
./q() [0x42d9c9]
./q(int[] std.algorithm.find!("a == b", int[], std.algorithm.filter!("true").filter!(int[]).filter.FilteredRange).find(int[], std.algorithm.filter!("true").filter!(int[]).filter, std.algorithm.filter!("true").filter!(int[]).filter.FilteredRange.FilteredRange function(int[]))+0xc8) [0x42b748]
./q(_Dmain+0xc9) [0x42b149]
./q(extern (C) int rt.dmain2.main(int, char**).void runMain()+0x1c) [0x42c818]
./q(extern (C) int rt.dmain2.main(int, char**).void tryExec(scope void delegate())+0x2a) [0x42c192]
./q(extern (C) int rt.dmain2.main(int, char**).void runAll()+0x3b) [0x42c85f]
./q(extern (C) int rt.dmain2.main(int, char**).void tryExec(scope void delegate())+0x2a) [0x42c192]
./q(main+0xd1) [0x42c11d]
/lib/libc.so.6(__libc_start_main+0xf5) [0x7f25ecccc455]
----------------
If needle is an array rather than a filtered range, it's fine, and if the mismatch is before the end of the haystack, it's fine, but that particular overload of find cannot handle having the beginning of the needle match the end of the haystack when the needle is longer than the remainder of the haystack:
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
if (isRandomAccessRange!R1 && isForwardRange!R2 && !isBidirectionalRange!R2
&& is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))