/*
 * SimExtract.c
 *
 *	This file provides routines to extract a single node name from the
 *	Magic circuit.  Some of this code is based on the Magic extract
 *	module.
 *
 *     *********************************************************************
 *     * Copyright (C) 1985, 1990 Regents of the University of California. *
 *     * Permission to use, copy, modify, and distribute this              *
 *     * software and its documentation for any purpose and without        *
 *     * fee is hereby granted, provided that the above copyright          *
 *     * notice appear in all copies.  The University of California        *
 *     * makes no representations about the suitability of this            *
 *     * software for any purpose.  It is provided "as is" without         *
 *     * express or implied warranty.  Export of this software outside     *
 *     * of the United States of America may require an export license.    *
 *     *********************************************************************
 * of California.
 */

#include <stdio.h>
#include <string.h>
#include <math.h>

#include "tcltk/tclmagic.h"
#include "utils/magic.h"
#include "utils/geometry.h"
#include "utils/geofast.h"
#include "tiles/tile.h"
#include "utils/hash.h"
#include "database/database.h"
#include "utils/malloc.h"
#include "textio/textio.h"
#include "debug/debug.h"
#include "extract/extract.h"
#include "extract/extractInt.h"
#include "utils/signals.h"
#include "windows/windows.h"
#include "dbwind/dbwind.h"
#include "utils/styles.h"
#include "utils/stack.h"
#include "sim/sim.h"

/* C99 compat */
#include "extract/extract.h"


/* When performing node name extraction, we mark all tiles of a node
 * as we walk through the database.  Since nodes can span multiple cells,
 * we need to keep a list off all cell definitions which we marked during
 * the search so we can erase these marks when we are finished.
 */
typedef struct def_list_elt
{
    CellDef *dl_def;
    struct def_list_elt *dl_next;
} DefListElt;

/* When the node name is extracted, all the labels associated with the
 * name are contained in a NodeRegion data structure.  We save all the
 * node regions created during the name search, freeing them when we are
 * finished.
 */

static DefListElt *DefList = (DefListElt *) NULL;
			/* list of cell defs used in the node name search */

static NodeRegion *NodeRegList = (NodeRegion *) NULL;
			/* list of the nodes found in the current selection */

extern Stack *extNodeStack;
			/* stack used to process node tiles */

static ExtStyle *simExtStyle = NULL;

    /*
     * Mask with a bit set for every type of transistor.
     */
TileTypeBitMask	SimTransMask;
    /*
     * Mask indicating which tile types may form a transistor
     * terminal (source/drain).
     */
TileTypeBitMask	SimSDMask;
    /*
     * A mask indicating which tile types may be the active part
     * of a transistor.  if type 't' is a possible transistor terminal,
     * then SimFetMask[t] indicates which tile types to search for the
     * 'gate' part.
     */
TileTypeBitMask	SimFetMask[TT_MAXTYPES];
    /*
     * Mask of planes for which SimFetMask is non-zero.
     */
PlaneMask	SimFetPlanes;


/*
 *----------------------------------------------------------------
 * SimAddDefList --
 *
 * 	This procedure adds a cell definition to the DefList.  A cell
 * 	definition is added only if is not already in the list.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The cell may be added to the list.
 *
 *----------------------------------------------------------------
 */

void
SimAddDefList(
    CellDef *newdef)
{
    DefListElt *d;

    /* check to see if the cell def is already in our list */

    for (d = DefList; d != (DefListElt *) NULL; d = d->dl_next) {
	if (d->dl_def == newdef) {
	    return;
	}
    }

    /* add the cell def to the list */

    if (DefList == (DefListElt *) NULL) {
	DefList = (DefListElt *) mallocMagic((unsigned) (sizeof(DefListElt)));
	DefList->dl_def = newdef;
	DefList->dl_next = (DefListElt *) NULL;
	return;
    }
    else {
	d = (DefListElt *)mallocMagic((unsigned) (sizeof(DefListElt)));
	d->dl_next = DefList;
	d->dl_def = newdef;
	DefList = d;
    }
}

