
    <<Tree.mesa>>
        <<Copyright  1985 by Xerox Corporation.  All rights reserved.>>
        <<Satterthwaite, June 18, 1986 12:17:23 pm PDT>>
    <<Russ Atkinson (RRA) January 31, 1985 1:03:04 pm PST>>

    DIRECTORY
        Table: TYPE USING [Base, Finger, IndexRep, Selector, Tag, chunkType],
        Literals: TYPE USING [LTIndex, STIndex, ltTag, stTag],
        Symbols: TYPE USING [ISEIndex, Name, htTag, seTag, nullName];

    Tree: DEFINITIONS = {

        treeType: Table.Selector = Table.chunkType;
        treeTag: Table.Tag = 0;

        Base: TYPE = Table.Base;
        Finger: TYPE = Table.Finger;

    <<data structures>>

        LinkTag: TYPE = MACHINE DEPENDENT {
            subtree    (treeTag),
            hash    (Symbols.htTag),
            symbol    (Symbols.seTag),
            literal    (Literals.ltTag),
            string    (Literals.stTag)};

        Link: TYPE = RECORD [
            SELECT COMPUTED LinkTag FROM
                subtree => [index: Tree.Index],
                hash => [index: Symbols.Name],
                symbol => [index: Symbols.ISEIndex],
                literal => [index: Literals.LTIndex],
                string => [index: Literals.STIndex],
                ENDCASE];
        LinkRep: TYPE = Table.IndexRep;


        Node: TYPE = MACHINE DEPENDENT RECORD [
            free (0: 0..0): BOOL,        -- reserved for allocator
            name (0: 1..8): Tree.NodeName,
            attr1 (0: 9..9), attr2 (0: 10..10), attr3 (0: 11..11): BOOL,
            shared (0: 12..15): BOOL,
            nSons (1): NAT,
            info (2): Tree.Info,
            son (4): SEQUENCE COMPUTED [1..NAT.LAST] OF Tree.Link];

        SonId: TYPE = [1..NAT.LAST);

        Info: TYPE [SIZE[CARD]];        -- no exporter, conversions by LOOPHOLEs
        AttrId: TYPE = [1..3];

        Index: TYPE = Base RELATIVE LONG POINTER TO Tree.Node;

        firstIndex: Tree.Index = LOOPHOLE[Table.IndexRep[tag: treeTag, highBits: 0, lowBits: 0]];
        nullIndex: Tree.Index = firstIndex;

        Null: Tree.Link = [subtree[index: Tree.nullIndex]];
        nullId: Tree.Link = [hash[index: Symbols.nullName]];

        nullInfo: Info = LOOPHOLE[CARD[0]];


        NodeName: TYPE = {
            <<general tree constructors>>
                list, item,

            <<declarations>>
                decl, typedecl,
                basicTC, enumeratedTC, recordTC, monitoredTC, variantTC,
                refTC, pointerTC, listTC, arrayTC, arraydescTC, sequenceTC,
                procTC, processTC, portTC, signalTC, errorTC, programTC,
                anyTC, definitionTC, unionTC, relativeTC,
                subrangeTC, longTC, opaqueTC, zoneTC, linkTC, varTC,
                implicitTC, frameTC, discrimTC,
                paintTC, spareTC,
                unit, diritem, module, body, inline, lambda, block,

            <<statements>>
                assign, extract,
                if,
                case, casetest, caseswitch,
                bind,
                do, forseq, upthru, downthru,
                return, result,
                goto, exit, loop,
                free,
                resume, reject, continue, retry, catchmark,
                restart, stop,
                lock, wait, notify, broadcast, unlock,
                null,
                label,
                open,
                enable, catch,
                dst, lste, lstf,
                syscall, checked, lst, spareS3,
                subst, call, portcall, signal, error, syserror, xerror,
                start, join,

            <<expressions>>
                apply,
                callx, portcallx, signalx, errorx, syserrorx, startx, fork, joinx,
                index, dindex, seqindex, reloc,
                construct, union, rowcons, sequence, listcons,
                substx,
                ifx, casex, bindx,
                assignx, extractx,
                or, and,
                relE, relN, relL, relGE, relG, relLE, in, notin,
                plus, minus, times, div, mod,
                dot, cdot, dollar,
                create,
                not,
                uminus,
                addr,
                uparrow,
                min, max, lengthen, abs, all,
                size, first, last, pred, succ,
                arraydesc, length, base,
                loophole,
                nil,
                new,
                void,
                clit, llit,
                cast, check, float, pad, chop, safen,
                syscallx, narrow, istype,
                openx,
                mwconst, cons,
                atom, typecode,
                stringinit, textlit, signalinit, procinit,
                intOO, intOC, intCO, intCC,

                thread,
                none,

                exlist,
                initlist,
                ditem,

                shorten,
                self,
                gcrt, proccheck,

                ord, val,

                entry, internal,

                mergecons};

    <<tree manipulation>>

        Id: TYPE = RECORD [baseP: Tree.Finger, link: Tree.Link];
        Scan: TYPE = PROC [t: Tree.Link];
        Map: TYPE = PROC [t: Tree.Link] RETURNS [v: Tree.Link];
        Test: TYPE = PROC [t: Tree.Link] RETURNS [BOOL];

        }.

