
<<LichenData3Impl.Mesa>>
    <<Last tweaked by Mike Spreitzer on February 2, 1988 12:48:23 pm PST>>

    DIRECTORY AbSets, BiRels, Convert, FS, IntStuff, LichenDataOps, LichenDataStructure, LichenNavigation, Rope, SetBasics, 
    StructuredStreams, SymTab, TiogaAccess, UnparserBuffer, ViewerIO;

    LichenData3Impl: CEDAR PROGRAM
        IMPORTS AbSets, BiRels, Convert, FS, IntStuff, LichenDataOps, LichenDataStructure, Rope, SetBasics
        EXPORTS LichenDataOps, LichenDataStructure
        =

    BEGIN OPEN LichenDataOps, LichenDataStructure, Sets:AbSets, SS:StructuredStreams, UB:UnparserBuffer;

    Escape: ERROR = CODE;

    EnumeratePortsForWire: PUBLIC PROC [w: Wire, Consume: PROC [Port]]= {
        See: PROC [p: Port, v: Vertex] = {
            IF IsMirror[NARROW[v]] THEN Consume[p];
            RETURN};
        w.EnumerateTransitiveConnections[See];
        w _ w;
        RETURN};

    EnumerateParts: PUBLIC PROC [ct: CellType, Consume: PROC [Vertex], mirrorToo: BOOL] ~ {
        Test: PROC [val: Sets.Value] RETURNS [BOOL]
            ~ {Consume[NARROW[val.VA]]; RETURN [FALSE]};
        IF ScanParts[ct, Test, ALL[TRUE], mirrorToo].found THEN ERROR;
        RETURN};

    ScanParts: PUBLIC PROC [ct: CellType, Test: Sets.Tester, filter: PartFilter, mirrorToo: BOOL] RETURNS [mv: Sets.MaybeValue _ 
    Sets.noMaybe] ~ {
        u: Unorganized ~ ct.asUnorganized;
        PerCell: PROC [ra: Sets.Value] RETURNS [BOOL] ~ {
            ci: CellInstance ~ NARROW[ra.VA];
            PassIMs: PROC [p: Port, v: Vertex, e: Edge] RETURNS [BOOL] ~ {
                WITH v SELECT FROM
                    ci: CellInstance => ERROR;
                    w: Wire => NULL;
                    im: Intermediary => {
                        IF Test[AV[im]] THEN RETURN [(mv _ [TRUE, AV[im]]).found];
                        RETURN ScanImmediateEdges[im, PassIMs, [cellward: FALSE, wireward: TRUE]];
                        };
                    ENDCASE => ERROR;
                RETURN [FALSE]};
            IF filter[cell] AND Test[AV[ci]] THEN RETURN [(mv _ [TRUE, AV[ci]]).found];
            IF filter[intermediate] THEN RETURN ScanImmediateEdges[ci, PassIMs];
            RETURN [FALSE]};
        PassChildren: PROC [w: Wire] RETURNS [Sets.MaybeValue] ~ {
            FOR w _ FirstChildWire[w], NextChildWire[w] WHILE w # NIL DO
                IF Test[AV[w]] THEN RETURN [[TRUE, AV[w] ]];
                {sub: Sets.MaybeValue ~ PassChildren[w];
                IF sub.found THEN RETURN [sub];
                }ENDLOOP;
            RETURN [Sets.noMaybe]};
        IF u=NIL THEN ERROR;
        IF filter[wire] AND (mv _ PassChildren[u.internalWire]).found THEN RETURN;
        IF filter[intermediate] THEN {IF (mv _ u.containedInstances.Scan[PerCell]).found THEN RETURN}
        ELSE IF filter[cell] AND (mv _ u.containedInstances.Scan[Test]).found THEN RETURN;
        IF mirrorToo AND PerCell[AV[u.mirror]] THEN mv _ [TRUE, AV[u.mirror]];
        RETURN};

    EnumerateCellTypes: PUBLIC PROC [design: Design, Consume: PROC [CellType]] = {
        PerCellType: PROC [elt: REF ANY] = {Consume[NARROW[elt]]};
        design.cellTypes.EnumA[PerCellType]};

    ScanImmediateEdges: PUBLIC PROC [v: Vertex, Test: PROC [Port, Vertex, Edge] RETURNS [BOOL], filter: ARRAY GraphDirection OF BOOL _ 
    ALL[TRUE], order: Order _ any] RETURNS [BOOL] = {
        nextEdge: Edge _ SELECT order FROM    --these depend on AI1
            forward, any => v.firstEdge,
            backward => v.lastEdge,
            ENDCASE => ERROR;
        lastEdge, lastConsumed: Edge _ NIL;
        FOR e: Edge _ nextEdge, nextEdge WHILE e # NIL DO
            selfward: GraphDirection = SELECT v.class FROM
                cell => cellward,
                wire => wireward,
                intermediate => e.SideFor[v],
                ENDCASE => ERROR;
            away: GraphDirection = OppositeDirection[selfward];
            w: Vertex = e.sides[away].v;
            IF v # e.sides[selfward].v THEN ERROR;
            IF v.class # intermediate AND v.class = w.class THEN ERROR Error["Broken"];
            nextEdge _ SELECT order FROM    --these depend on AI1
                forward, any => e.sides[selfward].next,
                backward => e.sides[selfward].prev,
                ENDCASE => ERROR;
            IF filter[away] THEN {
                IF Test[e.port, w, e] THEN RETURN [TRUE];
                lastConsumed _ e};
            lastEdge _ e;
            ENDLOOP;
        RETURN [FALSE]};

    EnumerateImmediateEdges: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ 
    ALL[TRUE], order: Order _ any] = {
        Test: PROC [p: Port, v: Vertex, e: Edge] RETURNS [BOOL] ~ {Consume[p, v, e]; RETURN [FALSE]};
        IF ScanImmediateEdges[v, Test, filter, order] THEN ERROR;
        RETURN};

    EnumerateImmediateConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ 
    ALL[TRUE], order: Order _ any] = {
        Test: PROC [p: Port, v: Vertex, e: Edge] RETURNS [BOOL] ~ {Consume[p, v]; RETURN [FALSE]};
        IF ScanImmediateEdges[v, Test, filter, order] THEN ERROR;
        RETURN};

    EnumerateNeighboringVertices: PUBLIC PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]] = {
        Test: PROC [port: Port, w: Vertex, e: Edge] RETURNS [BOOL]
            = {Consume[w]; RETURN [FALSE]};
        IF ScanImmediateEdges[v, Test, filter] THEN ERROR;
        RETURN};

    EnumerateTransitiveConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex]] = {
        WITH v SELECT FROM
            wire: Wire => {
                WireWork: PROC [wire: Wire, Consume: PROC [Port, Vertex]] = {
                    CellStart: PROC [port: Port, w: Vertex] = {
                        WITH w SELECT FROM
                            ci: CellInstance => Consume[port, ci];
                            im: Intermediary => {
                                CellFinish: PROC [parent: Port, u: Vertex] = {
                                    WITH u SELECT FROM
                                        ci: CellInstance => Consume[port, ci];
                                        im: Intermediary => EnumerateImmediateConnections[im, CellFinish, [cellward: TRUE, wireward: FALSE]];
                                        wire: Wire => ERROR;
                                        ENDCASE => ERROR;
                                    };
                                EnumerateImmediateConnections[im, CellFinish, [cellward: TRUE, wireward: FALSE]];
                                };
                            wire: Wire => ERROR;
                            ENDCASE => ERROR;
                        };
                    EnumerateImmediateConnections[wire, CellStart];
                    IF wire.containingWire # NIL THEN {
                        index: INT = WireIndex[wire.containingWire, wire];
                        Filter: PROC [parent: Port, w: Vertex] = {
                            port: Port = SubPort[parent, index];
                            Consume[port, w]};
                        WireWork[wire.containingWire, Filter];
                        };
                    };
                WireWork[wire, Consume];
                };
            im: Intermediary => ERROR;
            ci: CellInstance => {
                Elaborate: PROC [port: Port, wire: Wire] = {EnumeratePortAndWire[port, wire, Consume]};
                EnumerateTopConnections[ci, Elaborate];
                };
            ENDCASE => ERROR;
        RETURN};

    EnumerateTopEdges: PUBLIC PROC [ci: CellInstance, Consume: PROC [Port, Wire, Edge]]= {
        Work: PROC [port: Port, v: Vertex, e: Edge] = {
            WITH v SELECT FROM
                wire: Wire => Consume[port, wire, e];
                im: Intermediary => EnumerateImmediateEdges[im, Work, [cellward: FALSE, wireward: TRUE]];
                ci: CellInstance => ERROR;
                ENDCASE => ERROR;
            RETURN};
        EnumerateImmediateEdges[ci, Work];
        RETURN};

    EnumerateTopConnections: PUBLIC PROC [ci: CellInstance, Consume: PROC [Port, Wire]]= {
        Filter: PROC [port: Port, w: Wire, e: Edge] = {Consume[port, w]};
        EnumerateTopEdges[ci, Filter];
        };

    FindImmediateConnection: PUBLIC PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex] = {
        w _ FindImmediateEdge[cellward, port, hint].w;
        RETURN};

    FindImmediateEdge: PUBLIC PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex, e: Edge] = {
        ENABLE Escape => CONTINUE;
        Consume: PROC [tp: Port, tw: Vertex, te: Edge] = {
            IF tp = port THEN {w _ tw; e _ te; Escape};
            };
        EnumerateImmediateEdges[cellward, Consume, [cellward: FALSE, wireward: TRUE], hint];
        RETURN [NIL, NIL]};

    FindTransitiveConnection: PUBLIC PROC [cellward: Vertex, from, to: Port] RETURNS [v: Vertex] = {
        IF to=NIL THEN ERROR;
        IF from=to THEN RETURN [cellward];
        {mid: Vertex ~ IF from=to.parent THEN cellward ELSE FindTransitiveConnection[cellward, from, NARROW[to.parent]];
        IF mid=NIL THEN RETURN [NIL];
        WITH mid SELECT FROM
            ci: CellInstance => NULL;
            im: Intermediary => NULL;
            midw: Wire => RETURN [midw.SubWire[to.PortIndex[]]];
            ENDCASE => ERROR;
        RETURN [FindImmediateConnection[mid, to]]}};

    FindTopEdge: PUBLIC PROC [ci: CellInstance, port: Port] RETURNS [v: Vertex, e: Edge] ~ {
        IF port=ci.type.port THEN RETURN [ci, NIL];
        {pv: Vertex ~ SELECT port.parent FROM
            ci.type.port => ci,
            ENDCASE => FindTopEdge[ci, NARROW[port.parent]].v;
        [v, e] _ FindImmediateEdge[ci, port];
        RETURN}};

    ImParent: PUBLIC PROC [im: Intermediary] RETURNS [v: Vertex] = {
        See: PROC [w: Vertex] = {v _ w};
        EnumerateNeighboringVertices[im, See, [cellward: TRUE, wireward: FALSE]];
        };

    EnumeratePorts: PUBLIC PROC [cellType: CellType, Consume: PROC [Port]] = {
        Work: PROC [port: Port, wire: Wire, wired: BOOL] = {
            subPort: Port _ port.firstChild;
            subWire: Wire _ IF wired THEN wire.firstChild ELSE NIL;
            IF port.wire # wire THEN ERROR Error["Broken"];
            Consume[port];
            WHILE subPort # NIL DO
                IF NOT wired THEN subWire _ subPort.wire ELSE IF subWire = NIL THEN ERROR Error["Broken"];
                Work[subPort, subWire, subWire # NIL];
                subPort _ subPort.next;
                IF wired THEN subWire _ subWire.next;
                ENDLOOP;
            IF wired AND subWire # NIL THEN ERROR Error["Broken"];
            };
        Work[cellType.port, cellType.port.wire, cellType.port.wire # NIL];
        IF cellType.port.next # NIL THEN ERROR Error["Broken"];
        };

    ScanPorts: PUBLIC PROC [cellType: CellType, Consume: PROC [Port] RETURNS [subs, sibs: BOOL _ TRUE]] = {
        Work: PROC [port: Port, wire: Wire, wired: BOOL] RETURNS [sibs: BOOL] = {
            subPort: Port _ port.firstChild;
            subWire: Wire _ IF wired THEN wire.firstChild ELSE NIL;
            subs: BOOL;
            IF port.wire # wire THEN ERROR Error["Broken"];
            [subs, sibs] _ Consume[port];
            IF subs THEN {
                WHILE subPort # NIL DO
                    IF NOT wired THEN subWire _ subPort.wire ELSE IF subWire = NIL THEN ERROR Error["Broken"];
                    IF NOT Work[subPort, subWire, subWire # NIL] THEN RETURN;
                    subPort _ subPort.next;
                    IF wired THEN subWire _ subWire.next;
                    ENDLOOP;
                IF wired AND subWire # NIL THEN ERROR Error["Broken"];
                };
            RETURN};
        IF cellType.port.next # NIL THEN ERROR Error["Broken"];
        [] _ Work[cellType.port, cellType.port.wire, cellType.port.wire # NIL];
        IF cellType.port.next # NIL THEN ERROR Error["Broken"];
        };

    EnumerateInstances: PUBLIC PROC [cellType: CellType, Consume: PROC [CellInstance], mirror: BOOL] = {
        FOR ci: CellInstance _ cellType.firstInstance, ci.nextInstance WHILE ci # NIL DO
            Consume[ci];
            ENDLOOP;
        IF mirror AND cellType.asUnorganized#NIL THEN Consume[cellType.asUnorganized.mirror];
        };

    EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] ~ {
        FOR act: CellType _ cellType.firstArray, act.asArray.nextArray WHILE act#NIL DO Consume[act] ENDLOOP;
        RETURN};

    EnumeratePortAndWire: PUBLIC PROC [port: Port, wire: Wire, Consume: PROC [Port, Wire]] = {
        Consume[port, wire];
        port _ port.firstChild;
        wire _ wire.firstChild;
        WHILE port # NIL AND wire # NIL DO
            EnumeratePortAndWire[port, wire, Consume];
            port _ port.next;
            wire _ wire.next;
            ENDLOOP;
        IF port # NIL OR wire # NIL THEN ERROR Error["Broken"];
        };

    GroupWires: PUBLIC PROC [sibs: Seq--of wire--, parentNames: ListData] RETURNS [parent: Wire] ~ {
        n: NATURAL ~ sibs.GetIntDom.Length.EN;
        isibs: Seq ~ sibs.CreateHashCopy[mappable: [FALSE, TRUE]];
        aSib: Wire ~ NARROW[sibs.APair.it[right].VA];
        grandParent: Wire ~ aSib.containingWire;
        containingCT: CellType ~ aSib.containingCT;
        sibSet: Set ~ isibs.SetOn[right];
        needParent: BOOL _ TRUE;
        highLast, lowLast: Wire _ NIL;
        parent _ NEW [VertexPrivate.wire _ [
            containingCT: containingCT,
            names: parentNames,
            variant: wire[
                containingWire: grandParent
                ]]];
        FOR sib: Wire _ grandParent.FirstChildWire[], sib.NextChildWire[] UNTIL sib=NIL DO
            AddHigh: PROC [x: Wire] ~ {
                x.prev _ highLast;
                IF highLast#NIL THEN highLast.next _ x ELSE grandParent.firstChild _ x;
                highLast _ x;
                RETURN};
            IF sibSet.HasMemA[sib] THEN {
                forget: SteppyNameList _ NIL;
                index: INT ~ isibs.ApplyA[sib, rightToLeft].MI;
                name: SteppyName ~ LSn[LIST[NEW[INT _ index]]];
                ForgetName: PROC [val: Sets.Value] ~ {forget _ CONS[VSn[val], forget]};
                sib.VertexNames.Enumerate[ForgetName];
                FOR forget _ forget, forget.rest WHILE forget#NIL DO ForgetVertexName[sib, forget.first] ENDLOOP;
                UnindexVertexNames[sib];
                sib.containingWire _ parent;
                IndexVertexNames[sib];
                KnowVertexName[sib, name];
                IF needParent THEN {needParent _ FALSE; AddHigh[parent]};
                sib.prev _ lowLast;
                IF lowLast#NIL THEN lowLast.next _ sib ELSE parent.firstChild _ sib;
                lowLast _ sib;
                }
            ELSE {
                AddHigh[sib];
                };
            ENDLOOP;
        parent.lastChild _ lowLast;
        grandParent.lastChild _ highLast;
        highLast.next _ lowLast.next _ NIL;
        IndexVertexNames[parent];
        RETURN};

    GroupPorts: PUBLIC PROC [sibs: Seq--of port--, parentNames: ListData] RETURNS [parent: Port] ~ {
        n: NATURAL ~ sibs.GetIntDom.Length.EN;
        isibs: Seq ~ sibs.CreateHashCopy[mappable: [FALSE, TRUE]];
        aSib: Port ~ NARROW[sibs.APair.it[right].VA];
        grandParent: Port ~ NARROW[aSib.parent];
        containingCT: CellType ~ aSib.PortCCT;
        sibSet: Set ~ isibs.SetOn[right];
        FixInstance: PROC [ci: CellInstance] ~ {
            grandParentV: Vertex ~ FindTopEdge[ci, grandParent].v;
            parentIM: Intermediary ~ CreateIntermediary[from: grandParentV, go: wireward, containingCT: ci.containingCT, port: parent, names: 
            parentNames];
            vs: ARRAY GraphDirection OF Vertex _ ALL[parentIM];
            MoveEdge: PROC [sib: Port, v: Vertex, e: Edge] ~ {
                IF e.sides[wireward].v#v THEN ERROR;
                IF NOT sibSet.HasMemA[sib] THEN RETURN;
                RemoveEdge[e];
                vs[wireward] _ v;
                AddEdge[vs, sib];
                RETURN};
            grandParentV.EnumerateImmediateEdges[Consume: MoveEdge, filter: [cellward: FALSE, wireward: TRUE]];
            RETURN};
        needParent: BOOL _ TRUE;
        highLast, lowLast: Port _ NIL;
        parent _ NEW [PortPrivate _ [
            parent: grandParent,
            names: parentNames
            ]];
        FOR sib: Port _ grandParent.FirstChildPort[], sib.NextChildPort[] UNTIL sib=NIL DO
            AddHigh: PROC [x: Port] ~ {
                x.prev _ highLast;
                IF highLast#NIL THEN highLast.next _ x ELSE grandParent.firstChild _ x;
                highLast _ x;
                RETURN};
            IF sibSet.HasMemA[sib] THEN {
                index: INT ~ isibs.ApplyA[sib, rightToLeft].MI;
                name: SteppyName ~ LSn[LIST[NEW[INT _ index]]];
                sib.names _ CreateSteppyNames[LIST[name]];
                IF needParent THEN {needParent _ FALSE; AddHigh[parent]};
                sib.prev _ lowLast;
                IF lowLast#NIL THEN lowLast.next _ sib ELSE parent.firstChild _ sib;
                lowLast _ sib;
                sib.parent _ parent;
                }
            ELSE AddHigh[sib];
            ENDLOOP;
        parent.lastChild _ lowLast;
        grandParent.lastChild _ highLast;
        highLast.next _ lowLast.next _ NIL;
        containingCT.EnumerateInstances[FixInstance, TRUE];
        RETURN};

    ExpandName: PUBLIC PROC [fileName, defaultExtension: ROPE] RETURNS [fullFName: ROPE, cp: FS.ComponentPositions] = {
        [fullFName, cp, ] _ FS.ExpandName[fileName];
        IF defaultExtension.Length[]>0 AND cp.ext.start = cp.base.start+cp.base.length THEN {
            fileName _ FS.ConstructFName[[
                server: fullFName.Substr[cp.server.start, cp.server.length],
                dir: fullFName.Substr[cp.dir.start, cp.dir.length],
                subDirs: fullFName.Substr[cp.subDirs.start, cp.subDirs.length],
                base: fullFName.Substr[cp.base.start, cp.base.length],
                ext: defaultExtension,
                ver: fullFName.Substr[cp.ver.start, cp.ver.length]
                ]];
            [fullFName, cp, ] _ FS.ExpandName[fileName];
            };
        };

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

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

    EnumeratePort: PUBLIC PROC [port: Port, Consume: PROC [Port] RETURNS [doKids, moreSibs: BOOL _ TRUE]] RETURNS [didKids, moreSibs: 
    BOOL] ~ {
        [didKids, moreSibs] _ Consume[port];
        IF didKids THEN {
            FOR port _ port.FirstChildPort, port.NextChildPort UNTIL port=NIL DO IF NOT EnumeratePort[port, Consume].moreSibs THEN EXIT ENDLOOP;
            RETURN};
        RETURN};

    EnumerateWire: PUBLIC PROC [wire: Wire, Consume: PROC [Wire] RETURNS [doKids, moreSibs: BOOL _ TRUE]] RETURNS [didKids, moreSibs: 
    BOOL] ~ {
        [didKids, moreSibs] _ Consume[wire];
        IF didKids THEN {
            FOR wire _ wire.FirstChildWire, wire.NextChildWire UNTIL wire=NIL DO IF NOT EnumerateWire[wire, Consume].moreSibs THEN EXIT ENDLOOP;
            RETURN};
        RETURN};

    END.