LichenOrderingImpl.Mesa
Last tweaked by Mike Spreitzer on February 2, 1988 4:32:15 pm PST
DIRECTORY AbSets, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, LichenTransforms, Process, Rope, SetBasics, StructuredStreams, UnparserBuffer, ViewerIO;
LichenOrderingImpl:
CEDAR
PROGRAM
IMPORTS AbSets, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, Process, SetBasics
EXPORTS LichenTransforms
=
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]];
break1: SteppyName ← noName;
break2: SteppyName ← noName;
Break: SIGNAL ~ CODE;
ReOrderDesign:
PUBLIC
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;
IF break1#noName AND port.PortNames.HasMember[SnV[break1]] THEN Break;
{desire: Permutation ~ DesiredPerm[port, LichenNavigation.portToChildren, LichenNavigation.bestPortShortName];
refDesire: REF ANY ~ desire.Refify;
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[DelayInstance, TRUE];
ct.EnumerateArrays[DelayArray];
IF NOT delayedPorts.AddA[port] THEN ERROR;
portDesires.AddNewAA[port, refDesire];
RETURN}};
WorkOnWire:
PROC [wire: Wire]
RETURNS [doKids, moreSibs:
BOOL ←
TRUE] ~ {
IF wire.FirstChildWire[]=NIL THEN RETURN;
IF break1#noName AND wire.VertexNames.HasMember[SnV[break1]] THEN Break;
{desire: Permutation ~ DesiredPerm[wire, LichenNavigation.wireToChildren, LichenNavigation.bestVertexShortName];
refDesire: REF ANY ~ desire.Refify;
[] ← delayedVerts.AddA[wire];
[] ← desiredPerm.AddAA[wire, refDesire];
RETURN}};
Process.CheckForAbort[];
[] ← 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};
Process.CheckForAbort[];
IF break1#noName AND port.PortNames.HasMember[SnV[break1]] THEN Break;
ct.EnumerateInstances[CheckInstance, TRUE];
ct.EnumerateArrays[CheckArray];
IF allSame
THEN PermutePort[port, desire, FALSE]
ELSE Log["Port %g not permuted\n", LIST[port]];
RETURN};
DoDelayedVertex:
PROC [val:
REF
ANY] ~ {
v: Vertex ~ NARROW[val];
ct: CellType ~ v.containingCT;
perms: Set ~ desiredPerm.MappingA[v];
size: INT ~ perms.Size[Ints.two].EN;
Process.CheckForAbort[];
IF break1#noName AND v.VertexNames.HasMember[SnV[break1]] THEN Break;
IF size=0 THEN ERROR;
IF size>1
THEN {
Log["%g perms desired for vertex %g\n", LIST[NEW [INT ← size], v]];
RETURN};
{desire: Permutation ~ BiRels.DeRef[perms.TheElt.VA];
PermuteVertex[v, desire];
RETURN}};
d.cellTypes.EnumA[StartCellType];
delayedPorts.EnumA[DoDelayedPort];
delayedVerts.EnumA[DoDelayedVertex];
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].CreateVectorCopy;
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] .CreateVectorCopy;
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];
};
IF break2#noName AND port.PortNames.HasMember[SnV[break2]] THEN Break;
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] .CreateVectorCopy;
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};
IF break2#noName AND wire.VertexNames.HasMember[SnV[break2]] THEN Break;
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.CreateVector[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.