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 curent 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()
 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(syntax)
 550         int syntax;
 551 {
 552         int ret;
 553
 554         ret = regexp_syntax;
 555         regexp_syntax = syntax;
 556         re_syntax = syntax; /* Exported copy */
 557         re_compile_initialize();
 558         return ret;
 559 }
 560
 561 static int hex_char_to_decimal(ch)
 562         int ch;
 563 {
 564         if (ch >= '0' && ch <= '9')
 565                 return ch - '0';
 566         if (ch >= 'a' && ch <= 'f')
 567                 return ch - 'a' + 10;
 568         if (ch >= 'A' && ch <= 'F')
 569                 return ch - 'A' + 10;
 570         return 16;
 571 }
 572
 573 static void re_compile_fastmap_aux(code,
 574                                    pos,
 575                                    visited,
 576                                    can_be_null,
 577                                    fastmap)
 578         unsigned char *code;
 579         int pos;
 580         unsigned char *visited;
 581         unsigned char *can_be_null;
 582         unsigned char *fastmap;
 583 {
 584         int a;
 585         int b;
 586         int syntaxcode;
 587
 588         if (visited[pos])
 589                 return;  /* we have already been here */
 590         visited[pos] = 1;
 591         for (;;)
 592                 switch (code[pos++]) {
 593                 case Cend:
 594                         {
 595                                 *can_be_null = 1;
 596                                 return;
 597                         }
 598                 case Cbol:
 599                 case Cbegbuf:
 600                 case Cendbuf:
 601                 case Cwordbeg:
 602                 case Cwordend:
 603                 case Cwordbound:
 604                 case Cnotwordbound:
 605                 {
 606                         for (a = 0; a < 256; a++)
 607                                 fastmap[a] = 1;
 608                         break;
 609                 }
 610                 case Csyntaxspec:
 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 Cnotsyntaxspec:
 619                 {
 620                         syntaxcode = code[pos++];
 621                         for (a = 0; a < 256; a++)
 622                                 if (!(SYNTAX(a) & syntaxcode) )
 623                                         fastmap[a] = 1;
 624                         return;
 625                 }
 626                 case Ceol:
 627                 {
 628                         fastmap['\n'] = 1;
 629                         if (*can_be_null == 0)
 630                                 *can_be_null = 2; /* can match null, but only at end of buffer*/
 631                         return;
 632                 }
 633                 case Cset:
 634                 {
 635                         for (a = 0; a < 256/8; a++)
 636                                 if (code[pos + a] != 0)
 637                                         for (b = 0; b < 8; b++)
 638                                                 if (code[pos + a] & (1 << b))
 639                                                         fastmap[(a << 3) + b] = 1;
 640                         pos += 256/8;
 641                         return;
 642                 }
 643                 case Cexact:
 644                 {
 645                         fastmap[(unsigned char)code[pos]] = 1;
 646                         return;
 647                 }
 648                 case Canychar:
 649                 {
 650                         for (a = 0; a < 256; a++)
 651                                 if (a != '\n')
 652                                         fastmap[a] = 1;
 653                         return;
 654                 }
 655                 case Cstart_memory:
 656                 case Cend_memory:
 657                 {
 658                         pos++;
 659                         break;
 660                 }
 661                 case Cmatch_memory:
 662                 {
 663                         for (a = 0; a < 256; a++)
 664                                 fastmap[a] = 1;
 665                         *can_be_null = 1;
 666                         return;
 667                 }
 668                 case Cjump:
 669                 case Cdummy_failure_jump:
 670                 case Cupdate_failure_jump:
 671                 case Cstar_jump:
 672                 {
 673                         a = (unsigned char)code[pos++];
 674                         a |= (unsigned char)code[pos++] << 8;
 675                         pos += (int)SHORT(a);
 676                         if (visited[pos])
 677                         {
 678                                 /* argh... the regexp contains empty loops.  This is not
 679                                    good, as this may cause a failure stack overflow when
 680                                    matching.  Oh well. */
 681                                 /* this path leads nowhere; pursue other paths. */
 682                                 return;
 683                         }
 684                         visited[pos] = 1;
 685                         break;
 686                 }
 687                 case Cfailure_jump:
 688                 {
 689                         a = (unsigned char)code[pos++];
 690                         a |= (unsigned char)code[pos++] << 8;
 691                         a = pos + (int)SHORT(a);
 692                         re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
 693                         break;
 694                 }
 695                 case Crepeat1:
 696                 {
 697                         pos += 2;
 698                         break;
 699                 }
 700                 default:
 701                 {
 702                         PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
 703                         return;
 704                         /*NOTREACHED*/
 705                 }
 706                 }
 707 }
 708
 709 static int re_do_compile_fastmap(buffer,
 710                                  used,
 711                                  pos,
 712                                  can_be_null,
 713                                  fastmap)
 714         unsigned char *buffer;
 715         int used;
 716         int pos;
 717         unsigned char *can_be_null;
 718         unsigned char *fastmap;
 719 {
 720         unsigned char small_visited[512], *visited;
 721
 722         if (used <= sizeof(small_visited))
 723                 visited = small_visited;
 724         else
 725         {
 726                 visited = malloc(used);
 727                 if (!visited)
 728                         return 0;
 729         }
 730         *can_be_null = 0;
 731         memset(fastmap, 0, 256);
 732         memset(visited, 0, used);
 733         re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
 734         if (visited != small_visited)
 735                 free(visited);
 736         return 1;
 737 }
 738
 739 void re_compile_fastmap(bufp)
 740         regexp_t bufp;
 741 {
 742         if (!bufp->fastmap || bufp->fastmap_accurate)
 743                 return;
 744         assert(bufp->used > 0);
 745         if (!re_do_compile_fastmap(bufp->buffer,
 746                                    bufp->used,
 747                                    0,
 748                                    &bufp->can_be_null,
 749                                    bufp->fastmap))
 750                 return;
 751         if (PyErr_Occurred()) return;
 752         if (bufp->buffer[0] == Cbol)
 753                 bufp->anchor = 1;   /* begline */
 754         else
 755                 if (bufp->buffer[0] == Cbegbuf)
 756                         bufp->anchor = 2; /* begbuf */
 757                 else
 758                         bufp->anchor = 0; /* none */
 759         bufp->fastmap_accurate = 1;
 760 }
 761
 762 /*
 763  * star is coded as:
 764  * 1: failure_jump 2
 765  *    ... code for operand of star
 766  *    star_jump 1
 767  * 2: ... code after star
 768  *
 769  * We change the star_jump to update_failure_jump if we can determine
 770  * that it is safe to do so; otherwise we change it to an ordinary
 771  * jump.
 772  *
 773  * plus is coded as
 774  *
 775  *    jump 2
 776  * 1: failure_jump 3
 777  * 2: ... code for operand of plus
 778  *    star_jump 1
 779  * 3: ... code after plus
 780  *
 781  * For star_jump considerations this is processed identically to star.
 782  *
 783  */
 784
 785 static int re_optimize_star_jump(bufp, code)
 786         regexp_t bufp;
 787         unsigned char *code;
 788 {
 789         unsigned char map[256];
 790         unsigned char can_be_null;
 791         unsigned char *p1;
 792         unsigned char *p2;
 793         unsigned char ch;
 794         int a;
 795         int b;
 796         int num_instructions = 0;
 797
 798         a = (unsigned char)*code++;
 799         a |= (unsigned char)*code++ << 8;
 800         a = (int)SHORT(a);
 801
 802         p1 = code + a + 3; /* skip the failure_jump */
 803         /* Check that the jump is within the pattern */
 804         if (p1<bufp->buffer || bufp->buffer+bufp->used<p1)
 805           {
 806             PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (failure_jump opt)");
 807             return 0;
 808           }
 809
 810         assert(p1[-3] == Cfailure_jump);
 811         p2 = code;
 812         /* p1 points inside loop, p2 points to after loop */
 813         if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
 814                                    p2 - bufp->buffer, &can_be_null, map))
 815                 goto make_normal_jump;
 816
 817         /* If we might introduce a new update point inside the
 818          * loop, we can't optimize because then update_jump would
 819          * update a wrong failure point.  Thus we have to be
 820          * quite careful here.
 821          */
 822
 823         /* loop until we find something that consumes a character */
 824   loop_p1:
 825         num_instructions++;
 826         switch (*p1++)
 827         {
 828         case Cbol:
 829         case Ceol:
 830         case Cbegbuf:
 831         case Cendbuf:
 832         case Cwordbeg:
 833         case Cwordend:
 834         case Cwordbound:
 835         case Cnotwordbound:
 836         {
 837                 goto loop_p1;
 838         }
 839         case Cstart_memory:
 840         case Cend_memory:
 841         {
 842                 p1++;
 843                 goto loop_p1;
 844         }
 845         case Cexact:
 846         {
 847                 ch = (unsigned char)*p1++;
 848                 if (map[(int)ch])
 849                         goto make_normal_jump;
 850                 break;
 851         }
 852         case Canychar:
 853         {
 854                 for (b = 0; b < 256; b++)
 855                         if (b != '\n' && map[b])
 856                                 goto make_normal_jump;
 857                 break;
 858         }
 859         case Cset:
 860         {
 861                 for (b = 0; b < 256; b++)
 862                         if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
 863                                 goto make_normal_jump;
 864                 p1 += 256/8;
 865                 break;
 866         }
 867         default:
 868         {
 869                 goto make_normal_jump;
 870         }
 871         }
 872         /* now we know that we can't backtrack. */
 873         while (p1 != p2 - 3)
 874         {
 875                 num_instructions++;
 876                 switch (*p1++)
 877                 {
 878                 case Cend:
 879                 {
 880                         return 0;
 881                 }
 882                 case Cbol:
 883                 case Ceol:
 884                 case Canychar:
 885                 case Cbegbuf:
 886                 case Cendbuf:
 887                 case Cwordbeg:
 888                 case Cwordend:
 889                 case Cwordbound:
 890                 case Cnotwordbound:
 891                 {
 892                         break;
 893                 }
 894                 case Cset:
 895                 {
 896                         p1 += 256/8;
 897                         break;
 898                 }
 899                 case Cexact:
 900                 case Cstart_memory:
 901                 case Cend_memory:
 902                 case Cmatch_memory:
 903                 case Csyntaxspec:
 904                 case Cnotsyntaxspec:
 905                 {
 906                         p1++;
 907                         break;
 908                 }
 909                 case Cjump:
 910                 case Cstar_jump:
 911                 case Cfailure_jump:
 912                 case Cupdate_failure_jump:
 913                 case Cdummy_failure_jump:
 914                 {
 915                         goto make_normal_jump;
 916                 }
 917                 default:
 918                 {
 919                         return 0;
 920                 }
 921                 }
 922         }
 923
 924         /* make_update_jump: */
 925         code -= 3;
 926         a += 3;  /* jump to after the Cfailure_jump */
 927         code[0] = Cupdate_failure_jump;
 928         code[1] = a & 0xff;
 929         code[2] = a >> 8;
 930         if (num_instructions > 1)
 931                 return 1;
 932         assert(num_instructions == 1);
 933         /* if the only instruction matches a single character, we can do
 934          * better */
 935         p1 = code + 3 + a;   /* start of sole instruction */
 936         if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
 937             *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
 938                 code[0] = Crepeat1;
 939         return 1;
 940
 941   make_normal_jump:
 942         code -= 3;
 943         *code = Cjump;
 944         return 1;
 945 }
 946
 947 static int re_optimize(bufp)
 948         regexp_t bufp;
 949 {
 950         unsigned char *code;
 951
 952         code = bufp->buffer;
 953
 954         while(1)
 955         {
 956                 switch (*code++)
 957                 {
 958                 case Cend:
 959                 {
 960                         return 1;
 961                 }
 962                 case Canychar:
 963                 case Cbol:
 964                 case Ceol:
 965                 case Cbegbuf:
 966                 case Cendbuf:
 967                 case Cwordbeg:
 968                 case Cwordend:
 969                 case Cwordbound:
 970                 case Cnotwordbound:
 971                 {
 972                         break;
 973                 }
 974                 case Cset:
 975                 {
 976                         code += 256/8;
 977                         break;
 978                 }
 979                 case Cexact:
 980                 case Cstart_memory:
 981                 case Cend_memory:
 982                 case Cmatch_memory:
 983                 case Csyntaxspec:
 984                 case Cnotsyntaxspec:
 985                 {
 986                         code++;
 987                         break;
 988                 }
 989                 case Cstar_jump:
 990                 {
 991                         if (!re_optimize_star_jump(bufp, code))
 992                         {
 993                                 return 0;
 994                         }
 995                         /* fall through */
 996                 }
 997                 case Cupdate_failure_jump:
 998                 case Cjump:
 999                 case Cdummy_failure_jump:
1000                 case Cfailure_jump:
1001                 case Crepeat1:
1002                 {
1003                         code += 2;
1004                         break;
1005                 }
1006                 default:
1007                 {
1008                         return 0;
1009                 }
1010                 }
1011         }
1012 }
1013
1014 #define NEXTCHAR(var) \
1015 { \
1016         if (pos >= size) \
1017                 goto ends_prematurely; \
1018         (var) = regex[pos]; \
1019         pos++; \
1020 }
1021
1022 #define ALLOC(amount) \
1023 { \
1024           if (pattern_offset+(amount) > alloc) \
1025           { \
1026                   alloc += 256 + (amount); \
1027                   pattern = realloc(pattern, alloc); \
1028                   if (!pattern) \
1029                           goto out_of_memory; \
1030           } \
1031 }
1032
1033 #define STORE(ch) pattern[pattern_offset++] = (ch)
1034
1035 #define CURRENT_LEVEL_START (starts[starts_base + current_level])
1036
1037 #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
1038
1039 #define PUSH_LEVEL_STARTS \
1040 if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
1041         starts_base += NUM_LEVELS; \
1042 else \
1043         goto too_complex \
1044
1045 #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
1046
1047 #define PUT_ADDR(offset,addr) \
1048 { \
1049         int disp = (addr) - (offset) - 2; \
1050         pattern[(offset)] = disp & 0xff; \
1051         pattern[(offset)+1] = (disp>>8) & 0xff; \
1052 }
1053
1054 #define INSERT_JUMP(pos,type,addr) \
1055 { \
1056         int a, p = (pos), t = (type), ad = (addr); \
1057         for (a = pattern_offset - 1; a >= p; a--) \
1058                 pattern[a + 3] = pattern[a]; \
1059         pattern[p] = t; \
1060         PUT_ADDR(p+1,ad); \
1061         pattern_offset += 3; \
1062 }
1063
1064 #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
1065
1066 #define SET_FIELDS \
1067 { \
1068         bufp->allocated = alloc; \
1069         bufp->buffer = pattern; \
1070         bufp->used = pattern_offset; \
1071 }
1072
1073 #define GETHEX(var) \
1074 { \
1075         unsigned char gethex_ch, gethex_value; \
1076         NEXTCHAR(gethex_ch); \
1077         gethex_value = hex_char_to_decimal(gethex_ch); \
1078         if (gethex_value == 16) \
1079                 goto hex_error; \
1080         NEXTCHAR(gethex_ch); \
1081         gethex_ch = hex_char_to_decimal(gethex_ch); \
1082         if (gethex_ch == 16) \
1083                 goto hex_error; \
1084         (var) = gethex_value * 16 + gethex_ch; \
1085 }
1086
1087 #define ANSI_TRANSLATE(ch) \
1088 { \
1089         switch (ch) \
1090         { \
1091         case 'a': \
1092         case 'A': \
1093         { \
1094                 ch = 7; /* audible bell */ \
1095                 break; \
1096         } \
1097         case 'b': \
1098         case 'B': \
1099         { \
1100                 ch = 8; /* backspace */ \
1101                 break; \
1102         } \
1103         case 'f': \
1104         case 'F': \
1105         { \
1106                 ch = 12; /* form feed */ \
1107                 break; \
1108         } \
1109         case 'n': \
1110         case 'N': \
1111         { \
1112                 ch = 10; /* line feed */ \
1113                 break; \
1114         } \
1115         case 'r': \
1116         case 'R': \
1117         { \
1118                 ch = 13; /* carriage return */ \
1119                 break; \
1120         } \
1121         case 't': \
1122         case 'T': \
1123         { \
1124               ch = 9; /* tab */ \
1125               break; \
1126         } \
1127         case 'v': \
1128         case 'V': \
1129         { \
1130                 ch = 11; /* vertical tab */ \
1131                 break; \
1132         } \
1133         case 'x': /* hex code */ \
1134         case 'X': \
1135         { \
1136                 GETHEX(ch); \
1137                 break; \
1138         } \
1139         default: \
1140         { \
1141                 /* other characters passed through */ \
1142                 if (translate) \
1143                         ch = translate[(unsigned char)ch]; \
1144                 break; \
1145         } \
1146         } \
1147 }
1148
1149 char *re_compile_pattern(regex, size, bufp)
1150         unsigned char *regex;
1151         int size;
1152         regexp_t bufp;
1153 {
1154         int a;
1155         int pos;
1156         int op;
1157         int current_level;
1158         int level;
1159         int opcode;
1160         int pattern_offset = 0, alloc;
1161         int starts[NUM_LEVELS * MAX_NESTING];
1162         int starts_base;
1163         int future_jumps[MAX_NESTING];
1164         int num_jumps;
1165         unsigned char ch = '\0';
1166         unsigned char *pattern;
1167         unsigned char *translate;
1168         int next_register;
1169         int paren_depth;
1170         int num_open_registers;
1171         int open_registers[RE_NREGS];
1172         int beginning_context;
1173
1174         if (!re_compile_initialized)
1175                 re_compile_initialize();
1176         bufp->used = 0;
1177         bufp->fastmap_accurate = 0;
1178         bufp->uses_registers = 1;
1179         bufp->num_registers = 1;
1180         translate = bufp->translate;
1181         pattern = bufp->buffer;
1182         alloc = bufp->allocated;
1183         if (alloc == 0 || pattern == NULL)
1184         {
1185                 alloc = 256;
1186                 pattern = malloc(alloc);
1187                 if (!pattern)
1188                         goto out_of_memory;
1189         }
1190         pattern_offset = 0;
1191         starts_base = 0;
1192         num_jumps = 0;
1193         current_level = 0;
1194         SET_LEVEL_START;
1195         num_open_registers = 0;
1196         next_register = 1;
1197         paren_depth = 0;
1198         beginning_context = 1;
1199         op = -1;
1200         /* we use Rend dummy to ensure that pending jumps are updated
1201            (due to low priority of Rend) before exiting the loop. */
1202         pos = 0;
1203         while (op != Rend)
1204         {
1205                 if (pos >= size)
1206                         op = Rend;
1207                 else
1208                 {
1209                         NEXTCHAR(ch);
1210                         if (translate)
1211                                 ch = translate[(unsigned char)ch];
1212                         op = regexp_plain_ops[(unsigned char)ch];
1213                         if (op == Rquote)
1214                         {
1215                                 NEXTCHAR(ch);
1216                                 op = regexp_quoted_ops[(unsigned char)ch];
1217                                 if (op == Rnormal && regexp_ansi_sequences)
1218                                         ANSI_TRANSLATE(ch);
1219                         }
1220                 }
1221                 level = regexp_precedences[op];
1222                 /* printf("ch='%c' op=%d level=%d current_level=%d
1223                    curlevstart=%d\n", ch, op, level, current_level,
1224                    CURRENT_LEVEL_START); */
1225                 if (level > current_level)
1226                 {
1227                         for (current_level++; current_level < level; current_level++)
1228                                 SET_LEVEL_START;
1229                         SET_LEVEL_START;
1230                 }
1231                 else
1232                         if (level < current_level)
1233                         {
1234                                 current_level = level;
1235                                 for (;num_jumps > 0 &&
1236                                              future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
1237                                      num_jumps--)
1238                                         PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
1239                         }
1240                 switch (op)
1241                 {
1242                 case Rend:
1243                 {
1244                         break;
1245                 }
1246                 case Rnormal:
1247                 {
1248                   normal_char:
1249                         opcode = Cexact;
1250                   store_opcode_and_arg: /* opcode & ch must be set */
1251                         SET_LEVEL_START;
1252                         ALLOC(2);
1253                         STORE(opcode);
1254                         STORE(ch);
1255                         break;
1256                 }
1257                 case Ranychar:
1258                 {
1259                         opcode = Canychar;
1260                   store_opcode:
1261                         SET_LEVEL_START;
1262                         ALLOC(1);
1263                         STORE(opcode);
1264                         break;
1265                 }
1266                 case Rquote:
1267                 {
1268                         abort();
1269                         /*NOTREACHED*/
1270                 }
1271                 case Rbol:
1272                 {
1273                         if (!beginning_context) {
1274                                 if (regexp_context_indep_ops)
1275                                         goto op_error;
1276                                 else
1277                                         goto normal_char;
1278                         }
1279                         opcode = Cbol;
1280                         goto store_opcode;
1281                 }
1282                 case Reol:
1283                 {
1284                         if (!((pos >= size) ||
1285                               ((regexp_syntax & RE_NO_BK_VBAR) ?
1286                                (regex[pos] == '\174') :
1287                                (pos+1 < size && regex[pos] == '\134' &&
1288                                 regex[pos+1] == '\174')) ||
1289                               ((regexp_syntax & RE_NO_BK_PARENS)?
1290                                (regex[pos] == ')'):
1291                                (pos+1 < size && regex[pos] == '\134' &&
1292                                 regex[pos+1] == ')')))) {
1293                                 if (regexp_context_indep_ops)
1294                                         goto op_error;
1295                                 else
1296                                         goto normal_char;
1297                         }
1298                         opcode = Ceol;
1299                         goto store_opcode;
1300                         /* NOTREACHED */
1301                         break;
1302                 }
1303                 case Roptional:
1304                 {
1305                         if (beginning_context) {
1306                                 if (regexp_context_indep_ops)
1307                                         goto op_error;
1308                                 else
1309                                         goto normal_char;
1310                         }
1311                         if (CURRENT_LEVEL_START == pattern_offset)
1312                                 break; /* ignore empty patterns for ? */
1313                         ALLOC(3);
1314                         INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1315                                     pattern_offset + 3);
1316                         break;
1317                 }
1318                 case Rstar:
1319                 case Rplus:
1320                 {
1321                         if (beginning_context) {
1322                                 if (regexp_context_indep_ops)
1323                                         goto op_error;
1324                                 else
1325                                         goto normal_char;
1326                         }
1327                         if (CURRENT_LEVEL_START == pattern_offset)
1328                                 break; /* ignore empty patterns for + and * */
1329                         ALLOC(9);
1330                         INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1331                                     pattern_offset + 6);
1332                         INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
1333                         if (op == Rplus)  /* jump over initial failure_jump */
1334                                 INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
1335                                             CURRENT_LEVEL_START + 6);
1336                         break;
1337                 }
1338                 case Ror:
1339                 {
1340                         ALLOC(6);
1341                         INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1342                                     pattern_offset + 6);
1343                         if (num_jumps >= MAX_NESTING)
1344                                 goto too_complex;
1345                         STORE(Cjump);
1346                         future_jumps[num_jumps++] = pattern_offset;
1347                         STORE(0);
1348                         STORE(0);
1349                         SET_LEVEL_START;
1350                         break;
1351                 }
1352                 case Ropenpar:
1353                 {
1354                         SET_LEVEL_START;
1355                         if (next_register < RE_NREGS)
1356                         {
1357                                 bufp->uses_registers = 1;
1358                                 ALLOC(2);
1359                                 STORE(Cstart_memory);
1360                                 STORE(next_register);
1361                                 open_registers[num_open_registers++] = next_register;
1362                                 bufp->num_registers++;
1363                                 next_register++;
1364                         }
1365                         paren_depth++;
1366                         PUSH_LEVEL_STARTS;
1367                         current_level = 0;
1368                         SET_LEVEL_START;
1369                         break;
1370                 }
1371                 case Rclosepar:
1372                 {
1373                         if (paren_depth <= 0)
1374                                 goto parenthesis_error;
1375                         POP_LEVEL_STARTS;
1376                         current_level = regexp_precedences[Ropenpar];
1377                         paren_depth--;
1378                         if (paren_depth < num_open_registers)
1379                         {
1380                                 bufp->uses_registers = 1;
1381                                 ALLOC(2);
1382                                 STORE(Cend_memory);
1383                                 num_open_registers--;
1384                                 STORE(open_registers[num_open_registers]);
1385                         }
1386                         break;
1387                 }
1388                 case Rmemory:
1389                 {
1390                         if (ch == '0')
1391                                 goto bad_match_register;
1392                         assert(ch >= '0' && ch <= '9');
1393                         bufp->uses_registers = 1;
1394                         opcode = Cmatch_memory;
1395                         ch -= '0';
1396                         goto store_opcode_and_arg;
1397                 }
1398                 case Rextended_memory:
1399                 {
1400                         NEXTCHAR(ch);
1401                         if (ch < '0' || ch > '9')
1402                                 goto bad_match_register;
1403                         NEXTCHAR(a);
1404                         if (a < '0' || a > '9')
1405                                 goto bad_match_register;
1406                         ch = 10 * (a - '0') + ch - '0';
1407                         if (ch <= 0 || ch >= RE_NREGS)
1408                                 goto bad_match_register;
1409                         bufp->uses_registers = 1;
1410                         opcode = Cmatch_memory;
1411                         goto store_opcode_and_arg;
1412                 }
1413                 case Ropenset:
1414                 {
1415                         int complement;
1416                         int prev;
1417                         int offset;
1418                         int range;
1419                         int firstchar;
1420
1421                         SET_LEVEL_START;
1422                         ALLOC(1+256/8);
1423                         STORE(Cset);
1424                         offset = pattern_offset;
1425                         for (a = 0; a < 256/8; a++)
1426                                 STORE(0);
1427                         NEXTCHAR(ch);
1428                         if (translate)
1429                                 ch = translate[(unsigned char)ch];
1430                         if (ch == '\136')
1431                         {
1432                                 complement = 1;
1433                                 NEXTCHAR(ch);
1434                                 if (translate)
1435                                         ch = translate[(unsigned char)ch];
1436                         }
1437                         else
1438                                 complement = 0;
1439                         prev = -1;
1440                         range = 0;
1441                         firstchar = 1;
1442                         while (ch != '\135' || firstchar)
1443                         {
1444                                 firstchar = 0;
1445                                 if (regexp_ansi_sequences && ch == '\134')
1446                                 {
1447                                         NEXTCHAR(ch);
1448                                         ANSI_TRANSLATE(ch);
1449                                 }
1450                                 if (range)
1451                                 {
1452                                         for (a = prev; a <= (int)ch; a++)
1453                                                 SETBIT(pattern, offset, a);
1454                                         prev = -1;
1455                                         range = 0;
1456                                 }
1457                                 else
1458                                         if (prev != -1 && ch == '-')
1459                                                 range = 1;
1460                                         else
1461                                         {
1462                                                 SETBIT(pattern, offset, ch);
1463                                                 prev = ch;
1464                                         }
1465                                 NEXTCHAR(ch);
1466                                 if (translate)
1467                                         ch = translate[(unsigned char)ch];
1468                         }
1469                         if (range)
1470                                 SETBIT(pattern, offset, '-');
1471                         if (complement)
1472                         {
1473                                 for (a = 0; a < 256/8; a++)
1474                                         pattern[offset+a] ^= 0xff;
1475                         }
1476                         break;
1477                 }
1478                 case Rbegbuf:
1479                 {
1480                         opcode = Cbegbuf;
1481                         goto store_opcode;
1482                 }
1483                 case Rendbuf:
1484                 {
1485                         opcode = Cendbuf;
1486                         goto store_opcode;
1487                 }
1488                 case Rwordchar:
1489                 {
1490                         opcode = Csyntaxspec;
1491                         ch = Sword;
1492                         goto store_opcode_and_arg;
1493                 }
1494                 case Rnotwordchar:
1495                 {
1496                         opcode = Cnotsyntaxspec;
1497                         ch = Sword;
1498                         goto store_opcode_and_arg;
1499                 }
1500                 case Rwordbeg:
1501                 {
1502                         opcode = Cwordbeg;
1503                         goto store_opcode;
1504                 }
1505                 case Rwordend:
1506                 {
1507                         opcode = Cwordend;
1508                         goto store_opcode;
1509                 }
1510                 case Rwordbound:
1511                 {
1512                         opcode = Cwordbound;
1513                         goto store_opcode;
1514                 }
1515                 case Rnotwordbound:
1516                 {
1517                         opcode = Cnotwordbound;
1518                         goto store_opcode;
1519                 }
1520                 default:
1521                 {
1522                         abort();
1523                 }
1524                 }
1525                 beginning_context = (op == Ropenpar || op == Ror);
1526         }
1527         if (starts_base != 0)
1528                 goto parenthesis_error;
1529         assert(num_jumps == 0);
1530         ALLOC(1);
1531         STORE(Cend);
1532         SET_FIELDS;
1533         if(!re_optimize(bufp))
1534                 return "Optimization error";
1535         return NULL;
1536
1537   op_error:
1538         SET_FIELDS;
1539         return "Badly placed special character";
1540
1541   bad_match_register:
1542         SET_FIELDS;
1543         return "Bad match register number";
1544
1545   hex_error:
1546         SET_FIELDS;
1547         return "Bad hexadecimal number";
1548
1549   parenthesis_error:
1550         SET_FIELDS;
1551         return "Badly placed parenthesis";
1552
1553   out_of_memory:
1554         SET_FIELDS;
1555         return "Out of memory";
1556
1557   ends_prematurely:
1558         SET_FIELDS;
1559         return "Regular expression ends prematurely";
1560
1561   too_complex:
1562         SET_FIELDS;
1563         return "Regular expression too complex";
1564 }
1565
1566 #undef CHARAT
1567 #undef NEXTCHAR
1568 #undef GETHEX
1569 #undef ALLOC
1570 #undef STORE
1571 #undef CURRENT_LEVEL_START
1572 #undef SET_LEVEL_START
1573 #undef PUSH_LEVEL_STARTS
1574 #undef POP_LEVEL_STARTS
1575 #undef PUT_ADDR
1576 #undef INSERT_JUMP
1577 #undef SETBIT
1578 #undef SET_FIELDS
1579
1580 #define PREFETCH if (text == textend) goto fail
1581
1582 #define NEXTCHAR(var) \
1583 PREFETCH; \
1584 var = (unsigned char)*text++; \
1585 if (translate) \
1586         var = translate[var]
1587
1588 int re_match(bufp,
1589              string,
1590              size,
1591              pos,
1592              old_regs)
1593         regexp_t bufp;
1594         unsigned char *string;
1595         int size;
1596         int pos;
1597         regexp_registers_t old_regs;
1598 {
1599         unsigned char *code;
1600         unsigned char *translate;
1601         unsigned char *text;
1602         unsigned char *textstart;
1603         unsigned char *textend;
1604         int a;
1605         int b;
1606         int ch;
1607         int reg;
1608         int match_end;
1609         unsigned char *regstart;
1610         unsigned char *regend;
1611         int regsize;
1612         match_state state;
1613
1614         assert(pos >= 0 && size >= 0);
1615         assert(pos <= size);
1616
1617         text = string + pos;
1618         textstart = string;
1619         textend = string + size;
1620
1621         code = bufp->buffer;
1622
1623         translate = bufp->translate;
1624
1625         NEW_STATE(state, bufp->num_registers);
1626
1627   continue_matching:
1628         switch (*code++)
1629         {
1630         case Cend:
1631         {
1632                 match_end = text - textstart;
1633                 if (old_regs)
1634                 {
1635                         old_regs->start[0] = pos;
1636                         old_regs->end[0] = match_end;
1637                         if (!bufp->uses_registers)
1638                         {
1639                                 for (a = 1; a < RE_NREGS; a++)
1640                                 {
1641                                         old_regs->start[a] = -1;
1642                                         old_regs->end[a] = -1;
1643                                 }
1644                         }
1645                         else
1646                         {
1647                                 for (a = 1; a < bufp->num_registers; a++)
1648                                 {
1649                                         if ((GET_REG_START(state, a) == NULL) ||
1650                                             (GET_REG_END(state, a) == NULL))
1651                                         {
1652                                                 old_regs->start[a] = -1;
1653                                                 old_regs->end[a] = -1;
1654                                                 continue;
1655                                         }
1656                                         old_regs->start[a] = GET_REG_START(state, a) - textstart;
1657                                         old_regs->end[a] = GET_REG_END(state, a) - textstart;
1658                                 }
1659                                 for (; a < RE_NREGS; a++)
1660                                 {
1661                                         old_regs->start[a] = -1;
1662                                         old_regs->end[a] = -1;
1663                                 }
1664                         }
1665                 }
1666                 FREE_STATE(state);
1667                 return match_end - pos;
1668         }
1669         case Cbol:
1670         {
1671                 if (text == textstart || text[-1] == '\n')
1672                         goto continue_matching;
1673                 goto fail;
1674         }
1675         case Ceol:
1676         {
1677                 if (text == textend || *text == '\n')
1678                         goto continue_matching;
1679                 goto fail;
1680         }
1681         case Cset:
1682         {
1683                 NEXTCHAR(ch);
1684                 if (code[ch/8] & (1<<(ch & 7)))
1685                 {
1686                         code += 256/8;
1687                         goto continue_matching;
1688                 }
1689                 goto fail;
1690         }
1691         case Cexact:
1692         {
1693                 NEXTCHAR(ch);
1694                 if (ch != (unsigned char)*code++)
1695                         goto fail;
1696                 goto continue_matching;
1697         }
1698         case Canychar:
1699         {
1700                 NEXTCHAR(ch);
1701                 if (ch == '\n')
1702                         goto fail;
1703                 goto continue_matching;
1704         }
1705         case Cstart_memory:
1706         {
1707                 reg = *code++;
1708                 SET_REG_START(state, reg, text, goto error);
1709                 goto continue_matching;
1710         }
1711         case Cend_memory:
1712         {
1713                 reg = *code++;
1714                 SET_REG_END(state, reg, text, goto error);
1715                 goto continue_matching;
1716         }
1717         case Cmatch_memory:
1718         {
1719                 reg = *code++;
1720                 regstart = GET_REG_START(state, reg);
1721                 regend = GET_REG_END(state, reg);
1722                 if ((regstart == NULL) || (regend == NULL))
1723                         goto fail;  /* or should we just match nothing? */
1724                 regsize = regend - regstart;
1725
1726                 if (regsize > (textend - text))
1727                         goto fail;
1728                 if(translate)
1729                 {
1730                         for (; regstart < regend; regstart++, text++)
1731                                 if (translate[*regstart] != translate[*text])
1732                                         goto fail;
1733                 }
1734                 else
1735                         for (; regstart < regend; regstart++, text++)
1736                                 if (*regstart != *text)
1737                                         goto fail;
1738                 goto continue_matching;
1739         }
1740         case Cupdate_failure_jump:
1741         {
1742                 UPDATE_FAILURE(state, text, goto error);
1743                 /* fall to next case */
1744         }
1745         /* treat Cstar_jump just like Cjump if it hasn't been optimized */
1746         case Cstar_jump:
1747         case Cjump:
1748         {
1749                 a = (unsigned char)*code++;
1750                 a |= (unsigned char)*code++ << 8;
1751                 code += (int)SHORT(a);
1752                 if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
1753                         PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cjump)");
1754                         FREE_STATE(state);
1755                         return -2;
1756                 }
1757                 goto continue_matching;
1758         }
1759         case Cdummy_failure_jump:
1760         {
1761                 unsigned char *failuredest;
1762
1763                 a = (unsigned char)*code++;
1764                 a |= (unsigned char)*code++ << 8;
1765                 a = (int)SHORT(a);
1766                 assert(*code == Cfailure_jump);
1767                 b = (unsigned char)code[1];
1768                 b |= (unsigned char)code[2] << 8;
1769                 failuredest = code + (int)SHORT(b) + 3;
1770                 if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
1771                         PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
1772                         FREE_STATE(state);
1773                         return -2;
1774                 }
1775                 PUSH_FAILURE(state, failuredest, NULL, goto error);
1776                 code += a;
1777                 if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
1778                         PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)");
1779                         FREE_STATE(state);
1780                         return -2;
1781                 }
1782                 goto continue_matching;
1783         }
1784         case Cfailure_jump:
1785         {
1786                 a = (unsigned char)*code++;
1787                 a |= (unsigned char)*code++ << 8;
1788                 a = (int)SHORT(a);
1789                 if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
1790                         PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)");
1791                         FREE_STATE(state);
1792                         return -2;
1793                 }
1794                 PUSH_FAILURE(state, code + a, text, goto error);
1795                 goto continue_matching;
1796         }
1797         case Crepeat1:
1798         {
1799                 unsigned char *pinst;
1800                 a = (unsigned char)*code++;
1801                 a |= (unsigned char)*code++ << 8;
1802                 a = (int)SHORT(a);
1803                 pinst = code + a;
1804                 if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
1805                         PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Crepeat1)");
1806                         FREE_STATE(state);
1807                         return -2;
1808                 }
1809                 /* pinst is sole instruction in loop, and it matches a
1810                  * single character.  Since Crepeat1 was originally a
1811                  * Cupdate_failure_jump, we also know that backtracking
1812                  * is useless: so long as the single-character
1813                  * expression matches, it must be used.  Also, in the
1814                  * case of +, we've already matched one character, so +
1815                  * can't fail: nothing here can cause a failure.  */
1816                 switch (*pinst++)
1817                 {
1818                 case Cset:
1819                   {
1820                         if (translate)
1821                         {
1822                                 while (text < textend)
1823                                 {
1824                                         ch = translate[(unsigned char)*text];
1825                                         if (pinst[ch/8] & (1<<(ch & 7)))
1826                                                 text++;
1827                                         else
1828                                                 break;
1829                                 }
1830                         }
1831                         else
1832                         {
1833                                 while (text < textend)
1834                                 {
1835                                         ch = (unsigned char)*text;
1836                                         if (pinst[ch/8] & (1<<(ch & 7)))
1837                                                 text++;
1838                                         else
1839                                                 break;
1840                                 }
1841                         }
1842                         break;
1843                 }
1844                 case Cexact:
1845                 {
1846                         ch = (unsigned char)*pinst;
1847                         if (translate)
1848                         {
1849                                 while (text < textend &&
1850                                        translate[(unsigned char)*text] == ch)
1851                                         text++;
1852                         }
1853                         else
1854                         {
1855                                 while (text < textend && (unsigned char)*text == ch)
1856                                         text++;
1857                         }
1858                         break;
1859                 }
1860                 case Canychar:
1861                 {
1862                         while (text < textend && (unsigned char)*text != '\n')
1863                                 text++;
1864                         break;
1865                 }
1866                 case Csyntaxspec:
1867                 {
1868                         a = (unsigned char)*pinst;
1869                         if (translate)
1870                         {
1871                                 while (text < textend &&
1872                                        (SYNTAX(translate[*text]) & a) )
1873                                         text++;
1874                         }
1875                         else
1876                         {
1877                                 while (text < textend && (SYNTAX(*text) & a) )
1878                                         text++;
1879                         }
1880                         break;
1881                 }
1882                 case Cnotsyntaxspec:
1883                 {
1884                         a = (unsigned char)*pinst;
1885                         if (translate)
1886                         {
1887                                 while (text < textend &&
1888                                        !(SYNTAX(translate[*text]) & a) )
1889                                         text++;
1890                         }
1891                         else
1892                         {
1893                                 while (text < textend && !(SYNTAX(*text) & a) )
1894                                         text++;
1895                         }
1896                         break;
1897                 }
1898                 default:
1899                 {
1900                         FREE_STATE(state);
1901                         PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
1902                         return -2;
1903                         /*NOTREACHED*/
1904                 }
1905                 }
1906                 /* due to the funky way + and * are compiled, the top
1907                  * failure- stack entry at this point is actually a
1908                  * success entry -- update it & pop it */
1909                 UPDATE_FAILURE(state, text, goto error);
1910                 goto fail;      /* i.e., succeed <wink/sigh> */
1911         }
1912         case Cbegbuf:
1913         {
1914                 if (text == textstart)
1915                         goto continue_matching;
1916                 goto fail;
1917         }
1918         case Cendbuf:
1919         {
1920                 if (text == textend)
1921                         goto continue_matching;
1922                 goto fail;
1923         }
1924         case Cwordbeg:
1925         {
1926                 if (text == textend)
1927                         goto fail;
1928                 if (!(SYNTAX(*text) & Sword))
1929                         goto fail;
1930                 if (text == textstart)
1931                         goto continue_matching;
1932                 if (!(SYNTAX(text[-1]) & Sword))
1933                         goto continue_matching;
1934                 goto fail;
1935         }
1936         case Cwordend:
1937         {
1938                 if (text == textstart)
1939                         goto fail;
1940                 if (!(SYNTAX(text[-1]) & Sword))
1941                         goto fail;
1942                 if (text == textend)
1943                         goto continue_matching;
1944                 if (!(SYNTAX(*text) & Sword))
1945                         goto continue_matching;
1946                 goto fail;
1947         }
1948         case Cwordbound:
1949         {
1950                 /* Note: as in gnu regexp, this also matches at the
1951                  * beginning and end of buffer.  */
1952
1953                 if (text == textstart || text == textend)
1954                         goto continue_matching;
1955                 if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
1956                         goto continue_matching;
1957                 goto fail;
1958         }
1959         case Cnotwordbound:
1960         {
1961                 /* Note: as in gnu regexp, this never matches at the
1962                  * beginning and end of buffer.  */
1963                 if (text == textstart || text == textend)
1964                         goto fail;
1965                 if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
1966                         goto continue_matching;
1967                 goto fail;
1968         }
1969         case Csyntaxspec:
1970         {
1971                 NEXTCHAR(ch);
1972                 if (!(SYNTAX(ch) & (unsigned char)*code++))
1973                         goto fail;
1974                 goto continue_matching;
1975         }
1976         case Cnotsyntaxspec:
1977         {
1978                 NEXTCHAR(ch);
1979                 if (SYNTAX(ch) & (unsigned char)*code++)
1980                         goto fail;
1981                 goto continue_matching;
1982         }
1983         default:
1984         {
1985                 FREE_STATE(state);
1986                 PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
1987                 return -2;
1988                 /*NOTREACHED*/
1989         }
1990         }
1991
1992
1993
1994 #if 0 /* This line is never reached --Guido */
1995         abort();
1996 #endif
1997         /*
1998          *NOTREACHED
1999          */
2000
2001         /* Using "break;" in the above switch statement is equivalent to "goto fail;" */
2002   fail:
2003         POP_FAILURE(state, code, text, goto done_matching, goto error);
2004         goto continue_matching;
2005
2006   done_matching:
2007 /*   if(translated != NULL) */
2008 /*      free(translated); */
2009         FREE_STATE(state);
2010         return -1;
2011
2012   error:
2013 /*   if (translated != NULL) */
2014 /*      free(translated); */
2015         FREE_STATE(state);
2016         return -2;
2017 }
2018
2019
2020 #undef PREFETCH
2021 #undef NEXTCHAR
2022
2023 int re_search(bufp,
2024               string,
2025               size,
2026               pos,
2027               range,
2028               regs)
2029         regexp_t bufp;
2030         unsigned char *string;
2031         int size;
2032         int pos;
2033         int range;
2034         regexp_registers_t regs;
2035 {
2036         unsigned char *fastmap;
2037         unsigned char *translate;
2038         unsigned char *text;
2039         unsigned char *partstart;
2040         unsigned char *partend;
2041         int dir;
2042         int ret;
2043         unsigned char anchor;
2044
2045         assert(size >= 0 && pos >= 0);
2046         assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
2047
2048         fastmap = bufp->fastmap;
2049         translate = bufp->translate;
2050         if (fastmap && !bufp->fastmap_accurate) {
2051                 re_compile_fastmap(bufp);
2052                 if (PyErr_Occurred()) return -2;
2053         }
2054
2055         anchor = bufp->anchor;
2056         if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
2057                 fastmap = NULL;
2058
2059         if (range < 0)
2060         {
2061                 dir = -1;
2062                 range = -range;
2063         }
2064         else
2065                 dir = 1;
2066
2067         if (anchor == 2) {
2068                 if (pos != 0)
2069                         return -1;
2070                 else
2071                         range = 0;
2072         }
2073
2074         for (; range >= 0; range--, pos += dir)
2075         {
2076                 if (fastmap)
2077                 {
2078                         if (dir == 1)
2079                         { /* searching forwards */
2080
2081                                 text = string + pos;
2082                                 partend = string + size;
2083                                 partstart = text;
2084                                 if (translate)
2085                                         while (text != partend &&
2086                                                !fastmap[(unsigned char) translate[(unsigned char)*text]])
2087                                                 text++;
2088                                 else
2089                                         while (text != partend && !fastmap[(unsigned char)*text])
2090                                                 text++;
2091                                 pos += text - partstart;
2092                                 range -= text - partstart;
2093                                 if (pos == size && bufp->can_be_null == 0)
2094                                         return -1;
2095                         }
2096                         else
2097                         { /* searching backwards */
2098                                 text = string + pos;
2099                                 partstart = string + pos - range;
2100                                 partend = text;
2101                                 if (translate)
2102                                         while (text != partstart &&
2103                                                !fastmap[(unsigned char)
2104                                                        translate[(unsigned char)*text]])
2105                                                 text--;
2106                                 else
2107                                         while (text != partstart &&
2108                                                !fastmap[(unsigned char)*text])
2109                                                 text--;
2110                                 pos -= partend - text;
2111                                 range -= partend - text;
2112                         }
2113                 }
2114                 if (anchor == 1)
2115                 { /* anchored to begline */
2116                         if (pos > 0 && (string[pos - 1] != '\n'))
2117                                 continue;
2118                 }
2119                 assert(pos >= 0 && pos <= size);
2120                 ret = re_match(bufp, string, size, pos, regs);
2121                 if (ret >= 0)
2122                         return pos;
2123                 if (ret == -2)
2124                         return -2;
2125         }
2126         return -1;
2127 }
2128
2129 /*
2130 ** Local Variables:
2131 ** mode: c
2132 ** c-file-style: "python"
2133 ** End:
2134 */