SEI CERT Oracle Coding Standard for Java

Space shortcuts

Page tree

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 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 contract for compareTo() from Java SE 8 API [API 2014] states that

  1. 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 if y.compareTo(x) throws an exception.)
  2. The implementor must also ensure that the relation is transitive: (x.compareTo(y) > 0 && y.compareTo(z) > 0) implies x.compareTo(z) > 0.
  3. Finally, the implementor must ensure that x.compareTo(y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)) for all z.
  4. 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 possible.

Noncompliant Code Example (Rock-Paper-Scissors)

This program implements the classic game of rock-paper-scissors, 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 GameEntry)) {
      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 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:

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 GameEntry)) {
      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 cause unexpected results, possibly leading to invalid comparisons and information disclosure.

Rule

Severity

Likelihood

Remediation Cost

Priority

Level

MET10-J

Medium

Unlikely

Medium

P4

L3

Automated Detection

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

Tool
Version
Checker
Description
CodeSonar
8.1p0

JAVA.CLASS.MCS

Missing Call to super (Java)

Coverity7.5FB.RU_INVOKE_RUNImplemented

Related Guidelines

SEI CERT C++ Coding Standard

CTR57-CPP. Provide a valid ordering predicate

MITRE CWE

CWE-573, Improper Following of Specification by Caller

Bibliography

[API 2014]

Interface Comparable<T>
Method compareTo()

[JLS 2005]



18 Comments

  1. Dhruv Mohindra

    I think it may/may not lead to info disclosure depending on the logic. Usually it finds extensive use in sorting and the like.

    —
    Note from the API regarding one point mentioned in the intro:

    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."

    1. David Svoboda

      Having a partial ordering (eg a compare where ((compare(x,y) == 0) != (x.equals(y))) is a useful trait, for instance if you want to sort items by equivalence classes. For instance, you can sort cards by rank regardless of suit. Are there any Java standard libraries that assume or require total ordering?

      BTW I recently created CTR57-CPP. Provide a valid ordering predicate, which you should reference in an 'Other Languages' section.

  2. David Svoboda

    Thanks, Rob. I have one comment. The exception to this rule suggests to me that perhaps this should either:

    • be a recommendation, since the exception is not automatically enforceable
    • be a more limited rule, such as "Adhere to the comparabble interface for items in a Set or Map".

    Maybe we need both. However I have marked this rule as complete, so while I encourage Mr. Neville to make the change, he does not need to do so for the purpose of this assignment.

    1. Dhruv Mohindra

      David, IIRC this is to go into the recommendation 'Follow the contracts of methods' or similar. I think one single example that violates all the contracts (equals, compareto, hashcode...) and one compliant solution will save a lot of space. What do you feel?

      1. David Svoboda

        If you want to be illustrative, yes one NCCE that violates everything works. If you want to make a plausible NCCE that does interesting (and icorrect) behavior, you probably should only violate one of the conditions. Ideally ou'd have one NCCE for each condition.

        1. Dhruv Mohindra

          Perhaps we could have main() invoke the different methods. The idea is to eliminate common code as far as possible. I'll give it a try when this guideline is frozen. Thanks.

    2. Robert Seacord

      Try to narrow the rule to be enforceable. One of the things I've learned about recommendations, is that static analysis tool vendors are going to try to enforce compliance with them as well so we'll still have the issue with false positives.

    3. David Svoboda

      Some meail that should be added to this discussion. From rcs:

      I think you can probably include all of this information as part of the same rule. This will help analysis tool writers to limit false positives.

      Is part of the problem the usage? Can you have one rule that says implement comparable entirely and don't invoke some method on some subset of classes that don't implement comparable?

      rCs

      ----- Original Message -----
      From: David Svoboda <svoboda@cert.org>
      To: Robert Seacord; David Svoboda <svoboda@andrew.cmu.edu>
      Sent: Fri Apr 03 07:30:52 2009
      Subject: Re: question on MET34-J

      I had one idea. I'm not sure when the exception would apply, but I can
      think of one instance where it definitely doesn't. Any object that is
      inserted into a Set or Map must enforce the rule srictly (eg not fall
      under the exception). I'm wondering if maybe we should split this into a
      rule "Imp;lement comparable totally when inserting objects into a set or
      map" and a rec "implement comparable totallly + exception". I think that
      is technically correct, but strikes me as redundant. Coments?
      ~Dave

  3. David Neville

    I agree that equals and hashCode should go together in a single rule, since they should both be overriden together. The only problem with combining the rule for compareTo is that compareTo is a completely separate method - only objects that implement Comparable must implement it. It seems to me a pair of rules that (strongly) reference each other would be less unwieldy than one rule which would turn out to be more gargantuan than any I'm aware of on the site.

    I feel that separate code examples for equals, hashCode, and compareTo is a must for clarity, which is why a single rule would be so big.

    I agree that the rule should not be total, which is why I added the exception for compatibility issues. However, it seems to me that any class whatsoever that uses Comparable objects, from the past present or future, Sun a 3rd party or even a later programmer, would be likely to expect that Comparable objects follow the compareTo contract. Thus an object that wishes different functionality should not, as a rule with the caveat for compatibility, implement Comparable at all because of the potential for miscommunication, but instead use a different method/interface.

    1. Dhruv Mohindra

      For a casual reader, I don't think it matters too much whether they are in the same rule or different, as long as they are in the correct sequence. We can retain the readability and yet have them under two different topics. That said, many rules and recommendations have not been ordered keeping in mind a cover- to-end reader. It is simply impossible to do that during development but I think before the standard is frozen for release, it would be a good idea to determine what belongs together and what does not. I suspect, for tool vendors, separating the issues will be better. It's evident from their vulnerability catalogs.

      To some extent, I am (and David too I guess) only afraid of having to include several more guidelines that say "follow the contract of X method". But we might have to, if they result in frequent standalone coding errors.

  4. David Svoboda

    The exception seems valid to me, but it should be fleshed out, with a compliant code example at least. It is talking about partial ordering, a common mathematical concept. (Consider a set S. The set of all subsets of S has a partial ordering in the is-a-subset-of relation, in that there exists subsets S1 and S2 where neither is a subset of the other, but the relation matches the other requirements of an order relation.)

    1. Fred Long

      The rule has been reworded to say that only the first three conditions are required. Hence, the exception (about violating the fourth condition) is no longer an exception of the rule and has been removed.

  5. Philip Miller

    The first sentence of MET14-J., Objects of a class can be ordered relative to one another., should be eliminated. The recommendation itself is fine.

    1. Dhruv Mohindra

      I've shortened the sentence.

  6. Masaki Kubo

    The title uses "general contract" and the first sentence of the rule says "...general usage contract..." both of which is unclear. Is general usage contract what is defined in Java API specification?

    1. David Svoboda

      Yes. I changed the terminology for clarity in the intro.

  7. Mario Alviano

    I think there is a typo in the first line of compareTo() and beats() methods:

    if (!(that instanceof Roshambo)) {

    should be 

    if (!(that instanceof GameEntry)) {


    1. David Svoboda

      Fixed, thanks!