DIRECTORY AbSets, AMBridge, AMTypes, BasicTime, BiRels, IntStuff, IO, LichenDataOps, LichenDataStructure, LichenIntBasics, PrintTV, Rope, SetBasics;

LichenDataImpl2A: CEDAR PROGRAM
IMPORTS AbSets, AMBridge, BiRels, IntStuff, IO, LichenDataOps, LichenDataStructure, LichenIntBasics, PrintTV, SetBasics
EXPORTS LichenDataOps, LichenDataStructure
=

BEGIN OPEN IS:IntStuff, LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps, Sets:AbSets;

CreateDesign: PUBLIC PROC [names: Set--of ROPE--] RETURNS [d: Design] ~ {
IF names.SpaceOf[] # SetBasics.ropes[TRUE] THEN ERROR;
IF names.Empty[] THEN ERROR;
d _ NEW [DesignPrivate];
d.names _ Sets.CreateHashCopy[names];
d.eSpace _ CreateEntitySpace[d];
d.eSetSpace _ Sets.CreateSetSpace[d.eSpace];
d.cellTypes _ Sets.CreateHashSet[d.eSpace];
d.labelCellTypes _ Sets.CreateHashSet[d.eSpace];
d.crossedCellTypes _ Sets.CreateHashSet[d.eSpace];
d.transistorCellTypes _ Sets.CreateFilter[[CTIsTransistor, d.eSpace, d]];
d.sub _ BiRels.CreateHashFn[spaces: [d.eSpace, SetBasics.refs], invable: FALSE];
d.parent _ BiRels.CreateHashFn[spaces: ALL[d.eSpace], invable: TRUE];
d.ancest _ d.parent.TransitiveFnClosure[TRUE];
d.toRoot _ d.parent.ExtremeFnClosure[];
d.pwUpward _ d.parent.ClosureOrder[];
d.pwDownward _ d.pwUpward.ReversePO[];
d.nontriviallyConnectedWires _ Sets.CreateFilter[[WireNontriviallyConnected, d.eSpace, d]];
d.wiresConnectedAtSomeInstance _ Sets.CreateFilter[[WireConnectedAtSomeInstance, d.eSpace, d]];
d.cct _ [
p: BiRels.CreateHashFn[spaces: [d.eSpace, d.eSpace], invable: TRUE],
w: BiRels.CreateHashFn[spaces: [d.eSpace, d.eSpace], invable: TRUE],
i: BiRels.CreateHashFn[spaces: [d.eSpace, d.eSpace], invable: TRUE]];
d.partses _ [d.cct[p].SetOn[left], d.cct[w].SetOn[left], d.cct[i].SetOn[left]];
d.pws _ d.partses[p].Union[d.partses[w], TRUE];
d.parts _ d.pws.Union[d.partses[i], TRUE];
d.isntTop _ d.parent.SetOn[left];
d.isComposite _ d.sub.SetOn[left];
d.isTop _ d.pws.Difference[d.isntTop];
d.isAtomic _ d.pws.Difference[d.isComposite];
d.ciType _ BiRels.CreateHashFn[spaces: [d.eSpace, d.eSpace], invable: TRUE];
d.ctName _ BiRels.CreateHashReln[spaces: [d.eSpace, SetBasics.ropes[TRUE]]];
d.arrayElt _ BiRels.CreateHashFn[spaces: ALL[d.eSpace], invable: TRUE];
d.ciXfm _ BiRels.CreateHashTable[[d.eSpace, xfmSpace]];
{w2i: Fn ~ BiRels.FnFromProc[WireToInstances, [d.eSpace, d.eSetSpace], d];
i2w: Fn ~ BiRels.FnFromProc[InstanceToWires, [d.eSpace, d.eSetSpace], d];
d.iwConns _ BiRels.CreateFromHalves[
spaces: ALL[d.eSpace],
halves: [[dullHalfClass, i2w], [dullHalfClass, w2i]]]};
d.scale _ 0.0;
d.inheritNames _ FALSE;
d.physd _ TRUE;
d.other _ BiRels.CreateHashTable[];
RETURN};

