closest yetupstream/roland/dwarf_output-tracker

8 files changed, 156 insertions, 62 deletions

diff --git a/libdw/c++/dwarf b/libdw/c++/dwarf
index 61d9f8da..13257421 100644
--- a/libdw/c++/dwarf
+++ b/libdw/c++/dwarf
@@ -946,7 +946,10 @@ namespace elfutils
       typedef attr_value mapped_type;
       typedef attribute value_type;
 
-      static const bool ordered = false;
+      static inline bool ordered ()
+      {
+	return false;
+      }
 
       inline attributes_type (const attributes_type &a)
 	: attributes_base (a)
@@ -1285,7 +1288,11 @@ namespace elfutils
       typedef std::pair< ::Dwarf_Addr, ::Dwarf_Addr> key_type; // XXX reloc
       typedef key_type value_type;
 
-      static const bool ordered = false;
+      static inline bool ordered ()
+      {
+	return false;
+      }
+
       inline bool canonical () const
       {
 	return false;
@@ -2320,7 +2327,10 @@ namespace elfutils
       typedef _base::iterator iterator;
       typedef _base::const_iterator const_iterator;
 
-      static const bool ordered = true;
+      static inline bool ordered ()
+      {
+	return true;
+      }
 
       struct hasher : public subr::container_hasher<arange_list> {};
 
@@ -2377,7 +2387,7 @@ namespace elfutils
 	// Since we are not const, coalesce in place.
 	coalesce (*this);
 
-	if (list::ordered && other.canonical ()
+	if (list::ordered () && other.canonical ()
 	    && size () != other.size ())
 	  return false;
 
@@ -2386,13 +2396,13 @@ namespace elfutils
 	  return true;
 
 	// If he was sorted and canonical and we didn't match, it's conclusive.
-	if (list::ordered && other.canonical ())
+	if (list::ordered () && other.canonical ())
 	  return false;
 
 	// Make a sorted and canonicalized copy to compare to.
 	_base his (other);
 	if (size () > his.size ()
-	    || (list::ordered && size () == his.size ()))
+	    || (list::ordered () && size () == his.size ()))
 	  // Coalescing can only make him smaller.
 	  return false;
 	coalesce (his);
@@ -2402,7 +2412,7 @@ namespace elfutils
       template<typename list>
       inline bool operator== (const list &other) const
       {
-	if (list::ordered && other.canonical ()
+	if (list::ordered () && other.canonical ()
 	    && size () < other.size ())
 	  // Coalescing can only make us smaller.
 	  return false;
@@ -2412,7 +2422,7 @@ namespace elfutils
 	  return true;
 
 	// Make a non-const copy that will coalesce in its operator==.
-	if (list::ordered && other.canonical ())
+	if (list::ordered () && other.canonical ())
 	  return size () != other.size () && arange_list (*this) == other;
 
 	return arange_list (other) == *this;
diff --git a/libdw/c++/dwarf_comparator b/libdw/c++/dwarf_comparator
index 9bba0058..7ba2475c 100644
--- a/libdw/c++/dwarf_comparator
+++ b/libdw/c++/dwarf_comparator
@@ -160,8 +160,8 @@ namespace elfutils
     {}
 
     inline dwarf_tracker_base (const dwarf_tracker_base &, reference_match &,
-			       const left_context_type &, const die1 &,
-			       const right_context_type &, const die2 &)
+			       const left_context_type &,
+			       const right_context_type &)
     {}
   };
 
@@ -306,7 +306,7 @@ namespace elfutils
 	}
 
       if (it1 != end1 && it2 != end2
-	  && !(attributes1::ordered && attributes2::ordered))
+	  && !(attributes1::ordered () && attributes2::ordered ()))
 	{
 	  /* We have the same number of attributes, but the names don't match.
 
@@ -494,7 +494,7 @@ namespace elfutils
       bool result = !has_children;
       if (has_children)
 	{
-	  tracker t (_m_tracker, matched, lhs, ref1, rhs, ref2);
+	  tracker t (_m_tracker, matched, lhs, rhs);
 	  result = dwarf_comparator (t).match (a.children (), b.children ());
 	}
 
diff --git a/libdw/c++/dwarf_data b/libdw/c++/dwarf_data
index d11efdb3..b4de970d 100644
--- a/libdw/c++/dwarf_data
+++ b/libdw/c++/dwarf_data
@@ -1327,12 +1327,16 @@ namespace elfutils
 
       inline const std::string &string () const
       {
+	if (dynamic_cast<const typename vw::value_source_file *> (_m_value))
+	  return source_file ().name ();
 	return static_cast<const std::string &>
 	  (variant<typename vw::value_string> ());
       }
 
       inline std::string &string ()
       {
+	if (dynamic_cast<const typename vw::value_source_file *> (_m_value))
+	  return source_file ().name ();
 	return static_cast<std::string &>
 	  (variant<typename vw::value_string> ());
       }
@@ -1554,7 +1558,10 @@ namespace elfutils
       typedef typename base_type::value_type value_type;
       typedef typename base_type::mapped_type mapped_type;
 
-      static const bool ordered = true;
+      static inline bool ordered ()
+      {
+	return true;
+      }
 
       template<typename attrs>
       inline operator attrs () const
diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output
index 08a1b154..488ba1e2 100644
--- a/libdw/c++/dwarf_output
+++ b/libdw/c++/dwarf_output
@@ -1092,17 +1092,17 @@ namespace elfutils
       inline bool context_match (const left_context_type &a,
 				 const right_context_type &b)
       {
-	return std::equal (a.begin (), a.end (), b.begin (), equal_enough ());
+	return std::equal (a.begin (), a.end () - 1, b.begin (), equal_enough ());
       }
 
 #if 0		   // XXX
       // Share the _m_seen maps with the prototype tracker,
       // but start a fresh walk from the given starting point.
       inline tracker (const tracker &proto, reference_match &,
-		      const left_context_type &lhs, const die1 &a,
-		      const right_context_type &rhs, const die2 &b)
-	: _m_left (proto._m_left, lhs, a),
-	  _m_right (proto._m_right, rhs, b),
+		      const left_context_type &lhs,
+		      const right_context_type &rhs)
+	: _m_left (proto._m_left, lhs),
+	  _m_right (proto._m_right, rhs),
 	  _m_equiv (proto._m_equiv), _m_delete_equiv (false)
       {
 	// We are starting a recursive consideration of a vs b.
@@ -1401,10 +1401,13 @@ namespace elfutils
 	  // It's finished, resolve the final reference.
 	  return _m_final->second.self ();
 
-	/* This entry is still dangling or pending.
-	   Count the referrer's pending reference.  */
+	/* This entry is still dangling or pending.  Count the referrer's
+	   pending reference.  We account this as a dangling reference
+	   either if we have really not been seen yet at all, or if we are
+	   still under construction--i.e. before resolve_refs has run.  */
 
-	referrer->count_pending (_m_pending == NULL, this, "refer");
+	referrer->count_pending (_m_pending == NULL || _m_building != NULL,
+				 this, "refer");
 	_m_patch.push_back (std::make_pair (referrer, backptr));
 
 	dump () << " nrefs " << _m_patch.size () << "\n";
@@ -1854,6 +1857,9 @@ namespace elfutils
 	assert (_m_out == NULL);
 	if (unlikely (_m_in->_m_final == NULL))
 	  {
+	    std::cout.flush ();
+	    _m_copier->dump_seen ();
+	    std::cout.flush ();
 	    assert (_m_in->_m_pending != NULL);
 	    assert (_m_in->_m_pending->dangling ());
 	    throw std::runtime_error
diff --git a/libdw/c++/dwarf_tracker b/libdw/c++/dwarf_tracker
index ee4b02fb..23a8a6af 100644
--- a/libdw/c++/dwarf_tracker
+++ b/libdw/c++/dwarf_tracker
@@ -54,6 +54,7 @@
 #include "dwarf_comparator"
 #include <tr1/unordered_map>
 #include <tr1/unordered_set>
+#include <deque>
 
 namespace elfutils
 {
@@ -66,26 +67,50 @@ namespace elfutils
     typedef typename dw::debug_info_entry::children_type::const_iterator die;
 
     /* We maintain the current path down the logical DIE tree from the CU
-       as a stack of iterators pointing to the DIE at each level.  */
-    typedef std::list<die> die_path;
+       as a stack of iterators pointing to the DIE at each level.
+
+       Note that the path to a DIE includes the iterator to that DIE
+       itself as the last element.  This is necessary to permit sharing
+       our _m_seen cache across CUs.  That sharing is useful when CUs
+       might share children (i.e. they use DW_TAG_imported_unit).
+       But when they do, then the "construct a derived tracker that
+       jump-starts a walk" case for following a reference might be for
+       a reference to another CU than the one the base tracker is
+       walking (_m_root).  When path_to finds the "context" path to the
+       referent, the iterator that jump-starts a new walk must be an
+       iterator pointing to the referent, but must be an iterator
+       somewhere in the _m_root CU's tree, not another CU's.
+
+       NOTE!!! XXX
+       This scenario means we can have a die_path in our _m_seen that
+       is not from our current _m_root CU.  This is only safe as long
+       as we are sure that we have already completely walked the other
+       CU that die_path came from so all its entries are in _m_seen.
+       This ensures that a derived tracker that jump-starts its walk at
+       a path in another CU will never actually have to do any walking.
+       If it ever walked, it could go awry failing to recognize the end
+       of its CU's children list--it's not _m_root->children ().end ().
+       If we want to generalize dwarf_path_finder so it can be used as
+       a generic cache when we might not have walked whole CUs, then we
+       need to change things.  We'd have to store _m_root along with
+       _m_path in _m_seen so that a derived tracker made from path_to
+       "context" can use the right _m_root.
+    */
+    typedef std::deque<die> die_path;
 
   private:
-    // We use a singleton list of a default-constructed iterator as a marker.
+    // We use an empty list as a marker; every path includes at least one DIE.
     static inline const die_path bad_die_path ()
     {
-      return die_path (1);
+      return die_path ();
     }
     static inline 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 ();
+      return path.empty ();
     }
 
-    /* We record every DIE we have seen here, mapping its .identity ()
-       to the die_path of parent DIEs taken to reach it.  */
+    /* We record every DIE we have seen here, mapping its .identity () to
+       the die_path of parent DIEs taken to reach it, including itself.  */
     typedef std::tr1::unordered_map<dwarf::debug_info_entry::identity_type,
 				    const die_path> die_map;
     die_map *_m_seen;
@@ -111,14 +136,13 @@ namespace elfutils
       : _m_seen (proto._m_seen), _m_delete_seen (false)
     {}
 
-    // Construct a derived tracker that jump-starts a walk.
+    /* Construct a derived tracker that jump-starts a walk.
+       CONTEXT is from a path_to call made on PROTO.  */
     inline dwarf_path_finder (const dwarf_path_finder &proto,
-			      const die_path &context, const die &there)
+			      const die_path &context)
       : _m_seen (proto._m_seen), _m_delete_seen (false),
 	_m_root (proto._m_root), _m_path (context)
-    {
-      _m_path.push_back (there);
-    }
+    {}
 
     inline ~dwarf_path_finder ()
     {
@@ -156,15 +180,18 @@ namespace elfutils
     struct step
     {
       dwarf_path_finder *_m_walker;
-      inline step (dwarf_path_finder *w, const die &here)
+      inline step (dwarf_path_finder *w, const die &here,
+		   bool record = true)
 	: _m_walker (w)
       {
-	// Record the path down from the CU to see this DIE.
-	_m_walker->_m_seen->insert (std::make_pair (here->identity (),
-						    _m_walker->_m_path));
-
-	// Append this DIE to the path we'll record for its children.
+	// Append this DIE to the path we'll record for it and its children.
 	_m_walker->_m_path.push_back (here);
+
+	// Record the path down from the CU to see this DIE.
+	assert (!bad_die_path (_m_walker->_m_path));
+	if (record)
+	  _m_walker->_m_seen->insert (std::make_pair (here->identity (),
+						      _m_walker->_m_path));
       }
       inline ~step ()
       {
@@ -226,6 +253,10 @@ namespace elfutils
 		 Those can invalidate old iterators.  */
 	      cache = _m_seen->find (there);
 	      _m_seen->erase (cache);
+
+	      // Include the iterator we've found in the path to itself.
+	      step into (this, it, false);
+
 	      cache = _m_seen->insert (cache, std::make_pair (there, _m_path));
 	      return true;
 	    }
@@ -302,8 +333,7 @@ namespace elfutils
       die_path _m_save;
       inline step_up (dwarf_path_finder *w)
 	: _m_walker (w), _m_save (w->_m_path)
-      {
-      }
+      {}
       inline ~step_up ()
       {
 	_m_walker->_m_path.swap (_m_save);
@@ -472,7 +502,8 @@ namespace elfutils
     inline bool context_match (const left_context_type &a,
 			       const right_context_type &b)
     {
-      return std::equal (a.begin (), a.end (), b.begin (), equal_enough ());
+      // Ignore the last element, which is the target DIE itself.
+      return std::equal (a.begin (), a.end () - 1, b.begin (), equal_enough ());
     }
 
     class reference_match
@@ -539,10 +570,10 @@ namespace elfutils
     // 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, reference_match &,
-			      const left_context_type &lhs, const die1 &a,
-			      const right_context_type &rhs, const die2 &b)
-      : _m_left (proto._m_left, lhs, a),
-	_m_right (proto._m_right, rhs, b),
+			      const left_context_type &lhs,
+			      const right_context_type &rhs)
+      : _m_left (proto._m_left, lhs),
+	_m_right (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/libdw/c++/values.cc b/libdw/c++/values.cc
index f012434b..c8f65bb3 100644
--- a/libdw/c++/values.cc
+++ b/libdw/c++/values.cc
@@ -63,7 +63,6 @@ using namespace elfutils;
 using namespace std;
 
 #include "dwarf-knowledge.cc"
-
 
 // dwarf::attr_value disambiguation and dispatch.
 
diff --git a/src/dwarfcmp.cc b/src/dwarfcmp.cc
index 1ab2744a..91081587 100644
--- a/src/dwarfcmp.cc
+++ b/src/dwarfcmp.cc
@@ -146,9 +146,9 @@ struct talker : public dwarf_ref_tracker<dwarf1, dwarf2>
   {}
 
   inline talker (const talker &proto, typename _tracker::reference_match &m,
-		 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), m, l, a, r, b),
+		 const typename _tracker::left_context_type &l,
+		 const typename _tracker::right_context_type &r)
+    : _tracker (static_cast<const _tracker &> (proto), m, l, r),
       a_ (NULL), b_ (NULL)
   {
   }
diff --git a/tests/print-die.hh b/tests/print-die.hh
index 7b4fa3f5..d946a9eb 100644
--- a/tests/print-die.hh
+++ b/tests/print-die.hh
@@ -39,6 +39,8 @@
 
 static bool print_offset;
 static bool sort_attrs;
+static bool elide_refs;
+static bool dump_refs;
 
 static enum { copy_none, copy_edit, copy_output } make_copy;
 
@@ -63,6 +65,20 @@ print_die_main (int &argc, char **&argv, unsigned int &depth)
       ++argv;
     }
 
