This document is a tutorial  for programmers.  It does not describe
the user  interface except  incidentally.  It also does not describe all
the gory details of  exactly what  is  possible.    It is  intended  for
someone who has  never written anything using the keytree matcher before
and wants to learn how.

     The keytree matcher functions by traversing an internal tree as the
user  types keys.   This tree is built by the  tree_match_parse routine;
the form of the specification  for the  tree  is given below.  You  will
never need to worry about the exact details of this tree representation.

     There  are  two  main routines:   tree_match_parse  and tree_match.
Tree_match_parse takes a tree specification and returns a pointer (which
you  should treat as  `char *')  to an internal  tree structure.    This
structure is messy and the details are irrelevant anyway; so it will not
be  described  here.     Tree_match   takes   the  pointer  returned  by
tree_match_parse (and a few other arguments, see below  for details) and
actually   performs   the   user   interaction.      You   should   call
tree_match_parse  only  once  for each keyword tree your  program  uses;
tree_match should be called whenever you want user interaction.

     The restrictions  on what characters  are  legal  in  keywords  are
fairly lax;  the  characters you cannot use are currently:

	whitespace (space, tab, newline) and control characters
	! " # % & ( ) : ? [ ]

     (This list may  change, but the letters  of both cases, the digits,
and  `_'  will always be legal, and it is hoped that - . / @ will remain
legal as well.)

     This leaves the letters, the digits, and

	$ ' * + , - . / ; < = > @ \ ^ _ ` { | } ~

     If you suspect  this list is not up-to-date, consult  Mouse or  the
parser source code.  Note:  The use of * as a  character in a keyword is
not recommended  as * has  a special meaning when typed  by the  user to
tree_match.  For similar reasons, @ (when at the beginning of a keyword)
is discouraged.

     The best way to understand the syntax of the tree specification for
tree_match_parse is probably  to  go through it gradually.  The simplest
form simply matches one keyword from a list (the list need not be in any
special order such  as  alphabetic).   In all these  examples, the  last
argument passed  to  tree_match_parse  is a zero.  On the Suns,  this is
necessary due to braindamage  in  the 68000 calling  sequence (a routine
cannot find out how many actual parameters were passed, so we need  some
way of indicating the  end of the argument list); on the VAXen, this  is
unnecessary but harmless (so put it in, portability never hurt anybody).
Why do we need  to see how  many arguments are passed?  Read  on....  If
you are working on a Sun and you get a parse error and tree_match_err_at
(explained later) returns something that  you have  never seen before in
your life, you have probably forgotten the terminating zero.

	char *tree;
	char *tree_match_parse();

	....

	tree = tree_match_parse("(quit display read write negate)",0);

     This example  allows the user to enter one  of the keywords "quit",
"display",  "read", "write", or "negate" (when tree_match  is called).  
(Which  one  is  actually  entered  can  be  determined  from  a  string
tree_match takes as an argument  and modifies  -- see the description of
tree_match.)

     Don't worry about  the parentheses  around  the keywords --  you'll
soon see why they're there.

     Now to  the next  step.    Suppose you want to  display one of  two
things:  an image or a mask.  Then we might have:

	tree = tree_match_parse("( .... display (image mask) .... )",0);

which allows the  user to enter "display image" and "display mask"  (but
not just "display" -- in this case,  tree_match will wait  for  "image",
"mask", or the deletion of "display").   Now you may see the  reason for
the parentheses at the top level  -- it's partly to make the syntax more
consistent and partly to allow multiple top-level trees to be defined in
one call  to tree_match_parse.   How  can that be when  tree_match_parse
returns only one pointer?  You'll see.

     Let's  suppose you want several keywords all with the same subtree.
You can do something like

	.... [set show] ( ... ) ....
			   ^
			   | The keywords specifying what to
			     set or show go in here.

     More generally, you  can have  any  number of keywords in []s; they
are all  equivalent (and  if a  subtree is specified, they will all have
that same subtree).

     Now let's  suppose  you  want  not  a  keyword but a  number.   For
