common/eversholt/itree.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * itree.c -- instance tree creation and manipulation
 *
 * this module provides the instance tree
 */

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include "alloc.h"
#include "out.h"
#include "stable.h"
#include "literals.h"
#include "lut.h"
#include "tree.h"
#include "ptree.h"
#include "itree.h"
#include "ipath.h"
#include "iexpr.h"
#include "eval.h"
#include "config.h"

/*
 * struct info contains the state we keep when expanding a prop statement
 * as part of constructing the instance tree.  state kept in struct info
 * is the non-recursive stuff -- the stuff that doesn't need to be on
 * the stack.  the rest of the state that is passed between all the
 * mutually recursive functions, is required to be on the stack since
 * we need to backtrack and recurse as we do the instance tree construction.
 */
struct info {
	struct lut *lut;
	struct node *anp;	/* arrow np */
	struct lut *ex;		/* dictionary of explicit iterators */
	struct config *croot;
} Ninfo;

/*
 * struct wildcardinfo is used to track wildcarded portions of paths.
 *
 * for example, if the epname of an event is "c/d" and the path "a/b/c/d"
 * exists, the wildcard path ewname is filled in with the path "a/b".  when
 * matching is done, epname is temporarily replaced with the concatenation
 * of ewname and epname.
 *
 * a linked list of these structs is used to track the expansion of each
 * event node as it is processed in vmatch() --> vmatch_event() calls.
 */
struct wildcardinfo {
	struct node *nptop;		/* event node fed to vmatch */
	struct node *oldepname;		/* epname without the wildcard part */
	struct node *ewname;		/* wildcard path */
	int got_wc_hz;
	struct wildcardinfo *next;
};

static struct wildcardinfo *wcproot = NULL;

static void vmatch(struct info *infop, struct node *np, struct node *lnp,
    struct node *anp);
static void hmatch(struct info *infop, struct node *np, struct node *nextnp);
static void hmatch_event(struct info *infop, struct node *eventnp,
    struct node *epname, struct config *ncp, struct node *nextnp, int rematch);
static void itree_pbubble(int flags, struct bubble *bp);
static void itree_pruner(void *left, void *right, void *arg);
static void itree_destructor(void *left, void *right, void *arg);
static int itree_set_arrow_traits(struct arrow *ap, struct node *fromev,
    struct node *toev, struct lut *ex);
static void itree_free_arrowlists(struct bubble *bubp, int arrows_too);
static void itree_prune_arrowlists(struct bubble *bubp);
static void arrow_add_within(struct arrow *ap, struct node *xpr);
static struct arrow *itree_add_arrow(struct node *apnode,
    struct node *fromevent, struct node *toevent, struct lut *ex);
static struct event *find_or_add_event(struct info *infop, struct node *np);
static void add_arrow(struct bubble *bp, struct arrow *ap);
static struct constraintlist *itree_add_constraint(struct arrow *arrowp,
    struct node *c);
static struct bubble *itree_add_bubble(struct event *eventp,
    enum bubbletype btype, int nork, int gen);
static void itree_free_bubble(struct bubble *freeme);
static void itree_free_constraints(struct arrow *ap);

/*
 * the following struct contains the state we build up during
 * vertical and horizontal expansion so that generate()
 * has everything it needs to construct the appropriate arrows.
 * after setting up the state by calling:
 *	generate_arrownp()
 *	generate_nork()
 *	generate_new()
 *	generate_from()
 *	generate_to()
 * the actual arrow generation is done by calling:
 *	generate()
 */
static struct {
	int generation;		/* generation number of arrow set */
	int matched;		/* number of matches */
	struct node *arrownp;	/* top-level parse tree for arrow */
	int n;			/* n value associated with arrow */
	int k;			/* k value associated with arrow */
	struct node *fromnp;	/* left-hand-side event in parse tree */
	struct node *tonp;	/* right-hand-side event in parse tree */
	struct event *frome;	/* left-hand-side event in instance tree */
	struct event *toe;	/* right-hand-side event in instance tree */
	struct bubble *frombp;	/* bubble arrow comes from */
	struct bubble *tobp;	/* bubble arrow goes to */
} G;

static void
generate_arrownp(struct node *arrownp)
{
	G.arrownp = arrownp;
}

static void
generate_nork(int n, int k)
{
	G.n = n;
	G.k = k;
}

static void
generate_new(void)
{
	G.generation++;
}

static void
generate_from(struct node *fromeventnp)
{
	G.frombp = NULL;
	G.fromnp = fromeventnp;
}

static void
generate_to(struct node *toeventnp)
{
	G.tonp = toeventnp;
}

static void
generate(struct info *infop)
{
	struct arrow *arrowp;

	ASSERT(G.arrownp != NULL);
	ASSERT(G.fromnp != NULL);
	ASSERT(G.tonp != NULL);

	out(O_ALTFP|O_VERB3|O_NONL, "        Arrow \"");
	ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, G.fromnp);
	out(O_ALTFP|O_VERB3|O_NONL, "\" -> \"");
	ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, G.tonp);
	out(O_ALTFP|O_VERB3|O_NONL, "\" ");

	arrowp = itree_add_arrow(G.arrownp, G.fromnp, G.tonp, infop->ex);
	if (arrowp == NULL) {
		out(O_ALTFP|O_VERB3, "(prevented by constraints)");
	} else {
		out(O_ALTFP|O_VERB3, "");
		if (!G.frombp) {
			G.frome = find_or_add_event(infop, G.fromnp);
			G.frombp = itree_add_bubble(G.frome, B_FROM, G.n, 0);
		}
		G.toe = find_or_add_event(infop, G.tonp);
		G.tobp = itree_add_bubble(G.toe, B_TO, G.k, G.generation);
		arrowp->tail = G.frombp;
		arrowp->head = G.tobp;
		add_arrow(G.frombp, arrowp);
		add_arrow(G.tobp, arrowp);
	}
}

enum childnode_action {
	CN_NONE,
	CN_DUP
};

static struct node *
tname_dup(struct node *namep, enum childnode_action act)
{
	struct node *retp = NULL;
	const char *file;
	int line;

	if (namep == NULL)
		return (NULL);

	file = namep->file;
	line = namep->line;

	for (; namep != NULL; namep = namep->u.name.next) {
		struct node *newnp = newnode(T_NAME, file, line);

		newnp->u.name.t = namep->u.name.t;
		newnp->u.name.s = namep->u.name.s;
		newnp->u.name.last = newnp;
		newnp->u.name.it = namep->u.name.it;
		newnp->u.name.cp = namep->u.name.cp;

		if (act == CN_DUP) {
			struct node *npc;

			npc = namep->u.name.child;
			if (npc != NULL) {
				switch (npc->t) {
				case T_NUM:
					newnp->u.name.child =
					    newnode(T_NUM, file, line);
					newnp->u.name.child->u.ull =
					    npc->u.ull;
					break;
				case T_NAME:
					newnp->u.name.child =
					    tree_name(npc->u.name.s,
					    npc->u.name.it, file, line);
					break;
				default:
					out(O_DIE, "tname_dup: "
					    "invalid child type %s",
					    ptree_nodetype2str(npc->t));
				}
			}
		}

		if (retp == NULL) {
			retp = newnp;
		} else {
			retp->u.name.last->u.name.next = newnp;
			retp->u.name.last = newnp;
		}
	}

	return (retp);
}

struct prop_wlk_data {
	struct lut *props;
	struct node *epname;
};

static struct lut *props2instance(struct node *, struct node *);

/*
 * let oldepname be a subset of epname.  return the subsection of epname
 * that ends with oldepname.  make each component in the path explicitly
 * instanced (i.e., with a T_NUM child).
 */
