Implement the reference tracker, revamp dwarfcmp using new dwarf_comparator class.

16 files changed, 1389 insertions, 246 deletions

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 97ff01fa..9d185441 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,20 @@
+2009-06-19  Roland McGrath  <roland@redhat.com>
+
+	* c++/dwarf_comparator: New file.
+	* c++/dwarf_tracker: New file.
+	* Makefile.am (pkginclude_HEADERS): Add them.
+
+	* c++/dwarf_edit: Miscellaneous fixes.
+	Support dwarf_enum, to_string for attributes.
+	* c++/known.cc: Support dwarf_edit::dwarf_enum.
+	* c++/edit-values.cc: Support to_string for attributes.
+	* c++/values.cc: Rejiggered accordingly.
+
+	* c++/dwarf-knowledge.cc (expected_value_space): Expect unit_reference
+	only for DW_TAG_imported_unit.
+
+	* c++/dwarf: Miscellaneous fixes.
+
 2009-04-02  Roland McGrath  <roland@redhat.com>
 
 	* Makefile.am (noinst_HEADERS): Add known-dwarf.h and
diff --git a/libdw/Makefile.am b/libdw/Makefile.am
index 2e35cdc1..b957c168 100644
--- a/libdw/Makefile.am
+++ b/libdw/Makefile.am
@@ -49,7 +49,8 @@ endif
 include_HEADERS = dwarf.h
 pkginclude_HEADERS = libdw.h \
 		     c++/subr.hh \
-		     c++/dwarf c++/dwarf_edit
+		     c++/dwarf c++/dwarf_edit \
+		     c++/dwarf_tracker c++/dwarf_comparator
 
 libdw_a_SOURCES = dwarf_begin.c dwarf_begin_elf.c dwarf_end.c dwarf_getelf.c \
 		  dwarf_getpubnames.c dwarf_getabbrev.c dwarf_tag.c \
diff --git a/libdw/c++/dwarf b/libdw/c++/dwarf
index 591d5e1d..fab89611 100644
--- a/libdw/c++/dwarf
+++ b/libdw/c++/dwarf
@@ -62,6 +62,7 @@
 #include <stack>
 #include <algorithm>
 #include <functional>
+#include <tr1/unordered_map>
 
 /* Abstractly, one DWARF object file consists of a few containers.
    (We omit .debug_frame for now.  It does not interact with the others.)
@@ -154,6 +155,12 @@
 // DWARF reader interfaces: front end to <libdw.h> routines
 namespace elfutils
 {
+  template<typename type>
+  inline std::string to_string (const type &item)
+  {
+    return item.to_string ();
+  }
+
   template<typename key1, typename value1, class pair2>
   inline bool operator== (const std::pair<key1, value1> &a, const pair2 &b)
   {
@@ -169,6 +176,9 @@ namespace elfutils
     const elt *_m_array;
 
   public:
+    typedef size_t size_type;
+    typedef ptrdiff_t difference_type;
+    typedef elt value_type;
     typedef const elt *const_iterator;
 
     const_vector ()
@@ -321,6 +331,11 @@ namespace elfutils
 
       public:
 
+	inline const_iterator ()
+	  : _m_raw (), _m_end ()
+	{
+	}
+
 	const_iterator (const const_iterator &i)
 	  : _m_raw (i._m_raw), _m_end (i._m_end) {}
 
@@ -456,7 +471,8 @@ namespace elfutils
       template<typename die>
       bool operator== (const die &other) const
       {
-	return (attributes () == other.attributes ()
+	return (tag () == other.tag ()
+		&& attributes () == other.attributes ()
 		&& children () == other.children ());
       }
       template<typename die>
@@ -474,6 +490,13 @@ namespace elfutils
       {
 	return dwarf::ranges (*this);
       }
+
+      /* This is an identity pointer that only matches the very same
+	 DIE in the very same file (same opened Dwarf instance).  */
+      inline ::Dwarf_Off identity () const
+      {
+	return (uintptr_t) _m_die.addr;
+      }
     };
 
     // Container for raw list of child DIEs, intended to be a compatible with
@@ -505,7 +528,9 @@ namespace elfutils
       private:
 	debug_info_entry _m_die;
 
-	inline const_iterator () {}
+	inline const_iterator ()
+	{}
+
 	inline const_iterator (const debug_info_entry &parent)
 	{
 	  int result = ::dwarf_child (parent.thisdie (), &_m_die._m_die);
@@ -538,6 +563,13 @@ namespace elfutils
 	  return *this;
 	}
 
+	// Assign directly from a DIE, as if "taking its address".
+	inline const_iterator &operator= (const debug_info_entry &die)
+	{
+	  _m_die = die;
+	  return *this;
+	}
+
 	inline bool operator== (const const_iterator &other) const
 	{
 	  return _m_die._m_die.addr == other._m_die._m_die.addr;
@@ -566,7 +598,7 @@ namespace elfutils
       {
 	return const_iterator (_m_die);
       }
-      inline const_iterator end () const
+      static inline const_iterator end ()
       {
 	return const_iterator ();
       }
@@ -722,17 +754,16 @@ namespace elfutils
 
 	typedef raw_children::const_iterator raw_iterator;
 	std::stack<raw_iterator> _m_stack;
-	const raw_iterator _m_end;
 
-	/* Push and pop until either _m_stack.top () == _m_end or
-	   it's looking at a DIE other than DW_TAG_imported_unit.  */
+	/* Push and pop until either _m_stack.top () == raw_children::end ()
+	   or it's looking at a DIE other than DW_TAG_imported_unit.  */
 	inline void jiggle ()
 	{
 	  while (true)
 	    {
 	      raw_iterator &i = _m_stack.top ();
 
-	      if (i == _m_end)
+	      if (i == raw_children::end ())
 		{
 		  /* We're at the end of this raw DIE.
 		     Pop out to the iterator on the importing unit.  */
@@ -755,18 +786,25 @@ namespace elfutils
 	    }
 	}
 
-	inline const_iterator (const raw_iterator &end) : _m_end (end) {}
-
-	inline const_iterator (const raw_iterator &end, const raw_iterator &i)
-	  : _m_end (end)
+      public:
+	inline const_iterator (const raw_iterator &i)
 	{
 	  _m_stack.push (i);
 	  jiggle ();
 	}
 
-      public:
 	inline const_iterator (const const_iterator &i)
-	  : _m_stack (i._m_stack), _m_end (i._m_end) {}
+	  : _m_stack (i._m_stack)
+	{}
+
+	// Construct directly from a DIE, as if "taking its address".
+	inline const_iterator (const debug_info_entry &die)
+	{
+	  raw_iterator it;
+	  it = die;
+	  _m_stack.push (it);
+	  jiggle ();
+	}
 
 	inline const_iterator &operator= (const const_iterator &other)
 	{
@@ -808,8 +846,7 @@ namespace elfutils
 
       const_iterator begin () const
       {
-	return const_iterator (raw_children::end (),
-			       raw_children::begin ());
+	return const_iterator (raw_children::begin ());
       }
       const_iterator end () const
       {
@@ -856,6 +893,8 @@ namespace elfutils
       typedef attr_value mapped_type;
       typedef attribute value_type;
 
+      static const bool ordered = false;
+
       inline attributes (const class attributes &a)
 	: attributes_base (a) {}
 
@@ -1058,8 +1097,7 @@ namespace elfutils
       // attr_value (const attr_value &v) : _m_attr (v.attr) {}
 
       value_space what_space () const;
-
-      std::string to_string () const;
+      inline std::string to_string () const;
 
       // Return an iterator on which * will yield the referent debug_info_entry.
       inline debug_info_entry::raw_children::const_iterator reference () const
@@ -1124,8 +1162,9 @@ namespace elfutils
 	    {
 	    case VS_reference:
 	    case VS_unit_reference:
-	      return true; // XXX Reference identity check (?)
-	      //return reference ()->offset () == other.reference ()->offset ();
+	      // Stateless reference equality is just identity.
+	      return (reference ()->identity ()
+		      == other.reference ()->identity ());
 
 	    case VS_flag:
 	      return flag () == other.flag ();
@@ -1337,6 +1376,8 @@ namespace elfutils
       typedef std::pair< ::Dwarf_Addr, ::Dwarf_Addr> key_type; // XXX reloc
       typedef key_type value_type;
 
+      static const bool ordered = false;
+
       range_list (const range_list &other) : _m_attr (other._m_attr) {}
 
       std::string to_string () const;
@@ -1469,7 +1510,8 @@ namespace elfutils
 	typename table::const_iterator j = other.begin ();
 	return subr::container_equal
 	  (++i, end (), ++j, other.end (),
-	   subr::name_equal<typename table::value_type> ());
+	   subr::deref<directory_table, table,
+	   	       subr::name_equal<typename table::value_type> > ());
       }
 
     public:
@@ -1772,6 +1814,24 @@ namespace elfutils
 
       const char *identifier () const;
       const char *name () const;
+
+      // Return the DW_AT_* indicating which enum this value belongs to.
+      unsigned int which () const
+      {
+	return _m_attr.whatattr ();
+      }
+
+      template<typename constant>
+      inline bool operator== (const constant &other) const
+      {
+	return (static_cast<unsigned int> (*this)
+		== static_cast<unsigned int> (other));
+      }
+      template<typename constant>
+      inline bool operator!= (const constant &other) const
+      {
+	return !(*this == other);
+      }
     };
 
     // This describes one attribute, equivalent to pair<const int, attr_value>.
@@ -2013,6 +2073,10 @@ namespace elfutils
 	  : _m_file (&file), _m_next (next) {}
 
       public:
+	inline const_iterator ()
+	  : _m_die (), _m_file (NULL), _m_next (-1)
+	{}
+
 	inline const_iterator (const const_iterator &i)
 	  : _m_die (i._m_die), _m_file (i._m_file), _m_next (i._m_next) {}
 
@@ -2174,11 +2238,40 @@ namespace elfutils
       typedef _base::iterator iterator;
       typedef _base::const_iterator const_iterator;
 
+      static const bool ordered = true;
+
       arange_list () {}
       arange_list (const arange_list &other)
 	: _base (static_cast<const _base &> (other)) {}
 
       std::string to_string () const;
+
+      template<typename list>
+      inline bool operator== (const list &other)
+      {
+	coalesce (*this);
+	if (subr::container_equal (*this, other))
+	  return true;
+	std::set<key_type> his = other;
+	coalesce (his);
+	return *this == his;
+      }
+
+      template<typename list>
+      inline bool operator== (const list &other) const
+      {
+	if (subr::container_equal (*this, other))
+	  return true;
+	std::set<key_type> his = other;
+	coalesce (his);
+	// We have to make a copy just to coalesce, since we're const.
+	// Don't bother if we couldn't possibly match afterwards.
+	if (size () <= his.size ())
+	  return false;
+	std::set<key_type> mine = *this;
+	coalesce (mine);
+	return mine == his;
+      }
     };
 
   private:
@@ -2200,26 +2293,26 @@ namespace elfutils
   private:
     static bool adjacency (const arange_list::key_type &a,
 			   const arange_list::key_type &b)
-      {
-	return a.second == b.first;
-      }
+    {
+      return a.second == b.first;
+    }
 
-      // Coalesce adjacent ranges.
-      static void coalesce (std::set<arange_list::key_type> &set)
-      {
-	for (std::set<arange_list::key_type>::iterator i = set.begin ();
-	     (i = std::adjacent_find (i, set.end (), adjacency)) != set.end ();
-	     ++i)
-	  {
-	    std::set<arange_list::key_type>::iterator j = i;
-	    std::set<arange_list::key_type>::iterator k = ++j;
-	    while (++k != set.end () && adjacency (*j, *k))
-	      ++j;
-	    const arange_list::key_type joined (i->first, j->second);
-	    set.erase (i, k);
-	    i = set.insert (joined).first;
-	  }
-      }
+    // Coalesce adjacent ranges.
+    static void coalesce (std::set<arange_list::key_type> &set)
+    {
+      for (std::set<arange_list::key_type>::iterator i = set.begin ();
+	   (i = std::adjacent_find (i, set.end (), adjacency)) != set.end ();
+	   ++i)
+	{
+	  std::set<arange_list::key_type>::iterator j = i;
+	  std::set<arange_list::key_type>::iterator k = ++j;
+	  while (++k != set.end () && adjacency (*j, *k))
+	    ++j;
+	  const arange_list::key_type joined (i->first, j->second);
+	  set.erase (i, k);
+	  i = set.insert (joined).first;
+	}
+    }
   };
 
   inline class dwarf::debug_info_entry::raw_children
