DIRECTORY Basics, DFUtilities, FS, IO, LichenDataStructure, LichenOps, List, RedBlackTree, RedBlackTreeExtras, RefTab, Rope, ViewerIO;

LichenNormal: CEDAR PROGRAM
IMPORTS IO, LichenDataStructure, LichenOps, RedBlackTree, RedBlackTreeExtras, RefTab, Rope
EXPORTS LichenOps =

BEGIN OPEN LichenDataStructure, LichenOps;


Broken: ERROR = CODE;
BadData: ERROR = CODE;
NotNormal: PUBLIC ERROR [msg: ROPE] = CODE;
NotComparable: PUBLIC ERROR [msg: ROPE] = CODE;

debugging: BOOL _ TRUE;
OutersToo: BOOL = FALSE;

CheckDesign: PROC [design: Design, norm: AssertionOp, comparable: MerelyCheckableAssertionOp] = {
PerCellType: PROC [ra: REF ANY] RETURNS [quit: BOOL] = {
ct: CellType _ NARROW[ra];
quit _ FALSE;
CheckType[ct, norm, comparable];
};
SELECT norm FROM
ignore => NULL;
report, check, establish => EnsureAllIn[design];
ENDCASE => ERROR;
RedBlackTreeExtras.StatelessEnumerateIncreasing[design.cellTypesByAddress, PerCellType, GetIDKey];
};

PortData: TYPE = REF PortDataRep;
PortDataRep: TYPE = RECORD [data: SEQUENCE length: NAT OF PortDatum];
PortDatum: TYPE = RECORD [
used, seen, deleted: BOOL _ FALSE,
assoc: LIST OF NAT _ NIL,
newPortIndex: NAT _ NullPortIndex];

CheckType: PUBLIC PROC [ct: CellType, norm: AssertionOp, comparable: MerelyCheckableAssertionOp, ignoreInstances: BOOL _ FALSE] = {
lastInstance: Vertex _ NIL;
netCount, cellCount: NAT _ 0;
portData: PortData;
consequences: RefTab.Ref _ SELECT norm FROM
establish => RefTab.Create[],
ignore, report, check => NIL,
ENDCASE => ERROR;
altered: BOOL _ FALSE;
PerPart: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
a: Alias _ NARROW[ra];
v: Vertex _ NARROW[a.thing];
stop _ FALSE;
IF PickAName[v.names] # a.name THEN RETURN;
IF IsMirror[v] THEN ERROR Broken;	--AM1
IF v.parent # ct THEN ERROR Broken;
CheckAllDictness[v.names, ct.parts, v, TRUE];
SELECT v.class FROM
net => {netCount _ netCount + 1; IF CheckNet[v, norm, comparable, consequences] THEN altered _ TRUE};
cell => {cellCount _ cellCount + 1; CheckComponent[v]};
ENDCASE => ERROR;
};
portsDict: SymbolTable _ RedBlackTree.Create[GetIDKey, CompareRopes];
SELECT norm FROM
ignore, report, check => NULL;
establish => IF ignoreInstances THEN ERROR;
ENDCASE => ERROR;
IF ct.privateKnown AND NOT ct.publicKnown THEN ERROR Broken;
CheckAllDictness[ct.names, ct.design.cellTypesByName, ct, TRUE];
EnsureParts[ct];
EnsurePorts[ct];
IF ct.privateKnown AND NOT ct.publicKnown THEN ERROR Broken;
SELECT comparable FROM
ignore => NULL;
report, check => CheckComparable[ct.names, ct.equivClass, comparable, GlobalCellTypeName[ct], "ACCellTypeEquivd"];
ENDCASE => ERROR;
FOR pi: PortIndex IN [0 .. ct.ports.length) DO
CheckNames: PROC [nameList: RopeList] = {
FOR nameList _ nameList, nameList.rest WHILE nameList # NIL DO
portsDict.Insert[nameList.first, nameList.first !RedBlackTree.DuplicateKey => ERROR BadData];
ENDLOOP};
IF ExpansionKnown[ct] THEN SELECT GetInternalStyle[ct] FROM
graph => {
theNet: Vertex _ NARROW[Lookup[ct.parts, ct.ports[pi].netNames.first]];
IF theNet = NIL THEN ERROR BadData;
FOR nnl: RopeList _ ct.ports[pi].netNames.rest, nnl.rest WHILE nnl # NIL DO
IF Lookup[ct.parts, nnl.first] # theNet THEN ERROR BadData;
ENDLOOP;
};
array => NULL;
ENDCASE => ERROR;
SELECT comparable FROM
ignore => NULL;
report, check => CheckComparable[ct.ports[pi].names, ct.ports[pi].equivClass, comparable, GlobalPortName[ct, pi], "ACPortEquivd"];
ENDCASE => ERROR;
CheckNames[ct.ports[pi].names.designed];
CheckNames[ct.ports[pi].names.unknown];
CheckNames[ct.ports[pi].names.progged];
ENDLOOP;
portsDict.DestroyTable[];
IF NOT ignoreInstances THEN {
SELECT norm FROM
ignore => NULL;
report, check, establish => {
ct.wasntNormalized _ FALSE;
portData _ NEW [PortDataRep[ct.ports.length]];
FOR i: NAT IN [0 .. portData.length) DO portData[i] _ [] ENDLOOP;
};
ENDCASE => ERROR;
FOR v: Vertex _ ct.firstInstance, v.nextInstance WHILE v # NIL DO
IF v.prevInstance # lastInstance THEN ERROR Broken;
IF v.type # ct THEN ERROR Broken;
IF IsMirror[v] THEN ERROR Broken;	--AM2
CheckAllDictness[v.names, v.parent.parts, v, TRUE];
CheckInstance[v: v, portData: portData, norm: norm];
lastInstance _ v;
ENDLOOP;
IF ct.lastInstance # lastInstance THEN ERROR Broken;
SELECT norm FROM
ignore => NULL;
report, check => IF OutersToo THEN {
FOR pi: NAT IN [0 .. portData.length) DO
IF NOT portData[pi].used THEN Fail[normal, norm, "%g fails ANPortUsedO", IO.rope[GlobalPortName[ct, pi]]];
IF portData[pi].assoc # NIL THEN Fail[normal, norm, "%g fails ANPortsMergedO", IO.rope[GlobalPortName[ct, pi]]];
ENDLOOP;
};
establish => IF OutersToo THEN {
pi: NAT _ 0;
WHILE pi < portData.length DO
IF (NOT portData[pi].used) AND (portData[pi].assoc # NIL) THEN ERROR;
IF NOT portData[pi].used THEN {
IF debugging THEN Log["Deleting %g\n", IO.rope[GlobalPortName[ct, pi]]];
portData _ DeletePort[ct, pi, portData, consequences];
ct.wasntNormalized _ TRUE;
CheckType[ct, ignore, comparable]}
ELSE IF portData[pi].assoc # NIL THEN {
IF debugging THEN {
Log["On Type %g, merging ports", IO.rope[GlobalCellTypeName[ct]]];
FOR pil: LIST OF NAT _ portData[pi].assoc, pil.rest WHILE pil # NIL DO
Log[" %g", IO.rope[PickAName[ct.ports[pil.first].names]]];
ENDLOOP;
Log[".\n"]};
[portData, pi] _ MergePorts[ct, CONS[pi, portData[pi].assoc], portData, pi, consequences];
ct.wasntNormalized _ TRUE;
CheckType[ct, ignore, comparable]}
ELSE pi _ pi + 1;
ENDLOOP;
};
ENDCASE => ERROR;
};
IF ExpansionKnown[ct] THEN SELECT GetInternalStyle[ct] FROM
graph => {
IF ct.mirror = NIL THEN ERROR Broken;
IF ct.mirror.type # ct THEN ERROR Broken;
IF ct.mirror.parent # ct THEN ERROR Broken;
CheckAllDictness[ct.mirror.names, ct.parts, ct.mirror, FALSE];
RedBlackTreeExtras.StatelessEnumerateIncreasing[ct.parts, PerPart, GetAliasKey];
IF (NOT altered) AND (netCount # ct.netCount OR cellCount # ct.cellCount) THEN ERROR Broken;
CheckComponent[ct.mirror];
};
array => CheckArray[ct];
ENDCASE => ERROR;
IF NOT ignoreInstances THEN SELECT norm FROM
ignore => NULL;
report, check => IF ct.wasntNormalized THEN ERROR Broken;
establish => {
SELECT consequences.Fetch[ct].val FROM
$T => {
[] _ consequences.Delete[ct];
CheckType[ct, establish, comparable];
};
ENDCASE => IF ct.wasntNormalized THEN CheckType[ct, check, comparable];
[] _ consequences.Pairs[FixAffectedType];
};
ENDCASE => ERROR;
};

