[DebugInfo] Have custom std::reverse_iterator<DWARFDie>

[JDevlieghere]

Summary

Alternative for D49234.

[labath]

What's the reason for not specializing std::reverse_iterator? AFAIK, that is officially permitted by the standard.

This way somebody can still construct a std::reverse_iterator<DWARFDie::iterator> (via make_reverse_iterator or whatever) and get UB.

[JDevlieghere]

In D49679#1172143, @labath wrote:

What's the reason for not specializing std::reverse_iterator? AFAIK, that is officially permitted by the standard.

What exactly would you do difference? I can see a solution where we make the current __tmp a class member of the iterator adapter, but maybe you have something more straightforward in mind?

This way somebody can still construct a std::reverse_iterator<DWARFDie::iterator> (via make_reverse_iterator or whatever) and get UB.

That's not entirely true because it's no longer a bidirectional iterator. Regardless of the specialization, both *++iterator and *--iterator will remain UB.

[labath]

In D49679#1172404, @JDevlieghere wrote:

In D49679#1172143, @labath wrote:

What's the reason for not specializing std::reverse_iterator? AFAIK, that is officially permitted by the standard.

What exactly would you do difference? I can see a solution where we make the current __tmp a class member of the iterator adapter, but maybe you have something more straightforward in mind?

This way somebody can still construct a std::reverse_iterator<DWARFDie::iterator> (via make_reverse_iterator or whatever) and get UB.

That's not entirely true because it's no longer a bidirectional iterator. Regardless of the specialization, both *++iterator and *--iterator will remain UB.

Sorry I wrote the reply without looking at the patch in detail. I did not notice you demoted the iterator back to "forward". In case this is not a bidirectional operator, but a collection of two forward iterators that happen to iterate in the reverse order, the specializing std::reverse_iterator is not the right approach.

I have to admit I haven't thought about the specifics of how the reverse iterator would work until now. However, now that I think about it, I think it could be implemented as a pair of DWARFDie + bool flag. The trick would be that we store the element that we really dereference to, instead of its successor. The bool flag would be used denote the before_begin state, as we cannot represent rend() this way. The implementation would do something like:

operator++() {
  assert(!AtEnd && "Incrementing rend");
  DWARFDie D = Die.getPreviousSibling();
  if (D)
    Die = D;
  else
    AtEnd = true;
}

operator--() {
  if (AtEnd) {
    AtEnd = false;
    return;
  }
  Die = Die.getNextSibling();
  assert(!Die.isNULL() && "Decrementing rbegin");
}

However, if you don't need that extra complexity now, then I suppose this solution is fine too.

llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1081–1116 ↗

