%{
/*
This software may only be used by you under license from AT&T Corp.
("AT&T"). A copy of AT&T's Source Code Agreement is available at
AT&T's Internet website having the URL:
<http://www.research.att.com/sw/tools/graphviz/license/source.html>
If you received this software without first entering into a license
with AT&T, you have an infringing copy of this software and cannot use
it without violating AT&T's intellectual property rights.
*/
#pragma prototyped
#include <stdio.h> /* SAFE */
#include <aghdr.h> /* SAFE */
#ifdef _WIN32
#define gettxt(a,b) (b)
#endif
static char Key[] = "key";
typedef union s { /* possible items in generic list */
Agnode_t *n;
Agraph_t *subg;
Agedge_t *e;
Agsym_t *asym; /* bound attribute */
char *name; /* unbound attribute */
struct item_s *list; /* list-of-lists (for edgestmt) */
} val_t;
typedef struct item_s { /* generic list */
int tag; /* T_node, T_subgraph, T_edge, T_attr */
val_t u; /* primary element */
char *str; /* secondary value - port or attr value */
struct item_s *next;
} item;
typedef struct list_s { /* maintain head and tail ptrs for fast append */
item *first;
item *last;
} list_t;
/* functions */
static void appendnode(char *name, char *port);
static void attrstmt(int tkind, char *macroname);
static void startgraph(char *name, int directed, int strict);
static void bufferedges(void);
static void newedge(Agnode_t *t, char *tport, Agnode_t *h, char *hport, char *key);
static void edgerhs(Agnode_t *n, char *tport, item *hlist, char *key);
static void appendattr(char *name, char *value);
static void bindattrs(int kind);
static void applyattrs(void *obj);
static void endgraph(void);
static void endnode(void);
static void endedge(void);
static char* concat(char*, char*);
static void opensubg(char *name);
static void closesubg(void);
/* global */
static Agraph_t *G;
%}
%union {
int i;
char *str;
struct Agnode_s *n;
}
%token <i> T_graph T_node T_edge T_digraph T_subgraph T_strict T_edgeop
/* T_list, T_attr are internal tags, not really tokens */
%token T_list T_attr
%token <str> T_atom T_qatom
%type <i> optstrict graphtype rcompound attrtype
%type <str> optsubghdr optgraphname optmacroname optport atom qatom
%%
graph : hdr body {endgraph();}
| error {if (G) {agclose(G); G = Ag_G_global = NIL(Agraph_t*);}}
| /* empty */
;
body : '{' optstmtlist '}' ;
hdr : optstrict graphtype optgraphname {startgraph($3,$2,$1);}
;
optgraphname: atom {$$=$1;} | /* empty */ {$$=0;} ;
optstrict : T_strict {$$=1;} | /* empty */ {$$=0;} ;
graphtype : T_graph {$$ = 0;} | T_digraph {$$ = 1;} ;
optstmtlist : stmtlist | /* empty */ ;
stmtlist : stmtlist stmt | stmt ;
optsemi : ';' | ;
stmt : attrstmt optsemi
| compound optsemi
;
compound : simple rcompound optattr
{if ($2) endedge(); else endnode();}
;
simple : nodelist | subgraph ;
rcompound : T_edgeop {bufferedges();} simple rcompound {$$ = 1;}
| /* empty */ {$$ = 0;}
;
nodelist : node | nodelist ',' node ;
node : atom optport {appendnode($1,$2);}
;
optport : ':' atom {$$ = $2;} /* ignore port IDs */
| {$$ = NIL(char*);}
;
attrstmt : attrtype optmacroname attrlist {attrstmt($1,$2);}
| graphattrdefs {attrstmt(T_graph,NIL(char*));}
;
attrtype : T_graph {$$ = T_graph;}
| T_node {$$ = T_node;}
| T_edge {$$ = T_edge;}
;
optmacroname : atom '=' {$$ = $1;}
| /* empty */ {$$ = NIL(char*); }
;
optattr : attrlist | /* empty */ ;
attrlist : optattr '[' optattrdefs ']' ;
optattrdefs : optattrdefs attrdefs
| /* empty */ ;
attrdefs : attritem optseparator
;
attritem : attrassignment | attrmacro ;
attrassignment : atom '=' atom {appendattr($1,$3);}
;
attrmacro : '@' atom {appendattr($2,NIL(char*));} /* not yet impl */
;
graphattrdefs : attrassignment
;
subgraph : optsubghdr {opensubg($1);} body {closesubg();}
;
optsubghdr : T_subgraph atom {$$=$2;}
| T_subgraph {$$=NIL(char*);}
| /* empty */ {$$=NIL(char*);}
;
optseparator : ';' | ',' | /*empty*/ ;
atom : T_atom {$$ = $1;}
| qatom {$$ = $1;}
;
qatom : T_qatom {$$ = $1;}
| qatom '+' T_qatom
{$$ = concat($1,$3); agstrfree(G,$1); agstrfree(G,$3);}
;
%%
#define NILitem NIL(item*)
/* globals */
static Agraph_t *Subgraph; /* most recent subgraph that was opened */
static Agdisc_t *Disc; /* discipline passed to agread or agconcat */
static list_t Nodelist,Edgelist,Attrlist;
static item *newitem(int tag, void *p0, char *p1)
{
item *rv = agalloc(G,sizeof(item));
rv->tag = tag; rv->u.name = (char*)p0; rv->str = p1;
return rv;
}
static item *cons_node(Agnode_t *n, char *port)
{ return newitem(T_node,n,port); }
static item *cons_attr(char *name, char *value)
{ return newitem(T_atom,name,value); }
static item *cons_list(item *list)
{ return newitem(T_list,list,NIL(char*)); }
static item *cons_subg(Agraph_t *subg)
{ return newitem(T_subgraph,subg,NIL(char*)); }
#ifdef NOTDEF
static item *cons_edge(Agedge_t *e)
{ return newitem(T_edge,e,NIL(char*)); }
#endif
static void delete_items(item *ilist)
{
item *p,*pn;
for (p = ilist; p; p = pn) {
pn = p->next;
switch(p->tag) {
case T_list: delete_items(p->u.list); break;
case T_atom: case T_attr: agstrfree(G,p->str); break;
}
agfree(G,p);
}
}
static void deletelist(list_t *list)
{
delete_items(list->first);
list->first = list->last = NILitem;
}
#ifdef NOTDEF
static void listins(list_t *list, item *v)
{
v->next = list->first;
list->first = v;
if (list->last == NILitem) list->last = v;
}
#endif
static void listapp(list_t *list, item *v)
{
if (list->last) list->last->next = v;
list->last = v;
if (list->first == NILitem) list->first = v;
}
/* attrs */
static void appendattr(char *name, char *value)
{
item *v;
assert(value != NIL(char*));
v = cons_attr(name,value);
listapp(&Attrlist,v);
}
static void bindattrs(int kind)
{
item *aptr;
char *name;
for (aptr = Attrlist.first; aptr; aptr = aptr->next) {
assert(aptr->tag == T_atom); /* signifies unbound attr */
name = aptr->u.name;
if ((kind == AGEDGE) && streq(name,Key)) continue;
if ((aptr->u.asym = agattr(G,kind,name,NIL(char*))) == NILsym)
aptr->u.asym = agattr(G,kind,name,"");
aptr->tag = T_attr; /* signifies bound attr */
agstrfree(G,name);
}
}
static void applyattrs(void *obj)
{
item *aptr;
for (aptr = Attrlist.first; aptr; aptr = aptr->next) {
if (aptr->tag == T_attr) {
if (aptr->u.asym) {
agxset(obj,aptr->u.asym,aptr->str);
}
}
else {
assert(AGTYPE(obj) == AGEDGE);
assert(aptr->tag == T_atom);
assert(streq(aptr->u.name,Key));
}
}
}
static void nomacros(void)
{
agerror(AGERROR_UNIMPL,"attribute macros");
}
static void attrstmt(int tkind, char *macroname)
{
item *aptr;
int kind;
/* creating a macro def */
if (macroname) nomacros();
/* invoking a macro def */
for (aptr = Attrlist.first; aptr; aptr = aptr->next)
if (aptr->str == NIL(char*)) nomacros();
switch(tkind) {
case T_graph: kind = AGRAPH; break;
case T_node: kind = AGNODE; break;
case T_edge: kind = AGEDGE; break;
default : abort();
}
bindattrs(kind); /* set up defaults for new attributes */
for (aptr = Attrlist.first; aptr; aptr = aptr->next)
agattr(G,kind,aptr->u.asym->name,aptr->str);
deletelist(&Attrlist);
}
/* nodes */
static void appendnode(char *name, char *port)
{
item *elt;
elt = cons_node(agnode(G,name,TRUE),port);
listapp(&Nodelist,elt);
agstrfree(G,name);
}
/* apply current optional attrs to Nodelist and clean up lists */
static void endnode()
{
item *ptr;
bindattrs(AGNODE);
for (ptr = Nodelist.first; ptr; ptr = ptr->next)
applyattrs(ptr->u.n);
deletelist(&Nodelist);
deletelist(&Attrlist);
}
/* edges - store up node/subg lists until optional edge key can be seen */
static void bufferedges()
{
item *v;
if (Nodelist.first) {
v = cons_list(Nodelist.first);
Nodelist.first = Nodelist.last = NILitem;
}
else {v = cons_subg(Subgraph); Subgraph = NIL(Agraph_t*);}
listapp(&Edgelist,v);
}
static void endedge(void)
{
char *key;
item *aptr,*tptr,*p;
Agnode_t *t;
Agraph_t *subg;
bufferedges(); /* pick up the terminal nodelist or subg */
bindattrs(AGEDGE);
/* look for "key" pseudo-attribute */
key = NIL(char*);
for (aptr = Attrlist.first; aptr; aptr = aptr->next) {
if ((aptr->tag == T_atom) && streq(aptr->u.name,Key))
key = aptr->str;
}
/* can make edges with node lists or subgraphs */
for (p = Edgelist.first; p->next; p = p->next) {
if (p->tag == T_subgraph) {
subg = p->u.subg;
for (t = agfstnode(subg); t; t = agnxtnode(t))
edgerhs(agsubnode(G,t,FALSE),NIL(char*),p->next,key);
}
else {
for (tptr = p->u.list; tptr; tptr = tptr->next)
edgerhs(tptr->u.n,tptr->str,p->next,key);
}
}
deletelist(&Edgelist);
deletelist(&Attrlist);
}
/* concat:
*/
static char*
concat (char* s1, char* s2)
{
char* s;
char buf[BUFSIZ];
char* sym;
int len = strlen(s1) + strlen(s2) + 1;
if (len <= BUFSIZ) sym = buf;
else sym = (char*)malloc(len);
strcpy(sym,s1);
strcat(sym,s2);
s = agstrdup (G,sym);
agstrfree (G,s1);
agstrfree (G,s2);
if (sym != buf) free (sym);
return s;
}
static void edgerhs(Agnode_t *tail, char *tport, item *hlist, char *key)
{
Agnode_t *head;
Agraph_t *subg;
item *hptr;
if (hlist->tag == T_subgraph) {
subg = hlist->u.subg;
for (head = agfstnode(subg); head; head = agnxtnode(head))
newedge(tail,tport,agsubnode(G,head,FALSE),NIL(char*),key);
}
else {
for (hptr = hlist->u.list; hptr; hptr = hptr->next)
newedge(tail,tport,agsubnode(G,hptr->u.n,FALSE),hptr->str,key);
}
}
static void mkport(Agedge_t *e, char *name, char *val)
{
Agsym_t *attr;
if (val) {
if ((attr = agattr(G,AGEDGE,name,NIL(char*))) == NILsym)
attr = agattr(G,AGEDGE,name,"");
agxset(e,attr,val);
}
}
static void newedge(Agnode_t *t, char *tport, Agnode_t *h, char *hport, char *key)
{
Agedge_t *e;
e = agedge(t,h,key,TRUE);
if (e) { /* can fail if graph is strict and t==h */
char *tp = tport;
char *hp = hport;
if ((agtail(e) != aghead(e)) && (aghead(e) == t)) {
/* could happen with an undirected edge */
char *temp;
temp = tp; tp = hp; hp = temp;
}
mkport(e,"tailport",tp);
mkport(e,"headport",hp);
applyattrs(e);
}
}
/* graphs and subgraphs */
static void startgraph(char *name, int directed, int strict)
{
static Agdesc_t req; /* get rid of warnings */
if (G == NILgraph) {
req.directed = directed;
req.strict = strict;
req.flatlock = FALSE;
req.maingraph = TRUE;
Ag_G_global = G = agopen(name,req,Disc);
}
else {
Ag_G_global = G;
}
agstrfree(NIL(Agraph_t*),name);
}
static void endgraph()
{
aglexeof();
aginternalmapclearlocalnames(G);
}
static void opensubg(char *name)
{
G = agsubg(G,name,TRUE);
agstrfree(G,name);
}
static void closesubg()
{
Subgraph = G;
if ((G = agparent(G)) == NIL(Agraph_t*))
yyerror("libgraph: parser lost root graph\n");
}
extern void *yyin;
Agraph_t *agconcat(Agraph_t *g, void *chan, Agdisc_t *disc)
{
yyin = chan;
G = g;
Ag_G_global = NILgraph;
Disc = (disc? disc : &AgDefaultDisc);
aglexinit(Disc, chan);
yyparse();
return Ag_G_global;
}
Agraph_t *agread(void *fp, Agdisc_t *disc) {return agconcat(NILgraph,fp,disc); }