Merge branch 'dwarf' of ssh://git.fedorahosted.org/git/elfutils into dwarf

5 files changed, 222 insertions, 228 deletions

diff --git a/libdw/Makefile.am b/libdw/Makefile.am
index 279e8599..3fcfdb71 100644
--- a/libdw/Makefile.am
+++ b/libdw/Makefile.am
@@ -101,7 +101,7 @@ libdwpp_a_SOURCES = c++/values.cc \
 		    c++/known.cc \
 		    c++/line_info.cc \
 		    c++/edit-values.cc \
-		    c++/output-values.cc c++/output-shape.cc
+		    c++/output-values.cc
 
 if MAINTAINER_MODE
 BUILT_SOURCES = $(srcdir)/known-dwarf.h
diff --git a/libdw/c++/dwarf b/libdw/c++/dwarf
index 8342dc78..c386f0ed 100644
--- a/libdw/c++/dwarf
+++ b/libdw/c++/dwarf
@@ -1126,7 +1126,8 @@ namespace elfutils
       }
 
       /* Return a value unique to us while we're in memory.
-	 This is a stable pointer into the Dwarf_Files data.  */
+	 This is a stable pointer into the Dwarf_Files data
+         or to a static empty string.  */
       inline uintptr_t identity () const
       {
 	return (uintptr_t) name ();
diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output
index b7bbaadc..aeb192c4 100644
--- a/libdw/c++/dwarf_output
+++ b/libdw/c++/dwarf_output
@@ -151,6 +151,12 @@ namespace elfutils
       friend class dwarf_output;
       friend class dwarf_output_collector;
 
+      __attribute__((used)) die_info_pair *info () const
+      {
+       return reinterpret_cast<die_info_pair *>
+         (const_cast<debug_info_entry *> (this));
+      }
+
     public:
       class attributes_type
 	: public dwarf_data::attributes_type<dwarf_output, value>
@@ -403,13 +409,18 @@ namespace elfutils
 	: _base (i, dummy)
       {}
 
-      /* The hash of a value_reference is its referent's identity,
-	 because we can have multiple value_reference objects that
-	 wind up pointing to the same entry.  This method is virtual
-	 for the circular_reference case, below.  */
-      virtual size_t hash () const
+      /* The hash of a value_reference is its referent's local hash,
+	 which only takes non-reference values into account.  This
+	 method is virtual for the circular_reference case, below.  */
+      inline size_t hash () const
       {
-	return ref->identity ();
+	struct die_info *info = get_die_info ();
+	return info->_m_reference_hash;
+      }
+
+      virtual die_info *get_die_info () const
+      {
+	return &ref->info ()->second;
       }
     };
 
@@ -584,10 +595,21 @@ namespace elfutils
       std::bitset<2> _m_with_sibling;
       unsigned int _m_uses;
 
-      inline die_info ()
+      /* The local hash of the die, set when die_info is created.
+	 Uses only none-reference values.  */
+      size_t _m_local_hash;
+
+      /* The reference hash of the die, based on just reference
+	 attribute values.  Needs all local hashes of referenced dies
+	 to be set.  */
+      size_t _m_reference_hash;
+
+      inline die_info (size_t local_hash)
 	: _m_parent (NULL), _m_refs (),
 	  _m_originals (), _m_original_cost (0),
-	  _m_with_sibling (), _m_uses (0)
+	  _m_with_sibling (), _m_uses (0),
+	  _m_local_hash (local_hash),
+	  _m_reference_hash (0)
       {}
 
       inline ~die_info ()
@@ -982,11 +1004,12 @@ namespace elfutils
 
     inline die_info_pair *add_entry (int tag,
 				     const children_type *children,
-				     const attrs_type *attrs)
+				     const attrs_type *attrs,
+				     die_info *info)
     {
       std::pair <die_map::iterator, bool>
 	ins = _m_unique.insert (std::make_pair (die_type (tag, children, attrs),
-						die_info ()));
+						*info));
       die_info_pair &x = *ins.first;
       if (ins.second)
 	x.second.assert_unused ();
@@ -994,39 +1017,6 @@ namespace elfutils
       return &x;
     }
 
