openbsd-src / usr.bin / ctfconv / parse.c

/*	$OpenBSD: parse.c,v 1.20 2024/02/22 13:17:18 claudio Exp $ */

/*
 * Copyright (c) 2016-2017 Martin Pieuchot
 * Copyright (c) 2016 Jasper Lievisse Adriaanse <[e-mail]>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * DWARF to IT (internal type) representation parser.
 */

#include <sys/queue.h>
#include <sys/tree.h>
#include <sys/types.h>
#include <sys/ctf.h>

#include <assert.h>
#include <limits.h>
#include <err.h>
#include <stdlib.h>
#include <string.h>

#include "itype.h"
#include "xmalloc.h"
#include "dwarf.h"
#include "dw.h"
#include "pool.h"

#ifdef DEBUG
#include <stdio.h>
#endif

#ifndef NOPOOL
struct pool it_pool, im_pool, ir_pool;
#endif /* NOPOOL */

#ifndef nitems
#define nitems(_a)	(sizeof((_a)) / sizeof((_a)[0]))
#endif

#ifdef DEBUG
#define DPRINTF(x...)	do { printf(x); } while (0)
#else
#define DPRINTF(x...)	do { ; } while (0)
#endif

#define VOID_OFFSET	1	/* Fake offset for generating "void" type. */

/*
 * Tree used to resolve per-CU types based on their offset in
 * the abbrev section.
 */
RB_HEAD(ioff_tree, itype);

/*
 * Per-type trees used to merge existing types with the ones of
 * a newly parsed CU.
 */
RB_HEAD(itype_tree, itype)	 itypet[CTF_K_MAX];

/*
 * Tree of symbols used to build a list matching the order of
 * the ELF symbol table.
 */
struct isymb_tree	 isymbt;

struct itype		*void_it;		/* no type is emited for void */
uint16_t		 tidx, fidx, oidx;	/* type, func & object IDs */
uint16_t		 long_tidx;		/* index of "long", for array */


void		 cu_stat(void);
void		 cu_parse(struct dwcu *, struct itype_queue *,
		     struct ioff_tree *);
void		 cu_resolve(struct dwcu *, struct itype_queue *,
		     struct ioff_tree *);
void		 cu_reference(struct dwcu *, struct itype_queue *);
void		 cu_merge(struct dwcu *, struct itype_queue *);

struct itype	*parse_base(struct dwdie *, size_t);
struct itype	*parse_refers(struct dwdie *, size_t, int);
struct itype	*parse_array(struct dwdie *, size_t);
struct itype	*parse_enum(struct dwdie *, size_t);
struct itype	*parse_struct(struct dwdie *, size_t, int, size_t);
struct itype	*parse_function(struct dwdie *, size_t);
struct itype	*parse_funcptr(struct dwdie *, size_t);
struct itype	*parse_variable(struct dwdie *, size_t);

void		 subparse_subrange(struct dwdie *, size_t, struct itype *);
void		 subparse_enumerator(struct dwdie *, size_t, struct itype *);
void		 subparse_member(struct dwdie *, size_t, struct itype *, size_t);
void		 subparse_arguments(struct dwdie *, size_t, struct itype *);

size_t		 dav2val(struct dwaval *, size_t);
const char	*dav2str(struct dwaval *);
const char	*enc2name(unsigned short);

struct itype	*it_new(uint64_t, size_t, const char *, uint32_t, uint16_t,
		     uint64_t, uint16_t, unsigned int);
void		 it_merge(struct itype *, struct itype *);
void		 it_reference(struct itype *);
void		 it_free(struct itype *);
int		 it_cmp(struct itype *, struct itype *);
int		 it_name_cmp(struct itype *, struct itype *);
int		 it_off_cmp(struct itype *, struct itype *);
void		 ir_add(struct itype *, struct itype *);
void		 ir_purge(struct itype *);
struct imember	*im_new(const char *, size_t, size_t);

RB_GENERATE(itype_tree, itype, it_node, it_cmp);
RB_GENERATE(isymb_tree, itype, it_node, it_name_cmp);
RB_GENERATE(ioff_tree, itype, it_node, it_off_cmp);

/*
 * Construct a list of internal type and functions based on DWARF
 * INFO and ABBREV sections.
 *
 * Multiple CUs are supported.
 */
