/**
 * @file
 * @ingroup cgraph_core
 */
/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/

%require "3.0"

  /* By default, Bison emits a parser using symbols prefixed with "yy". Graphviz
   * contains multiple Bison-generated parsers, so we alter this prefix to avoid
   * symbol clashes.
   */
%define api.prefix {aag}

  /* Generate a reentrant parser with no global state. */
%define api.pure full
  /* aagparse() gets an argument defined by flex. */
%param { aagscan_t scanner }


%code requires {
#include <cghdr.h>
#include <util/agxbuf.h>

struct gstack_s;

struct aagextra_s {
	/* Common */
	Agdisc_t *Disc;		/* discipline passed to agread or agconcat */
	void *Ifile;
	Agraph_t *G;		/* top level graph */
	/* Parser */
	int SubgraphDepth;
	struct gstack_s *S;
	/* Lexer */
	int line_num; // = 1;
	int html_nest;  /* nesting level for html strings */
	const char *InputFile;
	agxbuf InputFileBuffer;
	int graphType;
	/* buffer for arbitrary length strings */
	agxbuf Sbuf;
};

}

%code provides {
	/* defined in/generated by scan.l */
	void aagerror(aagscan_t, const char*);
	int aaglex(AAGSTYPE *, aagscan_t);
}

%{

#include <stdbool.h>
#include <stdio.h>
#include <cghdr.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/streq.h>
#include <util/unreachable.h>

static const 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;

typedef struct gstack_s {
	Agraph_t *g;
	Agraph_t *subg;
	list_t	nodelist,edgelist,attrlist;
	struct gstack_s *down;
} gstack_t;

/* functions */
static void appendnode(aagscan_t scanner, char *name, char *port, char *sport);
static void attrstmt(aagscan_t scanner, int tkind, char *macroname);
static void startgraph(aagscan_t scanner, char *name, bool directed, bool strict);
static void getedgeitems(aagscan_t scanner);
static void newedge(aagscan_t scanner, Agnode_t *t, char *tport, Agnode_t *h, char *hport, char *key);
static void edgerhs(aagscan_t scanner, Agnode_t *n, char *tport, item *hlist, char *key);
static void appendattr(aagscan_t scanner, char *name, char *value);
static void bindattrs(aagextra_t *ctx, int kind);
static void applyattrs(aagextra_t *ctx, void *obj);
static void endgraph(aagscan_t scanner);
static void endnode(aagscan_t scanner);
static void endedge(aagscan_t scanner);
static void freestack(aagscan_t scanner);
static char* concat(aagscan_t scanner, char*, char*);
static char* concatPort(Agraph_t *G, char*, char*);

static void opensubg(aagscan_t scanner, char *name);
static void closesubg(aagscan_t scanner);
static void graph_error(aagscan_t scanner);

%}

%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 atom qatom


%%

graph		:  hdr body {freestack(scanner); endgraph(scanner);}
			|  error	{graph_error(scanner);}
			|  /* empty */
			;

body		: '{' optstmtlist '}' ;

hdr			:	optstrict graphtype optgraphname {startgraph(scanner,$3,$2 != 0,$1 != 0);}
			;

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(scanner); else endnode(scanner);}
			;

simple		:	nodelist | subgraph ;

rcompound	:	T_edgeop {getedgeitems(scanner);} simple {getedgeitems(scanner);} rcompound {$$ = 1;}
			|	/* empty */ {$$ = 0;}
			;


nodelist	: node | nodelist ',' node ;

node		: atom {appendnode(scanner,$1,NULL,NULL);}
            | atom ':' atom {appendnode(scanner,$1,$3,NULL);}
            | atom ':' atom ':' atom {appendnode(scanner,$1,$3,$5);}
            ;

attrstmt	:  attrtype optmacroname attrlist {attrstmt(scanner,$1,$2);}
			|  graphattrdefs {attrstmt(scanner,T_graph,NULL);}
			;

attrtype :	T_graph {$$ = T_graph;}
			| T_node {$$ = T_node;}
			| T_edge {$$ = T_edge;}
			;

optmacroname : atom '=' {$$ = $1;}
			| /* empty */ {$$ = NULL; }
			;

optattr		:	attrlist |  /* empty */ ;

attrlist	: optattr '[' optattrdefs ']' ;

optattrdefs	: optattrdefs attrdefs 
			| /* empty */ ;

attrdefs	:  attrassignment optseparator
			;

attrassignment	:  atom '=' atom {appendattr(scanner,$1,$3);}
			;

