/* regexpr.c * * Author: Tatu Ylonen * * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland * * Permission to use, copy, modify, distribute, and sell this software * and its documentation for any purpose is hereby granted without * fee, provided that the above copyright notice appear in all copies. * This software is provided "as is" without express or implied * warranty. * * Created: Thu Sep 26 17:14:05 1991 ylo * Last modified: Mon Nov 4 17:06:48 1991 ylo * Ported to Think C: 19 Jan 1992 guido@cwi.nl * * This code draws many ideas from the regular expression packages by * Henry Spencer of the University of Toronto and Richard Stallman of * the Free Software Foundation. * * Emacs-specific code and syntax table code is almost directly borrowed * from GNU regexp. * * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and * probably one or two others that I'm forgetting. * * $Id: regexpr.c 28049 2002-08-07 16:21:51Z loewis $ */ #include "Python.h" #include "regexpr.h" /* The original code blithely assumed that sizeof(short) == 2. Not * always true. Original instances of "(short)x" were replaced by * SHORT(x), where SHORT is #defined below. */ #define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x)) /* The stack implementation is taken from an idea by Andrew Kuchling. * It's a doubly linked list of arrays. The advantages of this over a * simple linked list are that the number of mallocs required are * reduced. It also makes it possible to statically allocate enough * space so that small patterns don't ever need to call malloc. * * The advantages over a single array is that is periodically * realloced when more space is needed is that we avoid ever copying * the stack. */ /* item_t is the basic stack element. Defined as a union of * structures so that both registers, failure points, and counters can * be pushed/popped from the stack. There's nothing built into the * item to keep track of whether a certain stack item is a register, a * failure point, or a counter. */ typedef union item_t { struct { int num; int level; unsigned char *start; unsigned char *end; } reg; struct { int count; int level; int phantom; unsigned char *code; unsigned char *text; } fail; struct { int num; int level; int count; } cntr; } item_t; #define STACK_PAGE_SIZE 256 #define NUM_REGISTERS 256 /* A 'page' of stack items. */ typedef struct item_page_t { item_t items[STACK_PAGE_SIZE]; struct item_page_t *prev; struct item_page_t *next; } item_page_t; typedef struct match_state { /* The number of registers that have been pushed onto the stack * since the last failure point. */ int count; /* Used to control when registers need to be pushed onto the * stack. */ int level; /* The number of failure points on the stack. */ int point; /* Storage for the registers. Each register consists of two * pointers to characters. So register N is represented as * start[N] and end[N]. The pointers must be converted to * offsets from the beginning of the string before returning the * registers to the calling program. */ unsigned char *start[NUM_REGISTERS]; unsigned char *end[NUM_REGISTERS]; /* Keeps track of whether a register has changed recently. */ int changed[NUM_REGISTERS]; /* Structure to encapsulate the stack. */ struct { /* index into the current page. If index == 0 and you need * to pop an item, move to the previous page and set index * = STACK_PAGE_SIZE - 1. Otherwise decrement index to * push a page. If index == STACK_PAGE_SIZE and you need * to push a page move to the next page and set index = * 0. If there is no new next page, allocate a new page * and link it in. Otherwise, increment index to push a * page. */ int index; item_page_t *current; /* Pointer to the current page. */ item_page_t first; /* First page is statically allocated. */ } stack; } match_state; /* Initialize a state object */ /* #define NEW_STATE(state) \ */ /* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */ /* state.stack.current = &state.stack.first; \ */ /* state.stack.first.prev = NULL; \ */ /* state.stack.first.next = NULL; \ */ /* state.stack.index = 0; \ */ /* state.level = 1 */ #define NEW_STATE(state, nregs) \ { \ int i; \ for (i = 0; i < nregs; i++) \ { \ state.start[i] = NULL; \ state.end[i] = NULL; \ state.changed[i] = 0; \ } \ state.stack.current = &state.stack.first; \ state.stack.first.prev = NULL; \ state.stack.first.next = NULL; \ state.stack.index = 0; \ state.level = 1; \ state.count = 0; \ state.level = 0; \ state.point = 0; \ } /* Free any memory that might have been malloc'd */ #define FREE_STATE(state) \ while(state.stack.first.next != NULL) \ { \ state.stack.current = state.stack.first.next; \ state.stack.first.next = state.stack.current->next; \ free(state.stack.current); \ } /* Discard the top 'count' stack items. */ #define STACK_DISCARD(stack, count, on_error) \ stack.index -= count; \ while (stack.index < 0) \ { \ if (stack.current->prev == NULL) \ on_error; \ stack.current = stack.current->prev; \ stack.index += STACK_PAGE_SIZE; \ } /* Store a pointer to the previous item on the stack. Used to pop an * item off of the stack. */ #define STACK_PREV(stack, top, on_error) \ if (stack.index == 0) \ { \ if (stack.current->prev == NULL) \ on_error; \ stack.current = stack.current->prev; \ stack.index = STACK_PAGE_SIZE - 1; \ } \ else \ { \ stack.index--; \ } \ top = &(stack.current->items[stack.index]) /* Store a pointer to the next item on the stack. Used to push an item * on to the stack. */ #define STACK_NEXT(stack, top, on_error) \ if (stack.index == STACK_PAGE_SIZE) \ { \ if (stack.current->next == NULL) \ { \ stack.current->next = (item_page_t *)malloc(sizeof(item_page_t)); \ if (stack.current->next == NULL) \ on_error; \ stack.current->next->prev = stack.current; \ stack.current->next->next = NULL; \ } \ stack.current = stack.current->next; \ stack.index = 0; \ } \ top = &(stack.current->items[stack.index++]) /* Store a pointer to the item that is 'count' items back in the * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to * STACK_TOP(stack, top, on_error). */ #define STACK_BACK(stack, top, count, on_error) \ { \ int index; \ item_page_t *current; \ current = stack.current; \ index = stack.index - (count); \ while (index < 0) \ { \ if (current->prev == NULL) \ on_error; \ current = current->prev; \ index += STACK_PAGE_SIZE; \ } \ top = &(current->items[index]); \ } /* Store a pointer to the top item on the stack. Execute the * 'on_error' code if there are no items on the stack. */ #define STACK_TOP(stack, top, on_error) \ if (stack.index == 0) \ { \ if (stack.current->prev == NULL) \ on_error; \ top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \ } \ else \ { \ top = &(stack.current->items[stack.index - 1]); \ } /* Test to see if the stack is empty */ #define STACK_EMPTY(stack) ((stack.index == 0) && \ (stack.current->prev == NULL)) /* Return the start of register 'reg' */ #define GET_REG_START(state, reg) (state.start[reg]) /* Return the end of register 'reg' */ #define GET_REG_END(state, reg) (state.end[reg]) /* Set the start of register 'reg'. If the state of the register needs * saving, push it on the stack. */ #define SET_REG_START(state, reg, text, on_error) \ if(state.changed[reg] < state.level) \ { \ item_t *item; \ STACK_NEXT(state.stack, item, on_error); \ item->reg.num = reg; \ item->reg.start = state.start[reg]; \ item->reg.end = state.end[reg]; \ item->reg.level = state.changed[reg]; \ state.changed[reg] = state.level; \ state.count++; \ } \ state.start[reg] = text /* Set the end of register 'reg'. If the state of the register needs * saving, push it on the stack. */ #define SET_REG_END(state, reg, text, on_error) \ if(state.changed[reg] < state.level) \ { \ item_t *item; \ STACK_NEXT(state.stack, item, on_error); \ item->reg.num = reg; \ item->reg.start = state.start[reg]; \ item->reg.end = state.end[reg]; \ item->reg.level = state.changed[reg]; \ state.changed[reg] = state.level; \ state.count++; \ } \ state.end[reg] = text #define PUSH_FAILURE(state, xcode, xtext, on_error) \ { \ item_t *item; \ STACK_NEXT(state.stack, item, on_error); \ item->fail.code = xcode; \ item->fail.text = xtext; \ item->fail.count = state.count; \ item->fail.level = state.level; \ item->fail.phantom = 0; \ state.count = 0; \ state.level++; \ state.point++; \ } /* Update the last failure point with a new position in the text. */ #define UPDATE_FAILURE(state, xtext, on_error) \ { \ item_t *item; \ STACK_BACK(state.stack, item, state.count + 1, on_error); \ if (!item->fail.phantom) \ { \ item_t *item2; \ STACK_NEXT(state.stack, item2, on_error); \ item2->fail.code = item->fail.code; \ item2->fail.text = xtext; \ item2->fail.count = state.count; \ item2->fail.level = state.level; \ item2->fail.phantom = 1; \ state.count = 0; \ state.level++; \ state.point++; \ } \ else \ { \ STACK_DISCARD(state.stack, state.count, on_error); \ STACK_TOP(state.stack, item, on_error); \ item->fail.text = xtext; \ state.count = 0; \ state.level++; \ } \ } #define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \ { \ item_t *item; \ do \ { \ while(state.count > 0) \ { \ STACK_PREV(state.stack, item, on_error); \ state.start[item->reg.num] = item->reg.start; \ state.end[item->reg.num] = item->reg.end; \ state.changed[item->reg.num] = item->reg.level; \ state.count--; \ } \ STACK_PREV(state.stack, item, on_empty); \ xcode = item->fail.code; \ xtext = item->fail.text; \ state.count = item->fail.count; \ state.level = item->fail.level; \ state.point--; \ } \ while (item->fail.text == NULL); \ } enum regexp_compiled_ops /* opcodes for compiled regexp */ { Cend, /* end of pattern reached */ Cbol, /* beginning of line */ Ceol, /* end of line */ Cset, /* character set. Followed by 32 bytes of set. */ Cexact, /* followed by a byte to match */ Canychar, /* matches any character except newline */ Cstart_memory, /* set register start addr (followed by reg number) */ Cend_memory, /* set register end addr (followed by reg number) */ Cmatch_memory, /* match a duplicate of reg contents (regnum follows)*/ Cjump, /* followed by two bytes (lsb,msb) of displacement. */ Cstar_jump, /* will change to jump/update_failure_jump at runtime */ Cfailure_jump, /* jump to addr on failure */ Cupdate_failure_jump, /* update topmost failure point and jump */ Cdummy_failure_jump, /* push a dummy failure point and jump */ Cbegbuf, /* match at beginning of buffer */ Cendbuf, /* match at end of buffer */ Cwordbeg, /* match at beginning of word */ Cwordend, /* match at end of word */ Cwordbound, /* match if at word boundary */ Cnotwordbound, /* match if not at word boundary */ Csyntaxspec, /* matches syntax code (1 byte follows) */ Cnotsyntaxspec, /* matches if syntax code does not match (1 byte follows) */ Crepeat1 }; enum regexp_syntax_op /* syntax codes for plain and quoted characters */ { Rend, /* special code for end of regexp */ Rnormal, /* normal character */ Ranychar, /* any character except newline */ Rquote, /* the quote character */ Rbol, /* match beginning of line */ Reol, /* match end of line */ Roptional, /* match preceding expression optionally */ Rstar, /* match preceding expr zero or more times */ Rplus, /* match preceding expr one or more times */ Ror, /* match either of alternatives */ Ropenpar, /* opening parenthesis */ Rclosepar, /* closing parenthesis */ Rmemory, /* match memory register */ Rextended_memory, /* \vnn to match registers 10-99 */ Ropenset, /* open set. Internal syntax hard-coded below. */ /* the following are gnu extensions to "normal" regexp syntax */ Rbegbuf, /* beginning of buffer */ Rendbuf, /* end of buffer */ Rwordchar, /* word character */ Rnotwordchar, /* not word character */ Rwordbeg, /* beginning of word */ Rwordend, /* end of word */ Rwordbound, /* word bound */ Rnotwordbound, /* not word bound */ Rnum_ops }; static int re_compile_initialized = 0; static int regexp_syntax = 0; int re_syntax = 0; /* Exported copy of regexp_syntax */ static unsigned char regexp_plain_ops[256]; static unsigned char regexp_quoted_ops[256]; static unsigned char regexp_precedences[Rnum_ops]; static int regexp_context_indep_ops; static int regexp_ansi_sequences; #define NUM_LEVELS 5 /* number of precedence levels in use */ #define MAX_NESTING 100 /* max nesting level of operators */ #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)] unsigned char re_syntax_table[256]; void re_compile_initialize(void) { int a; static int syntax_table_inited = 0; if (!syntax_table_inited) { syntax_table_inited = 1; memset(re_syntax_table, 0, 256); for (a = 'a'; a <= 'z'; a++) re_syntax_table[a] = Sword; for (a = 'A'; a <= 'Z'; a++) re_syntax_table[a] = Sword; for (a = '0'; a <= '9'; a++) re_syntax_table[a] = Sword | Sdigit | Shexdigit; for (a = '0'; a <= '7'; a++) re_syntax_table[a] |= Soctaldigit; for (a = 'A'; a <= 'F'; a++) re_syntax_table[a] |= Shexdigit; for (a = 'a'; a <= 'f'; a++) re_syntax_table[a] |= Shexdigit; re_syntax_table['_'] = Sword; for (a = 9; a <= 13; a++) re_syntax_table[a] = Swhitespace; re_syntax_table[' '] = Swhitespace; } re_compile_initialized = 1; for (a = 0; a < 256; a++) { regexp_plain_ops[a] = Rnormal; regexp_quoted_ops[a] = Rnormal; } for (a = '0'; a <= '9'; a++) regexp_quoted_ops[a] = Rmemory; regexp_plain_ops['\134'] = Rquote; if (regexp_syntax & RE_NO_BK_PARENS) { regexp_plain_ops['('] = Ropenpar; regexp_plain_ops[')'] = Rclosepar; } else { regexp_quoted_ops['('] = Ropenpar; regexp_quoted_ops[')'] = Rclosepar; } if (regexp_syntax & RE_NO_BK_VBAR) regexp_plain_ops['\174'] = Ror; else regexp_quoted_ops['\174'] = Ror; regexp_plain_ops['*'] = Rstar; if (regexp_syntax & RE_BK_PLUS_QM) { regexp_quoted_ops['+'] = Rplus; regexp_quoted_ops['?'] = Roptional; } else { regexp_plain_ops['+'] = Rplus; regexp_plain_ops['?'] = Roptional; } if (regexp_syntax & RE_NEWLINE_OR) regexp_plain_ops['\n'] = Ror; regexp_plain_ops['\133'] = Ropenset; regexp_plain_ops['\136'] = Rbol; regexp_plain_ops['$'] = Reol; regexp_plain_ops['.'] = Ranychar; if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS)) { regexp_quoted_ops['w'] = Rwordchar; regexp_quoted_ops['W'] = Rnotwordchar; regexp_quoted_ops['<'] = Rwordbeg; regexp_quoted_ops['>'] = Rwordend; regexp_quoted_ops['b'] = Rwordbound; regexp_quoted_ops['B'] = Rnotwordbound; regexp_quoted_ops['`'] = Rbegbuf; regexp_quoted_ops['\''] = Rendbuf; } if (regexp_syntax & RE_ANSI_HEX) regexp_quoted_ops['v'] = Rextended_memory; for (a = 0; a < Rnum_ops; a++) regexp_precedences[a] = 4; if (regexp_syntax & RE_TIGHT_VBAR) { regexp_precedences[Ror] = 3; regexp_precedences[Rbol] = 2; regexp_precedences[Reol] = 2; } else { regexp_precedences[Ror] = 2; regexp_precedences[Rbol] = 3; regexp_precedences[Reol] = 3; } regexp_precedences[Rclosepar] = 1; regexp_precedences[Rend] = 0; regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0; regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0; } int re_set_syntax(int syntax) { int ret; ret = regexp_syntax; regexp_syntax = syntax; re_syntax = syntax; /* Exported copy */ re_compile_initialize(); return ret; } static int hex_char_to_decimal(int ch) { if (ch >= '0' && ch <= '9') return ch - '0'; if (ch >= 'a' && ch <= 'f') return ch - 'a' + 10; if (ch >= 'A' && ch <= 'F') return ch - 'A' + 10; return 16; } static void re_compile_fastmap_aux(unsigned char *code, int pos, unsigned char *visited, unsigned char *can_be_null, unsigned char *fastmap) { int a; int b; int syntaxcode; if (visited[pos]) return; /* we have already been here */ visited[pos] = 1; for (;;) switch (code[pos++]) { case Cend: { *can_be_null = 1; return; } case Cbol: case Cbegbuf: case Cendbuf: case Cwordbeg: case Cwordend: case Cwordbound: case Cnotwordbound: { for (a = 0; a < 256; a++) fastmap[a] = 1; break; } case Csyntaxspec: { syntaxcode = code[pos++]; for (a = 0; a < 256; a++) if (SYNTAX(a) & syntaxcode) fastmap[a] = 1; return; } case Cnotsyntaxspec: { syntaxcode = code[pos++]; for (a = 0; a < 256; a++) if (!(SYNTAX(a) & syntaxcode) ) fastmap[a] = 1; return; } case Ceol: { fastmap['\n'] = 1; if (*can_be_null == 0) *can_be_null = 2; /* can match null, but only at end of buffer*/ return; } case Cset: { for (a = 0; a < 256/8; a++) if (code[pos + a] != 0) for (b = 0; b < 8; b++) if (code[pos + a] & (1 << b)) fastmap[(a << 3) + b] = 1; pos += 256/8; return; } case Cexact: { fastmap[(unsigned char)code[pos]] = 1; return; } case Canychar: { for (a = 0; a < 256; a++) if (a != '\n') fastmap[a] = 1; return; } case Cstart_memory: case Cend_memory: { pos++; break; } case Cmatch_memory: { for (a = 0; a < 256; a++) fastmap[a] = 1; *can_be_null = 1; return; } case Cjump: case Cdummy_failure_jump: case Cupdate_failure_jump: case Cstar_jump: { a = (unsigned char)code[pos++]; a |= (unsigned char)code[pos++] << 8; pos += (int)SHORT(a); if (visited[pos]) { /* argh... the regexp contains empty loops. This is not good, as this may cause a failure stack overflow when matching. Oh well. */ /* this path leads nowhere; pursue other paths. */ return; } visited[pos] = 1; break; } case Cfailure_jump: { a = (unsigned char)code[pos++]; a |= (unsigned char)code[pos++] << 8; a = pos + (int)SHORT(a); re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap); break; } case Crepeat1: { pos += 2; break; } default: { PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?"); return; /*NOTREACHED*/ } } } static int re_do_compile_fastmap(unsigned char *buffer, int used, int pos, unsigned char *can_be_null, unsigned char *fastmap) { unsigned char small_visited[512], *visited; if (used <= sizeof(small_visited)) visited = small_visited; else { visited = malloc(used); if (!visited) return 0; } *can_be_null = 0; memset(fastmap, 0, 256); memset(visited, 0, used); re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap); if (visited != small_visited) free(visited); return 1; } void re_compile_fastmap(regexp_t bufp) { if (!bufp->fastmap || bufp->fastmap_accurate) return; assert(bufp->used > 0); if (!re_do_compile_fastmap(bufp->buffer, bufp->used, 0, &bufp->can_be_null, bufp->fastmap)) return; if (PyErr_Occurred()) return; if (bufp->buffer[0] == Cbol) bufp->anchor = 1; /* begline */ else if (bufp->buffer[0] == Cbegbuf) bufp->anchor = 2; /* begbuf */ else bufp->anchor = 0; /* none */ bufp->fastmap_accurate = 1; } /* * star is coded as: * 1: failure_jump 2 * ... code for operand of star * star_jump 1 * 2: ... code after star * * We change the star_jump to update_failure_jump if we can determine * that it is safe to do so; otherwise we change it to an ordinary * jump. * * plus is coded as * * jump 2 * 1: failure_jump 3 * 2: ... code for operand of plus * star_jump 1 * 3: ... code after plus * * For star_jump considerations this is processed identically to star. * */ static int re_optimize_star_jump(regexp_t bufp, unsigned char *code) { unsigned char map[256]; unsigned char can_be_null; unsigned char *p1; unsigned char *p2; unsigned char ch; int a; int b; int num_instructions = 0; a = (unsigned char)*code++; a |= (unsigned char)*code++ << 8; a = (int)SHORT(a); p1 = code + a + 3; /* skip the failure_jump */ /* Check that the jump is within the pattern */ if (p1buffer || bufp->buffer+bufp->usedbuffer, bufp->used, (int)(p2 - bufp->buffer), &can_be_null, map)) goto make_normal_jump; /* If we might introduce a new update point inside the * loop, we can't optimize because then update_jump would * update a wrong failure point. Thus we have to be * quite careful here. */ /* loop until we find something that consumes a character */ loop_p1: num_instructions++; switch (*p1++) { case Cbol: case Ceol: case Cbegbuf: case Cendbuf: case Cwordbeg: case Cwordend: case Cwordbound: case Cnotwordbound: { goto loop_p1; } case Cstart_memory: case Cend_memory: { p1++; goto loop_p1; } case Cexact: { ch = (unsigned char)*p1++; if (map[(int)ch]) goto make_normal_jump; break; } case Canychar: { for (b = 0; b < 256; b++) if (b != '\n' && map[b]) goto make_normal_jump; break; } case Cset: { for (b = 0; b < 256; b++) if ((p1[b >> 3] & (1 << (b & 7))) && map[b]) goto make_normal_jump; p1 += 256/8; break; } default: { goto make_normal_jump; } } /* now we know that we can't backtrack. */ while (p1 != p2 - 3) { num_instructions++; switch (*p1++) { case Cend: { return 0; } case Cbol: case Ceol: case Canychar: case Cbegbuf: case Cendbuf: case Cwordbeg: case Cwordend: case Cwordbound: case Cnotwordbound: { break; } case Cset: { p1 += 256/8; break; } case Cexact: case Cstart_memory: case Cend_memory: case Cmatch_memory: case Csyntaxspec: case Cnotsyntaxspec: { p1++; break; } case Cjump: case Cstar_jump: case Cfailure_jump: case Cupdate_failure_jump: case Cdummy_failure_jump: { goto make_normal_jump; } default: { return 0; } } } /* make_update_jump: */ code -= 3; a += 3; /* jump to after the Cfailure_jump */ code[0] = Cupdate_failure_jump; code[1] = a & 0xff; code[2] = a >> 8; if (num_instructions > 1) return 1; assert(num_instructions == 1); /* if the only instruction matches a single character, we can do * better */ p1 = code + 3 + a; /* start of sole instruction */ if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar || *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec) code[0] = Crepeat1; return 1; make_normal_jump: code -= 3; *code = Cjump; return 1; } static int re_optimize(regexp_t bufp) { unsigned char *code; code = bufp->buffer; while(1) { switch (*code++) { case Cend: { return 1; } case Canychar: case Cbol: case Ceol: case Cbegbuf: case Cendbuf: case Cwordbeg: case Cwordend: case Cwordbound: case Cnotwordbound: { break; } case Cset: { code += 256/8; break; } case Cexact: case Cstart_memory: case Cend_memory: case Cmatch_memory: case Csyntaxspec: case Cnotsyntaxspec: { code++; break; } case Cstar_jump: { if (!re_optimize_star_jump(bufp, code)) { return 0; } /* fall through */ } case Cupdate_failure_jump: case Cjump: case Cdummy_failure_jump: case Cfailure_jump: case Crepeat1: { code += 2; break; } default: { return 0; } } } } #define NEXTCHAR(var) \ { \ if (pos >= size) \ goto ends_prematurely; \ (var) = regex[pos]; \ pos++; \ } #define ALLOC(amount) \ { \ if (pattern_offset+(amount) > alloc) \ { \ alloc += 256 + (amount); \ pattern = realloc(pattern, alloc); \ if (!pattern) \ goto out_of_memory; \ } \ } #define STORE(ch) pattern[pattern_offset++] = (ch) #define CURRENT_LEVEL_START (starts[starts_base + current_level]) #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset #define PUSH_LEVEL_STARTS \ if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \ starts_base += NUM_LEVELS; \ else \ goto too_complex \ #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS #define PUT_ADDR(offset,addr) \ { \ int disp = (addr) - (offset) - 2; \ pattern[(offset)] = disp & 0xff; \ pattern[(offset)+1] = (disp>>8) & 0xff; \ } #define INSERT_JUMP(pos,type,addr) \ { \ int a, p = (pos), t = (type), ad = (addr); \ for (a = pattern_offset - 1; a >= p; a--) \ pattern[a + 3] = pattern[a]; \ pattern[p] = t; \ PUT_ADDR(p+1,ad); \ pattern_offset += 3; \ } #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7)) #define SET_FIELDS \ { \ bufp->allocated = alloc; \ bufp->buffer = pattern; \ bufp->used = pattern_offset; \ } #define GETHEX(var) \ { \ unsigned char gethex_ch, gethex_value; \ NEXTCHAR(gethex_ch); \ gethex_value = hex_char_to_decimal(gethex_ch); \ if (gethex_value == 16) \ goto hex_error; \ NEXTCHAR(gethex_ch); \ gethex_ch = hex_char_to_decimal(gethex_ch); \ if (gethex_ch == 16) \ goto hex_error; \ (var) = gethex_value * 16 + gethex_ch; \ } #define ANSI_TRANSLATE(ch) \ { \ switch (ch) \ { \ case 'a': \ case 'A': \ { \ ch = 7; /* audible bell */ \ break; \ } \ case 'b': \ case 'B': \ { \ ch = 8; /* backspace */ \ break; \ } \ case 'f': \ case 'F': \ { \ ch = 12; /* form feed */ \ break; \ } \ case 'n': \ case 'N': \ { \ ch = 10; /* line feed */ \ break; \ } \ case 'r': \ case 'R': \ { \ ch = 13; /* carriage return */ \ break; \ } \ case 't': \ case 'T': \ { \ ch = 9; /* tab */ \ break; \ } \ case 'v': \ case 'V': \ { \ ch = 11; /* vertical tab */ \ break; \ } \ case 'x': /* hex code */ \ case 'X': \ { \ GETHEX(ch); \ break; \ } \ default: \ { \ /* other characters passed through */ \ if (translate) \ ch = translate[(unsigned char)ch]; \ break; \ } \ } \ } char *re_compile_pattern(unsigned char *regex, int size, regexp_t bufp) { int a; int pos; int op; int current_level; int level; int opcode; int pattern_offset = 0, alloc; int starts[NUM_LEVELS * MAX_NESTING]; int starts_base; int future_jumps[MAX_NESTING]; int num_jumps; unsigned char ch = '\0'; unsigned char *pattern; unsigned char *translate; int next_register; int paren_depth; int num_open_registers; int open_registers[RE_NREGS]; int beginning_context; if (!re_compile_initialized) re_compile_initialize(); bufp->used = 0; bufp->fastmap_accurate = 0; bufp->uses_registers = 1; bufp->num_registers = 1; translate = bufp->translate; pattern = bufp->buffer; alloc = bufp->allocated; if (alloc == 0 || pattern == NULL) { alloc = 256; pattern = malloc(alloc); if (!pattern) goto out_of_memory; } pattern_offset = 0; starts_base = 0; num_jumps = 0; current_level = 0; SET_LEVEL_START; num_open_registers = 0; next_register = 1; paren_depth = 0; beginning_context = 1; op = -1; /* we use Rend dummy to ensure that pending jumps are updated (due to low priority of Rend) before exiting the loop. */ pos = 0; while (op != Rend) { if (pos >= size) op = Rend; else { NEXTCHAR(ch); if (translate) ch = translate[(unsigned char)ch]; op = regexp_plain_ops[(unsigned char)ch]; if (op == Rquote) { NEXTCHAR(ch); op = regexp_quoted_ops[(unsigned char)ch]; if (op == Rnormal && regexp_ansi_sequences) ANSI_TRANSLATE(ch); } } level = regexp_precedences[op]; /* printf("ch='%c' op=%d level=%d current_level=%d curlevstart=%d\n", ch, op, level, current_level, CURRENT_LEVEL_START); */ if (level > current_level) { for (current_level++; current_level < level; current_level++) SET_LEVEL_START; SET_LEVEL_START; } else if (level < current_level) { current_level = level; for (;num_jumps > 0 && future_jumps[num_jumps-1] >= CURRENT_LEVEL_START; num_jumps--) PUT_ADDR(future_jumps[num_jumps-1], pattern_offset); } switch (op) { case Rend: { break; } case Rnormal: { normal_char: opcode = Cexact; store_opcode_and_arg: /* opcode & ch must be set */ SET_LEVEL_START; ALLOC(2); STORE(opcode); STORE(ch); break; } case Ranychar: { opcode = Canychar; store_opcode: SET_LEVEL_START; ALLOC(1); STORE(opcode); break; } case Rquote: { Py_FatalError("Rquote"); /*NOTREACHED*/ } case Rbol: { if (!beginning_context) { if (regexp_context_indep_ops) goto op_error; else goto normal_char; } opcode = Cbol; goto store_opcode; } case Reol: { if (!((pos >= size) || ((regexp_syntax & RE_NO_BK_VBAR) ? (regex[pos] == '\174') : (pos+1 < size && regex[pos] == '\134' && regex[pos+1] == '\174')) || ((regexp_syntax & RE_NO_BK_PARENS)? (regex[pos] == ')'): (pos+1 < size && regex[pos] == '\134' && regex[pos+1] == ')')))) { if (regexp_context_indep_ops) goto op_error; else goto normal_char; } opcode = Ceol; goto store_opcode; /* NOTREACHED */ break; } case Roptional: { if (beginning_context) { if (regexp_context_indep_ops) goto op_error; else goto normal_char; } if (CURRENT_LEVEL_START == pattern_offset) break; /* ignore empty patterns for ? */ ALLOC(3); INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, pattern_offset + 3); break; } case Rstar: case Rplus: { if (beginning_context) { if (regexp_context_indep_ops) goto op_error; else goto normal_char; } if (CURRENT_LEVEL_START == pattern_offset) break; /* ignore empty patterns for + and * */ ALLOC(9); INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, pattern_offset + 6); INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START); if (op == Rplus) /* jump over initial failure_jump */ INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump, CURRENT_LEVEL_START + 6); break; } case Ror: { ALLOC(6); INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, pattern_offset + 6); if (num_jumps >= MAX_NESTING) goto too_complex; STORE(Cjump); future_jumps[num_jumps++] = pattern_offset; STORE(0); STORE(0); SET_LEVEL_START; break; } case Ropenpar: { SET_LEVEL_START; if (next_register < RE_NREGS) { bufp->uses_registers = 1; ALLOC(2); STORE(Cstart_memory); STORE(next_register); open_registers[num_open_registers++] = next_register; bufp->num_registers++; next_register++; } paren_depth++; PUSH_LEVEL_STARTS; current_level = 0; SET_LEVEL_START; break; } case Rclosepar: { if (paren_depth <= 0) goto parenthesis_error; POP_LEVEL_STARTS; current_level = regexp_precedences[Ropenpar]; paren_depth--; if (paren_depth < num_open_registers) { bufp->uses_registers = 1; ALLOC(2); STORE(Cend_memory); num_open_registers--; STORE(open_registers[num_open_registers]); } break; } case Rmemory: { if (ch == '0') goto bad_match_register; assert(ch >= '0' && ch <= '9'); bufp->uses_registers = 1; opcode = Cmatch_memory; ch -= '0'; goto store_opcode_and_arg; } case Rextended_memory: { NEXTCHAR(ch); if (ch < '0' || ch > '9') goto bad_match_register; NEXTCHAR(a); if (a < '0' || a > '9') goto bad_match_register; ch = 10 * (a - '0') + ch - '0'; if (ch == 0 || ch >= RE_NREGS) goto bad_match_register; bufp->uses_registers = 1; opcode = Cmatch_memory; goto store_opcode_and_arg; } case Ropenset: { int complement; int prev; int offset; int range; int firstchar; SET_LEVEL_START; ALLOC(1+256/8); STORE(Cset); offset = pattern_offset; for (a = 0; a < 256/8; a++) STORE(0); NEXTCHAR(ch); if (translate) ch = translate[(unsigned char)ch]; if (ch == '\136') { complement = 1; NEXTCHAR(ch); if (translate) ch = translate[(unsigned char)ch]; } else complement = 0; prev = -1; range = 0; firstchar = 1; while (ch != '\135' || firstchar) { firstchar = 0; if (regexp_ansi_sequences && ch == '\134') { NEXTCHAR(ch); ANSI_TRANSLATE(ch); } if (range) { for (a = prev; a <= (int)ch; a++) SETBIT(pattern, offset, a); prev = -1; range = 0; } else if (prev != -1 && ch == '-') range = 1; else { SETBIT(pattern, offset, ch); prev = ch; } NEXTCHAR(ch); if (translate) ch = translate[(unsigned char)ch]; } if (range) SETBIT(pattern, offset, '-'); if (complement) { for (a = 0; a < 256/8; a++) pattern[offset+a] ^= 0xff; } break; } case Rbegbuf: { opcode = Cbegbuf; goto store_opcode; } case Rendbuf: { opcode = Cendbuf; goto store_opcode; } case Rwordchar: { opcode = Csyntaxspec; ch = Sword; goto store_opcode_and_arg; } case Rnotwordchar: { opcode = Cnotsyntaxspec; ch = Sword; goto store_opcode_and_arg; } case Rwordbeg: { opcode = Cwordbeg; goto store_opcode; } case Rwordend: { opcode = Cwordend; goto store_opcode; } case Rwordbound: { opcode = Cwordbound; goto store_opcode; } case Rnotwordbound: { opcode = Cnotwordbound; goto store_opcode; } default: { abort(); } } beginning_context = (op == Ropenpar || op == Ror); } if (starts_base != 0) goto parenthesis_error; assert(num_jumps == 0); ALLOC(1); STORE(Cend); SET_FIELDS; if(!re_optimize(bufp)) return "Optimization error"; return NULL; op_error: SET_FIELDS; return "Badly placed special character"; bad_match_register: SET_FIELDS; return "Bad match register number"; hex_error: SET_FIELDS; return "Bad hexadecimal number"; parenthesis_error: SET_FIELDS; return "Badly placed parenthesis"; out_of_memory: SET_FIELDS; return "Out of memory"; ends_prematurely: SET_FIELDS; return "Regular expression ends prematurely"; too_complex: SET_FIELDS; return "Regular expression too complex"; } #undef CHARAT #undef NEXTCHAR #undef GETHEX #undef ALLOC #undef STORE #undef CURRENT_LEVEL_START #undef SET_LEVEL_START #undef PUSH_LEVEL_STARTS #undef POP_LEVEL_STARTS #undef PUT_ADDR #undef INSERT_JUMP #undef SETBIT #undef SET_FIELDS #define PREFETCH if (text == textend) goto fail #define NEXTCHAR(var) \ PREFETCH; \ var = (unsigned char)*text++; \ if (translate) \ var = translate[var] int re_match(regexp_t bufp, unsigned char *string, int size, int pos, regexp_registers_t old_regs) { unsigned char *code; unsigned char *translate; unsigned char *text; unsigned char *textstart; unsigned char *textend; int a; int b; int ch; int reg; int match_end; unsigned char *regstart; unsigned char *regend; int regsize; match_state state; assert(pos >= 0 && size >= 0); assert(pos <= size); text = string + pos; textstart = string; textend = string + size; code = bufp->buffer; translate = bufp->translate; NEW_STATE(state, bufp->num_registers); continue_matching: switch (*code++) { case Cend: { match_end = text - textstart; if (old_regs) { old_regs->start[0] = pos; old_regs->end[0] = match_end; if (!bufp->uses_registers) { for (a = 1; a < RE_NREGS; a++) { old_regs->start[a] = -1; old_regs->end[a] = -1; } } else { for (a = 1; a < bufp->num_registers; a++) { if ((GET_REG_START(state, a) == NULL) || (GET_REG_END(state, a) == NULL)) { old_regs->start[a] = -1; old_regs->end[a] = -1; continue; } old_regs->start[a] = GET_REG_START(state, a) - textstart; old_regs->end[a] = GET_REG_END(state, a) - textstart; } for (; a < RE_NREGS; a++) { old_regs->start[a] = -1; old_regs->end[a] = -1; } } } FREE_STATE(state); return match_end - pos; } case Cbol: { if (text == textstart || text[-1] == '\n') goto continue_matching; goto fail; } case Ceol: { if (text == textend || *text == '\n') goto continue_matching; goto fail; } case Cset: { NEXTCHAR(ch); if (code[ch/8] & (1<<(ch & 7))) { code += 256/8; goto continue_matching; } goto fail; } case Cexact: { NEXTCHAR(ch); if (ch != (unsigned char)*code++) goto fail; goto continue_matching; } case Canychar: { NEXTCHAR(ch); if (ch == '\n') goto fail; goto continue_matching; } case Cstart_memory: { reg = *code++; SET_REG_START(state, reg, text, goto error); goto continue_matching; } case Cend_memory: { reg = *code++; SET_REG_END(state, reg, text, goto error); goto continue_matching; } case Cmatch_memory: { reg = *code++; regstart = GET_REG_START(state, reg); regend = GET_REG_END(state, reg); if ((regstart == NULL) || (regend == NULL)) goto fail; /* or should we just match nothing? */ regsize = regend - regstart; if (regsize > (textend - text)) goto fail; if(translate) { for (; regstart < regend; regstart++, text++) if (translate[*regstart] != translate[*text]) goto fail; } else for (; regstart < regend; regstart++, text++) if (*regstart != *text) goto fail; goto continue_matching; } case Cupdate_failure_jump: { UPDATE_FAILURE(state, text, goto error); /* fall to next case */ } /* treat Cstar_jump just like Cjump if it hasn't been optimized */ case Cstar_jump: case Cjump: { a = (unsigned char)*code++; a |= (unsigned char)*code++ << 8; code += (int)SHORT(a); if (codebuffer || bufp->buffer+bufp->usedbuffer || bufp->buffer+bufp->used < failuredest) { PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)"); FREE_STATE(state); return -2; } PUSH_FAILURE(state, failuredest, NULL, goto error); code += a; if (codebuffer || bufp->buffer+bufp->used < code) { PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)"); FREE_STATE(state); return -2; } goto continue_matching; } case Cfailure_jump: { a = (unsigned char)*code++; a |= (unsigned char)*code++ << 8; a = (int)SHORT(a); if (code+abuffer || bufp->buffer+bufp->used < code+a) { PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)"); FREE_STATE(state); return -2; } PUSH_FAILURE(state, code + a, text, goto error); goto continue_matching; } case Crepeat1: { unsigned char *pinst; a = (unsigned char)*code++; a |= (unsigned char)*code++ << 8; a = (int)SHORT(a); pinst = code + a; if (pinstbuffer || bufp->buffer+bufp->used */ } case Cbegbuf: { if (text == textstart) goto continue_matching; goto fail; } case Cendbuf: { if (text == textend) goto continue_matching; goto fail; } case Cwordbeg: { if (text == textend) goto fail; if (!(SYNTAX(*text) & Sword)) goto fail; if (text == textstart) goto continue_matching; if (!(SYNTAX(text[-1]) & Sword)) goto continue_matching; goto fail; } case Cwordend: { if (text == textstart) goto fail; if (!(SYNTAX(text[-1]) & Sword)) goto fail; if (text == textend) goto continue_matching; if (!(SYNTAX(*text) & Sword)) goto continue_matching; goto fail; } case Cwordbound: { /* Note: as in gnu regexp, this also matches at the * beginning and end of buffer. */ if (text == textstart || text == textend) goto continue_matching; if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)) goto continue_matching; goto fail; } case Cnotwordbound: { /* Note: as in gnu regexp, this never matches at the * beginning and end of buffer. */ if (text == textstart || text == textend) goto fail; if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))) goto continue_matching; goto fail; } case Csyntaxspec: { NEXTCHAR(ch); if (!(SYNTAX(ch) & (unsigned char)*code++)) goto fail; goto continue_matching; } case Cnotsyntaxspec: { NEXTCHAR(ch); if (SYNTAX(ch) & (unsigned char)*code++) goto fail; goto continue_matching; } default: { FREE_STATE(state); PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?"); return -2; /*NOTREACHED*/ } } #if 0 /* This line is never reached --Guido */ abort(); #endif /* *NOTREACHED */ /* Using "break;" in the above switch statement is equivalent to "goto fail;" */ fail: POP_FAILURE(state, code, text, goto done_matching, goto error); goto continue_matching; done_matching: /* if(translated != NULL) */ /* free(translated); */ FREE_STATE(state); return -1; error: /* if (translated != NULL) */ /* free(translated); */ FREE_STATE(state); return -2; } #undef PREFETCH #undef NEXTCHAR int re_search(regexp_t bufp, unsigned char *string, int size, int pos, int range, regexp_registers_t regs) { unsigned char *fastmap; unsigned char *translate; unsigned char *text; unsigned char *partstart; unsigned char *partend; int dir; int ret; unsigned char anchor; assert(size >= 0 && pos >= 0); assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */ fastmap = bufp->fastmap; translate = bufp->translate; if (fastmap && !bufp->fastmap_accurate) { re_compile_fastmap(bufp); if (PyErr_Occurred()) return -2; } anchor = bufp->anchor; if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */ fastmap = NULL; if (range < 0) { dir = -1; range = -range; } else dir = 1; if (anchor == 2) { if (pos != 0) return -1; else range = 0; } for (; range >= 0; range--, pos += dir) { if (fastmap) { if (dir == 1) { /* searching forwards */ text = string + pos; partend = string + size; partstart = text; if (translate) while (text != partend && !fastmap[(unsigned char) translate[(unsigned char)*text]]) text++; else while (text != partend && !fastmap[(unsigned char)*text]) text++; pos += text - partstart; range -= text - partstart; if (pos == size && bufp->can_be_null == 0) return -1; } else { /* searching backwards */ text = string + pos; partstart = string + pos - range; partend = text; if (translate) while (text != partstart && !fastmap[(unsigned char) translate[(unsigned char)*text]]) text--; else while (text != partstart && !fastmap[(unsigned char)*text]) text--; pos -= partend - text; range -= partend - text; } } if (anchor == 1) { /* anchored to begline */ if (pos > 0 && (string[pos - 1] != '\n')) continue; } assert(pos >= 0 && pos <= size); ret = re_match(bufp, string, size, pos, regs); if (ret >= 0) return pos; if (ret == -2) return -2; } return -1; } /* ** Local Variables: ** mode: c ** c-file-style: "python" ** End: */