/*-
 * Copyright (c) 2015--2018 Taylor R. Campbell
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * Compilation process:
 *
 * - Collect enumerations and report duplicate ones and enumerands.
 * - Collect message definitions and report duplicate ones and fields.
 * - Collect field types and report missing ones.
 * - Topologically sort message definitions and report cycles.
 * - Generate structure definitions.
 *
 * XXX Missing:
 *
 * - Extensions.
 * - Services.
 * - Imports.
 * - Packages.
 * - Options, including reporting unrecognized/unused options.
 *
 * XXX Any reason not to do the detection of duplicates at parse time?
 */

#include <assert.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "ast.h"
#include "emalloc.h"
#include "eprintf.h"
#include "format.h"
#include "queue.h"
#include "rbtree.h"
#include "scc.h"
#include "strung.h"
#include "syntax.h"

#define	PICOPBC_PROPLIB 1

#ifdef PICOPBC_PROPLIB
#define	PICOPBC_PROPLIB_OPTION_NAME	"(picopb).proplib.name"
#define	PICOPBC_PROPLIB_OPTION_VALUE	"(picopb).proplib.value"
#endif

static const uint32_t abi_version = 0x00000000; /* 0.0 */

/* Builtin types */

enum builtin_type {
	/* Keep these sorted so we can binary search on builtin_type_names.  */
	BUILTIN_TYPE_BOOL,
	BUILTIN_TYPE_BYTES,
	BUILTIN_TYPE_DOUBLE,
	BUILTIN_TYPE_FIXED32,
	BUILTIN_TYPE_FIXED64,
	BUILTIN_TYPE_FLOAT,
	BUILTIN_TYPE_INT32,
	BUILTIN_TYPE_INT64,
	BUILTIN_TYPE_SFIXED32,
	BUILTIN_TYPE_SFIXED64,
	BUILTIN_TYPE_SINT32,
	BUILTIN_TYPE_SINT64,
	BUILTIN_TYPE_STRING,
	BUILTIN_TYPE_UINT32,
	BUILTIN_TYPE_UINT64,
};

static const char *const builtin_type_names[] = {
	/*
	 * Order as listed in the protocol buffers documentation at
	 * <https://developers.google.com/protocol-buffers/docs/proto>.
	 */
	[BUILTIN_TYPE_DOUBLE] = "double",
	[BUILTIN_TYPE_FLOAT] = "float",
	[BUILTIN_TYPE_INT32] = "int32",
	[BUILTIN_TYPE_INT64] = "int64",
	[BUILTIN_TYPE_UINT32] = "uint32",
	[BUILTIN_TYPE_UINT64] = "uint64",
	[BUILTIN_TYPE_SINT32] = "sint32",
	[BUILTIN_TYPE_SINT64] = "sint64",
	[BUILTIN_TYPE_FIXED32] = "fixed32",
	[BUILTIN_TYPE_FIXED64] = "fixed64",
	[BUILTIN_TYPE_SFIXED32] = "sfixed32",
	[BUILTIN_TYPE_SFIXED64] = "sfixed64",
	[BUILTIN_TYPE_BOOL] = "bool",
	[BUILTIN_TYPE_STRING] = "string",
	[BUILTIN_TYPE_BYTES] = "bytes",
};

static const size_t nbuiltin_types =
    sizeof(builtin_type_names)/sizeof(builtin_type_names[0]);

static int
bsearch_strcmp(const void *va, const void *vb)
{
	const char *const *const a = va;
	const char *const *const b = vb;

	return strcmp(*a, *b);
}

static bool
find_builtin_type(struct string name, enum builtin_type *typep)
{
	const char *const namep = string_ptr(name);
	const char *const *nameloc;

	assert(strnlen(string_ptr(name), string_len(name) + 1) ==
	    string_len(name));
	nameloc = bsearch(&namep, builtin_type_names, nbuiltin_types,
	    sizeof(builtin_type_names[0]), bsearch_strcmp);
	if (nameloc == NULL)
		return false;
	assert(strncmp(string_ptr(name), *nameloc, string_len(name) + 1) == 0);
	assert(builtin_type_names <= nameloc);
	assert((size_t)(nameloc - builtin_type_names) < nbuiltin_types);
	if (typep)
		*typep = nameloc - builtin_type_names;
	return true;
}

/* Compiler */

struct def {
	struct ast_srcloc	def_loc;
	struct string		def_id;
	struct string		def_qname;
	rb_node_t		def_rb_node;
	struct scc_vertex	def_scc;
	SIMPLEQ_ENTRY(def)	def_entry;
	SIMPLEQ_ENTRY(def)	def_encentry;
	size_t			def_maxdepth;
	union {
		struct enumeration	*enumeration;
		struct message		*message;
	}		def_u;
	enum {
		DEF_ENUM,
		DEF_MSG,
	}		def_t;
	bool			def_cyclic_storage;
};
SIMPLEQ_HEAD(defq, def);
SIMPLEQ_HEAD(deflist, def);

struct dep {
	/*
	 * rb_node_t must come first to work around a bug in rbtree,
	 * specifically in rb_tree_find_node_geq/leq.
	 */
	rb_node_t			dep_rb_node;
	struct def			*dep_user;
	struct field			*dep_field;
	struct def			*dep_def;
};

struct message {
	struct ast_message		*msg_ast;
	rb_tree_t			msg_fields_by_name;
	rb_tree_t			msg_fields_by_tag;

#ifdef PICOPBC_PROPLIB
	rb_tree_t			msg_fields_by_proplib;
#endif	/* PICOPBC_PROPLIB */
};

struct field {
	struct ast_field		*field_ast;
	rb_node_t			field_by_name_rb_node;
	rb_node_t			field_by_tag_rb_node;
	union {
		enum builtin_type		builtin;
		struct def			*defined;
	}				field_type_u;
	enum {
		FIELD_TYPE_BUILTIN,
		FIELD_TYPE_DEFINED,
		FIELD_TYPE_UNKNOWN,
	}				field_type_t;

#ifdef PICOPBC_PROPLIB
	struct string			field_proplib;
	rb_node_t			field_by_proplib_rb_node;
	uint32_t			field_index;
#endif	/* PICOPBC_PROPLIB */
};

struct enumeration {
	struct ast_enumeration		*enum_ast;
	rb_tree_t			enum_by_name;
	rb_tree_t			enum_by_value;

#ifdef PICOPBC_PROPLIB
	rb_tree_t			enum_by_proplib;
#endif	/* PICOPBC_PROPLIB */
};

struct enumerand {
	struct ast_enumerand		*enumerand_ast;
	rb_node_t			enumerand_by_name_rb_node;
	rb_node_t			enumerand_by_value_rb_node;

#ifdef PICOPBC_PROPLIB
	struct string			enumerand_proplib;
	rb_node_t			enumerand_by_proplib_rb_node;
#endif	/* PICOPBC_PROPLIB */
};

static void	collect_defs(rb_tree_t *, struct ast_proto *, int *);
static void	collect_defs_msg(rb_tree_t *, struct ast_message *,
		    const struct string *, int *);
static void	collect_defs_enum(rb_tree_t *, struct ast_enumeration *,
		    const struct string *, int *);
static bool	collect_def(rb_tree_t *, struct def *, const struct string *,
		    int *);

static struct def *
		find_def(rb_tree_t *, struct string, const struct string *);

static void	collect_deps(rb_tree_t *, rb_tree_t *, struct ast_proto *,
		    int *);
static void	collect_deps_msg(rb_tree_t *, rb_tree_t *,
		    struct ast_message *, const struct string *, int *);
static void	collect_deps_field(rb_tree_t *, rb_tree_t *,
		    struct ast_field *, struct def *, const struct string *,
		    int *);
static void	collect_deps_enum(rb_tree_t *, rb_tree_t *,
		    struct ast_enumeration *, const struct string *, int *);
static void	collect_deps_enumerand(struct ast_enumerand *, struct def *,
		    int *);

static void	topsort_defs(struct defq *, rb_tree_t *, rb_tree_t *, int *);

static void	generate_code(FILE *, struct string, FILE *, struct string,
		    rb_tree_t *, struct defq *, const struct picopbc_formats *,
		    int);
static void	generate_h(FILE *, struct string, rb_tree_t *, struct defq *,
		    const struct picopbc_formats *);
static void	generate_c(FILE *, struct string, rb_tree_t *, struct defq *,
		    const struct picopbc_formats *, int);
static void	generate_enum_h(FILE *, struct def *);
static void	generate_msg_h(FILE *, rb_tree_t *, struct def *);
static void	generate_field_h(FILE *, rb_tree_t *, struct ast_field *,
		    const struct string *);
static void	generate_msg_c(FILE *, rb_tree_t *, struct def *,
		    const struct picopbc_formats *);
static void	generate_field_c(FILE *, rb_tree_t *, const char *,
		    struct ast_field *, const struct string *);
static void	generate_enum_c(FILE *, struct def *, int);

#ifdef PICOPBC_PROPLIB
static void	generate_proplib_c(FILE *, rb_tree_t *, struct defq *, int);
static void	generate_proplib_msg_c(FILE *, rb_tree_t *, struct def *);
static void	generate_proplib_array_c(FILE *, rb_tree_t *, struct def *,
		    struct message *, const char *);
static void	generate_proplib_field_c(FILE *, struct field *,
		    struct message *, const char *, const char *);
static void	generate_proplib_enum_c(FILE *, struct def *, int);

static struct string	optname_estring(const struct ast_optname *);
static int	optname_ref_order(const struct ast_optname *, const char *);
static bool	optname_ref_equal(const struct ast_optname *, const char *);
static struct ast_option *
		find_option_1(struct ast_option *, size_t, const char *);

static void	efprint_cstring(FILE *, struct string);
#endif	/* PICOPBC_PROPLIB */

static unsigned	efprintloc(FILE *, struct ast_srcloc);
static unsigned	efprintdef(FILE *, struct def *);
static struct string	eqnamestr_c(struct string);
static char *		eqnamestrp_c(struct string);

#define	RB_TREE_FOREACH_SAFE(N, T, N0)					\
	for ((N) = RB_TREE_MIN(T);					\
	     ((N) != NULL &&						\
		((N0) = rb_tree_iterate((T), (N), RB_DIR_RIGHT), 1));	\
	     (N) = (N0))