CheckArray: PROC [ct: CellType] = {
a: Array _ ct.asArray;
IF a.portConnections.arrayPorts # ct.ports.length THEN ERROR Broken;
IF a.eltPorts # a.eltType.ports.length THEN ERROR Broken;
FOR d: Dim IN Dim DO FOR perp: EO IN EO DO FOR parl: EO IN EO DO
j: Joint _ a.joints[d][perp][parl];
IF j = NIL THEN LOOP;
FOR pi: PortIndex IN [0 .. a.eltPorts) DO
lpi: PortIndex _ j[pi].low;
hpi: PortIndex _ j[pi].high;
IF lpi#NullPortIndex AND j[lpi].high # pi THEN ERROR;
IF hpi#NullPortIndex AND j[hpi].low # pi THEN ERROR;
ENDLOOP;
ENDLOOP ENDLOOP ENDLOOP;
FOR api: PortIndex IN [0 .. a.portConnections.arrayPorts) DO
FOR e: End IN End DO FOR d: Dim IN Dim DO
od: Dim _ OtherDim[d];
r: Range _ [0, 0];
FOR asl: ArraySocketList _ a.portConnections[api][e][d].sockets, asl.rest WHILE asl # NIL DO
ei: INT _ SELECT e FROM low => a.shape[d].min, high => (a.shape[d].maxPlusOne-1), ENDCASE => ERROR;
IF asl.first.ai[d] # ei THEN ERROR Broken;
IF r = [0, 0]
THEN r _ [asl.first.ai[od], asl.first.ai[od]+1]
ELSE {
IF r.maxPlusOne # asl.first.ai[od] THEN ERROR Broken;
r.maxPlusOne _ asl.first.ai[od] + 1;
};
IF GetArrayPort[a, asl.first.ai, asl.first.pi] # api THEN ERROR Broken;
ENDLOOP;
IF a.portConnections[api][e][d].range # r THEN ERROR Broken;
ENDLOOP ENDLOOP;
ENDLOOP;
};

CheckComparable: PROC [names: Names, equivClass: EquivClass, how: FailableAssertionOp, who, what: ROPE] = {
IF
equivClass = implicitClass AND
NOT (
IF names.designed # NIL THEN names.designed.rest = NIL ELSE
IF names.unknown # NIL THEN names.unknown.rest = NIL ELSE
IF names.progged # NIL THEN names.progged.rest = NIL ELSE
FALSE)
THEN Fail[comparable, how, "%g fails %g", IO.rope[who], IO.rope[what]];
};

CheckAllDictness: PROC [names: Names, dict: SymbolTable, obj: REF ANY, shouldFind: BOOL] = {
Work: PROC [rl: RopeList] = {
FOR rl _ rl, rl.rest WHILE rl # NIL DO
IF shouldFind # (AntiAlias[Lookup[dict, rl.first]] = obj) THEN ERROR Broken;
ENDLOOP;
rl _ rl};
Work[names.designed];
Work[names.unknown];
Work[names.progged]};

