1 /* Copyright (c) 1982 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)tree.c 1.5 08/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 } 646