
<<LichenDataImpl.Mesa>>
    <<Mike Spreitzer January 27, 1987 12:32:14 pm PST>>
    <<Last tweaked by Mike Spreitzer on May 4, 1987 4:02:46 pm PDT>>

    DIRECTORY AMBridge, Asserting, Basics, Convert, InterpreterOps, IO, LichenArrayStuff, LichenDataOps, LichenDataStructure, 
    LichenSetTheory, Rope, SymTab, ViewerIO;

    LichenDataImpl: CEDAR PROGRAM
        IMPORTS Asserting, IO, LichenArrayStuff, LichenDataStructure, LichenSetTheory, Rope, ViewerIO
        EXPORTS LichenDataStructure, LichenDataOps =

        BEGIN OPEN LichenSetTheory, LichenDataStructure, LichenArrayStuff;

        Escape: ERROR = CODE;

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

        endOfQ: PUBLIC Vertex _ NEW [VertexPrivate.intermediate];

        EnumerateImmediateEdges: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ 
        ALL[TRUE], order: Order _ any] = {
            nextEdge: Edge _ SELECT order FROM    --these depend on AI1
                forward, any => v.firstEdge,
                backward => v.lastEdge,
                ENDCASE => ERROR;
            FOR e: Edge _ nextEdge, nextEdge WHILE e # NIL DO
                selfward: GraphDirection = SELECT v.class FROM
                    cell => cellward,
                    wire => wireward,
                    intermediate => SELECT v FROM
                        e.sides[wireward].v => wireward,
                        e.sides[cellward].v => cellward,
                        ENDCASE => ERROR,
                    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 Consume[e.port, w, e];
                ENDLOOP;
            };

        EnumerateImmediateConnections: PUBLIC PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ 
        ALL[TRUE], order: Order _ any] = {
            Filter: PROC [port: Port, w: Vertex, e: Edge] = {Consume[port, w]};
            EnumerateImmediateEdges[v, Filter, filter, order];
            };

        EnumerateNeighboringVertices: PUBLIC PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]] = {
            Filter: PROC [port: Port, w: Vertex, e: Edge] = {Consume[w]};
            EnumerateImmediateEdges[v, Filter, filter];
            };

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

        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;
                };
            EnumerateImmediateEdges[ci, Work];
            };

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

        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];
            ERROR--not found--;
            };

        FindTransitiveConnection: PUBLIC PROC [cellward: Vertex, port: Port] RETURNS [w: Wire] = {
            ENABLE Escape => CONTINUE;
            Tryit: PROC [p: Port, v: Vertex] = {
                IF port = p THEN {w _ NARROW[v]; Escape};
                };
            EnumerateTransitiveConnections[cellward, Tryit];
            ERROR--not found--;
            };

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

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

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

        WireIndex: PUBLIC PROC [parent, child: Wire] RETURNS [index: INT] = {
            index _ 0;
            FOR x: Wire _ parent.firstChild, x.next WHILE x # child DO index _ index + 1 ENDLOOP;
            index _ index;
            };

        SubWire: PUBLIC PROC [parent: Wire, index: INT] RETURNS [child: Wire] = {
            FOR child _ parent.firstChild, child.next WHILE index > 0 DO index _ index - 1 ENDLOOP;
            };

        PortCCT: PUBLIC PROC [port: Port] RETURNS [containingCT: CellType] = {
            DO
                WITH port.parent SELECT FROM
                    ct: CellType => RETURN [ct];
                    p: Port => port _ p;
                    ENDCASE => ERROR;
                ENDLOOP;
            };

        PortIndex: PUBLIC PROC [parent, child: Port] RETURNS [index: INT] = {
            index _ 0;
            FOR x: Port _ parent.firstChild, x.next WHILE x # child DO index _ index + 1 ENDLOOP;
            index _ index;
            };

        SubPort: PUBLIC PROC [parent: Port, index: INT] RETURNS [child: Port] = {
            FOR child _ parent.firstChild, child.next WHILE index > 0 DO index _ index - 1 ENDLOOP;
            };

        portToInternalWire: PUBLIC Mapper ~ CreateProceduralMapper[MapPortToInternalWire];

        MapPortToInternalWire: PROC [m: Mapper, domain: REF ANY] RETURNS [range: REF ANY] ~ {
            port: Port ~ NARROW[domain];
            IF port.wire=NIL THEN ERROR;
            range _ port.wire;
            };

        EnsureAllIn: PUBLIC PROC [design: Design] = {
            IF design.allKnown THEN RETURN;
            design.allKnown _ TRUE;
            EnumerateCellTypes[design, EnsurePrivate];
            };

        EnsurePublic: PUBLIC PROC [ct: CellType] = {
            IF NOT ct.publicKnown THEN ERROR Error["Broken: Found cell type with undefined interface"];
            IF ct.port = NIL THEN ERROR;
            };

        EnsurePrivate: PUBLIC PROC [ct: CellType] = {
            IF NOT ct.privateKnown THEN {
                ct.class.DefinePrivates[ct];
                IF NOT ct.privateKnown THEN ERROR;
                };
            };

        ExpansionKnown: PUBLIC PROC [ct: CellType] RETURNS [known: BOOL] = {
            known _ ct.asUnorganized # NIL OR ct.asArray # NIL;
            };

        NoteChange: PUBLIC PROC [cellType: CellType] = {
            NULL--er, we haven't yet figured out just what to do about the fact that cell types can change--;
            };

        AddPort: PUBLIC PROC [p: PortPrivate _ []] RETURNS [port: Port] = {
            port _ NEW [PortPrivate _ p];
            WITH p.parent SELECT FROM
                pp: Port => {
                    port.next _ NIL;
                    port.prev _ pp.lastChild;
                    pp.lastChild _ port;
                    IF port.prev # NIL THEN port.prev.next _ port ELSE pp.firstChild _ port;
                    IF Asserting.FnVals[nameReln, port.other]=NIL AND port.wire # NIL THEN port.other _ 
                    Asserting.Union[Asserting.AssertionsAbout[nameReln, port.wire.other], port.other];
                    };
                ct: CellType => {
                    IF ct.port # NIL THEN ERROR;
                    ct.port _ port;
                    port.next _ port.prev _ NIL;
                    port.other _ Asserting.Assert[nameReln, LIST[R["PORTS"]], port.other];
                    };
                ENDCASE => ERROR;
            };

        R: PROC [r: ROPE] RETURNS [r2: ROPE] = INLINE {r2 _ r}--stupid goddam anachronism--;

        FullyAddPort: PUBLIC PROC [p: PortPrivate _ [], andReportConnectionTo: CellInstance _ NIL] RETURNS [port: Port, connection: Wire _ 
        NIL] = {
            ct: CellType = PortCCT[port _ AddPort[p]];
            portName: ROPE = Describe[port, ct.port];
            FixInstance: PROC [ci: CellInstance] = {
                instanceName: ROPE = Describe[ci, ci.containingCT].Cat["/", portName];
                w: Wire = CreateWire[ci.containingCT, NIL, Asserting.Assert[nameReln, LIST[instanceName], NIL]];
                AddEdge[[cellward: ci, wireward: w], port];
                IF andReportConnectionTo = ci THEN connection _ w;
                };
            FixArray: PROC [act: CellType] ~ {MakeGroupsForPort[act.asArray, port]};
            IF ct.asUnorganized # NIL THEN {
                IF ct.asUnorganized.mirror = NIL THEN ERROR;
                IF p.wire = NIL THEN ERROR;
                AddEdge[[cellward: ct.asUnorganized.mirror, wireward: port.wire], port];
                };
            IF ct.asArray # NIL THEN {
                NULL--we don't need to do anything--;
                };
            EnumerateInstances[ct, FixInstance];
            EnumerateArrays[ct, FixArray];
            };

        RemovePort: PUBLIC PROC [port: Port] = {
            WITH port.parent SELECT FROM
                pp: Port => {
                    IF port.next = NIL THEN pp.lastChild _ port.prev ELSE port.next.prev _ port.prev;
                    IF port.prev = NIL THEN pp.firstChild _ port.next ELSE port.prev.next _ port.next;
                    };
                ct: CellType => {
                    ERROR --I don't think we ever really want to Remove the root port--;
                    };
                ENDCASE => ERROR;
            };

        AddEdge: PUBLIC PROC [vs: ARRAY GraphDirection OF Vertex, port: Port] = {
            e: Edge = NEW [EdgePrivate _ [port: port]];
            FOR dir: GraphDirection IN GraphDirection DO e.sides[dir].v _ vs[dir] ENDLOOP;
            FOR side: GraphDirection IN GraphDirection DO
                LinkEdge[vs[side], e, side];
                ENDLOOP;
            };

        LinkEdge: PROC [v: Vertex, e: Edge, side: GraphDirection] = {
            prev, next: Edge;
            SELECT side FROM
                cellward => {
                    prev _ IF e.port.prev # NIL THEN FindImmediateEdge[v, e.port.prev, backward].e ELSE v.lastEdge;
                    };
                wireward => prev _ v.lastEdge;
                ENDCASE => ERROR;
            e.sides[side].next _ next _ IF prev # NIL THEN prev.sides[side].next ELSE NIL;
            e.sides[side].prev _ prev;
            IF prev = NIL THEN v.firstEdge _ e ELSE prev.sides[side].next _ e;
            IF next = NIL THEN v.lastEdge _ e ELSE next.sides[side].prev _ e;
            };

        AddEdges: PUBLIC PROC [vs: ARRAY GraphDirection OF Vertex, port: Port] = {
            rootPort: Port = WITH vs[cellward] SELECT FROM
                ci: CellInstance => ci.type.port,
                im: Intermediary => im.port,
                w: Wire => ERROR Error["Broken"],
                ENDCASE => ERROR;
            FindVertex: PROC [port: Port] RETURNS [v: Vertex] = {
                cellward: Vertex;
                IF port = rootPort THEN RETURN [vs[cellward]];
                cellward _ FindVertex[NARROW[port.parent]];
                v _ FindImmediateConnection[cellward, port];
                IF v # NIL THEN RETURN;
                v _ CreateIntermediary[cellward, wireward, cellward.containingCT, port];
                };
            immediatelyCellward: Vertex = FindVertex[NARROW[port.parent]];
            AddEdge[[cellward: immediatelyCellward, wireward: vs[wireward]], port];
            };

        RemoveEdge: PUBLIC PROC [e: Edge] = {
            FOR dir: GraphDirection IN GraphDirection DO
                [e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge] _ UnlinkEdge[e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge, e, dir];
                ENDLOOP;
            };

        UnlinkEdge: PROC [head, tail, e: Edge, dir: GraphDirection] RETURNS [newHead, newTail: Edge] = {
            newHead _ head; newTail _ tail;
            IF e.sides[dir].next # NIL THEN e.sides[dir].next.sides[dir].prev _ e.sides[dir].prev ELSE newTail _ e.sides[dir].prev;
            IF e.sides[dir].prev # NIL THEN e.sides[dir].prev.sides[dir].next _ e.sides[dir].next ELSE newHead _ e.sides[dir].next;
            };

        RemoveEdges: PUBLIC PROC [e: Edge] = {
            cellward: Vertex = e.sides[cellward].v;
            RemoveEdge[e];
            IF ISTYPE[cellward, Intermediary] AND (cellward.lastEdge = NIL OR cellward.lastEdge.sides[wireward].v = cellward--AI1 used here--) 
            THEN RemoveEdges[cellward.firstEdge--AI1 used here--];
            };

        UnlinkPort: PUBLIC PROC [ci: CellInstance, port: Port] = {
            RemoveEdge[FindImmediateEdge[ci, port].e]};

        UnlinkPorts: PUBLIC PROC [ci: CellInstance, ports: Set--of Port--] ~ {
            n: NATURAL ~ ports.Size[];
            i: NATURAL _ 0;
            Work: PROC [port: Port, v: Vertex, e: Edge] ~ {
                IF port=NIL THEN ERROR;
                IF ports.HasMember[port] THEN {
                    RemoveEdges[e];
                    i _ i + 1;
                    IF i=n THEN Escape;
                    }
                ELSE SELECT v.class FROM
                    cell => ERROR;
                    intermediate => EnumerateImmediateEdges[v, Work, [cellward: FALSE, wireward: TRUE]];
                    wire => NULL;
                    ENDCASE => ERROR;
                };
            EnumerateImmediateEdges[ci, Work !Escape => CONTINUE];
            IF i#n THEN ERROR;
            };

        Instantiate: PUBLIC PROC [type, containingCT: CellType, other: Assertions _ NIL] RETURNS [ci: CellInstance] = {
            ci _ NEW [VertexPrivate.cell _ [
                containingCT: containingCT,
                other: other,
                variant: cell[
                    type: type,
                    nextInstance: NIL,
                    prevInstance: type.lastInstance]]];
            type.lastInstance _ ci;
            IF ci.prevInstance # NIL THEN ci.prevInstance.nextInstance _ ci ELSE ci.type.firstInstance _ ci;
            type.useCount _ type.useCount + 1;
            [] _ containingCT.asUnorganized.containedInstances.UnionSingleton[ci];
            NoteNewPart[ci];
            };

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

        EnumerateParts: PUBLIC PROC [ct: CellType, Consume: PROC [Vertex], mirrorToo: BOOL] ~ {
            u: Unorganized ~ ct.asUnorganized;
            PerCell: PROC [ra: REF ANY] ~ {
                ci: CellInstance ~ NARROW[ra];
                PassIMs: PROC [p: Port, v: Vertex] ~ {
                    WITH v SELECT FROM
                        ci: CellInstance => ERROR;
                        w: Wire => NULL;
                        im: Intermediary => {
                            Consume[im];
                            EnumerateImmediateConnections[im, PassIMs, [cellward: FALSE, wireward: TRUE]];
                            };
                        ENDCASE => ERROR;
                    };
                Consume[ci];
                EnumerateImmediateConnections[ci, PassIMs];
                };
            PassChildren: PROC [w: Wire] ~ {
                FOR w _ FirstChildWire[w], NextChildWire[w] WHILE w # NIL DO
                    Consume[w];
                    PassChildren[w];
                    ENDLOOP;
                };
            IF u=NIL THEN ERROR;
            PassChildren[u.internalWire];
            u.containedInstances.Enumerate[PerCell];
            IF mirrorToo THEN PerCell[u.mirror];
            };

        PortForWire: PUBLIC PROC [ct: CellType, internal: Wire, ci: CellInstance, mayAdd: BOOL] RETURNS [port: Port, external: Wire] = {
            See: PROC [p: Port, v: Vertex] = {
                IF IsMirror[NARROW[v]] THEN port _ p;
                };
            IF internal.containingCT # ct THEN ERROR;
            internal.EnumerateTransitiveConnections[See];
            IF port = NIL THEN {
                IF mayAdd THEN {
                    [port, external] _ FullyAddPort[
                        [parent: ct.port, wire: internal, other: Asserting.Assert1[nameReln, Describe[internal, ct.asUnorganized.internalWire], NIL]],
                        ci
                        ];
                    };
                }
            ELSE IF ci # NIL THEN external _ FindTransitiveConnection[ci, port];
            };

        FullyInstantiate: PUBLIC PROC [type, containingCT: CellType, other: Assertions _ NIL] RETURNS [ci: CellInstance] = {
            ci _ Instantiate[type, containingCT, other];
            {instanceName: ROPE = Describe[ci, ci.containingCT];
            FOR port: Port _ type.port.FirstChildPort[], port.NextChildPort[] WHILE port # NIL DO
                portName: ROPE = Describe[port, type.port];
                wireName: ROPE = Rope.Cat[instanceName, "/", portName];
                w: Wire = CreateWire[ci.containingCT, NIL, Asserting.Assert[nameReln, LIST[wireName], NIL]];
                AddEdge[[cellward: ci, wireward: w], port];
                ENDLOOP;
            ci _ ci;
            }};

        CreateWire: PUBLIC PROC [containingCT: CellType, containingWire: Wire _ NIL, other: Assertions _ NIL, copy: Wire _ NIL] RETURNS [w: 
        Wire] = {
            IF containingWire = NIL THEN containingWire _ containingCT.asUnorganized.internalWire;
            w _ NEW [VertexPrivate.wire _ [
                containingCT: containingCT,
                other: other,
                variant: wire[
                    containingWire: containingWire,
                    next: NIL,
                    prev: IF containingWire#NIL THEN containingWire.lastChild ELSE NIL
                    ]]];
            IF w.prev # NIL THEN w.prev.next _ w ELSE IF containingWire#NIL THEN containingWire.firstChild _ w;
            IF containingWire#NIL THEN containingWire.lastChild _ w ELSE containingCT.asUnorganized.internalWire _ w;
            IF copy # NIL THEN WireCopy[copy, w];
            NoteNewPart[w];
            };

        WireCopy: PROC [from, to: Wire] = {
            IF Asserting.FnVals[nameReln, to.other]=NIL THEN to.other _ Asserting.Union[Asserting.AssertionsAbout[nameReln, from.other], 
            to.other];
            FOR child: Wire _ from.FirstChildWire[], child.NextChildWire[] WHILE child # NIL DO
                [] _ CreateWire[to.containingCT, to, NIL, child];
                ENDLOOP;
            };

        CreateIntermediary: PUBLIC PROC [from: Vertex, go: GraphDirection, containingCT: CellType, port: Port, other: Assertions _ NIL] 
        RETURNS [im: Intermediary] = {
            vs: ARRAY GraphDirection OF Vertex _ ALL[from];
            vs[go] _ im _ NEW [VertexPrivate.intermediate _ [
                containingCT: containingCT,
                other: other,
                variant: intermediate[port]]];
            AddEdge[vs, port];
            NoteNewPart[im];
            };

        NoteNewPart: PROC [v: Vertex] = {
            ct: CellType = v.containingCT;
            pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
            PerName: PROC [assertion: Asserting.Assertion] = {
                name: ROPE = NARROW[Asserting.TermsOf[assertion].first];
                SELECT pbn.Map[name] FROM
                    NIL => IF NOT pbn.PutMapping[name, v] THEN ERROR;
                    v => NULL;
                    ENDCASE => ERROR;
                };
            IF pbn = NIL THEN RETURN;
            Asserting.EnumerateAssertionsAbout[nameReln, v.other, PerName];
            };

        CreateCellType: PUBLIC PROC [design: Design, cellTypeName: ROPE, class: CellClass, internals: BOOL, otherPublic, otherPrivate: 
        Assertions _ NIL] RETURNS [ct: CellType] = {
            pbn: Mapper = CreateHashDictionary[TRUE];
            ct _ NEW [CellTypePrivate _ [
                class: class,
                designs: CreateHashSet[],
                publicKnown: TRUE,
                privateKnown: TRUE,
                otherPublic: Asserting.Assert[nameReln, LIST[cellTypeName], otherPublic],
                otherPrivate: otherPrivate
                ]];
            [] _ AddPort[[parent: ct]];
            IF internals THEN {
                iw: Wire;
                ct.otherPrivate _ Asserting.AssertFn1[partsByNameKey, pbn, ct.otherPrivate];
                ct.asUnorganized _ NEW [UnorganizedPrivate _ [
                    containedInstances: CreateHashSet[]
                    ]];
                iw _ CreateWire[ct];
                IF ct.asUnorganized.internalWire # iw THEN ERROR;
                AddMirror[ct];
                };
            [] _ design.cellTypes.UnionSingleton[ct];
            [] _ ct.designs.UnionSingleton[design];
            };

        CreateArray: PUBLIC PROC [design: Design, cellTypeName: ROPE, class: CellClass, eltType: CellType, size, jointsPeriod: Size2, 
        borders: ARRAY Dim OF ARRAY End OF NAT, otherPublic, otherPrivate: Assertions _ NIL] RETURNS [ct: CellType] = {
            nj: INT = jointsPeriod[Foo] * jointsPeriod[Bar];
            gps: GroupingParmses = [
                Foo: ComputeGroupingParms[size[Foo], jointsPeriod[Foo], borders[Foo]],
                Bar: ComputeGroupingParms[size[Bar], jointsPeriod[Bar], borders[Bar]]];
            middlea: Range2 = [gps[Foo].middle, gps[Bar].middle];
            ngi: NAT = gps[Foo].sum * gps[Bar].sum;
            a: Array = NEW [ArrayPrivate _ [
                eltType: eltType,
                prevArray: eltType.lastArray,
                nextArray: NIL,
                size: size,
                jointsPeriod: jointsPeriod,
                groupingParmses: gps,
                groupingses: CreateRefSeq[ngi],
                toRole: [[CreateRefTable[], CreateRefTable[]], [CreateRefTable[], CreateRefTable[]]],
                roles: [CreateVarRefSeq[], CreateVarRefSeq[]],
                joints: [CreateRefSeq[nj], CreateRefSeq[nj]],
                toWire: CreateRefTable[],
                wires: CreateHashSet[],
                portWire: CreateRefTable[]
                ]];
            
            
            ct _ CreateCellType[design, cellTypeName, class, FALSE, otherPublic, otherPrivate];
            ct.asArray _ a;
            IF a.prevArray # NIL THEN a.prevArray.asArray.nextArray _ ct ELSE eltType.firstArray _ ct;
            eltType.lastArray _ ct;
            eltType.useCount _ eltType.useCount + 1;
            FOR gi: NAT IN [0 .. ngi) DO
                a.groupingses[gi] _ NEW [GroupingsPrivate _ [
                    toGroup: CreateRefTable[],
                    groups: CreateHashSet[]
                    ]];
                ENDLOOP;
            FOR d: Dim IN Dim DO FOR 
                phase2: Nat2 = [
                rawLair: Range2 = SELECT d FROM
                    Foo => [[0, a.size[Foo]-1], [0, a.size[Bar]-0]],
                    Bar => [[0, a.size[Foo]-0], [0, a.size[Bar]-1]],
                    ENDCASE => ERROR;
                jiir: Range2 = Range2Div[r: rawLair, 
                size2: Size2 = RangeShape[jiir];
                i: INT = ArrayJointIndex[a, phase2];
                middlej: Range2 = Range2Div[r: ShaveRange2Top1[middlea, d], 
                jgps: GroupingParmses = [
                    Foo: ComputeJGP[jiir[Foo], middlej[Foo]],
                    Bar: ComputeJGP[jiir[Bar], middlej[Bar]]];
                njgi: NAT = jgps[Foo].sum * jgps[Bar].sum;
                j: Joint = a.joints[d][i] _ NEW [JointPrivate _ [
                    size2: size2,
                    size: size2[Foo]*size2[Bar],
                    groupingParmses: jgps,
                    ties: CreateRefSeq[njgi],
                    toTie: [CreateRefSeq[njgi], CreateRefSeq[njgi]]
                    ]];
                FOR jgi: NAT IN [0 .. njgi) DO
                    j.ties[jgi] _ CreateHashSet[];
                    j.toTie[low][jgi] _ CreateRefTable[];
                    j.toTie[high][jgi] _ CreateRefTable[];
                    ENDLOOP;
                design _ design;
                ENDLOOP ENDLOOP ENDLOOP;
            };

        ComputeGroupingParms: PROC [size, jointsPeriod: NAT, borders: ARRAY End OF NAT] RETURNS [gp: GroupingParms] = {
            peculiar: NAT = borders[low] + borders[high];
            IF peculiar >= size THEN RETURN [[
                middle: [size, size],
                firstHigh: size,
                sum: size,
                
            {firstHighGI: NAT = borders[low] + jointsPeriod;
            firstHighI: NAT = size - borders[high];
            gp _ [
                middle: [borders[low], firstHighI],
                firstHigh: firstHighGI,
                sum: peculiar + jointsPeriod,
                
            RETURN [gp];
            }};

        ComputeJGP: PROC [jiir, middle: Range] RETURNS [gp: GroupingParms] = {
            hasMiddle: BOOL = middle.maxPlusOne > middle.min;
            nMid: NAT = IF hasMiddle THEN 1 ELSE 0;
            nHigh: NAT = jiir.maxPlusOne - middle.maxPlusOne;
            nLow: NAT = middle.min - jiir.min;
            peculiar: NAT = nLow + nHigh;
            firstHigh: NAT = nLow + nMid;
            IF jiir.min # 0 THEN ERROR;
            gp _ [
                middle: middle,
                firstHigh: firstHigh,
                sum: peculiar + nMid,
                
                ];
            RETURN [gp];
            };

        KnowVertexName: PUBLIC PROC [v: Vertex, name: ROPE] = {
            ct: CellType = v.containingCT;
            pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
            last: Assertions _ NIL;
            next: Assertions _ v.other;
            IF pbn # NIL THEN {
                SELECT pbn.Map[name] FROM
                    v => RETURN;
                    NIL => IF NOT pbn.PutMapping[name, v] THEN ERROR;
                    ENDCASE => ERROR;
                };
            WHILE next#NIL AND (Asserting.RelnOf[next.first]#nameReln OR CompareNameQuality[name, NARROW[Asserting.TermsOf[next.first].first]] 
            = less) DO
                last _ next;
                next _ next.rest;
                ENDLOOP;
            next _ CONS[Asserting.Cons[nameReln, LIST[name]], next];
            IF last=NIL THEN v.other _ next ELSE last.rest _ next;
            };

        CompareNameQuality: PROC [n1, n2: ROPE] RETURNS [Basics.Comparison] ~ {
            s1, s2, d1, d2: NATURAL;
            [s1, d1] _ Grade[n1];
            [s2, d2] _ Grade[n2];
            RETURN [SELECT TRUE FROM
                s1<s2 => greater,
                s1>s1 => less,
                d1<d2 => greater,
                d1>d2 => less,
                ENDCASE => SELECT n2.Length[]-n1.Length[] FROM
                    >0 => greater,
                    <0 => less,
                    ENDCASE => equal];
            };

        Grade: PROC [name: ROPE] RETURNS [slashes, dots: NATURAL _ 0] ~ {
            len: INT ~ name.Length[];
            FOR index: INT _ name.SkipTo[0, "/."], name.SkipTo[index+1, "/."] WHILE index < len DO
                SELECT name.Fetch[index] FROM
                    '/ => slashes _ slashes+1;
                    '. => dots _ dots+1;
                    ENDCASE => ERROR;
                ENDLOOP;
            };

        DeleteVertex: PUBLIC PROC [v: Vertex] = {
            ct: CellType = v.containingCT;
            pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
            PerName: PROC [assertion: Asserting.Assertion] = {
                name: ROPE = NARROW[Asserting.TermsOf[assertion].first];
                IF pbn.PutMapping[name, NIL] THEN ERROR;
                };
            Killit: PROC [p: Port, w: Vertex, e: Edge] = {
                RemoveEdge[e];
                WITH w SELECT FROM
                    ci: CellInstance => NULL;
                    im: Intermediary => IF w = e.sides[wireward].v THEN DeleteVertex[w];
                    wire: Wire => NULL;
                    ENDCASE => ERROR;
                };
            EnumerateImmediateEdges[v, Killit];
            WITH v SELECT FROM
                ci: CellInstance => {
                    IF ci.nextInstance # NIL THEN ci.nextInstance.prevInstance _ ci.prevInstance ELSE ci.type.lastInstance _ ci.prevInstance;
                    IF ci.prevInstance # NIL THEN ci.prevInstance.nextInstance _ ci.nextInstance ELSE ci.type.firstInstance _ ci.nextInstance;
                    IF NOT v.containingCT.asUnorganized.containedInstances.RemoveElt[ci] THEN ERROR;
                    ci.type.useCount _ ci.type.useCount - 1;
                    };
                im: Intermediary => NULL;
                w: Wire => {
                    IF w.next # NIL THEN w.next.prev _ w.prev ELSE w.containingWire.lastChild _ w.prev;
                    IF w.prev # NIL THEN w.prev.next _ w.next ELSE w.containingWire.firstChild _ w.next;
                    };
                ENDCASE => ERROR;
            IF pbn # NIL THEN Asserting.EnumerateAssertionsAbout[nameReln, v.other, PerName];
            };

        IsMirror: PUBLIC PROC [v: CellInstance] RETURNS [isMirror: BOOL] = {
            isMirror _ v.type = v.containingCT;
            };

        AddMirror: PUBLIC PROC [lct: CellType] = {
            CreateMirrorBinding: PROC [port: Port, cellward: Vertex] = {
                FOR subPort: Port _ port.firstChild, subPort.next WHILE subPort # NIL DO
                    subVertex: Vertex;
                    IF subPort.wire # NIL THEN {
                        AddEdge[[cellward: cellward, wireward: subPort.wire], subPort]}
                    ELSE {
                        subVertex _ CreateIntermediary[cellward, wireward, lct, subPort, Asserting.Filter[nameReln, subPort.other].about];
                        CreateMirrorBinding[subPort, subVertex];
                        }
                    ENDLOOP;
                };
            v: CellInstance = NEW [VertexPrivate.cell _ [
                containingCT: lct,
                other: Asserting.Assert[nameReln, LIST[R["mirror"]], NIL],
                variant: cell[type: lct--AM2 says not to link it--]
                ]];
            lct.asUnorganized.mirror _ v;
            CreateMirrorBinding[lct.port, v];
            };

        VarRefSeqAppend: PUBLIC PROC [vrs: VarRefSeq, value: REF ANY] = {
            IF vrs.length = vrs.refs.length THEN {
                oldRefs: RefSeq = vrs.refs;
                vrs.refs _ CreateRefSeq[MAX[oldRefs.length*2, 1]];
                FOR i: INT IN [0 .. oldRefs.length) DO
                    vrs.refs[i] _ oldRefs[i];
                    ENDLOOP;
                };
            vrs.refs[vrs.length] _ value;
            vrs.length _ vrs.length + 1;
            };

        FloorDiv: PUBLIC PROC [num, den: INT] RETURNS [quot: INT] = {
            IF den < 0 THEN {den _ -den; num _ -num};
            IF num < 0 THEN num _ num - (den-1);
            quot _ num/den;
            };

        CeilDiv: PUBLIC PROC [num, den: INT] RETURNS [quot: INT] = {
            IF den < 0 THEN {den _ -den; num _ -num};
            IF num > 0 THEN num _ num + (den-1);
            quot _ num/den;
            };

        Choose2: PROC [n: INT] RETURNS [nChoose2: INT] = INLINE {
            nChoose2 _ n*(n-1)/2};

        Log: PUBLIC PROC [fmt: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL] = {
            DO
                IF log = NIL THEN log _ ViewerIO.CreateViewerStreams["Lichen Debugging Log"].out;
                log.PutF[fmt, [refAny[v1]], [refAny[v2]], [refAny[v3]], [refAny[v4]], [refAny[v5]] !IO.Error => IF ec = StreamClosed THEN {log _ 
                NIL; LOOP}];
                EXIT;
                ENDLOOP;
            };
            log: IO.STREAM _ NIL;

        END.