@@ -2258,6 +2351,23 @@ namespace elfutils
   {
     return const_iterator (*this, 1);
   }
+
+  // Explicit specialization.
+  template<>
+  std::string to_string<dwarf::attr_value> (const dwarf::attr_value &);
+  inline std::string dwarf::attr_value::to_string () const
+  {
+    return elfutils::to_string (*this); // Use that.
+  }
+
+  // Explicit specialization.
+  template<>
+  std::string to_string<dwarf::dwarf_enum> (const dwarf::dwarf_enum &);
+  inline std::string dwarf::dwarf_enum::to_string () const
+  {
+    return elfutils::to_string (*this); // Use that.
+  }
+
 };
 
 #endif	// <elfutils/dwarf>
diff --git a/libdw/c++/dwarf-knowledge.cc b/libdw/c++/dwarf-knowledge.cc
index de526fe5..698d49ac 100644
--- a/libdw/c++/dwarf-knowledge.cc
+++ b/libdw/c++/dwarf-knowledge.cc
@@ -98,7 +98,7 @@ expected_value_space (int attr, int tag)
       return VS(discr_list);
 
     case DW_AT_import:
-      return VS(unit_reference);
+      return tag == DW_TAG_imported_unit ? VS(unit_reference) : VS(reference);
 
     case DW_AT_comp_dir:
       return VS(source_file);