/*
 *----------------------------------------------------------------
 * SimInitDefList
 *
 * 	This procedure initializes the cell definition list.  Any cell
 *	definitions in the list have their tiles erased of the marks
 *	we left during the node name search, and the space in the list
 *	is freed.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The cell definitions' tiles' marks we left are erased and the
 *	list is set to NULL.
 *
 *----------------------------------------------------------------
 */

void
SimInitDefList(void)
{
    DefListElt *p, *q;

    p = q = DefList;
    while (p != (DefListElt *)NULL) {
	q = p;
	p = p->dl_next;
	ExtResetTiles(q->dl_def, CLIENTDEFAULT);
	freeMagic(q);
    }
    DefList = (DefListElt *) NULL;
}


/*
 *----------------------------------------------------------------
 * SimAddNodeList
 *
 *      This procedure prepends a node region to the node region list.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The region next pointer is updated.
 *
 *----------------------------------------------------------------
 */

void
SimAddNodeList(
    NodeRegion *newnode)
{
    if (NodeRegList != (NodeRegion *)NULL)
	newnode->nreg_next = NodeRegList;
    NodeRegList = newnode;
}



/*
 *----------------------------------------------------------------
 * SimFreeNodeRegs
 *
 * 	This procedure frees the label regions stored in the list.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The list is set to NULL.
 *
 *----------------------------------------------------------------
 */

void
SimFreeNodeRegs(void)
{
    NodeRegion *p, *q;

    if (NodeRegList != (NodeRegion *) NULL)		/* sanity */
	ExtFreeLabRegions((LabRegion *)NodeRegList);

     NodeRegList = (NodeRegion *)NULL;
}


/*
 *----------------------------------------------------------------
 * SimInitConnTables --
 *
 * Initialize the connectivity tables for finding transistors connected
 * to the region being searched.
 *----------------------------------------------------------------
 */

int
SimInitConnTables(void)
{
    int  i, t, sd, p;
    ExtDevice *devptr;

    SimTransMask = ExtCurStyle->exts_deviceMask;

    TTMaskZero(&SimSDMask);
    for (t = TT_TECHDEPBASE; t < DBNumTypes; t++)
    {
	for (devptr = ExtCurStyle->exts_device[t]; devptr;
			devptr = devptr->exts_next)
	{
	    for (i = 0; !TTMaskHasType(&devptr->exts_deviceSDTypes[i],
			TT_SPACE); i++)
	    {
	        TTMaskSetMask(&SimSDMask, &devptr->exts_deviceSDTypes[i]);
	        TTMaskZero(&SimFetMask[t]);
	    }
	}
    }

    SimFetPlanes = 0;
    for (t = TT_TECHDEPBASE; t < DBNumTypes; t++)
    {
	if (TTMaskHasType(&SimTransMask, t))
	{
	    for (devptr = ExtCurStyle->exts_device[t]; devptr;
			devptr = devptr->exts_next)
	    {
		for (sd = TT_TECHDEPBASE; sd < DBNumTypes; sd++)
		{
		    for (i = 0; !TTMaskHasType(&devptr->exts_deviceSDTypes[i],
				TT_SPACE); i++)
		    {
			if (TTMaskHasType(&devptr->exts_deviceSDTypes[i], sd))
			{
			    TTMaskSetType(&SimFetMask[sd], t);
			    SimFetPlanes |= PlaneNumToMaskBit(DBPlane(t));
			}
		    }
		}
	    }
	}
    }
    simExtStyle = ExtCurStyle;
    return 0;
}

#define	IsTransGate(T)		(TTMaskHasType(&SimTransMask, T))
#define	IsTransTerm(T)		(TTMaskHasType(&SimSDMask, T))


typedef struct
{
    NodeRegion	*region;	/* Node to which this terminal is connected */
    int		pnum;		/* Lowest numbered plane in this region */
    Point	pos;		/* Lower-leftmost point for this node  */
} TransTerm;


typedef struct
{
    LabRegion	*t_dummy;	/* UNUSED */
    int		t_pnum;		/* Lowest numbered plane in this region */
    int		t_type;		/* Type of tile that contains lreg_ll */
    Point	t_ll;		/* Lower-leftmost point of 'gate' region */
    int		t_nterm;	/* number of terminals (at most 2) */
    bool	t_do_terms;	/* Set if we should collect terminals */
    TransTerm	t_term[10];	/* transistor 'source/drain' terminal(s) */
} SimTrans;


