1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include <stdio.h> /* need sprintf() */
15#include <ctype.h>
16#include "cghdr.h"
17
18#define EMPTY(s) ((s == 0) || (s)[0] == '\0')
19#define MAX(a,b) ((a)>(b)?(a):(b))
20#define CHKRV(v) {if ((v) == EOF) return EOF;}
21
22typedef void iochan_t;
23
24static int ioput(Agraph_t * g, iochan_t * ofile, char *str)
25{
26 return AGDISC(g, io)->putstr(ofile, str);
27
28}
29
30#define MAX_OUTPUTLINE 128
31#define MIN_OUTPUTLINE 60
32static int write_body(Agraph_t * g, iochan_t * ofile);
33static int Level;
34static int Max_outputline = MAX_OUTPUTLINE;
35static unsigned char Attrs_not_written_flag;
36static Agsym_t *Tailport, *Headport;
37
38static int indent(Agraph_t * g, iochan_t * ofile)
39{
40 int i;
41 for (i = Level; i > 0; i--)
42 CHKRV(ioput(g, ofile, "\t"));
43 return 0;
44}
45
46#ifndef HAVE_STRCASECMP
47
48#include <string.h>
49
50static int strcasecmp(const char *s1, const char *s2)
51{
52 while ((*s1 != '\0')
53 && (tolower(*(unsigned char *) s1) ==
54 tolower(*(unsigned char *) s2))) {
55 s1++;
56 s2++;
57 }
58
59 return tolower(*(unsigned char *) s1) - tolower(*(unsigned char *) s2);
60}
61#endif
62
63 /* alphanumeric, '.', '-', or non-ascii; basically, chars used in unquoted ids */
64#define is_id_char(c) (isalnum(c) || ((c) == '.') || ((c) == '-') || !isascii(c))
65
66/* _agstrcanon:
67 * Canonicalize ordinary strings.
68 * Assumes buf is large enough to hold output.
69 */
70static char *_agstrcanon(char *arg, char *buf)
71{
72 char *s, *p;
73 unsigned char uc;
74 int cnt = 0, dotcnt = 0;
75 int needs_quotes = FALSE;
76 int maybe_num;
77 int backslash_pending = FALSE;
78 static const char *tokenlist[] /* must agree with scan.l */
79 = { "node", "edge", "strict", "graph", "digraph", "subgraph",
80 NIL(char *)
81 };
82 const char **tok;
83
84 if (EMPTY(arg))
85 return "\"\"";
86 s = arg;
87 p = buf;
88 *p++ = '\"';
89 uc = *(unsigned char *) s++;
90 maybe_num = isdigit(uc) || (uc == '.') || (uc == '-');
91 while (uc) {
92 if (uc == '\"') {
93 *p++ = '\\';
94 needs_quotes = TRUE;
95 }
96 else if (maybe_num) {
97 if (uc == '-') {
98 if (cnt) {
99 maybe_num = FALSE;
100 needs_quotes = TRUE;
101 }
102 }
103 else if (uc == '.') {
104 if (dotcnt++) {
105 maybe_num = FALSE;
106 needs_quotes = TRUE;
107 }
108 }
109 else if (!isdigit(uc)) {
110 maybe_num = FALSE;
111 needs_quotes = TRUE;
112 }
113 }
114 else if (!ISALNUM(uc))
115 needs_quotes = TRUE;
116 *p++ = (char) uc;
117 uc = *(unsigned char *) s++;
118 cnt++;
119
120 /* If breaking long strings into multiple lines, only allow breaks after a non-id char, not a backslash, where the next char is an
121 * id char.
122 */
123 if (Max_outputline) {
124 if (uc && backslash_pending && !(is_id_char(p[-1]) || (p[-1] == '\\')) && is_id_char(uc)) {
125 *p++ = '\\';
126 *p++ = '\n';
127 needs_quotes = TRUE;
128 backslash_pending = FALSE;
129 cnt = 0;
130 } else if (uc && (cnt >= Max_outputline)) {
131 if (!(is_id_char(p[-1]) || (p[-1] == '\\')) && is_id_char(uc)) {
132 *p++ = '\\';
133 *p++ = '\n';
134 needs_quotes = TRUE;
135 cnt = 0;
136 } else {
137 backslash_pending = TRUE;
138 }
139 }
140 }
141 }
142 *p++ = '\"';
143 *p = '\0';
144 if (needs_quotes || ((cnt == 1) && ((*arg == '.') || (*arg == '-'))))
145 return buf;
146
147 /* Use quotes to protect tokens (example, a node named "node") */
148 /* It would be great if it were easier to use flex here. */
149 for (tok = tokenlist; *tok; tok++)
150 if (!strcasecmp(*tok, arg))
151 return buf;
152 return arg;
153}
154
155/* agcanonhtmlstr:
156 * Canonicalize html strings.
157 */
158static char *agcanonhtmlstr(char *arg, char *buf)
159{
160 char *s, *p;
161
162 s = arg;
163 p = buf;
164 *p++ = '<';
165 while (*s)
166 *p++ = *s++;
167 *p++ = '>';
168 *p = '\0';
169 return buf;
170}
171
172/*
173 * canonicalize a string for printing.
174 * must agree with strings in scan.l
175 * Unsafe if buffer is not large enough.
176 */
177char *agstrcanon(char *arg, char *buf)
178{
179 if (aghtmlstr(arg))
180 return agcanonhtmlstr(arg, buf);
181 else
182 return _agstrcanon(arg, buf);
183}
184
185static char *getoutputbuffer(char *str)
186{
187 static char *rv;
188 static size_t len = 0;
189 size_t req;
190
191 req = MAX(2 * strlen(str) + 2, BUFSIZ);
192 if (req > len) {
193 if (rv)
194 rv = realloc(rv, req);
195 else
196 rv = malloc(req);
197 len = req;
198 }
199 return rv;
200}
201
202/*
203 * canonicalize a string for printing.
204 * must agree with strings in scan.l
205 * Shared static buffer - unsafe.
206 */
207char *agcanonStr(char *str)
208{
209 return agstrcanon(str, getoutputbuffer(str));
210}
211
212/*
213 * canonicalize a string for printing.
214 * If html is true, use HTML canonicalization.
215 * Shared static buffer - unsafe.
216 */
217char *agcanon(char *str, int html)
218{
219 char* buf = getoutputbuffer(str);
220 if (html)
221 return agcanonhtmlstr(str, buf);
222 else
223 return _agstrcanon(str, buf);
224}
225
226static int _write_canonstr(Agraph_t * g, iochan_t * ofile, char *str,
227 int chk)
228{
229 if (chk)
230 str = agcanonStr(str);
231 else
232 str = _agstrcanon(str, getoutputbuffer(str));
233 return ioput(g, ofile, str);
234}
235
236static int write_canonstr(Agraph_t * g, iochan_t * ofile, char *str)
237{
238 return _write_canonstr(g, ofile, str, TRUE);
239}
240
241static int write_dict(Agraph_t * g, iochan_t * ofile, char *name,
242 Dict_t * dict, int top)
243{
244 int cnt = 0;
245 Dict_t *view;
246 Agsym_t *sym, *psym;
247
248 if (!top)
249 view = dtview(dict, NIL(Dict_t *));
250 else
251 view = 0;
252 for (sym = (Agsym_t *) dtfirst(dict); sym;
253 sym = (Agsym_t *) dtnext(dict, sym)) {
254 if (EMPTY(sym->defval) && !sym->print) { /* try to skip empty str (default) */
255 if (view == NIL(Dict_t *))
256 continue; /* no parent */
257 psym = (Agsym_t *) dtsearch(view, sym);
258 assert(psym);
259 if (EMPTY(psym->defval) && psym->print)
260 continue; /* also empty in parent */
261 }
262 if (cnt++ == 0) {
263 CHKRV(indent(g, ofile));
264 CHKRV(ioput(g, ofile, name));
265 CHKRV(ioput(g, ofile, " ["));
266 Level++;
267 } else {
268 CHKRV(ioput(g, ofile, ",\n"));
269 CHKRV(indent(g, ofile));
270 }
271 CHKRV(write_canonstr(g, ofile, sym->name));
272 CHKRV(ioput(g, ofile, "="));
273 CHKRV(write_canonstr(g, ofile, sym->defval));
274 }
275 if (cnt > 0) {
276 Level--;
277 if (cnt > 1) {
278 CHKRV(ioput(g, ofile, "\n"));
279 CHKRV(indent(g, ofile));
280 }
281 CHKRV(ioput(g, ofile, "];\n"));
282 }
283 if (!top)
284 dtview(dict, view); /* restore previous view */
285 return 0;
286}
287
288static int write_dicts(Agraph_t * g, iochan_t * ofile, int top)
289{
290 Agdatadict_t *def;
291 if ((def = agdatadict(g, FALSE))) {
292 CHKRV(write_dict(g, ofile, "graph", def->dict.g, top));
293 CHKRV(write_dict(g, ofile, "node", def->dict.n, top));
294 CHKRV(write_dict(g, ofile, "edge", def->dict.e, top));
295 }
296 return 0;
297}
298
299static int write_hdr(Agraph_t * g, iochan_t * ofile, int top)
300{
301 char *name, *sep, *kind, *strict;
302 int root = 0;
303 int hasName = 1;
304
305 Attrs_not_written_flag = AGATTRWF(g);
306 strict = "";
307 if (NOT(top) && agparent(g))
308 kind = "sub";
309 else {
310 root = 1;
311 if (g->desc.directed)
312 kind = "di";
313 else
314 kind = "";
315 if (agisstrict(g))
316 strict = "strict ";
317 Tailport = agattr(g, AGEDGE, TAILPORT_ID, NIL(char *));
318 Headport = agattr(g, AGEDGE, HEADPORT_ID, NIL(char *));
319 }
320 name = agnameof(g);
321 sep = " ";
322 if (!name || name[0] == LOCALNAMEPREFIX) {
323 sep = name = "";
324 hasName = 0;
325 }
326 CHKRV(indent(g, ofile));
327 CHKRV(ioput(g, ofile, strict));
328
329 /* output "<kind>graph" only for root graphs or graphs with names */
330 if (root || hasName) {
331 CHKRV(ioput(g, ofile, kind));
332 CHKRV(ioput(g, ofile, "graph "));
333 }
334 if (hasName)
335 CHKRV(write_canonstr(g, ofile, name));
336 CHKRV(ioput(g, ofile, sep));
337 CHKRV(ioput(g, ofile, "{\n"));
338 Level++;
339 CHKRV(write_dicts(g, ofile, top));
340 AGATTRWF(g) = TRUE;
341 return 0;
342}
343
344static int write_trl(Agraph_t * g, iochan_t * ofile)
345{
346 NOTUSED(g);
347 Level--;
348 CHKRV(indent(g, ofile));
349 CHKRV(ioput(g, ofile, "}\n"));
350 return 0;
351}
352
353static int irrelevant_subgraph(Agraph_t * g)
354{
355 int i, n;
356 Agattr_t *sdata, *pdata, *rdata;
357 Agdatadict_t *dd;
358
359 char *name;
360
361 name = agnameof(g);
362 if (name && name[0] != LOCALNAMEPREFIX)
363 return FALSE;
364 if ((sdata = agattrrec(g)) && (pdata = agattrrec(agparent(g)))) {
365 rdata = agattrrec(agroot(g));
366 n = dtsize(rdata->dict);
367 for (i = 0; i < n; i++)
368 if (sdata->str[i] && pdata->str[i]
369 && strcmp(sdata->str[i], pdata->str[i]))
370 return FALSE;
371 }
372 dd = agdatadict(g, FALSE);
373 if (!dd)
374 return TRUE;
375 if ((dtsize(dd->dict.n) > 0) || (dtsize(dd->dict.e) > 0))
376 return FALSE;
377 return TRUE;
378}
379
380int node_in_subg(Agraph_t * g, Agnode_t * n)
381{
382 Agraph_t *subg;
383
384 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
385 if (irrelevant_subgraph(subg))
386 continue;
387 if (agsubnode(subg, n, FALSE))
388 return TRUE;
389 }
390 return FALSE;
391}
392
393static int has_no_edges(Agraph_t * g, Agnode_t * n)
394{
395 return ((agfstin(g, n) == NIL(Agedge_t *))
396 && (agfstout(g, n) == NIL(Agedge_t *)));
397}
398
399static int has_no_predecessor_below(Agraph_t * g, Agnode_t * n,
400 uint64_t val)
401{
402 Agedge_t *e;
403
404 if (AGSEQ(n) < val)
405 return FALSE;
406 for (e = agfstin(g, n); e; e = agnxtin(g, e))
407 if (AGSEQ(e->node) < val)
408 return FALSE;
409 return TRUE;
410}
411
412static int not_default_attrs(Agraph_t * g, Agnode_t * n)
413{
414 Agattr_t *data;
415 Agsym_t *sym;
416
417 NOTUSED(g);
418 if ((data = agattrrec(n))) {
419 for (sym = (Agsym_t *) dtfirst(data->dict); sym;
420 sym = (Agsym_t *) dtnext(data->dict, sym)) {
421 if (data->str[sym->id] != sym->defval)
422 return TRUE;
423 }
424 }
425 return FALSE;
426}
427
428static int write_subgs(Agraph_t * g, iochan_t * ofile)
429{
430 Agraph_t *subg;
431
432 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
433 if (irrelevant_subgraph(subg)) {
434 write_subgs(subg, ofile);
435 }
436 else {
437 CHKRV(write_hdr(subg, ofile, FALSE));
438 CHKRV(write_body(subg, ofile));
439 CHKRV(write_trl(subg, ofile));
440 }
441 }
442 return 0;
443}
444
445static int write_edge_name(Agedge_t * e, iochan_t * ofile, int terminate)
446{
447 int rv;
448 char *p;
449 Agraph_t *g;
450
451 p = agnameof(e);
452 g = agraphof(e);
453 if (NOT(EMPTY(p))) {
454 if (!terminate) {
455 Level++;
456 }
457 CHKRV(ioput(g, ofile, "\t[key="));
458 CHKRV(write_canonstr(g, ofile, p));
459 if (terminate)
460 CHKRV(ioput(g, ofile, "]"));
461 rv = TRUE;
462 } else
463 rv = FALSE;
464 return rv;
465}
466
467
468static int write_nondefault_attrs(void *obj, iochan_t * ofile,
469 Dict_t * defdict)
470{
471 Agattr_t *data;
472 Agsym_t *sym;
473 Agraph_t *g;
474 int cnt = 0;
475 int rv;
476
477 if ((AGTYPE(obj) == AGINEDGE) || (AGTYPE(obj) == AGOUTEDGE)) {
478 CHKRV(rv = write_edge_name(obj, ofile, FALSE));
479 if (rv)
480 cnt++;
481 }
482 data = agattrrec(obj);
483 g = agraphof(obj);
484 if (data)
485 for (sym = (Agsym_t *) dtfirst(defdict); sym;
486 sym = (Agsym_t *) dtnext(defdict, sym)) {
487 if ((AGTYPE(obj) == AGINEDGE) || (AGTYPE(obj) == AGOUTEDGE)) {
488 if (Tailport && (sym->id == Tailport->id))
489 continue;
490 if (Headport && (sym->id == Headport->id))
491 continue;
492 }
493 if (data->str[sym->id] != sym->defval) {
494 if (cnt++ == 0) {
495 CHKRV(ioput(g, ofile, "\t["));
496 Level++;
497 } else {
498 CHKRV(ioput(g, ofile, ",\n"));
499 CHKRV(indent(g, ofile));
500 }
501 CHKRV(write_canonstr(g, ofile, sym->name));
502 CHKRV(ioput(g, ofile, "="));
503 CHKRV(write_canonstr(g, ofile, data->str[sym->id]));
504 }
505 }
506 if (cnt > 0) {
507 CHKRV(ioput(g, ofile, "]"));
508 Level--;
509 }
510 AGATTRWF((Agobj_t *) obj) = TRUE;
511 return 0;
512}
513
514static int write_nodename(Agnode_t * n, iochan_t * ofile)
515{
516 char *name, buf[20];
517 Agraph_t *g;
518
519 name = agnameof(n);
520 g = agraphof(n);
521 if (name) {
522 CHKRV(write_canonstr(g, ofile, name));
523 } else {
524 sprintf(buf, "_%ld_SUSPECT", AGID(n)); /* could be deadly wrong */
525 CHKRV(ioput(g, ofile, buf));
526 }
527 return 0;
528}
529
530static int attrs_written(void *obj)
531{
532 return (AGATTRWF((Agobj_t *) obj));
533}
534
535static int write_node(Agnode_t * n, iochan_t * ofile, Dict_t * d)
536{
537 Agraph_t *g;
538
539 g = agraphof(n);
540 CHKRV(indent(g, ofile));
541 CHKRV(write_nodename(n, ofile));
542 if (NOT(attrs_written(n)))
543 CHKRV(write_nondefault_attrs(n, ofile, d));
544 return ioput(g, ofile, ";\n");
545}
546
547/* node must be written if it wasn't already emitted because of
548 * a subgraph or one of its predecessors, and if it is a singleton
549 * or has non-default attributes.
550 */
551static int write_node_test(Agraph_t * g, Agnode_t * n,
552 uint64_t pred_id)
553{
554 if (NOT(node_in_subg(g, n)) && has_no_predecessor_below(g, n, pred_id)) {
555 if (has_no_edges(g, n) || not_default_attrs(g, n))
556 return TRUE;
557 }
558 return FALSE;
559}
560
561static int write_port(Agedge_t * e, iochan_t * ofile, Agsym_t * port)
562{
563 char *val;
564 Agraph_t *g;
565
566 if (!port)
567 return 0;
568 g = agraphof(e);
569 val = agxget(e, port);
570 if (val[0] == '\0')
571 return 0;
572
573 CHKRV(ioput(g, ofile, ":"));
574 if (aghtmlstr(val)) {
575 CHKRV(write_canonstr(g, ofile, val));
576 } else {
577 char *s = strchr(val, ':');
578 if (s) {
579 *s = '\0';
580 CHKRV(_write_canonstr(g, ofile, val, FALSE));
581 CHKRV(ioput(g, ofile, ":"));
582 CHKRV(_write_canonstr(g, ofile, s + 1, FALSE));
583 *s = ':';
584 } else {
585 CHKRV(_write_canonstr(g, ofile, val, FALSE));
586 }
587 }
588 return 0;
589}
590
591static int write_edge_test(Agraph_t * g, Agedge_t * e)
592{
593 Agraph_t *subg;
594
595 /* can use agedge() because we subverted the dict compar_f */
596 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
597 if (irrelevant_subgraph(subg))
598 continue;
599 if (agsubedge(subg, e, FALSE))
600 return FALSE;
601 }
602 return TRUE;
603}
604
605static int write_edge(Agedge_t * e, iochan_t * ofile, Dict_t * d)
606{
607 Agnode_t *t, *h;
608 Agraph_t *g;
609
610 t = AGTAIL(e);
611 h = AGHEAD(e);
612 g = agraphof(t);
613 CHKRV(indent(g, ofile));
614 CHKRV(write_nodename(t, ofile));
615 CHKRV(write_port(e, ofile, Tailport));
616 CHKRV(ioput(g, ofile, (agisdirected(agraphof(t)) ? " -> " : " -- ")));
617 CHKRV(write_nodename(h, ofile));
618 CHKRV(write_port(e, ofile, Headport));
619 if (NOT(attrs_written(e))) {
620 CHKRV(write_nondefault_attrs(e, ofile, d));
621 } else {
622 CHKRV(write_edge_name(e, ofile, TRUE));
623 }
624 return ioput(g, ofile, ";\n");
625}
626
627static int write_body(Agraph_t * g, iochan_t * ofile)
628{
629 Agnode_t *n, *prev;
630 Agedge_t *e;
631 Agdatadict_t *dd;
632 /* int has_attr; */
633
634 /* has_attr = (agattrrec(g) != NIL(Agattr_t*)); */
635
636 CHKRV(write_subgs(g, ofile));
637 dd = agdatadict(agroot(g), FALSE);
638 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
639 if (write_node_test(g, n, AGSEQ(n)))
640 CHKRV(write_node(n, ofile, dd ? dd->dict.n : 0));
641 prev = n;
642 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
643 if ((prev != aghead(e))
644 && write_node_test(g, aghead(e), AGSEQ(n))) {
645 CHKRV(write_node(aghead(e), ofile, dd ? dd->dict.n : 0));
646 prev = aghead(e);
647 }
648 if (write_edge_test(g, e))
649 CHKRV(write_edge(e, ofile, dd ? dd->dict.e : 0));
650 }
651
652 }
653 return 0;
654}
655
656static void set_attrwf(Agraph_t * g, int toplevel, int value)
657{
658 Agraph_t *subg;
659 Agnode_t *n;
660 Agedge_t *e;
661
662 AGATTRWF(g) = value;
663 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
664 set_attrwf(subg, FALSE, value);
665 }
666 if (toplevel) {
667 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
668 AGATTRWF(n) = value;
669 for (e = agfstout(g, n); e; e = agnxtout(g, e))
670 AGATTRWF(e) = value;
671 }
672 }
673}
674
675/* agwrite:
676 * Return 0 on success, EOF on failure
677 */
678int agwrite(Agraph_t * g, void *ofile)
679{
680 char* s;
681 int len;
682 Level = 0; /* re-initialize tab level */
683 if ((s = agget(g, "linelength")) && isdigit(*s)) {
684 len = (int)strtol(s, (char **)NULL, 10);
685 if ((len == 0) || (len >= MIN_OUTPUTLINE))
686 Max_outputline = len;
687 }
688 set_attrwf(g, TRUE, FALSE);
689 CHKRV(write_hdr(g, ofile, TRUE));
690 CHKRV(write_body(g, ofile));
691 CHKRV(write_trl(g, ofile));
692 Max_outputline = MAX_OUTPUTLINE;
693 return AGDISC(g, io)->flush(ofile);
694}
695