Author: Duncan P. N. Exon Smith Date: 2020-12-08T18:10:53-08:00 New Revision: 2878e965af27ce037378a4f0409e89039108c09f
URL: https://github.com/llvm/llvm-project/commit/2878e965af27ce037378a4f0409e89039108c09f DIFF: https://github.com/llvm/llvm-project/commit/2878e965af27ce037378a4f0409e89039108c09f.diff LOG: Basic: Add hashing support for FileEntryRef and DirectoryEntryRef Allow hashing FileEntryRef and DirectoryEntryRef via `hash_value`, and use that to implement `DenseMapInfo`. This hash should be equal whenever the entry is the same (the name used to reference it is not relevant). Also add `DirectoryEntryRef::isSameRef` to simplify the implementation and facilitate testing. Differential Revision: https://reviews.llvm.org/D92627 Added: Modified: clang/include/clang/Basic/DirectoryEntry.h clang/include/clang/Basic/FileEntry.h clang/unittests/Basic/FileEntryTest.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Basic/DirectoryEntry.h b/clang/include/clang/Basic/DirectoryEntry.h index 4e229962bdcc..e0f4ae28321a 100644 --- a/clang/include/clang/Basic/DirectoryEntry.h +++ b/clang/include/clang/Basic/DirectoryEntry.h @@ -15,6 +15,8 @@ #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" @@ -46,10 +48,19 @@ class DirectoryEntryRef { 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) {} @@ -80,6 +91,20 @@ class DirectoryEntryRef { 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; }; @@ -164,6 +189,38 @@ static_assert( "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 { diff --git a/clang/include/clang/Basic/FileEntry.h b/clang/include/clang/Basic/FileEntry.h index 75158d44bf5a..8db5446aa8d4 100644 --- a/clang/include/clang/Basic/FileEntry.h +++ b/clang/include/clang/Basic/FileEntry.h @@ -16,6 +16,8 @@ #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" @@ -88,6 +90,12 @@ class FileEntryRef { 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. @@ -154,6 +162,20 @@ class FileEntryRef { 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; }; @@ -197,6 +219,35 @@ 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 { diff --git a/clang/unittests/Basic/FileEntryTest.cpp b/clang/unittests/Basic/FileEntryTest.cpp index f2619a21def7..3cc01870b800 100644 --- a/clang/unittests/Basic/FileEntryTest.cpp +++ b/clang/unittests/Basic/FileEntryTest.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "clang/Basic/FileEntry.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/StringMap.h" #include "gtest/gtest.h" @@ -22,11 +23,21 @@ 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(*Dirs.insert({"dir", D}).first) {} + RefMaps() : DR(addDirectory("dir")) {} + + 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>()); @@ -112,4 +123,74 @@ TEST(FileEntryTest, isSameRef) { 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 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