void
dwarf_parse(const char *infobuf, size_t infolen, const char *abbuf,
    size_t ablen)
{
	struct dwbuf		 info = { .buf = infobuf, .len = infolen };
	struct dwbuf		 abbrev = { .buf = abbuf, .len = ablen };
	struct dwcu		*dcu = NULL;
	struct ioff_tree	 cu_iofft;
	struct itype_queue	 cu_itypeq;
	struct itype		*it;
	int			 i;

	for (i = 0; i < CTF_K_MAX; i++)
		RB_INIT(&itypet[i]);
	RB_INIT(&isymbt);

	void_it = it_new(++tidx, VOID_OFFSET, "void", 0,
	    CTF_INT_SIGNED, 0, CTF_K_INTEGER, 0);
	TAILQ_INSERT_TAIL(&itypeq, void_it, it_next);

	while (dw_cu_parse(&info, &abbrev, infolen, &dcu) == 0) {
		TAILQ_INIT(&cu_itypeq);

		/* We use a tree to speed-up type resolution. */
		RB_INIT(&cu_iofft);

		/* Parse this CU */
		cu_parse(dcu, &cu_itypeq, &cu_iofft);

		/* Resolve its types. */
		cu_resolve(dcu, &cu_itypeq, &cu_iofft);
		assert(RB_EMPTY(&cu_iofft));

		/* Mark used type as such. */
		cu_reference(dcu, &cu_itypeq);

#ifdef DEBUG
		/* Dump statistics for current CU. */
		cu_stat();
#endif

		/* Merge them with the common type list. */
		cu_merge(dcu, &cu_itypeq);

		dw_dcu_free(dcu);
	}

	/* We force array's index type to be 'long', for that we need its ID. */
	RB_FOREACH(it, itype_tree, &itypet[CTF_K_INTEGER]) {
		if (it_name(it) == NULL || it->it_size != (8 * sizeof(long)))
			continue;

		if (strcmp(it_name(it), "unsigned") == 0) {
			long_tidx = it->it_idx;
			break;
		}
	}
}

struct itype *
it_new(uint64_t index, size_t off, const char *name, uint32_t size,
    uint16_t enc, uint64_t ref, uint16_t type, unsigned int flags)
{
	struct itype *it;
#ifndef NOPOOL
	static int it_pool_inited = 0;

	if (!it_pool_inited) {
		pool_init(&it_pool, "it", 512, sizeof(struct itype));
		pool_init(&im_pool, "im", 1024, sizeof(struct imember));
		pool_init(&ir_pool, "ir", 1024, sizeof(struct itref));
		it_pool_inited = 1;
	}
#endif

	assert((name != NULL) || !(flags & (ITF_FUNC|ITF_OBJ)));

	it = pmalloc(&it_pool, sizeof(*it));
	SIMPLEQ_INIT(&it->it_refs);
	TAILQ_INIT(&it->it_members);
	it->it_off = off;
	it->it_ref = ref;
	it->it_refp = NULL;
	it->it_size = size;
	it->it_nelems = 0;
	it->it_enc = enc;
	it->it_idx = index;
	it->it_type = type;
	it->it_flags = flags;

	if (name == NULL) {
		it->it_flags |= ITF_ANON;
	} else {
		size_t n;

		if ((n = strlcpy(it->it_name, name, ITNAME_MAX)) > ITNAME_MAX)
			warnx("name %s too long %zd > %d", name, n, ITNAME_MAX);
	}

	return it;
}

struct itype *
it_dup(struct itype *it)
{
	struct imember *copim, *im;
	struct itype *copit;

	copit = it_new(it->it_idx, it->it_off, it_name(it), it->it_size,
	    it->it_enc, it->it_ref, it->it_type, it->it_flags);

	copit->it_refp = it->it_refp;
	copit->it_nelems = it->it_nelems;

	TAILQ_FOREACH(im, &it->it_members, im_next) {
		copim = im_new(im_name(im), im->im_ref, im->im_off);
		copim->im_refp = im->im_refp;
		TAILQ_INSERT_TAIL(&copit->it_members, copim, im_next);
	}

	return copit;
}

/*
 * Merge the content of ``it'', the full type declaration into the
 * forwarding representation ``fwd''.
 */
void
it_merge(struct itype *fwd, struct itype *it)
{
	assert(fwd->it_flags & ITF_FORWARD);
	assert(fwd->it_type == it->it_type);
	assert(TAILQ_EMPTY(&fwd->it_members));
	assert(SIMPLEQ_EMPTY(&it->it_refs));

	fwd->it_off = it->it_off;
	fwd->it_ref = it->it_ref;
	fwd->it_refp = it->it_refp;
	fwd->it_size = it->it_size;
	fwd->it_nelems = it->it_nelems;
	fwd->it_enc = it->it_enc;
	fwd->it_flags = it->it_flags;

	TAILQ_CONCAT(&fwd->it_members, &it->it_members, im_next);
	assert(TAILQ_EMPTY(&it->it_members));
}

const char *
it_name(struct itype *it)
{
	if (!(it->it_flags & ITF_ANON))
		return it->it_name;

	return NULL;
}

