ListMultiMap - Failed to 'put' causes the internal iterator in inconsistent state - NoSuchElementException thrown

[gissuebot]

Original issue created by stinkyminky on 2012-03-01 at 11:19 PM

---

Failed to add 'value' to 'list'-value will make MultiMap in inconsistent state - so iterating through entry-iterator can throw NoSuchElementException is throw.

This happens if you only attempt to do MultiMap.put() - which fails b/c the supplied list fail to 'add()'.

If you try to putAll into another multimap, you get

Exception in thread "main" java.util.NoSuchElementException
    at java.util.AbstractList$Itr.next(AbstractList.java:350)
    at com.google.common.collect.AbstractMultimap$EntryIterator.next(AbstractMultimap.java:1140)
    at com.google.common.collect.AbstractMultimap$EntryIterator.next(AbstractMultimap.java:1108)
    at com.google.common.collect.AbstractMultimap.putAll(AbstractMultimap.java:264)

The sample code can reproduce the problem

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-01 at 11:28 PM

---

I confirm the bug. The cause is as follows: AbstractMultimap defines

  public boolean put(@Nullable K key, @Nullable V value) {
    Collection<V> collection = getOrCreateCollection(key);

if (collection.add(value)) {
  totalSize++;
  return true;
} else {
  return false;
}

  }

However, if a newly created, empty collection rejects an element, then this violates the AbstractMultimap invariant that there are no empty collections in the backing map.

---

Labels: Type-Defect, Package-Collect

[gissuebot]

Original comment posted by kevinb@google.com on 2012-03-01 at 11:44 PM

---

Note: While libraries should have failure atomicity in the face of checked exceptions, nowhere is it writ that the same standard need apply for programmer error exceptions. The solution is to fix the code that caused the exception.

---

Status: WontFix

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-02 at 12:07 AM

---

Kevin, this doesn't involve exceptions. The test case provided simply returns false on an attempt to add an illegal element; it doesn't throw an exception...and I think AbstractMultimap should allow that technique to work.

[gissuebot]

Original comment posted by cpovirk@google.com on 2012-03-02 at 12:28 AM

---

True, but the sample code implements a custom List that does not obey the List contract. Perhaps we could imagine an empty collection that does return false on an add() call, but this seems unlikely.

All that said, my initial reaction was "we should fix this."

[gissuebot]

Original comment posted by cpovirk@google.com on 2012-03-02 at 12:31 AM

---

In fact, Collection entirely rules out the "return false when empty" case:

"(Returns false if this collection does not permit duplicates and already contains the specified element.) ... If a collection refuses to add a particular element for any reason other than that it already contains the element, it must throw an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns."

But I presume that the problem also exists when an exception is thrown, and that seems worth fixing if it's not onerous. We have plenty of other tests for this sort of thing, e.g., that calling [remove(), next()] on an iterator throws ISE but then continues normally.

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-02 at 12:32 AM

---

We have the same problem for a bare Multimap (as opposed to a ListMultimap), and I can totally respect a Collection implementation that imposes constraints on the method it lets you add.

I have a patch and a test, by the way, if we agree that we should accept this bug.

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-02 at 12:33 AM

---

Bleah, sorry, meant "imposes constraints on the elements it lets you add."

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-02 at 12:36 AM

---

Ah, sorry. cpovirk's appeal to the Collection Javadoc convinces me.

That said, cpovirk, the patch I've prepared also provides failure atomicity of the kind you suggest. It's not very onerous at all.

[gissuebot]

Original comment posted by stinkyminky on 2012-03-02 at 12:41 AM

---

This is javadoc of List.add

add

boolean add(E e)

Appends the specified element to the end of this list (optional operation).

Lists that support this operation may place limitations on what elements may be added to this list. In particular, some lists will refuse to add null elements, and others will impose restrictions on the type of elements that may be added. List classes should clearly specify in their documentation any restrictions on what elements may be added. 

As it states - some lists can clearly specify restriction. In this case, we restriction - no negative integer. This is a valid List.add() constraint.

Also, we you put - valid-value and invalid-valaue, it works. So it is very inconsistent. It only fails when you put only invalid-value.

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-02 at 12:56 AM

---

The javadoc of Collection.add further specifies: "If a collection refuses to add a particular element for any reason other than that it already contains the element, it must throw an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns."

Therefore, you must fail by throwing an exception, not by returning false. (To be fair, if you threw an exception, you'd still break Multimap as-is, which is why I think there's a bug to be fixed here.)

[gissuebot]

Original comment posted by cpovirk@google.com on 2012-03-02 at 07:22 PM

---

Reopening pending further discussion.

---

Status: Acknowledged

[gissuebot]

Original comment posted by kevinb@google.com on 2012-03-02 at 08:54 PM

---

If this fix is simple and harmless then I won't argue against it, I just want to avoid setting up a false expectation that people might apply to the rest of the library as a whole.

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-02 at 10:18 PM

---

Okay. The fix is, indeed, quite simple; I'll send it for review.

---

Status: Accepted

[gissuebot]

Original comment posted by wasserman.louis on 2012-03-08 at 09:12 PM

---

HEAD has a fix that addresses the problem for put and add. It doesn't provide atomicity for addAll, putAll, or the like, but given that we're not planning to guarantee failure atomicity globally, I think we can call this issue "as resolved as it's going to be."

[gissuebot]

Original comment posted by fry@google.com on 2012-03-13 at 06:58 PM

---

(No comment entered for this change.)

---

Status: Fixed
Labels: Milestone-Release12