-- file SMTree.mesa
-- last modified by Satterthwaite, August 11, 1983 1:09 pm
-- last edit by Schmidt,  June 11, 1982 3:01 pm

DIRECTORY
  Rope: TYPE USING [Text],
  TimeStamp: TYPE USING [Stamp];
	
Tree: CEDAR DEFINITIONS~{

 -- data structures

  Link: TYPE~REF ANY;
  null: Link~NIL;

  Node: TYPE~RECORD[
    name: NodeName,
    attrs: PACKED ARRAY AttrId OF BOOL←ALL[FALSE],
    visited: BOOL←FALSE,		-- flips parity in (non-reentrant) tree walks
    info: Info,
    ext: Ext←nullExt,
    son: SEQUENCE sonLimit: [1..maxNSons] OF Link];

  maxNSons: PRIVATE NAT~NAT.LAST;
  SonId: TYPE~[1..maxNSons);

  AttrId: TYPE~[1..3];

  Info: TYPE~INT←0;		-- stream index
  
  Ext: TYPE~REF ANY;
  nullExt: Ext~NIL;
  
  Handle: TYPE~REF Node;
  nullHandle: Handle~NIL;

  NodeName: TYPE~{
    none,
    lambda,		-- LAMBDA decl => exp IN exp	1 = domain decl, 2 = range exp, 3 = exp
    let,		-- LET binding IN exp		1 = binding, 2 = exp
    arrow,		-- decl -> exp			1 = domain decl, 2 = range decl
    apply,		-- exp exp				1 = rator exp, 2 = rand exp
    applyDefault,	-- exp * exp				1 = rator exp, 2 = rand exp
    subscript,		-- exp . id				1 = exp, 2 = id
    union,		-- exp + exp				1, 2 = exp
    then,		-- exp THEN exp			1, 2 = exp
    exclusion,	-- exp - exp				1, 2 = exp
    restriction,	-- exp ↑ exp				1, 2 = exp
    splitUpper,	-- exp \ exp				1, 2 = exp
    splitLower,	-- exp / exp				1, 2 = exp
    group,		-- [ exp's ]				1, ..., n = exp
    decl,		-- [ declElem's ]			1, ..., n = declElem
    declElem,		-- name: exp				1 = id, 2 = exp (or null)
    bind,		-- [ bindElem's ]			1, ..., n = bindElem
    bindRec,		-- REC [ bindElem's ]		1, ..., n = bindElem
    bindElem,	-- decl ~ exp			1 = decl, 2 = exp
    type,		-- TYPE id				1 = name
    env,		-- ENV
    nil,		-- NIL
    control,		-- CONTROL
    unitId,		-- host dirlist namelist ! version	1 = host, 2 = dirlist, 
			--					3 = namelist, 4 = version
    uiList,		-- namelist				1, ..., name/unquote
    unQuote,		-- name ↑				1 = name

    typeTYPE,	-- (internal)
    typeDECL,	-- (internal)
    typeBINDING,	-- (internal)
    typePATTERN,	-- (internal)
    typeSTRING,	-- STRING
        
    nBind,		-- normalized bind (internal)	1 = decl, 2 = group or let
    nBindRec,	-- normalized bindRec (ditto)	1 = decl, 2 = group or let

    stamp,		-- (version stamp, internal)	1 = bcd version stamp
    cross,		-- cross type (internal)		1, 2 = type
    cross2,		-- cross cross type (internal)	1 = decl, 2 = type            

    locator		-- transparent (to hold source loc of terminal)
    };
    
  ApplOp: TYPE~NodeName[$apply..$applyDefault];
  BindOp: TYPE~NodeName[$nBind..$nBindRec];

   
 -- terminals

  Leaf: TYPE~REF ANY;		-- union of types below

  Name: TYPE~ATOM;
    nullName: Name~NIL;


  Id: TYPE~REF IdInfo;
    nullId: Id~NIL;
  IdInfo: TYPE~RECORD[
    db: Tree.Handle←,			-- decl or binding
    p: NAT←,					-- position in db
    mark1, mark2: BOOL←FALSE		-- for traversal, etc.
    ];
  

 -- literals

  Text: TYPE~Rope.Text;
    nullText: Text~NIL;  
  
  Number: TYPE~REF INT;
    nullNumber: Number~NIL;
    
  Stamp: TYPE~REF TimeStamp.Stamp;
    nullStamp: Stamp~NIL;

  }.