Force iteration over FieldDecls and RecordDecls in deterministic order.

[zturner]

Summary

Previously we were, in many places in the code, using a DenseMap<> to hold FieldDecls representing class members, and RecordDecls representing bases and virtual bases.

In some instances, we would try to copy records by iterating over their fields and bases and adding each one to a new AST. This yields a non-deterministic ordering of the results, and leads to invalid record layout. Specifically, clang expects field index order to be in offset order, and the field index order is determined by the order you add items to a record. So when synthesizing a new AST, you *must* add items in field offset order. Therefore, copying by iterating over a DenseMap of FieldDecls or RecordDecls for bases and inserting them this way yields invalid record layout.

This bug is present on all platforms and all ABIs, but was only surfaced on Windows with the MS ABI record layout because of extra checks and asserts present in MicrosoftRecordLayoutBuilder::layoutField. Also, this requirement of importing in a deterministic order applies to bases and virtual bases too, not just fields.

The fix employed here is to change all occurrences of DenseMap<A,B> as it pertains to ASTs to std::vector<std::pair<A, B>>. There were only a very few instances of anyone using the DenseMaps for lookup, and given the typical number of fields a class has, it seems like a reasonable tradeoff to ensure that this kind of problem can never happen again. A std::vector<> should also require less memory than a DenseMap. I'm not sure if there are tons of SymbolFileDWARF::LayoutInfos lying around in memory, but if there are this could have an impact on memory footprint too.

Since this problem was present everywhere it's unclear how -- if at all -- it was manifesting or what types of issues this might fix for everyone else. The problem may have been masked if ASLR was disabled or depending on what allocator was used. On Windows it definitely fixes a whole slew of test failures. I know Linux has been seeing some non-deterministic failures as well, so one of the Linux people shoudl see if this patch makes a difference.

[zturner]

source/Expression/ClangASTSource.cpp

1543 ↗

