MET14-J. Follow the general contract when implementing the compareTo() method

Choosing to implement the Comparable interface represents a commitment that the implementation of the compareTo() method adheres to the general usage contract for that method. Library classes such as TreeSet and TreeMap accept Comparable objects and use the associated compareTo() methods to sort the objects. However, a class that implements the compareTo() method in an unexpected way can cause undesirable results.

The general usage contract for compareTo() from Java SE 6 API [[API 2006]] states that

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. (This implies that x.compareTo(y) must throw an exception iff y.compareTo(x) throws an exception.)

The implementor must also ensure that the relation is transitive: (x.compareTo(y) > 0 && y.compareTo(z) > 0) implies x.compareTo(z) > 0.

Finally, the implementor must ensure that x.compareTo(y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

It is strongly recommended, but not strictly required that (x.compareTo(y) == 0) == x.equals(y). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return either -1, 0, or 1 depending on whether the value of the expression is negative, zero or positive.

Never violate any of the first three conditions when implementing the compareTo() method. Implementations should conform to the fourth condition whenever possible.

Noncompliant Code Example

This program implements the classic game of Roshambo, using the compareTo() operator to determine the winner of a game.

class GameEntry implements Comparable {
  public enum Roshambo {ROCK, PAPER, SCISSORS}
  private Roshambo value;

  public GameEntry(Roshambo value) {
    this.value = value;
  }
  
  public int compareTo(Object that) {
    if (!(that instanceof Roshambo)) {
      throw new ClassCastException();
    }
    GameEntry t = (GameEntry) that;
    return (value == t.value) ? 0
      : (value == Roshambo.ROCK && t.value == Roshambo.PAPER) ? -1
      : (value == Roshambo.PAPER && t.value == Roshambo.SCISSORS) ? -1
      : (value == Roshambo.SCISSORS && t.value == Roshambo.ROCK) ? -1
      : 1;
  }
}

However, this game violates the notion of transitivity, since Rock beats Scissors, Scissors beats Paper, but Rock does not beat Paper.

Compliant Solution

This compliant solution implements the game, but does not use the Comparable interface.

class GameEntry {
  public enum Roshambo {ROCK, PAPER, SCISSORS}
  private Roshambo value;

  public GameEntry(Roshambo value) {
    this.value = value;
  }
  
  public int beats(Object that) {
    if (!(that instanceof Roshambo)) {
      throw new ClassCastException();
    }
    GameEntry t = (GameEntry) that;
    return (value == t.value) ? 0
      : (value == Roshambo.ROCK && t.value == Roshambo.PAPER) ? -1
      : (value == Roshambo.PAPER && t.value == Roshambo.SCISSORS) ? -1
      : (value == Roshambo.SCISSORS && t.value == Roshambo.ROCK) ? -1
      : 1;
  }
}

Risk Assessment

Violating the general contract when implementing the compareTo() method can result in unexpected results, possibly leading to invalid comparisons and information disclosure.

Automated Detection

The Coverity Prevent Version 5.0 MUTABLE_COMPARISON checker can detect the instances where compareTo method is reading from a non constant field. If the non-constant field is modified, the value of compareTo might change, which may break program invariants.

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this guideline on the CERT website.

Other Languages

This guideline appears in the C++ Secure Coding Standard as ARR40-CPP. Use a valid ordering rule.

Bibliography

[[API 2006]] method compareTo()
[[JLS 2005]]

MET13-J. Classes that define an equals() method must also define a hashCode() method      05. Methods (MET)      MET15-J. Do not use deprecated or obsolete classes or methods