5

Consider the following code snippet:

List<String> list = new LinkedList<>();
list.add("Hello");
list.add("My");
list.add("Son");

for (String s: list){
    if (s.equals("My")) list.remove(s);
    System.out.printf("s=%s, list=%s\n",s,list.toString());
}

This results in output:

s=Hello, list=[Hello, My, Son]
s=My, list=[Hello, Son]

So clearly the loop was only entered twice, and the third element, "Son", never gets visited. From the underlying library code, it looks like what happens is that the hasNext() method in the iterator doesn't check for concurrent modification, only the size against the next index. Since the size has been reduced by 1 by the remove() call, the loop simply doesn't get entered again, but no ConcurrentModificationException is thrown.

This seems to contradict the contract of the iterator:

The list-iterator is fail-fast: if the list is structurally modified at any time after the Iterator is created, in any way except through the list-iterator's own remove or add methods, the list-iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Is this a bug? Again, the contract of the iterator definitely appears to be disobeyed here - the structure of the list is structurally modified by something other than the iterator in the middle of iteration.

PeteyPabPro
  • 839
  • 10
  • 18
  • Some people are pointing at the LinkedList class level documentation that gives some disclaimers that the ConcurrentModificationException is on a "best effort" basis. Unless someone can prove why adding it to `hasNext()` would be problematic for some reason, it doesn't seem to be a best effort at all. – PeteyPabPro Nov 28 '14 at 21:40
  • I might be stating the obvious here, but the only reason I can think of for not implementing the check for the modification in the `hasNext()` method is that it would guarantee doubling of check operations in *all* cases, while absence of such check only leads to the non-throwing of exception in only *some* cases when performed modification results in the immediate exit from the loop (e.g. when all the elements from the current position of iterator to the end of the container are removed), which I guess was considered relatively rare by the implementers. – striving_coder Nov 29 '14 at 00:03

2 Answers2

3

Read the class-level Javadoc:

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • Or is it the feature of compiler which uses iterator underneath? – mprabhat Nov 28 '14 at 21:14
  • It has nothing to do with the compiler and everything to do with it being impossible, or at minimum extremely impractical, to implement. – Louis Wasserman Nov 28 '14 at 21:15
  • Let me open up the source code to see what's there – mprabhat Nov 28 '14 at 21:19
  • I see, thanks. I think that the wording of the iterator documentation should be changed then. From the part I quoted above, which is directly from the iterator doc, it's not clear that it's not guaranteed, i.e., it should say "may throw". – PeteyPabPro Nov 28 '14 at 21:20
  • It could conceivably be _more_ aggressive about throwing, e.g. checking in `hasNext()`, but even then it couldn't guarantee the behavior. FWIW, I believe its documentation is inherited, which might have something to do with it. – Louis Wasserman Nov 28 '14 at 21:20
  • @mprabhat it's very clear from the code what's going on - it's as I described. It seems simple enough to add the concurrent modification check to `hasNext()` – PeteyPabPro Nov 28 '14 at 21:21
  • @PeteyPabPro I meant Java's implementation code. ConcurrentModificationException is not part of get method, its only applicable for the iterator – mprabhat Nov 28 '14 at 21:22
  • Also, @LouisWasserman this doesn't really seem like a "best effort" type thing. Adding the check to `hasNext()` seems easy. If there was some trade-off regarding performance, "best effort" might not be the most accurate language. – PeteyPabPro Nov 28 '14 at 21:23
3

From https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html:

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

That is, the iterator will try its best to throw exception, but isn't guaranteed to do so in all cases.

Here are some more links on how fail fast iterators works and how the are implemented - in case someone will be interested:

http://www.certpal.com/blogs/2009/09/iterators-fail-fast-vs-fail-safe/

http://javahungry.blogspot.com/2014/04/fail-fast-iterator-vs-fail-safe-iterator-difference-with-example-in-java.html

http://www.javaperformancetuning.com/articles/fastfail2.shtml

And here is another SO question where people trying to find out the same thing:

Why isn't this code causing a ConcurrentModificationException?

Community
  • 1
  • 1
striving_coder
  • 798
  • 1
  • 5
  • 7
  • I was just going to quote the same thing. It might worthwhile to file a bug report, but you can't actually rely on it to throw an exception. – markspace Nov 28 '14 at 21:12
  • @markspace: Well, the ability of the iterator to throw exception is definitely useful and might save you some trouble in a lot of cases, but it's still not a guarantee and doesn't mean you shouldn't try your best to avoid modifying List in improper ways. I guess it's more like a seatbelt: you're better off wearing it, but it doesn't mean you're safe driving into the lamp post at 60 mph. – striving_coder Nov 28 '14 at 21:36
  • @striving_coder it's not trying its best at all. While it may be impossible to guarantee this in complicated situations involving multiple threads, this is about as basic a use-case as one can get. – PeteyPabPro Nov 28 '14 at 21:38
  • @PeteyPabPro: Well here http://javahungry.blogspot.com/2014/04/fail-fast-iterator-vs-fail-safe-iterator-difference-with-example-in-java.html it says that it's actually checking container modification at the time of `hasNext()` and `next()` methods acting, as you were arguing here as the best method of implementing it. – striving_coder Nov 28 '14 at 22:03
  • @striving_coder it only checks it in `next()`, not `hasNext()`. – PeteyPabPro Nov 28 '14 at 22:13