1
2 /* This file contains code for building and printing a directed cyclic
3 * graph as part of the cflow program. */
4
5 /* Author: M.M. Taylor, DCIEM, Toronto, Canada.
6 * 22/Jan/81, Alexis Kwan (HCR at DCIEM).
7 * 12-Jun-84, Kevin Szabo
8 * 8/8/84, Tony Hansen, AT&T-IS, pegasus!hansen.
9 *
10 * This file is contributed to the public domain by Andrew Moore of
11 * Talke Studio */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <ctype.h>
16 #include <string.h>
17 #include <unistd.h>
18
19 #include "prcg.prototypes.h"
20 #ifndef PATH_MAX
21 #define PATH_MAX 1024 /* max pathname length */
22 #endif
23 #ifndef NAME_MAX
24 #define NAME_MAX 32
25 #endif
26
27 #define BUF_MAX (NAME_MAX * 2 + PATH_MAX + 20) /* max line buffer length */
28 #define DEPTH_MAX 200 /* max path length */
29 #define TABSIZE 8 /* tab size */
30 #define MARGIN 20 /* right margin of paper */
31 #define PAPERWIDTH (14*TABSIZE + MARGIN) /* tabbing limits */
32
33 #ifndef __P
34 #ifndef __STDC__
35 #define __P(proto) ()
36 #else
37 #define __P(proto) proto
38 #endif
39 #endif
40
41 /* name list node */
42 struct name_node {
43 struct name_node *next; /* next name list node */
44 struct imm_node *imm_list; /* node's immediate list */
45 long name_visited; /* set if node previously visited */
46 int is_arc_head; /* set if node is an arc head */
47 char *imm_name; /* name of first imm_list node */
48 char *imm_ref; /* reference to first imm_list node */
49 };
50
51 /* immediate list node */
52 struct imm_node {
53 struct imm_node *next; /* next immediate list node */
54 struct name_node *name_node_p; /* node's name node pointer */
55 };
56
57
58 /* The name list (nlist) contains names (e.g., function/variable) in
59 * lexicographical order. Each name node has its own list (imm_list) of
60 * immediates (e.g., callers/callees). The immediate nodes do not
61 * themselves have names; instead, each node has a pointer to its name
62 * (node) in the name list. The nodes and pointers form the vertices and
63 * edges, respectively, of a directed cyclic graph (DCG).
64 *
65 * The prcg program builds a DCG by inserting names pairs from the input
66 * as arcs into the graph. Printing the DCG is done by a preorder
67 * traversal from a root name node. Paths are defined by the immediate
68 * list of the root name node, and, recursively, by the immediate lists
69 * of its immediates. */
70 /* where is this initialized? */
71
72 static struct name_node *nlist;
73 static char *dashes; /* separators for deep nestings */
74
75 /* The following options are available :
76 *
77 * -a print a separate graph for each name (default: no)
78 * -d nn print graphs to at most depth `nn' (default: 200)
79 * -r root print graph only for `root' (default: each root name)
80 * -x print each sub-graph in full (default: no)
81 * -w nn print graph to fit in `nn' columns (default: 132 columns) */
82
83 /* option flags */
84 static int graph_all = 0; /* print a graph for each name */
85 static int maxdepth = DEPTH_MAX; /* print to at most depth `maxdepth' */
86 static int expand_all = 0; /* print each sub-graph in full */
87 static int ntabs = ((PAPERWIDTH - MARGIN) / TABSIZE); /* how wide to go */
88 static int select_roots = 0; /* print graph for selected names */
89
90 static char *arglist = "ad:r:ixw:"; /* valid options */
91
92 static char *progname; /* argv[0] */
93
94 extern char *optarg;
95 extern int optind;
96
usage(void)97 static void usage(void)
98 {
99
100 fprintf(stderr, "Usage: %s [-ax ] [-d depth] [-r root]\n", progname);
101 exit(1);
102 }
103
104 int
main(int argc,char ** argv)105 main(int argc, char **argv)
106 {
107
108 int c, i;
109 int width = PAPERWIDTH;
110
111 progname = argv[0];
112
113 while ((c = getopt(argc, argv, arglist)) != EOF)
114 switch (c) {
115 case 'a':
116 graph_all = 1;
117 break;
118 case 'd':
119 if ((maxdepth = atoi(optarg)) > DEPTH_MAX)
120 maxdepth = DEPTH_MAX;
121 break;
122 case 'i':
123 expand_all = 1;
124 graph_all = 1;
125 maxdepth = 2;
126 break;
127 case 'r':
128 select_roots = 1;
129 break;
130 case 'w':
131 if ((width = atoi(optarg)) <= 0)
132 width = PAPERWIDTH;
133 break;
134 case 'x':
135 expand_all = 1;
136 break;
137 case '?':
138 default:
139 usage();
140 }
141 ntabs = (width - MARGIN) / TABSIZE;
142
143 build_dcg();
144 print_dcg(argc, argv);
145 exit(0);
146 }
147
148 /* Name pairs in the input are expected in blocks of the form:
149 *
150 * name1a --> name2aa
151 * name1a --> name2ab
152 * name1a --> name2ac
153 * .
154 * .
155 * .
156 * name1b --> name2ba
157 * name1b --> name2bb
158 * name1b --> name2bc
159 * .
160 * .
161 * .
162 *
163 * For a distinct name1, only the first block of name pairs is valid. A
164 * graph can be inverted by reversing the relation between name pairs,
165 * i.e., by putting name2 first:
166 *
167 * name2 --> name1
168 *
169 * Unless a block contains only a single name pair, then an initial
170 * name1-name1 pair is effectively ignored. A name1-name1 pair after the
171 * first represents a cycle - i.e., a node which points to itself. A
172 * block consisting of a single name1-name1 pair represents a non-cyclic,
173 * possibly disconnected, node. */
174
175 static struct imm_node *imm_tail; /* immediate list tail */
176
177 /* Get name pairs from the input, and insert them as arcs to the DCG: an
178 * arc tail is the head of a linearly linked list (the immediate list) of
179 * arc heads to which it is connected (logically). */
build_dcg(void)180 static void build_dcg(void)
181 {
182 char arc_tail[BUF_MAX]; /* line buffer and arc tail name */
183 char *arc_head; /* arc head name */
184 char *arc_ref; /* arc reference */
185 register int connected;
186
187 while ((connected = get_arc(arc_tail, &arc_head, &arc_ref)) != -1)
188 if (!connected)
189 imm_tail = create_arc_node(arc_tail, arc_ref);
190 else if (connected && imm_tail)
191 imm_tail = link_arc_node(arc_head, imm_tail);
192 else
193 fprintf(stderr, "%s: cannot redefine: %s\n", progname, arc_tail);
194 }
195
196
197 char tail_name[NAME_MAX] = ""; /* previous arc tail name */
198
199 /* Read from stdin a name pair and a reference in the form
200 * `name1<tab>name2<tab>reference<newline>.' Return 1 if the tail of arc
201 * name1 --> name2 (i.e., name1) is the tail the previous arc,
202 * otherwise 0. */
203 int
get_arc(char * buf,char ** ip,char ** rp)204 get_arc(char *buf, char **ip, char **rp)
205 {
206
207 /* line read and data format okay */
208 if (fgets(buf, BUF_MAX, stdin) != NULL
209 && (*ip = strchr(buf, '\t')) != NULL
210 && (*rp = strchr(*ip + 1, '\t')) != NULL) {
211 /* null-terminate name1 and name2 substrings */
212 *(*rp)++ = *(*ip)++ = '\0';
213
214 /* arc tail not previous tail */
215 if (strcmp(buf, tail_name)) {
216 /* update arc tail name */
217 strcpy(tail_name, buf);
218
219 /* name pair is an arc (as opposed to a node) */
220 if (strcmp(buf, *ip)) {
221 /* create an arc tail node */
222 imm_tail = create_arc_node(buf, *rp);
223
224 /* arc */
225 return 1;
226 }
227 /* node */
228 return 0;
229 }
230 /* arc */
231 return 1;
232 }
233 /* eof */
234 return -1;
235 }
236
237
238 /* Given a name (s), if it is not already on the name list, create a node
239 * for it there. Otherwise, retrieve the name list node. Create an arc
240 * tail (i.e., imm_list) node and link it to the new/retrieved name
241 * node (via the name node's imm_list pointer). Return a pointer to the
242 * arc tail node. */
243 struct imm_node *
create_arc_node(char * s,char * t)244 create_arc_node(char *s, char *t)
245 {
246 struct name_node *np;
247 struct imm_node *ip;
248
249 /* name already on name list */
250 if ((np = nlist_contains(s))) {
251 /* arc tail node installed && arc reference realloc'd */
252 if ((ip = node_to_arc(np, (struct imm_node *) 0)) != 0
253 && (np->imm_ref = realloc(np->imm_ref, strlen(t) + 1)) != NULL) {
254 /* update arc reference */
255
256 strcpy(np->imm_ref, t);
257 return ip;
258 }
259 return (struct imm_node *) 0;
260 }
261 /* add name to name list and install arc tail node */
262 return node_to_arc(name_to_nlist(s, t), (struct imm_node *) 0);
263 }
264
265
266 char *nil = " "; /* should be "", but 386BSD 0.1 bus errors XXX */
267
268 /* Given a name (s), if it is not already on the name list, create a node
269 * for it there. Otherwise, retrieve the name list node. Create an arc
270 * head (i.e., imm_list) node and link it to the tail of the current
271 * immediate list. Return a pointer to the arc head node. */
272 struct imm_node *
link_arc_node(char * s,struct imm_node * tail)273 link_arc_node(char *s, struct imm_node *tail)
274 {
275 register struct name_node *p;
276 register struct imm_node *ip = 0;
277
278 /* (name already on name list or added name) and installed new arc
279 * and name != arc tail's name */
280 if (((p = nlist_contains(s)) != 0 || (p = name_to_nlist(s, nil)) != 0)
281 && (ip = node_to_arc(p, tail)) != 0 && strcmp(s, tail_name))
282 p->is_arc_head = 1; /* arc head node */
283 return ip;
284 }
285
286 /* Allocate memory for a name list node. Insert the node in the name
287 * list in lexicographical order by name. Return a pointer to the node. */
288 struct name_node *
name_to_nlist(char * s,char * t)289 name_to_nlist(char *s, char *t)
290 {
291 register struct name_node *np, *p;
292
293 /* name structure, name and arc reference alloc'd */
294 if ((np = (struct name_node *) malloc(sizeof (struct name_node))) != 0
295 && (np->imm_name = (char *) malloc(strlen(s) + 1)) != NULL
296 && (np->imm_ref = (char *) malloc(strlen(t) + 1)) != NULL) {
297 /* initialize name structure */
298 strcpy(np->imm_name, s);
299 strcpy(np->imm_ref, t);
300 np->imm_list = (struct imm_node *) 0;
301 np->is_arc_head = 0;
302 np->name_visited = 0;
303
304 /* no name list, or name less than head of name list */
305 if (nlist == 0 || strcmp(nlist->imm_name, s) > 0) {
306 /* add node to head of name list */
307 np->next = nlist;
308 nlist = np;
309 } else {
310 /* insert node in lexicographical order in name list */
311 for (p = nlist; p->next; p = p->next)
312 if (strcmp(p->next->imm_name, s) > 0)
313 break;
314 np->next = p->next;
315 p->next = np;
316 }
317 return np;
318 }
319 return (struct name_node *) 0;
320 }
321
322
323 /* Create an immediate node (imm_p) with a pointer (name_node_p) to its
324 * name list node (np). If the given immediate list pointer (ip) is NULL,
325 * the new immediate node is an arc tail, and it is pointed to by its
326 * name list node. Otherwise, the new immediate node is an arc head and
327 * is linked after the given immediate list pointer. Return a pointer to
328 * the new immediate node. */
329 struct imm_node *
node_to_arc(struct name_node * np,struct imm_node * ip)330 node_to_arc(struct name_node *np, struct imm_node *ip)
331 {
332 register struct imm_node *imm_p;
333
334 /* null name or (dummy && an immediate exists) or null immediate */
335 if (np == 0 || (!ip && np->imm_list) || (imm_p = get_imm_node()) == 0)
336 return (struct imm_node *) 0;
337 imm_p->name_node_p = np;
338 return ip ? (ip->next = imm_p) : (np->imm_list = imm_p);
339 }
340
341 /* Return pointer to alloc'd and initialized immediate node. */
342 static struct imm_node *
get_imm_node(void)343 get_imm_node(void)
344 {
345 register struct imm_node *rp;
346
347 /* immediate node alloc'd */
348 if ((rp = (struct imm_node *) malloc(sizeof (struct imm_node))) != 0) {
349 /* initialize immediate node */
350 rp->next = (struct imm_node *) 0;
351 return rp;
352 }
353 return (struct imm_node *) 0;
354 }
355
356 /* Preorder traverse the DCG, printing the names of nodes as they
357 * are visited. */
358 void
print_dcg(int argc,char ** argv)359 print_dcg(int argc, char **argv)
360 {
361 register int c;
362 register struct name_node *root_p;
363
364 /* root node(s) specified */
365 if (select_roots)
366 /* restart argument list; print only specified names */
367 for (optind = 1; (c = getopt(argc, argv, arglist)) != EOF;) {
368 if (c == 'r')
369 if ((root_p = nlist_contains(optarg)))
370 print_name(root_p, 1);
371 else
372 (void) fprintf(stderr, "%s: not found: %s\n", progname, optarg);
373 } else
374 /* print_name everything */
375 for (root_p = nlist; root_p; root_p = root_p->next)
376 if (graph_all || !root_p->is_arc_head)
377 print_name(root_p, 1);
378 }
379
380
381 /* Print one tab for each level of recursion, then the name of an unvisited
382 * immediate. Go to the immediate's immediate list and, recursively,
383 * print the name of an unvisited immediate. When the current path is
384 * exhausted, back track to an immediate list with unvisited nodes and
385 * continue with the next unvisited immediate.
386 *
387 * While travering the DCG, maintain an active list of nodes in the current
388 * path. If an active node is revisited, terminate the path and print a
389 * `cycle' mark. */
390 void
print_name(struct name_node * node,int tabc)391 print_name(struct name_node *node, int tabc)
392 {
393 static long line = 0; /* line number */
394
395 register int i, tabd, tabstar, tflag;
396 register struct imm_node *imm_p;
397
398 if (tabc > maxdepth)
399 return;
400 printf("%ld", ++line);
401 if (!makeactive(node))
402 printf(" * nesting is too deep\n");
403 else {
404 tabstar = 0;
405 tabd = tabc;
406 for (; tabd > ntabs; tabstar++)
407 tabd = tabd - ntabs;
408 if (tabstar > 0) {
409 printf(" ");
410 for (i = 0; i < tabstar; i++)
411 printf("<");
412 }
413 if (tabd == 0)
414 printf(" ");
415 else
416 for (i = 0; i < tabd; i++)
417 printf("\t");
418
419 /* cycle found */
420 if (active(node))
421 printf("... %s ... {%ld}\n", node->imm_name, node->name_visited);
422 else {
423 if (node->imm_list) {
424 printf("%s", node->imm_name);
425 imm_p = node->imm_list->next;
426 if (expand_all || !node->name_visited) {
427 printf(" %s", node->imm_ref);
428 ++tabc;
429 if (!node->name_visited)
430 node->name_visited = line;
431 /* if (tabc > ntabs && tabc%ntabs==1 && imm_p)
432 * {
433 * printf("%s\n", dashes);
434 * tflag = 1;
435 * }
436 * else
437 * tflag = 0;
438 */
439 for (; imm_p; imm_p = imm_p->next)
440 print_name(imm_p->name_node_p, tabc);
441 /* if (tflag)
442 * {
443 * printf("%s\n", dashes);
444 * tflag = 0;
445 * }
446 */
447 } else
448 printf(" ... {%ld}\n", node->name_visited);
449 }
450 /* library or external call */
451 else
452 printf("%s {}\n", node->imm_name);
453 }
454 backup();
455 }
456 return;
457 }
458
459 struct name_node *active_node[DEPTH_MAX]; /* current path */
460 int active_p = 0; /* current path size */
461
462 /* makeactive simply puts a pointer to the nameblock into a stack with
463 * maximum depth DEPTH_MAX. the error return only happens for stack
464 * overflow. */
465 int
makeactive(struct name_node * node)466 makeactive(struct name_node *node)
467 {
468 if (active_p < DEPTH_MAX) {
469 active_node[active_p] = node;
470 active_p++;
471 return 1;
472 }
473 return 0;
474 }
475
476 /* backup removes an item from the active stack */
477 void
backup(void)478 backup(void)
479 {
480 if (active_p)
481 active_node[active_p--] = 0;
482 }
483
484 /* active checks whether the pointer which is its argument has already
485 * occurred on the active list, and returns 1 if so. */
486 int
active(struct name_node * node)487 active(struct name_node *node)
488 {
489 register int i;
490
491 for (i = 0; i < active_p - 1; i++)
492 if (node == active_node[i])
493 return 1;
494 return 0;
495 }
496
497 /* accepts a pointer to a name and sees if the name is on the name list.
498 * If so, it returns a pointer to the nameblock. Otherwise it returns
499 * zero. If the name from argv is > NAME_MAX-1, then it is truncated. */
500 struct name_node *
nlist_contains(char * s)501 nlist_contains(char *s)
502 {
503 struct name_node *np = nlist;
504
505 if (strlen(s) > NAME_MAX - 1)
506 s[NAME_MAX - 1] = '\0';
507
508 for (np = nlist; np; np = np->next)
509 if (strcmp(s, np->imm_name) == 0)
510 return np;
511 return 0;
512 }
513