path: root/fluent-bit/lib/librdkafka-2.1.0/src/regexp.c

/**
 * Copyright: public domain
 *
 * From https://github.com/ccxvii/minilibs sha
 * 875c33568b5a4aa4fb3dd0c52ea98f7f0e5ca684:
 *
 * These libraries are in the public domain (or the equivalent where that is not
 * possible). You can do anything you want with them. You have no legal
 * obligation to do anything else, although I appreciate attribution.
 */

#include "rd.h"

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

#include "regexp.h"

#define nelem(a) (sizeof(a) / sizeof(a)[0])

typedef unsigned int Rune;

static int isalpharune(Rune c) {
        /* TODO: Add unicode support */
        return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}

static Rune toupperrune(Rune c) {
        /* TODO: Add unicode support */
        if (c >= 'a' && c <= 'z')
                return c - 'a' + 'A';
        return c;
}

static int chartorune(Rune *r, const char *s) {
        /* TODO: Add UTF-8 decoding */
        *r = *s;
        return 1;
}

#define REPINF    255
#define MAXTHREAD 1000
#define MAXSUB    REG_MAXSUB

typedef struct Reclass Reclass;
typedef struct Renode Renode;
typedef struct Reinst Reinst;
typedef struct Rethread Rethread;
typedef struct Restate Restate;

struct Reclass {
        Rune *end;
        Rune spans[64];
};

struct Restate {
        Reprog *prog;
        Renode *pstart, *pend;

        const char *source;
        unsigned int ncclass;
        unsigned int nsub;
        Renode *sub[MAXSUB];

        int lookahead;
        Rune yychar;
        Reclass *yycc;
        int yymin, yymax;

        const char *error;
        jmp_buf kaboom;
};

struct Reprog {
        Reinst *start, *end;
        int flags;
        unsigned int nsub;
        Reclass cclass[16];
        Restate g; /**< Upstream has this as a global variable */
};

static void die(Restate *g, const char *message) {
        g->error = message;
        longjmp(g->kaboom, 1);
}

static Rune canon(Rune c) {
        Rune u = toupperrune(c);
        if (c >= 128 && u < 128)
                return c;
        return u;
}

/* Scan */

enum { L_CHAR = 256,
       L_CCLASS,  /* character class */
       L_NCCLASS, /* negative character class */
       L_NC,      /* "(?:" no capture */
       L_PLA,     /* "(?=" positive lookahead */
       L_NLA,     /* "(?!" negative lookahead */
       L_WORD,    /* "\b" word boundary */
       L_NWORD,   /* "\B" non-word boundary */
       L_REF,     /* "\1" back-reference */
       L_COUNT    /* {M,N} */
};

static int hex(Restate *g, int c) {
        if (c >= '0' && c <= '9')
                return c - '0';
        if (c >= 'a' && c <= 'f')
                return c - 'a' + 0xA;
        if (c >= 'A' && c <= 'F')
                return c - 'A' + 0xA;
        die(g, "invalid escape sequence");
        return 0;
}

static int dec(Restate *g, int c) {
        if (c >= '0' && c <= '9')
                return c - '0';
        die(g, "invalid quantifier");
        return 0;
}

#define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789"

static int nextrune(Restate *g) {
        g->source += chartorune(&g->yychar, g->source);
        if (g->yychar == '\\') {
                g->source += chartorune(&g->yychar, g->source);
                switch (g->yychar) {
                case 0:
                        die(g, "unterminated escape sequence");
                case 'f':
                        g->yychar = '\f';
                        return 0;
                case 'n':
                        g->yychar = '\n';
                        return 0;
                case 'r':
                        g->yychar = '\r';
                        return 0;
                case 't':
                        g->yychar = '\t';
                        return 0;
                case 'v':
                        g->yychar = '\v';
                        return 0;
                case 'c':
                        g->yychar = (*g->source++) & 31;
                        return 0;
                case 'x':
                        g->yychar = hex(g, *g->source++) << 4;
                        g->yychar += hex(g, *g->source++);
                        if (g->yychar == 0) {
                                g->yychar = '0';
                                return 1;
                        }
                        return 0;
                case 'u':
                        g->yychar = hex(g, *g->source++) << 12;
                        g->yychar += hex(g, *g->source++) << 8;
                        g->yychar += hex(g, *g->source++) << 4;
                        g->yychar += hex(g, *g->source++);
                        if (g->yychar == 0) {
                                g->yychar = '0';
                                return 1;
                        }
                        return 0;
                }
                if (strchr(ESCAPES, g->yychar))
                        return 1;
                if (isalpharune(g->yychar) ||
                    g->yychar == '_') /* check identity escape */
                        die(g, "invalid escape character");
                return 0;
        }
        return 0;
}

