| 1 |
//===-- Serialization.cpp - Binary serialization of index data ------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "Serialization.h" |
| 10 |
#include "Headers.h" |
| 11 |
#include "RIFF.h" |
| 12 |
#include "index/MemIndex.h" |
| 13 |
#include "index/SymbolLocation.h" |
| 14 |
#include "index/SymbolOrigin.h" |
| 15 |
#include "index/dex/Dex.h" |
| 16 |
#include "support/Logger.h" |
| 17 |
#include "support/Trace.h" |
| 18 |
#include "clang/Tooling/CompilationDatabase.h" |
| 19 |
#include "llvm/ADT/StringRef.h" |
| 20 |
#include "llvm/Support/Compiler.h" |
| 21 |
#include "llvm/Support/Compression.h" |
| 22 |
#include "llvm/Support/Endian.h" |
| 23 |
#include "llvm/Support/Error.h" |
| 24 |
#include "llvm/Support/raw_ostream.h" |
| 25 |
#include <cstdint> |
| 26 |
#include <vector> |
| 27 |
|
| 28 |
namespace clang { |
| 29 |
namespace clangd { |
| 30 |
namespace { |
| 31 |
|
| 32 |
// IO PRIMITIVES |
| 33 |
// We use little-endian 32 bit ints, sometimes with variable-length encoding. |
| 34 |
// |
| 35 |
// Variable-length int encoding (varint) uses the bottom 7 bits of each byte |
| 36 |
// to encode the number, and the top bit to indicate whether more bytes follow. |
| 37 |
// e.g. 9a 2f means [0x1a and keep reading, 0x2f and stop]. |
| 38 |
// This represents 0x1a | 0x2f<<7 = 6042. |
| 39 |
// A 32-bit integer takes 1-5 bytes to encode; small numbers are more compact. |
| 40 |
|
| 41 |
// Reads binary data from a StringRef, and keeps track of position. |
| 42 |
class Reader { |
| 43 |
const char *Begin, *End; |
| 44 |
bool Err = false; |
| 45 |
|
| 46 |
public: |
| 47 |
Reader(llvm::StringRef Data) : Begin(Data.begin()), End(Data.end()) {} |
| 48 |
// The "error" bit is set by reading past EOF or reading invalid data. |
| 49 |
// When in an error state, reads may return zero values: callers should check. |
| 50 |
bool err() const { return Err; } |
| 51 |
// Did we read all the data, or encounter an error? |
| 52 |
bool eof() const { return Begin == End || Err; } |
| 53 |
// All the data we didn't read yet. |
| 54 |
llvm::StringRef rest() const { return llvm::StringRef(Begin, End - Begin); } |
| 55 |
|
| 56 |
uint8_t consume8() { |
| 57 |
if (LLVM_UNLIKELY(Begin == End)) { |
| 58 |
Err = true; |
| 59 |
return 0; |
| 60 |
} |
| 61 |
return *Begin++; |
| 62 |
} |
| 63 |
|
| 64 |
uint32_t consume32() { |
| 65 |
if (LLVM_UNLIKELY(Begin + 4 > End)) { |
| 66 |
Err = true; |
| 67 |
return 0; |
| 68 |
} |
| 69 |
auto Ret = llvm::support::endian::read32le(Begin); |
| 70 |
Begin += 4; |
| 71 |
return Ret; |
| 72 |
} |
| 73 |
|
| 74 |
llvm::StringRef consume(int N) { |
| 75 |
if (LLVM_UNLIKELY(Begin + N > End)) { |
| 76 |
Err = true; |
| 77 |
return llvm::StringRef(); |
| 78 |
} |
| 79 |
llvm::StringRef Ret(Begin, N); |
| 80 |
Begin += N; |
| 81 |
return Ret; |
| 82 |
} |
| 83 |
|
| 84 |
uint32_t consumeVar() { |
| 85 |
constexpr static uint8_t More = 1 << 7; |
| 86 |
|
| 87 |
// Use a 32 bit unsigned here to prevent promotion to signed int (unless int |
| 88 |
// is wider than 32 bits). |
| 89 |
uint32_t B = consume8(); |
| 90 |
if (LLVM_LIKELY(!(B & More))) |
| 91 |
return B; |
| 92 |
uint32_t Val = B & ~More; |
| 93 |
for (int Shift = 7; B & More && Shift < 32; Shift += 7) { |
| 94 |
B = consume8(); |
| 95 |
// 5th byte of a varint can only have lowest 4 bits set. |
| 96 |
assert((Shift != 28 || B == (B & 0x0f)) && "Invalid varint encoding"); |
| 97 |
Val |= (B & ~More) << Shift; |
| 98 |
} |
| 99 |
return Val; |
| 100 |
} |
| 101 |
|
| 102 |
llvm::StringRef consumeString(llvm::ArrayRef<llvm::StringRef> Strings) { |
| 103 |
auto StringIndex = consumeVar(); |
| 104 |
if (LLVM_UNLIKELY(StringIndex >= Strings.size())) { |
| 105 |
Err = true; |
| 106 |
return llvm::StringRef(); |
| 107 |
} |
| 108 |
return Strings[StringIndex]; |
| 109 |
} |
| 110 |
|
| 111 |
SymbolID consumeID() { |
| 112 |
llvm::StringRef Raw = consume(SymbolID::RawSize); // short if truncated. |
| 113 |
return LLVM_UNLIKELY(err()) ? SymbolID() : SymbolID::fromRaw(Raw); |
| 114 |
} |
| 115 |
|
| 116 |
// Read a varint (as consumeVar) and resize the container accordingly. |
| 117 |
// If the size is invalid, return false and mark an error. |
| 118 |
// (The caller should abort in this case). |
| 119 |
template <typename T> [[nodiscard]] bool consumeSize(T &Container) { |
| 120 |
auto Size = consumeVar(); |
| 121 |
// Conservatively assume each element is at least one byte. |
| 122 |
if (Size > (size_t)(End - Begin)) { |
| 123 |
Err = true; |
| 124 |
return false; |
| 125 |
} |
| 126 |
Container.resize(Size); |
| 127 |
return true; |
| 128 |
} |
| 129 |
}; |
| 130 |
|
| 131 |
void write32(uint32_t I, llvm::raw_ostream &OS) { |
| 132 |
char Buf[4]; |
| 133 |
llvm::support::endian::write32le(Buf, I); |
| 134 |
OS.write(Buf, sizeof(Buf)); |
| 135 |
} |
| 136 |
|
| 137 |
void writeVar(uint32_t I, llvm::raw_ostream &OS) { |
| 138 |
constexpr static uint8_t More = 1 << 7; |
| 139 |
if (LLVM_LIKELY(I < 1 << 7)) { |
| 140 |
OS.write(I); |
| 141 |
return; |
| 142 |
} |
| 143 |
for (;;) { |
| 144 |
OS.write(I | More); |
| 145 |
I >>= 7; |
| 146 |
if (I < 1 << 7) { |
| 147 |
OS.write(I); |
| 148 |
return; |
| 149 |
} |
| 150 |
} |
| 151 |
} |
| 152 |
|
| 153 |
// STRING TABLE ENCODING |
| 154 |
// Index data has many string fields, and many strings are identical. |
| 155 |
// We store each string once, and refer to them by index. |
| 156 |
// |
| 157 |
// The string table's format is: |
| 158 |
// - UncompressedSize : uint32 (or 0 for no compression) |
| 159 |
// - CompressedData : byte[CompressedSize] |
| 160 |
// |
| 161 |
// CompressedData is a zlib-compressed byte[UncompressedSize]. |
| 162 |
// It contains a sequence of null-terminated strings, e.g. "foo\0bar\0". |
| 163 |
// These are sorted to improve compression. |
| 164 |
|
| 165 |
// Maps each string to a canonical representation. |
| 166 |
// Strings remain owned externally (e.g. by SymbolSlab). |
| 167 |
class StringTableOut { |
| 168 |
llvm::DenseSet<llvm::StringRef> Unique; |
| 169 |
std::vector<llvm::StringRef> Sorted; |
| 170 |
// Since strings are interned, look up can be by pointer. |
| 171 |
llvm::DenseMap<std::pair<const char *, size_t>, unsigned> Index; |
| 172 |
|
| 173 |
public: |
| 174 |
StringTableOut() { |
| 175 |
// Ensure there's at least one string in the table. |
| 176 |
// Table size zero is reserved to indicate no compression. |
| 177 |
Unique.insert(""); |
| 178 |
} |
| 179 |
// Add a string to the table. Overwrites S if an identical string exists. |
| 180 |
void intern(llvm::StringRef &S) { S = *Unique.insert(S).first; }; |
| 181 |
// Finalize the table and write it to OS. No more strings may be added. |
| 182 |
void finalize(llvm::raw_ostream &OS) { |
| 183 |
Sorted = {Unique.begin(), Unique.end()}; |
| 184 |
llvm::sort(Sorted); |
| 185 |
for (unsigned I = 0; I < Sorted.size(); ++I) |
| 186 |
Index.try_emplace({Sorted[I].data(), Sorted[I].size()}, I); |
| 187 |
|
| 188 |
std::string RawTable; |
| 189 |
for (llvm::StringRef S : Sorted) { |
| 190 |
RawTable.append(std::string(S)); |
| 191 |
RawTable.push_back(0); |
| 192 |
} |
| 193 |
if (llvm::compression::zlib::isAvailable()) { |
| 194 |
llvm::SmallVector<uint8_t, 0> Compressed; |
| 195 |
llvm::compression::zlib::compress(llvm::arrayRefFromStringRef(RawTable), |
| 196 |
Compressed); |
| 197 |
write32(RawTable.size(), OS); |
| 198 |
OS << llvm::toStringRef(Compressed); |
| 199 |
} else { |
| 200 |
write32(0, OS); // No compression. |
| 201 |
OS << RawTable; |
| 202 |
} |
| 203 |
} |
| 204 |
// Get the ID of an string, which must be interned. Table must be finalized. |
| 205 |
unsigned index(llvm::StringRef S) const { |
| 206 |
assert(!Sorted.empty() && "table not finalized"); |
| 207 |
assert(Index.count({S.data(), S.size()}) && "string not interned"); |
| 208 |
return Index.find({S.data(), S.size()})->second; |
| 209 |
} |
| 210 |
}; |
| 211 |
|
| 212 |
struct StringTableIn { |
| 213 |
llvm::BumpPtrAllocator Arena; |
| 214 |
std::vector<llvm::StringRef> Strings; |
| 215 |
}; |
| 216 |
|
| 217 |
llvm::Expected<StringTableIn> readStringTable(llvm::StringRef Data) { |
| 218 |
Reader R(Data); |
| 219 |
size_t UncompressedSize = R.consume32(); |
| 220 |
if (R.err()) |
| 221 |
return error("Truncated string table"); |
| 222 |
|
| 223 |
llvm::StringRef Uncompressed; |
| 224 |
llvm::SmallVector<uint8_t, 0> UncompressedStorage; |
| 225 |
if (UncompressedSize == 0) // No compression |
| 226 |
Uncompressed = R.rest(); |
| 227 |
else if (llvm::compression::zlib::isAvailable()) { |
| 228 |
// Don't allocate a massive buffer if UncompressedSize was corrupted |
| 229 |
// This is effective for sharded index, but not big monolithic ones, as |
| 230 |
// once compressed size reaches 4MB nothing can be ruled out. |
| 231 |
// Theoretical max ratio from https://zlib.net/zlib_tech.html |
| 232 |
constexpr int MaxCompressionRatio = 1032; |
| 233 |
if (UncompressedSize / MaxCompressionRatio > R.rest().size()) |
| 234 |
return error("Bad stri table: uncompress {0} -> {1} bytes is implausible", |
| 235 |
R.rest().size(), UncompressedSize); |
| 236 |
|
| 237 |
if (llvm::Error E = llvm::compression::zlib::decompress( |
| 238 |
llvm::arrayRefFromStringRef(R.rest()), UncompressedStorage, |
| 239 |
UncompressedSize)) |
| 240 |
return std::move(E); |
| 241 |
Uncompressed = toStringRef(UncompressedStorage); |
| 242 |
} else |
| 243 |
return error("Compressed string table, but zlib is unavailable"); |
| 244 |
|
| 245 |
StringTableIn Table; |
| 246 |
llvm::StringSaver Saver(Table.Arena); |
| 247 |
R = Reader(Uncompressed); |
| 248 |
for (Reader R(Uncompressed); !R.eof();) { |
| 249 |
auto Len = R.rest().find(0); |
| 250 |
if (Len == llvm::StringRef::npos) |
| 251 |
return error("Bad string table: not null terminated"); |
| 252 |
Table.Strings.push_back(Saver.save(R.consume(Len))); |
| 253 |
R.consume8(); |
| 254 |
} |
| 255 |
if (R.err()) |
| 256 |
return error("Truncated string table"); |
| 257 |
return std::move(Table); |
| 258 |
} |
| 259 |
|
| 260 |
// SYMBOL ENCODING |
| 261 |
// Each field of clangd::Symbol is encoded in turn (see implementation). |
| 262 |
// - StringRef fields encode as varint (index into the string table) |
| 263 |
// - enums encode as the underlying type |
| 264 |
// - most numbers encode as varint |
| 265 |
|
| 266 |
void writeLocation(const SymbolLocation &Loc, const StringTableOut &Strings, |
| 267 |
llvm::raw_ostream &OS) { |
| 268 |
writeVar(Strings.index(Loc.FileURI), OS); |
| 269 |
for (const auto &Endpoint : {Loc.Start, Loc.End}) { |
| 270 |
writeVar(Endpoint.line(), OS); |
| 271 |
writeVar(Endpoint.column(), OS); |
| 272 |
} |
| 273 |
} |
| 274 |
|
| 275 |
SymbolLocation readLocation(Reader &Data, |
| 276 |
llvm::ArrayRef<llvm::StringRef> Strings) { |
| 277 |
SymbolLocation Loc; |
| 278 |
Loc.FileURI = Data.consumeString(Strings).data(); |
| 279 |
for (auto *Endpoint : {&Loc.Start, &Loc.End}) { |
| 280 |
Endpoint->setLine(Data.consumeVar()); |
| 281 |
Endpoint->setColumn(Data.consumeVar()); |
| 282 |
} |
| 283 |
return Loc; |
| 284 |
} |
| 285 |
|
| 286 |
IncludeGraphNode readIncludeGraphNode(Reader &Data, |
| 287 |
llvm::ArrayRef<llvm::StringRef> Strings) { |
| 288 |
IncludeGraphNode IGN; |
| 289 |
IGN.Flags = static_cast<IncludeGraphNode::SourceFlag>(Data.consume8()); |
| 290 |
IGN.URI = Data.consumeString(Strings); |
| 291 |
llvm::StringRef Digest = Data.consume(IGN.Digest.size()); |
| 292 |
std::copy(Digest.bytes_begin(), Digest.bytes_end(), IGN.Digest.begin()); |
| 293 |
if (!Data.consumeSize(IGN.DirectIncludes)) |
| 294 |
return IGN; |
| 295 |
for (llvm::StringRef &Include : IGN.DirectIncludes) |
| 296 |
Include = Data.consumeString(Strings); |
| 297 |
return IGN; |
| 298 |
} |
| 299 |
|
| 300 |
void writeIncludeGraphNode(const IncludeGraphNode &IGN, |
| 301 |
const StringTableOut &Strings, |
| 302 |
llvm::raw_ostream &OS) { |
| 303 |
OS.write(static_cast<uint8_t>(IGN.Flags)); |
| 304 |
writeVar(Strings.index(IGN.URI), OS); |
| 305 |
llvm::StringRef Hash(reinterpret_cast<const char *>(IGN.Digest.data()), |
| 306 |
IGN.Digest.size()); |
| 307 |
OS << Hash; |
| 308 |
writeVar(IGN.DirectIncludes.size(), OS); |
| 309 |
for (llvm::StringRef Include : IGN.DirectIncludes) |
| 310 |
writeVar(Strings.index(Include), OS); |
| 311 |
} |
| 312 |
|
| 313 |
void writeSymbol(const Symbol &Sym, const StringTableOut &Strings, |
| 314 |
llvm::raw_ostream &OS) { |
| 315 |
OS << Sym.ID.raw(); // TODO: once we start writing xrefs and posting lists, |
| 316 |
// symbol IDs should probably be in a string table. |
| 317 |
OS.write(static_cast<uint8_t>(Sym.SymInfo.Kind)); |
| 318 |
OS.write(static_cast<uint8_t>(Sym.SymInfo.Lang)); |
| 319 |
writeVar(Strings.index(Sym.Name), OS); |
| 320 |
writeVar(Strings.index(Sym.Scope), OS); |
| 321 |
writeVar(Strings.index(Sym.TemplateSpecializationArgs), OS); |
| 322 |
writeLocation(Sym.Definition, Strings, OS); |
| 323 |
writeLocation(Sym.CanonicalDeclaration, Strings, OS); |
| 324 |
writeVar(Sym.References, OS); |
| 325 |
OS.write(static_cast<uint8_t>(Sym.Flags)); |
| 326 |
writeVar(Strings.index(Sym.Signature), OS); |
| 327 |
writeVar(Strings.index(Sym.CompletionSnippetSuffix), OS); |
| 328 |
writeVar(Strings.index(Sym.Documentation), OS); |
| 329 |
writeVar(Strings.index(Sym.ReturnType), OS); |
| 330 |
writeVar(Strings.index(Sym.Type), OS); |
| 331 |
|
| 332 |
auto WriteInclude = [&](const Symbol::IncludeHeaderWithReferences &Include) { |
| 333 |
writeVar(Strings.index(Include.IncludeHeader), OS); |
| 334 |
writeVar((Include.References << 2) | Include.SupportedDirectives, OS); |
| 335 |
}; |
| 336 |
writeVar(Sym.IncludeHeaders.size(), OS); |
| 337 |
for (const auto &Include : Sym.IncludeHeaders) |
| 338 |
WriteInclude(Include); |
| 339 |
} |
| 340 |
|
| 341 |
Symbol readSymbol(Reader &Data, llvm::ArrayRef<llvm::StringRef> Strings, |
| 342 |
SymbolOrigin Origin) { |
| 343 |
Symbol Sym; |
| 344 |
Sym.ID = Data.consumeID(); |
| 345 |
Sym.SymInfo.Kind = static_cast<index::SymbolKind>(Data.consume8()); |
| 346 |
Sym.SymInfo.Lang = static_cast<index::SymbolLanguage>(Data.consume8()); |
| 347 |
Sym.Name = Data.consumeString(Strings); |
| 348 |
Sym.Scope = Data.consumeString(Strings); |
| 349 |
Sym.TemplateSpecializationArgs = Data.consumeString(Strings); |
| 350 |
Sym.Definition = readLocation(Data, Strings); |
| 351 |
Sym.CanonicalDeclaration = readLocation(Data, Strings); |
| 352 |
Sym.References = Data.consumeVar(); |
| 353 |
Sym.Flags = static_cast<Symbol::SymbolFlag>(Data.consume8()); |
| 354 |
Sym.Origin = Origin; |
| 355 |
Sym.Signature = Data.consumeString(Strings); |
| 356 |
Sym.CompletionSnippetSuffix = Data.consumeString(Strings); |
| 357 |
Sym.Documentation = Data.consumeString(Strings); |
| 358 |
Sym.ReturnType = Data.consumeString(Strings); |
| 359 |
Sym.Type = Data.consumeString(Strings); |
| 360 |
if (!Data.consumeSize(Sym.IncludeHeaders)) |
| 361 |
return Sym; |
| 362 |
for (auto &I : Sym.IncludeHeaders) { |
| 363 |
I.IncludeHeader = Data.consumeString(Strings); |
| 364 |
uint32_t RefsWithDirectives = Data.consumeVar(); |
| 365 |
I.References = RefsWithDirectives >> 2; |
| 366 |
I.SupportedDirectives = RefsWithDirectives & 0x3; |
| 367 |
} |
| 368 |
return Sym; |
| 369 |
} |
| 370 |
|
| 371 |
// REFS ENCODING |
| 372 |
// A refs section has data grouped by Symbol. Each symbol has: |
| 373 |
// - SymbolID: 8 bytes |
| 374 |
// - NumRefs: varint |
| 375 |
// - Ref[NumRefs] |
| 376 |
// Fields of Ref are encoded in turn, see implementation. |
| 377 |
|
| 378 |
void writeRefs(const SymbolID &ID, llvm::ArrayRef<Ref> Refs, |
| 379 |
const StringTableOut &Strings, llvm::raw_ostream &OS) { |
| 380 |
OS << ID.raw(); |
| 381 |
writeVar(Refs.size(), OS); |
| 382 |
for (const auto &Ref : Refs) { |
| 383 |
OS.write(static_cast<unsigned char>(Ref.Kind)); |
| 384 |
writeLocation(Ref.Location, Strings, OS); |
| 385 |
OS << Ref.Container.raw(); |
| 386 |
} |
| 387 |
} |
| 388 |
|
| 389 |
std::pair<SymbolID, std::vector<Ref>> |
| 390 |
readRefs(Reader &Data, llvm::ArrayRef<llvm::StringRef> Strings) { |
| 391 |
std::pair<SymbolID, std::vector<Ref>> Result; |
| 392 |
Result.first = Data.consumeID(); |
| 393 |
if (!Data.consumeSize(Result.second)) |
| 394 |
return Result; |
| 395 |
for (auto &Ref : Result.second) { |
| 396 |
Ref.Kind = static_cast<RefKind>(Data.consume8()); |
| 397 |
Ref.Location = readLocation(Data, Strings); |
| 398 |
Ref.Container = Data.consumeID(); |
| 399 |
} |
| 400 |
return Result; |
| 401 |
} |
| 402 |
|
| 403 |
// RELATIONS ENCODING |
| 404 |
// A relations section is a flat list of relations. Each relation has: |
| 405 |
// - SymbolID (subject): 8 bytes |
| 406 |
// - relation kind (predicate): 1 byte |
| 407 |
// - SymbolID (object): 8 bytes |
| 408 |
// In the future, we might prefer a packed representation if the need arises. |
| 409 |
|
| 410 |
void writeRelation(const Relation &R, llvm::raw_ostream &OS) { |
| 411 |
OS << R.Subject.raw(); |
| 412 |
OS.write(static_cast<uint8_t>(R.Predicate)); |
| 413 |
OS << R.Object.raw(); |
| 414 |
} |
| 415 |
|
| 416 |
Relation readRelation(Reader &Data) { |
| 417 |
SymbolID Subject = Data.consumeID(); |
| 418 |
RelationKind Predicate = static_cast<RelationKind>(Data.consume8()); |
| 419 |
SymbolID Object = Data.consumeID(); |
| 420 |
return {Subject, Predicate, Object}; |
| 421 |
} |
| 422 |
|
| 423 |
struct InternedCompileCommand { |
| 424 |
llvm::StringRef Directory; |
| 425 |
std::vector<llvm::StringRef> CommandLine; |
| 426 |
}; |
| 427 |
|
| 428 |
void writeCompileCommand(const InternedCompileCommand &Cmd, |
| 429 |
const StringTableOut &Strings, |
| 430 |
llvm::raw_ostream &CmdOS) { |
| 431 |
writeVar(Strings.index(Cmd.Directory), CmdOS); |
| 432 |
writeVar(Cmd.CommandLine.size(), CmdOS); |
| 433 |
for (llvm::StringRef C : Cmd.CommandLine) |
| 434 |
writeVar(Strings.index(C), CmdOS); |
| 435 |
} |
| 436 |
|
| 437 |
InternedCompileCommand |
| 438 |
readCompileCommand(Reader CmdReader, llvm::ArrayRef<llvm::StringRef> Strings) { |
| 439 |
InternedCompileCommand Cmd; |
| 440 |
Cmd.Directory = CmdReader.consumeString(Strings); |
| 441 |
if (!CmdReader.consumeSize(Cmd.CommandLine)) |
| 442 |
return Cmd; |
| 443 |
for (llvm::StringRef &C : Cmd.CommandLine) |
| 444 |
C = CmdReader.consumeString(Strings); |
| 445 |
return Cmd; |
| 446 |
} |
| 447 |
|
| 448 |
// FILE ENCODING |
| 449 |
// A file is a RIFF chunk with type 'CdIx'. |
| 450 |
// It contains the sections: |
| 451 |
// - meta: version number |
| 452 |
// - srcs: information related to include graph |
| 453 |
// - stri: string table |
| 454 |
// - symb: symbols |
| 455 |
// - refs: references to symbols |
| 456 |
|
| 457 |
// The current versioning scheme is simple - non-current versions are rejected. |
| 458 |
// If you make a breaking change, bump this version number to invalidate stored |
| 459 |
// data. Later we may want to support some backward compatibility. |
| 460 |
constexpr static uint32_t Version = 19; |
| 461 |
|
| 462 |
llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data, |
| 463 |
SymbolOrigin Origin) { |
| 464 |
auto RIFF = riff::readFile(Data); |
| 465 |
if (!RIFF) |
| 466 |
return RIFF.takeError(); |
| 467 |
if (RIFF->Type != riff::fourCC("CdIx")) |
| 468 |
return error("wrong RIFF filetype: {0}", riff::fourCCStr(RIFF->Type)); |
| 469 |
llvm::StringMap<llvm::StringRef> Chunks; |
| 470 |
for (const auto &Chunk : RIFF->Chunks) |
| 471 |
Chunks.try_emplace(llvm::StringRef(Chunk.ID.data(), Chunk.ID.size()), |
| 472 |
Chunk.Data); |
| 473 |
|
| 474 |
if (!Chunks.count("meta")) |
| 475 |
return error("missing meta chunk"); |
| 476 |
Reader Meta(Chunks.lookup("meta")); |
| 477 |
auto SeenVersion = Meta.consume32(); |
| 478 |
if (SeenVersion != Version) |
| 479 |
return error("wrong version: want {0}, got {1}", Version, SeenVersion); |
| 480 |
|
| 481 |
// meta chunk is checked above, as we prefer the "version mismatch" error. |
| 482 |
for (llvm::StringRef RequiredChunk : {"stri"}) |
| 483 |
if (!Chunks.count(RequiredChunk)) |
| 484 |
return error("missing required chunk {0}", RequiredChunk); |
| 485 |
|
| 486 |
auto Strings = readStringTable(Chunks.lookup("stri")); |
| 487 |
if (!Strings) |
| 488 |
return Strings.takeError(); |
| 489 |
|
| 490 |
IndexFileIn Result; |
| 491 |
if (Chunks.count("srcs")) { |
| 492 |
Reader SrcsReader(Chunks.lookup("srcs")); |
| 493 |
Result.Sources.emplace(); |
| 494 |
while (!SrcsReader.eof()) { |
| 495 |
auto IGN = readIncludeGraphNode(SrcsReader, Strings->Strings); |
| 496 |
auto Entry = Result.Sources->try_emplace(IGN.URI).first; |
| 497 |
Entry->getValue() = std::move(IGN); |
| 498 |
// We change all the strings inside the structure to point at the keys in |
| 499 |
// the map, since it is the only copy of the string that's going to live. |
| 500 |
Entry->getValue().URI = Entry->getKey(); |
| 501 |
for (auto &Include : Entry->getValue().DirectIncludes) |
| 502 |
Include = Result.Sources->try_emplace(Include).first->getKey(); |
| 503 |
} |
| 504 |
if (SrcsReader.err()) |
| 505 |
return error("malformed or truncated include uri"); |
| 506 |
} |
| 507 |
|
| 508 |
if (Chunks.count("symb")) { |
| 509 |
Reader SymbolReader(Chunks.lookup("symb")); |
| 510 |
SymbolSlab::Builder Symbols; |
| 511 |
while (!SymbolReader.eof()) |
| 512 |
Symbols.insert(readSymbol(SymbolReader, Strings->Strings, Origin)); |
| 513 |
if (SymbolReader.err()) |
| 514 |
return error("malformed or truncated symbol"); |
| 515 |
Result.Symbols = std::move(Symbols).build(); |
| 516 |
} |
| 517 |
if (Chunks.count("refs")) { |
| 518 |
Reader RefsReader(Chunks.lookup("refs")); |
| 519 |
RefSlab::Builder Refs; |
| 520 |
while (!RefsReader.eof()) { |
| 521 |
auto RefsBundle = readRefs(RefsReader, Strings->Strings); |
| 522 |
for (const auto &Ref : RefsBundle.second) // FIXME: bulk insert? |
| 523 |
Refs.insert(RefsBundle.first, Ref); |
| 524 |
} |
| 525 |
if (RefsReader.err()) |
| 526 |
return error("malformed or truncated refs"); |
| 527 |
Result.Refs = std::move(Refs).build(); |
| 528 |
} |
| 529 |
if (Chunks.count("rela")) { |
| 530 |
Reader RelationsReader(Chunks.lookup("rela")); |
| 531 |
RelationSlab::Builder Relations; |
| 532 |
while (!RelationsReader.eof()) |
| 533 |
Relations.insert(readRelation(RelationsReader)); |
| 534 |
if (RelationsReader.err()) |
| 535 |
return error("malformed or truncated relations"); |
| 536 |
Result.Relations = std::move(Relations).build(); |
| 537 |
} |
| 538 |
if (Chunks.count("cmdl")) { |
| 539 |
Reader CmdReader(Chunks.lookup("cmdl")); |
| 540 |
InternedCompileCommand Cmd = |
| 541 |
readCompileCommand(CmdReader, Strings->Strings); |
| 542 |
if (CmdReader.err()) |
| 543 |
return error("malformed or truncated commandline section"); |
| 544 |
Result.Cmd.emplace(); |
| 545 |
Result.Cmd->Directory = std::string(Cmd.Directory); |
| 546 |
Result.Cmd->CommandLine.reserve(Cmd.CommandLine.size()); |
| 547 |
for (llvm::StringRef C : Cmd.CommandLine) |
| 548 |
Result.Cmd->CommandLine.emplace_back(C); |
| 549 |
} |
| 550 |
return std::move(Result); |
| 551 |
} |
| 552 |
|
| 553 |
template <class Callback> |
| 554 |
void visitStrings(IncludeGraphNode &IGN, const Callback &CB) { |
| 555 |
CB(IGN.URI); |
| 556 |
for (llvm::StringRef &Include : IGN.DirectIncludes) |
| 557 |
CB(Include); |
| 558 |
} |
| 559 |
|
| 560 |
void writeRIFF(const IndexFileOut &Data, llvm::raw_ostream &OS) { |
| 561 |
assert(Data.Symbols && "An index file without symbols makes no sense!"); |
| 562 |
riff::File RIFF; |
| 563 |
RIFF.Type = riff::fourCC("CdIx"); |
| 564 |
|
| 565 |
llvm::SmallString<4> Meta; |
| 566 |
{ |
| 567 |
llvm::raw_svector_ostream MetaOS(Meta); |
| 568 |
write32(Version, MetaOS); |
| 569 |
} |
| 570 |
RIFF.Chunks.push_back({riff::fourCC("meta"), Meta}); |
| 571 |
|
| 572 |
StringTableOut Strings; |
| 573 |
std::vector<Symbol> Symbols; |
| 574 |
for (const auto &Sym : *Data.Symbols) { |
| 575 |
Symbols.emplace_back(Sym); |
| 576 |
visitStrings(Symbols.back(), |
| 577 |
[&](llvm::StringRef &S) { Strings.intern(S); }); |
| 578 |
} |
| 579 |
std::vector<IncludeGraphNode> Sources; |
| 580 |
if (Data.Sources) |
| 581 |
for (const auto &Source : *Data.Sources) { |
| 582 |
Sources.push_back(Source.getValue()); |
| 583 |
visitStrings(Sources.back(), |
| 584 |
[&](llvm::StringRef &S) { Strings.intern(S); }); |
| 585 |
} |
| 586 |
|
| 587 |
std::vector<std::pair<SymbolID, std::vector<Ref>>> Refs; |
| 588 |
if (Data.Refs) { |
| 589 |
for (const auto &Sym : *Data.Refs) { |
| 590 |
Refs.emplace_back(Sym); |
| 591 |
for (auto &Ref : Refs.back().second) { |
| 592 |
llvm::StringRef File = Ref.Location.FileURI; |
| 593 |
Strings.intern(File); |
| 594 |
Ref.Location.FileURI = File.data(); |
| 595 |
} |
| 596 |
} |
| 597 |
} |
| 598 |
|
| 599 |
std::vector<Relation> Relations; |
| 600 |
if (Data.Relations) { |
| 601 |
for (const auto &Relation : *Data.Relations) { |
| 602 |
Relations.emplace_back(Relation); |
| 603 |
// No strings to be interned in relations. |
| 604 |
} |
| 605 |
} |
| 606 |
|
| 607 |
InternedCompileCommand InternedCmd; |
| 608 |
if (Data.Cmd) { |
| 609 |
InternedCmd.CommandLine.reserve(Data.Cmd->CommandLine.size()); |
| 610 |
InternedCmd.Directory = Data.Cmd->Directory; |
| 611 |
Strings.intern(InternedCmd.Directory); |
| 612 |
for (llvm::StringRef C : Data.Cmd->CommandLine) { |
| 613 |
InternedCmd.CommandLine.emplace_back(C); |
| 614 |
Strings.intern(InternedCmd.CommandLine.back()); |
| 615 |
} |
| 616 |
} |
| 617 |
|
| 618 |
std::string StringSection; |
| 619 |
{ |
| 620 |
llvm::raw_string_ostream StringOS(StringSection); |
| 621 |
Strings.finalize(StringOS); |
| 622 |
} |
| 623 |
RIFF.Chunks.push_back({riff::fourCC("stri"), StringSection}); |
| 624 |
|
| 625 |
std::string SymbolSection; |
| 626 |
{ |
| 627 |
llvm::raw_string_ostream SymbolOS(SymbolSection); |
| 628 |
for (const auto &Sym : Symbols) |
| 629 |
writeSymbol(Sym, Strings, SymbolOS); |
| 630 |
} |
| 631 |
RIFF.Chunks.push_back({riff::fourCC("symb"), SymbolSection}); |
| 632 |
|
| 633 |
std::string RefsSection; |
| 634 |
if (Data.Refs) { |
| 635 |
{ |
| 636 |
llvm::raw_string_ostream RefsOS(RefsSection); |
| 637 |
for (const auto &Sym : Refs) |
| 638 |
writeRefs(Sym.first, Sym.second, Strings, RefsOS); |
| 639 |
} |
| 640 |
RIFF.Chunks.push_back({riff::fourCC("refs"), RefsSection}); |
| 641 |
} |
| 642 |
|
| 643 |
std::string RelationSection; |
| 644 |
if (Data.Relations) { |
| 645 |
{ |
| 646 |
llvm::raw_string_ostream RelationOS{RelationSection}; |
| 647 |
for (const auto &Relation : Relations) |
| 648 |
writeRelation(Relation, RelationOS); |
| 649 |
} |
| 650 |
RIFF.Chunks.push_back({riff::fourCC("rela"), RelationSection}); |
| 651 |
} |
| 652 |
|
| 653 |
std::string SrcsSection; |
| 654 |
{ |
| 655 |
{ |
| 656 |
llvm::raw_string_ostream SrcsOS(SrcsSection); |
| 657 |
for (const auto &SF : Sources) |
| 658 |
writeIncludeGraphNode(SF, Strings, SrcsOS); |
| 659 |
} |
| 660 |
RIFF.Chunks.push_back({riff::fourCC("srcs"), SrcsSection}); |
| 661 |
} |
| 662 |
|
| 663 |
std::string CmdlSection; |
| 664 |
if (Data.Cmd) { |
| 665 |
{ |
| 666 |
llvm::raw_string_ostream CmdOS(CmdlSection); |
| 667 |
writeCompileCommand(InternedCmd, Strings, CmdOS); |
| 668 |
} |
| 669 |
RIFF.Chunks.push_back({riff::fourCC("cmdl"), CmdlSection}); |
| 670 |
} |
| 671 |
|
| 672 |
OS << RIFF; |
| 673 |
} |
| 674 |
|
| 675 |
} // namespace |
| 676 |
|
| 677 |
// Defined in YAMLSerialization.cpp. |
| 678 |
void writeYAML(const IndexFileOut &, llvm::raw_ostream &); |
| 679 |
llvm::Expected<IndexFileIn> readYAML(llvm::StringRef, SymbolOrigin Origin); |
| 680 |
|
| 681 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const IndexFileOut &O) { |
| 682 |
switch (O.Format) { |
| 683 |
case IndexFileFormat::RIFF: |
| 684 |
writeRIFF(O, OS); |
| 685 |
break; |
| 686 |
case IndexFileFormat::YAML: |
| 687 |
writeYAML(O, OS); |
| 688 |
break; |
| 689 |
} |
| 690 |
return OS; |
| 691 |
} |
| 692 |
|
| 693 |
llvm::Expected<IndexFileIn> readIndexFile(llvm::StringRef Data, |
| 694 |
SymbolOrigin Origin) { |
| 695 |
if (Data.starts_with("RIFF")) { |
| 696 |
return readRIFF(Data, Origin); |
| 697 |
} |
| 698 |
if (auto YAMLContents = readYAML(Data, Origin)) { |
| 699 |
return std::move(*YAMLContents); |
| 700 |
} else { |
| 701 |
return error("Not a RIFF file and failed to parse as YAML: {0}", |
| 702 |
YAMLContents.takeError()); |
| 703 |
} |
| 704 |
} |
| 705 |
|
| 706 |
std::unique_ptr<SymbolIndex> loadIndex(llvm::StringRef SymbolFilename, |
| 707 |
SymbolOrigin Origin, bool UseDex) { |
| 708 |
trace::Span OverallTracer("LoadIndex"); |
| 709 |
auto Buffer = llvm::MemoryBuffer::getFile(SymbolFilename); |
| 710 |
if (!Buffer) { |
| 711 |
elog("Can't open {0}: {1}", SymbolFilename, Buffer.getError().message()); |
| 712 |
return nullptr; |
| 713 |
} |
| 714 |
|
| 715 |
SymbolSlab Symbols; |
| 716 |
RefSlab Refs; |
| 717 |
RelationSlab Relations; |
| 718 |
{ |
| 719 |
trace::Span Tracer("ParseIndex"); |
| 720 |
if (auto I = readIndexFile(Buffer->get()->getBuffer(), Origin)) { |
| 721 |
if (I->Symbols) |
| 722 |
Symbols = std::move(*I->Symbols); |
| 723 |
if (I->Refs) |
| 724 |
Refs = std::move(*I->Refs); |
| 725 |
if (I->Relations) |
| 726 |
Relations = std::move(*I->Relations); |
| 727 |
} else { |
| 728 |
elog("Bad index file: {0}", I.takeError()); |
| 729 |
return nullptr; |
| 730 |
} |
| 731 |
} |
| 732 |
|
| 733 |
size_t NumSym = Symbols.size(); |
| 734 |
size_t NumRefs = Refs.numRefs(); |
| 735 |
size_t NumRelations = Relations.size(); |
| 736 |
|
| 737 |
trace::Span Tracer("BuildIndex"); |
| 738 |
auto Index = UseDex ? dex::Dex::build(std::move(Symbols), std::move(Refs), |
| 739 |
std::move(Relations)) |
| 740 |
: MemIndex::build(std::move(Symbols), std::move(Refs), |
| 741 |
std::move(Relations)); |
| 742 |
vlog("Loaded {0} from {1} with estimated memory usage {2} bytes\n" |
| 743 |
" - number of symbols: {3}\n" |
| 744 |
" - number of refs: {4}\n" |
| 745 |
" - number of relations: {5}", |
| 746 |
UseDex ? "Dex" : "MemIndex", SymbolFilename, |
| 747 |
Index->estimateMemoryUsage(), NumSym, NumRefs, NumRelations); |
| 748 |
return Index; |
| 749 |
} |
| 750 |
|
| 751 |
} // namespace clangd |
| 752 |
} // namespace clang |