void
it_reference(struct itype *it)
{
	struct imember *im;

	if (it == NULL || it->it_flags & ITF_USED)
		return;

	it->it_flags |= ITF_USED;

	it_reference(it->it_refp);
	TAILQ_FOREACH(im, &it->it_members, im_next)
		it_reference(im->im_refp);
}

void
it_free(struct itype *it)
{
	struct imember *im;

	if (it == NULL)
		return;

	while ((im = TAILQ_FIRST(&it->it_members)) != NULL) {
		TAILQ_REMOVE(&it->it_members, im, im_next);
		pfree(&im_pool, im);
	}

	ir_purge(it);
	pfree(&it_pool, it);
}

/*
 * Return 0 if ``a'' matches ``b''.
 */
int
it_cmp(struct itype *a, struct itype *b)
{
	if (a->it_type > b->it_type)
		return 1;
	if (a->it_type < b->it_type)
		return -1;

	/* Basic types need to have the same encoding and size. */
	if ((a->it_type == CTF_K_INTEGER || a->it_type == CTF_K_FLOAT)) {
		if (a->it_enc > b->it_enc)
			return 1;
		if (a->it_enc < b->it_enc)
			return -1;
		if (a->it_size > b->it_size)
			return 1;
		if (a->it_size < b->it_size)
			return -1;
	}

	/* Arrays need to have same number of elements */
	if (a->it_type == CTF_K_ARRAY) {
		if (a->it_nelems > b->it_nelems)
			return 1;
		if (a->it_nelems < b->it_nelems)
			return -1;
	}

	/* Match by name */
	if (!(a->it_flags & ITF_ANON) && !(b->it_flags & ITF_ANON))
		return strcmp(it_name(a), it_name(b));

	/* Only one of them is anonym */
	if ((a->it_flags & ITF_ANON) != (b->it_flags & ITF_ANON))
		return (a->it_flags & ITF_ANON) ? -1 : 1;

	/* Match by reference */
	if ((a->it_refp != NULL) && (b->it_refp != NULL))
		return it_cmp(a->it_refp, b->it_refp);
	if (a->it_refp == NULL)
		return -1;
	if (b->it_refp == NULL)
		return 1;

	return 0;
}

int
it_name_cmp(struct itype *a, struct itype *b)
{
	int diff;

	if ((diff = strcmp(it_name(a), it_name(b))) != 0)
		return diff;

	return ((a->it_flags|ITF_MASK) - (b->it_flags|ITF_MASK));
}

int
it_off_cmp(struct itype *a, struct itype *b)
{
	return a->it_off - b->it_off;
}

void
ir_add(struct itype *it, struct itype *tmp)
{
	struct itref *ir;

	SIMPLEQ_FOREACH(ir, &tmp->it_refs, ir_next) {
		if (ir->ir_itp == it)
			return;
	}

	ir = pmalloc(&ir_pool, sizeof(*ir));
	ir->ir_itp = it;
	SIMPLEQ_INSERT_TAIL(&tmp->it_refs, ir, ir_next);
}

void
ir_purge(struct itype *it)
{
	struct itref *ir;

	while ((ir = SIMPLEQ_FIRST(&it->it_refs)) != NULL) {
		SIMPLEQ_REMOVE_HEAD(&it->it_refs, ir_next);
		pfree(&ir_pool, ir);
	}
}

struct imember *
im_new(const char *name, size_t ref, size_t off)
{
	struct imember *im;

	im = pmalloc(&im_pool, sizeof(*im));
	im->im_ref = ref;
	im->im_off = off;
	im->im_refp = NULL;
	if (name == NULL) {
		im->im_flags = IMF_ANON;
	} else {
		size_t n;

		n = strlcpy(im->im_name, name, ITNAME_MAX);
		if (n > ITNAME_MAX)
			warnx("name %s too long %zd > %d", name, n,
			    ITNAME_MAX);
		im->im_flags = 0;
	}

	return im;
}

const char *
im_name(struct imember *im)
{
	if (!(im->im_flags & IMF_ANON))
		return im->im_name;

	return NULL;
}

void
cu_stat(void)
{
#ifndef NOPOOL
	pool_dump();
#endif
}

/*
 * Iterate over all types found in a given CU.  For all non-resolved types
 * use their DWARF relative offset to find the relative type they are pointing
 * to.  The CU offset tree, `cuot', is used to speedup relative type lookup.
 */
