psx-extend.c

正则表达式库

/* psx-extend.c: Test POSIX extended regular expressions.  */

#include "test.h"


void
test_posix_extended ()
{
  /* Intervals can only match up to RE_DUP_MAX occurences of anything.  */
  char dup_max_plus_one[6];
  sprintf (dup_max_plus_one, "%d", RE_DUP_MAX + 1);


  printf ("\nStarting POSIX extended tests.\n");
  t = posix_extended_test;
  
  re_set_syntax (RE_SYNTAX_POSIX_MINIMAL_EXTENDED);  

  test_posix_generic ();

  printf ("\nContinuing POSIX extended tests.\n");

  /* Grouping tests that differ from basic's.  */
  
  test_should_match = true;
  MATCH_SELF ("a)");

                                /* Valid use of special characters.  */
  test_match ("\\(a", "(a");
  test_match ("a\\+", "a+");
  test_match ("a\\?", "a?");
  test_match ("\\{a", "{a");
  test_match ("\\|a", "|a");
  test_match ("a\\|b", "a|b");
  test_match ("a\\|?", "a");
  test_match ("a\\|?", "a|");
  test_match ("a\\|*", "a");
  test_match ("a\\|*", "a||");
  test_match ("\\(*\\)", ")");
  test_match ("\\(*\\)", "(()");
  test_match ("a\\|+", "a|");
  test_match ("a\\|+", "a||");
  test_match ("\\(+\\)", "()");
  test_match ("\\(+\\)", "(()");
  test_match ("a\\||b", "a|");
  test_match ("\\(?\\)", ")");
  test_match ("\\(?\\)", "()");

  test_match ("a+", "a");
  test_match ("a+", "aa");
  test_match ("a?", "");
  test_match ("a?", "a");

                                                /* Bracket expressions.  */
  test_match ("[(]", "(");
  test_match ("[+]", "+");
  test_match ("[?]", "?");
  test_match ("[{]", "{");
  test_match ("[|]", "|");
                                                /* Subexpressions.  */
  test_match ("(a+)*", "");
  test_match ("(a+)*", "aa");
  test_match ("(a?)*", "");
  test_match ("(a?)*", "aa");
                                                /* (No) back references.  */
  test_match ("(a)\\1", "a1");
                                                /* Invalid as intervals,
                                                   but are valid patterns.  */
  MATCH_SELF ("{");
  test_match ("^{", "{");
  test_match ("a|{", "{");
  test_match ("({)", "{");
  MATCH_SELF ("a{");
  MATCH_SELF ("a{}");
  MATCH_SELF ("a{-1");
  MATCH_SELF ("a{-1}");
  MATCH_SELF ("a{0");            
  MATCH_SELF ("a{0,"); 
  MATCH_SELF (concat ("a{", dup_max_plus_one));
  MATCH_SELF (concat (concat ("a{", dup_max_plus_one), ","));
  MATCH_SELF ("a{1,0");
  MATCH_SELF ("a{1,0}");
  MATCH_SELF ("a{0,1");
  test_match ("[a{0,1}]", "}");
  test_match ("a{1,3}{-1}", "aaa{-1}");
  test_match (concat ("a{1,3}{", dup_max_plus_one), 
	      concat ("aaa{", dup_max_plus_one));
  test_match ("a{1,3}{2,1}", "aaa{2,1}");
  test_match ("a{1,3}{1,2", "aaa{1,2");
					/* Valid consecutive repetitions.  */
  test_match ("a*+", "a");
  test_match ("a*?", "a");
  test_match ("a++", "a");
  test_match ("a+*", "a");
  test_match ("a+?", "a");
  test_match ("a??", "a");
  test_match ("a?*", "a");
  test_match ("a?+", "a");
  
  test_match ("a{2}?", "");
  test_match ("a{2}?", "aa");
  test_match ("a{2}+", "aa");
  test_match ("a{2}{2}", "aaaa");

  test_match ("a{1}?*", "");
  test_match ("a{1}?*", "aa");
  
  test_match ("(a?){0,3}b", "aaab"); 
  test_fastmap ("(a?){0,3}b", "ab", 0, 0); 
  test_match ("(a+){0,3}b", "b"); 
  test_fastmap ("(a+){0,3}b", "ab", 0, 0); 
  test_match ("(a+){0,3}b", "ab");
  test_fastmap ("(a+){0,3}b", "ab", 0, 0); 
  test_match ("(a+){1,3}b", "aaab"); 
  test_match ("(a?){1,3}b", "aaab");

  test_match ("\\\\{1}", "\\");				/* Extended only.  */

  test_match ("(a?)?", "a");
  test_match ("(a?b)?c", "abc");
  test_match ("(a+)*b", "b"); 
						/* Alternatives.  */
  test_match ("a|b", "a");
  test_match ("a|b", "b");
  test_fastmap ("a|b", "ab", 0, 0);

  TEST_SEARCH ("a|b", "cb", 0, 2);
  TEST_SEARCH ("a|b", "cb", 0, 2);

  test_match ("(a|b|c)", "a");
  test_match ("(a|b|c)", "b");
  test_match ("(a|b|c)", "c");

  test_match ("(a|b|c)*", "abccba");
  
  test_match ("(a(b*))|c", "a");	/* xx do registers.  */
  test_match ("(a(b*))|c", "ab");
  test_match ("(a(b*))|c", "c");

  test_fastmap ("(a+?*|b)", "ab", 0, 0);
  test_match ("(a+?*|b)", "b");
  TEST_REGISTERS ("(a+?*|b)", "b", 0, 1, 0, 1, -1, -1);
  
  test_fastmap ("(a+?*|b)*", "ab", 0, 0);
  test_match ("(a+?*|b)*", "bb");
  TEST_REGISTERS ("(a+?*|b)*", "bb", 0, 2, 1, 2, -1, -1);

  test_fastmap ("(a*|b)*", "ab", 0, 0);
  test_match ("(a*|b)*", "bb");
  TEST_REGISTERS ("(a*|b)*", "bb", 0, 2, 1, 2, -1, -1);

  test_fastmap ("((a*)|b)*", "ab", 0, 0);
  test_match ("((a*)|b)*", "bb");
  TEST_REGISTERS ("((a*)|b)*", "bb", 0, 2, 1, 2, 1, 1);

  test_fastmap ("(a{0,}|b)*", "ab", 0, 0);
  test_match ("(a{0,}|b)*", "bb");
  TEST_REGISTERS ("(a{0,}|b)*", "bb", 0, 2, 1, 2, -1, -1);

  test_fastmap ("((a{0,})|b)*", "ab", 0, 0);
  test_match ("((a{0,})|b)*", "bb");
  TEST_REGISTERS ("((a{0,})|b)*", "bb", 0, 2, 1, 2, 1, 1);

						/* With c's  */
  test_fastmap ("(a+?*|b)c", "abc", 0, 0);
  test_match ("(a+?*|b)c", "bc");
  TEST_REGISTERS ("(a+?*|b)c", "bc", 0, 2, 0, 1, -1, -1);
  
  test_fastmap ("(a+?*|b)*c", "abc", 0, 0);
  test_match ("(a+?*|b)*c", "bbc");
  TEST_REGISTERS ("(a+?*|b)*c", "bbc", 0, 3, 1, 2, -1, -1);

  test_fastmap ("(a*|b)*c", "abc", 0, 0);
  test_match ("(a*|b)*c", "bbc");
  TEST_REGISTERS ("(a*|b)*c", "bbc", 0, 3, 1, 2, -1, -1);

  test_fastmap ("((a*)|b)*c", "abc", 0, 0);
  test_match ("((a*)|b)*c", "bbc");
  TEST_REGISTERS ("((a*)|b)*c", "bbc", 0, 3, 1, 2, 1, 1);

  test_fastmap ("(a{0,}|b)*c", "abc", 0, 0);
  test_match ("(a{0,}|b)*c", "bbc");
  TEST_REGISTERS ("(a{0,}|b)*c", "bbc", 0, 3, 1, 2, -1, -1);

  test_fastmap ("((a{0,})|b)*c", "abc", 0, 0);
  test_match ("((a{0,})|b)*c", "bbc");
  TEST_REGISTERS ("((a{0,})|b)*c", "bbc", 0, 3, 1, 2, 1, 1);


  test_fastmap ("((a{0,}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a{0,}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a{0,}\\b\\<)|b)", "b", 
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a{0,}\\b\\<)|b)*", "ab", 0, 0);
  test_match ("((a{0,}\\b\\<)|b)*", "b");
  TEST_REGISTERS ("((a{0,}\\b\\<)|b)*", "b", 
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,1}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,1}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,1}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,2}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,2}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,2}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);


  test_fastmap ("((a+?*{0,4095}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,4095}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,4095}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,5119}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,5119}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,5119}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,6143}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,6143}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,6143}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,8191}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,8191}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,8191}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,16383}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,16383}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,16383}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);


  test_fastmap ("((a+?*{0,}\\b\\<)|b)", "ab", 0, 0);
  test_match ("((a+?*{0,}\\b\\<)|b)", "b");
  TEST_REGISTERS ("((a+?*{0,}\\b\\<)|b)", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,}\\b\\<)|b)*", "ab", 0, 0);
  test_match ("((a+?*{0,}\\b\\<)|b)*", "b");
  TEST_REGISTERS ("((a+?*{0,}\\b\\<)|b)*", "b",
    0, 1, 0, 1, 0, 0);

  test_fastmap ("((a+?*{0,}\\b\\<)|b)*", "ab", 0, 0);
  test_match ("((a+?*{0,}\\b\\<)|b)*", "bb");
  TEST_REGISTERS ("((a+?*{0,}\\b\\<)|b)*", "bb",
    0, 2, 1, 2, 0, 0);


				/* `*' after group.  */
  test_match ("(a*|b*)*c", "c");	
  TEST_REGISTERS ("(a*|b*)*c", "c", 0, 1, 0, 0, -1, -1);

  test_match ("(a*|b*)*c", "ac");
  TEST_REGISTERS ("(a*|b*)*c", "ac", 0, 2, 0, 1, -1, -1);

  test_match ("(a*|b*)*c", "aac");
  TEST_REGISTERS ("(a*|b*)*c", "aac", 0, 3, 0, 2, -1, -1);

  test_match ("(a*|b*)*c", "bbc");
  TEST_REGISTERS ("(a*|b*)*c", "bbc", 0, 3, 0, 2, -1, -1);

  test_match ("(a*|b*)*c", "abc");
  TEST_REGISTERS ("(a*|b*)*c", "abc", 0, 3, 1, 2, -1, -1);

				/* No `*' after group.  */
  test_match ("(a*|b*)c", "c");
  TEST_REGISTERS ("(a*|b*)c", "c", 0, 1, 0, 0, -1, -1);

  test_match ("(a*|b*)c", "ac");
  TEST_REGISTERS ("(a*|b*)c", "ac", 0, 2, 0, 1, -1, -1);

  test_match ("(a*|b*)c", "bc");
  TEST_REGISTERS ("(a*|b*)c", "bc", 0, 2, 0, 1, -1, -1);

  test_match ("(a*|b*)c", "aac");
  TEST_REGISTERS ("(a*|b*)c", "aac", 0, 3, 0, 2, -1, -1);

  /* Same as above, but with no `*'s in alternatives. 
  
  test_match ("(a|b)*c", "c");		/* `*' after group.  */
  TEST_REGISTERS ("(a|b)*c", "c", 0, 1, -1, -1, -1, -1);

  test_match ("(a|b)*c", "ac");
  TEST_REGISTERS ("(a|b)*c", "ac", 0, 2, 0, 1, -1, -1);

  test_match ("(a|b)*c", "bc");
  TEST_REGISTERS ("(a|b)*c", "bc", 0, 2, 0, 1, -1, -1);

  test_match ("(a|b)*c", "abc");
  TEST_REGISTERS ("(a|b)*c", "abc", 0, 3, 1, 2, -1, -1);


  test_match ("(a*|b*)c", "bbc");
  TEST_REGISTERS ("(a*|b*)c", "bbc", 0, 3, 0, 2, -1, -1);

  /* Complicated second alternative.  */
  
  test_match ("(a*|(b*)*)*c", "bc");
  TEST_REGISTERS ("(a*|(b*)*)*c", "bc", 0, 2, 0, 1, 0, 1);

  test_match ("(a*|(b*|c*)*)*d", "bd");
  TEST_REGISTERS ("(a*|(b*|c*)*)*d", "bd", 0, 2, 0, 1, 0, 1);

  test_match ("(a*|(b*|c*)*)*d", "bbd");
  TEST_REGISTERS ("(a*|(b*|c*)*)*d", "bbd", 0, 3, 0, 2, 0, 2);

  test_match ("(a*|(b*|c*)*)*d", "cd");
  TEST_REGISTERS ("(a*|(b*|c*)*)*d", "cd", 0, 2, 0, 1, 0, 1);

  test_match ("(a*|(b*|c*)*)*d", "ccd");
  TEST_REGISTERS ("(a*|(b*|c*)*)*d", "ccd", 0, 3, 0, 2, 0, 2);

  test_match ("(a*|b*|c*)*d", "aad");
  TEST_REGISTERS ("(a*|b*|c*)*d", "aad", 0, 3, 0, 2, 0, 2);

  test_match ("(a*|b*|c*)*d", "bbd");
  TEST_REGISTERS ("(a*|b*|c*)*d", "bbd", 0, 3, 0, 2, 0, 2);

  test_match ("(a*|b*|c*)*d", "ccd");
  TEST_REGISTERS ("(a*|b*|c*)*d", "ccd", 0, 3, 0, 2, 0, 2);

						/* Valid anchoring.  */
  valid_pattern ("a^");
  valid_pattern ("a^b");
  valid_pattern ("$a");
  valid_pattern ("a$b");
  valid_pattern ("foo^bar");
  valid_pattern ("foo$bar");
  valid_pattern ("(^)");
  valid_pattern ("($)");
  valid_pattern ("(^$)");

      /* These are the same (but valid) as those (invalid) in other_test.c.  */
  valid_pattern 
    ("(((((((((((((((((((((((((((((((((a^)))))))))))))))))))))))))))))))))");
  valid_pattern 
    ("((((((((((((((((((((((((((((((((($a)))))))))))))))))))))))))))))))))");
  valid_pattern ("\\(^a\\)");
  valid_pattern ("a\\|^b");
  valid_pattern ("\\w^a");
  valid_pattern ("\\W^a");
  valid_pattern ("(a^)");
  valid_pattern ("($a)");
  valid_pattern ("a(^b)");
  valid_pattern ("a$(b)");
  valid_pattern ("(a)^b");
  valid_pattern ("(a)$b");
  valid_pattern ("(a)(^b)");
  valid_pattern ("(a$)(b)");
  valid_pattern ("(a|b)^c");
  valid_pattern ("(a|b)$c");
  valid_pattern ("(a$|b)c");
  valid_pattern ("(a|b$)c");
  valid_pattern ("a(b|^c)");
  valid_pattern ("a(^b|c)");
  valid_pattern ("a$(b|c)");
  valid_pattern ("(a)(^b|c)");
  valid_pattern ("(a)(b|^c)");
  valid_pattern ("(b$|c)(a)");
  valid_pattern ("(b|c$)(a)");
  valid_pattern ("(a(^b|c))");
  valid_pattern ("(a(b|^c))");
  valid_pattern ("((b$|c)a)");
  valid_pattern ("((b|c$)a)");
  valid_pattern ("((^a|^b)^c)");
  valid_pattern ("(c$(a$|b$))");
  valid_pattern ("((^a|^b)^c)");
  valid_pattern ("((a$|b$)c)");
  valid_pattern ("(c$(a$|b$))");
  valid_pattern ("((^a|^b)|^c)^d");
  valid_pattern ("((a$|b$)|c$)d$");
  valid_pattern ("d$(c$|(a$|b$))");
  valid_pattern ("((^a|^b)|^c)(^d)");
  valid_pattern ("((a$|b$)|c$)(d$)");
  valid_pattern ("(d$)((a$|b$)|c$)");
  valid_pattern ("((^a|^b)|^c)((^d))");
  valid_pattern ("((a$|b$)|c$)((d$))");
  valid_pattern ("((d$))((a$|b$)|c$)");
  valid_pattern ("(((^a|^b))c|^d)^e");
  valid_pattern ("(((a$|b$))c|d$)$e$");
  valid_pattern ("e$(d$|c((a$|b$)))");
  valid_pattern ("(^a)((^b))");
  valid_pattern ("(a$)((b$))");
  valid_pattern ("((^a))(^b)");
  valid_pattern ("((a$))(b$)");
  valid_pattern ("((^a))((^b))");
  valid_pattern ("((a$))((b$))");
  valid_pattern ("((^a)^b)");
  valid_pattern ("((a$)b$)");
  valid_pattern ("(b$(a$))");
  valid_pattern ("(((^a)b)^c)");
  valid_pattern ("(((a$)b)c$)");
  valid_pattern ("(c$(b(a$)))");
  valid_pattern ("(((^a)b)c)^d");
  valid_pattern ("(((a$)b)c)d$");
  valid_pattern ("d$(c(b(a$)))");
  valid_pattern (".^a");
  valid_pattern ("a$.");
  valid_pattern ("[a]^b");
  valid_pattern ("b$[a]");
  valid_pattern ("\\(a$\\)");
  valid_pattern ("a$\\|b");
  valid_pattern ("(^a|^b)^c");
  valid_pattern ("c$(a$|b$)");
  valid_pattern ("(^a|^b)^|^c");
  valid_pattern ("(a$|b$)$|$c$");
  valid_pattern ("(a$|$b$)$|c$");
  valid_pattern ("($a$|b$)$|c$");
  valid_pattern ("$(a$|b$)$|c$");
  valid_pattern ("^c|d(^a|^b)");
  valid_pattern ("(^a|^b)|d^c");