/* -*- tab-width: 4 -*- * * Electric(tm) VLSI Design System * * File: Quick.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.drc;import com.sun.electric.database.geometry.*;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.text.TextUtils;import com.sun.electric.database.topology.ArcInst;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.variable.VarContext;import com.sun.electric.database.variable.Variable;import com.sun.electric.technology.*;import com.sun.electric.technology.technologies.Generic;import com.sun.electric.tool.Job;import com.sun.electric.tool.user.ErrorLogger;import java.awt.geom.AffineTransform;import java.awt.geom.Area;import java.awt.geom.Point2D;import java.awt.geom.Rectangle2D;import java.util.*;/** * This is the "quick" DRC which does full hierarchical examination of the circuit. * <P> * The "quick" DRC works as follows: *    It first examines every primitive node and arc in the cell *        For each layer on these objects, it examines everything surrounding it, even in subcells *            R-trees are used to limit search. *            Where cell instances are found, the contents are examined recursively *    It next examines every cell instance in the cell *        All other instances within the surrounding area are considered *            When another instance is found, the two instances are examined for interaction *                A cache is kept of instance pairs in specified configurations to speed-up arrays *            All objects in the other instance that are inside the bounds of the first are considered *                The other instance is hierarchically examined to locate primitives in the area of consideration *            For each layer on each primitive object found in the other instance, *                Examine the contents of the first instance for interactions about that layer * <P> * Since Electric understands connectivity, it uses this information to determine whether two layers * are connected or not.  However, if such global connectivity is propagated in the standard Electric * way (placing numbers on exports, descending into the cell, and pulling the numbers onto local networks) * then it is not possible to decompose the DRC for multiple processors, since two different processors * may want to write global network information on the same local networks at once. * <P> * To solve this problem, the "quick" DRC determines how many instances of each cell exist.  For every * network in every cell, an array is built that is as large as the number of instances of that cell. * This array contains the global network number for that each instance of the cell.  The algorithm for * building these arrays is quick (1 second for a million-transistor chip) and the memory requirement * is not excessive (8 megabytes for a million-transistor chip).  It uses the CheckInst and CheckProto * objects. * @author  Steve Rubin, Gilda Garreton */public class Quick{	private HashMap<NodeInst,CheckInst> checkInsts = null;    private HashMap<Cell,CheckProto> checkProtos = null;	private HashMap<Network,Integer[]> networkLists = null;	private HashMap<Layer,DRCTemplate> minAreaLayerMap = new HashMap<Layer,DRCTemplate>();    // For minimum area checking	private HashMap<Layer,DRCTemplate> enclosedAreaLayerMap = new HashMap<Layer,DRCTemplate>();    // For enclosed area checking    private HashMap<Layer,DRCTemplate> spacingLayerMap = new HashMap<Layer,DRCTemplate>();    // to detect holes using the area function    private HashMap<Layer,DRCTemplate> slotSizeLayerMap = new HashMap<Layer,DRCTemplate>();    // For max length checking    private DRC.CheckDRCJob job; // Reference to running job	private HashMap<Cell,Cell> cellsMap = new HashMap<Cell,Cell>(); // for cell caching    private HashMap<Geometric,Geometric> nodesMap = new HashMap<Geometric,Geometric>(); // for node caching    private GeometryHandler.GHMode mergeMode = GeometryHandler.GHMode.ALGO_SWEEP; // .ALGO_QTREE;    private Map<Layer,NodeInst> od2Layers = new HashMap<Layer,NodeInst>(3);  /** to control OD2 combination in the same die according to foundries */	public Quick(DRC.CheckDRCJob j, GeometryHandler.GHMode mode)	{		this.job = j;        this.mergeMode = mode;	}    private List<InstanceInter> instanceInteractionList = new ArrayList<InstanceInter>();	/** a NodeInst that is too tiny for its connection. */		private NodeInst tinyNodeInst;	/** the other Geometric in "tiny" errors. */				private Geometric tinyGeometric;	/** for tracking the time of good DRC. */					private HashSet<Cell> goodSpacingDRCDate = new HashSet<Cell>();	/** for tracking cells that need to clean good DRC vars */	private HashSet<Cell> cleanSpacingDRCDate = new HashSet<Cell>();	/** for tracking the time of good DRC. */					private HashSet<Cell> goodAreaDRCDate = new HashSet<Cell>();	/** for tracking cells that need to clean good DRC vars */	private HashSet<Cell> cleanAreaDRCDate = new HashSet<Cell>();	/** Top cell for DRC */                                     private Cell topCell;    /** Miscellanous data for DRC */                            private DRC.ReportInfo reportInfo;//    /* for figuring out which layers are valid for DRC */    // To speed up the layer process    private ValidationLayers validLayers;    public static ErrorLogger checkDesignRules(ErrorLogger errorLog, Cell cell, Geometric[] geomsToCheck, boolean[] validity,                                               Rectangle2D bounds)    {        if (errorLog == null) errorLog = DRC.getDRCErrorLogger(true, false, null);        return checkDesignRules(errorLog, cell, geomsToCheck, validity, bounds, null,                GeometryHandler.GHMode.ALGO_SWEEP, false);    }    /**	 * This is the entry point for DRC.	 *	 * Method to do a hierarchical DRC check on cell "cell".	 * If "count" is zero, check the entire cell.	 * If "count" is nonzero, only check that many instances (in "nodesToCheck") and set the	 * entry in "validity" TRUE if it is DRC clean.	 * @param bounds if null, check entire cell. If not null, only check area in bounds.     * @param drcJob	 * @param onlyArea     * @return ErrorLogger containing the information	 */	public static ErrorLogger checkDesignRules(ErrorLogger errorLog, Cell cell, Geometric[] geomsToCheck, boolean[] validity,                                               Rectangle2D bounds, DRC.CheckDRCJob drcJob, GeometryHandler.GHMode mode, boolean onlyArea)	{		Quick q = new Quick(drcJob, mode);        return q.doCheck(errorLog, cell, geomsToCheck, validity, bounds, onlyArea);	}    // returns the number of errors found	private ErrorLogger doCheck(ErrorLogger errorLog, Cell cell, Geometric[] geomsToCheck, boolean[] validity,                                Rectangle2D bounds, boolean onlyArea)	{		// Check if there are DRC rules for particular tech        Technology tech = cell.getTechnology();		DRCRules rules = DRC.getRules(tech);        // if checking specific instances, adjust options and processor count        int count = (geomsToCheck != null) ? geomsToCheck.length : 0;        reportInfo = new DRC.ReportInfo(errorLog, tech, (count > 0));        ErrorLogger errorLogger = errorLog;        // caching bits        System.out.println("Running DRC with " + DRC.explainBits(reportInfo.activeSpacingBits));		// Nothing to check for this particular technology		if (rules == null || rules.getNumberOfRules() == 0) return errorLogger;	    topCell = cell; /* Especially important for minArea checking */		// cache valid layers for this technology        validLayers = new ValidationLayers(reportInfo.errorLogger, topCell, rules);		// clean out the cache of instances	    instanceInteractionList.clear();		// determine maximum DRC interaction distance//		worstInteractionDistance = DRC.getWorstSpacingDistance(tech, -1);	    // determine if min area must be checked (if any layer got valid data)	    minAreaLayerMap.clear();	    enclosedAreaLayerMap.clear();        spacingLayerMap.clear();        slotSizeLayerMap.clear();	    cellsMap.clear();	    nodesMap.clear();	    // No incremental neither per Cell	    if (!DRC.isIgnoreAreaChecking() && reportInfo.errorTypeSearch != DRC.DRCCheckMode.ERROR_CHECK_CELL)	    {		    for(Iterator<Layer> it = tech.getLayers(); it.hasNext(); )			{				Layer layer = it.next();				// Storing min areas				DRCTemplate minAreaRule = DRC.getMinValue(layer, DRCTemplate.DRCRuleType.MINAREA);				if (minAreaRule != null)					minAreaLayerMap.put(layer, minAreaRule);				// Storing enclosed areas				DRCTemplate enclosedAreaRule = DRC.getMinValue(layer, DRCTemplate.DRCRuleType.MINENCLOSEDAREA);				if (enclosedAreaRule != null)					enclosedAreaLayerMap.put(layer, enclosedAreaRule);                // Storing spacing rules                DRCTemplate spaceRule = DRC.getSpacingRule(layer, null, layer, null, true, -1, -1.0, -1.0); // UCONSPA, CONSPA or SPACING                if (spaceRule != null)                    spacingLayerMap.put(layer, spaceRule);                // Storing slot sizes				DRCTemplate slotRule = DRC.getMinValue(layer, DRCTemplate.DRCRuleType.SLOTSIZE);				if (slotRule != null)					slotSizeLayerMap.put(layer, slotRule);			}            if (onlyArea)            {                int numErrors = checkMinAreaSlow(cell);                if (numErrors == 0)                    goodAreaDRCDate.add(cell);                else                    cleanAreaDRCDate.add(cell);                System.out.println("Missing update in dates");                return errorLogger;            }        }		// initialize all cells for hierarchical network numbering		checkProtos = new HashMap<Cell,CheckProto>();		checkInsts = new HashMap<NodeInst,CheckInst>();		// initialize cells in tree for hierarchical network numbering		Netlist netlist = cell.getNetlist();		CheckProto cp = checkEnumerateProtos(cell, netlist);		// now recursively examine, setting information on all instances		cp.hierInstanceCount = 1;		reportInfo.checkTimeStamp = 0;		checkEnumerateInstances(cell);		// now allocate space for hierarchical network arrays		//int totalNetworks = 0;		networkLists = new HashMap<Network,Integer[]>();        for (Map.Entry<Cell,CheckProto> e : checkProtos.entrySet())		{			Cell libCell = e.getKey();			CheckProto subCP = e.getValue();			if (subCP.hierInstanceCount > 0)			{				// allocate net number lists for every net in the cell				for(Iterator<Network> nIt = subCP.netlist.getNetworks(); nIt.hasNext(); )				{					Network net = nIt.next();					Integer [] netNumbers = new Integer[subCP.hierInstanceCount];					for(int i=0; i<subCP.hierInstanceCount; i++) netNumbers[i] = new Integer(0);					networkLists.put(net, netNumbers);					//totalNetworks += subCP.hierInstanceCount;				}			}			for(Iterator<NodeInst> nIt = libCell.getNodes(); nIt.hasNext(); )			{				NodeInst ni = nIt.next();				NodeProto np = ni.getProto();				if (!ni.isCellInstance()) continue;				// ignore documentation icons				if (ni.isIconOfParent()) continue;				CheckInst ci = checkInsts.get(ni);				CheckProto ocp = getCheckProto((Cell)np);				ci.offset = ocp.totalPerCell;			}			reportInfo.checkTimeStamp++;			for(Iterator<NodeInst> nIt = libCell.getNodes(); nIt.hasNext(); )			{				NodeInst ni = nIt.next();				NodeProto np = ni.getProto();				if (!ni.isCellInstance()) continue;				// ignore documentation icons				if (ni.isIconOfParent()) continue;				CheckProto ocp = getCheckProto((Cell)np);				if (ocp.timeStamp != reportInfo.checkTimeStamp)				{					CheckInst ci = checkInsts.get(ni);					ocp.timeStamp = reportInfo.checkTimeStamp;					ocp.totalPerCell += subCP.hierInstanceCount * ci.multiplier;				}			}		}		// now fill in the hierarchical network arrays		reportInfo.checkTimeStamp = 0;		int checkNetNumber = 1;		HashMap<Network,Integer> enumeratedNets = new HashMap<Network,Integer>();		for(Iterator<Network> nIt = cp.netlist.getNetworks(); nIt.hasNext(); )		{			Network net = nIt.next();			enumeratedNets.put(net, new Integer(checkNetNumber));			checkNetNumber++;		}		checkEnumerateNetworks(cell, cp, 0, enumeratedNets);		if (count <= 0)			System.out.println("Found " + checkNetNumber + " networks");		// now search for DRC exclusion areas        reportInfo.exclusionMap.clear();		accumulateExclusion(cell);		// now do the DRC        int logsFound = 0;//        int totalErrors = 0;		if (count == 0)		{