diff --git a/libdw/c++/dwarf_comparator b/libdw/c++/dwarf_comparator
new file mode 100644
index 00000000..11261b42
--- /dev/null
+++ b/libdw/c++/dwarf_comparator
@@ -0,0 +1,467 @@
+/* elfutils::dwarf_comparator -- -*- C++ -*- templates for comparing DWARF data
+   Copyright (C) 2009 Red Hat, Inc.
+   This file is part of Red Hat elfutils.
+
+   Red Hat elfutils is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by the
+   Free Software Foundation; version 2 of the License.
+
+   Red Hat elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License along
+   with Red Hat elfutils; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
+
+   In addition, as a special exception, Red Hat, Inc. gives You the
+   additional right to link the code of Red Hat elfutils with code licensed
+   under any Open Source Initiative certified open source license
+   (http://www.opensource.org/licenses/index.php) which requires the
+   distribution of source code with any binary distribution and to
+   distribute linked combinations of the two.  Non-GPL Code permitted under
+   this exception must only link to the code of Red Hat elfutils through
+   those well defined interfaces identified in the file named EXCEPTION
+   found in the source code files (the "Approved Interfaces").  The files
+   of Non-GPL Code may instantiate templates or use macros or inline
+   functions from the Approved Interfaces without causing the resulting
+   work to be covered by the GNU General Public License.  Only Red Hat,
+   Inc. may make changes or additions to the list of Approved Interfaces.
+   Red Hat's grant of this exception is conditioned upon your not adding
+   any new exceptions.  If you wish to add a new Approved Interface or
+   exception, please contact Red Hat.  You must obey the GNU General Public
+   License in all respects for all of the Red Hat elfutils code and other
+   code used in conjunction with Red Hat elfutils except the Non-GPL Code
+   covered by this exception.  If you modify this file, you may extend this
+   exception to your version of the file, but you are not obligated to do
+   so.  If you do not wish to provide this exception without modification,
+   you must delete this exception statement from your version and license
+   this file solely under the GPL without exception.
+
+   Red Hat elfutils is an included package of the Open Invention Network.
+   An included package of the Open Invention Network is a package for which
+   Open Invention Network licensees cross-license their patents.  No patent
+   license is granted, either expressly or impliedly, by designation as an
+   included package.  Should you wish to participate in the Open Invention
+   Network licensing program, please visit www.openinventionnetwork.com
+   <http://www.openinventionnetwork.com>.  */
+
+#ifndef _ELFUTILS_DWARF_COMPARATOR
+#define _ELFUTILS_DWARF_COMPARATOR	1
+
+#include "dwarf"
+
+namespace elfutils
+{
+  // Prototypical stub for reference tracker object.
+  // This keeps no state, and no two contexts ever match.
+  template<class dwarf1, class dwarf2>
+  class dwarf_tracker_base
+  {
+  protected:
+    typedef typename dwarf1::compile_units::const_iterator cu1;
+    typedef typename dwarf2::compile_units::const_iterator cu2;
+    typedef typename dwarf1::debug_info_entry::children::const_iterator die1;
+    typedef typename dwarf2::debug_info_entry::children::const_iterator die2;
+    typedef typename dwarf1::debug_info_entry::attributes::const_iterator attr1;
+    typedef typename dwarf2::debug_info_entry::attributes::const_iterator attr2;
+
+  public:
+    inline void start_walk (const cu1 &a, const cu2 &b)
+    {
+    }
+    inline void finish_walk (const cu1 &a, const cu2 &b)
+    {
+    }
+    inline void pre_order (const die1 &a, const die2 &b)
+    {
+    }
+    inline void post_order (const die1 &a, const die2 &b)
+    {
+    }
+
+    inline void visit (const typename dwarf1::debug_info_entry &a,
+		       const typename dwarf2::debug_info_entry &b)
+    {
+    }
+
+    inline void mismatch (const cu1 &it1, const cu1 &end1,
+			  const cu2 &it2, const cu2 &end2)
+    {
+    }
+
+    inline void mismatch (const die1 &it1, const die1 &end1,
+			  const die2 &it2, const die2 &end2)
+    {
+    }
+
+    inline void mismatch (const attr1 &it1, const attr1 &end1,
+			  const attr2 &it2, const attr2 &end2)
+    {
+    }
+
+    struct left_context_type {};
+    inline const left_context_type left_context (const die1 &die)
+    {
+      return left_context_type ();
+    }
+
+    struct right_context_type {};
+    inline const right_context_type right_context (const die2 &die)
+    {
+      return right_context_type ();
+    }
+
+    inline bool context_quick_mismatch (const left_context_type &a,
+					const right_context_type &b)
+
+    {
+      return true;
+    }
+
+    inline bool context_match (const left_context_type &a,
+			       const right_context_type &b)
+    {
+      return false;
+    }
+  };
+
+  template<class dwarf1, class dwarf2,
+	   bool ignore_refs = false,
+	   class tracker = dwarf_tracker_base<dwarf1, dwarf2>
+	   >
+  class dwarf_comparator
+    : public std::binary_function<dwarf1, dwarf2, bool>
+  {
+  private:
+    tracker _m_tracker;
+
+    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)
+	: _m_cmp (cmp)
+      {}
+
+      inline bool operator () (const item1 &a, const item2 &b)
+      {
+	return _m_cmp.match (a, b);
+      }
+    };
+#define MATCHER(item) \
+    matcher<typename dwarf1::item, typename dwarf2::item>
+
+    inline bool match (const dwarf1 &a, const dwarf2 &b)
+    {
+      return match (a.compile_units (), b.compile_units ());
+    }
+
+    typedef typename dwarf1::compile_units compile_units1;
+    typedef typename dwarf2::compile_units compile_units2;
+    typedef typename dwarf1::compile_units::const_iterator cu1_it;
+    typedef typename dwarf2::compile_units::const_iterator cu2_it;
+    inline bool match (const compile_units1 &a, const compile_units2 &b)
+    {
+      cu1_it it1 = a.begin ();
+      cu2_it it2 = b.begin ();
+      const cu1_it end1 = a.end ();
+      const cu2_it end2 = b.end ();
+      if (subr::container_equal
+	  (it1, end1, it2, end2,
+	   MATCHER (compile_units::const_iterator) (*this)))
+	return true;
+      _m_tracker.mismatch (it1, end1, it2, end2);
+      return false;
+    }
+
+    typedef typename dwarf1::debug_info_entry die1;
+    typedef typename dwarf2::debug_info_entry die2;
+    inline bool match (const cu1_it &a, const cu2_it &b)
+    {
+      bool result;
+      _m_tracker.start_walk (a, b);
+      try
+	{
+	  result = match (static_cast<die1> (*a), static_cast<die2> (*b));
+	}
+      catch (...)
+	{
+	  _m_tracker.finish_walk (a, b);
+	  throw;
+	}
+      _m_tracker.finish_walk (a, b);
+      return result;
+    }
+
+    inline bool match (const die1 &a, const die2 &b)
+    {
+      _m_tracker.visit (a, b);
+      return (a.tag () == b.tag ()
+	      && match (a.attributes (), b.attributes ())
+	      && match (a.children (), b.children ()));
+    }
+
+    template<typename in, typename out>
+    static inline void populate (out &o, const in &map)
+    {
+      for (typename in::const_iterator i = map.begin ();
+	   i != map.end ();
+	   ++i)
+	o.insert (std::make_pair ((*i).first, i));
+    }
+
+    typedef typename dwarf1::debug_info_entry::attributes attributes1;
+    typedef typename dwarf2::debug_info_entry::attributes attributes2;
+    typedef typename attributes1::const_iterator ait1;
+    typedef typename attributes2::const_iterator ait2;
+    typedef std::map<int, ait1> ait1_map;
+    typedef std::map<int, ait2> ait2_map;
+
+    struct match_lhs
+      : public std::binary_function<ait1, ait2, bool>
+    {
+      inline bool operator () (const ait1 &it1, const ait2 &it2)
+      {
+	return (*it1).first == (*it2).first;
+      }
+    };
+
+    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)
+	: _m_cmp (cmp)
+      {}
+
+      inline bool operator () (const ait1 &it1, const ait2 &it2)
+      {
+	return _m_cmp.match ((*it1).second, (*it2).second);
+      }
+    };
+
+    struct match_sorted
+      : public std::binary_function<typename ait1_map::value_type,
+				    typename ait2_map::value_type,
+				    bool>
+    {
+      dwarf_comparator<dwarf1, dwarf2, ignore_refs, tracker> &_m_cmp;
+      match_sorted (dwarf_comparator<dwarf1, dwarf2,
+		    ignore_refs, tracker> &cmp)
+	: _m_cmp (cmp)
+      {}
+
+      inline bool operator () (const typename ait1_map::value_type &x,
+			       const typename ait2_map::value_type &y)
+      {
+	return (x.first == y.first
+		&& _m_cmp.match ((*x.second).second, (*y.second).second));
+      }
+    };
+
+    inline bool match (const attributes1 &a, const attributes2 &b)
+    {
+      ait1 it1 = a.begin ();
+      ait2 it2 = b.begin ();
+      const ait1 end1 = a.end ();
+      const ait2 end2 = b.end ();
+      if (subr::container_equal (it1, end1, it2, end2, match_lhs ()))
+	{
+	  // The set of attributes matches, in order.  Compare the values.
+	  it1 = a.begin ();
+	  it2 = b.begin ();
+	  if (subr::container_equal (it1, end1, it2, end2, match_rhs (*this)))
+	    return true;
+	  _m_tracker.mismatch (it1, end1, it2, end2);
+	  return false;
+	}
+
+      if (it1 != end1 && it2 != end2
+	  && !(attributes1::ordered && attributes2::ordered))
+	{
+	  /* We have the same number of attributes, but the names don't match.
+
+	   */
+
+	  ait1_map sorted1;
+	  populate (sorted1, a);
+
+	  ait2_map sorted2;
+	  populate (sorted2, b);
+
+	  std::pair<typename ait1_map::iterator,
+	    	    typename ait2_map::iterator> result
+	    = std::mismatch (sorted1.begin (), sorted1.end (),
+			     sorted2.begin (), match_sorted (*this));
+	  if (result.first == sorted1.end () && result.second == sorted2.end ())
+	    return true;
+
+	  it1 = result.first->second;
+	  it2 = result.second->second;
+	}
+
+      _m_tracker.mismatch (it1, end1, it2, end2);
+      return false;
+    }
+
+    typedef typename dwarf1::debug_info_entry::children children1;
+    typedef typename dwarf2::debug_info_entry::children children2;
+    typedef typename children1::const_iterator cit1;
+    typedef typename children2::const_iterator cit2;
+    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)
+	: _m_cmp (cmp)
+      {}
+
+      inline bool operator () (const cit1 &a, const cit2 &b)
+      {
+	bool result;
+	_m_cmp._m_tracker.pre_order (a, b);
+	try
+	  {
+	    result = _m_cmp.match (*a, *b);
+	  }
+	catch (...)
+	  {
+	    _m_cmp._m_tracker.post_order (a, b);
+	    throw;
+	  }
+	_m_cmp._m_tracker.post_order (a, b);
+	return result;
+      }
+    };
+    inline bool match (const children1 &a, const children2 &b)
+    {
+      cit1 it1 = a.begin ();
+      cit2 it2 = b.begin ();
+      const cit1 end1 = a.end ();
+      const cit2 end2 = b.end ();
+      if (subr::container_equal (it1, end1, it2, end2, die_matcher (*this)))
+	return true;
+      _m_tracker.mismatch (it1, end1, it2, end2);
+      return false;
+    }
+
+    typedef typename dwarf1::attribute attribute1;
+    typedef typename dwarf2::attribute attribute2;
+    inline bool match (const attribute1 &a, const attribute2 &b)
+    {
+      return a.first == b.first && match (a.second, b.second);
+    }
+
+    typedef typename dwarf1::attr_value attr_value1;
+    typedef typename dwarf2::attr_value attr_value2;
+    inline bool match (const attr_value1 &a, const attr_value2 &b)
+    {
+      const dwarf::value_space what = a.what_space ();
+      if (what == b.what_space ())
+	switch (what)
+	  {
+	  case dwarf::VS_reference:
+	  case dwarf::VS_unit_reference:
+	    return reference_match (a.reference (), b.reference ());
+
+	  case dwarf::VS_flag:
+	    return a.flag () == b.flag ();
+
+	  case dwarf::VS_rangelistptr:
+	    return a.ranges () == b.ranges ();
+
+	  case dwarf::VS_lineptr:
+	    return a.line_info () == b.line_info ();
+
+	  case dwarf::VS_macptr:	// XXX punt for now, treat as constant
+	    return a.constant () == b.constant ();
+
+	  case dwarf::VS_dwarf_constant:
+	    return a.dwarf_constant () == b.dwarf_constant ();
+
+	  case dwarf::VS_constant:
+	    if (a.constant_is_integer ())
+	      return (b.constant_is_integer ()
+		      && a.constant () == b.constant ());
+	    return (!b.constant_is_integer ()
+		    && subr::container_equal (a.constant_block (),
+					      b.constant_block ()));
+
+	  case dwarf::VS_source_line:
+	    return a.source_line () == b.source_line ();
+	  case dwarf::VS_source_column:
+	    return a.source_column () == b.source_column ();
+
+	  case dwarf::VS_identifier:
+	    return subr::name_equal<typeof (b.identifier ())> ()
+	      (a.identifier (), b.identifier ());
+
+	  case dwarf::VS_string:
+	    return subr::name_equal<typeof (b.string ())> ()
+	      (a.string (), b.string ());
+
+	  case dwarf::VS_address:
+	    return a.address () == b.address ();
+
+	  case dwarf::VS_source_file:
+	    return a.source_file () == b.source_file ();
+
+	  case dwarf::VS_location:
+	    return a.location () == b.location ();
+
+	  case dwarf::VS_discr_list:
+	    throw std::runtime_error ("XXX unimplemented");
+	  }
+      return false;
+    }
+
+    /* We call references equal if they are literally the same DIE,
+       or if they are identical subtrees sitting in matching contexts.
+       The tracker's context_match method decides what that means.  */
+    inline bool reference_match (const cit1 &ref1, const cit2 &ref2)
+    {
+      if (ignore_refs)
+	return true;
+
+      const die1 &a = *ref1;
+      const die2 &b = *ref2;
+
+      if (a.identity () == a.identity ()) // Object identity.
+	return true;
+
+      // Simplest mismatches with the cheapest checks first.
+      if (a.tag () != b.tag ()
+	  || a.has_children () != b.has_children ())
+	return false;
+
+      // Now we have to get the tracker involved.
+      const typename tracker::left_context_type &lhs
+	= _m_tracker.left_context (ref1);
+      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 ()));
+    }
+
+  public:
+    inline bool operator () (const dwarf1 &a, const dwarf2 &b)
+    {
+      return match (a, b);
+    }
+
+    template<typename item1, typename item2>
+    inline bool equals (const item1 &a, const item2 &b)
+    {
+      return match (a, b);
+    }
+  };
+};
+
+#endif	// <elfutils/dwarf_comparator>
diff --git a/libdw/c++/dwarf_edit b/libdw/c++/dwarf_edit
index 85c3a4ff..c99d6763 100644
--- a/libdw/c++/dwarf_edit
+++ b/libdw/c++/dwarf_edit
@@ -77,6 +77,12 @@
 // DWARF manipulation interfaces (pure object construction)
 namespace elfutils
 {
+  template<typename elt>
+  inline bool operator== (const std::vector<elt> &a, const const_vector<elt> &b)
+  {
+    return a.size () == b.size () && subr::container_equal (a, b);
+  }
+
   class dwarf_edit
   {
   public:
@@ -118,6 +124,8 @@ namespace elfutils
 	typedef base_type::value_type value_type;
 	typedef base_type::mapped_type mapped_type;
 
+	static const bool ordered = true;
+
 	template<typename attrs>
 	inline operator attrs () const
 	{
@@ -177,7 +185,8 @@ namespace elfutils
       template<typename die>
       bool operator== (const die &other) const
       {
-	return (other.attributes () == attributes ()
+	return (other.tag () == tag ()
+		&& other.attributes () == attributes ()
 		&& other.children () == children ());
       }
       template<typename die>
@@ -185,6 +194,16 @@ namespace elfutils
       {
 	return !(*this == other);;
       }
+
+      inline ::Dwarf_Off identity () const
+      {
+	return (uintptr_t) this;
+      }
+
+      inline ::Dwarf_Off offset () const
+      {
+	return identity ();
+      }
     };
 
     typedef debug_info_entry::attributes::value_type attribute;
@@ -298,6 +317,8 @@ namespace elfutils
 	return *this;
       }
 
+      std::string to_string () const;
+
       inline std::string &name ()
       {
 	return _m_name;
@@ -598,6 +619,15 @@ namespace elfutils
       typedef std::map<dwarf::location_attr::key_type,
 		       std::vector<uint8_t> > _base;
 
+      template<typename pair>
+      struct nonempty : public std::unary_function<pair, bool>
+      {
+	inline bool operator () (const pair &x)
+	{
+	  return !x.second.empty ();
+	}
+      };
+
     public:
       typedef _base::size_type size_type;
       typedef _base::difference_type difference_type;
@@ -671,6 +701,87 @@ namespace elfutils
 	  }
 	throw std::runtime_error ("location is list, not single location");
       }
+
+      template<typename other_attr>
+      bool operator== (const other_attr &other) const
+      {
+	if (empty ())
+	  return (other.empty ()
+		  || std::find_if (other.begin (), other.end (),
+				   nonempty<typename other_attr::value_type> ()
+				   ) == other.end ());
+	if (!is_list ())
+	  return (!other.is_list () && !other.empty ()
+		  && subr::container_equal (location (), other.location ()));
+
+	return other.is_list () && subr::container_equal (*this, other);
+      }
+      template<typename other_attr>
+      inline bool operator!= (const other_attr &other) const
+      {
+	return !(*this == other);
+      }
+
+      std::string to_string () const;
+    };
+
+    class dwarf_enum
+    {
+    private:
+      ::Dwarf_Word _m_value;
+      unsigned int _m_which;
+
+    public:
+      inline dwarf_enum (unsigned int attr, unsigned int value)
+	: _m_value (value), _m_which (attr)
+      {}
+
+      template<typename constant>
+      inline dwarf_enum (const constant &other)
+	: _m_value (static_cast<unsigned int> (other)),
+	  _m_which (other.which ())
+      {}
+
+      // Return the DW_AT_* indicating which enum this value belongs to.
+      inline unsigned int which () const
+      {
+	return _m_which;
+      }
+
+      inline operator unsigned int () const
+      {
+	return _m_value;
+      }
+
+      inline dwarf_enum &operator= (const dwarf_enum& other)
+      {
+	_m_value = other._m_value;
+	_m_which = other._m_which;
+	return *this;
+      }
+
+      template<typename constant>
+      inline dwarf_enum &operator= (const constant& other)
+      {
+	return *this = dwarf_enum (other.which (), other);
+      }
+
+      std::string to_string () const;
+
+      const char *identifier () const;
+      const char *name () const;
+
+      template<typename constant>
+      inline bool operator== (const constant &other) const
+      {
+	return (static_cast<unsigned int> (*this)
+		== static_cast<unsigned int> (other));
+      }
+      template<typename constant>
+      inline bool operator!= (const constant &other) const
+      {
+	return !(*this == other);
+      }
     };
 
   private:
@@ -761,9 +872,10 @@ namespace elfutils
 	: std::vector<uint8_t> (b.begin (), b.end ()) {}
     };
 
-    struct value_dwarf_constant : public value_constant
+    struct value_dwarf_constant : public value_dispatch, public dwarf_enum
     {
-      value_dwarf_constant (unsigned int x) : value_constant (x) {}
+      template<typename constant>
+      value_dwarf_constant (const constant &other) : dwarf_enum (other) {}
     };
 
     struct value_source_file : public value_dispatch, public source_file
@@ -905,7 +1017,7 @@ namespace elfutils
       }
 
       dwarf::value_space what_space () const;
-      std::string to_string () const;
+      inline std::string to_string () const;
 
       inline bool &flag () const
       {
@@ -973,9 +1085,9 @@ namespace elfutils
 	  (variant<value_constant_block> ());
       }
 
-      inline ::Dwarf_Word &dwarf_constant () const
+      inline dwarf_enum &dwarf_constant () const
       {
-	return variant<value_dwarf_constant> ().word;
+	return variant<value_dwarf_constant> ();
       }
 
       inline bool constant_is_integer () const
@@ -1033,7 +1145,7 @@ namespace elfutils
 	    case dwarf::VS_location:
 	      return location () == other.location ();
 	    case dwarf::VS_dwarf_constant:
