1 /* Copyright (c) 1982 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)tree.c 1.5 8/10/83"; 4 5 static char rcsid[] = "$Header: tree.c,v 1.3 84/03/27 10:24:40 linton Exp $"; 6 7 /* 8 * Parse tree management. 9 */ 10 11 #include "defs.h" 12 #include "tree.h" 13 #include "operators.h" 14 #include "eval.h" 15 #include "events.h" 16 #include "symbols.h" 17 #include "scanner.h" 18 #include "source.h" 19 #include "object.h" 20 #include "mappings.h" 21 #include "process.h" 22 #include "machine.h" 23 24 #ifndef public 25 #include "lists.h" 26 27 typedef struct Node *Node; 28 typedef Node Command; 29 typedef List Cmdlist; 30 31 #include "operators.h" 32 #include "symbols.h" 33 #include "events.h" 34 35 #define MAXNARGS 5 36 37 struct Node { 38 Operator op; 39 Symbol nodetype; 40 union treevalue { 41 Symbol sym; 42 Name name; 43 long lcon; 44 double fcon; 45 String scon; 46 Node arg[MAXNARGS]; 47 struct { 48 Node cond; 49 Cmdlist actions; 50 } event; 51 struct { 52 Boolean inst; 53 Event event; 54 Cmdlist actions; 55 } trace; 56 struct { 57 Boolean source; 58 Boolean skipcalls; 59 } step; 60 struct { 61 String mode; 62 Node beginaddr; 63 Node endaddr; 64 Integer count; 65 } examine; 66 } value; 67 }; 68 69 #define evalcmd(cmd) eval(cmd) 70 #define cmdlist_append(cmd, cl) list_append(list_item(cmd), nil, cl) 71 72 #endif 73 74 typedef char *Arglist; 75 76 #define nextarg(type) ((type *) (ap += sizeof(type)))[-1] 77 78 /* 79 * Build a tree. 80 */ 81 82 /* VARARGS1 */ 83 public Node build(op, args) 84 Operator op; 85 { 86 register Node p, q; 87 register Arglist ap; 88 Integer i; 89 90 p = new(Node); 91 p->op = op; 92 p->nodetype = nil; 93 ap = (Arglist) &args; 94 switch (op) { 95 case O_NAME: 96 p->value.name = nextarg(Name); 97 break; 98 99 case O_SYM: 100 case O_PRINTCALL: 101 case O_PRINTRTN: 102 case O_PROCRTN: 103 p->value.sym = nextarg(Symbol); 104 break; 105 106 case O_DEBUG: 107 case O_LCON: 108 case O_CONT: 109 case O_CATCH: 110 case O_IGNORE: 111 case O_TRACEOFF: 112 p->value.lcon = nextarg(long); 113 break; 114 115 case O_FCON: 116 p->value.fcon = nextarg(double); 117 break; 118 119 case O_SCON: 120 case O_CHFILE: 121 case O_EDIT: 122 case O_SOURCE: 123 p->value.scon = nextarg(String); 124 break; 125 126 case O_RVAL: 127 q = nextarg(Node); 128 if (q->op == O_CALL) { 129 *p = *q; 130 dispose(q); 131 } else { 132 p->value.arg[0] = q; 133 } 134 break; 135 136 case O_INDIR: 137 q = nextarg(Node); 138 if (q != nil and q->op == O_RVAL) { 139 p->value.arg[0] = q->value.arg[0]; 140 dispose(q); 141 } else { 142 p->value.arg[0] = q; 143 } 144 break; 145 146 case O_ADDEVENT: 147 case O_ONCE: 148 case O_IF: 149 p->value.event.cond = nextarg(Node); 150 p->value.event.actions = nextarg(Cmdlist); 151 break; 152 153 case O_TRACEON: 154 p->value.trace.inst = nextarg(Boolean); 155 p->value.trace.event = nil; 156 p->value.trace.actions = nextarg(Cmdlist); 157 break; 158 159 case O_STEP: 160 p->value.step.source = nextarg(Boolean); 161 p->value.step.skipcalls = nextarg(Boolean); 162 break; 163 164 case O_EXAMINE: 165 p->value.examine.mode = nextarg(String); 166 p->value.examine.beginaddr = nextarg(Node); 167 p->value.examine.endaddr = nextarg(Node); 168 p->value.examine.count = nextarg(Integer); 169 break; 170 171 default: 172 for (i = 0; i < nargs(op); i++) { 173 p->value.arg[i] = nextarg(Node); 174 } 175 break; 176 } 177 check(p); 178 assigntypes(p); 179 if(debug_flag[5]) { 180 fprintf(stderr," built %s node %d with arg0 %d arg1 %d \n", 181 showoperator(p->op), p, p->value.arg[0],p->value.arg[1]); 182 } 183 return p; 184 } 185 186 /* 187 * Create a command list from a single command. 188 */ 189 190 public Cmdlist buildcmdlist(cmd) 191 Command cmd; 192 { 193 Cmdlist cmdlist; 194 195 cmdlist = list_alloc(); 196 cmdlist_append(cmd, cmdlist); 197 return cmdlist; 198 } 199 200 /* 201 * Return the tree for a unary ampersand operator. 202 */ 203 204 public Node amper(p) 205 Node p; 206 { 207 Node r; 208 209 checkref(p); 210 switch (p->op) { 211 case O_RVAL: 212 r = p->value.arg[0]; 213 break; 214 215 case O_CALL: 216 r = build(O_LCON, codeloc(p->value.arg[0]->value.sym)); 217 tfree(p); 218 break; 219 220 case O_SYM: 221 if (isblock(p->value.sym)) { 222 r = build(O_LCON, codeloc(p->value.sym)); 223 } else { 224 r = build(O_LCON, address(p->value.sym, nil)); 225 } 226 tfree(p); 227 break; 228 229 case O_DOT: 230 r = p; 231 break; 232 233 case O_INDIR: 234 r = p->value.arg[0]; 235 dispose(p); 236 break; 237 238 default: 239 beginerrmsg(); 240 fprintf(stderr, "expected variable, found "); 241 prtree(stderr, p); 242 tfree(p); 243 enderrmsg(); 244 /* NOTREACHED */ 245 } 246 r->nodetype = t_int; 247 return r; 248 } 249 250 /* 251 * Create a "concrete" version of a node. 252 * This is necessary when the type of the node contains 253 * an unresolved type reference. 254 */ 255 256 public Node concrete(p) 257 Node p; 258 { 259 findtype(p->nodetype); 260 return build(O_INDIR, p); 261 } 262 263 /* 264 * Print out a command. 265 */ 266 267 public printcmd(f, cmd) 268 File f; 269 Command cmd; 270 { 271 register Integer i; 272 register Command c; 273 register Node p; 274 275 switch (cmd->op) { 276 case O_PRINTIFCHANGED: 277 case O_PRINTSRCPOS: 278 case O_STOPIFCHANGED: 279 case O_TRACEON: 280 break; 281 282 case O_STEP: 283 if (cmd->value.step.skipcalls) { 284 fprintf(f, "next"); 285 } else { 286 fprintf(f, "step"); 287 } 288 if (not cmd->value.step.source) { 289 fprintf(f, "i"); 290 } 291 break; 292 293 default: 294 fprintf(f, "%s", opinfo[ord(cmd->op)].opstring); 295 if (nargs(cmd->op) != 0) { 296 fprintf(f, " "); 297 } 298 break; 299 } 300 switch (cmd->op) { 301 case O_PRINTCALL: 302 case O_PRINTRTN: 303 case O_PROCRTN: 304 fprintf(f, "%s", symname(cmd->value.sym)); 305 break; 306 307 case O_PRINTSRCPOS: 308 p = cmd->value.arg[0]; 309 if (p != nil and p->op != O_QLINE) { 310 printf("trace "); 311 prtree(f, p); 312 } 313 break; 314 315 case O_CHFILE: 316 case O_EDIT: 317 case O_SOURCE: 318 fprintf(f, "%s", cmd->value.scon); 319 break; 320 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 #define fprintI(f, b) { if (b) fprintf(f, "i"); } 378 379 private print_tracestop(f, cmd) 380 File f; 381 Command cmd; 382 { 383 register Command c, ifcmd, stopcmd; 384 Boolean done; 385 386 done = false; 387 ifcmd = list_element(Command, list_head(cmd->value.trace.actions)); 388 checkref(ifcmd); 389 if (ifcmd->op == O_IF) { 390 stopcmd = list_element(Command, list_head(ifcmd->value.event.actions)); 391 checkref(stopcmd); 392 if (stopcmd->op == O_STOPX) { 393 fprintf(f, "stop"); 394 fprintI(f, cmd->value.trace.inst); 395 fprintf(f, " if "); 396 prtree(f, ifcmd->value.event.cond); 397 done = true; 398 } 399 } else if (ifcmd->op == O_STOPIFCHANGED) { 400 fprintf(f, "stop"); 401 fprintI(f, cmd->value.trace.inst); 402 fprintf(f, " "); 403 prtree(f, ifcmd->value.arg[0]); 404 done = true; 405 } 406 if (not done) { 407 fprintf(f, "%s ", cmd->value.trace.inst ? "tracei" : "trace"); 408 foreach (Command, c, cmd->value.trace.actions) 409 printcmd(f, c); 410 if (not list_islast()) { 411 fprintf(f, ";"); 412 } 413 endfor 414 } 415 } 416 417 /* 418 * Print out a tree. 419 */ 420 421 public prtree(f, p) 422 File f; 423 register Node p; 424 { 425 register Node q; 426 Operator op; 427 428 if (p != nil) { 429 op = p->op; 430 if (ord(op) > ord(O_LASTOP)) { 431 panic("bad op %d in prtree", p->op); 432 } 433 switch (op) { 434 case O_NAME: 435 fprintf(f, "%s", ident(p->value.name)); 436 break; 437 438 case O_SYM: 439 printname(f, p->value.sym); 440 break; 441 442 case O_QLINE: 443 if (nlhdr.nfiles > 1) { 444 prtree(f, p->value.arg[0]); 445 fprintf(f, ":"); 446 } 447 prtree(f, p->value.arg[1]); 448 break; 449 450 case O_LCON: 451 if (compatible(p->nodetype, t_char)) { 452 fprintf(f, "'%c'", p->value.lcon); 453 } else { 454 fprintf(f, "%d", p->value.lcon); 455 } 456 break; 457 458 case O_FCON: 459 fprintf(f, "%g", p->value.fcon); 460 break; 461 462 case O_SCON: 463 fprintf(f, "\"%s\"", p->value.scon); 464 break; 465 466 case O_INDEX: 467 prtree(f, p->value.arg[0]); 468 fprintf(f, "["); 469 prtree(f, p->value.arg[1]); 470 fprintf(f, "]"); 471 break; 472 473 case O_COMMA: 474 prtree(f, p->value.arg[0]); 475 if (p->value.arg[1] != nil) { 476 fprintf(f, ", "); 477 prtree(f, p->value.arg[1]); 478 } 479 break; 480 481 case O_RVAL: 482 if (p->value.arg[0]->op == O_SYM) { 483 printname(f, p->value.arg[0]->value.sym); 484 } else { 485 prtree(f, p->value.arg[0]); 486 } 487 break; 488 489 case O_ITOF: 490 prtree(f, p->value.arg[0]); 491 break; 492 493 case O_CALL: 494 prtree(f, p->value.arg[0]); 495 if (p->value.arg[1]!= nil) { 496 fprintf(f, "("); 497 prtree(f, p->value.arg[1]); 498 fprintf(f, ")"); 499 } 500 break; 501 502 case O_INDIR: 503 q = p->value.arg[0]; 504 if (isvarparam(q->nodetype)) { 505 prtree(f, q); 506 } else { 507 if (q->op == O_SYM or q->op == O_LCON or q->op == O_DOT) { 508 prtree(f, q); 509 fprintf(f, "^"); 510 } else { 511 fprintf(f, "*("); 512 prtree(f, q); 513 fprintf(f, ")"); 514 } 515 } 516 break; 517 518 case O_DOT: 519 q = p->value.arg[0]; 520 if (q->op == O_INDIR) { 521 prtree(f, q->value.arg[0]); 522 } else { 523 prtree(f, q); 524 } 525 fprintf(f, ".%s", symname(p->value.arg[1]->value.sym)); 526 break; 527 528 default: 529 switch (degree(op)) { 530 case BINARY: 531 prtree(f, p->value.arg[0]); 532 fprintf(f, "%s", opinfo[ord(op)].opstring); 533 prtree(f, p->value.arg[1]); 534 break; 535 536 case UNARY: 537 fprintf(f, "%s", opinfo[ord(op)].opstring); 538 prtree(f, p->value.arg[0]); 539 break; 540 541 default: 542 error("internal error: bad op %d in prtree", op); 543 } 544 break; 545 } 546 } 547 } 548 549 /* 550 * Free storage associated with a tree. 551 */ 552 553 public tfree(p) 554 Node p; 555 { 556 Integer i; 557 558 if (p == nil) { 559 return; 560 } 561 switch (p->op) { 562 case O_QLINE: 563 dispose(p->value.arg[0]->value.scon); 564 dispose(p->value.arg[0]); 565 tfree(p->value.arg[1]); 566 break; 567 568 case O_SCON: 569 unmkstring(p->nodetype); 570 dispose(p->nodetype); 571 dispose(p->value.scon); 572 break; 573 574 default: 575 for (i = 0; i < nargs(p->op); i++) { 576 tfree(p->value.arg[i]); 577 } 578 break; 579 } 580 dispose(p); 581 } 582 583 /* 584 * A recursive tree search routine to test if two trees are equivalent. 585 */ 586 587 public Boolean tr_equal(t1, t2) 588 register Node t1; 589 register Node t2; 590 { 591 register Boolean b; 592 593 if (t1 == nil and t2 == nil) { 594 b = true; 595 } else if (t1 == nil or t2 == nil) { 596 b = false; 597 } else if (t1->op != t2->op or degree(t1->op) != degree(t2->op)) { 598 b = false; 599 } else { 600 switch (degree(t1->op)) { 601 case LEAF: 602 switch (t1->op) { 603 case O_NAME: 604 b = (Boolean) (t1->value.name == t2->value.name); 605 break; 606 607 case O_SYM: 608 b = (Boolean) (t1->value.sym == t2->value.sym); 609 break; 610 611 case O_LCON: 612 b = (Boolean) (t1->value.lcon == t2->value.lcon); 613 break; 614 615 case O_FCON: 616 b = (Boolean) (t1->value.fcon == t2->value.fcon); 617 break; 618 619 case O_SCON: 620 b = (Boolean) (t1->value.scon == t2->value.scon); 621 break; 622 623 default: 624 panic("tr_equal: leaf %d\n", t1->op); 625 } 626 /*NOTREACHED*/ 627 628 case BINARY: 629 if (not tr_equal(t1->value.arg[0], t2->value.arg[0])) { 630 b = false; 631 } else { 632 b = tr_equal(t1->value.arg[1], t2->value.arg[1]); 633 } 634 break; 635 636 case UNARY: 637 b = tr_equal(t1->value.arg[0], t2->value.arg[0]); 638 break; 639 640 default: 641 panic("tr_equal: bad degree for op %d\n", t1->op); 642 } 643 } 644 return b; 645 } 646