getAllPresent can return null values

[ipnm]

Looks like using Iterator.remove before Entry.setValue is not correct. remove can substitute some TreeNodes in HashMap to plain Nodes, while iterator continues to iterate over old TreeNode instances and sets the values to those garbage nodes.

public class Main {
    static class Key {
        @Override
        public int hashCode() {
            return 0; // to put keys in one bucket
        }
    }
    public static void main(String[] args) {
        List<Key> keys = new ArrayList<>();
        for (int i = 0; i < 11; ++i) { // 11 is big enough for a map to use tree nodes
            keys.add(new Key());
        }
        Map<Object, Object> data = Collections.singletonMap(keys.get(10), 1);

        Map<Object, Object> result = new HashMap<>();
        for (Object key : keys) {
            result.put(key, null);
        }

        for (Iterator<Map.Entry<Object, Object>> iter = result.entrySet().iterator(); iter.hasNext();) {
            Map.Entry<Object, Object> entry = iter.next();
            Object value = data.get(entry.getKey());
            if (value == null) {
                iter.remove();
            } else {
                entry.setValue(value); // this call doesn't set the value
            }
        }

        if (result.containsValue(null)) {
            System.out.println("FAILED");
        } else {
            System.out.println("OK");
        }
    }
}

[ben-manes]

ouch, if that's true doesn't HashMap break the Map contract? I'll try to play with your snippet and think about this when I have some time, but at first glance its an annoying break in the collections.

[ben-manes]

/**
 * Returns a {@link Set} view of the mappings contained in this map.
 * The set is backed by the map, so changes to the map are
 * reflected in the set, and vice-versa.  If the map is modified
 * while an iteration over the set is in progress (except through
 * the iterator's own <tt>remove</tt> operation, or through the
 * <tt>setValue</tt> operation on a map entry returned by the
 * iterator) the results of the iteration are undefined.  The set
 * supports element removal, which removes the corresponding
 * mapping from the map, via the <tt>Iterator.remove</tt>,
 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 * <tt>clear</tt> operations.  It does not support the
 * <tt>add</tt> or <tt>addAll</tt> operations.
 *
 * @return a set view of the mappings contained in this map
 */
public Set<Map.Entry<K,V>> entrySet() {...}

Since that's going through the APIs, I think my usage is correct and you might file a JDK bug? The iterator is supposed to be consistent.

[ipnm]

I also think that JDK behaviour is at least strange. There is a comment for setValue that could justify such behaviour:

V setValue(V value)
Replaces the value corresponding to this entry with the specified value (optional operation). (Writes through to the map.) The behavior of this call is undefined if the mapping has already been removed from the map (by the iterator's remove operation).

But I presume it means the explicitly deleted entry cannot be edited. Will ask JDK guys.

[ben-manes]

I verified that your program passes in JDK7. Have you opened up a JDK bug or shall I?

[ipnm]

I've submitted a bug report. Will give an update once have a feedback.

[ben-manes]

Interesting note is that ConcurrentHashMap behaves correctly because its setValue also does a map.put(key, value). I think this is what the fix to HashMap should be. What do you think?

/**
 * Sets our entry's value and writes through to the map. The
 * value to return is somewhat arbitrary here. Since we do not
 * necessarily track asynchronous changes, the most recent
 * "previous" value could be different from what we return (or
 * could even have been removed, in which case the put will
 * re-establish). We do not and cannot guarantee more.
 */
public V setValue(V value) {
  if (value == null) throw new NullPointerException();
  V v = val;
  val = value;
  map.put(key, value);
  return v;
}

[Maaartinus]

There are some minor problems:

if (value == null) throw new NullPointerException();

Obvious.

map.put(key, value);

This would make the next next() throw, but it can be fixed.

---

What's bothers me is the "unnecessary" table access, but setKey is not that common.

In case of getValue, a similar situation occurs:

{
    final Map<Key, String> map = new HashMap<>();

    for (int i = 0; i < 10; ++i) map.put(new Key(), "A");
    final Key favoriteKey = new Key();
    map.put(favoriteKey, "A");

    Map.Entry<Key, String> favoriteEntry = null;

    for (final Iterator<Map.Entry<Key, String>> iter = map.entrySet().iterator(); iter.hasNext();) {
        final Map.Entry<Key, String> entry = iter.next();
        if (entry.getKey().equals(favoriteKey)) {
            favoriteEntry = entry;
        } else {
            iter.remove();
        }
    }

    for (final Map.Entry<Key, String> e : map.entrySet()) e.setValue("B");

    // just to be sure
    map.put(favoriteEntry.getKey(), "C");

    System.out.println(favoriteEntry.getValue()); // still "A"
}

The Javadoc for Map.Entry#getValue says "If the mapping has been removed from the backing map (by the iterator's remove operation), the results of this call are undefined". There are two iterators in my test, but neither has removed my favorite mapping.

I guess, there's no solution. Calling map.get(entry.getValue()) would sacrifice too much efficiency for a fairly strange usage. Explaining this usage in the Javadoc would probably confuse everyone.

---

I guess, insertions replacing regular nodes by tree nodes can break the entry the same way.

[ben-manes]

It's unfortunate that they untreeify. They don't shrink the capacity on removal by assuming the high watermark will occur again or the map will be short lived. It seems that their optimization makes the opposite assumption and breaks backwards compatibility to do so.

[ben-manes]

Any update?

[ipnm]

No updates so far

[ben-manes]

@Maaartinus I think your example might be flawed because it assumes that writes to the map are visible to the entry. An entry's state should be a stable snapshot, outside of any direct mutations, and is not expected to change underneath the consumer. The collection classes tend to hand back a write-through entry rather than their internal one for this purpose.

Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration.

So I think the current behavior is correct, but perhaps subtle, detail of the Collections Framework.

[Maaartinus]

@ben-manes But an entry is neither a view into the map (as my example shows), nor a stable snapshot (just replace the 10 in my example by a smaller value). Speaking about "some point at or since the creation of the iterator" allows both kinds of behavior and even its mix.

In the javadoc for Map.Entry#getValue, the first part of "If the mapping has been removed from the backing map (by the iterator's remove operation), the results of this call are undefined". could be removed. :D

It should be explicitly stated, that any change to the map since this entry was returned, makes the result of getValue undefined. It seems to be hardly more than a syntactic anti-sugar for the lack of for (K k, V v: map) {...}.

[ben-manes]

In the case of HashMap that's true, but not for ConcurrentHashMap. That class still abides by the contracts and doesn't speak to breaking them, unlike say IdentityHashMap which states that it is not a general-purpose implementation. To me that means that an Entry may be live or a write-through copy, where the constraint is that it is stable for the given thread.

[ipnm]

Ticket created:
https://bugs.openjdk.java.net/browse/JDK-8186171

[ben-manes]

Thanks! I'll try to find the time to get this fixed and released. Great catch, btw.

[ben-manes]

Looks like the changes passed CI and its ready for release. I can do that now if this is impacting you in any way. If not, then I'll wait a little for #177 to see if there is another issue to fix. Since version numbers are free I am fine getting this to you, so please let me know.

[ipnm]

Thanks for a fix! It's not critical for me so feel free to release later.

[ben-manes]

Released!

[ben-manes]

@DougLea fixed the jdk bug, so I’ll revisit this optimization in the future.

[lingyunlujixin]

Thanks.