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
36#undef  TRE_MBSTATE
37
38#ifndef NDEBUG
39#define NDEBUG
40#endif
41
42#define TRE_REGEX_T_FIELD __opaque
43typedef int reg_errcode_t;
44
45typedef wchar_t tre_char_t;
46
47#define DPRINT(msg) do { } 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)) \
83   ? (sizeof(type) - (((long)ptr) % sizeof(type))) \
84   : 0)
85
86#undef MAX
87#undef MIN
88#define MAX(a, b) (((a) >= (b)) ? (a) : (b))
89#define MIN(a, b) (((a) <= (b)) ? (a) : (b))
90
91/* TNFA transition type. A TNFA state is an array of transitions,
92   the terminator is a transition with NULL `state'. */
93typedef struct tnfa_transition tre_tnfa_transition_t;
94
95struct tnfa_transition {
96  /* Range of accepted characters. */
97  tre_cint_t code_min;
98  tre_cint_t code_max;
99  /* Pointer to the destination state. */
100  tre_tnfa_transition_t *state;
101  /* ID number of the destination state. */
102  int state_id;
103  /* -1 terminated array of tags (or NULL). */
104  int *tags;
105  /* Assertion bitmap. */
106  int assertions;
107  /* Assertion parameters. */
108  union {
109    /* Character class assertion. */
110    tre_ctype_t class;
111    /* Back reference assertion. */
112    int backref;
113  } u;
114  /* Negative character class assertions. */
115  tre_ctype_t *neg_classes;
116};
117
118
119/* Assertions. */
120#define ASSERT_AT_BOL		  1   /* Beginning of line. */
121#define ASSERT_AT_EOL		  2   /* End of line. */
122#define ASSERT_CHAR_CLASS	  4   /* Character class in `class'. */
123#define ASSERT_CHAR_CLASS_NEG	  8   /* Character classes in `neg_classes'. */
124#define ASSERT_AT_BOW		 16   /* Beginning of word. */
125#define ASSERT_AT_EOW		 32   /* End of word. */
126#define ASSERT_AT_WB		 64   /* Word boundary. */
127#define ASSERT_AT_WB_NEG	128   /* Not a word boundary. */
128#define ASSERT_BACKREF		256   /* A back reference in `backref'. */
129#define ASSERT_LAST		256
130
131/* Tag directions. */
132typedef enum {
133  TRE_TAG_MINIMIZE = 0,
134  TRE_TAG_MAXIMIZE = 1
135} tre_tag_direction_t;
136
137/* Instructions to compute submatch register values from tag values
138   after a successful match.  */
139struct tre_submatch_data {
140  /* Tag that gives the value for rm_so (submatch start offset). */
141  int so_tag;
142  /* Tag that gives the value for rm_eo (submatch end offset). */
143  int eo_tag;
144  /* List of submatches this submatch is contained in. */
145  int *parents;
146};
147
148typedef struct tre_submatch_data tre_submatch_data_t;
149
150
151/* TNFA definition. */
152typedef struct tnfa tre_tnfa_t;
153
154struct tnfa {
155  tre_tnfa_transition_t *transitions;
156  unsigned int num_transitions;
157  tre_tnfa_transition_t *initial;
158  tre_tnfa_transition_t *final;
159  tre_submatch_data_t *submatch_data;
160  char *firstpos_chars;
161  int first_char;
162  unsigned int num_submatches;
163  tre_tag_direction_t *tag_directions;
164  int *minimal_tags;
165  int num_tags;
166  int num_minimals;
167  int end_tag;
168  int num_states;
169  int cflags;
170  int have_backrefs;
171  int have_approx;
172};
173
174/* from tre-mem.h: */
175
176#define TRE_MEM_BLOCK_SIZE 1024
177
178typedef struct tre_list {
179  void *data;
180  struct tre_list *next;
181} tre_list_t;
182
183typedef struct tre_mem_struct {
184  tre_list_t *blocks;
185  tre_list_t *current;
186  char *ptr;
187  size_t n;
188  int failed;
189  void **provided;
190} *tre_mem_t;
191
192#define tre_mem_new_impl   __tre_mem_new_impl
193#define tre_mem_alloc_impl __tre_mem_alloc_impl
194#define tre_mem_destroy    __tre_mem_destroy
195
196tre_mem_t tre_mem_new_impl(int provided, void *provided_block);
197void *tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block,
198			 int zero, size_t size);
199
200/* Returns a new memory allocator or NULL if out of memory. */
201#define tre_mem_new()  tre_mem_new_impl(0, NULL)
202
203/* Allocates a block of `size' bytes from `mem'.  Returns a pointer to the
204   allocated block or NULL if an underlying malloc() failed. */
205#define tre_mem_alloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 0, size)
206
207/* Allocates a block of `size' bytes from `mem'.  Returns a pointer to the
208   allocated block or NULL if an underlying malloc() failed.  The memory
209   is set to zero. */
210#define tre_mem_calloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 1, size)
211
212#ifdef TRE_USE_ALLOCA
213/* alloca() versions.  Like above, but memory is allocated with alloca()
214   instead of malloc(). */
215
216#define tre_mem_newa() \
217  tre_mem_new_impl(1, alloca(sizeof(struct tre_mem_struct)))
218
219#define tre_mem_alloca(mem, size)					      \
220  ((mem)->n >= (size)							      \
221   ? tre_mem_alloc_impl((mem), 1, NULL, 0, (size))			      \
222   : tre_mem_alloc_impl((mem), 1, alloca(TRE_MEM_BLOCK_SIZE), 0, (size)))
223#endif /* TRE_USE_ALLOCA */
224
225
226/* Frees the memory allocator and all memory allocated with it. */
227void tre_mem_destroy(tre_mem_t mem);
228
229#define xmalloc malloc
230#define xcalloc calloc
231#define xfree free
232#define xrealloc realloc
233
234