RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667

[Paul Sandoz]

Hi,

I think we should as consistent as possible about the functions being side-effect free when applied to "bulk" operations. A method such as computeIfAbsent can be viewed as a bulk operation in that it may perform two or more dependent actions (they are just not as bulky as forEach).

It's inconsistent if we state the functions should be side-effect free *but* map implementations tolerate side-effects resulting in state changes for entries other than that associated with the key under operation. I am not even sure this can be easily guaranteed with CHM in the face of resizes and keys hashing to the same bucket.

So i propose:

- the functions should be side-effect free.

- non-concurrent map implementations should, on a best-effort basis, detect comodification and fail with CME.

- concurrent map implementations should, on a best-effort basis, detect non-termination situations and fail with ISE. 

- document the best-effort behaviour and advise that implementations should override the default implementations if they want to do better.

Alas we cannot do anything about the default method implementations, but i don't think we should be constraining general behaviour based on that exact implementations (just as we do not for concurrent maps, it "behaves as if").

Paul.

On Feb 4, 2015, at 4:01 AM, Stuart Marks <stuart.marks at oracle.com> wrote:

> On 2/3/15 4:01 PM, Brent Christian wrote:
>> The code in bug 8071667 [1] passes a mappingFunction to computeIfAbsent() which
>> itself put()s a sufficient number of additional entries into the HashMap to
>> cause a resize/rehash.  As a result, computeIfAbsent() doesn't add the new entry
>> at the proper place in the HashMap.
>> 
>> While one should not (mis)use the mappingFunction in this way,
>> HashMap.computeIfAbsent() (and similar HashMap methods which accept Lambda
>> expressions) could check for and throw a ConcurrentModificationException on a
>> "best-effort" basis, similar to iterators.  This is already done in bulk
>> operations HashMap.forEach() and HashMap.replaceAll().
>> 
>> I think it's also worth making mention of this in the JavaDoc.
> 
> I think we need to have the specification discussion *first* before we decide what HashMap should do with side-effecty computations that are passed to computeIfAbsent and friends. Unfortunately the API specification for Map.computeIfAbsent is largely silent about what should happen. I don't know whether that means that the result should be undefined, or that passing a function with side effects is implicitly allowed and should therefore be defined.
> 
> I'd think it would be quite unpleasantly surprising to find that passing a mapping function with side effects -- especially on keys other than the current operation -- results in essentially a corrupted map. Then again, I'm surprised that somebody would think to pass a mapping function that does have side effects. However, this is what people do, and they expect the library to behave reasonably.
> 
> I can think of an (only moderately contrived) use case that's probably behind the bug report. Suppose I want to have a map that starts empty but which is lazily initialized, and when it's initialized, it should contain entries for all keys A, B, C, D, and E. Furthermore, it should be lazily initialized when any one of these keys is put into the map. Of course, you can write this out easily yourself. But hey, there's this new computeIfAbsent() method that should let me do
> 
>    map.computeIfAbsent(key, k -> {
>        /* put all entries A..E except k */
>        return value_for_k;
>    });
> 
> Based on the @implSpec for Map.computeIfAbsent, I'd expect this to work. And if your map inherits the Map.computeIfAbsent default implementation, it probably does work. Indeed, the workaround given in the bug report is essentially to implement your own method that duplicates the logic of the @implSpec and the default method. So, I'm leaning toward specifying that side effects should be supported, and that ConcurrentModificationException should not be thrown.
> 
> That implies that HashMap will have to detect the concurrent modification and deal with it instead of throwing an exception.
> 
> If we do clarify the spec to support this case, it probably shouldn't make any guarantees about what should happen if the mapping function puts the *same* key. That is, if
> 
>    map.computeIfAbsent(key, k -> {
>        put(k, value1);
>        return value2;
>    });
> 
> it seems reasonable that it not be defined which of value1 or value2 ends up getting mapped to the key.
> 
> s'marks
> 
> 
>> Here's an example of what might be done, using computeIfAbsent() as an example:
>> 
>> http://cr.openjdk.java.net/~bchristi/8071667/webrev.0/
>> 
>> I would update HashMap and Hashtable.  It looks like
>> ConcurrentHashMap.computeIfAbsent() already forbids such usage, stating that the
>> computation "must not attempt to update any other mappings of this map."
>> 
>> 
>> Comments on this approach?
>> 
>> Thanks,
>> -Brent
>> 
>> 1. https://bugs.openjdk.java.net/browse/JDK-8071667
>>    "HashMap.computeIfAbsent() adds entry that HashMap.get() does not find."