DIRECTORY AbSets, Basics, BasicTime, BiRels, FS, IntStuff, LichenIntBasics, Rope, SetBasics;

LichenDataStructure: CEDAR DEFINITIONS
IMPORTS AbSets, BiRels, IntStuff, SetBasics
=
BEGIN
OPEN Sets:AbSets, LichenIntBasics;
nyet: ERROR --not yet implemented--;

Warning: SIGNAL [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL];

Error: ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL];
LNAT: TYPE ~ INT--[0 .. INT.LAST]--;
LORA: TYPE ~ LIST OF REF ANY;
LOLORA: TYPE ~ LIST OF LORA;
LOI: TYPE ~ LIST OF INT;
ROPE: TYPE ~ Rope.ROPE;
RopeList: TYPE ~ LIST OF ROPE;
LOR: TYPE ~ LIST OF ROPE;
LOLOR: TYPE ~ LIST OF LOR;
Time: TYPE ~ RECORD [BasicTime.GMT]; --so we can discriminate REFS to them; you can't discriminate REFS to opaque types, and BasicTime.GMT is opaque.
Dim2: TYPE ~ LichenIntBasics.Dim2;
Int2: TYPE ~ LichenIntBasics.Int2;
Range2: TYPE ~ LichenIntBasics.Range2;
Transform: TYPE ~ LichenIntBasics.Transform;

Set: TYPE ~ Sets.Set;
nilSet: Set ~ Sets.nilSet;
VarSet: TYPE ~ Sets.VarSet;
ConstSet: TYPE ~ Sets.ConstSet;
ConstFilter: TYPE ~ Sets.ConstFilter;
BiRel: TYPE ~ BiRels.BiRel;
nilBiRel: BiRel ~ BiRels.nilBiRel;
RefBiRel: TYPE ~ BiRels.RefBiRel;
VarBiRel: TYPE ~ BiRels.VarBiRel;
ConstBiRel: TYPE ~ BiRels.ConstBiRel;
Fn: TYPE ~ BiRels.Function;
VarFn: TYPE ~ BiRels.VarFunction;
UWFn: TYPE ~ BiRels.UWFunction;
ConstFn: TYPE ~ BiRels.ConstFunction;
InvFn: TYPE ~ BiRels.InvFunction;
OneToOne: TYPE ~ BiRels.OneToOne;
VarOneToOne: TYPE ~ BiRels.VarOneToOne;
ConstOneToOne: TYPE ~ BiRels.ConstOneToOne;
IntFn: TYPE ~ BiRels.IntFn;
Permutation: TYPE ~ BiRels.Permutation;

R: PROC [r: ROPE] RETURNS [ROPE] ~ INLINE {RETURN [r]};

AV: PROC [a: REF ANY] RETURNS [Sets.Value]
~ INLINE {RETURN [[ra: a]]};
IV: PROC [i: INT] RETURNS [Sets.Value]
~ INLINE {RETURN [[i: i]]};
Design: TYPE = REF DesignPrivate;
DesignPrivate: TYPE = RECORD [
eSpace, eSetSpace: Sets.Space,
names: Set--of ROPE--,
root: CellType _ NIL,
cellTypes: Set--of CellType--,
labelCellTypes: Set--of CellType--,
transistorCellTypes: Set--of CellType--,
sub: Fn--Port or Wire _ Seq (of children)--,
parent: Fn--Port or Wire _ parent--,
ancest: Fn--Port or Wire X ancestor--,
toRoot: Fn--Port or Wire _ root--,
pwUpward, pwDownward: Sets.Order,
isTop, isntTop, isAtomic, isComposite: Set--of Port or Wire--,
nontriviallyConnectedWires, wiresConnectedAtSomeInstance: Set--of Wire--,
cct: ARRAY PartClass OF Fn--Part _ containing CellType--,
partses: ARRAY PartClass OF Set--of Part--,
pws: Set--of PW--,
parts: Set--of Part--,
ciType: Fn--CellInstance _ CellType--,
ctName: BiRel--CellType X ROPE--,
arrayElt: Fn--(array) CellType _ (element) CellType--,
ciXfm: Fn--CI _ Transform--,
iwConns: BiRel--ci X Wire--,
scale: REAL _ 0.0,
inheritNames: BOOL _ FALSE,
other: Fn
];

Cell: TYPE ~ REF ANY --actually UNION [CellType, CellInstance]--;

CellType: TYPE = REF CellTypePrivate;
CellTypePrivate: TYPE = RECORD [
d: Design _ NIL,
fullName: ARRAY PartClass OF BiRel--Part X SteppyName-- _ ALL[nilBiRel],
nameOrder: ARRAY PartClass OF Sets.Order _ ALL[Sets.alleq],
isDeduced: ARRAY PWClass OF ARRAY BOOL OF Set _ ALL[ALL[nilSet]],
bbox: Range2 _ fullRange2,
asu: Unorganized _ NIL,
asArray: Array _ NIL,
asTrans: Transistor _ NIL,
color: Color _ noColor,
other: Fn _ nilBiRel];

Unorganized: TYPE ~ REF UnorganizedPrivate;
UnorganizedPrivate: TYPE ~ RECORD [
exports: Fn--Port _ Wire--,
publics, exportable, publicOrExportable, stuck: Set--of Wire-- _ nilSet
];

EClass: TYPE ~ {p, w, i, t};
PartClass: TYPE ~ EClass[p..i];
PWClass: TYPE ~ PartClass[p..w];
VertexClass: TYPE ~ PartClass[w..i];

