[clang][clangd] Use reverse header map lookup in suggestPathToFileForDiagnostics

[DmitryPolukhin]

Summary

suggestPathToFileForDiagnostics is actively used in clangd for converting
an absolute path to a header file to a header name as it should be spelled
in the sources. Current approach converts absolute path to relative path.
This diff implements missing logic that makes a reverse lookup from the
relative path to the key in the header map that should be used in the sources.

Prerequisite diff https://reviews.llvm.org/D103229

Test Plan: check-clang

[DmitryPolukhin]

Fix clang-format issue

[DmitryPolukhin]

Fix linter

[bruno]

clang/lib/Lex/HeaderSearch.cpp

1851–1864

-> filename

1855

Can we save some dir scanning time by adding this logic to the previous loop? Shouldn't get hard to read if you early continue for each failed condition.

1859

I guess one of the rationale behind this change is that whatever is consuming your diagnostics is expecting the hmap key entry as an actionable path they could use.

I wonder whether other consumers of suggestPathToFileForDiagnostics expect an actual mapped value or just don't care. If the former, this might be better under some flag.

@dexonsmith @vsapsai @JDevlieghere @arphaman how does this relate with what you expect out of suggestPathToFileForDiagnostics? (If at all).

[dexonsmith]

Naively, this sounds like it could be a non-trivial tax on build times. But it looks like it's only called in Clang from Sema::diagnoseMissingImport, which only happens on error anyway.

clang/unittests/Lex/HeaderMapTest.cpp

9

Splitting this out seems like a great idea, but please split it out to a separate prep commit that's NFC.

[DmitryPolukhin]

Split changes into NFC https://reviews.llvm.org/D103229 and the rest

[DmitryPolukhin]

In D103142#2783665, @dexonsmith wrote:

Naively, this sounds like it could be a non-trivial tax on build times. But it looks like it's only called in Clang from Sema::diagnoseMissingImport, which only happens on error anyway.

Yes, in Clang suggestPathToFileForDiagnostics is used only in Sema::diagnoseMissingImport. In addition to clangd this function is also used in clang-include-fixer but new logic should also work there too (add @bkramer author of clang-include-fixer). This diff builds reverse index lazy only when it is required so it shouldn't normal build speed.

clang/lib/Lex/HeaderSearch.cpp

1855

It seems that unfortunately no, because we need the previous loop to convert absolute path into relative and this loop to convert relative path to key in header map. Normal header lookup also happens as two lookups: first lookup uses header map to convert key to relative path and then another lookup of the relative path.

1855

It seems that unfortunately no, because we need the previous loop to convert absolute path into relative and this loop to convert relative path to key in header map. Normal header lookup also happens as two lookups: first lookup uses header map to convert key to relative path and then another lookup of the relative path.

1859

I think it is safe to change default behaviour without introducing new flag/option because I don't expect that anyone really needs value from header map search in the source.

clang/unittests/Lex/HeaderMapTest.cpp

9

Done, https://reviews.llvm.org/D103229

[DmitryPolukhin]

Fix forgotten comment

[bruno]

Overall looks good, few remaining nitpicks.

clang/lib/Lex/HeaderMap.cpp

245

Please rewrite this to early return in case this isn't empty.

clang/lib/Lex/HeaderSearch.cpp

1856

Similar from above: rewrite to early continue if it's not meeting the conditions.

[DmitryPolukhin]

Resolved comments

clang/lib/Lex/HeaderMap.cpp

245

Done, but it causes a bit of code duplication due to second lookup. Please let me know if you thought about rewriting it somehow else.

[DmitryPolukhin]

Rebase + try build on Windows again

[bruno]

clang/lib/Lex/HeaderMap.cpp

265

How about something along the lines of:

