
<<LichenDataImpl.Mesa>>
    <<Last tweaked by Mike Spreitzer on February 2, 1988 1:40:55 pm PST>>

    DIRECTORY AbSets, AMBridge, Asserting, Basics, BiRels, Convert, InterpreterOps, IntStuff, IO, LichenArrayStuff, LichenDataOps, 
    LichenDataStructure, LichenPrinting, List, Rope, RopeHash, SetBasics, StructuredStreams, SymTab, UnparserBuffer, ViewerIO;

    LichenDataImpl: CEDAR PROGRAM
        IMPORTS AbSets, Asserting, Basics, BiRels, IntStuff, IO, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenPrinting, 
        List, Rope, RopeHash, SetBasics, StructuredStreams, UnparserBuffer, ViewerIO
        EXPORTS LichenDataStructure, LichenDataOps
        =

    BEGIN OPEN LichenDataOps, LichenDataStructure, LichenArrayStuff, Sets:AbSets, 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;

    CopyTil: PUBLIC PROC [old: TList] RETURNS [new: TList _ []] ~ {
        FOR cur: LORA _ old.head, cur.rest WHILE cur#old.tail DO
            this: LORA ~ LIST[cur.first];
            IF new.tail=NIL THEN new.head _ this ELSE new.tail.rest _ this;
            new.tail _ this;
            ENDLOOP;
        RETURN};

    nameStepSpace: PUBLIC SetBasics.Space _ NEW [SetBasics.SpacePrivate _ [
        Contains: StepContains,
        Equal: StepEqual,
        Hash: StepHash,
        Compare: StepCompare,
        name: "name steps"
        ]];

    StepContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [WITH v.ra SELECT FROM
            y: ROPE => TRUE,
            y: REF INT => TRUE,
            ENDCASE => FALSE]};

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

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

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

    steppyNameSpace: PUBLIC SetBasics.Space _ NEW [SetBasics.SpacePrivate _ [
        Contains: SteppyNamesContains,
        Equal: EqualSteppyNames,
        Hash: HashSteppyName,
        Compare: CompareSteppyNames,
        name: "steppy names"
        ]];

    SteppyNamesContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [WITH v.ra SELECT FROM
            x: NameStepList => TRUE,
            ENDCASE => FALSE]};

    EqualSteppyNames: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
        n1: SteppyName ~ VSn[v1];
        n2: SteppyName ~ VSn[v2];
        RETURN SteppyNameEqual[n1, n2]};

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

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

    CompareSteppyNames: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: Basics.Comparison] ~ {
        n1: SteppyName ~ VSn[v1];
        n2: SteppyName ~ VSn[v2];
        IF (c _ SteppyNameGradeCompare[n1.grade, n2.grade])#equal THEN RETURN;
        c _ SteppyNamePartsCompare[n1.steps, n2.steps];
        RETURN};

    SteppyNameGradeCompare: PUBLIC PROC [g1, g2: SteppyNameGrade] RETURNS [Basics.Comparison] ~ {
        IF g1 = g2 THEN RETURN [equal];
        RETURN [SELECT TRUE FROM
            g1.global<g2.global => greater,
            g1.global>g2.global => less,
            g1.gend<g2.gend => less,
            g1.gend>g2.gend => greater,
            g1.nonsubs<g2.nonsubs => less,
            g1.nonsubs>g2.nonsubs => greater,
            g1.subs<g2.subs => less,
            g1.subs>g2.subs => greater,
            ENDCASE => ERROR--they were equal!--];
        };

    SteppyNamePartsCompare: PUBLIC PROC [l1, l2: NameStepList] RETURNS [c: Basics.Comparison] ~ {
        WHILE l1#l2 DO
            WITH l1.first SELECT FROM
                x1: REF INT => WITH l2.first SELECT FROM
                    x2: REF INT => IF (c _ Basics.CompareInt[x1^, x2^]) # equal THEN RETURN;
                    x2: ROPE => RETURN [greater];
                    ENDCASE => ERROR;
                x1: ROPE => WITH l2.first SELECT FROM
                    x2: ROPE => IF (c _ x1.Compare[x2]) # equal THEN RETURN;
                    x2: REF INT => RETURN [less];
                    ENDCASE => ERROR;
                ENDCASE => ERROR;
            l1 _ l1.rest;
            l2 _ l2.rest;
            ENDLOOP;
        RETURN [equal]};

    SNCat: PUBLIC PROC [a, b: SteppyName] RETURNS [SteppyName] ~ {
        IF b=noName THEN RETURN [a];
        IF a=noName THEN RETURN [b];
        IF b.grade.nonsubs>0 THEN RETURN [[
            steps: List.Append[a.steps, b.steps],
            grade: [
                global: b.grade.global,
                nonsubs: a.grade.nonsubs + b.grade.nonsubs,
                gend: b.grade.gend,
                subs: a.grade.subs + b.grade.subs]
            ]];
        RETURN [[
            steps: List.Append[a.steps, b.steps],
            grade: [
                global: a.grade.global,
                nonsubs: a.grade.nonsubs,
                gend: a.grade.gend,
                subs: a.grade.subs + b.grade.subs]
            ]]};

    SNPrepend: PUBLIC PROC [ns: NameStep, sn: SteppyName] RETURNS [SteppyName] ~ {
        ans: SteppyName _ [steps: CONS[ns, sn.steps], grade: sn.grade];
        WITH ns SELECT FROM
            x: ROPE => IF (ans.grade.nonsubs _ ans.grade.nonsubs+1) = 1 THEN [ans.grade.global, ans.grade.gend] _ Analast[x];
            x: REF INT => ans.grade.subs _ ans.grade.subs+1;
            ENDCASE => ERROR;
        RETURN [ans]};

    SNAppend: PUBLIC PROC [sn: SteppyName, ns: NameStep] RETURNS [SteppyName] ~ {
        ans: SteppyName _ [steps: List.Append[sn.steps, LIST[ns]], grade: sn.grade];
        WITH ns SELECT FROM
            x: ROPE => {
                ans.grade.nonsubs _ ans.grade.nonsubs+1;
                [ans.grade.global, ans.grade.gend] _ Analast[x]};
            x: REF INT => ans.grade.subs _ ans.grade.subs+1;
            ENDCASE => ERROR;
        RETURN [ans]};

    LSn: PUBLIC PROC [l: NameStepList] RETURNS [SteppyName]
        ~ {RETURN [[l, Grade[l]]]};

    Grade: PROC [steps: NameStepList] RETURNS [grade: SteppyNameGrade _ [FALSE, 0, FALSE, 0]] ~ {
        last: ROPE _ NIL;
        FOR steps _ steps, steps.rest WHILE steps#NIL DO
            WITH steps.first SELECT FROM
                x: ROPE => {grade.nonsubs _ grade.nonsubs+1; last _ x};
                x: REF INT => grade.subs _ grade.subs+1;
                ENDCASE => ERROR;
            ENDLOOP;
        IF last#NIL THEN [grade.global, grade.gend] _ Analast[last];
        RETURN};

    Analast: PROC [last: ROPE] RETURNS [global, gend: BOOL _ FALSE] ~ {
        xLen: INT ~ last.Length;
        IF NOT (global _ last.InlineFetch[xLen-1]='!) THEN {
            FOR i: INT DECREASING IN [0 .. xLen) DO
                SELECT last.InlineFetch[i] FROM
                    '#, '& => {gend _ TRUE; EXIT};
                    ENDCASE => NULL;
                ENDLOOP;
            };
        RETURN};

    listClass: PUBLIC Sets.SetClass _ Sets.CreateList[vals: NIL, space: steppyNameSpace, order: fwd].class;

    CreateSteppyNames: PUBLIC PROC [names: SteppyNameList _ NIL] RETURNS [ListData] ~ {
        set: Set ~ Sets.CreateList[vals: NIL, space: steppyNameSpace, order: fwd];
        IF set.class#listClass THEN ERROR;
        FOR names _ names, names.rest WHILE names#NIL DO [] _ set.AddElt[SnV[names.first]] ENDLOOP;
        RETURN [[set.data.VA]]};

    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 ~ BiRels.FnFromProc[MapPortToInternalWire].AsUW;

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

    ActualName: PROC [instanceName, portName: SteppyName] RETURNS [actualName: SteppyName] ~ {
        IF portName.grade.global THEN RETURN [portName];
        actualName _ SNCat[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 _ noName;
        FixInstance: PROC [ci: CellInstance] = {
            names: ListData _ noListData;
            IF ci.containingCT.inheritNames THEN {
                IF portName=noName THEN portName _ SteppyDescribe[port, ct.port];
                names _ CreateSteppyNames[LIST[ActualName[SteppyDescribe[ci, ci.containingCT], portName]]]};
            {w: Wire = CreateWire[ci.containingCT, NIL, names];
            AddEdge[[cellward: ci, wireward: w], port];
            IF andReportConnectionTo = ci THEN connection _ w;
            RETURN}};
        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];
        RETURN};

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

    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;
            {ccct: CellType ~ cellward.containingCT;
            v _ CreateIntermediary[cellward, wireward, ccct, port, [IF ccct.inheritNames THEN port.PortNames.Copy.data.VA ELSE NIL]];
            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[].EN;
        i: NATURAL _ 0;
        Work: PROC [port: Port, v: Vertex, e: Edge] ~ {
            IF port=NIL THEN ERROR;
            IF ports.HasMemA[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 _ noListData, 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.AddA[ci];
        IndexVertexNames[ci];
        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[IF ct.inheritNames THEN LIST[SteppyDescribe[internal, 
                    ct.asUnorganized.internalWire]] ELSE NIL]],
                    ci
                    ];
                };
            }
        ELSE IF ci # NIL THEN external _ NARROW[FindCellConnection[ci, port]];
        RETURN};

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

    CreateWire: PUBLIC PROC [containingCT: CellType, containingWire: Wire _ NIL, names: ListData _ noListData, 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.AddA[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.Empty THEN to.names _ [from.VertexNames.Copy.data.VA];
        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 _ 
    noListData, 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};

    CreateCellType: PUBLIC PROC [design: Design, cellTypeName: ROPE, class: CellClass, inheritNames, internals: BOOL, otherPublic, 
    otherPrivate: Assertions _ NIL] RETURNS [ct: CellType] = {
        pbn: VarFunction = BiRels.CreateHashFn[[steppyNameSpace, SetBasics.refs]];
        ct _ NEW [CellTypePrivate _ [
            class: class,
            designs: Sets.CreateHashSet[],
            inheritNames: inheritNames,
            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: Sets.CreateHashSet[]
                ]];
            iw _ CreateWire[ct];
            IF ct.asUnorganized.internalWire # iw THEN ERROR;
            AddMirror[ct];
            };
        [] _ design.cellTypes.AddA[ct];
        [] _ ct.designs.AddA[design];
        RETURN};

    CreateArray: PUBLIC PROC [design: Design, cellTypeName: ROPE, class: CellClass, eltType: CellType, size2, basePeriod: Size2, 
    inheritNames: BOOL, otherPublic, otherPrivate: Assertions _ NIL] RETURNS [ct: CellType] = {
        a: Array ~ CreateArrayRep[eltType, size2, basePeriod];
        ct _ CreateCellType[design, cellTypeName, class, inheritNames, 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;
        };

    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.RemA[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, [IF lct.inheritNames THEN subPort.PortNames.Copy.data.VA ELSE 
                    NIL]];
                    CreateMirrorBinding[subPort, subVertex];
                    }
                ENDLOOP;
            };
        v: CellInstance = NEW [VertexPrivate.cell _ [
            containingCT: lct,
            names: CreateSteppyNames[LIST[LSn[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]]],
                x: StatEdge => LIST[[rope[FmtStatEdge[x]]]],
                x: REF Time => LIST[[time[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.