[clangd] Truncate SymbolID to 16 bytes.

[sammccall]

Summary

The goal is 8 bytes, which has a nonzero risk of collisions with huge indexes.
This patch should shake out any issues with truncation at all, we can lower
further later.

[ioeric]

We should watch out for the downstream backward compatibility.

clangd/index/Index.h

92 ↗

(On Diff #170684)

maybe SHA1(USR) truncated at RawSize bytes?

clangd/index/Serialization.cpp

303 ↗

(On Diff #170684)

A reminder from yourself: bump the binary version ;)

303 ↗

(On Diff #170684)

maybe use RawSize here instead of hardcoding?

[sammccall]

clangd/index/Serialization.cpp

303 ↗

(On Diff #170684)

I think it's actually more important that this is concrete than that it's correct :-)

clang-tools-extra/trunk/clangd/index/Index.h

inline bool operator<(const SymbolLocation &L, const SymbolLocation &R) {
   return std::tie(L.FileURI, L.Start, L.End) <
          std::tie(R.FileURI, R.Start, R.End);
 }
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &);
 
 // The class identifies a particular C++ symbol (class, function, method, etc).
 //
 // As USRs (Unified Symbol Resolution) could be large, especially for functions
-// with long type arguments, SymbolID is using 160-bits SHA1(USR) values to
+// with long type arguments, SymbolID is using truncated SHA1(USR) values to
 // guarantee the uniqueness of symbols while using a relatively small amount of
 // memory (vs storing USRs directly).
 //
 // SymbolID can be used as key in the symbol indexes to lookup the symbol.
 class SymbolID {
 public:
   SymbolID() = default;
   explicit SymbolID(llvm::StringRef USR);
 
   bool operator==(const SymbolID &Sym) const {
     return HashValue == Sym.HashValue;
   }
   bool operator<(const SymbolID &Sym) const {
     return HashValue < Sym.HashValue;
   }
 
-  constexpr static size_t RawSize = 20;
+  // The stored hash is truncated to RawSize bytes.
+  // This trades off memory against the number of symbols we can handle.
+  // FIXME: can we reduce this further to 8 bytes?
+  constexpr static size_t RawSize = 16;
   llvm::StringRef raw() const {
     return StringRef(reinterpret_cast<const char *>(HashValue.data()), RawSize);
   }
   static SymbolID fromRaw(llvm::StringRef);
 
-  // Returns a 40-bytes hex encoded string.
+  // Returns a hex encoded string.
   std::string str() const;
   static llvm::Expected<SymbolID> fromStr(llvm::StringRef);
 
 private:
   std::array<uint8_t, RawSize> HashValue;
 };
 
 inline llvm::hash_code hash_value(const SymbolID &ID) {

clang-tools-extra/trunk/clangd/index/Index.cpp

 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolLocation &L) {
   if (!L)
     return OS << "(none)";
   return OS << L.FileURI << "[" << L.Start.line() << ":" << L.Start.column()
             << "-" << L.End.line() << ":" << L.End.column() << ")";
 }
 
-SymbolID::SymbolID(StringRef USR)
-    : HashValue(SHA1::hash(arrayRefFromStringRef(USR))) {}
+SymbolID::SymbolID(StringRef USR) {
+  auto Hash = SHA1::hash(arrayRefFromStringRef(USR));
+  static_assert(sizeof(Hash) >= RawSize, "RawSize larger than SHA1");
+  memcpy(HashValue.data(), Hash.data(), RawSize);
+}
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolID &ID) {
   return OS << toHex(ID.raw());
 }
 
 SymbolID SymbolID::fromRaw(StringRef Raw) {
   SymbolID ID;
   assert(Raw.size() == RawSize);

clang-tools-extra/trunk/clangd/index/Serialization.cpp

for (auto &I : Sym.IncludeHeaders) {
     I.IncludeHeader = Data.consumeString(Strings);
     I.References = Data.consumeVar();
   }
   return Sym;
 }
 
 // REFS ENCODING
 // A refs section has data grouped by Symbol. Each symbol has:
