-- file Tree.Mesa
-- last modified by Satterthwaite, October 30, 1979  3:33 PM

DIRECTORY
  Table: FROM "table" USING [Base, Finger, Selector, Limit, chunkType],
  Literals: FROM "literals" USING [LitRecord],
  Symbols: FROM "symbols" USING [HTIndex, ISEIndex, HTNull];

Tree: DEFINITIONS =
  BEGIN

  treeType: Table.Selector = Table.chunkType;

 -- data structures

  Link: TYPE = RECORD [
    SELECT tag: * FROM
      subtree => [index: Tree.Index],
      hash => [index: Symbols.HTIndex],
      symbol => [index: Symbols.ISEIndex],
      literal => [info: Literals.LitRecord],
      ENDCASE];


  Node: TYPE = MACHINE DEPENDENT RECORD [
    free: BOOLEAN,	-- reserved for allocator
    name: NodeName,
    attr3: BOOLEAN,
    shared: BOOLEAN,
    attr1, attr2: BOOLEAN,
    nSons: [0..MaxNSons],
    info: UNSPECIFIED,
    son: ARRAY [1..1) OF Tree.Link];

  MaxNSons: CARDINAL = 7;

  Index: TYPE = Table.Base RELATIVE POINTER [0..Table.Limit) TO Tree.Node;

  NullIndex: Tree.Index = FIRST[Tree.Index];
  Null: Tree.Link = [subtree[index: Tree.NullIndex]];

  NullId: Tree.Link = [hash[index: Symbols.HTNull]];


  NodeName: TYPE = {
   -- general tree constructors
    list, item,

   -- declarations
    decl, typedecl,
    basicTC, enumeratedTC, recordTC, monitoredTC, variantTC,
    pointerTC, arrayTC, arraydescTC,
    procTC, processTC, portTC, signalTC, errorTC, programTC,
    definitionTC, unionTC, relativeTC,
    subrangeTC, longTC, virtualTC,
    implicitTC, frameTC, discrimTC,
    entry, internal,
    unit, diritem, module, body, inline, lambda, block,

  -- statements
    assign, extract,
    if,
    case, casetest, caseswitch,
    bind,
    do, forseq, upthru, downthru,
    return, result,
    goto, exit, loop,
    resume, continue, retry, catchmark,
    restart, stop,
    lock, wait, notify, broadcast, unlock,
    null,
    label,
    open,
    enable, catch,
    dst, lst, lstf,
    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,
    substx,
    ifx, casex, bindx,
    assignx,
    or,
    and,
    relE, relN, relL, relGE, relG, relLE, in, notin,
    plus, minus,
    times, div, mod,
    dot, cdot, dollar,
    new,
    not,
    uminus,
    addr,
    uparrow,
    min, max, lengthen, abs, all,
    size, first, last,
    arraydesc, length, base,
    loophole,
    void,
    clit, llit,
    cast, check, float, pad, chop, safen,
    openx,
    mwconst,
    typecode,
    stringinit, signalinit, portinit, procinit,
    intOO, intOC, intCO, intCC,

    thread,
    none,

    syscall, syscallx,
    exlist
    };
    
 -- tree manipulation

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

  END.