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 accept Comparable objects and use their compareTo() methods to sort them. However, a class that implements the compareTo() method in an unexpected way could cause unexpected results, like a TreeSet reporting it does not contain an object that it really does contain, that could lead to exploitable behavior.
The general usage contract for compareTo() has been put forth verbatim from the Java specification:
The implementor must ensure sgn(x.compareTo for all x and y. (This implies that x.compareTo
) == -sgn(y.compareTo
) must throw an exception iff y.compareTo throws an exception.)
The implementor must also ensure that the relation is transitive: (x.compareTo >0 && y.compareTo(z)>0) implies x.compareTo(z)>0.
Finally, the implementor must ensure that x.compareTo ==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.
Do not violate any of five conditions while overriding the compareTo method.
Noncompliant Code Example
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.
| Code Block | ||
|---|---|---|
| ||
public final class Card implements Comparable{
private String suit;
private int rank;
public Card(String s, int r) {
if (s == null)
throw new NullPointerException();
suit = s;
rank = r;
}
public boolean equals(Object o) {
if (o instanceof Card){
Card c=(Card)o;
return suit.equals(c.suit) || (rank == c.rank);
}
return false;
}
//this method violates its contract
public int compareTo(Object o){
if (o instanceof Card){
Card c=(Card)o;
if(suit.equals(c.suit)) return 0;
return c.rank - rank;
}
throw new ClassCastException();
}
public static void main(String[] args) {
Card a = new Card("Clubs", 2);
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
}
}
|
Compliant Solution
Make sure you fulfill the contract, and make sure your corresponding equals method matches with compareTo.
| Code Block | ||
|---|---|---|
| ||
public final class Card implements Comparable{
private String suit;
private int rank;
public Card(String s, int r) {
if (s == null)
throw new NullPointerException();
suit = s;
rank = r;
}
public boolean equals(Object o) {
if (o instanceof Card){
Card c=(Card)o;
return suit.equals(c.suit) && (rank == c.rank);
}
return false;
}
//this method fulfills its contract
public int compareTo(Object o){
if (o instanceof Card){
Card c=(Card)o;
if(suit.equals(c.suit)) return c.rank - rank;
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
}
}
|
Risk Assessment
Violating the general contract when overriding the compareTo() method can lead to unexpected results.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
|---|---|---|---|---|---|
MET30-J | low | unlikely | medium | P2 | L3 |
Automated Detection
TODO
References
Java API