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/FieldListRecordBuilder.h"
15#include "llvm/DebugInfo/CodeView/StreamRef.h"
16#include "llvm/DebugInfo/CodeView/TypeIndex.h"
17#include "llvm/DebugInfo/CodeView/TypeRecord.h"
18#include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
19#include "llvm/Support/Error.h"
20#include "llvm/Support/ScopedPrinter.h"
21
22using namespace llvm;
23using namespace llvm::codeview;
24
25namespace {
26
27/// Implementation of CodeView type stream merging.
28///
29/// A CodeView type stream is a series of records that reference each other
30/// through type indices. A type index is either "simple", meaning it is less
31/// than 0x1000 and refers to a builtin type, or it is complex, meaning it
32/// refers to a prior type record in the current stream. The type index of a
33/// record is equal to the number of records before it in the stream plus
34/// 0x1000.
35///
36/// Type records are only allowed to use type indices smaller than their own, so
37/// a type stream is effectively a topologically sorted DAG. Cycles occuring in
38/// the type graph of the source program are resolved with forward declarations
39/// of composite types. This class implements the following type stream merging
40/// algorithm, which relies on this DAG structure:
41///
42/// - Begin with a new empty stream, and a new empty hash table that maps from
43///   type record contents to new type index.
44/// - For each new type stream, maintain a map from source type index to
45///   destination type index.
46/// - For each record, copy it and rewrite its type indices to be valid in the
47///   destination type stream.
48/// - If the new type record is not already present in the destination stream
49///   hash table, append it to the destination type stream, assign it the next
50///   type index, and update the two hash tables.
51/// - If the type record already exists in the destination stream, discard it
52///   and update the type index map to forward the source type index to the
53///   existing destination type index.
54class TypeStreamMerger : public TypeVisitorCallbacks {
55public:
56  TypeStreamMerger(TypeTableBuilder &DestStream) : DestStream(DestStream) {
57    assert(!hadError());
58  }
59
60/// TypeVisitorCallbacks overrides.
61#define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
62  Error visit##Name(Name##Record &Record) override;
63#define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
64  TYPE_RECORD(EnumName, EnumVal, Name)
65#define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
66#define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
67#include "llvm/DebugInfo/CodeView/TypeRecords.def"
68
69  Error visitUnknownType(const CVRecord<TypeLeafKind> &Record) override;
70
71  Error visitTypeBegin(const CVRecord<TypeLeafKind> &Record) override;
72  Error visitTypeEnd(const CVRecord<TypeLeafKind> &Record) override;
73
74  Error visitFieldListEnd(const CVRecord<TypeLeafKind> &Record) override;
75
76  bool mergeStream(const CVTypeArray &Types);
77
78private:
79  bool hadError() { return FoundBadTypeIndex; }
80
81  bool FoundBadTypeIndex = false;
82
83  FieldListRecordBuilder FieldBuilder;
84
85  TypeTableBuilder &DestStream;
86
87  size_t BeginIndexMapSize = 0;
88
89  /// Map from source type index to destination type index. Indexed by source
90  /// type index minus 0x1000.
91  SmallVector<TypeIndex, 0> IndexMap;
92};
93
94} // end anonymous namespace
95
96Error TypeStreamMerger::visitTypeBegin(const CVRecord<TypeLeafKind> &Rec) {
97  BeginIndexMapSize = IndexMap.size();
98  return Error::success();
99}
100
101Error TypeStreamMerger::visitTypeEnd(const CVRecord<TypeLeafKind> &Rec) {
102  assert(IndexMap.size() == BeginIndexMapSize + 1);
103  return Error::success();
104}
105
106Error TypeStreamMerger::visitFieldListEnd(const CVRecord<TypeLeafKind> &Rec) {
107  IndexMap.push_back(DestStream.writeFieldList(FieldBuilder));
108  FieldBuilder.reset();
109  return Error::success();
110}
111
112#define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
113  Error TypeStreamMerger::visit##Name(Name##Record &Record) {                  \
114    FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);                   \
115    IndexMap.push_back(DestStream.write##Name(Record));                        \
116    return Error::success();                                                   \
117  }
118#define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
119#define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
120  Error TypeStreamMerger::visit##Name(Name##Record &Record) {                  \
121    FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);                   \
122    FieldBuilder.write##Name(Record);                                          \
123    return Error::success();                                                   \
124  }
125#define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
126#include "llvm/DebugInfo/CodeView/TypeRecords.def"
127
128Error TypeStreamMerger::visitUnknownType(const CVRecord<TypeLeafKind> &Rec) {
129  // We failed to translate a type. Translate this index as "not translated".
130  IndexMap.push_back(
131      TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct));
132  return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
133}
134
135bool TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
136  assert(IndexMap.empty());
137  CVTypeVisitor Visitor(*this);
138  if (auto EC = Visitor.visitTypeStream(Types)) {
139    consumeError(std::move(EC));
140    return false;
141  }
142  IndexMap.clear();
143  return !hadError();
144}
145
146bool llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestStream,
147                                      const CVTypeArray &Types) {
148  return TypeStreamMerger(DestStream).mergeStream(Types);
149}
150