int
picopbc_compile(FILE *hout, struct string hguard, FILE *cout,
    struct string hname, struct ast_proto *proto,
    const struct picopbc_formats *formats)
{
	rb_tree_t defs, deps;
	struct defq defq;
	struct dep *dep, *dep0;
	struct def *def, *def0;
	int error = 0;

	/* Analyze the schema.  */
	collect_defs(&defs, proto, &error);
	collect_deps(&deps, &defs, proto, &error);
	SIMPLEQ_INIT(&defq);
	topsort_defs(&defq, &defs, &deps, &error);

	/* Generate output.  */
	generate_code(hout, hguard, cout, hname, &defs, &defq, formats, error);

	/* Free our memory.  */
	RB_TREE_FOREACH_SAFE(dep, &deps, dep0) {
		rb_tree_remove_node(&deps, dep);
		free(dep);
	}
	RB_TREE_FOREACH_SAFE(def, &defs, def0) {
		rb_tree_remove_node(&defs, def);
		switch (def->def_t) {
		case DEF_MSG: {
			struct message *msg = def->def_u.message;
			struct field *field, *field0;
			rb_tree_t *by_name = &msg->msg_fields_by_name;
			rb_tree_t *by_tag = &msg->msg_fields_by_tag;
#ifdef PICOPBC_PROPLIB
			rb_tree_t *by_proplib = &msg->msg_fields_by_proplib;
#endif	/* PICOPBC_PROPLIB */

			RB_TREE_FOREACH_SAFE(field, &msg->msg_fields_by_name,
			    field0) {
				rb_tree_remove_node(by_name, field);
				rb_tree_remove_node(by_tag, field);
#ifdef PICOPBC_PROPLIB
				rb_tree_remove_node(by_proplib, field);
#endif	/* PICOPBC_PROPLIB */
				free(field);
			}
			assert(RB_TREE_MIN(by_name) == NULL);
			assert(RB_TREE_MIN(by_tag) == NULL);
#ifdef PICOPBC_PROPLIB
			assert(RB_TREE_MIN(by_proplib) == NULL);
#endif	/* PICOPBC_PROPLIB */

			free(msg);
			break;
		}
		case DEF_ENUM: {
			struct enumeration *enumeration =
			    def->def_u.enumeration;
			struct enumerand *enumerand, *enumerand0;
			rb_tree_t *by_name = &enumeration->enum_by_name;
			rb_tree_t *by_value = &enumeration->enum_by_value;
#ifdef PICOPBC_PROPLIB
			rb_tree_t *by_proplib = &enumeration->enum_by_proplib;
#endif

			RB_TREE_FOREACH_SAFE(enumerand, by_name, enumerand0) {
				rb_tree_remove_node(by_name, enumerand);
				rb_tree_remove_node(by_value, enumerand);
#ifdef PICOPBC_PROPLIB
				rb_tree_remove_node(by_proplib, enumerand);
#endif
				free(enumerand);
			}
			assert(RB_TREE_MIN(by_name) == NULL);
			assert(RB_TREE_MIN(by_value) == NULL);
#ifdef PICOPBC_PROPLIB
			assert(RB_TREE_MIN(by_proplib) == NULL);
#endif	/* PICOPBC_PROPLIB */

			free(enumeration);
			break;
		}
		}
		string_free(def->def_qname);
		free(def);
	}

	return error;
}

/* Red/black tree comparators */

static int
compare_defs(void *cookie attr_unused, const void *va, const void *vb)
{
	const struct def *const da = va;
	const struct def *const db = vb;

	return string_order(da->def_qname, db->def_qname);
}

static int
compare_def_key(void *cookie attr_unused, const void *vn, const void *vk)
{
	const struct def *const def = vn;
	const struct string *const name = vk;

	return string_order(def->def_qname, *name);
}

static int
compare_deps(void *cookie attr_unused, const void *va, const void *vb)
{
	const struct dep *const da = va;
	const struct dep *const db = vb;
	int order;

	order = string_order(da->dep_user->def_qname, db->dep_user->def_qname);
	if (order != 0)
		return order;

	return string_order(da->dep_def->def_qname, db->dep_def->def_qname);
}

static int
compare_dep_key(void *cookie attr_unused, const void *vn, const void *vk)
{
	const struct dep *const ndep = vn;
	const struct def *const kdef = vk;
	int order;

	order = string_order(ndep->dep_user->def_qname, kdef->def_qname);
	if (order != 0)
		return order;

	/* Key is always less than all deps.  */
	return +1;
}

static const rb_tree_ops_t def_rb_ops = {
	.rbto_compare_nodes = &compare_defs,
	.rbto_compare_key = &compare_def_key,
	.rbto_node_offset = offsetof(struct def, def_rb_node),
};

static const rb_tree_ops_t dep_rb_ops = {
	.rbto_compare_nodes = &compare_deps,
	.rbto_compare_key = &compare_dep_key,
	.rbto_node_offset = offsetof(struct dep, dep_rb_node),
};

static int
compare_fields_by_name(void *cookie attr_unused, const void *va,
    const void *vb)
{
	const struct field *const fa = va;
	const struct field *const fb = vb;

	return string_order(fa->field_ast->id, fb->field_ast->id);
}

#define	ORDER_NUM(A, B)	((A) < (B)? -1 : (A) > (B)? +1 : 0)

static int
compare_fields_by_tag(void *cookie attr_unused, const void *va, const void *vb)
{
	const struct field *const fa = va;
	const struct field *const fb = vb;

	return ORDER_NUM(fa->field_ast->tag, fb->field_ast->tag);
}

#ifdef PICOPBC_PROPLIB
static int
compare_fields_by_proplib(void *cookie attr_unused, const void *va,
    const void *vb)
{
	const struct field *const fa = va;
	const struct field *const fb = vb;

	return string_order(fa->field_proplib, fb->field_proplib);
}
#endif	/* PICOPBC_PROPLIB */

static int
compare_enumerands_by_name(void *cookie attr_unused, const void *va,
    const void *vb)
{
	const struct enumerand *const ea = va;
	const struct enumerand *const eb = vb;

	return string_order(ea->enumerand_ast->id, eb->enumerand_ast->id);
}

static int
compare_enumerands_by_value(void *cookie attr_unused, const void *va,
    const void *vb)
{
	const struct enumerand *const ea = va;
	const struct enumerand *const eb = vb;

	return ORDER_NUM(ea->enumerand_ast->value, eb->enumerand_ast->value);
}

#ifdef PICOPBC_PROPLIB
static int
compare_enumerands_by_proplib(void *cookie attr_unused, const void *va,
    const void *vb)
{
	const struct enumerand *const ea = va;
	const struct enumerand *const eb = vb;

	return string_order(ea->enumerand_proplib, eb->enumerand_proplib);
}
#endif	/* PICOPBC_PROPLIB */

static const rb_tree_ops_t field_by_name_rb_ops = {
	.rbto_compare_nodes = &compare_fields_by_name,
	.rbto_node_offset = offsetof(struct field, field_by_name_rb_node),
};

static const rb_tree_ops_t field_by_tag_rb_ops = {
	.rbto_compare_nodes = &compare_fields_by_tag,
	.rbto_node_offset = offsetof(struct field, field_by_tag_rb_node),
};

#ifdef PICOPBC_PROPLIB
static const rb_tree_ops_t field_by_proplib_rb_ops = {
	.rbto_compare_nodes = &compare_fields_by_proplib,
	.rbto_node_offset = offsetof(struct field, field_by_proplib_rb_node),
};
#endif	/* PICOPBC_PROPLIB */

static const rb_tree_ops_t enumerand_by_name_rb_ops = {
	.rbto_compare_nodes = &compare_enumerands_by_name,
	.rbto_node_offset =
	    offsetof(struct enumerand, enumerand_by_name_rb_node),
};

static const rb_tree_ops_t enumerand_by_value_rb_ops = {
	.rbto_compare_nodes = &compare_enumerands_by_value,
	.rbto_node_offset =
	    offsetof(struct enumerand, enumerand_by_value_rb_node),
};

#ifdef PICOPBC_PROPLIB
static const rb_tree_ops_t enumerand_by_proplib_rb_ops = {
	.rbto_compare_nodes = &compare_enumerands_by_proplib,
	.rbto_node_offset =
	    offsetof(struct enumerand, enumerand_by_proplib_rb_node),
};
#endif	/* PICOPBC_PROPLIB */

/* Collect type definitions */

static void
collect_defs(rb_tree_t *defs, struct ast_proto *proto, int *errorp)
{
	struct ast_proto_stmt *stmts = proto->stmts.stmts;
	size_t i, nstmts = proto->stmts.nstmts;

	rb_tree_init(defs, &def_rb_ops);

	for (i = 0; i < nstmts; i++) {
		switch (stmts[i].t) {
		case AST_PROTO_STMT_NULL:
			assert(!"spurious null proto statement");
			break;
		case AST_PROTO_STMT_MESSAGE:
			collect_defs_msg(defs, &stmts[i].u.message, NULL,
			    errorp);
			break;
		case AST_PROTO_STMT_ENUMERATION:
			collect_defs_enum(defs, &stmts[i].u.enumeration, NULL,
			    errorp);
			break;
		case AST_PROTO_STMT_SERVICE:
		case AST_PROTO_STMT_EXTEND:
		case AST_PROTO_STMT_IMPORT:
		case AST_PROTO_STMT_PACKAGE:
		case AST_PROTO_STMT_OPTION:
			break;
		default:
			assert(!"invalid proto statement");
			break;
		}
	}
}

static void
collect_defs_msg(rb_tree_t *defs, struct ast_message *msg_ast,
    const struct string *ns, int *errorp)
{
	struct message *msg;
	struct def *def;
	struct ast_message_stmt *stmts = msg_ast->stmts.stmts;
	size_t i, nstmts = msg_ast->stmts.nstmts;

	/* Create a message record.  */
	msg = emalloc(sizeof(*msg));
	msg->msg_ast = msg_ast;
	rb_tree_init(&msg->msg_fields_by_name, &field_by_name_rb_ops);
	rb_tree_init(&msg->msg_fields_by_tag, &field_by_tag_rb_ops);
#ifdef PICOPBC_PROPLIB
	rb_tree_init(&msg->msg_fields_by_proplib, &field_by_proplib_rb_ops);
#endif

	/* Create a definition record.  */
	def = emalloc(sizeof(*def));
	def->def_loc = msg_ast->loc;
	def->def_id = msg_ast->id;
	def->def_t = DEF_MSG;
	def->def_u.message = msg;

	/* Record the definition, or fail if this is a duplicate.  */
	if (!collect_def(defs, def, ns, errorp))
		return;

	/* Recursively collect the subdefinitions.  */
	ns = &def->def_qname;
	for (i = 0; i < nstmts; i++) {
		switch (stmts[i].t) {
		case AST_MESSAGE_STMT_NULL:
			assert(!"spurious null message statement");
			break;
		case AST_MESSAGE_STMT_MESSAGE:
			collect_defs_msg(defs, &stmts[i].u.message, ns,
			    errorp);
			break;
		case AST_MESSAGE_STMT_ENUMERATION:
			collect_defs_enum(defs, &stmts[i].u.enumeration, ns,
			    errorp);
			break;
		case AST_MESSAGE_STMT_EXTEND:
		case AST_MESSAGE_STMT_OPTION:
		case AST_MESSAGE_STMT_EXTENSIONS:
		case AST_MESSAGE_STMT_FIELD:
			break;
		default:
			assert(!"invalid message statement");
			break;
		}
	}
}

