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