hierarchyenumerator.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: HierarchyEnumerator.java
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.database.hierarchy;

import com.sun.electric.database.id.CellUsage;
import com.sun.electric.database.network.Global;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.network.NetworkTool;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.text.TextUtils;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.tool.generator.layout.LayoutLib;

import java.awt.geom.AffineTransform;
import java.io.Serializable;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/** The HierarchyEnumerator can help programs that need to "flatten"
 * the design hierarchy. Examples of such programs include the logical
 * effort engine and routers.
 *
 * <p>The HierarchyEnumerator performs a recursive descent of
 * the "completely expanded" design hierarchy. The HierarchyEnumerator
 * brings the Visitor along with it during the excursion.
 * The HierarchyEnumerator doesn't build a flattened data structure,
 * that's the prerogative of the Visitor. The HierarchyEnumerator simply
 * invokes Visitor methods for each Cell instance and NodeInst.
 *
 * <p>The following example illustrates the notion of "completely
 * expanded". Suppose the root Cell instantiates Cell A twice, and
 * Cell A instantiates Cell B twice. Then the HierarchyEnumerator
 * visits two instances of Cell A and four instances of Cell B.
 */
public final class HierarchyEnumerator {
    /** Stores the information necessary to generate an instance name for a Part
	  * It is sometimes important not to store the instance name as a String.
	  * When I stored instance names as strings in NCC profiles indicated that
	  * almost 50% of the storage space was used in these strings and 70% of the
	  * execution time was spent generating these Strings!!! */
	public static abstract class NameProxy implements Serializable {
		private VarContext context;
		private String sep;

		private String makePath(VarContext context, String sep) {
			String path = context.getInstPath(sep);
			if (!path.equals(""))  path+=sep;
			return path;
		}
		protected NameProxy(VarContext context, String sep) {
			this.context = context;
			this.sep = sep;
		}
		abstract public String leafName();
		abstract public Cell leafCell();
		public VarContext getContext() {return context;}
		public String toString() {
			return makePath(context, sep) + leafName();
		}
        public String toString(int numRemoveParents) {
            VarContext localContext = context.removeParentContext(numRemoveParents);
            String ret = makePath(localContext, sep) + leafName();
            return ret;
        }
	}
	public static class NetNameProxy extends NameProxy {
	    static final long serialVersionUID = 0;

		private Network net;
		public String leafName() {
			Iterator<String> it = net.getNames();
			if (it.hasNext()) {
				return it.next();
			}
			return "netIndex"+net.getNetIndex();
		}
		public Iterator<String> leafNames() {return net.getNames();}
		public NetNameProxy(VarContext context, String sep, Network net) {
			super(context, sep);
			this.net = net;
		}
		public Cell leafCell() {return net.getParent();}
        public Network getNet() { return net; }
	}
	public static class NodableNameProxy extends NameProxy {
	    static final long serialVersionUID = 0;

		private Nodable nodable;
		public String leafName() {return nodable.getName();}
		public NodableNameProxy(VarContext context, String sep, Nodable node) {
			super(context, sep);
			this.nodable = node;
		}
		public Cell leafCell() {return nodable.getParent();}
		public Nodable getNodable() {return nodable;}
	}

	// --------------------- private data ------------------------------
	private Visitor visitor;
	private boolean caching;
	private int curNetId = 0;
	private int cellCnt = 0; // For statistics
	private int instCnt = 0; // For statistics

	private Map<Integer, NetDescription> netIdToNetDesc =
		                                 new HashMap<Integer,NetDescription>();
    private HashMap<Cell,int[]> cellExternalIds = new HashMap<Cell,int[]>();

	private static void error(boolean pred, String msg) {
		LayoutLib.error(pred, msg);
	}

	// Prevent anyone from instantiating HierarchyEnumerator.
	private HierarchyEnumerator() {	}

    private int[] getExternalIds(Cell cell, Netlist netlist) {
        int[] externalIds = cellExternalIds.get(cell);
        if (externalIds != null) return externalIds;

        externalIds = new int[netlist.getNumExternalNetworks()];
        cellExternalIds.put(cell, externalIds);
		return externalIds;
	}

    //private int nextNetID() { return netIdToNetDesc.size(); }