CTIsTransistor: PROC [val: Sets.Value, data: REF ANY _ NIL] RETURNS [BOOL] ~ {
ct: CellType ~ NARROW[val.VA];
RETURN [ct.asTrans # NIL]};

WireNontriviallyConnected: PROC [val: Sets.Value, data: REF ANY _ NIL] RETURNS [BOOL] ~ {
w: Wire ~ NARROW[val.VA];
RETURN [w.conns.Size[IS.two].Compare[IS.two] >= equal]};

WireConnectedAtSomeInstance: PROC [val: Sets.Value, data: REF ANY _ NIL] RETURNS [BOOL] ~ {
w: Wire ~ NARROW[val.VA];
d: Design ~ NARROW[data];
RETURN [w.conns.ScanHalfRestriction[d.partses[i], BiRels.AcceptAny, right].found]};

WireToInstances: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ {
w: Wire ~ NARROW[v.VA];
d: Design ~ NARROW[data];
RETURN [[TRUE, w.conns.SetOn[right].SV[]]]};

InstanceToWires: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ {
ci: CellInstance ~ NARROW[v.VA];
d: Design ~ NARROW[data];
RETURN [[TRUE, ci.conns.SetOn[right].SV[]]]};

CreateEntitySpace: PROC [d: Design] RETURNS [Sets.Space] ~ {
RETURN [NEW [SetBasics.SpacePrivate _ [
Contains: EntityContains,
Equal: SetBasics.refs.Equal,
AHash: SetBasics.refs.AHash,
ACompare: SetBasics.refs.ACompare,
Print: EntityPrint,
name: IO.PutFR["entities of %g", [rope[NARROW[d.names.AnElt[].MA] ]] ],
data: d
]]]};

EntityContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
d: Design ~ NARROW[data];
IF v.i#0 THEN RETURN [FALSE];
WITH v.ra SELECT FROM
ct: CellType => RETURN [TRUE];
v: Vertex => RETURN [TRUE];
p: Port => RETURN [TRUE];
ENDCASE => RETURN [FALSE]};

EntityPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
d: Design ~ NARROW[data];
ra: REF ANY ~ v.VA;
WITH ra SELECT FROM
ct: CellType => {
name: ROPE ~ ct.ACtName[];
to.PutRope[name];
};
ENDCASE => {
class: PartClass ~ WITH ra SELECT FROM
p: Port => p,
w: Wire => w,
ci: CellInstance => i,
ENDCASE => ERROR;
cct: CellType ~ NARROW[d.cct[class].Apply[v].MA];
mv: Sets.MaybeValue ~ cct.fullName[class].Lookup[goal: v, side: left];
IF mv.found
THEN to.PutRope[UnparseSteppyName[VSn[mv.it]]]
ELSE PrintTV.Print[RaTv[ra], to, depth, length, verbose];
RETURN};
};

fullNameHints: PUBLIC BiRels.HintPair ~ [
leftToRight: [
fn: [$Hash],
set: [$List, LIST[[$RelOrder, $fwd]]]
],
rightToLeft: [
fn: [$Hash],
set: [$Hash]
]];

CreateCellType: PUBLIC PROC [d: Design, flavor: CellFlavor, names: Set--of ROPE--] RETURNS [ct: CellType] ~ {
ct _ NEW [CellTypePrivate _ [
d: d,
fullName: [
p: BiRels.GenCreate[spaces: [d.eSpace, steppyNameSpace], hints: fullNameHints],
w: nilBiRel,
i: nilBiRel],
bbox: IF d.physd THEN emptyRange2 ELSE fullRange2,
other: BiRels.CreateHashTable[]
]];
ct.nameOrder[p] _ BiRels.MapOrder[ct.fullName[p], leftToRight, Sets.fwd];
IF NOT d.cellTypes.AddA[ct] THEN ERROR;
[] _ d.ctName.AddSet[BiRels.CreateProduct[[Sets.CreateSingleA[ct, d.eSpace], names]]];
IF flavor=unorganized THEN FinishCreatingUnorganized[ct];
RETURN};
dullHalfClass: BiRels.HalfClass ~ NEW [BiRels.HalfClassPrivate _ [NIL]];

