LichenDataImpl1A.Mesa
Last tweaked by Mike Spreitzer on April 12, 1989 0:38:00 am PDT
DIRECTORY AbSets, BasicTime, BiRels, Convert, IntStuff, LichenDataStructure, LichenIntBasics, List, Rope, SetBasics;
LichenDataImpl1A: CEDAR PROGRAM
IMPORTS AbSets, BiRels, Convert, IntStuff, LichenDataStructure, List, Rope, SetBasics
EXPORTS LichenDataStructure
=
BEGIN OPEN IB:LichenIntBasics, IB, LichenDataStructure, Sets:AbSets;
PIndex: PUBLIC PROC [d: Design, ep: Port, parent: Port ← NIL] RETURNS [LNAT] ~ {
IF parent=NIL THEN parent ← d.PParent[ep];
{children: Seq--of child-- ~ BiRels.DeRef[d.sub.ApplyA[parent].MA];
RETURN [children.Lookup[AV[ep]].MI]}};
WIndex: PUBLIC PROC [d: Design, ew: Wire, parent: Wire ← NIL] RETURNS [LNAT] ~ {
IF parent=NIL THEN parent ← d.WParent[ew];
{children: Seq--of child-- ~ BiRels.DeRef[d.sub.ApplyA[parent].MA];
RETURN [children.Lookup[AV[ew]].MI]}};
SubseqIndex: PUBLIC PROC [d: Design, kids: Seq] RETURNS [ssi: SubsIndex ← [NIL, FALSE, FALSE, FALSE, 0]] ~ {
parentskids: Seq ← nilBiRel;
first: BOOLTRUE;
PerKid: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
index: INT ~ pair[left].VI;
kid: PW ~ pair[right].VA;
IF first THEN {
first ← FALSE;
ssi.parent ← d.parent.ApplyA[kid].MDA;
IF ssi.parent=NIL THEN RETURN [FALSE];
ssi.sub ← TRUE;
parentskids ← BiRels.DeRef[d.sub.ApplyA[ssi.parent].MA];
ssi.offset ← parentskids.Lookup[AV[kid]].MI - index;
RETURN [FALSE]}
ELSE {
ssi.multiparents ← ssi.multiparents OR d.parent.ApplyA[kid].MDA # ssi.parent;
ssi.sub ← ssi.sub AND (NOT ssi.multiparents) AND parentskids.ApplyI[index + ssi.offset].MDA = kid;
RETURN[ssi.multiparents]};
};
[] ← kids.Scan[PerKid, BiRels.leftFwd];
ssi.full ← ssi.sub AND ssi.offset=0 AND parentskids.Size=kids.Size;
RETURN};
ExportableKids: PUBLIC PROC [ct: CellType, kids: Seq--of Wire--] RETURNS [BOOL] ~ {
RETURN [kids.SkipTo[ct.asu.troubled].found]};
TopParts: PUBLIC PROC [ct: CellType, class: PWClass] RETURNS [Set] ~ {
RETURN[ ct.d.cct[class].MappingA[ct, rightToLeft].Intersection[ct.d.isTop]]};
EnumCTParts: PUBLIC PROC [ct: CellType, class: PartClass, atomic, composite: BOOL, Consume: PROC [Part]] ~ {
PassPart: PROC [v: Sets.Value] ~ {
part: REF ANY ~ v.VA;
IF (atomic AND composite) OR (IF ct.d.Atomic[part] THEN atomic ELSE composite) THEN Consume[v.VA];
RETURN};
IF atomic OR composite THEN ct.d.cct[class].EnumerateMapping[AV[ct], PassPart, rightToLeft];
RETURN};
NonPublicDescendants: PUBLIC PROC [ct: CellType, w: Wire] RETURNS [Set] ~ {
RETURN [PWDescendants[ct.d, w].Difference[ct.asu.publics]]};
Subcells: PUBLIC PROC [ct: CellType] RETURNS [Set--of CellInstance--] ~ {
RETURN ct.d.cct[i].MappingA[ct, rightToLeft]};
TypeSites: PUBLIC PROC [ct: CellType] RETURNS [Set--of Cell--] ~ {
RETURN [Subcells[ct].Union[Sets.CreateSingleA[ct, ct.d.eSpace]]]};
SiteConns: PUBLIC PROC [site: Cell] RETURNS [conns: Fn--Port b Wire--] ~ {
WITH site SELECT FROM
ct: CellType => conns ← ct.asu.exports;
ci: CellInstance => conns ← ci.conns;
ENDCASE => ERROR;
RETURN};
CTParts: PUBLIC PROC [ct: CellType, class: PartClass] RETURNS [Set] ~ {
RETURN [ct.d.cct[class].MappingA[ct, rightToLeft]]};
ConndWire: PUBLIC PROC [c: Cell, p: Port] RETURNS [Wire] ~ {
WITH c SELECT FROM
ct: CellType => {
IF ct.asu=NIL THEN ERROR;
RETURN [NARROW[ct.asu.exports.ApplyA[p].MDA]]};
ci: CellInstance => RETURN [NARROW[ci.conns.ApplyA[p].MDA]];
ENDCASE => ERROR;
};
AConndPort: PUBLIC PROC [c: Cell, w: Wire] RETURNS [Port] ~ {
conns: Fn--Port b Wire-- ~ WITH c SELECT FROM
ct: CellType => ct.asu.exports,
ci: CellInstance => ci.conns,
ENDCASE => ERROR;
RETURN [NARROW[conns.Lookup[goal: AV[w], order: Sets.alleq].MDA]]};
NFetchCellType: PUBLIC PROC [d: Design, name: ROPE] RETURNS [CellType]
~ {RETURN d.FetchCellType[name]};
Unused: PUBLIC PROC [ct: CellType] RETURNS [BOOL] ~ {
RETURN [ct.d.ciType.MappingEmpty[AV[ct], rightToLeft] AND ct.d.arrayElt.MappingEmpty[AV[ct], rightToLeft]]};
EnumerateUses: PUBLIC PROC [ct: CellType, Consume: PROC [CellUse]] ~ {
Convert: PROC [civ: Sets.Value] ~ {Consume[civ.VA]; RETURN};
ct.d.arrayElt.EnumerateMapping[AV[ct], Convert, rightToLeft];
ct.d.ciType.EnumerateMapping[AV[ct], Convert, rightToLeft];
RETURN};
ActualName: PUBLIC PROC [lab: BOOL, cin, pn: SteppyName] RETURNS [an: SteppyName] ~ {
IF lab OR pn.grade.global THEN RETURN [pn];
IF cin=noName THEN RETURN [pn];
IF pn=noName THEN RETURN [cin];
an ← SNCat[cin, pn];
RETURN};
ActualNames: PUBLIC PROC [lab: BOOL, cins, pns: Set--of SteppyName--] RETURNS [acts: Set] ~ {
Outer: PROC [pnv: Sets.Value] ~ {
pn: SteppyName ~ VSn[pnv];
Inner: PROC [cinv: Sets.Value] ~ {
cin: SteppyName ~ VSn[cinv];
act: SteppyName ~ SNCat[cin, pn];
[] ← acts.AddElt[SnV[act]];
RETURN};
IF lab OR pn.grade.global THEN [] ← acts.AddElt[pnv] ELSE cins.Enumerate[Inner];
RETURN};
acts ← Sets.CreateHashSet[steppyNameSpace];
pns.Enumerate[Outer];
RETURN};
SNsCat: PUBLIC PROC [as, bs: Set--of SteppyName--] RETURNS [cs: Set--of SteppyName--] ~ {
Outer: PROC [av: Sets.Value] ~ {
an: SteppyName ~ VSn[av];
Inner: PROC [bv: Sets.Value] ~ {
bn: SteppyName ~ VSn[bv];
cn: SteppyName ~ SNCat[an, bn];
[] ← cs.AddElt[SnV[cn]];
RETURN};
bs.Enumerate[Inner];
RETURN};
cs ← Sets.CreateHashSet[steppyNameSpace];
as.Enumerate[Outer];
RETURN};
RSNCat: PUBLIC PROC [a: RootedSteppyName, b: SteppyName] RETURNS [RootedSteppyName] ~ {
RETURN [[SNCat[a.name, b], a.unrel]]};
SNCat: PUBLIC PROC [a, b: SteppyName] RETURNS [SteppyName] ~ {
IF b=noName THEN RETURN [a];
IF a=noName THEN RETURN [b];
IF b.grade.nonsubs>0 THEN RETURN [[
steps: List.Append[a.steps, b.steps],
grade: [
global: b.grade.global,
power: b.grade.power,
nonsubs: a.grade.nonsubs + b.grade.nonsubs,
gend: b.grade.gend,
subs: a.grade.subs + b.grade.subs]
]];
RETURN [[
steps: List.Append[a.steps, b.steps],
grade: [
global: a.grade.global,
power: a.grade.power,
nonsubs: a.grade.nonsubs,
gend: a.grade.gend,
subs: a.grade.subs + b.grade.subs]
]]};
SNPrepend: PUBLIC PROC [ns: NameStep, sn: SteppyName] RETURNS [SteppyName] ~ {
ans: SteppyName ← [steps: CONS[ns, sn.steps], grade: sn.grade];
WITH ns SELECT FROM
x: ROPE => IF (ans.grade.nonsubs ← ans.grade.nonsubs+1) = 1 THEN [ans.grade.global, ans.grade.power, ans.grade.gend] ← Analast[x];
x: REF INT => {ans.grade.subs ← ans.grade.subs+1};
ENDCASE => ERROR;
RETURN [ans]};
SNAppend: PUBLIC PROC [sn: SteppyName, ns: NameStep] RETURNS [SteppyName] ~ {
ans: SteppyName ← [steps: List.Append[sn.steps, LIST[ns]], grade: sn.grade];
WITH ns SELECT FROM
x: ROPE => {
ans.grade.nonsubs ← ans.grade.nonsubs+1;
[ans.grade.global, ans.grade.power, ans.grade.gend] ← Analast[x]};
x: REF INT => ans.grade.subs ← ans.grade.subs+1;
ENDCASE => ERROR;
RETURN [ans]};
SNTail: PUBLIC PROC [sn: SteppyName] RETURNS [SteppyName] ~ {
WITH sn.steps.first SELECT FROM
x: ROPE => IF sn.grade.nonsubs>1
THEN RETURN [[sn.steps.rest, [
global: sn.grade.global, power: sn.grade.power, gend: sn.grade.gend,
subs: sn.grade.subs, nonsubs: sn.grade.nonsubs-1]]]
ELSE RETURN [[sn.steps.rest, [
global: noGrade.global, power: noGrade.power, gend: noGrade.gend,
subs: sn.grade.subs, nonsubs: sn.grade.nonsubs-1]]];
x: REF INT => RETURN [[sn.steps.rest, [
global: sn.grade.global, power: sn.grade.power, gend: sn.grade.gend,
subs: sn.grade.subs-1, nonsubs: sn.grade.nonsubs]]];
ENDCASE => ERROR};
SNthTail: PUBLIC PROC [sn: SteppyName, n: NATURAL] RETURNS [SteppyName] ~ {
IF n=0 THEN RETURN [sn];
{steps: NameStepList ← sn.steps;
THROUGH [1 .. n] DO steps ← steps.rest ENDLOOP;
RETURN LSn[steps]}};
ScanRelativeNames: PUBLIC PROC [ct: CellType, class: PWClass, anc, des: PW, Test: PROC [SteppyName] RETURNS [BOOL]] RETURNS [msn: MaybeSteppyName ← [FALSE, noName]] ~ {
countA: LNAT ~ ct.fullName[class].MappingSize[AV[anc]].EN;
countD: LNAT ~ ct.fullName[class].MappingSize[AV[des]].EN;
OuterA: PROC [va: Sets.Value] RETURNS [BOOL] ~ {
na: SteppyName ~ VSn[va];
InnerD: PROC [vd: Sets.Value] RETURNS [BOOL] ~ {
nd: SteppyName ~ VSn[vd];
RETURN [(msn ← SteppyIsPrefix[na, nd]).found]};
RETURN [ct.fullName[class].ScanMapping[AV[des], InnerD].found]};
OuterD: PROC [vd: Sets.Value] RETURNS [BOOL] ~ {
nd: SteppyName ~ VSn[vd];
InnerA: PROC [va: Sets.Value] RETURNS [BOOL] ~ {
na: SteppyName ~ VSn[va];
RETURN [(msn ← SteppyIsPrefix[na, nd]).found]};
RETURN [ct.fullName[class].ScanMapping[AV[anc], InnerA].found]};
IF countA < countD
THEN [] ← ct.fullName[class].ScanMapping[AV[anc], OuterA]
ELSE [] ← ct.fullName[class].ScanMapping[AV[des], OuterD];
RETURN};
AcceptAnySteppyName: PUBLIC PROC [SteppyName] RETURNS [BOOL] ~ {RETURN [TRUE]};
SteppyIsSub: PROC [sub, full: SteppyName] RETURNS [MaybeSteppyName] ~ {
IF sub.grade.nonsubs>full.grade.nonsubs OR sub.grade.subs>full.grade.subs THEN RETURN [[FALSE, noName]];
{ls: NameStepList ← sub.steps;
lf: NameStepList ← full.steps;
head, tail: NameStepList ← NIL;
WHILE ls#NIL AND lf#NIL DO
IF nameStepSpace.SEqual[AV[ls.first], AV[lf.first]] THEN {
ls ← ls.rest;
}
ELSE {
this: NameStepList ~ LIST[lf.first];
IF tail=NIL THEN head ← this ELSE tail.rest ← this;
tail ← this;
};
lf ← lf.rest;
ENDLOOP;
IF ls#NIL THEN RETURN [[FALSE, noName]];
IF tail=NIL THEN head ← lf ELSE tail.rest ← lf;
RETURN [[TRUE, LSn[head]]]}};
SteppyIsPrefix: PUBLIC PROC [prefix, full: SteppyName] RETURNS [MaybeSteppyName] ~ {
IF prefix.grade.nonsubs>full.grade.nonsubs OR prefix.grade.subs>full.grade.subs THEN RETURN [[FALSE, noName]];
{tail: NameStepList ~ List.NthTail[full.steps, prefix.grade.nonsubs+prefix.grade.subs];
IF NOT NameStepListEqual[prefix.steps, full.steps, NIL, tail] THEN RETURN [[FALSE, noName]];
{suffix: SteppyName ~ LSn[tail];
ok: BOOL ~ IF suffix.grade.nonsubs>0
THEN full.grade.global=suffix.grade.global AND full.grade.power=suffix.grade.power AND full.grade.nonsubs=prefix.grade.nonsubs+suffix.grade.nonsubs AND full.grade.gend=suffix.grade.gend AND full.grade.subs=prefix.grade.subs+suffix.grade.subs
ELSE full.grade.global=prefix.grade.global AND full.grade.power=prefix.grade.power AND full.grade.nonsubs=prefix.grade.nonsubs AND full.grade.gend=prefix.grade.gend AND full.grade.subs=prefix.grade.subs+suffix.grade.subs;
IF ok THEN RETURN [[TRUE, suffix]] ELSE RETURN [[FALSE, noName]]}}};
LT: TYPE ~ RECORD [l, t: NameStepList];
LSn: PUBLIC PROC [l: NameStepList] RETURNS [SteppyName] ~ {
RETURN [[l, Grade[l]]]};
Grade: PROC [steps: NameStepList] RETURNS [grade: SteppyNameGrade ← [FALSE, FALSE, 0, FALSE, 0]] ~ {
last: ROPENIL;
FOR steps ← steps, steps.rest WHILE steps#NIL DO
WITH steps.first SELECT FROM
x: ROPE => {
grade.nonsubs ← grade.nonsubs+1;
last ← x};
x: REF INT => grade.subs ← grade.subs+1;
ENDCASE => ERROR;
ENDLOOP;
IF last#NIL THEN [grade.global, grade.power, grade.gend] ← Analast[last];
RETURN};
Analast: PROC [last: ROPE] RETURNS [global, power, gend: BOOLFALSE] ~ {
xLen: INT ~ last.Length;
SELECT last.InlineFetch[xLen-1] FROM
'! => global ← TRUE;
'# => gend ← TRUE;
ENDCASE => gend ← last.InlineFetch[0] = '&;
power ← Rope.Match["gnd*", last, FALSE] OR Rope.Match["vdd*", last, FALSE];
RETURN};
OSn: PUBLIC PROC [ns: NameStep] RETURNS [SteppyName]
~ {RETURN LSn[LIST[ns]]};
OneRope: PUBLIC PROC [r: ROPE] RETURNS [Set--of ROPE--]
~ {RETURN [Sets.CreateSingleA[r, SetBasics.ropes[TRUE]]]};
OneSteppy: PUBLIC PROC [sn: SteppyName] RETURNS [Set--of SteppyName--]
~ {RETURN [Sets.CreateSingleton[SnV[sn], steppyNameSpace]]};
OneLSn: PUBLIC PROC [nsl: NameStepList] RETURNS [Set--of SteppyName--]
~ {RETURN OneSteppy[LSn[nsl]]};
OneOSn: PUBLIC PROC [ns: NameStep] RETURNS [Set--of SteppyName--]
~ {RETURN OneSteppy[OSn[ns]]};
ParseL: PUBLIC PROC [rs: LOR] RETURNS [sns: Set--of SteppyName--] ~ {
sns ← Sets.CreateRedBlackSet[steppyNameSpace];
FOR rs ← rs, rs.rest WHILE rs#NIL DO
[] ← sns.AddElt[SnV[ParseSteppyName[rs.first]]];
ENDLOOP;
rs ← rs};
ENames: PUBLIC PROC [d: Design, e: REF ANY] RETURNS [Set] ~ {
WITH e SELECT FROM
x: Design => RETURN [d.names];
x: CellType => RETURN d.CTNames[x];
x: Port => RETURN d.PCct[x].PNames[x];
x: Wire => RETURN d.WCct[x].WNames[x];
x: CellInstance => RETURN d.CiCct[x].INames[x];
ENDCASE => ERROR};
ACtName: PUBLIC PROC [ct: CellType] RETURNS [ROPE] ~ {
RETURN [NARROW[ct.d.ctName.Lookup[goal: AV[ct], side: left, order: Sets.alleq].MA]]};
BestPName: PUBLIC PROC [ct: CellType, p: Port] RETURNS [SteppyName] ~ {
RETURN [VSn[ct.fullName[p].Lookup[goal: AV[p], side: left].Val]]};
BestWName: PUBLIC PROC [ct: CellType, w: Wire] RETURNS [SteppyName] ~ {
RETURN [VSn[ct.fullName[w].Lookup[goal: AV[w], side: left].Val]]};
BestIName: PUBLIC PROC [ct: CellType, ci: CellInstance] RETURNS [SteppyName] ~ {
RETURN [VSn[ct.fullName[i].Lookup[goal: AV[ci], side: left].Val]]};
RelativeNames: PUBLIC PROC [ct: CellType, class: PWClass, anc, des: PW] RETURNS [names: Set--of SteppyName--] ~ {
InsertName: PROC [sn: SteppyName] RETURNS [BOOL]
~ {[] ← names.AddElt[SnV[sn]]; RETURN [FALSE]};
names ← Sets.CreateList[vals: NIL, space: steppyNameSpace, order: SetBasics.fwd];
[] ← ScanRelativeNames[ct, class, anc, des, InsertName];
RETURN};
Lookup: PUBLIC PROC [context, name, type: REF ANY] RETURNS [REF ANY] ~ {
WITH context SELECT FROM
d: Design => RETURN d.ctName.ApplyA[name, rightToLeft].MDA;
ct: CellType => {
sn: SteppyName ~ WITH name SELECT FROM
x: LORA => LSn[x],
x: ROPE => ParseSteppyName[x],
x: REF INT => OSn[x],
ENDCASE => ERROR;
SELECT type FROM
$w => RETURN SteppyLookup[ct, sn, w];
$p => RETURN SteppyLookup[ct, sn, p];
$i => RETURN SteppyLookup[ct, sn, i];
NIL => {it: REF ANY;
IF (it ← SteppyLookup[ct, sn, w])#NIL THEN RETURN [it];
IF (it ← SteppyLookup[ct, sn, i])#NIL THEN RETURN [it];
IF (it ← SteppyLookup[ct, sn, p])#NIL THEN RETURN [it];
RETURN [NIL]};
ENDCASE => ERROR};
ENDCASE => ERROR};
SteppyLookup: PUBLIC PROC [context: CellType, name: SteppyName, class: PartClass] RETURNS [Part] ~ {
RETURN context.fullName[class].Apply[SnV[name], rightToLeft].MDA};
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]};
UnparseRootedSteppyName: PUBLIC PROC [rsn: RootedSteppyName] RETURNS [u: ROPE] ~ {
u ← UnparseSteppyName[rsn.name];
IF rsn.unrel THEN u ← Rope.Concat["/", u];
RETURN};
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};
CreateVector: PUBLIC PROC [bounds: SetBasics.IntInterval ← [0, -1], val: SetBasics.Value ← SetBasics.noValue, oneToOne, dense, domainFixed: BOOLFALSE, rightSpace: Sets.Space ← SetBasics.refs] RETURNS [seq: Seq] ~ {
seq ← BiRels.CreateVector[bounds: bounds, val: val, dense: dense, domainFixed: domainFixed, rightSpace: rightSpace];
IF oneToOne THEN {
inv: Fn ~ BiRels.CreateHashTable[[rightSpace, SetBasics.ints]];
seq ← BiRels.CreateFromHalves[
spaces: [SetBasics.ints, rightSpace],
functional: ALL[TRUE],
halves: [[fn: seq], [fn: inv]]
];
};
RETURN};
Start: PROC ~ {
RETURN};
Start[];
END.