Home /Modules/test-suites/reg_regex.c

reg_regex.c

test-suites/regression/c/reg_regex.c · 283 line(s) · c

/*
 * reg_regex.c -- regression suite for impl/core/sleela_regex.c
 *
 * Contract (impl/core/sleela_regex.h, REGEX-NATIVE.md): a small, explicit
 * matcher.  Levels 1 (FIND) and 2 (SHAPE) are supported; 3 and 4 report
 * SLEELA_REGEX_UNSUPPORTED_LEVEL.  Patterns are "contains <lit>",
 * "starts <lit>", "ends <lit>" and "exact <lit-or-shape>", where a shape is
 * digit|word|space|any with an optional + * {n} {n,} {n,m} quantifier.
 */
#include "../../../impl/core/sleela_regex.h"
#include "regression.h"

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

typedef SleelaRegexResult R;

static SleelaRegexStatus run(const char *t, const char *p, int level, R *r) {
    return sleela_regex_match(t, p, (SleelaRegexLevel)level, r);
}

static int matched(const char *t, const char *p, int level) {
    R r; SleelaRegexStatus s = run(t, p, level, &r);
    return s == SLEELA_REGEX_OK && r.matched;
}

static void t_status_names(void) {
    REG_EQ_S("ok", sleela_regex_status_name(SLEELA_REGEX_OK));
    REG_EQ_S("invalid-argument", sleela_regex_status_name(SLEELA_REGEX_INVALID_ARGUMENT));
    REG_EQ_S("invalid-pattern", sleela_regex_status_name(SLEELA_REGEX_INVALID_PATTERN));
    REG_EQ_S("unsupported-level", sleela_regex_status_name(SLEELA_REGEX_UNSUPPORTED_LEVEL));
    REG_EQ_S("unsupported-pattern", sleela_regex_status_name(SLEELA_REGEX_UNSUPPORTED_PATTERN));
    REG_EQ_S("unknown", sleela_regex_status_name((SleelaRegexStatus)99));
    REG_EQ_S("unknown", sleela_regex_status_name((SleelaRegexStatus)-1));
    REG_EQ_I(0, SLEELA_REGEX_OK); REG_EQ_I(1, SLEELA_REGEX_LEVEL_FIND); REG_EQ_I(4, SLEELA_REGEX_LEVEL_EXPRESSION);
}

