
<<LichenDataImpl.Mesa>>
    <<Last tweaked by Mike Spreitzer on October 20, 1987 6:56:23 pm PDT>>

    DIRECTORY AMBridge, Asserting, Basics, Convert, InterpreterOps, IO, LichenArrayStuff, Collections, LichenDataOps, 
    LichenDataStructure, PairCollections, LichenPrinting, List, Rope, RopeHash, StructuredStreams, SymTab, UnparserBuffer, ViewerIO;

    LichenDataImpl: CEDAR PROGRAM
        IMPORTS Asserting, IO, LichenArrayStuff, Collections, LichenDataStructure, PairCollections, LichenPrinting, List, Rope, RopeHash, 
        StructuredStreams, UnparserBuffer, ViewerIO
        EXPORTS LichenDataStructure, LichenDataOps
        =

    BEGIN OPEN LichenDataStructure, LichenArrayStuff, Colls:Collections, PairColls:PairCollections, 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;
    partsByNameKey: PUBLIC ATOM _ $LichenNameToPart;

    Escape: ERROR = CODE;

    nameStepSpace: PUBLIC Colls.Space _ NEW [Colls.SpacePrivate _ [
        Equal: StepEqual,
        Hash: StepHash,
        Compare: StepCompare,
        other: List.PutAssoc[key: $Name, val: "name steps", aList: NIL]
        ]];

    StepEqual: PROC [data: REF ANY, elt1, elt2: Colls.Value] RETURNS [BOOL] ~ {
        WITH elt1 SELECT FROM
            x: REF INT => WITH elt2 SELECT FROM
                y: REF INT => RETURN [x^ = y^];
                y: ROPE => RETURN [FALSE];
                ENDCASE => ERROR;
            x: ROPE => WITH elt2 SELECT FROM
                y: REF INT => RETURN [FALSE];
                y: ROPE => RETURN [x.Equal[y]];
                ENDCASE => ERROR;
            ENDCASE => ERROR;
        };

    StepHash: PROC [data: REF ANY, elt: Colls.Value] RETURNS [CARDINAL] ~ {
        WITH elt SELECT FROM
            x: REF INT => RETURN Colls.HashIntI[x^];
            x: ROPE => RETURN [RopeHash.FromRope[rope: x]];
            ENDCASE => ERROR;
        };

    StepCompare: PROC [data: REF ANY, elt1, elt2: Colls.Value] RETURNS [Basics.Comparison] ~ {
        WITH elt1 SELECT FROM
            x: REF INT => WITH elt2 SELECT FROM
                y: REF INT => RETURN [Colls.CompareIntI[x^, y^]];
                y: ROPE => RETURN [less];
                ENDCASE => ERROR;
            x: ROPE => WITH elt2 SELECT FROM
                y: REF INT => RETURN [greater];
                y: ROPE => RETURN [x.Compare[y]];
                ENDCASE => ERROR;
            ENDCASE => ERROR;
        };

    steppyNameSpace: PUBLIC Colls.Space _ NEW [Colls.SpacePrivate _ [
        Equal: EqualSteppyNames,
        Hash: HashSteppyName,
        Compare: CompareSteppyNames,
        other: List.PutAssoc[$Name, "steppy names", NIL],
        data: NIL]];

    EqualSteppyNames: PROC [data: REF ANY, elt1, elt2: REF ANY] RETURNS [BOOL] ~ {
        n1: SteppyName ~ NARROW[elt1];
        n2: SteppyName ~ NARROW[elt2];
        RETURN SteppyNameEqual[n1, n2]};

    SteppyNameEqual: PUBLIC PROC [n1, n2: SteppyName, clip1, clip2: SteppyName _ NIL] RETURNS [BOOL] ~ {
        WHILE n1#clip1 AND n2#clip2 DO
            WITH n1.first SELECT FROM
                x: ROPE => WITH n2.first SELECT FROM
                    y: ROPE => IF NOT x.Equal[y] THEN RETURN [FALSE];
                    y: REF INT => RETURN [FALSE];
                    ENDCASE => ERROR;
                x: REF INT => WITH n2.first SELECT FROM
                    y: ROPE => RETURN [FALSE];
                    y: REF INT => IF x^#y^ THEN RETURN [FALSE];
                    ENDCASE => ERROR;
                ENDCASE => ERROR;
            n1 _ n1.rest;
            n2 _ n2.rest;
            ENDLOOP;
        RETURN [(n1=clip1) = (n2=clip2)]};

    HashSteppyName: PROC [data: REF ANY, elt: REF ANY] RETURNS [hash: CARDINAL _ 0] ~ {
        n: SteppyName _ NARROW[elt];
        FOR n _ n, n.rest WHILE n#NIL DO
            hash _ hash + (WITH n.first SELECT FROM
                x: ROPE => RopeHash.FromRope[x],
                x: REF INT => Colls.HashIntI[x^],
                ENDCASE => ERROR);
            ENDLOOP;
        RETURN};

    CompareSteppyNames: PROC [data: REF ANY, elt1, elt2: REF ANY] RETURNS [Basics.Comparison] ~ {
        n1: SteppyName ~ NARROW[elt1];
        n2: SteppyName ~ NARROW[elt2];
        len1, len2: NATURAL;
        gend1, gend2, glob1, glob2: BOOL;
        last1, last2: ROPE;
        [len1, gend1, glob1, last1] _ Grade[n1];
        [len2, gend2, glob2, last2] _ Grade[n2];
        RETURN [SELECT TRUE FROM
            glob1<glob2 => greater,
            glob1>glob2 => less,
            gend1<gend2 => less,
            gend1>gend2 => greater,
            len1<len2 => less,
            len1>len2 => greater,
            ENDCASE => SELECT last2.Length[]-last1.Length[] FROM
                >0 => less,
                <0 => greater,
                ENDCASE => last1.Compare[last2]];
        };

    Grade: PROC [name: SteppyName] RETURNS [length: NATURAL _ 0, gend: BOOL _ TRUE, glob: BOOL _ FALSE, last: ROPE _ NIL] ~ {
    FOR name _ name, name.rest WHILE name#NIL DO
    length _ length+1;
    WITH name.first SELECT FROM
    x: ROPE => {
    xLen: INT ~ x.Length;
    last _ x;
    gend _ FALSE;
    IF x.Fetch[xLen-1]='! THEN glob _ TRUE ELSE {
    FOR i: INT IN [0 .. xLen) DO
    SELECT x.Fetch[i] FROM
    IN ['a .. 'z], IN ['A .. 'Z], IN ['0 .. '9], '_, '-, '', '~ => NULL;
    ENDCASE => {gend _ TRUE; EXIT};
    ENDLOOP;
    };
    };
    x: REF INT => NULL;
    ENDCASE => ERROR;
    ENDLOOP;
        IF length=0 THEN length _ NATURAL.LAST;
        RETURN};

    listClass: PUBLIC Colls.CollectionClass _ Colls.CreateList[vals: NIL, space: steppyNameSpace, mayDuplicate: FALSE, orderStyle: 
    value].class;

    CreateSteppyNames: PUBLIC PROC [names: LORA--actually LIST OF SteppyName-- _ NIL] RETURNS [ListData] ~ {
        set: Set ~ Colls.CreateList[vals: names, space: steppyNameSpace, mayDuplicate: FALSE, orderStyle: value];
        IF set.class#listClass THEN ERROR;
        RETURN [set.data]};

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

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

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

    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 [child: Port] RETURNS [index: INT] = {
        index _ 0;
        FOR x: Port _ NARROW[child.parent, Port].firstChild, x.next WHILE x # child DO index _ index + 1 ENDLOOP;
        RETURN};

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

    portToInternalWire: PUBLIC UWFunction ~ PairColls.FnFromProc[MapPortToInternalWire].AsUW;

    MapPortToInternalWire: PROC [data: REF ANY, v: Colls.Value] RETURNS [Colls.MaybeValue] ~ {
        port: Port ~ NARROW[v];
        RETURN [[port.wire#NIL, 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 (port.names=NIL OR port.PortNames.Size=0) AND port.wire#NIL THEN port.names _ port.wire.VertexNames.Copy.data;
                };
            ct: CellType => {
                IF ct.port # NIL THEN ERROR;
                ct.port _ port;
                port.next _ port.prev _ NIL;
                IF port.names=NIL THEN port.names _ CreateSteppyNames[];
                [] _ port.PortNames.AddElt[LIST[BeRope["PORTS"]]];
                };
            ENDCASE => ERROR;
        };

    ActualName: PROC [instanceName, portName: SteppyName] RETURNS [actualName: SteppyName] ~ {
        lastRope: ROPE _ NIL;
        FOR l: SteppyName _ portName, l.rest WHILE l#NIL DO
            WITH l.first SELECT FROM
                x: ROPE => lastRope _ x;
                x: REF INT => NULL;
                ENDCASE => ERROR;
            ENDLOOP;
        IF lastRope.Fetch[lastRope.Length-1]='! THEN RETURN [portName];
        actualName _ List.Append[instanceName, portName];
        RETURN};

    FullyAddPort: PUBLIC PROC [p: PortPrivate _ [], andReportConnectionTo: CellInstance _ NIL] RETURNS [port: Port, connection: Wire _ 
    NIL] = {
        ct: CellType = PortCCT[port _ AddPort[p]];
        portName: SteppyName ~ SteppyDescribe[port, ct.port];
        FixInstance: PROC [ci: CellInstance] = {
            instanceName: SteppyName ~ SteppyDescribe[ci, ci.containingCT];
            wireName: SteppyName ~ ActualName[instanceName, portName];
            w: Wire = CreateWire[ci.containingCT, NIL, CreateSteppyNames[LIST[wireName]]];
            AddEdge[[cellward: ci, wireward: w], port];
            IF andReportConnectionTo = ci THEN connection _ w;
            };
        FixArray: PROC [act: CellType] ~ {NoteNewEltPort[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, FALSE];
        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];
            port _ port;
            ENDLOOP;
        RETURN};

    LinkEdge: PROC [v: Vertex, e: Edge, side: GraphDirection] = {
        prev, next: Edge;
        prevSide: GraphDirection;
        SELECT side FROM --we have to choose position carefully to satisfy AI1
            cellward => {
                IF e.port.prev # NIL THEN {
                    prev _ FindImmediateEdge[v, e.port.prev, backward].e;
                    IF prev=NIL THEN ERROR--we only implement AddEdge in increasing port order--;
                    IF prev.sides[prevSide _ cellward].v#v THEN ERROR Error["Broken"];
                    }
                ELSE IF v.firstEdge=NIL OR v.firstEdge.sides[cellward].v=v THEN prev _ NIL
                ELSE {
                    FOR prev _ v.lastEdge, prev.sides[cellward].prev UNTIL prev.sides[wireward].v=v DO
                        IF prev.sides[cellward].v#v THEN ERROR Error["Broken"];
                        ENDLOOP;
                    prevSide _ wireward};
                };
            wireward => prev _ NIL;
            ENDCASE => ERROR;
        e.sides[side].next _ next _ IF prev # NIL THEN prev.sides[prevSide].next ELSE v.firstEdge;
        e.sides[side].prev _ prev;
        IF prev=NIL THEN v.firstEdge _ e ELSE prev.sides[prevSide].next _ e;
        IF next=NIL THEN v.lastEdge _ e ELSE next.sides[next.SideFor[v]].prev _ e;
        RETURN};

    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, port.PortNames.Copy.data];
            RETURN};
        immediatelyCellward: Vertex = FindVertex[NARROW[port.parent]];
        AddEdge[[cellward: immediatelyCellward, wireward: vs[wireward]], port];
        RETURN};

    RemoveEdge: PUBLIC PROC [e: Edge] = {
        e _ e;
        FOR dir: GraphDirection IN GraphDirection DO
            next: Edge ~ e.sides[dir].next;
            prev: Edge ~ e.sides[dir].prev;
            v: Vertex ~ e.sides[dir].v;
            IF next#NIL THEN next.sides[SideFor[next, v]].prev _ prev ELSE v.lastEdge _ prev;
            IF prev#NIL THEN prev.sides[SideFor[prev, v]].next _ next ELSE v.firstEdge _ next;
            ENDLOOP;
        RETURN};

    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 DeleteVertex[cellward];
        RETURN};

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

    UnlinkPorts: PUBLIC PROC [ci: CellInstance, ports: ConstSet--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;
            RETURN};
        EnumerateImmediateEdges[ci, Work !Escape => CONTINUE];
        IF i#n THEN ERROR;
        RETURN};

    Instantiate: PUBLIC PROC [type, containingCT: CellType, names: ListData _ NIL, other: Assertions _ NIL] RETURNS [ci: CellInstance] 
    = {
        IF names=NIL THEN names _ CreateSteppyNames[];
        ci _ NEW [VertexPrivate.cell _ [
            containingCT: containingCT,
            names: names,
            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.AddElt[ci];
        IndexVertexNames[ci];
        RETURN};

    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] ~ {
        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;
                RETURN};
            Consume[ci];
            EnumerateImmediateConnections[ci, PassIMs];
            RETURN};
        PassChildren: PROC [w: Wire] ~ {
            FOR w _ FirstChildWire[w], NextChildWire[w] WHILE w # NIL DO
                Consume[w];
                PassChildren[w];
                ENDLOOP;
            RETURN};
        IF u=NIL THEN ERROR;
        PassChildren[u.internalWire];
        u.containedInstances.Enumerate[PerCell];
        IF mirrorToo THEN PerCell[u.mirror];
        RETURN};

    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;
            RETURN};
        IF internal.containingCT # ct THEN ERROR;
        internal.EnumerateTransitiveConnections[See];
        IF port = NIL THEN {
            IF mayAdd THEN {
                [port, external] _ FullyAddPort[
                    [parent: ct.port, wire: internal, names: CreateSteppyNames[LIST[SteppyDescribe[internal, ct.asUnorganized.internalWire]]]],
                    ci
                    ];
                };
            }
        ELSE IF ci # NIL THEN external _ FindTransitiveConnection[ci, port];
        RETURN};

    FullyInstantiate: PUBLIC PROC [type, containingCT: CellType, names: ListData _ NIL, other: Assertions _ NIL] RETURNS [ci: 
    CellInstance] ~ {
        ci _ Instantiate[type, containingCT, names, other];
        {instanceName: SteppyName ~ SteppyDescribe[ci, ci.containingCT];
        FOR port: Port _ type.port.FirstChildPort[], port.NextChildPort[] WHILE port # NIL DO
            portName: SteppyName ~ SteppyDescribe[port, type.port];
            wireName: SteppyName ~ ActualName[instanceName, portName];
            w: Wire = CreateWire[ci.containingCT, NIL, CreateSteppyNames[LIST[wireName]]];
            AddEdge[[cellward: ci, wireward: w], port];
            ENDLOOP;
        ci _ ci;
        RETURN}};

    CreateWire: PUBLIC PROC [containingCT: CellType, containingWire: Wire _ NIL, names: ListData _ NIL, other: Assertions _ NIL, copy: 
    Wire _ NIL] RETURNS [w: Wire] = {
        IF containingWire=NIL THEN containingWire _ containingCT.asUnorganized.internalWire;
        IF names=NIL THEN names _ CreateSteppyNames[];
        w _ NEW [VertexPrivate.wire _ [
            containingCT: containingCT,
            names: names,
            other: other,
            variant: wire[
                containingWire: containingWire,
                next: NIL,
                prev: IF containingWire#NIL THEN containingWire.lastChild ELSE NIL
                ]]];
        IF w.containingWire=NIL THEN [] _ w.VertexNames.AddElt[LIST[internalWireName]];
        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];
        IndexVertexNames[w];
        RETURN};
        internalWireName: ROPE ~ "INTERNAL";

    WireCopy: PROC [from, to: Wire] = {
        IF to.VertexNames.Size[]=0 THEN to.names _ from.VertexNames.Copy.data;
        FOR child: Wire _ from.FirstChildWire[], child.NextChildWire[] WHILE child # NIL DO
            [] _ CreateWire[containingCT: to.containingCT, containingWire: to, copy: child];
            ENDLOOP;
        RETURN};

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

    IndexVertexNames: PUBLIC PROC [v: Vertex, names: Set _ Colls.nilColl] = {
        ct: CellType = v.containingCT;
        pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
        top: BOOL ~ WITH v SELECT FROM
            x: CellInstance => TRUE,
            x: Intermediary => FALSE,
            x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
            ENDCASE => ERROR;
        PerName: PROC [val: REF ANY] ~ {
            name: SteppyName ~ NARROW[val];
            SELECT pbn.Apply[name].val FROM
                Colls.noValue => IF NOT pbn.Store[[name, v]] THEN ERROR;
                v => NULL;
                ENDCASE => ERROR;
            };
        IF pbn=PairColls.nilPairColl OR NOT top THEN RETURN;
        IF names=Colls.nilColl THEN names _ v.VertexNames;
        names.Enumerate[PerName];
        RETURN};

    UnindexVertexNames: PUBLIC PROC [v: Vertex] = {
        ct: CellType = v.containingCT;
        pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
        top: BOOL ~ WITH v SELECT FROM
            x: CellInstance => TRUE,
            x: Intermediary => FALSE,
            x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
            ENDCASE => ERROR;
        PerName: PROC [val: REF ANY] ~ {
            name: SteppyName ~ NARROW[val];
            SELECT pbn.Apply[name].val FROM
                Colls.noValue => NULL;
                v => IF NOT pbn.Delete[name] THEN ERROR;
                ENDCASE => ERROR;
            };
        IF pbn=PairColls.nilPairColl OR NOT top THEN RETURN;
        v.VertexNames.Enumerate[PerName];
        RETURN};

    CreateCellType: PUBLIC PROC [design: Design, cellTypeName: ROPE, class: CellClass, internals: BOOL, otherPublic, otherPrivate: 
    Assertions _ NIL] RETURNS [ct: CellType] = {
        pbn: VarFunction = PairColls.CreateHashFn[[steppyNameSpace, Colls.refs]];
        ct _ NEW [CellTypePrivate _ [
            class: class,
            designs: Colls.CreateHashSet[],
            publicKnown: TRUE,
            privateKnown: TRUE,
            otherPublic: otherPublic,
            otherPrivate: otherPrivate
            ]];
        IF cellTypeName#NIL THEN ct.otherPublic _ Asserting.Assert1[nameReln, cellTypeName, ct.otherPublic];
        [] _ AddPort[[parent: ct]];
        IF internals THEN {
            iw: Wire;
            ct.otherPrivate _ Asserting.AssertFn1[partsByNameKey, pbn.Refify, ct.otherPrivate];
            ct.asUnorganized _ NEW [UnorganizedPrivate _ [
                containedInstances: Colls.CreateHashSet[]
                ]];
            iw _ CreateWire[ct];
            IF ct.asUnorganized.internalWire # iw THEN ERROR;
            AddMirror[ct];
            };
        [] _ design.cellTypes.AddElt[ct];
        [] _ ct.designs.AddElt[design];
        };

    CreateArray: PUBLIC PROC [design: Design, cellTypeName: ROPE, class: CellClass, eltType: CellType, size2, basePeriod: Size2, 
    otherPublic, otherPrivate: Assertions _ NIL] RETURNS [ct: CellType] = {
        a: Array ~ CreateArrayRep[eltType, size2, basePeriod];
        ct _ CreateCellType[design, cellTypeName, class, FALSE, otherPublic, otherPrivate];
        ct.asArray _ a;
        a.prevArray _ eltType.lastArray;
        IF a.prevArray # NIL THEN a.prevArray.asArray.nextArray _ ct ELSE eltType.firstArray _ ct;
        eltType.lastArray _ ct;
        eltType.useCount _ eltType.useCount + 1;
        };

    KnowVertexName: PUBLIC PROC [v: Vertex, name: SteppyName] = {
        ct: CellType = v.containingCT;
        pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
        top: BOOL ~ WITH v SELECT FROM
            x: CellInstance => TRUE,
            x: Intermediary => FALSE,
            x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
            ENDCASE => ERROR;
        IF top AND pbn#PairColls.nilPairColl THEN {
            SELECT pbn.Apply[name].val FROM
                v => RETURN;
                Colls.noValue => IF NOT pbn.Store[[name, v]] THEN ERROR;
                ENDCASE => ERROR;
            };
        IF NOT v.VertexNames.AddElt[name] THEN ERROR;
        RETURN};

    ForgetVertexName: PUBLIC PROC [v: Vertex, name: SteppyName] = {
        ct: CellType = v.containingCT;
        pbn: VarFunction = PairColls.DeRef[Asserting.FnVal[partsByNameKey, ct.otherPrivate]].AsVar;
        last: Assertions _ NIL;
        next: Assertions _ v.other;
        top: BOOL ~ WITH v SELECT FROM
            x: CellInstance => TRUE,
            x: Intermediary => FALSE,
            x: Wire => x.containingCT.asUnorganized.internalWire=x.containingWire,
            ENDCASE => ERROR;
        IF top AND pbn#PairColls.nilPairColl THEN {
            IF NOT pbn.Delete[name] THEN ERROR;
            };
        IF NOT v.VertexNames.RemoveElt[name] THEN ERROR;
        RETURN};

    DeleteVertex: PUBLIC PROC [v: Vertex] = {
        ct: CellType = v.containingCT;
        Killit: PROC [p: Port, w: Vertex, e: Edge] = {
            dir: GraphDirection ~ e.SideFor[w];
            IF dir=cellward THEN RemoveEdges[e] ELSE RemoveEdge[e];
            WITH w SELECT FROM
                ci: CellInstance => NULL;
                im: Intermediary => IF dir=wireward THEN DeleteVertex[w];
                wire: Wire => NULL;
                ENDCASE => ERROR;
            };
        UnindexVertexNames[v];
        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;
        RETURN};

    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, subPort.PortNames.Copy.data];
                    CreateMirrorBinding[subPort, subVertex];
                    }
                ENDLOOP;
            };
        v: CellInstance = NEW [VertexPrivate.cell _ [
            containingCT: lct,
            names: CreateSteppyNames[LIST[LIST[BeRope["mirror"]]]],
            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;
        };

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

    PrintOnLog: PUBLIC PROC [ra: REF ANY] ~ {
        OPEN LichenPrinting;
        DO
            ENABLE IO.Error => IF ec=StreamClosed THEN {log _ NIL; LOOP};
            IF log = NIL THEN log _ ViewerIO.CreateViewerStreams["Lichen Debugging Log"].out;
            {slog: IO.STREAM ~ SS.Create[UB.NewInittedHandle[[output: [stream[log]], margin: printWidth]]];
            WITH ra SELECT FROM
                x: Design => PrintDesign[slog, x];
                x: CellType => PrintCellType[slog, x];
                x: Port => PrintPort[slog, x];
                x: Wire => PrintWire[slog, x];
                x: CellInstance => PrintInstance[slog, x];
                ENDCASE => ERROR;
            slog.PutRope["\n"];
            slog.Close[];
            EXIT;
            }ENDLOOP;
        RETURN};

    printWidth: INT _ 69;

    Log: PUBLIC PROC [fmt: ROPE, args: LORA _ NIL] = {
        head, tail, this: LIST OF IO.Value _ NIL;
        FOR args _ args, args.rest WHILE args#NIL DO
            this _ WITH args.first SELECT FROM
                x: Design => LIST[[rope[Describe[x]]]],
                x: CellType => LIST[[rope[Describe[x]]]],
                x: Vertex => LIST[[rope[Describe[x]]]],
                x: Port => LIST[[rope[Describe[x]]]],
                x: PortList => LIST[[rope[FmtPortList[x]]]],
                x: ROPE => LIST[[rope[x]]],
                ENDCASE => LIST[[refAny[args.first]]];
            IF tail=NIL THEN head _ this ELSE tail.rest _ this;
            tail _ this;
            ENDLOOP;
        DO
            ENABLE IO.Error => IF ec=StreamClosed THEN {log _ NIL; LOOP};
            IF log = NIL THEN log _ ViewerIO.CreateViewerStreams["Lichen Debugging Log"].out;
            log.PutFL[fmt, head];
            EXIT;
            ENDLOOP;
        RETURN};
        log: IO.STREAM _ NIL;

    FmtPortList: PROC [pl: PortList] RETURNS [asRope: ROPE] ~ {
        asRope _ NIL;
        FOR pl _ pl, pl.rest WHILE pl#NIL DO
            IF asRope#NIL THEN asRope _ asRope.Concat[", "];
            asRope _ asRope.Concat[Describe[pl.first]];
            ENDLOOP;
        asRope _ Rope.Cat["{", asRope, "}"];
        RETURN};

    NewInt: PUBLIC PROC [i: INT] RETURNS [REF INT] ~ {
        IF i IN [0 .. 64] THEN RETURN [intRefs[i]];
        RETURN [NEW [INT _ i]]};

    IntRefArray: TYPE ~ ARRAY [0 .. 64] OF REF INT;
    intRefs: REF IntRefArray ~ NEW [IntRefArray _ ALL[NIL]];

    Start: PROC ~ {
        FOR i: INT IN [0 .. 64] DO intRefs[i] _ NEW [INT _ i] ENDLOOP;
        RETURN};

    Start[];

    END.