-    struct shape_type
-    {
-      typedef std::vector<std::pair<int, int> > attrs_type;
-      attrs_type _m_attrs;
-      bool _m_has_children;
-      size_t _m_hash;
-
-      friend class subr::hashed_hasher<shape_type>;
-      typedef subr::hashed_hasher<shape_type> hasher;
-
-      inline void hashnadd (int name, int form);
-      inline shape_type (const die_type &die, bool last_sibling);
-
-      inline bool operator== (const shape_type &other) const
-      {
-	return (_m_hash == other._m_hash
-		&& _m_has_children == other._m_has_children
-		&& _m_attrs == other._m_attrs);
-      }
-      inline bool operator!= (const shape_type &other) const
-      {
-	return !(*this == other);
-      }
-    };
-
-    typedef subr::nothing shape_info;
-
-    typedef std::tr1::unordered_map<shape_type, shape_info,
-				    shape_type::hasher> shape_map;
-    shape_map _m_shapes;
-
-    void add_shape (die_type &die, bool last_sibling);
-
     struct stats_cmp
       : public std::binary_function<const die_map::value_type *,
 				    const die_map::value_type *,
@@ -1206,6 +1196,7 @@ namespace elfutils
     {
     private:
       const std::vector<entry *> *_m_entry;
+      bool _m_final;
 
       inline circular_reference (const circular_reference &)
 	: value::value_reference ()
@@ -1216,14 +1207,16 @@ namespace elfutils
     public:
       inline circular_reference (const entry *die, copier *)
 	: value::value_reference (),
-	  _m_entry (new std::vector<entry *> (1, const_cast<entry *> (die)))
+	  _m_entry (new std::vector<entry *> (1, const_cast<entry *> (die))),
+	  _m_final (false)
       {
 	die->dump () << " new circular_reference " << this << "\n";
       }
 
       inline bool final () const
       {
-	return _m_entry == NULL;
+	// XXX was return _m_entry == NULL;
+	return _m_final;
       }
 
       inline typename std::vector<entry *>::const_iterator pending () const
@@ -1241,8 +1234,10 @@ namespace elfutils
       {
 	pending_entry ()->dump () << " placed circular_reference "
 				  << this << "\n";
-	delete _m_entry;
-	_m_entry = NULL;
+	// XXX Keeping around for local hash...
+	_m_final = true;
+	// delete _m_entry;
+	// _m_entry = NULL;
       }
 
       inline ~circular_reference ()
@@ -1256,14 +1251,11 @@ namespace elfutils
       }
 
       /* We have a special case for a reference attribute that is part
-	 of a circular chain.  That value always hashes as zero, so that
-	 each entry in a circular chain of references has the same hash
-	 value as any entry that it otherwise matches and that has any
-	 (eventually) circular reference as the corresponding
-	 attribute's value.  */
-      virtual size_t hash () const
+	 of a circular chain.  It gets calculated from the
+	 pending_entry. */
+      virtual die_info *get_die_info () const
       {
-	return 0;
+	return pending_entry ()->get_die_info ();
       }
     };
 
@@ -1298,9 +1290,14 @@ namespace elfutils
       // Set if _m_children contains any entries not already final.
       bool _m_unfinished_children;
 
+      // The die_info that will be used when putting the die into
+      // the collector. Stores local hash as soon as all children
+      // are defined in defined_self ().
+      die_info *_m_info;
+
       inline pending_entry (int tag)
 	: _m_finalizing (NULL), _m_self (NULL), _m_matched (NULL),
-	  _m_tag (tag), _m_unfinished_children (false)
+	  _m_tag (tag), _m_unfinished_children (false), _m_info (NULL)
       {}
 
       inline ~pending_entry ()
@@ -1385,6 +1382,84 @@ namespace elfutils
       typedef typename final_children_getter::
       template copy<debug_info_entry::children_type> get_final_children;
 
