eversholt/common/tree.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 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * tree.c -- routines for manipulating the prop tree
 *
 * the actions in escparse.y call these routines to construct
 * the parse tree.  these routines, in turn, call the check_X()
 * routines for semantic checking.
 */

#pragma ident   "%Z%%M% %I% %E% SMI"

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <strings.h>
#include <alloca.h>
#include "alloc.h"
#include "out.h"
#include "stats.h"
#include "stable.h"
#include "literals.h"
#include "lut.h"
#include "esclex.h"
#include "tree.h"
#include "check.h"
#include "ptree.h"

static struct node *Root;

static char *Newname;

static struct stats *Faultcount;
static struct stats *Upsetcount;
static struct stats *Defectcount;
static struct stats *Errorcount;
static struct stats *Ereportcount;
static struct stats *SERDcount;
static struct stats *STATcount;
static struct stats *ASRUcount;
static struct stats *FRUcount;
static struct stats *Configcount;
static struct stats *Propcount;
static struct stats *Maskcount;
static struct stats *Nodecount;
static struct stats *Namecount;
static struct stats *Nodesize;

struct lut *Usedprops;

void
tree_init(void)
{
    Faultcount = stats_new_counter("parser.fault", "fault decls", 1);
    Upsetcount = stats_new_counter("parser.upset", "upset decls", 1);
    Defectcount = stats_new_counter("parser.defect", "defect decls", 1);
    Errorcount = stats_new_counter("parser.error", "error decls", 1);
    Ereportcount = stats_new_counter("parser.ereport", "ereport decls", 1);
    SERDcount = stats_new_counter("parser.SERD", "SERD engine decls", 1);
    STATcount = stats_new_counter("parser.STAT", "STAT engine decls", 1);
    ASRUcount = stats_new_counter("parser.ASRU", "ASRU decls", 1);
    FRUcount = stats_new_counter("parser.FRU", "FRU decls", 1);
    Configcount = stats_new_counter("parser.config", "config stmts", 1);
    Propcount = stats_new_counter("parser.prop", "prop stmts", 1);
    Maskcount = stats_new_counter("parser.mask", "mask stmts", 1);
    Nodecount = stats_new_counter("parser.node", "nodes created", 1);
    Namecount = stats_new_counter("parser.name", "names created", 1);
    Nodesize =
        stats_new_counter("parser.nodesize", "sizeof(struct node)", 1);
    stats_counter_add(Nodesize, sizeof (struct node));
}

void
tree_fini(void)
{
    stats_delete(Faultcount);
    stats_delete(Upsetcount);
    stats_delete(Defectcount);
    stats_delete(Errorcount);
    stats_delete(Ereportcount);
    stats_delete(SERDcount);
    stats_delete(STATcount);
    stats_delete(ASRUcount);
    stats_delete(FRUcount);
    stats_delete(Configcount);
    stats_delete(Propcount);
    stats_delete(Maskcount);
    stats_delete(Nodecount);
    stats_delete(Namecount);
    stats_delete(Nodesize);

    /* free entire parse tree */
    tree_free(Root);

    /* free up the luts we keep for decls */
    lut_free(Faults, NULL, NULL);
    Faults = NULL;
    lut_free(Upsets, NULL, NULL);
    Upsets = NULL;
    lut_free(Defects, NULL, NULL);
    Defects = NULL;
    lut_free(Errors, NULL, NULL);
    Errors = NULL;
    lut_free(Ereports, NULL, NULL);
    Ereports = NULL;
    lut_free(Ereportenames, NULL, NULL);
    Ereportenames = NULL;
    lut_free(Ereportenames_discard, NULL, NULL);
    Ereportenames_discard = NULL;
    lut_free(SERDs, NULL, NULL);
    SERDs = NULL;
    lut_free(STATs, NULL, NULL);
    STATs = NULL;
    lut_free(ASRUs, NULL, NULL);
    ASRUs = NULL;
    lut_free(FRUs, NULL, NULL);
    FRUs = NULL;
    lut_free(Configs, NULL, NULL);
    Configs = NULL;
    lut_free(Usedprops, NULL, NULL);
    Usedprops = NULL;

    Props = Lastprops = NULL;
    Masks = Lastmasks = NULL;
    Problems = Lastproblems = NULL;

    if (Newname != NULL) {
        FREE(Newname);
        Newname = NULL;
    }
}

/*ARGSUSED*/
static int
nodesize(enum nodetype t, struct node *ret)
{
    int size = sizeof (struct node);

    switch (t) {
    case T_NAME:
        size += sizeof (ret->u.name) - sizeof (ret->u);
        break;

    case T_GLOBID:
        size += sizeof (ret->u.globid) - sizeof (ret->u);
        break;

    case T_TIMEVAL:
    case T_NUM:
        size += sizeof (ret->u.ull) - sizeof (ret->u);
        break;

    case T_QUOTE:
        size += sizeof (ret->u.quote) - sizeof (ret->u);
        break;

    case T_FUNC:
        size += sizeof (ret->u.func) - sizeof (ret->u);
        break;

    case T_FAULT:
    case T_UPSET:
    case T_DEFECT:
    case T_ERROR:
    case T_EREPORT:
    case T_ASRU:
    case T_FRU:
    case T_SERD:
    case T_STAT:
    case T_CONFIG:
    case T_PROP:
    case T_MASK:
        size += sizeof (ret->u.stmt) - sizeof (ret->u);
        break;

    case T_EVENT:
        size += sizeof (ret->u.event) - sizeof (ret->u);
        break;

    case T_ARROW:
        size += sizeof (ret->u.arrow) - sizeof (ret->u);
        break;

    default:
        size += sizeof (ret->u.expr) - sizeof (ret->u);
        break;
    }
    return (size);
}

