[clang] Use SourceLocation as key in hash maps, NFCI

[miyuki]

Summary

The patch adjusts the existing llvm::DenseMap<unsigned, T> and
llvm::DenseSet<unsigned> objects that store source locations, so
that they use SourceLocation directly instead of unsigned.

This patch relies on the DenseMapInfo trait added in D89719.

It also replaces the construction of SourceLocation objects from
the constants -1 and -2 with calls to the trait's methods getEmptyKey
and getTombstoneKey where appropriate.

[miyuki]

Changed getRawEncoding -> getHashValue in Sema.h

[aprantl]

What's the motivation behind this?

[miyuki]

The motivation is to be able to make source locations' underlying type configurable. Richard Smith suggested that this might be feasible: http://lists.llvm.org/pipermail/cfe-dev/2019-October/063515.html
So, the first step is to get rid of getRawEncoding where possible. I think this would make the code cleaner anyway.

[miyuki]

ping

[miyuki]

ping^2

[miyuki]

ping^3

[aprantl]

@rsmith can you take a look at this to see if this is going into the right direction?

[miyuki]

ping^4

[miyuki]

Rebased, updated several more hash map occurrences.

[dexonsmith]

If you're still interested in pursuing this, I'm happy to review it.

A general comment is that there are a couple of functional changes in this patch, where hash values are changing and data structures are being changed, but they're buried in the noise of the refactoring that's going on at the same time. I suggest splitting this up at least into two, where most of the NFC changes are in a different commit.

clang-tools-extra/clang-tidy/abseil/UpgradeDurationConversionsCheck.h

35 ↗

(On Diff #249443)

Changing the data structure (DenseSet <= std::unordered_set) seems unrelated to the rest of the patch. If it's necessary / useful, then please do it separately. It'll be important to confirm that the users of MatchedTemplateLocations don't rely on the values having stable addresses.

clang/include/clang/Basic/SourceLocation.h

178

I suggest reusing the hash function for unsigned.

[miyuki]

Yes, I am still interested in working on this. For now, I've split out some changes that don't require any modifications in SourceLocation into https://reviews.llvm.org/D89705.

A general comment is that there are a couple of functional changes in this patch, where hash values are changing and data structures are being changed, but they're buried in the noise of the refactoring that's going on at the same time. I suggest splitting this up at least into two

Will do.

[miyuki]

Split out the refactoring part.

[dexonsmith]

LGTM.

clang/include/clang/Basic/SourceLocation.h

            End.isFileID();
   }
 
+  unsigned getHashValue() const {
+    return ID * 37U;
+  }
+
   void print(raw_ostream &OS, const SourceManager &SM) const;
   std::string printToString(const SourceManager &SM) const;
   void dump(const SourceManager &SM) const;

     }
   };
 
+  /// 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> {

clang/include/clang/Edit/EditedSource.h

     }
   };
 
-  llvm::DenseMap<unsigned, SmallVector<MacroArgUse, 2>> ExpansionToArgMap;
+  llvm::DenseMap<SourceLocation, SmallVector<MacroArgUse, 2>> ExpansionToArgMap;
   SmallVector<std::pair<SourceLocation, MacroArgUse>, 2>
     CurrCommitMacroArgExps;
 

clang/include/clang/Tooling/Syntax/Tokens.h

   /// the stack) and not when they end (when we pop a macro from the stack).
   /// To workaround this limitation, we rely on source location information
   /// stored in this map.
-  using PPExpansions = llvm::DenseMap</*SourceLocation*/ int, SourceLocation>;
+  using PPExpansions = llvm::DenseMap<SourceLocation, SourceLocation>;
   class Builder;
   class CollectPPExpansions;
 

clang/lib/ARCMigrate/TransGCAttrs.cpp

       return false;
 
     SourceLocation Loc = OwnershipAttr->getLocation();
-    unsigned RawLoc = Loc.getRawEncoding();
-    if (MigrateCtx.AttrSet.count(RawLoc))
+    SourceLocation OrigLoc = Loc;
+    if (MigrateCtx.AttrSet.count(OrigLoc))
       return true;
 
     ASTContext &Ctx = MigrateCtx.Pass.Ctx;

     else
       return false;
 
