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