NPE with eduction + cat on a collection containing nil

Description

Using the cat transducer with eduction leads to an NPE when the collection contains at least one collection with more than one item of which at least one is nil. The shortest reproduction case I could come up with is this:

Cause: An expanding transducer (cat, mapcat) puts the expansion on an internal buffer, which is a ConcurrentLinkedQueue. Java Queue impls do not support adding or removing null b/c null is used as a special value in some of the Queue apis.

Approach: Switch from ConcurrentLinkedQueue to LinkedList. LinkedList supports both Queue and other semantics as well and does support nulls (with caveats that that is a bad thing to do if you're using the Queue apis and expecting those special semantics). However, the TransformerIterator usage does not rely on any of that. LinkedList is also obviously not concurrency friendly, but the buffer is only used by a single thread at a time and the volatile field guarantees visibility, so this is fine.

I re-ran some of the perf tests from CLJ-1669 and found the expanding transducer test there (into [] (eduction (map inc) (mapcat range) s50)) went from 27 us to 24 us, so there is a bit of a perf improvement as well.

Patch: clj-1723.patch

Environment

None

Activity

Show:
Nicola Mometto
June 5, 2015, 3:53 PM

Patch committed and the ticket marked as resolved but not closed. I'm closing it.

Fogus
May 8, 2015, 3:49 PM

This is a very straight-forward solution that works and is easy to justify and grasp.

Alex Miller
May 4, 2015, 6:03 PM

Gah, Java Queues don't allow null. I have some prior work on other impls for this so I'm working on a fix.

Completed
Your pinned fields
Click on the next to a field label to start pinning.

Assignee

Alex Miller

Reporter

import

Labels

Approval

Ok

Patch

Code and Test

Priority

Critical

Affects versions

Fix versions