1 /* Copyright (c) 1982 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)tree.c 1.4 05/18/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 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, "%s if ", cmd->value.trace.inst ? "stopi" : "stop"); 392 prtree(f, ifcmd->value.event.cond); 393 done = true; 394 } 395 } 396 if (not done) { 397 fprintf(f, "%s ", cmd->value.trace.inst ? "tracei" : "trace"); 398 foreach (Command, c, cmd->value.trace.actions) 399 printcmd(f, c); 400 if (not list_islast()) { 401 fprintf(f, ";"); 402 } 403 endfor 404 } 405 } 406 407 /* 408 * Print a tree back out in Pascal form. 409 */ 410 411 public prtree(f, p) 412 File f; 413 register Node p; 414 { 415 register Node q; 416 Operator op; 417 418 if (p != nil) { 419 op = p->op; 420 if (ord(op) > ord(O_LASTOP)) { 421 panic("bad op %d in prtree", p->op); 422 } 423 switch (op) { 424 case O_NAME: 425 fprintf(f, "%s", ident(p->value.name)); 426 break; 427 428 case O_SYM: 429 printname(f, p->value.sym); 430 break; 431 432 case O_QLINE: 433 if (nlhdr.nfiles > 1) { 434 prtree(f, p->value.arg[0]); 435 fprintf(f, ":"); 436 } 437 prtree(f, p->value.arg[1]); 438 break; 439 440 case O_LCON: 441 if (compatible(p->nodetype, t_char)) { 442 fprintf(f, "'%c'", p->value.lcon); 443 } else { 444 fprintf(f, "%d", p->value.lcon); 445 } 446 break; 447 448 case O_FCON: 449 fprintf(f, "%g", p->value.fcon); 450 break; 451 452 case O_SCON: 453 fprintf(f, "\"%s\"", p->value.scon); 454 break; 455 456 case O_INDEX: 457 prtree(f, p->value.arg[0]); 458 fprintf(f, "["); 459 prtree(f, p->value.arg[1]); 460 fprintf(f, "]"); 461 break; 462 463 case O_COMMA: 464 prtree(f, p->value.arg[0]); 465 if (p->value.arg[1] != nil) { 466 fprintf(f, ", "); 467 prtree(f, p->value.arg[1]); 468 } 469 break; 470 471 case O_RVAL: 472 if (p->value.arg[0]->op == O_SYM) { 473 printname(f, p->value.arg[0]->value.sym); 474 } else { 475 prtree(f, p->value.arg[0]); 476 } 477 break; 478 479 case O_ITOF: 480 prtree(f, p->value.arg[0]); 481 break; 482 483 case O_CALL: 484 prtree(f, p->value.arg[0]); 485 if (p->value.arg[1]!= nil) { 486 fprintf(f, "("); 487 prtree(f, p->value.arg[1]); 488 fprintf(f, ")"); 489 } 490 break; 491 492 case O_INDIR: 493 q = p->value.arg[0]; 494 if (isvarparam(q->nodetype)) { 495 prtree(f, q); 496 } else { 497 if (q->op == O_SYM or q->op == O_LCON or q->op == O_DOT) { 498 prtree(f, q); 499 fprintf(f, "^"); 500 } else { 501 fprintf(f, "*("); 502 prtree(f, q); 503 fprintf(f, ")"); 504 } 505 } 506 break; 507 508 case O_DOT: 509 q = p->value.arg[0]; 510 if (q->op == O_INDIR) { 511 prtree(f, q->value.arg[0]); 512 } else { 513 prtree(f, q); 514 } 515 fprintf(f, ".%s", symname(p->value.arg[1]->value.sym)); 516 break; 517 518 default: 519 switch (degree(op)) { 520 case BINARY: 521 prtree(f, p->value.arg[0]); 522 fprintf(f, "%s", opinfo[ord(op)].opstring); 523 prtree(f, p->value.arg[1]); 524 break; 525 526 case UNARY: 527 fprintf(f, "%s", opinfo[ord(op)].opstring); 528 prtree(f, p->value.arg[0]); 529 break; 530 531 default: 532 error("internal error: bad op %d in prtree", op); 533 } 534 break; 535 } 536 } 537 } 538 539 /* 540 * Free storage associated with a tree. 541 */ 542 543 public tfree(p) 544 Node p; 545 { 546 Integer i; 547 548 if (p == nil) { 549 return; 550 } 551 switch (p->op) { 552 case O_QLINE: 553 dispose(p->value.arg[0]->value.scon); 554 dispose(p->value.arg[0]); 555 tfree(p->value.arg[1]); 556 break; 557 558 case O_SCON: 559 unmkstring(p->nodetype); 560 dispose(p->nodetype); 561 dispose(p->value.scon); 562 break; 563 564 default: 565 for (i = 0; i < nargs(p->op); i++) { 566 tfree(p->value.arg[i]); 567 } 568 break; 569 } 570 dispose(p); 571 } 572 573 /* 574 * A recursive tree search routine to test if two trees * are equivalent. 575 */ 576 577 public Boolean tr_equal(t1, t2) 578 register Node t1; 579 register Node t2; 580 { 581 register Boolean b; 582 583 if (t1 == nil and t2 == nil) { 584 b = true; 585 } else if (t1 == nil or t2 == nil) { 586 b = false; 587 } else if (t1->op != t2->op or degree(t1->op) != degree(t2->op)) { 588 b = false; 589 } else { 590 switch (degree(t1->op)) { 591 case LEAF: 592 switch (t1->op) { 593 case O_NAME: 594 b = (Boolean) (t1->value.name == t2->value.name); 595 break; 596 597 case O_SYM: 598 b = (Boolean) (t1->value.sym == t2->value.sym); 599 break; 600 601 case O_LCON: 602 b = (Boolean) (t1->value.lcon == t2->value.lcon); 603 break; 604 605 case O_FCON: 606 b = (Boolean) (t1->value.fcon == t2->value.fcon); 607 break; 608 609 case O_SCON: 610 b = (Boolean) (t1->value.scon == t2->value.scon); 611 break; 612 613 default: 614 panic("tr_equal: leaf %d\n", t1->op); 615 } 616 /*NOTREACHED*/ 617 618 case BINARY: 619 if (not tr_equal(t1->value.arg[0], t2->value.arg[0])) { 620 b = false; 621 } else { 622 b = tr_equal(t1->value.arg[1], t2->value.arg[1]); 623 } 624 break; 625 626 case UNARY: 627 b = tr_equal(t1->value.arg[0], t2->value.arg[0]); 628 break; 629 630 default: 631 panic("tr_equal: bad degree for op %d\n", t1->op); 632 } 633 } 634 return b; 635 } 636