LichenData4Impl.Mesa
Last tweaked by Mike Spreitzer on September 18, 1987 1:16:36 pm PDT
DIRECTORY LichenArrayStuff, LichenCollections, LichenDataOps, LichenDataStructure, LichenIntFunctions, LichenIntStuff, LichenNavigation, LichenPairCollections, Rope, StructuredStreams, UnparserBuffer, ViewerIO;
LichenData4Impl:
CEDAR
PROGRAM
IMPORTS LichenArrayStuff, LichenCollections, LichenDataOps, LichenDataStructure, LichenIntFunctions, LichenNavigation, LichenPairCollections
=
BEGIN OPEN LichenArrayStuff, LichenDataOps, LichenDataStructure, Colls:LichenCollections, PairColls:LichenPairCollections, Ints:LichenIntStuff, IntFns:LichenIntFunctions, 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, ArrayWire]--;
ReOrderDesign:
PROC [d: Design] ~ {
desiredPerm: Relation--Wirism REF Permutation-- ~ PairColls.CreateHashReln[[Colls.refs, IntFns.refIntFns]];
portDesires: Function--Port b REF Permutation-- ~ PairColls.CreateHashFn[invable: FALSE];
delayedVerts: Set--of Vertex-- ~ Colls.CreateHashSet[];
delayedPorts: Set--of Port-- ~ Colls.CreateHashSet[];
arrayWireArray: Function--ArrayWire b Array-- ~ PairColls.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.IsIdentitySubset[] THEN RETURN;
{refDesire: REF ANY ~ desire.Refify;
delay: BOOL ← FALSE;
CheckInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindTopEdge[ci, port].v;
allMe: BOOL ~ AllForPort[v, port];
IF NOT allMe THEN delay ← TRUE;
RETURN};
CheckArray:
PROC [act: CellType] ~ {
a: Array ~ act.asArray;
CheckGroup:
PROC [gi2: Nat2, gi:
NATURAL, g: Group] ~ {
CheckArrayWire:
PROC [aw: ArrayWire] ~ {
CheckOtherGroup:
PROC [gi2: Nat2, gi:
NATURAL, g: Group, membership: BoolSeq
--group instance index
b isMember--] ~ {
IF g.ports=NIL OR g.ports.rest#NIL OR g.ports.first#port THEN delay ← TRUE;
RETURN};
EnumerateGroupsOfArrayWire[a, aw, CheckOtherGroup];
RETURN};
EnumerateArrayWiresContainingGroup[a, gi2, gi, g, CheckArrayWire, TRUE];
RETURN};
EnumerateGroupsContainingPort[a, port, CheckGroup];
RETURN};
DelayInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindTopEdge[ci, port].v;
[] ← delayedVerts.AddElt[v];
[] ← desiredPerm.AddPair[[v, refDesire]];
RETURN};
DelayArray:
PROC [act: CellType] ~ {
a: Array ~ act.asArray;
DelayGroup:
PROC [gi2: Nat2, gi:
NATURAL, g: Group] ~ {
DelayArrayWire:
PROC [aw: ArrayWire] ~ {
[] ← arrayWireArray.AddPair[[aw, a]];
[] ← desiredPerm.AddPair[[aw, refDesire]];
RETURN};
EnumerateArrayWiresContainingGroup[a, gi2, gi, g, DelayArrayWire, TRUE];
RETURN};
EnumerateGroupsContainingPort[a, port, DelayGroup];
RETURN};
ct.EnumerateInstances[CheckInstance, TRUE];
ct.EnumerateArrays[CheckArray];
IF delay
THEN {
ct.EnumerateInstances[DelayInstance, TRUE];
ct.EnumerateArrays[DelayArray];
IF NOT delayedPorts.AddElt[port] THEN ERROR;
Store[portDesires, [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.IsIdentitySubset[] THEN RETURN;
{refDesire: REF ANY ~ desire.Refify;
delay: BOOL ~ NOT AllForPort[wire];
IF delay
THEN {
[] ← delayedVerts.AddElt[wire];
[] ← desiredPerm.AddPair[[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 ~ IntFns.DeRef[portDesires.Apply[port].val];
CheckInstance:
PROC [ci: CellInstance] ~ {
v: Vertex ~ FindTopEdge[ci, port].v;
perms: Set ~ desiredPerm.Mapping[v];
size: INT ~ perms.Size[2];
IF size=0 THEN ERROR;
IF size>1 THEN allSame ← FALSE;
RETURN};
CheckArray:
PROC [act: CellType] ~ {
a: Array ~ act.asArray;
CheckGroup:
PROC [gi2: Nat2, gi:
NATURAL, g: Group] ~ {
CheckArrayWire:
PROC [aw: ArrayWire] ~ {
perms: Set ~ desiredPerm.Mapping[aw];
size: INT ~ perms.Size[2];
IF size=0 THEN ERROR;
IF size>1 THEN allSame ← FALSE;
RETURN};
EnumerateArrayWiresContainingGroup[a, gi2, gi, g, CheckArrayWire, TRUE];
RETURN};
EnumerateGroupsContainingPort[a, port, CheckGroup];
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.Mapping[wire];
size: INT ~ perms.Size[2];
IF size=0 THEN ERROR;
IF size>1
THEN {
Log["%g perms desired for wire %g", LIST[NEW [INT ← size], wire]];
RETURN};
{desire: Permutation ~ IntFns.DeRef[perms.TheElt];
PermuteWire[wire, desire];
RETURN}};
d.cellTypes.Enumerate[StartCellType];
delayedPorts.Enumerate[DoDelayedPort];
delayedVerts.Enumerate[DoDelayedWire];
RETURN};
AllForPort:
PROC [v: Vertex, port: Port ←
NIL]
RETURNS [allSame:
BOOL ←
TRUE] ~ {
CheckEdge:
PROC [p: Port, w: Vertex, e: Edge] ~ {
IF p=NIL THEN ERROR;
IF port=NIL 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 => NULL;
im: Intermediary => NULL;
w: Wire => IF w.containingWire#NIL AND NOT AllForPort[w.containingWire] 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-- ~ IntFns.DeRef[ToChildren.Apply[parent].val];
names: Seq--of SteppyName-- ~ children.Compose[right: ToName, rightRestricts: FALSE];
perm ← IntFns.GradeUp[names, Colls.LexOrdering[NIL, LIST[nameStepSpace.SpaceOrdering]]];
RETURN};
PermutePort:
PROC [port: Port, perm: Permutation, doConnections:
BOOL] ~ {
oldKids: Seq ~ IntFns.DeRef[LichenNavigation.portToChildren.Apply[port].val] .CreateSimpleCopy;
n: INT ~ oldKids.Size;
prev: Port ← NIL;
index: INT ← 0;
FixElt:
PROC [pair: IntFns.IVPair] ~ {
newIndex: INT ~ pair.left;
oldIndex: INT ~ NARROW[pair.right, REF INT]^;
kid: Port ~ NARROW[oldKids.Apply[oldIndex].val];
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 ~ FindTopEdge[ci, port].v;
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 ~ IntFns.DeRef[LichenNavigation.wireToChildren.Apply[wire].val] .CreateSimpleCopy;
n: INT ~ oldKids.Size;
prev: Wire ← NIL;
index: INT ← 0;
FixElt:
PROC [pair: IntFns.IVPair] ~ {
newIndex: INT ~ pair.left;
oldIndex: INT ~ NARROW[pair.right, REF INT]^;
kid: Wire ~ NARROW[oldKids.Apply[oldIndex].val];
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-- ~ IntFns.CreateSimple[oneToOne: TRUE, dense: TRUE];
NoteOldEdge:
PROC [p: Port, w: Vertex, e: Edge] ~ {
IF e.sides[cellward].v#v THEN ERROR;
old.Append[e];
RETURN};
v.EnumerateImmediateEdges[NoteOldEdge, [cellward: FALSE, wireward: TRUE], forward];
{n: INT ~ old.Size;
oldFirstWireward: Edge ~ NARROW[old.First[].pair.right];
lastCellward: Edge ~ oldFirstWireward.sides[cellward].prev;
prev: Edge ← lastCellward;
prevSide: GraphDirection ← wireward;
index: INT ← 0;
FixElt:
PROC [pair: IntFns.IVPair] ~ {
newIndex: INT ~ pair.left;
oldIndex: INT ~ NARROW[pair.right, REF INT]^;
e: Edge ~ NARROW[old.Apply[oldIndex].val];
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}}};
Store:
PROC [pc: PairColls.PairColl, pair: PairColls.Pair] ~ {
lr: BOOL ~ pc.Functional[][leftToRight];
rl: BOOL ~ pc.Functional[][rightToLeft];
news: PairColls.NewsPair ~ pc.AddPair[pair, [[NOT lr, TRUE], [NOT rl, TRUE]]];
IF lr AND news[leftToRight]#new THEN ERROR;
IF rl AND news[rightToLeft]#new THEN ERROR;
};
END.