DIRECTORY AMBridge, Asserting, Convert, HashTable, InterpreterOps, IntHashTable, IO, LichenDataStructure, LichenDataOps, LichenSetTheory, Rope, StructuredStreams, SymTab, UnparserBuffer, ViewerIO;

LichenDataImpl: CEDAR PROGRAM
IMPORTS AMBridge, Asserting, Convert, HashTable, InterpreterOps, IntHashTable, IO, LichenDataStructure, LichenSetTheory, Rope, StructuredStreams, UnparserBuffer, ViewerIO
EXPORTS LichenDataStructure, LichenDataOps =

BEGIN OPEN LichenSetTheory, LichenDataStructure, SS:StructuredStreams, UB:UnparserBuffer;

nyet: PUBLIC ERROR = CODE;
Warning: PUBLIC SIGNAL [msg: ROPE _ NIL, v1, v2, v3, v4, v5: REF ANY _ NIL] = CODE;
Error: PUBLIC ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL] = CODE;

nameReln: PUBLIC ATOM _ $LichenName;
step: ROPE = ".";

partsByNameKey: PUBLIC ATOM _ $LichenNameToPart;

DimName: ARRAY Dim OF ROPE = [Foo: "Foo", Bar: "Bar"];

Describe: PUBLIC PROC [subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [name: ROPE] = {
GetShort: PROC [oldAssns: Assertions] RETURNS [newAssns: Assertions, name: ROPE] = {
name _ NARROW[Asserting.FnVal[nameReln, newAssns _ oldAssns]];
IF name = NIL THEN {
name _ nameGen.GenerateName[nameGen.data, subject];
newAssns _ Asserting.Assert[nameReln, LIST[name], newAssns];
};
};
IF nameGen = NIL THEN nameGen _ defaultNameGen;
IF subject = relativeTo THEN name _ NIL ELSE WITH subject SELECT FROM
d: Design => {
short: ROPE;
[d.other, short] _ GetShort[d.other];
name _ short;
};
ct: CellType => {
short: ROPE;
[ct.otherPublic, short] _ GetShort[ct.otherPublic];
name _ IF ct.designs.HasMember[relativeTo] OR ct.designs.Size[]=0 THEN short ELSE Describe[GetADesign[ct], relativeTo, nameGen].Cat[step, short];
};
v: Vertex => {
short: ROPE;
parent: REF ANY;
[v.other, short] _ GetShort[v.other];
WITH v SELECT FROM
ci: CellInstance => parent _ v.containingCT;
im: Intermediary => parent _ ImParent[im];
w: Wire => parent _ WireContainer[w];
ENDCASE => ERROR;
name _ IF relativeTo = parent OR parent = NIL THEN short ELSE Describe[parent, relativeTo, nameGen].Cat[step, short];
};
port: Port => {
short: ROPE;
parent: REF ANY = port.parent;
[port.other, short] _ GetShort[port.other];
name _ IF relativeTo = parent OR parent = NIL THEN short ELSE Describe[parent, relativeTo, nameGen].Cat[step, short];
};
ENDCASE => ERROR;
};

GetADesign: PROC [ct: CellType] RETURNS [d: Design] = {
See: PROC [ra: REF ANY] = {d _ NARROW[ra]};
IF ct.designs.Size[]  = 0 THEN RETURN [NIL];
ct.designs.Enumerate[See];
};

WireContainer: PROC [w: Wire] RETURNS [container: REF ANY] = {
container _ SELECT w.containingWire FROM
NIL => w.containingCT,
ENDCASE => w.containingWire;
};

defaultNameGen: NameGenerator = NEW [NameGeneratorPrivate _ [
GenerateBlandName,
NEW [NameCountsPrivate _ []]
]];

NameCounts: TYPE = REF NameCountsPrivate;
NameCountsPrivate: TYPE = RECORD [
design, cellType, port, vertex: INT _ 0
];

GenerateBlandName: PROC [data, subject: REF ANY] RETURNS [name: ROPE] = {
nc: NameCounts = NARROW[data];
name _ GenByCount[nc, subject];
};

TVNameGenerator: TYPE = REF TVNameGeneratorPrivate;
TVNameGeneratorPrivate: TYPE = RECORD [
nc: NameCounts,
symTab: SymTab.Ref
];

MakeTVNameGen: PROC [symTab: SymTab.Ref] RETURNS [ng: NameGenerator] = {
ng _ NEW [NameGeneratorPrivate _ [
GenerateTVName,
NEW [TVNameGeneratorPrivate _ [
nc: NEW [NameCountsPrivate _ []],
symTab: symTab
]]
]];
};

GenerateTVName: PROC [data, subject: REF ANY] RETURNS [name: ROPE] = {
tvng: TVNameGenerator = NARROW[data];
name _ Rope.Concat["&", GenByCount[tvng.nc, subject]];
TRUSTED {InterpreterOps.RegisterTV[
name: name,
tv: AMBridge.TVForReferent[WITH subject SELECT FROM
d: Design => NEW [Design _ d],
ct: CellType => NEW [CellType _ ct],
p: Port => NEW [Port _ p],
v: Vertex => NEW [Vertex _ v],
ENDCASE => ERROR],
symTab: tvng.symTab]};
};

GenByCount: PROC [nc: NameCounts, subject: REF ANY] RETURNS [name: ROPE] = {
n: INT _ 0;
WITH subject SELECT FROM
d: Design => {n _ nc.design _ nc.design + 1; name _ "D"};
ct: CellType => {n _ nc.cellType _ nc.cellType + 1; name _ "CT"};
p: Port => {n _ nc.port _ nc.port + 1; name _ "P"};
v: Vertex => {n _ nc.vertex _ nc.vertex + 1; name _ "V"};
ENDCASE => ERROR;
name _ name.Concat[Convert.RopeFromInt[n]];
};

PrintObject: PROC [to: IO.STREAM, united: BOOL, PrintIt: PROC] = {
SS.Bp[to, united, printStep];
SS.Begin[to];
PrintIt[!UNWIND => SS.End[to]];
SS.End[to];
};

printStep: INT _ 3;

PrintDesign: PROC [to: IO.STREAM, design: Design, nameGen: NameGenerator] = {
CTPrint: PROC [ra: REF ANY] = {
ct: CellType = NARROW[ra];
Inner: PROC = {PrintCellType[to, ct, nameGen]};
PrintObject[to, TRUE, Inner];
};
IF NOT SS.IsAnSS[to] THEN to _ SS.Create[UB.NewHandle[[stream[to]], 60]];
to.PutF["%g: Design {", [rope[Describe[design, NIL, nameGen]]]];
design.cellTypes.Enumerate[CTPrint];
to.PutF["}"];
};

PrintCellType: PROC [to: IO.STREAM, ct: CellType, nameGen: NameGenerator] = {
Main: PROC = {
to.PutF["%g: CellType[", [rope[Describe[ct, GetADesign[ct], nameGen]]]];
PrintObject[to, TRUE, PortPrint];
IF ct.asUnorganized # NIL THEN {
to.PutRope[", "]; PrintObject[to, TRUE, IWPrint];
to.PutRope[", "]; PrintObject[to, TRUE, CIPrint];
};
IF ct.asArray # NIL THEN {
to.PutRope[", "]; PrintObject[to, TRUE, AyPrint];
};
to.PutRope["]"];
};
PortPrint: PROC = {
to.PutF["port: "];
PrintPort[to, ct.port, nameGen];
};
IWPrint: PROC = {
to.PutF["internal wire: "];
PrintWire[to, ct.asUnorganized.internalWire, nameGen];
};
CIPrint: PROC = {
to.PutF["contained instances: "];
PrintInstances[to, ct.asUnorganized.containedInstances, ct.asUnorganized.mirror, nameGen];
};
AyPrint: PROC = {
to.PutRope["asArray: "];
PrintArray[to, ct, nameGen]
};
IF NOT SS.IsAnSS[to] THEN to _ SS.Create[UB.NewHandle[[stream[to]], 60]];
--PrintObject[to, TRUE, Main]--Main[];
};

