drc.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: DRC.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.tool.drc;

import com.sun.electric.database.CellBackup;
import com.sun.electric.database.ImmutableArcInst;
import com.sun.electric.database.ImmutableNodeInst;
import com.sun.electric.database.Snapshot;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.constraint.Layout;
import com.sun.electric.database.geometry.*;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Library;
import com.sun.electric.database.hierarchy.HierarchyEnumerator;
import com.sun.electric.database.hierarchy.Nodable;
import com.sun.electric.database.id.CellId;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.text.Pref;
import com.sun.electric.database.text.TextUtils;
import com.sun.electric.database.text.Version;
import com.sun.electric.database.topology.*;
import com.sun.electric.database.variable.Variable;
import com.sun.electric.technology.*;
import com.sun.electric.technology.technologies.Artwork;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.technology.technologies.Schematics;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.JobException;
import com.sun.electric.tool.Listener;
import com.sun.electric.tool.user.ErrorLogger;
import com.sun.electric.tool.user.User;

import java.awt.geom.Area;
import java.awt.geom.Rectangle2D;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.prefs.Preferences;
import java.io.Serializable;

/**
 * This is the Design Rule Checker tool.
 */
public class DRC extends Listener
{
	/** the DRC tool. */								     protected static DRC tool = new DRC();
	/** overrides of rules for each technology. */		     private static Map<Technology,Pref> prefDRCOverride = new HashMap<Technology,Pref>();
	/** map of cells and their objects to DRC */		     private static Map<Cell,Set<Geometric>> cellsToCheck = new HashMap<Cell,Set<Geometric>>();
    /** to temporary store DRC dates for spacing checking */ private static Map<Cell,StoreDRCInfo> storedSpacingDRCDate = new HashMap<Cell,StoreDRCInfo>();
    /** to temporary store DRC dates for area checking */    private static Map<Cell,StoreDRCInfo> storedAreaDRCDate = new HashMap<Cell,StoreDRCInfo>();
    /** for logging incremental errors */                    private static ErrorLogger errorLoggerIncremental = ErrorLogger.newInstance("DRC (incremental)", true);
    static final double TINYDELTA = DBMath.getEpsilon()*1.1;
    /** key of Variable holding DRC Cell annotations. */	static final Variable.Key DRC_ANNOTATION_KEY = Variable.newKey("ATTR_DRC");

    static Layer.Function.Set getMultiLayersSet(Layer layer)
    {
        Layer.Function.Set thisLayerFunction = (layer.getFunction().isPoly()) ?
        new Layer.Function.Set(Layer.Function.POLY1, Layer.Function.GATE) :
        new Layer.Function.Set(layer.getFunction(), layer.getFunctionExtras());
        return thisLayerFunction;
    }

    /**
	 * Method to see if polygons in "pList" (describing arc "ai") should be cropped against a
     * connecting transistor.  Crops the polygon if so.
     */
    static void cropActiveArc(ArcInst ai, boolean ignoreCenterCuts, Poly [] pList)
    {
        // look for an active layer in this arc
        int tot = pList.length;
        int diffPoly = -1;
        for(int j=0; j<tot; j++)
        {
            Poly poly = pList[j];
            Layer layer = poly.getLayer();
            if (layer == null) continue;
            Layer.Function fun = layer.getFunction();
            if (fun.isDiff()) { diffPoly = j;   break; }
        }
        if (diffPoly < 0) return;
        Poly poly = pList[diffPoly];

        // must be manhattan
        Rectangle2D polyBounds = poly.getBox();
        if (polyBounds == null) return;
        polyBounds = new Rectangle2D.Double(polyBounds.getMinX(), polyBounds.getMinY(), polyBounds.getWidth(), polyBounds.getHeight());

        // search for adjoining transistor in the cell
        boolean cropped = false;
        boolean halved = false;
        for(int i=0; i<2; i++)
        {
            PortInst pi = ai.getPortInst(i);
            NodeInst ni = pi.getNodeInst();
            if (!ni.getFunction().isFET()) continue;

            // crop the arc against this transistor
            AffineTransform trans = ni.rotateOut();
            Technology tech = ni.getProto().getTechnology();
            Poly [] activeCropPolyList = tech.getShapeOfNode(ni, false, ignoreCenterCuts, null);
            int nTot = activeCropPolyList.length;
            for(int k=0; k<nTot; k++)
            {
                Poly nPoly = activeCropPolyList[k];
                if (nPoly.getLayer() != poly.getLayer()) continue;
                nPoly.transform(trans);
                Rectangle2D nPolyBounds = nPoly.getBox();
                if (nPolyBounds == null) continue;
                // @TODO Why only one half is half crop?
                // Should I change cropBox by cropBoxComplete?
                int result = (halved) ?
                        Poly.cropBox(polyBounds, nPolyBounds) :
                        Poly.halfCropBox(polyBounds, nPolyBounds);

                if (result == 1)
                {
                    // remove this polygon from consideration
                    poly.setLayer(null);
                    return;
                }
                cropped = true;
                halved = true;
            }
        }
        if (cropped)
        {
            Poly.Type style = poly.getStyle();
            Layer layer = poly.getLayer();
            poly = new Poly(polyBounds);
            poly.setStyle(style);
            poly.setLayer(layer);
            pList[diffPoly] = poly;
        }
    }

