layoutcell.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: LayoutCell.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.constraint;

import com.sun.electric.database.CellBackup;
import com.sun.electric.database.ImmutableArcInst;
import com.sun.electric.database.ImmutableNodeInst;
import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.geometry.EPoint;
import com.sun.electric.database.geometry.Orientation;
import com.sun.electric.database.geometry.Poly;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.id.CellUsage;
import com.sun.electric.database.id.PortProtoId;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.text.ImmutableArrayList;
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.variable.ElectricObject;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.PrimitivePort;
import com.sun.electric.tool.user.User;

import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * Class to implement the layout-constraint system for a specific Cell.
 * Handles the fixed-angle and rigid constraints.
 */
class LayoutCell {
	/**
	 * The meaning of changeClock for object modification:
	 *
	 * ai.getChangeClock() <  changeClock-2  unmodified         arcs
	 * ai.getChangeClock() == changeClock-2  unmodified rigid   arcs
	 * ai.getChangeClock() == changeClock-1  unmodified unrigid arcs
	 * ai.getChangeClock() == changeClock      modified rigid   arcs
	 * ai.getChangeClock() == changeClock+1    modified unrigid arcs
	 * ni.getChangeClock() <  changeClock-1  unmodified         nodes
	 * ni.getChangeClock() == changeClock-1  size-changed       nodes
	 * ni.getChangeClock() == changeClock    position-changed   nodes
	 */
    private static final Integer AI_RIGID = new Integer(0);
    private static final Integer AI_FLEX = new Integer(1);

    final Cell cell;
    private HashMap<Export,PortInst> oldExports;
    private HashMap<ArcInst,ImmutableArcInst> oldArcs;
    private LinkedHashMap<NodeInst,ImmutableNodeInst> oldNodes = new LinkedHashMap<NodeInst,ImmutableNodeInst>();


    /** True if this Cell needs to be computed. */
    private boolean modified;
    /** True if change of Exports of this Cell causes recomputation of upper Cells. */
    private boolean exportsModified;
//    /** True if subcells changed names of Library:Cell:Export */
//    private boolean subcellsRenamed;
    /** True if this Cell is computed by Layout constraint system. */
    private boolean computed;
    /** Backup of this Cell before Job */
    private final CellBackup oldBackup;

//    /** Map from ArcInst to its change clock */
//    private HashMap<Geometric,Integer> changeClock;
    /** Set of nodes already moved not to move twice. */
    private HashSet<NodeInst> movedNodes;
    private CellBackup.Memoization m;

    LayoutCell(Cell cell, CellBackup oldBackup) {
        this.cell = cell;
        this.oldBackup = oldBackup;
    }

    /**
     * Recursively compute this cell and all its subcells in bottom-up order.
     */
    void compute() {
        if (computed) return;
        computed = true;
        for (Iterator<CellUsage> it = cell.getUsagesIn(); it.hasNext(); ) {
            CellUsage u = it.next();
            Layout.getCellInfo(u.getProto()).compute();
        }
        if (modified || exportsModified) {
            doCompute();
            if (exportsModified) {
                for (Iterator<CellUsage> it = cell.getUsagesOf(); it.hasNext(); ) {
                    CellUsage u = it.next();
                    Layout.getCellInfo(u.getParent()).modified = true;
                }
            }
        }
        // Release unnecessary memory
        oldArcs = null;
//        changeClock = null;
        movedNodes = null;
    }

    /**
     * Compute this Cell.
     **/
    private void doCompute() {
//        changeClock = new HashMap<Geometric,Integer>();
        movedNodes = new HashSet<NodeInst>();
        m = cell.getMemoization();

        LinkedHashSet<NodeInst> modifiedInsts = new LinkedHashSet<NodeInst>();
        for (Iterator<NodeInst> it = cell.getNodes(); it.hasNext(); ) {
            NodeInst ni = it.next();
            boolean portsModified;
            if (ni.isCellInstance()) {
                LayoutCell subCell = Layout.getCellInfo((Cell)ni.getProto());
                portsModified = subCell.exportsModified;
            } else {
                ImmutableNodeInst d = getOldD(ni);
                portsModified = d != null && d.size != ni.getD().size;
            }
            if (portsModified) {
                modifiedInsts.add(ni);
            }
        }
        if (oldNodes != null) {
            for (Map.Entry<NodeInst,ImmutableNodeInst> e : oldNodes.entrySet()) {
                NodeInst ni = e.getKey();
                ImmutableNodeInst d = e.getValue();
                if (d != null) {
                    modifiedInsts.add(ni);
                    if (!ni.getAnchorCenter().equals(d.anchor) || !ni.getOrient().equals(d.orient))
                        movedNodes.add(ni);
                }
            }
        }
        for (NodeInst ni : modifiedInsts) {
            if (hasExports(ni))
//            if (ni.hasExports())
                exportsModified = true;
            ImmutableNodeInst d = getOldD(ni);
            Orientation dOrient = d != null ? ni.getOrient().concatenate(d.orient.inverse()) : Orientation.IDENT;
            modNodeArcs(ni, dOrient);
        }
        if (oldArcs != null) {
            ArcInst[] oldArcsCopy = oldArcs.keySet().toArray(ArcInst.NULL_ARRAY);
            for (ArcInst ai: oldArcsCopy) {
                if (!ai.isLinked()) continue;
                ensureArcInst(ai, Layout.isRigid(ai) ? AI_RIGID : AI_FLEX);
            }
        }
        m = null;
    }

