← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to tools/gpr/gpr.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/gpr/gpr.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
 
 
11
/*
 
12
 * gpr: graph pattern recognizer
 
13
 *
 
14
 * Written by Emden Gansner
 
15
 */
 
16
 
 
17
#include <stdio.h>
 
18
#include <unistd.h>
 
19
#include <gprstate.h>
 
20
#include <agraph.h>
 
21
#include <ingraphs.h>
 
22
#include <compile.h>
 
23
#include <queue.h>
 
24
#include <sfstr.h>
 
25
#include <error.h>
 
26
#ifdef NO_OPTOPT_DECL
 
27
#include "getopt.h"
 
28
#endif
 
29
 
 
30
static const char* usage =
 
31
": gpr [-o <ofile>] ([-f <prog>] | 'prog') [files]\n\
 
32
   -c         - use source graph for output\n\
 
33
   -f <pfile> - find program in file <pfile>\n\
 
34
   -i         - create node induced subgraph\n\
 
35
   -o <ofile> - write output to <ofile>; stdout by default\n\
 
36
If no files are specified, stdin is used\n";
 
37
 
 
38
struct {
 
39
  char*     cmdName;
 
40
  FILE*     outFile;        /* output stream; stdout default */
 
41
  char*     program;
 
42
  int       useFile;        /* true if program comes from a file */
 
43
  int       compflags;
 
44
  char**    inFiles;
 
45
} options;
 
46
 
 
47
static FILE*
 
48
openOut (char* name)
 
49
{
 
50
  FILE*   outs;
 
51
 
 
52
  outs = fopen(name,"w");
 
53
  if (outs == 0) { 
 
54
    error (3|ERROR_SYSTEM, "could not open %s for writing", name);
 
55
  }
 
56
  return outs;
 
57
}
 
58
 
 
59
/* scanArgs:
 
60
 * Parse command line options.
 
61
 */
 
62
static void
 
63
scanArgs(int argc,char **argv)
 
64
{
 
65
  int       c;
 
66
  char*     outname = 0;
 
67
 
 
68
  options.cmdName = argv[0];
 
69
  options.outFile = 0;
 
70
  options.useFile = 0;
 
71
  error_info.id = options.cmdName;
 
72
 
 
73
  while ((c = getopt(argc, argv, ":?cif:o:")) != -1) {
 
74
    switch (c) {
 
75
      case 'c':
 
76
        options.compflags |= SRCOUT;
 
77
        break;
 
78
      case 'f':
 
79
        options.useFile = 1;
 
80
        options.program = optarg;
 
81
        break;
 
82
      case 'i':
 
83
        options.compflags |= INDUCE;
 
84
        break;
 
85
      case 'o':
 
86
        outname = optarg;
 
87
        break;
 
88
      case '?':
 
89
        if (optopt == '?') {
 
90
          error(ERROR_USAGE, "%s", usage);
 
91
          exit (0);
 
92
        }
 
93
        else {
 
94
          error(2, "option -%c unrecognized\n", optopt);
 
95
        }
 
96
        break;
 
97
      case ':':
 
98
        error(2, "missing argument for option -%c", optopt);
 
99
        break;
 
100
    }
 
101
  }
 
102
  argv += optind;
 
103
  argc -= optind;
 
104
 
 
105
    /* Handle additional semantics */
 
106
  if (options.useFile == 0) {
 
107
    if (argc == 0) {
 
108
      error(2, "No program supplied via argument or -f option");
 
109
      error_info.errors = 1;
 
110
    }
 
111
    else {
 
112
      options.program = *argv++;
 
113
      argc--;
 
114
    }
 
115
  }
 
116
  if (argc == 0) options.inFiles = 0;
 
117
  else options.inFiles = argv;
 
118
  if (outname) options.outFile = openOut (outname);
 
119
  else options.outFile = stdout;
 
120
 
 
121
  if (error_info.errors)
 
122
    error(ERROR_USAGE|4, "%s", usage);
 
123
}
 
124
 
 
125
static void
 
126
evalEdge (Gpr_t* state, comp_prog* xprog, Agedge_t* e)
 
