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

    Start[];

    END.