| 1 |
/* |
| 2 |
regexec.c - TRE POSIX compatible matching functions (and more). |
| 3 |
|
| 4 |
Copyright (c) 2001-2009 Ville Laurikari <[email protected]> |
| 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 <stdlib.h> |
| 33 |
#include <string.h> |
| 34 |
#include <wchar.h> |
| 35 |
#include <wctype.h> |
| 36 |
#include <limits.h> |
| 37 |
#include <stdint.h> |
| 38 |
|
| 39 |
#include <regex.h> |
| 40 |
|
| 41 |
#include "tre.h" |
| 42 |
|
| 43 |
#include <assert.h> |
| 44 |
|
| 45 |
static void |
| 46 |
tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, |
| 47 |
const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo); |
| 48 |
|
| 49 |
/*********************************************************************** |
| 50 |
from tre-match-utils.h |
| 51 |
***********************************************************************/ |
| 52 |
|
| 53 |
#define GET_NEXT_WCHAR() do { \ |
| 54 |
prev_c = next_c; pos += pos_add_next; \ |
| 55 |
if ((pos_add_next = mbtowc(&next_c, str_byte, MB_LEN_MAX)) <= 0) { \ |
| 56 |
if (pos_add_next < 0) { ret = REG_NOMATCH; goto error_exit; } \ |
| 57 |
else pos_add_next++; \ |
| 58 |
} \ |
| 59 |
str_byte += pos_add_next; \ |
| 60 |
} while (0) |
| 61 |
|
| 62 |
#define IS_WORD_CHAR(c) ((c) == L'_' || tre_isalnum(c)) |
| 63 |
|
| 64 |
#define CHECK_ASSERTIONS(assertions) \ |
| 65 |
(((assertions & ASSERT_AT_BOL) \ |
| 66 |
&& (pos > 0 || reg_notbol) \ |
| 67 |
&& (prev_c != L'\n' || !reg_newline)) \ |
| 68 |
|| ((assertions & ASSERT_AT_EOL) \ |
| 69 |
&& (next_c != L'\0' || reg_noteol) \ |
| 70 |
&& (next_c != L'\n' || !reg_newline)) \ |
| 71 |
|| ((assertions & ASSERT_AT_BOW) \ |
| 72 |
&& (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c))) \ |
| 73 |
|| ((assertions & ASSERT_AT_EOW) \ |
| 74 |
&& (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c))) \ |
| 75 |
|| ((assertions & ASSERT_AT_WB) \ |
| 76 |
&& (pos != 0 && next_c != L'\0' \ |
| 77 |
&& IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c))) \ |
| 78 |
|| ((assertions & ASSERT_AT_WB_NEG) \ |
| 79 |
&& (pos == 0 || next_c == L'\0' \ |
| 80 |
|| IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c)))) |
| 81 |
|
| 82 |
#define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags) \ |
| 83 |
(((trans_i->assertions & ASSERT_CHAR_CLASS) \ |
| 84 |
&& !(tnfa->cflags & REG_ICASE) \ |
| 85 |
&& !tre_isctype((tre_cint_t)prev_c, trans_i->u.class)) \ |
| 86 |
|| ((trans_i->assertions & ASSERT_CHAR_CLASS) \ |
| 87 |
&& (tnfa->cflags & REG_ICASE) \ |
| 88 |
&& !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class) \ |
| 89 |
&& !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class)) \ |
| 90 |
|| ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG) \ |
| 91 |
&& tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\ |
| 92 |
tnfa->cflags & REG_ICASE))) |
| 93 |
|
| 94 |
|
| 95 |
|
| 96 |
|
| 97 |
/* Returns 1 if `t1' wins `t2', 0 otherwise. */ |
| 98 |
static int |
| 99 |
tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions, |
| 100 |
regoff_t *t1, regoff_t *t2) |
| 101 |
{ |
| 102 |
int i; |
| 103 |
for (i = 0; i < num_tags; i++) |
| 104 |
{ |
| 105 |
if (tag_directions[i] == TRE_TAG_MINIMIZE) |
| 106 |
{ |
| 107 |
if (t1[i] < t2[i]) |
| 108 |
return 1; |
| 109 |
if (t1[i] > t2[i]) |
| 110 |
return 0; |
| 111 |
} |
| 112 |
else |
| 113 |
{ |
| 114 |
if (t1[i] > t2[i]) |
| 115 |
return 1; |
| 116 |
if (t1[i] < t2[i]) |
| 117 |
return 0; |
| 118 |
} |
| 119 |
} |
| 120 |
/* assert(0);*/ |
| 121 |
return 0; |
| 122 |
} |
| 123 |
|
| 124 |
static int |
| 125 |
tre_neg_char_classes_match(tre_ctype_t *classes, tre_cint_t wc, int icase) |
| 126 |
{ |
| 127 |
while (*classes != (tre_ctype_t)0) |
| 128 |
if ((!icase && tre_isctype(wc, *classes)) |
| 129 |
|| (icase && (tre_isctype(tre_toupper(wc), *classes) |
| 130 |
|| tre_isctype(tre_tolower(wc), *classes)))) |
| 131 |
return 1; /* Match. */ |
| 132 |
else |
| 133 |
classes++; |
| 134 |
return 0; /* No match. */ |
| 135 |
} |
| 136 |
|
| 137 |
|
| 138 |
/*********************************************************************** |
| 139 |
from tre-match-parallel.c |
| 140 |
***********************************************************************/ |
| 141 |
|
| 142 |
/* |
| 143 |
This algorithm searches for matches basically by reading characters |
| 144 |
in the searched string one by one, starting at the beginning. All |
| 145 |
matching paths in the TNFA are traversed in parallel. When two or |
| 146 |
more paths reach the same state, exactly one is chosen according to |
| 147 |
tag ordering rules; if returning submatches is not required it does |
| 148 |
not matter which path is chosen. |
| 149 |
|
| 150 |
The worst case time required for finding the leftmost and longest |
| 151 |
match, or determining that there is no match, is always linearly |
| 152 |
dependent on the length of the text being searched. |
| 153 |
|
| 154 |
This algorithm cannot handle TNFAs with back referencing nodes. |
| 155 |
See `tre-match-backtrack.c'. |
| 156 |
*/ |
| 157 |
|
| 158 |
typedef struct { |
| 159 |
tre_tnfa_transition_t *state; |
| 160 |
regoff_t *tags; |
| 161 |
} tre_tnfa_reach_t; |
| 162 |
|
| 163 |
typedef struct { |
| 164 |
regoff_t pos; |
| 165 |
regoff_t **tags; |
| 166 |
} tre_reach_pos_t; |
| 167 |
|
| 168 |
|
| 169 |
static reg_errcode_t |
| 170 |
tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string, |
| 171 |
regoff_t *match_tags, int eflags, |
| 172 |
regoff_t *match_end_ofs) |
| 173 |
{ |
| 174 |
/* State variables required by GET_NEXT_WCHAR. */ |
| 175 |
tre_char_t prev_c = 0, next_c = 0; |
| 176 |
const char *str_byte = string; |
| 177 |
regoff_t pos = -1; |
| 178 |
regoff_t pos_add_next = 1; |
| 179 |
#ifdef TRE_MBSTATE |
| 180 |
mbstate_t mbstate; |
| 181 |
#endif /* TRE_MBSTATE */ |
| 182 |
int reg_notbol = eflags & REG_NOTBOL; |
| 183 |
int reg_noteol = eflags & REG_NOTEOL; |
| 184 |
int reg_newline = tnfa->cflags & REG_NEWLINE; |
| 185 |
reg_errcode_t ret; |
| 186 |
|
| 187 |
char *buf; |
| 188 |
tre_tnfa_transition_t *trans_i; |
| 189 |
tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i; |
| 190 |
tre_reach_pos_t *reach_pos; |
| 191 |
int *tag_i; |
| 192 |
int num_tags, i; |
| 193 |
|
| 194 |
regoff_t match_eo = -1; /* end offset of match (-1 if no match found yet) */ |
| 195 |
int new_match = 0; |
| 196 |
regoff_t *tmp_tags = NULL; |
| 197 |
regoff_t *tmp_iptr; |
| 198 |
|
| 199 |
#ifdef TRE_MBSTATE |
| 200 |
memset(&mbstate, '\0', sizeof(mbstate)); |
| 201 |
#endif /* TRE_MBSTATE */ |
| 202 |
|
| 203 |
if (!match_tags) |
| 204 |
num_tags = 0; |
| 205 |
else |
| 206 |
num_tags = tnfa->num_tags; |
| 207 |
|
| 208 |
/* Allocate memory for temporary data required for matching. This needs to |
| 209 |
be done for every matching operation to be thread safe. This allocates |
| 210 |
everything in a single large block with calloc(). */ |
| 211 |
{ |
| 212 |
size_t tbytes, rbytes, pbytes, xbytes, total_bytes; |
| 213 |
char *tmp_buf; |
| 214 |
|
| 215 |
/* Ensure that tbytes and xbytes*num_states cannot overflow, and that |
| 216 |
* they don't contribute more than 1/8 of SIZE_MAX to total_bytes. */ |
| 217 |
if (num_tags > SIZE_MAX/(8 * sizeof(regoff_t) * tnfa->num_states)) |
| 218 |
return REG_ESPACE; |
| 219 |
|
| 220 |
/* Likewise check rbytes. */ |
| 221 |
if (tnfa->num_states+1 > SIZE_MAX/(8 * sizeof(*reach_next))) |
| 222 |
return REG_ESPACE; |
| 223 |
|
| 224 |
/* Likewise check pbytes. */ |
| 225 |
if (tnfa->num_states > SIZE_MAX/(8 * sizeof(*reach_pos))) |
| 226 |
return REG_ESPACE; |
| 227 |
|
| 228 |
/* Compute the length of the block we need. */ |
| 229 |
tbytes = sizeof(*tmp_tags) * num_tags; |
| 230 |
rbytes = sizeof(*reach_next) * (tnfa->num_states + 1); |
| 231 |
pbytes = sizeof(*reach_pos) * tnfa->num_states; |
| 232 |
xbytes = sizeof(regoff_t) * num_tags; |
| 233 |
total_bytes = |
| 234 |
(sizeof(long) - 1) * 4 /* for alignment paddings */ |
| 235 |
+ (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes; |
| 236 |
|
| 237 |
/* Allocate the memory. */ |
| 238 |
buf = calloc(total_bytes, 1); |
| 239 |
if (buf == NULL) |
| 240 |
return REG_ESPACE; |
| 241 |
|
| 242 |
/* Get the various pointers within tmp_buf (properly aligned). */ |
| 243 |
tmp_tags = (void *)buf; |
| 244 |
tmp_buf = buf + tbytes; |
| 245 |
tmp_buf += ALIGN(tmp_buf, long); |
| 246 |
reach_next = (void *)tmp_buf; |
| 247 |
tmp_buf += rbytes; |
| 248 |
tmp_buf += ALIGN(tmp_buf, long); |
| 249 |
reach = (void *)tmp_buf; |
| 250 |
tmp_buf += rbytes; |
| 251 |
tmp_buf += ALIGN(tmp_buf, long); |
| 252 |
reach_pos = (void *)tmp_buf; |
| 253 |
tmp_buf += pbytes; |
| 254 |
tmp_buf += ALIGN(tmp_buf, long); |
| 255 |
for (i = 0; i < tnfa->num_states; i++) |
| 256 |
{ |
| 257 |
reach[i].tags = (void *)tmp_buf; |
| 258 |
tmp_buf += xbytes; |
| 259 |
reach_next[i].tags = (void *)tmp_buf; |
| 260 |
tmp_buf += xbytes; |
| 261 |
} |
| 262 |
} |
| 263 |
|
| 264 |
for (i = 0; i < tnfa->num_states; i++) |
| 265 |
reach_pos[i].pos = -1; |
| 266 |
|
| 267 |
GET_NEXT_WCHAR(); |
| 268 |
pos = 0; |
| 269 |
|
| 270 |
reach_next_i = reach_next; |
| 271 |
while (1) |
| 272 |
{ |
| 273 |
/* If no match found yet, add the initial states to `reach_next'. */ |
| 274 |
if (match_eo < 0) |
| 275 |
{ |
| 276 |
trans_i = tnfa->initial; |
| 277 |
while (trans_i->state != NULL) |
| 278 |
{ |
| 279 |
if (reach_pos[trans_i->state_id].pos < pos) |
| 280 |
{ |
| 281 |
if (trans_i->assertions |
| 282 |
&& CHECK_ASSERTIONS(trans_i->assertions)) |
| 283 |
{ |
| 284 |
trans_i++; |
| 285 |
continue; |
| 286 |
} |
| 287 |
|
| 288 |
reach_next_i->state = trans_i->state; |
| 289 |
for (i = 0; i < num_tags; i++) |
| 290 |
reach_next_i->tags[i] = -1; |
| 291 |
tag_i = trans_i->tags; |
| 292 |
if (tag_i) |
| 293 |
while (*tag_i >= 0) |
| 294 |
{ |
| 295 |
if (*tag_i < num_tags) |
| 296 |
reach_next_i->tags[*tag_i] = pos; |
| 297 |
tag_i++; |
| 298 |
} |
| 299 |
if (reach_next_i->state == tnfa->final) |
| 300 |
{ |
| 301 |
match_eo = pos; |
| 302 |
new_match = 1; |
| 303 |
for (i = 0; i < num_tags; i++) |
| 304 |
match_tags[i] = reach_next_i->tags[i]; |
| 305 |
} |
| 306 |
reach_pos[trans_i->state_id].pos = pos; |
| 307 |
reach_pos[trans_i->state_id].tags = &reach_next_i->tags; |
| 308 |
reach_next_i++; |
| 309 |
} |
| 310 |
trans_i++; |
| 311 |
} |
| 312 |
reach_next_i->state = NULL; |
| 313 |
} |
| 314 |
else |
| 315 |
{ |
| 316 |
if (num_tags == 0 || reach_next_i == reach_next) |
| 317 |
/* We have found a match. */ |
| 318 |
break; |
| 319 |
} |
| 320 |
|
| 321 |
/* Check for end of string. */ |
| 322 |
if (!next_c) break; |
| 323 |
|
| 324 |
GET_NEXT_WCHAR(); |
| 325 |
|
| 326 |
/* Swap `reach' and `reach_next'. */ |
| 327 |
reach_i = reach; |
| 328 |
reach = reach_next; |
| 329 |
reach_next = reach_i; |
| 330 |
|
| 331 |
/* For each state in `reach', weed out states that don't fulfill the |
| 332 |
minimal matching conditions. */ |
| 333 |
if (tnfa->num_minimals && new_match) |
| 334 |
{ |
| 335 |
new_match = 0; |
| 336 |
reach_next_i = reach_next; |
| 337 |
for (reach_i = reach; reach_i->state; reach_i++) |
| 338 |
{ |
| 339 |
int skip = 0; |
| 340 |
for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) |
| 341 |
{ |
| 342 |
int end = tnfa->minimal_tags[i]; |
| 343 |
int start = tnfa->minimal_tags[i + 1]; |
| 344 |
if (end >= num_tags) |
| 345 |
{ |
| 346 |
skip = 1; |
| 347 |
break; |
| 348 |
} |
| 349 |
else if (reach_i->tags[start] == match_tags[start] |
| 350 |
&& reach_i->tags[end] < match_tags[end]) |
| 351 |
{ |
| 352 |
skip = 1; |
| 353 |
break; |
| 354 |
} |
| 355 |
} |
| 356 |
if (!skip) |
| 357 |
{ |
| 358 |
reach_next_i->state = reach_i->state; |
| 359 |
tmp_iptr = reach_next_i->tags; |
| 360 |
reach_next_i->tags = reach_i->tags; |
| 361 |
reach_i->tags = tmp_iptr; |
| 362 |
reach_next_i++; |
| 363 |
} |
| 364 |
} |
| 365 |
reach_next_i->state = NULL; |
| 366 |
|
| 367 |
/* Swap `reach' and `reach_next'. */ |
| 368 |
reach_i = reach; |
| 369 |
reach = reach_next; |
| 370 |
reach_next = reach_i; |
| 371 |
} |
| 372 |
|
| 373 |
/* For each state in `reach' see if there is a transition leaving with |
| 374 |
the current input symbol to a state not yet in `reach_next', and |
| 375 |
add the destination states to `reach_next'. */ |
| 376 |
reach_next_i = reach_next; |
| 377 |
for (reach_i = reach; reach_i->state; reach_i++) |
| 378 |
{ |
| 379 |
for (trans_i = reach_i->state; trans_i->state; trans_i++) |
| 380 |
{ |
| 381 |
/* Does this transition match the input symbol? */ |
| 382 |
if (trans_i->code_min <= (tre_cint_t)prev_c && |
| 383 |
trans_i->code_max >= (tre_cint_t)prev_c) |
| 384 |
{ |
| 385 |
if (trans_i->assertions |
| 386 |
&& (CHECK_ASSERTIONS(trans_i->assertions) |
| 387 |
|| CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) |
| 388 |
{ |
| 389 |
continue; |
| 390 |
} |
| 391 |
|
| 392 |
/* Compute the tags after this transition. */ |
| 393 |
for (i = 0; i < num_tags; i++) |
| 394 |
tmp_tags[i] = reach_i->tags[i]; |
| 395 |
tag_i = trans_i->tags; |
| 396 |
if (tag_i != NULL) |
| 397 |
while (*tag_i >= 0) |
| 398 |
{ |
| 399 |
if (*tag_i < num_tags) |
| 400 |
tmp_tags[*tag_i] = pos; |
| 401 |
tag_i++; |
| 402 |
} |
| 403 |
|
| 404 |
if (reach_pos[trans_i->state_id].pos < pos) |
| 405 |
{ |
| 406 |
/* Found an unvisited node. */ |
| 407 |
reach_next_i->state = trans_i->state; |
| 408 |
tmp_iptr = reach_next_i->tags; |
| 409 |
reach_next_i->tags = tmp_tags; |
| 410 |
tmp_tags = tmp_iptr; |
| 411 |
reach_pos[trans_i->state_id].pos = pos; |
| 412 |
reach_pos[trans_i->state_id].tags = &reach_next_i->tags; |
| 413 |
|
| 414 |
if (reach_next_i->state == tnfa->final |
| 415 |
&& (match_eo == -1 |
| 416 |
|| (num_tags > 0 |
| 417 |
&& reach_next_i->tags[0] <= match_tags[0]))) |
| 418 |
{ |
| 419 |
match_eo = pos; |
| 420 |
new_match = 1; |
| 421 |
for (i = 0; i < num_tags; i++) |
| 422 |
match_tags[i] = reach_next_i->tags[i]; |
| 423 |
} |
| 424 |
reach_next_i++; |
| 425 |
|
| 426 |
} |
| 427 |
else |
| 428 |
{ |
| 429 |
assert(reach_pos[trans_i->state_id].pos == pos); |
| 430 |
/* Another path has also reached this state. We choose |
| 431 |
the winner by examining the tag values for both |
| 432 |
paths. */ |
| 433 |
if (tre_tag_order(num_tags, tnfa->tag_directions, |
| 434 |
tmp_tags, |
| 435 |
*reach_pos[trans_i->state_id].tags)) |
| 436 |
{ |
| 437 |
/* The new path wins. */ |
| 438 |
tmp_iptr = *reach_pos[trans_i->state_id].tags; |
| 439 |
*reach_pos[trans_i->state_id].tags = tmp_tags; |
| 440 |
if (trans_i->state == tnfa->final) |
| 441 |
{ |
| 442 |
match_eo = pos; |
| 443 |
new_match = 1; |
| 444 |
for (i = 0; i < num_tags; i++) |
| 445 |
match_tags[i] = tmp_tags[i]; |
| 446 |
} |
| 447 |
tmp_tags = tmp_iptr; |
| 448 |
} |
| 449 |
} |
| 450 |
} |
| 451 |
} |
| 452 |
} |
| 453 |
reach_next_i->state = NULL; |
| 454 |
} |
| 455 |
|
| 456 |
*match_end_ofs = match_eo; |
| 457 |
ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; |
| 458 |
error_exit: |
| 459 |
xfree(buf); |
| 460 |
return ret; |
| 461 |
} |
| 462 |
|
| 463 |
|
| 464 |
|
| 465 |
/*********************************************************************** |
| 466 |
from tre-match-backtrack.c |
| 467 |
***********************************************************************/ |
| 468 |
|
| 469 |
/* |
| 470 |
This matcher is for regexps that use back referencing. Regexp matching |
| 471 |
with back referencing is an NP-complete problem on the number of back |
| 472 |
references. The easiest way to match them is to use a backtracking |
| 473 |
routine which basically goes through all possible paths in the TNFA |
| 474 |
and chooses the one which results in the best (leftmost and longest) |
| 475 |
match. This can be spectacularly expensive and may run out of stack |
| 476 |
space, but there really is no better known generic algorithm. Quoting |
| 477 |
Henry Spencer from comp.compilers: |
| 478 |
<URL: http://compilers.iecc.com/comparch/article/93-03-102> |
| 479 |
|
| 480 |
POSIX.2 REs require longest match, which is really exciting to |
| 481 |
implement since the obsolete ("basic") variant also includes |
| 482 |
\<digit>. I haven't found a better way of tackling this than doing |
| 483 |
a preliminary match using a DFA (or simulation) on a modified RE |
| 484 |
that just replicates subREs for \<digit>, and then doing a |
| 485 |
backtracking match to determine whether the subRE matches were |
| 486 |
right. This can be rather slow, but I console myself with the |
| 487 |
thought that people who use \<digit> deserve very slow execution. |
| 488 |
(Pun unintentional but very appropriate.) |
| 489 |
|
| 490 |
*/ |
| 491 |
|
| 492 |
typedef struct { |
| 493 |
regoff_t pos; |
| 494 |
const char *str_byte; |
| 495 |
tre_tnfa_transition_t *state; |
| 496 |
int state_id; |
| 497 |
int next_c; |
| 498 |
regoff_t *tags; |
| 499 |
#ifdef TRE_MBSTATE |
| 500 |
mbstate_t mbstate; |
| 501 |
#endif /* TRE_MBSTATE */ |
| 502 |
} tre_backtrack_item_t; |
| 503 |
|
| 504 |
typedef struct tre_backtrack_struct { |
| 505 |
tre_backtrack_item_t item; |
| 506 |
struct tre_backtrack_struct *prev; |
| 507 |
struct tre_backtrack_struct *next; |
| 508 |
} *tre_backtrack_t; |
| 509 |
|
| 510 |
#ifdef TRE_MBSTATE |
| 511 |
#define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate) |
| 512 |
#define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate |
| 513 |
#else /* !TRE_MBSTATE */ |
| 514 |
#define BT_STACK_MBSTATE_IN |
| 515 |
#define BT_STACK_MBSTATE_OUT |
| 516 |
#endif /* !TRE_MBSTATE */ |
| 517 |
|
| 518 |
#define tre_bt_mem_new tre_mem_new |
| 519 |
#define tre_bt_mem_alloc tre_mem_alloc |
| 520 |
#define tre_bt_mem_destroy tre_mem_destroy |
| 521 |
|
| 522 |
|
| 523 |
#define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \ |
| 524 |
do \ |
| 525 |
{ \ |
| 526 |
int i; \ |
| 527 |
if (!stack->next) \ |
| 528 |
{ \ |
| 529 |
tre_backtrack_t s; \ |
| 530 |
s = tre_bt_mem_alloc(mem, sizeof(*s)); \ |
| 531 |
if (!s) \ |
| 532 |
{ \ |
| 533 |
tre_bt_mem_destroy(mem); \ |
| 534 |
if (tags) \ |
| 535 |
xfree(tags); \ |
| 536 |
if (pmatch) \ |
| 537 |
xfree(pmatch); \ |
| 538 |
if (states_seen) \ |
| 539 |
xfree(states_seen); \ |
| 540 |
return REG_ESPACE; \ |
| 541 |
} \ |
| 542 |
s->prev = stack; \ |
| 543 |
s->next = NULL; \ |
| 544 |
s->item.tags = tre_bt_mem_alloc(mem, \ |
| 545 |
sizeof(*tags) * tnfa->num_tags); \ |
| 546 |
if (!s->item.tags) \ |
| 547 |
{ \ |
| 548 |
tre_bt_mem_destroy(mem); \ |
| 549 |
if (tags) \ |
| 550 |
xfree(tags); \ |
| 551 |
if (pmatch) \ |
| 552 |
xfree(pmatch); \ |
| 553 |
if (states_seen) \ |
| 554 |
xfree(states_seen); \ |
| 555 |
return REG_ESPACE; \ |
| 556 |
} \ |
| 557 |
stack->next = s; \ |
| 558 |
stack = s; \ |
| 559 |
} \ |
| 560 |
else \ |
| 561 |
stack = stack->next; \ |
| 562 |
stack->item.pos = (_pos); \ |
| 563 |
stack->item.str_byte = (_str_byte); \ |
| 564 |
stack->item.state = (_state); \ |
| 565 |
stack->item.state_id = (_state_id); \ |
| 566 |
stack->item.next_c = (_next_c); \ |
| 567 |
for (i = 0; i < tnfa->num_tags; i++) \ |
| 568 |
stack->item.tags[i] = (_tags)[i]; \ |
| 569 |
BT_STACK_MBSTATE_IN; \ |
| 570 |
} \ |
| 571 |
while (0) |
| 572 |
|
| 573 |
#define BT_STACK_POP() \ |
| 574 |
do \ |
| 575 |
{ \ |
| 576 |
int i; \ |
| 577 |
assert(stack->prev); \ |
| 578 |
pos = stack->item.pos; \ |
| 579 |
str_byte = stack->item.str_byte; \ |
| 580 |
state = stack->item.state; \ |
| 581 |
next_c = stack->item.next_c; \ |
| 582 |
for (i = 0; i < tnfa->num_tags; i++) \ |
| 583 |
tags[i] = stack->item.tags[i]; \ |
| 584 |
BT_STACK_MBSTATE_OUT; \ |
| 585 |
stack = stack->prev; \ |
| 586 |
} \ |
| 587 |
while (0) |
| 588 |
|
| 589 |
#undef MIN |
| 590 |
#define MIN(a, b) ((a) <= (b) ? (a) : (b)) |
| 591 |
|
| 592 |
static reg_errcode_t |
| 593 |
tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, |
| 594 |
regoff_t *match_tags, int eflags, regoff_t *match_end_ofs) |
| 595 |
{ |
| 596 |
/* State variables required by GET_NEXT_WCHAR. */ |
| 597 |
tre_char_t prev_c = 0, next_c = 0; |
| 598 |
const char *str_byte = string; |
| 599 |
regoff_t pos = 0; |
| 600 |
regoff_t pos_add_next = 1; |
| 601 |
#ifdef TRE_MBSTATE |
| 602 |
mbstate_t mbstate; |
| 603 |
#endif /* TRE_MBSTATE */ |
| 604 |
int reg_notbol = eflags & REG_NOTBOL; |
| 605 |
int reg_noteol = eflags & REG_NOTEOL; |
| 606 |
int reg_newline = tnfa->cflags & REG_NEWLINE; |
| 607 |
|
| 608 |
/* These are used to remember the necessary values of the above |
| 609 |
variables to return to the position where the current search |
| 610 |
started from. */ |
| 611 |
int next_c_start; |
| 612 |
const char *str_byte_start; |
| 613 |
regoff_t pos_start = -1; |
| 614 |
#ifdef TRE_MBSTATE |
| 615 |
mbstate_t mbstate_start; |
| 616 |
#endif /* TRE_MBSTATE */ |
| 617 |
|
| 618 |
/* End offset of best match so far, or -1 if no match found yet. */ |
| 619 |
regoff_t match_eo = -1; |
| 620 |
/* Tag arrays. */ |
| 621 |
int *next_tags; |
| 622 |
regoff_t *tags = NULL; |
| 623 |
/* Current TNFA state. */ |
| 624 |
tre_tnfa_transition_t *state; |
| 625 |
int *states_seen = NULL; |
| 626 |
|
| 627 |
/* Memory allocator to for allocating the backtracking stack. */ |
| 628 |
tre_mem_t mem = tre_bt_mem_new(); |
| 629 |
|
| 630 |
/* The backtracking stack. */ |
| 631 |
tre_backtrack_t stack; |
| 632 |
|
| 633 |
tre_tnfa_transition_t *trans_i; |
| 634 |
regmatch_t *pmatch = NULL; |
| 635 |
int ret; |
| 636 |
|
| 637 |
#ifdef TRE_MBSTATE |
| 638 |
memset(&mbstate, '\0', sizeof(mbstate)); |
| 639 |
#endif /* TRE_MBSTATE */ |
| 640 |
|
| 641 |
if (!mem) |
| 642 |
return REG_ESPACE; |
| 643 |
stack = tre_bt_mem_alloc(mem, sizeof(*stack)); |
| 644 |
if (!stack) |
| 645 |
{ |
| 646 |
ret = REG_ESPACE; |
| 647 |
goto error_exit; |
| 648 |
} |
| 649 |
stack->prev = NULL; |
| 650 |
stack->next = NULL; |
| 651 |
|
| 652 |
if (tnfa->num_tags) |
| 653 |
{ |
| 654 |
tags = xmalloc(sizeof(*tags) * tnfa->num_tags); |
| 655 |
if (!tags) |
| 656 |
{ |
| 657 |
ret = REG_ESPACE; |
| 658 |
goto error_exit; |
| 659 |
} |
| 660 |
} |
| 661 |
if (tnfa->num_submatches) |
| 662 |
{ |
| 663 |
pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches); |
| 664 |
if (!pmatch) |
| 665 |
{ |
| 666 |
ret = REG_ESPACE; |
| 667 |
goto error_exit; |
| 668 |
} |
| 669 |
} |
| 670 |
if (tnfa->num_states) |
| 671 |
{ |
| 672 |
states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states); |
| 673 |
if (!states_seen) |
| 674 |
{ |
| 675 |
ret = REG_ESPACE; |
| 676 |
goto error_exit; |
| 677 |
} |
| 678 |
} |
| 679 |
|
| 680 |
retry: |
| 681 |
{ |
| 682 |
int i; |
| 683 |
for (i = 0; i < tnfa->num_tags; i++) |
| 684 |
{ |
| 685 |
tags[i] = -1; |
| 686 |
if (match_tags) |
| 687 |
match_tags[i] = -1; |
| 688 |
} |
| 689 |
for (i = 0; i < tnfa->num_states; i++) |
| 690 |
states_seen[i] = 0; |
| 691 |
} |
| 692 |
|
| 693 |
state = NULL; |
| 694 |
pos = pos_start; |
| 695 |
GET_NEXT_WCHAR(); |
| 696 |
pos_start = pos; |
| 697 |
next_c_start = next_c; |
| 698 |
str_byte_start = str_byte; |
| 699 |
#ifdef TRE_MBSTATE |
| 700 |
mbstate_start = mbstate; |
| 701 |
#endif /* TRE_MBSTATE */ |
| 702 |
|
| 703 |
/* Handle initial states. */ |
| 704 |
next_tags = NULL; |
| 705 |
for (trans_i = tnfa->initial; trans_i->state; trans_i++) |
| 706 |
{ |
| 707 |
if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions)) |
| 708 |
{ |
| 709 |
continue; |
| 710 |
} |
| 711 |
if (state == NULL) |
| 712 |
{ |
| 713 |
/* Start from this state. */ |
| 714 |
state = trans_i->state; |
| 715 |
next_tags = trans_i->tags; |
| 716 |
} |
| 717 |
else |
| 718 |
{ |
| 719 |
/* Backtrack to this state. */ |
| 720 |
BT_STACK_PUSH(pos, str_byte, 0, trans_i->state, |
| 721 |
trans_i->state_id, next_c, tags, mbstate); |
| 722 |
{ |
| 723 |
int *tmp = trans_i->tags; |
| 724 |
if (tmp) |
| 725 |
while (*tmp >= 0) |
| 726 |
stack->item.tags[*tmp++] = pos; |
| 727 |
} |
| 728 |
} |
| 729 |
} |
| 730 |
|
| 731 |
if (next_tags) |
| 732 |
for (; *next_tags >= 0; next_tags++) |
| 733 |
tags[*next_tags] = pos; |
| 734 |
|
| 735 |
|
| 736 |
if (state == NULL) |
| 737 |
goto backtrack; |
| 738 |
|
| 739 |
while (1) |
| 740 |
{ |
| 741 |
tre_tnfa_transition_t *next_state; |
| 742 |
int empty_br_match; |
| 743 |
|
| 744 |
if (state == tnfa->final) |
| 745 |
{ |
| 746 |
if (match_eo < pos |
| 747 |
|| (match_eo == pos |
| 748 |
&& match_tags |
| 749 |
&& tre_tag_order(tnfa->num_tags, tnfa->tag_directions, |
| 750 |
tags, match_tags))) |
| 751 |
{ |
| 752 |
int i; |
| 753 |
/* This match wins the previous match. */ |
| 754 |
match_eo = pos; |
| 755 |
if (match_tags) |
| 756 |
for (i = 0; i < tnfa->num_tags; i++) |
| 757 |
match_tags[i] = tags[i]; |
| 758 |
} |
| 759 |
/* Our TNFAs never have transitions leaving from the final state, |
| 760 |
so we jump right to backtracking. */ |
| 761 |
goto backtrack; |
| 762 |
} |
| 763 |
|
| 764 |
/* Go to the next character in the input string. */ |
| 765 |
empty_br_match = 0; |
| 766 |
trans_i = state; |
| 767 |
if (trans_i->state && trans_i->assertions & ASSERT_BACKREF) |
| 768 |
{ |
| 769 |
/* This is a back reference state. All transitions leaving from |
| 770 |
this state have the same back reference "assertion". Instead |
| 771 |
of reading the next character, we match the back reference. */ |
| 772 |
regoff_t so, eo; |
| 773 |
int bt = trans_i->u.backref; |
| 774 |
regoff_t bt_len; |
| 775 |
int result; |
| 776 |
|
| 777 |
/* Get the substring we need to match against. Remember to |
| 778 |
turn off REG_NOSUB temporarily. */ |
| 779 |
tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB, |
| 780 |
tnfa, tags, pos); |
| 781 |
so = pmatch[bt].rm_so; |
| 782 |
eo = pmatch[bt].rm_eo; |
| 783 |
bt_len = eo - so; |
| 784 |
|
| 785 |
result = strncmp((const char*)string + so, str_byte - 1, |
| 786 |
(size_t)bt_len); |
| 787 |
|
| 788 |
if (result == 0) |
| 789 |
{ |
| 790 |
/* Back reference matched. Check for infinite loop. */ |
| 791 |
if (bt_len == 0) |
| 792 |
empty_br_match = 1; |
| 793 |
if (empty_br_match && states_seen[trans_i->state_id]) |
| 794 |
{ |
| 795 |
goto backtrack; |
| 796 |
} |
| 797 |
|
| 798 |
states_seen[trans_i->state_id] = empty_br_match; |
| 799 |
|
| 800 |
/* Advance in input string and resync `prev_c', `next_c' |
| 801 |
and pos. */ |
| 802 |
str_byte += bt_len - 1; |
| 803 |
pos += bt_len - 1; |
| 804 |
GET_NEXT_WCHAR(); |
| 805 |
} |
| 806 |
else |
| 807 |
{ |
| 808 |
goto backtrack; |
| 809 |
} |
| 810 |
} |
| 811 |
else |
| 812 |
{ |
| 813 |
/* Check for end of string. */ |
| 814 |
if (next_c == L'\0') |
| 815 |
goto backtrack; |
| 816 |
|
| 817 |
/* Read the next character. */ |
| 818 |
GET_NEXT_WCHAR(); |
| 819 |
} |
| 820 |
|
| 821 |
next_state = NULL; |
| 822 |
for (trans_i = state; trans_i->state; trans_i++) |
| 823 |
{ |
| 824 |
if (trans_i->code_min <= (tre_cint_t)prev_c |
| 825 |
&& trans_i->code_max >= (tre_cint_t)prev_c) |
| 826 |
{ |
| 827 |
if (trans_i->assertions |
| 828 |
&& (CHECK_ASSERTIONS(trans_i->assertions) |
| 829 |
|| CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) |
| 830 |
{ |
| 831 |
continue; |
| 832 |
} |
| 833 |
|
| 834 |
if (next_state == NULL) |
| 835 |
{ |
| 836 |
/* First matching transition. */ |
| 837 |
next_state = trans_i->state; |
| 838 |
next_tags = trans_i->tags; |
| 839 |
} |
| 840 |
else |
| 841 |
{ |
| 842 |
/* Second matching transition. We may need to backtrack here |
| 843 |
to take this transition instead of the first one, so we |
| 844 |
push this transition in the backtracking stack so we can |
| 845 |
jump back here if needed. */ |
| 846 |
BT_STACK_PUSH(pos, str_byte, 0, trans_i->state, |
| 847 |
trans_i->state_id, next_c, tags, mbstate); |
| 848 |
{ |
| 849 |
int *tmp; |
| 850 |
for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++) |
| 851 |
stack->item.tags[*tmp] = pos; |
| 852 |
} |
| 853 |
#if 0 /* XXX - it's important not to look at all transitions here to keep |
| 854 |
the stack small! */ |
| 855 |
break; |
| 856 |
#endif |
| 857 |
} |
| 858 |
} |
| 859 |
} |
| 860 |
|
| 861 |
if (next_state != NULL) |
| 862 |
{ |
| 863 |
/* Matching transitions were found. Take the first one. */ |
| 864 |
state = next_state; |
| 865 |
|
| 866 |
/* Update the tag values. */ |
| 867 |
if (next_tags) |
| 868 |
while (*next_tags >= 0) |
| 869 |
tags[*next_tags++] = pos; |
| 870 |
} |
| 871 |
else |
| 872 |
{ |
| 873 |
backtrack: |
| 874 |
/* A matching transition was not found. Try to backtrack. */ |
| 875 |
if (stack->prev) |
| 876 |
{ |
| 877 |
if (stack->item.state->assertions & ASSERT_BACKREF) |
| 878 |
{ |
| 879 |
states_seen[stack->item.state_id] = 0; |
| 880 |
} |
| 881 |
|
| 882 |
BT_STACK_POP(); |
| 883 |
} |
| 884 |
else if (match_eo < 0) |
| 885 |
{ |
| 886 |
/* Try starting from a later position in the input string. */ |
| 887 |
/* Check for end of string. */ |
| 888 |
if (next_c == L'\0') |
| 889 |
{ |
| 890 |
break; |
| 891 |
} |
| 892 |
next_c = next_c_start; |
| 893 |
#ifdef TRE_MBSTATE |
| 894 |
mbstate = mbstate_start; |
| 895 |
#endif /* TRE_MBSTATE */ |
| 896 |
str_byte = str_byte_start; |
| 897 |
goto retry; |
| 898 |
} |
| 899 |
else |
| 900 |
{ |
| 901 |
break; |
| 902 |
} |
| 903 |
} |
| 904 |
} |
| 905 |
|
| 906 |
ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; |
| 907 |
*match_end_ofs = match_eo; |
| 908 |
|
| 909 |
error_exit: |
| 910 |
tre_bt_mem_destroy(mem); |
| 911 |
#ifndef TRE_USE_ALLOCA |
| 912 |
if (tags) |
| 913 |
xfree(tags); |
| 914 |
if (pmatch) |
| 915 |
xfree(pmatch); |
| 916 |
if (states_seen) |
| 917 |
xfree(states_seen); |
| 918 |
#endif /* !TRE_USE_ALLOCA */ |
| 919 |
|
| 920 |
return ret; |
| 921 |
} |
| 922 |
|
| 923 |
/*********************************************************************** |
| 924 |
from regexec.c |
| 925 |
***********************************************************************/ |
| 926 |
|
| 927 |
/* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match |
| 928 |
endpoint values. */ |
| 929 |
static void |
| 930 |
tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, |
| 931 |
const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo) |
| 932 |
{ |
| 933 |
tre_submatch_data_t *submatch_data; |
| 934 |
unsigned int i, j; |
| 935 |
int *parents; |
| 936 |
|
| 937 |
i = 0; |
| 938 |
if (match_eo >= 0 && !(cflags & REG_NOSUB)) |
| 939 |
{ |
| 940 |
/* Construct submatch offsets from the tags. */ |
| 941 |
submatch_data = tnfa->submatch_data; |
| 942 |
while (i < tnfa->num_submatches && i < nmatch) |
| 943 |
{ |
| 944 |
if (submatch_data[i].so_tag == tnfa->end_tag) |
| 945 |
pmatch[i].rm_so = match_eo; |
| 946 |
else |
| 947 |
pmatch[i].rm_so = tags[submatch_data[i].so_tag]; |
| 948 |
|
| 949 |
if (submatch_data[i].eo_tag == tnfa->end_tag) |
| 950 |
pmatch[i].rm_eo = match_eo; |
| 951 |
else |
| 952 |
pmatch[i].rm_eo = tags[submatch_data[i].eo_tag]; |
| 953 |
|
| 954 |
/* If either of the endpoints were not used, this submatch |
| 955 |
was not part of the match. */ |
| 956 |
if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1) |
| 957 |
pmatch[i].rm_so = pmatch[i].rm_eo = -1; |
| 958 |
|
| 959 |
i++; |
| 960 |
} |
| 961 |
/* Reset all submatches that are not within all of their parent |
| 962 |
submatches. */ |
| 963 |
i = 0; |
| 964 |
while (i < tnfa->num_submatches && i < nmatch) |
| 965 |
{ |
| 966 |
if (pmatch[i].rm_eo == -1) |
| 967 |
assert(pmatch[i].rm_so == -1); |
| 968 |
assert(pmatch[i].rm_so <= pmatch[i].rm_eo); |
| 969 |
|
| 970 |
parents = submatch_data[i].parents; |
| 971 |
if (parents != NULL) |
| 972 |
for (j = 0; parents[j] >= 0; j++) |
| 973 |
{ |
| 974 |
if (pmatch[i].rm_so < pmatch[parents[j]].rm_so |
| 975 |
|| pmatch[i].rm_eo > pmatch[parents[j]].rm_eo) |
| 976 |
pmatch[i].rm_so = pmatch[i].rm_eo = -1; |
| 977 |
} |
| 978 |
i++; |
| 979 |
} |
| 980 |
} |
| 981 |
|
| 982 |
while (i < nmatch) |
| 983 |
{ |
| 984 |
pmatch[i].rm_so = -1; |
| 985 |
pmatch[i].rm_eo = -1; |
| 986 |
i++; |
| 987 |
} |
| 988 |
} |
| 989 |
|
| 990 |
|
| 991 |
/* |
| 992 |
Wrapper functions for POSIX compatible regexp matching. |
| 993 |
*/ |
| 994 |
|
| 995 |
int |
| 996 |
regexec(const regex_t *restrict preg, const char *restrict string, |
| 997 |
size_t nmatch, regmatch_t pmatch[restrict], int eflags) |
| 998 |
{ |
| 999 |
tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; |
| 1000 |
reg_errcode_t status; |
| 1001 |
regoff_t *tags = NULL, eo; |
| 1002 |
if (tnfa->cflags & REG_NOSUB) nmatch = 0; |
| 1003 |
if (tnfa->num_tags > 0 && nmatch > 0) |
| 1004 |
{ |
| 1005 |
tags = xmalloc(sizeof(*tags) * tnfa->num_tags); |
| 1006 |
if (tags == NULL) |
| 1007 |
return REG_ESPACE; |
| 1008 |
} |
| 1009 |
|
| 1010 |
/* Dispatch to the appropriate matcher. */ |
| 1011 |
if (tnfa->have_backrefs) |
| 1012 |
{ |
| 1013 |
/* The regex has back references, use the backtracking matcher. */ |
| 1014 |
status = tre_tnfa_run_backtrack(tnfa, string, tags, eflags, &eo); |
| 1015 |
} |
| 1016 |
else |
| 1017 |
{ |
| 1018 |
/* Exact matching, no back references, use the parallel matcher. */ |
| 1019 |
status = tre_tnfa_run_parallel(tnfa, string, tags, eflags, &eo); |
| 1020 |
} |
| 1021 |
|
| 1022 |
if (status == REG_OK) |
| 1023 |
/* A match was found, so fill the submatch registers. */ |
| 1024 |
tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo); |
| 1025 |
if (tags) |
| 1026 |
xfree(tags); |
| 1027 |
return status; |
| 1028 |
} |