	/**
	 * Method to modify nodeinst "ni" by "deltalx" in low X, "deltaly" in low Y,
	 * "deltahx" in high X, "deltahy" in high Y, and "dangle" tenth-degrees.
	 * If the nodeinst is a portproto of the current cell and has any arcs
	 * connected to it, the method returns nonzero to indicate that the outer
	 * cell has ports that moved (the nodeinst has exports).
	 */
	private void alterNodeInst(NodeInst ni, double deltaCX, double deltaCY, Orientation dOrient)
	{
		// reject if this change has already been done
        if (deltaCX == 0 && deltaCY == 0 && dOrient.equals(Orientation.IDENT)) return;
        if (movedNodes.contains(ni)) return;

		if (Layout.DEBUG) System.out.println("Moving "+ni+" [is "+ni.getXSize()+"x"+ni.getYSize()+" at ("+
                ni.getAnchorCenterX()+","+ni.getAnchorCenterY()+") rot "+ni.getOrient()+
			"] change is dx="+deltaCX+" dy="+deltaCY+") dOrient="+dOrient);

        ni.modifyInstance(deltaCX, deltaCY, 0, 0, dOrient);
        movedNodes.add(ni);

		// see if this nodeinst is a port of the current cell
		if (hasExports(ni))
//		if (ni.hasExports())
            exportsModified = true;
	}

	/**
	 * Method to modify all of the arcs connected to a NodeInst.
	 * @param ni the NodeInst being examined.
	 * @param dSX the change in the node's X size.
	 * @param dSY the change in the node's Y size.
	 * @param dOrient the change of Orientation of the NodeInst.
	 * @return true if some exports on the current cell have moved.
	 * This indicates that the cell must be re-examined for export locations.
	 */
	private void modNodeArcs(NodeInst ni, Orientation dOrient)
	{
		if (Layout.DEBUG) System.out.println("Updating arcs on "+ni);

		// next look at arcs that run within this nodeinst
		modWithin(ni, dOrient);

		// next look at the rest of the rigid arcs on this nodeinst
		modRigid(ni, dOrient);

		// finally, look at rest of the flexible arcs on this nodeinst
		modFlex(ni, dOrient);
	}

	/*
	 * Method to modify the arcs that run within nodeinst "ni"
	 */
	private void modWithin(NodeInst ni, Orientation dOrient)
	{
		// ignore all this stuff if the node just got created
		if (getOldD(ni) == null) return;

		// build a list of the arcs with both ends on this nodeinst
		List<ArcInst> interiorArcs = new ArrayList<ArcInst>();
		for(Iterator<Connection> it = getConnections(ni); it.hasNext(); )
//		for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
		{
			Connection con = it.next();
			ArcInst ai = con.getArc();

			// ignore if arcinst is not within the node
			if (ai.getHeadPortInst().getNodeInst() != ai.getTailPortInst().getNodeInst()) continue;
//			if (getChangeClock(ai) == AI_RIGID.intValue()) continue;

			// include in the list to be considered here
			interiorArcs.add(ai);
		}

		// look for arcs with both ends on this nodeinst
		for(ArcInst ai : interiorArcs)
		{
			if (!ai.isLinked()) continue;

			// if arcinst has already been changed check its connectivity
			if (arcMoved(ai))
//			if (getChangeClock(ai) == AI_RIGID.intValue())
			{
				if (Layout.DEBUG) System.out.println("    Arc already changed");
				ensureArcInst(ai, AI_RIGID);
				continue;
			}

			// determine the new ends of the arcinst
			AffineTransform trans = transformByPort(ai.getHeadPortInst());
			Point2D newHead = new Point2D.Double();
			trans.transform(ai.getHeadLocation(), newHead);

			trans = transformByPort(ai.getTailPortInst());
			Point2D newTail = new Point2D.Double();
			trans.transform(ai.getTailLocation(), newTail);

			// move the arcinst
			doMoveArcInst(ai, newHead, newTail, AI_RIGID);
		}
	}

