psx-extend.c

正则表达式库

  valid_pattern ("d$|$(c$|(a|b))$");
  valid_pattern ("$d$|(c$|(a|b))$");
  valid_pattern ("^c^|(^a|^b)");
  valid_pattern ("^c|(^a^|^b)");
  valid_pattern ("^c|(^a|^b^)");
  valid_pattern ("^c|(^a|^b)^");
  valid_pattern ("c$|(a$|$b$)");
  valid_pattern ("c$|($a$|b$)");
  valid_pattern ("c$|$(a$|b$)");
  valid_pattern ("$c$|(a$|b$)");
  valid_pattern ("^d^(c|e((a|b)))");
  valid_pattern ("^d(^c|e((a|b)))");
  valid_pattern ("^d(c^|e((a|b)))");
  valid_pattern ("^d(c|^e((a|b)))");
  valid_pattern ("^d(c|e^((a|b)))");
  valid_pattern ("^d(c|e(^(a|b)))");
  valid_pattern ("^d(c|e((^a|b)))");
  valid_pattern ("^d(c|e((a|^b)))");
  valid_pattern ("^d(c|e((a|b^)))");
  valid_pattern ("^d(c|e((a|b)^))");
  valid_pattern ("^d(c|e((a|b))^)");
  valid_pattern ("^d(c|e((a|b)))^");
  valid_pattern ("d(c$|e($(a$|b$)))");
  valid_pattern ("d(c$|e$((a$|b$)))");
  valid_pattern ("d(c$|$e((a$|b$)))");
  valid_pattern ("d($c$|e((a$|b$)))");
  valid_pattern ("d$(c$|e((a$|b$)))");
  valid_pattern ("$d(c$|e((a$|b$)))");
  valid_pattern ("^d|^a^(b|c)");
  valid_pattern ("^d|^a(^b|c)");
  valid_pattern ("^d|^a(b^|c)");
  valid_pattern ("^d|^a(b|^c)");
  valid_pattern ("^d|^a(b|c^)");
  valid_pattern ("^d|^a(b|c)^");
  valid_pattern ("d$|a($b$|c$)");
  valid_pattern ("d$|a$(b$|c$)");
  valid_pattern ("d$|$a(b$|c$)");
  valid_pattern ("$d$|a(b$|c$)");
  valid_pattern ("^d|^(b^|c)a");
  valid_pattern ("^d|^(b|c^)a");
  valid_pattern ("^d|^(b|c)^a");
  valid_pattern ("^d|^(b|c)a^");
  valid_pattern ("d$|(b|c)$a$");
  valid_pattern ("d$|(b|c$)a$");
  valid_pattern ("d$|(b|$c)a$");
  valid_pattern ("d$|(b$|c)a$");
  valid_pattern ("d$|($b|c)a$");
  valid_pattern ("d$|$(b|c)a$");
  valid_pattern ("$d$|(b|c)a$");

   /* xx Do these use all the valid_nonposix_pattern ones in other_test.c?  */

  TEST_SEARCH ("(^a|^b)c", "ac", 0, 2);
  TEST_SEARCH ("(^a|^b)c", "bc", 0, 2);
  TEST_SEARCH ("c(a$|b$)", "ca", 0, 2);
  TEST_SEARCH ("c(a$|b$)", "cb", 0, 2);
  TEST_SEARCH ("^(a|b)|^c", "ad", 0, 2);
  TEST_SEARCH ("^(a|b)|^c", "bd", 0, 2);
  TEST_SEARCH ("(a|b)$|c$", "da", 0, 2);
  TEST_SEARCH ("(a|b)$|c$", "db", 0, 2);
  TEST_SEARCH ("(a|b)$|c$", "dc", 0, 2);
  TEST_SEARCH ("(^a|^b)|^c", "ad", 0, 2);
  TEST_SEARCH ("(^a|^b)|^c", "bd", 0, 2);
  TEST_SEARCH ("(^a|^b)|^c", "cd", 0, 2);
  TEST_SEARCH ("(a$|b$)|c$", "da", 0, 2);
  TEST_SEARCH ("(a$|b$)|c$", "db", 0, 2);
  TEST_SEARCH ("(a$|b$)|c$", "dc", 0, 2);
  TEST_SEARCH ("^c|(^a|^b)", "ad", 0, 2);
  TEST_SEARCH ("^c|(^a|^b)", "bd", 0, 2);
  TEST_SEARCH ("^c|(^a|^b)", "cd", 0, 2);
  TEST_SEARCH ("c$|(a$|b$)", "da", 0, 2);
  TEST_SEARCH ("c$|(a$|b$)", "db", 0, 2);
  TEST_SEARCH ("c$|(a$|b$)", "dc", 0, 2);
  TEST_SEARCH ("^c|^(a|b)", "ad", 0, 2);
  TEST_SEARCH ("^c|^(a|b)", "bd", 0, 2);
  TEST_SEARCH ("^c|^(a|b)", "cd", 0, 2);
  TEST_SEARCH ("c$|(a|b)$", "da", 0, 2);
  TEST_SEARCH ("c$|(a|b)$", "db", 0, 2);
  TEST_SEARCH ("c$|(a|b)$", "dc", 0, 2);
  TEST_SEARCH ("(^a|^b)c|^d", "ace", 0, 3);
  TEST_SEARCH ("(^a|^b)c|^d", "bce", 0, 3);
  TEST_SEARCH ("(^a|^b)c|^d", "de", 0, 2);
  TEST_SEARCH ("(a|b)c$|d$", "eac", 0, 3);
  TEST_SEARCH ("(a|b)c$|d$", "ebc", 0, 3);
  TEST_SEARCH ("(a|b)c$|d$", "ed", 0, 3);
  TEST_SEARCH ("^d|^c(a|b)", "cae", 0, 3);
  TEST_SEARCH ("^d|^c(a|b)", "cbe", 0, 3);
  TEST_SEARCH ("^d|^c(a|b)", "de", 0, 3);
  TEST_SEARCH ("d$|c(a$|b$)", "eca", 0, 3);
  TEST_SEARCH ("d$|c(a$|b$)", "ecb", 0, 3);
  TEST_SEARCH ("d$|c(a$|b$)", "ed", 0, 3);

  TEST_SEARCH ("(((^a|^b))c|^d)e", "acef", 0, 4);
  TEST_SEARCH ("(((^a|^b))c|^d)e", "bcef", 0, 4);
  TEST_SEARCH ("(((^a|^b))c|^d)e", "def", 0, 3);

  TEST_SEARCH ("((^(a|b))c|^d)e", "acef", 0, 4);
  TEST_SEARCH ("((^(a|b))c|^d)e", "bcef", 0, 4);
  TEST_SEARCH ("((^(a|b))c|^d)e", "def", 0, 3);

  TEST_SEARCH ("(^((a|b))c|^d)e", "acef", 0, 4);
  TEST_SEARCH ("(^((a|b))c|^d)e", "bcef", 0, 4);
  TEST_SEARCH ("(^((a|b))c|^d)e", "def", 0, 3);

  TEST_SEARCH ("(((a|b))c|d)e$", "face", 0, 4);
  TEST_SEARCH ("(((a|b))c|d)e$", "fbce", 0, 4);
  TEST_SEARCH ("(((a|b))c|d)e$", "fde", 0, 3);

  TEST_SEARCH ("^e(d|c((a|b)))", "edf", 0, 3);
  TEST_SEARCH ("^e(d|c((a|b)))", "ecaf", 0, 4);
  TEST_SEARCH ("^e(d|c((a|b)))", "ecbf", 0, 4);

  TEST_SEARCH ("e(d$|c((a$|b$)))", "fed", 0, 3);
  TEST_SEARCH ("e(d$|c((a$|b$)))", "feca", 0, 4);
  TEST_SEARCH ("e(d$|c((a$|b$)))", "fecb", 0, 4);

  TEST_SEARCH ("e(d$|c((a|b)$))", "fed", 0, 3);
  TEST_SEARCH ("e(d$|c((a|b)$))", "feca", 0, 4);
  TEST_SEARCH ("e(d$|c((a|b)$))", "fecb", 0, 4);

  TEST_SEARCH ("e(d$|c((a|b))$)", "fed", 0, 3);
  TEST_SEARCH ("e(d$|c((a|b))$)", "feca", 0, 3);
  TEST_SEARCH ("e(d$|c((a|b))$)", "fecb", 0, 3);

  TEST_SEARCH ("e(d$|c((a|b)))$", "fed", 0, 3);
  TEST_SEARCH ("e(d$|c((a|b)))$", "feca", 0, 3);
  TEST_SEARCH ("e(d$|c((a|b)))$", "fecb", 0, 3);

  TEST_SEARCH ("(((^a|^b))c)|^de", "acf", 0, 3);
  TEST_SEARCH ("(((^a|^b))c)|^de", "bcf", 0, 3);
  TEST_SEARCH ("(((^a|^b))c)|^de", "def", 0, 3);

  TEST_SEARCH ("(((a|b))c$)|de$", "fac", 0, 3);
  TEST_SEARCH ("(((a|b))c$)|de$", "fbc", 0, 3);
  TEST_SEARCH ("(((a|b))c$)|de$", "fde", 0, 3);

  TEST_SEARCH ("(((a|b))c)$|de$", "fac", 0, 3);
  TEST_SEARCH ("(((a|b))c)$|de$", "fbc", 0, 3);
  TEST_SEARCH ("(((a|b))c)$|de$", "fde", 0, 3);

  TEST_SEARCH ("^ed|^(c((a|b)))", "edf", 0, 3);
  TEST_SEARCH ("^ed|^(c((a|b)))", "caf", 0, 3);
  TEST_SEARCH ("^ed|^(c((a|b)))", "cbf", 0, 3);

  TEST_SEARCH ("^ed|(^c((a|b)))", "edf", 0, 3);
  TEST_SEARCH ("^ed|(^c((a|b)))", "caf", 0, 3);
  TEST_SEARCH ("^ed|(^c((a|b)))", "cbf", 0, 3);

  TEST_SEARCH ("ed$|(c((a|b)))$", "fed", 0, 3);
  TEST_SEARCH ("ed$|(c((a|b)))$", "fca", 0, 3);
  TEST_SEARCH ("ed$|(c((a|b)))$", "fcb", 0, 3);

  TEST_SEARCH ("ed$|(c((a|b))$)", "fed", 0, 3);
  TEST_SEARCH ("ed$|(c((a|b))$)", "fca", 0, 3);
  TEST_SEARCH ("ed$|(c((a|b))$)", "fcb", 0, 3);

  TEST_SEARCH ("ed$|(c((a|b)$))", "fed", 0, 3);
  TEST_SEARCH ("ed$|(c((a|b)$))", "fca", 0, 3);
  TEST_SEARCH ("ed$|(c((a|b)$))", "fcb", 0, 3);

  TEST_SEARCH ("ed$|(c((a$|b$)))", "fed", 0, 3);
  TEST_SEARCH ("ed$|(c((a$|b$)))", "fca", 0, 3);
  TEST_SEARCH ("ed$|(c((a$|b$)))", "fcb", 0, 3);

  TEST_SEARCH ("^a(b|c)|^d", "abe", 0, 3);
  TEST_SEARCH ("^a(b|c)|^d", "ace", 0, 3);
  TEST_SEARCH ("^a(b|c)|^d", "df", 0, 2);

  TEST_SEARCH ("a(b$|c$)|d$", "fab", 0, 3);
  TEST_SEARCH ("a(b$|c$)|d$", "fac", 0, 3);
  TEST_SEARCH ("a(b$|c$)|d$", "fd", 0, 2);

  TEST_SEARCH ("^(a)(b|c)|^d", "abe", 0, 3);
  TEST_SEARCH ("^(a)(b|c)|^d", "ace", 0, 3);
  TEST_SEARCH ("^(a)(b|c)|^d", "df", 0, 2);
  
  TEST_SEARCH ("(^a)(b|c)|^d", "abe", 0, 3);
  TEST_SEARCH ("(^a)(b|c)|^d", "ace", 0, 3);
  TEST_SEARCH ("(^a)(b|c)|^d", "df", 0, 2);
  
  TEST_SEARCH ("(a)(b|c)$|d$", "fab", 0, 3);
  TEST_SEARCH ("(a)(b|c)$|d$", "fac", 0, 3);
  TEST_SEARCH ("(a)(b|c)$|d$", "fd", 0, 2);

  TEST_SEARCH ("(b|c)(a)$|d$", "fba", 0, 3);
  TEST_SEARCH ("(b|c)(a)$|d$", "fca", 0, 3);
  TEST_SEARCH ("(b|c)(a)$|d$", "fd", 0, 2);

  TEST_SEARCH ("(b|c)(a$)|d$", "fba", 0, 3);
  TEST_SEARCH ("(b|c)(a$)|d$", "fca", 0, 3);
  TEST_SEARCH ("(b|c)(a$)|d$", "fd", 0, 2);

  TEST_SEARCH ("(a)(b$|c$)|d$", "fab", 0, 3);
  TEST_SEARCH ("(a)(b$|c$)|d$", "fac", 0, 3);
  TEST_SEARCH ("(a)(b$|c$)|d$", "fd", 0, 2);

  TEST_SEARCH ("^d|^(b|c)(a)", "df", 0, 2);
  TEST_SEARCH ("^d|^(b|c)(a)", "baf", 0, 3);
  TEST_SEARCH ("^d|^(b|c)(a)", "caf", 0, 3);
  
  TEST_SEARCH ("^d|(^b|^c)(a)", "df", 0, 2);
  TEST_SEARCH ("^d|(^b|^c)(a)", "baf", 0, 3);
  TEST_SEARCH ("^d|(^b|^c)(a)", "caf", 0, 3);
  
  TEST_SEARCH ("d$|(b|c)(a$)", "fd", 0, 2);
  TEST_SEARCH ("d$|(b|c)(a$)", "fba", 0, 3);
  TEST_SEARCH ("d$|(b|c)(a$)", "fca", 0, 3);

  TEST_SEARCH ("d$|(b|c)(a)$", "fd", 0, 2);
  TEST_SEARCH ("d$|(b|c)(a)$", "fba", 0, 3);
  TEST_SEARCH ("d$|(b|c)(a)$", "fca", 0, 3);

  TEST_SEARCH ("d$|(b|c)(a$)", "fd", 0, 2);
  TEST_SEARCH ("d$|(b|c)(a$)", "fba", 0, 3);
  TEST_SEARCH ("d$|(b|c)(a$)", "fca", 0, 3);

  TEST_SEARCH ("^d|^(a)(b|c)", "df", 0, 2);
  TEST_SEARCH ("^d|^(a)(b|c)", "abf", 0, 3);
  TEST_SEARCH ("^d|^(a)(b|c)", "acf", 0, 3);

  TEST_SEARCH ("^d|(^a)(b|c)", "df", 0, 2);
  TEST_SEARCH ("^d|(^a)(b|c)", "abf", 0, 3);
  TEST_SEARCH ("^d|(^a)(b|c)", "acf", 0, 3);

  TEST_SEARCH ("d$|(a)(b$|c$)", "fd", 0, 2);
  TEST_SEARCH ("d$|(a)(b$|c$)", "fab", 0, 3);
  TEST_SEARCH ("d$|(a)(b$|c$)", "fac", 0, 3);

  TEST_SEARCH ("d$|(a)(b|c)$", "fd", 0, 2);
  TEST_SEARCH ("d$|(a)(b|c)$", "fab", 0, 3);
  TEST_SEARCH ("d$|(a)(b|c)$", "fac", 0, 3);

  TEST_SEARCH ("((^a|^b)|^c)|^d", "ae", 0, 2);
  TEST_SEARCH ("((^a|^b)|^c)|^d", "be", 0, 2);
  TEST_SEARCH ("((^a|^b)|^c)|^d", "ce", 0, 2);
  TEST_SEARCH ("((^a|^b)|^c)|^d", "de", 0, 2);

  TEST_SEARCH ("((a|b)|c)|d$", "ed", 0, 2);
  TEST_SEARCH ("((a|b)|c)|d$", "ea", 0, 2);
  TEST_SEARCH ("((a|b)|c)|d$", "eb", 0, 2);
  TEST_SEARCH ("((a|b)|c)|d$", "ec", 0, 2);

  TEST_SEARCH ("^d|(c|(a|b))", "de", 0, 2);

  TEST_SEARCH ("d$|(c$|(a$|b$))", "ed", 0, 2);
  TEST_SEARCH ("d$|(c$|(a$|b$))", "ec", 0, 2);
  TEST_SEARCH ("d$|(c$|(a$|b$))", "ea", 0, 2);
  TEST_SEARCH ("d$|(c$|(a$|b$))", "eb", 0, 2);

  TEST_SEARCH ("d$|(c$|(a|b)$)", "ed", 0, 2);
  TEST_SEARCH ("d$|(c$|(a|b)$)", "ec", 0, 2);
  TEST_SEARCH ("d$|(c$|(a|b)$)", "ea", 0, 2);
  TEST_SEARCH ("d$|(c$|(a|b)$)", "eb", 0, 2);

  TEST_SEARCH ("d$|(c$|(a|b))$", "ed", 0, 2);
  TEST_SEARCH ("d$|(c$|(a|b))$", "ec", 0, 2);
  TEST_SEARCH ("d$|(c$|(a|b))$", "ea", 0, 2);
  TEST_SEARCH ("d$|(c$|(a|b))$", "eb", 0, 2);

  test_match ("a|^b", "b");
  test_match ("a|b$", "b");
  test_match ("^b|a", "b");
  test_match ("b$|a", "b");
  test_match ("(^a)", "a");
  test_match ("(a$)", "a");
  TEST_SEARCH ("c|^ab", "aba", 0, 3);
  TEST_SEARCH ("c|ba$", "aba", 0, 3);
  TEST_SEARCH ("^ab|c", "aba", 0, 3);
  TEST_SEARCH ("ba$|c", "aba", 0, 3);
  TEST_SEARCH ("(^a)", "ab", 0, 2);
  TEST_SEARCH ("(a$)", "ba", 0, 2);

  TEST_SEARCH ("(^a$)", "a", 0, 1);
  TEST_SEARCH ("(^a)", "ab", 0, 2);
  TEST_SEARCH ("(b$)", "ab", 0, 2);

                                                /* Backtracking.  */
  /* Per POSIX D11.1 p. 108, leftmost longest match.  */
  test_match ("(wee|week)(knights|night)", "weeknights");

  test_match ("(fooq|foo)qbar", "fooqbar");
  test_match ("(fooq|foo)(qbarx|bar)", "fooqbarx");

  /* Take first alternative that does the longest match.  */
  test_all_registers ("(fooq|(foo)|(fo))((qbarx)|(oqbarx)|bar)", "fooqbarx", 
    "", 0, 8,  0, 3,  0, 3,  -1, -1,  3, 8,  3, 8,  -1, -1,  -1, -1, -1, -1,  
    -1, -1);

  test_match ("(fooq|foo)*qbar", "fooqbar");
  test_match ("(fooq|foo)*(qbar)", "fooqbar");
  test_match ("(fooq|foo)*(qbar)*", "fooqbar"); 

  test_match ("(fooq|fo|o)*qbar", "fooqbar");
  test_match ("(fooq|fo|o)*(qbar)", "fooqbar");
  test_match ("(fooq|fo|o)*(qbar)*", "fooqbar");

  test_match ("(fooq|fo|o)*(qbar|q)*", "fooqbar");
  test_match ("(fooq|foo)*(qbarx|bar)", "fooqbarx");
  test_match ("(fooq|foo)*(qbarx|bar)*", "fooqbarx");

  test_match ("(fooq|fo|o)+(qbar|q)+", "fooqbar");
  test_match ("(fooq|foo)+(qbarx|bar)", "fooqbarx");
  test_match ("(fooq|foo)+(qbarx|bar)+", "fooqbarx");

  /* Per Mike Haertel.  */
  test_match ("(foo|foobarfoo)(bar)*", "foobarfoo");

  						/* Combination.  */
  test_match ("[ab]?c", "ac");
  test_match ("[ab]*c", "ac");
  test_match ("[ab]+c", "ac");
  test_match ("(a|b)?c", "ac");
  test_match ("(a|b)*c", "ac");
  test_match ("(a|b)+c", "ac");
  test_match ("(a*c)?b", "b");
  test_match ("(a*c)+b", "aacb");
						/* Registers.  */
  /* Per David A. Willcox.  */
  test_match ("a((b)|(c))d", "acd");
  test_all_registers ("a((b)|(c))d", "acd", "", 0, 3, 1, 2, -1, -1, 1, 2,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1);


  /* Extended regular expressions, continued; these don't match their strings.  */
  test_should_match = false;

