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

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