PrintPort: PROC [to: IO.STREAM, port: Port, nameGen: NameGenerator] = {
first: BOOL _ TRUE;
to.PutRope[Describe[port, port.parent, nameGen]];
IF port.FirstChildPort[] = NIL THEN RETURN;
to.PutRope["["];
FOR subPort: Port _ port.FirstChildPort[], subPort.NextChildPort[] WHILE subPort # NIL DO
PortPrint: PROC = {PrintPort[to, subPort, nameGen]};
IF first THEN first _ FALSE ELSE to.PutRope[", "];
PrintObject[to, FALSE, PortPrint];
ENDLOOP;
to.PutRope["]"];
};

PrintWire: PROC [to: IO.STREAM, wire: Wire, nameGen: NameGenerator] = {
first: BOOL _ TRUE;
to.PutRope[Describe[wire, WireContainer[wire], nameGen]];
IF wire.FirstChildWire[] = NIL THEN RETURN;
to.PutRope["["];
FOR subWire: Wire _ wire.FirstChildWire[], subWire.NextChildWire[] WHILE subWire # NIL DO
WirePrint: PROC = {PrintWire[to, subWire, nameGen]};
IF first THEN first _ FALSE ELSE to.PutRope[", "];
PrintObject[to, FALSE, WirePrint];
ENDLOOP;
to.PutRope["]"];
};

PrintInstances: PROC [to: IO.STREAM, set: Set--OF CellInstance--, mirror: CellInstance, nameGen: NameGenerator] = {
first: BOOL _ TRUE;
PrintIt: PROC [ra: REF ANY] = {
ci: CellInstance = NARROW[ra];
IPrint: PROC = {PrintInstance[to, ci, nameGen]};
IF first THEN first _ FALSE ELSE to.PutRope[", "];
PrintObject[to, TRUE, IPrint];
};
to.PutRope["["];
set.Enumerate[PrintIt];
PrintIt[mirror];
to.PutRope["]"];
};

PrintInstance: PROC [to: IO.STREAM, ci: CellInstance, nameGen: NameGenerator] = {
PrintConnections: PROC [v: Vertex] = {
first: BOOL _ TRUE;
PrintConnection: PROC [port: Port, w: Vertex] = {
CPrint: PROC = {
to.PutF["%g: ", [rope[Describe[port, port.parent, nameGen]]]];
WITH w SELECT FROM
im: Intermediary => {
PrintConnections[im];
};
wire: Wire => {
to.PutRope[Describe[wire, WireContainer[wire], nameGen]];
};
ci: CellInstance => ERROR;
ENDCASE => ERROR;
};
IF first THEN first _ FALSE ELSE to.PutRope[", "];
PrintObject[to, FALSE, CPrint];
};
to.PutRope["["];
EnumerateImmediateConnections[v, PrintConnection, [cellward: FALSE, wireward: TRUE]];
to.PutRope["]"];
};
to.PutF["%g: %g", [rope[Describe[ci, ci.containingCT, nameGen]]], [rope[Describe[ci.type, GetADesign[ci.type], nameGen]]] ];
PrintConnections[ci];
};

PrintArray: PROC [to: IO.STREAM, ct: CellType, nameGen: NameGenerator] = {
a: Array = ct.asArray;
to.PutF["{%g BY %g OF %g (joints period is %g by %g)",
[integer[a.size[Foo]]], [integer[a.size[Bar]]],
[rope[Describe[a.eltType, GetADesign[ct], nameGen]]],
[integer[a.jointsPeriod[Foo]]], [integer[a.jointsPeriod[Bar]]]
];
FOR d: Dim IN Dim DO
PrintJoints: PROC = {
first: BOOL _ TRUE;
to.PutF[", joints[%g] = [", [rope[DimName[d]]]];
FOR ff: INT IN [0 .. a.jointsPeriod[Foo]) DO
FOR fb: INT IN [0 .. a.jointsPeriod[Bar]) DO
JPrint: PROC = {
to.PutF["[%g,%g]: ", [integer[ff]], [integer[fb]]];
PrintJoint[to, ct, GetArrayJoint[a, d, [ff, fb]], nameGen];
};
IF first THEN first _ FALSE ELSE to.PutRope[", "];
PrintObject[to, TRUE, JPrint];
ENDLOOP;
ENDLOOP;
to.PutRope["]"];
};
PrintObject[to, TRUE, PrintJoints];
ENDLOOP;
to.PutRope["}"];
};

PrintJoint: PROC [to: IO.STREAM, act: CellType, j: Joint, nameGen: NameGenerator] = {
first: BOOL _ TRUE;
PerPair: PROC [key, value: REF ANY] RETURNS [stop: BOOL _ FALSE] --HashTable.EachPairAction-- = {
lowPort: Port = NARROW[key];
highPort: Port = NARROW[value];
PPrint: PROC = {
inc: Incompleteness = IF j.lowToIncompleteness # NIL THEN NARROW[j.lowToIncompleteness.Fetch[key].value] ELSE NIL;
to.PutRope[Describe[lowPort, act, nameGen]];
to.PutRope[""];
to.PutRope[Describe[highPort, act, nameGen]];
IF inc # NIL THEN to.PutF["(%g/%g incomplete)", [integer[inc.nIncomplete]], [integer[inc.length]]];
};
IF first THEN first _ FALSE ELSE to.PutRope[", "];
PrintObject[to, TRUE, PPrint];
};
to.PutRope["["];
[] _ j.lowToHigh.Pairs[PerPair];
to.PutRope["]"];
};

EnumerateCellTypes: PUBLIC PROC [design: Design, Consume: PROC [CellType]] = {
PerCellType: PROC [elt: REF ANY] = {Consume[NARROW[elt]]};
design.cellTypes.Enumerate[PerCellType]};

endOfQ: PUBLIC Vertex _ NEW [VertexPrivate.intermediate];

EnumerateImmediateEdges: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any] = {
nextEdge: Edge _ SELECT order FROM	--these depend on AI1
forward, any => v.firstEdge,
backward => v.lastEdge,
ENDCASE => ERROR;
FOR e: Edge _ nextEdge, nextEdge WHILE e # NIL DO
selfward: GraphDirection = SELECT v.class FROM
cell => cellward,
wire => wireward,
intermediate => SELECT v FROM
e.sides[wireward].v => wireward,
e.sides[cellward].v => cellward,
ENDCASE => ERROR,
ENDCASE => ERROR;
away: GraphDirection = OppositeDirection[selfward];
w: Vertex = e.sides[away].v;
IF v # e.sides[selfward].v THEN ERROR;
IF v.class # intermediate AND v.class = w.class THEN ERROR Error["Broken"];
nextEdge _ SELECT order FROM	--these depend on AI1
forward, any => e.sides[selfward].next,
backward => e.sides[selfward].prev,
ENDCASE => ERROR;
IF filter[away] THEN Consume[e.port, w, e];
ENDLOOP;
};

EnumerateImmediateConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any] = {
Filter: PROC [port: Port, w: Vertex, e: Edge] = {Consume[port, w]};
EnumerateImmediateEdges[v, Filter, filter, order];
};

EnumerateNeighboringVertices: PUBLIC PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]] = {
Filter: PROC [port: Port, w: Vertex, e: Edge] = {Consume[w]};
EnumerateImmediateEdges[v, Filter, filter];
};

EnumerateTransitiveConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex]] = {
WITH v SELECT FROM
wire: Wire => {
WireWork: PROC [wire: Wire, Consume: PROC [Port, Vertex]] = {
CellStart: PROC [port: Port, w: Vertex] = {
WITH w SELECT FROM
ci: CellInstance => Consume[port, ci];
im: Intermediary => {
CellFinish: PROC [parent: Port, u: Vertex] = {
WITH u SELECT FROM
ci: CellInstance => Consume[port, ci];
im: Intermediary => EnumerateImmediateConnections[im, CellFinish, [cellward: TRUE, wireward: FALSE]];
wire: Wire => ERROR;
ENDCASE => ERROR;
};
EnumerateImmediateConnections[im, CellFinish, [cellward: TRUE, wireward: FALSE]];
};
wire: Wire => ERROR;
ENDCASE => ERROR;
};
EnumerateImmediateConnections[wire, CellStart];
IF wire.containingWire # NIL THEN {
index: INT = WireIndex[wire.containingWire, wire];
Filter: PROC [parent: Port, w: Vertex] = {
port: Port = SubPort[parent, index];
Consume[port, w]};
WireWork[wire.containingWire, Filter];
};
};
WireWork[wire, Consume];
};
im: Intermediary => ERROR;
ci: CellInstance => {
Elaborate: PROC [port: Port, wire: Wire] = {EnumeratePortAndWire[port, wire, Consume]};
EnumerateTopConnections[ci, Elaborate];
};
ENDCASE => ERROR;
};

