[codeview] Cope with unsorted streams in type merging

[rnk]

Summary

MASM can produce type streams that are not topologically sorted. It can
even produce type streams with circular references, but those are not
common in practice.

[ruiu]

Do you need multiple scans? I wonder if you can keep type records that were not resolved in the first pass in a map or something and backfill them once we visit all type records.

[rnk]

In D31629#717372, @ruiu wrote:

Do you need multiple scans? I wonder if you can keep type records that were not resolved in the first pass in a map or something and backfill them once we visit all type records.

You can avoid the traversal if you copy the unresolved records to temporary storage and topologically sort them. You can't backpatch the type records because inserting them into the destination stream requires hashing them, and the hash includes the type index references we'd need to backpatch.

In general, if the type stream is badly unsorted, this algorithm is O(n^2). Topo sort is O(n), but it requires extra storage. It seemed better to optimize for the common case of a large, sorted type stream, and hope that unsorted streams are rare and/or small.

[ruiu]

LGTM

llvm/trunk/include/llvm/DebugInfo/CodeView/TypeTableBuilder.h

TypeIndex end() {
     }
 
     TypeIndex Index;
     for (auto Record : TempSerializer.records()) {
       Index = TypeTable.writeSerializedRecord(Record);
     }
     return Index;
   }
+
+  /// Stop building the record.
+  void reset() {
+    if (auto EC = TempSerializer.visitTypeEnd(Type))
+      consumeError(std::move(EC));
+  }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_TYPETABLEBUILDER_H

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

 /// looking at the record kind.
 class TypeStreamMerger : public TypeVisitorCallbacks {
 public:
   TypeStreamMerger(TypeTableBuilder &DestIdStream,
                    TypeTableBuilder &DestTypeStream, TypeServerHandler *Handler)
       : DestIdStream(DestIdStream), DestTypeStream(DestTypeStream),
         FieldListBuilder(DestTypeStream), Handler(Handler) {}
 
+  static const TypeIndex Untranslated;
+
 /// TypeVisitorCallbacks overrides.
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
   Error visitKnownRecord(CVType &CVR, Name##Record &Record) override;
 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
   Error visitKnownMember(CVMemberRecord &CVR, Name##Record &Record) override;
 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
 
   Error visitUnknownType(CVType &Record) override;
 
   Error visitTypeBegin(CVType &Record) override;
   Error visitTypeEnd(CVType &Record) override;
   Error visitMemberEnd(CVMemberRecord &Record) override;
 
   Error mergeStream(const CVTypeArray &Types);
 
 private:
+  void addMapping(TypeIndex Idx);
+
   bool remapIndex(TypeIndex &Idx);
 
+  size_t slotForIndex(TypeIndex Idx) const {
+    assert(!Idx.isSimple() && "simple type indices have no slots");
+    return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
+  }
+
+  Error errorCorruptRecord() const {
+    return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
+  }
+
   template <typename RecordType>
   Error writeRecord(RecordType &R, bool RemapSuccess) {
-    if (!RemapSuccess) {
-      LastError = joinErrors(
-          std::move(*LastError),
-          llvm::make_error<CodeViewError>(cv_error_code::corrupt_record));
-    }
-    IndexMap.push_back(DestTypeStream.writeKnownType(R));
+    TypeIndex DestIdx = Untranslated;
+    if (RemapSuccess)
+      DestIdx = DestTypeStream.writeKnownType(R);
+    addMapping(DestIdx);
     return Error::success();
   }
 
   template <typename RecordType>
   Error writeIdRecord(RecordType &R, bool RemapSuccess) {
-    if (!RemapSuccess) {
-      LastError = joinErrors(
-          std::move(*LastError),
-          llvm::make_error<CodeViewError>(cv_error_code::corrupt_record));
-    }
-    IndexMap.push_back(DestIdStream.writeKnownType(R));
+    TypeIndex DestIdx = Untranslated;
+    if (RemapSuccess)
+      DestIdx = DestIdStream.writeKnownType(R);
+    addMapping(DestIdx);
     return Error::success();
   }
 
   template <typename RecordType>
   Error writeMember(RecordType &R, bool RemapSuccess) {
-    if (!RemapSuccess) {
-      LastError = joinErrors(
-          std::move(*LastError),
-          llvm::make_error<CodeViewError>(cv_error_code::corrupt_record));
-    }
+    if (RemapSuccess)
       FieldListBuilder.writeMemberType(R);
+    else
+      HadUntranslatedMember = true;
     return Error::success();
   }
 
   Optional<Error> LastError;
 
+  bool IsSecondPass = false;
+
+  bool HadUntranslatedMember = false;
+
+  unsigned NumBadIndices = 0;
+
   BumpPtrAllocator Allocator;
 
   TypeTableBuilder &DestIdStream;
   TypeTableBuilder &DestTypeStream;
   FieldListRecordBuilder FieldListBuilder;
   TypeServerHandler *Handler;
 
-#ifndef NDEBUG
-  /// Track the size of the index map in visitTypeBegin so we can check it in
-  /// visitTypeEnd.
-  size_t BeginIndexMapSize = 0;
-#endif
+  TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
 
   /// Map from source type index to destination type index. Indexed by source
   /// type index minus 0x1000.
   SmallVector<TypeIndex, 0> IndexMap;
 };
 
 } // end anonymous namespace
 
+const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
+
 Error TypeStreamMerger::visitTypeBegin(CVRecord<TypeLeafKind> &Rec) {
-#ifndef NDEBUG
-  BeginIndexMapSize = IndexMap.size();
-#endif
   return Error::success();
 }
 
 Error TypeStreamMerger::visitTypeEnd(CVRecord<TypeLeafKind> &Rec) {
-  assert(IndexMap.size() == BeginIndexMapSize + 1 &&
+  CurIndex = TypeIndex(CurIndex.getIndex() + 1);
+  if (!IsSecondPass)
+    assert(IndexMap.size() == slotForIndex(CurIndex) &&
            "visitKnownRecord should add one index map entry");
   return Error::success();
 }
 
 Error TypeStreamMerger::visitMemberEnd(CVMemberRecord &Rec) {
   return Error::success();
 }
 
+void TypeStreamMerger::addMapping(TypeIndex Idx) {
+  if (!IsSecondPass) {
+    assert(IndexMap.size() == slotForIndex(CurIndex) &&
+           "visitKnownRecord should add one index map entry");
+    IndexMap.push_back(Idx);
+  } else {
+    assert(slotForIndex(CurIndex) < IndexMap.size());
+    IndexMap[slotForIndex(CurIndex)] = Idx;
+  }
+}
+
 bool TypeStreamMerger::remapIndex(TypeIndex &Idx) {
   // Simple types are unchanged.
   if (Idx.isSimple())
     return true;
-  unsigned MapPos = Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
-  if (MapPos < IndexMap.size()) {
+
+  // Check if this type index refers to a record we've already translated
+  // successfully. If it refers to a type later in the stream or a record we
+  // had to defer, defer it until later pass.
+  unsigned MapPos = slotForIndex(Idx);
+  if (MapPos < IndexMap.size() && IndexMap[MapPos] != Untranslated) {
     Idx = IndexMap[MapPos];
     return true;
   }
 
+  // If this is the second pass and this index isn't in the map, then it points
+  // outside the current type stream, and this is a corrupt record.
+  if (IsSecondPass && MapPos >= IndexMap.size()) {
+    // FIXME: Print a more useful error. We can give the current record and the
+    // index that we think its pointing to.
+    LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
+  }
+
+  ++NumBadIndices;
+
   // This type index is invalid. Remap this to "not translated by cvpack",
   // and return failure.
-  Idx = TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct);
+  Idx = Untranslated;
   return false;
 }
 
 //----------------------------------------------------------------------------//
 // Item records
 //----------------------------------------------------------------------------//
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, FuncIdRecord &R) {
Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFunctionRecord &R) {
   bool Success = true;
   Success &= remapIndex(R.ReturnType);
   Success &= remapIndex(R.ClassType);
   Success &= remapIndex(R.ThisType);
   Success &= remapIndex(R.ArgumentList);
   return writeRecord(R, Success);
 }
 
-Error TypeStreamMerger::visitKnownRecord(CVType &, ArgListRecord &R) {
+Error TypeStreamMerger::visitKnownRecord(CVType &Type, ArgListRecord &R) {
   bool Success = true;
   for (TypeIndex &Arg : R.ArgIndices)
     Success &= remapIndex(Arg);
-  return writeRecord(R, Success);
+  if (auto EC = writeRecord(R, Success))
+    return EC;
+  return Error::success();
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, PointerRecord &R) {
   bool Success = true;
   Success &= remapIndex(R.ReferentType);
   if (R.isPointerToMember())
     Success &= remapIndex(R.MemberInfo->ContainingType);
   return writeRecord(R, Success);
Error TypeStreamMerger::visitKnownRecord(CVType &,
   bool Success = true;
   for (OneMethodRecord &Meth : R.Methods)
     Success &= remapIndex(Meth.Type);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, FieldListRecord &R) {
   // Visit the members inside the field list.
+  HadUntranslatedMember = false;
   FieldListBuilder.begin();
   CVTypeVisitor Visitor(*this);
   if (auto EC = Visitor.visitFieldListMemberStream(R.Data))
     return EC;
-  TypeIndex Index = FieldListBuilder.end();
-  IndexMap.push_back(Index);
+
+  // Write the record if we translated all field list members.
+  TypeIndex DestIdx = Untranslated;
+  if (!HadUntranslatedMember)
+    DestIdx = FieldListBuilder.end();
+  else
+    FieldListBuilder.reset();
+  addMapping(DestIdx);
+
   return Error::success();
 }
 
 //----------------------------------------------------------------------------//
 // Member records
 //----------------------------------------------------------------------------//
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,

 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          ListContinuationRecord &R) {
   return writeMember(R, remapIndex(R.ContinuationIndex));
 }
 
 Error TypeStreamMerger::visitUnknownType(CVType &Rec) {
   // We failed to translate a type. Translate this index as "not translated".
-  IndexMap.push_back(
-      TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct));
-  return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
+  addMapping(TypeIndex(SimpleTypeKind::NotTranslated));
+  return errorCorruptRecord();
 }
 
 Error TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
   assert(IndexMap.empty());
   TypeVisitorCallbackPipeline Pipeline;
   LastError = Error::success();
 
   TypeDeserializer Deserializer;
   Pipeline.addCallbackToPipeline(Deserializer);
   Pipeline.addCallbackToPipeline(*this);
 
   CVTypeVisitor Visitor(Pipeline);
   if (Handler)
     Visitor.addTypeServerHandler(*Handler);
 
   if (auto EC = Visitor.visitTypeStream(Types))
     return EC;
+
+  // If we found bad indices but no other errors, try doing another pass and see
+  // if we can resolve the indices that weren't in the map on the first pass.
+  // This may require multiple passes, but we should always make progress. MASM
+  // is the only known CodeView producer that makes type streams that aren't
+  // topologically sorted. The standard library contains MASM-produced objects,
+  // so this is important to handle correctly, but we don't have to be too
+  // efficient. MASM type streams are usually very small.
+  while (!*LastError && NumBadIndices > 0) {
+    unsigned BadIndicesRemaining = NumBadIndices;
+    IsSecondPass = true;
+    NumBadIndices = 0;
+    CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
+    if (auto EC = Visitor.visitTypeStream(Types))
+      return EC;
+
+    assert(NumBadIndices <= BadIndicesRemaining &&
+           "second pass found more bad indices");
+    if (!*LastError && NumBadIndices == BadIndicesRemaining) {
+      return llvm::make_error<CodeViewError>(
+          cv_error_code::corrupt_record, "input type graph contains cycles");
+    }
+  }
+
   IndexMap.clear();
 
   Error Ret = std::move(*LastError);
   LastError.reset();
   return Ret;
 }
 
 Error llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestIdStream,
                                        TypeTableBuilder &DestTypeStream,
                                        TypeServerHandler *Handler,
                                        const CVTypeArray &Types) {
   return TypeStreamMerger(DestIdStream, DestTypeStream, Handler)
       .mergeStream(Types);
 }

