itree.c revision 3e8d8e182b274ca2da0da571da1f62acac10fe6f
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*
* itree.c -- instance tree creation and manipulation
*
* this module provides the instance tree
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include "alloc.h"
#include "out.h"
#include "stable.h"
#include "literals.h"
#include "lut.h"
#include "tree.h"
#include "ptree.h"
#include "itree.h"
#include "ipath.h"
#include "eval.h"
#include "config.h"
/*
* struct info contains the state we keep when expanding a prop statement
* as part of constructing the instance tree. state kept in struct info
* is the non-recursive stuff -- the stuff that doesn't need to be on
* the stack. the rest of the state that is passed between all the
* mutually recursive functions, is required to be on the stack since
* we need to backtrack and recurse as we do the instance tree construction.
*/
struct info {
} Ninfo;
/*
* struct wildcardinfo is used to track wildcarded portions of paths.
*
* for example, if the epname of an event is "c/d" and the path "a/b/c/d"
* exists, the wildcard path ewname is filled in with the path "a/b". when
* matching is done, epname is temporarily replaced with the concatenation
* of ewname and epname. cpstart is set to the (struct config *)
* corresponding to component "c".
*
* a linked list of these structs is used to track the expansion of each
* event node as it is processed in vmatch() --> vmatch_event() calls.
*/
struct wildcardinfo {
enum status {
WC_UNDEFINED, /* struct is not yet initialized */
WC_UNDERCONSTRUCTION, /* wildcard path not yet done */
WC_COMPLETE /* wildcard path done and is in use */
} s;
struct wildcardpath {
int refcount; /* number of event nodes using this */
} *p;
struct wildcardinfo *next;
};
struct node *c);
/*
* the following struct contains the state we build up during
* vertical and horizontal expansion so that generate()
* has everything it needs to construct the appropriate arrows.
* after setting up the state by calling:
* generate_arrownp()
* generate_nork()
* generate_new()
* generate_from()
* generate_to()
* the actual arrow generation is done by calling:
* generate()
*/
static struct {
int generation; /* generation number of arrow set */
int n; /* n value associated with arrow */
int k; /* k value associated with arrow */
} G;
static void
{
}
static void
generate_nork(int n, int k)
{
G.n = n;
G.k = k;
}
static void
generate_new(void)
{
G.generation++;
}
static void
{
G.fromnp = fromeventnp;
}
static void
{
}
static void
{
} else {
}
}
enum childnode_action {
};
static struct node *
{
const char *file;
int line;
return (NULL);
switch (npc->t) {
case T_NUM:
break;
case T_NAME:
break;
default:
"invalid child type %s",
ptree_nodetype2str(npc->t));
}
}
} else if (act == CN_INSTANTIZE) {
int inum;
(unsigned long long)inum;
} else {
}
}
} else {
}
}
return (retp);
}
struct prop_wlk_data {
};
/*
* let oldepname be a subset of epname. return the subsection of epname
* that ends with oldepname. make each component in the path explicitly
* instanced (i.e., with a T_NUM child).
*/
static struct node *
{
int foundmatch = 0;
return (NULL);
/*
* search for the longest path in epname which contains
* oldnode->u.event.epname. set npend to point to just past the
* end of this path.
*/
break;
}
foundmatch = 1;
/* oldepname matched npref up to end */
break;
}
}
}
}
if (foundmatch == 0) {
/*
* if oldepname could not be found in epname, return a
* duplicate of the former. do not try to instantize
* oldepname since it might not be a path.
*/
}
/*
* dup (epname -- npend). all children should be T_NUMs.
*/
int childnum;
} else {
}
} else {
}
}
return (ret);
}
/*
* restriction: oldnode->u.event.epname has to be equivalent to or a subset
* of epname
*/
static struct node *
{
epname);
return (ret);
}
static void
{
/* handle engines by instantizing the entire engine */
/* there are only SERD engines for now */
return;
}
switch (orhs->t) {
case T_NUM:
break;
case T_TIMEVAL:
break;
case T_NAME:
break;
case T_EVENT:
break;
default:
}
}
static struct lut *
{
struct prop_wlk_data pd;
}
/*ARGSUSED*/
static void
{
/* we allocated the lut during itree_create(), so free it */
}
}
/*
* event_cmp -- used via lut_lookup/lut_add on instance tree lut
*/
static int
{
int diff;
return (diff);
return (diff);
return (0);
}
struct event *
{
struct node searcheventnode;
struct node searchenamenode;
searcheventnode.t = T_EVENT;
searchenamenode.t = T_NAME;
}
static struct event *
{
return (ret);
/* wasn't already in tree, allocate it */
return (ret);
}
/*
* hmatch_event -- perform any appropriate horizontal expansion on an event
*
* this routine is used to perform horizontal expansion on both the
* left-hand-side events in a prop, and the right-hand-side events.
* when called to handle a left-side event, nextnp point to the right
* side of the prop that should be passed to hmatch() for each match
* found by horizontal expansion. when no horizontal expansion exists,
* we will still "match" one event for every event found in the list on
* the left-hand-side of the prop because vmatch() already found that
* there's at least one match during vertical expansion.
*/
static void
{
/*
* end of pathname recursion, either we just located
* a left-hand-side event and we're ready to move on
* to the expanding the right-hand-side events, or
* we're further down the recursion and we just located
* a right-hand-side event. the passed-in parameter
* "nextnp" tells us whether we're working on the left
* side and need to move on to nextnp, or if nextnp is
* NULL, we're working on the right side.
*/
if (nextnp) {
/*
* finished a left side expansion, move on to right.
* tell generate() what event we just matched so
* it can be used at the source of any arrows
* we generate as we match events on the right side.
*/
} else {
/*
* finished a right side expansion. tell generate
* the information about the destination and let
* it construct the arrows as appropriate.
*/
}
return;
}
/*
* we only get here when eventnp already has a completely
* instanced epname in it already. so we first recurse
* down to the end of the name and as the recursion pops
* up, we look for opportunities to advance horizontal
* expansions on to the next match. when we do advance
* horizontal expansions, we potentially render all cp
* pointers on all components to the right as invalid,
* so we pass in an "ncp" config handle so matching against
* the config can happen.
*/
if (rematch) {
char *ncp_s;
/* found a matching component name */
continue;
nextnp, 1);
}
}
return; /* no more config to match against */
} else {
nextnp, 0);
}
char *cp_s;
int cp_num;
int ocp_num;
const char *iters;
"hmatch_event: internal error: "
"iterator \"%s\" undefined", iters);
} else {
/* advance dict entry to next match */
}
nextnp, 1);
}
}
/* restore dict entry */
}
}
}
/*
* hmatch -- check for horizontal expansion matches
*
* np points to the things we're matching (like a T_LIST or a T_EVENT)
* and if we're working on a left-side of a prop, nextnp points to
* the other side of the prop that we'll tackle next when this recursion
* bottoms out. when all the events in the entire prop arrow have been
* horizontally expanded, generate() will be called to generate the
* actualy arrow.
*/
static void
{
return; /* all done */
/*
* for each item in the list of events (which could just
* be a single event, or it could get larger in the loop
* below due to horizontal expansion), call hmatch on
* the right side and create arrows to each element.
*/
switch (np->t) {
case T_LIST:
/* loop through the list */
break;
case T_EVENT:
break;
default:
"hmatch: unexpected type: %s",
ptree_nodetype2str(np->t));
}
}
static int
{
return (1);
return (-1); /* our internal version of "all" */
else
"itree_np2nork: internal error type %s",
ptree_nodetype2str(norknp->t));
/*NOTREACHED*/
}
static struct iterinfo *
{
return (ret);
}
/*ARGSUSED*/
static void
{
}
/*
* return 1 if wildcard path for wcp matches another wildcard path;
* return 0 if otherwise.
*/
static int
{
/*
* names must match
*/
return (0);
/*
* children must exist and have the same numerical value
*/
return (0);
return (0);
return (0);
}
/*
* return true only if we have matches for all entries of n1 and
* n2. note that NULL wildcard paths (i.e., both wcp->p->ewname
* and wcp->matchwc->ewname are NULL) will be considered as
* matching paths.
*/
return (1);
return (0);
}
/*
* update epname to include the wildcarded portion
*/
static void
{
struct wildcardinfo *wcp;
if (wcp->s == WC_UNDERCONSTRUCTION) {
wcp->s = WC_COMPLETE;
}
/* path has no wildcard */
return;
/*
* get to this point if a wildcard portion of the path exists.
*
* first set oldepname to the start of the existing epname for use
* in future comparisons, then update epname to include the
* wildcard portion.
*/
}
/*
* restore epname to its former (nonwildcarded) state
*/
static void
{
struct wildcardinfo *wcp;
if (wcp->s == WC_COMPLETE) {
wcp->s = WC_UNDERCONSTRUCTION;
}
/* path has no wildcard */
return;
}
enum wildcard_action {
WA_NONE, /* do not do any wildcards */
WA_SINGLE, /* do wildcard only for current cp node */
WA_ALL /* do wildcards for all cp nodes */
};
static void
{
struct wildcardinfo *wcp;
char *cp_s;
int cp_num;
/*
* get to this point if the pathname matched the config
* (but not necessarily a match at the end). first check
* for any matching wildcard paths.
*/
return;
return;
}
return; /* no more config to match against */
! (wcp->s == WC_UNDERCONSTRUCTION &&
dowildcard == WA_SINGLE)) {
/* found a matching component name */
/*
* an explicit instance number was given
* in the source. so only consider this
* a configuration match if the number
* also matches.
*/
continue;
} else {
const char *iters;
/*
* vertical iterator. look it up in
* the appropriate lut and if we get
* back a value it is either one that we
* set earlier, in which case we record
* the new value for this iteration and
* keep matching, or it is one that was
* set by an earlier reference to the
* iterator, in which case we only consider
* this a configuration match if the number
* matches cp_num.
*/
/* we're the first use, record our np */
(void *)iters,
/*
* we're the first use, back again
* for another iteration. so update
* the num bound to this iterator in
* the lut.
*/
/*
* an earlier reference to this
* iterator bound it to a different
* instance number, so there's no
* match here after all.
*
* however, it's possible that this
* component should really be part of
* the wildcard. we explore this by
* forcing this component into the
* wildcarded section.
*
* for an more details of what's
* going to happen now, see
* comments block below entitled
* "forcing components into
* wildcard path".
*/
if (dowildcard == WA_ALL &&
wcp->s == WC_UNDERCONSTRUCTION) {
}
continue;
}
}
/*
* if wildcarding was done in a call earlier in the
* stack, record the current cp as the first
* matching and nonwildcarded cp.
*/
if (dowildcard == WA_ALL &&
wcp->s == WC_UNDERCONSTRUCTION)
/*
* if this was an IT_HORIZONTAL name,
* hmatch() will use the cp to expand
* all matches horizontally into a list.
* we know the list will contain at least
* one element (the one we just matched),
* so we just store cp and let hmatch_event()
* do the rest.
*
* recurse on to next component. note that
* wildcarding is now turned off.
*/
/*
* forcing components into wildcard path:
*
* if this component is the first match, force it
* to be part of the wildcarded path and see if we
* can get additional matches. repeat call to
* vmatch_event() with the same np, making sure
* wildcarding is forced for this component alone
* and not its peers by specifying vmatch_event(
* ..., WA_SINGLE). in other words, in the call to
* vmatch_event() below, there should be no loop
* over cp's peers since that is being done in the
* current loop [i.e., the loop we're in now].
*
* here's an example. suppose we have the
* definition
* event foo@x/y
* and configuration
*
* the code up to this point will treat "a0" as the
* nonwildcarded part, resulting in the instanced
* event
*
* in the configuration we have to force "x0" into
* the wildcarded part of the path. the following
* call to vmatch_event(..., WA_SINGLE) does this.
* by doing so, we discover the wildcarded part
*
* the following call to vmatch_event() is also
* needed to properly handle the configuration
*
* the recursions into vmatch_event() will start
* off uncovering "b0" as the wildcarded part and
* "x0" as the start of the nonwildcarded path.
* however, the next recursion will not result in a
* match since there is no "y" following "x0". the
* if "x0" is forced to be a part of the wildcarded
* path.
*/
if (dowildcard == WA_ALL &&
wcp->s == WC_UNDERCONSTRUCTION) {
}
/*
* hmatch() finished iterating through
* the configuration as described above, so
* don't continue iterating here.
*/
return;
}
wcp->s == WC_UNDERCONSTRUCTION) {
/*
* no matching cp, and we are constructing our own
* wildcard path. (in other words, we are not
* referencing a wildcard path created for an
* earlier event.)
*
* add wildcard entry, then recurse on to config
* child
*/
} else {
cpnode);
}
/*
* back out last addition to ewname and continue
* with loop
*/
} else {
}
/*
* return if wildcarding is done only for this cp
*/
if (dowildcard == WA_SINGLE)
return;
}
}
}
/*
* for the event node np, which will be subjected to pathname
* information. this struct will be inserted into the first location in
* the list that starts with *wcproot.
*
* cp is the starting node of the configuration; cpstart, which is output,
* is the starting node of the nonwildcarded portion of the path.
*/
static void
{
/*
* create entry for np
*/
wcpnew->s = WC_UNDERCONSTRUCTION;
/*
* search all completed entries for an epname whose first entry
* matches. note that NULL epnames are considered valid and can be
* matched.
*/
/*
* if we find a match in a completed entry, set
* matchwc to indicate that we would like to match
* it. it is necessary to do this since wildcards
* for each event are constructed independently.
*/
break;
}
}
}
static void
{
struct wildcardinfo *wcp;
switch (wcp->s) {
case WC_UNDERCONSTRUCTION:
case WC_COMPLETE:
break;
default:
break;
}
}
/*
* vmatch -- find the next vertical expansion match in the config database
*
* this routine is called with three node pointers:
* np -- the parse we're matching
* lnp -- the rest of the list we're currently working on
* anp -- the rest of the arrow we're currently working on
*
* the expansion matching happens via three types of recursion:
*
* - when given an arrow, handle the left-side and then recursively
* handle the right side (which might be another cascaded arrow).
*
* - when handling one side of an arrow, recurse through the T_LIST
* to get to each event (or just move on to the event if there
* is a single event instead of a list) since the arrow parse
* trees recurse left, we actually start with the right-most
* event list in the prop statement and work our way towards
* the left-most event list.
*
* - when handling an event, recurse down each component of the
* pathname, matching in the config database and recording the
* matches in the explicit iterator dictionary as we go.
*
* when the bottom of this matching recursion is met, meaning we have
* set the "cp" pointers on all the names in the entire statement,
* we call hmatch() which does it's own recursion to handle horizontal
* expandsion and then call generate() to generate nodes, bubbles, and
* arrows in the instance tree. generate() looks at the cp pointers to
* see what instance numbers were matched in the configuration database.
*
* when horizontal expansion appears, vmatch() finds only the first match
* and hmatch() then takes the horizontal expansion through all the other
* matches when generating the arrows in the instance tree.
*
* the "infop" passed down through the recursion contains a dictionary
* of the explicit iterators (all the implicit iterators have been converted
* to explicit iterators when the parse tree was created by tree.c), which
* allows things like this to work correctly:
*
* prop error.a@x[n]/y/z -> error.b@x/y[n]/z -> error.c@x/y/z[n];
*
* during the top level call, the explicit iterator "n" will match an
* instance number in the config database, and the result will be recorded
* in the explicit iterator dictionary and passed down via "infop". so
* when the recursive call tries to match y[n] in the config database, it
* will only match the same instance number as x[n] did since the dictionary
* is consulted to see if "n" took on a value already.
*
* at any point during the recursion, match*() can return to indicate
* a match was not found in the config database and that the caller should
* move on to the next potential match, if any.
*
* constraints are completely ignored by match(), so the statement:
*
* prop error.a@x[n] -> error.b@x[n] {n != 0};
*
* might very well match x[0] if it appears in the config database. it
* is the generate() routine that takes that match and then decides what
* arrow, if any, should be generated in the instance tree. generate()
* looks at the explicit iterator dictionary to get values like "n" in
* the above example so that it can evaluate constraints.
*
*/
static void
{
if (lnp)
else if (anp)
else {
/* end of vertical match recursion */
for (;;) {
generate_new(); /* new set of arrows */
} else {
break;
}
}
}
return;
}
switch (np->t) {
case T_EVENT: {
break;
}
case T_LIST:
break;
case T_ARROW:
break;
default:
"vmatch: unexpected type: %s",
ptree_nodetype2str(np->t));
}
}
static void
{
return;
switch (np->t) {
case T_NAME:
break;
case T_LIST:
break;
case T_ARROW:
break;
case T_EVENT:
break;
}
}
/*
* itree_create -- apply the current config to the current parse tree
*
* returns a lut mapping fully-instance-qualified names to struct events.
*
*/
struct lut *
{
}
}
return (retval);
}
void
{
}
int
{
int num1;
int num2;
} else {
}
} else {
}
}
}
else
return (-1);
return (1);
else
}
void
{
}
/*ARGSUSED*/
static void
{
struct plut_wlk_data propd;
else
}
/* Print only TO bubbles in this loop */
continue;
}
/* Print only INHIBIT bubbles in this loop */
continue;
}
/* Print only FROM bubbles in this loop */
continue;
}
}
static void
{
struct constraintlist *cp;
else
else
}
return;
}
/* Display anything from the propogation node? */
}
}
}
void
{
}
/*ARGSUSED*/
static void
{
/* Free the properties */
/* Free my bubbles */
/*
* Free arrows if they are FROM me. Free arrowlists on
* other types of bubbles (but not the attached arrows,
* which will be freed when we free the originating
* bubble.
*/
else
itree_free_arrowlists(bub, 0);
}
}
static void
{
}
static struct bubble *
{
/* Use existing bubbles as appropriate when possible */
/* see if an existing "to" bubble works for us */
return (curr); /* matched gen number */
return (curr); /* coalesce K==1 bubbles */
}
/* see if an existing "from" bubble works for us */
return (curr);
}
}
else
return (newb);
}
struct bubble *
{
for (;;) {
else
return (next);
/* bubble was empty, skip it */
}
}
static void
{
}
else
}
static struct arrow *
{
/*
* Set default delays, then try to re-set them from
* any within() constraints.
*/
return (NULL);
}
return (newa);
}
/* returns false if traits show that arrow should not be added after all */
static int
{
/*
* search for the within values first on the declaration of
* the destination event, and then on the prop. this allows
* one to specify a "default" within by putting it on the
* declaration, but then allow overriding on the prop statement.
*/
/*
* handle any global constraints inherited from the
* "fromev" event's declaration
*/
#ifdef notdef
/* XXX not quite ready to evaluate constraints from decls yet */
(void) itree_add_constraint(ap,
#endif /* notdef */
/* handle constraints on the from event in the prop statement */
return (0); /* constraint disallows arrow */
/*
* handle any global constraints inherited from the
* "toev" event's declaration
*/
#ifdef notdef
/* XXX not quite ready to evaluate constraints from decls yet */
(void) itree_add_constraint(ap,
#endif /* notdef */
/* handle constraints on the to event in the prop statement */
return (0); /* constraint disallows arrow */
/* if we came up with any deferred constraints, add them to arrow */
return (1); /* constraints allow arrow */
}
/*
* Set within() constraint. If the constraint were set multiple times,
* the last one would "win".
*/
static void
{
/* end of expressions list */
return;
switch (xpr->t) {
case T_LIST:
return;
case T_FUNC:
return;
switch (arglist->t) {
case T_TIMEVAL:
break;
case T_NAME:
break;
case T_LIST:
case T_TIMEVAL:
break;
case T_NAME:
break;
default:
}
break;
default:
}
break;
default:
return;
}
}
static void
{
if (arrows_too) {
}
}
}
struct arrowlist *
{
else
return (next);
}
static struct constraintlist *
{
struct constraintlist *curr;
struct constraintlist *newc;
else
return (newc);
}
struct constraintlist *
{
struct constraintlist *next;
else
return (next);
}
static void
{
}
}
const char *
itree_bubbletype2str(enum bubbletype t)
{
static char buf[100];
switch (t) {
default:
return (buf);
}
}
/*
* itree_fini -- clean up any half-built itrees
*/
void
itree_fini(void)
{
}
}
}