void
cu_resolve(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
{
	struct itype	*it, *ref, tmp;
	struct imember	*im;
	unsigned int	 toresolve;
	size_t		 off = dcu->dcu_offset;

	TAILQ_FOREACH(it, cutq, it_next) {
		if (!(it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)))
			continue;

		/* If this type references another one, try to find it. */
		if (it->it_flags & ITF_UNRES) {
			tmp.it_off = it->it_ref + off;
			ref = RB_FIND(ioff_tree, cuot, &tmp);
			if (ref != NULL) {
				it->it_refp = ref;
				ir_add(it, ref);
				it->it_flags &= ~ITF_UNRES;
			}
		}

		/* If this type has members, resolve all of them. */
		toresolve = it->it_nelems;
		if ((it->it_flags & ITF_UNRES_MEMB) && toresolve > 0) {
			TAILQ_FOREACH(im, &it->it_members, im_next) {
				tmp.it_off = im->im_ref + off;
				ref = RB_FIND(ioff_tree, cuot, &tmp);
				if (ref != NULL) {
					im->im_refp = ref;
					ir_add(it, ref);
					toresolve--;
				}
			}
			if (toresolve == 0)
				it->it_flags &= ~ITF_UNRES_MEMB;
		}
#if defined(DEBUG)
		if (it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)) {
			printf("0x%zx: %s type=%d unresolved 0x%llx",
			    it->it_off, it_name(it), it->it_type, it->it_ref);
			if (toresolve)
				printf(": %d members", toresolve);
			TAILQ_FOREACH(im, &it->it_members, im_next) {
				if (im->im_refp != NULL)
					continue;
				printf("\n%zu: %s", im->im_ref, im_name(im));
			}
			printf("\n");
		}
#endif /* defined(DEBUG) */
	}

	/* We'll reuse the tree for the next CU, so empty it. */
	RB_FOREACH_SAFE(it, ioff_tree, cuot, ref)
		RB_REMOVE(ioff_tree, cuot, it);
}

void
cu_reference(struct dwcu *dcu, struct itype_queue *cutq)
{
	struct itype *it;

	TAILQ_FOREACH(it, cutq, it_next) {
		if (it->it_flags & (ITF_OBJ|ITF_FUNC))
			it_reference(it);
	}
}

/*
 * Merge type representation from a CU with already known types.
 */
void
cu_merge(struct dwcu *dcu, struct itype_queue *cutq)
{
	struct itype *it, *nit, *prev, *first;
	int diff;

	/* First ``it'' that needs a duplicate check. */
	first = TAILQ_FIRST(cutq);
	if (first == NULL)
		return;

	TAILQ_CONCAT(&itypeq, cutq, it_next);

	/*
	 * First pass: merge types
	 */
	for (it = first; it != NULL; it = nit) {
		nit = TAILQ_NEXT(it, it_next);

		/* Move functions & variable to their own list. */
		if (it->it_flags & (ITF_FUNC|ITF_OBJ)) {
			/*
			 * FIXME: allow static variables with the same name
			 * to be of different type.
			 */
			if (RB_FIND(isymb_tree, &isymbt, it) == NULL)
				RB_INSERT(isymb_tree, &isymbt, it);
			continue;
		}

		/* Look if we already have this type. */
		if (it->it_flags & ITF_USED)
			prev = RB_FIND(itype_tree, &itypet[it->it_type], it);
		else
			prev = NULL;

		if (prev != NULL) {
			struct itype *old = it;
			struct itref *ir;
			struct imember *im;

			/* Substitute references */
			while ((ir = SIMPLEQ_FIRST(&old->it_refs)) != NULL) {
				it = ir->ir_itp;

				SIMPLEQ_REMOVE_HEAD(&old->it_refs, ir_next);
				pfree(&ir_pool, ir);

				if (it->it_refp == old)
					it->it_refp = prev;

				TAILQ_FOREACH(im, &it->it_members, im_next) {
					if (im->im_refp == old)
						im->im_refp = prev;
				}
			}

			/* If we first got a forward reference, complete it. */
			if ((prev->it_flags & ITF_FORWARD) &&
			    (old->it_flags & ITF_FORWARD) == 0)
			    	it_merge(prev, old);

			old->it_flags &= ~ITF_USED;
		} else if (it->it_flags & ITF_USED) {
			RB_INSERT(itype_tree, &itypet[it->it_type], it);
		}
	}

	/*
	 * Second pass: update indexes
	 */
	diff = 0;
	for (it = first; it != NULL; it = nit) {
		nit = TAILQ_NEXT(it, it_next);

		if (it->it_flags & (ITF_FUNC|ITF_OBJ))
			continue;

		/* Adjust indexes */
		if (it->it_flags & ITF_USED) {
			it->it_idx -= diff;
			continue;
		}

		/* Remove unused */
		TAILQ_REMOVE(&itypeq, it, it_next);
		it_free(it);
		diff++;
	}

	/* Update global index to match removed entries. */
	it = TAILQ_LAST(&itypeq, itype_queue);
	while (it->it_flags & (ITF_FUNC|ITF_OBJ))
		it = TAILQ_PREV(it, itype_queue, it_next);

	tidx = it->it_idx;
}