/* NOTE:  This is lazy;  these should not be global variables */

static	Tile		*gateTile;	/* Set to point to a transistor tile
					 * whose gate is connected to the
					 * node being searched
					 */
static  TileType	gateDinfo;	/* Split tile information, if needed */
static	Tile		*sdTile;	/* Set to point to a transistor tile
					 * whose source/drain is connected
					 * to the node being searched
					 */
static  TileType	sdDinfo;	/* Split tile information, if needed */
static	SimTrans	transistor;	/* Transistor being extracted */


typedef enum { ND_REGION, ND_NAME } RegOrName;


typedef struct			/* return value from SimFindOneNode */
{
    RegOrName	nd_what;	/* ND_REGION, => region, ND_NAME => nd_name */
    NodeRegion	*nd_region;	/* The node region extracted */
    char	*nd_name;	/* The 'final' node name */
} NodeSpec;


/*
 *----------------------------------------------------------------
 * SimTxtorLabel --
 *
 * Return a string that identifies a node as a function of a transistor
 * position.
 *
 *----------------------------------------------------------------
 */
char *
SimTxtorLabel(
    int		nterm,
    const Transform *tm,
    SimTrans	*trans)
{
    static char	name[30];
    Rect	r1, r2;

    r1.r_ll = trans->t_ll;
    r1.r_xtop = r1.r_xbot + 1;
    r1.r_ytop = r1.r_ybot + 1;
    GeoTransRect(tm, &r1, &r2);
    if (nterm > 1)
	nterm = 1;
    sprintf(name, "@=%c%d,%d", "gsd"[nterm+1], r2.r_xbot, r2.r_ybot);

    return name;
}

int
SimSDTransFunc(
    Tile  *tile,
    TileType dinfo)
{
    /* See above;  these should not be global variables! */
    sdTile = tile;
    sdDinfo = dinfo;
    return  1;
}


int
SimTransTerms(
    Boundary	*bp,
    SimTrans	*trans)
{
    TransTerm	*term;
    Tile	*tile = bp->b_outside;
    TileType	type;
    NodeRegion	*reg = (NodeRegion *)TiGetClientPTR(tile);
    int		pNum;
    int		i;

    if (IsSplit(tile)) {
	switch(bp->b_direction) {
	    case BD_LEFT:
		type = TiGetRightType(tile);
		break;
	    case BD_RIGHT:
		type = TiGetLeftType(tile);
		break;
	    case BD_TOP:
		type = TiGetBottomType(tile);
		break;
	    case BD_BOTTOM:
		type = TiGetTopType(tile);
		break;
	    default:
		/* Don't handle diagonal tiles */
		/* (future work?) */
		return 0;
	}
    }
    else
	type = TiGetTypeExact(tile);

    pNum = DBPlane(type);

    for (i = 0; i < trans->t_nterm; i++)
    {
	term = &trans->t_term[i];
	if (term->region == reg)
	{
	    if (pNum < term->pnum)
	    {
		term->pnum = pNum;
		term->pos = tile->ti_ll;
	    }
	    else if (pNum == term->pnum)
	    {
		if (LEFT(tile) < term->pos.p_x)
		    term->pos = tile->ti_ll;
		else if (LEFT(tile) == term->pos.p_x &&
			BOTTOM(tile) < term->pos.p_y)
		    term->pos.p_y = BOTTOM(tile);
	    }
	    return 0;
	}
    }

    term = &trans->t_term[trans->t_nterm++];
    term->region = reg;
    term->pnum = pNum;
    term->pos = tile->ti_ll;
    return 0;
}


