1 //===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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"
24 using namespace llvm::codeview;
28 /// Implementation of CodeView type stream merging.
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
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:
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.
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 {
62 TypeStreamMerger(TypeTableBuilder &DestIdStream,
63 TypeTableBuilder &DestTypeStream, TypeServerHandler *Handler)
64 : DestIdStream(DestIdStream), DestTypeStream(DestTypeStream),
65 FieldListBuilder(DestTypeStream), Handler(Handler) {}
67 static const TypeIndex Untranslated;
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"
78 Error visitUnknownType(CVType &Record) override;
80 Error visitTypeBegin(CVType &Record) override;
81 Error visitTypeEnd(CVType &Record) override;
82 Error visitMemberEnd(CVMemberRecord &Record) override;
84 Error mergeStream(const CVTypeArray &Types);
87 void addMapping(TypeIndex Idx);
89 bool remapIndex(TypeIndex &Idx);
91 size_t slotForIndex(TypeIndex Idx) const {
92 assert(!Idx.isSimple() && "simple type indices have no slots");
93 return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
96 Error errorCorruptRecord() const {
97 return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
100 template <typename RecordType>
101 Error writeRecord(RecordType &R, bool RemapSuccess) {
102 TypeIndex DestIdx = Untranslated;
104 DestIdx = DestTypeStream.writeKnownType(R);
106 return Error::success();
109 template <typename RecordType>
110 Error writeIdRecord(RecordType &R, bool RemapSuccess) {
111 TypeIndex DestIdx = Untranslated;
113 DestIdx = DestIdStream.writeKnownType(R);
115 return Error::success();
118 template <typename RecordType>
119 Error writeMember(RecordType &R, bool RemapSuccess) {
121 FieldListBuilder.writeMemberType(R);
123 HadUntranslatedMember = true;
124 return Error::success();
127 Optional<Error> LastError;
129 bool IsSecondPass = false;
131 bool HadUntranslatedMember = false;
133 unsigned NumBadIndices = 0;
135 BumpPtrAllocator Allocator;
137 TypeTableBuilder &DestIdStream;
138 TypeTableBuilder &DestTypeStream;
139 FieldListRecordBuilder FieldListBuilder;
140 TypeServerHandler *Handler;
142 TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
144 /// Map from source type index to destination type index. Indexed by source
145 /// type index minus 0x1000.
146 SmallVector<TypeIndex, 0> IndexMap;
149 } // end anonymous namespace
151 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
153 Error TypeStreamMerger::visitTypeBegin(CVRecord<TypeLeafKind> &Rec) {
154 return Error::success();
157 Error TypeStreamMerger::visitTypeEnd(CVRecord<TypeLeafKind> &Rec) {
158 CurIndex = TypeIndex(CurIndex.getIndex() + 1);
160 assert(IndexMap.size() == slotForIndex(CurIndex) &&
161 "visitKnownRecord should add one index map entry");
162 return Error::success();
165 Error TypeStreamMerger::visitMemberEnd(CVMemberRecord &Rec) {
166 return Error::success();
169 void TypeStreamMerger::addMapping(TypeIndex Idx) {
171 assert(IndexMap.size() == slotForIndex(CurIndex) &&
172 "visitKnownRecord should add one index map entry");
173 IndexMap.push_back(Idx);
175 assert(slotForIndex(CurIndex) < IndexMap.size());
176 IndexMap[slotForIndex(CurIndex)] = Idx;
180 bool TypeStreamMerger::remapIndex(TypeIndex &Idx) {
181 // Simple types are unchanged.
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];
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());
204 // This type index is invalid. Remap this to "not translated by cvpack",
205 // and return failure.
210 //----------------------------------------------------------------------------//
212 //----------------------------------------------------------------------------//
214 Error TypeStreamMerger::visitKnownRecord(CVType &, FuncIdRecord &R) {
216 Success &= remapIndex(R.ParentScope);
217 Success &= remapIndex(R.FunctionType);
218 return writeIdRecord(R, Success);
221 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFuncIdRecord &R) {
223 Success &= remapIndex(R.ClassType);
224 Success &= remapIndex(R.FunctionType);
225 return writeIdRecord(R, Success);
228 Error TypeStreamMerger::visitKnownRecord(CVType &, StringIdRecord &R) {
229 return writeIdRecord(R, remapIndex(R.Id));
232 Error TypeStreamMerger::visitKnownRecord(CVType &, StringListRecord &R) {
234 for (TypeIndex &Str : R.StringIndices)
235 Success &= remapIndex(Str);
236 return writeIdRecord(R, Success);
239 Error TypeStreamMerger::visitKnownRecord(CVType &, BuildInfoRecord &R) {
241 for (TypeIndex &Arg : R.ArgIndices)
242 Success &= remapIndex(Arg);
243 return writeIdRecord(R, Success);
246 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtSourceLineRecord &R) {
248 Success &= remapIndex(R.UDT);
249 Success &= remapIndex(R.SourceFile);
250 // FIXME: Translate UdtSourceLineRecord into UdtModSourceLineRecords in the
252 return writeIdRecord(R, Success);
255 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtModSourceLineRecord &R) {
257 Success &= remapIndex(R.UDT);
258 Success &= remapIndex(R.SourceFile);
259 return writeIdRecord(R, Success);
262 //----------------------------------------------------------------------------//
264 //----------------------------------------------------------------------------//
266 Error TypeStreamMerger::visitKnownRecord(CVType &, ModifierRecord &R) {
267 return writeRecord(R, remapIndex(R.ModifiedType));
270 Error TypeStreamMerger::visitKnownRecord(CVType &, ProcedureRecord &R) {
272 Success &= remapIndex(R.ReturnType);
273 Success &= remapIndex(R.ArgumentList);
274 return writeRecord(R, Success);
277 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFunctionRecord &R) {
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);
286 Error TypeStreamMerger::visitKnownRecord(CVType &Type, ArgListRecord &R) {
288 for (TypeIndex &Arg : R.ArgIndices)
289 Success &= remapIndex(Arg);
290 if (auto EC = writeRecord(R, Success))
292 return Error::success();
295 Error TypeStreamMerger::visitKnownRecord(CVType &, PointerRecord &R) {
297 Success &= remapIndex(R.ReferentType);
298 if (R.isPointerToMember())
299 Success &= remapIndex(R.MemberInfo->ContainingType);
300 return writeRecord(R, Success);
303 Error TypeStreamMerger::visitKnownRecord(CVType &, ArrayRecord &R) {
305 Success &= remapIndex(R.ElementType);
306 Success &= remapIndex(R.IndexType);
307 return writeRecord(R, Success);
310 Error TypeStreamMerger::visitKnownRecord(CVType &, ClassRecord &R) {
312 Success &= remapIndex(R.FieldList);
313 Success &= remapIndex(R.DerivationList);
314 Success &= remapIndex(R.VTableShape);
315 return writeRecord(R, Success);
318 Error TypeStreamMerger::visitKnownRecord(CVType &, UnionRecord &R) {
319 return writeRecord(R, remapIndex(R.FieldList));
322 Error TypeStreamMerger::visitKnownRecord(CVType &, EnumRecord &R) {
324 Success &= remapIndex(R.FieldList);
325 Success &= remapIndex(R.UnderlyingType);
326 return writeRecord(R, Success);
329 Error TypeStreamMerger::visitKnownRecord(CVType &, BitFieldRecord &R) {
330 return writeRecord(R, remapIndex(R.Type));
333 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableShapeRecord &R) {
334 return writeRecord(R, true);
337 Error TypeStreamMerger::visitKnownRecord(CVType &, TypeServer2Record &R) {
338 return writeRecord(R, true);
341 Error TypeStreamMerger::visitKnownRecord(CVType &, LabelRecord &R) {
342 return writeRecord(R, true);
345 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableRecord &R) {
347 Success &= remapIndex(R.CompleteClass);
348 Success &= remapIndex(R.OverriddenVFTable);
349 return writeRecord(R, Success);
352 Error TypeStreamMerger::visitKnownRecord(CVType &,
353 MethodOverloadListRecord &R) {
355 for (OneMethodRecord &Meth : R.Methods)
356 Success &= remapIndex(Meth.Type);
357 return writeRecord(R, Success);
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))
368 // Write the record if we translated all field list members.
369 TypeIndex DestIdx = Untranslated;
370 if (!HadUntranslatedMember)
371 DestIdx = FieldListBuilder.end();
373 FieldListBuilder.reset();
376 return Error::success();
379 //----------------------------------------------------------------------------//
381 //----------------------------------------------------------------------------//
383 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
384 NestedTypeRecord &R) {
385 return writeMember(R, remapIndex(R.Type));
388 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, OneMethodRecord &R) {
390 Success &= remapIndex(R.Type);
391 return writeMember(R, Success);
394 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
395 OverloadedMethodRecord &R) {
396 return writeMember(R, remapIndex(R.MethodList));
399 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
400 DataMemberRecord &R) {
401 return writeMember(R, remapIndex(R.Type));
404 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
405 StaticDataMemberRecord &R) {
406 return writeMember(R, remapIndex(R.Type));
409 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
410 EnumeratorRecord &R) {
411 return writeMember(R, true);
414 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, VFPtrRecord &R) {
415 return writeMember(R, remapIndex(R.Type));
418 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, BaseClassRecord &R) {
419 return writeMember(R, remapIndex(R.Type));
422 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
423 VirtualBaseClassRecord &R) {
425 Success &= remapIndex(R.BaseType);
426 Success &= remapIndex(R.VBPtrType);
427 return writeMember(R, Success);
430 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
431 ListContinuationRecord &R) {
432 return writeMember(R, remapIndex(R.ContinuationIndex));
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();
441 Error TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
442 assert(IndexMap.empty());
443 TypeVisitorCallbackPipeline Pipeline;
444 LastError = Error::success();
446 TypeDeserializer Deserializer;
447 Pipeline.addCallbackToPipeline(Deserializer);
448 Pipeline.addCallbackToPipeline(*this);
450 CVTypeVisitor Visitor(Pipeline);
452 Visitor.addTypeServerHandler(*Handler);
454 if (auto EC = Visitor.visitTypeStream(Types))
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;
468 CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
469 if (auto EC = Visitor.visitTypeStream(Types))
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");
482 Error Ret = std::move(*LastError);
487 Error llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestIdStream,
488 TypeTableBuilder &DestTypeStream,
489 TypeServerHandler *Handler,
490 const CVTypeArray &Types) {
491 return TypeStreamMerger(DestIdStream, DestTypeStream, Handler)