LichenData3Impl.Mesa
Last tweaked by Mike Spreitzer on August 27, 1987 2:32:24 pm PDT
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;
}
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<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:
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.