EnumerateTopEdges: PUBLIC PROC [ci: CellInstance, Consume: PROC [Port, Wire, Edge]]= {
Work: PROC [port: Port, v: Vertex, e: Edge] = {
WITH v SELECT FROM
wire: Wire => Consume[port, wire, e];
im: Intermediary => EnumerateImmediateEdges[im, Work, [cellward: FALSE, wireward: TRUE]];
ci: CellInstance => ERROR;
ENDCASE => ERROR;
};
EnumerateImmediateEdges[ci, Work];
};

EnumerateTopConnections: PUBLIC PROC [ci: CellInstance, Consume: PROC [Port, Wire]]= {
Filter: PROC [port: Port, w: Wire, e: Edge] = {Consume[port, w]};
EnumerateTopEdges[ci, Filter];
};

FindImmediateConnection: PUBLIC PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex] = {
w _ FindImmediateEdge[cellward, port, hint].w;
};

FindImmediateEdge: PUBLIC PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex, e: Edge] = {
ENABLE Escape => CONTINUE;
Consume: PROC [tp: Port, tw: Vertex, te: Edge] = {
IF tp = port THEN {w _ tw; e _ te; Escape};
};
EnumerateImmediateEdges[cellward, Consume, [cellward: FALSE, wireward: TRUE], hint];
ERROR--not found--;
};
Escape: ERROR = CODE;

FindTransitiveConnection: PUBLIC PROC [cellward: Vertex, port: Port] RETURNS [w: Wire] = {
ENABLE Escape => CONTINUE;
Tryit: PROC [p: Port, v: Vertex] = {
IF port = p THEN {w _ NARROW[v]; Escape};
};
EnumerateTransitiveConnections[cellward, Tryit];
ERROR--not found--;
};

ImParent: PUBLIC PROC [im: Intermediary] RETURNS [v: Vertex] = {
See: PROC [w: Vertex] = {v _ w};
EnumerateNeighboringVertices[im, See, [cellward: TRUE, wireward: FALSE]];
};

notPorted: PUBLIC Porting _ NEW [ROPE _ "not ported"];
unknownPorting: PUBLIC Porting _ NEW [ROPE _ "unknown porting"];