    /**
         * Method to examine cell "cell" in the area (lx<=X<=hx, ly<=Y<=hy) for objects
     * on layer "layer".  Apply transformation "moreTrans" to the objects.  If polygons are
     * found at (xf1,yf1) or (xf2,yf2) or (xf3,yf3) then sets "p1found/p2found/p3found" to 1.
     *  If poly1 or poly2 is not null, ignore geometries that are identical to them.
     * If all locations are found, returns true.
     */
    static boolean lookForLayerCoverage(Geometric geo1, Poly poly1, Geometric geo2, Poly poly2, Cell cell,
                                   Layer layer, AffineTransform moreTrans, Rectangle2D bounds,
                                   Point2D pt1, Point2D pt2, Point2D pt3, boolean[] pointsFound,
                                   boolean overlap, Layer.Function.Set layerFunction, boolean ignoreSameGeometry,
                                   boolean ignoreCenterCuts)
    {
        int j;
        Rectangle2D newBounds = new Rectangle2D.Double();  // Sept 30

        for (Iterator<RTBounds> it = cell.searchIterator(bounds); it.hasNext();)
        {
            RTBounds g = it.next();

            // You can't skip the same geometry otherwise layers in the same Geometric won't
            // be tested.
            // But it is necessary while testing flat geometries... in minWidthInternal
            if (ignoreSameGeometry && (g == geo1 || g == geo2))
                continue;

            // I can't skip geometries to exclude from the search
            if (g instanceof NodeInst)
            {
                NodeInst ni = (NodeInst) g;
                if (NodeInst.isSpecialNode(ni))
                    continue; // Nov 16, no need for checking pins or other special nodes;
                if (ni.isCellInstance())
                {
                    // compute bounding area inside of sub-cell
                    AffineTransform rotI = ni.rotateIn();
                    AffineTransform transI = ni.translateIn();
                    rotI.preConcatenate(transI);
                    newBounds.setRect(bounds);
                    DBMath.transformRect(newBounds, rotI);

                    // compute new matrix for sub-cell examination
                    AffineTransform trans = ni.translateOut(ni.rotateOut());
                    trans.preConcatenate(moreTrans);
                    if (lookForLayerCoverage(geo1, poly1, geo2, poly2, (Cell) ni.getProto(), layer, trans, newBounds,
                        pt1, pt2, pt3, pointsFound, overlap, layerFunction, false, ignoreCenterCuts))
                        return true;
                    continue;
                }
                AffineTransform bound = ni.rotateOut();
                bound.preConcatenate(moreTrans);
                Technology tech = ni.getProto().getTechnology();
                // I have to ask for electrical layers otherwise it will retrieve one polygon for polysilicon
                // and poly.polySame(poly1) will never be true. CONTRADICTION!
                Poly[] layerLookPolyList = tech.getShapeOfNode(ni, false, ignoreCenterCuts, layerFunction); // consistent change!);
                int tot = layerLookPolyList.length;
                for (int i = 0; i < tot; i++)
                {
                    Poly poly = layerLookPolyList[i];
                    // sameLayer test required to check if Active layer is not identical to thick active layer
                    if (!tech.sameLayer(poly.getLayer(), layer))
                    {
                        continue;
                    }

                    // Should be the transform before?
                    poly.transform(bound);

                    if (poly1 != null && !overlap && poly.polySame(poly1))
                        continue;
                    if (poly2 != null && !overlap && poly.polySame(poly2))
                        continue;

                    if (!pointsFound[0] && poly.isInside(pt1))
                        pointsFound[0] = true; // @TODO Should still evaluate isInside if pointsFound[i] is already valid?
                    if (!pointsFound[1] && poly.isInside(pt2)) pointsFound[1] = true;
                    if (pt3 != null && !pointsFound[2] && poly.isInside(pt3)) pointsFound[2] = true;
                    for (j = 0; j < pointsFound.length && pointsFound[j]; j++) ;
                    if (j == pointsFound.length) return true;
                    // No need of checking rest of the layers
                    break; // assuming only 1 polygon per layer (non-electrical)
                }
            } else
            {
                ArcInst ai = (ArcInst) g;
                Technology tech = ai.getProto().getTechnology();
                Poly[] layerLookPolyList = tech.getShapeOfArc(ai, layerFunction); // consistent change!);
                int tot = layerLookPolyList.length;
                for (int i = 0; i < tot; i++)
                {
                    Poly poly = layerLookPolyList[i];
                    // sameLayer test required to check if Active layer is not identical to thich actice layer
                    if (!tech.sameLayer(poly.getLayer(), layer))
                    {
                        continue;
                    }
                    poly.transform(moreTrans);  // @TODO Should still evaluate isInside if pointsFound[i] is already valid?
                    if (!pointsFound[0] && poly.isInside(pt1)) pointsFound[0] = true;
                    if (!pointsFound[1] && poly.isInside(pt2)) pointsFound[1] = true;
                    if (pt3 != null && !pointsFound[2] && poly.isInside(pt3)) pointsFound[2] = true;
                    for (j = 0; j < pointsFound.length && pointsFound[j]; j++) ;
                    if (j == pointsFound.length) return true;
                    // No need of checking rest of the layers
                    break;
                }
            }

            for (j = 0; j < pointsFound.length && pointsFound[j]; j++) ;
            if (j == pointsFound.length)
            {
                assert (false); // test when otherwise the calculation is useless! System.out.println("When?");
                return true;
            }
        }
        return false;
    }