llvm/trunk/test/tools/llvm-readobj/codeview-merging-cycle.test

+; RUN: not llvm-readobj -codeview-merged-types %S/Inputs/codeview-cycle.obj 2>&1 | FileCheck %s
+
+; CHECK: Error{{.*}} input type graph contains cycles
+
+; To reproduce codeview-cycle.obj:
+; $ cat codeview-cycle.asm
+;       .model  flat, C
+;       .code
+; pfoo_list TYPEDEF PTR foo_list
+; foo_list STRUCT
+;       next pfoo_list ?
+;       data dd ?
+; foo_list ENDS
+;       public  foo
+; foo proc dst:ptr foo_list
+;       ret
+; foo   endp
+;       end
+; $ ml -c -Zi codeview-cycle.asm

llvm/trunk/test/tools/llvm-readobj/codeview-merging-unsorted.test

+; RUN: llvm-readobj -codeview %S/Inputs/codeview-unsorted.obj | FileCheck %s
+; RUN: llvm-readobj -codeview-merged-types %S/Inputs/codeview-unsorted.obj | FileCheck %s --check-prefix=MERGED
+
+; The input type stream has records that refer to later type indices in the same
+; stream:
+
+; CHECK: Pointer (0x1000)
+; CHECK: Struct (0x1001)
+; CHECK:   FieldList: {{.*}} (0x1002)
+; CHECK: FieldList (0x1002)
+; CHECK: Pointer (0x1003)
+; CHECK: Procedure (0x1004)
+; CHECK:   ArgListType: {{.*}} (0x1005)
+; CHECK: ArgList (0x1005)
+
+; MERGED: Pointer (0x1000)
+; MERGED: FieldList (0x1001)
+; MERGED: Struct (0x1002)
+; MERGED:   FieldList: {{.*}} (0x1001)
+; MERGED: Pointer (0x1003)
+; MERGED: ArgList (0x1004)
+; MERGED: Procedure (0x1005)
+; MERGED:   ArgListType: {{.*}} (0x1004)
+
+
+; To reproduce codeview-unsorted.obj:
+; $ cat codeview-unsorted.asm
+;       .model  flat, C
+;       .code
+; PBYTE TYPEDEF PTR BYTE
+; foo_list STRUCT
+;       next PBYTE ?
+;       data dd ?
+; foo_list ENDS
+;       public  foo
+; foo proc dst:ptr foo_list
+;       ret
+; foo   endp
+;       end
+; $ ml -c -Zi codeview-unsorted.asm