Part: TYPE ~ REF ANY --UNION [Port, Wire, CellInstance]--;
PW: TYPE ~ REF ANY --UNION [Port, Wire]--;

Port: TYPE = REF PortPrivate;
PortPrivate: TYPE = RECORD [
color: Color _ noColor];

Wire: TYPE = REF VertexPrivate[w];
CellInstance: TYPE = REF VertexPrivate[i];
Vertex: TYPE = REF VertexPrivate;
VertexPrivate: TYPE = RECORD [
QNext: Vertex _ notInQ,
colorNext, equiv: Vertex _ NIL,
oldColor, curColor: Color _ noColor,
graph: GraphID _ Unspecified,
unique, suspect: BOOL _ FALSE,
variant: SELECT class: VertexClass FROM
i => [conns: Fn--Port _ Wire--, offset: Int2],
w => [conns: BiRel--Port X Cell--],
ENDCASE];

ClassOfPart: PROC [Part] RETURNS [PartClass];

PCct: PROC [d: Design, p: Port] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.cct[p].ApplyA[p].MA]]};
WCct: PROC [d: Design, w: Wire] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.cct[w].ApplyA[w].MA]]};
CiCct: PROC [d: Design, ci: CellInstance] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.cct[i].ApplyA[ci].MA]]};
VCct: PROC [d: Design, v: Vertex] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.cct[v.class].ApplyA[v].MA]]};
PartCct: PROC [d: Design, class: PartClass, part: Part] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.cct[class].ApplyA[part].MA]]};
CiT: PROC [d: Design, ci: CellInstance] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.ciType.ApplyA[ci].MA]]};
CtInsts: PROC [ct: CellType] RETURNS [Set]
~ INLINE {RETURN ct.d.ciType.MappingA[ct, rightToLeft]};

CiCtr: PROC [ci: CellInstance, ict: CellType] RETURNS [Int2];

Parenthood: TYPE ~ RECORD [parent: PW, index: LNAT];

PParent: PROC [d: Design, p: Port] RETURNS [Port]
~ INLINE {RETURN [NARROW[d.parent.ApplyA[p].MDA]]};
WParent: PROC [d: Design, w: Wire] RETURNS [Wire]
~ INLINE {RETURN [NARROW[d.parent.ApplyA[w].MDA]]};
PWRoot: PROC [d: Design, x: PW] RETURNS [PW];
CtArrays: PROC [ct: CellType] RETURNS [Set--of CellType--]
~ INLINE {RETURN ct.d.arrayElt.MappingA[ct, rightToLeft]};
Top: PROC [d: Design, x: PW] RETURNS [BOOL]
~ INLINE {RETURN [NOT d.parent.ApplyA[x].found]};
Atomic: PROC [d: Design, x: PW] RETURNS [BOOL]
~ INLINE {RETURN [NOT d.sub.HasMapA[x]]};
Width: PROC [d: Design, x: PW] RETURNS [NATURAL]
~ INLINE {kids: Seq ~ BiRels.DeRef[d.sub.ApplyA[x].MA]; RETURN [kids.Size.EN]};
Sub: PROC [d: Design, x: PW, i: LNAT] RETURNS [PW];
PWRank: PROC [d: Design, x: PW] RETURNS [NAT];
PIndex: PROC [d: Design, ep: Port, parent: Port _ NIL] RETURNS [LNAT];
WIndex: PROC [d: Design, ew: Wire, parent: Wire _ NIL] RETURNS [LNAT];
PParenthood: PROC [d: Design, p: Port] RETURNS [Parenthood];
WParenthood: PROC [d: Design, w: Wire] RETURNS [Parenthood];
SubSeq: PROC [d: Design, parent: PW] RETURNS [Seq--of child--]
~ INLINE {RETURN BiRels.DeRef[d.sub.ApplyA[parent].MDA]};
SubseqIndex: PROC [d: Design, kids: Seq] RETURNS [SubsIndex];
SubsIndex: TYPE ~ RECORD [parent: PW, multiparents, sub, full: BOOL, offset: INTEGER];
ExportableKids: PROC [ct: CellType, kids: Seq--of Wire--] RETURNS [BOOL];
PWIsAncestor: PROC [d: Design, ancestor, descendant: PW] RETURNS [BOOL]
~ INLINE {RETURN [d.ancest.HasAA[descendant, ancestor]]};
TopParts: PROC [ct: CellType, class: PWClass] RETURNS [Set];
EnumCTParts: PROC [ct: CellType, class: PartClass, atomic, composite: BOOL, Consume: PROC [Part]];
PWDescendants: PROC [d: Design, x: PW] RETURNS [Set]
~ INLINE {RETURN [d.ancest.MappingA[x, rightToLeft]]};
NonPublicDescendants: PROC [ct: CellType, w: Wire] RETURNS [Set];
Subcells: PROC [ct: CellType] RETURNS [Set--of CellInstance--];
CTParts: PROC [ct: CellType, class: PartClass] RETURNS [Set];
TypeSites: PROC [ct: CellType] RETURNS [Set--of Cell--];
SiteConns: PROC [site: Cell] RETURNS [conns: Fn--Port _ Wire--];

ConndWire: PROC [c: Cell, p: Port] RETURNS [Wire];
AConndPort: PROC [c: Cell, w: Wire] RETURNS [Port];

Unused: PROC [CellType] RETURNS [BOOL];
EnumerateUses: PROC [ct: CellType, Consume: PROC [CellUse]];
CellUse: TYPE ~ REF ANY --UNION [CellInstance, (array)CellType]--;