GetArrayPort: PUBLIC PROC [a: Array, index: ArrayIndex, ep: Port] RETURNS [arrayPort: Port] = {
Get: PROC [pp: PortPtr] = TRUSTED {arrayPort _ IF pp # NIL THEN pp^ ELSE NIL};
ForArrayPort[a, index, ep, Get, FALSE]};

SetArrayPort: PUBLIC PROC [a: Array, index: ArrayIndex, ep, ap: Port] = {
Set: PROC [pp: PortPtr] = TRUSTED {IF pp # NIL THEN pp^ _ ap ELSE ERROR};
wF: Where = WhereIs[index[Foo], [0, a.size[Foo]]];
wB: Where = WhereIs[index[Bar], [0, a.size[Bar]]];
apc: ArrayPortConnections _ NARROW[a.portConnections.Fetch[ap].value];
ForArrayPort[a, index, ep, Set, TRUE];
IF apc = NIL THEN {
apc _ NEW [ArrayPortConnectionsPrivate _ ALL[ALL[NIL]]];
FOR e: End IN End DO FOR d: Dim IN Dim DO
apc[e][d] _ CreateIntTable[];
ENDLOOP ENDLOOP;
[] _ a.portConnections.Store[ap, apc];
};
FOR d: Dim IN Dim DO
id: INT = index[d];
wd: Where = WhereIs[id, [0, a.size[d]]];
WITH ed: wd SELECT FROM
end => [] _ apc[ed.end][d].Store[index[OtherDim[d]], ep];
center => NULL;
ENDCASE => ERROR;
ENDLOOP;
};

PortPtr: TYPE = LONG POINTER TO Port;

ForArrayPort: PROC [a: Array, index: ArrayIndex, ep: Port, Consume: PROC [pp: PortPtr], mayCreate: BOOL] = TRUSTED {
p: Porting = a.porting.Fetch[ep].value;
dp: DetailedPorting;
SELECT p FROM
notPorted => {
IF NOT mayCreate THEN {
Consume[NIL];
RETURN}
ELSE {
xyz: NAT = (MAX[a.size[Foo]-2, 0] + MAX[a.size[Bar]-2, 0]) * 2;
firstSlot: INT _ 0;
dp _ NEW [DetailedPortingRep[xyz]];
dp.corners _ ALL[ALL[NIL]];
FOR e: End IN End DO FOR d: Dim IN Dim DO
dp.sideIndices[e][d] _ [FALSE, firstSlot];
firstSlot _ firstSlot + MAX[a.size[OtherDim[d]]-2, 0];
ENDLOOP ENDLOOP;
FOR i: INT IN [0 .. dp.length) DO dp[i] _ NIL ENDLOOP;
[] _ a.porting.Store[ep, dp];
};
};
unknownPorting => ERROR;
ENDCASE => dp _ NARROW[p];
{
For: PROC [si: SideIndex, offset: NAT] = TRUSTED {
s: NAT _ si.firstSlot;
IF NOT si.same THEN s _ s + offset;
Consume[@dp.slots[s]]};
wF: Where = WhereIs[index[Foo], [0, a.size[Foo]]];
wB: Where = WhereIs[index[Bar], [0, a.size[Bar]]];
WITH f: wF SELECT FROM
end => WITH b: wB SELECT FROM
end => Consume[@dp.corners[f.end][b.end]];
center => For[dp.sideIndices[f.end][Bar], b.offset];
ENDCASE => ERROR;
center => WITH b: wB SELECT FROM
end => For[dp.sideIndices[b.end][Foo], f.offset];
center => ERROR;
ENDCASE => ERROR;
ENDCASE => ERROR;
};
};

Where: TYPE = RECORD [
variant: SELECT kind: * FROM
end => [end: End],
center => [offset: NAT],
ENDCASE];

WhereIs: PROC [i: INT, r: Range] RETURNS [w: Where] = {
i _ r.min + ((i - r.min) MOD (r.maxPlusOne - r.min));
SELECT TRUE FROM
i = r.min => RETURN [[end[low]]];
i+1 = r.maxPlusOne => RETURN [[end[high]]];
ENDCASE => RETURN [[center[i - (r.min+1)]]];
};

EnumeratePorts: PUBLIC PROC [cellType: CellType, Consume: PROC [Port]] = {
Work: PROC [port: Port, wire: Wire, wired: BOOL] = {
subPort: Port _ port.firstChild;
subWire: Wire _ IF wired THEN wire.firstChild ELSE NIL;
IF port.wire # wire THEN ERROR Error["Broken"];
Consume[port];
WHILE subPort # NIL DO
IF NOT wired THEN subWire _ subPort.wire ELSE IF subWire = NIL THEN ERROR Error["Broken"];
Work[subPort, subWire, subWire # NIL];
subPort _ subPort.next;
IF wired THEN subWire _ subWire.next;
ENDLOOP;
IF wired AND subWire # NIL THEN ERROR Error["Broken"];
};
Work[cellType.port, cellType.port.wire, cellType.port.wire # NIL];
IF cellType.port.next # NIL THEN ERROR Error["Broken"];
};

EnumerateInstances: PUBLIC PROC [cellType: CellType, Consume: PROC [CellInstance]] = {
FOR ci: CellInstance _ cellType.firstInstance, ci.nextInstance WHILE ci # NIL DO
Consume[ci];
ENDLOOP;
};

EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] = {
FOR act: CellType _ cellType.firstArray, act.asArray.nextArray WHILE act # NIL DO
Consume[act];
ENDLOOP;
};

EnumeratePortAndWire: PUBLIC PROC [port: Port, wire: Wire, Consume: PROC [Port, Wire]] = {
Consume[port, wire];
port _ port.firstChild;
wire _ wire.firstChild;
WHILE port # NIL AND wire # NIL DO
EnumeratePortAndWire[port, wire, Consume];
port _ port.next;
wire _ wire.next;
ENDLOOP;
IF port # NIL OR wire # NIL THEN ERROR Error["Broken"];
};

WireIndex: PUBLIC PROC [parent, child: Wire] RETURNS [index: INT] = {
index _ 0;
FOR x: Wire _ parent.firstChild, x.next WHILE x # child DO index _ index + 1 ENDLOOP;
index _ index;
};

SubWire: PUBLIC PROC [parent: Wire, index: INT] RETURNS [child: Wire] = {
FOR child _ parent.firstChild, child.next WHILE index > 0 DO index _ index - 1 ENDLOOP;
};

PortCCT: PUBLIC PROC [port: Port] RETURNS [containingCT: CellType] = {
DO
WITH port.parent SELECT FROM
ct: CellType => RETURN [ct];
p: Port => port _ p;
ENDCASE => ERROR;
ENDLOOP;
};

PortIndex: PUBLIC PROC [parent, child: Port] RETURNS [index: INT] = {
index _ 0;
FOR x: Port _ parent.firstChild, x.next WHILE x # child DO index _ index + 1 ENDLOOP;
index _ index;
};

SubPort: PUBLIC PROC [parent: Port, index: INT] RETURNS [child: Port] = {
FOR child _ parent.firstChild, child.next WHILE index > 0 DO index _ index - 1 ENDLOOP;
};

EnsureAllIn: PUBLIC PROC [design: Design] = {
IF design.allKnown THEN RETURN;
design.allKnown _ TRUE;
EnumerateCellTypes[design, EnsurePrivate];
};

EnsurePublic: PUBLIC PROC [ct: CellType] = {
IF NOT ct.publicKnown THEN ERROR Error["Broken: Found cell type with undefined interface"];
IF ct.port = NIL THEN ERROR;
};

EnsurePrivate: PUBLIC PROC [ct: CellType] = {
IF NOT ct.privateKnown THEN {
ct.class.DefinePrivates[ct];
IF NOT ct.privateKnown THEN ERROR;
};
};

ExpansionKnown: PUBLIC PROC [ct: CellType] RETURNS [known: BOOL] = {
known _ ct.asUnorganized # NIL OR ct.asArray # NIL;
};

NoteChange: PUBLIC PROC [cellType: CellType] = {
NULL--er, we haven't yet figured out just what to do about the fact that cell types can change--;
};

AddPort: PUBLIC PROC [p: PortPrivate _ []] RETURNS [port: Port] = {
port _ NEW [PortPrivate _ p];
WITH p.parent SELECT FROM
pp: Port => {
port.next _ NIL;
port.prev _ pp.lastChild;
pp.lastChild _ port;
IF port.prev # NIL THEN port.prev.next _ port ELSE pp.firstChild _ port;
};
ct: CellType => {
IF ct.port # NIL THEN ERROR;
ct.port _ port;
port.next _ port.prev _ NIL;
port.other _ Asserting.Assert[nameReln, LIST[R["PORTS"]], port.other];
};
ENDCASE => ERROR;
};

R: PROC [r: ROPE] RETURNS [r2: ROPE] = INLINE {r2 _ r}--stupid goddam anachronism--;

FullyAddPort: PUBLIC PROC [p: PortPrivate _ [], andReportConnectionTo: CellInstance _ NIL] RETURNS [port: Port, connection: Wire _ NIL] = {
ct: CellType = PortCCT[port _ AddPort[p]];
portName: ROPE = Describe[port, ct.port];
FixInstance: PROC [ci: CellInstance] = {
instanceName: ROPE = Describe[ci, ci.containingCT].Cat["/", portName];
w: Wire = CreateWire[ci.containingCT, NIL, Asserting.Assert[nameReln, LIST[instanceName], NIL]];
AddEdge[[cellward: ci, wireward: w], port];
IF andReportConnectionTo = ci THEN connection _ w;
};
FixArray: PROC [act: CellType] = {
a: Array = act.asArray;
[] _ a.porting.Store[port, notPorted];
};
IF ct.asUnorganized # NIL THEN {
IF ct.asUnorganized.mirror = NIL THEN ERROR;
IF p.wire = NIL THEN ERROR;
AddEdge[[cellward: ct.asUnorganized.mirror, wireward: port.wire], port];
};
IF ct.asArray # NIL THEN {
apc: ArrayPortConnections = NEW [ArrayPortConnectionsPrivate];
FOR e: End IN End DO FOR d: Dim IN Dim DO
apc[e][d] _ CreateIntTable[];
ENDLOOP ENDLOOP;
[] _ ct.asArray.portConnections.Store[port, apc];
};
EnumerateInstances[ct, FixInstance];
EnumerateArrays[ct, FixArray];
};

RemovePort: PUBLIC PROC [port: Port] = {
WITH port.parent SELECT FROM
pp: Port => {
IF port.next = NIL THEN pp.lastChild _ port.prev ELSE port.next.prev _ port.prev;
IF port.prev = NIL THEN pp.firstChild _ port.next ELSE port.prev.next _ port.next;
};
ct: CellType => {
ERROR --I don't think we ever really want to Remove the root port--;
};
ENDCASE => ERROR;
};

AddEdge: PUBLIC PROC [vs: ARRAY GraphDirection OF Vertex, port: Port] = {
e: Edge = NEW [EdgePrivate _ [port: port]];
FOR dir: GraphDirection IN GraphDirection DO e.sides[dir].v _ vs[dir] ENDLOOP;
FOR side: GraphDirection IN GraphDirection DO
LinkEdge[vs[side], e, side];
ENDLOOP;
};

LinkEdge: PROC [v: Vertex, e: Edge, side: GraphDirection] = {
prev, next: Edge;
SELECT side FROM
cellward => {
prev _ IF e.port.prev # NIL THEN FindImmediateEdge[v, e.port.prev, backward].e ELSE v.lastEdge;
};
wireward => prev _ v.lastEdge;
ENDCASE => ERROR;
e.sides[side].next _ next _ IF prev # NIL THEN prev.sides[side].next ELSE NIL;
e.sides[side].prev _ prev;
IF prev = NIL THEN v.firstEdge _ e ELSE prev.sides[side].next _ e;
IF next = NIL THEN v.lastEdge _ e ELSE next.sides[side].prev _ e;
};

AddEdges: PUBLIC PROC [vs: ARRAY GraphDirection OF Vertex, port: Port] = {
rootPort: Port = WITH vs[cellward] SELECT FROM
ci: CellInstance => ci.type.port,
im: Intermediary => im.port,
w: Wire => ERROR Error["Broken"],
ENDCASE => ERROR;
FindVertex: PROC [port: Port] RETURNS [v: Vertex] = {
cellward: Vertex;
IF port = rootPort THEN RETURN [vs[cellward]];
cellward _ FindVertex[NARROW[port.parent]];
v _ FindImmediateConnection[cellward, port];
IF v # NIL THEN RETURN;
v _ CreateIntermediary[cellward, wireward, cellward.containingCT, port];
};
immediatelyCellward: Vertex = FindVertex[NARROW[port.parent]];
AddEdge[[cellward: immediatelyCellward, wireward: vs[wireward]], port];
};

RemoveEdge: PUBLIC PROC [e: Edge] = {
FOR dir: GraphDirection IN GraphDirection DO
[e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge] _ UnlinkEdge[e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge, e, dir];
ENDLOOP;
};

UnlinkEdge: PROC [head, tail, e: Edge, dir: GraphDirection] RETURNS [newHead, newTail: Edge] = {
newHead _ head; newTail _ tail;
IF e.sides[dir].next # NIL THEN e.sides[dir].next.sides[dir].prev _ e.sides[dir].prev ELSE newTail _ e.sides[dir].prev;
IF e.sides[dir].prev # NIL THEN e.sides[dir].prev.sides[dir].next _ e.sides[dir].next ELSE newHead _ e.sides[dir].next;
};

RemoveEdges: PUBLIC PROC [e: Edge] = {
cellward: Vertex = e.sides[cellward].v;
RemoveEdge[e];
IF ISTYPE[cellward, Intermediary] AND (cellward.lastEdge = NIL OR cellward.lastEdge.sides[wireward].v = cellward--AI1 used here--) THEN RemoveEdges[cellward.firstEdge--AI1 used here--];
};

UnlinkPort: PUBLIC PROC [ci: CellInstance, port: Port] = {
RemoveEdge[FindImmediateEdge[ci, port].e]};

Instantiate: PUBLIC PROC [type, containingCT: CellType, other: Assertions _ NIL] RETURNS [ci: CellInstance] = {
ci _ NEW [VertexPrivate.cell _ [
containingCT: containingCT,
other: other,
variant: cell[
type: type,
nextInstance: NIL,
prevInstance: type.lastInstance]]];
type.lastInstance _ ci;
IF ci.prevInstance # NIL THEN ci.prevInstance.nextInstance _ ci ELSE ci.type.firstInstance _ ci;
type.useCount _ type.useCount + 1;
[] _ containingCT.asUnorganized.containedInstances.UnionSingleton[ci];
NoteNewPart[ci];
};

CreateWire: PUBLIC PROC [containingCT: CellType, containingWire: Wire _ NIL, other: Assertions _ NIL, copy: Wire _ NIL] RETURNS [w: Wire] = {
IF containingWire = NIL THEN containingWire _ containingCT.asUnorganized.internalWire;
w _ NEW [VertexPrivate.wire _ [
containingCT: containingCT,
other: other,
variant: wire[
containingWire: containingWire,
next: NIL,
prev: IF containingWire#NIL THEN containingWire.lastChild ELSE NIL
]]];
IF w.prev # NIL THEN w.prev.next _ w ELSE IF containingWire#NIL THEN containingWire.firstChild _ w;
IF containingWire#NIL THEN containingWire.lastChild _ w ELSE containingCT.asUnorganized.internalWire _ w;
IF copy # NIL THEN WireCopy[copy, w];
NoteNewPart[w];
};

WireCopy: PROC [from, to: Wire] = {
FOR child: Wire _ from.FirstChildWire[], child.NextChildWire[] WHILE child # NIL DO
[] _ CreateWire[to.containingCT, to, NIL, child];
ENDLOOP;
};

CreateIntermediary: PUBLIC PROC [from: Vertex, go: GraphDirection, containingCT: CellType, port: Port, other: Assertions _ NIL] RETURNS [im: Intermediary] = {
vs: ARRAY GraphDirection OF Vertex _ ALL[from];
vs[go] _ im _ NEW [VertexPrivate.intermediate _ [
containingCT: containingCT,
other: other,
variant: intermediate[port]]];
AddEdge[vs, port];
NoteNewPart[im];
};

NoteNewPart: PROC [v: Vertex] = {
ct: CellType = v.containingCT;
pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
PerName: PROC [assertion: Asserting.Assertion] = {
name: ROPE = NARROW[Asserting.TermsOf[assertion].first];
SELECT pbn.Map[name] FROM
NIL => IF pbn.SetMapping[name, v] THEN ERROR;
v => NULL;
ENDCASE => ERROR;
};
IF pbn = NIL THEN RETURN;
Asserting.EnumerateAssertionsAbout[nameReln, v.other, PerName];
};

KnowVertexName: PUBLIC PROC [v: Vertex, name: ROPE] = {
ct: CellType = v.containingCT;
pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
IF pbn # NIL THEN {
SELECT pbn.Map[name] FROM
v => NULL;
NIL => IF pbn.SetMapping[name, v] THEN ERROR;
ENDCASE => ERROR;
};
v.other _ Asserting.Assert[nameReln, LIST[name], v.other];
};