#if 0
                                /* Invalid use of special characters.  */
  /* These are not invalid anymore, since POSIX says the behavior is
     undefined, and we prefer context-independent to context-invalid.  */
  invalid_pattern (REG_BADRPT, "*");
  invalid_pattern (REG_BADRPT, "a|*");
  invalid_pattern (REG_BADRPT, "(*)");
  invalid_pattern (REG_BADRPT, "^*");
  invalid_pattern (REG_BADRPT, "+");
  invalid_pattern (REG_BADRPT, "a|+");
  invalid_pattern (REG_BADRPT, "(+)");
  invalid_pattern (REG_BADRPT, "^+");

  invalid_pattern (REG_BADRPT, "?");
  invalid_pattern (REG_BADRPT, "a|?");
  invalid_pattern (REG_BADRPT, "(?)");
  invalid_pattern (REG_BADRPT, "^?");

  invalid_pattern (REG_BADPAT, "|");
  invalid_pattern (REG_BADPAT, "a|");
  invalid_pattern (REG_BADPAT, "a||");
  invalid_pattern (REG_BADPAT, "(|a)");
  invalid_pattern (REG_BADPAT, "(a|)");

  invalid_pattern (REG_BADPAT, PARENS_TO_OPS ("(|)"));

  invalid_pattern (REG_BADRPT, "{1}");
  invalid_pattern (REG_BADRPT, "a|{1}");
  invalid_pattern (REG_BADRPT, "^{1}");
  invalid_pattern (REG_BADRPT, "({1})");

  invalid_pattern (REG_BADPAT, "|b");

  invalid_pattern (REG_BADRPT, "^{0,}*");
  invalid_pattern (REG_BADRPT, "$*");
  invalid_pattern (REG_BADRPT, "${0,}*");