static void
collect_defs_enum(rb_tree_t *defs, struct ast_enumeration *enum_ast,
    const struct string *ns, int *errorp)
{
	struct enumeration *enumeration;
	struct def *def;
	struct ast_enum_stmt *stmts = enum_ast->stmts.stmts;
	size_t i, nstmts = enum_ast->stmts.nstmts;
	size_t nenumerands;

	/* Create an enumeration record.  */
	enumeration = emalloc(sizeof(*enumeration));
	enumeration->enum_ast = enum_ast;
	rb_tree_init(&enumeration->enum_by_name, &enumerand_by_name_rb_ops);
	rb_tree_init(&enumeration->enum_by_value, &enumerand_by_value_rb_ops);
#ifdef PICOPBC_PROPLIB
	rb_tree_init(&enumeration->enum_by_proplib,
	    &enumerand_by_proplib_rb_ops);
#endif	/* PICOPBC_PROPLIB */

	/* Create a definition record.  */
	def = emalloc(sizeof(*def));
	def->def_loc = enum_ast->loc;
	def->def_id = enum_ast->id;
	def->def_t = DEF_ENUM;
	def->def_u.enumeration = enumeration;

	/* Collect the definition, or fail if this is a duplicate.  */
	if (!collect_def(defs, def, ns, errorp))
		return;

	/* Count the enumerands to make sure we have at least one.  */
	nenumerands = 0;
	for (i = 0; i < nstmts; i++) {
		if (stmts[i].t != AST_ENUM_STMT_ENUMERAND)
			continue;
		assert(nenumerands < SIZE_MAX);
		nenumerands++;
	}
	if (nenumerands == 0) {
		char *v = string_evisciiz(def->def_qname);
		efprintloc(stderr, def->def_loc);
		efprintf(stderr, ": enumeration %s has no enumerands\n", v);
		free(v);
		*errorp = 1;
	}
}

static bool
collect_def(rb_tree_t *defs, struct def *def, const struct string *ns,
    int *errorp)
{
	const struct string dot = STRING_CONST(".");
	enum builtin_type type;
	struct def *def0;

	/*
	 * Qualified name is just the id, if we're at the top level; or
	 * the namespace dot the id, if not.
	 */
	if (ns == NULL)
		def->def_qname = string_ecopy(def->def_id);
	else
		def->def_qname = string_econcatn(ns, &dot, &def->def_id, NULL);

	/* Make sure nobody's trying to redefine a builtin type.  */
	/* XXX Can we do this in the parser?  */
	if (find_builtin_type(def->def_id, &type)) {
		char *v = string_evisciiz(def->def_qname);
		efprintloc(stderr, def->def_loc);
		efprintf(stderr, ": redefinition of builtin type %s as ", v);
		efprintdef(stderr, def);
		efprintf(stderr, "\n");
		free(v);
		goto fail;
	}

	/* Make sure nobody's trying to redefine their own type.  */
	def0 = rb_tree_insert_node(defs, def);
	if (def0 != def) {
		efprintloc(stderr, def->def_loc);
		efprintf(stderr, ": redefinition of type ");
		efprintdef(stderr, def);
		efprintf(stderr, "\n");
		efprintloc(stderr, def0->def_loc);
		efprintf(stderr, ": first defined here as ");
		efprintdef(stderr, def0);
		efprintf(stderr, "\n");
		goto fail;
	}

	return true;

fail:	string_free(def->def_qname);
	free(def);
	*errorp = 1;
	return false;
}

/* Collect and verify type dependencies */

static void
collect_deps(rb_tree_t *deps, rb_tree_t *defs, struct ast_proto *proto,
    int *errorp)
{
	struct ast_proto_stmt *stmts = proto->stmts.stmts;
	size_t i, nstmts = proto->stmts.nstmts;

	rb_tree_init(deps, &dep_rb_ops);

	for (i = 0; i < nstmts; i++) {
		switch (stmts[i].t) {
		case AST_PROTO_STMT_NULL:
			assert(!"spurious null proto statement");
			break;
		case AST_PROTO_STMT_MESSAGE:
			collect_deps_msg(deps, defs, &stmts[i].u.message,
			    NULL, errorp);
			break;
		case AST_PROTO_STMT_ENUMERATION:
			collect_deps_enum(deps, defs, &stmts[i].u.enumeration,
			    NULL, errorp);
			break;
		case AST_PROTO_STMT_SERVICE:
		case AST_PROTO_STMT_EXTEND:
		case AST_PROTO_STMT_IMPORT:
		case AST_PROTO_STMT_PACKAGE:
		case AST_PROTO_STMT_OPTION:
			break;
		default:
			assert(!"invalid proto statement");
			break;
		}
	}
}

static struct def *
find_def(rb_tree_t *defs, struct string name, const struct string *ns)
{
	const struct string dot = STRING_CONST(".");
	struct string prefix, qname;
	size_t end;
	struct def *def;

	assert(0 < string_len(name));

	/* If it starts with a dot, it is fully-qualified top-level.  */
	if (string_ptr(name)[0] == '.') {
		qname = substring(name, 1, string_len(name));
		return rb_tree_find_node(defs, &qname);
	}

	/* If there is no namespace, must be top-level.  */
	if (ns == NULL)
		return rb_tree_find_node(defs, &name);

	/* Try prepending shorter and shorter prefixes of the namespace.  */
	end = string_len(*ns);
	assert(0 < end);
	do {
		/* Try this prefix.  */
		prefix = substring(*ns, 0, end);
		/* XXX Reuse a single buffer.  */
		qname = string_econcatn(&prefix, &dot, &name, NULL);
		def = rb_tree_find_node(defs, &qname);
		string_free(qname);
		if (def)
			return def;

		/* Not here.  Find a shorter prefix.  */
		assert(0 < end);
		while (--end && string_ptr(*ns)[end] != '.')
			continue;
	} while (end);

	/* Finally, try a top-level name without the namespace.  */
	def = rb_tree_find_node(defs, &name);
	if (def)
		return def;

	/* No dice.  */
	return NULL;
}

static void
collect_deps_msg(rb_tree_t *deps, rb_tree_t *defs, struct ast_message *msg_ast,
    const struct string *ns, int *errorp)
{
	struct def *msgdef;
	const struct string *subns;
	struct ast_message_stmt *stmts = msg_ast->stmts.stmts;
	size_t i, nstmts = msg_ast->stmts.nstmts;

	msgdef = find_def(defs, msg_ast->id, ns);
	if (msgdef == NULL) {	/* Redefined builtin type.  */
		assert(find_builtin_type(msg_ast->id, NULL));
		return;
	}
	if (msgdef->def_t != DEF_MSG ||
	    msgdef->def_u.message->msg_ast != msg_ast)
		return;		/* Duplicate definition.  */
	subns = &msgdef->def_qname;

	/*
	 * Go through the fields to check for colliding names/tags and
	 * to collect dependencies.
	 */
	for (i = 0; i < nstmts; i++) {
		switch (stmts[i].t) {
		case AST_MESSAGE_STMT_NULL:
			assert(!"spurious null message statement");
			break;
		case AST_MESSAGE_STMT_MESSAGE:
		case AST_MESSAGE_STMT_ENUMERATION:
		case AST_MESSAGE_STMT_EXTEND:
		case AST_MESSAGE_STMT_OPTION:
		case AST_MESSAGE_STMT_EXTENSIONS:
			break;
		case AST_MESSAGE_STMT_FIELD:
			collect_deps_field(deps, defs, &stmts[i].u.field,
			    msgdef, subns, errorp);
			break;
		default:
			assert(!"invalid message statement");
			break;
		}
	}

#ifdef PICOPBC_PROPLIB
    {
	/* Go through the fields to assign consecutive indices.  */
	/* XXX Consider making this independent of proplib.  */
	struct field *field;
	uint32_t fi = 0;

	assert(msgdef->def_t == DEF_MSG);
	RB_TREE_FOREACH(field, &msgdef->def_u.message->msg_fields_by_tag) {
		field->field_index = fi++;
	}
    }
#endif	/* PICOPBC_PROPLIB */

	/*
	 * Go through the subdefinitions to collect dependencies.
	 */
	for (i = 0; i < nstmts; i++) {
		switch (stmts[i].t) {
		case AST_MESSAGE_STMT_NULL:
			assert(!"spurious null message statement");
			break;
		case AST_MESSAGE_STMT_MESSAGE:
			collect_deps_msg(deps, defs, &stmts[i].u.message,
			    subns, errorp);
			break;
		case AST_MESSAGE_STMT_ENUMERATION:
			collect_deps_enum(deps, defs, &stmts[i].u.enumeration,
			    subns, errorp);
			break;
		case AST_MESSAGE_STMT_EXTEND:
		case AST_MESSAGE_STMT_OPTION:
		case AST_MESSAGE_STMT_EXTENSIONS:
		case AST_MESSAGE_STMT_FIELD:
			break;
		default:
			assert(!"invalid message statement");
			break;
		}
	}
}

