RFR : 8016446 : (m) Add override forEach/replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap

[Remi Forax]

On 06/14/2013 11:20 AM, Paul Sandoz wrote:
> On Jun 13, 2013, at 11:56 PM, Remi Forax <forax at univ-mlv.fr> wrote:
>
>> On 06/13/2013 04:47 PM, Paul Sandoz wrote:
>>> On Jun 13, 2013, at 4:06 PM, Remi Forax <forax at univ-mlv.fr> wrote:
>>>>>> There is a difference between an Iterator/forEach and a spliterator/stream,
>>>>>> with a stream you know that the called lambdas will not interfere and mutate the source collection.
>>>>>>
>>>>> You do? I don't think there is any conceptual difference between the following w.r.t. interference:
>>>>>
>>>>>    ArrayList l = ...
>>>>>    l.stream().filter(...).forEach(e -> l.add(e));
>>>>>    l.spliterator().forEachRemaining(e -> l.add(e));
>>>>>
>>>>> and:
>>>>>
>>>>>    ArrayList l = ...
>>>>>    l.forEach(e -> l.add(e));
>>>>>    l.iterator().forEachRemaining(e -> l.add(e));
>>>>>
>>>>> Of course we have (or will have) strong wording saying don't implement interfering lambdas, but we still have to check for co-modification in the traversal methods of ArrayList spliterator.
>>>> Isn't it because if you remove an element from an ArrayList while iterating you can see a stale value ?
>>>> While with a HashMap, if you have only one thread, you can not see a stale entry ?
>>> Assuming just one thread do you agree that in all of the above examples the only way the list can be interfered with is by the Consumer instance e -> l.add(s) ?
>> yes, as I said to Mike, what is important IMO is that the semantics of forEach and the semantics of for(:) should be the same.
>>
>>>
>>>> So a spliterator on HashMap can only check the modCount at the end unlike the one on ArrayList that need to check at each step.
>>>>
>>> The ArrayList.spliterator.forEachRemaining implementation also checks at the end.
>> Given that a spliterator is something new which is weaker than an iterator, the semantics can be relaxed.
> In terms of traversal I don't see a spliterator from an ArrayList being weaker than an iterator from an ArrayList. I would argue Iterator has a weaker model of traversal.

I was taking about spliterator in general, not the one of ArrayList 
which can not be weaker as I have explained below.

>
> The following does not throw CME:
>
>              List<Integer> l = new ArrayList<>(Arrays.asList(1, 2));
>              for (Integer i : l) {
>                  l.remove(1);  // 2 is never encountered
>              }
>
> Where as the following does:
>
>              List<Integer> l = new ArrayList<>(Arrays.asList(1, 2, 3));
>              for (Integer i : l) {
>                  l.remove(1);
>              }
>
> Because the hasNext implementation does not check for modification. It's sad this also occurs for the default implementation of Iterable.forEach :-(
>
> This behaviour sucks.

devil advocate: why exactly, the iteration is finished when you remove 
the element ?

> It would be a shame for overriding forEach/forEachRemaining implementations to conform to such behaviour when they can implement stronger/consistent failure guarantees.

While I could agree with you in theory, in practice I have seen several 
times codes that rely on this behaviour,
usually there is a bunch of method calls between the for loop and the 
list.remove() so this is not something that can be easily fixed.
And because I think it's more important that users should be able to use 
either for(:) or forEach without thinking too much,
because otherwise nodoby will "modernize" their code, we have no choice 
but stick to the iterator behaviour for forEach
i.e. no modCount check at the end.

>
>
>> For ArrayList, because you can see a stale entry if you mutate during a forEachRemaining,
>> you have no choice but checking at each step.
> A CME does not make any hard guarantees, thus cannot be used for correctness. I think this comes down to a balance of performance and how fast the fail-fast should be.

yes, declare modCount volatile and your performance vanish :(

>   I can definitely see an argument for failing ASAP so as not to report dodgy data.
>
> Paul.

cheers,
Rémi

>
>> And because the semantics is not tight to the iterator one,
>> I agree that you can also perform a check at the end.
>> For HashMap.spliterator.forEachRemaining,  because you can not see stale entry (without concurrency),
>> you can only perform a check at the end. It's IMO also a valid semantics.
>>
>>> Paul.
>> Rémi
>>