[clangd] Truncate SymbolID to 8 bytes.

[hokein]

Summary

This is our goal. It has a non-zero rick, but so far we haven't see any
collision (externally and internally).

clangd/index/Index.h

bool operator==(const SymbolID &Sym) const {
     return HashValue == Sym.HashValue;
   }
   bool operator<(const SymbolID &Sym) const {
     return HashValue < Sym.HashValue;
   }
 
   // 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;
+  constexpr static size_t RawSize = 8;
   llvm::StringRef raw() const {
     return StringRef(reinterpret_cast<const char *>(HashValue.data()), RawSize);
   }
   static SymbolID fromRaw(llvm::StringRef);
 
   // Returns a hex encoded string.
   std::string str() const;
   static llvm::Expected<SymbolID> fromStr(llvm::StringRef);

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: 16 bytes
+//  - SymbolID: 8 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 = 6;
+constexpr static uint32_t Version = 7;
 
 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;

unittests/clangd/SerializationTests.cpp

 using namespace llvm;
 namespace clang {
 namespace clangd {
 namespace {
 
 const char *YAML = R"(
 ---
 !Symbol
-ID: 057557CEBF6E6B2DD437FBF60CC58F35
+ID: 057557CEBF6E6B2D
 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: 057557CEBF6E6B2DD437FBF60CC58F36
+ID: 057557CEBF6E6B2E
 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: 057557CEBF6E6B2DD437FBF60CC58F35
+ID: 057557CEBF6E6B2D
 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("057557CEBF6E6B2DD437FBF60CC58F35"),
-                                   ID("057557CEBF6E6B2DD437FBF60CC58F36")));
+              UnorderedElementsAre(ID("057557CEBF6E6B2D"),
+                                   ID("057557CEBF6E6B2E")));
 
   auto Sym1 = *ParsedYAML->Symbols->find(
-      cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F35")));
+      cantFail(SymbolID::fromStr("057557CEBF6E6B2D")));
   auto Sym2 = *ParsedYAML->Symbols->find(
-      cantFail(SymbolID::fromStr("057557CEBF6E6B2DD437FBF60CC58F36")));
+      cantFail(SymbolID::fromStr("057557CEBF6E6B2E")));
 
   EXPECT_THAT(Sym1, QName("clang::Foo1"));
   EXPECT_EQ(Sym1.Signature, "");
   EXPECT_EQ(Sym1.Documentation, "Foo doc");
   EXPECT_EQ(Sym1.ReturnType, "int");
   EXPECT_EQ(StringRef(Sym1.CanonicalDeclaration.FileURI), "file:///path/foo.h");
   EXPECT_EQ(Sym1.Origin, SymbolOrigin::Static);
   EXPECT_TRUE(Sym1.Flags & Symbol::IndexedForCodeCompletion);
EXPECT_EQ(llvm::StringRef(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("057557CEBF6E6B2DD437FBF60CC58F35")),
+          Pair(cantFail(SymbolID::fromStr("057557CEBF6E6B2D")),
                testing::SizeIs(1))));
   auto Ref1 = ParsedYAML->Refs->begin()->second.front();
   EXPECT_EQ(Ref1.Kind, RefKind::Reference);
   EXPECT_EQ(StringRef(Ref1.Location.FileURI), "file:///path/foo.cc");
 }
 
 std::vector<std::string> YAMLFromSymbols(const SymbolSlab &Slab) {
   std::vector<std::string> Result;