static struct node *
tname_dup_to_epname(struct node *oldepname, struct node *epname)
{
	struct node *npref, *npend, *np1, *np2;
	struct node *ret = NULL;
	int foundmatch = 0;

	if (epname == NULL)
		return (NULL);

	/*
	 * search for the longest path in epname which contains
	 * oldnode->u.event.epname.  set npend to point to just past the
	 * end of this path.
	 */
	npend = NULL;
	for (npref = epname; npref; npref = npref->u.name.next) {
		if (npref->u.name.s == oldepname->u.name.s) {
			for (np1 = npref, np2 = oldepname;
			    np1 != NULL && np2 != NULL;
			    np1 = np1->u.name.next, np2 = np2->u.name.next) {
				if (np1->u.name.s != np2->u.name.s)
					break;
			}
			if (np2 == NULL) {
				foundmatch = 1;
				npend = np1;
				if (np1 == NULL) {
					/* oldepname matched npref up to end */
					break;
				}
			}
		}
	}

	if (foundmatch == 0) {
		/*
		 * if oldepname could not be found in epname, return a
		 * duplicate of the former.  do not try to instantize
		 * oldepname since it might not be a path.
		 */
		return (tname_dup(oldepname, CN_DUP));
	}

	/*
	 * dup (epname -- npend).  all children should be T_NUMs.
	 */
	for (npref = epname;
	    ! (npref == NULL || npref == npend);
	    npref = npref->u.name.next) {
		struct node *newnp = newnode(T_NAME, oldepname->file,
		    oldepname->line);

		newnp->u.name.t = npref->u.name.t;
		newnp->u.name.s = npref->u.name.s;
		newnp->u.name.last = newnp;
		newnp->u.name.it = npref->u.name.it;
		newnp->u.name.cp = npref->u.name.cp;

		newnp->u.name.child = newnode(T_NUM, oldepname->file,
		    oldepname->line);

		if (npref->u.name.child == NULL ||
		    npref->u.name.child->t != T_NUM) {
			int childnum;

			ASSERT(npref->u.name.cp != NULL);
			config_getcompname(npref->u.name.cp, NULL, &childnum);
			newnp->u.name.child->u.ull = childnum;
		} else {
			newnp->u.name.child->u.ull =
			    npref->u.name.child->u.ull;
		}

		if (ret == NULL) {
			ret = newnp;
		} else {
			ret->u.name.last->u.name.next = newnp;
			ret->u.name.last = newnp;
		}
	}

	return (ret);
}

/*
 * restriction: oldnode->u.event.epname has to be equivalent to or a subset
 * of epname
 */
static struct node *
tevent_dup_to_epname(struct node *oldnode, struct node *epname)
{
	struct node *ret;

	ret = newnode(T_EVENT, oldnode->file, oldnode->line);
	ret->u.event.ename = tname_dup(oldnode->u.event.ename, CN_NONE);
	ret->u.event.epname = tname_dup_to_epname(oldnode->u.event.epname,
	    epname);
	return (ret);
}

static void
nv_instantiate(void *name, void *val, void *arg)
{
	struct prop_wlk_data *pd = (struct prop_wlk_data *)arg;
	struct node *orhs = (struct node *)val;
	struct node *nrhs;

	/* handle engines by instantizing the entire engine */
	if (name == L_engine) {
		ASSERT(orhs->t == T_EVENT);
		ASSERT(orhs->u.event.ename->u.name.t == N_SERD);

		/* there are only SERD engines for now */

		nrhs = newnode(T_SERD, orhs->file, orhs->line);
		nrhs->u.stmt.np = tevent_dup_to_epname(orhs, pd->epname);
		nrhs->u.stmt.lutp = props2instance(orhs, pd->epname);
		pd->props = lut_add(pd->props, name, nrhs, NULL);
		return;
	}

	switch (orhs->t) {
	case T_NUM:
		nrhs = newnode(T_NUM, orhs->file, orhs->line);
		nrhs->u.ull = orhs->u.ull;
		pd->props = lut_add(pd->props, name, nrhs, NULL);
		break;
	case T_TIMEVAL:
		nrhs = newnode(T_TIMEVAL, orhs->file, orhs->line);
		nrhs->u.ull = orhs->u.ull;
		pd->props = lut_add(pd->props, name, nrhs, NULL);
		break;
	case T_NAME:
		nrhs = tname_dup_to_epname(orhs, pd->epname);
		pd->props = lut_add(pd->props, name, nrhs, NULL);
		break;
	case T_EVENT:
		nrhs = tevent_dup_to_epname(orhs, pd->epname);
		pd->props = lut_add(pd->props, name, nrhs, NULL);
		break;
	case T_GLOBID:
		nrhs = newnode(T_GLOBID, orhs->file, orhs->line);
		nrhs->u.globid.s = orhs->u.globid.s;
		pd->props = lut_add(pd->props, name, nrhs, NULL);
		break;
	case T_FUNC:
		/* for T_FUNC, we don't duplicate it, just point to node */
		pd->props = lut_add(pd->props, name, orhs, NULL);
		break;
	default:
		out(O_DIE, "unexpected nvpair value type %s",
		    ptree_nodetype2str(((struct node *)val)->t));
	}
}

static struct lut *
props2instance(struct node *eventnp, struct node *epname)
{
	struct prop_wlk_data pd;

	pd.props = NULL;
	pd.epname = epname;

	ASSERT(eventnp->u.event.declp != NULL);
	lut_walk(eventnp->u.event.declp->u.stmt.lutp, nv_instantiate, &pd);
	return (pd.props);
}

/*ARGSUSED*/
static void
instances_destructor(void *left, void *right, void *arg)
{
	struct node *dn = (struct node *)right;

	if (dn->t == T_SERD) {
		/* we allocated the lut during itree_create(), so free it */
		lut_free(dn->u.stmt.lutp, instances_destructor, NULL);
		dn->u.stmt.lutp = NULL;
	}
	if (dn->t != T_FUNC)	/* T_FUNC pointed to original node */
		tree_free(dn);
}

/*ARGSUSED*/
static void
payloadprops_destructor(void *left, void *right, void *arg)
{
	FREE(right);
}

/*ARGSUSED*/
static void
serdprops_destructor(void *left, void *right, void *arg)
{
	FREE(right);
}

/*
 * event_cmp -- used via lut_lookup/lut_add on instance tree lut
 */
static int
event_cmp(struct event *ep1, struct event *ep2)
{
	int diff;

	if ((diff = ep2->enode->u.event.ename->u.name.s -
	    ep1->enode->u.event.ename->u.name.s) != 0)
		return (diff);
	if ((diff = (char *)ep2->ipp - (char *)ep1->ipp) != 0)
		return (diff);
	return (0);

}

struct event *
itree_lookup(struct lut *itp, const char *ename, const struct ipath *ipp)
{
	struct event searchevent;	/* just used for searching */
	struct node searcheventnode;
	struct node searchenamenode;

	searchevent.enode = &searcheventnode;
	searcheventnode.t = T_EVENT;
	searcheventnode.u.event.ename = &searchenamenode;
	searchenamenode.t = T_NAME;
	searchenamenode.u.name.s = ename;
	searchevent.ipp = ipp;
	return (lut_lookup(itp, (void *)&searchevent, (lut_cmp)event_cmp));
}

static struct event *
find_or_add_event(struct info *infop, struct node *np)
{
	struct event *ret;
	struct event searchevent;	/* just used for searching */

	ASSERTeq(np->t, T_EVENT, ptree_nodetype2str);

	searchevent.enode = np;
	searchevent.ipp = ipath(np->u.event.epname);
	if ((ret = lut_lookup(infop->lut, (void *)&searchevent,
	    (lut_cmp)event_cmp)) != NULL)
		return (ret);

	/* wasn't already in tree, allocate it */
	ret = alloc_xmalloc(sizeof (*ret));
	bzero(ret, sizeof (*ret));

	ret->t = np->u.event.ename->u.name.t;
	ret->enode = np;
	ret->ipp = searchevent.ipp;
	ret->props = props2instance(np, np->u.event.epname);

	infop->lut = lut_add(infop->lut, (void *)ret, (void *)ret,
	    (lut_cmp)event_cmp);

	return (ret);
}

/*
 * Used for handling expansions where first part of oldepname is a horizontal
 * expansion. Recurses through entire tree. oldepname argument is always the
 * full path as in the rules. Once we find a match we go back to using
 * hmatch_event to handle the rest.
 */
static void
hmatch_full_config(struct info *infop, struct node *eventnp,
    struct node *oldepname, struct config *ncp, struct node *nextnp,
    struct iterinfo *iterinfop)
{
	char *cp_s;
	int cp_num;
	struct config *cp;
	struct node *saved_ewname;
	struct node *saved_epname;
	struct config *pcp, *ocp;
	struct node *cpnode;
	struct node *ewlp, *ewfp;