-	      return constant () == other.constant (); // XXX
+	      return dwarf_constant () == other.dwarf_constant ();
 #if 0
 	    case dwarf::VS_macptr:
 	      return macptr () == other.macptr ();
@@ -1083,6 +1195,22 @@ namespace elfutils
       return !(*this == other);
     }
   };
+
+  // Explicit specializations.
+  template<>
+  std::string to_string<dwarf_edit::attribute> (const dwarf_edit::attribute &);
+  template<>
+  std::string to_string<dwarf_edit::attr_value> (const dwarf_edit::attr_value&);
+  inline std::string dwarf_edit::attr_value::to_string () const
+  {
+    return elfutils::to_string (*this); // Use that.
+  }
+  template<>
+  std::string to_string<dwarf_edit::dwarf_enum> (const dwarf_edit::dwarf_enum&);
+  inline std::string dwarf_edit::dwarf_enum::to_string () const
+  {
+    return elfutils::to_string (*this); // Use that.
+  }
 };
 
 #endif	// <elfutils/dwarf_edit>
diff --git a/libdw/c++/dwarf_tracker b/libdw/c++/dwarf_tracker
new file mode 100644
index 00000000..1c2d563e
--- /dev/null
+++ b/libdw/c++/dwarf_tracker
@@ -0,0 +1,229 @@
+/* elfutils::dwarf_ref_tracker -- DWARF reference tracking in -*- C++ -*-
+   Copyright (C) 2009 Red Hat, Inc.
+   This file is part of Red Hat elfutils.
+
+   Red Hat elfutils is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by the
+   Free Software Foundation; version 2 of the License.
+
+   Red Hat elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License along
+   with Red Hat elfutils; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
+
+   In addition, as a special exception, Red Hat, Inc. gives You the
+   additional right to link the code of Red Hat elfutils with code licensed
+   under any Open Source Initiative certified open source license
+   (http://www.opensource.org/licenses/index.php) which requires the
+   distribution of source code with any binary distribution and to
+   distribute linked combinations of the two.  Non-GPL Code permitted under
+   this exception must only link to the code of Red Hat elfutils through
+   those well defined interfaces identified in the file named EXCEPTION
+   found in the source code files (the "Approved Interfaces").  The files
+   of Non-GPL Code may instantiate templates or use macros or inline
+   functions from the Approved Interfaces without causing the resulting
+   work to be covered by the GNU General Public License.  Only Red Hat,
+   Inc. may make changes or additions to the list of Approved Interfaces.
+   Red Hat's grant of this exception is conditioned upon your not adding
+   any new exceptions.  If you wish to add a new Approved Interface or
+   exception, please contact Red Hat.  You must obey the GNU General Public
+   License in all respects for all of the Red Hat elfutils code and other
+   code used in conjunction with Red Hat elfutils except the Non-GPL Code
+   covered by this exception.  If you modify this file, you may extend this
+   exception to your version of the file, but you are not obligated to do
+   so.  If you do not wish to provide this exception without modification,
+   you must delete this exception statement from your version and license
+   this file solely under the GPL without exception.
+
+   Red Hat elfutils is an included package of the Open Invention Network.
+   An included package of the Open Invention Network is a package for which
+   Open Invention Network licensees cross-license their patents.  No patent
+   license is granted, either expressly or impliedly, by designation as an
+   included package.  Should you wish to participate in the Open Invention
+   Network licensing program, please visit www.openinventionnetwork.com
+   <http://www.openinventionnetwork.com>.  */
+
+#ifndef _ELFUTILS_DWARF_TRACKER
+#define _ELFUTILS_DWARF_TRACKER	1
+
+#include "dwarf"
+#include "dwarf_comparator"
+
+namespace elfutils
+{
+  // Standard tracker.
+  template<class dwarf1, class dwarf2>
+  class dwarf_ref_tracker : public dwarf_tracker_base<dwarf1, dwarf2>
+  {
+  private:
+    typedef typename dwarf1::compile_units::const_iterator cu1;
+    typedef typename dwarf2::compile_units::const_iterator cu2;
+    typedef typename dwarf1::debug_info_entry::children::const_iterator die1;
+    typedef typename dwarf2::debug_info_entry::children::const_iterator die2;
+
+    /* 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.  */
+    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;
+
+      ~tracker ()
+      {
+	// 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)
+      {
+	typename die_map::iterator it = _m_seen.find (a->identity ());
+	if (it == _m_seen.end ())
+	  {
+	    ::Dwarf_Off id = a->identity ();
+	    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;
+	  }
+	return it->second;
+      }
+
+      // Return true if this is the droid we're looking for,
+      // or recurse on its children.
+      bool walk_to (const typename die::value_type from, ::Dwarf_Off to,
+		    die_path &path)
+      {
+	if (from.identity () == to)
+	  return true;
+	for (die it = from.children ().begin ();
+	     it != from.children ().end ();
+	     ++it)
+	  if (walk_to (it, to, path))
+	    return true;
+	return false;
+      }
+
+      // Recursing on a child, include FROM in the path if the child matches.
+      bool walk_to (const die from, ::Dwarf_Off to, die_path &path)
+      {
+	if (walk_to (*from, to, path))
+	  {
+	    path.push_front (from);
+	    return true;
+	  }
+	return false;
+      }
+
+      inline void start_walk (const cu &a)
+      {
+	assert (_m_path.empty ());
+	_m_root = a;
+      }
+
+      inline void finish_walk (const cu &a)
+      {
+	assert (_m_path.empty ());
+	_m_root = cu ();
+      }
+
+      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));
+	// Append this DIE to the path we'll record for its children.
+	_m_path.push_back (a);
+      }
+
+      inline void post_order (const die &a)
+      {
+	_m_path.pop_back ();
+      }
+    };
+
+    typedef tracker<cu1, die1> tracker1;
+    typedef tracker<cu2, die2> tracker2;
+
+    tracker1 _m_left;
+    tracker2 _m_right;
+
+    /* 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
+       are not compared.  */
+    struct equal_enough : public std::binary_function<die1, die2, bool>
+    {
+      inline bool operator () (const die1 &a, const die2 &b)
+      {
+	return (a->tag () == b->tag ()
+		&& (dwarf_comparator<dwarf1, dwarf2, true> ()
+		    .equals (a->attributes (), b->attributes ())));
+      }
+    };
+
+  public:
+    inline void start_walk (const cu1 &a, const cu2 &b)
+    {
+      _m_left.start_walk (a);
+      _m_right.start_walk (b);
+    }
+
+    inline void finish_walk (const cu1 &a, const cu2 &b)
+    {
+      _m_left.finish_walk (a);
+      _m_right.finish_walk (b);
+    }
+
+    inline void pre_order (const die1 &a, const die2 &b)
+    {
+      _m_left.pre_order (a);
+      _m_right.pre_order (b);
+    }
+
+    inline void post_order (const die1 &a, const die2 &b)
+    {
+      _m_left.post_order (a);
+      _m_right.post_order (b);
+    }
+
+    typedef std::list<die1> left_context_type;
+    inline const left_context_type &left_context (const die1 &die)
+    {
+      return _m_left.path_to (die);
+    }
+
+    typedef std::list<die2> right_context_type;
+    inline const right_context_type &right_context (const die2 &die)
+    {
+      return _m_right.path_to (die);
+    }
+
+    // Very cheap check for an obvious mismatch of contexts.
+    inline bool context_quick_mismatch (const left_context_type &a,
+					const right_context_type &b)
+
+    {
+      return a.size () != a.size ();
+    }
+
+    // Full match when context_quick_mismatch has returned false.
+    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 ());
+    }
+  };
+};
+
+#endif	// <elfutils/dwarf_tracker>
diff --git a/libdw/c++/edit-values.cc b/libdw/c++/edit-values.cc
index f502c66c..eb957492 100644
--- a/libdw/c++/edit-values.cc
+++ b/libdw/c++/edit-values.cc
@@ -92,3 +92,30 @@ dwarf_edit::attr_value::what_space () const
 
   throw std::runtime_error ("XXX impossible");
 }
