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