static int lexcount(Restate *g) {
        g->yychar = *g->source++;

        g->yymin  = dec(g, g->yychar);
        g->yychar = *g->source++;
        while (g->yychar != ',' && g->yychar != '}') {
                g->yymin  = g->yymin * 10 + dec(g, g->yychar);
                g->yychar = *g->source++;
        }
        if (g->yymin >= REPINF)
                die(g, "numeric overflow");

        if (g->yychar == ',') {
                g->yychar = *g->source++;
                if (g->yychar == '}') {
                        g->yymax = REPINF;
                } else {
                        g->yymax  = dec(g, g->yychar);
                        g->yychar = *g->source++;
                        while (g->yychar != '}') {
                                g->yymax  = g->yymax * 10 + dec(g, g->yychar);
                                g->yychar = *g->source++;
                        }
                        if (g->yymax >= REPINF)
                                die(g, "numeric overflow");
                }
        } else {
                g->yymax = g->yymin;
        }

        return L_COUNT;
}

static void newcclass(Restate *g) {
        if (g->ncclass >= nelem(g->prog->cclass))
                die(g, "too many character classes");
        g->yycc      = g->prog->cclass + g->ncclass++;
        g->yycc->end = g->yycc->spans;
}

static void addrange(Restate *g, Rune a, Rune b) {
        if (a > b)
                die(g, "invalid character class range");
        if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans))
                die(g, "too many character class ranges");
        *g->yycc->end++ = a;
        *g->yycc->end++ = b;
}

static void addranges_d(Restate *g) {
        addrange(g, '0', '9');
}

static void addranges_D(Restate *g) {
        addrange(g, 0, '0' - 1);
        addrange(g, '9' + 1, 0xFFFF);
}

static void addranges_s(Restate *g) {
        addrange(g, 0x9, 0x9);
        addrange(g, 0xA, 0xD);
        addrange(g, 0x20, 0x20);
        addrange(g, 0xA0, 0xA0);
        addrange(g, 0x2028, 0x2029);
        addrange(g, 0xFEFF, 0xFEFF);
}

static void addranges_S(Restate *g) {
        addrange(g, 0, 0x9 - 1);
        addrange(g, 0x9 + 1, 0xA - 1);
        addrange(g, 0xD + 1, 0x20 - 1);
        addrange(g, 0x20 + 1, 0xA0 - 1);
        addrange(g, 0xA0 + 1, 0x2028 - 1);
        addrange(g, 0x2029 + 1, 0xFEFF - 1);
        addrange(g, 0xFEFF + 1, 0xFFFF);
}

static void addranges_w(Restate *g) {
        addrange(g, '0', '9');
        addrange(g, 'A', 'Z');
        addrange(g, '_', '_');
        addrange(g, 'a', 'z');
}

static void addranges_W(Restate *g) {
        addrange(g, 0, '0' - 1);
        addrange(g, '9' + 1, 'A' - 1);
        addrange(g, 'Z' + 1, '_' - 1);
        addrange(g, '_' + 1, 'a' - 1);
        addrange(g, 'z' + 1, 0xFFFF);
}

