Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

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