DIRECTORY AbSets, BiRelBasics, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics;

LichenDataImplArrays3: CEDAR PROGRAM
IMPORTS AbSets, BiRelBasics, BiRels, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics
EXPORTS LichenDataOps
=

BEGIN OPEN IS:IntStuff, Sets:AbSets, LIB:LichenIntBasics, LIB, LichenArrayPrivate, LichenDataStructure, LichenDataOps;

MayDeletePorts: PUBLIC PROC [ct: CellType, ports: Set--of port--, timid, isWholeTrees: BOOL] RETURNS [whyNot: ROPE _ NIL] ~ {
d: Design ~ ct.d;
PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
act: CellType ~ NARROW[actv.VA];
a: Array ~ act.asArray;
verts: Set--of StatVertex-- ~ Sets.CreateHashSet[a.statrep.svSpace];
edges: Set ~ a.statrep.portEdge[FALSE].Image[ports] .Union[a.statrep.portEdge[TRUE].Image[ports]];
CheckEdge: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
se: StatEdge ~ NARROW[sev.VA];
FOR b: BOOL IN BOOL DO
sv: StatVertex ~ se.SeSv[a, b];
IF ports.HasMemA[sv.port] THEN {
IF sv#se.SeSv[a, NOT b] AND NOT verts.AddElt[SvV[sv]] --this test is stronger than it needs to be, but maybe there's no arising case that exercises the difference-- THEN {
whyNot _ IO.PutFR["deleting static vertex %g@%g,%g in %g might partition a component", [rope[Describe[d, sv.port, ct]]], [integer[sv.phase[X]]], [integer[sv.phase[Y]]], [rope[Describe[d, act, d]]]];
RETURN [TRUE]}};
ENDLOOP;
RETURN [FALSE]};
[] _ edges.Scan[CheckEdge];
IF whyNot#NIL THEN RETURN [TRUE];
{losers, abandoned: Set;
[losers, abandoned] _ ArrayLosers[act, ports, FALSE];
IF NOT timid THEN ERROR --not implemented--;
IF NOT abandoned.Empty THEN whyNot _ IO.PutFR["would abandon ports %g of %g", [rope[abandoned.FormatSet[length: INT.LAST, order: act.nameOrder[p]]]], [rope[act.ACtName[]]]]
ELSE whyNot _ MayDeletePorts[act, losers, timid, TRUE];
RETURN [whyNot#NIL]}};
IF NOT isWholeTrees THEN ERROR --case not implemented--;
[] _ d.arrayElt.ScanMapping[AV[ct], PerArray, rightToLeft];
RETURN};

NoteExEltPorts: PUBLIC PROC [ect: CellType, eps: Set, mayHaveConsequences: BOOL, log: IO.STREAM _ NIL] ~ {
d: Design ~ ect.d;
PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
act: CellType ~ NARROW[actv.VA];
a: Array ~ act.asArray;
edges: Set ~ a.statrep.portEdge[FALSE].Image[eps] .Union[a.statrep.portEdge[TRUE].Image[eps]] .CreateHashCopy[];
losers, abandoned: Set;
IF a.buildPhase # statrepFixed THEN ERROR;
[losers, abandoned] _ ArrayLosers[act, eps, TRUE];
IF NOT abandoned.Empty THEN ERROR --shouldn't arise--;
{notLosers: Set ~ losers.Negate;
Undumb: PROC [epv: Sets.Value] RETURNS [BOOL] ~ {
ep: Port ~ NARROW[epv.VA];
dws: REF Fn ~ NARROW[a.dumrep.epToWire.Apply[epv].MDA];
PerWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
IF NOT dw.eps.DeleteA[ep] THEN ERROR;
IF dw.eps.Empty THEN {
aps: Set ~ a.dumrep.epToWire.Mapping[AV[dw], rightToLeft];
IF NOT aps.Intersection[notLosers].Empty THEN ERROR;
IF NOT a.dumrep.wires.RemA[dw] THEN ERROR;
--let DeletePorts[aps] fix apToWire--};
RETURN [FALSE]};
IF dws#NIL AND dws^.SetOn[right].Scan[PerWire].found THEN ERROR;
RETURN [FALSE]};
[] _ a.statrep.edges.RemSet[edges] --AAASEP says we don't have to worry about creating the child edges, if any--;
[] _ a.statrep.portEdge[FALSE].DeleteSet[edges, right];
[] _ a.statrep.portEdge[TRUE].DeleteSet[edges, right];
[] _ a.statrep.svEdge[FALSE].DeleteSet[edges, right];
[] _ a.statrep.svEdge[TRUE].DeleteSet[edges, right];
IF a.buildPhase = statrepFixed THEN {
IF eps.Scan[Undumb].found THEN ERROR;
[] _ a.dumrep.epToWire.DeleteSet[eps]};
IF NOT losers.Empty THEN {
IF NOT mayHaveConsequences THEN ERROR;
IF log#NIL THEN log.PutF["DelPs %g of %g exded.\n", [rope[losers.FormatSet[length: INT.LAST, order: act.nameOrder[p]]]], [rope[Describe[d, act, d]]]];
DeletePorts[act, losers, TRUE, FALSE, log];
log _ log};
RETURN [FALSE]}};
[] _ d.arrayElt.ScanMapping[AV[ect], PerArray, rightToLeft];
RETURN};

