
    <<TilingClassImpl.mesa>>
        <<Copyright © 1986 by Xerox Corporation.  All rights reversed.>>
        <<Created by Bertrand Serlet on September 19, 1986 1:48:15 pm PDT>>
        <<Bertrand Serlet November 9, 1986 0:43:55 am PST>>
        <<Barth, October 16, 1986 6:39:20 pm PDT>>
    <<>>
    DIRECTORY CD, CDInstances, CDLayers, Core, CoreClasses, CoreCreate, CoreOps, CoreProperties, CoreGeometry, GList, HashTable, PW, 
    PWCore, Sisyph, TilingClass;

    TilingClassImpl: CEDAR PROGRAM
        IMPORTS CD, CDInstances, CDLayers, CoreClasses, CoreCreate, CoreOps, CoreProperties, CoreGeometry, GList, HashTable, PW, PWCore, 
        Sisyph
        EXPORTS TilingClass
        ~ BEGIN OPEN TilingClass;
<<Utilities>>
PubActs: TYPE = REF PubActsRec;
PubActsRec: TYPE = RECORD [pubActs: SEQUENCE size: NAT OF RECORD [pub, act: Wire]];

PutTilePubActs: PROC [tile: Tile, pubs, acts: Wires] = {
size: NAT _ GList.Length[pubs];
seq: PubActs _ NEW [PubActsRec[size]];
IF size#GList.Length[acts] THEN ERROR;
FOR i: NAT IN [0 .. size) DO 
seq[i] _ [pub: pubs.first, act: acts.first]; 
pubs _ pubs.rest; acts _ acts.rest;
ENDLOOP;
tile.properties _ CoreProperties.PutProp[tile.properties, $TilingClassPubActs, seq];
};

GetTilePubActs: PROC [tile: Tile] RETURNS [seq: PubActs] = {
seq _ NARROW [CoreProperties.GetProp[tile.properties, $TilingClassPubActs]];
};

PutTileInstance: PROC [tile: Tile, instance: CoreClasses.CellInstance] = {
tile.properties _ CoreProperties.PutProp[tile.properties, $TilingClassInstance, instance];
};

GetTileInstance: PROC [tile: Tile] RETURNS [instance: CoreClasses.CellInstance] = {
RETURN [NARROW [CoreProperties.GetProp[tile.properties, $TilingClassInstance]]];
};

Replace: PROC [fused: HashTable.Table, old: Wire] RETURNS [new: Wire] = {
new _ RootWire[fused, old];
FOR i: NAT IN [0 .. old.size) DO new[i] _ Replace[fused, old[i]] ENDLOOP;
};