NFetchCellType: PROC [d: Design, name: ROPE] RETURNS [CellType];
FetchCellType: PROC [d: Design, name: ROPE] RETURNS [CellType]
~ INLINE {RETURN [NARROW[d.ctName.InvApplyA[name].MDA]]};
FetchPort: PROC [ct: CellType, fullName: SteppyName] RETURNS [Port]
~ INLINE {RETURN [NARROW[ct.fullName[p].InvApply[SnV[fullName]].MDA]]};
FetchWire: PROC [ct: CellType, fullName: SteppyName] RETURNS [Wire]
~ INLINE {RETURN [NARROW[ct.fullName[w].InvApply[SnV[fullName]].MDA]]};
FetchSubcell: PROC [ct: CellType, fullName: SteppyName] RETURNS [CellInstance]
~ INLINE {RETURN [NARROW[ct.fullName[i].InvApply[SnV[fullName]].MDA]]};

CTNames: PROC [d: Design, ct: CellType] RETURNS [Set]
~ INLINE {RETURN d.ctName.MappingA[ct]};
PNames: PROC [ct: CellType, p: Port] RETURNS [Set]
~ INLINE {RETURN ct.fullName[p].MappingA[p]};
WNames: PROC [ct: CellType, w: Wire] RETURNS [Set]
~ INLINE {RETURN ct.fullName[w].MappingA[w]};
INames: PROC [ct: CellType, ci: CellInstance] RETURNS [Set]
~ INLINE {RETURN ct.fullName[i].MappingA[ci]};
PartNames: PROC [ct: CellType, class: PartClass, part: Part] RETURNS [Set]
~ INLINE {RETURN ct.fullName[class].MappingA[part]};
ENames: PROC [d: Design, e: REF ANY] RETURNS [Set];

ACtName: PROC [ct: CellType] RETURNS [ROPE];
BestPName: PROC [ct: CellType, p: Port] RETURNS [SteppyName];
BestWName: PROC [ct: CellType, w: Wire] RETURNS [SteppyName];
BestIName: PROC [ct: CellType, ci: CellInstance] RETURNS [SteppyName];
BestVName: PROC [ct: CellType, v: Vertex] RETURNS [SteppyName];

PartClassName: ARRAY PartClass OF ROPE;

Array: TYPE = REF ArrayPrivate;
ArrayPrivate: TYPE = RECORD [
size2: Int2 _ ALL[1],
size: NATURAL _ 1,
basePeriod: Int2 _ ALL[1],
fXfm: Fn--phase _ Transform--,
offsets: OffsetSeq _ NIL,
connToPhys: Transform,
buildPhase: {buildingStatrep, statrepFixed} _ buildingStatrep,
dumrep: DumRep _ NIL,
statrep: StatRep _ NIL
];

OffsetSeq: TYPE ~ REF OffsetSequence;
OffsetSequence: TYPE ~ RECORD [elts: SEQUENCE length: NATURAL OF OffsetPat];
OffsetPat: TYPE ~ RECORD [o0, o1: Int2];

StatRep: TYPE ~ REF StatRepPrivate;
StatRepPrivate: TYPE ~ RECORD [
edgeSpace, paiSpace, svSpace: Sets.Space,
svNameOrder, edgeNameOrder: Sets.Order,
edges: Set--of StatEdge--,
paiToEP, paiToX, paiToY: Fn,
portEdge: ARRAY BOOL OF InvFn--elt port _ StatEdge--,
svEdge: ARRAY BOOL OF InvFn--StatVertex _ StatEdge--,
apToPAI: Fn--array port _ PortAtIndex--
];

StatEdgeSpec: TYPE ~ RECORD [
vs: ARRAY BOOL OF StatVertex,
d: Int2];
StatEdge: TYPE ~ REF StatEdgePrivate;
StatEdgePrivate: TYPE ~ RECORD [
rank: NAT,
d: Int2];

increasingSERank, decreasingSERank: READONLY Sets.Order;

StatVertex: TYPE ~ RECORD [port: Port, phase: Int2];
PortAtIndex: TYPE ~ RECORD [port: Port, ai: Int2];
PortCai: TYPE ~ RECORD [port: Port, cai: CompositeArrayIndex];

DumRep: TYPE ~ REF DumRepPrivate;
DumRepPrivate: TYPE ~ RECORD [
dwSpace: Sets.Space,
wires: Set--of DumbWire--,
epw: BiRel--elt port X DumbWire--,
dwSub: Fn--parent DumbWire _ Seq of children--,
dwParent: Fn--child DumbWire _ parent--,
epToWire: Fn--elt port _ Fn(composite array index _ DumbWire)--,
apToWire: Fn--array port _ DumbWire--
];

DumbWire: TYPE ~ REF DumbWirePrivate;
DumbWirePrivate: TYPE ~ RECORD [
eps: BiRel--elt port X composite array index--,
children: Seq--of DumbWire-- _ nilBiRel,
parent: DumbWire _ NIL, index: LNAT _ LNAT.LAST];

TopDumbWire: TYPE ~ DumbWire --with parent=NIL--;
ChildDumbWire: TYPE ~ DumbWire --with parent#NIL--;

CompositeArrayIndex: TYPE ~ NATURAL;

ComposeAI: PROC [a: Array, ai: Int2] RETURNS [CompositeArrayIndex]
~ INLINE {RETURN [a.size2[Y]*ai[X]+ai[Y]]};

DecomposeAI: PROC [a: Array, cai: CompositeArrayIndex] RETURNS [ai: Int2]
~ INLINE {ai[X] _ cai/a.size2[Y]; ai[Y] _ cai - ai[X]*a.size2[Y]};