struct node *
newnode(enum nodetype t, const char *file, int line)
{
    struct node *ret = NULL;
    int size = nodesize(t, ret);

    ret = alloc_xmalloc(size);
    stats_counter_bump(Nodecount);
    bzero(ret, size);
    ret->t = t;
    ret->file = (file == NULL) ? "<nofile>" : file;
    ret->line = line;

    return (ret);
}

/*ARGSUSED*/
void
tree_free(struct node *root)
{
    if (root == NULL)
        return;

    switch (root->t) {
    case T_NAME:
        tree_free(root->u.name.child);
        tree_free(root->u.name.next);
        break;
    case T_FUNC:
        tree_free(root->u.func.arglist);
        break;
    case T_AND:
    case T_OR:
    case T_EQ:
    case T_NE:
    case T_ADD:
    case T_DIV:
    case T_MOD:
    case T_MUL:
    case T_SUB:
    case T_LT:
    case T_LE:
    case T_GT:
    case T_GE:
    case T_BITAND:
    case T_BITOR:
    case T_BITXOR:
    case T_BITNOT:
    case T_LSHIFT:
    case T_RSHIFT:
    case T_NVPAIR:
    case T_ASSIGN:
    case T_CONDIF:
    case T_CONDELSE:
    case T_LIST:
        tree_free(root->u.expr.left);
        tree_free(root->u.expr.right);
        break;
    case T_EVENT:
        tree_free(root->u.event.ename);
        tree_free(root->u.event.epname);
        tree_free(root->u.event.eexprlist);
        break;
    case T_NOT:
        tree_free(root->u.expr.left);
        break;
    case T_ARROW:
        tree_free(root->u.arrow.lhs);
        tree_free(root->u.arrow.nnp);
        tree_free(root->u.arrow.knp);
        tree_free(root->u.arrow.rhs);
        break;
    case T_PROP:
    case T_MASK:
        tree_free(root->u.stmt.np);
        break;
    case T_FAULT:
    case T_UPSET:
    case T_DEFECT:
    case T_ERROR:
    case T_EREPORT:
    case T_ASRU:
    case T_FRU:
    case T_SERD:
    case T_STAT:
    case T_CONFIG:
        tree_free(root->u.stmt.np);
        if (root->u.stmt.nvpairs)
            tree_free(root->u.stmt.nvpairs);
        if (root->u.stmt.lutp)
            lut_free(root->u.stmt.lutp, NULL, NULL);
        break;
    case T_TIMEVAL:
    case T_NUM:
    case T_QUOTE:
    case T_GLOBID:
    case T_NOTHING:
        break;
    default:
        out(O_DIE,
            "internal error: tree_free unexpected nodetype: %d",
            root->t);
        /*NOTREACHED*/
    }
    alloc_xfree((char *)root, nodesize(root->t, root));
}