...
StringRef Key;
for (unsigned i = 0; i != NumBuckets; ++i) {
    HMapBucket B = getBucket(i);
    if (B.Key == HMAP_EmptyBucketKey)
      continue;

    Key = getString(B.Key);
    Optional<StringRef> Prefix = getString(B.Prefix);
    Optional<StringRef> Suffix = getString(B.Suffix);
    if (!Key.empty() && Prefix && Suffix) {
      SmallVector<char, 1024> Buf;
      Buf.append(Prefix->begin(), Prefix->end());
      Buf.append(Suffix->begin(), Suffix->end());
      ReverseMap[StringRef(Buf.begin(), Buf.size())] = Key;
      break;
    }
}
assert(!Key.empty() && "expected valid key");
return Key;

While proposing this change I've noticed that it would keep looking for other buckets even in face of a valid result, so I've added a break. Was that intentional?

[DmitryPolukhin]

Updated HeaderMapImpl::reverseLookupFilename according to the review comment

[DmitryPolukhin]

clang/lib/Lex/HeaderMap.cpp

265

Yes, keep iterating over all key-value pairs in the header map is important to add all elements to the map for subsequent lookups. If we stop on the current match, next lookup will not even try to populate the reverse lookup map (because the map is not empty) but not all elements are in the map due to early return from previous lookup, so subsequent lookup may not find the match even if it exists in the header map. We also cannot expect that DestPath is present in the given header map, so we cannot assert if it is missing. This function should return empty string as an indication that DestPath is not found.

Updated implementation with the review suggestion, please take another look.

[bruno]

LGTM!

[DmitryPolukhin]

@bruno and @dexonsmith thank you for the review!

clang/include/clang/Lex/HeaderMap.h

 //===--- HeaderMap.h - A file that acts like dir of symlinks ----*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the HeaderMap interface.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LEX_HEADERMAP_H
 #define LLVM_CLANG_LEX_HEADERMAP_H
 
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <memory>
 
 namespace clang {
 
 struct HMapBucket;
 struct HMapHeader;
 
 /// Implementation for \a HeaderMap that doesn't depend on \a FileManager.
 class HeaderMapImpl {
   std::unique_ptr<const llvm::MemoryBuffer> FileBuffer;
   bool NeedsBSwap;
+  mutable llvm::StringMap<StringRef> ReverseMap;
 
 public:
   HeaderMapImpl(std::unique_ptr<const llvm::MemoryBuffer> File, bool NeedsBSwap)
       : FileBuffer(std::move(File)), NeedsBSwap(NeedsBSwap) {}
 
   // Check for a valid header and extract the byte swap.
   static bool checkHeader(const llvm::MemoryBuffer &File, bool &NeedsByteSwap);
 
   /// If the specified relative filename is located in this HeaderMap return
   /// the filename it is mapped to, otherwise return an empty StringRef.
   StringRef lookupFilename(StringRef Filename,
                            SmallVectorImpl<char> &DestPath) const;
 
   /// Return the filename of the headermap.
   StringRef getFileName() const;
 
   /// Print the contents of this headermap to stderr.
   void dump() const;
 
+  /// Return key for specifed path.
+  StringRef reverseLookupFilename(StringRef DestPath) const;
+
 private:
   unsigned getEndianAdjustedWord(unsigned X) const;
   const HMapHeader &getHeader() const;
   HMapBucket getBucket(unsigned BucketNo) const;
 
   /// Look up the specified string in the string table.  If the string index is
   /// not valid, return None.
   Optional<StringRef> getString(unsigned StrTabIdx) const;
public:
   /// NULL and the file is found, RawPath will be set to the raw path at which
   /// the file was found in the file system. For example, for a search path
   /// ".." and a filename "../file.h" this would be "../../file.h".
   Optional<FileEntryRef> LookupFile(StringRef Filename, FileManager &FM) const;
 
   using HeaderMapImpl::lookupFilename;
   using HeaderMapImpl::getFileName;
   using HeaderMapImpl::dump;
+  using HeaderMapImpl::reverseLookupFilename;
 };
 
 } // end namespace clang.
 
 #endif

