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