RFR [15] 6394757: rev2: AbstractSet.removeAll semantics are surprisingly dependent on relative sizes

[Stuart Marks]

> You say:
> 
>     The issue of membership semantics is part of the original design.
> 
> I agree, but only to the point of identifying inconsistent membership semantics as a source of non-conformance. What is not part of the original design is allowing a broader range of membership semantics to be conformant, which I assume is what you want.

I'm not using the concept of "conformance" so that's unrelated to what I want.

> Another point of disagreement involves the specification of membership, especially in the case of Set, which I believe is where the problems arise.
> 
> I’m not completely sure what you are thinking, but it sounds like you believe that membership is defined by the implementation of the contains() method. I believe that is incorrect (i.e., not implied by the current specification).

No, I don't believe that membership is defined by the implementation of 
contains(). I'm not sure where that came from; it might be misapprehension or 
miscommunication.

> Consider the “more formal” definition of contains():
> 
>     More formally, returns true if and only if this set contains an element e such that Objects.equals(o, e).
> 
> Clearly, it would make no sense to define the contains() method in terms of itself. But it does make sense to say that the current state of a Set is a mathematical set of instances such that no pair of instances returns true from e1.equals(e2). I believe that is what the specification is trying to say, however imperfectly.

Yes, this much makes sense. Note that this embodies the membership contract of 
typical equals-based sets. Unfortunately, other sets (such as SortedSet) make 
some statements that imply that membership is determined by the comparator, they 
don't make any statments about how this affects contains(). The specification 
for SortedSet.contains(o) should say,

     Returns true if and only if this set contains an element e such that
     compare(o, e) == 0.

That it doesn't is yet another spec bug.

> Consider the classic example, a TreeSet of Strings that is case-insensitive. If I add one string “hello” to an empty TreeSet, how many elements does it contain? The specification of add() says one. The size() method returns one. The iterator returns one element. But the contains() method returns true for multiple non-equal objects. Oops.

The reason this seems wrong is that you're calling contains() on two "non-equal" 
objects, but your statement's use of "non-equal" means you're using a different 
notion of equivalence from that used by the TreeSet. Since the TreeSet from your 
example uses case-insensitivity, those multiple "non-equal" objects on which 
you're calling contains() are in fact equivalent, so the result makes sense.

> What I conclude from this exercise:

Does this mean you're close to conclusing this argument? :-)

I'll call out just one of your conclusions, since the other seem to be based on 
an incorrect assumption that I believe that the membership semantics are defined 
by the implementation of the contains() method, or that I'm proposing to do so. 
That conclusion is:

> The problems of non-conforming collections are larger than you think. It is *not* the case that all of the basic axioms still apply.


Well I don't know how you know how large I think the problem is, but I'll agree 
it's pretty large. It's certainly much larger than the changeset that is 
currently under review.

Regarding the basic axioms, I'll return to some wording from SortedSet:

     The behavior of a sorted set is well-defined even if its ordering is
     inconsistent with equals; it just fails to obey the general contract
     of the Set interface.

The "well-defined" clause means that the basic axioms apply.

However, I'll admit that the current wording of the spec does not support this! 
I'm assuming that there will be future changes to SortedSet et. al. that 
strengthen its notion of membership contract differing from other sets, and 
further that its add(), contains(), remove(), etc. methods all need to be 
adjusted to use this different membership contract.

Sorry if this wasn't clear. I know I've said this elsewhere, but possibly not on 
this thread or its predecessors.

s'marks