diff options
-rw-r--r-- | libdw/c++/dwarf_comparator | 51 | ||||
-rw-r--r-- | libdw/c++/dwarf_tracker | 90 | ||||
-rw-r--r-- | src/dwarfcmp.cc | 10 |
3 files changed, 119 insertions, 32 deletions
diff --git a/libdw/c++/dwarf_comparator b/libdw/c++/dwarf_comparator index 56bcd81d..b799ed42 100644 --- a/libdw/c++/dwarf_comparator +++ b/libdw/c++/dwarf_comparator @@ -128,22 +128,30 @@ namespace elfutils return false; } + struct reference_match + { + inline bool quick_match (const die2 &) + { + return false; + } + + inline void notice_match (const die2 &, bool) + { + } + }; + inline reference_match reference_matched (const die1 &) + { + return reference_match (); + } + inline dwarf_tracker_base () {} - inline dwarf_tracker_base (const dwarf_tracker_base &, + inline dwarf_tracker_base (const dwarf_tracker_base &, reference_match &, const left_context_type &, const die1 &, const right_context_type &, const die2 &) {} - inline bool quick_reference_match (const die1 &, const die2 &) - { - return false; - } - - inline void notice_reference_match (const die1 &, const die2 &) - { - } }; template<class dwarf1, class dwarf2, @@ -454,8 +462,8 @@ namespace elfutils if (a.tag () != b.tag ()) return false; - const bool any_children = a.has_children (); - if (any_children != b.has_children ()) + const bool has_children = a.has_children (); + if (has_children != b.has_children ()) return false; // Now we have to get the tracker involved. @@ -465,9 +473,15 @@ namespace elfutils = _m_tracker.right_context (ref2); // Maybe the tracker has already cached a correspondence of references. - if (_m_tracker.quick_reference_match (ref1, ref2)) + typename tracker::reference_match matched + = _m_tracker.reference_matched (ref1); + if (matched.quick_match (ref2)) return true; + std::cout << "considering ref " + << std::hex << a.offset () << " vs " + << std::hex << b.offset () << std::endl; + /* First do the cheap mismatch check on the contexts, then check the contents and contexts in ascending order of costliness of a check. */ if (_m_tracker.context_quick_mismatch (lhs, rhs) @@ -476,16 +490,17 @@ namespace elfutils return false; /* To compare the children, we have to clone the tracker and use a - new one. The new tracker jump-starts its walk to the referenced - DIE from the root of the CU. */ - bool result = !any_children || (dwarf_comparator (tracker (_m_tracker, + new one, in case of any reference attributes in their subtrees. + The new tracker jump-starts its walk to the referenced DIE from + the root of the CU. */ + bool result = !has_children || (dwarf_comparator (tracker (_m_tracker, + matched, lhs, ref1, rhs, ref2)) .match (a.children (), b.children ())); - // Let the tracker cache a known match for its quick_reference_match. - if (result) - _m_tracker.notice_reference_match (ref1, ref2); + // Let the tracker cache a result for its reference_match::quick_match. + matched.notice_match (ref2, result); return result; } diff --git a/libdw/c++/dwarf_tracker b/libdw/c++/dwarf_tracker index 70782258..2fefc426 100644 --- a/libdw/c++/dwarf_tracker +++ b/libdw/c++/dwarf_tracker @@ -52,6 +52,8 @@ #include "dwarf" #include "dwarf_comparator" +#include <tr1/unordered_map> +#include <tr1/unordered_set> namespace elfutils { @@ -110,10 +112,12 @@ namespace elfutils ~tracker () { - // We should never be left with a partial walk on the books. - assert (_m_path.empty ()); if (_m_delete_seen) - delete _m_seen; + { + delete _m_seen; + // We should never be left with a partial walk on the books. + assert (_m_path.empty ()); + } } inline const die_path &path_to (const die &a) @@ -135,10 +139,7 @@ namespace elfutils found.first = _m_seen->insert (found.first, std::make_pair (id, path)); } - - if (bad_die_path (found.first->second)) - abort (); // XXX - + assert (!bad_die_path (found.first->second)); return found.first->second; } @@ -200,6 +201,13 @@ namespace elfutils tracker1 _m_left; tracker2 _m_right; + typedef std::tr1::unordered_map< + ::Dwarf_Off, std::pair<dwarf_ref_tracker *, + std::tr1::unordered_set< ::Dwarf_Off> > + > equiv_map; + equiv_map *_m_equiv; + bool _m_delete_equiv; + /* Predicate for DIEs "equal enough" to match as context for a subtree. The definition we use is that the DIE has the same tag and all its attributes are equal, excepting that references in attribute values @@ -216,8 +224,16 @@ namespace elfutils public: inline dwarf_ref_tracker () + : _m_equiv (new equiv_map), _m_delete_equiv (true) {} + inline void reset () + { + _m_equiv->clear (); + assert (!_m_right->_m_delete_seen); + _m_right._m_seen->clear (); + } + inline void start_walk (const cu1 &a, const cu2 &b) { _m_left.start_walk (a); @@ -269,14 +285,66 @@ namespace elfutils return std::equal (a.begin (), a.end (), b.begin (), equal_enough ()); } + class reference_match + { + friend class dwarf_ref_tracker; + private: + typename equiv_map::mapped_type *_m_elt; + + inline reference_match (dwarf_ref_tracker *tracker, + typename equiv_map::mapped_type *elt) + : _m_elt (elt) + { + _m_elt->first = tracker; + } + + public: + + inline reference_match () + : _m_elt (NULL) + {} + + inline ~reference_match () + { + _m_elt->first = NULL; + } + + inline bool quick_match (const die2 &b) + { + return _m_elt->second.find (b->identity ()) != _m_elt->second.end (); + } + + inline void notice_match (const die2 &b, bool matches) + { + if (matches) + _m_elt->second.insert (b->identity ()); + } + }; + + inline reference_match reference_matched (const die1 &a) + { + typename equiv_map::mapped_type *elt = &(*_m_equiv)[a->identity ()]; + if (elt->first == NULL) + return reference_match (this, elt); + + // We have a circularity. + std::cout << "recursing? on " << std::hex << a->offset () << std::endl; + + throw std::logic_error ("XXX can't handle circularity"); + } + // Share the _m_seen maps with the prototype tracker, // but start a fresh walk from the given starting point. inline dwarf_ref_tracker (const dwarf_ref_tracker &proto, - const left_context_type &lhs, const die1 &, - const right_context_type &rhs, const die2 &) + reference_match &matched, + const left_context_type &lhs, const die1 &a, + const right_context_type &rhs, const die2 &b) : _m_left (tracker1 (proto._m_left, lhs)), - _m_right (tracker2 (proto._m_right, rhs)) - {} + _m_right (tracker2 (proto._m_right, rhs)), + _m_equiv (proto._m_equiv), _m_delete_equiv (false) + { + // We are starting a recursive consideration of a vs b. + } }; }; diff --git a/src/dwarfcmp.cc b/src/dwarfcmp.cc index c779fc49..acfeb3b6 100644 --- a/src/dwarfcmp.cc +++ b/src/dwarfcmp.cc @@ -138,21 +138,24 @@ struct talker : public dwarf_ref_tracker<dwarf1, dwarf2> const typename dwarf1::debug_info_entry *a_; const typename dwarf2::debug_info_entry *b_; + int depth_; inline talker () - : a_ (NULL), b_ (NULL) + : a_ (NULL), b_ (NULL), depth_ (0) {} inline talker (const talker &proto, + typename _tracker::reference_match &matched, const typename _tracker::left_context_type &l, const die1 &a, const typename _tracker::right_context_type &r, const die2 &b) - : _tracker (static_cast<const _tracker &> (proto), l, a, r, b), - a_ (NULL), b_ (NULL) + : _tracker (static_cast<const _tracker &> (proto), matched, l, a, r, b), + a_ (NULL), b_ (NULL), depth_ (proto.depth_ + 1) { } inline ostream &location () const { + cout << std::string(depth_, ' '); return cout << hex << a_->offset () << " vs " << b_->offset () << ": "; } @@ -161,6 +164,7 @@ struct talker : public dwarf_ref_tracker<dwarf1, dwarf2> { a_ = &a; b_ = &b; + location () << "visiting\n"; if (a.tag () != b.tag ()) location () << dwarf::tags::name (a.tag ()) << " vs " |