path: root/lib/test.cc

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "lib/regex.h"
#include "src/util/c99_stdint.h"


static int test(const char *pattern, const char *string
    , size_t nmatch, const regoff_t *submatch, int flags)
{
    static uint32_t total = 0;
    static uint32_t failed = 0;

    regex_t re;
    regmatch_t *pmatch = new regmatch_t[nmatch];
    const char *prefix = flags & REG_NFA ? "NFA" : "DFA";
    int result;

    result = regcomp(&re, pattern, flags);
    if (result != 0) {
        fprintf(stderr, "%s: regcomp() failed for RE %s\n", prefix, pattern);
        goto end;
    }

    // run multiple times to ensure everything gets cleaned up properly
    static const uint32_t NRUNS = 2;
    for (uint32_t i = 0; i < NRUNS; ++i) {
        result = regexec(&re, string, nmatch, pmatch, flags);
        if (result != 0) {
            if (nmatch == 0) {
                // 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);
                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);
            goto end;
        }
    }

    assert(nmatch == 0 || nmatch == re.re_nsub);

    for (uint32_t i = 0; i < nmatch; ++i) {
        regoff_t so = submatch[2 * i];
        regoff_t eo = submatch[2 * i + 1];
        const regmatch_t &have = pmatch[i];

        if (so != have.rm_so || eo != have.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)have.rm_so, (long)so
                , i, (long)have.rm_eo, (long)eo);
            goto end;
        }
    }

end:
    regfree(&re);
    delete[] pmatch;

    ++total;
    if (result != 0) {
        ++failed;
        fprintf(stderr, "failed %u of %u\n", failed, total);
    }

    return result;
}

// Poor man's replacement for C++11 initializer lists. :)
// Variadic macros are non-standard in c++98. Variadic functions have
// subtle problems with types: literals are 'int' by default, so passing
// 'long' as vararg requres suffix 'L', which is easy to forget and hard
// to notice (the problem is platform/toolchain-specific).
#define  GS                                              static const regoff_t gs[]
#define  T(R,S,gs)                                       do { e |= test(R,S,sizeof(gs)/sizeof(gs[0])/2,gs,flags); } while(0)
#define  T0(R,S)                                         do { e |= test(R,S,0,NULL,flags); } while(0)
#define  T1(R,S,a,b)                                     do { GS = {a,b};                                     T(R,S,gs); } while(0)
#define  T2(R,S,a,b,c,d)                                 do { GS = {a,b,c,d};                                 T(R,S,gs); } while(0)
#define  T3(R,S,a,b,c,d,e,f)                             do { GS = {a,b,c,d,e,f};                             T(R,S,gs); } while(0)
#define  T4(R,S,a,b,c,d,e,f,g,h)                         do { GS = {a,b,c,d,e,f,g,h};                         T(R,S,gs); } while(0)
#define  T5(R,S,a,b,c,d,e,f,g,h,i,j)                     do { GS = {a,b,c,d,e,f,g,h,i,j};                     T(R,S,gs); } while(0)
#define  T6(R,S,a,b,c,d,e,f,g,h,i,j,k,l)                 do { GS = {a,b,c,d,e,f,g,h,i,j,k,l};                 T(R,S,gs); } while(0)
#define  T7(R,S,a,b,c,d,e,f,g,h,i,j,k,l,m,n)             do { GS = {a,b,c,d,e,f,g,h,i,j,k,l,m,n};             T(R,S,gs); } while(0)
#define  T8(R,S,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p)         do { GS = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p};         T(R,S,gs); } while(0)
#define  T9(R,S,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r)     do { GS = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r};     T(R,S,gs); } while(0)
#define T10(R,S,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t) do { GS = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t}; T(R,S,gs); } while(0)