+
+template<>
+std::string
+to_string<dwarf_edit::attribute> (const dwarf_edit::attribute &attr)
+{
+  std::string result = dwarf::attributes::name (attr.first);
+  result += "=";
+  result += attr.second.to_string ();
+  return result;
+}
+
+std::string
+dwarf_edit::source_file::to_string () const
+{
+  if (likely (_m_mtime == 0) && likely (_m_size == 0))
+    return "\"" + _m_name + "\"";
+
+  std::ostringstream os;
+  os << "{\"" << _m_name << "," << _m_mtime << "," << _m_size << "}";
+  return os.str ();
+}
+
+std::string
+dwarf_edit::location_attr::to_string () const
+{
+  return is_list () ? "XXX-loclist" : "XXX-expr";
+}
diff --git a/libdw/c++/known.cc b/libdw/c++/known.cc
index 81e4417e..1bb84f13 100644
--- a/libdw/c++/known.cc
+++ b/libdw/c++/known.cc
@@ -49,6 +49,7 @@
 
 #include <config.h>
 #include "dwarf"
+#include "dwarf_edit"
 #include "known-dwarf.h"
 
 using namespace elfutils;
@@ -155,14 +156,14 @@ namespace elfutils
 #undef KNOWN_ENUM_CASE
 };
 
-const char *
-dwarf::dwarf_enum::identifier () const
+static const char *
+known_identifier (unsigned int which, unsigned int value)
 {
-  switch (_m_attr.whatattr ())
+  switch (which)
     {
 # define KNOWN_ENUM(attr, enum)						\
       case DW_AT_##attr:						\
-	return dwarf::known_enum<DW_AT_##attr>::identifier (*this);
+	return dwarf::known_enum<DW_AT_##attr>::identifier (value);
 
       ALL_KNOWN_ENUM
 
@@ -172,14 +173,14 @@ dwarf::dwarf_enum::identifier () const
   return NULL;
 }
 
-const char *
-dwarf::dwarf_enum::name () const
+static const char *
+known_name (unsigned int which, unsigned int value)
 {
-  switch (_m_attr.whatattr ())
+  switch (which)
     {
 # define KNOWN_ENUM(attr, enum)						\
       case DW_AT_##attr:						\
-	return dwarf::known_enum<DW_AT_##attr>::name (*this);
+	return dwarf::known_enum<DW_AT_##attr>::name (value);
 
       ALL_KNOWN_ENUM
 
@@ -189,9 +190,62 @@ dwarf::dwarf_enum::name () const
   return NULL;
 }
 
-std::string
-dwarf::dwarf_enum::to_string () const
+template<typename constant>
+static inline const char *
+enum_identifier (const constant &value)
+{
+  return known_identifier (value.which (), value);
+}
+
+template<typename constant>
+static inline const char *
+enum_name (const constant &value)
+{
+  return known_name (value.which (), value);
+}
+
+const char *
+dwarf::dwarf_enum::identifier () const
+{
+  return enum_identifier (*this);
+}
+
+const char *
+dwarf::dwarf_enum::name () const
+{
+  return enum_name (*this);
+}
+
+const char *
+dwarf_edit::dwarf_enum::identifier () const
+{
+  return enum_identifier (*this);
+}
+
+const char *
+dwarf_edit::dwarf_enum::name () const
+{
+  return enum_name (*this);
+}
+
+template<class value_type>
+static inline std::string
+enum_string (const value_type &value)
+{
+  const char *known = value.name ();
+  return known == NULL ? subr::hex_string (value) : std::string (known);
+}
+
+template<>
+string
+to_string<dwarf::dwarf_enum> (const dwarf::dwarf_enum &value)
+{
+  return enum_string (value);
+}
+
+template<>
+string
+to_string<dwarf_edit::dwarf_enum> (const dwarf_edit::dwarf_enum &value)
 {
-  const char *known = name ();
-  return known == NULL ? subr::hex_string (*this) : std::string (known);
+  return enum_string (value);
 }
diff --git a/libdw/c++/subr.hh b/libdw/c++/subr.hh
index d8862e53..e1184627 100644
--- a/libdw/c++/subr.hh
+++ b/libdw/c++/subr.hh
@@ -18,7 +18,8 @@ namespace elfutils
     template<typename string>
     struct name_equal : public std::binary_function<const char *, string, bool>
     {
-      inline bool operator () (const char *me, const string &you)
+      template<typename mystring>
+      inline bool operator () (const mystring &me, const string &you)
       {
 	return you == me;
       }
@@ -33,6 +34,11 @@ namespace elfutils
       {
 	return !strcmp (me, you);
       }
+      template<typename mystring>
+      inline bool operator () (const mystring &me, const char *you)
+      {
+	return me == you;
+      }
     };
 
     static inline std::string hex_string (int code)
@@ -71,27 +77,76 @@ namespace elfutils
       }
     };
 
+    template<typename t1, typename t2, typename pred_type>
+    class deref
+      : public std::binary_function<typename t1::const_iterator,
+				    typename t2::const_iterator,
+				    bool>
+    {
+    private:
+      pred_type _m_pred;
+
+    public:
+      inline deref ()
+	: _m_pred ()
+      {}
+
+      inline deref (const pred_type &pred)
+	: _m_pred (pred)
+      {}
+
+      inline bool operator () (const typename t1::const_iterator &a,
+			       const typename t2::const_iterator &b)
+      {
+	return _m_pred (*a, *b);
+      }
+    };
+
+    template<typename t1, typename t2>
+    struct deref_equal_to
+      : public deref<t1, t2,
+		     equal_to<typename t1::value_type, typename t2::value_type>
+		     >
+    {};
+
     template<typename iter1, typename iter2, typename pred_type>
