
<<file SMTree.mesa>>
<<Copyright  1985 by Xerox Corporation.  All rights reserved.>>
<<last edit by Satterthwaite, May 12, 1986 11:44:55 am PDT>>

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,
type: Link_null,
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, 3 = body
let,                -- LET binding IN exp                1 = binding, 2 = exp
arrow,             -- decl -> exp                        1 = domain decl, 2 = range
arrow2,             -- decl ->> exp                        1 = domain decl, 2 = range
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 = id, 2 = exp (or null)
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;
nullTest: Text~NIL;

Number: TYPE~REF INT;
nullNumber: Number~NIL;

Stamp: TYPE~REF TimeStamp.Stamp;
nullStamp: Stamp~NIL;

}.

