Implement a tiny regex engine in C in this directory. Files: regex.c, regex.h (supports…

codexgpt-5.6-sol · 41 steps · 5m 23s · 4 filessession d0658e65-59e@patrick-toulme

Implement a tiny regex engine in C in this directory. Files: regex.c, regex.h (supports literals, '.', '*', '+', '?', character classes like [a-z] and [^0-9], and anchors ^ $ — recursive backtracking matcher, no libc regex), tests.c (a table-driven test suite with at least 40 cases covering matches, non-matches, and edge cases like empty patterns and greedy repetition), Makefile. Build with make, run the tests, fix failures until all pass.

step 41 / 41

regex.cchange 2/2

#include "regex.h"
 
#include <stddef.h>
 
enum atom_type {
    ATOM_LITERAL,
    ATOM_ANY,
    ATOM_CLASS
};
 
struct atom {
    enum atom_type type;
    unsigned char literal;
    const char *class_begin;
    const char *class_end;
};
 
static int match_here(const char *pattern, const char *text);
 
/*
 * Locate the closing bracket of a character class. A ']' immediately after
 * '[' or '[^' is a class member; later unescaped ']' characters close it.
 */
static const char *class_end(const char *pattern)
{
    const char *cursor = pattern + 1;
    int first = 1;
 
    if (*cursor == '^') {
        ++cursor;
    }
 
    while (*cursor != '\0') {
        if (*cursor == '\\') {
            if (cursor[1] == '\0') {
                return NULL;
            }
            cursor += 2;
            first = 0;
            continue;
        }
 
        if (*cursor == ']' && !first) {
            return cursor;
        }
 
        ++cursor;
        first = 0;
    }
 
    return NULL;
}
 
/* Parse one one-byte-consuming atom and return the following pattern byte. */
static int parse_atom(const char *pattern, struct atom *atom,
                      const char **after)
{
    const char *end;
 
    if (*pattern == '\0' || *pattern == '*' || *pattern == '+' ||
        *pattern == '?') {
        return 0;
    }
 
    if (*pattern == '\\') {
        if (pattern[1] == '\0') {
            return 0;
        }
        atom->type = ATOM_LITERAL;
        atom->literal = (unsigned char)pattern[1];
        *after = pattern + 2;
        return 1;
    }
 
    if (*pattern == '.') {
        atom->type = ATOM_ANY;
        *after = pattern + 1;
        return 1;
    }
 
    if (*pattern == '[') {
        end = class_end(pattern);
        if (end == NULL) {
            return 0;
        }
        atom->type = ATOM_CLASS;
        atom->class_begin = pattern + 1;
        atom->class_end = end;
        *after = end + 1;
        return 1;
    }
 
    atom->type = ATOM_LITERAL;
    atom->literal = (unsigned char)*pattern;
    *after = pattern + 1;
    return 1;
}
 
/* Read one possibly escaped byte from inside a character class. */
static const char *class_char(const char *cursor, const char *end,
                              unsigned char *value)
{
    if (cursor >= end) {
        return NULL;
    }
 
    if (*cursor == '\\') {
        if (cursor + 1 >= end) {
            return NULL;
        }
        *value = (unsigned char)cursor[1];
        return cursor + 2;
    }
 
    *value = (unsigned char)*cursor;
    return cursor + 1;
}
 
static int class_matches(const struct atom *atom, unsigned char value)
{
    const char *cursor = atom->class_begin;
    const char *after_first;
    const char *after_last;
    unsigned char first;
    unsigned char last;
    int negate = 0;
    int found = 0;
 
    if (cursor < atom->class_end && *cursor == '^') {
        negate = 1;
        ++cursor;
    }
 
    while (cursor < atom->class_end) {
        after_first = class_char(cursor, atom->class_end, &first);
        if (after_first == NULL) {
            return 0;
        }
 
        if (after_first < atom->class_end && *after_first == '-' &&
            after_first + 1 < atom->class_end) {
            after_last = class_char(after_first + 1, atom->class_end,
                                    &last);
            if (after_last == NULL) {
                return 0;
            }
            if (first <= value && value <= last) {
                found = 1;
            }
            cursor = after_last;
        } else {
            if (first == value) {
                found = 1;
            }
            cursor = after_first;
        }
    }
 
    return negate ? !found : found;
}
 
static int valid_class(const struct atom *atom)
{
    const char *cursor = atom->class_begin;
    const char *after_first;
    const char *after_last;
    unsigned char first;
    unsigned char last;
 
    if (cursor < atom->class_end && *cursor == '^') {
        ++cursor;
    }
 
    while (cursor < atom->class_end) {
        after_first = class_char(cursor, atom->class_end, &first);
        if (after_first == NULL) {
            return 0;
        }
 
        if (after_first < atom->class_end && *after_first == '-' &&
            after_first + 1 < atom->class_end) {
            after_last = class_char(after_first + 1, atom->class_end,
                                    &last);
            if (after_last == NULL || first > last) {
                return 0;
            }
            cursor = after_last;
        } else {
            cursor = after_first;
        }
    }
 
    return 1;
}
 
static int atom_matches(const struct atom *atom, unsigned char value)
{
    switch (atom->type) {
    case ATOM_LITERAL:
        return atom->literal == value;
    case ATOM_ANY:
        return 1;
    case ATOM_CLASS:
        return class_matches(atom, value);
    }
 
    return 0;
}
 
/*
 * Try a greedy unbounded repetition. Each supported atom consumes exactly
 * one byte, so walking back one byte at a time explores every split point.
 */
static int match_many(const struct atom *atom, const char *rest,
                      const char *text, size_t minimum)
{
    const char *cursor = text;
    const char *minimum_end = text + minimum;
 
    while (*cursor != '\0' &&
           atom_matches(atom, (unsigned char)*cursor)) {
        ++cursor;
    }
 
    if (cursor < minimum_end) {
        return 0;
    }
 
    for (;;) {
        if (match_here(rest, cursor)) {
            return 1;
        }
        if (cursor == minimum_end) {
            break;
        }
        --cursor;
    }
 
    return 0;
}
 
static int match_here(const char *pattern, const char *text)
{
    struct atom atom;
    const char *after;
    char quantifier;
 
    if (*pattern == '\0') {
        return 1;
    }
 
    if (*pattern == '$' && pattern[1] == '\0') {
        return *text == '\0';
    }
 
    if (!parse_atom(pattern, &atom, &after)) {
        return 0;
    }
 
    quantifier = *after;
    if (quantifier == '*' || quantifier == '+') {
        return match_many(&atom, after + 1, text,
                          quantifier == '+' ? 1U : 0U);
    }
 
    if (quantifier == '?') {
        if (*text != '\0' &&
            atom_matches(&atom, (unsigned char)*text) &&
            match_here(after + 1, text + 1)) {
            return 1;
        }
        return match_here(after + 1, text);
    }
 
    if (*text != '\0' && atom_matches(&atom, (unsigned char)*text)) {
        return match_here(after, text + 1);
    }
 
    return 0;
}
 
/*
 * Validate before searching so a malformed expression cannot appear to match
 * merely because an earlier prefix did.
 */
static int valid_pattern(const char *pattern)
{
    const char *cursor = pattern;
    const char *after;
    struct atom atom;
 
    if (*cursor == '^') {
        ++cursor;
    }
 
    while (*cursor != '\0') {
        if (*cursor == '$' && cursor[1] == '\0') {
            return 1;
        }
 
        if (!parse_atom(cursor, &atom, &after)) {
            return 0;
        }
        if (atom.type == ATOM_CLASS && !valid_class(&atom)) {
            return 0;
        }
 
        cursor = after;
        if (*cursor == '*' || *cursor == '+' || *cursor == '?') {
            ++cursor;
            if (*cursor == '*' || *cursor == '+' || *cursor == '?') {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int regex_match(const char *pattern, const char *text)
{
    const char *cursor;
 
    if (pattern == NULL || text == NULL || !valid_pattern(pattern)) {
        return 0;
    }
 
    if (*pattern == '^') {
        return match_here(pattern + 1, text);
    }
 
    cursor = text;
    do {
        if (match_here(pattern, cursor)) {
            return 1;
        }
    } while (*cursor++ != '\0');
 
    return 0;
}
 

341 linesc

Implemented the tiny regex engine with: - Literals, `.`, `*`, `+`, `?` - Character classes,…

Files at this step

drag the rail to scrub

Discussion

No comments yet. Start the discussion. Recorded by @patrick-toulme.

#c #codex #gpt #gpt-5.6-sol #quick #subagents

s2-regex

← all sessions