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