NoteEltPortMerge: PUBLIC PROC [ect: CellType, kept: Port, lost: Set--of port--] ~ {
d: Design ~ ect.d;
PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
act: CellType ~ NARROW[actv.VA];
a: Array ~ act.asArray;
kdws: REF Fn _ GetDumbWires[a, kept, FALSE];
PerLoser: PROC [lv: Sets.Value] RETURNS [BOOL] ~ {
loser: Port ~ NARROW[lv.VA];
ldws: REF Fn ~ GetDumbWires[a, loser, FALSE];
FixDW: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
dw.eps.SubstituteA[loser, kept, left];
RETURN [FALSE]};
IF ldws#NIL THEN {
IF kdws=NIL THEN kdws _ GetDumbWires[a, kept, TRUE];
{had: BiRels.HadSetPair ~ kdws^.AddSet[ldws^, BiRels.addIfNew];
IF had[leftToRight][different] THEN ERROR;
IF ldws^.SetOn[right].Scan[FixDW].found THEN ERROR;
IF NOT a.dumrep.epToWire.DeleteA[loser] THEN ERROR}};
RETURN [FALSE]};
FixEdge: PROC [ev: Sets.Value] RETURNS [BOOL] ~ --probably relies on AAASEP-- {
se: StatEdge ~ NARROW[ev.VA];
FOR b: BOOL IN BOOL DO
sv: StatVertex ~ se.SeSv[a, b];
IF lost.HasMemA[sv.port] THEN {
[] _ a.statrep.portEdge[b].AddAA[kept, se];
[] _ a.statrep.svEdge[b].AddPair[[SvV[[kept, sv.phase]], AV[se]]]};
ENDLOOP;
RETURN [FALSE]};
FixExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
pai: PortAtIndex ~ VPai[pair[right]];
IF lost.HasMemA[pai.port] THEN {
had: BiRels.HadPair ~ a.statrep.apToPAI.AddPair[[pair[left], PaiV[[kept, pai.ai]]], BiRels.addIfOld];
IF had[leftToRight] # different THEN ERROR};
RETURN [FALSE]};
edges: Set ~ a.statrep.portEdge[FALSE].Image[lost] .Union[a.statrep.portEdge[TRUE].Image[lost]] .CreateHashCopy[];
IF a.buildPhase # statrepFixed THEN ERROR;
IF lost.Scan[PerLoser].found THEN ERROR;
IF edges.Scan[FixEdge].found THEN ERROR;
IF a.statrep.apToPAI.Scan[FixExport].found THEN ERROR;
TrimStatrep[act, a, edges];
RETURN [FALSE]};
[] _ d.arrayElt.ScanMapping[AV[ect], PerArray, rightToLeft];
RETURN};

ArrayLosers: PROC [act: CellType, eps: Set, replace: BOOL] RETURNS [losers, abandoned: Set] ~ {
d: Design ~ act.d; a: Array ~ act.asArray;
starts: Set ~ Sets.CreateHashSet[d.eSpace];
roots: Set ~ Sets.CreateHashSet[d.eSpace];
cousins: Set ~ d.ancest.Image[roots, rightToLeft];
CheckExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
pai: PortAtIndex ~ VPai[pair[right]];
IF eps.HasMemA[pai.port] THEN {
ap: Port ~ NARROW[pair[left].VA];
dw: DumbWire ~ NARROW[a.dumrep.apToWire.ApplyA[ap].MA];
repl: Port ~ NARROW[dw.eps.SetOn[left].Difference[eps].AnElt.MDA];
IF repl=NIL THEN {[] _ starts.AddA[ap]; [] _ roots.AddA[d.PWRoot[ap]]}
ELSE IF replace THEN {
epcai: BiRels.Pair ~ dw.eps.ScanMapping[AV[repl], Sets.AcceptAny].P;
cai: NAT ~ epcai[right].VI;
ai: Int2 ~ DecomposeAI[a, cai];
IF epcai[left] # AV[repl] THEN ERROR;
[] _ a.statrep.apToPAI.AddPair[[AV[ap], PaiV[[repl, ai]] ]]};
};
RETURN [FALSE]};
IF a.buildPhase # statrepFixed THEN ERROR;
IF a.statrep.apToPAI.Scan[CheckExport].found THEN ERROR;
losers _ d.ancest.Image[starts].CreateHashCopy[];
abandoned _ cousins.Difference[losers];
RETURN};