CheckInstance: PROC [v: Vertex, portData: PortData, norm: AssertionOp] = {
portIndex: NAT _ 0;
SELECT norm FROM
ignore => {
FOR e: Edge _ v.firstEdge, e.sides[cell].next WHILE e # NIL DO
net: Vertex _ e.sides[net].v;
IF e.sides[cell].v # v THEN ERROR Broken;
IF e.portIndex # portIndex THEN ERROR Broken;
portIndex _ portIndex + 1;
ENDLOOP;
IF portIndex # v.type.ports.length THEN ERROR Broken;
};
report, check, establish => {
FOR e: Edge _ v.firstEdge, e.sides[cell].next WHILE e # NIL DO
net: Vertex _ e.sides[net].v;
IF e.sides[cell].v # v THEN ERROR Broken;
IF e.portIndex # portIndex THEN ERROR Broken;
FOR pi: NAT IN [0 .. portData.length) DO portData[pi].seen _ FALSE ENDLOOP;
FOR f: Edge _ net.firstEdge, f.sides[net].next WHILE f # NIL DO
u: Vertex _ f.sides[cell].v;
IF f.sides[net].v # net THEN ERROR Broken;
IF f.sides[cell].v = v THEN portData[f.portIndex].seen _ TRUE;
IF f.sides[cell].v # v OR f.portIndex # portIndex THEN portData[portIndex].used _ TRUE;
ENDLOOP;
IF NOT portData[portIndex].seen THEN ERROR Broken;
IF v = v.type.firstInstance THEN {
portData[portIndex].assoc _ NIL;
FOR pi: NAT IN [0 .. portData.length) DO
IF portData[pi].seen AND pi # portIndex THEN portData[portIndex].assoc _ CONS[pi, portData[portIndex].assoc];
ENDLOOP;
}
ELSE {
lastAssoc: LIST OF NAT _ NIL;
FOR la: LIST OF NAT _ portData[portIndex].assoc, la.rest WHILE la # NIL DO
IF NOT portData[la.first].seen THEN {
IF lastAssoc = NIL THEN portData[portIndex].assoc _ la.rest ELSE lastAssoc.rest _ la.rest
}
ELSE lastAssoc _ la;
ENDLOOP;
};
portIndex _ portIndex + 1;
ENDLOOP;
IF portIndex # v.type.ports.length THEN ERROR Broken;
};
ENDCASE => ERROR;
};

CheckNet: PROC [v: Vertex, norm: AssertionOp, comparable: MerelyCheckableAssertionOp, noteIn: RefTab.Ref] RETURNS [altered: BOOL] = {
lastEdge: Edge _ NIL;
portCount, otherCount: NAT _ 0;
portIndices: LIST OF NAT _ NIL;
altered _ FALSE;
FOR e: Edge _ v.firstEdge, e.sides[net].next WHILE e # NIL DO
w: Vertex _ e.sides[cell].v;
IF e.sides[net].v # v THEN ERROR Broken;
IF e.sides[net].prev # lastEdge THEN ERROR Broken;
IF IsMirror[w] THEN {
portCount _ portCount + 1;
portIndices _ CONS[e.portIndex, portIndices];
}
ELSE otherCount _ otherCount + 1;
lastEdge _ e;
ENDLOOP;
IF v.lastEdge # lastEdge THEN ERROR Broken;
SELECT norm FROM
ignore => NULL;
report, check => {
IF portCount + otherCount = 0 THEN Fail[normal, norm, "%g fails ANNetUsed", IO.rope[GlobalVertexName[v]]];
IF portCount = 1 AND otherCount = 0 THEN Fail[normal, norm, "%g fails ANPortUsedI", IO.rope[GlobalVertexName[v]]];
IF portCount > 1 THEN Fail[normal, norm, "%g fails ANPortsMergedI", IO.rope[GlobalVertexName[v]]];
};
establish => {
IF portCount + otherCount = 0 THEN {
IF debugging THEN Log["Deleting net %g\n", IO.rope[GlobalVertexName[v]]];
altered _ TRUE;
[] _ noteIn.Store[v.parent, $T];
DeleteVertex[v];
v.parent.wasntNormalized _ TRUE;
CheckType[v.parent, ignore, comparable]};
IF portCount = 1 AND otherCount = 0 THEN {
IF debugging THEN Log["Deleting port %g\n", IO.rope[GlobalPortName[v.parent, portIndices.first]]];
altered _ TRUE;
[] _ noteIn.Store[v.parent, $T];
[] _ DeletePort[v.parent, portIndices.first, NIL, noteIn];
v.parent.wasntNormalized _ TRUE;
CheckType[v.parent, ignore, comparable]};
IF portCount > 1 THEN {
IF debugging THEN {
Log["On Type %g, merging ports", IO.rope[GlobalCellTypeName[v.parent]]];
FOR pil: LIST OF NAT _ portIndices, pil.rest WHILE pil # NIL DO
Log[" %g", IO.rope[PickAName[v.parent.ports[pil.first].names]]];
ENDLOOP;
Log[".\n"]};
altered _ TRUE;
[] _ noteIn.Store[v.parent, $T];
[] _ MergePorts[v.parent, portIndices, NIL, NullPortIndex, noteIn];
v.parent.wasntNormalized _ TRUE;
CheckType[v.parent, ignore, comparable]};
};
ENDCASE => ERROR;
};

CheckComponent: PROC [v: Vertex] = {
portIndex: NAT _ 0;
lastEdge: Edge _ NIL;
EnsurePorts[v.type];
FOR e: Edge _ v.firstEdge, e.sides[cell].next WHILE e # NIL DO
IF e.sides[cell].v # v THEN ERROR Broken;
IF e.sides[cell].prev # lastEdge THEN ERROR Broken;
IF e.portIndex # portIndex THEN ERROR Broken;
portIndex _ portIndex + 1;
lastEdge _ e;
ENDLOOP;
IF v.lastEdge # lastEdge THEN ERROR Broken;
IF portIndex # v.type.ports.length THEN ERROR Broken;
};