	for (cp = ncp; cp; cp = config_next(cp)) {
		config_getcompname(cp, &cp_s, &cp_num);
		if (cp_s == oldepname->u.name.s) {
			/*
			 * Found one.
			 */
			iterinfop->num = cp_num;

			/*
			 * Need to set ewname, epname for correct node as is
			 * needed by constraint path matching. This code is
			 * similar to that in vmatch_event.
			 */
			saved_ewname = eventnp->u.event.ewname;
			saved_epname = eventnp->u.event.epname;
			ocp = oldepname->u.name.cp;

			/*
			 * Find correct ewname by walking back up the config
			 * tree adding each name portion as we go.
			 */
			pcp = config_parent(cp);
			eventnp->u.event.ewname = NULL;
			for (; pcp != infop->croot; pcp = config_parent(pcp)) {
				config_getcompname(pcp, &cp_s, &cp_num);
				cpnode = tree_name(cp_s, IT_NONE, NULL, 0);
				cpnode->u.name.child = newnode(T_NUM, NULL, 0);
				cpnode->u.name.child->u.ull = cp_num;
				cpnode->u.name.cp = pcp;
				if (eventnp->u.event.ewname != NULL) {
					cpnode->u.name.next =
					    eventnp->u.event.ewname;
					cpnode->u.name.last =
					    eventnp->u.event.ewname->
					    u.name.last;
				}
				eventnp->u.event.ewname = cpnode;
			}

			/*
			 * Now create correct epname by duping new ewname
			 * and appending oldepname.
			 */
			ewfp = tname_dup(eventnp->u.event.ewname, CN_DUP);
			ewlp = ewfp->u.name.last;
			ewfp->u.name.last = oldepname->u.name.last;
			ewlp->u.name.next = oldepname;
			oldepname->u.name.cp = cp;
			eventnp->u.event.epname = ewfp;

			outfl(O_ALTFP|O_VERB3|O_NONL, infop->anp->file,
			    infop->anp->line, "hmatch_full_config: ");
			ptree_name_iter(O_ALTFP|O_VERB3|O_NONL,
			    eventnp->u.event.epname);
			out(O_ALTFP|O_VERB3, NULL);

			/*
			 * Now complete hmatch.
			 */
			hmatch_event(infop, eventnp, oldepname->u.name.next,
			    config_child(cp), nextnp, 1);

			/*
			 * set everything back again
			 */
			oldepname->u.name.cp = ocp;
			iterinfop->num = -1;
			ewlp->u.name.next = NULL;
			ewfp->u.name.last = ewlp;
			tree_free(ewfp);
			tree_free(eventnp->u.event.ewname);
			eventnp->u.event.ewname = saved_ewname;
			eventnp->u.event.epname = saved_epname;
		}
		/*
		 * Try the next level down.
		 */
		hmatch_full_config(infop, eventnp,
		    oldepname, config_child(cp), nextnp, iterinfop);
	}
}

/*
 * hmatch_event -- perform any appropriate horizontal expansion on an event
 *
 * this routine is used to perform horizontal expansion on both the
 * left-hand-side events in a prop, and the right-hand-side events.
 * when called to handle a left-side event, nextnp point to the right
 * side of the prop that should be passed to hmatch() for each match
 * found by horizontal expansion.   when no horizontal expansion exists,
 * we will still "match" one event for every event found in the list on
 * the left-hand-side of the prop because vmatch() already found that
 * there's at least one match during vertical expansion.
 */
static void
hmatch_event(struct info *infop, struct node *eventnp, struct node *epname,
    struct config *ncp, struct node *nextnp, int rematch)
{
	if (epname == NULL) {
		/*
		 * end of pathname recursion, either we just located
		 * a left-hand-side event and we're ready to move on
		 * to the expanding the right-hand-side events, or
		 * we're further down the recursion and we just located
		 * a right-hand-side event.  the passed-in parameter
		 * "nextnp" tells us whether we're working on the left
		 * side and need to move on to nextnp, or if nextnp is
		 * NULL, we're working on the right side.
		 */
		if (nextnp) {
			/*
			 * finished a left side expansion, move on to right.
			 * tell generate() what event we just matched so
			 * it can be used at the source of any arrows
			 * we generate as we match events on the right side.
			 */
			generate_from(eventnp);
			hmatch(infop, nextnp, NULL);
		} else {
			/*
			 * finished a right side expansion.  tell generate
			 * the information about the destination and let
			 * it construct the arrows as appropriate.
			 */
			generate_to(eventnp);
			generate(infop);
		}

		return;
	}

	ASSERTeq(epname->t, T_NAME, ptree_nodetype2str);

	if (epname->u.name.cp == NULL)
		return;

	/*
	 * we only get here when eventnp already has a completely
	 * instanced epname in it already.  so we first recurse
	 * down to the end of the name and as the recursion pops
	 * up, we look for opportunities to advance horizontal
	 * expansions on to the next match.
	 */
	if (epname->u.name.it == IT_HORIZONTAL || rematch) {
		struct config *cp;
		struct config *ocp = epname->u.name.cp;
		char *cp_s;
		int cp_num;
		int ocp_num;
		struct iterinfo *iterinfop = NULL;
		const char *iters;
		int hexpand = 0;

		if (epname->u.name.it != IT_HORIZONTAL) {
			/*
			 * Ancestor was horizontal though, so must rematch
			 * against the name/num found in vmatch.
			 */
			config_getcompname(ocp, NULL, &ocp_num);
		} else {
			iters = epname->u.name.child->u.name.s;
			if ((iterinfop = lut_lookup(infop->ex,
			    (void *)iters, NULL)) == NULL) {
				/*
				 * do horizontal expansion on this node
				 */
				hexpand = 1;
				iterinfop = alloc_xmalloc(
				    sizeof (struct iterinfo));
				iterinfop->num = -1;
				iterinfop->np = epname;
				infop->ex = lut_add(infop->ex, (void *)iters,
				    iterinfop, NULL);
			} else if (iterinfop->num == -1) {
				hexpand = 1;
			} else {
				/*
				 * This name has already been used in a
				 * horizontal expansion. This time just match it
				 */
				ocp_num = iterinfop->num;
			}
		}
		/*
		 * handle case where this is the first section of oldepname
		 * and it is horizontally expanded. Instead of just looking for
		 * siblings, we want to scan the entire config tree for further
		 * matches.
		 */
		if (epname == eventnp->u.event.oldepname &&
		    epname->u.name.it == IT_HORIZONTAL) {
			/*
			 * Run through config looking for any that match the
			 * name.
			 */
			hmatch_full_config(infop, eventnp, epname,
			    infop->croot, nextnp, iterinfop);
			return;
		}

		/*
		 * Run through siblings looking for any that match the name.
		 * If hexpand not set then num must also match ocp_num.
		 */
		for (cp = rematch ? ncp : ocp; cp; cp = config_next(cp)) {
			config_getcompname(cp, &cp_s, &cp_num);
			if (cp_s == epname->u.name.s) {
				if (hexpand)
					iterinfop->num = cp_num;
				else if (ocp_num != cp_num)
					continue;
				epname->u.name.cp = cp;
				hmatch_event(infop, eventnp,
				    epname->u.name.next, config_child(cp),
				    nextnp, 1);
			}
		}
		epname->u.name.cp = ocp;
		if (hexpand)
			iterinfop->num = -1;
	} else {
		hmatch_event(infop, eventnp, epname->u.name.next,
		    NULL, nextnp, 0);
	}
}

/*
 * hmatch -- check for horizontal expansion matches
 *
 * np points to the things we're matching (like a T_LIST or a T_EVENT)
 * and if we're working on a left-side of a prop, nextnp points to
 * the other side of the prop that we'll tackle next when this recursion
 * bottoms out.  when all the events in the entire prop arrow have been
 * horizontally expanded, generate() will be called to generate the
 * actualy arrow.
 */
static void
hmatch(struct info *infop, struct node *np, struct node *nextnp)
{
	if (np == NULL)
		return;		/* all done */

	/*
	 * for each item in the list of events (which could just
	 * be a single event, or it could get larger in the loop
	 * below due to horizontal expansion), call hmatch on
	 * the right side and create arrows to each element.
	 */

	switch (np->t) {
	case T_LIST:
		/* loop through the list */
		if (np->u.expr.left)
			hmatch(infop, np->u.expr.left, nextnp);
		if (np->u.expr.right)
			hmatch(infop, np->u.expr.right, nextnp);
		break;

	case T_EVENT:
		hmatch_event(infop, np, np->u.event.epname,
		    NULL, nextnp, 0);
		break;

	default:
		outfl(O_DIE, np->file, np->line,
		    "hmatch: unexpected type: %s",
		    ptree_nodetype2str(np->t));
	}
}

