Why does this Java code trigger a ConcurrentModificationException?

Question

In the first line of the loop I get the error, but I don't see why. From what I read this should happen only if I'm iterating over a collection and trying to modify it at the same time, but this is not the case.

In the code, list is of type ArrayList<Product>.

void mergeSort() { 
    mergeSort(0, list.size() - 1); //128
}

private void mergeSort(int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(p, q); //133
        mergeSort(q + 1, r);
        merge(p, q, r); //135
    }
}

private void merge(int p, int q, int r) {
    List<Product> left = list.subList(p, q);
    left.add(Product.PLUS_INFINITE);
    List<Product> right = list.subList(q + 1, r);
    right.add(Product.PLUS_INFINITE);
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; ++p) {
        Product x = left.get(i).compareTo(right.get(j)) <= 0 ? left.get(i++) : right.get(j++); //147
        list.set(k, x);
    }
}

This is the stacktrace:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1415)
    at java.base/java.util.ArrayList$SubList.get(ArrayList.java:1150)
    at ProductList$ProductSort.merge(MainClass.java:147)
    at ProductList$ProductSort.mergeSort(MainClass.java:135)
    at ProductList$ProductSort.mergeSort(MainClass.java:133)
    at ProductList$ProductSort.mergeSort(MainClass.java:128)
    at ProductList.sort(MainClass.java:95)
    at MainClass.main(MainClass.java:187)

Taking a subList and then calling add (which is a structural change) smells. — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented May 2, 2021 at 1:46
@azurefrog Yes, Product is just a class that I wrote, is not from a library. — gian_
– gian_, Commented May 2, 2021 at 1:50

Sweeper · Accepted Answer · 2021-05-02 01:50:41Z

8

subList does not create a new list that has the same elements as the original list in the specified range. Rather, it creates a "view" (docs):

Returns a view of the portion of this list [...]. The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa.

Also note:

The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list.

This is exactly what you are doing in merge. You are creating sublists left. Then modifying left structurally with add. So far so good. But then you created another sublist right and modifies it as well. This makes "the semantics of left to become undefined". And this causes the next call to get to throw an exception.

Minimal reproducible example:

ArrayList<String> list = new ArrayList<>(List.of("1", "2", "3", "4"));
List<String> left = list.subList(0, 2);
List<String> right = list.subList(2, 4);
right.add("5");
left.get(0);

Sublists are a bit like iterators in this regard (you can only remove via the iterator, if you remove via the original list, CME might be thrown).

One simple way to fix this is to create copies of the sublists so that they are no longer "views", but are actually independent lists:

List<Product> left = new ArrayList<>(list.subList(p,q));
List<Product> right = new ArrayList<>(list.subList(q+1,r));

answered May 2, 2021 at 1:50

Sweeper

292k23 gold badges260 silver badges439 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

gian_ Over a year ago

Thanks for the information. I tried this solution but the error persists with the same stacktrace.

Sweeper Over a year ago

@gian_ There shouldn't be a CME any more, but I found that your merge sort algorithm is implemented incorrectly. You probably meant to increment k instead of p in the for loop, and your indices seem a bit confused. The second parameter of sublist is exclusive while the first is inclusive. So subList(p,q) and subList(q+1,r) is totally skipping q, and ignoring r. You probably have other mistakes, that's just a few I saw.

gian_ Over a year ago

Oops, yes, I meant to increment k, and I wasn't aware that the second parameter of subList was exclusive. With these two fixes you suggested the code is working now, and the CME exception is gone. Thanks!

Collectives™ on Stack Overflow

Why does this Java code trigger a ConcurrentModificationException?

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related