(On Diff #22407)

Since I didn't call it out specifically in the CL, this is the line that was introducing the non-determinism when a DenseMap is used.

It would be possible to fix this by only copying the elements of the DenseMap<> out to a temporary list and sorting the list, but since iterating in a non-deterministic order is perilous, I will propose this change first.

[amccarth]

Nice find.

source/Expression/ClangASTSource.cpp

1543 ↗

(On Diff #22407)

Nit: I assume fi was and abbreviation for "field iterator". Since this is no longer and iterator and just (a reference to) the field, perhaps rename it.

[rnk]

Nice! If you actually need fast lookup, you can use llvm::MapVector, but based on your analysis it looks like std::vector is more appropriate.

[ovyalov]

Do we need to use operator[] on vector? I'm wondering whether list can be used instead of vector.

source/Expression/ClangASTSource.cpp

1541 ↗

(On Diff #22407)

Minor thing - destination_list.reserve(source_list.size())

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2675 ↗

(On Diff #22407)

Could you use cbegin and replace such a long type name with sth like
auto pos = layout_info.field_offsets.cbegin(), end = layout_info.field_offsets.cend();

[zturner]

Fixed some of the issues that were pointed out. Will try to upload this tomorrow if there's no further comments.

[clayborg]

Adding Sean as a reviewer now that he is back.

[spyffe]

The abstract interface for ExternalASTSource has a layoutRecordType() function (llvm/tools/clang/include/clang/AST/ExternalASTSource.h):

virtual bool layoutRecordType(
    const RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
    llvm::DenseMap<const FieldDecl *, uint64_t> &FieldOffsets,
    llvm::DenseMap<const CXXRecordDecl *, CharUnits> &BaseOffsets,
    llvm::DenseMap<const CXXRecordDecl *, CharUnits> &VirtualBaseOffsets);

We're conforming to that. I'm concerned that by changing the signature of layoutRecordType() in LLDB, you're causing our version to not be called at all. Unless I'm missing something, this doesn't look like the right fix.

[spyffe]

As an aside, when laying out a RecordDecl, you have the ordering for its fields right in the RecordDecl. If MicrosoftRecordLayoutBuilder relying on the llvm::DenseMap for ordering, I think it's MicrosoftRecordLayoutBuilder that has the bug. By my understanding of how record layout works, it should only be using the map to go from fields/bases to offsets – nothing else.

[zturner]

This bug isn't specific to Microsoft layout. Clang as a general rule
requires fields to be added in offset order, and iterating over a dense map
doesn't give you that.

I'll let majnemer or rnk comment on the ExternalASTSource interface

[zturner]

Also the layout builder never gets the dense map. So Microsoft Layout
Builder doesn't know anything about the dense map. It's ClangASTSource that
iterates over the map, and all the layout builder sees is fields being
added in the wrong order

[zturner]

I see what you mean about the interface. I guess that settles that then,
the interface needs to be consistent. I'll add override keywords so the
compiler can catch that for me in the future.

But our implementation still needs to add fields in the correct order, so
iterating over the DenseMap is still not the right approach

[zturner]

I talked to some of the clang guys here and they said to go back to
DenseMaps to conform to the ExternalASTSource interface, but make sure you
iterate over fields and bases in offset order, which means sorting the list
before doing the insertion. So I will submit a patch to do that today.

lldb/trunk/include/lldb/Expression/ClangASTSource.h

 //===-- ClangASTSource.h ----------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef liblldb_ClangASTSource_h_
 #define liblldb_ClangASTSource_h_
 
 #include <set>
+#include <vector>
 
 #include "clang/Basic/IdentifierTable.h"
 #include "lldb/Symbol/ClangExternalASTSourceCommon.h"
 #include "lldb/Symbol/ClangASTImporter.h"
 #include "lldb/Symbol/ClangASTType.h"
 #include "lldb/Target/Target.h"
 
 #include "llvm/ADT/SmallSet.h"
 
+namespace clang
+{
+class CharUnits;
+class FieldDecl;
+}
+
 namespace lldb_private {
     
 //----------------------------------------------------------------------
 /// @class ClangASTSource ClangASTSource.h "lldb/Expression/ClangASTSource.h"
 /// @brief Provider for named objects defined in the debug info for Clang
 ///
 /// As Clang parses an expression, it may encounter names that are not
 /// defined inside the expression, including variables, functions, and
clang::Selector GetExternalSelector (uint32_t)  {   return clang::Selector();   }
     ///
     /// @param[in] Decls
     ///     A vector that is filled in with matching Decls.
     //------------------------------------------------------------------
     clang::ExternalLoadResult 
     FindExternalLexicalDecls (const clang::DeclContext *DC,
                               bool (*isKindWeWant)(clang::Decl::Kind),
                               llvm::SmallVectorImpl<clang::Decl*> &Decls);
-    
+    typedef std::vector<std::pair<const clang::FieldDecl *, uint64_t>> FieldOffsetList;
+    typedef std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> BaseOffsetList;
+
     //------------------------------------------------------------------
     /// Specify the layout of the contents of a RecordDecl.
     ///
     /// @param[in] Record
     ///     The record (in the parser's AST context) that needs to be
     ///     laid out.
     ///
     /// @param[out] Size
clang::Selector GetExternalSelector (uint32_t)  {   return clang::Selector();   }
     /// @param[in] VirtualBaseOffsets
     ///     A map that must be populated with pairs of the record's
     ///     C++ virtual base classes (in the parser's AST context, 
     ///     and only if the record is a CXXRecordDecl and has base
     ///     classes) and their offsets (measured in bytes).
     ///
     /// @return
     ///     True <=> the layout is valid.
-    //-----------------------------------------------------------------    
-    bool 
-    layoutRecordType(const clang::RecordDecl *Record,
-                     uint64_t &Size, 
-                     uint64_t &Alignment,
-                     llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets);
-    
+    //-----------------------------------------------------------------
+    bool layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                          FieldOffsetList &FieldOffsets, BaseOffsetList &BaseOffsets,
+                          BaseOffsetList &VirtualBaseOffsets);
     //------------------------------------------------------------------
     /// Complete a TagDecl.
     ///
     /// @param[in] Tag
     ///     The Decl to be completed in place.
     //------------------------------------------------------------------
     virtual void
     CompleteType (clang::TagDecl *Tag);
public:
             return m_original.CompleteType(Tag);
         }
         
         void 
         CompleteType (clang::ObjCInterfaceDecl *Class)
         {
             return m_original.CompleteType(Class);
         }
-        
-        bool 
-        layoutRecordType(const clang::RecordDecl *Record,
-                         uint64_t &Size, 
-                         uint64_t &Alignment,
-                         llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                         llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                         llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets)
+        bool
+        layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                         FieldOffsetList &FieldOffsets, BaseOffsetList &BaseOffsets, BaseOffsetList &VirtualBaseOffsets)
         {
             return m_original.layoutRecordType(Record,
                                                Size, 
                                                Alignment, 
                                                FieldOffsets, 
                                                BaseOffsets, 
                                                VirtualBaseOffsets);
         }

lldb/trunk/include/lldb/Symbol/ClangExternalASTSourceCallbacks.h

 
 class ClangExternalASTSourceCallbacks : public ClangExternalASTSourceCommon
 {
 public:
 
     typedef void (*CompleteTagDeclCallback)(void *baton, clang::TagDecl *);
     typedef void (*CompleteObjCInterfaceDeclCallback)(void *baton, clang::ObjCInterfaceDecl *);
     typedef void (*FindExternalVisibleDeclsByNameCallback)(void *baton, const clang::DeclContext *DC, clang::DeclarationName Name, llvm::SmallVectorImpl <clang::NamedDecl *> *results);
-    typedef bool (*LayoutRecordTypeCallback)(void *baton, 
-                                             const clang::RecordDecl *Record,
-                                             uint64_t &Size, 
-                                             uint64_t &Alignment,
-                                             llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                                             llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                                             llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets);
+    typedef bool (*LayoutRecordTypeCallback)(
+        void *baton, const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+        std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
 
     ClangExternalASTSourceCallbacks (CompleteTagDeclCallback tag_decl_callback,
                                      CompleteObjCInterfaceDeclCallback objc_decl_callback,
                                      FindExternalVisibleDeclsByNameCallback find_by_name_callback,
                                      LayoutRecordTypeCallback layout_record_type_callback,
                                      void *callback_baton) :
         m_callback_tag_decl (tag_decl_callback),
         m_callback_objc_decl (objc_decl_callback),
virtual clang::ExternalLoadResult
     FindExternalVisibleDeclsByName (const clang::DeclContext *decl_ctx,
                                     clang::DeclarationName decl_name);
     
     virtual void
     CompleteType (clang::TagDecl *tag_decl);
     
     virtual void
     CompleteType (clang::ObjCInterfaceDecl *objc_decl);
-    
-    bool 
-    layoutRecordType(const clang::RecordDecl *Record,
-                     uint64_t &Size, 
-                     uint64_t &Alignment,
-                     llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets);
+    bool layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                          std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
     void
     SetExternalSourceCallbacks (CompleteTagDeclCallback tag_decl_callback,
                                 CompleteObjCInterfaceDeclCallback objc_decl_callback,
                                 FindExternalVisibleDeclsByNameCallback find_by_name_callback,
                                 LayoutRecordTypeCallback layout_record_type_callback,
                                 void *callback_baton)
     {
         m_callback_tag_decl = tag_decl_callback;

lldb/trunk/source/Expression/ClangASTSource.cpp

do
                                                    *m_ast_context,
                                                    m_ast_importer,
                                                    interface_decl_from_runtime))
             return;
     }
     while(0);
 }
 
-typedef llvm::DenseMap <const FieldDecl *, uint64_t> FieldOffsetMap;
-typedef llvm::DenseMap <const CXXRecordDecl *, CharUnits> BaseOffsetMap;
-
 template <class D, class O>
 static bool
-ImportOffsetMap (llvm::DenseMap <const D*, O> &destination_map,
-                 llvm::DenseMap <const D*, O> &source_map,
-                 ClangASTImporter *importer,
+ImportOffsetList(std::vector<std::pair<const D *, O>> &destination_list,
+                 const std::vector<std::pair<const D *, O>> &source_list, ClangASTImporter *importer,
                  ASTContext &dest_ctx)
 {
-    typedef llvm::DenseMap <const D*, O> MapType;
+    typedef std::vector<std::pair<const D *, O>> ListType;
 
-    for (typename MapType::iterator fi = source_map.begin(), fe = source_map.end();
-         fi != fe;
-         ++fi)
+    for (const auto &fi : source_list)
     {
-        DeclFromUser <D> user_decl(const_cast<D*>(fi->first));
+        DeclFromUser<D> user_decl(const_cast<D *>(fi.first));
         DeclFromParser <D> parser_decl(user_decl.Import(importer, dest_ctx));
         if (parser_decl.IsInvalid())
             return false;
-        destination_map.insert(std::pair<const D *, O>(parser_decl.decl, fi->second));
+        destination_list.push_back(std::pair<const D *, O>(parser_decl.decl, fi.second));
     }
 
     return true;
 }
 
-template <bool IsVirtual> bool ExtractBaseOffsets (const ASTRecordLayout &record_layout,
-                                                   DeclFromUser<const CXXRecordDecl> &record,
-                                                   BaseOffsetMap &base_offsets)
-{
-    for (CXXRecordDecl::base_class_const_iterator
-            bi = (IsVirtual ? record->vbases_begin() : record->bases_begin()),
-            be = (IsVirtual ? record->vbases_end() : record->bases_end());
-         bi != be;
-         ++bi)
+template <bool IsVirtual>
+bool
+ExtractBaseOffsets(const ASTRecordLayout &record_layout, DeclFromUser<const CXXRecordDecl> &record,
+                   ClangASTSource::BaseOffsetList &base_offsets)
+{
+    for (const auto &base : (IsVirtual ? record->vbases() : record->bases()))
     {
-        if (!IsVirtual && bi->isVirtual())
+        if (!IsVirtual && base.isVirtual())
             continue;
 
-        const clang::Type *origin_base_type = bi->getType().getTypePtr();
+        const clang::Type *origin_base_type = base.getType().getTypePtr();
         const clang::RecordType *origin_base_record_type = origin_base_type->getAs<RecordType>();
 
         if (!origin_base_record_type)
             return false;
 
         DeclFromUser <RecordDecl> origin_base_record(origin_base_record_type->getDecl());
 
         if (origin_base_record.IsInvalid())
             return false;
 
         DeclFromUser <CXXRecordDecl> origin_base_cxx_record(DynCast<CXXRecordDecl>(origin_base_record));
 
         if (origin_base_cxx_record.IsInvalid())
             return false;
 
         CharUnits base_offset;
 
         if (IsVirtual)
             base_offset = record_layout.getVBaseClassOffset(origin_base_cxx_record.decl);
         else
             base_offset = record_layout.getBaseClassOffset(origin_base_cxx_record.decl);
 
-        base_offsets.insert(std::pair<const CXXRecordDecl *, CharUnits>(origin_base_cxx_record.decl, base_offset));
+        base_offsets.push_back(std::make_pair(origin_base_cxx_record.decl, base_offset));
     }
 
     return true;
 }
 
 bool
-ClangASTSource::layoutRecordType(const RecordDecl *record,
-                                 uint64_t &size,
-                                 uint64_t &alignment,
-                                 FieldOffsetMap &field_offsets,
-                                 BaseOffsetMap &base_offsets,
-                                 BaseOffsetMap &virtual_base_offsets)
+ClangASTSource::layoutRecordType(const RecordDecl *record, uint64_t &size, uint64_t &alignment,
+                                 FieldOffsetList &field_offsets, BaseOffsetList &base_offsets,
+                                 BaseOffsetList &virtual_base_offsets)
 {
     ClangASTMetrics::RegisterRecordLayout();
 
     static unsigned int invocation_id = 0;
     unsigned int current_id = invocation_id++;
 
     Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_EXPRESSIONS));
 
     if (log)
         log->Printf("LayoutRecordType[%u] on (ASTContext*)%p for (RecordDecl*)%p [name = '%s']",
                     current_id, static_cast<void*>(m_ast_context),
                     static_cast<const void*>(record),
                     record->getNameAsString().c_str());
 
     DeclFromParser <const RecordDecl> parser_record(record);
     DeclFromUser <const RecordDecl> origin_record(parser_record.GetOrigin(m_ast_importer));
 
     if (origin_record.IsInvalid())
         return false;
 
-    FieldOffsetMap origin_field_offsets;
-    BaseOffsetMap origin_base_offsets;
-    BaseOffsetMap origin_virtual_base_offsets;
+    FieldOffsetList origin_field_offsets;
+    BaseOffsetList origin_base_offsets;
+    BaseOffsetList origin_virtual_base_offsets;
 
     ClangASTContext::GetCompleteDecl(&origin_record->getASTContext(), const_cast<RecordDecl*>(origin_record.decl));
 
     if (!origin_record.decl->getDefinition())
         return false;
 
     const ASTRecordLayout &record_layout(origin_record->getASTContext().getASTRecordLayout(origin_record.decl));
 
     int field_idx = 0, field_count = record_layout.getFieldCount();
 
-    for (RecordDecl::field_iterator fi = origin_record->field_begin(), fe = origin_record->field_end();
-         fi != fe;
-         ++fi)
+    origin_field_offsets.reserve(field_count);
+    for (const auto &field : origin_record->fields())
     {
         if (field_idx >= field_count)
             return false; // Layout didn't go well.  Bail out.
 
         uint64_t field_offset = record_layout.getFieldOffset(field_idx);
 
-        origin_field_offsets.insert(std::pair<const FieldDecl *, uint64_t>(*fi, field_offset));
+        origin_field_offsets.push_back(std::pair<const FieldDecl *, uint64_t>(field, field_offset));
 
         field_idx++;
     }
 
     ASTContext &parser_ast_context(record->getASTContext());
 
     DeclFromUser <const CXXRecordDecl> origin_cxx_record(DynCast<const CXXRecordDecl>(origin_record));
 
     if (origin_cxx_record.IsValid())
     {
         if (!ExtractBaseOffsets<false>(record_layout, origin_cxx_record, origin_base_offsets) ||
             !ExtractBaseOffsets<true>(record_layout, origin_cxx_record, origin_virtual_base_offsets))
             return false;
     }
 
-    if (!ImportOffsetMap(field_offsets, origin_field_offsets, m_ast_importer, parser_ast_context) ||
-        !ImportOffsetMap(base_offsets, origin_base_offsets, m_ast_importer, parser_ast_context) ||
-        !ImportOffsetMap(virtual_base_offsets, origin_virtual_base_offsets, m_ast_importer, parser_ast_context))
+    if (!ImportOffsetList(field_offsets, origin_field_offsets, m_ast_importer, parser_ast_context) ||
+        !ImportOffsetList(base_offsets, origin_base_offsets, m_ast_importer, parser_ast_context) ||
+        !ImportOffsetList(virtual_base_offsets, origin_virtual_base_offsets, m_ast_importer, parser_ast_context))
         return false;
 
     size = record_layout.getSize().getQuantity() * m_ast_context->getCharWidth();
     alignment = record_layout.getAlignment().getQuantity() * m_ast_context->getCharWidth();
 
     if (log)
     {
         log->Printf("LRT[%u] returned:", current_id);
         log->Printf("LRT[%u]   Original = (RecordDecl*)%p", current_id,
                     static_cast<const void*>(origin_record.decl));
         log->Printf("LRT[%u]   Size = %" PRId64, current_id, size);
         log->Printf("LRT[%u]   Alignment = %" PRId64, current_id, alignment);
         log->Printf("LRT[%u]   Fields:", current_id);
         for (RecordDecl::field_iterator fi = record->field_begin(), fe = record->field_end();
              fi != fe;
              ++fi)
         {
-            log->Printf("LRT[%u]     (FieldDecl*)%p, Name = '%s', Offset = %" PRId64 " bits",
-                        current_id, static_cast<void*>(*fi),
-                        fi->getNameAsString().c_str(), field_offsets[*fi]);
+
+            log->Printf("LRT[%u]     (FieldDecl*)%p, Name = '%s', Offset = %" PRId64 " bits", current_id,
+                        static_cast<void *>(*fi), fi->getNameAsString().c_str(),
+                        record_layout.getFieldOffset(fi->getFieldIndex()));
         }
         DeclFromParser <const CXXRecordDecl> parser_cxx_record = DynCast<const CXXRecordDecl>(parser_record);
         if (parser_cxx_record.IsValid())
         {
             log->Printf("LRT[%u]   Bases:", current_id);
             for (CXXRecordDecl::base_class_const_iterator bi = parser_cxx_record->bases_begin(), be = parser_cxx_record->bases_end();
                  bi != be;
                  ++bi)
             {
                 bool is_virtual = bi->isVirtual();
 
                 QualType base_type = bi->getType();
                 const RecordType *base_record_type = base_type->getAs<RecordType>();
                 DeclFromParser <RecordDecl> base_record(base_record_type->getDecl());
                 DeclFromParser <CXXRecordDecl> base_cxx_record = DynCast<CXXRecordDecl>(base_record);
 
-                log->Printf("LRT[%u]     %s(CXXRecordDecl*)%p, Name = '%s', Offset = %" PRId64 " chars",
-                            current_id, (is_virtual ? "Virtual " : ""),
-                            static_cast<void*>(base_cxx_record.decl),
-                            base_cxx_record.decl->getNameAsString().c_str(),
-                            (is_virtual
-                                ? virtual_base_offsets[base_cxx_record.decl].getQuantity()
-                                : base_offsets[base_cxx_record.decl].getQuantity()));
+                clang::CharUnits base_offset = is_virtual ? record_layout.getVBaseClassOffset(base_cxx_record.decl)
+                                                          : record_layout.getBaseClassOffset(base_cxx_record.decl);
+                log->Printf("LRT[%u]     %s(CXXRecordDecl*)%p, Name = '%s', Offset = %" PRId64 " chars", current_id,
+                            (is_virtual ? "Virtual " : ""), static_cast<void *>(base_cxx_record.decl),
+                            base_cxx_record.decl->getNameAsString().c_str(), base_offset);
             }
         }
         else
         {
             log->Printf("LRD[%u]   Not a CXXRecord, so no bases", current_id);
         }
     }
 

lldb/trunk/source/Plugins/LanguageRuntime/ObjC/AppleObjCRuntime/AppleObjCDeclVendor.cpp

CompleteType (clang::ObjCInterfaceDecl *interface_decl)
             log->Printf("  [CT] After:");
             ASTDumper dumper((clang::Decl*)interface_decl);
             dumper.ToLog(log, "    [CT] ");
         }
         return;
     }
 
     bool
