path: root/libdw/c++/output-shape.cc

/* 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 <cstdarg>
#include <byteswap.h>
#include "dwarf_output"
#include "../../src/dwarfstrings.h"

using namespace elfutils;

#define __unused __attribute__ ((unused))

namespace
{
  struct null_constraint_t
    : public dwarf_output::shape_type::form_constraint_t
  {
    virtual bool satisfied (__unused dwarf_output::debug_info_entry const &die,
			    __unused int attr,
			    __unused dwarf_output::attr_value const &value) const
    {
      return true;
    }

    virtual bool equal (form_constraint_t const *other) const;
  } null_constraint;

  bool
  null_constraint_t::equal (form_constraint_t const *other) const
  {
    return other == &null_constraint;
  }


  struct cu_local_ref_constraint_t
    : public dwarf_output::shape_type::form_constraint_t
  {
    virtual bool satisfied (__unused dwarf_output::debug_info_entry const &die,
			    __unused int attr,
			    __unused dwarf_output::attr_value const &value) const
    {
      return true; // xxx
    }

    virtual bool equal (form_constraint_t const *other) const;
  } cu_local_ref_constraint;

  bool
  cu_local_ref_constraint_t::equal (form_constraint_t const *other) const
  {
    return other == &cu_local_ref_constraint;
  }


  struct noreloc_constraint_t
    : public dwarf_output::shape_type::form_constraint_t
  {
    virtual bool satisfied (__unused dwarf_output::debug_info_entry const &die,
			    __unused int attr,
			    __unused dwarf_output::attr_value const &value) const
    {
      return true; // xxx
    }

    virtual bool equal (form_constraint_t const *other) const;
  } noreloc_constraint;

  bool
  noreloc_constraint_t::equal (form_constraint_t const *other) const
  {
    return other == &noreloc_constraint;
  }


  struct constraint_and
    : public dwarf_output::shape_type::form_constraint_t
  {
    form_constraint_t const *a;
    form_constraint_t const *b;

    constraint_and (form_constraint_t const *aa,
		    form_constraint_t const *bb)
      : a (aa), b (bb)
    {}

    virtual bool satisfied (dwarf_output::debug_info_entry const &die,
			    int attr,
			    dwarf_output::attr_value const &value) const
    {
      return a->satisfied (die, attr, value)
	&& b->satisfied (die, attr, value);
    }

    virtual bool equal (form_constraint_t const *other) const
    {
      if (constraint_and const *o
	    = dynamic_cast <constraint_and const *> (other))
	return (a->equal (o->a) && b->equal(o->b))
	  || (b->equal (o->a) && a->equal(o->b));
      else
	return false;
    }
  };
}

dwarf_output::shape_type::candidate_form::candidate_form
    (int a_form, form_constraint_t const *a_constraint)
  : _m_hash (0) // xxx
  , form (a_form)
  , constraint (a_constraint ?: &null_constraint)
{}

namespace
{
  struct ref_forms_t
    : public dwarf_output::shape_type::candidate_form_vec
  {
    ref_forms_t ()
    {
      typedef dwarf_output::shape_type::candidate_form
	candidate_form;
      static constraint_and local_noreloc_constaint (&cu_local_ref_constraint,
						     &noreloc_constraint);
      add (DW_FORM_ref_addr);
      add (candidate_form (DW_FORM_ref8, &cu_local_ref_constraint));
      add (candidate_form (DW_FORM_ref4, &cu_local_ref_constraint));
      add (candidate_form (DW_FORM_ref2, &local_noreloc_constaint));
      add (candidate_form (DW_FORM_ref1, &local_noreloc_constaint));
      add (candidate_form (DW_FORM_ref_udata, &local_noreloc_constaint));
    }
  } ref_forms;

  bool
  source_file_is_string (int tag, int attr)
  {
    switch (attr)
      {
      case DW_AT_decl_file:
      case DW_AT_call_file:
	return false;

      case DW_AT_comp_dir:
	return true;

      case DW_AT_name:
	switch (tag)
	  {
	  case DW_TAG_compile_unit:
	  case DW_TAG_partial_unit:
	    return true;
	  }
      }

    throw std::runtime_error ("can't decide whether source_file_is_string");
  }

  inline dwarf_output::shape_type::candidate_form_vec const &
  candidate_forms (int tag, int attr, const dwarf_output::attr_value &value)
  {
    // import some types into the namespace
    typedef dwarf_output::shape_type::candidate_form
      candidate_form;
    typedef dwarf_output::shape_type::candidate_form_vec
      candidate_form_vec;
    typedef dwarf_output::shape_type::form_constraint_t
      form_constraint_t;

    /* Having the most spacious form first means that simple sweep
       that picks the first suitable form picks that biggest one,
       meaning the form will be able to hold whatever data
       necessary.
       Having variable length the last means that in case of tie,
       fixed length forms that are easy to read win.  */
    static candidate_form_vec block_forms = candidate_form_vec ()
      .add (DW_FORM_block4)
      .add (DW_FORM_block2)
      .add (DW_FORM_block1)
      .add (DW_FORM_block);

    static candidate_form_vec const_forms = candidate_form_vec ()
      .add (DW_FORM_data8)
      .add (DW_FORM_data4)
      .add (candidate_form (DW_FORM_data2, &noreloc_constraint))
      .add (candidate_form (DW_FORM_data1, &noreloc_constraint))
      .add (candidate_form (DW_FORM_udata, &noreloc_constraint)) // xxx & nopatch constaint
      .add (candidate_form (DW_FORM_sdata, &noreloc_constraint));// xxx & nopatch constaint

    static candidate_form_vec string_forms = candidate_form_vec ()
      .add (DW_FORM_string)
      .add (DW_FORM_strp)
      ;

    switch (value.what_space ())
      {
      case dwarf::VS_address:
	{
	  static candidate_form_vec forms = candidate_form_vec ()
	    .add(DW_FORM_addr);
	  return forms;
	}

      case dwarf::VS_flag:
	{
	  static candidate_form_vec forms = candidate_form_vec ()
	    .add (DW_FORM_flag)
	    //.add (DW_FORM_flag_present) // xxx DWARF4
	    ;
	  return forms;
	}

      case dwarf::VS_reference:
	return ::ref_forms;

      case dwarf::VS_string:
      case dwarf::VS_identifier:
	return string_forms;

      case dwarf::VS_constant:
	if (!value.constant_is_integer ())
	  return block_forms;
	/* Fall through.  */

      case dwarf::VS_dwarf_constant:
      case dwarf::VS_source_line:
      case dwarf::VS_source_column:
	return const_forms;

      case dwarf::VS_location:
	if (!value.location ().is_list ())
	  return block_forms;
	/* Fall through.  */

      case dwarf::VS_lineptr:
      case dwarf::VS_macptr:
      case dwarf::VS_rangelistptr:
	/* This can be either data4 or data8 depending on the size of
	   the offset to the client data that we are trying to encode.
	   In DWARF 4, the only available offset is DW_FORM_sec_offset,
	   which is 4 bytes in 32-bit dwarf and 8 bytes in 64-bit.  */
	{
	  static candidate_form_vec forms = candidate_form_vec ()
	    //.add (DW_FORM_sec_offset) // xxx DWARF4
	    .add (DW_FORM_data8)
	    .add (DW_FORM_data4)
	    ;
	  return forms;
	}

      case dwarf::VS_source_file:
	if (source_file_is_string (tag, attr))
	  return string_forms;
	else
	  return const_forms;

      case dwarf::VS_discr_list:
	return block_forms;
      }

    throw std::logic_error ("strange value_space");
  }

  bool
  numerical_p (const dwarf_output::attr_value &value)
  {
    dwarf::value_space vs = value.what_space ();

    switch (vs)
      {
      case dwarf::VS_flag:
      case dwarf::VS_rangelistptr:
      case dwarf::VS_lineptr:
      case dwarf::VS_macptr:
      case dwarf::VS_location:
      case dwarf::VS_constant:
      case dwarf::VS_dwarf_constant:
      case dwarf::VS_source_line:
      case dwarf::VS_source_column:
      case dwarf::VS_address:

      // We can optimize strings here, too, we just take the length of
      // the string as the value to encode, and treat it specially.
      case dwarf::VS_string:
      case dwarf::VS_identifier:
      case dwarf::VS_source_file:
	return true;

      case dwarf::VS_reference:   // xxx this one is numerical in
				  // principle, but optimizing
				  // references is fun on its own and
				  // for much later
      case dwarf::VS_discr_list:
	return false;
      }

    abort ();
  }

  uint64_t
  numerical_value_to_optimize (int tag, int attr,
			       const dwarf_output::attr_value &value)
  {
    dwarf::value_space vs = value.what_space ();

    switch (vs)
      {
      case dwarf::VS_flag:
	return !!value.flag ();

      case dwarf::VS_rangelistptr:
      case dwarf::VS_lineptr:
      case dwarf::VS_macptr:
      case dwarf::VS_location:
	return 0; /* xxx */

      case dwarf::VS_constant:
	if (value.constant_is_integer ())
	  return value.constant ();
	else
	  return value.constant_block ().size ();

      case dwarf::VS_dwarf_constant:
	return value.dwarf_constant ();

      case dwarf::VS_source_line:
	return value.source_line ();

      case dwarf::VS_source_column:
	return value.source_column ();

      case dwarf::VS_address:
	return value.address ();

      case dwarf::VS_source_file:
	if (!source_file_is_string (tag, attr))
	  return 0; /* xxx */
	/* fall-through */

      case dwarf::VS_string:
      case dwarf::VS_identifier:
	return value.string ().size ();

      case dwarf::VS_reference:
      case dwarf::VS_discr_list:
	abort ();
      }

    abort ();
  }
}