intSets: Sets.Space ~ Sets.CreateSetSpace[SetBasics.ints];

TryToMergeDumbWires: PUBLIC PROC [d: Design, act: CellType, wires: Set] RETURNS [balks: Set] ~ {
a: Array ~ act.asArray;
balks _ Sets.CreateHashSet[a.dumrep.dwSpace];
IF wires.Trivial THEN RETURN;
DO
AddEdge: PROC [sep: StatEdgeSpec] ~ {
[] _ EnsureStatEdge[d, a.statrep, sep, FALSE, TRUE, FALSE];
RETURN};
anDw: DumbWire ~ NARROW[wires.AnElt.MA];
dumby: DumbWire ~ CreateBareDumbWire[act];
losers: Set ~ wires.Difference[Sets.CreateSingleA[anDw, a.dumrep.dwSpace]];
StartDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
[] _ dumby.eps.AddSet[dw.eps];
IF dw.children#nilBiRel THEN ERROR;
IF dw.parent#NIL THEN ERROR;
RETURN [FALSE]};
FixExport: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
IF dw#anDw THEN a.dumrep.apToWire.SubstituteA[dw, anDw, right];
RETURN [FALSE]};
IF wires.Scan[StartDumb].found THEN ERROR;
{givenCai: Set ~ dumby.eps.SetOn[right];
splort: BOOL ~ givenCai.NonTrivial;
allCai: Set ~ IF splort THEN Sets.IIAsSet[[0, a.size-1]] ELSE Sets.CreateSingleton[givenCai.TheElt, SetBasics.ints];
allEp: Set ~ a.dumrep.epw.Image[wires, rightToLeft].CreateHashCopy[];
allEps: BiRel ~ BiRels.CreateProduct[[allEp, allCai]];
missedEps: BiRel ~ allEps.Difference[dumby.eps];
IF missedEps.NonEmpty THEN {
missedEp: Set ~ missedEps.SetOn[left].CreateHashCopy[];
theirWires: Set ~ a.dumrep.epw.Image[missedEp];
ourLosses: Set ~ wires.Intersection[theirWires].CreateHashCopy[];
[] _ balks.AddSet[ourLosses];
[] _ wires.RemSet[ourLosses];
IF wires.Trivial THEN RETURN ELSE LOOP};
IF wires.Scan[FixExport].found THEN ERROR;
{edges: Set ~ a.statrep.portEdge[FALSE].Image[allEp] .Union[a.statrep.portEdge[TRUE].Image[allEp]] .CreateHashCopy[];
theCai: CompositeArrayIndex ~ givenCai.AnElt.MI;
theAi: Int2 ~ DecomposeAI[a, theCai];
thePhase: Int2 ~ Mod[theAi, a.basePeriod];
anEp: Port ~ NARROW[anDw.eps.SetOn[left].AnElt.MA];
epSofar: Set ~ Sets.CreateHashSet[d.eSpace];
caiSofar: Set _ Sets.CreateSingleI[theCai, SetBasics.ints];
epsSofar: BiRel _ BiRels.CreateProduct[[epSofar, caiSofar]];
splable: BOOL _ splort;
FinishDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
missedEps: Set ~ dw.eps.SetOn[left].Difference[epSofar];
DO
missedEp: Port ~ NARROW[missedEps.AnElt.MDA];
IF missedEp#NIL THEN {
IF splort THEN FOR fx: NAT IN [0 .. a.basePeriod[X]) DO FOR fy: NAT IN [0 .. a.basePeriod[X]) DO
AddEdge[[vs: [[anEp, [fx, fy]], [missedEp, [fx, fy]]], d: ALL[0]]];
ENDLOOP ENDLOOP
ELSE AddEdge[[vs: [[anEp, thePhase], [missedEp, thePhase]], d: ALL[0]]];
IF NOT epSofar.AddA[missedEp] THEN ERROR;
LOOP};
IF NOT splable THEN EXIT;
{missedCaiMv: Sets.MaybeValue ~ dw.eps.SetOn[right].Difference[caiSofar].AnElt;
IF NOT missedCaiMv.found THEN EXIT;
{missedAi: Int2 ~ DecomposeAI[a, missedCaiMv.it.VI];
mep: Port ~ NARROW[dw.eps.Mapping[missedCaiMv.it, rightToLeft].AnElt.MA];
doDim: ARRAY Dim2 OF BOOL ~ [a.size2[X]>1, a.size2[Y]>1];
FOR dim: Dim2 IN Dim2 DO
IF doDim[dim] THEN FOR fx: NAT IN [0 .. a.basePeriod[X]) DO FOR fy: NAT IN [0 .. a.basePeriod[X]) DO
delta: Int2 ~ ConsInt2[dim, 1, 0];
f: Int2 ~ [fx, fy];
IF a.size2[dim]>f[dim]+1 THEN AddEdge[[vs: [[mep, f], [mep, AddMod[f, delta, a.basePeriod]]], d: delta]];
ENDLOOP ENDLOOP;
ENDLOOP;
splable _ FALSE;
caiSofar _ allCai;
}}ENDLOOP;
RETURN [FALSE]};
FinishEP: PROC [epv: Sets.Value] RETURNS [BOOL] ~ {
ep: Port ~ NARROW[epv.VA];
dws: Fn--composite array index _ DumbWire-- ~ LichenArrayPrivate.GetDumbWires[a, ep, FALSE]^;
[] _ dws.AddSet[BiRels.CreateProduct[[allCai, Sets.CreateSingleA[anDw, a.dumrep.dwSpace]]]];
RETURN [FALSE]};
IF NOT epSofar.AddA[anEp] THEN ERROR;
IF wires.Scan[FinishDumb].found THEN ERROR;
IF allEp.Scan[FinishEP].found THEN ERROR;
[] _ anDw.eps.AddSet[allEps];
IF NOT a.dumrep.wires.RemSet[losers].had.all THEN ERROR;
TrimStatrep[act, a, edges];
RETURN}};
ENDLOOP;
};

