LichenChildishTransforms.Mesa
Last tweaked by Mike Spreitzer on August 28, 1987 11:17:12 am PDT
DIRECTORY Collections, LichenDataOps, LichenDataStructure, IntFunctions, LichenNavigation, PairCollections, LichenTransforms, LichenTransformsPrivate, RefTab;
LichenChildishTransforms:
CEDAR
PROGRAM
IMPORTS Collections, LichenDataOps, LichenDataStructure, IntFunctions, LichenNavigation, PairCollections, RefTab
EXPORTS LichenTransforms, LichenTransformsPrivate
=
BEGIN OPEN LichenDataStructure, LichenNavigation, LichenTransforms, LichenDataOps, LichenTransformsPrivate, Colls:Collections, PairColls:PairCollections, IntFns:IntFunctions;
LowerChildren:
PUBLIC
PROC [design: Design, childType: CellType, sibber: ConstFunction
--child
b Seq (role
é sibling: Vertex)--]
RETURNS [gcs: Seq
--role
é grandchild--] =
BEGIN
analysis: Analysis =
NEW [AnalysisPrivate ← [
roles: LAST[NATURAL],
wag:
NEW [WireAnsweringPrivate ← [
anses: PairColls.CreateHashFn[]
]],
doomedPorts: Colls.CreateHashSet[]
]];
{OPEN analysis;
oldPort: Port ~ childType.port;
newPort: Port ~ oldPort;
first: BOOL ← TRUE;
dif: BOOL ← FALSE;
parentTypes: VarSet ~ Colls.CreateHashSet[];
childrenV: VarSet ~ Colls.CreateHashSet[];
{
SeeInstance:
PROC [child: CellInstance] = {
sibs: Seq--role é sibling-- = IntFns.DeRef[sibber.Apply[child].val];
IF IsMirror[child] THEN ERROR; --AM2
IF first
THEN {
roles ← sibs.Size;
wag.oldSubjConnectionss ← CreateRefSeq[sibs.Size];
subjTypes ← sibs.Compose[right: instanceType, rightRestricts: FALSE].CreateSimpleCopy[domainFixed: TRUE];
};
IF Survey[child.containingCT, child, sibs, analysis, first] THEN dif ← TRUE;
first ← FALSE;
};
EnumerateInstances[childType, SeeInstance, FALSE];
};
IF first OR dif THEN RETURN [IntFns.nilIntFn];
NoteChange[childType];
gcs ← CreateSeq[oneToOne: TRUE];
FOR role:
NATURAL
IN [0 .. roles)
DO
gcs.Append[Instantiate[
type: NARROW[subjTypes.Apply[role].val],
containingCT: childType]];
ENDLOOP;
{
MaybeDeleteOldChildPort:
PROC [cPort: Port, w: Vertex, e: Edge] = {
wire: Wire = NARROW[w];
IF doomedPorts.HasMember[cPort] THEN RemoveEdges[e];
};
EnumerateTopEdges[childType.asUnorganized.mirror, MaybeDeleteOldChildPort]};
<<{
PerTopWire:
PROC [pair: PairColls.Pair] = {
outerWire: Wire = NARROW[pair[left]];
wa: WireAns = NARROW[pair[right]];
NewPort:
PROC
RETURNS [insideNet: Wire] = {
SELECT wa.doFrom
FROM
addPort => {
wa.counterpart ← insideNet ← CreateWire[containingCT: childType, copy: outerWire];
wa.fromPort ← AddPort[[parent: newPort, wire: insideNet]];
AddEdge[[childType.asUnorganized.mirror, insideNet], wa.fromPort];
};
dePort => ERROR;
leave, dontAdd => IF (insideNet ← wa.counterpart) = NIL THEN ERROR;
ENDCASE => ERROR;
RETURN};
MakeDummy:
PROC
RETURNS [insideNet: Wire] = {
IF wa.counterpart # NIL THEN RETURN [wa.counterpart];
wa.counterpart ← insideNet ← CreateWire[containingCT: childType, copy: outerWire];
RETURN};
innerWire: Wire = IF wa.sawBord THEN wa.fromPort.wire ELSE IF wa.sawElse THEN NewPort[] ELSE MakeDummy[];
FOR subjPorts: RoledPortList ← wa.subjPorts, subjPorts.rest
WHILE subjPorts #
NIL
DO
gc: CellInstance ~ NARROW[gcs.Apply[subjPorts.first.role].val];
AddEdges[[gc, innerWire], subjPorts.first.port];
design ← design;
ENDLOOP;
RETURN};
wag.anses.Enumerate[PerTopWire];
design ← design};>>
FOR role:
NATURAL
IN [0 .. roles)
DO
rt: RefTable--subj port b wire connected to that port of that subject at first site-- ~ NARROW[wag.oldSubjConnectionss[role]];
gc: CellInstance ~ NARROW[gcs.Apply[role].val];
PerPort:
PROC [gcPort: Port]
RETURNS [subs, sibs:
BOOL ←
TRUE] ~ {
urWire: Wire ~ NARROW[rt.Fetch[gcPort].val];
subs ← urWire=NIL;
IF urWire#
NIL
THEN {
wa: WireAns = GetRPAns[wag, role, gcPort, urWire, FALSE];
NewPort:
PROC
RETURNS [insideNet: Wire] = {
SELECT wa.doFrom
FROM
addPort => {
insideNet ← CreateWire[containingCT: childType, copy: urWire];
wa.fromPort ← AddPort[[parent: newPort, wire: insideNet]];
AddEdge[[childType.asUnorganized.mirror, insideNet], wa.fromPort];
};
dePort => ERROR;
leave, dontAdd => ERROR;
ENDCASE => ERROR;
RETURN};
MakeDummy:
PROC
RETURNS [insideNet: Wire] = {
insideNet ← CreateWire[containingCT: childType, copy: urWire];
RETURN};
IF wa.counterpart=NIL THEN wa.counterpart ← IF wa.sawBord THEN wa.fromPort.wire ELSE IF wa.sawElse THEN NewPort[] ELSE MakeDummy[];
{innerWire: Wire ~ wa.counterpart;
AddEdges[[gc, innerWire], gcPort];
design ← design;
}};
RETURN};
ScanPorts[gc.type, PerPort];
design ← design;
ENDLOOP;
CheckCellType[ct: childType, rep: ignore, norm: check, comparable: ignore, instances: FALSE];
{
TweakInstance:
PROC [child: CellInstance] = {
sibs: Seq--role é sibling--;
IF IsMirror[child] THEN ERROR; --AM2
[] ← childrenV.AddElt[child];
sibs ← IntFns.DeRef[sibber.Apply[child].val];
IF sibs.Size # roles THEN ERROR --caller blew it--;
FOR role:
NATURAL
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs.Apply[role].val];
PerEdge:
PROC [gcPort: Port, net: Vertex, e: Edge] = {
wa: WireAns = GetRPAns[wag, role, gcPort];
IF wa.sawElse
AND
NOT wa.sawBord
THEN {
IF wa.child # child
THEN {
AddEdges[[child, NARROW[net]], wa.fromPort];
wa.child ← child};
};
IF NOT (wa.sawElse OR wa.sawBords) THEN DeleteVertex[net] ELSE RemoveEdges[e];
};
IF sib.containingCT # child.containingCT THEN ERROR --caller blew it--;
EnumerateTopEdges[sib, PerEdge];
DeleteVertex[sib];
ENDLOOP;
NoteChange[child.containingCT];
[] ← parentTypes.AddElt[child.containingCT];
};
EnumerateInstances[childType, TweakInstance, FALSE]};
CheckCellTypes[parentTypes.Freeze, ignore, check, ignore];
}END;
RaiseGrandchildren:
PUBLIC
PROC [design: Design, gcs: Seq
--role
é instance in childType--]
RETURNS [childType: CellType, sibber: ConstFunction
--child
b Seq (role
é sibling: Vertex)--, typer: ConstFunction
--array
*n of childType
b Seq (role
é array
*n of type of gcs[role])--] =
BEGIN
analysis: Analysis =
NEW [AnalysisPrivate ← [
roles: gcs.Size,
subjTypes: gcs.Compose[instanceType].CreateSimpleCopy[oneToOne: TRUE].Freeze,
wag:
NEW [WireAnsweringPrivate ← [
oldSubjConnectionss: CreateRefSeq[gcs.Size],
anses: PairColls.CreateHashFn[]
]],
doomedPorts: Colls.CreateHashSet[]
]];
{OPEN analysis;
addedPorts: VarSet = Colls.CreateHashSet[];
parentTypes: VarSet = Colls.CreateHashSet[];
sibberV: VarFunction ~ PairColls.CreateHashFn[];
childType ← NARROW[gcs.First.pair.right, CellInstance].containingCT;
typer ← PairColls.CreateSingleton[[childType, subjTypes.Refify], [Colls.refs, Colls.refs]];
FOR role:
NAT
IN [0 .. roles)
DO
gc: CellInstance ~ NARROW[gcs.Apply[role].val];
IF gc.containingCT # childType THEN ERROR;
ENDLOOP;
{oldPort: Port ~ childType.port;
newPort: Port ~ oldPort;
IF Survey[childType, NIL, gcs, analysis, TRUE] THEN ERROR;
{
DeleteDoomed:
PROC [elt:
REF
ANY] = {
RemovePort[NARROW[elt]];
};
doomedPorts.Enumerate[DeleteDoomed];
};
{
MaybeAddPort:
PROC [pair: PairColls.Pair] ~ {
wire: Wire ~ NARROW[pair[left]];
wa: WireAns ~ NARROW[pair[right]];
IF NOT wa.analyzed THEN ERROR;
IF wa.sawElse
AND
NOT wa.sawBord
THEN {
SELECT wa.doFrom
FROM
addPort => {
wa.fromPort ← AddPort[[parent: newPort, wire: wire]];
[] ← addedPorts.AddElt[wa.fromPort];
AddEdge[[childType.asUnorganized.mirror, wire], wa.fromPort]};
leave, dontAdd, dePort => NULL;
ENDCASE => ERROR;
};
};
wag.anses.Enumerate[MaybeAddPort];
};
<<FOR role:
NATURAL
IN [0 .. roles)
DO
gc: CellInstance = NARROW[gcs[role]];
PerEdge:
PROC [gcPort: Port, wire: Wire] = {
wa: WireAns = GetRPAns[wag, role, gcPort, wire, FALSE];
IF NOT wa.analyzed THEN ERROR;
IF wa.sawElse
AND
NOT wa.sawBord
THEN {
SELECT wa.doFrom
FROM
addPort => {
wa.doFrom ← addedPort;
wa.fromPort ← AddPort[[parent: newPort, wire: wire]];
[] ← addedPorts.AddElt[wa.fromPort];
AddEdge[[childType.asUnorganized.mirror, wire], wa.fromPort]};
addedPort => NULL;
leave, dontAdd, dePort => NULL;
ENDCASE => ERROR;
};
};
EnumerateTopConnections[gc, PerEdge];
ENDLOOP;>>
NoteChange[childType];
FOR role:
NATURAL
IN [0 .. roles)
DO
gc: CellInstance ~ NARROW[gcs.Apply[role].val];
PerEdge:
PROC [gcPort: Port, wire: Wire, e: Edge] = {
wa: WireAns = GetRPAns[wag, role, gcPort, wire, FALSE];
IF NOT (wa.sawElse OR wa.sawBords) THEN DeleteVertex[wire] ELSE RemoveEdge[e];
};
EnumerateTopEdges[gc, PerEdge];
DeleteVertex[gc];
ENDLOOP;
CheckCellType[ct: childType, rep: ignore, norm: check, comparable: ignore, instances: FALSE];
{
FixInstance:
PROC [child: CellInstance] = {
sibs: Seq ~ CreateSeq[oneToOne: TRUE, dense: TRUE];
cons: RefTable--child port b wire-- = CreateRefTable[];
IF IsMirror[child] THEN ERROR; --AM2
[] ← sibberV.Store[[child, sibs.Refify]];
FOR role:
NATURAL
IN [0 .. roles)
DO
gc: CellInstance = NARROW[gcs.Apply[role].val];
sibs.Append[Instantiate[gc.type, child.containingCT]];
ENDLOOP;
{
PerConnection:
PROC [cPort: Port, net: Vertex, ce: Edge] = {
[] ← cons.Store[cPort, net];
IF doomedPorts.HasMember[cPort] THEN RemoveEdges[ce];
};
EnumerateTopEdges[child, PerConnection]};
{
LinkToNewPort:
PROC [elt:
REF
ANY] = {
cPort: Port = NARROW[elt];
outerNet: Wire = CreateWire[containingCT: child.containingCT, copy: cPort.wire];
IF cPort.wire=NIL THEN ERROR;
AddEdges[[child, outerNet], cPort];
[] ← cons.Store[cPort, outerNet];
};
addedPorts.Enumerate[LinkToNewPort]};
FOR role:
NATURAL
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs.Apply[role].val];
PerPort:
PROC [gcPort: Port] = {
wa: WireAns = GetRPAns[wag, role, gcPort];
MakeDummyNet:
PROC [iNet: Wire]
RETURNS [oNet: Wire] = {
oNet ← wa.counterpart;
IF oNet =
NIL
OR wa.child # child
THEN {
oNet ← CreateWire[containingCT: child.containingCT, copy: iNet];
wa.counterpart ← oNet;
wa.child ← child;
};
};
AddEdge[
[sib,
IF wa.sawBord
OR wa.sawElse
THEN NARROW[cons.Fetch[wa.fromPort].val]
ELSE MakeDummyNet[wa.proto]],
gcPort];
};
EnumeratePorts[sib.type, PerPort];
ENDLOOP;
NoteChange[child.containingCT];
[] ← parentTypes.AddElt[child.containingCT];
};
EnumerateInstances[childType, FixInstance, FALSE]};
CheckCellTypes[parentTypes.Freeze, ignore, check, ignore];
sibber ← sibberV.Freeze[];
}}END;
Survey:
PUBLIC
PROC [parent: CellType, child: Vertex, sibs: Seq
--role
é grandchild--, analysis: Analysis, first:
BOOL]
RETURNS [dif:
BOOL ←
FALSE] = {
OPEN analysis;
lwag: WireAnswering = NEW [WireAnsweringPrivate ← [CreateRefSeq[roles], PairColls.CreateHashFn[]]];
IF sibs.Size # subjTypes.Size
THEN {
Warning["Different number of siblings (%g, rather than %g) at %g", Int[sibs.Size], Int[subjTypes.Size], child];
dif ← TRUE}
ELSE
FOR role:
NATURAL
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs.Apply[role].val];
SeeConnection:
PROC [gcPort: Port, wire: Wire] = {
lwa: WireAns = GetRPAns[lwag, role, gcPort, wire, TRUE];
wa: WireAns = GetRPAns[wag, role, gcPort, wire, first];
SeeBackConnection:
PROC [cPort: Port, v: Vertex] = {
ci: CellInstance = NARROW[v];
bord: BOOL = IF child # NIL THEN ci=child ELSE IsMirror[ci];
IF bord
THEN {
lwa.sawBords ← lwa.sawBord;
lwa.sawBord ← TRUE;
lwa.fromPort ← cPort;
}
ELSE {sawSomeSelf:
BOOL ←
FALSE;
FOR j:
NATURAL
IN [0 .. roles)
DO
IF ci = sibs.Apply[j].Val THEN sawSomeSelf ← lwa.sawSelves[j] ← TRUE;
ENDLOOP;
IF NOT sawSomeSelf THEN lwa.sawElse ← TRUE;
};
RETURN};
IF
NOT lwa.analyzed
THEN {
lwa.analyzed ← TRUE;
lwa.sawSelves ← CreateBoolSeq[roles, FALSE];
EnumerateTransitiveConnections[wire, SeeBackConnection];
IF NOT lwa.sawSelves[role] THEN ERROR;
IF first
THEN {
wa^ ← lwa^;
IF wa.sawBord
AND
NOT (wa.sawElse
OR wa.sawBords)
THEN {
losses ← NoteLoss[wa, losses];
IF NOT doomedPorts.AddElt[wa.fromPort] THEN ERROR;
};
IF wa.sawElse AND NOT wa.sawBord THEN fromGains ← NoteFromGain[wa, fromGains];
IF NOT (wa.sawElse OR wa.sawBord) THEN wa.doFrom ← dontAdd;
IF wa.sawElse OR wa.sawBord THEN toGains ← NoteToGain[wa, toGains];
}
ELSE {
IF wa.sawBord # lwa.sawBord THEN GOTO Dif;
IF wa.sawBords # lwa.sawBords THEN GOTO Dif;
IF wa.sawElse # lwa.sawElse THEN GOTO Dif;
FOR j:
NATURAL
IN [0 .. roles)
DO
IF wa.sawSelves[j] # lwa.sawSelves[j] THEN GOTO Dif;
ENDLOOP;
EXITS
Dif => {Warning["%g is connected differently than at first site", wire]; dif ← TRUE};
};
};
IF first
THEN {
wa.subjPorts ← CONS[[role, gcPort], wa.subjPorts];
};
RETURN};
IF subjTypes.Apply[role].val # sib.type
THEN {
Warning["%g is a %g, not a %g", sib, sib.type, subjTypes.Apply[role].val];
dif ← TRUE}
ELSE
IF sib = child
THEN {
Warning["Child %g sibbed to itself", child];
dif ← TRUE}
ELSE IF sib.containingCT # parent THEN ERROR
ELSE {
EnumerateTopConnections[sib, SeeConnection];
parent ← parent};
ENDLOOP;
RETURN};
GetRPAns:
PUBLIC
PROC [wag: WireAnswering, role:
NATURAL, subjPort: Port, wire: Wire ←
NIL, mayChange:
BOOL ←
FALSE]
RETURNS [wa: WireAns] = {
kw: Wire;
rt: RefTable ← NARROW[wag.oldSubjConnectionss[role]];
IF rt =
NIL
THEN {
IF NOT mayChange THEN ERROR;
wag.oldSubjConnectionss[role] ← rt ← CreateRefTable[];
};
IF wire =
NIL
THEN {
wire ← NARROW[rt.Fetch[subjPort].val];
IF wire = NIL THEN ERROR;
};
kw ← NARROW[rt.Fetch[subjPort].val];
IF kw =
NIL
THEN {
IF NOT mayChange THEN ERROR;
IF NOT rt.Insert[subjPort, kw ← wire] THEN ERROR};
IF wire # kw THEN ERROR;
wa ← NARROW[wag.anses.Apply[wire].DVal];
IF wa =
NIL
THEN {
IF NOT mayChange THEN ERROR;
wa ← NEW [WireAnsPrivate ← [proto: wire]];
IF NOT wag.anses.Store[[wire, wa]].new THEN ERROR;
};
};
NoteLoss:
PROC [wa: WireAns, oldLosses:
CARDINAL]
RETURNS [newLosses:
CARDINAL] = {
newLosses ← oldLosses;
SELECT wa.doFrom
FROM
leave => {newLosses ← newLosses + 1; wa.doFrom ← dePort};
dePort => NULL;
addPort, dontAdd => ERROR;
ENDCASE => ERROR;
};
NoteFromGain:
PROC [wa: WireAns, oldGains:
CARDINAL]
RETURNS [newGains:
CARDINAL] = {
newGains ← oldGains;
SELECT wa.doFrom
FROM
leave => {newGains ← newGains + 1; wa.doFrom ← addPort};
addPort => NULL;
dePort, dontAdd => ERROR;
ENDCASE => ERROR;
};
NoteToGain:
PROC [wa: WireAns, oldGains:
CARDINAL]
RETURNS [newGains:
CARDINAL] = {
newGains ← oldGains;
SELECT wa.doTo
FROM
dontAdd => {newGains ← newGains + 1; wa.doTo ← addPort};
addPort => NULL;
ENDCASE => ERROR;
};
Int: PROC [i: INT] RETURNS [ra: REF ANY] = {ra ← NEW [INT ← i]};
END.