1257145Sbdrewery/* 2263938Sbdrewery tre.h - TRE internal definitions 3263938Sbdrewery 4263938Sbdrewery Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> 5263938Sbdrewery All rights reserved. 6263938Sbdrewery 7263938Sbdrewery Redistribution and use in source and binary forms, with or without 8263938Sbdrewery modification, are permitted provided that the following conditions 9263938Sbdrewery are met: 10257145Sbdrewery 11285830Sgjb 1. Redistributions of source code must retain the above copyright 12257145Sbdrewery notice, this list of conditions and the following disclaimer. 13257794Sbdrewery 14257572Sbdrewery 2. Redistributions in binary form must reproduce the above copyright 15258710Sgjb notice, this list of conditions and the following disclaimer in the 16257145Sbdrewery 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 36#undef TRE_MBSTATE 37 38#define NDEBUG 39 40#define TRE_REGEX_T_FIELD __opaque 41typedef int reg_errcode_t; 42 43typedef wchar_t tre_char_t; 44 45#define DPRINT(msg) \ 46 do { \ 47 } while (0) 48 49#define elementsof(x) (sizeof(x) / sizeof(x[0])) 50 51#define tre_mbrtowc(pwc, s, n, ps) (mbtowc((pwc), (s), (n))) 52 53/* Wide characters. */ 54typedef wint_t tre_cint_t; 55#define TRE_CHAR_MAX 0x10ffff 56 57#define tre_isalnum iswalnum 58#define tre_isalpha iswalpha 59#define tre_isblank iswblank 60#define tre_iscntrl iswcntrl 61#define tre_isdigit iswdigit 62#define tre_isgraph iswgraph 63#define tre_islower iswlower 64#define tre_isprint iswprint 65#define tre_ispunct iswpunct 66#define tre_isspace iswspace 67#define tre_isupper iswupper 68#define tre_isxdigit iswxdigit 69 70#define tre_tolower towlower 71#define tre_toupper towupper 72#define tre_strlen wcslen 73 74/* Use system provided iswctype() and wctype(). */ 75typedef wctype_t tre_ctype_t; 76#define tre_isctype iswctype 77#define tre_ctype wctype 78 79/* Returns number of bytes to add to (char *)ptr to make it 80 properly aligned for the type. */ 81#define ALIGN(ptr, type) \ 82 ((((long)ptr) % sizeof(type)) ? (sizeof(type) - (((long)ptr) % sizeof(type))) : 0) 83 84#undef MAX 85#undef MIN 86#define MAX(a, b) (((a) >= (b)) ? (a) : (b)) 87#define MIN(a, b) (((a) <= (b)) ? (a) : (b)) 88 89/* TNFA transition type. A TNFA state is an array of transitions, 90 the terminator is a transition with NULL `state'. */ 91typedef struct tnfa_transition tre_tnfa_transition_t; 92 93struct tnfa_transition { 94 /* Range of accepted characters. */ 95 tre_cint_t code_min; 96 tre_cint_t code_max; 97 /* Pointer to the destination state. */ 98 tre_tnfa_transition_t* state; 99 /* ID number of the destination state. */ 100 int state_id; 101 /* -1 terminated array of tags (or NULL). */ 102 int* tags; 103 /* Assertion bitmap. */ 104 int assertions; 105 /* Assertion parameters. */ 106 union { 107 /* Character class assertion. */ 108 tre_ctype_t class; 109 /* Back reference assertion. */ 110 int backref; 111 } u; 112 /* Negative character class assertions. */ 113 tre_ctype_t* neg_classes; 114}; 115 116/* Assertions. */ 117#define ASSERT_AT_BOL 1 /* Beginning of line. */ 118#define ASSERT_AT_EOL 2 /* End of line. */ 119#define ASSERT_CHAR_CLASS 4 /* Character class in `class'. */ 120#define ASSERT_CHAR_CLASS_NEG 8 /* Character classes in `neg_classes'. */ 121#define ASSERT_AT_BOW 16 /* Beginning of word. */ 122#define ASSERT_AT_EOW 32 /* End of word. */ 123#define ASSERT_AT_WB 64 /* Word boundary. */ 124#define ASSERT_AT_WB_NEG 128 /* Not a word boundary. */ 125#define ASSERT_BACKREF 256 /* A back reference in `backref'. */ 126#define ASSERT_LAST 256 127 128/* Tag directions. */ 129typedef enum { TRE_TAG_MINIMIZE = 0, 130 TRE_TAG_MAXIMIZE = 1 } tre_tag_direction_t; 131 132/* Instructions to compute submatch register values from tag values 133 after a successful match. */ 134struct tre_submatch_data { 135 /* Tag that gives the value for rm_so (submatch start offset). */ 136 int so_tag; 137 /* Tag that gives the value for rm_eo (submatch end offset). */ 138 int eo_tag; 139 /* List of submatches this submatch is contained in. */ 140 int* parents; 141}; 142 143typedef struct tre_submatch_data tre_submatch_data_t; 144 145/* TNFA definition. */ 146typedef struct tnfa tre_tnfa_t; 147 148struct tnfa { 149 tre_tnfa_transition_t* transitions; 150 unsigned int num_transitions; 151 tre_tnfa_transition_t* initial; 152 tre_tnfa_transition_t* final; 153 tre_submatch_data_t* submatch_data; 154 char* firstpos_chars; 155 int first_char; 156 unsigned int num_submatches; 157 tre_tag_direction_t* tag_directions; 158 int* minimal_tags; 159 int num_tags; 160 int num_minimals; 161 int end_tag; 162 int num_states; 163 int cflags; 164 int have_backrefs; 165 int have_approx; 166}; 167 168/* from tre-mem.h: */ 169 170#define TRE_MEM_BLOCK_SIZE 1024 171 172typedef struct tre_list { 173 void* data; 174 struct tre_list* next; 175} tre_list_t; 176 177typedef struct tre_mem_struct { 178 tre_list_t* blocks; 179 tre_list_t* current; 180 char* ptr; 181 size_t n; 182 int failed; 183 void** provided; 184} * tre_mem_t; 185 186#define tre_mem_new_impl __tre_mem_new_impl 187#define tre_mem_alloc_impl __tre_mem_alloc_impl 188#define tre_mem_destroy __tre_mem_destroy 189 190tre_mem_t tre_mem_new_impl(int provided, void* provided_block); 191void* tre_mem_alloc_impl(tre_mem_t mem, int provided, void* provided_block, int zero, size_t size); 192 193/* Returns a new memory allocator or NULL if out of memory. */ 194#define tre_mem_new() tre_mem_new_impl(0, NULL) 195 196/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the 197 allocated block or NULL if an underlying malloc() failed. */ 198#define tre_mem_alloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 0, size) 199 200/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the 201 allocated block or NULL if an underlying malloc() failed. The memory 202 is set to zero. */ 203#define tre_mem_calloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 1, size) 204 205#ifdef TRE_USE_ALLOCA 206/* alloca() versions. Like above, but memory is allocated with alloca() 207 instead of malloc(). */ 208 209#define tre_mem_newa() tre_mem_new_impl(1, alloca(sizeof(struct tre_mem_struct))) 210 211#define tre_mem_alloca(mem, size) \ 212 ((mem)->n >= (size) ? tre_mem_alloc_impl((mem), 1, NULL, 0, (size)) \ 213 : tre_mem_alloc_impl((mem), 1, alloca(TRE_MEM_BLOCK_SIZE), 0, (size))) 214#endif /* TRE_USE_ALLOCA */ 215 216/* Frees the memory allocator and all memory allocated with it. */ 217void tre_mem_destroy(tre_mem_t mem); 218 219#define xmalloc malloc 220#define xcalloc calloc 221#define xfree free 222#define xrealloc realloc 223