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