dwarf_output::shape_type::shape_type (const debug_info_entry &die,
				      const dwarf_output::die_info &info)
  : _m_tag (die.tag ())
  , _m_has_children (die.has_children ())
  , _m_hash (8675309 << _m_has_children)
{
  // xxx Except it's perfectly legal for _m_with_sibling[false] and
  // _m_with_sibling[true] to be true simultaneously.
  bool has_sibling_at = info._m_with_sibling[true] && die.has_children ();
  if (has_sibling_at)
    _m_attrs.push_back (DW_AT_sibling);

  for (debug_info_entry::attributes_type::const_iterator it
	 = die.attributes ().begin ();
       it != die.attributes ().end (); ++it)
    _m_attrs.push_back (it->first);

  // Sort it, but leave sibling attribute at the beginning.
  std::sort (_m_attrs.begin () + (has_sibling_at ? 1 : 0), _m_attrs.end ());

  // Make sure the hash is computed based on canonical order of
  // (unique) attributes, not based on order in which the attributes
  // are in DIE.
  for (attrs_vec::const_iterator it = _m_attrs.begin ();
       it != _m_attrs.end (); ++it)
    subr::hash_combine (_m_hash, *it);
}

namespace
{
  template <class Iterator>
  void
  dw_write_uleb128 (Iterator it, uint64_t value)
  {
    do
      {
	uint8_t byte = value & 0x7fULL;
	value >>= 7;
	if (value != 0)
	  byte |= 0x80;
	*it++ = byte;
      }
    while (value != 0);
  }