RootWire: PROC [fused: HashTable.Table, wire: Wire] RETURNS [root: Wire] = {
root _ NARROW [HashTable.Fetch[fused, wire].value];
IF root=NIL THEN RETURN [wire];
IF root=wire THEN ERROR;
root _ RootWire[fused, root];
[] _ HashTable.Replace[fused, wire, root];
};

    Fuse: PROC [fused: HashTable.Table, wire1, wire2: Wire] = {
    root1: Wire = RootWire[fused, wire1];
    root2: Wire = RootWire[fused, wire2];
    IF root1=root2 THEN RETURN;
    IF root1.size#root2.size THEN ERROR;
    [] _ HashTable.Store[fused, root1, root2];
    FOR i: NAT IN [0 .. root1.size) DO Fuse[fused, root1[i], root2[i]] ENDLOOP;
    };

    CreateBindingTable: PUBLIC PROC [wire1, wire2: Wire] RETURNS [table: HashTable.Table] = {
        AddInTable: CoreOps.EachWirePairProc = {[] _ HashTable.Store[table, actualWire, publicWire]};
        table _ HashTable.Create[wire1.size];
        [] _ CoreOps.VisitBinding[wire1, wire2, AddInTable];
        };

    WirePair: TYPE = RECORD [wire1, wire2: Wire];

    PublicPairsToWirePairs: PROC [ct1, ct2: CellType, publicPairs: LIST OF PublicPair] RETURNS [wirePairs: LIST OF WirePair _ NIL] = {
        WHILE publicPairs#NIL DO
            pub1: Wire = CoreCreate.FindWire[ct1.public, publicPairs.first.public1];
            pub2: Wire = CoreCreate.FindWire[ct2.public, publicPairs.first.public2];
            IF pub1=NIL OR pub2=NIL THEN ERROR; -- wrong NeighborProc
            wirePairs _ CONS [[pub1, pub2], wirePairs];
            publicPairs _ publicPairs.rest;
            ENDLOOP;
        };

    cacheX: HashTable.Table _ HashTable.Create[2];
        <<Caches [ct1 -> [ct2 -> wirePairs]]>>
    cacheY: HashTable.Table _ HashTable.Create[2];
        <<Caches [ct1 -> [ct2 -> wirePairs]]>>

    FuseNeighbors: PROC [cellType: CellType, neighbor: NeighborProc, tile1, tile2: Tile, fused: HashTable.Table, cache: 
    HashTable.Table] = {
        ct1: CellType = tile1.type;
        ct2: CellType = tile2.type;
        wirePairs: LIST OF WirePair _ NIL;
        subCache: HashTable.Table _ NARROW [HashTable.Fetch[cache, ct1].value];
        value: REF _ NIL;
        found: BOOL _ FALSE;
        IF subCache#NIL THEN [found, value] _ HashTable.Fetch[subCache, ct2];
        IF found THEN wirePairs _ NARROW [value] ELSE {
            wirePairs _ PublicPairsToWirePairs[ct1, ct2, neighbor[cellType, ct1, ct2]];
            IF subCache=NIL THEN subCache _ HashTable.Create[2];
            [] _ HashTable.Store[subCache, ct2, wirePairs];
            [] _ HashTable.Store[cache, ct1, subCache];
            };
        FOR list: LIST OF WirePair _ wirePairs, list.rest WHILE list#NIL DO
            Fuse[fused, CoreClasses.CorrespondingActual[GetTileInstance[tile1], list.first.wire1], 
            CoreClasses.CorrespondingActual[GetTileInstance[tile2], list.first.wire2]];
            ENDLOOP;
        };

    CreateActual: PROC [subPublicToActual: HashTable.Table, public: Wire] RETURNS [actual: Wire] = {
        actual _ NARROW [HashTable.Fetch[subPublicToActual, public].value];
        IF actual#NIL THEN RETURN;
        actual _ CoreOps.CreateWires[size: public.size];
        [] _ HashTable.Store[subPublicToActual, public, actual];
        FOR i: NAT IN [0 .. public.size) DO
            actual[i] _ CreateActual[subPublicToActual, public[i]];
            ENDLOOP;
        };

    CreateInstance: PROC [public: Wire, tile: Tile] RETURNS [instance: CoreClasses.CellInstance]= {
        subPublicToActual: HashTable.Table = HashTable.Create[];
        actual: Wire = CoreOps.CreateWires[size: tile.type.public.size];
        <<make a simpler renaming table [public of tile -> public of me.public]>>
        FOR list: LIST OF PA _ tile.renaming, list.rest WHILE list#NIL DO
            pub: Wire = CoreCreate.FindWire[tile.type.public, list.first.public];
            act: Wire = CoreCreate.FindWire[public, list.first.actual];
            IF pub=NIL OR act=NIL THEN ERROR; -- bad renaming list
            [] _ HashTable.Store[subPublicToActual, pub, act];
            ENDLOOP;
        FOR i: NAT IN [0 .. tile.type.public.size) DO
            actual[i] _ CreateActual[subPublicToActual, tile.type.public[i]];
            ENDLOOP;
        instance _ CoreClasses.CreateInstance[actual, tile.type];
        };