/*
 * Parse a CU.
 */
void
cu_parse(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
{
	struct itype *it = NULL;
	struct dwdie *die;
	size_t psz = dcu->dcu_psize;
	size_t off = dcu->dcu_offset;

	assert(RB_EMPTY(cuot));

	SIMPLEQ_FOREACH(die, &dcu->dcu_dies, die_next) {
		uint64_t tag = die->die_dab->dab_tag;

		switch (tag) {
		case DW_TAG_array_type:
			it = parse_array(die, dcu->dcu_psize);
			break;
		case DW_TAG_enumeration_type:
			it = parse_enum(die, dcu->dcu_psize);
			break;
		case DW_TAG_pointer_type:
			it = parse_refers(die, psz, CTF_K_POINTER);
			break;
		case DW_TAG_structure_type:
			it = parse_struct(die, psz, CTF_K_STRUCT, off);
			if (it == NULL)
				continue;
			break;
		case DW_TAG_typedef:
			it = parse_refers(die, psz, CTF_K_TYPEDEF);
			break;
		case DW_TAG_union_type:
			it = parse_struct(die, psz, CTF_K_UNION, off);
			if (it == NULL)
				continue;
			break;
		case DW_TAG_base_type:
			it = parse_base(die, psz);
			if (it == NULL)
				continue;
			break;
		case DW_TAG_const_type:
			it = parse_refers(die, psz, CTF_K_CONST);
			break;
		case DW_TAG_volatile_type:
			it = parse_refers(die, psz, CTF_K_VOLATILE);
			break;
		case DW_TAG_restrict_type:
			it = parse_refers(die, psz, CTF_K_RESTRICT);
			break;
		case DW_TAG_subprogram:
			it = parse_function(die, psz);
			if (it == NULL)
				continue;
			break;
		case DW_TAG_subroutine_type:
			it = parse_funcptr(die, psz);
			break;
		/*
		 * Children are assumed to be right after their parent in
		 * the list.  The parent parsing function takes care of
		 * parsing them.
		 */
		 case DW_TAG_member:
			 assert(it->it_type == CTF_K_STRUCT ||
			    it->it_type == CTF_K_UNION ||
			    it->it_type == CTF_K_ENUM);
			continue;
		 case DW_TAG_subrange_type:
			assert(it->it_type == CTF_K_ARRAY);
			continue;
		case DW_TAG_formal_parameter:
			/*
			 * If we skipped the second inline definition,
			 * skip its arguments.
			 */
			if (it == NULL)
				continue;

			/* See comment in subparse_arguments(). */
			if (it->it_type == CTF_K_STRUCT ||
			    it->it_type == CTF_K_UNION ||
			    it->it_type == CTF_K_ENUM ||
			    it->it_type == CTF_K_TYPEDEF)
				continue;

			if (it->it_flags & ITF_OBJ)
				continue;

			assert(it->it_type == CTF_K_FUNCTION);
			continue;
		case DW_TAG_variable:
			it = parse_variable(die, psz);
			/* Unnamed variables are discarded. */
			if (it == NULL)
				continue;
			break;
#if 1
		case DW_TAG_lexical_block:
		case DW_TAG_inlined_subroutine:
			continue;
#endif
		case DW_TAG_compile_unit:
		default:
			DPRINTF("%s\n", dw_tag2name(tag));
			continue;
		}

		TAILQ_INSERT_TAIL(cutq, it, it_next);
		RB_INSERT(ioff_tree, cuot, it);
	}
}

struct itype *
parse_base(struct dwdie *die, size_t psz)
{
	struct itype *it;
	struct dwaval *dav;
	uint16_t encoding, enc = 0, bits = 0;
	int type;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_encoding:
			enc = dav2val(dav, psz);
			break;
		case DW_AT_byte_size:
			bits = 8 * dav2val(dav, psz);
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}

	switch (enc) {
	case DW_ATE_unsigned:
	case DW_ATE_address:
		encoding = 0;
		type = CTF_K_INTEGER;
		break;
	case DW_ATE_unsigned_char:
		encoding = CTF_INT_CHAR;
		type = CTF_K_INTEGER;
		break;
	case DW_ATE_signed:
		encoding = CTF_INT_SIGNED;
		type = CTF_K_INTEGER;
		break;
	case DW_ATE_signed_char:
		encoding = CTF_INT_SIGNED | CTF_INT_CHAR;
		type = CTF_K_INTEGER;
		break;
	case DW_ATE_boolean:
		encoding = CTF_INT_SIGNED | CTF_INT_BOOL;
		type = CTF_K_INTEGER;
		break;
	case DW_ATE_float:
		if (bits < psz)
			encoding = CTF_FP_SINGLE;
		else if (bits == psz)
			encoding = CTF_FP_DOUBLE;
		else
			encoding = CTF_FP_LDOUBLE;
		type = CTF_K_FLOAT;
		break;
	case DW_ATE_complex_float:
		if (bits < psz)
			encoding = CTF_FP_CPLX;
		else if (bits == psz)
			encoding = CTF_FP_DCPLX;
		else
			encoding = CTF_FP_LDCPLX;
		type = CTF_K_FLOAT;
		break;
	case DW_ATE_imaginary_float:
		if (bits < psz)
			encoding = CTF_FP_IMAGRY;
		else if (bits == psz)
			encoding = CTF_FP_DIMAGRY;
		else
			encoding = CTF_FP_LDIMAGRY;
		type = CTF_K_FLOAT;
		break;
	default:
		DPRINTF("unknown encoding: %d\n", enc);
		return (NULL);
	}

	it = it_new(++tidx, die->die_offset, enc2name(enc), bits,
	    encoding, 0, type, 0);

	return it;
}

