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

The DWARFDie is a lightweight utility wrapper that stores a pointer to a
compile unit and a debug info entry. Currently, its iterator (used for
walking over its children) stores a DWARFDie and returns a const
reference when dereferencing it.

When the iterator is modified (by incrementing or decrementing it), this
reference becomes invalid. This was happening when calling reverse on
it, because the std::reverse_iterator is keeping a temporary copy of the
iterator (see
https://en.cppreference.com/w/cpp/iterator/reverse_iterator for a good
illustration).

The relevant code in libcxx:

  reference operator*() const {_Iter __tmp = current; return *--__tmp;}

When dereferencing the reverse iterator, we decrement and return a
reference to a DWARFDie stored in the stack frame of this function,
resulting in UB at runtime.

This patch specifies the std::reverse_iterator for DWARFDie to do the
right thing.

Differential revision: https://reviews.llvm.org/D49679

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@338506 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 146 insertions, 22 deletions

diff --git a/include/llvm/DebugInfo/DWARF/DWARFDie.h b/include/llvm/DebugInfo/DWARF/DWARFDie.h
index 6e6b57cbcbd..f10aaa6ce3d 100644
--- a/include/llvm/DebugInfo/DWARF/DWARFDie.h
+++ b/include/llvm/DebugInfo/DWARF/DWARFDie.h
@@ -275,6 +275,10 @@ public:
 
   iterator begin() const;
   iterator end() const;
+
+  std::reverse_iterator<iterator> rbegin() const;
+  std::reverse_iterator<iterator> rend() const;
+
   iterator_range<iterator> children() const;
 };
 
@@ -323,6 +327,11 @@ 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;
 
@@ -339,11 +348,19 @@ public:
     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 {
@@ -360,4 +377,80 @@ inline iterator_range<DWARFDie::iterator> DWARFDie::children() const {
 
 } // 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
diff --git a/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp b/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
index 442dea3c52f..273809fcbd3 100644
--- a/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
+++ b/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
@@ -1122,26 +1122,57 @@ TEST(DWARFDebugInfo, TestRelations) {
   EXPECT_EQ(C1.getParent(), C);
   EXPECT_EQ(C2.getParent(), C);
 
-  // Make sure bidirectional iterator works as expected.
-  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 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) {