MergeNets: PUBLIC PROC [net1, net2: Vertex] RETURNS [merged, doomed: Vertex] =
BEGIN
Rename: PROC [name: ROPE, class: ATOM--UNION[$designed, $unknown, $progged]--] = {
a: Alias _ NARROW[net1.parent.parts.Lookup[name]];
IF a.thing # net2 THEN ERROR;
a.thing _ net1;
};
Relink: PROC [item: REF ANY] RETURNS [stop: BOOL] = {
ec: ExtraConnection _ NARROW[item];
stop _ FALSE;
IF ec.parentNet # net2 THEN ERROR;
IF net2.extraConnections.Delete[ec].data # ec THEN ERROR;
ec.parentNet _ net1;
IF net1.extraConnections = NIL THEN net1.extraConnections _ RedBlackTree.Create[GetIDKey, CompareECSubCellThenChildNet];
net1.extraConnections.Insert[ec, ec];
};
IF net1.parent # net2.parent THEN ERROR;
IF net1.class # net OR net2.class # net THEN ERROR;
IF net1 = net2 THEN RETURN [net1, NIL];
merged _ net1;
doomed _ net2;
EnumerateNames[net2.names, Rename];
net1.names _ MergeNames[net1.names, net2.names];
FOR e: Edge _ net2.firstEdge, e.sides[net].next WHILE e # NIL DO
IF e.sides[net].v # net2 THEN ERROR;
e.sides[net].v _ net1;
ENDLOOP;
IF net2.firstEdge # NIL THEN {
IF net1.lastEdge # NIL THEN net1.lastEdge.sides[net].next _ net2.firstEdge ELSE net1.firstEdge _ net2.firstEdge;
net1.lastEdge _ net2.lastEdge;
net2.firstEdge.sides[net].prev _ net1.lastEdge;
net2.firstEdge _ NIL;
net2.lastEdge _ NIL;
};
IF net2.extraConnections # NIL THEN RedBlackTreeExtras.StatelessEnumerateIncreasing[net2.extraConnections, Relink, GetIDKey];
END;

MergePorts: PROC [ct: CellType, portIndices: LIST OF NAT, oldPortData: PortData, oldPortIndex: NAT, noteIn: RefTab.Ref] RETURNS [newPortData: PortData, newPortIndex: NAT] = {
Length: PROC [ln: LIST OF NAT] RETURNS [len: NAT _ 0] =
{FOR ln _ ln, ln.rest WHILE ln # NIL DO len _ len+1 ENDLOOP};
designed, unked, progged, recent, old: LIST OF NAT _ NIL;
oldest: INTEGER _ 0;
surviver: NAT _ NullPortIndex;
siNet: Vertex;
numIndices: NAT _ Length[portIndices];
updatePortData: BOOL _ oldPortData # NIL;
newPI: NAT _ 0;
oldPorts: PortS _ ct.ports;
newPorts: PortS _ NEW [PortSeq[oldPorts.length - (numIndices-1)]];
IF numIndices < 2 THEN ERROR;
IF numIndices >= 2 AND oldPortData # NIL THEN ERROR--code below might exhibit bugs--;
EnsureAllIn[ct.design];
IF oldPortData = NIL THEN oldPortData _ NEW [PortDataRep[ct.ports.length]];
FOR pi: NAT IN [0 .. ct.ports.length) DO oldPortData[pi].seen _ FALSE ENDLOOP;
FOR pil: LIST OF NAT _ portIndices, pil.rest WHILE pil # NIL DO
SELECT TRUE FROM
ct.ports[pil.first].names.designed # NIL => designed _ CONS[pil.first, designed];
ct.ports[pil.first].names.unknown # NIL => unked _ CONS[pil.first, unked];
ct.ports[pil.first].names.progged # NIL => progged _ CONS[pil.first, progged];
ENDCASE => ERROR Broken;
IF oldPortData[pil.first].seen THEN ERROR Broken;
oldPortData[pil.first].seen _ TRUE;
ENDLOOP;
SELECT Length[designed] FROM
>0 => surviver _ designed.first;
=0 => SELECT Length[unked] FROM
>0 => surviver _ unked.first;
=0 => SELECT Length[progged] FROM
>0 => surviver _ progged.first;
ENDCASE;
ENDCASE;
ENDCASE;
IF surviver = NullPortIndex THEN ERROR Broken;
FOR pi: NAT IN [0 .. ct.ports.length) DO oldPortData[pi].seen _ FALSE ENDLOOP;
FOR pil: LIST OF NAT _ portIndices, pil.rest WHILE pil # NIL DO
IF pil.first # surviver THEN {
oldPortData[pil.first].seen _ TRUE;
ct.ports[surviver].names _ MergeNames[ct.ports[surviver].names, ct.ports[pil.first].names];
ct.ports[surviver].netNames _ MergeRopeLists[ct.ports[surviver].netNames, ct.ports[pil.first].netNames];
ct.ports[surviver].equivClass _ MergeEquivClasses[ct.ports[surviver].equivClass, ct.ports[pil.first].equivClass];
};
ENDLOOP;
FOR oldPI: NAT IN [0 .. oldPorts.length) DO
IF oldPI = surviver OR NOT oldPortData[oldPI].seen THEN {
oldPortData[oldPI].newPortIndex _ newPI;
newPorts[newPI] _ oldPorts[oldPI];
newPI _ newPI + 1}
ELSE oldPortData[oldPI].newPortIndex _ NullPortIndex;
ENDLOOP;
IF newPI # newPorts.length THEN ERROR Broken;
ct.ports _ newPorts;
IF ExpansionKnown[ct] THEN {
pi: PortIndex _ 0;
nextEdge: Edge;
FOR e: Edge _ ct.mirror.firstEdge, e.sides[cell].next WHILE e # NIL DO
IF e.sides[cell].v # ct.mirror THEN ERROR Broken;
IF e.portIndex # pi THEN ERROR Broken;
IF e.portIndex = surviver THEN {siNet _ e.sides[net].v; EXIT};
pi _ pi + 1;
REPEAT FINISHED => ERROR Broken;
ENDLOOP;
pi _ 0;
FOR e: Edge _ ct.mirror.firstEdge, nextEdge WHILE e # NIL DO
iNet: Vertex _ e.sides[net].v;
IF e.sides[cell].v # ct.mirror THEN ERROR Broken;
IF e.portIndex # pi THEN ERROR Broken;
nextEdge _ e.sides[cell].next;
IF oldPortData[e.portIndex].seen AND iNet # siNet
THEN {RemoveEdge[e]; [] _ MergeNets[siNet, iNet]}
ELSE e.portIndex _ oldPortData[e.portIndex].newPortIndex;
pi _ pi + 1;
ENDLOOP;
IF pi # oldPortData.length THEN ERROR Broken;
};
FOR v: Vertex _ ct.firstInstance, v.nextInstance WHILE v # NIL DO
pi: NAT _ 0;
soNet: Vertex;
nextEdge: Edge;
FOR e: Edge _ v.firstEdge, e.sides[cell].next WHILE e # NIL DO
IF e.sides[cell].v # v THEN ERROR Broken;
IF e.portIndex # pi THEN ERROR Broken;
IF e.portIndex = surviver THEN {soNet _ e.sides[net].v; EXIT};
pi _ pi + 1;
REPEAT FINISHED => ERROR Broken;
ENDLOOP;
pi _ 0;
FOR e: Edge _ v.firstEdge, nextEdge WHILE e # NIL DO
oNet: Vertex _ e.sides[net].v;
IF e.sides[cell].v # v THEN ERROR Broken;
IF e.portIndex # pi THEN ERROR Broken;
nextEdge _ e.sides[cell].next;
IF oldPortData[e.portIndex].seen AND oNet # soNet
THEN {RemoveEdge[e]; [] _ MergeNets[soNet, oNet]}
ELSE e.portIndex _ oldPortData[e.portIndex].newPortIndex;
pi _ pi + 1;
ENDLOOP;
[] _ noteIn.Store[v.parent, $T];
ENDLOOP;
IF updatePortData THEN {
newPortData _ NEW [PortDataRep[newPorts.length]];
newPI _ 0;
FOR oldPI: NAT IN [0 .. oldPorts.length) DO
oldAssoc: LIST OF NAT;
IF NOT oldPortData[oldPI].seen THEN {
newPortData[newPI] _ oldPortData[oldPI];
oldAssoc _ oldPortData[oldPI].assoc;
newPortData[newPI].assoc _ NIL;
FOR oldAssoc _ oldAssoc, oldAssoc.rest WHILE oldAssoc # NIL DO
SELECT TRUE FROM
oldAssoc.first = oldPI => ERROR Broken;
oldPortData[oldAssoc.first].newPortIndex = NullPortIndex => NULL;
oldPortData[oldAssoc.first].newPortIndex # NullPortIndex => newPortData[newPI].assoc _ CONS[oldPortData[oldAssoc.first].newPortIndex, newPortData[newPI].assoc];
ENDCASE => ERROR Broken;
ENDLOOP;
};
ENDLOOP;
FOR oldPortIndex _ oldPortIndex, oldPortIndex + 1 WHILE oldPortIndex < oldPorts.length AND oldPortData[oldPortIndex].newPortIndex = NullPortIndex DO NULL ENDLOOP;
newPortIndex _ IF oldPortIndex < oldPorts.length THEN oldPortData[oldPortIndex].newPortIndex ELSE newPorts.length;
};
};

