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