blob: a45b9e264f3b8f37e592f1d8ed3d198adab8c321 [file] [log] [blame]
Guido van Rossum004c1e11997-05-09 02:35:58 +00001/* 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$ */
Guido van Rossumb674c3b1992-01-19 16:32:47 +000030
Guido van Rossum95e80531997-08-13 22:34:14 +000031#include "Python.h"
Guido van Rossumb674c3b1992-01-19 16:32:47 +000032#include "regexpr.h"
Guido van Rossum8102c001997-09-05 01:48:48 +000033#include <assert.h>
Guido van Rossumb674c3b1992-01-19 16:32:47 +000034
Guido van Rossumdb25f321997-07-10 14:31:32 +000035/* 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
Guido van Rossum004c1e11997-05-09 02:35:58 +000041/* 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
57typedef union item_t
58{
Guido van Rossumdb25f321997-07-10 14:31:32 +000059 struct
60 {
61 int num;
62 int level;
Guido van Rossum95e80531997-08-13 22:34:14 +000063 unsigned char *start;
64 unsigned char *end;
Guido van Rossumdb25f321997-07-10 14:31:32 +000065 } reg;
66 struct
67 {
68 int count;
69 int level;
70 int phantom;
Guido van Rossum95e80531997-08-13 22:34:14 +000071 unsigned char *code;
72 unsigned char *text;
Guido van Rossumdb25f321997-07-10 14:31:32 +000073 } fail;
74 struct
75 {
76 int num;
77 int level;
78 int count;
79 } cntr;
Guido van Rossum004c1e11997-05-09 02:35:58 +000080} item_t;
81
82#define STACK_PAGE_SIZE 256
83#define NUM_REGISTERS 256
84
85/* A 'page' of stack items. */
86
87typedef struct item_page_t
88{
Guido van Rossumdb25f321997-07-10 14:31:32 +000089 item_t items[STACK_PAGE_SIZE];
90 struct item_page_t *prev;
91 struct item_page_t *next;
Guido van Rossum004c1e11997-05-09 02:35:58 +000092} item_page_t;
93
94
95typedef struct match_state
96{
Guido van Rossumdb25f321997-07-10 14:31:32 +000097 /* The number of registers that have been pushed onto the stack
98 * since the last failure point. */
Guido van Rossum004c1e11997-05-09 02:35:58 +000099
Guido van Rossumdb25f321997-07-10 14:31:32 +0000100 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
Guido van Rossum95e80531997-08-13 22:34:14 +0000117 unsigned char *start[NUM_REGISTERS];
118 unsigned char *end[NUM_REGISTERS];
Guido van Rossumdb25f321997-07-10 14:31:32 +0000119
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;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000140} match_state;
141
Guido van Rossumdb25f321997-07-10 14:31:32 +0000142/* 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) \
174while(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
Guido van Rossum004c1e11997-05-09 02:35:58 +0000181/* Discard the top 'count' stack items. */
182
183#define STACK_DISCARD(stack, count, on_error) \
184stack.index -= count; \
185while (stack.index < 0) \
186{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000187 if (stack.current->prev == NULL) \
188 on_error; \
189 stack.current = stack.current->prev; \
190 stack.index += STACK_PAGE_SIZE; \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000191}
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) \
197if (stack.index == 0) \
198{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000199 if (stack.current->prev == NULL) \
200 on_error; \
201 stack.current = stack.current->prev; \
202 stack.index = STACK_PAGE_SIZE - 1; \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000203} \
204else \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000205{ \
206 stack.index--; \
207} \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000208top = &(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) \
214if (stack.index == STACK_PAGE_SIZE) \
215{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000216 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; \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000226} \
227top = &(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{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000235 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]); \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000247}
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) \
253if (stack.index == 0) \
254{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000255 if (stack.current->prev == NULL) \
256 on_error; \
257 top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000258} \
259else \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000260{ \
261 top = &(stack.current->items[stack.index - 1]); \
262}
Guido van Rossum004c1e11997-05-09 02:35:58 +0000263
264/* Test to see if the stack is empty */
265
266#define STACK_EMPTY(stack) ((stack.index == 0) && \
267 (stack.current->prev == NULL))
268
Guido van Rossum004c1e11997-05-09 02:35:58 +0000269/* 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) \
281if(state.changed[reg] < state.level) \
282{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000283 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++; \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000291} \
292state.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) \
298if(state.changed[reg] < state.level) \
299{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000300 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++; \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000308} \
309state.end[reg] = text
310
311#define PUSH_FAILURE(state, xcode, xtext, on_error) \
312{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000313 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++; \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000323}
324
325/* Update the last failure point with a new position in the text. */
326
Guido van Rossum004c1e11997-05-09 02:35:58 +0000327#define UPDATE_FAILURE(state, xtext, on_error) \
328{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000329 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 } \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000352}
353
354#define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \
355{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +0000356 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); \
Guido van Rossum004c1e11997-05-09 02:35:58 +0000375}
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000376
377enum regexp_compiled_ops /* opcodes for compiled regexp */
378{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000379 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) */
Guido van Rossum95e80531997-08-13 22:34:14 +0000400 Cnotsyntaxspec, /* matches if syntax code does not match (1 byte follows) */
Guido van Rossumfaf49081997-07-15 01:47:08 +0000401 Crepeat1
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000402};
403
404enum regexp_syntax_op /* syntax codes for plain and quoted characters */
405{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000406 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
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000431};
432
433static int re_compile_initialized = 0;
434static int regexp_syntax = 0;
Guido van Rossumb6775db1994-08-01 11:34:53 +0000435int re_syntax = 0; /* Exported copy of regexp_syntax */
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000436static unsigned char regexp_plain_ops[256];
437static unsigned char regexp_quoted_ops[256];
438static unsigned char regexp_precedences[Rnum_ops];
439static int regexp_context_indep_ops;
440static 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
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000445#define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000446
Guido van Rossum95e80531997-08-13 22:34:14 +0000447unsigned char re_syntax_table[256];
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000448
Guido van Rossum8102c001997-09-05 01:48:48 +0000449void re_compile_initialize()
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000450{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000451 int a;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000452
Guido van Rossumfaf49081997-07-15 01:47:08 +0000453 static int syntax_table_inited = 0;
Guido van Rossum74fb3031997-07-17 22:41:38 +0000454
Guido van Rossumfaf49081997-07-15 01:47:08 +0000455 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++)
Guido van Rossum52d68321997-08-13 03:21:14 +0000464 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;
Guido van Rossum74fb3031997-07-17 22:41:38 +0000471 re_syntax_table['_'] = Sword;
472 for (a = 9; a <= 13; a++)
473 re_syntax_table[a] = Swhitespace;
474 re_syntax_table[' '] = Swhitespace;
Guido van Rossumfaf49081997-07-15 01:47:08 +0000475 }
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;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000547}
548
Guido van Rossum8102c001997-09-05 01:48:48 +0000549int re_set_syntax(syntax)
550 int syntax;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000551{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000552 int ret;
553
554 ret = regexp_syntax;
555 regexp_syntax = syntax;
556 re_syntax = syntax; /* Exported copy */
557 re_compile_initialize();
558 return ret;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000559}
560
Guido van Rossum8102c001997-09-05 01:48:48 +0000561static int hex_char_to_decimal(ch)
562 int ch;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000563{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000564 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;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000571}
572
Guido van Rossum8102c001997-09-05 01:48:48 +0000573static 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;
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000583{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000584 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 (;;)
Guido van Rossum74fb3031997-07-17 22:41:38 +0000592 switch (code[pos++]) {
Guido van Rossumfaf49081997-07-15 01:47:08 +0000593 case Cend:
Guido van Rossum74fb3031997-07-17 22:41:38 +0000594 {
595 *can_be_null = 1;
596 return;
597 }
Guido van Rossumfaf49081997-07-15 01:47:08 +0000598 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++)
Guido van Rossume59d3f81997-12-02 20:39:23 +0000614 if (SYNTAX(a) & syntaxcode)
Guido van Rossumfaf49081997-07-15 01:47:08 +0000615 fastmap[a] = 1;
616 return;
617 }
618 case Cnotsyntaxspec:
619 {
620 syntaxcode = code[pos++];
621 for (a = 0; a < 256; a++)
Guido van Rossume59d3f81997-12-02 20:39:23 +0000622 if (!(SYNTAX(a) & syntaxcode) )
Guido van Rossumfaf49081997-07-15 01:47:08 +0000623 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 {
Guido van Rossum95e80531997-08-13 22:34:14 +0000702 PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
703 return;
Guido van Rossumfaf49081997-07-15 01:47:08 +0000704 /*NOTREACHED*/
705 }
706 }
Guido van Rossum004c1e11997-05-09 02:35:58 +0000707}
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000708
Guido van Rossum8102c001997-09-05 01:48:48 +0000709static 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;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000719{
Guido van Rossum95e80531997-08-13 22:34:14 +0000720 unsigned char small_visited[512], *visited;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000721
Guido van Rossumfaf49081997-07-15 01:47:08 +0000722 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;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000737}
Guido van Rossumb674c3b1992-01-19 16:32:47 +0000738
Guido van Rossum8102c001997-09-05 01:48:48 +0000739void re_compile_fastmap(bufp)
740 regexp_t bufp;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000741{
Guido van Rossumfaf49081997-07-15 01:47:08 +0000742 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;
Guido van Rossum95e80531997-08-13 22:34:14 +0000751 if (PyErr_Occurred()) return;
Guido van Rossumfaf49081997-07-15 01:47:08 +0000752 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;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000760}
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
Guido van Rossum8102c001997-09-05 01:48:48 +0000785static int re_optimize_star_jump(bufp, code)
786 regexp_t bufp;
787 unsigned char *code;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000788{
Guido van Rossum95e80531997-08-13 22:34:14 +0000789 unsigned char map[256];
790 unsigned char can_be_null;
791 unsigned char *p1;
792 unsigned char *p2;
793 unsigned char ch;
Guido van Rossumfaf49081997-07-15 01:47:08 +0000794 int a;
795 int b;
796 int num_instructions = 0;
Guido van Rossum95e80531997-08-13 22:34:14 +0000797
Guido van Rossumfaf49081997-07-15 01:47:08 +0000798 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 */
Guido van Rossum95e80531997-08-13 22:34:14 +0000803 /* 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
Guido van Rossumfaf49081997-07-15 01:47:08 +0000810 assert(p1[-3] == Cfailure_jump);
811 p2 = code;
812 /* p1 points inside loop, p2 points to after loop */
813 if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
814 p2 - bufp->buffer, &can_be_null, map))
815 goto make_normal_jump;
816
817 /* If we might introduce a new update point inside the
818 * loop, we can't optimize because then update_jump would
819 * update a wrong failure point. Thus we have to be
820 * quite careful here.
821 */
822
823 /* loop until we find something that consumes a character */
Guido van Rossum004c1e11997-05-09 02:35:58 +0000824 loop_p1:
Guido van Rossumfaf49081997-07-15 01:47:08 +0000825 num_instructions++;
826 switch (*p1++)
827 {
828 case Cbol:
829 case Ceol:
830 case Cbegbuf:
831 case Cendbuf:
832 case Cwordbeg:
833 case Cwordend:
834 case Cwordbound:
835 case Cnotwordbound:
836 {
837 goto loop_p1;
838 }
839 case Cstart_memory:
840 case Cend_memory:
841 {
842 p1++;
843 goto loop_p1;
844 }
845 case Cexact:
846 {
847 ch = (unsigned char)*p1++;
848 if (map[(int)ch])
849 goto make_normal_jump;
850 break;
851 }
852 case Canychar:
853 {
854 for (b = 0; b < 256; b++)
855 if (b != '\n' && map[b])
856 goto make_normal_jump;
857 break;
858 }
859 case Cset:
860 {
861 for (b = 0; b < 256; b++)
862 if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
863 goto make_normal_jump;
864 p1 += 256/8;
865 break;
866 }
867 default:
868 {
869 goto make_normal_jump;
870 }
871 }
872 /* now we know that we can't backtrack. */
873 while (p1 != p2 - 3)
874 {
875 num_instructions++;
876 switch (*p1++)
877 {
878 case Cend:
879 {
880 return 0;
881 }
882 case Cbol:
883 case Ceol:
884 case Canychar:
885 case Cbegbuf:
886 case Cendbuf:
887 case Cwordbeg:
888 case Cwordend:
889 case Cwordbound:
890 case Cnotwordbound:
891 {
892 break;
893 }
894 case Cset:
895 {
896 p1 += 256/8;
897 break;
898 }
899 case Cexact:
900 case Cstart_memory:
901 case Cend_memory:
902 case Cmatch_memory:
903 case Csyntaxspec:
904 case Cnotsyntaxspec:
905 {
906 p1++;
907 break;
908 }
909 case Cjump:
910 case Cstar_jump:
911 case Cfailure_jump:
912 case Cupdate_failure_jump:
913 case Cdummy_failure_jump:
914 {
915 goto make_normal_jump;
916 }
917 default:
918 {
919 return 0;
Guido van Rossumfaf49081997-07-15 01:47:08 +0000920 }
921 }
922 }
923
Guido van Rossum95e80531997-08-13 22:34:14 +0000924 /* make_update_jump: */
Guido van Rossumfaf49081997-07-15 01:47:08 +0000925 code -= 3;
926 a += 3; /* jump to after the Cfailure_jump */
927 code[0] = Cupdate_failure_jump;
928 code[1] = a & 0xff;
929 code[2] = a >> 8;
930 if (num_instructions > 1)
931 return 1;
932 assert(num_instructions == 1);
933 /* if the only instruction matches a single character, we can do
934 * better */
935 p1 = code + 3 + a; /* start of sole instruction */
936 if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
937 *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
938 code[0] = Crepeat1;
939 return 1;
940
Guido van Rossum004c1e11997-05-09 02:35:58 +0000941 make_normal_jump:
Guido van Rossumfaf49081997-07-15 01:47:08 +0000942 code -= 3;
943 *code = Cjump;
944 return 1;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000945}
946
Guido van Rossum8102c001997-09-05 01:48:48 +0000947static int re_optimize(bufp)
948 regexp_t bufp;
Guido van Rossum004c1e11997-05-09 02:35:58 +0000949{
Guido van Rossum95e80531997-08-13 22:34:14 +0000950 unsigned char *code;
Guido van Rossumfaf49081997-07-15 01:47:08 +0000951
952 code = bufp->buffer;
953
954 while(1)
955 {
956 switch (*code++)
957 {
958 case Cend:
959 {
960 return 1;
961 }
962 case Canychar:
963 case Cbol:
964 case Ceol:
965 case Cbegbuf:
966 case Cendbuf:
967 case Cwordbeg:
968 case Cwordend:
969 case Cwordbound:
970 case Cnotwordbound:
971 {
972 break;
973 }
974 case Cset:
975 {
976 code += 256/8;
977 break;
978 }
979 case Cexact:
980 case Cstart_memory:
981 case Cend_memory:
982 case Cmatch_memory:
983 case Csyntaxspec:
984 case Cnotsyntaxspec:
985 {
986 code++;
987 break;
988 }
989 case Cstar_jump:
990 {
991 if (!re_optimize_star_jump(bufp, code))
992 {
993 return 0;
994 }
995 /* fall through */
996 }
997 case Cupdate_failure_jump:
998 case Cjump:
999 case Cdummy_failure_jump:
1000 case Cfailure_jump:
1001 case Crepeat1:
1002 {
1003 code += 2;
1004 break;
1005 }
1006 default:
1007 {
1008 return 0;
1009 }
1010 }
1011 }
Guido van Rossum004c1e11997-05-09 02:35:58 +00001012}
1013
1014#define NEXTCHAR(var) \
1015{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001016 if (pos >= size) \
1017 goto ends_prematurely; \
1018 (var) = regex[pos]; \
1019 pos++; \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001020}
1021
1022#define ALLOC(amount) \
1023{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001024 if (pattern_offset+(amount) > alloc) \
1025 { \
1026 alloc += 256 + (amount); \
1027 pattern = realloc(pattern, alloc); \
1028 if (!pattern) \
1029 goto out_of_memory; \
1030 } \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001031}
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001032
1033#define STORE(ch) pattern[pattern_offset++] = (ch)
1034
1035#define CURRENT_LEVEL_START (starts[starts_base + current_level])
1036
1037#define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
1038
Guido van Rossum004c1e11997-05-09 02:35:58 +00001039#define PUSH_LEVEL_STARTS \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001040if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
1041 starts_base += NUM_LEVELS; \
1042else \
1043 goto too_complex \
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001044
1045#define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
1046
Guido van Rossum004c1e11997-05-09 02:35:58 +00001047#define PUT_ADDR(offset,addr) \
1048{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001049 int disp = (addr) - (offset) - 2; \
1050 pattern[(offset)] = disp & 0xff; \
1051 pattern[(offset)+1] = (disp>>8) & 0xff; \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001052}
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001053
Guido van Rossum004c1e11997-05-09 02:35:58 +00001054#define INSERT_JUMP(pos,type,addr) \
1055{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001056 int a, p = (pos), t = (type), ad = (addr); \
1057 for (a = pattern_offset - 1; a >= p; a--) \
1058 pattern[a + 3] = pattern[a]; \
1059 pattern[p] = t; \
1060 PUT_ADDR(p+1,ad); \
1061 pattern_offset += 3; \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001062}
Guido van Rossumfaf49081997-07-15 01:47:08 +00001063
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001064#define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
1065
Guido van Rossum004c1e11997-05-09 02:35:58 +00001066#define SET_FIELDS \
1067{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001068 bufp->allocated = alloc; \
1069 bufp->buffer = pattern; \
1070 bufp->used = pattern_offset; \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001071}
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001072
Guido van Rossum004c1e11997-05-09 02:35:58 +00001073#define GETHEX(var) \
1074{ \
Guido van Rossum95e80531997-08-13 22:34:14 +00001075 unsigned char gethex_ch, gethex_value; \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001076 NEXTCHAR(gethex_ch); \
1077 gethex_value = hex_char_to_decimal(gethex_ch); \
1078 if (gethex_value == 16) \
1079 goto hex_error; \
1080 NEXTCHAR(gethex_ch); \
1081 gethex_ch = hex_char_to_decimal(gethex_ch); \
1082 if (gethex_ch == 16) \
1083 goto hex_error; \
1084 (var) = gethex_value * 16 + gethex_ch; \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001085}
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001086
Guido van Rossumfaf49081997-07-15 01:47:08 +00001087#define ANSI_TRANSLATE(ch) \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001088{ \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001089 switch (ch) \
1090 { \
1091 case 'a': \
1092 case 'A': \
1093 { \
1094 ch = 7; /* audible bell */ \
1095 break; \
1096 } \
1097 case 'b': \
1098 case 'B': \
1099 { \
1100 ch = 8; /* backspace */ \
1101 break; \
1102 } \
1103 case 'f': \
1104 case 'F': \
1105 { \
1106 ch = 12; /* form feed */ \
1107 break; \
1108 } \
1109 case 'n': \
1110 case 'N': \
1111 { \
1112 ch = 10; /* line feed */ \
1113 break; \
1114 } \
1115 case 'r': \
1116 case 'R': \
1117 { \
1118 ch = 13; /* carriage return */ \
1119 break; \
1120 } \
1121 case 't': \
1122 case 'T': \
1123 { \
1124 ch = 9; /* tab */ \
1125 break; \
1126 } \
1127 case 'v': \
1128 case 'V': \
1129 { \
1130 ch = 11; /* vertical tab */ \
1131 break; \
1132 } \
1133 case 'x': /* hex code */ \
1134 case 'X': \
1135 { \
1136 GETHEX(ch); \
1137 break; \
1138 } \
1139 default: \
1140 { \
1141 /* other characters passed through */ \
1142 if (translate) \
1143 ch = translate[(unsigned char)ch]; \
1144 break; \
1145 } \
1146 } \
Guido van Rossum004c1e11997-05-09 02:35:58 +00001147}
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001148
Guido van Rossum8102c001997-09-05 01:48:48 +00001149char *re_compile_pattern(regex, size, bufp)
1150 unsigned char *regex;
1151 int size;
1152 regexp_t bufp;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001153{
Guido van Rossumfaf49081997-07-15 01:47:08 +00001154 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';
Guido van Rossum95e80531997-08-13 22:34:14 +00001166 unsigned char *pattern;
1167 unsigned char *translate;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001168 int next_register;
1169 int paren_depth;
1170 int num_open_registers;
1171 int open_registers[RE_NREGS];
1172 int beginning_context;
1173
1174 if (!re_compile_initialized)
1175 re_compile_initialize();
1176 bufp->used = 0;
1177 bufp->fastmap_accurate = 0;
1178 bufp->uses_registers = 1;
1179 bufp->num_registers = 1;
1180 translate = bufp->translate;
1181 pattern = bufp->buffer;
1182 alloc = bufp->allocated;
1183 if (alloc == 0 || pattern == NULL)
1184 {
1185 alloc = 256;
1186 pattern = malloc(alloc);
1187 if (!pattern)
1188 goto out_of_memory;
1189 }
1190 pattern_offset = 0;
1191 starts_base = 0;
1192 num_jumps = 0;
1193 current_level = 0;
1194 SET_LEVEL_START;
1195 num_open_registers = 0;
1196 next_register = 1;
1197 paren_depth = 0;
1198 beginning_context = 1;
1199 op = -1;
1200 /* we use Rend dummy to ensure that pending jumps are updated
1201 (due to low priority of Rend) before exiting the loop. */
1202 pos = 0;
1203 while (op != Rend)
1204 {
1205 if (pos >= size)
1206 op = Rend;
1207 else
1208 {
1209 NEXTCHAR(ch);
1210 if (translate)
1211 ch = translate[(unsigned char)ch];
1212 op = regexp_plain_ops[(unsigned char)ch];
1213 if (op == Rquote)
1214 {
1215 NEXTCHAR(ch);
1216 op = regexp_quoted_ops[(unsigned char)ch];
1217 if (op == Rnormal && regexp_ansi_sequences)
1218 ANSI_TRANSLATE(ch);
1219 }
1220 }
1221 level = regexp_precedences[op];
1222 /* printf("ch='%c' op=%d level=%d current_level=%d
1223 curlevstart=%d\n", ch, op, level, current_level,
1224 CURRENT_LEVEL_START); */
1225 if (level > current_level)
1226 {
1227 for (current_level++; current_level < level; current_level++)
1228 SET_LEVEL_START;
1229 SET_LEVEL_START;
1230 }
1231 else
1232 if (level < current_level)
1233 {
1234 current_level = level;
1235 for (;num_jumps > 0 &&
1236 future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
1237 num_jumps--)
1238 PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
1239 }
1240 switch (op)
1241 {
1242 case Rend:
1243 {
1244 break;
1245 }
1246 case Rnormal:
1247 {
1248 normal_char:
1249 opcode = Cexact;
1250 store_opcode_and_arg: /* opcode & ch must be set */
1251 SET_LEVEL_START;
1252 ALLOC(2);
1253 STORE(opcode);
1254 STORE(ch);
1255 break;
1256 }
1257 case Ranychar:
1258 {
1259 opcode = Canychar;
1260 store_opcode:
1261 SET_LEVEL_START;
1262 ALLOC(1);
1263 STORE(opcode);
1264 break;
1265 }
1266 case Rquote:
1267 {
1268 abort();
1269 /*NOTREACHED*/
1270 }
1271 case Rbol:
1272 {
Guido van Rossum730806d1998-04-10 22:27:42 +00001273 if (!beginning_context) {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001274 if (regexp_context_indep_ops)
1275 goto op_error;
1276 else
1277 goto normal_char;
Guido van Rossum730806d1998-04-10 22:27:42 +00001278 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001279 opcode = Cbol;
1280 goto store_opcode;
1281 }
1282 case Reol:
1283 {
1284 if (!((pos >= size) ||
1285 ((regexp_syntax & RE_NO_BK_VBAR) ?
1286 (regex[pos] == '\174') :
1287 (pos+1 < size && regex[pos] == '\134' &&
1288 regex[pos+1] == '\174')) ||
1289 ((regexp_syntax & RE_NO_BK_PARENS)?
1290 (regex[pos] == ')'):
1291 (pos+1 < size && regex[pos] == '\134' &&
Guido van Rossum730806d1998-04-10 22:27:42 +00001292 regex[pos+1] == ')')))) {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001293 if (regexp_context_indep_ops)
1294 goto op_error;
1295 else
1296 goto normal_char;
Guido van Rossum730806d1998-04-10 22:27:42 +00001297 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001298 opcode = Ceol;
1299 goto store_opcode;
1300 /* NOTREACHED */
1301 break;
1302 }
1303 case Roptional:
1304 {
Guido van Rossum730806d1998-04-10 22:27:42 +00001305 if (beginning_context) {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001306 if (regexp_context_indep_ops)
1307 goto op_error;
1308 else
1309 goto normal_char;
Guido van Rossum730806d1998-04-10 22:27:42 +00001310 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001311 if (CURRENT_LEVEL_START == pattern_offset)
1312 break; /* ignore empty patterns for ? */
1313 ALLOC(3);
1314 INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1315 pattern_offset + 3);
1316 break;
1317 }
1318 case Rstar:
1319 case Rplus:
1320 {
Guido van Rossum730806d1998-04-10 22:27:42 +00001321 if (beginning_context) {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001322 if (regexp_context_indep_ops)
1323 goto op_error;
1324 else
1325 goto normal_char;
Guido van Rossum730806d1998-04-10 22:27:42 +00001326 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001327 if (CURRENT_LEVEL_START == pattern_offset)
1328 break; /* ignore empty patterns for + and * */
1329 ALLOC(9);
1330 INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1331 pattern_offset + 6);
1332 INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
1333 if (op == Rplus) /* jump over initial failure_jump */
1334 INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
1335 CURRENT_LEVEL_START + 6);
1336 break;
1337 }
1338 case Ror:
1339 {
1340 ALLOC(6);
1341 INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1342 pattern_offset + 6);
1343 if (num_jumps >= MAX_NESTING)
1344 goto too_complex;
1345 STORE(Cjump);
1346 future_jumps[num_jumps++] = pattern_offset;
1347 STORE(0);
1348 STORE(0);
1349 SET_LEVEL_START;
1350 break;
1351 }
1352 case Ropenpar:
1353 {
1354 SET_LEVEL_START;
1355 if (next_register < RE_NREGS)
1356 {
1357 bufp->uses_registers = 1;
1358 ALLOC(2);
1359 STORE(Cstart_memory);
1360 STORE(next_register);
1361 open_registers[num_open_registers++] = next_register;
1362 bufp->num_registers++;
1363 next_register++;
1364 }
1365 paren_depth++;
1366 PUSH_LEVEL_STARTS;
1367 current_level = 0;
1368 SET_LEVEL_START;
1369 break;
1370 }
1371 case Rclosepar:
1372 {
1373 if (paren_depth <= 0)
1374 goto parenthesis_error;
1375 POP_LEVEL_STARTS;
1376 current_level = regexp_precedences[Ropenpar];
1377 paren_depth--;
1378 if (paren_depth < num_open_registers)
1379 {
1380 bufp->uses_registers = 1;
1381 ALLOC(2);
1382 STORE(Cend_memory);
1383 num_open_registers--;
1384 STORE(open_registers[num_open_registers]);
1385 }
1386 break;
1387 }
1388 case Rmemory:
1389 {
1390 if (ch == '0')
1391 goto bad_match_register;
1392 assert(ch >= '0' && ch <= '9');
1393 bufp->uses_registers = 1;
1394 opcode = Cmatch_memory;
1395 ch -= '0';
1396 goto store_opcode_and_arg;
1397 }
1398 case Rextended_memory:
1399 {
1400 NEXTCHAR(ch);
1401 if (ch < '0' || ch > '9')
1402 goto bad_match_register;
1403 NEXTCHAR(a);
1404 if (a < '0' || a > '9')
1405 goto bad_match_register;
1406 ch = 10 * (a - '0') + ch - '0';
1407 if (ch <= 0 || ch >= RE_NREGS)
1408 goto bad_match_register;
1409 bufp->uses_registers = 1;
1410 opcode = Cmatch_memory;
1411 goto store_opcode_and_arg;
1412 }
1413 case Ropenset:
1414 {
1415 int complement;
1416 int prev;
1417 int offset;
1418 int range;
1419 int firstchar;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001420
Guido van Rossumfaf49081997-07-15 01:47:08 +00001421 SET_LEVEL_START;
1422 ALLOC(1+256/8);
1423 STORE(Cset);
1424 offset = pattern_offset;
1425 for (a = 0; a < 256/8; a++)
1426 STORE(0);
1427 NEXTCHAR(ch);
1428 if (translate)
1429 ch = translate[(unsigned char)ch];
1430 if (ch == '\136')
1431 {
1432 complement = 1;
1433 NEXTCHAR(ch);
1434 if (translate)
1435 ch = translate[(unsigned char)ch];
1436 }
1437 else
1438 complement = 0;
1439 prev = -1;
1440 range = 0;
1441 firstchar = 1;
1442 while (ch != '\135' || firstchar)
1443 {
1444 firstchar = 0;
1445 if (regexp_ansi_sequences && ch == '\134')
1446 {
1447 NEXTCHAR(ch);
1448 ANSI_TRANSLATE(ch);
1449 }
1450 if (range)
1451 {
1452 for (a = prev; a <= (int)ch; a++)
1453 SETBIT(pattern, offset, a);
1454 prev = -1;
1455 range = 0;
1456 }
1457 else
1458 if (prev != -1 && ch == '-')
1459 range = 1;
1460 else
1461 {
1462 SETBIT(pattern, offset, ch);
1463 prev = ch;
1464 }
1465 NEXTCHAR(ch);
1466 if (translate)
1467 ch = translate[(unsigned char)ch];
1468 }
1469 if (range)
1470 SETBIT(pattern, offset, '-');
1471 if (complement)
1472 {
1473 for (a = 0; a < 256/8; a++)
1474 pattern[offset+a] ^= 0xff;
1475 }
1476 break;
1477 }
1478 case Rbegbuf:
1479 {
1480 opcode = Cbegbuf;
1481 goto store_opcode;
1482 }
1483 case Rendbuf:
1484 {
1485 opcode = Cendbuf;
1486 goto store_opcode;
1487 }
1488 case Rwordchar:
1489 {
1490 opcode = Csyntaxspec;
1491 ch = Sword;
1492 goto store_opcode_and_arg;
1493 }
1494 case Rnotwordchar:
1495 {
1496 opcode = Cnotsyntaxspec;
1497 ch = Sword;
1498 goto store_opcode_and_arg;
1499 }
1500 case Rwordbeg:
1501 {
1502 opcode = Cwordbeg;
1503 goto store_opcode;
1504 }
1505 case Rwordend:
1506 {
1507 opcode = Cwordend;
1508 goto store_opcode;
1509 }
1510 case Rwordbound:
1511 {
1512 opcode = Cwordbound;
1513 goto store_opcode;
1514 }
1515 case Rnotwordbound:
1516 {
1517 opcode = Cnotwordbound;
1518 goto store_opcode;
1519 }
1520 default:
1521 {
1522 abort();
1523 }
1524 }
1525 beginning_context = (op == Ropenpar || op == Ror);
1526 }
1527 if (starts_base != 0)
1528 goto parenthesis_error;
1529 assert(num_jumps == 0);
1530 ALLOC(1);
1531 STORE(Cend);
1532 SET_FIELDS;
1533 if(!re_optimize(bufp))
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001534 return "Optimization error";
Guido van Rossumfaf49081997-07-15 01:47:08 +00001535 return NULL;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001536
Guido van Rossum004c1e11997-05-09 02:35:58 +00001537 op_error:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001538 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001539 return "Badly placed special character";
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001540
Guido van Rossum004c1e11997-05-09 02:35:58 +00001541 bad_match_register:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001542 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001543 return "Bad match register number";
Guido van Rossum004c1e11997-05-09 02:35:58 +00001544
1545 hex_error:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001546 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001547 return "Bad hexadecimal number";
Guido van Rossum004c1e11997-05-09 02:35:58 +00001548
1549 parenthesis_error:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001550 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001551 return "Badly placed parenthesis";
Guido van Rossum004c1e11997-05-09 02:35:58 +00001552
1553 out_of_memory:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001554 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001555 return "Out of memory";
Guido van Rossum004c1e11997-05-09 02:35:58 +00001556
1557 ends_prematurely:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001558 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001559 return "Regular expression ends prematurely";
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001560
Guido van Rossum004c1e11997-05-09 02:35:58 +00001561 too_complex:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001562 SET_FIELDS;
Guido van Rossumd19c04a1997-09-03 00:47:36 +00001563 return "Regular expression too complex";
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001564}
Guido van Rossum004c1e11997-05-09 02:35:58 +00001565
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001566#undef CHARAT
1567#undef NEXTCHAR
1568#undef GETHEX
1569#undef ALLOC
1570#undef STORE
1571#undef CURRENT_LEVEL_START
1572#undef SET_LEVEL_START
1573#undef PUSH_LEVEL_STARTS
1574#undef POP_LEVEL_STARTS
1575#undef PUT_ADDR
1576#undef INSERT_JUMP
1577#undef SETBIT
1578#undef SET_FIELDS
1579
Guido van Rossum004c1e11997-05-09 02:35:58 +00001580#define PREFETCH if (text == textend) goto fail
1581
1582#define NEXTCHAR(var) \
1583PREFETCH; \
1584var = (unsigned char)*text++; \
1585if (translate) \
Guido van Rossumfaf49081997-07-15 01:47:08 +00001586 var = translate[var]
Guido van Rossum004c1e11997-05-09 02:35:58 +00001587
Guido van Rossum8102c001997-09-05 01:48:48 +00001588int re_match(bufp,
1589 string,
1590 size,
1591 pos,
1592 old_regs)
1593 regexp_t bufp;
1594 unsigned char *string;
1595 int size;
1596 int pos;
1597 regexp_registers_t old_regs;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001598{
Guido van Rossum95e80531997-08-13 22:34:14 +00001599 unsigned char *code;
1600 unsigned char *translate;
1601 unsigned char *text;
1602 unsigned char *textstart;
1603 unsigned char *textend;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001604 int a;
1605 int b;
1606 int ch;
1607 int reg;
1608 int match_end;
Guido van Rossum95e80531997-08-13 22:34:14 +00001609 unsigned char *regstart;
1610 unsigned char *regend;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001611 int regsize;
1612 match_state state;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001613
Guido van Rossumfaf49081997-07-15 01:47:08 +00001614 assert(pos >= 0 && size >= 0);
1615 assert(pos <= size);
Guido van Rossum004c1e11997-05-09 02:35:58 +00001616
Guido van Rossumfaf49081997-07-15 01:47:08 +00001617 text = string + pos;
1618 textstart = string;
1619 textend = string + size;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001620
Guido van Rossumfaf49081997-07-15 01:47:08 +00001621 code = bufp->buffer;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001622
Guido van Rossumfaf49081997-07-15 01:47:08 +00001623 translate = bufp->translate;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001624
Guido van Rossumfaf49081997-07-15 01:47:08 +00001625 NEW_STATE(state, bufp->num_registers);
1626
Guido van Rossum004c1e11997-05-09 02:35:58 +00001627 continue_matching:
Guido van Rossumfaf49081997-07-15 01:47:08 +00001628 switch (*code++)
Guido van Rossumb674c3b1992-01-19 16:32:47 +00001629 {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001630 case Cend:
Guido van Rossum004c1e11997-05-09 02:35:58 +00001631 {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001632 match_end = text - textstart;
1633 if (old_regs)
1634 {
1635 old_regs->start[0] = pos;
1636 old_regs->end[0] = match_end;
1637 if (!bufp->uses_registers)
1638 {
1639 for (a = 1; a < RE_NREGS; a++)
1640 {
1641 old_regs->start[a] = -1;
1642 old_regs->end[a] = -1;
1643 }
1644 }
1645 else
1646 {
1647 for (a = 1; a < bufp->num_registers; a++)
1648 {
1649 if ((GET_REG_START(state, a) == NULL) ||
1650 (GET_REG_END(state, a) == NULL))
1651 {
1652 old_regs->start[a] = -1;
1653 old_regs->end[a] = -1;
1654 continue;
1655 }
1656 old_regs->start[a] = GET_REG_START(state, a) - textstart;
1657 old_regs->end[a] = GET_REG_END(state, a) - textstart;
1658 }
1659 for (; a < RE_NREGS; a++)
1660 {
1661 old_regs->start[a] = -1;
1662 old_regs->end[a] = -1;
1663 }
1664 }
1665 }
1666 FREE_STATE(state);
1667 return match_end - pos;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001668 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001669 case Cbol:
1670 {
1671 if (text == textstart || text[-1] == '\n')
1672 goto continue_matching;
1673 goto fail;
1674 }
1675 case Ceol:
1676 {
1677 if (text == textend || *text == '\n')
1678 goto continue_matching;
1679 goto fail;
1680 }
1681 case Cset:
1682 {
1683 NEXTCHAR(ch);
1684 if (code[ch/8] & (1<<(ch & 7)))
1685 {
1686 code += 256/8;
1687 goto continue_matching;
1688 }
1689 goto fail;
1690 }
1691 case Cexact:
1692 {
1693 NEXTCHAR(ch);
1694 if (ch != (unsigned char)*code++)
1695 goto fail;
1696 goto continue_matching;
1697 }
1698 case Canychar:
1699 {
1700 NEXTCHAR(ch);
1701 if (ch == '\n')
1702 goto fail;
1703 goto continue_matching;
1704 }
1705 case Cstart_memory:
1706 {
1707 reg = *code++;
1708 SET_REG_START(state, reg, text, goto error);
1709 goto continue_matching;
1710 }
1711 case Cend_memory:
1712 {
1713 reg = *code++;
1714 SET_REG_END(state, reg, text, goto error);
1715 goto continue_matching;
1716 }
1717 case Cmatch_memory:
1718 {
1719 reg = *code++;
1720 regstart = GET_REG_START(state, reg);
1721 regend = GET_REG_END(state, reg);
1722 if ((regstart == NULL) || (regend == NULL))
1723 goto fail; /* or should we just match nothing? */
1724 regsize = regend - regstart;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001725
Guido van Rossumfaf49081997-07-15 01:47:08 +00001726 if (regsize > (textend - text))
1727 goto fail;
1728 if(translate)
1729 {
1730 for (; regstart < regend; regstart++, text++)
1731 if (translate[*regstart] != translate[*text])
1732 goto fail;
1733 }
1734 else
1735 for (; regstart < regend; regstart++, text++)
1736 if (*regstart != *text)
1737 goto fail;
1738 goto continue_matching;
Guido van Rossum004c1e11997-05-09 02:35:58 +00001739 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001740 case Cupdate_failure_jump:
Guido van Rossumdb25f321997-07-10 14:31:32 +00001741 {
Guido van Rossumfaf49081997-07-15 01:47:08 +00001742 UPDATE_FAILURE(state, text, goto error);
1743 /* fall to next case */
Guido van Rossumdb25f321997-07-10 14:31:32 +00001744 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001745 /* treat Cstar_jump just like Cjump if it hasn't been optimized */
1746 case Cstar_jump:
1747 case Cjump:
1748 {
1749 a = (unsigned char)*code++;
1750 a |= (unsigned char)*code++ << 8;
1751 code += (int)SHORT(a);
Guido van Rossum95e80531997-08-13 22:34:14 +00001752 if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
1753 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cjump)");
1754 FREE_STATE(state);
1755 return -2;
1756 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001757 goto continue_matching;
1758 }
1759 case Cdummy_failure_jump:
1760 {
Guido van Rossum95e80531997-08-13 22:34:14 +00001761 unsigned char *failuredest;
1762
Guido van Rossumfaf49081997-07-15 01:47:08 +00001763 a = (unsigned char)*code++;
1764 a |= (unsigned char)*code++ << 8;
1765 a = (int)SHORT(a);
1766 assert(*code == Cfailure_jump);
1767 b = (unsigned char)code[1];
1768 b |= (unsigned char)code[2] << 8;
Guido van Rossum95e80531997-08-13 22:34:14 +00001769 failuredest = code + (int)SHORT(b) + 3;
1770 if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
1771 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
1772 FREE_STATE(state);
1773 return -2;
1774 }
1775 PUSH_FAILURE(state, failuredest, NULL, goto error);
Guido van Rossumfaf49081997-07-15 01:47:08 +00001776 code += a;
Guido van Rossum95e80531997-08-13 22:34:14 +00001777 if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
1778 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)");
1779 FREE_STATE(state);
1780 return -2;
1781 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001782 goto continue_matching;
1783 }
1784 case Cfailure_jump:
1785 {
1786 a = (unsigned char)*code++;
1787 a |= (unsigned char)*code++ << 8;
1788 a = (int)SHORT(a);
Guido van Rossum95e80531997-08-13 22:34:14 +00001789 if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
1790 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)");
1791 FREE_STATE(state);
1792 return -2;
1793 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001794 PUSH_FAILURE(state, code + a, text, goto error);
1795 goto continue_matching;
1796 }
1797 case Crepeat1:
1798 {
Guido van Rossum95e80531997-08-13 22:34:14 +00001799 unsigned char *pinst;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001800 a = (unsigned char)*code++;
1801 a |= (unsigned char)*code++ << 8;
1802 a = (int)SHORT(a);
1803 pinst = code + a;
Guido van Rossum95e80531997-08-13 22:34:14 +00001804 if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
1805 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Crepeat1)");
1806 FREE_STATE(state);
1807 return -2;
1808 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001809 /* pinst is sole instruction in loop, and it matches a
1810 * single character. Since Crepeat1 was originally a
1811 * Cupdate_failure_jump, we also know that backtracking
1812 * is useless: so long as the single-character
1813 * expression matches, it must be used. Also, in the
1814 * case of +, we've already matched one character, so +
1815 * can't fail: nothing here can cause a failure. */
1816 switch (*pinst++)
1817 {
1818 case Cset:
Guido van Rossum95e80531997-08-13 22:34:14 +00001819 {
1820 if (translate)
Guido van Rossumfaf49081997-07-15 01:47:08 +00001821 {
1822 while (text < textend)
1823 {
1824 ch = translate[(unsigned char)*text];
1825 if (pinst[ch/8] & (1<<(ch & 7)))
1826 text++;
1827 else
1828 break;
1829 }
1830 }
1831 else
1832 {
1833 while (text < textend)
1834 {
1835 ch = (unsigned char)*text;
1836 if (pinst[ch/8] & (1<<(ch & 7)))
1837 text++;
1838 else
1839 break;
1840 }
1841 }
1842 break;
Guido van Rossum95e80531997-08-13 22:34:14 +00001843 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00001844 case Cexact:
1845 {
1846 ch = (unsigned char)*pinst;
1847 if (translate)
1848 {
1849 while (text < textend &&
1850 translate[(unsigned char)*text] == ch)
1851 text++;
1852 }
1853 else
1854 {
1855 while (text < textend && (unsigned char)*text == ch)
1856 text++;
1857 }
1858 break;
1859 }
1860 case Canychar:
1861 {
1862 while (text < textend && (unsigned char)*text != '\n')
1863 text++;
1864 break;
1865 }
1866 case Csyntaxspec:
1867 {
1868 a = (unsigned char)*pinst;
1869 if (translate)
1870 {
1871 while (text < textend &&
Guido van Rossume59d3f81997-12-02 20:39:23 +00001872 (SYNTAX(translate[*text]) & a) )
Guido van Rossumfaf49081997-07-15 01:47:08 +00001873 text++;
1874 }
1875 else
1876 {
Guido van Rossume59d3f81997-12-02 20:39:23 +00001877 while (text < textend && (SYNTAX(*text) & a) )
Guido van Rossumfaf49081997-07-15 01:47:08 +00001878 text++;
1879 }
1880 break;
1881 }
1882 case Cnotsyntaxspec:
1883 {
1884 a = (unsigned char)*pinst;
1885 if (translate)
1886 {
1887 while (text < textend &&
Guido van Rossume59d3f81997-12-02 20:39:23 +00001888 !(SYNTAX(translate[*text]) & a) )
Guido van Rossumfaf49081997-07-15 01:47:08 +00001889 text++;
1890 }
1891 else
1892 {
Guido van Rossume59d3f81997-12-02 20:39:23 +00001893 while (text < textend && !(SYNTAX(*text) & a) )
Guido van Rossumfaf49081997-07-15 01:47:08 +00001894 text++;
1895 }
1896 break;
1897 }
1898 default:
1899 {
Guido van Rossum95e80531997-08-13 22:34:14 +00001900 FREE_STATE(state);
1901 PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
1902 return -2;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001903 /*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;
Guido van Rossum95e80531997-08-13 22:34:14 +00001928 if (!(SYNTAX(*text) & Sword))
Guido van Rossumfaf49081997-07-15 01:47:08 +00001929 goto fail;
1930 if (text == textstart)
1931 goto continue_matching;
Guido van Rossum74fb3031997-07-17 22:41:38 +00001932 if (!(SYNTAX(text[-1]) & Sword))
Guido van Rossumfaf49081997-07-15 01:47:08 +00001933 goto continue_matching;
1934 goto fail;
1935 }
1936 case Cwordend:
1937 {
1938 if (text == textstart)
1939 goto fail;
Guido van Rossum74fb3031997-07-17 22:41:38 +00001940 if (!(SYNTAX(text[-1]) & Sword))
Guido van Rossumfaf49081997-07-15 01:47:08 +00001941 goto fail;
1942 if (text == textend)
1943 goto continue_matching;
Guido van Rossum95e80531997-08-13 22:34:14 +00001944 if (!(SYNTAX(*text) & Sword))
1945 goto continue_matching;
1946 goto fail;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001947 }
1948 case Cwordbound:
1949 {
1950 /* Note: as in gnu regexp, this also matches at the
1951 * beginning and end of buffer. */
Guido van Rossum004c1e11997-05-09 02:35:58 +00001952
Guido van Rossumfaf49081997-07-15 01:47:08 +00001953 if (text == textstart || text == textend)
1954 goto continue_matching;
Guido van Rossum74fb3031997-07-17 22:41:38 +00001955 if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
Guido van Rossumfaf49081997-07-15 01:47:08 +00001956 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;
Guido van Rossum74fb3031997-07-17 22:41:38 +00001965 if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
Guido van Rossum53665e51997-08-15 15:45:25 +00001966 goto continue_matching;
1967 goto fail;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001968 }
1969 case Csyntaxspec:
1970 {
1971 NEXTCHAR(ch);
Guido van Rossum74fb3031997-07-17 22:41:38 +00001972 if (!(SYNTAX(ch) & (unsigned char)*code++))
Guido van Rossumfaf49081997-07-15 01:47:08 +00001973 goto fail;
1974 goto continue_matching;
1975 }
1976 case Cnotsyntaxspec:
1977 {
1978 NEXTCHAR(ch);
Guido van Rossum74fb3031997-07-17 22:41:38 +00001979 if (SYNTAX(ch) & (unsigned char)*code++)
Guido van Rossum95e80531997-08-13 22:34:14 +00001980 goto fail;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001981 goto continue_matching;
1982 }
1983 default:
1984 {
Guido van Rossum95e80531997-08-13 22:34:14 +00001985 FREE_STATE(state);
1986 PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
1987 return -2;
Guido van Rossumfaf49081997-07-15 01:47:08 +00001988 /*NOTREACHED*/
1989 }
1990 }
Guido van Rossum95e80531997-08-13 22:34:14 +00001991
1992
Guido van Rossum004c1e11997-05-09 02:35:58 +00001993
Guido van Rossum3b1a57a1992-01-27 16:47:46 +00001994#if 0 /* This line is never reached --Guido */
Guido van Rossumfaf49081997-07-15 01:47:08 +00001995 abort();
Guido van Rossum5f21dd11992-01-19 16:49:14 +00001996#endif
Guido van Rossumfaf49081997-07-15 01:47:08 +00001997 /*
1998 *NOTREACHED
1999 */
Guido van Rossum95e80531997-08-13 22:34:14 +00002000
2001 /* Using "break;" in the above switch statement is equivalent to "goto fail;" */
Guido van Rossum004c1e11997-05-09 02:35:58 +00002002 fail:
Guido van Rossumfaf49081997-07-15 01:47:08 +00002003 POP_FAILURE(state, code, text, goto done_matching, goto error);
2004 goto continue_matching;
Guido van Rossum004c1e11997-05-09 02:35:58 +00002005
2006 done_matching:
2007/* if(translated != NULL) */
2008/* free(translated); */
Guido van Rossumfaf49081997-07-15 01:47:08 +00002009 FREE_STATE(state);
2010 return -1;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002011
Guido van Rossum004c1e11997-05-09 02:35:58 +00002012 error:
2013/* if (translated != NULL) */
2014/* free(translated); */
Guido van Rossumfaf49081997-07-15 01:47:08 +00002015 FREE_STATE(state);
2016 return -2;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002017}
Guido van Rossum95e80531997-08-13 22:34:14 +00002018
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002019
2020#undef PREFETCH
2021#undef NEXTCHAR
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002022
Guido van Rossum8102c001997-09-05 01:48:48 +00002023int re_search(bufp,
2024 string,
2025 size,
2026 pos,
2027 range,
2028 regs)
2029 regexp_t bufp;
2030 unsigned char *string;
2031 int size;
2032 int pos;
2033 int range;
2034 regexp_registers_t regs;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002035{
Guido van Rossum95e80531997-08-13 22:34:14 +00002036 unsigned char *fastmap;
2037 unsigned char *translate;
2038 unsigned char *text;
2039 unsigned char *partstart;
2040 unsigned char *partend;
Guido van Rossumfaf49081997-07-15 01:47:08 +00002041 int dir;
2042 int ret;
Guido van Rossum95e80531997-08-13 22:34:14 +00002043 unsigned char anchor;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002044
Guido van Rossumfaf49081997-07-15 01:47:08 +00002045 assert(size >= 0 && pos >= 0);
2046 assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002047
Guido van Rossumfaf49081997-07-15 01:47:08 +00002048 fastmap = bufp->fastmap;
2049 translate = bufp->translate;
Guido van Rossum95e80531997-08-13 22:34:14 +00002050 if (fastmap && !bufp->fastmap_accurate) {
2051 re_compile_fastmap(bufp);
2052 if (PyErr_Occurred()) return -2;
2053 }
2054
Guido van Rossumfaf49081997-07-15 01:47:08 +00002055 anchor = bufp->anchor;
2056 if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
2057 fastmap = NULL;
Guido van Rossum004c1e11997-05-09 02:35:58 +00002058
Guido van Rossumfaf49081997-07-15 01:47:08 +00002059 if (range < 0)
2060 {
2061 dir = -1;
2062 range = -range;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002063 }
Guido van Rossum004c1e11997-05-09 02:35:58 +00002064 else
Guido van Rossumfaf49081997-07-15 01:47:08 +00002065 dir = 1;
2066
Guido van Rossum730806d1998-04-10 22:27:42 +00002067 if (anchor == 2) {
Guido van Rossumfaf49081997-07-15 01:47:08 +00002068 if (pos != 0)
2069 return -1;
2070 else
2071 range = 0;
Guido van Rossum730806d1998-04-10 22:27:42 +00002072 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00002073
2074 for (; range >= 0; range--, pos += dir)
2075 {
2076 if (fastmap)
2077 {
2078 if (dir == 1)
2079 { /* searching forwards */
2080
2081 text = string + pos;
2082 partend = string + size;
2083 partstart = text;
2084 if (translate)
2085 while (text != partend &&
2086 !fastmap[(unsigned char) translate[(unsigned char)*text]])
2087 text++;
2088 else
2089 while (text != partend && !fastmap[(unsigned char)*text])
2090 text++;
2091 pos += text - partstart;
2092 range -= text - partstart;
2093 if (pos == size && bufp->can_be_null == 0)
2094 return -1;
2095 }
2096 else
2097 { /* searching backwards */
2098 text = string + pos;
2099 partstart = string + pos - range;
2100 partend = text;
2101 if (translate)
2102 while (text != partstart &&
2103 !fastmap[(unsigned char)
2104 translate[(unsigned char)*text]])
2105 text--;
2106 else
2107 while (text != partstart &&
2108 !fastmap[(unsigned char)*text])
2109 text--;
2110 pos -= partend - text;
2111 range -= partend - text;
2112 }
2113 }
2114 if (anchor == 1)
2115 { /* anchored to begline */
2116 if (pos > 0 && (string[pos - 1] != '\n'))
2117 continue;
2118 }
2119 assert(pos >= 0 && pos <= size);
2120 ret = re_match(bufp, string, size, pos, regs);
2121 if (ret >= 0)
2122 return pos;
2123 if (ret == -2)
2124 return -2;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002125 }
Guido van Rossumfaf49081997-07-15 01:47:08 +00002126 return -1;
Guido van Rossumb674c3b1992-01-19 16:32:47 +00002127}
Guido van Rossum74fb3031997-07-17 22:41:38 +00002128
2129/*
2130** Local Variables:
2131** mode: c
2132** c-file-style: "python"
2133** End:
2134*/