clang/lib/Lex/HeaderMap.cpp

 //===--- HeaderMap.cpp - A file that acts like dir of symlinks ------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) {
     DestPath.clear();
     if (LLVM_LIKELY(Prefix && Suffix)) {
       DestPath.append(Prefix->begin(), Prefix->end());
       DestPath.append(Suffix->begin(), Suffix->end());
     }
     return StringRef(DestPath.begin(), DestPath.size());
   }
 }
+
+StringRef HeaderMapImpl::reverseLookupFilename(StringRef DestPath) const {
+  if (ReverseMap.empty()) {
+    const HMapHeader &Hdr = getHeader();
+    unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
+    for (unsigned i = 0; i != NumBuckets; ++i) {
+      HMapBucket B = getBucket(i);
+      if (B.Key == HMAP_EmptyBucketKey)
+        continue;
+
+      Optional<StringRef> Key = getString(B.Key);
+      Optional<StringRef> Prefix = getString(B.Prefix);
+      Optional<StringRef> Suffix = getString(B.Suffix);
+      if (Key && Prefix && Suffix) {
+        SmallVector<char, 1024> Buf;
+        Buf.append(Prefix->begin(), Prefix->end());
+        Buf.append(Suffix->begin(), Suffix->end());
+        ReverseMap[StringRef(Buf.begin(), Buf.size())] = *Key;
+      }
+    }
+  }
+  return ReverseMap.lookup(DestPath);
+}

clang/lib/Lex/HeaderSearch.cpp

 //===- HeaderSearch.cpp - Resolve Header File Locations -------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
for (auto NI = path::begin(File), NE = path::end(File),
 
       if (*NI != *DI)
         break;
     }
     return false;
   };
 
   for (unsigned I = 0; I != SearchDirs.size(); ++I) {
-    // FIXME: Support this search within frameworks and header maps.
+    // FIXME: Support this search within frameworks.
     if (!SearchDirs[I].isNormalDir())
       continue;
 
     StringRef Dir = SearchDirs[I].getDir()->getName();
     if (CheckDir(Dir) && IsSystem)
       *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
   }
 
   // Try to shorten include path using TUs directory, if we couldn't find any
   // suitable prefix in include search paths.
   if (!BestPrefixLength && CheckDir(path::parent_path(MainFile)) && IsSystem)
     *IsSystem = false;
 
-
-  return path::convert_to_slash(File.drop_front(BestPrefixLength));
+  // Try resolving resulting filaname via reverse search in header maps,
+  // key from header name is user prefered name for the include file.
+  StringRef Filename = File.drop_front(BestPrefixLength);
+  for (unsigned I = 0; I != SearchDirs.size(); ++I) {
+    if (SearchDirs[I].isHeaderMap()) {
+      StringRef SpelledFilename =
+          SearchDirs[I].getHeaderMap()->reverseLookupFilename(Filename);
+      if (!SpelledFilename.empty()) {
+        Filename = SpelledFilename;
+        break;
+      }
+    }
+  }
+  return path::convert_to_slash(Filename);
 }

clang/unittests/Lex/HeaderMapTest.cpp

 //===- unittests/Lex/HeaderMapTest.cpp - HeaderMap tests ----------===//
 //
 // 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/CharInfo.h"
-#include "clang/Lex/HeaderMap.h"
-#include "clang/Lex/HeaderMapTypes.h"
+#include "HeaderMapTestUtils.h"
 #include "llvm/ADT/SmallString.h"
-#include "llvm/Support/SwapByteOrder.h"
 #include "gtest/gtest.h"
-#include <cassert>
 #include <type_traits>
 
 using namespace clang;
 using namespace llvm;
