
    <<InternalRCMapBuilderImpl.mesa>>
        <<Copyright © 1984, 1985 by Xerox Corporation.  All rights reserved.>>
        <<Satterthwaite On April 25, 1986 9:11:03 am PST>>
        <<Levin, August 8, 1983 4:06 pm>>
        <<Paul Rovner On September 19, 1983 9:31 pm>>
        <<Russ Atkinson On February 19, 1985 6:05:17 pm PST>>

    DIRECTORY
        Basics: TYPE USING [bitsPerWord],
        Symbols: TYPE USING [Base, Limit, SERecord, Type, TypeClass, CSEIndex, ArraySEIndex, RecordSEIndex, ISEIndex, CSENull, ISENull, 
        CTXRecord, CTXIndex, CTXNull, nullName, BitAddress, MDIndex],
        SymbolTable: TYPE USING [Base],
        PrincOpsUtils: TYPE USING [LongCopy],
        RCMap: TYPE,
        RCMapOps: TYPE USING [MapMapItem, MapMapObj, MapMap, OuterProc],
        VM: TYPE USING [wordsPerPage, Allocate, Free, PageNumberForAddress, AddressForPageNumber];

    InternalRCMapBuilderImpl: PROGRAM
        IMPORTS PrincOpsUtils, VM
        EXPORTS RCMapOps = {

        OPEN Symbols, RCMap;

        bitsPerWord: NAT = Basics.bitsPerWord;

    <<Types>>

        No: TYPE = BOOL_FALSE;        -- for enumerators

        UnionSEIndex: TYPE = Symbols.Base RELATIVE POINTER [0..Symbols.Limit)
            TO SERecord.cons.union;
        SequenceSEIndex: TYPE = Symbols.Base RELATIVE POINTER [0..Symbols.Limit)
            TO SERecord.cons.sequence;

        RCMapTable: PUBLIC TYPE = RECORD[
            <<basic state>>
                base: Base_NIL,
                x: INT_0,          -- number of words in use
                outer: OuterProc_NIL,
            <<expansion information>>
                expandable: BOOL_FALSE,
                limit: INT_0,      -- number of words allocated (= pages*wordsPerPage)
                pages: INT_0,
                zone: UNCOUNTED ZONE_
            ];

        RCMT: TYPE = LONG POINTER TO RCMapTable;

        Handle: TYPE = RECORD[base: Base, index: Index];

        MapMapItem: TYPE = RCMapOps.MapMapItem;
        MapMapObj: TYPE = RCMapOps.MapMapObj;
        MapMap: TYPE = RCMapOps.MapMap;
        OuterProc: TYPE = RCMapOps.OuterProc;

    <<Errors>>

        TooManyRCMaps: ERROR = CODE;
        NIY: ERROR[kind: {packedComponent, computedTag, nakedSeq}] = CODE;

        GetOuter: SIGNAL RETURNS[OuterProc];

    <<PUBLIC PROCS>>

        Create: PUBLIC PROC[
                zone: UNCOUNTED ZONE,
                ptr: Base, nPages: CARDINAL, outerProc: OuterProc_NIL,
                expansionOK: BOOL_FALSE] 
              RETURNS[rcmt: RCMT] = {
            rcmt _ zone.NEW[RCMapTable _ [
                base: ptr,    --ASSUME allocated by VM.Allocate--
                x: 0,
                outer: outerProc,
                expandable: expansionOK,
                pages: nPages,
                limit: nPages*VM.wordsPerPage,
                zone: zone]];
            IF rcmt.limit < 3 THEN ExpandRCMSpace[rcmt];
            <<make standard entries>>
                rcmt.base[nullIndex] _ [null[]];
                rcmt.base[refIndex] _ [ref[]];
                rcmt.base[controlLinkIndex] _ [controlLink[]];
            rcmt.x _ 3};

        Destroy: PUBLIC PROC[rcmt: RCMT] RETURNS[RCMT] = {
            zone: UNCOUNTED ZONE = rcmt.zone;
            IF rcmt.base # NIL THEN
                VM.Free[[page: VM.PageNumberForAddress[rcmt.base], count: rcmt.pages]];
            zone.FREE[@rcmt];
            RETURN[NIL]};

        GetSpan: PUBLIC PROC[rcmt: RCMT] RETURNS[base: Base, size: CARDINAL] = {
            RETURN[rcmt.base, rcmt.x]};

        Acquire: PUBLIC PROC[rcmt: RCMT, stb: SymbolTable.Base, type: Type] RETURNS[Index] = {
            RETURN[DoAcquire[rcmt, stb, type ! GetOuter => {RESUME[rcmt.outer]}]]};

        DoAcquire: PROC[rcmt: RCMT, stb: SymbolTable.Base, type: Type] RETURNS[Index] = {
            csei: CSEIndex = stb.UnderType[type];
            RETURN[WITH cse~~stb.seb[csei] SELECT FROM
                record => RCMapForRecord[rcmt, stb, LOOPHOLE[csei, RecordSEIndex]],
                array => RCMapForArray[rcmt, stb, LOOPHOLE[csei, ArraySEIndex]],
                sequence => RCMapForSequence[rcmt, stb, LOOPHOLE[csei, SequenceSEIndex]],
                union => RCMapForUnion[rcmt, stb, LOOPHOLE[csei, UnionSEIndex]],
                zone => (IF cse.counted THEN refIndex ELSE nullIndex),
                long => DoAcquire[rcmt, stb, cse.rangeType],
                ref => (IF cse.counted THEN refIndex ELSE nullIndex),
                ENDCASE => nullIndex]
            };

        Include: PUBLIC PROC[
                rcmt: RCMT, rcmb: Base, size: CARDINAL, zone: UNCOUNTED ZONE_NIL]
              RETURNS[mm: MapMap _ NIL] = {
            ENABLE GetOuter => {RESUME[rcmt.outer]};
            mmEntries, mmNext: CARDINAL _ 0;

            Count: PROC[Index] RETURNS[stop: No] = {mmEntries _ mmEntries + 1};

            Include: PROC[index: Index] RETURNS[stop: No] = {
                mmi: MapMapItem = [old: index, new: MapRCMIndex[rcmt, [rcmb, index]]];
                IF mm # NIL THEN mm[mmNext] _ mmi;
                mmNext _ mmNext + 1};

            IF zone # NIL THEN {
                [] _ DoEnumerate[rcmb, size, Count];
                mm _ zone.NEW[MapMapObj[mmEntries]]};
            [] _ DoEnumerate[rcmb, size, Include]};

        FindMapMapEntry: PUBLIC PROC[mapMap: MapMap, oldIndex: Index] RETURNS[Index] = {
            FOR i: CARDINAL IN [0..mapMap.length) DO
                IF mapMap[i].old = oldIndex THEN RETURN[mapMap[i].new]
                ENDLOOP;
            RETURN[invalidIndex]};

        Enumerate: PUBLIC PROC[
                base: RCMap.Base, limit: CARDINAL, proc: PROC[Index] RETURNS[stop: BOOL]]
              RETURNS[stopped: BOOL] =
            DoEnumerate;

        DoEnumerate: PROC[
                base: RCMap.Base, limit: CARDINAL, proc: PROC[Index] RETURNS[stop: BOOL]]
              RETURNS[stopped: BOOL _ FALSE] = {
            FOR rcmi: Index _ Index.FIRST, rcmi + InlineSize[[base, rcmi]]
                UNTIL LOOPHOLE[rcmi, CARDINAL] >= limit DO
                    IF Complete[[base, rcmi]] AND proc[rcmi] THEN RETURN[TRUE];
                ENDLOOP
            };


    <<FOR DEBUGGING>>
    <<>>
        NextRCMap: SIGNAL = CODE;

        ListRCMaps: PROC[rcmt: RCMT] = {
            p: PROC[index: Index] RETURNS[stop: No] = {SIGNAL NextRCMap};
            [] _ DoEnumerate[rcmt.base, rcmt.x, p]};

        Complete: PROC[h: Handle] RETURNS[BOOL] = INLINE {
            RETURN[WITH rcmr~~h.base[h.index] SELECT FROM
                null => TRUE,
                ref => TRUE,
                controlLink => TRUE,
                oneRef => TRUE,
                simple => TRUE,
                nonVariant => rcmr.complete,
                variant => rcmr.complete,
                array => TRUE,
                sequence => TRUE,
                ENDCASE => ERROR]
            };


    <<first level utility PROCs for constructing RCMap Objects>>

        NewSeqRCM: PROC[rcmt: RCMT] RETURNS[ans: SeqIndex] = {
            ans _ LOOPHOLE[AllocRCMap[rcmt, Object.sequence.SIZE]];
            rcmt.base[ans] _ [sequence[]]};

        SimpleRCM: TYPE = UNSPECIFIED;
            <<any of Object.null, Object.ref, Object.simple, Object.oneRef (Object.SIZE = 1)>>

        InstallSimpleRCM: PROC[rcmt: RCMT, srcm: SimpleRCM] RETURNS[ans: Index] = {

            proc: PROC[rcmi: Index] RETURNS[stop: BOOL] = {
                stop _ (WITH rcm~~rcmt.base[rcmi] SELECT FROM
                    simple => (srcm = rcm),
                    oneRef => (srcm = rcm),
                    ENDCASE => FALSE);
                IF stop THEN ans _ rcmi};

            IF LOOPHOLE[srcm, Object.null].type = $null THEN RETURN[nullIndex];
            IF LOOPHOLE[srcm, Object.ref].type = $ref THEN RETURN[refIndex];
            IF DoEnumerate[rcmt.base, rcmt.x, proc].stopped THEN RETURN[ans];
            ans _ AllocRCMap[rcmt, Object.simple.SIZE];    -- or any variant with size = 1
            rcmt.base[LOOPHOLE[ans, SimpIndex]] _ srcm};


        RCMapForRecord: PROC[rcmt: RCMT, stb: SymbolTable.Base, rsei: RecordSEIndex]
              RETURNS[Index] = {
            RETURN[SELECT TRUE FROM
                ~stb.seb[rsei].hints.refField => nullIndex,
                stb.seb[rsei].hints.variant => RCMapForVRecord[rcmt, stb, rsei],
                ENDCASE => RCMapForNVRecord[rcmt, stb, rsei]]
            };

        RCMapForArray: PROC[rcmt: RCMT, stb: SymbolTable.Base, asei: ArraySEIndex]
              RETURNS[Index] = {
            componentType: Type = stb.seb[asei].componentType;
            IF IsRC[stb, componentType] THEN {
                oldx: CARDINAL = rcmt.x;
                ercmi: Index = DoAcquire[rcmt, stb, componentType];

                NewARCM: PROC RETURNS[ans: AIndex] = INLINE {
                    ans _ LOOPHOLE[AllocRCMap[rcmt, Object.array.SIZE]];
                    rcmt.base[ans] _ [array[]]};

                arcmi: AIndex = NewARCM[];
                simpRCM: SimpleRCM;
                simplified: BOOL;
                <<IF stb.seb[asei].packed THEN ERROR NIY[$packedComponent];>>
                rcmt.base[arcmi] _ [array[
                    wordsPerElement: stb.WordsForType[componentType],
                    nElements: stb.Cardinality[stb.seb[asei].indexType],
                    rcmi: ercmi]];
                [simpRCM, simplified] _ SimplifyRCM[[rcmt.base, arcmi]];
                IF simplified THEN {rcmt.x _ oldx; RETURN[InstallSimpleRCM[rcmt, simpRCM]]}
                ELSE {
                    found: BOOL;  x: Index;
                    [found, x] _ FindRCMap[rcmt.base, [rcmt.base, arcmi], oldx];
                    IF found THEN {rcmt.x _ oldx; RETURN[x]} ELSE RETURN[arcmi]}}
            ELSE RETURN[nullIndex]};

        RCMapForSequence: PROC[rcmt: RCMT, stb: SymbolTable.Base, seqsei: SequenceSEIndex]
              RETURNS[Index] = {
            componentType: Type = stb.seb[seqsei].componentType;
            <<NOTE unlike unions, there is no way to get back to the enclosing record type>>
            IF TRUE THEN ERROR NIY[$nakedSeq];
            IF IsRC[stb, componentType] THEN  {
                oldx: CARDINAL = rcmt.x;
                tagSei: ISEIndex = stb.seb[seqsei].tagSei;
                ercmi: Index = DoAcquire[rcmt, stb, componentType];
                seqrcmi: SeqIndex = NewSeqRCM[rcmt];
                found: BOOL;  x: Index;
                IF ~stb.seb[seqsei].controlled THEN ERROR NIY[$computedTag];
                <<IF stb.seb[seqsei].packed THEN ERROR NIY[$packedComponent];>>
                rcmt.base[seqrcmi] _ [sequence[
                    wordsPerElement: stb.WordsForType[componentType],
                    fdLength: [
                        wordOffset: 0,
                        bitFirst: stb.seb[tagSei].idValue MOD bitsPerWord,
                        bitCount: stb.seb[tagSei].idInfo],
                    commonPart: nullIndex,
                    dataOffset: (stb.seb[tagSei].idValue + stb.seb[tagSei].idInfo)/bitsPerWord,
                    rcmi: ercmi]];
                [found, x] _ FindRCMap[rcmt.base, [rcmt.base, seqrcmi], oldx];
                IF found THEN {rcmt.x _ oldx; RETURN[x]} ELSE RETURN[seqrcmi]}
            ELSE RETURN[nullIndex]};

        RCMapForUnion: PROC[rcmt: RCMT, stb: SymbolTable.Base, usei: UnionSEIndex]
              RETURNS[rcmi: Index _ invalidIndex] = {
            IF stb.seb[usei].hints.refField THEN {

                GetRCMX: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
                    <<get the rcmi for the enclosing record>>
                    rcsei: CSEIndex = stb.UnderType[stb.TypeLink[isei]];
                    <<NOTE offset, inclusion of common parts>>
                    rcmi _ RCMapForRecord[rcmt, stb, LOOPHOLE[rcsei, RecordSEIndex]];
                    RETURN[TRUE]};  -- stop the enumeration

                nVariants: CARDINAL = stb.Cardinality[stb.seb[stb.seb[usei].tagSei].idType];
                caseCtx: CTXIndex = stb.seb[usei].caseCtx;
                [] _ EnumerateCtxIseis[stb, caseCtx, GetRCMX, (nVariants=stb.CtxEntries[caseCtx])];
                IF rcmi = invalidIndex THEN ERROR}
            ELSE rcmi _ nullIndex;
            RETURN};

        RCMapForNVRecord: PROC[rcmt: RCMT, stb: SymbolTable.Base, rsei: RecordSEIndex]
              RETURNS[Index] = {
            nc: CARDINAL = CountRCCommonComponents[stb, rsei];
            IF nc # 0 THEN {
                oldx: CARDINAL = rcmt.x;

                NewNVRCM: PROC[nComponents: [0..componentMaxIndex]]
                      RETURNS[ans: NVIndex] = INLINE {
                    ans _ LOOPHOLE[AllocRCMap[rcmt, Object.nonVariant.SIZE + nComponents*RCField.SIZE]];
                    rcmt.base[ans] _ [nonVariant[nComponents: nComponents, components: TRASH]];
                    FOR i: CARDINAL IN [0..nComponents) DO
                        rcmt.base[ans].components[i] _ []; ENDLOOP;  -- LOOPHOLE
                    };

                nvrcmi: NVIndex = NewNVRCM[nc];
                argrec: BOOL = stb.seb[rsei].argument;
                n: CARDINAL _ 0;

                Stuff: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
                    type: Type = stb.seb[isei].idType;

                    FieldOffset: PROC[isei: ISEIndex] RETURNS[BitAddress] = INLINE {
                        RETURN[IF argrec THEN stb.FnField[isei].offset ELSE stb.seb[isei].idValue]};

                    SELECT stb.TypeForm[type] FROM
                        $union, $sequence => NULL;    -- skip any variant part
                        ENDCASE =>
                            IF (~stb.seb[isei].constant) AND IsRC[stb, type] THEN {
                                rcmt.base[nvrcmi].components[n] _ [
                                    wordOffset: FieldOffset[isei].wd,
                                    rcmi: DoAcquire[rcmt, stb, type]]; 
                                n _ n + 1};
                    };

                simpRCM: SimpleRCM;
                simplified: BOOL;
                [] _ EnumerateRecordIseis[stb, rsei, Stuff];
                IF n # nc THEN ERROR;
                [simpRCM, simplified] _ SimplifyRCM[[rcmt.base, nvrcmi]];
                IF simplified THEN {rcmt.x _ oldx; RETURN[InstallSimpleRCM[rcmt, simpRCM]]}
                ELSE {
                    found: BOOL;  x: Index;
                    rcmt.base[nvrcmi].complete _ TRUE;
                    [found, x] _ FindRCMap[rcmt.base, [rcmt.base, nvrcmi], oldx];
                    IF found THEN {rcmt.x _ oldx; RETURN[x]} ELSE RETURN[nvrcmi]}
                }
            ELSE RETURN[nullIndex]};

        RCMapForVRecord: PROC[rcmt: RCMT, stb: SymbolTable.Base, rsei: RecordSEIndex]
              RETURNS[ans: Index] = {  -- maybe a sequence-containing record
            oldx: CARDINAL = rcmt.x;
            nvrcmi: Index = RCMapForNVRecord[rcmt, stb, rsei];

            TagFd: PROC[stb: SymbolTable.Base, tag: ISEIndex] RETURNS[FieldDescriptor] = {
                offset: BitAddress = stb.seb[tag].idValue;
                RETURN[[
                    wordOffset: offset.wd,
                    bitFirst: offset.bd,
                    bitCount: stb.seb[tag].idInfo]]
                };

            DoUnion: PROC[ucstb: SymbolTable.Base, ucsei: UnionSEIndex] = {  -- called once
                nvc: CARDINAL = CountRCVariants[ucstb, ucsei];
                IF nvc # 0 THEN {
                    tagSei: ISEIndex = ucstb.seb[ucsei].tagSei;
                    nVariants: CARDINAL = ucstb.Cardinality[ucstb.seb[tagSei].idType];
                    caseCtx: CTXIndex = stb.seb[ucsei].caseCtx;

                    NewVRCM: PROC[
                            nVariants: [0..componentMaxIndex], fdTag: FieldDescriptor, default: Index]
                          RETURNS[ans: VIndex] = INLINE {
                        ans _ LOOPHOLE[AllocRCMap[rcmt, Object.variant.SIZE + nVariants*Index.SIZE]];
                        rcmt.base[ans] _ [variant[fdTag: fdTag, nVariants: nVariants, variants: TRASH]];
                        FOR i: CARDINAL IN [0..nVariants) DO
                            rcmt.base[ans].variants[i] _ default ENDLOOP  -- NOTE LOOPHOLE
                        };

                    vrcmi: VIndex = NewVRCM[
                        nVariants: nVariants, fdTag: TagFd[ucstb, tagSei], default: nvrcmi];
                    n: CARDINAL _ 0;

                    Stuff: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
                        IF IsRC[stb, isei, FALSE] THEN {
                            rcmt.base[vrcmi].variants[stb.seb[isei].idValue] _ DoAcquire[rcmt, stb, isei];
                            n _ n + 1};
                        };

                    found: BOOL;  x: Index;
                    [] _ EnumerateCtxIseis[stb, caseCtx, Stuff, (nVariants=stb.CtxEntries[caseCtx])];
                    IF n # nvc THEN ERROR;
                    rcmt.base[vrcmi].complete _ TRUE;
                    [found, x] _ FindRCMap[rcmt.base, [rcmt.base, vrcmi], oldx];
                    IF found THEN {rcmt.x _ oldx; ans _ x} ELSE ans _ vrcmi}
                ELSE ans _ nvrcmi};

            DoSeq: PROC[scstb: SymbolTable.Base, scsei: SequenceSEIndex] = { -- called once
                componentType: Type = scstb.seb[scsei].componentType;
                IF IsRC[scstb, componentType] THEN {
                    ercmi: Index = DoAcquire[rcmt, scstb, componentType];
                    tagSei: ISEIndex = scstb.seb[scsei].tagSei;
                    seqrcmi: SeqIndex;
                    found: BOOL;  x: Index;
                    IF ~scstb.seb[scsei].controlled THEN ERROR NIY[$computedTag];
                    <<IF scstb.seb[scsei].packed THEN ERROR NIY[$packedComponent];>>
                    seqrcmi _ NewSeqRCM[rcmt];
                    rcmt.base[seqrcmi] _ [sequence[
                        wordsPerElement: scstb.WordsForType[componentType],
                        fdLength: TagFd[scstb, tagSei],
                        commonPart: nvrcmi,
                        dataOffset: (scstb.seb[tagSei].idValue + scstb.seb[tagSei].idInfo)/bitsPerWord,
                        rcmi: ercmi]];
                    [found, x] _ FindRCMap[rcmt.base, [rcmt.base, seqrcmi], oldx];
                    IF found THEN {rcmt.x _ oldx; ans _ x} ELSE ans _ seqrcmi}
                ELSE ans _ nvrcmi};

            DoVariant: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
                csei: CSEIndex = stb.UnderType[stb.seb[isei].idType];
                WITH c~~stb.seb[csei] SELECT FROM
                    union => DoUnion[stb, LOOPHOLE[csei]];
                    sequence => DoSeq[stb, LOOPHOLE[csei]]
                    ENDCASE => RETURN[FALSE];
                RETURN[TRUE]};

            IF ~EnumerateCtxIseis[stb, stb.seb[rsei].fieldCtx, DoVariant] THEN ERROR};


    <<second level utility PROCs for constructing RCMap Objects>>

        SimplifyRCM: PROC[h: Handle] RETURNS[rcmr: SimpleRCM, simplified: BOOL] = {
            srcmr: Object.simple _ [simple[refs: ALL[FALSE]]];
            rrcmr: Object.oneRef _ [oneRef[]];
            nRefOffsets: CARDINAL _ 0;
            nSimpleVecEntries: CARDINAL _ 0;

            Enumerate: PROC[index: Index, offset: CARDINAL] RETURNS[stopped: BOOL] = {
                WITH rcm~~h.base[index] SELECT FROM
                    null => RETURN[FALSE];
                    ref => RETURN[Test[offset]];
                    controlLink => RETURN[TRUE];
                    oneRef => RETURN[Test[offset+rcm.offset]];
                    simple => {
                        FOR i: CARDINAL IN [0..rcm.length) DO
                            IF rcm.refs[i] AND Test[offset+i].stop THEN RETURN[TRUE];
                            ENDLOOP;
                        RETURN[FALSE]};
                    nonVariant => {
                        FOR i: CARDINAL IN [0 .. rcm.nComponents) DO
                            IF Enumerate[rcm.components[i].rcmi, offset+rcm.components[i].wordOffset
                                ].stopped THEN
                                RETURN[TRUE];
                            ENDLOOP;
                        RETURN[FALSE]};
                    array => {
                        FOR i: CARDINAL IN [0 .. rcm.nElements) DO
                            IF Enumerate[rcm.rcmi, offset+i*rcm.wordsPerElement].stopped THEN
                                RETURN[TRUE];
                            ENDLOOP;
                        RETURN[FALSE]};
                    variant, sequence => RETURN[TRUE];
                    ENDCASE => ERROR
                };


            Test: PROC[refOffset: CARDINAL] RETURNS[stop: No] = {
                nRefOffsets _ nRefOffsets+1;
                IF ((nRefOffsets # 1) OR (refOffset > componentMaxIndex))
                    AND (refOffset > simpleMaxIndex) THEN RETURN[TRUE];  -- can't simplify
                IF nRefOffsets = 1 AND refOffset <= componentMaxIndex THEN
                    rrcmr.offset _ refOffset;
                IF refOffset <= simpleMaxIndex THEN {
                    nSimpleVecEntries _ nSimpleVecEntries + 1;
                    IF nSimpleVecEntries # nRefOffsets THEN RETURN[TRUE];  -- can't simplify
                    srcmr.refs[refOffset] _ TRUE;
                    srcmr.length _ MAX[srcmr.length, refOffset + 1]};
                };

            simplified _ ~Enumerate[h.index, 0].stopped;
            IF simplified THEN {
                IF nRefOffsets = 0 THEN rcmr _ Object[null[]]
                ELSE IF nRefOffsets = 1 THEN {
                    IF rrcmr.offset = 0 THEN rcmr _ Object[ref[]]
                    ELSE rcmr _ rrcmr}
                ELSE rcmr _ srcmr}
            ELSE rcmr _ Object[null[]]};

    <<>>
    <<PROCS for poking around in the symbol table>>

            <<copied (GROAN) from RTWalkSymbolsImpl>>
        EnumerateRecordIseis: PROC[
                stb: SymbolTable.Base,
                rsei: RecordSEIndex,
                p: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL],
                level: CARDINAL_0] 
              RETURNS[stopped: BOOL] = {

            Filter: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
                form: TypeClass = stb.TypeForm[stb.seb[isei].idType];
                IF ~(form = $union OR form = $sequence) OR level = 0 THEN RETURN[p[stb, isei]];
                RETURN[FALSE]};

            IF rsei = CSENull THEN RETURN[FALSE];
            SELECT stb.seb[rsei].linkTag FROM
                $linked =>
                    IF EnumerateRecordIseis[stb, stb.RecordLink[rsei], p, level+1] THEN RETURN[TRUE];
                ENDCASE;
            RETURN[EnumerateCtxIseis[stb, stb.seb[rsei].fieldCtx, Filter]]};

            <<copied (GROAN) from RTWalkSymbolsImpl>>
        EnumerateCtxIseis: PROC [
                stb: SymbolTable.Base, ctx: CTXIndex,
                proc: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL],
                reallyComplete: BOOL_FALSE]
              RETURNS[stopped: BOOL] = {
            isei: ISEIndex;
            IF ctx = CTXNull THEN RETURN[FALSE];
            IF ~reallyComplete THEN
                WITH c~~stb.ctxb[ctx] SELECT FROM
                    included => 
                        IF ~c.complete THEN {
                            p: PROC[base: SymbolTable.Base] = { -- called once
                                stopped _ EnumerateCtxIseis[base, c.map, proc]};
                            outer: OuterProc = SIGNAL GetOuter[];
                            IF outer = NIL THEN ERROR ELSE outer[stb, c.module, p];
                            RETURN[stopped]};
                    simple => NULL;
                    ENDCASE => ERROR;
            FOR isei _ stb.FirstCtxSe[ctx], stb.NextSe[isei] UNTIL isei = ISENull DO
                IF stb.seb[isei].hash = nullName AND stb.seb[isei].idCtx = CTXNull THEN NULL  -- padding
                ELSE IF proc[stb, isei] THEN RETURN[TRUE];
                ENDLOOP;
            RETURN[FALSE]};

        CountRCVariants: PROC[stb: SymbolTable.Base, usei: UnionSEIndex] 
              RETURNS[n: CARDINAL _ 0] = {

            Count: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
                IF IsRC[stb, isei, FALSE] THEN n _ n+1};

            caseCtx: CTXIndex = stb.seb[usei].caseCtx;
            tagCardinality: CARDINAL = stb.Cardinality[stb.seb[stb.seb[usei].tagSei].idType];
            [] _ EnumerateCtxIseis[stb, caseCtx, Count, (tagCardinality=stb.CtxEntries[caseCtx])]};

        CountRCCommonComponents: PROC[stb: SymbolTable.Base, rsei: RecordSEIndex] 
              RETURNS[n: CARDINAL _ 0] = {

            Count: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
                type: Type = stb.seb[isei].idType;
                SELECT stb.TypeForm[type] FROM
                    $union, $sequence => NULL;  -- don't count the variant part
                    ENDCASE => IF (~stb.seb[isei].constant) AND IsRC[stb, type] THEN n _ n+1
                };

            [] _ EnumerateRecordIseis[stb, rsei, Count]};

            <<copied (GROAN) from RTWalkSymbolsImpl>>
        IsRC: PROC[stb: SymbolTable.Base, seIndex: Type, checkCommon: BOOL_TRUE]
              RETURNS[BOOL] = {
            csei: CSEIndex = stb.UnderType[seIndex];
            WITH cr~~stb.seb[csei] SELECT FROM
                record => {

                    rcP: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
                        csei1: CSEIndex = stb.UnderType[stb.seb[isei].idType];
                        WITH cse1~~stb.seb[csei1] SELECT FROM
                            union => {

                                urcP: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
                                    RETURN[IsRC[stb, isei, FALSE]]};

                                tagCardinality: CARDINAL = stb.Cardinality[stb.seb[cse1.tagSei].idType];
                                RETURN[EnumerateCtxIseis[stb, cse1.caseCtx, urcP,
                                    (tagCardinality=stb.CtxEntries[cse1.caseCtx])]];
                                };
                            sequence => RETURN[IsRC[stb, cse1.componentType]];
                            ENDCASE => RETURN[IsRC[stb, csei1]];
                        };

                    RETURN[
                        IF checkCommon THEN cr.hints.refField  -- easy if the common parts count
                        ELSE  -- look individually at the fields of the variant part (unless none possible)
                            (cr.hints.refField AND EnumerateCtxIseis[stb, cr.fieldCtx, rcP])];
                    };
                ref => RETURN[cr.counted];
                array => RETURN[IsRC[stb, cr.componentType]];
                transfer => RETURN[FALSE];  -- NOTE for now
                union, sequence => ERROR;
                relative => RETURN[FALSE];  -- NOTE for now
                long => RETURN[IsRC[stb, cr.rangeType]];
                zone => RETURN[cr.counted];
                ENDCASE => RETURN[FALSE]
            };


    <<PROCs for managing RCMap Bases>>

        InlineSize: PROC[h: Handle] RETURNS[CARDINAL] = INLINE {
            RETURN[WITH rcm~~h.base[h.index] SELECT FROM
                null => Object.null.SIZE, --NOTE better be 1
                ref => Object.ref.SIZE, --NOTE better be 1
                controlLink => Object.controlLink.SIZE, --NOTE better be 1
                oneRef => Object.oneRef.SIZE, --NOTE better be 1
                simple => Object.simple.SIZE, --NOTE better be 1
                nonVariant => Object.nonVariant.SIZE + rcm.nComponents*RCField.SIZE,
                variant => Object.variant.SIZE + rcm.nVariants*Index.SIZE,
                array => Object.array.SIZE,
                sequence => Object.sequence.SIZE,
                ENDCASE => ERROR]
            };

        EqualMaps: PROC[h1, h2: Handle] RETURNS[BOOL] = {
            WITH m1~~h1.base[h1.index] SELECT FROM
                null, ref, controlLink => RETURN[h1.index = h2.index];    -- StandardRCMap's
                oneRef => RETURN[m1 = h2.base[h2.index]];
                simple => RETURN[m1 = h2.base[h2.index]];
                nonVariant =>
                    WITH m2~~h2.base[h2.index] SELECT FROM
                        nonVariant => {
                            matched: BOOL _
                                (m1.complete AND m2.complete) AND (m1.nComponents = m2.nComponents);
                            FOR i: NAT IN [0 .. m1.nComponents) WHILE matched DO
                                matched _ (m1.components[i].wordOffset = m2.components[i].wordOffset)
                                    AND EqualMaps[[h1.base, m1.components[i].rcmi],
                                        [h2.base, m2.components[i].rcmi]];
                                ENDLOOP;
                            RETURN[matched]};
                        ENDCASE => RETURN[FALSE];
                variant =>
                    WITH m2~~h2.base[h2.index] SELECT FROM
                        variant => {
                            matched: BOOL _ (m1.complete AND m2.complete)
                                AND (m1.nVariants = m2.nVariants) AND (m1.fdTag = m2.fdTag);
                            FOR i: NAT IN [0 .. m1.nVariants) WHILE matched DO
                                matched _ EqualMaps[[h1.base, m1.variants[i]], [h2.base, m2.variants[i]]];
                                ENDLOOP;
                            RETURN[matched]};
                        ENDCASE => RETURN[FALSE];
                array =>
                    WITH m2~~h2.base[h2.index] SELECT FROM
                        array =>
                            RETURN[
                                (m1.wordsPerElement # m2.wordsPerElement)
                                    AND (m1.nElements # m2.nElements)
                                    AND EqualMaps[[h1.base, m1.rcmi], [h2.base, m2.rcmi]]
                                ];
                        ENDCASE => RETURN[FALSE];
                sequence =>
                    WITH m2~~h2.base[h2.index] SELECT FROM
                        sequence =>
                            RETURN[
                                (m1.wordsPerElement # m2.wordsPerElement)
                                    AND (m1.fdLength # m2.fdLength)
                                    AND (m1.dataOffset # m2.dataOffset)
                                    AND EqualMaps[[h1.base, m1.commonPart], [h2.base, m2.commonPart]]
                                    AND EqualMaps[[h1.base, m1.rcmi], [h2.base, m2.rcmi]]
                                ];
                        ENDCASE => RETURN[FALSE];
                ENDCASE => ERROR;
            };


        FindRCMap: PROC[rcmb: Base, h: Handle, limit: CARDINAL]
              RETURNS[found: BOOL, index: Index] = {
            WITH rcm~~h.base[h.index] SELECT FROM
                null, ref, controlLink => {found _ TRUE;  index _ h.index};    -- standard entries
                ENDCASE => {
                    <<Frequent case of DoEnumerate is placed INLINE and specialized!>>
                    <<Note that EqualMaps itself tests for completeness>>
                    FOR rcmi: Index _ controlLinkIndex+Object.controlLink.SIZE,
                        rcmi + InlineSize[[rcmb, rcmi]] UNTIL LOOPHOLE[rcmi, CARDINAL] >= limit DO
                            IF EqualMaps[h, [rcmb, rcmi]] THEN RETURN[TRUE, rcmi];
                            ENDLOOP;
                    found _ FALSE};
            RETURN};

        EnterRCMap: PROC[rcmt: RCMT, h: Handle] RETURNS[new: Index] = {
            nw: CARDINAL = InlineSize[h];
            new _ AllocRCMap[rcmt, nw];

            WITH m~~h.base[h.index] SELECT FROM
                null, ref, controlLink, oneRef, simple => {
                    PrincOpsUtils.LongCopy[from: @h.base[h.index], to: @rcmt.base[new], nwords: nw]};
                array => {
                    cRcmi: Index = MapRCMIndex[rcmt, [h.base, m.rcmi]];
                    rcmt.base[new] _ [array[
                        wordsPerElement: m.wordsPerElement, nElements: m.nElements, rcmi: cRcmi]];
                    };
                nonVariant => {
                    nvRcmi: RCMap.NVIndex = LOOPHOLE[new];
                    rcmt.base[nvRcmi] _ [nonVariant[
                        nComponents: m.nComponents, components: TRASH, complete: FALSE]];
                    FOR i: NAT IN [0..m.nComponents) DO
                        rcmt.base[nvRcmi].components[i] _ [
                            m.components[i].wordOffset, MapRCMIndex[rcmt, [h.base, m.components[i].rcmi]]];
                        ENDLOOP;
                    rcmt.base[nvRcmi].complete _ TRUE};
                variant => {
                    vRcmi: RCMap.VIndex = LOOPHOLE[new];
                    rcmt.base[vRcmi] _ [variant[
                        nVariants: m.nVariants, fdTag: m.fdTag, variants: TRASH, complete: FALSE]];
                    FOR i: NAT IN [0..m.nVariants) DO
                        rcmt.base[vRcmi].variants[i] _ MapRCMIndex[rcmt, [h.base, m.variants[i]]];
                        ENDLOOP;
                    rcmt.base[vRcmi].complete _ TRUE};
                sequence => {
                    commonRcmi: Index = MapRCMIndex[rcmt, [h.base, m.commonPart]];
                    cRcmi: Index = MapRCMIndex[rcmt, [h.base, m.rcmi]];
                    rcmt.base[new] _ [sequence[
                        wordsPerElement: m.wordsPerElement, fdLength: m.fdLength,
                        commonPart: commonRcmi, dataOffset: m.dataOffset, rcmi: cRcmi]];
                    };
                ENDCASE => ERROR;
            RETURN};

        MapRCMIndex: PROC[rcmt: RCMT, old: Handle] RETURNS[new: Index] = {
            found: BOOL;
            [found, new] _ FindRCMap[rcmt.base, old, rcmt.x];
            IF ~found THEN new _ EnterRCMap[rcmt, old];
            RETURN};

        AllocRCMap: PROC[rcmt: RCMT, nw: CARDINAL] RETURNS[Index] = {
            short: CARDINAL _ rcmt.x;
            new: Index _ LOOPHOLE[short];
            IF new = invalidIndex THEN ERROR TooManyRCMaps;
            rcmt.x _ rcmt.x + nw;
            IF rcmt.x > rcmt.limit THEN ExpandRCMSpace[rcmt];
            rcmt.base[new] _ [null[]];
            IF nw > 1 THEN
                <<Ensure valid initialization for this map entry to avoid finding crap!>>
                PrincOpsUtils.LongCopy[from: @rcmt.base[new], to: @rcmt.base[new+1], nwords: nw-1];
            RETURN[LOOPHOLE[new]]};

        ExpandRCMSpace: PROC[rcmt: RCMT] = {
            newBase: RCMap.Base;
            newPages: INT = rcmt.pages+4;
            IF ~rcmt.expandable THEN ERROR TooManyRCMaps;
            newBase _
                LOOPHOLE[VM.AddressForPageNumber[VM.Allocate[count: newPages].page], RCMap.Base];
            IF rcmt.base # NIL THEN {
                PrincOpsUtils.LongCopy[from: rcmt.base, to: newBase, nwords: rcmt.limit];
                VM.Free[[page: VM.PageNumberForAddress[rcmt.base], count: rcmt.pages]]};
            rcmt.base _ newBase;
            rcmt.pages _ newPages;
            rcmt.limit _ newPages*VM.wordsPerPage};


    <<START HERE>>

        <<static check of size assumptions>>
        check: BOOL[FALSE ..
            Object.null.SIZE = 1
                AND Object.ref.SIZE = 1
                AND Object.oneRef.SIZE = 1
                AND Object.simple.SIZE = 1
                AND Object.controlLink.SIZE = 1
            ] = TRUE;

        }.