LichenDataStructure.Mesa
Mike Spreitzer November 13, 1986 9:02:21 pm PST
DIRECTORY Asserting, Basics, HashTable, IntHashTable, LichenSetTheory, Rope;
LichenDataStructure: CEDAR DEFINITIONS
IMPORTS HashTable, IntHashTable =
BEGIN OPEN LichenSetTheory;
nyet: ERROR --not yet implemented--;
Warning: SIGNAL [msg: ROPE, v1, v2, v3, v4, v5: REF ANYNIL];
Error: ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANYNIL];
LORA: TYPE = LIST OF REF ANY;
LOLORA: TYPE = LIST OF LORA;
ROPE: TYPE = Rope.ROPE;
RopeList: TYPE = LIST OF ROPE;
Assertions: TYPE = Asserting.Assertions;
RefTable: TYPE = HashTable.Table;
CreateRefTable: PROC RETURNS [rt: RefTable]
= INLINE {rt ← HashTable.Create[]};
IntTable: TYPE = IntHashTable.Table;
CreateIntTable: PROC RETURNS [it: IntTable]
= INLINE {it ← IntHashTable.Create[]};
GraphID: TYPE = {A, B, Unspecified};
RealGraphID: TYPE = GraphID[A .. B];
OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A];
graphIDToRope: ARRAY GraphID OF ROPE;
Color: TYPE = INT;
noColor: Color = LAST[Color];
someColor: Color = 871;
FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE {
filtered ← IF color # noColor THEN color ELSE someColor};
Design: TYPE = REF DesignPrivate;
DesignPrivate: TYPE = RECORD [
cellTypes: Set,
other: Assertions ← NIL,
allKnown: BOOLFALSE];
nameReln: ATOM; --relative to narrowest enclosing scope
Describe: PROC [subject: REF ANY, relativeTo: REF ANYNIL, nameGen: NameGenerator ← NIL] RETURNS [ROPE];
NameGenerator: TYPE = REF NameGeneratorPrivate;
NameGeneratorPrivate: TYPE = RECORD [
GenerateName: PROC [data, subject: REF ANY] RETURNS [ROPE],
data: REF ANYNIL
];
EnumerateCellTypes: PROC [design: Design, Consume: PROC [CellType]];
CellClass: TYPE = REF CellClassPrivate;
CellClassPrivate: TYPE = RECORD [
DefinePrivates: PROC [CellType]
];
CellType: TYPE = REF CellTypePrivate;
CellTypePrivate: TYPE = RECORD [
class: CellClass,
designs: Set,
publicKnown, privateKnown: BOOLFALSE,
wasntNormalized: BOOLFALSE,
Leftover
port: Port ← NIL,
asUnorganized: Unorganized ← NIL,
asArray: Array ← NIL,
firstInstance, lastInstance: CellInstance ← NIL,
firstArray, lastArray: CellType ← NIL,
useCount: INT ← 0 --#instances + #arrays--,
otherPublic, otherPrivate: Assertions ← NIL,
color: Color ← noColor];
EnumeratePorts: PROC [cellType: CellType, Consume: PROC [Port]];
EnumerateInstances: PROC [cellType: CellType, Consume: PROC [CellInstance]];
EnumerateArrays: PROC [cellType: CellType, Consume: PROC [CellType]];
partsByNameKey: ATOM;
private CellType b Mapper(ROPE b Vertex)
PortList: TYPE = LIST OF Port;
Port: TYPE = REF PortPrivate;
PortPrivate: TYPE = RECORD [
next, prev: Port,
firstChild, lastChild: Port,
parent: REF ANY--UNION [Port, CellType]--,
wire: Wire ← NIL,
other: Assertions ← NIL,
color: Color ← noColor];
PortCCT: PROC [port: Port] RETURNS [containingCT: CellType];
FirstChildPort: PROC [port: Port] RETURNS [child: Port]
= INLINE {child ← port.firstChild};
NextChildPort: PROC [child: Port] RETURNS [sibling: Port]
= INLINE {sibling ← child.next};
PortIndex: PROC [parent, child: Port] RETURNS [index: INT];
SubPort: PROC [parent: Port, index: INT] RETURNS [child: Port];
Unorganized: TYPE = REF UnorganizedPrivate;
UnorganizedPrivate: TYPE = RECORD [
internalWire: Wire ← NIL,
containedInstances: Set--of CellInstance--NIL,
mirror: CellInstance ← NIL --the outside world, as seen from the inside
AM1: A mirror is not entered in containedInstances.
AM2: A mirror is not counted as an instance of its type.
AM3: mirror.type = mirror.container
];
Vertex: TYPE = REF VertexPrivate;
VertexPrivate: TYPE = RECORD [
containingCT: CellType,
QNext: Vertex ← notInQ,
colorNext, equiv: Vertex ← NIL,
firstEdge, lastEdge: Edge ← NIL,
The connections to/from cells.
AI1: The edges are in the following order: first, the cellward ones, if any, in any order, then the wireward ones, ordered by port.
other: Assertions ← NIL,
oldColor, curColor: Color ← noColor,
graph: GraphID ← Unspecified,
unique, suspect: BOOLFALSE,
variant: SELECT class: VertexClass FROM
cell => [
type: CellType ← NIL,
nextInstance, prevInstance: CellInstance ← NIL
],
intermediate => [
port: Port
],
wire => [
containingWire: Wire ← NIL,
next, prev: Wire ← NIL, --Siblings
firstChild, lastChild: Wire ← NIL
],
ENDCASE];
VertexClass: TYPE = {cell, intermediate, wire};
CellInstance: TYPE = REF cell VertexPrivate;
Intermediary: TYPE = REF intermediate VertexPrivate;
Wire: TYPE = REF wire VertexPrivate;
WireIndex: PROC [parent, child: Wire] RETURNS [index: INT];
SubWire: PROC [parent: Wire, index: INT] RETURNS [child: Wire];
EnumeratePortAndWire: PROC [port: Port, wire: Wire, Consume: PROC [Port, Wire]];
FirstChildWire: PROC [parent: Wire] RETURNS [child: Wire]
= INLINE {child ← parent.firstChild};
NextChildWire: PROC [child: Wire] RETURNS [sibling: Wire]
= INLINE {sibling ← child.next};
Edge: TYPE = REF EdgePrivate;
EdgePrivate: TYPE = RECORD [
sides: ARRAY GraphDirection OF RECORD [v: Vertex, next, prev: Edge],
port: Port --what the wireward vertex is connected to
];
GraphDirection: TYPE = {cellward, wireward};
OppositeDirection: ARRAY GraphDirection OF GraphDirection = [cellward: wireward, wireward: cellward];
notInQ: Vertex --don't look:-- = NIL --you looked!--;
endOfQ: Vertex;
EnumerateImmediateEdges: PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOLALL[TRUE], order: Order ← any];
the Port is the wireward one.
EnumerateImmediateConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOLALL[TRUE], order: Order ← any];
EnumerateTransitiveConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex]];
EnumerateTopEdges: PROC [ci: CellInstance, Consume: PROC [Port, Wire, Edge]];
EnumerateTopConnections: PROC [ci: CellInstance, Consume: PROC [Port, Wire]];
EnumerateNeighboringVertices: PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOLALL[TRUE]];
FindImmediateConnection: PROC [cellward: Vertex, port: Port, hint: Order ← any] RETURNS [w: Vertex];
FindImmediateEdge: PROC [cellward: Vertex, port: Port, hint: Order ← any] RETURNS [w: Vertex, e: Edge];
FindTransitiveConnection: PROC [cellward: Vertex, port: Port] RETURNS [w: Wire];
ImParent: PROC [im: Intermediary] RETURNS [v: Vertex];
Order: TYPE = {forward, backward, any};
Array: TYPE = REF ArrayPrivate;
ArrayPrivate: TYPE = RECORD [
eltType: CellType ← NIL,
nextArray, prevArray: CellType ← NIL,
size: Size2 ← ALL[1],
jointsPeriod: Nat2 ← ALL[1],
groupingParmses: GroupingParmses,
groupingses: RefSeq--groupings index b Groupings--,
toRole: ARRAY Dim OF ARRAY End OF RefTable--dim b side b port b RoledPortData--ALL[ALL[NIL]],
roles: ARRAY Dim OF VarRefSeq--dim b index b RoledPortData--ALL[NIL],
nrp: ARRAY Dim OF NATALL[0],
joints: ARRAY Dim--in which we are joining-- OF RefSeq--of Joint--ALL[NIL],
portConnections: RefTable--ap  array.port b apc: ArrayPortConnections--,
redundant with porting.
porting: RefTable--ep  eltType.port b p: Porting--NIL
porting[p] gives port connections for e[f, b].p, for all f, b on edge of array.
];
Dim--ension--: TYPE = {Foo, Bar};
OtherDim: ARRAY Dim OF Dim = [Foo: Bar, Bar: Foo];
Size2: TYPE = ARRAY Dim OF NAT;
Range: TYPE = RECORD [min, maxPlusOne: INT];
Range2: TYPE = ARRAY Dim OF Range;
Int2: TYPE = ARRAY Dim OF INT;
Nat2: TYPE = ARRAY Dim OF NAT;
Central: PROC [a: Array, ai: ArrayIndex] RETURNS [BOOL];
GroupingParmses: TYPE = ARRAY Dim OF GroupingParms;
GroupingParms: TYPE = RECORD [
middle: Range--or array indices or joint instance indices--,
firstHigh, sum: NAT,
d: INT
];
middle is range of (joint | array) indices covered
firstHigh is first grouping index of high range of irregulars
ý peculiar = middle.min + size-middle.maxPlusOne
hasMiddle = middle.maxPlusOne > middle.min
sum = ý peculiar + hasMiddle*jointsPeriod for arrays
sum = ý peculiar + hasMiddle for joints
firstHigh = sum - (size-middle.maxPlusOne)
d = firstHigh - middle.maxPlusOne
HasMiddle: PROC [gp: GroupingParms] RETURNS [has: BOOL]
= INLINE {has ← gp.middle.maxPlusOne > gp.middle.min};
ComputeGroupingsIndex: PROC [a: Array, ai: ArrayIndex] RETURNS [gi2, gii2: Nat2, gi, cgii: NAT];
GPMiddle: PROC [gp: GroupingParmses] RETURNS [r2: Range2]
= INLINE {r2 ← [gp[Foo].middle, gp[Bar].middle]};
Groupings: TYPE = REF GroupingsPrivate;
GroupingsPrivate: TYPE = RECORD [
toGroup: RefTable--port b Group--,
groups: Set
];
PortToGroup: PROC [a: Array, gi: NAT, port: Port] RETURNS [g: Group] = INLINE {
gs: Groupings = NARROW[a.groupingses[gi]];
g ← NARROW[gs.toGroup.Fetch[port].value];
};
GroupListPair: TYPE = ARRAY End OF GroupList;
GroupList: TYPE = LIST OF Group;
Group: TYPE = REF GroupPrivate;
GroupPrivate: TYPE = RECORD [
ports: PortList ← NIL,
better: Group ← NIL,
worse: GroupList ← NIL,
stopLooking: ARRAY Dim OF ARRAY End OF BOOLALL[ALL[FALSE]]
];
BestGroup: PROC [g: Group] RETURNS [bg: Group]
= INLINE {IF g = NIL THEN bg ← g ELSE FOR bg ← g, bg.better WHILE bg.better # NIL DO NULL ENDLOOP};
ComputeJointGroupingsIndex: PROC [a: Array, j: Joint, jii: Nat2] RETURNS [jgi2: Nat2, jgi, ctii: NAT, jiir: Range2];
<low side's groupings index, high side's gi> é joint groupings index
Joint: TYPE = REF JointPrivate;
JointPrivate: TYPE = RECORD [
size2: Size2--number of instances--,
size: INT--P size2--,
groupingParmses: GroupingParmses,
ties: RefSeq--joint groupings index b Set(of Tie)--,
toTie: ARRAY End OF RefSeq--side of joint b joint groupings index b RefTable(Group b Tie)--
];
GetArrayJoint: PROC [a: Array, d: Dim, phase: Nat2] RETURNS [j: Joint]
= INLINE {j ← NARROW[a.joints[d][ArrayJointIndex[a, phase]]]};
ArrayJointIndex: PROC [a: Array, phase: Nat2] RETURNS [i: INT]
= INLINE {i ← phase[Foo]*a.jointsPeriod[Bar] + phase[Bar]};
Jgi2ToLair: PROC [a: Array, phase: Nat2, j: Joint, jgi2: Nat2] RETURNS [lair, jiir: Range2, jCount: NAT];
FetchTie: PROC [j: Joint, side: End, jgi: NAT, g: Group] RETURNS [tie: Tie]
= INLINE {rt: RefTable = NARROW[j.toTie[side][jgi]]; tie ← NARROW[rt.Fetch[g].value]};
TieList: TYPE = LIST OF Tie;
Tie: TYPE = REF TiePrivate;
TiePrivate: TYPE = RECORD [
groups: ARRAY End OF Group,
completion: Completion ← NIL,
better: Tie ← NIL--when tie gets merged with another, better=that union--
];
BestTie: PROC [x: Tie] RETURNS [bx: Tie]
= INLINE {FOR bx ← x, bx.better WHILE bx.better # NIL DO NULL ENDLOOP};
GroupsHypotheticallyConnected: PROC [a: Array, j: Joint, jgi: NAT, gs: ARRAY End OF Group] RETURNS [BOOL];
GroupsActuallyConnected: PROC [a: Array, j: Joint, jgi: NAT, lai: Nat2, gs: ARRAY End OF Group] RETURNS [BOOL];
RoledPortDataList: TYPE = LIST OF RoledPortData;
RoledPortData: TYPE = REF RoledPortDataPrivate;
RoledPortDataPrivate: TYPE = RECORD [
port: Port,
side: End,
index: NAT,
links: Links ← NIL
];
RoledPortList: TYPE = LIST OF RoledPort;
RoledPort: TYPE = RECORD [side: End, port: Port];
FetchRPD: PROC [a: Array, d: Dim, rp: RoledPort] RETURNS [rpd: RoledPortData]
= INLINE {rpd ← NARROW[a.toRole[d][rp.side].Fetch[rp.port].value]};
Links: TYPE = REF LinksPrivate;
LinksPrivate: TYPE = RECORD [
linkSize: NAT,
negLinkSize, negLgLinksPerWord: INTEGER,
lgLinksPerWord: Sublg,
words: SEQUENCE length: NAT OF WORD
];
words[clai ShiftRight lgLinksPerWord] ShiftRight (linkSize*(clai MaskLast lgLinksPerWord)) MaskLast linkSize gives index of another roledPort connected to this one at ji
where:
clai = <size[Foo], size[Bar]> ¥ <lai[Foo], lai[Bar]>
`¥' is APL's `decode'
size is the size of array
lai is the array index of the element on the low side of the joint
GetRoot: PROC [a: Array, d: Dim, rp: RoledPortData, clai: NAT] RETURNS [root: NAT];
GetNext: PROC [rp: RoledPortData, clai: NAT] RETURNS [next: NAT];
RPDNeedsLinks: PROC [a: Array, d: Dim, rpd: RoledPortData] RETURNS [needs: BOOL];
ArrayEltPortsConnected: PROC [a: Array, d: Dim, lowIndex: ArrayIndex, rp1, rp2: RoledPort] RETURNS [hypothetically, really: BOOL];
Sublg: TYPE = NAT [0 .. Basics.logBitsPerWord];
Completion: TYPE = REF CompletionPrivate;
CompletionPrivate: TYPE = RECORD [
nIncomplete: NAT ← 0,
complete: PACKED SEQUENCE length: NAT OF BOOL
];
complete[instance index] { all connections present at this instance
IsIncompleteArray: PROC [ct: CellType] RETURNS [BOOL];
Porting: TYPE = REF ANY --actually UNION [{notPorted, unknownPorting}, DetailedPorting]--;
notPorted: Porting;
unknownPorting: Porting;
DetailedPorting: TYPE = REF DetailedPortingRep;
DetailedPortingRep: TYPE = RECORD [
corners: ARRAY End--Foo-- OF ARRAY End--Bar-- OF Port,
e[Foo.LAST, Bar.LAST].p é a.q { porting[p].corners[high][high] = q
NIL means elt port not connected to any array port.
sideIndices: ARRAY End OF ARRAY Dim OF SideIndex,
sideIndices[low][Foo] covers [f, b] f = FIRST[Foo] & b  (FIRST[BAR] .. LAST[BAR])
slots: SEQUENCE length: NAT OF Port];
End: TYPE = {low, high};
OtherEnd: ARRAY End OF End = [low: high, high: low];
SideIndex: TYPE = RECORD [same: BOOL, firstSlot: NAT];
ArrayPortConnections: TYPE = REF ArrayPortConnectionsPrivate;
ArrayPortConnectionsPrivate: TYPE = ARRAY End OF ARRAY Dim OF SideConnection;
SideConnection: TYPE = IntTable--index[other dim] b elt Port--;
ArrayIndex: TYPE = ARRAY Dim OF INT;
GetArrayPort: PROC [a: Array, index: ArrayIndex, ep: Port] RETURNS [arrayPort: Port];
RefSeq: TYPE = REF RefSequence;
RefSequence: TYPE = RECORD [
elts: SEQUENCE length: NAT OF REF ANY];
CreateRefSeq: PROC [len: NAT] RETURNS [rs: RefSeq]
= INLINE {rs ← NEW [RefSequence[len]]};
VarRefSeq: TYPE = REF VarRefSequence;
VarRefSequence: TYPE = RECORD [
length: NAT,
refs: RefSeq];
CreateVarRefSeq: PROC [size: NAT ← 12] RETURNS [vrs: VarRefSeq]
= INLINE {vrs ← NEW [VarRefSequence ← [0, CreateRefSeq[size]]]};
VarRefSeqAppend: PROC [vrs: VarRefSeq, value: REF ANY];
BoolSeq: TYPE = REF BoolSequence;
BoolSequence: TYPE = RECORD [elts: PACKED SEQUENCE length: NAT OF BOOL];
CreateBoolSeq: PROC [len: NAT, b0: BOOLFALSE] RETURNS [bs: BoolSeq]
= INLINE {bs ← NEW [BoolSequence[len]]; FOR i: NAT IN [0 .. len) DO bs[i] ← b0 ENDLOOP};
FloorDiv: PROC [num, den: INT] RETURNS [quot: INT];
CeilDiv: PROC [num, den: INT] RETURNS [quot: INT];
Int2Add: PROC [a, b: Int2] RETURNS [c: Int2]
= INLINE {c ← [Foo: a[Foo]+b[Foo], Bar: a[Bar]+b[Bar]]};
Int2Sub: PROC [a, b: Int2] RETURNS [c: Int2]
= INLINE {c ← [Foo: a[Foo]-b[Foo], Bar: a[Bar]-b[Bar]]};
Int2InRange: PROC [i: Int2, r: Range2] RETURNS [in: BOOL]
= INLINE {in ← i[Foo] IN [r[Foo].min .. r[Foo].maxPlusOne) AND i[Bar] IN [r[Bar].min .. r[Bar].maxPlusOne)};
Int2Tweak: PROC [i: Int2, d: Dim, D: INT] RETURNS [j: Int2]
= INLINE {j ← i; j[d] ← j[d] + D};
ConsNat2: PROC [d1: Dim, x1, x2: NAT] RETURNS [x: Nat2]
= INLINE {x[d1] ← x1; x[OtherDim[d1]] ← x2};
Nat2Add: PROC [a, b: Nat2] RETURNS [c: Nat2]
= INLINE {c ← [Foo: a[Foo]+b[Foo], Bar: a[Bar]+b[Bar]]};
Nat2Mul: PROC [a, b: Nat2] RETURNS [c: Nat2]
= INLINE {c ← [Foo: a[Foo]*b[Foo], Bar: a[Bar]*b[Bar]]};
Nat2Tweak: PROC [i: Nat2, d: Dim, D: INT] RETURNS [j: Nat2]
= INLINE {j ← i; j[d] ← j[d] + D};
Nat2Area: PROC [x: Nat2] RETURNS [a: NAT]
= INLINE {a ← x[Foo] * x[Bar]};
RangeOff: PROC [r: Range, D: INT] RETURNS [s: Range]
= INLINE {s ← [min: r.min + D, maxPlusOne: r.maxPlusOne + D]};
RangeOffClip: PROC [r: Range, D: INT] RETURNS [s: Range]
= INLINE {s ← [min: MAX[r.min + D, 0], maxPlusOne: r.maxPlusOne + D]};
ShaveRange2Top1: PROC [r: Range2, d: Dim] RETURNS [sr: Range2]
= INLINE {sr ← r; sr[d].min ← MIN[sr[d].min, sr[d].maxPlusOne ← sr[d].maxPlusOne - 1]};
ConsRange2: PROC [d1: Dim, x1, x2: Range] RETURNS [x: Range2]
= INLINE {x[d1] ← x1; x[OtherDim[d1]] ← x2};
Range2Off: PROC [r: Range2, D: Int2] RETURNS [s: Range2]
= INLINE {s ← [Foo: RangeOff[r[Foo], D[Foo]], Bar: RangeOff[r[Bar], D[Bar]]]};
RangeArea: PROC [r: Range2] RETURNS [area: NAT]
= INLINE {area ← RangeLength[r[Foo]] * RangeLength[r[Bar]]};
RangeShape: PROC [r: Range2] RETURNS [shape: Nat2]
= INLINE {shape ← [RangeLength[r[Foo]], RangeLength[r[Bar]]]};
SizeRange: PROC [size: Nat2] RETURNS [r: Range2]
= INLINE {r ← [[0, size[Foo]], [0, size[Bar]]]};
RangeLength: PROC [r: Range] RETURNS [length: NAT]
= INLINE {length ← r.maxPlusOne - r.min};
RangesIntersect: PROC [r1, r2: Range] RETURNS [theyDo: BOOL]
= INLINE {theyDo ←
(r1.min IN [r2.min .. r2.maxPlusOne) AND r1.maxPlusOne > r1.min) OR
(r2.min IN [r1.min .. r1.maxPlusOne) AND r2.maxPlusOne > r2.min)};
Range1Mul: PROC [r: Range, t, f: NAT] RETURNS [rr: Range];
Range2Mul: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];
Range1Div: PROC [r: Range, t, f: NAT] RETURNS [rr: Range];
Range2Div: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];
END.