static int
itree_np2nork(struct node *norknp)
{
	if (norknp == NULL)
		return (1);
	else if (norknp->t == T_NAME && norknp->u.name.s == L_A)
		return (-1);	/* our internal version of "all" */
	else if (norknp->t == T_NUM)
		return ((int)norknp->u.ull);
	else
		outfl(O_DIE, norknp->file, norknp->line,
		    "itree_np2nork: internal error type %s",
		    ptree_nodetype2str(norknp->t));
	/*NOTREACHED*/
	return (1);
}

static struct iterinfo *
newiterinfo(int num, struct node *np)
{
	struct iterinfo *ret = alloc_xmalloc(sizeof (*ret));

	ret->num = num;
	ret->np = np;
	return (ret);
}

/*ARGSUSED*/
static void
iterinfo_destructor(void *left, void *right, void *arg)
{
	struct iterinfo *iterinfop = (struct iterinfo *)right;

	alloc_xfree(iterinfop, sizeof (*iterinfop));
}

static void
vmatch_event(struct info *infop, struct config *cp, struct node *np,
	    struct node *lnp, struct node *anp, struct wildcardinfo *wcp)
{
	char *cp_s;
	int cp_num;
	struct node *ewlp, *ewfp;
	struct config *pcp;
	struct node *cpnode;
	int newewname = 0;

	/*
	 * handle case where the first section of the path name is horizontally
	 * expanded. The whole expansion is handled by hmatch on the first
	 * match here - so we just skip any subsequent matches here.
	 */
	if (wcp->got_wc_hz == 1)
		return;

	if (np == NULL) {
		/*
		 * Reached the end of the name. u.name.cp pointers should be set
		 * up for each part of name. From this we can use config tree
		 * to build up the wildcard part of the name (if any).
		 */
		pcp = config_parent(wcp->nptop->u.event.epname->u.name.cp);
		if (pcp == infop->croot) {
			/*
			 * no wildcarding done - move on to next entry
			 */
			wcp->nptop->u.event.ewname = wcp->ewname;
			wcp->nptop->u.event.oldepname = wcp->oldepname;
			vmatch(infop, np, lnp, anp);
			wcp->got_wc_hz = 0;
			return;
		}
		if (wcp->ewname == NULL) {
			/*
			 * ewname not yet set up - do it now
			 */
			newewname = 1;
			for (; pcp != infop->croot; pcp = config_parent(pcp)) {
				config_getcompname(pcp, &cp_s, &cp_num);
				cpnode = tree_name(cp_s, IT_NONE, NULL, 0);
				cpnode->u.name.child = newnode(T_NUM, NULL, 0);
				cpnode->u.name.child->u.ull = cp_num;
				cpnode->u.name.cp = pcp;
				if (wcp->ewname != NULL) {
					cpnode->u.name.next = wcp->ewname;
					cpnode->u.name.last =
					    wcp->ewname->u.name.last;
				}
				wcp->ewname = cpnode;
			}
		}

		/*
		 * dup ewname and append oldepname
		 */
		ewfp = tname_dup(wcp->ewname, CN_DUP);
		ewlp = ewfp->u.name.last;
		ewfp->u.name.last = wcp->oldepname->u.name.last;
		ewlp->u.name.next = wcp->oldepname;

		wcp->nptop->u.event.epname = ewfp;
		wcp->nptop->u.event.ewname = wcp->ewname;
		wcp->nptop->u.event.oldepname = wcp->oldepname;
		vmatch(infop, np, lnp, anp);
		wcp->got_wc_hz = 0;
		wcp->nptop->u.event.epname = wcp->oldepname;

		/*
		 * reduce duped ewname to original then free
		 */
		ewlp->u.name.next = NULL;
		ewfp->u.name.last = ewlp;
		tree_free(ewfp);

		if (newewname) {
			/*
			 * free ewname if allocated above
			 */
			tree_free(wcp->ewname);
			wcp->ewname = NULL;
		}
		return;
	}

	/*
	 * We have an np. See if we can match it in this section of
	 * the config tree.
	 */
	if (cp == NULL)
		return;	/* no more config to match against */

	for (; cp; cp = config_next(cp)) {
		config_getcompname(cp, &cp_s, &cp_num);

		if (cp_s == np->u.name.s) {
			/* found a matching component name */
			if (np->u.name.child &&
			    np->u.name.child->t == T_NUM) {
				/*
				 * an explicit instance number was given
				 * in the source.  so only consider this
				 * a configuration match if the number
				 * also matches.
				 */
				if (cp_num != np->u.name.child->u.ull)
					continue;

			} else if (np->u.name.it != IT_HORIZONTAL) {
				struct iterinfo *iterinfop;
				const char *iters;

				/*
				 * vertical iterator.  look it up in
				 * the appropriate lut and if we get
				 * back a value it is either one that we
				 * set earlier, in which case we record
				 * the new value for this iteration and
				 * keep matching, or it is one that was
				 * set by an earlier reference to the
				 * iterator, in which case we only consider
				 * this a configuration match if the number
				 * matches cp_num.
				 */

				ASSERT(np->u.name.child != NULL);
				ASSERT(np->u.name.child->t == T_NAME);
				iters = np->u.name.child->u.name.s;

				if ((iterinfop = lut_lookup(infop->ex,
				    (void *)iters, NULL)) == NULL) {
					/* we're the first use, record our np */
					infop->ex = lut_add(infop->ex,
					    (void *)iters,
					    newiterinfo(cp_num, np), NULL);
				} else if (np == iterinfop->np) {
					/*
					 * we're the first use, back again
					 * for another iteration.  so update
					 * the num bound to this iterator in
					 * the lut.
					 */
					iterinfop->num = cp_num;
				} else if (cp_num != iterinfop->num) {
					/*
					 * an earlier reference to this
					 * iterator bound it to a different
					 * instance number, so there's no
					 * match here after all.
					 *
					 * however, it's possible that this
					 * component should really be part of
					 * the wildcard.  we explore this by
					 * forcing this component into the
					 * wildcarded section.
					 *
					 * for an more details of what's
					 * going to happen now, see
					 * comments block below entitled
					 * "forcing components into
					 * wildcard path".
					 */
					if (np == wcp->nptop->u.event.epname)
						vmatch_event(infop,
						    config_child(cp), np, lnp,
						    anp, wcp);
					continue;
				}
			}

			/*
			 * if this was an IT_HORIZONTAL name, hmatch() will
			 * expand all matches horizontally into a list.
			 * we know the list will contain at least
			 * one element (the one we just matched),
			 * so we just let hmatch_event() do the rest.
			 *
			 * recurse on to next component. Note that
			 * wildcarding is now turned off.
			 */
			np->u.name.cp = cp;
			vmatch_event(infop, config_child(cp), np->u.name.next,
			    lnp, anp, wcp);
			np->u.name.cp = NULL;

			/*
			 * handle case where this is the first section of the
			 * path name and it is horizontally expanded.
			 * In this case we want all matching nodes in the config
			 * to be expanded horizontally - so set got_wc_hz and
			 * leave all further processing to hmatch.
			 */
			if (G.matched && np == wcp->nptop->u.event.epname &&
			    np->u.name.it == IT_HORIZONTAL)
				wcp->got_wc_hz = 1;

			/*
			 * forcing components into wildcard path:
			 *
			 * if this component is the first match, force it
			 * to be part of the wildcarded path and see if we
			 * can get additional matches.
			 *
			 * here's an example.  suppose we have the
			 * definition
			 *	event foo@x/y
			 * and configuration
			 *	a0/x0/y0/a1/x1/y1
			 *
			 * the code up to this point will treat "a0" as the
			 * wildcarded part of the path and "x0/y0" as the
			 * nonwildcarded part, resulting in the instanced
			 * event
			 *	foo@a0/x0/y0
			 *
			 * in order to discover the next match (.../x1/y1)
			 * in the configuration we have to force "x0" into
			 * the wildcarded part of the path.
			 * by doing so, we discover the wildcarded part
			 * "a0/x0/y0/a1" and the nonwildcarded part "x1/y1"
			 *
			 * the following call to vmatch_event() is also
			 * needed to properly handle the configuration
			 *	b0/x0/b1/x1/y1
			 *
			 * the recursions into vmatch_event() will start
			 * off uncovering "b0" as the wildcarded part and
			 * "x0" as the start of the nonwildcarded path.
			 * however, the next recursion will not result in a
			 * match since there is no "y" following "x0".  the
			 * subsequent match of (wildcard = "b0/x0/b1" and
			 * nonwildcard = "x1/y1") will be discovered only
			 * if "x0" is forced to be a part of the wildcarded
			 * path.
			 */
			if (np == wcp->nptop->u.event.epname)
				vmatch_event(infop, config_child(cp), np, lnp,
				    anp, wcp);

			if (np->u.name.it == IT_HORIZONTAL) {
				/*
				 * hmatch() finished iterating through
				 * the configuration as described above, so
				 * don't continue iterating here.
				 */
				return;
			}
		} else if (np == wcp->nptop->u.event.epname) {
			/*
			 * no match - carry on down the tree looking for
			 * wildcarding
			 */
			vmatch_event(infop, config_child(cp), np, lnp, anp,
			    wcp);
		}
	}
}