static int
tree_treecmp(struct node *np1, struct node *np2, enum nodetype t,
        lut_cmp cmp_func)
{
    if (np1 == NULL || np2 == NULL)
        return (0);

    if (np1->t != np2->t)
        return (1);

    ASSERT(cmp_func != NULL);

    if (np1->t == t)
        return ((*cmp_func)(np1, np2));

    switch (np1->t) {
    case T_NAME:
        if (tree_treecmp(np1->u.name.child, np2->u.name.child, t,
            cmp_func))
            return (1);
        return (tree_treecmp(np1->u.name.next, np2->u.name.next, t,
            cmp_func));
        /*NOTREACHED*/
        break;
    case T_FUNC:
        return (tree_treecmp(np1->u.func.arglist, np2->u.func.arglist,
            t, cmp_func));
        /*NOTREACHED*/
        break;
    case T_AND:
    case T_OR:
    case T_EQ:
    case T_NE:
    case T_ADD:
    case T_DIV:
    case T_MOD:
    case T_MUL:
    case T_SUB:
    case T_LT:
    case T_LE:
    case T_GT:
    case T_GE:
    case T_BITAND:
    case T_BITOR:
    case T_BITXOR:
    case T_BITNOT:
    case T_LSHIFT:
    case T_RSHIFT:
    case T_NVPAIR:
    case T_ASSIGN:
    case T_CONDIF:
    case T_CONDELSE:
    case T_LIST:
        if (tree_treecmp(np1->u.expr.left, np2->u.expr.left, t,
            cmp_func))
            return (1);
        return (tree_treecmp(np1->u.expr.right, np2->u.expr.right, t,
            cmp_func));
        /*NOTREACHED*/
        break;
    case T_EVENT:
        if (tree_treecmp(np1->u.event.ename, np2->u.event.ename, t,
            cmp_func))
            return (1);
        if (tree_treecmp(np1->u.event.epname, np2->u.event.epname, t,
            cmp_func))
            return (1);
        return (tree_treecmp(np1->u.event.eexprlist,
            np2->u.event.eexprlist, t, cmp_func));
        /*NOTREACHED*/
        break;
    case T_NOT:
        return (tree_treecmp(np1->u.expr.left, np2->u.expr.left, t,
            cmp_func));
        /*NOTREACHED*/
        break;
    case T_ARROW:
        if (tree_treecmp(np1->u.arrow.lhs, np2->u.arrow.lhs, t,
            cmp_func))
            return (1);
        if (tree_treecmp(np1->u.arrow.nnp, np2->u.arrow.nnp, t,
            cmp_func))
            return (1);
        if (tree_treecmp(np1->u.arrow.knp, np2->u.arrow.knp, t,
            cmp_func))
            return (1);
        return (tree_treecmp(np1->u.arrow.rhs, np2->u.arrow.rhs, t,
            cmp_func));
        /*NOTREACHED*/
        break;
    case T_PROP:
    case T_MASK:
        return (tree_treecmp(np1->u.stmt.np, np2->u.stmt.np, t,
            cmp_func));
        /*NOTREACHED*/
        break;
    case T_FAULT:
    case T_UPSET:
    case T_DEFECT:
    case T_ERROR:
    case T_EREPORT:
    case T_ASRU:
    case T_FRU:
    case T_SERD:
    case T_STAT:
        if (tree_treecmp(np1->u.stmt.np, np2->u.stmt.np, t, cmp_func))
            return (1);
        return (tree_treecmp(np1->u.stmt.nvpairs, np2->u.stmt.nvpairs,
            t, cmp_func));
        /*NOTREACHED*/
        break;
    case T_TIMEVAL:
    case T_NUM:
    case T_QUOTE:
    case T_GLOBID:
    case T_NOTHING:
        break;
    default:
        out(O_DIE,
            "internal error: tree_treecmp unexpected nodetype: %d",
            np1->t);
        /*NOTREACHED*/
        break;
    }

    return (0);
}

struct node *
tree_root(struct node *np)
{
    if (np)
        Root = np;
    return (Root);
}

struct node *
tree_nothing(void)
{
    return (newnode(T_NOTHING, L_nofile, 0));
}

struct node *
tree_expr(enum nodetype t, struct node *left, struct node *right)
{
    struct node *ret;

    ASSERTinfo(left != NULL || right != NULL, ptree_nodetype2str(t));

    ret = newnode(t,
        (left) ? left->file : right->file,
        (left) ? left->line : right->line);

    ret->u.expr.left = left;
    ret->u.expr.right = right;

    check_expr(ret);

    return (ret);
}

/*
 * ename_compress -- convert event class name in to more space-efficient form
 *
 * this routine is called after the parser has completed an "ename", which
 * is that part of an event that contains the class name (like ereport.x.y.z).
 * after this routine gets done with the ename, two things are true:
 *   1. the ename uses only a single struct node
 *   2. ename->u.name.s contains the *complete* class name, dots and all,
 *      entered into the string table.
 *
 * so in addition to saving space by using fewer struct nodes, this routine
 * allows consumers of the fault tree to assume the ename is a single
 * string, rather than a linked list of strings.
 */
static struct node *
ename_compress(struct node *ename)
{
    char *buf;
    char *cp;
    int len = 0;
    struct node *np;

    if (ename == NULL)
        return (ename);

    ASSERT(ename->t == T_NAME);

    if (ename->u.name.next == NULL)
        return (ename); /* no compression to be applied here */

    for (np = ename; np != NULL; np = np->u.name.next) {
        ASSERT(np->t == T_NAME);
        len++;  /* room for '.' and final '\0' */
        len += strlen(np->u.name.s);
    }
    cp = buf = alloca(len);
    for (np = ename; np != NULL; np = np->u.name.next) {
        ASSERT(np->t == T_NAME);
        if (np != ename)
            *cp++ = '.';
        (void) strcpy(cp, np->u.name.s);
        cp += strlen(cp);
    }

    ename->u.name.s = stable(buf);
    tree_free(ename->u.name.next);
    ename->u.name.next = NULL;
    ename->u.name.last = ename;
    return (ename);
}

struct node *
tree_event(struct node *ename, struct node *epname, struct node *eexprlist)
{
    struct node *ret;

    ASSERT(ename != NULL);

    ret = newnode(T_EVENT, ename->file, ename->line);

    ret->u.event.ename = ename_compress(ename);
    ret->u.event.epname = epname;
    ret->u.event.eexprlist = eexprlist;

    check_event(ret);

    return (ret);
}