127
{
 
128
  int         i;
 
129
  case_stmt*  cs;
 
130
  int         okay;
 
131
 
 
132
  state->curobj = (Agobj_t*)e;
 
133
  for (i = 0; i < xprog->n_estmts; i++) {
 
134
    cs = xprog->edge_stmts+i;
 
135
    if (cs->guard) 
 
136
      okay = (exeval (xprog->prog, cs->guard, state)).integer;
 
137
    else okay = 1;
 
138
    if (okay) {
 
139
      if (cs->action) exeval (xprog->prog, cs->action, state);
 
140
      else agsubedge (state->target, e, TRUE);
 
141
    }
 
142
  }
 
143
}
 
144
 
 
145
static void
 
146
evalNode (Gpr_t* state, comp_prog* xprog, Agnode_t* n)
 
147
{
 
148
  int         i;
 
149
  case_stmt*  cs;
 
150
  int         okay;
 
151
 
 
152
  state->curobj = (Agobj_t*)n;
 
153
  for (i = 0; i < xprog->n_nstmts; i++) {
 
154
    cs = xprog->node_stmts+i;
 
155
    if (cs->guard) okay = (exeval (xprog->prog, cs->guard, state)).integer;
 
156
    else okay = 1;
 
157
    if (okay) {
 
158
      if (cs->action) exeval (xprog->prog, cs->action, state);
 
159
      else agsubnode (state->target, n, TRUE);
 
160
    }
 
161
  }
 
162
}
 
163
 
 
164
#define nData(n)    ((ndata*)(aggetrec(n,UDATA,0)))
 
165
#define MARKED(x)  (((x)->iu.integer)&1)
 
166
#define MARK(x)  (((x)->iu.integer) = 1)
 
167
#define ONSTACK(x)  (((x)->iu.integer)&2)
 
168
#define PUSH(x)  (((x)->iu.integer)|=2)
 
169
#define POP(x)  (((x)->iu.integer)&=(~2))
 
170
 
 
171
static void
 
172
travDFS (Gpr_t* state, comp_prog* xprog)
 
173
{
 
174
  Agnode_t*     n;
 
175
  queue*        stk;
 
176
  Agedgepair_t  seed;
 
177
  Agnode_t*     curn;
 
178
  Agedge_t*     cure;
 
179
  Agedge_t*     entry;
 
180
  int           more;
 
181
  ndata*        nd;
 
182
 
 
183
  stk = mkStack ();
 
184
  for (n = agfstnode(state->curgraph); n; n = agnxtnode(n)) {
 
185
    nd = nData(n);
 
186
    if (MARKED(nd)) continue;
 
187
    seed.out.node = n;
 
188
    seed.in.node = 0;
 
189
    curn = n;
 
190
    entry = &(seed.out);
 
191
    cure = 0;
 
192
    MARK(nd);
 
193
    PUSH(nd);
 
194
    evalNode (state, xprog, n);
 
195
    more = 1;
 
196
    while (more) {
 
197
      if (cure) cure = agnxtedge (cure,curn);
 
198
      else cure = agfstedge (curn);
 
199
      if (cure) {
 
200
        if (entry == agopp(cure)) continue;
 
201
        nd = nData(cure->node);
 
202
        if (MARKED(nd)) {
 
203
          if (ONSTACK(nd))
 
204
            evalEdge (state, xprog, cure);
 
205
        }
 
206
        else {
 
207
          evalEdge (state, xprog, cure);
 
208
          push(stk, entry);
 
209
          entry = cure;
 
210
          curn = cure->node;
 
211
          cure = 0;
 
212
          evalNode (state, xprog, curn);
 
213
          MARK(nd);
 
214
          PUSH(nd);
 
215
        }
 
216
      }
 
217
      else {
 
218
        nd = nData(curn);
 
219
        POP(nd);
 
220
        cure = entry;
 
221
        entry = (Agedge_t*)pull(stk);
 
222
        if (entry) curn = entry->node;
 
223
        else more = 0;
 
224
      }
 
225
    }
 
226
  }
 
227
}
 
228
  
 
229
static void
 
230
travFlat (Gpr_t* state, comp_prog* xprog)
 
