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