-    layoutRecordType(const clang::RecordDecl *Record,
-                     uint64_t &Size,
-                     uint64_t &Alignment,
-                     llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets)
+    layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                     std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets)
     {
         return false;
     }
 
     void StartTranslationUnit (clang::ASTConsumer *Consumer)
     {
         clang::TranslationUnitDecl *translation_unit_decl = m_decl_vendor.m_ast_ctx.getASTContext()->getTranslationUnitDecl();
         translation_unit_decl->setHasExternalVisibleStorage();

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

public:
     CompleteObjCInterfaceDecl (void *baton, clang::ObjCInterfaceDecl *);
     
     static void
     FindExternalVisibleDeclsByName (void *baton,
                                     const clang::DeclContext *DC,
                                     clang::DeclarationName Name,
                                     llvm::SmallVectorImpl <clang::NamedDecl *> *results);
 
-    static bool 
-    LayoutRecordType (void *baton, 
-                      const clang::RecordDecl *record_decl,
-                      uint64_t &size, 
-                      uint64_t &alignment,
-                      llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets);
-
-    bool 
-    LayoutRecordType (const clang::RecordDecl *record_decl,
-                      uint64_t &size, 
-                      uint64_t &alignment,
-                      llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets);
+    static bool
+    LayoutRecordType(void *baton, const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+                     std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
+
+    bool LayoutRecordType(const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+                          std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
 
     struct LayoutInfo
     {
         LayoutInfo () :
             bit_size(0),
             alignment(0),
             field_offsets(),
             base_offsets(),
             vbase_offsets()
         {
         }
         uint64_t bit_size;
         uint64_t alignment;
-        llvm::DenseMap <const clang::FieldDecl *, uint64_t> field_offsets;
-        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> base_offsets;
-        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> vbase_offsets;
+        std::vector<std::pair<const clang::FieldDecl *, uint64_t>> field_offsets;
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> base_offsets;
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> vbase_offsets;
     };
     //------------------------------------------------------------------
     // PluginInterface protocol
     //------------------------------------------------------------------
     virtual lldb_private::ConstString
     GetPluginName();
 
     virtual uint32_t

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

for (die = parent_die->GetFirstChild(); die != NULL; die = die->GetSibling())
                                         }
                                         
                                         if (anon_field_info.IsValid())
                                         {
                                             clang::FieldDecl *unnamed_bitfield_decl = class_clang_type.AddFieldToRecordType (NULL,
                                                                                                                              GetClangASTContext().GetBuiltinTypeForEncodingAndBitSize(eEncodingSint, word_width),
                                                                                                                              accessibility,
                                                                                                                              anon_field_info.bit_size);
-                                            
-                                            layout_info.field_offsets.insert(std::make_pair(unnamed_bitfield_decl, anon_field_info.bit_offset));
+                                            layout_info.field_offsets.push_back(
+                                                std::make_pair(unnamed_bitfield_decl, anon_field_info.bit_offset));
                                         }
                                     }
                                     last_field_info = this_field_info;
                                 }
                                 else
                                 {
                                     last_field_info.Clear();
                                 }