FinishCreatingUnorganized: PUBLIC PROC [ct: CellType] ~ {
d: Design ~ ct.d;
exports: BiRel ~ BiRels.CreateHashFn[[d.eSpace, d.eSpace]];
wires: Set ~ ct.CTParts[w];
ports: Set ~ ct.CTParts[p];
ntPorts: Set ~ ports.Intersection[d.isntTop];
ct.fullName[w] _ BiRels.GenCreate[spaces: [d.eSpace, steppyNameSpace], hints: fullNameHints];
ct.fullName[i] _ BiRels.GenCreate[spaces: [d.eSpace, steppyNameSpace], hints: fullNameHints];
ct.nameOrder[w] _ BiRels.MapOrder[ct.fullName[w], leftToRight, Sets.fwd];
ct.nameOrder[i] _ BiRels.MapOrder[ct.fullName[i], leftToRight, Sets.fwd, Sets.alleq];
ct.asu _ NEW [UnorganizedPrivate _ [
exports: exports,
publics: exports.SetOn[right]
]];
ct.asu.notPublics _ wires.Difference[ct.asu.publics];
ct.asu.troubled _ d.ancest.Image[ exports.Image[ntPorts] .Intersection[ d.parent.Image[ct.asu.notPublics, rightToLeft]]];
ct.asu.exportable _ ct.asu.notPublics.Difference[ct.asu.troubled];
RETURN};

CreatePort: PUBLIC PROC [ct: CellType, fullNames: Set--of SteppyName--, deduced, addum, nameDum, fixExpConns, fixInstConns, fixWExpConns, fixWInstConns: BOOL, children: Seq--of Port-- _ nilBiRel] RETURNS [p: Port] ~ {
d: Design ~ ct.d;
atomic: BOOL ~ children = nilBiRel;
FixUse: PROC [use: CellUse] ~ {WITH use SELECT FROM
ci: CellInstance => {
cct: CellType ~ d.CiCct[ci];
kidWires: Seq _ nilBiRel;
w: Wire _ NIL;
{IF NOT atomic THEN {
kidWires _ children.Compose[ci.conns];
IF kidWires.Size#children.Size THEN GOTO DontConnect;
{ssi: SubsIndex ~ d.SubseqIndex[kidWires];
IF ssi.multiparents THEN GOTO DontConnect;
IF ssi.full THEN {w _ NARROW[ssi.parent]; GOTO Connect};
IF NOT addum THEN GOTO DontConnect;
IF ssi.parent#NIL THEN GOTO DontConnect;
kidWires _ kidWires.CreateVectorCopy}}
ELSE IF NOT addum THEN GOTO DontConnect;
w _ CreateWire[cct, IF d.inheritNames AND nameDum THEN ActualNames[d.labelCellTypes.HasMemA[ct], cct.INames[ci], fullNames] ELSE emptySteppySet, FALSE, fixWExpConns, fixWInstConns, kidWires];
EXITS Connect => use _ use};
Connect[d, w, p, ci];
RETURN
EXITS DontConnect => ct _ ct};
act: CellType => NoteNewEltPort[act, p];
ENDCASE => ERROR};
p _ NEW [PortPrivate _ []];
d.cct[p].AddNewAA[p, ct];
KnowPortNames[ct, p, fullNames, FALSE];
IF children # nilBiRel THEN {
nKids: NAT ~ children.Size.EN;
IF children.GetIntDom # [0, nKids-1] THEN ERROR;
d.sub.AddNewAA[p, children.Refify];
[] _ d.parent.AddSet[BiRels.CreateProduct[[children.SetOn[right], Sets.CreateSingleA[p, d.eSpace]]]];
IF fixExpConns THEN {
IF ct.asu#NIL THEN ClosePortConnectivity[d, p, children, ct.asu.exports, ct];
IF ct.asArray#NIL THEN NoteNewArrayPort[ct, p]};
};
IF addum OR (fixInstConns AND NOT atomic) THEN ct.EnumerateUses[FixUse];
RETURN};