+using namespace clang::test;
 
 namespace {
 
-// Lay out a header file for testing.
-template <unsigned NumBuckets, unsigned NumBytes> struct MapFile {
-  HMapHeader Header;
-  HMapBucket Buckets[NumBuckets];
-  unsigned char Bytes[NumBytes];
-
-  void init() {
-    memset(this, 0, sizeof(MapFile));
-    Header.Magic = HMAP_HeaderMagicNumber;
-    Header.Version = HMAP_HeaderVersion;
-    Header.NumBuckets = NumBuckets;
-    Header.StringsOffset = sizeof(Header) + sizeof(Buckets);
-  }
-
-  void swapBytes() {
-    using llvm::sys::getSwappedBytes;
-    Header.Magic = getSwappedBytes(Header.Magic);
-    Header.Version = getSwappedBytes(Header.Version);
-    Header.NumBuckets = getSwappedBytes(Header.NumBuckets);
-    Header.StringsOffset = getSwappedBytes(Header.StringsOffset);
-  }
-
-  std::unique_ptr<const MemoryBuffer> getBuffer() const {
-    return MemoryBuffer::getMemBuffer(
-        StringRef(reinterpret_cast<const char *>(this), sizeof(MapFile)),
-        "header",
-        /* RequresNullTerminator */ false);
-  }
-};
-
-// The header map hash function.
-static inline unsigned getHash(StringRef Str) {
-  unsigned Result = 0;
-  for (char C : Str)
-    Result += toLowercase(C) * 13;
-  return Result;
-}
-
-template <class FileTy> struct FileMaker {
-  FileTy &File;
-  unsigned SI = 1;
-  unsigned BI = 0;
-  FileMaker(FileTy &File) : File(File) {}
-
-  unsigned addString(StringRef S) {
-    assert(SI + S.size() + 1 <= sizeof(File.Bytes));
-    std::copy(S.begin(), S.end(), File.Bytes + SI);
-    auto OldSI = SI;
-    SI += S.size() + 1;
-    return OldSI;
-  }
-  void addBucket(unsigned Hash, unsigned Key, unsigned Prefix, unsigned Suffix) {
-    assert(!(File.Header.NumBuckets & (File.Header.NumBuckets - 1)));
-    unsigned I = Hash & (File.Header.NumBuckets - 1);
-    do {
-      if (!File.Buckets[I].Key) {
-        File.Buckets[I].Key = Key;
-        File.Buckets[I].Prefix = Prefix;
-        File.Buckets[I].Suffix = Suffix;
-        ++File.Header.NumEntries;
-        return;
-      }
-      ++I;
-      I &= File.Header.NumBuckets - 1;
-    } while (I != (Hash & (File.Header.NumBuckets - 1)));
-    llvm_unreachable("no empty buckets");
-  }
-};
-
 TEST(HeaderMapTest, checkHeaderEmpty) {
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(
       *MemoryBuffer::getMemBufferCopy("", "empty"), NeedsSwap));
   ASSERT_FALSE(HeaderMapImpl::checkHeader(
       *MemoryBuffer::getMemBufferCopy("", "empty"), NeedsSwap));
 }
 
 TEST(HeaderMapTest, checkHeaderMagic) {
-  MapFile<1, 1> File;
+  HMapFileMock<1, 1> File;
   File.init();
   File.Header.Magic = 0;
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
 }
 
 TEST(HeaderMapTest, checkHeaderReserved) {
-  MapFile<1, 1> File;
+  HMapFileMock<1, 1> File;
   File.init();
   File.Header.Reserved = 1;
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
 }
 
 TEST(HeaderMapTest, checkHeaderVersion) {
-  MapFile<1, 1> File;
+  HMapFileMock<1, 1> File;
   File.init();
   ++File.Header.Version;
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
 }
 
 TEST(HeaderMapTest, checkHeaderValidButEmpty) {
-  MapFile<1, 1> File;
+  HMapFileMock<1, 1> File;
   File.init();
   bool NeedsSwap;
   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
   ASSERT_FALSE(NeedsSwap);
 
   File.swapBytes();
   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
   ASSERT_TRUE(NeedsSwap);
 }
 
 TEST(HeaderMapTest, checkHeader3Buckets) {
-  MapFile<3, 1> File;
+  HMapFileMock<3, 1> File;
   ASSERT_EQ(3 * sizeof(HMapBucket), sizeof(File.Buckets));
 
   File.init();
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
 }
 
 TEST(HeaderMapTest, checkHeader0Buckets) {
   // Create with 1 bucket to avoid 0-sized arrays.
-  MapFile<1, 1> File;
+  HMapFileMock<1, 1> File;
   File.init();
   File.Header.NumBuckets = 0;
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
 }
 
 TEST(HeaderMapTest, checkHeaderNotEnoughBuckets) {
-  MapFile<1, 1> File;
+  HMapFileMock<1, 1> File;
   File.init();
   File.Header.NumBuckets = 8;
   bool NeedsSwap;
   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
 }
 
 TEST(HeaderMapTest, lookupFilename) {
-  typedef MapFile<2, 7> FileTy;
+  typedef HMapFileMock<2, 7> FileTy;
   FileTy File;
   File.init();
 
-  FileMaker<FileTy> Maker(File);
+  HMapFileMockMaker<FileTy> Maker(File);
   auto a = Maker.addString("a");
   auto b = Maker.addString("b");
   auto c = Maker.addString("c");
-  Maker.addBucket(getHash("a"), a, b, c);
+  Maker.addBucket("a", a, b, c);
 
   bool NeedsSwap;
   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
   ASSERT_FALSE(NeedsSwap);
   HeaderMapImpl Map(File.getBuffer(), NeedsSwap);
 
   SmallString<8> DestPath;
   ASSERT_EQ("bc", Map.lookupFilename("a", DestPath));
 }
 
 template <class FileTy, class PaddingTy> struct PaddedFile {
   FileTy File;
   PaddingTy Padding;
 };
 
 TEST(HeaderMapTest, lookupFilenameTruncatedSuffix) {
-  typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy;
+  typedef HMapFileMock<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)>
+      FileTy;
   static_assert(std::is_standard_layout<FileTy>::value,
                 "Expected standard layout");
   static_assert(sizeof(FileTy) == 64, "check the math");
   PaddedFile<FileTy, uint64_t> P;
   auto &File = P.File;
   auto &Padding = P.Padding;
   File.init();
 