static void
collect_deps_field(rb_tree_t *deps, rb_tree_t *defs,
    struct ast_field *field_ast, struct def *msgdef, const struct string *ns,
    int *errorp)
{
	struct message *msg;
	struct string type_text;
	enum builtin_type type;
	struct def *def;
	struct dep *dep, *dep0;
	struct field *field, *field0;

	/* Get the message record.  */
	assert(msgdef->def_t == DEF_MSG);
	msg = msgdef->def_u.message;

	/* Create a field record.  */
	field = emalloc(sizeof(*field));
	field->field_ast = field_ast;

	/* Resolve the type.  */
	type_text = field_ast->type.text;
	assert(strnlen(string_ptr(type_text), string_len(type_text) + 1) ==
	    string_len(type_text));
	if (find_builtin_type(type_text, &type)) {
		field->field_type_t = FIELD_TYPE_BUILTIN;
		field->field_type_u.builtin = type;
		goto type_ok;
	}
	def = find_def(defs, type_text, ns);
	if (def != NULL) {
		field->field_type_t = FIELD_TYPE_DEFINED;
		field->field_type_u.defined = def;
		goto type_ok;
	}

	/*
	 * If we can't resolve the type, report it.  But go on
	 * validating everything else.
	 */
    {
	char *v_field = string_evisciiz(field_ast->id);
	char *v_msg = string_evisciiz(*ns);
	char *v_type = string_evisciiz(type_text);
	efprintloc(stderr, field_ast->loc);
	efprintf(stderr, ": field %s in message %s has unknown type %s\n",
	    v_field, v_msg, v_type);
	free(v_type);
	free(v_msg);
	free(v_field);
    }
	field->field_type_t = FIELD_TYPE_UNKNOWN;
	*errorp = 1;

type_ok:
	/* Record the field by name, or fail if this is a duplicate.  */
	field0 = rb_tree_insert_node(&msg->msg_fields_by_name, field);
	if (field0 != field) {
		char *v_field = string_evisciiz(field_ast->id);
		char *v_msg = string_evisciiz(msgdef->def_qname);
		efprintloc(stderr, field_ast->loc);
		efprintf(stderr, ": message %s: duplicate field: %s\n",
		    v_msg, v_field);
		efprintloc(stderr, field0->field_ast->loc);
		efprintf(stderr, ": first defined here\n");
		free(v_msg);
		free(v_field);
		goto fail0;
	}

	/* Record the field by tag, or fail if this is a duplicate.  */
	field0 = rb_tree_insert_node(&msg->msg_fields_by_tag, field);
	if (field0 != field) {
		char *v_msg = string_evisciiz(msgdef->def_qname);
		char *v_field0 = string_evisciiz(field0->field_ast->id);
		char *v_field = string_evisciiz(field_ast->id);
		efprintloc(stderr, field_ast->loc);
		efprintf(stderr, ": message %s"
		    ": duplicate field tag: %"PRI_field_tag"\n",
		    v_msg, field_ast->tag);
		efprintloc(stderr, field0->field_ast->loc);
		efprintf(stderr, ": first defined here\n");
		free(v_field);
		free(v_field0);
		free(v_msg);
		goto fail1;
	}

#ifdef PICOPBC_PROPLIB
    {
	/* Get the proplib name option, if there is one.  */
	struct ast_field_options *options = &field_ast->options;
	struct ast_option *option_ast;

	option_ast = find_option_1(options->options, options->noptions,
	    PICOPBC_PROPLIB_OPTION_NAME);
	if (option_ast != NULL && option_ast->value.t == AST_OPTVAL_STRING) {
		field->field_proplib = option_ast->value.u.string;
	} else {
		if (option_ast != NULL) {
			assert(option_ast->value.t != AST_OPTVAL_STRING);
		    {
			char *v_field = string_evisciiz(field_ast->id);
			char *v_msg = string_evisciiz(msgdef->def_qname);
			efprintloc(stderr, option_ast->loc);
			efprintf(stderr, ": message %s: field %s",
			    v_msg, v_field);
			efprintf(stderr, ": invalid proplib name\n");
			free(v_msg);
			free(v_field);
		    }
		}
		field->field_proplib = field_ast->id;
	}

	/*
	 * Record the field by its proplib name, or fail if this is a
	 * duplicate.
	 */
	field0 = rb_tree_insert_node(&msg->msg_fields_by_proplib, field);
	if (field0 != field) {
		char *v_msg = string_evisciiz(msgdef->def_qname);
		char *v_field0 = string_evisciiz(field0->field_ast->id);
		char *v_field = string_evisciiz(field_ast->id);
		char *v_name = string_evisciiz(field->field_proplib);
		efprintloc(stderr, field_ast->loc);
		efprintf(stderr, ": message %s: duplicate proplib name",
		    v_msg);
		efprintf(stderr, ": `%s'\n", v_name);
		efprintloc(stderr, field0->field_ast->loc);
		efprintf(stderr, ": first defined here\n");
		free(v_name);
		free(v_field);
		free(v_field0);
		free(v_msg);
		goto fail2;
	}
    }
#endif	/* PICOPBC_PROPLIB */

	/* Report a dependency if the type is a defined type.  */
	if (field->field_type_t == FIELD_TYPE_UNKNOWN)
		return;
	if (field->field_type_t == FIELD_TYPE_BUILTIN)
		return;
	dep = emalloc(sizeof(*dep));
	dep->dep_user = msgdef;
	dep->dep_field = field;
	dep->dep_def = field->field_type_u.defined;
	dep0 = rb_tree_insert_node(deps, dep);
	/* If it was already recorded, discard it.  */
	if (dep0 != dep)
		free(dep);

	/* Success!  */
	return;

#ifdef PICOPBC_PROPLIB
fail3: attr_unused
	rb_tree_remove_node(&msg->msg_fields_by_proplib, field);
#endif	/* PICOPBC_PROPLIB */
fail2: attr_unused
	rb_tree_remove_node(&msg->msg_fields_by_tag, field);
fail1:	rb_tree_remove_node(&msg->msg_fields_by_name, field);
fail0:	*errorp = 1;
	free(field);
}

/*
 * This doesn't actually collect any dependencies.  It just piggybacks
 * on the same pass.
 */
static void
collect_deps_enum(rb_tree_t *deps attr_unused, rb_tree_t *defs,
    struct ast_enumeration *enum_ast, const struct string *ns, int *errorp)
{
	struct def *enumdef;
	struct ast_enum_stmt *stmts = enum_ast->stmts.stmts;
	size_t i, nstmts = enum_ast->stmts.nstmts;

	enumdef = find_def(defs, enum_ast->id, ns);
	if (enumdef == NULL) {	/* Redefined builtin type.  */
		assert(find_builtin_type(enum_ast->id, NULL));
		return;
	}
	if (enumdef->def_t != DEF_ENUM ||
	    enumdef->def_u.enumeration->enum_ast != enum_ast)
		return;		/* Duplicate definition.  */

	/*
	 * Go through the enumerands to check for colliding
	 * names/values.
	 */
	for (i = 0; i < nstmts; i++) {
		switch (stmts[i].t) {
		case AST_ENUM_STMT_NULL:
			assert(!"spurious null enum statement");
			break;
		case AST_ENUM_STMT_OPTION:
			break;
		case AST_ENUM_STMT_ENUMERAND:
			collect_deps_enumerand(&stmts[i].u.enumerand, enumdef,
			    errorp);
			break;
		default:
			assert(!"invalid enum statement");
			break;
		}
	}
}

static void
collect_deps_enumerand(struct ast_enumerand *enumerand_ast,
    struct def *enumdef, int *errorp)
{
	struct enumeration *enumeration;
	struct enumerand *enumerand, *enumerand0;

	assert(enumdef->def_t == DEF_ENUM);
	enumeration = enumdef->def_u.enumeration;

	enumerand = emalloc(sizeof(*enumerand));
	enumerand->enumerand_ast = enumerand_ast;

	/* Record the enumerand by name, or fail if this is a duplicate.  */
	enumerand0 = rb_tree_insert_node(&enumeration->enum_by_name,
	    enumerand);
	if (enumerand0 != enumerand) {
		char *v_enumerand = string_evisciiz(enumerand_ast->id);
		char *v_enumeration = string_evisciiz(enumdef->def_qname);
		efprintloc(stderr, enumerand_ast->loc);
		efprintf(stderr, ": enum %s: duplicate enumerand %s\n",
		    v_enumeration, v_enumerand);
		efprintloc(stderr, enumerand0->enumerand_ast->loc);
		efprintf(stderr, ": first defined here\n");
		free(v_enumeration);
		free(v_enumerand);
		goto fail0;
	}

	/* Record the enumerand by value, or fail if this is a duplicate.  */
	/* XXX Support the option enabling collisions.  */
	enumerand0 = rb_tree_insert_node(&enumeration->enum_by_value,
	    enumerand);
	if (enumerand0 != enumerand) {
		char *v_enumeration = string_evisciiz(enumdef->def_qname);
		char *v_enumerand0 =
		    string_evisciiz(enumerand0->enumerand_ast->id);
		char *v_enumerand = string_evisciiz(enumerand_ast->id);
		efprintloc(stderr, enumerand_ast->loc);
		efprintf(stderr, ": enum %s: duplicate value: %"PRId32"\n",
		    v_enumeration, enumerand_ast->value);
		efprintloc(stderr, enumerand0->enumerand_ast->loc);
		efprintf(stderr, ": first defined here\n");
		free(v_enumerand);
		free(v_enumerand0);
		free(v_enumeration);
		goto fail1;
	}

#ifdef PICOPBC_PROPLIB
    {
	/* Get the proplib value option, if there is one.  */
	struct ast_enumerand_options *options = &enumerand_ast->options;
	struct ast_option *option_ast;

	option_ast = find_option_1(options->options, options->noptions,
	    PICOPBC_PROPLIB_OPTION_VALUE);
	if (option_ast != NULL && option_ast->value.t == AST_OPTVAL_STRING) {
		enumerand->enumerand_proplib = option_ast->value.u.string;
	} else {
		if (option_ast != NULL) {
			assert(option_ast->value.t != AST_OPTVAL_STRING);
		    {
			char *v_enumerand = string_evisciiz(enumerand_ast->id);
			char *v_enumeration =
			    string_evisciiz(enumdef->def_qname);
			efprintloc(stderr, option_ast->loc);
			efprintf(stderr, ": enum %s: enumerand %s",
			    v_enumeration, v_enumerand);
			efprintf(stderr, ": invalid proplib value\n");
			free(v_enumeration);
			free(v_enumerand);
		    }
		}
		enumerand->enumerand_proplib = enumerand_ast->id;
	}

	/*
	 * Record the enumerand by its proplib value, or fail if this is
	 * a duplicate.
	 */
	enumerand0 = rb_tree_insert_node(&enumeration->enum_by_proplib,
	    enumerand);
	if (enumerand0 != enumerand) {
		char *v_enumeration = string_evisciiz(enumdef->def_qname);
		char *v_enumerand0 =
		    string_evisciiz(enumerand0->enumerand_ast->id);
		char *v_enumerand = string_evisciiz(enumerand_ast->id);
		char *v_name = string_evisciiz(enumerand->enumerand_proplib);
		efprintloc(stderr, enumerand_ast->loc);
		efprintf(stderr, ": enum %s: duplicate proplib value: `%s'\n",
		    v_enumeration, v_name);
		efprintloc(stderr, enumerand0->enumerand_ast->loc);
		efprintf(stderr, ": first defined here\n");
		free(v_name);
		free(v_enumerand);
		free(v_enumerand0);
		free(v_enumeration);
		goto fail2;
	}
    }
#endif	/* PICOPBC_PROPLIB */

