LichenSplitMerge.Mesa
Last tweaked by Mike Spreitzer on October 20, 1987 8:17:13 pm PDT
DIRECTORY Asserting, LichenArrayStuff, Collections, LichenDataOps, LichenDataStructure, IntFunctions, LichenNavigation, PairCollections, LichenTransforms, LichenTransformsPrivate, Rope;
LichenSplitMerge: CEDAR PROGRAM
IMPORTS Asserting, LichenArrayStuff, Collections, LichenDataOps, LichenDataStructure, IntFunctions, LichenNavigation, PairCollections, LichenTransformsPrivate, Rope
EXPORTS LichenTransforms =
BEGIN OPEN LichenArrayStuff, LichenNavigation, LichenDataStructure, LichenTransforms, LichenDataOps, LichenTransformsPrivate, Colls:Collections, PairColls:PairCollections, IntFns:IntFunctions;
PortAns: TYPE ~ REF PortAnsPrivate;
PortAnsPrivate: TYPE ~ RECORD [
from, to: Port,
doFrom: PortAction ← leave,
doTo: PortAction[dontAdd..addPort] ← dontAdd
];
SplitType: PUBLIC PROC [design: Design, fizz: ConstSet--of CellInstance--] RETURNS [from, to: CellType, pairs: ConstOneToOne--instance of from or ancestor é instance of to or ancestor--] ~ {
cs: Seq--role é fizzee-- ~ IntFns.CreateFromCollection[fizz];
analysis: Analysis ~ NEW [AnalysisPrivate ← [
roles: fizz.Size[],
subjTypes: cs.Compose[right: instanceType, rightRestricts: FALSE].CreateSimpleCopy[oneToOne: TRUE].Freeze,
wag: NEW [WireAnsweringPrivate ← [
oldSubjConnectionss: CreateRefSeq[fizz.Size[]],
anses: PairColls.CreateHashFn[]
]],
doomedPorts: Colls.CreateHashSet[]
]];
{OPEN analysis;
connectionsV: VarOneToOne--port of to é port of from-- ~ PairColls.CreateHashOTO[];
pairsV: VarOneToOne ~ PairColls.CreateHashOTO[];
nameParts: LOLORA ← NIL;
toName, subTail: ROPE;
IF roles=0 THEN Error["Null fission"];
from ← NIL;
{i: INT ← 0;
PerElt: PROC [ra: REF ANY] ~ {v: CellInstance ~ NARROW[ra];
IF v.type=NIL OR v.containingCT=NIL THEN ERROR;
IF from=NIL THEN from ← v.containingCT ELSE IF from#v.containingCT THEN Error["Fission of vertices not all having same parent"];
nameParts ← CONS[Listify[v.VertexNames], nameParts];
IF v.type # subjTypes.Apply[i].val THEN ERROR;
i ← i + 1;
};
fizz.Enumerate[PerElt];
IF i # cs.Size THEN ERROR;
};
IF NOT from.designs.HasMember[design] THEN ERROR;
subTail ← RopeCrossCat[nameParts];
toName ← RopeCrossCat[LIST[Select[nameReln, 1, from.otherPublic], LIST[subTail]]];
subTail ← Rope.Concat["-", subTail];
to ← CreateCellType[design: design, cellTypeName: toName, class: NIL, internals: TRUE];
IF Survey[from, NIL, cs, analysis, TRUE] THEN ERROR;
{MoveWire: PROC [pair: PairColls.Pair] ~ {
wire: Wire ~ NARROW[pair[left]];
wa: WireAns ~ NARROW[pair[right]];
IF NOT wa.analyzed THEN ERROR;
IF wa.counterpart # NIL THEN ERROR;
wa.counterpart ← CreateWire[containingCT: to, copy: wire, names: wire.VertexNames.Copy.data];
SELECT wa.doFrom FROM
addPort => {
wa.fromPort ← AddPort[[parent: from.port, wire: wire]];
AddEdge[[from.asUnorganized.mirror, wire], wa.fromPort]};
leave, dontAdd, dePort => NULL;
ENDCASE => ERROR;
SELECT wa.doTo FROM
addPort => {
wa.toPort ← AddPort[[parent: to.port, wire: wa.counterpart]];
IF wa.fromPort=NIL THEN ERROR;
connectionsV.AddNewPair[[wa.toPort, wa.fromPort]];
AddEdge[[to.asUnorganized.mirror, wa.counterpart], wa.toPort]};
dontAdd => NULL;
ENDCASE => ERROR;
};
wag.anses.Enumerate[MoveWire];
};
FOR role: NATURAL IN [0 .. roles) DO
fci: CellInstance ~ NARROW[cs.Apply[role].val];
tci: CellInstance ~ Instantiate[fci.type, to, fci.other];
MoveConnection: PROC [subjPort: Port, fwire: Wire] ~ {
wa: WireAns = GetRPAns[wag, role, subjPort, fwire, FALSE];
IF NOT wa.analyzed THEN ERROR;
AddEdges[[tci, wa.counterpart], subjPort];
};
EnumerateTopConnections[fci, MoveConnection];
ENDLOOP;
{connections: ConstOneToOne ~ connectionsV.Freeze;
doomedPortsC: ConstSet ~ doomedPorts.Freeze;
FixArrays[design, from, to, connections, doomedPortsC, portToInternalWire, subTail, pairsV];
FixInstances[from, to, connections, doomedPortsC, portToInternalWire, pairsV];
FOR i: INT IN [0 .. cs.Size) DO
DeleteVertex[NARROW[cs.Apply[i].val]];
ENDLOOP;
{KillWireAndPort: PROC [pair: PairColls.Pair] ~ {
wire: Wire ~ NARROW[pair[left]];
wa: WireAns ~ NARROW[pair[right]];
IF NOT wa.analyzed THEN ERROR;
IF wa.counterpart=NIL THEN ERROR;
SELECT wa.doFrom FROM
addPort => NULL;
leave, dontAdd => NULL;
dePort => RemovePort[wa.fromPort];
ENDCASE => ERROR;
IF NOT (wa.sawElse OR wa.sawBords) THEN DeleteVertex[wire];
design ← design;
};
wag.anses.Enumerate[KillWireAndPort];
};
pairs ← pairsV.Freeze;
}}};
SubComponenting: TYPE ~ ARRAY BOOL OF Function--sv b component of subgraph of static graph--;
FixArrays: PROC
[
design: Design,
fromAncestorCT, toAncestorCT: CellType,
eltConnections: ConstOneToOne--port of toAncestorCT é port of fromAncestorCT--,
doomedFromPorts: ConstSet--of port of fromAncestorCT--,
eltTPToWire: UWFunction--port of toAncestorCT b prototypical wire--,
subTail: ROPE--to append to name of from array--,
pairs: VarOneToOne--instance of from or ancestor é instance of to or ancestor--
] ~ {
SplitArray: PROC [fromArrayCT: CellType] ~ {
fa: Array ~ fromArrayCT.asArray;
faName: ROPE ~ NARROW[Asserting.FnVal[nameReln, fromArrayCT.otherPublic]];
taName: ROPE ~ faName.Cat[subTail];
toArrayCT: CellType ~ CreateArray[design, taName, NIL, toAncestorCT, fa.size2, fa.basePeriod, NIL, NIL];
ta: Array ~ toArrayCT.asArray;
arrayConnectionsV: VarOneToOne--port of toArrayCT é port of fromArrayCT-- ~ PairColls.CreateHashOTO[];
arrayTPToWireV: VarFunction--port of ta b wire-- ~ PairColls.CreateHashFn[];
doomedArrayPortsV: VarSet--of port of fa-- ~ Colls.CreateHashSet[];
portRep: VarFunction--port of fa b non-doomed PortAtIndex-- ~ PairColls.CreateHashFn[invable: FALSE];
NotDoomed: PROC [sv: StatVertex] RETURNS [BOOL]
~ {RETURN [NOT doomedFromPorts.HasMember[sv.port]]};
HasNew: PROC [sv: StatVertex] RETURNS [BOOL]
~ {RETURN [eltConnections.Apply[sv.port, rightToLeft].found]};
toNewComp: SubComponenting ~ CreateSubComponents[fa, HasNew];
inSameNewComp: Relation--between svs of fa-- ~ PairColls.Compose[[toNewComp[TRUE], toNewComp[TRUE].Invert]];
nonDoomedSVs: Set--of sv of fa-- ~ FilterSVs[fa, NotDoomed];
inNonDoomedNewComp: Set--of sv of fa-- ~ inSameNewComp.Image[nonDoomedSVs];
crossings: LIST OF RECORD [hasNew, hasnt: StatVertex, d: Int2] ← NIL;
NoteCrossing: PROC [in, out: StatVertex, d: Int2] ~ {
IF inNonDoomedNewComp.HasMember[in]
THEN crossings ← CONS[[in, out, d], crossings]};
tNewStat: StatRep ~ CopySubGraph[fa, HasNew, eltConnections.Invert.AsConst, NoteCrossing];
sizeRange: Range2 ~ SizeRange[fa.size2];
FindRep: PROC [pair: PairColls.Pair] ~ {
fap: Port ~ NARROW[pair[left]];
dw: DumbWire ~ NARROW[pair[right]];
NotDoomed: PROC [fep: Port] RETURNS [BOOL] ~ {
IF NOT doomedFromPorts.HasMember[fep] THEN RETURN [TRUE];
RETURN [FALSE]};
fep: Port ~ ScanPortsInDumbWire[fa, dw, NotDoomed].ep;
IF fep#NIL THEN {
ai: ArrayIndex ~ GetInstForPortInDumbWire[fa, dw, fep];
IF ai=ALL[-1] THEN ERROR;
portRep.AddNewPair[[fap, NEW [PortAtIndexPrivate ← [fep, ai]]]]}
ELSE IF NOT doomedArrayPortsV.AddElt[fap] THEN ERROR;
RETURN};
SetStatRep[toArrayCT, tNewStat, FALSE];
FOR crossings ← crossings, crossings.rest WHILE crossings # NIL DO
rA: Range2 ~ Range2Intersection[sizeRange, Range2Off[sizeRange, Int2Neg[crossings.first.d]]];
irA: Range2 ~ Range2Div[rA, fa.basePeriod, crossings.first.hasNew.phase];
FOR if: NATURAL IN [NATURAL[irA[Foo].min] .. NATURAL[irA[Foo].maxPlusOne]) DO FOR ib: NATURAL IN [NATURAL[irA[Bar].min] .. NATURAL[irA[Bar].maxPlusOne]) DO
aiA: ArrayIndex ~ Int2Mul[[if, ib], fa.basePeriod, crossings.first.hasNew.phase];
aiB: ArrayIndex ~ Int2Add[aiA, crossings.first.d];
tep: Port ~ NARROW[eltConnections.Apply[crossings.first.hasNew.port, rightToLeft].val];
tepw: Wire ~ NARROW[eltTPToWire.Apply[tep].val];
fap: Port--of fromArrayCT-- ~ GetArrayPortForPort[fromArrayCT, aiB, crossings.first.hasnt.port, TRUE];
tap: Port--of toArrayCT-- ~ GetArrayPortForPort[toArrayCT, aiA, tep, TRUE];
np: PairColls.NewsPair ~ arrayConnectionsV.AddPair[[tap, fap]];
IF np#ALL[new] AND np#ALL[same] THEN ERROR;
[] ← arrayTPToWireV.AddPair[[tap, tepw]];
design ← design;
ENDLOOP ENDLOOP;
ENDLOOP;
fa.dumrep.apToWire.Enumerate[FindRep];
{fNewStat: StatRep ~ CopySubGraph[fa, NotDoomed, PairColls.id, NIL];
MakeNewPort: PROC [pair: PairColls.Pair] ~ {
fap: Port ~ NARROW[pair[left]];
pai: PortAtIndex ~ NARROW[pair[right]];
dw: DumbWire ~ GetDumbWire[fa, pai.port, pai.ai];
IF dw=NIL THEN ERROR--exporting a composite wire that doesn't really exist--;
fa.dumrep.apToWire.AddNewPair[[fap, dw]];
RETURN};
SetStatRep[fromArrayCT, fNewStat, TRUE];
[] ← fa.dumrep.apToWire.RemColl[fa.dumrep.apToWire];
IF NOT fa.dumrep.apToWire.Empty[] THEN ERROR;
portRep.Enumerate[MakeNewPort];
{arrayConnections: ConstFunction ~ arrayConnectionsV.Freeze;
doomedArrayPorts: ConstSet ~ doomedArrayPortsV.Freeze;
arrayTPToWire: ConstFunction ~ arrayTPToWireV.Freeze;
KillDoomedArrayPort: PROC [ra: REF ANY] ~ {
p: Port--of fromArrayCT-- ~ NARROW[ra];
RemovePort[p];
};
FixArrays[design, fromArrayCT, toArrayCT, arrayConnections, doomedArrayPorts, arrayTPToWire, subTail, pairs];
FixInstances[fromArrayCT, toArrayCT, arrayConnections, doomedArrayPorts, arrayTPToWire, pairs];
doomedArrayPorts.Enumerate[KillDoomedArrayPort];
RETURN}}};
fromAncestorCT.EnumerateArrays[SplitArray];
RETURN};
FilterSVs: PROC [a: Array, Vf: PROC [StatVertex] RETURNS [BOOL]] RETURNS [pass: Set--of sv of a--] ~ {
PerVertex: PROC [sv: StatVertex] RETURNS [BOOL] ~ {
IF Vf[sv] THEN IF NOT pass.AddElt[sv] THEN ERROR;
RETURN[FALSE]};
pass ← Colls.CreateHashSet[statVerts];
[] ← ScanStatVertices[a, PerVertex];
RETURN};
CreateSubComponents: PROC [a: Array, Vf: PROC [StatVertex] RETURNS [BOOL]] RETURNS [toComp: SubComponenting] ~ {
nComps: INT ← 0;
Start: PROC [sv: StatVertex] RETURNS [pass: BOOL ← FALSE] ~ {
b: BOOL ~ Vf[sv];
IF toComp[b].Apply[sv].found THEN RETURN;
{comp: REF INT ~ NEW [INT ← nComps];
ExploreFrom: PROC [sv: StatVertex] ~ {
ExploreEdge: PROC [se:StatEdge, ob:BOOL] RETURNS [pass:BOOL←FALSE] ~{
osv: StatVertex ~ se.vs[ob];
IF Vf[osv]#b THEN RETURN;
SELECT toComp[b].AddPair[[osv, comp]].news[leftToRight] FROM
same => NULL;
different => ERROR;
new => ExploreFrom[osv];
ENDCASE => ERROR;
RETURN};
toComp[b].AddNewPair[[sv, comp]];
[] ← ScanStatEdgesFrom[a.statrep, sv, ExploreEdge];
RETURN};
ExploreFrom[sv];
nComps ← nComps+1}};
toComp ← [
FALSE: PairColls.CreateHashFn[invable: TRUE],
TRUE: PairColls.CreateHashFn[invable: TRUE]];
[] ← ScanStatVertices[a, Start];
RETURN};
CopySubGraph: PROC [a: Array, Vf: PROC [StatVertex] RETURNS [BOOL], portMap: ConstOneToOne, NoteCrossing: PROC [in, out: StatVertex, d: Int2]] RETURNS [subCopy: StatRep] ~ {
AddEdge: PROC [vs: ARRAY BOOL OF StatVertexPrivate, d: Int2] ~ {
vs[FALSE].port ← NARROW[portMap.Apply[vs[FALSE].port].val];
vs[TRUE].port ← NARROW[portMap.Apply[vs[TRUE].port].val];
[] ← AddStatEdge[subCopy, [
vs: [
FALSE: NEW [StatVertexPrivate ← vs[FALSE]],
TRUE: NEW [StatVertexPrivate ← vs[TRUE]]],
d: d]];
RETURN};
PassCrosser: PROC [in, out: StatVertex, d: Int2] ~ {NoteCrossing[in, out, d]};
subCopy ← CreateStatRep[];
EnumerateSubGraph[a, include, Vf, AddEdge, PassCrosser];
RETURN};
EnumerateSubGraph: PROC [a: Array, directs: {include, exclude}, Vf: PROC [StatVertex] RETURNS [BOOL], PerEdge: PROC [vs: ARRAY BOOL OF StatVertexPrivate, d: Int2], PerCrosser: PROC [in, out: StatVertex, d: Int2]] ~ {
seenFailures: Set--of StatVertex-- ~ Colls.CreateHashSet[statVerts];
PerVertex: PROC [sv: StatVertex] RETURNS [pass: BOOL ← FALSE] ~ {
IF Vf[sv] THEN {
PassEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [pass: BOOL ← FALSE] ~ {
IF Vf[se.vs[ob]] THEN {IF directs=include THEN PerEdge[[se.vs[FALSE]^, se.vs[TRUE]^], se.d]}
ELSE {IF PerCrosser#NIL THEN PerCrosser[sv, se.vs[ob], IF ob THEN se.d ELSE Int2Neg[se.d]]};
RETURN};
IF directs=include OR PerCrosser#NIL THEN IF ScanStatEdgesFrom[a.statrep, sv, PassEdge].found THEN ERROR;
RETURN}
ELSE {
IF seenFailures.AddElt[sv] THEN {
seenSuccesses: Set--of PortAtIndex-- ~ Colls.CreateHashSet[portsAtIndices];
indices: Function--StatVertex b ArrayIndex-- ~ PairColls.CreateHashFn[invable: FALSE];
foundCycle: BOOL ← FALSE;
ExploreFrom: PROC [sv: StatVertex, ai: ArrayIndex] ~ {
ExploreEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [pass: BOOL ← FALSE] ~ {
osv: StatVertex ~ se.vs[ob];
oai: ArrayIndex ~ Int2Add[ai, IF ob THEN se.d ELSE Int2Neg[se.d]];
IF Vf[osv] THEN [] ← seenSuccesses.AddElt[NEW [PortAtIndexPrivate ← [osv.port, ai]]]
ELSE IF seenFailures.AddElt[osv] THEN ExploreFrom[osv, oai]
ELSE IF NARROW[indices.Apply[osv].val, REF ArrayIndex]^ # oai THEN foundCycle ← TRUE;
RETURN};
indices.AddNewPair[[sv, NEW [ArrayIndex ← ai]]];
IF ScanStatEdgesFrom[a.statrep, sv, ExploreEdge].found THEN ERROR;
RETURN};
ExploreFrom[sv, WidenNat2[sv.phase]];
IF seenSuccesses.Empty[] THEN RETURN;
IF foundCycle THEN ERROR nyet;
IF seenSuccesses.Size[2] < 2 THEN RETURN;
{sseq: Seq--of PortAtIndex-- ~ IntFns.CreateFromCollection [seenSuccesses.Freeze].CreateSimpleCopy[];
n: NATURAL ~ sseq.Size[];
FOR i: NATURAL IN [0 .. n) DO
piA: PortAtIndex ~ NARROW[sseq.Apply[i].val];
svpA: StatVertexPrivate ~ [piA.port, Int2Mod[piA.ai, a.basePeriod]];
FOR j: NATURAL IN [0 .. i) DO
piB: PortAtIndex ~ NARROW[sseq.Apply[j].val];
PerEdge[[svpA, [piB.port, Int2Mod[piB.ai, a.basePeriod]]], Int2Sub[piB.ai, piA.ai]];
a ← a;
ENDLOOP;
a ← a;
ENDLOOP;
}};
RETURN};
};
IF ScanStatVertices[a, PerVertex].found THEN ERROR;
RETURN};
FixInstances: PROC
[
fromAncestorCT, toAncestorCT: CellType,
connections: ConstOneToOne--port of toAncestorCT é port of fromAncestorCT--,
doomedFromPorts: ConstSet--of port of fromAncestorCT--,
tpToWire: UWFunction--port of toAncestorCT b prototypical wire--,
pairs: VarOneToOne--instance of from or ancestor é instance of to or ancestor--
] ~ {
FixInstance: PROC [fci: CellInstance] ~ {
parentCT: CellType ~ fci.containingCT;
tci: CellInstance ~ Instantiate[toAncestorCT, parentCT];
ConnectChildren: PROC [parent: Port, do: BOOL] RETURNS [done: BOOL] ~ {
done ← FALSE;
FOR tp: Port ← FirstChildPort[parent], NextChildPort[tp] WHILE tp # NIL DO
IF connections.MappingSize[tp, leftToRight, 1]#0 THEN done ← TRUE;
ENDLOOP;
IF done OR do THEN {
FOR tp: Port ← FirstChildPort[parent], NextChildPort[tp] WHILE tp # NIL DO
seen: BOOL ← FALSE;
PerFrom: PROC [ra: REF ANY] ~ {
fp: Port--of fa-- ~ NARROW[ra];
w: Wire ~ FindTransitiveConnection[fci, fp];
IF seen THEN ERROR ELSE seen ← TRUE;
IF w=NIL THEN ERROR;
AddEdges[[tci, w], tp];
};
connections.EnumerateMapping[tp, PerFrom];
IF seen THEN NULL
ELSE IF NOT ConnectChildren[tp, FALSE] THEN {
w: Wire ~ CreateWire[containingCT: parentCT, copy: NARROW[tpToWire.Apply[tp].DVal]];
AddEdges[[tci, w], tp];
};
ENDLOOP;
};
};
[] ← ConnectChildren[toAncestorCT.port, TRUE];
UnlinkPorts[fci, doomedFromPorts];
IF pairs.AddPair[[fci, tci], PairColls.addIfNew]#[new, new] THEN ERROR;
};
EnumerateInstances[fromAncestorCT, FixInstance, FALSE];
RETURN};
Listify: PROC [set: Set] RETURNS [list: LORA] ~ {
AddElt: PROC [val: REF ANY] ~ {
steppy: SteppyName ~ NARROW[val];
list ← CONS[UnparseSteppyName[steppy], list];
RETURN};
list ← NIL;
set.Enumerate[AddElt];
RETURN};
Select: PROC [reln: Asserting.Term, position: NATURAL, from: Assertions] RETURNS [terms: Asserting.Terms] ~ {
Filter: PROC [assertion: Asserting.Assertion] ~ {
these: Asserting.Terms ← Asserting.TermsOf[assertion];
THROUGH [1 .. position) DO these ← these.rest ENDLOOP;
terms ← CONS[these.first, terms];
};
Asserting.EnumerateAssertionsAbout[reln, from, Filter];
};
RopeCrossCat: PROC [lolora: LOLORA] RETURNS [ans: ROPE] ~ {
ans ← NIL;
FOR lolora ← lolora, lolora.rest WHILE lolora # NIL DO
lora: LORA ← NARROW[lolora.first];
subAns: ROPE ← NIL;
n: NATURAL ← 0;
FOR lora ← lora, lora.rest WHILE lora # NIL DO
n ← n + 1;
SELECT n FROM
1 => NULL;
2 => subAns ← Rope.Cat["{", subAns, "|"];
ENDCASE => subAns ← subAns.Concat["|"];
subAns ← subAns.Concat[NARROW[lora.first]];
ENDLOOP;
IF n > 1 THEN subAns ← subAns.Concat["}"];
IF ans # NIL THEN ans ← ans.Concat["-"];
ans ← ans.Concat[subAns];
ENDLOOP;
ans ← ans;
};
END.