for (die = parent_die->GetFirstChild(); die != NULL; die = die->GetSibling())
                                 }
                                 
                                 field_decl = class_clang_type.AddFieldToRecordType (name,
                                                                                     member_clang_type,
                                                                                     accessibility,
                                                                                     bit_size);
                                 
                                 GetClangASTContext().SetMetadataAsUserID (field_decl, MakeUserID(die->GetOffset()));
-                                
-                                layout_info.field_offsets.insert(std::make_pair(field_decl, field_bit_offset));
-
+                                layout_info.field_offsets.push_back(std::make_pair(field_decl, field_bit_offset));
                             }
                             else
                             {
                                 if (name)
                                     GetObjectFile()->GetModule()->ReportError ("0x%8.8" PRIx64 ": DW_TAG_member '%s' refers to type 0x%8.8" PRIx64 " which was unable to be parsed",
                                                                                MakeUserID(die->GetOffset()),
                                                                                name,
                                                                                encoding_uid);
for (die = parent_die->GetFirstChild(); die != NULL; die = die->GetSibling())
                             // in memory. the DW_AT_data_member_location for a virtual base class looks like:
                             //      DW_AT_data_member_location( DW_OP_dup, DW_OP_deref, DW_OP_constu(0x00000018), DW_OP_minus, DW_OP_deref, DW_OP_plus )
                             // Given this, there is really no valid response we can give to clang for virtual base
                             // class offsets, and this should eventually be removed from LayoutRecordType() in the external
                             // AST source in clang.
                         }
                         else
                         {
-                            layout_info.base_offsets.insert(std::make_pair(base_class_clang_type.GetAsCXXRecordDecl(),
-                                                                           clang::CharUnits::fromQuantity(member_byte_offset)));
+                            layout_info.base_offsets.push_back(
+                                std::make_pair(base_class_clang_type.GetAsCXXRecordDecl(),
                         }
                     }
                 }
             }
             break;
 
         default:
             break;
