[DebugInfo] Make children iterator bidirectional

[JDevlieghere]

Summary

Make the DIE iterator bidirectional so we can move to the previous sibling of a DIE.

[JDevlieghere]

• Remove null check so we can iterate backwards from the end iterator.

[JDevlieghere]

• Update comments

[dblaikie]

llvm/include/llvm/DebugInfo/DWARF/DWARFDie.h

359

Why was this change needed?

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

595–599

Unlike get(Next)Sibling, this loop may need to check for "<= Depth" and then return DWARFDie() if it's the < case.

When going forwards, there's always a null die sibling to break this loop (well, I guess a null die is returned from getSibling - and then no caller tries to call getSibling on the null die) - because it has the same depth.

But going backwards there's no null die to break the loop - oh, well, kind of.

So if you've got this arrangement: Unit{A{B,NULL},C{D,NULL},NULL}

And at D you "get previous" then you'll return the NULL child of A... which is still a null child, and that works I suppose. But you could've stopped searching once you saw C - because you've stepped out of C's children list by going to a shallower depth than the depth of D who's sibling you were searching for.

Oh... and it's undefined to dereference a begin iterator anyway, so none of that really matters, I suppose? :)

[JDevlieghere]

• Address review feedback Dave

[JDevlieghere]

llvm/include/llvm/DebugInfo/DWARF/DWARFDie.h

359

For a bidirectional iterator you should be able to start iterating from end(), right? (so long you don't dereference it)

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

595–599

Indeed. I added the check at some point but looks like it didn't make it into the patch. Even if it doesn't matter for the iterator (I assume you mean dereferencing the end iterator?) the check is cheap so we might as well make the interface behave as you'd expect.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

595–599

Yeah - if it were just the iterator API I'd say maybe make it an assert - but since this is a "getPrevSibling" it makes sense to me that it's not UB to call it on the first child, and for it to be symmetric with "get(Next)Sibling" in terms of returning null on the first/last element.

624

Maybe assert that DieArray[I].getDepth() > Depth - to ensure it didn't some how jump out of the children?

[JDevlieghere]

Thanks for the review!

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

624

Good idea, I'll add that before committing.

llvm/include/llvm/DebugInfo/DWARF/DWARFDie.h

public:
   DWARFDie getParent() const;
 
   /// Get the sibling of this DIE object.
   ///
   /// \returns a valid DWARFDie instance if this object has a sibling or an
   /// invalid DWARFDie instance if it doesn't.
   DWARFDie getSibling() const;
 
+  /// Get the previous sibling of this DIE object.
+  ///
+  /// \returns a valid DWARFDie instance if this object has a sibling or an
+  /// invalid DWARFDie instance if it doesn't.
+  DWARFDie getPreviousSibling() const;
+
   /// Get the first child of this DIE object.
   ///
   /// \returns a valid DWARFDie instance if this object has children or an
   /// invalid DWARFDie instance if it doesn't.
   DWARFDie getFirstChild() const;
 
   /// Dump the DIE and all of its attributes to the supplied stream.
   ///
public:
 
   class iterator;
 
   iterator begin() const;
   iterator end() const;
   iterator_range<iterator> children() const;
 };
 