+      inline size_t get_reference_hash (std::vector<const entry *> &stack) const
+      {
+	assert (_m_info != NULL);
+
+	// Could already have been set by forward reference.
+	if (_m_info->_m_reference_hash != 0)
+	  return _m_info->_m_reference_hash;
+
+	size_t rhash = _m_info->_m_local_hash;
+	size_t attr_rhashes = 0;
+	for (attr_map::const_iterator it = _m_attributes.begin ();
+             it != _m_attributes.end ();
+             ++it)
+          {
+	    // XXX XOR is for order irrelevance, but shouldn't be necessary.
+	    // See also calculate_local_hash, which does the same.
+	    const entry *ref
+	      = dynamic_cast<const entry *> (it->second._m_value);
+	    if (ref != NULL)
+	      {
+		// Workaround weird case (bug?)
+		// https://fedorahosted.org/pipermail/elfutils-devel/2011-February/001792.html
+		if (it->first == DW_AT_containing_type
+		    && ref->_m_pending == this)
+		  continue;
+		else
+		  attr_rhashes ^= ref->get_reference_hash (stack);
+	      }
+          }
+	subr::hash_combine (rhash, attr_rhashes);
+
+	return rhash;
+      }
+
+      inline size_t calculate_local_hash ()
+      {
+	// Calculate the local hash for this new die.
+	// XOR the attribute values together (so order doesn't matter)
+	// but exclude reference attributes values (just include
+	// their tag). XXX - shouldn't be necessary, double check.
+	size_t lhash = _m_tag;
+	size_t attr_hash = 0;
+	for (attr_map::const_iterator it = _m_attributes.begin ();
+	     it != _m_attributes.end ();
+	     ++it)
+	  {
+	    if (it->second.what_space () != dwarf::VS_reference)
+	      attr_hash ^= subr::hash_this (*it);
+	    else
+	      attr_hash ^= (it->first << 3);
+	  }
+	subr::hash_combine (lhash, attr_hash);
+
+	size_t children_hash = 0;
+	for (typename std::vector<entry *>::const_iterator it
+	       = _m_children.begin ();
+	     it != _m_children.end ();
+	     ++it)
+	  {
+	    // child lhash is always in the die_info, which might
+	    // be in the pending_entry when not yet finalized, or
+	    // part of the finalized child die_info.
+	    size_t child_lhash;
+	    struct pending_entry *pending = (*it)->_m_pending;
+	    if (pending)
+	      child_lhash = pending->_m_info->_m_local_hash;
+	    else
+	      {
+		die_info_pair *final_child = get_final_child (*it);
+		child_lhash = final_child->second._m_local_hash;
+	      }
+	    subr::hash_combine (children_hash, child_lhash);
+	  }
+	subr::hash_combine (lhash, children_hash);
+
+	return lhash;
+      }
+
       inline die_info_pair *final (copier *c,
 				   ::Dwarf_Off offset, ::Dwarf_Off cost)
       {
@@ -1404,7 +1479,7 @@ namespace elfutils
 				  (_m_children, std::ptr_fun (get_final_child)),
 				  fresh);
 
-	    _m_matched = co->add_entry (_m_tag, children, attrs);
+	    _m_matched = co->add_entry (_m_tag, children, attrs, _m_info);
 	  }
 
 	// Final bookkeeping in the collector for this copied entry.
@@ -1514,7 +1589,7 @@ namespace elfutils
        built in the output has one of these in place of a value_reference.
        These all live in the _m_entries map, one per input-side DIE.  */
     struct entry