DeletePort: PROC [ct: CellType, portIndex: NAT, oldPortData: PortData, noteIn: RefTab.Ref] RETURNS [newPortData: PortData] = {
oldPorts: PortS _ ct.ports;
newPorts: PortS _ NEW [PortSeq[oldPorts.length-1]];
EnsureAllIn[ct.design];
IF ExpansionKnown[ct] THEN {
pi: NAT _ 0;
nextEdge: Edge;
FOR e: Edge _ ct.mirror.firstEdge, nextEdge WHILE e # NIL DO
IF e.sides[cell].v # ct.mirror THEN ERROR Broken;
IF e.portIndex # pi THEN ERROR Broken;
nextEdge _ e.sides[cell].next;
IF e.portIndex = portIndex THEN RemoveEdge[e] ELSE
IF e.portIndex > portIndex THEN e.portIndex _ e.portIndex - 1;
pi _ pi + 1;
ENDLOOP;
IF pi # oldPorts.length THEN ERROR Broken;
};
FOR pi: NAT IN [0 .. newPorts.length) DO
newPorts[pi] _ oldPorts[IF pi < portIndex THEN pi ELSE (pi + 1)];
ENDLOOP;
ct.ports _ newPorts;
IF oldPortData # NIL THEN {
newPortData _ NEW [PortDataRep[oldPortData.length-1]];
FOR pi: NAT IN [0 .. newPortData.length) DO
oldAssoc: LIST OF NAT;
newPortData[pi] _ oldPortData[IF pi < portIndex THEN pi ELSE (pi + 1)];
oldAssoc _ newPortData[pi].assoc;
newPortData[pi].assoc _ NIL;
FOR oldAssoc _ oldAssoc, oldAssoc.rest WHILE oldAssoc # NIL DO
SELECT oldAssoc.first FROM
< portIndex => newPortData[pi].assoc _ CONS[oldAssoc.first, newPortData[pi].assoc];
= portIndex => ERROR Broken;
> portIndex => newPortData[pi].assoc _ CONS[oldAssoc.first - 1, newPortData[pi].assoc];
ENDCASE => ERROR;
ENDLOOP;
ENDLOOP;
};
FOR v: Vertex _ ct.firstInstance, v.nextInstance WHILE v # NIL DO
pi: NAT _ 0;
nextEdge: Edge;
FOR e: Edge _ v.firstEdge, nextEdge WHILE e # NIL DO
IF e.sides[cell].v # v THEN ERROR Broken;
IF e.portIndex # pi THEN ERROR Broken;
nextEdge _ e.sides[cell].next;
IF e.portIndex < portIndex THEN NULL ELSE
IF e.portIndex = portIndex THEN RemoveEdge[e] ELSE
IF e.portIndex > portIndex THEN e.portIndex _ e.portIndex - 1;
pi _ pi + 1;
ENDLOOP;
[] _ noteIn.Store[v.parent, $T];
ENDLOOP;
};

FixAffectedType: PROC [key, val: REF ANY] RETURNS [quit: BOOL] = {
parent: CellType _ NARROW[key];
CheckType[parent, establish, ignore];
quit _ FALSE};

