tests/fatest.c

   1 /*
   2  * fatest.c:
   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 #include <config.h>
  24
  25 #include "fa.h"
  26 #include "cutest.h"
  27 #include "internal.h"
  28 #include "memory.h"
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <ctype.h>
  32
  33 #define FA_DOT_DIR "FA_DOT_DIR"
  34
  35 struct fa_list {
  36     struct fa_list *next;
  37     struct fa *fa;
  38 };
  39
  40 static struct fa_list *fa_list;
  41
  42 static void print_regerror(int err, const char *regexp) {
  43     size_t size;
  44     char *errbuf;
  45     size = regerror(err, NULL, NULL, 0);
  46     if (ALLOC_N(errbuf, size) < 0)
  47         die_oom();
  48     regerror(err, NULL, errbuf, size);
  49     if (strlen(regexp) > 40) {
  50         char *s = strndup(regexp, 40);
  51         fprintf(stderr, "Error building fa from %s...:\n", s);
  52         free(s);
  53     } else {
  54         fprintf(stderr, "Error building fa from %s:\n", regexp);
  55     }
  56     fprintf(stderr, "  %s\n", errbuf);
  57     free(errbuf);
  58 }
  59
  60 static void setup(ATTRIBUTE_UNUSED CuTest *tc) {
  61     fa_list = NULL;
  62 }
  63
  64 static void teardown(ATTRIBUTE_UNUSED CuTest *tc) {
  65     list_for_each(fl, fa_list) {
  66         fa_free(fl->fa);
  67     }
  68     list_free(fa_list);
  69 }
  70
  71 static struct fa *mark(struct fa *fa) {
  72     struct fa_list *fl;
  73
  74     if (fa != NULL) {
  75         if (ALLOC(fl) < 0)
  76             die_oom();
  77         fl->fa = fa;
  78         list_cons(fa_list, fl);
  79     }
  80     return fa;
  81 }
  82
  83 static void assertAsRegexp(CuTest *tc, struct fa *fa) {
  84     char *re;
  85     size_t re_len;
  86     struct fa *fa1, *fa2;
  87     struct fa *empty = mark(fa_make_basic(FA_EPSILON));
  88     int r;
  89
  90     /* Jump through some hoops to make FA1 a copy of FA */
  91     fa1 = mark(fa_concat(fa, empty));
  92     /* Minimize FA1, otherwise the regexp returned is enormous for the */
  93     /* monster (~ 2MB) and fa_compile becomes incredibly slow          */
  94     r = fa_minimize(fa1);
  95     if (r < 0)
  96         die_oom();
  97
  98     r = fa_as_regexp(fa1, &re, &re_len);
  99     CuAssertIntEquals(tc, 0, r);
 100
 101     r = fa_compile(re, re_len, &fa2);
 102     if (r != REG_NOERROR) {
 103         print_regerror(r, re);
 104     }
 105     CuAssertIntEquals(tc, REG_NOERROR, r);
 106     CuAssertTrue(tc, fa_equals(fa, fa2));
 107
 108     fa_free(fa2);
 109     free(re);
 110 }
 111
 112 static struct fa *make_fa(CuTest *tc,
 113                           const char *regexp, size_t reglen,
 114                           int exp_err) {
 115     struct fa *fa;
 116     int r;
 117
 118     r = fa_compile(regexp, reglen, &fa);
 119     if (r == REG_ESPACE)
 120         die_oom();
 121     if (exp_err == REG_NOERROR) {
 122         if (r != REG_NOERROR)
 123             print_regerror(r, regexp);
 124         CuAssertIntEquals(tc, REG_NOERROR, r);
 125         CuAssertPtrNotNull(tc, fa);
 126         mark(fa);
 127         assertAsRegexp(tc, fa);
 128     } else {
 129         CuAssertIntEquals(tc, exp_err, r);
 130         CuAssertPtrEquals(tc, NULL, fa);
 131     }
 132     return fa;
 133 }
 134
 135 static struct fa *make_good_fa(CuTest *tc, const char *regexp) {
 136     return make_fa(tc, regexp, strlen(regexp), REG_NOERROR);
 137 }
 138
 139 static void dot(struct fa *fa) {
 140     static int count = 0;
 141     FILE *fp;
 142     const char *dot_dir;
 143     char *fname;
 144     int r;
 145
 146     if ((dot_dir = getenv(FA_DOT_DIR)) == NULL)
 147         return;
 148
 149     r = asprintf(&fname, "%s/fa_test_%02d.dot", dot_dir, count++);
 150     if (r == -1)
 151         return;
 152
 153     if ((fp = fopen(fname, "w")) == NULL) {
 154         free(fname);
 155         return;
 156     }
 157
 158     fa_dot(fp, fa);
 159     fclose(fp);
 160
 161     free(fname);
 162 }
 163
 164 static void testBadRegexps(CuTest *tc) {
 165     const char *const re1 = "(x";
 166     const char *const re2 = "a{5,3}";
 167     make_fa(tc, re1, strlen(re1), REG_EPAREN);
 168     make_fa(tc, re2, strlen(re2), REG_BADBR);
 169 }
 170
 171 /* Stress test, mostly good to check that allocation is clean */
 172 static void testMonster(CuTest *tc) {
 173 #define WORD "[a-zA-Z_0-9]+"
 174 #define CWS  "([ \\n\\t]+|\\/\\*([^\\*]|\\*[^\\/])*\\*\\/)*"
 175 #define QUOTED "\"[^\"]*\""
 176 #define ELT    "\\(" WORD "(," CWS WORD "){3}\\)"
 177
 178     static const char *const monster =
 179         "(" WORD "|" QUOTED "|" "\\(" CWS ELT  "(," CWS ELT ")*" CWS "\\))";
 180
 181 #undef ELT
 182 #undef QUOTED
 183 #undef CWS
 184 #undef WORD
 185
 186     struct fa *fa, *fas;
 187     char *upv, *pv, *v;
 188     size_t upv_len;
 189
 190     fa = make_good_fa(tc, monster);
 191
 192     fa_ambig_example(fa, fa, &upv, &upv_len, &pv, &v);
 193
 194     /* Monster can't be concatenated with itself */
 195     CuAssertStrEquals(tc, "AAA", upv);
 196     CuAssertStrEquals(tc, "AA", pv);
 197     CuAssertStrEquals(tc, "A", v);
 198     free(upv);
 199
 200     /* Monster can also not be starred */
 201     fas = mark(fa_iter(fa, 0, -1));
 202     /* Minimize FAS, otherwise the example returned is nondeterministic,
 203        since example generation depends on the structure of the FA.
 204        FIXME: Explain why UPV with the unminimized FAS changes to a much
 205        longer string simply when allocation patterns change (e.g., by
 206        running the test under valgrind vs. plain glibc malloc. Fishy ?
 207        FA_EXAMPLE should depend on the structure of the FA, but not
 208        incidental details like sorting of transitions.
 209      */
 210     fa_minimize(fas);
 211     fa_ambig_example(fas, fa, &upv, &upv_len, &pv, &v);
 212
 213     CuAssertStrEquals(tc, "AA", upv);
 214     CuAssertStrEquals(tc, "AA", pv);
 215     CuAssertStrEquals(tc, "A", v);
 216     free(upv);
 217 }
 218
 219 static void testChars(CuTest *tc) {
 220     struct fa *fa1, *fa2, *fa3;
 221
 222     fa1 = make_good_fa(tc, ".");
 223     fa2 = make_good_fa(tc, "[a-z]");
 224     CuAssertTrue(tc, fa_contains(fa2, fa1));
 225
 226     fa1 = make_good_fa(tc, "(.|\n)");
 227     CuAssertTrue(tc, fa_contains(fa2, fa1));
 228
 229     fa1 = mark(fa_intersect(fa1, fa2));
 230     CuAssertTrue(tc, fa_equals(fa1, fa2));
 231
 232     fa1 = make_good_fa(tc, "[^b-dxyz]");
 233     fa2 = make_good_fa(tc, "[a-z]");
 234     fa3 = mark(fa_intersect(fa1, fa2));
 235     fa2 = make_good_fa(tc, "[ae-w]");
 236     CuAssertTrue(tc, fa_equals(fa2, fa3));
 237 }
 238
 239 static void testManualAmbig(CuTest *tc) {
 240     /* The point of this test is mostly to teach me how Anders Moeller's
 241        algorithm for finding ambiguous strings works.
 242
 243        For the two languages a1 = a|ab and a2 = a|ba, a1.a2 has one
 244        ambiguous word aba, which can be split as a.ba and ab.a.
 245
 246        This uses X and Y as the markers*/
 247
 248     struct fa *a1f = make_good_fa(tc, "Xa|XaXb");
 249     struct fa *a1t = make_good_fa(tc, "(YX)*Xa|(YX)*Xa(YX)*Xb");
 250     struct fa *a2f = make_good_fa(tc, "Xa|XbXa");
 251     struct fa *a2t = make_good_fa(tc, "(YX)*Xa|((YX)*Xb(YX)*Xa)");
 252     struct fa *mp = make_good_fa(tc, "YX(X(.|\n))+");
 253     struct fa *ms = make_good_fa(tc, "YX(X(.|\n))*");
 254     struct fa *sp = make_good_fa(tc, "(X(.|\n))+YX");
 255     struct fa *ss = make_good_fa(tc, "(X(.|\n))*YX");
 256
 257     struct fa *a1f_mp = mark(fa_concat(a1f, mp));
 258     struct fa *a1f_mp_a1t = mark(fa_intersect(a1f_mp, a1t));
 259     struct fa *b1 = mark(fa_concat(a1f_mp_a1t, ms));
 260
 261     struct fa *sp_a2f = mark(fa_concat(sp, a2f));
 262     struct fa *sp_a2f_a2t = mark(fa_intersect(sp_a2f, a2t));
 263     struct fa *b2 = mark(fa_concat(ss, sp_a2f_a2t));
 264
 265     struct fa *amb = mark(fa_intersect(b1, b2));
 266     struct fa *exp = make_good_fa(tc, "XaYXXbYXXa");
 267     CuAssertTrue(tc, fa_equals(exp, amb));
 268 }
 269
 270 static void testContains(CuTest *tc) {
 271     struct fa *fa1, *fa2, *fa3;
 272
 273     fa1 = make_good_fa(tc, "ab*");
 274     fa2 = make_good_fa(tc, "ab+");
 275     fa3 = make_good_fa(tc, "ab+c*|acc");
 276
 277     CuAssertTrue(tc, fa_contains(fa1, fa1));
 278     CuAssertTrue(tc, fa_contains(fa2, fa2));
 279     CuAssertTrue(tc, fa_contains(fa3, fa3));
 280
 281     CuAssertTrue(tc, ! fa_contains(fa1, fa2));
 282     CuAssertTrue(tc, fa_contains(fa2, fa1));
 283     CuAssertTrue(tc, fa_contains(fa2, fa3));
 284     CuAssertTrue(tc, ! fa_contains(fa3, fa2));
 285     CuAssertTrue(tc, ! fa_contains(fa1, fa3));
 286     CuAssertTrue(tc, ! fa_contains(fa3, fa1));
 287 }
 288
 289 static void testIntersect(CuTest *tc) {
 290     struct fa *fa1, *fa2, *fa;
 291
 292     fa1 = make_good_fa(tc, "[a-zA-Z]*[.:=]([0-9]|[^A-Z])*");
 293     fa2 = make_good_fa(tc, "[a-z][:=][0-9a-z]+");
 294     fa = mark(fa_intersect(fa1, fa2));
 295     CuAssertPtrNotNull(tc, fa);
 296     CuAssertTrue(tc, fa_equals(fa, fa2));
 297     CuAssertTrue(tc, ! fa_equals(fa, fa1));
 298 }
 299
 300 static void testComplement(CuTest *tc) {
 301     struct fa *fa1 = make_good_fa(tc, "[b-y]+");
 302     struct fa *fa2 = mark(fa_complement(fa1));
 303     /* We use '()' to match the empty word explicitly */
 304     struct fa *fa3 = make_good_fa(tc, "(()|[b-y]*[^b-y](.|\n)*)");
 305
 306     CuAssertTrue(tc, fa_equals(fa2, fa3));
 307
 308     fa2 = mark(fa_complement(fa2));
 309     CuAssertTrue(tc, fa_equals(fa1, fa2));
 310 }
 311
 312 static void testOverlap(CuTest *tc) {
 313     struct fa *fa1 = make_good_fa(tc, "a|ab");
 314     struct fa *fa2 = make_good_fa(tc, "a|ba");
 315     struct fa *p   = mark(fa_overlap(fa1, fa2));
 316     struct fa *exp = make_good_fa(tc, "b");
 317
 318     CuAssertTrue(tc, fa_equals(exp, p));
 319
 320     fa1 = make_good_fa(tc, "a|b|c|abc");
 321     fa2 = mark(fa_iter(fa1, 0, -1));
 322     exp = make_good_fa(tc, "bc");
 323     p = mark(fa_overlap(fa1, fa2));
 324
 325     CuAssertTrue(tc, fa_equals(exp, p));
 326 }
 327
 328 static void assertExample(CuTest *tc, const char *regexp, const char *exp) {
 329     struct fa *fa = make_good_fa(tc, regexp);
 330     size_t xmpl_len;
 331     char *xmpl;
 332     fa_example(fa, &xmpl, &xmpl_len);
 333     CuAssertStrEquals(tc, exp, xmpl);
 334     free(xmpl);
 335
 336     fa_nocase(fa);
 337     char *s = strdup(exp);
 338     for (int i = 0; i < strlen(s); i++) s[i] = tolower(s[i]);
 339
 340     fa_example(fa, &xmpl, &xmpl_len);
 341     CuAssertStrEquals(tc, s, xmpl);
 342     free(xmpl);
 343     free(s);
 344 }
 345
 346 static void testExample(CuTest *tc) {
 347     assertExample(tc, "(.|\n)", "A");
 348     assertExample(tc, "(\n|\t|x)", "x");
 349     assertExample(tc, "[^b-y]", "A");
 350     assertExample(tc, "x*", "x");
 351     assertExample(tc, "yx*", "y");
 352     assertExample(tc, "ab+cx*", "abc");
 353     assertExample(tc, "ab+cx*|y*", "y");
 354     assertExample(tc, "u*|[0-9]", "u");
 355     assertExample(tc, "u+|[0-9]", "u");
 356     assertExample(tc, "vu+|[0-9]", "0");
 357     assertExample(tc, "vu{2}|[0-9]", "0");
 358     assertExample(tc, "\\[", "[");
 359     assertExample(tc, "[\\]", "\\");
 360     assertExample(tc, "a{3}", "aaa");
 361     assertExample(tc, "a{3,}", "aaa");
 362
 363     assertExample(tc, "\001((\002.)*\001)+\002", "\001\001\002");
 364     assertExample(tc, "\001((\001.)*\002)+\002", "\001\002\002");
 365
 366     assertExample(tc, "a[^\001-\004]+b", "aAb");
 367
 368     /* A strange way to write a? - allowed by POSIX */
 369     assertExample(tc, "(a|)", "a");
 370     assertExample(tc, "(|a)", "a");
 371
 372     struct fa *fa1 = mark(fa_make_basic(FA_EMPTY));
 373     size_t xmpl_len;
 374     char *xmpl;
 375     fa_example(fa1, &xmpl, &xmpl_len);
 376     CuAssertPtrEquals(tc, NULL, xmpl);
 377
 378     fa1 = mark(fa_make_basic(FA_EPSILON));
 379     fa_example(fa1, &xmpl, &xmpl_len);
 380     CuAssertStrEquals(tc, "", xmpl);
 381     free(xmpl);
 382 }
 383
 384 static void assertAmbig(CuTest *tc, const char *regexp1, const char *regexp2,
 385                         const char *exp_upv,
 386                         const char *exp_pv, const char *exp_v) {
 387
 388     struct fa *fa1 = make_good_fa(tc, regexp1);
 389     struct fa *fa2 = make_good_fa(tc, regexp2);
 390     char *upv, *pv, *v;
 391     size_t upv_len;
 392     fa_ambig_example(fa1, fa2, &upv, &upv_len, &pv, &v);
 393     CuAssertPtrNotNull(tc, upv);
 394     CuAssertPtrNotNull(tc, pv);
 395     CuAssertPtrNotNull(tc, v);
 396
 397     CuAssertStrEquals(tc, exp_upv, upv);
 398     CuAssertIntEquals(tc, strlen(exp_upv), upv_len);
 399     CuAssertStrEquals(tc, exp_pv, pv);
 400     CuAssertStrEquals(tc, exp_v, v);
 401     free(upv);
 402 }
 403
 404 static void assertNotAmbig(CuTest *tc, const char *regexp1,
 405                            const char *regexp2) {
 406     struct fa *fa1 = make_good_fa(tc, regexp1);
 407     struct fa *fa2 = make_good_fa(tc, regexp2);
 408     char *upv;
 409     size_t upv_len;
 410     fa_ambig_example(fa1, fa2, &upv, &upv_len, NULL, NULL);
 411     CuAssertPtrEquals(tc, NULL, upv);
 412 }
 413
 414 static void testAmbig(CuTest *tc) {
 415     assertAmbig(tc, "a|ab", "a|ba", "aba", "ba", "a");
 416     assertAmbig(tc, "(a|ab)*", "a|ba", "aba", "ba", "a");
 417     assertAmbig(tc, "(a|b|c|d|abcd)", "(a|b|c|d|abcd)*",
 418                 "abcd", "bcd", "");
 419     assertAmbig(tc, "(a*)*", "a*", "a", "a", "");
 420     assertAmbig(tc, "(a+)*", "a+", "aa", "aa", "a");
 421
 422     assertNotAmbig(tc, "a*", "a");
 423     assertNotAmbig(tc, "(a*b)*", "a*b");
 424     assertNotAmbig(tc, "(a|b|c|d|abcd)", "(a|b|c|d|abcd)");
 425 }
 426
 427 static void testAmbigWithNuls(CuTest *tc) {
 428     struct fa *fa1 = make_fa(tc, "X\0ba?", 5, REG_NOERROR);
 429     struct fa *fa2 = make_fa(tc, "a?\0Y", 4, REG_NOERROR);
 430     char *upv, *pv, *v;
 431     size_t upv_len;
 432     int r = fa_ambig_example(fa1, fa2, &upv, &upv_len, &pv, &v);
 433     CuAssertIntEquals(tc, 0, r);
 434     CuAssertIntEquals(tc, 6, (int)upv_len);
 435     /* u = "X\0b" */
 436     size_t u_len = pv - upv;
 437     CuAssertIntEquals(tc, 3, u_len);
 438     CuAssertIntEquals(tc, (int)'X', upv[0]);
 439     CuAssertIntEquals(tc, (int)'\0', upv[1]);
 440     CuAssertIntEquals(tc, (int)'b', upv[2]);
 441     /* p = "a" */
 442     size_t p_len = v - pv;
 443     CuAssertIntEquals(tc, 1, p_len);
 444     CuAssertIntEquals(tc, (int)'a', pv[0]);
 445     /* v = "\0Y" */
 446     size_t v_len = upv_len - (v - upv);
 447     CuAssertIntEquals(tc, 2, v_len);
 448     CuAssertIntEquals(tc, (int)'\0', v[0]);
 449     CuAssertIntEquals(tc, (int)'Y', v[1]);
 450     free(upv);
 451 }
 452
 453 static void assertFaAsRegexp(CuTest *tc, const char *regexp) {
 454     char *re;
 455     size_t re_len;
 456     struct fa *fa1 = make_good_fa(tc, regexp);
 457     struct fa *fa2;
 458     int r;
 459
 460     r = fa_as_regexp(fa1, &re, &re_len);
 461     CuAssertIntEquals(tc, 0, r);
 462
 463     r = fa_compile(re, strlen(re), &fa2);
 464     CuAssertIntEquals(tc, REG_NOERROR, r);
 465
 466     CuAssert(tc, regexp, fa_equals(fa1, fa2));
 467
 468     fa_free(fa2);
 469     free(re);
 470 }
 471
 472 static void testAsRegexp(CuTest *tc) {
 473     assertFaAsRegexp(tc, "a*");
 474     assertFaAsRegexp(tc, "abcd");
 475     assertFaAsRegexp(tc, "ab|cd");
 476     assertFaAsRegexp(tc, "[a-z]+");
 477     assertFaAsRegexp(tc, "[]a-]+");
 478     assertFaAsRegexp(tc, "[^0-9A-Z]");
 479     assertFaAsRegexp(tc, "ab|(xy[A-Z0-9])*(uv[^0-9]?)");
 480     assertFaAsRegexp(tc, "[A-CE-GI-LN-QS-Z]");
 481 }
 482
 483 static void testAsRegexpMinus(CuTest *tc) {
 484     struct fa *fa1 = make_good_fa(tc, "[A-Za-z]+");
 485     struct fa *fa2 = make_good_fa(tc, "Deny(Users|Groups|Other)");
 486     struct fa *fa = mark(fa_minus(fa1, fa2));
 487     char *re;
 488     size_t re_len;
 489     int r;
 490
 491     r = fa_as_regexp(fa, &re, &re_len);
 492     CuAssertIntEquals(tc, 0, r);
 493
 494     struct fa *far = make_good_fa(tc, re);
 495     CuAssertTrue(tc, fa_equals(fa, far));
 496
 497     free(re);
 498 }
 499
 500 static void testRangeEnd(CuTest *tc) {
 501     const char *const re = "[1-0]";
 502     make_fa(tc, re, strlen(re), REG_ERANGE);
 503 }
 504
 505 static void testNul(CuTest *tc) {
 506     static const char *const re0 = "a\0b";
 507     int re0_len = 3;
 508
 509     struct fa *fa1 = make_fa(tc, "a\0b", re0_len, REG_NOERROR);
 510     struct fa *fa2 = make_good_fa(tc, "a.b");
 511     char *re;
 512     size_t re_len;
 513     int r;
 514
 515     CuAssertTrue(tc, fa_contains(fa1, fa2));
 516
 517     r = fa_as_regexp(fa1, &re, &re_len);
 518     CuAssertIntEquals(tc, 0, r);
 519     CuAssertIntEquals(tc, re0_len, re_len);
 520     CuAssertIntEquals(tc, 0, memcmp(re0, re, re0_len));
 521     free(re);
 522 }
 523
 524 static void testRestrictAlphabet(CuTest *tc) {
 525     const char *re = "ab|(xy[B-Z0-9])*(uv[^0-9]?)";
 526     struct fa *fa_exp = make_good_fa(tc, "((xy[0-9])*)uv[^0-9A-Z]?|ab");
 527     struct fa *fa_act = NULL;
 528     size_t nre_len;
 529     char *nre;
 530     int r;
 531
 532     r = fa_restrict_alphabet(re, strlen(re), &nre, &nre_len, 'A', 'Z');
 533     CuAssertIntEquals(tc, 0, r);
 534     CuAssertIntEquals(tc, nre_len, strlen(nre));
 535     fa_act = make_good_fa(tc, nre);
 536     CuAssertTrue(tc, fa_equals(fa_exp, fa_act));
 537     free(nre);
 538
 539     r = fa_restrict_alphabet("HELLO", strlen("HELLO"),
 540                              &nre, &nre_len, 'A', 'Z');
 541     CuAssertIntEquals(tc, -2, r);
 542     CuAssertPtrEquals(tc, NULL, nre);
 543
 544     r = fa_restrict_alphabet("a{2,", strlen("a{2"), &nre, &nre_len, 'A', 'Z');
 545     CuAssertIntEquals(tc, REG_EBRACE, r);
 546 }
 547
 548 static void testExpandCharRanges(CuTest *tc) {
 549     const char *re = "[1-3]*|[a-b]([^\nU-X][^\n])*";
 550     const char *re2 = "a\\|b";
 551
 552     char *nre;
 553     size_t nre_len;
 554     int r;
 555
 556     r = fa_expand_char_ranges(re, strlen(re), &nre, &nre_len);
 557     CuAssertIntEquals(tc, 0, r);
 558     CuAssertStrEquals(tc, "[123]*|[ab]([^\nUVWX].)*", nre);
 559     CuAssertIntEquals(tc, strlen(nre), nre_len);
 560     free(nre);
 561
 562     r = fa_expand_char_ranges(re2, strlen(re2), &nre, &nre_len);
 563     CuAssertIntEquals(tc, 0, r);
 564     CuAssertStrEquals(tc, re2, nre);
 565     free(nre);
 566 }
 567
 568 static void testNoCase(CuTest *tc) {
 569     struct fa *fa1 = make_good_fa(tc, "[a-z0-9]");
 570     struct fa *fa2 = make_good_fa(tc, "B");
 571     struct fa *fa, *exp;
 572     int r;
 573
 574     fa_nocase(fa1);
 575     fa = fa_intersect(fa1, fa2);
 576     CuAssertPtrNotNull(tc, fa);
 577     r = fa_equals(fa, fa2);
 578     fa_free(fa);
 579     CuAssertIntEquals(tc, 1, r);
 580
 581     fa = fa_concat(fa1, fa2);
 582     exp = make_good_fa(tc, "[a-zA-Z0-9]B");
 583     r = fa_equals(fa, exp);
 584     fa_free(fa);
 585     CuAssertIntEquals(tc, 1, r);
 586 }
 587
 588 static void testExpandNoCase(CuTest *tc) {
 589     const char *p1 = "aB";
 590     const char *p2 = "[a-cUV]";
 591     const char *p3 = "[^a-z]";
 592     char *s;
 593     size_t len;
 594     int r;
 595
 596     r = fa_expand_nocase(p1, strlen(p1), &s, &len);
 597     CuAssertIntEquals(tc, 0, r);
 598     CuAssertStrEquals(tc, "[Aa][Bb]", s);
 599     free(s);
 600
 601     r = fa_expand_nocase(p2, strlen(p2), &s, &len);
 602     CuAssertIntEquals(tc, 0, r);
 603     CuAssertStrEquals(tc, "[A-CUVa-cuv]", s);
 604     free(s);
 605
 606     r = fa_expand_nocase(p3, strlen(p3), &s, &len);
 607     CuAssertIntEquals(tc, 0, r);
 608     CuAssertStrEquals(tc, "[^A-Za-z]", s);
 609     free(s);
 610 }
 611
 612 static void testNoCaseComplement(CuTest *tc) {
 613     const char *key_s = "keY";
 614     struct fa *key = make_good_fa(tc, key_s);
 615     struct fa *isect = NULL;
 616
 617     fa_nocase(key);
 618
 619     struct fa *comp = mark(fa_complement(key));
 620
 621     key = make_good_fa(tc, key_s);
 622
 623     /* We used to have a bug in totalize that caused the intersection
 624      * to contain "keY" */
 625     isect = fa_intersect(key, comp);
 626
 627     CuAssertIntEquals(tc, 1, fa_is_basic(isect, FA_EMPTY));
 628     fa_free(isect);
 629 }
 630
 631 static void free_words(int n, char **words) {
 632     for (int i=0; i < n; i++) {
 633         free(words[i]);
 634     }
 635     free(words);
 636 }
 637
 638 static void testEnumerate(CuTest *tc) {
 639     struct fa *fa1 = make_good_fa(tc, "[ab](cc|dd)");
 640     static const char *const fa1_expected[] =
 641         { "acc", "add", "bcc", "bdd" };
 642     struct fa *fa_inf = make_good_fa(tc, "a(b*|d)c");
 643     struct fa *fa_empty = make_good_fa(tc, "a?");
 644
 645     char **words;
 646     int r;
 647
 648     r = fa_enumerate(fa1, 2, &words);
 649     CuAssertIntEquals(tc, -2, r);
 650     CuAssertPtrEquals(tc, NULL, words);
 651
 652     r = fa_enumerate(fa1, 10, &words);
 653     CuAssertIntEquals(tc, 4, r);
 654     CuAssertPtrNotNull(tc, words);
 655
 656     for (int i=0; i < r; i++) {
 657         int found = 0;
 658         for (int j=0; j < ARRAY_CARDINALITY(fa1_expected); j++) {
 659             if (STREQ(words[i], fa1_expected[j]))
 660                 found = 1;
 661         }
 662         if (!found) {
 663             char *msg;
 664             /* Ignore return of asprintf intentionally */
 665             r = asprintf(&msg, "Generated word %s not expected", words[i]);
 666             CuFail(tc, msg);
 667         }
 668     }
 669     free_words(10, words);
 670
 671     r = fa_enumerate(fa_inf, 100, &words);
 672     CuAssertIntEquals(tc, -2, r);
 673     CuAssertPtrEquals(tc, NULL, words);
 674
 675     r = fa_enumerate(fa_empty, 10, &words);
 676     CuAssertIntEquals(tc, 2, r);
 677     CuAssertPtrNotNull(tc, words);
 678     CuAssertStrEquals(tc, "", words[0]);
 679     CuAssertStrEquals(tc, "a", words[1]);
 680     free_words(10, words);
 681 }
 682
 683 int main(int argc, char **argv) {
 684     if (argc == 1) {
 685         char *output = NULL;
 686         CuSuite* suite = CuSuiteNew();
 687         CuSuiteSetup(suite, setup, teardown);
 688
 689         SUITE_ADD_TEST(suite, testBadRegexps);
 690         SUITE_ADD_TEST(suite, testMonster);
 691         SUITE_ADD_TEST(suite, testChars);
 692         SUITE_ADD_TEST(suite, testManualAmbig);
 693         SUITE_ADD_TEST(suite, testContains);
 694         SUITE_ADD_TEST(suite, testIntersect);
 695         SUITE_ADD_TEST(suite, testComplement);
 696         SUITE_ADD_TEST(suite, testOverlap);
 697         SUITE_ADD_TEST(suite, testExample);
 698         SUITE_ADD_TEST(suite, testAmbig);
 699         SUITE_ADD_TEST(suite, testAmbigWithNuls);
 700         SUITE_ADD_TEST(suite, testAsRegexp);
 701         SUITE_ADD_TEST(suite, testAsRegexpMinus);
 702         SUITE_ADD_TEST(suite, testRangeEnd);
 703         SUITE_ADD_TEST(suite, testNul);
 704         SUITE_ADD_TEST(suite, testRestrictAlphabet);
 705         SUITE_ADD_TEST(suite, testExpandCharRanges);
 706         SUITE_ADD_TEST(suite, testNoCase);
 707         SUITE_ADD_TEST(suite, testExpandNoCase);
 708         SUITE_ADD_TEST(suite, testNoCaseComplement);
 709         SUITE_ADD_TEST(suite, testEnumerate);
 710
 711         CuSuiteRun(suite);
 712         CuSuiteSummary(suite, &output);
 713         CuSuiteDetails(suite, &output);
 714         printf("%s\n", output);
 715         free(output);
 716         int result = suite->failCount;
 717         CuSuiteFree(suite);
 718         return result;
 719     }
 720
 721     for (int i=1; i<argc; i++) {
 722         struct fa *fa;
 723         int r;
 724         if ((r = fa_compile(argv[i], strlen(argv[i]), &fa)) != REG_NOERROR) {
 725             print_regerror(r, argv[i]);
 726         } else {
 727             dot(fa);
 728             size_t s_len;
 729             char *s;
 730             fa_example(fa, &s, &s_len);
 731             printf("Example for %s: %s\n", argv[i], s);
 732             free(s);
 733             char *re;
 734             size_t re_len;
 735             r = fa_as_regexp(fa, &re, &re_len);
 736             if (r == 0) {
 737                 printf("/%s/ = /%s/\n", argv[i], re);
 738                 free(re);
 739             } else {
 740                 printf("/%s/ = ***\n", argv[i]);
 741             }
 742             fa_free(fa);
 743         }
 744     }
 745 }
 746
 747 /*
 748  * Local variables:
 749  *  indent-tabs-mode: nil
 750  *  c-indent-level: 4
 751  *  c-basic-offset: 4
 752  *  tab-width: 4
 753  * End:
 754  */