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.