git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/bregex.c

   1 /* regexpr.c
   2  *
   3  * Author: Tatu Ylonen <ylo@ngs.fi>
   4  *
   5  * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
   6  *
   7  * Permission to use, copy, modify, distribute, and sell this software
   8  * and its documentation for any purpose is hereby granted without
   9  * fee, provided that the above copyright notice appear in all copies.
  10  * This software is provided "as is" without express or implied
  11  * warranty.
  12  *
  13  * Created: Thu Sep 26 17:14:05 1991 ylo
  14  * Last modified: Mon Nov  4 17:06:48 1991 ylo
  15  * Ported to Think C: 19 Jan 1992 guido@cwi.nl
  16  *
  17  * This code draws many ideas from the regular expression packages by
  18  * Henry Spencer of the University of Toronto and Richard Stallman of
  19  * the Free Software Foundation.
  20  *
  21  * Emacs-specific code and syntax table code is almost directly borrowed
  22  * from GNU regexp.
  23  *
  24  * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April
  25  * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim
  26  * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and
  27  * probably one or two others that I'm forgetting.
  28  *
  29  * $Id$ */
  30
  31 #include "bacula.h"
  32 #include "bregex.h"
  33
  34 #define set_error(x) bufp->errmsg=((char *)(x))
  35 #define got_error bufp->errmsg!=NULL
  36
  37 /* The original code blithely assumed that sizeof(short) == 2.  Not
  38  * always true.  Original instances of "(short)x" were replaced by
  39  * SHORT(x), where SHORT is #defined below.  */
  40
  41 #define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x))
  42
  43 /* The stack implementation is taken from an idea by Andrew Kuchling.
  44  * It's a doubly linked list of arrays. The advantages of this over a
  45  * simple linked list are that the number of mallocs required are
  46  * reduced. It also makes it possible to statically allocate enough
  47  * space so that small patterns don't ever need to call malloc.
  48  *
  49  * The advantages over a single array is that is periodically
  50  * realloced when more space is needed is that we avoid ever copying
  51  * the stack. */
  52
  53 /* item_t is the basic stack element.  Defined as a union of
  54  * structures so that both registers, failure points, and counters can
  55  * be pushed/popped from the stack.  There's nothing built into the
  56  * item to keep track of whether a certain stack item is a register, a
  57  * failure point, or a counter. */
  58
  59 typedef union item_t {
  60    struct {
  61       int num;
  62       int level;
  63       unsigned char *start;
  64       unsigned char *end;
  65    } reg;
  66    struct {
  67       int count;
  68       int level;
  69       int phantom;
  70       unsigned char *code;
  71       unsigned char *text;
  72    } fail;
  73    struct {
  74       int num;
  75       int level;
  76       int count;
  77    } cntr;
  78 } item_t;
  79
  80 #define STACK_PAGE_SIZE 256
  81 #define NUM_REGISTERS 256
  82
  83 /* A 'page' of stack items. */
  84
  85 typedef struct item_page_t {
  86    item_t items[STACK_PAGE_SIZE];
  87    struct item_page_t *prev;
  88    struct item_page_t *next;
  89 } item_page_t;
  90
  91
  92 typedef struct match_state {
  93    /* The number of registers that have been pushed onto the stack
  94     * since the last failure point. */
  95
  96    int count;
  97
  98    /* Used to control when registers need to be pushed onto the
  99     * stack. */
 100
 101    int level;
 102
 103    /* The number of failure points on the stack. */
 104
 105    int point;
 106
 107    /* Storage for the registers.  Each register consists of two
 108     * pointers to characters.  So register N is represented as
 109     * start[N] and end[N].  The pointers must be converted to
 110     * offsets from the beginning of the string before returning the
 111     * registers to the calling program. */
 112
 113    unsigned char *start[NUM_REGISTERS];
 114    unsigned char *end[NUM_REGISTERS];
 115
 116    /* Keeps track of whether a register has changed recently. */
 117
 118    int changed[NUM_REGISTERS];
 119
 120    /* Structure to encapsulate the stack. */
 121    struct {
 122       /* index into the current page.  If index == 0 and you need
 123        * to pop an item, move to the previous page and set index
 124        * = STACK_PAGE_SIZE - 1.  Otherwise decrement index to
 125        * push a page. If index == STACK_PAGE_SIZE and you need
 126        * to push a page move to the next page and set index =
 127        * 0. If there is no new next page, allocate a new page
 128        * and link it in. Otherwise, increment index to push a
 129        * page. */
 130
 131       int index;
 132       item_page_t *current;        /* Pointer to the current page. */
 133       item_page_t first;           /* First page is statically allocated. */
 134    } stack;
 135 } match_state;
 136
 137 /* Initialize a state object */
 138
 139 /* #define NEW_STATE(state) \ */
 140 /* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */
 141 /* state.stack.current = &state.stack.first; \ */
 142 /* state.stack.first.prev = NULL; \ */
 143 /* state.stack.first.next = NULL; \ */
 144 /* state.stack.index = 0; \ */
 145 /* state.level = 1 */
 146
 147 #define NEW_STATE(state, nregs) \
 148 { \
 149    int i; \
 150    for (i = 0; i < nregs; i++) \
 151    { \
 152       state.start[i] = NULL; \
 153       state.end[i] = NULL; \
 154       state.changed[i] = 0; \
 155    } \
 156    state.stack.current = &state.stack.first; \
 157    state.stack.first.prev = NULL; \
 158    state.stack.first.next = NULL; \
 159    state.stack.index = 0; \
 160    state.level = 1; \
 161    state.count = 0; \
 162    state.level = 0; \
 163    state.point = 0; \
 164 }
 165
 166 /* Free any memory that might have been malloc'd */
 167
 168 #define FREE_STATE(state) \
 169 while(state.stack.first.next != NULL) \
 170 { \
 171    state.stack.current = state.stack.first.next; \
 172    state.stack.first.next = state.stack.current->next; \
 173    free(state.stack.current); \
 174 }
 175
 176 /* Discard the top 'count' stack items. */
 177
 178 #define STACK_DISCARD(stack, count, on_error) \
 179 stack.index -= count; \
 180 while (stack.index < 0) \
 181 { \
 182    if (stack.current->prev == NULL) \
 183            on_error; \
 184    stack.current = stack.current->prev; \
 185    stack.index += STACK_PAGE_SIZE; \
 186 }
 187
 188 /* Store a pointer to the previous item on the stack. Used to pop an
 189  * item off of the stack. */
 190
 191 #define STACK_PREV(stack, top, on_error) \
 192 if (stack.index == 0) \
 193 { \
 194         if (stack.current->prev == NULL) \
 195                 on_error; \
 196         stack.current = stack.current->prev; \
 197         stack.index = STACK_PAGE_SIZE - 1; \
 198 } \
 199 else \
 200 { \
 201         stack.index--; \
 202 } \
 203 top = &(stack.current->items[stack.index])
 204
 205 /* Store a pointer to the next item on the stack. Used to push an item
 206  * on to the stack. */
 207
 208 #define STACK_NEXT(stack, top, on_error) \
 209 if (stack.index == STACK_PAGE_SIZE) \
 210 { \
 211         if (stack.current->next == NULL) \
 212         { \
 213                 stack.current->next = (item_page_t *)malloc(sizeof(item_page_t)); \
 214                 if (stack.current->next == NULL) \
 215                         on_error; \
 216                 stack.current->next->prev = stack.current; \
 217                 stack.current->next->next = NULL; \
 218         } \
 219         stack.current = stack.current->next; \
 220         stack.index = 0; \
 221 } \
 222 top = &(stack.current->items[stack.index++])
 223
 224 /* Store a pointer to the item that is 'count' items back in the
 225  * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to
 226  * STACK_TOP(stack, top, on_error).  */
 227
 228 #define STACK_BACK(stack, top, count, on_error) \
 229 { \
 230         int index; \
 231         item_page_t *current; \
 232         current = stack.current; \
 233         index = stack.index - (count); \
 234         while (index < 0) \
 235         { \
 236                 if (current->prev == NULL) \
 237                         on_error; \
 238                 current = current->prev; \
 239                 index += STACK_PAGE_SIZE; \
 240         } \
 241         top = &(current->items[index]); \
 242 }
 243
 244 /* Store a pointer to the top item on the stack. Execute the
 245  * 'on_error' code if there are no items on the stack. */
 246
 247 #define STACK_TOP(stack, top, on_error) \
 248 if (stack.index == 0) \
 249 { \
 250         if (stack.current->prev == NULL) \
 251                 on_error; \
 252         top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
 253 } \
 254 else \
 255 { \
 256         top = &(stack.current->items[stack.index - 1]); \
 257 }
 258
 259 /* Test to see if the stack is empty */
 260
 261 #define STACK_EMPTY(stack) ((stack.index == 0) && \
 262                             (stack.current->prev == NULL))
 263
 264 /* Return the start of register 'reg' */
 265
 266 #define GET_REG_START(state, reg) (state.start[reg])
 267
 268 /* Return the end of register 'reg' */
 269
 270 #define GET_REG_END(state, reg) (state.end[reg])
 271
 272 /* Set the start of register 'reg'. If the state of the register needs
 273  * saving, push it on the stack. */
 274
 275 #define SET_REG_START(state, reg, text, on_error) \
 276 if(state.changed[reg] < state.level) \
 277 { \
 278         item_t *item; \
 279         STACK_NEXT(state.stack, item, on_error); \
 280         item->reg.num = reg; \
 281         item->reg.start = state.start[reg]; \
 282         item->reg.end = state.end[reg]; \
 283         item->reg.level = state.changed[reg]; \
 284         state.changed[reg] = state.level; \
 285         state.count++; \
 286 } \
 287 state.start[reg] = text
 288
 289 /* Set the end of register 'reg'. If the state of the register needs
 290  * saving, push it on the stack. */
 291
 292 #define SET_REG_END(state, reg, text, on_error) \
 293 if(state.changed[reg] < state.level) \
 294 { \
 295         item_t *item; \
 296         STACK_NEXT(state.stack, item, on_error); \
 297         item->reg.num = reg; \
 298         item->reg.start = state.start[reg]; \
 299         item->reg.end = state.end[reg]; \
 300         item->reg.level = state.changed[reg]; \
 301         state.changed[reg] = state.level; \
 302         state.count++; \
 303 } \
 304 state.end[reg] = text
 305
 306 #define PUSH_FAILURE(state, xcode, xtext, on_error) \
 307 { \
 308         item_t *item; \
 309         STACK_NEXT(state.stack, item, on_error); \
 310         item->fail.code = xcode; \
 311         item->fail.text = xtext; \
 312         item->fail.count = state.count; \
 313         item->fail.level = state.level; \
 314         item->fail.phantom = 0; \
 315         state.count = 0; \
 316         state.level++; \
 317         state.point++; \
 318 }
 319
 320 /* Update the last failure point with a new position in the text. */
 321
 322 #define UPDATE_FAILURE(state, xtext, on_error) \
 323 { \
 324    item_t *item; \
 325    STACK_BACK(state.stack, item, state.count + 1, on_error); \
 326    if (!item->fail.phantom) \
 327    { \
 328            item_t *item2; \
 329            STACK_NEXT(state.stack, item2, on_error); \
 330            item2->fail.code = item->fail.code; \
 331            item2->fail.text = xtext; \
 332            item2->fail.count = state.count; \
 333            item2->fail.level = state.level; \
 334            item2->fail.phantom = 1; \
 335            state.count = 0; \
 336            state.level++; \
 337            state.point++; \
 338    } \
 339    else \
 340    { \
 341            STACK_DISCARD(state.stack, state.count, on_error); \
 342            STACK_TOP(state.stack, item, on_error); \
 343            item->fail.text = xtext; \
 344            state.count = 0; \
 345            state.level++; \
 346    } \
 347 }
 348
 349 #define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \
 350 { \
 351    item_t *item; \
 352    do \
 353    { \
 354            while(state.count > 0) \
 355            { \
 356                    STACK_PREV(state.stack, item, on_error); \
 357                    state.start[item->reg.num] = item->reg.start; \
 358                    state.end[item->reg.num] = item->reg.end; \
 359                    state.changed[item->reg.num] = item->reg.level; \
 360                    state.count--; \
 361            } \
 362            STACK_PREV(state.stack, item, on_empty); \
 363            xcode = item->fail.code; \
 364            xtext = item->fail.text; \
 365            state.count = item->fail.count; \
 366            state.level = item->fail.level; \
 367            state.point--; \
 368    } \
 369    while (item->fail.text == NULL); \
 370 }
 371
 372 enum regexp_compiled_ops {         /* opcodes for compiled regexp */
 373    Cend,                           /* end of pattern reached */
 374    Cbol,                           /* beginning of line */
 375    Ceol,                           /* end of line */
 376    Cset,                           /* character set.  Followed by 32 bytes of set. */
 377    Cexact,                         /* followed by a byte to match */
 378    Canychar,                       /* matches any character except newline */
 379    Cstart_memory,                  /* set register start addr (followed by reg number) */
 380    Cend_memory,                    /* set register end addr (followed by reg number) */
 381    Cmatch_memory,                  /* match a duplicate of reg contents (regnum follows) */
 382    Cjump,                          /* followed by two bytes (lsb,msb) of displacement. */
 383    Cstar_jump,                     /* will change to jump/update_failure_jump at runtime */
 384    Cfailure_jump,                  /* jump to addr on failure */
 385    Cupdate_failure_jump,           /* update topmost failure point and jump */
 386    Cdummy_failure_jump,            /* push a dummy failure point and jump */
 387    Cbegbuf,                        /* match at beginning of buffer */
 388    Cendbuf,                        /* match at end of buffer */
 389    Cwordbeg,                       /* match at beginning of word */
 390    Cwordend,                       /* match at end of word */
 391    Cwordbound,                     /* match if at word boundary */
 392    Cnotwordbound,                  /* match if not at word boundary */
 393    Csyntaxspec,                    /* matches syntax code (1 byte follows) */
 394    Cnotsyntaxspec,                 /* matches if syntax code does not match (1 byte follows) */
 395    Crepeat1
 396 };
 397
 398 enum regexp_syntax_op {            /* syntax codes for plain and quoted characters */
 399    Rend,                           /* special code for end of regexp */
 400    Rnormal,                        /* normal character */
 401    Ranychar,                       /* any character except newline */
 402    Rquote,                         /* the quote character */
 403    Rbol,                           /* match beginning of line */
 404    Reol,                           /* match end of line */
 405    Roptional,                      /* match preceding expression optionally */
 406    Rstar,                          /* match preceding expr zero or more times */
 407    Rplus,                          /* match preceding expr one or more times */
 408    Ror,                            /* match either of alternatives */
 409    Ropenpar,                       /* opening parenthesis */
 410    Rclosepar,                      /* closing parenthesis */
 411    Rmemory,                        /* match memory register */
 412    Rextended_memory,               /* \vnn to match registers 10-99 */
 413    Ropenset,                       /* open set.  Internal syntax hard-coded below. */
 414    /* the following are gnu extensions to "normal" regexp syntax */
 415    Rbegbuf,                        /* beginning of buffer */
 416    Rendbuf,                        /* end of buffer */
 417    Rwordchar,                      /* word character */
 418    Rnotwordchar,                   /* not word character */
 419    Rwordbeg,                       /* beginning of word */
 420    Rwordend,                       /* end of word */
 421    Rwordbound,                     /* word bound */
 422    Rnotwordbound,                  /* not word bound */
 423    Rnum_ops
 424 };
 425
 426 static int re_compile_initialized = 0;
 427 static int regexp_syntax = RE_SYNTAX_EGREP;
 428 int re_syntax = RE_SYNTAX_EGREP;   /* Exported copy of regexp_syntax */
 429 static unsigned char plain_ops[256];
 430 static unsigned char quoted_ops[256];
 431 static unsigned char precedences[Rnum_ops];
 432 static int regexp_context_indep_ops;
 433 static int regexp_ansi_sequences;
 434
 435 #define NUM_LEVELS  5              /* number of precedence levels in use */
 436 #define MAX_NESTING 100            /* max nesting level of operators */
 437
 438 #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]
 439
 440 unsigned char re_syntax_table[256];
 441
 442 void re_compile_initialize(void)
 443 {
 444    int a;
 445
 446    static int syntax_table_inited = 0;
 447
 448    if (!syntax_table_inited) {
 449       syntax_table_inited = 1;
 450       memset(re_syntax_table, 0, 256);
 451       for (a = 'a'; a <= 'z'; a++)
 452          re_syntax_table[a] = Sword;
 453       for (a = 'A'; a <= 'Z'; a++)
 454          re_syntax_table[a] = Sword;
 455       for (a = '0'; a <= '9'; a++)
 456          re_syntax_table[a] = Sword | Sdigit | Shexdigit;
 457       for (a = '0'; a <= '7'; a++)
 458          re_syntax_table[a] |= Soctaldigit;
 459       for (a = 'A'; a <= 'F'; a++)
 460          re_syntax_table[a] |= Shexdigit;
 461       for (a = 'a'; a <= 'f'; a++)
 462          re_syntax_table[a] |= Shexdigit;
 463       re_syntax_table[(int)'_'] = Sword;
 464       for (a = 9; a <= 13; a++)
 465          re_syntax_table[a] = Swhitespace;
 466       re_syntax_table[(int)' '] = Swhitespace;
 467    }
 468    re_compile_initialized = 1;
 469    for (a = 0; a < 256; a++) {
 470       plain_ops[a] = Rnormal;
 471       quoted_ops[a] = Rnormal;
 472    }
 473    for (a = '0'; a <= '9'; a++)
 474       quoted_ops[a] = Rmemory;
 475    plain_ops[(int)'\134'] = Rquote;
 476    if (regexp_syntax & RE_NO_BK_PARENS) {
 477       plain_ops[(int)'('] = Ropenpar;
 478       plain_ops[(int)')'] = Rclosepar;
 479    } else {
 480       quoted_ops[(int)'('] = Ropenpar;
 481       quoted_ops[(int)')'] = Rclosepar;
 482    }
 483    if (regexp_syntax & RE_NO_BK_VBAR) {
 484       plain_ops[(int)'\174'] = Ror;
 485    } else {
 486       quoted_ops[(int)'\174'] = Ror;
 487       plain_ops[(int)'*'] = Rstar;
 488       if (regexp_syntax & RE_BK_PLUS_QM) {
 489          quoted_ops[(int)'+'] = Rplus;
 490          quoted_ops[(int)'?'] = Roptional;
 491       } else {
 492          plain_ops[(int)'+'] = Rplus;
 493          plain_ops[(int)'?'] = Roptional;
 494       }
 495       if (regexp_syntax & RE_NEWLINE_OR) {
 496          plain_ops[(int)'\n'] = Ror;
 497       }
 498       plain_ops[(int)'\133'] = Ropenset;
 499       plain_ops[(int)'\136'] = Rbol;
 500       plain_ops[(int)'$'] = Reol;
 501       plain_ops[(int)'.'] = Ranychar;
 502       if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS)) {
 503          quoted_ops[(int)'w'] = Rwordchar;
 504          quoted_ops[(int)'W'] = Rnotwordchar;
 505          quoted_ops[(int)'<'] = Rwordbeg;
 506          quoted_ops[(int)'>'] = Rwordend;
 507          quoted_ops[(int)'b'] = Rwordbound;
 508          quoted_ops[(int)'B'] = Rnotwordbound;
 509          quoted_ops[(int)'`'] = Rbegbuf;
 510          quoted_ops[(int)'\''] = Rendbuf;
 511       }
 512       if (regexp_syntax & RE_ANSI_HEX) {
 513          quoted_ops[(int)'v'] = Rextended_memory;
 514       }
 515       for (a = 0; a < Rnum_ops; a++) {
 516          precedences[a] = 4;
 517       }
 518       if (regexp_syntax & RE_TIGHT_VBAR) {
 519          precedences[Ror] = 3;
 520          precedences[Rbol] = 2;
 521          precedences[Reol] = 2;
 522       } else {
 523          precedences[Ror] = 2;
 524          precedences[Rbol] = 3;
 525          precedences[Reol] = 3;
 526       }
 527       precedences[Rclosepar] = 1;
 528       precedences[Rend] = 0;
 529       regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
 530       regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
 531    }
 532 }
 533
 534 int re_set_syntax(int syntax) {
 535    int ret;
 536
 537    ret = regexp_syntax;
 538    regexp_syntax = syntax;
 539    re_syntax = syntax;          /* Exported copy */
 540    re_compile_initialize();
 541    return ret;
 542 }
 543
 544 static int hex_char_to_decimal(int ch) {
 545    if (ch >= '0' && ch <= '9')
 546       return ch - '0';
 547    if (ch >= 'a' && ch <= 'f')
 548       return ch - 'a' + 10;
 549    if (ch >= 'A' && ch <= 'F')
 550       return ch - 'A' + 10;
 551    return 16;
 552 }
 553
 554 static void re_compile_fastmap_aux(regex_t * bufp, unsigned char *code, int pos,
 555                                    unsigned char *visited,
 556                                    unsigned char *can_be_null,
 557                                    unsigned char *fastmap)
 558 {
 559    int a;
 560    int b;
 561    int syntaxcode;
 562
 563    if (visited[pos])
 564       return;                   /* we have already been here */
 565    visited[pos] = 1;
 566    for (;;) {
 567       switch (code[pos++]) {
 568       case Cend:
 569          *can_be_null = 1;
 570          return;
 571       case Cbol:
 572       case Cbegbuf:
 573       case Cendbuf:
 574       case Cwordbeg:
 575       case Cwordend:
 576       case Cwordbound:
 577       case Cnotwordbound:
 578          for (a = 0; a < 256; a++)
 579             fastmap[a] = 1;
 580          break;
 581       case Csyntaxspec:
 582          syntaxcode = code[pos++];
 583          for (a = 0; a < 256; a++)
 584             if (SYNTAX(a) & syntaxcode)
 585                fastmap[a] = 1;
 586          return;
 587       case Cnotsyntaxspec:
 588          syntaxcode = code[pos++];
 589          for (a = 0; a < 256; a++)
 590             if (!(SYNTAX(a) & syntaxcode))
 591                fastmap[a] = 1;
 592          return;
 593       case Ceol:
 594          fastmap[(int)'\n'] = 1;
 595          if (*can_be_null == 0)
 596             *can_be_null = 2;      /* can match null, but only at end of buffer */
 597          return;
 598       case Cset:
 599          for (a = 0; a < 256 / 8; a++)
 600             if (code[pos + a] != 0)
 601                for (b = 0; b < 8; b++)
 602                   if (code[pos + a] & (1 << b))
 603                      fastmap[(a << 3) + b] = 1;
 604          pos += 256 / 8;
 605          return;
 606       case Cexact:
 607          fastmap[(unsigned char)code[pos]] = 1;
 608          return;
 609       case Canychar:
 610          for (a = 0; a < 256; a++)
 611             if (a != '\n')
 612                fastmap[a] = 1;
 613          return;
 614       case Cstart_memory:
 615       case Cend_memory:
 616          pos++;
 617          break;
 618       case Cmatch_memory:
 619          for (a = 0; a < 256; a++)
 620             fastmap[a] = 1;
 621          *can_be_null = 1;
 622          return;
 623       case Cjump:
 624       case Cdummy_failure_jump:
 625       case Cupdate_failure_jump:
 626       case Cstar_jump:
 627          a = (unsigned char)code[pos++];
 628          a |= (unsigned char)code[pos++] << 8;
 629          pos += (int)SHORT(a);
 630          if (visited[pos]) {
 631             /* argh... the regexp contains empty loops.  This is not
 632                good, as this may cause a failure stack overflow when
 633                matching.  Oh well. */
 634             /* this path leads nowhere; pursue other paths. */
 635             return;
 636          }
 637          visited[pos] = 1;
 638          break;
 639       case Cfailure_jump:
 640          a = (unsigned char)code[pos++];
 641          a |= (unsigned char)code[pos++] << 8;
 642          a = pos + (int)SHORT(a);
 643          re_compile_fastmap_aux(bufp, code, a, visited, can_be_null, fastmap);
 644          break;
 645       case Crepeat1:
 646          pos += 2;
 647          break;
 648       default:
 649          set_error("Unknown regex opcode: memory corrupted?");
 650          return;
 651       }
 652    }
 653 }
 654
 655 static int re_do_compile_fastmap(regex_t * bufp, unsigned char *buffer, int used,
 656                                  int pos, unsigned char *can_be_null,
 657                                  unsigned char *fastmap)
 658 {
 659    unsigned char small_visited[512], *visited;
 660
 661    if (used <= (int)sizeof(small_visited))
 662       visited = small_visited;
 663    else {
 664       visited = (unsigned char *)malloc(used);
 665       if (!visited)
 666          return 0;
 667    }
 668    *can_be_null = 0;
 669    memset(fastmap, 0, 256);
 670    memset(visited, 0, used);
 671    re_compile_fastmap_aux(bufp, buffer, pos, visited, can_be_null, fastmap);
 672    if (visited != small_visited)
 673       free(visited);
 674    return 1;
 675 }
 676
 677 void re_compile_fastmap(regex_t * bufp)
 678 {
 679    if (!bufp->fastmap || bufp->fastmap_accurate)
 680       return;
 681 // assert(bufp->used > 0);
 682    if (!re_do_compile_fastmap(bufp, bufp->buffer,
 683                               bufp->used, 0, &bufp->can_be_null, bufp->fastmap))
 684       return;
 685    if (got_error)
 686       return;
 687    if (bufp->buffer[0] == Cbol)
 688       bufp->anchor = 1;            /* begline */
 689    else if (bufp->buffer[0] == Cbegbuf)
 690       bufp->anchor = 2;            /* begbuf */
 691    else
 692       bufp->anchor = 0;            /* none */
 693    bufp->fastmap_accurate = 1;
 694 }
 695
 696 /*
 697  * star is coded as:
 698  * 1: failure_jump 2
 699  *    ... code for operand of star
 700  *    star_jump 1
 701  * 2: ... code after star
 702  *
 703  * We change the star_jump to update_failure_jump if we can determine
 704  * that it is safe to do so; otherwise we change it to an ordinary
 705  * jump.
 706  *
 707  * plus is coded as
 708  *
 709  *    jump 2
 710  * 1: failure_jump 3
 711  * 2: ... code for operand of plus
 712  *    star_jump 1
 713  * 3: ... code after plus
 714  *
 715  * For star_jump considerations this is processed identically to star.
 716  *
 717  */
 718
 719 static int re_optimize_star_jump(regex_t * bufp, unsigned char *code)
 720 {
 721    unsigned char map[256];
 722    unsigned char can_be_null;
 723    unsigned char *p1;
 724    unsigned char *p2;
 725    unsigned char ch;
 726    int a;
 727    int b;
 728    int num_instructions = 0;
 729
 730    a = (unsigned char)*code++;
 731    a |= (unsigned char)*code++ << 8;
 732    a = (int)SHORT(a);
 733
 734    p1 = code + a + 3;              /* skip the failure_jump */
 735    /* Check that the jump is within the pattern */
 736    if (p1 < bufp->buffer || bufp->buffer + bufp->used < p1) {
 737       set_error("Regex VM jump out of bounds (failure_jump opt)");
 738       return 0;
 739    }
 740 // assert(p1[-3] == Cfailure_jump);
 741    p2 = code;
 742    /* p1 points inside loop, p2 points to after loop */
 743    if (!re_do_compile_fastmap(bufp, bufp->buffer, bufp->used,
 744                               (int)(p2 - bufp->buffer), &can_be_null, map))
 745       goto make_normal_jump;
 746
 747    /* If we might introduce a new update point inside the
 748     * loop, we can't optimize because then update_jump would
 749     * update a wrong failure point.  Thus we have to be
 750     * quite careful here.
 751     */
 752
 753    /* loop until we find something that consumes a character */
 754    for (;;) {
 755       num_instructions++;
 756       switch (*p1++) {
 757       case Cbol:
 758       case Ceol:
 759       case Cbegbuf:
 760       case Cendbuf:
 761       case Cwordbeg:
 762       case Cwordend:
 763       case Cwordbound:
 764       case Cnotwordbound:
 765          continue;
 766       case Cstart_memory:
 767       case Cend_memory:
 768          p1++;
 769          continue;
 770       case Cexact:
 771          ch = (unsigned char)*p1++;
 772          if (map[(int)ch])
 773             goto make_normal_jump;
 774          break;
 775       case Canychar:
 776          for (b = 0; b < 256; b++)
 777             if (b != '\n' && map[b])
 778                goto make_normal_jump;
 779          break;
 780       case Cset:
 781          for (b = 0; b < 256; b++)
 782             if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
 783                goto make_normal_jump;
 784          p1 += 256 / 8;
 785          break;
 786       default:
 787          goto make_normal_jump;
 788       }
 789       break;
 790    }
 791    /* now we know that we can't backtrack. */
 792    while (p1 != p2 - 3) {
 793       num_instructions++;
 794       switch (*p1++) {
 795       case Cend:
 796          return 0;
 797       case Cbol:
 798       case Ceol:
 799       case Canychar:
 800       case Cbegbuf:
 801       case Cendbuf:
 802       case Cwordbeg:
 803       case Cwordend:
 804       case Cwordbound:
 805       case Cnotwordbound:
 806          break;
 807       case Cset:
 808          p1 += 256 / 8;
 809          break;
 810       case Cexact:
 811       case Cstart_memory:
 812       case Cend_memory:
 813       case Cmatch_memory:
 814       case Csyntaxspec:
 815       case Cnotsyntaxspec:
 816          p1++;
 817          break;
 818       case Cjump:
 819       case Cstar_jump:
 820       case Cfailure_jump:
 821       case Cupdate_failure_jump:
 822       case Cdummy_failure_jump:
 823          goto make_normal_jump;
 824       default:
 825          return 0;
 826       }
 827    }
 828
 829    /* make_update_jump: */
 830    code -= 3;
 831    a += 3;                         /* jump to after the Cfailure_jump */
 832    code[0] = Cupdate_failure_jump;
 833    code[1] = a & 0xff;
 834    code[2] = a >> 8;
 835    if (num_instructions > 1)
 836       return 1;
 837 // assert(num_instructions == 1);
 838    /* if the only instruction matches a single character, we can do
 839     * better */
 840    p1 = code + 3 + a;              /* start of sole instruction */
 841    if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
 842        *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
 843       code[0] = Crepeat1;
 844    return 1;
 845
 846  make_normal_jump:
 847    code -= 3;
 848    *code = Cjump;
 849    return 1;
 850 }
 851
 852 static int re_optimize(regex_t * bufp)
 853 {
 854    unsigned char *code;
 855
 856    code = bufp->buffer;
 857
 858    while (1) {
 859       switch (*code++) {
 860       case Cend:
 861          return 1;
 862       case Canychar:
 863       case Cbol:
 864       case Ceol:
 865       case Cbegbuf:
 866       case Cendbuf:
 867       case Cwordbeg:
 868       case Cwordend:
 869       case Cwordbound:
 870       case Cnotwordbound:
 871          break;
 872       case Cset:
 873          code += 256 / 8;
 874          break;
 875       case Cexact:
 876       case Cstart_memory:
 877       case Cend_memory:
 878       case Cmatch_memory:
 879       case Csyntaxspec:
 880       case Cnotsyntaxspec:
 881          code++;
 882          break;
 883       case Cstar_jump:
 884          if (!re_optimize_star_jump(bufp, code)) {
 885             return 0;
 886          }
 887          /* fall through */
 888       case Cupdate_failure_jump:
 889       case Cjump:
 890       case Cdummy_failure_jump:
 891       case Cfailure_jump:
 892       case Crepeat1:
 893          code += 2;
 894          break;
 895       default:
 896          return 0;
 897       }
 898    }
 899 }
 900
 901 #define NEXTCHAR(var) \
 902 { \
 903         if (pos >= size) \
 904                 goto ends_prematurely; \
 905         (var) = regex[pos]; \
 906         pos++; \
 907 }
 908
 909 #define ALLOC(amount) \
 910 { \
 911           if (pattern_offset+(amount) > alloc) \
 912           { \
 913                   alloc += 256 + (amount); \
 914                   pattern = (unsigned char *)realloc(pattern, alloc); \
 915                   if (!pattern) \
 916                           goto out_of_memory; \
 917           } \
 918 }
 919
 920 #define STORE(ch) pattern[pattern_offset++] = (ch)
 921
 922 #define CURRENT_LEVEL_START (starts[starts_base + current_level])
 923
 924 #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
 925
 926 #define PUSH_LEVEL_STARTS \
 927 if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
 928         starts_base += NUM_LEVELS; \
 929 else \
 930         goto too_complex \
 931
 932 #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
 933
 934 #define PUT_ADDR(offset,addr) \
 935 { \
 936         int disp = (addr) - (offset) - 2; \
 937         pattern[(offset)] = disp & 0xff; \
 938         pattern[(offset)+1] = (disp>>8) & 0xff; \
 939 }
 940
 941 #define INSERT_JUMP(pos,type,addr) \
 942 { \
 943         int a, p = (pos), t = (type), ad = (addr); \
 944         for (a = pattern_offset - 1; a >= p; a--) \
 945                 pattern[a + 3] = pattern[a]; \
 946         pattern[p] = t; \
 947         PUT_ADDR(p+1,ad); \
 948         pattern_offset += 3; \
 949 }
 950
 951 #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
 952
 953 #define SET_FIELDS \
 954 { \
 955         bufp->allocated = alloc; \
 956         bufp->buffer = pattern; \
 957         bufp->used = pattern_offset; \
 958 }
 959
 960 #define GETHEX(var) \
 961 { \
 962         unsigned char gethex_ch, gethex_value; \
 963         NEXTCHAR(gethex_ch); \
 964         gethex_value = hex_char_to_decimal(gethex_ch); \
 965         if (gethex_value == 16) \
 966                 goto hex_error; \
 967         NEXTCHAR(gethex_ch); \
 968         gethex_ch = hex_char_to_decimal(gethex_ch); \
 969         if (gethex_ch == 16) \
 970                 goto hex_error; \
 971         (var) = gethex_value * 16 + gethex_ch; \
 972 }
 973
 974 #define ANSI_TRANSLATE(ch) \
 975 { \
 976    switch (ch) \
 977    { \
 978    case 'a': \
 979    case 'A': \
 980    { \
 981            ch = 7; /* audible bell */ \
 982            break; \
 983    } \
 984    case 'b': \
 985    case 'B': \
 986    { \
 987            ch = 8; /* backspace */ \
 988            break; \
 989    } \
 990    case 'f': \
 991    case 'F': \
 992    { \
 993            ch = 12; /* form feed */ \
 994            break; \
 995    } \
 996    case 'n': \
 997    case 'N': \
 998    { \
 999            ch = 10; /* line feed */ \
1000            break; \
1001    } \
1002    case 'r': \
1003    case 'R': \
1004    { \
1005            ch = 13; /* carriage return */ \
1006            break; \
1007    } \
1008    case 't': \
1009    case 'T': \
1010    { \
1011          ch = 9; /* tab */ \
1012          break; \
1013    } \
1014    case 'v': \
1015    case 'V': \
1016    { \
1017            ch = 11; /* vertical tab */ \
1018            break; \
1019    } \
1020    case 'x': /* hex code */ \
1021    case 'X': \
1022    { \
1023            GETHEX(ch); \
1024            break; \
1025    } \
1026    default: \
1027    { \
1028            /* other characters passed through */ \
1029            if (translate) \
1030                    ch = translate[(unsigned char)ch]; \
1031            break; \
1032    } \
1033    } \
1034 }
1035
1036 const char *re_compile_pattern(regex_t * bufp, unsigned char *regex)
1037 {
1038    int a;
1039    int pos;
1040    int op;
1041    int current_level;
1042    int level;
1043    int opcode;
1044    int pattern_offset = 0, alloc;
1045    int starts[NUM_LEVELS * MAX_NESTING];
1046    int starts_base;
1047    int future_jumps[MAX_NESTING];
1048    int num_jumps;
1049    unsigned char ch = '\0';
1050    unsigned char *pattern;
1051    unsigned char *translate;
1052    int next_register;
1053    int paren_depth;
1054    int num_open_registers;
1055    int open_registers[RE_NREGS];
1056    int beginning_context;
1057    int size = strlen((char *)regex);
1058
1059    if (!re_compile_initialized)
1060       re_compile_initialize();
1061    bufp->used = 0;
1062    bufp->fastmap_accurate = 0;
1063    bufp->uses_registers = 1;
1064    bufp->num_registers = 1;
1065    translate = bufp->translate;
1066    pattern = bufp->buffer;
1067    alloc = bufp->allocated;
1068    if (alloc == 0 || pattern == NULL) {
1069       alloc = 256;
1070       pattern = (unsigned char *)malloc(alloc);
1071       if (!pattern)
1072          goto out_of_memory;
1073    }
1074    pattern_offset = 0;
1075    starts_base = 0;
1076    num_jumps = 0;
1077    current_level = 0;
1078    SET_LEVEL_START;
1079    num_open_registers = 0;
1080    next_register = 1;
1081    paren_depth = 0;
1082    beginning_context = 1;
1083    op = -1;
1084    /* we use Rend dummy to ensure that pending jumps are updated
1085       (due to low priority of Rend) before exiting the loop. */
1086    pos = 0;
1087    while (op != Rend) {
1088       if (pos >= size)
1089          op = Rend;
1090       else {
1091          NEXTCHAR(ch);
1092          if (translate)
1093             ch = translate[(unsigned char)ch];
1094          op = plain_ops[(unsigned char)ch];
1095          if (op == Rquote) {
1096             NEXTCHAR(ch);
1097             op = quoted_ops[(unsigned char)ch];
1098             if (op == Rnormal && regexp_ansi_sequences)
1099                ANSI_TRANSLATE(ch);
1100          }
1101       }
1102       level = precedences[op];
1103       /* printf("ch='%c' op=%d level=%d current_level=%d
1104          curlevstart=%d\n", ch, op, level, current_level,
1105          CURRENT_LEVEL_START); */
1106       if (level > current_level) {
1107          for (current_level++; current_level < level; current_level++)
1108             SET_LEVEL_START;
1109          SET_LEVEL_START;
1110       } else if (level < current_level) {
1111          current_level = level;
1112          for (; num_jumps > 0 &&
1113               future_jumps[num_jumps - 1] >= CURRENT_LEVEL_START; num_jumps--)
1114             PUT_ADDR(future_jumps[num_jumps - 1], pattern_offset);
1115       }
1116       switch (op) {
1117       case Rend:
1118          break;
1119       case Rnormal:
1120        normal_char:
1121          opcode = Cexact;
1122        store_opcode_and_arg:       /* opcode & ch must be set */
1123          SET_LEVEL_START;
1124          ALLOC(2);
1125          STORE(opcode);
1126          STORE(ch);
1127          break;
1128       case Ranychar:
1129          opcode = Canychar;
1130        store_opcode:
1131          SET_LEVEL_START;
1132          ALLOC(1);
1133          STORE(opcode);
1134          break;
1135       case Rquote:
1136          set_error("Rquote");
1137        /*NOTREACHED*/ case Rbol:
1138          if (!beginning_context) {
1139             if (regexp_context_indep_ops)
1140                goto op_error;
1141             else
1142                goto normal_char;
1143          }
1144          opcode = Cbol;
1145          goto store_opcode;
1146       case Reol:
1147          if (!((pos >= size) ||
1148                ((regexp_syntax & RE_NO_BK_VBAR) ?
1149                 (regex[pos] == '\174') :
1150                 (pos + 1 < size && regex[pos] == '\134' &&
1151                  regex[pos + 1] == '\174')) ||
1152                ((regexp_syntax & RE_NO_BK_PARENS) ?
1153                 (regex[pos] == ')') :
1154                 (pos + 1 < size && regex[pos] == '\134' &&
1155                  regex[pos + 1] == ')')))) {
1156             if (regexp_context_indep_ops)
1157                goto op_error;
1158             else
1159                goto normal_char;
1160          }
1161          opcode = Ceol;
1162          goto store_opcode;
1163          /* NOTREACHED */
1164          break;
1165       case Roptional:
1166          if (beginning_context) {
1167             if (regexp_context_indep_ops)
1168                goto op_error;
1169             else
1170                goto normal_char;
1171          }
1172          if (CURRENT_LEVEL_START == pattern_offset)
1173             break;                 /* ignore empty patterns for ? */
1174          ALLOC(3);
1175          INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, pattern_offset + 3);
1176          break;
1177       case Rstar:
1178       case Rplus:
1179          if (beginning_context) {
1180             if (regexp_context_indep_ops)
1181                goto op_error;
1182             else
1183                goto normal_char;
1184          }
1185          if (CURRENT_LEVEL_START == pattern_offset)
1186             break;                 /* ignore empty patterns for + and * */
1187          ALLOC(9);
1188          INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, pattern_offset + 6);
1189          INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
1190          if (op == Rplus)          /* jump over initial failure_jump */
1191             INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
1192                         CURRENT_LEVEL_START + 6);
1193          break;
1194       case Ror:
1195          ALLOC(6);
1196          INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, pattern_offset + 6);
1197          if (num_jumps >= MAX_NESTING)
1198             goto too_complex;
1199          STORE(Cjump);
1200          future_jumps[num_jumps++] = pattern_offset;
1201          STORE(0);
1202          STORE(0);
1203          SET_LEVEL_START;
1204          break;
1205       case Ropenpar:
1206          {
1207             SET_LEVEL_START;
1208             if (next_register < RE_NREGS) {
1209                bufp->uses_registers = 1;
1210                ALLOC(2);
1211                STORE(Cstart_memory);
1212                STORE(next_register);
1213                open_registers[num_open_registers++] = next_register;
1214                bufp->num_registers++;
1215                next_register++;
1216             }
1217             paren_depth++;
1218             PUSH_LEVEL_STARTS;
1219             current_level = 0;
1220             SET_LEVEL_START;
1221             break;
1222          }
1223       case Rclosepar:
1224          if (paren_depth <= 0)
1225             goto parenthesis_error;
1226          POP_LEVEL_STARTS;
1227          current_level = precedences[Ropenpar];
1228          paren_depth--;
1229          if (paren_depth < num_open_registers) {
1230             bufp->uses_registers = 1;
1231             ALLOC(2);
1232             STORE(Cend_memory);
1233             num_open_registers--;
1234             STORE(open_registers[num_open_registers]);
1235          }
1236          break;
1237       case Rmemory:
1238          if (ch == '0')
1239             goto bad_match_register;
1240          if (!(ch >= '0' && ch <= '9')) {
1241             goto bad_match_register;
1242          }
1243          bufp->uses_registers = 1;
1244          opcode = Cmatch_memory;
1245          ch -= '0';
1246          goto store_opcode_and_arg;
1247       case Rextended_memory:
1248          NEXTCHAR(ch);
1249          if (ch < '0' || ch > '9')
1250             goto bad_match_register;
1251          NEXTCHAR(a);
1252          if (a < '0' || a > '9')
1253             goto bad_match_register;
1254          ch = 10 * (a - '0') + ch - '0';
1255          if (ch == 0 || ch >= RE_NREGS)
1256             goto bad_match_register;
1257          bufp->uses_registers = 1;
1258          opcode = Cmatch_memory;
1259          goto store_opcode_and_arg;
1260       case Ropenset:
1261          {
1262             int complement;
1263             int prev;
1264             int offset;
1265             int range;
1266             int firstchar;
1267
1268             SET_LEVEL_START;
1269             ALLOC(1 + 256 / 8);
1270             STORE(Cset);
1271             offset = pattern_offset;
1272             for (a = 0; a < 256 / 8; a++)
1273                STORE(0);
1274             NEXTCHAR(ch);
1275             if (translate)
1276                ch = translate[(unsigned char)ch];
1277             if (ch == '\136') {
1278                complement = 1;
1279                NEXTCHAR(ch);
1280                if (translate)
1281                   ch = translate[(unsigned char)ch];
1282             } else
1283                complement = 0;
1284             prev = -1;
1285             range = 0;
1286             firstchar = 1;
1287             while (ch != '\135' || firstchar) {
1288                firstchar = 0;
1289                if (regexp_ansi_sequences && ch == '\134') {
1290                   NEXTCHAR(ch);
1291                   ANSI_TRANSLATE(ch);
1292                }
1293                if (range) {
1294                   for (a = prev; a <= (int)ch; a++)
1295                      SETBIT(pattern, offset, a);
1296                   prev = -1;
1297                   range = 0;
1298                } else if (prev != -1 && ch == '-')
1299                   range = 1;
1300                else {
1301                   SETBIT(pattern, offset, ch);
1302                   prev = ch;
1303                }
1304                NEXTCHAR(ch);
1305                if (translate)
1306                   ch = translate[(unsigned char)ch];
1307             }
1308             if (range)
1309                SETBIT(pattern, offset, '-');
1310             if (complement) {
1311                for (a = 0; a < 256 / 8; a++)
1312                   pattern[offset + a] ^= 0xff;
1313             }
1314             break;
1315          }
1316       case Rbegbuf:
1317          {
1318             opcode = Cbegbuf;
1319             goto store_opcode;
1320          }
1321       case Rendbuf:
1322          {
1323             opcode = Cendbuf;
1324             goto store_opcode;
1325          }
1326       case Rwordchar:
1327          {
1328             opcode = Csyntaxspec;
1329             ch = Sword;
1330             goto store_opcode_and_arg;
1331          }
1332       case Rnotwordchar:
1333          {
1334             opcode = Cnotsyntaxspec;
1335             ch = Sword;
1336             goto store_opcode_and_arg;
1337          }
1338       case Rwordbeg:
1339          {
1340             opcode = Cwordbeg;
1341             goto store_opcode;
1342          }
1343       case Rwordend:
1344          {
1345             opcode = Cwordend;
1346             goto store_opcode;
1347          }
1348       case Rwordbound:
1349          {
1350             opcode = Cwordbound;
1351             goto store_opcode;
1352          }
1353       case Rnotwordbound:
1354          {
1355             opcode = Cnotwordbound;
1356             goto store_opcode;
1357          }
1358       default:
1359          {
1360             abort();
1361          }
1362       }
1363       beginning_context = (op == Ropenpar || op == Ror);
1364    }
1365    if (starts_base != 0)
1366       goto parenthesis_error;
1367 // assert(num_jumps == 0);
1368    ALLOC(1);
1369    STORE(Cend);
1370    SET_FIELDS;
1371    if (!re_optimize(bufp))
1372       return "Optimization error";
1373    return NULL;
1374
1375  op_error:
1376    SET_FIELDS;
1377    return "Badly placed special character";
1378
1379  bad_match_register:
1380    SET_FIELDS;
1381    return "Bad match register number";
1382
1383  hex_error:
1384    SET_FIELDS;
1385    return "Bad hexadecimal number";
1386
1387  parenthesis_error:
1388    SET_FIELDS;
1389    return "Badly placed parenthesis";
1390
1391  out_of_memory:
1392    SET_FIELDS;
1393    return "Out of memory";
1394
1395  ends_prematurely:
1396    SET_FIELDS;
1397    return "Regular expression ends prematurely";
1398
1399  too_complex:
1400    SET_FIELDS;
1401    return "Regular expression too complex";
1402 }
1403
1404 #undef CHARAT
1405 #undef NEXTCHAR
1406 #undef GETHEX
1407 #undef ALLOC
1408 #undef STORE
1409 #undef CURRENT_LEVEL_START
1410 #undef SET_LEVEL_START
1411 #undef PUSH_LEVEL_STARTS
1412 #undef POP_LEVEL_STARTS
1413 #undef PUT_ADDR
1414 #undef INSERT_JUMP
1415 #undef SETBIT
1416 #undef SET_FIELDS
1417
1418 #define PREFETCH if (text == textend) goto fail
1419
1420 #define NEXTCHAR(var) \
1421 PREFETCH; \
1422 var = (unsigned char)*text++; \
1423 if (translate) \
1424         var = translate[var]
1425
1426
1427 int regcomp(regex_t * bufp, const char *regex, int cflags)
1428 {
1429    memset(bufp, 0, sizeof(regex_t));
1430    re_compile_pattern(bufp, (unsigned char *)regex);
1431    if (got_error) {
1432       return -1;
1433    }
1434    return 0;
1435 }
1436
1437 int regexec(regex_t * preg, const char *string, size_t nmatch,
1438             regmatch_t pmatch[], int eflags)
1439 {
1440    int stat;
1441    int len = strlen(string);
1442    struct re_registers regs;
1443    stat = re_search(preg, (unsigned char *)string, len, 0, len, &regs);
1444    /* stat is the start position in the string base 0 where
1445     *  the pattern was found or negative if not found.
1446     */
1447    return stat < 0 ? -1 : 0;
1448 }
1449
1450 size_t regerror(int errcode, regex_t * preg, char *errbuf, size_t errbuf_size)
1451 {
1452    bstrncpy(errbuf, preg->errmsg, errbuf_size);
1453    return 0;
1454 }
1455
1456 void regfree(regex_t * preg)
1457 {
1458 }
1459
1460 int re_match(regex_t * bufp, unsigned char *string, int size, int pos,
1461              regexp_registers_t old_regs)
1462 {
1463    unsigned char *code;
1464    unsigned char *translate;
1465    unsigned char *text;
1466    unsigned char *textstart;
1467    unsigned char *textend;
1468    int a;
1469    int b;
1470    int ch;
1471    int reg;
1472    int match_end;
1473    unsigned char *regstart;
1474    unsigned char *regend;
1475    int regsize;
1476    match_state state;
1477
1478 // assert(pos >= 0 && size >= 0);
1479 // assert(pos <= size);
1480
1481    text = string + pos;
1482    textstart = string;
1483    textend = string + size;
1484
1485    code = bufp->buffer;
1486
1487    translate = bufp->translate;
1488
1489    NEW_STATE(state, bufp->num_registers);
1490
1491  continue_matching:
1492    switch (*code++) {
1493    case Cend:
1494       {
1495          match_end = text - textstart;
1496          if (old_regs) {
1497             old_regs->start[0] = pos;
1498             old_regs->end[0] = match_end;
1499             if (!bufp->uses_registers) {
1500                for (a = 1; a < RE_NREGS; a++) {
1501                   old_regs->start[a] = -1;
1502                   old_regs->end[a] = -1;
1503                }
1504             } else {
1505                for (a = 1; a < bufp->num_registers; a++) {
1506                   if ((GET_REG_START(state, a) == NULL) ||
1507                       (GET_REG_END(state, a) == NULL)) {
1508                      old_regs->start[a] = -1;
1509                      old_regs->end[a] = -1;
1510                      continue;
1511                   }
1512                   old_regs->start[a] = GET_REG_START(state, a) - textstart;
1513                   old_regs->end[a] = GET_REG_END(state, a) - textstart;
1514                }
1515                for (; a < RE_NREGS; a++) {
1516                   old_regs->start[a] = -1;
1517                   old_regs->end[a] = -1;
1518                }
1519             }
1520          }
1521          FREE_STATE(state);
1522          return match_end - pos;
1523       }
1524    case Cbol:
1525       {
1526          if (text == textstart || text[-1] == '\n')
1527             goto continue_matching;
1528          goto fail;
1529       }
1530    case Ceol:
1531       {
1532          if (text == textend || *text == '\n')
1533             goto continue_matching;
1534          goto fail;
1535       }
1536    case Cset:
1537       {
1538          NEXTCHAR(ch);
1539          if (code[ch / 8] & (1 << (ch & 7))) {
1540             code += 256 / 8;
1541             goto continue_matching;
1542          }
1543          goto fail;
1544       }
1545    case Cexact:
1546       {
1547          NEXTCHAR(ch);
1548          if (ch != (unsigned char)*code++)
1549             goto fail;
1550          goto continue_matching;
1551       }
1552    case Canychar:
1553       {
1554          NEXTCHAR(ch);
1555          if (ch == '\n')
1556             goto fail;
1557          goto continue_matching;
1558       }
1559    case Cstart_memory:
1560       {
1561          reg = *code++;
1562          SET_REG_START(state, reg, text, goto error);
1563          goto continue_matching;
1564       }
1565    case Cend_memory:
1566       {
1567          reg = *code++;
1568          SET_REG_END(state, reg, text, goto error);
1569          goto continue_matching;
1570       }
1571    case Cmatch_memory:
1572       {
1573          reg = *code++;
1574          regstart = GET_REG_START(state, reg);
1575          regend = GET_REG_END(state, reg);
1576          if ((regstart == NULL) || (regend == NULL))
1577             goto fail;             /* or should we just match nothing? */
1578          regsize = regend - regstart;
1579
1580          if (regsize > (textend - text))
1581             goto fail;
1582          if (translate) {
1583             for (; regstart < regend; regstart++, text++)
1584                if (translate[*regstart] != translate[*text])
1585                   goto fail;
1586          } else
1587             for (; regstart < regend; regstart++, text++)
1588                if (*regstart != *text)
1589                   goto fail;
1590          goto continue_matching;
1591       }
1592    case Cupdate_failure_jump:
1593       {
1594          UPDATE_FAILURE(state, text, goto error);
1595          /* fall to next case */
1596       }
1597       /* treat Cstar_jump just like Cjump if it hasn't been optimized */
1598    case Cstar_jump:
1599    case Cjump:
1600       {
1601          a = (unsigned char)*code++;
1602          a |= (unsigned char)*code++ << 8;
1603          code += (int)SHORT(a);
1604          if (code < bufp->buffer || bufp->buffer + bufp->used < code) {
1605             set_error("Regex VM jump out of bounds (Cjump)");
1606             FREE_STATE(state);
1607             return -2;
1608          }
1609          goto continue_matching;
1610       }
1611    case Cdummy_failure_jump:
1612       {
1613          unsigned char *failuredest;
1614
1615          a = (unsigned char)*code++;
1616          a |= (unsigned char)*code++ << 8;
1617          a = (int)SHORT(a);
1618 //       assert(*code == Cfailure_jump);
1619          b = (unsigned char)code[1];
1620          b |= (unsigned char)code[2] << 8;
1621          failuredest = code + (int)SHORT(b) + 3;
1622          if (failuredest < bufp->buffer || bufp->buffer + bufp->used < failuredest) {
1623             set_error
1624                ("Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
1625             FREE_STATE(state);
1626             return -2;
1627          }
1628          PUSH_FAILURE(state, failuredest, NULL, goto error);
1629          code += a;
1630          if (code < bufp->buffer || bufp->buffer + bufp->used < code) {
1631             set_error("Regex VM jump out of bounds (Cdummy_failure_jump code)");
1632             FREE_STATE(state);
1633             return -2;
1634          }
1635          goto continue_matching;
1636       }
1637    case Cfailure_jump:
1638       {
1639          a = (unsigned char)*code++;
1640          a |= (unsigned char)*code++ << 8;
1641          a = (int)SHORT(a);
1642          if (code + a < bufp->buffer || bufp->buffer + bufp->used < code + a) {
1643             set_error("Regex VM jump out of bounds (Cfailure_jump)");
1644             FREE_STATE(state);
1645             return -2;
1646          }
1647          PUSH_FAILURE(state, code + a, text, goto error);
1648          goto continue_matching;
1649       }
1650    case Crepeat1:
1651       {
1652          unsigned char *pinst;
1653          a = (unsigned char)*code++;
1654          a |= (unsigned char)*code++ << 8;
1655          a = (int)SHORT(a);
1656          pinst = code + a;
1657          if (pinst < bufp->buffer || bufp->buffer + bufp->used < pinst) {
1658             set_error("Regex VM jump out of bounds (Crepeat1)");
1659             FREE_STATE(state);
1660             return -2;
1661          }
1662          /* pinst is sole instruction in loop, and it matches a
1663           * single character.  Since Crepeat1 was originally a
1664           * Cupdate_failure_jump, we also know that backtracking
1665           * is useless: so long as the single-character
1666           * expression matches, it must be used.  Also, in the
1667           * case of +, we've already matched one character, so +
1668           * can't fail: nothing here can cause a failure.  */
1669          switch (*pinst++) {
1670          case Cset:
1671             {
1672                if (translate) {
1673                   while (text < textend) {
1674                      ch = translate[(unsigned char)*text];
1675                      if (pinst[ch / 8] & (1 << (ch & 7)))
1676                         text++;
1677                      else
1678                         break;
1679                   }
1680                } else {
1681                   while (text < textend) {
1682                      ch = (unsigned char)*text;
1683                      if (pinst[ch / 8] & (1 << (ch & 7)))
1684                         text++;
1685                      else
1686                         break;
1687                   }
1688                }
1689                break;
1690             }
1691          case Cexact:
1692             {
1693                ch = (unsigned char)*pinst;
1694                if (translate) {
1695                   while (text < textend && translate[(unsigned char)*text] == ch)
1696                      text++;
1697                } else {
1698                   while (text < textend && (unsigned char)*text == ch)
1699                      text++;
1700                }
1701                break;
1702             }
1703          case Canychar:
1704             {
1705                while (text < textend && (unsigned char)*text != '\n')
1706                   text++;
1707                break;
1708             }
1709          case Csyntaxspec:
1710             {
1711                a = (unsigned char)*pinst;
1712                if (translate) {
1713                   while (text < textend && (SYNTAX(translate[*text]) & a))
1714                      text++;
1715                } else {
1716                   while (text < textend && (SYNTAX(*text) & a))
1717                      text++;
1718                }
1719                break;
1720             }
1721          case Cnotsyntaxspec:
1722             {
1723                a = (unsigned char)*pinst;
1724                if (translate) {
1725                   while (text < textend && !(SYNTAX(translate[*text]) & a))
1726                      text++;
1727                } else {
1728                   while (text < textend && !(SYNTAX(*text) & a))
1729                      text++;
1730                }
1731                break;
1732             }
1733          default:
1734             {
1735                FREE_STATE(state);
1736                set_error("Unknown regex opcode: memory corrupted?");
1737                return -2;
1738              /*NOTREACHED*/}
1739          }
1740          /* due to the funky way + and * are compiled, the top
1741           * failure- stack entry at this point is actually a
1742           * success entry -- update it & pop it */
1743          UPDATE_FAILURE(state, text, goto error);
1744          goto fail;                /* i.e., succeed <wink/sigh> */
1745       }
1746    case Cbegbuf:
1747       {
1748          if (text == textstart)
1749             goto continue_matching;
1750          goto fail;
1751       }
1752    case Cendbuf:
1753       {
1754          if (text == textend)
1755             goto continue_matching;
1756          goto fail;
1757       }
1758    case Cwordbeg:
1759       {
1760          if (text == textend)
1761             goto fail;
1762          if (!(SYNTAX(*text) & Sword))
1763             goto fail;
1764          if (text == textstart)
1765             goto continue_matching;
1766          if (!(SYNTAX(text[-1]) & Sword))
1767             goto continue_matching;
1768          goto fail;
1769       }
1770    case Cwordend:
1771       {
1772          if (text == textstart)
1773             goto fail;
1774          if (!(SYNTAX(text[-1]) & Sword))
1775             goto fail;
1776          if (text == textend)
1777             goto continue_matching;
1778          if (!(SYNTAX(*text) & Sword))
1779             goto continue_matching;
1780          goto fail;
1781       }
1782    case Cwordbound:
1783       {
1784          /* Note: as in gnu regexp, this also matches at the
1785           * beginning and end of buffer.  */
1786
1787          if (text == textstart || text == textend)
1788             goto continue_matching;
1789          if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
1790             goto continue_matching;
1791          goto fail;
1792       }
1793    case Cnotwordbound:
1794       {
1795          /* Note: as in gnu regexp, this never matches at the
1796           * beginning and end of buffer.  */
1797          if (text == textstart || text == textend)
1798             goto fail;
1799          if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
1800             goto continue_matching;
1801          goto fail;
1802       }
1803    case Csyntaxspec:
1804       {
1805          NEXTCHAR(ch);
1806          if (!(SYNTAX(ch) & (unsigned char)*code++))
1807             goto fail;
1808          goto continue_matching;
1809       }
1810    case Cnotsyntaxspec:
1811       {
1812          NEXTCHAR(ch);
1813          if (SYNTAX(ch) & (unsigned char)*code++)
1814             goto fail;
1815          goto continue_matching;
1816       }
1817    default:
1818       {
1819          FREE_STATE(state);
1820          set_error("Unknown regex opcode: memory corrupted?");
1821          return -2;
1822        /*NOTREACHED*/}
1823    }
1824
1825
1826
1827 #if 0                              /* This line is never reached --Guido */
1828    abort();
1829 #endif
1830    /*
1831     *NOTREACHED
1832     */
1833
1834    /* Using "break;" in the above switch statement is equivalent to "goto fail;" */
1835  fail:
1836    POP_FAILURE(state, code, text, goto done_matching, goto error);
1837    goto continue_matching;
1838
1839  done_matching:
1840 /*   if(translated != NULL) */
1841 /*      free(translated); */
1842    FREE_STATE(state);
1843    return -1;
1844
1845  error:
1846 /*   if (translated != NULL) */
1847 /*      free(translated); */
1848    FREE_STATE(state);
1849    return -2;
1850 }
1851
1852
1853 #undef PREFETCH
1854 #undef NEXTCHAR
1855
1856 int re_search(regex_t * bufp, unsigned char *string, int size, int pos,
1857               int range, regexp_registers_t regs)
1858 {
1859    unsigned char *fastmap;
1860    unsigned char *translate;
1861    unsigned char *text;
1862    unsigned char *partstart;
1863    unsigned char *partend;
1864    int dir;
1865    int ret;
1866    unsigned char anchor;
1867
1868 // assert(size >= 0 && pos >= 0);
1869 // assert(pos + range >= 0 && pos + range <= size);     /* Bugfix by ylo */
1870
1871    fastmap = bufp->fastmap;
1872    translate = bufp->translate;
1873    if (fastmap && !bufp->fastmap_accurate) {
1874       re_compile_fastmap(bufp);
1875       if (got_error)
1876          return -2;
1877    }
1878
1879    anchor = bufp->anchor;
1880    if (bufp->can_be_null == 1)     /* can_be_null == 2: can match null at eob */
1881       fastmap = NULL;
1882
1883    if (range < 0) {
1884       dir = -1;
1885       range = -range;
1886    } else
1887       dir = 1;
1888
1889    if (anchor == 2) {
1890       if (pos != 0)
1891          return -1;
1892       else
1893          range = 0;
1894    }
1895
1896    for (; range >= 0; range--, pos += dir) {
1897       if (fastmap) {
1898          if (dir == 1) {           /* searching forwards */
1899
1900             text = string + pos;
1901             partend = string + size;
1902             partstart = text;
1903             if (translate)
1904                while (text != partend &&
1905                       !fastmap[(unsigned char)translate[(unsigned char)*text]])
1906                   text++;
1907             else
1908                while (text != partend && !fastmap[(unsigned char)*text])
1909                   text++;
1910             pos += text - partstart;
1911             range -= text - partstart;
1912             if (pos == size && bufp->can_be_null == 0)
1913                return -1;
1914          } else {                  /* searching backwards */
1915             text = string + pos;
1916             partstart = string + pos - range;
1917             partend = text;
1918             if (translate)
1919                while (text != partstart && !fastmap[(unsigned char)
1920                                                     translate[(unsigned char)*text]])
1921                   text--;
1922             else
1923                while (text != partstart && !fastmap[(unsigned char)*text])
1924                   text--;
1925             pos -= partend - text;
1926             range -= partend - text;
1927          }
1928       }
1929       if (anchor == 1) {           /* anchored to begline */
1930          if (pos > 0 && (string[pos - 1] != '\n'))
1931             continue;
1932       }
1933 //    assert(pos >= 0 && pos <= size);
1934       ret = re_match(bufp, string, size, pos, regs);
1935       if (ret >= 0)
1936          return pos;
1937       if (ret == -2)
1938          return -2;
1939    }
1940    return -1;
1941 }
1942
1943 /*
1944 ** Local Variables:
1945 ** mode: c
1946 ** c-file-style: "python"
1947 ** End:
1948 */