<<Tiling >>
    TilingData: TYPE = REF TilingDataRec;
    TilingDataRec: TYPE = RECORD [
        tileArray: TileArray, 
        neighborX, neighborY: NeighborProc
        ];

    tilingClass: PUBLIC Core.CellClass _ NEW [Core.CellClassRec _ [name: "2DTiling", recast: RecastTiling, layersProps: FALSE, 
    properties: CoreProperties.Props[[$Layout, $Recast]]]];

    CreateTiling: PUBLIC PROC [public: Wire, tileArray: TileArray, neighborX, neighborY: NeighborProc, name: ROPE _ NIL, props: 
    Properties _ NIL] RETURNS [tiling: CellType] = {
        tiling _ CoreOps.CreateCellType[
            class: tilingClass, 
            public: public, 
            data: NEW [TilingDataRec _ [tileArray: tileArray, neighborX: neighborX, neighborY: neighborY]], 
            name: name, props: props
            ];
        };

    RecastTiling: Core.RecastProc = {
        tilingData: TilingData = NARROW [me.data];
        public: Wire = CoreOps.CopyWire[me.public];
        fused: HashTable.Table = CreateBindingTable[me.public, public]; -- keys are fused to values
        tiles: TileArray = tilingData.tileArray;
        sizeX: NAT = tiles[0].size;
        sizeY: NAT = tiles.size;
        internalsOnly: Wires _ NIL;
        instances: LIST OF CoreClasses.CellInstance _ NIL;
        <<Create instances (even with not the right wires yet)>>
        FOR i: NAT IN [0 .. sizeY) DO
            IF tiles[i].size#sizeX THEN ERROR;
            FOR j: NAT IN [0 .. sizeX) DO 
                tile: Tile = tiles[i][j];
                instance: CoreClasses.CellInstance _ CreateInstance[me.public, tile];
                PutTileInstance[tile, instance];
                IF tile.flatten THEN {
                    rct: CoreClasses.RecordCellType = NARROW [tile.type.data];
                    publicToActual: HashTable.Table = CreateBindingTable[instance.type.public, instance.actual];
                    FOR ii: NAT IN [0 .. rct.size) DO
                        actual: Wire = CoreOps.CreateWires[size: rct[ii].type.public.size];
                        FOR k: NAT IN [0 .. rct[ii].type.public.size) DO
                            actual[k] _ NARROW [HashTable.Fetch[publicToActual, rct[ii].actual[k]].value];
                            ENDLOOP;
                        instances _ CONS [CoreClasses.CreateInstance[actual, rct[ii].type], instances];
                        ENDLOOP;
                    } ELSE instances _ CONS [instance, instances];
                ENDLOOP;
            ENDLOOP;
        <<Find who to fuse, first progressing in rows>>
        FOR i: NAT IN [0 .. sizeY) DO
            FOR j: NAT IN [1 .. sizeX) DO
                FuseNeighbors[me, tilingData.neighborX, tiles[i][j-1], tiles[i][j], fused, cacheX];
                ENDLOOP;
            ENDLOOP;
        <<Find who to fuse, progressing in columns>>
        FOR j: NAT IN [0 .. sizeX) DO
            FOR i: NAT IN [1 .. sizeY) DO
                FuseNeighbors[me, tilingData.neighborY, tiles[i-1][j], tiles[i][j], fused, cacheY];
                ENDLOOP;
            ENDLOOP;
    <<Replace the public>>
        FOR i: NAT IN [0 .. public.size) DO
            public[i] _ Replace[fused, public[i]];
            ENDLOOP;
    <<Replace in instances the actuals>>
        FOR list: LIST OF CoreClasses.CellInstance _ instances, list.rest WHILE list#NIL DO
            instance: CoreClasses.CellInstance = list.first;
            instance.actual _ Replace[fused, instance.actual];
            IF NOT CoreOps.Conform[instance.actual, instance.type.public] THEN ERROR; -- the tiles shorts parts of the public together
        <<Compute the internal only wires>>
            FOR k: NAT IN [0 .. instance.actual.size) DO
                wire: Wire = instance.actual[k];
            IF NOT CoreOps.RecursiveMember[public, wire] AND NOT CoreOps.Member[internalsOnly, wire] THEN internalsOnly _ CONS [wire, 
            internalsOnly];
                ENDLOOP;
            ENDLOOP;
    IF NOT CoreOps.Conform[public, me.public] THEN ERROR; -- the tiles shorts parts of the public together
    <<-- Preparing the decoration by storing on each tile the list of publics which decorations should be offset and added and the list 
    of corresponding actuals [part of public].>>
        FOR i: NAT IN [0 .. sizeY) DO
            FOR j: NAT IN [0 .. sizeX) DO
                IF i=0 OR i=sizeY-1 OR j=0 OR j=sizeX-1 THEN {
                    tile: Tile = tiles[i][j];
                    pubs, acts: Wires _ NIL;
                    DecorateIfOutside: PROC [pub: Wire] = {
                        act: Wire = RootWire[fused, CoreClasses.CorrespondingActual[GetTileInstance[tile], pub]];
                        IF act=NIL THEN ERROR;
                        IF NOT CoreOps.RecursiveMember[public, act] THEN RETURN;
                        IF CoreOps.Member[pubs, pub] THEN RETURN; -- already seen
                    pubs _ CONS [pub, pubs];
                    acts _ CONS [act, acts];
                        };
                    CoreOps.VisitRootAtomics[tile.type.public, DecorateIfOutside];
                PutTilePubActs[tile, pubs, acts];
                    };
                ENDLOOP;
            ENDLOOP;
    <<Cleanup>>
        FOR i: NAT DECREASING IN [0 .. sizeY) DO
            FOR j: NAT DECREASING IN [0 .. sizeX) DO
                PutTileInstance[tiles[i][j], NIL];
                ENDLOOP;
            ENDLOOP;
    new _ CoreClasses.CreateRecordCell[
    public: public, 
    internal: CoreOps.UnionWire[public, CoreOps.CreateWire[internalsOnly]], 
    instances: instances, 
    name: CoreOps.GetCellTypeName[me],
    props: CoreProperties.Props[[$Layout, $Tiling], [$Tiles, tiles]]
    ];
    };