	/* Success!  */
	return;

#ifdef PICOPBC_PROPLIB
fail3: attr_unused
	rb_tree_remove_node(&enumeration->enum_by_proplib, enumerand);
#endif	/* PICOPBC_PROPLIB */
fail2: attr_unused
	rb_tree_remove_node(&enumeration->enum_by_value, enumerand);
fail1:	rb_tree_remove_node(&enumeration->enum_by_name, enumerand);
fail0:	*errorp = 1;
	free(enumerand);
}

/* Topological sort */

/*
 * We need to sort message struct definitions for the sake of C, which
 * requires structs to be defined before they can be used outside
 * pointer declarators.  We reject cyclic definitions because they
 * either make no sense (for required fields) or cannot be rendered
 * into C at the moment (for optional fields).
 *
 * We also want to find the maximum depth of recursion in decoding, and
 * warn the user if there is a cycle (whether in required, optional, or
 * repeated fields) in which case the recursion depth of the decoder is
 * unbounded.
 *
 * XXX In the future, we will want out-of-line optional fields by
 * pointers, which do not contribute to the partial ordering, and oneof
 * fields.
 */

#define	container_of(PTR, TYPE, FIELD)					\
	((TYPE *)(((char *)(PTR)) - offsetof(TYPE, FIELD) +		\
	    0*sizeof((PTR) -						\
		&((TYPE *)(((char *)(PTR)) -				\
			offsetof(TYPE, FIELD)))->FIELD)))

struct topsort {
	struct defq	*defq;
	rb_tree_t	*defs;
	rb_tree_t	*deps;
	struct deflist	enclist;
};

static struct scc_vertex	*next_def(void *, struct scc_vertex *);
static struct scc_edge		*next_dep_stored(void *, struct scc_vertex *,
				    struct scc_edge *);
static struct scc_edge		*next_dep_encoded(void *, struct scc_vertex *,
				    struct scc_edge *);
static struct scc_vertex	*dep_pred(void *, struct scc_edge *);
static struct scc_vertex	*dep_succ(void *, struct scc_edge *);
static void			emit_def_stored(void *, struct scc_vertex *);
static void			emit_def_encoded(void *, struct scc_vertex *);

#define	MAX(A, B)	((A) > (B)? (A) : (B))

static void
topsort_defs(struct defq *defq, rb_tree_t *defs, rb_tree_t *deps, int *errorp)
{
	struct topsort topsort, *const T = &topsort;
	struct def *def, *def1;
	struct scc_vertex *V;
	struct dep *dep;
	bool maxdepth_p = true;

	T->defs = defs;
	T->deps = deps;

	/*
	 * Topologically sort the messages by stored dependencies:
	 * messages with required or optional submessages have the
	 * submessages stored in-line, so the submessages' struct
	 * declarations must appear first, and cycles are not
	 * permitted.
	 */
	T->defq = defq;
	strongly_connected_components(T, &next_def, &next_dep_stored,
	    &dep_pred, &dep_succ, &emit_def_stored);

	/* Find and report any cycles.  */
	SIMPLEQ_FOREACH(def, defq, def_entry) {
		V = scc_vertex_next(&def->def_scc);
		def1 = container_of(V, struct def, def_scc);
		if (def1 == def) {
			def->def_cyclic_storage = false;
			continue;
		}
		efprintloc(stderr, def->def_loc);
		efprintf(stderr, ": cycle in ");
		efprintdef(stderr, def);
		efprintf(stderr, ": used by ");
		efprintdef(stderr, def1);
		efprintf(stderr, "\n");
		do {
			efprintloc(stderr, def1->def_loc);
			efprintf(stderr, ": used by ");
			V = scc_vertex_next(&def1->def_scc);
			def1 = container_of(V, struct def, def_scc);
			efprintdef(stderr, def1);
			efprintf(stderr, "\n");
		} while (def1 != def);
		*errorp = 1;
		def->def_cyclic_storage = true;
	}

	/*
	 * Topologically sort the messages by encoded dependencies:
	 * messages with any submessages require recursion to decode
	 * the submessages, and we want to compute the maximum depth of
	 * recursion or determine that it is unbounded.  Cycles, and
	 * thus unbounded decoder stack depth, are permitted, but are
	 * almost always a bad idea.
	 */
	SIMPLEQ_INIT(&T->enclist);
	strongly_connected_components(T, &next_def, &next_dep_encoded,
	    &dep_pred, &dep_succ, &emit_def_encoded);

	SIMPLEQ_FOREACH(def, &T->enclist, def_encentry) {
		def->def_maxdepth = 0;
	}
	SIMPLEQ_FOREACH(def, &T->enclist, def_encentry) {
		V = scc_vertex_next(&def->def_scc);
		def1 = container_of(V, struct def, def_scc);
		if (def1 != def) {
			if (!def->def_cyclic_storage) {
				efprintloc(stderr, def->def_loc);
				efprintf(stderr, ": warning");
				efprintf(stderr, ": potential cycle in ");
				efprintdef(stderr, def);
				efprintf(stderr, ": used by ");
				efprintdef(stderr, def1);
				efprintf(stderr, "\n");
				do {
					efprintloc(stderr, def1->def_loc);
					efprintf(stderr, ": used by ");
					V = scc_vertex_next(&def1->def_scc);
					def1 = container_of(V, struct def,
					    def_scc);
					efprintdef(stderr, def1);
					efprintf(stderr, "\n");
				} while (def1 != def);
			}
			maxdepth_p = false;
		}

		assert(def->def_maxdepth == 0);
		if (!maxdepth_p)
			continue;

		def->def_maxdepth = 1;
		for (dep = rb_tree_find_node_geq(deps, def);
		     dep != NULL;
		     dep = rb_tree_iterate(deps, dep, RB_DIR_RIGHT)) {
			if (dep->dep_user != def)
				break;
			assert(dep->dep_def->def_maxdepth);
			assert(dep->dep_def->def_maxdepth < SIZE_MAX);
			def->def_maxdepth = MAX(def->def_maxdepth,
			    1 + dep->dep_def->def_maxdepth);
		}
	}
}

static struct scc_vertex *
next_def(void *cookie, struct scc_vertex *V)
{
	struct topsort *const T = cookie;
	struct def *def1;

	if (V == NULL) {
		def1 = RB_TREE_MIN(T->defs);
	} else {
		struct def *const def = container_of(V, struct def, def_scc);

		def1 = rb_tree_iterate(T->defs, def, RB_DIR_RIGHT);
	}

	return def1? &def1->def_scc : NULL;
}

static struct scc_edge *
next_dep_stored(void *cookie, struct scc_vertex *V, struct scc_edge *E)
{
	struct topsort *const T = cookie;
	struct def *const def = container_of(V, struct def, def_scc);
	struct dep *dep1;

	if (E == NULL) {
		dep1 = rb_tree_find_node_geq(T->deps, def);
	} else {
		struct dep *const dep = (struct dep *)E;

		dep1 = rb_tree_iterate(T->deps, dep, RB_DIR_RIGHT);
	}

retry:	if (dep1 == NULL || dep1->dep_user != def)
		return NULL;
	if (dep1->dep_field->field_ast->quant == AST_FQ_REPEATED) {
		dep1 = rb_tree_iterate(T->deps, dep1, RB_DIR_RIGHT);
		goto retry;
	}

	return (struct scc_edge *)dep1;
}

static struct scc_edge *
next_dep_encoded(void *cookie, struct scc_vertex *V, struct scc_edge *E)
{
	struct topsort *const T = cookie;
	struct def *const def = container_of(V, struct def, def_scc);
	struct dep *dep1;

	if (E == NULL) {
		dep1 = rb_tree_find_node_geq(T->deps, def);
	} else {
		struct dep *const dep = (struct dep *)E;

		dep1 = rb_tree_iterate(T->deps, dep, RB_DIR_RIGHT);
	}

	if (dep1 == NULL || dep1->dep_user != def)
		return NULL;

	return (struct scc_edge *)dep1;
}

static struct scc_vertex *
dep_pred(void *cookie, struct scc_edge *E)
{
	struct dep *const dep = (struct dep *)E;

	(void)cookie;		/* ignore */

	return &dep->dep_user->def_scc;
}

static struct scc_vertex *
dep_succ(void *cookie, struct scc_edge *E)
{
	struct dep *const dep = (struct dep *)E;

	(void)cookie;		/* ignore */

	return &dep->dep_def->def_scc;
}

static void
emit_def_stored(void *cookie, struct scc_vertex *V)
{
	struct topsort *const T = cookie;
	struct def *const def = container_of(V, struct def, def_scc);

	SIMPLEQ_INSERT_TAIL(T->defq, def, def_entry);
}

static void
emit_def_encoded(void *cookie, struct scc_vertex *V)
{
	struct topsort *const T = cookie;
	struct def *const def = container_of(V, struct def, def_scc);

	SIMPLEQ_INSERT_TAIL(&T->enclist, def, def_encentry);
}

static void
generate_code(FILE *hout, struct string hguard, FILE *cout,
    struct string hname, rb_tree_t *defs, struct defq *defq,
    const struct picopbc_formats *formats, int error)
{

	if (hout)
		generate_h(hout, hguard, defs, defq, formats);
	if (cout) {
		assert(3 <= string_len(hname)); /* "..." or <...> */
		generate_c(cout, hname, defs, defq, formats, error);
	}
}

static void
generate_h(FILE *hout, struct string hguard, rb_tree_t *defs,
    struct defq *defq, const struct picopbc_formats *formats)
{
	struct def *def;

	assert(0 < string_len(hguard));

	efprintf(hout, "/*\n");
	efprintf(hout, " * Stand back!\n");
	efprintf(hout, " * This file was automagically generated!\n");
	efprintf(hout, " */\n");
	efprintf(hout, "\n");
	efprintf(hout, "#ifndef\t%s\n", string_ptr(hguard));
	efprintf(hout, "#define\t%s\n", string_ptr(hguard));
	efprintf(hout, "\n");
	efprintf(hout, "#include <pb.h>\n");

	SIMPLEQ_FOREACH(def, defq, def_entry) {
		efprintf(hout, "\n");
		switch (def->def_t) {
		case DEF_ENUM:
			generate_enum_h(hout, def);
			break;
		case DEF_MSG:
			generate_msg_h(hout, defs, def);
			break;
		default:
			assert(!"invalid definition");
			break;
		}
	}

	efprintf(hout, "\n");
	efprintf(hout, "#endif\t/* %s */\n", string_ptr(hguard));
}

