LichenData4Impl.Mesa
Last tweaked by Mike Spreitzer on January 7, 1988 5:20:47 pm PST
DIRECTORY AbSets, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, Rope, SetBasics, StructuredStreams, UnparserBuffer, ViewerIO;
LichenData4Impl:
CEDAR
PROGRAM
IMPORTS AbSets, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, SetBasics
=
BEGIN OPEN LichenArrayStuff, LichenDataOps, LichenDataStructure, Sets:AbSets, Ints:IntStuff, SS:StructuredStreams, UB:UnparserBuffer;
Set: TYPE ~ LichenDataStructure.Set;
Function: TYPE ~ LichenDataStructure.Function;
OneToOne: TYPE ~ LichenDataStructure.OneToOne;
Seq: TYPE ~ LichenDataStructure.Seq;
Thing: TYPE ~ REF ANY --actually UNION [Port, Wire]--;
Wirism: TYPE ~ REF ANY --actually UNION [Vertex, DumbWire]--;
refPerms: Sets.Space ~ BiRels.CreateBiRelSpace[ALL[SetBasics.ints]];
ReOrderDesign:
PROC [d: Design] ~ {
desiredPerm: BiRel--Wirism REF Permutation-- ~ BiRels.CreateHashReln[[SetBasics.refs, refPerms]];
portDesires: Function--Port b REF Permutation-- ~ BiRels.CreateHashFn[invable: FALSE];
delayedVerts: Set--of Vertex-- ~ Sets.CreateHashSet[];
delayedPorts: Set--of Port-- ~ Sets.CreateHashSet[];
arrayWireArray: Function--DumbWire b Array-- ~ BiRels.CreateHashFn[invable: FALSE];
StartCellType:
PROC [val:
REF
ANY] ~ {
ct: CellType ~ NARROW[val];
WorkOnPort:
PROC [port: Port]
RETURNS [doKids, moreSibs:
BOOL ←
TRUE] ~ {
IF port.FirstChildPort[]=NIL THEN RETURN;
{desire: Permutation ~ DesiredPerm[port, LichenNavigation.portToChildren, LichenNavigation.bestPortShortName];
IF desire.IsIDSubset[] THEN RETURN;
{refDesire: REF ANY ~ desire.Refify;
delay: BOOL ← FALSE;
CheckInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindCellConnection[ci, port];
allMe: BOOL ~ AllForPort[v, port];
IF NOT allMe THEN delay ← TRUE;
RETURN};
CheckArray:
PROC [act: CellType] ~ {
a: Array ~ act.asArray;
CheckOtherPort: PROC [other: Port] ~ {IF other#port THEN delay ← TRUE};
EnumerateConnectedEltPorts[a, port, CheckOtherPort, TRUE];
RETURN};
DelayInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindCellConnection[ci, port];
[] ← delayedVerts.AddA[v];
[] ← desiredPerm.AddAA[v, refDesire];
RETURN};
DelayArray:
PROC [act: CellType] ~ {
a: Array ~ act.asArray;
DelayArrayWire:
PROC [dw: DumbWire] ~ {
[] ← arrayWireArray.AddAA[dw, a];
[] ← desiredPerm.AddAA[dw, refDesire];
RETURN};
EnumerateDumbWiresForPort[a, port, DelayArrayWire];
RETURN};
ct.EnumerateInstances[CheckInstance, TRUE];
ct.EnumerateArrays[CheckArray];
IF delay
THEN {
ct.EnumerateInstances[DelayInstance, TRUE];
ct.EnumerateArrays[DelayArray];
IF NOT delayedPorts.AddA[port] THEN ERROR;
portDesires.AddNewAA[port, refDesire]}
ELSE PermutePort[port, desire, TRUE];
RETURN}}};
WorkOnWire:
PROC [wire: Wire]
RETURNS [doKids, moreSibs:
BOOL ←
TRUE] ~ {
IF wire.FirstChildWire[]=NIL THEN RETURN;
{desire: Permutation ~ DesiredPerm[wire, LichenNavigation.wireToChildren, LichenNavigation.bestVertexShortName];
IF desire.IsIDSubset[] THEN RETURN;
{refDesire: REF ANY ~ desire.Refify;
delay: BOOL ~ NOT AllForPort[wire, find];
IF delay
THEN {
[] ← delayedVerts.AddA[wire];
[] ← desiredPerm.AddAA[wire, refDesire];
}
ELSE PermuteWire[wire, desire];
RETURN}}};
[] ← EnumeratePort[ct.port, WorkOnPort];
IF ct.asUnorganized#NIL THEN [] ← ct.asUnorganized.internalWire.EnumerateWire[WorkOnWire];
RETURN};
DoDelayedPort:
PROC [val:
REF
ANY] ~ {
port: Port ~ NARROW[val];
ct: CellType ~ PortCCT[port];
allSame: BOOL ← TRUE;
desire: Permutation ~ BiRels.DeRef[portDesires.ApplyA[port].MA];
CheckInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindCellConnection[ci, port];
perms: Set ~ desiredPerm.MappingA[v];
size: INT ~ perms.Size[Ints.two].EN;
IF size=0 THEN ERROR;
IF size>1 THEN allSame ← FALSE;
RETURN};
CheckArray:
PROC [act: CellType] ~ {
a: Array ~ act.asArray;
CheckArrayWire:
PROC [dw: DumbWire] ~ {
perms: Set ~ desiredPerm.MappingA[dw];
size: INT ~ perms.Size[Ints.two].EN;
IF size=0 THEN ERROR;
IF size>1 THEN allSame ← FALSE;
RETURN};
EnumerateDumbWiresForPort[a, port, CheckArrayWire];
RETURN};
ct.EnumerateInstances[CheckInstance, TRUE];
ct.EnumerateArrays[CheckArray];
IF allSame
THEN PermutePort[port, desire, FALSE]
ELSE Log["Port %g not permuted", LIST[port]];
RETURN};
DoDelayedWire:
PROC [val:
REF
ANY] ~ {
wire: Wire ~ NARROW[val];
ct: CellType ~ wire.containingCT;
perms: Set ~ desiredPerm.MappingA[wire];
size: INT ~ perms.Size[Ints.two].EN;
IF size=0 THEN ERROR;
IF size>1
THEN {
Log["%g perms desired for wire %g", LIST[NEW [INT ← size], wire]];
RETURN};
{desire: Permutation ~ BiRels.DeRef[perms.TheElt.VA];
PermuteWire[wire, desire];
RETURN}};
d.cellTypes.EnumA[StartCellType];
delayedPorts.EnumA[DoDelayedPort];
delayedVerts.EnumA[DoDelayedWire];
RETURN};
find: Port ~ NEW [PortPrivate];
AllForPort:
PROC [v: Vertex, port: Port]
RETURNS [allSame:
BOOL ←
TRUE] ~ {
CheckEdge:
PROC [p: Port, w: Vertex, e: Edge] ~ {
IF p=NIL OR p=find THEN ERROR;
IF port=find THEN port ← p ELSE IF p#port THEN allSame ← FALSE;
RETURN};
v.EnumerateImmediateEdges[CheckEdge, [cellward: TRUE, wireward: FALSE]];
IF NOT allSame THEN RETURN;
WITH v
SELECT
FROM
ci: CellInstance => IF port#find AND port#ci.type.port THEN RETURN [FALSE];
im: Intermediary => IF port#find AND port#im.port THEN RETURN [FALSE];
w: Wire =>
IF w.containingWire#
NIL
THEN {
goal: Port;
IF port=find THEN goal ← find
ELSE IF port=NIL THEN goal ← NIL
ELSE
WITH port.parent
SELECT
FROM
ct: CellType => ERROR--shouldn't happen--;
parent: Port => {
wi: INT ~ w.containingWire.WireIndex[w];
pi: INT ~ port.PortIndex[];
IF wi=pi THEN goal ← parent ELSE goal ← NIL};
ENDCASE => ERROR;
IF NOT AllForPort[w.containingWire, goal] THEN RETURN [FALSE];
};
ENDCASE => ERROR;
RETURN};
DesiredPerm:
PROC [parent: Thing,
ToChildren: OneToOne
--Thing
é Seq of children--,
ToName: Function
--Thing
b SteppyName--]
RETURNS [perm: Permutation] ~ {
children: Seq--of child Things-- ~ BiRels.DeRef[ToChildren.ApplyA[parent].MA].CreateSimpleCopy;
names: Seq--of SteppyName-- ~ children.Compose[right: ToName, restricts: [TRUE, FALSE]];
perm ← BiRels.GradeUp[names, alphaSteppyNameOrder];
RETURN};
alphaSteppyNameOrder: SetBasics.Order ~ SetBasics.CreateLORASpace[NIL, LIST[nameStepSpace]].SpaceOrder[];
PermutePort:
PROC [port: Port, perm: Permutation, doConnections:
BOOL] ~ {
oldKids: Seq ~ BiRels.DeRef[LichenNavigation.portToChildren.ApplyA[port].MA] .CreateSimpleCopy;
n: INT ~ oldKids.Size.EN;
prev: Port ← NIL;
index: INT ← 0;
FixElt:
PROC [pair: BiRels.Pair] ~ {
newIndex: INT ~ pair[left].VI;
oldIndex: INT ~ pair[right].VI;
kid: Port ~ NARROW[oldKids.ApplyI[oldIndex].MA];
IF index#newIndex THEN ERROR;
kid.prev ← prev;
IF prev#NIL THEN prev.next ← kid ELSE port.firstChild ← kid;
prev ← kid;
index ← index+1;
RETURN};
FixInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindCellConnection[ci, port];
PermuteVertex[v, perm];
};
perm.Enumerate[FixElt];
IF index#n THEN ERROR;
prev.next ← NIL;
port.lastChild ← prev;
IF doConnections THEN port.PortCCT.EnumerateInstances[FixInstance, TRUE];
RETURN};
PermuteWire:
PROC [wire: Wire, perm: Permutation] ~ {
oldKids: Seq ~ BiRels.DeRef[LichenNavigation.wireToChildren.ApplyA[wire].MA] .CreateSimpleCopy;
n: INT ~ oldKids.Size.EN;
prev: Wire ← NIL;
index: INT ← 0;
FixElt:
PROC [pair: BiRels.Pair] ~ {
newIndex: INT ~ pair[left].VI;
oldIndex: INT ~ pair[right].VI;
kid: Wire ~ NARROW[oldKids.ApplyI[oldIndex].MA];
IF index#newIndex THEN ERROR;
kid.prev ← prev;
IF prev#NIL THEN prev.next ← kid ELSE wire.firstChild ← kid;
prev ← kid;
index ← index+1;
RETURN};
perm.Enumerate[FixElt];
IF index#n THEN ERROR;
prev.next ← NIL;
wire.lastChild ← prev;
RETURN};
PermuteVertex:
PROC [v: Vertex, perm: Permutation] ~ {
WITH v
SELECT
FROM
w: Wire => {PermuteWire[w, perm]; RETURN};
im: Intermediary => NULL;
ci: CellInstance => NULL;
ENDCASE => ERROR;
{old: Seq--of old Edge-- ~ BiRels.CreateSimple[oneToOne: TRUE, dense: TRUE];
NoteOldEdge:
PROC [p: Port, w: Vertex, e: Edge] ~ {
IF e.sides[cellward].v#v THEN ERROR;
old.AppendA[e];
RETURN};
v.EnumerateImmediateEdges[NoteOldEdge, [cellward: FALSE, wireward: TRUE], forward];
{n: INT ~ old.Size.EN;
oldFirstWireward: Edge ~ NARROW[old.First[].it[right].VA];
lastCellward: Edge ~ oldFirstWireward.sides[cellward].prev;
prev: Edge ← lastCellward;
prevSide: GraphDirection ← wireward;
index: INT ← 0;
FixElt:
PROC [pair: BiRels.Pair] ~ {
newIndex: INT ~ pair[left].VI;
oldIndex: INT ~ pair[right].VI;
e: Edge ~ NARROW[old.ApplyI[oldIndex].MA];
IF index#newIndex THEN ERROR;
e.sides[cellward].prev ← prev;
IF prev#NIL THEN prev.sides[prevSide].next ← e
ELSE IF v.firstEdge.sides[cellward].v#v THEN ERROR
ELSE v.firstEdge ← e;
prev ← e;
prevSide ← cellward;
index ← index+1;
RETURN};
IF lastCellward#NIL AND lastCellward.sides[wireward].v#v THEN ERROR;
perm.Enumerate[FixElt];
IF index#n OR n=0 THEN ERROR;
prev.sides[cellward].next ← NIL;
v.lastEdge ← prev;
RETURN}}};
END.