ClosePortsConnectivity: PUBLIC PROC [d: Design, parents: Set--of Port--, conns: Fn--Port _ Wire--, site: Cell] ~ {
CloseParent: PROC [pv: Sets.Value] RETURNS [BOOL] ~ {
parent: Port ~ NARROW[pv.VA];
kidPorts: Seq ~ d.SubSeq[parent];
ClosePortConnectivity[d, parent, kidPorts, conns, site];
RETURN [FALSE]};
IF parents.Scan[CloseParent].found THEN ERROR;
RETURN};

ClosePortConnectivity: PUBLIC PROC [d: Design, parent: Port, kidPorts: Seq--of Port--, conns: Fn--Port _ Wire--, site: Cell] ~ {
DO
kidWires: Seq--of Wire-- ~ kidPorts.Compose[conns];
IF kidWires.Size#kidPorts.Size THEN RETURN;
{si: SubsIndex ~ d.SubseqIndex[kidWires];
IF NOT si.full THEN RETURN;
IF si.parent=NIL THEN ERROR;
Connect[d, NARROW[si.parent], parent, site];
parent _ d.PParent[parent];
IF parent=NIL THEN RETURN;
kidPorts _ d.SubSeq[parent];
}ENDLOOP;
};

CreateWire: PUBLIC PROC [ct: CellType, fullNames: Set--of SteppyName--, deduced, fixExpConns, fixInstConns: BOOL, children: Seq--of Wire-- _ nilBiRel] RETURNS [w: Wire] ~ {
d: Design ~ ct.d;
FixConn: PROC [porta: REF ANY, site: Cell] ~ {
p0: Port ~ NARROW[porta];
pp: Port ~ d.PParent[p0];
IF pp=NIL THEN RETURN;
IF NOT ((fixExpConns AND fixInstConns) OR (WITH site SELECT FROM ci: CellInstance => fixInstConns, ct: CellType => fixExpConns, ENDCASE => ERROR)) THEN RETURN;
{kidPorts: Seq ~ BiRels.DeRef[d.sub.ApplyA[pp].MA];
kidWires: Seq ~ kidPorts.Compose[SiteConns[site]];
IF kidWires.Equal[children] THEN Connect[d, w, pp, site];
RETURN}};
w _ CreateBareWire[d];
d.cct[w].AddNewAA[w, ct];
KnowVertexNames[ct, w, fullNames, FALSE];
IF children # nilBiRel THEN {
nKids: NAT ~ children.Size.EN;
IF children.GetIntDom # [0, nKids-1] THEN ERROR;
d.sub.AddNewAA[w, children.Refify];
[]_ d.parent.AddSet[BiRels.CreateProduct[[children.SetOn[right], Sets.CreateSingleA[w, d.eSpace]]]];
IF fixExpConns OR fixInstConns THEN {
c0: Wire ~ NARROW[children.ApplyI[0].MA];
c0.conns.EnumAA[FixConn];
w _ w};
w _ w};
RETURN};

CreateBareWire: PUBLIC PROC [d: Design] RETURNS [Wire] ~ {
RETURN [NEW [VertexPrivate[w] _ [variant: w[conns: BiRels.CreateHashReln[spaces: ALL[d.eSpace]]] ]]]};

CreateBareInstance: PUBLIC PROC [d: Design, offset: Int2] RETURNS [CellInstance] ~ {
RETURN [NEW [VertexPrivate.i _ [variant: i[BiRels.CreateHashFn[ALL[d.eSpace]], offset]]]]};