static int lexclass(Restate *g) {
        int type = L_CCLASS;
        int quoted, havesave, havedash;
        Rune save = 0;

        newcclass(g);

        quoted = nextrune(g);
        if (!quoted && g->yychar == '^') {
                type   = L_NCCLASS;
                quoted = nextrune(g);
        }

        havesave = havedash = 0;
        for (;;) {
                if (g->yychar == 0)
                        die(g, "unterminated character class");
                if (!quoted && g->yychar == ']')
                        break;

                if (!quoted && g->yychar == '-') {
                        if (havesave) {
                                if (havedash) {
                                        addrange(g, save, '-');
                                        havesave = havedash = 0;
                                } else {
                                        havedash = 1;
                                }
                        } else {
                                save     = '-';
                                havesave = 1;
                        }
                } else if (quoted && strchr("DSWdsw", g->yychar)) {
                        if (havesave) {
                                addrange(g, save, save);
                                if (havedash)
                                        addrange(g, '-', '-');
                        }
                        switch (g->yychar) {
                        case 'd':
                                addranges_d(g);
                                break;
                        case 's':
                                addranges_s(g);
                                break;
                        case 'w':
                                addranges_w(g);
                                break;
                        case 'D':
                                addranges_D(g);
                                break;
                        case 'S':
                                addranges_S(g);
                                break;
                        case 'W':
                                addranges_W(g);
                                break;
                        }
                        havesave = havedash = 0;
                } else {
                        if (quoted) {
                                if (g->yychar == 'b')
                                        g->yychar = '\b';
                                else if (g->yychar == '0')
                                        g->yychar = 0;
                                /* else identity escape */
                        }
                        if (havesave) {
                                if (havedash) {
                                        addrange(g, save, g->yychar);
                                        havesave = havedash = 0;
                                } else {
                                        addrange(g, save, save);
                                        save = g->yychar;
                                }
                        } else {
                                save     = g->yychar;
                                havesave = 1;
                        }
                }

                quoted = nextrune(g);
        }

        if (havesave) {
                addrange(g, save, save);
                if (havedash)
                        addrange(g, '-', '-');
        }

        return type;
}

static int lex(Restate *g) {
        int quoted = nextrune(g);
        if (quoted) {
                switch (g->yychar) {
                case 'b':
                        return L_WORD;
                case 'B':
                        return L_NWORD;
                case 'd':
                        newcclass(g);
                        addranges_d(g);
                        return L_CCLASS;
                case 's':
                        newcclass(g);
                        addranges_s(g);
                        return L_CCLASS;
                case 'w':
                        newcclass(g);
                        addranges_w(g);
                        return L_CCLASS;
                case 'D':
                        newcclass(g);
                        addranges_d(g);
                        return L_NCCLASS;
                case 'S':
                        newcclass(g);
                        addranges_s(g);
                        return L_NCCLASS;
                case 'W':
                        newcclass(g);
                        addranges_w(g);
                        return L_NCCLASS;
                case '0':
                        g->yychar = 0;
                        return L_CHAR;
                }
                if (g->yychar >= '0' && g->yychar <= '9') {
                        g->yychar -= '0';
                        if (*g->source >= '0' && *g->source <= '9')
                                g->yychar = g->yychar * 10 + *g->source++ - '0';
                        return L_REF;
                }
                return L_CHAR;
        }

        switch (g->yychar) {
        case 0:
        case '$':
        case ')':
        case '*':
        case '+':
        case '.':
        case '?':
        case '^':
        case '|':
                return g->yychar;
        }

        if (g->yychar == '{')
                return lexcount(g);
        if (g->yychar == '[')
                return lexclass(g);
        if (g->yychar == '(') {
                if (g->source[0] == '?') {
                        if (g->source[1] == ':') {
                                g->source += 2;
                                return L_NC;
                        }
                        if (g->source[1] == '=') {
                                g->source += 2;
                                return L_PLA;
                        }
                        if (g->source[1] == '!') {
                                g->source += 2;
                                return L_NLA;
                        }
                }
                return '(';
        }

        return L_CHAR;
}

/* Parse */

enum { P_CAT,
       P_ALT,
       P_REP,
       P_BOL,
       P_EOL,
       P_WORD,
       P_NWORD,
       P_PAR,
       P_PLA,
       P_NLA,
       P_ANY,
       P_CHAR,
       P_CCLASS,
       P_NCCLASS,
       P_REF };

struct Renode {
        unsigned char type;
        unsigned char ng, m, n;
        Rune c;
        Reclass *cc;
        Renode *x;
        Renode *y;
};

static Renode *newnode(Restate *g, int type) {
        Renode *node = g->pend++;
        node->type   = type;
        node->cc     = NULL;
        node->c      = 0;
        node->ng     = 0;
        node->m      = 0;
        node->n      = 0;
        node->x = node->y = NULL;
        return node;
}

static int empty(Renode *node) {
        if (!node)
                return 1;
        switch (node->type) {
        default:
                return 1;
        case P_CAT:
                return empty(node->x) && empty(node->y);
        case P_ALT:
                return empty(node->x) || empty(node->y);
        case P_REP:
                return empty(node->x) || node->m == 0;
        case P_PAR:
                return empty(node->x);
        case P_REF:
                return empty(node->x);
        case P_ANY:
        case P_CHAR:
        case P_CCLASS:
        case P_NCCLASS:
                return 0;
        }
}