struct node *
tree_name(const char *s, enum itertype it, const char *file, int line)
{
    struct node *ret = newnode(T_NAME, file, line);

    ASSERT(s != NULL);

    stats_counter_bump(Namecount);
    ret->u.name.t = N_UNSPEC;
    ret->u.name.s = stable(s);
    ret->u.name.it = it;
    ret->u.name.last = ret;

    if (it == IT_ENAME) {
        /* PHASE2, possible optimization: convert to table driven */
        if (s == L_fault)
            ret->u.name.t = N_FAULT;
        else if (s == L_upset)
            ret->u.name.t = N_UPSET;
        else if (s == L_defect)
            ret->u.name.t = N_DEFECT;
        else if (s == L_error)
            ret->u.name.t = N_ERROR;
        else if (s == L_ereport)
            ret->u.name.t = N_EREPORT;
        else if (s == L_serd)
            ret->u.name.t = N_SERD;
        else if (s == L_stat)
            ret->u.name.t = N_STAT;
        else
            outfl(O_ERR, file, line, "unknown class: %s", s);
    }
    return (ret);
}

struct node *
tree_iname(const char *s, const char *file, int line)
{
    struct node *ret;
    char *ss;
    char *ptr;

    ASSERT(s != NULL && *s != '\0');

    ss = STRDUP(s);

    ptr = &ss[strlen(ss) - 1];
    if (!isdigit(*ptr)) {
        outfl(O_ERR, file, line,
            "instanced name expected (i.e. \"x0/y1\")");
        FREE(ss);
        return (tree_name(s, IT_NONE, file, line));
    }
    while (ptr > ss && isdigit(*(ptr - 1)))
        ptr--;

    ret = newnode(T_NAME, file, line);
    stats_counter_bump(Namecount);
    ret->u.name.child = tree_num(ptr, file, line);
    *ptr = '\0';
    ret->u.name.t = N_UNSPEC;
    ret->u.name.s = stable(ss);
    ret->u.name.it = IT_NONE;
    ret->u.name.last = ret;
    FREE(ss);

    return (ret);
}

struct node *
tree_globid(const char *s, const char *file, int line)
{
    struct node *ret = newnode(T_GLOBID, file, line);

    ASSERT(s != NULL);

    ret->u.globid.s = stable(s);

    return (ret);
}

struct node *
tree_name_append(struct node *np1, struct node *np2)
{
    ASSERT(np1 != NULL && np2 != NULL);

    if (np1->t != T_NAME)
        outfl(O_DIE, np1->file, np1->line,
            "tree_name_append: internal error (np1 type %d)", np1->t);
    if (np2->t != T_NAME)
        outfl(O_DIE, np2->file, np2->line,
            "tree_name_append: internal error (np2 type %d)", np2->t);

    ASSERT(np1->u.name.last != NULL);

    np1->u.name.last->u.name.next = np2;
    np1->u.name.last = np2;
    return (np1);
}

/*
 * tree_name_repairdash -- repair a class name that contained a dash
 *
 * this routine is called by the parser when a dash is encountered
 * in a class name.  the event protocol allows the dashes but our
 * lexer considers them a separate token (arithmetic minus).  an extra
 * rule in the parser catches this case and calls this routine to fixup
 * the last component of the class name (so far) by constructing the
 * new stable entry for a name including the dash.
 */
struct node *
tree_name_repairdash(struct node *np, const char *s)
{
    int len;
    char *buf;

    ASSERT(np != NULL && s != NULL);

    if (np->t != T_NAME)
        outfl(O_DIE, np->file, np->line,
            "tree_name_repairdash: internal error (np type %d)",
            np->t);

    ASSERT(np->u.name.last != NULL);

    len = strlen(np->u.name.last->u.name.s) + 1 + strlen(s) + 1;
    buf = MALLOC(len);
    (void) snprintf(buf, len, "%s-%s", np->u.name.last->u.name.s, s);
    np->u.name.last->u.name.s = stable(buf);
    FREE(buf);
    return (np);
}

struct node *
tree_name_repairdash2(const char *s, struct node *np)
{
    int len;
    char *buf;

    ASSERT(np != NULL && s != NULL);

    if (np->t != T_NAME)
        outfl(O_DIE, np->file, np->line,
            "tree_name_repairdash: internal error (np type %d)",
            np->t);

    ASSERT(np->u.name.last != NULL);

    len = strlen(np->u.name.last->u.name.s) + 1 + strlen(s) + 1;
    buf = MALLOC(len);
    (void) snprintf(buf, len, "%s-%s", s, np->u.name.last->u.name.s);
    np->u.name.last->u.name.s = stable(buf);
    FREE(buf);
    return (np);
}

struct node *
tree_name_iterator(struct node *np1, struct node *np2)
{
    ASSERT(np1 != NULL);
    ASSERT(np2 != NULL);
    ASSERTinfo(np1->t == T_NAME, ptree_nodetype2str(np1->t));

    np1->u.name.child = np2;

    check_name_iterator(np1);

    return (np1);
}

struct node *
tree_timeval(const char *s, const char *suffix, const char *file, int line)
{
    struct node *ret = newnode(T_TIMEVAL, file, line);
    const unsigned long long *ullp;

    ASSERT(s != NULL);
    ASSERT(suffix != NULL);

    if ((ullp = lex_s2ullp_lut_lookup(Timesuffixlut, suffix)) == NULL) {
        outfl(O_ERR, file, line,
            "unrecognized number suffix: %s", suffix);
        /* still construct a valid timeval node so parsing continues */
        ret->u.ull = 1;
    } else {
        ret->u.ull = (unsigned long long)strtoul(s, NULL, 0) * *ullp;
    }

    return (ret);
}