#endif /* 0 */

  invalid_pattern (REG_EESCAPE, "\\");

  test_match ("a?b", "a");


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

#if 0
  /* We make empty groups valid now, since they are undefined in POSIX.
    (13 Sep 92) */
                                                /* Subexpressions.  */
  invalid_pattern (REG_BADPAT, "()");
  invalid_pattern (REG_BADPAT, "a()");
  invalid_pattern (REG_BADPAT, "()b");
  invalid_pattern (REG_BADPAT, "a()b");
  invalid_pattern (REG_BADPAT, "()*");
  invalid_pattern (REG_BADPAT, "(()*");
#endif
                                                /* Invalid intervals.  */
  test_match ("a{2}*", "aaa");
  test_match ("a{2}?", "aaa");
  test_match ("a{2}+", "aaa");
  test_match ("a{2}{2}", "aaa");
  test_match ("a{1}{1}{2}", "aaa");
  test_match ("a{1}{1}{2}", "a");
						/* Invalid alternation.  */
  test_match ("a|b", "c");

  TEST_SEARCH ("c|^ba", "aba", 0, 3);
  TEST_SEARCH ("c|ab$", "aba", 0, 3);
  TEST_SEARCH ("^ba|c", "aba", 0, 3);
  TEST_SEARCH ("ab$|c", "aba", 0, 3);
						/* Invalid anchoring.  */
  TEST_SEARCH ("(^a)", "ba", 0, 2);
  TEST_SEARCH ("(b$)", "ba", 0, 2);

  printf ("\nFinished POSIX extended tests.\n");
}



/*
Local variables:
make-backup-files: t
version-control: t
trim-versions-without-asking: nil
End:
*/