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
15#include "convert.h"
16#include "agxbuf.h"
17#ifdef HAVE_EXPAT
18#include <expat.h>
19#include <ctype.h>
20
21#ifndef XML_STATUS_ERROR
22#define XML_STATUS_ERROR 0
23#endif
24
25#define STACK_DEPTH 32
26#define BUFSIZE 20000
27#define SMALLBUF 1000
28#define NAMEBUF 100
29
30#define GXL_ATTR "_gxl_"
31#define GXL_ID "_gxl_id"
32#define GXL_ROLE "_gxl_role"
33#define GXL_HYPER "_gxl_hypergraph"
34#define GXL_FROM "_gxl_fromorder"
35#define GXL_TO "_gxl_toorder"
36#define GXL_TYPE "_gxl_type"
37#define GXL_COMP "_gxl_composite_"
38#define GXL_LOC "_gxl_locator_"
39
40#define TAG_NONE -1
41#define TAG_GRAPH 0
42#define TAG_NODE 1
43#define TAG_EDGE 2
44
45typedef struct slist slist;
46struct slist {
47 slist *next;
48 char buf[1];
49};
50
51#define NEW(t) (t*)malloc(sizeof(t))
52#define N_NEW(n,t) (t*)malloc((n)*sizeof(t))
53/* Round x up to next multiple of y, which is a power of 2 */
54#define ROUND2(x,y) (((x) + ((y)-1)) & ~((y)-1))
55
56static void pushString(slist ** stk, const char *s)
57{
58 int sz = ROUND2(sizeof(slist) + strlen(s), sizeof(void *));
59 slist *sp = (slist *) N_NEW(sz, char);
60 strcpy(sp->buf, s);
61 sp->next = *stk;
62 *stk = sp;
63}
64
65static void popString(slist ** stk)
66{
67 slist *sp = *stk;
68 if (!sp) {
69 fprintf(stderr, "PANIC: gxl2gv: empty element stack\n");
70 exit(1);
71 }
72 *stk = sp->next;
73 free(sp);
74}
75
76static char *topString(slist * stk)
77{
78 if (!stk) {
79 fprintf(stderr, "PANIC: gxl2gv: empty element stack\n");
80 exit(1);
81 }
82 return stk->buf;
83}
84
85static void freeString(slist * stk)
86{
87 slist *sp;
88
89 while (stk) {
90 sp = stk->next;
91 free(stk);
92 stk = sp;
93 }
94}
95
96typedef struct userdata {
97 agxbuf xml_attr_name;
98 agxbuf xml_attr_value;
99 agxbuf composite_buffer;
100 slist *elements;
101 int listen;
102 int closedElementType;
103 int globalAttrType;
104 int compositeReadState;
105 int edgeinverted;
106 Dt_t *nameMap;
107} userdata_t;
108
109static Agraph_t *root; /* root graph */
110static int Current_class; /* Current element type */
111static Agraph_t *G; /* Current graph */
112static Agnode_t *N; /* Set if Current_class == TAG_NODE */
113static Agedge_t *E; /* Set if Current_class == TAG_EDGE */
114
115static int GSP;
116static Agraph_t *Gstack[STACK_DEPTH];
117
118typedef struct {
119 Dtlink_t link;
120 char *name;
121 char *unique_name;
122} namev_t;
123
124static namev_t *make_nitem(Dt_t * d, namev_t * objp, Dtdisc_t * disc)
125{
126 namev_t *np = NEW(namev_t);
127 np->name = objp->name;
128 np->unique_name = 0;
129 return np;
130}
131
132static void free_nitem(Dt_t * d, namev_t * np, Dtdisc_t * disc)
133{
134 free(np->unique_name);
135 free(np);
136}
137
138static Dtdisc_t nameDisc = {
139 offsetof(namev_t, name),
140 -1,
141 offsetof(namev_t, link),
142 (Dtmake_f) make_nitem,
143 (Dtfree_f) free_nitem,
144 NIL(Dtcompar_f),
145 NIL(Dthash_f),
146 NIL(Dtmemory_f),
147 NIL(Dtevent_f)
148};
149
150static userdata_t *genUserdata(void)
151{
152 userdata_t *user = NEW(userdata_t);
153 agxbinit(&(user->xml_attr_name), NAMEBUF, 0);
154 agxbinit(&(user->xml_attr_value), SMALLBUF, 0);
155 agxbinit(&(user->composite_buffer), SMALLBUF, 0);
156 user->listen = FALSE;
157 user->elements = 0;
158 user->closedElementType = TAG_NONE;
159 user->globalAttrType = TAG_NONE;
160 user->compositeReadState = FALSE;
161 user->edgeinverted = FALSE;
162 user->nameMap = dtopen(&nameDisc, Dtoset);
163 return user;
164}
165
166static void freeUserdata(userdata_t * ud)
167{
168 dtclose(ud->nameMap);
169 agxbfree(&(ud->xml_attr_name));
170 agxbfree(&(ud->xml_attr_value));
171 agxbfree(&(ud->composite_buffer));
172 freeString(ud->elements);
173 free(ud);
174}
175
176static void addToMap(Dt_t * map, char *name, char *uniqueName)
177{
178 namev_t obj;
179 namev_t *objp;
180
181 obj.name = name;
182 objp = dtinsert(map, &obj);
183 assert(objp->unique_name == 0);
184 objp->unique_name = strdup(uniqueName);
185}
186
187static char *mapLookup(Dt_t * nm, char *name)
188{
189 namev_t *objp = dtmatch(nm, name);
190 if (objp)
191 return objp->unique_name;
192 else
193 return 0;
194}
195
196static int isAnonGraph(char *name)
197{
198 if (*name++ != '%')
199 return 0;
200 while (isdigit(*name))
201 name++; /* skip over digits */
202 return (*name == '\0');
203}
204
205static void push_subg(Agraph_t * g)
206{
207 if (GSP == STACK_DEPTH) {
208 fprintf(stderr, "gxl2gv: Too many (> %d) nestings of subgraphs\n",
209 STACK_DEPTH);
210 exit(1);
211 } else if (GSP == 0)
212 root = g;
213 G = Gstack[GSP++] = g;
214}
215
216static Agraph_t *pop_subg(void)
217{
218 Agraph_t *g;
219 if (GSP == 0) {
220 fprintf(stderr, "gxl2gv: Gstack underflow in graph parser\n");
221 exit(1);
222 }
223 g = Gstack[--GSP];
224 if (GSP > 0)
225 G = Gstack[GSP - 1];
226 return g;
227}
228
229static Agnode_t *bind_node(const char *name)
230{
231 N = agnode(G, (char *) name, 1);
232 return N;
233}
234
235static Agedge_t *bind_edge(const char *tail, const char *head)
236{
237 Agnode_t *tailNode, *headNode;
238 char *key = 0;
239
240 tailNode = agnode(G, (char *) tail, 1);
241 headNode = agnode(G, (char *) head, 1);
242 E = agedge(G, tailNode, headNode, key, 1);
243 return E;
244}
245
246static int get_xml_attr(char *attrname, const char **atts)
247{
248 int count = 0;
249 while (atts[count] != NULL) {
250 if (strcmp(attrname, atts[count]) == 0) {
251 return count + 1;
252 }
253 count += 2;
254 }
255 return -1;
256}
257
258static void setName(Dt_t * names, Agobj_t * n, char *value)
259{
260 Agsym_t *ap;
261 char *oldName;
262
263 ap = agattr(root, AGTYPE(n), GXL_ID, "");
264 agxset(n, ap, agnameof(n));
265 oldName = agxget(n, ap); /* set/get gives us new copy */
266 addToMap(names, oldName, value);
267 agrename(n, value);
268}
269
270static char *defval = "";
271
272static void
273setNodeAttr(Agnode_t * np, char *name, char *value, userdata_t * ud)
274{
275 Agsym_t *ap;
276
277 if (strcmp(name, "name") == 0) {
278 setName(ud->nameMap, (Agobj_t *) np, value);
279 } else {
280 ap = agattr(root, AGNODE, name, 0);
281 if (!ap)
282 ap = agattr(root, AGNODE, name, defval);
283 agxset(np, ap, value);
284 }
285}
286
287#define NODELBL "node:"
288#define NLBLLEN (sizeof(NODELBL)-1)
289#define EDGELBL "edge:"
290#define ELBLLEN (sizeof(EDGELBL)-1)
291
292/* setGlobalNodeAttr:
293 * Set global node attribute.
294 * The names must always begin with "node:".
295 */
296static void
297setGlobalNodeAttr(Agraph_t * g, char *name, char *value, userdata_t * ud)
298{
299 if (strncmp(name, NODELBL, NLBLLEN))
300 fprintf(stderr,
301 "Warning: global node attribute %s in graph %s does not begin with the prefix %s\n",
302 name, agnameof(g), NODELBL);
303 else
304 name += NLBLLEN;
305 if ((g != root) && !agattr(root, AGNODE, name, 0))
306 agattr(root, AGNODE, name, defval);
307 agattr(G, AGNODE, name, value);
308}
309
310static void
311setEdgeAttr(Agedge_t * ep, char *name, char *value, userdata_t * ud)
312{
313 Agsym_t *ap;
314 char *attrname;
315
316 if (strcmp(name, "headport") == 0) {
317 if (ud->edgeinverted)
318 attrname = "tailport";
319 else
320 attrname = "headport";
321 ap = agattr(root, AGEDGE, attrname, 0);
322 if (!ap)
323 ap = agattr(root, AGEDGE, attrname, defval);
324 agxset(ep, ap, value);
325 } else if (strcmp(name, "tailport") == 0) {
326 if (ud->edgeinverted)
327 attrname = "headport";
328 else
329 attrname = "tailport";
330 ap = agattr(root, AGEDGE, attrname, 0);
331 if (!ap)
332 ap = agattr(root, AGEDGE, attrname, defval);
333 agxset(ep, ap, value);
334 } else {
335 ap = agattr(root, AGEDGE, name, 0);
336 if (!ap)
337 ap = agattr(root, AGEDGE, name, defval);
338 agxset(ep, ap, value);
339 }
340}
341
342/* setGlobalEdgeAttr:
343 * Set global edge attribute.
344 * The names always begin with "edge:".
345 */
346static void
347setGlobalEdgeAttr(Agraph_t * g, char *name, char *value, userdata_t * ud)
348{
349 if (strncmp(name, EDGELBL, ELBLLEN))
350 fprintf(stderr,
351 "Warning: global edge attribute %s in graph %s does not begin with the prefix %s\n",
352 name, agnameof(g), EDGELBL);
353 else
354 name += ELBLLEN;
355 if ((g != root) && !agattr(root, AGEDGE, name, 0))
356 agattr(root, AGEDGE, name, defval);
357 agattr(g, AGEDGE, name, value);
358}
359
360static void
361setGraphAttr(Agraph_t * g, char *name, char *value, userdata_t * ud)
362{
363 Agsym_t *ap;
364
365 if ((g == root) && !strcmp(name, "strict") && !strcmp(value, "true")) {
366 g->desc.strict = 1;
367 } else if (strcmp(name, "name") == 0)
368 setName(ud->nameMap, (Agobj_t *) g, value);
369 else {
370 ap = agattr(root, AGRAPH, name, 0);
371 if (ap)
372 agxset(g, ap, value);
373 else if (g == root)
374 agattr(root, AGRAPH, name, value);
375 else {
376 ap = agattr(root, AGRAPH, name, defval);
377 agxset(g, ap, value);
378 }
379 }
380}
381
382static void setAttr(char *name, char *value, userdata_t * ud)
383{
384 switch (Current_class) {
385 case TAG_GRAPH:
386 setGraphAttr(G, name, value, ud);
387 break;
388 case TAG_NODE:
389 setNodeAttr(N, name, value, ud);
390 break;
391 case TAG_EDGE:
392 setEdgeAttr(E, name, value, ud);
393 break;
394 }
395}
396
397/*------------- expat handlers ----------------------------------*/
398
399static void
400startElementHandler(void *userData, const char *name, const char **atts)
401{
402 int pos;
403 userdata_t *ud = (userdata_t *) userData;
404 Agraph_t *g = NULL;
405
406 if (strcmp(name, "gxl") == 0) {
407 /* do nothing */
408 } else if (strcmp(name, "graph") == 0) {
409 const char *edgeMode = "";
410 const char *id;
411 char buf[NAMEBUF]; /* holds % + number */
412
413 Current_class = TAG_GRAPH;
414 if (ud->closedElementType == TAG_GRAPH) {
415 fprintf(stderr,
416 "Warning: Node contains more than one graph.\n");
417 }
418 id = atts[get_xml_attr("id", atts)];
419 pos = get_xml_attr("edgemode", atts);
420 if (pos > 0) {
421 edgeMode = atts[pos];
422 }
423
424 if (GSP == 0) {
425 if (strcmp(edgeMode, "directed") == 0) {
426 g = agopen((char *) id, Agdirected, &AgDefaultDisc);
427 } else if (strcmp(edgeMode, "undirected") == 0) {
428 g = agopen((char *) id, Agundirected, &AgDefaultDisc);
429 } else {
430 fprintf(stderr,
431 "Warning: graph has no edgemode attribute");
432 fprintf(stderr, " - assume directed\n");
433 g = agopen((char *) id, Agdirected, &AgDefaultDisc);
434 }
435 push_subg(g);
436 } else {
437 Agraph_t *subg;
438 if (isAnonGraph((char *) id)) {
439 static int anon_id = 1;
440 sprintf(buf, "%%%d", anon_id++);
441 id = buf;
442 }
443 subg = agsubg(G, (char *) id, 1);
444 push_subg(subg);
445 }
446
447 pos = get_xml_attr("role", atts);
448 if (pos > 0) {
449 setGraphAttr(G, GXL_ROLE, (char *) atts[pos], ud);
450 }
451
452 pos = get_xml_attr("hypergraph", atts);
453 if (pos > 0) {
454 setGraphAttr(G, GXL_HYPER, (char *) atts[pos], ud);
455 }
456
457 pushString(&ud->elements, id);
458 } else if (strcmp(name, "node") == 0) {
459 Current_class = TAG_NODE;
460 pos = get_xml_attr("id", atts);
461 if (pos > 0) {
462 const char *attrname;
463 attrname = atts[pos];
464
465 bind_node(attrname);
466
467 pushString(&ud->elements, attrname);
468 }
469
470 } else if (strcmp(name, "edge") == 0) {
471 const char *head = "", *tail = "";
472 char *tname;
473 Agnode_t *t;
474
475 Current_class = TAG_EDGE;
476 pos = get_xml_attr("from", atts);
477 if (pos > 0)
478 tail = atts[pos];
479 pos = get_xml_attr("to", atts);
480 if (pos > 0)
481 head = atts[pos];
482
483 tname = mapLookup(ud->nameMap, (char *) tail);
484 if (tname)
485 tail = tname;
486
487 tname = mapLookup(ud->nameMap, (char *) head);
488 if (tname)
489 head = tname;
490
491 bind_edge(tail, head);
492
493 t = AGTAIL(E);
494 tname = agnameof(t);
495
496 if (strcmp(tname, tail) == 0) {
497 ud->edgeinverted = FALSE;
498 } else if (strcmp(tname, head) == 0) {
499 ud->edgeinverted = TRUE;
500 }
501
502 pos = get_xml_attr("fromorder", atts);
503 if (pos > 0) {
504 setEdgeAttr(E, GXL_FROM, (char *) atts[pos], ud);
505 }
506
507 pos = get_xml_attr("toorder", atts);
508 if (pos > 0) {
509 setEdgeAttr(E, GXL_TO, (char *) atts[pos], ud);
510 }
511
512 pos = get_xml_attr("id", atts);
513 if (pos > 0) {
514 setEdgeAttr(E, GXL_ID, (char *) atts[pos], ud);
515 }
516 } else if (strcmp(name, "attr") == 0) {
517 const char *attrname = atts[get_xml_attr("name", atts)];
518
519 agxbput(&ud->xml_attr_name, (char *) attrname);
520 pos = get_xml_attr("kind", atts);
521
522 if (pos > 0) {
523 if (strcmp("node", atts[pos]) == 0)
524 ud->globalAttrType = TAG_NODE;
525 else if (strcmp("edge", atts[pos]) == 0)
526 ud->globalAttrType = TAG_EDGE;
527 else if (strcmp("graph", atts[pos]) == 0)
528 ud->globalAttrType = TAG_GRAPH;
529 } else {
530 ud->globalAttrType = TAG_NONE;
531 }
532
533 } else if (strcmp(name, "string") == 0
534 || strcmp(name, "bool") == 0
535 || strcmp(name, "int") == 0 || strcmp(name, "float") == 0) {
536
537 ud->listen = TRUE;
538 if (ud->compositeReadState) {
539 agxbputc(&ud->composite_buffer, '<');
540 agxbput(&ud->composite_buffer, (char *) name);
541 agxbputc(&ud->composite_buffer, '>');
542 }
543 } else if (strcmp(name, "rel") == 0 || strcmp(name, "relend") == 0) {
544 fprintf(stderr, "%s element is ignored by DOT\n", name);
545 } else if (strcmp(name, "type") == 0) {
546 pos = get_xml_attr("xlink:href", atts);
547 if (pos > 0) {
548 setAttr(GXL_TYPE, (char *) atts[pos], ud);
549 }
550 } else if (strcmp(name, "locator") == 0) {
551 pos = get_xml_attr("xlink:href", atts);
552 if (pos > 0) {
553 const char *href = atts[pos];
554 agxbput(&ud->xml_attr_value, GXL_LOC);
555 agxbput(&ud->xml_attr_value, (char *) href);
556 }
557 } else if (strcmp(name, "seq") == 0
558 || strcmp(name, "set") == 0
559 || strcmp(name, "bag") == 0
560 || strcmp(name, "tup") == 0 || strcmp(name, "enum") == 0) {
561
562 ud->compositeReadState = TRUE;
563 agxbputc(&ud->composite_buffer, '<');
564 agxbput(&ud->composite_buffer, (char *) name);
565 agxbputc(&ud->composite_buffer, '>');
566 } else {
567 /* must be some extension */
568 fprintf(stderr,
569 "Unknown node %s; DOT does not support extensions.\n",
570 name);
571 }
572}
573
574static void endElementHandler(void *userData, const char *name)
575{
576 userdata_t *ud = (userdata_t *) userData;
577
578 if (strcmp(name, "graph") == 0) {
579 pop_subg();
580 popString(&ud->elements);
581 ud->closedElementType = TAG_GRAPH;
582 } else if (strcmp(name, "node") == 0) {
583 char *ele_name = topString(ud->elements);
584 if (ud->closedElementType == TAG_GRAPH) {
585 Agnode_t *node = agnode(root, ele_name, 0);
586 agdelete(root, node);
587 }
588 popString(&ud->elements);
589 Current_class = TAG_GRAPH;
590 N = 0;
591 ud->closedElementType = TAG_NODE;
592 } else if (strcmp(name, "edge") == 0) {
593 Current_class = TAG_GRAPH;
594 E = 0;
595 ud->closedElementType = TAG_EDGE;
596 ud->edgeinverted = FALSE;
597 } else if (strcmp(name, "attr") == 0) {
598 char *name;
599 char *value;
600 char buf[SMALLBUF] = GXL_COMP;
601 char *dynbuf = 0;
602
603 ud->closedElementType = TAG_NONE;
604 if (ud->compositeReadState) {
605 int len = sizeof(GXL_COMP) + agxblen(&ud->xml_attr_name);
606 if (len <= SMALLBUF) {
607 name = buf;
608 } else {
609 name = dynbuf = N_NEW(len, char);
610 strcpy(name, GXL_COMP);
611 }
612 strcpy(name + sizeof(GXL_COMP) - 1,
613 agxbuse(&ud->xml_attr_name));
614 value = agxbuse(&ud->composite_buffer);
615 agxbclear(&ud->xml_attr_value);
616 ud->compositeReadState = FALSE;
617 } else {
618 name = agxbuse(&ud->xml_attr_name);
619 value = agxbuse(&ud->xml_attr_value);
620 }
621
622 switch (ud->globalAttrType) {
623 case TAG_NONE:
624 setAttr(name, value, ud);
625 break;
626 case TAG_NODE:
627 setGlobalNodeAttr(G, name, value, ud);
628 break;
629 case TAG_EDGE:
630 setGlobalEdgeAttr(G, name, value, ud);
631 break;
632 case TAG_GRAPH:
633 setGraphAttr(G, name, value, ud);
634 break;
635 }
636 if (dynbuf)
637 free(dynbuf);
638 ud->globalAttrType = TAG_NONE;
639 } else if (strcmp(name, "string") == 0
640 || strcmp(name, "bool") == 0
641 || strcmp(name, "int") == 0 || strcmp(name, "float") == 0) {
642 ud->listen = FALSE;
643 if (ud->compositeReadState) {
644 agxbputc(&ud->composite_buffer, '<');
645 agxbputc(&ud->composite_buffer, '/');
646 agxbput(&ud->composite_buffer, (char *) name);
647 agxbputc(&ud->composite_buffer, '>');
648 }
649 } else if (strcmp(name, "seq") == 0
650 || strcmp(name, "set") == 0
651 || strcmp(name, "bag") == 0
652 || strcmp(name, "tup") == 0 || strcmp(name, "enum") == 0) {
653 agxbputc(&ud->composite_buffer, '<');
654 agxbputc(&ud->composite_buffer, '/');
655 agxbput(&ud->composite_buffer, (char *) name);
656 agxbputc(&ud->composite_buffer, '>');
657 }
658}
659
660static void characterDataHandler(void *userData, const char *s, int length)
661{
662 userdata_t *ud = (userdata_t *) userData;
663
664 if (!ud->listen)
665 return;
666
667 if (ud->compositeReadState) {
668 agxbput_n(&ud->composite_buffer, (char *) s, length);
669 return;
670 }
671
672 agxbput_n(&ud->xml_attr_value, (char *) s, length);
673}
674
675Agraph_t *gxl_to_gv(FILE * gxlFile)
676{
677 char buf[BUFSIZE];
678 int done;
679 userdata_t *udata = genUserdata();
680 XML_Parser parser = XML_ParserCreate(NULL);
681
682 XML_SetUserData(parser, udata);
683 XML_SetElementHandler(parser, startElementHandler, endElementHandler);
684 XML_SetCharacterDataHandler(parser, characterDataHandler);
685
686 Current_class = TAG_GRAPH;
687 root = 0;
688 do {
689 size_t len = fread(buf, 1, sizeof(buf), gxlFile);
690 if (len == 0)
691 break;
692 done = len < sizeof(buf);
693 if (XML_Parse(parser, buf, len, done) == XML_STATUS_ERROR) {
694 fprintf(stderr,
695 "%s at line %lu\n",
696 XML_ErrorString(XML_GetErrorCode(parser)),
697 XML_GetCurrentLineNumber(parser));
698 exit(1);
699 }
700 } while (!done);
701 XML_ParserFree(parser);
702 freeUserdata(udata);
703
704 return root;
705}
706
707#endif
708