Instantiate: PUBLIC PROC [ict, cct: CellType, addum: BOOL, xfm: Transform, offset: Int2, names: Set--of SteppyName--] RETURNS [ci: CellInstance] ~ {
d: Design ~ ict.d;
ci _ CreateBareInstance[d, offset];
d.cct[i].AddNewAA[ci, cct];
d.ciType.AddNewAA[ci, ict];
IF d.physd THEN {
d.ciXfm.AddNewPair[[AV[ci], XfmV[xfm]]];
cct.bbox _ Range2Mbb[cct.bbox, TransOffRange2[xfm, offset, ict.bbox]]}
ELSE ci.offset _ dullInt2;
KnowVertexNames[cct, ci, names, FALSE];
IF addum THEN {
DumPort: PROC [pval: Sets.Value] RETURNS [BOOL] ~ {
p: Port ~ NARROW[pval.VA];
kidPorts: Seq ~ d.SubSeq[p];
kidWires: Seq ~ IF kidPorts#nilBiRel THEN kidPorts.Compose[ci.conns] ELSE nilBiRel;
IF kidPorts#nilBiRel AND kidPorts.Size # kidWires.Size THEN ERROR;
{w: Wire ~ CreateWire[cct, IF d.inheritNames THEN ActualNames[d.labelCellTypes.HasMemA[ict], names, ict.PNames[p]] ELSE emptySteppySet, FALSE, FALSE--don't bother, we know it's private--, FALSE--don't bother, it's taken care of by me--, kidWires];
Connect[d, w, p, ci];
RETURN [FALSE]}};
IF ict.CTParts[p].Scan[DumPort, d.pwUpward].found THEN ERROR;
ci _ ci};
RETURN};

RaTv: PROC [ra: REF ANY] RETURNS [AMTypes.TV] ~ TRUSTED {
RETURN AMBridge.TVForReferent[NEW [REF ANY _ ra], const]};

END.
^LichenDataImpl2A.Mesa
Last tweaked by Mike Spreitzer on November 3, 1988 2:35:00 pm PST
ΚΨ–

