#pragma prototyped
#include <convert.h>
#include "aghdr.h"
#include "agxbuf.h"
#ifdef HAVE_LIBEXPAT
#include <expat.h>
#ifndef XML_STATUS_ERROR
#define XML_STATUS_ERROR 0
#endif
#define STACK_DEPTH 32
#define BUFSIZE 20000
#define SMALLBUF 1000
#define NAMEBUF 100
#define GXL_ATTR "_gxl_"
#define GXL_ID "_gxl_id"
#define GXL_ROLE "_gxl_role"
#define GXL_HYPER "_gxl_hypergraph"
#define GXL_FROM "_gxl_fromorder"
#define GXL_TO "_gxl_toorder"
#define GXL_TYPE "_gxl_type"
#define GXL_COMP "_gxl_composite_"
#define GXL_LOC "_gxl_locator_"
#define TAG_NONE -1
#define TAG_GRAPH 0
#define TAG_NODE 1
#define TAG_EDGE 2
typedef struct slist slist;
struct slist {
slist* next;
char buf[1];
};
#define NEW(t) (t*)malloc(sizeof(t))
#define N_NEW(n,t) (t*)malloc((n)*sizeof(t))
#define ROUND2(x,y) (((x) + ((y)-1)) & ~((y)-1))
static void
pushString (slist** stk, const char* s)
{
int sz = ROUND2(sizeof(slist)+strlen(s),sizeof(void*));
slist* sp = (slist*)N_NEW(sz,char);
strcpy (sp->buf, s);
sp->next = *stk;
*stk = sp;
}
static void
popString (slist** stk)
{
slist* sp = *stk;
if (!sp) {
fprintf (stderr, "PANIC: gxl2dot: empty element stack\n");
exit(1);
}
*stk = sp->next;
free (sp);
}
static char*
topString (slist* stk)
{
if (!stk) {
fprintf (stderr, "PANIC: gxl2dot: empty element stack\n");
exit(1);
}
return stk->buf;
}
static void
freeString (slist* stk)
{
slist* sp;
while (stk) {
sp = stk->next;
free (stk);
stk = sp;
}
}
typedef struct userdata {
agxbuf xml_attr_name;
agxbuf xml_attr_value;
agxbuf composite_buffer;
slist* elements;
int listen;
int closedElementType;
int globalAttrType;
int compositeReadState;
int edgeinverted;
Dt_t* nameMap;
} userdata_t;
static Agraph_t* root;
static int Current_class;
static Agraph_t* G;
static Agnode_t* N;
static Agedge_t* E;
static int GSP;
static Agraph_t *Gstack[STACK_DEPTH];
typedef struct {
Dtlink_t link;
char* name;
char* unique_name;
} namev_t;
static namev_t*
make_nitem (Dt_t* d, namev_t* objp, Dtdisc_t* disc)
{
namev_t* np = NEW(namev_t);
np->name = objp->name;
np->unique_name = 0;
return np;
}
static void
free_nitem (Dt_t* d, namev_t* np, Dtdisc_t* disc)
{
free (np);
}
static Dtdisc_t nameDisc = {
offsetof(namev_t,name),
-1,
offsetof(namev_t,link),
(Dtmake_f)make_nitem,
(Dtfree_f)free_nitem,
NIL(Dtcompar_f),
NIL(Dthash_f),
NIL(Dtmemory_f),
NIL(Dtevent_f)
};
static userdata_t*
genUserdata()
{
userdata_t* user = NEW(userdata_t);
agxbinit (&(user->xml_attr_name), NAMEBUF, 0);
agxbinit (&(user->xml_attr_value), SMALLBUF, 0);
agxbinit (&(user->composite_buffer), SMALLBUF, 0);
user->listen = FALSE;
user->elements = 0;
user->closedElementType = TAG_NONE;
user->globalAttrType = TAG_NONE;
user->compositeReadState = FALSE;
user->edgeinverted = FALSE;
user->nameMap = dtopen (&nameDisc, Dtoset);
return user;
}
static void
freeUserdata(userdata_t* ud)
{
dtclose(ud->nameMap);
agxbfree (&(ud->xml_attr_name));
agxbfree (&(ud->xml_attr_value));
agxbfree (&(ud->composite_buffer));
freeString(ud->elements);
free(ud);
}
static void
addToMap(Dt_t* map, char* name, char* uniqueName)
{
namev_t obj;
namev_t* objp;
obj.name = name;
objp = dtinsert (map, &obj);
assert (objp->unique_name == 0);
objp->unique_name = uniqueName;
}
static char*
mapLookup(Dt_t* nm, char* name)
{
namev_t* objp = dtmatch (nm, name);
if (objp) return objp->unique_name;
else return 0;
}
static int
isAnonGraph(char *name)
{
if (*name++ != '%') return 0;
while (isdigit(*name)) name++;
return (*name == '\0');
}
static void
push_subg(Agraph_t *g)
{
if (GSP == STACK_DEPTH) {
fprintf (stderr, "gxl2dot: Too many (> %d) nestings of subgraphs\n",
STACK_DEPTH);
exit(1);
}
else if (GSP == 0)
root = g;
G = Gstack[GSP++] = g;
}
static Agraph_t*
pop_subg(void)
{
Agraph_t *g;
if (GSP == 0) {
fprintf(stderr,"gxl2dot: Gstack underflow in graph parser\n"); exit(1);
}
g = Gstack[--GSP];
if (GSP > 0) G = Gstack[GSP - 1];
return g;
}
static Agnode_t*
bind_node(const char *name)
{
N = agnode(G,(char*)name,1);
return N;
}
static Agedge_t*
bind_edge(const char *tail, const char *head)
{
Agnode_t *tailNode, *headNode;
char* key = 0;
tailNode = agnode(G, (char*)tail,1);
headNode = agnode(G, (char*)head,1);
E = agedge(tailNode, headNode,key,1);
return E;
}
static int
get_xml_attr(char *attrname, const char **atts)
{
int count = 0;
while(atts[count] != NULL) {
if(strcmp(attrname, atts[count]) == 0) {
return count + 1;
}
count += 2;
}
return -1;
}
static void
setName (Dt_t* names, Agobj_t* n, char* value)
{
Agsym_t* ap;
char* oldName;
ap = agattr(root, AGTYPE(n), GXL_ID, "");
agxset(n,ap,agnameof(n));
oldName = agxget(n,ap);
addToMap(names, oldName, value);
agrename(n, value);
}
static char* defval = "";
static void
setNodeAttr (Agnode_t* np, char *name, char *value, userdata_t* ud)
{
Agsym_t* ap;
if(strcmp(name, "name") == 0) {
setName (ud->nameMap, (Agobj_t*)np, value);
}
else {
ap = agattr(root,AGNODE,name,0);
if (!ap)
ap = agattr(root,AGNODE,name,defval);
agxset(np,ap,value);
}
}
#define NODELBL "node:"
#define NLBLLEN (sizeof(NODELBL)-1)
#define EDGELBL "edge:"
#define ELBLLEN (sizeof(EDGELBL)-1)
static void
setGlobalNodeAttr (Agraph_t* g, char *name, char *value, userdata_t* ud)
{
if (strncmp(name,NODELBL,NLBLLEN))
fprintf (stderr, "Warning: global node attribute %s in graph %s does not begin with the prefix %s\n", name, agnameof(g), NODELBL);
else
name += NLBLLEN;
if ((g != root) && !agattr(root,AGNODE,name,0))
agattr(root,AGNODE,name,defval);
agattr(G, AGNODE, name, value);
}
static void
setEdgeAttr (Agedge_t* ep, char *name, char *value, userdata_t* ud)
{
Agsym_t* ap;
char* attrname;
if(strcmp(name, "headport") == 0) {
if(ud->edgeinverted) attrname = "tailport";
else attrname = "headport";
ap = agattr(root,AGEDGE,attrname,0);
if (!ap)
ap = agattr(root,AGEDGE,attrname,defval);
agxset(ep,ap,value);
} else if(strcmp(name, "tailport") == 0) {
if(ud->edgeinverted) attrname = "headport";
else attrname = "tailport";
ap = agattr(root,AGEDGE,attrname,0);
if (!ap)
ap = agattr(root,AGEDGE,attrname,defval);
agxset(ep,ap,value);
} else {
ap = agattr(root,AGEDGE,name,0);
if (!ap)
ap = agattr(root,AGEDGE,name,defval);
agxset(ep,ap,value);
}
}
static void
setGlobalEdgeAttr (Agraph_t* g, char *name, char *value, userdata_t* ud)
{
if (strncmp(name,EDGELBL,ELBLLEN))
fprintf (stderr, "Warning: global edge attribute %s in graph %s does not begin with the prefix %s\n", name, agnameof(g), EDGELBL);
else
name += ELBLLEN;
if ((g != root) && !agattr(root,AGEDGE,name,0))
agattr(root,AGEDGE,name,defval);
agattr(g, AGEDGE, name, value);
}
static void
setGraphAttr (Agraph_t* g, char *name, char *value, userdata_t* ud)
{
Agsym_t* ap;
if ((g == root) && !strcmp(name,"strict") && !strcmp(value,"true")){
g->desc.strict = 1;
}
else if (strcmp(name, "name") == 0)
setName (ud->nameMap, (Agobj_t *)g, value);
else {
ap = agattr(root,AGRAPH,name,0);
if (ap)
agxset(g,ap,value);
else if (g == root)
agattr(root,AGRAPH,name,value);
else {
ap = agattr(root,AGRAPH,name,defval);
agxset(g,ap,value);
}
}
}
static void
setAttr (char *name, char *value, userdata_t* ud)
{
switch (Current_class) {
case TAG_GRAPH :
setGraphAttr (G, name, value, ud);
break;
case TAG_NODE :
setNodeAttr (N, name, value, ud);
break;
case TAG_EDGE :
setEdgeAttr (E, name, value, ud);
break;
}
}
static void
startElementHandler(void *userData, const char *name, const char **atts)
{
int pos;
userdata_t* ud = (userdata_t*)userData;
Agraph_t *g = NULL;
if(strcmp(name, "gxl") == 0) {
} else if(strcmp(name, "graph") == 0) {
const char *edgeMode="";
const char *id;
char buf[NAMEBUF];
Current_class = TAG_GRAPH;
if(ud->closedElementType == TAG_GRAPH) {
fprintf(stderr, "Warning: Node contains more than one graph.\n");
}
id = atts[get_xml_attr("id", atts)];
pos = get_xml_attr("edgemode", atts);
if(pos > 0) {
edgeMode = atts[pos];
}
if(GSP == 0) {
if(strcmp(edgeMode, "directed") == 0) {
g = agopen((char*)id,Agdirected,&AgDefaultDisc);
} else if(strcmp(edgeMode, "undirected") == 0) {
g = agopen((char*)id,Agundirected,&AgDefaultDisc);
}
else {
fprintf(stderr, "Warning: graph has no edgemode attribute");
fprintf(stderr, " - assume directed\n");
g = agopen((char*)id,Agdirected,&AgDefaultDisc);
}
push_subg(g);
} else {
Agraph_t* subg;
if(isAnonGraph((char*)id)) {
static int anon_id = 1;
sprintf(buf,"%%%d", anon_id++);
id = buf;
}
subg = agsubg(G,(char*)id,1);
push_subg(subg);
}
pos = get_xml_attr("role", atts);
if(pos > 0) {
setGraphAttr(G, GXL_ROLE, (char*)atts[pos], ud);
}
pos = get_xml_attr("hypergraph", atts);
if(pos > 0) {
setGraphAttr (G, GXL_HYPER, (char*)atts[pos], ud);
}
pushString (&ud->elements, id);
} else if(strcmp(name, "node") == 0) {
Current_class = TAG_NODE;
pos = get_xml_attr("id", atts);
if(pos > 0) {
const char *attrname;
attrname = atts[pos];
bind_node(attrname);
pushString (&ud->elements, attrname);
}
} else if(strcmp(name, "edge") == 0) {
const char *head="", *tail="";
char *tname;
Agnode_t *t;
Current_class = TAG_EDGE;
pos = get_xml_attr("from", atts);
if(pos > 0)
tail = atts[pos];
pos = get_xml_attr("to", atts);
if(pos > 0)
head = atts[pos];
tname = mapLookup(ud->nameMap, (char*)tail);
if (tname) tail = tname;
tname = mapLookup(ud->nameMap, (char*)head);
if (tname) head = tname;
bind_edge(tail, head);
t = AGTAIL(E);
tname = agnameof(t);
if(strcmp(tname, tail) == 0) {
ud->edgeinverted = FALSE;
} else if(strcmp(tname, head) == 0){
ud->edgeinverted = TRUE;
}
pos = get_xml_attr("fromorder", atts);
if(pos > 0) {
setEdgeAttr(E, GXL_FROM, (char*)atts[pos], ud);
}
pos = get_xml_attr("toorder", atts);
if(pos > 0) {
setEdgeAttr(E, GXL_TO, (char*)atts[pos], ud);
}
pos = get_xml_attr("id", atts);
if(pos > 0) {
setEdgeAttr(E, GXL_ID, (char*)atts[pos], ud);
}
} else if(strcmp(name, "attr") == 0) {
const char *attrname = atts[get_xml_attr("name", atts)];
agxbput (&ud->xml_attr_name, (char*)attrname);
pos = get_xml_attr("kind", atts);
if(pos > 0) {
if(strcmp("node", atts[pos]) == 0)
ud->globalAttrType = TAG_NODE;
else if(strcmp("edge", atts[pos]) == 0)
ud->globalAttrType = TAG_EDGE;
else if(strcmp("graph", atts[pos]) == 0)
ud->globalAttrType = TAG_GRAPH;
} else {
ud->globalAttrType = TAG_NONE;
}
} else if(strcmp(name, "string") == 0
|| strcmp(name, "bool") == 0
|| strcmp(name, "int") == 0
|| strcmp(name, "float") == 0) {
ud->listen = TRUE;
if(ud->compositeReadState) {
agxbputc (&ud->composite_buffer, '<');
agxbput (&ud->composite_buffer, (char*)name);
agxbputc (&ud->composite_buffer, '>');
}
} else if(strcmp(name, "rel") == 0
|| strcmp(name, "relend") == 0) {
fprintf(stderr, "%s element is ignored by DOT\n", name);
} else if(strcmp(name, "type") == 0) {
pos = get_xml_attr("xlink:href", atts);
if(pos > 0) {
setAttr(GXL_TYPE, (char*)atts[pos], ud);
}
} else if(strcmp(name, "locator") == 0) {
pos = get_xml_attr("xlink:href", atts);
if(pos > 0) {
const char *href = atts[pos];
agxbput (&ud->xml_attr_value, GXL_LOC);
agxbput (&ud->xml_attr_value, (char*)href);
}
} else if(strcmp(name, "seq") == 0
|| strcmp(name, "set") == 0
|| strcmp(name, "bag") == 0
|| strcmp(name, "tup") == 0
|| strcmp(name, "enum") == 0 ) {
ud->compositeReadState = TRUE;
agxbputc (&ud->composite_buffer, '<');
agxbput (&ud->composite_buffer, (char*)name);
agxbputc (&ud->composite_buffer, '>');
} else {
fprintf(stderr, "Unknown node %s; DOT does not support extensions.\n", name);
}
}
static void
endElementHandler(void *userData, const char *name)
{
userdata_t* ud = (userdata_t*)userData;
if(strcmp(name, "graph") == 0) {
pop_subg();
popString (&ud->elements);
ud->closedElementType = TAG_GRAPH;
} else if(strcmp(name, "node") == 0) {
char* ele_name = topString (ud->elements);
if(ud->closedElementType == TAG_GRAPH) {
Agnode_t *node = agnode(root, ele_name, 0);
agdelete(root, node);
}
popString (&ud->elements);
Current_class = TAG_GRAPH;
N = 0;
ud->closedElementType = TAG_NODE;
} else if(strcmp(name, "edge") == 0) {
Current_class = TAG_GRAPH;
E = 0;
ud->closedElementType = TAG_EDGE;
ud->edgeinverted = FALSE;
} else if(strcmp(name, "attr") == 0) {
char* name;
char* value;
char buf[SMALLBUF] = GXL_COMP;
char* dynbuf = 0;
ud->closedElementType = TAG_NONE;
if(ud->compositeReadState) {
int len = sizeof(GXL_COMP)+agxblen(&ud->xml_attr_name);
if (len <= SMALLBUF) {
name = buf;
}
else {
name = dynbuf = N_NEW(len, char);
strcpy(name,GXL_COMP);
}
strcpy (name+sizeof(GXL_COMP)-1, agxbuse(&ud->xml_attr_name));
value = agxbuse(&ud->composite_buffer);
agxbclear(&ud->xml_attr_value);
ud->compositeReadState = FALSE;
}
else {
name = agxbuse(&ud->xml_attr_name);
value = agxbuse(&ud->xml_attr_value);
}
switch(ud->globalAttrType) {
case TAG_NONE:
setAttr (name, value, ud);
break;
case TAG_NODE:
setGlobalNodeAttr (G, name, value, ud);
break;
case TAG_EDGE:
setGlobalEdgeAttr (G, name, value, ud);
break;
case TAG_GRAPH:
setGraphAttr (G, name, value, ud);
break;
}
if (dynbuf) free (dynbuf);
ud->globalAttrType = TAG_NONE;
} else if(strcmp(name, "string") == 0
|| strcmp(name, "bool") == 0
|| strcmp(name, "int") == 0
|| strcmp(name, "float") == 0) {
ud->listen = FALSE;
if(ud->compositeReadState) {
agxbputc (&ud->composite_buffer, '<');
agxbputc (&ud->composite_buffer, '/');
agxbput (&ud->composite_buffer, (char*)name);
agxbputc (&ud->composite_buffer, '>');
}
} else if(strcmp(name, "seq") == 0
|| strcmp(name, "set") == 0
|| strcmp(name, "bag") == 0
|| strcmp(name, "tup") == 0
|| strcmp(name, "enum") == 0 ) {
agxbputc (&ud->composite_buffer, '<');
agxbputc (&ud->composite_buffer, '/');
agxbput (&ud->composite_buffer, (char*)name);
agxbputc (&ud->composite_buffer, '>');
}
}
static void
characterDataHandler(void *userData, const char *s, int length)
{
userdata_t* ud = (userdata_t*)userData;
if(!ud->listen)
return;
if(ud->compositeReadState) {
agxbput_n(&ud->composite_buffer, (char*)s, length);
return;
}
agxbput_n(&ud->xml_attr_value, (char*)s, length);
}
Agraph_t*
gxl_to_dot(FILE* gxlFile)
{
char buf[BUFSIZE];
int done;
userdata_t* udata = genUserdata();
XML_Parser parser = XML_ParserCreate(NULL);
XML_SetUserData(parser, udata);
XML_SetElementHandler(parser, startElementHandler, endElementHandler);
XML_SetCharacterDataHandler(parser, characterDataHandler);
Current_class = TAG_GRAPH;
root = 0;
do {
size_t len = fread(buf, 1, sizeof(buf), gxlFile);
if (len == 0) break;
done = len < sizeof(buf);
if (XML_Parse(parser, buf, len, done) == XML_STATUS_ERROR) {
fprintf(stderr,
"%s at line %d\n",
XML_ErrorString(XML_GetErrorCode(parser)),
XML_GetCurrentLineNumber(parser));
exit(1);
}
} while (!done);
XML_ParserFree(parser);
freeUserdata(udata);
return root;
}
#endif