Imported Upstream version 3.1upstream/3.1upstream

1 files changed, 214 insertions, 284 deletions

diff --git a/lib/test.cc b/lib/test.cc
index 72c3d0c8..5cdbf24a 100644
--- a/lib/test.cc
+++ b/lib/test.cc
@@ -1,4 +1,4 @@
-#include <assert.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -8,12 +8,12 @@
 
 #include "lib/regex.h"
 #include "lib/test_helper.h"
-#include "src/util/c99_stdint.h"
+#include "src/util/check.h"
 
-
-static int test(int flags, const char *pattern, const char *string,
-    const char *expected = NULL)
-{
+static int test(int flags,
+                const char* pattern,
+                const char* string,
+                const char* expected = nullptr) {
     std::vector<std::vector<regoff_t> > submatch;
     if (!parse_submatch(expected, submatch)) {
         fprintf(stderr, "failed to parse submatch string: %s\n", expected);
@@ -24,26 +24,26 @@ static int test(int flags, const char *pattern, const char *string,
     static uint32_t total = 0;
     static uint32_t failed = 0;
 
-    const char *prefix = flags & REG_NFA ? "NFA" : "DFA";
+    const char* prefix = flags & REG_NFA ? "NFA" : "DFA";
     bool with_hist = flags & REG_SUBHIST;
     regex_t re;
-    regmatch_t *pmatch = with_hist ? NULL : new regmatch_t[nmatch];
-    subhistory_t *psubhist = NULL;
+    regmatch_t* pmatch = with_hist ? nullptr : new regmatch_t[nmatch];
+    subhistory_t* psubhist = nullptr;
     int result;
 
     result = regcomp(&re, pattern, flags);
     if (result != 0) {
-        fprintf(stderr, "%s: regcomp() failed for RE %s\n", prefix, pattern);
+        fprintf(stderr, "%s: regcomp() failed for regexp %s\n", prefix, pattern);
         goto end;
     }
 
     // run multiple times to ensure everything gets cleaned up properly
-    static const uint32_t NRUNS = 2;
+    static constexpr uint32_t NRUNS = 2;
     for (uint32_t i = 0; i < NRUNS; ++i) {
         if (with_hist) {
-            // With subhistories every regexec() call may allocate offsets.
-            // Clean them up at the beginning of the loop, so that the offsets
-            // remain available for inspection after the last iteration.
+            // With subhistories every regexec() call may allocate offsets. Clean them up at the
+            // beginning of the loop, so that the offsets remain available for inspection after the
+            // last iteration.
             regfreesub(psubhist);
             psubhist = regparse(&re, string, nmatch);
             result = psubhist ? 0 : 1;
@@ -55,62 +55,67 @@ static int test(int flags, const char *pattern, const char *string,
                 // failure was expected => it's a success
                 result = 0;
             } else if (nmatch > 0) {
-                fprintf(stderr, "%s: regexec() failed for RE %s and string %s\n"
-                    , prefix, pattern, string);
+                fprintf(stderr,
+                        "%s: regexec() failed for regexp %s and string %s\n",
+                        prefix, pattern, string);
                 goto end;
             }
         } else if (nmatch == 0) {
             // regexed must have failed, something is wrong
             result = REG_NOMATCH;
-            fprintf(stderr, "%s: regexec() didn't fail while it should"
-                " for RE %s and string %s\n", prefix, pattern, string);
+            fprintf(stderr,
+                    "%s: regexec() didn't fail while it should for regexp %s and string %s\n",
+                    prefix, pattern, string);
             goto end;
         }
     }
 
-    assert(nmatch == 0 || nmatch == re.re_nsub);
+    CHECK(nmatch == 0 || nmatch == re.re_nsub);
 
     for (uint32_t i = 0; i < nmatch; ++i) {
-        const std::vector<regoff_t> &expect_history = submatch[i];
+        const std::vector<regoff_t>& expect_history = submatch[i];
         const size_t expect_size = expect_history.size() / 2;
 
         if (!with_hist) {
             // Check only the last pair of offsets for each capturing group.
             const regoff_t expect_so = expect_history[2 * expect_size - 2];
             const regoff_t expect_eo = expect_history[2 * expect_size - 1];
-            const regmatch_t &actual = pmatch[i];
+            const regmatch_t& actual = pmatch[i];
             if (expect_so != actual.rm_so || expect_eo != actual.rm_eo) {
                 result = 1;
-                fprintf(stderr, "%s: incorrect submatch for RE %s and string %s:\n"
-                    "\tpmatch[%u].rm_so = %ld (expected %ld)\n"
-                    "\tpmatch[%u].rm_eo = %ld (expected %ld)\n",
-                    prefix, pattern, string,
-                    i, (long)actual.rm_so, (long)expect_so,
-                    i, (long)actual.rm_eo, (long)expect_eo);
+                fprintf(stderr,
+                        "%s: incorrect submatch for regexp %s and string %s:\n"
+                        "\tpmatch[%u].rm_so = %td (expected %td)\n"
+                        "\tpmatch[%u].rm_eo = %td (expected %td)\n",
+                        prefix, pattern, string,
+                        i, actual.rm_so, expect_so,
+                        i, actual.rm_eo, expect_eo);
                 goto end;
             }
         } else {
             // Check the full history of each capturing group.
-            const subhistory_t &actual_history = psubhist[i];
+            const subhistory_t& actual_history = psubhist[i];
             if (actual_history.size != expect_size) {
                 result = 1;
-                fprintf(stderr, "%s: wrong subhistory-%u length for RE %s and "
-                    "string %s: expected %lu, have %lu\n",
-                    prefix, i, pattern, string, expect_size, actual_history.size);
+                fprintf(stderr,
+                        "%s: wrong subhistory-%u length for regexp %s and string %s: "
+                        "expected %zd, have %zd\n",
+                        prefix, i, pattern, string, expect_size, actual_history.size);
                 goto end;
             }
             for (uint32_t j = 0; j < actual_history.size; ++j) {
                 const regoff_t expect_so = expect_history[2 * j];
                 const regoff_t expect_eo = expect_history[2 * j + 1];
-                const regmatch_t &actual = actual_history.offs[j];
+                const regmatch_t& actual = actual_history.offs[j];
                 if (expect_so != actual.rm_so || expect_eo != actual.rm_eo) {
                     result = 1;
-                    fprintf(stderr, "%s: incorrect submatch for RE %s and string %s:\n"
-                        "\tpmatch[%u][%u].rm_so = %ld (expected %ld)\n"
-                        "\tpmatch[%u][%u].rm_eo = %ld (expected %ld)\n",
-                        prefix, pattern, string,
-                        i, j, (long)actual.rm_so, (long)expect_so,
-                        i, j, (long)actual.rm_eo, (long)expect_eo);
+                    fprintf(stderr,
+                            "%s: incorrect submatch for regexp %s and string %s:\n"
+                            "\tpmatch[%u][%u].rm_so = %td (expected %td)\n"
+                            "\tpmatch[%u][%u].rm_eo = %td (expected %td)\n",
+                            prefix, pattern, string,
+                            i, j, actual.rm_so, expect_so,
+                            i, j, actual.rm_eo, expect_eo);
                     goto end;
                 }
             }
@@ -134,27 +139,25 @@ end:
     return result;
 }
 
-static int test_tstring(const char *pattern, const char *string, const char *expected)
-{
+static int test_tstring(const char* pattern, const char* string, const char* expected) {
     regex_t re;
-    const tstring_t *tstr;
+    const tstring_t* tstr = nullptr;
     std::ostringstream s;
     int result;
 
-    result = regcomp(&re, pattern, REG_REGLESS | REG_TSTRING);
+    result = regcomp(&re, pattern, REG_MULTIPASS | REG_TSTRING);
     if (result != 0) {
-        fprintf(stderr, "[t-string] regcomp() failed for RE %s\n", pattern);
+        fprintf(stderr, "[t-string] regcomp() failed for regexp %s\n", pattern);
         goto end;
     }
 
     // run multiple times to ensure everything gets cleaned up properly
-    static const uint32_t NRUNS = 2;
+    static constexpr uint32_t NRUNS = 2;
     for (uint32_t i = 0; i < NRUNS; ++i) {
         tstr = regtstring(&re, string);
-        if (tstr == NULL) {
+        if (tstr == nullptr) {
             result = 1;
-            fprintf(stderr, "regtstring() failed for RE %s and string %s\n",
-                pattern, string);
+            fprintf(stderr, "regtstring() failed for regexp %s and string %s\n", pattern, string);
             goto end;
         }
     }
@@ -163,7 +166,7 @@ static int test_tstring(const char *pattern, const char *string, const char *exp
     for (size_t i = 0; i < tstr->length; ++i) {
         const tchar_t c = tstr->string[i];
         if (c < TAG_BASE) {
-            assert(c < 0xff); // expect 1-byte characters
+            CHECK(c < 0xff); // expect 1-byte characters
             s << static_cast<char>(c);
         } else {
             s << c - TAG_BASE;
@@ -173,8 +176,9 @@ static int test_tstring(const char *pattern, const char *string, const char *exp
 
     if (strcmp(expected, s.str().c_str()) != 0) {
         result = 1;
-        fprintf(stderr, "incorrect t-string for RE %s and string %s:\n"
-            "\texpect: %s\n\tactual: %s\n", pattern, string, expected, s.str().c_str());
+        fprintf(stderr,
+                "incorrect t-string for regexp %s and string %s:\n\texpect: %s\n\tactual: %s\n",
+                pattern, string, expected, s.str().c_str());
     }
 
 end:
@@ -182,70 +186,60 @@ end:
     return result;
 }
 
-static int test_all_posix(int f)
-{
+static int test_all_posix(int f) {
     int e = 0;
 
     e |= test(f, "(a+(c+))|(b+(d+))", "ac", "(0,2),(0,2),(1,2),(?,?),(?,?)");
 
     e |= test(f, "(aaaa|aaa|a)+",    "aaaaaaaaaa", "(0,10),(0,4)(4,8)(8,9)(9,10)");
     e |= test(f, "(aaaa|aaa|a){3,}", "aaaaaaaaaa", "(0,10),(0,4)(4,8)(8,9)(9,10)");
-    if (!(f & REG_BACKWARD)) {
-        // expected failures for Cox algorithm
+    e |= test(f, "(aaaa|aaa|a){3,4}", "aaaaaaaaaa", "(0,10),(0,4)(4,8)(8,9)(9,10)");
 
-        e |= test(f, "(aaaa|aaa|a){3,4}", "aaaaaaaaaa", "(0,10),(0,4)(4,8)(8,9)(9,10)");
+    e |= test(f, "(aaaaaa|aaaaa|aaaa|aa|a){3,4}", "aaaaaaaaaaaaaaa",
+              "(0,15),(0,6)(6,12)(12,14)(14,15)");
 
-        e |= test(f, "(aaaaaa|aaaaa|aaaa|aa|a){3,4}", "aaaaaaaaaaaaaaa",
-            "(0,15),(0,6)(6,12)(12,14)(14,15)");
+    e |= test(f, "(aaaaa?a?|aa?){1,4}", "aaaaaaaaaaaaaaa", "(0,15),(0,6)(6,12)(12,14)(14,15)");
 
-        e |= test(f, "(aaaaa?a?|aa?){1,4}", "aaaaaaaaaaaaaaa",
-            "(0,15),(0,6)(6,12)(12,14)(14,15)");
+    e |= test(f, "(((a){3,4}a?)()a|aa?){1,4}", "aaaaaaaaaaaaaaa",
+              "(0,15),(0,6)(6,12)(12,14)(14,15),(0,5)(6,11)(?,?)(?,?),"
+              "(0,1)(1,2)(2,3)(3,4)(6,7)(7,8)(8,9)(9,10)(?,?)(?,?),(5,5)(11,11)(?,?)(?,?)");
 
-        e |= test(f, "(((a){3,4}a?)()a|aa?){1,4}", "aaaaaaaaaaaaaaa",
-            "(0,15),(0,6)(6,12)(12,14)(14,15),(0,5)(6,11)(?,?)(?,?),"
-            "(0,1)(1,2)(2,3)(3,4)(6,7)(7,8)(8,9)(9,10)(?,?)(?,?),(5,5)(11,11)(?,?)(?,?)");
+    e |= test(f, "(((aaaa?|a?)){1,4})+", "aaaaaaaaaa",
+              "(0,10),(0,10),(0,4)(4,8)(8,9)(9,10),(0,4)(4,8)(8,9)(9,10)");
 
-        e |= test(f, "(((aaaa?|a?)){1,4})+", "aaaaaaaaaa",
-            "(0,10),(0,10),(0,4)(4,8)(8,9)(9,10),(0,4)(4,8)(8,9)(9,10)");
+    e |= test(f, "((((a){2,3}(()|a)(()|a?)a|a?)){2,5})*", "aaaaaaaaaaaaaa",
+              "(0,14),(0,14),(0,6)(6,12)(12,13)(13,14),(0,6)(6,12)(12,13)(13,14),"
+              "(0,1)(1,2)(2,3)(6,7)(7,8)(8,9)(?,?)(?,?),(3,4)(9,10)(?,?)(?,?),"
+              "(?,?)(?,?)(?,?)(?,?),(4,5)(10,11)(?,?)(?,?),(?,?)(?,?)(?,?)(?,?)");
 
-        e |= test(f, "((((a){2,3}(()|a)(()|a?)a|a?)){2,5})*", "aaaaaaaaaaaaaa",
-            "(0,14),(0,14),(0,6)(6,12)(12,13)(13,14),(0,6)(6,12)(12,13)(13,14),"
-            "(0,1)(1,2)(2,3)(6,7)(7,8)(8,9)(?,?)(?,?),(3,4)(9,10)(?,?)(?,?),"
-            "(?,?)(?,?)(?,?)(?,?),(4,5)(10,11)(?,?)(?,?),(?,?)(?,?)(?,?)(?,?)");
-    }
-    if (!((f & REG_BACKWARD) && (f & REG_GTOP))) {
-        // expected failures for Cox algorithm
+    e |= test(f, "(((((a){3,3}a?|a?)){0,4})?)*", "aaaaaaaaaa",
+              "(0,10),(0,10),(0,10),(0,4)(4,8)(8,9)(9,10),"
+              "(0,4)(4,8)(8,9)(9,10),(0,1)(1,2)(2,3)(4,5)(5,6)(6,7)(?,?)(?,?)");
 
-        e |= test(f, "(((((a){3,3}a?|a?)){0,4})?)*", "aaaaaaaaaa",
-            "(0,10),(0,10),(0,10),(0,4)(4,8)(8,9)(9,10),"
-            "(0,4)(4,8)(8,9)(9,10),(0,1)(1,2)(2,3)(4,5)(5,6)(6,7)(?,?)(?,?)");
+    e |= test(f, "(((((a){3,4}|a?)){1,4}|((a)+(a|())){1,2}))*", "aaaaaaaaaa",
+              "(0,10),(0,10),(0,10),(0,4)(4,8)(8,9)(9,10),(0,4)(4,8)(8,9)(9,10),"
+              "(0,1)(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(?,?)(?,?),(?,?),(?,?),(?,?),(?,?)");
+
+    e |= test(f, "((a?|a?(a?a?)((())+)+))*", "aaaaaa",
+              "(0,6),(0,3)(3,6),(0,3)(3,6),(1,3)(4,6),(3,3)(6,6),(3,3)(6,6),(3,3)(6,6)");
 
-        e |= test(f, "(((((a){3,4}|a?)){1,4}|((a)+(a|())){1,2}))*", "aaaaaaaaaa",
-            "(0,10),(0,10),(0,10),(0,4)(4,8)(8,9)(9,10),(0,4)(4,8)(8,9)(9,10),"
-            "(0,1)(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(?,?)(?,?),(?,?),(?,?),(?,?),(?,?)");
-    }
-    if (!((f & REG_BACKWARD) && !(f & REG_GTOP))) {
-        // expected failures for Cox algorithm
-        e |= test(f, "((a?|a?(a?a?)((())+)+))*", "aaaaaa",
-            "(0,6),(0,3)(3,6),(0,3)(3,6),(1,3)(4,6),(3,3)(6,6),(3,3)(6,6),(3,3)(6,6)");
-    }
     e |= test(f, "(((a?a)){2,3})*", "aaaa", "(0,4),(0,4),(0,2)(2,4),(0,2)(2,4)");
 
     e |= test(f, "(((aa?a)((aaa)+))+)+", "aaaaaaaaaa",
-        "(0,10),(0,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),(2,5)(7,10)");
+              "(0,10),(0,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),(2,5)(7,10)");
 
     e |= test(f, "(((aaa?)((aaa)+))+)+", "aaaaaaaaaa",
-        "(0,10),(0,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),(2,5)(7,10)");
+              "(0,10),(0,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),(2,5)(7,10)");
 
     e |= test(f, "(((aaa?)((aaa){1,3})){1,2})*", "aaaaaaaaaa",
-        "(0,10),(0,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),(2,5)(7,10)");
+              "(0,10),(0,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),(2,5)(7,10)");
 
     e |= test(f, "((((aaa?)(aaa){1,3})){1,2})*", "aaaaaaaaaa",
-        "(0,10),(0,10),(0,5)(5,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10)");
+              "(0,10),(0,10),(0,5)(5,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10)");
 
     e |= test(f, "((((aaa?)((a){3,3}){1,3})){1,2})*", "aaaaaaaaaa",
-        "(0,10),(0,10),(0,5)(5,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),"
-        "(2,3)(3,4)(4,5)(7,8)(8,9)(9,10)");
+              "(0,10),(0,10),(0,5)(5,10),(0,5)(5,10),(0,2)(5,7),(2,5)(7,10),"
+              "(2,3)(3,4)(4,5)(7,8)(8,9)(9,10)");
 
     e |= test(f, "(a|aa)*", "",           "(0,0),(?,?)");
     e |= test(f, "(a|aa)*", "a",          "(0,1),(0,1)");
@@ -279,25 +273,19 @@ static int test_all_posix(int f)
 
     e |= test(f, "((y?){2,3}){2}", "yyyyy", "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)");
 
-    e |= test(f, "((y?){2,3}){2,3}", "yyyyy",
-        "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)");
+    e |= test(f, "((y?){2,3}){2,3}", "yyyyy", "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)");
 
     e |= test(f, "((y?){2,3})*", "yyyyy", "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)");
 
-    e |= test(f, "((y?){3}){2}", "yyyyy",
-        "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
+    e |= test(f, "((y?){3}){2}", "yyyyy", "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
 
-    e |= test(f, "((y?){3}){2,3}", "yyyyy",
-        "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
+    e |= test(f, "((y?){3}){2,3}", "yyyyy", "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
 
-    e |= test(f, "((y?){3})*", "yyyyy",
-        "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
+    e |= test(f, "((y?){3})*", "yyyyy", "(0,5),(0,3)(3,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
 
-    e |= test(f, "((y?)*){2}", "yyyyy",
-        "(0,5),(0,5)(5,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
+    e |= test(f, "((y?)*){2}", "yyyyy", "(0,5),(0,5)(5,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
 
-    e |= test(f, "((y?)*){2,3}", "yyyyy",
-        "(0,5),(0,5)(5,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
+    e |= test(f, "((y?)*){2,3}", "yyyyy", "(0,5),(0,5)(5,5),(0,1)(1,2)(2,3)(3,4)(4,5)(5,5)");
 
     e |= test(f, "((y?)*)*", "yyyyy", "(0,5),(0,5),(0,1)(1,2)(2,3)(3,4)(4,5)");
 
@@ -306,12 +294,8 @@ static int test_all_posix(int f)
     e |= test(f, "((a)|(b))*",   "ab",  "(0,2),(0,1)(1,2),(0,1)(?,?),(?,?)(1,2)");
     e |= test(f, "((a?)|(b?))*", "ab",  "(0,2),(0,1)(1,2),(0,1)(?,?),(?,?)(1,2)");
     e |= test(f, "((a?)|(b?))*", "ba",  "(0,2),(0,1)(1,2),(?,?)(1,2),(0,1)(?,?)");
-
-    if (!((f & REG_BACKWARD) && !(f & REG_GTOP))) {
-        e |= test(f, "((a?)|(b?)){2,3}", "ab", "(0,2),(0,1)(1,2),(0,1)(?,?),(?,?)(1,2)");
-    }
-    e |= test(f, "((a?)|(b?)){3}", "ab",
-        "(0,2),(0,1)(1,2)(2,2),(0,1)(?,?)(2,2),(?,?)(1,2)(?,?)");
+    e |= test(f, "((a?)|(b?)){2,3}", "ab", "(0,2),(0,1)(1,2),(0,1)(?,?),(?,?)(1,2)");
+    e |= test(f, "((a?)|(b?)){3}",   "ab", "(0,2),(0,1)(1,2)(2,2),(0,1)(?,?)(2,2),(?,?)(1,2)(?,?)");
 
     e |= test(f, "y{3}",                     "yyy", "(0,3)");
     e |= test(f, "y{0,2}",                   "",    "(0,0)");
@@ -377,16 +361,16 @@ static int test_all_posix(int f)
     e |= test(f, "((((((x))))))", "x", "(0,1),(0,1),(0,1),(0,1),(0,1),(0,1),(0,1)");
 
     e |= test(f, "((((((x))))))*", "xx",
-        "(0,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2)");
+              "(0,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2)");
 
     e |= test(f, "a?(ab|ba)*",
-        "abababababababababababababababababababab"
-        "ababababababababababababababababababababa",
-        "(0,81),"
-        "(1,3)(3,5)(5,7)(7,9)(9,11)(11,13)(13,15)(15,17)(17,19)(19,21)(21,23)"
-        "(23,25)(25,27)(27,29)(29,31)(31,33)(33,35)(35,37)(37,39)(39,41)(41,43)"
-        "(43,45)(45,47)(47,49)(49,51)(51,53)(53,55)(55,57)(57,59)(59,61)(61,63)"
-        "(63,65)(65,67)(67,69)(69,71)(71,73)(73,75)(75,77)(77,79)(79,81)");
+              "abababababababababababababababababababab"
+              "ababababababababababababababababababababa",
+              "(0,81),"
+              "(1,3)(3,5)(5,7)(7,9)(9,11)(11,13)(13,15)(15,17)(17,19)(19,21)(21,23)"
+              "(23,25)(25,27)(27,29)(29,31)(31,33)(33,35)(35,37)(37,39)(39,41)(41,43)"
+              "(43,45)(45,47)(47,49)(49,51)(51,53)(53,55)(55,57)(57,59)(59,61)(61,63)"
+              "(63,65)(65,67)(67,69)(69,71)(71,73)(73,75)(75,77)(77,79)(79,81)");
 
     e |= test(f, "a*a*a*a*a*b",   "aaaaaaaaab", "(0,10)");
     e |= test(f, "a[b]+bc",       "abbc",       "(0,4)");
@@ -425,8 +409,7 @@ static int test_all_posix(int f)
     // categorize
     e |= test(f, "(a*)(ab)*(b*)", "abc", "(0,2),(0,1),(?,?),(1,2)");
 
-    e |= test(f, "((a*)(ab)*)((b*)(a*))", "aba",
-        "(0,3),(0,2),(0,0),(0,2),(2,3),(2,2),(2,3)");
+    e |= test(f, "((a*)(ab)*)((b*)(a*))", "aba", "(0,3),(0,2),(0,0),(0,2),(2,3),(2,2),(2,3)");
 
     e |= test(f, "(...?.?)*",          "xxxxxx", "(0,6),(0,4)(4,6)");
     e |= test(f, "(a|ab)(bc|c)",       "abcabc", "(0,3),(0,2),(2,3)");
@@ -437,8 +420,7 @@ static int test_all_posix(int f)
     e |= test(f, "(a(b)?)+",           "aba",    "(0,3),(0,2)(2,3),(1,2)(?,?)");
     e |= test(f, ".*(.*)",             "ab",     "(0,2),(2,2)");
 
-    e |= test(f, "(a?)((ab)?)(b?)a?(ab)?b?", "abab",
-        "(0,4),(0,1),(1,1),(?,?),(1,2),(?,?)");
+    e |= test(f, "(a?)((ab)?)(b?)a?(ab)?b?", "abab", "(0,4),(0,1),(1,1),(?,?),(1,2),(?,?)");
 
     // forcedassoc
     e |= test(f, "(a|ab)(c|bcd)",       "abcd", "(0,4),(0,1),(1,4)");
@@ -520,8 +502,7 @@ static int test_all_posix(int f)
 
     e |= test(f, "((..)*(...)*)",              "xxx", "(0,3),(0,3),(?,?),(0,3)");
     e |= test(f, "((..)*(...)*)*",             "xxx", "(0,3),(0,3),(?,?),(0,3)");
-    e |= test(f, "((..)*(...)*)((..)*(...)*)", "xxx",
-        "(0,3),(0,3),(?,?),(0,3),(3,3),(?,?),(?,?)");
+    e |= test(f, "((..)*(...)*)((..)*(...)*)", "xxx", "(0,3),(0,3),(?,?),(0,3),(3,3),(?,?),(?,?)");
 
     // nullsubexpr
     e |= test(f, "(a*)*",      "a",        "(0,1),(0,1)");
@@ -596,19 +577,16 @@ static int test_all_posix(int f)
     e |= test(f, "(aa*|aaa*)(aa*|aaa*)",         "aaaaaa", "(0,6),(0,5),(5,6)");
     e |= test(f, "(aa*|aaa*){2}",                "aaaaaa", "(0,6),(0,5)(5,6)");
     e |= test(f, "((aa)*|(aaa)*)((aa)*|(aaa)*)", "aaaaaa",
-        "(0,6),(0,6),(0,2)(2,4)(4,6),(?,?),(6,6),(?,?),(?,?)");
+              "(0,6),(0,6),(0,2)(2,4)(4,6),(?,?),(6,6),(?,?),(?,?)");
     e |= test(f, "((aa)*|(aaa)*){2}",            "aaaaaa",
-        "(0,6),(0,6)(6,6),(0,2)(2,4)(4,6)(?,?),(?,?)(?,?)");
-    e |= test(f, "(aa)*|(aaa)*",                 "aaaaaa",
-        "(0,6),(0,2)(2,4)(4,6),(?,?)");
-
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XY",     "(0,2),(0,1)(1,2)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabY",   "(0,4),(0,3)(3,4)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababY", "(0,6),(0,4)(4,6)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabababY",
-        "(0,8),(0,3)(3,7)(7,8)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababababY",
-        "(0,10),(0,4)(4,8)(8,10)");
+              "(0,6),(0,6)(6,6),(0,2)(2,4)(4,6)(?,?),(?,?)(?,?)");
+    e |= test(f, "(aa)*|(aaa)*",                 "aaaaaa", "(0,6),(0,2)(2,4)(4,6),(?,?)");
+
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XY",         "(0,2),(0,1)(1,2)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabY",       "(0,4),(0,3)(3,4)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababY",     "(0,6),(0,4)(4,6)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabababY",   "(0,8),(0,3)(3,7)(7,8)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababababY", "(0,10),(0,4)(4,8)(8,10)");
 
     e |= test(f, "(y){2}",         "");
     e |= test(f, "(y){2}",         "y");
@@ -675,66 +653,62 @@ static int test_all_posix(int f)
 
     e |= test(f, "((..)|(.))",                     "aa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aa",
-        "(0,2),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2)");
+              "(0,2),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aa");
     e |= test(f, "((..)|(.)){1}",                  "aa", "(0,2),(0,2),(0,2),(?,?)");
-    e |= test(f, "((..)|(.)){2}",                  "aa",
-        "(0,2),(0,1)(1,2),(?,?)(?,?),(0,1)(1,2)");
+    e |= test(f, "((..)|(.)){2}",                  "aa", "(0,2),(0,1)(1,2),(?,?)(?,?),(0,1)(1,2)");
     e |= test(f, "((..)|(.)){3}",                  "aa");
     e |= test(f, "((..)|(.))*",                    "aa", "(0,2),(0,2),(0,2),(?,?)");
 
     e |= test(f, "((..)|(.))",                     "aaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaa",
-        "(0,3),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3)");
+              "(0,3),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaa",
-        "(0,3),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2),(2,3),(?,?),(2,3)");
-    e |= test(f, "((..)|(.)){1}",                  "aaa",
-        "(0,2),(0,2),(0,2),(?,?)");
-    e |= test(f, "((..)|(.)){2}",                  "aaa",
-        "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
+              "(0,3),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2),(2,3),(?,?),(2,3)");
+    e |= test(f, "((..)|(.)){1}",                  "aaa", "(0,2),(0,2),(0,2),(?,?)");
+    e |= test(f, "((..)|(.)){2}",                  "aaa", "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
     e |= test(f, "((..)|(.)){3}",                  "aaa",
-        "(0,3),(0,1)(1,2)(2,3),(?,?)(?,?)(?,?),(0,1)(1,2)(2,3)");
-    e |= test(f, "((..)|(.))*",                    "aaa",
-        "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
+              "(0,3),(0,1)(1,2)(2,3),(?,?)(?,?)(?,?),(0,1)(1,2)(2,3)");
+    e |= test(f, "((..)|(.))*",                    "aaa", "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
 
     e |= test(f, "((..)|(.))",                     "aaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
+              "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3),(3,4),(?,?),(3,4)");
+              "(0,4),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3),(3,4),(?,?),(3,4)");
     e |= test(f, "((..)|(.)){1}",                  "aaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.)){2}",                  "aaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
     e |= test(f, "((..)|(.)){3}",                  "aaaa",
-        "(0,4),(0,2)(2,3)(3,4),(0,2)(?,?)(?,?),(?,?)(2,3)(3,4)");
+              "(0,4),(0,2)(2,3)(3,4),(0,2)(?,?)(?,?),(?,?)(2,3)(3,4)");
     e |= test(f, "((..)|(.))*",                    "aaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
 
     e |= test(f, "((..)|(.))",                     "aaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
+              "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaaaa",
-        "(0,5),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,5),(?,?),(4,5)");
+              "(0,5),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,5),(?,?),(4,5)");
     e |= test(f, "((..)|(.)){1}",                  "aaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.)){2}",                  "aaaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
     e |= test(f, "((..)|(.)){3}",                  "aaaaa",
-        "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
+              "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
     e |= test(f, "((..)|(.))*",                    "aaaaa",
-        "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
+              "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
 
     e |= test(f, "((..)|(.))",                     "aaaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaaaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
+              "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaaaaa",
-        "(0,6),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,6),(4,6),(?,?)");
+              "(0,6),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,6),(4,6),(?,?)");
     e |= test(f, "((..)|(.)){1}",                  "aaaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.)){2}",                  "aaaaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
     e |= test(f, "((..)|(.)){3}",                  "aaaaaa",
-        "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
+              "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
     e |= test(f, "((..)|(.))*",                    "aaaaaa",
-        "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
+              "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
 
     e |= test(f, "X(.?){0,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){1,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
@@ -744,8 +718,7 @@ static int test_all_posix(int f)
     e |= test(f, "X(.?){5,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){6,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){7,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
-    e |= test(f, "X(.?){8,}Y",  "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){8,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
     e |= test(f, "X(.?){0,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){1,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){2,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
@@ -754,8 +727,7 @@ static int test_all_posix(int f)
     e |= test(f, "X(.?){5,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){6,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){7,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
-    e |= test(f, "X(.?){8,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){8,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
 
     e |= test(f, "(a|ab|c|bcd){0,}(d*)",   "ababcd", "(0,6),(0,2)(2,3)(3,6),(6,6)");
     e |= test(f, "(a|ab|c|bcd){1,}(d*)",   "ababcd", "(0,6),(0,2)(2,3)(3,6),(6,6)");
@@ -798,59 +770,53 @@ static int test_all_posix(int f)
 
     if (!(f & REG_NFA)) {
         e |= test(f, "((a?){1,300})*",
-            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-            "(0,50),(0,50),"
-            "(0,1)(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,9)(9,10)"
-            "(10,11)(11,12)(12,13)(13,14)(14,15)(15,16)(16,17)(17,18)(18,19)(19,20)"
-            "(20,21)(21,22)(22,23)(23,24)(24,25)(25,26)(26,27)(27,28)(28,29)(29,30)"
-            "(30,31)(31,32)(32,33)(33,34)(34,35)(35,36)(36,37)(37,38)(38,39)(39,40)"
-            "(40,41)(41,42)(42,43)(43,44)(44,45)(45,46)(46,47)(47,48)(48,49)(49,50)");
-    }
-    else if (!(f & (REG_SLOWPREC | REG_KUKLEWICZ))) {
+                  "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+                  "(0,50),(0,50),"
+                  "(0,1)(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,9)(9,10)"
+                  "(10,11)(11,12)(12,13)(13,14)(14,15)(15,16)(16,17)(17,18)(18,19)(19,20)"
+                  "(20,21)(21,22)(22,23)(23,24)(24,25)(25,26)(26,27)(27,28)(28,29)(29,30)"
+                  "(30,31)(31,32)(32,33)(33,34)(34,35)(35,36)(36,37)(37,38)(38,39)(39,40)"
+                  "(40,41)(41,42)(42,43)(43,44)(44,45)(45,46)(46,47)(47,48)(48,49)(49,50)");
+    } else if (!(f & REG_SLOWPREC)) {
         e |= test(f, "((a?){1,1000})*", "aaaa", "(0,4),(0,4),(3,4)");
 
         e |= test(f, "(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "",
-            "(0,0),(0,0),(0,0),(0,0),(0,0),(?,?),(0,0),(0,0)");
-
-        if (!((f & REG_BACKWARD) && !(f & REG_GTOP))) {
-            // expected failures for Cox algorithm
+                  "(0,0),(0,0),(0,0),(0,0),(0,0),(?,?),(0,0),(0,0)");
 
-            e |= test(f, "(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "aaa",
-                "(0,3),(0,3),(0,3),(0,3),(0,3),(?,?),(0,3),(2,3)");
+        e |= test(f, "(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "aaa",
+                  "(0,3),(0,3),(0,3),(0,3),(0,3),(?,?),(0,3),(2,3)");
 
-            e |= test(f, "(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "aaaaa",
-                "(0,5),(0,5),(0,5),(0,5),(0,5),(?,?),(0,5),(4,5)");
-        }
+        e |= test(f, "(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "aaaaa",
+                  "(0,5),(0,5),(0,5),(0,5),(0,5),(?,?),(0,5),(4,5)");
     }
 
     e |= test(f, "((((a?)+)|(aa))+)", "aaa",
-        "(0,3),(0,3),(0,3),(0,3),(0,1)(1,2)(2,3),(?,?)");
+              "(0,3),(0,3),(0,3),(0,3),(0,1)(1,2)(2,3),(?,?)");
 
     e |= test(f, "(((aa)|((a?)+))+)", "aaa",
-        "(0,3),(0,3),(0,3),(?,?),(0,3),(0,1)(1,2)(2,3)");
+              "(0,3),(0,3),(0,3),(?,?),(0,3),(0,1)(1,2)(2,3)");
 
     e |= test(f, "((a?){1,2}|(a)*)*", "aaaa", "(0,4),(0,4),(?,?),(0,1)(1,2)(2,3)(3,4)");
 
     e |= test(f, "(((a?){2,3}|(a)*))*", "aaaaa",
-        "(0,5),(0,5),(0,5),(?,?),(0,1)(1,2)(2,3)(3,4)(4,5)");
+              "(0,5),(0,5),(0,5),(?,?),(0,1)(1,2)(2,3)(3,4)(4,5)");
 
     e |= test(f, "(((a?)|(a?a?))+)", "aa", "(0,2),(0,2),(0,2),(?,?),(0,2)");
 
     e |= test(f, "((((a)*))*|((((a))*))+)*", "aa",
-        "(0,2),(0,2),(0,2),(0,2),(0,1)(1,2),(?,?),(?,?),(?,?),(?,?)");
+              "(0,2),(0,2),(0,2),(0,2),(0,1)(1,2),(?,?),(?,?),(?,?),(?,?)");
 
     e |= test(f, "(((a)*)*|((a)*)+)*", "aa", "(0,2),(0,2),(0,2),(0,1)(1,2),(?,?),(?,?)");
 
     e |= test(f, "(((a)+)|(((a)+)?))+", "aa",
-        "(0,2),(0,2),(0,2),(0,1)(1,2),(?,?),(?,?),(?,?)");
+              "(0,2),(0,2),(0,2),(0,1)(1,2),(?,?),(?,?),(?,?)");
 
     e |= test(f, "(a*|(a)*)*", "aa", "(0,2),(0,2),(?,?)");
 
     return e;
 }
 
-static int test_all_leftmost(int f)
-{
+static int test_all_leftmost(int f) {
     int e = 0;
 
     e |= test(f, "a",        "a",    "(0,1)");
@@ -902,16 +868,16 @@ static int test_all_leftmost(int f)
 
     e |= test(f, "((((((x))))))", "x", "(0,1),(0,1),(0,1),(0,1),(0,1),(0,1),(0,1)");
     e |= test(f, "((((((x))))))*", "xx",
-        "(0,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2)");
+              "(0,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2),(0,1)(1,2)");
 
     e |= test(f, "a?(ab|ba)*",
-        "abababababababababababababababababababab"
-        "ababababababababababababababababababababa",
-        "(0,81),"
-        "(1,3)(3,5)(5,7)(7,9)(9,11)(11,13)(13,15)(15,17)(17,19)(19,21)(21,23)"
-        "(23,25)(25,27)(27,29)(29,31)(31,33)(33,35)(35,37)(37,39)(39,41)(41,43)"
-        "(43,45)(45,47)(47,49)(49,51)(51,53)(53,55)(55,57)(57,59)(59,61)(61,63)"
-        "(63,65)(65,67)(67,69)(69,71)(71,73)(73,75)(75,77)(77,79)(79,81)");
+              "abababababababababababababababababababab"
+              "ababababababababababababababababababababa",
+              "(0,81),"
+              "(1,3)(3,5)(5,7)(7,9)(9,11)(11,13)(13,15)(15,17)(17,19)(19,21)(21,23)"
+              "(23,25)(25,27)(27,29)(29,31)(31,33)(33,35)(35,37)(37,39)(39,41)(41,43)"
+              "(43,45)(45,47)(47,49)(49,51)(51,53)(53,55)(55,57)(57,59)(59,61)(61,63)"
+              "(63,65)(65,67)(67,69)(69,71)(71,73)(73,75)(75,77)(77,79)(79,81)");
 
     e |= test(f, "a*a*a*a*a*b",   "aaaaaaaaab", "(0,10)");
     e |= test(f, "a[b]+bc",       "abbc",       "(0,4)");
@@ -950,8 +916,7 @@ static int test_all_leftmost(int f)
     // categorize
     e |= test(f, "(a*)(ab)*(b*)", "abc", "(0,2),(0,1),(?,?),(1,2)");
 
-    e |= test(f, "((a*)(ab)*)((b*)(a*))", "aba",
-        "(0,3),(0,1),(0,1),(?,?),(1,3),(1,2),(2,3)");
+    e |= test(f, "((a*)(ab)*)((b*)(a*))", "aba", "(0,3),(0,1),(0,1),(?,?),(1,3),(1,2),(2,3)");
 
     e |= test(f, "(...?.?)*",          "xxxxxx", "(0,6),(0,4)(4,6)");
     e |= test(f, "(a|ab)(bc|c)",       "abcabc", "(0,3),(0,1),(1,3)");
@@ -962,8 +927,7 @@ static int test_all_leftmost(int f)
     e |= test(f, "(a(b)?)+",           "aba",    "(0,3),(0,2)(2,3),(1,2)(?,?)");
     e |= test(f, ".*(.*)",             "ab",     "(0,2),(2,2)");
 
-    e |= test(f, "(a?)((ab)?)(b?)a?(ab)?b?", "abab",
-        "(0,4),(0,1),(1,1),(?,?),(1,2),(?,?)");
+    e |= test(f, "(a?)((ab)?)(b?)a?(ab)?b?", "abab", "(0,4),(0,1),(1,1),(?,?),(1,2),(?,?)");
 
     // forcedassoc
     e |= test(f, "(a|ab)(c|bcd)",       "abcd", "(0,4),(0,1),(1,4)");
@@ -1042,8 +1006,7 @@ static int test_all_leftmost(int f)
 
     e |= test(f, "((..)*(...)*)",              "xxx", "(0,3),(0,3),(?,?),(0,3)");
     e |= test(f, "((..)*(...)*)*",             "xxx", "(0,3),(0,3),(?,?),(0,3)");
-    e |= test(f, "((..)*(...)*)((..)*(...)*)", "xxx",
-        "(0,3),(0,3),(?,?),(0,3),(3,3),(?,?),(?,?)");
+    e |= test(f, "((..)*(...)*)((..)*(...)*)", "xxx", "(0,3),(0,3),(?,?),(0,3),(3,3),(?,?),(?,?)");
 
     // nullsubexpr
     e |= test(f, "(a*)*",        "a",        "(0,1),(0,1)");
@@ -1121,17 +1084,16 @@ static int test_all_leftmost(int f)
     e |= test(f, "(aa*|aaa*)(aa*|aaa*)",         "aaaaaa", "(0,6),(0,5),(5,6)");
     e |= test(f, "(aa*|aaa*){2}",                "aaaaaa", "(0,6),(0,5)(5,6)");
     e |= test(f, "((aa)*|(aaa)*)((aa)*|(aaa)*)", "aaaaaa",
-        "(0,6),(0,6),(0,2)(2,4)(4,6),(?,?),(6,6),(?,?),(?,?)");
+              "(0,6),(0,6),(0,2)(2,4)(4,6),(?,?),(6,6),(?,?),(?,?)");
     e |= test(f, "((aa)*|(aaa)*){2}",            "aaaaaa",
-        "(0,6),(0,6)(6,6),(0,2)(2,4)(4,6)(?,?),(?,?)(?,?)");
+              "(0,6),(0,6)(6,6),(0,2)(2,4)(4,6)(?,?),(?,?)(?,?)");
     e |= test(f, "(aa)*|(aaa)*",                 "aaaaaa", "(0,6),(0,2)(2,4)(4,6),(?,?)");
 
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XY",        "(0,2),(0,1)(1,2)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabY",      "(0,4),(0,2)(2,4)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababY",    "(0,6),(0,1)(1,5)(5,6)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabababY",  "(0,8),(0,2)(2,6)(6,8)");
-    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababababY",
-        "(0,10),(0,1)(1,5)(5,9)(9,10)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XY",         "(0,2),(0,1)(1,2)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabY",       "(0,4),(0,2)(2,4)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababY",     "(0,6),(0,1)(1,5)(5,6)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XabababY",   "(0,8),(0,2)(2,6)(6,8)");
+    e |= test(f, "(X|Xa|Xab|Xaba|abab|baba|bY|Y)*", "XababababY", "(0,10),(0,1)(1,5)(5,9)(9,10)");
 
     e |= test(f, "(y){2}",        "");
     e |= test(f, "(y){2}",        "y");
@@ -1197,65 +1159,62 @@ static int test_all_leftmost(int f)
 
     e |= test(f, "((..)|(.))",                     "aa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aa",
-        "(0,2),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2)");
+              "(0,2),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aa");
     e |= test(f, "((..)|(.)){1}",                  "aa", "(0,2),(0,2),(0,2),(?,?)");
-    e |= test(f, "((..)|(.)){2}",                  "aa",
-        "(0,2),(0,1)(1,2),(?,?)(?,?),(0,1)(1,2)");
+    e |= test(f, "((..)|(.)){2}",                  "aa", "(0,2),(0,1)(1,2),(?,?)(?,?),(0,1)(1,2)");
     e |= test(f, "((..)|(.)){3}",                  "aa");
     e |= test(f, "((..)|(.))*",                    "aa", "(0,2),(0,2),(0,2),(?,?)");
 
     e |= test(f, "((..)|(.))",                     "aaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaa",
-        "(0,3),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3)");
+              "(0,3),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaa",
-        "(0,3),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2),(2,3),(?,?),(2,3)");
+              "(0,3),(0,1),(?,?),(0,1),(1,2),(?,?),(1,2),(2,3),(?,?),(2,3)");
     e |= test(f, "((..)|(.)){1}",                  "aaa", "(0,2),(0,2),(0,2),(?,?)");
-    e |= test(f, "((..)|(.)){2}",                  "aaa",
-        "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
+    e |= test(f, "((..)|(.)){2}",                  "aaa", "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
     e |= test(f, "((..)|(.)){3}",                  "aaa",
-        "(0,3),(0,1)(1,2)(2,3),(?,?)(?,?)(?,?),(0,1)(1,2)(2,3)");
-    e |= test(f, "((..)|(.))*",                    "aaa",
-        "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
+              "(0,3),(0,1)(1,2)(2,3),(?,?)(?,?)(?,?),(0,1)(1,2)(2,3)");
+    e |= test(f, "((..)|(.))*",                    "aaa", "(0,3),(0,2)(2,3),(0,2)(?,?),(?,?)(2,3)");
 
     e |= test(f, "((..)|(.))",                     "aaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
+              "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3),(3,4),(?,?),(3,4)");
+              "(0,4),(0,2),(0,2),(?,?),(2,3),(?,?),(2,3),(3,4),(?,?),(3,4)");
     e |= test(f, "((..)|(.)){1}",                  "aaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.)){2}",                  "aaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
     e |= test(f, "((..)|(.)){3}",                  "aaaa",
-        "(0,4),(0,2)(2,3)(3,4),(0,2)(?,?)(?,?),(?,?)(2,3)(3,4)");
+              "(0,4),(0,2)(2,3)(3,4),(0,2)(?,?)(?,?),(?,?)(2,3)(3,4)");
     e |= test(f, "((..)|(.))*",                    "aaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
 
     e |= test(f, "((..)|(.))",                     "aaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
+              "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaaaa",
-        "(0,5),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,5),(?,?),(4,5)");
+              "(0,5),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,5),(?,?),(4,5)");
     e |= test(f, "((..)|(.)){1}",                  "aaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.)){2}",                  "aaaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
     e |= test(f, "((..)|(.)){3}",                  "aaaaa",
-        "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
+              "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
     e |= test(f, "((..)|(.))*",                    "aaaaa",
-        "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
+              "(0,5),(0,2)(2,4)(4,5),(0,2)(2,4)(?,?),(?,?)(?,?)(4,5)");
 
     e |= test(f, "((..)|(.))",                     "aaaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))",           "aaaaaa",
-        "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
+              "(0,4),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?)");
     e |= test(f, "((..)|(.))((..)|(.))((..)|(.))", "aaaaaa",
-        "(0,6),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,6),(4,6),(?,?)");
+              "(0,6),(0,2),(0,2),(?,?),(2,4),(2,4),(?,?),(4,6),(4,6),(?,?)");
     e |= test(f, "((..)|(.)){1}",                  "aaaaaa", "(0,2),(0,2),(0,2),(?,?)");
     e |= test(f, "((..)|(.)){2}",                  "aaaaaa",
-        "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
+              "(0,4),(0,2)(2,4),(0,2)(2,4),(?,?)(?,?)");
     e |= test(f, "((..)|(.)){3}",                  "aaaaaa",
-        "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
+              "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
     e |= test(f, "((..)|(.))*",                    "aaaaaa",
-        "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
+              "(0,6),(0,2)(2,4)(4,6),(0,2)(2,4)(4,6),(?,?)(?,?)(?,?)");
 
     e |= test(f, "X(.?){0,}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){1,}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
@@ -1266,26 +1225,16 @@ static int test_all_leftmost(int f)
     e |= test(f, "X(.?){6,}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
     e |= test(f, "X(.?){7,}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)");
 
-    e |= test(f, "X(.?){8,}Y",  "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){0,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){1,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){2,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){3,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){4,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){5,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){6,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){7,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
-    e |= test(f, "X(.?){8,8}Y", "X1234567Y",
-        "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){8,}Y",  "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){0,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){1,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){2,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){3,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){4,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){5,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){6,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){7,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
+    e |= test(f, "X(.?){8,8}Y", "X1234567Y", "(0,9),(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,8)");
 
     e |= test(f, "(a|ab|c|bcd){0,}(d*)",   "ababcd", "(0,6),(0,2)(2,3)(3,6),(6,6)");
     e |= test(f, "(a|ab|c|bcd){1,}(d*)",   "ababcd", "(0,6),(0,2)(2,3)(3,6),(6,6)");
@@ -1327,20 +1276,15 @@ static int test_all_leftmost(int f)
     e |= test(f, "(ab|a)(bcd|c)(d|.*)", "abcd", "(0,4),(0,2),(2,3),(3,4)");
 
     // other
-    if (!(f & REG_STADFA)) {
-        // TODO: Find out why this test takes a long time on staDFA.
-
-        std::string s = "(0,4),(0,4),(0,1)(1,2)(2,3)(3,4)";
-        for (size_t i = 0; i < 1000 - 4; ++i) s += "(4,4)";
+    std::string s = "(0,4),(0,4),(0,1)(1,2)(2,3)(3,4)";
+    for (size_t i = 0; i < 1000 - 4; ++i) s += "(4,4)";
 
-        e |= test(f, "((a?){1,1000})*", "aaaa", s.c_str());
-    }
+    e |= test(f, "((a?){1,1000})*", "aaaa", s.c_str());
 
     return e;
 }
 
-static int test_all_tstring()
-{
+static int test_all_tstring() {
     int e = 0;
 
     e |= test_tstring("a",        "a",   "1 a 2 ");
@@ -1360,41 +1304,27 @@ static int test_all_tstring()
     return e;
 }
 
-int main()
-{
+int main() {
     int e = 0;
 
     e |= test_all_posix(0);
-    e |= test_all_posix(REG_STADFA);
-    e |= test_all_posix(REG_REGLESS);
+    e |= test_all_posix(REG_MULTIPASS);
     e |= test_all_posix(REG_SUBHIST);
-    e |= test_all_posix(REG_SUBHIST | REG_REGLESS);
+    e |= test_all_posix(REG_SUBHIST | REG_MULTIPASS);
 
     e |= test_all_leftmost(REG_LEFTMOST);
-    e |= test_all_leftmost(REG_LEFTMOST | REG_STADFA);
-    e |= test_all_leftmost(REG_LEFTMOST | REG_REGLESS);
+    e |= test_all_leftmost(REG_LEFTMOST | REG_MULTIPASS);
     e |= test_all_leftmost(REG_LEFTMOST | REG_SUBHIST);
-    e |= test_all_leftmost(REG_LEFTMOST | REG_SUBHIST | REG_REGLESS);
+    e |= test_all_leftmost(REG_LEFTMOST | REG_SUBHIST | REG_MULTIPASS);
 
     e |= test_all_posix(REG_NFA);
-    e |= test_all_posix(REG_NFA | REG_GTOP);
-
-    e |= test_all_posix(REG_NFA | REG_KUKLEWICZ);
-    e |= test_all_posix(REG_NFA | REG_KUKLEWICZ | REG_GTOP);
-
     e |= test_all_posix(REG_NFA | REG_TRIE);
-    e |= test_all_posix(REG_NFA | REG_TRIE | REG_GTOP);
-
     e |= test_all_posix(REG_NFA | REG_SLOWPREC);
 
     e |= test_all_leftmost(REG_NFA | REG_LEFTMOST);
     e |= test_all_leftmost(REG_NFA | REG_LEFTMOST | REG_TRIE);
 
-    e |= test_all_posix(REG_NFA | REG_BACKWARD);
-    e |= test_all_posix(REG_NFA | REG_BACKWARD | REG_GTOP);
-
     e |= test_all_tstring();
 
     return e;
 }
-