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