chiark - git - mdw - xyla/blob - t/treetest.c

   1 /* -*-c-*-
   2  *
   3  * Test driver
   4  *
   5  * (c) 2024 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Xyla, a library of binary trees.
  11  *
  12  * Xyla is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU Lesser General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Xyla is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20  * License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include <assert.h>
  29 #include <ctype.h>
  30 #include <errno.h>
  31 #include <stdarg.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 /*----- Primary switch ----------------------------------------------------*/
  37
  38 #define AVL 1
  39 #define RB 2
  40 #define SPLAY 3
  41 #define TREAP 4
  42
  43 #include "lib.h"
  44 #if TREE == AVL
  45 #  include "avl.h"
  46 #  define T avl
  47 #  define TREE__NAME(name) XYLA_AVL_##name
  48 #  define tree__name(name) xyla_avl_##name
  49 #  define HAVE_HEIGHT 1
  50 #  define FLAGMASK (~XYLA_AVLF_BALMASK)
  51 #elif TREE == RB
  52 #  include "rb.h"
  53 #  define T rb
  54 #  define TREE__NAME(name) XYLA_RB_##name
  55 #  define tree__name(name) xyla_rb_##name
  56 #  define HAVE_HEIGHT 1
  57 #  define FLAGMASK (~XYLA_RBF_RED)
  58 #elif TREE == SPLAY
  59 #  include "splay.h"
  60 #  define T spl
  61 #  define TREE__NAME(name) XYLA_SPLAY_##name
  62 #  define tree__name(name) xyla_splay_##name
  63 #  undef HAVE_HEIGHT
  64 #  undef FLAGMASK
  65 #elif TREE == TREAP
  66 #  include "treap.h"
  67 #  define T trp
  68 #  define TREE__NAME(name) XYLA_TREAP_##name
  69 #  define tree__name(name) xyla_treap_##name
  70 #  undef HAVE_HEIGHT
  71 #  undef FLAGMASK
  72 #else
  73 #  error "unknown `TREE' value"
  74 #endif
  75
  76 #define NODE tree__name(node)
  77 #define ITER tree__name(iter)
  78 #define RITER tree__name(riter)
  79 #define PATH tree__name(path)
  80 #define TREE_NODEPFX TREE__NAME(NODEPFX)
  81 #define TREE_NODEUSFX TREE__NAME(NODEUSFX)
  82 #define TREE_HEIGHT tree__name(height)
  83 #define TREE_INITITER tree__name(inititer)
  84 #define TREE_NEXT tree__name(next)
  85 #define TREE_INITRITER tree__name(initriter)
  86 #define TREE_PREV tree__name(prev)
  87 #define TREE_CURRENT tree__name(current)
  88 /* #define TREE_COPYPATH tree__name(copypath) */
  89 #define TREE_FIRSTPATH tree__name(firstpath)
  90 #define TREE_LASTPATH tree__name(lastpath)
  91 #define TREE_NEXTPATH tree__name(nextpath)
  92 #define TREE_PREVPATH tree__name(prevpath)
  93 #define TREE_BEFOREPATH tree__name(beforepath)
  94 #define TREE_AFTERPATH tree__name(afterpath)
  95 #define TREE_ROOTPATH tree__name(rootpath)
  96 #define TREE_UPPATH tree__name(uppath)
  97 #define TREE_LEFTPATH tree__name(leftpath)
  98 #define TREE_RIGHTPATH tree__name(rightpath)
  99 /* #define TREE_REPLACE tree__name(replace) */
 100 /* #define TREE_RIPPLE tree__name(ripple) */
 101 #define TREE_ASCEND tree__name(ascend)
 102 #define TREE_LOOKUP tree__name(lookup)
 103 #define TREE_PROBE tree__name(probe)
 104 #define TREE_INSERT tree__name(insert)
 105 #define TREE_REMOVE tree__name(remove)
 106 #define TREE_JOIN tree__name(join)
 107 #define TREE_SPLIT tree__name(split)
 108 #define TREE_SPLITAT tree__name(splitat)
 109 /* #define TREE_SPLITROOT tree__name(splitroot) */
 110 #define TREE_UNISECT tree__name(unisect)
 111 #define TREE_DIFFSECT tree__name(diffsect)
 112 #define TREE_CHECK tree__name(check)
 113
 114 #ifdef HAVE_HEIGHT
 115 #  define H(x) x
 116 #  define HELSE(x, y) x
 117 #  define HARG(x) , x
 118 #else
 119 #  define H(x)
 120 #  define HELSE(x, y) y
 121 #  define HARG(x)
 122 #endif
 123
 124 /*----- Preliminaries -----------------------------------------------------*/
 125
 126 static FILE *in, *out;
 127 int stop = 0;
 128
 129 #define BCAT_FAIL 1u
 130 #define BCAT_ERR 2u
 131 #define BCAT_BUG 3u
 132 static NORETURN PRINTF_LIKE(2, 3)
 133   void bail(unsigned cat, const char *msg, ...)
 134 {
 135   /* Write a`printf'-formatted message MSG to standard error and quit the
 136    * program.  CAT is a constant which indicates the reason: `BCAT_FAIL'
 137    * indicates an environmental problem (e.g., insufficient memory);
 138    * `BCAT_ERR' indicates a user error; `BCAT_BUG' indicates a bug detected
 139    * in the tree implementation.  The category determines the token printed
 140    * before the message.  Also, if this is a fuzzing build, `BCAT_BUG'
 141    * results in a call to `abort' rather than `exit' to let the fuzzer know
 142    * that it should claim a win.
 143    */
 144
 145   va_list ap;
 146   long pos;
 147
 148   switch (cat) {
 149     case BCAT_FAIL: fputs("failure: ", stderr); break;
 150     case BCAT_ERR: fputs("error: ", stderr); break;
 151     case BCAT_BUG: fputs("BUG: ", stderr); break;
 152     default:
 153       fprintf(stderr, "(unknown bail code %u): ", cat);
 154       cat = BCAT_BUG;
 155       break;
 156   }
 157   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
 158   if (in) {
 159     pos = ftell(in);
 160     if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
 161   }
 162   fputc('\n', stderr);
 163 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
 164   if (cat == BCAT_BUG) abort();
 165 #endif
 166   exit(2);
 167 }
 168
 169 enum { DIR_IN, DIR_OUT };
 170   /* Direction codes for `check_file', `open_file', and `close_file'. */
 171
 172 static void check_file(unsigned dir)
 173 {
 174   /* Check that the file indicated by DIR is free of errors.  If DIR is
 175    * `DIR_OUT' then buffered output is flushed.
 176    */
 177
 178   FILE *fp;
 179   const char *act;
 180   unsigned f = 0;
 181 #define f_flush 1u
 182
 183   switch (dir) {
 184     case DIR_IN: fp = in; act = "read"; break;
 185     case DIR_OUT: fp = out; act = "write"; f |= f_flush; break;
 186     default: assert(0);
 187   }
 188   if (fp) {
 189     if (((f&f_flush) && fflush(fp)) || ferror(fp))
 190       bail(BCAT_ERR, "%s error: %s", act, strerror(errno));
 191   }
 192
 193 #undef f_flush
 194 }
 195
 196 static void close_file(unsigned dir)
 197 {
 198   /* Close the file indicated by DIR.  Check that it was in a good state
 199    * beforehand.
 200    */
 201
 202   FILE **fp_inout, *fp, *stdfp;
 203
 204   switch (dir) {
 205     case DIR_IN: fp_inout = &in; stdfp = stdin; break;
 206     case DIR_OUT: fp_inout = &out; stdfp = stdout; break;
 207     default: assert(0);
 208   }
 209   fp = *fp_inout;
 210   if (fp) {
 211     check_file(dir);
 212     if (fp != stdfp) fclose(fp);
 213     *fp_inout = 0;
 214   }
 215 }
 216
 217 static void open_file(const char *file, unsigned dir)
 218 {
 219   /* Open FILE as the current input or output file, as indicated by DIR. */
 220
 221   FILE **fp_inout, *fp, *stdfp;
 222   const char *mode, *what;
 223   unsigned f = 0;
 224 #define f_chkeof 1u
 225
 226   switch (dir) {
 227     case DIR_IN:
 228       fp_inout = &in; stdfp = stdin; mode = "r"; what = "input";
 229       f |= f_chkeof;
 230       break;
 231     case DIR_OUT:
 232       fp_inout = &out; stdfp = stdout; mode = "w"; what = "output";
 233       break;
 234     default: assert(0);
 235   }
 236   close_file(dir);
 237   if (file[0] == '-' && !file[1]) {
 238     if (((f&f_chkeof) && feof(stdfp)) || ferror(stdfp))
 239       bail(BCAT_ERR, "already consumed standard %s", what);
 240     *fp_inout = stdfp;
 241   } else {
 242     fp = fopen(file, mode);
 243     if (!fp)
 244       bail(BCAT_ERR, "failed to open %s file `%s': %s",
 245            what, file, strerror(errno));
 246     *fp_inout = fp;
 247   }
 248
 249 #undef f_chkeof
 250 }
 251
 252 static unsigned long read_int(void)
 253 {
 254   /* Read and return an integer from the intput file.
 255    *
 256    * These are used as a search keys, indices, or weights.
 257    */
 258
 259   unsigned long k;
 260   int ch;
 261
 262   /* For some stupid reason, there isn't a `scanf' format which just reads
 263    * an unsigned integer with an arbitrary radix prefix.  The `%d' format
 264    * does the right thing for a signed value, but not unsigned.  So we have
 265    * this.
 266    */
 267   do ch = getc(in); while (isspace(ch));
 268   if (!isdigit(ch)) bail(BCAT_ERR, "integer expected, found `%c'", ch);
 269   if (ch != '0') {
 270     ungetc(ch, in);
 271     if (fscanf(in, "%lu", &k) != 1)
 272       bail(BCAT_ERR, "integer expected, scanf failed");
 273   } else {
 274     ch = getc(in);
 275     if (ch == 'x' || ch == 'X') {
 276       if (fscanf(in, "%lx", &k) != 1)
 277         bail(BCAT_ERR, "integer expected, scanf failed");
 278     } else if ('0' <= ch && ch <= '7') {
 279       ungetc(ch, in);
 280       if (fscanf(in, "%lo", &k) != 1)
 281         bail(BCAT_ERR, "integer expected, scanf failed");
 282     } else
 283       { ungetc(ch, in); k = 0; }
 284   }
 285   return (k);
 286 }
 287
 288 static unsigned long seed = 0xacd1051a;
 289   /* Seed for random number generator.  Don't set this to zero. */
 290
 291 #if TREE == TREAP || defined(FLAGMASK)
 292 static unsigned long randwt(void)
 293 {
 294   /* Return a pseudo-random integer.
 295    *
 296    * We have our own -- currently a rather simple LFSR -- so that the test
 297    * results are reproducible on all targets.
 298    */
 299
 300   unsigned long x = seed, m;
 301   unsigned i;
 302 #define RANDPOLY 0x915717d7
 303
 304   for (i = 0; i < 32; i++) {
 305     m = ~(((seed >> 31)&1) - 1);
 306     seed = (seed << 1) ^ (m&RANDPOLY);
 307   }
 308   seed &= 0xffffffff; return (x);
 309
 310 #undef RANDPOLY
 311 }
 312 #endif
 313
 314 static const char *rctag(int rc)
 315 {
 316   /* Return the name of return code RC as a string. */
 317
 318   static const char *const tagtab[] = {
 319 #define TAG(tag, msg) #tag,
 320     XYLA_RC_DOLOSE(TAG)
 321     XYLA_RC_DOWIN(TAG)
 322 #undef TAG
 323   };
 324
 325   if (XYLA_RC_LOSELIMIT <= rc && rc < XYLA_RC_WINLIMIT)
 326     return (tagtab[rc - XYLA_RC_LOSELIMIT]);
 327   else
 328     return ("#<unknown libxyla error code>");
 329 }
 330
 331 /*----- Node definition ---------------------------------------------------*/
 332
 333 struct my_node {
 334   /* Our test node structure. */
 335
 336   TREE_NODEPFX;                         /* tree node control data */
 337 #ifdef FLAGMASK
 338   unsigned fref;                        /* reference value for user flags */
 339 #endif
 340   struct my_node *next, *prev;          /* links in active nodes list */
 341   size_t n;                             /* number of nodes in this subtree */
 342   unsigned long seq, k;                 /* sequence number and key */
 343 };
 344 union my_nodeu { struct my_node my; TREE_NODEUSFX; };
 345
 346 /* Conversions. */
 347 #define MY_NODE(node)                                                   \
 348         CONVERT_CAREFULLY(struct my_node *, struct xyla_bt_node *, node)
 349 #define MY_NODEU(node)                                                  \
 350         CONVERT_CAREFULLY(union my_nodeu *, struct xyla_bt_node *, node)
 351 #define CONST_MY_NODE(node)                                             \
 352         CONVERT_CAREFULLY(const struct my_node *,                       \
 353                           const struct xyla_bt_node *,                  \
 354                           node)
 355 #define CONST_MY_NODEU(node)                                            \
 356         CONVERT_CAREFULLY(const union my_nodeu *,                       \
 357                           const struct xyla_bt_node *,                  \
 358                           node)
 359
 360 #define MY_SPLAY_NODE(node)                                             \
 361         CONVERT_CAREFULLY(struct my_node *, struct xyla_splay_node *, node)
 362
 363 #define TREE_NODE(node)                                                 \
 364         CONVERT_CAREFULLY(struct NODE *, struct xyla_bt_node *, node)
 365 #define CONST_TREE_NODE(node)                                           \
 366         CONVERT_CAREFULLY(const struct NODE *,                          \
 367                           const struct xyla_bt_node *,                  \
 368                           node)
 369
 370 static unsigned long nodeseq = 0;       /* next node sequence number */
 371 static struct my_node *nodes = 0;       /* list of active nodes */
 372
 373 static int my_ordnav(struct xyla_bt_nodecls *cls,
 374                      const struct xyla_bt_node *node, void *arg)
 375 {
 376   /* Navigation function to search by key. */
 377
 378   const struct my_node *mynode = CONST_MY_NODE(node);
 379   unsigned long *key = arg;
 380
 381   if (*key < mynode->k) return (-1);
 382   else if (*key > mynode->k) return (+1);
 383   else return (0);
 384 }
 385
 386 static int my_idxnav(struct xyla_bt_nodecls *cls,
 387                      const struct xyla_bt_node *node, void *arg)
 388 {
 389   /* Navigation function to search by index. */
 390
 391   const struct my_node *myleft = CONST_MY_NODE(node->left);
 392   unsigned long *i_inout = arg, i = *i_inout, n;
 393
 394   if (myleft) {
 395     n = myleft->n;
 396     if (i < n) return (-1);
 397     else i -= n;
 398   }
 399   if (!i) return (0);
 400   *i_inout = i - 1; return (+1);
 401 }
 402
 403 static void my_upd(struct xyla_bt_nodecls *cls, struct xyla_bt_node *node)
 404 {
 405   /* Update function to maintain node count. */
 406
 407   struct my_node
 408     *mynode = MY_NODE(node),
 409     *left = MY_NODE(mynode->bt.left), *right = MY_NODE(mynode->bt.right);
 410
 411   mynode->n = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 412 }
 413
 414 static const void *my_key(struct xyla_bt_nodecls *cls,
 415                           const struct xyla_bt_node *node)
 416 {
 417   /* Return search key for node. */
 418
 419   return (&CONST_MY_NODE(node)->k);
 420 }
 421
 422 #define CHKF_OUTMASK 0x3000u            /* check flags: output mode mask */
 423 #define CHKOUT_NONE 0x0000u             /*   no output */
 424 #define CHKOUT_LIST 0x1000u             /*   structure list */
 425 #define CHKOUT_KEYS 0x2000u             /*   plain list of keys */
 426 #define CHKOUT_DUMP 0x3000u             /*   full multiline dump */
 427 #define CHKF_SANITY 0x0800u             /* checking user input */
 428
 429 struct my_checkstate {
 430   /* Checking state. */
 431
 432   unsigned f;                           /* flags */
 433 #define CF_SPC 1u                       /*   put space before next output */
 434 };
 435
 436 struct my_nodeinfo {
 437   /* Per-node tracking information */
 438
 439   struct xyla_bt_ordinfo _ord;          /* order checking state */
 440   int lv;                               /* indentation level */
 441 };
 442
 443 static int my_check(unsigned op, const struct xyla_bt_check *chk)
 444 {
 445   /* Main checking and walking function. */
 446
 447   const struct my_node *node = CONST_MY_NODE(chk->node), *left, *right;
 448   struct my_checkstate *st = chk->state;
 449   struct my_nodeinfo
 450     *node_info = chk->node_info,
 451     *parent_info = chk->parent_info;
 452   size_t want;
 453   int rc = XYLA_RC_OK, subrc;
 454
 455   switch (op) {
 456     case XYLA_CHKOP_NIL:
 457       /* Reached a null link.  Some dump types print something distinctive
 458        * if the entire tree is empty, which we can determine easily enough.
 459        * The `CHKOUT_LIST' format needs to indicate all null links
 460        * explicitly.
 461        */
 462
 463       switch (chk->f&CHKF_OUTMASK) {
 464         case CHKOUT_NONE:
 465           break;
 466         case CHKOUT_LIST:
 467           putc('_', out);
 468           break;
 469         case CHKOUT_KEYS:
 470           if (chk->pos == XYLA_BTPOS_ROOT) fputs("(empty tree)", out);
 471           break;
 472         case CHKOUT_DUMP:
 473           if (chk->pos == XYLA_BTPOS_ROOT)
 474             fputs("\t(tree empty)\n", out);
 475           break;
 476       }
 477       break;
 478
 479     case XYLA_CHKOP_BEFORE:
 480       /* Called before the children.  Set up our indentation level, which
 481        * is a little tricky for red-black trees, because we align black
 482        * nodes.
 483        */
 484
 485       if (!parent_info)
 486         node_info->lv = 0;
 487       else
 488 #if TREE == RB
 489       if (!(node->rb.f&XYLA_RBF_RED))
 490         node_info->lv = (parent_info->lv + 2)&~1;
 491       else
 492 #endif
 493         node_info->lv = parent_info->lv + 1;
 494       if ((chk->f&CHKF_OUTMASK) == CHKOUT_LIST) putc('(', out);
 495       break;
 496
 497     case XYLA_CHKOP_MID:
 498       /* Called after the left subtree.  This is where the main printing
 499        * happens.
 500        */
 501
 502       switch (chk->f&CHKF_OUTMASK) {
 503         case CHKOUT_NONE:
 504           break;
 505         case CHKOUT_LIST:
 506           putc(' ', out);
 507 #if TREE == RB
 508           if (!(node->rb.f&XYLA_RBF_RED)) putc('*', out);
 509 #elif TREE == TREAP
 510           fprintf(out, "0x%08lx$ ", (unsigned long)node->trp.wt);
 511 #endif
 512           fprintf(out, "%lu", node->k);
 513           putc(' ', out);
 514           break;
 515         case CHKOUT_KEYS:
 516           if (!(st->f&CF_SPC)) st->f |= CF_SPC;
 517           else putc(' ', out);
 518           fprintf(out, "%lu", node->k);
 519           break;
 520         case CHKOUT_DUMP:
 521           fprintf(out, "\t#0x%08lx (n = %3lu)\t%*s",
 522                  node->seq, (unsigned long)node->n, 4*node_info->lv, "");
 523 #if TREE == AVL
 524           fprintf(out, "(%c)", AVL_BALCH(node));
 525 #elif TREE == RB
 526           fprintf(out, "(%c)", node->rb.f&XYLA_RBF_RED ? ' ' : '*');
 527 #else
 528           fputs("(*)", out);
 529 #endif
 530 #if TREE == TREAP
 531           fprintf(out, " 0x%08lx$", (unsigned long)node->trp.wt);
 532 #endif
 533           fprintf(out, " %lu\n", node->k);
 534           break;
 535       }
 536       break;
 537
 538     case XYLA_CHKOP_AFTER:
 539       /* Called after the right subtree.  This is where we check that the
 540        * node count is correct and that the user flags are faithfully
 541        * preserved.
 542        */
 543
 544       left = CONST_MY_NODE(chk->left);
 545       right = CONST_MY_NODE(chk->right);
 546       want = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 547       if (node->n != want) {
 548         if (chk->fp) {
 549           xyla_bt_bughdr("MY_TREE", chk->root, chk->fp);
 550           xyla_bt_printnode(chk->cls, &node->bt, chk->fp);
 551           fprintf(chk->fp, " count %lu /= %lu\n",
 552                   (unsigned long)node->n, (unsigned long)want);
 553         }
 554         rc = XYLA_RC_BAD;
 555       }
 556 #ifdef FLAGMASK
 557       if ((node->T.f&FLAGMASK) != node->fref) {
 558         if (chk->fp) {
 559           xyla_bt_bughdr("MY_TREE", chk->root, chk->fp);
 560           xyla_bt_printnode(chk->cls, &node->bt, chk->fp);
 561           fprintf(chk->fp, " flags %x /= %x\n",
 562                   node->T.f&FLAGMASK, node->fref);
 563         }
 564         rc = XYLA_RC_BAD;
 565       }
 566 #endif
 567       if ((chk->f&CHKF_OUTMASK) == CHKOUT_LIST) putc(')', out);
 568       break;
 569   }
 570
 571   /* Check that the ordering is respected. */
 572   subrc = xyla_bt_chkorder(op, chk);
 573     if (subrc) { rc = subrc; if (subrc != XYLA_RC_BAD) goto end; }
 574
 575   /* Done. */
 576 end:
 577   return (rc);
 578 }
 579
 580 static void my_ident(struct xyla_bt_nodecls *cls,
 581                      const struct xyla_bt_node *node, FILE *fp)
 582 {
 583   /* Node identification function. */
 584
 585   const struct my_node *my_node = CONST_MY_NODE(node);
 586
 587   fprintf(fp, "#<node #0x%08lx ", my_node->seq);
 588 #if TREE == TREAP
 589   fprintf(fp, "0x%08lx$ ", (unsigned long)my_node->trp.wt);
 590 #endif
 591   fprintf(fp, "%lu>", my_node->k);
 592 }
 593
 594 static const struct xyla_bt_chkops my_ops = {
 595   /* Node class operations table. */
 596
 597   { sizeof(my_ops), my_upd },
 598   { my_ordnav, my_key },
 599   { my_check, sizeof(struct my_nodeinfo), my_ident },
 600 };
 601
 602 /*----- Node utilities ----------------------------------------------------*/
 603
 604 static union my_nodeu *make_node(unsigned long k)
 605 {
 606   /* Return a fresh node with key K. */
 607
 608   union my_nodeu *node;
 609
 610   node = malloc(sizeof(*node));
 611   if (!node) bail(BCAT_FAIL, "out of memory");
 612 #ifdef FLAGMASK
 613   node->my.fref = node->my.T.f = randwt()&FLAGMASK;
 614 #endif
 615   node->my.n = 99; node->my.seq = nodeseq++; node->my.k = k;
 616   if (nodes) nodes->prev = &node->my;
 617   node->my.next = nodes; node->my.prev = 0; nodes = &node->my;
 618   return (node);
 619 }
 620
 621 static void free_node(struct my_node *node)
 622 {
 623   /* Free a node which we don't want any more. */
 624
 625   struct my_node *next = node->next, *prev = node->prev;
 626
 627   if (next) next->prev = prev;
 628   if (prev) prev->next = next;
 629   else nodes = next;
 630   free(node);
 631 }
 632
 633 static void free_tree(struct xyla_bt_node **root)
 634 {
 635   /* Free the tree rooted at ROOT. */
 636
 637   while (*root) free_node(xyla_bt_severfirst(root));
 638 }
 639
 640 static void check_dump(struct xyla_bt_nodecls *cls,
 641                        struct xyla_bt_node *const *root HARG(int expht),
 642                        unsigned f)
 643 {
 644   /* Run a check or dump of the tree at ROOT.
 645    *
 646    * If output is requested, then suppress checking output.  If there were
 647    * problems them report them afterwards.  If we didn't have a full dump
 648    * and problems were found, then print a dump afterwards.
 649    */
 650
 651   struct my_checkstate st;
 652   int rc;
 653   H( int ht; )
 654
 655   st.f = 0;
 656   if ((f&CHKF_OUTMASK) == CHKOUT_DUMP) {
 657     fputs("tree dump", out);
 658     H( if (expht != -1) fprintf(out, ", ht = %d", expht); )
 659     putc('\n', out);
 660   }
 661   rc = TREE_CHECK(cls, root,
 662                   (f&CHKF_OUTMASK) == CHKOUT_NONE ? stderr : 0, f
 663                   HARG(expht), &st);
 664 #ifdef HAVE_HEIGHT
 665   if ((f&CHKF_OUTMASK) == CHKOUT_NONE) {
 666     ht = TREE_HEIGHT(CONST_TREE_NODE(*root));
 667     if (ht != expht) {
 668       xyla_bt_bughdr("MY_TREE", root, stderr);
 669       fprintf(stderr, "expected height %d /= %d\n", expht, ht);
 670       if (!rc) rc = XYLA_RC_BAD;
 671     }
 672   }
 673 #endif
 674   if ((f&CHKF_OUTMASK) == CHKOUT_LIST || (f&CHKF_OUTMASK) == CHKOUT_KEYS)
 675     putc('\n', out);
 676   if (rc) {
 677     if ((f&CHKF_OUTMASK) != CHKOUT_NONE)
 678       TREE_CHECK(cls, root, stderr, CHKOUT_NONE HARG(expht), &st);
 679     if ((f&CHKF_OUTMASK) != CHKOUT_DUMP) {
 680       fputs("offending tree...\n", out);
 681       TREE_CHECK(cls, root, 0, CHKOUT_DUMP HARG(expht), &st);
 682     }
 683     if (f&CHKF_SANITY) bail(BCAT_ERR, "invalid tree: %s", xyla_strerror(rc));
 684     else bail(BCAT_BUG, "check failed: %s", xyla_strerror(rc));
 685   }
 686 }
 687
 688 static union my_nodeu *copy_tree(const union my_nodeu *node)
 689 {
 690   /* Make a copy of a tree.
 691    *
 692    * The nodes have new sequence numbers, but should otherwise be identical.
 693    */
 694
 695   union my_nodeu *copy, *left, *right;
 696
 697   if (!node) return (0);
 698   left = copy_tree(CONST_MY_NODEU(node->bt.left));
 699   right = copy_tree(CONST_MY_NODEU(node->bt.right));
 700   copy = make_node(node->my.k);
 701 #ifdef FLAGMASK
 702   copy->my.T.f = node->my.T.f;
 703   copy->my.fref = node->my.fref;
 704 #elif TREE == SPLAY
 705   copy->my.spl.parent = 0;
 706   if (left) left->my.spl.parent = &copy->spl;
 707   if (right) right->my.spl.parent = &copy->spl;
 708 #elif TREE == TREAP
 709   copy->my.trp.wt = node->my.trp.wt;
 710 #endif
 711   copy->my.bt.left = left ? &left->bt : 0;
 712   copy->my.bt.right = right ? &right->bt : 0;
 713   copy->my.n = node->my.n;
 714   return (copy);
 715 }
 716
 717 static int ascend_index(struct xyla_bt_node *node,
 718                         struct xyla_bt_node *parent,
 719                         struct xyla_bt_node *sibling,
 720                         unsigned pos, void *arg)
 721 {
 722   /* Ascension function to determine a node's index. */
 723
 724   struct my_node *mysib = MY_NODE(sibling);
 725   size_t *i_inout = arg;
 726
 727   if (pos == XYLA_BTPOS_RIGHT)
 728     *i_inout += 1 + (mysib ? mysib->n : 0);
 729   return (0);
 730 }
 731
 732 static size_t path_index(struct PATH *path)
 733 {
 734   /* Return the index of a node given a full path to it. */
 735
 736   struct my_node *mynode, *myleft;
 737   size_t i = 0;
 738
 739   mynode = TREE_CURRENT(path);
 740   if (mynode) {
 741     myleft = MY_NODE(mynode->bt.left);
 742     if (myleft) i += myleft->n;
 743   }
 744
 745   TREE_ASCEND(ascend_index, path, &i);
 746   return (i);
 747 }
 748
 749 static int full_path_p(struct PATH *path)
 750 {
 751   /* Return wehther PATH is full. */
 752
 753   return (!!TREE_CURRENT(path));
 754 }
 755
 756 static struct xyla_bt_node *read_tree(HELSE(int *ht_out, void))
 757 {
 758   /* Read a tree structure description from the input file and return
 759    * a pointer to the root.
 760    *
 761    * If the tree has a notion of height, then return the height in *HT_OUT.
 762    */
 763
 764   union my_nodeu *node;
 765   struct my_node *left, *right;
 766   int ch;
 767   unsigned long k;
 768   H( int ht; int lht; int rht; )
 769 #if TREE == AVL
 770   unsigned f = 3;
 771 #elif TREE == RB
 772   unsigned f = XYLA_RBF_RED;
 773 #elif TREE == TREAP
 774   size_t wt = 0, lwt, rwt;
 775   unsigned f = 0;
 776 #  define f_weight 1u
 777 #endif
 778
 779   /* Check for a `_' indicating a nil subtree, or the open paren. */
 780   do ch = getc(in); while (isspace(ch));
 781   if (ch == '_') { H( *ht_out = 0; ) return (0); }
 782   else if (ch != '(') bail(BCAT_ERR, "expected `(', found `%c'", ch);
 783
 784   /* Read the left subtree. */
 785   left = MY_NODE(read_tree(H(&lht)));
 786
 787   /* Read flags before the node proper. */
 788   for (;;) {
 789     do ch = getc(in); while (isspace(ch));
 790 #if TREE == AVL
 791     if (f == 3 && ch == '-') f = XYLA_AVLBAL_LBIAS;
 792     else if (f == 3 && ch == '=') f = XYLA_AVLBAL_EVEN;
 793     else if (f == 3 && ch == '+') f = XYLA_AVLBAL_RBIAS;
 794     else
 795 #elif TREE == RB
 796     if (ch == '*') f &= ~XYLA_RBF_RED;
 797     else
 798 #endif
 799     break;
 800   }
 801
 802   /* Read the node key. */
 803   ungetc(ch, in); k = read_int();
 804   do ch = getc(in); while (isspace(ch));
 805
 806   /* If this is a treap, then maybe that was actually the node weight.
 807    * If so, stash it and read the real key.
 808    */
 809 #if TREE == TREAP
 810   if (ch == '$') { wt = k; f |= f_weight; k = read_int(); }
 811   else
 812 #endif
 813   ungetc(ch, in);
 814
 815   /* Read the right subtree. */
 816   right = MY_NODE(read_tree(H(&rht)));
 817
 818   /* Expect the closing paren. */
 819   do ch = getc(in); while (isspace(ch));
 820   if (ch != ')') bail(BCAT_ERR, "expected `)', found `%c'", ch);
 821
 822   /* Make the node. */
 823   node = make_node(k);
 824   node->my.bt.left = left ? &left->bt : 0;
 825   node->my.bt.right = right ? &right->bt : 0;
 826   node->my.n = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 827
 828   /* Fill in the tree-specific bits. */
 829 #if TREE == AVL
 830   if (f != 3)
 831     ht = -1;
 832   else {
 833     if (lht == -1 || rht == -1)
 834       bail(BCAT_ERR, "missing balance annotation");
 835     switch (rht - lht) {
 836       case -1: f = XYLA_AVLBAL_LBIAS; ht = lht + 1; break;
 837       case  0: f = XYLA_AVLBAL_EVEN; ht = lht + 1; break;
 838       case +1: f = XYLA_AVLBAL_RBIAS; ht = rht + 1; break;
 839       default: bail(BCAT_ERR, "tree is not AVL"); ht = 0; break;
 840     }
 841   }
 842   node->my.avl.f = (node->my.avl.f&FLAGMASK) | f;
 843 #elif TREE == RB
 844   ht = f&XYLA_RBF_RED ? lht : lht + 1;
 845   node->my.rb.f = (node->my.rb.f&FLAGMASK) | f;
 846 #elif TREE == SPLAY
 847   if (left) left->spl.parent = &node->spl;
 848   if (right) right->spl.parent = &node->spl;
 849   node->my.spl.parent = 0;
 850 #elif TREE == TREAP
 851   lwt = left ? left->trp.wt : 0xffffffff;
 852   rwt = right ? right->trp.wt : 0xffffffff;
 853   if (f&f_weight)
 854     node->my.trp.wt = wt;
 855   else {
 856     wt = (((rwt < lwt ? rwt : lwt)&0xfff00000) - (1ul << 20)) | node->my.seq;
 857     if (wt > lwt || wt > rwt) bail(BCAT_ERR, "tree is not a treap");
 858     node->my.trp.wt = wt;
 859   }
 860 #endif
 861
 862   /* Save the subtree height. */
 863   H( *ht_out = ht; )
 864
 865   /* All done. */
 866   return (&node->bt);
 867
 868 #if TREE == TREAP
 869 #  undef f_weight
 870 #endif
 871 }
 872
 873 /*----- Main program ------------------------------------------------------*/
 874
 875 int main(int argc, char *argv[])
 876 {
 877 #define NSTACK 16
 878
 879   struct xyla_bt_nodecls mycls;
 880   struct { struct xyla_bt_node *root; H( int ht; ) } cur, stack[NSTACK], u;
 881   struct my_node *node = 0, *t;
 882   union my_nodeu *nodeu;
 883 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
 884   struct my_node *x, *y;
 885 #endif
 886 #if TREE != SPLAY
 887   struct xyla_bt_node **link;
 888 #endif
 889   struct xyla_bt_node *btnode;
 890   struct ITER it;
 891   struct RITER rit;
 892   struct PATH path;
 893   unsigned pos;
 894   const char *p;
 895   int opt, ch, rc, sp = 0;
 896   unsigned long i, j, k;
 897 #if TREE == TREAP
 898   size_t wt = 0;
 899 #endif
 900   V( unsigned v; )
 901   unsigned f = 0;
 902 #define f_path 1u
 903 #define f_key 2u
 904 #define f_first 4u
 905 #define f_weight 8u
 906
 907   /* Parse command-line options. */
 908   opt = 1;
 909   for (;;) {
 910     if (opt >= argc) break;
 911     p = argv[opt];
 912     if (*p != '-') break;
 913     p++; if (!*p) break;
 914     if (*p == '-' && !p[1]) { opt++; break; }
 915     for (;;) {
 916 #define GETARG do {                                                     \
 917   if (!*p) {                                                            \
 918     if (opt >= argc) bail(BCAT_ERR, "missing argument");                \
 919     p = argv[++opt];                                                    \
 920   }                                                                     \
 921 } while (0)
 922       switch (*p++) {
 923         case 'o': GETARG; open_file(p, DIR_OUT); goto next_arg;
 924         default: bail(BCAT_ERR, "unknown option `-%c'", p[-1]);
 925       }
 926 #undef GETARG
 927     }
 928   next_arg:
 929     opt++;
 930   }
 931
 932   /* Initialize my node class. */
 933   mycls.ops = &my_ops.node;
 934
 935   /* Initialize the current tree. */
 936   cur.root = 0; H( cur.ht = 0; )
 937
 938   /* Set up the input and output streams. */
 939   if (!out) out = stdout;
 940   if (opt >= argc) in = stdin;
 941   else open_file(argv[opt++], DIR_IN);
 942   V( xyla__verbout = out; )
 943
 944   for (;;) {
 945     do ch = getc(in); while (isspace(ch));
 946     switch (ch) {
 947
 948       case EOF:
 949         if (opt < argc) open_file(argv[opt++], DIR_IN);
 950         else goto done;
 951         break;
 952
 953       case ';': /* comment */
 954         do ch = getc(in); while (ch != EOF && ch != '\n');
 955         break;
 956
 957       case ':': /* print message */
 958         for (;;) {
 959           ch = getc(in); if (ch == '\n' || ch == EOF) break;
 960           putc(ch, out);
 961         }
 962         putc('\n', out);
 963         break;
 964
 965       case '.':
 966         stop = 1;
 967         break;
 968
 969       case '+': /* insert */
 970         if (!(f&f_key)) bail(BCAT_ERR, "no key");
 971         if (!(f&f_path))
 972           node = TREE_PROBE(&mycls, &cur.root, my_ordnav, &k, &path);
 973         else {
 974 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
 975           bail(BCAT_ERR, "placed insertion is out-of-bounds for fuzzers");
 976 #else
 977           if (full_path_p(&path)) bail(BCAT_ERR, "path full");
 978 #endif
 979         }
 980         if (node) bail(BCAT_ERR, "key %lu already present", k);
 981         nodeu = make_node(k);
 982 #if TREE == TREAP
 983         if (f&f_weight) nodeu->my.trp.wt = wt;
 984         else nodeu->my.trp.wt = randwt();
 985 #endif
 986         rc = TREE_INSERT(&mycls, &path, &nodeu->T);
 987           H( if (rc == XYLA_RC_HTCHG) cur.ht++; else )
 988           if (rc)
 989             bail(BCAT_BUG, "insert returned #%s: %s",
 990                  rctag(rc), xyla_strerror(rc));
 991         node = &nodeu->my;
 992         f &= ~(f_key | f_path | f_weight);
 993         break;
 994
 995       case '-': /* remove */
 996         if (f&f_path) {
 997           if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
 998         } else {
 999           if (!(f&f_key)) bail(BCAT_ERR, "no key or path");
1000           node = TREE_PROBE(&mycls, &cur.root, my_ordnav, &k, &path);
1001           if (!node) bail(BCAT_ERR, "key %lu not present", k);
1002         }
1003         rc = TREE_REMOVE(&mycls, &path);
1004           H( if (rc == XYLA_RC_HTCHG) cur.ht--; else )
1005           if (rc)
1006             bail(BCAT_BUG, "remove returned #%s: %s",
1007                  rctag(rc), xyla_strerror(rc));
1008         free_node(node); node = 0; f &= ~(f_key | f_path);
1009         break;
1010
1011       case '#': /* populate */
1012         i = read_int();
1013         do ch = getc(in); while (isspace(ch));
1014         if (ch == '-') j = read_int();
1015         else { ungetc(ch, in); j = i; i = 1; }
1016         for (;;) {
1017           if (!TREE_PROBE(&mycls, &cur.root, my_ordnav, &i, &path)) {
1018             nodeu = make_node(i);
1019 #if TREE == TREAP
1020             nodeu->my.trp.wt = randwt();
1021 #endif
1022             rc = TREE_INSERT(&mycls, &path, &nodeu->T);
1023               H( if (rc == XYLA_RC_HTCHG) cur.ht++; else )
1024               if (rc)
1025                 bail(BCAT_BUG, "insert returned #%s: %s",
1026                      rctag(rc), xyla_strerror(rc));
1027           }
1028           if (i == j) break;
1029           else if (i < j) i++;
1030           else i--;
1031         }
1032         node = 0; f &= ~(f_key | f_path | f_weight);
1033         break;
1034
1035       case '?': /* lookup */
1036         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1037         node = TREE_LOOKUP(&mycls, &cur.root, my_ordnav, &k);
1038         f &= ~(f_key | f_path);
1039         break;
1040
1041       case '@': /* probe */
1042         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1043         node = TREE_PROBE(&mycls, &cur.root, my_ordnav, &k, &path);
1044         f = (f&~f_key) | f_path;
1045         break;
1046
1047       case ',': /* lookup/probe by index */
1048         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1049         ch = getc(in);
1050         switch (ch) {
1051           case '?':
1052             node = TREE_LOOKUP(&mycls, &cur.root, my_idxnav, &k);
1053             f &= ~(f_key | f_path);
1054             break;
1055           case '@':
1056             node = TREE_PROBE(&mycls, &cur.root, my_idxnav, &k, &path);
1057             f = (f&~f_key) | f_path;
1058             break;
1059           default:
1060             bail(BCAT_ERR, "expected `?' or `@', found `%c'", ch);
1061             break;
1062         }
1063         break;
1064
1065       case '[': /* first */
1066         node = TREE_FIRSTPATH(&cur.root, &path);
1067         if (!node) f &= ~f_key;
1068         else { k = node->k; f |= f_key; }
1069         f |= f_path;
1070         break;
1071
1072       case ']': /* last */
1073         node = TREE_LASTPATH(&cur.root, &path);
1074         if (!node) f &= ~f_key;
1075         else { k = node->k; f |= f_key; }
1076         f |= f_path;
1077         break;
1078
1079       case 'c': /* current */
1080         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1081         node = TREE_CURRENT(&path);
1082         if (!node) f &= ~f_key;
1083         else { k = node->k; f |= f_key; }
1084         break;
1085
1086       case '<': /* previous */
1087         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1088         node = TREE_PREVPATH(&path);
1089         if (!node) f &= ~f_key;
1090         else { k = node->k; f |= f_key; }
1091         break;
1092
1093       case '>': /* next */
1094         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1095         node = TREE_NEXTPATH(&path);
1096         if (!node) f &= ~f_key;
1097         else { k = node->k; f |= f_key; }
1098         break;
1099
1100       case '{': /* before */
1101         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1102         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1103         TREE_BEFOREPATH(&path); f &= ~f_key;
1104         break;
1105
1106       case '}': /* after */
1107         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1108         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1109         TREE_AFTERPATH(&path); f &= ~f_key;
1110         break;
1111
1112       case 't': /* root (`top') */
1113         node = TREE_ROOTPATH(&cur.root, &path);
1114         if (!node) f &= ~f_key;
1115         else { k = node->k; f |= f_key; }
1116         f |= f_path;
1117         break;
1118
1119       case 'u': /* up */
1120         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1121         node = TREE_UPPATH(&pos, &path);
1122         switch (pos) {
1123           case XYLA_BTPOS_ROOT: fputs("root\n", out); break;
1124           case XYLA_BTPOS_LEFT: fputs("left\n", out); break;
1125           case XYLA_BTPOS_RIGHT: fputs("right\n", out); break;
1126           default: bail(BCAT_BUG, "unexpected position code %u\n", pos);
1127         }
1128         break;
1129
1130       case 'l': /* left */
1131         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1132         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1133         node = TREE_LEFTPATH(&path);
1134         if (!node) f &= ~f_key;
1135         else { k = node->k; f |= f_key; }
1136         break;
1137
1138       case 'r': /* right */
1139         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1140         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1141         node = TREE_RIGHTPATH(&path);
1142         if (!node) f &= ~f_key;
1143         else { k = node->k; f |= f_key; }
1144         break;
1145
1146       case '*': /* clear */
1147         node = 0; f &= ~(f_key | f_path);
1148         break;
1149
1150       case '(': /* push */
1151         if (sp >= NSTACK) bail(BCAT_ERR, "stack full");
1152         stack[sp++] = cur; cur.root = 0; H( cur.ht = 0; )
1153         node = 0; f &= ~(f_key | f_path | f_weight);
1154         break;
1155
1156       case '"': /* duplicate */
1157         if (sp >= NSTACK) bail(BCAT_ERR, "stack full");
1158         stack[sp++] = cur;
1159         cur.root = (struct xyla_bt_node *)copy_tree(MY_NODEU(cur.root));
1160         node = 0; f &= ~(f_key | f_path | f_weight);
1161         break;
1162
1163       case ')': /* pop */
1164         if (!sp) bail(BCAT_ERR, "stack empty");
1165         free_tree(&cur.root); cur = stack[--sp];
1166         node = 0; f &= ~(f_key | f_path | f_weight);
1167         break;
1168
1169       case '%': /* swap */
1170         if (!sp) bail(BCAT_ERR, "stack empty");
1171         u = stack[sp - 1]; stack[sp - 1] = cur; cur = u;
1172         node = 0; f &= ~(f_key | f_path | f_weight);
1173         break;
1174
1175       case '~': /* join */
1176         if (!sp) bail(BCAT_ERR, "stack empty");
1177         if (!(f&f_key)) t = 0;
1178         else {
1179           t = &make_node(k)->my;
1180 #  if TREE == TREAP
1181           if (f&f_weight) t->trp.wt = wt;
1182           else t->trp.wt = randwt();
1183 #  endif
1184         }
1185 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
1186         x = TREE_LASTPATH(&stack[sp - 1].root, &path);
1187         y = TREE_FIRSTPATH(&cur.root, &path);
1188         if (!t ? x && y && x->k >= y->k
1189                : (x && x->k >= t->k) || (y && t->k >= y->k))
1190           bail(BCAT_ERR, "invalid ordering");
1191 #endif
1192         rc = TREE_JOIN(&mycls, &cur.root HARG(&cur.ht),
1193                        &stack[sp - 1].root HARG(stack[sp - 1].ht),
1194                        t ? &t->bt : 0,
1195                        &cur.root HARG(cur.ht));
1196           if (rc)
1197             bail(BCAT_BUG, "join returned #%s: %s",
1198                  rctag(rc), xyla_strerror(rc));
1199         sp--; node = 0; f &= ~(f_key | f_path | f_weight);
1200         break;
1201
1202       case '/': /* split */
1203         if (sp > NSTACK - 2) bail(BCAT_ERR, "stack full");
1204         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1205         rc = TREE_SPLIT(&mycls, &stack[sp].root HARG(&stack[sp].ht),
1206                         &btnode,
1207                         &cur.root HARG(&cur.ht),
1208                         &path);
1209           if (rc)
1210             bail(BCAT_BUG, "split returned #%s: %s",
1211                  rctag(rc), xyla_strerror(rc));
1212         node = MY_NODE(btnode);
1213         if (node) node->n = 1;
1214         stack[sp + 1].root = node ? &node->bt : 0;
1215         H( stack[sp + 1].ht = node ? 1 : 0; )
1216         sp += 2; f &= ~(f_key | f_path | f_weight);
1217         break;
1218
1219       case '|': /* union/intersection */
1220         if (!sp) bail(BCAT_ERR, "stack empty");
1221         rc = TREE_UNISECT(&mycls, &cur.root HARG(&cur.ht),
1222                           &stack[sp - 1].root HARG(&stack[sp - 1].ht),
1223                           &stack[sp - 1].root HARG(stack[sp - 1].ht),
1224                           &cur.root HARG(cur.ht));
1225           if (rc)
1226             bail(BCAT_BUG, "unisect returned #%s: %s",
1227                  rctag(rc), xyla_strerror(rc));
1228         node = 0; f &= ~(f_key | f_path | f_weight);
1229         break;
1230
1231       case '\\': /* difference/intersection */
1232         if (!sp) bail(BCAT_ERR, "stack empty");
1233         if (sp >= NSTACK) bail(BCAT_ERR, "stack full");
1234         rc = TREE_DIFFSECT(&mycls, &cur.root HARG(&cur.ht),
1235                            &stack[sp].root HARG(&stack[sp].ht),
1236                            &cur.root HARG(cur.ht),
1237                            &stack[sp - 1].root);
1238           if (rc)
1239             bail(BCAT_BUG, "diffsect returned #%s: %s",
1240                  rctag(rc), xyla_strerror(rc));
1241         sp++; node = 0; f &= ~(f_key | f_path | f_weight);
1242         break;
1243
1244       case '^': /* ascend */
1245         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1246         fprintf(out, "%lu\n", (unsigned long)path_index(&path));
1247         break;
1248
1249       case 'k': /* print key */
1250         if (f&f_key) {
1251 #if TREE == TREAP
1252           if (f&f_weight) fprintf(out, "0x%08lx$ ", (unsigned long)wt);
1253 #endif
1254           fprintf(out, "%lu\n", k);
1255         }
1256         else fputs("(no key)\n", out);
1257         break;
1258
1259       case 'n': /* print node */
1260         if (!node) fputs("(nil)\n", out);
1261         else fprintf(out, "#<node #0x%08lx %lu>\n", node->seq, node->k);
1262         break;
1263
1264       case 'p': /* print path */
1265         if (!(f&f_path))
1266           fprintf(out, "(nil)\n");
1267         else {
1268           putc('(', out);
1269 #if TREE == SPLAY
1270           if (path.root == &cur.root) fputs("#<link root -> ", out);
1271           else fprintf(out, "#<link address %p -> ... ", (void *)path.root);
1272           t = MY_SPLAY_NODE(path.node);
1273           if (!t)
1274             fputs("(nil)>", out);
1275           else {
1276             fprintf(out, "node #0x%08lx %lu>", t->seq, t->k);
1277             if (path.f)
1278               fprintf(out, " #<node #0x%08lx %lu %s> -> (nil)",
1279                      t->seq, t->k,
1280                      path.f == XYLA_SPF_LEFT ? "left" : "right");
1281           }
1282 #else
1283           t = 0;
1284           for (i = 0, t = 0; i <= path.k; i++) {
1285             if (i) putc(' ', out);
1286             link = path.p[i];
1287             if (!t && link == &cur.root)
1288               fputs("#<link root -> ", out);
1289             else if (t && link == &t->bt.left)
1290               fprintf(out, "#<link node #0x%08lx %lu left -> ",
1291                       t->seq, t->k);
1292             else if (t && link == &t->bt.right)
1293               fprintf(out, "#<link node #0x%08lx %lu right -> ",
1294                       t->seq, t->k);
1295             else
1296               fprintf(out, "#<link address %p -> ", (void *)link);
1297             t = MY_NODE(*link);
1298             if (!t) fputs("(nil)", out);
1299             else fprintf(out, "node #0x%08lx %lu", t->seq, t->k);
1300             putc('>', out);
1301           }
1302 #endif
1303           putc(')', out); putc('\n', out);
1304         }
1305         break;
1306
1307       case 'i': /* iterate */
1308         TREE_INITITER(cur.root, &it); f |= f_first;
1309         for (;;) {
1310           t = TREE_NEXT(&it); if (!t) break;
1311           if (f&f_first) f &= ~f_first;
1312           else putc(' ', out);
1313           fprintf(out, "%lu", t->k);
1314         }
1315         if (f&f_first) fputs("(empty tree)", out);
1316         putc('\n', out);
1317         break;
1318
1319       case 'j': /* reverse iterate */
1320         TREE_INITRITER(cur.root, &rit); f |= f_first;
1321         for (;;) {
1322           t = TREE_PREV(&rit); if (!t) break;
1323           if (f&f_first) f &= ~f_first;
1324           else putc(' ', out);
1325           fprintf(out, "%lu", t->k);
1326         }
1327         if (f&f_first) fputs("(empty tree)", out);
1328         putc('\n', out);
1329         break;
1330
1331       case 'K': /* list keys */
1332         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_KEYS);
1333         break;
1334
1335       case 'L': /* list */
1336         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_LIST);
1337         break;
1338
1339       case 'D': /* dump */
1340         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_DUMP);
1341         break;
1342
1343       case '!': /* check */
1344         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_NONE);
1345         break;
1346
1347       case '=': /* assign */
1348         free_tree(&cur.root);
1349         cur.root = read_tree(H(&cur.ht));
1350 #if TREE == AVL
1351         if (cur.ht == -1) cur.ht = xyla_avl_height(AVL_NODE(cur.root));
1352 #endif
1353 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
1354         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_NONE | CF_SANITY);
1355 #endif
1356         node = 0; f &= ~(f_key | f_path | f_weight);
1357         break;
1358
1359       case 'S': /* seed */
1360         seed = read_int();
1361         break;
1362
1363       case 'V': /* verbose */
1364         V( v = 0; )
1365         for (;;) {
1366           ch = getc(in);
1367           if (ch == EOF || isspace(ch)) break;
1368           switch (ch) {
1369             case ':':
1370               for (;;) {
1371                 ch = getc(in); if (ch == '\n' || ch == EOF) break;
1372                 NV( putc(ch, out); )
1373               }
1374               NV( putc('\n', out); )
1375               goto skip;
1376             case 'i': V( v |= XYLA__VF_ITER; ) break;
1377             case 'p': V( v |= XYLA__VF_PATH; ) break;
1378             case '@': V( v |= XYLA__VF_PROBE; ) break;
1379             case '+': V( v |= XYLA__VF_INSERT; ) break;
1380             case '-': V( v |= XYLA__VF_REMOVE; ) break;
1381             case '/': V( v |= XYLA__VF_SPLIT; ) break;
1382             case '~': V( v |= XYLA__VF_JOIN; ) break;
1383             case '|': V( v |= XYLA__VF_UNISECT; ) break;
1384             case '\\': V( v |= XYLA__VF_DIFFSECT; ) break;
1385 #if TREE == SPLAY
1386             case 'Z': V( v |= XYLA__VF_SPLAY; ) break;
1387 #endif
1388             default: bail(BCAT_ERR, "unexpected category `%c'", ch);
1389           }
1390         }
1391         V( xyla__verbose = v; )
1392         break;
1393
1394       case 'B': /* rebalance */
1395 #if TREE == SPLAY
1396         xyla_splay_rebalance(&mycls, &cur.root);
1397 #endif
1398         break;
1399
1400       case 'Z': /* splay */
1401         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1402 #if TREE == SPLAY
1403         xyla_splay_splay(&mycls, &path);
1404 #endif
1405         break;
1406
1407 #if TREE == TREAP
1408       case '$': /* weight */
1409         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1410         wt = k; f = (f&~f_key) | f_weight;
1411         break;
1412 #endif
1413
1414       default:
1415         if (isdigit(ch)) /* set key */
1416           { ungetc(ch, in); k = read_int(); f |= f_key; }
1417         else /* error */
1418           bail(BCAT_ERR, "unexpected character `%c'", ch);
1419         break;
1420     }
1421
1422   skip:
1423     check_file(DIR_OUT);
1424   }
1425
1426 done:
1427   /* Free the current tree and all of the stacked trees. */
1428   free_tree(&cur.root);
1429   for (i = 0; i < sp; i++) free_tree(&stack[i].root);
1430
1431   /* Work through the list.  Anything here has mysteriously gone missing
1432    * from all of the trees we've been tracking.
1433    */
1434   if (nodes) {
1435     fputs("leaked nodes...", out);
1436     for (node = nodes; node; node = node->next)
1437       fprintf(out, "\t#0x%08lx %lu\n", node->seq, node->k);
1438     bail(BCAT_BUG, "leaked nodes");
1439   }
1440
1441   /* The user is expected to clear the stack. */
1442   if (sp) bail(BCAT_ERR, "stack not empty");
1443
1444   /* Close the files and make sure all the output actually got out. */
1445   close_file(DIR_IN); close_file(DIR_OUT);
1446
1447   /* It's all over. */
1448   return (0);
1449
1450 #undef f_path
1451 #undef f_key
1452 #undef f_first
1453 #undef f_weight
1454
1455 #undef NSTACK
1456 }
1457
1458 /*----- That's all, folks -------------------------------------------------*/