-//  - SymbolID: 20 bytes
+//  - SymbolID: 16 bytes
 //  - NumRefs: varint
 //  - Ref[NumRefs]
 // Fields of Ref are encoded in turn, see implementation.
 
 void writeRefs(const SymbolID &ID, ArrayRef<Ref> Refs,
                const StringTableOut &Strings, raw_ostream &OS) {
   OS << ID.raw();
   writeVar(Refs.size(), OS);

 //   - meta: version number
 //   - stri: string table
 //   - symb: symbols
 //   - refs: references to symbols
 
 // The current versioning scheme is simple - non-current versions are rejected.
 // If you make a breaking change, bump this version number to invalidate stored
 // data. Later we may want to support some backward compatibility.
-constexpr static uint32_t Version = 5;
+constexpr static uint32_t Version = 6;
 
 Expected<IndexFileIn> readRIFF(StringRef Data) {
   auto RIFF = riff::readFile(Data);
   if (!RIFF)
     return RIFF.takeError();
   if (RIFF->Type != riff::fourCC("CdIx"))
     return makeError("wrong RIFF type");
   StringMap<StringRef> Chunks;

clang-tools-extra/trunk/unittests/clangd/SerializationTests.cpp

 using namespace llvm;
 namespace clang {
 namespace clangd {
 namespace {
 
 const char *YAML = R"(
 ---
 !Symbol
-ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856
+ID: 057557CEBF6E6B2DD437FBF60CC58F35
 Name:   'Foo1'
 Scope:   'clang::'
 SymInfo:
   Kind:            Function
   Lang:            Cpp
 CanonicalDeclaration:
   FileURI:        file:///path/foo.h
   Start:

 IncludeHeaders:
   - Header:    'include1'
     References:    7
   - Header:    'include2'
     References:    3
 ...
 ---
 !Symbol
-ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF858
+ID: 057557CEBF6E6B2DD437FBF60CC58F36
 Name:   'Foo2'
 Scope:   'clang::'
 SymInfo:
   Kind:            Function
   Lang:            Cpp
 CanonicalDeclaration:
   FileURI:        file:///path/bar.h
   Start:
     Line: 1
     Column: 0
   End:
     Line: 1
     Column: 1
 Flags:    2
 Signature:    '-sig'
 CompletionSnippetSuffix:    '-snippet'
 ...
 !Refs
-ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856
+ID: 057557CEBF6E6B2DD437FBF60CC58F35
 References:
   - Kind: 4
     Location:
       FileURI:    file:///path/foo.cc
       Start:
         Line: 5
         Column: 3
       End:

 
 TEST(SerializationTest, YAMLConversions) {
   auto In = readIndexFile(YAML);
   EXPECT_TRUE(bool(In)) << In.takeError();
 
   auto ParsedYAML = readIndexFile(YAML);
   ASSERT_TRUE(bool(ParsedYAML)) << ParsedYAML.takeError();
   ASSERT_TRUE(bool(ParsedYAML->Symbols));
-  EXPECT_THAT(
-      *ParsedYAML->Symbols,
-      UnorderedElementsAre(ID("057557CEBF6E6B2DD437FBF60CC58F352D1DF856"),
-                           ID("057557CEBF6E6B2DD437FBF60CC58F352D1DF858")));
+  EXPECT_THAT(*ParsedYAML->Symbols,
+              UnorderedElementsAre(ID("057557CEBF6E6B2DD437FBF60CC58F35"),
+                                   ID("057557CEBF6E6B2DD437FBF60CC58F36")));
 
   auto Sym1 = *ParsedYAML->Symbols->find(
-      cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F352D1DF856")));
+      cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F35")));
   auto Sym2 = *ParsedYAML->Symbols->find(
-      cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F352D1DF858")));
+      cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F36")));
 
   EXPECT_THAT(Sym1, QName("clang::Foo1"));
   EXPECT_EQ(Sym1.Signature, "");
   EXPECT_EQ(Sym1.Documentation, "Foo doc");
   EXPECT_EQ(Sym1.ReturnType, "int");
   EXPECT_EQ(Sym1.CanonicalDeclaration.FileURI, "file:///path/foo.h");
   EXPECT_EQ(Sym1.Origin, SymbolOrigin::Static);
   EXPECT_TRUE(Sym1.Flags & Symbol::IndexedForCodeCompletion);
   EXPECT_FALSE(Sym1.Flags & Symbol::Deprecated);
   EXPECT_THAT(Sym1.IncludeHeaders,
               UnorderedElementsAre(IncludeHeaderWithRef("include1", 7u),
                                    IncludeHeaderWithRef("include2", 3u)));
 
   EXPECT_THAT(Sym2, QName("clang::Foo2"));
   EXPECT_EQ(Sym2.Signature, "-sig");
   EXPECT_EQ(Sym2.ReturnType, "");
   EXPECT_EQ(Sym2.CanonicalDeclaration.FileURI, "file:///path/bar.h");
   EXPECT_FALSE(Sym2.Flags & Symbol::IndexedForCodeCompletion);
   EXPECT_TRUE(Sym2.Flags & Symbol::Deprecated);
 
   ASSERT_TRUE(bool(ParsedYAML->Refs));
-  EXPECT_THAT(*ParsedYAML->Refs,
-              UnorderedElementsAre(
-                  Pair(cantFail(SymbolID::fromStr(
-                           "057557CEBF6E6B2DD437FBF60CC58F352D1DF856")),
-                       testing::SizeIs(1))));
+  EXPECT_THAT(
+      *ParsedYAML->Refs,
+          Pair(cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F35")),
   auto Ref1 = ParsedYAML->Refs->begin()->second.front();
   EXPECT_EQ(Ref1.Kind, RefKind::Reference);
   EXPECT_EQ(Ref1.Location.FileURI, "file:///path/foo.cc");
 }
 
 std::vector<std::string> YAMLFromSymbols(const SymbolSlab &Slab) {
   std::vector<std::string> Result;
   for (const auto &Sym : Slab)