DeleteVertex: PUBLIC PROC [v: Vertex] = {
ct: CellType = v.containingCT;
pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
PerName: PROC [assertion: Asserting.Assertion] = {
name: ROPE = NARROW[Asserting.TermsOf[assertion].first];
IF NOT pbn.SetMapping[name, NIL] THEN ERROR;
};
Killit: PROC [p: Port, w: Vertex, e: Edge] = {
RemoveEdge[e];
WITH w SELECT FROM
ci: CellInstance => NULL;
im: Intermediary => IF w = e.sides[wireward].v THEN DeleteVertex[w];
wire: Wire => NULL;
ENDCASE => ERROR;
};
EnumerateImmediateEdges[v, Killit];
WITH v SELECT FROM
ci: CellInstance => {
IF ci.nextInstance # NIL THEN ci.nextInstance.prevInstance _ ci.prevInstance ELSE ci.type.lastInstance _ ci.prevInstance;
IF ci.prevInstance # NIL THEN ci.prevInstance.nextInstance _ ci.nextInstance ELSE ci.type.firstInstance _ ci.nextInstance;
v.containingCT.asUnorganized.containedInstances.RemoveElt[ci];
ci.type.useCount _ ci.type.useCount - 1;
};
im: Intermediary => NULL;
w: Wire => {
IF w.next # NIL THEN w.next.prev _ w.prev ELSE w.containingWire.lastChild _ w.prev;
IF w.prev # NIL THEN w.prev.next _ w.next ELSE w.containingWire.firstChild _ w.next;
};
ENDCASE => ERROR;
IF pbn # NIL THEN Asserting.EnumerateAssertionsAbout[nameReln, v.other, PerName];
};

IsMirror: PUBLIC PROC [v: CellInstance] RETURNS [isMirror: BOOL] = {
isMirror _ v.type = v.containingCT;
};

AddMirror: PUBLIC PROC [lct: CellType] = {
CreateMirrorBinding: PROC [port: Port, cellward: Vertex] = {
FOR subPort: Port _ port.firstChild, subPort.next WHILE subPort # NIL DO
subVertex: Vertex;
IF subPort.wire # NIL THEN {
AddEdge[[cellward: cellward, wireward: subPort.wire], subPort]}
ELSE {
subVertex _ CreateIntermediary[cellward, wireward, lct, subPort, Asserting.Filter[nameReln, subPort.other].about];
CreateMirrorBinding[subPort, subVertex];
}
ENDLOOP;
};
v: CellInstance = NEW [VertexPrivate.cell _ [
containingCT: lct,
other: Asserting.Assert[nameReln, LIST[R["mirror"]], NIL],
variant: cell[type: lct--AM2 says not to link it--]
]];
lct.asUnorganized.mirror _ v;
CreateMirrorBinding[lct.port, v];
};