"cedar" style˜
code™K™A—K˜KšΟk	œ9œP˜”
K˜šΟnœœ
˜Kšœ%œI˜wKšœ#˜*K˜
—K˜Kšœ
œ
œœœ&žœ˜bK˜š
žœœ
œΟcœœ˜IKšœ#œœ
œ
˜6Kšœœ
œ
˜Kšœœ˜K˜%K˜ Kš
œ,˜,Kš
œ+˜+Kš
œ0˜0Kš
œ2˜2Kš
œI˜IKšœIœ˜PKšœ'œœ˜EKšœ(œ˜.Kš
œ'˜'Kš
œ%˜%Kš
œ&˜&Kš
œ[˜[Kš
œ_˜_˜	Kšœ>œ˜DKšœ>œ˜DKšœ>œ˜E—K˜OKšœ)œ˜/Kšœ$œ˜*K˜!Kš
œ"˜"Kš
œ&˜&Kš
œ-˜-KšœFœ˜LKšœDœ˜LKšœ)œœ˜GKš
œ7˜7Kš
œJ˜JKš
œI˜Iš
œ$˜$Kšœœ˜Kš
œ7˜7—K˜Kšœœ
˜Kšœ
œ
˜K˜#Kšœ˜—K˜šžœœœ
œœœœ˜NKšœœœ˜Kšœœ˜—K˜šžœœœ
œœœœ˜YKšœ
œœ˜Kšœœœ˜8—K˜šžœœœ
œœœœ˜[Kšœ
œœ˜Kšœœ˜KšœM˜S—K˜š
žœœœ
œœ˜VKšœ
œœ˜Kšœœ˜Kšœœœ˜,—K˜š
žœœœ
œœ˜VKšœœœ˜ Kšœœ˜Kšœœœ˜-—K˜šžœœ
œ˜<šœœ˜'Kšžœ˜Kšžœ˜Kšžœ˜Kšžœ˜"Kšžœ˜Kšœœœœ˜GKš
œ˜K˜——K˜šžœœœ
œœœ˜FKšœœ˜Kšœœ
œœ˜šœœ
˜Kšœœœ˜Kšœ
œœ˜Kšœœœ˜Kšœœœ˜——K˜šžœœœ
œœ
œœœ˜fKšœœ˜Kšœœ
œœ
˜šœœ
˜˜Kšœœ˜K˜K˜—šœ˜šœœœ
˜&Kš
œ
˜
K˜
K˜Kšœœ
˜—Kšœœœ˜1K˜Fšœ	˜Kšœ*˜.Kšœ5˜9—Kšœ˜——K˜—K˜šœœ˜)˜K˜Kšœ
œ˜%K˜—˜K˜K˜K˜——K˜š
žœœ
œ+Ÿœœ˜mšœœ˜K˜˜Kš
œO˜OK˜K˜
—Kšœœ	œ
œ˜2K˜K˜—Kš
œI˜IKšœ
œœ
œ
˜'Kš
œV˜VKšœœ˜9Kšœ˜Kšœ"œœ˜H—K˜šžœœ
œ˜9K˜Kš
œ;˜;K˜K˜Kš
œ-˜-Kš
œ]˜]Kš
œ]˜]Kš
œI˜IKš
œU˜Ušœ	œ˜$K˜K˜K˜—K˜5Kš
œy˜yK˜BKšœ˜—K˜šž
œœ
œŸœSœŸœ
œ˜Ω
K˜Kšœœ˜#š	žœœœœ
˜3š
œ˜K˜K˜Kšœ
œ
˜šœ
œ
œœ˜Kš
œ&˜&Kšœœ
œ
˜5Kš
œ*˜*Kšœœ
œ
˜*Kšœ
œœœ
˜8Kšœ
œœ
œ
˜#Kšœœ
œ
œ
˜(Kš
œ&˜&—Kš
œ
œ
œœ
œ
˜(Kšœœœ	œFœœ)˜Ώ
Kšœ˜Kš
œ˜Kš
˜Kšœ˜—K˜(Kšœœ˜—Kšœœ˜Kš
œ˜Kšœ œ˜'šœœ˜Kšœœœ
˜Kšœ#œ
œ
˜0Kš
œ#˜#Kš
œe˜ešœ
œ˜Kšœœ
œ;˜MKšœœ
œ˜0—K˜—Kš
œœœ
œ	œ˜HKšœ˜—K˜šžœœ
œŸœŸΠcm
Ÿœ˜ršžœœœœ˜5Kšœœœ˜Kš
œ!˜!Kš
œ8˜8Kšœœ˜—Kšœ!œ
œ
˜.Kšœ˜—K˜šžœœ
œ(ŸœŸ 
Ÿœ˜€
š
˜Kšœ
Ÿœ˜3Kšœœ
œ
˜+Kš
œ)˜)Kšœ
œ	œ
œ
˜Kšœœ
œ
œ
˜Kšœœ˜,Kš
œ˜Kšœœ
œ
œ
˜K˜Kšœ
œ
˜	—Kš
œ˜—K˜šž
œœ
œŸœ&œŸœ
œ˜¬
K˜šžœœ	œ
œ˜.Kšœœ˜Kš
œ˜Kšœœ
œ
œ
˜Kšœ
œœœœœ
œ@œœœ
œ
˜Ÿ
Kšœ/œ˜3Kš
œ2˜2Kšœœ˜9Kšœ˜	—Kš
œ˜Kš
œ˜Kšœ"œ˜)šœœ˜Kšœœœ
˜Kšœ#œ
œ
˜0Kš
œ#˜#Kš
œd˜dšœ
œœ˜%Kšœœœ˜)K˜K˜—K˜—Kšœ˜—K˜šžœœ
œ
œ˜:KšœœFœ˜f—K˜šžœœ
œœ˜TKšœœ4œ˜[—K˜šžœœ
œœ*Ÿœœ˜”
K˜Kš
œ#˜#Kš
œ˜Kš
œ˜šœ	œ˜Kšœœ˜(Kš
œF˜F—Kšœ˜Kšœ œ˜'šœœ˜šžœœœœ˜3Kšœ
œœ˜Kš
œ˜Kšœœœœ
˜SKšœœœ
œ
˜BKšœœœBœœŸ&œŸ*œ˜χ
Kš
œ˜Kšœœ˜—Kšœ0œ
œ
˜=Kš
œ	˜	—Kšœ˜—K˜šžœœœ
œœ
œœ˜9Kšœœœ
œ˜:—K˜Kšœ
˜—…—.*;`