[clangd] Serialization support for RelationSlab

[nridge]

Summary

This builds on D59407 to provide YAML and RIFF serialization support.

[kadircet]

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

29 ↗

(On Diff #201431)

no need for errors, use llvm_unreachable instead.

45 ↗

(On Diff #201431)

same for error

79 ↗

(On Diff #201431)

I believe reader should not care about the high level representation of data. therefore error state should be internal and only set if the low level read has failed.

high level reads are out of Readers scope and should be propagated by the caller.

394 ↗

(On Diff #201431)

could you also add a comment saying, we might prefer a packed representation if need arises in future?

clang-tools-extra/clangd/index/Serialization.h

81 ↗

(On Diff #201431)

why not start from zero?

Also let's change the index::SymbolRole in Relation with this one.

81 ↗

(On Diff #201431)

why not just store baseof ? do we need both directions for typehierarchy?

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

225 ↗

(On Diff #201431)

let's incorporate these data into existing yaml string at top of the file, I believe you just need to add `--- !Relations``` section

[nridge]

clang-tools-extra/clangd/index/Serialization.h

81 ↗

(On Diff #201431)

Also let's change the index::SymbolRole in Relation with this one.

You previously asked for the opposite change in this comment :)

Did your opinion change?

[nridge]

Addressed most review comments

clang-tools-extra/clangd/index/Serialization.h

81 ↗

(On Diff #201431)

why not start from zero?

The original motivation was so that we had a distinct value to return in case of an error. However, now that we use llvm_unreachable that doesn't seem to be necessary any more.

81 ↗

(On Diff #201431)

why not just store baseof ? do we need both directions for typehierarchy?

In the future, we may want to be able to look up supertypes in the index as well (for example, to handle scenarios where a type that is only forward-declared in the current TU is queried).

However, we can add that later, and just focus on subtypes for now, which only require BaseOf.

[kadircet]

LG, thanks for the patch!

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

34 ↗

(On Diff #202370)

nit: no need for braces

44 ↗

(On Diff #202370)

nit: braces

clang-tools-extra/clangd/index/Serialization.h

81 ↗

(On Diff #201431)

ahaha good catch :D for some reason I thought we were also storing our own struct in Symbol for SmybolInfo but apparently we are not. Just ignore that one.

clang-tools-extra/trunk/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;
+  llvm::Optional<RelationSlab> Relations;
   // Keys are URIs of the source files.
   llvm::Optional<IncludeGraph> Sources;
 };
 // 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;
+  const RelationSlab *Relations = nullptr;
   // Keys are URIs of the source files.
   const IncludeGraph *Sources = 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) {}
+        Refs(I.Refs ? I.Refs.getPointer() : nullptr),
+        Relations(I.Relations ? I.Relations.getPointer() : nullptr) {}
 };
 // Serializes an index file.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const IndexFileOut &O);
 
 // Convert a single symbol to YAML, a nice debug representation.
 std::string toYAML(const Symbol &);
 std::string toYAML(const std::pair<SymbolID, ArrayRef<Ref>> &);
+std::string toYAML(const Relation &);
 
 // Build an in-memory static index from an index file.
 // The size should be relatively small, so data can be managed in memory.
 std::unique_ptr<SymbolIndex> loadIndex(llvm::StringRef Filename,
                                        bool UseDex = true);
 
+// Used for serializing SymbolRole as used in Relation.
+enum class RelationKind : uint8_t { BaseOf };
+RelationKind symbolRoleToRelationKind(index::SymbolRole);
+index::SymbolRole relationKindToSymbolRole(RelationKind);
+
 } // namespace clangd
 } // namespace clang
 
 #endif

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

 
 namespace clang {
 namespace clangd {
 namespace {
 llvm::Error makeError(const llvm::Twine &Msg) {
   return llvm::make_error<llvm::StringError>(Msg,
                                              llvm::inconvertibleErrorCode());
 }
+} // namespace
+
+RelationKind symbolRoleToRelationKind(index::SymbolRole Role) {
+  // SymbolRole is used to record relations in the index.
+  // Only handle the relations we actually store currently.
+  // If we start storing more relations, this list can be expanded.
+  switch (Role) {
+  case index::SymbolRole::RelationBaseOf:
+    return RelationKind::BaseOf;
+  default:
+    llvm_unreachable("Unsupported symbol role");
+  }
+}
+
+index::SymbolRole relationKindToSymbolRole(RelationKind Kind) {
+  switch (Kind) {
+  case RelationKind::BaseOf:
+    return index::SymbolRole::RelationBaseOf;
+  }
+  llvm_unreachable("Invalid relation kind");
+}
+
+namespace {
 
 // IO PRIMITIVES
 // We use little-endian 32 bit ints, sometimes with variable-length encoding.
 //
 // Variable-length int encoding (varint) uses the bottom 7 bits of each byte
 // to encode the number, and the top bit to indicate whether more bytes follow.
 // e.g. 9a 2f means [0x1a and keep reading, 0x2f and stop].
 // This represents 0x1a | 0x2f<<7 = 6042.
readRefs(Reader &Data, llvm::ArrayRef<llvm::StringRef> Strings) {
   Result.second.resize(Data.consumeVar());
   for (auto &Ref : Result.second) {
     Ref.Kind = static_cast<RefKind>(Data.consume8());
     Ref.Location = readLocation(Data, Strings);
   }
   return Result;
 }
 
+// RELATIONS ENCODING
+// A relations section is a flat list of relations. Each relation has:
+//  - SymbolID (subject): 8 bytes
+//  - relation kind (predicate): 1 byte
+//  - SymbolID (object): 8 bytes
+// In the future, we might prefer a packed representation if the need arises.
+
+void writeRelation(const Relation &R, llvm::raw_ostream &OS) {
+  OS << R.Subject.raw();
+  RelationKind Kind = symbolRoleToRelationKind(R.Predicate);
+  OS.write(static_cast<uint8_t>(Kind));
+  OS << R.Object.raw();
+}
+
+Relation readRelation(Reader &Data) {
+  SymbolID Subject = Data.consumeID();
+  index::SymbolRole Predicate =
+      relationKindToSymbolRole(static_cast<RelationKind>(Data.consume8()));
+  SymbolID Object = Data.consumeID();
+  return {Subject, Predicate, Object};
+}
+
 // FILE ENCODING
 // A file is a RIFF chunk with type 'CdIx'.
 // It contains the sections:
 //   - meta: version number
 //   - srcs: information related to include graph
 //   - stri: string table
 //   - symb: symbols
 //   - refs: references to symbols
while (!RefsReader.eof()) {
       auto RefsBundle = readRefs(RefsReader, Strings->Strings);
       for (const auto &Ref : RefsBundle.second) // FIXME: bulk insert?
         Refs.insert(RefsBundle.first, Ref);
     }
     if (RefsReader.err())
       return makeError("malformed or truncated refs");
     Result.Refs = std::move(Refs).build();
   }
+  if (Chunks.count("rela")) {
+    Reader RelationsReader(Chunks.lookup("rela"));
+    RelationSlab::Builder Relations;
+    while (!RelationsReader.eof()) {
+      auto Relation = readRelation(RelationsReader);
+      Relations.insert(Relation);
+    }
+    if (RelationsReader.err())
+      return makeError("malformed or truncated relations");
+    Result.Relations = std::move(Relations).build();
+  }
   return std::move(Result);
 }
 
 template <class Callback>
 void visitStrings(IncludeGraphNode &IGN, const Callback &CB) {
   CB(IGN.URI);
   for (llvm::StringRef &Include : IGN.DirectIncludes)
     CB(Include);
for (const auto &Sym : *Data.Refs) {
       for (auto &Ref : Refs.back().second) {
         llvm::StringRef File = Ref.Location.FileURI;
         Strings.intern(File);
         Ref.Location.FileURI = File.data();
       }
     }
   }
 
+  std::vector<Relation> Relations;
+  if (Data.Relations) {
+    for (const auto &Relation : *Data.Relations) {
+      Relations.emplace_back(Relation);
+      // No strings to be interned in relations.
+    }
+  }
+
   std::string StringSection;
   {
     llvm::raw_string_ostream StringOS(StringSection);
     Strings.finalize(StringOS);
   }
   RIFF.Chunks.push_back({riff::fourCC("stri"), StringSection});
 
   std::string SymbolSection;
if (Data.Refs) {
     {
       llvm::raw_string_ostream RefsOS(RefsSection);
       for (const auto &Sym : Refs)
         writeRefs(Sym.first, Sym.second, Strings, RefsOS);
     }
     RIFF.Chunks.push_back({riff::fourCC("refs"), RefsSection});
   }
 
+  std::string RelationSection;
+  if (Data.Relations) {
+    {
+      llvm::raw_string_ostream RelationOS{RelationSection};
+      for (const auto &Relation : Relations)
+        writeRelation(Relation, RelationOS);
+    }
+    RIFF.Chunks.push_back({riff::fourCC("rela"), RelationSection});
+  }
+
   std::string SrcsSection;
   {
     {
       llvm::raw_string_ostream SrcsOS(SrcsSection);
       for (const auto &SF : Sources)
         writeIncludeGraphNode(SF, Strings, SrcsOS);
     }
     RIFF.Chunks.push_back({riff::fourCC("srcs"), SrcsSection});
std::unique_ptr<SymbolIndex> loadIndex(llvm::StringRef SymbolFilename,
   auto Buffer = llvm::MemoryBuffer::getFile(SymbolFilename);
   if (!Buffer) {
     llvm::errs() << "Can't open " << SymbolFilename << "\n";
     return nullptr;
   }
 
   SymbolSlab Symbols;
   RefSlab Refs;
+  RelationSlab Relations;
   {
     trace::Span Tracer("ParseIndex");
     if (auto I = readIndexFile(Buffer->get()->getBuffer())) {
       if (I->Symbols)
         Symbols = std::move(*I->Symbols);
       if (I->Refs)
         Refs = std::move(*I->Refs);
+      if (I->Relations)
+        Relations = std::move(*I->Relations);
     } else {
       llvm::errs() << "Bad Index: " << llvm::toString(I.takeError()) << "\n";
       return nullptr;
     }
   }
 
   size_t NumSym = Symbols.size();
   size_t NumRefs = Refs.numRefs();
+  size_t NumRelations = Relations.size();
 
   trace::Span Tracer("BuildIndex");
   auto Index = UseDex ? dex::Dex::build(std::move(Symbols), std::move(Refs))
                       : MemIndex::build(std::move(Symbols), std::move(Refs));
   vlog("Loaded {0} from {1} with estimated memory usage {2} bytes\n"
        "  - number of symbols: {3}\n"
-       "  - number of refs: {4}\n",
+       "  - number of refs: {4}\n"
+       "  - numnber of relations: {5}",
        UseDex ? "Dex" : "MemIndex", SymbolFilename,
-       Index->estimateMemoryUsage(), NumSym, NumRefs);
+       Index->estimateMemoryUsage(), NumSym, NumRefs, NumRelations);
   return Index;
 }
 
 } // namespace clangd
 } // namespace clang

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

 //===-- YAMLSerialization.cpp ------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // A YAML index file is a sequence of tagged entries.
 // Each entry either encodes a Symbol or the list of references to a symbol
 // (a "ref bundle").
 //
 //===----------------------------------------------------------------------===//
 
 #include "Index.h"
+#include "Relation.h"
 #include "Serialization.h"
 #include "SymbolLocation.h"
 #include "SymbolOrigin.h"
 #include "Trace.h"
 #include "dex/Dex.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/YAMLTraits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdint>
 
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Symbol::IncludeHeaderWithReferences)
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Ref)
 
 namespace {
 using RefBundle =
     std::pair<clang::clangd::SymbolID, std::vector<clang::clangd::Ref>>;
-// This is a pale imitation of std::variant<Symbol, RefBundle>
+// This is a pale imitation of std::variant<Symbol, RefBundle, Relation>
 struct VariantEntry {
   llvm::Optional<clang::clangd::Symbol> Symbol;
   llvm::Optional<RefBundle> Refs;
+  llvm::Optional<clang::clangd::Relation> Relation;
 };
 // A class helps YAML to serialize the 32-bit encoded position (Line&Column),
 // as YAMLIO can't directly map bitfields.
 struct YPosition {
   uint32_t Line;
   uint32_t Column;
 };
 
 } // namespace
 namespace llvm {
 namespace yaml {
 
 using clang::clangd::Ref;
 using clang::clangd::RefKind;
+using clang::clangd::Relation;
+using clang::clangd::RelationKind;
 using clang::clangd::Symbol;
 using clang::clangd::SymbolID;
 using clang::clangd::SymbolLocation;
 using clang::clangd::SymbolOrigin;
 using clang::index::SymbolInfo;
 using clang::index::SymbolKind;
 using clang::index::SymbolLanguage;
+using clang::index::SymbolRole;
 
 // Helper to (de)serialize the SymbolID. We serialize it as a hex string.
 struct NormalizedSymbolID {
   NormalizedSymbolID(IO &) {}
   NormalizedSymbolID(IO &, const SymbolID &ID) {
     llvm::raw_string_ostream OS(HexString);
     OS << ID;
   }

 template <> struct MappingTraits<Ref> {
   static void mapping(IO &IO, Ref &R) {
     MappingNormalization<NormalizedRefKind, RefKind> NKind(IO, R.Kind);
     IO.mapRequired("Kind", NKind->Kind);
     IO.mapRequired("Location", R.Location);
   }
 };
 
+struct NormalizedSymbolRole {
+  NormalizedSymbolRole(IO &) {}
+  NormalizedSymbolRole(IO &IO, SymbolRole R) {
+    Kind = static_cast<uint8_t>(clang::clangd::symbolRoleToRelationKind(R));
+  }
+
+  SymbolRole denormalize(IO &IO) {
+    return clang::clangd::relationKindToSymbolRole(
+        static_cast<RelationKind>(Kind));
+  }
+
+  uint8_t Kind = 0;
+};
+
+template <> struct MappingTraits<SymbolID> {
+  static void mapping(IO &IO, SymbolID &ID) {
+    MappingNormalization<NormalizedSymbolID, SymbolID> NSymbolID(IO, ID);
+    IO.mapRequired("ID", NSymbolID->HexString);
+  }
+};
+
+template <> struct MappingTraits<Relation> {
+  static void mapping(IO &IO, Relation &Relation) {
+    MappingNormalization<NormalizedSymbolRole, SymbolRole> NRole(
+        IO, Relation.Predicate);
+    IO.mapRequired("Subject", Relation.Subject);
+    IO.mapRequired("Predicate", NRole->Kind);
+    IO.mapRequired("Object", Relation.Object);
+  }
+};
+
 template <> struct MappingTraits<VariantEntry> {
   static void mapping(IO &IO, VariantEntry &Variant) {
     if (IO.mapTag("!Symbol", Variant.Symbol.hasValue())) {
       if (!IO.outputting())
         Variant.Symbol.emplace();
       MappingTraits<Symbol>::mapping(IO, *Variant.Symbol);
     } else if (IO.mapTag("!Refs", Variant.Refs.hasValue())) {
       if (!IO.outputting())
         Variant.Refs.emplace();
       MappingTraits<RefBundle>::mapping(IO, *Variant.Refs);
+    } else if (IO.mapTag("!Relations", Variant.Relation.hasValue())) {
+      if (!IO.outputting())
+        Variant.Relation.emplace();
+      MappingTraits<Relation>::mapping(IO, *Variant.Relation);
     }
   }
 };
 
 } // namespace yaml
 } // namespace llvm
 
 namespace clang {
 namespace clangd {
 
 void writeYAML(const IndexFileOut &O, llvm::raw_ostream &OS) {
   llvm::yaml::Output Yout(OS);
   for (const auto &Sym : *O.Symbols) {
     VariantEntry Entry;
     Entry.Symbol = Sym;
     Yout << Entry;
   }
   if (O.Refs)
     for (auto &Sym : *O.Refs) {
       VariantEntry Entry;
       Entry.Refs = Sym;
       Yout << Entry;
     }
+  if (O.Relations)
+    for (auto &R : *O.Relations) {
+      VariantEntry Entry;
+      Entry.Relation = R;
+      Yout << Entry;
+    }
 }
 
 llvm::Expected<IndexFileIn> readYAML(llvm::StringRef Data) {
   SymbolSlab::Builder Symbols;
   RefSlab::Builder Refs;
+  RelationSlab::Builder Relations;
   llvm::BumpPtrAllocator
       Arena; // store the underlying data of Position::FileURI.
   llvm::UniqueStringSaver Strings(Arena);
   llvm::yaml::Input Yin(Data, &Strings);
   while (Yin.setCurrentDocument()) {
     llvm::yaml::EmptyContext Ctx;
     VariantEntry Variant;
     yamlize(Yin, Variant, true, Ctx);
     if (Yin.error())
       return llvm::errorCodeToError(Yin.error());
 
     if (Variant.Symbol)
       Symbols.insert(*Variant.Symbol);
     if (Variant.Refs)
       for (const auto &Ref : Variant.Refs->second)
         Refs.insert(Variant.Refs->first, Ref);
+    if (Variant.Relation)
+      Relations.insert(*Variant.Relation);
     Yin.nextDocument();
   }
 
   IndexFileIn Result;
   Result.Symbols.emplace(std::move(Symbols).build());
   Result.Refs.emplace(std::move(Refs).build());
+  Result.Relations.emplace(std::move(Relations).build());
   return std::move(Result);
 }
 
 std::string toYAML(const Symbol &S) {
   std::string Buf;
   {
     llvm::raw_string_ostream OS(Buf);
     llvm::yaml::Output Yout(OS);
std::string toYAML(const std::pair<SymbolID, llvm::ArrayRef<Ref>> &Data) {
   {
     llvm::raw_string_ostream OS(Buf);
     llvm::yaml::Output Yout(OS);
     Yout << Refs;
   }
   return Buf;
 }
 
+std::string toYAML(const Relation &R) {
+  std::string Buf;
+  {
+    llvm::raw_string_ostream OS(Buf);
+    llvm::yaml::Output Yout(OS);
+    Relation Rel = R; // copy: Yout<< requires mutability.
+    Yout << Rel;
+  }
+  return Buf;
+}
+
 } // namespace clangd
 } // namespace clang

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

- Kind: 4
     Location:
       FileURI:    file:///path/foo.cc
       Start:
         Line: 5
         Column: 3
       End:
         Line: 5
         Column: 8
+...
+--- !Relations
+Subject:
+  ID:              6481EE7AF2841756
+Predicate:       0
+Object:
+  ID:              6512AEC512EA3A2D
+...
 )";
 
 MATCHER_P(ID, I, "") { return arg.ID == cantFail(SymbolID::fromStr(I)); }
 MATCHER_P(QName, Name, "") { return (arg.Scope + arg.Name).str() == Name; }
 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References, "") {
   return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
 }
 
TEST(SerializationTest, YAMLConversions) {
   ASSERT_TRUE(bool(ParsedYAML->Refs));
   EXPECT_THAT(
       *ParsedYAML->Refs,
       UnorderedElementsAre(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");
+
+  SymbolID Base = cantFail(SymbolID::fromStr("6481EE7AF2841756"));
+  SymbolID Derived = cantFail(SymbolID::fromStr("6512AEC512EA3A2D"));
+  ASSERT_TRUE(bool(ParsedYAML->Relations));
+  EXPECT_THAT(*ParsedYAML->Relations,
+              UnorderedElementsAre(
+                  Relation{Base, index::SymbolRole::RelationBaseOf, Derived}));
 }
 
 std::vector<std::string> YAMLFromSymbols(const SymbolSlab &Slab) {
   std::vector<std::string> Result;
   for (const auto &Sym : Slab)
     Result.push_back(toYAML(Sym));
   return Result;
 }
 std::vector<std::string> YAMLFromRefs(const RefSlab &Slab) {
   std::vector<std::string> Result;
-  for (const auto &Sym : Slab)
-    Result.push_back(toYAML(Sym));
+  for (const auto &Refs : Slab)
+    Result.push_back(toYAML(Refs));
+  return Result;
+}
+
+std::vector<std::string> YAMLFromRelations(const RelationSlab &Slab) {
+  std::vector<std::string> Result;
+  for (const auto &Rel : Slab)
+    Result.push_back(toYAML(Rel));
   return Result;
 }
 
 TEST(SerializationTest, BinaryConversions) {
   auto In = readIndexFile(YAML);
   EXPECT_TRUE(bool(In)) << In.takeError();
 
   // Write to binary format, and parse again.
   IndexFileOut Out(*In);
   Out.Format = IndexFileFormat::RIFF;
   std::string Serialized = llvm::to_string(Out);
 
   auto In2 = readIndexFile(Serialized);
   ASSERT_TRUE(bool(In2)) << In.takeError();
   ASSERT_TRUE(In2->Symbols);
   ASSERT_TRUE(In2->Refs);
+  ASSERT_TRUE(In2->Relations);
 
   // 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)));
+  EXPECT_THAT(YAMLFromRelations(*In2->Relations),
+              UnorderedElementsAreArray(YAMLFromRelations(*In->Relations)));
 }
 
 TEST(SerializationTest, SrcsTest) {
   auto In = readIndexFile(YAML);
   EXPECT_TRUE(bool(In)) << In.takeError();
 
   std::string TestContent("TestContent");
   IncludeGraphNode IGN;