/*
 * vmatch -- find the next vertical expansion match in the config database
 *
 * this routine is called with three node pointers:
 *	 np -- the parse we're matching
 *	lnp -- the rest of the list we're currently working on
 *	anp -- the rest of the arrow we're currently working on
 *
 * the expansion matching happens via three types of recursion:
 *
 *	- when given an arrow, handle the left-side and then recursively
 *	  handle the right side (which might be another cascaded arrow).
 *
 *	- when handling one side of an arrow, recurse through the T_LIST
 *	  to get to each event (or just move on to the event if there
 *	  is a single event instead of a list)  since the arrow parse
 *	  trees recurse left, we actually start with the right-most
 *	  event list in the prop statement and work our way towards
 *	  the left-most event list.
 *
 *	- when handling an event, recurse down each component of the
 *	  pathname, matching in the config database and recording the
 *	  matches in the explicit iterator dictionary as we go.
 *
 * when the bottom of this matching recursion is met, meaning we have
 * set the "cp" pointers on all the names in the entire statement,
 * we call hmatch() which does it's own recursion to handle horizontal
 * expandsion and then call generate() to generate nodes, bubbles, and
 * arrows in the instance tree.  generate() looks at the cp pointers to
 * see what instance numbers were matched in the configuration database.
 *
 * when horizontal expansion appears, vmatch() finds only the first match
 * and hmatch() then takes the horizontal expansion through all the other
 * matches when generating the arrows in the instance tree.
 *
 * the "infop" passed down through the recursion contains a dictionary
 * of the explicit iterators (all the implicit iterators have been converted
 * to explicit iterators when the parse tree was created by tree.c), which
 * allows things like this to work correctly:
 *
 *	prop error.a@x[n]/y/z -> error.b@x/y[n]/z -> error.c@x/y/z[n];
 *
 * during the top level call, the explicit iterator "n" will match an
 * instance number in the config database, and the result will be recorded
 * in the explicit iterator dictionary and passed down via "infop".  so
 * when the recursive call tries to match y[n] in the config database, it
 * will only match the same instance number as x[n] did since the dictionary
 * is consulted to see if "n" took on a value already.
 *
 * at any point during the recursion, match*() can return to indicate
 * a match was not found in the config database and that the caller should
 * move on to the next potential match, if any.
 *
 * constraints are completely ignored by match(), so the statement:
 *
 *	prop error.a@x[n] -> error.b@x[n] {n != 0};
 *
 * might very well match x[0] if it appears in the config database.  it
 * is the generate() routine that takes that match and then decides what
 * arrow, if any, should be generated in the instance tree.  generate()
 * looks at the explicit iterator dictionary to get values like "n" in
 * the above example so that it can evaluate constraints.
 *
 */
static void
vmatch(struct info *infop, struct node *np, struct node *lnp, struct node *anp)
{
	struct node *np1, *np2, *oldepname, *oldnptop;
	int epmatches;
	struct config *cp;
	struct wildcardinfo *wcp;

	if (np == NULL) {
		G.matched = 1;
		if (lnp)
			vmatch(infop, lnp, NULL, anp);
		else if (anp)
			vmatch(infop, anp, NULL, NULL);
		else {
			struct node *src;
			struct node *dst;

			/* end of vertical match recursion */
			outfl(O_ALTFP|O_VERB3|O_NONL,
			    infop->anp->file, infop->anp->line, "vmatch: ");
			ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, infop->anp);
			out(O_ALTFP|O_VERB3, NULL);

			generate_nork(
			    itree_np2nork(infop->anp->u.arrow.nnp),
			    itree_np2nork(infop->anp->u.arrow.knp));
			dst = infop->anp->u.arrow.rhs;
			src = infop->anp->u.arrow.lhs;
			for (;;) {
				generate_new();	/* new set of arrows */
				if (src->t == T_ARROW) {
					hmatch(infop, src->u.arrow.rhs, dst);
					generate_nork(
					    itree_np2nork(src->u.arrow.nnp),
					    itree_np2nork(src->u.arrow.knp));
					dst = src->u.arrow.rhs;
					src = src->u.arrow.lhs;
				} else {
					hmatch(infop, src, dst);
					break;
				}
			}
		}
		return;
	}

	switch (np->t) {
	case T_EVENT: {
		epmatches = 0;
		/*
		 * see if we already have a match in the wcps
		 */
		for (wcp = wcproot; wcp; wcp = wcp->next) {
			oldepname = wcp->oldepname;
			oldnptop = wcp->nptop;
			for (np1 = oldepname, np2 = np->u.event.epname;
			    np1 != NULL && np2 != NULL; np1 = np1->u.name.next,
			    np2 = np2->u.name.next) {
				if (strcmp(np1->u.name.s, np2->u.name.s) != 0)
					break;
				if (np1->u.name.child->t !=
				    np2->u.name.child->t)
					break;
				if (np1->u.name.child->t == T_NUM &&
				    np1->u.name.child->u.ull !=
				    np2->u.name.child->u.ull)
					break;
				if (np1->u.name.child->t == T_NAME &&
				    strcmp(np1->u.name.child->u.name.s,
				    np2->u.name.child->u.name.s) != 0)
					break;
				epmatches++;
			}
			if (epmatches)
				break;
		}
		if (epmatches && np1 == NULL && np2 == NULL) {
			/*
			 * complete names match, can just borrow the fields
			 */
			oldepname = np->u.event.epname;
			np->u.event.epname = oldnptop->u.event.epname;
			np->u.event.oldepname = wcp->oldepname;
			np->u.event.ewname = wcp->ewname;
			vmatch(infop, NULL, lnp, anp);
			np->u.event.epname = oldepname;
			return;
		}
		G.matched = 0;
		if (epmatches) {
			/*
			 * just first part of names match - do wildcarding
			 * by using existing wcp including ewname and also
			 * copying as much of pwname as is valid, then start
			 * vmatch_event() at start of non-matching section
			 */
			for (np1 = oldepname, np2 = np->u.event.epname;
			    epmatches != 0; epmatches--) {
				cp = np1->u.name.cp;
				np2->u.name.cp = cp;
				np1 = np1->u.name.next;
				np2 = np2->u.name.next;
			}
			wcp->oldepname = np->u.event.epname;
			wcp->nptop = np;
			vmatch_event(infop, config_child(cp), np2, lnp,
			    anp, wcp);
			wcp->oldepname = oldepname;
			wcp->nptop = oldnptop;
			if (G.matched == 0) {
				/*
				 * This list entry is NULL. Move on to next item
				 * in the list.
				 */
				vmatch(infop, NULL, lnp, anp);
			}
			return;
		}
		/*
		 * names do not match - allocate a new wcp
		 */
		wcp = MALLOC(sizeof (struct wildcardinfo));
		wcp->next = wcproot;
		wcproot = wcp;
		wcp->nptop = np;
		wcp->oldepname = np->u.event.epname;
		wcp->ewname = NULL;
		wcp->got_wc_hz = 0;

		vmatch_event(infop, config_child(infop->croot),
		    np->u.event.epname, lnp, anp, wcp);

		wcproot = wcp->next;
		FREE(wcp);
		if (G.matched == 0) {
			/*
			 * This list entry is NULL. Move on to next item in the
			 * list.
			 */
			vmatch(infop, NULL, lnp, anp);
		}
		break;
	}
	case T_LIST:
		ASSERT(lnp == NULL);
		vmatch(infop, np->u.expr.right, np->u.expr.left, anp);
		break;

	case T_ARROW:
		ASSERT(lnp == NULL && anp == NULL);
		vmatch(infop, np->u.arrow.rhs, NULL, np->u.arrow.parent);
		break;

	default:
		outfl(O_DIE, np->file, np->line,
		    "vmatch: unexpected type: %s",
		    ptree_nodetype2str(np->t));
	}
}