MakeArrayConnection: PUBLIC PROC [ct: CellType, d: Dim, lowRange: Range2, lowPort, highPort: Port] = {
o: Dim = OtherDim[d];
a: Array = ct.asArray;
tf: INT = a.jointsPeriod[Foo];
tb: INT = 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 ff: INT IN [0 .. tf) DO
FOR fb: INT IN [0 .. tb) DO
phase2: ArrayIndex = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase2];
jir: Range2 = [
Foo: [
min: CeilDiv[MAX[lowRange[Foo].min, ff] - ff, tf],
maxPlusOne: FloorDiv[lowRange[Foo].maxPlusOne-1 - ff, tf] + 1],
Bar: [
min: CeilDiv[MAX[lowRange[Bar].min, fb] - fb, tb],
maxPlusOne: FloorDiv[lowRange[Bar].maxPlusOne-1 - fb, tb] + 1]];
jsize: Range2 = [
Foo: [0, FloorDiv[a.size[Foo]-(IF d=Foo THEN 2 ELSE 1) - ff, tf]+1],
Bar: [0, FloorDiv[a.size[Bar]-(IF d=Bar THEN 2 ELSE 1) - fb, tb]+1]];
complete: BOOL = jsize = jir;
ncji: INT = jsize[Foo].maxPlusOne * jsize[Bar].maxPlusOne;
FixMapping: PROC [mapTable: RefTable, from, to: Port] = {
SELECT mapTable.Fetch[from].value FROM
NIL => [] _ mapTable.Store[from, to];
to => NULL;
ENDCASE => ERROR;
};
FixIncompleteness: PROC [oldToInc: RefTable, from: Port] RETURNS [newToInc: RefTable] = {
inc: Incompleteness;
newToInc _ oldToInc;
IF newToInc = NIL THEN {
IF complete THEN RETURN;
newToInc _ CreateRefTable[];
};
inc _ NARROW[newToInc.Fetch[from].value];
IF inc = NIL THEN {
IF complete THEN RETURN;
inc _ NEW [IncompletenessPrivate[ncji]];
inc.nIncomplete _ ncji - RangeArea[jir];
FOR if: INT IN [0 .. jsize[Foo].maxPlusOne) DO
inf: BOOL = if IN [jir[Foo].min .. jir[Foo].maxPlusOne);
FOR ib: INT IN [0 .. jsize[Bar].maxPlusOne) DO
cji: INT = if * jsize[Bar].maxPlusOne + ib;
inc[cji] _ NOT (inf AND ib IN [jir[Bar].min .. jir[Bar].maxPlusOne));
ENDLOOP;
ENDLOOP;
[] _ newToInc.Store[from, inc];
}
ELSE {
FOR if: INT IN [jir[Foo].min .. jir[Foo].maxPlusOne) DO
FOR ib: INT IN [jir[Bar].min .. jir[Bar].maxPlusOne) DO
cji: INT = if * jsize[Bar].maxPlusOne + ib;
IF inc[cji] THEN inc.nIncomplete _ inc.nIncomplete - 1;
inc[cji] _ FALSE;
ENDLOOP;
ENDLOOP;
};
IF inc.nIncomplete = 0 THEN [] _ newToInc.Store[from, NIL];
};
FixMapping[j.lowToHigh, lowPort, highPort];
FixMapping[j.highToLow, highPort, lowPort];
j.lowToIncompleteness _ FixIncompleteness[j.lowToIncompleteness, lowPort];
j.highToIncompleteness _ FixIncompleteness[j.highToIncompleteness, highPort];
ENDLOOP ENDLOOP;
};

RangeArea: PROC [r: Range2] RETURNS [area: INT] = {
area _ (r[Foo].maxPlusOne-r[Foo].min) * (r[Bar].maxPlusOne-r[Bar].min)};

FloorDiv: PROC [num, den: INT] RETURNS [quot: INT] = {
IF den <= 0 THEN ERROR;
IF num < 0 THEN num _ num - (den-1);
quot _ num/den;
};

CeilDiv: PROC [num, den: INT] RETURNS [quot: INT] = {
IF den <= 0 THEN ERROR;
IF num > 0 THEN num _ num + (den-1);
quot _ num/den;
};

Log: PUBLIC PROC [fmt: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL] = {
DO
IF log = NIL THEN log _ ViewerIO.CreateViewerStreams["Lichen Debugging Log"].out;
log.PutF[fmt, [refAny[v1]], [refAny[v2]], [refAny[v3]], [refAny[v4]], [refAny[v5]] !IO.Error => IF ec = StreamClosed THEN {log _ NIL; LOOP}];
EXIT;
ENDLOOP;
};
log: IO.STREAM _ NIL;

