/* * The machine is laid out as a sequence of integers in the walker. * The form described above is only used inside the preprocessor. * Each machine state is one of the following sequence: * * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1 * or * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1 * or * ACCEPT <accept table index> -1 * * The accept table is in the form: * * <tree index_1> ...<tree_index_m> -1 * */ enum{ FASTLIM, TABLE, FAIL, ACCEPT, TABLE2, EOT = -1, /* special machine state */ HANG = -1,}; /* * In order for the walker to access the labelled leaves of a pattern, * a table (mistakenly) called the path table is generated (see sym.c). * This table contains the following possible values: * * ePush follow the children link in the walker skeleton. * ePop Pop up to parent. * eNext follow the siblings link. * eEval <arg> The current node is a labelled leaf whose label id * is the integer <arg>. * eStop All done. stop! * * The table is interpreted by the _getleaves routine in the walker. */enum{ eSTOP = 0, ePOP = -1, eEVAL = -2, eNEXT = -3, ePUSH = -4, /* * Tags that indicate the type of a value * max values for shorts * CHANGE CAREFULLY!!! */ M_BRANCH = 0x4000, M_NODE = 0, M_LABEL = 0x2000, MAX_NODE_VALUE = 0x1fff, MTAG_SHIFT = 9,}; #define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE)) /* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */#define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)#define MI_DEFINED(x) ((x)!=-1)#define MI_LABEL(x) (((x)&M_LABEL)!=0)#define MI_BRANCH(x) (((x)&M_BRANCH)!=0) /* build a tagged value */#define MV_NODE(x) (x)#define MV_BRANCH(x) ((x)|M_BRANCH)#define MV_LABEL(x) ((x)|M_LABEL) #include "symbols.h" /* limits *//* * The depth of a pattern must be 7 or less. Otherwise the type of he * partial mask in skeleton must be changed */#define MAXDEPTH 7 /* modes */#define xTOPDOWN 3#define xABORT 2#define xREWRITE 1#define xDEFER 0 /* macros */#define tDO(m) _do((m)->skel, (m), 1)#define REWRITE return(_m->cost = cost, xREWRITE)#define TOPDOWN return(_m->cost = cost, xTOPDOWN)#define ABORT return(xABORT) /* * REORDER macro allows a knowledgeable user to change the order * of evaluation of the leaves. */#ifndef REORDER#define REORDER(list) _evalleaves(list)#endif#define EVAL REORDER(_ll) #define mpush(s,m) (m)->next = s, s = m /* skeleton structure */typedef struct skeleton skeleton;typedef struct __match __match;typedef struct __partial __partial;typedef int labelset; /* a bit vector of labels */ struct __partial { short treeno; short bits;}; struct skeleton { skeleton *sibling; skeleton *leftchild; /* leftmost child */ skeleton *rightchild; /* rightmost child */ NODEPTR root; NODEPTR parent; /* our parent */ int nson; int treecnt; __match *succ[MAXLABELS]; __partial *partial; __match *winner; COST mincost;}; struct __match { __match **lleaves; /* labelled leaves */ skeleton *skel; /* back pointer to skeleton node */ COST cost; short tree; short mode;}; /* ZEROCOST, and ADDCOST allows easy implementation of the common * operation of just equating the cost of a match to be the sum * of the costs of the labelled leaves. */#ifdef ADDCOST#define DEFAULT_COST sumleaves(_ll)COST sumleaves(__match **list){ COST cost; cost = ZEROCOST; for(; *list; list++) ADDCOST((cost),(*list)->cost); return cost;}#endif/* * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1 * for detail of the matching algorithm */ #ifndef va_start#include <stdarg.h>#endif/* from libc.h */extern void* malloc(long);extern void free(void*);extern void abort(void);#define _twig_assert(a,str) \ do{if(!(a)){\ fprintf(stderr, "twig internal error %s\n", (str));\ abort();\ }}while(0) /* these are user defined, so can be macros */#ifndef mtValueint mtValue(NODEPTR);#endif#ifndef mtSetNodesvoid mtSetNodes(NODEPTR, int, NODEPTR);#endif#ifndef mtGetNodesNODEPTR mtGetNodes(NODEPTR, int);#endif /* made by twig proper */NODEPTR mtAction(int, __match **, skeleton *);short mtEvalCost(__match *, __match **, skeleton *); /* stuff defined here */void _addmatches(int, skeleton *, __match *);void _closure(int, int, skeleton *);void _do(skeleton *, __match *, int);void _evalleaves(__match **);__match **_getleaves(__match *, skeleton *);int _machstep(short, short);void _match(void);void _matchinit(void);void _merge(skeleton *, skeleton *);NODEPTR _mtG(NODEPTR, ...);skeleton *_walk(skeleton *, int);__match *_allocmatch(void);skeleton *_allocskel(void);__partial *_allocpartial(void);void _freematch(__match *);void _freeskel(skeleton *);void _freepartial(__partial *);void _prskel(skeleton *, int); int mtDebug = 0;int treedebug = 0;extern short mtStart;extern short mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];#ifdef LINE_XREF extern short mtLine[];#endif #ifndef MPBLOCKSIZ#define MPBLOCKSIZ 10000#endif__match *_mpblock[MPBLOCKSIZ], **_mpbtop; /* * See sym.h in the preprocessor for details * Basically used to support eh $%n$ construct. */__match **_getleaves(__match *mp, skeleton *skp){ skeleton *stack[MAXDEPTH]; skeleton **stp = stack; short *sip = &mtPaths[mtPathStart[mp->tree]]; __match **mmp = _mpbtop; __match **mmp2 = mmp; _mpbtop += *sip++ + 1; _twig_assert(_mpbtop <= &_mpblock[MPBLOCKSIZ], "match block overflow"); for(;;) switch(*sip++){ case ePUSH: *stp++ = skp; skp = skp->leftchild; break; case eNEXT: skp = skp->sibling; break; case eEVAL: mp = skp->succ[M_DETAG(*sip++)]; _twig_assert(mp != 0, "bad eEVAL"); *mmp++ = mp; break; case ePOP: skp = *--stp; break; case eSTOP: *mmp = 0; return mmp2; }} void_do(skeleton *sp, __match *winner, int evalall){ skeleton *skel; if(winner == 0) { _prskel(sp, 0); fprintf(stderr, "no winner"); return; } skel = winner->skel; if(winner->mode == xDEFER || evalall && winner->mode != xTOPDOWN) REORDER(winner->lleaves); skel->root = mtAction(winner->tree, winner->lleaves, sp); mtSetNodes(skel->parent, skel->nson, skel->root);} void_evalleaves(__match **mpp){ __match *mp; while(*mpp){ mp = *mpp++; _do(mp->skel, mp, 1); }} skeleton *_walk(skeleton *sp, int ostate){ int state, nstate, nson; __partial *pp; __match *mp; skeleton *nsp, *lastchild = 0; NODEPTR son, root; root = sp->root; nson = 1; sp->mincost = INFINITY; state = _machstep(ostate, mtValue(root)); while(son = mtGetNodes(root, nson)){ nstate = _machstep(state, MV_BRANCH(nson)); nsp = _allocskel(); nsp->root = son; nsp->parent = root; nsp->nson = nson; _walk(nsp, nstate); if(COSTLESS(nsp->mincost, INFINITY)){ _twig_assert(nsp->winner->mode == xREWRITE, "bad mode"); if(mtDebug || treedebug) { fprintf(stderr, "rewrite\n"); _prskel(nsp, 0); } _do(nsp, nsp->winner, 0); _freeskel(nsp); continue; } _merge(sp, nsp); if(lastchild == 0) sp->leftchild = nsp; else lastchild->sibling = nsp; lastchild = nsp; nson++; } for(pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++) if(pp->bits & 01){ mp = _allocmatch(); mp->tree = pp->treeno; _addmatches(ostate, sp, mp); } if(son == 0 && nson == 1) _closure(state, ostate, sp); sp->rightchild = lastchild; if(root == 0){ COST c; __match *win; int i; nsp = sp->leftchild; c = INFINITY; win = 0; for(i = 0; i < MAXLABELS; i++){ mp = nsp->succ[i]; if(mp != 0 && COSTLESS(mp->cost, c)){ c = mp->cost; win = mp; } } if(mtDebug || treedebug) _prskel(nsp, 0); _do(nsp, win, 0); } if(mtDebug) _prskel(sp, 0); return sp;} static short _nodetab[MAXNDVAL], _labeltab[MAXLABELS]; /* * Convert the start state which has a large branching factor into * a index table. This must be called before the matcher is used. */void_matchinit(void){ short *sp; for(sp = _nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG; for(sp = _labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG; sp = &mtTable[mtStart]; _twig_assert(*sp == TABLE, "mtTable[mtStart]!=TABLE"); for(++sp; *sp != -1; sp += 2){ if(MI_NODE(*sp)) _nodetab[M_DETAG(*sp)] = sp[1]; else if(MI_LABEL(*sp)) _labeltab[M_DETAG(*sp)] = sp[1]; }} int_machstep(short state, short input){ short *stp = &mtTable[state]; int start = 0; if(state == HANG) return input == MV_BRANCH(1) ? mtStart : HANG;rescan: if(stp == &mtTable[mtStart]){ if(MI_NODE(input)) return _nodetab[M_DETAG(input)]; if(MI_LABEL(input)) return _labeltab[M_DETAG(input)]; } for(;;){ if(*stp == ACCEPT) stp += 2; if(*stp == TABLE){ stp++; while(*stp != -1) if(input == *stp) return stp[1]; else stp += 2; stp++; } if(*stp != FAIL){ if(start) return HANG; else{ stp = &mtTable[mtStart]; start = 1; goto rescan; } }else{ stp = &mtTable[stp[1]]; goto rescan; } }} void_addmatches(int ostate, skeleton *sp, __match *np){ int label; int state; __match *mp; label = mtMap[np->tree]; /* * this is a very poor substitute for good design of the DFA. * What we need is a special case that allows any label to be accepted * by the start state but we don't want the start state to recognize * them after a failure. */ state = _machstep(ostate, MV_LABEL(label)); if(ostate != mtStart && state == HANG){ _freematch(np); return; } np->lleaves = _getleaves(np, sp); np->skel = sp; if((np->mode = mtEvalCost(np, np->lleaves, sp)) == xABORT){ _freematch(np); return; } if(mp = sp->succ[label]){ if(!COSTLESS(np->cost, mp->cost)){ _freematch(np); return; } _freematch(mp); } if(COSTLESS(np->cost, sp->mincost)){ if(np->mode == xREWRITE){ sp->mincost = np->cost; sp->winner = np; }else{ sp->mincost = INFINITY; sp->winner = 0; } } sp->succ[label] = np; _closure(state, ostate, sp);} void_closure(int state, int ostate, skeleton *skp){ short *sp = &mtTable[state]; __match *mp; if(state == HANG || *sp != ACCEPT) return; for(sp = &mtAccept[sp[1]]; *sp != -1; sp += 2) if(sp[1] == 0){ mp = _allocmatch(); mp->tree = *sp; _addmatches(ostate, skp, mp); }else{ __partial *pp; __partial *lim = &skp->partial[skp->treecnt]; for(pp = skp->partial; pp < lim; pp++) if(pp->treeno == *sp) break; if(pp == lim){ skp->treecnt++;Lines 1–500 of 753. Load more
/* * The machine is laid out as a sequence of integers in the walker. * The form described above is only used inside the preprocessor. * Each machine state is one of the following sequence: * * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1 * or * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1 * or * ACCEPT <accept table index> -1 * * The accept table is in the form: * * <tree index_1> ...<tree_index_m> -1 * */ enum{ FASTLIM, TABLE, FAIL, ACCEPT, TABLE2, EOT = -1, /* special machine state */ HANG = -1, }; /* * In order for the walker to access the labelled leaves of a pattern, * a table (mistakenly) called the path table is generated (see sym.c). * This table contains the following possible values: * * ePush follow the children link in the walker skeleton. * ePop Pop up to parent. * eNext follow the siblings link. * eEval <arg> The current node is a labelled leaf whose label id * is the integer <arg>. * eStop All done. stop! * * The table is interpreted by the _getleaves routine in the walker. */ enum{ eSTOP = 0, ePOP = -1, eEVAL = -2, eNEXT = -3, ePUSH = -4, /* * Tags that indicate the type of a value * max values for shorts * CHANGE CAREFULLY!!! */ M_BRANCH = 0x4000, M_NODE = 0, M_LABEL = 0x2000, MAX_NODE_VALUE = 0x1fff, MTAG_SHIFT = 9, }; #define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE)) /* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */ #define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0) #define MI_DEFINED(x) ((x)!=-1) #define MI_LABEL(x) (((x)&M_LABEL)!=0) #define MI_BRANCH(x) (((x)&M_BRANCH)!=0) /* build a tagged value */ #define MV_NODE(x) (x) #define MV_BRANCH(x) ((x)|M_BRANCH) #define MV_LABEL(x) ((x)|M_LABEL) #include "symbols.h" /* limits */ /* * The depth of a pattern must be 7 or less. Otherwise the type of he * partial mask in skeleton must be changed */ #define MAXDEPTH 7 /* modes */ #define xTOPDOWN 3 #define xABORT 2 #define xREWRITE 1 #define xDEFER 0 /* macros */ #define tDO(m) _do((m)->skel, (m), 1) #define REWRITE return(_m->cost = cost, xREWRITE) #define TOPDOWN return(_m->cost = cost, xTOPDOWN) #define ABORT return(xABORT) /* * REORDER macro allows a knowledgeable user to change the order * of evaluation of the leaves. */ #ifndef REORDER #define REORDER(list) _evalleaves(list) #endif #define EVAL REORDER(_ll) #define mpush(s,m) (m)->next = s, s = m /* skeleton structure */ typedef struct skeleton skeleton; typedef struct __match __match; typedef struct __partial __partial; typedef int labelset; /* a bit vector of labels */ struct __partial { short treeno; short bits; }; struct skeleton { skeleton *sibling; skeleton *leftchild; /* leftmost child */ skeleton *rightchild; /* rightmost child */ NODEPTR root; NODEPTR parent; /* our parent */ int nson; int treecnt; __match *succ[MAXLABELS]; __partial *partial; __match *winner; COST mincost; }; struct __match { __match **lleaves; /* labelled leaves */ skeleton *skel; /* back pointer to skeleton node */ COST cost; short tree; short mode; }; /* ZEROCOST, and ADDCOST allows easy implementation of the common * operation of just equating the cost of a match to be the sum * of the costs of the labelled leaves. */ #ifdef ADDCOST #define DEFAULT_COST sumleaves(_ll) COST sumleaves(__match **list) { COST cost; cost = ZEROCOST; for(; *list; list++) ADDCOST((cost),(*list)->cost); return cost; } #endif /* * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1 * for detail of the matching algorithm */ #ifndef va_start #include <stdarg.h> #endif /* from libc.h */ extern void* malloc(long); extern void free(void*); extern void abort(void); #define _twig_assert(a,str) \ do{if(!(a)){\ fprintf(stderr, "twig internal error %s\n", (str));\ abort();\ }}while(0) /* these are user defined, so can be macros */ #ifndef mtValue int mtValue(NODEPTR); #endif #ifndef mtSetNodes void mtSetNodes(NODEPTR, int, NODEPTR); #endif #ifndef mtGetNodes NODEPTR mtGetNodes(NODEPTR, int); #endif /* made by twig proper */ NODEPTR mtAction(int, __match **, skeleton *); short mtEvalCost(__match *, __match **, skeleton *); /* stuff defined here */ void _addmatches(int, skeleton *, __match *); void _closure(int, int, skeleton *); void _do(skeleton *, __match *, int); void _evalleaves(__match **); __match **_getleaves(__match *, skeleton *); int _machstep(short, short); void _match(void); void _matchinit(void); void _merge(skeleton *, skeleton *); NODEPTR _mtG(NODEPTR, ...); skeleton *_walk(skeleton *, int); __match *_allocmatch(void); skeleton *_allocskel(void); __partial *_allocpartial(void); void _freematch(__match *); void _freeskel(skeleton *); void _freepartial(__partial *); void _prskel(skeleton *, int); int mtDebug = 0; int treedebug = 0; extern short mtStart; extern short mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[]; #ifdef LINE_XREF extern short mtLine[]; #endif #ifndef MPBLOCKSIZ #define MPBLOCKSIZ 10000 #endif __match *_mpblock[MPBLOCKSIZ], **_mpbtop; /* * See sym.h in the preprocessor for details * Basically used to support eh $%n$ construct. */ __match ** _getleaves(__match *mp, skeleton *skp) { skeleton *stack[MAXDEPTH]; skeleton **stp = stack; short *sip = &mtPaths[mtPathStart[mp->tree]]; __match **mmp = _mpbtop; __match **mmp2 = mmp; _mpbtop += *sip++ + 1; _twig_assert(_mpbtop <= &_mpblock[MPBLOCKSIZ], "match block overflow"); for(;;) switch(*sip++){ case ePUSH: *stp++ = skp; skp = skp->leftchild; break; case eNEXT: skp = skp->sibling; break; case eEVAL: mp = skp->succ[M_DETAG(*sip++)]; _twig_assert(mp != 0, "bad eEVAL"); *mmp++ = mp; break; case ePOP: skp = *--stp; break; case eSTOP: *mmp = 0; return mmp2; } } void _do(skeleton *sp, __match *winner, int evalall) { skeleton *skel; if(winner == 0) { _prskel(sp, 0); fprintf(stderr, "no winner"); return; } skel = winner->skel; if(winner->mode == xDEFER || evalall && winner->mode != xTOPDOWN) REORDER(winner->lleaves); skel->root = mtAction(winner->tree, winner->lleaves, sp); mtSetNodes(skel->parent, skel->nson, skel->root); } void _evalleaves(__match **mpp) { __match *mp; while(*mpp){ mp = *mpp++; _do(mp->skel, mp, 1); } } skeleton * _walk(skeleton *sp, int ostate) { int state, nstate, nson; __partial *pp; __match *mp; skeleton *nsp, *lastchild = 0; NODEPTR son, root; root = sp->root; nson = 1; sp->mincost = INFINITY; state = _machstep(ostate, mtValue(root)); while(son = mtGetNodes(root, nson)){ nstate = _machstep(state, MV_BRANCH(nson)); nsp = _allocskel(); nsp->root = son; nsp->parent = root; nsp->nson = nson; _walk(nsp, nstate); if(COSTLESS(nsp->mincost, INFINITY)){ _twig_assert(nsp->winner->mode == xREWRITE, "bad mode"); if(mtDebug || treedebug) { fprintf(stderr, "rewrite\n"); _prskel(nsp, 0); } _do(nsp, nsp->winner, 0); _freeskel(nsp); continue; } _merge(sp, nsp); if(lastchild == 0) sp->leftchild = nsp; else lastchild->sibling = nsp; lastchild = nsp; nson++; } for(pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++) if(pp->bits & 01){ mp = _allocmatch(); mp->tree = pp->treeno; _addmatches(ostate, sp, mp); } if(son == 0 && nson == 1) _closure(state, ostate, sp); sp->rightchild = lastchild; if(root == 0){ COST c; __match *win; int i; nsp = sp->leftchild; c = INFINITY; win = 0; for(i = 0; i < MAXLABELS; i++){ mp = nsp->succ[i]; if(mp != 0 && COSTLESS(mp->cost, c)){ c = mp->cost; win = mp; } } if(mtDebug || treedebug) _prskel(nsp, 0); _do(nsp, win, 0); } if(mtDebug) _prskel(sp, 0); return sp; } static short _nodetab[MAXNDVAL], _labeltab[MAXLABELS]; /* * Convert the start state which has a large branching factor into * a index table. This must be called before the matcher is used. */ void _matchinit(void) { short *sp; for(sp = _nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG; for(sp = _labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG; sp = &mtTable[mtStart]; _twig_assert(*sp == TABLE, "mtTable[mtStart]!=TABLE"); for(++sp; *sp != -1; sp += 2){ if(MI_NODE(*sp)) _nodetab[M_DETAG(*sp)] = sp[1]; else if(MI_LABEL(*sp)) _labeltab[M_DETAG(*sp)] = sp[1]; } } int _machstep(short state, short input) { short *stp = &mtTable[state]; int start = 0; if(state == HANG) return input == MV_BRANCH(1) ? mtStart : HANG; rescan: if(stp == &mtTable[mtStart]){ if(MI_NODE(input)) return _nodetab[M_DETAG(input)]; if(MI_LABEL(input)) return _labeltab[M_DETAG(input)]; } for(;;){ if(*stp == ACCEPT) stp += 2; if(*stp == TABLE){ stp++; while(*stp != -1) if(input == *stp) return stp[1]; else stp += 2; stp++; } if(*stp != FAIL){ if(start) return HANG; else{ stp = &mtTable[mtStart]; start = 1; goto rescan; } }else{ stp = &mtTable[stp[1]]; goto rescan; } } } void _addmatches(int ostate, skeleton *sp, __match *np) { int label; int state; __match *mp; label = mtMap[np->tree]; /* * this is a very poor substitute for good design of the DFA. * What we need is a special case that allows any label to be accepted * by the start state but we don't want the start state to recognize * them after a failure. */ state = _machstep(ostate, MV_LABEL(label)); if(ostate != mtStart && state == HANG){ _freematch(np); return; } np->lleaves = _getleaves(np, sp); np->skel = sp; if((np->mode = mtEvalCost(np, np->lleaves, sp)) == xABORT){ _freematch(np); return; } if(mp = sp->succ[label]){ if(!COSTLESS(np->cost, mp->cost)){ _freematch(np); return; } _freematch(mp); } if(COSTLESS(np->cost, sp->mincost)){ if(np->mode == xREWRITE){ sp->mincost = np->cost; sp->winner = np; }else{ sp->mincost = INFINITY; sp->winner = 0; } } sp->succ[label] = np; _closure(state, ostate, sp); } void _closure(int state, int ostate, skeleton *skp) { short *sp = &mtTable[state]; __match *mp; if(state == HANG || *sp != ACCEPT) return; for(sp = &mtAccept[sp[1]]; *sp != -1; sp += 2) if(sp[1] == 0){ mp = _allocmatch(); mp->tree = *sp; _addmatches(ostate, skp, mp); }else{ __partial *pp; __partial *lim = &skp->partial[skp->treecnt]; for(pp = skp->partial; pp < lim; pp++) if(pp->treeno == *sp) break; if(pp == lim){ skp->treecnt++;