home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1993 #1 / MONSTER.ISO / prog / gen / regex011.taz / regex011 / regex-0.11 / test / psx-extend.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-13  |  41.1 KB  |  1,245 lines
  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.  
  1238. /*
  1239. Local variables:
  1240. make-backup-files: t
  1241. version-control: t
  1242. trim-versions-without-asking: nil
  1243. End:
  1244. */
  1245.