/*****************************************************************************
*   Title : cdfg.h
*   Desc  : CDFG header file
*   Author: Jinhwan Jeon
*   Date  : 1996.5, 1996.7.22 1998.7.28
****************************************************************************/

#include <SLList.h>
#include <Strings.h>
#include <stdio.h>
#include <stdlib.h>
#include "token.h"

#ifndef __cdfg_h__
#define __cdfg_h__

class Assign;
class LengthType;
class Subgraph;
class Node;
class Module;
class Condition;
class Iteration;
class Edge;
class CDFG;

#ifdef WIN32
#define fprintf _win_fprintf
#define printf _win_printf
#define exit _win_exit
extern void _win_fprintf(FILE *, const char *, ...);
extern void _win_printf(const char *, ...);
extern void _win_exit(int);
#endif

extern "C" {
#ifdef MSVC5
#define strcasecmp _stricmp
#define strncasecmp _strnicmp
#endif
int strcasecmp(const char*, const char*);
};

//****************************************
// PtrList: list of pointers
//****************************************
template <class T>
class PtrList: public SLList<T*> {
	Pix _pi;
	T *_cur;
public:
	PtrList(): _pi(0), _cur(0)	{}

	T* isIn(T* d) 
		{
		if (d) { _pi = first(); _cur = d; }
		else	next(_pi);
		for (; _pi; next(_pi))	if ((*this)(_pi) == _cur)	return _cur;
		return 0;
		}

	T* sub(T* d) 
		{
		Pix pj=0;
		for (Pix pi=first(); pi; next(pi)) {
			T* cur = (*this)(pi);
			if (cur == d) {
				if (pj)		this->del_after(pj);
				else		this->remove_front(cur);
				return cur;
			}
			pj = pi;
		}
		return 0;
		}

	void replace(T* old, T* cur) 
		{
		for (Pix pi=first(); pi; next(pi)) 
			if ((*this)(pi) == old)		(*this)(pi) = cur;
		}

	T* item(int num) 
		{
		Pix pi=first();
		for (; num-- > 0 && pi; next(pi));
		return pi? (*this)(pi): 0;
		}
};

//****************************************
// NodePtrList: list of Node pointers
//****************************************
class NodePtrList: public PtrList<Node> {
public:
	Node* node(int id);

	Node* isIn(const char *name);
	void dump(int level=0);
	void recurCall(void (*func)(Node*, void*), void* flag=0);

	Node* isIn(Node *n)	{	return PtrList<Node>::isIn(n);	}
	void sub(Node *n)	{	PtrList<Node>::sub(n);	}
	void replace(Node* old, Node *cur)	
			{	PtrList<Node>::replace(old, cur);	}
	Node* item(int n)	{	return PtrList<Node>::item(n);	}
};

//****************************************
// EdgePtrList: list of Edge pointers
//****************************************
class EdgePtrList: public PtrList<Edge> {
public:
	Edge* isIn(Node *pred, Node *succ, const char *name, int wildcmp=0, 
				const char *type=0, int kind=0);
	int getNumData();
	void find(EdgePtrList &dest, Node *pred, Node *succ, const char *name, 
				int wildcmp=0, const char *type=0, int kind=0);

	void dump();

	Edge* isIn(Edge *n)	{	return PtrList<Edge>::isIn(n);	}
	void sub(Edge *n)	{	PtrList<Edge>::sub(n);	}
	void replace(Edge* old, Edge *cur)	
		{	PtrList<Edge>::replace(old, cur);	}
	Edge* item(int n)	{	return PtrList<Edge>::item(n);	}
};

//****************************************
// AssignPtrList: List of Assign pointers
//****************************************
class AssignPtrList: public PtrList<Assign> {
public:
	char* mapFormal(const char *actual);
	char* mapActual(const char *formal);

	Assign* isIn(const char *actual, const char *formal);
	void dump();

	void renameFormal(const char *prev, const char *cur);
	void renameActual(const char *prev, const char *cur);

	Assign* isIn(Assign *n)	{	return PtrList<Assign>::isIn(n);	}
	void sub(Assign *n)	{	PtrList<Assign>::sub(n);	}
	void replace(Assign* old, Assign *cur)	
			{	PtrList<Assign>::replace(old, cur);	}
	Assign* item(int n)	{	return PtrList<Assign>::item(n);	}
};

