regex_src/regexJIT.c

   1 /*
   2  *    Stack-less Just-In-Time compiler
   3  *
   4  *    Copyright Zoltan Herczeg (hzmester@freemail.hu). All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without modification, are
   7  * permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright notice, this list of
  10  *      conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright notice, this list
  13  *      of conditions and the following disclaimer in the documentation and/or other materials
  14  *      provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
  19  * SHALL THE COPYRIGHT HOLDER(S) OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  21  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  22  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  23  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  24  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "sljitLir.h"
  28 #include "regexJIT.h"
  29
  30 #include <stdlib.h>
  31
  32 #ifdef REGEX_MATCH_VERBOSE
  33 #include <stdio.h>
  34 #endif
  35
  36 /* Extra, hidden flags:
  37    {id!} where id > 0 found in the code. */
  38 #define REGEX_ID_CHECK          0x100
  39 /* When REGEX_NEWLINE && REGEX_MATCH_BEGIN defined, the pattern turn to a normal search,
  40    which starts with [\r\n] character range. */
  41 #define REGEX_FAKE_MATCH_BEGIN  0x200
  42 /* When REGEX_NEWLINE && REGEX_MATCH_END defined, the pattern turn to a normal search,
  43    which ends with [\r\n] character range. */
  44 #define REGEX_FAKE_MATCH_END    0x400
  45
  46 /* --------------------------------------------------------------------- */
  47 /*  Structures for JIT-ed pattern matching                               */
  48 /* --------------------------------------------------------------------- */
  49
  50 struct regex_machine
  51 {
  52         /* flags. */
  53         int flags;
  54         /* Number of state descriptors for one term. */
  55         sljit_sw no_states;
  56         /* Total size. */
  57         sljit_sw size;
  58
  59         union {
  60                 void *init_match;
  61                 sljit_sw (SLJIT_FUNC *call_init)(void *next, void* match);
  62         } u;
  63 #if (defined SLJIT_INDIRECT_CALL && SLJIT_INDIRECT_CALL)
  64         struct sljit_function_context context;
  65 #endif
  66
  67         void *continue_match;
  68
  69         /* Variable sized array to contain the handler addresses. */
  70         sljit_uw entry_addrs[1];
  71 };
  72
  73 struct regex_match
  74 {
  75         /* Current and next state array. */
  76         sljit_sw *current;
  77         sljit_sw *next;
  78         /* Starting. */
  79         sljit_sw head;
  80         /* String character index (ever increasing). */
  81         sljit_sw index;
  82         /* Best match found so far (members in priority order). */
  83         sljit_sw best_begin;
  84         sljit_sw best_end;
  85         sljit_sw best_id;
  86         /* Bool flags (encoded as word). */
  87         sljit_sw fast_quit;
  88         sljit_sw fast_forward;
  89         /* Machine. */
  90         struct regex_machine *machine;
  91
  92         union {
  93                 void *continue_match;
  94                 void (SLJIT_FUNC *call_continue)(struct regex_match *match, const regex_char_t *input_string, int length);
  95         } u;
  96
  97         /* Variable sized array to contain the state arrays. */
  98         sljit_sw states[1];
  99 };
 100
 101 /* State vector
 102     ITEM[0] - pointer to the address inside the machine code
 103     ITEM[1] - next pointer
 104     ITEM[2] - string started from (optional)
 105     ITEM[3] - max ID (optional) */
 106
 107 /* Register allocation. */
 108 /* Current state array (loaded & stored: regex_match->current). */
 109 #define R_CURR_STATE    SLJIT_S0
 110 /* Next state array (loaded & stored: regex_match->next). */
 111 #define R_NEXT_STATE    SLJIT_S1
 112 /* Head (loaded & stored: regex_match->head). */
 113 #define R_NEXT_HEAD     SLJIT_S2
 114 /* String fragment pointer. */
 115 #define R_STRING        SLJIT_S3
 116 /* String fragment length. */
 117 #define R_LENGTH        SLJIT_S4
 118 /* 'struct regex_match*' */
 119 #define R_REGEX_MATCH   SLJIT_R0
 120 /* Current character. */
 121 #define R_CURR_CHAR     SLJIT_R1
 122 /* Temporary register. */
 123 #define R_TEMP          SLJIT_R2
 124 /* Caches the regex_match->best_begin. */
 125 #define R_BEST_BEGIN    SLJIT_R3
 126 /* Current character index. */
 127 #define R_CURR_INDEX    SLJIT_R4
 128
 129 /* --------------------------------------------------------------------- */
 130 /*  Stack management                                                     */
 131 /* --------------------------------------------------------------------- */
 132
 133 /* Try to allocate 2^n blocks. */
 134 #define STACK_FRAGMENT_SIZE (((64 * sizeof(struct stack_item)) - (sizeof(struct stack_fragment_data))) / (sizeof(struct stack_item)))
 135
 136 struct stack_item {
 137         int type;
 138         int value;
 139 };
 140
 141 struct stack_fragment_data {
 142         struct stack_fragment *next;
 143         struct stack_fragment *prev;
 144 };
 145
 146 struct stack_fragment {
 147         struct stack_fragment_data data;
 148         struct stack_item items[STACK_FRAGMENT_SIZE];
 149 };
 150
 151 struct stack {
 152         struct stack_fragment *first;
 153         struct stack_fragment *last;
 154         int index;
 155         int count;
 156 };
 157
 158 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
 159
 160 static void stack_check(struct stack *stack)
 161 {
 162         struct stack_fragment *curr;
 163         int found;
 164
 165         if (!stack)
 166                 return;
 167
 168         SLJIT_ASSERT(stack->index >= 0 && stack->index < STACK_FRAGMENT_SIZE);
 169
 170         if (stack->first == NULL) {
 171                 SLJIT_ASSERT(stack->first == NULL && stack->last == NULL);
 172                 SLJIT_ASSERT(stack->index == STACK_FRAGMENT_SIZE - 1 && stack->count == 0);
 173                 return;
 174         }
 175
 176         found = 0;
 177         if (stack->last == NULL) {
 178                 SLJIT_ASSERT(stack->index == STACK_FRAGMENT_SIZE - 1 && stack->count == 0);
 179                 found = 1;
 180         }
 181         else
 182                 SLJIT_ASSERT(stack->index >= 0 && stack->count >= 0);
 183
 184         SLJIT_ASSERT(stack->first->data.prev == NULL);
 185         curr = stack->first;
 186         while (curr) {
 187                 if (curr == stack->last)
 188                         found = 1;
 189                 if (curr->data.next)
 190                         SLJIT_ASSERT(curr->data.next->data.prev == curr);
 191                 curr = curr->data.next;
 192         }
 193         SLJIT_ASSERT(found);
 194 }
 195
 196 #endif
 197
 198 static void stack_init(struct stack *stack)
 199 {
 200         stack->first = NULL;
 201         stack->last = NULL;
 202         stack->index = STACK_FRAGMENT_SIZE - 1;
 203         stack->count = 0;
 204 }
 205
 206 static void stack_destroy(struct stack *stack)
 207 {
 208         struct stack_fragment *curr = stack->first;
 209         struct stack_fragment *prev;
 210
 211 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
 212         stack_check(stack);
 213 #endif
 214
 215         while (curr) {
 216                 prev = curr;
 217                 curr = curr->data.next;
 218                 SLJIT_FREE(prev, NULL);
 219         }
 220 }
 221
 222 static SLJIT_INLINE struct stack_item* stack_top(struct stack *stack)
 223 {
 224         SLJIT_ASSERT(stack->last);
 225         return stack->last->items + stack->index;
 226 }
 227
 228 static int stack_push(struct stack *stack, int type, int value)
 229 {
 230         if (stack->last) {
 231                 stack->index++;
 232                 if (stack->index >= STACK_FRAGMENT_SIZE) {
 233                         stack->index = 0;
 234                         if (!stack->last->data.next) {
 235                                 stack->last->data.next = (struct stack_fragment*)SLJIT_MALLOC(sizeof(struct stack_fragment), NULL);
 236                                 if (!stack->last->data.next)
 237                                         return 1;
 238                                 stack->last->data.next->data.next = NULL;
 239                                 stack->last->data.next->data.prev = stack->last;
 240                         }
 241                         stack->last = stack->last->data.next;
 242                 }
 243         }
 244         else if (!stack->first) {
 245                 stack->last = (struct stack_fragment*)SLJIT_MALLOC(sizeof(struct stack_fragment), NULL);
 246                 if (!stack->last)
 247                         return 1;
 248                 stack->last->data.prev = NULL;
 249                 stack->last->data.next = NULL;
 250                 stack->first = stack->last;
 251                 stack->index = 0;
 252         }
 253         else {
 254                 stack->last = stack->first;
 255                 stack->index = 0;
 256         }
 257         stack->last->items[stack->index].type = type;
 258         stack->last->items[stack->index].value = value;
 259         stack->count++;
 260 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
 261         stack_check(stack);
 262 #endif
 263         return 0;
 264 }
 265
 266 static struct stack_item* stack_pop(struct stack *stack)
 267 {
 268         struct stack_item *ret = stack_top(stack);
 269
 270         if (stack->index > 0)
 271                 stack->index--;
 272         else {
 273                 stack->last = stack->last->data.prev;
 274                 stack->index = STACK_FRAGMENT_SIZE - 1;
 275         }
 276
 277         stack->count--;
 278 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
 279         stack_check(stack);
 280 #endif
 281         return ret;
 282 }
 283
 284 static SLJIT_INLINE void stack_clone(struct stack *src, struct stack *dst)
 285 {
 286         *dst = *src;
 287 }
 288
 289 static int stack_push_copy(struct stack *stack, int items, int length)
 290 {
 291         struct stack_fragment *frag1;
 292         int ind1;
 293         struct stack_fragment *frag2;
 294         int ind2;
 295         int counter;
 296
 297         SLJIT_ASSERT(stack->count >= length && items <= length && items > 0);
 298
 299         /* Allocate the necessary elements. */
 300         counter = items;
 301         frag1 = stack->last;
 302         ind1 = stack->index;
 303         while (counter > 0) {
 304                 if (stack->index + counter >= STACK_FRAGMENT_SIZE) {
 305                         counter -= STACK_FRAGMENT_SIZE - stack->index - 1 + 1;
 306                         stack->index = 0;
 307                         if (!stack->last->data.next) {
 308                                 stack->last->data.next = (struct stack_fragment*)SLJIT_MALLOC(sizeof(struct stack_fragment), NULL);
 309                                 if (!stack->last->data.next)
 310                                         return 1;
 311                                 stack->last->data.next->data.next = NULL;
 312                                 stack->last->data.next->data.prev = stack->last;
 313                         }
 314                         stack->last = stack->last->data.next;
 315                 }
 316                 else {
 317                         stack->index += counter;
 318                         counter = 0;
 319                 }
 320         }
 321
 322         frag2 = stack->last;
 323         ind2 = stack->index;
 324         while (length > 0) {
 325                 frag2->items[ind2--] = frag1->items[ind1--];
 326                 if (ind1 < 0) {
 327                         ind1 = STACK_FRAGMENT_SIZE - 1;
 328                         frag1 = frag1->data.prev;
 329                 }
 330                 if (ind2 < 0) {
 331                         ind2 = STACK_FRAGMENT_SIZE - 1;
 332                         frag2 = frag2->data.prev;
 333                 }
 334                 length--;
 335         }
 336
 337 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
 338         stack_check(stack);
 339 #endif
 340         stack->count += items;
 341         return 0;
 342 }
 343
 344 /* --------------------------------------------------------------------- */
 345 /*  Parser                                                               */
 346 /* --------------------------------------------------------------------- */
 347
 348 enum {
 349         /* Common. */
 350         type_begin,
 351         type_end,
 352         type_char,
 353         type_newline,
 354         type_id,
 355         type_rng_start,
 356         type_rng_end,
 357         type_rng_char,
 358         type_rng_left,
 359         type_rng_right,
 360
 361         /* generator only. */
 362         type_branch,
 363         type_jump,
 364
 365         /* Parser only. */
 366         type_open_br,
 367         type_close_br,
 368         type_select,
 369         type_asterisk,
 370         type_plus_sign,
 371         type_qestion_mark
 372 };
 373
 374 struct compiler_common {
 375         /* Temporary stacks. */
 376         struct stack stack;
 377         struct stack depth;
 378         /* REGEX_ flags. */
 379         int flags;
 380         /* Encoded size of the dfa representation. */
 381         sljit_sw dfa_size;
 382         /* Number of terms. */
 383         sljit_sw terms_size;
 384         /* Number of state descriptors for one term (same as machine->no_states). */
 385         sljit_sw no_states;
 386         /* Number of type_rng_(char|left)-s in the longest character range. */
 387         sljit_sw longest_range_size;
 388
 389         /* DFA linear representation (size: dfa_size). */
 390         struct stack_item *dfa_transitions;
 391         /* Term id and search state pairs (size: dfa_size). */
 392         struct stack_item *search_states;
 393
 394         /* sljit compiler */
 395         struct sljit_compiler *compiler;
 396         /* Machine data, which must be kept for later use. */
 397         struct regex_machine *machine;
 398         /* Temporary space for jumps (size: longest_range_size). */
 399         struct sljit_jump **range_jump_list;
 400 };
 401
 402 static const regex_char_t* decode_number(const regex_char_t *regex_string, int length, int *result)
 403 {
 404         int value = 0;
 405
 406         SLJIT_ASSERT(length > 0);
 407         if (*regex_string < '0' || *regex_string > '9') {
 408                 *result = -1;
 409                 return regex_string;
 410         }
 411
 412         while (length > 0 && *regex_string >= '0' && *regex_string <= '9') {
 413                 value = value * 10 + (*regex_string - '0');
 414                 length--;
 415                 regex_string++;
 416         }
 417
 418         *result = value;
 419         return regex_string;
 420 }
 421
 422 static int iterate(struct stack *stack, int min, int max)
 423 {
 424         struct stack it;
 425         struct stack_item *item;
 426         int count = -1;
 427         int len = 0;
 428         int depth = 0;
 429
 430         stack_clone(stack, &it);
 431
 432         /* Calculate size. */
 433         while (count < 0) {
 434                 item = stack_pop(&it);
 435                 switch (item->type) {
 436                 case type_id:
 437                 case type_rng_end:
 438                 case type_rng_char:
 439                 case type_rng_left:
 440                 case type_rng_right:
 441                 case type_plus_sign:
 442                 case type_qestion_mark:
 443                         len++;
 444                         break;
 445
 446                 case type_asterisk:
 447                         len += 2;
 448                         break;
 449
 450                 case type_close_br:
 451                         depth++;
 452                         break;
 453
 454                 case type_open_br:
 455                         SLJIT_ASSERT(depth > 0);
 456                         depth--;
 457                         if (depth == 0)
 458                                 count = it.count;
 459                         break;
 460
 461                 case type_select:
 462                         SLJIT_ASSERT(depth > 0);
 463                         len += 2;
 464                         break;
 465
 466                 default:
 467                         SLJIT_ASSERT(item->type != type_begin && item->type != type_end);
 468                         if (depth == 0)
 469                                 count = it.count;
 470                         len++;
 471                         break;
 472                 }
 473         }
 474
 475         if (min == 0 && max == 0) {
 476                 /* {0,0} case, not {0,} case: delete subtree. */
 477                 stack_clone(&it, stack);
 478                 /* and put an empty bracket expression instead of it. */
 479                 if (stack_push(stack, type_open_br, 0))
 480                         return REGEX_MEMORY_ERROR;
 481                 if (stack_push(stack, type_close_br, 0))
 482                         return REGEX_MEMORY_ERROR;
 483                 return len;
 484         }
 485
 486         count = stack->count - count;
 487
 488         /* Put an open bracket before the sequence. */
 489         if (stack_push_copy(stack, 1, count))
 490                 return -1;
 491
 492 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
 493         SLJIT_ASSERT(stack_push(&it, type_open_br, 0) == 0);
 494 #else
 495         stack_push(&it, type_open_br, 0);
 496 #endif
 497
 498         /* Copy the data. */
 499         if (max > 0) {
 500                 len = len * (max - 1);
 501                 max -= min;
 502                 /* Insert ? operators. */
 503                 len += max;
 504
 505                 if (min > 0) {
 506                         min--;
 507                         while (min > 0) {
 508                                 if (stack_push_copy(stack, count, count))
 509                                         return -1;
 510                                 min--;
 511                         }
 512                         if (max > 0) {
 513                                 if (stack_push_copy(stack, count, count))
 514                                         return -1;
 515                                 if (stack_push(stack, type_qestion_mark, 0))
 516                                         return REGEX_MEMORY_ERROR;
 517                                 count++;
 518                                 max--;
 519                         }
 520                 }
 521                 else {
 522                         SLJIT_ASSERT(max > 0);
 523                         max--;
 524                         count++;
 525                         if (stack_push(stack, type_qestion_mark, 0))
 526                                 return REGEX_MEMORY_ERROR;
 527                 }
 528
 529                 while (max > 0) {
 530                         if (stack_push_copy(stack, count, count))
 531                                 return -1;
 532                         max--;
 533                 }
 534         }
 535         else {
 536                 SLJIT_ASSERT(min > 0);
 537                 min--;
 538                 /* Insert + operator. */
 539                 len = len * min + 1;
 540                 while (min > 0) {
 541                         if (stack_push_copy(stack, count, count))
 542                                 return -1;
 543                         min--;
 544                 }
 545
 546                 if (stack_push(stack, type_plus_sign, 0))
 547                         return REGEX_MEMORY_ERROR;
 548         }
 549
 550         /* Close the opened bracket. */
 551         if (stack_push(stack, type_close_br, 0))
 552                 return REGEX_MEMORY_ERROR;
 553
 554         return len;
 555 }
 556
 557 static int parse_iterator(const regex_char_t *regex_string, int length, struct stack *stack, sljit_sw *dfa_size, int begin)
 558 {
 559         /* We only know that *regex_string == { . */
 560         int val1, val2;
 561         const regex_char_t *base_from = regex_string;
 562         const regex_char_t *from;
 563
 564         length--;
 565         regex_string++;
 566
 567         /* Decode left value. */
 568         val2 = -1;
 569         if (length == 0)
 570                 return -2;
 571         if (*regex_string == ',') {
 572                 val1 = 0;
 573                 length--;
 574                 regex_string++;
 575         }
 576         else {
 577                 from = regex_string;
 578                 regex_string = decode_number(regex_string, length, &val1);
 579                 if (val1 < 0)
 580                         return -2;
 581                 length -= regex_string - from;
 582
 583                 if (length == 0)
 584                         return -2;
 585                 if (*regex_string == '}') {
 586                         val2 = val1;
 587                         if (val1 == 0)
 588                                 val1 = -1;
 589                 }
 590                 else if (length >= 2 && *regex_string == '!' && regex_string[1] == '}') {
 591                         /* Non posix extension. */
 592                         if (stack_push(stack, type_id, val1))
 593                                 return -1;
 594                         (*dfa_size)++;
 595                         return (regex_string - base_from) + 1;
 596                 }
 597                 else {
 598                         if (*regex_string != ',')
 599                                 return -2;
 600                         length--;
 601                         regex_string++;
 602                 }
 603         }
 604
 605         if (begin)
 606                 return -2;
 607
 608         /* Decode right value. */
 609         if (val2 == -1) {
 610                 if (length == 0)
 611                         return -2;
 612                 if (*regex_string == '}')
 613                         val2 = 0;
 614                 else {
 615                         from = regex_string;
 616                         regex_string = decode_number(regex_string, length, &val2);
 617                         length -= regex_string - from;
 618                         if (val2 < 0 || length == 0 || *regex_string != '}' || val2 < val1)
 619                                 return -2;
 620                         if (val2 == 0) {
 621                                 SLJIT_ASSERT(val1 == 0);
 622                                 val1 = -1;
 623                         }
 624                 }
 625         }
 626
 627         /* Fast cases. */
 628         if (val1 > 1 || val2 > 1) {
 629                 val1 = iterate(stack, val1, val2);
 630                 if (val1 < 0)
 631                         return -1;
 632                 *dfa_size += val1;
 633         }
 634         else if (val1 == 0 && val2 == 0) {
 635                 if (stack_push(stack, type_asterisk, 0))
 636                         return -1;
 637                 *dfa_size += 2;
 638         }
 639         else if (val1 == 1 && val2 == 0) {
 640                 if (stack_push(stack, type_plus_sign, 0))
 641                         return -1;
 642                 (*dfa_size)++;
 643         }
 644         else if (val1 == 0 && val2 == 1) {
 645                 if (stack_push(stack, type_qestion_mark, 0))
 646                         return -1;
 647                 (*dfa_size)++;
 648         }
 649         else if (val1 == -1) {
 650                 val1 = iterate(stack, 0, 0);
 651                 if (val1 < 0)
 652                         return -1;
 653                 *dfa_size -= val1;
 654                 SLJIT_ASSERT(*dfa_size >= 2);
 655         }
 656         else {
 657                 /* Ignore. */
 658                 SLJIT_ASSERT(val1 == 1 && val2 == 1);
 659         }
 660         return regex_string - base_from;
 661 }
 662
 663 static int parse_char_range(const regex_char_t *regex_string, int length, struct compiler_common *compiler_common)
 664 {
 665         struct stack* stack = &compiler_common->stack;
 666         const regex_char_t *base_from = regex_string;
 667         regex_char_t left_char, right_char, tmp_char;
 668
 669         length--;
 670         regex_string++;
 671
 672         if (length == 0)
 673                 return -2;
 674
 675         if (*regex_string != '^') {
 676                 if (stack_push(stack, type_rng_start, 0))
 677                         return -1;
 678         }
 679         else {
 680                 length--;
 681                 regex_string++;
 682
 683                 if (length == 0)
 684                         return -2;
 685
 686                 if (stack_push(stack, type_rng_start, 1))
 687                         return -1;
 688         }
 689         /* For both the type_rng_start & type_rng_end. */
 690         compiler_common->dfa_size += 2;
 691
 692         /* Range must be at least 1 character. */
 693         if (*regex_string == ']') {
 694                 length--;
 695                 regex_string++;
 696                 if (stack_push(stack, type_rng_char, ']'))
 697                         return -1;
 698                 compiler_common->dfa_size++;
 699         }
 700
 701         while (1) {
 702                 if (length == 0)
 703                         return -2;
 704
 705                 if (*regex_string == ']')
 706                         break;
 707
 708                 if (*regex_string != '\\')
 709                         left_char = *regex_string;
 710                 else {
 711                         regex_string++;
 712                         length--;
 713                         if (length == 0)
 714                                 return -2;
 715                         left_char = *regex_string;
 716                 }
 717                 regex_string++;
 718                 length--;
 719
 720                 /* Is a range here? */
 721                 if (length >= 3 && *regex_string == '-' && *(regex_string + 1) != ']') {
 722                         regex_string++;
 723                         length--;
 724
 725                         if (*regex_string != '\\')
 726                                 right_char = *regex_string;
 727                         else {
 728                                 regex_string++;
 729                                 length--;
 730                                 if (length == 0)
 731                                         return -2;
 732                                 right_char = *regex_string;
 733                         }
 734                         regex_string++;
 735                         length--;
 736
 737                         if (left_char > right_char) {
 738                                 /* Swap if necessary. */
 739                                 tmp_char = left_char;
 740                                 left_char = right_char;
 741                                 right_char = tmp_char;
 742                         }
 743
 744                         if (stack_push(stack, type_rng_left, left_char))
 745                                 return -1;
 746                         if (stack_push(stack, type_rng_right, right_char))
 747                                 return -1;
 748                         compiler_common->dfa_size += 2;
 749                 }
 750                 else {
 751                         if (stack_push(stack, type_rng_char, left_char))
 752                                 return -1;
 753                         compiler_common->dfa_size++;
 754                 }
 755         }
 756
 757         if (stack_push(stack, type_rng_end, 0))
 758                 return -1;
 759         return regex_string - base_from;
 760 }
 761
 762 static int parse(const regex_char_t *regex_string, int length, struct compiler_common *compiler_common)
 763 {
 764         /* Depth of bracketed expressions. */
 765         int depth = 0;
 766         /* Have we already found a term? '1' if not yet. */
 767         int begin = 1;
 768         /* Cache stack pointer. */
 769         struct stack* stack = &compiler_common->stack;
 770         int tmp;
 771
 772         /* Type_begin and type_end. */
 773         compiler_common->dfa_size = 2;
 774         stack_init(stack);
 775         if (stack_push(stack, type_begin, 0))
 776                 return REGEX_MEMORY_ERROR;
 777
 778         if (length > 0 && *regex_string == '^') {
 779                 compiler_common->flags |= REGEX_MATCH_BEGIN;
 780                 length--;
 781                 regex_string++;
 782         }
 783
 784         if ((compiler_common->flags & (REGEX_MATCH_BEGIN | REGEX_NEWLINE)) == (REGEX_MATCH_BEGIN | REGEX_NEWLINE)) {
 785                 /* Replace REGEX_MATCH_BEGIN flag to REGEX_FAKE_MATCH_BEGIN */
 786                 compiler_common->flags &= ~REGEX_MATCH_BEGIN;
 787                 compiler_common->flags |= REGEX_FAKE_MATCH_BEGIN;
 788                 /* and append a new-line search. */
 789                 if (stack_push(stack, type_newline, 0))
 790                         return REGEX_MEMORY_ERROR;
 791                 compiler_common->dfa_size++;
 792                 /* Begin intentionally kept as 1. */
 793         }
 794
 795         while (length > 0) {
 796                 switch (*regex_string) {
 797                 case '\\' :
 798                         length--;
 799                         regex_string++;
 800                         if (length == 0)
 801                                 return REGEX_INVALID_REGEX;
 802                         if (stack_push(stack, type_char, *regex_string))
 803                                 return REGEX_MEMORY_ERROR;
 804                         begin = 0;
 805                         compiler_common->dfa_size++;
 806                         break;
 807
 808                 case '.' :
 809                         if (stack_push(stack, type_rng_start, 1))
 810                                 return REGEX_MEMORY_ERROR;
 811                         if (compiler_common->flags & REGEX_NEWLINE) {
 812                                 if (stack_push(stack, type_rng_char, '\n'))
 813                                         return REGEX_MEMORY_ERROR;
 814                                 if (stack_push(stack, type_rng_char, '\r'))
 815                                         return REGEX_MEMORY_ERROR;
 816                                 compiler_common->dfa_size += 2;
 817                         }
 818                         if (stack_push(stack, type_rng_end, 1))
 819                                 return REGEX_MEMORY_ERROR;
 820                         begin = 0;
 821                         compiler_common->dfa_size += 2;
 822                         break;
 823
 824                 case '(' :
 825                         depth++;
 826                         if (stack_push(stack, type_open_br, 0))
 827                                 return REGEX_MEMORY_ERROR;
 828                         begin = 1;
 829                         break;
 830
 831                 case ')' :
 832                         if (depth == 0)
 833                                 return REGEX_INVALID_REGEX;
 834                         depth--;
 835                         if (stack_push(stack, type_close_br, 0))
 836                                 return REGEX_MEMORY_ERROR;
 837                         begin = 0;
 838                         break;
 839
 840                 case '|' :
 841                         if (stack_push(stack, type_select, 0))
 842                                 return REGEX_MEMORY_ERROR;
 843                         begin = 1;
 844                         compiler_common->dfa_size += 2;
 845                         break;
 846
 847                 case '*' :
 848                         if (begin)
 849                                 return REGEX_INVALID_REGEX;
 850                         if (stack_push(stack, type_asterisk, 0))
 851                                 return REGEX_MEMORY_ERROR;
 852                         compiler_common->dfa_size += 2;
 853                         break;
 854
 855                 case '?' :
 856                 case '+' :
 857                         if (begin)
 858                                 return REGEX_INVALID_REGEX;
 859                         if (stack_push(stack, (*regex_string == '+') ? type_plus_sign : type_qestion_mark, 0))
 860                                 return REGEX_MEMORY_ERROR;
 861                         compiler_common->dfa_size++;
 862                         break;
 863
 864                 case '{' :
 865                         tmp = parse_iterator(regex_string, length, stack, &compiler_common->dfa_size, begin);
 866
 867                         if (tmp >= 0) {
 868                                 length -= tmp;
 869                                 regex_string += tmp;
 870                         }
 871                         else if (tmp == -1)
 872                                 return REGEX_MEMORY_ERROR;
 873                         else {
 874                                 /* Not a valid range expression. */
 875                                 SLJIT_ASSERT(tmp == -2);
 876                                 if (stack_push(stack, type_char, '{'))
 877                                         return REGEX_MEMORY_ERROR;
 878                                 compiler_common->dfa_size++;
 879                         }
 880                         break;
 881
 882                 case '[' :
 883                         tmp = parse_char_range(regex_string, length, compiler_common);
 884                         if (tmp >= 0) {
 885                                 length -= tmp;
 886                                 regex_string += tmp;
 887                         }
 888                         else if (tmp == -1)
 889                                 return REGEX_MEMORY_ERROR;
 890                         else {
 891                                 SLJIT_ASSERT(tmp == -2);
 892                                 return REGEX_INVALID_REGEX;
 893                         }
 894                         begin = 0;
 895                         break;
 896
 897                 default:
 898                         if (length == 1 && *regex_string == '$') {
 899                                 compiler_common->flags |= REGEX_MATCH_END;
 900                                 break;
 901                         }
 902                         if (stack_push(stack, type_char, *regex_string))
 903                                 return REGEX_MEMORY_ERROR;
 904                         begin = 0;
 905                         compiler_common->dfa_size++;
 906                         break;
 907                 }
 908                 length--;
 909                 regex_string++;
 910         }
 911
 912         if (depth != 0)
 913                 return REGEX_INVALID_REGEX;
 914
 915         if ((compiler_common->flags & (REGEX_MATCH_END | REGEX_NEWLINE)) == (REGEX_MATCH_END | REGEX_NEWLINE)) {
 916                 /* Replace REGEX_MATCH_END flag to REGEX_FAKE_MATCH_END */
 917                 compiler_common->flags &= ~REGEX_MATCH_END;
 918                 compiler_common->flags |= REGEX_FAKE_MATCH_END;
 919                 /* and append a new-line search. */
 920                 if (stack_push(stack, type_newline, 1))
 921                         return REGEX_MEMORY_ERROR;
 922                 compiler_common->dfa_size++;
 923                 /* Begin intentionally kept as 1. */
 924         }
 925
 926         if (stack_push(stack, type_end, 0))
 927                 return REGEX_MEMORY_ERROR;
 928
 929         return REGEX_NO_ERROR;
 930 }
 931
 932 /* --------------------------------------------------------------------- */
 933 /*  Generating machine state transitions                                 */
 934 /* --------------------------------------------------------------------- */
 935
 936 #define PUT_TRANSITION(typ, val) \
 937         do { \
 938                 --transitions_ptr; \
 939                 transitions_ptr->type = typ; \
 940                 transitions_ptr->value = val; \
 941         } while (0)
 942
 943 static struct stack_item* handle_iteratives(struct stack_item *transitions_ptr, struct stack_item *transitions, struct stack *depth)
 944 {
 945         struct stack_item *item;
 946
 947         while (1) {
 948                 item = stack_top(depth);
 949
 950                 switch (item->type) {
 951                 case type_asterisk:
 952                         SLJIT_ASSERT(transitions[item->value].type == type_branch);
 953                         transitions[item->value].value = transitions_ptr - transitions;
 954                         PUT_TRANSITION(type_branch, item->value + 1);
 955                         break;
 956
 957                 case type_plus_sign:
 958                         SLJIT_ASSERT(transitions[item->value].type == type_branch);
 959                         transitions[item->value].value = transitions_ptr - transitions;
 960                         break;
 961
 962                 case type_qestion_mark:
 963                         PUT_TRANSITION(type_branch, item->value);
 964                         break;
 965
 966                 default:
 967                         return transitions_ptr;
 968                 }
 969                 stack_pop(depth);
 970         }
 971 }
 972
 973 static int generate_transitions(struct compiler_common *compiler_common)
 974 {
 975         struct stack *stack = &compiler_common->stack;
 976         struct stack *depth = &compiler_common->depth;
 977         struct stack_item *transitions_ptr;
 978         struct stack_item *item;
 979
 980         stack_init(depth);
 981         compiler_common->dfa_transitions = SLJIT_MALLOC(sizeof(struct stack_item) * compiler_common->dfa_size, NULL);
 982         if (!compiler_common->dfa_transitions)
 983                 return REGEX_MEMORY_ERROR;
 984
 985         /* Go through the items of the stack and generate the necessary branches and jumps (edges of DFA). */
 986         transitions_ptr = compiler_common->dfa_transitions + compiler_common->dfa_size;
 987         while (stack->count > 0) {
 988                 item = stack_pop(stack);
 989                 switch (item->type) {
 990                 case type_begin:
 991                 case type_open_br:
 992                         item = stack_pop(depth);
 993                         if (item->type == type_select)
 994                                 PUT_TRANSITION(type_branch, item->value + 1);
 995                         else
 996                                 SLJIT_ASSERT(item->type == type_close_br);
 997                         if (stack->count == 0)
 998                                 PUT_TRANSITION(type_begin, 0);
 999                         else
1000                                 transitions_ptr = handle_iteratives(transitions_ptr, compiler_common->dfa_transitions, depth);
1001                         break;
1002
1003                 case type_end:
1004                 case type_close_br:
1005                         if (item->type == type_end)
1006                                 *--transitions_ptr = *item;
1007                         if (stack_push(depth, type_close_br, transitions_ptr - compiler_common->dfa_transitions))
1008                                 return REGEX_MEMORY_ERROR;
1009                         break;
1010
1011                 case type_select:
1012                         item = stack_top(depth);
1013                         if (item->type == type_select) {
1014                                 SLJIT_ASSERT(compiler_common->dfa_transitions[item->value].type == type_jump);
1015                                 PUT_TRANSITION(type_branch, item->value + 1);
1016                                 PUT_TRANSITION(type_jump, item->value);
1017                                 item->value = transitions_ptr - compiler_common->dfa_transitions;
1018                         }
1019                         else {
1020                                 SLJIT_ASSERT(item->type == type_close_br);
1021                                 item->type = type_select;
1022                                 PUT_TRANSITION(type_jump, item->value);
1023                                 item->value = transitions_ptr - compiler_common->dfa_transitions;
1024                         }
1025                         break;
1026
1027                 case type_asterisk:
1028                 case type_plus_sign:
1029                 case type_qestion_mark:
1030                         if (item->type != type_qestion_mark)
1031                                 PUT_TRANSITION(type_branch, 0);
1032                         if (stack_push(depth, item->type, transitions_ptr - compiler_common->dfa_transitions))
1033                                 return REGEX_MEMORY_ERROR;
1034                         break;
1035
1036                 case type_char:
1037                 case type_newline:
1038                 case type_rng_start:
1039                         /* Requires handle_iteratives. */
1040                         *--transitions_ptr = *item;
1041                         transitions_ptr = handle_iteratives(transitions_ptr, compiler_common->dfa_transitions, depth);
1042                         break;
1043
1044                 default:
1045                         *--transitions_ptr = *item;
1046                         break;
1047                 }
1048         }
1049
1050         SLJIT_ASSERT(compiler_common->dfa_transitions == transitions_ptr);
1051         SLJIT_ASSERT(depth->count == 0);
1052         return REGEX_NO_ERROR;
1053 }
1054
1055 #undef PUT_TRANSITION
1056
1057 #ifdef REGEX_MATCH_VERBOSE
1058
1059 static void verbose_transitions(struct compiler_common *compiler_common)
1060 {
1061         struct stack_item *transitions_ptr = compiler_common->dfa_transitions;
1062         struct stack_item *transitions_end = transitions_ptr + compiler_common->dfa_size;
1063         struct stack_item *search_states_ptr = compiler_common->search_states;
1064         int pos;
1065
1066         printf("-----------------\nTransitions\n-----------------\n");
1067         pos = 0;
1068         while (transitions_ptr < transitions_end) {
1069                 printf("[%3d] ", pos++);
1070                 if (search_states_ptr->type >= 0)
1071                         printf("(%3d) ", search_states_ptr->type);
1072                 switch (transitions_ptr->type) {
1073                 case type_begin:
1074                         printf("type_begin\n");
1075                         break;
1076
1077                 case type_end:
1078                         printf("type_end\n");
1079                         break;
1080
1081                 case type_char:
1082                         if (transitions_ptr->value >= ' ')
1083                                 printf("type_char '%c'\n", transitions_ptr->value);
1084                         else
1085                                 printf("type_char 0x%x\n", transitions_ptr->value);
1086                         break;
1087
1088                 case type_newline:
1089                         printf("type_newline %s\n", transitions_ptr->value ? "(end)" : "(begin)");
1090                         break;
1091
1092                 case type_id:
1093                         printf("type_id %d\n", transitions_ptr->value);
1094                         break;
1095
1096                 case type_rng_start:
1097                         printf("type_rng_start %s\n", transitions_ptr->value ? "(invert)" : "(normal)");
1098                         break;
1099
1100                 case type_rng_end:
1101                         printf("type_rng_end\n");
1102                         break;
1103
1104                 case type_rng_char:
1105                         if (transitions_ptr->value >= ' ')
1106                                 printf("type_rng_char '%c'\n", transitions_ptr->value);
1107                         else
1108                                 printf("type_rng_char 0x%x\n", transitions_ptr->value);
1109                         break;
1110
1111                 case type_rng_left:
1112                         if (transitions_ptr->value >= ' ')
1113                                 printf("type_rng_left '%c'\n", transitions_ptr->value);
1114                         else
1115                                 printf("type_rng_left 0x%x\n", transitions_ptr->value);
1116                         break;
1117
1118                 case type_rng_right:
1119                         if (transitions_ptr->value >= ' ')
1120                                 printf("type_rng_right '%c'\n", transitions_ptr->value);
1121                         else
1122                                 printf("type_rng_right 0x%x\n", transitions_ptr->value);
1123                         break;
1124
1125                 case type_branch:
1126                         printf("type_branch -> %d\n", transitions_ptr->value);
1127                         break;
1128
1129                 case type_jump:
1130                         printf("type_jump -> %d\n", transitions_ptr->value);
1131                         break;
1132
1133                 default:
1134                         printf("UNEXPECTED TYPE\n");
1135                         break;
1136                 }
1137                 transitions_ptr++;
1138                 search_states_ptr++;
1139         }
1140         printf("flags: ");
1141         if (!(compiler_common->flags & (REGEX_MATCH_BEGIN | REGEX_MATCH_END | REGEX_NEWLINE | REGEX_ID_CHECK | REGEX_FAKE_MATCH_BEGIN | REGEX_FAKE_MATCH_END)))
1142                 printf("none ");
1143         if (compiler_common->flags & REGEX_MATCH_BEGIN)
1144                 printf("REGEX_MATCH_BEGIN ");
1145         if (compiler_common->flags & REGEX_MATCH_END)
1146                 printf("REGEX_MATCH_END ");
1147         if (compiler_common->flags & REGEX_NEWLINE)
1148                 printf("REGEX_NEWLINE ");
1149         if (compiler_common->flags & REGEX_ID_CHECK)
1150                 printf("REGEX_ID_CHECK ");
1151         if (compiler_common->flags & REGEX_FAKE_MATCH_BEGIN)
1152                 printf("REGEX_FAKE_MATCH_BEGIN ");
1153         if (compiler_common->flags & REGEX_FAKE_MATCH_END)
1154                 printf("REGEX_FAKE_MATCH_END ");
1155         if (compiler_common->longest_range_size > 0)
1156                 printf("(longest range: %ld) ", (long)compiler_common->longest_range_size);
1157         printf("\n");
1158 }
1159
1160 #endif
1161
1162 /* --------------------------------------------------------------------- */
1163 /*  Utilities                                                            */
1164 /* --------------------------------------------------------------------- */
1165
1166 static int generate_search_states(struct compiler_common *compiler_common)
1167 {
1168         struct stack_item *transitions_ptr = compiler_common->dfa_transitions;
1169         struct stack_item *transitions_end = transitions_ptr + compiler_common->dfa_size;
1170         struct stack_item *search_states_ptr;
1171         struct stack_item *rng_start = NULL;
1172
1173         compiler_common->terms_size = !(compiler_common->flags & REGEX_FAKE_MATCH_END) ? 1 : 2;
1174         compiler_common->longest_range_size = 0;
1175         compiler_common->search_states = SLJIT_MALLOC(sizeof(struct stack_item) * compiler_common->dfa_size, NULL);
1176         if (!compiler_common->search_states)
1177                 return REGEX_MEMORY_ERROR;
1178
1179         search_states_ptr = compiler_common->search_states;
1180         while (transitions_ptr < transitions_end) {
1181                 switch (transitions_ptr->type) {
1182                 case type_begin:
1183                 case type_end:
1184                         search_states_ptr->type = 0;
1185                         break;
1186
1187                 case type_char:
1188                         search_states_ptr->type = compiler_common->terms_size++;
1189                         break;
1190
1191                 case type_newline:
1192                         if (transitions_ptr->value)
1193                                 search_states_ptr->type = 1;
1194                         else
1195                                 search_states_ptr->type = compiler_common->terms_size++;
1196                         SLJIT_ASSERT(search_states_ptr->type == 1 || search_states_ptr->type == 2);
1197                         break;
1198
1199                 case type_id:
1200                         if (transitions_ptr->value > 0)
1201                                 compiler_common->flags |= REGEX_ID_CHECK;
1202                         search_states_ptr->type = -1;
1203                         break;
1204
1205                 case type_rng_start:
1206                         search_states_ptr->type = compiler_common->terms_size;
1207                         rng_start = search_states_ptr;
1208                         break;
1209
1210                 case type_rng_end:
1211                         search_states_ptr->type = compiler_common->terms_size++;
1212                         /* Ok, this is a blunt over estimation :) */
1213                         if (compiler_common->longest_range_size < search_states_ptr - rng_start)
1214                                 compiler_common->longest_range_size = search_states_ptr - rng_start;
1215                         break;
1216
1217                 default:
1218                         search_states_ptr->type = -1;
1219                         break;
1220                 }
1221                 search_states_ptr->value = -1;
1222                 search_states_ptr++;
1223                 transitions_ptr++;
1224         }
1225         return REGEX_NO_ERROR;
1226 }
1227
1228 static int trace_transitions(int from, struct compiler_common *compiler_common)
1229 {
1230         int id = 0;
1231         struct stack *stack = &compiler_common->stack;
1232         struct stack *depth = &compiler_common->depth;
1233         struct stack_item *dfa_transitions = compiler_common->dfa_transitions;
1234         struct stack_item *search_states = compiler_common->search_states;
1235
1236         SLJIT_ASSERT(search_states[from].type >= 0);
1237
1238         from++;
1239
1240         /* Be prepared for any paths (loops, etc). */
1241         while (1) {
1242                 if (dfa_transitions[from].type == type_id)
1243                         if (id < dfa_transitions[from].value)
1244                                 id = dfa_transitions[from].value;
1245
1246                 if (search_states[from].value < id) {
1247                         /* Forward step. */
1248                         if (search_states[from].value == -1)
1249                                 if (stack_push(stack, 0, from))
1250                                         return REGEX_MEMORY_ERROR;
1251                         search_states[from].value = id;
1252
1253                         if (dfa_transitions[from].type == type_branch) {
1254                                 if (stack_push(depth, id, from))
1255                                         return REGEX_MEMORY_ERROR;
1256                                 from++;
1257                                 continue;
1258                         }
1259                         else if (dfa_transitions[from].type == type_jump) {
1260                                 from = dfa_transitions[from].value;
1261                                 continue;
1262                         }
1263                         else if (search_states[from].type < 0) {
1264                                 from++;
1265                                 continue;
1266                         }
1267                 }
1268
1269                 /* Back tracking. */
1270                 if (depth->count > 0) {
1271                         id = stack_top(depth)->type;
1272                         from = dfa_transitions[stack_pop(depth)->value].value;
1273                         continue;
1274                 }
1275                 return 0;
1276         }
1277 }
1278
1279 /* --------------------------------------------------------------------- */
1280 /*  Code generator                                                       */
1281 /* --------------------------------------------------------------------- */
1282
1283 #define TERM_OFFSET_OF(index, offs)     (((index) * no_states + (offs)) * sizeof(sljit_sw))
1284 #define TERM_REL_OFFSET_OF(base, offs)  ((base) + ((offs) * sizeof(sljit_sw)))
1285
1286 #define EMIT_OP1(type, arg1, arg2, arg3, arg4) \
1287         CHECK(sljit_emit_op1(compiler, type, arg1, arg2, arg3, arg4))
1288
1289 #define EMIT_OP2(type, arg1, arg2, arg3, arg4, arg5, arg6) \
1290         CHECK(sljit_emit_op2(compiler, type, arg1, arg2, arg3, arg4, arg5, arg6))
1291
1292 #define EMIT_LABEL(label) \
1293         label = sljit_emit_label(compiler); \
1294         CHECK(!label)
1295
1296 #define EMIT_JUMP(jump, type) \
1297         jump = sljit_emit_jump(compiler, type); \
1298         CHECK(!jump)
1299
1300 #define EMIT_CMP(jump, type, arg1, arg2, arg3, arg4) \
1301         jump = sljit_emit_cmp(compiler, type, arg1, arg2, arg3, arg4); \
1302         CHECK(!jump)
1303
1304 /* CHECK depends on the use case. */
1305
1306 #define CHECK(exp) \
1307         if (SLJIT_UNLIKELY(exp)) \
1308                 return REGEX_MEMORY_ERROR
1309
1310 static int compile_uncond_tran(struct compiler_common *compiler_common, int reg)
1311 {
1312         struct sljit_compiler *compiler = compiler_common->compiler;
1313         struct stack *stack = &compiler_common->stack;
1314         struct stack_item *search_states = compiler_common->search_states;
1315         int flags = compiler_common->flags;
1316         sljit_sw no_states = compiler_common->no_states;
1317         sljit_uw head = 0;
1318         sljit_sw offset, value;
1319
1320         if (reg != R_CURR_STATE || !(compiler_common->flags & REGEX_FAKE_MATCH_BEGIN)) {
1321                 CHECK(trace_transitions(0, compiler_common));
1322         }
1323         else {
1324                 CHECK(trace_transitions(1, compiler_common));
1325         }
1326
1327         while (stack->count > 0) {
1328                 value = stack_pop(stack)->value;
1329                 if (search_states[value].type >= 0) {
1330                         offset = TERM_OFFSET_OF(search_states[value].type, 0);
1331                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 1), SLJIT_IMM, head);
1332                         if (offset > 0)
1333                                 head = offset;
1334
1335                         if (!(flags & REGEX_MATCH_BEGIN)) {
1336                                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 2), R_TEMP, 0);
1337                                 if (flags & REGEX_ID_CHECK) {
1338                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 3), SLJIT_IMM, search_states[value].value);
1339                                 }
1340                         }
1341                         else if (flags & REGEX_ID_CHECK) {
1342                                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 2), SLJIT_IMM, search_states[value].value);
1343                         }
1344                 }
1345                 search_states[value].value = -1;
1346         }
1347         if (reg == R_NEXT_STATE) {
1348                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_NEXT_HEAD, 0);
1349         }
1350         else if (flags & REGEX_FAKE_MATCH_BEGIN) {
1351                 SLJIT_ASSERT(compiler_common->dfa_transitions[1].type == type_newline && !compiler_common->dfa_transitions[1].value);
1352                 offset = TERM_OFFSET_OF(search_states[1].type, 0);
1353
1354                 SLJIT_ASSERT(!(flags & REGEX_MATCH_BEGIN));
1355
1356                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 1), SLJIT_IMM, head);
1357                 head = offset;
1358
1359                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 2), SLJIT_IMM, 1);
1360                 if (flags & REGEX_ID_CHECK) {
1361                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(reg), TERM_REL_OFFSET_OF(offset, 3), SLJIT_IMM, 0);
1362                 }
1363         }
1364         EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, head);
1365         return REGEX_NO_ERROR;
1366 }
1367
1368 static int compile_cond_tran(struct compiler_common *compiler_common, sljit_sw curr_index)
1369 {
1370         struct sljit_compiler *compiler = compiler_common->compiler;
1371         struct stack *stack = &compiler_common->stack;
1372         struct stack_item *search_states = compiler_common->search_states;
1373         sljit_sw offset;
1374         int flags;
1375         sljit_sw no_states;
1376         sljit_sw value;
1377         struct sljit_jump *jump1;
1378         struct sljit_jump *jump2;
1379         struct sljit_jump *jump3;
1380         struct sljit_jump *jump4;
1381         struct sljit_jump *jump5;
1382         struct sljit_label *label1;
1383
1384         flags = compiler_common->flags;
1385         no_states = compiler_common->no_states;
1386
1387         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_forward), SLJIT_IMM, 0);
1388         if (!(flags & (REGEX_ID_CHECK | REGEX_MATCH_BEGIN))) {
1389                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(curr_index, 2));
1390         }
1391
1392         while (stack->count > 0) {
1393                 value = stack_pop(stack)->value;
1394                 if (search_states[value].type >= 0) {
1395 #ifdef REGEX_MATCH_VERBOSE
1396                         if (flags & REGEX_MATCH_VERBOSE)
1397                                 printf("-> (%3d:%3d) ", search_states[value].type, search_states[value].value);
1398 #endif
1399                         offset = TERM_OFFSET_OF(search_states[value].type, 0);
1400
1401                         if (!(flags & REGEX_ID_CHECK)) {
1402                                 if (!(flags & REGEX_MATCH_BEGIN)) {
1403                                         /* Check whether item is inserted. */
1404                                         EMIT_CMP(jump1, SLJIT_NOT_EQUAL, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), SLJIT_IMM, -1);
1405                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), R_NEXT_HEAD, 0);
1406                                         if (offset > 0) {
1407                                                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, offset);
1408                                         }
1409                                         EMIT_JUMP(jump2, SLJIT_JUMP);
1410
1411                                         /* Check whether old index <= index. */
1412                                         EMIT_LABEL(label1);
1413                                         sljit_set_label(jump1, label1);
1414
1415                                         EMIT_CMP(jump1, SLJIT_LESS_EQUAL, SLJIT_MEM1(R_NEXT_STATE), offset + 2 * sizeof(sljit_sw), R_TEMP, 0);
1416
1417                                         EMIT_LABEL(label1);
1418                                         sljit_set_label(jump2, label1);
1419                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + 2 * sizeof(sljit_sw), R_TEMP, 0);
1420
1421                                         EMIT_LABEL(label1);
1422                                         sljit_set_label(jump1, label1);
1423                                 }
1424                                 else {
1425                                         /* Check whether item is inserted. */
1426                                         EMIT_CMP(jump1, SLJIT_NOT_EQUAL, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), SLJIT_IMM, -1);
1427                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), R_NEXT_HEAD, 0);
1428                                         if (offset > 0) {
1429                                                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, offset);
1430                                         }
1431                                         EMIT_LABEL(label1);
1432                                         sljit_set_label(jump1, label1);
1433                                 }
1434                         }
1435                         else {
1436                                 if (!(flags & REGEX_MATCH_BEGIN)) {
1437                                         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(curr_index, 2));
1438
1439                                         /* Check whether item is inserted. */
1440                                         EMIT_CMP(jump1, SLJIT_NOT_EQUAL, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), SLJIT_IMM, -1);
1441                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), R_NEXT_HEAD, 0);
1442                                         if (offset > 0) {
1443                                                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, offset);
1444                                         }
1445                                         EMIT_JUMP(jump2, SLJIT_JUMP);
1446
1447                                         /* Check whether old index != index. */
1448                                         EMIT_LABEL(label1);
1449                                         sljit_set_label(jump1, label1);
1450
1451                                         EMIT_OP2(SLJIT_SUB | SLJIT_SET_Z | SLJIT_SET_LESS, SLJIT_UNUSED, 0, SLJIT_MEM1(R_NEXT_STATE), offset + 2 * sizeof(sljit_sw), R_TEMP, 0);
1452                                         EMIT_JUMP(jump1, SLJIT_LESS);
1453                                         EMIT_JUMP(jump3, SLJIT_NOT_EQUAL); /* Greater. */
1454
1455                                         /* Old index == index. */
1456                                         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(curr_index, 3));
1457                                         if (search_states[value].value > 0) {
1458                                                 EMIT_CMP(jump4, SLJIT_GREATER, R_TEMP, 0, SLJIT_IMM, search_states[value].value);
1459
1460                                                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_IMM, search_states[value].value);
1461                                                 EMIT_LABEL(label1);
1462                                                 sljit_set_label(jump4, label1);
1463                                         }
1464
1465                                         EMIT_OP2(SLJIT_SUB | SLJIT_SET_GREATER_EQUAL, SLJIT_UNUSED, 0, SLJIT_MEM1(R_NEXT_STATE), offset + 3 * sizeof(sljit_sw), R_TEMP, 0);
1466                                         EMIT_JUMP(jump4, SLJIT_GREATER_EQUAL);
1467                                         EMIT_JUMP(jump5, SLJIT_JUMP);
1468
1469                                         /* Overwrite index & id. */
1470                                         EMIT_LABEL(label1);
1471                                         sljit_set_label(jump3, label1);
1472                                         sljit_set_label(jump2, label1);
1473                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + 2 * sizeof(sljit_sw), R_TEMP, 0);
1474
1475                                         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(curr_index, 3));
1476                                         if (search_states[value].value > 0) {
1477                                                 EMIT_CMP(jump3, SLJIT_GREATER, R_TEMP, 0, SLJIT_IMM, search_states[value].value);
1478
1479                                                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_IMM, search_states[value].value);
1480                                                 EMIT_LABEL(label1);
1481                                                 sljit_set_label(jump3, label1);
1482                                         }
1483
1484                                         EMIT_LABEL(label1);
1485                                         sljit_set_label(jump5, label1);
1486                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + 3 * sizeof(sljit_sw), R_TEMP, 0);
1487
1488                                         /* Exit. */
1489                                         EMIT_LABEL(label1);
1490                                         sljit_set_label(jump1, label1);
1491                                         sljit_set_label(jump4, label1);
1492                                 }
1493                                 else {
1494                                         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(curr_index, 2));
1495
1496                                         if (search_states[value].value > 0) {
1497                                                 EMIT_CMP(jump1, SLJIT_GREATER, R_TEMP, 0, SLJIT_IMM, search_states[value].value);
1498
1499                                                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_IMM, search_states[value].value);
1500                                                 EMIT_LABEL(label1);
1501                                                 sljit_set_label(jump1, label1);
1502                                         }
1503
1504                                         /* Check whether item is inserted. */
1505                                         EMIT_CMP(jump1, SLJIT_NOT_EQUAL, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), SLJIT_IMM, -1);
1506                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + sizeof(sljit_sw), R_NEXT_HEAD, 0);
1507                                         if (offset > 0) {
1508                                                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, offset);
1509                                         }
1510                                         EMIT_JUMP(jump2, SLJIT_JUMP);
1511
1512                                         /* Check whether old id >= id. */
1513                                         EMIT_LABEL(label1);
1514                                         sljit_set_label(jump1, label1);
1515
1516                                         EMIT_CMP(jump1, SLJIT_GREATER_EQUAL, SLJIT_MEM1(R_NEXT_STATE), offset + 2 * sizeof(sljit_sw), R_TEMP, 0);
1517
1518                                         EMIT_LABEL(label1);
1519                                         sljit_set_label(jump2, label1);
1520                                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), offset + 2 * sizeof(sljit_sw), R_TEMP, 0);
1521
1522                                         EMIT_LABEL(label1);
1523                                         sljit_set_label(jump1, label1);
1524                                 }
1525                         }
1526                 }
1527                 search_states[value].value = -1;
1528         }
1529
1530 #ifdef REGEX_MATCH_VERBOSE
1531         if (flags & REGEX_MATCH_VERBOSE)
1532                 printf("\n");
1533 #endif
1534         return REGEX_NO_ERROR;
1535 }
1536
1537 static int compile_end_check(struct compiler_common *compiler_common, struct sljit_label *end_check_label)
1538 {
1539         struct sljit_compiler *compiler = compiler_common->compiler;
1540         struct sljit_jump *jump;
1541         struct sljit_jump *clear_states_jump;
1542         struct sljit_label *label;
1543         struct sljit_label *leave_label;
1544         struct sljit_label *begin_loop_label;
1545
1546         /* Priority order: best_begin > best_end > best_id.
1547            In other words:
1548                if (new best_begin > old test_begin) do nothing
1549                otherwise we know that new_end > old_end, since R_CURR_INDEX ever increasing
1550                therefore we must overwrite all best_* variables (new_id also contains the highest id for this turn). */
1551
1552         /* Both R_CURR_CHAR and R_BEST_BEGIN used as temporary registers. */
1553
1554         if (!(compiler_common->flags & REGEX_MATCH_BEGIN)) {
1555                 EMIT_OP1(SLJIT_MOV, R_CURR_CHAR, 0, SLJIT_MEM1(R_CURR_STATE), TERM_REL_OFFSET_OF(0, 2));
1556                 EMIT_CMP(jump, !(compiler_common->flags & REGEX_MATCH_NON_GREEDY) ? SLJIT_LESS : SLJIT_LESS_EQUAL, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_begin), R_CURR_CHAR, 0);
1557                 sljit_set_label(jump, end_check_label);
1558
1559                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_begin), R_CURR_CHAR, 0);
1560                 if (!(compiler_common->flags & (REGEX_FAKE_MATCH_BEGIN | REGEX_FAKE_MATCH_END))) {
1561                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_end), R_CURR_INDEX, 0);
1562                 }
1563                 else {
1564                         if ((compiler_common->flags & (REGEX_FAKE_MATCH_BEGIN | REGEX_FAKE_MATCH_END)) == (REGEX_FAKE_MATCH_BEGIN | REGEX_FAKE_MATCH_END)) {
1565                                 EMIT_OP2(SLJIT_SUB, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_end), R_CURR_INDEX, 0, SLJIT_IMM, 2);
1566                         }
1567                         else {
1568                                 EMIT_OP2(SLJIT_SUB, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_end), R_CURR_INDEX, 0, SLJIT_IMM, 1);
1569                         }
1570                 }
1571                 if (compiler_common->flags & REGEX_ID_CHECK) {
1572                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_id), SLJIT_MEM1(R_CURR_STATE), TERM_REL_OFFSET_OF(0, 3));
1573                 }
1574
1575                 EMIT_CMP(clear_states_jump, SLJIT_LESS, R_CURR_CHAR, 0, R_BEST_BEGIN, 0);
1576
1577                 EMIT_LABEL(leave_label);
1578                 EMIT_OP1(SLJIT_MOV, R_BEST_BEGIN, 0, R_CURR_CHAR, 0);
1579                 EMIT_JUMP(jump, SLJIT_JUMP);
1580                 sljit_set_label(jump, end_check_label);
1581
1582                 /* A loop to clear all states, which are > (or >=) than R_CURR_CHAR. */
1583                 EMIT_LABEL(label);
1584                 sljit_set_label(clear_states_jump, label);
1585
1586                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_NEXT_HEAD, 0);
1587                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, 0);
1588
1589                 /* Begin of the loop. */
1590                 EMIT_LABEL(begin_loop_label);
1591                 EMIT_CMP(jump, SLJIT_EQUAL, R_TEMP, 0, SLJIT_IMM, 0);
1592                 sljit_set_label(jump, leave_label);
1593
1594                 EMIT_OP2(SLJIT_ADD, R_TEMP, 0, R_TEMP, 0, R_CURR_STATE, 0);
1595                 EMIT_OP1(SLJIT_MOV, R_BEST_BEGIN, 0, SLJIT_MEM1(R_TEMP), sizeof(sljit_sw));
1596                 EMIT_CMP(clear_states_jump, !(compiler_common->flags & REGEX_MATCH_NON_GREEDY) ? SLJIT_GREATER : SLJIT_GREATER_EQUAL, SLJIT_MEM1(R_TEMP), 2 * sizeof(sljit_sw), R_CURR_CHAR, 0);
1597
1598                 /* Case 1: keep this case. */
1599                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_TEMP), sizeof(sljit_sw), R_NEXT_HEAD, 0);
1600                 EMIT_OP2(SLJIT_SUB, R_NEXT_HEAD, 0, R_TEMP, 0, R_CURR_STATE, 0);
1601
1602                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_BEST_BEGIN, 0);
1603                 EMIT_JUMP(jump, SLJIT_JUMP);
1604                 sljit_set_label(jump, begin_loop_label);
1605
1606                 /* Case 2: remove this case. */
1607                 EMIT_LABEL(label);
1608                 sljit_set_label(clear_states_jump, label);
1609
1610                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_TEMP), sizeof(sljit_sw), SLJIT_IMM, -1);
1611
1612                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_BEST_BEGIN, 0);
1613                 EMIT_JUMP(jump, SLJIT_JUMP);
1614                 sljit_set_label(jump, begin_loop_label);
1615         }
1616         else {
1617                 EMIT_OP1(SLJIT_MOV, R_BEST_BEGIN, 0, SLJIT_IMM, 0);
1618                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_begin), SLJIT_IMM, 0);
1619                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_end), R_CURR_INDEX, 0);
1620                 if (compiler_common->flags & REGEX_ID_CHECK) {
1621                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_id), SLJIT_MEM1(R_CURR_STATE), TERM_REL_OFFSET_OF(0, 2));
1622                 }
1623                 EMIT_JUMP(jump, SLJIT_JUMP);
1624                 sljit_set_label(jump, end_check_label);
1625         }
1626         return REGEX_NO_ERROR;
1627 }
1628
1629 static int compile_leave_fast_forward(struct compiler_common *compiler_common, struct sljit_label *fast_forward_label)
1630 {
1631         struct sljit_compiler *compiler = compiler_common->compiler;
1632         struct stack *stack = &compiler_common->stack;
1633         struct stack_item *dfa_transitions = compiler_common->dfa_transitions;
1634         struct stack_item *search_states = compiler_common->search_states;
1635         int ind;
1636         struct sljit_jump *jump;
1637         int init_range = 1, prev_value = 0;
1638
1639         while (stack->count > 0) {
1640                 ind = stack_pop(stack)->value;
1641                 search_states[ind].value = -1;
1642                 if (search_states[ind].type >= 0) {
1643                         if (dfa_transitions[ind].type == type_char) {
1644                                 EMIT_CMP(jump, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, dfa_transitions[ind].value);
1645                                 sljit_set_label(jump, fast_forward_label);
1646                         }
1647                         else if (dfa_transitions[ind].type == type_rng_start) {
1648                                 SLJIT_ASSERT(!dfa_transitions[ind].value);
1649                                 ind++;
1650                                 while (dfa_transitions[ind].type != type_rng_end) {
1651                                         if (dfa_transitions[ind].type == type_rng_char) {
1652                                                 EMIT_CMP(jump, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, dfa_transitions[ind].value);
1653                                                 sljit_set_label(jump, fast_forward_label);
1654                                         }
1655                                         else {
1656                                                 SLJIT_ASSERT(dfa_transitions[ind].type == type_rng_left);
1657                                                 if (init_range) {
1658                                                         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_CURR_CHAR, 0);
1659                                                         init_range = 0;
1660                                                 }
1661                                                 if (dfa_transitions[ind].value != prev_value) {
1662                                                         /* Best compatibility to all archs. */
1663                                                         prev_value -= dfa_transitions[ind].value;
1664                                                         if (prev_value < 0) {
1665                                                                 EMIT_OP2(SLJIT_SUB, R_TEMP, 0, R_TEMP, 0, SLJIT_IMM, -prev_value);
1666                                                         }
1667                                                         else {
1668                                                                 EMIT_OP2(SLJIT_ADD, R_TEMP, 0, R_TEMP, 0, SLJIT_IMM, prev_value);
1669                                                         }
1670                                                         prev_value = dfa_transitions[ind].value;
1671                                                 }
1672                                                 EMIT_CMP(jump, SLJIT_LESS_EQUAL, R_TEMP, 0, SLJIT_IMM, dfa_transitions[ind + 1].value - dfa_transitions[ind].value);
1673                                                 sljit_set_label(jump, fast_forward_label);
1674                                                 ind++;
1675                                         }
1676                                         ind++;
1677                                 }
1678                         }
1679                         else {
1680                                 SLJIT_ASSERT(dfa_transitions[ind].type == type_newline);
1681                                 EMIT_CMP(jump, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, '\n');
1682                                 sljit_set_label(jump, fast_forward_label);
1683                                 EMIT_CMP(jump, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, '\r');
1684                                 sljit_set_label(jump, fast_forward_label);
1685                         }
1686                 }
1687         }
1688         return REGEX_NO_ERROR;
1689 }
1690
1691 static int compile_newline_check(struct compiler_common *compiler_common, sljit_sw ind)
1692 {
1693         struct sljit_compiler *compiler = compiler_common->compiler;
1694         struct sljit_jump *jump1;
1695         struct sljit_jump *jump2;
1696         struct sljit_label *label;
1697         sljit_sw no_states;
1698         sljit_sw offset;
1699
1700         /* Check whether a new-line character is found. */
1701         EMIT_CMP(jump1, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, '\n');
1702         EMIT_CMP(jump2, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, '\r');
1703
1704         no_states = compiler_common->no_states;
1705         offset = TERM_OFFSET_OF(compiler_common->search_states[ind].type, 1);
1706         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), offset);
1707         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_CURR_STATE), offset, SLJIT_IMM, -1);
1708         CHECK(sljit_emit_ijump(compiler, SLJIT_JUMP, SLJIT_MEM2(R_CURR_STATE, R_TEMP), 0));
1709
1710         EMIT_LABEL(label);
1711         sljit_set_label(jump1, label);
1712         sljit_set_label(jump2, label);
1713         return REGEX_NO_ERROR;
1714 }
1715
1716 #undef CHECK
1717
1718 #define CHECK(exp) \
1719         if (SLJIT_UNLIKELY(exp)) \
1720                 return 0
1721
1722 static SLJIT_INLINE void range_set_label(struct sljit_jump **range_jump_list, struct sljit_label *label)
1723 {
1724         while (*range_jump_list) {
1725                 sljit_set_label(*range_jump_list, label);
1726                 range_jump_list++;
1727         }
1728 }
1729
1730 static sljit_sw compile_range_check(struct compiler_common *compiler_common, sljit_sw ind)
1731 {
1732         struct sljit_compiler *compiler = compiler_common->compiler;
1733         struct stack_item *dfa_transitions = compiler_common->dfa_transitions;
1734         struct sljit_jump **range_jump_list = compiler_common->range_jump_list;
1735         int invert = dfa_transitions[ind].value;
1736         struct sljit_label *label;
1737         sljit_sw no_states;
1738         sljit_sw offset;
1739         int init_range = 1, prev_value = 0;
1740
1741         ind++;
1742
1743         while (dfa_transitions[ind].type != type_rng_end) {
1744                 if (dfa_transitions[ind].type == type_rng_char) {
1745                         EMIT_CMP(*range_jump_list, SLJIT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, dfa_transitions[ind].value);
1746                         range_jump_list++;
1747                 }
1748                 else {
1749                         SLJIT_ASSERT(dfa_transitions[ind].type == type_rng_left);
1750                         if (init_range) {
1751                                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_CURR_CHAR, 0);
1752                                 init_range = 0;
1753                         }
1754                         if (dfa_transitions[ind].value != prev_value) {
1755                                 /* Best compatibility to all archs. */
1756                                 prev_value -= dfa_transitions[ind].value;
1757                                 if (prev_value < 0) {
1758                                         EMIT_OP2(SLJIT_SUB, R_TEMP, 0, R_TEMP, 0, SLJIT_IMM, -prev_value);
1759                                 }
1760                                 else {
1761                                         EMIT_OP2(SLJIT_ADD, R_TEMP, 0, R_TEMP, 0, SLJIT_IMM, prev_value);
1762                                 }
1763                                 prev_value = dfa_transitions[ind].value;
1764                         }
1765                         EMIT_CMP(*range_jump_list, SLJIT_LESS_EQUAL, R_TEMP, 0, SLJIT_IMM, dfa_transitions[ind + 1].value - dfa_transitions[ind].value);
1766                         range_jump_list++;
1767                         ind++;
1768                 }
1769                 ind++;
1770         }
1771
1772         *range_jump_list = NULL;
1773
1774         if (!invert) {
1775                 no_states = compiler_common->no_states;
1776                 offset = TERM_OFFSET_OF(compiler_common->search_states[ind].type, 1);
1777                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), offset);
1778                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_CURR_STATE), offset, SLJIT_IMM, -1);
1779                 CHECK(sljit_emit_ijump(compiler, SLJIT_JUMP, SLJIT_MEM2(R_CURR_STATE, R_TEMP), 0));
1780
1781                 EMIT_LABEL(label);
1782                 range_set_label(compiler_common->range_jump_list, label);
1783                 /* Clears the jump list. */
1784                 *compiler_common->range_jump_list = NULL;
1785         }
1786         return ind;
1787 }
1788
1789 #undef TERM_OFFSET_OF
1790 #undef EMIT_OP1
1791 #undef EMIT_OP2
1792 #undef EMIT_LABEL
1793 #undef EMIT_JUMP
1794 #undef EMIT_CMP
1795 #undef CHECK
1796
1797 /* --------------------------------------------------------------------- */
1798 /*  Main compiler                                                        */
1799 /* --------------------------------------------------------------------- */
1800
1801 #define TERM_OFFSET_OF(ind, offs) (((ind) * compiler_common.no_states + (offs)) * sizeof(sljit_sw))
1802
1803 #define EMIT_OP1(type, arg1, arg2, arg3, arg4) \
1804         CHECK(sljit_emit_op1(compiler_common.compiler, type, arg1, arg2, arg3, arg4))
1805
1806 #define EMIT_OP2(type, arg1, arg2, arg3, arg4, arg5, arg6) \
1807         CHECK(sljit_emit_op2(compiler_common.compiler, type, arg1, arg2, arg3, arg4, arg5, arg6))
1808
1809 #define EMIT_LABEL(label) \
1810         label = sljit_emit_label(compiler_common.compiler); \
1811         CHECK(!label)
1812
1813 #define EMIT_JUMP(jump, type) \
1814         jump = sljit_emit_jump(compiler_common.compiler, type); \
1815         CHECK(!jump)
1816
1817 #define EMIT_CMP(jump, type, arg1, arg2, arg3, arg4) \
1818         jump = sljit_emit_cmp(compiler_common.compiler, type, arg1, arg2, arg3, arg4); \
1819         CHECK(!jump)
1820
1821 /* A do {} while(0) expression helps to avoid goto statements. */
1822 #define BEGIN_GUARD \
1823         do {
1824
1825 #define END_GUARD \
1826         } while(0);
1827
1828 #define CHECK(exp) \
1829         if (SLJIT_UNLIKELY(exp)) \
1830                 break;
1831
1832 struct regex_machine* regex_compile(const regex_char_t *regex_string, int length, int re_flags, int *error)
1833 {
1834         struct compiler_common compiler_common;
1835         sljit_sw ind;
1836         int error_code, done, suggest_fast_forward;
1837         /* ID of an empty match (-1 if not reachable). */
1838         int empty_match_id;
1839
1840         struct sljit_jump *jump;
1841         struct sljit_jump *best_match_found_jump;
1842         struct sljit_jump *fast_forward_jump = NULL;
1843         struct sljit_jump *length_is_zero_jump;
1844         struct sljit_jump *end_check_jump = NULL;
1845         struct sljit_jump *best_match_check_jump = NULL;
1846         struct sljit_jump *non_greedy_end_jump = NULL;
1847         struct sljit_label *label;
1848         struct sljit_label *end_check_label = NULL;
1849         struct sljit_label *start_label;
1850         struct sljit_label *fast_forward_label;
1851         struct sljit_label *fast_forward_return_label;
1852
1853         if (error)
1854                 *error = REGEX_NO_ERROR;
1855 #ifdef REGEX_MATCH_VERBOSE
1856         compiler_common.flags = re_flags & (REGEX_MATCH_BEGIN | REGEX_MATCH_END | REGEX_MATCH_NON_GREEDY | REGEX_NEWLINE | REGEX_MATCH_VERBOSE);
1857 #else
1858         compiler_common.flags = re_flags & (REGEX_MATCH_BEGIN | REGEX_MATCH_END | REGEX_MATCH_NON_GREEDY | REGEX_NEWLINE);
1859 #endif
1860
1861         /* Step 1: parsing (Left->Right).
1862            Syntax check and AST generator. */
1863         error_code = parse(regex_string, length, &compiler_common);
1864         if (error_code) {
1865                 stack_destroy(&compiler_common.stack);
1866                 if (error)
1867                         *error = error_code;
1868                 return NULL;
1869         }
1870
1871         /* Step 2: generating branches (Right->Left). */
1872         error_code = generate_transitions(&compiler_common);
1873         stack_destroy(&compiler_common.stack);
1874         stack_destroy(&compiler_common.depth);
1875         if (error_code) {
1876                 if (compiler_common.dfa_transitions)
1877                         SLJIT_FREE(compiler_common.dfa_transitions, NULL);
1878                 if (error)
1879                         *error = error_code;
1880                 return NULL;
1881         }
1882
1883         /* Step 3: Generate necessary data for depth-first search (Left->Right). */
1884         error_code = generate_search_states(&compiler_common);
1885         if (error_code) {
1886                 SLJIT_FREE(compiler_common.dfa_transitions, NULL);
1887                 if (error)
1888                         *error = error_code;
1889                 return NULL;
1890         }
1891
1892 #ifdef REGEX_MATCH_VERBOSE
1893         if (compiler_common.flags & REGEX_MATCH_VERBOSE)
1894                 verbose_transitions(&compiler_common);
1895 #endif
1896
1897         /* Step 4: Left->Right generate code. */
1898         stack_init(&compiler_common.stack);
1899         stack_init(&compiler_common.depth);
1900         done = 0;
1901         compiler_common.machine = NULL;
1902         compiler_common.compiler = NULL;
1903         compiler_common.range_jump_list = NULL;
1904
1905         BEGIN_GUARD
1906
1907         compiler_common.machine = (struct regex_machine*)SLJIT_MALLOC(sizeof(struct regex_machine) + (compiler_common.terms_size - 1) * sizeof(sljit_uw), NULL);
1908         CHECK(!compiler_common.machine);
1909
1910         compiler_common.compiler = sljit_create_compiler(NULL, NULL);
1911         CHECK(!compiler_common.compiler);
1912
1913         if (compiler_common.longest_range_size > 0) {
1914                 compiler_common.range_jump_list = (struct sljit_jump**)SLJIT_MALLOC(sizeof(struct sljit_jump*) * compiler_common.longest_range_size, NULL);
1915                 CHECK(!compiler_common.range_jump_list);
1916         }
1917
1918         if ((compiler_common.flags & REGEX_ID_CHECK) && !(compiler_common.flags & REGEX_MATCH_BEGIN))
1919                 compiler_common.no_states = 4;
1920         else if (!(compiler_common.flags & REGEX_ID_CHECK) && (compiler_common.flags & REGEX_MATCH_BEGIN))
1921                 compiler_common.no_states = 2;
1922         else
1923                 compiler_common.no_states = 3;
1924
1925         compiler_common.machine->flags = compiler_common.flags;
1926         compiler_common.machine->no_states = compiler_common.no_states;
1927         compiler_common.machine->size = compiler_common.machine->no_states * compiler_common.terms_size;
1928
1929         /* Study the regular expression. */
1930         empty_match_id = -1;
1931         suggest_fast_forward = 1;
1932         if (!(compiler_common.flags & REGEX_FAKE_MATCH_BEGIN)) {
1933                 CHECK(trace_transitions(0, &compiler_common));
1934                 while (compiler_common.stack.count > 0) {
1935                         ind = stack_pop(&compiler_common.stack)->value;
1936                         if (compiler_common.search_states[ind].type == 0) {
1937                                 SLJIT_ASSERT(compiler_common.dfa_transitions[ind].type == type_end);
1938                                 suggest_fast_forward = 0;
1939                                 empty_match_id = compiler_common.search_states[ind].value;
1940                         }
1941                         else if (compiler_common.search_states[ind].type > 0) {
1942                                 SLJIT_ASSERT(compiler_common.dfa_transitions[ind].type != type_end);
1943                                 if (compiler_common.dfa_transitions[ind].type == type_rng_start && compiler_common.dfa_transitions[ind].value)
1944                                         suggest_fast_forward = 0;
1945                         }
1946                         compiler_common.search_states[ind].value = -1;
1947                 }
1948         }
1949         else {
1950                 SLJIT_ASSERT(compiler_common.dfa_transitions[1].type == type_newline);
1951                 CHECK(trace_transitions(1, &compiler_common));
1952                 while (compiler_common.stack.count > 0) {
1953                         ind = stack_pop(&compiler_common.stack)->value;
1954                         if (compiler_common.search_states[ind].type == 0) {
1955                                 SLJIT_ASSERT(compiler_common.dfa_transitions[ind].type == type_end);
1956                                 suggest_fast_forward = 0;
1957                                 empty_match_id = compiler_common.search_states[ind].value;
1958                         }
1959                         compiler_common.search_states[ind].value = -1;
1960                 }
1961         }
1962
1963         /* Step 4.1: Generate entry. */
1964         CHECK(sljit_emit_enter(compiler_common.compiler, 0, SLJIT_ARG1(SW) | SLJIT_ARG2(SW) | SLJIT_ARG3(SW), 5, 5, 0, 0, 0));
1965
1966         /* Copy arguments to their place. */
1967         EMIT_OP1(SLJIT_MOV, R_REGEX_MATCH, 0, SLJIT_S0, 0);
1968         EMIT_OP1(SLJIT_MOV, R_STRING, 0, SLJIT_S1, 0);
1969         EMIT_OP2(SLJIT_ADD, R_LENGTH, 0, SLJIT_S2, 0, SLJIT_IMM, 1);
1970
1971         /* Init global registers. */
1972         EMIT_OP1(SLJIT_MOV, R_CURR_STATE, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, current));
1973         EMIT_OP1(SLJIT_MOV, R_NEXT_STATE, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, next));
1974         EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, head));
1975         EMIT_OP1(SLJIT_MOV, R_BEST_BEGIN, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_begin));
1976         EMIT_OP1(SLJIT_MOV, R_CURR_INDEX, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, index));
1977
1978         /* Check whether the best match has already found in a previous frame. */
1979         EMIT_CMP(jump, SLJIT_EQUAL, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_quit), SLJIT_IMM, 0);
1980         EMIT_JUMP(best_match_found_jump, SLJIT_JUMP);
1981
1982 #ifdef REGEX_MATCH_VERBOSE
1983         if (compiler_common.flags & REGEX_MATCH_VERBOSE)
1984                 printf("\n-----------------\nTrace\n-----------------\n");
1985 #endif
1986
1987         /* Step 4.2: Generate code for state 0. */
1988         EMIT_LABEL(label);
1989         sljit_emit_op0(compiler_common.compiler, SLJIT_ENDBR);
1990         compiler_common.machine->entry_addrs[0] = (sljit_uw)label;
1991
1992         /* Swapping current and next. */
1993         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_CURR_STATE, 0);
1994         EMIT_OP1(SLJIT_MOV, R_CURR_STATE, 0, R_NEXT_STATE, 0);
1995         EMIT_OP1(SLJIT_MOV, R_NEXT_STATE, 0, R_TEMP, 0);
1996
1997         /* Checking whether the best case needs to be updated. */
1998         if (!(compiler_common.flags & REGEX_MATCH_END)) {
1999                 EMIT_CMP(end_check_jump, SLJIT_NOT_EQUAL, SLJIT_MEM1(R_CURR_STATE), TERM_REL_OFFSET_OF(0, 1), SLJIT_IMM, -1);
2000                 EMIT_LABEL(end_check_label);
2001         }
2002         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_NEXT_STATE), TERM_REL_OFFSET_OF(0, 1), SLJIT_IMM, -1);
2003         EMIT_OP2(SLJIT_ADD, R_CURR_INDEX, 0, R_CURR_INDEX, 0, SLJIT_IMM, 1);
2004
2005         /* Checking whether best case has already found. */
2006         if (!(compiler_common.flags & REGEX_MATCH_END) || (compiler_common.flags & REGEX_MATCH_BEGIN)) {
2007                 if (!(compiler_common.flags & REGEX_MATCH_BEGIN)) {
2008                         /* We can bail out if no more active states remain and R_BEST_BEGIN != -1. */
2009                         EMIT_CMP(best_match_check_jump, SLJIT_NOT_EQUAL, R_BEST_BEGIN, 0, SLJIT_IMM, -1);
2010                 }
2011                 else {
2012                         /* We can bail out if no more active states remain (regardless of R_BEST_BEGIN). */
2013                         EMIT_CMP(best_match_check_jump, SLJIT_EQUAL, R_NEXT_HEAD, 0, SLJIT_IMM, 0);
2014                 }
2015         }
2016
2017         EMIT_LABEL(start_label);
2018         sljit_set_label(jump, start_label);
2019
2020         if (!(compiler_common.flags & REGEX_MATCH_BEGIN) && suggest_fast_forward) {
2021                 EMIT_CMP(fast_forward_jump, SLJIT_NOT_EQUAL, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_forward), SLJIT_IMM, 0);
2022         }
2023
2024         /* Loading the next character. */
2025         EMIT_OP2(SLJIT_SUB | SLJIT_SET_Z, R_LENGTH, 0, R_LENGTH, 0, SLJIT_IMM, 1);
2026         EMIT_JUMP(length_is_zero_jump, SLJIT_EQUAL);
2027
2028         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_STRING, 0);
2029 #ifdef REGEX_USE_8BIT_CHARS
2030         EMIT_OP1(SLJIT_MOV_U8, R_CURR_CHAR, 0, SLJIT_MEM1(R_TEMP), 0);
2031         EMIT_OP2(SLJIT_ADD, R_TEMP, 0, R_TEMP, 0, SLJIT_IMM, 1);
2032 #else
2033         EMIT_OP1(SLJIT_MOV_UH, R_CURR_CHAR, 0, SLJIT_MEM1(R_TEMP), 0);
2034         EMIT_OP2(SLJIT_ADD, R_TEMP, 0, R_TEMP, 0, SLJIT_IMM, 2);
2035 #endif
2036         EMIT_OP1(SLJIT_MOV, R_STRING, 0, R_TEMP, 0);
2037
2038 #ifdef REGEX_MATCH_VERBOSE
2039         if (compiler_common.flags & REGEX_MATCH_VERBOSE) {
2040                 printf("(%3d): ", 0);
2041                 CHECK(trace_transitions(0, &compiler_common));
2042                 while (compiler_common.stack.count > 0) {
2043                         ind = stack_pop(&compiler_common.stack)->value;
2044                         if (compiler_common.search_states[ind].type >= 0)
2045                                 printf("-> (%3d:%3d) ", compiler_common.search_states[ind].type, compiler_common.search_states[ind].value);
2046                         compiler_common.search_states[ind].value = -1;
2047                 }
2048                 printf("\n");
2049         }
2050 #endif
2051
2052         EMIT_LABEL(fast_forward_return_label);
2053         if (!(compiler_common.flags & REGEX_MATCH_BEGIN)) {
2054                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_forward), SLJIT_IMM, 1);
2055                 if (!(compiler_common.flags & REGEX_MATCH_END)) {
2056                         EMIT_CMP(jump, SLJIT_NOT_EQUAL, R_BEST_BEGIN, 0, SLJIT_IMM, -1);
2057                 }
2058
2059                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_CURR_INDEX, 0);
2060                 CHECK(compile_uncond_tran(&compiler_common, R_NEXT_STATE));
2061                 /* And branching to the first state. */
2062                 CHECK(sljit_emit_ijump(compiler_common.compiler, SLJIT_JUMP, SLJIT_MEM2(R_CURR_STATE, R_TEMP), 0));
2063
2064                 if (!(compiler_common.flags & REGEX_MATCH_END)) {
2065                         EMIT_LABEL(label);
2066                         sljit_set_label(jump, label);
2067                 }
2068         }
2069         /* This is the case where we only have to reset the R_NEXT_HEAD. */
2070         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, R_NEXT_HEAD, 0);
2071         EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, 0);
2072         CHECK(sljit_emit_ijump(compiler_common.compiler, SLJIT_JUMP, SLJIT_MEM2(R_CURR_STATE, R_TEMP), 0));
2073
2074         /* Fast-forward loop. */
2075         if (fast_forward_jump) {
2076                 /* Quit from fast-forward loop. */
2077                 EMIT_LABEL(fast_forward_label);
2078                 EMIT_OP2(SLJIT_SUB, R_TEMP, 0, R_NEXT_HEAD, 0, SLJIT_IMM, 1);
2079                 EMIT_OP1(SLJIT_MOV, R_LENGTH, 0, R_NEXT_STATE, 0);
2080                 EMIT_OP1(SLJIT_MOV, R_STRING, 0, R_CURR_STATE, 0);
2081                 EMIT_OP1(SLJIT_MOV, R_CURR_INDEX, 0, R_NEXT_HEAD, 0);
2082                 EMIT_OP1(SLJIT_MOV, R_NEXT_STATE, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, next));
2083                 EMIT_OP1(SLJIT_MOV, R_CURR_STATE, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, current));
2084                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, head));
2085
2086                 /* Update the start field of the locations. */
2087                 CHECK(trace_transitions(0, &compiler_common));
2088                 while (compiler_common.stack.count > 0) {
2089                         ind = stack_pop(&compiler_common.stack)->value;
2090                         if (compiler_common.search_states[ind].type >= 0) {
2091                                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(compiler_common.search_states[ind].type, 2), R_TEMP, 0);
2092                         }
2093                         compiler_common.search_states[ind].value = -1;
2094                 }
2095                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_forward), SLJIT_IMM, 0);
2096                 EMIT_JUMP(jump, SLJIT_JUMP);
2097                 sljit_set_label(jump, fast_forward_return_label);
2098
2099                 /* Start fast-forward. */
2100                 EMIT_LABEL(label);
2101                 sljit_set_label(fast_forward_jump, label);
2102
2103                 /* Moving everything to registers. */
2104                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, next), R_NEXT_STATE, 0);
2105                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, current), R_CURR_STATE, 0);
2106                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, head), R_NEXT_HEAD, 0);
2107                 EMIT_OP1(SLJIT_MOV, R_NEXT_STATE, 0, R_LENGTH, 0);
2108                 EMIT_OP1(SLJIT_MOV, R_CURR_STATE, 0, R_STRING, 0);
2109                 EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, R_CURR_INDEX, 0);
2110
2111                 /* Fast forward mainloop. */
2112                 EMIT_LABEL(label);
2113                 EMIT_OP2(SLJIT_SUB | SLJIT_SET_Z, R_NEXT_STATE, 0, R_NEXT_STATE, 0, SLJIT_IMM, 1);
2114                 EMIT_JUMP(fast_forward_jump, SLJIT_EQUAL);
2115
2116 #ifdef REGEX_USE_8BIT_CHARS
2117                 EMIT_OP1(SLJIT_MOV_U8, R_CURR_CHAR, 0, SLJIT_MEM1(R_CURR_STATE), 0);
2118                 EMIT_OP2(SLJIT_ADD, R_CURR_STATE, 0, R_CURR_STATE, 0, SLJIT_IMM, 1);
2119 #else
2120                 EMIT_OP1(SLJIT_MOV_UH, R_CURR_CHAR, 0, SLJIT_MEM1(R_CURR_STATE), 0);
2121                 EMIT_OP2(SLJIT_ADD, R_CURR_STATE, 0, R_CURR_STATE, 0, SLJIT_IMM, 2);
2122 #endif
2123
2124                 CHECK(trace_transitions(0, &compiler_common));
2125                 CHECK(compile_leave_fast_forward(&compiler_common, fast_forward_label));
2126
2127                 EMIT_OP2(SLJIT_ADD, R_NEXT_HEAD, 0, R_NEXT_HEAD, 0, SLJIT_IMM, 1);
2128                 EMIT_JUMP(jump, SLJIT_JUMP);
2129                 sljit_set_label(jump, label);
2130
2131                 /* String is finished. */
2132                 EMIT_LABEL(label);
2133                 sljit_set_label(fast_forward_jump, label);
2134                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, index), R_NEXT_HEAD, 0);
2135                 EMIT_JUMP(fast_forward_jump, SLJIT_JUMP);
2136         }
2137
2138         /* End check. */
2139         if (end_check_jump) {
2140                 EMIT_LABEL(label);
2141                 sljit_set_label(end_check_jump, label);
2142
2143                 if (!(compiler_common.flags & REGEX_MATCH_NON_GREEDY) || !(compiler_common.flags & REGEX_MATCH_BEGIN)) {
2144                         CHECK(compile_end_check(&compiler_common, end_check_label));
2145                 }
2146                 else {
2147                         /* Since we leave, we do not need to update the R_BEST_BEGIN. */
2148                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_begin), SLJIT_IMM, 0);
2149                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_end), R_CURR_INDEX, 0);
2150                         if (compiler_common.flags & REGEX_ID_CHECK) {
2151                                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, best_id), SLJIT_MEM1(R_CURR_STATE), TERM_REL_OFFSET_OF(0, 2));
2152                         }
2153                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_quit), SLJIT_IMM, 1);
2154                         EMIT_JUMP(non_greedy_end_jump, SLJIT_JUMP);
2155                 }
2156         }
2157
2158         /* Finish check. */
2159         if (best_match_check_jump) {
2160                 EMIT_LABEL(label);
2161                 sljit_set_label(best_match_check_jump, label);
2162
2163                 if (!(compiler_common.flags & REGEX_MATCH_BEGIN)) {
2164                         EMIT_CMP(jump, SLJIT_NOT_EQUAL, R_NEXT_HEAD, 0, SLJIT_IMM, 0);
2165                         sljit_set_label(jump, start_label);
2166                 }
2167                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, fast_quit), SLJIT_IMM, 1);
2168         }
2169
2170         /* Leaving matching and storing the necessary values. */
2171         EMIT_LABEL(label);
2172         sljit_set_label(length_is_zero_jump, label);
2173         if (non_greedy_end_jump)
2174                 sljit_set_label(non_greedy_end_jump, label);
2175
2176         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, index), R_CURR_INDEX, 0);
2177         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, head), R_NEXT_HEAD, 0);
2178         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, next), R_NEXT_STATE, 0);
2179         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_REGEX_MATCH), SLJIT_OFFSETOF(struct regex_match, current), R_CURR_STATE, 0);
2180
2181         /* Exit from JIT. */
2182         EMIT_LABEL(label);
2183         sljit_set_label(best_match_found_jump, label);
2184         if (fast_forward_jump)
2185                 sljit_set_label(fast_forward_jump, label);
2186         CHECK(sljit_emit_return(compiler_common.compiler, SLJIT_UNUSED, 0, 0));
2187
2188         for (ind = 1; ind < compiler_common.dfa_size - 1; ind++) {
2189                 if (compiler_common.search_states[ind].type >= 0) {
2190                         SLJIT_ASSERT(compiler_common.search_states[ind].type < compiler_common.terms_size);
2191                         EMIT_LABEL(label);
2192                         sljit_emit_op0(compiler_common.compiler, SLJIT_ENDBR);
2193                         compiler_common.machine->entry_addrs[compiler_common.search_states[ind].type] = (sljit_uw)label;
2194
2195                         if (compiler_common.dfa_transitions[ind].type == type_char) {
2196                                 EMIT_CMP(jump, SLJIT_NOT_EQUAL, R_CURR_CHAR, 0, SLJIT_IMM, compiler_common.dfa_transitions[ind].value);
2197                         }
2198                         else if (compiler_common.dfa_transitions[ind].type == type_rng_start) {
2199                                 ind = compile_range_check(&compiler_common, ind);
2200                                 CHECK(!ind);
2201                         }
2202                         else {
2203                                 SLJIT_ASSERT(compiler_common.dfa_transitions[ind].type == type_newline);
2204                                 CHECK(compile_newline_check(&compiler_common, ind));
2205                         }
2206
2207                         CHECK(trace_transitions(ind, &compiler_common));
2208 #ifdef REGEX_MATCH_VERBOSE
2209                         if (compiler_common.flags & REGEX_MATCH_VERBOSE)
2210                                 printf("(%3d): ", compiler_common.search_states[ind].type);
2211 #endif
2212                         CHECK(compile_cond_tran(&compiler_common, compiler_common.search_states[ind].type));
2213
2214                         if (compiler_common.dfa_transitions[ind].type == type_char) {
2215                                 EMIT_LABEL(label);
2216                                 sljit_set_label(jump, label);
2217                         }
2218                         else if (compiler_common.dfa_transitions[ind].type == type_rng_end) {
2219                                 EMIT_LABEL(label);
2220                                 range_set_label(compiler_common.range_jump_list, label);
2221                         }
2222                         else {
2223                                 SLJIT_ASSERT(compiler_common.dfa_transitions[ind].type == type_newline);
2224                         }
2225
2226                         /* Branch to the next item in the list. */
2227                         EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(compiler_common.search_states[ind].type, 1));
2228                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(R_CURR_STATE), TERM_OFFSET_OF(compiler_common.search_states[ind].type, 1), SLJIT_IMM, -1);
2229                         CHECK(sljit_emit_ijump(compiler_common.compiler, SLJIT_JUMP, SLJIT_MEM2(R_CURR_STATE, R_TEMP), 0));
2230                 }
2231         }
2232
2233         if (ind == compiler_common.dfa_size - 1) {
2234                 /* Generate an init stub function. */
2235                 EMIT_LABEL(label);
2236                 CHECK(sljit_emit_enter(compiler_common.compiler, 0, SLJIT_ARG1(SW) | SLJIT_ARG2(SW), 3, 3, 0, 0, 0));
2237
2238                 if (empty_match_id == -1) {
2239                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(SLJIT_S1), SLJIT_OFFSETOF(struct regex_match, best_begin), SLJIT_IMM, -1);
2240                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(SLJIT_S1), SLJIT_OFFSETOF(struct regex_match, best_id), SLJIT_IMM, 0);
2241                 }
2242                 else {
2243                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(SLJIT_S1), SLJIT_OFFSETOF(struct regex_match, best_begin), SLJIT_IMM, 0);
2244                         EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(SLJIT_S1), SLJIT_OFFSETOF(struct regex_match, best_id), SLJIT_IMM, empty_match_id);
2245                 }
2246
2247                 EMIT_OP1(SLJIT_MOV, SLJIT_MEM1(SLJIT_S1), SLJIT_OFFSETOF(struct regex_match, index), SLJIT_IMM, !(compiler_common.flags & REGEX_FAKE_MATCH_BEGIN) ? 1 : 2);
2248
2249                 if (!(compiler_common.flags & REGEX_MATCH_NON_GREEDY) || empty_match_id == -1) {
2250                         /* The else is a really rare event, so we still generate an empty function instead of a runtime pointer check. */
2251                         SLJIT_ASSERT(R_CURR_STATE == SLJIT_S0);
2252                         if (!(compiler_common.flags & REGEX_MATCH_BEGIN)) {
2253                                 /* R_CURR_INDEX (put to R_TEMP) is zero. */
2254                                 EMIT_OP1(SLJIT_MOV, R_TEMP, 0, SLJIT_IMM, 0);
2255                         }
2256                         CHECK(compile_uncond_tran(&compiler_common, R_CURR_STATE));
2257                 }
2258                 else {
2259                         EMIT_OP1(SLJIT_MOV, R_NEXT_HEAD, 0, SLJIT_IMM, 0);
2260                 }
2261                 CHECK(sljit_emit_return(compiler_common.compiler, SLJIT_MOV, R_NEXT_HEAD, 0));
2262
2263                 compiler_common.machine->continue_match = sljit_generate_code(compiler_common.compiler);
2264 #ifndef SLJIT_INDIRECT_CALL
2265                 compiler_common.machine->u.init_match = (void*)(sljit_sw)sljit_get_label_addr(label);
2266 #else
2267                 sljit_set_function_context(&compiler_common.machine->u.init_match, &compiler_common.machine->context, sljit_get_label_addr(label), regex_compile);
2268 #endif
2269 #ifdef REGEX_MATCH_VERBOSE
2270                 if (compiler_common.flags & REGEX_MATCH_VERBOSE)
2271                         printf("Continue match: %p Init match: %p\n\n", compiler_common.machine->continue_match, compiler_common.machine->u.init_match);
2272 #endif
2273                 if (compiler_common.machine->continue_match) {
2274                         for (ind = 0; ind < compiler_common.terms_size; ++ind)
2275                                 compiler_common.machine->entry_addrs[ind] = sljit_get_label_addr((struct sljit_label*)compiler_common.machine->entry_addrs[ind]);
2276                         done = 1;
2277                 }
2278         }
2279         END_GUARD
2280
2281         stack_destroy(&compiler_common.stack);
2282         stack_destroy(&compiler_common.depth);
2283         SLJIT_FREE(compiler_common.dfa_transitions, NULL);
2284         SLJIT_FREE(compiler_common.search_states, NULL);
2285         if (compiler_common.range_jump_list)
2286                 SLJIT_FREE(compiler_common.range_jump_list, NULL);
2287         if (compiler_common.compiler)
2288                 sljit_free_compiler(compiler_common.compiler);
2289         if (done)
2290                 return compiler_common.machine;
2291
2292         if (compiler_common.machine) {
2293                 SLJIT_FREE(compiler_common.machine, NULL);
2294         }
2295         if (error)
2296                 *error = REGEX_MEMORY_ERROR;
2297         return NULL;
2298 }
2299
2300 #undef TERM_OFFSET_OF
2301 #undef EMIT_OP1
2302 #undef EMIT_OP2
2303 #undef EMIT_LABEL
2304 #undef EMIT_JUMP
2305 #undef EMIT_CMP
2306 #undef BEGIN_GUARD
2307 #undef END_GUARD
2308 #undef CHECK
2309
2310 void regex_free_machine(struct regex_machine *machine)
2311 {
2312         sljit_free_code(machine->continue_match, NULL);
2313         SLJIT_FREE(machine, NULL);
2314 }
2315
2316 const char* regex_get_platform_name(void)
2317 {
2318         return sljit_get_platform_name();
2319 }
2320
2321 /* --------------------------------------------------------------------- */
2322 /*  Mathching utilities                                                  */
2323 /* --------------------------------------------------------------------- */
2324
2325 struct regex_match* regex_begin_match(struct regex_machine *machine)
2326 {
2327         sljit_sw *ptr1;
2328         sljit_sw *ptr2;
2329         sljit_sw *end;
2330         sljit_sw *entry_addrs;
2331
2332         struct regex_match *match = (struct regex_match*)SLJIT_MALLOC(sizeof(struct regex_match) + (machine->size * 2 - 1) * sizeof(sljit_sw), NULL);
2333         if (!match)
2334                 return NULL;
2335
2336         ptr1 = match->states;
2337         ptr2 = match->states + machine->size;
2338         end = ptr2;
2339         entry_addrs = (sljit_sw*)machine->entry_addrs;
2340
2341         match->current = ptr1;
2342         match->next = ptr2;
2343         match->head = 0;
2344         match->machine = machine;
2345
2346         /* Init machine states. */
2347         switch (machine->no_states) {
2348         case 2:
2349                 while (ptr1 < end) {
2350                         *ptr1++ = *entry_addrs;
2351                         *ptr2++ = *entry_addrs++;
2352                         *ptr1++ = -1;
2353                         *ptr2++ = -1;
2354                 }
2355                 break;
2356
2357         case 3:
2358                 while (ptr1 < end) {
2359                         *ptr1++ = *entry_addrs;
2360                         *ptr2++ = *entry_addrs++;
2361                         *ptr1++ = -1;
2362                         *ptr2++ = -1;
2363                         *ptr1++ = 0;
2364                         *ptr2++ = 0;
2365                 }
2366                 break;
2367
2368         case 4:
2369                 while (ptr1 < end) {
2370                         *ptr1++ = *entry_addrs;
2371                         *ptr2++ = *entry_addrs++;
2372                         *ptr1++ = -1;
2373                         *ptr2++ = -1;
2374                         *ptr1++ = 0;
2375                         *ptr2++ = 0;
2376                         *ptr1++ = 0;
2377                         *ptr2++ = 0;
2378                 }
2379                 break;
2380
2381         default:
2382                 SLJIT_UNREACHABLE();
2383                 break;
2384         }
2385
2386         SLJIT_ASSERT(ptr1 == end);
2387
2388         match->u.continue_match = machine->continue_match;
2389
2390         regex_reset_match(match);
2391         return match;
2392 }
2393
2394 void regex_reset_match(struct regex_match *match)
2395 {
2396         struct regex_machine *machine = match->machine;
2397         sljit_sw current, ind;
2398         sljit_sw *current_ptr;
2399
2400         match->best_end = 0;
2401         match->fast_quit = 0;
2402         match->fast_forward = 0;
2403
2404         if (match->head != 0) {
2405                 /* Clear the current state. */
2406                 current = match->head;
2407                 current_ptr = match->current;
2408                 do {
2409                         ind = (current / sizeof(sljit_sw)) + 1;
2410                         current = current_ptr[ind];
2411                         current_ptr[ind] = -1;
2412                 } while (current != 0);
2413         }
2414         match->head = machine->u.call_init(match->current, match);
2415 }
2416
2417 void regex_free_match(struct regex_match *match)
2418 {
2419         SLJIT_FREE(match, NULL);
2420 }
2421
2422 void regex_continue_match(struct regex_match *match, const regex_char_t *input_string, int length)
2423 {
2424         match->u.call_continue(match, input_string, length);
2425 }
2426
2427 int regex_get_result(struct regex_match *match, int *end, int *id)
2428 {
2429         int flags = match->machine->flags;
2430         sljit_sw no_states;
2431
2432         *end = match->best_end;
2433         *id = match->best_id;
2434         if (!(flags & (REGEX_MATCH_END | REGEX_FAKE_MATCH_END)))
2435                 return match->best_begin;
2436
2437         if (flags & REGEX_FAKE_MATCH_END) {
2438                 SLJIT_ASSERT(!(flags & (REGEX_MATCH_BEGIN | REGEX_MATCH_END)));
2439                 if (match->best_begin != -1)
2440                         return match->best_begin;
2441
2442                 no_states = match->machine->no_states;
2443                 if (match->current[no_states + 1] == -1)
2444                         return -1;
2445                 if (flags & REGEX_ID_CHECK)
2446                         *id = match->current[no_states + 3];
2447                 if (!(flags & REGEX_FAKE_MATCH_BEGIN))
2448                         *end = match->index - 1;
2449                 else
2450                         *end = match->index - 2;
2451                 return match->current[no_states + 2];
2452         }
2453         else {
2454                 /* Check the status of the last code. */
2455                 if (!(flags & REGEX_MATCH_BEGIN)) {
2456                         /* No shortcut in this case. */
2457                         if (!(flags & REGEX_ID_CHECK)) {
2458                                 if (match->current[1] == -1)
2459                                         return -1;
2460                                 *end = match->index - 1;
2461                                 return match->current[2];
2462                         }
2463
2464                         if (match->current[1] == -1)
2465                                 return -1;
2466                         *end = match->index - 1;
2467                         *id = match->current[3];
2468                         return match->current[2];
2469                 }
2470
2471                 /* Shortcut is possible in this case. */
2472                 if (!(flags & REGEX_ID_CHECK)) {
2473                         if (match->current[1] == -1 || match->head == -1)
2474                                 return -1;
2475                         *end = match->index - 1;
2476                         return 0;
2477                 }
2478
2479                 if (match->current[1] == -1 || match->head == -1)
2480                         return -1;
2481                 *end = match->index - 1;
2482                 *id = match->current[2];
2483                 return 0;
2484         }
2485 }
2486
2487 int regex_is_match_finished(struct regex_match *match)
2488 {
2489         return match->fast_quit;
2490 }
2491
2492 #ifdef REGEX_MATCH_VERBOSE
2493 void regex_continue_match_debug(struct regex_match *match, const regex_char_t *input_string, int length)
2494 {
2495         sljit_sw *ptr;
2496         sljit_sw *end;
2497         sljit_sw count;
2498 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
2499         sljit_sw current;
2500 #endif
2501         sljit_sw no_states = match->machine->no_states;
2502         sljit_sw len = match->machine->size;
2503
2504         while (length > 0) {
2505                 match->u.call_continue(match, input_string, 1);
2506
2507                 if (match->fast_forward) {
2508                         if (match->machine->flags & REGEX_MATCH_VERBOSE)
2509                                 printf("fast forward\n");
2510                 }
2511
2512                 /* Verbose (first). */
2513                 if (match->machine->flags & REGEX_MATCH_VERBOSE) {
2514                         ptr = match->current;
2515                         end = ptr + len;
2516                         count = 0;
2517                         printf("'%c' (%3ld->%3ld [%3ld]) ", *input_string, (long)match->best_begin, (long)match->best_end, (long)match->best_id);
2518                         while (ptr < end) {
2519                                 printf("[%3ld:", (long)count++);
2520                                 switch (no_states) {
2521                                 case 2:
2522                                         if (ptr[1] != -1)
2523                                                 printf("+] ");
2524                                         else
2525                                                 printf(" ] ");
2526                                         break;
2527
2528                                 case 3:
2529                                         if (ptr[1] != -1)
2530                                                 printf("+,%3ld] ", (long)ptr[2]);
2531                                         else
2532                                                 printf(" ,XXX] ");
2533                                         break;
2534
2535                                 case 4:
2536                                         if (ptr[1] != -1)
2537                                                 printf("+,%3ld,%3ld] ", (long)ptr[2], (long)ptr[3]);
2538                                         else
2539                                                 printf(" ,XXX,XXX] ");
2540                                         break;
2541                                 }
2542                                 ptr += no_states;
2543                         }
2544                         printf("\n");
2545                 }
2546
2547 #if (defined SLJIT_DEBUG && SLJIT_DEBUG)
2548                 /* Sanity check (later). */
2549                 ptr = match->next;
2550                 end = ptr + len;
2551                 while (ptr < end) {
2552                         SLJIT_ASSERT(ptr[1] == -1);
2553                         ptr += no_states;
2554                 }
2555
2556                 /* Check number of active elements. */
2557                 ptr = match->current + no_states;
2558                 end = ptr + len - no_states;
2559                 count = 0;
2560                 while (ptr < end) {
2561                         if (ptr[1] != -1)
2562                                 count++;
2563                         ptr += no_states;
2564                 }
2565
2566                 /* Check chain list. */
2567                 current = match->head;
2568                 ptr = match->current;
2569                 while (current != 0) {
2570                         SLJIT_ASSERT(current >= 0 && current < len * sizeof(sljit_sw));
2571                         SLJIT_ASSERT((current % (no_states * sizeof(sljit_sw))) == 0);
2572                         SLJIT_ASSERT(count > 0);
2573                         current = ptr[(current / sizeof(sljit_sw)) + 1];
2574                         count--;
2575                 }
2576                 SLJIT_ASSERT(count == 0);
2577 #endif
2578
2579                 if (match->fast_quit) {
2580                         /* the machine has stopped working. */
2581                         if (match->machine->flags & REGEX_MATCH_VERBOSE)
2582                                 printf("Best match has found\n");
2583                         break;
2584                 }
2585
2586                 input_string++;
2587                 length--;
2588         }
2589 }
2590 #endif