struct node *
tree_num(const char *s, const char *file, int line)
{
    struct node *ret = newnode(T_NUM, file, line);

    ret->u.ull = (unsigned long long)strtoul(s, NULL, 0);
    return (ret);
}

struct node *
tree_quote(const char *s, const char *file, int line)
{
    struct node *ret = newnode(T_QUOTE, file, line);

    ret->u.quote.s = stable(s);
    return (ret);
}

struct node *
tree_func(const char *s, struct node *np, const char *file, int line)
{
    struct node *ret = newnode(T_FUNC, file, line);
    const char *ptr;

    ret->u.func.s = s;
    ret->u.func.arglist = np;

    check_func(ret);

    /*
     * keep track of the properties we're interested in so we can ignore the
     * rest
     */
    if (strcmp(s, L_confprop) == 0 || strcmp(s, L_confprop_defined) == 0) {
        ptr = stable(np->u.expr.right->u.quote.s);
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
    } else if (strcmp(s, L_is_connected) == 0) {
        ptr = stable("connected");
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
        ptr = stable("CONNECTED");
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
    } else if (strcmp(s, L_is_type) == 0) {
        ptr = stable("type");
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
        ptr = stable("TYPE");
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
    } else if (strcmp(s, L_is_on) == 0) {
        ptr = stable("on");
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
        ptr = stable("ON");
        Usedprops = lut_add(Usedprops, (void *)ptr, (void *)ptr, NULL);
    }

    return (ret);
}

/*
 * given a list from a prop or mask statement or a function argument,
 * convert all iterators to explicit iterators by inventing appropriate
 * iterator names.
 */
static void
make_explicit(struct node *np, int eventonly)
{
    struct node *pnp;   /* component of pathname */
    struct node *pnp2;
    int count;
    static size_t namesz;

    if (Newname == NULL) {
        namesz = 200;
        Newname = MALLOC(namesz);
    }

    if (np == NULL)
        return;     /* all done */

    switch (np->t) {
        case T_ASSIGN:
        case T_CONDIF:
        case T_CONDELSE:
        case T_NE:
        case T_EQ:
        case T_LT:
        case T_LE:
        case T_GT:
        case T_GE:
        case T_BITAND:
        case T_BITOR:
        case T_BITXOR:
        case T_BITNOT:
        case T_LSHIFT:
        case T_RSHIFT:
        case T_LIST:
        case T_AND:
        case T_OR:
        case T_NOT:
        case T_ADD:
        case T_SUB:
        case T_MUL:
        case T_DIV:
        case T_MOD:
            make_explicit(np->u.expr.left, eventonly);
            make_explicit(np->u.expr.right, eventonly);
            break;

        case T_EVENT:
            make_explicit(np->u.event.epname, 0);
            make_explicit(np->u.event.eexprlist, 1);
            break;

        case T_FUNC:
            make_explicit(np->u.func.arglist, eventonly);
            break;

        case T_NAME:
            if (eventonly)
                return;
            for (pnp = np; pnp != NULL; pnp = pnp->u.name.next)
                if (pnp->u.name.child == NULL) {
                    /*
                     * found implicit iterator.  convert
                     * it to an explicit iterator by
                     * using the name of the component
                     * appended with '#' and the number
                     * of times we've seen this same
                     * component name in this path so far.
                     */
                    count = 0;
                    for (pnp2 = np; pnp2 != NULL;
                        pnp2 = pnp2->u.name.next)
                        if (pnp2 == pnp)
                            break;
                        else if (pnp2->u.name.s ==
                            pnp->u.name.s)
                            count++;

                    if (namesz < strlen(pnp->u.name.s) +
                        100) {
                        namesz = strlen(pnp->u.name.s) +
                            100;
                        FREE(Newname);
                        Newname = MALLOC(namesz);
                    }
                    /*
                     * made up interator name is:
                     *  name#ordinal
                     * or
                     *  name##ordinal
                     * the first one is used for vertical
                     * expansion, the second for horizontal.
                     * either way, the '#' embedded in
                     * the name makes it impossible to
                     * collide with an actual iterator
                     * given to us in the eversholt file.
                     */
                    (void) snprintf(Newname, namesz,
                        "%s#%s%d", pnp->u.name.s,
                        (pnp->u.name.it == IT_HORIZONTAL) ?
                        "#" : "", count);

                    pnp->u.name.child = tree_name(Newname,
                        IT_NONE, pnp->file, pnp->line);
                    pnp->u.name.childgen = 1;
                }
            break;
    }
}

struct node *
tree_pname(struct node *np)
{
    make_explicit(np, 0);
    return (np);
}

struct node *
tree_arrow(struct node *lhs, struct node *nnp, struct node *knp,
    struct node *rhs)
{
    struct node *ret;

    ASSERT(lhs != NULL || rhs != NULL);