class LengthType;
//****************************************
// LengthTypePtrList: List of LengthType pointers
//****************************************
class LengthTypePtrList: public PtrList<LengthType> {
public:
	LengthType* isIn(const char *name, int tag=1);
	void dump();

	LengthType* isIn(LengthType *n)	
			{	return PtrList<LengthType>::isIn(n);	}
	void sub(LengthType *n)	{	PtrList<LengthType>::sub(n);	}
	void replace(LengthType* old, LengthType *cur)	
			{	PtrList<LengthType>::replace(old, cur);	}
	LengthType* item(int n)	{	return PtrList<LengthType>::item(n);	}
};

//****************************************
// LinkPtrList:
//		List of Link(String) (LISP form)
//****************************************
class Link;

class LinkPtrList: public PtrList<Link> {
public:
	int parse(char *token, char *buf=0, FILE *fp=0, int lno=0);
	int parseList(FILE *fp, int lno=0);

	Link* findList(const char *hdr, int caseflag=0);
	Link* findList(Link *l, int caseflag=0);
	Link* findValue(const char *value, int caseflag=0);

	void recurCall(void (*func)(Link *l));
	int  print(FILE *fp, int indent=0, int fmt=0);
	void dump();

	void  add(const char *fmt, ...);
	Link* sub(char *hdr, int caseflag=0);

	Link* isIn(Link *n)	{	return PtrList<Link>::isIn(n);	}
	void  sub(Link *n)	{	PtrList<Link>::sub(n);	}
	void  replace(Link* old, Link *cur)	
			{	PtrList<Link>::replace(old, cur);	}
	Link* item(int n)	{	return PtrList<Link>::item(n);	}

	Link* getNext(Link *n);
};

class Link : public LinkPtrList {
	String _val;
	int _no;
public:
	Link(): _no(0)	{}
	Link(char *str): _no(0)		{	parse(str);	}
	~Link();

	int isList()		{	return !empty();	}
	int compare(const char *str, int caseflag=0)		
		{	return caseflag? _val == str: !strcasecmp(_val.chars(), str);	}
	int compare(Link *l, int caseflag=0);
	int compareHeader(const char *hdr, int caseflag=0);

	int setNo(int n)	{	return _no = n;	}
	int getNo()			{	return _no;	}
	
	char* value()		{	return _val.empty()? 0: (char*)_val.chars();}
	int   intValue()	{	return atoi(_val);	}
	float floatValue()	{	return atof(_val);	}
	void  setValue(const char *fmt, ...);

	int  length()			{	return isList()? LinkPtrList::length(): 1;	}

	int  parse(FILE *fp, int lno=0);
	int  parse(char *buf);
	int  print(FILE *fp, int indent=0, int fmt=0);
	void dump();
};

#define		LERR_LEFT		1
#define		LERR_RIGHT		2

extern void (*_link_error_handler)(int, int);

//**************************************************************************
// LengthType Kind:
//   value of the member variable LengthType::type_kind
//**************************************************************************
enum LT_KIND {
	LT_NULL = 0, 
	LT_IN = 1,
	LT_OUT = 2,
	LT_INOUT = 4,
	LT_SUBTYPE = 8,
	LT_ARRAY = 0x10,
	LT_CONSTANT = 0x20,
	LT_INDEX = 0x40
};

//****************************************
// LengthType:
//	class for symbol table.
//****************************************
class LengthType {
public:
	String name;
	String type;
	int bits;
	short type_kind;
	int left;
	int right;
	String constants;

	Module *pmodule;
	LengthType *child;

	int port;
	int mark;

	LinkPtrList _attrib;
public:
	LengthType(): bits(0), type_kind(0), mark(0),
				left(-1), right(-1), child(0), port(0)		{}
	LengthType(char *n, char *t, int b, int kind, int l, int r): 
		name(n), type(t), bits(b), type_kind(kind), 
		mark(0), left(l), right(r), child(0), port(0) {}

	void setPort(int p)		{	port = p;	}
	int  getPort()			{	return port;	}

