1 /* 2 * Copyright (c) 1983 Regents of the University of California. 3 * All rights reserved. The Berkeley software License Agreement 4 * specifies the terms and conditions for redistribution. 5 */ 6 7 #ifndef lint 8 static char sccsid[] = "@(#)tree.c 5.2 (Berkeley) 04/06/87"; 9 #endif not lint 10 11 static char rcsid[] = "$Header: tree.c,v 1.5 84/12/26 10:42:55 linton Exp $"; 12 13 /* 14 * Parse tree management. 15 */ 16 17 #include "defs.h" 18 #include "tree.h" 19 #include "operators.h" 20 #include "debug.h" 21 #include "eval.h" 22 #include "events.h" 23 #include "symbols.h" 24 #include "scanner.h" 25 #include "source.h" 26 #include "object.h" 27 #include "mappings.h" 28 #include "process.h" 29 #include "machine.h" 30 31 #ifndef public 32 #include "lists.h" 33 34 typedef struct Node *Node; 35 typedef Node Command; 36 typedef List Cmdlist; 37 38 #include "operators.h" 39 #include "symbols.h" 40 #include "events.h" 41 42 #define MAXNARGS 5 43 44 struct Node { 45 Operator op; 46 Symbol nodetype; 47 union treevalue { 48 Symbol sym; 49 Name name; 50 long lcon; 51 double fcon; 52 String scon; 53 Node arg[MAXNARGS]; 54 struct { 55 Node cond; 56 Cmdlist actions; 57 } event; 58 struct { 59 Boolean inst; 60 Event event; 61 Cmdlist actions; 62 } trace; 63 struct { 64 Boolean source; 65 Boolean skipcalls; 66 } step; 67 struct { 68 String mode; 69 Node beginaddr; 70 Node endaddr; 71 Integer count; 72 } examine; 73 } value; 74 }; 75 76 #define evalcmd(cmd) eval(cmd) 77 #define cmdlist_append(cmd, cl) list_append(list_item(cmd), nil, cl) 78 79 #endif 80 81 typedef char *Arglist; 82 83 #define nextarg(type) ((type *) (ap += sizeof(type)))[-1] 84 85 /* 86 * Build a tree. 87 */ 88 89 /* VARARGS1 */ 90 public Node build(op, args) 91 Operator op; 92 { 93 register Node p, q; 94 register Arglist ap; 95 Integer i; 96 97 p = new(Node); 98 p->op = op; 99 p->nodetype = nil; 100 ap = (Arglist) &args; 101 switch (op) { 102 case O_NAME: 103 p->value.name = nextarg(Name); 104 break; 105 106 case O_SYM: 107 case O_PRINTCALL: 108 case O_PRINTRTN: 109 case O_PROCRTN: 110 p->value.sym = nextarg(Symbol); 111 break; 112 113 case O_DEBUG: 114 case O_LCON: 115 case O_CCON: 116 case O_CONT: 117 case O_CATCH: 118 case O_IGNORE: 119 case O_TRACEOFF: 120 p->value.lcon = nextarg(long); 121 break; 122 123 case O_FCON: 124 p->value.fcon = nextarg(double); 125 break; 126 127 case O_SCON: 128 case O_CHFILE: 129 case O_EDIT: 130 case O_SOURCE: 131 p->value.scon = nextarg(String); 132 break; 133 134 case O_RVAL: 135 case O_INDIR: 136 p->value.arg[0] = nextarg(Node); 137 break; 138 139 case O_CALL: 140 q = nextarg(Node); 141 if (q->op == O_SYM and 142 (q->value.sym->class == TYPE or q->value.sym->class == TAG) 143 ) { 144 p->op = O_TYPERENAME; 145 p->value.arg[0] = nextarg(Node); 146 p->value.arg[1] = q; 147 q = p->value.arg[0]; 148 if (q->value.arg[1] != nil) { 149 error("too many arguments to type rename"); 150 } 151 p->value.arg[0] = q->value.arg[0]; 152 } else { 153 p->value.arg[0] = q; 154 p->value.arg[1] = nextarg(Node); 155 } 156 break; 157 158 case O_ADDEVENT: 159 case O_ONCE: 160 case O_IF: 161 p->value.event.cond = nextarg(Node); 162 p->value.event.actions = nextarg(Cmdlist); 163 break; 164 165 case O_TRACEON: 166 p->value.trace.inst = nextarg(Boolean); 167 p->value.trace.event = nil; 168 p->value.trace.actions = nextarg(Cmdlist); 169 break; 170 171 case O_STEP: 172 p->value.step.source = nextarg(Boolean); 173 p->value.step.skipcalls = nextarg(Boolean); 174 break; 175 176 case O_EXAMINE: 177 p->value.examine.mode = nextarg(String); 178 p->value.examine.beginaddr = nextarg(Node); 179 p->value.examine.endaddr = nextarg(Node); 180 p->value.examine.count = nextarg(Integer); 181 break; 182 183 default: 184 for (i = 0; i < nargs(op); i++) { 185 p->value.arg[i] = nextarg(Node); 186 } 187 break; 188 } 189 check(p); 190 assigntypes(p); 191 if (tracetree) { 192 printf("built %s node 0x%x with arg[0] 0x%x arg[1] 0x%x\n", 193 opname(p->op), p, p->value.arg[0], p->value.arg[1]); 194 fflush(stdout); 195 } 196 return p; 197 } 198 199 /* 200 * Strip away indirection from a node, thus returning a node for 201 * interpreting the expression as an lvalue. 202 */ 203 204 public Node unrval (exp) 205 Node exp; 206 { 207 Node p; 208 Symbol t; 209 210 if (exp->op == O_RVAL) { 211 p = exp->value.arg[0]; 212 dispose(exp); 213 } else if (exp->op == O_INDIR) { 214 p = exp->value.arg[0]; 215 if (p->op == O_RVAL) { 216 p->op = O_INDIR; 217 p->nodetype = exp->nodetype; 218 } 219 dispose(exp); 220 } else { 221 p = exp; 222 } 223 return p; 224 } 225 226 /* 227 * Create a node for renaming a node to a pointer type. 228 */ 229 230 public Node renameptr (p, t) 231 Node p; 232 Node t; 233 { 234 t->nodetype = newSymbol(nil, 0, PTR, t->nodetype, nil); 235 p = build(O_TYPERENAME, p, t); 236 } 237 238 /* 239 * Return the tree for a unary ampersand operator. 240 */ 241 242 public Node amper(p) 243 Node p; 244 { 245 Node r; 246 247 checkref(p); 248 switch (p->op) { 249 case O_RVAL: 250 case O_INDIR: 251 r = p->value.arg[0]; 252 r->nodetype = t_addr; 253 dispose(p); 254 break; 255 256 case O_TYPERENAME: 257 r = p; 258 r->nodetype = newSymbol(nil, 0, PTR, r->nodetype, nil); 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