struct itype *
parse_refers(struct dwdie *die, size_t psz, int type)
{
	struct itype *it;
	struct dwaval *dav;
	const char *name = NULL;
	size_t ref = 0, size = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_name:
			name = dav2str(dav);
			break;
		case DW_AT_type:
			ref = dav2val(dav, psz);
			break;
		case DW_AT_byte_size:
			size = dav2val(dav, psz);
			assert(size < UINT_MAX);
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}

	it = it_new(++tidx, die->die_offset, name, size, 0, ref, type,
	    ITF_UNRES);

	if (it->it_ref == 0 && (it->it_size == sizeof(void *) ||
	    type == CTF_K_CONST || type == CTF_K_VOLATILE ||
	    type == CTF_K_POINTER || type == CTF_K_TYPEDEF)) {
		/* Work around GCC/clang not emiting a type for void */
		it->it_flags &= ~ITF_UNRES;
		it->it_ref = VOID_OFFSET;
		it->it_refp = void_it;
	}

	return it;
}

struct itype *
parse_array(struct dwdie *die, size_t psz)
{
	struct itype *it;
	struct dwaval *dav;
	const char *name = NULL;
	size_t ref = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_name:
			name = dav2str(dav);
			break;
		case DW_AT_type:
			ref = dav2val(dav, psz);
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}

	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_ARRAY,
	    ITF_UNRES);

	subparse_subrange(die, psz, it);

	return it;
}

struct itype *
parse_enum(struct dwdie *die, size_t psz)
{
	struct itype *it;
	struct dwaval *dav;
	const char *name = NULL;
	size_t size = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_byte_size:
			size = dav2val(dav, psz);
			assert(size < UINT_MAX);
			break;
		case DW_AT_name:
			name = dav2str(dav);
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}

	it = it_new(++tidx, die->die_offset, name, size, 0, 0, CTF_K_ENUM, 0);

	subparse_enumerator(die, psz, it);

	return it;
}

void
subparse_subrange(struct dwdie *die, size_t psz, struct itype *it)
{
	struct dwaval *dav;

	assert(it->it_type == CTF_K_ARRAY);

	if (die->die_dab->dab_children == DW_CHILDREN_no)
		return;

	/*
	 * This loop assumes that the children of a DIE are just
	 * after it on the list.
	 */
	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
		uint64_t tag = die->die_dab->dab_tag;
		size_t nelems = 0;

		if (tag != DW_TAG_subrange_type)
			break;

		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
			switch (dav->dav_dat->dat_attr) {
			case DW_AT_count:
				nelems = dav2val(dav, psz);
				break;
			case DW_AT_upper_bound:
				nelems = dav2val(dav, psz) + 1;
				break;
			default:
				DPRINTF("%s\n",
				    dw_at2name(dav->dav_dat->dat_attr));
				break;
			}
		}

		assert(nelems < UINT_MAX);
		it->it_nelems = nelems;
	}
}

void
subparse_enumerator(struct dwdie *die, size_t psz, struct itype *it)
{
	struct imember *im;
	struct dwaval *dav;

	assert(it->it_type == CTF_K_ENUM);

	if (die->die_dab->dab_children == DW_CHILDREN_no)
		return;

	/*
	 * This loop assumes that the children of a DIE are just
	 * after it on the list.
	 */
	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
		uint64_t tag = die->die_dab->dab_tag;
		size_t val = 0;
		const char *name = NULL;

		if (tag != DW_TAG_enumerator)
			break;

		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
			switch (dav->dav_dat->dat_attr) {
			case DW_AT_name:
				name = dav2str(dav);
				break;
			case DW_AT_const_value:
				val = dav2val(dav, psz);
				break;
			default:
				DPRINTF("%s\n",
				    dw_at2name(dav->dav_dat->dat_attr));
				break;
			}
		}

		if (name == NULL) {
			warnx("%s with anon member", it_name(it));
			continue;
		}

		im = im_new(name, val, 0);
		assert(it->it_nelems < UINT_MAX);
		it->it_nelems++;
		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
	}
}

