1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 
  22 /*
  23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  *
  26  * itree.c -- instance tree creation and manipulation
  27  *
  28  * this module provides the instance tree
  29  */
  30 
  31 #include <stdio.h>
  32 #include <ctype.h>
  33 #include <string.h>
  34 #include <strings.h>
  35 #include "alloc.h"
  36 #include "out.h"
  37 #include "stable.h"
  38 #include "literals.h"
  39 #include "lut.h"
  40 #include "tree.h"
  41 #include "ptree.h"
  42 #include "itree.h"
  43 #include "ipath.h"
  44 #include "iexpr.h"
  45 #include "eval.h"
  46 #include "config.h"
  47 
  48 /*
  49  * struct info contains the state we keep when expanding a prop statement
  50  * as part of constructing the instance tree.  state kept in struct info
  51  * is the non-recursive stuff -- the stuff that doesn't need to be on
  52  * the stack.  the rest of the state that is passed between all the
  53  * mutually recursive functions, is required to be on the stack since
  54  * we need to backtrack and recurse as we do the instance tree construction.
  55  */
  56 struct info {
  57         struct lut *lut;
  58         struct node *anp;       /* arrow np */
  59         struct lut *ex;         /* dictionary of explicit iterators */
  60         struct config *croot;
  61 } Ninfo;
  62 
  63 /*
  64  * struct wildcardinfo is used to track wildcarded portions of paths.
  65  *
  66  * for example, if the epname of an event is "c/d" and the path "a/b/c/d"
  67  * exists, the wildcard path ewname is filled in with the path "a/b".  when
  68  * matching is done, epname is temporarily replaced with the concatenation
  69  * of ewname and epname.
  70  *
  71  * a linked list of these structs is used to track the expansion of each
  72  * event node as it is processed in vmatch() --> vmatch_event() calls.
  73  */
  74 struct wildcardinfo {
  75         struct node *nptop;             /* event node fed to vmatch */
  76         struct node *oldepname;         /* epname without the wildcard part */
  77         struct node *ewname;            /* wildcard path */
  78         int got_wc_hz;
  79         struct wildcardinfo *next;
  80 };
  81 
  82 static struct wildcardinfo *wcproot = NULL;
  83 
  84 static void vmatch(struct info *infop, struct node *np, struct node *lnp,
  85     struct node *anp);
  86 static void hmatch(struct info *infop, struct node *np, struct node *nextnp);
  87 static void hmatch_event(struct info *infop, struct node *eventnp,
  88     struct node *epname, struct config *ncp, struct node *nextnp, int rematch);
  89 static void itree_pbubble(int flags, struct bubble *bp);
  90 static void itree_pruner(void *left, void *right, void *arg);
  91 static void itree_destructor(void *left, void *right, void *arg);
  92 static int itree_set_arrow_traits(struct arrow *ap, struct node *fromev,
  93     struct node *toev, struct lut *ex);
  94 static void itree_free_arrowlists(struct bubble *bubp, int arrows_too);
  95 static void itree_prune_arrowlists(struct bubble *bubp);
  96 static void arrow_add_within(struct arrow *ap, struct node *xpr);
  97 static struct arrow *itree_add_arrow(struct node *apnode,
  98     struct node *fromevent, struct node *toevent, struct lut *ex);
  99 static struct event *find_or_add_event(struct info *infop, struct node *np);
 100 static void add_arrow(struct bubble *bp, struct arrow *ap);
 101 static struct constraintlist *itree_add_constraint(struct arrow *arrowp,
 102     struct node *c);
 103 static struct bubble *itree_add_bubble(struct event *eventp,
 104     enum bubbletype btype, int nork, int gen);
 105 static void itree_free_bubble(struct bubble *freeme);
 106 static void itree_free_constraints(struct arrow *ap);
 107 
 108 /*
 109  * the following struct contains the state we build up during
 110  * vertical and horizontal expansion so that generate()
 111  * has everything it needs to construct the appropriate arrows.
 112  * after setting up the state by calling:
 113  *      generate_arrownp()
 114  *      generate_nork()
 115  *      generate_new()
 116  *      generate_from()
 117  *      generate_to()
 118  * the actual arrow generation is done by calling:
 119  *      generate()
 120  */
 121 static struct {
 122         int generation;         /* generation number of arrow set */
 123         int matched;            /* number of matches */
 124         struct node *arrownp;   /* top-level parse tree for arrow */
 125         int n;                  /* n value associated with arrow */
 126         int k;                  /* k value associated with arrow */
 127         struct node *fromnp;    /* left-hand-side event in parse tree */
 128         struct node *tonp;      /* right-hand-side event in parse tree */
 129         struct event *frome;    /* left-hand-side event in instance tree */
 130         struct event *toe;      /* right-hand-side event in instance tree */
 131         struct bubble *frombp;  /* bubble arrow comes from */
 132         struct bubble *tobp;    /* bubble arrow goes to */
 133 } G;
 134 
 135 static void
 136 generate_arrownp(struct node *arrownp)
 137 {
 138         G.arrownp = arrownp;
 139 }
 140 
 141 static void
 142 generate_nork(int n, int k)
 143 {
 144         G.n = n;
 145         G.k = k;
 146 }
 147 
 148 static void
 149 generate_new(void)
 150 {
 151         G.generation++;
 152 }
 153 
 154 static void
 155 generate_from(struct node *fromeventnp)
 156 {
 157         G.frombp = NULL;
 158         G.fromnp = fromeventnp;
 159 }
 160 
 161 static void
 162 generate_to(struct node *toeventnp)
 163 {
 164         G.tonp = toeventnp;
 165 }
 166 
 167 static void
 168 generate(struct info *infop)
 169 {
 170         struct arrow *arrowp;
 171 
 172         ASSERT(G.arrownp != NULL);
 173         ASSERT(G.fromnp != NULL);
 174         ASSERT(G.tonp != NULL);
 175 
 176         out(O_ALTFP|O_VERB3|O_NONL, "        Arrow \"");
 177         ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, G.fromnp);
 178         out(O_ALTFP|O_VERB3|O_NONL, "\" -> \"");
 179         ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, G.tonp);
 180         out(O_ALTFP|O_VERB3|O_NONL, "\" ");
 181 
 182         arrowp = itree_add_arrow(G.arrownp, G.fromnp, G.tonp, infop->ex);
 183         if (arrowp == NULL) {
 184                 out(O_ALTFP|O_VERB3, "(prevented by constraints)");
 185         } else {
 186                 out(O_ALTFP|O_VERB3, "");
 187                 if (!G.frombp) {
 188                         G.frome = find_or_add_event(infop, G.fromnp);
 189                         G.frombp = itree_add_bubble(G.frome, B_FROM, G.n, 0);
 190                 }
 191                 G.toe = find_or_add_event(infop, G.tonp);
 192                 G.tobp = itree_add_bubble(G.toe, B_TO, G.k, G.generation);
 193                 arrowp->tail = G.frombp;
 194                 arrowp->head = G.tobp;
 195                 add_arrow(G.frombp, arrowp);
 196                 add_arrow(G.tobp, arrowp);
 197         }
 198 }
 199 
 200 enum childnode_action {
 201         CN_NONE,
 202         CN_DUP
 203 };
 204 
 205 static struct node *
 206 tname_dup(struct node *namep, enum childnode_action act)
 207 {
 208         struct node *retp = NULL;
 209         const char *file;
 210         int line;
 211 
 212         if (namep == NULL)
 213                 return (NULL);
 214 
 215         file = namep->file;
 216         line = namep->line;
 217 
 218         for (; namep != NULL; namep = namep->u.name.next) {
 219                 struct node *newnp = newnode(T_NAME, file, line);
 220 
 221                 newnp->u.name.t = namep->u.name.t;
 222                 newnp->u.name.s = namep->u.name.s;
 223                 newnp->u.name.last = newnp;
 224                 newnp->u.name.it = namep->u.name.it;
 225                 newnp->u.name.cp = namep->u.name.cp;
 226 
 227                 if (act == CN_DUP) {
 228                         struct node *npc;
 229 
 230                         npc = namep->u.name.child;
 231                         if (npc != NULL) {
 232                                 switch (npc->t) {
 233                                 case T_NUM:
 234                                         newnp->u.name.child =
 235                                             newnode(T_NUM, file, line);
 236                                         newnp->u.name.child->u.ull =
 237                                             npc->u.ull;
 238                                         break;
 239                                 case T_NAME:
 240                                         newnp->u.name.child =
 241                                             tree_name(npc->u.name.s,
 242                                             npc->u.name.it, file, line);
 243                                         break;
 244                                 default:
 245                                         out(O_DIE, "tname_dup: "
 246                                             "invalid child type %s",
 247                                             ptree_nodetype2str(npc->t));
 248                                 }
 249                         }
 250                 }
 251 
 252                 if (retp == NULL) {
 253                         retp = newnp;
 254                 } else {
 255                         retp->u.name.last->u.name.next = newnp;
 256                         retp->u.name.last = newnp;
 257                 }
 258         }
 259 
 260         return (retp);
 261 }
 262 
 263 struct prop_wlk_data {
 264         struct lut *props;
 265         struct node *epname;
 266 };
 267 
 268 static struct lut *props2instance(struct node *, struct node *);
 269 
 270 /*
 271  * let oldepname be a subset of epname.  return the subsection of epname
 272  * that ends with oldepname.  make each component in the path explicitly
 273  * instanced (i.e., with a T_NUM child).
 274  */
 275 static struct node *
 276 tname_dup_to_epname(struct node *oldepname, struct node *epname)
 277 {
 278         struct node *npref, *npend, *np1, *np2;
 279         struct node *ret = NULL;
 280         int foundmatch = 0;
 281 
 282         if (epname == NULL)
 283                 return (NULL);
 284 
 285         /*
 286          * search for the longest path in epname which contains
 287          * oldnode->u.event.epname.  set npend to point to just past the
 288          * end of this path.
 289          */
 290         npend = NULL;
 291         for (npref = epname; npref; npref = npref->u.name.next) {
 292                 if (npref->u.name.s == oldepname->u.name.s) {
 293                         for (np1 = npref, np2 = oldepname;
 294                             np1 != NULL && np2 != NULL;
 295                             np1 = np1->u.name.next, np2 = np2->u.name.next) {
 296                                 if (np1->u.name.s != np2->u.name.s)
 297                                         break;
 298                         }
 299                         if (np2 == NULL) {
 300                                 foundmatch = 1;
 301                                 npend = np1;
 302                                 if (np1 == NULL) {
 303                                         /* oldepname matched npref up to end */
 304                                         break;
 305                                 }
 306                         }
 307                 }
 308         }
 309 
 310         if (foundmatch == 0) {
 311                 /*
 312                  * if oldepname could not be found in epname, return a
 313                  * duplicate of the former.  do not try to instantize
 314                  * oldepname since it might not be a path.
 315                  */
 316                 return (tname_dup(oldepname, CN_DUP));
 317         }
 318 
 319         /*
 320          * dup (epname -- npend).  all children should be T_NUMs.
 321          */
 322         for (npref = epname;
 323             ! (npref == NULL || npref == npend);
 324             npref = npref->u.name.next) {
 325                 struct node *newnp = newnode(T_NAME, oldepname->file,
 326                     oldepname->line);
 327 
 328                 newnp->u.name.t = npref->u.name.t;
 329                 newnp->u.name.s = npref->u.name.s;
 330                 newnp->u.name.last = newnp;
 331                 newnp->u.name.it = npref->u.name.it;
 332                 newnp->u.name.cp = npref->u.name.cp;
 333 
 334                 newnp->u.name.child = newnode(T_NUM, oldepname->file,
 335                     oldepname->line);
 336 
 337                 if (npref->u.name.child == NULL ||
 338                     npref->u.name.child->t != T_NUM) {
 339                         int childnum;
 340 
 341                         ASSERT(npref->u.name.cp != NULL);
 342                         config_getcompname(npref->u.name.cp, NULL, &childnum);
 343                         newnp->u.name.child->u.ull = childnum;
 344                 } else {
 345                         newnp->u.name.child->u.ull =
 346                             npref->u.name.child->u.ull;
 347                 }
 348 
 349                 if (ret == NULL) {
 350                         ret = newnp;
 351                 } else {
 352                         ret->u.name.last->u.name.next = newnp;
 353                         ret->u.name.last = newnp;
 354                 }
 355         }
 356 
 357         return (ret);
 358 }
 359 
 360 /*
 361  * restriction: oldnode->u.event.epname has to be equivalent to or a subset
 362  * of epname
 363  */
 364 static struct node *
 365 tevent_dup_to_epname(struct node *oldnode, struct node *epname)
 366 {
 367         struct node *ret;
 368 
 369         ret = newnode(T_EVENT, oldnode->file, oldnode->line);
 370         ret->u.event.ename = tname_dup(oldnode->u.event.ename, CN_NONE);
 371         ret->u.event.epname = tname_dup_to_epname(oldnode->u.event.epname,
 372             epname);
 373         return (ret);
 374 }
 375 
 376 static void
 377 nv_instantiate(void *name, void *val, void *arg)
 378 {
 379         struct prop_wlk_data *pd = (struct prop_wlk_data *)arg;
 380         struct node *orhs = (struct node *)val;
 381         struct node *nrhs;
 382 
 383         /* handle engines by instantizing the entire engine */
 384         if (name == L_engine) {
 385                 ASSERT(orhs->t == T_EVENT);
 386                 ASSERT(orhs->u.event.ename->u.name.t == N_SERD);
 387 
 388                 /* there are only SERD engines for now */
 389 
 390                 nrhs = newnode(T_SERD, orhs->file, orhs->line);
 391                 nrhs->u.stmt.np = tevent_dup_to_epname(orhs, pd->epname);
 392                 nrhs->u.stmt.lutp = props2instance(orhs, pd->epname);
 393                 pd->props = lut_add(pd->props, name, nrhs, NULL);
 394                 return;
 395         }
 396 
 397         switch (orhs->t) {
 398         case T_NUM:
 399                 nrhs = newnode(T_NUM, orhs->file, orhs->line);
 400                 nrhs->u.ull = orhs->u.ull;
 401                 pd->props = lut_add(pd->props, name, nrhs, NULL);
 402                 break;
 403         case T_TIMEVAL:
 404                 nrhs = newnode(T_TIMEVAL, orhs->file, orhs->line);
 405                 nrhs->u.ull = orhs->u.ull;
 406                 pd->props = lut_add(pd->props, name, nrhs, NULL);
 407                 break;
 408         case T_NAME:
 409                 nrhs = tname_dup_to_epname(orhs, pd->epname);
 410                 pd->props = lut_add(pd->props, name, nrhs, NULL);
 411                 break;
 412         case T_EVENT:
 413                 nrhs = tevent_dup_to_epname(orhs, pd->epname);
 414                 pd->props = lut_add(pd->props, name, nrhs, NULL);
 415                 break;
 416         case T_GLOBID:
 417                 nrhs = newnode(T_GLOBID, orhs->file, orhs->line);
 418                 nrhs->u.globid.s = orhs->u.globid.s;
 419                 pd->props = lut_add(pd->props, name, nrhs, NULL);
 420                 break;
 421         case T_FUNC:
 422                 /* for T_FUNC, we don't duplicate it, just point to node */
 423                 pd->props = lut_add(pd->props, name, orhs, NULL);
 424                 break;
 425         default:
 426                 out(O_DIE, "unexpected nvpair value type %s",
 427                     ptree_nodetype2str(((struct node *)val)->t));
 428         }
 429 }
 430 
 431 static struct lut *
 432 props2instance(struct node *eventnp, struct node *epname)
 433 {
 434         struct prop_wlk_data pd;
 435 
 436         pd.props = NULL;
 437         pd.epname = epname;
 438 
 439         ASSERT(eventnp->u.event.declp != NULL);
 440         lut_walk(eventnp->u.event.declp->u.stmt.lutp, nv_instantiate, &pd);
 441         return (pd.props);
 442 }
 443 
 444 /*ARGSUSED*/
 445 static void
 446 instances_destructor(void *left, void *right, void *arg)
 447 {
 448         struct node *dn = (struct node *)right;
 449 
 450         if (dn->t == T_SERD) {
 451                 /* we allocated the lut during itree_create(), so free it */
 452                 lut_free(dn->u.stmt.lutp, instances_destructor, NULL);
 453                 dn->u.stmt.lutp = NULL;
 454         }
 455         if (dn->t != T_FUNC) /* T_FUNC pointed to original node */
 456                 tree_free(dn);
 457 }
 458 
 459 /*ARGSUSED*/
 460 static void
 461 payloadprops_destructor(void *left, void *right, void *arg)
 462 {
 463         FREE(right);
 464 }
 465 
 466 /*ARGSUSED*/
 467 static void
 468 serdprops_destructor(void *left, void *right, void *arg)
 469 {
 470         FREE(right);
 471 }
 472 
 473 /*
 474  * event_cmp -- used via lut_lookup/lut_add on instance tree lut
 475  */
 476 static int
 477 event_cmp(struct event *ep1, struct event *ep2)
 478 {
 479         int diff;
 480 
 481         if ((diff = ep2->enode->u.event.ename->u.name.s -
 482             ep1->enode->u.event.ename->u.name.s) != 0)
 483                 return (diff);
 484         if ((diff = (char *)ep2->ipp - (char *)ep1->ipp) != 0)
 485                 return (diff);
 486         return (0);
 487 
 488 }
 489 
 490 struct event *
 491 itree_lookup(struct lut *itp, const char *ename, const struct ipath *ipp)
 492 {
 493         struct event searchevent;       /* just used for searching */
 494         struct node searcheventnode;
 495         struct node searchenamenode;
 496 
 497         searchevent.enode = &searcheventnode;
 498         searcheventnode.t = T_EVENT;
 499         searcheventnode.u.event.ename = &searchenamenode;
 500         searchenamenode.t = T_NAME;
 501         searchenamenode.u.name.s = ename;
 502         searchevent.ipp = ipp;
 503         return (lut_lookup(itp, (void *)&searchevent, (lut_cmp)event_cmp));
 504 }
 505 
 506 static struct event *
 507 find_or_add_event(struct info *infop, struct node *np)
 508 {
 509         struct event *ret;
 510         struct event searchevent;       /* just used for searching */
 511 
 512         ASSERTeq(np->t, T_EVENT, ptree_nodetype2str);
 513 
 514         searchevent.enode = np;
 515         searchevent.ipp = ipath(np->u.event.epname);
 516         if ((ret = lut_lookup(infop->lut, (void *)&searchevent,
 517             (lut_cmp)event_cmp)) != NULL)
 518                 return (ret);
 519 
 520         /* wasn't already in tree, allocate it */
 521         ret = alloc_xmalloc(sizeof (*ret));
 522         bzero(ret, sizeof (*ret));
 523 
 524         ret->t = np->u.event.ename->u.name.t;
 525         ret->enode = np;
 526         ret->ipp = searchevent.ipp;
 527         ret->props = props2instance(np, np->u.event.epname);
 528 
 529         infop->lut = lut_add(infop->lut, (void *)ret, (void *)ret,
 530             (lut_cmp)event_cmp);
 531 
 532         return (ret);
 533 }
 534 
 535 /*
 536  * Used for handling expansions where first part of oldepname is a horizontal
 537  * expansion. Recurses through entire tree. oldepname argument is always the
 538  * full path as in the rules. Once we find a match we go back to using
 539  * hmatch_event to handle the rest.
 540  */
 541 static void
 542 hmatch_full_config(struct info *infop, struct node *eventnp,
 543     struct node *oldepname, struct config *ncp, struct node *nextnp,
 544     struct iterinfo *iterinfop)
 545 {
 546         char *cp_s;
 547         int cp_num;
 548         struct config *cp;
 549         struct node *saved_ewname;
 550         struct node *saved_epname;
 551         struct config *pcp, *ocp;
 552         struct node *cpnode;
 553         struct node *ewlp, *ewfp;
 554 
 555         for (cp = ncp; cp; cp = config_next(cp)) {
 556                 config_getcompname(cp, &cp_s, &cp_num);
 557                 if (cp_s == oldepname->u.name.s) {
 558                         /*
 559                          * Found one.
 560                          */
 561                         iterinfop->num = cp_num;
 562 
 563                         /*
 564                          * Need to set ewname, epname for correct node as is
 565                          * needed by constraint path matching. This code is
 566                          * similar to that in vmatch_event.
 567                          */
 568                         saved_ewname = eventnp->u.event.ewname;
 569                         saved_epname = eventnp->u.event.epname;
 570                         ocp = oldepname->u.name.cp;
 571 
 572                         /*
 573                          * Find correct ewname by walking back up the config
 574                          * tree adding each name portion as we go.
 575                          */
 576                         pcp = config_parent(cp);
 577                         eventnp->u.event.ewname = NULL;
 578                         for (; pcp != infop->croot; pcp = config_parent(pcp)) {
 579                                 config_getcompname(pcp, &cp_s, &cp_num);
 580                                 cpnode = tree_name(cp_s, IT_NONE, NULL, 0);
 581                                 cpnode->u.name.child = newnode(T_NUM, NULL, 0);
 582                                 cpnode->u.name.child->u.ull = cp_num;
 583                                 cpnode->u.name.cp = pcp;
 584                                 if (eventnp->u.event.ewname != NULL) {
 585                                         cpnode->u.name.next =
 586                                             eventnp->u.event.ewname;
 587                                         cpnode->u.name.last =
 588                                             eventnp->u.event.ewname->
 589                                             u.name.last;
 590                                 }
 591                                 eventnp->u.event.ewname = cpnode;
 592                         }
 593 
 594                         /*
 595                          * Now create correct epname by duping new ewname
 596                          * and appending oldepname.
 597                          */
 598                         ewfp = tname_dup(eventnp->u.event.ewname, CN_DUP);
 599                         ewlp = ewfp->u.name.last;
 600                         ewfp->u.name.last = oldepname->u.name.last;
 601                         ewlp->u.name.next = oldepname;
 602                         oldepname->u.name.cp = cp;
 603                         eventnp->u.event.epname = ewfp;
 604 
 605                         outfl(O_ALTFP|O_VERB3|O_NONL, infop->anp->file,
 606                             infop->anp->line, "hmatch_full_config: ");
 607                         ptree_name_iter(O_ALTFP|O_VERB3|O_NONL,
 608                             eventnp->u.event.epname);
 609                         out(O_ALTFP|O_VERB3, NULL);
 610 
 611                         /*
 612                          * Now complete hmatch.
 613                          */
 614                         hmatch_event(infop, eventnp, oldepname->u.name.next,
 615                             config_child(cp), nextnp, 1);
 616 
 617                         /*
 618                          * set everything back again
 619                          */
 620                         oldepname->u.name.cp = ocp;
 621                         iterinfop->num = -1;
 622                         ewlp->u.name.next = NULL;
 623                         ewfp->u.name.last = ewlp;
 624                         tree_free(ewfp);
 625                         tree_free(eventnp->u.event.ewname);
 626                         eventnp->u.event.ewname = saved_ewname;
 627                         eventnp->u.event.epname = saved_epname;
 628                 }
 629                 /*
 630                  * Try the next level down.
 631                  */
 632                 hmatch_full_config(infop, eventnp,
 633                     oldepname, config_child(cp), nextnp, iterinfop);
 634         }
 635 }
 636 
 637 /*
 638  * hmatch_event -- perform any appropriate horizontal expansion on an event
 639  *
 640  * this routine is used to perform horizontal expansion on both the
 641  * left-hand-side events in a prop, and the right-hand-side events.
 642  * when called to handle a left-side event, nextnp point to the right
 643  * side of the prop that should be passed to hmatch() for each match
 644  * found by horizontal expansion.   when no horizontal expansion exists,
 645  * we will still "match" one event for every event found in the list on
 646  * the left-hand-side of the prop because vmatch() already found that
 647  * there's at least one match during vertical expansion.
 648  */
 649 static void
 650 hmatch_event(struct info *infop, struct node *eventnp, struct node *epname,
 651     struct config *ncp, struct node *nextnp, int rematch)
 652 {
 653         if (epname == NULL) {
 654                 /*
 655                  * end of pathname recursion, either we just located
 656                  * a left-hand-side event and we're ready to move on
 657                  * to the expanding the right-hand-side events, or
 658                  * we're further down the recursion and we just located
 659                  * a right-hand-side event.  the passed-in parameter
 660                  * "nextnp" tells us whether we're working on the left
 661                  * side and need to move on to nextnp, or if nextnp is
 662                  * NULL, we're working on the right side.
 663                  */
 664                 if (nextnp) {
 665                         /*
 666                          * finished a left side expansion, move on to right.
 667                          * tell generate() what event we just matched so
 668                          * it can be used at the source of any arrows
 669                          * we generate as we match events on the right side.
 670                          */
 671                         generate_from(eventnp);
 672                         hmatch(infop, nextnp, NULL);
 673                 } else {
 674                         /*
 675                          * finished a right side expansion.  tell generate
 676                          * the information about the destination and let
 677                          * it construct the arrows as appropriate.
 678                          */
 679                         generate_to(eventnp);
 680                         generate(infop);
 681                 }
 682 
 683                 return;
 684         }
 685 
 686         ASSERTeq(epname->t, T_NAME, ptree_nodetype2str);
 687 
 688         if (epname->u.name.cp == NULL)
 689                 return;
 690 
 691         /*
 692          * we only get here when eventnp already has a completely
 693          * instanced epname in it already.  so we first recurse
 694          * down to the end of the name and as the recursion pops
 695          * up, we look for opportunities to advance horizontal
 696          * expansions on to the next match.
 697          */
 698         if (epname->u.name.it == IT_HORIZONTAL || rematch) {
 699                 struct config *cp;
 700                 struct config *ocp = epname->u.name.cp;
 701                 char *cp_s;
 702                 int cp_num;
 703                 int ocp_num;
 704                 struct iterinfo *iterinfop = NULL;
 705                 const char *iters;
 706                 int hexpand = 0;
 707 
 708                 if (epname->u.name.it != IT_HORIZONTAL) {
 709                         /*
 710                          * Ancestor was horizontal though, so must rematch
 711                          * against the name/num found in vmatch.
 712                          */
 713                         config_getcompname(ocp, NULL, &ocp_num);
 714                 } else {
 715                         iters = epname->u.name.child->u.name.s;
 716                         if ((iterinfop = lut_lookup(infop->ex,
 717                             (void *)iters, NULL)) == NULL) {
 718                                 /*
 719                                  * do horizontal expansion on this node
 720                                  */
 721                                 hexpand = 1;
 722                                 iterinfop = alloc_xmalloc(
 723                                     sizeof (struct iterinfo));
 724                                 iterinfop->num = -1;
 725                                 iterinfop->np = epname;
 726                                 infop->ex = lut_add(infop->ex, (void *)iters,
 727                                     iterinfop, NULL);
 728                         } else if (iterinfop->num == -1) {
 729                                 hexpand = 1;
 730                         } else {
 731                                 /*
 732                                  * This name has already been used in a
 733                                  * horizontal expansion. This time just match it
 734                                  */
 735                                 ocp_num = iterinfop->num;
 736                         }
 737                 }
 738                 /*
 739                  * handle case where this is the first section of oldepname
 740                  * and it is horizontally expanded. Instead of just looking for
 741                  * siblings, we want to scan the entire config tree for further
 742                  * matches.
 743                  */
 744                 if (epname == eventnp->u.event.oldepname &&
 745                     epname->u.name.it == IT_HORIZONTAL) {
 746                         /*
 747                          * Run through config looking for any that match the
 748                          * name.
 749                          */
 750                         hmatch_full_config(infop, eventnp, epname,
 751                             infop->croot, nextnp, iterinfop);
 752                         return;
 753                 }
 754 
 755                 /*
 756                  * Run through siblings looking for any that match the name.
 757                  * If hexpand not set then num must also match ocp_num.
 758                  */
 759                 for (cp = rematch ? ncp : ocp; cp; cp = config_next(cp)) {
 760                         config_getcompname(cp, &cp_s, &cp_num);
 761                         if (cp_s == epname->u.name.s) {
 762                                 if (hexpand)
 763                                         iterinfop->num = cp_num;
 764                                 else if (ocp_num != cp_num)
 765                                         continue;
 766                                 epname->u.name.cp = cp;
 767                                 hmatch_event(infop, eventnp,
 768                                     epname->u.name.next, config_child(cp),
 769                                     nextnp, 1);
 770                         }
 771                 }
 772                 epname->u.name.cp = ocp;
 773                 if (hexpand)
 774                         iterinfop->num = -1;
 775         } else {
 776                 hmatch_event(infop, eventnp, epname->u.name.next,
 777                     NULL, nextnp, 0);
 778         }
 779 }
 780 
 781 /*
 782  * hmatch -- check for horizontal expansion matches
 783  *
 784  * np points to the things we're matching (like a T_LIST or a T_EVENT)
 785  * and if we're working on a left-side of a prop, nextnp points to
 786  * the other side of the prop that we'll tackle next when this recursion
 787  * bottoms out.  when all the events in the entire prop arrow have been
 788  * horizontally expanded, generate() will be called to generate the
 789  * actualy arrow.
 790  */
 791 static void
 792 hmatch(struct info *infop, struct node *np, struct node *nextnp)
 793 {
 794         if (np == NULL)
 795                 return;         /* all done */
 796 
 797         /*
 798          * for each item in the list of events (which could just
 799          * be a single event, or it could get larger in the loop
 800          * below due to horizontal expansion), call hmatch on
 801          * the right side and create arrows to each element.
 802          */
 803 
 804         switch (np->t) {
 805         case T_LIST:
 806                 /* loop through the list */
 807                 if (np->u.expr.left)
 808                         hmatch(infop, np->u.expr.left, nextnp);
 809                 if (np->u.expr.right)
 810                         hmatch(infop, np->u.expr.right, nextnp);
 811                 break;
 812 
 813         case T_EVENT:
 814                 hmatch_event(infop, np, np->u.event.epname,
 815                     NULL, nextnp, 0);
 816                 break;
 817 
 818         default:
 819                 outfl(O_DIE, np->file, np->line,
 820                     "hmatch: unexpected type: %s",
 821                     ptree_nodetype2str(np->t));
 822         }
 823 }
 824 
 825 static int
 826 itree_np2nork(struct node *norknp)
 827 {
 828         if (norknp == NULL)
 829                 return (1);
 830         else if (norknp->t == T_NAME && norknp->u.name.s == L_A)
 831                 return (-1);    /* our internal version of "all" */
 832         else if (norknp->t == T_NUM)
 833                 return ((int)norknp->u.ull);
 834         else
 835                 outfl(O_DIE, norknp->file, norknp->line,
 836                     "itree_np2nork: internal error type %s",
 837                     ptree_nodetype2str(norknp->t));
 838         /*NOTREACHED*/
 839         return (1);
 840 }
 841 
 842 static struct iterinfo *
 843 newiterinfo(int num, struct node *np)
 844 {
 845         struct iterinfo *ret = alloc_xmalloc(sizeof (*ret));
 846 
 847         ret->num = num;
 848         ret->np = np;
 849         return (ret);
 850 }
 851 
 852 /*ARGSUSED*/
 853 static void
 854 iterinfo_destructor(void *left, void *right, void *arg)
 855 {
 856         struct iterinfo *iterinfop = (struct iterinfo *)right;
 857 
 858         alloc_xfree(iterinfop, sizeof (*iterinfop));
 859 }
 860 
 861 static void
 862 vmatch_event(struct info *infop, struct config *cp, struct node *np,
 863             struct node *lnp, struct node *anp, struct wildcardinfo *wcp)
 864 {
 865         char *cp_s;
 866         int cp_num;
 867         struct node *ewlp, *ewfp;
 868         struct config *pcp;
 869         struct node *cpnode;
 870         int newewname = 0;
 871 
 872         /*
 873          * handle case where the first section of the path name is horizontally
 874          * expanded. The whole expansion is handled by hmatch on the first
 875          * match here - so we just skip any subsequent matches here.
 876          */
 877         if (wcp->got_wc_hz == 1)
 878                 return;
 879 
 880         if (np == NULL) {
 881                 /*
 882                  * Reached the end of the name. u.name.cp pointers should be set
 883                  * up for each part of name. From this we can use config tree
 884                  * to build up the wildcard part of the name (if any).
 885                  */
 886                 pcp = config_parent(wcp->nptop->u.event.epname->u.name.cp);
 887                 if (pcp == infop->croot) {
 888                         /*
 889                          * no wildcarding done - move on to next entry
 890                          */
 891                         wcp->nptop->u.event.ewname = wcp->ewname;
 892                         wcp->nptop->u.event.oldepname = wcp->oldepname;
 893                         vmatch(infop, np, lnp, anp);
 894                         wcp->got_wc_hz = 0;
 895                         return;
 896                 }
 897                 if (wcp->ewname == NULL) {
 898                         /*
 899                          * ewname not yet set up - do it now
 900                          */
 901                         newewname = 1;
 902                         for (; pcp != infop->croot; pcp = config_parent(pcp)) {
 903                                 config_getcompname(pcp, &cp_s, &cp_num);
 904                                 cpnode = tree_name(cp_s, IT_NONE, NULL, 0);
 905                                 cpnode->u.name.child = newnode(T_NUM, NULL, 0);
 906                                 cpnode->u.name.child->u.ull = cp_num;
 907                                 cpnode->u.name.cp = pcp;
 908                                 if (wcp->ewname != NULL) {
 909                                         cpnode->u.name.next = wcp->ewname;
 910                                         cpnode->u.name.last =
 911                                             wcp->ewname->u.name.last;
 912                                 }
 913                                 wcp->ewname = cpnode;
 914                         }
 915                 }
 916 
 917                 /*
 918                  * dup ewname and append oldepname
 919                  */
 920                 ewfp = tname_dup(wcp->ewname, CN_DUP);
 921                 ewlp = ewfp->u.name.last;
 922                 ewfp->u.name.last = wcp->oldepname->u.name.last;
 923                 ewlp->u.name.next = wcp->oldepname;
 924 
 925                 wcp->nptop->u.event.epname = ewfp;
 926                 wcp->nptop->u.event.ewname = wcp->ewname;
 927                 wcp->nptop->u.event.oldepname = wcp->oldepname;
 928                 vmatch(infop, np, lnp, anp);
 929                 wcp->got_wc_hz = 0;
 930                 wcp->nptop->u.event.epname = wcp->oldepname;
 931 
 932                 /*
 933                  * reduce duped ewname to original then free
 934                  */
 935                 ewlp->u.name.next = NULL;
 936                 ewfp->u.name.last = ewlp;
 937                 tree_free(ewfp);
 938 
 939                 if (newewname) {
 940                         /*
 941                          * free ewname if allocated above
 942                          */
 943                         tree_free(wcp->ewname);
 944                         wcp->ewname = NULL;
 945                 }
 946                 return;
 947         }
 948 
 949         /*
 950          * We have an np. See if we can match it in this section of
 951          * the config tree.
 952          */
 953         if (cp == NULL)
 954                 return; /* no more config to match against */
 955 
 956         for (; cp; cp = config_next(cp)) {
 957                 config_getcompname(cp, &cp_s, &cp_num);
 958 
 959                 if (cp_s == np->u.name.s) {
 960                         /* found a matching component name */
 961                         if (np->u.name.child &&
 962                             np->u.name.child->t == T_NUM) {
 963                                 /*
 964                                  * an explicit instance number was given
 965                                  * in the source.  so only consider this
 966                                  * a configuration match if the number
 967                                  * also matches.
 968                                  */
 969                                 if (cp_num != np->u.name.child->u.ull)
 970                                         continue;
 971 
 972                         } else if (np->u.name.it != IT_HORIZONTAL) {
 973                                 struct iterinfo *iterinfop;
 974                                 const char *iters;
 975 
 976                                 /*
 977                                  * vertical iterator.  look it up in
 978                                  * the appropriate lut and if we get
 979                                  * back a value it is either one that we
 980                                  * set earlier, in which case we record
 981                                  * the new value for this iteration and
 982                                  * keep matching, or it is one that was
 983                                  * set by an earlier reference to the
 984                                  * iterator, in which case we only consider
 985                                  * this a configuration match if the number
 986                                  * matches cp_num.
 987                                  */
 988 
 989                                 ASSERT(np->u.name.child != NULL);
 990                                 ASSERT(np->u.name.child->t == T_NAME);
 991                                 iters = np->u.name.child->u.name.s;
 992 
 993                                 if ((iterinfop = lut_lookup(infop->ex,
 994                                     (void *)iters, NULL)) == NULL) {
 995                                         /* we're the first use, record our np */
 996                                         infop->ex = lut_add(infop->ex,
 997                                             (void *)iters,
 998                                             newiterinfo(cp_num, np), NULL);
 999                                 } else if (np == iterinfop->np) {
1000                                         /*
1001                                          * we're the first use, back again
1002                                          * for another iteration.  so update
1003                                          * the num bound to this iterator in
1004                                          * the lut.
1005                                          */
1006                                         iterinfop->num = cp_num;
1007                                 } else if (cp_num != iterinfop->num) {
1008                                         /*
1009                                          * an earlier reference to this
1010                                          * iterator bound it to a different
1011                                          * instance number, so there's no
1012                                          * match here after all.
1013                                          *
1014                                          * however, it's possible that this
1015                                          * component should really be part of
1016                                          * the wildcard.  we explore this by
1017                                          * forcing this component into the
1018                                          * wildcarded section.
1019                                          *
1020                                          * for an more details of what's
1021                                          * going to happen now, see
1022                                          * comments block below entitled
1023                                          * "forcing components into
1024                                          * wildcard path".
1025                                          */
1026                                         if (np == wcp->nptop->u.event.epname)
1027                                                 vmatch_event(infop,
1028                                                     config_child(cp), np, lnp,
1029                                                     anp, wcp);
1030                                         continue;
1031                                 }
1032                         }
1033 
1034                         /*
1035                          * if this was an IT_HORIZONTAL name, hmatch() will
1036                          * expand all matches horizontally into a list.
1037                          * we know the list will contain at least
1038                          * one element (the one we just matched),
1039                          * so we just let hmatch_event() do the rest.
1040                          *
1041                          * recurse on to next component. Note that
1042                          * wildcarding is now turned off.
1043                          */
1044                         np->u.name.cp = cp;
1045                         vmatch_event(infop, config_child(cp), np->u.name.next,
1046                             lnp, anp, wcp);
1047                         np->u.name.cp = NULL;
1048 
1049                         /*
1050                          * handle case where this is the first section of the
1051                          * path name and it is horizontally expanded.
1052                          * In this case we want all matching nodes in the config
1053                          * to be expanded horizontally - so set got_wc_hz and
1054                          * leave all further processing to hmatch.
1055                          */
1056                         if (G.matched && np == wcp->nptop->u.event.epname &&
1057                             np->u.name.it == IT_HORIZONTAL)
1058                                 wcp->got_wc_hz = 1;
1059 
1060                         /*
1061                          * forcing components into wildcard path:
1062                          *
1063                          * if this component is the first match, force it
1064                          * to be part of the wildcarded path and see if we
1065                          * can get additional matches.
1066                          *
1067                          * here's an example.  suppose we have the
1068                          * definition
1069                          *      event foo@x/y
1070                          * and configuration
1071                          *      a0/x0/y0/a1/x1/y1
1072                          *
1073                          * the code up to this point will treat "a0" as the
1074                          * wildcarded part of the path and "x0/y0" as the
1075                          * nonwildcarded part, resulting in the instanced
1076                          * event
1077                          *      foo@a0/x0/y0
1078                          *
1079                          * in order to discover the next match (.../x1/y1)
1080                          * in the configuration we have to force "x0" into
1081                          * the wildcarded part of the path.
1082                          * by doing so, we discover the wildcarded part
1083                          * "a0/x0/y0/a1" and the nonwildcarded part "x1/y1"
1084                          *
1085                          * the following call to vmatch_event() is also
1086                          * needed to properly handle the configuration
1087                          *      b0/x0/b1/x1/y1
1088                          *
1089                          * the recursions into vmatch_event() will start
1090                          * off uncovering "b0" as the wildcarded part and
1091                          * "x0" as the start of the nonwildcarded path.
1092                          * however, the next recursion will not result in a
1093                          * match since there is no "y" following "x0".  the
1094                          * subsequent match of (wildcard = "b0/x0/b1" and
1095                          * nonwildcard = "x1/y1") will be discovered only
1096                          * if "x0" is forced to be a part of the wildcarded
1097                          * path.
1098                          */
1099                         if (np == wcp->nptop->u.event.epname)
1100                                 vmatch_event(infop, config_child(cp), np, lnp,
1101                                     anp, wcp);
1102 
1103                         if (np->u.name.it == IT_HORIZONTAL) {
1104                                 /*
1105                                  * hmatch() finished iterating through
1106                                  * the configuration as described above, so
1107                                  * don't continue iterating here.
1108                                  */
1109                                 return;
1110                         }
1111                 } else if (np == wcp->nptop->u.event.epname) {
1112                         /*
1113                          * no match - carry on down the tree looking for
1114                          * wildcarding
1115                          */
1116                         vmatch_event(infop, config_child(cp), np, lnp, anp,
1117                             wcp);
1118                 }
1119         }
1120 }
1121 
1122 /*
1123  * vmatch -- find the next vertical expansion match in the config database
1124  *
1125  * this routine is called with three node pointers:
1126  *       np -- the parse we're matching
1127  *      lnp -- the rest of the list we're currently working on
1128  *      anp -- the rest of the arrow we're currently working on
1129  *
1130  * the expansion matching happens via three types of recursion:
1131  *
1132  *      - when given an arrow, handle the left-side and then recursively
1133  *        handle the right side (which might be another cascaded arrow).
1134  *
1135  *      - when handling one side of an arrow, recurse through the T_LIST
1136  *        to get to each event (or just move on to the event if there
1137  *        is a single event instead of a list)  since the arrow parse
1138  *        trees recurse left, we actually start with the right-most
1139  *        event list in the prop statement and work our way towards
1140  *        the left-most event list.
1141  *
1142  *      - when handling an event, recurse down each component of the
1143  *        pathname, matching in the config database and recording the
1144  *        matches in the explicit iterator dictionary as we go.
1145  *
1146  * when the bottom of this matching recursion is met, meaning we have
1147  * set the "cp" pointers on all the names in the entire statement,
1148  * we call hmatch() which does it's own recursion to handle horizontal
1149  * expandsion and then call generate() to generate nodes, bubbles, and
1150  * arrows in the instance tree.  generate() looks at the cp pointers to
1151  * see what instance numbers were matched in the configuration database.
1152  *
1153  * when horizontal expansion appears, vmatch() finds only the first match
1154  * and hmatch() then takes the horizontal expansion through all the other
1155  * matches when generating the arrows in the instance tree.
1156  *
1157  * the "infop" passed down through the recursion contains a dictionary
1158  * of the explicit iterators (all the implicit iterators have been converted
1159  * to explicit iterators when the parse tree was created by tree.c), which
1160  * allows things like this to work correctly:
1161  *
1162  *      prop error.a@x[n]/y/z -> error.b@x/y[n]/z -> error.c@x/y/z[n];
1163  *
1164  * during the top level call, the explicit iterator "n" will match an
1165  * instance number in the config database, and the result will be recorded
1166  * in the explicit iterator dictionary and passed down via "infop".  so
1167  * when the recursive call tries to match y[n] in the config database, it
1168  * will only match the same instance number as x[n] did since the dictionary
1169  * is consulted to see if "n" took on a value already.
1170  *
1171  * at any point during the recursion, match*() can return to indicate
1172  * a match was not found in the config database and that the caller should
1173  * move on to the next potential match, if any.
1174  *
1175  * constraints are completely ignored by match(), so the statement:
1176  *
1177  *      prop error.a@x[n] -> error.b@x[n] {n != 0};
1178  *
1179  * might very well match x[0] if it appears in the config database.  it
1180  * is the generate() routine that takes that match and then decides what
1181  * arrow, if any, should be generated in the instance tree.  generate()
1182  * looks at the explicit iterator dictionary to get values like "n" in
1183  * the above example so that it can evaluate constraints.
1184  *
1185  */
1186 static void
1187 vmatch(struct info *infop, struct node *np, struct node *lnp, struct node *anp)
1188 {
1189         struct node *np1, *np2, *oldepname, *oldnptop;
1190         int epmatches;
1191         struct config *cp;
1192         struct wildcardinfo *wcp;
1193 
1194         if (np == NULL) {
1195                 G.matched = 1;
1196                 if (lnp)
1197                         vmatch(infop, lnp, NULL, anp);
1198                 else if (anp)
1199                         vmatch(infop, anp, NULL, NULL);
1200                 else {
1201                         struct node *src;
1202                         struct node *dst;
1203 
1204                         /* end of vertical match recursion */
1205                         outfl(O_ALTFP|O_VERB3|O_NONL,
1206                             infop->anp->file, infop->anp->line, "vmatch: ");
1207                         ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, infop->anp);
1208                         out(O_ALTFP|O_VERB3, NULL);
1209 
1210                         generate_nork(
1211                             itree_np2nork(infop->anp->u.arrow.nnp),
1212                             itree_np2nork(infop->anp->u.arrow.knp));
1213                         dst = infop->anp->u.arrow.rhs;
1214                         src = infop->anp->u.arrow.lhs;
1215                         for (;;) {
1216                                 generate_new(); /* new set of arrows */
1217                                 if (src->t == T_ARROW) {
1218                                         hmatch(infop, src->u.arrow.rhs, dst);
1219                                         generate_nork(
1220                                             itree_np2nork(src->u.arrow.nnp),
1221                                             itree_np2nork(src->u.arrow.knp));
1222                                         dst = src->u.arrow.rhs;
1223                                         src = src->u.arrow.lhs;
1224                                 } else {
1225                                         hmatch(infop, src, dst);
1226                                         break;
1227                                 }
1228                         }
1229                 }
1230                 return;
1231         }
1232 
1233         switch (np->t) {
1234         case T_EVENT: {
1235                 epmatches = 0;
1236                 /*
1237                  * see if we already have a match in the wcps
1238                  */
1239                 for (wcp = wcproot; wcp; wcp = wcp->next) {
1240                         oldepname = wcp->oldepname;
1241                         oldnptop = wcp->nptop;
1242                         for (np1 = oldepname, np2 = np->u.event.epname;
1243                             np1 != NULL && np2 != NULL; np1 = np1->u.name.next,
1244                             np2 = np2->u.name.next) {
1245                                 if (strcmp(np1->u.name.s, np2->u.name.s) != 0)
1246                                         break;
1247                                 if (np1->u.name.child->t !=
1248                                     np2->u.name.child->t)
1249                                         break;
1250                                 if (np1->u.name.child->t == T_NUM &&
1251                                     np1->u.name.child->u.ull !=
1252                                     np2->u.name.child->u.ull)
1253                                         break;
1254                                 if (np1->u.name.child->t == T_NAME &&
1255                                     strcmp(np1->u.name.child->u.name.s,
1256                                     np2->u.name.child->u.name.s) != 0)
1257                                         break;
1258                                 epmatches++;
1259                         }
1260                         if (epmatches)
1261                                 break;
1262                 }
1263                 if (epmatches && np1 == NULL && np2 == NULL) {
1264                         /*
1265                          * complete names match, can just borrow the fields
1266                          */
1267                         oldepname = np->u.event.epname;
1268                         np->u.event.epname = oldnptop->u.event.epname;
1269                         np->u.event.oldepname = wcp->oldepname;
1270                         np->u.event.ewname = wcp->ewname;
1271                         vmatch(infop, NULL, lnp, anp);
1272                         np->u.event.epname = oldepname;
1273                         return;
1274                 }
1275                 G.matched = 0;
1276                 if (epmatches) {
1277                         /*
1278                          * just first part of names match - do wildcarding
1279                          * by using existing wcp including ewname and also
1280                          * copying as much of pwname as is valid, then start
1281                          * vmatch_event() at start of non-matching section
1282                          */
1283                         for (np1 = oldepname, np2 = np->u.event.epname;
1284                             epmatches != 0; epmatches--) {
1285                                 cp = np1->u.name.cp;
1286                                 np2->u.name.cp = cp;
1287                                 np1 = np1->u.name.next;
1288                                 np2 = np2->u.name.next;
1289                         }
1290                         wcp->oldepname = np->u.event.epname;
1291                         wcp->nptop = np;
1292                         vmatch_event(infop, config_child(cp), np2, lnp,
1293                             anp, wcp);
1294                         wcp->oldepname = oldepname;
1295                         wcp->nptop = oldnptop;
1296                         if (G.matched == 0) {
1297                                 /*
1298                                  * This list entry is NULL. Move on to next item
1299                                  * in the list.
1300                                  */
1301                                 vmatch(infop, NULL, lnp, anp);
1302                         }
1303                         return;
1304                 }
1305                 /*
1306                  * names do not match - allocate a new wcp
1307                  */
1308                 wcp = MALLOC(sizeof (struct wildcardinfo));
1309                 wcp->next = wcproot;
1310                 wcproot = wcp;
1311                 wcp->nptop = np;
1312                 wcp->oldepname = np->u.event.epname;
1313                 wcp->ewname = NULL;
1314                 wcp->got_wc_hz = 0;
1315 
1316                 vmatch_event(infop, config_child(infop->croot),
1317                     np->u.event.epname, lnp, anp, wcp);
1318 
1319                 wcproot = wcp->next;
1320                 FREE(wcp);
1321                 if (G.matched == 0) {
1322                         /*
1323                          * This list entry is NULL. Move on to next item in the
1324                          * list.
1325                          */
1326                         vmatch(infop, NULL, lnp, anp);
1327                 }
1328                 break;
1329         }
1330         case T_LIST:
1331                 ASSERT(lnp == NULL);
1332                 vmatch(infop, np->u.expr.right, np->u.expr.left, anp);
1333                 break;
1334 
1335         case T_ARROW:
1336                 ASSERT(lnp == NULL && anp == NULL);
1337                 vmatch(infop, np->u.arrow.rhs, NULL, np->u.arrow.parent);
1338                 break;
1339 
1340         default:
1341                 outfl(O_DIE, np->file, np->line,
1342                     "vmatch: unexpected type: %s",
1343                     ptree_nodetype2str(np->t));
1344         }
1345 }
1346 
1347 static void
1348 find_first_arrow(struct info *infop, struct node *anp)
1349 {
1350         if (anp->u.arrow.lhs->t == T_ARROW) {
1351                 anp->u.arrow.lhs->u.arrow.parent = anp;
1352                 find_first_arrow(infop, anp->u.arrow.lhs);
1353         } else
1354                 vmatch(infop, anp->u.arrow.lhs, NULL, anp);
1355 }
1356 
1357 static void
1358 cp_reset(struct node *np)
1359 {
1360         if (np == NULL)
1361                 return;
1362         switch (np->t) {
1363         case T_NAME:
1364                 np->u.name.cp = NULL;
1365                 cp_reset(np->u.name.next);
1366                 break;
1367 
1368         case T_LIST:
1369                 cp_reset(np->u.expr.left);
1370                 cp_reset(np->u.expr.right);
1371                 break;
1372 
1373         case T_ARROW:
1374                 cp_reset(np->u.arrow.lhs);
1375                 cp_reset(np->u.arrow.rhs);
1376                 break;
1377 
1378         case T_EVENT:
1379                 cp_reset(np->u.event.epname);
1380                 break;
1381         }
1382 }
1383 
1384 /*
1385  * itree_create -- apply the current config to the current parse tree
1386  *
1387  * returns a lut mapping fully-instance-qualified names to struct events.
1388  *
1389  */
1390 struct lut *
1391 itree_create(struct config *croot)
1392 {
1393         struct lut *retval;
1394         struct node *propnp;
1395         extern int alloc_total();
1396         int init_size;
1397 
1398         Ninfo.lut = NULL;
1399         Ninfo.croot = croot;
1400         init_size = alloc_total();
1401         out(O_ALTFP|O_STAMP, "start itree_create using %d bytes", init_size);
1402         for (propnp = Props; propnp; propnp = propnp->u.stmt.next) {
1403                 struct node *anp = propnp->u.stmt.np;
1404 
1405                 ASSERTeq(anp->t, T_ARROW, ptree_nodetype2str);
1406 
1407                 if (!anp->u.arrow.needed)
1408                         continue;
1409                 Ninfo.anp = anp;
1410                 Ninfo.ex = NULL;
1411 
1412                 generate_arrownp(anp);
1413                 anp->u.arrow.parent = NULL;
1414                 find_first_arrow(&Ninfo, anp);
1415 
1416                 if (Ninfo.ex) {
1417                         lut_free(Ninfo.ex, iterinfo_destructor, NULL);
1418                         Ninfo.ex = NULL;
1419                 }
1420                 cp_reset(anp);
1421         }
1422 
1423         out(O_ALTFP|O_STAMP, "itree_create added %d bytes",
1424             alloc_total() - init_size);
1425         retval = Ninfo.lut;
1426         Ninfo.lut = NULL;
1427         return (retval);
1428 }
1429 
1430 /*
1431  * initial first pass of the rules.
1432  * We don't use the config at all. Just check the last part of the pathname
1433  * in the rules. If this matches the last part of the pathname in the first
1434  * ereport, then set pathname to the pathname in the ereport. If not then
1435  * set pathname to just the last part of pathname with instance number 0.
1436  * Constraints are ignored and all nork values are set to 0. If after all that
1437  * any rules can still not be associated with the ereport, then they are set
1438  * to not needed in prune_propagations() and ignored in the real itree_create()
1439  * which follows.
1440  */
1441 
1442 static struct event *
1443 add_event_dummy(struct node *np, const struct ipath *ipp)
1444 {
1445         struct event *ret;
1446         struct event searchevent;       /* just used for searching */
1447         extern struct ipath *ipath_dummy(struct node *, struct ipath *);
1448         struct ipath *ipp_un;
1449         extern struct ipath *ipath_for_usednames(struct node *);
1450 
1451         searchevent.enode = np;
1452         searchevent.ipp = ipath_dummy(np->u.event.epname, (struct ipath *)ipp);
1453         ipp_un = ipath_for_usednames(np->u.event.epname);
1454         if ((ret = lut_lookup(Ninfo.lut, (void *)&searchevent,
1455             (lut_cmp)event_cmp)) != NULL)
1456                 return (ret);
1457 
1458         ret = alloc_xmalloc(sizeof (*ret));
1459         bzero(ret, sizeof (*ret));
1460         ret->t = np->u.event.ename->u.name.t;
1461         ret->enode = np;
1462         ret->ipp = searchevent.ipp;
1463         ret->ipp_un = ipp_un;
1464         Ninfo.lut = lut_add(Ninfo.lut, (void *)ret, (void *)ret,
1465             (lut_cmp)event_cmp);
1466         return (ret);
1467 }
1468 
1469 /*ARGSUSED*/
1470 struct lut *
1471 itree_create_dummy(const char *e0class, const struct ipath *e0ipp)
1472 {
1473         struct node *propnp;
1474         struct event *frome, *toe;
1475         struct bubble *frombp, *tobp;
1476         struct arrow *arrowp;
1477         struct node *src, *dst, *slst, *dlst, *arrownp, *oldarrownp;
1478         int gen = 0;
1479         extern int alloc_total();
1480         int init_size;
1481 
1482         Ninfo.lut = NULL;
1483         init_size = alloc_total();
1484         out(O_ALTFP|O_STAMP, "start itree_create using %d bytes", init_size);
1485         for (propnp = Props; propnp; propnp = propnp->u.stmt.next) {
1486                 arrownp = propnp->u.stmt.np;
1487                 while (arrownp) {
1488                         gen++;
1489                         dlst = arrownp->u.arrow.rhs;
1490                         slst = arrownp->u.arrow.lhs;
1491                         oldarrownp = arrownp;
1492                         if (slst->t == T_ARROW) {
1493                                 arrownp = slst;
1494                                 slst = slst->u.arrow.rhs;
1495                         } else {
1496                                 arrownp = NULL;
1497                         }
1498                         while (slst) {
1499                                 if (slst->t == T_LIST) {
1500                                         src = slst->u.expr.right;
1501                                         slst = slst->u.expr.left;
1502                                 } else {
1503                                         src = slst;
1504                                         slst = NULL;
1505                                 }
1506                                 frome = add_event_dummy(src, e0ipp);
1507                                 frombp = itree_add_bubble(frome, B_FROM, 0, 0);
1508                                 while (dlst) {
1509                                         if (dlst->t == T_LIST) {
1510                                                 dst = dlst->u.expr.right;
1511                                                 dlst = dlst->u.expr.left;
1512                                         } else {
1513                                                 dst = dlst;
1514                                                 dlst = NULL;
1515                                         }
1516                                         arrowp = alloc_xmalloc(
1517                                             sizeof (struct arrow));
1518                                         bzero(arrowp, sizeof (struct arrow));
1519                                         arrowp->pnode = oldarrownp;
1520                                         toe = add_event_dummy(dst, e0ipp);
1521                                         tobp = itree_add_bubble(toe, B_TO, 0,
1522                                             gen);
1523                                         arrowp->tail = frombp;
1524                                         arrowp->head = tobp;
1525                                         add_arrow(frombp, arrowp);
1526                                         add_arrow(tobp, arrowp);
1527                                         arrow_add_within(arrowp,
1528                                             dst->u.event.declp->u.stmt.np->
1529                                             u.event.eexprlist);
1530                                         arrow_add_within(arrowp,
1531                                             dst->u.event.eexprlist);
1532                                 }
1533                         }
1534                 }
1535         }
1536         out(O_ALTFP|O_STAMP, "itree_create added %d bytes",
1537             alloc_total() - init_size);
1538         return (Ninfo.lut);
1539 }
1540 
1541 void
1542 itree_free(struct lut *lutp)
1543 {
1544         int init_size;
1545 
1546         init_size = alloc_total();
1547         out(O_ALTFP|O_STAMP, "start itree_free");
1548         lut_free(lutp, itree_destructor, NULL);
1549         out(O_ALTFP|O_STAMP, "itree_free freed %d bytes",
1550             init_size - alloc_total());
1551 }
1552 
1553 void
1554 itree_prune(struct lut *lutp)
1555 {
1556         int init_size;
1557 
1558         init_size = alloc_total();
1559         out(O_ALTFP|O_STAMP, "start itree_prune");
1560         lut_walk(lutp, itree_pruner, NULL);
1561         out(O_ALTFP|O_STAMP, "itree_prune freed %d bytes",
1562             init_size - alloc_total());
1563 }
1564 
1565 void
1566 itree_pevent_brief(int flags, struct event *ep)
1567 {
1568         ASSERT(ep != NULL);
1569         ASSERT(ep->enode != NULL);
1570         ASSERT(ep->ipp != NULL);
1571 
1572         ipath_print(flags, ep->enode->u.event.ename->u.name.s, ep->ipp);
1573 }
1574 
1575 /*ARGSUSED*/
1576 static void
1577 itree_pevent(struct event *lhs, struct event *ep, void *arg)
1578 {
1579         struct plut_wlk_data propd;
1580         struct bubble *bp;
1581         int flags = (int)(intptr_t)arg;
1582 
1583         itree_pevent_brief(flags, ep);
1584         if (ep->t == N_EREPORT)
1585                 out(flags, " (count %d)", ep->count);
1586         else
1587                 out(flags, NULL);
1588 
1589         if (ep->props) {
1590                 propd.flags = flags;
1591                 propd.first = 1;
1592                 out(flags, "Properties:");
1593                 lut_walk(ep->props, ptree_plut, (void *)&propd);
1594         }
1595 
1596         for (bp = itree_next_bubble(ep, NULL); bp;
1597             bp = itree_next_bubble(ep, bp)) {
1598                 /* Print only TO bubbles in this loop */
1599                 if (bp->t != B_TO)
1600                         continue;
1601                 itree_pbubble(flags, bp);
1602         }
1603 
1604         for (bp = itree_next_bubble(ep, NULL); bp;
1605             bp = itree_next_bubble(ep, bp)) {
1606                 /* Print only INHIBIT bubbles in this loop */
1607                 if (bp->t != B_INHIBIT)
1608                         continue;
1609                 itree_pbubble(flags, bp);
1610         }
1611 
1612         for (bp = itree_next_bubble(ep, NULL); bp;
1613             bp = itree_next_bubble(ep, bp)) {
1614                 /* Print only FROM bubbles in this loop */
1615                 if (bp->t != B_FROM)
1616                         continue;
1617                 itree_pbubble(flags, bp);
1618         }
1619 }
1620 
1621 static void
1622 itree_pbubble(int flags, struct bubble *bp)
1623 {
1624         struct constraintlist *cp;
1625         struct arrowlist *ap;
1626 
1627         ASSERT(bp != NULL);
1628 
1629         out(flags|O_NONL, "   ");
1630         if (bp->mark)
1631                 out(flags|O_NONL, "*");
1632         else
1633                 out(flags|O_NONL, " ");
1634         if (bp->t == B_FROM)
1635                 out(flags|O_NONL, "N=%d to:", bp->nork);
1636         else if (bp->t == B_TO)
1637                 out(flags|O_NONL, "K=%d from:", bp->nork);
1638         else
1639                 out(flags|O_NONL, "K=%d masked from:", bp->nork);
1640 
1641         if (bp->t == B_TO || bp->t == B_INHIBIT) {
1642                 for (ap = itree_next_arrow(bp, NULL); ap;
1643                     ap = itree_next_arrow(bp, ap)) {
1644                         ASSERT(ap->arrowp->head == bp);
1645                         ASSERT(ap->arrowp->tail != NULL);
1646                         ASSERT(ap->arrowp->tail->myevent != NULL);
1647                         out(flags|O_NONL, " ");
1648                         itree_pevent_brief(flags, ap->arrowp->tail->myevent);
1649                 }
1650                 out(flags, NULL);
1651                 return;
1652         }
1653 
1654         for (ap = itree_next_arrow(bp, NULL); ap;
1655             ap = itree_next_arrow(bp, ap)) {
1656                 ASSERT(ap->arrowp->tail == bp);
1657                 ASSERT(ap->arrowp->head != NULL);
1658                 ASSERT(ap->arrowp->head->myevent != NULL);
1659 
1660                 out(flags|O_NONL, " ");
1661                 itree_pevent_brief(flags, ap->arrowp->head->myevent);
1662 
1663                 out(flags|O_NONL, " ");
1664                 ptree_timeval(flags, &ap->arrowp->mindelay);
1665                 out(flags|O_NONL, ",");
1666                 ptree_timeval(flags, &ap->arrowp->maxdelay);
1667 
1668                 /* Display anything from the propogation node? */
1669                 out(O_VERB3|O_NONL, " <%s:%d>",
1670                     ap->arrowp->pnode->file, ap->arrowp->pnode->line);
1671 
1672                 if (itree_next_constraint(ap->arrowp, NULL))
1673                         out(flags|O_NONL, " {");
1674 
1675                 for (cp = itree_next_constraint(ap->arrowp, NULL); cp;
1676                     cp = itree_next_constraint(ap->arrowp, cp)) {
1677                         ptree(flags, cp->cnode, 1, 0);
1678                         if (itree_next_constraint(ap->arrowp, cp))
1679                                 out(flags|O_NONL, ", ");
1680                 }
1681 
1682                 if (itree_next_constraint(ap->arrowp, NULL))
1683                         out(flags|O_NONL, "}");
1684         }
1685         out(flags, NULL);
1686 }
1687 
1688 void
1689 itree_ptree(int flags, struct lut *itp)
1690 {
1691         lut_walk(itp, (lut_cb)itree_pevent, (void *)(intptr_t)flags);
1692 }
1693 
1694 /*ARGSUSED*/
1695 static void
1696 itree_destructor(void *left, void *right, void *arg)
1697 {
1698         struct event *ep = (struct event *)right;
1699         struct bubble *nextbub, *bub;
1700 
1701         /* Free the properties */
1702         if (ep->props)
1703                 lut_free(ep->props, instances_destructor, NULL);
1704 
1705         /* Free the payload properties */
1706         if (ep->payloadprops)
1707                 lut_free(ep->payloadprops, payloadprops_destructor, NULL);
1708 
1709         /* Free the serd properties */
1710         if (ep->serdprops)
1711                 lut_free(ep->serdprops, serdprops_destructor, NULL);
1712 
1713         /* Free my bubbles */
1714         for (bub = ep->bubbles; bub != NULL; ) {
1715                 nextbub = bub->next;
1716                 /*
1717                  * Free arrows if they are FROM me.  Free arrowlists on
1718                  * other types of bubbles (but not the attached arrows,
1719                  * which will be freed when we free the originating
1720                  * bubble.
1721                  */
1722                 if (bub->t == B_FROM)
1723                         itree_free_arrowlists(bub, 1);
1724                 else
1725                         itree_free_arrowlists(bub, 0);
1726                 itree_free_bubble(bub);
1727                 bub = nextbub;
1728         }
1729 
1730         if (ep->nvp != NULL)
1731                 nvlist_free(ep->nvp);
1732         alloc_xfree(ep, sizeof (*ep));
1733 }
1734 
1735 /*ARGSUSED*/
1736 static void
1737 itree_pruner(void *left, void *right, void *arg)
1738 {
1739         struct event *ep = (struct event *)right;
1740         struct bubble *nextbub, *bub;
1741 
1742         if (ep->keep_in_tree)
1743                 return;
1744 
1745         /* Free the properties */
1746         lut_free(ep->props, instances_destructor, NULL);
1747 
1748         /* Free the payload properties */
1749         lut_free(ep->payloadprops, payloadprops_destructor, NULL);
1750 
1751         /* Free the serd properties */
1752         lut_free(ep->serdprops, serdprops_destructor, NULL);
1753 
1754         /* Free my bubbles */
1755         for (bub = ep->bubbles; bub != NULL; ) {
1756                 nextbub = bub->next;
1757                 itree_prune_arrowlists(bub);
1758                 itree_free_bubble(bub);
1759                 bub = nextbub;
1760         }
1761 
1762         if (ep->nvp != NULL)
1763                 nvlist_free(ep->nvp);
1764         ep->props = NULL;
1765         ep->payloadprops = NULL;
1766         ep->serdprops = NULL;
1767         ep->bubbles = NULL;
1768         ep->nvp = NULL;
1769 }
1770 
1771 static void
1772 itree_free_bubble(struct bubble *freeme)
1773 {
1774         alloc_xfree(freeme, sizeof (*freeme));
1775 }
1776 
1777 static struct bubble *
1778 itree_add_bubble(struct event *eventp, enum bubbletype btype, int nork, int gen)
1779 {
1780         struct bubble *prev = NULL;
1781         struct bubble *curr;
1782         struct bubble *newb;
1783 
1784         /* Use existing bubbles as appropriate when possible */
1785         for (curr = eventp->bubbles;
1786             curr != NULL;
1787             prev = curr, curr = curr->next) {
1788                 if (btype == B_TO && curr->t == B_TO) {
1789                         /* see if an existing "to" bubble works for us */
1790                         if (gen == curr->gen)
1791                                 return (curr);  /* matched gen number */
1792                         else if (nork == 1 && curr->nork == 1) {
1793                                 curr->gen = gen;
1794                                 return (curr);  /* coalesce K==1 bubbles */
1795                         }
1796                 } else if (btype == B_FROM && curr->t == B_FROM) {
1797                         /* see if an existing "from" bubble works for us */
1798                         if ((nork == N_IS_ALL && curr->nork == N_IS_ALL) ||
1799                             (nork == 0 && curr->nork == 0))
1800                                 return (curr);
1801                 }
1802         }
1803 
1804         newb = alloc_xmalloc(sizeof (struct bubble));
1805         newb->next = NULL;
1806         newb->t = btype;
1807         newb->myevent = eventp;
1808         newb->nork = nork;
1809         newb->mark = 0;
1810         newb->gen = gen;
1811         newb->arrows = NULL;
1812 
1813         if (prev == NULL)
1814                 eventp->bubbles = newb;
1815         else
1816                 prev->next = newb;
1817 
1818         return (newb);
1819 }
1820 
1821 struct bubble *
1822 itree_next_bubble(struct event *eventp, struct bubble *last)
1823 {
1824         struct bubble *next;
1825 
1826         for (;;) {
1827                 if (last != NULL)
1828                         next = last->next;
1829                 else
1830                         next = eventp->bubbles;
1831 
1832                 if (next == NULL || next->arrows != NULL)
1833                         return (next);
1834 
1835                 /* bubble was empty, skip it */
1836                 last = next;
1837         }
1838 }
1839 
1840 static void
1841 add_arrow(struct bubble *bp, struct arrow *ap)
1842 {
1843         struct arrowlist *prev = NULL;
1844         struct arrowlist *curr;
1845         struct arrowlist *newal;
1846 
1847         newal = alloc_xmalloc(sizeof (struct arrowlist));
1848         bzero(newal, sizeof (struct arrowlist));
1849         newal->arrowp = ap;
1850 
1851         curr = itree_next_arrow(bp, NULL);
1852         while (curr != NULL) {
1853                 prev = curr;
1854                 curr = itree_next_arrow(bp, curr);
1855         }
1856 
1857         if (prev == NULL)
1858                 bp->arrows = newal;
1859         else
1860                 prev->next = newal;
1861 }
1862 
1863 static struct arrow *
1864 itree_add_arrow(struct node *apnode, struct node *fromevent,
1865     struct node *toevent, struct lut *ex)
1866 {
1867         struct arrow *newa;
1868 
1869         newa = alloc_xmalloc(sizeof (struct arrow));
1870         bzero(newa, sizeof (struct arrow));
1871         newa->pnode = apnode;
1872         newa->constraints = NULL;
1873 
1874         /*
1875          *  Set default delays, then try to re-set them from
1876          *  any within() constraints.
1877          */
1878         newa->mindelay = newa->maxdelay = 0ULL;
1879         if (itree_set_arrow_traits(newa, fromevent, toevent, ex) == 0) {
1880                 alloc_xfree(newa, sizeof (struct arrow));
1881                 return (NULL);
1882         }
1883 
1884         return (newa);
1885 }
1886 
1887 /* returns false if traits show that arrow should not be added after all */
1888 static int
1889 itree_set_arrow_traits(struct arrow *ap, struct node *fromev,
1890     struct node *toev, struct lut *ex)
1891 {
1892         struct node *events[] = { NULL, NULL, NULL };
1893         struct node *newc = NULL;
1894 
1895         ASSERTeq(fromev->t, T_EVENT, ptree_nodetype2str);
1896         ASSERTeq(toev->t, T_EVENT, ptree_nodetype2str);
1897 
1898         /*
1899          * search for the within values first on the declaration of
1900          * the destination event, and then on the prop.  this allows
1901          * one to specify a "default" within by putting it on the
1902          * declaration,  but then allow overriding on the prop statement.
1903          */
1904         arrow_add_within(ap, toev->u.event.declp->u.stmt.np->u.event.eexprlist);
1905         arrow_add_within(ap, toev->u.event.eexprlist);
1906 
1907         /*
1908          * handle any global constraints inherited from the
1909          * "fromev" event's declaration
1910          */
1911         ASSERT(fromev->u.event.declp != NULL);
1912         ASSERT(fromev->u.event.declp->u.stmt.np != NULL);
1913 
1914 #ifdef  notdef
1915         /* XXX not quite ready to evaluate constraints from decls yet */
1916         if (fromev->u.event.declp->u.stmt.np->u.event.eexprlist)
1917                 (void) itree_add_constraint(ap,
1918                     fromev->u.event.declp->u.stmt.np->u.event.eexprlist);
1919 #endif  /* notdef */
1920 
1921         /* handle constraints on the from event in the prop statement */
1922         events[0] = fromev;
1923         events[1] = toev;
1924         if (eval_potential(fromev->u.event.eexprlist, ex, events, &newc,
1925             Ninfo.croot) == 0)
1926                 return (0);             /* constraint disallows arrow */
1927 
1928         /*
1929          * handle any global constraints inherited from the
1930          * "toev" event's declaration
1931          */
1932         ASSERT(toev->u.event.declp != NULL);
1933         ASSERT(toev->u.event.declp->u.stmt.np != NULL);
1934 
1935 #ifdef  notdef
1936         /* XXX not quite ready to evaluate constraints from decls yet */
1937         if (toev->u.event.declp->u.stmt.np->u.event.eexprlist)
1938                 (void) itree_add_constraint(ap,
1939                     toev->u.event.declp->u.stmt.np->u.event.eexprlist);
1940 #endif  /* notdef */
1941 
1942         /* handle constraints on the to event in the prop statement */
1943         events[0] = toev;
1944         events[1] = fromev;
1945         if (eval_potential(toev->u.event.eexprlist, ex, events, &newc,
1946             Ninfo.croot) == 0) {
1947                 if (newc != NULL)
1948                         tree_free(newc);
1949                 return (0);             /* constraint disallows arrow */
1950         }
1951 
1952         /* if we came up with any deferred constraints, add them to arrow */
1953         if (newc != NULL) {
1954                 out(O_ALTFP|O_VERB3, "(deferred constraints)");
1955                 (void) itree_add_constraint(ap, iexpr(newc));
1956         }
1957 
1958         return (1);     /* constraints allow arrow */
1959 }
1960 
1961 /*
1962  * Set within() constraint.  If the constraint were set multiple times,
1963  * the last one would "win".
1964  */
1965 static void
1966 arrow_add_within(struct arrow *ap, struct node *xpr)
1967 {
1968         struct node *arglist;
1969 
1970         /* end of expressions list */
1971         if (xpr == NULL)
1972                 return;
1973 
1974         switch (xpr->t) {
1975         case T_LIST:
1976                 arrow_add_within(ap, xpr->u.expr.left);
1977                 arrow_add_within(ap, xpr->u.expr.right);
1978                 return;
1979         case T_FUNC:
1980                 if (xpr->u.func.s != L_within)
1981                         return;
1982                 arglist = xpr->u.func.arglist;
1983                 switch (arglist->t) {
1984                 case T_TIMEVAL:
1985                         ap->mindelay = 0;
1986                         ap->maxdelay = arglist->u.ull;
1987                         break;
1988                 case T_NAME:
1989                         ASSERT(arglist->u.name.s == L_infinity);
1990                         ap->mindelay = 0;
1991                         ap->maxdelay = TIMEVAL_EVENTUALLY;
1992                         break;
1993                 case T_LIST:
1994                         ASSERT(arglist->u.expr.left->t == T_TIMEVAL);
1995                         ap->mindelay = arglist->u.expr.left->u.ull;
1996                         switch (arglist->u.expr.right->t) {
1997                         case T_TIMEVAL:
1998                                 ap->maxdelay = arglist->u.ull;
1999                                 break;
2000                         case T_NAME:
2001                                 ASSERT(arglist->u.expr.right->u.name.s ==
2002                                     L_infinity);
2003                                 ap->maxdelay = TIMEVAL_EVENTUALLY;
2004                                 break;
2005                         default:
2006                                 out(O_DIE, "within: unexpected 2nd arg type");
2007                         }
2008                         break;
2009                 default:
2010                         out(O_DIE, "within: unexpected 1st arg type");
2011                 }
2012                 break;
2013         default:
2014                 return;
2015         }
2016 }
2017 
2018 static void
2019 itree_free_arrowlists(struct bubble *bubp, int arrows_too)
2020 {
2021         struct arrowlist *al, *nal;
2022 
2023         al = bubp->arrows;
2024         while (al != NULL) {
2025                 nal = al->next;
2026                 if (arrows_too) {
2027                         itree_free_constraints(al->arrowp);
2028                         alloc_xfree(al->arrowp, sizeof (struct arrow));
2029                 }
2030                 alloc_xfree(al, sizeof (*al));
2031                 al = nal;
2032         }
2033 }
2034 
2035 static void
2036 itree_delete_arrow(struct bubble *bubp, struct arrow *arrow)
2037 {
2038         struct arrowlist *al, *oal;
2039 
2040         al = bubp->arrows;
2041         if (al->arrowp == arrow) {
2042                 bubp->arrows = al->next;
2043                 alloc_xfree(al, sizeof (*al));
2044                 return;
2045         }
2046         while (al != NULL) {
2047                 oal = al;
2048                 al = al->next;
2049                 ASSERT(al != NULL);
2050                 if (al->arrowp == arrow) {
2051                         oal->next = al->next;
2052                         alloc_xfree(al, sizeof (*al));
2053                         return;
2054                 }
2055         }
2056 }
2057 
2058 static void
2059 itree_prune_arrowlists(struct bubble *bubp)
2060 {
2061         struct arrowlist *al, *nal;
2062 
2063         al = bubp->arrows;
2064         while (al != NULL) {
2065                 nal = al->next;
2066                 if (bubp->t == B_FROM)
2067                         itree_delete_arrow(al->arrowp->head, al->arrowp);
2068                 else
2069                         itree_delete_arrow(al->arrowp->tail, al->arrowp);
2070                 itree_free_constraints(al->arrowp);
2071                 alloc_xfree(al->arrowp, sizeof (struct arrow));
2072                 alloc_xfree(al, sizeof (*al));
2073                 al = nal;
2074         }
2075 }
2076 
2077 struct arrowlist *
2078 itree_next_arrow(struct bubble *bubble, struct arrowlist *last)
2079 {
2080         struct arrowlist *next;
2081 
2082         if (last != NULL)
2083                 next = last->next;
2084         else
2085                 next = bubble->arrows;
2086         return (next);
2087 }
2088 
2089 static struct constraintlist *
2090 itree_add_constraint(struct arrow *arrowp, struct node *c)
2091 {
2092         struct constraintlist *prev = NULL;
2093         struct constraintlist *curr;
2094         struct constraintlist *newc;
2095 
2096         for (curr = arrowp->constraints;
2097             curr != NULL;
2098             prev = curr, curr = curr->next)
2099                 ;
2100 
2101         newc = alloc_xmalloc(sizeof (struct constraintlist));
2102         newc->next = NULL;
2103         newc->cnode = c;
2104 
2105         if (prev == NULL)
2106                 arrowp->constraints = newc;
2107         else
2108                 prev->next = newc;
2109 
2110         return (newc);
2111 }
2112 
2113 struct constraintlist *
2114 itree_next_constraint(struct arrow *arrowp, struct constraintlist *last)
2115 {
2116         struct constraintlist *next;
2117 
2118         if (last != NULL)
2119                 next = last->next;
2120         else
2121                 next = arrowp->constraints;
2122         return (next);
2123 }
2124 
2125 static void
2126 itree_free_constraints(struct arrow *ap)
2127 {
2128         struct constraintlist *cl, *ncl;
2129 
2130         cl = ap->constraints;
2131         while (cl != NULL) {
2132                 ncl = cl->next;
2133                 ASSERT(cl->cnode != NULL);
2134                 if (!iexpr_cached(cl->cnode))
2135                         tree_free(cl->cnode);
2136                 else
2137                         iexpr_free(cl->cnode);
2138                 alloc_xfree(cl, sizeof (*cl));
2139                 cl = ncl;
2140         }
2141 }
2142 
2143 const char *
2144 itree_bubbletype2str(enum bubbletype t)
2145 {
2146         static char buf[100];
2147 
2148         switch (t) {
2149         case B_FROM:    return L_from;
2150         case B_TO:      return L_to;
2151         case B_INHIBIT: return L_inhibit;
2152         default:
2153                 (void) sprintf(buf, "[unexpected bubbletype: %d]", t);
2154                 return (buf);
2155         }
2156 }
2157 
2158 /*
2159  * itree_fini -- clean up any half-built itrees
2160  */
2161 void
2162 itree_fini(void)
2163 {
2164         if (Ninfo.lut != NULL) {
2165                 itree_free(Ninfo.lut);
2166                 Ninfo.lut = NULL;
2167         }
2168         if (Ninfo.ex) {
2169                 lut_free(Ninfo.ex, iterinfo_destructor, NULL);
2170                 Ninfo.ex = NULL;
2171         }
2172 }