Basic: Add hashing support for FileEntryRef and DirectoryEntryRef

[dexonsmith]

Summary

Allow hashing FileEntryRef and DirectoryEntryRef via hash_value, and
use that to implement DenseMapInfo. This hash be equal whenever the
entry is the same (the name used to reference it is not relevant).

Also added DirectoryEntryRef::isSameRef as a drive-by to facilitate
testing.

[jansvoboda11]

Left a couple of nits and a question, but LGTM overall.

clang/include/clang/Basic/DirectoryEntry.h

104

Nit: would it make sense to avoid copy-pasting the constructor logic here (llvm::DenseMapInfo<const MapEntry *>::getEmptyKey()) and call the constructor instead?
For example: isSameRef(DirectoryEntryRef(dense_map_empty_tag{})).

The same goes for FileEntryRef.

212

Nit: could use LHS.isSameRef(RHS) to keep this uniform.

clang/unittests/Basic/FileEntryTest.cpp

126

Question: do we prefer naming tests with the function/data structure under test, or using more descriptive names? (e.g. DenseMapFindsOldestEntry)

[dexonsmith]

clang/include/clang/Basic/DirectoryEntry.h

104

Yes, that seems decent; I hadn't considered using isSameRef when the MapEntry is a bogus pointer, but that's probably better too. I'll update this and the instance of that below.

clang/unittests/Basic/FileEntryTest.cpp

126

Likely depends on the primary motivation of the test; I have a bit of tendency for the former in case expected behaviour changes, unless the whole point of the test is to test an interesting behaviour or corner case.

In this case, the main purpose of the test is to demonstrate that these can be used as DenseMap-family keys -- i.e., that the insert calls successfully compile. It's important that the behaviour is correct, too, of course.

[dexonsmith]

Thanks for the reviews! Pushed 2878e965af27ce037378a4f0409e89039108c09f.

clang/include/clang/Basic/DirectoryEntry.h

104

Incorporated those suggestions (and the nit below) in the commit I pushed.

