LichenData3Impl.Mesa
Last tweaked by Mike Spreitzer on February 2, 1988 12:48:23 pm PST
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;
}
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<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 => 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.