case DW_TAG_class_type:
                                                                   static_cast<void*>(clang_type.GetOpaqueQualType()),
                                                                   static_cast<void*>(record_decl),
                                                                   layout_info.bit_size,
                                                                   layout_info.alignment,
                                                                   static_cast<uint32_t>(layout_info.field_offsets.size()),
                                                                   static_cast<uint32_t>(layout_info.base_offsets.size()),
                                                                   static_cast<uint32_t>(layout_info.vbase_offsets.size()));
 
-                        uint32_t idx;
-                        {
-                        llvm::DenseMap <const clang::FieldDecl *, uint64_t>::const_iterator pos, end = layout_info.field_offsets.end();
-                        for (idx = 0, pos = layout_info.field_offsets.begin(); pos != end; ++pos, ++idx)
-                        {
-                            GetObjectFile()->GetModule()->LogMessage (log,
-                                                                      "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) field[%u] = { bit_offset=%u, name='%s' }",
-                                                                      static_cast<void*>(clang_type.GetOpaqueQualType()),
-                                                                      idx,
-                                                                      static_cast<uint32_t>(pos->second),
-                                                                      pos->first->getNameAsString().c_str());
-                        }
-                        }
-
-                        {
-                        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits>::const_iterator base_pos, base_end = layout_info.base_offsets.end();
-                        for (idx = 0, base_pos = layout_info.base_offsets.begin(); base_pos != base_end; ++base_pos, ++idx)
+                        for (const auto &entry : layout_info.field_offsets)
                         {
-                            GetObjectFile()->GetModule()->LogMessage (log,
-                                                                      "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) base[%u] = { byte_offset=%u, name='%s' }",
-                                                                      clang_type.GetOpaqueQualType(),
-                                                                      idx,
-                                                                      (uint32_t)base_pos->second.getQuantity(),
-                                                                      base_pos->first->getNameAsString().c_str());
-                        }
-                        }
-                        {
-                        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits>::const_iterator vbase_pos, vbase_end = layout_info.vbase_offsets.end();
-                        for (idx = 0, vbase_pos = layout_info.vbase_offsets.begin(); vbase_pos != vbase_end; ++vbase_pos, ++idx)
-                        {
-                            GetObjectFile()->GetModule()->LogMessage (log,
-                                                                      "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) vbase[%u] = { byte_offset=%u, name='%s' }",
-                                                                      static_cast<void*>(clang_type.GetOpaqueQualType()),
-                                                                      idx,
-                                                                      static_cast<uint32_t>(vbase_pos->second.getQuantity()),
-                                                                      vbase_pos->first->getNameAsString().c_str());
-                        }
+                            GetObjectFile()->GetModule()->LogMessage(
+                                log, "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) field[%u] = "
+                                     "{ bit_offset=%u, name='%s' }",
+                                static_cast<void *>(clang_type.GetOpaqueQualType()), entry.first->getFieldIndex(),
+                                static_cast<uint32_t>(entry.second), entry.first->getNameAsString().c_str());
+                        }
+
+                        uint32_t idx = 0;
+                        for (const auto &entry : layout_info.base_offsets)
+                        {
+                            GetObjectFile()->GetModule()->LogMessage(
+                                log, "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) base[%u] = { "
+                                     "byte_offset=%u, name='%s' }",
+                                clang_type.GetOpaqueQualType(), idx, (uint32_t)entry.second.getQuantity(),
+                                entry.first->getNameAsString().c_str());
+                            ++idx;
+                        }
+
+                        idx = 0;
+                        for (const auto &entry : layout_info.vbase_offsets)
+                        {
+                            GetObjectFile()->GetModule()->LogMessage(
+                                log, "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) vbase[%u] = "
+                                     "{ byte_offset=%u, name='%s' }",
+                                static_cast<void *>(clang_type.GetOpaqueQualType()), idx,
+                                static_cast<uint32_t>(entry.second.getQuantity()),
+                                entry.first->getNameAsString().c_str());
+                            ++idx;
                         }
                     }
                     m_record_decl_to_layout_map.insert(std::make_pair(record_decl, layout_info));
                 }
             }
         }
 
         return (bool)clang_type;