  template <class Iterator>
  void
  dw_write_sleb128 (Iterator it, int64_t value)
  {
    bool more = true;
    do
      {
	uint8_t byte = value & 0x7fULL;
	value >>= 7;
	if ((value == 0 && !(byte & 0x40))
	    || (value == -1 && (byte & 0x40)))
	  more = false;
	else
	  byte |= 0x80;

	*it++ = byte;
      }
    while (more);
  }

  template <int width> struct width_to_int;

  template <> struct width_to_int <0>
  {
    typedef uint8_t unsigned_t;
    static uint8_t bswap (uint8_t value) { return value; }
  };

  template <> struct width_to_int <1>
    : width_to_int <0>
  {};

  template <> struct width_to_int <2>
  {
    typedef uint16_t unsigned_t;
    static uint16_t bswap (uint16_t value) { return bswap_16 (value); }
  };

  template <> struct width_to_int <4>
  {
    typedef uint32_t unsigned_t;
    static uint32_t bswap (uint32_t value) { return bswap_32 (value); }
  };

  template <> struct width_to_int <8>
  {
    typedef uint64_t unsigned_t;
    static uint64_t bswap (uint64_t value) { return bswap_64 (value); }
  };

  template <int width, class Iterator>
  void dw_write (Iterator it,
		 typename width_to_int<width>::unsigned_t value,
		 bool big_endian)
  {
    if (big_endian)
      value = width_to_int<width>::bswap (value);

    for (int i = 0; i < width; ++i)
      {
	*it++ = (uint8_t)value & 0xffUL;
	value >>= 8;
      }
  }

  template <class Iterator>
  void dw_write_var (Iterator it, unsigned width,
		     uint64_t value, bool big_endian)
  {
    switch (width)
      {
      case 8:
	::dw_write<8> (it, value, big_endian);
	break;
      case 4:
	::dw_write<4> (it, value, big_endian);
	break;
      case 2:
	::dw_write<2> (it, value, big_endian);
	break;
      case 1:
	::dw_write<1> (it, value, big_endian);
      case 0:
	break;
      default:
	throw std::runtime_error ("Width has to be 0, 1, 2, 4 or 8.");
      }
  }

  void dw_write_64 (section_appender &appender, bool is_64,
		    uint64_t value, bool big_endian)
  {
    size_t w = is_64 ? 8 : 4;
    dw_write_var (appender.alloc (w), w, value, big_endian);
  }