	void setMark(int m)		{	mark = m;	}
	int getMark()			{	return mark;	}

	Module* getPModule()	{	return pmodule;	}

	int  isSym();

	LinkPtrList* getAttrib()		{	return &_attrib;	}
	Link* findAttrib(char *name)	{	return _attrib.findList(name);	}

	void print(FILE *fp=stdout, int indent=0);
	void dump();
};

//****************************************
// Assign:
//	alias i/o symbols
//****************************************
class Assign {
public:
	String actual;
	String formal;
public:
	Assign(const char *a, const char *f): actual(a), formal(f) {}
	Assign()	{}

	void print(FILE *fp=stdout, int indent=0);
	void dump();
};

#define		NORET_FLAG		0x8000

//********************************************
// Edge Kind: return value of Edge::getKind()
//********************************************
enum EDGE_KIND {
	E_NULL = 0,
	E_DATA = 1,
	E_CTRL = 2,
	E_ENDLOOP = 4,
	E_DEPEND = 8,
	E_EVENT = 0x10,
	E_RETURN = 0x20,
};

//****************************************
// Edge:
//****************************************
class Edge {
protected:
	Node *pred;
	Node *succ;		// Successor: used when kind of CDFG is C_NORMAL
	String name;
	String type;
	int weight;
	int bits;

	int mark;
	short kind;

	int port;

	LinkPtrList _attrib;

	int _no;

	int tstart, tend;

	// Successor list: used when kind of CDFG is C_HYPER 
	NodePtrList _succs;

	void *info;
public:
	Edge(Node *p, Node *s, char *n): pred(p), succ(s), name(n),
		weight(0), bits(0), mark(0), _no(0), kind(0)
		{}

	Edge(): pred(0), succ(0), weight(0), bits(0), mark(0), _no(0), kind(0)
		{}

	Node* setPred(Node *p)	{	return pred = p;	}
	Node* setSucc(Node *s)	{	return succ = s;	}
	Node* getPred()			{	return pred;	}
	Node* getSucc()			{	return succ;	}

	NodePtrList* getSuccs()	{	return &_succs;	}

	void setPort(int p)		{	port = p;	}
	int  getPort()			{	return port;	}

	int setMark(int m)		{	return mark = m;	}
	int getMark()			{	return mark;		}

	void setName(const char *n)	{	name = n;	}
	void setType(const char *t)	{	type = t;	}
	char* getName()			{	return (char*)(name.chars());	}
	char* getType()			{	return (char*)(type.chars());	}

	int setWeight(int w)	{	return weight = w;	}
	int getWeight()			{	return weight;	}
	int setBits(int b)		{	return bits = b;	}
	int getBits()			{	return bits;	}

	int getKind(int calc=0);
	int isConst();

	// set/get line number
	void setNo(int n)		{	_no = n;	}
	int getNo()				{	return _no;	}

	LinkPtrList* getAttrib()		{	return &_attrib;	}
	Link* findAttrib(char *name)	{	return _attrib.findList(name);	}

	void setTstart(int ts)			{	tstart = ts;	}
	int  getTstart()				{	return tstart;	}
	void setTend(int te)			{	tend =te;		}
	int  getTend()					{	return tend;	}

	void* getInfo()					{	return info;	}
	void  setInfo(void *ptr)		{	info = ptr;		}

	int   compare(Node *pred, Node *succ, const char *name, int wildcmp=0,
					const char *type=0, int kind=0);

	void dump();
	virtual void print(FILE *fp=stdout, int i=0);

	virtual void parseInit()		{}
	virtual void copy(Edge *src)	{	void *ptr=info; *this=*src; info=ptr; }
};

//**************************************************************************
// Subgraph Type: return value of Subgraph::getType()
//**************************************************************************
enum SUBG_T {
	ST_NULL = 0,
	ST_COND,
	ST_ITER,
	ST_TRUE,
	ST_FALSE,
	ST_SUBG,
};

//****************************************
// Subgraph:
//****************************************
class Subgraph {
	int id;
	String pname;
	String name;
	NodePtrList nlist;
	EdgePtrList elist;
	AssignPtrList alist;

	Node *parent;
	Node **map;
	int  num_node;

