
<<LichenDataImpl.Mesa>>
<<Last Edited by: Spreitzer, June 13, 1986 2:53:21 pm PDT>>

    DIRECTORY AMBridge, Asserting, Convert, HashTable, InterpreterOps, IntHashTable, IO, LichenDataStructure, LichenDataOps, 
    LichenSetTheory, Rope, StructuredStreams, SymTab, UnparserBuffer, ViewerIO;

    LichenDataImpl: CEDAR PROGRAM
        IMPORTS AMBridge, Asserting, Convert, HashTable, InterpreterOps, IntHashTable, IO, LichenDataStructure, LichenSetTheory, Rope, 
        StructuredStreams, UnparserBuffer, ViewerIO
        EXPORTS LichenDataStructure, LichenDataOps =

        BEGIN OPEN LichenSetTheory, LichenDataStructure, SS:StructuredStreams, UB:UnparserBuffer;

        nyet: PUBLIC ERROR = CODE;
        Warning: PUBLIC SIGNAL [msg: ROPE _ NIL, v1, v2, v3, v4, v5: REF ANY _ NIL] = CODE;
        Error: PUBLIC ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL] = CODE;

        nameReln: PUBLIC ATOM _ $LichenName;
        step: ROPE = ".";

        partsByNameKey: PUBLIC ATOM _ $LichenNameToPart;

        DimName: ARRAY Dim OF ROPE = [Foo: "Foo", Bar: "Bar"];

        Describe: PUBLIC PROC [subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [name: ROPE] = {
            GetShort: PROC [oldAssns: Assertions] RETURNS [newAssns: Assertions, name: ROPE] = {
                name _ NARROW[Asserting.FnVal[nameReln, newAssns _ oldAssns]];
                IF name = NIL THEN {
                    name _ nameGen.GenerateName[nameGen.data, subject];
                    newAssns _ Asserting.Assert[nameReln, LIST[name], newAssns];
                    };
                };
            IF nameGen = NIL THEN nameGen _ defaultNameGen;
            IF subject = relativeTo THEN name _ NIL ELSE WITH subject SELECT FROM
                d: Design => {
                    short: ROPE;
                    [d.other, short] _ GetShort[d.other];
                    name _ short;
                    };
                ct: CellType => {
                    short: ROPE;
                    [ct.otherPublic, short] _ GetShort[ct.otherPublic];
                    name _ IF ct.designs.HasMember[relativeTo] OR ct.designs.Size[]=0 THEN short ELSE Describe[GetADesign[ct], relativeTo, 
                    nameGen].Cat[step, short];
                    };
                v: Vertex => {
                    short: ROPE;
                    parent: REF ANY;
                    [v.other, short] _ GetShort[v.other];
                    WITH v SELECT FROM
                        ci: CellInstance => parent _ v.containingCT;
                        im: Intermediary => parent _ ImParent[im];
                        w: Wire => parent _ WireContainer[w];
                        ENDCASE => ERROR;
                    name _ IF relativeTo = parent OR parent = NIL THEN short ELSE Describe[parent, relativeTo, nameGen].Cat[step, short];
                    };
                port: Port => {
                    short: ROPE;
                    parent: REF ANY = port.parent;
                    [port.other, short] _ GetShort[port.other];
                    name _ IF relativeTo = parent OR parent = NIL THEN short ELSE Describe[parent, relativeTo, nameGen].Cat[step, short];
                    };
                ENDCASE => ERROR;
            };

        GetADesign: PROC [ct: CellType] RETURNS [d: Design] = {
            See: PROC [ra: REF ANY] = {d _ NARROW[ra]};
            IF ct.designs.Size[]  = 0 THEN RETURN [NIL];
            ct.designs.Enumerate[See];
            };

        WireContainer: PROC [w: Wire] RETURNS [container: REF ANY] = {
            container _ SELECT w.containingWire FROM
                NIL => w.containingCT,
                ENDCASE => w.containingWire;
            };

        defaultNameGen: NameGenerator = NEW [NameGeneratorPrivate _ [
            GenerateBlandName,
            NEW [NameCountsPrivate _ []]
            ]];

        NameCounts: TYPE = REF NameCountsPrivate;
        NameCountsPrivate: TYPE = RECORD [
            design, cellType, port, vertex: INT _ 0
            ];

        GenerateBlandName: PROC [data, subject: REF ANY] RETURNS [name: ROPE] = {
            nc: NameCounts = NARROW[data];
            name _ GenByCount[nc, subject];
            };

        TVNameGenerator: TYPE = REF TVNameGeneratorPrivate;
        TVNameGeneratorPrivate: TYPE = RECORD [
            nc: NameCounts,
            symTab: SymTab.Ref
            ];

        MakeTVNameGen: PROC [symTab: SymTab.Ref] RETURNS [ng: NameGenerator] = {
            ng _ NEW [NameGeneratorPrivate _ [
                GenerateTVName,
                NEW [TVNameGeneratorPrivate _ [
                    nc: NEW [NameCountsPrivate _ []],
                    symTab: symTab
                    ]]
                ]];
            };

        GenerateTVName: PROC [data, subject: REF ANY] RETURNS [name: ROPE] = {
            tvng: TVNameGenerator = NARROW[data];
            name _ Rope.Concat["&", GenByCount[tvng.nc, subject]];
            TRUSTED {InterpreterOps.RegisterTV[
                name: name,
                tv: AMBridge.TVForReferent[WITH subject SELECT FROM
                    d: Design => NEW [Design _ d],
                    ct: CellType => NEW [CellType _ ct],
                    p: Port => NEW [Port _ p],
                    v: Vertex => NEW [Vertex _ v],
                    ENDCASE => ERROR],
                symTab: tvng.symTab]};
            };

        GenByCount: PROC [nc: NameCounts, subject: REF ANY] RETURNS [name: ROPE] = {
            n: INT _ 0;
            WITH subject SELECT FROM
                d: Design => {n _ nc.design _ nc.design + 1; name _ "D"};
                ct: CellType => {n _ nc.cellType _ nc.cellType + 1; name _ "CT"};
                p: Port => {n _ nc.port _ nc.port + 1; name _ "P"};
                v: Vertex => {n _ nc.vertex _ nc.vertex + 1; name _ "V"};
                ENDCASE => ERROR;
            name _ name.Concat[Convert.RopeFromInt[n]];
            };

        PrintObject: PROC [to: IO.STREAM, united: BOOL, PrintIt: PROC] = {
            SS.Bp[to, united, printStep];
            SS.Begin[to];
            PrintIt[!UNWIND => SS.End[to]];
            SS.End[to];
            };

        printStep: INT _ 3;

        PrintDesign: PROC [to: IO.STREAM, design: Design, nameGen: NameGenerator] = {
            CTPrint: PROC [ra: REF ANY] = {
                ct: CellType = NARROW[ra];
                Inner: PROC = {PrintCellType[to, ct, nameGen]};
                PrintObject[to, TRUE, Inner];
                };
            IF NOT SS.IsAnSS[to] THEN to _ SS.Create[UB.NewHandle[[stream[to]], 60]];
            to.PutF["%g: Design {", [rope[Describe[design, NIL, nameGen]]]];
            design.cellTypes.Enumerate[CTPrint];
            to.PutF["}"];
            };

        PrintCellType: PROC [to: IO.STREAM, ct: CellType, nameGen: NameGenerator] = {
            Main: PROC = {
                to.PutF["%g: CellType[", [rope[Describe[ct, GetADesign[ct], nameGen]]]];
                PrintObject[to, TRUE, PortPrint];
                IF ct.asUnorganized # NIL THEN {
                    to.PutRope[", "]; PrintObject[to, TRUE, IWPrint];
                    to.PutRope[", "]; PrintObject[to, TRUE, CIPrint];
                    };
                IF ct.asArray # NIL THEN {
                    to.PutRope[", "]; PrintObject[to, TRUE, AyPrint];
                    };
                to.PutRope["]"];
                };
            PortPrint: PROC = {
                to.PutF["port: "];
                PrintPort[to, ct.port, nameGen];
                };
            IWPrint: PROC = {
                to.PutF["internal wire: "];
                PrintWire[to, ct.asUnorganized.internalWire, nameGen];
                };
            CIPrint: PROC = {
                to.PutF["contained instances: "];
                PrintInstances[to, ct.asUnorganized.containedInstances, ct.asUnorganized.mirror, nameGen];
                };
            AyPrint: PROC = {
                to.PutRope["asArray: "];
                PrintArray[to, ct, nameGen]
                };
            IF NOT SS.IsAnSS[to] THEN to _ SS.Create[UB.NewHandle[[stream[to]], 60]];
            --PrintObject[to, TRUE, Main]--Main[];
            };

        PrintPort: PROC [to: IO.STREAM, port: Port, nameGen: NameGenerator] = {
            first: BOOL _ TRUE;
            to.PutRope[Describe[port, port.parent, nameGen]];
            IF port.FirstChildPort[] = NIL THEN RETURN;
            to.PutRope["["];
            FOR subPort: Port _ port.FirstChildPort[], subPort.NextChildPort[] WHILE subPort # NIL DO
                PortPrint: PROC = {PrintPort[to, subPort, nameGen]};
                IF first THEN first _ FALSE ELSE to.PutRope[", "];
                PrintObject[to, FALSE, PortPrint];
                ENDLOOP;
            to.PutRope["]"];
            };

        PrintWire: PROC [to: IO.STREAM, wire: Wire, nameGen: NameGenerator] = {
            first: BOOL _ TRUE;
            to.PutRope[Describe[wire, WireContainer[wire], nameGen]];
            IF wire.FirstChildWire[] = NIL THEN RETURN;
            to.PutRope["["];
            FOR subWire: Wire _ wire.FirstChildWire[], subWire.NextChildWire[] WHILE subWire # NIL DO
                WirePrint: PROC = {PrintWire[to, subWire, nameGen]};
                IF first THEN first _ FALSE ELSE to.PutRope[", "];
                PrintObject[to, FALSE, WirePrint];
                ENDLOOP;
            to.PutRope["]"];
            };

        PrintInstances: PROC [to: IO.STREAM, set: Set--OF CellInstance--, mirror: CellInstance, nameGen: NameGenerator] = {
            first: BOOL _ TRUE;
            PrintIt: PROC [ra: REF ANY] = {
                ci: CellInstance = NARROW[ra];
                IPrint: PROC = {PrintInstance[to, ci, nameGen]};
                IF first THEN first _ FALSE ELSE to.PutRope[", "];
                PrintObject[to, TRUE, IPrint];
                };
            to.PutRope["["];
            set.Enumerate[PrintIt];
            PrintIt[mirror];
            to.PutRope["]"];
            };

        PrintInstance: PROC [to: IO.STREAM, ci: CellInstance, nameGen: NameGenerator] = {
            PrintConnections: PROC [v: Vertex] = {
                first: BOOL _ TRUE;
                PrintConnection: PROC [port: Port, w: Vertex] = {
                    CPrint: PROC = {
                        to.PutF["%g: ", [rope[Describe[port, port.parent, nameGen]]]];
                        WITH w SELECT FROM
                            im: Intermediary => {
                                PrintConnections[im];
                                };
                            wire: Wire => {
                                to.PutRope[Describe[wire, WireContainer[wire], nameGen]];
                                };
                            ci: CellInstance => ERROR;
                            ENDCASE => ERROR;
                        };
                    IF first THEN first _ FALSE ELSE to.PutRope[", "];
                    PrintObject[to, FALSE, CPrint];
                    };
                to.PutRope["["];
                EnumerateImmediateConnections[v, PrintConnection, [cellward: FALSE, wireward: TRUE]];
                to.PutRope["]"];
                };
            to.PutF["%g: %g", [rope[Describe[ci, ci.containingCT, nameGen]]], [rope[Describe[ci.type, GetADesign[ci.type], nameGen]]] ];
            PrintConnections[ci];
            };

        PrintArray: PROC [to: IO.STREAM, ct: CellType, nameGen: NameGenerator] = {
            a: Array = ct.asArray;
            to.PutF["{%g BY %g OF %g (joints period is %g by %g)",
                [integer[a.size[Foo]]], [integer[a.size[Bar]]],
                [rope[Describe[a.eltType, GetADesign[ct], nameGen]]],
                [integer[a.jointsPeriod[Foo]]], [integer[a.jointsPeriod[Bar]]]
                ];
            FOR d: Dim IN Dim DO
                PrintJoints: PROC = {
                    first: BOOL _ TRUE;
                    to.PutF[", joints[%g] = [", [rope[DimName[d]]]];
                    FOR 
                        FOR 
                            JPrint: PROC = {
                                to.PutF["[%g,%g]: ", [integer[
                                PrintJoint[to, ct, GetArrayJoint[a, d, [
                                };
                            IF first THEN first _ FALSE ELSE to.PutRope[", "];
                            PrintObject[to, TRUE, JPrint];
                            ENDLOOP;
                        ENDLOOP;
                    to.PutRope["]"];
                    };
                PrintObject[to, TRUE, PrintJoints];
                ENDLOOP;
            to.PutRope["}"];
            };

        PrintJoint: PROC [to: IO.STREAM, act: CellType, j: Joint, nameGen: NameGenerator] = {
            first: BOOL _ TRUE;
            PerPair: PROC [key, value: REF ANY] RETURNS [stop: BOOL _ FALSE] --HashTable.EachPairAction-- = {
                lowPort: Port = NARROW[key];
                highPort: Port = NARROW[value];
                PPrint: PROC = {
                    inc: Incompleteness = IF j.lowToIncompleteness # NIL THEN NARROW[j.lowToIncompleteness.Fetch[key].value] ELSE NIL;
                    to.PutRope[Describe[lowPort, act, nameGen]];
                    to.PutRope[""];
                    to.PutRope[Describe[highPort, act, nameGen]];
                    IF inc # NIL THEN to.PutF["(%g/%g incomplete)", [integer[inc.nIncomplete]], [integer[inc.length]]];
                    };
                IF first THEN first _ FALSE ELSE to.PutRope[", "];
                PrintObject[to, TRUE, PPrint];
                };
            to.PutRope["["];
            [] _ j.lowToHigh.Pairs[PerPair];
            to.PutRope["]"];
            };

        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--;
            };
            Escape: ERROR = CODE;

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

        notPorted: PUBLIC Porting _ NEW [ROPE _ "not ported"];
        unknownPorting: PUBLIC Porting _ NEW [ROPE _ "unknown porting"];

        GetArrayPort: PUBLIC PROC [a: Array, index: ArrayIndex, ep: Port] RETURNS [arrayPort: Port] = {
            Get: PROC [pp: PortPtr] = TRUSTED {arrayPort _ IF pp # NIL THEN pp^ ELSE NIL};
            ForArrayPort[a, index, ep, Get, FALSE]};

        SetArrayPort: PUBLIC PROC [a: Array, index: ArrayIndex, ep, ap: Port] = {
            Set: PROC [pp: PortPtr] = TRUSTED {IF pp # NIL THEN pp^ _ ap ELSE ERROR};
            wF: Where = WhereIs[index[Foo], [0, a.size[Foo]]];
            wB: Where = WhereIs[index[Bar], [0, a.size[Bar]]];
            apc: ArrayPortConnections _ NARROW[a.portConnections.Fetch[ap].value];
            ForArrayPort[a, index, ep, Set, TRUE];
            IF apc = NIL THEN {
                apc _ NEW [ArrayPortConnectionsPrivate _ ALL[ALL[NIL]]];
                FOR e: End IN End DO FOR d: Dim IN Dim DO
                    apc[e][d] _ CreateIntTable[];
                    ENDLOOP ENDLOOP;
                [] _ a.portConnections.Store[ap, apc];
                };
            FOR d: Dim IN Dim DO
                id: INT = index[d];
                wd: Where = WhereIs[id, [0, a.size[d]]];
                WITH ed: wd SELECT FROM
                    end => [] _ apc[ed.end][d].Store[index[OtherDim[d]], ep];
                    center => NULL;
                    ENDCASE => ERROR;
                ENDLOOP;
            };

        PortPtr: TYPE = LONG POINTER TO Port;

        ForArrayPort: PROC [a: Array, index: ArrayIndex, ep: Port, Consume: PROC [pp: PortPtr], mayCreate: BOOL] = TRUSTED {
            p: Porting = a.porting.Fetch[ep].value;
            dp: DetailedPorting;
            SELECT p FROM
                notPorted => {
                    IF NOT mayCreate THEN {
                        Consume[NIL];
                        RETURN}
                    ELSE {
                        xyz: NAT = (MAX[a.size[Foo]-2, 0] + MAX[a.size[Bar]-2, 0]) * 2;
                        firstSlot: INT _ 0;
                        dp _ NEW [DetailedPortingRep[xyz]];
                        dp.corners _ ALL[ALL[NIL]];
                        FOR e: End IN End DO FOR d: Dim IN Dim DO
                            dp.sideIndices[e][d] _ [FALSE, firstSlot];
                            firstSlot _ firstSlot + MAX[a.size[OtherDim[d]]-2, 0];
                            ENDLOOP ENDLOOP;
                        FOR i: INT IN [0 .. dp.length) DO dp[i] _ NIL ENDLOOP;
                        [] _ a.porting.Store[ep, dp];
                        };
                    };
                unknownPorting => ERROR;
                ENDCASE => dp _ NARROW[p];
            {
            For: PROC [si: SideIndex, offset: NAT] = TRUSTED {
                s: NAT _ si.firstSlot;
                IF NOT si.same THEN s _ s + offset;
                Consume[@dp.slots[s]]};
            wF: Where = WhereIs[index[Foo], [0, a.size[Foo]]];
            wB: Where = WhereIs[index[Bar], [0, a.size[Bar]]];
            WITH f: wF SELECT FROM
                end => WITH b: wB SELECT FROM
                    end => Consume[@dp.corners[f.end][b.end]];
                    center => For[dp.sideIndices[f.end][Bar], b.offset];
                    ENDCASE => ERROR;
                center => WITH b: wB SELECT FROM
                    end => For[dp.sideIndices[b.end][Foo], f.offset];
                    center => ERROR;
                    ENDCASE => ERROR;
                ENDCASE => ERROR;
            };
            };

        Where: TYPE = RECORD [
            variant: SELECT kind: * FROM
                end => [end: End],
                center => [offset: NAT],
                ENDCASE];

        WhereIs: PROC [i: INT, r: Range] RETURNS [w: Where] = {
            i _ r.min + ((i - r.min) MOD (r.maxPlusOne - r.min));
            SELECT TRUE FROM
                i = r.min => RETURN [[end[low]]];
                i+1 = r.maxPlusOne => RETURN [[end[high]]];
                ENDCASE => RETURN [[center[i - (r.min+1)]]];
            };

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

        EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] = {
            FOR act: CellType _ cellType.firstArray, act.asArray.nextArray WHILE act # NIL DO
                Consume[act];
                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;
            };

        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;
                    };
                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] = {
                a: Array = act.asArray;
                [] _ a.porting.Store[port, notPorted];
                };
            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 {
                apc: ArrayPortConnections = NEW [ArrayPortConnectionsPrivate];
                FOR e: End IN End DO FOR d: Dim IN Dim DO
                    apc[e][d] _ CreateIntTable[];
                    ENDLOOP ENDLOOP;
                [] _ ct.asArray.portConnections.Store[port, apc];
                };
            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]};

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

        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] = {
            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 pbn.SetMapping[name, v] THEN ERROR;
                    v => NULL;
                    ENDCASE => ERROR;
                };
            IF pbn = NIL THEN RETURN;
            Asserting.EnumerateAssertionsAbout[nameReln, v.other, PerName];
            };

        KnowVertexName: PUBLIC PROC [v: Vertex, name: ROPE] = {
            ct: CellType = v.containingCT;
            pbn: Mapper = NARROW[Asserting.FnVal[partsByNameKey, ct.otherPrivate]];
            IF pbn # NIL THEN {
                SELECT pbn.Map[name] FROM
                    v => NULL;
                    NIL => IF pbn.SetMapping[name, v] THEN ERROR;
                    ENDCASE => ERROR;
                };
            v.other _ Asserting.Assert[nameReln, LIST[name], v.other];
            };

        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 NOT pbn.SetMapping[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;
                    v.containingCT.asUnorganized.containedInstances.RemoveElt[ci];
                    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];
            };

        MakeArrayConnection: PUBLIC PROC [ct: CellType, d: Dim, lowRange: Range2, lowPort, highPort: Port] = {
            o: Dim = OtherDim[d];
            a: Array = ct.asArray;
            
            
            IF a = NIL THEN ERROR;
            IF lowRange[d].min<0 OR lowRange[d].maxPlusOne>=a.size[d] THEN ERROR;
            IF lowRange[o].min<0 OR lowRange[o].maxPlusOne>a.size[o] THEN ERROR;
            IF a.jointsPeriod[d] > a.size[d] THEN ERROR;
            FOR 
                FOR 
                    phase2: ArrayIndex = [
                    j: Joint = GetArrayJoint[a, d, phase2];
                    jir: Range2 = [
                        Foo: [
                            min: CeilDiv[MAX[lowRange[Foo].min, 
                            maxPlusOne: FloorDiv[lowRange[Foo].maxPlusOne-1 - 
                        Bar: [
                            min: CeilDiv[MAX[lowRange[Bar].min, 
                            maxPlusOne: FloorDiv[lowRange[Bar].maxPlusOne-1 - 
                    jsize: Range2 = [
                        Foo: [0, FloorDiv[a.size[Foo]-(IF d=Foo THEN 2 ELSE 1) - 
                        Bar: [0, FloorDiv[a.size[Bar]-(IF d=Bar THEN 2 ELSE 1) - 
                    complete: BOOL = jsize = jir;
                    ncji: INT = jsize[Foo].maxPlusOne * jsize[Bar].maxPlusOne;
                    FixMapping: PROC [mapTable: RefTable, from, to: Port] = {
                        SELECT mapTable.Fetch[from].value FROM
                            NIL => [] _ mapTable.Store[from, to];
                            to => NULL;
                            ENDCASE => ERROR;
                        };
                    FixIncompleteness: PROC [oldToInc: RefTable, from: Port] RETURNS [newToInc: RefTable] = {
                        inc: Incompleteness;
                        newToInc _ oldToInc;
                        IF newToInc = NIL THEN {
                            IF complete THEN RETURN;
                            newToInc _ CreateRefTable[];
                            };
                        inc _ NARROW[newToInc.Fetch[from].value];
                        IF inc = NIL THEN {
                            IF complete THEN RETURN;
                            inc _ NEW [IncompletenessPrivate[ncji]];
                            inc.nIncomplete _ ncji - RangeArea[jir];
                            FOR if: INT IN [0 .. jsize[Foo].maxPlusOne) DO
                                inf: BOOL = if IN [jir[Foo].min .. jir[Foo].maxPlusOne);
                                FOR ib: INT IN [0 .. jsize[Bar].maxPlusOne) DO
                                    cji: INT = if * jsize[Bar].maxPlusOne + ib;
                                    inc[cji] _ NOT (inf AND ib IN [jir[Bar].min .. jir[Bar].maxPlusOne));
                                    ENDLOOP;
                                ENDLOOP;
                            [] _ newToInc.Store[from, inc];
                            }
                        ELSE {
                            FOR if: INT IN [jir[Foo].min .. jir[Foo].maxPlusOne) DO
                                FOR ib: INT IN [jir[Bar].min .. jir[Bar].maxPlusOne) DO
                                    cji: INT = if * jsize[Bar].maxPlusOne + ib;
                                    IF inc[cji] THEN inc.nIncomplete _ inc.nIncomplete - 1;
                                    inc[cji] _ FALSE;
                                    ENDLOOP;
                                ENDLOOP;
                            };
                        IF inc.nIncomplete = 0 THEN [] _ newToInc.Store[from, NIL];
                        };
                    FixMapping[j.lowToHigh, lowPort, highPort];
                    FixMapping[j.highToLow, highPort, lowPort];
                    j.lowToIncompleteness _ FixIncompleteness[j.lowToIncompleteness, lowPort];
                    j.highToIncompleteness _ FixIncompleteness[j.highToIncompleteness, highPort];
                    ENDLOOP ENDLOOP;
            };

        RangeArea: PROC [r: Range2] RETURNS [area: INT] = {
            area _ (r[Foo].maxPlusOne-r[Foo].min) * (r[Bar].maxPlusOne-r[Bar].min)};

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

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

        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.