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

[Brent Christian]

I prefer this approach of discouraging/preventing side-effects via CME, 
rather than allowing them.  Keep the functions "functional", as it were.

If there are situations where determining the mapping for one key 
necessitates making additional changes to the Map, that should be coded 
some other way.  IMO, sneaking extra work into computeIfAbsent() is too 
big a departure from how the method is intended to be used.

Regarding the default methods:

Would we be able to make a "best-effort" detection of comodification by 
checking for a change in size before and after calling mappingFunction? 
  Or are there other reasons we "cannot do anything" about the default 
methods?

Thanks,
-Brent

On 2/4/15 2:01 AM, Paul Sandoz wrote:
> 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."
>