src/fa.c

   1 /*
   2  * fa.c: finite automata
   3  *
   4  * Copyright (C) 2007-2016 David Lutterkort
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: David Lutterkort <dlutter@redhat.com>
  21  */
  22
  23 /*
  24  * This implementation follows closely the Java dk.brics.automaton package
  25  * by Anders Moeller. The project's website is
  26  * http://www.brics.dk/automaton/.
  27  *
  28  * It is by no means a complete reimplementation of that package; only a
  29  * subset of what Automaton provides is implemented here.
  30  */
  31
  32 #include <config.h>
  33 #include <limits.h>
  34 #include <ctype.h>
  35 #include <stdbool.h>
  36
  37 #include "internal.h"
  38 #include "memory.h"
  39 #include "ref.h"
  40 #include "hash.h"
  41 #include "fa.h"
  42
  43 #define UCHAR_NUM (UCHAR_MAX+1)
  44 #define UCHAR_MIN 0
  45 typedef unsigned char uchar;
  46
  47 #define E(cond) if (cond) goto error
  48 #define F(expr) if ((expr) < 0) goto error
  49
  50 /* Which algorithm to use in FA_MINIMIZE */
  51 int fa_minimization_algorithm = FA_MIN_HOPCROFT;
  52
  53 /* A finite automaton. INITIAL is both the initial state and the head of
  54  * the list of all states. Any state that is allocated for this automaton
  55  * is put on this list. Dead/unreachable states are cleared from the list
  56  * at opportune times (e.g., during minimization) It's poor man's garbage
  57  * collection
  58  *
  59  * Normally, transitions are on a character range [min..max]; in
  60  * fa_as_regexp, we store regexps on transitions in the re field of each
  61  * transition. TRANS_RE indicates that we do that, and is used by fa_dot to
  62  * produce proper graphs of an automaton transitioning on regexps.
  63  *
  64  * For case-insensitive regexps (nocase == 1), the FA never has transitions
  65  * on uppercase letters [A-Z], effectively removing these letters from the
  66  * alphabet.
  67  */
  68 struct fa {
  69     struct state *initial;
  70     int           deterministic : 1;
  71     int           minimal : 1;
  72     unsigned int  nocase : 1;
  73     int           trans_re : 1;
  74 };
  75
  76 /* A state in a finite automaton. Transitions are never shared between
  77    states so that we can free the list when we need to free the state */
  78 struct state {
  79     struct state *next;
  80     hash_val_t    hash;
  81     unsigned int  accept : 1;
  82     unsigned int  live : 1;
  83     unsigned int  reachable : 1;
  84     unsigned int  visited : 1;   /* Used in various places to track progress */
  85     /* Array of transitions. The TUSED first entries are used, the array
  86        has allocated room for TSIZE */
  87     size_t        tused;
  88     size_t        tsize;
  89     struct trans *trans;
  90 };
  91
  92 /* A transition. If the input has a character in the inclusive
  93  * range [MIN, MAX], move to TO
  94  */
  95 struct trans {
  96     struct state *to;
  97     union {
  98         struct {
  99             uchar         min;
 100             uchar         max;
 101         };
 102         struct re *re;
 103     };
 104 };
 105
 106 /*
 107  * Bitsets
 108  */
 109 #define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)
 110
 111 typedef unsigned int bitset;
 112
 113 static bitset *bitset_init(size_t nbits) {
 114     bitset *bs;
 115     if (ALLOC_N(bs, (nbits + UINT_BIT) / UINT_BIT) == -1)
 116         return NULL;
 117     return bs;
 118 }
 119
 120 static inline void bitset_clr(bitset *bs, unsigned int bit) {
 121     bs[bit/UINT_BIT] &= ~(1 << (bit % UINT_BIT));
 122 }
 123
 124 static inline void bitset_set(bitset *bs, unsigned int bit) {
 125     bs[bit/UINT_BIT] |= 1 << (bit % UINT_BIT);
 126 }
 127
 128 ATTRIBUTE_PURE
 129 static inline int bitset_get(const bitset * const bs, unsigned int bit) {
 130     return (bs[bit/UINT_BIT] >> bit % UINT_BIT) & 1;
 131 }
 132
 133 ATTRIBUTE_PURE
 134 static inline bool bitset_disjoint(const bitset *const bs1,
 135                                    const bitset *const bs2,
 136                                    size_t nbits) {
 137     for (int i=0; i < (nbits + UINT_BIT) / UINT_BIT; i++) {
 138         if (bs1[i] & bs2[i])
 139             return false;
 140     }
 141     return true;
 142 }
 143
 144 static void bitset_free(bitset *bs) {
 145     free(bs);
 146 }
 147
 148 static void bitset_negate(bitset *bs, size_t nbits) {
 149     for (int i=0; i < (nbits + UINT_BIT) / UINT_BIT; i++)
 150         bs[i] = ~ bs[i];
 151 }
 152
 153 /*
 154  * Representation of a parsed regular expression. The regular expression is
 155  * parsed according to the following grammar by PARSE_REGEXP:
 156  *
 157  * regexp:        concat_exp ('|' regexp)?
 158  * concat_exp:    repeated_exp concat_exp?
 159  * repeated_exp:  simple_exp
 160  *              | simple_exp '*'
 161  *              | simple_exp '+'
 162  *              | simple_exp '?'
 163  *              | simple_exp '{' INT (',' INT)? '}'
 164  * simple_exp:  char_class
 165  *            | '.'
 166  *            |  '(' regexp ')'
 167  *            |  CHAR
 168  * char_class: '[' char_exp+ ']'
 169  *           | '[' '^' char_exp+ ']'
 170  * char_exp:   CHAR '-' CHAR
 171  *           | CHAR
 172  */
 173
 174 enum re_type {
 175     UNION,
 176     CONCAT,
 177     CSET,
 178     CHAR,
 179     ITER,
 180     EPSILON
 181 };
 182
 183 #define re_unref(r) unref(r, re)
 184
 185 struct re {
 186     ref_t        ref;
 187     enum re_type type;
 188     union {
 189         struct {                  /* UNION, CONCAT */
 190             struct re *exp1;
 191             struct re *exp2;
 192         };
 193         struct {                  /* CSET */
 194             bool    negate;
 195             bitset *cset;
 196             /* Whether we can use character ranges when converting back
 197              * to a string */
 198             unsigned int no_ranges:1;
 199         };
 200         struct {                  /* CHAR */
 201             uchar c;
 202         };
 203         struct {                  /* ITER */
 204             struct re *exp;
 205             int min;
 206             int max;
 207         };
 208     };
 209 };
 210
 211 /* Used to keep state of the regex parse; RX may contain NUL's */
 212 struct re_parse {
 213     const char *rx;          /* Current position in regex */
 214     const char *rend;        /* Last char of rx+ 1 */
 215     int         error;       /* error code */
 216     /* Whether new CSET's should have the no_ranges flag set */
 217     unsigned int no_ranges:1;
 218 };
 219
 220 /* String with explicit length, used when converting re to string */
 221 struct re_str {
 222     char  *rx;
 223     size_t len;
 224 };
 225
 226 static struct re *parse_regexp(struct re_parse *parse);
 227
 228 /* A map from a set of states to a state. */
 229 typedef hash_t state_set_hash;
 230
 231 static hash_val_t ptr_hash(const void *p);
 232
 233 static const int array_initial_size = 4;
 234 static const int array_max_expansion   = 128;
 235
 236 enum state_set_init_flags {
 237     S_NONE   = 0,
 238     S_SORTED = (1 << 0),
 239     S_DATA   = (1 << 1)
 240 };
 241
 242 struct state_set {
 243     size_t            size;
 244     size_t            used;
 245     unsigned int      sorted : 1;
 246     unsigned int      with_data : 1;
 247     struct state    **states;
 248     void            **data;
 249 };
 250
 251 struct state_set_list {
 252     struct state_set_list *next;
 253     struct state_set      *set;
 254 };
 255
 256 /* Clean up FA by removing dead transitions and states and reducing
 257  * transitions. Unreachable states are freed. The return value is the same
 258  * as FA; returning it is merely a convenience.
 259  *
 260  * Only automata in this state should be returned to the user
 261  */
 262 ATTRIBUTE_RETURN_CHECK
 263 static int collect(struct fa *fa);
 264
 265 ATTRIBUTE_RETURN_CHECK
 266 static int totalize(struct fa *fa);
 267
 268 /* Print an FA into a (fairly) fixed file if the environment variable
 269  * FA_DOT_DIR is set. This code is only used for debugging
 270  */
 271 #define FA_DOT_DIR "FA_DOT_DIR"
 272
 273 ATTRIBUTE_UNUSED
 274 static void fa_dot_debug(struct fa *fa, const char *tag) {
 275     const char *dot_dir;
 276     static int count = 0;
 277     int r;
 278     char *fname;
 279     FILE *fp;
 280
 281     if ((dot_dir = getenv(FA_DOT_DIR)) == NULL)
 282         return;
 283
 284     r = asprintf(&fname, "%s/fa_%02d_%s.dot", dot_dir, count++, tag);
 285     if (r == -1)
 286         return;
 287
 288     fp = fopen(fname, "w");
 289     if (fp == NULL) {
 290         free(fname);
 291         return;
 292     }
 293
 294     fa_dot(fp, fa);
 295     fclose(fp);
 296     free(fname);
 297 }
 298
 299 static void print_char_set(struct re *set) {
 300     int from, to;
 301
 302     if (set->negate)
 303         printf("[^");
 304     else
 305         printf("[");
 306     for (from = UCHAR_MIN; from <= UCHAR_MAX; from = to+1) {
 307         while (bitset_get(set->cset, from) == set->negate)
 308             from += 1;
 309         if (from > UCHAR_MAX)
 310             break;
 311         for (to = from;
 312              to < UCHAR_MAX && (bitset_get(set->cset, to+1) == !set->negate);
 313              to++);
 314         if (to == from) {
 315             printf("%c", from);
 316         } else {
 317             printf("%c-%c", from, to);
 318         }
 319     }
 320     printf("]");
 321 }
 322
 323 ATTRIBUTE_UNUSED
 324 static void print_re(struct re *re) {
 325     switch(re->type) {
 326     case UNION:
 327         print_re(re->exp1);
 328         printf("|");
 329         print_re(re->exp2);
 330         break;
 331     case CONCAT:
 332         print_re(re->exp1);
 333         printf(".");
 334         print_re(re->exp2);
 335         break;
 336     case CSET:
 337         print_char_set(re);
 338         break;
 339     case CHAR:
 340         printf("%c", re->c);
 341         break;
 342     case ITER:
 343         printf("(");
 344         print_re(re->exp);
 345         printf("){%d,%d}", re->min, re->max);
 346         break;
 347     case EPSILON:
 348         printf("<>");
 349         break;
 350     default:
 351         printf("(**)");
 352         break;
 353     }
 354 }
 355
 356 /*
 357  * struct re_str
 358  */
 359 static void release_re_str(struct re_str *str) {
 360     if (str == NULL)
 361         return;
 362     FREE(str->rx);
 363     str->len = 0;
 364 }
 365
 366 static void free_re_str(struct re_str *str) {
 367     if (str == NULL)
 368         return;
 369     release_re_str(str);
 370     FREE(str);
 371 }
 372
 373 static struct re_str *make_re_str(const char *s) {
 374     struct re_str *str;
 375
 376     if (ALLOC(str) < 0)
 377         return NULL;
 378     if (s != NULL) {
 379         str->rx = strdup(s);
 380         str->len = strlen(s);
 381         if (str->rx == NULL) {
 382             FREE(str);
 383             return NULL;
 384         }
 385     }
 386     return str;
 387 }
 388
 389 static int re_str_alloc(struct re_str *str) {
 390     return ALLOC_N(str->rx, str->len + 1);
 391 }
 392
 393 /*
 394  * Memory management
 395  */
 396
 397 static void free_trans(struct state *s) {
 398     free(s->trans);
 399     s->trans = NULL;
 400     s->tused = s->tsize = 0;
 401 }
 402
 403 static void gut(struct fa *fa) {
 404     list_for_each(s, fa->initial) {
 405         free_trans(s);
 406     }
 407     list_free(fa->initial);
 408     fa->initial = NULL;
 409 }
 410
 411 void fa_free(struct fa *fa) {
 412     if (fa == NULL)
 413         return;
 414     gut(fa);
 415     free(fa);
 416 }
 417
 418 static struct state *make_state(void) {
 419     struct state *s;
 420     if (ALLOC(s) == -1)
 421         return NULL;
 422     s->hash = ptr_hash(s);
 423     return s;
 424 }
 425
 426 static struct state *add_state(struct fa *fa, int accept) {
 427     struct state *s = make_state();
 428     if (s) {
 429         s->accept = accept;
 430         if (fa->initial == NULL) {
 431             fa->initial = s;
 432         } else {
 433             list_cons(fa->initial->next, s);
 434         }
 435     }
 436     return s;
 437 }
 438
 439 #define last_trans(s)  ((s)->trans + (s)->tused - 1)
 440
 441 #define for_each_trans(t, s)                                            \
 442     for (struct trans *t = (s)->trans;                                  \
 443          (t - (s)->trans) < (s)->tused;                                 \
 444          t++)
 445
 446 ATTRIBUTE_RETURN_CHECK
 447 static int add_new_trans(struct state *from, struct state *to,
 448                          uchar min, uchar max) {
 449     assert(to != NULL);
 450
 451     if (from->tused == from->tsize) {
 452         size_t tsize = from->tsize;
 453         if (tsize == 0)
 454             tsize = array_initial_size;
 455         else if (from->tsize > array_max_expansion)
 456             tsize += array_max_expansion;
 457         else
 458             tsize *= 2;
 459         if (REALLOC_N(from->trans, tsize) == -1)
 460             return -1;
 461         from->tsize = tsize;
 462     }
 463     from->trans[from->tused].to  = to;
 464     from->trans[from->tused].min = min;
 465     from->trans[from->tused].max = max;
 466     from->tused += 1;
 467     return 0;
 468 }
 469
 470 ATTRIBUTE_RETURN_CHECK
 471 static int add_epsilon_trans(struct state *from,
 472                              struct state *to) {
 473     int r;
 474     from->accept |= to->accept;
 475     for_each_trans(t, to) {
 476         r = add_new_trans(from, t->to, t->min, t->max);
 477         if (r < 0)
 478             return -1;
 479     }
 480     return 0;
 481 }
 482
 483 static void set_initial(struct fa *fa, struct state *s) {
 484     list_remove(s, fa->initial);
 485     list_cons(fa->initial, s);
 486 }
 487
 488 /* Merge automaton FA2 into FA1. This simply adds FA2's states to FA1
 489    and then frees FA2. It has no influence on the language accepted by FA1
 490 */
 491 static void fa_merge(struct fa *fa1, struct fa **fa2) {
 492     list_append(fa1->initial, (*fa2)->initial);
 493     free(*fa2);
 494     *fa2 = NULL;
 495 }
 496
 497 /*
 498  * Operations on STATE_SET
 499  */
 500 static void state_set_free(struct state_set *set) {
 501     if (set == NULL)
 502         return;
 503     free(set->states);
 504     free(set->data);
 505     free(set);
 506 }
 507
 508 static int state_set_init_data(struct state_set *set) {
 509     set->with_data = 1;
 510     if (set->data == NULL)
 511         return ALLOC_N(set->data, set->size);
 512     else
 513         return 0;
 514 }
 515
 516 /* Create a new STATE_SET with an initial size of SIZE. If SIZE is -1, use
 517    the default size ARRAY_INITIAL_SIZE. FLAGS is a bitmask indicating
 518    some options:
 519    - S_SORTED: keep the states in the set sorted by their address, and use
 520      binary search for lookups. If it is not set, entries are kept in the
 521      order in which they are added and lookups scan linearly through the
 522      set of states.
 523    - S_DATA: allocate the DATA array in the set, and keep its size in sync
 524      with the size of the STATES array.
 525 */
 526 static struct state_set *state_set_init(int size, int flags) {
 527     struct state_set *set = NULL;
 528
 529     F(ALLOC(set));
 530
 531     set->sorted = (flags & S_SORTED) ? 1 : 0;
 532     set->with_data = (flags & S_DATA) ? 1 : 0;
 533     if (size > 0) {
 534         set->size = size;
 535         F(ALLOC_N(set->states, set->size));
 536         if (set->with_data)
 537             F(state_set_init_data(set));
 538     }
 539     return set;
 540  error:
 541     state_set_free(set);
 542     return NULL;
 543 }
 544
 545 ATTRIBUTE_RETURN_CHECK
 546 static int state_set_expand(struct state_set *set) {
 547     if (set->size == 0)
 548         set->size = array_initial_size;
 549     else if (set->size > array_max_expansion)
 550         set->size += array_max_expansion;
 551     else
 552         set->size *= 2;
 553     if (REALLOC_N(set->states, set->size) < 0)
 554         goto error;
 555     if (set->with_data)
 556         if (REALLOC_N(set->data, set->size) < 0)
 557             goto error;
 558     return 0;
 559  error:
 560     /* We do this to provoke a SEGV as early as possible */
 561     FREE(set->states);
 562     FREE(set->data);
 563     return -1;
 564 }
 565
 566 /* Return the index where S belongs in SET->STATES to keep it sorted.  S
 567    may not be in SET->STATES. The returned index is in the interval [0
 568    .. SET->USED], with the latter indicating that S is larger than all
 569    values in SET->STATES
 570 */
 571 static int state_set_pos(const struct state_set *set, const struct state *s) {
 572     int l = 0, h = set->used;
 573     while (l < h) {
 574         int m = (l + h)/2;
 575         if (set->states[m] > s)
 576             h = m;
 577         else if (set->states[m] < s)
 578             l = m + 1;
 579         else
 580             return m;
 581     }
 582     return l;
 583 }
 584
 585 ATTRIBUTE_RETURN_CHECK
 586 static int state_set_push(struct state_set *set, struct state *s) {
 587     if (set->size == set->used)
 588         if (state_set_expand(set) < 0)
 589             return -1;
 590     if (set->sorted) {
 591         int p = state_set_pos(set, s);
 592         if (set->size == set->used)
 593             if (state_set_expand(set) < 0)
 594                 return -1;
 595         while (p < set->used && set->states[p] <= s)
 596             p += 1;
 597         if (p < set->used) {
 598             memmove(set->states + p + 1, set->states + p,
 599                     sizeof(*set->states) * (set->used - p));
 600             if (set->data != NULL)
 601                 memmove(set->data + p + 1, set->data + p,
 602                         sizeof(*set->data) * (set->used - p));
 603         }
 604         set->states[p] = s;
 605         set->used += 1;
 606         return p;
 607     } else {
 608         set->states[set->used++] = s;
 609         return set->used - 1;
 610     }
 611 }
 612
 613 ATTRIBUTE_RETURN_CHECK
 614 static int state_set_push_data(struct state_set *set, struct state *s,
 615                                void *d) {
 616     int i = state_set_push(set, s);
 617     if (i == -1)
 618         return -1;
 619     set->data[i] = d;
 620     return i;
 621 }
 622
 623 static int state_set_index(const struct state_set *set,
 624                            const struct state *s) {
 625     if (set->sorted) {
 626         int p = state_set_pos(set, s);
 627         return (p < set->used && set->states[p] == s) ? p : -1;
 628     } else {
 629         for (int i=0; i < set->used; i++) {
 630             if (set->states[i] == s)
 631                 return i;
 632         }
 633     }
 634     return -1;
 635 }
 636
 637 static void state_set_remove(struct state_set *set,
 638                              const struct state *s) {
 639    if (set->sorted) {
 640        int p = state_set_index(set, s);
 641        if (p == -1) return;
 642        memmove(set->states + p, set->states + p + 1,
 643                sizeof(*set->states) * (set->used - p - 1));
 644        if (set->data != NULL)
 645            memmove(set->data + p, set->data + p + 1,
 646                    sizeof(*set->data) * (set->used - p - 1));
 647    } else {
 648        int p = state_set_index(set, s);
 649        if (p >= 0) {
 650            set->states[p] = set->states[--set->used];
 651        }
 652    }
 653 }
 654
 655 /* Only add S if it's not in SET yet. Return 1 if S was added, 0 if it was
 656    already in the set and -1 on error. */
 657 ATTRIBUTE_RETURN_CHECK
 658 static int state_set_add(struct state_set *set, struct state *s) {
 659     if (set->sorted) {
 660         int p = state_set_pos(set, s);
 661         if (p < set->used && set->states[p] == s)
 662             return 0;
 663         if (set->size == set->used)
 664             if (state_set_expand(set) < 0)
 665                 return -1;
 666         while (p < set->used && set->states[p] <= s)
 667             p += 1;
 668         if (p < set->used) {
 669             memmove(set->states + p + 1, set->states + p,
 670                     sizeof(*set->states) * (set->used - p));
 671             if (set->data != NULL)
 672                 memmove(set->data + p + 1, set->data + p,
 673                         sizeof(*set->data) * (set->used - p));
 674         }
 675         set->states[p] = s;
 676         set->used += 1;
 677     } else {
 678         if (state_set_index(set, s) >= 0)
 679             return 0;
 680         if (state_set_push(set, s) < 0)
 681             goto error;
 682     }
 683     return 1;
 684  error:
 685     /* We do this to provoke a SEGV as early as possible */
 686     FREE(set->states);
 687     FREE(set->data);
 688     return -1;
 689 }
 690
 691 static struct state *state_set_pop(struct state_set *set) {
 692     struct state *s = NULL;
 693     if (set->used > 0)
 694         s = set->states[--set->used];
 695     return s;
 696 }
 697
 698 static struct state *state_set_pop_data(struct state_set *set, void **d) {
 699     struct state *s = NULL;
 700     s = state_set_pop(set);
 701     *d = set->data[set->used];
 702     return s;
 703 }
 704
 705 static void *state_set_find_data(struct state_set *set, struct state *s) {
 706     int i = state_set_index(set, s);
 707     if (i >= 0)
 708         return set->data[i];
 709     else
 710         return NULL;
 711 }
 712
 713 static int state_set_equal(const struct state_set *set1,
 714                            const struct state_set *set2) {
 715     if (set1->used != set2->used)
 716         return 0;
 717     if (set1->sorted && set2->sorted) {
 718         for (int i = 0; i < set1->used; i++)
 719             if (set1->states[i] != set2->states[i])
 720                 return 0;
 721         return 1;
 722     } else {
 723         for (int i=0; i < set1->used; i++)
 724             if (state_set_index(set2, set1->states[i]) == -1)
 725                 return 0;
 726         return 1;
 727     }
 728 }
 729
 730 #if 0
 731 static void state_set_compact(struct state_set *set) {
 732     while (set->used > 0 && set->states[set->used] == NULL)
 733         set->used -= 1;
 734     for (int i=0; i < set->used; i++) {
 735         if (set->states[i] == NULL) {
 736             set->used -= 1;
 737             set->states[i] = set->states[set->used];
 738             if (set->data)
 739                 set->data[i] = set->data[set->used];
 740         }
 741         while (set->used > 0 && set->states[set->used] == NULL)
 742             set->used -= 1;
 743     }
 744 }
 745 #endif
 746
 747 /* Add an entry (FST, SND) to SET. FST is stored in SET->STATES, and SND is
 748    stored in SET->DATA at the same index.
 749 */
 750 ATTRIBUTE_RETURN_CHECK
 751 static int state_pair_push(struct state_set **set,
 752                            struct state *fst, struct state *snd) {
 753     if (*set == NULL)
 754         *set = state_set_init(-1, S_DATA);
 755     if (*set == NULL)
 756         return -1;
 757     int i = state_set_push(*set, fst);
 758     if (i == -1)
 759         return -1;
 760     (*set)->data[i] = snd;
 761
 762     return 0;
 763 }
 764
 765 /* Return the index of the pair (FST, SND) in SET, or -1 if SET contains no
 766    such pair.
 767  */
 768 static int state_pair_find(struct state_set *set, struct state *fst,
 769                            struct state *snd) {
 770     for (int i=0; i < set->used; i++)
 771         if (set->states[i] == fst && set->data[i] == snd)
 772             return i;
 773     return -1;
 774 }
 775
 776 /* Jenkins' hash for void* */
 777 static hash_val_t ptr_hash(const void *p) {
 778     hash_val_t hash = 0;
 779     char *c = (char *) &p;
 780     for (int i=0; i < sizeof(p); i++) {
 781         hash += c[i];
 782         hash += (hash << 10);
 783         hash ^= (hash >> 6);
 784     }
 785     hash += (hash << 3);
 786     hash ^= (hash >> 11);
 787     hash += (hash << 15);
 788     return hash;
 789 }
 790
 791 typedef hash_t state_triple_hash;
 792
 793 static hash_val_t pair_hash(const void *key) {
 794     register struct state *const *pair = key;
 795     return pair[0]->hash + pair[1]->hash;
 796 }
 797
 798 static int pair_cmp(const void *key1, const void *key2) {
 799     return memcmp(key1, key2, 2*sizeof(struct state *));
 800 }
 801
 802 static void state_triple_node_free(hnode_t *node, ATTRIBUTE_UNUSED void *ctx) {
 803     free((void *) hnode_getkey(node));
 804     free(node);
 805 }
 806
 807 static state_triple_hash *state_triple_init(void) {
 808     state_triple_hash *hash;
 809
 810     hash = hash_create(HASHCOUNT_T_MAX, pair_cmp, pair_hash);
 811     if (hash == NULL)
 812         return NULL;
 813     hash_set_allocator(hash, NULL, state_triple_node_free, NULL);
 814     return hash;
 815 }
 816
 817 ATTRIBUTE_RETURN_CHECK
 818 static int state_triple_push(state_triple_hash *hash,
 819                              struct state *s1,
 820                              struct state *s2,
 821                              struct state *s3) {
 822     struct state **pair;
 823     if (ALLOC_N(pair, 2) < 0)
 824         return -1;
 825     pair[0] = s1;
 826     pair[1] = s2;
 827     return hash_alloc_insert(hash, pair, s3);
 828 }
 829
 830 static struct state * state_triple_thd(state_triple_hash *hash,
 831                                        struct state *s1,
 832                                        struct state *s2) {
 833     struct state *pair[2];
 834     hnode_t *node;
 835     pair[0] = s1;
 836     pair[1] = s2;
 837     node = hash_lookup(hash, pair);
 838     return (node == NULL) ? NULL : (struct state *) hnode_get(node);
 839 }
 840
 841 static void state_triple_free(state_triple_hash *hash) {
 842     if (hash != NULL) {
 843         hash_free_nodes(hash);
 844         hash_destroy(hash);
 845     }
 846 }
 847
 848 /*
 849  * State operations
 850  */
 851 ATTRIBUTE_RETURN_CHECK
 852 static int mark_reachable(struct fa *fa) {
 853     struct state_set *worklist = state_set_init(-1, S_NONE);
 854     int result = -1;
 855
 856     E(worklist == NULL);
 857
 858     list_for_each(s, fa->initial) {
 859         s->reachable = 0;
 860     }
 861     fa->initial->reachable = 1;
 862
 863     for (struct state *s = fa->initial;
 864          s != NULL;
 865          s = state_set_pop(worklist)) {
 866         for_each_trans(t, s) {
 867             if (! t->to->reachable) {
 868                 t->to->reachable = 1;
 869                 F(state_set_push(worklist, t->to));
 870             }
 871         }
 872     }
 873     result = 0;
 874
 875  error:
 876     state_set_free(worklist);
 877     return result;
 878 }
 879
 880 /* Return all reachable states. As a sideeffect, all states have their
 881    REACHABLE flag set appropriately.
 882  */
 883 static struct state_set *fa_states(struct fa *fa) {
 884     struct state_set *visited = state_set_init(-1, S_NONE);
 885     int r;
 886
 887     r = mark_reachable(fa);
 888     E(visited == NULL || r < 0);
 889
 890     list_for_each(s, fa->initial) {
 891         if (s->reachable)
 892             F(state_set_push(visited, s));
 893     }
 894     return visited;
 895  error:
 896     state_set_free(visited);
 897     return NULL;
 898 }
 899
 900 /* Return all reachable accepting states. As a sideeffect, all states have
 901    their REACHABLE flag set appropriately.
 902  */
 903 static struct state_set *fa_accept_states(struct fa *fa) {
 904     struct state_set *accept = state_set_init(-1, S_NONE);
 905     int r;
 906
 907     E(accept == NULL);
 908
 909     r = mark_reachable(fa);
 910     E(r < 0);
 911
 912     list_for_each(s, fa->initial) {
 913         if (s->reachable && s->accept)
 914             F(state_set_push(accept, s));
 915     }
 916     return accept;
 917  error:
 918     state_set_free(accept);
 919     return NULL;
 920 }
 921
 922 /* Mark all live states, i.e. states from which an accepting state can be
 923    reached. All states have their REACHABLE and LIVE flags set
 924    appropriately.
 925  */
 926 ATTRIBUTE_RETURN_CHECK
 927 static int mark_live(struct fa *fa) {
 928     int changed;
 929
 930     F(mark_reachable(fa));
 931
 932     list_for_each(s, fa->initial) {
 933         s->live = s->reachable && s->accept;
 934     }
 935
 936     do {
 937         changed = 0;
 938         list_for_each(s, fa->initial) {
 939             if (! s->live && s->reachable) {
 940                 for_each_trans(t, s) {
 941                     if (t->to->live) {
 942                         s->live = 1;
 943                         changed = 1;
 944                         break;
 945                     }
 946                 }
 947             }
 948         }
 949     } while (changed);
 950     return 0;
 951  error:
 952     return -1;
 953 }
 954
 955 /*
 956  * Reverse an automaton in place. Change FA so that it accepts the
 957  * language that is the reverse of the input automaton.
 958  *
 959  * Returns a list of the new initial states of the automaton. The list must
 960  * be freed by the caller.
 961  */
 962 static struct state_set *fa_reverse(struct fa *fa) {
 963     struct state_set *all = NULL;
 964     struct state_set *accept = NULL;
 965     int r;
 966
 967     all = fa_states(fa);
 968     E(all == NULL);
 969     accept = fa_accept_states(fa);
 970     E(accept == NULL);
 971
 972     F(state_set_init_data(all));
 973
 974     /* Reverse all transitions */
 975     int *tused;
 976     F(ALLOC_N(tused, all->used));
 977     for (int i=0; i < all->used; i++) {
 978         all->data[i] = all->states[i]->trans;
 979         tused[i] = all->states[i]->tused;
 980         all->states[i]->trans = NULL;
 981         all->states[i]->tsize = 0;
 982         all->states[i]->tused = 0;
 983     }
 984     for (int i=0; i < all->used; i++) {
 985         struct state *s = all->states[i];
 986         struct trans *t = all->data[i];
 987         s->accept = 0;
 988         for (int j=0; j < tused[i]; j++) {
 989             r = add_new_trans(t[j].to, s, t[j].min, t[j].max);
 990             if (r < 0)
 991                 goto error;
 992         }
 993         free(t);
 994     }
 995     free(tused);
 996
 997     /* Make new initial and final states */
 998     struct state *s = add_state(fa, 0);
 999     E(s == NULL);
1000
1001     fa->initial->accept = 1;
1002     set_initial(fa, s);
1003     for (int i=0; i < accept->used; i++) {
1004         r = add_epsilon_trans(s, accept->states[i]);
1005         if (r < 0)
1006             goto error;
1007     }
1008
1009     fa->deterministic = 0;
1010     fa->minimal = 0;
1011     state_set_free(all);
1012     return accept;
1013  error:
1014     state_set_free(all);
1015     state_set_free(accept);
1016     return NULL;
1017 }
1018
1019 /*
1020  * Return a sorted array of all interval start points in FA. The returned
1021  * array is a string (null terminated)
1022  */
1023 static uchar* start_points(struct fa *fa, int *npoints) {
1024     char pointset[UCHAR_NUM];
1025     uchar *points = NULL;
1026
1027     F(mark_reachable(fa));
1028     MEMZERO(pointset, UCHAR_NUM);
1029     list_for_each(s, fa->initial) {
1030         if (! s->reachable)
1031             continue;
1032         pointset[0] = 1;
1033         for_each_trans(t, s) {
1034             pointset[t->min] = 1;
1035             if (t->max < UCHAR_MAX)
1036                 pointset[t->max+1] = 1;
1037         }
1038     }
1039
1040     *npoints = 0;
1041     for(int i=0; i < UCHAR_NUM; *npoints += pointset[i], i++);
1042
1043     F(ALLOC_N(points, *npoints+1));
1044     for (int i=0, n=0; i < UCHAR_NUM; i++) {
1045         if (pointset[i])
1046             points[n++] = (uchar) i;
1047     }
1048
1049     return points;
1050  error:
1051     free(points);
1052     return NULL;
1053 }
1054
1055 /*
1056  * Operations on STATE_SET_HASH
1057  */
1058 static int state_set_hash_contains(state_set_hash *smap,
1059                                struct state_set *set) {
1060     return hash_lookup(smap, set) != NULL;
1061 }
1062
1063 /*
1064  * Find the set in SMAP that has the same states as SET. If the two are
1065  * different, i.e. they point to different memory locations, free SET and
1066  * return the set found in SMAP
1067  */
1068 static struct state_set *state_set_hash_uniq(state_set_hash *smap,
1069                                              struct state_set *set) {
1070     hnode_t *node = hash_lookup(smap, set);
1071     const struct state_set *orig_set = hnode_getkey(node);
1072     if (orig_set != set) {
1073         state_set_free(set);
1074     }
1075     return (struct state_set *) orig_set;
1076 }
1077
1078 static struct state *state_set_hash_get_state(state_set_hash *smap,
1079                                              struct state_set *set) {
1080     hnode_t *node = hash_lookup(smap, set);
1081     return (struct state *) hnode_get(node);
1082 }
1083
1084 static hash_val_t set_hash(const void *key) {
1085     hash_val_t hash = 0;
1086     const struct state_set *set = key;
1087
1088     for (int i = 0; i < set->used; i++) {
1089         hash += set->states[i]->hash;
1090     }
1091     return hash;
1092 }
1093
1094 static int set_cmp(const void *key1, const void *key2) {
1095     const struct state_set *set1 = key1;
1096     const struct state_set *set2 = key2;
1097
1098     return state_set_equal(set1, set2) ? 0 : 1;
1099 }
1100
1101 static void set_destroy(hnode_t *node, ATTRIBUTE_UNUSED void *ctx) {
1102     struct state_set *set = (struct state_set *) hnode_getkey(node);
1103     state_set_free(set);
1104     free(node);
1105 }
1106
1107 ATTRIBUTE_RETURN_CHECK
1108 static int state_set_hash_add(state_set_hash **smap,
1109                               struct state_set *set, struct fa *fa) {
1110     if (*smap == NULL) {
1111         *smap = hash_create(HASHCOUNT_T_MAX, set_cmp, set_hash);
1112         E(*smap == NULL);
1113         hash_set_allocator(*smap, NULL, set_destroy, NULL);
1114     }
1115     struct state *s = add_state(fa, 0);
1116     E(s == NULL);
1117     F(hash_alloc_insert(*smap, set, s));
1118     return 0;
1119  error:
1120     return -1;
1121 }
1122
1123 static void state_set_hash_free(state_set_hash *smap,
1124                                 struct state_set *protect) {
1125     if (protect != NULL) {
1126         hnode_t *node = hash_lookup(smap, protect);
1127         hash_delete(smap, node);
1128         hnode_getkey(node) = NULL;
1129         set_destroy(node, NULL);
1130     }
1131     hash_free_nodes(smap);
1132     hash_destroy(smap);
1133 }
1134
1135 static int state_set_list_add(struct state_set_list **list,
1136                               struct state_set *set) {
1137     struct state_set_list *elt;
1138     if (ALLOC(elt) < 0)
1139         return -1;
1140     elt->set = set;
1141     list_cons(*list, elt);
1142     return 0;
1143 }
1144
1145 static struct state_set *state_set_list_pop(struct state_set_list **list) {
1146     struct state_set_list *elt = *list;
1147     struct state_set      *set = elt->set;
1148
1149     *list = elt->next;
1150     free(elt);
1151     return set;
1152 }
1153
1154 /* Compare transitions lexicographically by (to, min, reverse max) */
1155 static int trans_to_cmp(const void *v1, const void *v2) {
1156     const struct trans *t1 = v1;
1157     const struct trans *t2 = v2;
1158
1159     if (t1->to != t2->to) {
1160         return (t1->to < t2->to) ? -1 : 1;
1161     }
1162     if (t1->min < t2->min)
1163         return -1;
1164     if (t1->min > t2->min)
1165         return 1;
1166     if (t1->max > t2->max)
1167         return -1;
1168     return (t1->max < t2->max) ? 1 : 0;
1169 }
1170
1171 /* Compare transitions lexicographically by (min, reverse max, to) */
1172 static int trans_intv_cmp(const void *v1, const void *v2) {
1173     const struct trans *t1 = v1;
1174     const struct trans *t2 = v2;
1175
1176     if (t1->min < t2->min)
1177         return -1;
1178     if (t1->min > t2->min)
1179         return 1;
1180     if (t1->max > t2->max)
1181         return -1;
1182     if (t1->max < t2->max)
1183         return 1;
1184     if (t1->to != t2->to) {
1185         return (t1->to < t2->to) ? -1 : 1;
1186     }
1187     return 0;
1188 }
1189
1190 /*
1191  * Reduce an automaton by combining overlapping and adjacent edge intervals
1192  * with the same destination.
1193  */
1194 static void reduce(struct fa *fa) {
1195     list_for_each(s, fa->initial) {
1196         if (s->tused == 0)
1197             continue;
1198
1199         qsort(s->trans, s->tused, sizeof(*s->trans), trans_to_cmp);
1200         int i=0, j=1;
1201         struct trans *t = s->trans;
1202         while (j < s->tused) {
1203             if (t[i].to == t[j].to && t[j].min <= t[i].max + 1) {
1204                 if (t[j].max > t[i].max)
1205                     t[i].max = t[j].max;
1206                 j += 1;
1207             } else {
1208                 i += 1;
1209                 if (i < j)
1210                     memmove(s->trans + i, s->trans + j,
1211                             sizeof(*s->trans) * (s->tused - j));
1212                 s->tused -= j - i;
1213                 j = i + 1;
1214             }
1215         }
1216         s->tused = i+1;
1217         /* Shrink if we use less than half the allocated size */
1218         if (s->tsize > array_initial_size && 2*s->tused < s->tsize) {
1219             int r;
1220             r = REALLOC_N(s->trans, s->tsize);
1221             if (r == 0)
1222                 s->tsize = s->tused;
1223         }
1224     }
1225 }
1226
1227 /*
1228  * Remove dead transitions from an FA; a transition is dead is it does not
1229  * lead to a live state. This also removes any states that are not
1230  * reachable any longer from FA->INITIAL.
1231  *
1232  * Returns the same FA as a convenience
1233  */
1234
1235 static void collect_trans(struct fa *fa) {
1236     list_for_each(s, fa->initial) {
1237         if (! s->live) {
1238             free_trans(s);
1239         } else {
1240             int i=0;
1241             while (i < s->tused) {
1242                 if (! s->trans[i].to->live) {
1243                     s->tused -= 1;
1244                     memmove(s->trans + i, s->trans + s->tused,
1245                             sizeof(*s->trans));
1246                 } else {
1247                     i += 1;
1248                 }
1249             }
1250         }
1251     }
1252 }
1253
1254 static void collect_dead_states(struct fa *fa) {
1255     /* Remove all dead states and free their storage */
1256     for (struct state *s = fa->initial; s->next != NULL; ) {
1257         if (! s->next->live) {
1258             struct state *del = s->next;
1259             s->next = del->next;
1260             free_trans(del);
1261             free(del);
1262         } else {
1263             s = s->next;
1264         }
1265     }
1266 }
1267
1268 static int collect(struct fa *fa) {
1269     F(mark_live(fa));
1270
1271     if (! fa->initial->live) {
1272         /* This automaton accepts nothing, make it the canonical
1273          * epsilon automaton
1274          */
1275         list_for_each(s, fa->initial) {
1276             free_trans(s);
1277         }
1278         list_free(fa->initial->next);
1279         fa->deterministic = 1;
1280     } else {
1281         collect_trans(fa);
1282         collect_dead_states(fa);
1283     }
1284     reduce(fa);
1285     return 0;
1286  error:
1287     return -1;
1288 }
1289
1290 static void swap_initial(struct fa *fa) {
1291     struct state *s = fa->initial;
1292     if (s->next != NULL) {
1293         fa->initial = s->next;
1294         s->next = fa->initial->next;
1295         fa->initial->next = s;
1296     }
1297 }
1298
1299 /*
1300  * Make a finite automaton deterministic using the given set of initial
1301  * states with the subset construction. This also eliminates dead states
1302  * and transitions and reduces and orders the transitions for each state
1303  */
1304 static int determinize(struct fa *fa, struct state_set *ini) {
1305     int npoints;
1306     int make_ini = (ini == NULL);
1307     const uchar *points = NULL;
1308     state_set_hash *newstate = NULL;
1309     struct state_set_list *worklist = NULL;
1310     int ret = 0;
1311
1312     if (fa->deterministic)
1313         return 0;
1314
1315     points = start_points(fa, &npoints);
1316     E(points == NULL);
1317     if (make_ini) {
1318         ini = state_set_init(-1, S_NONE);
1319         if (ini == NULL || state_set_push(ini, fa->initial) < 0) {
1320             state_set_free(ini);
1321             goto error;
1322         }
1323     }
1324
1325     F(state_set_list_add(&worklist, ini));
1326     F(state_set_hash_add(&newstate, ini, fa));
1327     // Make the new state the initial state
1328     swap_initial(fa);
1329     while (worklist != NULL) {
1330         struct state_set *sset = state_set_list_pop(&worklist);
1331         struct state *r = state_set_hash_get_state(newstate, sset);
1332         for (int q=0; q < sset->used; q++) {
1333             r->accept |= sset->states[q]->accept;
1334         }
1335         for (int n=0; n < npoints; n++) {
1336             struct state_set *pset = state_set_init(-1, S_SORTED);
1337             E(pset == NULL);
1338             for(int q=0 ; q < sset->used; q++) {
1339                 for_each_trans(t, sset->states[q]) {
1340                     if (t->min <= points[n] && points[n] <= t->max) {
1341                         F(state_set_add(pset, t->to));
1342                     }
1343                 }
1344             }
1345             if (!state_set_hash_contains(newstate, pset)) {
1346                 F(state_set_list_add(&worklist, pset));
1347                 F(state_set_hash_add(&newstate, pset, fa));
1348             }
1349             pset = state_set_hash_uniq(newstate, pset);
1350
1351             struct state *q = state_set_hash_get_state(newstate, pset);
1352             uchar min = points[n];
1353             uchar max = UCHAR_MAX;
1354             if (n+1 < npoints)
1355                 max = points[n+1] - 1;
1356             if (add_new_trans(r, q, min, max) < 0)
1357                 goto error;
1358         }
1359     }
1360     fa->deterministic = 1;
1361
1362  done:
1363     if (newstate)
1364         state_set_hash_free(newstate, make_ini ? NULL : ini);
1365     free((void *) points);
1366     if (collect(fa) < 0)
1367         ret = -1;
1368     return ret;
1369  error:
1370     ret = -1;
1371     goto done;
1372 }
1373
1374 /*
1375  * Minimization. As a sideeffect of minimization, the transitions are
1376  * reduced and ordered.
1377  */
1378
1379 static struct state *step(struct state *s, uchar c) {
1380     for_each_trans(t, s) {
1381         if (t->min <= c && c <= t->max)
1382             return t->to;
1383     }
1384     return NULL;
1385 }
1386
1387 struct state_list {
1388     struct state_list_node *first;
1389     struct state_list_node *last;
1390     unsigned int            size;
1391 };
1392
1393 struct state_list_node {
1394     struct state_list      *sl;
1395     struct state_list_node *next;
1396     struct state_list_node *prev;
1397     struct state           *state;
1398 };
1399
1400 static struct state_list_node *state_list_add(struct state_list *sl,
1401                                               struct state *s) {
1402     struct state_list_node *n;
1403
1404     if (ALLOC(n) < 0)
1405         return NULL;
1406
1407     n->state = s;
1408     n->sl = sl;
1409
1410     if (sl->size++ == 0) {
1411         sl->first = n;
1412         sl->last = n;
1413     } else {
1414         sl->last->next = n;
1415         n->prev = sl->last;
1416         sl->last = n;
1417     }
1418     return n;
1419 }
1420
1421 static void state_list_remove(struct state_list_node *n) {
1422     struct state_list *sl = n->sl;
1423     sl->size -= 1;
1424     if (sl->first == n)
1425         sl->first = n->next;
1426     else
1427         n->prev->next = n->next;
1428     if (sl->last == n)
1429         sl->last = n->prev;
1430     else
1431         n->next->prev = n->prev;
1432
1433     free(n);
1434 }
1435
1436 static void state_list_free(struct state_list *sl) {
1437     if (sl)
1438         list_free(sl->first);
1439     free(sl);
1440 }
1441
1442 /* The linear index of element (q,c) in an NSTATES * NSIGMA matrix */
1443 #define INDEX(q, c) (q * nsigma + c)
1444
1445 static int minimize_hopcroft(struct fa *fa) {
1446     struct state_set *states = NULL;
1447     uchar *sigma = NULL;
1448     struct state_set **reverse = NULL;
1449     bitset *reverse_nonempty = NULL;
1450     struct state_set **partition = NULL;
1451     unsigned int *block = NULL;
1452     struct state_list **active = NULL;
1453     struct state_list_node **active2 = NULL;
1454     int *pending = NULL;
1455     bitset *pending2 = NULL;
1456     struct state_set *split = NULL;
1457     bitset *split2 = NULL;
1458     int *refine = NULL;
1459     bitset *refine2 = NULL;
1460     struct state_set **splitblock = NULL;
1461     struct state_set *newstates = NULL;
1462     int *nsnum = NULL;
1463     int *nsind = NULL;
1464     int result = -1;
1465     unsigned int nstates = 0;
1466     int nsigma = 0;
1467
1468     F(determinize(fa, NULL));
1469
1470     /* Total automaton, nothing to do */
1471     if (fa->initial->tused == 1
1472         && fa->initial->trans[0].to == fa->initial
1473         && fa->initial->trans[0].min == UCHAR_MIN
1474         && fa->initial->trans[0].max == UCHAR_MAX)
1475         return 0;
1476
1477     F(totalize(fa));
1478
1479     /* make arrays for numbered states and effective alphabet */
1480     states = state_set_init(-1, S_NONE);
1481     E(states == NULL);
1482
1483     list_for_each(s, fa->initial) {
1484         F(state_set_push(states, s));
1485     }
1486     nstates = states->used;
1487
1488     sigma = start_points(fa, &nsigma);
1489     E(sigma == NULL);
1490
1491     /* initialize data structures */
1492
1493     /* An ss->used x nsigma matrix of lists of states */
1494     F(ALLOC_N(reverse, nstates * nsigma));
1495     reverse_nonempty = bitset_init(nstates * nsigma);
1496     E(reverse_nonempty == NULL);
1497     F(ALLOC_N(partition, nstates));
1498     F(ALLOC_N(block, nstates));
1499
1500     F(ALLOC_N(active, nstates * nsigma));
1501     F(ALLOC_N(active2, nstates * nsigma));
1502
1503     /* PENDING is an array of pairs of ints. The i'th pair is stored in
1504      * PENDING[2*i] and PENDING[2*i + 1]. There are NPENDING pairs in
1505      * PENDING at any time. SPENDING is the maximum number of pairs
1506      * allocated for PENDING.
1507      */
1508     size_t npending = 0, spending = 0;
1509     pending2 = bitset_init(nstates * nsigma);
1510     E(pending2 == NULL);
1511
1512     split = state_set_init(-1, S_NONE);
1513     split2 = bitset_init(nstates);
1514     E(split == NULL || split2 == NULL);
1515
1516     F(ALLOC_N(refine, nstates));
1517     refine2 = bitset_init(nstates);
1518     E(refine2 == NULL);
1519
1520     F(ALLOC_N(splitblock, nstates));
1521
1522     for (int q = 0; q < nstates; q++) {
1523         splitblock[q] = state_set_init(-1, S_NONE);
1524         partition[q] = state_set_init(-1, S_NONE);
1525         E(splitblock[q] == NULL || partition[q] == NULL);
1526         for (int x = 0; x < nsigma; x++) {
1527             reverse[INDEX(q, x)] = state_set_init(-1, S_NONE);
1528             E(reverse[INDEX(q, x)] == NULL);
1529             F(ALLOC_N(active[INDEX(q, x)], 1));
1530         }
1531     }
1532
1533     /* find initial partition and reverse edges */
1534     for (int q = 0; q < nstates; q++) {
1535         struct state *qq = states->states[q];
1536         int j;
1537         if (qq->accept)
1538             j = 0;
1539         else
1540             j = 1;
1541         F(state_set_push(partition[j], qq));
1542         block[q] = j;
1543         for (int x = 0; x < nsigma; x++) {
1544             uchar y = sigma[x];
1545             struct state *p = step(qq, y);
1546             assert(p != NULL);
1547             int pn = state_set_index(states, p);
1548             assert(pn >= 0);
1549             F(state_set_push(reverse[INDEX(pn, x)], qq));
1550             bitset_set(reverse_nonempty, INDEX(pn, x));
1551         }
1552     }
1553
1554     /* initialize active sets */
1555     for (int j = 0; j <= 1; j++)
1556         for (int x = 0; x < nsigma; x++)
1557             for (int q = 0; q < partition[j]->used; q++) {
1558                 struct state *qq = partition[j]->states[q];
1559                 int qn = state_set_index(states, qq);
1560                 if (bitset_get(reverse_nonempty, INDEX(qn, x))) {
1561                     active2[INDEX(qn, x)] =
1562                         state_list_add(active[INDEX(j, x)], qq);
1563                     E(active2[INDEX(qn, x)] == NULL);
1564                 }
1565             }
1566
1567     /* initialize pending */
1568     F(ALLOC_N(pending, 2*nsigma));
1569     npending = nsigma;
1570     spending = nsigma;
1571     for (int x = 0; x < nsigma; x++) {
1572         int a0 = active[INDEX(0,x)]->size;
1573         int a1 = active[INDEX(1,x)]->size;
1574         int j;
1575         if (a0 <= a1)
1576             j = 0;
1577         else
1578             j = 1;
1579         pending[2*x] = j;
1580         pending[2*x+1] = x;
1581         bitset_set(pending2, INDEX(j, x));
1582     }
1583
1584     /* process pending until fixed point */
1585     int k = 2;
1586     while (npending-- > 0) {
1587         int p = pending[2*npending];
1588         int x = pending[2*npending+1];
1589         bitset_clr(pending2, INDEX(p, x));
1590         int ref = 0;
1591         /* find states that need to be split off their blocks */
1592         struct state_list *sh = active[INDEX(p,x)];
1593         for (struct state_list_node *m = sh->first; m != NULL; m = m->next) {
1594             int q = state_set_index(states, m->state);
1595             struct state_set *rev = reverse[INDEX(q, x)];
1596             for (int r =0; r < rev->used; r++) {
1597                 struct state *rs = rev->states[r];
1598                 int s = state_set_index(states, rs);
1599                 if (! bitset_get(split2, s)) {
1600                     bitset_set(split2, s);
1601                     F(state_set_push(split, rs));
1602                     int j = block[s];
1603                     F(state_set_push(splitblock[j], rs));
1604                     if (!bitset_get(refine2, j)) {
1605                         bitset_set(refine2, j);
1606                         refine[ref++] = j;
1607                     }
1608                 }
1609             }
1610         }
1611         // refine blocks
1612         for(int rr=0; rr < ref; rr++) {
1613             int j = refine[rr];
1614             struct state_set *sp = splitblock[j];
1615             if (sp->used < partition[j]->used) {
1616                 struct state_set *b1 = partition[j];
1617                 struct state_set *b2 = partition[k];
1618                 for (int s = 0; s < sp->used; s++) {
1619                     state_set_remove(b1, sp->states[s]);
1620                     F(state_set_push(b2, sp->states[s]));
1621                     int snum = state_set_index(states, sp->states[s]);
1622                     block[snum] = k;
1623                     for (int c = 0; c < nsigma; c++) {
1624                         struct state_list_node *sn = active2[INDEX(snum, c)];
1625                         if (sn != NULL && sn->sl == active[INDEX(j,c)]) {
1626                             state_list_remove(sn);
1627                             active2[INDEX(snum, c)] =
1628                                 state_list_add(active[INDEX(k, c)],
1629                                                sp->states[s]);
1630                             E(active2[INDEX(snum, c)] == NULL);
1631                         }
1632                     }
1633                 }
1634                 // update pending
1635                 for (int c = 0; c < nsigma; c++) {
1636                     int aj = active[INDEX(j, c)]->size;
1637                     int ak = active[INDEX(k, c)]->size;
1638                     if (npending + 1 > spending) {
1639                         spending *= 2;
1640                         F(REALLOC_N(pending, 2 * spending));
1641                     }
1642                     pending[2*npending + 1] = c;
1643                     if (!bitset_get(pending2, INDEX(j, c))
1644                         && 0 < aj && aj <= ak) {
1645                         bitset_set(pending2, INDEX(j, c));
1646                         pending[2*npending] = j;
1647                     } else {
1648                         bitset_set(pending2, INDEX(k, c));
1649                         pending[2*npending] = k;
1650                     }
1651                     npending += 1;
1652                 }
1653                 k++;
1654             }
1655             for (int s = 0; s < sp->used; s++) {
1656                 int snum = state_set_index(states, sp->states[s]);
1657                 bitset_clr(split2, snum);
1658             }
1659             bitset_clr(refine2, j);
1660             sp->used = 0;
1661         }
1662         split->used = 0;
1663     }
1664
1665     /* make a new state for each equivalence class, set initial state */
1666     newstates = state_set_init(k, S_NONE);
1667     E(newstates == NULL);
1668     F(ALLOC_N(nsnum, k));
1669     F(ALLOC_N(nsind, nstates));
1670
1671     for (int n = 0; n < k; n++) {
1672         struct state *s = make_state();
1673         E(s == NULL);
1674         newstates->states[n] = s;
1675         struct state_set *partn = partition[n];
1676         for (int q=0; q < partn->used; q++) {
1677             struct state *qs = partn->states[q];
1678             int qnum = state_set_index(states, qs);
1679             if (qs == fa->initial)
1680                 s->live = 1;     /* Abuse live to flag the new initial state */
1681             nsnum[n] = qnum;     /* select representative */
1682             nsind[qnum] = n;     /* and point from partition to new state */
1683         }
1684     }
1685
1686     /* build transitions and set acceptance */
1687     for (int n = 0; n < k; n++) {
1688         struct state *s = newstates->states[n];
1689         s->accept = states->states[nsnum[n]]->accept;
1690         for_each_trans(t, states->states[nsnum[n]]) {
1691             int toind = state_set_index(states, t->to);
1692             struct state *nto = newstates->states[nsind[toind]];
1693             F(add_new_trans(s, nto, t->min, t->max));
1694         }
1695     }
1696
1697     /* Get rid of old states and transitions and turn NEWTSTATES into
1698        a linked list */
1699     gut(fa);
1700     for (int n=0; n < k; n++)
1701         if (newstates->states[n]->live) {
1702             struct state *ini = newstates->states[n];
1703             newstates->states[n] = newstates->states[0];
1704             newstates->states[0] = ini;
1705         }
1706     for (int n=0; n < k-1; n++)
1707         newstates->states[n]->next = newstates->states[n+1];
1708     fa->initial = newstates->states[0];
1709
1710     result = 0;
1711
1712     /* clean up */
1713  done:
1714     free(nsind);
1715     free(nsnum);
1716     state_set_free(states);
1717     free(sigma);
1718     bitset_free(reverse_nonempty);
1719     free(block);
1720     for (int i=0; i < nstates*nsigma; i++) {
1721         if (reverse)
1722             state_set_free(reverse[i]);
1723         if (active)
1724             state_list_free(active[i]);
1725     }
1726     free(reverse);
1727     free(active);
1728     free(active2);
1729     free(pending);
1730     bitset_free(pending2);
1731     state_set_free(split);
1732     bitset_free(split2);
1733     free(refine);
1734     bitset_free(refine2);
1735     for (int q=0; q < nstates; q++) {
1736         if (splitblock)
1737             state_set_free(splitblock[q]);
1738         if (partition)
1739             state_set_free(partition[q]);
1740     }
1741     free(splitblock);
1742     free(partition);
1743     state_set_free(newstates);
1744
1745     if (collect(fa) < 0)
1746         result = -1;
1747     return result;
1748  error:
1749     result = -1;
1750     goto done;
1751 }
1752
1753 static int minimize_brzozowski(struct fa *fa) {
1754     struct state_set *set;
1755
1756     /* Minimize using Brzozowski's algorithm */
1757     set = fa_reverse(fa);
1758     E(set == NULL);
1759     F(determinize(fa, set));
1760     state_set_free(set);
1761
1762     set = fa_reverse(fa);
1763     E(set == NULL);
1764     F(determinize(fa, set));
1765     state_set_free(set);
1766     return 0;
1767  error:
1768     return -1;
1769 }
1770
1771 int fa_minimize(struct fa *fa) {
1772     int r;
1773
1774     if (fa == NULL)
1775         return -1;
1776     if (fa->minimal)
1777         return 0;
1778
1779     if (fa_minimization_algorithm == FA_MIN_BRZOZOWSKI) {
1780         r = minimize_brzozowski(fa);
1781     } else {
1782         r = minimize_hopcroft(fa);
1783     }
1784
1785     if (r == 0)
1786         fa->minimal = 1;
1787     return r;
1788 }
1789
1790 /*
1791  * Construction of fa
1792  */
1793
1794 static struct fa *fa_make_empty(void) {
1795     struct fa *fa;
1796
1797     if (ALLOC(fa) < 0)
1798         return NULL;
1799     if (add_state(fa, 0) == NULL) {
1800         fa_free(fa);
1801         return NULL;
1802     }
1803     /* Even though, technically, this fa is both minimal and deterministic,
1804      * this function is also used to allocate new fa's which are then modified
1805      * further. Rather than risk erroneously marking such an fa as minimal
1806      * and deterministic, we do not do that here and take the minor hit if
1807      * that should ever need to be determined for an actual empty fa
1808      */
1809     return fa;
1810 }
1811
1812 static struct fa *fa_make_epsilon(void) {
1813     struct fa *fa = fa_make_empty();
1814     if (fa) {
1815         fa->initial->accept = 1;
1816         fa->deterministic= 1;
1817         fa->minimal = 1;
1818     }
1819     return fa;
1820 }
1821
1822 static struct fa *fa_make_char(uchar c) {
1823     struct fa *fa = fa_make_empty();
1824     if (! fa)
1825         return NULL;
1826
1827     struct state *s = fa->initial;
1828     struct state *t = add_state(fa, 1);
1829     int r;
1830
1831     if (t == NULL)
1832         goto error;
1833
1834     r = add_new_trans(s, t, c, c);
1835     if (r < 0)
1836         goto error;
1837     fa->deterministic = 1;
1838     fa->minimal = 1;
1839     return fa;
1840  error:
1841     fa_free(fa);
1842     return NULL;
1843 }
1844
1845 struct fa *fa_make_basic(unsigned int basic) {
1846     int r;
1847
1848     if (basic == FA_EMPTY) {
1849         return fa_make_empty();
1850     } else if (basic == FA_EPSILON) {
1851         return fa_make_epsilon();
1852     } else if (basic == FA_TOTAL) {
1853         struct fa *fa = fa_make_epsilon();
1854         r = add_new_trans(fa->initial, fa->initial, UCHAR_MIN, UCHAR_MAX);
1855         if (r < 0) {
1856             fa_free(fa);
1857             fa = NULL;
1858         }
1859         return fa;
1860     }
1861     return NULL;
1862 }
1863
1864 int fa_is_basic(struct fa *fa, unsigned int basic) {
1865     if (basic == FA_EMPTY) {
1866         return ! fa->initial->accept && fa->initial->tused == 0;
1867     } else if (basic == FA_EPSILON) {
1868         return fa->initial->accept && fa->initial->tused == 0;
1869     } else if (basic == FA_TOTAL) {
1870         if (! fa->initial->accept)
1871             return 0;
1872         if (fa->nocase) {
1873             if (fa->initial->tused != 2)
1874                 return 0;
1875             struct trans *t1 = fa->initial->trans;
1876             struct trans *t2 = fa->initial->trans + 1;
1877             if (t1->to != fa->initial || t2->to != fa->initial)
1878                 return 0;
1879             if (t2->max != UCHAR_MAX) {
1880                 t1 = t2;
1881                 t2 = fa->initial->trans;
1882             }
1883             return (t1->min == UCHAR_MIN && t1->max == 'A' - 1 &&
1884                     t2->min == 'Z' + 1 && t2->max == UCHAR_MAX);
1885         } else {
1886             struct trans *t = fa->initial->trans;
1887             return fa->initial->tused == 1 &&
1888                 t->to == fa->initial &&
1889                 t->min == UCHAR_MIN && t->max == UCHAR_MAX;
1890         }
1891     }
1892     return 0;
1893 }
1894
1895 static struct fa *fa_clone(struct fa *fa) {
1896     struct fa *result = NULL;
1897     struct state_set *set = state_set_init(-1, S_DATA|S_SORTED);
1898     int r;
1899
1900     if (fa == NULL || set == NULL || ALLOC(result) < 0)
1901         goto error;
1902
1903     result->deterministic = fa->deterministic;
1904     result->minimal = fa->minimal;
1905     result->nocase = fa->nocase;
1906     list_for_each(s, fa->initial) {
1907         int i = state_set_push(set, s);
1908         E(i < 0);
1909
1910         struct state *q = add_state(result, s->accept);
1911         if (q == NULL)
1912             goto error;
1913         set->data[i] = q;
1914         q->live = s->live;
1915         q->reachable = s->reachable;
1916     }
1917     for (int i=0; i < set->used; i++) {
1918         struct state *s = set->states[i];
1919         struct state *sc = set->data[i];
1920         for_each_trans(t, s) {
1921             int to = state_set_index(set, t->to);
1922             assert(to >= 0);
1923             struct state *toc = set->data[to];
1924             r = add_new_trans(sc, toc, t->min, t->max);
1925             if (r < 0)
1926                 goto error;
1927         }
1928     }
1929     state_set_free(set);
1930     return result;
1931  error:
1932     state_set_free(set);
1933     fa_free(result);
1934     return NULL;
1935 }
1936
1937 static int case_expand(struct fa *fa);
1938
1939 /* Compute FA1|FA2 and set FA1 to that automaton. FA2 is freed */
1940 ATTRIBUTE_RETURN_CHECK
1941 static int union_in_place(struct fa *fa1, struct fa **fa2) {
1942     struct state *s;
1943     int r;
1944
1945     if (fa1->nocase != (*fa2)->nocase) {
1946         if (case_expand(fa1) < 0)
1947             return -1;
1948         if (case_expand(*fa2) < 0)
1949             return -1;
1950     }
1951
1952     s = add_state(fa1, 0);
1953     if (s == NULL)
1954         return -1;
1955     r = add_epsilon_trans(s, fa1->initial);
1956     if (r < 0)
1957         return -1;
1958     r = add_epsilon_trans(s, (*fa2)->initial);
1959     if (r < 0)
1960         return -1;
1961
1962     fa1->deterministic = 0;
1963     fa1->minimal = 0;
1964     fa_merge(fa1, fa2);
1965
1966     set_initial(fa1, s);
1967
1968     return 0;
1969 }
1970
1971 struct fa *fa_union(struct fa *fa1, struct fa *fa2) {
1972     fa1 = fa_clone(fa1);
1973     fa2 = fa_clone(fa2);
1974     if (fa1 == NULL || fa2 == NULL)
1975         goto error;
1976
1977     F(union_in_place(fa1, &fa2));
1978
1979     return fa1;
1980  error:
1981     fa_free(fa1);
1982     fa_free(fa2);
1983     return NULL;
1984 }
1985
1986 /* Concat FA2 onto FA1; frees FA2 and changes FA1 to FA1.FA2 */
1987 ATTRIBUTE_RETURN_CHECK
1988 static int concat_in_place(struct fa *fa1, struct fa **fa2) {
1989     int r;
1990
1991     if (fa1->nocase != (*fa2)->nocase) {
1992         if (case_expand(fa1) < 0)
1993             return -1;
1994         if (case_expand(*fa2) < 0)
1995             return -1;
1996     }
1997
1998     list_for_each(s, fa1->initial) {
1999         if (s->accept) {
2000             s->accept = 0;
2001             r = add_epsilon_trans(s, (*fa2)->initial);
2002             if (r < 0)
2003                 return -1;
2004         }
2005     }
2006
2007     fa1->deterministic = 0;
2008     fa1->minimal = 0;
2009     fa_merge(fa1, fa2);
2010
2011     return 0;
2012 }
2013
2014 struct fa *fa_concat(struct fa *fa1, struct fa *fa2) {
2015     fa1 = fa_clone(fa1);
2016     fa2 = fa_clone(fa2);
2017
2018     if (fa1 == NULL || fa2 == NULL)
2019         goto error;
2020
2021     F(concat_in_place(fa1, &fa2));
2022
2023     F(collect(fa1));
2024
2025     return fa1;
2026
2027  error:
2028     fa_free(fa1);
2029     fa_free(fa2);
2030     return NULL;
2031 }
2032
2033 static struct fa *fa_make_char_set(bitset *cset, int negate) {
2034     struct fa *fa = fa_make_empty();
2035     if (!fa)
2036         return NULL;
2037
2038     struct state *s = fa->initial;
2039     struct state *t = add_state(fa, 1);
2040     int from = 0;
2041     int r;
2042
2043     if (t == NULL)
2044         goto error;
2045
2046     while (from <= UCHAR_MAX) {
2047         while (from <= UCHAR_MAX && bitset_get(cset, from) == negate)
2048             from += 1;
2049         if (from > UCHAR_MAX)
2050             break;
2051         int to = from;
2052         while (to < UCHAR_MAX && (bitset_get(cset, to + 1) == !negate))
2053             to += 1;
2054         r = add_new_trans(s, t, from, to);
2055         if (r < 0)
2056             goto error;
2057         from = to + 1;
2058     }
2059
2060     fa->deterministic = 1;
2061     fa->minimal = 1;
2062     return fa;
2063
2064  error:
2065     fa_free(fa);
2066     return NULL;
2067 }
2068
2069 static struct fa *fa_star(struct fa *fa) {
2070     struct state *s;
2071     int r;
2072
2073     fa = fa_clone(fa);
2074     if (fa == NULL)
2075         return NULL;
2076
2077     s = add_state(fa, 1);
2078     if (s == NULL)
2079         goto error;
2080
2081     r = add_epsilon_trans(s, fa->initial);
2082     if (r < 0)
2083         goto error;
2084
2085     set_initial(fa, s);
2086     list_for_each(p, fa->initial->next) {
2087         if (p->accept) {
2088             r = add_epsilon_trans(p, s);
2089             if (r < 0)
2090                 goto error;
2091         }
2092     }
2093     fa->deterministic = 0;
2094     fa->minimal = 0;
2095
2096     return fa;
2097
2098  error:
2099     fa_free(fa);
2100     return NULL;
2101 }
2102
2103 /* Form the automaton (FA){N}; FA is not modified */
2104 static struct fa *repeat(struct fa *fa, int n) {
2105     if (n == 0) {
2106         return fa_make_epsilon();
2107     } else if (n == 1) {
2108         return fa_clone(fa);
2109     } else {
2110         struct fa *cfa = fa_clone(fa);
2111         if (cfa == NULL)
2112             return NULL;
2113         while (n > 1) {
2114             struct fa *tfa = fa_clone(fa);
2115             if (tfa == NULL) {
2116                 fa_free(cfa);
2117                 return NULL;
2118             }
2119             if (concat_in_place(cfa, &tfa) < 0) {
2120                 fa_free(cfa);
2121                 fa_free(tfa);
2122                 return NULL;
2123             }
2124             n -= 1;
2125         }
2126         return cfa;
2127     }
2128 }
2129
2130 struct fa *fa_iter(struct fa *fa, int min, int max) {
2131     int r;
2132
2133     if (min < 0)
2134         min = 0;
2135
2136     if (min > max && max != -1) {
2137         return fa_make_empty();
2138     }
2139     if (max == -1) {
2140         struct fa *sfa = fa_star(fa);
2141         if (min == 0)
2142             return sfa;
2143         if (! sfa)
2144             return NULL;
2145         struct fa *cfa = repeat(fa, min);
2146         if (! cfa) {
2147             fa_free(sfa);
2148             return NULL;
2149         }
2150         if (concat_in_place(cfa, &sfa) < 0) {
2151             fa_free(sfa);
2152             fa_free(cfa);
2153             return NULL;
2154         }
2155         return cfa;
2156     } else {
2157         struct fa *cfa = NULL;
2158
2159         max -= min;
2160         cfa = repeat(fa, min);
2161         if (cfa == NULL)
2162             return NULL;
2163         if (max > 0) {
2164             struct fa *cfa2 = fa_clone(fa);
2165             if (cfa2 == NULL) {
2166                 fa_free(cfa);
2167                 return NULL;
2168             }
2169             while (max > 1) {
2170                 struct fa *cfa3 = fa_clone(fa);
2171                 if (cfa3 == NULL) {
2172                     fa_free(cfa);
2173                     fa_free(cfa2);
2174                     return NULL;
2175                 }
2176                 list_for_each(s, cfa3->initial) {
2177                     if (s->accept) {
2178                         r = add_epsilon_trans(s, cfa2->initial);
2179                         if (r < 0) {
2180                             fa_free(cfa);
2181                             fa_free(cfa2);
2182                             fa_free(cfa3);
2183                             return NULL;
2184                         }
2185                     }
2186                 }
2187                 fa_merge(cfa3, &cfa2);
2188                 cfa2 = cfa3;
2189                 max -= 1;
2190             }
2191             list_for_each(s, cfa->initial) {
2192                 if (s->accept) {
2193                     r = add_epsilon_trans(s, cfa2->initial);
2194                     if (r < 0) {
2195                         fa_free(cfa);
2196                         fa_free(cfa2);
2197                         return NULL;
2198                     }
2199                 }
2200             }
2201             fa_merge(cfa, &cfa2);
2202             cfa->deterministic = 0;
2203             cfa->minimal = 0;
2204         }
2205         if (collect(cfa) < 0) {
2206             fa_free(cfa);
2207             cfa = NULL;
2208         }
2209         return cfa;
2210     }
2211 }
2212
2213 static void sort_transition_intervals(struct fa *fa) {
2214     list_for_each(s, fa->initial) {
2215         qsort(s->trans, s->tused, sizeof(*s->trans), trans_intv_cmp);
2216     }
2217 }
2218
2219 struct fa *fa_intersect(struct fa *fa1, struct fa *fa2) {
2220     int ret;
2221     struct fa *fa = NULL;
2222     struct state_set *worklist = NULL;
2223     state_triple_hash *newstates = NULL;
2224
2225     if (fa1 == fa2)
2226         return fa_clone(fa1);
2227
2228     if (fa_is_basic(fa1, FA_EMPTY) || fa_is_basic(fa2, FA_EMPTY))
2229         return fa_make_empty();
2230
2231     if (fa1->nocase != fa2->nocase) {
2232         F(case_expand(fa1));
2233         F(case_expand(fa2));
2234     }
2235
2236     fa = fa_make_empty();
2237     worklist = state_set_init(-1, S_NONE);
2238     newstates = state_triple_init();
2239     if (fa == NULL || worklist == NULL || newstates == NULL)
2240         goto error;
2241
2242     sort_transition_intervals(fa1);
2243     sort_transition_intervals(fa2);
2244
2245     F(state_set_push(worklist, fa1->initial));
2246     F(state_set_push(worklist, fa2->initial));
2247     F(state_set_push(worklist, fa->initial));
2248     F(state_triple_push(newstates,
2249                          fa1->initial, fa2->initial, fa->initial));
2250     while (worklist->used) {
2251         struct state *s  = state_set_pop(worklist);
2252         struct state *p2 = state_set_pop(worklist);
2253         struct state *p1 = state_set_pop(worklist);
2254         s->accept = p1->accept && p2->accept;
2255
2256         struct trans *t1 = p1->trans;
2257         struct trans *t2 = p2->trans;
2258         for (int n1 = 0, b2 = 0; n1 < p1->tused; n1++) {
2259             while (b2 < p2->tused && t2[b2].max < t1[n1].min)
2260                 b2++;
2261             for (int n2 = b2;
2262                  n2 < p2->tused && t1[n1].max >= t2[n2].min;
2263                  n2++) {
2264                 if (t2[n2].max >= t1[n1].min) {
2265                     struct state *r = state_triple_thd(newstates,
2266                                                        t1[n1].to, t2[n2].to);
2267                     if (r == NULL) {
2268                         r = add_state(fa, 0);
2269                         E(r == NULL);
2270                         F(state_set_push(worklist, t1[n1].to));
2271                         F(state_set_push(worklist, t2[n2].to));
2272                         F(state_set_push(worklist, r));
2273                         F(state_triple_push(newstates,
2274                                              t1[n1].to, t2[n2].to, r));
2275                     }
2276                     char min = t1[n1].min > t2[n2].min
2277                         ? t1[n1].min : t2[n2].min;
2278                     char max = t1[n1].max < t2[n2].max
2279                         ? t1[n1].max : t2[n2].max;
2280                     ret = add_new_trans(s, r, min, max);
2281                     if (ret < 0)
2282                         goto error;
2283                 }
2284             }
2285         }
2286     }
2287     fa->deterministic = fa1->deterministic && fa2->deterministic;
2288     fa->nocase = fa1->nocase && fa2->nocase;
2289  done:
2290     state_set_free(worklist);
2291     state_triple_free(newstates);
2292     if (fa != NULL) {
2293         if (collect(fa) < 0) {
2294             fa_free(fa);
2295             fa = NULL;
2296         }
2297     }
2298
2299     return fa;
2300  error:
2301     fa_free(fa);
2302     fa = NULL;
2303     goto done;
2304 }
2305
2306 int fa_contains(struct fa *fa1, struct fa *fa2) {
2307     int result = 0;
2308     struct state_set *worklist = NULL;  /* List of pairs of states */
2309     struct state_set *visited = NULL;   /* List of pairs of states */
2310
2311     if (fa1 == NULL || fa2 == NULL)
2312         return -1;
2313
2314     if (fa1 == fa2)
2315         return 1;
2316
2317     F(determinize(fa2, NULL));
2318     sort_transition_intervals(fa1);
2319     sort_transition_intervals(fa2);
2320
2321     F(state_pair_push(&worklist, fa1->initial, fa2->initial));
2322     F(state_pair_push(&visited, fa1->initial, fa2->initial));
2323     while (worklist->used) {
2324         struct state *p1, *p2;
2325         void *v2;
2326         p1 = state_set_pop_data(worklist, &v2);
2327         p2 = v2;
2328
2329         if (p1->accept && !p2->accept)
2330             goto done;
2331
2332         struct trans *t1 = p1->trans;
2333         struct trans *t2 = p2->trans;
2334         for(int n1 = 0, b2 = 0; n1 < p1->tused; n1++) {
2335             while (b2 < p2->tused && t2[b2].max < t1[n1].min)
2336                 b2++;
2337             int min1 = t1[n1].min, max1 = t1[n1].max;
2338             for (int n2 = b2;
2339                  n2 < p2->tused && t1[n1].max >= t2[n2].min;
2340                  n2++) {
2341                 if (t2[n2].min > min1)
2342                     goto done;
2343                 if (t2[n2].max < CHAR_MAX)
2344                     min1 = t2[n2].max + 1;
2345                 else {
2346                     min1 = UCHAR_MAX;
2347                     max1 = UCHAR_MIN;
2348                 }
2349                 if (state_pair_find(visited, t1[n1].to, t2[n2].to) == -1) {
2350                     F(state_pair_push(&worklist, t1[n1].to, t2[n2].to));
2351                     F(state_pair_push(&visited, t1[n1].to, t2[n2].to));
2352                 }
2353             }
2354             if (min1 <= max1)
2355                 goto done;
2356         }
2357     }
2358
2359     result = 1;
2360  done:
2361     state_set_free(worklist);
2362     state_set_free(visited);
2363     return result;
2364  error:
2365     result = -1;
2366     goto done;
2367 }
2368
2369 static int add_crash_trans(struct fa *fa, struct state *s, struct state *crash,
2370                            int min, int max) {
2371     int result;
2372
2373     if (fa->nocase) {
2374         /* Never transition on anything in [A-Z] */
2375         if (min > 'Z' || max < 'A') {
2376             result = add_new_trans(s, crash, min, max);
2377         } else if (min >= 'A' && max <= 'Z') {
2378             result = 0;
2379         } else if (max <= 'Z') {
2380             /* min < 'A' */
2381             result = add_new_trans(s, crash, min, 'A' - 1);
2382         } else if (min >= 'A') {
2383             /* max > 'Z' */
2384             result = add_new_trans(s, crash, 'Z' + 1, max);
2385         } else {
2386             /* min < 'A' && max > 'Z' */
2387             result = add_new_trans(s, crash, min, 'A' - 1);
2388             if (result == 0)
2389                 result = add_new_trans(s, crash, 'Z' + 1, max);
2390         }
2391     } else {
2392         result = add_new_trans(s, crash, min, max);
2393     }
2394     return result;
2395 }
2396
2397 static int totalize(struct fa *fa) {
2398     int r;
2399     struct state *crash = add_state(fa, 0);
2400
2401     E(crash == NULL);
2402     F(mark_reachable(fa));
2403     sort_transition_intervals(fa);
2404
2405     r = add_crash_trans(fa, crash, crash, UCHAR_MIN, UCHAR_MAX);
2406     if (r < 0)
2407         return -1;
2408
2409     list_for_each(s, fa->initial) {
2410         int next = UCHAR_MIN;
2411         int tused = s->tused;
2412         for (int i=0; i < tused; i++) {
2413             uchar min = s->trans[i].min, max = s->trans[i].max;
2414             if (min > next) {
2415                 r = add_crash_trans(fa, s, crash, next, min - 1);
2416                 if (r < 0)
2417                     return -1;
2418             }
2419             if (max + 1 > next)
2420                 next = max + 1;
2421         }
2422         if (next <= UCHAR_MAX) {
2423             r = add_crash_trans(fa, s, crash, next, UCHAR_MAX);
2424             if (r < 0)
2425                 return -1;
2426         }
2427     }
2428     return 0;
2429  error:
2430     return -1;
2431 }
2432
2433 struct fa *fa_complement(struct fa *fa) {
2434     fa = fa_clone(fa);
2435     E(fa == NULL);
2436     F(determinize(fa, NULL));
2437     F(totalize(fa));
2438     list_for_each(s, fa->initial)
2439         s->accept = ! s->accept;
2440
2441     F(collect(fa));
2442     return fa;
2443  error:
2444     fa_free(fa);
2445     return NULL;
2446 }
2447
2448 struct fa *fa_minus(struct fa *fa1, struct fa *fa2) {
2449     if (fa1 == NULL || fa2 == NULL)
2450         return NULL;
2451
2452     if (fa_is_basic(fa1, FA_EMPTY) || fa1 == fa2)
2453         return fa_make_empty();
2454     if (fa_is_basic(fa2, FA_EMPTY))
2455         return fa_clone(fa1);
2456
2457     struct fa *cfa2 = fa_complement(fa2);
2458     if (cfa2 == NULL)
2459         return NULL;
2460
2461     struct fa *result = fa_intersect(fa1, cfa2);
2462     fa_free(cfa2);
2463     return result;
2464 }
2465
2466 static int accept_to_accept(struct fa *fa) {
2467     int r;
2468     struct state *s = add_state(fa, 0);
2469     if (s == NULL)
2470         return -1;
2471
2472     F(mark_reachable(fa));
2473     list_for_each(a, fa->initial) {
2474         if (a->accept && a->reachable) {
2475             r = add_epsilon_trans(s, a);
2476             if (r < 0)
2477                 return -1;
2478         }
2479     }
2480
2481     set_initial(fa, s);
2482     fa->deterministic = fa->minimal = 0;
2483     return 0;
2484  error:
2485     return -1;
2486 }
2487
2488 struct fa *fa_overlap(struct fa *fa1, struct fa *fa2) {
2489     struct fa *fa = NULL, *eps = NULL, *result = NULL;
2490     struct state_set *map = NULL;
2491
2492     if (fa1 == NULL || fa2 == NULL)
2493         return NULL;
2494
2495     fa1 = fa_clone(fa1);
2496     fa2 = fa_clone(fa2);
2497     if (fa1 == NULL || fa2 == NULL)
2498         goto error;
2499
2500     if (determinize(fa1, NULL) < 0)
2501         goto error;
2502     if (accept_to_accept(fa1) < 0)
2503         goto error;
2504
2505     map = fa_reverse(fa2);
2506     state_set_free(map);
2507     if (determinize(fa2, NULL) < 0)
2508         goto error;
2509     if (accept_to_accept(fa2) < 0)
2510         goto error;
2511     map = fa_reverse(fa2);
2512     state_set_free(map);
2513     if (determinize(fa2, NULL) < 0)
2514         goto error;
2515
2516     fa = fa_intersect(fa1, fa2);
2517     if (fa == NULL)
2518         goto error;
2519
2520     eps = fa_make_epsilon();
2521     if (eps == NULL)
2522         goto error;
2523
2524     result = fa_minus(fa, eps);
2525     if (result == NULL)
2526         goto error;
2527
2528  error:
2529     fa_free(fa1);
2530     fa_free(fa2);
2531     fa_free(fa);
2532     fa_free(eps);
2533     return result;
2534 }
2535
2536 int fa_equals(struct fa *fa1, struct fa *fa2) {
2537     if (fa1 == NULL || fa2 == NULL)
2538         return -1;
2539
2540     /* fa_contains(fa1, fa2) && fa_contains(fa2, fa1) with error checking */
2541     int c1 = fa_contains(fa1, fa2);
2542     if (c1 < 0)
2543         return -1;
2544     if (c1 == 0)
2545         return 0;
2546     return fa_contains(fa2, fa1);
2547 }
2548
2549 static unsigned int chr_score(char c) {
2550     if (isalpha(c)) {
2551         return 2;
2552     } else if (isalnum(c)) {
2553         return 3;
2554     } else if (isprint(c)) {
2555         return 7;
2556     } else if (c == '\0') {
2557         return 10000;
2558     } else {
2559         return 100;
2560     }
2561 }
2562
2563 static unsigned int str_score(const struct re_str *str) {
2564     unsigned int score = 0;
2565     for (int i=0; i < str->len; i++) {
2566         score += chr_score(str->rx[i]);
2567     }
2568     return score;
2569 }
2570
2571 /* See if we get a better string for DST by appending C to SRC. If DST is
2572  * NULL or empty, always use SRC + C
2573  */
2574 static struct re_str *string_extend(struct re_str *dst,
2575                                     const struct re_str *src,
2576                                     char c) {
2577     if (dst == NULL
2578         || dst->len == 0
2579         || str_score(src) + chr_score(c) < str_score(dst)) {
2580         int slen = src->len;
2581         if (dst == NULL)
2582             dst = make_re_str(NULL);
2583         if (dst == NULL)
2584             return NULL;
2585         if (REALLOC_N(dst->rx, slen+2) < 0) {
2586             free(dst);
2587             return NULL;
2588         }
2589         memcpy(dst->rx, src->rx, slen);
2590         dst->rx[slen] = c;
2591         dst->rx[slen + 1] = '\0';
2592         dst->len = slen + 1;
2593     }
2594     return dst;
2595 }
2596
2597 static char pick_char(struct trans *t) {
2598     for (int c = t->min; c <= t->max; c++)
2599         if (isalpha(c)) return c;
2600     for (int c = t->min; c <= t->max; c++)
2601         if (isalnum(c)) return c;
2602     for (int c = t->min; c <= t->max; c++)
2603         if (isprint(c)) return c;
2604     return t->max;
2605 }
2606
2607 /* Generate an example string for FA. Traverse all transitions and record
2608  * at each turn the "best" word found for that state.
2609  */
2610 int fa_example(struct fa *fa, char **example, size_t *example_len) {
2611     struct re_str *word = NULL;
2612     struct state_set *path = NULL, *worklist = NULL;
2613     struct re_str *str = NULL;
2614
2615     *example = NULL;
2616     *example_len = 0;
2617
2618     /* Sort to avoid any ambiguity because of reordering of transitions */
2619     sort_transition_intervals(fa);
2620
2621     /* Map from state to string */
2622     path = state_set_init(-1, S_DATA|S_SORTED);
2623     str = make_re_str("");
2624     if (path == NULL || str == NULL)
2625         goto error;
2626     F(state_set_push_data(path, fa->initial, str));
2627     str = NULL;
2628
2629     /* List of states still to visit */
2630     worklist = state_set_init(-1, S_NONE);
2631     if (worklist == NULL)
2632         goto error;
2633     F(state_set_push(worklist, fa->initial));
2634
2635     while (worklist->used) {
2636         struct state *s = state_set_pop(worklist);
2637         struct re_str *ps = state_set_find_data(path, s);
2638         for_each_trans(t, s) {
2639             char c = pick_char(t);
2640             int toind = state_set_index(path, t->to);
2641             if (toind == -1) {
2642                 struct re_str *w = string_extend(NULL, ps, c);
2643                 E(w == NULL);
2644                 F(state_set_push(worklist, t->to));
2645                 F(state_set_push_data(path, t->to, w));
2646             } else {
2647                 path->data[toind] = string_extend(path->data[toind], ps, c);
2648             }
2649         }
2650     }
2651
2652     for (int i=0; i < path->used; i++) {
2653         struct state *p = path->states[i];
2654         struct re_str *ps = path->data[i];
2655         if (p->accept &&
2656             (word == NULL || word->len == 0
2657              || (ps->len > 0 && str_score(word) > str_score(ps)))) {
2658             free_re_str(word);
2659             word = ps;
2660         } else {
2661             free_re_str(ps);
2662         }
2663     }
2664     state_set_free(path);
2665     state_set_free(worklist);
2666     if (word != NULL) {
2667         *example_len = word->len;
2668         *example = word->rx;
2669         free(word);
2670     }
2671     return 0;
2672  error:
2673     state_set_free(path);
2674     state_set_free(worklist);
2675     free_re_str(word);
2676     free_re_str(str);
2677     return -1;
2678 }
2679
2680 struct enum_intl {
2681     int       limit;
2682     int       nwords;
2683     char    **words;
2684     char     *buf;
2685     size_t    bsize;
2686 };
2687
2688 static int fa_enumerate_intl(struct state *s, struct enum_intl *ei, int pos) {
2689     int result = -1;
2690
2691     if (ei->bsize <= pos + 1) {
2692         ei->bsize *= 2;
2693         F(REALLOC_N(ei->buf, ei->bsize));
2694     }
2695
2696     ei->buf[pos] = '\0';
2697     for_each_trans(t, s) {
2698         if (t->to->visited)
2699             return -2;
2700         t->to->visited = 1;
2701         for (int i=t->min; i <= t->max; i++) {
2702             ei->buf[pos] = i;
2703             if (t->to->accept) {
2704                 if (ei->nwords >= ei->limit)
2705                     return -2;
2706                 ei->words[ei->nwords] = strdup(ei->buf);
2707                 E(ei->words[ei->nwords] == NULL);
2708                 ei->nwords += 1;
2709             }
2710             result = fa_enumerate_intl(t->to, ei, pos+1);
2711             E(result < 0);
2712         }
2713         t->to->visited = 0;
2714     }
2715     ei->buf[pos] = '\0';
2716     result = 0;
2717  error:
2718     return result;
2719 }
2720
2721 int fa_enumerate(struct fa *fa, int limit, char ***words) {
2722     struct enum_intl ei;
2723     int result = -1;
2724
2725     *words = NULL;
2726     MEMZERO(&ei, 1);
2727     ei.bsize = 8;                    /* Arbitrary initial size */
2728     ei.limit = limit;
2729     F(ALLOC_N(ei.words, limit));
2730     F(ALLOC_N(ei.buf, ei.bsize));
2731
2732     /* We use the visited bit to track which states we already visited
2733      * during the construction of a word to detect loops */
2734     list_for_each(s, fa->initial)
2735         s->visited = 0;
2736     fa->initial->visited = 1;
2737     if (fa->initial->accept) {
2738         if (ei.nwords >= limit)
2739             return -2;
2740         ei.words[0] = strdup("");
2741         E(ei.words[0] == NULL);
2742         ei.nwords = 1;
2743     }
2744     result = fa_enumerate_intl(fa->initial, &ei, 0);
2745     E(result < 0);
2746
2747     result = ei.nwords;
2748     *words = ei.words;
2749     ei.words = NULL;
2750  done:
2751     free(ei.buf);
2752     return result;
2753
2754  error:
2755     for (int i=0; i < ei.nwords; i++)
2756         free(ei.words[i]);
2757     free(ei.words);
2758     goto done;
2759 }
2760
2761 /* Expand the automaton FA by replacing every transition s(c) -> p from
2762  * state s to p on character c by two transitions s(X) -> r, r(c) -> p via
2763  * a new state r.
2764  * If ADD_MARKER is true, also add for each original state s a new a loop
2765  * s(Y) -> q and q(X) -> s through a new state q.
2766  *
2767  * The end result is that an automaton accepting "a|ab" is turned into one
2768  * accepting "Xa|XaXb" if add_marker is false and "(YX)*Xa|(YX)*Xa(YX)*Xb"
2769  * when add_marker is true.
2770  *
2771  * The returned automaton is a copy of FA, FA is not modified.
2772  */
2773 static struct fa *expand_alphabet(struct fa *fa, int add_marker,
2774                                   char X, char Y) {
2775     int ret;
2776
2777     fa = fa_clone(fa);
2778     if (fa == NULL)
2779         return NULL;
2780
2781     F(mark_reachable(fa));
2782     list_for_each(p, fa->initial) {
2783         if (! p->reachable)
2784             continue;
2785
2786         struct state *r = add_state(fa, 0);
2787         if (r == NULL)
2788             goto error;
2789         r->trans = p->trans;
2790         r->tused = p->tused;
2791         r->tsize = p->tsize;
2792         p->trans = NULL;
2793         p->tused = p->tsize = 0;
2794         ret = add_new_trans(p, r, X, X);
2795         if (ret < 0)
2796             goto error;
2797         if (add_marker) {
2798             struct state *q = add_state(fa, 0);
2799             ret = add_new_trans(p, q, Y, Y);
2800             if (ret < 0)
2801                 goto error;
2802             ret = add_new_trans(q, p, X, X);
2803             if (ret < 0)
2804                 goto error;
2805         }
2806     }
2807     return fa;
2808  error:
2809     fa_free(fa);
2810     return NULL;
2811 }
2812
2813 static bitset *alphabet(struct fa *fa) {
2814     bitset *bs = bitset_init(UCHAR_NUM);
2815
2816     if (bs == NULL)
2817         return NULL;
2818
2819     list_for_each(s, fa->initial) {
2820         for (int i=0; i < s->tused; i++) {
2821             for (uint c = s->trans[i].min; c <= s->trans[i].max; c++)
2822                 bitset_set(bs, c);
2823         }
2824     }
2825     return bs;
2826 }
2827
2828 static bitset *last_chars(struct fa *fa) {
2829     bitset *bs = bitset_init(UCHAR_NUM);
2830
2831     if (bs == NULL)
2832         return NULL;
2833
2834     list_for_each(s, fa->initial) {
2835         for (int i=0; i < s->tused; i++) {
2836             if (s->trans[i].to->accept) {
2837                 for (uint c = s->trans[i].min; c <= s->trans[i].max; c++)
2838                     bitset_set(bs, c);
2839             }
2840         }
2841     }
2842     return bs;
2843 }
2844
2845 static bitset *first_chars(struct fa *fa) {
2846     bitset *bs = bitset_init(UCHAR_NUM);
2847     struct state *s = fa->initial;
2848
2849     if (bs == NULL)
2850         return NULL;
2851
2852     for (int i=0; i < s->tused; i++) {
2853         for (uint c = s->trans[i].min; c <= s->trans[i].max; c++)
2854             bitset_set(bs, c);
2855     }
2856     return bs;
2857 }
2858
2859 /* Return 1 if F1 and F2 are known to be unambiguously concatenable
2860  * according to simple heuristics. Return 0 if they need to be checked
2861  * further to decide ambiguity
2862  * Return -1 if an allocation fails
2863  */
2864 static int is_splittable(struct fa *fa1, struct fa *fa2) {
2865     bitset *alpha1 = NULL;
2866     bitset *alpha2 = NULL;
2867     bitset *last1 = NULL;
2868     bitset *first2 = NULL;
2869     bool result = -1;
2870
2871     alpha2 = alphabet(fa2);
2872     last1 = last_chars(fa1);
2873     if (alpha2 == NULL || last1 == NULL)
2874         goto done;
2875     if (bitset_disjoint(last1, alpha2, UCHAR_NUM)) {
2876         result = 1;
2877         goto done;
2878     }
2879
2880     alpha1 = alphabet(fa1);
2881     first2 = first_chars(fa2);
2882     if (alpha1 == NULL || first2 == NULL)
2883         goto done;
2884     if (bitset_disjoint(first2, alpha1, UCHAR_NUM)) {
2885         result = 1;
2886         goto done;
2887     }
2888     result = 0;
2889  done:
2890     bitset_free(alpha1);
2891     bitset_free(alpha2);
2892     bitset_free(last1);
2893     bitset_free(first2);
2894     return result;
2895 }
2896
2897 /* This algorithm is due to Anders Moeller, and can be found in class
2898  * AutomatonOperations in dk.brics.grammar
2899  */
2900 int fa_ambig_example(struct fa *fa1, struct fa *fa2,
2901                      char **upv, size_t *upv_len,
2902                      char **pv, char **v) {
2903     static const char X = '\001';
2904     static const char Y = '\002';
2905     char *result = NULL, *s = NULL;
2906     size_t result_len = 0;
2907     int ret = -1, r;
2908     struct fa *mp = NULL, *ms = NULL, *sp = NULL, *ss = NULL, *amb = NULL;
2909     struct fa *a1f = NULL, *a1t = NULL, *a2f = NULL, *a2t = NULL;
2910     struct fa *b1 = NULL, *b2 = NULL;
2911
2912     *upv = NULL;
2913     *upv_len = 0;
2914     if (pv != NULL)
2915         *pv = NULL;
2916     if (v != NULL)
2917         *v = NULL;
2918
2919     r = is_splittable(fa1, fa2);
2920     if (r < 0)
2921         goto error;
2922     if (r == 1)
2923         return 0;
2924
2925 #define Xs "\001"
2926 #define Ys "\002"
2927 #define MPs Ys Xs "(" Xs "(.|\n))+"
2928 #define MSs Ys Xs "(" Xs "(.|\n))*"
2929 #define SPs "(" Xs "(.|\n))+" Ys Xs
2930 #define SSs "(" Xs "(.|\n))*" Ys Xs
2931     /* These could become static constants */
2932     r = fa_compile( MPs, strlen(MPs), &mp);
2933     if (r != REG_NOERROR)
2934         goto error;
2935     r = fa_compile( MSs, strlen(MSs), &ms);
2936     if (r != REG_NOERROR)
2937         goto error;
2938     r = fa_compile( SPs, strlen(SPs), &sp);
2939     if (r != REG_NOERROR)
2940         goto error;
2941     r = fa_compile( SSs, strlen(SSs), &ss);
2942     if (r != REG_NOERROR)
2943         goto error;
2944 #undef SSs
2945 #undef SPs
2946 #undef MSs
2947 #undef MPs
2948 #undef Xs
2949 #undef Ys
2950
2951     a1f = expand_alphabet(fa1, 0, X, Y);
2952     a1t = expand_alphabet(fa1, 1, X, Y);
2953     a2f = expand_alphabet(fa2, 0, X, Y);
2954     a2t = expand_alphabet(fa2, 1, X, Y);
2955     if (a1f == NULL || a1t == NULL || a2f == NULL || a2t == NULL)
2956         goto error;
2957
2958     /* Compute b1 = ((a1f . mp) & a1t) . ms */
2959     if (concat_in_place(a1f, &mp) < 0)
2960         goto error;
2961     b1 = fa_intersect(a1f, a1t);
2962     if (b1 == NULL)
2963         goto error;
2964     if (concat_in_place(b1, &ms) < 0)
2965         goto error;
2966     if (fa_is_basic(b1, FA_EMPTY)) {
2967         /* We are done - amb which we take an example from below
2968          * will be empty, and there can therefore not be an ambiguity */
2969         ret = 0;
2970         goto done;
2971     }
2972
2973     /* Compute b2 = ss . ((sp . a2f) & a2t) */
2974     if (concat_in_place(sp, &a2f) < 0)
2975         goto error;
2976     b2 = fa_intersect(sp, a2t);
2977     if (b2 == NULL)
2978         goto error;
2979     if (concat_in_place(ss, &b2) < 0)
2980         goto error;
2981     b2 = ss;
2982     ss = NULL;
2983
2984     /* The automaton we are really interested in */
2985     amb = fa_intersect(b1, b2);
2986     if (amb == NULL)
2987         goto error;
2988
2989     size_t s_len = 0;
2990     r = fa_example(amb, &s, &s_len);
2991     if (r < 0)
2992         goto error;
2993
2994     if (s != NULL) {
2995         char *t;
2996         result_len = (s_len-1)/2 - 1;
2997         F(ALLOC_N(result, result_len + 1));
2998         t = result;
2999         int i = 0;
3000         for (i=0; s[2*i] == X; i++) {
3001             assert((t - result) < result_len);
3002             *t++ = s[2*i + 1];
3003         }
3004         if (pv != NULL)
3005             *pv = t;
3006         i += 1;
3007
3008         for ( ;s[2*i] == X; i++) {
3009             assert((t - result) < result_len);
3010             *t++ = s[2*i + 1];
3011         }
3012         if (v != NULL)
3013             *v = t;
3014         i += 1;
3015
3016         for (; 2*i+1 < s_len; i++) {
3017             assert((t - result) < result_len);
3018             *t++ = s[2*i + 1];
3019         }
3020     }
3021     ret = 0;
3022
3023  done:
3024     /* Clean up intermediate automata */
3025     fa_free(mp);
3026     fa_free(ms);
3027     fa_free(ss);
3028     fa_free(sp);
3029     fa_free(a1f);
3030     fa_free(a1t);
3031     fa_free(a2f);
3032     fa_free(a2t);
3033     fa_free(b1);
3034     fa_free(b2);
3035     fa_free(amb);
3036
3037     FREE(s);
3038     *upv = result;
3039     if (result != NULL)
3040         *upv_len = result_len;
3041     return ret;
3042  error:
3043     FREE(result);
3044     ret = -1;
3045     goto done;
3046 }
3047
3048 /*
3049  * Construct an fa from a regular expression
3050  */
3051 static struct fa *fa_from_re(struct re *re) {
3052     struct fa *result = NULL;
3053
3054     switch(re->type) {
3055     case UNION:
3056         {
3057             result = fa_from_re(re->exp1);
3058             if (result == NULL)
3059                 goto error;
3060             struct fa *fa2 = fa_from_re(re->exp2);
3061             if (fa2 == NULL)
3062                 goto error;
3063             if (union_in_place(result, &fa2) < 0)
3064                 goto error;
3065         }
3066         break;
3067     case CONCAT:
3068         {
3069             result = fa_from_re(re->exp1);
3070             if (result == NULL)
3071                 goto error;
3072             struct fa *fa2 = fa_from_re(re->exp2);
3073             if (fa2 == NULL)
3074                 goto error;
3075             if (concat_in_place(result, &fa2) < 0)
3076                 goto error;
3077         }
3078         break;
3079     case CSET:
3080         result = fa_make_char_set(re->cset, re->negate);
3081         break;
3082     case ITER:
3083         {
3084             struct fa *fa = fa_from_re(re->exp);
3085             if (fa == NULL)
3086                 goto error;
3087             result = fa_iter(fa, re->min, re->max);
3088             fa_free(fa);
3089         }
3090         break;
3091     case EPSILON:
3092         result = fa_make_epsilon();
3093         break;
3094     case CHAR:
3095         result = fa_make_char(re->c);
3096         break;
3097     default:
3098         assert(0);
3099         break;
3100     }
3101     return result;
3102  error:
3103     fa_free(result);
3104     return NULL;
3105 }
3106
3107 static void free_re(struct re *re) {
3108     if (re == NULL)
3109         return;
3110     assert(re->ref == 0);
3111
3112     if (re->type == UNION || re->type == CONCAT) {
3113         re_unref(re->exp1);
3114         re_unref(re->exp2);
3115     } else if (re->type == ITER) {
3116         re_unref(re->exp);
3117     } else if (re->type == CSET) {
3118         bitset_free(re->cset);
3119     }
3120     free(re);
3121 }
3122
3123 int fa_compile(const char *regexp, size_t size, struct fa **fa) {
3124     struct re *re = NULL;
3125     struct re_parse parse;
3126
3127     *fa = NULL;
3128
3129     parse.rx = regexp;
3130     parse.rend = regexp + size;
3131     parse.error = REG_NOERROR;
3132
3133     re = parse_regexp(&parse);
3134     if (re == NULL)
3135         return parse.error;
3136
3137     *fa = fa_from_re(re);
3138     re_unref(re);
3139
3140     if (*fa == NULL || collect(*fa) < 0)
3141         parse.error = REG_ESPACE;
3142     return parse.error;
3143 }
3144
3145 /* We represent a case-insensitive FA by using only transitions on
3146  * lower-case letters.
3147  */
3148 int fa_nocase(struct fa *fa) {
3149     if (fa == NULL || fa->nocase)
3150         return 0;
3151
3152     fa->nocase = 1;
3153     list_for_each(s, fa->initial) {
3154         int tused = s->tused;
3155         /* For every transition on characters in [A-Z] add a corresponding
3156          * transition on [a-z]; remove any portion covering [A-Z] */
3157         for (int i=0; i < tused; i++) {
3158             struct trans *t = s->trans + i;
3159             int lc_min = t->min < 'A' ? 'a' : tolower(t->min);
3160             int lc_max = t->max > 'Z' ? 'z' : tolower(t->max);
3161
3162             if (t->min > 'Z' || t->max < 'A')
3163                 continue;
3164             if (t->min >= 'A' && t->max <= 'Z') {
3165                 t->min = tolower(t->min);
3166                 t->max = tolower(t->max);
3167             } else if (t->max <= 'Z') {
3168                 /* t->min < 'A' */
3169                 t->max = 'A' - 1;
3170                 F(add_new_trans(s, t->to, lc_min, lc_max));
3171             } else if (t->min >= 'A') {
3172                 /* t->max > 'Z' */
3173                 t->min = 'Z' + 1;
3174                 F(add_new_trans(s, t->to, lc_min, lc_max));
3175             } else {
3176                 /* t->min < 'A' && t->max > 'Z' */
3177                 F(add_new_trans(s, t->to, 'Z' + 1, t->max));
3178                 s->trans[i].max = 'A' - 1;
3179                 F(add_new_trans(s, s->trans[i].to, lc_min, lc_max));
3180             }
3181         }
3182     }
3183     F(collect(fa));
3184     return 0;
3185  error:
3186     return -1;
3187 }
3188
3189 int fa_is_nocase(struct fa *fa) {
3190     return fa->nocase;
3191 }
3192
3193 /* If FA is case-insensitive, turn it into a case-sensitive automaton by
3194  * adding transitions on upper-case letters for each existing transition on
3195  * lower-case letters */
3196 static int case_expand(struct fa *fa) {
3197     if (! fa->nocase)
3198         return 0;
3199
3200     fa->nocase = 0;
3201     list_for_each(s, fa->initial) {
3202         int tused = s->tused;
3203         /* For every transition on characters in [a-z] add a corresponding
3204          * transition on [A-Z] */
3205         for (int i=0; i < tused; i++) {
3206             struct trans *t = s->trans + i;
3207             int lc_min = t->min < 'a' ? 'A' : toupper(t->min);
3208             int lc_max = t->max > 'z' ? 'Z' : toupper(t->max);
3209
3210             if (t->min > 'z' || t->max < 'a')
3211                 continue;
3212             F(add_new_trans(s, t->to, lc_min, lc_max));
3213         }
3214     }
3215     F(collect(fa));
3216     return 0;
3217  error:
3218     return -1;
3219 }
3220
3221 /*
3222  * Regular expression parser
3223  */
3224
3225 static struct re *make_re(enum re_type type) {
3226     struct re *re;
3227     if (make_ref(re) == 0)
3228         re->type = type;
3229     return re;
3230 }
3231
3232 static struct re *make_re_rep(struct re *exp, int min, int max) {
3233     struct re *re = make_re(ITER);
3234     if (re) {
3235         re->exp = exp;
3236         re->min = min;
3237         re->max = max;
3238     } else {
3239         re_unref(exp);
3240     }
3241     return re;
3242 }
3243
3244 static struct re *make_re_binop(enum re_type type, struct re *exp1,
3245                                 struct re *exp2) {
3246     struct re *re = make_re(type);
3247     if (re) {
3248         re->exp1 = exp1;
3249         re->exp2 = exp2;
3250     } else {
3251         re_unref(exp1);
3252         re_unref(exp2);
3253     }
3254     return re;
3255 }
3256
3257 static struct re *make_re_char(uchar c) {
3258     struct re *re = make_re(CHAR);
3259     if (re)
3260         re->c = c;
3261     return re;
3262 }
3263
3264 static struct re *make_re_char_set(bool negate, bool no_ranges) {
3265     struct re *re = make_re(CSET);
3266     if (re) {
3267         re->negate = negate;
3268         re->no_ranges = no_ranges;
3269         re->cset = bitset_init(UCHAR_NUM);
3270         if (re->cset == NULL)
3271             re_unref(re);
3272     }
3273     return re;
3274 }
3275
3276 static bool more(struct re_parse *parse) {
3277     return parse->rx < parse->rend;
3278 }
3279
3280 static bool match(struct re_parse *parse, char m) {
3281     if (!more(parse))
3282         return false;
3283     if (*parse->rx == m) {
3284         parse->rx += 1;
3285         return true;
3286     }
3287     return false;
3288 }
3289
3290 static bool peek(struct re_parse *parse, const char *chars) {
3291     return *parse->rx != '\0' && strchr(chars, *parse->rx) != NULL;
3292 }
3293
3294 static bool next(struct re_parse *parse, char *c) {
3295     if (!more(parse))
3296         return false;
3297     *c = *parse->rx;
3298     parse->rx += 1;
3299     return true;
3300 }
3301
3302 static bool parse_char(struct re_parse *parse, int quoted, char *c) {
3303     if (!more(parse))
3304         return false;
3305     if (quoted && *parse->rx == '\\') {
3306         parse->rx += 1;
3307         return next(parse, c);
3308     } else {
3309         return next(parse, c);
3310     }
3311 }
3312
3313 static void add_re_char(struct re *re, uchar from, uchar to) {
3314     assert(re->type == CSET);
3315     for (unsigned int c = from; c <= to; c++)
3316         bitset_set(re->cset, c);
3317 }
3318
3319 static void parse_char_class(struct re_parse *parse, struct re *re) {
3320     if (! more(parse)) {
3321         parse->error = REG_EBRACK;
3322         goto error;
3323     }
3324     char from, to;
3325     parse_char(parse, 0, &from);
3326     to = from;
3327     if (match(parse, '-')) {
3328         if (! more(parse)) {
3329             parse->error = REG_EBRACK;
3330             goto error;
3331         }
3332         if (peek(parse, "]")) {
3333             if (from > to) {
3334                 parse->error = REG_ERANGE;
3335                 goto error;
3336             }
3337             add_re_char(re, from, to);
3338             add_re_char(re, '-', '-');
3339             return;
3340         } else if (!parse_char(parse, 0, &to)) {
3341             parse->error = REG_ERANGE;
3342             goto error;
3343         }
3344     }
3345     if (from > to) {
3346         parse->error = REG_ERANGE;
3347         goto error;
3348     }
3349     add_re_char(re, from, to);
3350  error:
3351     return;
3352 }
3353
3354 static struct re *parse_simple_exp(struct re_parse *parse) {
3355     struct re *re = NULL;
3356
3357     if (match(parse, '[')) {
3358         bool negate = match(parse, '^');
3359         re = make_re_char_set(negate, parse->no_ranges);
3360         if (re == NULL) {
3361             parse->error = REG_ESPACE;
3362             goto error;
3363         }
3364         parse_char_class(parse, re);
3365         if (parse->error != REG_NOERROR)
3366             goto error;
3367         while (more(parse) && ! peek(parse, "]")) {
3368             parse_char_class(parse, re);
3369             if (parse->error != REG_NOERROR)
3370                 goto error;
3371         }
3372         if (! match(parse, ']')) {
3373             parse->error = REG_EBRACK;
3374             goto error;
3375         }
3376     } else if (match(parse, '(')) {
3377         if (match(parse, ')')) {
3378             re = make_re(EPSILON);
3379             if (re == NULL) {
3380                 parse->error = REG_ESPACE;
3381                 goto error;
3382             }
3383         } else {
3384             re = parse_regexp(parse);
3385             if (re == NULL)
3386                 goto error;
3387             if (! match(parse, ')')) {
3388                 parse->error = REG_EPAREN;
3389                 goto error;
3390             }
3391         }
3392     } else if (match(parse, '.')) {
3393         re = make_re_char_set(1, parse->no_ranges);
3394         if (re == NULL) {
3395             parse->error = REG_ESPACE;
3396             goto error;
3397         }
3398         add_re_char(re, '\n', '\n');
3399     } else if (more(parse)) {
3400         char c;
3401         if (!parse_char(parse, 1, &c)) {
3402             parse->error = REG_EESCAPE;
3403             goto error;
3404         }
3405         re = make_re_char(c);
3406         if (re == NULL) {
3407             parse->error = REG_ESPACE;
3408             goto error;
3409         }
3410     } else {
3411         re = make_re(EPSILON);
3412         if (re == NULL) {
3413             parse->error = REG_ESPACE;
3414             goto error;
3415         }
3416     }
3417     return re;
3418  error:
3419     re_unref(re);
3420     return NULL;
3421 }
3422
3423 static int parse_int(struct re_parse *parse) {
3424     const char *lim;
3425     char *end;
3426     size_t used;
3427     long l;
3428
3429     /* We need to be careful that strtoul will never access
3430      * memory beyond parse->rend
3431      */
3432     for (lim = parse->rx; lim < parse->rend && *lim >= '0' && *lim <= '9';
3433          lim++);
3434     if (lim < parse->rend) {
3435         l = strtoul(parse->rx, &end, 10);
3436         used = end - parse->rx;
3437     } else {
3438         char *s = strndup(parse->rx, parse->rend - parse->rx);
3439         if (s == NULL) {
3440             parse->error = REG_ESPACE;
3441             return -1;
3442         }
3443         l = strtoul(s, &end, 10);
3444         used = end - s;
3445         free(s);
3446     }
3447
3448     if (used == 0)
3449         return -1;
3450     parse->rx += used;
3451     if ((l<0) || (l > INT_MAX)) {
3452         parse->error = REG_BADBR;
3453         return -1;
3454     }
3455     return (int) l;
3456 }
3457
3458 static struct re *parse_repeated_exp(struct re_parse *parse) {
3459     struct re *re = parse_simple_exp(parse);
3460     if (re == NULL)
3461         goto error;
3462     if (match(parse, '?')) {
3463         re = make_re_rep(re, 0, 1);
3464     } else if (match(parse, '*')) {
3465         re = make_re_rep(re, 0, -1);
3466     } else if (match(parse, '+')) {
3467         re = make_re_rep(re, 1, -1);
3468     } else if (match(parse, '{')) {
3469         int min, max;
3470         min = parse_int(parse);
3471         if (min == -1)
3472             goto error;
3473         if (match(parse, ',')) {
3474             max = parse_int(parse);
3475             if (max == -1)
3476                 max = -1;      /* If it's not an int, it means 'unbounded' */
3477             if (! match(parse, '}')) {
3478                 parse->error = REG_EBRACE;
3479                 goto error;
3480             }
3481         } else if (match(parse, '}')) {
3482             max = min;
3483         } else {
3484             parse->error = REG_EBRACE;
3485             goto error;
3486         }
3487         if (min > max && max != -1) {
3488             parse->error = REG_BADBR;
3489             goto error;
3490         }
3491         re = make_re_rep(re, min, max);
3492     }
3493     if (re == NULL)
3494         parse->error = REG_ESPACE;
3495     return re;
3496  error:
3497     re_unref(re);
3498     return NULL;
3499 }
3500
3501 static struct re *parse_concat_exp(struct re_parse *parse) {
3502     struct re *re = parse_repeated_exp(parse);
3503     if (re == NULL)
3504         goto error;
3505
3506     if (more(parse) && ! peek(parse, ")|")) {
3507         struct re *re2 = parse_concat_exp(parse);
3508         if (re2 == NULL)
3509             goto error;
3510         re = make_re_binop(CONCAT, re, re2);
3511         if (re == NULL) {
3512             parse->error = REG_ESPACE;
3513             goto error;
3514         }
3515     }
3516     return re;
3517
3518  error:
3519     re_unref(re);
3520     return NULL;
3521 }
3522
3523 static struct re *parse_regexp(struct re_parse *parse) {
3524     struct re *re = NULL;
3525
3526     /* Something like (|r) */
3527     if (peek(parse, "|"))
3528         re = make_re(EPSILON);
3529     else
3530         re = parse_concat_exp(parse);
3531     if (re == NULL)
3532         goto error;
3533
3534     if (match(parse, '|')) {
3535         struct re *re2 = NULL;
3536         /* Something like (r|) */
3537         if (peek(parse, ")"))
3538             re2 = make_re(EPSILON);
3539         else
3540             re2 = parse_regexp(parse);
3541         if (re2 == NULL)
3542             goto error;
3543
3544         re = make_re_binop(UNION, re, re2);
3545         if (re == NULL) {
3546             parse->error = REG_ESPACE;
3547             goto error;
3548         }
3549     }
3550     return re;
3551
3552  error:
3553     re_unref(re);
3554     return NULL;
3555 }
3556
3557 /*
3558  * Convert a STRUCT RE to a string. Code is complicated by the fact that
3559  * we try to be clever and avoid unneeded parens and concatenation with
3560  * epsilon etc.
3561  */
3562 static int re_as_string(const struct re *re, struct re_str *str);
3563
3564 static int re_binop_count(enum re_type type, const struct re *re) {
3565     assert(type == CONCAT || type == UNION);
3566     if (re->type == type) {
3567         return re_binop_count(type, re->exp1) + re_binop_count(type, re->exp2);
3568     } else {
3569         return 1;
3570     }
3571 }
3572
3573 static int re_binop_store(enum re_type type, const struct re *re,
3574                           const struct re **list) {
3575     int pos = 0;
3576     if (type == re->type) {
3577         pos = re_binop_store(type, re->exp1, list);
3578         pos += re_binop_store(type, re->exp2, list + pos);
3579     } else {
3580         list[0] = re;
3581         pos = 1;
3582     }
3583     return pos;
3584 }
3585
3586 static int re_union_as_string(const struct re *re, struct re_str *str) {
3587     assert(re->type == UNION);
3588
3589     int result = -1;
3590     const struct re **res = NULL;
3591     struct re_str *strings = NULL;
3592     int nre = 0, r;
3593
3594     nre = re_binop_count(re->type, re);
3595     r = ALLOC_N(res, nre);
3596     if (r < 0)
3597         goto done;
3598
3599     re_binop_store(re->type, re, res);
3600
3601     r = ALLOC_N(strings, nre);
3602     if (r < 0)
3603         goto error;
3604
3605     str->len = 0;
3606     for (int i=0; i < nre; i++) {
3607         if (re_as_string(res[i], strings + i) < 0)
3608             goto error;
3609         str->len += strings[i].len;
3610     }
3611     str->len += nre-1;
3612
3613     r = re_str_alloc(str);
3614     if (r < 0)
3615         goto error;
3616
3617     char *p = str->rx;
3618     for (int i=0; i < nre; i++) {
3619         if (i>0)
3620             *p++ = '|';
3621         memcpy(p, strings[i].rx, strings[i].len);
3622         p += strings[i].len;
3623     }
3624
3625     result = 0;
3626  done:
3627     free(res);
3628     if (strings != NULL) {
3629         for (int i=0; i < nre; i++)
3630             release_re_str(strings + i);
3631     }
3632     free(strings);
3633     return result;
3634  error:
3635     release_re_str(str);
3636     result = -1;
3637     goto done;
3638 }
3639
3640 ATTRIBUTE_PURE
3641 static int re_needs_parens_in_concat(const struct re *re) {
3642     return (re->type != CHAR && re->type != CSET && re->type != ITER);
3643 }
3644
3645 static int re_concat_as_string(const struct re *re, struct re_str *str) {
3646     assert(re->type == CONCAT);
3647
3648     const struct re **res = NULL;
3649     struct re_str *strings = NULL;
3650     int nre = 0, r;
3651     int result = -1;
3652
3653     nre = re_binop_count(re->type, re);
3654     r = ALLOC_N(res, nre);
3655     if (r < 0)
3656         goto error;
3657     re_binop_store(re->type, re, res);
3658
3659     r = ALLOC_N(strings, nre);
3660     if (r < 0)
3661         goto error;
3662
3663     str->len = 0;
3664     for (int i=0; i < nre; i++) {
3665         if (res[i]->type == EPSILON)
3666             continue;
3667         if (re_as_string(res[i], strings + i) < 0)
3668             goto error;
3669         str->len += strings[i].len;
3670         if (re_needs_parens_in_concat(res[i]))
3671             str->len += 2;
3672     }
3673
3674     r = re_str_alloc(str);
3675     if (r < 0)
3676         goto error;
3677
3678     char *p = str->rx;
3679     for (int i=0; i < nre; i++) {
3680         if (res[i]->type == EPSILON)
3681             continue;
3682         if (re_needs_parens_in_concat(res[i]))
3683             *p++ = '(';
3684         p = memcpy(p, strings[i].rx, strings[i].len);
3685         p += strings[i].len;
3686         if (re_needs_parens_in_concat(res[i]))
3687             *p++ = ')';
3688     }
3689
3690     result = 0;
3691  done:
3692     free(res);
3693     if (strings != NULL) {
3694         for (int i=0; i < nre; i++)
3695             release_re_str(strings + i);
3696     }
3697     free(strings);
3698     return result;
3699  error:
3700     release_re_str(str);
3701     result = -1;
3702     goto done;
3703 }
3704
3705 static bool cset_contains(const struct re *cset, int c) {
3706     return bitset_get(cset->cset, c) != cset->negate;
3707 }
3708
3709 static int re_cset_as_string(const struct re *re, struct re_str *str) {
3710     const uchar rbrack = ']';
3711     const uchar dash = '-';
3712     const uchar nul = '\0';
3713
3714     static const char *const empty_set = "[]";
3715     static const char *const total_set = "(.|\n)";
3716     static const char *const not_newline = ".";
3717
3718     char *s;
3719     int from, to, negate;
3720     size_t len;
3721     int incl_rbrack, incl_dash;
3722     int r;
3723
3724     str->len = strlen(empty_set);
3725
3726     /* We can not include NUL explicitly in a CSET since we use ordinary
3727        NUL delimited strings to represent them. That means that we need to
3728        use negated representation if NUL is to be included (and vice versa)
3729     */
3730     negate = cset_contains(re, nul);
3731     if (negate) {
3732         for (from = UCHAR_MIN;
3733              from <= UCHAR_MAX && cset_contains(re, from);
3734              from += 1);
3735         if (from > UCHAR_MAX) {
3736             /* Special case: the set matches every character */
3737             str->rx = strdup(total_set);
3738             goto done;
3739         }
3740         if (from == '\n') {
3741             for (from += 1;
3742                  from <= UCHAR_MAX && cset_contains(re, from);
3743                  from += 1);
3744             if (from > UCHAR_MAX) {
3745                 /* Special case: the set matches everything but '\n' */
3746                 str->rx = strdup(not_newline);
3747                 goto done;
3748             }
3749         }
3750     }
3751
3752     /* See if ']' and '-' will be explicitly included in the character set
3753        (INCL_RBRACK, INCL_DASH) As we loop over the character set, we reset
3754        these flags if they are in the set, but not mentioned explicitly
3755     */
3756     incl_rbrack = cset_contains(re, rbrack) != negate;
3757     incl_dash = cset_contains(re, dash) != negate;
3758
3759     if (re->no_ranges) {
3760         for (from = UCHAR_MIN; from <= UCHAR_MAX; from++)
3761             if (cset_contains(re, from) != negate)
3762                 str->len += 1;
3763     } else {
3764         for (from = UCHAR_MIN; from <= UCHAR_MAX; from = to+1) {
3765             while (from <= UCHAR_MAX && cset_contains(re, from) == negate)
3766                 from += 1;
3767             if (from > UCHAR_MAX)
3768                 break;
3769             for (to = from;
3770                  to < UCHAR_MAX && (cset_contains(re, to+1) != negate);
3771                  to++);
3772
3773             if (to == from && (from == rbrack || from == dash))
3774                 continue;
3775             if (from == rbrack || from == dash)
3776                 from += 1;
3777             if (to == rbrack || to == dash)
3778                 to -= 1;
3779
3780             len = (to == from) ? 1 : ((to == from + 1) ? 2 : 3);
3781
3782             if (from < rbrack && rbrack < to)
3783                 incl_rbrack = 0;
3784             if (from < dash && dash < to)
3785                 incl_dash = 0;
3786             str->len += len;
3787         }
3788         str->len += incl_rbrack + incl_dash;
3789     }
3790     if (negate)
3791         str->len += 1;        /* For the ^ */
3792
3793     r = re_str_alloc(str);
3794     if (r < 0)
3795         goto error;
3796
3797     s = str->rx;
3798     *s++ = '[';
3799     if (negate)
3800         *s++ = '^';
3801     if (incl_rbrack)
3802         *s++ = rbrack;
3803
3804     if (re->no_ranges) {
3805         for (from = UCHAR_MIN; from <= UCHAR_MAX; from++) {
3806             if (from == rbrack || from == dash)
3807                 continue;
3808             if (cset_contains(re, from) != negate)
3809                 *s++ = from;
3810         }
3811     } else {
3812         for (from = UCHAR_MIN; from <= UCHAR_MAX; from = to+1) {
3813             while (from <= UCHAR_MAX && cset_contains(re, from) == negate)
3814                 from += 1;
3815             if (from > UCHAR_MAX)
3816                 break;
3817             for (to = from;
3818                  to < UCHAR_MAX && (cset_contains(re, to+1) != negate);
3819                  to++);
3820
3821             if (to == from && (from == rbrack || from == dash))
3822                 continue;
3823             if (from == rbrack || from == dash)
3824                 from += 1;
3825             if (to == rbrack || to == dash)
3826                 to -= 1;
3827
3828             if (to == from) {
3829                 *s++ = from;
3830             } else if (to == from + 1) {
3831                 *s++ = from;
3832                 *s++ = to;
3833             } else {
3834                 *s++ = from;
3835                 *s++ = '-';
3836                 *s++ = to;
3837             }
3838         }
3839     }
3840     if (incl_dash)
3841         *s++ = dash;
3842
3843     *s = ']';
3844  done:
3845     if (str->rx == NULL)
3846         goto error;
3847     str->len = strlen(str->rx);
3848     return 0;
3849  error:
3850     release_re_str(str);
3851     return -1;
3852 }
3853
3854 static int re_iter_as_string(const struct re *re, struct re_str *str) {
3855     const char *quant = NULL;
3856     char *iter = NULL;
3857     int r, result = -1;
3858
3859     if (re_as_string(re->exp, str) < 0)
3860         return -1;
3861
3862     if (re->min == 0 && re->max == -1) {
3863         quant = "*";
3864     } else if (re->min == 1 && re->max == -1) {
3865         quant = "+";
3866     } else if (re->min == 0 && re->max == 1) {
3867         quant = "?";
3868     } else if (re->max == -1) {
3869         r = asprintf(&iter, "{%d,}", re->min);
3870         if (r < 0)
3871             return -1;
3872         quant = iter;
3873     } else {
3874         r = asprintf(&iter, "{%d,%d}", re->min, re->max);
3875         if (r < 0)
3876             return -1;
3877         quant = iter;
3878     }
3879
3880     if (re->exp->type == CHAR || re->exp->type == CSET) {
3881         if (REALLOC_N(str->rx, str->len + strlen(quant) + 1) < 0)
3882             goto error;
3883         strcpy(str->rx + str->len, quant);
3884         str->len += strlen(quant);
3885     } else {
3886         /* Format '(' + str->rx ')' + quant */
3887         if (REALLOC_N(str->rx, str->len + strlen(quant) + 1 + 2) < 0)
3888             goto error;
3889         memmove(str->rx + 1, str->rx, str->len);
3890         str->rx[0] = '(';
3891         str->rx[str->len + 1] = ')';
3892         str->len += 2;
3893         strcpy(str->rx + str->len, quant);
3894         str->len += strlen(quant);
3895     }
3896
3897     result = 0;
3898  done:
3899     FREE(iter);
3900     return result;
3901  error:
3902     release_re_str(str);
3903     goto done;
3904 }
3905
3906 static int re_as_string(const struct re *re, struct re_str *str) {
3907     /* Characters that must be escaped */
3908     static const char * const special_chars = ".()[]{}*|+?\\^$";
3909     int result = 0;
3910
3911     switch(re->type) {
3912     case UNION:
3913         result = re_union_as_string(re, str);
3914         break;
3915     case CONCAT:
3916         result = re_concat_as_string(re, str);
3917         break;
3918     case CSET:
3919         result = re_cset_as_string(re, str);
3920         break;
3921     case CHAR:
3922         if (re->c == '\0' || strchr(special_chars, re->c) == NULL) {
3923             if (ALLOC_N(str->rx, 2) < 0)
3924                 goto error;
3925             str->rx[0] = re->c;
3926             str->len = 1;
3927         } else {
3928             if (ALLOC_N(str->rx, 3) < 0)
3929                 goto error;
3930             str->rx[0] = '\\';
3931             str->rx[1] = re->c;
3932             str->len = strlen(str->rx);
3933         }
3934         break;
3935     case ITER:
3936         result = re_iter_as_string(re, str);
3937         break;
3938     case EPSILON:
3939         if (ALLOC_N(str->rx, 3) < 0)
3940             goto error;
3941         strcpy(str->rx, "()");
3942         str->len = strlen(str->rx);
3943         break;
3944     default:
3945         assert(0);
3946         abort();
3947         break;
3948     }
3949     return result;
3950  error:
3951     release_re_str(str);
3952     return -1;
3953 }
3954
3955 static int convert_trans_to_re(struct state *s) {
3956     struct re *re = NULL;
3957     size_t nto = 1;
3958     struct trans *trans = NULL;
3959     int r;
3960
3961     if (s->tused == 0)
3962         return 0;
3963
3964     qsort(s->trans, s->tused, sizeof(*s->trans), trans_to_cmp);
3965     for (int i = 0; i < s->tused - 1; i++) {
3966         if (s->trans[i].to != s->trans[i+1].to)
3967             nto += 1;
3968     }
3969     r = ALLOC_N(trans, nto);
3970     if (r < 0)
3971         goto error;
3972
3973     struct state *to = s->trans[0].to;
3974     int tind = 0;
3975     for_each_trans(t, s) {
3976         if (t->to != to) {
3977             trans[tind].to = to;
3978             trans[tind].re = re;
3979             tind += 1;
3980             re = NULL;
3981             to = t->to;
3982         }
3983         if (re == NULL) {
3984             re = make_re_char_set(0, 0);
3985             if (re == NULL)
3986                 goto error;
3987         }
3988         add_re_char(re, t->min, t->max);
3989     }
3990     assert(nto == tind + 1);
3991     trans[tind].to = to;
3992     trans[tind].re = re;
3993
3994     /* Simplify CSETs with a single char to a CHAR */
3995     for (int t=0; t < nto; t++) {
3996         int cnt = 0;
3997         uchar chr = UCHAR_MIN;
3998         for (int c = 0; c < UCHAR_NUM; c++) {
3999             if (bitset_get(trans[t].re->cset, c)) {
4000                 cnt += 1;
4001                 chr = c;
4002             }
4003         }
4004         if (cnt == 1) {
4005             re_unref(trans[t].re);
4006             trans[t].re = make_re_char(chr);
4007             if (trans[t].re == NULL)
4008                 goto error;
4009         }
4010     }
4011     free_trans(s);
4012     s->trans = trans;
4013     s->tused = s->tsize = nto;
4014     return 0;
4015
4016  error:
4017     if (trans)
4018         for (int i=0; i < nto; i++)
4019             unref(trans[i].re, re);
4020     free(trans);
4021     return -1;
4022 }
4023
4024 ATTRIBUTE_RETURN_CHECK
4025 static int add_new_re_trans(struct state *s1, struct state *s2,
4026                             struct re *re) {
4027     int r;
4028     r = add_new_trans(s1, s2, 0, 0);
4029     if (r < 0)
4030         return -1;
4031     last_trans(s1)->re = re;
4032     return 0;
4033 }
4034
4035 /* Add the regular expression R1 . LOOP* . R2 to the transition
4036    from S1 to S2. */
4037 static int re_collapse_trans(struct state *s1, struct state *s2,
4038                              struct re *r1, struct re *loop, struct re *r2) {
4039     struct re *re = NULL;
4040
4041     if (loop->type != EPSILON) {
4042         loop = make_re_rep(ref(loop), 0, -1);
4043         if (loop == NULL)
4044             goto error;
4045     }
4046
4047     if (r1->type == EPSILON) {
4048         if (loop->type == EPSILON) {
4049             re = ref(r2);
4050         } else {
4051             re = make_re_binop(CONCAT, loop, ref(r2));
4052         }
4053     } else {
4054         if (loop->type == EPSILON) {
4055             if (r2->type == EPSILON) {
4056                 re = ref(r1);
4057             } else {
4058                 re = make_re_binop(CONCAT, ref(r1), ref(r2));
4059             }
4060         } else {
4061             re = make_re_binop(CONCAT, ref(r1), loop);
4062             if (re != NULL && r2->type != EPSILON) {
4063                 re = make_re_binop(CONCAT, re, ref(r2));
4064             }
4065         }
4066     }
4067     if (re == NULL)
4068         goto error;
4069
4070     struct trans *t = NULL;
4071     for (t = s1->trans; t <= last_trans(s1) && t->to != s2; t += 1);
4072     if (t > last_trans(s1)) {
4073         if (add_new_re_trans(s1, s2, re) < 0)
4074             goto error;
4075     } else {
4076         if (t->re == NULL) {
4077             t->re = re;
4078         } else {
4079             t->re = make_re_binop(UNION, re, t->re);
4080             if (t->re == NULL)
4081                 goto error;
4082         }
4083     }
4084     return 0;
4085  error:
4086     // FIXME: make sure we don't leak loop
4087     return -1;
4088 }
4089
4090 static int convert_strings(struct fa *fa) {
4091     struct state_set *worklist = state_set_init(-1, S_NONE);
4092     int result = -1;
4093
4094     E(worklist == NULL);
4095
4096     /* Abuse hash to count indegree, reachable to mark visited states */
4097     list_for_each(s, fa->initial) {
4098         s->hash = 0;
4099         s->reachable = 0;
4100     }
4101
4102     list_for_each(s, fa->initial) {
4103         for_each_trans(t, s) {
4104             t->to->hash += 1;
4105         }
4106     }
4107
4108     for (struct state *s = fa->initial;
4109          s != NULL;
4110          s = state_set_pop(worklist)) {
4111         for (int i=0; i < s->tused; i++) {
4112             struct trans *t = s->trans + i;
4113             struct state *to = t->to;
4114             while (to->hash == 1 && to->tused == 1 && ! to->accept) {
4115                 if (t->re == NULL) {
4116                     t->re = to->trans->re;
4117                     to->trans->re = NULL;
4118                 } else {
4119                     t->re = make_re_binop(CONCAT, t->re, to->trans->re);
4120                     if (t->re == NULL)
4121                         goto error;
4122                 }
4123                 t->to = to->trans->to;
4124                 to->tused = 0;
4125                 to->hash -= 1;
4126                 to = t->to;
4127                 for (int j=0; j < s->tused; j++) {
4128                     if (j != i && s->trans[j].to == to) {
4129                         /* Combine transitions i and j; remove trans j */
4130                         t->re = make_re_binop(UNION, t->re, s->trans[j].re);
4131                         if (t->re == NULL)
4132                             goto error;
4133                         memmove(s->trans + j, s->trans + j + 1,
4134                                 sizeof(s->trans[j]) * (s->tused - j - 1));
4135                         to->hash -= 1;
4136                         s->tused -= 1;
4137                         if (j < i) {
4138                             i = i - 1;
4139                             t = s->trans + i;
4140                         }
4141                     }
4142                 }
4143             }
4144
4145             if (! to->reachable) {
4146                 to->reachable = 1;
4147                 F(state_set_push(worklist, to));
4148             }
4149         }
4150     }
4151
4152     for (struct state *s = fa->initial; s->next != NULL; ) {
4153         if (s->next->hash == 0 && s->next->tused == 0) {
4154             struct state *del = s->next;
4155             s->next = del->next;
4156             free(del->trans);
4157             free(del);
4158         } else {
4159             s = s->next;
4160         }
4161     }
4162     result = 0;
4163
4164  error:
4165     state_set_free(worklist);
4166     return result;
4167 }
4168
4169 /* Convert an FA to a regular expression.
4170  * The strategy is the following:
4171  * (1) For all states S1 and S2, convert the transitions between them
4172  *     into one transition whose regexp is a CSET
4173  * (2) Add a new initial state INI and a new final state FIN to the automaton,
4174  *     a transition from INI to the old initial state of FA, and a transition
4175  *     from all accepting states of FA to FIN; the regexp on those transitions
4176  *     matches only the empty word
4177  * (3) Eliminate states S (except for INI and FIN) one by one:
4178  *     Let LOOP the regexp for the transition S -> S if it exists, epsilon
4179  *     otherwise.
4180  *     For all S1, S2 different from S with S1 -> S -> S2
4181  *       Let R1 the regexp of S1 -> S
4182  *           R2 the regexp of S -> S2
4183  *           R3 the regexp S1 -> S2 (or epsilon if no such transition)
4184  *        set the regexp on the transition S1 -> S2 to
4185  *          R1 . (LOOP)* . R2 | R3
4186  * (4) The regexp for the whole FA can now be found as the regexp of
4187  *     the transition INI -> FIN
4188  * (5) Convert that STRUCT RE to a string with RE_AS_STRING
4189  */
4190 int fa_as_regexp(struct fa *fa, char **regexp, size_t *regexp_len) {
4191     int r;
4192     struct state *fin = NULL, *ini = NULL;
4193     struct re *eps = NULL;
4194
4195     *regexp = NULL;
4196     *regexp_len = 0;
4197     fa = fa_clone(fa);
4198     if (fa == NULL)
4199         goto error;
4200
4201     eps = make_re(EPSILON);
4202     if (eps == NULL)
4203         goto error;
4204
4205     fin = add_state(fa,1);
4206     if (fin == NULL)
4207         goto error;
4208
4209     fa->trans_re = 1;
4210
4211     list_for_each(s, fa->initial) {
4212         r = convert_trans_to_re(s);
4213         if (r < 0)
4214             goto error;
4215         if (s->accept && s != fin) {
4216             r = add_new_re_trans(s, fin, ref(eps));
4217             if (r < 0)
4218                 goto error;
4219             s->accept = 0;
4220         }
4221     }
4222
4223     ini = add_state(fa, 0);
4224     if (ini == NULL)
4225         goto error;
4226
4227     r = add_new_re_trans(ini, fa->initial, ref(eps));
4228     if (r < 0)
4229         goto error;
4230     set_initial(fa, ini);
4231
4232     convert_strings(fa);
4233
4234     list_for_each(s, fa->initial->next) {
4235         if (s == fin)
4236             continue;
4237         /* Eliminate S */
4238         struct re *loop = eps;
4239         for_each_trans(t, s) {
4240             if (t->to == s)
4241                 loop = t->re;
4242         }
4243         list_for_each(s1, fa->initial) {
4244             if (s == s1)
4245                 continue;
4246             for (int t1 = 0; t1 < s1->tused; t1++) {
4247                 if (s1->trans[t1].to == s) {
4248                     for (int t = 0; t < s->tused; t++) {
4249                         if (s->trans[t].to == s)
4250                             continue;
4251                         r = re_collapse_trans(s1, s->trans[t].to,
4252                                               s1->trans[t1].re,
4253                                               loop,
4254                                               s->trans[t].re);
4255                         if (r < 0)
4256                             goto error;
4257                     }
4258                 }
4259             }
4260         }
4261     }
4262
4263     re_unref(eps);
4264
4265     for_each_trans(t, fa->initial) {
4266         if (t->to == fin) {
4267             struct re_str str;
4268             MEMZERO(&str, 1);
4269             if (re_as_string(t->re, &str) < 0)
4270                 goto error;
4271             *regexp = str.rx;
4272             *regexp_len = str.len;
4273         }
4274     }
4275
4276     list_for_each(s, fa->initial) {
4277         for_each_trans(t, s) {
4278             unref(t->re, re);
4279         }
4280     }
4281     fa_free(fa);
4282
4283     return 0;
4284  error:
4285     fa_free(fa);
4286     re_unref(eps);
4287     return -1;
4288 }
4289
4290 static int re_restrict_alphabet(struct re *re, uchar from, uchar to) {
4291     int r1, r2;
4292     int result = 0;
4293
4294     switch(re->type) {
4295     case UNION:
4296     case CONCAT:
4297         r1 = re_restrict_alphabet(re->exp1, from, to);
4298         r2 = re_restrict_alphabet(re->exp2, from, to);
4299         result = (r1 != 0) ? r1 : r2;
4300         break;
4301     case CSET:
4302         if (re->negate) {
4303             re->negate = 0;
4304             bitset_negate(re->cset, UCHAR_NUM);
4305         }
4306         for (int i=from; i <= to; i++)
4307             bitset_clr(re->cset, i);
4308         break;
4309     case CHAR:
4310         if (from <= re->c && re->c <= to)
4311             result = -1;
4312         break;
4313     case ITER:
4314         result = re_restrict_alphabet(re->exp, from, to);
4315         break;
4316     case EPSILON:
4317         break;
4318     default:
4319         assert(0);
4320         abort();
4321         break;
4322     }
4323     return result;
4324 }
4325
4326 int fa_restrict_alphabet(const char *regexp, size_t regexp_len,
4327                          char **newregexp, size_t *newregexp_len,
4328                          char from, char to) {
4329     int result;
4330     struct re *re = NULL;
4331     struct re_parse parse;
4332     struct re_str str;
4333
4334     *newregexp = NULL;
4335     MEMZERO(&parse, 1);
4336     parse.rx = regexp;
4337     parse.rend = regexp + regexp_len;
4338     parse.error = REG_NOERROR;
4339     re = parse_regexp(&parse);
4340     if (parse.error != REG_NOERROR)
4341         return parse.error;
4342
4343     result = re_restrict_alphabet(re, from, to);
4344     if (result != 0) {
4345         result = -2;
4346         goto done;
4347     }
4348
4349     MEMZERO(&str, 1);
4350     result = re_as_string(re, &str);
4351     *newregexp = str.rx;
4352     *newregexp_len = str.len;
4353  done:
4354     re_unref(re);
4355     return result;
4356 }
4357
4358 int fa_expand_char_ranges(const char *regexp, size_t regexp_len,
4359                           char **newregexp, size_t *newregexp_len) {
4360     int result;
4361     struct re *re = NULL;
4362     struct re_parse parse;
4363     struct re_str str;
4364
4365     *newregexp = NULL;
4366     MEMZERO(&parse, 1);
4367     parse.rx = regexp;
4368     parse.rend = regexp + regexp_len;
4369     parse.error = REG_NOERROR;
4370     parse.no_ranges = 1;
4371     re = parse_regexp(&parse);
4372     if (parse.error != REG_NOERROR)
4373         return parse.error;
4374
4375     MEMZERO(&str, 1);
4376     result = re_as_string(re, &str);
4377     *newregexp = str.rx;
4378     *newregexp_len = str.len;
4379     re_unref(re);
4380     return result;
4381 }
4382
4383 /* Expand regexp so that it is case-insensitive in a case-sensitive match.
4384  *
4385  * Return 1 when a change was made, -1 when an allocation failed, and 0
4386  * when no change was made.
4387  */
4388 static int re_case_expand(struct re *re) {
4389     int result = 0, r1, r2;
4390
4391     switch(re->type) {
4392     case UNION:
4393     case CONCAT:
4394         r1 = re_case_expand(re->exp1);
4395         r2 = re_case_expand(re->exp2);
4396         result = (r1 != 0) ? r1 : r2;
4397         break;
4398     case CSET:
4399         for (int c = 'A'; c <= 'Z'; c++)
4400             if (bitset_get(re->cset, c)) {
4401                 result = 1;
4402                 bitset_set(re->cset, tolower(c));
4403             }
4404         for (int c = 'a'; c <= 'z'; c++)
4405             if (bitset_get(re->cset, c)) {
4406                 result = 1;
4407                 bitset_set(re->cset, toupper(c));
4408             }
4409         break;
4410     case CHAR:
4411         if (isalpha(re->c)) {
4412             int c = re->c;
4413             re->type = CSET;
4414             re->negate = false;
4415             re->no_ranges = 0;
4416             re->cset = bitset_init(UCHAR_NUM);
4417             if (re->cset == NULL)
4418                 return -1;
4419             bitset_set(re->cset, tolower(c));
4420             bitset_set(re->cset, toupper(c));
4421             result = 1;
4422         }
4423         break;
4424     case ITER:
4425         result = re_case_expand(re->exp);
4426         break;
4427     case EPSILON:
4428         break;
4429     default:
4430         assert(0);
4431         abort();
4432         break;
4433     }
4434     return result;
4435 }
4436
4437 int fa_expand_nocase(const char *regexp, size_t regexp_len,
4438                      char **newregexp, size_t *newregexp_len) {
4439     int result, r;
4440     struct re *re = NULL;
4441     struct re_parse parse;
4442     struct re_str str;
4443
4444     *newregexp = NULL;
4445     MEMZERO(&parse, 1);
4446     parse.rx = regexp;
4447     parse.rend = regexp + regexp_len;
4448     parse.error = REG_NOERROR;
4449     re = parse_regexp(&parse);
4450     if (parse.error != REG_NOERROR)
4451         return parse.error;
4452
4453     r = re_case_expand(re);
4454     if (r < 0) {
4455         re_unref(re);
4456         return REG_ESPACE;
4457     }
4458
4459     if (r == 1) {
4460         MEMZERO(&str, 1);
4461         result = re_as_string(re, &str);
4462         *newregexp = str.rx;
4463         *newregexp_len = str.len;
4464     } else {
4465         *newregexp = strndup(regexp, regexp_len);
4466         *newregexp_len = regexp_len;
4467         result = (*newregexp == NULL) ? REG_ESPACE : REG_NOERROR;
4468     }
4469     re_unref(re);
4470     return result;
4471 }
4472
4473 static void print_char(FILE *out, uchar c) {
4474     /* We escape '/' as '\\/' since dot chokes on bare slashes in labels;
4475        Also, a space ' ' is shown as '\s' */
4476     static const char *const escape_from = " \n\t\v\b\r\f\a/\0";
4477     static const char *const escape_to = "sntvbrfa/0";
4478     char *p = strchr(escape_from, c);
4479     if (p != NULL) {
4480         int i = p - escape_from;
4481         fprintf(out, "\\\\%c", escape_to[i]);
4482     } else if (! isprint(c)) {
4483         fprintf(out, "\\\\0%03o", (unsigned char) c);
4484     } else if (c == '"') {
4485         fprintf(out, "\\\"");
4486     } else {
4487         fputc(c, out);
4488     }
4489 }
4490
4491 void fa_dot(FILE *out, struct fa *fa) {
4492     fprintf(out, "digraph {\n  rankdir=LR;");
4493     list_for_each(s, fa->initial) {
4494         if (s->accept) {
4495             fprintf(out, "\"%p\" [shape=doublecircle];\n", s);
4496         } else {
4497             fprintf(out, "\"%p\" [shape=circle];\n", s);
4498         }
4499     }
4500     fprintf(out, "%s -> \"%p\";\n", fa->deterministic ? "dfa" : "nfa",
4501             fa->initial);
4502
4503     struct re_str str;
4504     MEMZERO(&str, 1);
4505     list_for_each(s, fa->initial) {
4506         for_each_trans(t, s) {
4507             fprintf(out, "\"%p\" -> \"%p\" [ label = \"", s, t->to);
4508             if (fa->trans_re) {
4509                 re_as_string(t->re, &str);
4510                 for (int i=0; i < str.len; i++) {
4511                     print_char(out, str.rx[i]);
4512                 }
4513                 release_re_str(&str);
4514             } else {
4515                 print_char(out, t->min);
4516                 if (t->min != t->max) {
4517                     fputc('-', out);
4518                     print_char(out, t->max);
4519                 }
4520             }
4521             fprintf(out, "\" ];\n");
4522         }
4523     }
4524     fprintf(out, "}\n");
4525 }
4526
4527 int fa_json(FILE *out, struct fa *fa) {
4528     hash_val_t *list_hashes = NULL;
4529     int list_size = 100;
4530     int num_states = 0;
4531     int it;
4532     char first = true;
4533     int result = -1;
4534
4535     fprintf(out,"{\n\t\"final\": [");
4536
4537     F(ALLOC_N(list_hashes, list_size));
4538
4539     list_for_each(s, fa->initial) {
4540         if (num_states == list_size - 1){
4541             list_size += list_size;
4542             F(REALLOC_N(list_hashes, list_size));
4543         }
4544         // Store hash value
4545         list_hashes[num_states] = s->hash;
4546         // We use the hashes to map states to Z_{num_states}
4547         s->hash = num_states++;
4548         if (s->accept) {
4549             if (first) {
4550                 fprintf(out,"%ld", s->hash);
4551                 first = false;
4552             } else {
4553                 fprintf(out, ", %ld", s->hash);
4554             }
4555         }
4556     }
4557
4558     fprintf(out, "],\n\t\"deterministic\": %d,\n\t\"transitions\": [\n",
4559             fa->deterministic ? 1 : 0);
4560
4561     first = true;
4562     list_for_each(s, fa->initial) {
4563         for_each_trans(t, s) {
4564             if (!first)
4565                 fprintf(out, ",\n");
4566             first = false;
4567             fprintf(out, "\t\t{ \"from\": %ld, \"to\": %ld, \"on\": \"",
4568                     s->hash, t->to->hash);
4569             print_char(out, t->min);
4570             if (t->min != t->max) {
4571                 fputc('-', out);
4572                 print_char(out, t->max);
4573             }
4574             fprintf(out, "\" }");
4575         }
4576     }
4577
4578     fprintf(out,"\n\t]\n}");
4579     result = 0;
4580
4581 error:
4582     // Restoring hash values to leave the FA structure untouched. That is
4583     // only needed if we actually copied hashes, indicated by num_states
4584     // being non-zero
4585     if (num_states > 0) {
4586         it = 0;
4587         list_for_each(s, fa->initial) {
4588             s->hash = list_hashes[it++];
4589         }
4590     }
4591     free(list_hashes);
4592     return result;
4593 }
4594
4595 bool fa_is_deterministic(struct fa *fa) {
4596     return fa->deterministic;
4597 }
4598
4599 struct state *fa_state_initial(struct fa *fa) {
4600     return fa->initial;
4601 }
4602
4603 bool fa_state_is_accepting(struct state *st) {
4604     return st->accept;
4605 }
4606
4607 struct state* fa_state_next(struct state *st) {
4608     return st->next;
4609 }
4610
4611 size_t fa_state_num_trans(struct state *st) {
4612     return st->tused;
4613 }
4614
4615 int fa_state_trans(struct state *st, size_t i,
4616                    struct state **to, unsigned char *min, unsigned char *max) {
4617     if (st->tused <= i)
4618         return -1;
4619
4620     (*to) = st->trans[i].to;
4621     (*min) = st->trans[i].min;
4622     (*max) = st->trans[i].max;
4623     return 0;
4624 }
4625
4626 /*
4627  * Local variables:
4628  *  indent-tabs-mode: nil
4629  *  c-indent-level: 4
4630  *  c-basic-offset: 4
4631  *  tab-width: 4
4632  * End:
4633  */