static void
generate_c(FILE *cout, struct string hname, rb_tree_t *defs, struct defq *defq,
    const struct picopbc_formats *formats, int error)
{
	struct def *def;

	assert(0 < string_len(hname));

	efprintf(cout, "/*\n");
	efprintf(cout, " * Stand back!\n");
	efprintf(cout, " * This file was automagically generated!\n");
	efprintf(cout, " */\n");
	efprintf(cout, "\n");
	efprintf(cout, "#include <pb.h>\n");
#ifdef PICOPBC_PROPLIB
	if (picopbc_format_enabled(formats, PICOPBC_FORMAT_PROPLIB))
		efprintf(cout, "#include <pb_prop.h>\n");
#endif	/* PICOPBC_PROPLIB */
	efprintf(cout, "\n");
	efprintf(cout, "#include %s\n", string_ptr(hname));

	SIMPLEQ_FOREACH(def, defq, def_entry) {
		efprintf(cout, "\n");
		switch (def->def_t) {
		case DEF_MSG:
			generate_msg_c(cout, defs, def, formats);
			break;
		case DEF_ENUM:
			generate_enum_c(cout, def, error);
			break;
		default:
			assert(!"invalid definition");
			break;
		}
	}

#ifdef PICOPBC_PROPLIB
	if (picopbc_format_enabled(formats, PICOPBC_FORMAT_PROPLIB))
		generate_proplib_c(cout, defs, defq, error);
#endif	/* PICOPBC_PROPLIB */
}

static void
generate_enum_h(FILE *hout, struct def *def)
{
	char *qnc;
	struct ast_enumeration *enumeration_ast;
	struct ast_enum_stmt *stmts;
	size_t i, nstmts;
	struct ast_enumerand *enumerand_ast;

	qnc = eqnamestrp_c(def->def_qname);
	efprintf(hout, "enum %s {\n", qnc);

	assert(def->def_t == DEF_ENUM);
	enumeration_ast = def->def_u.enumeration->enum_ast;
	stmts = enumeration_ast->stmts.stmts;
	nstmts = enumeration_ast->stmts.nstmts;
	for (i = 0; i < nstmts; i++) {
		if (stmts[i].t != AST_ENUM_STMT_ENUMERAND)
			continue;
		enumerand_ast = &stmts[i].u.enumerand;
		/* XXX Qualify the enumerand name.  */
		efprintf(hout, "\t%s = %"PRId32",\n",
		    string_ptr(enumerand_ast->id),
		    enumerand_ast->value);
	}
	efprintf(hout, "};\n");
	free(qnc);
}

static void
generate_msg_h(FILE *hout, rb_tree_t *defs, struct def *def)
{
	char *qnc;
	struct ast_message *message_ast;
	struct ast_message_stmt *stmts;
	size_t i, nstmts;

	qnc = eqnamestrp_c(def->def_qname);
	efprintf(hout, "struct %s {\n", qnc);
	efprintf(hout, "\tstruct pb_msg_hdr\t_pb_msg_hdr;\n");

	/* XXX Consider sorting the fields by descending size.  */
	assert(def->def_t == DEF_MSG);
	message_ast = def->def_u.message->msg_ast;
	stmts = message_ast->stmts.stmts;
	nstmts = message_ast->stmts.nstmts;
	for (i = 0; i < nstmts; i++) {
		if (stmts[i].t != AST_MESSAGE_STMT_FIELD)
			continue;
		generate_field_h(hout, defs, &stmts[i].u.field,
		    &def->def_qname);
	}

	efprintf(hout, "};\n");
	efprintf(hout, "\n");
	efprintf(hout, "extern const struct pb_msgdesc %s__msgdesc;\n", qnc);
	efprintf(hout, "\n");
	efprintf(hout, "static inline struct pb_msg_ptr\n");
	efprintf(hout, "%s_ptr(struct %s **ptrp)\n", qnc, qnc);
	efprintf(hout, "{\n");
	efprintf(hout, "\treturn (struct pb_msg_ptr) {\n");
	efprintf(hout, "\t    .pbmp_msgdesc = &%s__msgdesc,\n", qnc);
	efprintf(hout, "\t    .pbmp_ptrp = ptrp,\n");
	efprintf(hout, "\t};\n");
	efprintf(hout, "}\n");
	efprintf(hout, "\n");
	efprintf(hout, "static inline struct pb_msg\n");
	efprintf(hout, "%s(struct %s *ptr)\n", qnc, qnc);
	efprintf(hout, "{\n");
	efprintf(hout, "\treturn (struct pb_msg) {\n");
	efprintf(hout, "\t    .pbm_msgdesc = &%s__msgdesc,\n", qnc);
	efprintf(hout, "\t    .pbm_ptr = ptr,\n");
	efprintf(hout, "\t};\n");
	efprintf(hout, "}\n");
	free(qnc);
}

static const char *const ctypes[] = {
	[BUILTIN_TYPE_DOUBLE] = "double",
	[BUILTIN_TYPE_FLOAT] = "float",
	[BUILTIN_TYPE_INT32] = "int32_t",
	[BUILTIN_TYPE_INT64] = "int64_t",
	[BUILTIN_TYPE_UINT32] = "uint32_t",
	[BUILTIN_TYPE_UINT64] = "uint64_t",
	[BUILTIN_TYPE_SINT32] = "int32_t",
	[BUILTIN_TYPE_SINT64] = "int64_t",
	[BUILTIN_TYPE_FIXED32] = "uint32_t",
	[BUILTIN_TYPE_FIXED64] = "uint64_t",
	[BUILTIN_TYPE_SFIXED32] = "int32_t",
	[BUILTIN_TYPE_SFIXED64] = "int64_t",
	[BUILTIN_TYPE_BOOL] = "bool",
	[BUILTIN_TYPE_STRING] = "struct pb_string",
	[BUILTIN_TYPE_BYTES] = "struct pb_bytes",
};

static void
generate_field_h(FILE *hout, rb_tree_t *defs, struct ast_field *field_ast,
    const struct string *ns)
{
	enum builtin_type type;
	struct def *def;
	struct string tname;
	const char *tabs;

	if (find_builtin_type(field_ast->type.text, &type)) {
		tname = string_edupz(ctypes[type], strlen(ctypes[type]));
	} else if ((def = find_def(defs, field_ast->type.text, ns)) == NULL) {
		tname = string_edupz("(error)", strlen("(error)"));
	} else {
		switch (def->def_t) {
		case DEF_ENUM:
			tname = string_edupz("int32_t", strlen("int32_t"));
			break;
		case DEF_MSG: {
			struct string s = STRING_CONST("struct ");
			struct string qnc = eqnamestr_c(def->def_qname);

			tname = string_econcat(s, qnc);
			string_free(qnc);
			break;
		}
		default:
			assert(!"invalid definition");
			tname = string_edupz("(error)", strlen("(error)"));
			break;
		}
	}

	if (string_len(tname) < 8)
		tabs = "\t\t\t";
	else if (string_len(tname) < 16)
		tabs = "\t\t";
	else
		tabs = "\t";

	switch (field_ast->quant) {
	case AST_FQ_REQUIRED:
		efprintf(hout, "\t%s%s%s;\n", string_ptr(tname), tabs,
		    string_ptr(field_ast->id));
		break;
	case AST_FQ_OPTIONAL:
		efprintf(hout, "\tstruct {\n");
		efprintf(hout, "\t\tbool\t\t\tpresent;\n");
		efprintf(hout, "\t\t%s%svalue;\n", string_ptr(tname), tabs);
		efprintf(hout, "\t}\t\t\t%s;\n", string_ptr(field_ast->id));
		break;
	case AST_FQ_REPEATED:
		efprintf(hout, "\tstruct {\n");
		efprintf(hout, "\t\tstruct pb_repeated\trepeated;\n");
		efprintf(hout, "\t\t%s%s*item;\n", string_ptr(tname), tabs);
		efprintf(hout, "\t}\t\t\t%s;\n", string_ptr(field_ast->id));
		break;
	default:
		assert(!"invalid field quantifier");
		efprintf(hout, "\terror {\n");
		efprintf(hout, "\t\t%s;\n", string_ptr(tname));
		efprintf(hout, "\t}\t\t\t%s;\n", string_ptr(field_ast->id));
		break;
	}
}

static void
generate_msg_c(FILE *cout, rb_tree_t *defs, struct def *def,
    const struct picopbc_formats *formats)
{
	char *qnc;
	struct message *msg;
	struct field *field;
	size_t nreq;

	qnc = eqnamestrp_c(def->def_qname);

	assert(def->def_t == DEF_MSG);
	msg = def->def_u.message;

	if (RB_TREE_MIN(&msg->msg_fields_by_tag) != NULL) {
		efprintf(cout, "static const struct pb_field");
		efprintf(cout, " %s__fields[] = {\n", qnc);
		/* Sort by field tag, as required by the decoder library.  */
		RB_TREE_FOREACH(field, &msg->msg_fields_by_tag) {
			generate_field_c(cout, defs, qnc, field->field_ast,
			    &def->def_qname);
		}
		efprintf(cout, "};\n");
		efprintf(cout, "\n");
	}

	/*
	 * XXX Statically check this too.  Requires writing the
	 * definition of PB_MAX_REQUIRED_NFIELDS in two places, or
	 * including <pb.h> in picopbc.
	 */
	nreq = 0;
	RB_TREE_FOREACH(field, &msg->msg_fields_by_tag) {
		if (field->field_ast->quant == AST_FQ_REQUIRED)
			nreq++;
	}
	if (0 < nreq) {
		efprintf(cout, "/* Number of required fields.  */\n");
		efprintf(cout, "PB_CTASSERT(%zu <= PB_MAX_REQUIRED_FIELDS);\n",
		    nreq);
		efprintf(cout, "\n");
	}
	if (def->def_maxdepth)
		efprintf(cout, "/* Maximum depth: %zu.  */\n",
		    def->def_maxdepth);
	else
		efprintf(cout, "/* Unbounded stack depth!  */\n");

#ifdef PICOPBC_PROPLIB
	if (picopbc_format_enabled(formats, PICOPBC_FORMAT_PROPLIB)) {
		efprintf(cout, "\n");
		efprintf(cout, "static const struct pb_prop_msgdesc");
		efprintf(cout, " %s__prop;\n", qnc);
		efprintf(cout, "\n");
		efprintf(cout, "static const struct pb_format_cookie");
		efprintf(cout, " %s__format_cookies[] = {\n", qnc);
		efprintf(cout, "\t{\n");
		efprintf(cout, "\t\t.pbfc_format = &pb_prop_format,\n");
		efprintf(cout, "\t\t.pbfc_cookie = &%s__prop,\n", qnc);
		efprintf(cout, "\t},\n");
		efprintf(cout, "};\n");
		efprintf(cout, "\n");
	}
#endif

	efprintf(cout, "const struct pb_msgdesc %s__msgdesc = {\n", qnc);
	efprintf(cout, "\t.pbmd_abi_version = 0x%08"PRIx32",\n", abi_version);
	efprintf(cout, "\t.pbmd_name = \"%s\",\n", string_ptr(def->def_qname));
	efprintf(cout, "\t.pbmd_size = sizeof(struct %s),\n", qnc);
	if (RB_TREE_MIN(&msg->msg_fields_by_tag) != NULL) {
		efprintf(cout, "\t.pbmd_fields = %s__fields,\n", qnc);
		efprintf(cout, "\t.pbmd_nfields = sizeof(%s__fields) /\n",
		    qnc);
		efprintf(cout, "\t    sizeof(%s__fields[0]),\n", qnc);
	} else {
		efprintf(cout, "\t.pbmd_fields = NULL,\n");
		efprintf(cout, "\t.pbmd_nfields = 0,\n");
	}
#ifdef PICOPBC_PROPLIB
	if (picopbc_format_enabled(formats, PICOPBC_FORMAT_PROPLIB)) {
		efprintf(cout, "\t.pbmd_format_cookies");
		efprintf(cout, " = %s__format_cookies,\n", qnc);
		efprintf(cout, "\t.pbmd_nformat_cookies");
		efprintf(cout, " = sizeof(%s__format_cookies) /\n", qnc);
		efprintf(cout, "\t    sizeof(%s__format_cookies[0]),\n", qnc);
	}
#endif	/* PICOPBC_PROPLIB */
	efprintf(cout, "};\n");
	free(qnc);
}

