LichenSplitMerge.Mesa
Last tweaked by Mike Spreitzer on February 2, 1988 10:47:16 am PST
DIRECTORY AbSets, Asserting, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, LichenTransforms, LichenTransformsPrivate, Rope, SetBasics;
LichenSplitMerge: CEDAR PROGRAM
IMPORTS AbSets, Asserting, BiRels, IntStuff, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenNavigation, LichenTransformsPrivate, Rope, SetBasics
EXPORTS LichenTransforms =
BEGIN OPEN LichenArrayStuff, LichenNavigation, LichenDataStructure, LichenTransforms, LichenDataOps, LichenTransformsPrivate, Ints:IntStuff, Sets:AbSets;
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-- ~ BiRels.EnumSeqOfSet[fizz];
analysis: Analysis ~ NEW [AnalysisPrivate ← [
roles: fizz.Size.EN,
subjTypes: cs.Compose[instanceType, [TRUE, FALSE]].CreateVectorCopy[oneToOne: TRUE].Freeze,
wag: NEW [WireAnsweringPrivate ← [
oldSubjConnectionss: CreateRefSeq[fizz.Size.EN],
anses: BiRels.CreateHashFn[]
]],
doomedPorts: Sets.CreateHashSet[]
]];
{OPEN analysis;
connectionsV: VarOneToOne--port of to é port of from-- ~ BiRels.CreateHashOTO[];
pairsV: VarOneToOne ~ BiRels.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 subjTypes.ApplyI[i].MA # v.type THEN ERROR;
i ← i + 1;
};
fizz.EnumA[PerElt];
IF i # cs.Size.EN THEN ERROR;
};
IF NOT from.designs.HasMemA[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, inheritNames: from.inheritNames, internals: TRUE];
IF Survey[from, NIL, cs, analysis, TRUE] THEN ERROR;
{MoveWire: PROC [left, right: REF ANY] ~ {
wire: Wire ~ NARROW[left];
wa: WireAns ~ NARROW[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.VA]];
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.AddNewAA[wa.toPort, wa.fromPort];
AddEdge[[to.asUnorganized.mirror, wa.counterpart], wa.toPort]};
dontAdd => NULL;
ENDCASE => ERROR;
};
wag.anses.EnumAA[MoveWire];
};
FOR role: NATURAL IN [0 .. roles) DO
fci: CellInstance ~ NARROW[cs.ApplyI[role].MA];
tci: CellInstance ~ Instantiate[fci.type, to, noListData, 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.EN) DO
DeleteVertex[NARROW[cs.ApplyI[i].MA]];
ENDLOOP;
{KillWireAndPort: PROC [left, right: REF ANY] ~ {
wire: Wire ~ NARROW[left];
wa: WireAns ~ NARROW[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.EnumAA[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, fromArrayCT.inheritNames, NIL, NIL];
ta: Array ~ toArrayCT.asArray;
arrayConnectionsV: VarOneToOne--port of toArrayCT é port of fromArrayCT-- ~ BiRels.CreateHashOTO[];
arrayTPToWireV: VarFunction--port of ta b wire-- ~ BiRels.CreateHashFn[];
doomedArrayPortsV: VarSet--of port of fa-- ~ Sets.CreateHashSet[];
NotDoomed: PROC [fep: Port] RETURNS [BOOL]
~ {RETURN [NOT doomedFromPorts.HasMemA[fep]]};
HasNew: PROC [fep: Port] RETURNS [BOOL]
~ {RETURN [eltConnections.ApplyA[fep, rightToLeft].found]};
toNewComp: SubComponenting ~ CreateSubComponents[fa, HasNew];
inSameNewComp: BiRel--between svs of fa-- ~ toNewComp[TRUE].Compose[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.HasMemA[in]
THEN crossings ← CONS[[in, out, d], crossings]};
tNewStat: StatRep ~ CopySubGraph[fa, HasNew, eltConnections.Invert.AsConst, NoteCrossing];
sizeRange: Range2 ~ SizeRange[fa.size2];
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.ApplyA[crossings.first.hasNew.port, rightToLeft].MA];
tepw: Wire ~ NARROW[eltTPToWire.ApplyA[tep].MA];
fap: Port--of fromArrayCT-- ~ GetArrayPortForPort[fromArrayCT, aiB, crossings.first.hasnt.port, TRUE];
tap: Port--of toArrayCT-- ~ GetArrayPortForPort[toArrayCT, aiA, tep, TRUE];
np: BiRels.HadPair ~ arrayConnectionsV.AddAA[tap, fap];
IF np#ALL[none] AND np#ALL[same] THEN ERROR;
[] ← arrayTPToWireV.AddAA[tap, tepw];
design ← design;
ENDLOOP ENDLOOP;
ENDLOOP;
{fNewStat: StatRep ~ CopySubGraph[fa, NotDoomed, refsID, NIL];
FindRep: PROC [left, right: REF ANY] ~ {
fap: Port ~ NARROW[left];
dw: DumbWire ~ NARROW[right];
fep: Port ~ ScanPortsInDumbWire[fa, dw, NotDoomed].ep;
IF fep#NIL THEN {
ai: ArrayIndex ~ GetInstForPortInDumbWire[fa, dw, fep];
IF ai=ALL[-1] THEN ERROR;
fNewStat.apToPAI.AddNewAA[fap, NEW [PortAtIndexPrivate ← [fep, ai]]]}
ELSE IF NOT doomedArrayPortsV.AddA[fap] THEN ERROR;
RETURN};
fa.dumrep.apToWire.EnumAA[FindRep];
SetStatRep[fromArrayCT, fNewStat, TRUE];
{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];
RETURN};
FixArrays[design, fromArrayCT, toArrayCT, arrayConnections, doomedArrayPorts, arrayTPToWire, subTail, pairs];
FixInstances[fromArrayCT, toArrayCT, arrayConnections, doomedArrayPorts, arrayTPToWire, pairs];
doomedArrayPorts.EnumA[KillDoomedArrayPort];
RETURN}}};
fromAncestorCT.EnumerateArrays[SplitArray];
RETURN};
refsID: ConstOneToOne ~ BiRels.CreateFullIDSubset[SetBasics.refs];
FilterSVs: PROC [a: Array, Pf: PROC [Port] RETURNS [BOOL]] RETURNS [pass: Set--of sv of a-- ← Sets.CreateHashSet[statVerts]] ~ {
PerVertex: PROC [sv: StatVertex] RETURNS [BOOL] ~ {
IF Pf[sv.port] THEN IF NOT pass.AddA[sv] THEN ERROR;
RETURN[FALSE]};
[] ← ScanStatVertices[a, PerVertex];
RETURN};
CreateSubComponents: PROC [a: Array, Pf: PROC [Port] RETURNS [BOOL]] RETURNS [toComp: SubComponenting] ~ {
nComps: INT ← 0;
Start: PROC [sv: StatVertex] RETURNS [pass: BOOL ← FALSE] ~ {
b: BOOL ~ Pf[sv.port];
IF toComp[b].ApplyA[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 Pf[osv.port]#b THEN RETURN;
SELECT toComp[b].AddAA[osv, comp].had[leftToRight] FROM
same => NULL;
different => ERROR;
none => ExploreFrom[osv];
ENDCASE => ERROR;
RETURN};
toComp[b].AddNewAA[sv, comp];
[] ← ScanStatEdgesFrom[a.statrep, sv, ExploreEdge];
RETURN};
ExploreFrom[sv];
nComps ← nComps+1}};
toComp ← [
FALSE: BiRels.CreateHashFn[invable: TRUE],
TRUE: BiRels.CreateHashFn[invable: TRUE]];
[] ← ScanStatVertices[a, Start];
RETURN};
CopySubGraph: PROC [a: Array, Pf: PROC [Port] 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.ApplyA[vs[FALSE].port].MA];
vs[TRUE].port ← NARROW[portMap.ApplyA[vs[TRUE].port].MA];
[] ← 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, Pf, AddEdge, PassCrosser];
RETURN};
EnumerateSubGraph: PROC [a: Array, directs: {include, exclude}, Pf: PROC [Port] RETURNS [BOOL], PerEdge: PROC [vs: ARRAY BOOL OF StatVertexPrivate, d: Int2], PerCrosser: PROC [in, out: StatVertex, d: Int2]] ~ {
seenFailures: Set--of StatVertex-- ~ Sets.CreateHashSet[statVerts];
PerVertex: PROC [sv: StatVertex] RETURNS [pass: BOOL ← FALSE] ~ {
IF Pf[sv.port] THEN {
PassEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [pass: BOOL ← FALSE] ~ {
IF Pf[se.vs[ob].port] 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.AddA[sv] THEN {
seenSuccesses: Set--of PortAtIndex-- ~ Sets.CreateHashSet[portsAtIndices];
indices: Function--StatVertex b ArrayIndex-- ~ BiRels.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 Pf[osv.port] THEN [] ← seenSuccesses.AddA[NEW [PortAtIndexPrivate ← [osv.port, ai]]]
ELSE IF seenFailures.AddA[osv] THEN ExploreFrom[osv, oai]
ELSE IF NARROW[indices.ApplyA[osv].MA, REF ArrayIndex]^ # oai THEN foundCycle ← TRUE;
RETURN};
indices.AddNewAA[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[Ints.two].CompareI[2]<equal THEN RETURN;
{sseq: Seq--of PortAtIndex-- ~ BiRels.EnumSeqOfSet[seenSuccesses.Freeze].CreateVectorCopy[];
n: NATURAL ~ sseq.Size[].EN;
FOR i: NATURAL IN [0 .. n) DO
piA: PortAtIndex ~ NARROW[sseq.ApplyI[i].MA];
svpA: StatVertexPrivate ~ [piA.port, Int2Mod[piA.ai, a.basePeriod]];
FOR j: NATURAL IN [0 .. i) DO
piB: PortAtIndex ~ NARROW[sseq.ApplyI[j].MA];
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 NOT connections.MappingEmpty[AV[tp], leftToRight] 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: Sets.Value] ~ {
fp: Port--of fa-- ~ NARROW[ra.VA];
w: Wire ~ NARROW[FindCellConnection[fci, fp]];
IF seen THEN ERROR ELSE seen ← TRUE;
IF w=NIL THEN ERROR;
AddEdges[[tci, w], tp];
};
connections.EnumerateMapping[AV[tp], PerFrom];
IF seen THEN NULL
ELSE IF NOT ConnectChildren[tp, FALSE] THEN {
w: Wire ~ CreateWire[containingCT: parentCT, copy: NARROW[tpToWire.ApplyA[tp].MDA]];
AddEdges[[tci, w], tp];
};
ENDLOOP;
};
};
[] ← ConnectChildren[toAncestorCT.port, TRUE];
UnlinkPorts[fci, doomedFromPorts];
pairs.AddNewAA[fci, tci];
RETURN};
EnumerateInstances[fromAncestorCT, FixInstance, FALSE];
RETURN};
Listify: PROC [set: Set] RETURNS [list: LORA] ~ {
AddElt: PROC [val: Sets.Value] ~ {
steppy: SteppyName ~ VSn[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.