Use a separate tracker for subtree comparisons inside reference_match.

3 files changed, 134 insertions, 26 deletions

diff --git a/libdw/c++/dwarf_comparator b/libdw/c++/dwarf_comparator
index 8042a949..56bcd81d 100644
--- a/libdw/c++/dwarf_comparator
+++ b/libdw/c++/dwarf_comparator
@@ -127,6 +127,23 @@ namespace elfutils
     {
       return false;
     }
+
+    inline dwarf_tracker_base ()
+    {}
+
+    inline dwarf_tracker_base (const dwarf_tracker_base &,
+			       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,
@@ -142,8 +159,8 @@ namespace elfutils
     template<typename item1, typename item2>
     struct matcher : public std::binary_function<item1, item2, bool>
     {
-      dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &_m_cmp;
-      matcher (dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &cmp)
+      dwarf_comparator &_m_cmp;
+      matcher (dwarf_comparator &cmp)
 	: _m_cmp (cmp)
       {}
 
@@ -233,8 +250,8 @@ namespace elfutils
     struct match_rhs
       : public std::binary_function<ait1, ait2, bool>
     {
-      dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &_m_cmp;
-      match_rhs (dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &cmp)
+      dwarf_comparator &_m_cmp;
+      match_rhs (dwarf_comparator &cmp)
 	: _m_cmp (cmp)
       {}
 
@@ -249,7 +266,7 @@ namespace elfutils
 				    typename ait2_map::value_type,
 				    bool>
     {
-      dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &_m_cmp;
+      dwarf_comparator &_m_cmp;
       match_sorted (dwarf_comparator<dwarf1, dwarf2,
 		    ignore_refs, tracker> &cmp)
 	: _m_cmp (cmp)
@@ -315,8 +332,8 @@ namespace elfutils
     struct die_matcher
       : public std::binary_function<cit1, cit2, bool>
     {
-      dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &_m_cmp;
-      die_matcher (dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &cmp)
+      dwarf_comparator &_m_cmp;
+      die_matcher (dwarf_comparator &cmp)
 	: _m_cmp (cmp)
       {}
 
@@ -434,8 +451,11 @@ namespace elfutils
 	return true;
 
       // Simplest mismatches with the cheapest checks first.
-      if (a.tag () != b.tag ()
-	  || a.has_children () != b.has_children ())
+      if (a.tag () != b.tag ())
+	return false;
+
+      const bool any_children = a.has_children ();
+      if (any_children != b.has_children ())
 	return false;
 
       // Now we have to get the tracker involved.
@@ -444,15 +464,40 @@ namespace elfutils
       const typename tracker::right_context_type &rhs
 	= _m_tracker.right_context (ref2);
 
-      // First do the cheap mismatch check on the contexts, then check the
-      // contents and contexts in ascending order of costliness of a check.
-      return (!_m_tracker.context_quick_mismatch (lhs, rhs)
-	      && match (a.attributes (), b.attributes ())
-	      && _m_tracker.context_match (lhs, rhs)
-	      && match (a.children (), b.children ()));
+      // Maybe the tracker has already cached a correspondence of references.
+      if (_m_tracker.quick_reference_match (ref1, ref2))
+	return true;
+
+      /* 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)
+	  || !match (a.attributes (), b.attributes ())
+	  || !_m_tracker.context_match (lhs, rhs))
+	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,
+								 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);
+
+      return result;
     }
 
+    inline explicit dwarf_comparator (const tracker &t)
+      : _m_tracker (t)
+    {}
+
   public:
+    inline dwarf_comparator ()
+    {}
+
     inline bool operator () (const dwarf1 &a, const dwarf2 &b)
     {
       return match (a, b);
diff --git a/libdw/c++/dwarf_tracker b/libdw/c++/dwarf_tracker
index 8382d2e1..70782258 100644
--- a/libdw/c++/dwarf_tracker
+++ b/libdw/c++/dwarf_tracker
@@ -72,34 +72,74 @@ namespace elfutils
     template<typename cu, typename die>
     struct tracker
     {
-      cu _m_root;
-
       typedef std::list<die> die_path;
-      die_path _m_path;
 
       /* We record every DIE we have seen here, mapping its .identity ()
 	 to the die_path of parent DIEs taken to reach it.  */
       typedef std::tr1::unordered_map< ::Dwarf_Off, const die_path> die_map;
-      die_map _m_seen;
+      die_map *_m_seen;
+      bool _m_delete_seen;
+
+      cu _m_root;
+
+      die_path _m_path;
+
+      static const die_path bad_die_path ()
+      {
+	return die_path (1);
+      }
+
+      static bool bad_die_path (const die_path &path)
+      {
+	typename die_path::const_iterator it = path.begin ();
+	if (it == path.end ())
+	  return false;
+	const die &elt = *it;
+	return ++it == path.end () && elt == die ();
+      }
+
+      inline tracker ()
+	: _m_seen (new die_map), _m_delete_seen (true)
+      {}
+
+      inline tracker (const tracker &proto, const die_path &context)
+	: _m_seen (proto._m_seen), _m_delete_seen (false),
+	  _m_root (proto._m_root), _m_path (context)
+      {
+      }
 
       ~tracker ()
       {
 	// We should never be left with a partial walk on the books.
 	assert (_m_path.empty ());
+	if (_m_delete_seen)
+	  delete _m_seen;
       }
 
       inline const die_path &path_to (const die &a)
       {
-	typename die_map::iterator it = _m_seen.find (a->identity ());
-	if (it == _m_seen.end ())
+	::Dwarf_Off id = a->identity ();
+	std::pair<typename die_map::iterator, bool> found
+	  = _m_seen->insert (std::make_pair (id, bad_die_path ()));
+	if (found.second)
 	  {
-	    ::Dwarf_Off id = a->identity ();
+	    /* We have a forward reference.  That is, we didn't
+	       already hit this DIE in our top-level walk and so
+	       it is not in _m_seen yet.  We must do a separate
+	       walk to find it.  */
+
 	    die_path path;
 	    if (!walk_to (*_m_root, id, path))
 	      throw std::runtime_error ("DIE not reachable from CU!");
-	    it = _m_seen.insert (std::make_pair (id, path)).first;
+	    _m_seen->erase (found.first);
+	    found.first = _m_seen->insert (found.first,
+					   std::make_pair (id, path));
 	  }
-	return it->second;
+
+	if (bad_die_path (found.first->second))
+	  abort ();		// XXX
+
+	return found.first->second;
       }
 
       // Return true if this is the droid we're looking for,
@@ -143,7 +183,7 @@ namespace elfutils
       inline void pre_order (const die &a)
       {
 	// Record the path down from the CU to see this DIE.
-	_m_seen.insert (std::make_pair (a->identity (), _m_path));
+	_m_seen->insert (std::make_pair (a->identity (), _m_path));
 	// Append this DIE to the path we'll record for its children.
 	_m_path.push_back (a);
       }
@@ -175,6 +215,9 @@ namespace elfutils
     };
 
   public:
+    inline dwarf_ref_tracker ()
+    {}
+
     inline void start_walk (const cu1 &a, const cu2 &b)
     {
       _m_left.start_walk (a);
@@ -225,6 +268,15 @@ namespace elfutils
     {
       return std::equal (a.begin (), a.end (), b.begin (), equal_enough ());
     }
+
+    // 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 &)
+      : _m_left (tracker1 (proto._m_left, lhs)),
+	_m_right (tracker2 (proto._m_right, rhs))
+    {}
   };
 };
 
diff --git a/src/dwarfcmp.cc b/src/dwarfcmp.cc
index ecadfd52..c779fc49 100644
--- a/src/dwarfcmp.cc
+++ b/src/dwarfcmp.cc
@@ -128,6 +128,7 @@ template<class dwarf1, class dwarf2>
 struct talker : public dwarf_ref_tracker<dwarf1, dwarf2>
 {
   typedef dwarf_tracker_base<dwarf1, dwarf2> _base;
+  typedef dwarf_ref_tracker<dwarf1, dwarf2> _tracker;
   typedef typename _base::cu1 cu1;
   typedef typename _base::cu2 cu2;
   typedef typename _base::die1 die1;
@@ -138,7 +139,17 @@ struct talker : public dwarf_ref_tracker<dwarf1, dwarf2>
   const typename dwarf1::debug_info_entry *a_;
   const typename dwarf2::debug_info_entry *b_;
 
-  inline talker () : a_ (NULL), b_ (NULL) {}
+  inline talker ()
+    : a_ (NULL), b_ (NULL)
+  {}
+
+  inline talker (const talker &proto,
+		 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)
+  {
+  }
 
   inline ostream &location () const
   {