static void
find_first_arrow(struct info *infop, struct node *anp)
{
	if (anp->u.arrow.lhs->t == T_ARROW) {
		anp->u.arrow.lhs->u.arrow.parent = anp;
		find_first_arrow(infop, anp->u.arrow.lhs);
	} else
		vmatch(infop, anp->u.arrow.lhs, NULL, anp);
}

static void
cp_reset(struct node *np)
{
	if (np == NULL)
		return;
	switch (np->t) {
	case T_NAME:
		np->u.name.cp = NULL;
		cp_reset(np->u.name.next);
		break;

	case T_LIST:
		cp_reset(np->u.expr.left);
		cp_reset(np->u.expr.right);
		break;

	case T_ARROW:
		cp_reset(np->u.arrow.lhs);
		cp_reset(np->u.arrow.rhs);
		break;

	case T_EVENT:
		cp_reset(np->u.event.epname);
		break;
	}
}

/*
 * itree_create -- apply the current config to the current parse tree
 *
 * returns a lut mapping fully-instance-qualified names to struct events.
 *
 */
struct lut *
itree_create(struct config *croot)
{
	struct lut *retval;
	struct node *propnp;
	extern int alloc_total();
	int init_size;

	Ninfo.lut = NULL;
	Ninfo.croot = croot;
	init_size = alloc_total();
	out(O_ALTFP|O_STAMP, "start itree_create using %d bytes", init_size);
	for (propnp = Props; propnp; propnp = propnp->u.stmt.next) {
		struct node *anp = propnp->u.stmt.np;

		ASSERTeq(anp->t, T_ARROW, ptree_nodetype2str);

		if (!anp->u.arrow.needed)
			continue;
		Ninfo.anp = anp;
		Ninfo.ex = NULL;

		generate_arrownp(anp);
		anp->u.arrow.parent = NULL;
		find_first_arrow(&Ninfo, anp);

		if (Ninfo.ex) {
			lut_free(Ninfo.ex, iterinfo_destructor, NULL);
			Ninfo.ex = NULL;
		}
		cp_reset(anp);
	}

	out(O_ALTFP|O_STAMP, "itree_create added %d bytes",
	    alloc_total() - init_size);
	retval = Ninfo.lut;
	Ninfo.lut = NULL;
	return (retval);
}

/*
 * initial first pass of the rules.
 * We don't use the config at all. Just check the last part of the pathname
 * in the rules. If this matches the last part of the pathname in the first
 * ereport, then set pathname to the pathname in the ereport. If not then
 * set pathname to just the last part of pathname with instance number 0.
 * Constraints are ignored and all nork values are set to 0. If after all that
 * any rules can still not be associated with the ereport, then they are set
 * to not needed in prune_propagations() and ignored in the real itree_create()
 * which follows.
 */

static struct event *
add_event_dummy(struct node *np, const struct ipath *ipp)
{
	struct event *ret;
	struct event searchevent;	/* just used for searching */
	extern struct ipath *ipath_dummy(struct node *, struct ipath *);
	struct ipath *ipp_un;
	extern struct ipath *ipath_for_usednames(struct node *);

	searchevent.enode = np;
	searchevent.ipp = ipath_dummy(np->u.event.epname, (struct ipath *)ipp);
	ipp_un = ipath_for_usednames(np->u.event.epname);
	if ((ret = lut_lookup(Ninfo.lut, (void *)&searchevent,
	    (lut_cmp)event_cmp)) != NULL)
		return (ret);

	ret = alloc_xmalloc(sizeof (*ret));
	bzero(ret, sizeof (*ret));
	ret->t = np->u.event.ename->u.name.t;
	ret->enode = np;
	ret->ipp = searchevent.ipp;
	ret->ipp_un = ipp_un;
	Ninfo.lut = lut_add(Ninfo.lut, (void *)ret, (void *)ret,
	    (lut_cmp)event_cmp);
	return (ret);
}

/*ARGSUSED*/
struct lut *
itree_create_dummy(const char *e0class, const struct ipath *e0ipp)
{
	struct node *propnp;
	struct event *frome, *toe;
	struct bubble *frombp, *tobp;
	struct arrow *arrowp;
	struct node *src, *dst, *slst, *dlst, *arrownp, *oldarrownp;
	int gen = 0;
	extern int alloc_total();
	int init_size;

	Ninfo.lut = NULL;
	init_size = alloc_total();
	out(O_ALTFP|O_STAMP, "start itree_create using %d bytes", init_size);
	for (propnp = Props; propnp; propnp = propnp->u.stmt.next) {
		arrownp = propnp->u.stmt.np;
		while (arrownp) {
			gen++;
			dlst = arrownp->u.arrow.rhs;
			slst = arrownp->u.arrow.lhs;
			oldarrownp = arrownp;
			if (slst->t == T_ARROW) {
				arrownp = slst;
				slst = slst->u.arrow.rhs;
			} else {
				arrownp = NULL;
			}
			while (slst) {
				if (slst->t == T_LIST) {
					src = slst->u.expr.right;
					slst = slst->u.expr.left;
				} else {
					src = slst;
					slst = NULL;
				}
				frome = add_event_dummy(src, e0ipp);
				frombp = itree_add_bubble(frome, B_FROM, 0, 0);
				while (dlst) {
					if (dlst->t == T_LIST) {
						dst = dlst->u.expr.right;
						dlst = dlst->u.expr.left;
					} else {
						dst = dlst;
						dlst = NULL;
					}
					arrowp = alloc_xmalloc(
					    sizeof (struct arrow));
					bzero(arrowp, sizeof (struct arrow));
					arrowp->pnode = oldarrownp;
					toe = add_event_dummy(dst, e0ipp);
					tobp = itree_add_bubble(toe, B_TO, 0,
					    gen);
					arrowp->tail = frombp;
					arrowp->head = tobp;
					add_arrow(frombp, arrowp);
					add_arrow(tobp, arrowp);
					arrow_add_within(arrowp,
					    dst->u.event.declp->u.stmt.np->
					    u.event.eexprlist);
					arrow_add_within(arrowp,
					    dst->u.event.eexprlist);
				}
			}
		}
	}
	out(O_ALTFP|O_STAMP, "itree_create added %d bytes",
	    alloc_total() - init_size);
	return (Ninfo.lut);
}

void
itree_free(struct lut *lutp)
{
	int init_size;

	init_size = alloc_total();
	out(O_ALTFP|O_STAMP, "start itree_free");
	lut_free(lutp, itree_destructor, NULL);
	out(O_ALTFP|O_STAMP, "itree_free freed %d bytes",
	    init_size - alloc_total());
}

void
itree_prune(struct lut *lutp)
{
	int init_size;

	init_size = alloc_total();
	out(O_ALTFP|O_STAMP, "start itree_prune");
	lut_walk(lutp, itree_pruner, NULL);
	out(O_ALTFP|O_STAMP, "itree_prune freed %d bytes",
	    init_size - alloc_total());
}

void
itree_pevent_brief(int flags, struct event *ep)
{
	ASSERT(ep != NULL);
	ASSERT(ep->enode != NULL);
	ASSERT(ep->ipp != NULL);

	ipath_print(flags, ep->enode->u.event.ename->u.name.s, ep->ipp);
}

/*ARGSUSED*/
static void
itree_pevent(struct event *lhs, struct event *ep, void *arg)
{
	struct plut_wlk_data propd;
	struct bubble *bp;
	int flags = (int)(intptr_t)arg;

	itree_pevent_brief(flags, ep);
	if (ep->t == N_EREPORT)
		out(flags, " (count %d)", ep->count);
	else
		out(flags, NULL);

	if (ep->props) {
		propd.flags = flags;
		propd.first = 1;
		out(flags, "Properties:");
		lut_walk(ep->props, ptree_plut, (void *)&propd);
	}

	for (bp = itree_next_bubble(ep, NULL); bp;
	    bp = itree_next_bubble(ep, bp)) {
		/* Print only TO bubbles in this loop */
		if (bp->t != B_TO)
			continue;
		itree_pbubble(flags, bp);
	}

	for (bp = itree_next_bubble(ep, NULL); bp;
	    bp = itree_next_bubble(ep, bp)) {
		/* Print only INHIBIT bubbles in this loop */
		if (bp->t != B_INHIBIT)
			continue;
		itree_pbubble(flags, bp);
	}

	for (bp = itree_next_bubble(ep, NULL); bp;
	    bp = itree_next_bubble(ep, bp)) {
		/* Print only FROM bubbles in this loop */
		if (bp->t != B_FROM)
			continue;
		itree_pbubble(flags, bp);
	}
}

