
    <<Pass4D.mesa>>
        <<Copyright  1985 by Xerox Corporation.  All rights reserved.>>
        <<Satterthwaite, June 18, 1986 11:43:47 am PDT>>
        <<Russ Atkinson (RRA) March 6, 1985 10:51:16 pm PST>>

    DIRECTORY
        Alloc: TYPE USING [Notifier],
        BcdDefs: TYPE USING [ModuleIndex],
        ComData: TYPE USING [idCARDINAL, interface, mainCtx, textIndex],
        PrincOps: TYPE USING [globalbase, localbase],
        Log: TYPE USING [Error, ErrorSei, ErrorTree, Warning],
        P4: TYPE USING [AdjustBias, BitsForType, both, CheckFields, ConstantInterval, currentLevel, EmptyInterval, ForceType, Interval, 
        LayoutArgs, LayoutFields, MakeEPLink, mark, none, OpWordCount, other, ownGfi, Prop, Repr, RewriteAssign, Rhs, SetType, 
        signed, StructuredLiteral, TreeLiteral, TreeLiteralValue, unsigned, VPop, VProp, VRep],
        SourceMap: TYPE USING [Loc],
        Symbols: TYPE USING [Base, BitAddress, BitCount, bodyType, CBTIndex, CBTNull, codeANY, codeCHAR, codeINT, CSEIndex, CSENull, 
        CTXIndex, ctxType, ExtensionType, ISEIndex, ISEFirst, ISENull, lG, lZ, nullType, RecordSEIndex, RecordSENull, RootBti, 
        seType, Type, typeANY, TypeClass, typeTYPE, UNSPEC],
        SymbolOps: TYPE USING [ArgRecord, AUsForType, BitsPerElement, Cardinality, ConstantId, CtxEntries, CtxLevel, DecodeCard, DecodeBti, 
        DecodeTreeIndex, DecodeType, EncodeBti, EncodeBitAddr, EncodeCard, EncodeLink, EnterExtension, FindExtension, FirstCtxSe, 
        FromBti, LinkMode, NextSe, NormalType, RCType, SearchContext, ToBti, ToType, TypeLink, UnderType],
        Target: TYPE MachineParms USING [bitsPerAU, maxWord],
        Tree: TYPE USING [Base, Index, Link, Map, NodeName, Null, Scan, treeType],
        TreeOps: TYPE USING [CopyTree, FreeNode, FreeTree, GetNode, GetTag, IdentityMap, ListHead, ListLength, NthSon, OpName, PopTree, 
        PushList, PushNode, PushTree, ScanList, SetAttr, SetInfo, ToCard, ToLoc, UpdateList];

    Pass4D: PROGRAM
        IMPORTS Log, P4, SymbolOps, TreeOps, dataPtr: ComData
        EXPORTS P4 = {
        OPEN TreeOps, SymbolOps, Symbols;

        tb: Tree.Base;    -- tree base address (local copy)
        seb: Symbols.Base;    -- se table base address (local copy)
        ctxb: Symbols.Base;    -- context table base address (local copy)
        bb: Symbols.Base;    -- body table base address (local copy)

        DeclNotify: PUBLIC Alloc.Notifier = {
            <<called by allocator whenever table area is repacked>>
            tb _ base[Tree.treeType];
            seb _ base[seType];  ctxb _ base[ctxType];
            bb _ base[bodyType]};


        VarInit: PUBLIC SIGNAL RETURNS[BOOL] = CODE;

        ownGfi: BcdDefs.ModuleIndex = P4.ownGfi;

        bitsPerAU: CARDINAL = Target.bitsPerAU;


        ItemId: PROC[t: Tree.Link] RETURNS[ISEIndex] = {
            RETURN[WITH t SELECT GetTag[t] FROM
                symbol => index,
                subtree => ItemId[tb[index].son[1]],
                ENDCASE => ERROR]
            };

        FirstId: PROC[node: Tree.Index] RETURNS[ISEIndex] = {
            RETURN[ItemId[ListHead[tb[node].son[1]]]]};


        DeclItem: PUBLIC PROC[item: Tree.Link] = {
            node: Tree.Index = GetNode[item];
            initFlag, eqFlag: BOOL;

            ExpInit: PROC = INLINE {
                OPEN tb[node];
                type: Type = TypeForDecl[node];
                class: TypeClass = seb[NormalType[type]].typeTag;
                son[3] _ P4.Rhs[son[3], type, $init];
                IF eqFlag THEN {
                    t: Tree.Link _ son[3];
                    prop: P4.Prop = P4.VProp[];
                    WHILE OpName[t] = cast DO t _ NthSon[t, 1] ENDLOOP;
                    IF P4.TreeLiteral[t] THEN {
                        DefineSEValue[ids: son[1], value: EncodeCard[P4.TreeLiteralValue[t]]];
                        GO TO defined};
                    IF prop.noFreeVar AND prop.noXfer AND class # $transfer THEN {
                        DefineSEValue[ids:son[1]];
                        AugmentSEValue[son[1], value, son[3]]; son[3] _ Tree.Null; GO TO defined};
                    IF class = $transfer THEN
                        WITH t SELECT GetTag[t] FROM
                            symbol => {
                                sei: ISEIndex = index;
                                IF seb[sei].constant THEN {
                                    DefineSEValue[
                                        ids: son[1], value: seb[sei].idValue, info: DecodeBti[seb[sei].idInfo]];
                                    IF seb[sei].extended THEN
                                        AugmentSEValue[son[1], form, FindExtension[sei].tree, TRUE];
                                    GO TO defined}};
                            ENDCASE;
                    DefineSEVar[ids:son[1]];
                    EXITS
                        defined => son[3] _ FreeTree[son[3]]};
                SELECT class FROM
                    $ref, $arraydesc, $relative =>
                        IF ListLength[son[1]] # 1 AND son[3] # Tree.Null
                            AND ~P4.StructuredLiteral[son[3]] THEN
                                Log.Warning[pointerInit];
                    ENDCASE;
                P4.VPop[]};

            BodyInit: PROC = INLINE {
                expNode: Tree.Index = GetNode[tb[node].son[3]];
                bti: CBTIndex = LOOPHOLE[ToBti[tb[expNode].info]];
                IF eqFlag THEN {
                    IF tb[expNode].attr3 THEN {  -- inline
                        DefineSEValue[ids:tb[node].son[1], info:bti];
                        AugmentSEValue[tb[node].son[1], form,
                            IF dataPtr.interface THEN TrimTree[tb[node].son[3]] ELSE Tree.Null]}
                    ELSE DefineSEValue[
                        ids: tb[node].son[1],
                        value: EncodeLink[P4.MakeEPLink[bb[bti].entryIndex, ownGfi]],
                        info: bti];
                    tb[node].son[3] _ Tree.Null}
                ELSE {PushNode[body, 0]; SetInfo[FromBti[bti]]; tb[node].son[3] _ PopTree[]}};

            saveIndex: SourceMap.Loc = dataPtr.textIndex;
            IF tb[node].attr3 = P4.mark THEN RETURN;    -- already processed
            tb[node].attr3 _ P4.mark;
            dataPtr.textIndex _ ToLoc[tb[node].info];
            initFlag _ (tb[node].son[3] # Tree.Null);
            IF tb[node].name = typedecl THEN {
                ENABLE VarInit => {RESUME[FALSE]};
                TypeExp[tb[node].son[2]];  CheckDefaults[item]}
            ELSE {
                OPEN tb[node];
                op: Tree.NodeName = OpName[son[3]];
                IF son[2] # Tree.Null THEN TypeExp[son[2], op = body];
                IF initFlag THEN {
                    eqFlag _ attr1;
                    SELECT op FROM
                        body, procinit => BodyInit[];
                        signalinit =>
                            IF eqFlag THEN {
                                expNode: Tree.Index = GetNode[son[3]];
                                DefineSEValue[
                                    son[1],
                                    EncodeLink[P4.MakeEPLink[ToCard[tb[expNode].info], ownGfi]],
                                    RootBti]; 
                                son[3] _ FreeTree[son[3]]};
                        inline => {
                            expNode: Tree.Index = GetNode[son[3]];
                            tb[expNode].son[1] _ UpdateList[tb[expNode].son[1], InlineOp];
                            DefineSEValue[ids:son[1]];
                            AugmentSEValue[son[1], value, son[3]];  son[3] _ Tree.Null};
                        ENDCASE => ExpInit[]}};
            MarkAndCheckSE[tb[node].son[1], initFlag];
            dataPtr.textIndex _ saveIndex};

        TypeForDecl: PROC[node: Tree.Index] RETURNS[Type] = {
            RETURN[IF tb[node].son[2] # Tree.Null
                THEN TypeForTree[tb[node].son[2]]
                ELSE seb[FirstId[node]].idType]
            };


        ConstInit: PROC[t: Tree.Link] RETURNS[BOOL] = {
            RETURN[IF OpName[t] # all THEN P4.StructuredLiteral[t] ELSE ConstInit[NthSon[t, 1]]]};

        InlineByte: Tree.Map = {
            v _ P4.Rhs[t, dataPtr.idCARDINAL];  P4.VPop[];
            IF ~P4.TreeLiteral[v] THEN Log.ErrorTree[nonConstant, v];
            RETURN};

        InlineOp: Tree.Map = {RETURN[UpdateList[t, InlineByte]]};


        DefineSEVar: PROC[ids: Tree.Link] = {

            UpdateSE: Tree.Scan = {
                sei: ISEIndex = ItemId[t];
                seb[sei].constant _ FALSE};

            ScanList[ids, UpdateSE]};

        nullValue: UNSPEC = EncodeCard[0];

        DefineSEValue: PROC[ids: Tree.Link, value: UNSPEC_nullValue, info: CBTIndex_CBTNull] = {

            UpdateSE: Tree.Scan = {
                sei: ISEIndex = ItemId[t];
                seb[sei].constant _ TRUE;
                seb[sei].idValue _ value;  seb[sei].idInfo _ EncodeBti[info]};

            ScanList[ids, UpdateSE]};

        AugmentSEValue: PROC[
            ids: Tree.Link,
            type: ExtensionType, extension: Tree.Link,
            copy: BOOL_FALSE] = {

            UpdateSE: Tree.Scan = {
                sei: ISEIndex = ItemId[t];
                EnterExtension[sei, type, IF copy THEN IdentityMap[extension] ELSE extension];
                copy _ TRUE};

            ScanList[ids, UpdateSE]};


        MarkAndCheckSE: PROC[ids: Tree.Link, initialized: BOOL] = {

            UpdateSE: Tree.Scan = {
                sei: ISEIndex = ItemId[t];
                seb[sei].mark4 _ TRUE;
                IF dataPtr.interface THEN CheckDefinition[sei, initialized];
                IF seb[sei].idType = typeTYPE AND CtxLevel[seb[sei].idCtx] # lZ THEN
                    seb[sei].idValue _ EncodeCard[sei - ISEFirst]
                };

            ScanList[ids, UpdateSE]};


        CheckDefinition: PROC[sei: ISEIndex, initialized: BOOL] = {
            SELECT seb[sei].idCtx FROM
                dataPtr.mainCtx =>
                    SELECT LinkMode[sei] FROM
                        val => IF ~initialized OR seb[sei].extended THEN RETURN;
                        ref => IF ~initialized THEN RETURN;
                        manifest, type => IF ConstantId[sei] THEN RETURN;
                        ENDCASE;
                ENDCASE => RETURN;
            Log.ErrorSei[nonDefinition, sei]};


        CheckDefaults: PROC[t: Tree.Link] = {

            TestDefaults: Tree.Scan = {
                node: Tree.Index = GetNode[t];
                saveIndex: SourceMap.Loc = dataPtr.textIndex;
                sei: ISEIndex = FirstId[node];
                dataPtr.textIndex _ ToLoc[tb[node].info];
                IF seb[sei].extended THEN {
                    type: Type = (IF seb[sei].idType = typeTYPE THEN sei ELSE seb[sei].idType);
                    nType: CSEIndex = NormalType[type];

                    TestDefault: Tree.Map = {
                        IF OpName[t] = void THEN v _ t
                        ELSE {
                            v _ P4.AdjustBias[P4.Rhs[t, type, $init], -BiasForType[type]];
                            IF P4.TreeLiteral[v] AND (
                                WITH n: seb[nType] SELECT FROM
                                    basic => n.code # codeINT OR P4.VRep[] = P4.signed,
                                    ENDCASE => TRUE) THEN
                                    v _ P4.ForceType[v, type];
                            IF ~(P4.VProp[].noFreeVar OR (SIGNAL VarInit[])) THEN
                                Log.ErrorTree[nonConstant, v];
                            P4.VPop[]};
                        RETURN};

                    t: Tree.Link _ FindExtension[sei].tree;
                    v: Tree.Link _ UpdateList[IdentityMap[t], TestDefault];
                    IF GetTag[t] # symbol AND P4.StructuredLiteral[v] THEN
                        UpdateDefaults[tb[node].son[1], v]
                    ELSE v _ FreeTree[v]};
                dataPtr.textIndex _ saveIndex};

            IF dataPtr.interface THEN ScanList[t, TestDefaults]};

        UpdateDefaults: PROC[ids: Tree.Link, v: Tree.Link] = {
            copy: BOOL _ FALSE;

            UpdateDefault: Tree.Scan = {
                sei: ISEIndex = ItemId[t];
                old: Tree.Link _ FindExtension[sei].tree;
                EnterExtension[sei, default, IF copy THEN IdentityMap[v] ELSE v];
                copy _ TRUE;
                [] _ FreeTree[old]};

            ScanList[ids, UpdateDefault]};


        TrimTree: Tree.Map = {
            WITH t SELECT GetTag[t] FROM
                subtree => {
                    node: Tree.Index = index;
                    SELECT tb[node].name FROM
                        body => {
                            OPEN tb[node];
                            PushTree[TrimTree[son[1]]];
                            PushTrimDecls[son[2]];
                            PushTree[TrimTree[son[3]]];  PushTree[TrimTree[son[4]]];
                            PushNode[body, 4];  SetInfo[info];
                            SetAttr[1, attr1]; SetAttr[2, attr2]; SetAttr[3, attr3];
                            v _ PopTree[]};
                        block => {
                            OPEN tb[node];
                            PushTrimDecls[son[1]];  PushTree[TrimTree[son[2]]];
                            PushNode[block, 2];  SetInfo[info];
                            SetAttr[1, attr1]; SetAttr[2, attr2]; SetAttr[3, attr3];
                            v _ PopTree[]};
                        cdot => v _ TrimTree[tb[node].son[2]];
                        ENDCASE => v _ CopyTree[[@tb, t], TrimTree]};
                ENDCASE => v _ t;
            RETURN};

        PushTrimDecls: PROC[t: Tree.Link] = {
            IF OpName[t] = initlist THEN {
                node: Tree.Index = GetNode[t];
                PushTree[TrimTree[tb[node].son[1]]];  PushTrimDecls[tb[node].son[2]];
                PushNode[initlist, 2];  SetInfo[tb[node].info]}
            ELSE {
                n: CARDINAL _ 0;

                PushDecl: Tree.Scan = {
                    node: Tree.Index = GetNode[t];
                    SELECT tb[node].name FROM
                        typedecl => NULL;
                        decl =>
                            IF tb[node].son[3] # Tree.Null THEN {
                                OPEN  tb[node];
                                PushTree[TrimTree[son[1]]];  PushTree[Tree.Null];
                                PushTree[TrimTree[son[3]]];
                                PushNode[decl, 3];  SetInfo[info];
                                SetAttr[1, attr1]; SetAttr[2, attr2]; SetAttr[3, ~P4.mark];
                                n _ n+1};
                        ENDCASE => ERROR};

                ScanList[t, PushDecl];  PushList[n]}
            };


        DeclUpdate: PUBLIC PROC[item: Tree.Link] RETURNS[update: Tree.Link] = {
            node: Tree.Index = GetNode[item];
            IF tb[node].name = typedecl OR tb[node].son[3] = Tree.Null THEN
                update _ Tree.Null
            ELSE {
                OPEN tb[node];
                type: Type = TypeForDecl[node];
                rewrite: BOOL = SELECT OpName[tb[node].son[3]] FROM
                    body, signalinit => FALSE,
                    ENDCASE => TRUE;
                n: CARDINAL = ListLength[tb[node].son[1]];
                ScanList[tb[node].son[1], PushTree];
                PushTree[tb[node].son[3]];
                FOR i: CARDINAL IN [1 .. n] DO
                    IF i = n THEN PushNode[assign, 2]
                    ELSE {PushNode[assignx, 2]; P4.SetType[type]};
                    SetInitAttr[type, ConstInit[tb[node].son[3]]];
                    IF rewrite THEN PushTree[P4.RewriteAssign[GetNode[PopTree[]], type]];
                    ENDLOOP;
                SetInfo[info];  update _ PopTree[];  tb[node].son[3] _ Tree.Null};
            FreeNode[node];
            RETURN};


        SetInitAttr: PROC[type: Type, const: BOOL] = {
            SetAttr[1, TRUE];
            IF P4.currentLevel = lG AND ~const THEN
                SELECT RCType[type] FROM
                    simple => {SetAttr[2, TRUE]; SetAttr[3, FALSE]};
                    composite => {SetAttr[2, TRUE]; SetAttr[3, TRUE]};
                    ENDCASE => SetAttr[2, FALSE]
            ELSE SetAttr[2, FALSE]};


        TypeExp: PUBLIC PROC[typeExp: Tree.Link, body, indirect: BOOL _ FALSE] = {
            <<body => arg records subsumed by frame>>
            WITH typeExp SELECT GetTag[typeExp] FROM
                symbol =>
                    IF ~indirect THEN {
                        iSei: ISEIndex = index;
                        IF ~seb[iSei].mark4 THEN
                            DeclItem[[subtree[index: DecodeTreeIndex[seb[iSei].idValue]]]]
                        };
                subtree => {
                    node: Tree.Index = index;
                    SELECT tb[node].name FROM
                        discrimTC => TypeExp[tb[node].son[1], FALSE, indirect];
                        cdot => TypeExp[tb[node].son[2], body, indirect];
                        implicitTC, linkTC => NULL;
                        frameTC => NULL;
                        ENDCASE => {
                            OPEN tb[node];
                            sei: CSEIndex = UnderType[ToType[info]];
                            IF ~seb[sei].mark4 THEN
                                WITH type: seb[sei] SELECT FROM
                                    enumerated =>
                                        IF type.machineDep THEN
                                            [empty: type.empty, range: type.range, sparse: type.sparse] _
                                                LayoutEnum[son[1], type.valueCtx];
                                    record => {
                                        ENABLE VarInit => {RESUME[FALSE]};
                                        ScanList[son[1], DeclItem];
                                        IF attr1 THEN ScanList[son[1], AssignPositions];
                                        WITH type SELECT FROM
                                            notLinked =>
                                                IF attr1 THEN P4.CheckFields[LOOPHOLE[sei, RecordSEIndex], 0]
                                                ELSE P4.LayoutFields[LOOPHOLE[sei, RecordSEIndex], 0];
                                            ENDCASE;
                                        ExtractFieldAttributes[LOOPHOLE[sei, RecordSEIndex]];
                                        CheckDefaults[son[1]]};
                                    ref => {
                                        IF type.var AND FALSE THEN Log.Error[unimplemented];
                                        TypeExp[son[1], FALSE, TRUE]};
                                    array => {
                                        maxArraySize: CARD = BitCount.LAST/bitsPerAU;
                                        IF son[1] # Tree.Null THEN TypeExp[son[1]];
                                        TypeExp[son[2], FALSE, indirect];
                                        IF Cardinality[type.indexType] >
                                            MaxCardinality[type.componentType, type.packed, maxArraySize] THEN
                                                Log.Error[arraySize]};
                                    arraydesc => TypeExp[son[1], FALSE, TRUE];
                                    transfer => {
                                        origin, newOrigin: CARDINAL;
                                        rSei: RecordSEIndex;
                                        origin _ SELECT type.mode FROM
                                            program => PrincOps.globalbase,
                                            signal, error => PrincOps.localbase+1,
                                            proc => PrincOps.localbase,
                                            ENDCASE => 0;
                                        IF OpName[son[1]] # anyTC THEN {
                                            ScanList[son[1], DeclItem];  CheckDefaults[son[1]]};
                                        rSei _ ArgRecord[type.typeIn];
                                        IF rSei # RecordSENull THEN {
                                            seb[rSei].hints.comparable _ TRUE;    -- for now
                                            newOrigin _ P4.LayoutArgs[rSei, origin, body];
                                            seb[rSei].length _ (newOrigin - origin)*bitsPerAU;
                                            seb[rSei].mark4 _ TRUE;
                                            origin _ newOrigin};
                                        IF OpName[son[2]] # anyTC THEN {
                                            ScanList[son[2], DeclItem];  CheckDefaults[son[2]]};
                                        rSei _ ArgRecord[type.typeOut];
                                        IF rSei # RecordSENull THEN {
                                            seb[rSei].hints.comparable _ TRUE;    -- for now
                                            seb[rSei].length _
                                                (P4.LayoutArgs[rSei, origin, body]-origin)*bitsPerAU;
                                            seb[rSei].mark4 _ TRUE}
                                        };
                                    definition => NULL;
                                    union => {
                                        DeclItem[son[1]];
                                        IF attr1 AND type.controlled THEN AssignPositions[son[1]];
                                        ProcessVariants[UnderType[seb[type.tagSei].idType], son[2]]};
                                    sequence => {
                                        DeclItem[son[1]];
                                        IF attr1 AND type.controlled THEN AssignPositions[son[1]];
                                        TypeExp[son[2], FALSE, indirect]};
                                    relative => {TypeExp[son[1], FALSE, TRUE];  TypeExp[son[2], FALSE, TRUE]};
                                    opaque =>
                                        IF son[1] # Tree.Null THEN {
                                            son[1] _ P4.Rhs[son[1], dataPtr.idCARDINAL];  P4.VPop[];
                                            IF P4.TreeLiteral[son[1]] THEN
                                                type.length _ P4.TreeLiteralValue[son[1]]*bitsPerAU
                                            };
                                    zone => NULL;
                                    subrange => {
                                        subNode: Tree.Index;
                                        tSei: CSEIndex = UnderType[type.rangeType];
                                        TypeExp[son[1], FALSE, indirect];
                                        subNode _ GetNode[son[2]];
                                        IF P4.Interval[subNode, 0, P4.both] THEN
                                            [type.origin, type.range] _ P4.ConstantInterval[subNode
                                                ! P4.EmptyInterval => {type.empty _ TRUE; RESUME}]
                                        ELSE type.origin _ type.range _ 0;
                                        type.filled _ TRUE;
                                        SELECT P4.VRep[] FROM
                                            P4.none => Log.ErrorTree[mixedRepresentation, son[2]];
                                            P4.unsigned => IF type.origin < 0 THEN Log.Error[subrangeNesting];
                                            ENDCASE;
                                        P4.VPop[];
                                        WITH cover: seb[tSei] SELECT FROM
                                            subrange =>    -- incomplete test
                                                IF  type.origin < cover.origin
                                                    OR (~type.empty AND type.range > cover.range) THEN
                                                        Log.Error[subrangeNesting];
                                            ENDCASE => NULL;
                                        son[2] _ FreeTree[son[2]]};
                                    long => TypeExp[son[1], FALSE, indirect];
                                    any => NULL;
                                    ENDCASE => ERROR;
                            seb[sei].mark4 _ TRUE}
                    };
                ENDCASE => ERROR};


    <<machine dependent representations>>

        MaxCardinality: PUBLIC PROC[type: Type, packed: BOOL, maxSize: CARD] RETURNS[CARD] = {
            maxBits: BitCount =
                (IF maxSize > BitCount.LAST/bitsPerAU THEN BitCount.LAST ELSE maxSize*bitsPerAU);
            eSize: BitCount = BitsPerElement[type, packed];
            RETURN[maxBits/(IF eSize # 0 THEN eSize ELSE 1)]};


        EvalUnsigned: PROC[t: Tree.Link, default: CARD] RETURNS [v: Tree.Link, n: CARD] = {
            v _ P4.Rhs[t, dataPtr.idCARDINAL];  P4.VPop[];
            IF P4.TreeLiteral[v] THEN n _ P4.TreeLiteralValue[v]
            ELSE {Log.ErrorTree[nonConstant, v]; n _ default};
            RETURN};


        LayoutEnum: PROC[t: Tree.Link, ctx: CTXIndex]
              RETURNS [empty: BOOL, range: CARD, sparse: BOOL] = {
            sei: ISEIndex;
            started: BOOL;
            last: CARD;

            AssignElement: Tree.Scan = {
                val: CARD;
                WITH t SELECT GetTag[t] FROM
                    subtree => {
                        node: Tree.Index = index;
                        [tb[node].son[2], val] _
                            EvalUnsigned[tb[node].son[2], IF started THEN last+1 ELSE 0]
                        };
                    ENDCASE => val _ IF started THEN last+1 ELSE 0;
                IF val > Target.maxWord THEN Log.ErrorSei[addressOverflow, sei];
                IF ~started THEN {sparse _ (val#0); started _ TRUE}
                ELSE {
                    IF val <= last THEN Log.ErrorSei[enumOrder, sei];
                    IF val # last+1 THEN sparse _ TRUE};
                last _ val;  seb[sei].idValue _ EncodeCard[val];  sei _ NextSe[sei]};

            started _ sparse _ FALSE; sei _ FirstCtxSe[ctx];
            ScanList[t, AssignElement];
            empty _ ~started;  range _ (IF empty THEN 0 ELSE last);  RETURN};


        AssignPositions: PROC[item: Tree.Link] = {
            node: Tree.Index = GetNode[item];
            saveIndex: SourceMap.Loc = dataPtr.textIndex;
            type: Type = TypeForTree[tb[node].son[2]];
            nB, nU: CARD;

            EncodeBitAddress: PROC[ud, bd: CARDINAL] RETURNS[BitAddress] = INLINE {
                RETURN[[bd: ud*bitsPerAU + bd]]};

            AssignPosition: Tree.Scan = {
                ud, bL, bR: CARD;
                dB: CARD = IF nB=0 THEN 0 ELSE nB-1;
                sei: ISEIndex = ItemId[t];
                node: Tree.Index = GetNode[NthSon[t, 2]];
                [tb[node].son[1], ud] _ EvalUnsigned[tb[node].son[1], 0];
                IF tb[node].son[2] = Tree.Null THEN {
                    bL _ 0;  bR _ (IF nB = 0 THEN 0 ELSE nU*bitsPerAU - 1)}
                ELSE {
                    subNode: Tree.Index = GetNode[tb[node].son[2]];
                    [tb[subNode].son[1], bL] _ EvalUnsigned[tb[subNode].son[1], 0];
                    [tb[subNode].son[2], bR] _ EvalUnsigned[tb[subNode].son[2], dB]};
                ud _ ud + bL/bitsPerAU;
                IF bR >= bL THEN bR _ bR - (bL/bitsPerAU)*bitsPerAU;
                bL _ bL MOD bitsPerAU;
                IF (SELECT TRUE FROM
                      (nB = 0) => bR < bL,
                      (nB >= bitsPerAU) => bL # 0 OR bR # bL + dB,
                      ENDCASE => bR > bitsPerAU OR bR < bL + dB) THEN {
                    Log.ErrorSei[fieldPosition, sei]; bR _ bL + dB};
                seb[sei].idValue _ EncodeBitAddr[EncodeBitAddress[ud:ud, bd:bL]];
                seb[sei].idInfo _
                    EncodeCard[IF nB=0 AND tb[node].son[2] = Tree.Null THEN 0 ELSE bR-bL + 1]
                };

            dataPtr.textIndex _ ToLoc[tb[node].info];
            nB _ P4.BitsForType[type];  nU _ (nB+(bitsPerAU-1))/bitsPerAU;
            ScanList[tb[node].son[1], AssignPosition];
            dataPtr.textIndex _ saveIndex};


        ExtractFieldAttributes: PROC[rType: RecordSEIndex] = {
            <<compatibility version>>
            type: CSEIndex;
            comparable, privateFields: BOOL;
            comparable _ TRUE;   privateFields _ FALSE;
            FOR sei: ISEIndex _ FirstCtxSe[seb[rType].fieldCtx], NextSe[sei] UNTIL sei = ISENull DO
                IF ~seb[sei].public THEN privateFields _ TRUE;
                type _ UnderType[seb[sei].idType];
                WITH t: seb[type] SELECT FROM
                    record =>
                        IF ~t.hints.comparable AND ~ComparableType[type] THEN comparable _ FALSE;
                    array => IF ~ComparableType[type] THEN comparable _ FALSE;
                    union => IF ~t.hints.equalLengths THEN comparable _ FALSE;
                    sequence => comparable _ FALSE;
                    ENDCASE;
                ENDLOOP;
            seb[rType].hints.comparable _ comparable;
            seb[rType].hints.privateFields _ privateFields};


        ProcessVariants: PROC[tagType: CSEIndex, list: Tree.Link] = {
            lb, ub: CARDINAL;

            MapTag: PROC[vSei: ISEIndex] RETURNS[CARDINAL] = {
                WITH t: seb[tagType] SELECT FROM
                    enumerated =>
                        IF t.machineDep THEN {
                            sei: ISEIndex = SearchContext[seb[vSei].hash, t.valueCtx];
                            IF sei # ISENull THEN RETURN[DecodeCard[seb[sei].idValue]]};
                    ENDCASE;
                RETURN[DecodeCard[seb[vSei].idValue]]};

            CheckTag: Tree.Scan = {
                sei: ISEIndex = ItemId[t];
                tag: CARDINAL = MapTag[sei];
                IF tag NOT IN [lb .. ub) THEN Log.ErrorSei[boundsFault, sei];
                seb[sei].idValue _ EncodeCard[tag - lb]};

            ProcessVariant: Tree.Scan = {
                saveIndex: SourceMap.Loc = dataPtr.textIndex;
                node: Tree.Index = GetNode[t];
                dataPtr.textIndex _ ToLoc[tb[node].info];
                ScanList[tb[node].son[1], CheckTag];
                DeclItem[t];
                dataPtr.textIndex _ saveIndex};

            lb _ BiasForType[tagType];  ub _ lb + CARDINAL[Cardinality[tagType]];
            ScanList[list, ProcessVariant]};


        TypeForTree: PUBLIC PROC[t: Tree.Link] RETURNS[Type] = {
            RETURN[WITH t SELECT GetTag[t] FROM
                symbol => index,
                subtree => ToType[tb[index].info],
                ENDCASE => typeANY]
            };



        CanonicalType: PUBLIC PROC[type: Type] RETURNS[Type] = {
            sei: CSEIndex = UnderType[type];
            RETURN[WITH t: seb[sei] SELECT FROM
                subrange => CanonicalType[t.rangeType],
                record =>
                    IF t.hints.unifield AND CtxEntries[t.fieldCtx] = 1
                        THEN CanonicalType[seb[ctxb[t.fieldCtx].seList].idType]
                        ELSE type,
                ENDCASE => type]
            };


        BiasForType: PUBLIC PROC[type: Type] RETURNS[INTEGER] = {
            sei: CSEIndex = UnderType[type];
            RETURN[IF sei = CSENull
                THEN 0
                ELSE
                    WITH t: seb[sei] SELECT FROM
                        subrange => INTEGER[t.origin],
                        record =>
                            IF t.hints.unifield AND CtxEntries[t.fieldCtx] = 1
                                THEN BiasForType[seb[ctxb[t.fieldCtx].seList].idType]
                                ELSE 0,
                        ENDCASE => 0]
            };

        RepForType: PUBLIC PROC[type: Type] RETURNS[P4.Repr] = {
            sei: CSEIndex = UnderType[type];
            RETURN[IF sei = CSENull
                THEN P4.none
                ELSE
                    WITH t: seb[sei] SELECT FROM
                        basic =>
                            SELECT t.code FROM
                                codeANY => P4.both + P4.other,
                                codeINT => P4.signed,
                                codeCHAR => P4.both,
                                ENDCASE => P4.other,
                        enumerated => P4.both,
                        ref => P4.unsigned,
                        record =>
                            IF t.hints.unifield AND CtxEntries[t.fieldCtx] = 1
                                THEN RepForType[seb[ctxb[t.fieldCtx].seList].idType]
                                ELSE P4.other,
                        relative => RepForType[t.offsetType],
                        subrange =>
                            IF t.origin >= 0
                                THEN (IF CARD[t.origin] + t.range > Target.maxWord/2
                                    THEN P4.unsigned ELSE P4.both)
                                ELSE (IF t.range <= Target.maxWord/2 THEN P4.signed ELSE P4.none),
                        long => RepForType[t.rangeType],
                        opaque => IF t.lengthKnown THEN P4.other ELSE P4.none,
                        ENDCASE => P4.other]
            };

        SparseRep: PUBLIC PROC[type: Type] RETURNS[BOOL] = {
            nType: CSEIndex = NormalType[type];
            RETURN[WITH t: seb[nType] SELECT FROM
                enumerated => t.sparse,
                ENDCASE => FALSE]
            };


        AUsForType: PUBLIC PROC[type: Type] RETURNS[CARD] = {
            RETURN[IF ~seb[type].mark4
                THEN (P4.BitsForType[type]+(bitsPerAU-1))/bitsPerAU
                ELSE SymbolOps.AUsForType[type]]
            };


        ComparableType: PUBLIC PROC[type: Type] RETURNS[BOOL] = {
            <<compatibility version>>
            sei: CSEIndex = UnderType[type];
            RETURN[WITH t: seb[sei] SELECT FROM
                record => t.hints.comparable OR t.argument,    -- for now
                array => ~SparseRep[t.indexType]
                    AND ComparableType[t.componentType]
                    AND AUsForType[sei] <= P4.OpWordCount.LAST,
                opaque => t.lengthKnown,
                any => FALSE,
                ENDCASE => TRUE]
            };

        DefaultBasicOps: PUBLIC PROC[type: Type, size: BitCount] RETURNS[BOOL] = {
            next: Type;
            FOR s: Type _ type, next DO
                WITH se: seb[s] SELECT FROM
                    id => {
                        sei: ISEIndex = LOOPHOLE[s];
                        IF seb[sei].extended THEN {
                            IF OpName[FindExtension[sei].tree] # void THEN RETURN[FALSE] ELSE EXIT};
                        next _ DecodeType[seb[sei].idInfo]};
                    cons =>
                        WITH t: se SELECT FROM
                            ref => IF t.counted THEN RETURN[FALSE] ELSE EXIT;
                            array => next _ t.componentType;
                            record => IF t.hints.default THEN RETURN[FALSE] ELSE EXIT;
                            transfer => IF t.mode = port THEN RETURN[FALSE] ELSE EXIT;
                            long => next _ t.rangeType;
                            zone => IF t.counted THEN RETURN[FALSE] ELSE EXIT;
                            ENDCASE => EXIT;
                    ENDCASE;
                ENDLOOP;
            RETURN[AUsForType[type]*bitsPerAU = size
                AND ComparableType[type] AND TypeLink[type] = nullType]};

        }.

