contrib/llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

   1 //===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
  11 #include "llvm/ADT/SmallString.h"
  12 #include "llvm/ADT/StringExtras.h"
  13 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
  14 #include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
  15 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
  16 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
  17 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
  18 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
  19 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
  20 #include "llvm/Support/Error.h"
  21 #include "llvm/Support/ScopedPrinter.h"
  22
  23 using namespace llvm;
  24 using namespace llvm::codeview;
  25
  26 namespace {
  27
  28 /// Implementation of CodeView type stream merging.
  29 ///
  30 /// A CodeView type stream is a series of records that reference each other
  31 /// through type indices. A type index is either "simple", meaning it is less
  32 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
  33 /// refers to a prior type record in the current stream. The type index of a
  34 /// record is equal to the number of records before it in the stream plus
  35 /// 0x1000.
  36 ///
  37 /// Type records are only allowed to use type indices smaller than their own, so
  38 /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
  39 /// the type graph of the source program are resolved with forward declarations
  40 /// of composite types. This class implements the following type stream merging
  41 /// algorithm, which relies on this DAG structure:
  42 ///
  43 /// - Begin with a new empty stream, and a new empty hash table that maps from
  44 ///   type record contents to new type index.
  45 /// - For each new type stream, maintain a map from source type index to
  46 ///   destination type index.
  47 /// - For each record, copy it and rewrite its type indices to be valid in the
  48 ///   destination type stream.
  49 /// - If the new type record is not already present in the destination stream
  50 ///   hash table, append it to the destination type stream, assign it the next
  51 ///   type index, and update the two hash tables.
  52 /// - If the type record already exists in the destination stream, discard it
  53 ///   and update the type index map to forward the source type index to the
  54 ///   existing destination type index.
  55 ///
  56 /// As an additional complication, type stream merging actually produces two
  57 /// streams: an item (or IPI) stream and a type stream, as this is what is
  58 /// actually stored in the final PDB. We choose which records go where by
  59 /// looking at the record kind.
  60 class TypeStreamMerger : public TypeVisitorCallbacks {
  61 public:
  62   TypeStreamMerger(TypeTableBuilder &DestIdStream,
  63                    TypeTableBuilder &DestTypeStream, TypeServerHandler *Handler)
  64       : DestIdStream(DestIdStream), DestTypeStream(DestTypeStream),
  65         FieldListBuilder(DestTypeStream), Handler(Handler) {}
  66
  67   static const TypeIndex Untranslated;
  68
  69 /// TypeVisitorCallbacks overrides.
  70 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
  71   Error visitKnownRecord(CVType &CVR, Name##Record &Record) override;
  72 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
  73   Error visitKnownMember(CVMemberRecord &CVR, Name##Record &Record) override;
  74 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  75 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  76 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
  77
  78   Error visitUnknownType(CVType &Record) override;
  79
  80   Error visitTypeBegin(CVType &Record) override;
  81   Error visitTypeEnd(CVType &Record) override;
  82   Error visitMemberEnd(CVMemberRecord &Record) override;
  83
  84   Error mergeStream(const CVTypeArray &Types);
  85
  86 private:
  87   void addMapping(TypeIndex Idx);
  88
  89   bool remapIndex(TypeIndex &Idx);
  90
  91   size_t slotForIndex(TypeIndex Idx) const {
  92     assert(!Idx.isSimple() && "simple type indices have no slots");
  93     return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
  94   }
  95
  96   Error errorCorruptRecord() const {
  97     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
  98   }
  99
 100   template <typename RecordType>
 101   Error writeRecord(RecordType &R, bool RemapSuccess) {
 102     TypeIndex DestIdx = Untranslated;
 103     if (RemapSuccess)
 104       DestIdx = DestTypeStream.writeKnownType(R);
 105     addMapping(DestIdx);
 106     return Error::success();
 107   }
 108
 109   template <typename RecordType>
 110   Error writeIdRecord(RecordType &R, bool RemapSuccess) {
 111     TypeIndex DestIdx = Untranslated;
 112     if (RemapSuccess)
 113       DestIdx = DestIdStream.writeKnownType(R);
 114     addMapping(DestIdx);
 115     return Error::success();
 116   }
 117
 118   template <typename RecordType>
 119   Error writeMember(RecordType &R, bool RemapSuccess) {
 120     if (RemapSuccess)
 121       FieldListBuilder.writeMemberType(R);
 122     else
 123       HadUntranslatedMember = true;
 124     return Error::success();
 125   }
 126
 127   Optional<Error> LastError;
 128
 129   bool IsSecondPass = false;
 130
 131   bool HadUntranslatedMember = false;
 132
 133   unsigned NumBadIndices = 0;
 134
 135   BumpPtrAllocator Allocator;
 136
 137   TypeTableBuilder &DestIdStream;
 138   TypeTableBuilder &DestTypeStream;
 139   FieldListRecordBuilder FieldListBuilder;
 140   TypeServerHandler *Handler;
 141
 142   TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
 143
 144   /// Map from source type index to destination type index. Indexed by source
 145   /// type index minus 0x1000.
 146   SmallVector<TypeIndex, 0> IndexMap;
 147 };
 148
 149 } // end anonymous namespace
 150
 151 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
 152
 153 Error TypeStreamMerger::visitTypeBegin(CVRecord<TypeLeafKind> &Rec) {
 154   return Error::success();
 155 }
 156
 157 Error TypeStreamMerger::visitTypeEnd(CVRecord<TypeLeafKind> &Rec) {
 158   CurIndex = TypeIndex(CurIndex.getIndex() + 1);
 159   if (!IsSecondPass)
 160     assert(IndexMap.size() == slotForIndex(CurIndex) &&
 161            "visitKnownRecord should add one index map entry");
 162   return Error::success();
 163 }
 164
 165 Error TypeStreamMerger::visitMemberEnd(CVMemberRecord &Rec) {
 166   return Error::success();
 167 }
 168
 169 void TypeStreamMerger::addMapping(TypeIndex Idx) {
 170   if (!IsSecondPass) {
 171     assert(IndexMap.size() == slotForIndex(CurIndex) &&
 172            "visitKnownRecord should add one index map entry");
 173     IndexMap.push_back(Idx);
 174   } else {
 175     assert(slotForIndex(CurIndex) < IndexMap.size());
 176     IndexMap[slotForIndex(CurIndex)] = Idx;
 177   }
 178 }
 179
 180 bool TypeStreamMerger::remapIndex(TypeIndex &Idx) {
 181   // Simple types are unchanged.
 182   if (Idx.isSimple())
 183     return true;
 184
 185   // Check if this type index refers to a record we've already translated
 186   // successfully. If it refers to a type later in the stream or a record we
 187   // had to defer, defer it until later pass.
 188   unsigned MapPos = slotForIndex(Idx);
 189   if (MapPos < IndexMap.size() && IndexMap[MapPos] != Untranslated) {
 190     Idx = IndexMap[MapPos];
 191     return true;
 192   }
 193
 194   // If this is the second pass and this index isn't in the map, then it points
 195   // outside the current type stream, and this is a corrupt record.
 196   if (IsSecondPass && MapPos >= IndexMap.size()) {
 197     // FIXME: Print a more useful error. We can give the current record and the
 198     // index that we think its pointing to.
 199     LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
 200   }
 201
 202   ++NumBadIndices;
 203
 204   // This type index is invalid. Remap this to "not translated by cvpack",
 205   // and return failure.
 206   Idx = Untranslated;
 207   return false;
 208 }
 209
 210 //----------------------------------------------------------------------------//
 211 // Item records
 212 //----------------------------------------------------------------------------//
 213
 214 Error TypeStreamMerger::visitKnownRecord(CVType &, FuncIdRecord &R) {
 215   bool Success = true;
 216   Success &= remapIndex(R.ParentScope);
 217   Success &= remapIndex(R.FunctionType);
 218   return writeIdRecord(R, Success);
 219 }
 220
 221 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFuncIdRecord &R) {
 222   bool Success = true;
 223   Success &= remapIndex(R.ClassType);
 224   Success &= remapIndex(R.FunctionType);
 225   return writeIdRecord(R, Success);
 226 }
 227
 228 Error TypeStreamMerger::visitKnownRecord(CVType &, StringIdRecord &R) {
 229   return writeIdRecord(R, remapIndex(R.Id));
 230 }
 231
 232 Error TypeStreamMerger::visitKnownRecord(CVType &, StringListRecord &R) {
 233   bool Success = true;
 234   for (TypeIndex &Str : R.StringIndices)
 235     Success &= remapIndex(Str);
 236   return writeIdRecord(R, Success);
 237 }
 238
 239 Error TypeStreamMerger::visitKnownRecord(CVType &, BuildInfoRecord &R) {
 240   bool Success = true;
 241   for (TypeIndex &Arg : R.ArgIndices)
 242     Success &= remapIndex(Arg);
 243   return writeIdRecord(R, Success);
 244 }
 245
 246 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtSourceLineRecord &R) {
 247   bool Success = true;
 248   Success &= remapIndex(R.UDT);
 249   Success &= remapIndex(R.SourceFile);
 250   // FIXME: Translate UdtSourceLineRecord into UdtModSourceLineRecords in the
 251   // IPI stream.
 252   return writeIdRecord(R, Success);
 253 }
 254
 255 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtModSourceLineRecord &R) {
 256   bool Success = true;
 257   Success &= remapIndex(R.UDT);
 258   Success &= remapIndex(R.SourceFile);
 259   return writeIdRecord(R, Success);
 260 }
 261
 262 //----------------------------------------------------------------------------//
 263 // Type records
 264 //----------------------------------------------------------------------------//
 265
 266 Error TypeStreamMerger::visitKnownRecord(CVType &, ModifierRecord &R) {
 267   return writeRecord(R, remapIndex(R.ModifiedType));
 268 }
 269
 270 Error TypeStreamMerger::visitKnownRecord(CVType &, ProcedureRecord &R) {
 271   bool Success = true;
 272   Success &= remapIndex(R.ReturnType);
 273   Success &= remapIndex(R.ArgumentList);
 274   return writeRecord(R, Success);
 275 }
 276
 277 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFunctionRecord &R) {
 278   bool Success = true;
 279   Success &= remapIndex(R.ReturnType);
 280   Success &= remapIndex(R.ClassType);
 281   Success &= remapIndex(R.ThisType);
 282   Success &= remapIndex(R.ArgumentList);
 283   return writeRecord(R, Success);
 284 }
 285
 286 Error TypeStreamMerger::visitKnownRecord(CVType &Type, ArgListRecord &R) {
 287   bool Success = true;
 288   for (TypeIndex &Arg : R.ArgIndices)
 289     Success &= remapIndex(Arg);
 290   if (auto EC = writeRecord(R, Success))
 291     return EC;
 292   return Error::success();
 293 }
 294
 295 Error TypeStreamMerger::visitKnownRecord(CVType &, PointerRecord &R) {
 296   bool Success = true;
 297   Success &= remapIndex(R.ReferentType);
 298   if (R.isPointerToMember())
 299     Success &= remapIndex(R.MemberInfo->ContainingType);
 300   return writeRecord(R, Success);
 301 }
 302
 303 Error TypeStreamMerger::visitKnownRecord(CVType &, ArrayRecord &R) {
 304   bool Success = true;
 305   Success &= remapIndex(R.ElementType);
 306   Success &= remapIndex(R.IndexType);
 307   return writeRecord(R, Success);
 308 }
 309
 310 Error TypeStreamMerger::visitKnownRecord(CVType &, ClassRecord &R) {
 311   bool Success = true;
 312   Success &= remapIndex(R.FieldList);
 313   Success &= remapIndex(R.DerivationList);
 314   Success &= remapIndex(R.VTableShape);
 315   return writeRecord(R, Success);
 316 }
 317
 318 Error TypeStreamMerger::visitKnownRecord(CVType &, UnionRecord &R) {
 319   return writeRecord(R, remapIndex(R.FieldList));
 320 }
 321
 322 Error TypeStreamMerger::visitKnownRecord(CVType &, EnumRecord &R) {
 323   bool Success = true;
 324   Success &= remapIndex(R.FieldList);
 325   Success &= remapIndex(R.UnderlyingType);
 326   return writeRecord(R, Success);
 327 }
 328
 329 Error TypeStreamMerger::visitKnownRecord(CVType &, BitFieldRecord &R) {
 330   return writeRecord(R, remapIndex(R.Type));
 331 }
 332
 333 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableShapeRecord &R) {
 334   return writeRecord(R, true);
 335 }
 336
 337 Error TypeStreamMerger::visitKnownRecord(CVType &, TypeServer2Record &R) {
 338   return writeRecord(R, true);
 339 }
 340
 341 Error TypeStreamMerger::visitKnownRecord(CVType &, LabelRecord &R) {
 342   return writeRecord(R, true);
 343 }
 344
 345 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableRecord &R) {
 346   bool Success = true;
 347   Success &= remapIndex(R.CompleteClass);
 348   Success &= remapIndex(R.OverriddenVFTable);
 349   return writeRecord(R, Success);
 350 }
 351
 352 Error TypeStreamMerger::visitKnownRecord(CVType &,
 353                                          MethodOverloadListRecord &R) {
 354   bool Success = true;
 355   for (OneMethodRecord &Meth : R.Methods)
 356     Success &= remapIndex(Meth.Type);
 357   return writeRecord(R, Success);
 358 }
 359
 360 Error TypeStreamMerger::visitKnownRecord(CVType &, FieldListRecord &R) {
 361   // Visit the members inside the field list.
 362   HadUntranslatedMember = false;
 363   FieldListBuilder.begin();
 364   CVTypeVisitor Visitor(*this);
 365   if (auto EC = Visitor.visitFieldListMemberStream(R.Data))
 366     return EC;
 367
 368   // Write the record if we translated all field list members.
 369   TypeIndex DestIdx = Untranslated;
 370   if (!HadUntranslatedMember)
 371     DestIdx = FieldListBuilder.end();
 372   else
 373     FieldListBuilder.reset();
 374   addMapping(DestIdx);
 375
 376   return Error::success();
 377 }
 378
 379 //----------------------------------------------------------------------------//
 380 // Member records
 381 //----------------------------------------------------------------------------//
 382
 383 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 384                                          NestedTypeRecord &R) {
 385   return writeMember(R, remapIndex(R.Type));
 386 }
 387
 388 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, OneMethodRecord &R) {
 389   bool Success = true;
 390   Success &= remapIndex(R.Type);
 391   return writeMember(R, Success);
 392 }
 393
 394 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 395                                          OverloadedMethodRecord &R) {
 396   return writeMember(R, remapIndex(R.MethodList));
 397 }
 398
 399 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 400                                          DataMemberRecord &R) {
 401   return writeMember(R, remapIndex(R.Type));
 402 }
 403
 404 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 405                                          StaticDataMemberRecord &R) {
 406   return writeMember(R, remapIndex(R.Type));
 407 }
 408
 409 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 410                                          EnumeratorRecord &R) {
 411   return writeMember(R, true);
 412 }
 413
 414 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, VFPtrRecord &R) {
 415   return writeMember(R, remapIndex(R.Type));
 416 }
 417
 418 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, BaseClassRecord &R) {
 419   return writeMember(R, remapIndex(R.Type));
 420 }
 421
 422 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 423                                          VirtualBaseClassRecord &R) {
 424   bool Success = true;
 425   Success &= remapIndex(R.BaseType);
 426   Success &= remapIndex(R.VBPtrType);
 427   return writeMember(R, Success);
 428 }
 429
 430 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 431                                          ListContinuationRecord &R) {
 432   return writeMember(R, remapIndex(R.ContinuationIndex));
 433 }
 434
 435 Error TypeStreamMerger::visitUnknownType(CVType &Rec) {
 436   // We failed to translate a type. Translate this index as "not translated".
 437   addMapping(TypeIndex(SimpleTypeKind::NotTranslated));
 438   return errorCorruptRecord();
 439 }
 440
 441 Error TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
 442   assert(IndexMap.empty());
 443   TypeVisitorCallbackPipeline Pipeline;
 444   LastError = Error::success();
 445
 446   TypeDeserializer Deserializer;
 447   Pipeline.addCallbackToPipeline(Deserializer);
 448   Pipeline.addCallbackToPipeline(*this);
 449
 450   CVTypeVisitor Visitor(Pipeline);
 451   if (Handler)
 452     Visitor.addTypeServerHandler(*Handler);
 453
 454   if (auto EC = Visitor.visitTypeStream(Types))
 455     return EC;
 456
 457   // If we found bad indices but no other errors, try doing another pass and see
 458   // if we can resolve the indices that weren't in the map on the first pass.
 459   // This may require multiple passes, but we should always make progress. MASM
 460   // is the only known CodeView producer that makes type streams that aren't
 461   // topologically sorted. The standard library contains MASM-produced objects,
 462   // so this is important to handle correctly, but we don't have to be too
 463   // efficient. MASM type streams are usually very small.
 464   while (!*LastError && NumBadIndices > 0) {
 465     unsigned BadIndicesRemaining = NumBadIndices;
 466     IsSecondPass = true;
 467     NumBadIndices = 0;
 468     CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
 469     if (auto EC = Visitor.visitTypeStream(Types))
 470       return EC;
 471
 472     assert(NumBadIndices <= BadIndicesRemaining &&
 473            "second pass found more bad indices");
 474     if (!*LastError && NumBadIndices == BadIndicesRemaining) {
 475       return llvm::make_error<CodeViewError>(
 476           cv_error_code::corrupt_record, "input type graph contains cycles");
 477     }
 478   }
 479
 480   IndexMap.clear();
 481
 482   Error Ret = std::move(*LastError);
 483   LastError.reset();
 484   return Ret;
 485 }
 486
 487 Error llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestIdStream,
 488                                        TypeTableBuilder &DestTypeStream,
 489                                        TypeServerHandler *Handler,
 490                                        const CVTypeArray &Types) {
 491   return TypeStreamMerger(DestIdStream, DestTypeStream, Handler)
 492       .mergeStream(Types);
 493 }