LayoutTiling: PWCore.LayoutProc = {
SmashPins: PROC [wire: Wire] = {CoreGeometry.PutPins[PWCore.extractMode.decoration, wire, NIL]};
    Layout: PROC [i, j: NAT] RETURNS [CD.Object] = {RETURN [PWCore.Layout[tiles[i][j].type]]};
    tiles: TileArray = NARROW [CoreProperties.GetCellTypeProp[cellType, $Tiles]];
    sizeX: NAT = tiles[0].size;
    sizeY: NAT = tiles.size;
    offset: CD.Position _ [0, 0];
    ir: CD.Rect;
    <<Generating the layout, now>>
    obj _ PW.CreateEmptyCell[];
    <<We check that sizes of the IR verify the assumptions>>
    FOR i: NAT IN [0 .. sizeY) DO
        height: INT = CD.InterestSize[Layout[i, 0]].y;
        FOR j: NAT IN [1 .. sizeX) DO
            IF height#CD.InterestSize[Layout[i, j]].y THEN ERROR; -- assumption not verified
            ENDLOOP;
        ENDLOOP;
    FOR j: NAT IN [0 .. sizeX) DO
        width: INT = CD.InterestSize[Layout[0, j]].x;
        FOR i: NAT IN [1 .. sizeY) DO
            IF width#CD.InterestSize[Layout[i, j]].x THEN ERROR; -- assumption not verified
            ENDLOOP;
        ENDLOOP;
<<We tile>>
    FOR i: NAT IN [0 .. sizeY) DO
        offset.x _ 0;
        FOR j: NAT IN [0 .. sizeX) DO
            [] _ PW.IncludeInCell[obj, Layout[i, j], offset];
            offset.x _ offset.x + CD.InterestSize[Layout[i, j]].x;
            ENDLOOP;
        offset.y _ offset.y + CD.InterestSize[Layout[i, 0]].y;
        ENDLOOP;
    PW.SetInterestRect[obj, offset];
    PW.RepositionCell[obj];
    ir _ CD.InterestRect[obj];
<<Getting rid of copied properties (one day not necessary)>>
    CoreOps.VisitRootAtomics[cellType.public, SmashPins];
<<Decorating cellType (we do a second pass because of reposition!)>>
    offset.y _ ir.y1;
    FOR i: NAT IN [0 .. sizeY) DO
        offset.x _ ir.x1;
        FOR j: NAT IN [0 .. sizeX) DO
            tile: Tile = tiles[i][j];
        seq: PubActs = GetTilePubActs[tile];
            origin: CD.Rect = CD.InterestRect[Layout[i, j]];
            transf: CD.Instance = CDInstances.NewInst[CDCells.CreateEmptyCell[], [offset.x-origin.x1, offset.y-origin.y1]];
            IF seq#NIL THEN FOR i: NAT IN [0 .. seq.size) DO
                pins: CoreGeometry.Instances _ CoreGeometry.GetPins[PWCore.extractMode.decoration, seq[i].act];
                FOR list: CoreGeometry.Instances _ CoreGeometry.GetPins[PWCore.extractMode.decoration, seq[i].pub], list.rest WHILE list#NIL DO
                    IF CoreGeometry.TransfedNotAtEdge[transf, ir, list.first] THEN LOOP;
                    pins _ CONS [CoreGeometry.Transform[transf, list.first], pins];
                    ENDLOOP;
                CoreGeometry.PutPins[PWCore.extractMode.decoration, seq[i].act, pins];
                ENDLOOP;
            offset.x _ offset.x + CD.InterestSize[Layout[i, j]].x;
            ENDLOOP;
        offset.y _ offset.y + CD.InterestSize[Layout[i, 0]].y;
        ENDLOOP;
CoreGeometry.PutIR[PWCore.extractMode.decoration, cellType, ir];
    };
