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