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