    ret = newnode(T_ARROW,
        (lhs) ? lhs->file : rhs->file,
        (lhs) ? lhs->line : rhs->line);

    ret->u.arrow.lhs = lhs;
    ret->u.arrow.nnp = nnp;
    ret->u.arrow.knp = knp;
    ret->u.arrow.rhs = rhs;

    make_explicit(lhs, 0);
    make_explicit(rhs, 0);

    check_arrow(ret);

    return (ret);
}

static struct lut *
nvpair2lut(struct node *np, struct lut *lutp, enum nodetype t)
{
    if (np) {
        if (np->t == T_NVPAIR) {
            ASSERTeq(np->u.expr.left->t, T_NAME,
                ptree_nodetype2str);
            check_stmt_allowed_properties(t, np, lutp);
            lutp = tree_s2np_lut_add(lutp,
                np->u.expr.left->u.name.s, np->u.expr.right);
        } else if (np->t == T_LIST) {
            lutp = nvpair2lut(np->u.expr.left, lutp, t);
            lutp = nvpair2lut(np->u.expr.right, lutp, t);
        } else
            outfl(O_DIE, np->file, np->line,
                "internal error: nvpair2lut type %s",
                ptree_nodetype2str(np->t));
    }

    return (lutp);
}

struct lut *
tree_s2np_lut_add(struct lut *root, const char *s, struct node *np)
{
    return (lut_add(root, (void *)s, (void *)np, NULL));
}

struct node *
tree_s2np_lut_lookup(struct lut *root, const char *s)
{
    return (struct node *)lut_lookup(root, (void *)s, NULL);
}

struct lut *
tree_name2np_lut_add(struct lut *root, struct node *namep, struct node *np)
{
    return (lut_add(root, (void *)namep, (void *)np,
        (lut_cmp)tree_namecmp));
}

struct node *
tree_name2np_lut_lookup(struct lut *root, struct node *namep)
{
    return (struct node *)
        lut_lookup(root, (void *)namep, (lut_cmp)tree_namecmp);
}

struct node *
tree_name2np_lut_lookup_name(struct lut *root, struct node *namep)
{
    return (struct node *)
        lut_lookup_lhs(root, (void *)namep, (lut_cmp)tree_namecmp);
}

struct lut *
tree_event2np_lut_add(struct lut *root, struct node *enp, struct node *np)
{
    return (lut_add(root, (void *)enp, (void *)np, (lut_cmp)tree_eventcmp));
}

struct node *
tree_event2np_lut_lookup(struct lut *root, struct node *enp)
{
    return ((struct node *)
        lut_lookup(root, (void *)enp, (lut_cmp)tree_eventcmp));
}

struct node *
tree_event2np_lut_lookup_event(struct lut *root, struct node *enp)
{
    return ((struct node *)
        lut_lookup_lhs(root, (void *)enp, (lut_cmp)tree_eventcmp));
}

static struct node *
dodecl(enum nodetype t, const char *file, int line,
    struct node *np, struct node *nvpairs, struct lut **lutpp,
    struct stats *countp, int justpath)
{
    struct node *ret;
    struct node *decl;

    /* allocate parse tree node */
    ret = newnode(t, file, line);
    ret->u.stmt.np = np;
    ret->u.stmt.nvpairs = nvpairs;

    /*
     * the global lut pointed to by lutpp (Faults, Defects, Upsets,
     * Errors, Ereports, Serds, FRUs, or ASRUs) keeps the first decl.
     * if this isn't the first declr, we merge the
     * nvpairs into the first decl so we have a
     * merged table to look up properties from.
     * if this is the first time we've seen this fault,
     * we add it to the global lut and start lutp
     * off with any nvpairs from this declaration statement.
     */
    if (justpath && (decl = tree_name2np_lut_lookup(*lutpp, np)) == NULL) {
        /* this is the first time name is declared */
        stats_counter_bump(countp);
        *lutpp = tree_name2np_lut_add(*lutpp, np, ret);
        ret->u.stmt.lutp = nvpair2lut(nvpairs, NULL, t);
    } else if (!justpath &&
        (decl = tree_event2np_lut_lookup(*lutpp, np)) == NULL) {
        /* this is the first time event is declared */
        stats_counter_bump(countp);
        *lutpp = tree_event2np_lut_add(*lutpp, np, ret);
        ret->u.stmt.lutp = nvpair2lut(nvpairs, NULL, t);
    } else {
        /* was declared before, just add new nvpairs to its lutp */
        decl->u.stmt.lutp = nvpair2lut(nvpairs, decl->u.stmt.lutp, t);
    }

    return (ret);
}

/*ARGSUSED*/
static void
update_serd_refstmt(void *lhs, void *rhs, void *arg)
{
    struct node *serd;

    ASSERT(rhs != NULL);

    serd = tree_s2np_lut_lookup(((struct node *)rhs)->u.stmt.lutp,
        L_engine);
    if (serd == NULL)
        return;

    ASSERT(serd->t == T_EVENT);
    if (arg != NULL && tree_eventcmp(serd, (struct node *)arg) != 0)
        return;

    serd = tree_event2np_lut_lookup(SERDs, serd);
    if (serd != NULL)
        serd->u.stmt.flags |= STMT_REF;
}

