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 less, glob1>glob2 => greater, gend1 less, gend1>gend2 => greater, len1 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 ff: INT IN [0 .. tf) DO FOR fb: INT IN [0 .. tb) 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. \LichenDataImpl.Mesa Last tweaked by Mike Spreitzer on August 28, 1987 11:45:37 am PDT Κ&z˜™IcodešœA™A—J˜KšΟk œ7œΌ˜ώK˜šΡbnxœœ˜Kšœ œ€˜ΉKšœ#˜*Kšœ˜—K˜Kš œœ(ΟnœŸ œœœ˜”K˜Kšœœœœ˜KšŸœœœœœœœœœ˜SKšŸœœœœœœœœ˜JK˜Kšœ œœ˜$Kšœœœ˜0K˜KšŸœœœ˜K˜šœœœ˜?KšŸœ ˜KšŸœ ˜KšŸœ˜K•StartOfExpansion5[key: REF ANY, val: REF ANY, aList: List.AList]šœ;œ˜?Kšœ˜—K˜š Ÿ œœœœœœ˜Kšœœ˜š œœœœœ˜#Kšœœœœ ˜Kšœœœœ˜Kšœœ˜—šœœœœ˜ Kš œœœœœ˜Kšœœœ˜Kšœœ˜—Kšœœ˜—K˜—K˜š Ÿœœœœœœ˜Gšœœ˜Kšœœœœ˜(K–q[rope: ROPE, case: BOOL _ TRUE, start: INT _ 0, len: INT _ 2147483647, seed: CARDINAL _ 75267B (31415)]šœœœ˜/Kšœœ˜—K˜—K˜š Ÿ œœœœœ˜Zšœœ˜š œœœœœ˜#Kšœœœœ˜1Kšœœœ˜Kšœœ˜—šœœœœ˜ Kšœœœœ ˜Kšœœœ˜!Kšœœ˜—Kšœœ˜—K˜—K˜šœœœ˜AKšŸœ˜KšŸœ˜KšŸœ˜Kšœ,œ˜1Kšœœ˜ —K˜šŸœœœœœœœœ˜NKšœœ˜Kšœœ˜Kšœ˜ —K˜š Ÿœœœ1œœœ˜dšœ œ ˜šœ œ˜šœœœ œ˜$Kš œœœœ œœœ˜1Kš œœœœœ˜Kšœœ˜—š œœœœ œ˜'Kšœœœœ˜Kš œœœœœœœ˜+Kšœœ˜—Kšœœ˜—K˜ K˜ Kšœ˜—Kšœ˜"—K˜šŸœœœœœœœœ ˜SKšœœ˜šœœœ˜ šœœ œ˜'Kšœœ˜ Kšœœœ˜!Kšœœ˜—Kšœ˜—Kšœ˜—K˜šŸœœœœœœœ˜]Kšœœ˜Kšœœ˜Kšœ œ˜Kšœœ˜!Kšœœ˜Kšœ(˜(Kšœ(˜(šœœœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜šœœ˜4K˜ K˜Kšœ˜!——K˜—K˜šŸœœœ œœœœœ˜kšœœœ˜,J˜šœ œ˜šœœ˜ Jšœœ ˜J˜ Jšœœ˜ šœœœœ˜-šœœœ ˜šœ ˜Jšœ œ œœ˜DJšœ œœ˜—Jšœ˜—J˜—J˜—Jšœœœœ˜Jšœœ˜—Jšœ˜—Kšœ œ œœ˜'Kšœ˜—K˜Kšœ œ0œ(œ˜ŒK˜š Ÿœœœ Οcœœœ˜hKšœOœ˜iKšœœœ˜"Kšœ ˜—K˜Kšœœ œ˜9K˜š Ÿ œœœœ œ˜EK˜ Kšœ%œ œœ˜UKšœ˜—K˜š Ÿœœœœœ˜IKšœ'œ œœ˜WKšœ˜—K˜šŸœœœœ˜Fš˜šœ œ˜Kšœœ˜K˜Kšœœ˜—Kšœ˜—Kšœ˜—K˜š Ÿ œœœœ œ˜EK˜ Kšœ%œ œœ˜UKšœ˜—K˜š Ÿœœœœœ˜IKšœ'œ œœ˜WKšœ˜—K˜Kšœœ?˜YK˜š Ÿœœœœœ˜ZKšœ œ˜Kšœ œ˜$K˜—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š œ œœœ œœ.˜qK˜—˜Kšœ œœœ˜K˜Kšœœ˜Kšœ œœ"˜8Kšœœ˜2Kšœ˜—Kšœœ˜—K˜—K˜šŸ œœ&œ˜ZKšœ œœ˜šœ"œœ˜3šœ œ˜Kšœœ˜Kšœœœœ˜Kšœœ˜—Kšœ˜—Kšœ&œœ ˜?Kšœ1˜1Kšœ˜—K˜š Ÿ œœœ=œœ!œ˜‹Kšœ*˜*Kšœ5˜5šŸ œœ˜(Kšœ?˜?Kšœ:˜:Kšœ&œœ ˜NK˜+Kšœœ˜2K˜—KšŸœœ:˜Hšœœœ˜ Kšœœœœ˜,Kšœ œœœ˜KšœH˜HK˜—šœœœ˜Kš  œ˜%K˜—Kšœ$œ˜+Kšœ˜K˜—K˜šŸ œœœ˜(šœ œ˜˜ Kšœ œœœ˜QKšœ œœœ˜RK˜—˜Kšœ =œ˜DK˜—Kšœœ˜—K˜—K˜š Ÿœœœœœ˜IKšœ œ˜+Kšœœœœ˜Nšœœ˜-Kšœ˜K˜ Kšœ˜—Kšœ˜—K˜šŸœœ/˜=K˜Kšœ˜šœœ 5˜Fšœ ˜ šœœœ˜Kšœ5˜5Kš œœœ 6œ˜MKšœ%œœ˜BK˜—Kš œœ œœ!œ˜Jšœ˜šœ.œ˜RKšœœœ˜7Kšœ˜—Kšœ˜—Kšœ˜—Kšœœ˜Kšœœ˜—Kš œœœœœ ˜ZKšœ˜Kšœœœœ˜DKšœœœœ&˜JKšœ˜—K˜š Ÿœœœœœ˜Jšœœœ˜.K˜!K˜Kšœ œ˜!Kšœœ˜—šŸ œœœ˜5K˜Kšœœœ˜.Kšœœ˜+Kšœ,˜,Kšœœœœ˜Kšœb˜bKšœ˜—Kšœ)œ˜>KšœG˜GKšœ˜—K˜šŸ œœœ˜%K˜šœœ˜,Kšœ˜Kšœ˜K˜Kšœœœ*œ˜QKšœœœ*œ˜RKšœ˜—Kšœ˜—K˜šŸ œœœ˜&K˜'K˜Kšœœœœœ/ œœ˜ŸKšœ˜—K˜šŸ œœœ#˜:Kšœ+œ˜3—K˜šŸ œœœ#  œ˜KKšœœ˜Kšœœ˜šŸœœ%˜/Kšœœœœ˜šœœ˜Kšœ˜K˜ Kšœœ˜K˜—šœœ ˜Kšœœ˜Kšœ<œ œ˜TKšœœ˜ Kšœœ˜—Kšœ˜—Kšœ,œ˜6Kšœœœ˜Kšœ˜—K˜š Ÿ œœœ2œœœ˜†Kšœœœ˜.šœœ˜ Kšœ˜K˜ K˜ ˜K˜ Kšœœ˜Kšœ#˜#——Kšœ˜Kšœœœ#œ˜`Kšœ"˜"Kšœ>˜>Kšœ˜Kšœ˜—K˜š Ÿœœœ Ÿœœ ˜EšŸœœ˜"Kšœ œœ ˜'Kšœ˜—Kšœ&˜&K˜Kšœ˜—K˜š ŸœœœŸœœœ˜WKšœ"˜"šŸœœœœ˜Kšœœ˜šŸœœ˜&šœœ˜Kšœœ˜Kšœ œ˜˜K˜ Kšœ6œ œ˜NK˜—Kšœœ˜—Kšœ˜—K˜ Kšœ+˜+Kšœ˜—šŸ œœ˜ šœ)œœ˜Kšœ˜—K˜K˜K˜Kšœ˜—…—n”ά