(On Diff #156820)

This will succeed even if the iterator range returns an empty sequence.

Might I suggest a shorter alternative with a more helpful error message?

EXPECT_THAT(std::vector<DWARFDie>(A.begin(), A.end()),
            testing::ElementsAre(B, C, D));

[JDevlieghere]

• Feedback Pavel

[JDevlieghere]

In D49679#1173122, @labath wrote:

Sorry I wrote the reply without looking at the patch in detail. I did not notice you demoted the iterator back to "forward". In case this is not a bidirectional operator, but a collection of two forward iterators that happen to iterate in the reverse order, the specializing std::reverse_iterator is not the right approach.

I have to admit I haven't thought about the specifics of how the reverse iterator would work until now. However, now that I think about it, I think it could be implemented as a pair of DWARFDie + bool flag. The trick would be that we store the element that we really dereference to, instead of its successor. The bool flag would be used denote the before_begin state, as we cannot represent rend() this way. The implementation would do something like:

operator++() {
  assert(!AtEnd && "Incrementing rend");
  DWARFDie D = Die.getPreviousSibling();
  if (D)
    Die = D;
  else
    AtEnd = true;
}

operator--() {
  if (AtEnd) {
    AtEnd = false;
    return;
  }
  Die = Die.getNextSibling();
  assert(!Die.isNULL() && "Decrementing rbegin");
}

I think I'm missing something; what are you implementing here exactly and what problem is it trying to solve?

However, if you don't need that extra complexity now, then I suppose this solution is fine too.

[JDevlieghere]

• Specialize std::reverse_iterator for llvm::DWARFDie as suggested by Pavel.

[labath]

I like this, but that's not surprising, as it was my idea in the first place. :)

I think David should have a pass at this too.

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

373 ↗

(On Diff #157026)

This will inject all llvm decls into the std namespace. bad idea :)

389–392 ↗

(On Diff #157026)

These should be already inherited via std::iterator, shouldn't they?

410–418 ↗

(On Diff #157026)

We should also add a test which does a manual reverse iteration (via this function) on the reverse_iterator :), to check that this works too.

420 ↗

(On Diff #157026)

This should also take the value of AtEnd into account. Probably something like Die.isValid() && !AtEnd. Maybe you could even assert AtEnd == false when dereferencing.

[JDevlieghere]

Address Pavel's feedback:

• Don't clutter std namespace.
• Don't redefine iterator traits.
• Add test cases that checks bidirectional aspect of both iterators.
• Fix operator bool() to check AtEnd.

[dblaikie]

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

383–384 ↗

(On Diff #157035)

Could a null DWARFDie (a default constructed one, rather than a non-default constructed one that points to a null DIE) be used as the 'rend' value - avoiding the need for the bool?

413–414 ↗

(On Diff #157035)

Is this used/needed? Might be easier to leave it out & require users to do comparisons with the rend iterator?

420 ↗

(On Diff #157035)

Any operator that can be a non-member should be, ideally (so op== and op!= for example), so that any implicit conversions can occur equally on the LHS and RHS of the expression.

[labath]

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

383–384 ↗

(On Diff #157035)

for operator-- you need to be able to go back from the "rend" position, which won't work for a default-constructed DWARFDie. I suppose that would be possible if we dropped operator-- (I don't expect anyone will need it), though then this will not be a conforming reverse_iterator.

[JDevlieghere]

• Address Dave's feedback

[dblaikie]

(probably a separate patch) Wonder if we could have a specialization of llvm::reverse that detects whether the underlying range has 'rbegin/rend' functions and use those, rather than making reverse iterators out of end/begin. That way reverse(die) would work correctly.

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

393–394 ↗

(On Diff #157242)

/looks/ to me like this declaration isn't needed? I don't see any use of it in the specialization/before the op== definition later.

397–402 ↗

(On Diff #157242)

Any chance of using llvm's iterator_facade here, might simplify things a bit?

447–456 ↗

(On Diff #157242)

I wonder if these should go in the llvm namespace (they'd still be found by ADL, I think) rather than here in the std namespace?

[JDevlieghere]

• Address Dave's feedback

[dblaikie]

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

285–286 ↗

(On Diff #158254)

extraneous/extra formatting?

295–324 ↗

(On Diff #158254)

Looks like an unrelated change that can be committed separately?

435–436 ↗

(On Diff #158254)

Could you be more precise - what goes wrong/what error is produced?

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

public:
   ///
   /// \returns an iterator range for the attributes of the current DIE.
   iterator_range<attribute_iterator> attributes() const;
 
   class iterator;
 
   iterator begin() const;
   iterator end() const;
+
+  std::reverse_iterator<iterator> rbegin() const;
+  std::reverse_iterator<iterator> rend() const;
+
   iterator_range<iterator> children() const;
 };
 
 class DWARFDie::attribute_iterator :
     public iterator_facade_base<attribute_iterator, std::forward_iterator_tag,
                                 const DWARFAttribute> {
   /// The DWARF DIE we are extracting attributes from.
   DWARFDie Die;

 inline bool operator<(const DWARFDie &LHS, const DWARFDie &RHS) {
   return LHS.getOffset() < RHS.getOffset();
 }
 
 class DWARFDie::iterator
     : public iterator_facade_base<iterator, std::bidirectional_iterator_tag,
                                   const DWARFDie> {
   DWARFDie Die;
+
+  friend std::reverse_iterator<llvm::DWARFDie::iterator>;
+  friend bool operator==(const DWARFDie::iterator &LHS,
+                         const DWARFDie::iterator &RHS);
+
 public:
   iterator() = default;
 
   explicit iterator(DWARFDie D) : Die(D) {
   }
 
   iterator &operator++() {
     Die = Die.getSibling();
     return *this;
   }
 
   iterator &operator--() {
     Die = Die.getPreviousSibling();
     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; }
 };
 
+inline bool operator==(const DWARFDie::iterator &LHS,
+                       const DWARFDie::iterator &RHS) {
+  return LHS.Die == RHS.Die;
+}
+
+inline bool operator!=(const DWARFDie::iterator &LHS,
+                       const DWARFDie::iterator &RHS) {
+  return !(LHS == RHS);
+}
+
 // 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(getLastChild());
 }
 
 inline iterator_range<DWARFDie::iterator> DWARFDie::children() const {
   return make_range(begin(), end());
 }
 
 } // end namespace llvm
 
+namespace std {
+
+template <>
+class reverse_iterator<llvm::DWARFDie::iterator>
+    : public llvm::iterator_facade_base<
+          reverse_iterator<llvm::DWARFDie::iterator>,
+          bidirectional_iterator_tag, const llvm::DWARFDie> {
+
+private:
+  llvm::DWARFDie Die;
+  bool AtEnd;
+
+public:
+  reverse_iterator(llvm::DWARFDie::iterator It)
+      : Die(It.Die), AtEnd(!It.Die.getPreviousSibling()) {
+    if (!AtEnd)
+      Die = Die.getPreviousSibling();
+  }
+
+  reverse_iterator<llvm::DWARFDie::iterator> &operator++() {
+    assert(!AtEnd && "Incrementing rend");
+    llvm::DWARFDie D = Die.getPreviousSibling();
+    if (D)
+      Die = D;
+    else
+      AtEnd = true;
+    return *this;
+  }
+
+  reverse_iterator<llvm::DWARFDie::iterator> &operator--() {
+    if (AtEnd) {
+      AtEnd = false;
+      return *this;
+    }
+    Die = Die.getSibling();
+    assert(!Die.isNULL() && "Decrementing rbegin");
+    return *this;
+  }
+
+  const llvm::DWARFDie &operator*() const {
+    assert(Die.isValid());
+    return Die;
+  }
+
+  // FIXME: We should be able to specify the equals operator as a friend, but
+  //        that causes the compiler to think the operator overload is ambiguous
+  //        with the friend declaration and the actual definition as candidates.
+  bool equals(const reverse_iterator<llvm::DWARFDie::iterator> &RHS) const {
+    return Die == RHS.Die && AtEnd == RHS.AtEnd;
+  }
+};
+
+} // namespace std
+
+namespace llvm {
+
+inline bool operator==(const std::reverse_iterator<DWARFDie::iterator> &LHS,
+                       const std::reverse_iterator<DWARFDie::iterator> &RHS) {
+  return LHS.equals(RHS);
+}
+
+inline bool operator!=(const std::reverse_iterator<DWARFDie::iterator> &LHS,
+                       const std::reverse_iterator<DWARFDie::iterator> &RHS) {
+  return !(LHS == RHS);
+}
+
+inline std::reverse_iterator<DWARFDie::iterator> DWARFDie::rbegin() const {
+  return make_reverse_iterator(end());
+}
+
+inline std::reverse_iterator<DWARFDie::iterator> DWARFDie::rend() const {
+  return make_reverse_iterator(begin());
+}
+
+} // end namespace llvm
+
 #endif // LLVM_DEBUGINFO_DWARFDIE_H

llvm/trunk/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

TEST(DWARFDebugInfo, TestRelations) {
   // Verify all children of the B DIE correctly valid or invalid.
   EXPECT_EQ(C1.getTag(), (dwarf::Tag)Tag::C1);
   EXPECT_EQ(C2.getTag(), (dwarf::Tag)Tag::C2);
 
   // Make sure the parent of all the children of the B are the B.
   EXPECT_EQ(C1.getParent(), C);
   EXPECT_EQ(C2.getParent(), C);
 
-  // Make sure bidirectional iterator works as expected.
+  // Make sure iterators work as expected.
+  EXPECT_THAT(std::vector<DWARFDie>(A.begin(), A.end()),
+              testing::ElementsAre(B, C, D));
+  EXPECT_THAT(std::vector<DWARFDie>(A.rbegin(), A.rend()),
+              testing::ElementsAre(D, C, B));
+
+  // Make sure iterator is bidirectional.
+  {
     auto Begin = A.begin();
     auto End = A.end();
     auto It = A.begin();
 
     EXPECT_EQ(It, Begin);
     EXPECT_EQ(*It, B);
     ++It;
     EXPECT_EQ(*It, C);
     ++It;
     EXPECT_EQ(*It, D);
     ++It;
     EXPECT_EQ(It, End);
     --It;
     EXPECT_EQ(*It, D);
     --It;
     EXPECT_EQ(*It, C);
     --It;
     EXPECT_EQ(*It, B);
     EXPECT_EQ(It, Begin);
   }
 
+  // Make sure reverse iterator is bidirectional.
+  {
+    auto Begin = A.rbegin();
+    auto End = A.rend();
+    auto It = A.rbegin();
+
+    EXPECT_EQ(It, Begin);
+    EXPECT_EQ(*It, D);
+    ++It;
+    EXPECT_EQ(*It, C);
+    ++It;
+    EXPECT_EQ(*It, B);
+    ++It;
+    EXPECT_EQ(It, End);
+    --It;
+    EXPECT_EQ(*It, B);
+    --It;
+    EXPECT_EQ(*It, C);
+    --It;
+    EXPECT_EQ(*It, D);
+    EXPECT_EQ(It, Begin);
+  }
+}
+
 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());
 }