+  if (argc > 1 && !strcmp (argv[1], "--norefs"))
+    {
+      elide_refs = true;
+      --argc;
+      ++argv;
+    }
+
+  if (argc > 1 && !strcmp (argv[1], "--dump-refs"))
+    {
+      dump_refs = true;
+      --argc;
+      ++argv;
+    }
+
   if (argc > 1 && !strcmp (argv[1], "--sort-attrs"))
     {
       sort_attrs = true;
@@ -92,7 +108,8 @@ print_die_main (int &argc, char **&argv, unsigned int &depth)
 }
 
 static int next_ref = 1;
-typedef tr1::unordered_map< ::Dwarf_Off, int> refs_map;
+typedef tr1::unordered_map<dwarf::debug_info_entry::identity_type,
+			   int> refs_map;
 
 template<typename attrs_type,
 	 void (*act) (const typename attrs_type::value_type &, refs_map &)
@@ -114,7 +131,7 @@ public:
 
   static inline void walk (const attrs_type &attrs, refs_map &r)
   {
-    if (attrs_type::ordered || !sort_attrs)
+    if (attrs_type::ordered () || !sort_attrs)
       for (iterator i = attrs.begin (); i != attrs.end (); ++i)
 	(*act) (*i, r);
     else
@@ -133,8 +150,13 @@ void
 print_attr (const typename attrs_type::value_type &attr, refs_map &refs)
 {
   if (!print_offset && attr.second.what_space () == dwarf::VS_reference)
-    cout << " " << dwarf::attributes::name (attr.first) << "=\"#ref"
-	 << dec << refs[attr.second.reference ()->identity ()] << "\"";
+    {
+      if (elide_refs)
+	cout << " " << dwarf::attributes::name (attr.first) << "=\"ref\"";
+      else
+	cout << " " << dwarf::attributes::name (attr.first) << "=\"#ref"
+	     << dec << refs[attr.second.reference ()->identity ()] << "\"";
+    }
   else
     cout << " " << to_string (attr);
 }
@@ -174,6 +196,9 @@ prewalk_die (const typename file::debug_info_entry &die, refs_map &refs)
   prewalk_attrs (die.attributes (), refs);
 }
 
