RFR-8148748: ArrayList.subList().spliterator() is not late-binding

Tagir F. Valeev amaembo at gmail.com
Wed Feb 3 12:20:24 UTC 2016


Here's the webrev:

I noticed that list == null checks are never true, thus redundant, so
I removed them. The list field is final and always assigned to the
outer ArrayList instance. So it seems quite natural to make
ArrayListSpliterator non-static instead. Also I added one more field
into ArrayListSpliterator to hold the SubList reference. Hopefully
such footprint increase is acceptable. The offset field is initialized
eagerly as it does not change during the SubList lifetime. Also I
replaced "if (action == null)" checks with "Objects.requireNonNull".

Some more thoughts about forEachRemaining:

To me it seems that
if ((a = lst.elementData) != null)
is a redundant check as well as in current ArrayList implementation
elementData is never null. So it can be replaced with simple

Also this check:
 (i = index) >= 0
I don't see the case when i could be negative. Should it be removed as
well? Or probably it's added to aid JIT to elimitate bounds-checking?

With best regards,
Tagir Valeev.

PS> Hi Tagir,

PS> Last-binding while adding some complexity to the implementation
PS> is an important property, as it is to fail-fast on a best effort basis.

PS> When one has mutable collections that can be structurally
PS> modified and lazy views over those collections (Streams/Iterators)
PS> then those views really need to act on the most up to date
PS> structure and not a snapshot (structural  or otherwise) when the
PS> view was created. Otherwise, it is a potential source of bugs
PS> producing incorrect results or exceptions, or another form of
PS> complexity for the implementation to maintain integrity under such conditions.

PS> We took a short-cut here to reuse the existing top-level
PS> spliterator in a non-late-binding manner by specifying the
PS> absolute fence. We should fix it.

PS> Glancing at the code i believe there is a simple fix. When -1 is
PS> passed as the fence to the ArrayList.ArrayListSpliterator then the
PS> fence is created lazily and should be the result of offset +
PS> list.size e.g. in the constructor:

PS>   hi = fence = offset + lst.size;

PS> The forEach impl also needs updating.

PS> —

PS> Sublists are also tricky beasts. See documentation on List.subList:

PS> * The semantics of the list returned by this method become undefined if
PS> * the backing list (i.e., this list) is <i>structurally modified</i> in
PS> * any way other than via the returned list.  (Structural modifications are
PS> * those that change the size of this list, or otherwise perturb it in such
PS> * a fashion that iterations in progress may yield incorrect results.)

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

===8<===========End of original message text===========

Best regards,
 Tagir                            mailto:amaembo at gmail.com

More information about the core-libs-dev mailing list