<<Predefined NeighborProcs >>
    WMML: TYPE = RECORD [wire: Wire, min, max: INT, layer: CD.Layer];
    ListSide: PROC [ct: CellType, side: CoreGeometry.Side, decoration: CoreGeometry.Decoration] RETURNS [list: LIST OF WMML _ NIL] = {
        EachSortedPin: CoreGeometry.EachSortedPinProc = {
            list _ CONS [[wire, min, max, layer], list];
            };
        [] _ CoreGeometry.EnumerateSortedSides[decoration, ct, side, EachSortedPin];
        };

    AddPublicPairs: PROC [wire1, wire2: Wire, old: LIST OF PublicPair] RETURNS [new: LIST OF PublicPair] = {
        FOR list: LIST OF PublicPair _ old, list.rest WHILE list#NIL DO
            IF list.first=[wire1, wire2] THEN RETURN [old];
            ENDLOOP;
        RETURN [CONS [[wire1, wire2], old]];
        };

    IntersectLists: PROC [list1, list2: LIST OF WMML, usedLayers: LIST OF CD.Layer] RETURNS [publicPairs: LIST OF PublicPair _ NIL] = {
        FOR layers: LIST OF CD.Layer _ usedLayers, layers.rest WHILE layers#NIL DO
        layer: CD.Layer _ CDLayers.AbstractToPaint[layers.first];
        FOR l1: LIST OF WMML _ list1, l1.rest WHILE l1#NIL DO
        IF l1.first.layer#layer THEN LOOP;
        FOR l2: LIST OF WMML _ list2, l2.rest WHILE l2#NIL DO
        IF l2.first.layer#layer THEN LOOP;
        IF l2.first.min>l1.first.max OR l1.first.min>l2.first.max THEN LOOP;
        publicPairs _ AddPublicPairs[l1.first.wire, l2.first.wire, publicPairs];
        ENDLOOP;
        ENDLOOP;
        ENDLOOP;
        };

    LayoutNeighborX: PUBLIC NeighborProc = {
    [] _ PWCore.InterestRect[ct1]; -- to make sure the cellType is decorated
    [] _ PWCore.InterestRect[ct2]; -- to make sure the cellType is decorated
    publicPairs _ IntersectLists[
    ListSide[ct1, right, PWCore.extractMode.decoration], 
    ListSide[ct2, left, PWCore.extractMode.decoration], 
    CD.FetchTechnology[$cmosB].usedLayers
    ];
        };
    LayoutNeighborY: PUBLIC NeighborProc = {
    [] _ PWCore.InterestRect[ct1]; -- to make sure the cellType is decorated
    [] _ PWCore.InterestRect[ct2]; -- to make sure the cellType is decorated
    publicPairs _ IntersectLists[
    ListSide[ct1, top, PWCore.extractMode.decoration], 
    ListSide[ct2, bottom, PWCore.extractMode.decoration], 
    CD.FetchTechnology[$cmosB].usedLayers
    ];
        };
    SchematicsNeighborX: PUBLIC NeighborProc ={
    publicPairs _ IntersectLists[
    ListSide[ct1, right, Sisyph.mode.decoration], 
    ListSide[ct2, left, Sisyph.mode.decoration], 
    LIST [CD.commentLayer]
    ];
    };

    SchematicsNeighborY: PUBLIC NeighborProc ={
    publicPairs _ IntersectLists[
    ListSide[ct1, top, Sisyph.mode.decoration], 
    ListSide[ct2, bottom, Sisyph.mode.decoration], 
    LIST [CD.commentLayer]
    ];
    };
<<Initialization>>
[] _ PWCore.RegisterLayoutAtom[$Tiling, LayoutTiling];

    END.