ComposePhase: PROC [a: Array, f: Int2] RETURNS [CompositeArrayIndex]
~ INLINE {RETURN [a.basePeriod[Y]*f[X]+f[Y]]};

DecomposePhase: PROC [a: Array, cf: CompositeArrayIndex] RETURNS [f: Int2]
~ INLINE {f[X] _ cf/a.basePeriod[Y]; f[Y] _ cf - f[X]*a.basePeriod[Y]};

EltType: PROC [act: CellType] RETURNS [CellType]
~ INLINE {RETURN [NARROW[act.d.arrayElt.ApplyA[act].MA]]};

EltCtr: PROC [a: Array, ect: CellType, ai: Int2] RETURNS [Int2];

ArrayEltPortsConnected: PROC [act: CellType, ai1, ai2: Int2, ep1, ep2: Port] RETURNS [BOOL];

SomePAI: PROC [act: CellType, dw: DumbWire] RETURNS [PortAtIndex];

SeP: PROC [se: StatEdge, a: Array, b: BOOL] RETURNS [Port];

SeRP: PROC [se: StatEdge, sr: StatRep, b: BOOL] RETURNS [Port];

SeSv: PROC [se: StatEdge, a: Array, b: BOOL] RETURNS [StatVertex]
~ INLINE {RETURN VSv[a.statrep.svEdge[b].InvApplyA[se].Val]};

SeRSv: PROC [se: StatEdge, sr: StatRep, b: BOOL] RETURNS [StatVertex]
~ INLINE {RETURN VSv[sr.svEdge[b].InvApplyA[se].Val]};

SeRSvV: PROC [se: StatEdge, sr: StatRep, b: BOOL] RETURNS [Sets.Value]
~ INLINE {RETURN sr.svEdge[b].InvApplyA[se].Val[]};

SeSp: PROC [se: StatEdge, sr: StatRep] RETURNS [StatEdgeSpec];

SvV: PROC [sv: StatVertex] RETURNS [Sets.Value]
~ INLINE {RETURN [[ra: sv.port, i: LOOPHOLE[sv.phase]]]};

VSv: PROC [v: Sets.Value] RETURNS [StatVertex]
~ INLINE {RETURN [[port: NARROW[v.ra], phase: LOOPHOLE[v.i]]]};

PaiV: PROC [pai: PortAtIndex] RETURNS [Sets.Value]
~ INLINE {RETURN [[ra: pai.port, i: LOOPHOLE[pai.ai]]]};

VPai: PROC [v: Sets.Value] RETURNS [PortAtIndex]
~ INLINE {RETURN [[port: NARROW[v.ra], ai: LOOPHOLE[v.i]]]};

PcV: PROC [pc: PortCai] RETURNS [Sets.Value]
~ INLINE {RETURN [[ra: pc.port, i: pc.cai]]};

VPc: PROC [v: Sets.Value] RETURNS [PortCai]
~ INLINE {RETURN [[port: NARROW[v.ra], cai: v.i]]};

I2V: PROC [x: Int2] RETURNS [Sets.Value]
~ INLINE {RETURN [[ra: NIL, i: LOOPHOLE[x]]]};

VI2: PROC [v: Sets.Value] RETURNS [Int2]
~ INLINE {RETURN LOOPHOLE[v.i]};

