[clang][Basic] Make SourceLocation usable as key in hash maps, NFCI

[miyuki]

Summary

This change creates a DenseMapInfo trait specialization for the
SourceLocation class. The empty key, the tombstone key, and the hash
function are identical to DenseMapInfo<unsigned>, because we already
have hash maps that use raw the representation of SourceLocation as
a key.

The update of existing DenseMaps containing raw representation of
SourceLocations will be done in a follow-up patch. As an example
the patch makes use of the new trait in one instance:
clang-tidy/google/UpgradeGoogletestCaseCheck.{h,cpp}

[dexonsmith]

We don't usually add code without any current users. I suggest either adding a small unit test proving SourceLocation can now be used as a DenseMap key (probably preferred) or converting one DenseMap over so that it at least has one use.

[miyuki]

Added an example of usage.

[dexonsmith]

LGTM.

[miyuki]

The test failure is unrelated (see D89463)

clang-tools-extra/clang-tidy/google/UpgradeGoogletestCaseCheck.h

bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
     return LangOpts.CPlusPlus;
   }
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void registerPPCallbacks(const SourceManager &SM, Preprocessor *PP,
                            Preprocessor *ModuleExpanderPP) override;
   void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
 
 private:
-  llvm::DenseSet<unsigned> MatchedTemplateLocations;
+  llvm::DenseSet<SourceLocation> MatchedTemplateLocations;
 };
 
 } // namespace google
 } // namespace tidy
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_GOOGLE_UPGRADEGOOGLETESTCASECHECK_H

clang-tools-extra/clang-tidy/google/UpgradeGoogletestCaseCheck.cpp

if (const auto *Call = Result.Nodes.getNodeAs<CXXMemberCallExpr>("call")) {
 
       // If the type of the matched method is strictly derived from a googletest
       // type and has both the old and new member function names, then we cannot
       // safely rename (or delete) the old name version.
       AddFix = !derivedTypeHasReplacementMethod(Result, ReplacementText);
     }
 
     if (IsInInstantiation) {
-      if (MatchedTemplateLocations.count(
-              ReplacementRange.getBegin().getRawEncoding()) == 0) {
+      if (MatchedTemplateLocations.count(ReplacementRange.getBegin()) == 0) {
         // For each location matched in a template instantiation, we check if
         // the location can also be found in `MatchedTemplateLocations`. If it
         // is not found, that means the expression did not create a match
         // without the instantiation and depends on template parameters. A
         // manual fix is probably required so we provide only a warning.
         diag(ReplacementRange.getBegin(), RenameCaseToSuiteMessage);
       }
       return;
     }
 
     if (IsInTemplate) {
       // We gather source locations from template matches not in template
       // instantiations for future matches.
-      MatchedTemplateLocations.insert(
-          ReplacementRange.getBegin().getRawEncoding());
+      MatchedTemplateLocations.insert(ReplacementRange.getBegin());
     }
 
     if (!AddFix) {
       diag(ReplacementRange.getBegin(), RenameCaseToSuiteMessage);
       return;
     }
   } else {
     // This is a match for `TestCase` to `TestSuite` refactoring.

clang/include/clang/Basic/SourceLocation.h

static SourceLocation getFromPtrEncoding(const void *Encoding) {
     return getFromRawEncoding((unsigned)(uintptr_t)Encoding);
   }
 
   static bool isPairOfFileLocations(SourceLocation Start, SourceLocation End) {
     return Start.isValid() && Start.isFileID() && End.isValid() &&
            End.isFileID();
   }
 
+  unsigned getHashValue() const;
   void print(raw_ostream &OS, const SourceManager &SM) const;
   std::string printToString(const SourceManager &SM) const;
   void dump(const SourceManager &SM) const;
 };
 
 inline bool operator==(const SourceLocation &LHS, const SourceLocation &RHS) {
   return LHS.getRawEncoding() == RHS.getRawEncoding();
 }
static unsigned getHashValue(clang::FileID S) {
       return S.getHashValue();
     }
 
     static bool isEqual(clang::FileID LHS, clang::FileID RHS) {
       return LHS == RHS;
     }
   };
 
+  /// Define DenseMapInfo so that SourceLocation's can be used as keys in
+  /// DenseMap and DenseSet. This trait class is eqivalent to
+  /// DenseMapInfo<unsigned> which uses SourceLocation::ID is used as a key.
+  template <> struct DenseMapInfo<clang::SourceLocation> {
+    static clang::SourceLocation getEmptyKey() {
+      return clang::SourceLocation::getFromRawEncoding(~0U);
+    }
+
+    static clang::SourceLocation getTombstoneKey() {
+      return clang::SourceLocation::getFromRawEncoding(~0U - 1);
+    }
+
+    static unsigned getHashValue(clang::SourceLocation Loc) {
+      return Loc.getHashValue();
+    }
+
+    static bool isEqual(clang::SourceLocation LHS, clang::SourceLocation RHS) {
+      return LHS == RHS;
+    }
+  };
+
   // Teach SmallPtrSet how to handle SourceLocation.
   template<>
   struct PointerLikeTypeTraits<clang::SourceLocation> {
     static constexpr int NumLowBitsAvailable = 0;
 
     static void *getAsVoidPointer(clang::SourceLocation L) {
       return L.getPtrEncoding();
     }

clang/lib/Basic/SourceLocation.cpp

 //===- SourceLocation.cpp - Compact identifier for Source Files -----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines accessor methods for the FullSourceLoc class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/PrettyStackTrace.h"
 #include "clang/Basic/SourceManager.h"
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <string>
 #include <utility>
 
void PrettyStackTraceLoc::print(raw_ostream &OS) const {
   }
   OS << Message << '\n';
 }
 
 //===----------------------------------------------------------------------===//
 // SourceLocation
 //===----------------------------------------------------------------------===//
 
+unsigned SourceLocation::getHashValue() const {
+  return llvm::DenseMapInfo<unsigned>::getHashValue(ID);
+}
+
 void SourceLocation::print(raw_ostream &OS, const SourceManager &SM)const{
   if (!isValid()) {
     OS << "<invalid loc>";
     return;
   }
 
   if (isFileID()) {
     PresumedLoc PLoc = SM.getPresumedLoc(*this);