[CLJ-1237] reduce gives a SO for pathological seqs Created: 27/Jul/13 Updated: 22/May/15
|Affects Version/s:||Release 1.5|
|Fix Version/s:||Release 1.7|
|Patch:||Code and Test|
reduce gives a StackOverflowError on long sequences that contain many transitions between chunked and unchunked:
Such a sequence is well behaved under most other sequence operations, and its underlying structure can even be masked such that reduce succeeds:
I don't think Clojure developers normally worry about mixing chunked and unchunked seqs, so the existence of such a sequence is not at all unreasonable (and indeed this happened to me at work and was very difficult to debug).
It seems obvious what causes this given the implementation of reduce – it bounces back and forth between the chunked impl and the unchunked impl, consuming more and more stack as it goes. Without proper tail call optimization, it's not obvious to me what a good fix would be.
In the IChunkedSeq implementation, instead of calling internal-reduce when the
This would presumably work, but requires wrapping the normal return values from all
(attached as CLJ-1237c.patch)
Similar to using trampoline, but create a special type (Unreduced) that signals
Then seq-reduce is converted to check for instances of Unreduced before returning,
|Comment by Gary Fredericks [ 25/Aug/13 4:13 PM ]|
|Comment by Gary Fredericks [ 24/Mar/15 11:33 AM ]|
My coworker just ran into this, independently.
|Comment by Jason Wolfe [ 22/May/15 5:13 PM ]|
In Clojure 1.7, this is now happening for more cases, such as:
|Comment by Alex Miller [ 22/May/15 7:39 PM ]|
Pulling into 1.7 just so we don't lose it.