example, you want  to  be  able to  set  a variable called 'sigma' to  a
floating-point value.  Then you can say something like this:

	tree = tree_match_parse("( ... set (sigma (%r",&sigma,")) ... )",0);

     (Yes, that means more arguments to tree_match_parse.)

     Then the  user can  enter "set sigma  3.5"  (for  example), and the
variable sigma will be  set to 3.5 and the returned string  will contain
"set  sigma"  (with the  "3.5"  deleted).   There are three points which
should be  made  now:   (1) You must pass the  address  of  the variable
(sigma in this  case).  (2) The keyword is  called "sigma" and so is the
variable.  This is entirely  "accidental"; the  keytree matcher does not
have  access to the name  of the  variable passed to  it!    (3)  If the
variable (sigma  here) is automatic  (ie,  neither  declared static  nor
declared outside  of all  routines  in a file), then the flow-of-control
must never leave the block  in  which it is declared between the call to
tree_match_parse and the call  to  tree_match.  Otherwise,  the  matcher
will  probably  lose the variable and  wind  up writing to  some  random
location in the stack somewhere.  This can cause almost any sort of bug.

     It is possible to  enter an integer  (use %i instead  of  %r) or  a
string (use %s and pass a pointer to char; this normally is done without
an & sign, as  in  the  next example).    By  the  way, %f is completely
equivalent to  %r;  this is done to be  more  mnemonic (in  C, reals are
called "float").

     On numbers (ie, %i and %r) you can  put  limits (upper,  lower,  or
both).  For example,

	char filename[256];
	int count;

	tree = tree_match_parse("(... set (\
count (%i",&count,",0,10)\
file (%s",filename,") ...) ...)",0);

     This example looks a  little involved, because the string arguments
to tree_match_parse are  split  over three lines.  The  backslash at the
end  of the first two lines is C  syntax  for  continuing a string;  the
backslash and the following newline are both ignored when  the string is
compiled.  The 0 and  10  tell the matcher  that count is to be a number
from 0 to 10 inclusive.  If you want a lower limit with no upper  limit,
use something like (%i",&count,",0)  which specifies  a lower limit of 0
and  no upper  limit.  If you want an upper limit without a lower limit,
you can use  something like  (%i",&count,",,10)  which means  any number
less than or equal to 10 (including negative  numbers).   Unfortunately,
exponential notation  for reals  is not supported (either here or at the
user level).  This is hopefully not a serious problem, since  user input
should  usually be  scaled to be on the order  of 1  anyway.  Strings of
course cannot have ranges.  There is a minor lossage here in that ranges
of  the  form  "...greater(less)  than but  not  equal  to..."  are  not
supported; this may get put in if there is enough need for it.

     Limits can take the form %",&variable," to make the limit the value
of a variable.  For example:

	... count (%i",&count,",1,%",&max_count,") ...

In this case, there is no type specification letter since the limit must
be of the same type as the main keyword.

     TREE NAMES

     A tree of keywords can have a name.  This name can contain letters,
digits, $, and  _ and  nothing  else (note this is  not the same set  of
characters as are legal in keywords).  This should not be so restrictive
as the name of  a tree is never  visible  to  the user;  it is used only
internally.  What good is this, you ask?   Well, it allows the same tree
to be used several places.  For example,

	tree_match_parse("(onoff: yes no on off)\
			  (...set (dashes !onoff\
				   crosses !onoff)\
				...)",0);

