[clang-tidy] Add check for classes missing -hash ⚠️

[stephanemoore]

Summary

Apple documentation states that:
"If two objects are equal, they must have the same hash value. This last
point is particularly important if you define isEqual: in a subclass and
intend to put instances of that subclass into a collection. Make sure
you also define hash in your subclass."
https://developer.apple.com/documentation/objectivec/1418956-nsobject/1418795-isequal?language=objc

In many or all versions of libobjc, -[NSObject isEqual:] is a pointer
equality check and -[NSObject hash] returns the messaged object's
pointer. A relatively common form of developer error is for a developer to
override -isEqual: in a subclass without overriding -hash to ensure that
hashes are equal for objects that are equal.

It is assumed that an override of -isEqual: is a strong signal for
changing the object's equality operator to something other than pointer
equality which implies that a missing override of -hash could result in
distinct objects being equal but having distinct hashes because they are
independent instances. This added check flags classes that override
-isEqual: but inherit NSObject's implementation of -hash to warn of the
potential for unexpected behavior.

The proper implementation of -hash is the responsibility of the
developer and the check will only verify that the developer made an
effort to properly implement -hash. Developers can set up unit tests
to verify that their implementation of -hash is appropriate.

Test Notes:
Ran check-clang-tools.

[Eugene.Zelenko]

clang-tools-extra/docs/ReleaseNotes.rst

105

Wrong place. Please move to new checks list (in alphabetical order).

[Eugene.Zelenko]

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

41

Should check if language is Objective-C. See ForbiddenSubclassingCheck.cpp as example. Will be good ensure that all Objective-C checks do this.

[stephanemoore]

Restrict ojbc-missing-hash to Objective-C language variants and fix sorting of
release notes.

[stephanemoore]

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

41

Thanks for calling this out; I tried using the check addition script and forgot to include this important conditional. I believe this has been resolved with my proposed changes.

clang-tools-extra/docs/ReleaseNotes.rst

105

Thanks for pointing this out. I believe I may have made an error while resolving merge conflicts. I believe this has now been resolved.

[aaron.ballman]

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

56