-      : public value::value_dispatch
+      : public value::value_reference
     {
       ::Dwarf_Off _m_offset; // For debugging and statistics only.
       ::Dwarf_Off _m_cost;   // For statistics only.
@@ -1603,10 +1678,9 @@ namespace elfutils
       }
 
       /* We are no longer an undefined entry, so decrement the count.
-	 Then finalize as much as we can now.  We attempt finalization
-	 even when the count is nonzero, so that a leaf entry with no
-	 forward references finishes immediately, and so then can its
-	 parents and on up if they don't own any pending references.  */
+	 But don't finalize yet. Since all children are known now we
+	 can create a candidate die_info that includes the local hash
+	 for this entry.  */
       inline void defined_self (copier *c)
       {
 	assert (_m_final == NULL);
@@ -1614,9 +1688,9 @@ namespace elfutils
 	assert (c->_m_undefined_entries > 0);
 	--c->_m_undefined_entries;
 	dump () << " defined_self => " << c->_m_undefined_entries << "\n";
-	finalize (c);
-	if (_m_final == NULL)
-	  assert (c->_m_undefined_entries > 0);
+
+	size_t lhash = _m_pending->calculate_local_hash ();
+	_m_pending->_m_info = new die_info (lhash);
       }
 
       /* A reference-following matching operation noticed along
@@ -1649,6 +1723,48 @@ namespace elfutils
 	  *p.second = true;
       }
 
+      /* Recursively sets up reference hashes for the die_info of this
+	 pending_entry.  Depends on all local hashes having been setup
+	 already.  At this point all entries are still pending.  */
+      inline void setup_reference_hash () const
+      {
+	std::vector<const entry *> stack;
+	_m_pending->_m_info->_m_reference_hash = get_reference_hash (stack);
+	assert (stack.empty ());
+
+        for (typename std::vector<entry *>::const_iterator it
+               = _m_pending->_m_children.begin ();
+             it != _m_pending->_m_children.end ();
+             ++it)
+	  (*it)->setup_reference_hash ();
+      }
+
+      inline size_t get_reference_hash (std::vector<const entry *> &stack) const
+      {
+	if (std::find (stack.begin (), stack.end (), this) != stack.end ())
+	  {
+	    std::cout << "Reference chain cycle detected\n"
+		      << "offset=[0x" << std::hex << _m_offset << std::dec
+		      << "] already on the reference chain stack\n";
+	    typename std::vector<const entry *>::iterator it;
+	    for (it = stack.begin ();
+		 it != stack.end ();
+		 it++)
+	      {
+		std::cout << "offset=[0x" << std::hex << (*it)->_m_offset
+			  << std::dec << "] "
+			  << dwarf::tags::name ((*it)->_m_pending->_m_tag)
+			  << "\n";
+	      }
+	    abort ();
+	  }
+
+	stack.push_back (this);
+	size_t res = _m_pending->get_reference_hash (stack);
+	stack.pop_back ();
+	return res;
+      }
+
       // Attempt to turn the pending entry into a final entry.
       void finalize (copier *c)
       {
@@ -1780,6 +1896,15 @@ namespace elfutils
 	assert (_m_pending != NULL);
 	return _m_parent->_m_pending->child (_m_self_idx);
       }
+
+      /* The local hash of the debug_info_entry if we are already
+	 final, otherwise get it from the pending_entry. */
+      inline die_info *get_die_info () const
+      {
+	if (_m_final)
+	  return &_m_final->second;
+	return _m_pending->_m_info;
+      }
     };
 
     // This object lives while we are copying one particular input DIE.
@@ -1874,11 +1999,22 @@ namespace elfutils
 	return *_m_copier;
       }
 
