Page History

Objects of a class can be ordered relative to one another. One way to do this is for the class to implement the Comparable interface. Library classes like TreeSet or TreeMap will Choosing to implement the Comparable interface represents a commitment that the implementation of the compareTo() method adheres to the general contract for that method regarding how the method is to be called. Library classes such as TreeSet and TreeMap accept Comparable objects and use their the associated compareTo() methods to sort themthe objects. However, a class that implements the compareTo() method in an unexpected way could can cause unexpected results, like a TreeSet reporting it does not contain an object that it really does contain, that could lead to exploitable behaviorundesirable results.

The general usage contract for compareTo() has been put forth verbatim from the Java specification:Java SE 8 API [API 2014] states that

1. The implementor must ensure sgn(x.compareTo

...

1. (y)) == -sgn(y.compareTo

...

1. (x)) for all x and y. (This implies that x.compareTo

...

1. (y) must throw an exception

...

1. if y.compareTo

...

1. (x) throws an exception.)
2. The implementor must also ensure that the relation is transitive: (x.compareTo

...

1. (y) > 0 && y.compareTo(z)

...

1. > 0) implies x.compareTo(z)

...

1. > 0.
2. Finally, the implementor must ensure that x.compareTo

...

1. (y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))

...

1. for all z.
2. 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.

Implementations must never violate any of the first three conditions when implementing the compareTo() method. Implementations should conform to the fourth condition whenever possibleDo not violate any of five conditions while overriding the compareTo method.

Noncompliant Code Example (Rock-Paper-Scissors)

This noncompliant code example violates the third condition in the contract.
Consider a Card that considers itself equal to any card of the same suit; otherwise it orders based on rank.program implements the classic game of rock-paper-scissors, using the compareTo() operator to determine the winner of a game:

public final class CardGameEntry implements Comparable {
  private String suit;public enum Roshambo {ROCK, PAPER, SCISSORS}
  private intRoshambo rankvalue;

  public CardGameEntry(String s, int rRoshambo value) {
    if (s == null)
      throw new NullPointerException();
    suit = s;
    rank = rthis.value = value;
  }

  public booleanint equalscompareTo(Object othat) {
    if (o!(that instanceof CardGameEntry)) {
      Card c=(Card)o;
      return suit.equals(c.suit) || (rank == c.rankthrow new ClassCastException();
    }
    returnGameEntry false;
  }

  //this method violates its contract
  public int compareTo(Object o){t = (GameEntry) that;
    ifreturn (o instanceof Card){
      Card c=(Card)o;
      if(suit.equals(c.suit)) return 0;value == t.value) ? 0
      return c.rank - rank;
    }
    throw new ClassCastException();
  }

  public static void main(String[] args) {
    Card a = new Card("Clubs", 2);: (value == Roshambo.ROCK && t.value == Roshambo.PAPER) ? -1
      : (value == Roshambo.PAPER && t.value == Roshambo.SCISSORS) ? -1
    Card b =: new Card("Clubs", 10);
    Card c = new Card("Hearts", 7);
    System.out.println(a.compareTo(b)); //returns 0
    System.out.println(a.compareTo(c)); //returns a negative number
    System.out.println(b.compareTo(c)); //returns a positive number(value == Roshambo.SCISSORS && t.value == Roshambo.ROCK) ? -1
      : 1;
  }
}

However, this game violates the required transitivity property because rock beats scissors, scissors beats paper, but rock does not beat paper.

Compliant Solution

...

(Rock-Paper-Scissors)

This compliant solution implements the same game without using the Comparable interface:Make sure you fulfill the contract, and make sure your corresponding equals method matches with compareTo.

publicclass finalGameEntry class{
 Card implementspublic Comparable{
enum Roshambo private String suit;{ROCK, PAPER, SCISSORS}
  private intRoshambo rankvalue;

  public CardGameEntry(String s, int rRoshambo value) {
    if (s == null)
      throw new NullPointerException();
    suit = s;
    rank = rthis.value = value;
  }

  public booleanint equalsbeats(Object othat) {
    if (o!(that instanceof CardGameEntry)) {
      Card c=(Card)othrow new ClassCastException();
    }
  return suit.equals(c.suit) && (rank GameEntry t == c.rank);
    }(GameEntry) that;
    return false;
  }

  //this method fulfills its contract
  public int compareTo(Object o){
(value == t.value) ? 0
      if: (ovalue instanceof Card){
      Card c=(Card)o;
      if(suit.equals(c.suit)) return c.rank - rank;== Roshambo.ROCK && t.value == Roshambo.PAPER) ? -1
      return: suit.compareTo(c.suit);
    }
    throw new ClassCastException();
  }

  public static void main(String[] args) {
    Card a = new Card("Clubs", 2);
    Card b = new Card("Clubs", 2);
    Card c = new Card("Hearts", 7);
    System.out.println(a.compareTo(b)); //returns 0
    System.out.println(a.compareTo(c)); //returns a negative number
    System.out.println(b.compareTo(c)); //returns a negative number(value == Roshambo.PAPER && t.value == Roshambo.SCISSORS) ? -1
      : (value == Roshambo.SCISSORS && t.value == Roshambo.ROCK) ? -1
      : 1;
  }
}

Risk Assessment

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

Automated Detection

TODO

References

Automated detections of violations of this rule is infeasible in the general case.

Related Guidelines

Bibliography

...

Image Added Image Added Image AddedJava API