struct itype *
parse_struct(struct dwdie *die, size_t psz, int type, size_t off)
{
	struct itype *it = NULL;
	struct dwaval *dav;
	const char *name = NULL;
	unsigned int flags = 0;
	size_t size = 0;
	int forward = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_declaration:
			forward = dav2val(dav, psz);
			break;
		case DW_AT_byte_size:
			size = dav2val(dav, psz);
			assert(size < UINT_MAX);
			break;
		case DW_AT_name:
			name = dav2str(dav);
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}


	if (forward)
		flags = ITF_FORWARD;
	it = it_new(++tidx, die->die_offset, name, size, 0, 0, type, flags);
	subparse_member(die, psz, it, off);

	return it;
}

void
subparse_member(struct dwdie *die, size_t psz, struct itype *it, size_t offset)
{
	struct imember *im;
	struct dwaval *dav;
	const char *name;
	size_t off = 0, ref = 0, bits = 0;
	uint8_t lvl = die->die_lvl;

	assert(it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION);

	if (die->die_dab->dab_children == DW_CHILDREN_no)
		return;

	/*
	 * This loop assumes that the children of a DIE are just
	 * after it on the list.
	 */
	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
		int64_t tag = die->die_dab->dab_tag;

		name = NULL;
		if (die->die_lvl <= lvl)
			break;

		/* Skip members of members */
		if (die->die_lvl > lvl + 1)
			continue;
		/*
		 * Nested declaration.
		 *
		 * This matches the case where a ``struct'', ``union'',
		 * ``enum'' or ``typedef'' is first declared "inside" a
		 * union or struct declaration.
		 */
		if (tag == DW_TAG_structure_type || tag == DW_TAG_union_type ||
		    tag == DW_TAG_enumeration_type || tag == DW_TAG_typedef)
			continue;

		it->it_flags |= ITF_UNRES_MEMB;

		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
			switch (dav->dav_dat->dat_attr) {
			case DW_AT_name:
				name = dav2str(dav);
				break;
			case DW_AT_type:
				ref = dav2val(dav, psz);
				break;
			case DW_AT_data_member_location:
				off = 8 * dav2val(dav, psz);
				break;
			case DW_AT_bit_size:
				bits = dav2val(dav, psz);
				assert(bits < USHRT_MAX);
				break;
			default:
				DPRINTF("%s\n",
				    dw_at2name(dav->dav_dat->dat_attr));
				break;
			}
		}

		/*
		 * When a structure is declared inside an union, we
		 * have to generate a reference to make the resolver
		 * happy.
		 */
		if ((ref == 0) && (tag == DW_TAG_structure_type))
			ref = die->die_offset - offset;

		im = im_new(name, ref, off);
		assert(it->it_nelems < UINT_MAX);
		it->it_nelems++;
		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
	}
}


void
subparse_arguments(struct dwdie *die, size_t psz, struct itype *it)
{
	struct imember *im;
	struct dwaval *dav;
	size_t ref = 0;

	assert(it->it_type == CTF_K_FUNCTION);

	if (die->die_dab->dab_children == DW_CHILDREN_no)
		return;

	/*
	 * This loop assumes that the children of a DIE are after it
	 * on the list.
	 */
	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
		uint64_t tag = die->die_dab->dab_tag;

		if (tag == DW_TAG_unspecified_parameters) {
			/* TODO */
			continue;
		}

		/*
		 * Nested declaration.
		 *
		 * This matches the case where a ``struct'', ``union'',
		 * ``enum'', ``typedef'' or ``static'' variable is first
		 * declared inside a function declaration.
		 */
		switch (tag) {
		case DW_TAG_structure_type:
		case DW_TAG_union_type:
		case DW_TAG_enumeration_type:
		case DW_TAG_typedef:
		case DW_TAG_variable:
			continue;
		default:
			break;
		}

		if (tag != DW_TAG_formal_parameter)
			break;

		it->it_flags |= ITF_UNRES_MEMB;

		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
			switch (dav->dav_dat->dat_attr) {
			case DW_AT_type:
				ref = dav2val(dav, psz);
				break;
			default:
				DPRINTF("%s\n",
				    dw_at2name(dav->dav_dat->dat_attr));
				break;
			}
		}

		im = im_new(NULL, ref, 0);
		assert(it->it_nelems < UINT_MAX);
		it->it_nelems++;
		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
	}
}

