LichenData3Impl.Mesa
Last tweaked by Mike Spreitzer on October 20, 1987 5:05:23 pm PDT
DIRECTORY Convert, FS, Collections, LichenDataOps, LichenDataStructure, IntFunctions, IntStuff, LichenNavigation, PairCollections, Rope, StructuredStreams, SymTab, TiogaAccess, UnparserBuffer, ViewerIO;
LichenData3Impl: CEDAR PROGRAM
IMPORTS Convert, FS, Collections, LichenDataOps, LichenDataStructure, IntFunctions, IntStuff, Rope
EXPORTS LichenDataOps, LichenDataStructure
=
BEGIN OPEN LichenDataOps, LichenDataStructure, Colls:Collections, PairColls:PairCollections, IntFns:IntFunctions, 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 BOOLALL[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;
RETURN};
EnumerateImmediateConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOLALL[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 BOOLALL[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;
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, 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: BOOLTRUE]] = {
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.GetBounds.Length.EN;
aSib: Wire ~ NARROW[sibs.First.pair.right];
grandParent: Wire ~ aSib.containingWire;
containingCT: CellType ~ aSib.containingCT;
sibSet: Set ~ Speedup[sibs.RightCollection[]];
needParent: BOOLTRUE;
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: BOOLTRUE;
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<len DO
SELECT raw.InlineFetch[i] FROM
'/ => 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: BOOLTRUE]] 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: BOOLTRUE]] 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.