[_CD4_]<datools7.0>Lichen2>LichenDataImpl1A.Mesa!22

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: 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.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: 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]]};

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};

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;

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: PROC ~ {

RETURN};

Start[];

END.