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 BOOLALL[FALSE],
visited: BOOLFALSE, -- 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𡤀 -- 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: BOOLFALSE -- 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;
}.