struct node *
tree_decl(enum nodetype t, struct node *np, struct node *nvpairs,
    const char *file, int line)
{
    struct node *decl;
    struct node *ret;

    ASSERT(np != NULL);

    check_type_iterator(np);

    switch (t) {
    case T_EVENT:
        /* determine the type of event being declared */
        ASSERT(np->u.event.ename->t == T_NAME);
        switch (np->u.event.ename->u.name.t) {
        case N_FAULT:
            ret = dodecl(T_FAULT, file, line, np, nvpairs,
                &Faults, Faultcount, 0);

            /* increment serd statement reference */
            decl = tree_event2np_lut_lookup(Faults, np);
            update_serd_refstmt(NULL, decl, NULL);
            break;

        case N_UPSET:
            ret = dodecl(T_UPSET, file, line, np, nvpairs,
                &Upsets, Upsetcount, 0);

            /* increment serd statement reference */
            decl = tree_event2np_lut_lookup(Upsets, np);
            update_serd_refstmt(NULL, decl, NULL);
            break;

        case N_DEFECT:
            ret = dodecl(T_DEFECT, file, line, np, nvpairs,
                &Defects, Defectcount, 0);

            /* increment serd statement reference */
            decl = tree_event2np_lut_lookup(Defects, np);
            update_serd_refstmt(NULL, decl, NULL);
            break;

        case N_ERROR:
            ret = dodecl(T_ERROR, file, line, np, nvpairs,
                &Errors, Errorcount, 0);
            break;

        case N_EREPORT:
            ret = dodecl(T_EREPORT, file, line, np, nvpairs,
                &Ereports, Ereportcount, 0);
            /*
             * Keep a lut of just the enames, so that the DE
             * can subscribe to a uniqified list of event
             * classes.
             */
            Ereportenames =
                tree_name2np_lut_add(Ereportenames,
                np->u.event.ename, np);

            /*
             * Keep a lut of the enames (event classes) to
             * silently discard if we can't find a matching
             * configuration node when an ereport of of a given
             * class is received.  Such events are declaired
             * with 'discard_if_config_unknown=1'.
             */
            if (tree_s2np_lut_lookup(ret->u.stmt.lutp,
                L_discard_if_config_unknown)) {
                Ereportenames_discard = lut_add(
                    Ereportenames_discard,
                    (void *)np->u.event.ename->u.name.s,
                    (void *)np->u.event.ename->u.name.s, NULL);
            }
            break;

        default:
            outfl(O_ERR, file, line,
                "tree_decl: internal error, event name type %s",
                ptree_nametype2str(np->u.event.ename->u.name.t));
        }
        break;

    case T_ENGINE:
        /* determine the type of engine being declared */
        ASSERT(np->u.event.ename->t == T_NAME);
        switch (np->u.event.ename->u.name.t) {
        case N_SERD:
            ret = dodecl(T_SERD, file, line, np, nvpairs,
                &SERDs, SERDcount, 0);
            lut_walk(Upsets, update_serd_refstmt, np);
            break;

        case N_STAT:
            ret = dodecl(T_STAT, file, line, np, nvpairs,
                &STATs, STATcount, 0);
            break;

        default:
            outfl(O_ERR, file, line,
                "tree_decl: internal error, engine name type %s",
                ptree_nametype2str(np->u.event.ename->u.name.t));
        }
        break;
    case T_ASRU:
        ret = dodecl(T_ASRU, file, line, np, nvpairs,
            &ASRUs, ASRUcount, 1);
        break;

    case T_FRU:
        ret = dodecl(T_FRU, file, line, np, nvpairs,
            &FRUs, FRUcount, 1);
        break;

    case T_CONFIG:
        /*
         * config statements are different from above: they
         * are not merged at all (until the configuration cache
         * code does its own style of merging.  and the properties
         * are a free-for-all -- we don't check for allowed or
         * required config properties.
         */
        ret = newnode(T_CONFIG, file, line);
        ret->u.stmt.np = np;
        ret->u.stmt.nvpairs = nvpairs;
        ret->u.stmt.lutp = nvpair2lut(nvpairs, NULL, T_CONFIG);

        if (lut_lookup(Configs, np, (lut_cmp)tree_namecmp) == NULL)
            stats_counter_bump(Configcount);

        Configs = lut_add(Configs, (void *)np, (void *)ret, NULL);
        break;

    default:
        out(O_DIE, "tree_decl: internal error, type %s",
            ptree_nodetype2str(t));
    }

    return (ret);
}

/* keep backpointers in arrows to the prop they belong to (used for scoping) */
static void
set_arrow_prop(struct node *prop, struct node *np)
{
    if (np == NULL)
        return;

    if (np->t == T_ARROW) {
        np->u.arrow.prop = prop;
        set_arrow_prop(prop, np->u.arrow.lhs);
        /*
         * no need to recurse right or handle T_LIST since
         * T_ARROWs always cascade left and are at the top
         * of the parse tree.  (you can see this in the rule
         * for "propbody" in escparse.y.)
         */
    }
}