CheckPerType: PUBLIC PROC [key, val: REF ANY] RETURNS [quit: BOOL] = {
parent: CellType _ NARROW[key];
args: LORA _ NARROW[val];
CheckType[ct: parent, norm: ToAO[args.first], comparable: ToAO[args.rest.first], ignoreInstances: IF args.rest.rest # NIL THEN ToBOOL[args.rest.rest.first] ELSE FALSE];
quit _ FALSE};

ToAO: PROC [ra: REF ANY] RETURNS [ao: AssertionOp] = {
ao _ SELECT ra FROM
$ignore => ignore,
$report => report,
$check => check,
$establish => establish,
ENDCASE => ERROR};

ToBOOL: PROC [ra: REF ANY] RETURNS [b: BOOL] = {
b _ SELECT ra FROM
$FALSE => FALSE,
$TRUE => TRUE,
ENDCASE => ERROR};

MergeNames: PROC [n1, n2: Names] RETURNS [m: Names] = {
st: SymbolTable _ RedBlackTree.Create[GetAliasKey, CompareAliases];
Add: PROC [rl: RopeList, ns: ATOM] = {
FOR rl _ rl, rl.rest WHILE rl # NIL DO
a: Alias _ NARROW[st.Lookup[rl.first]];
IF a = NIL THEN st.Insert[NEW [AliasRep _ [name: rl.first, thing: ns]], rl.first] ELSE IF a.thing # ns THEN ERROR Broken;
ENDLOOP;
};
Dump: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
a: Alias _ NARROW[ra];
stop _ FALSE;
SELECT a.thing FROM
$D => m.designed _ CONS[a.name, m.designed];
$U => m.unknown _ CONS[a.name, m.unknown];
$P => m.progged _ CONS[a.name, m.progged];
ENDCASE => ERROR BadData;
};
m _ [];
Add[n1.designed, $D];
Add[n1.unknown, $U];
Add[n1.progged, $P];
Add[n2.designed, $D];
Add[n2.unknown, $U];
Add[n2.progged, $P];
st.EnumerateIncreasing[Dump];
};

MergeRopeLists: PROC [a, b: RopeList] RETURNS [c: RopeList] = {
c _ b;
FOR a _ a, a.rest WHILE a # NIL DO
IF NOT RopeListIncludes[c, a.first] THEN c _ CONS[a.first, c];
ENDLOOP;
};

MergeEquivClasses: PROC [a, b: EquivClass] RETURNS [c: EquivClass] = {
IF a = implicitClass THEN RETURN [b];
IF b = implicitClass THEN RETURN [a];
IF NOT a.Equal[b] THEN ERROR;
c _ a;
};

END.
พLichenNormal.Mesa
Last Edited by: Spreitzer, July 15, 1985 7:38:18 pm PDT
When in normal form:
ANNetUsed: Each net is attached to at least one thing.
A n E ci, p , ci.p f n
(note that we allow a ci to be the outside world)
ANPortUsedI: Each net attached to a port is also attached to something else.
A n, p [n f p g E ci, p' = p , n f ci.p']
ANPortsMergedI: Each net connected to at most one port.
A n n E p = p' , n f p & n f p'
Implies nets merged.
The following duals are NOT required to be true:
ANPortUsedO: Each port is used for something interesting at least once.
A p E p', ci = world, ci', n , ci.p f n & ci'.p' f n & (ci = ci' V p = p')
ANPortsMergedO: Each port distinction is used at least once.
A p = p' of ct E ci = world, n, n' , ci.p f n & ci.p' f n' & n n S n'
For a design to be comparable, we must also have:
ACCellTypeEquivd: The structural equivalence class of a cell type is clear.
ct.equivClass # implicitClass COR |ct.names.designed| = 1 OR |ct.names.designed| = 0 CAND (|ct.names.unknown| = 1 OR |ct.names.unknown| = 0 CAND |ct.names.progged| = 1)
ACPortEquivd: The structural equivalence class of a port is clear.
p.equivClass # implicitClass COR |p.names.designed| = 1 OR |p.names.designed| = 0 CAND (|p.names.unknown| = 1 OR |p.names.unknown| = 0 CAND |p.names.progged| = 1)
Note that we depend on ANPortsMergedO being true for some other cellTypes, and ANPortsMergedI being true for this and some other cellTypes, in making this test.
สฆ–

"cedar" style˜Icode™J™7K˜Kšฯk	œœœa˜†
K˜šะbxœœ
˜Kšœ
œP˜ZKšœ˜K˜Kšœ
œ ˜*K˜
display™™6Lšฯm
œŸ
œŸ
œŸ
œ™L™1—™LLšŸ
œ	Ÿ
œŸ
œ
Ÿ
œŸ
œŸ
œŸ
œ™)—™7LšŸ
œŸ
œ
Ÿ
œŸ
œŸ
œŸ
œŸ
œ™L™——™0™GLšŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œ™J—™<LšŸ
œŸ
œ
Ÿ
œŸ
œŸ
œŸ
œŸ
œŸ
œŸ
œ
Ÿ
œŸ
œ™E——™1™KLš
œจ
™จ
—™BLš
œข
™ข
——K˜Kšœœœ
˜Kšœ	œœ
˜Kš	œœ
œœœ
˜+Kš	œœ
œœœ
˜/K˜Kšœœœ
˜Kšœœœ
˜K˜šฯnœœP˜aš œœœ
œœœ˜8Kšœœ˜Kšœœ
˜
Kš
œ ˜ K˜—šœ˜Kšœ
œ
˜Kš
œ0˜0Kšœœ
˜—Kš
œb˜bK˜—K˜Kšœ
œœ
˜!Kšœ
œœœ	œ
œ˜Ešœœœ˜Kšœœœ
˜"Kš	œœ
œ
œœ
˜Kšœœ˜#—K˜š
 	œœ
