nsz Git - musl/blob - src/regex/tre.h

   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 #define NDEBUG
  39
  40 #define TRE_REGEX_T_FIELD __opaque
  41 typedef int reg_errcode_t;
  42
  43 typedef wchar_t tre_char_t;
  44
  45 #define DPRINT(msg) do { } while(0)
  46
  47 #define elementsof(x)   ( sizeof(x) / sizeof(x[0]) )
  48
  49 #define tre_mbrtowc(pwc, s, n, ps) (mbtowc((pwc), (s), (n)))
  50
  51 /* Wide characters. */
  52 typedef wint_t tre_cint_t;
  53 #define TRE_CHAR_MAX 0x10ffff
  54
  55 #define tre_isalnum iswalnum
  56 #define tre_isalpha iswalpha
  57 #define tre_isblank iswblank
  58 #define tre_iscntrl iswcntrl
  59 #define tre_isdigit iswdigit
  60 #define tre_isgraph iswgraph
  61 #define tre_islower iswlower
  62 #define tre_isprint iswprint
  63 #define tre_ispunct iswpunct
  64 #define tre_isspace iswspace
  65 #define tre_isupper iswupper
  66 #define tre_isxdigit iswxdigit
  67
  68 #define tre_tolower towlower
  69 #define tre_toupper towupper
  70 #define tre_strlen  wcslen
  71
  72 /* Use system provided iswctype() and wctype(). */
  73 typedef wctype_t tre_ctype_t;
  74 #define tre_isctype iswctype
  75 #define tre_ctype   wctype
  76
  77 /* Returns number of bytes to add to (char *)ptr to make it
  78    properly aligned for the type. */
  79 #define ALIGN(ptr, type) \
  80   ((((long)ptr) % sizeof(type)) \
  81    ? (sizeof(type) - (((long)ptr) % sizeof(type))) \
  82    : 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'. */
  91 typedef struct tnfa_transition tre_tnfa_transition_t;
  92
  93 struct 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
 117 /* Assertions. */
 118 #define ASSERT_AT_BOL             1   /* Beginning of line. */
 119 #define ASSERT_AT_EOL             2   /* End of line. */
 120 #define ASSERT_CHAR_CLASS         4   /* Character class in `class'. */
 121 #define ASSERT_CHAR_CLASS_NEG     8   /* Character classes in `neg_classes'. */
 122 #define ASSERT_AT_BOW            16   /* Beginning of word. */
 123 #define ASSERT_AT_EOW            32   /* End of word. */
 124 #define ASSERT_AT_WB             64   /* Word boundary. */
 125 #define ASSERT_AT_WB_NEG        128   /* Not a word boundary. */
 126 #define ASSERT_BACKREF          256   /* A back reference in `backref'. */
 127 #define ASSERT_LAST             256
 128
 129 /* Tag directions. */
 130 typedef enum {
 131   TRE_TAG_MINIMIZE = 0,
 132   TRE_TAG_MAXIMIZE = 1
 133 } tre_tag_direction_t;
 134
 135 /* Instructions to compute submatch register values from tag values
 136    after a successful match.  */
 137 struct tre_submatch_data {
 138   /* Tag that gives the value for rm_so (submatch start offset). */
 139   int so_tag;
 140   /* Tag that gives the value for rm_eo (submatch end offset). */
 141   int eo_tag;
 142   /* List of submatches this submatch is contained in. */
 143   int *parents;
 144 };
 145
 146 typedef struct tre_submatch_data tre_submatch_data_t;
 147
 148
 149 /* TNFA definition. */
 150 typedef struct tnfa tre_tnfa_t;
 151
 152 struct tnfa {
 153   tre_tnfa_transition_t *transitions;
 154   unsigned int num_transitions;
 155   tre_tnfa_transition_t *initial;
 156   tre_tnfa_transition_t *final;
 157   tre_submatch_data_t *submatch_data;
 158   char *firstpos_chars;
 159   int first_char;
 160   unsigned int num_submatches;
 161   tre_tag_direction_t *tag_directions;
 162   int *minimal_tags;
 163   int num_tags;
 164   int num_minimals;
 165   int end_tag;
 166   int num_states;
 167   int cflags;
 168   int have_backrefs;
 169   int have_approx;
 170 };
 171
 172 /* from tre-mem.h: */
 173
 174 #define TRE_MEM_BLOCK_SIZE 1024
 175
 176 typedef struct tre_list {
 177   void *data;
 178   struct tre_list *next;
 179 } tre_list_t;
 180
 181 typedef struct tre_mem_struct {
 182   tre_list_t *blocks;
 183   tre_list_t *current;
 184   char *ptr;
 185   size_t n;
 186   int failed;
 187   void **provided;
 188 } *tre_mem_t;
 189
 190 #define tre_mem_new_impl   __tre_mem_new_impl
 191 #define tre_mem_alloc_impl __tre_mem_alloc_impl
 192 #define tre_mem_destroy    __tre_mem_destroy
 193
 194 tre_mem_t tre_mem_new_impl(int provided, void *provided_block);
 195 void *tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block,
 196                          int zero, size_t size);
 197
 198 /* Returns a new memory allocator or NULL if out of memory. */
 199 #define tre_mem_new()  tre_mem_new_impl(0, NULL)
 200
 201 /* Allocates a block of `size' bytes from `mem'.  Returns a pointer to the
 202    allocated block or NULL if an underlying malloc() failed. */
 203 #define tre_mem_alloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 0, size)
 204
 205 /* Allocates a block of `size' bytes from `mem'.  Returns a pointer to the
 206    allocated block or NULL if an underlying malloc() failed.  The memory
 207    is set to zero. */
 208 #define tre_mem_calloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 1, size)
 209
 210 #ifdef TRE_USE_ALLOCA
 211 /* alloca() versions.  Like above, but memory is allocated with alloca()
 212    instead of malloc(). */
 213
 214 #define tre_mem_newa() \
 215   tre_mem_new_impl(1, alloca(sizeof(struct tre_mem_struct)))
 216
 217 #define tre_mem_alloca(mem, size)                                             \
 218   ((mem)->n >= (size)                                                         \
 219    ? tre_mem_alloc_impl((mem), 1, NULL, 0, (size))                            \
 220    : tre_mem_alloc_impl((mem), 1, alloca(TRE_MEM_BLOCK_SIZE), 0, (size)))
 221 #endif /* TRE_USE_ALLOCA */
 222
 223
 224 /* Frees the memory allocator and all memory allocated with it. */
 225 void tre_mem_destroy(tre_mem_t mem);
 226
 227 #define xmalloc malloc
 228 #define xcalloc calloc
 229 #define xfree free
 230 #define xrealloc realloc
 231