int
SimTermNum(
    SimTrans	*trans,
    NodeRegion	*reg)
{
    int		i, changed;
    TransTerm	*p1, *p2, tmp;

    do
    {
	changed = 0;
	for (i = 0; i < trans->t_nterm-1; i++)
	{
	    p1 = &(trans->t_term[i]);
	    p2 = &(trans->t_term[i+1]);
	    if (p2->pnum > p1->pnum)
		continue;
	    else if (p2->pnum == p1->pnum)
	    {
		if (p2->pos.p_x > p1->pos.p_x)
		    continue;
		else if (p2->pos.p_x == p1->pos.p_x &&
			p2->pos.p_y > p1->pos.p_y)
		    continue;
	    }
	    changed = 1;
	    tmp = *p1;
	    *p1 = *p2;
	    *p2 = tmp;
	}
     }
     while (changed);

    for (i = 0; i < trans->t_nterm; i++)
    {
	if (trans->t_term[i].region == reg)
	    return i;
    }
    return -1;	/* not reached */
}

int
SimTransistorTile(
    Tile	*tile,
    TileType	dinfo,
    int		pNum,
    FindRegion	*arg)
{
    int i;
    TileType t;
    ExtDevice *devptr;

    extSetNodeNum((LabRegion *)&transistor, pNum, tile, dinfo);
    if (transistor.t_do_terms)
    {
	t = TiGetType(tile);
	devptr = ExtCurStyle->exts_device[t];
	for (i = 0; !TTMaskHasType(&devptr->exts_deviceSDTypes[i],
			TT_SPACE); i++)
	    extEnumTilePerim(tile, dinfo, &devptr->exts_deviceSDTypes[i],
			pNum, SimTransTerms, (ClientData)&transistor);
    }
    return 0;
}


int
SimFindTxtor(
    Tile	*tile,
    TileType	dinfo,
    int		pNum,
    FindRegion	*arg)
{
    TileType	type;

    extSetNodeNum((LabRegion *)arg->fra_region, pNum, tile, dinfo);

    if (!SimUseCoords)		/* keep searching, forget transistors */
	return 0;

    type = TiGetType(tile);

    if (IsTransGate(type))
    {
	gateTile = tile;	/* found a transistor gate, stop searching */
	gateDinfo = dinfo;
	return 1;
    }
    else if (IsTransTerm(type) && (sdTile == (Tile *)NULL))
    {
	Rect  area;

	TITORECT(tile, &area);
	GEO_EXPAND(&area, 1, &area);
	for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
	    if (PlaneMaskHasPlane(SimFetPlanes, pNum))
	    {
		if (DBSrPaintArea((Tile *)NULL,
		  	arg->fra_def->cd_planes[pNum], &area, &SimFetMask[type],
		  	SimSDTransFunc, (ClientData)NULL))
		    break;
	    }
    }
    return 0;
}


/*
 *----------------------------------------------------------------
 * SimFindOneNode
 *
 *	This procedure returns the node region for a tile which lies
 *	in the node.
 *
 * Results:
 *	A pointer to the node's node region data structure is returned.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------
 */

