demos/expr/expr.c

   1 /* mpexpr_evaluate -- shared code for simple expression evaluation
   2
   3 Copyright 2000, 2001, 2002, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  19
  20 #include <ctype.h>
  21 #include <stdio.h>
  22 #include <string.h>
  23
  24 #include "gmp.h"
  25 #include "expr-impl.h"
  26
  27
  28 /* Change this to "#define TRACE(x) x" to get some traces.  The trace
  29    printfs junk up the code a bit, but it's very hard to tell what's going
  30    on without them.  Set MPX_TRACE to a suitable output function for the
  31    mpz/mpq/mpf being run (if you have the wrong trace function it'll
  32    probably segv).  */
  33
  34 #define TRACE(x)
  35 #define MPX_TRACE  mpz_trace
  36
  37
  38 /* A few helper macros copied from gmp-impl.h */
  39 #define ALLOCATE_FUNC_TYPE(n,type) \
  40   ((type *) (*allocate_func) ((n) * sizeof (type)))
  41 #define ALLOCATE_FUNC_LIMBS(n)   ALLOCATE_FUNC_TYPE (n, mp_limb_t)
  42 #define REALLOCATE_FUNC_TYPE(p, old_size, new_size, type) \
  43   ((type *) (*reallocate_func)                            \
  44    (p, (old_size) * sizeof (type), (new_size) * sizeof (type)))
  45 #define REALLOCATE_FUNC_LIMBS(p, old_size, new_size) \
  46   REALLOCATE_FUNC_TYPE(p, old_size, new_size, mp_limb_t)
  47 #define FREE_FUNC_TYPE(p,n,type) (*free_func) (p, (n) * sizeof (type))
  48 #define FREE_FUNC_LIMBS(p,n)     FREE_FUNC_TYPE (p, n, mp_limb_t)
  49 #define ASSERT(x)
  50
  51
  52
  53 /* All the error strings are just for diagnostic traces.  Only the error
  54    code is actually returned.  */
  55 #define ERROR(str,code)                 \
  56   {                                     \
  57     TRACE (printf ("%s\n", str));       \
  58     p->error_code = (code);             \
  59     goto done;                          \
  60   }
  61
  62
  63 #define REALLOC(ptr, alloc, incr, type)                         \
  64   do {                                                          \
  65     int  new_alloc = (alloc) + (incr);                          \
  66     ptr = REALLOCATE_FUNC_TYPE (ptr, alloc, new_alloc, type);   \
  67     (alloc) = new_alloc;                                        \
  68   } while (0)
  69
  70
  71 /* data stack top element */
  72 #define SP   (p->data_stack + p->data_top)
  73
  74 /* Make sure there's room for another data element above current top.
  75    reallocate_func is fetched for when this macro is used in lookahead(). */
  76 #define DATA_SPACE()                                                    \
  77   do {                                                                  \
  78     if (p->data_top + 1 >= p->data_alloc)                               \
  79       {                                                                 \
  80         void *(*reallocate_func) (void *, size_t, size_t);              \
  81         mp_get_memory_functions (NULL, &reallocate_func, NULL);         \
  82         TRACE (printf ("grow stack from %d\n", p->data_alloc));         \
  83         REALLOC (p->data_stack, p->data_alloc, 20, union mpX_t);        \
  84       }                                                                 \
  85     ASSERT (p->data_top + 1 <= p->data_inited);                         \
  86     if (p->data_top + 1 == p->data_inited)                              \
  87       {                                                                 \
  88         TRACE (printf ("initialize %d\n", p->data_top + 1));            \
  89         (*p->mpX_init) (&p->data_stack[p->data_top + 1], p->prec);      \
  90         p->data_inited++;                                               \
  91       }                                                                 \
  92   } while (0)
  93
  94 #define DATA_PUSH()                             \
  95   do {                                          \
  96     p->data_top++;                              \
  97     ASSERT (p->data_top < p->data_alloc);       \
  98     ASSERT (p->data_top < p->data_inited);      \
  99   } while (0)
 100
 101 /* the last stack entry is never popped, so top>=0 will be true */
 102 #define DATA_POP(n)             \
 103   do {                          \
 104     p->data_top -= (n);         \
 105     ASSERT (p->data_top >= 0);  \
 106   } while (0)
 107
 108
 109 /* lookahead() parses the next token.  Return 1 if successful, with some
 110    extra data.  Return 0 if fail, with reason in p->error_code.
 111
 112    "prefix" is MPEXPR_TYPE_PREFIX if an operator with that attribute is
 113    preferred, or 0 if an operator without is preferred. */
 114
 115 #define TOKEN_EOF         -1   /* no extra data */
 116 #define TOKEN_VALUE       -2   /* pushed onto data stack */
 117 #define TOKEN_OPERATOR    -3   /* stored in p->token_op */
 118 #define TOKEN_FUNCTION    -4   /* stored in p->token_op */
 119
 120 #define TOKEN_NAME(n)                           \
 121   ((n) == TOKEN_EOF ? "TOKEN_EOF"               \
 122    : (n) == TOKEN_VALUE ? "TOKEN_VALUE"         \
 123    : (n) == TOKEN_OPERATOR ? "TOKEN_OPERATOR"   \
 124    : (n) == TOKEN_VALUE ? "TOKEN_FUNCTION"      \
 125    : "UNKNOWN TOKEN")
 126
 127 /* Functions default to being parsed as whole words, operators to match just
 128    at the start of the string.  The type flags override this. */
 129 #define WHOLEWORD(op)                           \
 130   (op->precedence == 0                          \
 131    ? (! (op->type & MPEXPR_TYPE_OPERATOR))      \
 132    :   (op->type & MPEXPR_TYPE_WHOLEWORD))
 133
 134 #define isasciispace(c)   (isascii (c) && isspace (c))
 135
 136 static int
 137 lookahead (struct mpexpr_parse_t *p, int prefix)
 138 {
 139   __gmp_const struct mpexpr_operator_t  *op, *op_found;
 140   size_t  oplen, oplen_found, wlen;
 141   int     i;
 142
 143   /* skip white space */
 144   while (p->elen > 0 && isasciispace (*p->e))
 145     p->e++, p->elen--;
 146
 147   if (p->elen == 0)
 148     {
 149       TRACE (printf ("lookahead EOF\n"));
 150       p->token = TOKEN_EOF;
 151       return 1;
 152     }
 153
 154   DATA_SPACE ();
 155
 156   /* Get extent of whole word. */
 157   for (wlen = 0; wlen < p->elen; wlen++)
 158     if (! isasciicsym (p->e[wlen]))
 159       break;
 160
 161   TRACE (printf ("lookahead at: \"%.*s\" length %u, word %u\n",
 162                  (int) p->elen, p->e, p->elen, wlen));
 163
 164   op_found = NULL;
 165   oplen_found = 0;
 166   for (op = p->table; op->name != NULL; op++)
 167     {
 168       if (op->type == MPEXPR_TYPE_NEW_TABLE)
 169         {
 170           printf ("new\n");
 171           op = (struct mpexpr_operator_t *) op->name - 1;
 172           continue;
 173         }
 174
 175       oplen = strlen (op->name);
 176       if (! ((WHOLEWORD (op) ? wlen == oplen : p->elen >= oplen)
 177              && memcmp (p->e, op->name, oplen) == 0))
 178         continue;
 179
 180       /* Shorter matches don't replace longer previous ones. */
 181       if (op_found && oplen < oplen_found)
 182         continue;
 183
 184       /* On a match of equal length to a previous one, the old match isn't
 185          replaced if it has the preferred prefix, and if it doesn't then
 186          it's not replaced if the new one also doesn't.  */
 187       if (op_found && oplen == oplen_found
 188           && ((op_found->type & MPEXPR_TYPE_PREFIX) == prefix
 189               || (op->type & MPEXPR_TYPE_PREFIX) != prefix))
 190         continue;
 191
 192       /* This is now either the first match seen, or a longer than previous
 193          match, or an equal to previous one but with a preferred prefix. */
 194       op_found = op;
 195       oplen_found = oplen;
 196     }
 197
 198   if (op_found)
 199     {
 200       p->e += oplen_found, p->elen -= oplen_found;
 201
 202       if (op_found->type == MPEXPR_TYPE_VARIABLE)
 203         {
 204           if (p->elen == 0)
 205             ERROR ("end of string expecting a variable",
 206                    MPEXPR_RESULT_PARSE_ERROR);
 207           i = p->e[0] - 'a';
 208           if (i < 0 || i >= MPEXPR_VARIABLES)
 209             ERROR ("bad variable name", MPEXPR_RESULT_BAD_VARIABLE);
 210           goto variable;
 211         }
 212
 213       if (op_found->precedence == 0)
 214         {
 215           TRACE (printf ("lookahead function: %s\n", op_found->name));
 216           p->token = TOKEN_FUNCTION;
 217           p->token_op = op_found;
 218           return 1;
 219         }
 220       else
 221         {
 222           TRACE (printf ("lookahead operator: %s\n", op_found->name));
 223           p->token = TOKEN_OPERATOR;
 224           p->token_op = op_found;
 225           return 1;
 226         }
 227     }
 228
 229   oplen = (*p->mpX_number) (SP+1, p->e, p->elen, p->base);
 230   if (oplen != 0)
 231     {
 232       p->e += oplen, p->elen -= oplen;
 233       p->token = TOKEN_VALUE;
 234       DATA_PUSH ();
 235       TRACE (MPX_TRACE ("lookahead number", SP));
 236       return 1;
 237     }
 238
 239   /* Maybe an unprefixed one character variable */
 240   i = p->e[0] - 'a';
 241   if (wlen == 1 && i >= 0 && i < MPEXPR_VARIABLES)
 242     {
 243     variable:
 244       p->e++, p->elen--;
 245       if (p->var[i] == NULL)
 246         ERROR ("NULL variable", MPEXPR_RESULT_BAD_VARIABLE);
 247       TRACE (printf ("lookahead variable: var[%d] = ", i);
 248              MPX_TRACE ("", p->var[i]));
 249       p->token = TOKEN_VALUE;
 250       DATA_PUSH ();
 251       (*p->mpX_set) (SP, p->var[i]);
 252       return 1;
 253     }
 254
 255   ERROR ("no token matched", MPEXPR_RESULT_PARSE_ERROR);
 256
 257  done:
 258   return 0;
 259 }
 260
 261
 262 /* control stack current top element */
 263 #define CP   (p->control_stack + p->control_top)
 264
 265 /* make sure there's room for another control element above current top */
 266 #define CONTROL_SPACE()                                                    \
 267   do {                                                                     \
 268     if (p->control_top + 1 >= p->control_alloc)                            \
 269       {                                                                    \
 270         TRACE (printf ("grow control stack from %d\n", p->control_alloc)); \
 271         REALLOC (p->control_stack, p->control_alloc, 20,                   \
 272                  struct mpexpr_control_t);                                 \
 273       }                                                                    \
 274   } while (0)
 275
 276 /* Push an operator on the control stack, claiming currently to have the
 277    given number of args ready.  Local variable "op" is used in case opptr is
 278    a reference through CP.  */
 279 #define CONTROL_PUSH(opptr,args)                        \
 280   do {                                                  \
 281     __gmp_const struct mpexpr_operator_t *op = opptr;   \
 282     struct mpexpr_control_t *cp;                        \
 283     CONTROL_SPACE ();                                   \
 284     p->control_top++;                                   \
 285     ASSERT (p->control_top < p->control_alloc);         \
 286     cp = CP;                                            \
 287     cp->op = op;                                        \
 288     cp->argcount = (args);                              \
 289     TRACE_CONTROL("control stack push:");               \
 290   } while (0)
 291
 292 /* The special operator_done is never popped, so top>=0 will hold. */
 293 #define CONTROL_POP()                           \
 294   do {                                          \
 295     p->control_top--;                           \
 296     ASSERT (p->control_top >= 0);               \
 297     TRACE_CONTROL ("control stack pop:");       \
 298   } while (0)
 299
 300 #define TRACE_CONTROL(str)                              \
 301   TRACE ({                                              \
 302     int  i;                                             \
 303     printf ("%s depth %d:", str, p->control_top);       \
 304     for (i = 0; i <= p->control_top; i++)               \
 305       printf (" \"%s\"(%d)",                            \
 306               p->control_stack[i].op->name,             \
 307               p->control_stack[i].argcount);            \
 308     printf ("\n");                                      \
 309   });
 310
 311
 312 #define LOOKAHEAD(prefix)               \
 313   do {                                  \
 314     if (! lookahead (p, prefix))        \
 315       goto done;                        \
 316   } while (0)
 317
 318 #define CHECK_UI(n)                                                     \
 319   do {                                                                  \
 320     if (! (*p->mpX_ulong_p) (n))                                        \
 321       ERROR ("operand doesn't fit ulong", MPEXPR_RESULT_NOT_UI);        \
 322   } while (0)
 323
 324 #define CHECK_ARGCOUNT(str,n)                                              \
 325   do {                                                                     \
 326     if (CP->argcount != (n))                                               \
 327       {                                                                    \
 328         TRACE (printf ("wrong number of arguments for %s, got %d want %d", \
 329                        str, CP->argcount, n));                             \
 330         ERROR ("", MPEXPR_RESULT_PARSE_ERROR);                             \
 331       }                                                                    \
 332   } while (0)
 333
 334
 335 /* There's two basic states here.  In both p->token is the next token.
 336
 337    "another_expr" is when a whole expression should be parsed.  This means a
 338    literal or variable value possibly followed by an operator, or a function
 339    or prefix operator followed by a further whole expression.
 340
 341    "another_operator" is when an expression has been parsed and its value is
 342    on the top of the data stack (SP) and an optional further postfix or
 343    infix operator should be parsed.
 344
 345    In "another_operator" precedences determine whether to push the operator
 346    onto the control stack, or instead go to "apply_control" to reduce the
 347    operator currently on top of the control stack.
 348
 349    When an operator has both a prefix and postfix/infix form, a LOOKAHEAD()
 350    for "another_expr" will seek the prefix form, a LOOKAHEAD() for
 351    "another_operator" will seek the postfix/infix form.  The grammar is
 352    simple enough that the next state is known before reading the next token.
 353
 354    Argument count checking guards against functions consuming the wrong
 355    number of operands from the data stack.  The same checks are applied to
 356    operators, but will always pass since a UNARY or BINARY will only ever
 357    parse with the correct operands.  */
 358
 359 int
 360 mpexpr_evaluate (struct mpexpr_parse_t *p)
 361 {
 362   void *(*allocate_func) (size_t);
 363   void *(*reallocate_func) (void *, size_t, size_t);
 364   void (*free_func) (void *, size_t);
 365
 366   mp_get_memory_functions (&allocate_func, &reallocate_func, &free_func);
 367
 368   TRACE (printf ("mpexpr_evaluate() base %d \"%.*s\"\n",
 369                  p->base, (int) p->elen, p->e));
 370
 371   /* "done" is a special sentinel at the bottom of the control stack,
 372      precedence -1 is lower than any normal operator.  */
 373   {
 374     static __gmp_const struct mpexpr_operator_t  operator_done
 375       = { "DONE", NULL, MPEXPR_TYPE_DONE, -1 };
 376
 377     p->control_alloc = 20;
 378     p->control_stack = ALLOCATE_FUNC_TYPE (p->control_alloc,
 379                                            struct mpexpr_control_t);
 380     p->control_top = 0;
 381     CP->op = &operator_done;
 382     CP->argcount = 1;
 383   }
 384
 385   p->data_inited = 0;
 386   p->data_alloc = 20;
 387   p->data_stack = ALLOCATE_FUNC_TYPE (p->data_alloc, union mpX_t);
 388   p->data_top = -1;
 389
 390   p->error_code = MPEXPR_RESULT_OK;
 391
 392
 393  another_expr_lookahead:
 394   LOOKAHEAD (MPEXPR_TYPE_PREFIX);
 395   TRACE (printf ("another expr\n"));
 396
 397   /*another_expr:*/
 398   switch (p->token) {
 399   case TOKEN_VALUE:
 400     goto another_operator_lookahead;
 401
 402   case TOKEN_OPERATOR:
 403     TRACE (printf ("operator %s\n", p->token_op->name));
 404     if (! (p->token_op->type & MPEXPR_TYPE_PREFIX))
 405       ERROR ("expected a prefix operator", MPEXPR_RESULT_PARSE_ERROR);
 406
 407     CONTROL_PUSH (p->token_op, 1);
 408     goto another_expr_lookahead;
 409
 410   case TOKEN_FUNCTION:
 411     CONTROL_PUSH (p->token_op, 1);
 412
 413     if (p->token_op->type & MPEXPR_TYPE_CONSTANT)
 414       goto apply_control_lookahead;
 415
 416     LOOKAHEAD (MPEXPR_TYPE_PREFIX);
 417     if (! (p->token == TOKEN_OPERATOR
 418            && p->token_op->type == MPEXPR_TYPE_OPENPAREN))
 419       ERROR ("expected open paren for function", MPEXPR_RESULT_PARSE_ERROR);
 420
 421     TRACE (printf ("open paren for function \"%s\"\n", CP->op->name));
 422
 423     if ((CP->op->type & MPEXPR_TYPE_MASK_ARGCOUNT) == MPEXPR_TYPE_NARY(0))
 424       {
 425         LOOKAHEAD (0);
 426         if (! (p->token == TOKEN_OPERATOR
 427                && p->token_op->type == MPEXPR_TYPE_CLOSEPAREN))
 428           ERROR ("expected close paren for 0ary function",
 429                  MPEXPR_RESULT_PARSE_ERROR);
 430         goto apply_control_lookahead;
 431       }
 432
 433     goto another_expr_lookahead;
 434   }
 435   ERROR ("unrecognised start of expression", MPEXPR_RESULT_PARSE_ERROR);
 436
 437
 438  another_operator_lookahead:
 439   LOOKAHEAD (0);
 440  another_operator:
 441   TRACE (printf ("another operator maybe: %s\n", TOKEN_NAME(p->token)));
 442
 443   switch (p->token) {
 444   case TOKEN_EOF:
 445     goto apply_control;
 446
 447   case TOKEN_OPERATOR:
 448     /* The next operator is compared to the one on top of the control stack.
 449        If the next is lower precedence, or the same precedence and not
 450        right-associative, then reduce using the control stack and look at
 451        the next operator again later.  */
 452
 453 #define PRECEDENCE_TEST_REDUCE(tprec,cprec,ttype,ctype)                 \
 454     ((tprec) < (cprec)                                                  \
 455      || ((tprec) == (cprec) && ! ((ttype) & MPEXPR_TYPE_RIGHTASSOC)))
 456
 457     if (PRECEDENCE_TEST_REDUCE (p->token_op->precedence, CP->op->precedence,
 458                                 p->token_op->type,       CP->op->type))
 459       {
 460         TRACE (printf ("defer operator: %s (prec %d vs %d, type 0x%X)\n",
 461                        p->token_op->name,
 462                        p->token_op->precedence, CP->op->precedence,
 463                        p->token_op->type));
 464         goto apply_control;
 465       }
 466
 467     /* An argsep is a binary operator, but is never pushed on the control
 468        stack, it just accumulates an extra argument for a function. */
 469     if (p->token_op->type == MPEXPR_TYPE_ARGSEP)
 470       {
 471         if (CP->op->precedence != 0)
 472           ERROR ("ARGSEP not in a function call", MPEXPR_RESULT_PARSE_ERROR);
 473
 474         TRACE (printf ("argsep for function \"%s\"(%d)\n",
 475                        CP->op->name, CP->argcount));
 476
 477 #define IS_PAIRWISE(type)                                               \
 478         (((type) & (MPEXPR_TYPE_MASK_ARGCOUNT | MPEXPR_TYPE_PAIRWISE))  \
 479          == (MPEXPR_TYPE_BINARY | MPEXPR_TYPE_PAIRWISE))
 480
 481         if (IS_PAIRWISE (CP->op->type) && CP->argcount >= 2)
 482           {
 483             TRACE (printf ("    will reduce pairwise now\n"));
 484             CP->argcount--;
 485             CONTROL_PUSH (CP->op, 2);
 486             goto apply_control;
 487           }
 488
 489         CP->argcount++;
 490         goto another_expr_lookahead;
 491       }
 492
 493     switch (p->token_op->type & MPEXPR_TYPE_MASK_ARGCOUNT) {
 494     case MPEXPR_TYPE_NARY(1):
 495       /* Postfix unary operators can always be applied immediately.  The
 496          easiest way to do this is just push it on the control stack and go
 497          to the normal control stack reduction code. */
 498
 499       TRACE (printf ("postfix unary operator: %s\n", p->token_op->name));
 500       if (p->token_op->type & MPEXPR_TYPE_PREFIX)
 501         ERROR ("prefix unary operator used postfix",
 502                MPEXPR_RESULT_PARSE_ERROR);
 503       CONTROL_PUSH (p->token_op, 1);
 504       goto apply_control_lookahead;
 505
 506     case MPEXPR_TYPE_NARY(2):
 507       CONTROL_PUSH (p->token_op, 2);
 508       goto another_expr_lookahead;
 509
 510     case MPEXPR_TYPE_NARY(3):
 511       CONTROL_PUSH (p->token_op, 1);
 512       goto another_expr_lookahead;
 513     }
 514
 515     TRACE (printf ("unrecognised operator \"%s\" type: 0x%X",
 516                    CP->op->name, CP->op->type));
 517     ERROR ("", MPEXPR_RESULT_PARSE_ERROR);
 518     break;
 519
 520   default:
 521     TRACE (printf ("expecting an operator, got token %d", p->token));
 522     ERROR ("", MPEXPR_RESULT_PARSE_ERROR);
 523   }
 524
 525
 526  apply_control_lookahead:
 527   LOOKAHEAD (0);
 528  apply_control:
 529   /* Apply the top element CP of the control stack.  Data values are SP,
 530      SP-1, etc.  Result is left as stack top SP after popping consumed
 531      values.
 532
 533      The use of sp as a duplicate of SP will help compilers that can't
 534      otherwise recognise the various uses of SP as common subexpressions.  */
 535
 536   TRACE (printf ("apply control: nested %d, \"%s\" 0x%X, %d args\n",
 537                  p->control_top, CP->op->name, CP->op->type, CP->argcount));
 538
 539   TRACE (printf ("apply 0x%X-ary\n",
 540                  CP->op->type & MPEXPR_TYPE_MASK_ARGCOUNT));
 541   switch (CP->op->type & MPEXPR_TYPE_MASK_ARGCOUNT) {
 542   case MPEXPR_TYPE_NARY(0):
 543     {
 544       mpX_ptr  sp;
 545       DATA_SPACE ();
 546       DATA_PUSH ();
 547       sp = SP;
 548       switch (CP->op->type & MPEXPR_TYPE_MASK_ARGSTYLE) {
 549       case 0:
 550         (* (mpexpr_fun_0ary_t) CP->op->fun) (sp);
 551         break;
 552       case MPEXPR_TYPE_RESULT_INT:
 553         (*p->mpX_set_si) (sp, (long) (* (mpexpr_fun_i_0ary_t) CP->op->fun) ());
 554         break;
 555       default:
 556         ERROR ("unrecognised 0ary argument calling style",
 557                MPEXPR_RESULT_BAD_TABLE);
 558       }
 559     }
 560     break;
 561
 562   case MPEXPR_TYPE_NARY(1):
 563     {
 564       mpX_ptr  sp = SP;
 565       CHECK_ARGCOUNT ("unary", 1);
 566       TRACE (MPX_TRACE ("before", sp));
 567
 568       switch (CP->op->type & MPEXPR_TYPE_MASK_SPECIAL) {
 569       case 0:
 570         /* not a special */
 571         break;
 572
 573       case MPEXPR_TYPE_DONE & MPEXPR_TYPE_MASK_SPECIAL:
 574         TRACE (printf ("special done\n"));
 575         goto done;
 576
 577       case MPEXPR_TYPE_LOGICAL_NOT & MPEXPR_TYPE_MASK_SPECIAL:
 578         TRACE (printf ("special logical not\n"));
 579         (*p->mpX_set_si)
 580           (sp, (long) ((* (mpexpr_fun_i_unary_t) CP->op->fun) (sp) == 0));
 581         goto apply_control_done;
 582
 583       case MPEXPR_TYPE_CLOSEPAREN & MPEXPR_TYPE_MASK_SPECIAL:
 584         CONTROL_POP ();
 585         if (CP->op->type == MPEXPR_TYPE_OPENPAREN)
 586           {
 587             TRACE (printf ("close paren matching open paren\n"));
 588             CONTROL_POP ();
 589             goto another_operator;
 590           }
 591         if (CP->op->precedence == 0)
 592           {
 593             TRACE (printf ("close paren for function\n"));
 594             goto apply_control;
 595           }
 596         ERROR ("unexpected close paren", MPEXPR_RESULT_PARSE_ERROR);
 597
 598       default:
 599         TRACE (printf ("unrecognised special unary operator 0x%X",
 600                        CP->op->type & MPEXPR_TYPE_MASK_SPECIAL));
 601         ERROR ("", MPEXPR_RESULT_BAD_TABLE);
 602       }
 603
 604       switch (CP->op->type & MPEXPR_TYPE_MASK_ARGSTYLE) {
 605       case 0:
 606         (* (mpexpr_fun_unary_t) CP->op->fun) (sp, sp);
 607         break;
 608       case MPEXPR_TYPE_LAST_UI:
 609         CHECK_UI (sp);
 610         (* (mpexpr_fun_unary_ui_t) CP->op->fun)
 611           (sp, (*p->mpX_get_ui) (sp));
 612         break;
 613       case MPEXPR_TYPE_RESULT_INT:
 614         (*p->mpX_set_si)
 615           (sp, (long) (* (mpexpr_fun_i_unary_t) CP->op->fun) (sp));
 616         break;
 617       case MPEXPR_TYPE_RESULT_INT | MPEXPR_TYPE_LAST_UI:
 618         CHECK_UI (sp);
 619         (*p->mpX_set_si)
 620           (sp,
 621            (long) (* (mpexpr_fun_i_unary_ui_t) CP->op->fun)
 622            ((*p->mpX_get_ui) (sp)));
 623         break;
 624       default:
 625         ERROR ("unrecognised unary argument calling style",
 626                MPEXPR_RESULT_BAD_TABLE);
 627       }
 628     }
 629     break;
 630
 631   case MPEXPR_TYPE_NARY(2):
 632     {
 633       mpX_ptr  sp;
 634
 635       /* pairwise functions are allowed to have just one argument */
 636       if ((CP->op->type & MPEXPR_TYPE_PAIRWISE)
 637           && CP->op->precedence == 0
 638           && CP->argcount == 1)
 639         goto apply_control_done;
 640
 641       CHECK_ARGCOUNT ("binary", 2);
 642       DATA_POP (1);
 643       sp = SP;
 644       TRACE (MPX_TRACE ("lhs", sp);
 645              MPX_TRACE ("rhs", sp+1));
 646
 647       if (CP->op->type & MPEXPR_TYPE_MASK_CMP)
 648         {
 649           int  type = CP->op->type;
 650           int  cmp = (* (mpexpr_fun_i_binary_t) CP->op->fun)
 651             (sp, sp+1);
 652           (*p->mpX_set_si)
 653             (sp,
 654              (long)
 655              ((  (cmp  < 0) & ((type & MPEXPR_TYPE_MASK_CMP_LT) != 0))
 656               | ((cmp == 0) & ((type & MPEXPR_TYPE_MASK_CMP_EQ) != 0))
 657               | ((cmp  > 0) & ((type & MPEXPR_TYPE_MASK_CMP_GT) != 0))));
 658           goto apply_control_done;
 659         }
 660
 661       switch (CP->op->type & MPEXPR_TYPE_MASK_SPECIAL) {
 662       case 0:
 663         /* not a special */
 664         break;
 665
 666       case MPEXPR_TYPE_QUESTION & MPEXPR_TYPE_MASK_SPECIAL:
 667         ERROR ("'?' without ':'", MPEXPR_RESULT_PARSE_ERROR);
 668
 669       case MPEXPR_TYPE_COLON & MPEXPR_TYPE_MASK_SPECIAL:
 670         TRACE (printf ("special colon\n"));
 671         CONTROL_POP ();
 672         if (CP->op->type != MPEXPR_TYPE_QUESTION)
 673           ERROR ("':' without '?'", MPEXPR_RESULT_PARSE_ERROR);
 674
 675         CP->argcount--;
 676         DATA_POP (1);
 677         sp--;
 678         TRACE (MPX_TRACE ("query", sp);
 679                MPX_TRACE ("true",  sp+1);
 680                MPX_TRACE ("false", sp+2));
 681         (*p->mpX_set)
 682           (sp, (* (mpexpr_fun_i_unary_t) CP->op->fun) (sp)
 683            ? sp+1 : sp+2);
 684         goto apply_control_done;
 685
 686       case MPEXPR_TYPE_LOGICAL_AND & MPEXPR_TYPE_MASK_SPECIAL:
 687         TRACE (printf ("special logical and\n"));
 688         (*p->mpX_set_si)
 689           (sp,
 690            (long)
 691            ((* (mpexpr_fun_i_unary_t) CP->op->fun) (sp)
 692             && (* (mpexpr_fun_i_unary_t) CP->op->fun) (sp+1)));
 693         goto apply_control_done;
 694
 695       case MPEXPR_TYPE_LOGICAL_OR & MPEXPR_TYPE_MASK_SPECIAL:
 696         TRACE (printf ("special logical and\n"));
 697         (*p->mpX_set_si)
 698           (sp,
 699            (long)
 700            ((* (mpexpr_fun_i_unary_t) CP->op->fun) (sp)
 701             || (* (mpexpr_fun_i_unary_t) CP->op->fun) (sp+1)));
 702         goto apply_control_done;
 703
 704       case MPEXPR_TYPE_MAX & MPEXPR_TYPE_MASK_SPECIAL:
 705         TRACE (printf ("special max\n"));
 706         if ((* (mpexpr_fun_i_binary_t) CP->op->fun) (sp, sp+1) < 0)
 707           (*p->mpX_swap) (sp, sp+1);
 708         goto apply_control_done;
 709       case MPEXPR_TYPE_MIN & MPEXPR_TYPE_MASK_SPECIAL:
 710         TRACE (printf ("special min\n"));
 711         if ((* (mpexpr_fun_i_binary_t) CP->op->fun) (sp, sp+1) > 0)
 712           (*p->mpX_swap) (sp, sp+1);
 713         goto apply_control_done;
 714
 715       default:
 716         ERROR ("unrecognised special binary operator",
 717                MPEXPR_RESULT_BAD_TABLE);
 718       }
 719
 720       switch (CP->op->type & MPEXPR_TYPE_MASK_ARGSTYLE) {
 721       case 0:
 722         (* (mpexpr_fun_binary_t) CP->op->fun) (sp, sp, sp+1);
 723         break;
 724       case MPEXPR_TYPE_LAST_UI:
 725         CHECK_UI (sp+1);
 726         (* (mpexpr_fun_binary_ui_t) CP->op->fun)
 727           (sp, sp, (*p->mpX_get_ui) (sp+1));
 728         break;
 729       case MPEXPR_TYPE_RESULT_INT:
 730         (*p->mpX_set_si)
 731           (sp,
 732            (long) (* (mpexpr_fun_i_binary_t) CP->op->fun) (sp, sp+1));
 733         break;
 734       case MPEXPR_TYPE_LAST_UI | MPEXPR_TYPE_RESULT_INT:
 735         CHECK_UI (sp+1);
 736         (*p->mpX_set_si)
 737           (sp,
 738            (long) (* (mpexpr_fun_i_binary_ui_t) CP->op->fun)
 739            (sp, (*p->mpX_get_ui) (sp+1)));
 740         break;
 741       default:
 742         ERROR ("unrecognised binary argument calling style",
 743                MPEXPR_RESULT_BAD_TABLE);
 744       }
 745     }
 746     break;
 747
 748   case MPEXPR_TYPE_NARY(3):
 749     {
 750       mpX_ptr  sp;
 751
 752       CHECK_ARGCOUNT ("ternary", 3);
 753       DATA_POP (2);
 754       sp = SP;
 755       TRACE (MPX_TRACE ("arg1", sp);
 756              MPX_TRACE ("arg2", sp+1);
 757              MPX_TRACE ("arg3", sp+1));
 758
 759       switch (CP->op->type & MPEXPR_TYPE_MASK_ARGSTYLE) {
 760       case 0:
 761         (* (mpexpr_fun_ternary_t) CP->op->fun) (sp, sp, sp+1, sp+2);
 762         break;
 763       case MPEXPR_TYPE_LAST_UI:
 764         CHECK_UI (sp+2);
 765         (* (mpexpr_fun_ternary_ui_t) CP->op->fun)
 766           (sp, sp, sp+1, (*p->mpX_get_ui) (sp+2));
 767         break;
 768       case MPEXPR_TYPE_RESULT_INT:
 769         (*p->mpX_set_si)
 770           (sp,
 771            (long) (* (mpexpr_fun_i_ternary_t) CP->op->fun)
 772            (sp, sp+1, sp+2));
 773         break;
 774       case MPEXPR_TYPE_LAST_UI | MPEXPR_TYPE_RESULT_INT:
 775         CHECK_UI (sp+2);
 776         (*p->mpX_set_si)
 777           (sp,
 778            (long) (* (mpexpr_fun_i_ternary_ui_t) CP->op->fun)
 779            (sp, sp+1, (*p->mpX_get_ui) (sp+2)));
 780         break;
 781       default:
 782         ERROR ("unrecognised binary argument calling style",
 783                MPEXPR_RESULT_BAD_TABLE);
 784       }
 785     }
 786     break;
 787
 788   default:
 789     TRACE (printf ("unrecognised operator type: 0x%X\n", CP->op->type));
 790     ERROR ("", MPEXPR_RESULT_PARSE_ERROR);
 791   }
 792
 793  apply_control_done:
 794   TRACE (MPX_TRACE ("result", SP));
 795   CONTROL_POP ();
 796   goto another_operator;
 797
 798  done:
 799   if (p->error_code == MPEXPR_RESULT_OK)
 800     {
 801       if (p->data_top != 0)
 802         {
 803           TRACE (printf ("data stack want top at 0, got %d\n", p->data_top));
 804           p->error_code = MPEXPR_RESULT_PARSE_ERROR;
 805         }
 806       else
 807         (*p->mpX_set_or_swap) (p->res, SP);
 808     }
 809
 810   {
 811     int  i;
 812     for (i = 0; i < p->data_inited; i++)
 813       {
 814         TRACE (printf ("clear %d\n", i));
 815         (*p->mpX_clear) (p->data_stack+i);
 816       }
 817   }
 818
 819   FREE_FUNC_TYPE (p->data_stack, p->data_alloc, union mpX_t);
 820   FREE_FUNC_TYPE (p->control_stack, p->control_alloc, struct mpexpr_control_t);
 821
 822   return p->error_code;
 823 }