-    MigrateCtx.AttrSet.insert(RawLoc);
+    MigrateCtx.AttrSet.insert(OrigLoc);
     MigrateCtx.GCAttrs.push_back(MigrationContext::GCAttrOccurrence());
     MigrationContext::GCAttrOccurrence &Attr = MigrateCtx.GCAttrs.back();
 

       if (!canApplyWeak(MigrateCtx.Pass.Ctx, Attr.ModifiedType,
                         /*AllowOnUnknownClass=*/true)) {
         Transaction Trans(TA);
-        if (!MigrateCtx.RemovedAttrSet.count(Attr.Loc.getRawEncoding()))
+        if (!MigrateCtx.RemovedAttrSet.count(Attr.Loc))
           TA.replaceText(Attr.Loc, "__weak", "__unsafe_unretained");
         TA.clearDiagnostic(diag::err_arc_weak_no_runtime,
                            diag::err_arc_unsupported_weak_class,

   if (GCAttrsCollector::hasObjCImpl(
                               cast<Decl>(IndProps.front()->getDeclContext()))) {
     if (hasWeak)
-      MigrateCtx.AtPropsWeak.insert(AtLoc.getRawEncoding());
+      MigrateCtx.AtPropsWeak.insert(AtLoc);
 
   } else {
     StringRef toAttr = "strong";

     TA.clearDiagnostic(diag::err_objc_property_attr_mutually_exclusive, AtLoc);
     TA.clearDiagnostic(diag::err_arc_inconsistent_property_ownership,
                        ATLs[i].second->getLocation());
-    MigrateCtx.RemovedAttrSet.insert(Loc.getRawEncoding());
+    MigrateCtx.RemovedAttrSet.insert(Loc);
   }
 }
 
 static void checkAllProps(MigrationContext &MigrateCtx,
                           std::vector<ObjCPropertyDecl *> &AllProps) {
   typedef llvm::TinyPtrVector<ObjCPropertyDecl *> IndivPropsTy;
-  llvm::DenseMap<unsigned, IndivPropsTy> AtProps;
+  llvm::DenseMap<SourceLocation, IndivPropsTy> AtProps;
 
   for (unsigned i = 0, e = AllProps.size(); i != e; ++i) {
     ObjCPropertyDecl *PD = AllProps[i];

       SourceLocation AtLoc = PD->getAtLoc();
       if (AtLoc.isInvalid())
         continue;
-      unsigned RawAt = AtLoc.getRawEncoding();
-      AtProps[RawAt].push_back(PD);
+      AtProps[AtLoc].push_back(PD);
     }
   }
 
-  for (llvm::DenseMap<unsigned, IndivPropsTy>::iterator
-         I = AtProps.begin(), E = AtProps.end(); I != E; ++I) {
-    SourceLocation AtLoc = SourceLocation::getFromRawEncoding(I->first);
+  for (auto I = AtProps.begin(), E = AtProps.end(); I != E; ++I) {
+    SourceLocation AtLoc = I->first;
     IndivPropsTy &IndProps = I->second;
     checkAllAtProps(MigrateCtx, AtLoc, IndProps);
   }

clang/lib/ARCMigrate/TransProperties.cpp

   };
 
   typedef SmallVector<PropData, 2> PropsTy;
-  typedef std::map<unsigned, PropsTy> AtPropDeclsTy;
+  typedef std::map<SourceLocation, PropsTy> AtPropDeclsTy;
   AtPropDeclsTy AtProps;
   llvm::DenseMap<IdentifierInfo *, PropActionKind> ActionOnProp;
 

   static void collectProperties(ObjCContainerDecl *D, AtPropDeclsTy &AtProps,
                                 AtPropDeclsTy *PrevAtProps = nullptr) {
     for (auto *Prop : D->instance_properties()) {
-      if (Prop->getAtLoc().isInvalid())
+      SourceLocation Loc = Prop->getAtLoc();
+      if (Loc.isInvalid())
         continue;
-      unsigned RawLoc = Prop->getAtLoc().getRawEncoding();
       if (PrevAtProps)
-        if (PrevAtProps->find(RawLoc) != PrevAtProps->end())
+        if (PrevAtProps->find(Loc) != PrevAtProps->end())
           continue;
-      PropsTy &props = AtProps[RawLoc];
+      PropsTy &props = AtProps[Loc];
       props.push_back(Prop);
     }
   }

       ObjCIvarDecl *ivarD = implD->getPropertyIvarDecl();
       if (!ivarD || ivarD->isInvalidDecl())
         continue;
-      unsigned rawAtLoc = propD->getAtLoc().getRawEncoding();
-      AtPropDeclsTy::iterator findAtLoc = AtProps.find(rawAtLoc);
+      AtPropDeclsTy::iterator findAtLoc = AtProps.find(propD->getAtLoc());
       if (findAtLoc == AtProps.end())
         continue;
 

 
     for (AtPropDeclsTy::iterator
            I = AtProps.begin(), E = AtProps.end(); I != E; ++I) {
-      SourceLocation atLoc = SourceLocation::getFromRawEncoding(I->first);
+      SourceLocation atLoc = I->first;
       PropsTy &props = I->second;
       if (!getPropertyType(props)->isObjCRetainableType())
         continue;

       return false;
     if (props.empty())
       return false;
-    return MigrateCtx.AtPropsWeak.count(atLoc.getRawEncoding());
+    return MigrateCtx.AtPropsWeak.count(atLoc);
   }
 
   bool isUserDeclared(ObjCIvarDecl *ivarD) const {

clang/lib/ARCMigrate/Transforms.h

     bool FullyMigratable;
   };
   std::vector<GCAttrOccurrence> GCAttrs;
-  llvm::DenseSet<unsigned> AttrSet;
-  llvm::DenseSet<unsigned> RemovedAttrSet;
+  llvm::DenseSet<SourceLocation> AttrSet;
+  llvm::DenseSet<SourceLocation> RemovedAttrSet;
 
   /// Set of raw '@' locations for 'assign' properties group that contain
   /// GC __weak.
-  llvm::DenseSet<unsigned> AtPropsWeak;
+  llvm::DenseSet<SourceLocation> AtPropsWeak;
 
   explicit MigrationContext(MigrationPass &pass) : Pass(pass) {}
   ~MigrationContext();

clang/lib/CodeGen/CGOpenMPRuntime.h

   QualType IdentQTy;
   llvm::StructType *IdentTy = nullptr;
   /// Map for SourceLocation and OpenMP runtime library debug locations.
-  typedef llvm::DenseMap<unsigned, llvm::Value *> OpenMPDebugLocMapTy;
+  typedef llvm::DenseMap<SourceLocation, llvm::Value *> OpenMPDebugLocMapTy;
   OpenMPDebugLocMapTy OpenMPDebugLocMap;
   /// The type for a microtask which gets passed to __kmpc_fork_call().
   /// Original representation is:

clang/lib/CodeGen/CGOpenMPRuntime.cpp

   LValue PSource =
       CGF.EmitLValueForField(Base, *std::next(Fields, IdentField_PSource));
 
-  llvm::Value *OMPDebugLoc = OpenMPDebugLocMap.lookup(Loc.getRawEncoding());
+  llvm::Value *OMPDebugLoc = OpenMPDebugLocMap.lookup(Loc);
   if (OMPDebugLoc == nullptr) {
     SmallString<128> Buffer2;
     llvm::raw_svector_ostream OS2(Buffer2);

       OS2 << FD->getQualifiedNameAsString();
     OS2 << ";" << PLoc.getLine() << ";" << PLoc.getColumn() << ";;";
     OMPDebugLoc = CGF.Builder.CreateGlobalStringPtr(OS2.str());
-    OpenMPDebugLocMap[Loc.getRawEncoding()] = OMPDebugLoc;
+    OpenMPDebugLocMap[Loc] = OMPDebugLoc;
   }
   // *psource = ";<File>;<Function>;<Line>;<Column>;;";
   CGF.EmitStoreOfScalar(OMPDebugLoc, PSource);

clang/lib/Edit/EditedSource.cpp

     SourceLocation ExpLoc;
     MacroArgUse ArgUse;
     std::tie(ExpLoc, ArgUse) = ExpArg;
-    auto &ArgUses = ExpansionToArgMap[ExpLoc.getRawEncoding()];
+    auto &ArgUses = ExpansionToArgMap[ExpLoc];
     if (llvm::find(ArgUses, ArgUse) == ArgUses.end())
       ArgUses.push_back(ArgUse);
   }

     SourceLocation ExpLoc;
     MacroArgUse ArgUse;
     deconstructMacroArgLoc(OrigLoc, ExpLoc, ArgUse);