Transistor: TYPE = REF TransistorPrivate;
TransistorPrivate: TYPE = RECORD [
type: ROPE,
length, width, area, perimeter: LNAT _ 0
];
StructurallyEquivalent: PROC [cta, ctb: CellType] RETURNS [equiv: BOOL, assoc: OneToOne];
Describe: PROC [d: Design, subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [ROPE];

SteppyDescribe: PROC [d: Design, subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [RootedSteppyName];

NameGenerator: TYPE = REF NameGeneratorPrivate;
NameGeneratorPrivate: TYPE = RECORD [
GenerateName: PROC [data, subject: REF ANY] RETURNS [ROPE],
data: REF ANY _ NIL
];

RelativeNames: PROC [ct: CellType, class: PWClass, anc, des: PW] RETURNS [Set--of SteppyName--];
ScanRelativeNames: PROC [ct: CellType, class: PWClass, anc, des: PW, Test: PROC [SteppyName] RETURNS [BOOL]] RETURNS [MaybeSteppyName];
AcceptAnySteppyName: PROC [SteppyName] RETURNS [BOOL];

Lookup: PROC [context, name, type: REF ANY] RETURNS [REF ANY];

SteppyLookup: PROC [context: CellType, name: SteppyName, class: PartClass] RETURNS [Part];
SteppyNameList: TYPE ~ LIST OF SteppyName;
MaybeSteppyName: TYPE ~ RECORD [found: BOOL, it: SteppyName];
RootedSteppyName: TYPE ~ RECORD [name: SteppyName, unrel: BOOL];

SteppyName: TYPE ~ RECORD [
steps: NameStepList <<ignore: --ASO: with every REF INT after all ROPEs-->>,
grade: SteppyNameGrade];

NameStepList: TYPE ~ LIST OF NameStep --most significant first--;
NameStep: TYPE ~ REF ANY --actually UNION [ROPE, REF INT]--;

SteppyNameGrade: TYPE ~ RECORD [
global, power: BOOL,
nonsubs: [0 .. NATURAL.LAST/2],
gend: BOOL,
subs: NATURAL];

noGrade: SteppyNameGrade ~ [FALSE, FALSE, 0, FALSE, 0];
noName: SteppyName ~ [NIL, noGrade];
noNameVal: Sets.Value ~ [NIL, LOOPHOLE[noGrade]];

SteppyNamePattern: TYPE ~ SteppyName;
anyROPE: READONLY ROPE;
anyInt: READONLY REF INT;

SNMatch: PROC [pat: SteppyNamePattern, subj: SteppyName] RETURNS [MaybeSteppyName];

SnV: PROC [sn: SteppyName] RETURNS [Sets.Value]
~ INLINE {RETURN [[ra: sn.steps, i: LOOPHOLE[sn.grade]]]};

VSn: PROC [v: Sets.Value] RETURNS [SteppyName]
~ INLINE {RETURN [[steps: NARROW[v.ra], grade: LOOPHOLE[v.i]]]};

LSn: PROC [NameStepList] RETURNS [SteppyName];

OSn: PROC [NameStep] RETURNS [SteppyName];

ListRopes: PROC [LOR] RETURNS [Set--of ROPE--];

OneRope: PROC [ROPE] RETURNS [Set--of ROPE--];

ListSteppys: PROC [SteppyNameList] RETURNS [Set--of SteppyName--];

OneSteppy: PROC [SteppyName] RETURNS [Set--of SteppyName--];

OneLSn: PROC [NameStepList] RETURNS [Set--of SteppyName--];

OneOSn: PROC [NameStep] RETURNS [Set--of SteppyName--];

ParseSteppyName: PROC [raw: ROPE] RETURNS [SteppyName];
UnparseSteppyName: PROC [s: SteppyName] RETURNS [ROPE];
UnparseRootedSteppyName: PROC [RootedSteppyName] RETURNS [ROPE];

ActualName: PROC [lab: BOOL, cin, pn: SteppyName] RETURNS [SteppyName];
ActualNames: PROC [lab: BOOL, cins, pns: Set--of SteppyName--] RETURNS [Set];
SNsCat: PROC [as, bs: Set--of SteppyName--] RETURNS [Set--of SteppyName--];
SNCat: PROC [a, b: SteppyName] RETURNS [SteppyName];
RSNCat: PROC [RootedSteppyName, SteppyName] RETURNS [RootedSteppyName];
SNPrepend: PROC [NameStep, SteppyName] RETURNS [SteppyName];
SNAppend: PROC [SteppyName, NameStep] RETURNS [SteppyName];
SteppyIsPrefix: PROC [prefix, full: SteppyName] RETURNS [MaybeSteppyName];
SteppyIsSuffix: PROC [suffix, full: SteppyName] RETURNS [MaybeSteppyName];
SNTail: PROC [SteppyName] RETURNS [SteppyName];
SNthTail: PROC [SteppyName, NATURAL] RETURNS [SteppyName];
PreTails: PROC [SteppyName] RETURNS [Set--of SteppyName--];
LastRope: PROC [SteppyName] RETURNS [ROPE];

AIName: PROC [a: Array, ai: Int2] RETURNS [SteppyName];

SteppyNameGradeCompare: PROC [g1, g2: SteppyNameGrade] RETURNS [SetBasics.TotalComparison];
GrossSteppyNameGradeCompare: PROC [g1, g2: SteppyNameGrade] RETURNS [SetBasics.TotalComparison];
NameStepListCompare: PROC [l1, l2: NameStepList] RETURNS [SetBasics.TotalComparison];
NameStepListEqual: PROC [l1, l2: NameStepList, clip1, clip2: NameStepList _ NIL] RETURNS [BOOL];

nameStepSpace, steplistSpace, steppyNameSpace: READONLY Sets.Space;
emptyRopeSet, emptySteppySet: READONLY Set;
fullNameHints: READONLY BiRels.HintPair;
intVsNs: READONLY OneToOne;
grossSteppyOrder: READONLY Sets.Order;
nonGlobals, gends, powerNames: READONLY Set--of SteppyName--;
vddNames, gndNames: READONLY Set--of SteppyName--;
vddRopes, gndRopes: READONLY Set--of ROPE--;
lastRope: READONLY Fn--steppyName _ ROPE--;
matching: READONLY BiRel--pattern X SteppyName--;
difoverlap: READONLY BiRel--pattern X pattern--;
GraphID: TYPE = {A, B, Unspecified};
RealGraphID: TYPE = GraphID[A .. B];
OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A];
graphIDToRope: GraphDescriptions;
GraphDescriptions: TYPE ~ ARRAY GraphID OF ROPE;
RealGraphDescriptions: TYPE ~ ARRAY RealGraphID OF ROPE;
Color: TYPE = INT;
noColor: Color = LAST[Color];
someColor: Color = 87654321H;

FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE {
filtered _ IF color # noColor THEN color ELSE someColor};

notInQ: Vertex --don't look:-- = NIL --you looked!--;
endOfQ: READONLY Vertex;
TList: TYPE ~ RECORD [head, tail: LORA _ NIL]; --first and last, not after last

Cat: PROC [a, b: TList] RETURNS [TList]
~ INLINE {IF a.head=NIL THEN RETURN [b] ELSE IF b.head=NIL THEN RETURN [a] ELSE {a.tail.rest _ b.head; RETURN [[a.head, b.tail]]}};
Prepend: PROC [l: TList, ra: REF ANY] RETURNS [l2: TList]
~ INLINE {l2.head _ CONS[ra, l.head]; l2.tail _ IF l.tail#NIL THEN l.tail ELSE l2.head};
Append: PROC [l: TList, ra: REF ANY] RETURNS [l2: TList]
~ INLINE {l2.tail _ LIST[ra]; IF l.head=NIL THEN l2.head _ l2.tail ELSE {l2.head _ l.head; l.tail.rest _ l2.tail}};
CopyTill: PROC [first, afterlast: LORA] RETURNS [TList];
LTl: PROC [LORA] RETURNS [TList];
Seq: TYPE ~ BiRels.Sequence;

CreateVector: PROC [bounds: SetBasics.IntInterval _ [0, -1], val: SetBasics.Value _ SetBasics.noValue, oneToOne, dense, domainFixed: BOOL _ FALSE, rightSpace: SetBasics.Space _ SetBasics.reps] RETURNS [Seq];

CreateSeq: PROC [len: NATURAL _ 0, oneToOne, dense, domainFixed: BOOL _ FALSE, rightSpace: Sets.Space _ SetBasics.reps] RETURNS [Seq]
~ INLINE {RETURN CreateVector[[0, len-1], SetBasics.noValue, oneToOne, dense, domainFixed, rightSpace]};

NewInt: PROC [i: INT] RETURNS [REF INT];

ExtendName: PROC [fileName, defaultExtension: ROPE] RETURNS [fullFName: ROPE, cp: FS.ComponentPositions];
END.
LichenDataStructure.Mesa
Last tweaked by Mike Spreitzer on August 26, 1988 3:06:18 pm PDT
SIGNALs and ERRORs
Familiar Stuff
The Main Point
When scale#0, it gives the number of meters per unit of linear dimension
Arrays
We make a simplifying assumption (AASEU: (Assertion about Arrays - Static Edges Uniform)): in any given wire tree in an array, all wires have the same number of connections.  In other words, the connectivity of the root tells the whole story.  Because of this, we can say some static edges are top, and the others are wholly owned subsidiaries.
We also maintain AAMW: (Maximal Wires) we keep static edges and dumb wires as "high" as meaningful and possible.
offset for index*basePeriod+phase is offsets[phase].o0 + offsets[phase].o1*index
transforms X,Y indices to X,Y coordinates, modulo magnitude and offset
true: AAASEP: all StatEdges explicitly present.
false: AAOTSE: only top stat edges are explicitly present.
d[X] > 0, or d[X]=0 and d[Y] >= 0.
Transistors
Uh, yuk (we shouldn't have to know about these).
Structural Comparison
General Naming
name may be a LORA or a ROPE or a REF ANY.
context: Design => result: CellType.
context: CellType, type: {$w, $p, $i} => result of that class.
context: CellType, type: NIL => classes tried in some order.
Steppy (Structured) Names
The argument is a Tail^n of each result.
has <a, b> iff a#b and there are some names they both match.
Circuit Graph Stuff
Head&Tail Lists
Randumb conveniences
If oneToOne, inverse kept in a HashTable.
Treat the result as a REF READONLY INT, or you'll be sorry!
Κ€–

"cedar" style˜
code™K™@—K˜KšΟk	œ$œ-˜\K˜šΠbxœœ
˜&Kšœ$˜+Kš
œ
˜
—
headš
˜Kšœ
Οnœ˜"—™KšΠblœœ
Οcœ
˜$K˜Kš œœœœ
œœ˜?K˜Kš œœœœ
œœ˜<—™Kšœœ‘œ
˜$Kšœœœ
œ
œ
œ
˜Kš
œœœ
œ
œ
˜Kš
œœœ
œ
œ
˜Kšœœœ
˜Kš	œ
œœ
œ
œ
˜Kš
œœœ
œ
œ
˜Kš
œœœ
œ
œ
˜Kšœœœœ‘p˜•
Kšœœ˜"Kšœœ˜"Kšœœ˜&Kšœœ˜,K˜Kšœœ˜K˜Kšœœ˜Kšœ
œ˜Kšœ
œ˜%Kšœœ˜K˜"Kšœ
œ˜!Kšœ
œ˜!Kšœœ˜%Kšœœ˜Kšœœ˜!Kšœœ˜Kšœ	œ˜%Kšœœ˜!Kšœ
œ˜!Kšœ
œ˜'Kšœœ˜+Kšœœ˜Kšœ
œ˜'K˜KšŸ
œœœœœœœ˜7K˜š
œœœ
œœ
˜*Kšœœœ˜—šœœœœ
˜&Kšœœœ˜——™Kšœœœ˜!šœœœ˜Kš
œ˜Kšœ
‘œ
˜Kšœœ
˜Kšœ‘œ
˜Kšœ‘œ
˜#Kšœ‘œ
˜(Kšœ‘Πcm
‘œ
˜,Kšœ
‘’
‘	œ
˜$Kšœ
‘’
‘œ
˜&Kšœ
‘’
‘œ
˜"K˜!Kšœ*‘œ
˜>Kšœ=‘œ
˜IKš	œœœ‘’
‘œ
˜9Kšœ	œœ‘œ
˜+Kšœ‘	œ
˜Kšœ
‘œ
˜Kšœ
‘’
‘œ
˜&Kšœ
‘’
‘œ
˜!Kšœ‘’
‘œ
˜6Kšœ	‘’
‘œ
˜Kšœ‘’
‘œ
˜šœœ˜K™H—Kšœœœ
˜K˜	Kš
œ˜—K˜Kš	œœœ
œ
‘+œ
˜AK˜Kšœ
œœ˜%šœœœ˜ Kšœœ
˜Kšœ
œœ‘’
‘
œœ˜HKšœœœœ
˜;Kšœœ	œ
œ
œ
œœ
œ
˜AKš
œ˜Kšœœ
˜Kšœœ
˜Kšœœ
˜Kš
œ˜Kš
œ˜—K˜Kšœ
œœ˜+šœœœ˜#Kšœ‘’
‘œ
˜Kšœ3‘œ	˜GK˜—K˜Kšœœ˜Kšœœ˜Kšœ	œ˜ Kšœ
œ˜$K˜Kš	œœœ
œ
‘$œ
˜:Kš
œœœ
œ
‘œ
˜*K˜Kšœœœ
˜šœ
œœ˜Kš
œ˜—K˜Kšœœœ˜"Kšœœœ˜*Kšœœœ˜!šœœœ˜K˜Kšœœ
˜K˜$Kš
œ˜Kšœœœ
˜šœ	œ˜'Kšœ‘’
‘œ˜.Kšœ‘’
‘œ˜#Kšœ˜	——K˜KšŸœœœ
˜-K˜šŸœœœ˜2Kš	œœœœœ˜2—šŸœœœ˜2Kš	œœœœœ˜2—šŸœœœ˜<Kš	œœœœœ˜3—šŸœœœ˜4Kš	œœœœœ˜8—šŸœœ+œ˜JKš	œœœœœ˜9—šŸœœœ˜:Kš	œœœœœ˜3—šŸœœœ˜*Kšœœœ(˜8—K˜KšŸœœ#œ˜=K˜Kš	œœœ
œ	œ˜4K˜šŸœœœ˜1Kš	œœœœœ˜3—šŸœœœ˜1Kš	œœœœœ˜3—KšŸœœœ˜-šŸœœœ‘œ
˜:Kšœœœ*˜:—š
Ÿœœœœœ
˜+Kšœœœœ˜1—š
Ÿœœœœœ
˜.Kšœœœœ˜)—š
Ÿœœœœœ
˜0Kš	œœ+œœœ˜O—KšŸœœœœœœ˜3Kš
Ÿœœœœœ˜.Kš
Ÿœœ&œœœ˜FKš
Ÿœœ&œœœ˜FKšŸœœœ˜<KšŸœœœ˜<š
Ÿœœœœ‘œ
˜>Kšœœœ#œ˜9—šŸœœœ
˜=Kšœœœ
œœ
œ˜V—Kš
Ÿœœ‘œœœ˜Iš
Ÿœœ#œœœ
˜GKšœœœ)˜9—KšŸœœ œ˜<Kš
Ÿœœ5œŸœœ	˜bšŸ
œœœœ˜4Kšœœœ&˜6—KšŸœœœ˜AKšŸœœœ‘œ˜?KšŸœœ"œ˜=KšŸ	œœœ‘œ˜8Kš
Ÿ	œœœ‘’
‘œ˜@K˜KšŸ	œœœ˜2KšŸ
œœœ˜3K˜KšŸœœœœ˜'šŸ
œœŸœœ˜<Kš	œ	œœ
œ
‘)œ
˜B—K˜KšŸœœœœ˜@šŸ
œœœœ˜>Kš	œœœœœ˜9—šŸ	œœ&œ˜CKš	œœœœ(œ˜G—šŸ	œœ&œ˜CKš	œœœœ(œ˜G—šŸœœ&œ˜NKš	œœœœ(œ˜G—K˜šŸœœœ˜5Kšœœœ˜(—šŸœœœ˜2Kšœœœ˜-—šŸœœœ˜2Kšœœœ˜-—šŸœœ"œ˜;Kšœœœ˜.—šŸ	œœ.œ˜JKšœœœ$˜4—Kš
Ÿœœœ
œœ˜3K˜KšŸœœœœ˜,KšŸ	œœœ˜=KšŸ	œœœ˜=KšŸ	œœ"œ˜FKšŸ	œœœ˜?K˜KšŸ
œœœ
œ
˜'—™Kš
œ*Οe
ϣ
ϣ
ϣ
ϣ
œΥ
£œ/™ΨK™pK˜Kšœœœ˜šœœœ˜Kšœœ˜Kšœœ˜Kšœœ˜KšΟg
œ‘’
‘œ
˜šœœ
˜Kš
œP™P—˜K™F—K˜>Kšœœ
˜Kšœ˜K˜—K˜Kšœœœ˜%Kšœœœœ	œ
œ˜LKšœœœ˜(K˜Kšœ	œœ˜#šœœœ˜K˜)K˜'šœ
‘œ
˜K™/K™:—K˜Kš	œ
œ
œ
œ‘œ
˜5Kš	œœ
œ
œ‘œ
˜5Kšœ‘
’
‘˜'K˜—K˜šœœœ˜Kšœœ
œ
œ˜Kš€
œ˜	—Kšœ
œœ˜%šœœœ˜ Kšœœ
˜
Kš€
œ˜	Kš€
œ€
œ
€
œ	™"—K˜Kšœ$œ˜8K˜Kšœœœ˜4Kšœ
œœ˜2Kšœ	œœ(˜>K˜Kšœœœ˜!šœœœ˜K˜Kšœ
‘œ
˜Kšœ
‘’
‘œ
˜"Kšœ	‘’
‘œ
˜/Kšœ‘’
‘	œ
˜(Kšœ‘’
‘’
‘œ
˜@Kšœ‘
’
‘˜%K˜—K˜Kšœ
œœ˜%šœœœ˜ Kšœ
‘’
‘œ
˜/Kšœ
‘œ˜(Kš	œœ	œœ
œ˜1—K˜Kšœ
œ‘œ
˜1Kšœœ‘œ
˜3K˜Kšœœœ
˜$K˜šŸ	œœœ˜BKšœœœ˜+—K˜šŸœœ&œ˜IKšœœ:˜B—K˜šŸœœ€
œœ˜DKš	œœœ€
œ€
œ˜.—K˜š
Ÿœœ
€
œœ€
œ˜JKš
œœ€
œ€
œ€
œ€
œ€
œ˜G—K˜šŸœœœ˜0Kš	œœœœœ˜:—K˜KšŸœœ%œ˜@K˜KšŸœœ1œœ˜\K˜KšŸœœœ˜BK˜KšŸœœœœ˜;K˜KšŸœœ œœ˜?K˜šŸœœœœ
˜AKšœœœ-˜=—K˜šŸœœ œœ
˜EKšœœœ&˜6—K˜šŸœœ œœ
˜FKšœœœ#˜3—K˜KšŸœœœ˜>K˜šŸœœœ
˜/Kšœœœœ˜9—K˜šŸœœœ
˜.Kš	œœœ	œœ	˜?—K˜šŸœœœ
˜2Kšœœœœ˜8—K˜šŸœœœ˜0Kš	œœœ	œœ	˜<—K˜šŸœœœ
˜,Kšœœœ˜-—K˜šŸœœœ
˜+Kšœœœ	œ˜3—K˜šœœœ
˜(Kš	œœœœœ˜.—K˜šœœœ˜(Kšœœœ
œ˜ ——™K™0K˜Kšœœœ˜)šœœœ˜"Kšœœ
˜Kšœ œ˜(K˜——™KšŸœœœ	œ˜Y—™KšŸœœœ
œœ
œœœœœ˜uK˜KšŸœœœ
œœ
œœœœ˜‡
K˜Kšœœœ˜/šœœœ˜%KšŸœœœ
œœœ˜;Kšœœ
œ˜K˜—K˜Kš
Ÿ
œœ*œœ‘œ˜`KšŸœœ*œŸœœœœœ˜‡
KšŸœœœœ˜6K˜šŸœœœ
œœœ
œ˜>K™*K™$K™>K™<—K˜KšŸœœ9œ˜Z—™Kšœœœ
œ˜*Kšœœœ	œ˜=Kšœœœœ˜@K˜šœœœ˜Kš
œL˜LKš
œ˜—K˜Kš	œœœ
œ
‘œ
˜AKš	œ
œœ
œ
‘"œ
˜<K˜šœœœ˜ Kšœœ
˜Kšœœ
œ˜Kšœœ
˜Kšœœ˜—K˜Kšœœœœ˜7Kšœœ˜$Kšœœœ˜1K˜Kšœœ˜%Kšœ	œ
œ
˜Kšœœ
œ
œ
˜K˜KšŸœœ,œ˜SK˜šŸœœœ
˜/Kšœœœœ˜:—K˜šŸœœœ
˜.Kš	œœœ
œœ	˜@—K˜KšŸœœœ˜.K˜KšŸœœœ˜*K˜Kš
Ÿ	œœœœ‘œ˜/K˜Kš
Ÿœœœœ‘œ˜.K˜KšŸœœœ‘œ˜BK˜KšŸ	œœœ‘œ˜<K˜KšŸœœœ‘œ˜;K˜KšŸœœœ‘œ˜7K˜KšŸœœœœ˜7KšŸœœœœ˜7KšŸœœœœ˜@K˜KšŸ
œœœœ˜GKš
Ÿœœœ‘œœ˜MKš
Ÿœœ
‘œœ‘œ˜KKšŸœœœ˜4KšŸœœ œ˜GKšŸ	œœœ˜<KšŸœœœ˜;KšŸœœœ˜JKšŸœœœ˜JKšŸœœœ˜/KšŸœœœœ˜:šŸœœœ‘œ˜;K™(—KšŸœœœœ˜+K˜KšŸœœœ˜7K˜KšŸœœœ˜[KšŸœœœ˜`KšŸœœœ˜UKš
Ÿœœ5œœœ˜`K˜Kšœ/œ˜CKšœœ˜+Kšœœ˜(Kšœ	œ
˜Kšœœ˜&Kšœœ‘œ
˜=Kšœœ‘œ
˜2Kšœœ‘œ
˜,Kšœ
œ‘
’
‘œ
˜+Kšœ
œ‘
’
‘
œ
˜1šœœ‘
’
‘
œ
˜0K™<——™Kšœ	œ˜$Kšœ
œ˜$Kšœœ
œ˜<Kš
œ!˜!Kš	œœœ	œ
œ
˜0Kš	œœœ
œ
œ
˜8Kšœœœ
˜Kšœœ˜K˜K˜šŸœœœœ˜EKšœœœœ˜9—K˜Kšœ‘œœ
‘œ
˜5Kšœœ˜—™Kš
œœœœœ‘ ˜OK˜šŸœœœ˜'Kšœœœœ
œ
œœ
œœ
œ
œœœ˜ƒ
—š
Ÿœœœ
œœ˜9Kš
œœœœœ
œœ
˜X—š
Ÿœœœ
œœ˜8Kš
œœœœœ
œœ,˜s—KšŸœœœœ	˜8KšŸœœœœ	˜!—™Kšœœ˜K˜š
Ÿœœsœœ0œ˜Ο
K™)—K˜šŸ	œœœ$œœ+œ˜…
KšœœœX˜h—K˜šŸœœœœœ
œ˜(Kšœ+Οb™;—K˜KšŸ
œœœœ
œœ˜i—Lšœ
˜—…—Lžo<