Guava: NoSuchElementException when using Lists.partition and remove

[amine-java]

Hello,

It seems that there's a bug in the implementation of the Lists.partition. Here's the problem; assume that I have partitionned a List of Integers, if you perform a loop over the partitionned list, and for each subList you perform a removeAll() function, you'll get an error (NoSuchElementException)

Here's the code:

It seems like whenever the subList is emptied, the empty subList is REMOVED from the partitionned list and therefore causes the exception mentioned above, the exception is thrown from the next() method inside AbstractList.java

[dimo414]

This is an interesting failure mode 🙂 ultimately I suspect the caveat in the docs about mutations applies:

The inner lists are ... subject to all the usual caveats about modification as explained in [List.sublist()].

That said, this is definitely odd behavior. Consider:

jshell> var partitioned = Lists.partition(Lists.newArrayList(1), 2)
partitioned ==> [[1]]

jshell> var iter = partitioned.iterator()
iter ==> java.util.AbstractList$Itr@28c4711c

jshell> iter.hasNext()
$5 ==> true

jshell> iter.next().removeAll(Lists.newArrayList(1))
$6 ==> true

jshell> iter.hasNext()
$7 ==> true

jshell> iter.next()
|  Exception java.util.NoSuchElementException
|        at AbstractList$Itr.next (AbstractList.java:377)
|        at (#8:1)

partitioned only starts with one element! Why would iter.hasNext() return true the second time it's called?

We can trigger the same behavior with an even simpler example that doesn't involve Lists.partition():

jshell> var ls = Lists.newArrayList(1)
ls ==> [1]

jshell> var iter = ls.iterator()
iter ==> java.util.ArrayList$Itr@534df152

jshell> iter.hasNext()
$11 ==> true

jshell> iter.next()
$12 ==> 1

jshell> ls.remove(0)
$13 ==> 1

jshell> iter.hasNext()
$14 ==> true

That's not right! Calling .next() will similarly fail, though with a slightly more informative ConcurrentModificationException. Either way though, this directly violates the Iterator spec, which says:

[hasNext()] returns true if next() would return an element rather than throwing an exception.

It seems like AbstractList.Itr.hasNext() has a bug:

public boolean hasNext() {
  return cursor != size();
}

As this will return true if cursor is larger than size().

I wonder if there's a good reason for != instead of <?

[netdpb]

The Javadoc for ArrayList says that the iterators will fail (by throwing ConcurrentModificationException) if the list is modified during iteration unless by the iterator's own remove() or add() methods—which is what you're doing by calling remove(0). It also says that exactly when it will fail is not specified.

Basically, if you modify a list that isn't thread-safe while iterating, you should expect CME, but not reliably.

Lists.partition() returns a list of lists; each inner list is a dynamic view of a sublist of the original lists and is "subject to all the usual caveats about modification as explained in that API".

The docs for hasNext() that say that if it returns true then next() won't throw are actually referring to next()'s not throwing NoSuchElementException, which it's documented to throw if hasNext() returns false. (I admit that the docs that say "rather than throwing an exception" should be clarified to say "rather than throwing NoSuchElementException.)

[dimo414]

I'm not sure I follow your last paragraph. In my example above hasNext() returns true and then next() throws NoSuchElementException. Even if the docs on Iterator.hasNext() were tweaked to specifically reference NoSuchElementException, it still seems to be asserting this exception shouldn't be thrown if hasNext() returns true.

[netdpb]

OK, I didn't read your example closely enough. This is not great, but ArrayList does effectively say all bets are off if the list is modified during iteration.

If we wanted to make a change to the iterator, I'd say we should instead make hasNext() call checkForComodification().

Separately from the JDK, however, I see that Partition doesn't use the AbstractList feature that makes it throw CME. Partition itself doesn't allow modification, but its iterator could react that way if the source list is modified.

[Buddy119]

@netdpb @dimo414
Hi,
After reviewed your discussion, I have some my thoughts as below

According to the discussion, you are confused on why iter.hasNext() is true. Actually, it is because class Partition use Iterator from superclass AbstractList. And the hasNext() function in class AbstractList is not perfect. They have been optimized in subclass ArrayList.Plese review below

This is hasNext in AbstractList class. It call size() function

public boolean hasNext() {
    return cursor != size();
} 

This is hasNext in ArrayList class. It use value size. And the documentation said it is An optimized version of AbstractList.Itr. I see this in JDK1.8

public boolean hasNext() {
    return cursor != size;
}

when use fuction size(), every time propram call hasNext(). The hasNext() will call size(), then the value size will be recalculated. Back to the code from #3570, when the propram execute removeall(), the recalculate size will be 0, but the cursor is 1. so the hasNext() return true.

for(List<Integer> l : ll){
   l.removeAll(elementExclude);
}

[Buddy119]

@netdpb @dimo414
there is a Typo 3790 not 3570.

I also tested below code. I use ArrayList as container and then do the same removeAll. No exception is throw. So, I think the behavior of partition should be same

        List<Integer> list = new ArrayList();
        list.add(1);
        List<Integer> elementExclude = new ArrayList();
        elementExclude.add(1);

        List<List<Integer>> ll = new ArrayList();

        ll.add(list);
        for(List<Integer> l : ll){

            l.removeAll(elementExclude);
        }

[dimo414]

According to the discussion, you are confused on why iter.hasNext() is true.

I think you misunderstand; it's clear why hasNext() is returning true given the current implementation, it's not clear that this behavior is actually to-spec (I don't think it is).

[Buddy119]

@dimo414
Ok, So I am wondering what is the expected behavior? In my view, I think the expected behavior should be same with the ArrayList. No exception should be thrown.

To be more clear, I think below two code should have same behavior

Example with Partition as container

        List<Integer> list = new ArrayList();
        list.add(1);
        List<Integer> elementExclude = new ArrayList();
        elementExclude.add(1);

        List<List<Integer>> ll =Lists.partition(list, 5);

        ll.add(list);
        for(List<Integer> l : ll){

            l.removeAll(elementExclude);
        }

Example with ArrayList as container

        List<Integer> list = new ArrayList();
        list.add(1);
        List<Integer> elementExclude = new ArrayList();
        elementExclude.add(1);

        List<List<Integer>> ll = new ArrayList();

        ll.add(list);
        for(List<Integer> l : ll){

            l.removeAll(elementExclude);
        }