-  FileMaker<FileTy> Maker(File);
+  HMapFileMockMaker<FileTy> Maker(File);
   auto a = Maker.addString("a");
   auto b = Maker.addString("b");
   auto c = Maker.addString("c");
-  Maker.addBucket(getHash("a"), a, b, c);
+  Maker.addBucket("a", a, b, c);
 
   // Add 'x' characters to cause an overflow into Padding.
   ASSERT_EQ('c', File.Bytes[5]);
   for (unsigned I = 6; I < sizeof(File.Bytes); ++I) {
     ASSERT_EQ(0, File.Bytes[I]);
     File.Bytes[I] = 'x';
   }
   Padding = 0xffffffff; // Padding won't stop it either.
 
   bool NeedsSwap;
   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
   ASSERT_FALSE(NeedsSwap);
   HeaderMapImpl Map(File.getBuffer(), NeedsSwap);
 
   // The string for "c" runs to the end of File.  Check that the suffix
   // ("cxxxx...") is detected as truncated, and an empty string is returned.
   SmallString<24> DestPath;
   ASSERT_EQ("", Map.lookupFilename("a", DestPath));
 }
 
 TEST(HeaderMapTest, lookupFilenameTruncatedPrefix) {
-  typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy;
+  typedef HMapFileMock<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)>
+      FileTy;
   static_assert(std::is_standard_layout<FileTy>::value,
                 "Expected standard layout");
   static_assert(sizeof(FileTy) == 64, "check the math");
   PaddedFile<FileTy, uint64_t> P;
   auto &File = P.File;
   auto &Padding = P.Padding;
   File.init();
 
-  FileMaker<FileTy> Maker(File);
+  HMapFileMockMaker<FileTy> Maker(File);
   auto a = Maker.addString("a");
   auto c = Maker.addString("c");
   auto b = Maker.addString("b"); // Store the prefix last.
