-- file Tree.mesa
-- last modified by Satterthwaite, February 17, 1983 3:08 pm

DIRECTORY
  Table: TYPE USING [Base, Finger, Selector, Limit, chunkType],
  Literals: TYPE USING [LitIndex],
  Symbols: TYPE USING [ISEIndex, Name, nullName];

Tree: DEFINITIONS = {

  treeType: Table.Selector = Table.chunkType;

  Base: TYPE = Table.Base;
  Finger: TYPE = Table.Finger;
  Limit: CARDINAL = Table.Limit;
  
 -- data structures

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


  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..12): BOOL,
    nSons (0: 13..15): [0..maxNSons],
    info (1): Tree.Info,
    son (2): ARRAY [1..1) OF Tree.Link];

  Info: TYPE = UNSPECIFIED;
  AttrId: TYPE = [1..3];
  
  maxNSons: NAT = 7;

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

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

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


  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];

  }.