4.4BSD/usr/src/old/dbx/tree.c
/*
* Copyright (c) 1983 The Regents of the University of California.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#ifndef lint
static char sccsid[] = "@(#)tree.c 5.5 (Berkeley) 6/1/90";
#endif /* not lint */
/*
* Parse tree management.
*/
#include "defs.h"
#include "tree.h"
#include "operators.h"
#include "debug.h"
#include "eval.h"
#include "events.h"
#include "symbols.h"
#include "scanner.h"
#include "source.h"
#include "object.h"
#include "mappings.h"
#include "process.h"
#include "machine.h"
#ifndef public
#include "lists.h"
typedef struct Node *Node;
typedef Node Command;
typedef List Cmdlist;
#include "operators.h"
#include "symbols.h"
#include "events.h"
#define MAXNARGS 5
struct Node {
Operator op;
Symbol nodetype;
union treevalue {
Symbol sym;
Name name;
long lcon;
double fcon;
String scon;
Node arg[MAXNARGS];
struct {
Node cond;
Cmdlist actions;
} event;
struct {
Boolean inst;
Event event;
Cmdlist actions;
} trace;
struct {
Boolean source;
Boolean skipcalls;
} step;
struct {
String mode;
Node beginaddr;
Node endaddr;
Integer count;
} examine;
} value;
};
#define evalcmd(cmd) eval(cmd)
#define cmdlist_append(cmd, cl) list_append(list_item(cmd), nil, cl)
#endif
typedef char *Arglist;
#define nextarg(type) ((type *) (ap += sizeof(type)))[-1]
/*
* Build a tree.
*/
/* VARARGS1 */
public Node build(op, args)
Operator op;
{
register Node p, q;
register Arglist ap;
Integer i;
p = new(Node);
p->op = op;
p->nodetype = nil;
ap = (Arglist) &args;
switch (op) {
case O_NAME:
p->value.name = nextarg(Name);
break;
case O_SYM:
case O_PRINTCALL:
case O_PRINTRTN:
case O_PROCRTN:
p->value.sym = nextarg(Symbol);
break;
case O_DEBUG:
case O_LCON:
case O_CCON:
case O_CONT:
case O_CATCH:
case O_IGNORE:
case O_TRACEOFF:
p->value.lcon = nextarg(long);
break;
case O_FCON:
p->value.fcon = nextarg(double);
break;
case O_SCON:
case O_CHFILE:
case O_EDIT:
case O_SOURCE:
p->value.scon = nextarg(String);
break;
case O_RVAL:
case O_INDIR:
p->value.arg[0] = nextarg(Node);
break;
case O_CALL:
q = nextarg(Node);
if (q->op == O_SYM and
(q->value.sym->class == TYPE or q->value.sym->class == TAG)
) {
p->op = O_TYPERENAME;
p->value.arg[0] = nextarg(Node);
p->value.arg[1] = q;
q = p->value.arg[0];
if (q->value.arg[1] != nil) {
error("too many arguments to type rename");
}
p->value.arg[0] = q->value.arg[0];
} else {
p->value.arg[0] = q;
p->value.arg[1] = nextarg(Node);
}
break;
case O_ADDEVENT:
case O_ONCE:
case O_IF:
p->value.event.cond = nextarg(Node);
p->value.event.actions = nextarg(Cmdlist);
break;
case O_TRACEON:
p->value.trace.inst = nextarg(Boolean);
p->value.trace.event = nil;
p->value.trace.actions = nextarg(Cmdlist);
break;
case O_STEP:
p->value.step.source = nextarg(Boolean);
p->value.step.skipcalls = nextarg(Boolean);
break;
case O_EXAMINE:
p->value.examine.mode = nextarg(String);
p->value.examine.beginaddr = nextarg(Node);
p->value.examine.endaddr = nextarg(Node);
p->value.examine.count = nextarg(Integer);
break;
default:
for (i = 0; i < nargs(op); i++) {
p->value.arg[i] = nextarg(Node);
}
break;
}
check(p);
assigntypes(p);
if (tracetree) {
printf("built %s node 0x%x with arg[0] 0x%x arg[1] 0x%x\n",
opname(p->op), p, p->value.arg[0], p->value.arg[1]);
fflush(stdout);
}
return p;
}
/*
* Strip away indirection from a node, thus returning a node for
* interpreting the expression as an lvalue.
*/
public Node unrval (exp)
Node exp;
{
Node p;
Symbol t;
if (exp->op == O_RVAL) {
p = exp->value.arg[0];
dispose(exp);
} else if (exp->op == O_INDIR) {
p = exp->value.arg[0];
if (p->op == O_RVAL) {
p->op = O_INDIR;
p->nodetype = exp->nodetype;
}
dispose(exp);
} else {
p = exp;
}
return p;
}
/*
* Create a node for renaming a node to a pointer type.
*/
public Node renameptr (p, t)
Node p;
Node t;
{
t->nodetype = newSymbol(nil, 0, PTR, t->nodetype, nil);
p = build(O_TYPERENAME, p, t);
}
/*
* Return the tree for a unary ampersand operator.
*/
public Node amper(p)
Node p;
{
Node r;
checkref(p);
switch (p->op) {
case O_RVAL:
case O_INDIR:
r = p->value.arg[0];
r->nodetype = t_addr;
dispose(p);
break;
case O_TYPERENAME:
r = p;
r->nodetype = newSymbol(nil, 0, PTR, r->nodetype, nil);
r->nodetype->language = p->nodetype->language;
break;
case O_SYM:
if (isblock(p->value.sym)) {
r = build(O_LCON, codeloc(p->value.sym));
} else {
r = build(O_LCON, address(p->value.sym, nil));
}
r->nodetype = t_addr;
dispose(p);
break;
case O_DOT:
r = p;
r->nodetype = t_addr;
break;
default:
beginerrmsg();
fprintf(stderr, "expected variable, found \"");
prtree(stderr, p);
fprintf(stderr, "\"");
tfree(p);
enderrmsg();
/* NOTREACHED */
}
return r;
}
/*
* Create a "concrete" version of a node.
* This is necessary when the type of the node contains
* an unresolved type reference.
*/
public Node concrete(p)
Node p;
{
findtype(p->nodetype);
return build(O_INDIR, p);
}
/*
* Create a command list from a single command.
*/
public Cmdlist buildcmdlist(cmd)
Command cmd;
{
Cmdlist cmdlist;
cmdlist = list_alloc();
cmdlist_append(cmd, cmdlist);
return cmdlist;
}
/*
* Print out a command.
*/
public printcmd(f, cmd)
File f;
Command cmd;
{
register Integer i;
register Command c;
register Node p;
switch (cmd->op) {
case O_PRINTIFCHANGED:
case O_PRINTSRCPOS:
case O_STOPIFCHANGED:
case O_TRACEON:
break;
case O_STEP:
if (cmd->value.step.skipcalls) {
fprintf(f, "next");
} else {
fprintf(f, "step");
}
if (not cmd->value.step.source) {
fprintf(f, "i");
}
break;
default:
fprintf(f, "%s", opinfo[ord(cmd->op)].opstring);
if (nargs(cmd->op) != 0) {
fprintf(f, " ");
}
break;
}
switch (cmd->op) {
case O_PRINTCALL:
case O_PRINTRTN:
case O_PROCRTN:
fprintf(f, "%s", symname(cmd->value.sym));
break;
case O_PRINTSRCPOS:
p = cmd->value.arg[0];
if (p != nil and p->op != O_QLINE) {
printf("trace ");
prtree(f, p);
}
break;
case O_CHFILE:
case O_EDIT:
case O_SOURCE:
fprintf(f, "%s", cmd->value.scon);
break;
case O_CATCH:
case O_IGNORE:
case O_TRACEOFF:
fprintf(f, "%d", cmd->value.lcon);
break;
case O_ADDEVENT:
case O_ONCE:
case O_IF:
fprintf(f, " ");
prtree(f, cmd->value.event.cond);
fprintf(f, " { ");
foreach (Command, c, cmd->value.event.actions)
printcmd(f, c);
if (not list_islast()) {
fprintf(f, ";");
}
endfor
fprintf(f, "%s }", opinfo[ord(cmd->op)].opstring);
break;
case O_TRACEON:
print_tracestop(f, cmd);
break;
case O_EXAMINE:
prtree(f, cmd->value.examine.beginaddr);
if (cmd->value.examine.endaddr != nil) {
fprintf(f, ",");
prtree(f, cmd->value.examine.endaddr);
}
fprintf(f, "/");
if (cmd->value.examine.count > 1) {
fprintf(f, "%d", cmd->value.examine.count);
}
fprintf("%s", cmd->value.examine.mode);
break;
default:
if (nargs(cmd->op) != 0) {
i = 0;
for (;;) {
prtree(f, cmd->value.arg[i]);
++i;
if (i >= nargs(cmd->op)) break;
fprintf(f, " ");
}
}
break;
}
}
/*
* Print out a trace/stop command name.
*/
#define fprintI(f, b) { if (b) fprintf(f, "i"); }
private print_tracestop(f, cmd)
File f;
Command cmd;
{
register Command c, ifcmd, stopcmd;
Boolean done;
done = false;
ifcmd = list_element(Command, list_head(cmd->value.trace.actions));
checkref(ifcmd);
if (ifcmd->op == O_IF) {
stopcmd = list_element(Command, list_head(ifcmd->value.event.actions));
checkref(stopcmd);
if (stopcmd->op == O_STOPX) {
fprintf(f, "stop");
fprintI(f, cmd->value.trace.inst);
fprintf(f, " if ");
prtree(f, ifcmd->value.event.cond);
done = true;
}
} else if (ifcmd->op == O_STOPIFCHANGED) {
fprintf(f, "stop");
fprintI(f, cmd->value.trace.inst);
fprintf(f, " ");
prtree(f, ifcmd->value.arg[0]);
done = true;
}
if (not done) {
fprintf(f, "%s ", cmd->value.trace.inst ? "tracei" : "trace");
foreach (Command, c, cmd->value.trace.actions)
printcmd(f, c);
if (not list_islast()) {
fprintf(f, ";");
}
endfor
}
}
/*
* Print out a tree.
*/
public prtree(f, p)
File f;
register Node p;
{
register Node q;
Operator op;
if (p != nil) {
op = p->op;
if (ord(op) > ord(O_LASTOP)) {
panic("bad op %d in prtree", p->op);
}
switch (op) {
case O_NAME:
fprintf(f, "%s", ident(p->value.name));
break;
case O_SYM:
printname(f, p->value.sym);
break;
case O_QLINE:
if (nlhdr.nfiles > 1) {
prtree(f, p->value.arg[0]);
fprintf(f, ":");
}
prtree(f, p->value.arg[1]);
break;
case O_LCON:
fprintf(f, "%d", p->value.lcon);
break;
case O_CCON:
fprintf(f, "'%c'", p->value.lcon);
break;
case O_FCON:
fprintf(f, "%g", p->value.fcon);
break;
case O_SCON:
fprintf(f, "\"%s\"", p->value.scon);
break;
case O_INDEX:
prtree(f, p->value.arg[0]);
fprintf(f, "[");
prtree(f, p->value.arg[1]);
fprintf(f, "]");
break;
case O_COMMA:
prtree(f, p->value.arg[0]);
if (p->value.arg[1] != nil) {
fprintf(f, ", ");
prtree(f, p->value.arg[1]);
}
break;
case O_RVAL:
case O_ITOF:
prtree(f, p->value.arg[0]);
break;
case O_CALL:
prtree(f, p->value.arg[0]);
if (p->value.arg[1]!= nil) {
fprintf(f, "(");
prtree(f, p->value.arg[1]);
fprintf(f, ")");
}
break;
case O_INDIR:
prtree(f, p->value.arg[0]);
fprintf(f, "^");
break;
case O_DOT:
prtree(f, p->value.arg[0]);
fprintf(f, ".%s", symname(p->value.arg[1]->value.sym));
break;
case O_TYPERENAME:
prtree(f, p->value.arg[1]);
fprintf(f, "(");
prtree(f, p->value.arg[0]);
fprintf(f, ")");
break;
default:
switch (degree(op)) {
case BINARY:
prtree(f, p->value.arg[0]);
fprintf(f, "%s", opinfo[ord(op)].opstring);
prtree(f, p->value.arg[1]);
break;
case UNARY:
fprintf(f, "%s", opinfo[ord(op)].opstring);
prtree(f, p->value.arg[0]);
break;
default:
if (opinfo[ord(op)].opstring == nil) {
fprintf(f, "[op %d]", ord(op));
} else {
fprintf(f, "%s", opinfo[ord(op)].opstring);
}
break;
}
break;
}
}
}
/*
* Free storage associated with a tree.
*/
public tfree(p)
Node p;
{
Integer i;
if (p == nil) {
return;
}
switch (p->op) {
case O_QLINE:
dispose(p->value.arg[0]->value.scon);
dispose(p->value.arg[0]);
tfree(p->value.arg[1]);
break;
case O_SCON:
unmkstring(p->nodetype);
dispose(p->nodetype);
dispose(p->value.scon);
break;
default:
for (i = 0; i < nargs(p->op); i++) {
tfree(p->value.arg[i]);
}
break;
}
dispose(p);
}