static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) {
        Renode *rep = newnode(g, P_REP);
        if (max == REPINF && empty(atom))
                die(g, "infinite loop matching the empty string");
        rep->ng = ng;
        rep->m  = min;
        rep->n  = max;
        rep->x  = atom;
        return rep;
}

static void next(Restate *g) {
        g->lookahead = lex(g);
}

static int re_accept(Restate *g, int t) {
        if (g->lookahead == t) {
                next(g);
                return 1;
        }
        return 0;
}

static Renode *parsealt(Restate *g);

static Renode *parseatom(Restate *g) {
        Renode *atom;
        if (g->lookahead == L_CHAR) {
                atom    = newnode(g, P_CHAR);
                atom->c = g->yychar;
                next(g);
                return atom;
        }
        if (g->lookahead == L_CCLASS) {
                atom     = newnode(g, P_CCLASS);
                atom->cc = g->yycc;
                next(g);
                return atom;
        }
        if (g->lookahead == L_NCCLASS) {
                atom     = newnode(g, P_NCCLASS);
                atom->cc = g->yycc;
                next(g);
                return atom;
        }
        if (g->lookahead == L_REF) {
                atom = newnode(g, P_REF);
                if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar])
                        die(g, "invalid back-reference");
                atom->n = g->yychar;
                atom->x = g->sub[g->yychar];
                next(g);
                return atom;
        }
        if (re_accept(g, '.'))
                return newnode(g, P_ANY);
        if (re_accept(g, '(')) {
                atom = newnode(g, P_PAR);
                if (g->nsub == MAXSUB)
                        die(g, "too many captures");
                atom->n         = g->nsub++;
                atom->x         = parsealt(g);
                g->sub[atom->n] = atom;
                if (!re_accept(g, ')'))
                        die(g, "unmatched '('");
                return atom;
        }
        if (re_accept(g, L_NC)) {
                atom = parsealt(g);
                if (!re_accept(g, ')'))
                        die(g, "unmatched '('");
                return atom;
        }
        if (re_accept(g, L_PLA)) {
                atom    = newnode(g, P_PLA);
                atom->x = parsealt(g);
                if (!re_accept(g, ')'))
                        die(g, "unmatched '('");
                return atom;
        }
        if (re_accept(g, L_NLA)) {
                atom    = newnode(g, P_NLA);
                atom->x = parsealt(g);
                if (!re_accept(g, ')'))
                        die(g, "unmatched '('");
                return atom;
        }
        die(g, "syntax error");
        return NULL;
}

static Renode *parserep(Restate *g) {
        Renode *atom;

        if (re_accept(g, '^'))
                return newnode(g, P_BOL);
        if (re_accept(g, '$'))
                return newnode(g, P_EOL);
        if (re_accept(g, L_WORD))
                return newnode(g, P_WORD);
        if (re_accept(g, L_NWORD))
                return newnode(g, P_NWORD);

        atom = parseatom(g);
        if (g->lookahead == L_COUNT) {
                int min = g->yymin, max = g->yymax;
                next(g);
                if (max < min)
                        die(g, "invalid quantifier");
                return newrep(g, atom, re_accept(g, '?'), min, max);
        }
        if (re_accept(g, '*'))
                return newrep(g, atom, re_accept(g, '?'), 0, REPINF);
        if (re_accept(g, '+'))
                return newrep(g, atom, re_accept(g, '?'), 1, REPINF);
        if (re_accept(g, '?'))
                return newrep(g, atom, re_accept(g, '?'), 0, 1);
        return atom;
}

static Renode *parsecat(Restate *g) {
        Renode *cat, *x;
        if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') {
                cat = parserep(g);
                while (g->lookahead && g->lookahead != '|' &&
                       g->lookahead != ')') {
                        x      = cat;
                        cat    = newnode(g, P_CAT);
                        cat->x = x;
                        cat->y = parserep(g);
                }
                return cat;
        }
        return NULL;
}

static Renode *parsealt(Restate *g) {
        Renode *alt, *x;
        alt = parsecat(g);
        while (re_accept(g, '|')) {
                x      = alt;
                alt    = newnode(g, P_ALT);
                alt->x = x;
                alt->y = parsecat(g);
        }
        return alt;
}

/* Compile */

