Unexpected `.subList()` behavior when getting a `[0, size()]` slice

[Spikhalskiy]

Expected behavior

I have an append-only IntArrayList and I want to take slices of it periodically. I would expect that the following code

var list = new IntArrayList();
list.add(1);
list.add(2);
var snapshot = list.subList(0, 2) // you would expect this never be more than 2 items, right?
list.add(3);
assertEquals(2, snapshot.size()); // assert fails, actually 3
assertEquals(3, list.size());

will lead to snapshot having only the first two elements.

Actual behavior

var list = new IntArrayList();
list.add(1);
list.add(2);
var snapshot = list.subList(0, 2)
list.add(3);
assertSame(list, snapshot); // wat

Root cause

This comes from the following implementation of subList:

	@Override
	public IntList subList(int from, int to) {
		if (from == 0 && to == size()) return this; // this is a good optimization for an unmodifiable collection, but it's not right for a modifiable one.
        ...
	}

Versions

At least [8.5.4, 8.5.15]

Workaround

IntArrayList.SubList and related classes are private.

The best workaround I found so far is to use

new it.unimi.dsi.fastutil.ints.AbstractIntList.IntSubList(list, from, to);

instead, as AbstractIntList.IntRandomAccessSubList that is a superclass of IntArrayList.SubList and is thankfully public.

[incaseoftrouble]

Citing JavaDoc for sub-list:

The semantics of the list returned by this method become undefined if the backing list ... is structurally modified 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.)

That means after list.add, the snapshot is in an undefined state.

The workaround probably is the way to go here

[Spikhalskiy]

In that case, it would be nice to at least make IntArrayList.SubList public to we don't have to fallback onto AbstractIntList.IntSubList

[Spikhalskiy]

I do understand the reference to such a clause in the javadoc if, for example, we took a slice and shrank the underlying collection after that, or even if we removed elements.
However, in this scenario (append-only list), there is no real reason for the slice to behave unexpectedly; it's neither intuitive nor necessary here. Such a simple usage doesn't have to be confusing and set up to be error-prone.
While it's technically correct to just point in the direction of the javadoc, I'm not sure it's the best solution here.

Also, just a nit: the javadoc on #subList you reference is getting overwritten and shadowed by IntList with the following:

	/** Returns a type-specific view of the portion of this list from the index {@code from}, inclusive, to the index {@code to}, exclusive.
	 *
	 * @apiNote This specification strengthens the one given in {@link List#subList(int,int)}.
	 *
	 * @see List#subList(int,int)
	 */

[incaseoftrouble]

However, in this scenario (append-only list), there is no real reason for the slice to behave unexpectedly

Well, it saves an allocation. Keep in mind that views on mutable collections are always weird, there will always be trade-offs. (The "correct" behavior would be to throw an exception, just like concurrent modification for iterators.) Similarly, on the call to subList, we don't know that it is an append-only list.

Genuine question: For such a specific use case, wouldn't it be easier to just adapt the implementation to that?

Also, just a nit: the javadoc on #subList you reference is getting overwritten and shadowed by IntList with the following:

nit on the nit: It links to the subList documentation and says it is strengthening it.

[Spikhalskiy]

@incaseoftrouble The problem is that the current behavior is contradictory to the behavior of slices from other programming languages and not aligned with user expectations. A user who is taking a subList(0, 5) doesn't expect it to grow to 20 elements. It expects it to be... a sublist from index 0 to index 5, as requested.

Well, it saves an allocation.

This is a good optimization for an unmodifiable collection.

If someone changes the semantics of the method for the sake of micro-optimization, it's a sign of a problem, especially for a library. Methods should do what... they are expected to do. Not what is cheap to do.

What happens here is worse, fastutils creates a tricky, unexpected edge case that behaves differently without an apparent reason for a microoptimization that is not necessary and can be easily implemented by the user if desired. fastutil does not provide a way to avoid this edge case. fastutil doesn't even explicitly document the existence of this edge case in the methods. All of this sets up users for a tricky production issue. This is not an optimization; it's a bug.

If a user wants to save this allocation and doesn't need an actual sublist/slice in this case, they can write a very simple if in their code.

var sublits = (from == 0 && to == list.size()) ? list : list.sublist();

^ on the user side is a perfect code that describes what happens explicitly and avoids misunderstanding and bugs.

A library should behave safely and in an expected manner. Users can and should do microoptimizations that change behavior like that themselves and keep them in their codebase, so they are clear, explicit, expected, and consensual.

Genuine question: For such a specific use case, wouldn't it be easier to just adapt the implementation to that?

We already solved our problem by using new AbstractIntList.IntRandomAccessSubList. Adapting an IntArrayList implementation is not an option, because this code works with IntList that may be created and come from several different places in the code.

If we go around and replace every IntArrayList with our own implementation and ban the use of the original IntArrayList just to fix the .subList() behavior, we'd better switch to a library with a safe API design or make a fork.

I don't know when another developer on our team calls a subList, hoping it behaves as a slicing method should, and we end up chasing one more issue in production because of that.

The final decision on API design is ultimately in the hands of the maintainers.

If the implementation remains the same, we'll have to ban .subList() at static code analysis to avoid future problems due to the unexpected method behavior in the edge case. We'll have to write our helpers for SubLists that behave as one would expect slicing methods to behave. Please consider at least making IntArrayList.SubList public, so we don't have to reimplement it for our helper methods then.

[vigna]

I'm a bit conflicted here because, one one side, you have somewhat natural expectations, and, on the other side, relying on undocumented implementation details that are not specified in the documentation, and instead go explicitly against a clear "don't do this" will always lead to cases like that.

If you were writing in Rust, your code wouldn't even compile.

By the same token, one could take a sublist from 0 to size(), delete the last element of the original list, and expect the sublist to become shorter—“hey, it was the whole list”. Which will happen with the current implementation, but not with the one you want. If I fixed the method eliminating the optimization, I could get a similar report about unexpected behavior, only, the other way around.

Consider that in 30 years nobody ever reported a problem with this behavior. So "unexpected", "contradictory", "tricky"... no, thanks. You are misusing the API and hoping it works the way you want. You hit a corner case in which your hopes are crushed, but you should not have relied on that behavior in the first place.

OMG this code has TODOs from 14 years ago. 😓

I'm happy to make SubList and its constructor public if that helps you. But remember that even if you build manually the sublist, there is no guarantee that in the future modifications to the code will render your manually constructed sublist behave in unpredictable ways.

[incaseoftrouble]

Just one more thing to add:

The problem is that the current behavior is contradictory to the behavior of slices from other programming languages and not aligned with user expectations.

A) this is Java, not other languages. The behavior is in line with Java's definitions. B) It may align with your expectations (which, don't get me wrong, is fine and not unreasonable), but it doesn't with mine, for example. As mentioned, I would have expected an exception to be thrown. Modifying the underlying data structure of a view always leads to problems. My point being, the implementation doesn't deviate from an established standard or behaves unconventionally.

Just to confirm, this is indeed what the Java reference implementation does (throw an exception)

var list = new ArrayList<Integer>();
list.add(1);
var snapshot = list.subList(0, 1);
list.add(1);
snapshot.size(); // ConcMod exception