ArrayList.subList().spliterator() is not late-binding

[Paul Sandoz]

Hi Tagir,

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.)

Paul.

> On 29 Jan 2016, at 05:32, Tagir F. Valeev <amaembo at gmail.com> wrote:
> 
> Hello!
> 
> 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();
> list.add(5);
> s.findFirst();
> --> 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.
>