enum { I_END,
       I_JUMP,
       I_SPLIT,
       I_PLA,
       I_NLA,
       I_ANYNL,
       I_ANY,
       I_CHAR,
       I_CCLASS,
       I_NCCLASS,
       I_REF,
       I_BOL,
       I_EOL,
       I_WORD,
       I_NWORD,
       I_LPAR,
       I_RPAR };

struct Reinst {
        unsigned char opcode;
        unsigned char n;
        Rune c;
        Reclass *cc;
        Reinst *x;
        Reinst *y;
};

static unsigned int count(Renode *node) {
        unsigned int min, max;
        if (!node)
                return 0;
        switch (node->type) {
        default:
                return 1;
        case P_CAT:
                return count(node->x) + count(node->y);
        case P_ALT:
                return count(node->x) + count(node->y) + 2;
        case P_REP:
                min = node->m;
                max = node->n;
                if (min == max)
                        return count(node->x) * min;
                if (max < REPINF)
                        return count(node->x) * max + (max - min);
                return count(node->x) * (min + 1) + 2;
        case P_PAR:
                return count(node->x) + 2;
        case P_PLA:
                return count(node->x) + 2;
        case P_NLA:
                return count(node->x) + 2;
        }
}

static Reinst *emit(Reprog *prog, int opcode) {
        Reinst *inst = prog->end++;
        inst->opcode = opcode;
        inst->n      = 0;
        inst->c      = 0;
        inst->cc     = NULL;
        inst->x = inst->y = NULL;
        return inst;
}

static void compile(Reprog *prog, Renode *node) {
        Reinst *inst, *split, *jump;
        unsigned int i;

        if (!node)
                return;

        switch (node->type) {
        case P_CAT:
                compile(prog, node->x);
                compile(prog, node->y);
                break;

        case P_ALT:
                split = emit(prog, I_SPLIT);
                compile(prog, node->x);
                jump = emit(prog, I_JUMP);
                compile(prog, node->y);
                split->x = split + 1;
                split->y = jump + 1;
                jump->x  = prog->end;
                break;

        case P_REP:
                for (i = 0; i < node->m; ++i) {
                        inst = prog->end;
                        compile(prog, node->x);
                }
                if (node->m == node->n)
                        break;
                if (node->n < REPINF) {
                        for (i = node->m; i < node->n; ++i) {
                                split = emit(prog, I_SPLIT);
                                compile(prog, node->x);
                                if (node->ng) {
                                        split->y = split + 1;
                                        split->x = prog->end;
                                } else {
                                        split->x = split + 1;
                                        split->y = prog->end;
                                }
                        }
                } else if (node->m == 0) {
                        split = emit(prog, I_SPLIT);
                        compile(prog, node->x);
                        jump = emit(prog, I_JUMP);
                        if (node->ng) {
                                split->y = split + 1;
                                split->x = prog->end;
                        } else {
                                split->x = split + 1;
                                split->y = prog->end;
                        }
                        jump->x = split;
                } else {
                        split = emit(prog, I_SPLIT);
                        if (node->ng) {
                                split->y = inst;
                                split->x = prog->end;
                        } else {
                                split->x = inst;
                                split->y = prog->end;
                        }
                }
                break;

        case P_BOL:
                emit(prog, I_BOL);
                break;
        case P_EOL:
                emit(prog, I_EOL);
                break;
        case P_WORD:
                emit(prog, I_WORD);
                break;
        case P_NWORD:
                emit(prog, I_NWORD);
                break;

        case P_PAR:
                inst    = emit(prog, I_LPAR);
                inst->n = node->n;
                compile(prog, node->x);
                inst    = emit(prog, I_RPAR);
                inst->n = node->n;
                break;
        case P_PLA:
                split = emit(prog, I_PLA);
                compile(prog, node->x);
                emit(prog, I_END);
                split->x = split + 1;
                split->y = prog->end;
                break;
        case P_NLA:
                split = emit(prog, I_NLA);
                compile(prog, node->x);
                emit(prog, I_END);
                split->x = split + 1;
                split->y = prog->end;
                break;

        case P_ANY:
                emit(prog, I_ANY);
                break;
        case P_CHAR:
                inst    = emit(prog, I_CHAR);
                inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c;
                break;
        case P_CCLASS:
                inst     = emit(prog, I_CCLASS);
                inst->cc = node->cc;
                break;
        case P_NCCLASS:
                inst     = emit(prog, I_NCCLASS);
                inst->cc = node->cc;
                break;
        case P_REF:
                inst    = emit(prog, I_REF);
                inst->n = node->n;
                break;
        }
}

#ifdef TEST
static void dumpnode(Renode *node) {
        Rune *p;
        if (!node) {
                printf("Empty");
                return;
        }
        switch (node->type) {
        case P_CAT:
                printf("Cat(");
                dumpnode(node->x);
                printf(", ");
                dumpnode(node->y);
                printf(")");
                break;
        case P_ALT:
                printf("Alt(");
                dumpnode(node->x);
                printf(", ");
                dumpnode(node->y);
                printf(")");
                break;
        case P_REP:
                printf(node->ng ? "NgRep(%d,%d," : "Rep(%d,%d,", node->m,
                       node->n);
                dumpnode(node->x);
                printf(")");
                break;
        case P_BOL:
                printf("Bol");
                break;
        case P_EOL:
                printf("Eol");
                break;
        case P_WORD:
                printf("Word");
                break;
        case P_NWORD:
                printf("NotWord");
                break;
        case P_PAR:
                printf("Par(%d,", node->n);
                dumpnode(node->x);
                printf(")");
                break;
        case P_PLA:
                printf("PLA(");
                dumpnode(node->x);
                printf(")");
                break;
        case P_NLA:
                printf("NLA(");
                dumpnode(node->x);
                printf(")");
                break;
        case P_ANY:
                printf("Any");
                break;
        case P_CHAR:
                printf("Char(%c)", node->c);
                break;
        case P_CCLASS:
                printf("Class(");
                for (p = node->cc->spans; p < node->cc->end; p += 2)
                        printf("%02X-%02X,", p[0], p[1]);
                printf(")");
                break;
        case P_NCCLASS:
                printf("NotClass(");
                for (p = node->cc->spans; p < node->cc->end; p += 2)
                        printf("%02X-%02X,", p[0], p[1]);
                printf(")");
                break;
        case P_REF:
                printf("Ref(%d)", node->n);
                break;
        }
}

static void dumpprog(Reprog *prog) {
        Reinst *inst;
        int i;
        for (i = 0, inst = prog->start; inst < prog->end; ++i, ++inst) {
                printf("% 5d: ", i);
                switch (inst->opcode) {
                case I_END:
                        puts("end");
                        break;
                case I_JUMP:
                        printf("jump %d\n", (int)(inst->x - prog->start));
                        break;
                case I_SPLIT:
                        printf("split %d %d\n", (int)(inst->x - prog->start),
                               (int)(inst->y - prog->start));
                        break;
                case I_PLA:
                        printf("pla %d %d\n", (int)(inst->x - prog->start),
                               (int)(inst->y - prog->start));
                        break;
                case I_NLA:
                        printf("nla %d %d\n", (int)(inst->x - prog->start),
                               (int)(inst->y - prog->start));
                        break;
                case I_ANY:
                        puts("any");
                        break;
                case I_ANYNL:
                        puts("anynl");
                        break;
                case I_CHAR:
                        printf(inst->c >= 32 && inst->c < 127 ? "char '%c'\n"
                                                              : "char U+%04X\n",
                               inst->c);
                        break;
                case I_CCLASS:
                        puts("cclass");
                        break;
                case I_NCCLASS:
                        puts("ncclass");
                        break;
                case I_REF:
                        printf("ref %d\n", inst->n);
                        break;
                case I_BOL:
                        puts("bol");
                        break;
                case I_EOL:
                        puts("eol");
                        break;
                case I_WORD:
                        puts("word");
                        break;
                case I_NWORD:
                        puts("nword");
                        break;
                case I_LPAR:
                        printf("lpar %d\n", inst->n);
                        break;
                case I_RPAR:
                        printf("rpar %d\n", inst->n);
                        break;
                }
        }
}
#endif

Reprog *re_regcomp(const char *pattern, int cflags, const char **errorp) {
        Reprog *prog;
        Restate *g;
        Renode *node;
        Reinst *split, *jump;
        int i;
        unsigned int ncount;
        size_t pattern_len = strlen(pattern);

        if (pattern_len > 10000) {
                /* Avoid stack exhaustion in recursive parseatom() et.al. */
                if (errorp)
                        *errorp = "regexp pattern too long (max 10000)";
                return NULL;
        }

        prog      = rd_calloc(1, sizeof(Reprog));
        g         = &prog->g;
        g->prog   = prog;
        g->pstart = g->pend = rd_malloc(sizeof(Renode) * pattern_len * 2);

        if (setjmp(g->kaboom)) {
                if (errorp)
                        *errorp = g->error;
                rd_free(g->pstart);
                rd_free(prog);
                return NULL;
        }

        g->source  = pattern;
        g->ncclass = 0;
        g->nsub    = 1;
        for (i = 0; i < MAXSUB; ++i)
                g->sub[i] = 0;

        g->prog->flags = cflags;

        next(g);
        node = parsealt(g);
        if (g->lookahead == ')')
                die(g, "unmatched ')'");
        if (g->lookahead != 0)
                die(g, "syntax error");

        g->prog->nsub = g->nsub;
        ncount        = count(node);
        if (ncount > 10000)
                die(g, "regexp graph too large");
        g->prog->start = g->prog->end =
            rd_malloc((ncount + 6) * sizeof(Reinst));

        split    = emit(g->prog, I_SPLIT);
        split->x = split + 3;
        split->y = split + 1;
        emit(g->prog, I_ANYNL);
        jump    = emit(g->prog, I_JUMP);
        jump->x = split;
        emit(g->prog, I_LPAR);
        compile(g->prog, node);
        emit(g->prog, I_RPAR);
        emit(g->prog, I_END);

#ifdef TEST
        dumpnode(node);
        putchar('\n');
        dumpprog(g->prog);
#endif

        rd_free(g->pstart);

        if (errorp)
                *errorp = NULL;
        return g->prog;
}

void re_regfree(Reprog *prog) {
        if (prog) {
                rd_free(prog->start);
                rd_free(prog);
        }
}

/* Match */

static int isnewline(int c) {
        return c == 0xA || c == 0xD || c == 0x2028 || c == 0x2029;
}

static int iswordchar(int c) {
        return c == '_' || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
               (c >= '0' && c <= '9');
}

static int incclass(Reclass *cc, Rune c) {
        Rune *p;
        for (p = cc->spans; p < cc->end; p += 2)
                if (p[0] <= c && c <= p[1])
                        return 1;
        return 0;
}

static int incclasscanon(Reclass *cc, Rune c) {
        Rune *p, r;
        for (p = cc->spans; p < cc->end; p += 2)
                for (r = p[0]; r <= p[1]; ++r)
                        if (c == canon(r))
                                return 1;
        return 0;
}

static int strncmpcanon(const char *a, const char *b, unsigned int n) {
        Rune ra, rb;
        int c;
        while (n--) {
                if (!*a)
                        return -1;
                if (!*b)
                        return 1;
                a += chartorune(&ra, a);
                b += chartorune(&rb, b);
                c = canon(ra) - canon(rb);
                if (c)
                        return c;
        }
        return 0;
}

struct Rethread {
        Reinst *pc;
        const char *sp;
        Resub sub;
};

static void spawn(Rethread *t, Reinst *pc, const char *sp, Resub *sub) {
        t->pc = pc;
        t->sp = sp;
        memcpy(&t->sub, sub, sizeof t->sub);
}