struct itype *
parse_function(struct dwdie *die, size_t psz)
{
	struct itype *it;
	struct dwaval *dav;
	const char *name = NULL;
	size_t ref = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_name:
			name = dav2str(dav);
			break;
		case DW_AT_type:
			ref = dav2val(dav, psz);
			break;
		case DW_AT_abstract_origin:
			/*
			 * Skip second empty definition for inline
			 * functions.
			 */
			return NULL;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}

	/*
	 * Work around for clang 4.0 generating DW_TAG_subprogram without
	 * any attribute.
	 */
	if (name == NULL)
		return NULL;

	it = it_new(++fidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
	    ITF_UNRES|ITF_FUNC);

	subparse_arguments(die, psz, it);

	if (it->it_ref == 0) {
		/* Work around GCC not emiting a type for void */
		it->it_flags &= ~ITF_UNRES;
		it->it_ref = VOID_OFFSET;
		it->it_refp = void_it;
	}

	return it;
}

struct itype *
parse_funcptr(struct dwdie *die, size_t psz)
{
	struct itype *it;
	struct dwaval *dav;
	const char *name = NULL;
	size_t ref = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_name:
			name = dav2str(dav);
			break;
		case DW_AT_type:
			ref = dav2val(dav, psz);
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}

	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
	    ITF_UNRES);

	subparse_arguments(die, psz, it);

	if (it->it_ref == 0) {
		/* Work around GCC not emiting a type for void */
		it->it_flags &= ~ITF_UNRES;
		it->it_ref = VOID_OFFSET;
		it->it_refp = void_it;
	}

	return it;
}

struct itype *
parse_variable(struct dwdie *die, size_t psz)
{
	struct itype *it = NULL;
	struct dwaval *dav;
	const char *name = NULL;
	size_t ref = 0;
	int forward = 0, global = 0;

	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
		switch (dav->dav_dat->dat_attr) {
		case DW_AT_declaration:
			forward = dav2val(dav, psz);
			break;
		case DW_AT_name:
			name = dav2str(dav);
			break;
		case DW_AT_type:
			ref = dav2val(dav, psz);
			break;
		case DW_AT_location:
			switch (dav->dav_dat->dat_form) {
			case DW_FORM_block:
			case DW_FORM_block1:
			case DW_FORM_block2:
			case DW_FORM_block4:
				global = 1;
				break;
			default:
				break;
			}
			break;
		default:
			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
			break;
		}
	}


	if (global && !forward && name != NULL) {
		it = it_new(++oidx, die->die_offset, name, 0, 0, ref, 0,
		    ITF_UNRES|ITF_OBJ);
	}

	return it;
}

size_t
dav2val(struct dwaval *dav, size_t psz)
{
	uint64_t val = (uint64_t)-1;

	switch (dav->dav_dat->dat_form) {
	case DW_FORM_addr:
	case DW_FORM_ref_addr:
		if (psz == sizeof(uint32_t))
			val = dav->dav_u32;
		else
			val = dav->dav_u64;
		break;
	case DW_FORM_block1:
	case DW_FORM_block2:
	case DW_FORM_block4:
	case DW_FORM_block:
		dw_loc_parse(&dav->dav_buf, NULL, &val, NULL);
		break;
	case DW_FORM_flag:
	case DW_FORM_data1:
	case DW_FORM_ref1:
		val = dav->dav_u8;
		break;
	case DW_FORM_data2:
	case DW_FORM_ref2:
		val = dav->dav_u16;
		break;
	case DW_FORM_data4:
	case DW_FORM_ref4:
		val = dav->dav_u32;
		break;
	case DW_FORM_sdata:
	case DW_FORM_data8:
	case DW_FORM_ref8:
	case DW_FORM_udata:
	case DW_FORM_ref_udata:
		val = dav->dav_u64;
		break;
	case DW_FORM_strp:
		val = dav->dav_u32;
		break;
	case DW_FORM_flag_present:
		val = 1;
		break;
	default:
		break;
	}

	return val;
}

const char *
dav2str(struct dwaval *dav)
{
	const char *str = NULL;
	extern const char *dstrbuf;
	extern size_t dstrlen;

	switch (dav->dav_dat->dat_form) {
	case DW_FORM_string:
		str = dav->dav_str;
		break;
	case DW_FORM_strp:
		if (dav->dav_u32 >= dstrlen)
			str = NULL;
		else
			str = dstrbuf + dav->dav_u32;
		break;
	default:
		break;
	}

	return str;
}

const char *
enc2name(unsigned short enc)
{
	static const char *enc_name[] = { "address", "boolean", "complex float",
	    "float", "signed", "char", "unsigned", "unsigned char",
	    "imaginary float", "packed decimal", "numeric string", "edited",
	    "signed fixed", "unsigned fixed", "decimal float" };

	if (enc > 0 && enc <= nitems(enc_name))
		return enc_name[enc - 1];

	return "invalid";
}