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     fa->deterministic = 1;
1799     fa->minimal = 1;
1800     return fa;
1801 }
1802
1803 static struct fa *fa_make_epsilon(void) {
1804     struct fa *fa = fa_make_empty();
1805     if (fa) {
1806         fa->initial->accept = 1;
1807         fa->deterministic= 1;
1808         fa->minimal = 1;
1809     }
1810     return fa;
1811 }
1812
1813 static struct fa *fa_make_char(uchar c) {
1814     struct fa *fa = fa_make_empty();
1815     if (! fa)
1816         return NULL;
1817
1818     struct state *s = fa->initial;
1819     struct state *t = add_state(fa, 1);
1820     int r;
1821
1822     if (t == NULL)
1823         goto error;
1824
1825     r = add_new_trans(s, t, c, c);
1826     if (r < 0)
1827         goto error;
1828     fa->deterministic = 1;
1829     fa->minimal = 1;
1830     return fa;
1831  error:
1832     fa_free(fa);
1833     return NULL;
1834 }
1835
1836 struct fa *fa_make_basic(unsigned int basic) {
1837     int r;
1838
1839     if (basic == FA_EMPTY) {
1840         return fa_make_empty();
1841     } else if (basic == FA_EPSILON) {
1842         return fa_make_epsilon();
1843     } else if (basic == FA_TOTAL) {
1844         struct fa *fa = fa_make_epsilon();
1845         r = add_new_trans(fa->initial, fa->initial, UCHAR_MIN, UCHAR_MAX);
1846         if (r < 0) {
1847             fa_free(fa);
1848             fa = NULL;
1849         }
1850         return fa;
1851     }
1852     return NULL;
1853 }
1854
1855 int fa_is_basic(struct fa *fa, unsigned int basic) {
1856     if (basic == FA_EMPTY) {
1857         return ! fa->initial->accept && fa->initial->tused == 0;
1858     } else if (basic == FA_EPSILON) {
1859         return fa->initial->accept && fa->initial->tused == 0;
1860     } else if (basic == FA_TOTAL) {
1861         if (! fa->initial->accept)
1862             return 0;
1863         if (fa->nocase) {
1864             if (fa->initial->tused != 2)
1865                 return 0;
1866             struct trans *t1 = fa->initial->trans;
1867             struct trans *t2 = fa->initial->trans + 1;
1868             if (t1->to != fa->initial || t2->to != fa->initial)
1869                 return 0;
1870             if (t2->max != UCHAR_MAX) {
1871                 t1 = t2;
1872                 t2 = fa->initial->trans;
1873             }
1874             return (t1->min == UCHAR_MIN && t1->max == 'A' - 1 &&
1875                     t2->min == 'Z' + 1 && t2->max == UCHAR_MAX);
1876         } else {
1877             struct trans *t = fa->initial->trans;
1878             return fa->initial->tused == 1 &&
1879                 t->to == fa->initial &&
1880                 t->min == UCHAR_MIN && t->max == UCHAR_MAX;
1881         }
1882     }
1883     return 0;
1884 }
1885
1886 static struct fa *fa_clone(struct fa *fa) {
1887     struct fa *result = NULL;
1888     struct state_set *set = state_set_init(-1, S_DATA|S_SORTED);
1889     int r;
1890
1891     if (fa == NULL || set == NULL || ALLOC(result) < 0)
1892         goto error;
1893
1894     result->deterministic = fa->deterministic;
1895     result->minimal = fa->minimal;
1896     result->nocase = fa->nocase;
1897     list_for_each(s, fa->initial) {
1898         int i = state_set_push(set, s);
1899         E(i < 0);
1900
1901         struct state *q = add_state(result, s->accept);
1902         if (q == NULL)
1903             goto error;
1904         set->data[i] = q;
1905         q->live = s->live;
1906         q->reachable = s->reachable;
1907     }
1908     for (int i=0; i < set->used; i++) {
1909         struct state *s = set->states[i];
1910         struct state *sc = set->data[i];
1911         for_each_trans(t, s) {
1912             int to = state_set_index(set, t->to);
1913             assert(to >= 0);
1914             struct state *toc = set->data[to];
1915             r = add_new_trans(sc, toc, t->min, t->max);
1916             if (r < 0)
1917                 goto error;
1918         }
1919     }
1920     state_set_free(set);
1921     return result;
1922  error:
1923     state_set_free(set);
1924     fa_free(result);
1925     return NULL;
1926 }
1927
1928 static int case_expand(struct fa *fa);
1929
1930 /* Compute FA1|FA2 and set FA1 to that automaton. FA2 is freed */
1931 ATTRIBUTE_RETURN_CHECK
1932 static int union_in_place(struct fa *fa1, struct fa **fa2) {
1933     struct state *s;
1934     int r;
1935
1936     if (fa1->nocase != (*fa2)->nocase) {
1937         if (case_expand(fa1) < 0)
1938             return -1;
1939         if (case_expand(*fa2) < 0)
1940             return -1;
1941     }
1942
1943     s = add_state(fa1, 0);
1944     if (s == NULL)
1945         return -1;
1946     r = add_epsilon_trans(s, fa1->initial);
1947     if (r < 0)
1948         return -1;
1949     r = add_epsilon_trans(s, (*fa2)->initial);
1950     if (r < 0)
1951         return -1;
1952
1953     fa1->deterministic = 0;
1954     fa1->minimal = 0;
1955     fa_merge(fa1, fa2);
1956
1957     set_initial(fa1, s);
1958
1959     return 0;
1960 }
1961
1962 struct fa *fa_union(struct fa *fa1, struct fa *fa2) {
1963     fa1 = fa_clone(fa1);
1964     fa2 = fa_clone(fa2);
1965     if (fa1 == NULL || fa2 == NULL)
1966         goto error;
1967
1968     F(union_in_place(fa1, &fa2));
1969
1970     return fa1;
1971  error:
1972     fa_free(fa1);
1973     fa_free(fa2);
1974     return NULL;
1975 }
1976
1977 /* Concat FA2 onto FA1; frees FA2 and changes FA1 to FA1.FA2 */
1978 ATTRIBUTE_RETURN_CHECK
1979 static int concat_in_place(struct fa *fa1, struct fa **fa2) {
1980     int r;
1981
1982     if (fa1->nocase != (*fa2)->nocase) {
1983         if (case_expand(fa1) < 0)
1984             return -1;
1985         if (case_expand(*fa2) < 0)
1986             return -1;
1987     }
1988
1989     list_for_each(s, fa1->initial) {
1990         if (s->accept) {
1991             s->accept = 0;
1992             r = add_epsilon_trans(s, (*fa2)->initial);
1993             if (r < 0)
1994                 return -1;
1995         }
1996     }
1997
1998     fa1->deterministic = 0;
1999     fa1->minimal = 0;
2000     fa_merge(fa1, fa2);
2001
2002     return 0;
2003 }
2004
2005 struct fa *fa_concat(struct fa *fa1, struct fa *fa2) {
2006     fa1 = fa_clone(fa1);
2007     fa2 = fa_clone(fa2);
2008
2009     if (fa1 == NULL || fa2 == NULL)
2010         goto error;
2011
2012     F(concat_in_place(fa1, &fa2));
2013
2014     F(collect(fa1));
2015
2016     return fa1;
2017
2018  error:
2019     fa_free(fa1);
2020     fa_free(fa2);
2021     return NULL;
2022 }
2023
2024 static struct fa *fa_make_char_set(bitset *cset, int negate) {
2025     struct fa *fa = fa_make_empty();
2026     if (!fa)
2027         return NULL;
2028
2029     struct state *s = fa->initial;
2030     struct state *t = add_state(fa, 1);
2031     int from = 0;
2032     int r;
2033
2034     if (t == NULL)
2035         goto error;
2036
2037     while (from <= UCHAR_MAX) {
2038         while (from <= UCHAR_MAX && bitset_get(cset, from) == negate)
2039             from += 1;
2040         if (from > UCHAR_MAX)
2041             break;
2042         int to = from;
2043         while (to < UCHAR_MAX && (bitset_get(cset, to + 1) == !negate))
2044             to += 1;
2045         r = add_new_trans(s, t, from, to);
2046         if (r < 0)
2047             goto error;
2048         from = to + 1;
2049     }
2050
2051     fa->deterministic = 1;
2052     fa->minimal = 1;
2053     return fa;
2054
2055  error:
2056     fa_free(fa);
2057     return NULL;
2058 }
2059
2060 static struct fa *fa_star(struct fa *fa) {
2061     struct state *s;
2062     int r;
2063
2064     fa = fa_clone(fa);
2065     if (fa == NULL)
2066         return NULL;
2067
2068     s = add_state(fa, 1);
2069     if (s == NULL)
2070         goto error;
2071
2072     r = add_epsilon_trans(s, fa->initial);
2073     if (r < 0)
2074         goto error;
2075
2076     set_initial(fa, s);
2077     list_for_each(p, fa->initial->next) {
2078         if (p->accept) {
2079             r = add_epsilon_trans(p, s);
2080             if (r < 0)
2081                 goto error;
2082         }
2083     }
2084     fa->deterministic = 0;
2085     fa->minimal = 0;
2086
2087     return fa;
2088
2089  error:
2090     fa_free(fa);
2091     return NULL;
2092 }
2093
2094 /* Form the automaton (FA){N}; FA is not modified */
2095 static struct fa *repeat(struct fa *fa, int n) {
2096     if (n == 0) {
2097         return fa_make_epsilon();
2098     } else if (n == 1) {
2099         return fa_clone(fa);
2100     } else {
2101         struct fa *cfa = fa_clone(fa);
2102         if (cfa == NULL)
2103             return NULL;
2104         while (n > 1) {
2105             struct fa *tfa = fa_clone(fa);
2106             if (tfa == NULL) {
2107                 fa_free(cfa);
2108                 return NULL;
2109             }
2110             if (concat_in_place(cfa, &tfa) < 0) {
2111                 fa_free(cfa);
2112                 fa_free(tfa);
2113                 return NULL;
2114             }
2115             n -= 1;
2116         }
2117         return cfa;
2118     }
2119 }
2120
2121 struct fa *fa_iter(struct fa *fa, int min, int max) {
2122     int r;
2123
2124     if (min < 0)
2125         min = 0;
2126
2127     if (min > max && max != -1) {
2128         return fa_make_empty();
2129     }
2130     if (max == -1) {
2131         struct fa *sfa = fa_star(fa);
2132         if (min == 0)
2133             return sfa;
2134         if (! sfa)
2135             return NULL;
2136         struct fa *cfa = repeat(fa, min);
2137         if (! cfa) {
2138             fa_free(sfa);
2139             return NULL;
2140         }
2141         if (concat_in_place(cfa, &sfa) < 0) {
2142             fa_free(sfa);
2143             fa_free(cfa);
2144             return NULL;
2145         }
2146         return cfa;
2147     } else {
2148         struct fa *cfa = NULL;
2149
2150         max -= min;
2151         cfa = repeat(fa, min);
2152         if (cfa == NULL)
2153             return NULL;
2154         if (max > 0) {
2155             struct fa *cfa2 = fa_clone(fa);
2156             if (cfa2 == NULL) {
2157                 fa_free(cfa);
2158                 return NULL;
2159             }
2160             while (max > 1) {
2161                 struct fa *cfa3 = fa_clone(fa);
2162                 if (cfa3 == NULL) {
2163                     fa_free(cfa);
2164                     fa_free(cfa2);
2165                     return NULL;
2166                 }
2167                 list_for_each(s, cfa3->initial) {
2168                     if (s->accept) {
2169                         r = add_epsilon_trans(s, cfa2->initial);
2170                         if (r < 0) {
2171                             fa_free(cfa);
2172                             fa_free(cfa2);
2173                             fa_free(cfa3);
2174                             return NULL;
2175                         }
2176                     }
2177                 }
2178                 fa_merge(cfa3, &cfa2);
2179                 cfa2 = cfa3;
2180                 max -= 1;
2181             }
2182             list_for_each(s, cfa->initial) {
2183                 if (s->accept) {
2184                     r = add_epsilon_trans(s, cfa2->initial);
2185                     if (r < 0) {
2186                         fa_free(cfa);
2187                         fa_free(cfa2);
2188                         return NULL;
2189                     }
2190                 }
2191             }
2192             fa_merge(cfa, &cfa2);
2193             cfa->deterministic = 0;
2194             cfa->minimal = 0;
2195         }
2196         if (collect(cfa) < 0) {
2197             fa_free(cfa);
2198             cfa = NULL;
2199         }
2200         return cfa;
2201     }
2202 }
2203
2204 static void sort_transition_intervals(struct fa *fa) {
2205     list_for_each(s, fa->initial) {
2206         qsort(s->trans, s->tused, sizeof(*s->trans), trans_intv_cmp);
2207     }
2208 }
2209
2210 struct fa *fa_intersect(struct fa *fa1, struct fa *fa2) {
2211     int ret;
2212     struct fa *fa = NULL;
2213     struct state_set *worklist = NULL;
2214     state_triple_hash *newstates = NULL;
2215
2216     if (fa1 == fa2)
2217         return fa_clone(fa1);
2218
2219     if (fa_is_basic(fa1, FA_EMPTY) || fa_is_basic(fa2, FA_EMPTY))
2220         return fa_make_empty();
2221
2222     if (fa1->nocase != fa2->nocase) {
2223         F(case_expand(fa1));
2224         F(case_expand(fa2));
2225     }
2226
2227     fa = fa_make_empty();
2228     worklist = state_set_init(-1, S_NONE);
2229     newstates = state_triple_init();
2230     if (fa == NULL || worklist == NULL || newstates == NULL)
2231         goto error;
2232
2233     sort_transition_intervals(fa1);
2234     sort_transition_intervals(fa2);
2235
2236     F(state_set_push(worklist, fa1->initial));
2237     F(state_set_push(worklist, fa2->initial));
2238     F(state_set_push(worklist, fa->initial));
2239     F(state_triple_push(newstates,
2240                          fa1->initial, fa2->initial, fa->initial));
2241     while (worklist->used) {
2242         struct state *s  = state_set_pop(worklist);
2243         struct state *p2 = state_set_pop(worklist);
2244         struct state *p1 = state_set_pop(worklist);
2245         s->accept = p1->accept && p2->accept;
2246
2247         struct trans *t1 = p1->trans;
2248         struct trans *t2 = p2->trans;
2249         for (int n1 = 0, b2 = 0; n1 < p1->tused; n1++) {
2250             while (b2 < p2->tused && t2[b2].max < t1[n1].min)
2251                 b2++;
2252             for (int n2 = b2;
2253                  n2 < p2->tused && t1[n1].max >= t2[n2].min;
2254                  n2++) {
2255                 if (t2[n2].max >= t1[n1].min) {
2256                     struct state *r = state_triple_thd(newstates,
2257                                                        t1[n1].to, t2[n2].to);
2258                     if (r == NULL) {
2259                         r = add_state(fa, 0);
2260                         E(r == NULL);
2261                         F(state_set_push(worklist, t1[n1].to));
2262                         F(state_set_push(worklist, t2[n2].to));
2263                         F(state_set_push(worklist, r));
2264                         F(state_triple_push(newstates,
2265                                              t1[n1].to, t2[n2].to, r));
2266                     }
2267                     char min = t1[n1].min > t2[n2].min
2268                         ? t1[n1].min : t2[n2].min;
2269                     char max = t1[n1].max < t2[n2].max
2270                         ? t1[n1].max : t2[n2].max;
2271                     ret = add_new_trans(s, r, min, max);
2272                     if (ret < 0)
2273                         goto error;
2274                 }
2275             }
2276         }
2277     }
2278     fa->deterministic = fa1->deterministic && fa2->deterministic;
2279     fa->nocase = fa1->nocase && fa2->nocase;
2280  done:
2281     state_set_free(worklist);
2282     state_triple_free(newstates);
2283     if (fa != NULL) {
2284         if (collect(fa) < 0) {
2285             fa_free(fa);
2286             fa = NULL;
2287         }
2288     }
2289
2290     return fa;
2291  error:
2292     fa_free(fa);
2293     fa = NULL;
2294     goto done;
2295 }
2296
2297 int fa_contains(struct fa *fa1, struct fa *fa2) {
2298     int result = 0;
2299     struct state_set *worklist = NULL;  /* List of pairs of states */
2300     struct state_set *visited = NULL;   /* List of pairs of states */
2301
2302     if (fa1 == NULL || fa2 == NULL)
2303         return -1;
2304
2305     if (fa1 == fa2)
2306         return 1;
2307
2308     F(determinize(fa2, NULL));
2309     sort_transition_intervals(fa1);
2310     sort_transition_intervals(fa2);
2311
2312     F(state_pair_push(&worklist, fa1->initial, fa2->initial));
2313     F(state_pair_push(&visited, fa1->initial, fa2->initial));
2314     while (worklist->used) {
2315         struct state *p1, *p2;
2316         void *v2;
2317         p1 = state_set_pop_data(worklist, &v2);
2318         p2 = v2;
2319
2320         if (p1->accept && !p2->accept)
2321             goto done;
2322
2323         struct trans *t1 = p1->trans;
2324         struct trans *t2 = p2->trans;
2325         for(int n1 = 0, b2 = 0; n1 < p1->tused; n1++) {
2326             while (b2 < p2->tused && t2[b2].max < t1[n1].min)
2327                 b2++;
2328             int min1 = t1[n1].min, max1 = t1[n1].max;
2329             for (int n2 = b2;
2330                  n2 < p2->tused && t1[n1].max >= t2[n2].min;
2331                  n2++) {
2332                 if (t2[n2].min > min1)
2333                     goto done;
2334                 if (t2[n2].max < CHAR_MAX)
2335                     min1 = t2[n2].max + 1;
2336                 else {
2337                     min1 = UCHAR_MAX;
2338                     max1 = UCHAR_MIN;
2339                 }
2340                 if (state_pair_find(visited, t1[n1].to, t2[n2].to) == -1) {
2341                     F(state_pair_push(&worklist, t1[n1].to, t2[n2].to));
2342                     F(state_pair_push(&visited, t1[n1].to, t2[n2].to));
2343                 }
2344             }
2345             if (min1 <= max1)
2346                 goto done;
2347         }
2348     }
2349
2350     result = 1;
2351  done:
2352     state_set_free(worklist);
2353     state_set_free(visited);
2354     return result;
2355  error:
2356     result = -1;
2357     goto done;
2358 }
2359
2360 static int add_crash_trans(struct fa *fa, struct state *s, struct state *crash,
2361                            int min, int max) {
2362     int result;
2363
2364     if (fa->nocase) {
2365         /* Never transition on anything in [A-Z] */
2366         if (min > 'Z' || max < 'A') {
2367             result = add_new_trans(s, crash, min, max);
2368         } else if (min >= 'A' && max <= 'Z') {
2369             result = 0;
2370         } else if (max <= 'Z') {
2371             /* min < 'A' */
2372             result = add_new_trans(s, crash, min, 'A' - 1);
2373         } else if (min >= 'A') {
2374             /* max > 'Z' */
2375             result = add_new_trans(s, crash, 'Z' + 1, max);
2376         } else {
2377             /* min < 'A' && max > 'Z' */
2378             result = add_new_trans(s, crash, min, 'A' - 1);
2379             if (result == 0)
2380                 result = add_new_trans(s, crash, 'Z' + 1, max);
2381         }
2382     } else {
2383         result = add_new_trans(s, crash, min, max);
2384     }
2385     return result;
2386 }
2387
2388 static int totalize(struct fa *fa) {
2389     int r;
2390     struct state *crash = add_state(fa, 0);
2391
2392     E(crash == NULL);
2393     F(mark_reachable(fa));
2394     sort_transition_intervals(fa);
2395
2396     r = add_crash_trans(fa, crash, crash, UCHAR_MIN, UCHAR_MAX);
2397     if (r < 0)
2398         return -1;
2399
2400     list_for_each(s, fa->initial) {
2401         int next = UCHAR_MIN;
2402         int tused = s->tused;
2403         for (int i=0; i < tused; i++) {
2404             uchar min = s->trans[i].min, max = s->trans[i].max;
2405             if (min > next) {
2406                 r = add_crash_trans(fa, s, crash, next, min - 1);
2407                 if (r < 0)
2408                     return -1;
2409             }
2410             if (max + 1 > next)
2411                 next = max + 1;
2412         }
2413         if (next <= UCHAR_MAX) {
2414             r = add_crash_trans(fa, s, crash, next, UCHAR_MAX);
2415             if (r < 0)
2416                 return -1;
2417         }
2418     }
2419     return 0;
2420  error:
2421     return -1;
2422 }
2423
2424 struct fa *fa_complement(struct fa *fa) {
2425     fa = fa_clone(fa);
2426     E(fa == NULL);
2427     F(determinize(fa, NULL));
2428     F(totalize(fa));
2429     list_for_each(s, fa->initial)
2430         s->accept = ! s->accept;
2431
2432     F(collect(fa));
2433     return fa;
2434  error:
2435     fa_free(fa);
2436     return NULL;
2437 }
2438
2439 struct fa *fa_minus(struct fa *fa1, struct fa *fa2) {
2440     if (fa1 == NULL || fa2 == NULL)
2441         return NULL;
2442
2443     if (fa_is_basic(fa1, FA_EMPTY) || fa1 == fa2)
2444         return fa_make_empty();
2445     if (fa_is_basic(fa2, FA_EMPTY))
2446         return fa_clone(fa1);
2447
2448     struct fa *cfa2 = fa_complement(fa2);
2449     if (cfa2 == NULL)
2450         return NULL;
2451
2452     struct fa *result = fa_intersect(fa1, cfa2);
2453     fa_free(cfa2);
2454     return result;
2455 }
2456
2457 static int accept_to_accept(struct fa *fa) {
2458     int r;
2459     struct state *s = add_state(fa, 0);
2460     if (s == NULL)
2461         return -1;
2462
2463     F(mark_reachable(fa));
2464     list_for_each(a, fa->initial) {
2465         if (a->accept && a->reachable) {
2466             r = add_epsilon_trans(s, a);
2467             if (r < 0)
2468                 return -1;
2469         }
2470     }
2471
2472     set_initial(fa, s);
2473     fa->deterministic = fa->minimal = 0;
2474     return 0;
2475  error:
2476     return -1;
2477 }
2478
2479 struct fa *fa_overlap(struct fa *fa1, struct fa *fa2) {
2480     struct fa *fa = NULL, *eps = NULL, *result = NULL;
2481     struct state_set *map = NULL;
2482
2483     if (fa1 == NULL || fa2 == NULL)
2484         return NULL;
2485
2486     fa1 = fa_clone(fa1);
2487     fa2 = fa_clone(fa2);
2488     if (fa1 == NULL || fa2 == NULL)
2489         goto error;
2490
2491     if (determinize(fa1, NULL) < 0)
2492         goto error;
2493     if (accept_to_accept(fa1) < 0)
2494         goto error;
2495
2496     map = fa_reverse(fa2);
2497     state_set_free(map);
2498     if (determinize(fa2, NULL) < 0)
2499         goto error;
2500     if (accept_to_accept(fa2) < 0)
2501         goto error;
2502     map = fa_reverse(fa2);
2503     state_set_free(map);
2504     if (determinize(fa2, NULL) < 0)
2505         goto error;
2506
2507     fa = fa_intersect(fa1, fa2);
2508     if (fa == NULL)
2509         goto error;
2510
2511     eps = fa_make_epsilon();
2512     if (eps == NULL)
2513         goto error;
2514
2515     result = fa_minus(fa, eps);
2516     if (result == NULL)
2517         goto error;
2518
2519  error:
2520     fa_free(fa1);
2521     fa_free(fa2);
2522     fa_free(fa);
2523     fa_free(eps);
2524     return result;
2525 }
2526
2527 int fa_equals(struct fa *fa1, struct fa *fa2) {
2528     if (fa1 == NULL || fa2 == NULL)
2529         return -1;
2530
2531     /* fa_contains(fa1, fa2) && fa_contains(fa2, fa1) with error checking */
2532     int c1 = fa_contains(fa1, fa2);
2533     if (c1 < 0)
2534         return -1;
2535     if (c1 == 0)
2536         return 0;
2537     return fa_contains(fa2, fa1);
2538 }
2539
2540 static unsigned int chr_score(char c) {
2541     if (isalpha(c)) {
2542         return 2;
2543     } else if (isalnum(c)) {
2544         return 3;
2545     } else if (isprint(c)) {
2546         return 7;
2547     } else if (c == '\0') {
2548         return 10000;
2549     } else {
2550         return 100;
2551     }
2552 }
2553
2554 static unsigned int str_score(const struct re_str *str) {
2555     unsigned int score = 0;
2556     for (int i=0; i < str->len; i++) {
2557         score += chr_score(str->rx[i]);
2558     }
2559     return score;
2560 }
2561
2562 /* See if we get a better string for DST by appending C to SRC. If DST is
2563  * NULL or empty, always use SRC + C
2564  */
2565 static struct re_str *string_extend(struct re_str *dst,
2566                                     const struct re_str *src,
2567                                     char c) {
2568     if (dst == NULL
2569         || dst->len == 0
2570         || str_score(src) + chr_score(c) < str_score(dst)) {
2571         int slen = src->len;
2572         if (dst == NULL)
2573             dst = make_re_str(NULL);
2574         if (dst == NULL)
2575             return NULL;
2576         if (REALLOC_N(dst->rx, slen+2) < 0) {
2577             free(dst);
2578             return NULL;
2579         }
2580         memcpy(dst->rx, src->rx, slen);
2581         dst->rx[slen] = c;
2582         dst->rx[slen + 1] = '\0';
2583         dst->len = slen + 1;
2584     }
2585     return dst;
2586 }
2587
2588 static char pick_char(struct trans *t) {
2589     for (int c = t->min; c <= t->max; c++)
2590         if (isalpha(c)) return c;
2591     for (int c = t->min; c <= t->max; c++)
2592         if (isalnum(c)) return c;
2593     for (int c = t->min; c <= t->max; c++)
2594         if (isprint(c)) return c;
2595     return t->max;
2596 }
2597
2598 /* Generate an example string for FA. Traverse all transitions and record
2599  * at each turn the "best" word found for that state.
2600  */
2601 int fa_example(struct fa *fa, char **example, size_t *example_len) {
2602     struct re_str *word = NULL;
2603     struct state_set *path = NULL, *worklist = NULL;
2604     struct re_str *str = NULL;
2605
2606     *example = NULL;
2607     *example_len = 0;
2608
2609     /* Sort to avoid any ambiguity because of reordering of transitions */
2610     sort_transition_intervals(fa);
2611
2612     /* Map from state to string */
2613     path = state_set_init(-1, S_DATA|S_SORTED);
2614     str = make_re_str("");
2615     if (path == NULL || str == NULL)
2616         goto error;
2617     F(state_set_push_data(path, fa->initial, str));
2618     str = NULL;
2619
2620     /* List of states still to visit */
2621     worklist = state_set_init(-1, S_NONE);
2622     if (worklist == NULL)
2623         goto error;
2624     F(state_set_push(worklist, fa->initial));
2625
2626     while (worklist->used) {
2627         struct state *s = state_set_pop(worklist);
2628         struct re_str *ps = state_set_find_data(path, s);
2629         for_each_trans(t, s) {
2630             char c = pick_char(t);
2631             int toind = state_set_index(path, t->to);
2632             if (toind == -1) {
2633                 struct re_str *w = string_extend(NULL, ps, c);
2634                 E(w == NULL);
2635                 F(state_set_push(worklist, t->to));
2636                 F(state_set_push_data(path, t->to, w));
2637             } else {
2638                 path->data[toind] = string_extend(path->data[toind], ps, c);
2639             }
2640         }
2641     }
2642
2643     for (int i=0; i < path->used; i++) {
2644         struct state *p = path->states[i];
2645         struct re_str *ps = path->data[i];
2646         if (p->accept &&
2647             (word == NULL || word->len == 0
2648              || (ps->len > 0 && str_score(word) > str_score(ps)))) {
2649             free_re_str(word);
2650             word = ps;
2651         } else {
2652             free_re_str(ps);
2653         }
2654     }
2655     state_set_free(path);
2656     state_set_free(worklist);
2657     if (word != NULL) {
2658         *example_len = word->len;
2659         *example = word->rx;
2660         free(word);
2661     }
2662     return 0;
2663  error:
2664     state_set_free(path);
2665     state_set_free(worklist);
2666     free_re_str(word);
2667     free_re_str(str);
2668     return -1;
2669 }
2670
2671 struct enum_intl {
2672     int       limit;
2673     int       nwords;
2674     char    **words;
2675     char     *buf;
2676     size_t    bsize;
2677 };
2678
2679 static int fa_enumerate_intl(struct state *s, struct enum_intl *ei, int pos) {
2680     int result = -1;
2681
2682     if (ei->bsize <= pos + 1) {
2683         ei->bsize *= 2;
2684         F(REALLOC_N(ei->buf, ei->bsize));
2685     }
2686
2687     ei->buf[pos] = '\0';
2688     for_each_trans(t, s) {
2689         if (t->to->visited)
2690             return -2;
2691         t->to->visited = 1;
2692         for (int i=t->min; i <= t->max; i++) {
2693             ei->buf[pos] = i;
2694             if (t->to->accept) {
2695                 if (ei->nwords >= ei->limit)
2696                     return -2;
2697                 ei->words[ei->nwords] = strdup(ei->buf);
2698                 E(ei->words[ei->nwords] == NULL);
2699                 ei->nwords += 1;
2700             }
2701             result = fa_enumerate_intl(t->to, ei, pos+1);
2702             E(result < 0);
2703         }
2704         t->to->visited = 0;
2705     }
2706     ei->buf[pos] = '\0';
2707     result = 0;
2708  error:
2709     return result;
2710 }
2711
2712 int fa_enumerate(struct fa *fa, int limit, char ***words) {
2713     struct enum_intl ei;
2714     int result = -1;
2715
2716     *words = NULL;
2717     MEMZERO(&ei, 1);
2718     ei.bsize = 8;                    /* Arbitrary initial size */
2719     ei.limit = limit;
2720     F(ALLOC_N(ei.words, limit));
2721     F(ALLOC_N(ei.buf, ei.bsize));
2722
2723     /* We use the visited bit to track which states we already visited
2724      * during the construction of a word to detect loops */
2725     list_for_each(s, fa->initial)
2726         s->visited = 0;
2727     fa->initial->visited = 1;
2728     if (fa->initial->accept) {
2729         if (ei.nwords >= limit)
2730             return -2;
2731         ei.words[0] = strdup("");
2732         E(ei.words[0] == NULL);
2733         ei.nwords = 1;
2734     }
2735     result = fa_enumerate_intl(fa->initial, &ei, 0);
2736     E(result < 0);
2737
2738     result = ei.nwords;
2739     *words = ei.words;
2740     ei.words = NULL;
2741  done:
2742     free(ei.buf);
2743     return result;
2744
2745  error:
2746     for (int i=0; i < ei.nwords; i++)
2747         free(ei.words[i]);
2748     free(ei.words);
2749     goto done;
2750 }
2751
2752 /* Expand the automaton FA by replacing every transition s(c) -> p from
2753  * state s to p on character c by two transitions s(X) -> r, r(c) -> p via
2754  * a new state r.
2755  * If ADD_MARKER is true, also add for each original state s a new a loop
2756  * s(Y) -> q and q(X) -> s through a new state q.
2757  *
2758  * The end result is that an automaton accepting "a|ab" is turned into one
2759  * accepting "Xa|XaXb" if add_marker is false and "(YX)*Xa|(YX)*Xa(YX)*Xb"
2760  * when add_marker is true.
2761  *
2762  * The returned automaton is a copy of FA, FA is not modified.
2763  */
2764 static struct fa *expand_alphabet(struct fa *fa, int add_marker,
2765                                   char X, char Y) {
2766     int ret;
2767
2768     fa = fa_clone(fa);
2769     if (fa == NULL)
2770         return NULL;
2771
2772     F(mark_reachable(fa));
2773     list_for_each(p, fa->initial) {
2774         if (! p->reachable)
2775             continue;
2776
2777         struct state *r = add_state(fa, 0);
2778         if (r == NULL)
2779             goto error;
2780         r->trans = p->trans;
2781         r->tused = p->tused;
2782         r->tsize = p->tsize;
2783         p->trans = NULL;
2784         p->tused = p->tsize = 0;
2785         ret = add_new_trans(p, r, X, X);
2786         if (ret < 0)
2787             goto error;
2788         if (add_marker) {
2789             struct state *q = add_state(fa, 0);
2790             ret = add_new_trans(p, q, Y, Y);
2791             if (ret < 0)
2792                 goto error;
2793             ret = add_new_trans(q, p, X, X);
2794             if (ret < 0)
2795                 goto error;
2796         }
2797     }
2798     return fa;
2799  error:
2800     fa_free(fa);
2801     return NULL;
2802 }
2803
2804 static bitset *alphabet(struct fa *fa) {
2805     bitset *bs = bitset_init(UCHAR_NUM);
2806
2807     if (bs == NULL)
2808         return NULL;
2809
2810     list_for_each(s, fa->initial) {
2811         for (int i=0; i < s->tused; i++) {
2812             for (uint c = s->trans[i].min; c <= s->trans[i].max; c++)
2813                 bitset_set(bs, c);
2814         }
2815     }
2816     return bs;
2817 }
2818
2819 static bitset *last_chars(struct fa *fa) {
2820     bitset *bs = bitset_init(UCHAR_NUM);
2821
2822     if (bs == NULL)
2823         return NULL;
2824
2825     list_for_each(s, fa->initial) {
2826         for (int i=0; i < s->tused; i++) {
2827             if (s->trans[i].to->accept) {
2828                 for (uint c = s->trans[i].min; c <= s->trans[i].max; c++)
2829                     bitset_set(bs, c);
2830             }
2831         }
2832     }
2833     return bs;
2834 }
2835
2836 static bitset *first_chars(struct fa *fa) {
2837     bitset *bs = bitset_init(UCHAR_NUM);
2838     struct state *s = fa->initial;
2839
2840     if (bs == NULL)
2841         return NULL;
2842
2843     for (int i=0; i < s->tused; i++) {
2844         for (uint c = s->trans[i].min; c <= s->trans[i].max; c++)
2845             bitset_set(bs, c);
2846     }
2847     return bs;
2848 }
2849
2850 /* Return 1 if F1 and F2 are known to be unambiguously concatenable
2851  * according to simple heuristics. Return 0 if they need to be checked
2852  * further to decide ambiguity
2853  * Return -1 if an allocation fails
2854  */
2855 static int is_splittable(struct fa *fa1, struct fa *fa2) {
2856     bitset *alpha1 = NULL;
2857     bitset *alpha2 = NULL;
2858     bitset *last1 = NULL;
2859     bitset *first2 = NULL;
2860     bool result = -1;
2861
2862     alpha2 = alphabet(fa2);
2863     last1 = last_chars(fa1);
2864     if (alpha2 == NULL || last1 == NULL)
2865         goto done;
2866     if (bitset_disjoint(last1, alpha2, UCHAR_NUM)) {
2867         result = 1;
2868         goto done;
2869     }
2870
2871     alpha1 = alphabet(fa1);
2872     first2 = first_chars(fa2);
2873     if (alpha1 == NULL || first2 == NULL)
2874         goto done;
2875     if (bitset_disjoint(first2, alpha1, UCHAR_NUM)) {
2876         result = 1;
2877         goto done;
2878     }
2879     result = 0;
2880  done:
2881     bitset_free(alpha1);
2882     bitset_free(alpha2);
2883     bitset_free(last1);
2884     bitset_free(first2);
2885     return result;
2886 }
2887
2888 /* This algorithm is due to Anders Moeller, and can be found in class
2889  * AutomatonOperations in dk.brics.grammar
2890  */
2891 int fa_ambig_example(struct fa *fa1, struct fa *fa2,
2892                      char **upv, size_t *upv_len,
2893                      char **pv, char **v) {
2894     static const char X = '\001';
2895     static const char Y = '\002';
2896     char *result = NULL, *s = NULL;
2897     size_t result_len = 0;
2898     int ret = -1, r;
2899     struct fa *mp = NULL, *ms = NULL, *sp = NULL, *ss = NULL, *amb = NULL;
2900     struct fa *a1f = NULL, *a1t = NULL, *a2f = NULL, *a2t = NULL;
2901     struct fa *b1 = NULL, *b2 = NULL;
2902
2903     *upv = NULL;
2904     *upv_len = 0;
2905     if (pv != NULL)
2906         *pv = NULL;
2907     if (v != NULL)
2908         *v = NULL;
2909
2910     r = is_splittable(fa1, fa2);
2911     if (r < 0)
2912         goto error;
2913     if (r == 1)
2914         return 0;
2915
2916 #define Xs "\001"
2917 #define Ys "\002"
2918 #define MPs Ys Xs "(" Xs "(.|\n))+"
2919 #define MSs Ys Xs "(" Xs "(.|\n))*"
2920 #define SPs "(" Xs "(.|\n))+" Ys Xs
2921 #define SSs "(" Xs "(.|\n))*" Ys Xs
2922     /* These could become static constants */
2923     r = fa_compile( MPs, strlen(MPs), &mp);
2924     if (r != REG_NOERROR)
2925         goto error;
2926     r = fa_compile( MSs, strlen(MSs), &ms);
2927     if (r != REG_NOERROR)
2928         goto error;
2929     r = fa_compile( SPs, strlen(SPs), &sp);
2930     if (r != REG_NOERROR)
2931         goto error;
2932     r = fa_compile( SSs, strlen(SSs), &ss);
2933     if (r != REG_NOERROR)
2934         goto error;
2935 #undef SSs
2936 #undef SPs
2937 #undef MSs
2938 #undef MPs
2939 #undef Xs
2940 #undef Ys
2941
2942     a1f = expand_alphabet(fa1, 0, X, Y);
2943     a1t = expand_alphabet(fa1, 1, X, Y);
2944     a2f = expand_alphabet(fa2, 0, X, Y);
2945     a2t = expand_alphabet(fa2, 1, X, Y);
2946     if (a1f == NULL || a1t == NULL || a2f == NULL || a2t == NULL)
2947         goto error;
2948
2949     /* Compute b1 = ((a1f . mp) & a1t) . ms */
2950     if (concat_in_place(a1f, &mp) < 0)
2951         goto error;
2952     b1 = fa_intersect(a1f, a1t);
2953     if (b1 == NULL)
2954         goto error;
2955     if (concat_in_place(b1, &ms) < 0)
2956         goto error;
2957
2958     /* Compute b2 = ss . ((sp . a2f) & a2t) */
2959     if (concat_in_place(sp, &a2f) < 0)
2960         goto error;
2961     b2 = fa_intersect(sp, a2t);
2962     if (b2 == NULL)
2963         goto error;
2964     if (concat_in_place(ss, &b2) < 0)
2965         goto error;
2966     b2 = ss;
2967     ss = NULL;
2968
2969     /* The automaton we are really interested in */
2970     amb = fa_intersect(b1, b2);
2971     if (amb == NULL)
2972         goto error;
2973
2974     size_t s_len = 0;
2975     r = fa_example(amb, &s, &s_len);
2976     if (r < 0)
2977         goto error;
2978
2979     if (s != NULL) {
2980         char *t;
2981         result_len = (s_len-1)/2 - 1;
2982         F(ALLOC_N(result, result_len + 1));
2983         t = result;
2984         int i = 0;
2985         for (i=0; s[2*i] == X; i++) {
2986             assert((t - result) < result_len);
2987             *t++ = s[2*i + 1];
2988         }
2989         if (pv != NULL)
2990             *pv = t;
2991         i += 1;
2992
2993         for ( ;s[2*i] == X; i++) {
2994             assert((t - result) < result_len);
2995             *t++ = s[2*i + 1];
2996         }
2997         if (v != NULL)
2998             *v = t;
2999         i += 1;
3000
3001         for (; 2*i+1 < s_len; i++) {
3002             assert((t - result) < result_len);
3003             *t++ = s[2*i + 1];
3004         }
3005     }
3006     ret = 0;
3007
3008  done:
3009     /* Clean up intermediate automata */
3010     fa_free(mp);
3011     fa_free(ms);
3012     fa_free(ss);
3013     fa_free(sp);
3014     fa_free(a1f);
3015     fa_free(a1t);
3016     fa_free(a2f);
3017     fa_free(a2t);
3018     fa_free(b1);
3019     fa_free(b2);
3020     fa_free(amb);
3021
3022     FREE(s);
3023     *upv = result;
3024     if (result != NULL)
3025         *upv_len = result_len;
3026     return ret;
3027  error:
3028     FREE(result);
3029     ret = -1;
3030     goto done;
3031 }
3032
3033 /*
3034  * Construct an fa from a regular expression
3035  */
3036 static struct fa *fa_from_re(struct re *re) {
3037     struct fa *result = NULL;
3038
3039     switch(re->type) {
3040     case UNION:
3041         {
3042             result = fa_from_re(re->exp1);
3043             if (result == NULL)
3044                 goto error;
3045             struct fa *fa2 = fa_from_re(re->exp2);
3046             if (fa2 == NULL)
3047                 goto error;
3048             if (union_in_place(result, &fa2) < 0)
3049                 goto error;
3050         }
3051         break;
3052     case CONCAT:
3053         {
3054             result = fa_from_re(re->exp1);
3055             if (result == NULL)
3056                 goto error;
3057             struct fa *fa2 = fa_from_re(re->exp2);
3058             if (fa2 == NULL)
3059                 goto error;
3060             if (concat_in_place(result, &fa2) < 0)
3061                 goto error;
3062         }
3063         break;
3064     case CSET:
3065         result = fa_make_char_set(re->cset, re->negate);
3066         break;
3067     case ITER:
3068         {
3069             struct fa *fa = fa_from_re(re->exp);
3070             if (fa == NULL)
3071                 goto error;
3072             result = fa_iter(fa, re->min, re->max);
3073             fa_free(fa);
3074         }
3075         break;
3076     case EPSILON:
3077         result = fa_make_epsilon();
3078         break;
3079     case CHAR:
3080         result = fa_make_char(re->c);
3081         break;
3082     default:
3083         assert(0);
3084         break;
3085     }
3086     return result;
3087  error:
3088     fa_free(result);
3089     return NULL;
3090 }
3091
3092 static void free_re(struct re *re) {
3093     if (re == NULL)
3094         return;
3095     assert(re->ref == 0);
3096
3097     if (re->type == UNION || re->type == CONCAT) {
3098         re_unref(re->exp1);
3099         re_unref(re->exp2);
3100     } else if (re->type == ITER) {
3101         re_unref(re->exp);
3102     } else if (re->type == CSET) {
3103         bitset_free(re->cset);
3104     }
3105     free(re);
3106 }
3107
3108 int fa_compile(const char *regexp, size_t size, struct fa **fa) {
3109     struct re *re = NULL;
3110     struct re_parse parse;
3111
3112     *fa = NULL;
3113
3114     parse.rx = regexp;
3115     parse.rend = regexp + size;
3116     parse.error = REG_NOERROR;
3117
3118     re = parse_regexp(&parse);
3119     if (re == NULL)
3120         return parse.error;
3121
3122     *fa = fa_from_re(re);
3123     re_unref(re);
3124
3125     if (*fa == NULL || collect(*fa) < 0)
3126         parse.error = REG_ESPACE;
3127     return parse.error;
3128 }
3129
3130 /* We represent a case-insensitive FA by using only transitions on
3131  * lower-case letters.
3132  */
3133 int fa_nocase(struct fa *fa) {
3134     if (fa == NULL || fa->nocase)
3135         return 0;
3136
3137     fa->nocase = 1;
3138     list_for_each(s, fa->initial) {
3139         int tused = s->tused;
3140         /* For every transition on characters in [A-Z] add a corresponding
3141          * transition on [a-z]; remove any portion covering [A-Z] */
3142         for (int i=0; i < tused; i++) {
3143             struct trans *t = s->trans + i;
3144             int lc_min = t->min < 'A' ? 'a' : tolower(t->min);
3145             int lc_max = t->max > 'Z' ? 'z' : tolower(t->max);
3146
3147             if (t->min > 'Z' || t->max < 'A')
3148                 continue;
3149             if (t->min >= 'A' && t->max <= 'Z') {
3150                 t->min = tolower(t->min);
3151                 t->max = tolower(t->max);
3152             } else if (t->max <= 'Z') {
3153                 /* t->min < 'A' */
3154                 t->max = 'A' - 1;
3155                 F(add_new_trans(s, t->to, lc_min, lc_max));
3156             } else if (t->min >= 'A') {
3157                 /* t->max > 'Z' */
3158                 t->min = 'Z' + 1;
3159                 F(add_new_trans(s, t->to, lc_min, lc_max));
3160             } else {
3161                 /* t->min < 'A' && t->max > 'Z' */
3162                 F(add_new_trans(s, t->to, 'Z' + 1, t->max));
3163                 s->trans[i].max = 'A' - 1;
3164                 F(add_new_trans(s, s->trans[i].to, lc_min, lc_max));
3165             }
3166         }
3167     }
3168     F(collect(fa));
3169     return 0;
3170  error:
3171     return -1;
3172 }
3173
3174 int fa_is_nocase(struct fa *fa) {
3175     return fa->nocase;
3176 }
3177
3178 /* If FA is case-insensitive, turn it into a case-sensitive automaton by
3179  * adding transitions on upper-case letters for each existing transition on
3180  * lower-case letters */
3181 static int case_expand(struct fa *fa) {
3182     if (! fa->nocase)
3183         return 0;
3184
3185     fa->nocase = 0;
3186     list_for_each(s, fa->initial) {
3187         int tused = s->tused;
3188         /* For every transition on characters in [a-z] add a corresponding
3189          * transition on [A-Z] */
3190         for (int i=0; i < tused; i++) {
3191             struct trans *t = s->trans + i;
3192             int lc_min = t->min < 'a' ? 'A' : toupper(t->min);
3193             int lc_max = t->max > 'z' ? 'Z' : toupper(t->max);
3194
3195             if (t->min > 'z' || t->max < 'a')
3196                 continue;
3197             F(add_new_trans(s, t->to, lc_min, lc_max));
3198         }
3199     }
3200     F(collect(fa));
3201     return 0;
3202  error:
3203     return -1;
3204 }
3205
3206 /*
3207  * Regular expression parser
3208  */
3209
3210 static struct re *make_re(enum re_type type) {
3211     struct re *re;
3212     if (make_ref(re) == 0)
3213         re->type = type;
3214     return re;
3215 }
3216
3217 static struct re *make_re_rep(struct re *exp, int min, int max) {
3218     struct re *re = make_re(ITER);
3219     if (re) {
3220         re->exp = exp;
3221         re->min = min;
3222         re->max = max;
3223     } else {
3224         re_unref(exp);
3225     }
3226     return re;
3227 }
3228
3229 static struct re *make_re_binop(enum re_type type, struct re *exp1,
3230                                 struct re *exp2) {
3231     struct re *re = make_re(type);
3232     if (re) {
3233         re->exp1 = exp1;
3234         re->exp2 = exp2;
3235     } else {
3236         re_unref(exp1);
3237         re_unref(exp2);
3238     }
3239     return re;
3240 }
3241
3242 static struct re *make_re_char(uchar c) {
3243     struct re *re = make_re(CHAR);
3244     if (re)
3245         re->c = c;
3246     return re;
3247 }
3248
3249 static struct re *make_re_char_set(bool negate, bool no_ranges) {
3250     struct re *re = make_re(CSET);
3251     if (re) {
3252         re->negate = negate;
3253         re->no_ranges = no_ranges;
3254         re->cset = bitset_init(UCHAR_NUM);
3255         if (re->cset == NULL)
3256             re_unref(re);
3257     }
3258     return re;
3259 }
3260
3261 static bool more(struct re_parse *parse) {
3262     return parse->rx < parse->rend;
3263 }
3264
3265 static bool match(struct re_parse *parse, char m) {
3266     if (!more(parse))
3267         return false;
3268     if (*parse->rx == m) {
3269         parse->rx += 1;
3270         return true;
3271     }
3272     return false;
3273 }
3274
3275 static bool peek(struct re_parse *parse, const char *chars) {
3276     return *parse->rx != '\0' && strchr(chars, *parse->rx) != NULL;
3277 }
3278
3279 static bool next(struct re_parse *parse, char *c) {
3280     if (!more(parse))
3281         return false;
3282     *c = *parse->rx;
3283     parse->rx += 1;
3284     return true;
3285 }
3286
3287 static bool parse_char(struct re_parse *parse, int quoted, char *c) {
3288     if (!more(parse))
3289         return false;
3290     if (quoted && *parse->rx == '\\') {
3291         parse->rx += 1;
3292         return next(parse, c);
3293     } else {
3294         return next(parse, c);
3295     }
3296 }
3297
3298 static void add_re_char(struct re *re, uchar from, uchar to) {
3299     assert(re->type == CSET);
3300     for (unsigned int c = from; c <= to; c++)
3301         bitset_set(re->cset, c);
3302 }
3303
3304 static void parse_char_class(struct re_parse *parse, struct re *re) {
3305     if (! more(parse)) {
3306         parse->error = REG_EBRACK;
3307         goto error;
3308     }
3309     char from, to;
3310     parse_char(parse, 0, &from);
3311     to = from;
3312     if (match(parse, '-')) {
3313         if (! more(parse)) {
3314             parse->error = REG_EBRACK;
3315             goto error;
3316         }
3317         if (peek(parse, "]")) {
3318             if (from > to) {
3319                 parse->error = REG_ERANGE;
3320                 goto error;
3321             }
3322             add_re_char(re, from, to);
3323             add_re_char(re, '-', '-');
3324             return;
3325         } else if (!parse_char(parse, 0, &to)) {
3326             parse->error = REG_ERANGE;
3327             goto error;
3328         }
3329     }
3330     if (from > to) {
3331         parse->error = REG_ERANGE;
3332         goto error;
3333     }
3334     add_re_char(re, from, to);
3335  error:
3336     return;
3337 }
3338
3339 static struct re *parse_simple_exp(struct re_parse *parse) {
3340     struct re *re = NULL;
3341
3342     if (match(parse, '[')) {
3343         bool negate = match(parse, '^');
3344         re = make_re_char_set(negate, parse->no_ranges);
3345         if (re == NULL) {
3346             parse->error = REG_ESPACE;
3347             goto error;
3348         }
3349         parse_char_class(parse, re);
3350         if (parse->error != REG_NOERROR)
3351             goto error;
3352         while (more(parse) && ! peek(parse, "]")) {
3353             parse_char_class(parse, re);
3354             if (parse->error != REG_NOERROR)
3355                 goto error;
3356         }
3357         if (! match(parse, ']')) {
3358             parse->error = REG_EBRACK;
3359             goto error;
3360         }
3361     } else if (match(parse, '(')) {
3362         if (match(parse, ')')) {
3363             re = make_re(EPSILON);
3364             if (re == NULL) {
3365                 parse->error = REG_ESPACE;
3366                 goto error;
3367             }
3368         } else {
3369             re = parse_regexp(parse);
3370             if (re == NULL)
3371                 goto error;
3372             if (! match(parse, ')')) {
3373                 parse->error = REG_EPAREN;
3374                 goto error;
3375             }
3376         }
3377     } else if (match(parse, '.')) {
3378         re = make_re_char_set(1, parse->no_ranges);
3379         if (re == NULL) {
3380             parse->error = REG_ESPACE;
3381             goto error;
3382         }
3383         add_re_char(re, '\n', '\n');
3384     } else if (more(parse)) {
3385         char c;
3386         if (!parse_char(parse, 1, &c)) {
3387             parse->error = REG_EESCAPE;
3388             goto error;
3389         }
3390         re = make_re_char(c);
3391         if (re == NULL) {
3392             parse->error = REG_ESPACE;
3393             goto error;
3394         }
3395     } else {
3396         re = make_re(EPSILON);
3397         if (re == NULL) {
3398             parse->error = REG_ESPACE;
3399             goto error;
3400         }
3401     }
3402     return re;
3403  error:
3404     re_unref(re);
3405     return NULL;
3406 }
3407
3408 static int parse_int(struct re_parse *parse) {
3409     const char *lim;
3410     char *end;
3411     size_t used;
3412     long l;
3413
3414     /* We need to be careful that strtoul will never access
3415      * memory beyond parse->rend
3416      */
3417     for (lim = parse->rx; lim < parse->rend && *lim >= '0' && *lim <= '9';
3418          lim++);
3419     if (lim < parse->rend) {
3420         l = strtoul(parse->rx, &end, 10);
3421         used = end - parse->rx;
3422     } else {
3423         char *s = strndup(parse->rx, parse->rend - parse->rx);
3424         if (s == NULL) {
3425             parse->error = REG_ESPACE;
3426             return -1;
3427         }
3428         l = strtoul(s, &end, 10);
3429         used = end - s;
3430         free(s);
3431     }
3432
3433     if (used == 0)
3434         return -1;
3435     parse->rx += used;
3436     if ((l<0) || (l > INT_MAX)) {
3437         parse->error = REG_BADBR;
3438         return -1;
3439     }
3440     return (int) l;
3441 }
3442
3443 static struct re *parse_repeated_exp(struct re_parse *parse) {
3444     struct re *re = parse_simple_exp(parse);
3445     if (re == NULL)
3446         goto error;
3447     if (match(parse, '?')) {
3448         re = make_re_rep(re, 0, 1);
3449     } else if (match(parse, '*')) {
3450         re = make_re_rep(re, 0, -1);
3451     } else if (match(parse, '+')) {
3452         re = make_re_rep(re, 1, -1);
3453     } else if (match(parse, '{')) {
3454         int min, max;
3455         min = parse_int(parse);
3456         if (min == -1)
3457             goto error;
3458         if (match(parse, ',')) {
3459             max = parse_int(parse);
3460             if (max == -1)
3461                 max = -1;      /* If it's not an int, it means 'unbounded' */
3462             if (! match(parse, '}')) {
3463                 parse->error = REG_EBRACE;
3464                 goto error;
3465             }
3466         } else if (match(parse, '}')) {
3467             max = min;
3468         } else {
3469             parse->error = REG_EBRACE;
3470             goto error;
3471         }
3472         if (min > max && max != -1) {
3473             parse->error = REG_BADBR;
3474             goto error;
3475         }
3476         re = make_re_rep(re, min, max);
3477     }
3478     if (re == NULL)
3479         parse->error = REG_ESPACE;
3480     return re;
3481  error:
3482     re_unref(re);
3483     return NULL;
3484 }
3485
3486 static struct re *parse_concat_exp(struct re_parse *parse) {
3487     struct re *re = parse_repeated_exp(parse);
3488     if (re == NULL)
3489         goto error;
3490
3491     if (more(parse) && ! peek(parse, ")|")) {
3492         struct re *re2 = parse_concat_exp(parse);
3493         if (re2 == NULL)
3494             goto error;
3495         re = make_re_binop(CONCAT, re, re2);
3496         if (re == NULL) {
3497             parse->error = REG_ESPACE;
3498             goto error;
3499         }
3500     }
3501     return re;
3502
3503  error:
3504     re_unref(re);
3505     return NULL;
3506 }
3507
3508 static struct re *parse_regexp(struct re_parse *parse) {
3509     struct re *re = NULL;
3510
3511     /* Something like (|r) */
3512     if (peek(parse, "|"))
3513         re = make_re(EPSILON);
3514     else
3515         re = parse_concat_exp(parse);
3516     if (re == NULL)
3517         goto error;
3518
3519     if (match(parse, '|')) {
3520         struct re *re2 = NULL;
3521         /* Something like (r|) */
3522         if (peek(parse, ")"))
3523             re2 = make_re(EPSILON);
3524         else
3525             re2 = parse_regexp(parse);
3526         if (re2 == NULL)
3527             goto error;
3528
3529         re = make_re_binop(UNION, re, re2);
3530         if (re == NULL) {
3531             parse->error = REG_ESPACE;
3532             goto error;
3533         }
3534     }
3535     return re;
3536
3537  error:
3538     re_unref(re);
3539     return NULL;
3540 }
3541
3542 /*
3543  * Convert a STRUCT RE to a string. Code is complicated by the fact that
3544  * we try to be clever and avoid unneeded parens and concatenation with
3545  * epsilon etc.
3546  */
3547 static int re_as_string(const struct re *re, struct re_str *str);
3548
3549 static int re_binop_count(enum re_type type, const struct re *re) {
3550     assert(type == CONCAT || type == UNION);
3551     if (re->type == type) {
3552         return re_binop_count(type, re->exp1) + re_binop_count(type, re->exp2);
3553     } else {
3554         return 1;
3555     }
3556 }
3557
3558 static int re_binop_store(enum re_type type, const struct re *re,
3559                           const struct re **list) {
3560     int pos = 0;
3561     if (type == re->type) {
3562         pos = re_binop_store(type, re->exp1, list);
3563         pos += re_binop_store(type, re->exp2, list + pos);
3564     } else {
3565         list[0] = re;
3566         pos = 1;
3567     }
3568     return pos;
3569 }
3570
3571 static int re_union_as_string(const struct re *re, struct re_str *str) {
3572     assert(re->type == UNION);
3573
3574     int result = -1;
3575     const struct re **res = NULL;
3576     struct re_str *strings = NULL;
3577     int nre = 0, r;
3578
3579     nre = re_binop_count(re->type, re);
3580     r = ALLOC_N(res, nre);
3581     if (r < 0)
3582         goto done;
3583
3584     re_binop_store(re->type, re, res);
3585
3586     r = ALLOC_N(strings, nre);
3587     if (r < 0)
3588         goto error;
3589
3590     str->len = 0;
3591     for (int i=0; i < nre; i++) {
3592         if (re_as_string(res[i], strings + i) < 0)
3593             goto error;
3594         str->len += strings[i].len;
3595     }
3596     str->len += nre-1;
3597
3598     r = re_str_alloc(str);
3599     if (r < 0)
3600         goto error;
3601
3602     char *p = str->rx;
3603     for (int i=0; i < nre; i++) {
3604         if (i>0)
3605             *p++ = '|';
3606         memcpy(p, strings[i].rx, strings[i].len);
3607         p += strings[i].len;
3608     }
3609
3610     result = 0;
3611  done:
3612     free(res);
3613     if (strings != NULL) {
3614         for (int i=0; i < nre; i++)
3615             release_re_str(strings + i);
3616     }
3617     free(strings);
3618     return result;
3619  error:
3620     release_re_str(str);
3621     result = -1;
3622     goto done;
3623 }
3624
3625 ATTRIBUTE_PURE
3626 static int re_needs_parens_in_concat(const struct re *re) {
3627     return (re->type != CHAR && re->type != CSET && re->type != ITER);
3628 }
3629
3630 static int re_concat_as_string(const struct re *re, struct re_str *str) {
3631     assert(re->type == CONCAT);
3632
3633     const struct re **res = NULL;
3634     struct re_str *strings = NULL;
3635     int nre = 0, r;
3636     int result = -1;
3637
3638     nre = re_binop_count(re->type, re);
3639     r = ALLOC_N(res, nre);
3640     if (r < 0)
3641         goto error;
3642     re_binop_store(re->type, re, res);
3643
3644     r = ALLOC_N(strings, nre);
3645     if (r < 0)
3646         goto error;
3647
3648     str->len = 0;
3649     for (int i=0; i < nre; i++) {
3650         if (res[i]->type == EPSILON)
3651             continue;
3652         if (re_as_string(res[i], strings + i) < 0)
3653             goto error;
3654         str->len += strings[i].len;
3655         if (re_needs_parens_in_concat(res[i]))
3656             str->len += 2;
3657     }
3658
3659     r = re_str_alloc(str);
3660     if (r < 0)
3661         goto error;
3662
3663     char *p = str->rx;
3664     for (int i=0; i < nre; i++) {
3665         if (res[i]->type == EPSILON)
3666             continue;
3667         if (re_needs_parens_in_concat(res[i]))
3668             *p++ = '(';
3669         p = memcpy(p, strings[i].rx, strings[i].len);
3670         p += strings[i].len;
3671         if (re_needs_parens_in_concat(res[i]))
3672             *p++ = ')';
3673     }
3674
3675     result = 0;
3676  done:
3677     free(res);
3678     if (strings != NULL) {
3679         for (int i=0; i < nre; i++)
3680             release_re_str(strings + i);
3681     }
3682     free(strings);
3683     return result;
3684  error:
3685     release_re_str(str);
3686     result = -1;
3687     goto done;
3688 }
3689
3690 static bool cset_contains(const struct re *cset, int c) {
3691     return bitset_get(cset->cset, c) != cset->negate;
3692 }
3693
3694 static int re_cset_as_string(const struct re *re, struct re_str *str) {
3695     const uchar rbrack = ']';
3696     const uchar dash = '-';
3697     const uchar nul = '\0';
3698
3699     static const char *const empty_set = "[]";
3700     static const char *const total_set = "(.|\n)";
3701     static const char *const not_newline = ".";
3702
3703     char *s;
3704     int from, to, negate;
3705     size_t len;
3706     int incl_rbrack, incl_dash;
3707     int r;
3708
3709     str->len = strlen(empty_set);
3710
3711     /* We can not include NUL explicitly in a CSET since we use ordinary
3712        NUL delimited strings to represent them. That means that we need to
3713        use negated representation if NUL is to be included (and vice versa)
3714     */
3715     negate = cset_contains(re, nul);
3716     if (negate) {
3717         for (from = UCHAR_MIN;
3718              from <= UCHAR_MAX && cset_contains(re, from);
3719              from += 1);
3720         if (from > UCHAR_MAX) {
3721             /* Special case: the set matches every character */
3722             str->rx = strdup(total_set);
3723             goto done;
3724         }
3725         if (from == '\n') {
3726             for (from += 1;
3727                  from <= UCHAR_MAX && cset_contains(re, from);
3728                  from += 1);
3729             if (from > UCHAR_MAX) {
3730                 /* Special case: the set matches everything but '\n' */
3731                 str->rx = strdup(not_newline);
3732                 goto done;
3733             }
3734         }
3735     }
3736
3737     /* See if ']' and '-' will be explicitly included in the character set
3738        (INCL_RBRACK, INCL_DASH) As we loop over the character set, we reset
3739        these flags if they are in the set, but not mentioned explicitly
3740     */
3741     incl_rbrack = cset_contains(re, rbrack) != negate;
3742     incl_dash = cset_contains(re, dash) != negate;
3743
3744     if (re->no_ranges) {
3745         for (from = UCHAR_MIN; from <= UCHAR_MAX; from++)
3746             if (cset_contains(re, from) != negate)
3747                 str->len += 1;
3748     } else {
3749         for (from = UCHAR_MIN; from <= UCHAR_MAX; from = to+1) {
3750             while (from <= UCHAR_MAX && cset_contains(re, from) == negate)
3751                 from += 1;
3752             if (from > UCHAR_MAX)
3753                 break;
3754             for (to = from;
3755                  to < UCHAR_MAX && (cset_contains(re, to+1) != negate);
3756                  to++);
3757
3758             if (to == from && (from == rbrack || from == dash))
3759                 continue;
3760             if (from == rbrack || from == dash)
3761                 from += 1;
3762             if (to == rbrack || to == dash)
3763                 to -= 1;
3764
3765             len = (to == from) ? 1 : ((to == from + 1) ? 2 : 3);
3766
3767             if (from < rbrack && rbrack < to)
3768                 incl_rbrack = 0;
3769             if (from < dash && dash < to)
3770                 incl_dash = 0;
3771             str->len += len;
3772         }
3773         str->len += incl_rbrack + incl_dash;
3774     }
3775     if (negate)
3776         str->len += 1;        /* For the ^ */
3777
3778     r = re_str_alloc(str);
3779     if (r < 0)
3780         goto error;
3781
3782     s = str->rx;
3783     *s++ = '[';
3784     if (negate)
3785         *s++ = '^';
3786     if (incl_rbrack)
3787         *s++ = rbrack;
3788
3789     if (re->no_ranges) {
3790         for (from = UCHAR_MIN; from <= UCHAR_MAX; from++) {
3791             if (from == rbrack || from == dash)
3792                 continue;
3793             if (cset_contains(re, from) != negate)
3794                 *s++ = from;
3795         }
3796     } else {
3797         for (from = UCHAR_MIN; from <= UCHAR_MAX; from = to+1) {
3798             while (from <= UCHAR_MAX && cset_contains(re, from) == negate)
3799                 from += 1;
3800             if (from > UCHAR_MAX)
3801                 break;
3802             for (to = from;
3803                  to < UCHAR_MAX && (cset_contains(re, to+1) != negate);
3804                  to++);
3805
3806             if (to == from && (from == rbrack || from == dash))
3807                 continue;
3808             if (from == rbrack || from == dash)
3809                 from += 1;
3810             if (to == rbrack || to == dash)
3811                 to -= 1;
3812
3813             if (to == from) {
3814                 *s++ = from;
3815             } else if (to == from + 1) {
3816                 *s++ = from;
3817                 *s++ = to;
3818             } else {
3819                 *s++ = from;
3820                 *s++ = '-';
3821                 *s++ = to;
3822             }
3823         }
3824     }
3825     if (incl_dash)
3826         *s++ = dash;
3827
3828     *s = ']';
3829  done:
3830     if (str->rx == NULL)
3831         goto error;
3832     str->len = strlen(str->rx);
3833     return 0;
3834  error:
3835     release_re_str(str);
3836     return -1;
3837 }
3838
3839 static int re_iter_as_string(const struct re *re, struct re_str *str) {
3840     const char *quant = NULL;
3841     char *iter = NULL;
3842     int r, result = -1;
3843
3844     if (re_as_string(re->exp, str) < 0)
3845         return -1;
3846
3847     if (re->min == 0 && re->max == -1) {
3848         quant = "*";
3849     } else if (re->min == 1 && re->max == -1) {
3850         quant = "+";
3851     } else if (re->min == 0 && re->max == 1) {
3852         quant = "?";
3853     } else if (re->max == -1) {
3854         r = asprintf(&iter, "{%d,}", re->min);
3855         if (r < 0)
3856             return -1;
3857         quant = iter;
3858     } else {
3859         r = asprintf(&iter, "{%d,%d}", re->min, re->max);
3860         if (r < 0)
3861             return -1;
3862         quant = iter;
3863     }
3864
3865     if (re->exp->type == CHAR || re->exp->type == CSET) {
3866         if (REALLOC_N(str->rx, str->len + strlen(quant) + 1) < 0)
3867             goto error;
3868         strcpy(str->rx + str->len, quant);
3869         str->len += strlen(quant);
3870     } else {
3871         /* Format '(' + str->rx ')' + quant */
3872         if (REALLOC_N(str->rx, str->len + strlen(quant) + 1 + 2) < 0)
3873             goto error;
3874         memmove(str->rx + 1, str->rx, str->len);
3875         str->rx[0] = '(';
3876         str->rx[str->len + 1] = ')';
3877         str->len += 2;
3878         strcpy(str->rx + str->len, quant);
3879         str->len += strlen(quant);
3880     }
3881
3882     result = 0;
3883  done:
3884     FREE(iter);
3885     return result;
3886  error:
3887     release_re_str(str);
3888     goto done;
3889 }
3890
3891 static int re_as_string(const struct re *re, struct re_str *str) {
3892     /* Characters that must be escaped */
3893     static const char * const special_chars = ".()[]{}*|+?\\^$";
3894     int result = 0;
3895
3896     switch(re->type) {
3897     case UNION:
3898         result = re_union_as_string(re, str);
3899         break;
3900     case CONCAT:
3901         result = re_concat_as_string(re, str);
3902         break;
3903     case CSET:
3904         result = re_cset_as_string(re, str);
3905         break;
3906     case CHAR:
3907         if (re->c == '\0' || strchr(special_chars, re->c) == NULL) {
3908             if (ALLOC_N(str->rx, 2) < 0)
3909                 goto error;
3910             str->rx[0] = re->c;
3911             str->len = 1;
3912         } else {
3913             if (ALLOC_N(str->rx, 3) < 0)
3914                 goto error;
3915             str->rx[0] = '\\';
3916             str->rx[1] = re->c;
3917             str->len = strlen(str->rx);
3918         }
3919         break;
3920     case ITER:
3921         result = re_iter_as_string(re, str);
3922         break;
3923     case EPSILON:
3924         if (ALLOC_N(str->rx, 3) < 0)
3925             goto error;
3926         strcpy(str->rx, "()");
3927         str->len = strlen(str->rx);
3928         break;
3929     default:
3930         assert(0);
3931         abort();
3932         break;
3933     }
3934     return result;
3935  error:
3936     release_re_str(str);
3937     return -1;
3938 }
3939
3940 static int convert_trans_to_re(struct state *s) {
3941     struct re *re = NULL;
3942     size_t nto = 1;
3943     struct trans *trans = NULL;
3944     int r;
3945
3946     if (s->tused == 0)
3947         return 0;
3948
3949     qsort(s->trans, s->tused, sizeof(*s->trans), trans_to_cmp);
3950     for (int i = 0; i < s->tused - 1; i++) {
3951         if (s->trans[i].to != s->trans[i+1].to)
3952             nto += 1;
3953     }
3954     r = ALLOC_N(trans, nto);
3955     if (r < 0)
3956         goto error;
3957
3958     struct state *to = s->trans[0].to;
3959     int tind = 0;
3960     for_each_trans(t, s) {
3961         if (t->to != to) {
3962             trans[tind].to = to;
3963             trans[tind].re = re;
3964             tind += 1;
3965             re = NULL;
3966             to = t->to;
3967         }
3968         if (re == NULL) {
3969             re = make_re_char_set(0, 0);
3970             if (re == NULL)
3971                 goto error;
3972         }
3973         add_re_char(re, t->min, t->max);
3974     }
3975     assert(nto == tind + 1);
3976     trans[tind].to = to;
3977     trans[tind].re = re;
3978
3979     /* Simplify CSETs with a single char to a CHAR */
3980     for (int t=0; t < nto; t++) {
3981         int cnt = 0;
3982         uchar chr = UCHAR_MIN;
3983         for (int c = 0; c < UCHAR_NUM; c++) {
3984             if (bitset_get(trans[t].re->cset, c)) {
3985                 cnt += 1;
3986                 chr = c;
3987             }
3988         }
3989         if (cnt == 1) {
3990             re_unref(trans[t].re);
3991             trans[t].re = make_re_char(chr);
3992             if (trans[t].re == NULL)
3993                 goto error;
3994         }
3995     }
3996     free_trans(s);
3997     s->trans = trans;
3998     s->tused = s->tsize = nto;
3999     return 0;
4000
4001  error:
4002     if (trans)
4003         for (int i=0; i < nto; i++)
4004             unref(trans[i].re, re);
4005     free(trans);
4006     return -1;
4007 }
4008
4009 ATTRIBUTE_RETURN_CHECK
4010 static int add_new_re_trans(struct state *s1, struct state *s2,
4011                             struct re *re) {
4012     int r;
4013     r = add_new_trans(s1, s2, 0, 0);
4014     if (r < 0)
4015         return -1;
4016     last_trans(s1)->re = re;
4017     return 0;
4018 }
4019
4020 /* Add the regular expression R1 . LOOP* . R2 to the transition
4021    from S1 to S2. */
4022 static int re_collapse_trans(struct state *s1, struct state *s2,
4023                              struct re *r1, struct re *loop, struct re *r2) {
4024     struct re *re = NULL;
4025
4026     if (loop->type != EPSILON) {
4027         loop = make_re_rep(ref(loop), 0, -1);
4028         if (loop == NULL)
4029             goto error;
4030     }
4031
4032     if (r1->type == EPSILON) {
4033         if (loop->type == EPSILON) {
4034             re = ref(r2);
4035         } else {
4036             re = make_re_binop(CONCAT, loop, ref(r2));
4037         }
4038     } else {
4039         if (loop->type == EPSILON) {
4040             if (r2->type == EPSILON) {
4041                 re = ref(r1);
4042             } else {
4043                 re = make_re_binop(CONCAT, ref(r1), ref(r2));
4044             }
4045         } else {
4046             re = make_re_binop(CONCAT, ref(r1), loop);
4047             if (re != NULL && r2->type != EPSILON) {
4048                 re = make_re_binop(CONCAT, re, ref(r2));
4049             }
4050         }
4051     }
4052     if (re == NULL)
4053         goto error;
4054
4055     struct trans *t = NULL;
4056     for (t = s1->trans; t <= last_trans(s1) && t->to != s2; t += 1);
4057     if (t > last_trans(s1)) {
4058         if (add_new_re_trans(s1, s2, re) < 0)
4059             goto error;
4060     } else {
4061         if (t->re == NULL) {
4062             t->re = re;
4063         } else {
4064             t->re = make_re_binop(UNION, re, t->re);
4065             if (t->re == NULL)
4066                 goto error;
4067         }
4068     }
4069     return 0;
4070  error:
4071     // FIXME: make sure we don't leak loop
4072     return -1;
4073 }
4074
4075 static int convert_strings(struct fa *fa) {
4076     struct state_set *worklist = state_set_init(-1, S_NONE);
4077     int result = -1;
4078
4079     E(worklist == NULL);
4080
4081     /* Abuse hash to count indegree, reachable to mark visited states */
4082     list_for_each(s, fa->initial) {
4083         s->hash = 0;
4084         s->reachable = 0;
4085     }
4086
4087     list_for_each(s, fa->initial) {
4088         for_each_trans(t, s) {
4089             t->to->hash += 1;
4090         }
4091     }
4092
4093     for (struct state *s = fa->initial;
4094          s != NULL;
4095          s = state_set_pop(worklist)) {
4096         for (int i=0; i < s->tused; i++) {
4097             struct trans *t = s->trans + i;
4098             struct state *to = t->to;
4099             while (to->hash == 1 && to->tused == 1 && ! to->accept) {
4100                 if (t->re == NULL) {
4101                     t->re = to->trans->re;
4102                     to->trans->re = NULL;
4103                 } else {
4104                     t->re = make_re_binop(CONCAT, t->re, to->trans->re);
4105                     if (t->re == NULL)
4106                         goto error;
4107                 }
4108                 t->to = to->trans->to;
4109                 to->tused = 0;
4110                 to->hash -= 1;
4111                 to = t->to;
4112                 for (int j=0; j < s->tused; j++) {
4113                     if (j != i && s->trans[j].to == to) {
4114                         /* Combine transitions i and j; remove trans j */
4115                         t->re = make_re_binop(UNION, t->re, s->trans[j].re);
4116                         if (t->re == NULL)
4117                             goto error;
4118                         memmove(s->trans + j, s->trans + j + 1,
4119                                 sizeof(s->trans[j]) * (s->tused - j - 1));
4120                         to->hash -= 1;
4121                         s->tused -= 1;
4122                         if (j < i) {
4123                             i = i - 1;
4124                             t = s->trans + i;
4125                         }
4126                     }
4127                 }
4128             }
4129
4130             if (! to->reachable) {
4131                 to->reachable = 1;
4132                 F(state_set_push(worklist, to));
4133             }
4134         }
4135     }
4136
4137     for (struct state *s = fa->initial; s->next != NULL; ) {
4138         if (s->next->hash == 0 && s->next->tused == 0) {
4139             struct state *del = s->next;
4140             s->next = del->next;
4141             free(del->trans);
4142             free(del);
4143         } else {
4144             s = s->next;
4145         }
4146     }
4147     result = 0;
4148
4149  error:
4150     state_set_free(worklist);
4151     return result;
4152 }
4153
4154 /* Convert an FA to a regular expression.
4155  * The strategy is the following:
4156  * (1) For all states S1 and S2, convert the transitions between them
4157  *     into one transition whose regexp is a CSET
4158  * (2) Add a new initial state INI and a new final state FIN to the automaton,
4159  *     a transition from INI to the old initial state of FA, and a transition
4160  *     from all accepting states of FA to FIN; the regexp on those transitions
4161  *     matches only the empty word
4162  * (3) Eliminate states S (except for INI and FIN) one by one:
4163  *     Let LOOP the regexp for the transition S -> S if it exists, epsilon
4164  *     otherwise.
4165  *     For all S1, S2 different from S with S1 -> S -> S2
4166  *       Let R1 the regexp of S1 -> S
4167  *           R2 the regexp of S -> S2
4168  *           R3 the regexp S1 -> S2 (or epsilon if no such transition)
4169  *        set the regexp on the transition S1 -> S2 to
4170  *          R1 . (LOOP)* . R2 | R3
4171  * (4) The regexp for the whole FA can now be found as the regexp of
4172  *     the transition INI -> FIN
4173  * (5) Convert that STRUCT RE to a string with RE_AS_STRING
4174  */
4175 int fa_as_regexp(struct fa *fa, char **regexp, size_t *regexp_len) {
4176     int r;
4177     struct state *fin = NULL, *ini = NULL;
4178     struct re *eps = NULL;
4179
4180     *regexp = NULL;
4181     *regexp_len = 0;
4182     fa = fa_clone(fa);
4183     if (fa == NULL)
4184         goto error;
4185
4186     eps = make_re(EPSILON);
4187     if (eps == NULL)
4188         goto error;
4189
4190     fin = add_state(fa,1);
4191     if (fin == NULL)
4192         goto error;
4193
4194     fa->trans_re = 1;
4195
4196     list_for_each(s, fa->initial) {
4197         r = convert_trans_to_re(s);
4198         if (r < 0)
4199             goto error;
4200         if (s->accept && s != fin) {
4201             r = add_new_re_trans(s, fin, ref(eps));
4202             if (r < 0)
4203                 goto error;
4204             s->accept = 0;
4205         }
4206     }
4207
4208     ini = add_state(fa, 0);
4209     if (ini == NULL)
4210         goto error;
4211
4212     r = add_new_re_trans(ini, fa->initial, ref(eps));
4213     if (r < 0)
4214         goto error;
4215     set_initial(fa, ini);
4216
4217     convert_strings(fa);
4218
4219     list_for_each(s, fa->initial->next) {
4220         if (s == fin)
4221             continue;
4222         /* Eliminate S */
4223         struct re *loop = eps;
4224         for_each_trans(t, s) {
4225             if (t->to == s)
4226                 loop = t->re;
4227         }
4228         list_for_each(s1, fa->initial) {
4229             if (s == s1)
4230                 continue;
4231             for (int t1 = 0; t1 < s1->tused; t1++) {
4232                 if (s1->trans[t1].to == s) {
4233                     for (int t = 0; t < s->tused; t++) {
4234                         if (s->trans[t].to == s)
4235                             continue;
4236                         r = re_collapse_trans(s1, s->trans[t].to,
4237                                               s1->trans[t1].re,
4238                                               loop,
4239                                               s->trans[t].re);
4240                         if (r < 0)
4241                             goto error;
4242                     }
4243                 }
4244             }
4245         }
4246     }
4247
4248     re_unref(eps);
4249
4250     for_each_trans(t, fa->initial) {
4251         if (t->to == fin) {
4252             struct re_str str;
4253             MEMZERO(&str, 1);
4254             if (re_as_string(t->re, &str) < 0)
4255                 goto error;
4256             *regexp = str.rx;
4257             *regexp_len = str.len;
4258         }
4259     }
4260
4261     list_for_each(s, fa->initial) {
4262         for_each_trans(t, s) {
4263             unref(t->re, re);
4264         }
4265     }
4266     fa_free(fa);
4267
4268     return 0;
4269  error:
4270     fa_free(fa);
4271     re_unref(eps);
4272     return -1;
4273 }
4274
4275 static int re_restrict_alphabet(struct re *re, uchar from, uchar to) {
4276     int r1, r2;
4277     int result = 0;
4278
4279     switch(re->type) {
4280     case UNION:
4281     case CONCAT:
4282         r1 = re_restrict_alphabet(re->exp1, from, to);
4283         r2 = re_restrict_alphabet(re->exp2, from, to);
4284         result = (r1 != 0) ? r1 : r2;
4285         break;
4286     case CSET:
4287         if (re->negate) {
4288             re->negate = 0;
4289             bitset_negate(re->cset, UCHAR_NUM);
4290         }
4291         for (int i=from; i <= to; i++)
4292             bitset_clr(re->cset, i);
4293         break;
4294     case CHAR:
4295         if (from <= re->c && re->c <= to)
4296             result = -1;
4297         break;
4298     case ITER:
4299         result = re_restrict_alphabet(re->exp, from, to);
4300         break;
4301     case EPSILON:
4302         break;
4303     default:
4304         assert(0);
4305         abort();
4306         break;
4307     }
4308     return result;
4309 }
4310
4311 int fa_restrict_alphabet(const char *regexp, size_t regexp_len,
4312                          char **newregexp, size_t *newregexp_len,
4313                          char from, char to) {
4314     int result;
4315     struct re *re = NULL;
4316     struct re_parse parse;
4317     struct re_str str;
4318
4319     *newregexp = NULL;
4320     MEMZERO(&parse, 1);
4321     parse.rx = regexp;
4322     parse.rend = regexp + regexp_len;
4323     parse.error = REG_NOERROR;
4324     re = parse_regexp(&parse);
4325     if (parse.error != REG_NOERROR)
4326         return parse.error;
4327
4328     result = re_restrict_alphabet(re, from, to);
4329     if (result != 0) {
4330         result = -2;
4331         goto done;
4332     }
4333
4334     MEMZERO(&str, 1);
4335     result = re_as_string(re, &str);
4336     *newregexp = str.rx;
4337     *newregexp_len = str.len;
4338  done:
4339     re_unref(re);
4340     return result;
4341 }
4342
4343 int fa_expand_char_ranges(const char *regexp, size_t regexp_len,
4344                           char **newregexp, size_t *newregexp_len) {
4345     int result;
4346     struct re *re = NULL;
4347     struct re_parse parse;
4348     struct re_str str;
4349
4350     *newregexp = NULL;
4351     MEMZERO(&parse, 1);
4352     parse.rx = regexp;
4353     parse.rend = regexp + regexp_len;
4354     parse.error = REG_NOERROR;
4355     parse.no_ranges = 1;
4356     re = parse_regexp(&parse);
4357     if (parse.error != REG_NOERROR)
4358         return parse.error;
4359
4360     MEMZERO(&str, 1);
4361     result = re_as_string(re, &str);
4362     *newregexp = str.rx;
4363     *newregexp_len = str.len;
4364     re_unref(re);
4365     return result;
4366 }
4367
4368 /* Expand regexp so that it is case-insensitive in a case-sensitive match.
4369  *
4370  * Return 1 when a change was made, -1 when an allocation failed, and 0
4371  * when no change was made.
4372  */
4373 static int re_case_expand(struct re *re) {
4374     int result = 0, r1, r2;
4375
4376     switch(re->type) {
4377     case UNION:
4378     case CONCAT:
4379         r1 = re_case_expand(re->exp1);
4380         r2 = re_case_expand(re->exp2);
4381         result = (r1 != 0) ? r1 : r2;
4382         break;
4383     case CSET:
4384         for (int c = 'A'; c <= 'Z'; c++)
4385             if (bitset_get(re->cset, c)) {
4386                 result = 1;
4387                 bitset_set(re->cset, tolower(c));
4388             }
4389         for (int c = 'a'; c <= 'z'; c++)
4390             if (bitset_get(re->cset, c)) {
4391                 result = 1;
4392                 bitset_set(re->cset, toupper(c));
4393             }
4394         break;
4395     case CHAR:
4396         if (isalpha(re->c)) {
4397             int c = re->c;
4398             re->type = CSET;
4399             re->negate = false;
4400             re->no_ranges = 0;
4401             re->cset = bitset_init(UCHAR_NUM);
4402             if (re->cset == NULL)
4403                 return -1;
4404             bitset_set(re->cset, tolower(c));
4405             bitset_set(re->cset, toupper(c));
4406             result = 1;
4407         }
4408         break;
4409     case ITER:
4410         result = re_case_expand(re->exp);
4411         break;
4412     case EPSILON:
4413         break;
4414     default:
4415         assert(0);
4416         abort();
4417         break;
4418     }
4419     return result;
4420 }
4421
4422 int fa_expand_nocase(const char *regexp, size_t regexp_len,
4423                      char **newregexp, size_t *newregexp_len) {
4424     int result, r;
4425     struct re *re = NULL;
4426     struct re_parse parse;
4427     struct re_str str;
4428
4429     *newregexp = NULL;
4430     MEMZERO(&parse, 1);
4431     parse.rx = regexp;
4432     parse.rend = regexp + regexp_len;
4433     parse.error = REG_NOERROR;
4434     re = parse_regexp(&parse);
4435     if (parse.error != REG_NOERROR)
4436         return parse.error;
4437
4438     r = re_case_expand(re);
4439     if (r < 0) {
4440         re_unref(re);
4441         return REG_ESPACE;
4442     }
4443
4444     if (r == 1) {
4445         MEMZERO(&str, 1);
4446         result = re_as_string(re, &str);
4447         *newregexp = str.rx;
4448         *newregexp_len = str.len;
4449     } else {
4450         *newregexp = strndup(regexp, regexp_len);
4451         *newregexp_len = regexp_len;
4452         result = (*newregexp == NULL) ? REG_ESPACE : REG_NOERROR;
4453     }
4454     re_unref(re);
4455     return result;
4456 }
4457
4458 static void print_char(FILE *out, uchar c) {
4459     /* We escape '/' as '\\/' since dot chokes on bare slashes in labels;
4460        Also, a space ' ' is shown as '\s' */
4461     static const char *const escape_from = " \n\t\v\b\r\f\a/\0";
4462     static const char *const escape_to = "sntvbrfa/0";
4463     char *p = strchr(escape_from, c);
4464     if (p != NULL) {
4465         int i = p - escape_from;
4466         fprintf(out, "\\\\%c", escape_to[i]);
4467     } else if (! isprint(c)) {
4468         fprintf(out, "\\\\0%03o", (unsigned char) c);
4469     } else if (c == '"') {
4470         fprintf(out, "\\\"");
4471     } else {
4472         fputc(c, out);
4473     }
4474 }
4475
4476 void fa_dot(FILE *out, struct fa *fa) {
4477     fprintf(out, "digraph {\n  rankdir=LR;");
4478     list_for_each(s, fa->initial) {
4479         if (s->accept) {
4480             fprintf(out, "\"%p\" [shape=doublecircle];\n", s);
4481         } else {
4482             fprintf(out, "\"%p\" [shape=circle];\n", s);
4483         }
4484     }
4485     fprintf(out, "%s -> \"%p\";\n", fa->deterministic ? "dfa" : "nfa",
4486             fa->initial);
4487
4488     struct re_str str;
4489     MEMZERO(&str, 1);
4490     list_for_each(s, fa->initial) {
4491         for_each_trans(t, s) {
4492             fprintf(out, "\"%p\" -> \"%p\" [ label = \"", s, t->to);
4493             if (fa->trans_re) {
4494                 re_as_string(t->re, &str);
4495                 for (int i=0; i < str.len; i++) {
4496                     print_char(out, str.rx[i]);
4497                 }
4498                 release_re_str(&str);
4499             } else {
4500                 print_char(out, t->min);
4501                 if (t->min != t->max) {
4502                     fputc('-', out);
4503                     print_char(out, t->max);
4504                 }
4505             }
4506             fprintf(out, "\" ];\n");
4507         }
4508     }
4509     fprintf(out, "}\n");
4510 }
4511
4512 /*
4513  * Local variables:
4514  *  indent-tabs-mode: nil
4515  *  c-indent-level: 4
4516  *  c-basic-offset: 4
4517  *  tab-width: 4
4518  * End:
4519  */