static void
itree_pbubble(int flags, struct bubble *bp)
{
	struct constraintlist *cp;
	struct arrowlist *ap;

	ASSERT(bp != NULL);

	out(flags|O_NONL, "   ");
	if (bp->mark)
		out(flags|O_NONL, "*");
	else
		out(flags|O_NONL, " ");
	if (bp->t == B_FROM)
		out(flags|O_NONL, "N=%d to:", bp->nork);
	else if (bp->t == B_TO)
		out(flags|O_NONL, "K=%d from:", bp->nork);
	else
		out(flags|O_NONL, "K=%d masked from:", bp->nork);

	if (bp->t == B_TO || bp->t == B_INHIBIT) {
		for (ap = itree_next_arrow(bp, NULL); ap;
		    ap = itree_next_arrow(bp, ap)) {
			ASSERT(ap->arrowp->head == bp);
			ASSERT(ap->arrowp->tail != NULL);
			ASSERT(ap->arrowp->tail->myevent != NULL);
			out(flags|O_NONL, " ");
			itree_pevent_brief(flags, ap->arrowp->tail->myevent);
		}
		out(flags, NULL);
		return;
	}

	for (ap = itree_next_arrow(bp, NULL); ap;
	    ap = itree_next_arrow(bp, ap)) {
		ASSERT(ap->arrowp->tail == bp);
		ASSERT(ap->arrowp->head != NULL);
		ASSERT(ap->arrowp->head->myevent != NULL);

		out(flags|O_NONL, " ");
		itree_pevent_brief(flags, ap->arrowp->head->myevent);

		out(flags|O_NONL, " ");
		ptree_timeval(flags, &ap->arrowp->mindelay);
		out(flags|O_NONL, ",");
		ptree_timeval(flags, &ap->arrowp->maxdelay);

		/* Display anything from the propogation node? */
		out(O_VERB3|O_NONL, " <%s:%d>",
		    ap->arrowp->pnode->file, ap->arrowp->pnode->line);

		if (itree_next_constraint(ap->arrowp, NULL))
			out(flags|O_NONL, " {");

		for (cp = itree_next_constraint(ap->arrowp, NULL); cp;
		    cp = itree_next_constraint(ap->arrowp, cp)) {
			ptree(flags, cp->cnode, 1, 0);
			if (itree_next_constraint(ap->arrowp, cp))
				out(flags|O_NONL, ", ");
		}

		if (itree_next_constraint(ap->arrowp, NULL))
			out(flags|O_NONL, "}");
	}
	out(flags, NULL);
}

void
itree_ptree(int flags, struct lut *itp)
{
	lut_walk(itp, (lut_cb)itree_pevent, (void *)(intptr_t)flags);
}

/*ARGSUSED*/
static void
itree_destructor(void *left, void *right, void *arg)
{
	struct event *ep = (struct event *)right;
	struct bubble *nextbub, *bub;

	/* Free the properties */
	if (ep->props)
		lut_free(ep->props, instances_destructor, NULL);

	/* Free the payload properties */
	if (ep->payloadprops)
		lut_free(ep->payloadprops, payloadprops_destructor, NULL);

	/* Free the serd properties */
	if (ep->serdprops)
		lut_free(ep->serdprops, serdprops_destructor, NULL);

	/* Free my bubbles */
	for (bub = ep->bubbles; bub != NULL; ) {
		nextbub = bub->next;
		/*
		 * Free arrows if they are FROM me.  Free arrowlists on
		 * other types of bubbles (but not the attached arrows,
		 * which will be freed when we free the originating
		 * bubble.
		 */
		if (bub->t == B_FROM)
			itree_free_arrowlists(bub, 1);
		else
			itree_free_arrowlists(bub, 0);
		itree_free_bubble(bub);
		bub = nextbub;
	}

	if (ep->nvp != NULL)
		nvlist_free(ep->nvp);
	alloc_xfree(ep, sizeof (*ep));
}

/*ARGSUSED*/
static void
itree_pruner(void *left, void *right, void *arg)
{
	struct event *ep = (struct event *)right;
	struct bubble *nextbub, *bub;

	if (ep->keep_in_tree)
		return;

	/* Free the properties */
	lut_free(ep->props, instances_destructor, NULL);

	/* Free the payload properties */
	lut_free(ep->payloadprops, payloadprops_destructor, NULL);

	/* Free the serd properties */
	lut_free(ep->serdprops, serdprops_destructor, NULL);

	/* Free my bubbles */
	for (bub = ep->bubbles; bub != NULL; ) {
		nextbub = bub->next;
		itree_prune_arrowlists(bub);
		itree_free_bubble(bub);
		bub = nextbub;
	}

	if (ep->nvp != NULL)
		nvlist_free(ep->nvp);
	ep->props = NULL;
	ep->payloadprops = NULL;
	ep->serdprops = NULL;
	ep->bubbles = NULL;
	ep->nvp = NULL;
}

static void
itree_free_bubble(struct bubble *freeme)
{
	alloc_xfree(freeme, sizeof (*freeme));
}

static struct bubble *
itree_add_bubble(struct event *eventp, enum bubbletype btype, int nork, int gen)
{
	struct bubble *prev = NULL;
	struct bubble *curr;
	struct bubble *newb;

	/* Use existing bubbles as appropriate when possible */
	for (curr = eventp->bubbles;
	    curr != NULL;
	    prev = curr, curr = curr->next) {
		if (btype == B_TO && curr->t == B_TO) {
			/* see if an existing "to" bubble works for us */
			if (gen == curr->gen)
				return (curr);	/* matched gen number */
			else if (nork == 1 && curr->nork == 1) {
				curr->gen = gen;
				return (curr);	/* coalesce K==1 bubbles */
			}
		} else if (btype == B_FROM && curr->t == B_FROM) {
			/* see if an existing "from" bubble works for us */
			if ((nork == N_IS_ALL && curr->nork == N_IS_ALL) ||
			    (nork == 0 && curr->nork == 0))
				return (curr);
		}
	}

	newb = alloc_xmalloc(sizeof (struct bubble));
	newb->next = NULL;
	newb->t = btype;
	newb->myevent = eventp;
	newb->nork = nork;
	newb->mark = 0;
	newb->gen = gen;
	newb->arrows = NULL;

	if (prev == NULL)
		eventp->bubbles = newb;
	else
		prev->next = newb;

	return (newb);
}

struct bubble *
itree_next_bubble(struct event *eventp, struct bubble *last)
{
	struct bubble *next;

	for (;;) {
		if (last != NULL)
			next = last->next;
		else
			next = eventp->bubbles;

		if (next == NULL || next->arrows != NULL)
			return (next);

		/* bubble was empty, skip it */
		last = next;
	}
}

static void
add_arrow(struct bubble *bp, struct arrow *ap)
{
	struct arrowlist *prev = NULL;
	struct arrowlist *curr;
	struct arrowlist *newal;

	newal = alloc_xmalloc(sizeof (struct arrowlist));
	bzero(newal, sizeof (struct arrowlist));
	newal->arrowp = ap;

	curr = itree_next_arrow(bp, NULL);
	while (curr != NULL) {
		prev = curr;
		curr = itree_next_arrow(bp, curr);
	}

	if (prev == NULL)
		bp->arrows = newal;
	else
		prev->next = newal;
}

static struct arrow *
itree_add_arrow(struct node *apnode, struct node *fromevent,
    struct node *toevent, struct lut *ex)
{
	struct arrow *newa;

	newa = alloc_xmalloc(sizeof (struct arrow));
	bzero(newa, sizeof (struct arrow));
	newa->pnode = apnode;
	newa->constraints = NULL;

