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    bufp->cflags = cflags;
1463    if (bufp->cflags & REG_ICASE) {
1464       // ICI passer regex en lcase
1465    }
1466    re_compile_pattern(bufp, (unsigned char *)regex);
1467    if (got_error) {
1468       return -1;
1469    }
1470    return 0;
1471 }
1472
1473 int regexec(regex_t * preg, const char *string, size_t nmatch,
1474             regmatch_t pmatch[], int eflags)
1475 {
1476    int stat;
1477    int len = strlen(string);
1478    // ICI passer string en lcase
1479    struct re_registers regs;
1480    stat = re_search(preg, (unsigned char *)string, len, 0, len, &regs);
1481    /* stat is the start position in the string base 0 where
1482     *  the pattern was found or negative if not found.
1483     */
1484    return stat < 0 ? -1 : 0;
1485 }
1486
1487 size_t regerror(int errcode, regex_t * preg, char *errbuf, size_t errbuf_size)
1488 {
1489    bstrncpy(errbuf, preg->errmsg, errbuf_size);
1490    return 0;
1491 }
1492
1493 void regfree(regex_t * preg)
1494 {
1495 }
1496
1497 int re_match(regex_t * bufp, unsigned char *string, int size, int pos,
1498              regexp_registers_t old_regs)
1499 {
1500    unsigned char *code;
1501    unsigned char *translate;
1502    unsigned char *text;
1503    unsigned char *textstart;
1504    unsigned char *textend;
1505    int a;
1506    int b;
1507    int ch;
1508    int reg;
1509    int match_end;
1510    unsigned char *regstart;
1511    unsigned char *regend;
1512    int regsize;
1513    match_state state;
1514
1515 // assert(pos >= 0 && size >= 0);
1516 // assert(pos <= size);
1517
1518    text = string + pos;
1519    textstart = string;
1520    textend = string + size;
1521
1522    code = bufp->buffer;
1523
1524    translate = bufp->translate;
1525
1526    NEW_STATE(state, bufp->num_registers);
1527
1528  continue_matching:
1529    switch (*code++) {
1530    case Cend:
1531       {
1532          match_end = text - textstart;
1533          if (old_regs) {
1534             old_regs->start[0] = pos;
1535             old_regs->end[0] = match_end;
1536             if (!bufp->uses_registers) {
1537                for (a = 1; a < RE_NREGS; a++) {
1538                   old_regs->start[a] = -1;
1539                   old_regs->end[a] = -1;
1540                }
1541             } else {
1542                for (a = 1; a < bufp->num_registers; a++) {
1543                   if ((GET_REG_START(state, a) == NULL) ||
1544                       (GET_REG_END(state, a) == NULL)) {
1545                      old_regs->start[a] = -1;
1546                      old_regs->end[a] = -1;
1547                      continue;
1548                   }
1549                   old_regs->start[a] = GET_REG_START(state, a) - textstart;
1550                   old_regs->end[a] = GET_REG_END(state, a) - textstart;
1551                }
1552                for (; a < RE_NREGS; a++) {
1553                   old_regs->start[a] = -1;
1554                   old_regs->end[a] = -1;
1555                }
1556             }
1557          }
1558          FREE_STATE(state);
1559          return match_end - pos;
1560       }
1561    case Cbol:
1562       {
1563          if (text == textstart || text[-1] == '\n')
1564             goto continue_matching;
1565          goto fail;
1566       }
1567    case Ceol:
1568       {
1569          if (text == textend || *text == '\n')
1570             goto continue_matching;
1571          goto fail;
1572       }
1573    case Cset:
1574       {
1575          NEXTCHAR(ch);
1576          if (code[ch / 8] & (1 << (ch & 7))) {
1577             code += 256 / 8;
1578             goto continue_matching;
1579          }
1580          goto fail;
1581       }
1582    case Cexact:
1583       {
1584          NEXTCHAR(ch);
1585          if (ch != (unsigned char)*code++)
1586             goto fail;
1587          goto continue_matching;
1588       }
1589    case Canychar:
1590       {
1591          NEXTCHAR(ch);
1592          if (ch == '\n')
1593             goto fail;
1594          goto continue_matching;
1595       }
1596    case Cstart_memory:
1597       {
1598          reg = *code++;
1599          SET_REG_START(state, reg, text, goto error);
1600          goto continue_matching;
1601       }
1602    case Cend_memory:
1603       {
1604          reg = *code++;
1605          SET_REG_END(state, reg, text, goto error);
1606          goto continue_matching;
1607       }
1608    case Cmatch_memory:
1609       {
1610          reg = *code++;
1611          regstart = GET_REG_START(state, reg);
1612          regend = GET_REG_END(state, reg);
1613          if ((regstart == NULL) || (regend == NULL))
1614             goto fail;             /* or should we just match nothing? */
1615          regsize = regend - regstart;
1616
1617          if (regsize > (textend - text))
1618             goto fail;
1619          if (translate) {
1620             for (; regstart < regend; regstart++, text++)
1621                if (translate[*regstart] != translate[*text])
1622                   goto fail;
1623          } else
1624             for (; regstart < regend; regstart++, text++)
1625                if (*regstart != *text)
1626                   goto fail;
1627          goto continue_matching;
1628       }
1629    case Cupdate_failure_jump:
1630       {
1631          UPDATE_FAILURE(state, text, goto error);
1632          /* fall to next case */
1633       }
1634       /* treat Cstar_jump just like Cjump if it hasn't been optimized */
1635    case Cstar_jump:
1636    case Cjump:
1637       {
1638          a = (unsigned char)*code++;
1639          a |= (unsigned char)*code++ << 8;
1640          code += (int)SHORT(a);
1641          if (code < bufp->buffer || bufp->buffer + bufp->used < code) {
1642             set_error("Regex VM jump out of bounds (Cjump)");
1643             FREE_STATE(state);
1644             return -2;
1645          }
1646          goto continue_matching;
1647       }
1648    case Cdummy_failure_jump:
1649       {
1650          unsigned char *failuredest;
1651
1652          a = (unsigned char)*code++;
1653          a |= (unsigned char)*code++ << 8;
1654          a = (int)SHORT(a);
1655 //       assert(*code == Cfailure_jump);
1656          b = (unsigned char)code[1];
1657          b |= (unsigned char)code[2] << 8;
1658          failuredest = code + (int)SHORT(b) + 3;
1659          if (failuredest < bufp->buffer || bufp->buffer + bufp->used < failuredest) {
1660             set_error
1661                ("Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
1662             FREE_STATE(state);
1663             return -2;
1664          }
1665          PUSH_FAILURE(state, failuredest, NULL, goto error);
1666          code += a;
1667          if (code < bufp->buffer || bufp->buffer + bufp->used < code) {
1668             set_error("Regex VM jump out of bounds (Cdummy_failure_jump code)");
1669             FREE_STATE(state);
1670             return -2;
1671          }
1672          goto continue_matching;
1673       }
1674    case Cfailure_jump:
1675       {
1676          a = (unsigned char)*code++;
1677          a |= (unsigned char)*code++ << 8;
1678          a = (int)SHORT(a);
1679          if (code + a < bufp->buffer || bufp->buffer + bufp->used < code + a) {
1680             set_error("Regex VM jump out of bounds (Cfailure_jump)");
1681             FREE_STATE(state);
1682             return -2;
1683          }
1684          PUSH_FAILURE(state, code + a, text, goto error);
1685          goto continue_matching;
1686       }
1687    case Crepeat1:
1688       {
1689          unsigned char *pinst;
1690          a = (unsigned char)*code++;
1691          a |= (unsigned char)*code++ << 8;
1692          a = (int)SHORT(a);
1693          pinst = code + a;
1694          if (pinst < bufp->buffer || bufp->buffer + bufp->used < pinst) {
1695             set_error("Regex VM jump out of bounds (Crepeat1)");
1696             FREE_STATE(state);
1697             return -2;
1698          }
1699          /* pinst is sole instruction in loop, and it matches a
1700           * single character.  Since Crepeat1 was originally a
1701           * Cupdate_failure_jump, we also know that backtracking
1702           * is useless: so long as the single-character
1703           * expression matches, it must be used.  Also, in the
1704           * case of +, we've already matched one character, so +
1705           * can't fail: nothing here can cause a failure.  */
1706          switch (*pinst++) {
1707          case Cset:
1708             {
1709                if (translate) {
1710                   while (text < textend) {
1711                      ch = translate[(unsigned char)*text];
1712                      if (pinst[ch / 8] & (1 << (ch & 7)))
1713                         text++;
1714                      else
1715                         break;
1716                   }
1717                } else {
1718                   while (text < textend) {
1719                      ch = (unsigned char)*text;
1720                      if (pinst[ch / 8] & (1 << (ch & 7)))
1721                         text++;
1722                      else
1723                         break;
1724                   }
1725                }
1726                break;
1727             }
1728          case Cexact:
1729             {
1730                ch = (unsigned char)*pinst;
1731                if (translate) {
1732                   while (text < textend && translate[(unsigned char)*text] == ch)
1733                      text++;
1734                } else {
1735                   while (text < textend && (unsigned char)*text == ch)
1736                      text++;
1737                }
1738                break;
1739             }
1740          case Canychar:
1741             {
1742                while (text < textend && (unsigned char)*text != '\n')
1743                   text++;
1744                break;
1745             }
1746          case Csyntaxspec:
1747             {
1748                a = (unsigned char)*pinst;
1749                if (translate) {
1750                   while (text < textend && (SYNTAX(translate[*text]) & a))
1751                      text++;
1752                } else {
1753                   while (text < textend && (SYNTAX(*text) & a))
1754                      text++;
1755                }
1756                break;
1757             }
1758          case Cnotsyntaxspec:
1759             {
1760                a = (unsigned char)*pinst;
1761                if (translate) {
1762                   while (text < textend && !(SYNTAX(translate[*text]) & a))
1763                      text++;
1764                } else {
1765                   while (text < textend && !(SYNTAX(*text) & a))
1766                      text++;
1767                }
1768                break;
1769             }
1770          default:
1771             {
1772                FREE_STATE(state);
1773                set_error("Unknown regex opcode: memory corrupted?");
1774                return -2;
1775              /*NOTREACHED*/}
1776          }
1777          /* due to the funky way + and * are compiled, the top
1778           * failure- stack entry at this point is actually a
1779           * success entry -- update it & pop it */
1780          UPDATE_FAILURE(state, text, goto error);
1781          goto fail;                /* i.e., succeed <wink/sigh> */
1782       }
1783    case Cbegbuf:
1784       {
1785          if (text == textstart)
1786             goto continue_matching;
1787          goto fail;
1788       }
1789    case Cendbuf:
1790       {
1791          if (text == textend)
1792             goto continue_matching;
1793          goto fail;
1794       }
1795    case Cwordbeg:
1796       {
1797          if (text == textend)
1798             goto fail;
1799          if (!(SYNTAX(*text) & Sword))
1800             goto fail;
1801          if (text == textstart)
1802             goto continue_matching;
1803          if (!(SYNTAX(text[-1]) & Sword))
1804             goto continue_matching;
1805          goto fail;
1806       }
1807    case Cwordend:
1808       {
1809          if (text == textstart)
1810             goto fail;
1811          if (!(SYNTAX(text[-1]) & Sword))
1812             goto fail;
1813          if (text == textend)
1814             goto continue_matching;
1815          if (!(SYNTAX(*text) & Sword))
1816             goto continue_matching;
1817          goto fail;
1818       }
1819    case Cwordbound:
1820       {
1821          /* Note: as in gnu regexp, this also matches at the
1822           * beginning and end of buffer.  */
1823
1824          if (text == textstart || text == textend)
1825             goto continue_matching;
1826          if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
1827             goto continue_matching;
1828          goto fail;
1829       }
1830    case Cnotwordbound:
1831       {
1832          /* Note: as in gnu regexp, this never matches at the
1833           * beginning and end of buffer.  */
1834          if (text == textstart || text == textend)
1835             goto fail;
1836          if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
1837             goto continue_matching;
1838          goto fail;
1839       }
1840    case Csyntaxspec:
1841       {
1842          NEXTCHAR(ch);
1843          if (!(SYNTAX(ch) & (unsigned char)*code++))
1844             goto fail;
1845          goto continue_matching;
1846       }
1847    case Cnotsyntaxspec:
1848       {
1849          NEXTCHAR(ch);
1850          if (SYNTAX(ch) & (unsigned char)*code++)
1851             goto fail;
1852          goto continue_matching;
1853       }
1854    default:
1855       {
1856          FREE_STATE(state);
1857          set_error("Unknown regex opcode: memory corrupted?");
1858          return -2;
1859        /*NOTREACHED*/}
1860    }
1861
1862
1863
1864 #if 0                              /* This line is never reached --Guido */
1865    abort();
1866 #endif
1867    /*
1868     *NOTREACHED
1869     */
1870
1871    /* Using "break;" in the above switch statement is equivalent to "goto fail;" */
1872  fail:
1873    POP_FAILURE(state, code, text, goto done_matching, goto error);
1874    goto continue_matching;
1875
1876  done_matching:
1877 /*   if(translated != NULL) */
1878 /*      free(translated); */
1879    FREE_STATE(state);
1880    return -1;
1881
1882  error:
1883 /*   if (translated != NULL) */
1884 /*      free(translated); */
1885    FREE_STATE(state);
1886    return -2;
1887 }
1888
1889
1890 #undef PREFETCH
1891 #undef NEXTCHAR
1892
1893 int re_search(regex_t * bufp, unsigned char *string, int size, int pos,
1894               int range, regexp_registers_t regs)
1895 {
1896    unsigned char *fastmap;
1897    unsigned char *translate;
1898    unsigned char *text;
1899    unsigned char *partstart;
1900    unsigned char *partend;
1901    int dir;
1902    int ret;
1903    unsigned char anchor;
1904
1905 // assert(size >= 0 && pos >= 0);
1906 // assert(pos + range >= 0 && pos + range <= size);     /* Bugfix by ylo */
1907
1908    fastmap = bufp->fastmap;
1909    translate = bufp->translate;
1910    if (fastmap && !bufp->fastmap_accurate) {
1911       re_compile_fastmap(bufp);
1912       if (got_error)
1913          return -2;
1914    }
1915
1916    anchor = bufp->anchor;
1917    if (bufp->can_be_null == 1)     /* can_be_null == 2: can match null at eob */
1918       fastmap = NULL;
1919
1920    if (range < 0) {
1921       dir = -1;
1922       range = -range;
1923    } else
1924       dir = 1;
1925
1926    if (anchor == 2) {
1927       if (pos != 0)
1928          return -1;
1929       else
1930          range = 0;
1931    }
1932
1933    for (; range >= 0; range--, pos += dir) {
1934       if (fastmap) {
1935          if (dir == 1) {           /* searching forwards */
1936
1937             text = string + pos;
1938             partend = string + size;
1939             partstart = text;
1940             if (translate)
1941                while (text != partend &&
1942                       !fastmap[(unsigned char)translate[(unsigned char)*text]])
1943                   text++;
1944             else
1945                while (text != partend && !fastmap[(unsigned char)*text])
1946                   text++;
1947             pos += text - partstart;
1948             range -= text - partstart;
1949             if (pos == size && bufp->can_be_null == 0)
1950                return -1;
1951          } else {                  /* searching backwards */
1952             text = string + pos;
1953             partstart = string + pos - range;
1954             partend = text;
1955             if (translate)
1956                while (text != partstart && !fastmap[(unsigned char)
1957                                                     translate[(unsigned char)*text]])
1958                   text--;
1959             else
1960                while (text != partstart && !fastmap[(unsigned char)*text])
1961                   text--;
1962             pos -= partend - text;
1963             range -= partend - text;
1964          }
1965       }
1966       if (anchor == 1) {           /* anchored to begline */
1967          if (pos > 0 && (string[pos - 1] != '\n'))
1968             continue;
1969       }
1970 //    assert(pos >= 0 && pos <= size);
1971       ret = re_match(bufp, string, size, pos, regs);
1972       if (ret >= 0)
1973          return pos;
1974       if (ret == -2)
1975          return -2;
1976    }
1977    return -1;
1978 }
1979
1980 /*
1981 ** Local Variables:
1982 ** mode: c
1983 ** c-file-style: "python"
1984 ** End:
1985 */