	/**
	 * Method to modify the rigid arcs connected to a NodeInst.
	 * @param ni the NodeInst being examined.
	 * @param dOrient the change in the node Orientation.
	 * @return true if any nodes that have exports move.
	 * This indicates that instances of the current cell must be examined for ArcInst motion.
	 */
	private void modRigid(NodeInst ni, Orientation dOrient)
	{
		// build a list of the rigid arcs on this nodeinst
		List<Connection> rigidArcs = new ArrayList<Connection>();
		for(Iterator<Connection> it = getConnections(ni); it.hasNext(); )
//		for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
		{
			Connection con = it.next();
			ArcInst ai = con.getArc();

			// ignore if arcinst is not flexible
//			if (getChangeClock(ai) == AI_FLEX.intValue()) continue;
			if (!Layout.isRigid(ai)) continue;

			// ignore arcs that connect two ports on the same node
			if (ai.getHeadPortInst().getNodeInst() == ai.getTailPortInst().getNodeInst()) continue;

			// include in the list to be considered here
            rigidArcs.add(con);
		}
		if (rigidArcs.size() == 0) return;

		// look for rigid arcs on this nodeinst
        HashSet<ArcInst> rigidModified = new HashSet<ArcInst>();
		for(Connection thisEnd : rigidArcs)
		{
            ArcInst ai = thisEnd.getArc();
			if (!ai.isLinked()) continue;
			if (Layout.DEBUG) System.out.println("  From " + ni + " Modifying Rigid "+ai);

			// if rigid arcinst has already been changed check its connectivity
			if (arcMoved(ai))
//			if (getChangeClock(ai) == AI_RIGID.intValue())
			{
				if (Layout.DEBUG) System.out.println("    Arc already changed");
				ensureArcInst(ai, AI_RIGID);
				continue;
			}

			// find out which end of the arcinst is where, ignore internal arcs
            int thisEndIndex = thisEnd.getEndIndex();
            int otherEndIndex = 1 - thisEndIndex;

			PortInst opi = ai.getPortInst(otherEndIndex);
			NodeInst ono = opi.getNodeInst();
//			PortProto opt = opi.getPortProto();
			EPoint otherLocation = ai.getLocation(otherEndIndex);

			// create the two points that will be the new ends of this arc
            AffineTransform trans = transformByPort(thisEnd.getPortInst());
			Point2D [] newPts = new Point2D.Double[2];
			newPts[0] = new Point2D.Double();
			newPts[1] = new Point2D.Double();

			// figure out the new location of this arcinst connection
			trans.transform(thisEnd.getLocation(), newPts[thisEndIndex]);

			// figure out the new location of that arcinst connection
			trans.transform(otherLocation, newPts[otherEndIndex]);

			// see if other nodeinst has changed
			boolean locked = false;
			if (movedNodes.contains(ono)) locked = true; else
			{
				if (ono.isLocked()) locked = true; else
				{
					if (ono.isCellInstance())
					{
						if (ono.getParent().isInstancesLocked()) locked = true;
						if (User.isDisallowModificationComplexNodes()) locked = true;
					} else
					{
						if (User.isDisallowModificationLockedPrims() &&
							((PrimitiveNode)ono.getProto()).isLockedPrim()) locked = true;
						if (User.isDisallowModificationComplexNodes())
						{
							PrimitiveNode.Function fun = ono.getFunction();
							if (fun != PrimitiveNode.Function.PIN && fun != PrimitiveNode.Function.CONTACT &&
								fun != PrimitiveNode.Function.NODE && fun != PrimitiveNode.Function.CONNECT)
									locked = true;
						}
					}
				}
			}
			if (!locked)
			{
				// compute port motion within the other nodeinst (is this right? !!!)
				Poly oldPoly = Layout.oldPortPosition(opi);
				Poly oPoly = opi.getPoly();
                if (oldPoly == null) oldPoly = oPoly;
				double oldX = oldPoly.getCenterX();
				double oldY = oldPoly.getCenterY();
				double dx = oPoly.getCenterX();   double dy = oPoly.getCenterY();
				double othX = dx - oldX;
				double othY = dy - oldY;