static void t_argument_and_level_validation(void) {
    R r; memset(&r, 0xAB, sizeof r);
    REG_EQ_I(SLEELA_REGEX_INVALID_ARGUMENT, run(NULL, "contains a", 1, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_ARGUMENT, run("a", NULL, 1, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_ARGUMENT, run("a", "contains a", 1, NULL));
    REG_EQ_I(SLEELA_REGEX_INVALID_ARGUMENT, run("a", "contains a", 0, &r));
    REG_CHECK(r.matched == 0 && r.length == 0);            /* result is always reset */
    REG_EQ_I(SLEELA_REGEX_INVALID_ARGUMENT, run("a", "contains a", 5, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_ARGUMENT, run("a", "contains a", -1, &r));
    /* levels 3 and 4 are recognised but unsupported, even for a valid pattern */
    memset(&r, 0xAB, sizeof r);
    REG_EQ_I(SLEELA_REGEX_UNSUPPORTED_LEVEL, run("a", "contains a", 3, &r));
    REG_CHECK(r.matched == 0); REG_EQ_I(3, r.level);
    REG_EQ_I(SLEELA_REGEX_UNSUPPORTED_LEVEL, run("a", "exact digit+", 4, &r));
    REG_EQ_I(4, r.level);
}

static void t_pattern_prefix_grammar(void) {
    R r;
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", "", 1, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", "a", 1, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", "contains", 1, &r));   /* needs the space */
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", "exact", 2, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", "Contains a", 1, &r)); /* case-sensitive */
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", " contains a", 1, &r));
    REG_EQ_I(SLEELA_REGEX_INVALID_PATTERN, run("a", "match a", 2, &r));
    REG_CHECK(r.matched == 0);
}

static void t_find_family_positions(void) {
    R r;
    for (int level = 1; level <= 2; ++level) {
        REG_EQ_I(0, run("hello", "contains lo", level, &r));
        REG_CHECK(r.matched); REG_EQ_U(3, r.start); REG_EQ_U(5, r.end); REG_EQ_U(2, r.length); REG_EQ_I(level, r.level);
        REG_EQ_I(0, run("aaa", "contains aa", level, &r)); REG_CHECK(r.matched); REG_EQ_U(0, r.start);   /* first hit */
        REG_EQ_I(0, run("hello", "contains xyz", level, &r)); REG_CHECK(!r.matched); REG_EQ_U(0, r.length);
        REG_EQ_I(0, run("hello", "contains Hello", level, &r)); REG_CHECK(!r.matched);                    /* case */
        REG_EQ_I(0, run("hello", "contains ", level, &r)); REG_CHECK(r.matched); REG_EQ_U(0, r.length);   /* empty lit */
        REG_EQ_I(0, run("", "contains a", level, &r)); REG_CHECK(!r.matched);
        REG_EQ_I(0, run("", "contains ", level, &r)); REG_CHECK(r.matched);

        REG_EQ_I(0, run("hello", "starts he", level, &r)); REG_CHECK(r.matched); REG_EQ_U(0, r.start); REG_EQ_U(2, r.end);
        REG_EQ_I(0, run("hello", "starts el", level, &r)); REG_CHECK(!r.matched);
        REG_EQ_I(0, run("he", "starts hello", level, &r)); REG_CHECK(!r.matched);                         /* longer */
        REG_EQ_I(0, run("hello", "starts hello", level, &r)); REG_CHECK(r.matched); REG_EQ_U(5, r.end);

        REG_EQ_I(0, run("hello", "ends llo", level, &r)); REG_CHECK(r.matched); REG_EQ_U(2, r.start); REG_EQ_U(5, r.end);
        REG_EQ_I(0, run("hello", "ends hel", level, &r)); REG_CHECK(!r.matched);
        REG_EQ_I(0, run("lo", "ends hello", level, &r)); REG_CHECK(!r.matched);                           /* longer */
        REG_EQ_I(0, run("hello", "ends ", level, &r)); REG_CHECK(r.matched); REG_EQ_U(5, r.start); REG_EQ_U(5, r.end);
        /* a space is an ordinary literal character after the keyword's own space */
        REG_EQ_I(0, run("a b c", "contains  b", level, &r)); REG_CHECK(r.matched); REG_EQ_U(1, r.start);
    }
}

static void t_exact_literal(void) {
    R r;
    REG_EQ_I(0, run("hello", "exact hello", 1, &r)); REG_CHECK(r.matched); REG_EQ_U(5, r.length);
    REG_EQ_I(0, run("hello!", "exact hello", 1, &r)); REG_CHECK(!r.matched);
    REG_EQ_I(0, run("", "exact ", 1, &r)); REG_CHECK(r.matched);
    REG_EQ_I(0, run("x", "exact ", 1, &r)); REG_CHECK(!r.matched);
    /* at SHAPE level a plain word is still a literal comparison */
    REG_EQ_I(0, run("hello", "exact hello", 2, &r)); REG_CHECK(r.matched);
    REG_EQ_I(0, run("hellO", "exact hello", 2, &r)); REG_CHECK(!r.matched);
    /* FIND level never interprets shapes: "digit+" is just text */
    REG_CHECK(!matched("123", "exact digit+", 1));
    REG_CHECK(matched("digit+", "exact digit+", 1));
}

static void t_shapes(void) {
    static const struct { const char *shape; const char *text; int want; } c[] = {
        {"digit+", "123", 1}, {"digit+", "", 0}, {"digit+", "12a", 0}, {"digit+", "a12", 0}, {"digit+", " 1", 0},
        {"digit*", "", 1}, {"digit*", "0", 1}, {"digit*", "x", 0},
        {"digit", "7", 1}, {"digit", "77", 0}, {"digit", "", 0},
        {"digit{3}", "123", 1}, {"digit{3}", "12", 0}, {"digit{3}", "1234", 0},
        {"digit{0}", "", 1}, {"digit{0}", "1", 0},
        {"digit{2,4}", "1", 0}, {"digit{2,4}", "12", 1}, {"digit{2,4}", "1234", 1}, {"digit{2,4}", "12345", 0},
        {"digit{3,3}", "123", 1}, {"digit{3,3}", "12", 0},
        {"digit{2,}", "1", 0}, {"digit{2,}", "12", 1}, {"digit{2,}", "1234567890123456789", 1},
        {"word+", "ab_9", 1}, {"word+", "a b", 0}, {"word+", "", 0}, {"word+", "a-b", 0}, {"word+", "_", 1},
        {"word{2}", "ab", 1}, {"word{2}", "abc", 0},
        {"space+", " \t\r\n\v\f", 1}, {"space+", "a", 0}, {"space+", "", 0}, {"space*", "", 1},
        {"any+", "x y\n!", 1}, {"any+", "", 0}, {"any*", "", 1}, {"any{2}", "ab", 1}, {"any{2}", "a", 0},
    };
    for (size_t i = 0; i < sizeof c / sizeof c[0]; ++i) {
        char pat[64]; R r; SleelaRegexStatus s;
        strcpy(pat, "exact "); strcat(pat, c[i].shape);
        s = run(c[i].text, pat, 2, &r);
        reg_note_check();
        if (s != SLEELA_REGEX_OK || r.matched != c[i].want)
            reg_fail(__FILE__, __LINE__, "shape %s on \"%s\": status=%d matched=%d want=%d",
                     c[i].shape, c[i].text, (int)s, r.matched, c[i].want);
        if (c[i].want && s == SLEELA_REGEX_OK) {
            REG_EQ_U(0, r.start); REG_EQ_U(strlen(c[i].text), r.end); REG_EQ_U(strlen(c[i].text), r.length);
        }
    }
    /* the matcher is locale-independent for high bytes (C locale classes) */
    REG_CHECK(!matched("\xC3\xA9", "exact word+", 2));
    REG_CHECK(!matched("\xFF", "exact digit", 2));
    REG_CHECK(matched("\xFF", "exact any", 2));
}

/* Malformed shapes are not errors: they report OK with no match. */
static void t_malformed_shapes_do_not_match(void) {
    static const char *bad[] = {"digit{}", "digit{,3}", "digit{4,2}", "digit{2", "digit{2,3", "digit{2,x}",
                                "digit{x}", "digit+x", "digit++", "foo+", "foo*", "foo{2}", "{3}", "+"};
    for (size_t i = 0; i < sizeof bad / sizeof bad[0]; ++i) {
        char pat[64]; R r; SleelaRegexStatus s;
        strcpy(pat, "exact "); strcat(pat, bad[i]);
        s = run("123", pat, 2, &r);
        reg_note_check();
        if (s != SLEELA_REGEX_OK || r.matched)
            reg_fail(__FILE__, __LINE__, "malformed shape %s: status=%d matched=%d", bad[i], (int)s, r.matched);
    }
}

/* CHARACTERIZATION of current behaviour at SHAPE level: a literal containing
 * one of + * { cannot be matched literally (the shape parse fails and the
 * quantifier characters short-circuit to "no match"). FIND level is exact. */
static void t_shape_level_literal_with_quantifier_chars(void) {
    REG_CHECK(matched("a+b", "exact a+b", 1));
    REG_CHECK(!matched("a+b", "exact a+b", 2));
    REG_CHECK(matched("digit5", "exact digit5", 2));   /* no quantifier char: literal */
    REG_CHECK(matched("digit", "exact digit", 2));     /* text 'digit' is not 1 digit char; literal fallback */
}

/* Regression (was REGEX-QUANT-OVERFLOW): quantifier counts are accumulated with
 * an overflow check, so a count that does not fit size_t is an invalid shape
 * (no match) and never wraps around to a small number. */
static void t_quantifier_overflow_is_not_wrapped(void) {
    static const char *huge[] = {
        "exact digit{18446744073709551617}",        /* 2^64 + 1 would wrap to {1} */
        "exact digit{18446744073709551616}",        /* 2^64 would wrap to {0}      */
        "exact digit{99999999999999999999}",
        "exact digit{1,18446744073709551617}",
        "exact digit{18446744073709551617,}",
        "exact digit{0,36893488147419103232}",
    };
    for (size_t i = 0; i < sizeof huge / sizeof huge[0]; ++i) {
        R r; SleelaRegexStatus s;
        s = run("5", huge[i], 2, &r);
        REG_EQ_I(SLEELA_REGEX_OK, s); REG_CHECK(!r.matched);
        s = run("", huge[i], 2, &r);
        REG_EQ_I(SLEELA_REGEX_OK, s); REG_CHECK(!r.matched);
    }
    /* the largest representable counts still parse (they just cannot match short text) */
    REG_CHECK(!matched("5", "exact digit{18446744073709551615}", 2));
    REG_CHECK(matched("5", "exact digit{1,18446744073709551615}", 2));
    REG_CHECK(matched("55", "exact digit{2,18446744073709551615}", 2));
    REG_CHECK(matched("", "exact digit{0,18446744073709551615}", 2));
    REG_CHECK(matched("5", "exact digit{1}", 2));
}

/* Differential: find-family against libc strstr/strncmp over random text. */
static void t_differential_find_family(void) {
    static const char alpha[] = "ab1 _";
    reg_seed(0xFEEDF00Dull);
    for (int it = 0; it < 20000; ++it) {
        char t[10], lit[5], pat[16]; size_t tn = reg_below(10), ln = reg_below(5);
        R r; const char *kind[] = {"contains ", "starts ", "ends "}; unsigned k = reg_below(3);
        int want; size_t wstart = 0;
        for (size_t i = 0; i < tn; ++i) t[i] = alpha[reg_below(5)];
        for (size_t i = 0; i < ln; ++i) lit[i] = alpha[reg_below(5)];
        t[tn] = 0; lit[ln] = 0;
        strcpy(pat, kind[k]); strcat(pat, lit);
        if (k == 0) { const char *p = strstr(t, lit); want = p != NULL; if (p) wstart = (size_t)(p - t); }
        else if (k == 1) { want = strncmp(t, lit, ln) == 0 && ln <= tn; wstart = 0; }
        else { want = ln <= tn && strcmp(t + tn - ln, lit) == 0; wstart = tn - ln; }
        REG_EQ_I(0, run(t, pat, 1 + (int)reg_below(2), &r));
        REG_EQ_I(want, r.matched);
        if (want) { REG_EQ_U(wstart, r.start); REG_EQ_U(wstart + ln, r.end); REG_EQ_U(ln, r.length); }
    }
}

/* Differential: shapes against an independent counting oracle. */
static void t_differential_shapes(void) {
    static const char alpha[] = "0 9a_-\n";
    static const char *cls[] = {"digit", "word", "space", "any"};
    reg_seed(0xBADC0FFEull);
    for (int it = 0; it < 30000; ++it) {
        char t[9], pat[96]; size_t tn = reg_below(9); R r; unsigned c = reg_below(4), q = reg_below(7);
        size_t lo = 1, hi = 1, cnt = 0; int all = 1, want;
        char suffix[64] = "";
        for (size_t i = 0; i < tn; ++i) t[i] = alpha[reg_below(7)];
        t[tn] = 0;
        switch (q) {
            case 0: break;
            case 1: strcpy(suffix, "+"); lo = 1; hi = (size_t)-1; break;
            case 2: strcpy(suffix, "*"); lo = 0; hi = (size_t)-1; break;
            case 3: lo = hi = reg_below(5); snprintf(suffix, sizeof suffix, "{%zu}", lo); break;
            case 4: lo = reg_below(4); hi = lo + reg_below(3); snprintf(suffix, sizeof suffix, "{%zu,%zu}", lo, hi); break;
            case 5: lo = reg_below(4); hi = (size_t)-1; snprintf(suffix, sizeof suffix, "{%zu,}", lo); break;
            default: strcpy(suffix, "+"); lo = 1; hi = (size_t)-1; break;
        }
        for (size_t i = 0; i < tn; ++i) {
            unsigned char ch = (unsigned char)t[i]; int ok;
            switch (c) {
                case 0: ok = ch >= '0' && ch <= '9'; break;
                case 1: ok = (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_'; break;
                case 2: ok = ch == ' ' || (ch >= 9 && ch <= 13); break;
                default: ok = 1; break;
            }
            if (!ok) all = 0;
            cnt++;
        }
        want = all && cnt >= lo && cnt <= hi;
        snprintf(pat, sizeof pat, "exact %s%s", cls[c], suffix);
        REG_EQ_I(0, run(t, pat, 2, &r));
        reg_note_check();
        if (r.matched != want) {
            reg_fail(__FILE__, __LINE__, "pattern \"%s\" text \"%s\": matched=%d want=%d", pat, t, r.matched, want);
            return;
        }
    }
}

/* Scale: linear-time behaviour on a 1 MiB input (bounded runtime). */
static void t_large_text(void) {
    const size_t n = 1u << 20; char *t = (char *)malloc(n + 2); R r;
    REG_REQUIRE(t != NULL);
    memset(t, 'a', n); t[n] = 'b'; t[n + 1] = 0;
    REG_EQ_I(0, run(t, "contains ab", 1, &r)); REG_CHECK(r.matched); REG_EQ_U(n - 1, r.start);
    REG_EQ_I(0, run(t, "ends ab", 1, &r)); REG_CHECK(r.matched); REG_EQ_U(n - 1, r.start);
    REG_EQ_I(0, run(t, "exact word+", 2, &r)); REG_CHECK(r.matched); REG_EQ_U(n + 1, r.end);
    t[n / 2] = '-';
    REG_EQ_I(0, run(t, "exact word+", 2, &r)); REG_CHECK(!r.matched);
    free(t);
}

int main(void) {
    REG_RUN(t_status_names);
    REG_RUN(t_argument_and_level_validation);
    REG_RUN(t_pattern_prefix_grammar);
    REG_RUN(t_find_family_positions);
    REG_RUN(t_exact_literal);
    REG_RUN(t_shapes);
    REG_RUN(t_malformed_shapes_do_not_match);
    REG_RUN(t_shape_level_literal_with_quantifier_chars);
    REG_RUN(t_quantifier_overflow_is_not_wrapped);
    REG_RUN(t_differential_find_family);
    REG_RUN(t_differential_shapes);
    REG_RUN(t_large_text);
    return reg_finish("regex");
}