Add iterator support to DWARFDie to allow child DIE iteration.

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFDie.h

46

Probably best to define != in terms of ==, or the other way around:

return !(*this == RHS);

(also, I generally suggest that any op overload that can be a non-member should be a non-member: http://stackoverflow.com/questions/4421706/operator-overloading/4421729#4421729 )

& is this clang-formatted? (I'm surprised by the space after the operator keyword)

375

iterator() = default;

376

If DWARFDie is cheap enough to copy into a member of an iterator it's probably cheap enough to pass by value here.

383–384

Does the facade provide a way to only have to implement one of these two?

lib/DebugInfo/DWARF/DWARFDie.cpp

448–450

This could probably be inline - begin/end wouldn't be bad as inline definitions either.

tools/dsymutil/DwarfLinker.cpp

1800–1801

When can a child be null? Oh, we're still leaving null as a child in the iteration. That seems really weird.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1131–1138

This seems like more testing than I'd expect, given the code change.

If you want to exercise the same cases for iterator accessors as for the other accessors (could we remove the other accessors (getChild/getSibling) & just rely on iteration instead?) - then perhaps a parameterized test.

Otherwise I'd expect only some fairly brief testing that iterators appear to work - no need to redundantly test the cases that are interesting for getChild/getSibling.

1199–1204

Can you create a NULL DWARFDie object directly & test that separately (in a separate test function)?

1202–1203

can use x->y rather than (*x).y, hopefully

1206–1212

Split this out as a separate test function

[clayborg]

lib/DebugInfo/DWARF/DWARFDie.cpp

450

I can inline children(), but not begin() and end() since they use the iterator class which must be forward declared since it has a member variable:

DWARFDie Die;

tools/dsymutil/DwarfLinker.cpp

1800–1801

Yeah, we currently want it there for dumping, but not for real world use. Should we add a "bool IncludeNull" as a parameter to the children function to allow clients to choose?

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1138

ok, I can simplify and remove B1, B2, C, C1 and D.

1202–1203

I currently return a DWARFDie instance from the operator * for DWARFDie::iterator as I didn't want clients to modify the DWARFDie in the iterator by returning it by reference since it is what controls the iteration. This makes the -> operator not work as it takes the address of the returned DWARFDie and causes a compile error. Should we just have "DWARFDie::iterator operator*" return a reference to the contained item? I didn't like either approach.

1204

No, you can't get a NULL die without creating DWARF for it, so this should probably stay here.

1212

Why? this is testing the iterators and their functionality.

[clayborg]

Addressed inline comments.

[clayborg]

Marked things as done.

[clayborg]

• Inlined DWARFDie::iterator::begin(), DWARFDie::iterator::end() and DWARFDie::iterator::children()
• Don't include NULL DIE when using DWARFDie::iterator as most clients want this behavior
• Simplify tests for iterators to bare minimum

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFDie.h

389–391

I think this inconsistency is going to be confusing to users (I suspect the right thing is to only provide the iterator and don't provide the sibling API to users at all - and have the dumpers reconstitute the NULL dies for their own needs)

389–391

I'm guessing this will have problems with a present yet zero-length child list? (in that case the children() iteration would include the null die, since this check isn't done on construction, only on increment)

397

If you have op* return a reference (as it's meant to to conform to the iterator concept in the C++ standard) do you still need to write op->, or do you get that for free from the facade?

410–412

Probably just put this one directly inline in the class, since it can be

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1164–1170

Testing that they're equal should be sufficient - it's certainly not necessary to define or test what happens when an end iterator is deferenced.

[clayborg]

Fixed DWARFDie::iterator to skip NULL DIE if it is initialized with one.

[clayborg]

include/llvm/DebugInfo/DWARF/DWARFDie.h

391

I would rather not tackle reconstituting the NULL Die in this patch. I would rather do that if we remove the NULL dies. I think it is fair to say that when iterating across the children that we skip the NULL DIEs. I can fix the issue where we have only a NULL DIE as the only child.

397

If I return a "const DWARFDie &" from operator* I get:

/Volumes/Data/Users/gclayton/Documents/src/llvm/tot/llvm/include/llvm/ADT/iterator.h:138:12: error: cannot initialize return object of type 'llvm::DWARFDie *' with an rvalue of type 'const llvm::DWARFDie *'

For the following code in iterator.h:

PointerT operator->() const {
  return &static_cast<const DerivedT *>(this)->operator*();
}

If I make operator* return a "DWARFDie &" then it works and I can remove operator->:

DWARFDie &operator*() const { return const_cast<DWARFDie &>(Die); }

Without the cast it complains about a const function converting to a non const DWARFDie &. Which solution do you prefer?

410–412

It can't it needs to know what a DWARFDie::iterator is. I tried but got a compile error.

[clayborg]

Changed over to using "const DWARFDie" as the template parameter to iterator_facade_base so we don't have to override the operator->.

All issues should be resolved.

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFDie.h

392

Is this tested?

[clayborg]

Added a test to test Null DIEs being constructed into a DWARFDie::iterator to ensure it skips the NULL die and is the same as the end iterator.

[clayborg]

Next I will get back to removing the NULL dies as a patch to clean things up.

include/llvm/DebugInfo/DWARF/DWARFDie.h

392

I can add a test for it.

[dblaikie]

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1210–1228

I would expect this test case (or the one above (TestChildIterators)) to have a DIE with a zero length children list, rather than the explicit test at the end here which looks more like it's testing the internals of DWARFDie::iterator (that iterator(DWARFDie) ctor should probably not be public and instead only accessible from DWARFDie).

Is there a way to create a test that parses a DIE with a zero-length (but present) child list instead? Perhaps if it's not possible with the DWARF APIs we have, Chris Bieneman's yaml2obj might be up to the task.

[clayborg]

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1228

It isn't possible with the DWARF APIs currently without adding code that no one would want.

I was able to use DwarfGenerator to generate a DWARF file that was close that I saved to disk. I then used obj2yaml to make a yaml file, edited it and got what we need:

--- !mach-o
FileHeader:      
  magic:           0xFEEDFACF
  cputype:         0x01000007
  cpusubtype:      0x00000003
  filetype:        0x00000001
  ncmds:           2
  sizeofcmds:      248
  flags:           0x00000000
  reserved:        0x00000000
LoadCommands:    
  - cmd:             LC_SEGMENT_64
    cmdsize:         232
    segname:         ''
    vmaddr:          0
    vmsize:          27
    fileoff:         280
    filesize:        27
    maxprot:         7
    initprot:        7
    nsects:          2
    flags:           0
    Sections:        
      - sectname:        __debug_abbrev
        segname:         __DWARF
        addr:            0x0000000000000000
        size:            5
        offset:          0x00000118
        align:           0
        reloff:          0x00000000
        nreloc:          0
        flags:           0x02000000
        reserved1:       0x00000000
        reserved2:       0x00000000
        reserved3:       0x00000000
      - sectname:        __debug_info
        segname:         __DWARF
        addr:            0x000000000000000D
        size:            14
        offset:          0x00000125
        align:           0
        reloff:          0x00000000
        nreloc:          0
        flags:           0x02000000
        reserved1:       0x00000000
        reserved2:       0x00000000
        reserved3:       0x00000000
  - cmd:             LC_VERSION_MIN_MACOSX
    cmdsize:         16
    version:         1048576
    sdk:             0
DWARF:           
  debug_abbrev:    
    - Code:            0x00000001
      Tag:             DW_TAG_compile_unit
      Children:        DW_CHILDREN_yes
      Attributes:      
  debug_info:      
    - Length:          10
      Version:         4
      AbbrOffset:      0
      AddrSize:        8
      Entries:         
        - AbbrCode:        0x00000001
          Values:          
        - AbbrCode:        0x00000000
          Values:          
...

Are you OK if I have this text in a "const char *" variable and use the yaml2obj APIs to create an in memory file and then parse that DWARF and then test this? I can't really use FileCheck to test this internal iteration API. Let me know if you are ok with this approach?

[clayborg]

Looks like the guts to yaml2obj is only available as a command line tool and won't be available to use in the DWARF unit test binary.

[clayborg]

Are there any unit tests that spawn child processes to do work? That is what I would need to do to make this work.

[clayborg]

Fixed the DIE class to allow it generate an abbreviation that says the DIE has children even when it doesn't. This allows us to properly test the child iteration for DIEs that say they have kids, but don't.

[clayborg]

Added the ability to generate a DIE with children even when it doesn't turned out to be pretty easy.

[dblaikie]

One minor comment.

Also would still love to hear from Chris about testing more interesting cases of non-trivial DWARF and API interactions. I mean perhaps we'll end up with all parsing failures testable with llvm-dwarfdump and something like obj2yaml, then all API interactions we'll test with the DWARF generation APIs and make sure they can express all valid DWARF. (though I'm wondering at that point if it wouldn't be better for us to just create the DWARF objects directly - in fact, in this case we could do that, perhaps - rather than parsing DWARF, we could just create the DWARF parser API objects directly and check that the accessors all work, etc)

unittests/DebugInfo/DWARF/DwarfGenerator.cpp

112 ↗

(On Diff #83315)

Is this conditional needed - or do we generally assume it's an invariant that the Die is non-null for most of the operations on dwarfgen::DIE?

[clayborg]

unittests/DebugInfo/DWARF/DwarfGenerator.cpp

112 ↗

(On Diff #83315)

I'll take the if out.

include/llvm/DebugInfo/DWARF/DWARFDie.h

 //===-- DWARFDie.h --------------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_DEBUGINFO_DWARFDIE_H
 #define LLVM_LIB_DEBUGINFO_DWARFDIE_H
 
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h"
 
 namespace llvm {
     
 class DWARFUnit;
 class DWARFDebugInfoEntry;
 class raw_ostream;
class DWARFDie {
   DWARFUnit *U;
   const DWARFDebugInfoEntry *Die;
 public:
   DWARFDie() : U(nullptr), Die(nullptr) {}
   DWARFDie(DWARFUnit *Unit, const DWARFDebugInfoEntry * D) : U(Unit), Die(D) {}
   
   bool isValid() const { return U && Die; }
   explicit operator bool() const { return isValid(); }
-  bool operator ==(const DWARFDie &RHS) const {
-    return Die == RHS.Die && U == RHS.U;
-  }
   const DWARFDebugInfoEntry *getDebugInfoEntry() const { return Die; }
   DWARFUnit *getDwarfUnit() const { return U; }
 
 
   /// Get the abbreviation declaration for this DIE.
   ///
   /// \returns the abbreviation declaration or NULL for null tags.
   const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const {
     assert(isValid() && "must check validity prior to calling");
     return Die->getAbbreviationDeclarationPtr();
public:
   
   /// Get inlined chain for a given address, rooted at the current DIE.
   /// Returns empty chain if address is not contained in address range
   /// of current DIE.
   void
   getInlinedChainForAddress(const uint64_t Address,
                             SmallVectorImpl<DWARFDie> &InlinedChain) const;
 
+  class iterator;
+  
+  iterator begin() const;
+  iterator end() const;
+  iterator_range<iterator> children() const;
+};
+
+  
+inline bool operator==(const DWARFDie &LHS, const DWARFDie &RHS) {
+  return LHS.getDebugInfoEntry() == RHS.getDebugInfoEntry() &&
+      LHS.getDwarfUnit() == RHS.getDwarfUnit();
+}
+
+inline bool operator!=(const DWARFDie &LHS, const DWARFDie &RHS) {
+  return !(LHS == RHS);
+}
+
+class DWARFDie::iterator : public iterator_facade_base<iterator,
+                                                      std::forward_iterator_tag,
+                                                      const DWARFDie> {
+  DWARFDie Die;
+  void skipNull() {
+    if (Die && Die.isNULL())
+      Die = DWARFDie();
+  }
+public:
+  iterator() = default;
+  explicit iterator(DWARFDie D) : Die(D) {
+    // If we start out with only a Null DIE then invalidate.
+    skipNull();
+  }
+  iterator &operator++() {
+    Die = Die.getSibling();
+    // Don't include the NULL die when iterating.
+    skipNull();
+    return *this;
+  }
+  explicit operator bool() const { return Die.isValid(); }
+  const DWARFDie &operator*() const { return Die; }
+  bool operator==(const iterator &X) const { return Die == X.Die; }
 };
 
+// These inline functions must follow the DWARFDie::iterator definition above
+// as they use functions from that class.
+inline DWARFDie::iterator DWARFDie::begin() const {
+  return iterator(getFirstChild());
+}
+
+inline DWARFDie::iterator DWARFDie::end() const {
+  return iterator();
+}
+
+inline iterator_range<DWARFDie::iterator> DWARFDie::children() const {
+  return make_range(begin(), end());
+}
 
 } // end namespace llvm
 
 #endif  // LLVM_LIB_DEBUGINFO_DWARFDIE_H

lib/DebugInfo/DWARF/DWARFDie.cpp

 DWARFDie::collectChildrenAddressRanges(DWARFAddressRangesVector& Ranges) const {
   if (isNULL())
     return;
   if (isSubprogramDIE()) {
     const auto &DIERanges = getAddressRanges();
     Ranges.insert(Ranges.end(), DIERanges.begin(), DIERanges.end());
   }
 
-  DWARFDie Child = getFirstChild();
-  while (Child) {
+  for (auto Child: children())
     Child.collectChildrenAddressRanges(Ranges);
-    Child = Child.getSibling();
-  }
 }
 
 bool DWARFDie::addressRangeContainsAddress(const uint64_t Address) const {
   for (const auto& R : getAddressRanges()) {
     if (R.first <= Address && Address < R.second)
       return true;
   }
   return false;
if (isValid())
     return U->getParent(Die);
   return DWARFDie();
 }
 
 DWARFDie DWARFDie::getSibling() const {
   if (isValid())
     return U->getSibling(Die);
   return DWARFDie();
 }

tools/dsymutil/DwarfLinker.cpp

if (CurrentDeclContext) {
       Info.Ctxt =
           PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer();
     } else
       Info.Ctxt = CurrentDeclContext = nullptr;
   }
 
   Info.Prune = InImportedModule;
   if (DIE.hasChildren())
-    for (auto Child = DIE.getFirstChild(); Child && !Child.isNULL();
-         Child = Child.getSibling())
+    for (auto Child: DIE.children())
       Info.Prune &= analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext,
                                        StringPool, Contexts, InImportedModule);
 
   // Prune this DIE if it is either a forward declaration inside a
   // DW_TAG_module or a DW_TAG_module that contains nothing but
   // forward declarations.
   Info.Prune &= (DIE.getTag() == dwarf::DW_TAG_module) ||
                 DIE.getAttributeValueAsUnsignedConstant(
                     dwarf::DW_AT_declaration, 0);
 
void DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
   // set of DIE types for which we want to ignore that directive and still
   // walk their children.
   if (dieNeedsChildrenToBeMeaningful(Die.getTag()))
     Flags &= ~TF_ParentWalk;
 
   if (!Die.hasChildren() || (Flags & TF_ParentWalk))
     return;
 
-  for (auto Child = Die.getFirstChild(); Child && !Child.isNULL();
-       Child = Child.getSibling())
+  for (auto Child: Die.children())
     lookForDIEsToKeep(RelocMgr, Child, DMO, CU, Flags);
 }
 
 /// \brief Assign an abbreviation numer to \p Abbrev.
 ///
 /// Our DIEs get freed after every DebugMapObject has been processed,
 /// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
 /// the instances hold by the DIEs. When we encounter an abbreviation
if (AttrInfo.Name)
                               Tag == dwarf::DW_TAG_inlined_subroutine);
   } else if (isTypeTag(Tag) && !AttrInfo.IsDeclaration &&
              getDIENames(InputDIE, AttrInfo)) {
     Unit.addTypeAccelerator(Die, AttrInfo.Name, AttrInfo.NameOffset);
   }
 
   // Determine whether there are any children that we want to keep.
   bool HasChildren = false;
-  for (auto Child = InputDIE.getFirstChild(); Child && !Child.isNULL();
-       Child = Child.getSibling()) {
+  for (auto Child: InputDIE.children()) {
     unsigned Idx = U.getDIEIndex(Child);
     if (Unit.getInfo(Idx).Keep) {
       HasChildren = true;
       break;
     }
   }
 
   DIEAbbrev NewAbbrev = Die->generateAbbrev();
   if (HasChildren)
     NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
   // Assign a permanent abbrev number
   Linker.AssignAbbrev(NewAbbrev);
   Die->setAbbrevNumber(NewAbbrev.getNumber());
 
   // Add the size of the abbreviation number to the output offset.
   OutOffset += getULEB128Size(Die->getAbbrevNumber());
 
   if (!HasChildren) {
     // Update our size.
     Die->setSize(OutOffset - Die->getOffset());
     return Die;
   }
 
   // Recursively clone children.
-  for (auto Child = InputDIE.getFirstChild(); Child && !Child.isNULL();
-       Child = Child.getSibling()) {
+  for (auto Child: InputDIE.children()) {
     if (DIE *Clone = cloneDIE(Child, Unit, PCOffset, OutOffset, Flags)) {
       Die->addChild(Clone);
       OutOffset = Clone->getOffset() + Clone->getSize();
     }
   }
 
   // Account for the end of children marker.
   OutOffset += sizeof(int8_t);

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

TEST(DWARFDebugInfo, TestDWARFDie) {
   // Make sure a default constructed DWARFDie doesn't have any parent, sibling
   // or child;
   DWARFDie DefaultDie;
   EXPECT_FALSE(DefaultDie.getParent().isValid());
   EXPECT_FALSE(DefaultDie.getFirstChild().isValid());
   EXPECT_FALSE(DefaultDie.getSibling().isValid());
 }
 
+TEST(DWARFDebugInfo, TestChildIterators) {
+  // Test the DWARF APIs related to iterating across the children of a DIE using
+  // the DWARFDie::iterator class.
+  uint16_t Version = 4;
+  
+  const uint8_t AddrSize = sizeof(void *);
+  initLLVMIfNeeded();
+  Triple Triple = getHostTripleForAddrSize(AddrSize);
+  auto ExpectedDG = dwarfgen::Generator::create(Triple, Version);
+  if (HandleExpectedError(ExpectedDG))
+    return;
+  dwarfgen::Generator *DG = ExpectedDG.get().get();
+  dwarfgen::CompileUnit &CU = DG->addCompileUnit();
+  
+  enum class Tag: uint16_t  {
+    A = dwarf::DW_TAG_lo_user,
+    B,
+  };
+  
+  // Scope to allow us to re-use the same DIE names
+  {
+    // Create DWARF tree that looks like:
+    //
+    // CU
+    //   A
+    //   B
+    auto CUDie = CU.getUnitDIE();
+    CUDie.addChild((dwarf::Tag)Tag::A);
+    CUDie.addChild((dwarf::Tag)Tag::B);
+  }
+  
+  MemoryBufferRef FileBuffer(DG->generate(), "dwarf");
+  auto Obj = object::ObjectFile::createObjectFile(FileBuffer);
+  EXPECT_TRUE((bool)Obj);
+  DWARFContextInMemory DwarfContext(*Obj.get());
+  
+  // Verify the number of compile units is correct.
+  uint32_t NumCUs = DwarfContext.getNumCompileUnits();
+  EXPECT_EQ(NumCUs, 1u);
+  DWARFCompileUnit *U = DwarfContext.getCompileUnitAtIndex(0);
+  
+  // Get the compile unit DIE is valid.
+  auto CUDie = U->getUnitDIE(false);
+  EXPECT_TRUE(CUDie.isValid());
+  // CUDie.dump(llvm::outs(), UINT32_MAX);
+  uint32_t Index;
+  DWARFDie A;
+  DWARFDie B;
+  
+  // Verify the compile unit DIE's children.
+  Index = 0;
+  for (auto Die : CUDie.children()) {
+    switch (Index++) {
+      case 0: A = Die; break;
+      case 1: B = Die; break;
+    }
+  }
+  
+  EXPECT_EQ(A.getTag(), (dwarf::Tag)Tag::A);
+  EXPECT_EQ(B.getTag(), (dwarf::Tag)Tag::B);
+
+  // Verify that A has no children by verifying that the begin and end contain
+  // invalid DIEs and also that the iterators are equal.
+  EXPECT_EQ(A.begin(), A.end());
+}
+
+TEST(DWARFDebugInfo, TestChildIteratorsOnInvalidDie) {
+  // Verify that an invalid DIE has no children.
+  DWARFDie Invalid;
+  auto begin = Invalid.begin();
+  auto end = Invalid.end();
+  EXPECT_FALSE(begin->isValid());
+  EXPECT_FALSE(end->isValid());
+  EXPECT_EQ(begin, end);
+}
 
 } // end anonymous namespace