NodeSpec *
SimFindOneNode(
    SearchContext	*sx,
    Tile		*tile,
    TileType		dinfo)
{
    CellDef		*def = sx->scx_use->cu_def;
    NodeRegion		*reg;
    FindRegion		arg;
    TileType		type, loctype;
    static NodeSpec	ret;

    /* Allocate a new node */
    reg = (NodeRegion *) mallocMagic((unsigned) (sizeof(NodeRegion) ));
    reg->nreg_labels = (LabelList *) NULL;
    reg->nreg_cap = 0;
    reg->nreg_resist = 0;
    reg->nreg_pnum = DBNumPlanes;
    reg->nreg_next = (NodeRegion *) NULL;

    gateTile = sdTile = (Tile *)NULL;
    gateDinfo = sdDinfo = (TileType)0;

    /* Find all connected paint in this cell */
    arg.fra_connectsTo = ExtCurStyle->exts_nodeConn;
    arg.fra_def = def;

    if (IsSplit(tile))
	type = (dinfo & TT_SIDE) ? TiGetRightType(tile) : TiGetLeftType(tile);
    else
	type = TiGetTypeExact(tile);

    arg.fra_pNum = DBPlane(type);
    arg.fra_uninit = (ClientData) CLIENTDEFAULT;
    arg.fra_region = (ExtRegion *) reg;
    arg.fra_each = SimFindTxtor;
    (void) ExtFindNeighbors(tile, dinfo, arg.fra_pNum, &arg);

    if (gateTile != (Tile *)NULL)
    {
	    /* Determine the transistor position (leftmost-lowest tile) */
	transistor.t_pnum = DBNumPlanes;
	transistor.t_do_terms = FALSE;

	TiSetClient(gateTile, CLIENTDEFAULT);
	arg.fra_connectsTo = &SimTransMask;

	if (IsSplit(tile))
	    loctype = (gateDinfo & TT_SIDE) ? TiGetRightType(gateTile)
			: TiGetLeftType(gateTile);
	else
	    loctype = TiGetTypeExact(gateTile);

	arg.fra_pNum = DBPlane(loctype);
	arg.fra_uninit = (ClientData) CLIENTDEFAULT;
	arg.fra_region = (ExtRegion *) reg;
	arg.fra_each = SimTransistorTile;
	(void) ExtFindNeighbors(gateTile, gateDinfo, arg.fra_pNum, &arg);

	    /* Unmark current region since not all paint was traced */
	arg.fra_connectsTo = ExtCurStyle->exts_nodeConn;
	arg.fra_pNum = DBPlane(type);
	arg.fra_uninit = (ClientData) reg;
	arg.fra_region = (ExtRegion *) CLIENTDEFAULT;
	arg.fra_each = (int (*)()) NULL;
	(void) ExtFindNeighbors(tile, dinfo, arg.fra_pNum, &arg);

	freeMagic(reg);

	ret.nd_name = SimTxtorLabel(-1, &sx->scx_trans, &transistor);
	ret.nd_what = ND_NAME;
    }
    else if (sdTile != (Tile *)NULL)
    {
	int  tNum;

	SimAddNodeList(reg);
	SimAddDefList(def);

	transistor.t_pnum = DBNumPlanes;
	transistor.t_nterm = 0;
	transistor.t_do_terms = TRUE;

	/* collect the transistor position, and its terminals */
	arg.fra_connectsTo = &SimTransMask;

	if (IsSplit(sdTile))
	    loctype = (sdDinfo & TT_SIDE) ? TiGetRightType(sdTile)
			: TiGetLeftType(sdTile);
	else
	    loctype = TiGetTypeExact(sdTile);

	arg.fra_pNum = DBPlane(loctype);
	arg.fra_uninit = TiGetClient(sdTile);
	arg.fra_region = (ExtRegion *)&ret;
	arg.fra_each = SimTransistorTile;
	(void) ExtFindNeighbors(sdTile, sdDinfo, arg.fra_pNum, &arg);

	/* Unmark the transitor, since its not part of this region */
	arg.fra_region = (ExtRegion *) arg.fra_uninit;
	arg.fra_uninit = (ClientData) &ret;
	arg.fra_each = (int (*)()) NULL;
	(void) ExtFindNeighbors(sdTile, sdDinfo, arg.fra_pNum, &arg);

	if ((tNum = SimTermNum(&transistor, reg)) < 0)
	{
	    TxPrintf("\tSimFindOneNode: bad transistor terminal number\n");
	    goto use_name;
	}

	ret.nd_name = SimTxtorLabel(tNum, &sx->scx_trans, &transistor);
	ret.nd_what = ND_NAME;
    }
    else		/* no transistors found, get the regions labels */
    {
	SimAddNodeList(reg);
	SimAddDefList(def);

      use_name:
	ExtLabelOneRegion(def, ExtCurStyle->exts_nodeConn, reg);
	ret.nd_region = reg;
	ret.nd_what = ND_REGION;
    }
    return &ret;
}


/*
 *----------------------------------------------------------------
 * SimGetNodeName
 *
 * 	This procedure uses the Magic circuit extraction code to generate
 *	the node name.  The node is extracted by searching the database
 *	for all tiles electrically connected to the node.  Each tile is
 *	marked with a pointer to the node region it belongs to.  It is
 *	the node region data structure which contains the labels for a
 *	node.  The "preferred" label for the node is taken, and this
 *	is combined with the path name to produce the complete node name.
 *
 * Results:
 *	A pointer to the node name is returned.  This is a pointer to
 *	statically allocated memory, so subsequent calls to this procedure
 *	will change the node name the returned pointer references.
 *
 * Side effects:
 *	Any node region created is added to the node region list.
 *----------------------------------------------------------------
 */

