From 86e18055e607b257c6867e444a4e598cb8f812b8 Mon Sep 17 00:00:00 2001 From: Jonas Devlieghere Date: Wed, 1 Aug 2018 10:24:17 +0000 Subject: [DebugInfo] Have custom std::reverse_iterator 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 --- include/llvm/DebugInfo/DWARF/DWARFDie.h | 97 +++++++++++++++++++++++- unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp | 71 ++++++++++++----- 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 rbegin() const; + std::reverse_iterator rend() const; + iterator_range children() const; }; @@ -323,6 +327,11 @@ class DWARFDie::iterator : public iterator_facade_base { DWARFDie Die; + + friend std::reverse_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::children() const { } // end namespace llvm +namespace std { + +template <> +class reverse_iterator + : public llvm::iterator_facade_base< + reverse_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 &operator++() { + assert(!AtEnd && "Incrementing rend"); + llvm::DWARFDie D = Die.getPreviousSibling(); + if (D) + Die = D; + else + AtEnd = true; + return *this; + } + + reverse_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 &RHS) const { + return Die == RHS.Die && AtEnd == RHS.AtEnd; + } +}; + +} // namespace std + +namespace llvm { + +inline bool operator==(const std::reverse_iterator &LHS, + const std::reverse_iterator &RHS) { + return LHS.equals(RHS); +} + +inline bool operator!=(const std::reverse_iterator &LHS, + const std::reverse_iterator &RHS) { + return !(LHS == RHS); +} + +inline std::reverse_iterator DWARFDie::rbegin() const { + return make_reverse_iterator(end()); +} + +inline std::reverse_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(A.begin(), A.end()), + testing::ElementsAre(B, C, D)); + EXPECT_THAT(std::vector(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) { -- cgit v1.2.3