static int
match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out) {
        Rethread ready[MAXTHREAD];
        Resub scratch;
        Resub sub;
        Rune c;
        unsigned int nready;
        int i;

        /* queue initial thread */
        spawn(ready + 0, pc, sp, out);
        nready = 1;

        /* run threads in stack order */
        while (nready > 0) {
                --nready;
                pc = ready[nready].pc;
                sp = ready[nready].sp;
                memcpy(&sub, &ready[nready].sub, sizeof sub);
                for (;;) {
                        switch (pc->opcode) {
                        case I_END:
                                for (i = 0; i < MAXSUB; ++i) {
                                        out->sub[i].sp = sub.sub[i].sp;
                                        out->sub[i].ep = sub.sub[i].ep;
                                }
                                return 1;
                        case I_JUMP:
                                pc = pc->x;
                                continue;
                        case I_SPLIT:
                                if (nready >= MAXTHREAD) {
                                        fprintf(
                                            stderr,
                                            "regexec: backtrack overflow!\n");
                                        return 0;
                                }
                                spawn(&ready[nready++], pc->y, sp, &sub);
                                pc = pc->x;
                                continue;

                        case I_PLA:
                                if (!match(pc->x, sp, bol, flags, &sub))
                                        goto dead;
                                pc = pc->y;
                                continue;
                        case I_NLA:
                                memcpy(&scratch, &sub, sizeof scratch);
                                if (match(pc->x, sp, bol, flags, &scratch))
                                        goto dead;
                                pc = pc->y;
                                continue;

                        case I_ANYNL:
                                sp += chartorune(&c, sp);
                                if (c == 0)
                                        goto dead;
                                break;
                        case I_ANY:
                                sp += chartorune(&c, sp);
                                if (c == 0)
                                        goto dead;
                                if (isnewline(c))
                                        goto dead;
                                break;
                        case I_CHAR:
                                sp += chartorune(&c, sp);
                                if (c == 0)
                                        goto dead;
                                if (flags & REG_ICASE)
                                        c = canon(c);
                                if (c != pc->c)
                                        goto dead;
                                break;
                        case I_CCLASS:
                                sp += chartorune(&c, sp);
                                if (c == 0)
                                        goto dead;
                                if (flags & REG_ICASE) {
                                        if (!incclasscanon(pc->cc, canon(c)))
                                                goto dead;
                                } else {
                                        if (!incclass(pc->cc, c))
                                                goto dead;
                                }
                                break;
                        case I_NCCLASS:
                                sp += chartorune(&c, sp);
                                if (c == 0)
                                        goto dead;
                                if (flags & REG_ICASE) {
                                        if (incclasscanon(pc->cc, canon(c)))
                                                goto dead;
                                } else {
                                        if (incclass(pc->cc, c))
                                                goto dead;
                                }
                                break;
                        case I_REF:
                                i = (int)(sub.sub[pc->n].ep -
                                          sub.sub[pc->n].sp);
                                if (flags & REG_ICASE) {
                                        if (strncmpcanon(sp, sub.sub[pc->n].sp,
                                                         i))
                                                goto dead;
                                } else {
                                        if (strncmp(sp, sub.sub[pc->n].sp, i))
                                                goto dead;
                                }
                                if (i > 0)
                                        sp += i;
                                break;

                        case I_BOL:
                                if (sp == bol && !(flags & REG_NOTBOL))
                                        break;
                                if (flags & REG_NEWLINE)
                                        if (sp > bol && isnewline(sp[-1]))
                                                break;
                                goto dead;
                        case I_EOL:
                                if (*sp == 0)
                                        break;
                                if (flags & REG_NEWLINE)
                                        if (isnewline(*sp))
                                                break;
                                goto dead;
                        case I_WORD:
                                i = sp > bol && iswordchar(sp[-1]);
                                i ^= iswordchar(sp[0]);
                                if (i)
                                        break;
                                goto dead;
                        case I_NWORD:
                                i = sp > bol && iswordchar(sp[-1]);
                                i ^= iswordchar(sp[0]);
                                if (!i)
                                        break;
                                goto dead;

                        case I_LPAR:
                                sub.sub[pc->n].sp = sp;
                                break;
                        case I_RPAR:
                                sub.sub[pc->n].ep = sp;
                                break;
                        default:
                                goto dead;
                        }
                        pc = pc + 1;
                }
        dead:;
        }
        return 0;
}

int re_regexec(Reprog *prog, const char *sp, Resub *sub, int eflags) {
        Resub scratch;
        int i;

        if (!sub)
                sub = &scratch;

        sub->nsub = prog->nsub;
        for (i = 0; i < MAXSUB; ++i)
                sub->sub[i].sp = sub->sub[i].ep = NULL;

        return !match(prog->start, sp, sp, prog->flags | eflags, sub);
}

#ifdef TEST
int main(int argc, char **argv) {
        const char *error;
        const char *s;
        Reprog *p;
        Resub m;
        unsigned int i;

        if (argc > 1) {
                p = regcomp(argv[1], 0, &error);
                if (!p) {
                        fprintf(stderr, "regcomp: %s\n", error);
                        return 1;
                }

                if (argc > 2) {
                        s = argv[2];
                        printf("nsub = %d\n", p->nsub);
                        if (!regexec(p, s, &m, 0)) {
                                for (i = 0; i < m.nsub; ++i) {
                                        int n = m.sub[i].ep - m.sub[i].sp;
                                        if (n > 0)
                                                printf(
                                                    "match %d: s=%d e=%d n=%d "
                                                    "'%.*s'\n",
                                                    i, (int)(m.sub[i].sp - s),
                                                    (int)(m.sub[i].ep - s), n,
                                                    n, m.sub[i].sp);
                                        else
                                                printf("match %d: n=0 ''\n", i);
                                }
                        } else {
                                printf("no match\n");
                        }
                }
        }

        return 0;
}
#endif