graphattrdefs : attrassignment
			;

subgraph	:  optsubghdr {opensubg(scanner,$1);} body {closesubg(scanner);}
			;

optsubghdr	: T_subgraph atom {$$=$2;}
			| T_subgraph  {$$=NULL;}
			| /* empty */ {$$=NULL;}
			;

optseparator :  ';' | ',' | /*empty*/ ;

atom	:  T_atom {$$ = $1;}
			|  qatom {$$ = $1;}
			;

qatom	:  T_qatom {$$ = $1;}
			|  qatom '+' T_qatom {$$ = concat(scanner, $1,$3);}
			;
%%

static item *newitem(int tag, void *p0, char *p1)
{
	item *rv = gv_alloc(sizeof(item));
	rv->tag = tag;
	rv->u.name = 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,NULL); }

static item *cons_subg(Agraph_t *subg)
	{ return newitem(T_subgraph,subg,NULL); }

static gstack_t *push(gstack_t *s, Agraph_t *subg) {
	gstack_t *rv = gv_alloc(sizeof(gstack_t));
	rv->down = s;
	rv->g = subg;
	return rv;
}

static gstack_t *pop(gstack_t *s)
{
	gstack_t *rv;
	rv = s->down;
	free(s);
	return rv;
}

static void delete_items(Agraph_t *G, item *ilist)
{
	item	*p,*pn;

	for (p = ilist; p; p = pn) {
		pn = p->next;
		if (p->tag == T_list) delete_items(G, p->u.list);
		if (p->tag == T_atom) agstrfree(G, p->str, aghtmlstr(p->str));
		free(p);
	}
}

static void deletelist(Agraph_t *G, list_t *list)
{
	delete_items(G,list->first);
	list->first = list->last = NULL;
}

static void listapp(list_t *list, item *v)
{
	if (list->last) list->last->next = v;
	list->last = v;
	if (list->first == NULL) list->first = v;
}


/* attrs */
static void appendattr(aagscan_t scanner, char *name, char *value)
{
	item		*v;
	aagextra_t 	*ctx = aagget_extra(scanner);

	assert(value != NULL);
	v = cons_attr(name,value);
	listapp(&ctx->S->attrlist, v);
}

static void bindattrs(aagextra_t *ctx, int kind)
{
	item		*aptr;
	char		*name;

	for (aptr = ctx->S->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_text(ctx->S->g,kind,name,NULL)) == NULL)
			aptr->u.asym = agattr_text(ctx->S->g,kind,name,"");
		aptr->tag = T_attr;				/* signifies bound attr */
		agstrfree(ctx->G, name, false);
	}
}

/* attach node/edge specific attributes */
static void applyattrs(aagextra_t *ctx, void *obj)
{
	item		*aptr;

	for (aptr = ctx->S->attrlist.first; aptr; aptr = aptr->next) {
		if (aptr->tag == T_attr) {
			if (aptr->u.asym) {
				if (aghtmlstr(aptr->str)) {
				  agxset_html(obj, aptr->u.asym, aptr->str);
				} else {
				  agxset(obj, aptr->u.asym, aptr->str);
				}
			}
		}
		else {
			assert(AGTYPE(obj) == AGINEDGE || AGTYPE(obj) == AGOUTEDGE);
			assert(aptr->tag == T_atom);
			assert(streq(aptr->u.name,Key));
		}
	}
}

static void nomacros(void)
{
  agwarningf("attribute macros not implemented");
}

/* attrstmt:
 * First argument is always attrtype, so switch covers all cases.
 * This function is used to handle default attribute value assignment.
 */
static void attrstmt(aagscan_t scanner, int tkind, char *macroname)
{
	item			*aptr;
	int				kind = 0;
	aagextra_t 		*ctx = aagget_extra(scanner);
	Agsym_t*  sym;
	Agraph_t *G = ctx->G;
	gstack_t *S = ctx->S;

		/* creating a macro def */
	if (macroname) nomacros();
		/* invoking a macro def */
	for (aptr = S->attrlist.first; aptr; aptr = aptr->next)
		if (aptr->str == NULL) nomacros();

	switch(tkind) {
		case T_graph: kind = AGRAPH; break;
		case T_node: kind = AGNODE; break;
		case T_edge: kind = AGEDGE; break;
		default: UNREACHABLE();
	}
	bindattrs(ctx, kind);	/* set up defaults for new attributes */
	for (aptr = S->attrlist.first; aptr; aptr = aptr->next) {
		/* If the tag is still T_atom, aptr->u.asym has not been set */
		if (aptr->tag == T_atom) continue;
		if (!aptr->u.asym->fixed || S->g != G) {
			if (aghtmlstr(aptr->str)) {
			  sym = agattr_html(S->g, kind, aptr->u.asym->name, aptr->str);
			} else {
			  sym = agattr_text(S->g, kind, aptr->u.asym->name, aptr->str);
			}
		} else
			sym = aptr->u.asym;
		if (S->g == G)
			sym->print = true;
	}
	deletelist(G, &S->attrlist);
}