case clang::Decl::TranslationUnit:
             symbol_file_dwarf->SearchDeclContext (decl_context, decl_name.getAsString().c_str(), results);
         }
         break;
     default:
         break;
     }
 }
 
-bool 
-SymbolFileDWARF::LayoutRecordType (void *baton, 
-                                   const clang::RecordDecl *record_decl,
-                                   uint64_t &size, 
-                                   uint64_t &alignment,
-                                   llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets)
+bool
+SymbolFileDWARF::LayoutRecordType(void *baton, const clang::RecordDecl *record_decl, uint64_t &size,
+                                  std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &field_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &base_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &vbase_offsets)
 {
     SymbolFileDWARF *symbol_file_dwarf = (SymbolFileDWARF *)baton;
     return symbol_file_dwarf->LayoutRecordType (record_decl, size, alignment, field_offsets, base_offsets, vbase_offsets);
 }
 
-
-bool 
-SymbolFileDWARF::LayoutRecordType (const clang::RecordDecl *record_decl,
-                                   uint64_t &bit_size, 
-                                   uint64_t &alignment,
-                                   llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets)
+bool
+SymbolFileDWARF::LayoutRecordType(const clang::RecordDecl *record_decl, uint64_t &bit_size, uint64_t &alignment,
+                                  std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &field_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &base_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &vbase_offsets)
 {
     Log *log (LogChannelDWARF::GetLogIfAll(DWARF_LOG_DEBUG_INFO));
     RecordDeclToLayoutMap::iterator pos = m_record_decl_to_layout_map.find (record_decl);
     bool success = false;
     base_offsets.clear();
     vbase_offsets.clear();
     if (pos != m_record_decl_to_layout_map.end())
     {

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

public:
     //------------------------------------------------------------------
     // ClangASTContext callbacks for external source lookups.
     //------------------------------------------------------------------
     static void
     CompleteTagDecl (void *baton, clang::TagDecl *);
     
     static void
     CompleteObjCInterfaceDecl (void *baton, clang::ObjCInterfaceDecl *);
-    
-    static bool 
-    LayoutRecordType (void *baton, 
-                      const clang::RecordDecl *record_decl,
-                      uint64_t &size, 
-                      uint64_t &alignment,
-                      llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets);
-
+    static bool
+    LayoutRecordType(void *baton, const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+                     std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
 
     //------------------------------------------------------------------
     // PluginInterface protocol
     //------------------------------------------------------------------
     virtual lldb_private::ConstString
     GetPluginName();
 
     virtual uint32_t

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp

if (clang_type)
             {
                 oso_dwarf->ResolveClangOpaqueTypeDefinition (clang_type);
                 return;
             }
         }
     }
 }
 