	void *_info;
public:
	Subgraph(): id(0), map(0), _info(0) {	pname = "subgraph";	}
	Subgraph(char *pn, char *sn=0): id(0), pname(pn), map(0), _info(0)
		{	if (sn)	name = sn;	}

	Subgraph(int i): id(i)	{}
	~Subgraph();

	int setId(int i)	{	return id = i;	}
	int getId()			{	return id;	}

	void setPName(const char *n)	{	pname = n;	}
	char* getPName()				{	return (char*)(pname.chars());	}
	void setName(const char *n)		{	name = n;	}
	char* getName()					{	return (char*)(name.chars());	}

	void addNode(Node *n)		{	nlist.append(n);	}
	void addEdge(Edge *e)		{	elist.append(e);	}
	void addAssign(Assign *a)	{	alist.append(a);	}

	void subNode(Node *n);
	void subEdge(Edge *e);
	void subAssign(Assign *a);

	NodePtrList* getNodes()	{	return &nlist;	}
	EdgePtrList* getEdges()	{	return &elist;	}
	AssignPtrList* getAssigns()	{	return &alist;	}

	Node* setParent(Node *n)	{	return parent = n;	}
	Node* getParent()			{	return parent;		}
	Node* getTop();

	Node* node(int id)			{	return map? map[id]: 0;		}

	int  empty();
	int  getNumNodes(int level=0);
	int  getNumEdges(int level=0);
	int  getMaxNodeId();

	void parse(FILE *fp);
	void print(int level=1, FILE *fp=stdout, int i=0);
	void dump(int level=0);

	void mapNode(int parse=1);

	int getType();
	void recurCall(void (*func)(Node*, void*), void* flag=0);

	void* getInfo()		{	return _info;	}
	void  setInfo(void *ptr)	{	_info = ptr;	}

	// map external edge with name to internal edge
	void mapEdge(EdgePtrList &elist, Node *pred, Node *succ, 
				const char *name, int wildcmp=0, const char *type=0,
				int kind=0);
	Edge* mapEdge(Node *pred, Node *succ, const char *name, 
				int wildcmp=0, const char *type=0, int kind=0);
};

//**************************************************************************
// Node Type : return value of getType(), argument to setType()
//**************************************************************************
enum N_TYPE {
	N_NULL = 0,
	N_OPER = 1,
	N_MOD = 2,
	N_ITER = 4,
	N_COND = 8
};

//**************************************************************************
// HW SW Type: return value of getHwSwType(), argument to setHwSwType()
//**************************************************************************
enum HW_SW_TYPE {
	T_NULL = 0,
	T_SW = 1,
	T_HW,
	T_MIXED
};


//*******************************************************
// Node:
//		base class of class Module, Condition, Iteration
//*******************************************************
class Node {
protected:
	int id;
	String name;
	int op;
	short type;

	short hw_sw_type;
	int hw_speed;
	int sw_speed;

	Subgraph *parent;

	EdgePtrList preds;
	EdgePtrList succs;

	int mark;
	int _no;

	LinkPtrList _attrib;

	int tstart, tend;
	int pid;

	void *info;
public:
	Node(int i, char *n): id(i), name(n), type(N_OPER), op(-1), parent(0)
		{	mark = hw_speed = sw_speed = hw_sw_type = 0;	}
	Node(int i): id(i), type(N_OPER), op(-1), parent(0)
		{	mark = hw_speed = sw_speed = hw_sw_type = 0;	}
	Node(): type(N_OPER), op(-1), parent(0)
		{	mark = id = hw_speed = sw_speed = hw_sw_type = 0;	}
	~Node();

	int setId(int i)		{	return id = i;	}
	int getId()				{	return id;	}

	int setOp(int i)		{	return op = i;	}
	int getOp()				{	return op;	}

	void setNo(int n)		{	_no = n;	}
	int getNo()				{	return _no;	}

	void setName(const char *n)	{	name = n;	}
	char* getName()			{	return (char*)(name.chars());	}

	int setType(int t)		{	return type = t;	}
	N_TYPE getType()		{	return (N_TYPE)type;	}