/* nodes */

static void appendnode(aagscan_t scanner, char *name, char *port, char *sport)
{
	item		*elt;
	aagextra_t 	*ctx = aagget_extra(scanner);
	Agraph_t *G = ctx->G;
	gstack_t *S = ctx->S;

	if (sport) {
		port = concatPort (G, port, sport);
	}
	elt = cons_node(agnode(S->g, name, 1), port);
	listapp(&S->nodelist, elt);
	agstrfree(G, name, false);
}

/* apply current optional attrs to nodelist and clean up lists */
/* what's bad is that this could also be endsubg.  also, you can't
clean up S->subg in closesubg() because S->subg might be needed
to construct edges.  these are the sort of notes you write to yourself
in the future. */
static void endnode(aagscan_t scanner)
{
	item	*ptr;
	aagextra_t 	*ctx = aagget_extra(scanner);
	Agraph_t *G = ctx->G;
	gstack_t *S = ctx->S;

	bindattrs(ctx, AGNODE);
	for (ptr = S->nodelist.first; ptr; ptr = ptr->next)
		applyattrs(ctx, ptr->u.n);
	deletelist(G, &S->nodelist);
	deletelist(G, &S->attrlist);
	deletelist(G, &S->edgelist);
	S->subg = 0;  /* notice a pattern here? :-( */
}

/* edges - store up node/subg lists until optional edge key can be seen */

static void getedgeitems(aagscan_t scanner)
{
	aagextra_t *ctx = aagget_extra(scanner);;
	gstack_t *S = ctx->S;
	item	*v = 0;

	if (S->nodelist.first) {
		v = cons_list(S->nodelist.first);
		S->nodelist.first = S->nodelist.last = NULL;
	}
	else {if (S->subg) v = cons_subg(S->subg); S->subg = 0;}
	/* else nil append */
	if (v) listapp(&S->edgelist, v);
}

static void endedge(aagscan_t scanner)
{
	char			*key;
	item			*aptr,*tptr,*p;

	Agnode_t		*t;
	Agraph_t		*subg;
	aagextra_t 		*ctx = aagget_extra(scanner);
	Agraph_t 		*G = ctx->G;

	bindattrs(ctx, AGEDGE);

	/* look for "key" pseudo-attribute */
	key = NULL;
	for (aptr = ctx->S->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 = ctx->S->edgelist.first; p->next; p = p->next) {
		if (p->tag == T_subgraph) {
			subg = p->u.subg;
			for (t = agfstnode(subg); t; t = agnxtnode(subg,t))
				edgerhs(scanner,agsubnode(ctx->S->g, t, 0), NULL, p->next, key);
		}
		else {
			for (tptr = p->u.list; tptr; tptr = tptr->next)
				edgerhs(scanner,tptr->u.n,tptr->str,p->next,key);
		}
	}
	deletelist(G, &ctx->S->nodelist);
	deletelist(G, &ctx->S->edgelist);
	deletelist(G, &ctx->S->attrlist);
	ctx->S->subg = 0;
}

/* concat:
 */
static char*
concat (aagscan_t scanner, char* s1, char* s2)
{
  agxbuf buf = {0};
  Agraph_t *G = aagget_extra(scanner)->G;

  agxbprint(&buf, "%s%s", s1, s2);
  char *const s = agstrdup(G, agxbuse(&buf));
  agstrfree(G, s1, false);
  agstrfree(G, s2, false);
  agxbfree(&buf);
  return s;
}

static char*
concatPort (Agraph_t *G, char* s1, char* s2)
{
  agxbuf buf = {0};

  agxbprint(&buf, "%s:%s", s1, s2);
  char *s = agstrdup(G, agxbuse(&buf));
  agstrfree(G, s1, false);
  agstrfree(G, s2, false);
  agxbfree(&buf);
  return s;
}


