libregexp.c - quickjs-tart - quickjs-based runtime for wallet-core logic

libregexp.c (113209B)
      1 /*
      2  * Regular Expression Engine
      3  *
      4  * Copyright (c) 2017-2018 Fabrice Bellard
      5  *
      6  * Permission is hereby granted, free of charge, to any person obtaining a copy
      7  * of this software and associated documentation files (the "Software"), to deal
      8  * in the Software without restriction, including without limitation the rights
      9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
     10  * copies of the Software, and to permit persons to whom the Software is
     11  * furnished to do so, subject to the following conditions:
     12  *
     13  * The above copyright notice and this permission notice shall be included in
     14  * all copies or substantial portions of the Software.
     15  *
     16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
     19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
     22  * THE SOFTWARE.
     23  */
     24 #include <stdlib.h>
     25 #include <stdio.h>
     26 #include <stdarg.h>
     27 #include <inttypes.h>
     28 #include <string.h>
     29 #include <assert.h>
     30 
     31 #include "cutils.h"
     32 #include "libregexp.h"
     33 #include "libunicode.h"
     34 
     35 /*
     36   TODO:
     37   - remove REOP_char_i and REOP_range_i by precomputing the case folding.
     38   - add specific opcodes for simple unicode property tests so that the
     39     generated bytecode is smaller.
     40   - Add a lock step execution mode (=linear time execution guaranteed)
     41     when the regular expression is "simple" i.e. no backreference nor
     42     complicated lookahead. The opcodes are designed for this execution
     43     model.
     44 */
     45 
     46 #if defined(TEST) 
     47 #define DUMP_REOP
     48 #endif
     49 //#define DUMP_REOP
     50 //#define DUMP_EXEC
     51 
     52 typedef enum {
     53 #define DEF(id, size) REOP_ ## id,
     54 #include "libregexp-opcode.h"
     55 #undef DEF
     56     REOP_COUNT,
     57 } REOPCodeEnum;
     58 
     59 #define CAPTURE_COUNT_MAX 255
     60 #define REGISTER_COUNT_MAX 255
     61 /* must be large enough to have a negligible runtime cost and small
     62    enough to call the interrupt callback often. */
     63 #define INTERRUPT_COUNTER_INIT 10000
     64 
     65 /* unicode code points */
     66 #define CP_LS   0x2028
     67 #define CP_PS   0x2029
     68 
     69 #define TMP_BUF_SIZE 128
     70 
     71 typedef struct {
     72     DynBuf byte_code;
     73     const uint8_t *buf_ptr;
     74     const uint8_t *buf_end;
     75     const uint8_t *buf_start;
     76     int re_flags;
     77     BOOL is_unicode;
     78     BOOL unicode_sets; /* if set, is_unicode is also set */
     79     BOOL ignore_case;
     80     BOOL multi_line;
     81     BOOL dotall;
     82     uint8_t group_name_scope;
     83     int capture_count;
     84     int total_capture_count; /* -1 = not computed yet */
     85     int has_named_captures; /* -1 = don't know, 0 = no, 1 = yes */
     86     void *opaque;
     87     DynBuf group_names;
     88     union {
     89         char error_msg[TMP_BUF_SIZE];
     90         char tmp_buf[TMP_BUF_SIZE];
     91     } u;
     92 } REParseState;
     93 
     94 typedef struct {
     95 #ifdef DUMP_REOP
     96     const char *name;
     97 #endif
     98     uint8_t size;
     99 } REOpCode;
    100 
    101 static const REOpCode reopcode_info[REOP_COUNT] = {
    102 #ifdef DUMP_REOP
    103 #define DEF(id, size) { #id, size },
    104 #else
    105 #define DEF(id, size) { size },
    106 #endif
    107 #include "libregexp-opcode.h"
    108 #undef DEF
    109 };
    110 
    111 #define RE_HEADER_FLAGS          0
    112 #define RE_HEADER_CAPTURE_COUNT  2
    113 #define RE_HEADER_REGISTER_COUNT 3
    114 #define RE_HEADER_BYTECODE_LEN   4
    115 
    116 #define RE_HEADER_LEN 8
    117 
    118 static inline int is_digit(int c) {
    119     return c >= '0' && c <= '9';
    120 }
    121 
    122 /* insert 'len' bytes at position 'pos'. Return < 0 if error. */
    123 static int dbuf_insert(DynBuf *s, int pos, int len)
    124 {
    125     if (dbuf_claim(s, len))
    126         return -1;
    127     memmove(s->buf + pos + len, s->buf + pos, s->size - pos);
    128     s->size += len;
    129     return 0;
    130 }
    131 
    132 typedef struct REString {
    133     struct REString *next;
    134     uint32_t hash;
    135     uint32_t len;
    136     uint32_t buf[];
    137 } REString;
    138 
    139 typedef struct {
    140     /* the string list is the union of 'char_range' and of the strings
    141        in hash_table[]. The strings in hash_table[] have a length !=
    142        1. */
    143     CharRange cr;
    144     uint32_t n_strings;
    145     uint32_t hash_size;
    146     int hash_bits;
    147     REString **hash_table;
    148 } REStringList;
    149 
    150 static uint32_t re_string_hash(int len, const uint32_t *buf)
    151 {
    152     int i;
    153     uint32_t h;
    154     h = 1;
    155     for(i = 0; i < len; i++)
    156         h = h * 263 + buf[i];
    157     return h * 0x61C88647;
    158 }
    159 
    160 static void re_string_list_init(REParseState *s1, REStringList *s)
    161 {
    162     cr_init(&s->cr, s1->opaque, lre_realloc);
    163     s->n_strings = 0;
    164     s->hash_size = 0;
    165     s->hash_bits = 0;
    166     s->hash_table = NULL;
    167 }
    168 
    169 static void re_string_list_free(REStringList *s)
    170 {
    171     REString *p, *p_next;
    172     int i;
    173     for(i = 0; i < s->hash_size; i++) {
    174         for(p = s->hash_table[i]; p != NULL; p = p_next) {
    175             p_next = p->next;
    176             lre_realloc(s->cr.mem_opaque, p, 0);
    177         }
    178     }
    179     lre_realloc(s->cr.mem_opaque, s->hash_table, 0);
    180 
    181     cr_free(&s->cr);
    182 }
    183 
    184 static void lre_print_char(int c, BOOL is_range)
    185 {
    186     if (c == '\'' || c == '\\' ||
    187         (is_range && (c == '-' || c == ']'))) {
    188         printf("\\%c", c);
    189     } else if (c >= ' ' && c <= 126) {
    190         printf("%c", c);
    191     } else {
    192         printf("\\u{%04x}", c);
    193     }
    194 }
    195 
    196 static __maybe_unused void re_string_list_dump(const char *str, const REStringList *s)
    197 {
    198     REString *p;
    199     const CharRange *cr;
    200     int i, j, k;
    201 
    202     printf("%s:\n", str);
    203     printf("  ranges: [");
    204     cr = &s->cr;
    205     for(i = 0; i < cr->len; i += 2) {
    206         lre_print_char(cr->points[i], TRUE);
    207         if (cr->points[i] != cr->points[i + 1] - 1) {
    208             printf("-");
    209             lre_print_char(cr->points[i + 1] - 1, TRUE);
    210         }
    211     }
    212     printf("]\n");
    213     
    214     j = 0;
    215     for(i = 0; i < s->hash_size; i++) {
    216         for(p = s->hash_table[i]; p != NULL; p = p->next) {
    217             printf("  %d/%d: '", j, s->n_strings);
    218             for(k = 0; k < p->len; k++) {
    219                 lre_print_char(p->buf[k], FALSE);
    220             }
    221             printf("'\n");
    222             j++;
    223         }
    224     }
    225 }
    226 
    227 static int re_string_find2(REStringList *s, int len, const uint32_t *buf,
    228                            uint32_t h0, BOOL add_flag)
    229 {
    230     uint32_t h = 0; /* avoid warning */
    231     REString *p;
    232     if (s->n_strings != 0) {
    233         h = h0 >> (32 - s->hash_bits);
    234         for(p = s->hash_table[h]; p != NULL; p = p->next) {
    235             if (p->hash == h0 && p->len == len &&
    236                 !memcmp(p->buf, buf, len * sizeof(buf[0]))) {
    237                 return 1;
    238             }
    239         }
    240     }
    241     /* not found */
    242     if (!add_flag)
    243         return 0;
    244     /* increase the size of the hash table if needed */
    245     if (unlikely((s->n_strings + 1) > s->hash_size)) {
    246         REString **new_hash_table, *p_next;
    247         int new_hash_bits, i;
    248         uint32_t new_hash_size;
    249         new_hash_bits = max_int(s->hash_bits + 1, 4);
    250         new_hash_size = 1 << new_hash_bits;
    251         new_hash_table = lre_realloc(s->cr.mem_opaque, NULL,
    252                                      sizeof(new_hash_table[0]) * new_hash_size);
    253         if (!new_hash_table)
    254             return -1;
    255         memset(new_hash_table, 0, sizeof(new_hash_table[0]) * new_hash_size);
    256         for(i = 0; i < s->hash_size; i++) {
    257             for(p = s->hash_table[i]; p != NULL; p = p_next) {
    258                 p_next = p->next;
    259                 h = p->hash >> (32 - new_hash_bits);
    260                 p->next = new_hash_table[h];
    261                 new_hash_table[h] = p;
    262             }
    263         }
    264         lre_realloc(s->cr.mem_opaque, s->hash_table, 0);
    265         s->hash_bits = new_hash_bits;
    266         s->hash_size = new_hash_size;
    267         s->hash_table = new_hash_table;
    268         h = h0 >> (32 - s->hash_bits);
    269     }
    270 
    271     p = lre_realloc(s->cr.mem_opaque, NULL, sizeof(REString) + len * sizeof(buf[0]));
    272     if (!p)
    273         return -1;
    274     p->next = s->hash_table[h];
    275     s->hash_table[h] = p;
    276     s->n_strings++;
    277     p->hash = h0;
    278     p->len = len;
    279     memcpy(p->buf, buf, sizeof(buf[0]) * len);
    280     return 1;
    281 }
    282 
    283 static int re_string_find(REStringList *s, int len, const uint32_t *buf,
    284                           BOOL add_flag)
    285 {
    286     uint32_t h0;
    287     h0 = re_string_hash(len, buf);
    288     return re_string_find2(s, len, buf, h0, add_flag);
    289 }
    290 
    291 /* return -1 if memory error, 0 if OK */
    292 static int re_string_add(REStringList *s, int len, const uint32_t *buf)
    293 {
    294     if (len == 1) {
    295         return cr_union_interval(&s->cr, buf[0], buf[0]);
    296     }
    297     if (re_string_find(s, len, buf, TRUE) < 0)
    298         return -1;
    299     return 0;
    300 }
    301 
    302 /* a = a op b */
    303 static int re_string_list_op(REStringList *a, REStringList *b, int op)
    304 {
    305     int i, ret;
    306     REString *p, **pp;
    307 
    308     if (cr_op1(&a->cr, b->cr.points, b->cr.len, op))
    309         return -1;
    310 
    311     switch(op) {
    312     case CR_OP_UNION:
    313         if (b->n_strings != 0) {
    314             for(i = 0; i < b->hash_size; i++) {
    315                 for(p = b->hash_table[i]; p != NULL; p = p->next) {
    316                     if (re_string_find2(a, p->len, p->buf, p->hash, TRUE) < 0)
    317                         return -1;
    318                 }
    319             }
    320         }
    321         break;
    322     case CR_OP_INTER:
    323     case CR_OP_SUB:
    324         for(i = 0; i < a->hash_size; i++) {
    325             pp = &a->hash_table[i];
    326             for(;;) {
    327                 p = *pp;
    328                 if (p == NULL)
    329                     break;
    330                 ret = re_string_find2(b, p->len, p->buf, p->hash, FALSE);
    331                 if (op == CR_OP_SUB)
    332                     ret = !ret;
    333                 if (!ret) {
    334                     /* remove it */
    335                     *pp = p->next;
    336                     a->n_strings--;
    337                     lre_realloc(a->cr.mem_opaque, p, 0);
    338                 } else {
    339                     /* keep it */
    340                     pp = &p->next;
    341                 }
    342             }
    343         }
    344         break;
    345     default:
    346         abort();
    347     }
    348     return 0;
    349 }
    350 
    351 static int re_string_list_canonicalize(REParseState *s1,
    352                                        REStringList *s, BOOL is_unicode)
    353 {
    354     if (cr_regexp_canonicalize(&s->cr, is_unicode))
    355         return -1;
    356     if (s->n_strings != 0) {
    357         REStringList a_s, *a = &a_s;
    358         int i, j;
    359         REString *p;
    360         
    361         /* XXX: simplify */
    362         re_string_list_init(s1, a);
    363 
    364         a->n_strings = s->n_strings;
    365         a->hash_size = s->hash_size;
    366         a->hash_bits = s->hash_bits;
    367         a->hash_table = s->hash_table;
    368         
    369         s->n_strings = 0;
    370         s->hash_size = 0;
    371         s->hash_bits = 0;
    372         s->hash_table = NULL;
    373 
    374         for(i = 0; i < a->hash_size; i++) {
    375             for(p = a->hash_table[i]; p != NULL; p = p->next) {
    376                 for(j = 0; j < p->len; j++) {
    377                     p->buf[j] = lre_canonicalize(p->buf[j], is_unicode);
    378                 }
    379                 if (re_string_add(s, p->len, p->buf)) {
    380                     re_string_list_free(a);
    381                     return -1;
    382                 }
    383             }
    384         }
    385         re_string_list_free(a);
    386     }
    387     return 0;
    388 }
    389 
    390 static const uint16_t char_range_d[] = {
    391     1,
    392     0x0030, 0x0039 + 1,
    393 };
    394 
    395 /* code point ranges for Zs,Zl or Zp property */
    396 static const uint16_t char_range_s[] = {
    397     10,
    398     0x0009, 0x000D + 1,
    399     0x0020, 0x0020 + 1,
    400     0x00A0, 0x00A0 + 1,
    401     0x1680, 0x1680 + 1,
    402     0x2000, 0x200A + 1,
    403     /* 2028;LINE SEPARATOR;Zl;0;WS;;;;;N;;;;; */
    404     /* 2029;PARAGRAPH SEPARATOR;Zp;0;B;;;;;N;;;;; */
    405     0x2028, 0x2029 + 1,
    406     0x202F, 0x202F + 1,
    407     0x205F, 0x205F + 1,
    408     0x3000, 0x3000 + 1,
    409     /* FEFF;ZERO WIDTH NO-BREAK SPACE;Cf;0;BN;;;;;N;BYTE ORDER MARK;;;; */
    410     0xFEFF, 0xFEFF + 1,
    411 };
    412 
    413 static const uint16_t char_range_w[] = {
    414     4,
    415     0x0030, 0x0039 + 1,
    416     0x0041, 0x005A + 1,
    417     0x005F, 0x005F + 1,
    418     0x0061, 0x007A + 1,
    419 };
    420 
    421 #define CLASS_RANGE_BASE 0x40000000
    422 
    423 typedef enum {
    424     CHAR_RANGE_d,
    425     CHAR_RANGE_D,
    426     CHAR_RANGE_s,
    427     CHAR_RANGE_S,
    428     CHAR_RANGE_w,
    429     CHAR_RANGE_W,
    430 } CharRangeEnum;
    431 
    432 static const uint16_t * const char_range_table[] = {
    433     char_range_d,
    434     char_range_s,
    435     char_range_w,
    436 };
    437 
    438 static int cr_init_char_range(REParseState *s, REStringList *cr, uint32_t c)
    439 {
    440     BOOL invert;
    441     const uint16_t *c_pt;
    442     int len, i;
    443 
    444     invert = c & 1;
    445     c_pt = char_range_table[c >> 1];
    446     len = *c_pt++;
    447     re_string_list_init(s, cr);
    448     for(i = 0; i < len * 2; i++) {
    449         if (cr_add_point(&cr->cr, c_pt[i]))
    450             goto fail;
    451     }
    452     if (invert) {
    453         if (cr_invert(&cr->cr))
    454             goto fail;
    455     }
    456     return 0;
    457  fail:
    458     re_string_list_free(cr);
    459     return -1;
    460 }
    461 
    462 #ifdef DUMP_REOP
    463 static __maybe_unused void lre_dump_bytecode(const uint8_t *buf,
    464                                                      int buf_len)
    465 {
    466     int pos, len, opcode, bc_len, re_flags, i;
    467     uint32_t val, val2;
    468 
    469     assert(buf_len >= RE_HEADER_LEN);
    470 
    471     re_flags = lre_get_flags(buf);
    472     bc_len = get_u32(buf + RE_HEADER_BYTECODE_LEN);
    473     assert(bc_len + RE_HEADER_LEN <= buf_len);
    474     printf("flags: 0x%x capture_count=%d reg_count=%d\n",
    475            re_flags, buf[RE_HEADER_CAPTURE_COUNT], buf[RE_HEADER_REGISTER_COUNT]);
    476     if (re_flags & LRE_FLAG_NAMED_GROUPS) {
    477         const char *p;
    478         p = (char *)buf + RE_HEADER_LEN + bc_len;
    479         printf("named groups: ");
    480         for(i = 1; i < buf[RE_HEADER_CAPTURE_COUNT]; i++) {
    481             if (i != 1)
    482                 printf(",");
    483             printf("<%s>", p);
    484             p += strlen(p) + LRE_GROUP_NAME_TRAILER_LEN;
    485         }
    486         printf("\n");
    487         assert(p == (char *)(buf + buf_len));
    488     }
    489     printf("bytecode_len=%d\n", bc_len);
    490 
    491     buf += RE_HEADER_LEN;
    492     pos = 0;
    493     while (pos < bc_len) {
    494         printf("%5u: ", pos);
    495         opcode = buf[pos];
    496         len = reopcode_info[opcode].size;
    497         if (opcode >= REOP_COUNT) {
    498             printf(" invalid opcode=0x%02x\n", opcode);
    499             break;
    500         }
    501         if ((pos + len) > bc_len) {
    502             printf(" buffer overflow (opcode=0x%02x)\n", opcode);
    503             break;
    504         }
    505         printf("%s", reopcode_info[opcode].name);
    506         switch(opcode) {
    507         case REOP_char:
    508         case REOP_char_i:
    509             val = get_u16(buf + pos + 1);
    510             if (val >= ' ' && val <= 126)
    511                 printf(" '%c'", val);
    512             else
    513                 printf(" 0x%04x", val);
    514             break;
    515         case REOP_char32:
    516         case REOP_char32_i:
    517             val = get_u32(buf + pos + 1);
    518             if (val >= ' ' && val <= 126)
    519                 printf(" '%c'", val);
    520             else
    521                 printf(" 0x%08x", val);
    522             break;
    523         case REOP_goto:
    524         case REOP_split_goto_first:
    525         case REOP_split_next_first:
    526         case REOP_lookahead:
    527         case REOP_negative_lookahead:
    528             val = get_u32(buf + pos + 1);
    529             val += (pos + 5);
    530             printf(" %u", val);
    531             break;
    532         case REOP_loop:
    533             val2 = buf[pos + 1];
    534             val = get_u32(buf + pos + 2);
    535             val += (pos + 6);
    536             printf(" r%u, %u", val2, val);
    537             break;
    538         case REOP_loop_split_goto_first:
    539         case REOP_loop_split_next_first:
    540         case REOP_loop_check_adv_split_goto_first:
    541         case REOP_loop_check_adv_split_next_first:
    542             {
    543                 uint32_t limit;
    544                 val2 = buf[pos + 1];
    545                 limit = get_u32(buf + pos + 2);
    546                 val = get_u32(buf + pos + 6);
    547                 val += (pos + 10);
    548                 printf(" r%u, %u, %u", val2, limit, val);
    549             }
    550             break;
    551         case REOP_save_start:
    552         case REOP_save_end:
    553             printf(" %u", buf[pos + 1]);
    554             break;
    555         case REOP_back_reference:
    556         case REOP_back_reference_i:
    557         case REOP_backward_back_reference:
    558         case REOP_backward_back_reference_i:
    559             {
    560                 int n, i;
    561                 n = buf[pos + 1];
    562                 len += n;
    563                 for(i = 0; i < n; i++) {
    564                     if (i != 0)
    565                         printf(",");
    566                     printf(" %u", buf[pos + 2 + i]);
    567                 }
    568             }
    569             break;
    570         case REOP_save_reset:
    571             printf(" %u %u", buf[pos + 1], buf[pos + 2]);
    572             break;
    573         case REOP_set_i32:
    574             val = buf[pos + 1];
    575             val2 = get_u32(buf + pos + 2);
    576             printf(" r%u, %d", val, val2);
    577             break;
    578         case REOP_set_char_pos:
    579         case REOP_check_advance:
    580             val = buf[pos + 1];
    581             printf(" r%u", val);
    582             break;
    583         case REOP_range:
    584         case REOP_range_i:
    585             {
    586                 int n, i;
    587                 n = get_u16(buf + pos + 1);
    588                 len += n * 4;
    589                 for(i = 0; i < n * 2; i++) {
    590                     val = get_u16(buf + pos + 3 + i * 2);
    591                     printf(" 0x%04x", val);
    592                 }
    593             }
    594             break;
    595         case REOP_range32:
    596         case REOP_range32_i:
    597             {
    598                 int n, i;
    599                 n = get_u16(buf + pos + 1);
    600                 len += n * 8;
    601                 for(i = 0; i < n * 2; i++) {
    602                     val = get_u32(buf + pos + 3 + i * 4);
    603                     printf(" 0x%08x", val);
    604                 }
    605             }
    606             break;
    607         default:
    608             break;
    609         }
    610         printf("\n");
    611         pos += len;
    612     }
    613 }
    614 #endif
    615 
    616 static void re_emit_op(REParseState *s, int op)
    617 {
    618     dbuf_putc(&s->byte_code, op);
    619 }
    620 
    621 /* return the offset of the u32 value */
    622 static int re_emit_op_u32(REParseState *s, int op, uint32_t val)
    623 {
    624     int pos;
    625     dbuf_putc(&s->byte_code, op);
    626     pos = s->byte_code.size;
    627     dbuf_put_u32(&s->byte_code, val);
    628     return pos;
    629 }
    630 
    631 static int re_emit_goto(REParseState *s, int op, uint32_t val)
    632 {
    633     int pos;
    634     dbuf_putc(&s->byte_code, op);
    635     pos = s->byte_code.size;
    636     dbuf_put_u32(&s->byte_code, val - (pos + 4));
    637     return pos;
    638 }
    639 
    640 static int re_emit_goto_u8(REParseState *s, int op, uint32_t arg, uint32_t val)
    641 {
    642     int pos;
    643     dbuf_putc(&s->byte_code, op);
    644     dbuf_putc(&s->byte_code, arg);
    645     pos = s->byte_code.size;
    646     dbuf_put_u32(&s->byte_code, val - (pos + 4));
    647     return pos;
    648 }
    649 
    650 static int re_emit_goto_u8_u32(REParseState *s, int op, uint32_t arg0, uint32_t arg1, uint32_t val)
    651 {
    652     int pos;
    653     dbuf_putc(&s->byte_code, op);
    654     dbuf_putc(&s->byte_code, arg0);
    655     dbuf_put_u32(&s->byte_code, arg1);
    656     pos = s->byte_code.size;
    657     dbuf_put_u32(&s->byte_code, val - (pos + 4));
    658     return pos;
    659 }
    660 
    661 static void re_emit_op_u8(REParseState *s, int op, uint32_t val)
    662 {
    663     dbuf_putc(&s->byte_code, op);
    664     dbuf_putc(&s->byte_code, val);
    665 }
    666 
    667 static void re_emit_op_u16(REParseState *s, int op, uint32_t val)
    668 {
    669     dbuf_putc(&s->byte_code, op);
    670     dbuf_put_u16(&s->byte_code, val);
    671 }
    672 
    673 static int __attribute__((format(printf, 2, 3))) re_parse_error(REParseState *s, const char *fmt, ...)
    674 {
    675     va_list ap;
    676     va_start(ap, fmt);
    677     vsnprintf(s->u.error_msg, sizeof(s->u.error_msg), fmt, ap);
    678     va_end(ap);
    679     return -1;
    680 }
    681 
    682 static int re_parse_out_of_memory(REParseState *s)
    683 {
    684     return re_parse_error(s, "out of memory");
    685 }
    686 
    687 /* If allow_overflow is false, return -1 in case of
    688    overflow. Otherwise return INT32_MAX. */
    689 static int parse_digits(const uint8_t **pp, BOOL allow_overflow)
    690 {
    691     const uint8_t *p;
    692     uint64_t v;
    693     int c;
    694 
    695     p = *pp;
    696     v = 0;
    697     for(;;) {
    698         c = *p;
    699         if (c < '0' || c > '9')
    700             break;
    701         v = v * 10 + c - '0';
    702         if (v >= INT32_MAX) {
    703             if (allow_overflow)
    704                 v = INT32_MAX;
    705             else
    706                 return -1;
    707         }
    708         p++;
    709     }
    710     *pp = p;
    711     return v;
    712 }
    713 
    714 static int re_parse_expect(REParseState *s, const uint8_t **pp, int c)
    715 {
    716     const uint8_t *p;
    717     p = *pp;
    718     if (*p != c)
    719         return re_parse_error(s, "expecting '%c'", c);
    720     p++;
    721     *pp = p;
    722     return 0;
    723 }
    724 
    725 /* Parse an escape sequence, *pp points after the '\':
    726    allow_utf16 value:
    727    0 : no UTF-16 escapes allowed
    728    1 : UTF-16 escapes allowed
    729    2 : UTF-16 escapes allowed and escapes of surrogate pairs are
    730    converted to a unicode character (unicode regexp case).
    731 
    732    Return the unicode char and update *pp if recognized,
    733    return -1 if malformed escape,
    734    return -2 otherwise. */
    735 int lre_parse_escape(const uint8_t **pp, int allow_utf16)
    736 {
    737     const uint8_t *p;
    738     uint32_t c;
    739 
    740     p = *pp;
    741     c = *p++;
    742     switch(c) {
    743     case 'b':
    744         c = '\b';
    745         break;
    746     case 'f':
    747         c = '\f';
    748         break;
    749     case 'n':
    750         c = '\n';
    751         break;
    752     case 'r':
    753         c = '\r';
    754         break;
    755     case 't':
    756         c = '\t';
    757         break;
    758     case 'v':
    759         c = '\v';
    760         break;
    761     case 'x':
    762         {
    763             int h0, h1;
    764 
    765             h0 = from_hex(*p++);
    766             if (h0 < 0)
    767                 return -1;
    768             h1 = from_hex(*p++);
    769             if (h1 < 0)
    770                 return -1;
    771             c = (h0 << 4) | h1;
    772         }
    773         break;
    774     case 'u':
    775         {
    776             int h, i;
    777             uint32_t c1;
    778 
    779             if (*p == '{' && allow_utf16) {
    780                 p++;
    781                 c = 0;
    782                 for(;;) {
    783                     h = from_hex(*p++);
    784                     if (h < 0)
    785                         return -1;
    786                     c = (c << 4) | h;
    787                     if (c > 0x10FFFF)
    788                         return -1;
    789                     if (*p == '}')
    790                         break;
    791                 }
    792                 p++;
    793             } else {
    794                 c = 0;
    795                 for(i = 0; i < 4; i++) {
    796                     h = from_hex(*p++);
    797                     if (h < 0) {
    798                         return -1;
    799                     }
    800                     c = (c << 4) | h;
    801                 }
    802                 if (is_hi_surrogate(c) &&
    803                     allow_utf16 == 2 && p[0] == '\\' && p[1] == 'u') {
    804                     /* convert an escaped surrogate pair into a
    805                        unicode char */
    806                     c1 = 0;
    807                     for(i = 0; i < 4; i++) {
    808                         h = from_hex(p[2 + i]);
    809                         if (h < 0)
    810                             break;
    811                         c1 = (c1 << 4) | h;
    812                     }
    813                     if (i == 4 && is_lo_surrogate(c1)) {
    814                         p += 6;
    815                         c = from_surrogate(c, c1);
    816                     }
    817                 }
    818             }
    819         }
    820         break;
    821     case '0': case '1': case '2': case '3':
    822     case '4': case '5': case '6': case '7':
    823         c -= '0';
    824         if (allow_utf16 == 2) {
    825             /* only accept \0 not followed by digit */
    826             if (c != 0 || is_digit(*p))
    827                 return -1;
    828         } else {
    829             /* parse a legacy octal sequence */
    830             uint32_t v;
    831             v = *p - '0';
    832             if (v > 7)
    833                 break;
    834             c = (c << 3) | v;
    835             p++;
    836             if (c >= 32)
    837                 break;
    838             v = *p - '0';
    839             if (v > 7)
    840                 break;
    841             c = (c << 3) | v;
    842             p++;
    843         }
    844         break;
    845     default:
    846         return -2;
    847     }
    848     *pp = p;
    849     return c;
    850 }
    851 
    852 #ifdef CONFIG_ALL_UNICODE
    853 /* XXX: we use the same chars for name and value */
    854 static BOOL is_unicode_char(int c)
    855 {
    856     return ((c >= '0' && c <= '9') ||
    857             (c >= 'A' && c <= 'Z') ||
    858             (c >= 'a' && c <= 'z') ||
    859             (c == '_'));
    860 }
    861 
    862 /* XXX: memory error test */
    863 static void seq_prop_cb(void *opaque, const uint32_t *seq, int seq_len)
    864 {
    865     REStringList *sl = opaque;
    866     re_string_add(sl, seq_len, seq);
    867 }
    868 
    869 static int parse_unicode_property(REParseState *s, REStringList *cr,
    870                                   const uint8_t **pp, BOOL is_inv,
    871                                   BOOL allow_sequence_prop)
    872 {
    873     const uint8_t *p;
    874     char name[64], value[64];
    875     char *q;
    876     BOOL script_ext;
    877     int ret;
    878 
    879     p = *pp;
    880     if (*p != '{')
    881         return re_parse_error(s, "expecting '{' after \\p");
    882     p++;
    883     q = name;
    884     while (is_unicode_char(*p)) {
    885         if ((q - name) >= sizeof(name) - 1)
    886             goto unknown_property_name;
    887         *q++ = *p++;
    888     }
    889     *q = '\0';
    890     q = value;
    891     if (*p == '=') {
    892         p++;
    893         while (is_unicode_char(*p)) {
    894             if ((q - value) >= sizeof(value) - 1)
    895                 return re_parse_error(s, "unknown unicode property value");
    896             *q++ = *p++;
    897         }
    898     }
    899     *q = '\0';
    900     if (*p != '}')
    901         return re_parse_error(s, "expecting '}'");
    902     p++;
    903     //    printf("name=%s value=%s\n", name, value);
    904 
    905     if (!strcmp(name, "Script") || !strcmp(name, "sc")) {
    906         script_ext = FALSE;
    907         goto do_script;
    908     } else if (!strcmp(name, "Script_Extensions") || !strcmp(name, "scx")) {
    909         script_ext = TRUE;
    910     do_script:
    911         re_string_list_init(s, cr);
    912         ret = unicode_script(&cr->cr, value, script_ext);
    913         if (ret) {
    914             re_string_list_free(cr);
    915             if (ret == -2)
    916                 return re_parse_error(s, "unknown unicode script");
    917             else
    918                 goto out_of_memory;
    919         }
    920     } else if (!strcmp(name, "General_Category") || !strcmp(name, "gc")) {
    921         re_string_list_init(s, cr);
    922         ret = unicode_general_category(&cr->cr, value);
    923         if (ret) {
    924             re_string_list_free(cr);
    925             if (ret == -2)
    926                 return re_parse_error(s, "unknown unicode general category");
    927             else
    928                 goto out_of_memory;
    929         }
    930     } else if (value[0] == '\0') {
    931         re_string_list_init(s, cr);
    932         ret = unicode_general_category(&cr->cr, name);
    933         if (ret == -1) {
    934             re_string_list_free(cr);
    935             goto out_of_memory;
    936         }
    937         if (ret < 0) {
    938             ret = unicode_prop(&cr->cr, name);
    939             if (ret == -1) {
    940                 re_string_list_free(cr);
    941                 goto out_of_memory;
    942             }
    943         }
    944         if (ret < 0 && !is_inv && allow_sequence_prop) {
    945             CharRange cr_tmp;
    946             cr_init(&cr_tmp, s->opaque, lre_realloc);
    947             ret = unicode_sequence_prop(name, seq_prop_cb, cr, &cr_tmp);
    948             cr_free(&cr_tmp);
    949             if (ret == -1) {
    950                 re_string_list_free(cr);
    951                 goto out_of_memory;
    952             }
    953         }
    954         if (ret < 0)
    955             goto unknown_property_name;
    956     } else {
    957     unknown_property_name:
    958         return re_parse_error(s, "unknown unicode property name");
    959     }
    960 
    961     /* the ordering of case folding and inversion  differs with
    962        unicode_sets. 'unicode_sets' ordering is more consistent */
    963     /* XXX: the spec seems incorrect, we do it as the other engines
    964        seem to do it. */
    965     if (s->ignore_case && s->unicode_sets) {
    966         if (re_string_list_canonicalize(s, cr, s->is_unicode)) {
    967             re_string_list_free(cr);
    968             goto out_of_memory;
    969         }
    970     }
    971     if (is_inv) {
    972         if (cr_invert(&cr->cr)) {
    973             re_string_list_free(cr);
    974             goto out_of_memory;
    975         }
    976     }
    977     if (s->ignore_case && !s->unicode_sets) {
    978         if (re_string_list_canonicalize(s, cr, s->is_unicode)) {
    979             re_string_list_free(cr);
    980             goto out_of_memory;
    981         }
    982     }
    983     *pp = p;
    984     return 0;
    985  out_of_memory:
    986     return re_parse_out_of_memory(s);
    987 }
    988 #endif /* CONFIG_ALL_UNICODE */
    989 
    990 static int get_class_atom(REParseState *s, REStringList *cr,
    991                           const uint8_t **pp, BOOL inclass);
    992 
    993 static int parse_class_string_disjunction(REParseState *s, REStringList *cr,
    994                                           const uint8_t **pp)
    995 {
    996     const uint8_t *p;
    997     DynBuf str;
    998     int c;
    999     
   1000     p = *pp;
   1001     if (*p != '{')
   1002         return re_parse_error(s, "expecting '{' after \\q");
   1003 
   1004     dbuf_init2(&str, s->opaque, lre_realloc);
   1005     re_string_list_init(s, cr);
   1006     
   1007     p++;
   1008     for(;;) {
   1009         str.size = 0;
   1010         while (*p != '}' && *p != '|') {
   1011             c = get_class_atom(s, NULL, &p, FALSE);
   1012             if (c < 0)
   1013                 goto fail;
   1014             if (dbuf_put_u32(&str, c)) {
   1015                 re_parse_out_of_memory(s);
   1016                 goto fail;
   1017             }
   1018         }
   1019         if (re_string_add(cr, str.size / 4, (uint32_t *)str.buf)) {
   1020             re_parse_out_of_memory(s);
   1021             goto fail;
   1022         }
   1023         if (*p == '}')
   1024             break;
   1025         p++;
   1026     }
   1027     if (s->ignore_case) {
   1028         if (re_string_list_canonicalize(s, cr, TRUE))
   1029             goto fail;
   1030     }
   1031     p++; /* skip the '}' */
   1032     dbuf_free(&str);
   1033     *pp = p;
   1034     return 0;
   1035  fail:
   1036     dbuf_free(&str);
   1037     re_string_list_free(cr);
   1038     return -1;
   1039 }
   1040 
   1041 /* return -1 if error otherwise the character or a class range
   1042    (CLASS_RANGE_BASE) if cr != NULL. In case of class range, 'cr' is
   1043    initialized. Otherwise, it is ignored. */
   1044 static int get_class_atom(REParseState *s, REStringList *cr,
   1045                           const uint8_t **pp, BOOL inclass)
   1046 {
   1047     const uint8_t *p;
   1048     uint32_t c;
   1049     int ret;
   1050 
   1051     p = *pp;
   1052 
   1053     c = *p;
   1054     switch(c) {
   1055     case '\\':
   1056         p++;
   1057         if (p >= s->buf_end)
   1058             goto unexpected_end;
   1059         c = *p++;
   1060         switch(c) {
   1061         case 'd':
   1062             c = CHAR_RANGE_d;
   1063             goto class_range;
   1064         case 'D':
   1065             c = CHAR_RANGE_D;
   1066             goto class_range;
   1067         case 's':
   1068             c = CHAR_RANGE_s;
   1069             goto class_range;
   1070         case 'S':
   1071             c = CHAR_RANGE_S;
   1072             goto class_range;
   1073         case 'w':
   1074             c = CHAR_RANGE_w;
   1075             goto class_range;
   1076         case 'W':
   1077             c = CHAR_RANGE_W;
   1078         class_range:
   1079             if (!cr)
   1080                 goto default_escape;
   1081             if (cr_init_char_range(s, cr, c))
   1082                 return -1;
   1083             c += CLASS_RANGE_BASE;
   1084             break;
   1085         case 'c':
   1086             c = *p;
   1087             if ((c >= 'a' && c <= 'z') ||
   1088                 (c >= 'A' && c <= 'Z') ||
   1089                 (((c >= '0' && c <= '9') || c == '_') &&
   1090                  inclass && !s->is_unicode)) {   /* Annex B.1.4 */
   1091                 c &= 0x1f;
   1092                 p++;
   1093             } else if (s->is_unicode) {
   1094                 goto invalid_escape;
   1095             } else {
   1096                 /* otherwise return '\' and 'c' */
   1097                 p--;
   1098                 c = '\\';
   1099             }
   1100             break;
   1101         case '-':
   1102             if (!inclass && s->is_unicode)
   1103                 goto invalid_escape;
   1104             break;
   1105         case '^':
   1106         case '$':
   1107         case '\\':
   1108         case '.':
   1109         case '*':
   1110         case '+':
   1111         case '?':
   1112         case '(':
   1113         case ')':
   1114         case '[':
   1115         case ']':
   1116         case '{':
   1117         case '}':
   1118         case '|':
   1119         case '/':
   1120             /* always valid to escape these characters */
   1121             break;
   1122 #ifdef CONFIG_ALL_UNICODE
   1123         case 'p':
   1124         case 'P':
   1125             if (s->is_unicode && cr) {
   1126                 if (parse_unicode_property(s, cr, &p, (c == 'P'), s->unicode_sets))
   1127                     return -1;
   1128                 c = CLASS_RANGE_BASE;
   1129                 break;
   1130             }
   1131             goto default_escape;
   1132 #endif
   1133         case 'q':
   1134             if (s->unicode_sets && cr && inclass) {
   1135                 if (parse_class_string_disjunction(s, cr, &p))
   1136                     return -1;
   1137                 c = CLASS_RANGE_BASE;
   1138                 break;
   1139             }
   1140             goto default_escape;
   1141         default:
   1142         default_escape:
   1143             p--;
   1144             ret = lre_parse_escape(&p, s->is_unicode * 2);
   1145             if (ret >= 0) {
   1146                 c = ret;
   1147             } else {
   1148                 if (s->is_unicode) {
   1149                 invalid_escape:
   1150                     return re_parse_error(s, "invalid escape sequence in regular expression");
   1151                 } else {
   1152                     /* just ignore the '\' */
   1153                     goto normal_char;
   1154                 }
   1155             }
   1156             break;
   1157         }
   1158         break;
   1159     case '\0':
   1160         if (p >= s->buf_end) {
   1161         unexpected_end:
   1162             return re_parse_error(s, "unexpected end");
   1163         }
   1164         /* fall thru */
   1165         goto normal_char;
   1166 
   1167     case '&':
   1168     case '!':
   1169     case '#':
   1170     case '$':
   1171     case '%':
   1172     case '*':
   1173     case '+':
   1174     case ',':
   1175     case '.':
   1176     case ':':
   1177     case ';':
   1178     case '<':
   1179     case '=':
   1180     case '>':
   1181     case '?':
   1182     case '@':
   1183     case '^':
   1184     case '`':
   1185     case '~':
   1186         if (s->unicode_sets && p[1] == c) {
   1187             /* forbidden double characters */
   1188             return re_parse_error(s, "invalid class set operation in regular expression");
   1189         }
   1190         goto normal_char;
   1191 
   1192     case '(':
   1193     case ')':
   1194     case '[':
   1195     case ']':
   1196     case '{':
   1197     case '}':
   1198     case '/':
   1199     case '-':
   1200     case '|':
   1201         if (s->unicode_sets) {
   1202             /* invalid characters in unicode sets */
   1203             return re_parse_error(s, "invalid character in class in regular expression");
   1204         }
   1205         goto normal_char;
   1206 
   1207     default:
   1208     normal_char:
   1209         /* normal char */
   1210         if (c >= 128) {
   1211             c = unicode_from_utf8(p, UTF8_CHAR_LEN_MAX, &p);
   1212             if ((unsigned)c > 0xffff && !s->is_unicode) {
   1213                 /* XXX: should handle non BMP-1 code points */
   1214                 return re_parse_error(s, "malformed unicode char");
   1215             }
   1216         } else {
   1217             p++;
   1218         }
   1219         break;
   1220     }
   1221     *pp = p;
   1222     return c;
   1223 }
   1224 
   1225 static int re_emit_range(REParseState *s, const CharRange *cr)
   1226 {
   1227     int len, i;
   1228     uint32_t high;
   1229 
   1230     len = (unsigned)cr->len / 2;
   1231     if (len >= 65535)
   1232         return re_parse_error(s, "too many ranges");
   1233     if (len == 0) {
   1234         re_emit_op_u32(s, REOP_char32, -1);
   1235     } else {
   1236         high = cr->points[cr->len - 1];
   1237         if (high == UINT32_MAX)
   1238             high = cr->points[cr->len - 2];
   1239         if (high <= 0xffff) {
   1240             /* can use 16 bit ranges with the conversion that 0xffff =
   1241                infinity */
   1242             re_emit_op_u16(s, s->ignore_case ? REOP_range_i : REOP_range, len);
   1243             for(i = 0; i < cr->len; i += 2) {
   1244                 dbuf_put_u16(&s->byte_code, cr->points[i]);
   1245                 high = cr->points[i + 1] - 1;
   1246                 if (high == UINT32_MAX - 1)
   1247                     high = 0xffff;
   1248                 dbuf_put_u16(&s->byte_code, high);
   1249             }
   1250         } else {
   1251             re_emit_op_u16(s, s->ignore_case ? REOP_range32_i : REOP_range32, len);
   1252             for(i = 0; i < cr->len; i += 2) {
   1253                 dbuf_put_u32(&s->byte_code, cr->points[i]);
   1254                 dbuf_put_u32(&s->byte_code, cr->points[i + 1] - 1);
   1255             }
   1256         }
   1257     }
   1258     return 0;
   1259 }
   1260 
   1261 static int re_string_cmp_len(const void *a, const void *b, void *arg)
   1262 {
   1263     REString *p1 = *(REString **)a;
   1264     REString *p2 = *(REString **)b;
   1265     return (p1->len < p2->len) - (p1->len > p2->len);
   1266 }
   1267 
   1268 static void re_emit_char(REParseState *s, int c)
   1269 {
   1270     if (c <= 0xffff)
   1271         re_emit_op_u16(s, s->ignore_case ? REOP_char_i : REOP_char, c);
   1272     else
   1273         re_emit_op_u32(s, s->ignore_case ? REOP_char32_i : REOP_char32, c);
   1274 }
   1275 
   1276 static int re_emit_string_list(REParseState *s, const REStringList *sl)
   1277 {
   1278     REString **tab, *p;
   1279     int i, j, split_pos, last_match_pos, n;
   1280     BOOL has_empty_string, is_last;
   1281     
   1282     //    re_string_list_dump("sl", sl);
   1283     if (sl->n_strings == 0) {
   1284         /* simple case: only characters */
   1285         if (re_emit_range(s, &sl->cr))
   1286             return -1;
   1287     } else {
   1288         /* at least one string list is present : match the longest ones first */
   1289         /* XXX: add a new op_switch opcode to compile as a trie */
   1290         tab = lre_realloc(s->opaque, NULL, sizeof(tab[0]) * sl->n_strings);
   1291         if (!tab) {
   1292             re_parse_out_of_memory(s);
   1293             return -1;
   1294         }
   1295         has_empty_string = FALSE;
   1296         n = 0;
   1297         for(i = 0; i < sl->hash_size; i++) {
   1298             for(p = sl->hash_table[i]; p != NULL; p = p->next) {
   1299                 if (p->len == 0) {
   1300                     has_empty_string = TRUE;
   1301                 } else {
   1302                     tab[n++] = p;
   1303                 }
   1304             }
   1305         }
   1306         assert(n <= sl->n_strings);
   1307         
   1308         rqsort(tab, n, sizeof(tab[0]), re_string_cmp_len, NULL);
   1309 
   1310         last_match_pos = -1;
   1311         for(i = 0; i < n; i++) {
   1312             p = tab[i];
   1313             is_last = !has_empty_string && sl->cr.len == 0 && i == (n - 1);
   1314             if (!is_last)
   1315                 split_pos = re_emit_op_u32(s, REOP_split_next_first, 0);
   1316             else
   1317                 split_pos = 0;
   1318             for(j = 0; j < p->len; j++) {
   1319                 re_emit_char(s, p->buf[j]);
   1320             }
   1321             if (!is_last) {
   1322                 last_match_pos = re_emit_op_u32(s, REOP_goto, last_match_pos);
   1323                 put_u32(s->byte_code.buf + split_pos, s->byte_code.size - (split_pos + 4));
   1324             }
   1325         }
   1326 
   1327         if (sl->cr.len != 0) {
   1328             /* char range */
   1329             is_last = !has_empty_string;
   1330             if (!is_last)
   1331                 split_pos = re_emit_op_u32(s, REOP_split_next_first, 0);
   1332             else
   1333                 split_pos = 0; /* not used */
   1334             if (re_emit_range(s, &sl->cr)) {
   1335                 lre_realloc(s->opaque, tab, 0);
   1336                 return -1;
   1337             }
   1338             if (!is_last)
   1339                 put_u32(s->byte_code.buf + split_pos, s->byte_code.size - (split_pos + 4));
   1340         }
   1341 
   1342         /* patch the 'goto match' */
   1343         while (last_match_pos != -1) {
   1344             int next_pos = get_u32(s->byte_code.buf + last_match_pos);
   1345             put_u32(s->byte_code.buf + last_match_pos, s->byte_code.size - (last_match_pos + 4));
   1346             last_match_pos = next_pos;
   1347         }
   1348         
   1349         lre_realloc(s->opaque, tab, 0);
   1350     }
   1351     return 0;
   1352 }
   1353 
   1354 static int re_parse_nested_class(REParseState *s, REStringList *cr, const uint8_t **pp);
   1355 
   1356 static int re_parse_class_set_operand(REParseState *s, REStringList *cr, const uint8_t **pp)
   1357 {
   1358     int c1;
   1359     const uint8_t *p = *pp;
   1360     
   1361     if (*p == '[') {
   1362         if (re_parse_nested_class(s, cr, pp))
   1363             return -1;
   1364     } else {
   1365         c1 = get_class_atom(s, cr, pp, TRUE);
   1366         if (c1 < 0)
   1367             return -1;
   1368         if (c1 < CLASS_RANGE_BASE) {
   1369             /* create a range with a single character */
   1370             re_string_list_init(s, cr);
   1371             if (s->ignore_case)
   1372                 c1 = lre_canonicalize(c1, s->is_unicode);
   1373             if (cr_union_interval(&cr->cr, c1, c1)) {
   1374                 re_string_list_free(cr);
   1375                 return -1;
   1376             }
   1377         }
   1378     }
   1379     return 0;
   1380 }
   1381 
   1382 static int re_parse_nested_class(REParseState *s, REStringList *cr, const uint8_t **pp)
   1383 {
   1384     const uint8_t *p;
   1385     uint32_t c1, c2;
   1386     int ret;
   1387     REStringList cr1_s, *cr1 = &cr1_s;
   1388     BOOL invert, is_first;
   1389 
   1390     if (lre_check_stack_overflow(s->opaque, 0))
   1391         return re_parse_error(s, "stack overflow");
   1392 
   1393     re_string_list_init(s, cr);
   1394     p = *pp;
   1395     p++;    /* skip '[' */
   1396 
   1397     invert = FALSE;
   1398     if (*p == '^') {
   1399         p++;
   1400         invert = TRUE;
   1401     }
   1402     
   1403     /* handle unions */
   1404     is_first = TRUE;
   1405     for(;;) {
   1406         if (*p == ']')
   1407             break;
   1408         if (*p == '[' && s->unicode_sets) {
   1409             if (re_parse_nested_class(s, cr1, &p))
   1410                 goto fail;
   1411             goto class_union;
   1412         } else {
   1413             c1 = get_class_atom(s, cr1, &p, TRUE);
   1414             if ((int)c1 < 0)
   1415                 goto fail;
   1416             if (*p == '-' && p[1] != ']') {
   1417                 const uint8_t *p0 = p + 1;
   1418                 if (p[1] == '-' && s->unicode_sets && is_first)
   1419                     goto class_atom; /* first character class followed by '--' */
   1420                 if (c1 >= CLASS_RANGE_BASE) {
   1421                     if (s->is_unicode) {
   1422                         re_string_list_free(cr1);
   1423                         goto invalid_class_range;
   1424                     }
   1425                     /* Annex B: match '-' character */
   1426                     goto class_atom;
   1427                 }
   1428                 c2 = get_class_atom(s, cr1, &p0, TRUE);
   1429                 if ((int)c2 < 0)
   1430                     goto fail;
   1431                 if (c2 >= CLASS_RANGE_BASE) {
   1432                     re_string_list_free(cr1);
   1433                     if (s->is_unicode) {
   1434                         goto invalid_class_range;
   1435                     }
   1436                     /* Annex B: match '-' character */
   1437                     goto class_atom;
   1438                 }
   1439                 p = p0;
   1440                 if (c2 < c1) {
   1441                 invalid_class_range:
   1442                     re_parse_error(s, "invalid class range");
   1443                     goto fail;
   1444                 }
   1445                 if (s->ignore_case) {
   1446                     CharRange cr2_s, *cr2 = &cr2_s;
   1447                     cr_init(cr2, s->opaque, lre_realloc);
   1448                     if (cr_add_interval(cr2, c1, c2 + 1) ||
   1449                         cr_regexp_canonicalize(cr2, s->is_unicode) ||
   1450                         cr_op1(&cr->cr, cr2->points, cr2->len, CR_OP_UNION)) {
   1451                         cr_free(cr2);
   1452                         goto memory_error;
   1453                     }
   1454                     cr_free(cr2);
   1455                 } else {
   1456                     if (cr_union_interval(&cr->cr, c1, c2))
   1457                         goto memory_error;
   1458                 }
   1459                 is_first = FALSE; /* union operation */
   1460             } else {
   1461             class_atom:
   1462                 if (c1 >= CLASS_RANGE_BASE) {
   1463                 class_union:
   1464                     ret = re_string_list_op(cr, cr1, CR_OP_UNION);
   1465                     re_string_list_free(cr1);
   1466                     if (ret)
   1467                         goto memory_error;
   1468                 } else {
   1469                     if (s->ignore_case)
   1470                         c1 = lre_canonicalize(c1, s->is_unicode);
   1471                     if (cr_union_interval(&cr->cr, c1, c1))
   1472                         goto memory_error;
   1473                 }
   1474             }
   1475         }
   1476         if (s->unicode_sets && is_first) {
   1477             if (*p == '&' && p[1] == '&' && p[2] != '&') {
   1478                 /* handle '&&' */
   1479                 for(;;) {
   1480                     if (*p == ']') {
   1481                         break;
   1482                     } else if (*p == '&' && p[1] == '&' && p[2] != '&') {
   1483                         p += 2;
   1484                     } else {
   1485                         goto invalid_operation;
   1486                     }
   1487                     if (re_parse_class_set_operand(s, cr1, &p))
   1488                         goto fail;
   1489                     ret = re_string_list_op(cr, cr1, CR_OP_INTER);
   1490                     re_string_list_free(cr1);
   1491                     if (ret)
   1492                         goto memory_error;
   1493                 }
   1494             } else if (*p == '-' && p[1] == '-') {
   1495                 /* handle '--' */
   1496                 for(;;) {
   1497                     if (*p == ']') {
   1498                         break;
   1499                     } else if (*p == '-' && p[1] == '-') {
   1500                         p += 2;
   1501                     } else {
   1502                     invalid_operation:
   1503                         re_parse_error(s, "invalid operation in regular expression");
   1504                         goto fail;
   1505                     }
   1506                     if (re_parse_class_set_operand(s, cr1, &p))
   1507                         goto fail;
   1508                     ret = re_string_list_op(cr, cr1, CR_OP_SUB);
   1509                     re_string_list_free(cr1);
   1510                     if (ret)
   1511                         goto memory_error;
   1512                 }
   1513             }
   1514         }
   1515         is_first = FALSE;
   1516     }
   1517 
   1518     p++;    /* skip ']' */
   1519     *pp = p;
   1520     if (invert) {
   1521         /* XXX: add may_contain_string syntax check to be fully
   1522            compliant. The test here accepts more input than the
   1523            spec. */
   1524         if (cr->n_strings != 0) {
   1525             re_parse_error(s, "negated character class with strings in regular expression debugger eval code");
   1526             goto fail;
   1527         }
   1528         if (cr_invert(&cr->cr))
   1529             goto memory_error;
   1530     }
   1531     return 0;
   1532  memory_error:
   1533     re_parse_out_of_memory(s);
   1534  fail:
   1535     re_string_list_free(cr);
   1536     return -1;
   1537 }
   1538 
   1539 static int re_parse_char_class(REParseState *s, const uint8_t **pp)
   1540 {
   1541     REStringList cr_s, *cr = &cr_s;
   1542 
   1543     if (re_parse_nested_class(s, cr, pp))
   1544         return -1;
   1545     if (re_emit_string_list(s, cr))
   1546         goto fail;
   1547     re_string_list_free(cr);
   1548     return 0;
   1549  fail:
   1550     re_string_list_free(cr);
   1551     return -1;
   1552 }
   1553 
   1554 /* need_check_adv: false if the opcodes always advance the char pointer
   1555    need_capture_init: true if all the captures in the atom are not set
   1556 */
   1557 static BOOL re_need_check_adv_and_capture_init(BOOL *pneed_capture_init,
   1558                                                const uint8_t *bc_buf, int bc_buf_len)
   1559 {
   1560     int pos, opcode, len;
   1561     uint32_t val;
   1562     BOOL need_check_adv, need_capture_init;
   1563 
   1564     need_check_adv = TRUE;
   1565     need_capture_init = FALSE;
   1566     pos = 0;
   1567     while (pos < bc_buf_len) {
   1568         opcode = bc_buf[pos];
   1569         len = reopcode_info[opcode].size;
   1570         switch(opcode) {
   1571         case REOP_range:
   1572         case REOP_range_i:
   1573             val = get_u16(bc_buf + pos + 1);
   1574             len += val * 4;
   1575             need_check_adv = FALSE;
   1576             break;
   1577         case REOP_range32:
   1578         case REOP_range32_i:
   1579             val = get_u16(bc_buf + pos + 1);
   1580             len += val * 8;
   1581             need_check_adv = FALSE;
   1582             break;
   1583         case REOP_char:
   1584         case REOP_char_i:
   1585         case REOP_char32:
   1586         case REOP_char32_i:
   1587         case REOP_dot:
   1588         case REOP_any:
   1589         case REOP_space:
   1590         case REOP_not_space:
   1591             need_check_adv = FALSE;
   1592             break;
   1593         case REOP_line_start:
   1594         case REOP_line_start_m:
   1595         case REOP_line_end:
   1596         case REOP_line_end_m:
   1597         case REOP_set_i32:
   1598         case REOP_set_char_pos:
   1599         case REOP_word_boundary:
   1600         case REOP_word_boundary_i:
   1601         case REOP_not_word_boundary:
   1602         case REOP_not_word_boundary_i:
   1603         case REOP_prev:
   1604             /* no effect */
   1605             break;
   1606         case REOP_save_start:
   1607         case REOP_save_end:
   1608         case REOP_save_reset:
   1609             break;
   1610         case REOP_back_reference:
   1611         case REOP_back_reference_i:
   1612         case REOP_backward_back_reference:
   1613         case REOP_backward_back_reference_i:
   1614             val = bc_buf[pos + 1];
   1615             len += val;
   1616             need_capture_init = TRUE;
   1617             break;
   1618         default:
   1619             /* safe behavior: we cannot predict the outcome */
   1620             need_capture_init = TRUE;
   1621             goto done;
   1622         }
   1623         pos += len;
   1624     }
   1625  done:
   1626     *pneed_capture_init = need_capture_init;
   1627     return need_check_adv;
   1628 }
   1629 
   1630 /* '*pp' is the first char after '<' */
   1631 static int re_parse_group_name(char *buf, int buf_size, const uint8_t **pp)
   1632 {
   1633     const uint8_t *p, *p1;
   1634     uint32_t c, d;
   1635     char *q;
   1636 
   1637     p = *pp;
   1638     q = buf;
   1639     for(;;) {
   1640         c = *p;
   1641         if (c == '\\') {
   1642             p++;
   1643             if (*p != 'u')
   1644                 return -1;
   1645             c = lre_parse_escape(&p, 2); // accept surrogate pairs
   1646         } else if (c == '>') {
   1647             break;
   1648         } else if (c >= 128) {
   1649             c = unicode_from_utf8(p, UTF8_CHAR_LEN_MAX, &p);
   1650             if (is_hi_surrogate(c)) {
   1651                 d = unicode_from_utf8(p, UTF8_CHAR_LEN_MAX, &p1);
   1652                 if (is_lo_surrogate(d)) {
   1653                     c = from_surrogate(c, d);
   1654                     p = p1;
   1655                 }
   1656             }
   1657         } else {
   1658             p++;
   1659         }
   1660         if (c > 0x10FFFF)
   1661             return -1;
   1662         if (q == buf) {
   1663             if (!lre_js_is_ident_first(c))
   1664                 return -1;
   1665         } else {
   1666             if (!lre_js_is_ident_next(c))
   1667                 return -1;
   1668         }
   1669         if ((q - buf + UTF8_CHAR_LEN_MAX + 1) > buf_size)
   1670             return -1;
   1671         if (c < 128) {
   1672             *q++ = c;
   1673         } else {
   1674             q += unicode_to_utf8((uint8_t*)q, c);
   1675         }
   1676     }
   1677     if (q == buf)
   1678         return -1;
   1679     *q = '\0';
   1680     p++;
   1681     *pp = p;
   1682     return 0;
   1683 }
   1684 
   1685 /* if capture_name = NULL: return the number of captures + 1.
   1686    Otherwise, return the number of matching capture groups  */
   1687 static int re_parse_captures(REParseState *s, int *phas_named_captures,
   1688                              const char *capture_name, BOOL emit_group_index)
   1689 {
   1690     const uint8_t *p;
   1691     int capture_index, n;
   1692     char name[TMP_BUF_SIZE];
   1693 
   1694     capture_index = 1;
   1695     n = 0;
   1696     *phas_named_captures = 0;
   1697     for (p = s->buf_start; p < s->buf_end; p++) {
   1698         switch (*p) {
   1699         case '(':
   1700             if (p[1] == '?') {
   1701                 if (p[2] == '<' && p[3] != '=' && p[3] != '!') {
   1702                     *phas_named_captures = 1;
   1703                     /* potential named capture */
   1704                     if (capture_name) {
   1705                         p += 3;
   1706                         if (re_parse_group_name(name, sizeof(name), &p) == 0) {
   1707                             if (!strcmp(name, capture_name)) {
   1708                                 if (emit_group_index)
   1709                                     dbuf_putc(&s->byte_code, capture_index);
   1710                                 n++;
   1711                             }
   1712                         }
   1713                     }
   1714                     capture_index++;
   1715                     if (capture_index >= CAPTURE_COUNT_MAX)
   1716                         goto done;
   1717                 }
   1718             } else {
   1719                 capture_index++;
   1720                 if (capture_index >= CAPTURE_COUNT_MAX)
   1721                     goto done;
   1722             }
   1723             break;
   1724         case '\\':
   1725             p++;
   1726             break;
   1727         case '[':
   1728             for (p += 1 + (*p == ']'); p < s->buf_end && *p != ']'; p++) {
   1729                 if (*p == '\\')
   1730                     p++;
   1731             }
   1732             break;
   1733         }
   1734     }
   1735  done:
   1736     if (capture_name) {
   1737         return n;
   1738     } else {
   1739         return capture_index;
   1740     }
   1741 }
   1742 
   1743 static int re_count_captures(REParseState *s)
   1744 {
   1745     if (s->total_capture_count < 0) {
   1746         s->total_capture_count = re_parse_captures(s, &s->has_named_captures,
   1747                                                    NULL, FALSE);
   1748     }
   1749     return s->total_capture_count;
   1750 }
   1751 
   1752 static BOOL re_has_named_captures(REParseState *s)
   1753 {
   1754     if (s->has_named_captures < 0)
   1755         re_count_captures(s);
   1756     return s->has_named_captures;
   1757 }
   1758 
   1759 static int find_group_name(REParseState *s, const char *name, BOOL emit_group_index)
   1760 {
   1761     const char *p, *buf_end;
   1762     size_t len, name_len;
   1763     int capture_index, n;
   1764 
   1765     p = (char *)s->group_names.buf;
   1766     if (!p)
   1767         return 0;
   1768     buf_end = (char *)s->group_names.buf + s->group_names.size;
   1769     name_len = strlen(name);
   1770     capture_index = 1;
   1771     n = 0;
   1772     while (p < buf_end) {
   1773         len = strlen(p);
   1774         if (len == name_len && memcmp(name, p, name_len) == 0) {
   1775             if (emit_group_index)
   1776                 dbuf_putc(&s->byte_code, capture_index);
   1777             n++;
   1778         }
   1779         p += len + LRE_GROUP_NAME_TRAILER_LEN;
   1780         capture_index++;
   1781     }
   1782     return n;
   1783 }
   1784 
   1785 static BOOL is_duplicate_group_name(REParseState *s, const char *name, int scope)
   1786 {
   1787     const char *p, *buf_end;
   1788     size_t len, name_len;
   1789     int scope1;
   1790     
   1791     p = (char *)s->group_names.buf;
   1792     if (!p)
   1793         return 0;
   1794     buf_end = (char *)s->group_names.buf + s->group_names.size;
   1795     name_len = strlen(name);
   1796     while (p < buf_end) {
   1797         len = strlen(p);
   1798         if (len == name_len && memcmp(name, p, name_len) == 0) {
   1799             scope1 = (uint8_t)p[len + 1];
   1800             if (scope == scope1)
   1801                 return TRUE;
   1802         }
   1803         p += len + LRE_GROUP_NAME_TRAILER_LEN;
   1804     }
   1805     return FALSE;
   1806 }
   1807 
   1808 static int re_parse_disjunction(REParseState *s, BOOL is_backward_dir);
   1809 
   1810 static int re_parse_modifiers(REParseState *s, const uint8_t **pp)
   1811 {
   1812     const uint8_t *p = *pp;
   1813     int mask = 0;
   1814     int val;
   1815 
   1816     for(;;) {
   1817         if (*p == 'i') {
   1818             val = LRE_FLAG_IGNORECASE;
   1819         } else if (*p == 'm') {
   1820             val = LRE_FLAG_MULTILINE;
   1821         } else if (*p == 's') {
   1822             val = LRE_FLAG_DOTALL;
   1823         } else {
   1824             break;
   1825         }
   1826         if (mask & val)
   1827             return re_parse_error(s, "duplicate modifier: '%c'", *p);
   1828         mask |= val;
   1829         p++;
   1830     }
   1831     *pp = p;
   1832     return mask;
   1833 }
   1834 
   1835 static BOOL update_modifier(BOOL val, int add_mask, int remove_mask,
   1836                             int mask)
   1837 {
   1838     if (add_mask & mask)
   1839         val = TRUE;
   1840     if (remove_mask & mask)
   1841         val = FALSE;
   1842     return val;
   1843 }
   1844 
   1845 static int re_parse_term(REParseState *s, BOOL is_backward_dir)
   1846 {
   1847     const uint8_t *p;
   1848     int c, last_atom_start, quant_min, quant_max, last_capture_count;
   1849     BOOL greedy, is_neg, is_backward_lookahead;
   1850     REStringList cr_s, *cr = &cr_s;
   1851 
   1852     last_atom_start = -1;
   1853     last_capture_count = 0;
   1854     p = s->buf_ptr;
   1855     c = *p;
   1856     switch(c) {
   1857     case '^':
   1858         p++;
   1859         re_emit_op(s, s->multi_line ? REOP_line_start_m : REOP_line_start);
   1860         break;
   1861     case '$':
   1862         p++;
   1863         re_emit_op(s, s->multi_line ? REOP_line_end_m : REOP_line_end);
   1864         break;
   1865     case '.':
   1866         p++;
   1867         last_atom_start = s->byte_code.size;
   1868         last_capture_count = s->capture_count;
   1869         if (is_backward_dir)
   1870             re_emit_op(s, REOP_prev);
   1871         re_emit_op(s, s->dotall ? REOP_any : REOP_dot);
   1872         if (is_backward_dir)
   1873             re_emit_op(s, REOP_prev);
   1874         break;
   1875     case '{':
   1876         if (s->is_unicode) {
   1877             return re_parse_error(s, "syntax error");
   1878         } else if (!is_digit(p[1])) {
   1879             /* Annex B: we accept '{' not followed by digits as a
   1880                normal atom */
   1881             goto parse_class_atom;
   1882         } else {
   1883             const uint8_t *p1 = p + 1;
   1884             /* Annex B: error if it is like a repetition count */
   1885             parse_digits(&p1, TRUE);
   1886             if (*p1 == ',') {
   1887                 p1++;
   1888                 if (is_digit(*p1)) {
   1889                     parse_digits(&p1, TRUE);
   1890                 }
   1891             }
   1892             if (*p1 != '}') {
   1893                 goto parse_class_atom;
   1894             }
   1895         }
   1896         /* fall thru */
   1897     case '*':
   1898     case '+':
   1899     case '?':
   1900         return re_parse_error(s, "nothing to repeat");
   1901     case '(':
   1902         if (p[1] == '?') {
   1903             if (p[2] == ':') {
   1904                 p += 3;
   1905                 last_atom_start = s->byte_code.size;
   1906                 last_capture_count = s->capture_count;
   1907                 s->buf_ptr = p;
   1908                 if (re_parse_disjunction(s, is_backward_dir))
   1909                     return -1;
   1910                 p = s->buf_ptr;
   1911                 if (re_parse_expect(s, &p, ')'))
   1912                     return -1;
   1913             } else if (p[2] == 'i' || p[2] == 'm' || p[2] == 's' || p[2] == '-') {
   1914                 BOOL saved_ignore_case, saved_multi_line, saved_dotall;
   1915                 int add_mask, remove_mask;
   1916                 p += 2;
   1917                 remove_mask = 0;
   1918                 add_mask = re_parse_modifiers(s, &p);
   1919                 if (add_mask < 0)
   1920                     return -1;
   1921                 if (*p == '-') {
   1922                     p++;
   1923                     remove_mask = re_parse_modifiers(s, &p);
   1924                     if (remove_mask < 0)
   1925                         return -1;
   1926                 }
   1927                 if ((add_mask == 0 && remove_mask == 0) ||
   1928                     (add_mask & remove_mask) != 0) {
   1929                     return re_parse_error(s, "invalid modifiers");
   1930                 }
   1931                 if (re_parse_expect(s, &p, ':'))
   1932                     return -1;
   1933                 saved_ignore_case = s->ignore_case;
   1934                 saved_multi_line = s->multi_line;
   1935                 saved_dotall = s->dotall;
   1936                 s->ignore_case = update_modifier(s->ignore_case, add_mask, remove_mask, LRE_FLAG_IGNORECASE);
   1937                 s->multi_line = update_modifier(s->multi_line, add_mask, remove_mask, LRE_FLAG_MULTILINE);
   1938                 s->dotall = update_modifier(s->dotall, add_mask, remove_mask, LRE_FLAG_DOTALL);
   1939 
   1940                 last_atom_start = s->byte_code.size;
   1941                 last_capture_count = s->capture_count;
   1942                 s->buf_ptr = p;
   1943                 if (re_parse_disjunction(s, is_backward_dir))
   1944                     return -1;
   1945                 p = s->buf_ptr;
   1946                 if (re_parse_expect(s, &p, ')'))
   1947                     return -1;
   1948                 s->ignore_case = saved_ignore_case;
   1949                 s->multi_line = saved_multi_line;
   1950                 s->dotall = saved_dotall;
   1951             } else if ((p[2] == '=' || p[2] == '!')) {
   1952                 is_neg = (p[2] == '!');
   1953                 is_backward_lookahead = FALSE;
   1954                 p += 3;
   1955                 goto lookahead;
   1956             } else if (p[2] == '<' &&
   1957                        (p[3] == '=' || p[3] == '!')) {
   1958                 int pos;
   1959                 is_neg = (p[3] == '!');
   1960                 is_backward_lookahead = TRUE;
   1961                 p += 4;
   1962                 /* lookahead */
   1963             lookahead:
   1964                 /* Annex B allows lookahead to be used as an atom for
   1965                    the quantifiers */
   1966                 if (!s->is_unicode && !is_backward_lookahead)  {
   1967                     last_atom_start = s->byte_code.size;
   1968                     last_capture_count = s->capture_count;
   1969                 }
   1970                 pos = re_emit_op_u32(s, REOP_lookahead + is_neg, 0);
   1971                 s->buf_ptr = p;
   1972                 if (re_parse_disjunction(s, is_backward_lookahead))
   1973                     return -1;
   1974                 p = s->buf_ptr;
   1975                 if (re_parse_expect(s, &p, ')'))
   1976                     return -1;
   1977                 re_emit_op(s, REOP_lookahead_match + is_neg);
   1978                 /* jump after the 'match' after the lookahead is successful */
   1979                 if (dbuf_error(&s->byte_code))
   1980                     return -1;
   1981                 put_u32(s->byte_code.buf + pos, s->byte_code.size - (pos + 4));
   1982             } else if (p[2] == '<') {
   1983                 p += 3;
   1984                 if (re_parse_group_name(s->u.tmp_buf, sizeof(s->u.tmp_buf),
   1985                                         &p)) {
   1986                     return re_parse_error(s, "invalid group name");
   1987                 }
   1988                 /* poor's man method to test duplicate group
   1989                    names. */
   1990                 /* XXX: this method does not catch all the errors*/
   1991                 if (is_duplicate_group_name(s, s->u.tmp_buf, s->group_name_scope)) {
   1992                     return re_parse_error(s, "duplicate group name");
   1993                 }
   1994                 /* group name with a trailing zero */
   1995                 dbuf_put(&s->group_names, (uint8_t *)s->u.tmp_buf,
   1996                          strlen(s->u.tmp_buf) + 1);
   1997                 dbuf_putc(&s->group_names, s->group_name_scope);
   1998                 s->has_named_captures = 1;
   1999                 goto parse_capture;
   2000             } else {
   2001                 return re_parse_error(s, "invalid group");
   2002             }
   2003         } else {
   2004             int capture_index;
   2005             p++;
   2006             /* capture without group name */
   2007             dbuf_putc(&s->group_names, 0);
   2008             dbuf_putc(&s->group_names, 0);
   2009         parse_capture:
   2010             if (s->capture_count >= CAPTURE_COUNT_MAX)
   2011                 return re_parse_error(s, "too many captures");
   2012             last_atom_start = s->byte_code.size;
   2013             last_capture_count = s->capture_count;
   2014             capture_index = s->capture_count++;
   2015             re_emit_op_u8(s, REOP_save_start + is_backward_dir,
   2016                           capture_index);
   2017 
   2018             s->buf_ptr = p;
   2019             if (re_parse_disjunction(s, is_backward_dir))
   2020                 return -1;
   2021             p = s->buf_ptr;
   2022 
   2023             re_emit_op_u8(s, REOP_save_start + 1 - is_backward_dir,
   2024                           capture_index);
   2025 
   2026             if (re_parse_expect(s, &p, ')'))
   2027                 return -1;
   2028         }
   2029         break;
   2030     case '\\':
   2031         switch(p[1]) {
   2032         case 'b':
   2033         case 'B':
   2034             if (p[1] != 'b') {
   2035                 re_emit_op(s, s->ignore_case && s->is_unicode ? REOP_not_word_boundary_i : REOP_not_word_boundary);
   2036             } else {
   2037                 re_emit_op(s, s->ignore_case && s->is_unicode ? REOP_word_boundary_i : REOP_word_boundary);
   2038             }
   2039             p += 2;
   2040             break;
   2041         case 'k':
   2042             {
   2043                 const uint8_t *p1;
   2044                 int dummy_res, n;
   2045                 BOOL is_forward;
   2046                 
   2047                 p1 = p;
   2048                 if (p1[2] != '<') {
   2049                     /* annex B: we tolerate invalid group names in non
   2050                        unicode mode if there is no named capture
   2051                        definition */
   2052                     if (s->is_unicode || re_has_named_captures(s))
   2053                         return re_parse_error(s, "expecting group name");
   2054                     else
   2055                         goto parse_class_atom;
   2056                 }
   2057                 p1 += 3;
   2058                 if (re_parse_group_name(s->u.tmp_buf, sizeof(s->u.tmp_buf),
   2059                                         &p1)) {
   2060                     if (s->is_unicode || re_has_named_captures(s))
   2061                         return re_parse_error(s, "invalid group name");
   2062                     else
   2063                         goto parse_class_atom;
   2064                 }
   2065                 is_forward = FALSE;
   2066                 n = find_group_name(s, s->u.tmp_buf, FALSE);
   2067                 if (n == 0) {
   2068                     /* no capture name parsed before, try to look
   2069                        after (inefficient, but hopefully not common */
   2070                     n = re_parse_captures(s, &dummy_res, s->u.tmp_buf, FALSE);
   2071                     if (n == 0) {
   2072                         if (s->is_unicode || re_has_named_captures(s))
   2073                             return re_parse_error(s, "group name not defined");
   2074                         else
   2075                             goto parse_class_atom;
   2076                     }
   2077                     is_forward = TRUE;
   2078                 }
   2079                 last_atom_start = s->byte_code.size;
   2080                 last_capture_count = s->capture_count;
   2081                 
   2082                 /* emit back references to all the captures indexes matching the group name */
   2083                 re_emit_op_u8(s, REOP_back_reference + 2 * is_backward_dir + s->ignore_case, n);
   2084                 if (is_forward) {
   2085                     re_parse_captures(s, &dummy_res, s->u.tmp_buf, TRUE);
   2086                 } else {
   2087                     find_group_name(s, s->u.tmp_buf, TRUE);
   2088                 }
   2089                 p = p1;
   2090             }
   2091             break;
   2092         case '0':
   2093             p += 2;
   2094             c = 0;
   2095             if (s->is_unicode) {
   2096                 if (is_digit(*p)) {
   2097                     return re_parse_error(s, "invalid decimal escape in regular expression");
   2098                 }
   2099             } else {
   2100                 /* Annex B.1.4: accept legacy octal */
   2101                 if (*p >= '0' && *p <= '7') {
   2102                     c = *p++ - '0';
   2103                     if (*p >= '0' && *p <= '7') {
   2104                         c = (c << 3) + *p++ - '0';
   2105                     }
   2106                 }
   2107             }
   2108             goto normal_char;
   2109         case '1': case '2': case '3': case '4':
   2110         case '5': case '6': case '7': case '8':
   2111         case '9':
   2112             {
   2113                 const uint8_t *q = ++p;
   2114 
   2115                 c = parse_digits(&p, FALSE);
   2116                 if (c < 0 || (c >= s->capture_count && c >= re_count_captures(s))) {
   2117                     if (!s->is_unicode) {
   2118                         /* Annex B.1.4: accept legacy octal */
   2119                         p = q;
   2120                         if (*p <= '7') {
   2121                             c = 0;
   2122                             if (*p <= '3')
   2123                                 c = *p++ - '0';
   2124                             if (*p >= '0' && *p <= '7') {
   2125                                 c = (c << 3) + *p++ - '0';
   2126                                 if (*p >= '0' && *p <= '7') {
   2127                                     c = (c << 3) + *p++ - '0';
   2128                                 }
   2129                             }
   2130                         } else {
   2131                             c = *p++;
   2132                         }
   2133                         goto normal_char;
   2134                     }
   2135                     return re_parse_error(s, "back reference out of range in regular expression");
   2136                 }
   2137                 last_atom_start = s->byte_code.size;
   2138                 last_capture_count = s->capture_count;
   2139                 
   2140                 re_emit_op_u8(s, REOP_back_reference + 2 * is_backward_dir + s->ignore_case, 1);
   2141                 dbuf_putc(&s->byte_code, c);
   2142             }
   2143             break;
   2144         default:
   2145             goto parse_class_atom;
   2146         }
   2147         break;
   2148     case '[':
   2149         last_atom_start = s->byte_code.size;
   2150         last_capture_count = s->capture_count;
   2151         if (is_backward_dir)
   2152             re_emit_op(s, REOP_prev);
   2153         if (re_parse_char_class(s, &p))
   2154             return -1;
   2155         if (is_backward_dir)
   2156             re_emit_op(s, REOP_prev);
   2157         break;
   2158     case ']':
   2159     case '}':
   2160         if (s->is_unicode)
   2161             return re_parse_error(s, "syntax error");
   2162         goto parse_class_atom;
   2163     default:
   2164     parse_class_atom:
   2165         c = get_class_atom(s, cr, &p, FALSE);
   2166         if ((int)c < 0)
   2167             return -1;
   2168     normal_char:
   2169         last_atom_start = s->byte_code.size;
   2170         last_capture_count = s->capture_count;
   2171         if (is_backward_dir)
   2172             re_emit_op(s, REOP_prev);
   2173         if (c >= CLASS_RANGE_BASE) {
   2174             int ret = 0;
   2175             /* optimize the common 'space' tests */
   2176             if (c == (CLASS_RANGE_BASE + CHAR_RANGE_s)) {
   2177                 re_emit_op(s, REOP_space);
   2178             } else if (c == (CLASS_RANGE_BASE + CHAR_RANGE_S)) {
   2179                 re_emit_op(s, REOP_not_space);
   2180             } else {
   2181                 ret = re_emit_string_list(s, cr);
   2182             }
   2183             re_string_list_free(cr);
   2184             if (ret)
   2185                 return -1;
   2186         } else {
   2187             if (s->ignore_case)
   2188                 c = lre_canonicalize(c, s->is_unicode);
   2189             re_emit_char(s, c);
   2190         }
   2191         if (is_backward_dir)
   2192             re_emit_op(s, REOP_prev);
   2193         break;
   2194     }
   2195 
   2196     /* quantifier */
   2197     if (last_atom_start >= 0) {
   2198         c = *p;
   2199         switch(c) {
   2200         case '*':
   2201             p++;
   2202             quant_min = 0;
   2203             quant_max = INT32_MAX;
   2204             goto quantifier;
   2205         case '+':
   2206             p++;
   2207             quant_min = 1;
   2208             quant_max = INT32_MAX;
   2209             goto quantifier;
   2210         case '?':
   2211             p++;
   2212             quant_min = 0;
   2213             quant_max = 1;
   2214             goto quantifier;
   2215         case '{':
   2216             {
   2217                 const uint8_t *p1 = p;
   2218                 /* As an extension (see ES6 annex B), we accept '{' not
   2219                    followed by digits as a normal atom */
   2220                 if (!is_digit(p[1])) {
   2221                     if (s->is_unicode)
   2222                         goto invalid_quant_count;
   2223                     break;
   2224                 }
   2225                 p++;
   2226                 quant_min = parse_digits(&p, TRUE);
   2227                 quant_max = quant_min;
   2228                 if (*p == ',') {
   2229                     p++;
   2230                     if (is_digit(*p)) {
   2231                         quant_max = parse_digits(&p, TRUE);
   2232                         if (quant_max < quant_min) {
   2233                         invalid_quant_count:
   2234                             return re_parse_error(s, "invalid repetition count");
   2235                         }
   2236                     } else {
   2237                         quant_max = INT32_MAX; /* infinity */
   2238                     }
   2239                 }
   2240                 if (*p != '}' && !s->is_unicode) {
   2241                     /* Annex B: normal atom if invalid '{' syntax */
   2242                     p = p1;
   2243                     break;
   2244                 }
   2245                 if (re_parse_expect(s, &p, '}'))
   2246                     return -1;
   2247             }
   2248         quantifier:
   2249             greedy = TRUE;
   2250             if (*p == '?') {
   2251                 p++;
   2252                 greedy = FALSE;
   2253             }
   2254             if (last_atom_start < 0) {
   2255                 return re_parse_error(s, "nothing to repeat");
   2256             }
   2257             {
   2258                 BOOL need_capture_init, add_zero_advance_check;
   2259                 int len, pos;
   2260                 
   2261                 /* the spec tells that if there is no advance when
   2262                    running the atom after the first quant_min times,
   2263                    then there is no match. We remove this test when we
   2264                    are sure the atom always advances the position. */
   2265                 add_zero_advance_check =
   2266                     re_need_check_adv_and_capture_init(&need_capture_init,
   2267                                                        s->byte_code.buf + last_atom_start,
   2268                                                        s->byte_code.size - last_atom_start);
   2269             
   2270                 /* general case: need to reset the capture at each
   2271                    iteration. We don't do it if there are no captures
   2272                    in the atom or if we are sure all captures are
   2273                    initialized in the atom. If quant_min = 0, we still
   2274                    need to reset once the captures in case the atom
   2275                    does not match. */
   2276                 if (need_capture_init && last_capture_count != s->capture_count) {
   2277                     if (dbuf_insert(&s->byte_code, last_atom_start, 3))
   2278                         goto out_of_memory;
   2279                     int pos = last_atom_start;
   2280                     s->byte_code.buf[pos++] = REOP_save_reset;
   2281                     s->byte_code.buf[pos++] = last_capture_count;
   2282                     s->byte_code.buf[pos++] = s->capture_count - 1;
   2283                 }
   2284 
   2285                 len = s->byte_code.size - last_atom_start;
   2286                 if (quant_min == 0) {
   2287                     /* need to reset the capture in case the atom is
   2288                        not executed */
   2289                     if (!need_capture_init && last_capture_count != s->capture_count) {
   2290                         if (dbuf_insert(&s->byte_code, last_atom_start, 3))
   2291                             goto out_of_memory;
   2292                         s->byte_code.buf[last_atom_start++] = REOP_save_reset;
   2293                         s->byte_code.buf[last_atom_start++] = last_capture_count;
   2294                         s->byte_code.buf[last_atom_start++] = s->capture_count - 1;
   2295                     }
   2296                     if (quant_max == 0) {
   2297                         s->byte_code.size = last_atom_start;
   2298                     } else if (quant_max == 1 || quant_max == INT32_MAX) {
   2299                         BOOL has_goto = (quant_max == INT32_MAX);
   2300                         if (dbuf_insert(&s->byte_code, last_atom_start, 5 + add_zero_advance_check * 2))
   2301                             goto out_of_memory;
   2302                         s->byte_code.buf[last_atom_start] = REOP_split_goto_first +
   2303                             greedy;
   2304                         put_u32(s->byte_code.buf + last_atom_start + 1,
   2305                                 len + 5 * has_goto + add_zero_advance_check * 2 * 2);
   2306                         if (add_zero_advance_check) {
   2307                             s->byte_code.buf[last_atom_start + 1 + 4] = REOP_set_char_pos;
   2308                             s->byte_code.buf[last_atom_start + 1 + 4 + 1] = 0;
   2309                             re_emit_op_u8(s, REOP_check_advance, 0);
   2310                         }
   2311                         if (has_goto)
   2312                             re_emit_goto(s, REOP_goto, last_atom_start);
   2313                     } else {
   2314                         if (dbuf_insert(&s->byte_code, last_atom_start, 11 + add_zero_advance_check * 2))
   2315                             goto out_of_memory;
   2316                         pos = last_atom_start;
   2317                         s->byte_code.buf[pos++] = REOP_split_goto_first + greedy;
   2318                         put_u32(s->byte_code.buf + pos, 6 + add_zero_advance_check * 2 + len + 10);
   2319                         pos += 4;
   2320 
   2321                         s->byte_code.buf[pos++] = REOP_set_i32;
   2322                         s->byte_code.buf[pos++] = 0;
   2323                         put_u32(s->byte_code.buf + pos, quant_max);
   2324                         pos += 4;
   2325                         last_atom_start = pos;
   2326                         if (add_zero_advance_check) {
   2327                             s->byte_code.buf[pos++] = REOP_set_char_pos;
   2328                             s->byte_code.buf[pos++] = 0;
   2329                         }
   2330                         re_emit_goto_u8_u32(s, (add_zero_advance_check ? REOP_loop_check_adv_split_next_first : REOP_loop_split_next_first) - greedy, 0, quant_max, last_atom_start);
   2331                     }
   2332                 } else if (quant_min == 1 && quant_max == INT32_MAX &&
   2333                            !add_zero_advance_check) {
   2334                     re_emit_goto(s, REOP_split_next_first - greedy,
   2335                                  last_atom_start);
   2336                 } else {
   2337                     if (quant_min == quant_max)
   2338                         add_zero_advance_check = FALSE;
   2339                     if (dbuf_insert(&s->byte_code, last_atom_start, 6 + add_zero_advance_check * 2))
   2340                         goto out_of_memory;
   2341                     /* Note: we assume the string length is < INT32_MAX */
   2342                     pos = last_atom_start;
   2343                     s->byte_code.buf[pos++] = REOP_set_i32;
   2344                     s->byte_code.buf[pos++] = 0;
   2345                     put_u32(s->byte_code.buf + pos, quant_max);
   2346                     pos += 4;
   2347                     last_atom_start = pos;
   2348                     if (add_zero_advance_check) {
   2349                         s->byte_code.buf[pos++] = REOP_set_char_pos;
   2350                         s->byte_code.buf[pos++] = 0;
   2351                     }
   2352                     if (quant_min == quant_max) {
   2353                         /* a simple loop is enough */
   2354                         re_emit_goto_u8(s, REOP_loop, 0, last_atom_start);
   2355                     } else {
   2356                         re_emit_goto_u8_u32(s, (add_zero_advance_check ? REOP_loop_check_adv_split_next_first : REOP_loop_split_next_first) - greedy, 0, quant_max - quant_min, last_atom_start);
   2357                     }
   2358                 }
   2359                 last_atom_start = -1;
   2360             }
   2361             break;
   2362         default:
   2363             break;
   2364         }
   2365     }
   2366     s->buf_ptr = p;
   2367     return 0;
   2368  out_of_memory:
   2369     return re_parse_out_of_memory(s);
   2370 }
   2371 
   2372 static int re_parse_alternative(REParseState *s, BOOL is_backward_dir)
   2373 {
   2374     const uint8_t *p;
   2375     int ret;
   2376     size_t start, term_start, end, term_size;
   2377 
   2378     start = s->byte_code.size;
   2379     for(;;) {
   2380         p = s->buf_ptr;
   2381         if (p >= s->buf_end)
   2382             break;
   2383         if (*p == '|' || *p == ')')
   2384             break;
   2385         term_start = s->byte_code.size;
   2386         ret = re_parse_term(s, is_backward_dir);
   2387         if (ret)
   2388             return ret;
   2389         if (is_backward_dir) {
   2390             /* reverse the order of the terms (XXX: inefficient, but
   2391                speed is not really critical here) */
   2392             end = s->byte_code.size;
   2393             term_size = end - term_start;
   2394             if (dbuf_claim(&s->byte_code, term_size))
   2395                 return -1;
   2396             memmove(s->byte_code.buf + start + term_size,
   2397                     s->byte_code.buf + start,
   2398                     end - start);
   2399             memcpy(s->byte_code.buf + start, s->byte_code.buf + end,
   2400                    term_size);
   2401         }
   2402     }
   2403     return 0;
   2404 }
   2405 
   2406 static int re_parse_disjunction(REParseState *s, BOOL is_backward_dir)
   2407 {
   2408     int start, len, pos;
   2409 
   2410     if (lre_check_stack_overflow(s->opaque, 0))
   2411         return re_parse_error(s, "stack overflow");
   2412 
   2413     start = s->byte_code.size;
   2414     if (re_parse_alternative(s, is_backward_dir))
   2415         return -1;
   2416     while (*s->buf_ptr == '|') {
   2417         s->buf_ptr++;
   2418 
   2419         len = s->byte_code.size - start;
   2420 
   2421         /* insert a split before the first alternative */
   2422         if (dbuf_insert(&s->byte_code, start, 5)) {
   2423             return re_parse_out_of_memory(s);
   2424         }
   2425         s->byte_code.buf[start] = REOP_split_next_first;
   2426         put_u32(s->byte_code.buf + start + 1, len + 5);
   2427 
   2428         pos = re_emit_op_u32(s, REOP_goto, 0);
   2429 
   2430         s->group_name_scope++;
   2431         
   2432         if (re_parse_alternative(s, is_backward_dir))
   2433             return -1;
   2434 
   2435         /* patch the goto */
   2436         len = s->byte_code.size - (pos + 4);
   2437         put_u32(s->byte_code.buf + pos, len);
   2438     }
   2439     return 0;
   2440 }
   2441 
   2442 /* Allocate the registers as a stack. The control flow is recursive so
   2443    the analysis can be linear. */
   2444 static int compute_register_count(uint8_t *bc_buf, int bc_buf_len)
   2445 {
   2446     int stack_size, stack_size_max, pos, opcode, len;
   2447     uint32_t val;
   2448 
   2449     stack_size = 0;
   2450     stack_size_max = 0;
   2451     bc_buf += RE_HEADER_LEN;
   2452     bc_buf_len -= RE_HEADER_LEN;
   2453     pos = 0;
   2454     while (pos < bc_buf_len) {
   2455         opcode = bc_buf[pos];
   2456         len = reopcode_info[opcode].size;
   2457         assert(opcode < REOP_COUNT);
   2458         assert((pos + len) <= bc_buf_len);
   2459         switch(opcode) {
   2460         case REOP_set_i32:
   2461         case REOP_set_char_pos:
   2462             bc_buf[pos + 1] = stack_size;
   2463             stack_size++;
   2464             if (stack_size > stack_size_max) {
   2465                 if (stack_size > REGISTER_COUNT_MAX)
   2466                     return -1;
   2467                 stack_size_max = stack_size;
   2468             }
   2469             break;
   2470         case REOP_check_advance:
   2471         case REOP_loop:
   2472         case REOP_loop_split_goto_first:
   2473         case REOP_loop_split_next_first:
   2474             assert(stack_size > 0);
   2475             stack_size--;
   2476             bc_buf[pos + 1] = stack_size;
   2477             break;
   2478         case REOP_loop_check_adv_split_goto_first:
   2479         case REOP_loop_check_adv_split_next_first:
   2480             assert(stack_size >= 2);
   2481             stack_size -= 2;
   2482             bc_buf[pos + 1] = stack_size;
   2483             break;
   2484         case REOP_range:
   2485         case REOP_range_i:
   2486             val = get_u16(bc_buf + pos + 1);
   2487             len += val * 4;
   2488             break;
   2489         case REOP_range32:
   2490         case REOP_range32_i:
   2491             val = get_u16(bc_buf + pos + 1);
   2492             len += val * 8;
   2493             break;
   2494         case REOP_back_reference:
   2495         case REOP_back_reference_i:
   2496         case REOP_backward_back_reference:
   2497         case REOP_backward_back_reference_i:
   2498             val = bc_buf[pos + 1];
   2499             len += val;
   2500             break;
   2501         }
   2502         pos += len;
   2503     }
   2504     return stack_size_max;
   2505 }
   2506 
   2507 static void *lre_bytecode_realloc(void *opaque, void *ptr, size_t size)
   2508 {
   2509     if (size > (INT32_MAX / 2)) {
   2510         /* the bytecode cannot be larger than 2G. Leave some slack to 
   2511            avoid some overflows. */
   2512         return NULL;
   2513     } else {
   2514         return lre_realloc(opaque, ptr, size);
   2515     }
   2516 }
   2517 
   2518 /* 'buf' must be a zero terminated UTF-8 string of length buf_len.
   2519    Return NULL if error and allocate an error message in *perror_msg,
   2520    otherwise the compiled bytecode and its length in plen.
   2521 */
   2522 uint8_t *lre_compile(int *plen, char *error_msg, int error_msg_size,
   2523                      const char *buf, size_t buf_len, int re_flags,
   2524                      void *opaque)
   2525 {
   2526     REParseState s_s, *s = &s_s;
   2527     int register_count;
   2528     BOOL is_sticky;
   2529 
   2530     memset(s, 0, sizeof(*s));
   2531     s->opaque = opaque;
   2532     s->buf_ptr = (const uint8_t *)buf;
   2533     s->buf_end = s->buf_ptr + buf_len;
   2534     s->buf_start = s->buf_ptr;
   2535     s->re_flags = re_flags;
   2536     s->is_unicode = ((re_flags & (LRE_FLAG_UNICODE | LRE_FLAG_UNICODE_SETS)) != 0);
   2537     is_sticky = ((re_flags & LRE_FLAG_STICKY) != 0);
   2538     s->ignore_case = ((re_flags & LRE_FLAG_IGNORECASE) != 0);
   2539     s->multi_line = ((re_flags & LRE_FLAG_MULTILINE) != 0);
   2540     s->dotall = ((re_flags & LRE_FLAG_DOTALL) != 0);
   2541     s->unicode_sets = ((re_flags & LRE_FLAG_UNICODE_SETS) != 0);
   2542     s->capture_count = 1;
   2543     s->total_capture_count = -1;
   2544     s->has_named_captures = -1;
   2545 
   2546     dbuf_init2(&s->byte_code, opaque, lre_bytecode_realloc);
   2547     dbuf_init2(&s->group_names, opaque, lre_realloc);
   2548 
   2549     dbuf_put_u16(&s->byte_code, re_flags); /* first element is the flags */
   2550     dbuf_putc(&s->byte_code, 0); /* second element is the number of captures */
   2551     dbuf_putc(&s->byte_code, 0); /* stack size */
   2552     dbuf_put_u32(&s->byte_code, 0); /* bytecode length */
   2553 
   2554     if (!is_sticky) {
   2555         /* iterate thru all positions (about the same as .*?( ... ) )
   2556            .  We do it without an explicit loop so that lock step
   2557            thread execution will be possible in an optimized
   2558            implementation */
   2559         re_emit_op_u32(s, REOP_split_goto_first, 1 + 5);
   2560         re_emit_op(s, REOP_any);
   2561         re_emit_op_u32(s, REOP_goto, -(5 + 1 + 5));
   2562     }
   2563     re_emit_op_u8(s, REOP_save_start, 0);
   2564 
   2565     if (re_parse_disjunction(s, FALSE)) {
   2566     error:
   2567         dbuf_free(&s->byte_code);
   2568         dbuf_free(&s->group_names);
   2569         pstrcpy(error_msg, error_msg_size, s->u.error_msg);
   2570         *plen = 0;
   2571         return NULL;
   2572     }
   2573 
   2574     re_emit_op_u8(s, REOP_save_end, 0);
   2575 
   2576     re_emit_op(s, REOP_match);
   2577 
   2578     if (*s->buf_ptr != '\0') {
   2579         re_parse_error(s, "extraneous characters at the end");
   2580         goto error;
   2581     }
   2582 
   2583     if (dbuf_error(&s->byte_code)) {
   2584         re_parse_out_of_memory(s);
   2585         goto error;
   2586     }
   2587 
   2588     register_count = compute_register_count(s->byte_code.buf, s->byte_code.size);
   2589     if (register_count < 0) {
   2590         re_parse_error(s, "too many imbricated quantifiers");
   2591         goto error;
   2592     }
   2593 
   2594     s->byte_code.buf[RE_HEADER_CAPTURE_COUNT] = s->capture_count;
   2595     s->byte_code.buf[RE_HEADER_REGISTER_COUNT] = register_count;
   2596     put_u32(s->byte_code.buf + RE_HEADER_BYTECODE_LEN,
   2597             s->byte_code.size - RE_HEADER_LEN);
   2598 
   2599     /* add the named groups if needed */
   2600     if (s->group_names.size > (s->capture_count - 1) * LRE_GROUP_NAME_TRAILER_LEN) {
   2601         dbuf_put(&s->byte_code, s->group_names.buf, s->group_names.size);
   2602         put_u16(s->byte_code.buf + RE_HEADER_FLAGS,
   2603                 lre_get_flags(s->byte_code.buf) | LRE_FLAG_NAMED_GROUPS);
   2604     }
   2605     dbuf_free(&s->group_names);
   2606 
   2607 #ifdef DUMP_REOP
   2608     lre_dump_bytecode(s->byte_code.buf, s->byte_code.size);
   2609 #endif
   2610 
   2611     error_msg[0] = '\0';
   2612     *plen = s->byte_code.size;
   2613     return s->byte_code.buf;
   2614 }
   2615 
   2616 static BOOL is_line_terminator(uint32_t c)
   2617 {
   2618     return (c == '\n' || c == '\r' || c == CP_LS || c == CP_PS);
   2619 }
   2620 
   2621 #define GET_CHAR(c, cptr, cbuf_end, cbuf_type)                          \
   2622     do {                                                                \
   2623         if (cbuf_type == 0) {                                           \
   2624             c = *cptr++;                                                \
   2625         } else {                                                        \
   2626             const uint16_t *_p = (const uint16_t *)cptr;                \
   2627             const uint16_t *_end = (const uint16_t *)cbuf_end;          \
   2628             c = *_p++;                                                  \
   2629             if (is_hi_surrogate(c) && cbuf_type == 2) {                 \
   2630                 if (_p < _end && is_lo_surrogate(*_p)) {                \
   2631                     c = from_surrogate(c, *_p++);                       \
   2632                 }                                                       \
   2633             }                                                           \
   2634             cptr = (const void *)_p;                                    \
   2635         }                                                               \
   2636     } while (0)
   2637 
   2638 #define PEEK_CHAR(c, cptr, cbuf_end, cbuf_type)                         \
   2639     do {                                                                \
   2640         if (cbuf_type == 0) {                                           \
   2641             c = cptr[0];                                                \
   2642         } else {                                                        \
   2643             const uint16_t *_p = (const uint16_t *)cptr;                \
   2644             const uint16_t *_end = (const uint16_t *)cbuf_end;          \
   2645             c = *_p++;                                                  \
   2646             if (is_hi_surrogate(c) && cbuf_type == 2) {                 \
   2647                 if (_p < _end && is_lo_surrogate(*_p)) {                \
   2648                     c = from_surrogate(c, *_p);                         \
   2649                 }                                                       \
   2650             }                                                           \
   2651         }                                                               \
   2652     } while (0)
   2653 
   2654 #define PEEK_PREV_CHAR(c, cptr, cbuf_start, cbuf_type)                  \
   2655     do {                                                                \
   2656         if (cbuf_type == 0) {                                           \
   2657             c = cptr[-1];                                               \
   2658         } else {                                                        \
   2659             const uint16_t *_p = (const uint16_t *)cptr - 1;            \
   2660             const uint16_t *_start = (const uint16_t *)cbuf_start;      \
   2661             c = *_p;                                                    \
   2662             if (is_lo_surrogate(c) && cbuf_type == 2) {                 \
   2663                 if (_p > _start && is_hi_surrogate(_p[-1])) {           \
   2664                     c = from_surrogate(*--_p, c);                       \
   2665                 }                                                       \
   2666             }                                                           \
   2667         }                                                               \
   2668     } while (0)
   2669 
   2670 #define GET_PREV_CHAR(c, cptr, cbuf_start, cbuf_type)                   \
   2671     do {                                                                \
   2672         if (cbuf_type == 0) {                                           \
   2673             cptr--;                                                     \
   2674             c = cptr[0];                                                \
   2675         } else {                                                        \
   2676             const uint16_t *_p = (const uint16_t *)cptr - 1;            \
   2677             const uint16_t *_start = (const uint16_t *)cbuf_start;      \
   2678             c = *_p;                                                    \
   2679             if (is_lo_surrogate(c) && cbuf_type == 2) {                 \
   2680                 if (_p > _start && is_hi_surrogate(_p[-1])) {           \
   2681                     c = from_surrogate(*--_p, c);                       \
   2682                 }                                                       \
   2683             }                                                           \
   2684             cptr = (const void *)_p;                                    \
   2685         }                                                               \
   2686     } while (0)
   2687 
   2688 #define PREV_CHAR(cptr, cbuf_start, cbuf_type)                          \
   2689     do {                                                                \
   2690         if (cbuf_type == 0) {                                           \
   2691             cptr--;                                                     \
   2692         } else {                                                        \
   2693             const uint16_t *_p = (const uint16_t *)cptr - 1;            \
   2694             const uint16_t *_start = (const uint16_t *)cbuf_start;      \
   2695             if (is_lo_surrogate(*_p) && cbuf_type == 2) {               \
   2696                 if (_p > _start && is_hi_surrogate(_p[-1])) {           \
   2697                     --_p;                                               \
   2698                 }                                                       \
   2699             }                                                           \
   2700             cptr = (const void *)_p;                                    \
   2701         }                                                               \
   2702     } while (0)
   2703 
   2704 typedef enum {
   2705     RE_EXEC_STATE_SPLIT,
   2706     RE_EXEC_STATE_LOOKAHEAD,
   2707     RE_EXEC_STATE_NEGATIVE_LOOKAHEAD,
   2708 } REExecStateEnum;
   2709 
   2710 #if INTPTR_MAX >= INT64_MAX
   2711 #define BP_TYPE_BITS 3
   2712 #else
   2713 #define BP_TYPE_BITS 2
   2714 #endif
   2715 
   2716 typedef union {
   2717     uint8_t *ptr;
   2718     intptr_t val; /* for bp, the low BP_SHIFT bits store REExecStateEnum */
   2719     struct {
   2720         uintptr_t val : sizeof(uintptr_t) * 8 - BP_TYPE_BITS;
   2721         uintptr_t type : BP_TYPE_BITS;
   2722     } bp;
   2723 } StackElem;
   2724 
   2725 typedef struct {
   2726     const uint8_t *cbuf;
   2727     const uint8_t *cbuf_end;
   2728     /* 0 = 8 bit chars, 1 = 16 bit chars, 2 = 16 bit chars, UTF-16 */
   2729     int cbuf_type;
   2730     int capture_count;
   2731     BOOL is_unicode;
   2732     int interrupt_counter;
   2733     void *opaque; /* used for stack overflow check */
   2734 
   2735     StackElem *stack_buf;
   2736     size_t stack_size;
   2737     StackElem static_stack_buf[32]; /* static stack to avoid allocation in most cases */
   2738 } REExecContext;
   2739 
   2740 static int lre_poll_timeout(REExecContext *s)
   2741 {
   2742     if (unlikely(--s->interrupt_counter <= 0)) {
   2743         s->interrupt_counter = INTERRUPT_COUNTER_INIT;
   2744         if (lre_check_timeout(s->opaque))
   2745             return LRE_RET_TIMEOUT;
   2746     }
   2747     return 0;
   2748 }
   2749 
   2750 static no_inline int stack_realloc(REExecContext *s, size_t n)
   2751 {
   2752     StackElem *new_stack;
   2753     size_t new_size;
   2754     new_size = s->stack_size * 3 / 2;
   2755     if (new_size < n)
   2756         new_size = n;
   2757     if (s->stack_buf == s->static_stack_buf) {
   2758         new_stack = lre_realloc(s->opaque, NULL, new_size * sizeof(StackElem));
   2759         if (!new_stack)
   2760             return -1;
   2761         /* XXX: could use correct size */
   2762         memcpy(new_stack, s->stack_buf, s->stack_size * sizeof(StackElem));
   2763     } else {
   2764         new_stack = lre_realloc(s->opaque, s->stack_buf, new_size * sizeof(StackElem));
   2765         if (!new_stack)
   2766             return -1;
   2767     }
   2768     s->stack_size = new_size;
   2769     s->stack_buf = new_stack;
   2770     return 0;
   2771 }
   2772 
   2773 /* return 1 if match, 0 if not match or < 0 if error. */
   2774 static intptr_t lre_exec_backtrack(REExecContext *s, uint8_t **capture,
   2775                                    const uint8_t *pc, const uint8_t *cptr)
   2776 {
   2777     int opcode;
   2778     int cbuf_type;
   2779     uint32_t val, c, idx;
   2780     const uint8_t *cbuf_end;
   2781     StackElem *sp, *bp, *stack_end;
   2782 #ifdef DUMP_EXEC
   2783     const uint8_t *pc_start = pc; /* TEST */
   2784 #endif
   2785     cbuf_type = s->cbuf_type;
   2786     cbuf_end = s->cbuf_end;
   2787 
   2788     sp = s->stack_buf;
   2789     bp = s->stack_buf;
   2790     stack_end = s->stack_buf + s->stack_size;
   2791     
   2792 #define CHECK_STACK_SPACE(n)                            \
   2793     if (unlikely((stack_end - sp) < (n))) {             \
   2794         size_t saved_sp = sp - s->stack_buf;            \
   2795         size_t saved_bp = bp - s->stack_buf;            \
   2796         if (stack_realloc(s, sp - s->stack_buf + (n)))  \
   2797             return LRE_RET_MEMORY_ERROR;                \
   2798         stack_end = s->stack_buf + s->stack_size;       \
   2799         sp = s->stack_buf + saved_sp;                   \
   2800         bp = s->stack_buf + saved_bp;                   \
   2801     }
   2802 
   2803     /* XXX: could test if the value was saved to reduce the stack size
   2804        but slower */
   2805 #define SAVE_CAPTURE(idx, value)                        \
   2806     {                                                   \
   2807         CHECK_STACK_SPACE(2);                           \
   2808         sp[0].val = idx;                                \
   2809         sp[1].ptr = capture[idx];                       \
   2810         sp += 2;                                        \
   2811         capture[idx] = (value);                         \
   2812     }
   2813 
   2814     /* avoid saving the previous value if already saved */
   2815 #define SAVE_CAPTURE_CHECK(idx, value)          \
   2816     {                                           \
   2817         StackElem *sp1;                         \
   2818         sp1 = sp;                               \
   2819         for(;;) {                               \
   2820             if (sp1 > bp) {                             \
   2821                 if (sp1[-2].val == idx)                 \
   2822                     break;                              \
   2823                 sp1 -= 2;                               \
   2824             } else {                                    \
   2825                 CHECK_STACK_SPACE(2);                   \
   2826                 sp[0].val = idx;                        \
   2827                 sp[1].ptr = capture[idx];               \
   2828                 sp += 2;                                \
   2829                 break;                                  \
   2830             }                                           \
   2831         }                                               \
   2832         capture[idx] = (value);                         \
   2833     }
   2834 
   2835 
   2836 #ifdef DUMP_EXEC
   2837     printf("%5s %5s %5s %5s %s\n", "PC", "CP", "BP", "SP", "OPCODE");
   2838 #endif    
   2839     for(;;) {
   2840         opcode = *pc++;
   2841 #ifdef DUMP_EXEC
   2842         printf("%5ld %5ld %5ld %5ld %s\n",
   2843                pc - 1 - pc_start,
   2844                cbuf_type == 0 ? cptr - s->cbuf : (cptr - s->cbuf) / 2,
   2845                bp - s->stack_buf,
   2846                sp - s->stack_buf,
   2847                reopcode_info[opcode].name);
   2848 #endif        
   2849         switch(opcode) {
   2850         case REOP_match:
   2851             return 1;
   2852         no_match:
   2853             for(;;) {
   2854                 REExecStateEnum type;
   2855                 if (bp == s->stack_buf)
   2856                     return 0;
   2857                 /* undo the modifications to capture[] */
   2858                 while (sp > bp) {
   2859                     capture[sp[-2].val] = sp[-1].ptr;
   2860                     sp -= 2;
   2861                 }
   2862                 
   2863                 pc = sp[-3].ptr;
   2864                 cptr = sp[-2].ptr;
   2865                 type = sp[-1].bp.type;
   2866                 bp = s->stack_buf + sp[-1].bp.val;
   2867                 sp -= 3;
   2868                 if (type != RE_EXEC_STATE_LOOKAHEAD)
   2869                     break;
   2870             }
   2871             if (lre_poll_timeout(s))
   2872                 return LRE_RET_TIMEOUT;
   2873             break;
   2874         case REOP_lookahead_match:
   2875             /* pop all the saved states until reaching the start of
   2876                the lookahead and keep the updated captures and
   2877                variables and the corresponding undo info. */
   2878             {
   2879                 StackElem *sp1, *sp_top, *next_sp;
   2880                 REExecStateEnum type;
   2881 
   2882                 sp_top = sp;
   2883                 for(;;) {
   2884                     sp1 = sp;
   2885                     sp = bp;
   2886                     pc = sp[-3].ptr;
   2887                     cptr = sp[-2].ptr;
   2888                     type = sp[-1].bp.type;
   2889                     bp = s->stack_buf + sp[-1].bp.val;
   2890                     sp[-1].ptr = (void *)sp1; /* save the next value for the copy step */
   2891                     sp -= 3;
   2892                     if (type == RE_EXEC_STATE_LOOKAHEAD)
   2893                         break;
   2894                 }
   2895                 if (sp != s->stack_buf) {
   2896                     /* keep the undo info if there is a saved state */
   2897                     sp1 = sp;
   2898                     while (sp1 < sp_top) {
   2899                         next_sp = (void *)sp1[2].ptr;
   2900                         sp1 += 3;
   2901                         while (sp1 < next_sp)
   2902                             *sp++ = *sp1++;
   2903                     }
   2904                 }
   2905             }
   2906             break;
   2907         case REOP_negative_lookahead_match:
   2908             /* pop all the saved states until reaching start of the negative lookahead */
   2909             for(;;) {
   2910                 REExecStateEnum type;
   2911                 type = bp[-1].bp.type;
   2912                 /* undo the modifications to capture[] */
   2913                 while (sp > bp) {
   2914                     capture[sp[-2].val] = sp[-1].ptr;
   2915                     sp -= 2;
   2916                 }
   2917                 pc = sp[-3].ptr;
   2918                 cptr = sp[-2].ptr;
   2919                 type = sp[-1].bp.type;
   2920                 bp = s->stack_buf + sp[-1].bp.val;
   2921                 sp -= 3;
   2922                 if (type == RE_EXEC_STATE_NEGATIVE_LOOKAHEAD)
   2923                     break;
   2924             }
   2925             goto no_match;
   2926         case REOP_char32:
   2927         case REOP_char32_i:
   2928             val = get_u32(pc);
   2929             pc += 4;
   2930             goto test_char;
   2931         case REOP_char:
   2932         case REOP_char_i:
   2933             val = get_u16(pc);
   2934             pc += 2;
   2935         test_char:
   2936             if (cptr >= cbuf_end)
   2937                 goto no_match;
   2938             GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   2939             if (opcode == REOP_char_i || opcode == REOP_char32_i) {
   2940                 c = lre_canonicalize(c, s->is_unicode);
   2941             }
   2942             if (val != c)
   2943                 goto no_match;
   2944             break;
   2945         case REOP_split_goto_first:
   2946         case REOP_split_next_first:
   2947             {
   2948                 const uint8_t *pc1;
   2949 
   2950                 val = get_u32(pc);
   2951                 pc += 4;
   2952                 if (opcode == REOP_split_next_first) {
   2953                     pc1 = pc + (int)val;
   2954                 } else {
   2955                     pc1 = pc;
   2956                     pc = pc + (int)val;
   2957                 }
   2958                 CHECK_STACK_SPACE(3);
   2959                 sp[0].ptr = (uint8_t *)pc1;
   2960                 sp[1].ptr = (uint8_t *)cptr;
   2961                 sp[2].bp.val = bp - s->stack_buf;
   2962                 sp[2].bp.type = RE_EXEC_STATE_SPLIT;
   2963                 sp += 3;
   2964                 bp = sp;
   2965             }
   2966             break;
   2967         case REOP_lookahead:
   2968         case REOP_negative_lookahead:
   2969             val = get_u32(pc);
   2970             pc += 4;
   2971             CHECK_STACK_SPACE(3);
   2972             sp[0].ptr = (uint8_t *)(pc + (int)val);
   2973             sp[1].ptr = (uint8_t *)cptr;
   2974             sp[2].bp.val = bp - s->stack_buf;
   2975             sp[2].bp.type = RE_EXEC_STATE_LOOKAHEAD + opcode - REOP_lookahead;
   2976             sp += 3;
   2977             bp = sp;
   2978             break;
   2979         case REOP_goto:
   2980             val = get_u32(pc);
   2981             pc += 4 + (int)val;
   2982             if (lre_poll_timeout(s))
   2983                 return LRE_RET_TIMEOUT;
   2984             break;
   2985         case REOP_line_start:
   2986         case REOP_line_start_m:
   2987             if (cptr == s->cbuf)
   2988                 break;
   2989             if (opcode == REOP_line_start)
   2990                 goto no_match;
   2991             PEEK_PREV_CHAR(c, cptr, s->cbuf, cbuf_type);
   2992             if (!is_line_terminator(c))
   2993                 goto no_match;
   2994             break;
   2995         case REOP_line_end:
   2996         case REOP_line_end_m:
   2997             if (cptr == cbuf_end)
   2998                 break;
   2999             if (opcode == REOP_line_end)
   3000                 goto no_match;
   3001             PEEK_CHAR(c, cptr, cbuf_end, cbuf_type);
   3002             if (!is_line_terminator(c))
   3003                 goto no_match;
   3004             break;
   3005         case REOP_dot:
   3006             if (cptr == cbuf_end)
   3007                 goto no_match;
   3008             GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   3009             if (is_line_terminator(c))
   3010                 goto no_match;
   3011             break;
   3012         case REOP_any:
   3013             if (cptr == cbuf_end)
   3014                 goto no_match;
   3015             GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   3016             break;
   3017         case REOP_space:
   3018             if (cptr == cbuf_end)
   3019                 goto no_match;
   3020             GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   3021             if (!lre_is_space(c))
   3022                 goto no_match;
   3023             break;
   3024         case REOP_not_space:
   3025             if (cptr == cbuf_end)
   3026                 goto no_match;
   3027             GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   3028             if (lre_is_space(c))
   3029                 goto no_match;
   3030             break;
   3031         case REOP_save_start:
   3032         case REOP_save_end:
   3033             val = *pc++;
   3034             assert(val < s->capture_count);
   3035             idx = 2 * val + opcode - REOP_save_start;
   3036             SAVE_CAPTURE(idx, (uint8_t *)cptr);
   3037             break;
   3038         case REOP_save_reset:
   3039             {
   3040                 uint32_t val2;
   3041                 val = pc[0];
   3042                 val2 = pc[1];
   3043                 pc += 2;
   3044                 assert(val2 < s->capture_count);
   3045                 CHECK_STACK_SPACE(2 * (val2 - val + 1));
   3046                 while (val <= val2) {
   3047                     idx = 2 * val;
   3048                     SAVE_CAPTURE(idx, NULL);
   3049                     idx = 2 * val + 1;
   3050                     SAVE_CAPTURE(idx, NULL);
   3051                     val++;
   3052                 }
   3053             }
   3054             break;
   3055         case REOP_set_i32:
   3056             idx = 2 * s->capture_count + pc[0];
   3057             val = get_u32(pc + 1);
   3058             pc += 5;
   3059             SAVE_CAPTURE_CHECK(idx, (void *)(uintptr_t)val);
   3060             break;
   3061         case REOP_loop:
   3062             {
   3063                 uint32_t val2;
   3064                 idx = 2 * s->capture_count + pc[0];
   3065                 val = get_u32(pc + 1);
   3066                 pc += 5;
   3067 
   3068                 val2 = (uintptr_t)capture[idx] - 1;
   3069                 SAVE_CAPTURE_CHECK(idx, (void *)(uintptr_t)val2);
   3070                 if (val2 != 0) {
   3071                     pc += (int)val;
   3072                     if (lre_poll_timeout(s))
   3073                         return LRE_RET_TIMEOUT;
   3074                 }
   3075             }
   3076             break;
   3077         case REOP_loop_split_goto_first:
   3078         case REOP_loop_split_next_first:
   3079         case REOP_loop_check_adv_split_goto_first:
   3080         case REOP_loop_check_adv_split_next_first:
   3081             {
   3082                 const uint8_t *pc1;
   3083                 uint32_t val2, limit;
   3084                 idx = 2 * s->capture_count + pc[0];
   3085                 limit = get_u32(pc + 1);
   3086                 val = get_u32(pc + 5);
   3087                 pc += 9;
   3088 
   3089                 /* decrement the counter */
   3090                 val2 = (uintptr_t)capture[idx] - 1;
   3091                 SAVE_CAPTURE_CHECK(idx, (void *)(uintptr_t)val2);
   3092 
   3093                 if (val2 > limit) {
   3094                     /* normal loop if counter > limit */
   3095                     pc += (int)val;
   3096                     if (lre_poll_timeout(s))
   3097                         return LRE_RET_TIMEOUT;
   3098                 } else {
   3099                     /* check advance */
   3100                     if ((opcode == REOP_loop_check_adv_split_goto_first ||
   3101                          opcode == REOP_loop_check_adv_split_next_first) &&
   3102                         capture[idx + 1] == cptr &&
   3103                         val2 != limit) {
   3104                         goto no_match;
   3105                     }
   3106                     
   3107                     /* otherwise conditional split */
   3108                     if (val2 != 0) {
   3109                         if (opcode == REOP_loop_split_next_first ||
   3110                             opcode == REOP_loop_check_adv_split_next_first) {
   3111                             pc1 = pc + (int)val;
   3112                         } else {
   3113                             pc1 = pc;
   3114                             pc = pc + (int)val;
   3115                         }
   3116                         CHECK_STACK_SPACE(3);
   3117                         sp[0].ptr = (uint8_t *)pc1;
   3118                         sp[1].ptr = (uint8_t *)cptr;
   3119                         sp[2].bp.val = bp - s->stack_buf;
   3120                         sp[2].bp.type = RE_EXEC_STATE_SPLIT;
   3121                         sp += 3;
   3122                         bp = sp;
   3123                     }
   3124                 }
   3125             }
   3126             break;
   3127         case REOP_set_char_pos:
   3128             idx = 2 * s->capture_count + pc[0];
   3129             pc++;
   3130             SAVE_CAPTURE_CHECK(idx, (uint8_t *)cptr);
   3131             break;
   3132         case REOP_check_advance:
   3133             idx = 2 * s->capture_count + pc[0];
   3134             pc++;
   3135             if (capture[idx] == cptr)
   3136                 goto no_match;
   3137             break;
   3138         case REOP_word_boundary:
   3139         case REOP_word_boundary_i:
   3140         case REOP_not_word_boundary:
   3141         case REOP_not_word_boundary_i:
   3142             {
   3143                 BOOL v1, v2;
   3144                 int ignore_case = (opcode == REOP_word_boundary_i || opcode == REOP_not_word_boundary_i);
   3145                 BOOL is_boundary = (opcode == REOP_word_boundary || opcode == REOP_word_boundary_i);
   3146                 /* char before */
   3147                 if (cptr == s->cbuf) {
   3148                     v1 = FALSE;
   3149                 } else {
   3150                     PEEK_PREV_CHAR(c, cptr, s->cbuf, cbuf_type);
   3151                     if (c < 256) {
   3152                         v1 = (lre_is_word_byte(c) != 0);
   3153                     } else {
   3154                         v1 = ignore_case && (c == 0x017f || c == 0x212a);
   3155                     }
   3156                 }
   3157                 /* current char */
   3158                 if (cptr >= cbuf_end) {
   3159                     v2 = FALSE;
   3160                 } else {
   3161                     PEEK_CHAR(c, cptr, cbuf_end, cbuf_type);
   3162                     if (c < 256) {
   3163                         v2 = (lre_is_word_byte(c) != 0);
   3164                     } else {
   3165                         v2 = ignore_case && (c == 0x017f || c == 0x212a);
   3166                     }
   3167                 }
   3168                 if (v1 ^ v2 ^ is_boundary)
   3169                     goto no_match;
   3170             }
   3171             break;
   3172         case REOP_back_reference:
   3173         case REOP_back_reference_i:
   3174         case REOP_backward_back_reference:
   3175         case REOP_backward_back_reference_i:
   3176             {
   3177                 const uint8_t *cptr1, *cptr1_end, *cptr1_start;
   3178                 const uint8_t *pc1;
   3179                 uint32_t c1, c2;
   3180                 int i, n;
   3181 
   3182                 n = *pc++;
   3183                 pc1 = pc;
   3184                 pc += n;
   3185 
   3186                 for(i = 0; i < n; i++) {
   3187                     val = pc1[i];
   3188                     if (val >= s->capture_count)
   3189                         goto no_match;
   3190                     cptr1_start = capture[2 * val];
   3191                     cptr1_end = capture[2 * val + 1];
   3192                     /* test the first not empty capture */
   3193                     if (cptr1_start && cptr1_end) {
   3194                         if (opcode == REOP_back_reference ||
   3195                             opcode == REOP_back_reference_i) {
   3196                             cptr1 = cptr1_start;
   3197                             while (cptr1 < cptr1_end) {
   3198                                 if (cptr >= cbuf_end)
   3199                                     goto no_match;
   3200                                 GET_CHAR(c1, cptr1, cptr1_end, cbuf_type);
   3201                                 GET_CHAR(c2, cptr, cbuf_end, cbuf_type);
   3202                                 if (opcode == REOP_back_reference_i) {
   3203                                     c1 = lre_canonicalize(c1, s->is_unicode);
   3204                                     c2 = lre_canonicalize(c2, s->is_unicode);
   3205                                 }
   3206                                 if (c1 != c2)
   3207                                     goto no_match;
   3208                             }
   3209                         } else {
   3210                             cptr1 = cptr1_end;
   3211                             while (cptr1 > cptr1_start) {
   3212                                 if (cptr == s->cbuf)
   3213                                     goto no_match;
   3214                                 GET_PREV_CHAR(c1, cptr1, cptr1_start, cbuf_type);
   3215                                 GET_PREV_CHAR(c2, cptr, s->cbuf, cbuf_type);
   3216                                 if (opcode == REOP_backward_back_reference_i) {
   3217                                     c1 = lre_canonicalize(c1, s->is_unicode);
   3218                                     c2 = lre_canonicalize(c2, s->is_unicode);
   3219                                 }
   3220                                 if (c1 != c2)
   3221                                     goto no_match;
   3222                             }
   3223                         }
   3224                         break;
   3225                     }
   3226                 }
   3227             }
   3228             break;
   3229         case REOP_range:
   3230         case REOP_range_i:
   3231             {
   3232                 int n;
   3233                 uint32_t low, high, idx_min, idx_max, idx;
   3234 
   3235                 n = get_u16(pc); /* n must be >= 1 */
   3236                 pc += 2;
   3237                 if (cptr >= cbuf_end)
   3238                     goto no_match;
   3239                 GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   3240                 if (opcode == REOP_range_i) {
   3241                     c = lre_canonicalize(c, s->is_unicode);
   3242                 }
   3243                 idx_min = 0;
   3244                 low = get_u16(pc + 0 * 4);
   3245                 if (c < low)
   3246                     goto no_match;
   3247                 idx_max = n - 1;
   3248                 high = get_u16(pc + idx_max * 4 + 2);
   3249                 /* 0xffff in for last value means +infinity */
   3250                 if (unlikely(c >= 0xffff) && high == 0xffff)
   3251                     goto range_match;
   3252                 if (c > high)
   3253                     goto no_match;
   3254                 while (idx_min <= idx_max) {
   3255                     idx = (idx_min + idx_max) / 2;
   3256                     low = get_u16(pc + idx * 4);
   3257                     high = get_u16(pc + idx * 4 + 2);
   3258                     if (c < low)
   3259                         idx_max = idx - 1;
   3260                     else if (c > high)
   3261                         idx_min = idx + 1;
   3262                     else
   3263                         goto range_match;
   3264                 }
   3265                 goto no_match;
   3266             range_match:
   3267                 pc += 4 * n;
   3268             }
   3269             break;
   3270         case REOP_range32:
   3271         case REOP_range32_i:
   3272             {
   3273                 int n;
   3274                 uint32_t low, high, idx_min, idx_max, idx;
   3275 
   3276                 n = get_u16(pc); /* n must be >= 1 */
   3277                 pc += 2;
   3278                 if (cptr >= cbuf_end)
   3279                     goto no_match;
   3280                 GET_CHAR(c, cptr, cbuf_end, cbuf_type);
   3281                 if (opcode == REOP_range32_i) {
   3282                     c = lre_canonicalize(c, s->is_unicode);
   3283                 }
   3284                 idx_min = 0;
   3285                 low = get_u32(pc + 0 * 8);
   3286                 if (c < low)
   3287                     goto no_match;
   3288                 idx_max = n - 1;
   3289                 high = get_u32(pc + idx_max * 8 + 4);
   3290                 if (c > high)
   3291                     goto no_match;
   3292                 while (idx_min <= idx_max) {
   3293                     idx = (idx_min + idx_max) / 2;
   3294                     low = get_u32(pc + idx * 8);
   3295                     high = get_u32(pc + idx * 8 + 4);
   3296                     if (c < low)
   3297                         idx_max = idx - 1;
   3298                     else if (c > high)
   3299                         idx_min = idx + 1;
   3300                     else
   3301                         goto range32_match;
   3302                 }
   3303                 goto no_match;
   3304             range32_match:
   3305                 pc += 8 * n;
   3306             }
   3307             break;
   3308         case REOP_prev:
   3309             /* go to the previous char */
   3310             if (cptr == s->cbuf)
   3311                 goto no_match;
   3312             PREV_CHAR(cptr, s->cbuf, cbuf_type);
   3313             break;
   3314         default:
   3315 #ifdef DUMP_EXEC
   3316             printf("unknown opcode pc=%ld\n", pc - 1 - pc_start);
   3317 #endif            
   3318             abort();
   3319         }
   3320     }
   3321 }
   3322 
   3323 /* Return 1 if match, 0 if not match or < 0 if error (see LRE_RET_x). cindex is the
   3324    starting position of the match and must be such as 0 <= cindex <=
   3325    clen. */
   3326 int lre_exec(uint8_t **capture,
   3327              const uint8_t *bc_buf, const uint8_t *cbuf, int cindex, int clen,
   3328              int cbuf_type, void *opaque)
   3329 {
   3330     REExecContext s_s, *s = &s_s;
   3331     int re_flags, i, ret;
   3332     const uint8_t *cptr;
   3333 
   3334     re_flags = lre_get_flags(bc_buf);
   3335     s->is_unicode = (re_flags & (LRE_FLAG_UNICODE | LRE_FLAG_UNICODE_SETS)) != 0;
   3336     s->capture_count = bc_buf[RE_HEADER_CAPTURE_COUNT];
   3337     s->cbuf = cbuf;
   3338     s->cbuf_end = cbuf + (clen << cbuf_type);
   3339     s->cbuf_type = cbuf_type;
   3340     if (s->cbuf_type == 1 && s->is_unicode)
   3341         s->cbuf_type = 2;
   3342     s->interrupt_counter = INTERRUPT_COUNTER_INIT;
   3343     s->opaque = opaque;
   3344 
   3345     s->stack_buf = s->static_stack_buf;
   3346     s->stack_size = countof(s->static_stack_buf);
   3347 
   3348     for(i = 0; i < s->capture_count * 2; i++)
   3349         capture[i] = NULL;
   3350 
   3351     cptr = cbuf + (cindex << cbuf_type);
   3352     if (0 < cindex && cindex < clen && s->cbuf_type == 2) {
   3353         const uint16_t *p = (const uint16_t *)cptr;
   3354         if (is_lo_surrogate(*p) && is_hi_surrogate(p[-1])) {
   3355             cptr = (const uint8_t *)(p - 1);
   3356         }
   3357     }
   3358 
   3359     ret = lre_exec_backtrack(s, capture, bc_buf + RE_HEADER_LEN, cptr);
   3360 
   3361     if (s->stack_buf != s->static_stack_buf)
   3362         lre_realloc(s->opaque, s->stack_buf, 0);
   3363     return ret;
   3364 }
   3365 
   3366 int lre_get_alloc_count(const uint8_t *bc_buf)
   3367 {
   3368     return bc_buf[RE_HEADER_CAPTURE_COUNT] * 2 +
   3369         bc_buf[RE_HEADER_REGISTER_COUNT];
   3370 }
   3371 
   3372 int lre_get_capture_count(const uint8_t *bc_buf)
   3373 {
   3374     return bc_buf[RE_HEADER_CAPTURE_COUNT];
   3375 }
   3376 
   3377 int lre_get_flags(const uint8_t *bc_buf)
   3378 {
   3379     return get_u16(bc_buf + RE_HEADER_FLAGS);
   3380 }
   3381 
   3382 /* Return NULL if no group names. Otherwise, return a pointer to
   3383    'capture_count - 1' zero terminated UTF-8 strings. */
   3384 const char *lre_get_groupnames(const uint8_t *bc_buf)
   3385 {
   3386     uint32_t re_bytecode_len;
   3387     if ((lre_get_flags(bc_buf) & LRE_FLAG_NAMED_GROUPS) == 0)
   3388         return NULL;
   3389     re_bytecode_len = get_u32(bc_buf + RE_HEADER_BYTECODE_LEN);
   3390     return (const char *)(bc_buf + RE_HEADER_LEN + re_bytecode_len);
   3391 }
   3392 
   3393 #ifdef TEST
   3394 
   3395 BOOL lre_check_stack_overflow(void *opaque, size_t alloca_size)
   3396 {
   3397     return FALSE;
   3398 }
   3399 
   3400 void *lre_realloc(void *opaque, void *ptr, size_t size)
   3401 {
   3402     return realloc(ptr, size);
   3403 }
   3404 
   3405 int main(int argc, char **argv)
   3406 {
   3407     int len, flags, ret, i;
   3408     uint8_t *bc;
   3409     char error_msg[64];
   3410     uint8_t *capture;
   3411     const char *input;
   3412     int input_len, capture_count;
   3413 
   3414     if (argc < 4) {
   3415         printf("usage: %s regexp flags input\n", argv[0]);
   3416         return 1;
   3417     }
   3418     flags = atoi(argv[2]);
   3419     bc = lre_compile(&len, error_msg, sizeof(error_msg), argv[1],
   3420                      strlen(argv[1]), flags, NULL);
   3421     if (!bc) {
   3422         fprintf(stderr, "error: %s\n", error_msg);
   3423         exit(1);
   3424     }
   3425 
   3426     input = argv[3];
   3427     input_len = strlen(input);
   3428 
   3429     capture = malloc(sizeof(capture[0]) * lre_get_alloc_count(bc));
   3430     ret = lre_exec(capture, bc, (uint8_t *)input, 0, input_len, 0, NULL);
   3431     printf("ret=%d\n", ret);
   3432     if (ret == 1) {
   3433         capture_count = lre_get_capture_count(bc);
   3434         for(i = 0; i < 2 * capture_count; i++) {
   3435             uint8_t *ptr;
   3436             ptr = capture[i];
   3437             printf("%d: ", i);
   3438             if (!ptr)
   3439                 printf("<nil>");
   3440             else
   3441                 printf("%u", (int)(ptr - (uint8_t *)input));
   3442             printf("\n");
   3443         }
   3444     }
   3445     free(capture);
   3446     return 0;
   3447 }
   3448 #endif
	quickjs-tart quickjs-based runtime for wallet-core logic
	Log \| Files \| Refs \| README \| LICENSE