  void dw_write_form (section_appender &appender, int form,
		      uint64_t value, bool big_endian,
		      bool addr_64, bool dwarf_64)
  {
    switch (form)
      {
      case DW_FORM_flag_present:
	return;

#define HANDLE_DATA_REF(W)					\
	case DW_FORM_data##W:					\
	case DW_FORM_ref##W:					\
	  dw_write<W> (appender.alloc (W), value, big_endian);	\
	  return

      case DW_FORM_flag:
	assert (value == 1 || value == 0);
      case DW_FORM_block1:
      HANDLE_DATA_REF (1);

      case DW_FORM_block2:
      HANDLE_DATA_REF (2);

      case DW_FORM_block4:
      HANDLE_DATA_REF (4);

      HANDLE_DATA_REF (8);

#undef HANDLE_DATA_REF

      case DW_FORM_addr:
	dw_write_64 (appender, addr_64, value, big_endian);
	return;

      case DW_FORM_ref_addr:
      case DW_FORM_strp:
      case DW_FORM_sec_offset:
	// In these cases, we have to check that the value fits the
	// form.  If it doesn't switch to dwarf_64.
	if (!dwarf_64 && value > (uint64_t)(uint32_t)-1)
	  throw dwarf_output::writer::dwarf_32_not_enough ();
	dw_write_64 (appender, dwarf_64, value, big_endian);
	return;

      case DW_FORM_udata:
      case DW_FORM_ref_udata:
      case DW_FORM_exprloc:
      case DW_FORM_indirect:
	dw_write_uleb128 (std::back_inserter (appender), value);
	return;

      case DW_FORM_sdata:
	dw_write_sleb128 (std::back_inserter (appender), value);
      }

    throw std::runtime_error (std::string ("Don't know how to write ")
			      + dwarf_form_string (form));
  }

  class CountingIterator
  {
    size_t &_m_count;

  public:
    CountingIterator (size_t &count)
      : _m_count (count)
    {}

    CountingIterator (CountingIterator const &copy)
      : _m_count (copy._m_count)
    {}

    CountingIterator &operator= (CountingIterator const &other)
    {
      _m_count = other._m_count;
      return *this;
    }

    CountingIterator &operator++ (int)
    {
      _m_count++;
      return *this;
    }

    struct ref
    {
      template <class T>
      ref &operator= (T t __attribute__ ((unused)))
      {
	return *this;
      }
    };

    ref operator *()
    {
      return ref ();
    }
  };

  /* Return width of data stored with given form.  For block forms,
     return width of length field.  */
  size_t
  form_width (int form, bool addr_64, bool dwarf_64)
  {
    switch (form)
      {
      case DW_FORM_flag_present:
	return 0;

      case DW_FORM_block1:
      case DW_FORM_data1:
      case DW_FORM_flag:
      case DW_FORM_ref1:
	return 1;

      case DW_FORM_block2:
      case DW_FORM_data2:
      case DW_FORM_ref2:
	return 2;

      case DW_FORM_block4:
      case DW_FORM_data4:
      case DW_FORM_ref4:
	return 4;

      case DW_FORM_data8:
      case DW_FORM_ref8:
      case DW_FORM_ref_sig8:
	return 8;

      case DW_FORM_addr:
	return addr_64 ? 8 : 4;

      case DW_FORM_ref_addr:
      case DW_FORM_strp:
      case DW_FORM_sec_offset:
	return dwarf_64 ? 8 : 4;

      case DW_FORM_block:
      case DW_FORM_sdata:
      case DW_FORM_udata:
      case DW_FORM_ref_udata:
      case DW_FORM_exprloc:
      case DW_FORM_indirect:
	throw std::runtime_error
	  (std::string ("Can't compute width of LEB128 form ")
	   + dwarf_form_string (form));

      case DW_FORM_string:
	throw std::runtime_error
	  ("You shouldn't need the width of DW_FORM_string.");
      }

    throw std::runtime_error
      (std::string ("Don't know length of ") + dwarf_form_string (form));
  }

  size_t
  numerical_encoded_length (uint64_t value, int form,
			    bool addr_64, bool dwarf_64)
  {
    switch (form)
      {
      case DW_FORM_udata:
      case DW_FORM_ref_udata:
      case DW_FORM_exprloc:
      case DW_FORM_indirect:
      case DW_FORM_block:
      case DW_FORM_sdata:
	{
	  size_t count = 0;
	  CountingIterator counter (count);
	  if (form == DW_FORM_sdata)
	    dw_write_sleb128 (counter, value);
	  else
	    dw_write_uleb128 (counter, value);
	  return count;
	}

      case DW_FORM_string:
	return value + 1; /* For strings, we yield string length plus
			     terminating zero.  */

      default:
	return form_width (form, addr_64, dwarf_64);
      }
  }

