
    <<LichenNavigationImpl.mesa>>
        <<Last tweaked by Mike Spreitzer on February 2, 1988 10:32:36 am PST>>

    DIRECTORY AbSets, Asserting, BiRels, LichenDataOps, LichenDataStructure, LichenNavigation, RegularExpression, Rope, SetBasics;

    LichenNavigationImpl: CEDAR PROGRAM
        IMPORTS AbSets, Asserting, BiRels, LichenDataOps, LichenDataStructure, RegularExpression, Rope, SetBasics
        EXPORTS LichenNavigation
        =

    BEGIN OPEN LichenDataOps, LichenDataStructure, LichenNavigation, Sets:AbSets;

    CTByName: PUBLIC PROC [d: Design, name: ROPE] RETURNS [ans: CellType _ NIL] ~ {
        ans _ NARROW[CTsByName[d, name, TRUE, TRUE].TheElt.VA];
        RETURN};

    CTsByName: PUBLIC PROC [d: Design, pattern: ROPE, case: BOOL _ TRUE, literal: BOOL _ FALSE] RETURNS [Set--of CellType--] ~ {
        RETURN [d.cellTypes.Intersection[NameMatches[pattern, case, literal]]]};

    NameMatches: PROC [pattern: ROPE, case: BOOL _ TRUE, literal: BOOL _ FALSE] RETURNS [Set] ~ {
        f: RegularExpression.Finder ~ RegularExpression.CreateFromRope[
            <<addBounds: TRUE,>>
            literal: literal,
            ignoreCase: NOT case,
            pattern: pattern];
        RETURN Sets.CreateFilter[[TestName, SetBasics.refs, f]]};

    TestName: PROC [val: Sets.Value, data: REF ANY _ NIL] RETURNS [BOOL] ~ {
        f: RegularExpression.Finder ~ NARROW[data];
        WITH val.VA SELECT FROM
            ct: CellType => RETURN HasMatchingNameAssn[ct.otherPublic, f];
            v: Vertex => RETURN [HasMatchingSteppyName[v.names, f]];
            p: Port => RETURN [HasMatchingSteppyName[p.names, f]];
            ENDCASE => ERROR;
        };

    ChildByName: PUBLIC PROC [ct: CellType, name: ROPE] RETURNS [ans: Vertex _ NIL] ~ {
        ans _ NARROW[ChildrenByName[ct, name, TRUE, TRUE].TheElt.VA];
        RETURN};

    ChildrenByName: PUBLIC PROC [ct: CellType, pattern: ROPE, case: BOOL _ TRUE, literal: BOOL _ FALSE] RETURNS [Set--of CellType--] ~ {
        RETURN [Parts[ct].Intersection[NameMatches[pattern, case, literal]]]};

    Parts: PROC [ct: CellType] RETURNS [Set] ~ {
        RETURN [Sets.CreateEnumerator[[ScanParts, SetBasics.refs, ct]]]};

    ScanParts: PROC [Test: Sets.Tester, data: REF ANY _ NIL] RETURNS [Sets.MaybeValue] ~ {
        ct: CellType ~ NARROW[data];
        RETURN ct.ScanParts[Test, ALL[TRUE], FALSE]};

    ChildByType: PUBLIC PROC [parent, type: CellType] RETURNS [ans: CellInstance _ NIL] ~ {
        ans _ NARROW[ChildrenByType[parent, type].First[].MDA];
        RETURN};

    ChildrenByType: PUBLIC PROC [parent, type: CellType] RETURNS [Set--of CellInstance--] ~ {
        u: Unorganized ~ parent.asUnorganized;
        IF u=NIL THEN ERROR;
        RETURN [u.containedInstances.Intersection[instanceType.MappingA[type, rightToLeft]]]};

    PortByName: PUBLIC PROC [root: Port, name: ROPE] RETURNS [ans: Port] ~ {
        ans _ NARROW[PortsByName[root, name, TRUE, TRUE].First[].MDA];
        RETURN};

    PortsByName: PUBLIC PROC [root: Port, pattern: ROPE, case: BOOL _ TRUE, literal: BOOL _ FALSE] RETURNS [Set--of Port--] ~ {
        RETURN [Ports[root].Intersection[NameMatches[pattern, case, literal]]]};

    Ports: PROC [root: Port] RETURNS [Set--of Port--] ~ {
        RETURN [Sets.CreateEnumerator[[ScanPorts, SetBasics.refs, root]]]};

    ScanPorts: PROC [Test: Sets.Tester, data: REF ANY _ NIL] RETURNS [Sets.MaybeValue]~ {
        root: Port ~ NARROW[data];
        stack: PortList _ LIST[root];
        WHILE stack#NIL DO
            p: Port ~ stack.first;
            IF Test[AV[p]] THEN RETURN [[TRUE, AV[p] ]];
            stack _ stack.rest;
            IF p.firstChild#NIL THEN stack _ CONS[p.firstChild, stack];
            IF p.next#NIL THEN stack _ CONS[p.next, stack];
            ENDLOOP;
        RETURN [Sets.noMaybe]};

    Quit: ERROR ~ CODE;

    HasMatchingNameAssn: PROC [assns: Assertions, f: RegularExpression.Finder] RETURNS [BOOL] ~ {
        TestName: PROC [assertion: Assertion] ~ {
            thisN: ROPE ~ NARROW[Asserting.TermOf[assertion]];
            before, after: INT;
            found: BOOL;
            [found: found, before: before, after: after] _ f.SearchRope[thisN];
            IF found AND before=0 AND after=thisN.Length THEN Quit;
            };
        Asserting.EnumerateAssertionsAbout[nameReln, assns, TestName !Quit => GOTO Has];
        RETURN [FALSE];
        EXITS Has => RETURN [TRUE];
        };

    HasMatchingSteppyName: PROC [listData: ListData, f: RegularExpression.Finder] RETURNS [has: BOOL] ~ {
        names: Set ~ Setify[listData];
        TestName: PROC [val: Sets.Value] RETURNS [pass: BOOL _ FALSE] ~ {
            steppy: SteppyName ~ VSn[val];
            ropy: ROPE ~ UnparseSteppyName[steppy];
            before, after: INT;
            found: BOOL;
            [found: found, before: before, after: after] _ f.SearchRope[ropy];
            IF found AND before=0 AND after=ropy.Length THEN pass _ TRUE;
            RETURN};
        has _ names.Scan[TestName].found;
        RETURN};

    FilterSet: PUBLIC PROC [big: Set, Test: PROC [ra: REF ANY] RETURNS [passes: BOOL]] RETURNS [filtered: Set _ Sets.CreateHashSet[]] ~ 
    {
        MaybePass: PROC [ra: REF ANY] ~ {
            IF Test[ra] AND NOT filtered.AddA[ra] THEN ERROR;
            RETURN};
        big.EnumA[MaybePass];
        RETURN};

    instanceType: PUBLIC Function ~ BiRels.FnFromProc[Apply: InstanceToType, ScanInverse: ScanInstancesOfType];

    InstanceToType: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        WITH v.VA SELECT FROM
            ci: CellInstance => RETURN [[TRUE, AV[ci.type]]];
            ENDCASE => ERROR;
        };

    ScanInstancesOfType: PROC [data: REF ANY, v: Sets.Value, Test: BiRels.Tester] RETURNS [BiRels.MaybePair] ~ {
        WITH v.VA SELECT FROM
            ct: CellType => {
                FOR ci: CellInstance _ ct.firstInstance, ci.nextInstance WHILE ci # NIL DO
                    IF Test[[AV[ci], AV[ct]]] THEN RETURN [[TRUE, [AV[ci], AV[ct]]]];
                    ENDLOOP;
                };
            ENDCASE => ERROR;
        RETURN [BiRels.noMaybePair]};

    refSeqs: Sets.Space ~ BiRels.CreateBiRelSpace[[SetBasics.ints, SetBasics.refs]];

    wireToChildren: PUBLIC OneToOne ~ BiRels.FnFromProc[Apply: WireToChildren, ScanInverse: ScanParentOfChildWires, spaces: 
    [SetBasics.refs, refSeqs], oneToOne: TRUE];

    WireToChildren: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        WITH v.VA SELECT FROM
            x: Wire => RETURN [[TRUE, AV[BiRels.EnumSeqOfSet[Sets.CreateEnumerator[e: [ScanChildrenOfWire, SetBasics.refs, x]]].Refify]]];
            ENDCASE => RETURN [Sets.noMaybe];
        };

    ScanParentOfChildWires: PROC [data: REF ANY, v: Sets.Value, Test: BiRels.Tester] RETURNS [BiRels.MaybePair] ~ {
        children: Seq ~ BiRels.DeRef[v.VA];
        child: Wire ~ NARROW[children.ApplyI[0].MA];
        IF child.containingWire=NIL THEN RETURN [BiRels.noMaybePair];
        IF NOT children.Equal[BiRels.DeRef[WireToChildren[data: NIL, v: AV[child.containingWire]].MA]] THEN RETURN [BiRels.noMaybePair];
        IF Test[[AV[child.containingWire], v]] THEN RETURN [[TRUE, [AV[child.containingWire], v]]];
        RETURN [BiRels.noMaybePair]};

    ScanChildrenOfWire: PROC [Test: Sets.Tester, data: REF ANY _ NIL] RETURNS [Sets.MaybeValue] ~ {
        w: Wire ~ NARROW[data];
        FOR child: Wire _ w.FirstChildWire[], child.NextChildWire[] UNTIL child=NIL DO
            IF Test[AV[child]] THEN RETURN [[TRUE, AV[child] ]];
            ENDLOOP;
        RETURN [Sets.noMaybe]};

    portToChildren: PUBLIC OneToOne ~ BiRels.FnFromProc[Apply: PortToChildren, ScanInverse: ScanParentOfChildPorts, spaces: 
    [SetBasics.refs, refSeqs], oneToOne: TRUE];

    PortToChildren: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        WITH v.VA SELECT FROM
            x: Port => RETURN [[TRUE, AV[BiRels.EnumSeqOfSet[Sets.CreateEnumerator[e: [ScanChildrenOfPort, SetBasics.refs, x]]].Refify]]];
            ENDCASE => RETURN [Sets.noMaybe];
        };

    ScanParentOfChildPorts: PROC [data: REF ANY, v: Sets.Value, Test: BiRels.Tester] RETURNS [BiRels.MaybePair] ~ {
        children: Seq ~ BiRels.DeRef[v.VA];
        child: Port ~ NARROW[children.ApplyI[0].MA];
        parent: Port ~ WITH child.parent SELECT FROM
            x: Port => x,
            ct: CellType => NIL,
            ENDCASE => ERROR;
        IF parent=NIL THEN RETURN [BiRels.noMaybePair];
        IF NOT children.Equal[BiRels.DeRef[PortToChildren[data: NIL, v: AV[parent]].MA]] THEN RETURN [BiRels.noMaybePair];
        IF Test[[AV[parent], v]] THEN RETURN [[TRUE, [AV[parent], v]]];
        RETURN [BiRels.noMaybePair]};

    ScanChildrenOfPort: PROC [Test: Sets.Tester, data: REF ANY _ NIL] RETURNS [Sets.MaybeValue] ~ {
        w: Port ~ NARROW[data];
        FOR child: Port _ w.FirstChildPort[], child.NextChildPort[] UNTIL child=NIL DO
            IF Test[AV[child]] THEN RETURN [[TRUE, AV[child] ]];
            ENDLOOP;
        RETURN [Sets.noMaybe]};

    bestVertexShortName: PUBLIC Function ~ BiRels.FnFromProc[Apply: VertexToBestShortName, spaces: [SetBasics.refs, steppyNameSpace]];

    VertexToBestShortName: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        x: Vertex ~ NARROW[v.VA];
        RETURN x.VertexNames.First[]};

    bestPortShortName: PUBLIC Function ~ BiRels.FnFromProc[Apply: PortToBestShortName, spaces: [SetBasics.refs, steppyNameSpace]];

    PortToBestShortName: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        x: Port ~ NARROW[v.VA];
        RETURN x.PortNames.First[]};

    steppyNameSets: Sets.Space ~ Sets.CreateSetSpace[steppyNameSpace];

    vertexNames: PUBLIC Function ~ BiRels.FnFromProc[Apply: VertexToNames, spaces: [SetBasics.refs, steppyNameSets]];

    VertexToNames: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        x: Vertex ~ NARROW[v.VA];
        RETURN [[TRUE, AV[x.VertexNames.Refify]]]};

    portNames: PUBLIC Function ~ BiRels.FnFromProc[Apply: PortToNames, spaces: [SetBasics.refs, steppyNameSets]];

    PortToNames: PROC [data: REF ANY, v: Sets.Value] RETURNS [Sets.MaybeValue] ~ {
        x: Port ~ NARROW[v.VA];
        RETURN [[TRUE, AV[x.PortNames.Refify]]]};

    END.