LichenDataImpl.Mesa
Last tweaked by Mike Spreitzer on August 28, 1987 11:45:37 am PDT
DIRECTORY AMBridge, Asserting, Basics, Convert, InterpreterOps, IO, LichenArrayStuff, LichenCollections, LichenDataOps, LichenDataStructure, LichenPairCollections, LichenPrinting, List, Rope, RopeHash, StructuredStreams, SymTab, UnparserBuffer, ViewerIO;
LichenDataImpl:
CEDAR
PROGRAM
IMPORTS Asserting, IO, LichenArrayStuff, LichenCollections, LichenDataStructure, LichenPairCollections, LichenPrinting, List, Rope, RopeHash, StructuredStreams, UnparserBuffer, ViewerIO
EXPORTS LichenDataStructure, LichenDataOps
=
BEGIN OPEN LichenDataStructure, LichenArrayStuff, Colls:LichenCollections, PairColls:LichenPairCollections, 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;
partsByNameKey: PUBLIC ATOM ← $LichenNameToPart;
Escape: ERROR = CODE;
nameStepSpace:
PUBLIC Colls.Space ←
NEW [Colls.SpacePrivate ← [
Equal: StepEqual,
Hash: StepHash,
Compare: StepCompare,
other: List.PutAssoc[key: $Name, val: "name steps", aList: NIL]
]];
StepEqual:
PROC [data:
REF
ANY, elt1, elt2: Colls.Value]
RETURNS [
BOOL] ~ {
WITH elt1
SELECT
FROM
x:
REF
INT =>
WITH elt2
SELECT
FROM
y: REF INT => RETURN [x^ = y^];
y: ROPE => RETURN [FALSE];
ENDCASE => ERROR;
x:
ROPE =>
WITH elt2
SELECT
FROM
y: REF INT => RETURN [FALSE];
y: ROPE => RETURN [x.Equal[y]];
ENDCASE => ERROR;
ENDCASE => ERROR;
};
StepHash:
PROC [data:
REF
ANY, elt: Colls.Value]
RETURNS [
CARDINAL] ~ {
WITH elt
SELECT
FROM
x: REF INT => RETURN Colls.HashIntI[x^];
x: ROPE => RETURN [RopeHash.FromRope[rope: x]];
ENDCASE => ERROR;
};
StepCompare:
PROC [data:
REF
ANY, elt1, elt2: Colls.Value]
RETURNS [Basics.Comparison] ~ {
WITH elt1
SELECT
FROM
x:
REF
INT =>
WITH elt2
SELECT
FROM
y: REF INT => RETURN [Colls.CompareIntI[x^, y^]];
y: ROPE => RETURN [less];
ENDCASE => ERROR;
x:
ROPE =>
WITH elt2
SELECT
FROM
y: REF INT => RETURN [greater];
y: ROPE => RETURN [x.Compare[y]];
ENDCASE => ERROR;
ENDCASE => ERROR;
};
steppyNameSpace:
PUBLIC Colls.Space ←
NEW [Colls.SpacePrivate ← [
Equal: EqualSteppyNames,
Hash: HashSteppyName,
Compare: CompareSteppyNames,
other: List.PutAssoc[$Name, "steppy names", NIL],
data: NIL]];
EqualSteppyNames:
PROC [data:
REF
ANY, elt1, elt2:
REF
ANY]
RETURNS [
BOOL] ~ {
n1: SteppyName ~ NARROW[elt1];
n2: SteppyName ~ NARROW[elt2];
RETURN SteppyNameEqual[n1, n2]};
SteppyNameEqual:
PUBLIC
PROC [n1, n2: SteppyName, clip1, clip2: SteppyName ←
NIL]
RETURNS [
BOOL] ~ {
WHILE n1#clip1
AND n2#clip2
DO
WITH n1.first
SELECT
FROM
x:
ROPE =>
WITH n2.first
SELECT
FROM
y: ROPE => IF NOT x.Equal[y] THEN RETURN [FALSE];
y: REF INT => RETURN [FALSE];
ENDCASE => ERROR;
x:
REF
INT =>
WITH n2.first
SELECT
FROM
y: ROPE => RETURN [FALSE];
y: REF INT => IF x^#y^ THEN RETURN [FALSE];
ENDCASE => ERROR;
ENDCASE => ERROR;
n1 ← n1.rest;
n2 ← n2.rest;
ENDLOOP;
RETURN [(n1=clip1) = (n2=clip2)]};
HashSteppyName:
PROC [data:
REF
ANY, elt:
REF
ANY]
RETURNS [hash:
CARDINAL ← 0] ~ {
n: SteppyName ← NARROW[elt];
FOR n ← n, n.rest
WHILE n#
NIL
DO
hash ← hash + (
WITH n.first
SELECT
FROM
x: ROPE => RopeHash.FromRope[x],
x: REF INT => Colls.HashIntI[x^],
ENDCASE => ERROR);
ENDLOOP;
RETURN};
CompareSteppyNames:
PROC [data:
REF
ANY, elt1, elt2:
REF
ANY]
RETURNS [Basics.Comparison] ~ {
n1: SteppyName ~ NARROW[elt1];
n2: SteppyName ~ NARROW[elt2];
len1, len2: NATURAL;
gend1, gend2, glob1, glob2: BOOL;
last1, last2: ROPE;
[len1, gend1, glob1, last1] ← Grade[n1];
[len2, gend2, glob2, last2] ← Grade[n2];
RETURN [
SELECT
TRUE
FROM
glob1<glob2 => less,
glob1>glob2 => greater,
gend1<gend2 => less,
gend1>gend2 => greater,
len1<len2 => less,
len1>len2 => greater,
ENDCASE =>
SELECT last2.Length[]-last1.Length[]
FROM
>0 => less,
<0 => greater,
ENDCASE => last1.Compare[last2]];
};
Grade:
PROC [name: SteppyName]
RETURNS [length:
NATURAL ← 0, gend, glob:
BOOL ←
TRUE, last:
ROPE ←
NIL] ~ {
FOR name ← name, name.rest
WHILE name#
NIL
DO
length ← length+1;
WITH name.first
SELECT
FROM
x:
ROPE => {
xLen: INT ~ x.Length;
last ← x;
gend ← FALSE;
IF x.Fetch[xLen-1]='!
THEN glob ←
TRUE
ELSE {
FOR i:
INT
IN [0 .. xLen)
DO
SELECT x.Fetch[i]
FROM
IN ['a .. 'z], IN ['A .. 'Z], IN ['0 .. '9], '←, '-, '', '~ => NULL;
ENDCASE => {gend ← TRUE; EXIT};
ENDLOOP;
};
};
x: REF INT => NULL;
ENDCASE => ERROR;
ENDLOOP;
IF length=0 THEN length ← NATURAL.LAST;
RETURN};
listClass: PUBLIC Colls.CollectionClass ← Colls.CreateList[vals: NIL, space: steppyNameSpace, mayDuplicate: FALSE, orderStyle: value].class;
CreateSteppyNames:
PUBLIC
PROC [names:
LORA
--actually LIST OF SteppyName-- ←
NIL]
RETURNS [ListData] ~ {
set: Set ~ Colls.CreateList[vals: names, space: steppyNameSpace, mayDuplicate: FALSE, orderStyle: value];
IF set.class#listClass THEN ERROR;
RETURN [set.data]};
endOfQ: PUBLIC Vertex ← NEW [VertexPrivate.intermediate];
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;
RETURN};
SubWire:
PUBLIC
PROC [parent: Wire, index:
INT]
RETURNS [child: Wire] = {
FOR child ← parent.firstChild, child.next WHILE index > 0 DO index ← index - 1 ENDLOOP;
RETURN};
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;
RETURN};
SubPort:
PUBLIC
PROC [parent: Port, index:
INT]
RETURNS [child: Port] = {
FOR child ← parent.firstChild, child.next WHILE index > 0 DO index ← index - 1 ENDLOOP;
RETURN};
portToInternalWire: PUBLIC UWFunction ~ PairColls.FnFromProc[MapPortToInternalWire].AsUW;
MapPortToInternalWire:
PROC [data:
REF
ANY, v: Colls.Value]
RETURNS [Colls.MaybeValue] ~ {
port: Port ~ NARROW[v];
RETURN [[port.wire#NIL, port.wire]];
};
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;
IF (port.names=NIL OR port.PortNames.Size=0) AND port.wire#NIL THEN port.names ← port.wire.VertexNames.Copy.data;
};
ct: CellType => {
IF ct.port # NIL THEN ERROR;
ct.port ← port;
port.next ← port.prev ← NIL;
IF port.names=NIL THEN port.names ← CreateSteppyNames[];
[] ← port.PortNames.AddElt[LIST[BeRope["PORTS"]]];
};
ENDCASE => ERROR;
};
ActualName:
PROC [instanceName, portName: SteppyName]
RETURNS [actualName: SteppyName] ~ {
lastRope: ROPE ← NIL;
FOR l: SteppyName ← portName, l.rest
WHILE l#
NIL
DO
WITH l.first
SELECT
FROM
x: ROPE => lastRope ← x;
x: REF INT => NULL;
ENDCASE => ERROR;
ENDLOOP;
IF lastRope.Fetch[lastRope.Length-1]='! THEN RETURN [portName];
actualName ← List.Append[instanceName, portName];
RETURN};
FullyAddPort:
PUBLIC
PROC [p: PortPrivate ← [], andReportConnectionTo: CellInstance ←
NIL]
RETURNS [port: Port, connection: Wire ←
NIL] = {
ct: CellType = PortCCT[port ← AddPort[p]];
portName: SteppyName ~ SteppyDescribe[port, ct.port];
FixInstance:
PROC [ci: CellInstance] = {
instanceName: SteppyName ~ SteppyDescribe[ci, ci.containingCT];
wireName: SteppyName ~ ActualName[instanceName, portName];
w: Wire = CreateWire[ci.containingCT, NIL, CreateSteppyNames[LIST[wireName]]];
AddEdge[[cellward: ci, wireward: w], port];
IF andReportConnectionTo = ci THEN connection ← w;
};
FixArray: PROC [act: CellType] ~ {MakeGroupsForPort[act.asArray, port]};
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 {
NULL--we don't need to do anything--;
};
EnumerateInstances[ct, FixInstance, FALSE];
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];
port ← port;
ENDLOOP;
RETURN};
LinkEdge:
PROC [v: Vertex, e: Edge, side: GraphDirection] = {
prev, next: Edge;
prevSide: GraphDirection;
SELECT side
FROM
--we have to choose position carefully to satisfy AI1
cellward => {
IF e.port.prev #
NIL
THEN {
prev ← FindImmediateEdge[v, e.port.prev, backward].e;
IF prev=NIL THEN ERROR--we only implement AddEdge in increasing port order--;
IF prev.sides[prevSide ← cellward].v#v THEN ERROR Error["Broken"];
}
ELSE IF v.firstEdge=NIL OR v.firstEdge.sides[cellward].v=v THEN prev ← NIL
ELSE {
FOR prev ← v.lastEdge, prev.sides[cellward].prev
UNTIL prev.sides[wireward].v=v
DO
IF prev.sides[cellward].v#v THEN ERROR Error["Broken"];
ENDLOOP;
prevSide ← wireward};
};
wireward => prev ← NIL;
ENDCASE => ERROR;
e.sides[side].next ← next ← IF prev # NIL THEN prev.sides[prevSide].next ELSE v.firstEdge;
e.sides[side].prev ← prev;
IF prev=NIL THEN v.firstEdge ← e ELSE prev.sides[prevSide].next ← e;
IF next=NIL THEN v.lastEdge ← e ELSE next.sides[next.SideFor[v]].prev ← e;
RETURN};
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, port.PortNames.Copy.data];
RETURN};
immediatelyCellward: Vertex = FindVertex[NARROW[port.parent]];
AddEdge[[cellward: immediatelyCellward, wireward: vs[wireward]], port];
RETURN};
RemoveEdge:
PUBLIC
PROC [e: Edge] = {
e ← e;
FOR dir: GraphDirection
IN GraphDirection
DO
next: Edge ~ e.sides[dir].next;
prev: Edge ~ e.sides[dir].prev;
v: Vertex ~ e.sides[dir].v;
IF next#NIL THEN next.sides[SideFor[next, v]].prev ← prev ELSE v.lastEdge ← prev;
IF prev#NIL THEN prev.sides[SideFor[prev, v]].next ← next ELSE v.firstEdge ← next;
ENDLOOP;
RETURN};
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 DeleteVertex[cellward];
RETURN};
UnlinkPort:
PUBLIC
PROC [ci: CellInstance, port: Port] = {
RemoveEdge[FindImmediateEdge[ci, port].e]; RETURN};
UnlinkPorts:
PUBLIC
PROC [ci: CellInstance, ports: ConstSet
--of Port--] ~ {
n: NATURAL ~ ports.Size[];
i: NATURAL ← 0;
Work:
PROC [port: Port, v: Vertex, e: Edge] ~ {
IF port=NIL THEN ERROR;
IF ports.HasMember[port]
THEN {
RemoveEdges[e];
i ← i + 1;
IF i=n THEN Escape;
}
ELSE
SELECT v.class
FROM
cell => ERROR;
intermediate => EnumerateImmediateEdges[v, Work, [cellward: FALSE, wireward: TRUE]];
wire => NULL;
ENDCASE => ERROR;
RETURN};
EnumerateImmediateEdges[ci, Work !Escape => CONTINUE];
IF i#n THEN ERROR;
RETURN};
Instantiate:
PUBLIC
PROC [type, containingCT: CellType, names: ListData ←
NIL, other: Assertions ←
NIL]
RETURNS [ci: CellInstance] = {
IF names=NIL THEN names ← CreateSteppyNames[];
ci ←
NEW [VertexPrivate.cell ← [
containingCT: containingCT,
names: names,
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.AddElt[ci];
IndexVertexNames[ci];
RETURN};
EnumeratePortsForWire:
PUBLIC
PROC [w: Wire,
Consume:
PROC [Port]]= {
See:
PROC [p: Port, v: Vertex] = {
IF IsMirror[NARROW[v]] THEN Consume[p];
RETURN};
w.EnumerateTransitiveConnections[See];
w ← w;
RETURN};
EnumerateParts:
PUBLIC
PROC [ct: CellType,
Consume:
PROC [Vertex], mirrorToo:
BOOL] ~ {
u: Unorganized ~ ct.asUnorganized;
PerCell:
PROC [ra:
REF
ANY] ~ {
ci: CellInstance ~ NARROW[ra];
PassIMs:
PROC [p: Port, v: Vertex] ~ {
WITH v
SELECT
FROM
ci: CellInstance => ERROR;
w: Wire => NULL;
im: Intermediary => {
Consume[im];
EnumerateImmediateConnections[im, PassIMs, [cellward: FALSE, wireward: TRUE]];
};
ENDCASE => ERROR;
RETURN};
Consume[ci];
EnumerateImmediateConnections[ci, PassIMs];
RETURN};
PassChildren:
PROC [w: Wire] ~ {
FOR w ← FirstChildWire[w], NextChildWire[w]
WHILE w #
NIL
DO
Consume[w];
PassChildren[w];
ENDLOOP;
RETURN};
IF u=NIL THEN ERROR;
PassChildren[u.internalWire];
u.containedInstances.Enumerate[PerCell];
IF mirrorToo THEN PerCell[u.mirror];
RETURN};
PortForWire:
PUBLIC
PROC [ct: CellType, internal: Wire, ci: CellInstance, mayAdd:
BOOL]
RETURNS [port: Port, external: Wire] = {
See:
PROC [p: Port, v: Vertex] = {
IF IsMirror[NARROW[v]] THEN port ← p;
RETURN};
IF internal.containingCT # ct THEN ERROR;
internal.EnumerateTransitiveConnections[See];
IF port =
NIL
THEN {
IF mayAdd
THEN {
[port, external] ← FullyAddPort[
[parent: ct.port, wire: internal, names: CreateSteppyNames[LIST[SteppyDescribe[internal, ct.asUnorganized.internalWire]]]],
ci
];
};
}
ELSE IF ci # NIL THEN external ← FindTransitiveConnection[ci, port];
RETURN};
FullyInstantiate:
PUBLIC
PROC [type, containingCT: CellType, names: ListData ←
NIL, other: Assertions ←
NIL]
RETURNS [ci: CellInstance] ~ {
ci ← Instantiate[type, containingCT, names, other];
{instanceName: SteppyName ~ SteppyDescribe[ci, ci.containingCT];
FOR port: Port ← type.port.FirstChildPort[], port.NextChildPort[]
WHILE port #
NIL
DO
portName: SteppyName ~ SteppyDescribe[port, type.port];
wireName: SteppyName ~ ActualName[instanceName, portName];
w: Wire = CreateWire[ci.containingCT, NIL, CreateSteppyNames[LIST[wireName]]];
AddEdge[[cellward: ci, wireward: w], port];
ENDLOOP;
ci ← ci;
RETURN}};
CreateWire:
PUBLIC
PROC [containingCT: CellType, containingWire: Wire ←
NIL, names: ListData ←
NIL, other: Assertions ←
NIL, copy: Wire ←
NIL]
RETURNS [w: Wire] = {
IF containingWire=NIL THEN containingWire ← containingCT.asUnorganized.internalWire;
IF names=NIL THEN names ← CreateSteppyNames[];
w ←
NEW [VertexPrivate.wire ← [
containingCT: containingCT,
names: names,
other: other,
variant: wire[
containingWire: containingWire,
next: NIL,
prev: IF containingWire#NIL THEN containingWire.lastChild ELSE NIL
]]];
IF w.containingWire=NIL THEN [] ← w.VertexNames.AddElt[LIST[internalWireName]];
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];
IndexVertexNames[w];
RETURN};
internalWireName: ROPE ~ "INTERNAL";
WireCopy:
PROC [from, to: Wire] = {
IF to.VertexNames.Size[]=0 THEN to.names ← from.VertexNames.Copy.data;
FOR child: Wire ← from.FirstChildWire[], child.NextChildWire[]
WHILE child #
NIL
DO
[] ← CreateWire[containingCT: to.containingCT, containingWire: to, copy: child];
ENDLOOP;
RETURN};
CreateIntermediary:
PUBLIC
PROC [from: Vertex, go: GraphDirection, containingCT: CellType, port: Port, names: ListData ←
NIL, other: Assertions ←
NIL]
RETURNS [im: Intermediary] = {
vs: ARRAY GraphDirection OF Vertex ← ALL[from];
IF names=NIL THEN names ← CreateSteppyNames[];
vs[go] ← im ←
NEW [VertexPrivate.intermediate ← [
containingCT: containingCT,
names: names,
other: other,
variant: intermediate[port]]];
AddEdge[vs, port];
IndexVertexNames[im];
RETURN};
IndexVertexNames:
PUBLIC
PROC [v: Vertex, names: Set ← Colls.nilColl] = {
ct: CellType = v.containingCT;
pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
top:
BOOL ~
WITH v
SELECT
FROM
x: CellInstance => TRUE,
x: Intermediary => FALSE,
x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
ENDCASE => ERROR;
PerName:
PROC [val:
REF
ANY] ~ {
name: SteppyName ~ NARROW[val];
SELECT pbn.Apply[name].val
FROM
Colls.noValue => IF NOT pbn.Store[[name, v]] THEN ERROR;
v => NULL;
ENDCASE => ERROR;
};
IF pbn=PairColls.nilPairColl OR NOT top THEN RETURN;
IF names=Colls.nilColl THEN names ← v.VertexNames;
names.Enumerate[PerName];
RETURN};
UnindexVertexNames:
PUBLIC
PROC [v: Vertex] = {
ct: CellType = v.containingCT;
pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
top:
BOOL ~
WITH v
SELECT
FROM
x: CellInstance => TRUE,
x: Intermediary => FALSE,
x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
ENDCASE => ERROR;
PerName:
PROC [val:
REF
ANY] ~ {
name: SteppyName ~ NARROW[val];
SELECT pbn.Apply[name].val
FROM
Colls.noValue => NULL;
v => IF NOT pbn.Delete[name] THEN ERROR;
ENDCASE => ERROR;
};
IF pbn=PairColls.nilPairColl OR NOT top THEN RETURN;
v.VertexNames.Enumerate[PerName];
RETURN};
CreateCellType:
PUBLIC
PROC [design: Design, cellTypeName:
ROPE, class: CellClass, internals:
BOOL, otherPublic, otherPrivate: Assertions ←
NIL]
RETURNS [ct: CellType] = {
pbn: VarFunction = PairColls.CreateHashFn[[steppyNameSpace, Colls.refs]];
ct ←
NEW [CellTypePrivate ← [
class: class,
designs: Colls.CreateHashSet[],
publicKnown: TRUE,
privateKnown: TRUE,
otherPublic: otherPublic,
otherPrivate: otherPrivate
]];
IF cellTypeName#NIL THEN ct.otherPublic ← Asserting.Assert1[nameReln, cellTypeName, ct.otherPublic];
[] ← AddPort[[parent: ct]];
IF internals
THEN {
iw: Wire;
ct.otherPrivate ← Asserting.AssertFn1[partsByNameKey, pbn.Refify, ct.otherPrivate];
ct.asUnorganized ←
NEW [UnorganizedPrivate ← [
containedInstances: Colls.CreateHashSet[]
]];
iw ← CreateWire[ct];
IF ct.asUnorganized.internalWire # iw THEN ERROR;
AddMirror[ct];
};
[] ← design.cellTypes.AddElt[ct];
[] ← ct.designs.AddElt[design];
};
CreateArray:
PUBLIC
PROC [design: Design, cellTypeName:
ROPE, class: CellClass, eltType: CellType, size, jointsPeriod: Size2, borders:
ARRAY Dim
OF
ARRAY End
OF
NAT, otherPublic, otherPrivate: Assertions ←
NIL]
RETURNS [ct: CellType] = {
nj: INT = jointsPeriod[Foo] * jointsPeriod[Bar];
gps: GroupingParmses = [
Foo: ComputeGroupingParms[size[Foo], jointsPeriod[Foo], borders[Foo]],
Bar: ComputeGroupingParms[size[Bar], jointsPeriod[Bar], borders[Bar]]];
middlea: Range2 = [gps[Foo].middle, gps[Bar].middle];
ngi: NAT = gps[Foo].sum * gps[Bar].sum;
a: Array =
NEW [ArrayPrivate ← [
eltType: eltType,
prevArray: eltType.lastArray,
nextArray: NIL,
size: size,
jointsPeriod: jointsPeriod,
groupingParmses: gps,
groupingses: CreateRefSeq[ngi],
toRole: [[CreateRefTable[], CreateRefTable[]], [CreateRefTable[], CreateRefTable[]]],
roles: [CreateVarRefSeq[], CreateVarRefSeq[]],
joints: [CreateRefSeq[nj], CreateRefSeq[nj]],
toWire: CreateRefTable[],
wires: Colls.CreateHashSet[],
portWire: CreateRefTable[]
]];
tf: INT = a.jointsPeriod[Foo];
tb: INT = a.jointsPeriod[Bar];
ct ← CreateCellType[design, cellTypeName, class, FALSE, otherPublic, otherPrivate];
ct.asArray ← a;
IF a.prevArray # NIL THEN a.prevArray.asArray.nextArray ← ct ELSE eltType.firstArray ← ct;
eltType.lastArray ← ct;
eltType.useCount ← eltType.useCount + 1;
FOR gi:
NAT
IN [0 .. ngi)
DO
a.groupingses[gi] ←
NEW [GroupingsPrivate ← [
toGroup: CreateRefTable[],
groups: Colls.CreateHashSet[]
]];
ENDLOOP;
FOR d: Dim
IN Dim
DO
FOR
f
f:
INT
IN [0 ..
t
f)
DO
FOR
f
b:
INT
IN [0 ..
t
b)
DO
phase2: Nat2 = [ff, fb];
rawLair: Range2 =
SELECT d
FROM
Foo => [[0, a.size[Foo]-1], [0, a.size[Bar]-0]],
Bar => [[0, a.size[Foo]-0], [0, a.size[Bar]-1]],
ENDCASE => ERROR;
jiir: Range2 = Range2Div[r: rawLair, t: jointsPeriod, f: phase2];
size2: Size2 = RangeShape[jiir];
i: INT = ArrayJointIndex[a, phase2];
middlej: Range2 = Range2Div[r: ShaveRange2Top1[middlea, d], t: jointsPeriod, f: phase2];
jgps: GroupingParmses = [
Foo: ComputeJGP[jiir[Foo], middlej[Foo]],
Bar: ComputeJGP[jiir[Bar], middlej[Bar]]];
njgi: NAT = jgps[Foo].sum * jgps[Bar].sum;
j: Joint = a.joints[d][i] ←
NEW [JointPrivate ← [
size2: size2,
size: size2[Foo]*size2[Bar],
groupingParmses: jgps,
ties: CreateRefSeq[njgi],
toTie: [CreateRefSeq[njgi], CreateRefSeq[njgi]]
]];
FOR jgi:
NAT
IN [0 .. njgi)
DO
j.ties[jgi] ← Colls.CreateHashSet[].Refify;
j.toTie[low][jgi] ← CreateRefTable[];
j.toTie[high][jgi] ← CreateRefTable[];
ENDLOOP;
design ← design;
ENDLOOP ENDLOOP ENDLOOP;
};
ComputeGroupingParms:
PROC [size, jointsPeriod:
NAT, borders:
ARRAY End
OF
NAT]
RETURNS [gp: GroupingParms] = {
peculiar: NAT = borders[low] + borders[high];
IF peculiar >= size
THEN
RETURN [[
middle: [size, size],
firstHigh: size,
sum: size,
d: 0]];
{firstHighGI: NAT = borders[low] + jointsPeriod;
firstHighI: NAT = size - borders[high];
gp ← [
middle: [borders[low], firstHighI],
firstHigh: firstHighGI,
sum: peculiar + jointsPeriod,
d: firstHighGI - firstHighI];
RETURN [gp];
}};
ComputeJGP:
PROC [jiir, middle: Range]
RETURNS [gp: GroupingParms] = {
hasMiddle: BOOL = middle.maxPlusOne > middle.min;
nMid: NAT = IF hasMiddle THEN 1 ELSE 0;
nHigh: NAT = jiir.maxPlusOne - middle.maxPlusOne;
nLow: NAT = middle.min - jiir.min;
peculiar: NAT = nLow + nHigh;
firstHigh: NAT = nLow + nMid;
IF jiir.min # 0 THEN ERROR;
gp ← [
middle: middle,
firstHigh: firstHigh,
sum: peculiar + nMid,
d: firstHigh - middle.maxPlusOne
];
RETURN [gp];
};
KnowVertexName:
PUBLIC
PROC [v: Vertex, name: SteppyName] = {
ct: CellType = v.containingCT;
pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
top:
BOOL ~
WITH v
SELECT
FROM
x: CellInstance => TRUE,
x: Intermediary => FALSE,
x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
ENDCASE => ERROR;
IF top
AND pbn#PairColls.nilPairColl
THEN {
SELECT pbn.Apply[name].val
FROM
v => RETURN;
Colls.noValue => IF NOT pbn.Store[[name, v]] THEN ERROR;
ENDCASE => ERROR;
};
IF NOT v.VertexNames.AddElt[name] THEN ERROR;
RETURN};
ForgetVertexName:
PUBLIC
PROC [v: Vertex, name: SteppyName] = {
ct: CellType = v.containingCT;
pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
last: Assertions ← NIL;
next: Assertions ← v.other;
top:
BOOL ~
WITH v
SELECT
FROM
x: CellInstance => TRUE,
x: Intermediary => FALSE,
x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
ENDCASE => ERROR;
IF top
AND pbn#PairColls.nilPairColl
THEN {
IF NOT pbn.Delete[name] THEN ERROR;
};
IF NOT v.VertexNames.RemoveElt[name] THEN ERROR;
RETURN};
DeleteVertex:
PUBLIC
PROC [v: Vertex] = {
ct: CellType = v.containingCT;
Killit:
PROC [p: Port, w: Vertex, e: Edge] = {
dir: GraphDirection ~ e.SideFor[w];
IF dir=cellward THEN RemoveEdges[e] ELSE RemoveEdge[e];
WITH w
SELECT
FROM
ci: CellInstance => NULL;
im: Intermediary => IF dir=wireward THEN DeleteVertex[w];
wire: Wire => NULL;
ENDCASE => ERROR;
};
UnindexVertexNames[v];
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;
IF NOT v.containingCT.asUnorganized.containedInstances.RemoveElt[ci] THEN ERROR;
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;
RETURN};
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, subPort.PortNames.Copy.data];
CreateMirrorBinding[subPort, subVertex];
}
ENDLOOP;
};
v: CellInstance =
NEW [VertexPrivate.cell ← [
containingCT: lct,
names: CreateSteppyNames[LIST[LIST[BeRope["mirror"]]]],
variant: cell[type: lct--AM2 says not to link it--]
]];
lct.asUnorganized.mirror ← v;
CreateMirrorBinding[lct.port, v];
};
VarRefSeqAppend:
PUBLIC
PROC [vrs: VarRefSeq, value:
REF
ANY] = {
IF vrs.length = vrs.refs.length
THEN {
oldRefs: RefSeq = vrs.refs;
vrs.refs ← CreateRefSeq[MAX[oldRefs.length*2, 1]];
FOR i:
INT
IN [0 .. oldRefs.length)
DO
vrs.refs[i] ← oldRefs[i];
ENDLOOP;
};
vrs.refs[vrs.length] ← value;
vrs.length ← vrs.length + 1;
};
FloorDiv:
PUBLIC
PROC [num, den:
INT]
RETURNS [quot:
INT] = {
IF den < 0 THEN {den ← -den; num ← -num};
IF num < 0 THEN num ← num - (den-1);
quot ← num/den;
};
CeilDiv:
PUBLIC
PROC [num, den:
INT]
RETURNS [quot:
INT] = {
IF den < 0 THEN {den ← -den; num ← -num};
IF num > 0 THEN num ← num + (den-1);
quot ← num/den;
};
Choose2:
PROC [n:
INT]
RETURNS [nChoose2:
INT] =
INLINE {
nChoose2 ← n*(n-1)/2};
PrintOnLog:
PUBLIC
PROC [ra:
REF
ANY] ~ {
OPEN LichenPrinting;
DO
ENABLE IO.Error => IF ec=StreamClosed THEN {log ← NIL; LOOP};
IF log = NIL THEN log ← ViewerIO.CreateViewerStreams["Lichen Debugging Log"].out;
{slog: IO.STREAM ~ SS.Create[UB.NewInittedHandle[[output: [stream[log]], margin: printWidth]]];
WITH ra
SELECT
FROM
x: Design => PrintDesign[slog, x];
x: CellType => PrintCellType[slog, x];
x: Port => PrintPort[slog, x];
x: Wire => PrintWire[slog, x];
x: CellInstance => PrintInstance[slog, x];
ENDCASE => ERROR;
slog.PutRope["\n"];
slog.Close[];
EXIT;
}ENDLOOP;
RETURN};
printWidth: INT ← 69;
Log:
PUBLIC
PROC [fmt:
ROPE, args:
LORA ←
NIL] = {
head, tail, this: LIST OF IO.Value ← NIL;
FOR args ← args, args.rest
WHILE args#
NIL
DO
this ←
WITH args.first
SELECT
FROM
x: Design => LIST[[rope[Describe[x]]]],
x: CellType => LIST[[rope[Describe[x]]]],
x: Vertex => LIST[[rope[Describe[x]]]],
x: Port => LIST[[rope[Describe[x]]]],
x: PortList => LIST[[rope[FmtPortList[x]]]],
x: ROPE => LIST[[rope[x]]],
ENDCASE => LIST[[refAny[args.first]]];
IF tail=NIL THEN head ← this ELSE tail.rest ← this;
tail ← this;
ENDLOOP;
DO
ENABLE IO.Error => IF ec=StreamClosed THEN {log ← NIL; LOOP};
IF log = NIL THEN log ← ViewerIO.CreateViewerStreams["Lichen Debugging Log"].out;
log.PutFL[fmt, head];
EXIT;
ENDLOOP;
RETURN};
log: IO.STREAM ← NIL;
FmtPortList:
PROC [pl: PortList]
RETURNS [asRope:
ROPE] ~ {
asRope ← NIL;
FOR pl ← pl, pl.rest
WHILE pl#
NIL
DO
IF asRope#NIL THEN asRope ← asRope.Concat[", "];
asRope ← asRope.Concat[Describe[pl.first]];
ENDLOOP;
asRope ← Rope.Cat["{", asRope, "}"];
RETURN};
NewInt:
PUBLIC
PROC [i:
INT]
RETURNS [
REF
INT] ~ {
IF i IN [0 .. 64] THEN RETURN [intRefs[i]];
RETURN [NEW [INT ← i]]};
IntRefArray: TYPE ~ ARRAY [0 .. 64] OF REF INT;
intRefs: REF IntRefArray ~ NEW [IntRefArray ← ALL[NIL]];
Start:
PROC ~ {
FOR i: INT IN [0 .. 64] DO intRefs[i] ← NEW [INT ← i] ENDLOOP;
RETURN};
Start[];
END.