  bool
  numerical_value_fits_form (uint64_t value, int form, bool addr_64)
  {
    switch (form)
      {
      case DW_FORM_flag_present:
	return value == 1;

      case DW_FORM_flag:
      case DW_FORM_data1:
      case DW_FORM_ref1:
      case DW_FORM_block1:
	return value <= (uint8_t)-1;

      case DW_FORM_data2:
      case DW_FORM_ref2:
      case DW_FORM_block2:
	return value <= (uint16_t)-1;

      case DW_FORM_ref_addr:
      case DW_FORM_strp:
      case DW_FORM_sec_offset:
	// We simply assume that these dwarf_64-dependent forms can
	// contain any value.  If dwarf_64==false && value > 32bit, we
	// throw an exception when we try to write that value.
	return true;

      case DW_FORM_string:
	// This can hold anything.
	return true;

      case DW_FORM_addr:
	if (addr_64)
	  return true;
	/* fall-through */
      case DW_FORM_data4:
      case DW_FORM_ref4:
      case DW_FORM_block4:
	return value <= (uint64_t)(uint32_t)-1;

      /* 64-bit forms.  Everything fits there.  */
      case DW_FORM_data8:
      case DW_FORM_ref8:
      case DW_FORM_udata:
      case DW_FORM_ref_udata:
      case DW_FORM_exprloc:
      case DW_FORM_indirect:
      case DW_FORM_block:
      case DW_FORM_sdata:
	return true;
      }

    throw std::runtime_error
      (std::string ("Don't know whether value fits ")
       + dwarf_form_string (form));
  }
}

void
dwarf_output::writer::write_string (std::string const &str,
				    int form,
				    section_appender &appender)
{
  if (form == DW_FORM_string)
    {
      std::copy (str.begin (), str.end (),
		 std::back_inserter (appender));
      appender.push_back (0);
    }
  else
    {
      assert (form == DW_FORM_strp);

      // xxx dwarf_64
      _m_str_backpatch.push_back
	(std::make_pair (gap (appender, 4, _m_big_endian),
			 _m_debug_str.add (str)));
    }
}

void
dwarf_output::shape_info::instantiate
  (dwarf_output::shape_type const &shape,
   dwarf_output_collector &col,
   bool addr_64, bool dwarf_64)
{
  // Prevent instance pointers from invalidation upon push_back.
  _m_instances.reserve (_m_users.size ());

  for (die_ref_vect::const_iterator it = _m_users.begin ();
       it != _m_users.end (); ++it)
    {
      instance_type inst;
      debug_info_entry const &die = *it;
      debug_info_entry::attributes_type const &attribs = die.attributes ();
      for (shape_type::attrs_vec::const_iterator at = shape._m_attrs.begin ();
	   at != shape._m_attrs.end (); ++at)
	{
	  int attr = *at;

	  // Optimization of sibling attribute will be done afterward.
	  // For now just stick the biggest form in there.
	  int form;
	  if (attr == DW_AT_sibling)
	    form = DW_FORM_ref8;
	  else
	    {
	      int tag = die.tag ();
	      dwarf_output::attr_value const &value
		= attribs.find (attr)->second;
	      shape_type::candidate_form_vec const &candidates
		= ::candidate_forms (tag, *at, value);

	      if (!numerical_p (value))
		{
		  form = -1;

		  // Just take the first form matching the
		  // constraints, we will optimize in separate sweep.
		  // Assume that candidates are stored in order from
		  // the most capacitous to the least.
		  for (shape_type::candidate_form_vec::const_iterator ct
			 = candidates.begin ();
		       ct != candidates.end (); ++ct)
		    if (ct->constraint->satisfied (die, attr, value))
		      {
			form = ct->form;
			break;
		      }
		  assert (form != -1);
		}
	      else
		{
		  size_t best_len = 0;
		  form = -1;

		  uint64_t opt_val
		    = numerical_value_to_optimize (tag, attr, value);

		  for (shape_type::candidate_form_vec::const_iterator ct
			 = candidates.begin ();
		       ct != candidates.end (); ++ct)
		    if (ct->constraint->satisfied (die, attr, value)
			&& numerical_value_fits_form (opt_val, ct->form,
						      addr_64))
		      {
			size_t len
			  = numerical_encoded_length (opt_val, ct->form,
						      addr_64, dwarf_64);
			if (form == -1 || len < best_len)
			  {
			    form = ct->form;
			    if (len == 1) // you can't top that
			      break;
			    best_len = len;
			  }
		      }
		  assert (form != -1);
		}
	    }
	  inst.forms.insert (std::make_pair (attr, form));
	}

      die_info &i = col._m_unique.find (die)->second;
      i.abbrev_ptr = _m_instances.end ();
      _m_instances.push_back (inst);
    }

  // xxx: instance merging?  Locate instances A and B (and C and ...?)
  // such that instance X can be created that covers all users of A
  // and B, and such that the space saved by removing the
  // abbreviations A and B tops the overhead of introducing non-ideal
  // (wrt users of A and B) X and moving all the users over to it.

  // Hmm, except that the is-advantageous math involves number of
  // users of the abbrev, and we don't know number of users before we
  // do the dissection of the tree to imported partial units.
}

