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