autostitch.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: AutoStitch.java
 * Routing tool: Auto-Stitcher (places wires where geometry touches).
 * Written by Steven M. Rubin, Sun Microsystems.
 *
 * 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.tool.routing;

import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.geometry.EPoint;
import com.sun.electric.database.geometry.GenMath;
import com.sun.electric.database.geometry.ObjectQTree;
import com.sun.electric.database.geometry.Poly;
import com.sun.electric.database.geometry.PolyBase;
import com.sun.electric.database.geometry.PolyMerge;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.hierarchy.HierarchyEnumerator;
import com.sun.electric.database.hierarchy.Nodable;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.prototype.PortOriginal;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.Connection;
import com.sun.electric.database.topology.Geometric;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.topology.RTBounds;
import com.sun.electric.database.topology.RTNode;
import com.sun.electric.database.variable.EditWindow_;
import com.sun.electric.database.variable.ElectricObject;
import com.sun.electric.database.variable.UserInterface;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.Layer;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.JobException;
import com.sun.electric.tool.user.CircuitChangeJobs;

import java.awt.geom.AffineTransform;
import java.awt.geom.NoninvertibleTransformException;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Class which implements the Auto Stitching tool.
 */
public class AutoStitch
{
	/** true to use Quad-trees for port searching */				private static final boolean USEQTREE = true;

	/** router used to wire */  									private static InteractiveRouter router = new SimpleWirer();

	/** list of all routes to be created at end of analysis */		private List<Route> allRoutes;
	/** list of pins that may be inline pins due to created arcs */	private Set<NodeInst> possibleInlinePins;
	/** set of nodes to check (prevents duplicate checks) */		private Set<NodeInst> nodeMark;

	/****************************************** CONTROL ******************************************/

	/**
	 * Method to do auto-stitching.
	 * @param highlighted true to stitch only the highlighted objects.
	 * False to stitch the entire current cell.
	 * @param forced true if the stitching was explicitly requested (and so results should be printed).
	 */
	public static void autoStitch(boolean highlighted, boolean forced)
	{
		UserInterface ui = Job.getUserInterface();
		Cell cell = ui.needCurrentCell();
		if (cell == null) return;

		List<NodeInst> nodesToStitch = null;
		List<ArcInst> arcsToStitch = null;
		Rectangle2D limitBound = null;

		if (highlighted)
		{
			nodesToStitch = new ArrayList<NodeInst>();
			arcsToStitch = new ArrayList<ArcInst>();
			EditWindow_ wnd = ui.getCurrentEditWindow_();
			if (wnd == null) return;
			List<Geometric> highs = wnd.getHighlightedEObjs(true, true);
			limitBound = wnd.getHighlightedArea();
			for(Geometric geom : highs)
			{
				ElectricObject eObj = geom;
				if (eObj instanceof PortInst) eObj = ((PortInst)eObj).getNodeInst();
				if (eObj instanceof NodeInst)
				{
					NodeInst ni = (NodeInst)eObj;
					if (!ni.isCellInstance())
					{
						PrimitiveNode pnp = (PrimitiveNode)ni.getProto();
						if (pnp.getTechnology() == Generic.tech()) continue;
						if (pnp.getFunction() == PrimitiveNode.Function.NODE) continue;
					}
					nodesToStitch.add((NodeInst)eObj);
				} else if (eObj instanceof ArcInst)
				{
					arcsToStitch.add((ArcInst)eObj);
				}
			}
			if (nodesToStitch.size() == 0 && arcsToStitch.size() == 0)
			{
				if (forced) System.out.println("Nothing selected to auto-route");
				return;
			}
		}

		double lX = 0, hX = 0, lY = 0, hY = 0;
		if (limitBound != null)
		{
			lX = limitBound.getMinX();
			hX = limitBound.getMaxX();
			lY = limitBound.getMinY();
			hY = limitBound.getMaxY();
		}

		// find out the prefered routing arc
		new AutoStitchJob(cell, nodesToStitch, arcsToStitch, lX, hX, lY, hY, forced);
	}

	/**
	 * Class to do auto-stitching in a new thread.
	 */
	private static class AutoStitchJob extends Job
	{
		private Cell cell;
		private List<NodeInst> nodesToStitch;
		private List<ArcInst> arcsToStitch;
		private double lX, hX, lY, hY;
		private boolean forced;

		private AutoStitchJob(Cell cell, List<NodeInst> nodesToStitch, List<ArcInst> arcsToStitch,
			double lX, double hX, double lY, double hY, boolean forced)
		{
			super("Auto-Stitch", Routing.getRoutingTool(), Job.Type.CHANGE, null, null, Job.Priority.USER);
			this.cell = cell;
			this.nodesToStitch = nodesToStitch;
			this.arcsToStitch = arcsToStitch;
			this.lX = lX;
			this.hX = hX;
			this.lY = lY;
			this.hY = hY;
			this.forced = forced;
			setReportExecutionFlag(true);
			startJob();
		}

		public boolean doIt() throws JobException
		{
			Rectangle2D limitBound = null;
			if (lX != hX && lY != hY)
				limitBound = new Rectangle2D.Double(lX, lY, hX-lX, hY-lY);
			runAutoStitch(cell, nodesToStitch, arcsToStitch, this, null, limitBound, forced, Routing.isAutoStitchCreateExports(), false);
			return true;
		}
	}

	/**
	 * This is the public interface for Auto-stitching when done in batch mode.
	 * @param cell the cell in which to stitch.
	 * @param nodesToStitch a list of NodeInsts to stitch (null to use all in the cell).
	 * @param arcsToStitch a list of ArcInsts to stitch (null to use all in the cell).
	 * @param stayInside is the area in which to route (null to route arbitrarily).
	 * @param limitBound if not null, only consider connections that occur in this area.
	 * @param forced true if the stitching was explicitly requested (and so results should be printed).
	 * @param createExports true to create exports in subcells where necessary.
	 * @param showProgress true to show progress.
	 */
	public static void runAutoStitch(Cell cell, List<NodeInst> nodesToStitch, List<ArcInst> arcsToStitch, Job job,
		PolyMerge stayInside, Rectangle2D limitBound, boolean forced, boolean createExports, boolean showProgress)
	{
		// initialization
		if (cell.isAllLocked())
		{
			System.out.println("WARNING: Cell " + cell.describe(false) + " is locked: no changes can be made");
			return;
		}

		AutoStitch as = new AutoStitch();
		as.runNow(cell, nodesToStitch, arcsToStitch, job, stayInside, limitBound, forced, createExports, showProgress);
	}

	private AutoStitch()
	{
		possibleInlinePins = new HashSet<NodeInst>();
	}

	/**
	 * Method to run auto-stitching.
	 * @param cell the cell in which to stitch.
	 * @param nodesToStitch a list of NodeInsts to stitch (null to use all in the cell).
	 * @param arcsToStitch a list of ArcInsts to stitch (null to use all in the cell).
	 * @param job the Job running this, for aborting.
	 * @param stayInside is the area in which to route (null to route arbitrarily).
	 * @param limitBound if not null, only consider connections that occur in this area.
	 * @param forced true if the stitching was explicitly requested (and so results should be printed).
	 * @param createExports true to create exports in subcells where necessary.
	 * @param showProgress true to show progress.
	 */
	private void runNow(Cell cell, List<NodeInst> nodesToStitch, List<ArcInst> arcsToStitch, Job job,
		PolyMerge stayInside, Rectangle2D limitBound, boolean forced, boolean createExports, boolean showProgress)
	{
		if (showProgress) Job.getUserInterface().setProgressNote("Initializing routing");
		ArcProto preferredArc = Routing.getPreferredRoutingArcProto();

		// gather objects to stitch
		if (nodesToStitch == null)
		{
			// no data from highlighter
			nodesToStitch = new ArrayList<NodeInst>();
			for(Iterator<NodeInst> it = cell.getNodes(); it.hasNext(); )
			{
				NodeInst ni = it.next();
				if (ni.isIconOfParent()) continue;
				if (!ni.isCellInstance())
				{
					PrimitiveNode pnp = (PrimitiveNode)ni.getProto();
					if (pnp.getTechnology() == Generic.tech()) continue;
					if (pnp.getFunction() == PrimitiveNode.Function.NODE) continue;
				}
				nodesToStitch.add(ni);
			}
		}

		if (arcsToStitch == null)
		{
			arcsToStitch = new ArrayList<ArcInst>();
			for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
				arcsToStitch.add(it.next());
		}

		// next mark nodes to be checked
		nodeMark = new HashSet<NodeInst>();
		for(NodeInst ni : nodesToStitch)
			nodeMark.add(ni);
		Map<ArcProto,Integer> arcsCreatedMap = new HashMap<ArcProto,Integer>();
		Map<NodeProto,Integer> nodesCreatedMap = new HashMap<NodeProto,Integer>();
		allRoutes = new ArrayList<Route>();

		// compute the number of tasks to perform and start progress bar
		int totalToStitch = nodesToStitch.size() + arcsToStitch.size();
		if (createExports) totalToStitch *= 2;
		totalToStitch += arcsToStitch.size();
		int soFar = 0;

		if (job != null && job.checkAbort()) return;

		// if creating exports, make first pass in which exports must be created
		if (createExports)
		{
			if (showProgress) Job.getUserInterface().setProgressNote("Routing " + totalToStitch + " objects with export creation...");

			// run through the nodeinsts to be checked for export-creation stitching
			for(NodeInst ni : nodesToStitch)
			{
				soFar++;
				if (showProgress && (soFar%100) == 0)
				{
					if (job != null && job.checkAbort()) return;
					Job.getUserInterface().setProgressValue(soFar * 100 / totalToStitch);
				}
				checkExportCreationStitching(ni);
			}

			// now run through the arcinsts to be checked for export-creation stitching
			for(ArcInst ai : arcsToStitch)
			{
				soFar++;
				if (showProgress && (soFar%100) == 0)
				{
					if (job != null && job.checkAbort()) return;
					Job.getUserInterface().setProgressValue(soFar * 100 / totalToStitch);
				}

				// only interested in arcs that are wider than their nodes (and have geometry that sticks out)
				if (!arcTooWide(ai)) continue;
				if (!ai.isLinked()) continue;
				checkExportCreationStitching(ai);
			}

			// now run these arcs and reinitialize the list
			makeConnections(showProgress, arcsCreatedMap, nodesCreatedMap);
			allRoutes = new ArrayList<Route>();
			if (showProgress) Job.getUserInterface().setProgressNote("Initializing routing");
		}

		// next pre-compute bounds on all nodes in cell
		Map<NodeInst, Rectangle2D[]> nodeBounds = new HashMap<NodeInst, Rectangle2D[]>();
		Map<NodeInst, ObjectQTree> nodePortBounds = new HashMap<NodeInst, ObjectQTree>();
		for(Iterator<NodeInst> nIt = cell.getNodes(); nIt.hasNext(); )
		{
			NodeInst ni = nIt.next();

			// remember bounding box for each port
			int total = ni.getProto().getNumPorts();
			Rectangle2D [] bbArray = new Rectangle2D[total];
			int i = 0;
			for(Iterator<PortProto> pIt = ni.getProto().getPorts(); pIt.hasNext(); )
			{
				PortProto pp = pIt.next();
				PortOriginal fp = new PortOriginal(ni, pp);
				AffineTransform trans = fp.getTransformToTop();
				NodeInst rNi = fp.getBottomNodeInst();

				Rectangle2D bounds = new Rectangle2D.Double(rNi.getAnchorCenterX() - rNi.getXSize()/2,
					rNi.getAnchorCenterY() - rNi.getYSize()/2, rNi.getXSize(), rNi.getYSize());
				DBMath.transformRect(bounds, trans);
				bbArray[i++] = bounds;
			}
			nodeBounds.put(ni, bbArray);

			// remember quad-tree for ports on the node
			if (USEQTREE)
			{
				Rectangle2D niBounds = ni.getBounds();
				ObjectQTree oqt = new ObjectQTree(niBounds);
				for(Iterator<PortInst> it = ni.getPortInsts(); it.hasNext(); )
				{
					PortInst pi = it.next();
					PortProto pp = pi.getPortProto();
					PortOriginal fp = new PortOriginal(ni, pp);
					AffineTransform trans = fp.getTransformToTop();
					NodeInst rNi = fp.getBottomNodeInst();

					Rectangle2D bounds = new Rectangle2D.Double(rNi.getAnchorCenterX() - rNi.getXSize()/2,
						rNi.getAnchorCenterY() - rNi.getYSize()/2, rNi.getXSize(), rNi.getYSize());
					DBMath.transformRect(bounds, trans);
					oqt.add(pi, bounds);
				}
				nodePortBounds.put(ni, oqt);
			}
		}

		// finally, initialize the information about which layer is smallest on each arc
		Map<ArcProto,Layer> arcLayers = new HashMap<ArcProto,Layer>();

		// get the topology object for knowing what is connected
		Topology top = new Topology(cell);

		if (showProgress) Job.getUserInterface().setProgressNote("Routing " + totalToStitch + " objects...");