LichenDataImpl1A.Mesa
Last tweaked by Mike Spreitzer on August 18, 1988 12:04:05 pm 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: BOOL ← TRUE;
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.stuck].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] ~ {
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: ROPE ← NIL;
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:
BOOL ←
FALSE] ~ {
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]]};
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:
BOOL ←
FALSE, 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[];
END.