
DIRECTORY
Literals USING [LTIndex, ltTag, STIndex, stTag],
Symbols USING [htTag, ISEIndex, Name, nullName, seTag],
Table USING [Base, chunkType, Finger, HighBits, lowBitHi, lowBitLo, LowBits, restBitHi, restBitLo, Selector, Tag, tagBitHi, tagBitLo];

Tree: DEFINITIONS = {
OPEN Table;
treeType: Table.Selector = Table.chunkType;
treeTag: Table.Tag = 0;

Base: TYPE = Table.Base;
Finger: TYPE = Table.Finger;


LinkTag: TYPE = MACHINE DEPENDENT {
subtree	(treeTag),
hash	(Symbols.htTag),
symbol	(Symbols.seTag),
literal	(Literals.ltTag),
string	(Literals.stTag)};

Link: TYPE = RECORD [
SELECT COMPUTED LinkTag FROM
subtree => [index: Tree.Index],
hash => [index: Symbols.Name],
symbol => [index: Symbols.ISEIndex],
literal => [index: Literals.LTIndex],
string => [index: Literals.STIndex],
ENDCASE];

LinkRep: TYPE = MACHINE DEPENDENT RECORD [
tag (0: tagBitLo..tagBitHi): LinkTag ¬ subtree,
highBits (0: restBitLo..restBitHi): HighBits ¬ HighBits.LAST,
lowBits (0: lowBitLo..lowBitHi): LowBits ¬ LowBits.LAST];

NodePtr: TYPE = LONG POINTER TO Node;
Node: TYPE = MACHINE DEPENDENT RECORD [
free (0: 0..0): BOOL,	-- reserved for allocator
name (0: 1..8): NodeName,
attr1 (0: 9..9), attr2 (0: 10..10), attr3 (0: 11..11): BOOL,
subInfo (0: 12..15): SubInfo,
shared (0: 16..16): BOOL,
nSons (0: 17..31): NAT15,
info (0: 32..63): Info,
son (64/BITS[WORD]): SEQUENCE COMPUTED SonId OF Tree.Link];

SubInfo: TYPE = [0..15];

packedOption: SubInfo	= 1;
msbitOption: SubInfo	= 2;
lsbitOption: SubInfo	= 3;
nativeOption: SubInfo	= 4;
word8Option: SubInfo	= 5;
word16Option: SubInfo	= 6;
word32Option: SubInfo	= 7;
word64Option: SubInfo	= 8;

SonId: TYPE = [1..NAT.LAST);

Info: TYPE [SIZE[CARD]];		-- no exporter, conversions by LOOPHOLEs
AttrId: TYPE = [1..3];

Index: TYPE = Base RELATIVE LONG POINTER TO Tree.Node;

firstIndex: Tree.Index = LOOPHOLE[Tree.LinkRep[tag: subtree, highBits: 0, lowBits: 0]];
nullIndex: Tree.Index = firstIndex;

Null: Tree.Link = [subtree[index: Tree.nullIndex]];
nullId: Tree.Link = [hash[index: Symbols.nullName]];

nullInfo: Info = LOOPHOLE[CARD[0]];

NodeName: TYPE = MACHINE DEPENDENT {
list (0), item (1),

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, optionTC, spareTC,
unit, diritem, module, body, inline, lambda, block,

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,

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, power,
dot, cdot, dollar,
create,
not,
uminus,
addr,
uparrow,
min, max, ord, val, 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,

lengthen, shorten,
self,
gcrt, proccheck,

entry, internal,

invalid};


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

}.

   Ž  
Tree.mesa
Copyright Ó 1985, 1986, 1987, 1988, 1991 by Xerox Corporation.  All rights reserved.
Satterthwaite, June 18, 1986 12:17:23 pm PDT
Russ Atkinson (RRA) August 30, 1988 4:22:25 am PDT
data structures
(must be compatible with Table.IndexRep)
The following values for SubInfo are used in the optionTC case
general tree constructors
declarations
statements
expressions
tree manipulation
Ê  –(cedarcode) style•NewlineDelimiter
™ codešœ	™	Kšœ
ÏeœI™TKšÏy,™,J™2—˜ šÏk	˜	Kšœ	Ÿœ"˜0KšœŸœ*˜7KšœŸœ{˜†K˜ ——headšÏnœŸœ˜KšŸœ˜K˜+K˜K˜ KšœŸœ˜KšœŸœ˜K˜ —Kšœ™˜ šœ	ŸœŸœŸ	œ˜#Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜—K˜ šœŸœŸœ˜šŸœŸœ	Ÿ˜K˜K˜K˜$Kšœ%˜%Kšœ$˜$KšŸœ˜	—K˜ —š	œ	ŸœŸœŸ	œŸœ˜*Kšœ(™(Kšœ/˜/Kšœ8Ÿœ˜=Kšœ3Ÿœ˜9K˜ —Kš	œ	ŸœŸœŸœŸœ˜%š	œŸœŸœŸ	œŸœ˜'KšœŸœÏc˜/K˜Kšœ7Ÿœ˜<Kšœ˜KšœŸœ˜KšœŸœ˜Kšœ˜KšœŸœŸœŸœŸœŸœ˜;K˜ —šœ	Ÿœ˜K˜ Kšœ>™>Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜K˜ —KšœŸœŸœŸœ˜K˜ KšœŸœŸœŸœ¡(˜BKšœŸœ
˜K˜ Kš	œŸœŸœŸœŸœ˜6K˜ KšœŸœ6˜WKšœ#˜#K˜ K˜3K˜4K˜ KšœŸœŸœ˜#K˜ šœ
ŸœŸœŸ	œ˜$šœ™K˜K˜ —šœ™K˜K˜8K˜;K˜8K˜)K˜4K˜K˜K˜3K˜ —šœ
™
K˜K˜K˜K˜K˜K˜K˜K˜K˜+K˜K˜&K˜K˜K˜K˜K˜K˜K˜7K˜K˜ —šœ™K˜K˜BK˜K˜.K˜K˜K˜K˜K˜0K˜$K˜K˜K˜K˜K˜K˜K˜K˜K˜K˜	K˜K˜K˜K˜K˜%K˜K˜K˜K˜K˜*K˜K˜ K˜K˜K˜ K˜K˜	K˜K˜ K˜K˜K˜K˜ K˜K˜ K˜	K˜ ———Kšœ™˜ KšœŸœŸœ'˜8Kš œŸœŸœ˜!Kš œŸœŸœŸœ˜7Kš
 œŸœŸœŸœŸœ˜0K˜ K˜K˜ —— …—    "  1  