-    inline bool container_equal (iter1 first1, iter1 last1,
-				 iter2 first2, iter2 last2,
+    inline bool container_equal (iter1 &first1, const iter1 &last1,
+				 iter2 &first2, const iter2 &last2,
 				 pred_type pred)
     {
       while (first1 != last1)
-	if (first2 == last2 || !pred (*first1++, *first2++))
-	  return false;
+	{
+	  if (first2 == last2 || !pred (first1, first2))
+	    return false;
+	  ++first1;
+	  ++first2;
+	}
       return first2 == last2;
     }
 
-    template<typename t1, typename t2>
-    inline bool container_equal (const t1 &a, const t2 &b)
+    template<typename t1, typename t2, typename pred_type>
+    inline bool container_equal (const t1 &a, const t2 &b, pred_type pred)
     {
       typename t1::const_iterator first1 = a.begin ();
       typename t1::const_iterator last1 = a.end ();
       typename t2::const_iterator first2 = b.begin ();
       typename t2::const_iterator last2 = b.end ();
-      return container_equal (first1, last1, first2, last2,
-			      equal_to<typename t1::value_type,
-			               typename t2::value_type> ());
+      return container_equal (first1, last1, first2, last2, pred);
+    }
+
+    template<typename t1, typename t2>
+    inline bool container_equal (const t1 &a, const t2 &b)
+    {
+      return container_equal (a, b, deref_equal_to<t1, t2> ());
+    }
+
+    template<typename iter>
+    inline typename iter::difference_type length (iter i, const iter &end)
+    {
+      typename iter::difference_type n = 0;
+      while (i != end)
+	++i, ++n;
+      return n;
     }
 
     template<typename array, typename element = typename array::value_type>
diff --git a/libdw/c++/values.cc b/libdw/c++/values.cc
index 8b278c49..5e0eda23 100644
--- a/libdw/c++/values.cc
+++ b/libdw/c++/values.cc
@@ -50,6 +50,7 @@
 #include <config.h>
 #include <cassert>
 #include "dwarf"
+#include "dwarf_edit"
 
 extern "C"
 {
@@ -175,55 +176,77 @@ plain_string (const char *filename)
   return string ("\"") + filename + "\"";
 }
 
-string
-dwarf::attr_value::to_string () const
+static inline string
+plain_string (const string &filename)
+{
+  return "\"" + filename + "\"";
+}
+
+template<class value_type>
+static inline string
+value_string (const value_type &value)
 {
-  switch (what_space ())
+  switch (value.what_space ())
     {
-    case VS_flag:
-      return flag () ? "1" : "0";
+    case dwarf::VS_flag:
+      return value.flag () ? "1" : "0";
 
-    case VS_rangelistptr:
-      return ranges ().to_string ();
+    case dwarf::VS_rangelistptr:
+      return value.ranges ().to_string ();
 
-    case VS_lineptr:	// XXX punt for now, treat as constant
-    case VS_macptr:	// XXX punt for now, treat as constant
-    case VS_constant:
-      return hex_string (constant ());
+    case dwarf::VS_lineptr:	// XXX punt for now, treat as constant
+    case dwarf::VS_macptr:	// XXX punt for now, treat as constant
+    case dwarf::VS_constant:
+      return hex_string (value.constant ());
 
-    case VS_dwarf_constant:
-      return dwarf_constant ().to_string ();
+    case dwarf::VS_dwarf_constant:
+      return value.dwarf_constant ().to_string ();
 
-    case VS_source_line:
-    case VS_source_column:
-      return dec_string (constant ());
+    case dwarf::VS_source_line:
+    case dwarf::VS_source_column:
+      return dec_string (value.constant ());
 
-    case VS_identifier:
-      return plain_string (identifier ());
+    case dwarf::VS_identifier:
+      return plain_string (value.identifier ());
 
-    case VS_string:
-      return plain_string (string ());
+    case dwarf::VS_string:
+      return plain_string (value.string ());
 
-    case VS_address:
-      return addr_string (address ());
+    case dwarf::VS_address:
+      return addr_string (value.address ());
 
-    case VS_reference:
-    case VS_unit_reference:
-      return hex_string (reference ()->offset (), "[", "]");
+    case dwarf::VS_reference:
+    case dwarf::VS_unit_reference:
+      return hex_string (value.reference ()->offset (), "[", "]");
 
-    case VS_source_file:
-      return source_file ().to_string ();
+    case dwarf::VS_source_file:
+      return value.source_file ().to_string ();
 
-    case VS_location:
-      return location ().to_string ();
+    case dwarf::VS_location:
+      return value.location ().to_string ();
 
-    case VS_discr_list:
+    case dwarf::VS_discr_list:
       break;			// XXX DW_AT_discr_list unimplemented
     }
 
   throw std::runtime_error ("XXX unsupported value space");
 }
 
+template<>
+string
+to_string<dwarf::attr_value> (const dwarf::attr_value &value)
+{
+  return value_string (value);
+}
+
+template<>
+string
+to_string<dwarf_edit::attr_value> (const dwarf_edit::attr_value &value)
+{
+  return value_string (value);
+}
+
+
 // A few cases are trivial.
 #define SIMPLE(type, name, form)					\
   type									\
diff --git a/src/ChangeLog b/src/ChangeLog
index 8de13031..a0402416 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,13 @@
 2009-06-19  Roland McGrath  <roland@redhat.com>
 
+	* dwarfcmp.cc: Revamp using dwarf_comparator.
+
+	* dwarflint-expected-at.cc: Include <config.h> first.
+	* dwarflint-expected.hh (expected_map::expectation_map):
+	Use dwarf::tags.
+	(to_string): Function removed.
+	* dwarflint-hl.cc (recursively_validate): Don't use it.
+
 	* dwarflint.c (abbrev_table_load): No-op control flow fiddle
 	silences gcc-4.4 -O3 warning.
 
diff --git a/src/dwarfcmp.cc b/src/dwarfcmp.cc
index 522b719e..d4c32108 100644
--- a/src/dwarfcmp.cc
+++ b/src/dwarfcmp.cc
@@ -45,6 +45,8 @@
 
 #include "c++/dwarf"
 #include "c++/dwarf_edit"
+#include "c++/dwarf_comparator"
+#include "c++/dwarf_tracker"
 
 using namespace elfutils;
 using namespace std;
@@ -121,140 +123,140 @@ open_file (const char *fname, int *fdp)
 
 
 // XXX make translation-friendly
-struct context
-{
-  const dwarf::debug_info_entry *a_;
-  const dwarf::debug_info_entry *b_;
-  const char *container_;
 
-  context (const dwarf::debug_info_entry &a, const dwarf::debug_info_entry &b)
-    : a_ (&a), b_ (&b), container_ (NULL) {}
-  context () : a_ (NULL), b_ (NULL), container_ ("compilation units") {}
+template<class dwarf1, class dwarf2>
+struct talker : public dwarf_ref_tracker<dwarf1, dwarf2>
+{
+  typedef typename dwarf1::compile_units::const_iterator cu1;
+  typedef typename dwarf2::compile_units::const_iterator cu2;
+  typedef typename dwarf1::debug_info_entry::children::const_iterator die1;
+  typedef typename dwarf2::debug_info_entry::children::const_iterator die2;
+  typedef typename dwarf1::debug_info_entry::attributes::const_iterator attr1;
+  typedef typename dwarf2::debug_info_entry::attributes::const_iterator attr2;
 
-  ostream &location () const
-  {
-    if (a_ == NULL)
-      cout << "files differ: ";
-    else
-      cout << hex << a_->offset () << " vs " << b_->offset () << ": ";
-    return cout;
-  }
+  const typename dwarf1::debug_info_entry *a_;
+  const typename dwarf2::debug_info_entry *b_;
 
-  void container (const char *msg) const
-  {
-    location () << msg << " " << container_ << endl;
-  }
+  inline talker () : a_ (NULL), b_ (NULL) {}
 
-  void missing () const
+  inline ostream &location () const
   {
-    container ("missing");
+    return cout << hex << a_->offset () << " vs " << b_->offset () << ": ";
   }
 
-  void extra () const
+  inline void visit (const typename dwarf1::debug_info_entry &a,
+		     const typename dwarf2::debug_info_entry &b)
   {
-    container ("extra");
+    a_ = &a;
+    b_ = &b;
+    if (a.tag () != b.tag ())
+      location () << dwarf::tags::name (a.tag ())
+		  << " vs "
+		  << dwarf::tags::name (b.tag ());
   }
 
-  void tag () const
+  inline void mismatch (const cu1 &it1, const cu1 &end1,
+			const cu2 &it2, const cu2 &end2)
   {
-    location () << "different tag" << endl;
+    if (it1 == end1)		// a lacks some of b's CUs.
+      cout << "files differ: "
+	   << dec << subr::length (it2, end2)
+	   << " extra compilation units "
+	   << endl;
+    else if (it2 == end2)	// b lacks some of a's CUs.
+      cout << "files differ: "
+	   << dec << subr::length (it1, end1)
+	   << " compilation units missing "
+	   << endl;
+    // Otherwise the differing CU will have announced itself.
   }
 
-  void attributes () const
+  inline void mismatch (const die1 &it1, const die1 &end1,
+			const die2 &it2, const die2 &end2)
   {
-    location () << "different attributes" << endl;
+    if (it1 == end1)		// a_ lacks some of b_'s children.
+      location () << dec << subr::length (it2, end2)
+		  << " extra children " << endl;
+    else if (it2 == end2)	// b_ lacks some of a_'s children.
+      location () << dec << subr::length (it1, end1)
+		  << " children missing " << endl;
+    // Otherwise the differing child will have announced itself.
   }
 
-  void values (const string &a, const string &b) const
+  inline void mismatch (attr1 it1, const attr1 &end1,
+			attr2 it2, const attr2 &end2)
   {
-    location () << "attribute " << a << " vs " << b << endl;
+    if (it1 == end1)		// a_ lacks some of b_'s attrs.
+      for (location () << " extra attributes:"; it2 != end2; ++it2)
+	cout << " " << to_string (*it2);
+    else if (it2 == end2)	// b_ lacks some of a_'s attrs.
+      for (location () << " missing attributes:"; it1 != end1; ++it1)
+	cout << " " << to_string (*it1);
+    else
+      location () << to_string (*it1) << " vs " << to_string (*it2);
+    cout << endl;
   }
 };
 
-template<typename container1, typename container2>
-static int
-describe_mismatch (const container1 &a, const container2 &b, const context &say)
+// For a silent comparison we just use the standard ref tracker.
+template<class dwarf1, class dwarf2>
+struct quiet_cmp : public dwarf_comparator<dwarf1, dwarf2, false,
+					   dwarf_ref_tracker<dwarf1, dwarf2> >
+{};
+
+// To be noisy, the talker wraps the standard tracker with verbosity hooks.
+template<class dwarf1, class dwarf2>
+struct noisy_cmp : public dwarf_comparator<dwarf1, dwarf2, false,
+					   talker<dwarf1, dwarf2> >
+{};
+
+
+// Test that one comparison works as expected.
+template<class dwarf1, class dwarf2>
+static void
+test_compare (const dwarf1 &file1, const dwarf2 &file2, bool expect)
 {
-  typename container1::const_iterator i = a.begin ();
-  typename container2::const_iterator j = b.begin ();
-  int result = 0;
-  while (i != a.end ())
-    {
-      if (j == b.end ())
-	{
-	  say.missing ();	// b lacks some of a.
-	  result = 1;
-	  break;
-	}
-      result = describe_mismatch (*i, *j, say);
-      assert ((result != 0) == (*i != *j));
-      if (result != 0)
-	break;
-      ++i;
-      ++j;
-    }
-  if (result == 0 && j != b.end ())
+  if (quiet_cmp<dwarf1, dwarf2> () (file1, file2) != expect)
     {
-      say.extra ();		// a lacks some of b.
-      result = 1;
+      if (expect)
+	noisy_cmp<dwarf1, dwarf2> () (file1, file2);
+      throw std::logic_error (__PRETTY_FUNCTION__);
     }
-  return result;
 }
 
-template<>
-int
-describe_mismatch (const dwarf::debug_info_entry &a,
-		   const dwarf::debug_info_entry &b,
-		   const context &ctx)
+// Test all directions of two classes.
+template<class dwarf1, class dwarf2>
+static void
+test_classes (const dwarf1 &file1, const dwarf1 &file2,
+	      const dwarf2 &out1, const dwarf2 &out2,
+	      bool expect)
 {
-  context here (a, b);
+  // Compare self, same type.
+  test_compare (out1, out1, true);
+  test_compare (out2, out2, true);
 
-  int result = a.tag () != b.tag ();
-  if (result != 0)
-    here.tag ();
+  // Compare self, output == input.
+  test_compare (out1, file1, true);
+  test_compare (out2, file2, true);
 
-  if (result == 0)
-    {
-      here.container_ = "attributes";
-      result = describe_mismatch (a.attributes (), b.attributes (), here);
-      assert ((result != 0) == (a.attributes () != b.attributes ()));
-    }
-  if (result == 0)
-    {
-      here.container_ = "children";
-      result = describe_mismatch (a.children (), b.children (), here);
-      assert ((result != 0) == (a.children () != b.children ()));
-    }
-  return result;
-}
+  // Compare self, input == output.
+  test_compare (file1, out1, true);
+  test_compare (file2, out2, true);
 
-template<>
-int
-describe_mismatch (const dwarf::compile_unit &a, const dwarf::compile_unit &b,
-		   const context &ctx)
-{
-  return describe_mismatch (static_cast<const dwarf::debug_info_entry &> (a),
-			    static_cast<const dwarf::debug_info_entry &> (b),
-			    ctx);
-}
+  // Compare files, output == output.
+  test_compare (out1, out2, expect);
+  test_compare (out2, out1, expect);
 
-template<>
-int
-describe_mismatch (const dwarf::attribute &a, const dwarf::attribute &b,
-		   const context &say)
-{
-  int result = a.first != b.first;
-  if (result != 0)
-    say.attributes ();
-  else
-    {
-      result = a.second != b.second;
-      if (result != 0)
-	say.values (a.to_string (), b.to_string ());
-    }
-  return result;
+  // Compare files, output vs input.
+  test_compare (out1, file2, expect);
+  test_compare (out2, file1, expect);
+
+  // Compare files, input vs output.
+  test_compare (file2, out1, expect);
+  test_compare (file1, out2, expect);
 }
 
+
 int
 main (int argc, char *argv[])
 {
@@ -304,52 +306,18 @@ main (int argc, char *argv[])
       dwarf file1 (dw1);
       dwarf file2 (dw2);
 
-      if (quiet)
-	result = !(file1 == file2);
-      else
-	result = describe_mismatch (file1.compile_units (),
-				    file2.compile_units (),
-				    context ());
+      bool same = (quiet
+		   ? quiet_cmp<dwarf, dwarf> () (file1, file2)
+		   : noisy_cmp<dwarf, dwarf> () (file1, file2));
 
       if (test_writer)
 	{
 	  dwarf_edit out1 (file1);
 	  dwarf_edit out2 (file2);
-
-# define compare_self(x, y)			\
-	  assert (x == y);			\
-	  assert (!(x != y))
-# define compare_other(x, y)			\
-	  assert (!(x == y) == result);		\
-	  assert (!(x != y) == !result)
-
-	  // Compare self, same type.
-	  compare_self (out1, out1);
-	  compare_self (out2, out2);
-
-	  // Compare self, output == input.
-	  compare_self (out1, file1);
-	  compare_self (out2, file2);
-
-	  // Compare self, input == output.
-	  compare_self (file1, out1);
-	  compare_self (file2, out2);
-
-	  // Compare files, output == output.
-	  compare_other (out1, out2);
-	  compare_other (out2, out1);
-
-	  // Compare files, output vs input.
-	  compare_other (out1, file2);
-	  compare_other (out2, file1);
-
-	  // Compare files, input vs output.
-	  compare_other (file2, out1);
-	  compare_other (file1, out2);
-
-#undef	compare_self
-#undef	compare_other
+	  test_classes (file1, file2, out1, out2, same);
 	}
+
+      result = !same;
     }
 
   return result;
diff --git a/src/dwarflint-expected-at.cc b/src/dwarflint-expected-at.cc
index ed47121b..d63c14db 100644
--- a/src/dwarflint-expected-at.cc
+++ b/src/dwarflint-expected-at.cc
@@ -1,3 +1,30 @@
+/* Pedantic checking of DWARF files.
+   Copyright (C) 2009 Red Hat, Inc.
+   This file is part of Red Hat elfutils.
+   Written by Petr Machata <pmachata@redhat.com>, 2009.
+
+   Red Hat elfutils is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by the
+   Free Software Foundation; version 2 of the License.
+
+   Red Hat elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License along
+   with Red Hat elfutils; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
+
+   Red Hat elfutils is an included package of the Open Invention Network.
+   An included package of the Open Invention Network is a package for which
+   Open Invention Network licensees cross-license their patents.  No patent
+   license is granted, either expressly or impliedly, by designation as an
+   included package.  Should you wish to participate in the Open Invention
+   Network licensing program, please visit www.openinventionnetwork.com
+   <http://www.openinventionnetwork.com>.  */
+
+#include <config.h>
 #include "dwarflint-expected.hh"
 #include "../libdw/dwarf.h"
 
diff --git a/src/dwarflint-expected.hh b/src/dwarflint-expected.hh
index 429d64c1..bcb0de5b 100644
--- a/src/dwarflint-expected.hh
+++ b/src/dwarflint-expected.hh
@@ -1,9 +1,37 @@
+/* Pedantic checking of DWARF files.
+   Copyright (C) 2009 Red Hat, Inc.
+   This file is part of Red Hat elfutils.
+   Written by Petr Machata <pmachata@redhat.com>, 2009.
+
+   Red Hat elfutils is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by the
+   Free Software Foundation; version 2 of the License.
+
+   Red Hat elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License along
+   with Red Hat elfutils; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
+
+   Red Hat elfutils is an included package of the Open Invention Network.
+   An included package of the Open Invention Network is a package for which
+   Open Invention Network licensees cross-license their patents.  No patent
+   license is granted, either expressly or impliedly, by designation as an
+   included package.  Should you wish to participate in the Open Invention
+   Network licensing program, please visit www.openinventionnetwork.com
+   <http://www.openinventionnetwork.com>.  */
+
 #include <map>
 #include <set>
 #include <stdexcept>
 #include <sstream>
 #include <cassert>
 
+#include "c++/dwarf"
+
 enum optionality
 {
   opt_optional = 0,	// may or may not be present
@@ -13,7 +41,7 @@ enum optionality
 
 template <class T>
 std::string
-to_string (T x)
+string_of (T x)
 {
   std::ostringstream o;
   o << x;
@@ -67,7 +95,8 @@ public:
   {
     expected_map_t::const_iterator it = m_map.find (tag);
     if (it == m_map.end ())
-      throw std::runtime_error ("Unknown tag #" + to_string (tag));
+      throw std::runtime_error ("Unknown tag "
+				+ elfutils::dwarf::tags::identifier (tag));
     return it->second.map ();
   }
 };
diff --git a/src/dwarflint-hl.cc b/src/dwarflint-hl.cc
index 1b8961a2..0663114f 100644
--- a/src/dwarflint-hl.cc
+++ b/src/dwarflint-hl.cc
@@ -229,10 +229,10 @@ recursively_validate (elfutils::dwarf::compile_unit const &cu,
 	  elfutils::dwarf::value_space vs = (*jt).second.what_space ();
 	  if ((exp_vs & (1U << vs)) == 0)
 	    wr_message (cat (mc_impact_3, mc_info), &where,
-			": in DIE \"%s\", attribute \"%s\" has value of unexpected type \"%s\".\n",
+			": in DIE \"%s\", attribute \"%s\" has value of unexpected type \"%u\".\n",
 			dwarf_tag_string (parent_tag),
 			dwarf_attr_string (name),
-			to_string (vs).c_str ());
+			vs);
 	}
       catch (...)
 	{