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