char *
SimGetNodeName(
    SearchContext	*sx,		/* current search context */
    Tile		*tp,		/* tile in this cell which is part
					 * of the node
					 */
    TileType		dinfo,		/* Split tile information */
    const char		*path)		/* path name of hierarchy of search */
{
    CellDef	*def = sx->scx_use->cu_def;
    NodeRegion 	*nodeList;
    LabelList 	*ll;
    static char nodename[256];
    char	buff[256];
    char 	*text;
    char 	*nname;

    SimSawAbortString = FALSE;

    if (SimUseCoords && simExtStyle != ExtCurStyle)
	SimInitConnTables();

    /* check to see if this tile has been extracted before */

    if (ExtGetRegion(tp, dinfo) == (ExtRegion *)CLIENTDEFAULT)
    {
	NodeSpec  *ns;

	ns = SimFindOneNode(sx, tp, dinfo);
	if (ns->nd_what == ND_NAME)
	{
	    SimSawAbortString = TRUE;
	    return ns->nd_name;
	}
	nodeList = ns->nd_region;
    }
    else
    {
	nodeList = (NodeRegion *)ExtGetRegion(tp, dinfo);
    }

    /* generate the node name from the label region and the path name */

    text = extNodeName((LabRegion *)nodeList);
    strcpy(buff, text);
    strcpy(nodename, path);
    strcat(nodename, text);

    /* check to see if we should abort the search on the node name */

    if (!SimInitGetnode) {
	if (HashLookOnly(&SimGetnodeTbl, buff) != (HashEntry *) NULL) {
	    SimSawAbortString = TRUE;
	    if (HashLookOnly(&SimAbortSeenTbl, buff) == (HashEntry *) NULL) {
		HashFind(&SimAbortSeenTbl, buff);
		TxPrintf("Node name search aborted on \"%s\"\n", buff);
	    }
	}
    }

    /* Check whether or not to print out node name aliases.  Each alias
     * found is hashed in a table in order to suppress printing of
     * duplicate aliases.
     */

    if (SimGetnodeAlias && SimIsGetnode) {
	if (HashLookOnly(&SimGNAliasTbl, nodename) == (HashEntry *) NULL) {
	    HashFind(&SimGNAliasTbl, nodename);
#ifdef MAGIC_WRAPPER
	    Tcl_AppendElement(magicinterp, nodename);
#else
	    TxPrintf("alias: %s\n", nodename);
#endif
	}
    }

    /* search the list of all labels for this node, creating the full
     * node name and returning the "best" node name found.
     */
    for (ll = nodeList->nreg_labels; ll; ll = ll->ll_next) {
	if (ll->ll_label->lab_text == text) {
	    for (ll = ll->ll_next; ll; ll = ll->ll_next) {
		nname = ll->ll_label->lab_text;
		if (extLabType(nname, LABTYPE_NAME)) {
		    strcpy(nodename, path);
		    strcat(nodename, nname);
		    if (efPreferredName(nname, buff)) {
			strcpy(buff, nname);
		    }
		    if (SimGetnodeAlias && SimIsGetnode) {
			if (HashLookOnly(&SimGNAliasTbl, nodename)
			    == (HashEntry *) NULL) {
			    HashFind(&SimGNAliasTbl, nodename);
#ifdef MAGIC_WRAPPER
			    Tcl_AppendElement(magicinterp, nodename);
#else
			    TxPrintf("alias: %s\n", nodename);
#endif
			}
		    }
		}
	    }
	    break;
	}
    }
    strcpy(nodename, path);
    strcat(nodename, buff);
    return(nodename);
}

/*
 *----------------------------------------------------------------
 * SimGetNodeCleanup
 *
 *	This procedure is called to clean up the data structures and the
 *	tile database after a node name is extracted.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The node region list and cell def lists are re-initialized.
 *----------------------------------------------------------------
 */

void
SimGetNodeCleanUp(void)
{
    SimFreeNodeRegs();
    SimInitDefList();
}
