Graphviz 13.1.2~dev.20250807.2324
Loading...
Searching...
No Matches
gvpr.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11/*
12 * gpr: graph pattern recognizer
13 *
14 * Written by Emden Gansner
15 */
16
17#include "builddate.h"
18#include <assert.h>
19#include <ast/error.h>
20#include <cgraph/cgraph.h>
21#include <cgraph/ingraphs.h>
22#include <common/globals.h>
23#include <getopt.h>
24#include <gvpr/actions.h>
25#include <gvpr/compile.h>
26#include <gvpr/gprstate.h>
27#include <gvpr/gvpr.h>
28#include <setjmp.h>
29#include <stdbool.h>
30#include <stddef.h>
31#include <stdio.h>
32#include <string.h>
33#include <unistd.h>
34#include <util/agxbuf.h>
35#include <util/alloc.h>
36#include <util/exit.h>
37#include <util/gv_ctype.h>
38#include <util/gv_find_me.h>
39#include <util/list.h>
40#include <util/path.h>
41#include <util/unreachable.h>
42
43static char *Info[] = {
44 "gvpr", /* Program */
45 PACKAGE_VERSION, /* Version */
46 BUILDDATE /* Build Date */
47};
48
49static const char *usage =
50 " [-o <ofile>] [-a <args>] ([-f <prog>] | 'prog') [files]\n\
51 -c - use source graph for output\n\
52 -f <pfile> - find program in file <pfile>\n\
53 -i - create node induced subgraph\n\
54 -a <args> - string arguments available as ARGV[0..]\n\
55 -o <ofile> - write output to <ofile>; stdout by default\n\
56 -n - no read-ahead of input graphs\n\
57 -q - turn off warning messages\n\
58 -v - enable verbose messages\n\
59 -V - print version info\n\
60 -? - print usage info\n\
61If no files are specified, stdin is used\n";
62
63typedef struct {
64 char *cmdName; /* command name */
65 FILE *outFile; /* output stream; stdout default */
66 char *program; /* program source */
67 int useFile; /* true if program comes from a file */
70 char **inFiles;
71 int argc;
72 char **argv;
73 int state; /* > 0 : continue; <= 0 finish */
75} options;
76
77static FILE *openOut(char *name) {
78 FILE *outs = fopen(name, "w");
79 if (outs == 0) {
80 error(ERROR_ERROR, "could not open %s for writing", name);
81 }
82 return outs;
83}
84
85/* gettok:
86 * Tokenize a string. Tokens consist of either a non-empty string
87 * of non-space characters, or all characters between a pair of
88 * single or double quotes. As usual, we map
89 * \c -> c
90 * for all c
91 * Return next argument token, returning NULL if none.
92 * sp is updated to point to next character to be processed.
93 * NB. There must be white space between tokens. Otherwise, they
94 * are concatenated.
95 */
96static char *gettok(char **sp) {
97 char *s = *sp;
98 char *ws = s;
99 char *rs = s;
100 char c;
101 char q = '\0'; /* if non-0, in quote mode with quote char q */
102
103 while (gv_isspace(*rs))
104 rs++;
105 if ((c = *rs) == '\0')
106 return NULL;
107 while ((c = *rs)) {
108 if (q && q == c) { /* end quote */
109 q = '\0';
110 } else if (!q && (c == '"' || c == '\'')) {
111 q = c;
112 } else if (c == '\\') {
113 rs++;
114 c = *rs;
115 if (c)
116 *ws++ = c;
117 else {
119 "backslash in argument followed by no character - ignored");
120 rs--;
121 }
122 } else if (q || !gv_isspace(c))
123 *ws++ = c;
124 else
125 break;
126 rs++;
127 }
128 if (*rs)
129 rs++;
130 else if (q)
131 error(ERROR_WARNING, "no closing quote for argument %s", s);
132 *sp = rs;
133 *ws = '\0';
134 return s;
135}
136
137#define NUM_ARGS 100
138
139/* parseArgs:
140 * Split s into whitespace separated tokens, allowing quotes.
141 * Append tokens to argument list and return new number of arguments.
142 * argc is the current number of arguments, with the arguments
143 * stored in *argv.
144 */
145static int parseArgs(char *s, int argc, char ***argv) {
146 int i, cnt = 0;
147 char *args[NUM_ARGS];
148 char *t;
149 char **av;
150
151 assert(argc >= 0);
152
153 while ((t = gettok(&s))) {
154 if (cnt == NUM_ARGS) {
156 "at most %d arguments allowed per -a flag - ignoring rest",
157 NUM_ARGS);
158 break;
159 }
160 args[cnt++] = t;
161 }
162
163 if (cnt) {
164 int oldcnt = argc;
165 argc = oldcnt + cnt;
166 av = gv_recalloc(*argv, (size_t)oldcnt, (size_t)argc, sizeof(char *));
167 for (i = 0; i < cnt; i++)
168 av[oldcnt + i] = gv_strdup(args[i]);
169 *argv = av;
170 }
171 return argc;
172}
173
174#if defined(_WIN32) && !defined(__MINGW32__)
175#define LISTSEP ';'
176#else
177#define LISTSEP ':'
178#endif
179
180static char *concat(char *pfx, char *sfx) {
181 agxbuf sp = {0};
182 agxbprint(&sp, "%s%s", pfx, sfx);
183 return agxbdisown(&sp);
184}
185
193static char *dflt_gvprpath(void) {
194
195 // find our containing executable
196 char *const exe = gv_find_me();
197 if (exe == NULL) {
198 return NULL;
199 }
200
201 // assume it is of the form …/bin/foo[.exe] and construct
202 // .:…/share/graphviz/gvpr
203
204 char *slash = strrchr(exe, PATH_SEPARATOR);
205 if (slash == NULL) {
206 free(exe);
207 return NULL;
208 }
209
210 *slash = '\0';
211 slash = strrchr(exe, PATH_SEPARATOR);
212 if (slash == NULL) {
213 free(exe);
214 return NULL;
215 }
216
217 *slash = '\0';
218 const size_t share_len =
219 strlen(".:") + strlen(exe) + strlen("/share/graphviz/gvpr") + 1;
220 char *const share = malloc(share_len);
221 if (share == NULL) {
222 free(exe);
223 return NULL;
224 }
225 snprintf(share, share_len, ".%c%s%cshare%cgraphviz%cgvpr", LISTSEP, exe,
227 free(exe);
228
229 return share;
230}
231
232/* resolve:
233 * Translate -f arg parameter into a pathname.
234 * If arg contains '/', return arg.
235 * Else search directories in GVPRPATH for arg.
236 * Return NULL on error.
237 */
238static char *resolve(char *arg, int verbose) {
239 char *path;
240 char *s;
241 char *cp;
242 char c;
243 char *fname = 0;
244 char *pathp = NULL;
245 size_t sz;
246
247 if (strchr(arg, PATH_SEPARATOR))
248 return gv_strdup(arg);
249
250 char *const dflt = dflt_gvprpath();
251 if (dflt == NULL) {
252 error(ERROR_ERROR, "Could not determine DFLT_GVPRPATH");
253 }
254
255 path = getenv("GVPRPATH");
256 if (!path)
257 path = getenv("GPRPATH"); // deprecated
258 if (dflt == NULL) {
259 // do not use `dflt` at all
260 } else if (path && (c = *path)) {
261 if (c == LISTSEP) {
262 pathp = path = concat(dflt, path);
263 } else if (path[strlen(path) - 1] == LISTSEP) {
264 pathp = path = concat(path, dflt);
265 }
266 } else
267 path = dflt;
268 if (verbose)
269 fprintf(stderr, "PATH: %s\n", path);
270 agxbuf fp = {0};
271
272 while (*path && !fname) {
273 if (*path == LISTSEP) { /* skip colons */
274 path++;
275 continue;
276 }
277 cp = strchr(path, LISTSEP);
278 if (cp) {
279 sz = (size_t)(cp - path);
280 agxbput_n(&fp, path, sz);
281 path = cp + 1; /* skip past current colon */
282 } else {
283 sz = agxbput(&fp, path);
284 path += sz;
285 }
286 agxbprint(&fp, "%c%s", PATH_SEPARATOR, arg);
287 s = agxbuse(&fp);
288
289 if (access(s, R_OK) == 0) {
290 fname = gv_strdup(s);
291 }
292 }
293
294 free(dflt);
295
296 if (!fname)
297 error(ERROR_ERROR, "Could not find file \"%s\" in GVPRPATH", arg);
298
299 agxbfree(&fp);
300 free(pathp);
301 if (verbose)
302 fprintf(stderr, "file %s resolved to %s\n", arg,
303 fname == NULL ? "<null>" : fname);
304 return fname;
305}
306
307static char *getOptarg(int c, char **argp, int *argip, int argc, char **argv) {
308 char *rv;
309 char *arg = *argp;
310 int argi = *argip;
311
312 if (*arg) {
313 rv = arg;
314 while (*arg)
315 arg++;
316 *argp = arg;
317 } else if (argi < argc) {
318 rv = argv[argi++];
319 *argip = argi;
320 } else {
321 rv = NULL;
322 error(ERROR_WARNING, "missing argument for option -%c", c);
323 }
324 return rv;
325}
326
327/* doFlags:
328 * Process a command-line argument starting with a '-'.
329 * argi is the index of the next available item in argv[].
330 * argc has its usual meaning.
331 *
332 * return > 0 given next argi value
333 * = 0 for exit with 0
334 * < 0 for error
335 */
336static int doFlags(char *arg, int argi, int argc, char **argv, options *opts) {
337 int c;
338
339 while ((c = *arg++)) {
340 switch (c) {
341 case 'c':
342 opts->compflags.srcout = true;
343 break;
344 case 'C':
345 opts->compflags.srcout = true;
346 opts->compflags.clone = true;
347 break;
348 case 'f':
349 if ((optarg = getOptarg(c, &arg, &argi, argc, argv)) &&
350 (opts->program = resolve(optarg, opts->verbose))) {
351 opts->useFile = 1;
352 } else
353 return -1;
354 break;
355 case 'i':
356 opts->compflags.induce = true;
357 break;
358 case 'n':
359 opts->readAhead = 0;
360 break;
361 case 'a':
362 if ((optarg = getOptarg(c, &arg, &argi, argc, argv))) {
363 opts->argc = parseArgs(optarg, opts->argc, &(opts->argv));
364 } else
365 return -1;
366 break;
367 case 'o':
368 if (!(optarg = getOptarg(c, &arg, &argi, argc, argv)) ||
369 !(opts->outFile = openOut(optarg)))
370 return -1;
371 break;
372 case 'q':
373 setTraceLevel(ERROR_ERROR); /* Don't emit warning messages */
374 break;
375 case 'v':
376 opts->verbose = 1;
377 break;
378 case 'V':
379 fprintf(stderr, "%s version %s (%s)\n", Info[0], Info[1], Info[2]);
380 return 0;
381 case '?':
382 if (optopt == '\0' || optopt == '?')
383 fprintf(stderr, "Usage: gvpr%s", usage);
384 else {
386 }
387 return 0;
388 default:
389 error(ERROR_WARNING, "option -%c unrecognized", c);
390 break;
391 }
392 }
393 return argi;
394}
395
396static void freeOpts(options opts) {
397 if (opts.outFile != NULL && opts.outFile != stdout)
398 fclose(opts.outFile);
399 free(opts.inFiles);
400 if (opts.useFile)
401 free(opts.program);
402 for (int i = 0; i < opts.argc; i++)
403 free(opts.argv[i]);
404 free(opts.argv);
405}
406
407DEFINE_LIST(strs, char *)
408
409/* scanArgs:
410 * Parse command line options.
411 */
412static options scanArgs(int argc, char **argv) {
413 char *arg;
414 options opts = {0};
415
416 opts.cmdName = argv[0];
417 opts.state = 1;
418 opts.readAhead = 1;
419 setErrorId(opts.cmdName);
420 opts.verbose = 0;
421
422 strs_t input_filenames = {0};
423
424 /* loop over arguments */
425 for (int i = 1; i < argc;) {
426 arg = argv[i++];
427 if (*arg == '-') {
428 i = doFlags(arg + 1, i, argc, argv, &opts);
429 if (i <= 0) {
430 opts.state = i;
431 goto opts_done;
432 }
433 } else if (arg)
434 strs_append(&input_filenames, arg);
435 }
436
437 /* Handle additional semantics */
438 if (opts.useFile == 0) {
439 if (strs_is_empty(&input_filenames)) {
440 error(ERROR_ERROR, "No program supplied via argument or -f option");
441 opts.state = -1;
442 } else {
443 opts.program = strs_pop_front(&input_filenames);
444 }
445 }
446 if (strs_is_empty(&input_filenames)) {
447 opts.inFiles = 0;
448 strs_free(&input_filenames);
449 } else {
450 strs_append(&input_filenames, NULL);
451 opts.inFiles = strs_detach(&input_filenames);
452 }
453
454 if (!opts.outFile)
455 opts.outFile = stdout;
456
457opts_done:
458 if (opts.state <= 0) {
459 if (opts.state < 0)
461 strs_free(&input_filenames);
462 }
463
464 return opts;
465}
466
467static Agobj_t *evalEdge(Gpr_t *state, Expr_t *prog, comp_block *xprog,
468 Agedge_t *e) {
469 case_stmt *cs;
470 bool okay;
471
472 state->curobj = (Agobj_t *)e;
473 for (size_t i = 0; i < xprog->n_estmts; i++) {
474 cs = xprog->edge_stmts + i;
475 if (cs->guard)
476 okay = exeval(prog, cs->guard, state).integer != 0;
477 else
478 okay = true;
479 if (okay) {
480 if (cs->action)
481 exeval(prog, cs->action, state);
482 else
483 agsubedge(state->target, e, 1);
484 }
485 }
486 return state->curobj;
487}
488
489static Agobj_t *evalNode(Gpr_t *state, Expr_t *prog, comp_block *xprog,
490 Agnode_t *n) {
491 case_stmt *cs;
492 bool okay;
493
494 state->curobj = (Agobj_t *)n;
495 for (size_t i = 0; i < xprog->n_nstmts; i++) {
496 cs = xprog->node_stmts + i;
497 if (cs->guard)
498 okay = exeval(prog, cs->guard, state).integer != 0;
499 else
500 okay = true;
501 if (okay) {
502 if (cs->action)
503 exeval(prog, cs->action, state);
504 else
505 agsubnode(state->target, n, 1);
506 }
507 }
508 return (state->curobj);
509}
510
515
516static Agnode_t *nextNode(Gpr_t *state, nodestream *nodes) {
517 Agnode_t *np;
518
519 if (state->tvroot != nodes->oldroot) {
520 np = nodes->oldroot = state->tvroot;
521 } else if (state->flags & GV_NEXT_SET) {
522 np = nodes->oldroot = state->tvroot = state->tvnext;
523 state->flags &= ~GV_NEXT_SET;
524 } else if (nodes->prev) {
525 np = nodes->prev = agnxtnode(state->curgraph, nodes->prev);
526 } else {
527 np = nodes->prev = agfstnode(state->curgraph);
528 }
529 return np;
530}
531
532#define MARKED(x) (((x)->iu.integer) & 1)
533#define MARK(x) (((x)->iu.integer) = 1)
534#define ONSTACK(x) (((x)->iu.integer) & 2)
535#define PUSH(x, e) (((x)->iu.integer) |= 2, (x)->ine = (e))
536#define POP(x) (((x)->iu.integer) &= (~2))
537
538typedef Agedge_t *(*fstedgefn_t)(Agraph_t *, Agnode_t *);
539typedef Agedge_t *(*nxttedgefn_t)(Agraph_t *, Agedge_t *, Agnode_t *);
540
541#define PRE_VISIT 1
542#define POST_VISIT 2
543
544typedef struct {
547 unsigned char undirected;
548 unsigned char visit;
549} trav_fns;
550
552static Agedge_t *agnxtout_(Agraph_t *g, Agedge_t *e, Agnode_t *ignored) {
553 (void)ignored;
554 return agnxtout(g, e);
555}
556
558static Agedge_t *agnxtin_(Agraph_t *g, Agedge_t *e, Agnode_t *ignored) {
559 (void)ignored;
560 return agnxtin(g, e);
561}
562
565static trav_fns REVfns = {agfstin, agnxtin_, 0, 0};
566
567DEFINE_LIST(node_queue, Agnode_t *)
568
569static void travBFS(Gpr_t *state, Expr_t *prog, comp_block *xprog) {
570 nodestream nodes;
571 node_queue_t q = {0};
572 ndata *nd;
573 Agnode_t *n;
574 Agedge_t *cure;
575 Agedge_t *nxte;
576 Agraph_t *g = state->curgraph;
577
578 nodes.oldroot = 0;
579 nodes.prev = 0;
580 while ((n = nextNode(state, &nodes))) {
581 nd = nData(n);
582 if (MARKED(nd))
583 continue;
584 PUSH(nd, 0);
585 node_queue_push_back(&q, n);
586 while (!node_queue_is_empty(&q)) {
587 n = node_queue_pop_front(&q);
588 nd = nData(n);
589 MARK(nd);
590 POP(nd);
591 state->tvedge = nd->ine;
592 if (!evalNode(state, prog, xprog, n))
593 continue;
594 for (cure = agfstedge(g, n); cure; cure = nxte) {
595 nxte = agnxtedge(g, cure, n);
596 nd = nData(cure->node);
597 if (MARKED(nd))
598 continue;
599 if (!evalEdge(state, prog, xprog, cure))
600 continue;
601 if (!ONSTACK(nd)) {
602 node_queue_push_back(&q, cure->node);
603 PUSH(nd, cure);
604 }
605 }
606 }
607 }
608 state->tvedge = 0;
609 node_queue_free(&q);
610}
611
612DEFINE_LIST(edge_stack, Agedge_t *)
613
614static void travDFS(Gpr_t *state, Expr_t *prog, comp_block *xprog,
615 trav_fns *fns) {
616 Agnode_t *n;
617 edge_stack_t stk = {0};
618 Agnode_t *curn;
619 Agedge_t *cure;
620 Agedge_t *entry;
621 int more;
622 ndata *nd;
623 nodestream nodes;
625
626 nodes.oldroot = 0;
627 nodes.prev = 0;
628 while ((n = nextNode(state, &nodes))) {
629 nd = nData(n);
630 if (MARKED(nd))
631 continue;
632 seed.out.node = n;
633 seed.in.node = 0;
634 curn = n;
635 entry = &seed.out;
636 state->tvedge = cure = 0;
637 MARK(nd);
638 PUSH(nd, 0);
639 if (fns->visit & PRE_VISIT)
640 evalNode(state, prog, xprog, n);
641 more = 1;
642 while (more) {
643 if (cure)
644 cure = fns->nxtedge(state->curgraph, cure, curn);
645 else
646 cure = fns->fstedge(state->curgraph, curn);
647 if (cure) {
648 if (entry == agopp(cure)) /* skip edge used to get here */
649 continue;
650 nd = nData(cure->node);
651 if (MARKED(nd)) {
652 /* For undirected DFS, visit an edge only if its head
653 * is on the stack, to avoid visiting it twice.
654 * This is no problem in directed DFS.
655 */
656 if (fns->undirected) {
657 if (ONSTACK(nd))
658 evalEdge(state, prog, xprog, cure);
659 } else
660 evalEdge(state, prog, xprog, cure);
661 } else {
662 evalEdge(state, prog, xprog, cure);
663 edge_stack_push_back(&stk, entry);
664 state->tvedge = entry = cure;
665 curn = cure->node;
666 cure = 0;
667 if (fns->visit & PRE_VISIT)
668 evalNode(state, prog, xprog, curn);
669 MARK(nd);
670 PUSH(nd, entry);
671 }
672 } else {
673 if (fns->visit & POST_VISIT)
674 evalNode(state, prog, xprog, curn);
675 nd = nData(curn);
676 POP(nd);
677 cure = entry;
678 entry = edge_stack_is_empty(&stk) ? NULL : edge_stack_pop_back(&stk);
679 if (entry == &seed.out)
680 state->tvedge = 0;
681 else
682 state->tvedge = entry;
683 if (entry)
684 curn = entry->node;
685 else
686 more = 0;
687 }
688 }
689 }
690 state->tvedge = 0;
691 edge_stack_free(&stk);
692}
693
694static void travNodes(Gpr_t *state, Expr_t *prog, comp_block *xprog) {
695 Agnode_t *n;
696 Agnode_t *next;
697 Agraph_t *g = state->curgraph;
698 for (n = agfstnode(g); n; n = next) {
699 next = agnxtnode(g, n);
700 evalNode(state, prog, xprog, n);
701 }
702}
703
704static void travEdges(Gpr_t *state, Expr_t *prog, comp_block *xprog) {
705 Agnode_t *n;
706 Agnode_t *next;
707 Agedge_t *e;
708 Agedge_t *nexte;
709 Agraph_t *g = state->curgraph;
710 for (n = agfstnode(g); n; n = next) {
711 next = agnxtnode(g, n);
712 for (e = agfstout(g, n); e; e = nexte) {
713 nexte = agnxtout(g, e);
714 evalEdge(state, prog, xprog, e);
715 }
716 }
717}
718
719static void travFlat(Gpr_t *state, Expr_t *prog, comp_block *xprog) {
720 Agnode_t *n;
721 Agnode_t *next;
722 Agedge_t *e;
723 Agedge_t *nexte;
724 Agraph_t *g = state->curgraph;
725 for (n = agfstnode(g); n; n = next) {
726 next = agnxtnode(g, n);
727 if (!evalNode(state, prog, xprog, n))
728 continue;
729 if (xprog->n_estmts > 0) {
730 for (e = agfstout(g, n); e; e = nexte) {
731 nexte = agnxtout(g, e);
732 evalEdge(state, prog, xprog, e);
733 }
734 }
735 }
736}
737
738/* doCleanup:
739 * Reset node traversal data
740 */
741static void doCleanup(Agraph_t *g) {
742 Agnode_t *n;
743 ndata *nd;
744
745 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
746 nd = nData(n);
747 nd->ine = NULL;
748 nd->iu.integer = 0;
749 }
750}
751
752/* traverse:
753 * return true if traversal requires cleanup
754 */
755static bool traverse(Gpr_t *state, Expr_t *prog, comp_block *bp, bool cleanup) {
756 if (!state->target) {
757 char *target;
758 agxbuf tmp = {0};
759
760 if (state->name_used) {
761 agxbprint(&tmp, "%s%d", state->tgtname, state->name_used);
762 target = agxbuse(&tmp);
763 } else
764 target = state->tgtname;
765 state->name_used++;
766 /* make sure target subgraph does not exist */
767 while (agsubg(state->curgraph, target, 0)) {
768 state->name_used++;
769 agxbprint(&tmp, "%s%d", state->tgtname, state->name_used);
770 target = agxbuse(&tmp);
771 }
772 state->target = openSubg(state->curgraph, target);
773 agxbfree(&tmp);
774 }
775 if (!state->outgraph)
776 state->outgraph = state->target;
777
778 switch (state->tvt) {
779 case TV_flat:
780 travFlat(state, prog, bp);
781 break;
782 case TV_bfs:
783 if (cleanup)
784 doCleanup(state->curgraph);
785 travBFS(state, prog, bp);
786 cleanup = true;
787 break;
788 case TV_dfs:
789 if (cleanup)
790 doCleanup(state->curgraph);
792 travDFS(state, prog, bp, &DFSfns);
793 cleanup = true;
794 break;
795 case TV_fwd:
796 if (cleanup)
797 doCleanup(state->curgraph);
799 travDFS(state, prog, bp, &FWDfns);
800 cleanup = true;
801 break;
802 case TV_rev:
803 if (cleanup)
804 doCleanup(state->curgraph);
806 travDFS(state, prog, bp, &REVfns);
807 cleanup = true;
808 break;
809 case TV_postdfs:
810 if (cleanup)
811 doCleanup(state->curgraph);
813 travDFS(state, prog, bp, &DFSfns);
814 cleanup = true;
815 break;
816 case TV_postfwd:
817 if (cleanup)
818 doCleanup(state->curgraph);
820 travDFS(state, prog, bp, &FWDfns);
821 cleanup = true;
822 break;
823 case TV_postrev:
824 if (cleanup)
825 doCleanup(state->curgraph);
827 travDFS(state, prog, bp, &REVfns);
828 cleanup = true;
829 break;
830 case TV_prepostdfs:
831 if (cleanup)
832 doCleanup(state->curgraph);
834 travDFS(state, prog, bp, &DFSfns);
835 cleanup = true;
836 break;
837 case TV_prepostfwd:
838 if (cleanup)
839 doCleanup(state->curgraph);
841 travDFS(state, prog, bp, &FWDfns);
842 cleanup = true;
843 break;
844 case TV_prepostrev:
845 if (cleanup)
846 doCleanup(state->curgraph);
848 travDFS(state, prog, bp, &REVfns);
849 cleanup = true;
850 break;
851 case TV_ne:
852 travNodes(state, prog, bp);
853 travEdges(state, prog, bp);
854 break;
855 case TV_en:
856 travEdges(state, prog, bp);
857 travNodes(state, prog, bp);
858 break;
859 default:
860 UNREACHABLE();
861 }
862 return cleanup;
863}
864
865/* addOutputGraph:
866 * Append output graph to option struct.
867 * We know uopts and state->outgraph are non-NULL.
868 */
869static void addOutputGraph(Gpr_t *state, gvpropts *uopts) {
870 Agraph_t *g = state->outgraph;
871
872 if ((agroot(g) == state->curgraph) && !uopts->ingraphs)
873 g = (Agraph_t *)cloneO(0, (Agobj_t *)g);
874
875 uopts->outgraphs = gv_recalloc(uopts->outgraphs, uopts->n_outgraphs,
876 uopts->n_outgraphs + 1, sizeof(Agraph_t *));
877 uopts->n_outgraphs++;
878 uopts->outgraphs[uopts->n_outgraphs - 1] = g;
879}
880
881static void chkClose(Agraph_t *g) {
882 gdata *data;
883
884 data = gData(g);
885 if (data->lock.locked)
886 data->lock.zombie = true;
887 else
888 agclose(g);
889}
890
891static Agraph_t *ing_read(const char *filename, void *fp) {
892 Agraph_t *g = agconcat(NULL, filename, fp, NULL);
893 if (g) {
894 aginit(g, AGRAPH, UDATA, sizeof(gdata), false);
895 aginit(g, AGNODE, UDATA, sizeof(ndata), false);
896 aginit(g, AGEDGE, UDATA, sizeof(edata), false);
897 }
898 return g;
899}
900
909
910/* gvexitf:
911 * Only used if GV_USE_EXIT not set during exeval.
912 * This implies setjmp/longjmp set up.
913 */
914static void gvexitf(void *env, int v) {
915 gvpr_state_t *st = env;
916
917 longjmp(st->state->jbuf, v);
918}
919
920static void gverrorf(Expr_t *handle, Exdisc_t *discipline, int level,
921 const char *fmt, ...) {
922 va_list ap;
923
924 va_start(ap, fmt);
925 errorv((discipline && handle) ? *((char **)handle) : (char *)handle, level,
926 fmt, ap);
927 va_end(ap);
928
929 if (level >= ERROR_ERROR) {
930 Gpr_t *state = discipline->user;
931 if (state->flags & GV_USE_EXIT)
932 graphviz_exit(1);
933 else if (state->flags & GV_USE_JUMP)
934 longjmp(state->jbuf, 1);
935 }
936}
937
938/* gvpr_core:
939 * Return 0 on success; non-zero on error.
940 *
941 * FIX/TODO:
942 * - close non-source/non-output graphs
943 * - flag to clone target graph?
944 * - remove assignment in boolean warning if wrapped in ()
945 * - do automatic cast for array indices if type is known
946 * - array initialization
947 */
948static int gvpr_core(int argc, char *argv[], gvpropts *uopts,
949 gvpr_state_t *gs) {
951 int rv = 0;
952
954
955 gs->opts = scanArgs(argc, argv);
956 if (gs->opts.state <= 0) {
957 return gs->opts.state;
958 }
959
960 if (gs->opts.verbose)
962 gs->prog = parseProg(gs->opts.program, gs->opts.useFile);
963 if (gs->prog == NULL) {
964 return 1;
965 }
966 info.outFile = gs->opts.outFile;
967 info.argc = gs->opts.argc;
968 info.argv = gs->opts.argv;
969 info.errf = gverrorf;
970 if (uopts)
971 info.flags = uopts->flags;
972 else
973 info.flags = 0;
974 if ((uopts->flags & GV_USE_EXIT))
975 info.exitf = 0;
976 else
977 info.exitf = gvexitf;
978 gs->state = openGPRState(&info);
979 if (gs->state == NULL) {
980 return 1;
981 }
982 if (uopts->bindings)
983 addBindings(gs->state, uopts->bindings);
984 gs->xprog = compileProg(gs->prog, gs->state, gs->opts.compflags);
985 if (gs->xprog == NULL) {
986 return 1;
987 }
988
989 initGPRState(gs->state);
990
991 if ((uopts->flags & GV_USE_OUTGRAPH)) {
992 uopts->outgraphs = 0;
993 uopts->n_outgraphs = 0;
994 }
995
996 if (!(uopts->flags & GV_USE_EXIT)) {
997 gs->state->flags |= GV_USE_JUMP;
998 if ((rv = setjmp(gs->state->jbuf))) {
999 return rv;
1000 }
1001 }
1002
1003 bool incoreGraphs = uopts && uopts->ingraphs;
1004
1005 if (gs->opts.verbose)
1006 fprintf(stderr, "Parse/compile/init: %.2f secs.\n", gvelapsed_sec());
1007 /* do begin */
1008 if (gs->xprog->begin_stmt != NULL)
1009 exeval(gs->xprog->prog, gs->xprog->begin_stmt, gs->state);
1010
1011 /* if program is not null */
1012 if (gs->xprog->uses_graph) {
1013 if (uopts && uopts->ingraphs)
1014 gs->ing = newIngGraphs(0, uopts->ingraphs, ing_read);
1015 else
1016 gs->ing = newIng(0, gs->opts.inFiles, ing_read);
1017
1018 if (gs->opts.verbose)
1019 gvstart_timer();
1020 Agraph_t *nextg = NULL;
1021 for (gs->state->curgraph = nextGraph(gs->ing); gs->state->curgraph;
1022 gs->state->curgraph = nextg) {
1023 if (gs->opts.verbose)
1024 fprintf(stderr, "Read graph: %.2f secs.\n", gvelapsed_sec());
1025 gs->state->infname = fileName(gs->ing);
1026 if (gs->opts.readAhead)
1027 nextg = gs->state->nextgraph = nextGraph(gs->ing);
1028 bool cleanup = false;
1029
1030 for (size_t i = 0; i < gs->xprog->n_blocks; i++) {
1031 comp_block *bp = gs->xprog->blocks + i;
1032
1033 /* begin graph */
1034 if (incoreGraphs && gs->opts.compflags.clone)
1035 gs->state->curgraph =
1036 (Agraph_t *)cloneO(0, &gs->state->curgraph->base);
1037 gs->state->curobj = &gs->state->curgraph->base;
1038 gs->state->tvroot = 0;
1039 if (bp->begg_stmt)
1040 exeval(gs->xprog->prog, bp->begg_stmt, gs->state);
1041
1042 /* walk graph */
1043 if (bp->does_walk_graph) {
1044 cleanup = traverse(gs->state, gs->xprog->prog, bp, cleanup);
1045 }
1046 }
1047
1048 /* end graph */
1049 gs->state->curobj = &gs->state->curgraph->base;
1050 if (gs->xprog->endg_stmt != NULL)
1051 exeval(gs->xprog->prog, gs->xprog->endg_stmt, gs->state);
1052 if (gs->opts.verbose)
1053 fprintf(stderr, "Finish graph: %.2f secs.\n", gvelapsed_sec());
1054
1055 /* if $O == $G and $T is empty, delete $T */
1056 if (gs->state->outgraph == gs->state->curgraph &&
1057 gs->state->target != NULL && !agnnodes(gs->state->target))
1058 agdelete(gs->state->curgraph, gs->state->target);
1059
1060 /* output graph, if necessary
1061 * For this, the outgraph must be defined, and either
1062 * be non-empty or the -c option was used.
1063 */
1064 if (gs->state->outgraph != NULL &&
1065 (agnnodes(gs->state->outgraph) || gs->opts.compflags.srcout)) {
1066 if (uopts && (uopts->flags & GV_USE_OUTGRAPH))
1067 addOutputGraph(gs->state, uopts);
1068 else
1069 sfioWrite(gs->state->outgraph, gs->opts.outFile);
1070 }
1071
1072 if (!incoreGraphs)
1073 chkClose(gs->state->curgraph);
1074 gs->state->target = 0;
1075 gs->state->outgraph = 0;
1076
1077 if (gs->opts.verbose)
1078 gvstart_timer();
1079 if (!gs->opts.readAhead)
1080 nextg = nextGraph(gs->ing);
1081 if (gs->opts.verbose && nextg != NULL) {
1082 fprintf(stderr, "Read graph: %.2f secs.\n", gvelapsed_sec());
1083 }
1084 }
1085 }
1086
1087 /* do end */
1088 gs->state->curgraph = 0;
1089 gs->state->curobj = 0;
1090 if (gs->xprog->end_stmt != NULL)
1091 exeval(gs->xprog->prog, gs->xprog->end_stmt, gs->state);
1092
1093 return 0;
1094}
1095
1100int gvpr(int argc, char *argv[], gvpropts *uopts) {
1101 gvpr_state_t gvpr_state = {0};
1102
1103 // initialize opts to something that makes freeOpts() a no-op if we fail early
1104 gvpr_state.opts.outFile = stdout;
1105
1106 int rv = gvpr_core(argc, argv, uopts, &gvpr_state);
1107
1108 // free all allocated resources
1109 freeParseProg(gvpr_state.prog);
1110 freeCompileProg(gvpr_state.xprog);
1111 closeGPRState(gvpr_state.state);
1112 if (gvpr_state.ing != NULL) {
1113 closeIngraph(gvpr_state.ing);
1114 }
1115 freeOpts(gvpr_state.opts);
1116
1117 return rv;
1118}
1119
Agobj_t * cloneO(Agraph_t *g, Agobj_t *obj)
Definition actions.c:342
int sfioWrite(Agraph_t *g, FILE *fp)
Definition actions.c:536
void gvstart_timer(void)
Definition actions.c:851
double gvelapsed_sec(void)
Definition actions.c:853
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:78
static size_t agxbput_n(agxbuf *xb, const char *s, size_t ssz)
append string s of length ssz into xb
Definition agxbuf.h:250
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:234
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:307
static char * agxbdisown(agxbuf *xb)
Definition agxbuf.h:327
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
static char * gv_strdup(const char *original)
Definition alloc.h:101
int verbose
Definition bcomps.c:62
abstract graph C library, Cgraph API
comp_prog * compileProg(parse_prog *inp, Gpr_t *state, compflags_t flags)
Definition compile.c:2328
Agraph_t * openSubg(Agraph_t *g, char *name)
Definition compile.c:2446
void freeCompileProg(comp_prog *p)
Definition compile.c:2408
#define nData(n)
Definition compile.h:57
#define UDATA
Definition compile.h:30
#define gData(g)
Definition compile.h:58
static char * fname
void setTraceLevel(int i)
Definition error.c:32
void errorv(const char *id, int level, const char *s, va_list ap)
Definition error.c:34
void setErrorId(char *id)
Definition error.c:29
void setErrorErrors(int errors)
Definition error.c:30
#define ERROR_WARNING
Definition error.h:35
#define ERROR_ERROR
Definition error.h:36
#define ERROR_USAGE
Definition error.h:41
Extype_t exeval(Expr_t *ex, Exnode_t *exnode, void *env)
Definition exeval.c:1984
static long seed
Definition exeval.c:1049
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
static void cleanup(void)
Definition gmlparse.c:130
void * malloc(YYSIZE_T)
void free(void *)
void initGPRState(Gpr_t *state)
Definition gprstate.c:30
void addBindings(Gpr_t *state, gvprbinding *bindings)
Definition gprstate.c:89
Gpr_t * openGPRState(gpr_info *info)
Definition gprstate.c:34
void closeGPRState(Gpr_t *state)
Definition gprstate.c:117
@ TV_flat
Definition gprstate.h:27
@ TV_fwd
Definition gprstate.h:29
@ TV_rev
Definition gprstate.h:29
@ TV_postdfs
Definition gprstate.h:30
@ TV_dfs
Definition gprstate.h:29
@ TV_prepostfwd
Definition gprstate.h:31
@ TV_en
Definition gprstate.h:27
@ TV_prepostrev
Definition gprstate.h:31
@ TV_prepostdfs
Definition gprstate.h:31
@ TV_postfwd
Definition gprstate.h:30
@ TV_bfs
Definition gprstate.h:28
@ TV_ne
Definition gprstate.h:27
@ TV_postrev
Definition gprstate.h:30
node NULL
Definition grammar.y:180
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
int agnnodes(Agraph_t *g)
Definition graph.c:155
#define agopp(e)
opposite edge: flip Agedgepair_s.out ⇄ Agedgepair_s.in/*#end#*‍/
Definition cgraph.h:990
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition edge.c:348
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition edge.c:71
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:96
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition edge.c:57
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:95
Agraph_t * agconcat(Agraph_t *g, const char *filename, void *chan, Agdisc_t *disc)
merges the file contents with a pre-existing graph
Definition grammar.c:2036
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition node.c:252
int agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
Definition obj.c:20
Agraph_t * agroot(void *obj)
Definition obj.c:168
@ AGEDGE
Definition cgraph.h:207
@ AGNODE
Definition cgraph.h:207
@ AGRAPH
Definition cgraph.h:207
void aginit(Agraph_t *g, int kind, const char *rec_name, int rec_size, int move_to_front)
attach new records to objects of specified kind
Definition rec.c:170
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition subg.c:53
replacements for ctype.h functions
static bool gv_isspace(int c)
Definition gv_ctype.h:55
char * gv_find_me(void)
Definition gv_find_me.c:65
platform abstraction for finding the path to yourself
agxbput(xb, staging)
static opts_t opts
Definition gvgen.c:401
static void freeOpts(options opts)
Definition gvpr.c:396
static char * concat(char *pfx, char *sfx)
Definition gvpr.c:180
#define MARKED(x)
Definition gvpr.c:532
static char * resolve(char *arg, int verbose)
Definition gvpr.c:238
static char * Info[]
Definition gvpr.c:43
static Agobj_t * evalNode(Gpr_t *state, Expr_t *prog, comp_block *xprog, Agnode_t *n)
Definition gvpr.c:489
static void gvexitf(void *env, int v)
Definition gvpr.c:914
int gvpr(int argc, char *argv[], gvpropts *uopts)
Definition gvpr.c:1100
static void chkClose(Agraph_t *g)
Definition gvpr.c:881
static void travNodes(Gpr_t *state, Expr_t *prog, comp_block *xprog)
Definition gvpr.c:694
static void doCleanup(Agraph_t *g)
Definition gvpr.c:741
#define ONSTACK(x)
Definition gvpr.c:534
static char * gettok(char **sp)
Definition gvpr.c:96
#define PRE_VISIT
Definition gvpr.c:541
static FILE * openOut(char *name)
Definition gvpr.c:77
static bool traverse(Gpr_t *state, Expr_t *prog, comp_block *bp, bool cleanup)
Definition gvpr.c:755
#define MARK(x)
Definition gvpr.c:533
static Agedge_t * agnxtin_(Agraph_t *g, Agedge_t *e, Agnode_t *ignored)
agnxtin wrapper to tweak calling convention
Definition gvpr.c:558
#define LISTSEP
Definition gvpr.c:177
Agedge_t *(* nxttedgefn_t)(Agraph_t *, Agedge_t *, Agnode_t *)
Definition gvpr.c:539
static options scanArgs(int argc, char **argv)
Definition gvpr.c:412
static trav_fns DFSfns
Definition gvpr.c:563
static void travDFS(Gpr_t *state, Expr_t *prog, comp_block *xprog, trav_fns *fns)
Definition gvpr.c:614
static trav_fns REVfns
Definition gvpr.c:565
#define POST_VISIT
Definition gvpr.c:542
static trav_fns FWDfns
Definition gvpr.c:564
static void travBFS(Gpr_t *state, Expr_t *prog, comp_block *xprog)
Definition gvpr.c:569
static void travFlat(Gpr_t *state, Expr_t *prog, comp_block *xprog)
Definition gvpr.c:719
static char * dflt_gvprpath(void)
Definition gvpr.c:193
static void travEdges(Gpr_t *state, Expr_t *prog, comp_block *xprog)
Definition gvpr.c:704
static Agraph_t * ing_read(const char *filename, void *fp)
Definition gvpr.c:891
static Agnode_t * nextNode(Gpr_t *state, nodestream *nodes)
Definition gvpr.c:516
static void addOutputGraph(Gpr_t *state, gvpropts *uopts)
Definition gvpr.c:869
static int gvpr_core(int argc, char *argv[], gvpropts *uopts, gvpr_state_t *gs)
Definition gvpr.c:948
static int doFlags(char *arg, int argi, int argc, char **argv, options *opts)
Definition gvpr.c:336
static void gverrorf(Expr_t *handle, Exdisc_t *discipline, int level, const char *fmt,...)
Definition gvpr.c:920
Agedge_t *(* fstedgefn_t)(Agraph_t *, Agnode_t *)
Definition gvpr.c:538
static Agedge_t * agnxtout_(Agraph_t *g, Agedge_t *e, Agnode_t *ignored)
agnxtout wrapper to tweak calling convention
Definition gvpr.c:552
static const char * usage
Definition gvpr.c:49
#define NUM_ARGS
Definition gvpr.c:137
static Agobj_t * evalEdge(Gpr_t *state, Expr_t *prog, comp_block *xprog, Agedge_t *e)
Definition gvpr.c:467
static int parseArgs(char *s, int argc, char ***argv)
Definition gvpr.c:145
#define PUSH(x, e)
Definition gvpr.c:535
#define POP(x)
Definition gvpr.c:536
static char * getOptarg(int c, char **argp, int *argip, int argc, char **argv)
Definition gvpr.c:307
graph pattern scanning and processing language API, main function gvpr
#define GV_USE_OUTGRAPH
Definition gvpr.h:49
#define GV_USE_EXIT
Definition gvpr.h:47
#define GV_NEXT_SET
Definition gvpr.h:53
#define GV_USE_JUMP
Definition gvpr.h:51
table Syntax error
Definition htmlparse.y:294
char * fileName(ingraph_state *sp)
Return name of current file being processed.
Definition ingraphs.c:154
void closeIngraph(ingraph_state *sp)
Definition ingraphs.c:145
Agraph_t * nextGraph(ingraph_state *sp)
Definition ingraphs.c:59
ingraph_state * newIng(ingraph_state *sp, char **files, Agraph_t *(*readf)(const char *, void *))
Definition ingraphs.c:118
ingraph_state * newIngGraphs(ingraph_state *sp, Agraph_t **graphs, Agraph_t *(*readf)(const char *, void *))
Definition ingraphs.c:126
supports user-supplied data
#define DEFINE_LIST(name, type)
Definition list.h:22
void freeParseProg(parse_prog *prog)
Definition parse.c:491
parse_prog * parseProg(char *input, int isFile)
parses input into gpr sections
Definition parse.c:381
File system path helpers.
#define PATH_SEPARATOR
character for separating directory components in a file system path
Definition path.h:10
Agnode_t * node
Definition cgraph.h:272
a generic header of Agraph_s, Agnode_s and Agedge_s
Definition cgraph.h:210
graph or subgraph
Definition cgraph.h:424
Agobj_t base
Definition cgraph.h:425
void * user
Definition expr.h:216
Definition expr.h:220
char * tgtname
Definition gprstate.h:43
Agobj_t * curobj
Definition gprstate.h:39
Agraph_t * target
Definition gprstate.h:37
Agraph_t * curgraph
Definition gprstate.h:35
int flags
Definition gprstate.h:53
Agraph_t * outgraph
Definition gprstate.h:38
Agnode_t * tvroot
Definition gprstate.h:47
Agnode_t * tvnext
Definition gprstate.h:48
char * infname
Definition gprstate.h:44
jmp_buf jbuf
Definition gprstate.h:56
Agraph_t * nextgraph
Definition gprstate.h:36
int name_used
Definition gprstate.h:50
trav_type tvt
Definition gprstate.h:46
Exnode_t * guard
Definition compile.h:26
Exnode_t * action
Definition compile.h:27
case_stmt * node_stmts
Definition compile.h:71
Exnode_t * begg_stmt
Definition compile.h:67
size_t n_nstmts
Definition compile.h:69
size_t n_estmts
Definition compile.h:70
case_stmt * edge_stmts
Definition compile.h:72
bool does_walk_graph
does this block have a node or edge statement?
Definition compile.h:68
Exnode_t * begin_stmt
Definition compile.h:78
comp_block * blocks
Definition compile.h:80
Expr_t * prog
Definition compile.h:77
size_t n_blocks
Definition compile.h:79
bool uses_graph
does this program use the input graph?
Definition compile.h:76
Exnode_t * endg_stmt
Definition compile.h:81
Exnode_t * end_stmt
Definition compile.h:82
bool srcout
Definition compile.h:61
bool clone
Definition compile.h:63
Definition legal.c:50
collective managed state used in gvpr_core
Definition gvpr.c:902
parse_prog * prog
Definition gvpr.c:903
comp_prog * xprog
Definition gvpr.c:905
options opts
Definition gvpr.c:907
ingraph_state * ing
Definition gvpr.c:904
Gpr_t * state
Definition gvpr.c:906
size_t n_outgraphs
if GV_USE_OUTGRAPH set, output graphs
Definition gvpr.h:65
Agraph_t ** outgraphs
Definition gvpr.h:66
gvprbinding * bindings
Definition gvpr.h:70
int flags
Definition gvpr.h:69
Agraph_t ** ingraphs
Definition gvpr.h:64
Agnode_t * prev
Definition gvpr.c:513
Agnode_t * oldroot
Definition gvpr.c:512
Definition gvpr.c:63
compflags_t compflags
Definition gvpr.c:68
int argc
Definition gvpr.c:71
char * program
Definition gvpr.c:66
int readAhead
Definition gvpr.c:69
int verbose
Definition gvpr.c:74
char * cmdName
Definition gvpr.c:64
FILE * outFile
Definition gvpr.c:65
int useFile
Definition gvpr.c:67
int state
Definition gvpr.c:73
char ** inFiles
Definition gvpr.c:70
char ** argv
Definition gvpr.c:72
Definition types.h:81
unsigned char visit
Definition gvpr.c:548
nxttedgefn_t nxtedge
Definition gvpr.c:546
unsigned char undirected
Definition gvpr.c:547
fstedgefn_t fstedge
Definition gvpr.c:545
long long integer
Definition exparse.h:240
Definition grammar.c:89
#define UNREACHABLE()
Definition unreachable.h:30