From: Pekka Riikonen Date: Wed, 2 Jan 2008 20:39:42 +0000 (+0000) Subject: Imported new improved free regex implementation. Added (again) X-Git-Tag: 1.2.beta1~38 X-Git-Url: http://git.silcnet.org/gitweb/?p=crypto.git;a=commitdiff_plain;h=72c29fbfbf198651c1125ac3d991df7a0cdf8acd Imported new improved free regex implementation. Added (again) support for SILC_REGEX_NOTBOL and SILC_REGEX_NOTEOLF flags. Added also support for POSIX bounded repeat expression (a{n,m}) to make it more POSIX compliant. Added SilcStack support to the regex too. --- diff --git a/lib/silcutil/silcerrno.c b/lib/silcutil/silcerrno.c index fae62b50..ff809c5f 100644 --- a/lib/silcutil/silcerrno.c +++ b/lib/silcutil/silcerrno.c @@ -4,7 +4,7 @@ Author: Pekka Riikonen - Copyright (C) 2007 Pekka Riikonen + Copyright (C) 2007 - 2008 Pekka Riikonen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -432,6 +432,8 @@ const char *silc_errno_strings[] = "Bad match register number", "Badly placed special character", "Regular expression too complex", + "Bad regular expression opcode", + "Bad repeat value", }; /* Map error to string */ diff --git a/lib/silcutil/silcerrno.h b/lib/silcutil/silcerrno.h index c13749ac..f8e8f15f 100644 --- a/lib/silcutil/silcerrno.h +++ b/lib/silcutil/silcerrno.h @@ -4,7 +4,7 @@ Author: Pekka Riikonen - Copyright (C) 2007 Pekka Riikonen + Copyright (C) 2007 - 2008 Pekka Riikonen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -132,6 +132,8 @@ typedef enum { SILC_ERR_REGEX_REG = 102, /* Bad register number */ SILC_ERR_REGEX_SPECIAL = 103, /* Unmatched special character */ SILC_ERR_REGEX_TOO_COMPLEX = 104, /* Too complex expression */ + SILC_ERR_REGEX_OPCODE = 105, /* Bad regex opcode */ + SILC_ERR_REGEX_REPEAT = 106, /* Bad repeat value */ SILC_ERR_MAX, } SilcResult; diff --git a/lib/silcutil/silcregex.c b/lib/silcutil/silcregex.c index 1412f20d..cdd6ecfa 100644 --- a/lib/silcutil/silcregex.c +++ b/lib/silcutil/silcregex.c @@ -1,41 +1,42 @@ -/* - - 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 is hereby granted without fee, provided that the - above copyright notice appears in all source code copies, the name of - Tatu Ylonen is not used to advertise products containing this software - or a derivation thereof, and all modified versions are clearly marked - as such. - - This software is provided "as is" without express or implied warranty. - - Created: Thu Sep 26 17:14:05 1991 ylo - Last modified: Sun Mar 29 16:47:31 1992 ylo - - 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. +/* 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. + * + * 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. + * + */ +/* The SILC Regex API and modifications by Pekka Riikonen, under the same - license as the original code. + license as the original code. We've added following features: + - RE_NOTBOL - bol fails to match (conforming POSIX) + - RE_NOTEOL - eol fails to match (conforming POSIX) + - RE_REPEAT a{n,m} - bounded repeat (conforming POSIX) + - SilStack support - compile without real memory allocations */ #include "silc.h" -/* Modified for use in SILC Runtime Toolkit. I think we have disabled many - features we could use, for the sake of simple API, which we may want to - extend later. But, we've added RE_NOTBOL and RE_NOTEOL. */ - #define RE_NREGS 128 /* number of registers available */ /* bit definitions for syntax */ @@ -49,6 +50,8 @@ #define RE_NO_GNU_EXTENSIONS 128 /* no gnu extensions */ #define RE_NOTBOL 256 /* bol fails to match */ #define RE_NOTEOL 512 /* eol fails to match */ +#define RE_REPEAT 1024 /* bounded repeat, must be quoted without + RE_NO_BK_VBAR */ /* definitions for some common regexp styles */ #define RE_SYNTAX_AWK (RE_NO_BK_PARENS|RE_NO_BK_VBAR|RE_CONTEXT_INDEP_OPS) @@ -56,62 +59,359 @@ #define RE_SYNTAX_GREP (RE_BK_PLUS_QM|RE_NEWLINE_OR) #define RE_SYNTAX_EMACS 0 +#define Sword 1 +#define Swhitespace 2 +#define Sdigit 4 +#define Soctaldigit 8 +#define Shexdigit 16 + /* Registers */ typedef struct re_registers { int start[RE_NREGS]; /* start offset of region */ int end[RE_NREGS]; /* end offset of region */ } *regexp_registers_t; -int re_set_syntax(int syntax); -/* This sets the syntax to use and returns the previous syntax. The - syntax is specified by a bit mask of the above defined bits. */ - -SilcResult re_compile_pattern(char *regex, int regex_size, SilcRegex compiled); -/* This compiles the regexp (given in regex and length in regex_size). - This returns NULL if the regexp compiled successfully, and an error - message if an error was encountered. The buffer field must be - initialized to a memory area allocated by malloc (or to NULL) before - use, and the allocated field must be set to its length (or 0 if buffer is - NULL). Also, the translate field must be set to point to a valid - translation table, or NULL if it is not used. */ - -int re_match(SilcRegex compiled, char *string, int size, int pos, - regexp_registers_t regs, unsigned int flags); -/* This tries to match the regexp against the string. This returns the - length of the matched portion, or -1 if the pattern could not be - matched and -2 if an error (such as failure stack overflow) is - encountered. */ - -int re_match_2(SilcRegex compiled, char *string1, int size1, - char *string2, int size2, int pos, regexp_registers_t regs, - int mstop, unsigned int flags); -/* This tries to match the regexp to the concatenation of string1 and - string2. This returns the length of the matched portion, or -1 if the - pattern could not be matched and -2 if an error (such as failure stack - overflow) is encountered. */ - -int re_search(SilcRegex compiled, char *string, int size, int startpos, - int range, regexp_registers_t regs, unsigned int flags); -/* This rearches for a substring matching the regexp. This returns the first - index at which a match is found. range specifies at how many positions to - try matching; positive values indicate searching forwards, and negative - values indicate searching backwards. mstop specifies the offset beyond - which a match must not go. This returns -1 if no match is found, and - -2 if an error (such as failure stack overflow) is encountered. */ - -int re_search_2(SilcRegex compiled, char *string1, int size1, - char *string2, int size2, int startpos, int range, - regexp_registers_t regs, int mstop, unsigned int flags); -/* This is like re_search, but search from the concatenation of string1 and - string2. */ - -void re_compile_fastmap(SilcRegex compiled); -/* This computes the fastmap for the regexp. For this to have any effect, - the calling program must have initialized the fastmap field to point - to an array of 256 characters. */ - -#define MACRO_BEGIN do { -#define MACRO_END } while (0) +/* 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; \ + silc_sfree(bufp->rstack, 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 *)silc_smalloc(bufp->rstack, 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 */ { @@ -135,11 +435,9 @@ enum regexp_compiled_ops /* opcodes for compiled regexp */ Cwordend, /* match at end of word */ Cwordbound, /* match if at word boundary */ Cnotwordbound, /* match if not at word boundary */ -#ifdef emacs - Cemacs_at_dot, /* emacs only: matches at dot */ -#endif /* emacs */ Csyntaxspec, /* matches syntax code (1 byte follows) */ - Cnotsyntaxspec /* matches if syntax code does not match (1 byte foll)*/ + Cnotsyntaxspec, /* matches if syntax code does not match (1 byte foll)*/ + Crepeat1, }; enum regexp_syntax_op /* syntax codes for plain and quoted characters */ @@ -168,12 +466,8 @@ enum regexp_syntax_op /* syntax codes for plain and quoted characters */ Rwordend, /* end of word */ Rwordbound, /* word bound */ Rnotwordbound, /* not word bound */ -#ifdef emacs - Remacs_at_dot, /* emacs: at dot */ - Remacs_syntaxspec, /* syntaxspec */ - Remacs_notsyntaxspec, /* notsyntaxspec */ -#endif /* emacs */ - Rnum_ops + Rnum_ops, + Ropenrep, /* opening bounded repeat */ }; static int re_compile_initialized = 0; @@ -187,37 +481,14 @@ static int regexp_ansi_sequences; #define NUM_LEVELS 5 /* number of precedence levels in use */ #define MAX_NESTING 100 /* max nesting level of operators */ -#ifdef emacs - -/* This code is for emacs compatibility only. */ - -#include "config.h" -#include "lisp.h" -#include "buffer.h" -#include "syntax.h" - -/* emacs defines NULL in some strange way? */ -#undef NULL -#define NULL 0 - -#else /* emacs */ - #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)] -#define Sword 1 -#ifdef SYNTAX_TABLE -char *re_syntax_table; -#else -static char re_syntax_table[256]; -#endif /* SYNTAX_TABLE */ +unsigned char re_syntax_table[256]; -#endif /* emacs */ - -static void re_compile_initialize() +void re_compile_initialize(void) { int a; -#if !defined(emacs) && !defined(SYNTAX_TABLE) static int syntax_table_inited = 0; if (!syntax_table_inited) @@ -229,9 +500,18 @@ static void re_compile_initialize() for (a = 'A'; a <= 'Z'; a++) re_syntax_table[a] = Sword; for (a = '0'; a <= '9'; a++) - re_syntax_table[a] = Sword; + 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; } -#endif /* !emacs && !SYNTAX_TABLE */ re_compile_initialized = 1; for (a = 0; a < 256; a++) { @@ -274,11 +554,6 @@ static void re_compile_initialize() regexp_plain_ops['.'] = Ranychar; if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS)) { -#ifdef emacs - regexp_quoted_ops['='] = Remacs_at_dot; - regexp_quoted_ops['s'] = Remacs_syntaxspec; - regexp_quoted_ops['S'] = Remacs_notsyntaxspec; -#endif /* emacs */ regexp_quoted_ops['w'] = Rwordchar; regexp_quoted_ops['W'] = Rnotwordchar; regexp_quoted_ops['<'] = Rwordbeg; @@ -304,14 +579,24 @@ static void re_compile_initialize() regexp_precedences[Rbol] = 3; regexp_precedences[Reol] = 3; } + if (regexp_syntax & RE_REPEAT) + { + if (regexp_syntax & RE_NO_BK_PARENS) + { + regexp_plain_ops['{'] = Ropenrep; + } + else + { + regexp_quoted_ops['{'] = Ropenrep; + } + } 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(syntax) -int syntax; +int re_set_syntax(int syntax) { int ret; @@ -321,8 +606,7 @@ int syntax; return ret; } -static int hex_char_to_decimal(ch) -int ch; +static int hex_char_to_decimal(int ch) { if (ch >= '0' && ch <= '9') return ch - '0'; @@ -333,186 +617,647 @@ int ch; return 16; } -SilcResult re_compile_pattern(regex, size, bufp) -char *regex; -int size; -SilcRegex bufp; +static int re_compile_fastmap_aux(unsigned char *code, int pos, + unsigned char *visited, + unsigned char *can_be_null, + unsigned char *fastmap) { - int a, pos, op, current_level, level, opcode; - int pattern_offset = 0, alloc; - int starts[NUM_LEVELS * MAX_NESTING], starts_base; - int future_jumps[MAX_NESTING], num_jumps; - unsigned char ch = 0; - char *pattern, *translate; - int next_register, paren_depth, num_open_registers, open_registers[RE_NREGS]; - int beginning_context; - -#define NEXTCHAR(var) \ - MACRO_BEGIN \ - if (pos >= size) \ - goto ends_prematurely; \ - (var) = regex[pos]; \ - pos++; \ - MACRO_END - -#define ALLOC(amount) \ - MACRO_BEGIN \ - if (pattern_offset+(amount) > alloc) \ - { \ - alloc += 256 + (amount); \ - pattern = silc_realloc(pattern, alloc); \ - if (!pattern) \ - goto out_of_memory; \ - } \ - MACRO_END - -#define STORE(ch) pattern[pattern_offset++] = (ch) + int a; + int b; + int syntaxcode; -#define CURRENT_LEVEL_START (starts[starts_base + current_level]) + if (visited[pos]) + return 0; /* we have already been here */ + visited[pos] = 1; + for (;;) + switch (code[pos++]) { + case Cend: + { + *can_be_null = 1; + return 0; + } + 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 0; + } + case Cnotsyntaxspec: + { + syntaxcode = code[pos++]; + for (a = 0; a < 256; a++) + if (!(SYNTAX(a) & syntaxcode) ) + fastmap[a] = 1; + return 0; + } + case Ceol: + { + fastmap['\n'] = 1; + if (*can_be_null == 0) + *can_be_null = 2; /* can match null, but only at end of buffer*/ + return 0; + } + 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 0; + } + case Cexact: + { + fastmap[(unsigned char)code[pos]] = 1; + return 0; + } + case Canychar: + { + for (a = 0; a < 256; a++) + if (a != '\n') + fastmap[a] = 1; + return 0; + } + 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 0; + } + 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 0; + } + visited[pos] = 1; + break; + } + case Cfailure_jump: + { + a = (unsigned char)code[pos++]; + a |= (unsigned char)code[pos++] << 8; + a = pos + (int)SHORT(a); + return re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap); + } + case Crepeat1: + { + pos += 2; + break; + } + default: + { + silc_set_errno(SILC_ERR_REGEX_OPCODE); + return -1; + /*NOTREACHED*/ + } + } +} -#define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset +static int re_do_compile_fastmap(unsigned char *buffer, int used, int pos, + unsigned char *can_be_null, + unsigned char *fastmap, SilcRegex bufp) +{ + unsigned char small_visited[512], *visited; + int ret; -#define PUSH_LEVEL_STARTS if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \ - starts_base += NUM_LEVELS; \ - else \ - goto too_complex + if (used <= sizeof(small_visited)) + visited = small_visited; + else + { + silc_stack_push(bufp->rstack, NULL); + visited = silc_smalloc(bufp->rstack, used); + if (!visited) { + silc_stack_pop(bufp->rstack); + return 0; + } + } + *can_be_null = 0; + memset(fastmap, 0, 256); + memset(visited, 0, used); + ret = re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap); + if (visited != small_visited) { + silc_sfree(bufp->rstack, visited); + silc_stack_pop(bufp->rstack); + } + return ret == 0; +} -#define POP_LEVEL_STARTS starts_base -= NUM_LEVELS +int re_compile_fastmap(SilcRegex bufp) +{ + if (!bufp->fastmap || bufp->fastmap_accurate) + return 0; + SILC_ASSERT(bufp->used > 0); + if (!re_do_compile_fastmap(bufp->buffer, + bufp->used, + 0, + &bufp->can_be_null, + bufp->fastmap, bufp)) + return -1; + 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; + return 0; +} -#define PUT_ADDR(offset,addr) \ - MACRO_BEGIN \ - int disp = (addr) - (offset) - 2; \ - pattern[(offset)] = disp & 0xff; \ - pattern[(offset)+1] = (disp>>8) & 0xff; \ - MACRO_END - -#define INSERT_JUMP(pos,type,addr) \ - MACRO_BEGIN \ - 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; \ - MACRO_END +/* + * 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(SilcRegex 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; -#define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7)) + a = (unsigned char)*code++; + a |= (unsigned char)*code++ << 8; + a = (int)SHORT(a); -#define SET_FIELDS \ - MACRO_BEGIN \ - bufp->allocated = alloc; \ - bufp->buffer = pattern; \ - bufp->used = pattern_offset; \ - MACRO_END - -#define GETHEX(var) \ - MACRO_BEGIN \ - 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; \ - MACRO_END - -#define ANSI_TRANSLATE(ch) \ - MACRO_BEGIN \ - 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; \ - } \ - MACRO_END + p1 = code + a + 3; /* skip the failure_jump */ + /* Check that the jump is within the pattern */ + if (p1buffer || bufp->buffer+bufp->usedused = 0; - bufp->fastmap_accurate = 0; - bufp->uses_registers = 0; - translate = bufp->translate; - pattern = bufp->buffer; - alloc = bufp->allocated; - if (alloc == 0 || pattern == NULL) + SILC_ASSERT(p1[-3] == Cfailure_jump); + p2 = code; + /* p1 points inside loop, p2 points to after loop */ + if (!re_do_compile_fastmap(bufp->buffer, bufp->used, + (int)(p2 - bufp->buffer), + &can_be_null, map, bufp)) + 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++) { - alloc = 256; - pattern = silc_malloc(alloc); - if (!pattern) - goto out_of_memory; + 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; + } } - 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) + /* now we know that we can't backtrack. */ + while (p1 != p2 - 3) { - 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) + 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; + SILC_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(SilcRegex 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) \ + { \ + pattern = silc_srealloc(bufp->rstack, alloc, pattern, \ + alloc + 256 + (amount)); \ + alloc += 256 + (amount); \ + 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; \ + } \ + } \ + } + +SilcResult re_compile_pattern(unsigned char *regex, int size, SilcRegex 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 = silc_smalloc(bufp->rstack, 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; @@ -523,158 +1268,191 @@ SilcRegex bufp; { current_level = level; for (;num_jumps > 0 && - future_jumps[num_jumps-1] >= CURRENT_LEVEL_START; + future_jumps[num_jumps-1] >= CURRENT_LEVEL_START; num_jumps--) PUT_ADDR(future_jumps[num_jumps-1], pattern_offset); } switch (op) { case Rend: - break; + { + 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; + { + 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; + { + opcode = Canychar; + store_opcode: + SET_LEVEL_START; + ALLOC(1); + STORE(opcode); + break; + } case Rquote: - abort(); - /*NOTREACHED*/ + { + SILC_VERIFY(op != Rquote); + /*NOTREACHED*/ + } case Rbol: - if (!beginning_context) { - if (regexp_context_indep_ops) - goto op_error; - else - goto normal_char; + { + if (!beginning_context) { + if (regexp_context_indep_ops) + goto op_error; + else + goto normal_char; + } + opcode = Cbol; + goto store_opcode; } - 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; + { + 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; } - opcode = Ceol; - goto store_opcode; - break; case Roptional: - if (beginning_context) { - if (regexp_context_indep_ops) - goto op_error; - else - goto normal_char; + { + 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; } - 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; + { + store_jump: + 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; } - 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; + { + 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; - next_register++; - } - paren_depth++; - PUSH_LEVEL_STARTS; - current_level = 0; - SET_LEVEL_START; - break; + { + 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; + { + 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; + { + if (ch == '0') + goto bad_match_register; + SILC_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; + { + 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,prev,offset,range,firstchar; + int complement; + int prev; + int offset; + int range; + int firstchar; SET_LEVEL_START; ALLOC(1+256/8); @@ -707,7 +1485,7 @@ SilcRegex bufp; } if (range) { - for (a = prev; a <= ch; a++) + for (a = prev; a <= (int)ch; a++) SETBIT(pattern, offset, a); prev = -1; range = 0; @@ -733,62 +1511,195 @@ SilcRegex bufp; } break; } + case Ropenrep: + { + /* The bounded repeat syntax: a{n}, a{n,} and a{n,m}. The first + is compiled as n-1 Rnormals. The second is compiled as n-1 + Rnormals and one Rplus. The third is compiled as n-1 Rnormals + and m-n Rnormals with Roptionals. 0 values have special + compilation. */ + int min, max, i; + + if (pos >= size) + goto op_error; + + /* Get the preceding atom */ + if (pos < 2) + goto op_error; + pos -= 2; + NEXTCHAR(a); + NEXTCHAR(ch); + + /* Get min value */ + NEXTCHAR(ch); + if (!isdigit(ch)) + goto repeat_value_error; + min = ch - '0'; + NEXTCHAR(ch); + while (isdigit(ch)) { + min *= 10; + min += ch - '0'; + NEXTCHAR(ch); + } + + if (min > 255) + goto repeat_value_error; + + if (ch == '}') { + /* The a{n} case */ + + if (!min) { + /* Will not do any matching with a{0} */ + pattern_offset -= 2; + break; + } + + /* Store min - 1 many Cexacts. */ + for (i = 0; i < min - 1; i++) { + SET_LEVEL_START; + ALLOC(2); + STORE(Cexact); + STORE((unsigned char)a); + } + break; + } + + if (ch == ',') { + NEXTCHAR(ch); + + if (ch == '}') { + /* The a{n,} case */ + + if (!min) { + /* Store Rstar with a{0,} */ + op = Rstar; + goto store_jump; + } + + /* Store min - 1 many Cexacts. */ + for (i = 0; i < min - 1; i++) { + SET_LEVEL_START; + ALLOC(2); + STORE(Cexact); + STORE((unsigned char)a); + } + + /* Store Rplus */ + op = Rplus; + goto store_jump; + } + + /* The a{n,m} case */ + + /* Get max value */ + if (!isdigit(ch)) + goto repeat_value_error; + max = ch - '0'; + NEXTCHAR(ch); + while (isdigit(ch)) { + max *= 10; + max += ch - '0'; + NEXTCHAR(ch); + } + + if (max > 255) + goto repeat_value_error; + if (min > max) + goto repeat_value_error; + + if (!min && !max) { + /* Will not do any matching with a{0,0} */ + pattern_offset -= 2; + break; + } + + if (ch != '}') + goto op_error; + + if (!min) + /* Only optional matching with a{0,m}. */ + pattern_offset -= 2; + + /* Store min - 1 many Cexacts. */ + for (i = 0; min && i < min - 1; i++) { + SET_LEVEL_START; + ALLOC(2); + STORE(Cexact); + STORE((unsigned char)a); + } + + /* Store max - min Cexacts and Roptionals. */ + for (i = 0; i < max - min; i++) { + SET_LEVEL_START; + ALLOC(2); + STORE(Cexact); + STORE((unsigned char)a); + ALLOC(3); + INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, + pattern_offset + 3); + } + break; + } + + goto op_error; + } case Rbegbuf: - opcode = Cbegbuf; - goto store_opcode; + { + opcode = Cbegbuf; + goto store_opcode; + } case Rendbuf: - opcode = Cendbuf; - goto store_opcode; + { + opcode = Cendbuf; + goto store_opcode; + } case Rwordchar: - opcode = Csyntaxspec; - ch = Sword; - goto store_opcode_and_arg; + { + opcode = Csyntaxspec; + ch = Sword; + goto store_opcode_and_arg; + } case Rnotwordchar: - opcode = Cnotsyntaxspec; - ch = Sword; - goto store_opcode_and_arg; + { + opcode = Cnotsyntaxspec; + ch = Sword; + goto store_opcode_and_arg; + } case Rwordbeg: - opcode = Cwordbeg; - goto store_opcode; + { + opcode = Cwordbeg; + goto store_opcode; + } case Rwordend: - opcode = Cwordend; - goto store_opcode; + { + opcode = Cwordend; + goto store_opcode; + } case Rwordbound: - opcode = Cwordbound; - goto store_opcode; + { + opcode = Cwordbound; + goto store_opcode; + } case Rnotwordbound: - opcode = Cnotwordbound; - goto store_opcode; -#ifdef emacs - case Remacs_at_dot: - opcode = Cemacs_at_dot; - goto store_opcode; - case Remacs_syntaxspec: - NEXTCHAR(ch); - if (translate) - ch = translate[(unsigned char)ch]; - opcode = Csyntaxspec; - ch = syntax_spec_code[(unsigned char)ch]; - goto store_opcode_and_arg; - case Remacs_notsyntaxspec: - NEXTCHAR(ch); - if (translate) - ch = translate[(unsigned char)ch]; - opcode = Cnotsyntaxspec; - ch = syntax_spec_code[(unsigned char)ch]; - goto store_opcode_and_arg; -#endif /* emacs */ + { + opcode = Cnotwordbound; + goto store_opcode; + } default: - abort(); + { + abort(); + } } beginning_context = (op == Ropenpar || op == Ror); } if (starts_base != 0) goto parenthesis_error; - assert(num_jumps == 0); + SILC_ASSERT(num_jumps == 0); ALLOC(1); STORE(Cend); SET_FIELDS; + if (!re_optimize(bufp)) + return SILC_ERR; return SILC_OK; op_error: @@ -818,667 +1729,484 @@ SilcRegex bufp; too_complex: SET_FIELDS; return SILC_ERR_REGEX_TOO_COMPLEX; + + repeat_value_error: + SET_FIELDS; + return SILC_ERR_REGEX_REPEAT; } + #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 - -static void re_compile_fastmap_aux(code, pos, visited, can_be_null, fastmap) -char *code, *visited, *can_be_null, *fastmap; -int pos; -{ - int a, b, 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: -#ifdef emacs - case Cemacs_at_dot: -#endif /* emacs */ - 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; - default: - abort(); /* probably some opcode is missing from this switch */ - /*NOTREACHED*/ - } -} - -static int re_do_compile_fastmap(buffer, used, pos, can_be_null, fastmap) -char *buffer, *fastmap, *can_be_null; -int used, pos; -{ - char small_visited[512], *visited; - - if (used <= sizeof(small_visited)) - visited = small_visited; - else - { - visited = silc_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) - silc_free(visited); - return 1; -} - -void re_compile_fastmap(bufp) -SilcRegex 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 (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; -} - -#define INITIAL_FAILURES 128 /* initial # failure points to allocate */ -#define MAX_FAILURES 4100 /* max # of failure points before failing */ +#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 -int re_match_2(bufp, string1, size1, string2, size2, pos, regs, mstop, flags) -SilcRegex bufp; -char *string1, *string2; -int size1, size2, pos, mstop; -regexp_registers_t regs; -unsigned int flags; -{ - struct failure_point { char *text, *partend, *code; } - *failure_stack_start, *failure_sp, *failure_stack_end, - initial_failure_stack[INITIAL_FAILURES]; - char *code, *translate, *text, *textend, *partend, *part_2_end; - char *regstart_text[RE_NREGS], *regstart_partend[RE_NREGS]; - char *regend_text[RE_NREGS], *regend_partend[RE_NREGS]; - int a, b, ch, reg, regch, match_end; - char *regtext, *regpartend, *regtextend; - -#define PREFETCH \ - MACRO_BEGIN \ - if (text == partend) \ - { \ - if (text == textend) \ - goto fail; \ - text = string2; \ - partend = part_2_end; \ - } \ - MACRO_END +#define PREFETCH if (text == textend) goto fail #define NEXTCHAR(var) \ - MACRO_BEGIN \ - PREFETCH; \ - (var) = (unsigned char)*text++; \ - if (translate) \ - (var) = (unsigned char)translate[(var)]; \ - MACRO_END - - assert(pos >= 0 && size1 >= 0 && size2 >= 0 && mstop >= 0); - assert(mstop <= size1 + size2); - assert(pos <= mstop); - - if (pos <= size1) - { - text = string1 + pos; - if (mstop <= size1) - { - partend = string1 + mstop; - textend = partend; - } - else - { - partend = string1 + size1; - textend = string2 + mstop - size1; - } - part_2_end = string2 + mstop - size1; - } - else - { - text = string2 + pos - size1; - partend = string2 + mstop - size1; - textend = partend; - part_2_end = partend; - } + PREFETCH; \ + var = (unsigned char)*text++; \ + if (translate) \ + var = translate[var] - if (bufp->uses_registers && regs != NULL) - for (a = 0; a < RE_NREGS; a++) - regend_text[a] = NULL; +int re_match(SilcRegex bufp, unsigned char *string, int size, int pos, + regexp_registers_t old_regs, unsigned int flags) +{ + 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; + + SILC_ASSERT(pos >= 0 && size >= 0); + SILC_ASSERT(pos <= size); + + text = string + pos; + textstart = string; + textend = string + size; code = bufp->buffer; + translate = bufp->translate; - failure_stack_start = failure_sp = initial_failure_stack; - failure_stack_end = initial_failure_stack + INITIAL_FAILURES; - -#if 0 - /* re_search_2 has already done this, and otherwise we get little benefit - from this. So I'll leave this out. */ - if (bufp->fastmap_accurate && !bufp->can_be_null && - text != textend && - !bufp->fastmap[translate ? - (unsigned char)translate[(unsigned char)*text] : - (unsigned char)*text]) - return -1; /* it can't possibly match */ -#endif + + NEW_STATE(state, bufp->num_registers); continue_matching: - for (;;) + switch (*code++) { - switch (*code++) - { - case Cend: - if (partend != part_2_end) - match_end = text - string1; - else - match_end = text - string2 + size1; - if (regs) + 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') { + if (flags & RE_NOTBOL) + goto fail; + goto continue_matching; + } + goto fail; + } + case Ceol: + { + if (text == textend || *text == '\n') { + if (flags & RE_NOTEOL) + goto fail; + 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) { + silc_set_errno(SILC_ERR_OVERFLOW); + FREE_STATE(state); + return -2; + } + PUSH_FAILURE(state, failuredest, NULL, goto error); + code += a; + if (codebuffer || bufp->buffer+bufp->used < code) { + silc_set_errno(SILC_ERR_OVERFLOW); + 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) { + silc_set_errno(SILC_ERR_OVERFLOW); + 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->usedstart[0] = pos; - regs->end[0] = match_end; - if (!bufp->uses_registers) + if (translate) { - for (a = 1; a < RE_NREGS; a++) + while (text < textend) { - regs->start[a] = -1; - regs->end[a] = -1; + ch = translate[(unsigned char)*text]; + if (pinst[ch/8] & (1<<(ch & 7))) + text++; + else + break; } } else { - for (a = 1; a < RE_NREGS; a++) + while (text < textend) { - if (regend_text[a] == NULL) - { - regs->start[a] = -1; - regs->end[a] = -1; - continue; - } - if (regstart_partend[a] != part_2_end) - regs->start[a] = regstart_text[a] - string1; + ch = (unsigned char)*text; + if (pinst[ch/8] & (1<<(ch & 7))) + text++; else - regs->start[a] = regstart_text[a] - string2 + size1; - if (regend_partend[a] != part_2_end) - regs->end[a] = regend_text[a] - string1; - else - regs->end[a] = regend_text[a] - string2 + size1; + break; } } + break; } - if (failure_stack_start != initial_failure_stack) - silc_free((char *)failure_stack_start); - return match_end - pos; - case Cbol: - if (text == string1 || text[-1] == '\n') { /* text[-1] always valid */ - if (flags & RE_NOTBOL) - goto fail; - break; - } - goto fail; - case Ceol: - if (text == string2 + size2 || - (text == string1 + size1 ? - (size2 == 0 || *string2 == '\n') : - *text == '\n')) { - if (flags & RE_NOTEOL) - goto fail; - break; - } - goto fail; - case Cset: - NEXTCHAR(ch); - if (code[ch/8] & (1<<(ch & 7))) + case Cexact: { - code += 256/8; + ch = (unsigned char)*pinst; + if (translate) + { + while (text < textend && + translate[(unsigned char)*text] == ch) + text++; + } + else + { + while (text < textend && (unsigned char)*text == ch) + text++; + } break; } - goto fail; - case Cexact: - NEXTCHAR(ch); - if (ch != (unsigned char)*code++) - goto fail; - break; - case Canychar: - NEXTCHAR(ch); - if (ch == '\n') - goto fail; - break; - case Cstart_memory: - reg = *code++; - regstart_text[reg] = text; - regstart_partend[reg] = partend; - break; - case Cend_memory: - reg = *code++; - regend_text[reg] = text; - regend_partend[reg] = partend; - break; - case Cmatch_memory: - reg = *code++; - if (regend_text[reg] == NULL) - goto fail; /* or should we just match nothing? */ - regtext = regstart_text[reg]; - regtextend = regend_text[reg]; - if (regstart_partend[reg] == regend_partend[reg]) - regpartend = regtextend; - else - regpartend = string1 + size1; - - for (;regtext != regtextend;) + case Canychar: { - NEXTCHAR(ch); - if (regtext == regpartend) - regtext = string2; - regch = (unsigned char)*regtext++; - if (translate) - regch = (unsigned char)translate[regch]; - if (regch != ch) - goto fail; + while (text < textend && (unsigned char)*text != '\n') + text++; + break; } - break; - case Cstar_jump: - /* 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. */ - a = (unsigned char)*code++; - a |= (unsigned char)*code++ << 8; - a = (int)(short)a; - { - char map[256], can_be_null; - char *p1, *p2; - - p1 = code + a + 3; /* skip the failure_jump */ - assert(p1[-3] == Cfailure_jump); - p2 = code; - /* p1 points inside loop, p2 points to after loop */ - if (!re_do_compile_fastmap(bufp->buffer, bufp->used, - 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_p1: - /* loop until we find something that consumes a character */ - switch (*p1++) - { - case Cbol: - case Ceol: - case Cbegbuf: - case Cendbuf: - case Cwordbeg: - case Cwordend: - case Cwordbound: - case Cnotwordbound: -#ifdef emacs - case Cemacs_at_dot: -#endif /* emacs */ - goto loop_p1; - case Cstart_memory: - case Cend_memory: - p1++; - goto loop_p1; - case Cexact: - ch = (unsigned char)*p1++; - if (map[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) - { - switch (*p1++) - { - case Cend: - abort(); /* we certainly shouldn't get this inside loop */ - /*NOTREACHED*/ - case Cbol: - case Ceol: - case Canychar: - case Cbegbuf: - case Cendbuf: - case Cwordbeg: - case Cwordend: - case Cwordbound: - case Cnotwordbound: -#ifdef emacs - case Cemacs_at_dot: -#endif /* emacs */ - 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: - printf("regexpr.c: processing star_jump: unknown op %d\n", p1[-1]); - break; - } - } - goto make_update_jump; - } - make_normal_jump: - /* printf("changing to normal jump\n"); */ - code -= 3; - *code = Cjump; - break; - make_update_jump: - /* printf("changing to update jump\n"); */ - code -= 2; - a += 3; /* jump to after the Cfailure_jump */ - code[-1] = Cupdate_failure_jump; - code[0] = a & 0xff; - code[1] = a >> 8; - /* fall to next case */ - case Cupdate_failure_jump: - failure_sp[-1].text = text; - failure_sp[-1].partend = partend; - /* fall to next case */ - case Cjump: - a = (unsigned char)*code++; - a |= (unsigned char)*code++ << 8; - code += (int)(short)a; - break; - case Cdummy_failure_jump: - case Cfailure_jump: - if (failure_sp == failure_stack_end) + case Csyntaxspec: { - if (failure_stack_start != initial_failure_stack) - goto error; - failure_stack_start = (struct failure_point *) - silc_malloc(MAX_FAILURES * sizeof(*failure_stack_start)); - failure_stack_end = failure_stack_start + MAX_FAILURES; - memcpy((char *)failure_stack_start, (char *)initial_failure_stack, - INITIAL_FAILURES * sizeof(*failure_stack_start)); - failure_sp = failure_stack_start + INITIAL_FAILURES; + a = (unsigned char)*pinst; + if (translate) + { + while (text < textend && + (SYNTAX(translate[*text]) & a) ) + text++; + } + else + { + while (text < textend && (SYNTAX(*text) & a) ) + text++; + } + break; } - a = (unsigned char)*code++; - a |= (unsigned char)*code++ << 8; - a = (int)(short)a; - if (code[-3] == Cdummy_failure_jump) - { /* this is only used in plus */ - assert(*code == Cfailure_jump); - b = (unsigned char)code[1]; - b |= (unsigned char)code[2] << 8; - failure_sp->code = code + (int)(short)b + 3; - failure_sp->text = NULL; - code += a; + case Cnotsyntaxspec: + { + a = (unsigned char)*pinst; + if (translate) + { + while (text < textend && + !(SYNTAX(translate[*text]) & a) ) + text++; + } + else + { + while (text < textend && !(SYNTAX(*text) & a) ) + text++; + } + break; } - else + default: { - failure_sp->code = code + a; - failure_sp->text = text; - failure_sp->partend = partend; + FREE_STATE(state); + silc_set_errno(SILC_ERR_REGEX_OPCODE); + return -2; + /*NOTREACHED*/ } - failure_sp++; - break; - case Cbegbuf: - if (text == string1) - break; + } + /* due to the funky way + and * are compiled, the top + * failure- stack entry at this point is actually a + * success entry -- update it & pop it */ + UPDATE_FAILURE(state, text, goto error); + goto fail; /* i.e., succeed */ + } + 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; - case Cendbuf: - if (size2 == 0 ? text == string1 + size1 : text == string2 + size2) - break; + if (!(SYNTAX(*text) & Sword)) goto fail; - case Cwordbeg: - if (text == string2 + size2) - goto fail; - if (size2 == 0 && text == string1 + size1) - goto fail; - if (SYNTAX(text == string1 + size1 ? *string1 : *text) != Sword) - goto fail; - if (text == string1) - break; - if (SYNTAX(text[-1]) != Sword) - break; + if (text == textstart) + goto continue_matching; + if (!(SYNTAX(text[-1]) & Sword)) + goto continue_matching; + goto fail; + } + case Cwordend: + { + if (text == textstart) goto fail; - case Cwordend: - if (text == string1) - goto fail; - if (SYNTAX(text[-1]) != Sword) - goto fail; - if (text == string2 + size2) - break; - if (size2 == 0 && text == string1 + size1) - break; - if (SYNTAX(*text) == Sword) - goto fail; - break; - case Cwordbound: - /* Note: as in gnu regexp, this also matches at the beginning - and end of buffer. */ - if (text == string1 || text == string2 + size2 || - (size2 == 0 && text == string1 + size1)) - break; - if ((SYNTAX(text[-1]) == Sword) ^ - (SYNTAX(text == string1 + size1 ? *string2 : *text) == Sword)) - break; + if (!(SYNTAX(text[-1]) & Sword)) goto fail; - case Cnotwordbound: - /* Note: as in gnu regexp, this never matches at the beginning - and end of buffer. */ - if (text == string1 || text == string2 + size2 || - (size2 == 0 && text == string1 + size1)) - goto fail; - if (!((SYNTAX(text[-1]) == Sword) ^ - (SYNTAX(text == string1 + size1 ? *string2 : *text) == Sword))) - goto fail; - break; - case Csyntaxspec: - NEXTCHAR(ch); - if (SYNTAX(ch) != (unsigned char)*code++) - goto fail; - break; - case Cnotsyntaxspec: - NEXTCHAR(ch); - if (SYNTAX(ch) != (unsigned char)*code++) - break; + 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; -#ifdef emacs - case Cemacs_at_dot: - if (PTR_CHAR_POS((unsigned char *)text) + 1 != point) - goto fail; - break; -#endif /* emacs */ - default: - abort(); - /*NOTREACHED*/ - } + 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); + silc_set_errno(SILC_ERR_REGEX_OPCODE); + return -2; + /*NOTREACHED*/ + } } - abort(); - /*NOTREACHED*/ + /* Using "break;" in the above switch statement is equivalent to + "goto fail;" */ fail: - if (failure_sp != failure_stack_start) - { - failure_sp--; - text = failure_sp->text; - if (text == NULL) - goto fail; - partend = failure_sp->partend; - code = failure_sp->code; - goto continue_matching; - } - if (failure_stack_start != initial_failure_stack) - silc_free((char *)failure_stack_start); + 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 (failure_stack_start != initial_failure_stack) - silc_free((char *)failure_stack_start); + /* if (translated != NULL) */ + /* free(translated); */ + FREE_STATE(state); return -2; } #undef PREFETCH #undef NEXTCHAR -#undef PUSH_FAILURE - -int re_match(bufp, string, size, pos, regs, flags) -SilcRegex bufp; -char *string; -int size, pos; -regexp_registers_t regs; -unsigned int flags; -{ - return re_match_2(bufp, string, size, (char *)NULL, 0, pos, regs, size, - flags); -} -int re_search_2(bufp, string1, size1, string2, size2, pos, range, regs, - mstop, flags) -SilcRegex bufp; -char *string1, *string2; -int size1, size2, pos, range, mstop; -regexp_registers_t regs; -unsigned int flags; +int re_search(SilcRegex bufp, unsigned char *string, int size, int pos, + int range, regexp_registers_t regs, unsigned int flags) { - char *fastmap, *translate, *text, *partstart, *partend; - int dir, ret; - char anchor; + unsigned char *fastmap; + unsigned char *translate; + unsigned char *text; + unsigned char *partstart; + unsigned char *partend; + int dir; + int ret; + unsigned char anchor; - assert(size1 >= 0 && size2 >= 0 && pos >= 0 && mstop >= 0); - assert(pos + range >= 0 && pos + range <= size1 + size2); - assert(pos <= mstop); + SILC_ASSERT(size >= 0 && pos >= 0); + SILC_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 (fastmap && !bufp->fastmap_accurate) { + if (re_compile_fastmap(bufp)) + 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; @@ -1486,60 +2214,40 @@ unsigned int flags; } 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 */ - if (pos < size1) - { - text = string1 + pos; - if (pos + range > size1) - partend = string1 + size1; - else - partend = string1 + pos + range; - } - else - { - text = string2 + pos - size1; - partend = string2 + pos + range - size1; - } + + text = string + pos; + partend = string + size; partstart = text; if (translate) while (text != partend && - !fastmap[(unsigned char) - translate[(unsigned char)*text]]) + !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 == size1 + size2 && bufp->can_be_null == 0) + if (pos == size && bufp->can_be_null == 0) return -1; } else { /* searching backwards */ - if (pos <= size1) - { - text = string1 + pos; - partstart = string1 + pos - range; - } - else - { - text = string2 + pos - size1; - if (range < pos - size1) - partstart = string2 + pos - size1 - range; - else - partstart = string2; - } + text = string + pos; + partstart = string + pos - range; partend = text; if (translate) while (text != partstart && @@ -1556,14 +2264,11 @@ unsigned int flags; } if (anchor == 1) { /* anchored to begline */ - if (pos > 0 && - (pos <= size1 ? string1[pos - 1] : - string2[pos - size1 - 1]) != '\n') + if (pos > 0 && (string[pos - 1] != '\n')) continue; } - assert(pos >= 0 && pos <= size1 + size2); - ret = re_match_2(bufp, string1, size1, string2, size2, pos, regs, mstop, - flags); + SILC_ASSERT(pos >= 0 && pos <= size); + ret = re_match(bufp, string, size, pos, regs, flags); if (ret >= 0) return pos; if (ret == -2) @@ -1572,17 +2277,6 @@ unsigned int flags; return -1; } -int re_search(bufp, string, size, startpos, range, regs, flags) -SilcRegex bufp; -char *string; -int size, startpos, range; -regexp_registers_t regs; -unsigned int flags; -{ - return re_search_2(bufp, string, size, (char *)NULL, 0, - startpos, range, regs, size, flags); -} - /****************************** SILC Regex API ******************************/ /* Compile regular expression */ @@ -1600,8 +2294,14 @@ SilcBool silc_regex_compile(SilcRegex regexp, const char *regex, memset(regexp, 0, sizeof(*regexp)); + /* Get global stack, if set, and create child stack. */ + regexp->rstack = silc_stack_get_global(); + if (regexp->rstack) + regexp->rstack = silc_stack_alloc(512, regexp->rstack); + /* Set syntax */ - syntax |= (RE_CONTEXT_INDEP_OPS | RE_NO_BK_PARENS | RE_NO_BK_VBAR); + syntax |= (RE_CONTEXT_INDEP_OPS | RE_NO_BK_PARENS | + RE_NO_BK_VBAR | RE_REPEAT); re_set_syntax(syntax); /* Compile */ @@ -1646,9 +2346,7 @@ SilcBool silc_regex_match(SilcRegex regexp, const char *string, ret = re_search(regexp, (char *)string, string_len, 0, string_len, num_match ? ®s : NULL, f); if (ret < 0) { - if (ret == -2) - silc_set_errno(SILC_ERR); - else + if (ret == -1) silc_set_errno(SILC_ERR_NOT_FOUND); } @@ -1667,7 +2365,8 @@ SilcBool silc_regex_match(SilcRegex regexp, const char *string, void silc_regex_free(SilcRegex regexp) { - silc_free(regexp->buffer); + silc_sfree(regexp->rstack, regexp->buffer); + silc_stack_free(regexp->rstack); } /* Match string */ diff --git a/lib/silcutil/silcregex.h b/lib/silcutil/silcregex.h index 2adddb37..b44456f1 100644 --- a/lib/silcutil/silcregex.h +++ b/lib/silcutil/silcregex.h @@ -1,25 +1,19 @@ /* - regexpr.h + silcregex.h - Author: Tatu Ylonen + Author: Pekka Riikonen - Copyright (c) 1991 Tatu Ylonen, Espoo, Finland + Copyright (C) 2007 Pekka Riikonen - Permission to use, copy, modify, distribute, and sell this software - and its documentation is hereby granted without fee, provided that the - above copyright notice appears in all source code copies, the name of - Tatu Ylonen is not used to advertise products containing this software - or a derivation thereof, and all modified versions are clearly marked - as such. + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. - This software is provided "as is" without express or implied warranty. - - Created: Thu Sep 26 17:15:36 1991 ylo - Last modified: Fri Jan 3 12:05:45 1992 ylo - - The SILC Regex API by Pekka Riikonen, under the same license as the original - code. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. */ @@ -68,11 +62,13 @@ * ***/ typedef struct SilcRegexObject { - char *buffer; /* compiled pattern */ - int allocated; /* allocated size of compiled pattern */ - int used; /* actual length of compiled pattern */ + SilcStack rstack; /* Stack for fast allocations */ + unsigned char *buffer; /* compiled pattern */ char *fastmap; /* fastmap[ch] is true if ch can start pattern */ char *translate; /* translation to apply during comp/match */ + int allocated; /* allocated size of compiled pattern */ + int used; /* actual length of compiled pattern */ + int num_registers; /* number of registers used */ char fastmap_accurate; /* true if fastmap is valid */ char can_be_null; /* true if can match empty string */ char uses_registers; /* registers used and need to be initialized */ diff --git a/lib/silcutil/tests/test_silcregex.c b/lib/silcutil/tests/test_silcregex.c index 87b7a5f4..0e7f4527 100644 --- a/lib/silcutil/tests/test_silcregex.c +++ b/lib/silcutil/tests/test_silcregex.c @@ -9,6 +9,7 @@ int main(int argc, char **argv) SilcRegexMatchStruct match[10]; int i, num_match = 10; char *regex, *string, *sub; + SilcBufferStruct bmatch; if (argc > 1 && !strcmp(argv[1], "-d")) { silc_log_debug(TRUE); @@ -17,6 +18,181 @@ int main(int argc, char **argv) silc_log_set_debug_string("*regex*,*errno*"); } + regex = "^a{0}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = ""; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{0,}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "bbbb"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{0,}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaaaaaaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{0,0}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "a"; + SILC_LOG_DEBUG(("DO NOT Match %s", string)); + if (silc_regex(string, regex, &bmatch, NULL)) + goto err; + + regex = "^a{3}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{3}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaa"; + SILC_LOG_DEBUG(("DO NOT Match %s", string)); + if (silc_regex(string, regex, &bmatch, NULL)) + goto err; + + regex = "^a{3,5}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{3,5}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{3,5}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaaaa"; + SILC_LOG_DEBUG(("DO NOT Match %s", string)); + if (silc_regex(string, regex, &bmatch, NULL)) + goto err; + + regex = "^a{3,}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{3,}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaaaaaaaaaaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "^a{3,}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aa"; + SILC_LOG_DEBUG(("DO NOT Match %s", string)); + if (silc_regex(string, regex, &bmatch, NULL)) + goto err; + + + regex = "a*b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "b"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "a*b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "ab"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "a*b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaab"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + + regex = "a+b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "ab"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "a+b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaaab"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "a+b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "b"; + SILC_LOG_DEBUG(("DO NOT Match %s", string)); + if (silc_regex(string, regex, &bmatch, NULL)) + goto err; + + + regex = "ca?b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "cb"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "ca?b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "cab"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_buffer_printf(&bmatch, TRUE); + + regex = "ca?b"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "caab"; + SILC_LOG_DEBUG(("DO NOT Match %s", string)); + if (silc_regex(string, regex, &bmatch, NULL)) + goto err; + + + regex = "^a{2,3}$"; + SILC_LOG_DEBUG(("Regex %s", regex)); + string = "aaa"; + SILC_LOG_DEBUG(("Match %s", string)); + if (!silc_regex(string, regex, &bmatch, NULL)) + goto err; + silc_file_write(1, silc_buffer_data(&bmatch), silc_buffer_len(&bmatch)); + fflush(stdout); + regex = "(H..).(o..)"; SILC_LOG_DEBUG(("Regex %s", regex)); if (!silc_regex_compile(®, regex, 0))