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