-  Maker.addBucket(getHash("a"), a, b, c);
+  Maker.addBucket("a", a, b, c);
 
   // Add 'x' characters to cause an overflow into Padding.
   ASSERT_EQ('b', File.Bytes[5]);
   for (unsigned I = 6; I < sizeof(File.Bytes); ++I) {
     ASSERT_EQ(0, File.Bytes[I]);
     File.Bytes[I] = 'x';
   }
   Padding = 0xffffffff; // Padding won't stop it either.

clang/unittests/Lex/HeaderMapTestUtils.h

+//===- unittests/Lex/HeaderMapTestUtils.h - HeaderMap utils -------===//
+//
+// 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_UNITTESTS_LEX_HEADERMAPTESTUTILS_H
+#define LLVM_CLANG_UNITTESTS_LEX_HEADERMAPTESTUTILS_H
+
+#include "clang/Basic/CharInfo.h"
+#include "clang/Lex/HeaderMap.h"
+#include "clang/Lex/HeaderMapTypes.h"
+#include "llvm/Support/SwapByteOrder.h"
+#include <cassert>
+
+namespace clang {
+namespace test {
+
+// Lay out a header file for testing.
+template <unsigned NumBuckets, unsigned NumBytes> struct HMapFileMock {
+  HMapHeader Header;
+  HMapBucket Buckets[NumBuckets];
+  unsigned char Bytes[NumBytes];
+
+  void init() {
+    memset(this, 0, sizeof(HMapFileMock));
+    Header.Magic = HMAP_HeaderMagicNumber;
+    Header.Version = HMAP_HeaderVersion;
+    Header.NumBuckets = NumBuckets;
+    Header.StringsOffset = sizeof(Header) + sizeof(Buckets);
+  }
+
+  void swapBytes() {
+    using llvm::sys::getSwappedBytes;
+    Header.Magic = getSwappedBytes(Header.Magic);
+    Header.Version = getSwappedBytes(Header.Version);
+    Header.NumBuckets = getSwappedBytes(Header.NumBuckets);
+    Header.StringsOffset = getSwappedBytes(Header.StringsOffset);
+  }
+
+  std::unique_ptr<llvm::MemoryBuffer> getBuffer() {
+    return llvm::MemoryBuffer::getMemBuffer(
+        StringRef(reinterpret_cast<char *>(this), sizeof(HMapFileMock)),
+        "header",
+        /* RequresNullTerminator */ false);
+  }
+};
+
+template <class FileTy> struct HMapFileMockMaker {
+  FileTy &File;
+  unsigned SI = 1;
+  unsigned BI = 0;
+  HMapFileMockMaker(FileTy &File) : File(File) {}
+
+  unsigned addString(StringRef S) {
+    assert(SI + S.size() + 1 <= sizeof(File.Bytes));
+    std::copy(S.begin(), S.end(), File.Bytes + SI);
+    auto OldSI = SI;
+    SI += S.size() + 1;
+    return OldSI;
+  }
+
+  void addBucket(StringRef Str, unsigned Key, unsigned Prefix,
+                 unsigned Suffix) {
+    addBucket(getHash(Str), Key, Prefix, Suffix);
+  }
+
+  void addBucket(unsigned Hash, unsigned Key, unsigned Prefix,
+                 unsigned Suffix) {
+    assert(!(File.Header.NumBuckets & (File.Header.NumBuckets - 1)));
+    unsigned I = Hash & (File.Header.NumBuckets - 1);
+    do {
+      if (!File.Buckets[I].Key) {
+        File.Buckets[I].Key = Key;
+        File.Buckets[I].Prefix = Prefix;
+        File.Buckets[I].Suffix = Suffix;
+        ++File.Header.NumEntries;
+        return;
+      }
+      ++I;
+      I &= File.Header.NumBuckets - 1;
+    } while (I != (Hash & (File.Header.NumBuckets - 1)));
+    llvm_unreachable("no empty buckets");
+  }
+
+  // The header map hash function.
+  static unsigned getHash(StringRef Str) {
+    unsigned Result = 0;
+    for (char C : Str)
+      Result += toLowercase(C) * 13;
+    return Result;
+  }
+};
+
+} // namespace test
+} // namespace clang
+
+#endif