which gives the tree  with  just four keywords (yes, no, on, off) a name
"onoff".  This  name is then used to allow  this same tree to be used as
the  subtree for  both "set  dashes" and  "set  crosses".    The  `!' is
necessary syntax when specifying a tree name as a subtree (rather than a
parenthesized list of keywords, which is the usual way  of  specifying a
subtree).

     Now, let's suppose that you wanted to use the above "onoff" tree in
a lot of places, but a couple of places you wanted yes, no, on, off, and
a couple of others (say "long" and "short").  Well, try this:

	....set (dashes (long short &onoff) ...) ....

where the &onoff means "expand the top level of tree onoff here".

     CONDITIONALS

     Let's suppose you want to read an even  number.  This is impossible
to do with what's been mentioned so far.  What you have  to do  is write
an int function (let's say it's called "ifeven") which returns true (ie,
non-zero) when its argument  is even.    Then  to read  the  number into
even_var, telling  the matcher to  accept only  those  numbers for which
"ifeven" returns true

	.... (%i",&even_var," ?",ifeven,") ....

     The specified routine  will  be called with either  no arguments or
one argument,  depending on the  keyword it is performing checking  for.
If the key  type is %i, the argument will be an int.  If  it is %r,  the
argument type will be a float.  If it is %s, the argument type will be a
pointer to char,  pointing to the (null-terminated)  string.  If it is a
vanilla keyword, no argument will necessarily be passed.

     The  routine  named in  a conditional should obey some conventions.
It must not  matter if  the routine  is called  at  odd times;  you must
assume that it could get called  at any point within tree_match.  If the
routine is not stable, in that its return value depends on  other things
than its  argument, whether or not the  keyword  is  recognized  can  be
unpredictable.

     There is  another syntax for  specifying keywords.  It is the  most
general, in that  with this,  you  can  give  *any*  keyword  you  want.
However, this can be a mixed blessing.  Well, here it is:

	.... %v",charbuf," ....

where charbuf is a  char pointer which  points to  the (null-terminated)
keyword.  This string can then change and tree_match's idea of what that
keyword is  will change with  it.   Note:   It is  possible to  set this
string to some values  which will prevent tree_match from ever matching.
For  example, if the  first  character is  a  `*' or `?', the  user will
(almost) never be able to make tree_match match it.

     ARGUMENTS AND DEFINITIONS

     The  argument(s)   to   tree_match_parse  were   covered  above.   
Tree_match_parse returns a pointer, which you should treat  as a pointer
to char.  If this pointer is 0,  the parse of the  tree failed for  some
reason; the  call tree_match_err_at (a char * function  of no arguments)
returns a pointer  into the parse string at the point at which the error
occurred.  A  note which may help you  read this parse string:  This  is
built from  the arguments  to tree_match_parse by  concatenating all the
strings,  with the variable and function arguments converted  to numbers
for the parse.

     As mentioned above, under the # syntax (see  the section on ANCIENT
FORMS), tree_match may take more than three arguments, though  it always
takes at least three.  The three constant arguments are the first three;
they are:

	tree_match(tree,prompt,buf)
	char *tree;
	char *prompt;
	char *buf;

where tree is the pointer returned by tree_match_parse,  prompt  is  the
prompt  to  be issued, and  buf  is a buffer  which will  be used  as  a
temporary buffer for all user interaction; when  tree_match returns, buf
will  contain   the  user's  input.    This   returned  input   will  be
null-terminated and will have had all variable keyword text (%i, %r, %s,
#i, #r, #s,  but not  %v) removed  from  it.  Tree_match returns nothing
useful.

     ANCIENT FORMS

     There  is another  syntax, maintained  for compatibility  with  the
version  running on Moe,  for reading  variables.  You can say something
like

	.... (#i1) ....

to read an integer.  Then when  you call tree_match, you must have extra
arguments.  For example, if a usual call to tree_match would read

	tree_match(tree,">> ",input);

then you could do

	tree_match(tree,">> ",input,&int_var)

which would cause the #i1 to refer to int_var.  The 1 means that this is
to be the first  "extra"  argument  to tree_match.  This is not terribly
useful unless  you want to  change  which  variable is  to be read  into
dynamically.  It is somewhat harder to read the code, since the variable
is seperated from the tree spec, but it's there in case you need it.

     RESTRICTIONS

     Tree_match_parse  calls  malloc() and realloc() to  allocate memory
for the tree; hence if you  provide  your  own  malloc() (overriding the
system  default  malloc()) it  must  perform  the same function  as  the
standard malloc() (see malloc(3)).  The same is true of realloc().

     The only available forms for reading numbers are the i and r (or f)
types.  If you want something else, it's up to you to build it.  This is
feasible,  using  %s to accept a string  and a conditional routine  (see
CONDITIONALS) to parse it and  reject  it  if it is  non-syntactic  (and
incidentally remember the  result  of  the last  parse  for tree_match's
caller to use).

					der Mouse