    /**
         * Method to determine if neighbor would help to cover the minimum conditions
 *
 * @return true if error was found (not warning)
 */
static boolean checkExtensionWithNeighbors(Cell cell, Geometric geom, Poly poly, Layer layer, Rectangle2D bounds,
                                            DRCTemplate minWidthRule, int dir, boolean onlyOne, boolean reportError,
                                            Layer.Function.Set layerFunction, ReportInfo reportInfo)
{
    double actual = 0;
    Point2D left1, left2, left3, right1, right2, right3;
    //if (bounds.getWidth() < minWidthRule.value)
    String msg = "";

    // potential problem along X
    if (dir == 0)
    {
        actual = bounds.getWidth();
        msg = "(X axis)";
        double leftW = bounds.getMinX() - TINYDELTA;
        left1 = new Point2D.Double(leftW, bounds.getMinY());
        left2 = new Point2D.Double(leftW, bounds.getMaxY());
        left3 = new Point2D.Double(leftW, bounds.getCenterY());
        double rightW = bounds.getMaxX() + TINYDELTA;
        right1 = new Point2D.Double(rightW, bounds.getMinY());
        right2 = new Point2D.Double(rightW, bounds.getMaxY());
        right3 = new Point2D.Double(rightW, bounds.getCenterY());
    } else
    {
        actual = bounds.getHeight();
        msg = "(Y axis)";
        double leftH = bounds.getMinY() - TINYDELTA;
        left1 = new Point2D.Double(bounds.getMinX(), leftH);
        left2 = new Point2D.Double(bounds.getMaxX(), leftH);
        left3 = new Point2D.Double(bounds.getCenterX(), leftH);
        double rightH = bounds.getMaxY() + TINYDELTA;
        right1 = new Point2D.Double(bounds.getMinX(), rightH);
        right2 = new Point2D.Double(bounds.getMaxX(), rightH);
        right3 = new Point2D.Double(bounds.getCenterX(), rightH);
    }
    // see if there is more of this layer adjoining on either side
    boolean[] pointsFound = new boolean[3];
    pointsFound[0] = pointsFound[1] = pointsFound[2] = false;