gnu/lib/libregex/test/psx-extend.c

   1 /* psx-extend.c: Test POSIX extended regular expressions.  */
   2
   3 #include "test.h"
   4
   5
   6 void
   7 test_posix_extended ()
   8 {
   9   /* Intervals can only match up to RE_DUP_MAX occurences of anything.  */
  10   char dup_max_plus_one[6];
  11   sprintf (dup_max_plus_one, "%d", RE_DUP_MAX + 1);
  12
  13
  14   printf ("\nStarting POSIX extended tests.\n");
  15   t = posix_extended_test;
  16
  17   re_set_syntax (RE_SYNTAX_POSIX_MINIMAL_EXTENDED);
  18
  19   test_posix_generic ();
  20
  21   printf ("\nContinuing POSIX extended tests.\n");
  22
  23   /* Grouping tests that differ from basic's.  */
  24
  25   test_should_match = true;
  26   MATCH_SELF ("a)");
  27
  28                                 /* Valid use of special characters.  */
  29   test_match ("\\(a", "(a");
  30   test_match ("a\\+", "a+");
  31   test_match ("a\\?", "a?");
  32   test_match ("\\{a", "{a");
  33   test_match ("\\|a", "|a");
  34   test_match ("a\\|b", "a|b");
  35   test_match ("a\\|?", "a");
  36   test_match ("a\\|?", "a|");
  37   test_match ("a\\|*", "a");
  38   test_match ("a\\|*", "a||");
  39   test_match ("\\(*\\)", ")");
  40   test_match ("\\(*\\)", "(()");
  41   test_match ("a\\|+", "a|");
  42   test_match ("a\\|+", "a||");
  43   test_match ("\\(+\\)", "()");
  44   test_match ("\\(+\\)", "(()");
  45   test_match ("a\\||b", "a|");
  46   test_match ("\\(?\\)", ")");
  47   test_match ("\\(?\\)", "()");
  48
  49   test_match ("a+", "a");
  50   test_match ("a+", "aa");
  51   test_match ("a?", "");
  52   test_match ("a?", "a");
  53
  54                                                 /* Bracket expressions.  */
  55   test_match ("[(]", "(");
  56   test_match ("[+]", "+");
  57   test_match ("[?]", "?");
  58   test_match ("[{]", "{");
  59   test_match ("[|]", "|");
  60                                                 /* Subexpressions.  */
  61   test_match ("(a+)*", "");
  62   test_match ("(a+)*", "aa");
  63   test_match ("(a?)*", "");
  64   test_match ("(a?)*", "aa");
  65                                                 /* (No) back references.  */
  66   test_match ("(a)\\1", "a1");
  67                                                 /* Invalid as intervals,
  68                                                    but are valid patterns.  */
  69   MATCH_SELF ("{");
  70   test_match ("^{", "{");
  71   test_match ("a|{", "{");
  72   test_match ("({)", "{");
  73   MATCH_SELF ("a{");
  74   MATCH_SELF ("a{}");
  75   MATCH_SELF ("a{-1");
  76   MATCH_SELF ("a{-1}");
  77   MATCH_SELF ("a{0");
  78   MATCH_SELF ("a{0,");
  79   MATCH_SELF (concat ("a{", dup_max_plus_one));
  80   MATCH_SELF (concat (concat ("a{", dup_max_plus_one), ","));
  81   MATCH_SELF ("a{1,0");
  82   MATCH_SELF ("a{1,0}");
  83   MATCH_SELF ("a{0,1");
  84   test_match ("[a{0,1}]", "}");
  85   test_match ("a{1,3}{-1}", "aaa{-1}");
  86   test_match (concat ("a{1,3}{", dup_max_plus_one),
  87               concat ("aaa{", dup_max_plus_one));
  88   test_match ("a{1,3}{2,1}", "aaa{2,1}");
  89   test_match ("a{1,3}{1,2", "aaa{1,2");
  90                                         /* Valid consecutive repetitions.  */
  91   test_match ("a*+", "a");
  92   test_match ("a*?", "a");
  93   test_match ("a++", "a");
  94   test_match ("a+*", "a");
  95   test_match ("a+?", "a");
  96   test_match ("a??", "a");
  97   test_match ("a?*", "a");
  98   test_match ("a?+", "a");
  99
 100   test_match ("a{2}?", "");
 101   test_match ("a{2}?", "aa");
 102   test_match ("a{2}+", "aa");
 103   test_match ("a{2}{2}", "aaaa");
 104
 105   test_match ("a{1}?*", "");
 106   test_match ("a{1}?*", "aa");
 107
 108   test_match ("(a?){0,3}b", "aaab");
 109   test_fastmap ("(a?){0,3}b", "ab", 0, 0);
 110   test_match ("(a+){0,3}b", "b");
 111   test_fastmap ("(a+){0,3}b", "ab", 0, 0);
 112   test_match ("(a+){0,3}b", "ab");
 113   test_fastmap ("(a+){0,3}b", "ab", 0, 0);
 114   test_match ("(a+){1,3}b", "aaab");
 115   test_match ("(a?){1,3}b", "aaab");
 116
 117   test_match ("\\\\{1}", "\\");                         /* Extended only.  */
 118
 119   test_match ("(a?)?", "a");
 120   test_match ("(a?b)?c", "abc");
 121   test_match ("(a+)*b", "b");
 122                                                 /* Alternatives.  */
 123   test_match ("a|b", "a");
 124   test_match ("a|b", "b");
 125   test_fastmap ("a|b", "ab", 0, 0);
 126
 127   TEST_SEARCH ("a|b", "cb", 0, 2);
 128   TEST_SEARCH ("a|b", "cb", 0, 2);
 129
 130   test_match ("(a|b|c)", "a");
 131   test_match ("(a|b|c)", "b");
 132   test_match ("(a|b|c)", "c");
 133
 134   test_match ("(a|b|c)*", "abccba");
 135
 136   test_match ("(a(b*))|c", "a");        /* xx do registers.  */
 137   test_match ("(a(b*))|c", "ab");
 138   test_match ("(a(b*))|c", "c");
 139
 140   test_fastmap ("(a+?*|b)", "ab", 0, 0);
 141   test_match ("(a+?*|b)", "b");
 142   TEST_REGISTERS ("(a+?*|b)", "b", 0, 1, 0, 1, -1, -1);
 143
 144   test_fastmap ("(a+?*|b)*", "ab", 0, 0);
 145   test_match ("(a+?*|b)*", "bb");
 146   TEST_REGISTERS ("(a+?*|b)*", "bb", 0, 2, 1, 2, -1, -1);
 147
 148   test_fastmap ("(a*|b)*", "ab", 0, 0);
 149   test_match ("(a*|b)*", "bb");
 150   TEST_REGISTERS ("(a*|b)*", "bb", 0, 2, 1, 2, -1, -1);
 151
 152   test_fastmap ("((a*)|b)*", "ab", 0, 0);
 153   test_match ("((a*)|b)*", "bb");
 154   TEST_REGISTERS ("((a*)|b)*", "bb", 0, 2, 1, 2, 1, 1);
 155
 156   test_fastmap ("(a{0,}|b)*", "ab", 0, 0);
 157   test_match ("(a{0,}|b)*", "bb");
 158   TEST_REGISTERS ("(a{0,}|b)*", "bb", 0, 2, 1, 2, -1, -1);
 159
 160   test_fastmap ("((a{0,})|b)*", "ab", 0, 0);
 161   test_match ("((a{0,})|b)*", "bb");
 162   TEST_REGISTERS ("((a{0,})|b)*", "bb", 0, 2, 1, 2, 1, 1);
 163
 164                                                 /* With c's  */
 165   test_fastmap ("(a+?*|b)c", "abc", 0, 0);
 166   test_match ("(a+?*|b)c", "bc");
 167   TEST_REGISTERS ("(a+?*|b)c", "bc", 0, 2, 0, 1, -1, -1);
 168
 169   test_fastmap ("(a+?*|b)*c", "abc", 0, 0);
 170   test_match ("(a+?*|b)*c", "bbc");
 171   TEST_REGISTERS ("(a+?*|b)*c", "bbc", 0, 3, 1, 2, -1, -1);
 172
 173   test_fastmap ("(a*|b)*c", "abc", 0, 0);
 174   test_match ("(a*|b)*c", "bbc");
 175   TEST_REGISTERS ("(a*|b)*c", "bbc", 0, 3, 1, 2, -1, -1);
 176
 177   test_fastmap ("((a*)|b)*c", "abc", 0, 0);
 178   test_match ("((a*)|b)*c", "bbc");
 179   TEST_REGISTERS ("((a*)|b)*c", "bbc", 0, 3, 1, 2, 1, 1);
 180
 181   test_fastmap ("(a{0,}|b)*c", "abc", 0, 0);
 182   test_match ("(a{0,}|b)*c", "bbc");
 183   TEST_REGISTERS ("(a{0,}|b)*c", "bbc", 0, 3, 1, 2, -1, -1);
 184
 185   test_fastmap ("((a{0,})|b)*c", "abc", 0, 0);
 186   test_match ("((a{0,})|b)*c", "bbc");
 187   TEST_REGISTERS ("((a{0,})|b)*c", "bbc", 0, 3, 1, 2, 1, 1);
 188
 189
 190   test_fastmap ("((a{0,}\\b\\<)|b)", "ab", 0, 0);
 191   test_match ("((a{0,}\\b\\<)|b)", "b");
 192   TEST_REGISTERS ("((a{0,}\\b\\<)|b)", "b",
 193     0, 1, 0, 1, 0, 0);
 194
 195   test_fastmap ("((a{0,}\\b\\<)|b)*", "ab", 0, 0);
 196   test_match ("((a{0,}\\b\\<)|b)*", "b");
 197   TEST_REGISTERS ("((a{0,}\\b\\<)|b)*", "b",
 198     0, 1, 0, 1, 0, 0);
 199
 200   test_fastmap ("((a+?*{0,1}\\b\\<)|b)", "ab", 0, 0);
 201   test_match ("((a+?*{0,1}\\b\\<)|b)", "b");
 202   TEST_REGISTERS ("((a+?*{0,1}\\b\\<)|b)", "b",
 203     0, 1, 0, 1, 0, 0);
 204
 205   test_fastmap ("((a+?*{0,2}\\b\\<)|b)", "ab", 0, 0);
 206   test_match ("((a+?*{0,2}\\b\\<)|b)", "b");
 207   TEST_REGISTERS ("((a+?*{0,2}\\b\\<)|b)", "b",
 208     0, 1, 0, 1, 0, 0);
 209
 210
 211   test_fastmap ("((a+?*{0,4095}\\b\\<)|b)", "ab", 0, 0);
 212   test_match ("((a+?*{0,4095}\\b\\<)|b)", "b");
 213   TEST_REGISTERS ("((a+?*{0,4095}\\b\\<)|b)", "b",
 214     0, 1, 0, 1, 0, 0);
 215
 216   test_fastmap ("((a+?*{0,5119}\\b\\<)|b)", "ab", 0, 0);
 217   test_match ("((a+?*{0,5119}\\b\\<)|b)", "b");
 218   TEST_REGISTERS ("((a+?*{0,5119}\\b\\<)|b)", "b",
 219     0, 1, 0, 1, 0, 0);
 220
 221   test_fastmap ("((a+?*{0,6143}\\b\\<)|b)", "ab", 0, 0);
 222   test_match ("((a+?*{0,6143}\\b\\<)|b)", "b");
 223   TEST_REGISTERS ("((a+?*{0,6143}\\b\\<)|b)", "b",
 224     0, 1, 0, 1, 0, 0);
 225
 226   test_fastmap ("((a+?*{0,8191}\\b\\<)|b)", "ab", 0, 0);
 227   test_match ("((a+?*{0,8191}\\b\\<)|b)", "b");
 228   TEST_REGISTERS ("((a+?*{0,8191}\\b\\<)|b)", "b",
 229     0, 1, 0, 1, 0, 0);
 230
 231   test_fastmap ("((a+?*{0,16383}\\b\\<)|b)", "ab", 0, 0);
 232   test_match ("((a+?*{0,16383}\\b\\<)|b)", "b");
 233   TEST_REGISTERS ("((a+?*{0,16383}\\b\\<)|b)", "b",
 234     0, 1, 0, 1, 0, 0);
 235
 236
 237   test_fastmap ("((a+?*{0,}\\b\\<)|b)", "ab", 0, 0);
 238   test_match ("((a+?*{0,}\\b\\<)|b)", "b");
 239   TEST_REGISTERS ("((a+?*{0,}\\b\\<)|b)", "b",
 240     0, 1, 0, 1, 0, 0);
 241
 242   test_fastmap ("((a+?*{0,}\\b\\<)|b)*", "ab", 0, 0);
 243   test_match ("((a+?*{0,}\\b\\<)|b)*", "b");
 244   TEST_REGISTERS ("((a+?*{0,}\\b\\<)|b)*", "b",
 245     0, 1, 0, 1, 0, 0);
 246
 247   test_fastmap ("((a+?*{0,}\\b\\<)|b)*", "ab", 0, 0);
 248   test_match ("((a+?*{0,}\\b\\<)|b)*", "bb");
 249   TEST_REGISTERS ("((a+?*{0,}\\b\\<)|b)*", "bb",
 250     0, 2, 1, 2, 0, 0);
 251
 252
 253                                 /* `*' after group.  */
 254   test_match ("(a*|b*)*c", "c");
 255   TEST_REGISTERS ("(a*|b*)*c", "c", 0, 1, 0, 0, -1, -1);
 256
 257   test_match ("(a*|b*)*c", "ac");
 258   TEST_REGISTERS ("(a*|b*)*c", "ac", 0, 2, 0, 1, -1, -1);
 259
 260   test_match ("(a*|b*)*c", "aac");
 261   TEST_REGISTERS ("(a*|b*)*c", "aac", 0, 3, 0, 2, -1, -1);
 262
 263   test_match ("(a*|b*)*c", "bbc");
 264   TEST_REGISTERS ("(a*|b*)*c", "bbc", 0, 3, 0, 2, -1, -1);
 265
 266   test_match ("(a*|b*)*c", "abc");
 267   TEST_REGISTERS ("(a*|b*)*c", "abc", 0, 3, 1, 2, -1, -1);
 268
 269                                 /* No `*' after group.  */
 270   test_match ("(a*|b*)c", "c");
 271   TEST_REGISTERS ("(a*|b*)c", "c", 0, 1, 0, 0, -1, -1);
 272
 273   test_match ("(a*|b*)c", "ac");
 274   TEST_REGISTERS ("(a*|b*)c", "ac", 0, 2, 0, 1, -1, -1);
 275
 276   test_match ("(a*|b*)c", "bc");
 277   TEST_REGISTERS ("(a*|b*)c", "bc", 0, 2, 0, 1, -1, -1);
 278
 279   test_match ("(a*|b*)c", "aac");
 280   TEST_REGISTERS ("(a*|b*)c", "aac", 0, 3, 0, 2, -1, -1);
 281
 282   /* Same as above, but with no `*'s in alternatives.
 283
 284   test_match ("(a|b)*c", "c");          /* `*' after group.  */
 285   TEST_REGISTERS ("(a|b)*c", "c", 0, 1, -1, -1, -1, -1);
 286
 287   test_match ("(a|b)*c", "ac");
 288   TEST_REGISTERS ("(a|b)*c", "ac", 0, 2, 0, 1, -1, -1);
 289
 290   test_match ("(a|b)*c", "bc");
 291   TEST_REGISTERS ("(a|b)*c", "bc", 0, 2, 0, 1, -1, -1);
 292
 293   test_match ("(a|b)*c", "abc");
 294   TEST_REGISTERS ("(a|b)*c", "abc", 0, 3, 1, 2, -1, -1);
 295
 296
 297   test_match ("(a*|b*)c", "bbc");
 298   TEST_REGISTERS ("(a*|b*)c", "bbc", 0, 3, 0, 2, -1, -1);
 299
 300   /* Complicated second alternative.  */
 301
 302   test_match ("(a*|(b*)*)*c", "bc");
 303   TEST_REGISTERS ("(a*|(b*)*)*c", "bc", 0, 2, 0, 1, 0, 1);
 304
 305   test_match ("(a*|(b*|c*)*)*d", "bd");
 306   TEST_REGISTERS ("(a*|(b*|c*)*)*d", "bd", 0, 2, 0, 1, 0, 1);
 307
 308   test_match ("(a*|(b*|c*)*)*d", "bbd");
 309   TEST_REGISTERS ("(a*|(b*|c*)*)*d", "bbd", 0, 3, 0, 2, 0, 2);
 310
 311   test_match ("(a*|(b*|c*)*)*d", "cd");
 312   TEST_REGISTERS ("(a*|(b*|c*)*)*d", "cd", 0, 2, 0, 1, 0, 1);
 313
 314   test_match ("(a*|(b*|c*)*)*d", "ccd");
 315   TEST_REGISTERS ("(a*|(b*|c*)*)*d", "ccd", 0, 3, 0, 2, 0, 2);
 316
 317   test_match ("(a*|b*|c*)*d", "aad");
 318   TEST_REGISTERS ("(a*|b*|c*)*d", "aad", 0, 3, 0, 2, 0, 2);
 319
 320   test_match ("(a*|b*|c*)*d", "bbd");
 321   TEST_REGISTERS ("(a*|b*|c*)*d", "bbd", 0, 3, 0, 2, 0, 2);
 322
 323   test_match ("(a*|b*|c*)*d", "ccd");
 324   TEST_REGISTERS ("(a*|b*|c*)*d", "ccd", 0, 3, 0, 2, 0, 2);
 325
 326                                                 /* Valid anchoring.  */
 327   valid_pattern ("a^");
 328   valid_pattern ("a^b");
 329   valid_pattern ("$a");
 330   valid_pattern ("a$b");
 331   valid_pattern ("foo^bar");
 332   valid_pattern ("foo$bar");
 333   valid_pattern ("(^)");
 334   valid_pattern ("($)");
 335   valid_pattern ("(^$)");
 336
 337       /* These are the same (but valid) as those (invalid) in other_test.c.  */
 338   valid_pattern
 339     ("(((((((((((((((((((((((((((((((((a^)))))))))))))))))))))))))))))))))");
 340   valid_pattern
 341     ("((((((((((((((((((((((((((((((((($a)))))))))))))))))))))))))))))))))");
 342   valid_pattern ("\\(^a\\)");
 343   valid_pattern ("a\\|^b");
 344   valid_pattern ("\\w^a");
 345   valid_pattern ("\\W^a");
 346   valid_pattern ("(a^)");
 347   valid_pattern ("($a)");
 348   valid_pattern ("a(^b)");
 349   valid_pattern ("a$(b)");
 350   valid_pattern ("(a)^b");
 351   valid_pattern ("(a)$b");
 352   valid_pattern ("(a)(^b)");
 353   valid_pattern ("(a$)(b)");
 354   valid_pattern ("(a|b)^c");
 355   valid_pattern ("(a|b)$c");
 356   valid_pattern ("(a$|b)c");
 357   valid_pattern ("(a|b$)c");
 358   valid_pattern ("a(b|^c)");
 359   valid_pattern ("a(^b|c)");
 360   valid_pattern ("a$(b|c)");
 361   valid_pattern ("(a)(^b|c)");
 362   valid_pattern ("(a)(b|^c)");
 363   valid_pattern ("(b$|c)(a)");
 364   valid_pattern ("(b|c$)(a)");
 365   valid_pattern ("(a(^b|c))");
 366   valid_pattern ("(a(b|^c))");
 367   valid_pattern ("((b$|c)a)");
 368   valid_pattern ("((b|c$)a)");
 369   valid_pattern ("((^a|^b)^c)");
 370   valid_pattern ("(c$(a$|b$))");
 371   valid_pattern ("((^a|^b)^c)");
 372   valid_pattern ("((a$|b$)c)");
 373   valid_pattern ("(c$(a$|b$))");
 374   valid_pattern ("((^a|^b)|^c)^d");
 375   valid_pattern ("((a$|b$)|c$)d$");
 376   valid_pattern ("d$(c$|(a$|b$))");
 377   valid_pattern ("((^a|^b)|^c)(^d)");
 378   valid_pattern ("((a$|b$)|c$)(d$)");
 379   valid_pattern ("(d$)((a$|b$)|c$)");
 380   valid_pattern ("((^a|^b)|^c)((^d))");
 381   valid_pattern ("((a$|b$)|c$)((d$))");
 382   valid_pattern ("((d$))((a$|b$)|c$)");
 383   valid_pattern ("(((^a|^b))c|^d)^e");
 384   valid_pattern ("(((a$|b$))c|d$)$e$");
 385   valid_pattern ("e$(d$|c((a$|b$)))");
 386   valid_pattern ("(^a)((^b))");
 387   valid_pattern ("(a$)((b$))");
 388   valid_pattern ("((^a))(^b)");
 389   valid_pattern ("((a$))(b$)");
 390   valid_pattern ("((^a))((^b))");
 391   valid_pattern ("((a$))((b$))");
 392   valid_pattern ("((^a)^b)");
 393   valid_pattern ("((a$)b$)");
 394   valid_pattern ("(b$(a$))");
 395   valid_pattern ("(((^a)b)^c)");
 396   valid_pattern ("(((a$)b)c$)");
 397   valid_pattern ("(c$(b(a$)))");
 398   valid_pattern ("(((^a)b)c)^d");
 399   valid_pattern ("(((a$)b)c)d$");
 400   valid_pattern ("d$(c(b(a$)))");
 401   valid_pattern (".^a");
 402   valid_pattern ("a$.");
 403   valid_pattern ("[a]^b");
 404   valid_pattern ("b$[a]");
 405   valid_pattern ("\\(a$\\)");
 406   valid_pattern ("a$\\|b");
 407   valid_pattern ("(^a|^b)^c");
 408   valid_pattern ("c$(a$|b$)");
 409   valid_pattern ("(^a|^b)^|^c");
 410   valid_pattern ("(a$|b$)$|$c$");
 411   valid_pattern ("(a$|$b$)$|c$");
 412   valid_pattern ("($a$|b$)$|c$");
 413   valid_pattern ("$(a$|b$)$|c$");
 414   valid_pattern ("^c|d(^a|^b)");
 415   valid_pattern ("(^a|^b)|d^c");
 416   valid_pattern ("c$|(a$|b$)d");
 417   valid_pattern ("c$d|(a$|b$)");
 418   valid_pattern ("c(^a|^b)|^d");
 419   valid_pattern ("(a$|b$)c|d$");
 420   valid_pattern ("c(((^a|^b))|^d)e");
 421   valid_pattern ("(c((^a|^b))|^d)e");
 422   valid_pattern ("((c(^a|^b))|^d)e");
 423   valid_pattern ("(((^a|^b))|c^d)e");
 424   valid_pattern ("(((^a|^b))|^d)^e");
 425   valid_pattern ("(c$((a|b))|d)e$");
 426   valid_pattern ("(c((a$|b$))|d)e$");
 427   valid_pattern ("(c((a|b)$)|d)e$");
 428   valid_pattern ("(c((a|b))|d$)e$");
 429   valid_pattern ("^d(^c|e((a|b)))");
 430   valid_pattern ("^d(c|^e((a|b)))");
 431   valid_pattern ("^d(c|e(^(a|b)))");
 432   valid_pattern ("^d(c|e((^a|b)))");
 433   valid_pattern ("^d(c|e((a|^b)))");
 434   valid_pattern ("^d(c|e((a|b^)))");
 435   valid_pattern ("^d(c|e((a|b)^))");
 436   valid_pattern ("^d(c|e((a|b))^)");
 437   valid_pattern ("^d(c|e((a|b)))^");
 438   valid_pattern ("d$(c$|e((a$|b$)))");
 439   valid_pattern ("d(c$|e$((a$|b$)))");
 440   valid_pattern ("(((^a|^b))^c)|^de");
 441   valid_pattern ("(((^a|^b))c)|^d^e");
 442   valid_pattern ("(((a$|b))c$)|de$");
 443   valid_pattern ("(((a|b$))c$)|de$");
 444   valid_pattern ("(((a|b))c$)|d$e$");
 445   valid_pattern ("^d^e|^(c((a|b)))");
 446   valid_pattern ("^de|^(c^((a|b)))");
 447   valid_pattern ("^de|^(c(^(a|b)))");
 448   valid_pattern ("^de|^(c((^a|b)))");
 449   valid_pattern ("^de|^(c((a|^b)))");
 450   valid_pattern ("^de|(^c(^(a|b)))");
 451   valid_pattern ("^de|(^c((^a|b)))");
 452   valid_pattern ("^de|(^c((a|^b)))");
 453   valid_pattern ("de$|(c($(a|b)$))");
 454   valid_pattern ("de$|(c$((a|b)$))");
 455   valid_pattern ("de$|($c((a|b)$))");
 456   valid_pattern ("de$|$(c((a|b)$))");
 457   valid_pattern ("de$|(c($(a|b))$)");
 458   valid_pattern ("de$|(c$((a|b))$)");
 459   valid_pattern ("de$|$(c((a|b))$)");
 460   valid_pattern ("de$|(c($(a|b)))$");
 461   valid_pattern ("de$|(c$((a|b)))$");
 462   valid_pattern ("de$|($c((a|b)))$");
 463   valid_pattern ("de$|$(c((a|b)))$");
 464   valid_pattern ("^a(^b|c)|^d");
 465   valid_pattern ("^a(b|^c)|^d");
 466   valid_pattern ("^a(b|c^)|^d");
 467   valid_pattern ("^a(b|c)^|^d");
 468   valid_pattern ("a$(b$|c$)|d$");
 469   valid_pattern ("^d|^a(^b|c)");
 470   valid_pattern ("^d|^a(b|^c)");
 471   valid_pattern ("d$|a$(b$|c$)");
 472   valid_pattern ("^d|^(b|c)^a");
 473   valid_pattern ("d$|(b|c$)a$");
 474   valid_pattern ("d$|(b$|c)a$");
 475   valid_pattern ("^(a)^(b|c)|^d");
 476   valid_pattern ("^(a)(^b|c)|^d");
 477   valid_pattern ("^(a)(b|^c)|^d");
 478   valid_pattern ("(a)$(b|c)$|d$");
 479   valid_pattern ("(a$)(b|c)$|d$");
 480   valid_pattern ("(^a)(^b|c)|^d");
 481   valid_pattern ("(^a)(b|^c)|^d");
 482   valid_pattern ("(a)$(b$|c$)|d$");
 483   valid_pattern ("(a$)(b$|c$)|d$");
 484   valid_pattern ("^d|^(b|c)^(a)");
 485   valid_pattern ("^d|^(b|c)(^a)");
 486   valid_pattern ("d$|(b|c$)(a)$");
 487   valid_pattern ("d$|(b$|c)(a)$");
 488   valid_pattern ("^d|(^b|^c)^(a)");
 489   valid_pattern ("^d|(^b|^c)(^a)");
 490   valid_pattern ("d$|(b|c)$(a$)");
 491   valid_pattern ("d$|(b|c$)(a$)");
 492   valid_pattern ("d$|(b$|c)(a$)");
 493   valid_pattern ("^d|^(a)^(b|c)");
 494   valid_pattern ("^d|^(a)(^b|c)");
 495   valid_pattern ("^d|^(a)(b|^c)");
 496   valid_pattern ("^d|(^a)^(b|c)");
 497   valid_pattern ("^d|(^a)(^b|c)");
 498   valid_pattern ("^d|(^a)(b|^c)");
 499   valid_pattern ("d$|(a)$(b$|c$)");
 500   valid_pattern ("d$|(a$)(b$|c$)");
 501   valid_pattern ("((e^a|^b)|^c)|^d");
 502   valid_pattern ("((^a|e^b)|^c)|^d");
 503   valid_pattern ("((^a|^b)|e^c)|^d");
 504   valid_pattern ("((^a|^b)|^c)|e^d");
 505   valid_pattern ("d$e|(c$|(a$|b$))");
 506   valid_pattern ("d$|(c$e|(a$|b$))");
 507   valid_pattern ("d$|(c$|(a$e|b$))");
 508   valid_pattern ("d$|(c$|(a$|b$e))");
 509   valid_pattern ("d$|(c$|(a$|b$)e)");
 510   valid_pattern ("d$|(c$|(a$|b$))e");
 511   valid_pattern ("(a|b)^|c");
 512   valid_pattern ("(a|b)|c^");
 513   valid_pattern ("$(a|b)|c");
 514   valid_pattern ("(a|b)|$c");
 515   valid_pattern ("(a^|^b)|^c");
 516   valid_pattern ("(^a|b^)|^c");
 517   valid_pattern ("(^a|^b)|c^");
 518   valid_pattern ("($a|b$)|c$");
 519   valid_pattern ("(a$|$b)|c$");
 520   valid_pattern ("(a$|b$)|$c");
 521   valid_pattern ("c^|(^a|^b)");
 522   valid_pattern ("^c|(a^|^b)");
 523   valid_pattern ("^c|(^a|b^)");
 524   valid_pattern ("$c|(a$|b$)");
 525   valid_pattern ("c$|($a|b$)");
 526   valid_pattern ("c$|(a$|$b)");
 527   valid_pattern ("c^|^(a|b)");
 528   valid_pattern ("^c|(a|b)^");
 529   valid_pattern ("$c|(a|b)$");
 530   valid_pattern ("c$|$(a|b)");
 531   valid_pattern ("(a^|^b)c|^d");
 532   valid_pattern ("(^a|b^)c|^d");
 533   valid_pattern ("(^a|^b)c|d^");
 534   valid_pattern ("(^a|^b)^c|^d");
 535   valid_pattern ("(a|b)c$|$d");
 536   valid_pattern ("(a|b)$c$|d$");
 537   valid_pattern ("(a|b)$c$|d$");
 538   valid_pattern ("(a|b$)c$|d$");
 539   valid_pattern ("(a$|b)c$|d$");
 540   valid_pattern ("($a|b)c$|d$");
 541   valid_pattern ("$(a|b)c$|d$");
 542   valid_pattern ("^d|^c^(a|b)");
 543   valid_pattern ("^d|^c(^a|b)");
 544   valid_pattern ("^d|^c(a|^b)");
 545   valid_pattern ("^d|^c(a|b^)");
 546   valid_pattern ("^d|^c(a|b)^");
 547   valid_pattern ("$d|c(a$|b$)");
 548   valid_pattern ("d$|c($a$|b$)");
 549   valid_pattern ("d$|c$(a$|b$)");
 550   valid_pattern ("d$|$c(a$|b$)");
 551
 552   valid_pattern ("(((a^|^b))c|^d)e");
 553   valid_pattern ("(((^a|b^))c|^d)e");
 554   valid_pattern ("(((^a|^b))^c|^d)e");
 555   valid_pattern ("((^(a|b))c|d^)e");
 556   valid_pattern ("(^((a|b))c|^d)^e");
 557   valid_pattern ("(^((a|b)^)c|^d)e");
 558   valid_pattern ("(^((a^|b))c|^d)e");
 559   valid_pattern ("(^((a|b^))c|^d)e");
 560   valid_pattern ("(^((a|b)^)c|^d)e");
 561   valid_pattern ("(^((a|b))^c|^d)e");
 562   valid_pattern ("(^((a|b))c^|^d)e");
 563   valid_pattern ("(^((a|b))c|^d^)e");
 564   valid_pattern ("(^((a|b))c|^d)^e");
 565   valid_pattern ("(((a|b))c|d)$e$");
 566   valid_pattern ("(((a|b))c|d$)e$");
 567   valid_pattern ("(((a|b))c|$d)e$");
 568   valid_pattern ("(((a|b))c$|d)e$");
 569   valid_pattern ("(((a|b))$c|d)e$");
 570   valid_pattern ("(((a|b)$)c|d)e$");
 571   valid_pattern ("(((a|b$))c|d)e$");
 572   valid_pattern ("(((a$|b))c|d)e$");
 573   valid_pattern ("((($a|b))c|d)e$");
 574   valid_pattern ("(($(a|b))c|d)e$");
 575   valid_pattern ("($((a|b))c|d)e$");
 576   valid_pattern ("$(((a|b))c|d)e$");
 577   valid_pattern ("(^((a|b)^)c|^d)e");
 578   valid_pattern ("(^((a|b))^c|^d)e");
 579   valid_pattern ("(^((a|b))c|^d^)e");
 580   valid_pattern ("(^((a|b))c|^d)^e");
 581
 582   valid_pattern ("^e(^d|c((a|b)))");
 583   valid_pattern ("^e(d|^c((a|b)))");
 584   valid_pattern ("^e(d|c^((a|b)))");
 585   valid_pattern ("^e(d|c(^(a|b)))");
 586   valid_pattern ("^e(d|c((^a|b)))");
 587   valid_pattern ("^e(d|c((a|^b)))");
 588   valid_pattern ("^e(d|c((a|b^)))");
 589   valid_pattern ("^e(d|c((a|b)^))");
 590   valid_pattern ("^e(d|c((a|b))^)");
 591   valid_pattern ("^e(d|c((a|b)))^");
 592   valid_pattern ("e$(d$|c((a$|b$)))");
 593   valid_pattern ("e(d$|c$((a$|b$)))");
 594   valid_pattern ("e(d$|c($(a$|b$)))");
 595   valid_pattern ("e(d$|c(($a$|b$)))");
 596   valid_pattern ("e$(d$|c((a|b)$))");
 597   valid_pattern ("e($d$|c((a|b)$))");
 598   valid_pattern ("e(d$|$c((a|b)$))");
 599   valid_pattern ("e(d$|c$((a|b)$))");
 600   valid_pattern ("e(d$|c($(a|b)$))");
 601   valid_pattern ("e(d$|c(($a|b)$))");
 602   valid_pattern ("e(d$|c((a|$b)$))");
 603   valid_pattern ("e(d$|c((a$|$b$)))");
 604
 605   valid_pattern ("e$(d$|c((a|b))$)");
 606   valid_pattern ("e($d$|c((a|b))$)");
 607   valid_pattern ("e(d$|$c((a|b))$)");
 608   valid_pattern ("e(d$|c$((a|b))$)");
 609   valid_pattern ("e(d$|c($(a|b))$)");
 610   valid_pattern ("e(d$|c(($a|b))$)");
 611   valid_pattern ("e(d$|c((a|$b))$)");
 612   valid_pattern ("e$(d$|c((a|b)))$");
 613   valid_pattern ("e($d$|c((a|b)))$");
 614   valid_pattern ("e(d$|$c((a|b)))$");
 615   valid_pattern ("e(d$|c$((a|b)))$");
 616   valid_pattern ("e(d$|c($(a|b)))$");
 617   valid_pattern ("e(d$|c(($a|b)))$");
 618   valid_pattern ("e(d$|c((a|$b)))$");
 619   valid_pattern ("(((^a|^b)^)c)|^de");
 620   valid_pattern ("(((^a|^b))^c)|^de");
 621   valid_pattern ("(((^a|^b))c)^|^de");
 622   valid_pattern ("$(((a|b))c$)|de$");
 623   valid_pattern ("($((a|b))c$)|de$");
 624   valid_pattern ("(($(a|b))c$)|de$");
 625   valid_pattern ("((($a|b))c$)|de$");
 626   valid_pattern ("(((a|$b))c$)|de$");
 627   valid_pattern ("(((a|b)$)c$)|de$");
 628   valid_pattern ("(((a|b))$c$)|de$");
 629   valid_pattern ("$(((a|b))c)$|de$");
 630   valid_pattern ("($((a|b))c)$|de$");
 631   valid_pattern ("(($(a|b))c)$|de$");
 632   valid_pattern ("((($a|b))c)$|de$");
 633   valid_pattern ("(((a|$b))c)$|de$");
 634   valid_pattern ("(((a|b)$)c)$|de$");
 635   valid_pattern ("(((a|b))$c)$|de$");
 636   valid_pattern ("^ed|^(c((a|b)))^");
 637   valid_pattern ("^ed|^(c((a|b))^)");
 638   valid_pattern ("^ed|^(c((a|b)^))");
 639   valid_pattern ("^ed|^(c((a|b^)))");
 640   valid_pattern ("^ed|^(c((a^|b)))");
 641   valid_pattern ("^ed|^(c((^a|b)))");
 642   valid_pattern ("^ed|^(c(^(a|b)))");
 643   valid_pattern ("^ed|^(c^((a|b)))");
 644   valid_pattern ("^ed|(^c((a|b)))^");
 645   valid_pattern ("^ed|(^c((a|b))^)");
 646   valid_pattern ("^ed|(^c((a|b)^))");
 647   valid_pattern ("^ed|(^c((a|b^)))");
 648   valid_pattern ("^ed|(^c((a|^b)))");
 649   valid_pattern ("^ed|(^c((a^|b)))");
 650   valid_pattern ("^ed|(^c((^a|b)))");
 651   valid_pattern ("^ed|(^c(^(a|b)))");
 652   valid_pattern ("^ed|(^c(^(a|b)))");
 653   valid_pattern ("^ed|(^c^((a|b)))");
 654   valid_pattern ("ed$|$(c((a|b)))$");
 655   valid_pattern ("ed$|($c((a|b)))$");
 656   valid_pattern ("ed$|(c$((a|b)))$");
 657   valid_pattern ("ed$|(c($(a|b)))$");
 658   valid_pattern ("ed$|(c(($a|b)))$");
 659   valid_pattern ("ed$|(c((a|$b)))$");
 660   valid_pattern ("ed$|$(c((a|b))$)");
 661   valid_pattern ("ed$|($c((a|b))$)");
 662   valid_pattern ("ed$|(c$((a|b))$)");
 663   valid_pattern ("ed$|(c($(a|b))$)");
 664   valid_pattern ("ed$|(c(($a|b))$)");
 665   valid_pattern ("ed$|(c((a|$b))$)");
 666   valid_pattern ("ed$|$(c((a|b)$))");
 667   valid_pattern ("ed$|($c((a|b)$))");
 668   valid_pattern ("ed$|(c$((a|b)$))");
 669   valid_pattern ("ed$|(c($(a|b)$))");
 670   valid_pattern ("ed$|(c(($a|b)$))");
 671   valid_pattern ("ed$|(c((a|$b)$))");
 672   valid_pattern ("ed$|$(c((a|b)$))");
 673   valid_pattern ("ed$|($c((a|b)$))");
 674   valid_pattern ("ed$|(c$((a|b)$))");
 675   valid_pattern ("ed$|(c($(a|b)$))");
 676   valid_pattern ("ed$|(c(($a|b)$))");
 677   valid_pattern ("ed$|(c((a|$b)$))");
 678   valid_pattern ("ed$|$(c((a|b)$))");
 679   valid_pattern ("ed$|($c((a|b)$))");
 680   valid_pattern ("ed$|(c$((a|b)$))");
 681   valid_pattern ("ed$|(c($(a|b)$))");
 682   valid_pattern ("ed$|(c(($a|b)$))");
 683   valid_pattern ("ed$|(c((a|$b)$))");
 684   valid_pattern ("ed$|$(c((a|b)$))");
 685   valid_pattern ("ed$|($c((a|b)$))");
 686   valid_pattern ("ed$|(c$((a|b)$))");
 687   valid_pattern ("ed$|(c($(a|b)$))");
 688   valid_pattern ("ed$|(c(($a|b)$))");
 689   valid_pattern ("ed$|(c((a|$b)$))");
 690   valid_pattern ("ed$|$(c((a|b)$))");
 691   valid_pattern ("ed$|($c((a|b)$))");
 692   valid_pattern ("ed$|(c$((a|b)$))");
 693   valid_pattern ("ed$|(c($(a|b)$))");
 694   valid_pattern ("ed$|(c(($a|b)$))");
 695   valid_pattern ("ed$|(c((a|$b)$))");
 696   valid_pattern ("ed$|$(c((a$|b$)))");
 697   valid_pattern ("ed$|($c((a$|b$)))");
 698   valid_pattern ("ed$|(c$((a$|b$)))");
 699   valid_pattern ("ed$|(c($(a$|b$)))");
 700   valid_pattern ("ed$|(c(($a$|b$)))");
 701   valid_pattern ("ed$|(c((a$|$b$)))");
 702   valid_pattern ("^a(b|c)^|^d");
 703   valid_pattern ("^a(b|c^)|^d");
 704   valid_pattern ("^a(b|^c)|^d");
 705   valid_pattern ("^a(b^|c)|^d");
 706   valid_pattern ("^a(^b|c)|^d");
 707   valid_pattern ("^a^(b|c)|^d");
 708   valid_pattern ("$a(b$|c$)|d$");
 709   valid_pattern ("a$(b$|c$)|d$");
 710   valid_pattern ("a($b$|c$)|d$");
 711   valid_pattern ("a(b$|$c$)|d$");
 712   valid_pattern ("a(b$|c$)|$d$");
 713   valid_pattern ("^(a^)(b|c)|^d");
 714   valid_pattern ("^(a)^(b|c)|^d");
 715   valid_pattern ("^(a)(^b|c)|^d");
 716   valid_pattern ("^(a)(b^|c)|^d");
 717   valid_pattern ("^(a)(b|^c)|^d");
 718   valid_pattern ("^(a)(b|c^)|^d");
 719   valid_pattern ("^(a)(b|c)^|^d");
 720   valid_pattern ("(^a^)(b|c)|^d");
 721   valid_pattern ("(^a)^(b|c)|^d");
 722   valid_pattern ("(^a)(^b|c)|^d");
 723   valid_pattern ("(^a)(b^|c)|^d");
 724   valid_pattern ("(^a)(b|^c)|^d");
 725   valid_pattern ("(^a)(b|c^)|^d");
 726   valid_pattern ("(^a)(b|c)^|^d");
 727
 728   valid_pattern ("(a)(b$|c$)d$");
 729   valid_pattern ("(a)(b|$c)$|d$");
 730   valid_pattern ("(a)($b|c)$|d$");
 731   valid_pattern ("(a)$(b|c)$|d$");
 732   valid_pattern ("(a$)(b|c)$|d$");
 733   valid_pattern ("($a)(b|c)$|d$");
 734   valid_pattern ("$(a)(b|c)$|d$");
 735   valid_pattern ("(b|c)($a)$|d$");
 736   valid_pattern ("(b|c)$(a)$|d$");
 737   valid_pattern ("(b|c$)(a)$|d$");
 738   valid_pattern ("(b|$c)(a)$|d$");
 739   valid_pattern ("(b$|c)(a)$|d$");
 740   valid_pattern ("($b|c)(a)$|d$");
 741   valid_pattern ("$(b|c)(a)$|d$");
 742   valid_pattern ("(b|c)($a$)|d$");
 743   valid_pattern ("(b|c)$(a$)|d$");
 744   valid_pattern ("(b|c$)(a$)|d$");
 745   valid_pattern ("(b|$c)(a$)|d$");
 746   valid_pattern ("(b$|c)(a$)|d$");
 747   valid_pattern ("($b|c)(a$)|d$");
 748   valid_pattern ("$(b|c)(a$)|d$");
 749   valid_pattern ("(a)$(b$|c$)|d$");
 750   valid_pattern ("(a$)(b$|c$)|d$");
 751   valid_pattern ("($a)(b$|c$)|d$");
 752   valid_pattern ("$(a)(b$|c$)|d$");
 753   valid_pattern ("^d|^(b^|c)(a)");
 754   valid_pattern ("^d|^(b|c^)(a)");
 755   valid_pattern ("^d|^(b|c)^(a)");
 756   valid_pattern ("^d|^(b|c)(^a)");
 757   valid_pattern ("^d|^(b|c)(a^)");
 758   valid_pattern ("^d|^(b|c)(a)^");
 759   valid_pattern ("^d|(^b|^c^)(a)");
 760   valid_pattern ("^d|(^b|^c)^(a)");
 761   valid_pattern ("^d|(^b|^c)(^a)");
 762   valid_pattern ("^d|(^b|^c)(a^)");
 763   valid_pattern ("^d|(^b|^c)(a)^");
 764   valid_pattern ("d$|(b|c)($a$)");
 765   valid_pattern ("d$|(b|c)$(a$)");
 766   valid_pattern ("d$|(b|c$)(a$)");
 767   valid_pattern ("d$|(b$|c)(a$)");
 768   valid_pattern ("d$|($b|c)(a$)");
 769   valid_pattern ("d$|$(b|c)(a$)");
 770   valid_pattern ("d$|(b|c)($a)$");
 771   valid_pattern ("d$|(b|c)$(a)$");
 772   valid_pattern ("d$|(b|c$)(a)$");
 773   valid_pattern ("d$|(b$|c)(a)$");
 774   valid_pattern ("d$|($b|c)(a)$");
 775   valid_pattern ("d$|$(b|c)(a)$");
 776   valid_pattern ("^d|^(a^)(b|c)");
 777   valid_pattern ("^d|^(a)^(b|c)");
 778   valid_pattern ("^d|^(a)(^b|c)");
 779   valid_pattern ("^d|^(a)(b^|c)");
 780   valid_pattern ("^d|^(a)(b|^c)");
 781   valid_pattern ("^d|^(a)(b|c^)");
 782   valid_pattern ("^d|^(a)(b|c)^");
 783   valid_pattern ("^d|(^a^)(b|c)");
 784   valid_pattern ("^d|(^a)^(b|c)");
 785   valid_pattern ("^d|(^a)(^b|c)");
 786   valid_pattern ("^d|(^a)(b^|c)");
 787   valid_pattern ("^d|(^a)(b|^c)");
 788   valid_pattern ("^d|(^a)(b|c^)");
 789   valid_pattern ("^d|(^a)(b|c)^");
 790   valid_pattern ("d$|(a)$(b$|c$)");
 791   valid_pattern ("d$|(a$)(b$|c$)");
 792   valid_pattern ("d$|($a)(b$|c$)");
 793   valid_pattern ("d$|$(a)(b$|c$)");
 794   valid_pattern ("d$|(a)(b|$c)$");
 795   valid_pattern ("d$|(a)($b|c)$");
 796   valid_pattern ("d$|(a)$(b|c)$");
 797   valid_pattern ("d$|(a$)(b|c)$");
 798   valid_pattern ("d$|($a)(b|c)$");
 799   valid_pattern ("d$|$(a)(b|c)$");
 800   valid_pattern ("((^a|^b)|^c)|^d^");
 801   valid_pattern ("((^a|^b)|^c)^|^d");
 802   valid_pattern ("((^a|^b)|^c^)|^d");
 803   valid_pattern ("((^a|^b)^|^c)|^d");
 804   valid_pattern ("((^a|^b^)|^c)|^d");
 805   valid_pattern ("((^a^|^b)|^c)|^d");
 806   valid_pattern ("((a|b)|c)|$d$");
 807   valid_pattern ("((a|b)|$c)|d$");
 808   valid_pattern ("((a|$b)|c)|d$");
 809   valid_pattern ("(($a|b)|c)|d$");
 810   valid_pattern ("($(a|b)|c)|d$");
 811   valid_pattern ("$((a|b)|c)|d$");
 812   valid_pattern ("^d^|(c|(a|b))");
 813   valid_pattern ("^d|(c^|(a|b))");
 814   valid_pattern ("^d|(c|(a^|b))");
 815   valid_pattern ("^d|(c|(a|b^))");
 816   valid_pattern ("^d|(c|(a|b)^)");
 817   valid_pattern ("^d|(c|(a|b))^");
 818   valid_pattern ("d$|(c$|(a$|$b$))");
 819   valid_pattern ("d$|(c$|($a$|b$))");
 820   valid_pattern ("d$|($c$|(a$|b$))");
 821   valid_pattern ("d$|$(c$|(a$|b$))");
 822   valid_pattern ("$d$|(c$|(a$|b$))");
 823   valid_pattern ("d$|(c$|(a|$b)$)");
 824   valid_pattern ("d$|(c$|($a|b)$)");
 825   valid_pattern ("d$|($c$|(a|b)$)");
 826   valid_pattern ("d$|$(c$|(a|b)$)");
 827   valid_pattern ("$d$|(c$|(a|b)$)");
 828   valid_pattern ("d$|(c$|(a|$b))$");
 829   valid_pattern ("d$|(c$|($a|b))$");
 830   valid_pattern ("d$|($c$|(a|b))$");
 831   valid_pattern ("d$|$(c$|(a|b))$");
 832   valid_pattern ("$d$|(c$|(a|b))$");
 833   valid_pattern ("^c^|(^a|^b)");
 834   valid_pattern ("^c|(^a^|^b)");
 835   valid_pattern ("^c|(^a|^b^)");
 836   valid_pattern ("^c|(^a|^b)^");
 837   valid_pattern ("c$|(a$|$b$)");
 838   valid_pattern ("c$|($a$|b$)");
 839   valid_pattern ("c$|$(a$|b$)");
 840   valid_pattern ("$c$|(a$|b$)");
 841   valid_pattern ("^d^(c|e((a|b)))");
 842   valid_pattern ("^d(^c|e((a|b)))");
 843   valid_pattern ("^d(c^|e((a|b)))");
 844   valid_pattern ("^d(c|^e((a|b)))");
 845   valid_pattern ("^d(c|e^((a|b)))");
 846   valid_pattern ("^d(c|e(^(a|b)))");
 847   valid_pattern ("^d(c|e((^a|b)))");
 848   valid_pattern ("^d(c|e((a|^b)))");
 849   valid_pattern ("^d(c|e((a|b^)))");
 850   valid_pattern ("^d(c|e((a|b)^))");
 851   valid_pattern ("^d(c|e((a|b))^)");
 852   valid_pattern ("^d(c|e((a|b)))^");
 853   valid_pattern ("d(c$|e($(a$|b$)))");
 854   valid_pattern ("d(c$|e$((a$|b$)))");
 855   valid_pattern ("d(c$|$e((a$|b$)))");
 856   valid_pattern ("d($c$|e((a$|b$)))");
 857   valid_pattern ("d$(c$|e((a$|b$)))");
 858   valid_pattern ("$d(c$|e((a$|b$)))");
 859   valid_pattern ("^d|^a^(b|c)");
 860   valid_pattern ("^d|^a(^b|c)");
 861   valid_pattern ("^d|^a(b^|c)");
 862   valid_pattern ("^d|^a(b|^c)");
 863   valid_pattern ("^d|^a(b|c^)");
 864   valid_pattern ("^d|^a(b|c)^");
 865   valid_pattern ("d$|a($b$|c$)");
 866   valid_pattern ("d$|a$(b$|c$)");
 867   valid_pattern ("d$|$a(b$|c$)");
 868   valid_pattern ("$d$|a(b$|c$)");
 869   valid_pattern ("^d|^(b^|c)a");
 870   valid_pattern ("^d|^(b|c^)a");
 871   valid_pattern ("^d|^(b|c)^a");
 872   valid_pattern ("^d|^(b|c)a^");
 873   valid_pattern ("d$|(b|c)$a$");
 874   valid_pattern ("d$|(b|c$)a$");
 875   valid_pattern ("d$|(b|$c)a$");
 876   valid_pattern ("d$|(b$|c)a$");
 877   valid_pattern ("d$|($b|c)a$");
 878   valid_pattern ("d$|$(b|c)a$");
 879   valid_pattern ("$d$|(b|c)a$");
 880
 881    /* xx Do these use all the valid_nonposix_pattern ones in other_test.c?  */
 882
 883   TEST_SEARCH ("(^a|^b)c", "ac", 0, 2);
 884   TEST_SEARCH ("(^a|^b)c", "bc", 0, 2);
 885   TEST_SEARCH ("c(a$|b$)", "ca", 0, 2);
 886   TEST_SEARCH ("c(a$|b$)", "cb", 0, 2);
 887   TEST_SEARCH ("^(a|b)|^c", "ad", 0, 2);
 888   TEST_SEARCH ("^(a|b)|^c", "bd", 0, 2);
 889   TEST_SEARCH ("(a|b)$|c$", "da", 0, 2);
 890   TEST_SEARCH ("(a|b)$|c$", "db", 0, 2);
 891   TEST_SEARCH ("(a|b)$|c$", "dc", 0, 2);
 892   TEST_SEARCH ("(^a|^b)|^c", "ad", 0, 2);
 893   TEST_SEARCH ("(^a|^b)|^c", "bd", 0, 2);
 894   TEST_SEARCH ("(^a|^b)|^c", "cd", 0, 2);
 895   TEST_SEARCH ("(a$|b$)|c$", "da", 0, 2);
 896   TEST_SEARCH ("(a$|b$)|c$", "db", 0, 2);
 897   TEST_SEARCH ("(a$|b$)|c$", "dc", 0, 2);
 898   TEST_SEARCH ("^c|(^a|^b)", "ad", 0, 2);
 899   TEST_SEARCH ("^c|(^a|^b)", "bd", 0, 2);
 900   TEST_SEARCH ("^c|(^a|^b)", "cd", 0, 2);
 901   TEST_SEARCH ("c$|(a$|b$)", "da", 0, 2);
 902   TEST_SEARCH ("c$|(a$|b$)", "db", 0, 2);
 903   TEST_SEARCH ("c$|(a$|b$)", "dc", 0, 2);
 904   TEST_SEARCH ("^c|^(a|b)", "ad", 0, 2);
 905   TEST_SEARCH ("^c|^(a|b)", "bd", 0, 2);
 906   TEST_SEARCH ("^c|^(a|b)", "cd", 0, 2);
 907   TEST_SEARCH ("c$|(a|b)$", "da", 0, 2);
 908   TEST_SEARCH ("c$|(a|b)$", "db", 0, 2);
 909   TEST_SEARCH ("c$|(a|b)$", "dc", 0, 2);
 910   TEST_SEARCH ("(^a|^b)c|^d", "ace", 0, 3);
 911   TEST_SEARCH ("(^a|^b)c|^d", "bce", 0, 3);
 912   TEST_SEARCH ("(^a|^b)c|^d", "de", 0, 2);
 913   TEST_SEARCH ("(a|b)c$|d$", "eac", 0, 3);
 914   TEST_SEARCH ("(a|b)c$|d$", "ebc", 0, 3);
 915   TEST_SEARCH ("(a|b)c$|d$", "ed", 0, 3);
 916   TEST_SEARCH ("^d|^c(a|b)", "cae", 0, 3);
 917   TEST_SEARCH ("^d|^c(a|b)", "cbe", 0, 3);
 918   TEST_SEARCH ("^d|^c(a|b)", "de", 0, 3);
 919   TEST_SEARCH ("d$|c(a$|b$)", "eca", 0, 3);
 920   TEST_SEARCH ("d$|c(a$|b$)", "ecb", 0, 3);
 921   TEST_SEARCH ("d$|c(a$|b$)", "ed", 0, 3);
 922
 923   TEST_SEARCH ("(((^a|^b))c|^d)e", "acef", 0, 4);
 924   TEST_SEARCH ("(((^a|^b))c|^d)e", "bcef", 0, 4);
 925   TEST_SEARCH ("(((^a|^b))c|^d)e", "def", 0, 3);
 926
 927   TEST_SEARCH ("((^(a|b))c|^d)e", "acef", 0, 4);
 928   TEST_SEARCH ("((^(a|b))c|^d)e", "bcef", 0, 4);
 929   TEST_SEARCH ("((^(a|b))c|^d)e", "def", 0, 3);
 930
 931   TEST_SEARCH ("(^((a|b))c|^d)e", "acef", 0, 4);
 932   TEST_SEARCH ("(^((a|b))c|^d)e", "bcef", 0, 4);
 933   TEST_SEARCH ("(^((a|b))c|^d)e", "def", 0, 3);
 934
 935   TEST_SEARCH ("(((a|b))c|d)e$", "face", 0, 4);
 936   TEST_SEARCH ("(((a|b))c|d)e$", "fbce", 0, 4);
 937   TEST_SEARCH ("(((a|b))c|d)e$", "fde", 0, 3);
 938
 939   TEST_SEARCH ("^e(d|c((a|b)))", "edf", 0, 3);
 940   TEST_SEARCH ("^e(d|c((a|b)))", "ecaf", 0, 4);
 941   TEST_SEARCH ("^e(d|c((a|b)))", "ecbf", 0, 4);
 942
 943   TEST_SEARCH ("e(d$|c((a$|b$)))", "fed", 0, 3);
 944   TEST_SEARCH ("e(d$|c((a$|b$)))", "feca", 0, 4);
 945   TEST_SEARCH ("e(d$|c((a$|b$)))", "fecb", 0, 4);
 946
 947   TEST_SEARCH ("e(d$|c((a|b)$))", "fed", 0, 3);
 948   TEST_SEARCH ("e(d$|c((a|b)$))", "feca", 0, 4);
 949   TEST_SEARCH ("e(d$|c((a|b)$))", "fecb", 0, 4);
 950
 951   TEST_SEARCH ("e(d$|c((a|b))$)", "fed", 0, 3);
 952   TEST_SEARCH ("e(d$|c((a|b))$)", "feca", 0, 3);
 953   TEST_SEARCH ("e(d$|c((a|b))$)", "fecb", 0, 3);
 954
 955   TEST_SEARCH ("e(d$|c((a|b)))$", "fed", 0, 3);
 956   TEST_SEARCH ("e(d$|c((a|b)))$", "feca", 0, 3);
 957   TEST_SEARCH ("e(d$|c((a|b)))$", "fecb", 0, 3);
 958
 959   TEST_SEARCH ("(((^a|^b))c)|^de", "acf", 0, 3);
 960   TEST_SEARCH ("(((^a|^b))c)|^de", "bcf", 0, 3);
 961   TEST_SEARCH ("(((^a|^b))c)|^de", "def", 0, 3);
 962
 963   TEST_SEARCH ("(((a|b))c$)|de$", "fac", 0, 3);
 964   TEST_SEARCH ("(((a|b))c$)|de$", "fbc", 0, 3);
 965   TEST_SEARCH ("(((a|b))c$)|de$", "fde", 0, 3);
 966
 967   TEST_SEARCH ("(((a|b))c)$|de$", "fac", 0, 3);
 968   TEST_SEARCH ("(((a|b))c)$|de$", "fbc", 0, 3);
 969   TEST_SEARCH ("(((a|b))c)$|de$", "fde", 0, 3);
 970
 971   TEST_SEARCH ("^ed|^(c((a|b)))", "edf", 0, 3);
 972   TEST_SEARCH ("^ed|^(c((a|b)))", "caf", 0, 3);
 973   TEST_SEARCH ("^ed|^(c((a|b)))", "cbf", 0, 3);
 974
 975   TEST_SEARCH ("^ed|(^c((a|b)))", "edf", 0, 3);
 976   TEST_SEARCH ("^ed|(^c((a|b)))", "caf", 0, 3);
 977   TEST_SEARCH ("^ed|(^c((a|b)))", "cbf", 0, 3);
 978
 979   TEST_SEARCH ("ed$|(c((a|b)))$", "fed", 0, 3);
 980   TEST_SEARCH ("ed$|(c((a|b)))$", "fca", 0, 3);
 981   TEST_SEARCH ("ed$|(c((a|b)))$", "fcb", 0, 3);
 982
 983   TEST_SEARCH ("ed$|(c((a|b))$)", "fed", 0, 3);
 984   TEST_SEARCH ("ed$|(c((a|b))$)", "fca", 0, 3);
 985   TEST_SEARCH ("ed$|(c((a|b))$)", "fcb", 0, 3);
 986
 987   TEST_SEARCH ("ed$|(c((a|b)$))", "fed", 0, 3);
 988   TEST_SEARCH ("ed$|(c((a|b)$))", "fca", 0, 3);
 989   TEST_SEARCH ("ed$|(c((a|b)$))", "fcb", 0, 3);
 990
 991   TEST_SEARCH ("ed$|(c((a$|b$)))", "fed", 0, 3);
 992   TEST_SEARCH ("ed$|(c((a$|b$)))", "fca", 0, 3);
 993   TEST_SEARCH ("ed$|(c((a$|b$)))", "fcb", 0, 3);
 994
 995   TEST_SEARCH ("^a(b|c)|^d", "abe", 0, 3);
 996   TEST_SEARCH ("^a(b|c)|^d", "ace", 0, 3);
 997   TEST_SEARCH ("^a(b|c)|^d", "df", 0, 2);
 998
 999   TEST_SEARCH ("a(b$|c$)|d$", "fab", 0, 3);
1000   TEST_SEARCH ("a(b$|c$)|d$", "fac", 0, 3);
1001   TEST_SEARCH ("a(b$|c$)|d$", "fd", 0, 2);
1002
1003   TEST_SEARCH ("^(a)(b|c)|^d", "abe", 0, 3);
1004   TEST_SEARCH ("^(a)(b|c)|^d", "ace", 0, 3);
1005   TEST_SEARCH ("^(a)(b|c)|^d", "df", 0, 2);
1006
1007   TEST_SEARCH ("(^a)(b|c)|^d", "abe", 0, 3);
1008   TEST_SEARCH ("(^a)(b|c)|^d", "ace", 0, 3);
1009   TEST_SEARCH ("(^a)(b|c)|^d", "df", 0, 2);
1010
1011   TEST_SEARCH ("(a)(b|c)$|d$", "fab", 0, 3);
1012   TEST_SEARCH ("(a)(b|c)$|d$", "fac", 0, 3);
1013   TEST_SEARCH ("(a)(b|c)$|d$", "fd", 0, 2);
1014
1015   TEST_SEARCH ("(b|c)(a)$|d$", "fba", 0, 3);
1016   TEST_SEARCH ("(b|c)(a)$|d$", "fca", 0, 3);
1017   TEST_SEARCH ("(b|c)(a)$|d$", "fd", 0, 2);
1018
1019   TEST_SEARCH ("(b|c)(a$)|d$", "fba", 0, 3);
1020   TEST_SEARCH ("(b|c)(a$)|d$", "fca", 0, 3);
1021   TEST_SEARCH ("(b|c)(a$)|d$", "fd", 0, 2);
1022
1023   TEST_SEARCH ("(a)(b$|c$)|d$", "fab", 0, 3);
1024   TEST_SEARCH ("(a)(b$|c$)|d$", "fac", 0, 3);
1025   TEST_SEARCH ("(a)(b$|c$)|d$", "fd", 0, 2);
1026
1027   TEST_SEARCH ("^d|^(b|c)(a)", "df", 0, 2);
1028   TEST_SEARCH ("^d|^(b|c)(a)", "baf", 0, 3);
1029   TEST_SEARCH ("^d|^(b|c)(a)", "caf", 0, 3);
1030
1031   TEST_SEARCH ("^d|(^b|^c)(a)", "df", 0, 2);
1032   TEST_SEARCH ("^d|(^b|^c)(a)", "baf", 0, 3);
1033   TEST_SEARCH ("^d|(^b|^c)(a)", "caf", 0, 3);
1034
1035   TEST_SEARCH ("d$|(b|c)(a$)", "fd", 0, 2);
1036   TEST_SEARCH ("d$|(b|c)(a$)", "fba", 0, 3);
1037   TEST_SEARCH ("d$|(b|c)(a$)", "fca", 0, 3);
1038
1039   TEST_SEARCH ("d$|(b|c)(a)$", "fd", 0, 2);
1040   TEST_SEARCH ("d$|(b|c)(a)$", "fba", 0, 3);
1041   TEST_SEARCH ("d$|(b|c)(a)$", "fca", 0, 3);
1042
1043   TEST_SEARCH ("d$|(b|c)(a$)", "fd", 0, 2);
1044   TEST_SEARCH ("d$|(b|c)(a$)", "fba", 0, 3);
1045   TEST_SEARCH ("d$|(b|c)(a$)", "fca", 0, 3);
1046
1047   TEST_SEARCH ("^d|^(a)(b|c)", "df", 0, 2);
1048   TEST_SEARCH ("^d|^(a)(b|c)", "abf", 0, 3);
1049   TEST_SEARCH ("^d|^(a)(b|c)", "acf", 0, 3);
1050
1051   TEST_SEARCH ("^d|(^a)(b|c)", "df", 0, 2);
1052   TEST_SEARCH ("^d|(^a)(b|c)", "abf", 0, 3);
1053   TEST_SEARCH ("^d|(^a)(b|c)", "acf", 0, 3);
1054
1055   TEST_SEARCH ("d$|(a)(b$|c$)", "fd", 0, 2);
1056   TEST_SEARCH ("d$|(a)(b$|c$)", "fab", 0, 3);
1057   TEST_SEARCH ("d$|(a)(b$|c$)", "fac", 0, 3);
1058
1059   TEST_SEARCH ("d$|(a)(b|c)$", "fd", 0, 2);
1060   TEST_SEARCH ("d$|(a)(b|c)$", "fab", 0, 3);
1061   TEST_SEARCH ("d$|(a)(b|c)$", "fac", 0, 3);
1062
1063   TEST_SEARCH ("((^a|^b)|^c)|^d", "ae", 0, 2);
1064   TEST_SEARCH ("((^a|^b)|^c)|^d", "be", 0, 2);
1065   TEST_SEARCH ("((^a|^b)|^c)|^d", "ce", 0, 2);
1066   TEST_SEARCH ("((^a|^b)|^c)|^d", "de", 0, 2);
1067
1068   TEST_SEARCH ("((a|b)|c)|d$", "ed", 0, 2);
1069   TEST_SEARCH ("((a|b)|c)|d$", "ea", 0, 2);
1070   TEST_SEARCH ("((a|b)|c)|d$", "eb", 0, 2);
1071   TEST_SEARCH ("((a|b)|c)|d$", "ec", 0, 2);
1072
1073   TEST_SEARCH ("^d|(c|(a|b))", "de", 0, 2);
1074
1075   TEST_SEARCH ("d$|(c$|(a$|b$))", "ed", 0, 2);
1076   TEST_SEARCH ("d$|(c$|(a$|b$))", "ec", 0, 2);
1077   TEST_SEARCH ("d$|(c$|(a$|b$))", "ea", 0, 2);
1078   TEST_SEARCH ("d$|(c$|(a$|b$))", "eb", 0, 2);
1079
1080   TEST_SEARCH ("d$|(c$|(a|b)$)", "ed", 0, 2);
1081   TEST_SEARCH ("d$|(c$|(a|b)$)", "ec", 0, 2);
1082   TEST_SEARCH ("d$|(c$|(a|b)$)", "ea", 0, 2);
1083   TEST_SEARCH ("d$|(c$|(a|b)$)", "eb", 0, 2);
1084
1085   TEST_SEARCH ("d$|(c$|(a|b))$", "ed", 0, 2);
1086   TEST_SEARCH ("d$|(c$|(a|b))$", "ec", 0, 2);
1087   TEST_SEARCH ("d$|(c$|(a|b))$", "ea", 0, 2);
1088   TEST_SEARCH ("d$|(c$|(a|b))$", "eb", 0, 2);
1089
1090   test_match ("a|^b", "b");
1091   test_match ("a|b$", "b");
1092   test_match ("^b|a", "b");
1093   test_match ("b$|a", "b");
1094   test_match ("(^a)", "a");
1095   test_match ("(a$)", "a");
1096   TEST_SEARCH ("c|^ab", "aba", 0, 3);
1097   TEST_SEARCH ("c|ba$", "aba", 0, 3);
1098   TEST_SEARCH ("^ab|c", "aba", 0, 3);
1099   TEST_SEARCH ("ba$|c", "aba", 0, 3);
1100   TEST_SEARCH ("(^a)", "ab", 0, 2);
1101   TEST_SEARCH ("(a$)", "ba", 0, 2);
1102
1103   TEST_SEARCH ("(^a$)", "a", 0, 1);
1104   TEST_SEARCH ("(^a)", "ab", 0, 2);
1105   TEST_SEARCH ("(b$)", "ab", 0, 2);
1106
1107                                                 /* Backtracking.  */
1108   /* Per POSIX D11.1 p. 108, leftmost longest match.  */
1109   test_match ("(wee|week)(knights|night)", "weeknights");
1110
1111   test_match ("(fooq|foo)qbar", "fooqbar");
1112   test_match ("(fooq|foo)(qbarx|bar)", "fooqbarx");
1113
1114   /* Take first alternative that does the longest match.  */
1115   test_all_registers ("(fooq|(foo)|(fo))((qbarx)|(oqbarx)|bar)", "fooqbarx",
1116     "", 0, 8,  0, 3,  0, 3,  -1, -1,  3, 8,  3, 8,  -1, -1,  -1, -1, -1, -1,
1117     -1, -1);
1118
1119   test_match ("(fooq|foo)*qbar", "fooqbar");
1120   test_match ("(fooq|foo)*(qbar)", "fooqbar");
1121   test_match ("(fooq|foo)*(qbar)*", "fooqbar");
1122
1123   test_match ("(fooq|fo|o)*qbar", "fooqbar");
1124   test_match ("(fooq|fo|o)*(qbar)", "fooqbar");
1125   test_match ("(fooq|fo|o)*(qbar)*", "fooqbar");
1126
1127   test_match ("(fooq|fo|o)*(qbar|q)*", "fooqbar");
1128   test_match ("(fooq|foo)*(qbarx|bar)", "fooqbarx");
1129   test_match ("(fooq|foo)*(qbarx|bar)*", "fooqbarx");
1130
1131   test_match ("(fooq|fo|o)+(qbar|q)+", "fooqbar");
1132   test_match ("(fooq|foo)+(qbarx|bar)", "fooqbarx");
1133   test_match ("(fooq|foo)+(qbarx|bar)+", "fooqbarx");
1134
1135   /* Per Mike Haertel.  */
1136   test_match ("(foo|foobarfoo)(bar)*", "foobarfoo");
1137
1138                                                 /* Combination.  */
1139   test_match ("[ab]?c", "ac");
1140   test_match ("[ab]*c", "ac");
1141   test_match ("[ab]+c", "ac");
1142   test_match ("(a|b)?c", "ac");
1143   test_match ("(a|b)*c", "ac");
1144   test_match ("(a|b)+c", "ac");
1145   test_match ("(a*c)?b", "b");
1146   test_match ("(a*c)+b", "aacb");
1147                                                 /* Registers.  */
1148   /* Per David A. Willcox.  */
1149   test_match ("a((b)|(c))d", "acd");
1150   test_all_registers ("a((b)|(c))d", "acd", "", 0, 3, 1, 2, -1, -1, 1, 2,
1151     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1);
1152
1153
1154   /* Extended regular expressions, continued; these don't match their strings.  */
1155   test_should_match = false;
1156
1157 #if 0
1158                                 /* Invalid use of special characters.  */
1159   /* These are not invalid anymore, since POSIX says the behavior is
1160      undefined, and we prefer context-independent to context-invalid.  */
1161   invalid_pattern (REG_BADRPT, "*");
1162   invalid_pattern (REG_BADRPT, "a|*");
1163   invalid_pattern (REG_BADRPT, "(*)");
1164   invalid_pattern (REG_BADRPT, "^*");
1165   invalid_pattern (REG_BADRPT, "+");
1166   invalid_pattern (REG_BADRPT, "a|+");
1167   invalid_pattern (REG_BADRPT, "(+)");
1168   invalid_pattern (REG_BADRPT, "^+");
1169
1170   invalid_pattern (REG_BADRPT, "?");
1171   invalid_pattern (REG_BADRPT, "a|?");
1172   invalid_pattern (REG_BADRPT, "(?)");
1173   invalid_pattern (REG_BADRPT, "^?");
1174
1175   invalid_pattern (REG_BADPAT, "|");
1176   invalid_pattern (REG_BADPAT, "a|");
1177   invalid_pattern (REG_BADPAT, "a||");
1178   invalid_pattern (REG_BADPAT, "(|a)");
1179   invalid_pattern (REG_BADPAT, "(a|)");
1180
1181   invalid_pattern (REG_BADPAT, PARENS_TO_OPS ("(|)"));
1182
1183   invalid_pattern (REG_BADRPT, "{1}");
1184   invalid_pattern (REG_BADRPT, "a|{1}");
1185   invalid_pattern (REG_BADRPT, "^{1}");
1186   invalid_pattern (REG_BADRPT, "({1})");
1187
1188   invalid_pattern (REG_BADPAT, "|b");
1189
1190   invalid_pattern (REG_BADRPT, "^{0,}*");
1191   invalid_pattern (REG_BADRPT, "$*");
1192   invalid_pattern (REG_BADRPT, "${0,}*");
1193 #endif /* 0 */
1194
1195   invalid_pattern (REG_EESCAPE, "\\");
1196
1197   test_match ("a?b", "a");
1198
1199
1200   test_match ("a+", "");
1201   test_match ("a+b", "a");
1202   test_match ("a?", "b");
1203
1204 #if 0
1205   /* We make empty groups valid now, since they are undefined in POSIX.
1206     (13 Sep 92) */
1207                                                 /* Subexpressions.  */
1208   invalid_pattern (REG_BADPAT, "()");
1209   invalid_pattern (REG_BADPAT, "a()");
1210   invalid_pattern (REG_BADPAT, "()b");
1211   invalid_pattern (REG_BADPAT, "a()b");
1212   invalid_pattern (REG_BADPAT, "()*");
1213   invalid_pattern (REG_BADPAT, "(()*");
1214 #endif
1215                                                 /* Invalid intervals.  */
1216   test_match ("a{2}*", "aaa");
1217   test_match ("a{2}?", "aaa");
1218   test_match ("a{2}+", "aaa");
1219   test_match ("a{2}{2}", "aaa");
1220   test_match ("a{1}{1}{2}", "aaa");
1221   test_match ("a{1}{1}{2}", "a");
1222                                                 /* Invalid alternation.  */
1223   test_match ("a|b", "c");
1224
1225   TEST_SEARCH ("c|^ba", "aba", 0, 3);
1226   TEST_SEARCH ("c|ab$", "aba", 0, 3);
1227   TEST_SEARCH ("^ba|c", "aba", 0, 3);
1228   TEST_SEARCH ("ab$|c", "aba", 0, 3);
1229                                                 /* Invalid anchoring.  */
1230   TEST_SEARCH ("(^a)", "ba", 0, 2);
1231   TEST_SEARCH ("(b$)", "ba", 0, 2);
1232
1233   printf ("\nFinished POSIX extended tests.\n");
1234 }
1235
1236
1237 \f
1238 /*
1239 Local variables:
1240 make-backup-files: t
1241 version-control: t
1242 trim-versions-without-asking: nil
1243 End:
1244 */