struct node *
tree_stmt(enum nodetype t, struct node *np, const char *file, int line)
{
    struct node *ret = newnode(t, file, line);
    struct node *pp;
    int inlist = 0;

    ret->u.stmt.np = np;

    switch (t) {
    case T_PROP:
        check_proplists(t, np);
        check_propnames(t, np, 0, 0);
        check_propscope(np);
        set_arrow_prop(ret, np);

        for (pp = Props; pp; pp = pp->u.stmt.next) {
            if (tree_treecmp(pp, ret, T_NAME,
                (lut_cmp)tree_namecmp) == 0) {
                inlist = 1;
                break;
            }
        }
        if (inlist == 0)
            stats_counter_bump(Propcount);

        /* "Props" is a linked list of all prop statements */
        if (Lastprops)
            Lastprops->u.stmt.next = ret;
        else
            Props = ret;
        Lastprops = ret;
        break;

    case T_MASK:
        check_proplists(t, np);
        check_propnames(t, np, 0, 0);
        check_propscope(np);
        set_arrow_prop(ret, np);

        for (pp = Masks; pp; pp = pp->u.stmt.next) {
            if (tree_treecmp(pp, ret, T_NAME,
                (lut_cmp)tree_namecmp) == 0) {
                inlist = 1;
                break;
            }
        }
        if (inlist == 0)
            stats_counter_bump(Maskcount);

        /* "Masks" is a linked list of all mask statements */
        if (Lastmasks)
            Lastmasks->u.stmt.next = ret;
        else
            Masks = ret;
        Lastmasks = ret;
        stats_counter_bump(Maskcount);
        break;

    default:
        outfl(O_DIE, np->file, np->line,
            "tree_stmt: internal error (t %d)", t);
    }

    return (ret);
}

void
tree_report()
{
    /*
     * The only declarations with required properties
     * currently are faults and serds. Make sure the
     * the declarations have the required properties.
     */
    lut_walk(Faults, (lut_cb)check_required_props, (void *)T_FAULT);
    lut_walk(Upsets, (lut_cb)check_required_props, (void *)T_UPSET);
    lut_walk(Errors, (lut_cb)check_required_props, (void *)T_ERROR);
    lut_walk(Ereports, (lut_cb)check_required_props, (void *)T_EREPORT);
    lut_walk(SERDs, (lut_cb)check_required_props, (void *)T_SERD);
    lut_walk(STATs, (lut_cb)check_required_props, (void *)T_STAT);

    /*
     * we do this now rather than while building the parse
     * tree because it is inconvenient for the user if we
     * require SERD engines to be declared before used in
     * an upset "engine" property.
     */
    lut_walk(Faults, (lut_cb)check_refcount, (void *)T_FAULT);
    lut_walk(Faults, (lut_cb)check_upset_engine, (void *)T_FAULT);
    lut_walk(Defects, (lut_cb)check_upset_engine, (void *)T_DEFECT);
    lut_walk(Upsets, (lut_cb)check_upset_engine, (void *)T_UPSET);
    lut_walk(Upsets, (lut_cb)check_refcount, (void *)T_UPSET);
    lut_walk(Errors, (lut_cb)check_refcount, (void *)T_ERROR);
    lut_walk(Ereports, (lut_cb)check_refcount, (void *)T_EREPORT);
    lut_walk(SERDs, (lut_cb)check_refcount, (void *)T_SERD);

    /* check for cycles */
    lut_walk(Errors, (lut_cb)check_cycle, (void *)0);
}

/* compare two T_NAMES by only looking at components, not iterators */
int
tree_namecmp(struct node *np1, struct node *np2)
{
    ASSERT(np1 != NULL);
    ASSERT(np2 != NULL);
    ASSERTinfo(np1->t == T_NAME, ptree_nodetype2str(np1->t));
    ASSERTinfo(np2->t == T_NAME, ptree_nodetype2str(np1->t));

    while (np1 && np2 && np1->u.name.s == np2->u.name.s) {
        np1 = np1->u.name.next;
        np2 = np2->u.name.next;
    }
    if (np1 == NULL)
        if (np2 == NULL)
            return (0);
        else
            return (-1);
    else if (np2 == NULL)
        return (1);
    else
        return (np2->u.name.s - np1->u.name.s);
}

int
tree_eventcmp(struct node *np1, struct node *np2)
{
    int ret;

    ASSERT(np1 != NULL);
    ASSERT(np2 != NULL);
    ASSERTinfo(np1->t == T_EVENT, ptree_nodetype2str(np1->t));
    ASSERTinfo(np2->t == T_EVENT, ptree_nodetype2str(np2->t));

    if ((ret = tree_namecmp(np1->u.event.ename,
        np2->u.event.ename)) == 0) {
            if (np1->u.event.epname == NULL &&
                np2->u.event.epname == NULL)
                return (0);
            else if (np1->u.event.epname == NULL)
                return (-1);
            else if (np2->u.event.epname == NULL)
                return (1);
            else
                return tree_namecmp(np1->u.event.epname,
                    np2->u.event.epname);
    } else
    return (ret);
}