ArrayList.subList().spliterator() is not late-binding
paul.sandoz at oracle.com
Fri Jan 29 09:02:55 UTC 2016
Last-binding while adding some complexity to the implementation is an important property, as it is to fail-fast on a best effort basis.
When one has mutable collections that can be structurally modified and lazy views over those collections (Streams/Iterators) then those views really need to act on the most up to date structure and not a snapshot (structural or otherwise) when the view was created. Otherwise, it is a potential source of bugs producing incorrect results or exceptions, or another form of complexity for the implementation to maintain integrity under such conditions.
We took a short-cut here to reuse the existing top-level spliterator in a non-late-binding manner by specifying the absolute fence. We should fix it.
Glancing at the code i believe there is a simple fix. When -1 is passed as the fence to the ArrayList.ArrayListSpliterator then the fence is created lazily and should be the result of offset + list.size e.g. in the constructor:
hi = fence = offset + lst.size;
The forEach impl also needs updating.
Sublists are also tricky beasts. See documentation on List.subList:
* The semantics of the list returned by this method become undefined if
* the backing list (i.e., this list) is <i>structurally modified</i> in
* any way other than via the returned list. (Structural modifications are
* those that change the size of this list, or otherwise perturb it in such
* a fashion that iterations in progress may yield incorrect results.)
> On 29 Jan 2016, at 05:32, Tagir F. Valeev <amaembo at gmail.com> wrote:
> When reviewing 8079136 I noticed that
> ArrayList.subList().spliterator() is not late-binding:
> List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4)).subList(0, 3);
> Stream<Integer> s = list.stream();
> --> Exception in thread "main" java.util.ConcurrentModificationException
> This works correctly for other list implementation (for example,
> replacing ArrayList with LinkedList makes this code working). As
> Collection.spliterator() spec says:
>> In order to preserve expected laziness behavior for the stream() and
>> parallelStream() methods, spliterators should either have the
>> characteristic of IMMUTABLE or CONCURRENT, or be late-binding. If
>> none of these is practical, the overriding class should describe the
>> spliterator's documented policy of binding and structural
>> interference, and should override the stream() and parallelStream()
>> methods to create streams using a Supplier of the spliterator
> None of these is true for ArrayList.subList().spliterator(): it's not
> IMMUTABLE, not CONCURRENT, not late-binding, the binding policy is not
> documented and stream()/parallelStream() methods are not overridden.
> Is this an issue?
> Actually to my opinion late-binding spliterator behavior is a mistake.
> Nobody cares about it as nobody modifies the source between stream
> creation and terminal operation call. On the other hand, this
> requirement adds implementation complexity and I already found the
> second late-binding problem in existing code (the first one was with
> Pattern.splitAsStream). Also it's not documented that Stream.concat
> may bind the late-binding source, but nobody cares anyways. Life would
> be easier without late-binding spliterators.
> With best regards,
> Tagir Valeev.
More information about the core-libs-dev