LichenArrayImpl.Mesa
Last tweaked by Mike Spreitzer on August 28, 1987 11:44:43 am PDT
DIRECTORY Basics, Convert, GList, InterpreterOps, IntHashTable, IO, LichenArrayStuff, LichenCollections, LichenDataOps, LichenDataStructure, LichenPairCollections, RefTab, Rope;
LichenArrayImpl:
CEDAR
PROGRAM
IMPORTS Basics, GList, IntHashTable, LichenArrayStuff, LichenCollections, LichenDataOps, LichenDataStructure, LichenPairCollections, RefTab
EXPORTS LichenArrayStuff, LichenDataStructure
=
BEGIN OPEN LichenDataStructure, LichenArrayStuff, LichenDataOps, Sets:LichenCollections, Fns:LichenPairCollections;
Quit: ERROR = CODE;
PackedArrayIndex: PUBLIC TYPE = INT;
PackArrayIndex:
PUBLIC
PROC [ai: ArrayIndex]
RETURNS [PackedArrayIndex]
= {RETURN [PackArrayIndexI[ai]]};
PackArrayIndexI:
PROC [ai: ArrayIndex]
RETURNS [PackedArrayIndex]
= INLINE {RETURN [LOOPHOLE[Nat2[ai[Foo], ai[Bar]]]]};
UnpackArrayIndex:
PUBLIC
PROC [pai: PackedArrayIndex]
RETURNS [ArrayIndex]
= {RETURN [UnpackArrayIndexI[pai]]};
UnpackArrayIndexI:
PROC [pai: PackedArrayIndex]
RETURNS [ArrayIndex]
= INLINE {RETURN [[LOOPHOLE[pai, Nat2][Foo], LOOPHOLE[pai, Nat2][Bar]]]};
Central:
PUBLIC
PROC [a: Array, ai: ArrayIndex]
RETURNS [
BOOL] = {
RETURN [
ai[Foo] > 0 AND ai[Foo]+1 < a.size[Foo] AND
ai[Bar] > 0 AND ai[Bar]+1 < a.size[Bar]];
};
ComputeGroupingsIndex:
PUBLIC
PROC [a: Array, ai: ArrayIndex]
RETURNS [gi2, gii2: Nat2, gi, cgii:
NAT] = {
ngii: Nat2 ← [1, 1];
Gi1D:
PROC [d: Dim] = {
i: INT = ai[d];
SELECT
TRUE
FROM
i < a.groupingParmses[d].middle.min => gi2[d] ← i;
i >= a.groupingParmses[d].middle.maxPlusOne => gi2[d] ← i + a.groupingParmses[d].d;
ENDCASE => {
t: NAT = a.jointsPeriod[d];
f: NAT = i MOD t;
jiir: Range = Range1Div[a.groupingParmses[d].middle, t, f];
gi2[d] ← a.groupingParmses[d].middle.min + f;
gii2[d] ← i/a.jointsPeriod[d] - jiir.min;
ngii[d] ← RangeLength[jiir];
}};
gii2 ← [0, 0];
Gi1D[Foo]; Gi1D[Bar];
gi ← a.groupingParmses[Bar].sum * gi2[Foo] + gi2[Bar];
cgii ← ngii[Bar] * gii2[Foo] + gii2[Bar]};
ComputeJointGroupingsIndex:
PUBLIC
PROC [a: Array, j: Joint, jii: Nat2]
RETURNS [jgi2: Nat2, jgi, ctii:
NAT, jiir: Range2] = {
njgii: Nat2 ← [1, 1];
jgii2: Nat2 ← [0, 0];
Gi1D:
PROC [d: Dim] = {
i: NAT = jii[d];
jiir[d] ← [min: i, maxPlusOne: i+1];
SELECT
TRUE
FROM
i < j.groupingParmses[d].middle.min => jgi2[d] ← i;
i >= j.groupingParmses[d].middle.maxPlusOne => jgi2[d] ← i + j.groupingParmses[d].d;
ENDCASE => {
jgi2[d] ← j.groupingParmses[d].middle.min;
jiir[d] ← j.groupingParmses[d].middle;
jgii2[d] ← i - jgi2[d];
njgii[d] ← RangeLength[jiir[d]];
}};
Gi1D[Foo]; Gi1D[Bar];
jgi ← j.groupingParmses[Bar].sum * jgi2[Foo] + jgi2[Bar];
ctii ← njgii[Bar] * jgii2[Foo] + jgii2[Bar]};
AddTiedGroups:
PROC [d: Dim, j: Joint, side: End, jgi:
NAT, g: Group, to: GroupList]
RETURNS [tied: GroupList] = {
IF g = NIL THEN RETURN [to];
IF FetchTie[j, side, jgi, g] # NIL THEN RETURN [CONS[g, to]];
IF g.stopLooking[d][side] THEN RETURN [to];
tied ← to;
FOR worse: GroupList ← g.worse, worse.rest
WHILE worse #
NIL
DO
tied ← AddTiedGroups[d, j, side, jgi, worse.first, tied];
ENDLOOP;
tied ← tied;
};
AddListTiedGroups:
PROC [d: Dim, j: Joint, side: End, jgi:
NAT, gs, to: GroupList]
RETURNS [tied: GroupList] = {
tied ← NIL;
FOR gs ← gs, gs.rest
WHILE gs #
NIL
DO
tied ← AddTiedGroups[d, j, side, jgi, gs.first, tied];
ENDLOOP;
tied ← tied;
};
ArrayWireForGroup:
PUBLIC
PROC [a: Array, index: ArrayIndex, gi:
NAT, g: Group, mayAdd:
BOOL]
RETURNS [aw: ArrayWire] ~ {
pai: PackedArrayIndex ~ PackArrayIndexI[index];
last: IntTable --PackedArrayIndex b ArrayWire-- ~ NARROW[a.toWire.Fetch[g].val];
IF g.ports=NIL THEN ERROR;
IF last #
NIL
THEN {
aw ← NARROW[last.Fetch[pai].value];
IF aw # NIL THEN RETURN;
};
IF NOT mayAdd THEN RETURN [NIL];
aw ←
NEW [ArrayWirePrivate ← [
members: Fns.CreateHashFn[],
ports: Sets.CreateHashSet[]
]];
IF NOT a.wires.AddElt[aw] THEN ERROR;
AddEltToArrayWire[a, aw, [g, index]];
};
SetGroupInWireAt:
PROC [a: Array, gi2: Nat2, g: Group, aw: ArrayWire, ai: ArrayIndex]
RETURNS [news:
BOOL] ~ {
air: Range2 ~ Gi2ToAir[a, gi2].air;
shape: Nat2 ~ RangeShape[air];
gii: Nat2 ~ Nat2Div[Int2SubN[ai, Range2Min[air]], a.jointsPeriod];
index: NAT ~ shape[Bar] * gii[Foo] + gii[Bar];
bs: BoolSeq ←
WITH aw.members.Apply[g].val
SELECT
FROM
x: BoolSeq => x,
x: Sets.NoValue => NARROW[aw.members.Inserted[[g, CreateBoolSeq[Nat2Area[shape]]]]],
ENDCASE => ERROR;
IF g.ports=NIL THEN ERROR;
IF bs = NIL AND NOT aw.members.Store[[g, bs ← CreateBoolSeq[Nat2Area[shape]]]].new THEN ERROR;
IF bs[index] THEN RETURN [FALSE];
{
last: IntTable --PackedArrayIndex b ArrayWire-- ← NARROW[a.toWire.Fetch[g].val];
pai: PackedArrayIndex ~ PackArrayIndexI[ai];
IF last = NIL AND NOT a.toWire.Insert[g, last ← CreateIntTable[]] THEN ERROR;
[] ← last.Store[pai, aw];
news ← bs[index] ← TRUE;
}};
AddEltToArrayWire:
PROC [a: Array, aw: ArrayWire, elt: ArrayWireElt] = {
NoteConnection:
PROC [ai
n: ArrayIndex, g
n: Group] ~ {
IF gn.ports#
NIL
THEN {
gi2n: Nat2 ~ ComputeGroupingsIndex[a, ain].gi2;
IF SetGroupInWireAt[a, gi2n, gn, aw, ain].news THEN stack ← CONS[[gn, ain], stack];
};
};
stack: LIST OF ArrayWireElt ← NIL;
NoteConnection[elt.ai, elt.g];
WHILE stack #
NIL
DO
elt: ArrayWireElt ~ stack.first;
gi: NAT ~ ComputeGroupingsIndex[a, elt.ai].gi;
stack ← stack.rest;
EnumerateLocalConnections[a, elt.ai, gi, elt.g, NoteConnection];
stack ← stack;
ENDLOOP;
stack ← stack;
};
JoinArrayWires:
PROC [a: Array, aw1, aw2: ArrayWire] ~ {
MoveElt:
PROC [pair: Fns.Pair] ~ {
g: Group ~ NARROW[pair[left]];
bs: BoolSeq ~ NARROW[pair[right]];
air: Range2 ~ Gi2ToAir[a, g.gi2].air;
shape: Nat2 ~ RangeShape[air];
FOR ai
f:
NAT ← air[Foo].min, ai
f+a.jointsPeriod[Foo]
WHILE ai
f < air[Foo].maxPlusOne
DO
FOR ai
b:
NAT ← air[Bar].min, ai
b+a.jointsPeriod[Bar]
WHILE ai
b < air[Bar].maxPlusOne
DO
ai: ArrayIndex ~ [aif, aib];
gii: Nat2 ~ Nat2Div[Int2SubN[ai, Range2Min[air]], a.jointsPeriod];
index: NAT ~ shape[Bar] * gii[Foo] + gii[Bar];
IF bs[index]
THEN {
AddEltToArrayWire[a, aw1, [g, ai]];
Quit;
};
ENDLOOP ENDLOOP;
};
MovePort:
PROC [ra:
REF
ANY] ~ {
ap: Port ~ NARROW[ra];
IF NOT aw1.ports.AddElt[ap] THEN ERROR;
IF NOT a.portWire.Replace[ap, aw1] THEN ERROR;
};
aw2.members.Enumerate[MoveElt !Quit => CONTINUE];
aw2.ports.Enumerate[MovePort];
IF NOT a.wires.RemoveElt[aw2] THEN ERROR;
};
EnumerateLocalConnections:
PROC [a: Array, index: ArrayIndex, gi:
NAT, g: Group,
Consume:
PROC [ai
n: ArrayIndex, g
n: Group]] = {
FOR d: Dim
IN Dim
DO
FOR side: End
IN End
DO
otherSide: End = OtherEnd[side];
lai: ArrayIndex = Int2Tweak[index, d, SELECT side FROM low => 0, high => -1, ENDCASE => ERROR];
hai: ArrayIndex = Int2Tweak[lai, d, 1];
IF lai[d] < 0 OR hai[d] >= a.size[d] THEN LOOP;
{jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
tie: Tie = FetchTie[j, side, jgi, g];
IF tie = NIL THEN LOOP;
IF tie.groups[side] # g THEN ERROR;
IF tie.groups[otherSide] # NIL THEN Consume[SELECT side FROM low => hai, high => lai, ENDCASE => ERROR, tie.groups[otherSide]];
}ENDLOOP ENDLOOP;
a ← a;
};
EnumerateArrays:
PUBLIC
PROC [cellType: CellType,
Consume:
PROC [CellType]] = {
FOR act: CellType ← cellType.firstArray, act.asArray.nextArray
WHILE act #
NIL
DO
Consume[act];
ENDLOOP;
};
Jgi2ToGi:
PUBLIC
PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, side: End]
RETURNS [gi2: Nat2, gi:
NAT] = {
Do1:
PROC [d: Dim]
RETURNS [ji:
NAT] = {
SELECT
TRUE
FROM
jgi2[d] < j.groupingParmses[d].middle.min => RETURN [jgi2[d]];
jgi2[d] >= j.groupingParmses[d].firstHigh => RETURN [jgi2[d]-j.groupingParmses[d].d];
ENDCASE => RETURN [j.groupingParmses[d].middle.min];
};
ji2: Int2 = [Foo: Do1[Foo], Bar: Do1[Bar]];
lai: ArrayIndex = [
Foo: phase[Foo] + a.jointsPeriod[Foo] * ji2[Foo],
Bar: phase[Bar] + a.jointsPeriod[Bar] * ji2[Bar]];
[gi2: gi2, gi: gi] ← ComputeGroupingsIndex[a, IF side = low THEN lai ELSE Int2Tweak[lai, d, 1]];
};
Jgi2ToGip:
PUBLIC
PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2]
RETURNS [gip: GIPair] = {
gip ← [
low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
};
AgiToAi:
PUBLIC
PROC [a: Array, gi2, gii2: Nat2]
RETURNS [ai: ArrayIndex] = {
Do:
PROC [d: Dim]
RETURNS [
INT] = {
SELECT
TRUE
FROM
gi2[d] < a.groupingParmses[d].middle.min => RETURN [gi2[d]];
gi2[d] >= a.groupingParmses[d].firstHigh => RETURN [gi2[d] - a.groupingParmses[d].d];
ENDCASE => {
t: NAT = a.jointsPeriod[d];
f: NAT = gi2[d] - a.groupingParmses[d].middle.min;
min: NAT = CeilDiv[MAX[a.groupingParmses[d].middle.min, f] - f, t];
RETURN [(gii2[d] + min) * t + f];
};
};
ai[Foo] ← Do[Foo];
ai[Bar] ← Do[Bar];
};
JGRListize:
PROC [a: Array, d: Dim, phase: Nat2, j: Joint, lowRange: Range2]
RETURNS [jgrl: JGRList] = {
jiir: Range2 = Range2Div[lowRange, a.jointsPeriod, phase];
Enum:
PROC [d
e: Dim,
Per:
PROC [
NAT,
NAT,
NAT,
NAT,
NAT,
INT,
INT, Range, Range]] = {
D: INT = IF de = d THEN 1 ELSE 0;
fh: NAT = ((phase[de]+D) MOD a.jointsPeriod[de]);
giml: NAT = a.groupingParmses[de].middle.min + phase[de];
gimh: NAT = a.groupingParmses[de].middle.min + fh;
jir
m:
ARRAY End
OF Range = [
low: Range1Div[a.groupingParmses[de].middle, a.jointsPeriod[de], phase[de]],
high: Range1Div[RangeOffClip[a.groupingParmses[de].middle, -D], a.jointsPeriod[de], phase[de]]];
nm: ARRAY End OF NAT = [low: RangeLength[jirm[low]], high: RangeLength[jirm[high]]];
gijl: NAT ← jiir[de].min;
gial: NAT ← gijl * a.jointsPeriod[de] + phase[de];
ji: NAT ← jiir[de].maxPlusOne-1;
ai: NAT ← ji * a.jointsPeriod[de] + phase[de] + D;
giah: INT ← ai + a.groupingParmses[de].d;
gijh: INT ← ji + j.groupingParmses[de].d;
lowLimit: NAT = MIN[j.groupingParmses[de].middle.min, jiir[de].maxPlusOne];
highLimit: NAT = MAX[j.groupingParmses[de].middle.maxPlusOne, jiir[de].min];
FOR gi
j
l ← gi
j
l, gi
j
l+1
WHILE gi
j
l < lowLimit
DO
this: Range = [min: gijl, maxPlusOne: gijl+1];
nh: NAT ← 1;
giah: INT ← gial + D;
IF
D=1
AND gi
a
l=a.groupingParmses[d
e].middle.min-1
THEN {giah ← gimh; nh ← nm[high]};
Per[gial, giah, gijl, 1, nh, gijl, gijl, this, this];
gial ← gial + a.jointsPeriod[de];
ENDLOOP;
FOR ji ← ji, ji-1
WHILE ji >= highLimit
DO
this: Range = [min: ji, maxPlusOne: ji + 1];
nl: NAT ← 1;
jii0al: INT ← ji;
gial: INT ← giah - D;
IF
D=1
AND gi
a
h=a.groupingParmses[d
e].firstHigh
THEN {gial ← giml; nl ← nm[low]; jii0al ← jirm[low].min};
Per[gial, giah, gijh, nl, 1, jii0al, ji, this, this];
giah ← giah - a.jointsPeriod[de];
gijh ← gijh - 1;
ENDLOOP;
IF RangesIntersect[jiir[de], j.groupingParmses[d
e].middle]
THEN {
mjir: Range = [
min: MAX[j.groupingParmses[de].middle.min, jiir[de].min],
maxPlusOne: MIN[j.groupingParmses[de].middle.maxPlusOne, jiir[de].maxPlusOne]];
Per[
giml,
gimh,
j.groupingParmses[de].middle.min,
nm[low],
nm[high],
jirm[low].min,
jirm[high].min,
mjir,
j.groupingParmses[de].middle
];
};
};
PerFoo:
PROC [gi
al
f, gi
ah
f, gi
j
f, ngii
l
f, ngii
h
f:
NAT, jii0
al
f, jii0
ah
f:
INT, jir
f, fullJiir
f: Range] = {
cf: BOOL = jirf = fullJiirf;
PerBar:
PROC [gi
al
b, gi
ah
b, gi
j
b, ngii
l
b, ngii
h
b:
NAT, jii0
al
b, jii0
ah
b:
INT, jir
b, fullJiir
b: Range] = {
cb: BOOL = jirb = fullJiirb;
jgrl ←
CONS[
[
gis: [
low: a.groupingParmses[Bar].sum * gialf + gialb,
high: a.groupingParmses[Bar].sum * giahf + giahb],
ngii: [low: [ngiilf, ngiilb], high: [ngiihf, ngiihb]],
firstJIIOfGI: [low: [jii0alf, jii0alb], high: [jii0ahf, jii0ahb]],
jgi2: [Foo: gijf, Bar: gijb],
jgi: j.groupingParmses[Bar].sum * gijf + gijb,
jiir: [Foo: jirf, Bar: jirb],
fullJiir: [Foo: fullJiirf, Bar: fullJiirb],
complete: cf AND cb
],
jgrl];
};
Enum[Bar, PerBar];
};
jgrl ← NIL;
Enum[Foo, PerFoo];
jgrl ← jgrl;
};
JGRList: TYPE = LIST OF READONLY JGR;
JGR:
TYPE =
RECORD [
gis: ARRAY End OF NAT,
ngii: ARRAY End OF ARRAY Dim OF NAT,
firstJIIOfGI: ARRAY End OF Int2,
jgi2: Nat2,
jgi: NAT,
jiir, fullJiir: Range2,
complete: BOOL
];
ngii[side] is the number of instances of gis[side] in the entire array.
firstJIIOfGI[side] is the jii of the first joint in the entire array that has gis[side] on side; note that this may include imaginary joints along the low sides of the array.
MakeArrayConnection:
PUBLIC
PROC [ct: CellType, d: Dim, lowRange: Range2, rp1, rp2: SidedPort, may:
BOOL]
RETURNS [connected:
BOOL] = {
o: Dim = OtherDim[d];
a: Array = ct.asArray;
tf: NAT = a.jointsPeriod[Foo];
tb: NAT = a.jointsPeriod[Bar];
IF a = NIL THEN ERROR;
IF lowRange[d].min<0 OR lowRange[d].maxPlusOne>=a.size[d] THEN ERROR;
IF lowRange[o].min<0 OR lowRange[o].maxPlusOne>a.size[o] THEN ERROR;
IF a.jointsPeriod[d] > a.size[d] THEN ERROR;
FOR
f
f:
NAT
IN [0 ..
t
f)
DO
FOR
f
b:
NAT
IN [0 ..
t
b)
DO
phase2: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase2];
jgrl: JGRList ← JGRListize[a, d, phase2, j, lowRange];
FOR jgrl ← jgrl, jgrl.rest
WHILE jgrl #
NIL
DO
jgr: JGR = jgrl.first;
njgiib: NAT = RangeLength[jgr.fullJiir[Bar]];
g1: Group = GetGroup[a, jgr.gis[rp1.side], rp1.port, may];
g2: Group = GetGroup[a, jgr.gis[rp2.side], rp2.port, may];
tie: Tie;
rpd1, rpd2: SidedPortData;
IF g1 = NIL OR g2 = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
[tie, rpd1, rpd2] ← GetTieAndRPD[a, d, phase2, j, jgr.jgi2, jgr.jgi, jgr.fullJiir, rp1, rp2, g1, g2, jgr.gis[rp1.side], jgr.gis[rp2.side], may];
IF tie = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
IF may
AND tie.completion #
NIL
THEN {
FOR jii
f:
INT
IN [jgr.jiir[Foo].min .. jgr.jiir[Foo].maxPlusOne)
DO
FOR jii
b:
INT
IN [jgr.jiir[Bar].min .. jgr.jiir[Bar].maxPlusOne)
DO
lai: ArrayIndex = [
Foo: jiif*a.jointsPeriod[Foo] + ff,
Bar: jiib*a.jointsPeriod[Bar] + fb];
giis:
ARRAY End
OF
NAT = [
low: jgr.ngii[low][Bar] * (jiif - jgr.firstJIIOfGI[low][Foo]) + jiib - jgr.firstJIIOfGI[low][Bar],
high: jgr.ngii[high][Bar] * (jiif - jgr.firstJIIOfGI[high][Foo]) + jiib - jgr.firstJIIOfGI[high][Bar]];
ctii: NAT = njgiib * (jiif - jgr.fullJiir[Foo].min) + jiib - jgr.fullJiir[Bar].min;
Merge[a, d, lai, j, jgr.jgi, tie, rpd1, rpd2, ctii];
tie ← BestTie[tie];
IF tie.completion = NIL THEN GOTO Completed;
ENDLOOP ENDLOOP;
EXITS Completed => tie ← tie;
};
ENDLOOP;
ENDLOOP ENDLOOP;
connected ← TRUE;
IF NOT may THEN RETURN;
FOR f:
NAT
IN [
NAT[lowRange[Foo].min] ..
NAT[lowRange[Foo].maxPlusOne])
DO
FOR b:
NAT
IN [
NAT[lowRange[Bar].min] ..
NAT[lowRange[Bar].maxPlusOne])
DO
ais: ARRAY End OF ArrayIndex = [[f, b], Int2Tweak[[f, b], d, 1]];
gis: ARRAY End OF NAT = [ComputeGroupingsIndex[a, ais[low]].gi, ComputeGroupingsIndex[a, ais[high]].gi];
g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
aw1: ArrayWire = ArrayWireForGroup[a, ais[rp1.side], gis[rp1.side], g1, FALSE];
aw2: ArrayWire = ArrayWireForGroup[a, ais[rp2.side], gis[rp2.side], g2, FALSE];
IF aw1 = aw2 THEN NULL
ELSE IF aw2 = NIL THEN AddEltToArrayWire[a, aw1, [g2, ais[rp2.side]]]
ELSE IF aw1 = NIL THEN AddEltToArrayWire[a, aw2, [g1, ais[rp1.side]]]
ELSE JoinArrayWires[a, aw1, aw2];
ENDLOOP ENDLOOP;
};
MakeGroupsForPort:
PUBLIC
PROC [a: Array, ep: Port] ~ {
a ← a;
FOR gi:
NATURAL
IN [0 .. a.groupingses.length)
DO
[] ← GetGroup[a, gi, ep, TRUE];
ENDLOOP;
a ← a;
};
GetGroup:
PUBLIC
PROC [a: Array, gi:
NAT, ep: Port, mayAdd:
BOOL]
RETURNS [g: Group] ~ {
gs: Groupings ~ NARROW[a.groupingses[gi]];
g ← NARROW[gs.toGroup.Fetch[ep].val];
IF g =
NIL
AND mayAdd
THEN {
gi2: Nat2 ~ GiToGi2[a, gi];
g ← MakeGroup[a, gi2, gs];
AddPortToGroup[a, gi, ep, g, TRUE];
IF gs.toGroup.Fetch[ep].val # g THEN ERROR};
};
MakeGroup:
PUBLIC
PROC [a: Array, gi2: Nat2, gs: Groupings]
RETURNS [g: Group] = {
g ← NEW [GroupPrivate ← [gi2: gi2]];
IF NOT gs.groups.AddElt[g] THEN ERROR;
g ← g};
AddPortToGroup:
PUBLIC
PROC [a: Array, gi:
NATURAL, ep: Port, g: Group, links:
BOOL] ~ {
gs: Groupings ~ NARROW[a.groupingses[gi]];
IF g.better#NIL OR g.worse#NIL THEN ERROR;
g.ports ← CONS[ep, g.ports];
IF NOT gs.toGroup.Insert[ep, g] THEN ERROR;
FOR d: Dim
IN Dim
DO
FOR side: End
IN End
DO
EnsureRPD[a, d, [side: side, port: ep], links];
ENDLOOP;
ENDLOOP;
g ← g};
RemovePortFromGroup:
PUBLIC
PROC [a: Array, gi:
NATURAL, ep: Port, g: Group] ~ {
gs: Groupings ~ NARROW[a.groupingses[gi]];
IF g.better#NIL OR g.worse#NIL THEN ERROR;
IF gs.toGroup.Fetch[ep].val # g THEN ERROR;
g.ports ← NARROW[GList.DRemove[ep, g.ports]];
IF NOT gs.toGroup.Delete[ep] THEN ERROR;
g ← g};
UnrolePort:
PUBLIC
PROC [a: Array, ep: Port] ~ {
FOR d: Dim
IN Dim
DO
FOR s: End
IN End
DO
spd: SidedPortData ~ NARROW[a.toRole[d][s].Fetch[ep].val];
IF a.roles[d].refs[spd.index] # spd THEN ERROR;
IF spd.index+1 = a.nextRP[d]
THEN {
a.nextRP[d] ← a.nextRP[d]-1;
a.roles[d].length ← a.roles[d].length-1};
a.roles[d].refs[spd.index] ← NIL;
IF NOT a.toRole[d][s].Delete[ep] THEN ERROR;
ENDLOOP ENDLOOP;
a ← a;
};
EnsureRPD:
PROC [a: Array, d: Dim, rp: SidedPort, links:
BOOL] = {
rpd: SidedPortData ← FetchRPD[a, d, rp];
IF rpd =
NIL
THEN {
rpd ←
NEW [SidedPortDataPrivate ← [
port: rp.port,
side: rp.side,
index: a.nextRP[d],
links: NIL
]];
IF a.roles[d].length # rpd.index THEN ERROR;
VarRefSeqAppend[a.roles[d], rpd];
a.nextRP[d] ← a.nextRP[d] + 1;
IF NOT a.toRole[d][rp.side].Store[rp.port, rpd] THEN ERROR;
IF links THEN AddLinks[a, d, rpd];
};
rpd ← rpd};
GetTieAndRPD:
PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi:
NAT, jiir: Range2, rp1, rp2: SidedPort, g1, g2: Group, gi1, gi2:
NAT, may:
BOOL]
RETURNS [tie: Tie, rpd1, rpd2: SidedPortData] = {
tie1: Tie = GetTie[a, d, phase, j, rp1.side, jgi2, jgi, jiir, g1, gi1, may];
tie2: Tie = GetTie[a, d, phase, j, rp2.side, jgi2, jgi, jiir, g2, gi2, may];
tie ←
SELECT
TRUE
FROM
tie1 = tie2 => tie1,
NOT may => NIL,
ENDCASE => JoinTies[a, d, phase, j, jgi2, jgi, jiir, LIST[tie1, tie2], TRUE];
IF may
AND tie.completion #
NIL
THEN {
rpd1 ← FetchRPD[a, d, rp1];
rpd2 ← FetchRPD[a, d, rp2];
};
};
GetTie:
PROC [a: Array, d: Dim, phase: Nat2, j: Joint, side: End, jgi2: Nat2, jgi:
NAT, jiir: Range2, g: Group, gi:
NAT, may:
BOOL]
RETURNS [tie: Tie] = {
tie ← FetchTie[j, side, jgi, g];
IF tie =
NIL
AND may
THEN {
cn: Completion ← NIL;
IF g.ports #
NIL
AND g.ports.rest #
NIL
THEN {
ntii: NAT = RangeArea[jiir];
tii, ni: NAT ← 0;
D: Nat2 ← [0, 0];
cn ← NEW [CompletionPrivate[ntii]];
IF side = high THEN D[d] ← 1;
FOR jii
f:
INT
IN [jiir[Foo].min .. jiir[Foo].maxPlusOne)
DO
FOR jii
b:
INT
IN [jiir[Bar].min .. jiir[Bar].maxPlusOne)
DO
lai: ArrayIndex = [jiif*a.jointsPeriod[Foo]+phase[Foo], jiib*a.jointsPeriod[Bar]+phase[Bar]];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF NOT (cn[tii] ← ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side]) THEN ni ← ni + 1;
ENDLOOP ENDLOOP;
cn.nIncomplete ← ni;
IF ni = 0 THEN cn ← NIL;
};
tie ←
NEW [TiePrivate ← [
groups: ALL[NIL],
completion: cn
]];
tie.groups[side] ← g;
g.stopLooking[d][side] ← TRUE;
AddTie[j, jgi, tie];
};
};
JoinTies:
PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi:
NAT, jiir: Range2, ties: TieList, mayJoinGroups:
BOOL]
RETURNS [tie: Tie] = {
ntii: NAT = RangeArea[jiir];
groups: ARRAY End OF Group ← ALL[NIL];
urTies: TieList = ties;
doomeds: TieList ← NIL;
gi2s: ARRAY End OF Nat2;
gis: ARRAY End OF NAT;
hPhase: Nat2 ← phase;
hPhase[d] ← (phase[d] + 1) MOD a.jointsPeriod[d];
FOR ts: TieList ← ties, ts.rest
WHILE ts #
NIL
DO
tie: Tie = ts.first;
IF tie.better # NIL THEN ERROR;
IF GList.Member[tie, ts.rest] THEN ERROR;
ENDLOOP;
FOR side: End
IN End
DO
olds: GroupList ← NIL;
[gi2s[side], gis[side]] ← Jgi2ToGi[a, d, phase, j, jgi2, side];
FOR ts: TieList ← ties, ts.rest
WHILE ts #
NIL
DO
g: Group = BestGroup[ts.first.groups[side]];
IF g # NIL AND NOT GList.Member[g, olds] THEN olds ← CONS[g, olds];
ENDLOOP;
groups[side] ← IF olds # NIL THEN IF olds.rest = NIL THEN olds.first ELSE IF mayJoinGroups THEN JoinGroups[a, phase, gi2s[side], olds, NARROW[a.groupingses[gis[side]]]] ELSE ERROR ELSE NIL;
ENDLOOP;
FOR side: End
IN End
DO
best: Group = groups[side] ← BestGroup[groups[side]];
FOR worses: GroupList ← AddTiedGroups[d, j, side, jgi, best,
NIL], worses.rest
WHILE worses #
NIL
DO
worse: Group = worses.first;
tie: Tie = FetchTie[j, side, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF NOT GList.Member[tie, doomeds] THEN doomeds ← CONS[tie, doomeds];
ENDLOOP;
ENDLOOP;
FOR ts: TieList ← urTies, ts.rest
WHILE ts #
NIL
DO
IF NOT GList.Member[ts.first, doomeds] THEN ERROR;
ENDLOOP;
tie ← NEW [TiePrivate ← [groups: groups]];
FOR ts: TieList ← doomeds, ts.rest
WHILE ts #
NIL
DO
doomed: Tie = ts.first;
Incompletify[a, d, doomed, ntii];
doomed.better ← tie;
ENDLOOP;
FinishIncompletion[a, d, phase, tie, ntii];
FOR ts: TieList ← doomeds, ts.rest
WHILE ts #
NIL
DO
doomed: Tie = ts.first;
DeleteTie[j, jgi, doomed];
ENDLOOP;
AddTie[j, jgi, tie];
FOR side
g: End
IN End
DO
--make sure all ties for group on this side are joined
gPhase: Nat2 = IF sideg = low THEN phase ELSE hPhase;
g: Group = groups[sideg];
IF g #
NIL
THEN {
FOR d
e: Dim
IN Dim
DO
FOR side
e: End
IN End
DO
Consume:
PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi:
NAT, j: Joint] = {
oldTies: TieList ← NIL;
FOR ws: GroupList ← AddTiedGroups[d
e, j, side
e, jgi, g,
NIL], ws.rest
WHILE ws #
NIL
DO
worse: Group = ws.first;
tie: Tie = FetchTie[j, sidee, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF NOT GList.Member[tie, oldTies] THEN oldTies ← CONS[tie, oldTies];
ENDLOOP;
IF oldTies #
NIL
AND (oldTies.rest #
NIL
OR oldTies.first.groups[side
e] # g)
THEN {
jiir: Range2 = Jgi2ToLair[a, gPhase, j, jgi2].jiir;
newTie: Tie = JoinTies[a, de, gPhase, j, jgi2, jgi, jiir, oldTies, FALSE];
IF newTie.groups[sidee] # g THEN ERROR;
oldTies ← oldTies;
};
oldTies ← oldTies;
};
EnumerateJointsForGi[a, de, sidee, gPhase, gi2s[sideg], Consume];
g.stopLooking[de][sidee] ← TRUE;
ENDLOOP;
ENDLOOP;
IF g.stopLooking = ALL[ALL[TRUE]] THEN KillWorse[g];
};
ENDLOOP;
tie ← tie;
};
KillWorse:
PROC [g: Group] = {
FOR ws: GroupList ← g.worse, ws.rest
WHILE ws #
NIL
DO
KillWorse[ws.first];
ENDLOOP;
g.worse ← NIL;
};
JoinGroups:
PROC [a: Array, phase: Nat2, gi2: Nat2, groups: GroupList, gs: Groupings]
RETURNS [g: Group] = {
bests: GroupList ← NIL;
ports: PortList ← NIL;
FOR raws: GroupList ← groups, raws.rest
WHILE raws #
NIL
DO
IF raws.first = NIL THEN LOOP;
IF raws.first.ports = NIL THEN ERROR;
{best: Group = BestGroup[raws.first];
IF
NOT GList.Member[best, bests]
THEN {
bests ← CONS[best, bests];
ports ← NARROW[GList.Append[best.ports, ports]];
};
}ENDLOOP;
IF bests = NIL THEN ERROR;
IF bests.rest = NIL THEN RETURN [bests.first];
g ← NEW [GroupPrivate ← [ports: ports, worse: bests, gi2: gi2]];
FOR pl: PortList ← g.ports, pl.rest
WHILE pl #
NIL
DO
IF NOT gs.toGroup.Replace[pl.first, g] THEN ERROR;
ENDLOOP;
IF NOT gs.groups.AddElt[g] THEN ERROR;
FOR worse: GroupList ← bests, worse.rest
WHILE worse #
NIL
DO
IF NOT gs.groups.RemoveElt[worse.first] THEN ERROR;
worse.first.better ← g;
ENDLOOP;
FOR d: Dim
IN Dim
DO
FOR side: End
IN End
DO
Consume:
PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi:
NAT, j: Joint] = {
otherSide: End = OtherEnd[side];
otherGs: Groupings = NARROW[a.groupingses[otherGi]];
otherSideGroups: GroupList ← NIL;
FOR ws: GroupList ← AddListTiedGroups[d, j, side, jgi, bests,
NIL], ws.rest
WHILE ws #
NIL
DO
worse: Group = ws.first;
tie: Tie = FetchTie[j, side, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF tie.groups[otherSide] # NIL THEN otherSideGroups ← CONS[tie.groups[otherSide], otherSideGroups];
ENDLOOP;
IF otherSideGroups # NIL AND otherSideGroups.rest # NIL THEN [] ← JoinGroups[a, otherPhase, otherGi2, otherSideGroups, otherGs];
};
EnumerateJointsForGi[a, d, side, phase, gi2, Consume];
ENDLOOP;
ENDLOOP;
g ← g;
};
EnumerateJointsForGi:
PROC [a: Array, d: Dim, side: End, phase, gi2: Nat2,
Consume:
PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi:
NAT, j: Joint]] = {
lowPhase, highPhase: Nat2 ← phase;
IF side = high
THEN {
lowPhase[d] ← (phase[d] + a.jointsPeriod[d] - 1) MOD a.jointsPeriod[d];
}
ELSE {
highPhase[d] ← (phase[d] + 1) MOD a.jointsPeriod[d];
};
{j: Joint = GetArrayJoint[a, d, lowPhase];
otherPhase: Nat2 = IF side = low THEN highPhase ELSE lowPhase;
otherGi2, jgi2: Nat2 ← [LAST[NAT], LAST[NAT]];
Do1:
PROC [d
e: Dim,
Consume1:
PROC] = {
SELECT
TRUE
FROM
d
e # d => {
otherGi2[de] ← gi2[de];
SELECT
TRUE
FROM
gi2[de] < a.groupingParmses[de].middle.min => jgi2[de] ← gi2[de] / a.jointsPeriod[de];
gi2[d
e] >= a.groupingParmses[d
e].firstHigh => {
lai: NAT = gi2[de] - a.groupingParmses[de].d;
jii: NAT = lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d};
ENDCASE => jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
side = low =>
SELECT
TRUE
FROM
gi2[d
e] < a.groupingParmses[d
e].middle.min =>
IF gi2[d
e]+1 < a.groupingParmses[d
e].sum
THEN {
jgi2[de] ← gi2[de] / a.jointsPeriod[de];
IF gi2[de]+1 < a.groupingParmses[de].middle.min THEN otherGi2[de] ← gi2[de]+1
ELSE IF HasMiddle[a.groupingParmses[de]] THEN otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de]
ELSE otherGi2[de] ← a.groupingParmses[de].middle.maxPlusOne;
Consume1[];
};
gi2[d
e] >= a.groupingParmses[d
e].firstHigh =>
IF gi2[d
e]+1 < a.groupingParmses[d
e].sum
THEN {
lai: NAT = gi2[de] - a.groupingParmses[de].d;
jii: NAT = lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d;
otherGi2[de] ← gi2[de] + 1;
Consume1[];
};
ENDCASE => {
IF HasMiddle[j.groupingParmses[d
e]]
THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
IF highPhase[d
e] = (a.groupingParmses[d
e].middle.maxPlusOne
MOD a.jointsPeriod[d
e])
AND a.groupingParmses[d
e].firstHigh < a.groupingParmses[d
e].sum
THEN {
jgi2[de] ← j.groupingParmses[de].firstHigh;
otherGi2[de] ← a.groupingParmses[de].firstHigh;
Consume1[];
};
};
side = high =>
SELECT
TRUE
FROM
gi2[d
e] < a.groupingParmses[d
e].middle.min =>
IF gi2[d
e] > 0
THEN {
otherGi2[de] ← gi2[de] - 1;
jgi2[de] ← otherGi2[de] / a.jointsPeriod[de];
Consume1[];
};
gi2[d
e] >= a.groupingParmses[d
e].firstHigh =>
IF gi2[d
e] > 0
THEN {
lai, jii: NAT;
IF gi2[d
e] > a.groupingParmses[d
e].firstHigh
THEN {
otherGi2[de] ← gi2[de]-1;
lai ← otherGi2[de] - a.groupingParmses[de].d;
jii ← lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d;
}
ELSE
IF HasMiddle[a.groupingParmses[d
e]]
THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].firstHigh;
}
ELSE {
otherGi2[de] ← a.groupingParmses[de].middle.min-1;
jgi2[de] ← j.groupingParmses[de].firstHigh;
};
Consume1[];
};
ENDCASE => {
IF HasMiddle[j.groupingParmses[d
e]]
THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
IF highPhase[d
e] = (a.groupingParmses[d
e].middle.min
MOD a.jointsPeriod[d
e])
AND a.groupingParmses[d
e].middle.min > 0
THEN {
jgi2[de] ← j.groupingParmses[de].middle.min-1;
otherGi2[de] ← a.groupingParmses[de].middle.min-1;
Consume1[];
};
};
ENDCASE => ERROR;
};
PerFoo: PROC = {Do1[Bar, PerBoth]};
PerBoth:
PROC = {
Consume[otherPhase, otherGi2, jgi2, a.groupingParmses[Bar].sum*otherGi2[Foo] + otherGi2[Bar], j.groupingParmses[Bar].sum*jgi2[Foo] + jgi2[Bar], j];
};
Do1[Foo, PerFoo];
}};
AddTie:
PUBLIC
PROC [j: Joint, jgi:
NAT, tie: Tie] = {
ties: Set--of Tie-- = Sets.DeRef[j.ties[jgi]];
IF NOT ties.AddElt[tie] THEN ERROR;
FOR side: End
IN End
DO
last: RefTable--Group b Tie-- = NARROW[j.toTie[side][jgi]];
g: Group = tie.groups[side];
IF g #
NIL
THEN {
IF NOT last.Insert[g, tie] THEN ERROR;
};
ENDLOOP;
};
DeleteGroup:
PUBLIC
PROC [a: Array, g: Group] ~ {
gs: Groupings ~ NARROW[a.groupingses[ComposeGI[a, g.gi2]]];
Untie:
PROC [d: Dim, phase: Nat2, jgi:
NATURAL, jgi2: Nat2, j: Joint, tie: Tie, side: End] ~ {
IF tie.completion#NIL OR tie.groups[side]#g THEN ERROR;
IF FetchTie[j, side, jgi, g] # tie THEN ERROR;
tie.groups[side] ← NIL;
IF tie.groups = ALL[NIL] THEN DeleteTie[j, jgi, tie];
};
places: IntTable ~ NARROW[a.toWire.Fetch[g].val];
IF places #
NIL
THEN {
Unwire:
PROC [key: PackedArrayIndex, value:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE]
--IntHashTable.EachPairAction-- ~ {
aw: ArrayWire ~ NARROW[value];
[] ← aw.members.Store[[g, NIL]];
};
IF places.Pairs[Unwire] THEN ERROR;
IF NOT a.toWire.Delete[g] THEN ERROR;
};
EnumerateTiesOfGroup[a, g.gi2, g, Untie];
FOR ports: PortList ← g.ports, ports.rest
WHILE ports #
NIL
DO
IF gs.toGroup.Fetch[ports.first].val # g THEN ERROR;
IF NOT gs.toGroup.Delete[ports.first] THEN ERROR;
ENDLOOP;
IF NOT gs.groups.RemoveElt[g] THEN ERROR;
};
DeleteTie:
PUBLIC
PROC [j: Joint, jgi:
NAT, tie: Tie] = {
ties: Set--of Tie-- = Sets.DeRef[j.ties[jgi]];
IF NOT ties.RemoveElt[tie] THEN ERROR;
FOR side: End
IN End
DO
last: RefTable--Group b Tie-- = NARROW[j.toTie[side][jgi]];
IF tie.groups[side] # NIL AND NOT last.Delete[tie.groups[side]] THEN ERROR;
ENDLOOP;
};
PortPair: TYPE = ARRAY [1 .. 2] OF Port;
MergeStack: TYPE = LIST OF MergeStackFrame;
MergeStackFrame:
TYPE =
RECORD [
lai: ArrayIndex,
d: Dim,
side: End,
pair: PortPair];
Merge:
PROC [a: Array, d: Dim, lai: ArrayIndex, j: Joint, jgi:
NAT, tie: Tie, rpd1, rpd2: SidedPortData, ctii:
NAT] = {
stack: MergeStack ← NIL;
Consider:
PROC [ai: ArrayIndex, d: Dim, eltSide: End, pair: PortPair] = {
jointSide: End = OtherEnd[eltSide];
o: Dim = OtherDim[d];
lai: ArrayIndex = IF eltSide = high THEN ai ELSE Int2Tweak[ai, d, -1];
IF lai[d]
IN [0 .. a.size[d]-1)
AND lai[o]
IN [0 .. a.size[o])
THEN {
stack ← CONS[[lai, d, jointSide, pair], stack];
};
};
DO
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
clai: INT = jSize[Bar] * lai[Foo] + lai[Bar];
r1: NAT = GetRoot[a, d, rpd1, clai];
r2: NAT = GetRoot[a, d, rpd2, clai];
IF r1 # r2
THEN {
o: Dim = OtherDim[d];
hai: Int2 = Int2Tweak[lai, d, 1];
IF tie.completion[ctii] THEN ERROR;
FOR side: End
IN End
DO
g: Group = tie.groups[side];
ai: ArrayIndex = IF side = low THEN lai ELSE hai;
pair: PortPair ← ALL[NIL];
otherSide: End = OtherEnd[side];
IF rpd1.side = side AND rpd2.side = side THEN pair ← [rpd1.port, rpd2.port]
ELSE {
IF g #
NIL
THEN
FOR pl: PortList ← g.ports, pl.rest
WHILE pl #
NIL
DO
rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
r: NAT = GetRoot[a, d, rpd, clai];
i: INT = SELECT r FROM r1 => 1, r2 => 2, ENDCASE => 3;
IF i
IN [1 .. 2]
AND pair[i] =
NIL
THEN {
pair[i] ← pl.first;
IF pair[3-i] # NIL THEN EXIT};
ENDLOOP;
};
IF pair[1] #
NIL
AND pair[2] #
NIL
THEN {
Consider[ai, d, side, pair];
Consider[ai, o, side, pair];
Consider[ai, o, otherSide, pair];
};
ENDLOOP;
IF r1 < r2 THEN SetNext[a, d, r2, clai, r1] ELSE SetNext[a, d, r1, clai, r2];
IF tie.completion[ctii] ← ComputeTieCompleteAt[a, d, tie, clai]
THEN {
IF (tie.completion.nIncomplete ← tie.completion.nIncomplete - 1) = 0 THEN CompletifyTie[a, d, tie];
};
};
DO
IF stack = NIL THEN GOTO Dun;
{msf: MergeStackFrame = stack.first;
stack ← stack.rest;
d ← msf.d;
lai ← msf.lai;
{ai: ArrayIndex = IF msf.side = low THEN lai ELSE Int2Tweak[lai, d, 1];
gi: NAT = ComputeGroupingsIndex[a, ai].gi;
jii: Nat2 = [
Foo: lai[Foo] / a.jointsPeriod[Foo],
Bar: lai[Bar] / a.jointsPeriod[Bar]];
phase: Nat2 = [
Foo: lai[Foo] - jii[Foo] * a.jointsPeriod[Foo],
Bar: lai[Bar] - jii[Bar] * a.jointsPeriod[Bar]];
rp1: SidedPort = [msf.side, msf.pair[1]];
rp2: SidedPort = [msf.side, msf.pair[2]];
g1: Group = GetGroup[a, gi, rp1.port, TRUE];
g2: Group = GetGroup[a, gi, rp2.port, TRUE];
jgi2: Nat2;
jiir: Range2;
j ← GetArrayJoint[a, d, phase];
[jgi2, jgi, ctii, jiir] ← ComputeJointGroupingsIndex[a, j, jii];
[tie, rpd1, rpd2] ← GetTieAndRPD[a, d, phase, j, jgi2, jgi, jiir, rp1, rp2, g1, g2, gi, gi, TRUE];
IF tie.completion # NIL THEN EXIT;
}}ENDLOOP;
ENDLOOP;
};
Incompletify:
PROC [a: Array, d: Dim, tie: Tie, ntii:
NAT] = {
IF tie.completion # NIL THEN RETURN;
tie.completion ← NEW [CompletionPrivate[ntii]];
tie.completion.nIncomplete ← 0;
FOR tii:
NAT
IN [0 .. tie.completion.length)
DO
tie.completion[tii] ← TRUE;
ENDLOOP;
tie ← tie;
};
CompletifyTie:
PROC [a: Array, d: Dim, tie: Tie] = {
IF tie.completion = NIL THEN ERROR;
tie.completion ← NIL;
};
FinishIncompletion:
PROC [a: Array, d: Dim, phase: Nat2, tie: Tie, ntii:
NAT] = {
IF tie.completion # NIL THEN ERROR;
tie.completion ← NEW [CompletionPrivate[ntii]];
tie.completion.nIncomplete ← ntii;
FOR ctii: NAT IN [0 .. ntii) DO tie.completion[ctii] ← FALSE ENDLOOP;
};
AddLinks:
PROC [a: Array, d: Dim, rpd: SidedPortData] = {
IF rpd.links # NIL THEN ERROR;
IF rpd.index = 0 THEN RETURN;
{
linksNeeded: NAT = Nat2Area[Nat2Tweak[a.size, d, -1]];
linkSize, wordsNeeded: NAT;
lgLinksPerWord: Sublg;
[linkSize, lgLinksPerWord] ← ChooseLinkSize[rpd.index];
wordsNeeded ← CeilDiv[linkSize * linksNeeded, Basics.bitsPerWord];
rpd.links ← NEW [LinksPrivate[wordsNeeded]];
rpd.links.linkSize ← linkSize;
rpd.links.negLinkSize ← - linkSize;
rpd.links.negLgLinksPerWord ← - lgLinksPerWord;
rpd.links.lgLinksPerWord ← lgLinksPerWord;
FOR clai:
NAT
IN [0 .. linksNeeded)
DO
SetNext[a, d, rpd.index, clai, rpd.index];
ENDLOOP;
rpd ← rpd;
}};
ChooseLinkSize:
PROC [index:
NAT]
RETURNS [linkSize:
NAT, lgLinksPerWord: Sublg] = {
SELECT index
FROM
<1 => ERROR;
<2 => RETURN [1, Basics.logBitsPerWord];
<4 => RETURN [2, Basics.logBitsPerWord-1];
<16 => RETURN [4, Basics.logBitsPerWord-2];
<256 => RETURN [8, Basics.logBitsPerWord-3];
<=32767 => RETURN [16, Basics.logBitsPerWord-4];
ENDCASE => ERROR;
};
RPDNeedsLinks:
PUBLIC
PROC [a: Array, d: Dim, rpd: SidedPortData]
RETURNS [needs:
BOOL] = {
phase: NAT ← 0;
needs ← FALSE;
FOR
f
f:
INT
IN [0 .. a.jointsPeriod[Foo])
DO
FOR
f
b:
INT
IN [0 .. a.jointsPeriod[Bar])
DO
j: Joint = NARROW[a.joints[d][phase]];
jgi: NAT ← 0;
FOR jgi
f:
NAT
IN [0 .. j.groupingParmses[Foo].sum)
DO
FOR jgi
b:
NAT
IN [0 .. j.groupingParmses[Bar].sum)
DO
gi: NAT = Jgi2ToGi[a, d, [ff, fb], j, [jgif, jgib], rpd.side].gi;
gs: Groupings = NARROW[a.groupingses[gi]];
g: Group = NARROW[gs.toGroup.Fetch[rpd.port].val];
IF g #
NIL
THEN {
tie: Tie = FetchTie[j, rpd.side, jgi, g];
IF tie # NIL AND tie.completion # NIL THEN RETURN [TRUE];
};
jgi ← jgi + 1;
ENDLOOP;
ENDLOOP;
phase ← phase + 1;
ENDLOOP ENDLOOP;
needs ← needs;
};
GroupCompleteAt:
PROC [a: Array, gi:
NAT, g: Group, ai: ArrayIndex]
RETURNS [complete:
BOOL] = {
complete ← FALSE;
FOR d: Dim
IN Dim
DO
Try:
PROC [side: End, lai: ArrayIndex]
RETURNS [determined:
BOOL] = {
jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
tie: Tie = FetchTie[j, side, jgi, g];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF tie = NIL THEN RETURN [FALSE];
complete ← tie.completion = NIL OR ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side];
determined ← TRUE;
};
IF
(ai[d] < a.size[d]-1 AND Try[low, ai]) OR
(ai[d] > 0 AND Try[high, Int2Tweak[ai, d, -1]])
THEN EXIT;
ENDLOOP;
RETURN;
};
ComputeGroupCompleteAt:
PROC [a: Array, g: Group, clai:
NAT, d: Dim, side: End
--of joint--]
RETURNS [complete:
BOOL] = {
root: NAT;
first: BOOL ← TRUE;
someNIL, someNonNIL: BOOL ← FALSE;
complete ← TRUE;
{
FOR pl: PortList ← g.ports, pl.rest
WHILE pl #
NIL
DO
rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
r2: NAT;
IF rpd.index = 0 THEN r2 ← 0
ELSE IF rpd.links = NIL THEN {r2 ← LAST[NAT]; someNIL ← TRUE}
ELSE {r2 ← GetRoot[a, d, rpd, clai]; someNonNIL ← TRUE};
IF first
THEN {root ← r2; first ← FALSE}
ELSE IF r2 # root THEN GOTO Fail;
ENDLOOP;
EXITS Fail => complete ← FALSE};
IF someNIL AND someNonNIL THEN ERROR;
};
ComputeTieCompleteAt:
PUBLIC
PROC [a: Array, d: Dim, tie: Tie, clai:
NAT]
RETURNS [complete:
BOOL] = {
root: NAT;
first: BOOL ← TRUE;
someNIL, someNonNIL: BOOL ← FALSE;
complete ← TRUE;
{
FOR side: End
IN End
DO
g: Group = tie.groups[side];
IF g #
NIL
THEN
FOR pl: PortList ← g.ports, pl.rest
WHILE pl #
NIL
DO
rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
r2: NAT;
IF rpd.index = 0 THEN r2 ← 0
ELSE IF rpd.links = NIL THEN {r2 ← LAST[NAT]; someNIL ← TRUE}
ELSE {r2 ← GetRoot[a, d, rpd, clai]; someNonNIL ← TRUE};
IF first
THEN {root ← r2; first ← FALSE}
ELSE IF r2 # root THEN GOTO Fail;
ENDLOOP;
ENDLOOP;
EXITS Fail => complete ← FALSE};
IF someNIL AND someNonNIL THEN ERROR;
};
WordPtr: TYPE = LONG POINTER TO WORD;
GetNext:
PUBLIC
PROC [rp: SidedPortData, clai:
NAT]
RETURNS [next:
NAT] =
TRUSTED {
IF rp.index = 0 THEN RETURN [rp.index];
{ls: Links = rp.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
mask: WORD = last[ls.linkSize];
next ← Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
}};
ArrayEltPortsConnectedByJoint:
PUBLIC
PROC [a: Array, d: Dim, lowIndex: ArrayIndex, rp1, rp2: SidedPort]
RETURNS [hypothetically, really:
BOOL] = {
o: Dim = OtherDim[d];
IF NOT (lowIndex[d] IN [0 .. a.size[d]-1) AND lowIndex[o] IN [0 .. a.size[o])) THEN RETURN [FALSE, FALSE];
{phase: Nat2 = [
Foo: lowIndex[Foo] MOD a.jointsPeriod[Foo],
Bar: lowIndex[Bar] MOD a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jii: Nat2 = [
Foo: lowIndex[Foo] / a.jointsPeriod[Foo],
Bar: lowIndex[Bar] / a.jointsPeriod[Bar]];
jgi2: Nat2;
jgi, ctii: NAT;
jiir: Range2;
[jgi2, jgi, ctii, jiir] ← ComputeJointGroupingsIndex[a, j, jii];
{gis:
ARRAY End
OF
NAT = [
low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE, FALSE];
{tie1: Tie = FetchTie[j, rp1.side, jgi, g1];
tie2: Tie = FetchTie[j, rp2.side, jgi, g2];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF tie1 # tie2 OR tie1 = NIL THEN RETURN [FALSE, FALSE]
ELSE IF tie1.completion = NIL THEN RETURN [TRUE, TRUE]
ELSE {
rpd1: SidedPortData = FetchRPD[a, d, rp1];
rpd2: SidedPortData = FetchRPD[a, d, rp2];
clai: INT = jSize[Bar] * lowIndex[Foo] + lowIndex[Bar];
really ← GetRoot[a, d, rpd1, clai] = GetRoot[a, d, rpd2, clai];
hypothetically ← TRUE;
};
}}}};
ArrayEltPortsConnected:
PUBLIC
PROC [a: Array, ai1, ai2: ArrayIndex, ep1, ep2: Port]
RETURNS [hypothetically:
BOOL] = {
gi1: NAT = ComputeGroupingsIndex[a, ai1].gi;
gi2: NAT = ComputeGroupingsIndex[a, ai2].gi;
g1: Group = GetGroup[a, gi1, ep1, FALSE];
g2: Group = GetGroup[a, gi2, ep2, FALSE];
IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE];
{aw1: ArrayWire = ArrayWireForGroup[a, ai1, gi1, g1, TRUE];
aw2: ArrayWire = ArrayWireForGroup[a, ai2, gi2, g2, TRUE];
RETURN [aw1 = aw2];
}};
GroupsHypotheticallyConnected:
PUBLIC
PROC [a: Array, j: Joint, jgi:
NAT, gs:
ARRAY End
OF Group]
RETURNS [
BOOL] = {
Get:
PROC [side: End]
RETURNS [tie: Tie] = {
rt: RefTable = NARROW[j.toTie[side][jgi]];
tie ← NARROW[rt.Fetch[gs[side]].val]};
RETURN [Get[low] = Get[high]];
};
GetRoot:
PUBLIC
PROC [a: Array, d: Dim, rp: SidedPortData, clai:
NAT]
RETURNS [root:
NAT] =
TRUSTED {
IF rp.index = 0 THEN RETURN [rp.index];
{ls: Links = rp.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
mask: WORD = last[ls.linkSize];
next: NAT = Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
IF next = rp.index THEN RETURN [rp.index];
{rp2: SidedPortData = NARROW[a.roles[d].refs[next]];
IF next # rp2.index THEN ERROR;
root ← GetRoot[a, d, rp2, clai];
IF root # next
THEN {
leftShift: INTEGER = - rightShift;
shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[mask, leftShift]];
shiftedRoot: WORD = Basics.BITSHIFT[root, leftShift];
word: WORD = Basics.BITOR[shiftedRoot, Basics.BITAND[shiftedMask, wordPtr^]];
wordPtr^ ← word;
};
}}};
SetNext:
PROC [a: Array, d: Dim, index, clai, next:
NAT] =
TRUSTED {
IF index = 0 THEN ERROR;
{rpd: SidedPortData = NARROW[a.roles[d].refs[index]];
ls: Links = rpd.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
leftShift: INTEGER = ls.linkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[last[ls.linkSize], leftShift]];
shiftedNext: WORD = Basics.BITSHIFT[next, leftShift];
word: WORD = Basics.BITOR[shiftedNext, Basics.BITAND[shiftedMask, wordPtr^]];
IF Basics.BITAND[shiftedNext, shiftedMask] # 0 THEN ERROR;
wordPtr^ ← word;
}};
last:
ARRAY [0 .. Basics.bitsPerWord]
OF
WORD = [
00000H,
00001H, 00003H, 00007H, 0000FH,
0001FH, 0003FH, 0007FH, 000FFH,
001FFH, 003FFH, 007FFH, 00FFFH,
01FFFH, 03FFFH, 07FFFH, 0FFFFH];
EnsurePortForGroups:
PUBLIC
PROC [act: CellType, gis, giis:
ARRAY End
OF Nat2, gss: GroupListPair]
RETURNS [ap: Port] = {
a: Array = act.asArray;
ais: ARRAY End OF ArrayIndex = [AgiToAi[a, gis[low], giis[low]], AgiToAi[a, gis[high], giis[high]]];
Enumerate:
PROC [
Consume:
PROC [ai: ArrayIndex, ep: Port]
RETURNS [stop:
BOOL ←
FALSE]]
RETURNS [aborted:
BOOL] = {
FOR side: End
IN End
DO
FOR gs: GroupList ← gss[side], gs.rest
WHILE gs #
NIL
DO
g: Group = gs.first;
FOR ps: PortList ← g.ports, ps.rest
WHILE ps #
NIL
DO
IF Consume[ais[side], ps.first] THEN RETURN [TRUE];
ENDLOOP;
ENDLOOP;
ENDLOOP;
aborted ← FALSE;
};
Search:
PROC [ai: ArrayIndex, ep: Port]
RETURNS [stop:
BOOL ←
FALSE] = {
stop ← (NOT Central[a, ai]) AND (ap ← GetArrayPortForPort[act, a, ai, ep, FALSE]) # NIL;
};
Export:
PROC [ai: ArrayIndex, ep: Port]
RETURNS [stop:
BOOL ←
FALSE] = {
IF NOT Central[a, ai] THEN SetArrayPortForPort[a, ai, ep, ap];
};
IF Enumerate[Search] THEN RETURN;
IF act.port = NIL THEN ERROR --is it true that a cell type always has a port?--;
ap ← FullyAddPort[[parent: act.port]].port;
IF Enumerate[Export] THEN ERROR;
};
CrossATie:
PUBLIC
PROC [ct: CellType, d: Dim, fromP: Port, fromS: End]
RETURNS [toP: Port] = {
toS: End = OtherEnd[fromS];
a: Array = ct.asArray;
tf: INT = a.jointsPeriod[Foo];
tb: INT = a.jointsPeriod[Bar];
candidates: PortList ← NIL;
first: BOOL ← TRUE;
FOR
f
f:
INT
IN [0 ..
t
f)
DO
FOR
f
b:
INT
IN [0 ..
t
b)
DO
phase: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase];
FOR jgi
f:
NAT
IN [0 .. j.groupingParmses[Foo].sum)
DO
FOR jgi
b:
NAT
IN [0 .. j.groupingParmses[Bar].sum)
DO
jgi2: Nat2 = [jgif, jgib];
jgi: NAT = j.groupingParmses[Bar].sum * jgif + jgib;
gif: NAT = Jgi2ToGi[a, d, phase, j, jgi2, fromS].gi;
gf: Group = GetGroup[a, gif, fromP, FALSE];
IF gf = NIL THEN RETURN [NIL];
{tie: Tie = FetchTie[j, fromS, jgi, gf];
IF tie = NIL THEN RETURN [NIL];
{gt: Group = tie.groups[toS];
IF gt = NIL THEN NULL
ELSE IF first THEN {first ← FALSE; candidates ← gt.ports}
ELSE candidates ← NARROW[GList.Intersection[candidates, gt.ports]];
IF candidates = NIL THEN RETURN [NIL];
}}ENDLOOP ENDLOOP;
ENDLOOP ENDLOOP;
toP ← IF candidates # NIL THEN candidates.first ELSE NIL;
};
Range1Mul:
PUBLIC
PROC [r: Range,
t,
f:
NAT]
RETURNS [rr: Range] = {
rr ← [
min: r.min*t + f,
maxPlusOne: r.maxPlusOne*t + f];
};
Range2Mul:
PUBLIC
PROC [r: Range2,
t,
f: Nat2]
RETURNS [rr: Range2] = {
rr ← [
Foo: [
min: r[Foo].min*t[Foo] + f[Foo],
maxPlusOne: r[Foo].maxPlusOne*t[Foo] + f[Foo]],
Bar: [
min: r[Bar].min*t[Bar] + f[Bar],
maxPlusOne: r[Bar].maxPlusOne*t[Bar] + f[Bar]]];
};
Range1Div:
PUBLIC
PROC [r: Range,
t,
f:
NAT]
RETURNS [rr: Range] = {
rr ← [
min: CeilDiv[r.min-f, t],
maxPlusOne: FloorDiv[r.maxPlusOne-1-f, t] + 1];
};
Range2Div:
PUBLIC
PROC [r: Range2,
t,
f: Nat2]
RETURNS [rr: Range2] = {
rr ← [
Foo: [
min: CeilDiv[r[Foo].min-f[Foo], t[Foo]],
maxPlusOne: FloorDiv[r[Foo].maxPlusOne-1-f[Foo], t[Foo]] + 1],
Bar: [
min: CeilDiv[r[Bar].min-f[Bar], t[Bar]],
maxPlusOne: FloorDiv[r[Bar].maxPlusOne-1-f[Bar], t[Bar]] + 1]];
};
END.