LichenChildishTransforms.Mesa
Last tweaked by Mike Spreitzer on February 3, 1988 3:23:17 pm PST
DIRECTORY AbSets, BiRels, IntStuff, LichenDataOps, LichenDataStructure, LichenNavigation, LichenTransforms, LichenTransformsPrivate, RefTab;
LichenChildishTransforms:
CEDAR
PROGRAM
IMPORTS AbSets, BiRels, IntStuff, LichenDataOps, LichenDataStructure, LichenNavigation, RefTab
EXPORTS LichenTransforms, LichenTransformsPrivate
=
BEGIN OPEN LichenDataStructure, LichenNavigation, LichenTransforms, LichenDataOps, LichenTransformsPrivate, Sets:AbSets;
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: BiRels.CreateHashFn[]
]],
doomedPorts: Sets.CreateHashSet[]
]];
IF childType.firstArray#NIL THEN ERROR nyet;
{OPEN analysis;
oldPort: Port ~ childType.port;
newPort: Port ~ oldPort;
first: BOOL ← TRUE;
dif: BOOL ← FALSE;
parentTypes: VarSet ~ Sets.CreateHashSet[];
childrenV: VarSet ~ Sets.CreateHashSet[];
{
SeeInstance:
PROC [child: CellInstance] = {
sibs: Seq--role é sibling-- = BiRels.DeRef[sibber.ApplyA[child].MA];
IF IsMirror[child] THEN ERROR; --AM2
IF first
THEN {
wag.oldSubjConnectionss ← CreateRefSeq[roles ← sibs.Size.EN];
subjTypes ← sibs.Compose[right: instanceType, restricts: [TRUE, FALSE]].CreateVectorCopy[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 [BiRels.nilBiRel];
NoteChange[childType];
gcs ← CreateSeq[oneToOne: TRUE];
FOR role:
NATURAL
IN [0 .. roles)
DO
gcs.AppendA[Instantiate[
type: NARROW[subjTypes.ApplyI[role].MA],
containingCT: childType]];
ENDLOOP;
{
MaybeDeleteOldChildPort:
PROC [cPort: Port, w: Vertex, e: Edge] = {
wire: Wire = NARROW[w];
IF doomedPorts.HasMemA[cPort] THEN RemoveEdges[e];
};
EnumerateTopEdges[childType.asUnorganized.mirror, MaybeDeleteOldChildPort]};
<<{
PerTopWire:
PROC [pair: BiRels.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.ApplyI[subjPorts.first.role].MA];
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.ApplyI[role].MA];
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.AddA[child];
sibs ← BiRels.DeRef[sibber.ApplyA[child].MA];
IF sibs.Size.EN # roles THEN ERROR --caller blew it--;
FOR role:
NATURAL
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs.ApplyI[role].MA];
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.AddA[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.EN,
subjTypes: gcs.Compose[instanceType].CreateVectorCopy[oneToOne: TRUE].Freeze,
wag:
NEW [WireAnsweringPrivate ← [
oldSubjConnectionss: CreateRefSeq[gcs.Size.EN],
anses: BiRels.CreateHashFn[]
]],
doomedPorts: Sets.CreateHashSet[]
]];
{OPEN analysis;
addedPorts: VarSet = Sets.CreateHashSet[];
parentTypes: VarSet = Sets.CreateHashSet[];
sibberV: VarFunction ~ BiRels.CreateHashFn[];
childType ← NARROW[gcs.First.it[right].VA, CellInstance].containingCT;
typer ← BiRels.CreateSingleton[[AV[childType], AV[subjTypes.Refify]], ALL[SetBasics.refs]];
IF childType.firstArray#NIL THEN ERROR nyet;
FOR role:
NAT
IN [0 .. roles)
DO
gc: CellInstance ~ NARROW[gcs.ApplyI[role].MA];
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.EnumA[DeleteDoomed];
};
{
MaybeAddPort:
PROC [left, right:
REF
ANY] ~ {
wire: Wire ~ NARROW[left];
wa: WireAns ~ NARROW[right];
IF NOT wa.analyzed THEN ERROR;
SELECT wa.doFrom
FROM
addPort => {
wa.fromPort ← AddPort[[parent: newPort, wire: wire]];
[] ← addedPorts.AddA[wa.fromPort];
AddEdge[[childType.asUnorganized.mirror, wire], wa.fromPort]};
leave, dontAdd, dePort => NULL;
ENDCASE => ERROR;
};
wag.anses.EnumAA[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.ApplyI[role].MA];
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.AddAA[child, sibs.Refify];
FOR role:
NATURAL
IN [0 .. roles)
DO
gc: CellInstance = NARROW[gcs.ApplyI[role].MA];
sibs.AppendA[Instantiate[gc.type, child.containingCT]];
ENDLOOP;
{
PerConnection:
PROC [cPort: Port, net: Vertex, ce: Edge] = {
[] ← cons.Store[cPort, net];
IF doomedPorts.HasMemA[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.EnumA[LinkToNewPort]};
FOR role:
NATURAL
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs.ApplyI[role].MA];
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.AddA[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], BiRels.CreateHashFn[]]];
IF sibs.Size # subjTypes.Size
THEN {
Warning["Different number of siblings (%g, rather than %g) at %g", Int[sibs.Size.EI], Int[subjTypes.Size.EI], child];
dif ← TRUE}
ELSE
FOR role:
NATURAL
IN [0 .. roles)
DO
sib: CellInstance = NARROW[sibs.ApplyI[role].MA];
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.ApplyI[j].MA 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.AddA[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.ApplyI[role].
MA # sib.type
THEN {
Warning["%g is a %g, not a %g", sib, sib.type, subjTypes.ApplyI[role].MA];
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.ApplyA[wire].MDA];
IF wa =
NIL
THEN {
IF NOT mayChange THEN ERROR;
wa ← NEW [WireAnsPrivate ← [proto: wire]];
wag.anses.AddNewAA[wire, wa];
};
};
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.