-class DWARFDie::attribute_iterator :
-    public iterator_facade_base<attribute_iterator, std::forward_iterator_tag,
+class DWARFDie::attribute_iterator
+    : public iterator_facade_base<attribute_iterator,
+                                  std::bidirectional_iterator_tag,
                                   const DWARFAttribute> {
   /// The DWARF DIE we are extracting attributes from.
   DWARFDie Die;
   /// The value vended to clients via the operator*() or operator->().
   DWARFAttribute AttrValue;
   /// The attribute index within the abbreviation declaration in Die.
   uint32_t Index;
 
   /// Update the attribute index and attempt to read the attribute value. If the
   /// attribute is able to be read, update AttrValue and the Index member
   /// variable. If the attribute value is not able to be read, an appropriate
   /// error will be set if the Err member variable is non-NULL and the iterator
   /// will be set to the end value so iteration stops.
   void updateForIndex(const DWARFAbbreviationDeclaration &AbbrDecl, uint32_t I);
 
 public:
   attribute_iterator() = delete;
   explicit attribute_iterator(DWARFDie D, bool End);
 
   attribute_iterator &operator++();
+  attribute_iterator &operator--();
   explicit operator bool() const { return AttrValue.isValid(); }
   const DWARFAttribute &operator*() const { return AttrValue; }
   bool operator==(const attribute_iterator &X) const { return Index == X.Index; }
 };
 
 inline bool operator==(const DWARFDie &LHS, const DWARFDie &RHS) {
   return LHS.getDebugInfoEntry() == RHS.getDebugInfoEntry() &&
       LHS.getDwarfUnit() == RHS.getDwarfUnit();
public:
 
   iterator &operator++() {
     Die = Die.getSibling();
     // Don't include the NULL die when iterating.
     skipNull();
     return *this;
   }
 
+  iterator &operator--() {
+    Die = Die.getPreviousSibling();
+    // 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_DEBUGINFO_DWARFDIE_H

llvm/include/llvm/DebugInfo/DWARF/DWARFUnit.h

public:
   /// Return the DIE object at the given index.
   DWARFDie getDIEAtIndex(unsigned Index) {
     assert(Index < DieArray.size());
     return DWARFDie(this, &DieArray[Index]);
   }
 
   DWARFDie getParent(const DWARFDebugInfoEntry *Die);
   DWARFDie getSibling(const DWARFDebugInfoEntry *Die);
+  DWARFDie getPreviousSibling(const DWARFDebugInfoEntry *Die);
   DWARFDie getFirstChild(const DWARFDebugInfoEntry *Die);
 
   /// Return the DIE object for a given offset inside the
   /// unit's DIE vector.
   ///
   /// The unit needs to have its DIEs extracted for this method to work.
   DWARFDie getDIEForOffset(uint32_t Offset) {
     extractDIEsIfNeeded(false);

llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

 }
 
 DWARFDie DWARFDie::getSibling() const {
   if (isValid())
     return U->getSibling(Die);
   return DWARFDie();
 }
 
+DWARFDie DWARFDie::getPreviousSibling() const {
+  if (isValid())
+    return U->getPreviousSibling(Die);
+  return DWARFDie();
+}
+
 DWARFDie DWARFDie::getFirstChild() const {
   if (isValid())
     return U->getFirstChild(Die);
   return DWARFDie();
 }
 
 iterator_range<DWARFDie::attribute_iterator> DWARFDie::attributes() const {
   return make_range(attribute_iterator(*this, false),

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
        ++I) {
     if (DieArray[I].getDepth() == Depth)
       return DWARFDie(this, &DieArray[I]);
   }
   return DWARFDie();
 }
 
+DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
+  if (!Die)
+    return DWARFDie();
+  uint32_t Depth = Die->getDepth();
+  // Unit DIEs always have a depth of zero and never have siblings.
+  if (Depth == 0)
+    return DWARFDie();
+
+  // Find the previous DIE whose depth is the same as the Die's depth.
+  for (size_t I = getDIEIndex(Die) - 1; I >= 0; --I) {
+    if (DieArray[I].getDepth() == Depth)
+      return DWARFDie(this, &DieArray[I]);
+  }
+  return DWARFDie();
+}
+
 DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
   if (!Die->hasChildren())
     return DWARFDie();
 
   // We do not want access out of bounds when parsing corrupted debug data.
   size_t I = getDIEIndex(Die) + 1;
   if (I >= DieArray.size())
     return DWARFDie();
   return DWARFDie(this, &DieArray[I]);
 }
 
 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
   if (!Abbrevs)
     Abbrevs = Abbrev->getAbbreviationDeclarationSet(Header.getAbbrOffset());
   return Abbrevs;
 }
 
 llvm::Optional<BaseAddress> DWARFUnit::getBaseAddress() {
   if (BaseAddr)
     return BaseAddr;
 
   DWARFDie UnitDie = getUnitDIE();
   Optional<DWARFFormValue> PC = UnitDie.find({DW_AT_low_pc, DW_AT_entry_pc});
   if (Optional<uint64_t> Addr = toAddress(PC))
     BaseAddr = {*Addr, PC->getSectionIndex()};
 
   return BaseAddr;
 }
 
 Optional<StrOffsetsContributionDescriptor>

llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

template <uint16_t Version, class AddrType> void TestChildren() {
   // Verify the sibling of our subprogram is our integer base is a NULL tag.
   NullDieDG = IntDieDG.getSibling();
   EXPECT_TRUE(NullDieDG.isValid());
   if (NullDieDG) {
     EXPECT_EQ(NullDieDG.getTag(), DW_TAG_null);
     EXPECT_TRUE(!NullDieDG.getSibling().isValid());
     EXPECT_TRUE(!NullDieDG.getFirstChild().isValid());
   }
+
+  // Verify the previous sibling of our subprogram is our integer base type.
+  IntDieDG = NullDieDG.getPreviousSibling();
+  EXPECT_TRUE(IntDieDG.isValid());
+  EXPECT_EQ(IntDieDG.getTag(), DW_TAG_base_type);
 }
 
 TEST(DWARFDebugInfo, TestDWARF32Version2Addr4Children) {
   // Test that we can decode all forms for DWARF32, version 2, with 4 byte
   // addresses.
   typedef uint32_t AddrType;
   TestChildren<2, AddrType>();
 }