clang/unittests/Lex/HeaderSearchTest.cpp

 //===- unittests/Lex/HeaderSearchTest.cpp ------ HeaderSearch tests -------===//
 //
 // 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/Lex/HeaderSearch.h"
+#include "HeaderMapTestUtils.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Basic/TargetOptions.h"
 #include "clang/Lex/HeaderSearch.h"
void addSearchDir(llvm::StringRef Dir) {
     VFS->addFile(Dir, 0, llvm::MemoryBuffer::getMemBuffer(""), /*User=*/None,
                  /*Group=*/None, llvm::sys::fs::file_type::directory_file);
     auto DE = FileMgr.getOptionalDirectoryRef(Dir);
     assert(DE);
     auto DL = DirectoryLookup(*DE, SrcMgr::C_User, /*isFramework=*/false);
     Search.AddSearchPath(DL, /*isAngled=*/false);
   }
 
+  void addHeaderMap(llvm::StringRef Filename,
+                    std::unique_ptr<llvm::MemoryBuffer> Buf) {
+    VFS->addFile(Filename, 0, std::move(Buf), /*User=*/None, /*Group=*/None,
+                 llvm::sys::fs::file_type::regular_file);
+    auto FE = FileMgr.getFile(Filename, true);
+    assert(FE);
+
+    // Test class supports only one HMap at a time.
+    assert(!HMap);
+    HMap = HeaderMap::Create(*FE, FileMgr);
+    auto DL =
+        DirectoryLookup(HMap.get(), SrcMgr::C_User, /*isFramework=*/false);
+    Search.AddSearchPath(DL, /*isAngled=*/false);
+  }
+
   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> VFS;
   FileSystemOptions FileMgrOpts;
   FileManager FileMgr;
   IntrusiveRefCntPtr<DiagnosticIDs> DiagID;
   DiagnosticsEngine Diags;
   SourceManager SourceMgr;
   LangOptions LangOpts;
   std::shared_ptr<TargetOptions> TargetOpts;
   IntrusiveRefCntPtr<TargetInfo> Target;
   HeaderSearch Search;
+  std::unique_ptr<HeaderMap> HMap;
 };
 
 TEST_F(HeaderSearchTest, NoSearchDir) {
   EXPECT_EQ(Search.search_dir_size(), 0u);
   EXPECT_EQ(Search.suggestPathToFileForDiagnostics("/x/y/z", /*WorkingDir=*/"",
                                                    /*MainFile=*/""),
             "/x/y/z");
 }
TEST_F(HeaderSearchTest, IncludeFromSameDirectory) {
 
   addSearchDir("/");
   EXPECT_EQ(Search.suggestPathToFileForDiagnostics("/y/z/t.h",
                                                    /*WorkingDir=*/"",
                                                    /*MainFile=*/"/y/a.cc"),
             "y/z/t.h");
 }
 
+// Helper struct with null terminator character to make MemoryBuffer happy.
+template <class FileTy, class PaddingTy>
+struct NullTerminatedFile : public FileTy {
+  PaddingTy Padding = 0;
+};
+
+TEST_F(HeaderSearchTest, HeaderMapReverseLookup) {
+  typedef NullTerminatedFile<test::HMapFileMock<2, 32>, char> FileTy;
+  FileTy File;
+  File.init();
+
+  test::HMapFileMockMaker<FileTy> Maker(File);
+  auto a = Maker.addString("d.h");
+  auto b = Maker.addString("b/");
+  auto c = Maker.addString("c.h");
+  Maker.addBucket("d.h", a, b, c);
+
+  addHeaderMap("/x/y/z.hmap", File.getBuffer());
+  addSearchDir("/a");
+
+  EXPECT_EQ(Search.suggestPathToFileForDiagnostics("/a/b/c.h",
+                                                   /*WorkingDir=*/"",
+                                                   /*MainFile=*/""),
+            "d.h");
+}
+
 } // namespace
 } // namespace clang