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.3 (Berkeley) 01/12/88"; 9 #endif not lint 10 11 static char rcsid[] = "$Header: tree.c,v 1.3 87/07/08 21:38:59 donn 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 r->nodetype->language = p->nodetype->language; 260 break; 261 262 case O_SYM: 263 if (isblock(p->value.sym)) { 264 r = build(O_LCON, codeloc(p->value.sym)); 265 } else { 266 r = build(O_LCON, address(p->value.sym, nil)); 267 } 268 r->nodetype = t_addr; 269 dispose(p); 270 break; 271 272 case O_DOT: 273 r = p; 274 r->nodetype = t_addr; 275 break; 276 277 default: 278 beginerrmsg(); 279 fprintf(stderr, "expected variable, found \""); 280 prtree(stderr, p); 281 fprintf(stderr, "\""); 282 tfree(p); 283 enderrmsg(); 284 /* NOTREACHED */ 285 } 286 return r; 287 } 288 289 /* 290 * Create a "concrete" version of a node. 291 * This is necessary when the type of the node contains 292 * an unresolved type reference. 293 */ 294 295 public Node concrete(p) 296 Node p; 297 { 298 findtype(p->nodetype); 299 return build(O_INDIR, p); 300 } 301 302 /* 303 * Create a command list from a single command. 304 */ 305 306 public Cmdlist buildcmdlist(cmd) 307 Command cmd; 308 { 309 Cmdlist cmdlist; 310 311 cmdlist = list_alloc(); 312 cmdlist_append(cmd, cmdlist); 313 return cmdlist; 314 } 315 316 /* 317 * Print out a command. 318 */ 319 320 public printcmd(f, cmd) 321 File f; 322 Command cmd; 323 { 324 register Integer i; 325 register Command c; 326 register Node p; 327 328 switch (cmd->op) { 329 case O_PRINTIFCHANGED: 330 case O_PRINTSRCPOS: 331 case O_STOPIFCHANGED: 332 case O_TRACEON: 333 break; 334 335 case O_STEP: 336 if (cmd->value.step.skipcalls) { 337 fprintf(f, "next"); 338 } else { 339 fprintf(f, "step"); 340 } 341 if (not cmd->value.step.source) { 342 fprintf(f, "i"); 343 } 344 break; 345 346 default: 347 fprintf(f, "%s", opinfo[ord(cmd->op)].opstring); 348 if (nargs(cmd->op) != 0) { 349 fprintf(f, " "); 350 } 351 break; 352 } 353 switch (cmd->op) { 354 case O_PRINTCALL: 355 case O_PRINTRTN: 356 case O_PROCRTN: 357 fprintf(f, "%s", symname(cmd->value.sym)); 358 break; 359 360 case O_PRINTSRCPOS: 361 p = cmd->value.arg[0]; 362 if (p != nil and p->op != O_QLINE) { 363 printf("trace "); 364 prtree(f, p); 365 } 366 break; 367 368 case O_CHFILE: 369 case O_EDIT: 370 case O_SOURCE: 371 fprintf(f, "%s", cmd->value.scon); 372 break; 373 374 case O_CATCH: 375 case O_IGNORE: 376 case O_TRACEOFF: 377 fprintf(f, "%d", cmd->value.lcon); 378 break; 379 380 case O_ADDEVENT: 381 case O_ONCE: 382 case O_IF: 383 fprintf(f, " "); 384 prtree(f, cmd->value.event.cond); 385 fprintf(f, " { "); 386 foreach (Command, c, cmd->value.event.actions) 387 printcmd(f, c); 388 if (not list_islast()) { 389 fprintf(f, ";"); 390 } 391 endfor 392 fprintf(f, "%s }", opinfo[ord(cmd->op)].opstring); 393 break; 394 395 case O_TRACEON: 396 print_tracestop(f, cmd); 397 break; 398 399 case O_EXAMINE: 400 prtree(f, cmd->value.examine.beginaddr); 401 if (cmd->value.examine.endaddr != nil) { 402 fprintf(f, ","); 403 prtree(f, cmd->value.examine.endaddr); 404 } 405 fprintf(f, "/"); 406 if (cmd->value.examine.count > 1) { 407 fprintf(f, "%d", cmd->value.examine.count); 408 } 409 fprintf("%s", cmd->value.examine.mode); 410 break; 411 412 default: 413 if (nargs(cmd->op) != 0) { 414 i = 0; 415 for (;;) { 416 prtree(f, cmd->value.arg[i]); 417 ++i; 418 if (i >= nargs(cmd->op)) break; 419 fprintf(f, " "); 420 } 421 } 422 break; 423 } 424 } 425 426 /* 427 * Print out a trace/stop command name. 428 */ 429 430 #define fprintI(f, b) { if (b) fprintf(f, "i"); } 431 432 private print_tracestop(f, cmd) 433 File f; 434 Command cmd; 435 { 436 register Command c, ifcmd, stopcmd; 437 Boolean done; 438 439 done = false; 440 ifcmd = list_element(Command, list_head(cmd->value.trace.actions)); 441 checkref(ifcmd); 442 if (ifcmd->op == O_IF) { 443 stopcmd = list_element(Command, list_head(ifcmd->value.event.actions)); 444 checkref(stopcmd); 445 if (stopcmd->op == O_STOPX) { 446 fprintf(f, "stop"); 447 fprintI(f, cmd->value.trace.inst); 448 fprintf(f, " if "); 449 prtree(f, ifcmd->value.event.cond); 450 done = true; 451 } 452 } else if (ifcmd->op == O_STOPIFCHANGED) { 453 fprintf(f, "stop"); 454 fprintI(f, cmd->value.trace.inst); 455 fprintf(f, " "); 456 prtree(f, ifcmd->value.arg[0]); 457 done = true; 458 } 459 if (not done) { 460 fprintf(f, "%s ", cmd->value.trace.inst ? "tracei" : "trace"); 461 foreach (Command, c, cmd->value.trace.actions) 462 printcmd(f, c); 463 if (not list_islast()) { 464 fprintf(f, ";"); 465 } 466 endfor 467 } 468 } 469 470 /* 471 * Print out a tree. 472 */ 473 474 public prtree(f, p) 475 File f; 476 register Node p; 477 { 478 register Node q; 479 Operator op; 480 481 if (p != nil) { 482 op = p->op; 483 if (ord(op) > ord(O_LASTOP)) { 484 panic("bad op %d in prtree", p->op); 485 } 486 switch (op) { 487 case O_NAME: 488 fprintf(f, "%s", ident(p->value.name)); 489 break; 490 491 case O_SYM: 492 printname(f, p->value.sym); 493 break; 494 495 case O_QLINE: 496 if (nlhdr.nfiles > 1) { 497 prtree(f, p->value.arg[0]); 498 fprintf(f, ":"); 499 } 500 prtree(f, p->value.arg[1]); 501 break; 502 503 case O_LCON: 504 fprintf(f, "%d", p->value.lcon); 505 break; 506 507 case O_CCON: 508 fprintf(f, "'%c'", p->value.lcon); 509 break; 510 511 case O_FCON: 512 fprintf(f, "%g", p->value.fcon); 513 break; 514 515 case O_SCON: 516 fprintf(f, "\"%s\"", p->value.scon); 517 break; 518 519 case O_INDEX: 520 prtree(f, p->value.arg[0]); 521 fprintf(f, "["); 522 prtree(f, p->value.arg[1]); 523 fprintf(f, "]"); 524 break; 525 526 case O_COMMA: 527 prtree(f, p->value.arg[0]); 528 if (p->value.arg[1] != nil) { 529 fprintf(f, ", "); 530 prtree(f, p->value.arg[1]); 531 } 532 break; 533 534 case O_RVAL: 535 case O_ITOF: 536 prtree(f, p->value.arg[0]); 537 break; 538 539 case O_CALL: 540 prtree(f, p->value.arg[0]); 541 if (p->value.arg[1]!= nil) { 542 fprintf(f, "("); 543 prtree(f, p->value.arg[1]); 544 fprintf(f, ")"); 545 } 546 break; 547 548 case O_INDIR: 549 prtree(f, p->value.arg[0]); 550 fprintf(f, "^"); 551 break; 552 553 case O_DOT: 554 prtree(f, p->value.arg[0]); 555 fprintf(f, ".%s", symname(p->value.arg[1]->value.sym)); 556 break; 557 558 case O_TYPERENAME: 559 prtree(f, p->value.arg[1]); 560 fprintf(f, "("); 561 prtree(f, p->value.arg[0]); 562 fprintf(f, ")"); 563 break; 564 565 default: 566 switch (degree(op)) { 567 case BINARY: 568 prtree(f, p->value.arg[0]); 569 fprintf(f, "%s", opinfo[ord(op)].opstring); 570 prtree(f, p->value.arg[1]); 571 break; 572 573 case UNARY: 574 fprintf(f, "%s", opinfo[ord(op)].opstring); 575 prtree(f, p->value.arg[0]); 576 break; 577 578 default: 579 if (opinfo[ord(op)].opstring == nil) { 580 fprintf(f, "[op %d]", ord(op)); 581 } else { 582 fprintf(f, "%s", opinfo[ord(op)].opstring); 583 } 584 break; 585 } 586 break; 587 } 588 } 589 } 590 591 /* 592 * Free storage associated with a tree. 593 */ 594 595 public tfree(p) 596 Node p; 597 { 598 Integer i; 599 600 if (p == nil) { 601 return; 602 } 603 switch (p->op) { 604 case O_QLINE: 605 dispose(p->value.arg[0]->value.scon); 606 dispose(p->value.arg[0]); 607 tfree(p->value.arg[1]); 608 break; 609 610 case O_SCON: 611 unmkstring(p->nodetype); 612 dispose(p->nodetype); 613 dispose(p->value.scon); 614 break; 615 616 default: 617 for (i = 0; i < nargs(p->op); i++) { 618 tfree(p->value.arg[i]); 619 } 620 break; 621 } 622 dispose(p); 623 } 624