Index: head/usr.bin/grep/Makefile =================================================================== --- head/usr.bin/grep/Makefile (revision 316491) +++ head/usr.bin/grep/Makefile (revision 316492) @@ -1,95 +1,95 @@ # $NetBSD: Makefile,v 1.4 2011/02/16 01:31:33 joerg Exp $ # $FreeBSD$ # $OpenBSD: Makefile,v 1.6 2003/06/25 15:00:04 millert Exp $ .include .if ${MK_BSD_GREP} == "yes" PROG= grep .else PROG= bsdgrep CLEANFILES+= bsdgrep.1 bsdgrep.1: grep.1 ${CP} ${.ALLSRC} ${.TARGET} .endif SRCS= file.c grep.c queue.c util.c # Extra files ported backported form some regex improvements .PATH: ${.CURDIR}/regex -SRCS+= fastmatch.c hashtable.c tre-compile.c tre-fastmatch.c xmalloc.c +SRCS+= fastmatch.c hashtable.c tre-compile.c tre-fastmatch.c CFLAGS+=-I${.CURDIR}/regex CFLAGS.gcc+= --param max-inline-insns-single=500 .if ${MK_BSD_GREP} == "yes" LINKS= ${BINDIR}/grep ${BINDIR}/egrep \ ${BINDIR}/grep ${BINDIR}/fgrep \ ${BINDIR}/grep ${BINDIR}/rgrep \ ${BINDIR}/grep ${BINDIR}/zgrep \ ${BINDIR}/grep ${BINDIR}/zegrep \ ${BINDIR}/grep ${BINDIR}/zfgrep MLINKS= grep.1 egrep.1 \ grep.1 fgrep.1 \ grep.1 rgrep.1 \ grep.1 zgrep.1 \ grep.1 zegrep.1 \ grep.1 zfgrep.1 .endif LIBADD= z .if ${MK_LZMA_SUPPORT} != "no" LIBADD+= lzma .if ${MK_BSD_GREP} == "yes" LINKS+= ${BINDIR}/${PROG} ${BINDIR}/xzgrep \ ${BINDIR}/${PROG} ${BINDIR}/xzegrep \ ${BINDIR}/${PROG} ${BINDIR}/xzfgrep \ ${BINDIR}/${PROG} ${BINDIR}/lzgrep \ ${BINDIR}/${PROG} ${BINDIR}/lzegrep \ ${BINDIR}/${PROG} ${BINDIR}/lzfgrep MLINKS+= grep.1 xzgrep.1 \ grep.1 xzegrep.1 \ grep.1 xzfgrep.1 \ grep.1 lzgrep.1 \ grep.1 lzegrep.1 \ grep.1 lzfgrep.1 .endif .else CFLAGS+= -DWITHOUT_LZMA .endif .if ${MK_BZIP2_SUPPORT} != "no" LIBADD+= bz2 .if ${MK_BSD_GREP} == "yes" LINKS+= ${BINDIR}/grep ${BINDIR}/bzgrep \ ${BINDIR}/grep ${BINDIR}/bzegrep \ ${BINDIR}/grep ${BINDIR}/bzfgrep MLINKS+= grep.1 bzgrep.1 \ grep.1 bzegrep.1 \ grep.1 bzfgrep.1 .endif .else CFLAGS+= -DWITHOUT_BZIP2 .endif .if ${MK_GNU_GREP_COMPAT} != "no" CFLAGS+= -I${DESTDIR}/usr/include/gnu LIBADD+= gnuregex .endif .if ${MK_NLS} != "no" .include "${.CURDIR}/nls/Makefile.inc" .else CFLAGS+= -DWITHOUT_NLS .endif .if ${MK_TESTS} != "no" SUBDIR+= tests .endif .include Index: head/usr.bin/grep/regex/xmalloc.c =================================================================== --- head/usr.bin/grep/regex/xmalloc.c (revision 316491) +++ head/usr.bin/grep/regex/xmalloc.c (nonexistent) @@ -1,349 +0,0 @@ -/* $FreeBSD$ */ - -/* - xmalloc.c - Simple malloc debugging library implementation - - This software is released under a BSD-style license. - See the file LICENSE for details and copyright. - -*/ - -/* - TODO: - - red zones - - group dumps by source location -*/ - -#include -#include -#include -#define XMALLOC_INTERNAL 1 -#include "xmalloc.h" - - -/* - Internal stuff. -*/ - -typedef struct hashTableItemRec { - void *ptr; - int bytes; - const char *file; - int line; - const char *func; - struct hashTableItemRec *next; -} hashTableItem; - -typedef struct { - hashTableItem **table; -} hashTable; - -static int xmalloc_peak; -static int xmalloc_current; -static int xmalloc_peak_blocks; -static int xmalloc_current_blocks; -static int xmalloc_fail_after; - -#define TABLE_BITS 8 -#define TABLE_MASK ((1 << TABLE_BITS) - 1) -#define TABLE_SIZE (1 << TABLE_BITS) - -static hashTable * -hash_table_new(void) -{ - hashTable *tbl; - - tbl = malloc(sizeof(*tbl)); - - if (tbl != NULL) - { - tbl->table = calloc(TABLE_SIZE, sizeof(*tbl->table)); - - if (tbl->table == NULL) - { - free(tbl); - return NULL; - } - } - - return tbl; -} - -static int -hash_void_ptr(void *ptr) -{ - int hash; - int i; - - /* I took this hash function just off the top of my head, I have - no idea whether it is bad or very bad. */ - hash = 0; - for (i = 0; i < (int)sizeof(ptr)*8 / TABLE_BITS; i++) - { - hash ^= (unsigned long)ptr >> i*8; - hash += i * 17; - hash &= TABLE_MASK; - } - return hash; -} - -static void -hash_table_add(hashTable *tbl, void *ptr, int bytes, - const char *file, int line, const char *func) -{ - int i; - hashTableItem *item, *new; - - i = hash_void_ptr(ptr); - - item = tbl->table[i]; - if (item != NULL) - while (item->next != NULL) - item = item->next; - - new = malloc(sizeof(*new)); - assert(new != NULL); - new->ptr = ptr; - new->bytes = bytes; - new->file = file; - new->line = line; - new->func = func; - new->next = NULL; - if (item != NULL) - item->next = new; - else - tbl->table[i] = new; - - xmalloc_current += bytes; - if (xmalloc_current > xmalloc_peak) - xmalloc_peak = xmalloc_current; - xmalloc_current_blocks++; - if (xmalloc_current_blocks > xmalloc_peak_blocks) - xmalloc_peak_blocks = xmalloc_current_blocks; -} - -static void -hash_table_del(hashTable *tbl, void *ptr) -{ - int i; - hashTableItem *item, *prev; - - i = hash_void_ptr(ptr); - - item = tbl->table[i]; - if (item == NULL) - { - printf("xfree: invalid ptr %p\n", ptr); - abort(); - } - prev = NULL; - while (item->ptr != ptr) - { - prev = item; - item = item->next; - } - if (item->ptr != ptr) - { - printf("xfree: invalid ptr %p\n", ptr); - abort(); - } - - xmalloc_current -= item->bytes; - xmalloc_current_blocks--; - - if (prev != NULL) - { - prev->next = item->next; - free(item); - } - else - { - tbl->table[i] = item->next; - free(item); - } -} - -static hashTable *xmalloc_table = NULL; - -static void -xmalloc_init(void) -{ - if (xmalloc_table == NULL) - { - xmalloc_table = hash_table_new(); - xmalloc_peak = 0; - xmalloc_peak_blocks = 0; - xmalloc_current = 0; - xmalloc_current_blocks = 0; - xmalloc_fail_after = -1; - } - assert(xmalloc_table != NULL); - assert(xmalloc_table->table != NULL); -} - - - -/* - Public API. -*/ - -void -xmalloc_configure(int fail_after) -{ - xmalloc_init(); - xmalloc_fail_after = fail_after; -} - -int -xmalloc_dump_leaks(void) -{ - int i; - int num_leaks = 0; - int leaked_bytes = 0; - hashTableItem *item; - - xmalloc_init(); - - for (i = 0; i < TABLE_SIZE; i++) - { - item = xmalloc_table->table[i]; - while (item != NULL) - { - printf("%s:%d: %s: %d bytes at %p not freed\n", - item->file, item->line, item->func, item->bytes, item->ptr); - num_leaks++; - leaked_bytes += item->bytes; - item = item->next; - } - } - if (num_leaks == 0) - printf("No memory leaks.\n"); - else - printf("%d unfreed memory chuncks, total %d unfreed bytes.\n", - num_leaks, leaked_bytes); - printf("Peak memory consumption %d bytes (%.1f kB, %.1f MB) in %d blocks ", - xmalloc_peak, (double)xmalloc_peak / 1024, - (double)xmalloc_peak / (1024*1024), xmalloc_peak_blocks); - printf("(average "); - if (xmalloc_peak_blocks) - printf("%d", ((xmalloc_peak + xmalloc_peak_blocks / 2) - / xmalloc_peak_blocks)); - else - printf("N/A"); - printf(" bytes per block).\n"); - - return num_leaks; -} - -void * -xmalloc_impl(size_t size, const char *file, int line, const char *func) -{ - void *ptr; - - xmalloc_init(); - assert(size > 0); - - if (xmalloc_fail_after == 0) - { - xmalloc_fail_after = -2; -#if 0 - printf("xmalloc: forced failure %s:%d: %s\n", file, line, func); -#endif - return NULL; - } - else if (xmalloc_fail_after == -2) - { - printf("xmalloc: called after failure from %s:%d: %s\n", - file, line, func); - assert(0); - } - else if (xmalloc_fail_after > 0) - xmalloc_fail_after--; - - ptr = malloc(size); - if (ptr != NULL) - hash_table_add(xmalloc_table, ptr, (int)size, file, line, func); - return ptr; -} - -void * -xcalloc_impl(size_t nmemb, size_t size, const char *file, int line, - const char *func) -{ - void *ptr; - - xmalloc_init(); - assert(size > 0); - - if (xmalloc_fail_after == 0) - { - xmalloc_fail_after = -2; -#if 0 - printf("xcalloc: forced failure %s:%d: %s\n", file, line, func); -#endif - return NULL; - } - else if (xmalloc_fail_after == -2) - { - printf("xcalloc: called after failure from %s:%d: %s\n", - file, line, func); - assert(0); - } - else if (xmalloc_fail_after > 0) - xmalloc_fail_after--; - - ptr = calloc(nmemb, size); - if (ptr != NULL) - hash_table_add(xmalloc_table, ptr, (int)(nmemb * size), file, line, func); - return ptr; -} - -void -xfree_impl(void *ptr, const char *file, int line, const char *func) -{ - /*LINTED*/(void)&file; - /*LINTED*/(void)&line; - /*LINTED*/(void)&func; - xmalloc_init(); - - if (ptr != NULL) - hash_table_del(xmalloc_table, ptr); - free(ptr); -} - -void * -xrealloc_impl(void *ptr, size_t new_size, const char *file, int line, - const char *func) -{ - void *new_ptr; - - xmalloc_init(); - assert(ptr != NULL); - assert(new_size > 0); - - if (xmalloc_fail_after == 0) - { - xmalloc_fail_after = -2; - return NULL; - } - else if (xmalloc_fail_after == -2) - { - printf("xrealloc: called after failure from %s:%d: %s\n", - file, line, func); - assert(0); - } - else if (xmalloc_fail_after > 0) - xmalloc_fail_after--; - - new_ptr = realloc(ptr, new_size); - if (new_ptr != NULL) - { - hash_table_del(xmalloc_table, ptr); - hash_table_add(xmalloc_table, new_ptr, (int)new_size, file, line, func); - } - return new_ptr; -} - - - -/* EOF */ Property changes on: head/usr.bin/grep/regex/xmalloc.c ___________________________________________________________________ Deleted: svn:eol-style ## -1 +0,0 ## -native \ No newline at end of property Deleted: svn:keywords ## -1 +0,0 ## -FreeBSD=%H \ No newline at end of property Deleted: svn:mime-type ## -1 +0,0 ## -text/plain \ No newline at end of property Index: head/usr.bin/grep/regex/xmalloc.h =================================================================== --- head/usr.bin/grep/regex/xmalloc.h (revision 316491) +++ head/usr.bin/grep/regex/xmalloc.h (nonexistent) @@ -1,79 +0,0 @@ -/* $FreeBSD$ */ - -/* - xmalloc.h - Simple malloc debugging library API - - This software is released under a BSD-style license. - See the file LICENSE for details and copyright. - -*/ - -#ifndef _XMALLOC_H -#define _XMALLOC_H 1 - -void *xmalloc_impl(size_t size, const char *file, int line, const char *func); -void *xcalloc_impl(size_t nmemb, size_t size, const char *file, int line, - const char *func); -void xfree_impl(void *ptr, const char *file, int line, const char *func); -void *xrealloc_impl(void *ptr, size_t new_size, const char *file, int line, - const char *func); -int xmalloc_dump_leaks(void); -void xmalloc_configure(int fail_after); - - -#ifndef XMALLOC_INTERNAL -#ifdef MALLOC_DEBUGGING - -/* Version 2.4 and later of GCC define a magical variable `__PRETTY_FUNCTION__' - which contains the name of the function currently being defined. -# define __XMALLOC_FUNCTION __PRETTY_FUNCTION__ - This is broken in G++ before version 2.6. - C9x has a similar variable called __func__, but prefer the GCC one since - it demangles C++ function names. */ -# ifdef __GNUC__ -# if __GNUC__ > 2 || (__GNUC__ == 2 \ - && __GNUC_MINOR__ >= (defined __cplusplus ? 6 : 4)) -# define __XMALLOC_FUNCTION __PRETTY_FUNCTION__ -# else -# define __XMALLOC_FUNCTION ((const char *) 0) -# endif -# else -# if defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L -# define __XMALLOC_FUNCTION __func__ -# else -# define __XMALLOC_FUNCTION ((const char *) 0) -# endif -# endif - -#define xmalloc(size) xmalloc_impl(size, __FILE__, __LINE__, \ - __XMALLOC_FUNCTION) -#define xcalloc(nmemb, size) xcalloc_impl(nmemb, size, __FILE__, __LINE__, \ - __XMALLOC_FUNCTION) -#define xfree(ptr) xfree_impl(ptr, __FILE__, __LINE__, __XMALLOC_FUNCTION) -#define xrealloc(ptr, new_size) xrealloc_impl(ptr, new_size, __FILE__, \ - __LINE__, __XMALLOC_FUNCTION) -#undef malloc -#undef calloc -#undef free -#undef realloc - -#define malloc USE_XMALLOC_INSTEAD_OF_MALLOC -#define calloc USE_XCALLOC_INSTEAD_OF_CALLOC -#define free USE_XFREE_INSTEAD_OF_FREE -#define realloc USE_XREALLOC_INSTEAD_OF_REALLOC - -#else /* !MALLOC_DEBUGGING */ - -#include - -#define xmalloc(size) malloc(size) -#define xcalloc(nmemb, size) calloc(nmemb, size) -#define xfree(ptr) free(ptr) -#define xrealloc(ptr, new_size) realloc(ptr, new_size) - -#endif /* !MALLOC_DEBUGGING */ -#endif /* !XMALLOC_INTERNAL */ - -#endif /* _XMALLOC_H */ - -/* EOF */ Property changes on: head/usr.bin/grep/regex/xmalloc.h ___________________________________________________________________ Deleted: svn:eol-style ## -1 +0,0 ## -native \ No newline at end of property Deleted: svn:keywords ## -1 +0,0 ## -FreeBSD=%H \ No newline at end of property Deleted: svn:mime-type ## -1 +0,0 ## -text/plain \ No newline at end of property Index: head/usr.bin/grep/regex/fastmatch.c =================================================================== --- head/usr.bin/grep/regex/fastmatch.c (revision 316491) +++ head/usr.bin/grep/regex/fastmatch.c (revision 316492) @@ -1,169 +1,168 @@ /* $FreeBSD$ */ /*- * Copyright (C) 2011 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include "glue.h" #include #include #include #include #include "tre-fastmatch.h" -#include "xmalloc.h" int tre_fixncomp(fastmatch_t *preg, const char *regex, size_t n, int cflags) { int ret; tre_char_t *wregex; size_t wlen; if (n != 0) { ret = tre_convert_pattern(regex, n, &wregex, &wlen); if (ret != REG_OK) return ret; else ret = tre_compile_literal(preg, wregex, wlen, cflags); tre_free_pattern(wregex); return ret; } else return tre_compile_literal(preg, NULL, 0, cflags); } int tre_fastncomp(fastmatch_t *preg, const char *regex, size_t n, int cflags) { int ret; tre_char_t *wregex; size_t wlen; if (n != 0) { ret = tre_convert_pattern(regex, n, &wregex, &wlen); if (ret != REG_OK) return ret; else ret = (cflags & REG_LITERAL) ? tre_compile_literal(preg, wregex, wlen, cflags) : tre_compile_fast(preg, wregex, wlen, cflags); tre_free_pattern(wregex); return ret; } else return tre_compile_literal(preg, NULL, 0, cflags); } int tre_fixcomp(fastmatch_t *preg, const char *regex, int cflags) { return tre_fixncomp(preg, regex, regex ? strlen(regex) : 0, cflags); } int tre_fastcomp(fastmatch_t *preg, const char *regex, int cflags) { return tre_fastncomp(preg, regex, regex ? strlen(regex) : 0, cflags); } int tre_fixwncomp(fastmatch_t *preg, const wchar_t *regex, size_t n, int cflags) { return tre_compile_literal(preg, regex, n, cflags); } int tre_fastwncomp(fastmatch_t *preg, const wchar_t *regex, size_t n, int cflags) { return (cflags & REG_LITERAL) ? tre_compile_literal(preg, regex, n, cflags) : tre_compile_fast(preg, regex, n, cflags); } int tre_fixwcomp(fastmatch_t *preg, const wchar_t *regex, int cflags) { return tre_fixwncomp(preg, regex, regex ? tre_strlen(regex) : 0, cflags); } int tre_fastwcomp(fastmatch_t *preg, const wchar_t *regex, int cflags) { return tre_fastwncomp(preg, regex, regex ? tre_strlen(regex) : 0, cflags); } void tre_fastfree(fastmatch_t *preg) { tre_free_fast(preg); } int tre_fastnexec(const fastmatch_t *preg, const char *string, size_t len, size_t nmatch, regmatch_t pmatch[], int eflags) { tre_str_type_t type = (TRE_MB_CUR_MAX == 1) ? STR_BYTE : STR_MBS; if (eflags & REG_STARTEND) CALL_WITH_OFFSET(tre_match_fast(preg, &string[offset], slen, type, nmatch, pmatch, eflags)); else return tre_match_fast(preg, string, len, type, nmatch, pmatch, eflags); } int tre_fastexec(const fastmatch_t *preg, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags) { return tre_fastnexec(preg, string, (size_t)-1, nmatch, pmatch, eflags); } int tre_fastwnexec(const fastmatch_t *preg, const wchar_t *string, size_t len, size_t nmatch, regmatch_t pmatch[], int eflags) { tre_str_type_t type = STR_WIDE; if (eflags & REG_STARTEND) CALL_WITH_OFFSET(tre_match_fast(preg, &string[offset], slen, type, nmatch, pmatch, eflags)); else return tre_match_fast(preg, string, len, type, nmatch, pmatch, eflags); } int tre_fastwexec(const fastmatch_t *preg, const wchar_t *string, size_t nmatch, regmatch_t pmatch[], int eflags) { return tre_fastwnexec(preg, string, (size_t)-1, nmatch, pmatch, eflags); } Index: head/usr.bin/grep/regex/tre-compile.c =================================================================== --- head/usr.bin/grep/regex/tre-compile.c (revision 316491) +++ head/usr.bin/grep/regex/tre-compile.c (revision 316492) @@ -1,103 +1,101 @@ /* $FreeBSD$ */ #include "glue.h" #include #include #include #include #include #include -#include "xmalloc.h" - int tre_convert_pattern(const char *regex, size_t n, tre_char_t **w, size_t *wn) { #if TRE_WCHAR tre_char_t *wregex; size_t wlen; - wregex = xmalloc(sizeof(tre_char_t) * (n + 1)); + wregex = malloc(sizeof(tre_char_t) * (n + 1)); if (wregex == NULL) return REG_ESPACE; /* If the current locale uses the standard single byte encoding of characters, we don't do a multibyte string conversion. If we did, many applications which use the default locale would break since the default "C" locale uses the 7-bit ASCII character set, and all characters with the eighth bit set would be considered invalid. */ #if TRE_MULTIBYTE if (TRE_MB_CUR_MAX == 1) #endif /* TRE_MULTIBYTE */ { unsigned int i; const unsigned char *str = (const unsigned char *)regex; tre_char_t *wstr = wregex; for (i = 0; i < n; i++) *(wstr++) = *(str++); wlen = n; } #if TRE_MULTIBYTE else { int consumed; tre_char_t *wcptr = wregex; #ifdef HAVE_MBSTATE_T mbstate_t state; memset(&state, '\0', sizeof(state)); #endif /* HAVE_MBSTATE_T */ while (n > 0) { consumed = tre_mbrtowc(wcptr, regex, n, &state); switch (consumed) { case 0: if (*regex == '\0') consumed = 1; else { - xfree(wregex); + free(wregex); return REG_BADPAT; } break; case -1: DPRINT(("mbrtowc: error %d: %s.\n", errno, strerror(errno))); - xfree(wregex); + free(wregex); return REG_BADPAT; case -2: /* The last character wasn't complete. Let's not call it a fatal error. */ consumed = n; break; } regex += consumed; n -= consumed; wcptr++; } wlen = wcptr - wregex; } #endif /* TRE_MULTIBYTE */ wregex[wlen] = L'\0'; *w = wregex; *wn = wlen; return REG_OK; #else /* !TRE_WCHAR */ { *w = (tre_char_t * const *)regex; *wn = n; return REG_OK; } #endif /* !TRE_WCHAR */ } void tre_free_pattern(tre_char_t *wregex) { #if TRE_WCHAR - xfree(wregex); + free(wregex); #endif } Index: head/usr.bin/grep/regex/tre-fastmatch.c =================================================================== --- head/usr.bin/grep/regex/tre-fastmatch.c (revision 316491) +++ head/usr.bin/grep/regex/tre-fastmatch.c (revision 316492) @@ -1,1042 +1,1041 @@ /* $FreeBSD$ */ /*- * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav * Copyright (C) 2008-2011 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include "glue.h" #include #include #include #include #include #include #ifdef TRE_WCHAR #include #include #endif #include "hashtable.h" #include "tre-fastmatch.h" -#include "xmalloc.h" static int fastcmp(const fastmatch_t *fg, const void *data, tre_str_type_t type); /* * Clean up if pattern compilation fails. */ #define FAIL_COMP(errcode) \ { \ if (fg->pattern) \ - xfree(fg->pattern); \ + free(fg->pattern); \ if (fg->wpattern) \ - xfree(fg->wpattern); \ + free(fg->wpattern); \ if (fg->qsBc_table) \ hashtable_free(fg->qsBc_table); \ fg = NULL; \ return errcode; \ } /* * Skips n characters in the input string and assigns the start * address to startptr. Note: as per IEEE Std 1003.1-2008 * matching is based on bit pattern not character representations * so we can handle MB strings as byte sequences just like * SB strings. */ #define SKIP_CHARS(n) \ switch (type) \ { \ case STR_WIDE: \ startptr = str_wide + n; \ break; \ default: \ startptr = str_byte + n; \ } /* * Converts the wide string pattern to SB/MB string and stores * it in fg->pattern. Sets fg->len to the byte length of the * converted string. */ #define STORE_MBS_PAT \ { \ size_t siz; \ \ siz = wcstombs(NULL, fg->wpattern, 0); \ if (siz == (size_t)-1) \ return REG_BADPAT; \ fg->len = siz; \ - fg->pattern = xmalloc(siz + 1); \ + fg->pattern = malloc(siz + 1); \ if (fg->pattern == NULL) \ return REG_ESPACE; \ wcstombs(fg->pattern, fg->wpattern, siz); \ fg->pattern[siz] = '\0'; \ } \ #define IS_OUT_OF_BOUNDS \ ((!fg->reversed \ ? ((type == STR_WIDE) ? ((j + fg->wlen) > len) \ : ((j + fg->len) > len)) \ : (j < 0))) /* * Checks whether the new position after shifting in the input string * is out of the bounds and break out from the loop if so. */ #define CHECKBOUNDS \ if (IS_OUT_OF_BOUNDS) \ break; \ /* * Shifts in the input string after a mismatch. The position of the * mismatch is stored in the mismatch variable. */ #define SHIFT \ CHECKBOUNDS; \ \ { \ int r = -1; \ unsigned int bc = 0, gs = 0, ts; \ \ switch (type) \ { \ case STR_WIDE: \ if (!fg->hasdot) \ { \ if (u != 0 && (unsigned)mismatch == fg->wlen - 1 - shift) \ mismatch -= u; \ v = fg->wlen - 1 - mismatch; \ r = hashtable_get(fg->qsBc_table, \ &str_wide[!fg->reversed ? (size_t)j + fg->wlen \ : (size_t)j - 1], &bc); \ gs = fg->bmGs[mismatch]; \ } \ bc = (r == HASH_OK) ? bc : fg->defBc; \ DPRINT(("tre_fast_match: mismatch on character" CHF ", " \ "BC %d, GS %d\n", \ ((const tre_char_t *)startptr)[mismatch + 1], \ bc, gs)); \ break; \ default: \ if (!fg->hasdot) \ { \ if (u != 0 && (unsigned)mismatch == fg->len - 1 - shift) \ mismatch -= u; \ v = fg->len - 1 - mismatch; \ gs = fg->sbmGs[mismatch]; \ } \ bc = fg->qsBc[((const unsigned char *)str_byte) \ [!fg->reversed ? (size_t)j + fg->len \ : (size_t)j - 1]]; \ DPRINT(("tre_fast_match: mismatch on character %c, " \ "BC %d, GS %d\n", \ ((const unsigned char *)startptr)[mismatch + 1], \ bc, gs)); \ } \ if (fg->hasdot) \ shift = bc; \ else \ { \ ts = (u >= v) ? (u - v) : 0; \ shift = MAX(ts, bc); \ shift = MAX(shift, gs); \ if (shift == gs) \ u = MIN((type == STR_WIDE ? fg->wlen : fg->len) - shift, v); \ else \ { \ if (ts < bc) \ shift = MAX(shift, u + 1); \ u = 0; \ } \ } \ DPRINT(("tre_fast_match: shifting %u characters\n", shift)); \ j = !fg->reversed ? j + shift : j - shift; \ } /* * Normal Quick Search would require a shift based on the position the * next character after the comparison is within the pattern. With * wildcards, the position of the last dot effects the maximum shift * distance. * The closer to the end the wild card is the slower the search. * * Examples: * Pattern Max shift * ------- --------- * this 5 * .his 4 * t.is 3 * th.s 2 * thi. 1 */ /* * Fills in the bad character shift array for SB/MB strings. */ #define FILL_QSBC \ if (fg->reversed) \ { \ _FILL_QSBC_REVERSED \ } \ else \ { \ _FILL_QSBC \ } #define _FILL_QSBC \ for (unsigned int i = 0; i <= UCHAR_MAX; i++) \ fg->qsBc[i] = fg->len - hasdot; \ for (unsigned int i = hasdot + 1; i < fg->len; i++) \ { \ fg->qsBc[(unsigned char)fg->pattern[i]] = fg->len - i; \ DPRINT(("BC shift for char %c is %zu\n", fg->pattern[i], \ fg->len - i)); \ if (fg->icase) \ { \ char c = islower((unsigned char)fg->pattern[i]) ? \ toupper((unsigned char)fg->pattern[i]) : \ tolower((unsigned char)fg->pattern[i]); \ fg->qsBc[(unsigned char)c] = fg->len - i; \ DPRINT(("BC shift for char %c is %zu\n", c, fg->len - i)); \ } \ } #define _FILL_QSBC_REVERSED \ for (unsigned int i = 0; i <= UCHAR_MAX; i++) \ fg->qsBc[i] = firstdot + 1; \ for (int i = firstdot - 1; i >= 0; i--) \ { \ fg->qsBc[(unsigned char)fg->pattern[i]] = i + 1; \ DPRINT(("Reverse BC shift for char %c is %d\n", fg->pattern[i], \ i + 1)); \ if (fg->icase) \ { \ char c = islower((unsigned char)fg->pattern[i]) ? \ toupper((unsigned char)fg->pattern[i]) : \ tolower((unsigned char)fg->pattern[i]); \ fg->qsBc[(unsigned char)c] = i + 1; \ DPRINT(("Reverse BC shift for char %c is %d\n", c, i + 1)); \ } \ } /* * Fills in the bad character shifts into a hastable for wide strings. * With wide characters it is not possible any more to use a normal * array because there are too many characters and we could not * provide enough memory. Fortunately, we only have to store distinct * values for so many characters as the number of distinct characters * in the pattern, so we can store them in a hashtable and store a * default shift value for the rest. */ #define FILL_QSBC_WIDE \ if (fg->reversed) \ { \ _FILL_QSBC_WIDE_REVERSED \ } \ else \ { \ _FILL_QSBC_WIDE \ } #define _FILL_QSBC_WIDE \ /* Adjust the shift based on location of the last dot ('.'). */ \ fg->defBc = fg->wlen - whasdot; \ \ /* Preprocess pattern. */ \ fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \ sizeof(tre_char_t), sizeof(int)); \ if (!fg->qsBc_table) \ FAIL_COMP(REG_ESPACE); \ for (unsigned int i = whasdot + 1; i < fg->wlen; i++) \ { \ int k = fg->wlen - i; \ int r; \ \ r = hashtable_put(fg->qsBc_table, &fg->wpattern[i], &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("BC shift for wide char " CHF " is %d\n", fg->wpattern[i],\ k)); \ if (fg->icase) \ { \ tre_char_t wc = iswlower(fg->wpattern[i]) ? \ towupper(fg->wpattern[i]) : towlower(fg->wpattern[i]); \ r = hashtable_put(fg->qsBc_table, &wc, &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("BC shift for wide char " CHF " is %d\n", wc, k)); \ } \ } #define _FILL_QSBC_WIDE_REVERSED \ /* Adjust the shift based on location of the last dot ('.'). */ \ fg->defBc = (size_t)wfirstdot; \ \ /* Preprocess pattern. */ \ fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \ sizeof(tre_char_t), sizeof(int)); \ if (!fg->qsBc_table) \ FAIL_COMP(REG_ESPACE); \ for (int i = wfirstdot - 1; i >= 0; i--) \ { \ int k = i + 1; \ int r; \ \ r = hashtable_put(fg->qsBc_table, &fg->wpattern[i], &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("Reverse BC shift for wide char " CHF " is %d\n", \ fg->wpattern[i], k)); \ if (fg->icase) \ { \ tre_char_t wc = iswlower(fg->wpattern[i]) ? \ towupper(fg->wpattern[i]) : towlower(fg->wpattern[i]); \ r = hashtable_put(fg->qsBc_table, &wc, &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("Reverse BC shift for wide char " CHF " is %d\n", wc, \ k)); \ } \ } #ifdef _GREP_DEBUG #define DPRINT_BMGS(len, fmt_str, sh) \ for (unsigned int i = 0; i < len; i++) \ DPRINT((fmt_str, i, sh[i])); #else #define DPRINT_BMGS(len, fmt_str, sh) \ do { } while(/*CONSTCOND*/0) #endif /* * Fills in the good suffix table for SB/MB strings. */ #define FILL_BMGS \ if (!fg->hasdot) \ { \ - fg->sbmGs = xmalloc(fg->len * sizeof(int)); \ + fg->sbmGs = malloc(fg->len * sizeof(int)); \ if (!fg->sbmGs) \ return REG_ESPACE; \ if (fg->len == 1) \ fg->sbmGs[0] = 1; \ else \ _FILL_BMGS(fg->sbmGs, fg->pattern, fg->len, false); \ DPRINT_BMGS(fg->len, "GS shift for pos %d is %d\n", fg->sbmGs); \ } /* * Fills in the good suffix table for wide strings. */ #define FILL_BMGS_WIDE \ if (!fg->hasdot) \ { \ - fg->bmGs = xmalloc(fg->wlen * sizeof(int)); \ + fg->bmGs = malloc(fg->wlen * sizeof(int)); \ if (!fg->bmGs) \ return REG_ESPACE; \ if (fg->wlen == 1) \ fg->bmGs[0] = 1; \ else \ _FILL_BMGS(fg->bmGs, fg->wpattern, fg->wlen, true); \ DPRINT_BMGS(fg->wlen, "GS shift (wide) for pos %d is %d\n", \ fg->bmGs); \ } #define _FILL_BMGS(arr, pat, plen, wide) \ { \ char *p; \ tre_char_t *wp; \ \ if (wide) \ { \ if (fg->icase) \ { \ - wp = xmalloc(plen * sizeof(tre_char_t)); \ + wp = malloc(plen * sizeof(tre_char_t)); \ if (wp == NULL) \ return REG_ESPACE; \ for (unsigned int i = 0; i < plen; i++) \ wp[i] = towlower(pat[i]); \ _CALC_BMGS(arr, wp, plen); \ - xfree(wp); \ + free(wp); \ } \ else \ _CALC_BMGS(arr, pat, plen); \ } \ else \ { \ if (fg->icase) \ { \ - p = xmalloc(plen); \ + p = malloc(plen); \ if (p == NULL) \ return REG_ESPACE; \ for (unsigned int i = 0; i < plen; i++) \ p[i] = tolower((unsigned char)pat[i]); \ _CALC_BMGS(arr, p, plen); \ - xfree(p); \ + free(p); \ } \ else \ _CALC_BMGS(arr, pat, plen); \ } \ } #define _CALC_BMGS(arr, pat, plen) \ { \ int f = 0, g; \ \ - int *suff = xmalloc(plen * sizeof(int)); \ + int *suff = malloc(plen * sizeof(int)); \ if (suff == NULL) \ return REG_ESPACE; \ \ suff[plen - 1] = plen; \ g = plen - 1; \ for (int i = plen - 2; i >= 0; i--) \ { \ if (i > g && suff[i + plen - 1 - f] < i - g) \ suff[i] = suff[i + plen - 1 - f]; \ else \ { \ if (i < g) \ g = i; \ f = i; \ while (g >= 0 && pat[g] == pat[g + plen - 1 - f]) \ g--; \ suff[i] = f - g; \ } \ } \ \ for (unsigned int i = 0; i < plen; i++) \ arr[i] = plen; \ g = 0; \ for (int i = plen - 1; i >= 0; i--) \ if (suff[i] == i + 1) \ for(; (unsigned long)g < plen - 1 - i; g++) \ if (arr[g] == plen) \ arr[g] = plen - 1 - i; \ for (unsigned int i = 0; i <= plen - 2; i++) \ arr[plen - 1 - suff[i]] = plen - 1 - i; \ \ - xfree(suff); \ + free(suff); \ } /* * Copies the pattern pat having length n to p and stores * the size in l. */ #define SAVE_PATTERN(src, srclen, dst, dstlen) \ dstlen = srclen; \ - dst = xmalloc((dstlen + 1) * sizeof(tre_char_t)); \ + dst = malloc((dstlen + 1) * sizeof(tre_char_t)); \ if (dst == NULL) \ return REG_ESPACE; \ if (dstlen > 0) \ memcpy(dst, src, dstlen * sizeof(tre_char_t)); \ dst[dstlen] = TRE_CHAR('\0'); /* * Initializes pattern compiling. */ #define INIT_COMP \ /* Initialize. */ \ memset(fg, 0, sizeof(*fg)); \ fg->icase = (cflags & REG_ICASE); \ fg->word = (cflags & REG_WORD); \ fg->newline = (cflags & REG_NEWLINE); \ fg->nosub = (cflags & REG_NOSUB); \ \ /* Cannot handle REG_ICASE with MB string */ \ if (fg->icase && (TRE_MB_CUR_MAX > 1) && n > 0) \ { \ DPRINT(("Cannot use fast matcher for MBS with REG_ICASE\n")); \ return REG_BADPAT; \ } /* * Checks whether we have a 0-length pattern that will match * anything. If literal is set to false, the EOL anchor is also * taken into account. */ #define CHECK_MATCHALL(literal) \ if (!literal && n == 1 && pat[0] == TRE_CHAR('$')) \ { \ n--; \ fg->eol = true; \ } \ \ if (n == 0) \ { \ fg->matchall = true; \ - fg->pattern = xmalloc(sizeof(char)); \ + fg->pattern = malloc(sizeof(char)); \ if (!fg->pattern) \ FAIL_COMP(REG_ESPACE); \ fg->pattern[0] = '\0'; \ - fg->wpattern = xmalloc(sizeof(tre_char_t)); \ + fg->wpattern = malloc(sizeof(tre_char_t)); \ if (!fg->wpattern) \ FAIL_COMP(REG_ESPACE); \ fg->wpattern[0] = TRE_CHAR('\0'); \ DPRINT(("Matching every input\n")); \ return REG_OK; \ } /* * Returns: REG_OK on success, error code otherwise */ int tre_compile_literal(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) { size_t hasdot = 0, whasdot = 0; ssize_t firstdot = -1, wfirstdot = -1; INIT_COMP; CHECK_MATCHALL(true); /* Cannot handle word boundaries with MB string */ if (fg->word && (TRE_MB_CUR_MAX > 1)) return REG_BADPAT; #ifdef TRE_WCHAR SAVE_PATTERN(pat, n, fg->wpattern, fg->wlen); STORE_MBS_PAT; #else SAVE_PATTERN(pat, n, fg->pattern, fg->len); #endif DPRINT(("tre_compile_literal: pattern: %s, len %zu, icase: %c, word: %c, " "newline %c\n", fg->pattern, fg->len, fg->icase ? 'y' : 'n', fg->word ? 'y' : 'n', fg->newline ? 'y' : 'n')); FILL_QSBC; FILL_BMGS; #ifdef TRE_WCHAR FILL_QSBC_WIDE; FILL_BMGS_WIDE; #endif return REG_OK; } /* * Returns: REG_OK on success, error code otherwise */ int tre_compile_fast(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) { tre_char_t *tmp; size_t pos = 0, hasdot = 0, whasdot = 0; ssize_t firstdot = -1, wfirstdot = -1; bool escaped = false; bool *_escmap = NULL; INIT_COMP; /* Remove beginning-of-line character ('^'). */ if (pat[0] == TRE_CHAR('^')) { fg->bol = true; n--; pat++; } CHECK_MATCHALL(false); /* Handle word-boundary matching when GNU extensions are enabled */ if ((cflags & REG_GNU) && (n >= 14) && (memcmp(pat, TRE_CHAR("[[:<:]]"), 7 * sizeof(tre_char_t)) == 0) && (memcmp(pat + n - 7, TRE_CHAR("[[:>:]]"), 7 * sizeof(tre_char_t)) == 0)) { n -= 14; pat += 7; fg->word = true; } /* Cannot handle word boundaries with MB string */ if (fg->word && (TRE_MB_CUR_MAX > 1)) return REG_BADPAT; - tmp = xmalloc((n + 1) * sizeof(tre_char_t)); + tmp = malloc((n + 1) * sizeof(tre_char_t)); if (tmp == NULL) return REG_ESPACE; /* Copies the char into the stored pattern and skips to the next char. */ #define STORE_CHAR \ do \ { \ tmp[pos++] = pat[i]; \ escaped = false; \ continue; \ } while (0) /* Traverse the input pattern for processing */ for (unsigned int i = 0; i < n; i++) { switch (pat[i]) { case TRE_CHAR('\\'): if (escaped) STORE_CHAR; else if (i == n - 1) goto badpat; else escaped = true; continue; case TRE_CHAR('['): if (escaped) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('*'): if (escaped || (!(cflags & REG_EXTENDED) && (i == 0))) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('+'): case TRE_CHAR('?'): if ((cflags & REG_EXTENDED) && (i == 0)) goto badpat; else if ((cflags & REG_EXTENDED) ^ !escaped) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('.'): if (escaped) { if (!_escmap) - _escmap = xmalloc(n * sizeof(bool)); + _escmap = malloc(n * sizeof(bool)); if (!_escmap) { - xfree(tmp); + free(tmp); return REG_ESPACE; } _escmap[i] = true; STORE_CHAR; } else { whasdot = i; if (wfirstdot == -1) wfirstdot = i; STORE_CHAR; } continue; case TRE_CHAR('^'): STORE_CHAR; continue; case TRE_CHAR('$'): if (!escaped && (i == n - 1)) fg->eol = true; else STORE_CHAR; continue; case TRE_CHAR('('): if ((cflags & REG_EXTENDED) ^ escaped) goto badpat; else STORE_CHAR; continue; case TRE_CHAR('{'): if (!(cflags & REG_EXTENDED) ^ escaped) STORE_CHAR; else if (!(cflags & REG_EXTENDED) && (i == 0)) STORE_CHAR; else if ((cflags & REG_EXTENDED) && (i == 0)) continue; else goto badpat; continue; case TRE_CHAR('|'): if ((cflags & REG_EXTENDED) ^ escaped) goto badpat; else STORE_CHAR; continue; default: if (escaped) goto badpat; else STORE_CHAR; continue; } continue; badpat: - xfree(tmp); + free(tmp); DPRINT(("tre_compile_fast: compilation of pattern failed, falling" "back to NFA\n")); return REG_BADPAT; } fg->hasdot = wfirstdot > -1; /* * The pattern has been processed and copied to tmp as a literal string * with escapes, anchors (^$) and the word boundary match character * classes stripped out. */ #ifdef TRE_WCHAR SAVE_PATTERN(tmp, pos, fg->wpattern, fg->wlen); fg->wescmap = _escmap; STORE_MBS_PAT; /* * The position of dots and escaped dots is different in the MB string * than in to the wide string so traverse the converted string, as well, * to store these positions. */ if (fg->hasdot || (fg->wescmap != NULL)) { if (fg->wescmap != NULL) { - fg->escmap = xmalloc(fg->len * sizeof(bool)); + fg->escmap = malloc(fg->len * sizeof(bool)); if (!fg->escmap) { tre_free_fast(fg); return REG_ESPACE; } } escaped = false; for (unsigned int i = 0; i < fg->len; i++) if (fg->pattern[i] == '\\') escaped = !escaped; else if (fg->pattern[i] == '.' && fg->escmap && escaped) { fg->escmap[i] = true; escaped = false; } else if (fg->pattern[i] == '.' && !escaped) { hasdot = i; if (firstdot == -1) firstdot = i; } else escaped = false; } #else SAVE_PATTERN(tmp, pos, fg->pattern, fg->len); fg->escmap = _escmap; #endif - xfree(tmp); + free(tmp); DPRINT(("tre_compile_fast: pattern: %s, len %zu, bol %c, eol %c, " "icase: %c, word: %c, newline %c\n", fg->pattern, fg->len, fg->bol ? 'y' : 'n', fg->eol ? 'y' : 'n', fg->icase ? 'y' : 'n', fg->word ? 'y' : 'n', fg->newline ? 'y' : 'n')); /* Check whether reverse QS algorithm is more efficient */ if ((wfirstdot > -1) && (fg->wlen - whasdot + 1 < (size_t)wfirstdot) && fg->nosub) { fg->reversed = true; DPRINT(("tre_compile_fast: using reverse QS algorithm\n")); } FILL_QSBC; FILL_BMGS; #ifdef TRE_WCHAR FILL_QSBC_WIDE; FILL_BMGS_WIDE; #endif return REG_OK; } #define _SHIFT_ONE \ { \ shift = 1; \ j = !fg->reversed ? j + shift : j - shift; \ continue; \ } #define _BBOUND_COND \ ((type == STR_WIDE) ? \ ((j == 0) || !(tre_isalnum(str_wide[j - 1]) || \ (str_wide[j - 1] == TRE_CHAR('_')))) : \ ((j == 0) || !(tre_isalnum(str_byte[j - 1]) || \ (str_byte[j - 1] == '_')))) #define _EBOUND_COND \ ((type == STR_WIDE) ? \ ((j + fg->wlen == len) || !(tre_isalnum(str_wide[j + fg->wlen]) || \ (str_wide[j + fg->wlen] == TRE_CHAR('_')))) : \ ((j + fg->len == len) || !(tre_isalnum(str_byte[j + fg->len]) || \ (str_byte[j + fg->len] == '_')))) /* * Condition to check whether the match on position j is on a * word boundary. */ #define IS_ON_WORD_BOUNDARY \ (_BBOUND_COND && _EBOUND_COND) /* * Checks word boundary and shifts one if match is not on a * boundary. */ #define CHECK_WORD_BOUNDARY \ if (!IS_ON_WORD_BOUNDARY) \ _SHIFT_ONE; #define _BOL_COND \ ((j == 0) || ((type == STR_WIDE) ? (str_wide[j - 1] == TRE_CHAR('\n'))\ : (str_byte[j - 1] == '\n'))) /* * Checks BOL anchor and shifts one if match is not on a * boundary. */ #define CHECK_BOL_ANCHOR \ if (!_BOL_COND) \ _SHIFT_ONE; #define _EOL_COND \ ((type == STR_WIDE) \ ? ((j + fg->wlen == len) || \ (str_wide[j + fg->wlen] == TRE_CHAR('\n'))) \ : ((j + fg->len == len) || (str_byte[j + fg->wlen] == '\n'))) /* * Checks EOL anchor and shifts one if match is not on a * boundary. */ #define CHECK_EOL_ANCHOR \ if (!_EOL_COND) \ _SHIFT_ONE; /* * Executes matching of the precompiled pattern on the input string. * Returns REG_OK or REG_NOMATCH depending on if we find a match or not. */ int tre_match_fast(const fastmatch_t *fg, const void *data, size_t len, tre_str_type_t type, int nmatch, regmatch_t pmatch[], int eflags) { unsigned int shift, u = 0, v = 0; ssize_t j = 0; int ret = REG_NOMATCH; int mismatch; const char *str_byte = data; const void *startptr = NULL; const tre_char_t *str_wide = data; /* Calculate length if unspecified. */ if (len == (size_t)-1) switch (type) { case STR_WIDE: len = tre_strlen(str_wide); break; default: len = strlen(str_byte); break; } /* Shortcut for empty pattern */ if (fg->matchall) { if (!fg->nosub && nmatch >= 1) { pmatch[0].rm_so = 0; pmatch[0].rm_eo = len; } if (fg->bol && fg->eol) return (len == 0) ? REG_OK : REG_NOMATCH; else return REG_OK; } /* No point in going farther if we do not have enough data. */ switch (type) { case STR_WIDE: if (len < fg->wlen) return ret; shift = fg->wlen; break; default: if (len < fg->len) return ret; shift = fg->len; } /* * REG_NOTBOL means not anchoring ^ to the beginning of the line, so we * can shift one because there can't be a match at the beginning. */ if (fg->bol && (eflags & REG_NOTBOL)) j = 1; /* * Like above, we cannot have a match at the very end when anchoring to * the end and REG_NOTEOL is specified. */ if (fg->eol && (eflags & REG_NOTEOL)) len--; if (fg->reversed) j = len - (type == STR_WIDE ? fg->wlen : fg->len); /* Only try once at the beginning or ending of the line. */ if ((fg->bol || fg->eol) && !fg->newline && !(eflags & REG_NOTBOL) && !(eflags & REG_NOTEOL)) { /* Simple text comparison. */ if (!((fg->bol && fg->eol) && (type == STR_WIDE ? (len != fg->wlen) : (len != fg->len)))) { /* Determine where in data to start search at. */ j = fg->eol ? len - (type == STR_WIDE ? fg->wlen : fg->len) : 0; SKIP_CHARS(j); mismatch = fastcmp(fg, startptr, type); if (mismatch == REG_OK) { if (fg->word && !IS_ON_WORD_BOUNDARY) return ret; if (!fg->nosub && nmatch >= 1) { pmatch[0].rm_so = j; pmatch[0].rm_eo = j + (type == STR_WIDE ? fg->wlen : fg->len); } return REG_OK; } } } else { /* Quick Search / Turbo Boyer-Moore algorithm. */ do { SKIP_CHARS(j); mismatch = fastcmp(fg, startptr, type); if (mismatch == REG_OK) { if (fg->word) CHECK_WORD_BOUNDARY; if (fg->bol) CHECK_BOL_ANCHOR; if (fg->eol) CHECK_EOL_ANCHOR; if (!fg->nosub && nmatch >= 1) { pmatch[0].rm_so = j; pmatch[0].rm_eo = j + ((type == STR_WIDE) ? fg->wlen : fg->len); } return REG_OK; } else if (mismatch > 0) return mismatch; mismatch = -mismatch - 1; SHIFT; } while (!IS_OUT_OF_BOUNDS); } return ret; } /* * Frees the resources that were allocated when the pattern was compiled. */ void tre_free_fast(fastmatch_t *fg) { DPRINT(("tre_fast_free: freeing structures for pattern %s\n", fg->pattern)); #ifdef TRE_WCHAR hashtable_free(fg->qsBc_table); if (!fg->hasdot) - xfree(fg->bmGs); + free(fg->bmGs); if (fg->wescmap) - xfree(fg->wescmap); - xfree(fg->wpattern); + free(fg->wescmap); + free(fg->wpattern); #endif if (!fg->hasdot) - xfree(fg->sbmGs); + free(fg->sbmGs); if (fg->escmap) - xfree(fg->escmap); - xfree(fg->pattern); + free(fg->escmap); + free(fg->pattern); } /* * Returns: -(i + 1) on failure (position that it failed with minus sign) * error code on error * REG_OK on success */ static inline int fastcmp(const fastmatch_t *fg, const void *data, tre_str_type_t type) { const char *str_byte = data; const char *pat_byte = fg->pattern; const tre_char_t *str_wide = data; const tre_char_t *pat_wide = fg->wpattern; const bool *escmap = (type == STR_WIDE) ? fg->wescmap : fg->escmap; size_t len = (type == STR_WIDE) ? fg->wlen : fg->len; int ret = REG_OK; /* Compare the pattern and the input char-by-char from the last position. */ for (int i = len - 1; i >= 0; i--) { switch (type) { case STR_WIDE: /* Check dot */ if (fg->hasdot && pat_wide[i] == TRE_CHAR('.') && (!escmap || !escmap[i]) && (!fg->newline || (str_wide[i] != TRE_CHAR('\n')))) continue; /* Compare */ if (fg->icase ? (towlower(pat_wide[i]) == towlower(str_wide[i])) : (pat_wide[i] == str_wide[i])) continue; break; default: /* Check dot */ if (fg->hasdot && pat_byte[i] == '.' && (!escmap || !escmap[i]) && (!fg->newline || (str_byte[i] != '\n'))) continue; /* Compare */ if (fg->icase ? (tolower((unsigned char)pat_byte[i]) == tolower((unsigned char)str_byte[i])) : (pat_byte[i] == str_byte[i])) continue; } DPRINT(("fastcmp: mismatch at position %d\n", i)); ret = -(i + 1); break; } return ret; }