Do you think we could generate a fixit to add the hash method? Do you think we could even add a default implementation that returns the pointer to the object (assuming that's the correct default behavior)?

[stephanemoore]

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

56

Do you think we could generate a fixit to add the hash method?

I think it would be pretty tough to generate a reasonable hash method without knowing the equality and hashing semantics that the scenario calls for.

Here is an analogous situation presented in C++ (please excuse the hastily assembled sample code):

namespace {

class NSObject {
  public:
    NSObject() {}
    virtual ~NSObject() {}

    virtual bool isEqual(const NSObject *other) const {
      return this == other;
    }
    virtual unsigned long long hash() const {
      return (unsigned long long)this;
    }
};

}

#include <stdio.h>
#include <string>

namespace {

class Movie : public virtual NSObject {
  private:
    std::string name;
    std::string language;

  public:
    Movie(std::string name, std::string language) : name(name), language(language) {}
    ~Movie() override {}
    bool isEqual(const NSObject *other) const override {
      if (auto otherMovie = dynamic_cast<const Movie *>(other)) {
        // Movies with the same name are considered equal
        // regardless of the language of the screening.
        return name == otherMovie->name;
      }
      return false;
    }
    unsigned long long hash() const override {
      return name.length();
    }
};

}

As before, the base class uses pointer equality and the pointer as a hash. A subclass may arbitrarily add additional state but only the developer knows which added state factors into equality operations and consequently should be considered—but not necessarily required—in the hash operation. The matter can technically get even more complicated if an object stores state externally. I would hope that externally stored state would not factor into the equality operation of an object but I hesitate to make an assumption.

The developer is also in the best position to prioritize different properties of the hash function including performance, collision resistance, uniformity, and non-invertibility.

Writing effective hash functions is probably difficult independent of the programming language but it might help to consider some specific examples in Objective-C. GPBMessage, the Objective-C base class for Google Protocol Buffer message classes, implements -hash but has an extensive comment explaining that its complex but generic implementation is not generally optimal and recommends that developers override -hash and -isEqual: to optimize for runtime performance. In contrast, the basic collection classes in Apple's Foundation framework have surprisingly simple hash behavior that clearly indicate priority to runtime performance over uniformity and collision resistance. The former is a conservatively expensive hash function and the latter is a conservatively inexpensive hash function.

Do you think we could even add a default implementation that returns the pointer to the object (assuming that's the correct default behavior)?

A hash returning the object pointer is already inherited from the superclass (i..e, -[NSObject hash]). Defining an override that returns the object pointer would be a functional no-op for classes directly derived from NSObject (although the explicit override could be useful as a signal of intended behavior).

[aaron.ballman]

LGTM!

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

56

A hash returning the object pointer is already inherited from the superclass (i..e, -[NSObject hash]). Defining an override that returns the object pointer would be a functional no-op for classes directly derived from NSObject (although the explicit override could be useful as a signal of intended behavior).

Ah, my ObjC knowledge is weak and I was thinking that the one inherited from NSObject would be hidden. Thank you for the detailed explanation, that makes a lot of sense to me.

[stephanemoore]

Thanks for the review!

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

56

Thank you for the detailed explanation, that makes a lot of sense to me.

My pleasure!

clang-tools-extra/clang-tidy/objc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyObjCModule
   AvoidNSErrorInitCheck.cpp
   AvoidSpinlockCheck.cpp
   ForbiddenSubclassingCheck.cpp
+  MissingHashCheck.cpp
   ObjCTidyModule.cpp
   PropertyDeclarationCheck.cpp
   SuperSelfCheck.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy

clang-tools-extra/clang-tidy/objc/MissingHashCheck.h

+//===--- MissingHashCheck.h - clang-tidy ------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OBJC_MISSINGHASHCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OBJC_MISSINGHASHCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace objc {
+
+/// Finds Objective-C implementations that implement -isEqual: without also
+/// appropriately implementing -hash.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/objc-missing-hash.html
+class MissingHashCheck : public ClangTidyCheck {
+public:
+  MissingHashCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace objc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OBJC_MISSINGHASHCHECK_H

clang-tools-extra/clang-tidy/objc/MissingHashCheck.cpp

+//===--- MissingHashCheck.cpp - clang-tidy --------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "MissingHashCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace objc {
+
+namespace {
+
+AST_MATCHER_P(ObjCImplementationDecl, hasInterface,
+              ast_matchers::internal::Matcher<ObjCInterfaceDecl>, Base) {
+  const ObjCInterfaceDecl *InterfaceDecl = Node.getClassInterface();
+  return Base.matches(*InterfaceDecl, Finder, Builder);
+}
+
+AST_MATCHER_P(ObjCContainerDecl, hasInstanceMethod,
+              ast_matchers::internal::Matcher<ObjCMethodDecl>, Base) {
+  // Check each instance method against the provided matcher.
+  for (const auto *I : Node.instance_methods()) {
+    if (Base.matches(*I, Finder, Builder))
+      return true;
+  }
+  return false;
+}
+
+} // namespace
+
+void MissingHashCheck::registerMatchers(MatchFinder *Finder) {
+  // This check should only be applied to Objective-C sources.
+  if (!getLangOpts().ObjC)
+    return;
+
+  Finder->addMatcher(
+      objcMethodDecl(
+          hasName("isEqual:"), isInstanceMethod(),
+          hasDeclContext(objcImplementationDecl(
+                             hasInterface(isDirectlyDerivedFrom("NSObject")),
+                             unless(hasInstanceMethod(hasName("hash"))))
+                             .bind("impl"))),
+      this);
+}
+
+void MissingHashCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *ID = Result.Nodes.getNodeAs<ObjCImplementationDecl>("impl");
+  diag(ID->getLocation(), "%0 implements -isEqual: without implementing -hash")
+      << ID;
+}
+
+} // namespace objc
+} // namespace tidy
+} // namespace clang

clang-tools-extra/clang-tidy/objc/ObjCTidyModule.cpp

 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "AvoidNSErrorInitCheck.h"
 #include "AvoidSpinlockCheck.h"
 #include "ForbiddenSubclassingCheck.h"
