Return to machine.c CVS log

Up to [Research Unix] / researchv10no / cmd / twig

Annotation of researchv10no/cmd/twig/machine.c, revision 1.1

1.1     ! root        1: #include "common.h"
        !             2: #include "code.h"
        !             3: #include "sym.h"
        !             4: #include "machine.h"
        !             5: 
        !             6: int gen_table2;                /* generate type two tables */
        !             7: struct machine_node *machine = NULL;
        !             8: static int depth;
        !             9: 
        !            10: static struct machine_node *
        !            11: get_state()
        !            12: {
        !            13:        struct machine_node *mp = (struct machine_node *)
        !            14:                                malloc (sizeof (struct machine_node));
        !            15:        assert (mp!=NULL);
        !            16:        mp->inp.value = -1;
        !            17:        mp->nst = NULL;
        !            18:        mp->link = NULL;
        !            19:        mp->fail = NULL;
        !            20:        mp->match = NULL;
        !            21:        return(mp);
        !            22: }
        !            23: 
        !            24: add_match(s, tp, depth)
        !            25:        struct machine_node *s;
        !            26:        LabelData *tp;
        !            27:        int depth;
        !            28: {
        !            29:        struct match *mp = (struct match *) malloc (sizeof (struct match));
        !            30: 
        !            31:        assert (mp!=NULL);
        !            32:        mp->next = s->match;
        !            33:        mp->depth = depth;
        !            34:        mp->tree = tp;
        !            35:        s->match = mp;
        !            36: }
        !            37:        
        !            38: /*
        !            39:  * Build a trie from the path strings.  Failure transition are added later.
        !            40:  */
        !            41: cgotofn(tp)
        !            42:        LabelData *tp;
        !            43: {
        !            44:        struct machine_input inp;
        !            45:        int ret;
        !            46:        register struct machine_node *s;
        !            47:        register int quit = 0;
        !            48: 
        !            49:        if (machine==NULL) {
        !            50:                /* first time thru */
        !            51:                machine = get_state();
        !            52:        }
        !            53:        s = machine;
        !            54:        depth = -1;
        !            55: 
        !            56:        assert (tp->tree!=NULL);
        !            57:        path_setup (tp->tree);
        !            58: 
        !            59:        for(;;) {
        !            60:                ret = path_getsym(&inp);
        !            61: 
        !            62:                /* no more paths */
        !            63:                if (ret == EOF)
        !            64:                        break;
        !            65: 
        !            66:                if (ret == NULL) {
        !            67:                        /*
        !            68:                         * the end of the path.  Add a match to the
        !            69:                         * accepting state.
        !            70:                         */
        !            71:                        assert ((depth&01)==0); /* make sure it's even */
        !            72:                        add_match(s, tp, depth >> 1);
        !            73:                        s = machine;
        !            74:                        depth = -1;
        !            75:                        ntrees++;
        !            76:                        continue;
        !            77:                }
        !            78: 
        !            79:                while (!MI_EQUAL(s->inp, inp)) {
        !            80:                        if (!MI_DEFINED(s->inp.value) || s->link == NULL) {
        !            81:                                if (MI_DEFINED(s->inp.value)) {
        !            82:                                        /*
        !            83:                                         * The trie must be split here
        !            84:                                         */
        !            85:                                        s->link = get_state();
        !            86:                                        s = s->link;
        !            87:                                }
        !            88:                                /*
        !            89:                                 * Fill in the state
        !            90:                                 */
        !            91:                                s->inp = inp;
        !            92:                                s->nst = get_state();
        !            93:                                s = s->nst;
        !            94:                                depth++;
        !            95:                                break;
        !            96:                        } else s = s->link;
        !            97:                }
        !            98:                if (MI_EQUAL(s->inp, inp)) {
        !            99:                        s = s->nst;
        !           100:                        depth++;
        !           101:                }
        !           102:        }
        !           103: }
        !           104: 
        !           105: /* print out the machine for debugging */
        !           106: machine_print(mp)
        !           107:        struct machine_node *mp;
        !           108: {
        !           109:        register struct machine_node *mp2;
        !           110:        struct machine_node *fail;
        !           111:        struct match *match, *p;
        !           112: 
        !           113:        if (mp==NULL)
        !           114:                return;
        !           115:        printf("%x %d:", mp, mp->index);
        !           116:        if((fail = mp->fail))
        !           117:                printf("\tfail %x", fail);
        !           118:        if((match = mp->match)) {
        !           119:                printf("\taccept ");
        !           120:                for(p = match; p!=NULL; p = p->next) {
        !           121:                        LabelData *tp = p->tree;
        !           122:                        printf("%s ", (tp->label)->name);
        !           123:                }
        !           124:        }
        !           125:        putchar('\n');
        !           126:        for(mp2=mp; mp2!=NULL; mp2 = mp2->link) {
        !           127:                if (MI_DEFINED(mp2->inp.value)) {
        !           128:                        if (MI_BRANCH(mp->inp.value))
        !           129:                                printf(" %d -> ", mp2->inp.value);
        !           130:                        else
        !           131:                                printf(" [%s] -> ", (mp2->inp.sym)->name);
        !           132:                        printf("%x", mp2->nst);
        !           133:                }
        !           134:                assert(mp2->fail==fail);
        !           135:                assert(mp2->match==match);
        !           136:        }
        !           137:        if(MI_DEFINED(mp->inp.value))
        !           138:                putchar('\n');
        !           139:        for (mp2 = mp; mp2!=NULL; mp2=mp2->link) {
        !           140:                machine_print(mp2->nst);
        !           141:        }
        !           142: }
        !           143: 
        !           144: /*
        !           145:  * This routine augments the machine with failure transition.
        !           146:  * The trie is examined in breadth first order.
        !           147:  *     See Aho, Corasick Comm ACM 18:6 for details
        !           148:  */
        !           149: cfail()
        !           150: {
        !           151:        struct machine_node **stack, **stack2;
        !           152:        struct machine_node **stackTop, **stack2Top, **temp;
        !           153:        int stackCnt, stack2Cnt;
        !           154:        struct machine_node *state;
        !           155:        struct machine_input sym;
        !           156:        register struct machine_node *s, *q;
        !           157: 
        !           158:        /* allocate stacks */
        !           159:        stackTop = stack = (struct machine_node **) malloc
        !           160:                                (ntrees*sizeof (struct machine_node *));
        !           161:        stack2 = stack2Top = (struct machine_node **) malloc
        !           162:                                (ntrees*sizeof (struct machine_node *));
        !           163:        stackCnt = stack2Cnt = 0;
        !           164:        s = machine;
        !           165:        do {
        !           166:                if (MI_DEFINED(s->inp.value)) {
        !           167:                        assert(++stackCnt <= ntrees);
        !           168:                        *stackTop++ = s->nst;
        !           169:                }
        !           170:                s = s->link;
        !           171:        } while (s != NULL);
        !           172: 
        !           173:        for(;;) {
        !           174:                if (stackCnt == 0) {
        !           175:                        /* swap stacks */
        !           176:                        if (stack2Cnt == 0)
        !           177:                                break;
        !           178:                        stackCnt = stack2Cnt; stack2Cnt = 0;
        !           179:                        stackTop = stack2Top;
        !           180:                        temp = stack; stack = stack2; stack2 = temp;
        !           181:                        stack2Top = stack2;
        !           182:                }
        !           183:                stackCnt--;
        !           184:                s = *--stackTop;
        !           185:                do {
        !           186:                        int startstate = 0;
        !           187:                        sym = s->inp;
        !           188:                        if (MI_DEFINED(sym.value)) {    /* g(s,c) != 0 */
        !           189:                            assert (++stack2Cnt <= ntrees);
        !           190:                            *stack2Top++ = (q=s->nst);
        !           191:                            state = s->fail;    /* state = f(s) */
        !           192:                            for(;;) {
        !           193:                                if (state == 0) {
        !           194:                                        state = machine;
        !           195:                                        startstate++;
        !           196:                                }
        !           197:                                if (MI_EQUAL(state->inp, sym)) {
        !           198:                                    struct match *mp = NULL;
        !           199: 
        !           200:                                    /* append any accepting matches */
        !           201:                                    for(mp=(state->nst)->match;mp;mp=mp->next)
        !           202:                                        add_match(q,mp->tree, mp->depth);
        !           203:                                    mp = q->match;
        !           204: 
        !           205:                                    do {
        !           206:                                        /* f(q) = g(state,sym)
        !           207:                                         * for all q links */
        !           208:                                        q->fail = state->nst;
        !           209:                                        q->match = mp;
        !           210:                                    } while ((q = q->link) != 0);
        !           211:                                    break;
        !           212:                                }
        !           213:                                else if (state->link != 0)
        !           214:                                    state = state->link;
        !           215:                                else {
        !           216:                                        state = state->fail;
        !           217:                                        if (state==NULL&&startstate)
        !           218:                                                break;
        !           219:                                }
        !           220:                            }
        !           221:                        }
        !           222:                        s = s->link;
        !           223:                } while (s!=NULL);
        !           224:        }
        !           225: }
        !           226: 
        !           227: /*
        !           228:  * Called from the YACC rule pattern_spec
        !           229:  */
        !           230: void
        !           231: machine_build()
        !           232: {
        !           233:        cfail();
        !           234:        (void) MachineNumber(machine, 0);
        !           235:        if(debug_flag&DB_MACH) {
        !           236:                fputs("\n-------\n", stderr);
        !           237:                machine_print(machine);
        !           238:        }
        !           239: }
        !           240: 
        !           241: struct match *acceptTable[MAXACCEPTS];
        !           242: struct match **acceptTableTop = acceptTable;
        !           243: static short int *arityTable;
        !           244: int nextAcceptIndex = 0;
        !           245: 
        !           246: /*
        !           247:  * This is the first pass of the process to generate the
        !           248:  * flattened machine used in the walker.  Called from machine_build
        !           249:  */
        !           250: int
        !           251: MachineNumber(mach, index)
        !           252:        struct machine_node *mach;
        !           253:        int index;
        !           254: {
        !           255:        struct machine_node *mp;
        !           256: 
        !           257:        for(mp=mach; mp!=NULL; mp = mp->link)
        !           258:                if(MI_DEFINED(mp->inp.value))
        !           259:                        index = MachineNumber(mp->nst, index);
        !           260: 
        !           261:        mach->index = index;
        !           262:        if (mach->match!=NULL) index += 2;
        !           263:        if(mach->link!=NULL || mach->nst!=NULL) {
        !           264:                index += 2;
        !           265:                for(mp = mach; mp!=NULL; mp = mp->link)
        !           266:                        if(mp->nst!=NULL) 
        !           267:                                index += 2;
        !           268:        }
        !           269: 
        !           270:        if (mach->fail!=NULL)
        !           271:                index += 2;
        !           272:        index++;
        !           273:        return(index);
        !           274: }
        !           275: 
        !           276: /*
        !           277:  * Build the flattened out machine used in the walker.
        !           278:  * See machine.h for description
        !           279:  */
        !           280: MachineGen()
        !           281: {
        !           282:        struct match **atp, *ap;
        !           283:        short int *sp;
        !           284: 
        !           285:        oreset();
        !           286:        fputs("short int mtTable[] = {\n", outfile);
        !           287:        machineGen2(machine);
        !           288:        fputs("};\n", outfile);
        !           289: 
        !           290:        fputs("short int mtAccept[] = {\n", outfile);
        !           291: 
        !           292:        oreset();
        !           293:        for(atp = acceptTable; atp < acceptTableTop; atp++) {
        !           294:                for(ap = *atp; ap!=NULL; ap = ap->next) {
        !           295:                        register LabelData *tree = ap->tree;
        !           296: 
        !           297:                        /* if you change any of the code below you must change
        !           298:                         * the increment added to nextAcceptIndex in
        !           299:                         * machineGen2
        !           300:                         */
        !           301:                        oputint(tree->treeIndex);
        !           302:                        oputint(ap->depth);
        !           303:                }
        !           304:                oputint(-1);
        !           305:        }
        !           306:        fprintf(outfile, "};\nshort int mtStart = %d;\n", machine->index);
        !           307: }
        !           308:                 
        !           309: machineGen2(mach)
        !           310:        struct machine_node *mach;
        !           311: {
        !           312:        struct machine_node *mp;
        !           313:        struct match *ap;
        !           314: 
        !           315:        if (mach==NULL)
        !           316:                return;
        !           317: 
        !           318:        for(mp=mach; mp!=NULL; mp = mp->link)
        !           319:                if(MI_DEFINED(mp->inp.value))
        !           320:                        machineGen2(mp->nst);
        !           321: 
        !           322:        assert(mach->index == ointcnt());
        !           323:        if (mach->match!=NULL) {
        !           324:                *acceptTableTop++ = mach->match;
        !           325:                oputint(ACCEPT); oputint(nextAcceptIndex);
        !           326:                for(ap = mach->match; ap!=NULL; ap = ap->next)
        !           327:                        nextAcceptIndex += 2;
        !           328:                nextAcceptIndex++;
        !           329:        }
        !           330:        if(mach->link!=NULL || mach->nst!=NULL) {
        !           331:                if(MI_BRANCH(mp->inp.value)&&gen_table2) {
        !           332:                        oputint (TABLE2);
        !           333:                        for(mp = mach; mp!=NULL; mp = mp->link) {
        !           334:                                if(mp->nst!=NULL) {
        !           335:                                        oputoct(mp->inp.value);
        !           336:                                        oputint((mp->nst)->index);
        !           337:                                }
        !           338:                        }
        !           339:                } else {
        !           340:                        oputint (TABLE);
        !           341:                        for(mp = mach; mp!=NULL; mp = mp->link) {
        !           342:                                if(mp->nst!=NULL) {
        !           343:                                        oputoct(mp->inp.value);
        !           344:                                        oputint((mp->nst)->index);
        !           345:                                }
        !           346:                        }
        !           347:                }
        !           348:                oputint(-1);
        !           349:        }
        !           350: 
        !           351:        /* A failure transition or a -1 terminate every state */
        !           352:        if (mach->fail!=NULL) {
        !           353:                oputint(FAIL); oputint((mach->fail)->index);
        !           354:        }
        !           355:        oputint(-1);
        !           356: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.