	/*
	 *  Set default delays, then try to re-set them from
	 *  any within() constraints.
	 */
	newa->mindelay = newa->maxdelay = 0ULL;
	if (itree_set_arrow_traits(newa, fromevent, toevent, ex) == 0) {
		alloc_xfree(newa, sizeof (struct arrow));
		return (NULL);
	}

	return (newa);
}

/* returns false if traits show that arrow should not be added after all */
static int
itree_set_arrow_traits(struct arrow *ap, struct node *fromev,
    struct node *toev, struct lut *ex)
{
	struct node *events[] = { NULL, NULL, NULL };
	struct node *newc = NULL;

	ASSERTeq(fromev->t, T_EVENT, ptree_nodetype2str);
	ASSERTeq(toev->t, T_EVENT, ptree_nodetype2str);

	/*
	 * search for the within values first on the declaration of
	 * the destination event, and then on the prop.  this allows
	 * one to specify a "default" within by putting it on the
	 * declaration,  but then allow overriding on the prop statement.
	 */
	arrow_add_within(ap, toev->u.event.declp->u.stmt.np->u.event.eexprlist);
	arrow_add_within(ap, toev->u.event.eexprlist);

	/*
	 * handle any global constraints inherited from the
	 * "fromev" event's declaration
	 */
	ASSERT(fromev->u.event.declp != NULL);
	ASSERT(fromev->u.event.declp->u.stmt.np != NULL);

#ifdef	notdef
	/* XXX not quite ready to evaluate constraints from decls yet */
	if (fromev->u.event.declp->u.stmt.np->u.event.eexprlist)
		(void) itree_add_constraint(ap,
		    fromev->u.event.declp->u.stmt.np->u.event.eexprlist);
#endif	/* notdef */

	/* handle constraints on the from event in the prop statement */
	events[0] = fromev;
	events[1] = toev;
	if (eval_potential(fromev->u.event.eexprlist, ex, events, &newc,
	    Ninfo.croot) == 0)
		return (0);		/* constraint disallows arrow */

	/*
	 * handle any global constraints inherited from the
	 * "toev" event's declaration
	 */
	ASSERT(toev->u.event.declp != NULL);
	ASSERT(toev->u.event.declp->u.stmt.np != NULL);

#ifdef	notdef
	/* XXX not quite ready to evaluate constraints from decls yet */
	if (toev->u.event.declp->u.stmt.np->u.event.eexprlist)
		(void) itree_add_constraint(ap,
		    toev->u.event.declp->u.stmt.np->u.event.eexprlist);
#endif	/* notdef */

	/* handle constraints on the to event in the prop statement */
	events[0] = toev;
	events[1] = fromev;
	if (eval_potential(toev->u.event.eexprlist, ex, events, &newc,
	    Ninfo.croot) == 0) {
		if (newc != NULL)
			tree_free(newc);
		return (0);		/* constraint disallows arrow */
	}

	/* if we came up with any deferred constraints, add them to arrow */
	if (newc != NULL) {
		out(O_ALTFP|O_VERB3, "(deferred constraints)");
		(void) itree_add_constraint(ap, iexpr(newc));
	}

	return (1);	/* constraints allow arrow */
}

/*
 * Set within() constraint.  If the constraint were set multiple times,
 * the last one would "win".
 */
static void
arrow_add_within(struct arrow *ap, struct node *xpr)
{
	struct node *arglist;

	/* end of expressions list */
	if (xpr == NULL)
		return;

	switch (xpr->t) {
	case T_LIST:
		arrow_add_within(ap, xpr->u.expr.left);
		arrow_add_within(ap, xpr->u.expr.right);
		return;
	case T_FUNC:
		if (xpr->u.func.s != L_within)
			return;
		arglist = xpr->u.func.arglist;
		switch (arglist->t) {
		case T_TIMEVAL:
			ap->mindelay = 0;
			ap->maxdelay = arglist->u.ull;
			break;
		case T_NAME:
			ASSERT(arglist->u.name.s == L_infinity);
			ap->mindelay = 0;
			ap->maxdelay = TIMEVAL_EVENTUALLY;
			break;
		case T_LIST:
			ASSERT(arglist->u.expr.left->t == T_TIMEVAL);
			ap->mindelay = arglist->u.expr.left->u.ull;
			switch (arglist->u.expr.right->t) {
			case T_TIMEVAL:
				ap->maxdelay = arglist->u.ull;
				break;
			case T_NAME:
				ASSERT(arglist->u.expr.right->u.name.s ==
				    L_infinity);
				ap->maxdelay = TIMEVAL_EVENTUALLY;
				break;
			default:
				out(O_DIE, "within: unexpected 2nd arg type");
			}
			break;
		default:
			out(O_DIE, "within: unexpected 1st arg type");
		}
		break;
	default:
		return;
	}
}

static void
itree_free_arrowlists(struct bubble *bubp, int arrows_too)
{
	struct arrowlist *al, *nal;

	al = bubp->arrows;
	while (al != NULL) {
		nal = al->next;
		if (arrows_too) {
			itree_free_constraints(al->arrowp);
			alloc_xfree(al->arrowp, sizeof (struct arrow));
		}
		alloc_xfree(al, sizeof (*al));
		al = nal;
	}
}

static void
itree_delete_arrow(struct bubble *bubp, struct arrow *arrow)
{
	struct arrowlist *al, *oal;

	al = bubp->arrows;
	if (al->arrowp == arrow) {
		bubp->arrows = al->next;
		alloc_xfree(al, sizeof (*al));
		return;
	}
	while (al != NULL) {
		oal = al;
		al = al->next;
		ASSERT(al != NULL);
		if (al->arrowp == arrow) {
			oal->next = al->next;
			alloc_xfree(al, sizeof (*al));
			return;
		}
	}
}

static void
itree_prune_arrowlists(struct bubble *bubp)
{
	struct arrowlist *al, *nal;

	al = bubp->arrows;
	while (al != NULL) {
		nal = al->next;
		if (bubp->t == B_FROM)
			itree_delete_arrow(al->arrowp->head, al->arrowp);
		else
			itree_delete_arrow(al->arrowp->tail, al->arrowp);
		itree_free_constraints(al->arrowp);
		alloc_xfree(al->arrowp, sizeof (struct arrow));
		alloc_xfree(al, sizeof (*al));
		al = nal;
	}
}

struct arrowlist *
itree_next_arrow(struct bubble *bubble, struct arrowlist *last)
{
	struct arrowlist *next;

	if (last != NULL)
		next = last->next;
	else
		next = bubble->arrows;
	return (next);
}

static struct constraintlist *
itree_add_constraint(struct arrow *arrowp, struct node *c)
{
	struct constraintlist *prev = NULL;
	struct constraintlist *curr;
	struct constraintlist *newc;

	for (curr = arrowp->constraints;
	    curr != NULL;
	    prev = curr, curr = curr->next)
		;

	newc = alloc_xmalloc(sizeof (struct constraintlist));
	newc->next = NULL;
	newc->cnode = c;

	if (prev == NULL)
		arrowp->constraints = newc;
	else
		prev->next = newc;

	return (newc);
}

struct constraintlist *
itree_next_constraint(struct arrow *arrowp, struct constraintlist *last)
{
	struct constraintlist *next;

	if (last != NULL)
		next = last->next;
	else
		next = arrowp->constraints;
	return (next);
}

static void
itree_free_constraints(struct arrow *ap)
{
	struct constraintlist *cl, *ncl;

	cl = ap->constraints;
	while (cl != NULL) {
		ncl = cl->next;
		ASSERT(cl->cnode != NULL);
		if (!iexpr_cached(cl->cnode))
			tree_free(cl->cnode);
		else
			iexpr_free(cl->cnode);
		alloc_xfree(cl, sizeof (*cl));
		cl = ncl;
	}
}

const char *
itree_bubbletype2str(enum bubbletype t)
{
	static char buf[100];

	switch (t) {
	case B_FROM:	return L_from;
	case B_TO:	return L_to;
	case B_INHIBIT:	return L_inhibit;
	default:
		(void) sprintf(buf, "[unexpected bubbletype: %d]", t);
		return (buf);
	}
}

/*
 * itree_fini -- clean up any half-built itrees
 */
void
itree_fini(void)
{
	if (Ninfo.lut != NULL) {
		itree_free(Ninfo.lut);
		Ninfo.lut = NULL;
	}
	if (Ninfo.ex) {
		lut_free(Ninfo.ex, iterinfo_destructor, NULL);
		Ninfo.ex = NULL;
	}
}