clang/include/clang/Basic/DirectoryEntry.h

 /// Defines interfaces for clang::DirectoryEntry and clang::DirectoryEntryRef.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_BASIC_DIRECTORYENTRY_H
 #define LLVM_CLANG_BASIC_DIRECTORYENTRY_H
 
 #include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ErrorOr.h"
 
 namespace clang {
 namespace FileMgr {
 
 template <class RefTy> class MapEntryOptionalStorage;

 /// A reference to a \c DirectoryEntry  that includes the name of the directory
 /// as it was accessed by the FileManager's client.
 class DirectoryEntryRef {
 public:
   const DirectoryEntry &getDirEntry() const { return *ME->getValue(); }
 
   StringRef getName() const { return ME->getKey(); }
 
+  /// Hash code is based on the DirectoryEntry, not the specific named
+  /// reference.
+  friend llvm::hash_code hash_value(DirectoryEntryRef Ref) {
+    return llvm::hash_value(&Ref.getDirEntry());
+  }
+
   using MapEntry = llvm::StringMapEntry<llvm::ErrorOr<DirectoryEntry &>>;
 
   const MapEntry &getMapEntry() const { return *ME; }
 
+  /// Check if RHS referenced the file in exactly the same way.
+  bool isSameRef(DirectoryEntryRef RHS) const { return ME == RHS.ME; }
+
   DirectoryEntryRef() = delete;
   DirectoryEntryRef(const MapEntry &ME) : ME(&ME) {}
 
   /// Allow DirectoryEntryRef to degrade into 'const DirectoryEntry*' to
   /// facilitate incremental adoption.
   ///
   /// The goal is to avoid code churn due to dances like the following:
   /// \code

 private:
   friend class FileMgr::MapEntryOptionalStorage<DirectoryEntryRef>;
   struct optional_none_tag {};
 
   // Private constructor for use by OptionalStorage.
   DirectoryEntryRef(optional_none_tag) : ME(nullptr) {}
   bool hasOptionalValue() const { return ME; }
 
+  friend struct llvm::DenseMapInfo<DirectoryEntryRef>;
+  struct dense_map_empty_tag {};
+  struct dense_map_tombstone_tag {};
+
+  // Private constructors for use by DenseMapInfo.
+  DirectoryEntryRef(dense_map_empty_tag)
+      : ME(llvm::DenseMapInfo<const MapEntry *>::getEmptyKey()) {}
+  DirectoryEntryRef(dense_map_tombstone_tag)
+      : ME(llvm::DenseMapInfo<const MapEntry *>::getTombstoneKey()) {}
+  bool isSpecialDenseMapKey() const {
+    return isSameRef(DirectoryEntryRef(dense_map_empty_tag())) ||
+           isSameRef(DirectoryEntryRef(dense_map_tombstone_tag()));
+  }
+
   const MapEntry *ME;
 };
 
 namespace FileMgr {
 
 /// Customized storage for refs derived from map entires in FileManager, using
 /// the private optional_none_tag to keep it to the size of a single pointer.
 template <class RefTy> class MapEntryOptionalStorage {
static_assert(sizeof(Optional<clang::DirectoryEntryRef>) ==
                   sizeof(clang::DirectoryEntryRef),
               "Optional<DirectoryEntryRef> must avoid size overhead");
 
 static_assert(
     std::is_trivially_copyable<Optional<clang::DirectoryEntryRef>>::value,
     "Optional<DirectoryEntryRef> should be trivially copyable");
 
 } // end namespace optional_detail
+
+/// Specialisation of DenseMapInfo for DirectoryEntryRef.
+template <> struct DenseMapInfo<clang::DirectoryEntryRef> {
+  static inline clang::DirectoryEntryRef getEmptyKey() {
+    return clang::DirectoryEntryRef(
+        clang::DirectoryEntryRef::dense_map_empty_tag());
+  }
+
+  static inline clang::DirectoryEntryRef getTombstoneKey() {
+    return clang::DirectoryEntryRef(
+        clang::DirectoryEntryRef::dense_map_tombstone_tag());
+  }
+
+  static unsigned getHashValue(clang::DirectoryEntryRef Val) {
+    return hash_value(Val);
+  }
+
+  static bool isEqual(clang::DirectoryEntryRef LHS,
+                      clang::DirectoryEntryRef RHS) {
+    // Catch the easy cases: both empty, both tombstone, or the same ref.
+    if (LHS.isSameRef(RHS))
+      return true;
+
+    // Confirm LHS and RHS are valid.
+    if (LHS.isSpecialDenseMapKey() || RHS.isSpecialDenseMapKey())
+      return false;
+
+    // It's safe to use operator==.
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 namespace clang {
 
 /// Wrapper around Optional<DirectoryEntryRef> that degrades to 'const
 /// DirectoryEntry*', facilitating incremental patches to propagate
 /// DirectoryEntryRef.
 ///

clang/include/clang/Basic/FileEntry.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_BASIC_FILEENTRY_H
 #define LLVM_CLANG_BASIC_FILEENTRY_H
 
 #include "clang/Basic/DirectoryEntry.h"
 #include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/FileSystem/UniqueID.h"
 
 namespace llvm {
 namespace vfs {
public:
   }
   friend bool operator!=(const FileEntry *LHS, const FileEntryRef &RHS) {
     return !(LHS == RHS);
   }
   friend bool operator!=(const FileEntryRef &LHS, const FileEntry *RHS) {
     return !(LHS == RHS);
   }
 
+  /// Hash code is based on the FileEntry, not the specific named reference,
+  /// just like operator==.
+  friend llvm::hash_code hash_value(FileEntryRef Ref) {
+    return llvm::hash_value(&Ref.getFileEntry());
+  }
+
   struct MapValue;
 
   /// Type used in the StringMap.
   using MapEntry = llvm::StringMapEntry<llvm::ErrorOr<MapValue>>;
 
   /// Type stored in the StringMap.
   struct MapValue {
     /// The pointer at another MapEntry is used when the FileManager should

 private:
   friend class FileMgr::MapEntryOptionalStorage<FileEntryRef>;
   struct optional_none_tag {};
 
   // Private constructor for use by OptionalStorage.
   FileEntryRef(optional_none_tag) : ME(nullptr) {}
   bool hasOptionalValue() const { return ME; }
 
+  friend struct llvm::DenseMapInfo<FileEntryRef>;
+  struct dense_map_empty_tag {};
+  struct dense_map_tombstone_tag {};
+
+  // Private constructors for use by DenseMapInfo.
+  FileEntryRef(dense_map_empty_tag)
+      : ME(llvm::DenseMapInfo<const MapEntry *>::getEmptyKey()) {}
+  FileEntryRef(dense_map_tombstone_tag)
+      : ME(llvm::DenseMapInfo<const MapEntry *>::getTombstoneKey()) {}
+  bool isSpecialDenseMapKey() const {
+    return isSameRef(FileEntryRef(dense_map_empty_tag())) ||
+           isSameRef(FileEntryRef(dense_map_tombstone_tag()));
+  }
+
   const MapEntry *ME;
 };
 
 static_assert(sizeof(FileEntryRef) == sizeof(const FileEntry *),
               "FileEntryRef must avoid size overhead");
 
 static_assert(std::is_trivially_copyable<FileEntryRef>::value,
               "FileEntryRef must be trivially copyable");

 static_assert(sizeof(Optional<clang::FileEntryRef>) ==
                   sizeof(clang::FileEntryRef),
               "Optional<FileEntryRef> must avoid size overhead");
 
 static_assert(std::is_trivially_copyable<Optional<clang::FileEntryRef>>::value,
               "Optional<FileEntryRef> should be trivially copyable");
 
 } // end namespace optional_detail
+
+/// Specialisation of DenseMapInfo for FileEntryRef.
+template <> struct DenseMapInfo<clang::FileEntryRef> {
+  static inline clang::FileEntryRef getEmptyKey() {
+    return clang::FileEntryRef(clang::FileEntryRef::dense_map_empty_tag());
+  }
+
+  static inline clang::FileEntryRef getTombstoneKey() {
+    return clang::FileEntryRef(clang::FileEntryRef::dense_map_tombstone_tag());
+  }
+
+  static unsigned getHashValue(clang::FileEntryRef Val) {
+    return hash_value(Val);
+  }
+
+  static bool isEqual(clang::FileEntryRef LHS, clang::FileEntryRef RHS) {
+    // Catch the easy cases: both empty, both tombstone, or the same ref.
+    if (LHS.isSameRef(RHS))
+      return true;
+
+    // Confirm LHS and RHS are valid.
+    if (LHS.isSpecialDenseMapKey() || RHS.isSpecialDenseMapKey())
+      return false;
+
+    // It's safe to use operator==.
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 namespace clang {
 
 /// Wrapper around Optional<FileEntryRef> that degrades to 'const FileEntry*',
 /// facilitating incremental patches to propagate FileEntryRef.
 ///
 /// This class can be used as return value or field where it's convenient for

clang/unittests/Basic/FileEntryTest.cpp

 //===- unittests/Basic/FileEntryTest.cpp - Test FileEntry/FileEntryRef ----===//
 //
 // 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 "clang/Basic/FileEntry.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringMap.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace clang;
 
 namespace {
 
 using FileMap = StringMap<llvm::ErrorOr<FileEntryRef::MapValue>>;
 using DirMap = StringMap<llvm::ErrorOr<DirectoryEntry &>>;
 
 struct RefMaps {
   FileMap Files;
   DirMap Dirs;
 
-  DirectoryEntry D;
-  DirectoryEntryRef DR;
   SmallVector<std::unique_ptr<FileEntry>, 5> FEs;
+  SmallVector<std::unique_ptr<DirectoryEntry>, 5> DEs;
+  DirectoryEntryRef DR;
+
+  RefMaps() : DR(addDirectory("dir")) {}
 
-  RefMaps() : DR(*Dirs.insert({"dir", D}).first) {}
+  DirectoryEntryRef addDirectory(StringRef Name) {
+    DEs.push_back(std::make_unique<DirectoryEntry>());
+    return DirectoryEntryRef(*Dirs.insert({Name, *DEs.back()}).first);
+  }
+  DirectoryEntryRef addDirectoryAlias(StringRef Name, DirectoryEntryRef Base) {
+    return DirectoryEntryRef(
+        *Dirs.insert({Name, const_cast<DirectoryEntry &>(Base.getDirEntry())})
+             .first);
+  }
 
   FileEntryRef addFile(StringRef Name) {
     FEs.push_back(std::make_unique<FileEntry>());
     return FileEntryRef(
         *Files.insert({Name, FileEntryRef::MapValue(*FEs.back().get(), DR)})
              .first);
   }
   FileEntryRef addFileAlias(StringRef Name, FileEntryRef Base) {
TEST(FileEntryTest, isSameRef) {
   FileEntryRef R1Also = Refs.addFileAlias("1-also", R1);
 
   EXPECT_TRUE(R1.isSameRef(FileEntryRef(R1)));
   EXPECT_TRUE(R1.isSameRef(FileEntryRef(R1.getMapEntry())));
   EXPECT_FALSE(R1.isSameRef(R2));
   EXPECT_FALSE(R1.isSameRef(R1Also));
 }
 
+TEST(FileEntryTest, DenseMapInfo) {
+  RefMaps Refs;
+  FileEntryRef R1 = Refs.addFile("1");
+  FileEntryRef R2 = Refs.addFile("2");
+  FileEntryRef R1Also = Refs.addFileAlias("1-also", R1);
+
+  // Insert R1Also first and confirm it "wins".
+  {
+    SmallDenseSet<FileEntryRef, 8> Set;
+    Set.insert(R1Also);
+    Set.insert(R1);
+    Set.insert(R2);
+    EXPECT_TRUE(Set.find(R1Also)->isSameRef(R1Also));
+    EXPECT_TRUE(Set.find(R1)->isSameRef(R1Also));
+    EXPECT_TRUE(Set.find(R2)->isSameRef(R2));
+  }
+
+  // Insert R1Also second and confirm R1 "wins".
+  {
+    SmallDenseSet<FileEntryRef, 8> Set;
+    Set.insert(R1);
+    Set.insert(R1Also);
+    Set.insert(R2);
+    EXPECT_TRUE(Set.find(R1Also)->isSameRef(R1));
+    EXPECT_TRUE(Set.find(R1)->isSameRef(R1));
+    EXPECT_TRUE(Set.find(R2)->isSameRef(R2));
+  }
+}
+
+TEST(DirectoryEntryTest, isSameRef) {
+  RefMaps Refs;
+  DirectoryEntryRef R1 = Refs.addDirectory("1");
+  DirectoryEntryRef R2 = Refs.addDirectory("2");
+  DirectoryEntryRef R1Also = Refs.addDirectoryAlias("1-also", R1);
+
+  EXPECT_TRUE(R1.isSameRef(DirectoryEntryRef(R1)));
+  EXPECT_TRUE(R1.isSameRef(DirectoryEntryRef(R1.getMapEntry())));
+  EXPECT_FALSE(R1.isSameRef(R2));
+  EXPECT_FALSE(R1.isSameRef(R1Also));
+}
+
+TEST(DirectoryEntryTest, DenseMapInfo) {
+  RefMaps Refs;
+  DirectoryEntryRef R1 = Refs.addDirectory("1");
+  DirectoryEntryRef R2 = Refs.addDirectory("2");
+  DirectoryEntryRef R1Also = Refs.addDirectoryAlias("1-also", R1);
+
+  // Insert R1Also first and confirm it "wins".
+  {
+    SmallDenseSet<DirectoryEntryRef, 8> Set;
+    Set.insert(R1Also);
+    Set.insert(R1);
+    Set.insert(R2);
+    EXPECT_TRUE(Set.find(R1Also)->isSameRef(R1Also));
+    EXPECT_TRUE(Set.find(R1)->isSameRef(R1Also));
+    EXPECT_TRUE(Set.find(R2)->isSameRef(R2));
+  }
+
+  // Insert R1Also second and confirm R1 "wins".
+  {
+    SmallDenseSet<DirectoryEntryRef, 8> Set;
+    Set.insert(R1);
+    Set.insert(R1Also);
+    Set.insert(R2);
+    EXPECT_TRUE(Set.find(R1Also)->isSameRef(R1));
+    EXPECT_TRUE(Set.find(R1)->isSameRef(R1));
+    EXPECT_TRUE(Set.find(R2)->isSameRef(R2));
+  }
+}
+
 } // end namespace