œ\œœ˜ƒ
Kšœœ
˜Kšœœ˜K˜šœœ˜+K˜Kšœœ
˜Kšœœ
˜—Kšœ	œœ
˜š œœœ
œœœ˜4Kšœœ˜Kšœœ
˜Kšœœ
˜
Kšœœ
œ
˜+Kšœ
œ
œ	ฯc˜'Kšœœ
œ˜#Kšœ'œ˜-šœ	˜Kšœ!œ-œœ˜eKš
œ7˜7Kšœœ
˜—K˜—Kš
œE˜Ešœ˜Kšœœ
˜Kšœ
œœ
œ
˜+Kšœœ
˜—Kš
œœ
œœ
œ˜<Kšœ:œ˜@K˜K˜Kš
œœ
œœ
œ˜<šœ˜Kšœ
œ
˜Kš
œr˜rKšœœ
˜—šœœ˜.š 
œœ˜)šœ$œœ
˜>KšœNœ
˜]Kšœ˜	——šœœ
œ˜;š
œ
˜
Kšœœ0˜GKšœ
œ
œ
œ	˜#šœ6œœ
˜KKšœ&œ
œ	˜;Kšœ
˜—K˜—Kšœ	œ
˜Kšœœ
˜—šœ˜Kšœ
œ
˜Kš
œ‚
˜‚
Kšœœ
˜—K˜(K˜'K˜'Kšœ
˜—K˜šœ
œœ˜šœ˜Kšœ
œ
˜˜Kšœœ
˜Kšœœ ˜.Kš
œœ
œœœ
˜AK˜—Kšœœ
˜—šœ.œœ
˜AKšœœ
œ˜3Kšœ
œ
œ˜!Kšœ
œ
œ	ก˜'Kšœ-œ˜3Kš
œ4˜4K˜Kšœ
˜—Kšœ œ
œ˜4šœ˜Kšœ
œ
˜šœœœ˜$šœœ
œ˜(Kšœ
œœ,œ˜jšœœ
œ/œ˜pK™ 
—Kšœ
˜—K˜—šœ
œœ˜ Kšœœ˜šœ˜Kšœœœœœ
œ
˜Ešœ
œœ˜Kšœœœ˜HKš
œ6˜6Kšœœ
˜Kš
œ"˜"—šœ
œœ
œ˜'šœœ˜Kšœ!œ˜Bš
œœ
œ
œ œœ
˜FKšœœ-˜:Kšœ
˜—K˜—Kšœ œ6˜ZKšœœ
˜Kš
œ"˜"—Kšœ
˜Kšœ
˜—K˜—Kšœœ
˜—K˜—šœœ
œ˜;š
œ
˜
Kšœ
œ
œ
œ˜%Kšœœ
œ˜)Kšœœ
œ˜+Kšœ7œ˜>Kš
œP˜PKšœœ
œœœ
œ˜\K˜K˜—Kš
œ˜Kšœœ
˜—š	œ
œœ
œ˜,Kšœ
œ
˜Kšœœœ
œ˜9˜šœ˜&˜Kš
œ˜Kš
œ%˜%K˜—Kšœœœ"˜G—K˜)K˜—Kšœœ
˜—K˜—K˜š 
œœ˜#K˜Kšœ0œ
œ˜DKšœ%œ
œ˜9šœœœ
œœ
œ
œ
œ
œœ
œ
œ
˜@K˜#Kšœœ
œ
œ
˜šœœ˜)K˜K˜Kšœœœ
œ
˜5Kšœœœ
œ
˜4Kšœ
˜—Kšœ
œ
œ
˜—šœœ%˜<šœœœ
œœ˜)K˜K˜šœGœœ
˜\Kšœœœœ;œœ
˜cKšœœ
œ˜*šœ˜
Kšœ+˜/šœ˜Kšœ!œ
œ˜5Kš
œ$˜$K˜——Kšœ3œ
œ˜GKšœ
˜—Kšœ(œ
œ˜<Kšœ
œ
˜—Kšœ
˜—K˜—K˜š œœMœ˜kš
˜Kšœ˜šœ˜Kš	œœ
œœ
˜;Kš	œœ
œœ
˜9Kš	œœ
œœ
˜9Kšœ
˜—Kšœ&œœ
˜G—K˜—K˜š
 œœ(œ
œœ˜\š œœ˜šœœœ
˜&Jšœ8œ
œ˜LKšœ
˜—K˜	—K˜K˜K˜—K˜š 
œœ7˜JKšœœ˜šœ˜š
œ˜šœ+œœ
˜>K˜Kšœœ
œ˜)Kšœœ
œ˜-K˜Kšœ
˜—Kšœ!œ
œ˜5Kš
œ˜—˜šœ+œœ
˜>K˜Kšœœ
œ˜)Kšœœ
œ˜-Kšœœ
œœœ
œ
˜Kšœ,œœ
˜?K˜Kšœœ
œ˜*Kšœœœ
˜>Kšœœœœ
˜WKšœ
˜—Kšœ
œœ
œ˜2šœœ˜"Kšœœ
˜ šœœ
œ˜(Kšœœœœ ˜mKšœ
˜—K˜
—šœ˜Kš	œœ
œ
œœ
˜š
œœ
œ
œ&œœ
˜Jšœ
œœ˜%Kšœ
œ
œ%œ˜YK˜
—Kšœ˜Kšœ
˜—K˜—K˜Kšœ
˜—Kšœ!œ
œ˜5K˜—Kšœœ
˜—K˜—K˜š œœ\œœ˜…
Kšœœ
˜Kšœœ˜Kš	œ
œ
œ
œœ
˜Kšœ
œ
˜šœ*œœ
˜=K˜Kšœœ
œ˜(Kšœœ
œ˜2šœ
œ˜Kš
œ˜Kšœœ˜-Kš
œ
˜
—Kšœ˜!K˜
Kšœ
˜—Kšœœ
œ˜+šœ˜Kšœ
œ
˜˜Kšœœ*œ˜jKšœœœ,œ˜rKšœœ/œ˜bK˜—˜šœœ˜$Kšœœœ˜IKšœ
œ
˜K˜ Kš
œ˜Kšœœ
˜ K˜)—šœœœ˜*Kšœœœ4˜bKšœ
œ
˜K˜ Kšœ-œ
˜:Kšœœ
˜ K˜)—šœœ˜šœœ˜Kšœ!œ%˜Hš
œœ
œ
œœœ
˜?Kšœœ3˜@Kšœ
˜—K˜—Kšœ
œ
˜K˜ Kšœ'œ˜CKšœœ
˜ Kš
œ)˜)—K˜—Kšœœ
˜—K˜—K˜š œœ˜$Kšœœ˜Kšœœ
˜K˜šœ+œœ
˜>Kšœœ
œ˜)Kšœœ
œ˜3Kšœœ
œ˜-Kš
œ˜K˜
Kšœ
˜—Kšœœ
œ˜+Kšœ!œ
œ˜5K˜—K˜š 	œœ
œœ˜NKš
˜š	 œœœ	ก(œ˜RKšœœ!˜2Kšœœ
œ
˜K˜K˜—š œœœ
œœœ˜5Kšœœ˜#Kšœœ
˜
Kšœœ
œ
˜"Kšœ,œ
œ
˜9K˜Kšœœ
œU˜xKš
œ%˜%K˜—Kšœœ
œ
˜(Kšœœœ
œ
˜3Kšœ
œ
œœ˜'Kš
œ˜K˜Kš
œ#˜#K˜0šœ-œœ
˜@Kšœœ
œ
˜$K˜Kšœ
˜—šœœ
œ˜Kšœœ
œ0œ!˜pK˜Kš
œ/˜/Kšœœ
˜Kšœœ
˜K˜—Kšœœ
œZ˜}Kšœ
˜—K˜š 
œœœ
œ
œ'œœ'œ˜ฎ
š œœœ
œ
œœœ˜7Kšœ
œœœ
œ
œ˜=—Kš	œ'œ
œ
œœ
˜9Kšœœ˜Kšœ
œ˜K˜Kšœœ˜&Kšœœœ
˜)Kšœœ˜K˜Kšœœ-˜BKšœœ
œ
˜Kšœœœ
œ
ก!œ
˜UK˜Kšœœ
œœ ˜KKšœœ
œœœ
œ
˜Nš
œœ
œ
œœœ
˜?šœ
œ
˜Kšœ%œœ˜QKšœ$œœ˜JKšœ$œœ˜NKšœœ˜—Kšœœ
œ˜1Kšœœ
˜#Kšœ
˜—šœ˜K˜ šœœ˜K˜šœœ˜!K˜Kšœ
˜—Kšœ
˜—Kšœ
˜—Kšœœ
œ˜.Kšœœ
œœœ
œ
˜Nš
œœ
œ
œœœ
˜?šœœ˜Kšœœ
˜#Kš
œ[˜[Kš
œh˜hKš
œq˜qK˜—Kšœ
˜—šœœ
œ˜+šœœ
œœ˜9K˜(K˜"K˜—Kšœ1˜5Kšœ
˜—Kšœœ
œ˜-K˜šœœ˜K˜K˜šœ3œœ
˜FKšœœ
œ˜1Kšœœ
œ˜&Kšœœœ˜>K˜Kšœ
œœ˜ Kšœ
˜—K˜šœ)œœ
˜<Kš
œ˜Kšœœ
œ˜1Kšœœ
œ˜&Kš
œ˜šœœ
˜1Kšœ-˜1Kšœ5˜9—K˜Kšœ
˜—Kšœœ
œ˜-K˜—šœ.œœ
˜AKšœœ˜K˜K˜šœ+œœ
˜>Kšœœ
œ˜)Kšœœ
œ˜&Kšœœœ˜>K˜Kšœ
œœ˜ Kšœ
˜—Kš
œ˜šœ!œœ
˜4Kš
œ˜Kšœœ
œ˜)Kšœœ
œ˜&Kš
œ˜šœœ
˜1Kšœ-˜1Kšœ5˜9—K˜Kšœ
˜—Kš
œ ˜ Kšœ
˜—šœœ˜Kšœœ ˜1K˜
šœœ
œ˜+Kšœ
œ
œ
œ
˜šœ
œœ˜%Kš
œ(˜(Kš
œ$˜$Kšœœ
˜šœ$œœ
˜>šœ
œ
˜Kšœœ˜'Kšœ<œ
˜AKšœWœE˜ 
Kšœœ˜—Kšœ
˜—K˜—Kšœ
˜—Kšœ/œ œ8œ
œ
œ
˜ข
Kšœœ œ(œ˜rK˜—K˜—K˜š 
œœœ-œ˜~K˜Kšœœ˜3K˜šœœ˜Kšœœ˜K˜šœ)œœ
˜<Kšœœ
œ˜1Kšœœ
œ˜&Kš
œ˜Kšœœ˜2Kšœœ˜>K˜Kšœ
˜—Kšœœ
œ˜*K˜—šœœ
œ˜(Kšœœœœ˜AKšœ
˜—K˜šœœ
œ˜Kšœœ%˜6šœœ
œ˜+Kšœ
œ
œ
œ
˜Kšœœœœ˜GKš
œ!˜!Kšœœ
˜šœ$œœ
˜>šœ˜Kšœ'œ(˜SKšœœ˜Kšœ'œ,˜WKšœœ
˜—Kšœ
˜—Kšœ
˜—K˜—šœ.œœ
˜AKšœœ˜K˜šœ!œœ
˜4Kšœœ
œ˜)Kšœœ
œ˜&Kš
œ˜Kšœœ
œ
˜)Kšœœ˜2Kšœœ˜>K˜Kšœ
˜—Kš
œ ˜ Kšœ
˜—Kš
œ˜—K˜š œœœ
œœœ˜BKšœœ˜Kš
œ%˜%Kšœœ˜—K˜š œœ
œœ
œœœ˜FKšœœ˜Kšœœœ˜Kšœbœœ
œœ
œ˜จ
Kšœœ˜—K˜š
 œœœ
œœ˜6šœœ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kšœœ˜——K˜š œœœ
œœœ˜0šœœ˜Kšœ
œ
˜Kšœ	œ
˜Kšœœ˜——K˜š 
œœœ˜7Kš
œC˜Cš œœœ˜&šœœœ
˜&Kšœœ˜'Kšœœ
œœ5œ
œœ
œ˜yKšœ
˜—K˜—š œœœ
œœœ˜1Kšœœ˜Kšœœ
˜
šœ	˜Kšœœ˜,Kšœœ˜*Kšœœ˜*Kšœœ	˜—K˜—K˜K˜K˜K˜K˜K˜K˜K˜K˜—K˜š œœœ˜?K˜šœœœ
˜"Kšœ
œœœ
˜>Kšœ
˜—K˜—K˜š œœœ˜FKšœœ
œ˜%Kšœœ
œ˜%Kšœ
œœ
œ
˜K˜K˜—K˜Kšœ
˜——…—Xฺ}>