void
dwarf_output::shape_info::build_data
    (dwarf_output::shape_type const &shape,
     dwarf_output::shape_info::instance_type const &inst,
     section_appender &appender)
{
  std::back_insert_iterator<section_appender> inserter
    = std::back_inserter (appender);
  ::dw_write_uleb128 (inserter, inst.code);
  ::dw_write_uleb128 (inserter, shape._m_tag);
  *inserter++ = shape._m_has_children ? DW_CHILDREN_yes : DW_CHILDREN_no;

  assert (shape._m_attrs.size () == inst.forms.size ());
  for (instance_type::forms_type::const_iterator it = inst.forms.begin ();
       it != inst.forms.end (); ++it)
    {
      // ULEB128 name & form
      ::dw_write_uleb128 (inserter, it->first);
      ::dw_write_uleb128 (inserter, it->second);
    }

  // 0 for name & form to terminate the abbreviation
  *inserter++ = 0;
  *inserter++ = 0;
}

dwarf_output::writer::gap::gap ()
  : _m_ptr (NULL)
{}

dwarf_output::writer::gap::gap (section_appender &appender, size_t len,
				bool big_endian, uint64_t base)
  : _m_ptr (appender.alloc (len)),
    _m_len (len),
    _m_big_endian (big_endian),
    _m_base (base)
{}

dwarf_output::writer::gap::gap (unsigned char *ptr, size_t len,
				bool big_endian, uint64_t base)
  : _m_ptr (ptr),
    _m_len (len),
    _m_big_endian (big_endian),
    _m_base (base)
{}

dwarf_output::writer::gap &
dwarf_output::writer::gap::operator= (gap const &other)
{
  _m_ptr = other._m_ptr;
  _m_len = other._m_len;
  _m_big_endian = other._m_big_endian;
  _m_base = other._m_base;
  return *this;
}

void
dwarf_output::writer::gap::patch (uint64_t value) const
{
  ::dw_write_var (_m_ptr, _m_len, value - _m_base, _m_big_endian);
}

dwarf_output::writer::writer (dwarf_output_collector &col,
			      dwarf_output &dw,
			      bool big_endian, bool addr_64, bool dwarf_64,
			      strtab &debug_str)
  : _m_col (col)
  , _m_dw (dw)
  , _m_addr_64 (addr_64)
  , _m_dwarf_64 (dwarf_64)
  , _m_big_endian (big_endian)
  , _m_debug_str (debug_str)
{
  size_t code = 0;
  for (dwarf_output_collector::die_map::const_iterator it
	 = col._m_unique.begin ();
       it != col._m_unique.end (); ++it)
    {
      dwarf_output::shape_type shape (it->first, it->second);
      shape_map::iterator st = _m_shapes.find (shape);
      if (st != _m_shapes.end ())
	st->second.add_user (it->first);
      else
	{
	  dwarf_output::shape_info i (it->first);
	  _m_shapes.insert (std::make_pair (shape, i));
	}
    }

  for (shape_map::iterator it = _m_shapes.begin ();
       it != _m_shapes.end (); ++it)
    {
      it->second.instantiate (it->first, col, addr_64, dwarf_64);
      for (dwarf_output::shape_info::instance_vec::iterator jt
	     = it->second._m_instances.begin ();
	   jt != it->second._m_instances.end (); ++jt)
	jt->code = ++code;
    }
}

void
dwarf_output::writer::output_debug_abbrev (section_appender &appender)
{
  for (shape_map::iterator it = _m_shapes.begin ();
       it != _m_shapes.end (); ++it)
    for (dwarf_output::shape_info::instance_vec::const_iterator jt
	   = it->second._m_instances.begin ();
	 jt != it->second._m_instances.end (); ++jt)
      it->second.build_data (it->first, *jt, appender);

  appender.push_back (0); // terminate table
}

class dwarf_output::writer::dump_die_tree
{
  // [(gap, die offset)]
  typedef std::vector<std::pair<gap, ::Dwarf_Off>> die_backpatch_vec;