llvm/trunk/tools/llvm-readobj/COFFDumper.cpp

if (SectionName == ".debug$T") {
       CVTypeArray Types;
       BinaryStreamReader Reader(Stream);
       if (auto EC = Reader.readArray(Types, Reader.getLength())) {
         consumeError(std::move(EC));
         W.flush();
         error(object_error::parse_failed);
       }
 
-      if (auto EC = mergeTypeStreams(CVIDs, CVTypes, nullptr, Types)) {
-        consumeError(std::move(EC));
-        return error(object_error::parse_failed);
-      }
+      if (auto EC = mergeTypeStreams(CVIDs, CVTypes, nullptr, Types))
+        return error(std::move(EC));
     }
   }
 }
 
 void COFFDumper::printCodeViewTypeSection(StringRef SectionName,
                                           const SectionRef &Section) {
   ListScope D(W, "CodeViewTypes");
   W.printNumber("Section", SectionName, Obj->getSectionID(Section));
void llvm::dumpCodeViewMergedTypes(ScopedPrinter &Writer,
   TypeDatabase TypeDB;
   {
     ListScope S(Writer, "MergedTypeStream");
     CVTypeDumper CVTD(TypeDB);
     TypeDumpVisitor TDV(TypeDB, &Writer, opts::CodeViewSubsectionBytes);
     if (auto EC = CVTD.dump(
             {TypeBuf.str().bytes_begin(), TypeBuf.str().bytes_end()}, TDV)) {
       Writer.flush();
-      error(llvm::errorToErrorCode(std::move(EC)));
+      error(std::move(EC));
     }
   }
 
   // Flatten the id stream and print it next. The ID stream refers to names from
   // the type stream.
   SmallString<0> IDBuf;
   IDTable.ForEachRecord([&](TypeIndex TI, ArrayRef<uint8_t> Record) {
     IDBuf.append(Record.begin(), Record.end());
   });
 
   {
     ListScope S(Writer, "MergedIDStream");
     TypeDatabase IDDB;
     CVTypeDumper CVTD(IDDB);
     TypeDumpVisitor TDV(TypeDB, &Writer, opts::CodeViewSubsectionBytes);
     TDV.setItemDB(IDDB);
     if (auto EC = CVTD.dump(
             {IDBuf.str().bytes_begin(), IDBuf.str().bytes_end()}, TDV)) {
       Writer.flush();
-      error(llvm::errorToErrorCode(std::move(EC)));
+      error(std::move(EC));
     }
   }
 }