	private int[] numberNets(Cell cell, Netlist netlist,
							 int[][] portNdxToNetIDs, CellInfo info) {
		int numNets = netlist.getNumNetworks();
        int[] externalIds = getExternalIds(cell, netlist);
		int[] netNdxToNetID = new int[numNets];
        int baseId = curNetId;
        Arrays.fill(externalIds, -1);
		if (portNdxToNetIDs != null) {
			assert portNdxToNetIDs.length == cell.getNumPorts() + 1;
			Global.Set globals = netlist.getGlobals();
			assert portNdxToNetIDs[0].length == globals.size();
			for (int i = 0; i < globals.size(); i++) {
				Global global = globals.get(i);
				int netIndex = netlist.getNetwork(global).getNetIndex();
                externalIds[netIndex] = portNdxToNetIDs[0][i];
			}
			for (int i = 0, numPorts = cell.getNumPorts(); i < numPorts; i++) {
				Export export = cell.getPort(i);
				int[] ids = portNdxToNetIDs[i + 1];
				assert ids.length == export.getNameKey().busWidth();
				for (int j=0; j<ids.length; j++) {
					int netIndex = netlist.getNetwork(export, j).getNetIndex();
                    externalIds[netIndex] = ids[j];
				}
			}
            for (int i = 0; i < externalIds.length; i++)
                assert externalIds[i] >= 0;
            baseId -= externalIds.length;
        }
		for (int i = 0; i < numNets; i++) {
			Network net = netlist.getNetwork(i);
            int localId = i;
            assert baseId + localId <= curNetId;
            if (baseId + localId == curNetId) {
                if (portNdxToNetIDs == null && localId < externalIds.length)
                    externalIds[localId] = localId;
                assert curNetId == baseId + localId;
                netIdToNetDesc.put(curNetId++, new NetDescription(net, info));
            } else if (localId >= externalIds.length || portNdxToNetIDs == null) {
                NetDescription nd = netIdToNetDesc.get(baseId + localId);
                int cmp = !net.isUsernamed() ? 1 : nd.net.isUsernamed() ? 0 : -1;
                if (cmp == 0 && net.isExported() != nd.net.isExported())
                    cmp = net.isExported() ? -1 : 1;
                if (cmp == 0)
                    cmp = TextUtils.STRING_NUMBER_ORDER.compare(net.getName(), nd.net.getName());
                if (cmp < 0)
                    nd.net = net;
            }
            int id = localId < externalIds.length ? externalIds[localId] : baseId + localId;
            netNdxToNetID[i] = id;
		}
		return netNdxToNetID;
	}

	private static int[] getGlobalNetIDs(Nodable no, Netlist netlist, int[] netNdxToNetID) {
		Global.Set gs = netlist.getNetlist(no).getGlobals();
		int[] netIDs = new int[gs.size()];
		for (int i = 0; i < gs.size(); i++) {
			int netIndex = netlist.getNetwork(no, gs.get(i)).getNetIndex();
			int netID = netNdxToNetID[netIndex];
			error(netID<0, "no netID for net");
			netIDs[i] = netID;
		}
		return netIDs;
	}

	private static int[] getPortNetIDs(Nodable no, PortProto pp,
									   Netlist netlist, int[] netNdxToNetID) {
		int busWidth = pp.getNameKey().busWidth();
		int[] netIDs = new int[busWidth];
		for (int j=0; j<busWidth; j++) {
            Network net = netlist.getNetwork(no, pp, j);
            error (net==null, "no network for net " + pp.getNameKey());
            int netIndex = net.getNetIndex();
			int netID = netNdxToNetID[netIndex];
			error(netID<0, "no netID for net " + pp.getNameKey());
			netIDs[j] = netID;
		}
		return netIDs;
	}

	private static int[][] buildPortMap(Netlist netlist, Nodable ni,
							     int[] netNdxToNetID) {
		Cell cell = (Cell)ni.getProto();
		int numPorts = cell.getNumPorts();
		int[][] portNdxToNetIDs = new int[numPorts + 1][];
		portNdxToNetIDs[0] = getGlobalNetIDs(ni, netlist, netNdxToNetID);
		for (int i=0; i<numPorts; i++) {
			PortProto pp = cell.getPort(i);
			portNdxToNetIDs[i + 1] = getPortNetIDs(ni, pp, netlist, netNdxToNetID);
		}
		return portNdxToNetIDs;
	}

	/** portNdxToNetIDs translates an Export's index to an array of NetIDs */
	private void enumerateCell(Nodable parentInst, Cell cell,
	                           VarContext context, Netlist netlist,
	                           int[][] portNdxToNetIDs,
		                       AffineTransform xformToRoot, CellInfo parent) {
		CellInfo info = visitor.newCellInfo();

		int firstNetID = curNetId;
		int[] netNdxToNetID = numberNets(cell, netlist, portNdxToNetIDs, info);
		int lastNetIDPlusOne = curNetId;
		cellCnt++;
		info.init(parentInst, cell,	context, netlist, netNdxToNetID,
				  portNdxToNetIDs, xformToRoot, netIdToNetDesc, parent);

		boolean enumInsts = visitor.enterCell(info);
		if (!enumInsts) return;

		for (Iterator<Nodable> it = netlist.getNodables(); it.hasNext();) {
			Nodable ni = it.next();

			instCnt++;
			boolean descend = visitor.visitNodeInst(ni, info);
			NodeProto np = ni.getProto();
			if (descend && ni.isCellInstance() && !((Cell)np).isIcon()) {
				int[][] portNmToNetIDs2 = buildPortMap(netlist, ni, netNdxToNetID);
				AffineTransform xformToRoot2 = xformToRoot;
				if (ni instanceof NodeInst) {
					// add transformation from lower level
					xformToRoot2 = new AffineTransform(xformToRoot);
					xformToRoot2.concatenate(((NodeInst)ni).rotateOut());
					xformToRoot2.concatenate(((NodeInst)ni).translateOut());
				}
				enumerateCell(ni, (Cell)np,
							  caching ? context.pushCaching(ni): context.push(ni),
							  netlist.getNetlist(ni),
							  portNmToNetIDs2, xformToRoot2, info);
			}
		}

		visitor.exitCell(info);

		// release storage associated with VarContext variable cache
		context.deleteVariableCache();

		// remove entries in netIdToNetDesc that we'll never use again
		for (int i = firstNetID; i < lastNetIDPlusOne; i++) {
			netIdToNetDesc.remove(i);
		}
	}

	//  Set up everything for the root cell and then initiate the
	//  hierarchical traversal.
	private void doIt(Cell root, VarContext context, Netlist netlist,
	                  Visitor visitor, boolean cache) {
		this.visitor = visitor;