path: root/libdw/c++/dwarf_tracker

/* 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"
#include <tr1/unordered_map>
#include <tr1/unordered_set>

namespace elfutils
{
  // Basic tracker of tree-walk paths to DIEs.
  template<typename dw>
  class dwarf_path_finder
  {
  public:
    typedef typename dw::compile_units::const_iterator cu;
    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;

  private:
    // We use a singleton list of a default-constructed iterator as a marker.
    static inline const die_path bad_die_path ()
    {
      return die_path (1);
    }
    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 ();
    }

    /* 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::debug_info_entry::identity_type,
				    const die_path> die_map;
    die_map *_m_seen;
    bool _m_delete_seen;

    cu _m_root;

    die_path _m_path;

    explicit dwarf_path_finder (const dwarf_path_finder &)
    {
      throw std::logic_error ("not copy-constructible");
    }

  public:
    // Default constructor: an original tracker.
    inline dwarf_path_finder ()
      : _m_seen (new die_map), _m_delete_seen (true)
    {}

    // Construct a derived tracker: does its own whole walk, but sharing caches.
    inline dwarf_path_finder (const dwarf_path_finder &proto, bool)
      : _m_seen (proto._m_seen), _m_delete_seen (false)
    {}

    // Construct a derived tracker that jump-starts a walk.
    inline dwarf_path_finder (const dwarf_path_finder &proto,
			      const die_path &context, const die &there)
      : _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 ()
    {
      if (_m_delete_seen)
	{
	  delete _m_seen;
	  // We should never be left with a partial walk on the books.
	  assert (_m_path.empty ());
	}
    }

    // Main hooks for a normal walk.

    /* A walk object does set-up work when constructed and tear-down
       work when destroyed, so tear-down is done even for exceptions.  */
    struct walk
    {
      dwarf_path_finder *_m_tracker;
      inline walk (dwarf_path_finder *w, const cu &root)
	: _m_tracker (w)
      {
	assert (_m_tracker->_m_path.empty ());
	_m_tracker->_m_root = root;
      }
      inline ~walk ()
      {
	assert (_m_tracker->_m_path.empty ());
	_m_tracker->_m_root = cu ();
      }
    };

    /* A step object does pre-order work when constructed and post-order
       work when destroyed, so post-order is done even for exceptions.
       While this object lives, HERE is on the _m_path stack.  */
    struct step
    {
      dwarf_path_finder *_m_walker;
      inline step (dwarf_path_finder *w, const die &here)
	: _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.
	_m_walker->_m_path.push_back (here);
      }
      inline ~step ()
      {
	_m_walker->_m_path.pop_back ();
      }
    };

    // Random access to a DIE, find the path of the walk that gets there.
    inline const die_path &path_to (const die &a)
    {
      const dwarf::debug_info_entry::identity_type id = a->identity ();
      std::pair<typename die_map::iterator, bool> found
	= _m_seen->insert (std::make_pair (id, bad_die_path ()));
      if (found.second
	  /* It's not in our _m_seen map.  Our main walk recording
	     into _m_seen is exhaustive, so this can only be a forward
	     reference.  That is, we didn't already hit this DIE in
	     our top-level walk and so it is not in _m_seen yet.

	     We must do a separate walk to find it.  Since we know
	     this is a forward reference, we don't have to start a
	     fresh walk from the root, just momentarily wind forward
	     from where we are.  */
	  && !walk_down_to (id, found.first)
	  && !walk_over_to (id, found.first)
	  && !walk_up_to (id, found.first))
	throw std::runtime_error ("DIE not reachable from CU!");
      assert (&found.first->second != NULL);
      assert (!bad_die_path (found.first->second));
      return found.first->second;
    }

  private:
    inline bool walk_to (const typename die::value_type &here,
			 dwarf::debug_info_entry::identity_type there,
			 typename die_map::iterator &cache)
    {
      return walk_to (here.children ().begin (),
		      here.children ().end (),
		      there, cache);
    }

    bool walk_to (die it, const die &end,
		  dwarf::debug_info_entry::identity_type there,
		  typename die_map::iterator &cache)
    {
      for (; it != end; ++it)
	{
	  /* Note that we compare identities here, rather than passing down
	     a THERE iterator and comparing iterators.  In dwarf_output, we
	     can have multiple iterators into distinct children_type vectors
	     that all point to the same entry.  A reference could be one of
	     these iterators, and all mean the same entry.  */
	  if (it->identity () == there)
	    {
	      /* We can't keep the old CACHE iterator and avoid this
		 find (hash lookup), because there could have been
		 other insertions in the map since it was taken.
		 Those can invalidate old iterators.  */
	      cache = _m_seen->find (there);
	      _m_seen->erase (cache);
	      cache = _m_seen->insert (cache, std::make_pair (there, _m_path));
	      return true;
	    }
	  else
	    {
	      /* Do "step into" even for !has_children ()
		 because it records this child in _m_seen,
		 which we will rely on later.  */
	      step into (this, it);
	      const typename die::value_type &child = *it;
	      if (child.has_children () && walk_to (child, there, cache))
		return true;
	    }
	}
      return false;
    }

    /* First descend into the current DIE's children.
       _m_path already has the current DIE, so it is ready to go.  */
    // XXX is a reference to an owned DIE really possible??
    inline bool walk_down_to (dwarf::debug_info_entry::identity_type there,
			      typename die_map::iterator &cache)
    {
      const die &start = _m_path.back ();
      const typename die::value_type &here = *start;

      /* It's common to have a reference to the next sibling DIE.
	 So bypass the descent to HERE's children if THERE is
	 HERE's immediate next sibling.  */
      if (!here.has_children () || there == (++die (start))->identity ())
	return false;

      return walk_to (here, there, cache);
    }

    /* A step_back object pops the current DIE off _m_path when
       constructed, and pushes it back when destroyed.  */
    struct step_back
    {
      dwarf_path_finder *_m_walker;
      const die _m_here;
      inline step_back (dwarf_path_finder *w, die &copy)
	: _m_walker (w), _m_here (w->_m_path.back ())
      {
	w->_m_path.pop_back ();
	copy = _m_here;
      }
      inline ~step_back ()
      {
	_m_walker->_m_path.push_back (_m_here);
      }
    };

    /* Now wind the walk forward starting from the current DIE's
       immediate sibling.  */
    inline bool walk_over_to (dwarf::debug_info_entry::identity_type there,
			      typename die_map::iterator &cache)
    {
      die next;
      step_back from (this, next);
      ++next;

      return walk_to (next, (_m_path.empty ()
			     ? (*_m_root).children ().end ()
			     : _m_path.back ()->children ().end ()),
		      there, cache);
    }

    /* A step_up object saves _m_path when constructed
       and restores it when destroyed.  */
    struct step_up
    {
      dwarf_path_finder *_m_walker;
      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);
      }
    };

    /* Now wind the walk forward starting from the current DIE's
       parent's immediate sibling.  */
    inline bool walk_up_to (dwarf::debug_info_entry::identity_type there,
			    typename die_map::iterator &cache)
    {
      if (_m_path.empty ())
	return false;

      step_up from (this);

      do
	{
	  _m_path.pop_back ();
	  assert (!_m_path.empty ());
	  if (walk_over_to (there, cache))
	    return true;
	}
      while (!_m_path.empty ());

      return false;
    }
  };

  // Standard tracker.
  template<class dwarf1, class dwarf2>
  class dwarf_ref_tracker : public dwarf_tracker_base<dwarf1, dwarf2>
  {
  private:
    typedef dwarf_tracker_base<dwarf1, dwarf2> _base;

    explicit dwarf_ref_tracker (const dwarf_ref_tracker &)
       : _base ()
    {
      throw std::logic_error ("not copy-constructible");
    }

  public:
    typedef typename _base::cu1 cu1;
    typedef typename _base::cu2 cu2;
    typedef typename _base::die1 die1;
    typedef typename _base::die2 die2;
    typedef typename _base::dwarf1_ref dwarf1_ref;

  protected:
    typedef dwarf_path_finder<dwarf1> tracker1;
    typedef dwarf_path_finder<dwarf2> tracker2;

    tracker1 _m_left;
    tracker2 _m_right;

    struct ref_hasher : public std::unary_function<die2, size_t>
    {
      inline size_t operator () (const die2 &i) const
      {
	return i->identity ();
      }
    };

    struct same_ref : public std::equal_to<die2>
    {
      inline bool operator () (const die2 &a, const die2 &b) const
      {
	return a->identity () == b->identity ();
      }
    };

    typedef std::pair<const die2 *,
		      std::tr1::unordered_set<die2, ref_hasher, same_ref>
		      > equiv_list;
    typedef std::tr1::unordered_map<dwarf::debug_info_entry::identity_type,
				    equiv_list> equiv_map;
    equiv_map *_m_equiv;
    bool _m_delete_equiv;

    inline equiv_list *equiv_to (const die1 &a)
    {
      return &(*_m_equiv)[a->identity ()];
    }

    /* 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)
      {
	if (a->tag () != b->tag ())
	  return false;
	dwarf_tracker_base<dwarf1, dwarf2> t;
	return (dwarf_comparator<dwarf1, dwarf2, true> (t)
		.equals (a->attributes (), b->attributes ()));
      }
    };

  public:
    inline dwarf_ref_tracker ()
      : _m_equiv (new equiv_map), _m_delete_equiv (true)
    {}

    inline dwarf_ref_tracker (const tracker2 &proto)
      : _m_right (proto, true),
	_m_equiv (new equiv_map), _m_delete_equiv (true)
    {}

    inline ~dwarf_ref_tracker ()
    {
      if (_m_delete_equiv)
	delete _m_equiv;
    }

    inline void reset ()
    {
      _m_equiv->clear ();
      assert (!_m_right->_m_delete_seen);
      _m_right._m_seen->clear ();
    }

    struct walk
    {
      typename tracker1::walk _m_left;
      typename tracker2::walk _m_right;

      inline walk (dwarf_ref_tracker *w, const cu1 &a, const cu2 &b)
	: _m_left (&w->_m_left, a), _m_right (&w->_m_right, b)
      {}
    };

    struct step
    {
      typename tracker1::step _m_left;
      typename tracker2::step _m_right;

      inline step (dwarf_ref_tracker *w, const die1 &a, const die2 &b)
	: _m_left (&w->_m_left, a), _m_right (&w->_m_right, b)
      {}
    };

    typedef typename tracker1::die_path left_context_type;
    inline const left_context_type &left_context (const die1 &die)
    {
      return _m_left.path_to (die);
    }

    typedef typename tracker2::die_path 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 () != b.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 ());
    }

    class reference_match
    {
      friend class dwarf_ref_tracker;
    private:
      equiv_list *_m_elt;

    public:

      inline reference_match ()
	: _m_elt (NULL)
      {}

      inline ~reference_match ()
      {
	if (_m_elt != NULL)
	  _m_elt->first = NULL;
      }

      inline bool cannot_match () const
      {
	return _m_elt == NULL;
      }

      inline void notice_match (const die2 &b, bool matches) const
      {
	if (matches && _m_elt != NULL)
	  _m_elt->second.insert (b);
      }
    };

    inline bool
    reference_matched (reference_match &matched, const die1 &a, const die2 &b)
    {
      equiv_list *elt = equiv_to (a);
      if (elt->first == NULL)
	{
	  /* Record that we have a walk in progress crossing A.
	     When MATCHED goes out of scope in our caller, its
	     destructor will reset ELT->first to clear this record.  */
	  elt->first = &b;
	  matched._m_elt = elt;

	  // Short-circuit if we have already matched B to A.
	  return elt->second.find (b) != elt->second.end ();
	}

      /* We have a circularity.  We can tell because ELT->first remains
	 set from an outer recursion still in progress.

	 The circular chain of references rooted at A matches B if B is
	 also the root of its own circularity and everything along those
	 parallel chains matches.  If the chains hadn't matched so far,
	 we would not have kept following them to get here.

	 We recorded the B that arrived at the first comparison with A.
	 We actually record the pointer on the caller's stack rather
	 than a copy of B, just because the iterator might be larger.  */

      return *elt->first == b;
    }

    // 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),
	_m_equiv (proto._m_equiv), _m_delete_equiv (false)
    {
      // We are starting a recursive consideration of a vs b.
    }
  };
};

#endif	// <elfutils/dwarf_tracker>