+#include "MissingHashCheck.h"
 #include "PropertyDeclarationCheck.h"
 #include "SuperSelfCheck.h"
 
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {
 namespace objc {
 
 class ObjCModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<AvoidNSErrorInitCheck>(
         "objc-avoid-nserror-init");
     CheckFactories.registerCheck<AvoidSpinlockCheck>(
         "objc-avoid-spinlock");
     CheckFactories.registerCheck<ForbiddenSubclassingCheck>(
         "objc-forbidden-subclassing");
+    CheckFactories.registerCheck<MissingHashCheck>(
+        "objc-missing-hash");
     CheckFactories.registerCheck<PropertyDeclarationCheck>(
         "objc-property-declaration");
     CheckFactories.registerCheck<SuperSelfCheck>(
         "objc-super-self");
   }
 };
 
 // Register the ObjCTidyModule using this statically initialized variable.
 static ClangTidyModuleRegistry::Add<ObjCModule> X(
     "objc-module",

clang-tools-extra/docs/ReleaseNotes.rst

 
   Finds uses of deprecated Googletest APIs with names containing ``case`` and
   replaces them with equivalent APIs with ``suite``.
 
 - New :doc:`llvm-prefer-register-over-unsigned
   <clang-tidy/checks/llvm-prefer-register-over-unsigned>` check.
 
   Finds historical use of ``unsigned`` to hold vregs and physregs and rewrites
   them to use ``Register``
 
+- New :doc:`objc-missing-hash
+  <clang-tidy/checks/objc-missing-hash>` check.
+
+  Finds Objective-C implementations that implement ``-isEqual:`` without also
+  appropriately implementing ``-hash``.
+
 - Improved :doc:`bugprone-posix-return
   <clang-tidy/checks/bugprone-posix-return>` check.
 
   Now also checks if any calls to ``pthread_*`` functions expect negative return
   values.
 
 Improvements to include-fixer
 -----------------------------
 
 The improvements are...

clang-tools-extra/docs/clang-tidy/checks/list.rst

    modernize-use-override
    modernize-use-trailing-return-type
    modernize-use-transparent-functors
    modernize-use-uncaught-exceptions
    modernize-use-using
    mpi-buffer-deref
    mpi-type-mismatch
    objc-avoid-nserror-init
    objc-avoid-spinlock
    objc-forbidden-subclassing
+   objc-missing-hash
    objc-property-declaration
    objc-super-self
    openmp-exception-escape
    openmp-use-default-none
    performance-faster-string-find
    performance-for-range-copy
    performance-implicit-conversion-in-loop
    performance-inefficient-algorithm
    performance-inefficient-string-concatenation
    performance-inefficient-vector-operation

clang-tools-extra/docs/clang-tidy/checks/objc-missing-hash.rst

+.. title:: clang-tidy - objc-missing-hash
+
+objc-missing-hash
+=================
+
+Finds Objective-C implementations that implement ``-isEqual:`` without also
+appropriately implementing ``-hash``.
+
+Apple documentation highlights that objects that are equal must have the same
+hash value:
+https://developer.apple.com/documentation/objectivec/1418956-nsobject/1418795-isequal?language=objc
+
+Note that the check only verifies the presence of ``-hash`` in scenarios where
+its omission could result in unexpected behavior. The verification of the
+implementation of ``-hash`` is the responsibility of the developer, e.g.,
+through the addition of unit tests to verify the implementation.

clang-tools-extra/test/clang-tidy/objc-missing-hash.m

+// RUN: %check_clang_tidy %s objc-missing-hash %t
+
+typedef _Bool BOOL;
+#define YES 1
+#define NO 0
+typedef unsigned int NSUInteger;
+typedef void *id;
+
+@interface NSObject
+- (NSUInteger)hash;
+- (BOOL)isEqual:(id)object;
+@end
+
+@interface MissingHash : NSObject
+@end
+
+@implementation MissingHash
+// CHECK-MESSAGES: :[[@LINE-1]]:17: warning: 'MissingHash' implements -isEqual: without implementing -hash [objc-missing-hash]
+
+- (BOOL)isEqual:(id)object {
+  return YES;
+}
+
+@end
+
+@interface HasHash : NSObject
+@end
+
+@implementation HasHash
+
+- (NSUInteger)hash {
+  return 0;
+}
+
+- (BOOL)isEqual:(id)object {
+  return YES;
+}
+
+@end
+
+@interface NSArray : NSObject
+@end
+
+@interface MayHaveInheritedHash : NSArray
+@end
+
+@implementation MayHaveInheritedHash
+
+- (BOOL)isEqual:(id)object {
+  return YES;
+}
+
+@end
+
+@interface AnotherRootClass
+@end
+
+@interface NotDerivedFromNSObject : AnotherRootClass
+@end
+
+@implementation NotDerivedFromNSObject
+
+- (BOOL)isEqual:(id)object {
+  return NO;
+}
+
+@end
+