DIRECTORY Convert, FS, LichenCollections, LichenDataOps, LichenDataStructure, LichenIntFunctions, LichenIntStuff, LichenNavigation, LichenPairCollections, Rope, StructuredStreams, SymTab, TiogaAccess, UnparserBuffer, ViewerIO; LichenData3Impl: CEDAR PROGRAM IMPORTS Convert, FS, LichenCollections, LichenDataOps, LichenDataStructure, LichenIntFunctions, LichenIntStuff, Rope EXPORTS LichenDataOps, LichenDataStructure = BEGIN OPEN LichenDataOps, LichenDataStructure, Colls:LichenCollections, PairColls:LichenPairCollections, IntFns:LichenIntFunctions, SS:StructuredStreams, UB:UnparserBuffer; Relation: TYPE ~ PairColls.Relation; Escape: ERROR = CODE; EnumerateCellTypes: PUBLIC PROC [design: Design, Consume: PROC [CellType]] = { PerCellType: PROC [elt: REF ANY] = {Consume[NARROW[elt]]}; design.cellTypes.Enumerate[PerCellType]}; 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; lastEdge, lastConsumed: Edge _ NIL; FOR e: Edge _ nextEdge, nextEdge WHILE e # NIL DO selfward: GraphDirection = SELECT v.class FROM cell => cellward, wire => wireward, intermediate => e.SideFor[v], 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]; lastConsumed _ e}; lastEdge _ 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; RETURN}; 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]; RETURN [NIL, NIL]}; 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]; RETURN[NIL]}; FindTopEdge: PUBLIC PROC [ci: CellInstance, port: Port] RETURNS [v: Vertex, e: Edge] ~ { IF port=ci.type.port THEN RETURN [ci, NIL]; {pv: Vertex ~ SELECT port.parent FROM ci.type.port => ci, ENDCASE => FindTopEdge[ci, NARROW[port.parent]].v; [v, e] _ FindImmediateEdge[ci, port]; RETURN}}; ImParent: PUBLIC PROC [im: Intermediary] RETURNS [v: Vertex] = { See: PROC [w: Vertex] = {v _ w}; EnumerateNeighboringVertices[im, See, [cellward: TRUE, wireward: FALSE]]; }; 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"]; }; ScanPorts: PUBLIC PROC [cellType: CellType, Consume: PROC [Port] RETURNS [subs, sibs: BOOL _ TRUE]] = { Work: PROC [port: Port, wire: Wire, wired: BOOL] RETURNS [sibs: BOOL] = { subPort: Port _ port.firstChild; subWire: Wire _ IF wired THEN wire.firstChild ELSE NIL; subs: BOOL; IF port.wire # wire THEN ERROR Error["Broken"]; [subs, sibs] _ Consume[port]; IF subs THEN { WHILE subPort # NIL DO IF NOT wired THEN subWire _ subPort.wire ELSE IF subWire = NIL THEN ERROR Error["Broken"]; IF NOT Work[subPort, subWire, subWire # NIL] THEN RETURN; subPort _ subPort.next; IF wired THEN subWire _ subWire.next; ENDLOOP; IF wired AND subWire # NIL THEN ERROR Error["Broken"]; }; RETURN}; IF cellType.port.next # 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], mirror: BOOL] = { FOR ci: CellInstance _ cellType.firstInstance, ci.nextInstance WHILE ci # NIL DO Consume[ci]; ENDLOOP; IF mirror AND cellType.asUnorganized#NIL THEN Consume[cellType.asUnorganized.mirror]; }; 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"]; }; GroupWires: PUBLIC PROC [sibs: Seq--of wire--, parentNames: ListData] RETURNS [parent: Wire] ~ { n: NATURAL ~ sibs.GetBounds.Length.EN; aSib: Wire ~ NARROW[sibs.First.pair.right]; grandParent: Wire ~ aSib.containingWire; containingCT: CellType ~ aSib.containingCT; sibSet: Set ~ Speedup[sibs.RightCollection[]]; needParent: BOOL _ TRUE; highLast, lowLast: Wire _ NIL; parent _ NEW [VertexPrivate.wire _ [ containingCT: containingCT, names: parentNames, variant: wire[ containingWire: grandParent ]]]; FOR sib: Wire _ grandParent.FirstChildWire[], sib.NextChildWire[] UNTIL sib=NIL DO AddHigh: PROC [x: Wire] ~ { x.prev _ highLast; IF highLast#NIL THEN highLast.next _ x ELSE grandParent.firstChild _ x; highLast _ x; RETURN}; IF sibSet.HasMember[sib] THEN { forget: LIST OF SteppyName _ NIL; index: INT ~ sibs.InvApply[sib].I; name: SteppyName ~ LIST[NEW[INT _ index]]; PerName: PROC [val: REF ANY] ~ {forget _ CONS[NARROW[val], forget]}; sib.VertexNames.Enumerate[PerName]; FOR forget _ forget, forget.rest WHILE forget#NIL DO ForgetVertexName[sib, forget.first] ENDLOOP; UnindexVertexNames[sib]; sib.containingWire _ parent; IndexVertexNames[sib]; KnowVertexName[sib, name]; IF needParent THEN {needParent _ FALSE; AddHigh[parent]}; sib.prev _ lowLast; IF lowLast#NIL THEN lowLast.next _ sib ELSE parent.firstChild _ sib; lowLast _ sib; } ELSE { AddHigh[sib]; }; ENDLOOP; parent.lastChild _ lowLast; grandParent.lastChild _ highLast; highLast.next _ lowLast.next _ NIL; IndexVertexNames[parent]; RETURN}; GroupPorts: PUBLIC PROC [sibs: Seq--of port--, parentNames: ListData] RETURNS [parent: Port] ~ { n: NATURAL ~ sibs.GetBounds.Length.EN; aSib: Port ~ NARROW[sibs.First.pair.right]; grandParent: Port ~ NARROW[aSib.parent]; containingCT: CellType ~ aSib.PortCCT; sibSet: Set ~ Speedup[sibs.RightCollection[]]; FixInstance: PROC [ci: CellInstance] ~ { grandParentV: Vertex ~ FindTopEdge[ci, grandParent].v; parentIM: Intermediary ~ CreateIntermediary[from: grandParentV, go: wireward, containingCT: ci.containingCT, port: parent, names: parentNames]; vs: ARRAY GraphDirection OF Vertex _ ALL[parentIM]; MoveEdge: PROC [sib: Port, v: Vertex, e: Edge] ~ { IF e.sides[wireward].v#v THEN ERROR; IF NOT sibSet.HasMember[sib] THEN RETURN; RemoveEdge[e]; vs[wireward] _ v; AddEdge[vs, sib]; RETURN}; grandParentV.EnumerateImmediateEdges[Consume: MoveEdge, filter: [cellward: FALSE, wireward: TRUE]]; RETURN}; needParent: BOOL _ TRUE; highLast, lowLast: Port _ NIL; parent _ NEW [PortPrivate _ [ parent: grandParent, names: parentNames ]]; FOR sib: Port _ grandParent.FirstChildPort[], sib.NextChildPort[] UNTIL sib=NIL DO AddHigh: PROC [x: Port] ~ { x.prev _ highLast; IF highLast#NIL THEN highLast.next _ x ELSE grandParent.firstChild _ x; highLast _ x; RETURN}; IF sibSet.HasMember[sib] THEN { index: INT ~ sibs.InvApply[sib].I; name: SteppyName ~ LIST[NEW[INT _ index]]; sib.names _ CreateSteppyNames[LIST[name]]; IF needParent THEN {needParent _ FALSE; AddHigh[parent]}; sib.prev _ lowLast; IF lowLast#NIL THEN lowLast.next _ sib ELSE parent.firstChild _ sib; lowLast _ sib; sib.parent _ parent; } ELSE AddHigh[sib]; ENDLOOP; parent.lastChild _ lowLast; grandParent.lastChild _ highLast; highLast.next _ lowLast.next _ NIL; containingCT.EnumerateInstances[FixInstance, TRUE]; RETURN}; Speedup: PROC [org: Set] RETURNS [fast: Set] ~ { IF org.Size[]<4 THEN RETURN [org]; fast _ org.CreateHashCopy[]; RETURN}; ExpandName: PUBLIC PROC [fileName, defaultExtension: ROPE] RETURNS [fullFName: ROPE, cp: FS.ComponentPositions] = { [fullFName, cp, ] _ FS.ExpandName[fileName]; IF defaultExtension.Length[]>0 AND cp.ext.start = cp.base.start+cp.base.length THEN { fileName _ FS.ConstructFName[[ server: fullFName.Substr[cp.server.start, cp.server.length], dir: fullFName.Substr[cp.dir.start, cp.dir.length], subDirs: fullFName.Substr[cp.subDirs.start, cp.subDirs.length], base: fullFName.Substr[cp.base.start, cp.base.length], ext: defaultExtension, ver: fullFName.Substr[cp.ver.start, cp.ver.length] ]]; [fullFName, cp, ] _ FS.ExpandName[fileName]; }; }; ParseSteppyName: PUBLIC PROC [raw: ROPE] RETURNS [p: SteppyName] ~ { len: INT ~ raw.Length; t: SteppyName _ p _ NIL; Append: PROC [step: NameStep] = { this: SteppyName ~ LIST[step]; IF t = NIL THEN p _ this ELSE t.rest _ this; t _ this}; i: INT _ 0; DO start: INT ~ i; type: {unk, num, name} _ unk; WHILE i EXIT; IN ['0 .. '9] => IF type=unk THEN type _ num; ENDCASE => type _ name; i _ i + 1; ENDLOOP; {part: ROPE ~ raw.Substr[start: start, len: i-start]; SELECT type FROM unk, name => Append[part]; num => Append[NewInt[Convert.IntFromRope[part]]]; ENDCASE => ERROR; IF i=len THEN EXIT ELSE i _ i + 1; }ENDLOOP; RETURN}; UnparseSteppyName: PUBLIC PROC [s: SteppyName] RETURNS [u: ROPE] ~ { u _ NIL; FOR s _ s, s.rest WHILE s#NIL DO r: ROPE ~ WITH s.first SELECT FROM x: ROPE => x, x: REF INT => Convert.RopeFromInt[x^], ENDCASE => ERROR; IF u#NIL THEN u _ u.Concat["/"]; u _ u.Concat[r]; ENDLOOP; RETURN}; EnumeratePort: PUBLIC PROC [port: Port, Consume: PROC [Port] RETURNS [doKids, moreSibs: BOOL _ TRUE]] RETURNS [didKids, moreSibs: BOOL] ~ { [didKids, moreSibs] _ Consume[port]; IF didKids THEN { FOR port _ port.FirstChildPort, port.NextChildPort UNTIL port=NIL DO IF NOT EnumeratePort[port, Consume].moreSibs THEN EXIT ENDLOOP; RETURN}; RETURN}; EnumerateWire: PUBLIC PROC [wire: Wire, Consume: PROC [Wire] RETURNS [doKids, moreSibs: BOOL _ TRUE]] RETURNS [didKids, moreSibs: BOOL] ~ { [didKids, moreSibs] _ Consume[wire]; IF didKids THEN { FOR wire _ wire.FirstChildWire, wire.NextChildWire UNTIL wire=NIL DO IF NOT EnumerateWire[wire, Consume].moreSibs THEN EXIT ENDLOOP; RETURN}; RETURN}; END. \LichenData3Impl.Mesa Last tweaked by Mike Spreitzer on August 27, 1987 2:32:24 pm PDT Κ*˜™Icodešœ@™@—J˜KšΟk œ œΝ˜βK˜šΡbnxœœ˜Kšœ œa˜tKšœ#˜*Kšœ˜—K˜Kšœœ%ΟnœŸ œŸœœœ˜¬K˜Kšœ œ˜$K˜KšŸœœœ˜K˜š ŸœœœŸœœ˜NK•StartOfExpansionP -- [key: HashTable.Key, value: HashTable.Value] RETURNS [quit: BOOLEAN _ FALSE]š Ÿ œœœœ œ˜:Kšœ)˜)—K˜šŸœœœ Ÿœœœœœœœ˜žšœœœΟc˜8Kšœ˜K˜Kšœœ˜—Kšœœ˜#šœœœ˜1šœœ ˜.K˜K˜Kšœ˜Kšœœ˜—K˜3K˜Kšœœœ˜&Kšœœœœ˜Kšœ œœ ˜2Kšœ'˜'Kšœ#˜#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˜šŸœœœ œ˜ZKšœ œ˜šŸœœ˜$Kšœ œœ ˜)K˜—Kšœ0˜0Kšœœ˜ —K˜šŸ œœœ œ˜XKšœœœœ˜+šœœ ˜%Kšœ˜Kšœœ˜2—Kšœ%˜%Kšœ˜ —K˜šŸœœœœ˜@KšŸœœ˜ Kšœ1œ œ˜IK˜—K˜š ŸœœœŸœœ ˜JšŸœœ!œ˜4K˜ Kš œœœœœ˜7Kšœœœ˜/K˜šœ œ˜Kšœœœœœ œœœ˜ZKšœ!œ˜&Kšœ˜Kšœœ˜%Kšœ˜—Kš œœ œœœ˜6K˜—Kšœ=œ˜BKšœœœœ˜7K˜—K˜šŸ œœœŸœœœœœ˜gš Ÿœœ!œœœ˜IK˜ Kš œœœœœ˜7Kšœœ˜ Kšœœœ˜/Kšœ˜šœœ˜šœ œ˜Kšœœœœœ œœœ˜ZKš œœ"œœœ˜9Kšœ˜Kšœœ˜%Kšœ˜—Kš œœ œœœ˜6K˜—Kšœ˜—Kšœœœœ˜7KšœBœ˜GKšœœœœ˜7K˜—K˜š ŸœœœŸœœœ˜dšœ<œœ˜PK˜ Kšœ˜—Kšœœœœ(˜UK˜—K˜š ŸœœœŸœœ˜ZK˜K˜K˜š œœœœ˜"Kšœ*˜*K˜K˜Kšœ˜—Kš œœœœœœ˜7K˜—K˜š Ÿ œœœ   œœ˜`Kšœœœ˜&Kšœ œ˜+Kšœ(˜(Kšœ+˜+K˜.Kšœ œœ˜Kšœœ˜šœ œ˜$Kšœ˜Kšœ˜šœ˜Kšœ˜Kšœ˜——šœ?œœ˜RšŸœœ˜K˜Kšœ œœœ˜GK˜ Kšœ˜—šœœ˜Kšœœœœ˜!Kšœœ˜"Kšœœœœ ˜*Kš Ÿœœœœœœ˜DK˜#Kš œœœœ%œ˜aKšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ œœ˜9K˜Kšœ œœœ˜DKšœ˜K˜—šœ˜K˜ K˜—Kšœ˜—K˜K˜!Kšœœ˜#K˜Kšœ˜—K˜š Ÿ œœœ   œœ˜`Kšœœœ˜&Kšœ œ˜+Kšœœ˜(Kšœ&˜&K˜.šŸ œœ˜(Kšœ6˜6Kšœ˜Kšœœœ œ ˜3šŸœœ$˜2Kšœœœ˜$Kšœœœœ˜)Kšœ˜Kšœ˜Kšœ˜Kšœ˜—Kšœ%Ÿœœ œ˜cKšœ˜—Kšœ œœ˜Kšœœ˜šœ œ˜K˜Kšœ˜K˜—šœ?œœ˜RšŸœœ˜K˜Kšœ œœœ˜GK˜ Kšœ˜—šœœ˜Kšœœ˜"Kšœœœœ ˜*Kšœœ˜*Kšœ œœ˜9K˜Kšœ œœœ˜DKšœ˜K˜K˜—Kšœ˜Kšœ˜—K˜K˜!Kšœœ˜#Kšœ-œ˜3Kšœ˜—K˜šŸœœ œ˜0Kšœœœ˜"K˜Kšœ˜—K˜šŸ œœœœœ œœ˜sKšœœ˜,šœœ-œ˜Ušœ œ˜Kšœ<˜