	int setHwSpeed(int s)	{	return hw_speed = s;	}
	int getHwSpeed()		{	return hw_speed;	}
	int setSwSpeed(int s)	{	return sw_speed = s;	}
	int getSwSpeed()		{	return sw_speed;	}
	int setHwSwType(int t)	{	return hw_sw_type = t;	}
	int getHwSwType()		{	return hw_sw_type;	}

	void addPred(Edge *e)		{	preds.append(e);	}
	void addSucc(Edge *e)		{	succs.append(e);	}
	void subPred(Edge *e)		{	preds.sub(e);		}
	void subSucc(Edge *e)		{	succs.sub(e);		}

	void convPred(Edge *s, Edge *d);
	void convSucc(Edge *s, Edge *d);

	EdgePtrList* getPreds()	{	return &preds;	}
	EdgePtrList* getSuccs()	{	return &succs;	}
	Edge* getPred(int n, int data_flag=0);
	Edge* getSucc(int n, int data_flag=0);

	int getNumInPort(int edge_kind=E_DATA);
	int getNumOutPort(int edge_kind=E_DATA);

	Subgraph* getParent()				{	return parent;	}
	Subgraph* setParent(Subgraph *n)	{	return parent = n;	}

	Node* getPNode();
	Module* getPModule();

	int setMark(int m)				{	return mark = m;	}
	int getMark()					{	return mark;	}

	char* getPos(char *buf=0);
	Node* findPos(char *pos);

	Node* findNode(const char *nname);
	Node* getTop();
	int   getLevel();

	LinkPtrList* getAttrib()		{	return &_attrib;	}
	Link* findAttrib(char *name)	{	return _attrib.findList(name);	}

	void setTstart(int ts)		{	tstart = ts;		}
	int  getTstart()			{	return tstart;	}
	void setTend(int te)		{	tend = te;		}
	int  getTend()				{	return tend;	}
	void setPid(int _pid)		{	pid = _pid;		}
	int  getPid()				{	return pid;		}

	void* getInfo()				{	return info;	}
	void  setInfo(void *iptr)	{	info = iptr;	}

	virtual Subgraph* getCond()		{	return 0;	}
	virtual Subgraph* getTrue()		{	return 0;	}
	virtual Subgraph* getFalse()		{	return 0;	}
	virtual Subgraph* getSubg(int i=0)	{	return 0;	}
	virtual int getNumSubg()			{	return 0;	}

	virtual int isHierarchy();
	virtual void print(int level=1, FILE *fp=stdout, int i=0);
	virtual void dump(int level=0);

	virtual LengthType* findType(const char *type, int level=0);
	virtual LengthType* findSym(const char *name, int tag=1, int level=0);
	virtual LengthTypePtrList* getLengthTypes();

	virtual int getKind()		{	return 0;	}

	virtual void parseInit()		{}
	virtual void copy(Node *src)	{ void *ptr=info; *this = *src; info=ptr; }
};

//******************************************************
// Module:
//     hierarchical node which contains child subgraph
//******************************************************
class Module : public Node {
protected:
	LengthTypePtrList ltlist;
	Subgraph nsubg;

public:
	Module(int i=0): Node(i)	
		{	nsubg.setParent(this);	type = N_MOD;		}
	Module(int i, char *n): Node(i, n)	
		{ 	nsubg.setParent(this);	type = N_MOD;		}
	~Module();

	void addLengthType(LengthType *t)		{	ltlist.append(t);	}
	void subLengthType(LengthType *t)		{	ltlist.sub(t);		}
	LengthTypePtrList* getLengthTypes()		{	return &ltlist;		}

	void parse(FILE *fp);

	virtual LengthType* findType(const char *type, int level=0);
	virtual LengthType* findSym(const char *name, int tag=1, int level=0);

	virtual Subgraph* getSubg(int i=0)	{	return i? 0: &nsubg;	}
	virtual int getNumSubg()			{	return nsubg.empty()? 0: 1;	}

	virtual void print(int level=1, FILE *fp=stdout, int i=0);
	virtual void dump(int level=0);

	virtual int isHierarchy()	{	return nsubg.empty()? 0: 1;	}
};