static void edgerhs(aagscan_t scanner, Agnode_t *tail, char *tport, item *hlist, char *key)
{
	Agnode_t		*head;
	Agraph_t		*subg;
	item			*hptr;
	aagextra_t 		*ctx = aagget_extra(scanner);

	if (hlist->tag == T_subgraph) {
		subg = hlist->u.subg;
		for (head = agfstnode(subg); head; head = agnxtnode(subg,head))
			newedge(scanner, tail, tport, agsubnode(ctx->S->g, head, 0), NULL, key);
	}
	else {
		for (hptr = hlist->u.list; hptr; hptr = hptr->next)
			newedge(scanner, tail, tport, agsubnode(ctx->S->g, hptr->u.n, 0), hptr->str, key);
	}
}

static void mkport(aagscan_t scanner, Agedge_t *e, char *name, char *val)
{
	Agsym_t *attr;
	aagextra_t *ctx = aagget_extra(scanner);

	if (val) {
		if ((attr = agattr_text(ctx->S->g,AGEDGE,name,NULL)) == NULL)
			attr = agattr_text(ctx->S->g,AGEDGE,name,"");
		agxset(e,attr,val);
	}
}

static void newedge(aagscan_t scanner, Agnode_t *t, char *tport, Agnode_t *h, char *hport, char *key)
{
	Agedge_t 	*e;
	aagextra_t 	*ctx = aagget_extra(scanner);

	e = agedge(ctx->S->g, t, h, key, 1);
	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 */
			SWAP(&tp, &hp);
		}
		mkport(scanner, e,TAILPORT_ID,tp);
		mkport(scanner, e,HEADPORT_ID,hp);
		applyattrs(ctx, e);
	}
}

/* graphs and subgraphs */


static void startgraph(aagscan_t scanner, char *name, bool directed, bool strict)
{
	aagextra_t *ctx = aagget_extra(scanner);
	if (ctx->G == NULL) {
		ctx->SubgraphDepth = 0;
		Agdesc_t req = {.directed = directed, .strict = strict, .maingraph = true};
		ctx->G = agopen(name,req,ctx->Disc);
	}
	ctx->S = push(ctx->S,ctx->G);
	agstrfree(NULL, name, false);
}

static void endgraph(aagscan_t scanner)
{
	aglexeof(scanner);
	aginternalmapclearlocalnames(aagget_extra(scanner)->G);
}

static void opensubg(aagscan_t scanner, char *name)
{
  aagextra_t *ctx = aagget_extra(scanner);

  if (++ctx->SubgraphDepth >= YYMAXDEPTH/2) {
    agerrorf("subgraphs nested more than %d deep", YYMAXDEPTH);
  }
	ctx->S = push(ctx->S, agsubg(ctx->S->g, name, 1));
	agstrfree(ctx->G, name, false);
}

static void closesubg(aagscan_t scanner)
{
	aagextra_t *ctx = aagget_extra(scanner);
	Agraph_t *subg = ctx->S->g;

	--ctx->SubgraphDepth;
	ctx->S = pop(ctx->S);
	ctx->S->subg = subg;
	assert(subg);
}

static void freestack(aagscan_t scanner)
{
	aagextra_t *ctx = aagget_extra(scanner);
	while (ctx->S) {
		deletelist(ctx->G, &ctx->S->nodelist);
		deletelist(ctx->G, &ctx->S->attrlist);
		deletelist(ctx->G, &ctx->S->edgelist);
		ctx->S = pop(ctx->S);
	}
}

static void graph_error(aagscan_t scanner)
{
	aagextra_t *ctx = aagget_extra(scanner);
	if (ctx->G) {
		freestack(scanner);
		endgraph(scanner);
		agclose(ctx->G);
		ctx->G = NULL;
	}
}

Agraph_t *agconcat(Agraph_t *g, const char *filename, void *chan,
                   Agdisc_t *disc) {
	aagscan_t scanner = NULL;
	aagextra_t extra = {
		.Disc = disc ? disc : &AgDefaultDisc,
		.Ifile = chan,
		.G = g,
		.line_num = 1,
		.InputFile = filename,
	};
	if (aaglex_init_extra(&extra, &scanner)) {
		return NULL;
	}
	aagset_in(chan, scanner);
	aagparse(scanner);
	if (extra.G == NULL) aglexbad(scanner);
	aaglex_destroy(scanner);
	agxbfree(&extra.InputFileBuffer);
	agxbfree(&extra.Sbuf);
	return extra.G;
}

Agraph_t *agread(void *fp, Agdisc_t *disc) {
  return agconcat(NULL, NULL, fp, disc);
}