DIRECTORY AbSets, BiRels, Convert, FS, IntStuff, LichenDataOps, LichenDataStructure, LichenNavigation, Rope, SetBasics, StructuredStreams, SymTab, TiogaAccess, UnparserBuffer, ViewerIO; LichenData3Impl: CEDAR PROGRAM IMPORTS AbSets, BiRels, Convert, FS, IntStuff, LichenDataOps, LichenDataStructure, Rope, SetBasics EXPORTS LichenDataOps, LichenDataStructure = BEGIN OPEN LichenDataOps, LichenDataStructure, Sets:AbSets, SS:StructuredStreams, UB:UnparserBuffer; Escape: ERROR = CODE; 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] ~ { Test: PROC [val: Sets.Value] RETURNS [BOOL] ~ {Consume[NARROW[val.VA]]; RETURN [FALSE]}; IF ScanParts[ct, Test, ALL[TRUE], mirrorToo].found THEN ERROR; RETURN}; ScanParts: PUBLIC PROC [ct: CellType, Test: Sets.Tester, filter: PartFilter, mirrorToo: BOOL] RETURNS [mv: Sets.MaybeValue _ Sets.noMaybe] ~ { u: Unorganized ~ ct.asUnorganized; PerCell: PROC [ra: Sets.Value] RETURNS [BOOL] ~ { ci: CellInstance ~ NARROW[ra.VA]; PassIMs: PROC [p: Port, v: Vertex, e: Edge] RETURNS [BOOL] ~ { WITH v SELECT FROM ci: CellInstance => ERROR; w: Wire => NULL; im: Intermediary => { IF Test[AV[im]] THEN RETURN [(mv _ [TRUE, AV[im]]).found]; RETURN ScanImmediateEdges[im, PassIMs, [cellward: FALSE, wireward: TRUE]]; }; ENDCASE => ERROR; RETURN [FALSE]}; IF filter[cell] AND Test[AV[ci]] THEN RETURN [(mv _ [TRUE, AV[ci]]).found]; IF filter[intermediate] THEN RETURN ScanImmediateEdges[ci, PassIMs]; RETURN [FALSE]}; PassChildren: PROC [w: Wire] RETURNS [Sets.MaybeValue] ~ { FOR w _ FirstChildWire[w], NextChildWire[w] WHILE w # NIL DO IF Test[AV[w]] THEN RETURN [[TRUE, AV[w] ]]; {sub: Sets.MaybeValue ~ PassChildren[w]; IF sub.found THEN RETURN [sub]; }ENDLOOP; RETURN [Sets.noMaybe]}; IF u=NIL THEN ERROR; IF filter[wire] AND (mv _ PassChildren[u.internalWire]).found THEN RETURN; IF filter[intermediate] THEN {IF (mv _ u.containedInstances.Scan[PerCell]).found THEN RETURN} ELSE IF filter[cell] AND (mv _ u.containedInstances.Scan[Test]).found THEN RETURN; IF mirrorToo AND PerCell[AV[u.mirror]] THEN mv _ [TRUE, AV[u.mirror]]; RETURN}; EnumerateCellTypes: PUBLIC PROC [design: Design, Consume: PROC [CellType]] = { PerCellType: PROC [elt: REF ANY] = {Consume[NARROW[elt]]}; design.cellTypes.EnumA[PerCellType]}; ScanImmediateEdges: PUBLIC PROC [v: Vertex, Test: PROC [Port, Vertex, Edge] RETURNS [BOOL], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any] RETURNS [BOOL] = { 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 { IF Test[e.port, w, e] THEN RETURN [TRUE]; lastConsumed _ e}; lastEdge _ e; ENDLOOP; RETURN [FALSE]}; EnumerateImmediateEdges: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any] = { Test: PROC [p: Port, v: Vertex, e: Edge] RETURNS [BOOL] ~ {Consume[p, v, e]; RETURN [FALSE]}; IF ScanImmediateEdges[v, Test, filter, order] THEN ERROR; RETURN}; EnumerateImmediateConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any] = { Test: PROC [p: Port, v: Vertex, e: Edge] RETURNS [BOOL] ~ {Consume[p, v]; RETURN [FALSE]}; IF ScanImmediateEdges[v, Test, filter, order] THEN ERROR; RETURN}; EnumerateNeighboringVertices: PUBLIC PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]] = { Test: PROC [port: Port, w: Vertex, e: Edge] RETURNS [BOOL] = {Consume[w]; RETURN [FALSE]}; IF ScanImmediateEdges[v, Test, filter] THEN ERROR; RETURN}; 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; RETURN}; 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; RETURN}; EnumerateImmediateEdges[ci, Work]; RETURN}; 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, from, to: Port] RETURNS [v: Vertex] = { IF to=NIL THEN ERROR; IF from=to THEN RETURN [cellward]; {mid: Vertex ~ IF from=to.parent THEN cellward ELSE FindTransitiveConnection[cellward, from, NARROW[to.parent]]; IF mid=NIL THEN RETURN [NIL]; WITH mid SELECT FROM ci: CellInstance => NULL; im: Intermediary => NULL; midw: Wire => RETURN [midw.SubWire[to.PortIndex[]]]; ENDCASE => ERROR; RETURN [FindImmediateConnection[mid, to]]}}; 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]; }; EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] ~ { FOR act: CellType _ cellType.firstArray, act.asArray.nextArray WHILE act#NIL DO Consume[act] ENDLOOP; RETURN}; 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.GetIntDom.Length.EN; isibs: Seq ~ sibs.CreateHashCopy[mappable: [FALSE, TRUE]]; aSib: Wire ~ NARROW[sibs.APair.it[right].VA]; grandParent: Wire ~ aSib.containingWire; containingCT: CellType ~ aSib.containingCT; sibSet: Set ~ isibs.SetOn[right]; 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.HasMemA[sib] THEN { forget: SteppyNameList _ NIL; index: INT ~ isibs.ApplyA[sib, rightToLeft].MI; name: SteppyName ~ LSn[LIST[NEW[INT _ index]]]; ForgetName: PROC [val: Sets.Value] ~ {forget _ CONS[VSn[val], forget]}; sib.VertexNames.Enumerate[ForgetName]; 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.GetIntDom.Length.EN; isibs: Seq ~ sibs.CreateHashCopy[mappable: [FALSE, TRUE]]; aSib: Port ~ NARROW[sibs.APair.it[right].VA]; grandParent: Port ~ NARROW[aSib.parent]; containingCT: CellType ~ aSib.PortCCT; sibSet: Set ~ isibs.SetOn[right]; 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.HasMemA[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.HasMemA[sib] THEN { index: INT ~ isibs.ApplyA[sib, rightToLeft].MI; name: SteppyName ~ LSn[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}; 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 [SteppyName] ~ { len: INT ~ raw.Length; steps: TList _ []; 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 => steps _ steps.Append[part]; num => steps _ steps.Append[NewInt[Convert.IntFromRope[part]]]; ENDCASE => ERROR; IF i=len THEN EXIT ELSE i _ i + 1; }ENDLOOP; RETURN LSn[steps.head]}; UnparseSteppyName: PUBLIC PROC [s: SteppyName] RETURNS [u: ROPE] ~ { u _ NIL; FOR steps: NameStepList _ s.steps, steps.rest WHILE steps#NIL DO r: ROPE ~ WITH steps.first SELECT FROM x: ROPE => x, x: REF INT => Convert.RopeFromInt[x^], ENDCASE => ERROR; IF u#NIL THEN u _ u.Cat["/", r] ELSE 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 February 2, 1988 12:48:23 pm PST Κ7˜™IcodešœB™B—J˜KšΟk œœ”˜ΉK˜šΡbnxœœ˜Kšœœ?˜bKšœ#˜*Kšœ˜—K˜Kš œœ%Οnœœœ˜dK˜KšŸœœœ˜K˜š Ÿœœœ Ÿœœ ˜EšŸœœ˜"Kšœ œœ ˜'Kšœ˜—Kšœ&˜&K˜Kšœ˜—K˜š ŸœœœŸœœœ˜WšŸœœœœ˜+Kš œ œœœœ˜,—Kš œœœœœ˜>Kšœ˜—K˜š Ÿ œœœŸœ.œœ)˜ŽKšœ"˜"šŸœœœœ˜1Kšœœœ˜!šŸœœœœ˜>šœœ˜Kšœœ˜Kšœ œ˜šœ˜Kš œœœœ œœ˜:Kšœ,œ œ˜JK˜—Kšœœ˜—Kšœœ˜—Kšœœœœœ œœ˜KKšœœœ!˜DKšœœ˜—šŸ œœ œ˜:šœ)œœ˜