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