[clangd] Store source file hash in IndexFile{In,Out}

[kadircet]

Summary

Puts the digest of the source file that generated the index into
serialized index and stores them back on load, if exists.

[jkorous]

Hi Kadir, I have one small nit otherwise LGTM.

clangd/index/Serialization.cpp

368

Nit: Maybe we could use Result.Digest.size() and avoid having 20 hardcoded here?

[kadircet]

• Use digest size instead of hardcoding it.

[sammccall]

clangd/index/Serialization.cpp

330

update

366

I'd call this chunk "srcs" or so - I suspect we may want to include path info and/or dependencies in the future.

368

It's still in a couple of places in Serialization.h. Could we add an alias there e.g. using FileDigest = std::array<uint8_t, 20>?

[kadircet]

• Address comments.

clangd/index/Background.cpp

for (const auto &F : Files) {
     auto Hash = FilesToUpdate.lookup(Path);
     // We need to store shards before updating the index, since the latter
     // consumes slabs.
     // FIXME: Store Hash in the Shard.
     if (IndexStorage) {
       IndexFileOut Shard;
       Shard.Symbols = SS.get();
       Shard.Refs = RS.get();
+      Shard.Digest = &Hash;
       if (auto Error = IndexStorage->storeShard(Path, Shard))
         elog("Failed to write background-index shard for file {0}: {1}", Path,
              std::move(Error));
     }
 
     std::lock_guard<std::mutex> Lock(DigestsMu);
     // This can override a newer version that is added in another thread,
     // if this thread sees the older version but finishes later. This should be

clangd/index/Serialization.h

enum class IndexFileFormat {
   RIFF, // Versioned binary format, suitable for production use.
   YAML, // Human-readable format, suitable for experiments and debugging.
 };
 
 // Holds the contents of an index file that was read.
 struct IndexFileIn {
   llvm::Optional<SymbolSlab> Symbols;
   llvm::Optional<RefSlab> Refs;
+  // Digest of the source file that generated the contents.
+  llvm::Optional<std::array<uint8_t, 20>> Digest;
 };
 // Parse an index file. The input must be a RIFF or YAML file.
 llvm::Expected<IndexFileIn> readIndexFile(llvm::StringRef);
 
 // Specifies the contents of an index file to be written.
 struct IndexFileOut {
   const SymbolSlab *Symbols = nullptr;
   const RefSlab *Refs = nullptr;
+  // Digest of the source file that generated the contents.
+  const std::array<uint8_t, 20> *Digest = nullptr;
   // TODO: Support serializing Dex posting lists.
   IndexFileFormat Format = IndexFileFormat::RIFF;
 
   IndexFileOut() = default;
   IndexFileOut(const IndexFileIn &I)
       : Symbols(I.Symbols ? I.Symbols.getPointer() : nullptr),
         Refs(I.Refs ? I.Refs.getPointer() : nullptr) {}
 };

clangd/index/Serialization.cpp

std::pair<SymbolID, std::vector<Ref>> readRefs(Reader &Data,
   Result.second.resize(Data.consumeVar());
   for (auto &Ref : Result.second) {
     Ref.Kind = static_cast<RefKind>(Data.consume8());
     Ref.Location = readLocation(Data, Strings);
   }
   return Result;
 }
 
 // FILE ENCODING
 // A file is a RIFF chunk with type 'CdIx'.
 // It contains the sections:
 //   - meta: version number
 //   - stri: string table
 //   - symb: symbols
 //   - refs: references to symbols
 
 // The current versioning scheme is simple - non-current versions are rejected.
Expected<IndexFileIn> readRIFF(StringRef Data) {
   if (Meta.consume32() != Version)
     return makeError("wrong version");
 
   auto Strings = readStringTable(Chunks.lookup("stri"));
   if (!Strings)
     return Strings.takeError();
 
   IndexFileIn Result;
+  if (Chunks.count("hash")) {
+    Reader Hash(Chunks.lookup("hash"));
+    Result.Digest.emplace();
+    llvm::StringRef Digest = Hash.consume(Result.Digest->size());
+    std::copy(Digest.bytes_begin(), Digest.bytes_end(), Result.Digest->begin());
+  }
+
   if (Chunks.count("symb")) {
     Reader SymbolReader(Chunks.lookup("symb"));
     SymbolSlab::Builder Symbols;
     while (!SymbolReader.eof())
       Symbols.insert(readSymbol(SymbolReader, Strings->Strings));
     if (SymbolReader.err())
       return makeError("malformed or truncated symbol");
     Result.Symbols = std::move(Symbols).build();
void writeRIFF(const IndexFileOut &Data, raw_ostream &OS) {
 
   SmallString<4> Meta;
   {
     raw_svector_ostream MetaOS(Meta);
     write32(Version, MetaOS);
   }
   RIFF.Chunks.push_back({riff::fourCC("meta"), Meta});
 
+  if (Data.Digest) {
+    llvm::StringRef Hash(reinterpret_cast<const char *>(Data.Digest->data()),
+                         Data.Digest->size());
+    RIFF.Chunks.push_back({riff::fourCC("hash"), Hash});
+  }
+
   StringTableOut Strings;
   std::vector<Symbol> Symbols;
   for (const auto &Sym : *Data.Symbols) {
     Symbols.emplace_back(Sym);
     visitStrings(Symbols.back(), [&](StringRef &S) { Strings.intern(S); });
   }
   std::vector<std::pair<SymbolID, std::vector<Ref>>> Refs;
   if (Data.Refs) {

unittests/clangd/BackgroundIndexTests.cpp

 
 TEST(BackgroundIndexTest, ShardStorageWriteTest) {
   MockFSProvider FS;
   FS.Files[testPath("root/A.h")] = R"cpp(
       void common();
       void f_b();
       class A_CC {};
       )cpp";
-  FS.Files[testPath("root/A.cc")] =
-      "#include \"A.h\"\nvoid g() { (void)common; }";
+  std::string A_CC = "#include \"A.h\"\nvoid g() { (void)common; }";
+  FS.Files[testPath("root/A.cc")] = A_CC;
+  auto Digest = llvm::SHA1::hash(
+      {reinterpret_cast<const uint8_t *>(A_CC.data()), A_CC.size()});
 
   llvm::StringMap<std::string> Storage;
   size_t CacheHits = 0;
   MemoryShardStorage MSS(Storage, CacheHits);
 
   tooling::CompileCommand Cmd;
   Cmd.Filename = testPath("root/A.cc");
   Cmd.Directory = testPath("root");
TEST(BackgroundIndexTest, ShardStorageWriteTest) {
   for (const auto &Ref : *ShardHeader->Refs)
     EXPECT_THAT(Ref.second,
                 UnorderedElementsAre(FileURI("unittest:///root/A.h")));
 
   auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
   EXPECT_NE(ShardSource, nullptr);
   EXPECT_THAT(*ShardSource->Symbols, UnorderedElementsAre());
   EXPECT_THAT(*ShardSource->Refs, RefsAre({FileURI("unittest:///root/A.cc")}));
+  EXPECT_EQ(*ShardSource->Digest, Digest);
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/SerializationTests.cpp

 //===-- SerializationTests.cpp - Binary and YAML serialization unit tests -===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "index/Index.h"
 #include "index/Serialization.h"
+#include "llvm/Support/SHA1.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::_;
 using testing::AllOf;
 using testing::Pair;
 using testing::UnorderedElementsAre;
TEST(SerializationTest, BinaryConversions) {
 
   // Assert the YAML serializations match, for nice comparisons and diffs.
   EXPECT_THAT(YAMLFromSymbols(*In2->Symbols),
               UnorderedElementsAreArray(YAMLFromSymbols(*In->Symbols)));
   EXPECT_THAT(YAMLFromRefs(*In2->Refs),
               UnorderedElementsAreArray(YAMLFromRefs(*In->Refs)));
 }
 
+TEST(SerializationTest, HashTest) {
+  auto In = readIndexFile(YAML);
+  EXPECT_TRUE(bool(In)) << In.takeError();
+
+  std::string TestContent("TESTCONTENT");
+  auto Digest =
+      llvm::SHA1::hash({reinterpret_cast<const uint8_t *>(TestContent.data()),
+                        TestContent.size()});
+  // Write to binary format, and parse again.
+  IndexFileOut Out(*In);
+  Out.Format = IndexFileFormat::RIFF;
+  Out.Digest = &Digest;
+  std::string Serialized = to_string(Out);
+
+  auto In2 = readIndexFile(Serialized);
+  ASSERT_TRUE(bool(In2)) << In.takeError();
+  ASSERT_EQ(In2->Digest, Digest);
+  ASSERT_TRUE(In2->Symbols);
+  ASSERT_TRUE(In2->Refs);
+
+  // Assert the YAML serializations match, for nice comparisons and diffs.
+  EXPECT_THAT(YAMLFromSymbols(*In2->Symbols),
+              UnorderedElementsAreArray(YAMLFromSymbols(*In->Symbols)));
+  EXPECT_THAT(YAMLFromRefs(*In2->Refs),
+              UnorderedElementsAreArray(YAMLFromRefs(*In->Refs)));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang