ercwellcheck.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: ERCWellCheck.java
 *
 * Copyright (c) 2004 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.erc;

import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.geometry.EPoint;
import com.sun.electric.database.geometry.GeometryHandler;
import com.sun.electric.database.geometry.Poly;
import com.sun.electric.database.geometry.PolyBase;
import com.sun.electric.database.geometry.GenMath.MutableBoolean;
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.text.TextUtils;
import com.sun.electric.database.topology.ArcInst;
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.UserInterface;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.DRCTemplate;
import com.sun.electric.technology.Layer;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.Technology.NodeLayer;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.JobException;
import com.sun.electric.tool.drc.DRC;
import com.sun.electric.tool.user.ErrorLogger;
import com.sun.electric.tool.user.Highlighter;
import com.sun.electric.tool.user.dialogs.EModelessDialog;
import com.sun.electric.tool.user.ui.EditWindow;
import com.sun.electric.tool.user.ui.TopLevel;

import java.awt.Color;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.awt.Shape;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collection;
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;
import java.util.concurrent.Semaphore;

import javax.swing.JButton;
import javax.swing.JLabel;
import javax.swing.JTextField;
import javax.swing.Timer;
import javax.swing.event.DocumentEvent;
import javax.swing.event.DocumentListener;

/**
 * This is the Electrical Rule Checker tool.
 * @author  Steve Rubin, Gilda Garreton
 */
public class ERCWellCheck
{
	private Cell cell;
	private Set<Object> possiblePrimitives;
	private List<WellCon> wellCons = new ArrayList<WellCon>();
	private Iterator<WellCon> [] wellConIterator;
	private List<WellCon> [] wellConLists;
	private RTNode pWellRoot, nWellRoot;
	private Layer pWellLayer, nWellLayer;
	private ErrorLogger errorLogger;
	private WellCheckJob job;
	private double worstPWellDist;
	private Point2D worstPWellCon;
	private Point2D worstPWellEdge;
	private double worstNWellDist;
	private Point2D worstNWellCon;
	private Point2D worstNWellEdge;

	private static final boolean GATHERSTATISTICS = false;
	private static final boolean DISTANTSEEDS = true;
	private static final boolean INCREMENTALGROWTH = false;

	/**
	 * Method to analyze the current Cell for well errors.
	 */
	public static void analyzeCurCell(GeometryHandler.GHMode newAlgorithm)
	{
		UserInterface ui = Job.getUserInterface();
		Cell curCell = ui.needCurrentCell();
		if (curCell == null) return;

		new WellCheckJob(curCell, newAlgorithm);
	}

	/**
	 * Method used by the regressions.
	 * @param cell the Cell to well-check.
	 * @param newAlgorithm the geometry algorithm to use.
	 * @return the success of running well-check.
	 */
	public static int checkERCWell(Cell cell, GeometryHandler.GHMode newAlgorithm)
	{
		ERCWellCheck check = new ERCWellCheck(cell, null, newAlgorithm);
		return check.runNow();
	}

	private ERCWellCheck(Cell cell, WellCheckJob job, GeometryHandler.GHMode newAlgorithm)
	{
		this.job = job;
		this.mode = newAlgorithm;
		this.cell = cell;
	}

	private static class WellCheckJob extends Job
	{
		private Cell cell;
		private GeometryHandler.GHMode newAlgorithm;
		private double worstPWellDist, worstNWellDist;
		private EPoint worstPWellCon, worstPWellEdge;
		private EPoint worstNWellCon, worstNWellEdge;

		private WellCheckJob(Cell cell, GeometryHandler.GHMode newAlgorithm)
		{
			super("ERC Well Check on " + cell, ERC.tool, Job.Type.EXAMINE, null, null, Job.Priority.USER);
			this.cell = cell;
			this.newAlgorithm = newAlgorithm;
			startJob();
		}

		public boolean doIt() throws JobException
		{
			ERCWellCheck check = new ERCWellCheck(cell, this, newAlgorithm);
			check.runNow();
			worstPWellDist = check.worstPWellDist;
			fieldVariableChanged("worstPWellDist");
			worstNWellDist = check.worstNWellDist;
			fieldVariableChanged("worstNWellDist");
			if (check.worstPWellCon != null)
			{
				worstPWellCon = new EPoint(check.worstPWellCon.getX(), check.worstPWellCon.getY());
				fieldVariableChanged("worstPWellCon");
			}
			if (check.worstPWellEdge != null)
			{
				worstPWellEdge = new EPoint(check.worstPWellEdge.getX(), check.worstPWellEdge.getY());
				fieldVariableChanged("worstPWellEdge");
			}
			if (check.worstNWellCon != null)
			{
				worstNWellCon = new EPoint(check.worstNWellCon.getX(), check.worstNWellCon.getY());
				fieldVariableChanged("worstNWellCon");
			}
			if (check.worstNWellEdge != null)
			{
				worstNWellEdge = new EPoint(check.worstNWellEdge.getX(), check.worstNWellEdge.getY());
				fieldVariableChanged("worstNWellEdge");
			}
			return true;
		}

		public void terminateOK()
		{
			// show the farthest distance from a well contact
			UserInterface ui = Job.getUserInterface();
			EditWindow_ wnd = ui.getCurrentEditWindow_();
			if (wnd != null && (worstPWellDist > 0 || worstNWellDist > 0))
			{
				wnd.clearHighlighting();
				if (worstPWellDist > 0)
				{
					wnd.addHighlightLine(worstPWellCon, worstPWellEdge, cell, false);
					System.out.println("Farthest distance from a P-Well contact is " + worstPWellDist);
				}
				if (worstNWellDist > 0)
				{
					wnd.addHighlightLine(worstNWellCon, worstNWellEdge, cell, false);
					System.out.println("Farthest distance from an N-Well contact is " + worstNWellDist);
				}
				wnd.finishedHighlighting();
			}
		}
	}

	private int runNow()
	{
		System.out.println("Checking Wells and Substrates in '" + cell.libDescribe() + "' ...");
		long startTime = System.currentTimeMillis();
		errorLogger = ErrorLogger.newInstance("ERC Well Check ");
		initStatistics();

		// make a list of primtivies that need to be examined
		possiblePrimitives = new HashSet<Object>();
		for(Iterator<Technology> it = Technology.getTechnologies(); it.hasNext(); )
		{
			Technology tech = it.next();
			for(Iterator<PrimitiveNode> pIt = tech.getNodes(); pIt.hasNext(); )
			{
				PrimitiveNode pn = pIt.next();
				NodeLayer [] nl = pn.getLayers();
				for(int i=0; i<nl.length; i++)
				{
					Layer lay = nl[i].getLayer();
					if (lay.getFunction().isSubstrate())
					{
						possiblePrimitives.add(pn);
						break;
					}
				}
			}
			for(Iterator<ArcProto> pIt = tech.getArcs(); pIt.hasNext(); )
			{
				ArcProto ap = pIt.next();
				for(int i=0; i<ap.getNumArcLayers(); i++)
				{
					Layer lay = ap.getLayer(i);
					if (lay.getFunction().isSubstrate())
					{
						if (lay.getFunction().isWell())
							pWellLayer = lay; else
								nWellLayer = lay;
						possiblePrimitives.add(ap);
						break;
					}
				}
			}
		}
//		int errorCount = doOldWay();
		int errorCount = doNewWay();
		showStatistics();
		// report the number of errors found
		long endTime = System.currentTimeMillis();
		if (errorCount == 0)
		{
			System.out.println("No Well errors found (took " + TextUtils.getElapsedTime(endTime - startTime) + ")");
		} else
		{
			System.out.println("FOUND " + errorCount + " WELL ERRORS (took " + TextUtils.getElapsedTime(endTime - startTime) + ")");
			
		}
		return errorCount;
	}

	private WellCon getNextWellCon(int threadIndex)
	{
		synchronized(wellConIterator[threadIndex])
		{
			while (wellConIterator[threadIndex].hasNext())
			{
				WellCon wc = wellConIterator[threadIndex].next();
				if (wc.wellNum == null) return wc;
			}
		}

		// not found in this list: try the others
		int numLists = wellConIterator.length;
		for(int i=1; i<numLists; i++)
		{
			int otherList = (threadIndex + i) % numLists;
			synchronized(wellConIterator[otherList])
			{
				while (wellConIterator[otherList].hasNext())
				{
					WellCon wc = wellConIterator[otherList].next();
					if (wc.wellNum == null) return wc;
				}
			}
		}
		return null;
	}

	private void spreadSeeds(int threadIndex)
	{
		for(;;)
		{
			WellCon wc = getNextWellCon(threadIndex);
			if (wc == null) break;

			// see if this contact is in a marked well
			Rectangle2D searchArea = new Rectangle2D.Double(wc.ctr.getX(), wc.ctr.getY(), 0, 0);
			RTNode topSearch = nWellRoot;
			if (wc.fun == PrimitiveNode.Function.WELL) topSearch = pWellRoot;
			boolean geomFound = false;
			for(RTNode.Search sea = new RTNode.Search(searchArea, topSearch, true); sea.hasNext(); )
			{
				WellBound wb = (WellBound)sea.next();
				geomFound = true;
				wc.wellNum = wb.netID;
				if (wc.wellNum != null) break;
			}
			if (wc.wellNum != null) continue;

			// mark it and spread the value
			wc.wellNum = new NetValues();

			// if nothing to spread, give an error
			if (!geomFound)
			{
				String errorMsg = "N-Well contact is floating";
				if (wc.fun == PrimitiveNode.Function.WELL) errorMsg = "P-Well contact is floating";
				errorLogger.logError(errorMsg, new EPoint(wc.ctr.getX(), wc.ctr.getY()), cell, 0);
				continue;
			}

			// spread out through the well area
			spreadWellSeed(wc.ctr.getX(), wc.ctr.getY(), wc.wellNum, topSearch, threadIndex);
		}
	}

	private class SpreadInThread extends Thread
	{
		private Semaphore whenDone;
		private int threadIndex;

		public SpreadInThread(String name, Semaphore whenDone, int index)
		{
			super(name);
			this.whenDone = whenDone;
			threadIndex = index;
			start();
		}

		public void run()
		{
			spreadSeeds(threadIndex);
			whenDone.release();
		}
	}

	private int doNewWay()
	{
		pWellRoot = RTNode.makeTopLevel();
		nWellRoot = RTNode.makeTopLevel();

		// enumerate the hierarchy below here
		long startTime = System.currentTimeMillis();
		NewWellCheckVisitor wcVisitor = new NewWellCheckVisitor();
		HierarchyEnumerator.enumerateCell(cell, VarContext.globalContext, wcVisitor);
		int numPRects = getTreeSize(pWellRoot);
		int numNRects = getTreeSize(nWellRoot);
		long endTime = System.currentTimeMillis();
		System.out.println("   Geometry collection found " + (numPRects + numNRects) + " well pieces, took " +
			TextUtils.getElapsedTime(endTime - startTime));
		startTime = endTime;

		// determine the number of threads to use
		int numberOfThreads = 1;
		if (ERC.isParallelWellAnalysis()) numberOfThreads = Runtime.getRuntime().availableProcessors();
		if (numberOfThreads > 1)
		{
			int maxProc = ERC.getWellAnalysisNumProc();
			if (maxProc > 0) numberOfThreads = maxProc;
		}

		// make arrays of well contacts clustered for each processor
		assignWellContacts(numberOfThreads);

		// analyze the contacts
		NetValues.reset();
		if (numberOfThreads <= 1) spreadSeeds(0); else
		{
			Semaphore outSem = new Semaphore(0);
			for(int i=0; i<numberOfThreads; i++)
				new SpreadInThread("WellCheck propagate #" + (i+1), outSem, i);

			// now wait for spread threads to finish
			outSem.acquireUninterruptibly(numberOfThreads);
		}

		endTime = System.currentTimeMillis();
		String msg = "   Geometry analysis ";
		if (numberOfThreads > 1) msg += "used " + numberOfThreads + " threads and ";
		msg += "took ";
		System.out.println(msg + TextUtils.getElapsedTime(endTime - startTime));
		startTime = endTime;

		// look for short-circuits
		Map<Integer,WellCon> wellContacts = new HashMap<Integer,WellCon>();
		Map<Integer,Set<Integer>> wellShorts = new HashMap<Integer,Set<Integer>>();
		for(WellCon wc : wellCons)
		{
			Integer wellIndex = new Integer(wc.wellNum.getIndex());
			WellCon other = wellContacts.get(wellIndex);
			if (other == null) wellContacts.put(wellIndex, wc); else
			{
				if (wc.netNum != other.netNum)
				{
					Integer wcNetNum = new Integer(wc.netNum);
					Set<Integer> shortsInWC = wellShorts.get(wcNetNum);
					if (shortsInWC == null)
					{
						shortsInWC = new HashSet<Integer>();
						wellShorts.put(wcNetNum, shortsInWC);
					}

					Integer otherNetNum = new Integer(other.netNum);
					Set<Integer> shortsInOther = wellShorts.get(otherNetNum);
					if (shortsInOther == null)
					{
						shortsInOther = new HashSet<Integer>();
						wellShorts.put(otherNetNum, shortsInOther);
					}

					// give error if not seen before
					if (!shortsInWC.contains(otherNetNum))
					{
						List<EPoint> pointList = new ArrayList<EPoint>();
						pointList.add(new EPoint(wc.ctr.getX(), wc.ctr.getY()));