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