  writer &_m_parent;
  section_appender &appender;
  die_off_map &die_off;
  die_backpatch_vec die_backpatch;
  uint64_t _m_cu_start;
  static const bool debug = false;

  void recursive_dump (die_info_pair const &info_pair,
		       gap &sibling_gap,
		       unsigned level)
  {
    static char const spaces[] =
      "                                                            "
      "                                                            "
      "                                                            ";
    static char const *tail = spaces + strlen (spaces);
    __attribute__ ((unused)) char const *pad = tail - level * 2;

    debug_info_entry const &die = info_pair.first;
    die_info const &info = info_pair.second;
    int tag = die.tag ();
    std::back_insert_iterator <section_appender> inserter
      = std::back_inserter (appender);

    /* Record where the DIE begins.  */
    die_off [die.offset ()] = appender.size ();
    if (debug)
      std::cout << pad << "CHILD " << dwarf_tag_string (die.tag ())
		<< " [0x" << std::hex << die_off [die.offset ()] << std::dec << "]"
		<< " " << std::flush;

    /* Our instance.  */
    shape_info::instance_type const &instance = *info.abbrev_ptr;
    ::dw_write_uleb128 (inserter, instance.code);

    if (debug)
      std::cout << " " << instance.code << std::endl;

    /* Dump attribute values.  */
    debug_info_entry::attributes_type const &attribs = die.attributes ();
    for (shape_info::instance_type::forms_type::const_iterator
	   at = instance.forms.begin (); at != instance.forms.end (); ++at)
      {
	int attr = at->first;
	int form = at->second;
	if (attr == DW_AT_sibling)
	  {
	    // XXX in fact we want to handle this case just like any
	    // other CU-local reference.  So also use this below (or
	    // better reuse single piece of code for reference
	    // handling).
	    if (debug)
	      std::cout << pad << "    " << dwarf_attr_string (attr)
			<< ":" << dwarf_form_string (form)
			<< " sibling=" << info._m_with_sibling[false]
			<< ":" << info._m_with_sibling[true]
			<< std::endl;
	    size_t gap_size = ::form_width (form,
					    _m_parent._m_addr_64,
					    _m_parent._m_dwarf_64);
	    sibling_gap = gap (appender, gap_size,
			       _m_parent._m_big_endian, _m_cu_start);
	    continue;
	  }

	debug_info_entry::attributes_type::const_iterator
	  vt = attribs.find (attr);
	assert (vt != attribs.end ());

	attr_value const &value = vt->second;
	if (false && debug)
	  std::cout << ":" << value.to_string () << std::endl;

	dwarf::value_space vs = value.what_space ();

	switch (vs)
	  {
	  case dwarf::VS_flag:
	    if (form == DW_FORM_flag)
	      *appender.alloc (1) = !!value.flag ();
	    else
	      assert (form == DW_FORM_flag_present);
	    break;

	  case dwarf::VS_rangelistptr:
	  case dwarf::VS_lineptr:
	  case dwarf::VS_macptr:
	    ::dw_write_form (appender, form, 0 /*xxx*/,
			     _m_parent._m_big_endian,
			     _m_parent._m_addr_64,
			     _m_parent._m_dwarf_64);
	    break;

	  case dwarf::VS_constant:
	    if (value.constant_is_integer ())
	      ::dw_write_form (appender, form, value.constant (),
			       _m_parent._m_big_endian,
			       _m_parent._m_addr_64,
			       _m_parent._m_dwarf_64);
	    else
	      {
		const std::vector<uint8_t> &block = value.constant_block ();
		::dw_write_form (appender, form, block.size (),
				 _m_parent._m_big_endian,
				 _m_parent._m_addr_64,
				 _m_parent._m_dwarf_64);
		std::copy (block.begin (), block.end (), inserter);
	      }
	    break;

	  case dwarf::VS_dwarf_constant:
	    ::dw_write_form (appender, form, value.dwarf_constant (),
			     _m_parent._m_big_endian,
			     _m_parent._m_addr_64,
			     _m_parent._m_dwarf_64);
	    break;

	  case dwarf::VS_source_line:
	    ::dw_write_form (appender, form, value.source_line (),
			     _m_parent._m_big_endian,
			     _m_parent._m_addr_64,
			     _m_parent._m_dwarf_64);
	    break;

	  case dwarf::VS_source_column:
	    ::dw_write_form (appender, form, value.source_column (),
			     _m_parent._m_big_endian,
			     _m_parent._m_addr_64,
			     _m_parent._m_dwarf_64);
	    break;

	  case dwarf::VS_string:
	    _m_parent.write_string (value.string (), form, appender);
	    break;

	  case dwarf::VS_identifier:
	    _m_parent.write_string (value.identifier (), form, appender);
	    break;

	  case dwarf::VS_source_file:
	    if (source_file_is_string (tag, attr))
	      {
		_m_parent.write_string (value.source_file ().name (),
					form, appender);
		break;
	      }
	    else
	      ::dw_write_form (appender, form, 0 /*xxx*/,
			       _m_parent._m_big_endian,
			       _m_parent._m_addr_64,
			       _m_parent._m_dwarf_64);
	    break;

	  case dwarf::VS_address:
	    {
	      assert (form == DW_FORM_addr);
	      size_t w = _m_parent._m_addr_64 ? 8 : 4;
	      ::dw_write_var (appender.alloc (w), w,
			      value.address (),
			      _m_parent._m_big_endian);
	    }
	    break;

	  case dwarf::VS_reference:
	    {
	      assert (form == DW_FORM_ref_addr);
	      // XXX dwarf64
	      die_backpatch.push_back
		(std::make_pair (gap (appender, 4, _m_parent._m_big_endian),
				 value.reference ()->offset ()));
	    }
	    break;

	  case dwarf::VS_location:
	    // XXX leave out for now
	    if (form == DW_FORM_block)
	      ::dw_write_uleb128 (inserter, 0);
	    else
	      ::dw_write_form (appender, form, 0 /*xxx*/,
			       _m_parent._m_big_endian,
			       _m_parent._m_addr_64,
			       _m_parent._m_dwarf_64);
	    break;

	  case dwarf::VS_discr_list:
	    throw std::runtime_error ("Can't handle VS_discr_list.");
	  };
      }

    if (!die.children ().empty ())
      {
	gap my_sibling_gap;
	Dwarf_Off die_offset = 0;
	for (std::vector<die_info_pair *>::const_iterator jt
	       = die.children ().info ().begin (); ;)
	  {
	    if (my_sibling_gap.valid ())
	      {
		die_backpatch.push_back
		  (std::make_pair (my_sibling_gap,
				   (*jt)->first.offset ()));
		my_sibling_gap = gap ();
	      }
	    die_offset = appender.size ();
	    recursive_dump (**jt, my_sibling_gap, level + 1);
	    if (++jt == die.children ().info ().end ())
	      {
		assert (!my_sibling_gap.valid ());
		break;
	      }
	  }
	*inserter++ = 0;
      }
  }

public:
  dump_die_tree (writer &writer,
		 section_appender &a_appender,
		 die_off_map &a_die_off,
		 uint64_t cu_start,
		 die_info_pair const &info_pair)
    : _m_parent (writer),
      appender (a_appender),
      die_off (a_die_off),
      _m_cu_start (cu_start)
  {
    gap fake_gap;
    recursive_dump (info_pair, fake_gap, 0);
    assert (!fake_gap.valid ());

    for (die_backpatch_vec::const_iterator it = die_backpatch.begin ();
	 it != die_backpatch.end (); ++it)
      {
	die_off_map::const_iterator jt = die_off.find (it->second);
	assert (jt != die_off.end ());
	it->first.patch (jt->second);
      }
  }
};

