[External] : Re: ReversibleCollection proposal

Wed Apr 28 05:19:29 UTC 2021

On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote:
> On Tuesday, April 27, 2021 11:25 CEST, Peter Levart <peter.levart at gmail.com> wrote:
>> Now just some of my thoughts about the proposal:
>>
>> - SortedSet.addFirst/.addLast - I think an operation that would be used
>> in situations like: "I know this element should always be greater than
>> any existing element in the set and I will push it to the end which
>> should also verify my assumption" is a perfectly valid operation. So
>> those methods throwing IllegalStateException in case the invariant can't
>> be kept seem perfectly fine to me.
> 
> This was raised before and addressed by Stuart in [0]:
> "An alternative as you suggest might be that SortedSet::addFirst/addLast could throw
> something like IllegalStateException if the element is wrongly positioned.
> (Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity
> restriction.) This seems error-prone, though, and it's easier to understand and
> specify that these methods simply throw UOE unconditionally. If there's a good use
> case for the alternative I'd be interested in hearing it though."

Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's 
my response that's quoted above.

Some further thoughts on this.

This is an example where, depending on the current state of the collection, the 
method might throw or it might succeed. This is useful in concurrent collections 
(such as the capacity-restricted Deque above), where the caller cannot check 
preconditions beforehand, because they might be out of date by the time the 
operation is attempted. In such cases the caller might not want to block, but 
instead it might catch the exception and report an error to its caller (or drop the 
request). Thus, calling the exception-throwing method is appropriate.

Something like SortedSet::addLast seems different, though. The state is the *values* 
of the elements already in the collection. This is something that can easily be 
checked, and probably should be checked beforehand:

     if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0)
         sortedSet.add(e);
     else
         // e wouldn't be the last element, do something different

Now this is a fair bit of code, and it would be shorter just to call 
sortedSet.addLast(e). But does that actually help? What if e is already in the set 
and is the last element? Is catching an exception really what we want to do if e 
wouldn't be the last element? Maybe we'd want to do nothing instead. If so, catching 
an exception in order to do nothing is extra work.

Again, I'd like to hear about use cases for a conditionally-throwing version of 
addLast et. al. I don't want to be limited by failure of imagination, but it does 
seem like this kind of behavior would be useful only in a narrow set of cases where 
it happens to do exactly the right thing. Otherwise, it just gets in the way, and 
its behavior is pretty obscure. So, color me skeptical.

> [0] https://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076518.html

[1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076505.html

>> - ReversibleCollection.addFirst/.addLast are specified to have void
>> return type. This works for List and Deque which always add element and
>> so have no information to return. OTOH Collection.add is specified to
>> return boolean to indicate whether collection was modified or not, but
>> Set modifies the specification of that method a bit to be: return false
>> or true when Set already contained an element equal to the parameter or
>> not. So ReversibleCollection.addFirst/.addLast could play the same
>> trick. for List(s) and Deque(s) it would always return true, but for
>> ReversibleSet(s) it would return true only if the set didn't contain an
>> element equal to the parameter, so re-positioning of equal element would
>> return false although the collection was modified as a result.
> 
> If addFirst/addLast were to return boolean, Deque would no longer compile due to its existing methods being incompatible with the new ones.

Right, the current proposal copies the addX method signatures from Deque into 
ReversibleCollection.

I think it was Mike Duigou who said that a method that returns void is a missed 
opportunity. The idea is, the library probably has some useful bit of information it 
can return. If the caller doesn't need it, the caller can just ignore it.

On Collection::add returning a boolean, most calls to this ignore the return value, 
and the boolean "did this collection change as a result of this call?" is only 
occasionally useful. Sometimes it can be used for little tricks, such as an easy way 
to determine if a stream contains all unique elements:

     stream.allMatch(new HashSet<>()::add)

But really, the boolean return value doesn't seem all that useful.

Still, it could be added. The methods couldn't be called addFirst/addLast as Anthony 
pointed out, as this would clash with those methods already on Deque. However, Deque 
already contains boolean-returning offerFirst/offerLast methods! We could use those 
instead of addFirst/addLast, right?

Maybe. There are several different concerns here.

* Collection::add says:

"Returns true if this collection changed as a result of the call. (Returns false if 
this collection does not permit duplicates and already contains the specified element.)"

* Deque::add says:

"Inserts ... if it is possible to do so immediately without violating capacity 
restrictions, returning true upon success and throwing an IllegalStateException if 
no space is currently available."

* Deque::offerFirst/Last say:

"Inserts ... unless it would violate capacity restrictions. ... Returns: true if the 
element was added to this deque, else false"

* LinkedHashSet::offerX return value

If it's like add(), then it returns true if the element was added to the set, false 
if it wasn't added (even if repositioned). But Collection::add says true if this 
collection changed. Is repositioning a change? It isn't from the standpoint of 
equals(), but it is from the standpoint of ConcurrentModificationException. (At 
least that's true of access-ordered LinkedHashMap.)

* SortedSet::offerX return value

If it's like add(), then it returns true if the element was added to the set, false 
otherwise. But what about the case where the element isn't in the set, but adding it 
would not put it in the requested position?

  - if it's added but not in the requested position, that weakens the concepts of 
first/last

  - if it's not added and returns false, this clashes with other sets, where a false 
return means "not added because already in the set" but an equal element is present 
in the set after the call

Also, what if the element is already in the set but is in the wrong position?

***

The Deque class specification [2] has a nice table of the different operations, a 
subset of which is as follows:

              Exception       Special Value
     Insert   addFirst(e)     offerFirst(e)
     Remove   removeFirst()   pollFirst()
     Examine  getFirst()      peekFirst()

The original proposal takes the operations straight down the first column. It would 
be strangely inconsistent to take offerX from the second column and removeX and getX 
from the first column.

[2] https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/Deque.html

Using offerX certainly has the right "shape" of returning a boolean. The central 
question is what the boolean means. The problem is that Deque::offerX has a specific 
meaning that isn't operative in most collections, and we really want something more 
like Collection::add, but these clash. Trying to wedge in weird semantics of 
LinkedHashSet element reordering and SortedSet's special casing just makes things worse.

Finally, it's seems error-prone to have a conventional (i.e., non-concurrent) 
collection that tells you it has refused to insert an element by returning a 
boolean. It's too easy to ignore. Perfectly working code might silently break if the 
collection type is changed. (I'm reminded of various boolean-returning operations -- 
not queries -- on java.io.File, like delete and mkdir, which are a continual source 
of errors.)

I'll think about this more, but it doesn't seem promising.

s'marks