<commit_before>#include "regexp.h"

void insert_code(char *code, int at, int num, int *pc)
{
    memmove(code + at + num, code + at, *pc - at);
    *pc += num;
}

#define REL(at, to) (to - at - 2)

int size_code(const char *re)
{
    int pc = 5; // Save 0, Save 1, Match

    for (; *re; re++) {
        switch (*re) {
        case '\\':
            re++;
        default:
        case '?':
        case '+':
            pc += 2;
            break;
        case '.':
        case '^':
        case '$':
            pc++;
            break;
        case '*':
        case '|':
        case '(':
            pc += 4;
            break;
        case ')':
            break;
        }
    }

    return pc;
}

#define EMIT(at, byte) code[at] = byte

const char *_compile2code(const char *re, ByteProg *prog)
{
    char *code = prog->insts;
    int pc = prog->bytelen;
    int start = pc;
    int term = pc;
    int alt_label = 0;

    for (; *re && *re != ')'; re++) {
        switch (*re) {
        case '\\':
            re++;
        default:
            term = pc;
            EMIT(pc++, Char);
            EMIT(pc++, *re);
            prog->len++;
            break;
        case '.':
            term = pc;
            EMIT(pc++, Any);
            prog->len++;
            break;
        case '(':
            term = pc;

            EMIT(pc++, Save);
            EMIT(pc++, 2 * ++prog->sub);
            prog->len++;

            prog->bytelen = pc;
            re = _compile2code(re + 1, prog);
            pc = prog->bytelen;

            EMIT(pc++, Save);
            EMIT(pc++, 2 * prog->sub + 1);
            prog->len++;

            break;
        case '?':
            insert_code(code, term, 2, &pc);
            EMIT(term, Split);
            EMIT(term + 1, REL(term, pc));
            prog->len++;
            break;
        case '*':
            insert_code(code, term, 2, &pc);
            EMIT(pc, Jmp);
            EMIT(pc + 1, REL(pc, term));
            pc += 2;
            EMIT(term, Split);
            EMIT(term + 1, REL(term, pc));
            prog->len += 2;
            break;
        case '+':
            EMIT(pc, RSplit);
            EMIT(pc + 1, REL(pc, term));
            pc += 2;
            prog->len++;
            break;
        case '|':
            if (alt_label) {
                EMIT(alt_label, REL(alt_label, pc) + 1);
            }
            insert_code(code, start, 2, &pc);
            EMIT(pc++, Jmp);
            alt_label = pc++;
            EMIT(start, Split);
            EMIT(start + 1, REL(start, pc));
            prog->len += 2;
            break;<commit_msg>Support non-greedy operators *?, +?.<commit_after>#include "regexp.h"

void insert_code(char *code, int at, int num, int *pc)
{
    memmove(code + at + num, code + at, *pc - at);
    *pc += num;
}

#define REL(at, to) (to - at - 2)

int size_code(const char *re)
{
    int pc = 5; // Save 0, Save 1, Match

    for (; *re; re++) {
        switch (*re) {
        case '\\':
            re++;
        default:
            pc += 2;
            break;
        case '+':
            // Skip entire "+?"
            if (re[1] == '?')
                re++;
        case '?':
            pc += 2;
            break;
        case '.':
        case '^':
        case '$':
            pc++;
            break;
        case '*':
            // Skip entire "*?"
            if (re[1] == '?')
                re++;
        case '|':
        case '(':
            pc += 4;
            break;
        case ')':
            break;
        }
    }

    return pc;
}

#define EMIT(at, byte) code[at] = byte

const char *_compile2code(const char *re, ByteProg *prog)
{
    char *code = prog->insts;
    int pc = prog->bytelen;
    int start = pc;
    int term = pc;
    int alt_label = 0;

    for (; *re && *re != ')'; re++) {
        switch (*re) {
        case '\\':
            re++;
        default:
            term = pc;
            EMIT(pc++, Char);
            EMIT(pc++, *re);
            prog->len++;
            break;
        case '.':
            term = pc;
            EMIT(pc++, Any);
            prog->len++;
            break;
        case '(':
            term = pc;

            EMIT(pc++, Save);
            EMIT(pc++, 2 * ++prog->sub);
            prog->len++;

            prog->bytelen = pc;
            re = _compile2code(re + 1, prog);
            pc = prog->bytelen;

            EMIT(pc++, Save);
            EMIT(pc++, 2 * prog->sub + 1);
            prog->len++;

            break;
        case '?':
            insert_code(code, term, 2, &pc);
            EMIT(term, Split);
            EMIT(term + 1, REL(term, pc));
            prog->len++;
            break;
        case '*':
            insert_code(code, term, 2, &pc);
            EMIT(pc, Jmp);
            EMIT(pc + 1, REL(pc, term));
            pc += 2;
            if (re[1] == '?') {
                EMIT(term, RSplit);
                re++;
            } else {
                EMIT(term, Split);
            }
            EMIT(term + 1, REL(term, pc));
            prog->len += 2;
            break;
        case '+':
            if (re[1] == '?') {
                EMIT(pc, Split);
                re++;
            } else {
                EMIT(pc, RSplit);
            }
            EMIT(pc + 1, REL(pc, term));
            pc += 2;
            prog->len++;
            break;
        case '|':
            if (alt_label) {
                EMIT(alt_label, REL(alt_label, pc) + 1);
            }
            insert_code(code, start, 2, &pc);
            EMIT(pc++, Jmp);
            alt_label = pc++;
            EMIT(start, Split);
            EMIT(start + 1, REL(start, pc));
            prog->len += 2;
            break;
{'fraction_non_alphanumeric': 0.16631689401888772, 'fraction_numerical': 0.009968520461699895, 'mean_word_length': 1.0623873061666065, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6560955', 'n_tokens_mistral': 1954, 'n_tokens_neox': 1795, 'n_words': 451}