END.
RLichenDataImpl.Mesa
Last Edited by: Spreitzer, June 13, 1986 2:53:21 pm PDT
Κ)`˜™J™7—J˜IcodešΟk	œHœq˜Δ
K˜šΠbxœœ
˜KšœHœY˜ͺ
Kšœ%˜,K˜Kšœ
œ'œœ˜YK˜Kšœœ
œœ
˜KšΟnœœ
œœœœ
œœœ
˜SKšŸœœ
œœœ
œœœ
˜JK˜Kšœ
œ
œ˜$Kšœœ˜K˜Kšœœ
œ˜0K˜KšŸœœœ
œ˜6K˜šŸœœ
œœ
œœ
œœœœœ˜zšŸœœœœ˜TKšœœ1˜>šœœ
œ˜K˜3Kšœ&œ˜<K˜—K˜—Kšœœ
œ˜/š
œœœ
œ
œ	œ
˜E˜Kšœœ
˜K˜%K˜
K˜—˜Kšœœ
˜Kš
œ3˜3Kš	œœ"œœœ@˜‘
K˜—˜Kšœœ
˜Kšœœ
œ
˜Kš
œ%˜%šœœ
˜K˜,Kš
œ*˜*Kš
œ%˜%Kšœœ
˜—Kšœœœ
œ
œœ8˜uK˜—˜Kšœœ
˜Kšœœ
œ˜Kš
œ+˜+Kšœœœ
œ
œœ8˜uK˜—Kšœœ
˜—K˜—K˜šŸ
œœœ˜7Kš
Ÿœœœ
œ	œ˜+Kšœœ
œœ˜,K˜K˜—K˜š
Ÿ
œœœ
œ
œ˜>šœœ˜(Kšœ˜Kšœ˜—K˜—K˜šœ œ˜=K˜Kšœ˜K˜—K˜Kšœœœ˜)šœœœ˜"Kšœ œ˜'K˜—K˜šŸœœœ
œœœ˜IKšœœ˜K˜K˜—K˜Kšœœœ˜3šœœœ˜'K˜K˜K˜—K˜šŸ
œœœ˜Hšœœ˜"K˜šœ˜Kšœœ˜!K˜K˜—K˜—K˜—K˜šŸœœœ
œœœ˜FKšœœ˜%K˜6šœ˜#K˜šœœ	œ
˜3Kšœ
œ˜Kšœœ˜$Kšœœ˜Kšœ
œ˜Kšœœ˜—K˜—K˜—K˜šŸ
œœœ
œœœ˜LKšœœ˜šœ	œ
˜K˜9K˜AK˜3K˜9Kšœœ
˜—K˜+K˜—K˜šŸœœœ
œ
œŸœœ˜BKšœ˜Kšœ˜
Kšœ	œœ
˜Kšœ	˜K˜—K˜Kšœœ˜K˜šŸœœœ
œ-˜MšŸœœœ
œ˜Kšœœ˜KšŸœœ$˜/Kšœœ	˜K˜—Kšœ
œ
œœœœ˜IKšœ/œ˜@Kš
œ$˜$K˜
K˜—K˜šŸ
œœœ
œ+˜MšŸœœ˜K˜HKšœœ
˜!šœœ
œ˜ Kšœ"œ˜1Kšœ"œ˜1K˜—šœœ
œ˜Kšœ"œ˜1K˜—K˜K˜—šŸ	œœ˜K˜K˜ K˜—šŸœœ˜K˜Kš
œ6˜6K˜—šŸœœ˜K˜!Kš
œZ˜ZK˜—šŸœœ˜K˜Kš
œ˜K˜—Kšœ
œ
œœœœ˜IKšΟcœ˜&K˜—K˜šŸ	œœœ
œ)˜GKšœœœ
˜K˜1Kšœœ
œ
œ
˜+K˜šœ@œœ
˜YKšŸ	œœ%˜4Kšœœ	œ
œ˜2Kšœœ
˜"Kšœ
˜—K˜K˜—K˜šŸ	œœœ
œ)˜GKšœœœ
˜Kš
œ9˜9Kšœœ
œ
œ
˜+K˜šœ@œœ
˜YKšŸ	œœ%˜4Kšœœ	œ
œ˜2Kšœœ
˜"Kšœ
˜—K˜K˜—K˜š
Ÿœœœ
œ
 œ3˜sKšœœœ
˜šŸœœœ
œ˜Kšœœ˜KšŸœœ$˜0Kšœœ	œ
œ˜2Kšœœ
˜K˜—K˜K˜K˜K˜K˜—K˜šŸ
œœœ
œ/˜QšŸœœ˜&Kšœœœ
˜šŸœœ˜1šŸœœ˜K˜>šœœ
˜˜Kš
œ˜K˜—˜K˜9K˜—Kšœœ
˜Kšœœ
˜—K˜—Kšœœ	œ
œ˜2Kšœœ
˜K˜—K˜Kšœ=œœ˜UK˜K˜—K˜|K˜K˜—K˜šŸ
œœœ
œ+˜JKš
œ˜˜6K˜/Kš
œ5˜5K˜>K˜—šœœ˜šŸœœ˜Kšœœœ
˜K˜0š
œ
Οg
Οd
œœ
œ˜,š
œ
‘
’
œœ
œ˜,šŸœœ˜Kšœ‘
’
œ
‘
’
œ˜3Kšœ(‘
’
œ‘
’
œ
˜;K˜—Kšœœ	œ
œ˜2Kšœœ
˜Kšœ
˜—Kšœ
˜—K˜K˜—Kšœœ˜#Kšœ
˜—K˜K˜—K˜šŸ
œœœ
œ6˜UKšœœœ
˜šŸœœœ
œœœœ œ˜aKšœœ˜Kšœœ˜šŸœœ˜Kš
œœœ
œ
œ)œ
œ
˜rK˜,K˜Kš
œ-˜-Kšœœ
œR˜cK˜—Kšœœ	œ
œ˜2Kšœœ
˜K˜—K˜Kš
œ ˜ K˜K˜—K˜š
Ÿœœ
œŸœœ˜NK•StartOfExpansionP -- [key: HashTable.Key, value: HashTable.Value] RETURNS [quit: BOOLEAN _ FALSE]š
Ÿœœœ
œ
œ˜:Kš
œ)˜)—K˜Kšœœ
œ˜9K˜šŸœœ
œ
Ÿœœœœ
œœ
œ˜ž
šœœœ
 ˜8Kš
œ˜K˜Kšœœ
˜—šœœœ
˜1šœœ	˜.K˜K˜šœœ˜K˜ K˜ Kšœœ
˜—Kšœœ
˜—K˜3K˜Kšœœ
œ
˜&Kšœœœ
œ˜Kšœœœ
 ˜2Kš
œ'˜'Kš
œ#˜#Kšœœ
˜—Kšœœ˜+Kšœ
˜—K˜—K˜šŸœœ
œ
Ÿœœœœ
œœ
œ˜ž
KšŸœœ7˜CKš
œ2˜2K˜—K˜šŸœœ
œ
Ÿœœœœ
œœ
œ˜ƒ
KšŸœœ1˜=Kš
œ+˜+K˜—K˜š
Ÿœœ
œ
Ÿœœ˜Yšœœ
˜˜šŸœœŸœœ˜=šŸ	œœ˜+šœœ
˜K˜&˜šŸ
œœ˜.šœœ
˜K˜&KšœMœœ˜eKšœœ
˜Kšœœ
˜—K˜—Kšœ9œœ˜QK˜—Kšœœ
˜Kšœœ
˜—K˜—Kš
œ/˜/šœœ
œ˜#Kšœœ(˜2šŸœœ˜*K˜$K˜—Kš
œ&˜&K˜—Kš
œ˜—K˜K˜—Kšœœ
˜˜KšŸ	œœH˜WKš
œ'˜'K˜—Kšœœ
˜—K˜—K˜š
Ÿœœ
œŸœœ˜VšŸœœ%˜/šœœ
˜Kš
œ%˜%KšœAœœ˜YKšœœ
˜Kšœœ
˜—K˜—Kš
œ"˜"K˜—K˜š
Ÿœœ
œŸœœ˜VKšŸœœ5˜AKš
œ˜K˜—K˜šŸœœ
œ3œ˜nKš
œ.˜.K˜—K˜šŸœœ
œ3œ˜qKšœœ
˜šŸœœ%˜2Kšœœ˜+K˜—Kšœ6œœ	˜TKš 
œ
˜K˜Kšœœœ
˜—K˜šŸœœ
œ œ˜ZKšœœ
˜šŸœœ˜$Kšœ
œœ
˜)K˜—Kš
œ0˜0Kš 
œ
˜K˜—K˜šŸœœ
œœ˜@KšŸœœ˜ Kšœ1œœ˜IK˜—K˜Kšœœœœ˜6Kšœœœœ˜@K˜šŸœœ
œ)œ˜_KšŸœœœœœ
œœ
œ˜NKšœ œ˜(—K˜šŸœœ
œ0˜IKšŸœœœœœ
œ
œ
œ˜IK˜2K˜2Kšœœ$˜FKšœ œ˜&šœœ
œ˜Kš	œœ œ
œ
œ˜8šœœœ
œœ˜)K˜Kšœ
œ
˜—Kš
œ&˜&Kš
œ˜—šœœ˜Kšœ
’
œœ˜Kšœ
’
œ’
œ˜(šœ’
œœ
˜Kšœ’
œ'˜9Kšœ
œ
˜Kšœœ
˜—Kšœ
˜—Kš
œ˜—K˜Kš	œ	œœ
œ
œ˜%K˜šŸœœ)Ÿœœœœ˜tKš
œ'˜'Kš
œ˜šœ˜
š
œ˜šœ
œœ˜Kšœœ˜
Kšœ
˜—šœ˜Kšœœœœ˜?Kšœœ˜Kšœœ˜#Kšœ
œ
œ
œ˜šœœœ
œœ˜)Kšœœ
˜*Kšœœ˜6Kšœ
œ
˜—Kšœœ
œœ	œ
œ
˜6Kš
œ˜K˜—K˜—Kšœœ
˜Kšœ	œ˜—K˜
šŸœœœœ˜2Kšœœ˜Kšœ
œ	œ˜#K˜—K˜2K˜2šœœ
˜šœœœ
˜Kš
œ*˜*Kš
œ4˜4Kšœœ
˜—šœ
œœ
˜ Kš
œ1˜1Kšœ
œ
˜Kšœœ
˜—Kšœœ
˜—K˜K˜—K˜šœœœ˜šœ	œ	˜K˜Kšœœ˜Kšœ˜	——K˜šŸœœœœ˜7Kšœœ˜5šœ
œ
˜Kšœ
œ˜!Kšœœ˜+Kšœœ˜,—K˜—K˜š
Ÿœœ
œŸœœ˜JšŸœœ!œ˜4K˜ Kš	œœœœ
œ
˜7Kšœœ
œ˜/K˜šœœ
˜Kšœ
œœœ
œœ
œ
œ˜ZKšœ!œ˜&Kš
œ˜Kšœœ˜%Kšœ
˜—Kš
œœœ
œ
œ˜6K˜—Kšœ=œ˜BKšœœ
œ
œ˜7K˜—K˜š
Ÿœœ
œŸœœ˜Všœ<œœ
˜PK˜Kšœ
˜—K˜—K˜š
Ÿœœ
œŸœœ˜Ošœ<œœ
˜QKš
œ
˜
Kšœ
˜—K˜—K˜š
Ÿœœ
œŸœœ˜ZK˜K˜K˜š	œœ
œœ
˜"Kš
œ*˜*K˜K˜Kšœ
˜—Kšœœ
œœ
œ
œ˜7K˜—K˜š
Ÿ	œœ
œœ	œ˜EK˜
Kšœ%œœœ
˜UK˜K˜—K˜š
Ÿœœ
œœœ˜IKšœ'œœœ
˜WK˜—K˜šŸœœ
œœ˜Fš
˜šœ
œ
˜Kšœœ˜K˜Kšœœ
˜—Kšœ
˜—K˜—K˜š
Ÿ	œœ
œœ	œ˜EK˜
Kšœ%œœœ
˜UK˜K˜—K˜š
Ÿœœ
œœœ˜IKšœ'œœœ
˜WK˜—K˜šŸœœ
œ˜-Kšœœ
œ
˜Kšœœ
˜Kš
œ*˜*K˜—K˜šŸœœ
œ˜,Kšœ
œœ
œ;˜[Kšœœ
œ
œ
˜K˜—K˜šŸ
œœ
œ˜-šœ
œœ˜Kš
œ˜Kšœ
œœ
œ
˜"K˜—K˜—K˜š
Ÿœœ
œœ	œ˜DKšœœ
œœ
˜3Kš
œ˜—K˜šŸ
œœ
œ˜0Kš \œ
˜aK˜—K˜šŸœœ
œœ˜CKšœœ˜šœ
œ
˜˜
Kšœœ
˜Kš
œ˜Kš
œ˜Kšœ
œ
œœ˜HK˜—˜Kšœœ
œ
œ
˜K˜Kšœœ
˜Kšœ(œ˜FKš
œ˜—Kšœœ
˜—K˜—K˜KšŸ
œœœœœœ	 œ
˜TK˜šŸœœ
œ=œœ!œ˜‹
Kš
œ*˜*Kšœ
œ˜)šŸœœ˜(Kšœœ4˜FKšœ&œœœ˜`K˜+Kšœœ˜2K˜—šŸœœ˜"K˜K˜&K˜—šœœ
œ˜ Kšœœ
œ
œ
˜,Kšœ
œ
œ
œ
˜Kš
œH˜HK˜—šœœ
œ˜Kšœœ˜>šœœœ
œœ˜)K˜Kšœ
œ
˜—Kš
œ1˜1K˜—K˜$K˜K˜—K˜šŸ
œœ
œ˜(šœ
œ
˜˜
Kšœ
œ
œœ˜QKšœ
œ
œœ˜RK˜—˜Kšœ
 =œ
˜DK˜—Kšœœ
˜—K˜—K˜š
Ÿœœ
œœœ˜IKšœ
œ˜+Kšœœœœ
˜Nšœœ˜-Kš
œ˜Kšœ
˜—K˜—K˜šŸœœ/˜=K˜šœ˜š
œ
˜
Kš	œœœ
œ/œ˜_Kš
œ˜—Kš
œ˜Kšœœ
˜—Kšœœœ
œœ
œ
˜NKš
œ˜Kšœœ
œœ˜BKšœœ
œœ˜AK˜—K˜š
Ÿœœ
œœœ˜Jšœœœ
˜.K˜!K˜Kšœœ˜!Kšœœ
˜—šŸ
œœœ˜5K˜Kšœœ
œ˜.Kšœœ˜+Kš
œ,˜,Kšœœ
œ
œ
˜Kš
œH˜HK˜—Kšœ)œ˜>Kš
œG˜GK˜—K˜šŸ
œœ
œ˜%šœœ˜,K˜|Kšœ
˜—K˜—K˜šŸ
œœ,œ˜`K˜Kšœœ
œ7œ˜wKšœœ
œ7œ˜wK˜—K˜šŸœœ
œ˜&K˜'K˜Kšœ
œœœ
œ/ œœ œ˜Ή
K˜—K˜šŸ
œœ
œ#˜:Kš
œ+˜+—K˜š
Ÿœœ
œ4œœ˜ošœœ˜ Kš
œ˜K˜
˜K˜Kšœœ
˜Kš
œ#˜#——Kš
œ˜Kšœœ
œ#œ˜`Kš
œ"˜"Kš
œF˜FKš
œ˜K˜—K˜šŸ
œœ
œ1œœœœ˜
Kšœœ
œ:˜Všœœ˜Kš
œ˜K˜
š
œ˜Kš
œ˜Kšœœ
˜
Kš
œœœ
œœ
˜BKš
œ˜——Kšœ
œ
œœ
œœ
œ˜cKšœœ
œœ-˜iKšœœ
œ˜%Kš
œ˜K˜—K˜šŸœœ˜#šœ<œ	œ
˜SKšœ%œ	˜1Kšœ
˜—K˜—K˜š
Ÿœœ
œ\œœ˜ž
Kšœœœ
œ˜/šœœ ˜1Kš
œ˜K˜
Kš
œ˜—Kš
œ˜Kš
œ˜K˜—K˜šŸœœ˜!K˜Kšœœ3˜GšŸœœ%˜2Kšœœœ%˜8šœ˜Kšœœœ
œ
˜-Kšœœ
˜
Kšœœ
˜—K˜—Kšœœ
œ
œ
˜Kš
œ?˜?K˜—K˜šŸœœ
œœ˜7K˜Kšœœ3˜Gšœœ
œ˜šœ˜Kšœœ
˜
Kšœœœ
œ
˜-Kšœœ
˜—Kš
œ˜—Kšœ%œ˜:K˜—K˜šŸœœ
œ˜)K˜Kšœœ3˜GšŸœœ%˜2Kšœœœ%˜8Kš
œ
œœœ
œ
˜,K˜—šŸœœ"˜.Kš
œ˜šœœ
˜Kšœœ
˜Kšœœœ˜DKšœœ
˜Kšœœ
˜—Kš
œ˜—Kš
œ#˜#šœœ
˜˜Kšœœ
œ0œ(˜yKšœœ
œ0œ)˜zKš
œ>˜>Kš
œ(˜(K˜—Kšœœ
˜š
œ˜Kšœ
œ
œœ%˜SKšœ
œ
œœ&˜TK˜—Kšœœ
˜—Kšœœ
œ@˜QK˜—K˜š
Ÿœœ
œœœ˜DKš
œ#˜#K˜—K˜šŸ	œœ
œ˜*šŸœœ#˜<šœ/œœ
˜HKš
œ˜šœœ
œ˜Kš
œ?˜?—šœ˜Kš
œr˜rKš
œ(˜(Kš
œ
˜
—Kšœ
˜—K˜—šœœ˜-K˜Kšœ"œœ˜:Kšœ œ
˜3K˜—Kš
œ˜K˜!K˜—K˜šŸœœ
œF˜fK˜Kš
œ˜Kš‘
’
œœ˜Kš‘
’
œœ˜Kšœœ
œ
œ
˜Kšœœ#œ
œ
˜EKšœœ"œ
œ
˜DKšœœ
œ
˜,š
œ
‘
’
œœ
œ‘
’
œ˜š
œ
‘
’
œœ
œ‘
’
œ˜Kšœ‘
’
œ‘
’
œ˜Kš
œ'˜'˜˜Kšœ
œ‘
’
œ‘
’
œ‘
’
œ˜2Kšœ2‘
’
œ‘
’
œ˜?—˜Kšœ
œ‘
’
œ‘
’
œ‘
’
œ˜2Kšœ2‘
’
œ‘
’
œ˜@——˜Kš
œœœœ‘
’
œ‘
’
œ˜DKš
œœœœ‘
’
œ‘
’
œ˜E—Kšœ
œ˜Kšœœ1˜:šŸ
œœ)˜9šœ˜&Kšœ"˜%Kšœœ
˜Kšœœ
˜—K˜—šŸœœ"œ˜YK˜K˜šœœ
œ˜Kšœ
œ
œ
˜Kš
œ˜K˜—Kšœœ˜)šœœ
œ˜Kšœ
œ
œ
˜Kšœœ˜(Kš
œ(˜(š	œ’
œœ
œ˜.Kš	œ’
œœ’
œ
œ'˜8š	œ’
œœ
œ˜.Kšœœ’
œ’
œ
˜+Kšœœ’
œ
œ’
œ
œ(˜EKšœ
˜—Kšœ
˜—Kš
œ˜K˜
—šœ˜š	œ’
œœ
œ'˜7š	œ’
œœ
œ'˜7Kšœœ’
œ’
œ
˜+Kšœ
œ'˜7Kšœœ
˜Kšœ
˜—Kšœ
˜—K˜—Kšœœœ˜;K˜—K˜+Kš
œ+˜+Kš
œJ˜JKš
œM˜MKšœ
œ
˜——K˜—K˜šŸ	œœ
œœ˜3K˜H—K˜š
Ÿœœœœœ˜6Kšœ
œ
œ
˜Kšœ	œ˜$K˜K˜—K˜š
Ÿœœœœœ˜5Kšœ
œ
œ
˜Kšœ	œ˜$K˜K˜—K˜šŸœœ
œœœ
œœ˜Cš
˜Kšœœ
œ@˜QKšœTœ
œœœœ˜
Kšœ
˜Kšœ
˜—K˜Kšœœ
œœ
˜—K˜Kšœ
˜——…—}Ξ§€