2
\$\begingroup\$

My question is about the equals() method. Most people implement equals() to start like:

@Override public boolean equals(Object o) {
    if (this == o) { return true; }
    if ( (o == null) || !(o instanceof MyClass) ) { return false; }

    ...

The !(o instanceof MyClass) line here can be very limiting. Once a class with such an equals method is wrapped in another class, it is no-longer equal to itself! Consider the following function and wrapper class. It works like Collections.unmodifiableList(x), only I made an UnList interface that extends List to deprecate each mutator method in addition to making the method throw an UnsupportedOperationException.

/** Returns an unmodifiable version of the given list. */
public static <T> UnList<T> un(List<T> list) {
    if (list == null) { return UnList.empty(); }
    if (list instanceof UnList) { return (UnList<T>) list; }
    if (list.size() < 1) { return UnList.empty(); }

    // Declare a real class instead of an anonymous one so that we can
    // check the class of the object passed to the equals() method and
    // compare the inner objects if that's appropriate.
    class UnListWrapper<E> implements UnList<E> {
        private final List<E> inner;
        private UnListWrapper(List<E> i) { inner = i; }
        @Override public UnListIterator<E> listIterator(int index) {
            return un(inner.listIterator(index));
        }
        @Override public int size() { return inner.size(); }
        @Override public E get(int index) { return inner.get(index); }

        @Override public int hashCode() { return inner.hashCode(); }
        @Override public boolean equals(Object o) {
            // Typical implementations of equals() check the exact
            // class of the passed object so actually give up the
            // inner, wrapped object to allow the class check to pass
            // in those cases.  For best results, use Sorted
            // collections that don't call this method.
            return inner.equals((o instanceof UnListWrapper)
                                ? ((UnListWrapper) o).inner
                                : o);
        }
    };
    return new UnListWrapper<>(list);
}

When I wrote the above equals() method, I thought that I was doing a good thing by broadening the scope where the equals method could still work. But sometimes failing fast can be kinder than working half the time.

Imagine a bunch of lists with the above implementation being thrown into a HashSet. Some are wrapped in the UnListWrapper, some are not. If you put in two equivalent unwrapped lists, or put the unwrapped list in first, then you add the wrapped one, the equals method in the wrapped list will compare its inner list and see that they are the same. But if you add the wrapped list followed by an unwrapped one, the equals method of the unwrapped List could reject the wrapped one as being the wrong class, and you'd end up with two of the same List in your set.

This order-dependent problem can be hard to test for and is an awful kind of problem to debug. So now I'm thinking that it's kinder to implement equals to fail fast:

        @Override public boolean equals(Object o) {
            return inner.equals(o);
        }

Then if someone writes a List with an instanceof MyClass equals() implementation, they will have to fix their equals to use instanceof List which is probably better all the way around.

On the other hand, the end user might not have control over the List implementation and might not put it in a HashSet and would appreciate things working half the time.

I'm at the edge of my experience here and could use some better informed opinions. If this has no right answer, is there a best wrong answer?

P.S. I'm using the TreeSet and TreeMap implementations from Clojure so that people using this utility don't have to worry about equals() and hashCode(). But just writing JUnit tests, having a working equals() is extremely useful, 'cause Java is designed to be used that way, and a lot of Java expects it, even if using a separate Comparator is generally superior.

\$\endgroup\$
5
\$\begingroup\$

This statement here:

The !(o instanceof MyClass) line here can be very limiting. Once a class with such an equals method is wrapped in another class, it is no-longer equal to itself!

is not true. Consider this code taken from AbstractList:

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

That code works for almost all List implementations out there, including LinkedList, ArrayList, etc. The !(o instanceof List). Since AbstractList, ArrayList, LinkedList, etc. are all instances of List, they will all 'pass' that "not instance" test, and will be tested with matching ListIterator sequences.

Also, not that there is no need to test for o == null either, in your question you say "Most people implement equals() to start like...." :

if ( (o == null) || !(o instanceof MyClass) ) { return false; }

Well, that o == null check is redundant because null is not an instance of any class, so the line can just be:

if ( !(o instanceof MyClass) ) { return false; }

The bottom line, is that, since your UnList implements List, the list it wraps should have a meaningful implementation of both equals(..) and listIterator() already, and, as a consequence, there should be no need to re-implement or override the equals(...) method at all.

If your equals(...) method is not working using its base/underlying implementation, then you have a bug somewhere else.

I would simply use hashCode() and equals() methods directly on the UnList interface using default methods that caller the inner version, like you have done with most other methods.

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ Wow - this is incredibly helpful - thanks! 1. I edited the question to say instanceof MySpecificImplementation because you assumed that people chose the most general interface, and I assumed they picked the most specific implementation. Your assumption is better, but I've seen a lot of bad code. Heck, that assumption was probably my biggest problem! 2. I don't understand your last paragraph. I thought I was defensive programming to never return a null instead of an empty collection (Josh Bloch Item 43). \$\endgroup\$ – GlenPeterson Apr 29 '15 at 12:12
  • \$\begingroup\$ @GlenPeterson - all the last paragraph is saying, is that, if someone were to do: UnList<Integer> ul = UnList.un(null); then you would get NPE's all over the place. .... but, that's wrong.... you won't. let me edit my answer. \$\endgroup\$ – rolfl Apr 29 '15 at 13:29
2
\$\begingroup\$

Your interface extends List therefore it should obey List contract.

Contract of List.equals is here.

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ?e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.

And this is from Object.equals, which List.equals overrides.

The equals method implements an equivalence relation on non-null object references: ... It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.

So there is no one-sided equality. If it is one-sided, that is it's asymmetric, then it's just wrong.

Since all Lists should have the same equals you can, and really should, just do :

@Override
public boolean equals(Object o) {
    return inner.equals(o);
}

EDIT in response to comment

Imagine Point3D extends Point2D by adding a z member variable. Now new Point2D(3, 5).equals(new Point3D(3, 5, 7)) returns true, but new Point3D(3, 5, 7).equals(new Point2D(3, 5)) returns false.

Above equals method would be broken. If you're overriding an equals implementation that isn't Object.equals you are most likely doing something very wrong.

This is what goes wrong in production if you use a broken equals:

static int undefinedBehavior(Set s) {
    assert s.isEmpty();
    s.add(new Point3D(3, 5, 7));
    s.add(new Point2D(3, 5));
    return s.size();
}

In this case you should respect the contract of List.equals. Same goes for Map, Set etc. If you have another real-life case where you think you need to modify equals behavior, such that it won't be reflexive anymore; it would be an interesting codereview question, I definitely would like to have a look at it.

Comparator is a partial order. equals is an equivalence relation. Although all partial orders also define an equivalence, not all equivalences has an accompanying partial order. An example of an equivalence relation is .NET's IEqualityComparer<T>. Which doesn't really have a Java equivalent.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You are right about one-sided equality, but that's not the whole story. Imagine class Point2D with member variables x and y, with the appropriate equals() and hashcode() implementation. Imagine Point3D extends Point2D by adding a z member variable. Now new Point2D(3, 5).equals(new Point3D(3, 5, 7)) returns true, but new Point3D(3, 5, 7).equals(new Point2D(3, 5)) returns false. Equality in Java becomes one-sided pretty much any time inheritance is involved. Comparator is designed for context-sensitive ordering and guaranteed reflexive equality. equals(Other o) is not. \$\endgroup\$ – GlenPeterson May 19 '15 at 12:24
1
\$\begingroup\$

Is one-sided equality more helpful or more confusing than quick failure?

If you mean a.equals(b) but not b.equals(a), then don't even think about it.... it's a sure way to disaster.

Once a class with such an equals method is wrapped in another class, it is no-longer equal to itself!

This may be on purpose - imagine a (sanely implemented) Properties based on a HashMap<String, String>. A Properties just wraps it, but is not HashMap, so they should never be equal.

If you really want an unmodifiable List, then implement List, possibly by extending AbstractList or by using Guava's ForwardingList and let equals and hashCode work just like they do.

if (list.size() < 1) { return UnList.empty(); }

I guess, testing zero would be clearer, however, there's list.isEmpty.

@Override public UnListIterator<E> listIterator(int index) {
     return un(inner.listIterator(index));
}

This is wrong, as you expose Iterator#remove() (and add() and set()). Here, Guava offers UnmodifiableListIterator.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.