Bug 21215 – std.range.recurrence leads to an infinite loop
Status
RESOLVED
Resolution
INVALID
Severity
blocker
Priority
P1
Component
phobos
Product
D
Version
D2
Platform
x86_64
OS
Linux
Creation time
2020-09-02T11:15:08Z
Last change time
2021-06-23T18:02:05Z
Assigned to
No Owner
Creator
Russel Winder
Comments
Comment #0 by russel — 2020-09-02T11:15:08Z
The following code leads to what seems to be an infinite loop when executed using "dub test":
```
import std.range: dropExactly, recurrence;
ulong recurrency(immutable ulong n) {
auto sequence = recurrence!((a, n) => a[n - 1] * n)(1UL);
return sequence.dropExactly(n - 1).front;
}
version(unittest) {
import unit_threaded;
}
@("Check the base case")
unittest {
recurrency(0).should == 1;
}
/*
@("Check the property")
unittest {
check!((ubyte n) => recurrency(n + 1) == (n + 1) * recurrency(n));
}
*/
```
Comment #1 by Ajieskola — 2021-06-23T18:02:05Z
This is intended behaviour.
When recurrency function is called with 0, sequence.dropExactly is called with 0ul - 1, which overflows to ulong.max. The code is multiplying the previous factorial ulong.max times.
It is not an infinite loop literally, but would presumably take thousands of years to complete.