static const char *const pbtypes[] = {
	[BUILTIN_TYPE_DOUBLE] = "PB_TYPE_DOUBLE",
	[BUILTIN_TYPE_FLOAT] = "PB_TYPE_FLOAT",
	[BUILTIN_TYPE_INT32] = "PB_TYPE_INT32",
	[BUILTIN_TYPE_INT64] = "PB_TYPE_INT64",
	[BUILTIN_TYPE_UINT32] = "PB_TYPE_UINT32",
	[BUILTIN_TYPE_UINT64] = "PB_TYPE_UINT64",
	[BUILTIN_TYPE_SINT32] = "PB_TYPE_SINT32",
	[BUILTIN_TYPE_SINT64] = "PB_TYPE_SINT64",
	[BUILTIN_TYPE_FIXED32] = "PB_TYPE_FIXED32",
	[BUILTIN_TYPE_FIXED64] = "PB_TYPE_FIXED64",
	[BUILTIN_TYPE_SFIXED32] = "PB_TYPE_SFIXED32",
	[BUILTIN_TYPE_SFIXED64] = "PB_TYPE_SFIXED64",
	[BUILTIN_TYPE_BOOL] = "PB_TYPE_BOOL",
	[BUILTIN_TYPE_STRING] = "PB_TYPE_STRING",
	[BUILTIN_TYPE_BYTES] = "PB_TYPE_BYTES",
};

/*
 * XXX Enforce libpicopb's limit on the number of required fields.
 * XXX Generate default values.
 */

static void
generate_field_c(FILE *cout, rb_tree_t *defs, const char *qnc,
    struct ast_field *field_ast, const struct string *ns)
{
	const char *qenum, *qu;
	enum builtin_type type;
	struct def *def;

	efprintf(cout, "\t{\n");
	switch (field_ast->quant) {
	case AST_FQ_REQUIRED:	qenum = "PBQ_REQUIRED";	qu = "required"; break;
	case AST_FQ_OPTIONAL:	qenum = "PBQ_OPTIONAL"; qu = "optional"; break;
	case AST_FQ_REPEATED:	qenum = "PBQ_REPEATED"; qu = "repeated"; break;
	default:		assert(!"invalid field quantifier");
				qenum = "PBQ_ERROR"; qu = "error"; break;
	}
	efprintf(cout, "\t\t.pbf_quant = %s,\n", qenum);
	efprintf(cout, "\t\t.pbf_qu = { .%s = {\n", qu);
	switch (field_ast->quant) {
	case AST_FQ_REQUIRED:
		efprintf(cout, "\t\t\t.offset = offsetof(struct %s, %s),\n",
		    qnc, string_ptr(field_ast->id));
		break;
	case AST_FQ_OPTIONAL:
		efprintf(cout, "\t\t\t.present_offset = offsetof(struct %s,"
		    " %s.present),\n",
		    qnc, string_ptr(field_ast->id));
		efprintf(cout, "\t\t\t.value_offset = offsetof(struct %s,"
		    " %s.value),\n",
		    qnc, string_ptr(field_ast->id));
		break;
	case AST_FQ_REPEATED:
		efprintf(cout, "\t\t\t.hdr_offset = offsetof(struct %s,"
		    " %s.repeated),\n",
		    qnc, string_ptr(field_ast->id));
		efprintf(cout, "\t\t\t.ptr_offset = offsetof(struct %s,"
		    " %s.item),\n",
		    qnc, string_ptr(field_ast->id));
		/* XXX Maximum repeated.  */
		break;
	}
	efprintf(cout, "\t\t} },\n");
	efprintf(cout, "\t\t.pbf_type = {\n");
	if (find_builtin_type(field_ast->type.text, &type)) {
		efprintf(cout, "\t\t\t.pbt_type = %s,\n", pbtypes[type]);
	} else if ((def = find_def(defs, field_ast->type.text, ns)) == NULL) {
		efprintf(cout, "\t\t\t.pbt_type = PB_TYPE_ERROR,\n");
	} else {
		char *qnc0 = eqnamestrp_c(def->def_qname);
		switch (def->def_t) {
		case DEF_ENUM:
			efprintf(cout, "\t\t\t.pbt_type = PB_TYPE_ENUM,\n");
			efprintf(cout, "\t\t\t.pbt_u = { .enumerated = {\n");
			efprintf(cout, "\t\t\t\t.enumeration =");
			efprintf(cout, " &%s__enumeration,\n", qnc0);
			efprintf(cout, "\t\t\t} },\n");
			break;
		case DEF_MSG:
			efprintf(cout, "\t\t\t.pbt_type = PB_TYPE_MSG,\n");
			efprintf(cout, "\t\t\t.pbt_u = { .msg = {\n");
			efprintf(cout, "\t\t\t\t.msgdesc = &%s__msgdesc,\n",
			    qnc0);
			efprintf(cout, "\t\t\t} },\n");
			break;
		default:
			assert(!"invalid definition");
			efprintf(cout, "\t\t\t.pbt_type = PB_TYPE_ERROR,\n");
		}
		free(qnc0);
	}
	efprintf(cout, "\t\t},\n");
	efprintf(cout, "\t\t.pbf_name = \"%s\",\n", string_ptr(field_ast->id));
	efprintf(cout, "\t\t.pbf_tag = %"PRId32",\n", field_ast->tag);
	efprintf(cout, "\t},\n");
}

static void
generate_enum_c(FILE *cout, struct def *def, int error)
{
	char *qnc;
	struct enumeration *enumeration;
	struct enumerand *enumerand;

	qnc = eqnamestrp_c(def->def_qname);

	assert(def->def_t == DEF_ENUM);
	enumeration = def->def_u.enumeration;

	efprintf(cout, "static const struct pb_enumerand");
	efprintf(cout, " %s__enumerands[] = {\n", qnc);
	assert(error || RB_TREE_MIN(&enumeration->enum_by_value) != NULL);
	RB_TREE_FOREACH(enumerand, &enumeration->enum_by_value) {
		efprintf(cout, "\t{\n");
		efprintf(cout, "\t\t.pbed_name = \"%s\",\n",
		    string_ptr(enumerand->enumerand_ast->id));
		efprintf(cout, "\t\t.pbed_number = %"PRId32",\n",
		    enumerand->enumerand_ast->value);
		efprintf(cout, "\t},\n");
	}
	efprintf(cout, "};\n");
	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_enumeration");
	efprintf(cout, " %s__enumeration = {\n", qnc);
	efprintf(cout, "\t.pben_enumerands = %s__enumerands,\n", qnc);
	efprintf(cout, "\t.pben_nenumerands =");
	efprintf(cout, " sizeof(%s__enumerands) /\n", qnc);
	efprintf(cout, "\t    sizeof(%s__enumerands[0]),\n", qnc);
	efprintf(cout, "};\n");

	free(qnc);
}

#ifdef PICOPBC_PROPLIB

static void
generate_proplib_c(FILE *cout, rb_tree_t *defs, struct defq *defq, int error)
{
	struct def *def;

	SIMPLEQ_FOREACH(def, defq, def_entry) {
		switch (def->def_t) {
		case DEF_MSG:
			generate_proplib_msg_c(cout, defs, def);
			break;
		case DEF_ENUM:
			generate_proplib_enum_c(cout, def, error);
			break;
		default:
			assert(!"invalid definition");
			break;
		}
	}
}

static void
generate_proplib_msg_c(FILE *cout, rb_tree_t *defs, struct def *def)
{
	char *qnc;
	struct message *msg;
	struct field *field;
	size_t nfield;

	qnc = eqnamestrp_c(def->def_qname);

	assert(def->def_t == DEF_MSG);
	msg = def->def_u.message;

	/*
	 * Determine whether this is a surrogate for an array.
	 *
	 * XXX This is a lossy heuristic.
	 */
	nfield = 0;
	RB_TREE_FOREACH(field, &msg->msg_fields_by_tag) {
		nfield++;
	}
	if (nfield == 1) {
		field = RB_TREE_MIN(&msg->msg_fields_by_tag);
		if (field->field_ast->quant == AST_FQ_REPEATED) {
			generate_proplib_array_c(cout, defs, def, msg, qnc);
			goto out;
		}
	}

	if (RB_TREE_MIN(&msg->msg_fields_by_tag) != NULL) {
		efprintf(cout, "\n");
		efprintf(cout, "static const struct pb_prop_record_field");
		efprintf(cout, " %s__proprecord_fields[] = {\n", qnc);

		/* Order must match the array of original fields.  */
		RB_TREE_FOREACH(field, &msg->msg_fields_by_tag) {
			efprintf(cout, "\t{\n");
			efprintf(cout, "\t\t.pbprf_key = ");
			efprint_cstring(cout, field->field_proplib);
			efprintf(cout, ",\n");
			efprintf(cout, "\t\t.pbprf_field = {\n");
			generate_proplib_field_c(cout, field, msg, qnc,
			    "\t\t");
			efprintf(cout, "\t\t},\n");
			efprintf(cout, "\t},\n");
		}

		efprintf(cout, "};\n");
	}

	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_prop_msgdesc %s__prop = {\n",
	    qnc);
	efprintf(cout, "\t.pbpm_msgdesc = &%s__msgdesc,\n", qnc);
	efprintf(cout, "\t.pbpm_t = PB_PROP_MSG_RECORD,\n");
	if (RB_TREE_MIN(&msg->msg_fields_by_tag) != NULL) {
		efprintf(cout, "\t.pbpm_u = { .record = {\n");
		efprintf(cout, "\t\t.pbpr_fields = %s__proprecord_fields,\n",
		    qnc);
		efprintf(cout, "\t\t.pbpr_nfields =");
		efprintf(cout, " sizeof(%s__proprecord_fields) /\n", qnc);
		efprintf(cout, "\t\t    sizeof(%s__proprecord_fields[0]),\n",
		    qnc);
		efprintf(cout, "\t} },\n");
	}
	efprintf(cout, "};\n");

out:	free(qnc);
}