+static int nth;
+static std::map<int, int> nth_ref;
+
 template<typename file>
 static void
 print_die (const typename file::debug_info_entry &die,
@@ -182,14 +207,21 @@ print_die (const typename file::debug_info_entry &die,
   string prefix (indent, ' ');
   const string tag = dwarf::tags::name (die.tag ());
 
+  ++nth;
+  if (dump_refs)
+    cout << dec << nth << ": ";
+
   cout << prefix << "<" << tag;
   if (print_offset)
-    cout << " offset=[" << die.offset () << "]";
-  else
+    cout << " offset=[" << hex << die.offset () << "]";
+  else if (!elide_refs)
     {
       refs_map::const_iterator it = refs.find (die.identity ());
       if (it != refs.end ())
-	cout << " ref=\"ref" << dec << it->second << "\"";
+	{
+	  cout << " ref=\"ref" << dec << it->second << "\"";
+	  nth_ref[nth] = it->second;
+	}
     }
 
   print_attrs (die.attributes (), refs);
@@ -214,6 +246,12 @@ print_die (const typename file::debug_info_entry &die,
     cout << "/>\n";
 }
 
+static inline void
+dump_nth (pair<int, int> p)
+{
+  cout << dec << p.first << ": ref" << p.second << "\n";
+}
+
 template<typename file>
 static void
 print_cu (const typename file::compile_unit &cu, const unsigned int limit)
@@ -223,10 +261,13 @@ print_cu (const typename file::compile_unit &cu, const unsigned int limit)
 
   refs_map refs;
 
-  if (!print_offset)
+  if (!print_offset && !elide_refs)
     prewalk_die<file> (die, refs);
 
   print_die<file> (die, 1, limit, refs);
+
+  if (dump_refs)
+    for_each (nth_ref.begin (), nth_ref.end (), dump_nth);
 }
 
 template<typename file>