END.
bLichenDataImplArrays3.Mesa
Last tweaked by Mike Spreitzer on August 15, 1988 4:23:11 pm PDT
Κ
E–

"cedar" style˜
code™Kš
œ@™@—K˜KšΟk	œ(œ[˜Ž
K˜šΟnœœ
˜$KšœœT˜{Kšœ˜K˜
—K˜Kšœ
œ
œžœ	œœ9˜vK˜šžœœ
œΟcœœœ
œœ˜}K˜šžœœœœ˜4Kšœœœ˜ K˜Kšœ
Ÿœ)˜DKšœ œ)œ˜bšž	œœœœ˜4Kšœœœ˜š	œœ
œ
œ
˜Kš
œ˜šœœ˜ šœœœ
œŸnœ
œ˜«
Kšœ	œ»
˜Ζ
Kšœœ˜——Kšœ
˜—Kšœœ˜—Kš
œ˜Kš
œœ
œ
œœ˜!Kš
œ˜Kšœ.œ˜5Kš
œ
œœ
œ
Ÿœ
˜,Kšœ
œœ
œIœ
œ4˜¬
Kšœ-œ˜7Kšœ	œ˜—Kš
œ
œœ
œ
Ÿœ
˜8Kšœœ˜;Kšœ˜—K˜šžœœ
œ0œœ
œœ˜jKš
œ˜šžœœœœ˜4Kšœœœ˜ Kš
œ˜Kšœ œ'œ ˜pKš
œ˜Kšœœ
œ
˜*Kšœ,œ˜2Kš
œ
œœ
œ
Ÿœ
˜6K˜ šžœœœœ˜1Kšœœœ˜Kšœœœœ˜7šžœœœœ˜2Kšœœœ˜Kšœ
œœ
œ
˜%šœœ˜Kšœ%œ˜:Kšœ
œ#œ
œ
˜4Kšœ
œœ
œ
˜*KšŸ%œ˜'—Kšœœ˜—Kš
œœ
œ'œ
œ
˜@Kšœœ˜—Kšœ#ŸMœ
˜qKšœœ˜7Kšœœ˜6Kšœœ˜5Kšœœ˜4šœœ˜%Kšœœ
œ
˜%Kš
œ'˜'—šœ
œœ˜Kšœ
œœ
œ
˜&Kš
œœ
œDœ
œ;˜–
Kšœœœ˜+Kš
œ˜—Kšœœ˜—Kšœœ˜<Kšœ˜—K˜šžœœ
œ&Ÿœ˜SKš
œ˜šžœœœœ˜4Kšœœœ˜ Kš
œ˜Kšœœœ˜,šžœœœœ˜2Kšœœœ˜Kšœœœ˜-šžœœœœ˜0Kšœœœ˜K˜&Kšœœ˜—šœœ
œ˜Kšœœ
œœ˜4Kš
œ?˜?Kšœœ
œ
˜*Kšœ&œ
œ
˜3Kšœ
œ"œ
œ˜5—Kšœœ˜—š
žœœœœŸœ˜OKšœœœ˜š	œœ
œ
œ
˜Kš
œ˜šœœ˜Kš
œ+˜+Kšœ9œ˜C—Kšœ
˜—Kšœœ˜—šž	œœœœ˜6K˜%šœœ˜ Kš
œe˜eKšœœ
œ˜,—Kšœœ˜—Kšœ œ(œ!˜rKšœœ
œ
˜*Kšœœ
œ
˜(Kšœœ
œ
˜(Kšœ)œ
œ
˜6Kš
œ˜Kšœœ˜—Kšœœ˜<Kšœ˜—K˜šžœœ$œœ˜_K˜*K˜+K˜*K˜2šžœœœœ˜8K˜%šœœ˜Kšœœœ˜!Kšœœœ˜7Kšœ
œ*œ˜BKšœœ
œ6˜Fšœ
œ	œ˜Kšœ(œ˜DKšœœœ
˜Kš
œ˜Kšœœœ
œ
˜%Kšœ œ˜=—K˜—Kšœœ˜—Kšœœ
œ
˜*Kšœ+œ
œ
˜8K˜1Kš
œ'˜'Kšœ˜—K˜Kš
œ:˜:K˜šžœœ
œ(œ˜`Kš
œ˜Kš
œ-˜-Kšœœ
œ
˜š
˜šžœœ˜%Kšœ'œœœ˜;Kšœ˜—Kšœœ
œ˜(Kš
œ*˜*K˜Kšž	œœœœ˜4Kšœœœ˜Kš
œ˜Kšœœ
œ
˜#Kšœœ
œ
œ
˜Kšœœ˜—šž	œœœœ˜4Kšœœœ˜Kšœ	œ0˜?Kšœœ˜—Kšœœ
œ
˜*Kš
œ(˜(Kšœœ˜#Kšœœœœ7˜tKš
œE˜EKš
œ6˜6Kš
œ0˜0šœœ˜Kš
œ7˜7Kš
œ/˜/Kš
œA˜AKš
œ˜Kš
œ˜Kš
œœ
œ
œ
œ˜(—Kšœœ
œ
˜*Kšœ!œ)œ"˜uKšœ-œ
˜0Kš
œ%˜%K˜*Kšœ
œœ˜3K˜,K˜;K˜<Kšœ	œ
˜šž
œœœœ˜5Kšœœœ˜K˜8š
˜Kšœœœ˜-šœ
œ
œ˜šœœ
œ
Οg
Οd
œœ
œœ
œ
 
‘
œœ
œ˜`Kšœ 
‘
œ 
‘
œ 
‘
œ 
‘
œ 
œœ˜CKšœ
˜—Kšœ8 
œœ˜HKšœ
œœ
œ
˜)Kšœ˜—Kšœ
œ	œ
œ
˜K˜OKšœ
œœ
œ
˜#Kšœ0œ˜4Kšœœ3œ˜IKšœœœ
œ ˜9šœœ˜šœœ
œ
 
‘
œœ
œœ
œ
 
‘
œœ
œ˜dK˜"Kš 
œ
 
‘
œ 
‘
œ˜Kšœ 
œœ 
œ 
œ 
œ
˜iKšœ
œ
˜—Kšœ
˜—Kšœ
œ
˜Kš
œ˜Kšœœ
˜
—Kšœœ˜—šžœœœœ˜3Kšœœœ˜KšœŸΠcm
Ÿœ*œ˜]Kš
œ\˜\Kšœœ˜—Kšœ
œœ
œ
˜%Kšœœ
œ
˜+Kšœœ
œ
˜)K˜Kšœ
œ'œ
œ
˜8Kš
œ˜Kšœ˜	Kšœ
˜—Kš
œ˜—K˜Kšœ
˜—…—*J7ρ