static int test_all_posix(int flags)
{
    int e = 0;

    T5("(a+(c+))|(b+(d+))", "ac", 0,2, 0,2, 1,2, -1,-1, -1,-1);

    T2("(aaaa|aaa|a)+", "aaaaaaaaaa", 0,10, 9,10);
    T2("(aaaa|aaa|a){3,}", "aaaaaaaaaa", 0,10, 9,10);
    if (!(flags & REG_BACKWARD)) {
        // expected failures for Cox algorithm
        T2("(aaaa|aaa|a){3,4}", "aaaaaaaaaa", 0,10, 9,10);
        T2("(aaaaaa|aaaaa|aaaa|aa|a){3,4}", "aaaaaaaaaaaaaaa", 0,15, 14,15);
        T2("(aaaaa?a?|aa?){1,4}", "aaaaaaaaaaaaaaa", 0,15, 14,15);
        T5("(((a){3,4}a?)()a|aa?){1,4}", "aaaaaaaaaaaaaaa", 0,15, 14,15, -1,-1, -1,-1, -1,-1);
        T4("(((aaaa?|a?)){1,4})+", "aaaaaaaaaa", 0,10, 0,10, 9,10, 9,10);
        T9("((((a){2,3}(()|a)(()|a?)a|a?)){2,5})*", "aaaaaaaaaaaaaa", 0,14, 0,14, 13,14, 13,14, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1);
    }
    if (!((flags & REG_BACKWARD) && (flags & REG_GTOP))) {
        // expected failures for Cox algorithm
        T6("(((((a){3,3}a?|a?)){0,4})?)*", "aaaaaaaaaa", 0,10, 0,10, 0,10, 9,10, 9,10, -1,-1);
        T10("(((((a){3,4}|a?)){1,4}|((a)+(a|())){1,2}))*", "aaaaaaaaaa", 0,10, 0,10, 0,10, 9,10, 9,10, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1);
    }
    if (!((flags & REG_BACKWARD) && !(flags & REG_GTOP))) {
        // expected failures for Cox algorithm
        T7("((a?|a?(a?a?)((())+)+))*", "aaaaaa", 0,6, 3,6, 3,6, 4,6, 6,6, 6,6, 6,6);
    }
    T4("(((a?a)){2,3})*", "aaaa", 0,4, 0,4, 2,4, 2,4);

    T6("(((aa?a)((aaa)+))+)+",              "aaaaaaaaaa", 0,10, 0,10, 5,10, 5,7, 7,10, 7,10);
    T6("(((aaa?)((aaa)+))+)+",              "aaaaaaaaaa", 0,10, 0,10, 5,10, 5,7, 7,10, 7,10);
    T6("(((aaa?)((aaa){1,3})){1,2})*",      "aaaaaaaaaa", 0,10, 0,10, 5,10, 5,7, 7,10, 7,10);
    T6("((((aaa?)(aaa){1,3})){1,2})*",      "aaaaaaaaaa", 0,10, 0,10, 5,10, 5,10, 5,7, 7,10);
    T7("((((aaa?)((a){3,3}){1,3})){1,2})*", "aaaaaaaaaa", 0,10, 0,10, 5,10, 5,10, 5,7, 7,10, 9,10);

    T2("(a|aa)*", "",           0,0,  -1,-1);
    T2("(a|aa)*", "a",          0,1,  0,1);
    T2("(a|aa)*", "aa",         0,2,  0,2);
    T2("(a|aa)*", "aaa",        0,3,  2,3);
    T2("(a|aa)*", "aaaa",       0,4,  2,4);
    T2("(a|aa)*", "aaaaa",      0,5,  4,5);
    T2("(a|aa)*", "aaaaaa",     0,6,  4,6);
    T2("(a|aa)*", "aaaaaaa",    0,7,  6,7);
    T2("(a|aa)*", "aaaaaaaa",   0,8,  6,8);
    T2("(a|aa)*", "aaaaaaaaa",  0,9,  8,9);
    T2("(a|aa)*", "aaaaaaaaaa", 0,10, 8,10);
    T2("(aa|a)*", "",           0,0,  -1,-1);
    T2("(aa|a)*", "a",          0,1,  0,1);
    T2("(aa|a)*", "aa",         0,2,  0,2);
    T2("(aa|a)*", "aaa",        0,3,  2,3);
    T2("(aa|a)*", "aaaa",       0,4,  2,4);
    T2("(aa|a)*", "aaaaa",      0,5,  4,5);
    T2("(aa|a)*", "aaaaaa",     0,6,  4,6);
    T2("(aa|a)*", "aaaaaaa",    0,7,  6,7);
    T2("(aa|a)*", "aaaaaaaa",   0,8,  6,8);
    T2("(aa|a)*", "aaaaaaaaa",  0,9,  8,9);
    T2("(aa|a)*", "aaaaaaaaaa", 0,10, 8,10);

    T2("(aaa|aa)*", "aaaaaaaaaa",        0,10, 8,10);
    T2("(aa|aaa)*", "aaaaaaaaaa",        0,10, 8,10);

    T3("((a*)*)*",                           "",            0,0, 0,0, 0,0);

    T2("(y?){0,2}",                          "",            0,0, 0,0);
    T3("((y?){2,3}){2}",                     "yyyyy",       0,5, 3,5, 4,5);
    T3("((y?){2,3}){2,3}",                   "yyyyy",       0,5, 3,5, 4,5);
    T3("((y?){2,3})*",                       "yyyyy",       0,5, 3,5, 4,5);
    T3("((y?){3}){2}",                       "yyyyy",       0,5, 3,5, 5,5);
    T3("((y?){3}){2,3}",                     "yyyyy",       0,5, 3,5, 5,5);
    T3("((y?){3})*",                         "yyyyy",       0,5, 3,5, 5,5);
    T3("((y?)*){2}",                         "yyyyy",       0,5, 5,5, 5,5);
    T3("((y?)*){2,3}",                       "yyyyy",       0,5, 5,5, 5,5);
    T3("((y?)*)*",                           "yyyyy",       0,5, 0,5, 4,5);

    T4("((a)(b)?)*",                         "aba",         0,3, 2,3, 2,3, -1,-1);
    T4("((a)|(b))*",                         "ba",          0,2, 1,2, 1,2, -1,-1);
    T4("((a)|(b))*",                         "ab",          0,2, 1,2, -1,-1, 1,2);
    T4("((a?)|(b?))*",                       "ab",          0,2, 1,2, -1,-1, 1,2);
    T4("((a?)|(b?))*",                       "ba",          0,2, 1,2, 1,2, -1,-1);
    if (!((flags & REG_BACKWARD) && !(flags & REG_GTOP))) {
        T4("((a?)|(b?)){2,3}",               "ab",          0,2, 1,2, -1,-1, 1,2);
    }
    T4("((a?)|(b?)){3}",                     "ab",          0,2, 2,2, 2,2, -1,-1);
    T1("y{3}",                               "yyy",         0,3);
    T1("y{0,2}",                             "",            0,0);
    T1("y{0,2}",                             "y",           0,1);
    T1("y{0,2}",                             "yy",          0,2);
    T2("(y){3}",                             "yyy",         0,3, 2,3);
    T2("(y){0,2}",                           "",            0,0, -1,-1);
    T2("(y){0,2}",                           "y",           0,1, 0,1);
    T2("(y){0,2}",                           "yy",          0,2, 1,2);
    T2("()",                                 "",            0,0, 0,0);
    T2("(){2}",                              "",            0,0, 0,0);
    T2("(){0,2}",                            "",            0,0, 0,0);
    T4("(((){0,30}){0,30}){0,30}",           "",            0,0, 0,0, 0,0, 0,0);
    T2("(y?){2}",                            "y",           0,1, 1,1);

    T1("a",        "a",    0,1);
    T2("(a)",      "a",    0,1, 0,1);
    T2("(a*)",     "aaa",  0,3, 0,3);
    T3("(a*)(b*)", "aabb", 0,4, 0,2, 2,4);
    T3("(a*)(a*)", "aa",   0,2, 0,2, 2,2);
    T2("(a|aa)*",  "aa",   0,2, 0,2);
    T3("(a)|(a)",  "a",    0,1, 0,1, -1,-1);
    T3("(a)*(a)*", "a",    0,1, 0,1, -1,-1);

    T1("[a]",      "a",    0,1);
    T0("[a]",      "b");
    T0("[^a]",     "a");
    T1("[^a]",     "b",    0,1);
    T1("[ac]*",    "ac",   0,2);
    T1("[a-c]*",   "abc",  0,3);
    T1("[]]",      "]",    0,1);
    T0("[^]]",     "]");
    T1("[^]]",     "a",    0,1);
    T1("[-]",      "-",    0,1);
    T1("[]-]*",    "]-",   0,2);
    T1("[-a]*",    "-a",   0,2);
    T1("[a-]*",    "-a",   0,2);
    T1("[-a-]*",   "-a",   0,2);

    // basic
    T3("(..)*(...)*",              "a",           0,0, -1,-1, -1,-1);
    T3("(..)*(...)*",              "abcd",        0,4, 2,4, -1,-1);
    T3("(ab|a)(bc|c)",             "abc",         0,3, 0,2, 2,3);
    T2("(ab)c|abc",                "abc",         0,3, 0,2);
    T4("(a*)(b?)(b+)b{3}",         "aaabbbbbbb",  0,10, 0,3, 3,4, 4,7);
    T4("(a*)(b{0,1})(b{1,})b{3}",  "aaabbbbbbb",  0,10, 0,3, 3,4, 4,7);
    T3("((a|a)|a)",                "a",           0,1, 0,1, 0,1);
    T3("(a*)(a|aa)",               "aaaa",        0,4, 0,3, 3,4);
    T2("a*(a.|aa)",                "aaaa",        0,4, 2,4);
    T4("a(b)|c(d)|a(e)f",          "aef",         0,3, -1,-1, -1,-1, 1,2);
    T2("(a|b)?.*",                 "b",           0,1, 0,1);
    T3("(a|b)c|a(b|c)",            "ac",          0,2, 0,1, -1,-1);
    T3("(a|b)c|a(b|c)",            "ab",          0,2, -1,-1, 1,2);
    T3("(a|b)*c|(a|ab)*c",         "abc",         0,3, 1,2, -1,-1);
    T3("(.a|.b).*|.*(.a|.b)",      "xa",          0,2, 0,2, -1,-1);
    T2("a?(ab|ba)ab",              "abab",        0,4, 0,2);
    T2("a?(a[c]{0}b|ba)ab",        "abab",        0,4, 0,2);
    T1("ab|abab",                  "abbabab",     0,2);
    T3("(aa|aaa)*|(a|aaaaa)",      "aa",          0,2, 0,2, -1,-1);
    T3("(a.|.a.)*|(a|.a...)",      "aa",          0,2, 0,2, -1,-1);
    T4("(a)(b)(c)",                "abc",         0,3, 0,1, 1,2, 2,3);
    T7("((((((x))))))",            "x",           0,1, 0,1, 0,1, 0,1, 0,1, 0,1, 0,1);
    T7("((((((x))))))*",           "xx",          0,2, 1,2, 1,2, 1,2, 1,2, 1,2, 1,2);
    T2("a?(ab|ba)*",               "ababababababababababababababababababababababababababababababababababababababababa", 0,81, 79,81);
    T1("a*a*a*a*a*b",              "aaaaaaaaab",  0,10);
    T1("a[b]+bc",                  "abbc",        0,4);
    T1("a[b]+bc",                  "abbbbc",      0,6);
    T1("a[b]?bc",                  "abbc",        0,4);
    T1("a[b]?bc",                  "abc",         0,3);
    T1("a[b]?c",                   "abc",         0,3);
    T1("ab|cd",                    "abc",         0,2);
    T1("ab|cd",                    "abcd",        0,2);
    T3("((a))",                    "abc",         0,1, 0,1, 0,1);
    T3("(a)b(c)",                  "abc",         0,3, 0,1, 2,3);
    T1("a*",                       "aaa",         0,3);
    T2("(a*)*",                    "-",           0,0, 0,0);
    T2("(a*)+",                    "-",           0,0, 0,0);
    T2("(a*|b)*",                  "-",           0,0, 0,0);
    T2("(a+|b)*",                  "ab",          0,2, 1,2);
    T2("(a+|b)+",                  "ab",          0,2, 1,2);
    T2("(a+|b)?",                  "ab",          0,1, 0,1);
    T2("([abc])*d",                "abbbcd",      0,6, 4,5);
    T2("([abc])*bcd",              "abcd",        0,4, 0,1);
    T1("a|b|c|d|e",                "e",           0,1);
    T2("(a|b|c|d|e)f",             "ef",          0,2, 0,1);
    T3("((a*|b))*",                "-",           0,0, 0,0, 0,0);
    T2("(ab|a[b]*)bc",             "abc",         0,3, 0,1);
    T2("a([bc]*)c*",               "abc",         0,3, 1,3);
    T3("a([bc]*)(c*d)",            "abcd",        0,4, 1,3, 3,4);
    T3("a([bc]+)(c*d)",            "abcd",        0,4, 1,3, 3,4);
    T3("a([bc]*)(c+d)",            "abcd",        0,4, 1,2, 2,4);
    T1("a[bcd]*dcdcde",            "adcdcde",     0,7);
    T2("(ab|a)b*c",                "abc",         0,3, 0,2);
    T5("((a)(b)c)(d)",             "abcd",        0,4, 0,3, 0,1, 1,2, 3,4);
    T3("(.*)c(.*)",                "abcde",       0,5, 0,2, 3,5);
    T2("a(bc)d",                   "abcd",        0,4, 1,3);
    T2("a+(b|c)*d+",               "aabcdd",      0,6, 3,4);

    // categorize
    T4("(a*)(ab)*(b*)",            "abc",    0,2, 0,1, -1,-1, 1,2);
    T7("((a*)(ab)*)((b*)(a*))",    "aba",    0,3, 0,2, 0,0, 0,2, 2,3, 2,2, 2,3);
    T2("(...?.?)*",                "xxxxxx", 0,6, 4,6);
    T3("(a|ab)(bc|c)",             "abcabc", 0,3, 0,2, 2,3);
    T3("(aba|a*b)(aba|a*b)",       "ababa",  0,5, 0,2, 2,5);
    T2("(a*){2}",                  "xxxxx",  0,0, 0,0);
    T2("(a*)*",                    "a",      0,1, 0,1);
    T2("(aba|a*b)*",               "ababa",  0,5, 2,5);
    T3("(a(b)?)+",                 "aba",    0,3, 2,3, -1,-1);
    T2(".*(.*)",                   "ab",     0,2, 2,2);
    T6("(a?)((ab)?)(b?)a?(ab)?b?", "abab",   0,4, 0,1, 1,1, -1,-1, 1,2, -1,-1);

    // forcedassoc
    T3("(a|ab)(c|bcd)",       "abcd", 0,4, 0,1, 1,4);
    T3("(a|ab)(bcd|c)",       "abcd", 0,4, 0,1, 1,4);
    T3("(ab|a)(c|bcd)",       "abcd", 0,4, 0,1, 1,4);
    T3("(ab|a)(bcd|c)",       "abcd", 0,4, 0,1, 1,4);
    T5("((a|ab)(c|bcd))(d*)", "abcd", 0,4, 0,4, 0,1, 1,4, 4,4);
    T5("((a|ab)(bcd|c))(d*)", "abcd", 0,4, 0,4, 0,1, 1,4, 4,4);
    T5("((ab|a)(c|bcd))(d*)", "abcd", 0,4, 0,4, 0,1, 1,4, 4,4);
    T5("((ab|a)(bcd|c))(d*)", "abcd", 0,4, 0,4, 0,1, 1,4, 4,4);
    T5("(a|ab)((c|bcd)(d*))", "abcd", 0,4, 0,2, 2,4, 2,3, 3,4);
    T5("(a|ab)((bcd|c)(d*))", "abcd", 0,4, 0,2, 2,4, 2,3, 3,4);
    T5("(ab|a)((c|bcd)(d*))", "abcd", 0,4, 0,2, 2,4, 2,3, 3,4);
    T5("(ab|a)((bcd|c)(d*))", "abcd", 0,4, 0,2, 2,4, 2,3, 3,4);
    T3("(a*)(b|abc)",         "abc",  0,3, 0,0, 0,3);
    T3("(a*)(abc|b)",         "abc",  0,3, 0,0, 0,3);
    T5("((a*)(b|abc))(c*)",   "abc",  0,3, 0,3, 0,0, 0,3, 3,3);
    T5("((a*)(abc|b))(c*)",   "abc",  0,3, 0,3, 0,0, 0,3, 3,3);
    T5("(a*)((b|abc)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T5("(a*)((abc|b)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T3("(a*)(b|abc)",         "abc",  0,3, 0,0, 0,3);
    T3("(a*)(abc|b)",         "abc",  0,3, 0,0, 0,3);
    T5("((a*)(b|abc))(c*)",   "abc",  0,3, 0,3, 0,0, 0,3, 3,3);
    T5("((a*)(abc|b))(c*)",   "abc",  0,3, 0,3, 0,0, 0,3, 3,3);
    T5("(a*)((b|abc)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T5("(a*)((abc|b)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T2("(a|ab)",              "ab",   0,2, 0,2);
    T2("(ab|a)",              "ab",   0,2, 0,2);
    T3("(a|ab)(b*)",          "ab",   0,2, 0,2, 2,2);
    T3("(ab|a)(b*)",          "ab",   0,2, 0,2, 2,2);

    // glennfowler
    T4("(a?)((ab)?)",                    "ab",      0,2, 0,0, 0,2, 0,2);
    T5("(a?)((ab)?)(b?)",                "ab",      0,2, 0,1, 1,1, -1,-1, 1,2);
    T6("((a?)((ab)?))(b?)",              "ab",      0,2, 0,2, 0,0, 0,2, 0,2, 2,2);
    T6("(a?)(((ab)?)(b?))",              "ab",      0,2, 0,1, 1,2, 1,1, -1,-1, 1,2);
    T2("(.?)",                           "x",       0,1, 0,1);
    T2("(.?){1}",                        "x",       0,1, 0,1);
    T3("(.?)(.?)",                       "x",       0,1, 0,1, 1,1);
    T2("(.?){2}",                        "x",       0,1, 1,1);
    T2("(.?)*",                          "x",       0,1, 0,1);
    T2("(.?.?)",                         "xxx",     0,2, 0,2);
    T2("(.?.?){1}",                      "xxx",     0,2, 0,2);
    T3("(.?.?)(.?.?)",                   "xxx",     0,3, 0,2, 2,3);
    T2("(.?.?){2}",                      "xxx",     0,3, 2,3);
    T4("(.?.?)(.?.?)(.?.?)",             "xxx",     0,3, 0,2, 2,3, 3,3);
    T2("(.?.?){3}",                      "xxx",     0,3, 3,3);
    T2("(.?.?)*",                        "xx",      0,2, 0,2);
    T2("(.?.?)*",                        "xxx",     0,3, 2,3);
    T2("(.?.?)*",                        "xxxx",    0,4, 2,4);
    T4("a?((ab)?)(b?)",                  "ab",      0,2, 1,1, -1,-1, 1,2);
    T4("(a?)((ab)?)b?",                  "ab",      0,2, 0,1, 1,1, -1,-1);
    T3("a?((ab)?)b?",                    "ab",      0,2, 1,1, -1,-1);
    T2("(a*){2}",                        "xxxxx",   0,0, 0,0);
    T3("(ab?)(b?a)",                     "aba",     0,3, 0,2, 2,3);
    T3("(a|ab)(ba|a)",                   "aba",     0,3, 0,2, 2,3);
    T2("(a|ab|ba)",                      "aba",     0,2, 0,2);
    T3("(a|ab|ba)(a|ab|ba)",             "aba",     0,3, 0,2, 2,3);
    T2("(a|ab|ba)*",                     "aba",     0,3, 2,3);
    T2("(aba|a*b)",                      "ababa",   0,3, 0,3);
    T3("(aba|a*b)(aba|a*b)",             "ababa",   0,5, 0,2, 2,5);
    T0("(aba|a*b)(aba|a*b)(aba|a*b)",    "ababa");
    T2("(aba|a*b)*",                     "ababa",   0,5, 2,5);
    T2("(aba|ab|a)",                     "ababa",   0,3, 0,3);
    T3("(aba|ab|a)(aba|ab|a)",           "ababa",   0,5, 0,2, 2,5);
    T4("(aba|ab|a)(aba|ab|a)(aba|ab|a)", "ababa",   0,5, 0,2, 2,4, 4,5);
    T2("(aba|ab|a)*",                    "ababa",   0,5, 2,5);
    T3("(a(b)?)",                        "aba",     0,2, 0,2, 1,2);
    T5("(a(b)?)(a(b)?)",                 "aba",     0,3, 0,2, 1,2, 2,3, -1,-1);
    T3("(a(b)?)+",                       "aba",     0,3, 2,3, -1,-1);
    T3("(.*)(.*)",                       "xx",      0,2, 0,2, 2,2);
    T2(".*(.*)",                         "xx",      0,2, 2,2);
    T2("(a.*z|b.*y)",                    "azbazby", 0,5, 0,5);
    T3("(a.*z|b.*y)(a.*z|b.*y)",         "azbazby", 0,7, 0,5, 5,7);
    T2("(a.*z|b.*y)*",                   "azbazby", 0,7, 5,7);
    T3("(.|..)(.*)",                     "ab",      0,2, 0,2, 2,2);
    T4("((..)*(...)*)",                  "xxx",     0,3, 0,3, -1,-1, 0,3);
    T7("((..)*(...)*)((..)*(...)*)",     "xxx",     0,3, 0,3, -1,-1, 0,3, 3,3, -1,-1, -1,-1);
    T4("((..)*(...)*)*",                 "xxx",     0,3, 0,3, -1,-1, 0,3);

    // nullsubexpr
    T2("(a*)*",      "a",        0,1, 0,1);
    T2("(a*)*",      "x",        0,0, 0,0);
    T2("(a*)*",      "aaaaaa",   0,6, 0,6);
    T2("(a*)*",      "aaaaaax",  0,6, 0,6);
    T2("(a*)+",      "a",        0,1, 0,1);
    T2("(a*)+",      "x",        0,0, 0,0);
    T2("(a*)+",      "aaaaaa",   0,6, 0,6);
    T2("(a*)+",      "aaaaaax",  0,6, 0,6);
    T2("(a+)*",      "a",        0,1, 0,1);
    T2("(a+)*",      "x",        0,0, -1,-1);
    T2("(a+)*",      "aaaaaa",   0,6, 0,6);
    T2("(a+)*",      "aaaaaax",  0,6, 0,6);
    T2("(a+)+",      "a",        0,1, 0,1);
    T0("(a+)+",      "x");
    T2("(a+)+",      "aaaaaa",   0,6, 0,6);
    T2("(a+)+",      "aaaaaax",  0,6, 0,6);
    T2("([a]*)*",    "a",        0,1, 0,1);
    T2("([a]*)*",    "x",        0,0, 0,0);
    T2("([a]*)*",    "aaaaaa",   0,6, 0,6);
    T2("([a]*)*",    "aaaaaax",  0,6, 0,6);
    T2("([a]*)+",    "a",        0,1, 0,1);
    T2("([a]*)+",    "x",        0,0, 0,0);
    T2("([a]*)+",    "aaaaaa",   0,6, 0,6);
    T2("([a]*)+",    "aaaaaax",  0,6, 0,6);
    T2("([^b]*)*",   "a",        0,1, 0,1);
    T2("([^b]*)*",   "b",        0,0, 0,0);
    T2("([^b]*)*",   "aaaaaa",   0,6, 0,6);
    T2("([^b]*)*",   "aaaaaab",  0,6, 0,6);
    T2("([ab]*)*",   "a",        0,1, 0,1);
    T2("([ab]*)*",   "aaaaaa",   0,6, 0,6);
    T2("([ab]*)*",   "ababab",   0,6, 0,6);
    T2("([ab]*)*",   "bababa",   0,6, 0,6);
    T2("([ab]*)*",   "b",        0,1, 0,1);
    T2("([ab]*)*",   "bbbbbb",   0,6, 0,6);
    T2("([ab]*)*",   "aaaabcde", 0,5, 0,5);
    T2("([^a]*)*",   "b",        0,1, 0,1);
    T2("([^a]*)*",   "bbbbbb",   0,6, 0,6);
    T2("([^a]*)*",   "aaaaaa",   0,0, 0,0);
    T2("([^ab]*)*",  "ccccxx",   0,6, 0,6);
    T2("([^ab]*)*",  "ababab",   0,0, 0,0);
    T3("((z)+|a)*",  "zabcde",   0,2, 1,2, -1,-1);
    T2("(a)",        "aaa",      0,1, 0,1);
    T3("(a*)*(x)",   "x",        0,1, 0,0, 0,1);
    T3("(a*)*(x)",   "ax",       0,2, 0,1, 1,2);
    T3("(a*)*(x)",   "axa",      0,2, 0,1, 1,2);
    T3("(a*)+(x)",   "x",        0,1, 0,0, 0,1);
    T3("(a*)+(x)",   "ax",       0,2, 0,1, 1,2);
    T3("(a*)+(x)",   "axa",      0,2, 0,1, 1,2);
    T3("(a*){2}(x)", "x",        0,1, 0,0, 0,1);
    T3("(a*){2}(x)", "ax",       0,2, 1,1, 1,2);
    T3("(a*){2}(x)", "axa",      0,2, 1,1, 1,2);

    T4("(()|.)(b)",     "ab",    0,2, 0,1, -1,-1, 1,2);
    T4("(()|[ab])(b)",  "ab",    0,2, 0,1, -1,-1, 1,2);
    T3("(()|[ab])+b",   "aaab",  0,4, 2,3, -1,-1);
    T4("(.|())(b)",     "ab",    0,2, 0,1, -1,-1, 1,2);
    T4("([ab]|())(b)",  "ab",    0,2, 0,1, -1,-1, 1,2);
    T3("([ab]|())+b",   "aaab",  0,4, 2,3, -1,-1);
    T3("(.?)(b)",       "ab",    0,2, 0,1, 1,2);

    // other
    T2("(a|aa)*",                            "aaa",         0,3, 2,3);
    T2("(a|aa)*",                            "aaaa",        0,4, 2,4);
    T2("(aa|a)*",                            "aaa",         0,3, 2,3);
    T2("(aa|a)*",                            "aaaa",        0,4, 2,4);
    T2("a|(a)",                              "a",           0,1, -1,-1);
    T2("(a)|a",                              "a",           0,1, 0,1);
    T3("(b)a|b(a)",                          "ba",          0,2, 0,1, -1,-1);
    T3("b(a)|(b)a",                          "ba",          0,2, 1,2, -1,-1);
    T2("a*|(a|aa)*",                         "aa",          0,2, -1,-1);
    T2("(a|aa)*|a*",                         "aa",          0,2, 0,2);
    T2("(aa*|aaa*)*",                        "aaaaaa",      0,6, 0,6);
    T3("(aa*|aaa*)(aa*|aaa*)",               "aaaaaa",      0,6, 0,5, 5,6);
    T2("(aa*|aaa*){2}",                      "aaaaaa",      0,6, 5,6);
    T7("((aa)*|(aaa)*)((aa)*|(aaa)*)",       "aaaaaa",      0,6, 0,6, 4,6, -1,-1, 6,6, -1,-1, -1,-1);
    T4("((aa)*|(aaa)*){2}",                  "aaaaaa",      0,6, 6,6, -1,-1, -1,-1);
    T3("(aa)*|(aaa)*",                       "aaaaaa",      0,6, 4,6, -1,-1);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XY",          0,2, 1,2);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XabY",        0,4, 3,4);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XababY",      0,6, 4,6);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XabababY",    0,8, 7,8);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XababababY",  0,10, 8,10);
    T0("(y){2}",                             "");
    T0("(y){2}",                             "y");
    T2("(y){2}",                             "yy",          0,2, 1,2);
    T2("(y){0,2}",                           "",            0,0, -1,-1);
    T2("(y){0,2}",                           "y",           0,1, 0,1);
    T2("(y){0,2}",                           "yy",          0,2, 1,2);
    T0("(y){1,2}",                           "");
    T2("(y){1,2}",                           "y",           0,1, 0,1);
    T2("(y){1,2}",                           "yy",          0,2, 1,2);
    T0("(y){1,2}y",                          "");
    T0("(y){1,2}y",                          "y");
    T2("(y){1,2}y",                          "yy",          0,2, 0,1);
    T2("(y){1,2}y",                          "yyy",         0,3, 1,2);
    T0("(y){1,2}y?",                         "");
    T2("(y){1,2}y?",                         "y",           0,1, 0,1);
    T2("(y){1,2}y?",                         "yy",          0,2, 1,2);
    T2("(y){1,2}y?",                         "yyy",         0,3, 1,2);
    T0("(y){2,}",                            "");
    T0("(y){2,}",                            "y");
    T2("(y){2,}",                            "yy",          0,2, 1,2);
    T2("(y){2,}",                            "yyy",         0,3, 2,3);
    T2("(y?){2}",                            "",            0,0, 0,0);
    T2("(y?){2}",                            "y",           0,1, 1,1);
    T2("(y?){2}",                            "yy",          0,2, 1,2);
    T2("(y?){0,2}",                          "",            0,0, 0,0);
    T3("(y?){0,2}|(y?)",                     "y",           0,1, 0,1, -1,-1);
    T2("(y?){0,2}",                          "y",           0,1, 0,1);
    T2("(y?){0,2}",                          "yy",          0,2, 1,2);
    T2("(y?){1,2}",                          "",            0,0, 0,0);
    T2("(y?){1,2}",                          "y",           0,1, 0,1);
    T2("(y?){1,2}",                          "yy",          0,2, 1,2);
    T0("(y?){1,2}y",                         "");
    T2("(y?){1,2}y",                         "y",           0,1, 0,0);
    T2("(y?){1,2}y",                         "yy",          0,2, 0,1);
    T2("(y?){1,2}y",                         "yyy",         0,3, 1,2);
    T2("(y?){1,2}y?",                        "",            0,0, 0,0);
    T2("(y?){1,2}y?",                        "y",           0,1, 0,1);
    T2("(y?){1,2}y?",                        "yy",          0,2, 1,2);
    T2("(y?){1,2}y?",                        "yyy",         0,3, 1,2);
    T2("(y?){2,}",                           "",            0,0, 0,0);
    T2("(y?){2,}",                           "y",           0,1, 1,1);
    T2("(y?){2,}",                           "yy",          0,2, 1,2);
    T2("(y?){2,}",                           "yyy",         0,3, 2,3);
    T3("(y|(x?)){1,3}",                      "y",           0,1, 0,1, -1,-1);
    T2("(y[y]?){3}",                         "yyyy",        0,4, 3,4);

    // repetition
    T0("((..)|(.))",                         "");
    T0("((..)|(.))((..)|(.))",               "");
    T0("((..)|(.))((..)|(.))((..)|(.))",     "");
    T0("((..)|(.)){1}",                      "");
    T0("((..)|(.)){2}",                      "");
    T0("((..)|(.)){3}",                      "");
    T4("((..)|(.))*",                        "",            0,0, -1,-1, -1,-1, -1,-1);
    T4("((..)|(.))",                         "a",           0,1, 0,1, -1,-1, 0,1);
    T0("((..)|(.))((..)|(.))",               "a");
    T0("((..)|(.))((..)|(.))((..)|(.))",     "a");
    T4("((..)|(.)){1}",                      "a",           0,1, 0,1, -1,-1, 0,1);
    T0("((..)|(.)){2}",                      "a");
    T0("((..)|(.)){3}",                      "a");
    T4("((..)|(.))*",                        "a",           0,1, 0,1, -1,-1, 0,1);
    T4("((..)|(.))",                         "aa",          0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aa",          0,2, 0,1, -1,-1, 0,1, 1,2, -1,-1, 1,2);
    T0("((..)|(.))((..)|(.))((..)|(.))",     "aa");
    T4("((..)|(.)){1}",                      "aa",          0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aa",          0,2, 1,2, -1,-1, 1,2);
    T0("((..)|(.)){3}",                      "aa");
    T4("((..)|(.))*",                        "aa",          0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.))",                         "aaa",         0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaa",         0,3, 0,2, 0,2, -1,-1, 2,3, -1,-1, 2,3);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaa",         0,3, 0,1, -1,-1, 0,1, 1,2, -1,-1, 1,2, 2,3, -1,-1, 2,3);
    T4("((..)|(.)){1}",                      "aaa",         0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaa",         0,3, 2,3, -1,-1, 2,3);
    T4("((..)|(.)){3}",                      "aaa",         0,3, 2,3, -1,-1, 2,3);
    T4("((..)|(.))*",                        "aaa",         0,3, 2,3, -1,-1, 2,3);
    T4("((..)|(.))",                         "aaaa",        0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaaa",        0,4, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaaa",        0,4, 0,2, 0,2, -1,-1, 2,3, -1,-1, 2,3, 3,4, -1,-1, 3,4);
    T4("((..)|(.)){1}",                      "aaaa",        0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaaa",        0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.)){3}",                      "aaaa",        0,4, 3,4, -1,-1, 3,4);
    T4("((..)|(.))*",                        "aaaa",        0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.))",                         "aaaaa",       0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaaaa",       0,4, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaaaa",       0,5, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1, 4,5, -1,-1, 4,5);
    T4("((..)|(.)){1}",                      "aaaaa",       0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaaaa",       0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.)){3}",                      "aaaaa",       0,5, 4,5, -1,-1, 4,5);
    T4("((..)|(.))*",                        "aaaaa",       0,5, 4,5, -1,-1, 4,5);
    T4("((..)|(.))",                         "aaaaaa",      0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaaaaa",      0,4, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaaaaa",      0,6, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1, 4,6, 4,6, -1,-1);
    T4("((..)|(.)){1}",                      "aaaaaa",      0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaaaaa",      0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.)){3}",                      "aaaaaa",      0,6, 4,6, 4,6, -1,-1);
    T4("((..)|(.))*",                        "aaaaaa",      0,6, 4,6, 4,6, -1,-1);
    T2("X(.?){0,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){1,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){2,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){3,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){4,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){5,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){6,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){7,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){8,}Y",                         "X1234567Y",   0,9, 8,8);
    T2("X(.?){0,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){1,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){2,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){3,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){4,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){5,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){6,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){7,8}Y",                        "X1234567Y",   0,9, 7,8);
    T2("X(.?){8,8}Y",                        "X1234567Y",   0,9, 8,8);
    T3("(a|ab|c|bcd){0,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){1,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){2,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){3,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T0("(a|ab|c|bcd){4,}(d*)",               "ababcd");
    T3("(a|ab|c|bcd){0,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){1,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){2,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){3,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T0("(a|ab|c|bcd){4,10}(d*)",             "ababcd");
    T3("(a|ab|c|bcd)*(d*)",                  "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd)+(d*)",                  "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){0,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){1,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){2,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){3,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T0("(ab|a|c|bcd){4,}(d*)",               "ababcd");
    T3("(ab|a|c|bcd){0,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){1,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){2,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){3,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T0("(ab|a|c|bcd){4,10}(d*)",             "ababcd");
    T3("(ab|a|c|bcd)*(d*)",                  "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd)+(d*)",                  "ababcd",      0,6, 3,6, 6,6);

    // rightassoc
    T4("(a|ab)(c|bcd)(d*)",                  "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(a|ab)(bcd|c)(d*)",                  "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(ab|a)(c|bcd)(d*)",                  "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(ab|a)(bcd|c)(d*)",                  "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(a*)(b|abc)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a*)(abc|b)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a*)(b|abc)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a*)(abc|b)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a|ab)(c|bcd)(d|.*)",                "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(a|ab)(bcd|c)(d|.*)",                "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(ab|a)(c|bcd)(d|.*)",                "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(ab|a)(bcd|c)(d|.*)",                "abcd",        0,4, 0,2, 2,3, 3,4);

    if (!(flags & REG_NFA)) {
        T3("((a?){1,300})*", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0,50, 0,50, 49,50);
    }
    else if (!(flags & (REG_SLOWPREC | REG_KUKLEWICZ))) {
        T3("((a?){1,1000})*", "aaaa", 0,4, 0,4, 3,4);

        T8("(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "", 0,0, 0,0, 0,0, 0,0, 0,0, -1,-1, 0,0, 0,0);
        if (!((flags & REG_BACKWARD) && !(flags & REG_GTOP))) {
            // expected failures for Cox algorithm
            T8("(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "aaa", 0,3, 0,3, 0,3, 0,3, 0,3, -1,-1, 0,3, 2,3);
            T8("(((((aa)|((a?)*))*){0,10}){0,10}){0,10}", "aaaaa", 0,5, 0,5, 0,5, 0,5, 0,5, -1,-1, 0,5, 4,5);
        }
    }

    T6("((((a?)+)|(aa))+)", "aaa", 0,3, 0,3, 0,3, 0,3, 2,3, -1,-1);
    T6("(((aa)|((a?)+))+)", "aaa", 0,3, 0,3, 0,3, -1,-1, 0,3, 2,3);
    T4("((a?){1,2}|(a)*)*", "aaaa", 0,4, 0,4, -1,-1, 3,4);
    T5("(((a?){2,3}|(a)*))*", "aaaaa", 0,5, 0,5, 0,5, -1,-1, 4,5);
    T5("(((a?)|(a?a?))+)", "aa", 0,2, 0,2, 0,2, -1,-1, 0,2);
    T9("((((a)*))*|((((a))*))+)*", "aa", 0,2, 0,2, 0,2, 0,2, 1,2, -1,-1, -1,-1, -1,-1, -1,-1);
    T6("(((a)*)*|((a)*)+)*", "aa", 0,2, 0,2, 0,2, 1,2, -1,-1, -1,-1);
    T7("(((a)+)|(((a)+)?))+", "aa", 0,2, 0,2, 0,2, 1,2, -1,-1, -1,-1, -1,-1);
    T3("(a*|(a)*)*", "aa", 0,2, 0,2, -1,-1);

    return e;
}

static int test_all_leftmost(int flags)
{
    int e = 0;

    T1("a",        "a",    0,1);
    T2("(a)",      "a",    0,1, 0,1);
    T2("(a*)",     "aaa",  0,3, 0,3);
    T3("(a*)(b*)", "aabb", 0,4, 0,2, 2,4);
    T3("(a*)(a*)", "aa",   0,2, 0,2, 2,2);
    T2("(a|aa)*",  "aa",   0,2, 1,2);
    T3("(a)|(a)",  "a",    0,1, 0,1, -1,-1);
    T3("(a)*(a)*", "a",    0,1, 0,1, -1,-1);

    T1("[a]",      "a",    0,1);
    T0("[a]",      "b");
    T0("[^a]",     "a");
    T1("[^a]",     "b",    0,1);
    T1("[ac]*",    "ac",   0,2);
    T1("[a-c]*",   "abc",  0,3);
    T1("[]]",      "]",    0,1);
    T0("[^]]",     "]");
    T1("[^]]",     "a",    0,1);
    T1("[-]",      "-",    0,1);
    T1("[]-]*",    "]-",   0,2);
    T1("[-a]*",    "-a",   0,2);
    T1("[a-]*",    "-a",   0,2);
    T1("[-a-]*",   "-a",   0,2);

    // basic
    T3("(..)*(...)*",              "a",           0,0, -1,-1, -1,-1);
    T3("(..)*(...)*",              "abcd",        0,4, 2,4, -1,-1);
    T3("(ab|a)(bc|c)",             "abc",         0,3, 0,2, 2,3);
    T2("(ab)c|abc",                "abc",         0,3, 0,2);
    T4("(a*)(b?)(b+)b{3}",         "aaabbbbbbb",  0,10, 0,3, 3,4, 4,7);
    T4("(a*)(b{0,1})(b{1,})b{3}",  "aaabbbbbbb",  0,10, 0,3, 3,4, 4,7);
    T3("((a|a)|a)",                "a",           0,1, 0,1, 0,1);
    T3("(a*)(a|aa)",               "aaaa",        0,4, 0,3, 3,4);
    T2("a*(a.|aa)",                "aaaa",        0,4, 2,4);
    T4("a(b)|c(d)|a(e)f",          "aef",         0,3, -1,-1, -1,-1, 1,2);
    T2("(a|b)?.*",                 "b",           0,1, 0,1);
    T3("(a|b)c|a(b|c)",            "ac",          0,2, 0,1, -1,-1);
    T3("(a|b)c|a(b|c)",            "ab",          0,2, -1,-1, 1,2);
    T3("(a|b)*c|(a|ab)*c",         "abc",         0,3, 1,2, -1,-1);
    T3("(.a|.b).*|.*(.a|.b)",      "xa",          0,2, 0,2, -1,-1);
    T2("a?(ab|ba)ab",              "abab",        0,4, 0,2);
    T2("a?(a[c]{0}b|ba)ab",        "abab",        0,4, 0,2);
    T1("ab|abab",                  "abbabab",     0,2);
    T3("(aa|aaa)*|(a|aaaaa)",      "aa",          0,2, 0,2, -1,-1);
    T3("(a.|.a.)*|(a|.a...)",      "aa",          0,2, 0,2, -1,-1);
    T4("(a)(b)(c)",                "abc",         0,3, 0,1, 1,2, 2,3);
    T7("((((((x))))))",            "x",           0,1, 0,1, 0,1, 0,1, 0,1, 0,1, 0,1);
    T7("((((((x))))))*",           "xx",          0,2, 1,2, 1,2, 1,2, 1,2, 1,2, 1,2);
    T2("a?(ab|ba)*",               "ababababababababababababababababababababababababababababababababababababababababa", 0,81, 79,81);
    T1("a*a*a*a*a*b",              "aaaaaaaaab",  0,10);
    T1("a[b]+bc",                  "abbc",        0,4);
    T1("a[b]+bc",                  "abbbbc",      0,6);
    T1("a[b]?bc",                  "abbc",        0,4);
    T1("a[b]?bc",                  "abc",         0,3);
    T1("a[b]?c",                   "abc",         0,3);
    T1("ab|cd",                    "abc",         0,2);
    T1("ab|cd",                    "abcd",        0,2);
    T3("((a))",                    "abc",         0,1, 0,1, 0,1);
    T3("(a)b(c)",                  "abc",         0,3, 0,1, 2,3);
    T1("a*",                       "aaa",         0,3);
    T2("(a*)*",                    "-",           0,0, 0,0);
    T2("(a*)+",                    "-",           0,0, 0,0);
    T2("(a*|b)*",                  "-",           0,0, 0,0);
    T2("(a+|b)*",                  "ab",          0,2, 1,2);
    T2("(a+|b)+",                  "ab",          0,2, 1,2);
    T2("(a+|b)?",                  "ab",          0,1, 0,1);
    T2("([abc])*d",                "abbbcd",      0,6, 4,5);
    T2("([abc])*bcd",              "abcd",        0,4, 0,1);
    T1("a|b|c|d|e",                "e",           0,1);
    T2("(a|b|c|d|e)f",             "ef",          0,2, 0,1);
    T3("((a*|b))*",                "-",           0,0, 0,0, 0,0);
    T2("(ab|a[b]*)bc",             "abc",         0,3, 0,1);
    T2("a([bc]*)c*",               "abc",         0,3, 1,3);
    T3("a([bc]*)(c*d)",            "abcd",        0,4, 1,3, 3,4);
    T3("a([bc]+)(c*d)",            "abcd",        0,4, 1,3, 3,4);
    T3("a([bc]*)(c+d)",            "abcd",        0,4, 1,2, 2,4);
    T1("a[bcd]*dcdcde",            "adcdcde",     0,7);
    T2("(ab|a)b*c",                "abc",         0,3, 0,2);
    T5("((a)(b)c)(d)",             "abcd",        0,4, 0,3, 0,1, 1,2, 3,4);
    T3("(.*)c(.*)",                "abcde",       0,5, 0,2, 3,5);
    T2("a(bc)d",                   "abcd",        0,4, 1,3);
    T2("a+(b|c)*d+",               "aabcdd",      0,6, 3,4);

    // categorize
    T4("(a*)(ab)*(b*)",            "abc",    0,2, 0,1, -1,-1, 1,2);
    T7("((a*)(ab)*)((b*)(a*))",    "aba",    0,3, 0,1, 0,1, -1,-1, 1,3, 1,2, 2,3);
    T2("(...?.?)*",                "xxxxxx", 0,6, 4,6);
    T3("(a|ab)(bc|c)",             "abcabc", 0,3, 0,1, 1,3);
    T3("(aba|a*b)(aba|a*b)",       "ababa",  0,5, 0,2, 2,5);
    T2("(a*){2}",                  "xxxxx",  0,0, 0,0);
    T2("(a*)*",                    "a",      0,1, 0,1);
    T2("(aba|a*b)*",               "ababa",  0,5, 2,5);
    T3("(a(b)?)+",                 "aba",    0,3, 2,3, -1,-1);
    T2(".*(.*)",                   "ab",     0,2, 2,2);
    T6("(a?)((ab)?)(b?)a?(ab)?b?", "abab",   0,4, 0,1, 1,1, -1,-1, 1,2, -1,-1);

    // forcedassoc
    T3("(a|ab)(c|bcd)",       "abcd", 0,4, 0,1, 1,4);
    T3("(a|ab)(bcd|c)",       "abcd", 0,4, 0,1, 1,4);
    T3("(ab|a)(c|bcd)",       "abcd", 0,4, 0,1, 1,4);
    T3("(ab|a)(bcd|c)",       "abcd", 0,4, 0,1, 1,4);
    T5("((a|ab)(c|bcd))(d*)", "abcd", 0,4, 0,4, 0,1, 1,4, 4,4);
    T5("((a|ab)(bcd|c))(d*)", "abcd", 0,4, 0,4, 0,1, 1,4, 4,4);
    T5("((ab|a)(c|bcd))(d*)", "abcd", 0,4, 0,3, 0,2, 2,3, 3,4);
    T5("((ab|a)(bcd|c))(d*)", "abcd", 0,4, 0,3, 0,2, 2,3, 3,4);
    T5("(a|ab)((c|bcd)(d*))", "abcd", 0,4, 0,1, 1,4, 1,4, 4,4);
    T5("(a|ab)((bcd|c)(d*))", "abcd", 0,4, 0,1, 1,4, 1,4, 4,4);
    T5("(ab|a)((c|bcd)(d*))", "abcd", 0,4, 0,2, 2,4, 2,3, 3,4);
    T5("(ab|a)((bcd|c)(d*))", "abcd", 0,4, 0,2, 2,4, 2,3, 3,4);
    T3("(a*)(b|abc)",         "abc",  0,3, 0,0, 0,3);
    T3("(a*)(abc|b)",         "abc",  0,3, 0,0, 0,3);
    T5("((a*)(b|abc))(c*)",   "abc",  0,3, 0,2, 0,1, 1,2, 2,3);
    T5("((a*)(abc|b))(c*)",   "abc",  0,3, 0,2, 0,1, 1,2, 2,3);
    T5("(a*)((b|abc)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T5("(a*)((abc|b)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T3("(a*)(b|abc)",         "abc",  0,3, 0,0, 0,3);
    T3("(a*)(abc|b)",         "abc",  0,3, 0,0, 0,3);
    T5("((a*)(b|abc))(c*)",   "abc",  0,3, 0,2, 0,1, 1,2, 2,3);
    T5("((a*)(abc|b))(c*)",   "abc",  0,3, 0,2, 0,1, 1,2, 2,3);
    T5("(a*)((b|abc)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T5("(a*)((abc|b)(c*))",   "abc",  0,3, 0,1, 1,3, 1,2, 2,3);
    T2("(a|ab)",              "ab",   0,2, 0,2);
    T2("(ab|a)",              "ab",   0,2, 0,2);
    T3("(a|ab)(b*)",          "ab",   0,2, 0,1, 1,2);
    T3("(ab|a)(b*)",          "ab",   0,2, 0,2, 2,2);

    // glennfowler
    T4("(a?)((ab)?)",                    "ab",      0,2, 0,0, 0,2, 0,2);
    T5("(a?)((ab)?)(b?)",                "ab",      0,2, 0,1, 1,1, -1,-1, 1,2);
    T6("((a?)((ab)?))(b?)",              "ab",      0,2, 0,1, 0,1, 1,1, -1,-1, 1,2);
    T6("(a?)(((ab)?)(b?))",              "ab",      0,2, 0,1, 1,2, 1,1, -1,-1, 1,2);
    T2("(.?)",                           "x",       0,1, 0,1);
    T2("(.?){1}",                        "x",       0,1, 0,1);
    T3("(.?)(.?)",                       "x",       0,1, 0,1, 1,1);
    T2("(.?){2}",                        "x",       0,1, 1,1);
    T2("(.?)*",                          "x",       0,1, 0,1);
    T2("(.?.?)",                         "xxx",     0,2, 0,2);
    T2("(.?.?){1}",                      "xxx",     0,2, 0,2);
    T3("(.?.?)(.?.?)",                   "xxx",     0,3, 0,2, 2,3);
    T2("(.?.?){2}",                      "xxx",     0,3, 2,3);
    T4("(.?.?)(.?.?)(.?.?)",             "xxx",     0,3, 0,2, 2,3, 3,3);
    T2("(.?.?){3}",                      "xxx",     0,3, 3,3);
    T2("(.?.?)*",                        "xxx",     0,3, 2,3);
    T4("a?((ab)?)(b?)",                  "ab",      0,2, 1,1, -1,-1, 1,2);
    T4("(a?)((ab)?)b?",                  "ab",      0,2, 0,1, 1,1, -1,-1);
    T3("a?((ab)?)b?",                    "ab",      0,2, 1,1, -1,-1);
    T2("(a*){2}",                        "xxxxx",   0,0, 0,0);
    T3("(ab?)(b?a)",                     "aba",     0,3, 0,2, 2,3);
    T3("(a|ab)(ba|a)",                   "aba",     0,3, 0,1, 1,3);
    T2("(a|ab|ba)",                      "aba",     0,2, 0,2);
    T3("(a|ab|ba)(a|ab|ba)",             "aba",     0,3, 0,1, 1,3);
    T2("(a|ab|ba)*",                     "aba",     0,3, 1,3);
    T2("(aba|a*b)",                      "ababa",   0,3, 0,3);
    T3("(aba|a*b)(aba|a*b)",             "ababa",   0,5, 0,2, 2,5);
    T0("(aba|a*b)(aba|a*b)(aba|a*b)",    "ababa");
    T2("(aba|a*b)*",                     "ababa",   0,5, 2,5);
    T2("(aba|ab|a)",                     "ababa",   0,3, 0,3);
    T3("(aba|ab|a)(aba|ab|a)",           "ababa",   0,5, 0,2, 2,5);
    T4("(aba|ab|a)(aba|ab|a)(aba|ab|a)", "ababa",   0,5, 0,2, 2,4, 4,5);
    T2("(aba|ab|a)*",                    "ababa",   0,5, 2,5);
    T3("(a(b)?)",                        "aba",     0,2, 0,2, 1,2);
    T5("(a(b)?)(a(b)?)",                 "aba",     0,3, 0,2, 1,2, 2,3, -1,-1);
    T3("(a(b)?)+",                       "aba",     0,3, 2,3, -1,-1);
    T3("(.*)(.*)",                       "xx",      0,2, 0,2, 2,2);
    T2(".*(.*)",                         "xx",      0,2, 2,2);
    T2("(a.*z|b.*y)",                    "azbazby", 0,5, 0,5);
    T3("(a.*z|b.*y)(a.*z|b.*y)",         "azbazby", 0,7, 0,5, 5,7);
    T2("(a.*z|b.*y)*",                   "azbazby", 0,7, 5,7);
    T3("(.|..)(.*)",                     "ab",      0,2, 0,1, 1,2);
    T4("((..)*(...)*)",                  "xxx",     0,3, 0,3, -1,-1, 0,3);
    T7("((..)*(...)*)((..)*(...)*)",     "xxx",     0,3, 0,3, -1,-1, 0,3, 3,3, -1,-1, -1,-1);
    T4("((..)*(...)*)*",                 "xxx",     0,3, 0,3, -1,-1, 0,3);

    // nullsubexpr
    T2("(a*)*",      "a",        0,1, 0,1);
    T2("(a*)*",      "x",        0,0, 0,0);
    T2("(a*)*",      "aaaaaa",   0,6, 0,6);
    T2("(a*)*",      "aaaaaax",  0,6, 0,6);
    T2("(a*)+",      "a",        0,1, 0,1);
    T2("(a*)+",      "x",        0,0, 0,0);
    T2("(a*)+",      "aaaaaa",   0,6, 0,6);
    T2("(a*)+",      "aaaaaax",  0,6, 0,6);
    T2("(a+)*",      "a",        0,1, 0,1);
    T2("(a+)*",      "x",        0,0, -1,-1);
    T2("(a+)*",      "aaaaaa",   0,6, 0,6);
    T2("(a+)*",      "aaaaaax",  0,6, 0,6);
    T2("(a+)+",      "a",        0,1, 0,1);
    T0("(a+)+",      "x");
    T2("(a+)+",      "aaaaaa",   0,6, 0,6);
    T2("(a+)+",      "aaaaaax",  0,6, 0,6);
    T2("([a]*)*",    "a",        0,1, 0,1);
    T2("([a]*)*",    "x",        0,0, 0,0);
    T2("([a]*)*",    "aaaaaa",   0,6, 0,6);
    T2("([a]*)*",    "aaaaaax",  0,6, 0,6);
    T2("([a]*)+",    "a",        0,1, 0,1);
    T2("([a]*)+",    "x",        0,0, 0,0);
    T2("([a]*)+",    "aaaaaa",   0,6, 0,6);
    T2("([a]*)+",    "aaaaaax",  0,6, 0,6);
    T2("([^b]*)*",   "a",        0,1, 0,1);
    T2("([^b]*)*",   "b",        0,0, 0,0);
    T2("([^b]*)*",   "aaaaaa",   0,6, 0,6);
    T2("([^b]*)*",   "aaaaaab",  0,6, 0,6);
    T2("([ab]*)*",   "a",        0,1, 0,1);
    T2("([ab]*)*",   "aaaaaa",   0,6, 0,6);
    T2("([ab]*)*",   "ababab",   0,6, 0,6);
    T2("([ab]*)*",   "bababa",   0,6, 0,6);
    T2("([ab]*)*",   "b",        0,1, 0,1);
    T2("([ab]*)*",   "bbbbbb",   0,6, 0,6);
    T2("([ab]*)*",   "aaaabcde", 0,5, 0,5);
    T2("([^a]*)*",   "b",        0,1, 0,1);
    T2("([^a]*)*",   "bbbbbb",   0,6, 0,6);
    T2("([^a]*)*",   "aaaaaa",   0,0, 0,0);
    T2("([^ab]*)*",  "ccccxx",   0,6, 0,6);
    T2("([^ab]*)*",  "ababab",   0,0, 0,0);
    T3("((z)+|a)*",  "zabcde",   0,2, 1,2, -1,-1);
    T2("(a)",        "aaa",      0,1, 0,1);
    T3("(a*)*(x)",   "x",        0,1, 0,0, 0,1);
    T3("(a*)*(x)",   "ax",       0,2, 0,1, 1,2);
    T3("(a*)*(x)",   "axa",      0,2, 0,1, 1,2);
    T3("(a*)+(x)",   "x",        0,1, 0,0, 0,1);
    T3("(a*)+(x)",   "ax",       0,2, 0,1, 1,2);
    T3("(a*)+(x)",   "axa",      0,2, 0,1, 1,2);
    T3("(a*){2}(x)", "x",        0,1, 0,0, 0,1);
    T3("(a*){2}(x)", "ax",       0,2, 1,1, 1,2);
    T3("(a*){2}(x)", "axa",      0,2, 1,1, 1,2);
    T4("(()|.)(b)",     "ab",    0,2, 0,1, -1,-1, 1,2);
    T4("(()|[ab])(b)",  "ab",    0,2, 0,1, -1,-1, 1,2);
    T3("(()|[ab])+b",   "aaab",  0,4, 2,3, -1,-1);
    T4("(.|())(b)",     "ab",    0,2, 0,1, -1,-1, 1,2);
    T4("([ab]|())(b)",  "ab",    0,2, 0,1, -1,-1, 1,2);
    T3("([ab]|())+b",   "aaab",  0,4, 2,3, -1,-1);
    T3("(.?)(b)",       "ab",    0,2, 0,1, 1,2);

    // other
    T2("(a|aa)*",                            "aaa",         0,3, 2,3);
    T2("(a|aa)*",                            "aaaa",        0,4, 3,4);
    T2("(aa|a)*",                            "aaa",         0,3, 2,3);
    T2("(aa|a)*",                            "aaaa",        0,4, 2,4);
    T2("a|(a)",                              "a",           0,1, -1,-1);
    T2("(a)|a",                              "a",           0,1, 0,1);
    T3("(b)a|b(a)",                          "ba",          0,2, 0,1, -1,-1);
    T3("b(a)|(b)a",                          "ba",          0,2, 1,2, -1,-1);
    T2("a*|(a|aa)*",                         "aa",          0,2, -1,-1);
    T2("(a|aa)*|a*",                         "aa",          0,2, 1,2);
    T2("(aa*|aaa*)*",                        "aaaaaa",      0,6, 0,6);
    T3("(aa*|aaa*)(aa*|aaa*)",               "aaaaaa",      0,6, 0,5, 5,6);
    T2("(aa*|aaa*){2}",                      "aaaaaa",      0,6, 5,6);
    T7("((aa)*|(aaa)*)((aa)*|(aaa)*)",       "aaaaaa",      0,6, 0,6, 4,6, -1,-1, 6,6, -1,-1, -1,-1);
    T4("((aa)*|(aaa)*){2}",                  "aaaaaa",      0,6, 6,6, -1,-1, -1,-1);
    T3("(aa)*|(aaa)*",                       "aaaaaa",      0,6, 4,6, -1,-1);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XY",          0,2, 1,2);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XabY",        0,4, 2,4);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XababY",      0,6, 5,6);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XabababY",    0,8, 6,8);
    T2("(X|Xa|Xab|Xaba|abab|baba|bY|Y)*",    "XababababY",  0,10, 9,10);
    T0("(y){2}",                             "");
    T0("(y){2}",                             "y");
    T2("(y){2}",                             "yy",          0,2, 1,2);
    T2("(y){0,2}",                           "",            0,0, -1,-1);
    T2("(y){0,2}",                           "y",           0,1, 0,1);
    T2("(y){0,2}",                           "yy",          0,2, 1,2);
    T0("(y){1,2}",                           "");
    T2("(y){1,2}",                           "y",           0,1, 0,1);
    T2("(y){1,2}",                           "yy",          0,2, 1,2);
    T0("(y){1,2}y",                          "");
    T0("(y){1,2}y",                          "y");
    T2("(y){1,2}y",                          "yy",          0,2, 0,1);
    T2("(y){1,2}y",                          "yyy",         0,3, 1,2);
    T0("(y){1,2}y?",                         "");
    T2("(y){1,2}y?",                         "y",           0,1, 0,1);
    T2("(y){1,2}y?",                         "yy",          0,2, 1,2);
    T2("(y){1,2}y?",                         "yyy",         0,3, 1,2);
    T0("(y){2,}",                            "");
    T0("(y){2,}",                            "y");
    T2("(y){2,}",                            "yy",          0,2, 1,2);
    T2("(y){2,}",                            "yyy",         0,3, 2,3);
    T2("(y?){2}",                            "",            0,0, 0,0);
    T2("(y?){2}",                            "y",           0,1, 1,1);
    T2("(y?){2}",                            "yy",          0,2, 1,2);
    T2("(y?){0,2}",                          "",            0,0, 0,0);
    T2("(y?){0,2}",                          "y",           0,1, 1,1);
    T2("(y?){0,2}",                          "yy",          0,2, 1,2);
    T2("(y?){1,2}",                          "",            0,0, 0,0);
    T2("(y?){1,2}",                          "y",           0,1, 1,1);
    T2("(y?){1,2}",                          "yy",          0,2, 1,2);
    T0("(y?){1,2}y",                         "");
    T2("(y?){1,2}y",                         "y",           0,1, 0,0);
    T2("(y?){1,2}y",                         "yy",          0,2, 1,1);
    T2("(y?){1,2}y",                         "yyy",         0,3, 1,2);
    T2("(y?){1,2}y?",                        "",            0,0, 0,0);
    T2("(y?){1,2}y?",                        "y",           0,1, 1,1);
    T2("(y?){1,2}y?",                        "yy",          0,2, 1,2);
    T2("(y?){1,2}y?",                        "yyy",         0,3, 1,2);
    T2("(y?){2,}",                           "",            0,0, 0,0);
    T2("(y?){2,}",                           "y",           0,1, 1,1);
    T2("(y?){2,}",                           "yy",          0,2, 1,2);
    T2("(y?){2,}",                           "yyy",         0,3, 2,3);
    T3("(y|(x?)){1,3}",                      "y",           0,1, 1,1, 1,1);
    T2("(y[y]?){3}",                         "yyyy",        0,4, 3,4);

    // repetition
    T0("((..)|(.))",                         "");
    T0("((..)|(.))((..)|(.))",               "");
    T0("((..)|(.))((..)|(.))((..)|(.))",     "");
    T0("((..)|(.)){1}",                      "");
    T0("((..)|(.)){2}",                      "");
    T0("((..)|(.)){3}",                      "");
    T4("((..)|(.))*",                        "",            0,0, -1,-1, -1,-1, -1,-1);
    T4("((..)|(.))",                         "a",           0,1, 0,1, -1,-1, 0,1);
    T0("((..)|(.))((..)|(.))",               "a");
    T0("((..)|(.))((..)|(.))((..)|(.))",     "a");
    T4("((..)|(.)){1}",                      "a",           0,1, 0,1, -1,-1, 0,1);
    T0("((..)|(.)){2}",                      "a");
    T0("((..)|(.)){3}",                      "a");
    T4("((..)|(.))*",                        "a",           0,1, 0,1, -1,-1, 0,1);
    T4("((..)|(.))",                         "aa",          0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aa",          0,2, 0,1, -1,-1, 0,1, 1,2, -1,-1, 1,2);
    T0("((..)|(.))((..)|(.))((..)|(.))",     "aa");
    T4("((..)|(.)){1}",                      "aa",          0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aa",          0,2, 1,2, -1,-1, 1,2);
    T0("((..)|(.)){3}",                      "aa");
    T4("((..)|(.))*",                        "aa",          0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.))",                         "aaa",         0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaa",         0,3, 0,2, 0,2, -1,-1, 2,3, -1,-1, 2,3);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaa",         0,3, 0,1, -1,-1, 0,1, 1,2, -1,-1, 1,2, 2,3, -1,-1, 2,3);
    T4("((..)|(.)){1}",                      "aaa",         0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaa",         0,3, 2,3, -1,-1, 2,3);
    T4("((..)|(.)){3}",                      "aaa",         0,3, 2,3, -1,-1, 2,3);
    T4("((..)|(.))*",                        "aaa",         0,3, 2,3, -1,-1, 2,3);
    T4("((..)|(.))",                         "aaaa",        0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaaa",        0,4, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaaa",        0,4, 0,2, 0,2, -1,-1, 2,3, -1,-1, 2,3, 3,4, -1,-1, 3,4);
    T4("((..)|(.)){1}",                      "aaaa",        0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaaa",        0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.)){3}",                      "aaaa",        0,4, 3,4, -1,-1, 3,4);
    T4("((..)|(.))*",                        "aaaa",        0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.))",                         "aaaaa",       0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaaaa",       0,4, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaaaa",       0,5, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1, 4,5, -1,-1, 4,5);
    T4("((..)|(.)){1}",                      "aaaaa",       0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaaaa",       0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.)){3}",                      "aaaaa",       0,5, 4,5, -1,-1, 4,5);
    T4("((..)|(.))*",                        "aaaaa",       0,5, 4,5, -1,-1, 4,5);
    T4("((..)|(.))",                         "aaaaaa",      0,2, 0,2, 0,2, -1,-1);
    T7("((..)|(.))((..)|(.))",               "aaaaaa",      0,4, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1);
    T10("((..)|(.))((..)|(.))((..)|(.))",    "aaaaaa",      0,6, 0,2, 0,2, -1,-1, 2,4, 2,4, -1,-1, 4,6, 4,6, -1,-1);
    T4("((..)|(.)){1}",                      "aaaaaa",      0,2, 0,2, 0,2, -1,-1);
    T4("((..)|(.)){2}",                      "aaaaaa",      0,4, 2,4, 2,4, -1,-1);
    T4("((..)|(.)){3}",                      "aaaaaa",      0,6, 4,6, 4,6, -1,-1);
    T4("((..)|(.))*",                        "aaaaaa",      0,6, 4,6, 4,6, -1,-1);
    T2("X(.?){0,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){1,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){2,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){3,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){4,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){5,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){6,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){7,}Y",                         "X1234567Y",   0,9, 7,8);
    T2("X(.?){8,}Y",                         "X1234567Y",   0,9, 8,8);
    T2("X(.?){0,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){1,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){2,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){3,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){4,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){5,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){6,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){7,8}Y",                        "X1234567Y",   0,9, 8,8);
    T2("X(.?){8,8}Y",                        "X1234567Y",   0,9, 8,8);
    T3("(a|ab|c|bcd){0,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){1,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){2,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){3,}(d*)",               "ababcd",      0,6, 3,6, 6,6);
    T0("(a|ab|c|bcd){4,}(d*)",               "ababcd");
    T3("(a|ab|c|bcd){0,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){1,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){2,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd){3,10}(d*)",             "ababcd",      0,6, 3,6, 6,6);
    T0("(a|ab|c|bcd){4,10}(d*)",             "ababcd");
    T3("(a|ab|c|bcd)*(d*)",                  "ababcd",      0,6, 3,6, 6,6);
    T3("(a|ab|c|bcd)+(d*)",                  "ababcd",      0,6, 3,6, 6,6);
    T3("(ab|a|c|bcd){0,}(d*)",               "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd){1,}(d*)",               "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd){2,}(d*)",               "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd){3,}(d*)",               "ababcd",      0,6, 4,5, 5,6);
    T0("(ab|a|c|bcd){4,}(d*)",               "ababcd");
    T3("(ab|a|c|bcd){0,10}(d*)",             "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd){1,10}(d*)",             "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd){2,10}(d*)",             "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd){3,10}(d*)",             "ababcd",      0,6, 4,5, 5,6);
    T0("(ab|a|c|bcd){4,10}(d*)",             "ababcd");
    T3("(ab|a|c|bcd)*(d*)",                  "ababcd",      0,6, 4,5, 5,6);
    T3("(ab|a|c|bcd)+(d*)",                  "ababcd",      0,6, 4,5, 5,6);

    // rightassoc
    T4("(a|ab)(c|bcd)(d*)",                  "abcd",        0,4, 0,1, 1,4, 4,4);
    T4("(a|ab)(bcd|c)(d*)",                  "abcd",        0,4, 0,1, 1,4, 4,4);
    T4("(ab|a)(c|bcd)(d*)",                  "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(ab|a)(bcd|c)(d*)",                  "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(a*)(b|abc)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a*)(abc|b)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a*)(b|abc)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a*)(abc|b)(c*)",                    "abc",         0,3, 0,1, 1,2, 2,3);
    T4("(a|ab)(c|bcd)(d|.*)",                "abcd",        0,4, 0,1, 1,4, 4,4);
    T4("(a|ab)(bcd|c)(d|.*)",                "abcd",        0,4, 0,1, 1,4, 4,4);
    T4("(ab|a)(c|bcd)(d|.*)",                "abcd",        0,4, 0,2, 2,3, 3,4);
    T4("(ab|a)(bcd|c)(d|.*)",                "abcd",        0,4, 0,2, 2,3, 3,4);

    // other
    T3("((a?){1,1000})*", "aaaa", 0,4, 0,4, 4,4);

    return e;
}

#undef GS
#undef T
#undef T0
#undef T1
#undef T2
#undef T3
#undef T4
#undef T5
#undef T6
#undef T7
#undef T8
#undef T9
#undef T10

int main()
{
    int e = 0;

    e |= test_all_posix(0);
    e |= test_all_posix(REG_STADFA);

    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);

    return e;
}