static void
generate_proplib_array_c(FILE *cout, rb_tree_t *defs, struct def *def,
    struct message *msg, const char *qnc)
{
	struct field *field;

	field = RB_TREE_MIN(&msg->msg_fields_by_tag);
	assert(field != NULL);
	assert(rb_tree_iterate(&msg->msg_fields_by_tag, field, RB_DIR_RIGHT)
	    == NULL);
	assert(field->field_index == 0);

	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_prop_field %s__proparray_field",
	    qnc);
	efprintf(cout, " = {\n");
	generate_proplib_field_c(cout, field, msg, qnc, "");
	efprintf(cout, "};\n");
	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_prop_msgdesc %s__prop = {\n",
	    qnc);
	efprintf(cout, "\t.pbpm_msgdesc = &%s__msgdesc,\n", qnc);
	efprintf(cout, "\t.pbpm_t = PB_PROP_MSG_ARRAY,\n");
	efprintf(cout, "\t.pbpm_u = { .array = {\n");
	efprintf(cout, "\t\t.pbpa_msgdesc = &%s__msgdesc,\n", qnc);
	efprintf(cout, "\t\t.pbpa_field = &%s__proparray_field,\n", qnc);
	efprintf(cout, "\t} },\n");
	efprintf(cout, "};\n");
}

static void
generate_proplib_field_c(FILE *cout, struct field *field, struct message *msg,
    const char *qnc, const char *prefix)
{

	efprintf(cout, "%s\t.pbpf_msgdesc = &%s__msgdesc,\n", prefix, qnc);
	efprintf(cout, "%s\t.pbpf_fieldno = %"PRId32",\n", prefix,
	    field->field_index);
	if (field->field_type_t == FIELD_TYPE_DEFINED) {
		struct def *tdef = field->field_type_u.defined;
		char *tqnc = eqnamestrp_c(tdef->def_qname);
		switch (tdef->def_t) {
		case DEF_MSG:
			efprintf(cout, "%s\t.pbpf_u = {", prefix);
			efprintf(cout, " .message = &%s__prop", tqnc);
			efprintf(cout, " },\n");
			break;
		case DEF_ENUM:
			efprintf(cout, "%s\t.pbpf_u = {", prefix);
			efprintf(cout, " .enumeration = &%s__propenum", tqnc);
			efprintf(cout, " },\n");
			break;
		default:
			assert(!"invalid definition");
			break;
		}
		free(tqnc);
	}
}

static void
generate_proplib_enum_c(FILE *cout, struct def *def, int error)
{
	char *qnc;
	struct enumeration *enumeration;
	struct enumerand *enumerand;

	qnc = eqnamestrp_c(def->def_qname);

	assert(def->def_t == DEF_ENUM);
	enumeration = def->def_u.enumeration;

	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_prop_enumerand");
	efprintf(cout, " %s__propenum_by_number[] = {\n", qnc);
	assert(error || RB_TREE_MIN(&enumeration->enum_by_value) != NULL);
	RB_TREE_FOREACH(enumerand, &enumeration->enum_by_value) {
		efprintf(cout, "\t{\n");
		efprintf(cout, "\t\t.pbped_string = ");
		efprint_cstring(cout, enumerand->enumerand_proplib);
		efprintf(cout, ",\n");
		efprintf(cout, "\t\t.pbped_number = %"PRId32",\n",
		    enumerand->enumerand_ast->value);
		efprintf(cout, "\t},\n");
	}
	efprintf(cout, "};\n");
	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_prop_enumerand");
	efprintf(cout, " %s__propenum_by_string[] = {\n", qnc);
	assert(error || RB_TREE_MIN(&enumeration->enum_by_proplib) != NULL);
	RB_TREE_FOREACH(enumerand, &enumeration->enum_by_proplib) {
		efprintf(cout, "\t{\n");
		efprintf(cout, "\t\t.pbped_string = ");
		efprint_cstring(cout, enumerand->enumerand_proplib);
		efprintf(cout, ",\n");
		efprintf(cout, "\t\t.pbped_number = %"PRId32",\n",
		    enumerand->enumerand_ast->value);
		efprintf(cout, "\t},\n");
	}
	efprintf(cout, "};\n");
	efprintf(cout, "\n");
	efprintf(cout, "static const struct pb_prop_enumeration");
	efprintf(cout, " %s__propenum = {\n", qnc);
	efprintf(cout, "\t.pbpen_by_number = %s__propenum_by_number,\n", qnc);
	efprintf(cout, "\t.pbpen_by_string = %s__propenum_by_string,\n", qnc);
	efprintf(cout, "\t.pbpen_nenumerands =");
	efprintf(cout, " sizeof(%s__propenum_by_number) /\n", qnc);
	efprintf(cout, "\t    sizeof(%s__propenum_by_number[0]),\n", qnc);
	efprintf(cout, "};\n");
}

/*
 * optname_estring(optname)
 *
 *	Return a string representation of the given option name AST.
 *	Aborts as if with efun(3) if out of memory.
 */
static struct string
optname_estring(const struct ast_optname *optname)
{
	const struct string lround = STRING_CONST("(");
	const struct string rround = STRING_CONST(")");
	const struct string dot = STRING_CONST(".");
	const struct string null = STRING_CONST("");
	struct string s = string_null;
	size_t i;

	/* XXX quadratic */
	for (i = 0; i < optname->nparts; i++) {
		const struct string *const next =
		    (i + 1 < optname->nparts ? &dot : &null);
		switch (optname->parts[i].t) {
		case AST_OPTPART_NORMAL:
			s = string_econcatn_into(&s,
			    &optname->parts[i].u.normal, next, NULL);
			break;
		case AST_OPTPART_EXTENSION:
			s = string_econcatn_into(&s,
			    &lround, &optname->parts[i].u.extension, &rround,
			    next, NULL);
			break;
		default:
			assert(!"invalid option part");
			break;
		}
	}

	return s;
}

/*
 * optname_ref_order(optname, reference)
 *
 *	Return negative, zero, or positive if, respectively, the option
 *	name represented by the structure optname precedes, equals, or
 *	follows the option name represented by the NUL-terminated C
 *	string reference.
 */
static int
optname_ref_order(const struct ast_optname *optname, const char *reference)
{
	struct string target;
	int order;

	target = optname_estring(optname);
	order = strncmp(string_ptr(target), reference, string_len(target) + 1);
	string_free(target);

	return order;
}

/*
 * optname_ref_equal(optname, reference)
 *
 *	Return true if the option name represented by the structure
 *	optname is equal to the option name represented by the
 *	NUL-terminated C string reference, or false if not.
 */
static bool
optname_ref_equal(const struct ast_optname *optname, const char *reference)
{

	return optname_ref_order(optname, reference) == 0;
}

/*
 * find_option_1(options, noptions, name)
 *
 *	Find the unique option with the given name among the given
 *	array of options.  Fail if there are multiple such options.
 *	Return NULL if there are none.
 */
static struct ast_option *
find_option_1(struct ast_option *options, size_t noptions, const char *name)
{
	struct ast_option *found = NULL;
	size_t i;

	for (i = 0; i < noptions; i++) {
		struct ast_option *option = &options[i];

		/* Skip if it's not the desired option.  */
		if (!optname_ref_equal(&option->name, name))
			continue;

		/* Noisily ignore it if we already have one.  */
		if (found) {
			efprintloc(stderr, option->loc);
			efprintf(stderr, ": duplicate option `%s'\n", name);
			efprintloc(stderr, found->loc);
			efprintf(stderr, ": first specified here\n");
			continue;
		}

		/* Remember it, and go on to find any duplicates.  */
		found = option;
	}

	return found;
}

/*
 * efprint_cstring(out, s)
 *
 *	Print a C-language representation of the string s to cout,
 *	including surrounding quotation marks and any necessary escape
 *	characters.
 */
static void
efprint_cstring(FILE *out, struct string s)
{
	size_t i;

	efprintf(out, "\"");
	for (i = 0; i < string_len(s); i++) {
		unsigned char ch = string_ptr(s)[i];

		if (ch == '"' || ch == '\\')
			efprintf(out, "\\%c", ch);
		else if (ch < 32 || 127 <= ch)
			efprintf(out, "\\%03o", ch);
		else
			efprintf(out, "%c", ch);
	}
	efprintf(out, "\"");
}

#endif	/* PICOPBC_PROPLIB */

static unsigned
efprintloc(FILE *out, struct ast_srcloc loc)
{

	return efprintf(out, "%s:%zu:%zu",
	    loc.filename, loc.lineno, loc.column);
}

static unsigned
efprintdef(FILE *out, struct def *def)
{
	const char *prefix;
	char *v = string_evisciiz(def->def_qname);
	unsigned n;

	switch (def->def_t) {
	case DEF_ENUM:	prefix = "enum"; break;
	case DEF_MSG:	prefix = "message"; break;
	default:	assert(!"invalid definition");
			prefix = "unknown"; break;
	}

	n = efprintf(out, "%s %s", prefix, v);
	free(v);
	return n;
}

static struct string
eqnamestr_c(struct string qname)
{
	const struct string sep = STRING_CONST("__");
	struct string qnc = string_null;
	size_t start, i, n = string_len(qname);

	for (start = i = 0; i < n; i++) {
		if (string_ptr(qname)[i] == '.') {
			struct string seg = substring(qname, start, i);
			qnc = string_econcatn_into(&qnc, &seg, &sep, NULL);
			start = i + 1;
		}
	}
	qnc = string_econcat_into(qnc, string_suffix(qname, start));

	return qnc;
}

static char *
eqnamestrp_c(struct string qname)
{

	return string_ptr(eqnamestr_c(qname));
}