-bool 
-SymbolFileDWARFDebugMap::LayoutRecordType (void *baton, 
-                                           const clang::RecordDecl *record_decl,
-                                           uint64_t &size, 
-                                           uint64_t &alignment,
-                                           llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                                           llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                                           llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets)
+bool
+SymbolFileDWARFDebugMap::LayoutRecordType(
+    void *baton, const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+    std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &field_offsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &base_offsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &vbase_offsets)
 {
     SymbolFileDWARFDebugMap *symbol_file_dwarf = (SymbolFileDWARFDebugMap *)baton;
     SymbolFileDWARF *oso_dwarf;
     for (uint32_t oso_idx = 0; ((oso_dwarf = symbol_file_dwarf->GetSymbolFileByOSOIndex (oso_idx)) != NULL); ++oso_idx)
     {
         if (oso_dwarf->LayoutRecordType (record_decl, size, alignment, field_offsets, base_offsets, vbase_offsets))
             return true;
     }

lldb/trunk/source/Symbol/ClangExternalASTSourceCallbacks.cpp

 
 void
 ClangExternalASTSourceCallbacks::CompleteType (ObjCInterfaceDecl *objc_decl)
 {
     if (m_callback_objc_decl)
         m_callback_objc_decl (m_callback_baton, objc_decl);
 }
 
-bool 
-ClangExternalASTSourceCallbacks::layoutRecordType(const clang::RecordDecl *Record,
-                                                  uint64_t &Size, 
-                                                  uint64_t &Alignment,
-                                                  llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                                                  llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                                                  llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets)
+bool
+ClangExternalASTSourceCallbacks::layoutRecordType(
+    const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+    std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets)
 {
     if (m_callback_layout_record_type)
         return m_callback_layout_record_type(m_callback_baton,
                                              Record,
                                              Size, 
                                              Alignment, 
                                              FieldOffsets, 
                                              BaseOffsets, 
                                              VirtualBaseOffsets);
     
     return false;
 }
 

lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/vbool/TestDataFormatterLibcxxVBool.py

class LibcxxVBoolDataFormatterTestCase(TestBase):
     @unittest2.skipUnless(sys.platform.startswith("darwin"), "requires Darwin")
     @dsym_test
     def test_with_dsym_and_run_command(self):
         """Test data formatter commands."""
         self.buildDsym()
         self.data_formatter_commands()
 
     @skipIfLinux # No standard locations for libc++ on Linux, so skip for now 
-    @skipIfWindows # http://llvm.org/pr21800
+    @skipIfWindows # Windows doesn't have libcxx
     @dwarf_test
     def test_with_dwarf_and_run_command(self):
         """Test data formatter commands."""
         self.buildDwarf()
         self.data_formatter_commands()
 
     def setUp(self):
         # Call super's setUp().

lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libstdcpp/vbool/TestDataFormatterStdVBool.py

class StdVBoolDataFormatterTestCase(TestBase):
     @skipIfDarwin
     def test_with_dsym_and_run_command(self):
         """Test data formatter commands."""
         self.buildDsym()
         self.data_formatter_commands()
 
     @expectedFailureFreeBSD("llvm.org/pr20548") # fails to build on lab.llvm.org buildbot
     @dwarf_test
-    @skipIfWindows # http://llvm.org/pr21800
     @skipIfDarwin
     def test_with_dwarf_and_run_command(self):
         """Test data formatter commands."""
         self.buildDwarf()
         self.data_formatter_commands()
 
     def setUp(self):
         # Call super's setUp().

lldb/trunk/test/lang/c/bitfields/TestBitfields.py

class BitfieldsTestCase(TestBase):
     @python_api_test
     @dsym_test
     def test_with_dsym_and_python_api(self):
         """Use Python APIs to inspect a bitfields variable."""
         self.buildDsym()
         self.bitfields_variable_python()
 
     @dwarf_test
-    @unittest2.skipIf(sys.platform.startswith("win32"), "BitFields exhibit crashes in record layout on Windows (http://llvm.org/pr21800)")
     def test_with_dwarf_and_run_command(self):
         """Test 'frame variable ...' on a variable with bitfields."""
         self.buildDwarf()
         self.bitfields_variable()
 
     @python_api_test
     @dwarf_test
-    @unittest2.skipIf(sys.platform.startswith("win32"), "BitFields exhibit crashes in record layout on Windows (http://llvm.org/pr21800)")
     @expectedFailureGcc # GCC (4.6/4.7) generates incorrect code with unnamed bitfields.
     def test_with_dwarf_and_python_api(self):
         """Use Python APIs to inspect a bitfields variable."""
         self.buildDwarf()
         self.bitfields_variable_python()
 
     def setUp(self):
         # Call super's setUp().