void
dwarf_output::writer::output_debug_info (section_appender &appender)
{
  std::back_insert_iterator <section_appender> inserter
    = std::back_inserter (appender);

  for (compile_units::const_iterator it = _m_dw._m_units.begin ();
       it != _m_dw._m_units.end (); ++it)
    {
      // Remember where the unit started for back-patching of size.
      size_t cu_start = appender.size ();

      // Unit length.
      gap length_gap (appender,
		      _m_dwarf_64 ? 8 : 4,
		      _m_big_endian);

      // Version.
      ::dw_write<2> (appender.alloc (2), 3, _m_big_endian);

      // Debug abbrev offset.  Use the single abbrev table that we
      // emit at offset 0.
      ::dw_write<4> (appender.alloc (4), 0, _m_big_endian);

      // Size in bytes of an address on the target architecture.
      *inserter++ = _m_addr_64 ? 8 : 4;

      die_off_map die_off;

      dump_die_tree (*this, appender, die_off, cu_start,
		     *_m_col._m_unique.find (*it));

      /* Back-patch length.  */
      size_t length = appender.size () - cu_start - 4; // -4 for length info. XXX dwarf64
      assert (length < (uint32_t)-1); // XXX temporary XXX dwarf64
      length_gap.patch (length);
    }
}

void
dwarf_output::writer::apply_patches ()
{
  for (str_backpatch_vec::const_iterator it = _m_str_backpatch.begin ();
       it != _m_str_backpatch.end (); ++it)
    it->first.patch (ebl_strtaboffset (it->second));
}