1 /* 2 tre-internal.h - TRE internal definitions 3 4 Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> 5 All rights reserved. 6 7 Redistribution and use in source and binary forms, with or without 8 modification, are permitted provided that the following conditions 9 are met: 10 11 1. Redistributions of source code must retain the above copyright 12 notice, this list of conditions and the following disclaimer. 13 14 2. Redistributions in binary form must reproduce the above copyright 15 notice, this list of conditions and the following disclaimer in the 16 documentation and/or other materials provided with the distribution. 17 18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS 19 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30 */ 31 32 #include <regex.h> 33 #include <wchar.h> 34 #include <wctype.h> 35 #include "../include/features.h" 36 37 #undef TRE_MBSTATE 38 39 #define NDEBUG 40 41 #define TRE_REGEX_T_FIELD __opaque 42 typedef int reg_errcode_t; 43 44 typedef wchar_t tre_char_t; 45 46 #define DPRINT(msg) do { } while(0) 47 48 #define elementsof(x) ( sizeof(x) / sizeof(x[0]) ) 49 50 #define tre_mbrtowc(pwc, s, n, ps) (mbtowc((pwc), (s), (n))) 51 52 /* Wide characters. */ 53 typedef wint_t tre_cint_t; 54 #define TRE_CHAR_MAX 0x10ffff 55 56 #define tre_isalnum iswalnum 57 #define tre_isalpha iswalpha 58 #define tre_isblank iswblank 59 #define tre_iscntrl iswcntrl 60 #define tre_isdigit iswdigit 61 #define tre_isgraph iswgraph 62 #define tre_islower iswlower 63 #define tre_isprint iswprint 64 #define tre_ispunct iswpunct 65 #define tre_isspace iswspace 66 #define tre_isupper iswupper 67 #define tre_isxdigit iswxdigit 68 69 #define tre_tolower towlower 70 #define tre_toupper towupper 71 #define tre_strlen wcslen 72 73 /* Use system provided iswctype() and wctype(). */ 74 typedef wctype_t tre_ctype_t; 75 #define tre_isctype iswctype 76 #define tre_ctype wctype 77 78 /* Returns number of bytes to add to (char *)ptr to make it 79 properly aligned for the type. */ 80 #define ALIGN(ptr, type) \ 81 ((((long)ptr) % sizeof(type)) \ 82 ? (sizeof(type) - (((long)ptr) % sizeof(type))) \ 83 : 0) 84 85 #undef MAX 86 #undef MIN 87 #define MAX(a, b) (((a) >= (b)) ? (a) : (b)) 88 #define MIN(a, b) (((a) <= (b)) ? (a) : (b)) 89 90 /* TNFA transition type. A TNFA state is an array of transitions, 91 the terminator is a transition with NULL `state'. */ 92 typedef struct tnfa_transition tre_tnfa_transition_t; 93 94 struct tnfa_transition { 95 /* Range of accepted characters. */ 96 tre_cint_t code_min; 97 tre_cint_t code_max; 98 /* Pointer to the destination state. */ 99 tre_tnfa_transition_t *state; 100 /* ID number of the destination state. */ 101 int state_id; 102 /* -1 terminated array of tags (or NULL). */ 103 int *tags; 104 /* Assertion bitmap. */ 105 int assertions; 106 /* Assertion parameters. */ 107 union { 108 /* Character class assertion. */ 109 tre_ctype_t class; 110 /* Back reference assertion. */ 111 int backref; 112 } u; 113 /* Negative character class assertions. */ 114 tre_ctype_t *neg_classes; 115 }; 116 117 118 /* Assertions. */ 119 #define ASSERT_AT_BOL 1 /* Beginning of line. */ 120 #define ASSERT_AT_EOL 2 /* End of line. */ 121 #define ASSERT_CHAR_CLASS 4 /* Character class in `class'. */ 122 #define ASSERT_CHAR_CLASS_NEG 8 /* Character classes in `neg_classes'. */ 123 #define ASSERT_AT_BOW 16 /* Beginning of word. */ 124 #define ASSERT_AT_EOW 32 /* End of word. */ 125 #define ASSERT_AT_WB 64 /* Word boundary. */ 126 #define ASSERT_AT_WB_NEG 128 /* Not a word boundary. */ 127 #define ASSERT_BACKREF 256 /* A back reference in `backref'. */ 128 #define ASSERT_LAST 256 129 130 /* Tag directions. */ 131 typedef enum { 132 TRE_TAG_MINIMIZE = 0, 133 TRE_TAG_MAXIMIZE = 1 134 } tre_tag_direction_t; 135 136 /* Instructions to compute submatch register values from tag values 137 after a successful match. */ 138 struct tre_submatch_data { 139 /* Tag that gives the value for rm_so (submatch start offset). */ 140 int so_tag; 141 /* Tag that gives the value for rm_eo (submatch end offset). */ 142 int eo_tag; 143 /* List of submatches this submatch is contained in. */ 144 int *parents; 145 }; 146 147 typedef struct tre_submatch_data tre_submatch_data_t; 148 149 150 /* TNFA definition. */ 151 typedef struct tnfa tre_tnfa_t; 152 153 struct tnfa { 154 tre_tnfa_transition_t *transitions; 155 unsigned int num_transitions; 156 tre_tnfa_transition_t *initial; 157 tre_tnfa_transition_t *final; 158 tre_submatch_data_t *submatch_data; 159 char *firstpos_chars; 160 int first_char; 161 unsigned int num_submatches; 162 tre_tag_direction_t *tag_directions; 163 int *minimal_tags; 164 int num_tags; 165 int num_minimals; 166 int end_tag; 167 int num_states; 168 int cflags; 169 int have_backrefs; 170 int have_approx; 171 }; 172 173 /* from tre-mem.h: */ 174 175 #define TRE_MEM_BLOCK_SIZE 1024 176 177 typedef struct tre_list { 178 void *data; 179 struct tre_list *next; 180 } tre_list_t; 181 182 typedef struct tre_mem_struct { 183 tre_list_t *blocks; 184 tre_list_t *current; 185 char *ptr; 186 size_t n; 187 int failed; 188 void **provided; 189 } *tre_mem_t; 190 191 #define tre_mem_new_impl __tre_mem_new_impl 192 #define tre_mem_alloc_impl __tre_mem_alloc_impl 193 #define tre_mem_destroy __tre_mem_destroy 194 195 hidden tre_mem_t tre_mem_new_impl(int provided, void *provided_block); 196 hidden void *tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block, 197 int zero, size_t size); 198 199 /* Returns a new memory allocator or NULL if out of memory. */ 200 #define tre_mem_new() tre_mem_new_impl(0, NULL) 201 202 /* Allocates a block of `size' bytes from `mem'. Returns a pointer to the 203 allocated block or NULL if an underlying malloc() failed. */ 204 #define tre_mem_alloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 0, size) 205 206 /* Allocates a block of `size' bytes from `mem'. Returns a pointer to the 207 allocated block or NULL if an underlying malloc() failed. The memory 208 is set to zero. */ 209 #define tre_mem_calloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 1, size) 210 211 #ifdef TRE_USE_ALLOCA 212 /* alloca() versions. Like above, but memory is allocated with alloca() 213 instead of malloc(). */ 214 215 #define tre_mem_newa() \ 216 tre_mem_new_impl(1, alloca(sizeof(struct tre_mem_struct))) 217 218 #define tre_mem_alloca(mem, size) \ 219 ((mem)->n >= (size) \ 220 ? tre_mem_alloc_impl((mem), 1, NULL, 0, (size)) \ 221 : tre_mem_alloc_impl((mem), 1, alloca(TRE_MEM_BLOCK_SIZE), 0, (size))) 222 #endif /* TRE_USE_ALLOCA */ 223 224 225 /* Frees the memory allocator and all memory allocated with it. */ 226 hidden void tre_mem_destroy(tre_mem_t mem); 227 228 #define xmalloc malloc 229 #define xcalloc calloc 230 #define xfree free 231 #define xrealloc realloc 232 233