-    auto I = ExpansionToArgMap.find(ExpLoc.getRawEncoding());
+    auto I = ExpansionToArgMap.find(ExpLoc);
     if (I != ExpansionToArgMap.end() &&
         find_if(I->second, [&](const MacroArgUse &U) {
           return ArgUse.Identifier == U.Identifier &&

clang/lib/Frontend/Rewrite/InclusionRewriter.cpp

   bool ShowLineMarkers; ///< Show #line markers.
   bool UseLineDirectives; ///< Use of line directives or line markers.
   /// Tracks where inclusions that change the file are found.
-  std::map<unsigned, IncludedFile> FileIncludes;
+  std::map<SourceLocation, IncludedFile> FileIncludes;
   /// Tracks where inclusions that import modules are found.
-  std::map<unsigned, const Module *> ModuleIncludes;
+  std::map<SourceLocation, const Module *> ModuleIncludes;
   /// Tracks where inclusions that enter modules (in a module build) are found.
-  std::map<unsigned, const Module *> ModuleEntryIncludes;
+  std::map<SourceLocation, const Module *> ModuleEntryIncludes;
   /// Tracks where #if and #elif directives get evaluated and whether to true.
-  std::map<unsigned, bool> IfConditions;
+  std::map<SourceLocation, bool> IfConditions;
   /// Used transitively for building up the FileIncludes mapping over the
   /// various \c PPCallbacks callbacks.
   SourceLocation LastInclusionLocation;

   void detectMainFileEOL();
   void handleModuleBegin(Token &Tok) {
     assert(Tok.getKind() == tok::annot_module_begin);
-    ModuleEntryIncludes.insert({Tok.getLocation().getRawEncoding(),
+    ModuleEntryIncludes.insert({Tok.getLocation(),
                                 (Module *)Tok.getAnnotationValue()});
   }
 private:

     return;
   FileID Id = FullSourceLoc(Loc, SM).getFileID();
   auto P = FileIncludes.insert(
-      std::make_pair(LastInclusionLocation.getRawEncoding(),
+      std::make_pair(LastInclusionLocation,
                      IncludedFile(Id, NewFileType, PP.GetCurDirLookup())));
   (void)P;
   assert(P.second && "Unexpected revisitation of the same include directive");

                                            const Module *Imported,
                                            SrcMgr::CharacteristicKind FileType){
   if (Imported) {
-    auto P = ModuleIncludes.insert(
-        std::make_pair(HashLoc.getRawEncoding(), Imported));
+    auto P = ModuleIncludes.insert(std::make_pair(HashLoc, Imported));
     (void)P;
     assert(P.second && "Unexpected revisitation of the same include directive");
   } else

 
 void InclusionRewriter::If(SourceLocation Loc, SourceRange ConditionRange,
                            ConditionValueKind ConditionValue) {
-  auto P = IfConditions.insert(
-      std::make_pair(Loc.getRawEncoding(), ConditionValue == CVK_True));
+  auto P = IfConditions.insert(std::make_pair(Loc, ConditionValue == CVK_True));
   (void)P;
   assert(P.second && "Unexpected revisitation of the same if directive");
 }

 void InclusionRewriter::Elif(SourceLocation Loc, SourceRange ConditionRange,
                              ConditionValueKind ConditionValue,
                              SourceLocation IfLoc) {
-  auto P = IfConditions.insert(
-      std::make_pair(Loc.getRawEncoding(), ConditionValue == CVK_True));
+  auto P = IfConditions.insert(std::make_pair(Loc, ConditionValue == CVK_True));
   (void)P;
   assert(P.second && "Unexpected revisitation of the same elif directive");
 }

 /// an inclusion directive) in the map of inclusion information, FileChanges.
 const InclusionRewriter::IncludedFile *
 InclusionRewriter::FindIncludeAtLocation(SourceLocation Loc) const {
-  const auto I = FileIncludes.find(Loc.getRawEncoding());
+  const auto I = FileIncludes.find(Loc);
   if (I != FileIncludes.end())
     return &I->second;
   return nullptr;

 /// an inclusion directive) in the map of module inclusion information.
 const Module *
 InclusionRewriter::FindModuleAtLocation(SourceLocation Loc) const {
-  const auto I = ModuleIncludes.find(Loc.getRawEncoding());
+  const auto I = ModuleIncludes.find(Loc);
   if (I != ModuleIncludes.end())
     return I->second;
   return nullptr;

 /// an inclusion directive) in the map of module entry information.
 const Module *
 InclusionRewriter::FindEnteredModule(SourceLocation Loc) const {
-  const auto I = ModuleEntryIncludes.find(Loc.getRawEncoding());
+  const auto I = ModuleEntryIncludes.find(Loc);
   if (I != ModuleEntryIncludes.end())
     return I->second;
   return nullptr;
 }
 
 bool InclusionRewriter::IsIfAtLocationTrue(SourceLocation Loc) const {
-  const auto I = IfConditions.find(Loc.getRawEncoding());
+  const auto I = IfConditions.find(Loc);
   if (I != IfConditions.end())
     return I->second;
   return false;

clang/lib/Tooling/Syntax/Tokens.cpp

          Collector->PP.getSourceManager().isBeforeInTranslationUnit(
              Range.getBegin(), LastExpansionEnd)))
       return;
-    Collector->Expansions[Range.getBegin().getRawEncoding()] = Range.getEnd();
+    Collector->Expansions[Range.getBegin()] = Range.getEnd();
     LastExpansionEnd = Range.getEnd();
   }
   // FIXME: handle directives like #pragma, #include, etc.

       auto L = File.SpelledTokens[NextSpelled].location();
       if (Offset <= SM.getFileOffset(L))
         return llvm::None; // reached the offset we are looking for.
-      auto Mapping = CollectedExpansions.find(L.getRawEncoding());
+      auto Mapping = CollectedExpansions.find(L);
       if (Mapping != CollectedExpansions.end())
         return Mapping->second; // found a mapping before the offset.
     }