//*********************************************************
// Condition:
//     Hierarchical node containing subgraph for condition
//     and different control path
//*********************************************************
enum COND_KIND {
	COND_IF,
	COND_CASE
};

class Condition : public Node {
protected:
	Subgraph ncond;
	Subgraph nfalse;
	SLList<Subgraph*> ntrues;
public:
	Condition(int i=0): Node(i), ncond("cond"), nfalse("false") 	
		{	
		ncond.setParent(this); 	nfalse.setParent(this);	
		type = N_COND; 			name = "cond";	
		}
	~Condition();

	void parse(FILE *fp);

	/* COND_KIND */
	virtual int getKind();

	virtual Subgraph* getTrue()		
		{	return ntrues.length()==1? ntrues(ntrues.first()): 0; 	}
	virtual Subgraph* getFalse()		{	return &nfalse;	}
	virtual Subgraph* getCond()			{	return &ncond;	}
	virtual Subgraph* getSubg(int i=0);
	virtual int getNumSubg()			{	return ntrues.length();	}

	virtual void print(int level=1, FILE *fp=stdout, int i=0);
	virtual void dump(int level=0);
};

//**************************************************************************
// Iteration Kind: return value of Iteration::getKind()
//**************************************************************************
enum ITER_KIND {
	ITER_NULL = 0,
	ITER_FOR,		// For loop
	ITER_WHILE		// While loop
};

//***********************************************************************
// Iteration:
//    Hierarchical node containing loop condition and loop body
//***********************************************************************
class Iteration : public Node {
protected:
	Subgraph niter;
	Subgraph nsubg;
public:
	Iteration(int i=0): Node(i), niter("iteration")	
		{	
		niter.setParent(this); 	nsubg.setParent(this);	
		type = N_ITER; 			name = "loop";	
		}

	void parse(FILE *fp);

	/* ITER_KIND */
	virtual int getKind();

	virtual Subgraph* getSubg(int i=0)	{	return i? 0: &nsubg;	}
	virtual Subgraph* getCond()		{	return &niter;	}
	virtual int	getNumSubg()			{	return 1;	}

	virtual void print(int level=1, FILE *fp=stdout, int i=0);
	virtual void dump(int level=0);
};

//**************************************************************************
// CDFG Kind: return value of CDFG::getKind()
//**************************************************************************
enum CDFG_KIND {
	C_NORMAL=1,				// normal form
	C_HYPER =2,				// CDFG in hyper edge format
	C_FLAT_MOD = 4,			// CDFG with modules flattened
	C_FLAT_LOOP = 8			// CDFG with loop condition flattened
};

//****************************************
// CDFG:
//****************************************
class CDFG : public Module {
protected:
	int _kind;

	void convHyper(Subgraph *subg);
	void convFlatLoop(Subgraph *subg);
	void convFlatModule(Subgraph *subg, int minlevel=2);
public:
	CDFG(): _kind(C_NORMAL) { nsubg.setPName(""); }
	CDFG(const char *fname, int ckind=C_NORMAL): _kind(ckind)
		{	nsubg.setPName("");	parse(fname); convGraph(ckind); }

	/* virtual */
	int  getKind()			{	return _kind;	}
	void convGraph(int kind, int option=0);

	void parse(const char *fname);

	void print(int level=1, FILE *fp=stdout, int indent=0);
	void dump(const char *fname=0, int level = 1);

	virtual Edge* newEdge()				{	return new Edge;	}
	virtual Node* newNode()				{	return new Node;	}
	virtual Module* newModule()			{	return new Module;	}
	virtual Condition* newCondition()	{	return new Condition;	}
	virtual Iteration* newIteration()	{	return new Iteration;	}

	virtual void parseInit(Node *n)		{}
	virtual void parseInit(Edge *e)		{}
};

//**************************************************************************
// basic routines for parser
//**************************************************************************
char* read_line(char *buf, int len, FILE *fp);
void  unread_line(FILE *fp, char *buf);
char* next_token(char *str=0, int exitflag=1, char *split=" \n\t");

//**************************************************************************
// basic error message routines
//**************************************************************************
void ErrorMsg(int exit_code, const char *fmt, ...);
void WarningMsg(const char *fmt, ...);

extern int line_no;
extern int debug_mode;

#endif
