Return to tree.c CVS log

Up to [CSRG BSD Unix] / 42BSD / ucb / dbx

Annotation of 42BSD/ucb/dbx/tree.c, revision 1.1

1.1     ! root        1: /* Copyright (c) 1982 Regents of the University of California */
        !             2: 
        !             3: static char sccsid[] = "@(#)tree.c 1.5 8/10/83";
        !             4: 
        !             5: /*
        !             6:  * Parse tree management.
        !             7:  */
        !             8: 
        !             9: #include "defs.h"
        !            10: #include "tree.h"
        !            11: #include "operators.h"
        !            12: #include "eval.h"
        !            13: #include "events.h"
        !            14: #include "symbols.h"
        !            15: #include "scanner.h"
        !            16: #include "source.h"
        !            17: #include "object.h"
        !            18: #include "mappings.h"
        !            19: #include "process.h"
        !            20: #include "machine.h"
        !            21: 
        !            22: #ifndef public
        !            23: #include "lists.h"
        !            24: 
        !            25: typedef struct Node *Node;
        !            26: typedef Node Command;
        !            27: typedef List Cmdlist;
        !            28: 
        !            29: #include "operators.h"
        !            30: #include "symbols.h"
        !            31: #include "events.h"
        !            32: 
        !            33: #define MAXNARGS 5
        !            34: 
        !            35: struct Node {
        !            36:     Operator op;
        !            37:     Symbol nodetype;
        !            38:     union treevalue {
        !            39:        Symbol sym;
        !            40:        Name name;
        !            41:        long lcon;
        !            42:        double fcon;
        !            43:        String scon;
        !            44:        Node arg[MAXNARGS];
        !            45:        struct {
        !            46:            Node cond;
        !            47:            Cmdlist actions;
        !            48:        } event;
        !            49:        struct {
        !            50:            Boolean inst;
        !            51:            Event event;
        !            52:            Cmdlist actions;
        !            53:        } trace;
        !            54:        struct {
        !            55:            Boolean source;
        !            56:            Boolean skipcalls;
        !            57:        } step;
        !            58:        struct {
        !            59:            String mode;
        !            60:            Node beginaddr;
        !            61:            Node endaddr;
        !            62:            Integer count;
        !            63:        } examine;
        !            64:     } value;
        !            65: };
        !            66: 
        !            67: #define evalcmd(cmd) eval(cmd)
        !            68: #define cmdlist_append(cmd, cl) list_append(list_item(cmd), nil, cl)
        !            69: 
        !            70: #endif
        !            71: 
        !            72: typedef char *Arglist;
        !            73: 
        !            74: #define nextarg(type)  ((type *) (ap += sizeof(type)))[-1]
        !            75: 
        !            76: /*
        !            77:  * Build a tree.
        !            78:  */
        !            79: 
        !            80: /* VARARGS1 */
        !            81: public Node build(op, args)
        !            82: Operator op;
        !            83: {
        !            84:     register Node p, q;
        !            85:     register Arglist ap;
        !            86:     Integer i;
        !            87: 
        !            88:     p = new(Node);
        !            89:     p->op = op;
        !            90:     p->nodetype = nil;
        !            91:     ap = (Arglist) &args;
        !            92:     switch (op) {
        !            93:        case O_NAME:
        !            94:            p->value.name = nextarg(Name);
        !            95:            break;
        !            96: 
        !            97:        case O_SYM:
        !            98:        case O_PRINTCALL:
        !            99:        case O_PRINTRTN:
        !           100:        case O_PROCRTN:
        !           101:            p->value.sym = nextarg(Symbol);
        !           102:            break;
        !           103: 
        !           104:        case O_DEBUG:
        !           105:        case O_LCON:
        !           106:        case O_CONT:
        !           107:        case O_DELETE:
        !           108:        case O_CATCH:
        !           109:        case O_IGNORE:
        !           110:        case O_TRACEOFF:
        !           111:            p->value.lcon = nextarg(long);
        !           112:            break;
        !           113: 
        !           114:        case O_FCON:
        !           115:            p->value.fcon = nextarg(double);
        !           116:            break;
        !           117: 
        !           118:        case O_SCON:
        !           119:        case O_CHFILE:
        !           120:        case O_EDIT:
        !           121:        case O_SOURCE:
        !           122:            p->value.scon = nextarg(String);
        !           123:            break;
        !           124: 
        !           125:        case O_RVAL:
        !           126:            q = nextarg(Node);
        !           127:            if (q->op == O_CALL) {
        !           128:                *p = *q;
        !           129:                dispose(q);
        !           130:            } else {
        !           131:                p->value.arg[0] = q;
        !           132:            }
        !           133:            break;
        !           134: 
        !           135:        case O_INDIR:
        !           136:            q = nextarg(Node);
        !           137:            if (q != nil and q->op == O_RVAL) {
        !           138:                p->value.arg[0] = q->value.arg[0];
        !           139:                dispose(q);
        !           140:            } else {
        !           141:                p->value.arg[0] = q;
        !           142:            }
        !           143:            break;
        !           144: 
        !           145:        case O_ADDEVENT:
        !           146:        case O_ONCE:
        !           147:        case O_IF:
        !           148:            p->value.event.cond = nextarg(Node);
        !           149:            p->value.event.actions = nextarg(Cmdlist);
        !           150:            break;
        !           151: 
        !           152:        case O_TRACEON:
        !           153:            p->value.trace.inst = nextarg(Boolean);
        !           154:            p->value.trace.event = nil;
        !           155:            p->value.trace.actions = nextarg(Cmdlist);
        !           156:            break;
        !           157: 
        !           158:        case O_STEP:
        !           159:            p->value.step.source = nextarg(Boolean);
        !           160:            p->value.step.skipcalls = nextarg(Boolean);
        !           161:            break;
        !           162: 
        !           163:        case O_EXAMINE:
        !           164:            p->value.examine.mode = nextarg(String);
        !           165:            p->value.examine.beginaddr = nextarg(Node);
        !           166:            p->value.examine.endaddr = nextarg(Node);
        !           167:            p->value.examine.count = nextarg(Integer);
        !           168:            break;
        !           169: 
        !           170:        default:
        !           171:            for (i = 0; i < nargs(op); i++) {
        !           172:                p->value.arg[i] = nextarg(Node);
        !           173:            }
        !           174:            break;
        !           175:     }
        !           176:     check(p);
        !           177:     assigntypes(p);
        !           178:     if(debug_flag[5]) {     
        !           179:        fprintf(stderr," built %s node %d with arg0 %d arg1 %d \n",
        !           180:                showoperator(p->op), p, p->value.arg[0],p->value.arg[1]);
        !           181:     }
        !           182:     return p;
        !           183: }
        !           184: 
        !           185: /*
        !           186:  * Create a command list from a single command.
        !           187:  */
        !           188: 
        !           189: public Cmdlist buildcmdlist(cmd)
        !           190: Command cmd;
        !           191: {
        !           192:     Cmdlist cmdlist;
        !           193: 
        !           194:     cmdlist = list_alloc();
        !           195:     cmdlist_append(cmd, cmdlist);
        !           196:     return cmdlist;
        !           197: }
        !           198: 
        !           199: /*
        !           200:  * Return the tree for a unary ampersand operator.
        !           201:  */
        !           202: 
        !           203: public Node amper(p)
        !           204: Node p;
        !           205: {
        !           206:     Node r;
        !           207: 
        !           208:     checkref(p);
        !           209:     switch (p->op) {
        !           210:        case O_RVAL:
        !           211:            r = p->value.arg[0];
        !           212:            break;
        !           213: 
        !           214:        case O_CALL:
        !           215:            r = build(O_LCON, codeloc(p->value.arg[0]->value.sym));
        !           216:            tfree(p);
        !           217:            break;
        !           218: 
        !           219:        case O_SYM:
        !           220:            if (isblock(p->value.sym)) {
        !           221:                r = build(O_LCON, codeloc(p->value.sym));
        !           222:            } else {
        !           223:                r = build(O_LCON, address(p->value.sym, nil));
        !           224:            }
        !           225:            tfree(p);
        !           226:            break;
        !           227: 
        !           228:        case O_DOT:
        !           229:            r = p;
        !           230:            break;
        !           231: 
        !           232:        case O_INDIR:
        !           233:            r = p->value.arg[0];
        !           234:            dispose(p);
        !           235:            break;
        !           236: 
        !           237:        default:
        !           238:            beginerrmsg();
        !           239:            fprintf(stderr, "expected variable, found ");
        !           240:            prtree(stderr, p);
        !           241:            tfree(p);
        !           242:            enderrmsg();
        !           243:            /* NOTREACHED */
        !           244:     }
        !           245:     r->nodetype = t_int;
        !           246:     return r;
        !           247: }
        !           248: 
        !           249: /*
        !           250:  * Create a "concrete" version of a node.
        !           251:  * This is necessary when the type of the node contains
        !           252:  * an unresolved type reference.
        !           253:  */
        !           254: 
        !           255: public Node concrete(p)
        !           256: Node p;
        !           257: {
        !           258:     findtype(p->nodetype);
        !           259:     return build(O_INDIR, p);
        !           260: }
        !           261: 
        !           262: /*
        !           263:  * Print out a command.
        !           264:  */
        !           265: 
        !           266: public printcmd(f, cmd)
        !           267: File f;
        !           268: Command cmd;
        !           269: {
        !           270:     register Integer i;
        !           271:     register Command c;
        !           272:     register Node p;
        !           273: 
        !           274:     switch (cmd->op) {
        !           275:        case O_PRINTIFCHANGED:
        !           276:        case O_PRINTSRCPOS:
        !           277:        case O_STOPIFCHANGED:
        !           278:        case O_TRACEON:
        !           279:            break;
        !           280: 
        !           281:        case O_STEP:
        !           282:            if (cmd->value.step.skipcalls) {
        !           283:                fprintf(f, "next");
        !           284:            } else {
        !           285:                fprintf(f, "step");
        !           286:            }
        !           287:            if (not cmd->value.step.source) {
        !           288:                fprintf(f, "i");
        !           289:            }
        !           290:            break;
        !           291: 
        !           292:        default:
        !           293:            fprintf(f, "%s", opinfo[ord(cmd->op)].opstring);
        !           294:            if (nargs(cmd->op) != 0) {
        !           295:                fprintf(f, " ");
        !           296:            }
        !           297:            break;
        !           298:     }
        !           299:     switch (cmd->op) {
        !           300:        case O_PRINTCALL:
        !           301:        case O_PRINTRTN:
        !           302:        case O_PROCRTN:
        !           303:            fprintf(f, "%s", symname(cmd->value.sym));
        !           304:            break;
        !           305: 
        !           306:        case O_PRINTSRCPOS:
        !           307:            p = cmd->value.arg[0];
        !           308:            if (p != nil and p->op != O_QLINE) {
        !           309:                printf("trace ");
        !           310:                prtree(f, p);
        !           311:            }
        !           312:            break;
        !           313: 
        !           314:        case O_CHFILE:
        !           315:        case O_EDIT:
        !           316:        case O_SOURCE:
        !           317:            fprintf(f, "%s", cmd->value.scon);
        !           318:            break;
        !           319: 
        !           320:        case O_DELETE:
        !           321:        case O_CATCH:
        !           322:        case O_IGNORE:
        !           323:        case O_TRACEOFF:
        !           324:            fprintf(f, "%d", cmd->value.lcon);
        !           325:            break;
        !           326: 
        !           327:        case O_ADDEVENT:
        !           328:        case O_ONCE:
        !           329:        case O_IF:
        !           330:            fprintf(f, " ");
        !           331:            prtree(f, cmd->value.event.cond);
        !           332:            fprintf(f, " { ");
        !           333:            foreach (Command, c, cmd->value.event.actions)
        !           334:                printcmd(f, c);
        !           335:                if (not list_islast()) {
        !           336:                    fprintf(f, ";");
        !           337:                }
        !           338:            endfor
        !           339:            fprintf(f, " }", opinfo[ord(cmd->op)].opstring);
        !           340:            break;
        !           341: 
        !           342:        case O_TRACEON:
        !           343:            print_tracestop(f, cmd);
        !           344:            break;
        !           345: 
        !           346:        case O_EXAMINE:
        !           347:            prtree(f, cmd->value.examine.beginaddr);
        !           348:            if (cmd->value.examine.endaddr != nil) {
        !           349:                fprintf(f, ",");
        !           350:                prtree(f, cmd->value.examine.endaddr);
        !           351:            }
        !           352:            fprintf(f, "/");
        !           353:            if (cmd->value.examine.count > 1) {
        !           354:                fprintf(f, "%d", cmd->value.examine.count);
        !           355:            }
        !           356:            fprintf("%s", cmd->value.examine.mode);
        !           357:            break;
        !           358: 
        !           359:        default:
        !           360:            if (nargs(cmd->op) != 0) {
        !           361:                i = 0;
        !           362:                for (;;) {
        !           363:                    prtree(f, cmd->value.arg[i]);
        !           364:                    ++i;
        !           365:                if (i >= nargs(cmd->op)) break;
        !           366:                    fprintf(f, " ");
        !           367:                }
        !           368:            }
        !           369:            break;
        !           370:     }
        !           371: }
        !           372: 
        !           373: /*
        !           374:  * Print out a trace/stop command name.
        !           375:  */
        !           376: 
        !           377: #define fprintI(f, b) { if (b) fprintf(f, "i"); }
        !           378: 
        !           379: private print_tracestop(f, cmd)
        !           380: File f;
        !           381: Command cmd;
        !           382: {
        !           383:     register Command c, ifcmd, stopcmd;
        !           384:     Boolean done;
        !           385: 
        !           386:     done = false;
        !           387:     ifcmd = list_element(Command, list_head(cmd->value.trace.actions));
        !           388:     checkref(ifcmd);
        !           389:     if (ifcmd->op == O_IF) {
        !           390:        stopcmd = list_element(Command, list_head(ifcmd->value.event.actions));
        !           391:        checkref(stopcmd);
        !           392:        if (stopcmd->op == O_STOPX) {
        !           393:            fprintf(f, "stop");
        !           394:            fprintI(f, cmd->value.trace.inst);
        !           395:            fprintf(f, " if ");
        !           396:            prtree(f, ifcmd->value.event.cond);
        !           397:            done = true;
        !           398:        }
        !           399:     } else if (ifcmd->op == O_STOPIFCHANGED) {
        !           400:        fprintf(f, "stop");
        !           401:        fprintI(f, cmd->value.trace.inst);
        !           402:        fprintf(f, " ");
        !           403:        prtree(f, ifcmd->value.arg[0]);
        !           404:        done = true;
        !           405:     }
        !           406:     if (not done) {
        !           407:        fprintf(f, "%s ", cmd->value.trace.inst ? "tracei" : "trace");
        !           408:        foreach (Command, c, cmd->value.trace.actions)
        !           409:            printcmd(f, c);
        !           410:            if (not list_islast()) {
        !           411:                fprintf(f, ";");
        !           412:            }
        !           413:        endfor
        !           414:     }
        !           415: }
        !           416: 
        !           417: /*
        !           418:  * Print out a tree.
        !           419:  */
        !           420: 
        !           421: public prtree(f, p)
        !           422: File f;
        !           423: register Node p;
        !           424: {
        !           425:     register Node q;
        !           426:     Operator op;
        !           427: 
        !           428:     if (p != nil) {
        !           429:        op = p->op;
        !           430:        if (ord(op) > ord(O_LASTOP)) {
        !           431:            panic("bad op %d in prtree", p->op);
        !           432:        }
        !           433:        switch (op) {
        !           434:            case O_NAME:
        !           435:                fprintf(f, "%s", ident(p->value.name));
        !           436:                break;
        !           437: 
        !           438:            case O_SYM:
        !           439:                printname(f, p->value.sym);
        !           440:                break;
        !           441: 
        !           442:            case O_QLINE:
        !           443:                if (nlhdr.nfiles > 1) {
        !           444:                    prtree(f, p->value.arg[0]);
        !           445:                    fprintf(f, ":");
        !           446:                }
        !           447:                prtree(f, p->value.arg[1]);
        !           448:                break;
        !           449: 
        !           450:            case O_LCON:
        !           451:                if (compatible(p->nodetype, t_char)) {
        !           452:                    fprintf(f, "'%c'", p->value.lcon);
        !           453:                } else {
        !           454:                    fprintf(f, "%d", p->value.lcon);
        !           455:                }
        !           456:                break;
        !           457: 
        !           458:            case O_FCON:
        !           459:                fprintf(f, "%g", p->value.fcon);
        !           460:                break;
        !           461: 
        !           462:            case O_SCON:
        !           463:                fprintf(f, "\"%s\"", p->value.scon);
        !           464:                break;
        !           465: 
        !           466:            case O_INDEX:
        !           467:                prtree(f, p->value.arg[0]);
        !           468:                fprintf(f, "[");
        !           469:                prtree(f, p->value.arg[1]);
        !           470:                fprintf(f, "]");
        !           471:                break;
        !           472: 
        !           473:            case O_COMMA:
        !           474:                prtree(f, p->value.arg[0]);
        !           475:                if (p->value.arg[1] != nil) {
        !           476:                    fprintf(f, ", ");
        !           477:                    prtree(f, p->value.arg[1]);
        !           478:                }
        !           479:                break;
        !           480: 
        !           481:            case O_RVAL:
        !           482:                if (p->value.arg[0]->op == O_SYM) {
        !           483:                    printname(f, p->value.arg[0]->value.sym);
        !           484:                } else {
        !           485:                    prtree(f, p->value.arg[0]);
        !           486:                }
        !           487:                break;
        !           488: 
        !           489:            case O_ITOF:
        !           490:                prtree(f, p->value.arg[0]);
        !           491:                break;
        !           492: 
        !           493:            case O_CALL:
        !           494:                prtree(f, p->value.arg[0]);
        !           495:                if (p->value.arg[1]!= nil) {
        !           496:                    fprintf(f, "(");
        !           497:                    prtree(f, p->value.arg[1]);
        !           498:                    fprintf(f, ")");
        !           499:                }
        !           500:                break;
        !           501: 
        !           502:            case O_INDIR:
        !           503:                q = p->value.arg[0];
        !           504:                if (isvarparam(q->nodetype)) {
        !           505:                    prtree(f, q);
        !           506:                } else {
        !           507:                    if (q->op == O_SYM or q->op == O_LCON or q->op == O_DOT) {
        !           508:                        prtree(f, q);
        !           509:                        fprintf(f, "^");
        !           510:                    } else {
        !           511:                        fprintf(f, "*(");
        !           512:                        prtree(f, q);
        !           513:                        fprintf(f, ")");
        !           514:                    }
        !           515:                }
        !           516:                break;
        !           517: 
        !           518:            case O_DOT:
        !           519:                q = p->value.arg[0];
        !           520:                if (q->op == O_INDIR) {
        !           521:                    prtree(f, q->value.arg[0]);
        !           522:                } else {
        !           523:                    prtree(f, q);
        !           524:                }
        !           525:                fprintf(f, ".%s", symname(p->value.arg[1]->value.sym));
        !           526:                break;
        !           527: 
        !           528:            default:
        !           529:                switch (degree(op)) {
        !           530:                    case BINARY:
        !           531:                        prtree(f, p->value.arg[0]);
        !           532:                        fprintf(f, "%s", opinfo[ord(op)].opstring);
        !           533:                        prtree(f, p->value.arg[1]);
        !           534:                        break;
        !           535: 
        !           536:                    case UNARY:
        !           537:                        fprintf(f, "%s", opinfo[ord(op)].opstring);
        !           538:                        prtree(f, p->value.arg[0]);
        !           539:                        break;
        !           540: 
        !           541:                    default:
        !           542:                        error("internal error: bad op %d in prtree", op);
        !           543:                }
        !           544:                break;
        !           545:        }
        !           546:     }
        !           547: }
        !           548: 
        !           549: /*
        !           550:  * Free storage associated with a tree.
        !           551:  */
        !           552: 
        !           553: public tfree(p)
        !           554: Node p;
        !           555: {
        !           556:     Integer i;
        !           557: 
        !           558:     if (p == nil) {
        !           559:        return;
        !           560:     }
        !           561:     switch (p->op) {
        !           562:        case O_QLINE:
        !           563:            dispose(p->value.arg[0]->value.scon);
        !           564:            dispose(p->value.arg[0]);
        !           565:            tfree(p->value.arg[1]);
        !           566:            break;
        !           567: 
        !           568:        case O_SCON:
        !           569:            unmkstring(p->nodetype);
        !           570:            dispose(p->nodetype);
        !           571:            dispose(p->value.scon);
        !           572:            break;
        !           573: 
        !           574:        default:
        !           575:            for (i = 0; i < nargs(p->op); i++) {
        !           576:                tfree(p->value.arg[i]);
        !           577:            }
        !           578:            break;
        !           579:     }
        !           580:     dispose(p);
        !           581: }
        !           582: 
        !           583: /*
        !           584:  * A recursive tree search routine to test if two trees * are equivalent.
        !           585:  */
        !           586: 
        !           587: public Boolean tr_equal(t1, t2)
        !           588: register Node t1;
        !           589: register Node t2;
        !           590: {
        !           591:     register Boolean b;
        !           592: 
        !           593:     if (t1 == nil and t2 == nil) {
        !           594:        b = true;
        !           595:     } else if (t1 == nil or t2 == nil) {
        !           596:        b = false;
        !           597:     } else if (t1->op != t2->op or degree(t1->op) != degree(t2->op)) {
        !           598:        b = false;
        !           599:     } else {
        !           600:        switch (degree(t1->op)) {
        !           601:            case LEAF:
        !           602:                switch (t1->op) {
        !           603:                    case O_NAME:
        !           604:                        b = (Boolean) (t1->value.name == t2->value.name);
        !           605:                        break;
        !           606: 
        !           607:                    case O_SYM:
        !           608:                        b = (Boolean) (t1->value.sym == t2->value.sym);
        !           609:                        break;
        !           610: 
        !           611:                    case O_LCON:
        !           612:                        b = (Boolean) (t1->value.lcon == t2->value.lcon);
        !           613:                        break;
        !           614: 
        !           615:                    case O_FCON:
        !           616:                        b = (Boolean) (t1->value.fcon == t2->value.fcon);
        !           617:                        break;
        !           618: 
        !           619:                    case O_SCON:
        !           620:                        b = (Boolean) (t1->value.scon == t2->value.scon);
        !           621:                        break;
        !           622: 
        !           623:                    default:
        !           624:                        panic("tr_equal: leaf %d\n", t1->op);
        !           625:                }
        !           626:                /*NOTREACHED*/
        !           627: 
        !           628:            case BINARY:
        !           629:                if (not tr_equal(t1->value.arg[0], t2->value.arg[0])) {
        !           630:                    b = false;
        !           631:                } else {
        !           632:                    b = tr_equal(t1->value.arg[1], t2->value.arg[1]);
        !           633:                }
        !           634:                break;
        !           635: 
        !           636:            case UNARY:
        !           637:                b = tr_equal(t1->value.arg[0], t2->value.arg[0]);
        !           638:                break;
        !           639: 
        !           640:            default:
        !           641:                panic("tr_equal: bad degree for op %d\n", t1->op);
        !           642:        }
        !           643:     }
        !           644:     return b;
        !           645: }

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