-      /* Complain if we still have dangling references.
+      /* Walk over the whole cu again to set reference hashes up.
+	 Then try to finalize everything at once.
+	 Complain if we still have dangling references.
 	 If not, it should be impossible to have pending entries left.  */
       inline die_info_pair *final_unit () const
       {
 	assert (_m_out == NULL);
+
+	// First walk over the whole CU tree again to setup the
+	// reference hash for each die_info.
+	_m_in->setup_reference_hash ();
+
+	// We should now be able to finalize everything at once.
+	if (_m_copier->_m_undefined_entries == 0)
+	  _m_in->finalize (_m_copier);
+
 	if (unlikely (_m_in->_m_final == NULL))
 	  {
 	    _m_in->dump_entry ();
diff --git a/libdw/c++/line_info.cc b/libdw/c++/line_info.cc
index e613c16b..df7a2172 100644
--- a/libdw/c++/line_info.cc
+++ b/libdw/c++/line_info.cc
@@ -61,6 +61,15 @@ stringform (Dwarf_Attribute *attr)
   return false;
 }
 
+/* Returns true if the attribute represents a valid zero udata.
+   This represents "no-file".  */
+static bool
+zero_formudata (Dwarf_Attribute *attr)
+{
+  Dwarf_Word zero;
+  return dwarf_formudata (attr, &zero) == 0 && zero == 0;
+}
+
 /* Mock up a dummy attribute with a special kludge that get_files groks.
    We use these for source_file objects consed directly from an index
    rather than from a real attribute.  */
@@ -91,7 +100,7 @@ get_files (const Dwarf_Attribute *attr, Dwarf_Files **files, Dwarf_Word *idx)
 Dwarf_Word
 dwarf::source_file::mtime () const
 {
-  if (stringform (thisattr ()))
+  if (stringform (thisattr ()) || zero_formudata (thisattr ()))
     return 0;
 
   Dwarf_Files *files;
@@ -106,7 +115,7 @@ dwarf::source_file::mtime () const
 Dwarf_Word
 dwarf::source_file::size () const
 {
-  if (stringform (thisattr ()))
+  if (stringform (thisattr ()) || zero_formudata (thisattr ()))
     return 0;
 
   Dwarf_Files *files;
@@ -118,12 +127,16 @@ dwarf::source_file::size () const
   return result;
 }
 
+static const char *no_file = "";
+
 const char *
 dwarf::source_file::name () const
 {
   const char *result;
   if (stringform (thisattr ()))
     result = dwarf_formstring (thisattr ());
+  else if (zero_formudata (thisattr ()))
+    result = no_file;
   else
     {
       Dwarf_Files *files;
@@ -154,6 +167,9 @@ dwarf::source_file::to_string () const
       return plain_string (result);
     }
 
+  if (zero_formudata (thisattr ()))
+    return plain_string (no_file);
+
   Dwarf_Files *files;
   Dwarf_Word idx;
   xif (thisattr (), get_files (thisattr (), &files, &idx));
diff --git a/libdw/c++/output-shape.cc b/libdw/c++/output-shape.cc
deleted file mode 100644
index 8d25b389..00000000
--- a/libdw/c++/output-shape.cc
+++ /dev/null
@@ -1,159 +0,0 @@
-/* elfutils::dwarf_output abbrev generation.
-   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>.  */
-
-#include <config.h>
-#include "dwarf_output"
-
-using namespace elfutils;
-
-static inline int
-attr_form (int tag, const dwarf_output::attribute &attr)
-{
-  switch (attr.second.what_space ())
-    {
-    case dwarf::VS_address:
-      return DW_FORM_addr;
-
-    case dwarf::VS_flag:
-      return DW_FORM_flag;
-
-    case dwarf::VS_reference:
-      return DW_FORM_ref_addr;
-
-    case dwarf::VS_string:
-    case dwarf::VS_identifier:
-      return DW_FORM_string;
-
-    case dwarf::VS_constant:
-      if (! attr.second.constant_is_integer ())
-	return DW_FORM_block;
-      /* Fall through.  */
-
-    case dwarf::VS_dwarf_constant:
-    case dwarf::VS_source_line:
-    case dwarf::VS_source_column:
-      return DW_FORM_udata;
-
-    case dwarf::VS_location:
-      if (!attr.second.location ().is_list ())
-	return DW_FORM_block;
-      /* Fall through.  */
-
-    case dwarf::VS_lineptr:
-    case dwarf::VS_macptr:
-    case dwarf::VS_rangelistptr:
-      /* For class *ptr (including loclistptr), the one of data[48] that
-	 matches offset_size is the only form encoding to use.  Other data*
-	 forms can mean the attribute is class constant instead.  */
-      return DW_FORM_data4;
-
-    case dwarf::VS_source_file:
-      switch (attr.first)
-	{
-	case DW_AT_decl_file:
-	case DW_AT_call_file:
-	  return DW_FORM_udata;
-
-	case DW_AT_comp_dir:
-	  return DW_FORM_string;
-
-	case DW_AT_name:
-	  switch (tag)
-	    {
-	    case DW_TAG_compile_unit:
-	    case DW_TAG_partial_unit:
-	      return DW_FORM_string;
-	    }
-	  break;
-	}
-      throw std::runtime_error ("source_file value unexpected in "
-				+ to_string (attr));
-
-    case dwarf::VS_discr_list:
-      return DW_FORM_block;
-    }
-
-  throw std::logic_error ("strange value_space");
-}
-
-inline void
-dwarf_output_collector::shape_type::hashnadd (int name, int form)
-{
-  subr::hash_combine (_m_hash, name);
-  subr::hash_combine (_m_hash, form);
-  _m_attrs.push_back (std::make_pair (name, form));
-}
-
-inline
-dwarf_output_collector::shape_type::shape_type (const die_type &die,
-						bool last_sibling)
-  : _m_has_children (die.has_children ()), _m_hash (8675309 << _m_has_children)
-{
-  if (!last_sibling)
-    hashnadd (DW_AT_sibling, DW_FORM_ref_udata);
-
-  for (die_type::attributes_type::const_iterator it = die.attributes ().begin ();
-       it != die.attributes ().end ();
-       ++it)
-    hashnadd (it->first, attr_form (die.tag (), *it));
-}
-#if 0
-void
-dwarf_output_collector::add_shape (die_type &die, bool last_sibling)
-{
-  assert (die._m_shape == NULL);
-
-  shape_map::value_type &x
-    = *_m_shapes.insert (std::make_pair (shape_type (die, last_sibling),
-					 shape_info ())).first;
-  // x.second.nusers++, etc.
-
-  die._m_shape = &x;
-}
-#endif