231
{
 
232
  Agnode_t*   n;
 
233
  Agedge_t*   e;
 
234
 
 
235
  for (n = agfstnode(state->curgraph); n; n = agnxtnode(n)) {
 
236
    evalNode (state, xprog, n);
 
237
    if (xprog->n_estmts > 0) {
 
238
      for (e = agfstout(n); e; e = agnxtout(e)) {
 
239
        evalEdge (state, xprog, e);
 
240
      }
 
241
    }
 
242
  }
 
243
}
 
244
  
 
245
static void
 
246
traverse (Gpr_t* state, comp_prog* xprog)
 
247
{
 
248
  char*       target;
 
249
 
 
250
  if (state->name_used) {
 
251
    sfprintf (state->tmp, "%s%d", state->tgtname, state->name_used);
 
252
    target = sfstruse (state->tmp);
 
253
  }
 
254
  else target = state->tgtname;
 
255
  state->name_used++;
 
256
  state->target = agsubg(state->curgraph,target,TRUE);
 
257
  state->outgraph = state->target;
 
258
 
 
259
  if (state->tvt == TV_dfs)
 
260
    travDFS (state, xprog);
 
261
  else 
 
262
    travFlat (state, xprog);
 
263
}
 
264
 
 
265
static Agraph_t*
 
266
readG (FILE* fp)
 
267
{
 
268
  Agraph_t*   g;
 
269
 
 
270
  g = agread(fp, 0);
 
271
  if (g) {
 
272
    aginit(g,AGRAPH,UDATA,sizeof(gdata),0);
 
273
    aginit(g,AGNODE,UDATA,sizeof(ndata),0);
 
274
    aginit(g,AGEDGE,UDATA,sizeof(edata),0);
 
275
  }
 
276
  return g;
 
277
}
 
278
 
 
279
int 
 
280
main (int argc, char* argv[])
 
281
{
 
282
  parse_prog*     prog;
 
283
  ingraph_state*  ing;
 
284
  comp_prog*      xprog;
 
285
  Gpr_t*          state;
 
286
 
 
287
  scanArgs(argc,argv);
 
288
 
 
289
  prog = parseProg (options.program, options.useFile);
 
290
  state = openGPRState ();
 
291
  xprog = compileProg (prog, state, options.compflags);
 
292
  initGPRState (state,xprog->prog->vm,options.outFile);
 
293
 
 
294
    /* do begin */
 
295
  if (xprog->begin_stmt)
 
296
    exeval (xprog->prog, xprog->begin_stmt, state);
 
297
 
 
298
    /* if program is not null */
 
299
  if (usesGraph(xprog)) {
 
300
    ing = newIngraph (0, options.inFiles, readG);
 
301
        while (state->curgraph = nextGraph(ing)) {
 
302
        /* begin graph */
 
303
      if (xprog->begg_stmt)
 
304
        exeval (xprog->prog, xprog->begg_stmt, state);
 
305
 
 
306
        /* walk graph */
 
307
      if (walksGraph(xprog))
 
308
        traverse (state, xprog);
 
309
 
 
310
        /* end graph */
 
311
      if (xprog->endg_stmt)
 
312
        exeval (xprog->prog, xprog->endg_stmt, state);
 
313
 
 
314
        /* if $O == $G and $T is empty, delete $T */
 
315
      if ((state->outgraph == state->curgraph) && 
 
316
          (state->target) && !agnnodes(state->target))
 
317
        agdelete (state->curgraph, state->target);
 
318
 
 
319
        /* output graph, if necessary */
 
320
      if (state->outgraph && agnnodes(state->outgraph))
 
321
        agwrite (state->outgraph, options.outFile);
 
322
 
 
323
      agclose (state->curgraph);
 
324
      state->target = 0;
 
325
      state->outgraph = 0;
 
326
        }
 
327
  }
 
328
 
 
329
    /* do end */
 
330
  state->curgraph = 0;
 
331
  state->curobj = 0;
 
332
  if (xprog->end_stmt)
 
333
    exeval (xprog->prog, xprog->end_stmt, state);
 
334
 
 
335
  exit(0);
 
336
}
 
337