unfinished w/debug hacks

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 "