regexpr.c 45.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
/* regexpr.c
 *
 * Author: Tatu Ylonen <ylo@ngs.fi>
 *
 * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose is hereby granted without
 * fee, provided that the above copyright notice appear in all copies.
 * This software is provided "as is" without express or implied
 * warranty.
 *
 * Created: Thu Sep 26 17:14:05 1991 ylo
 * Last modified: Mon Nov  4 17:06:48 1991 ylo
 * Ported to Think C: 19 Jan 1992 guido@cwi.nl
 *
 * This code draws many ideas from the regular expression packages by
 * Henry Spencer of the University of Toronto and Richard Stallman of
 * the Free Software Foundation.
 *
 * Emacs-specific code and syntax table code is almost directly borrowed
 * from GNU regexp.
 *
 * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April
 * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim
 * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and
 * probably one or two others that I'm forgetting.
 *
 * $Id$ */
Guido van Rossum's avatar
Guido van Rossum committed
30

31
#include "Python.h"
Guido van Rossum's avatar
Guido van Rossum committed
32 33
#include "regexpr.h"

34 35 36 37 38 39
/* The original code blithely assumed that sizeof(short) == 2.  Not
 * always true.  Original instances of "(short)x" were replaced by
 * SHORT(x), where SHORT is #defined below.  */

#define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x))

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
/* The stack implementation is taken from an idea by Andrew Kuchling.
 * It's a doubly linked list of arrays. The advantages of this over a
 * simple linked list are that the number of mallocs required are
 * reduced. It also makes it possible to statically allocate enough
 * space so that small patterns don't ever need to call malloc.
 *
 * The advantages over a single array is that is periodically
 * realloced when more space is needed is that we avoid ever copying
 * the stack. */

/* item_t is the basic stack element.  Defined as a union of
 * structures so that both registers, failure points, and counters can
 * be pushed/popped from the stack.  There's nothing built into the
 * item to keep track of whether a certain stack item is a register, a
 * failure point, or a counter. */

typedef union item_t
{
58 59 60 61
	struct
	{
		int num;
		int level;
62 63
		unsigned char *start;
		unsigned char *end;
64 65 66 67 68 69
	} reg;
	struct
	{
		int count;
		int level;
		int phantom;
70 71
		unsigned char *code;
		unsigned char *text;
72 73 74 75 76 77 78
	} fail;
	struct
	{
		int num;
		int level;
		int count;
	} cntr;
79 80 81 82 83 84 85 86 87
} item_t;

#define STACK_PAGE_SIZE 256
#define NUM_REGISTERS 256

/* A 'page' of stack items. */

typedef struct item_page_t
{
88 89 90
	item_t items[STACK_PAGE_SIZE];
	struct item_page_t *prev;
	struct item_page_t *next;
91 92 93 94 95
} item_page_t;


typedef struct match_state
{
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
	/* The number of registers that have been pushed onto the stack
	 * since the last failure point. */

	int count;

	/* Used to control when registers need to be pushed onto the
	 * stack. */
	
	int level;
	
	/* The number of failure points on the stack. */
	
	int point;
	
	/* Storage for the registers.  Each register consists of two
	 * pointers to characters.  So register N is represented as
	 * start[N] and end[N].  The pointers must be converted to
	 * offsets from the beginning of the string before returning the
	 * registers to the calling program. */
	
116 117
	unsigned char *start[NUM_REGISTERS];
	unsigned char *end[NUM_REGISTERS];
118 119 120 121 122 123 124 125
	
	/* Keeps track of whether a register has changed recently. */
	
	int changed[NUM_REGISTERS];
	
	/* Structure to encapsulate the stack. */
	struct
	{
126
		/* index into the current page.  If index == 0 and you need
127 128 129 130 131 132 133 134 135 136 137 138
		 * to pop an item, move to the previous page and set index
		 * = STACK_PAGE_SIZE - 1.  Otherwise decrement index to
		 * push a page. If index == STACK_PAGE_SIZE and you need
		 * to push a page move to the next page and set index =
		 * 0. If there is no new next page, allocate a new page
		 * and link it in. Otherwise, increment index to push a
		 * page. */
		
		int index;
		item_page_t *current; /* Pointer to the current page. */
		item_page_t first; /* First page is statically allocated. */
	} stack;
139 140
} match_state;

141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
/* Initialize a state object */

/* #define NEW_STATE(state) \ */
/* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */
/* state.stack.current = &state.stack.first; \ */
/* state.stack.first.prev = NULL; \ */
/* state.stack.first.next = NULL; \ */
/* state.stack.index = 0; \ */
/* state.level = 1 */

#define NEW_STATE(state, nregs) \
{ \
	int i; \
	for (i = 0; i < nregs; i++) \
	{ \
		state.start[i] = NULL; \
		state.end[i] = NULL; \
		state.changed[i] = 0; \
	} \
	state.stack.current = &state.stack.first; \
	state.stack.first.prev = NULL; \
	state.stack.first.next = NULL; \
	state.stack.index = 0; \
	state.level = 1; \
	state.count = 0; \
	state.level = 0; \
	state.point = 0; \
}

/* Free any memory that might have been malloc'd */

#define FREE_STATE(state) \
while(state.stack.first.next != NULL) \
{ \
	state.stack.current = state.stack.first.next; \
	state.stack.first.next = state.stack.current->next; \
	free(state.stack.current); \
}

180 181 182 183 184 185
/* Discard the top 'count' stack items. */

#define STACK_DISCARD(stack, count, on_error) \
stack.index -= count; \
while (stack.index < 0) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
186 187 188 189
	if (stack.current->prev == NULL) \
		on_error; \
	stack.current = stack.current->prev; \
	stack.index += STACK_PAGE_SIZE; \
190 191 192 193 194 195 196 197
}

/* Store a pointer to the previous item on the stack. Used to pop an
 * item off of the stack. */

#define STACK_PREV(stack, top, on_error) \
if (stack.index == 0) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
198 199 200 201
	if (stack.current->prev == NULL) \
		on_error; \
	stack.current = stack.current->prev; \
	stack.index = STACK_PAGE_SIZE - 1; \
202 203
} \
else \
Guido van Rossum's avatar
Guido van Rossum committed
204 205 206
{ \
	stack.index--; \
} \
207 208 209 210 211 212 213 214
top = &(stack.current->items[stack.index])

/* Store a pointer to the next item on the stack. Used to push an item
 * on to the stack. */

#define STACK_NEXT(stack, top, on_error) \
if (stack.index == STACK_PAGE_SIZE) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
215 216 217 218 219 220 221 222 223 224
	if (stack.current->next == NULL) \
	{ \
		stack.current->next = (item_page_t *)malloc(sizeof(item_page_t)); \
		if (stack.current->next == NULL) \
			on_error; \
		stack.current->next->prev = stack.current; \
		stack.current->next->next = NULL; \
	} \
	stack.current = stack.current->next; \
	stack.index = 0; \
225 226 227 228 229 230 231 232 233
} \
top = &(stack.current->items[stack.index++])

/* Store a pointer to the item that is 'count' items back in the
 * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to
 * STACK_TOP(stack, top, on_error).  */

#define STACK_BACK(stack, top, count, on_error) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
234 235 236 237 238 239 240 241 242 243 244 245
	int index; \
	item_page_t *current; \
	current = stack.current; \
	index = stack.index - (count); \
	while (index < 0) \
	{ \
		if (current->prev == NULL) \
			on_error; \
		current = current->prev; \
		index += STACK_PAGE_SIZE; \
	} \
	top = &(current->items[index]); \
246 247 248 249 250 251 252 253
}

/* Store a pointer to the top item on the stack. Execute the
 * 'on_error' code if there are no items on the stack. */

#define STACK_TOP(stack, top, on_error) \
if (stack.index == 0) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
254 255 256
	if (stack.current->prev == NULL) \
		on_error; \
	top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
257 258
} \
else \
Guido van Rossum's avatar
Guido van Rossum committed
259 260 261
{ \
	top = &(stack.current->items[stack.index - 1]); \
}
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281

/* Test to see if the stack is empty */

#define STACK_EMPTY(stack) ((stack.index == 0) && \
			    (stack.current->prev == NULL))

/* Return the start of register 'reg' */

#define GET_REG_START(state, reg) (state.start[reg])

/* Return the end of register 'reg' */

#define GET_REG_END(state, reg) (state.end[reg])

/* Set the start of register 'reg'. If the state of the register needs
 * saving, push it on the stack. */

#define SET_REG_START(state, reg, text, on_error) \
if(state.changed[reg] < state.level) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
282 283 284 285 286 287 288 289
	item_t *item; \
	STACK_NEXT(state.stack, item, on_error); \
	item->reg.num = reg; \
	item->reg.start = state.start[reg]; \
	item->reg.end = state.end[reg]; \
	item->reg.level = state.changed[reg]; \
	state.changed[reg] = state.level; \
	state.count++; \
290 291 292 293 294 295 296 297 298
} \
state.start[reg] = text

/* Set the end of register 'reg'. If the state of the register needs
 * saving, push it on the stack. */

#define SET_REG_END(state, reg, text, on_error) \
if(state.changed[reg] < state.level) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
299 300 301 302 303 304 305 306
	item_t *item; \
	STACK_NEXT(state.stack, item, on_error); \
	item->reg.num = reg; \
	item->reg.start = state.start[reg]; \
	item->reg.end = state.end[reg]; \
	item->reg.level = state.changed[reg]; \
	state.changed[reg] = state.level; \
	state.count++; \
307 308 309 310 311
} \
state.end[reg] = text

#define PUSH_FAILURE(state, xcode, xtext, on_error) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
312 313 314 315 316 317 318 319 320 321
	item_t *item; \
	STACK_NEXT(state.stack, item, on_error); \
	item->fail.code = xcode; \
	item->fail.text = xtext; \
	item->fail.count = state.count; \
	item->fail.level = state.level; \
	item->fail.phantom = 0; \
	state.count = 0; \
	state.level++; \
	state.point++; \
322 323 324 325 326 327
}

/* Update the last failure point with a new position in the text. */

#define UPDATE_FAILURE(state, xtext, on_error) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
	item_t *item; \
	STACK_BACK(state.stack, item, state.count + 1, on_error); \
	if (!item->fail.phantom) \
	{ \
		item_t *item2; \
		STACK_NEXT(state.stack, item2, on_error); \
		item2->fail.code = item->fail.code; \
		item2->fail.text = xtext; \
		item2->fail.count = state.count; \
		item2->fail.level = state.level; \
		item2->fail.phantom = 1; \
		state.count = 0; \
		state.level++; \
		state.point++; \
	} \
	else \
	{ \
		STACK_DISCARD(state.stack, state.count, on_error); \
		STACK_TOP(state.stack, item, on_error); \
		item->fail.text = xtext; \
		state.count = 0; \
		state.level++; \
	} \
351 352 353 354
}

#define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
	item_t *item; \
	do \
	{ \
		while(state.count > 0) \
		{ \
			STACK_PREV(state.stack, item, on_error); \
			state.start[item->reg.num] = item->reg.start; \
			state.end[item->reg.num] = item->reg.end; \
			state.changed[item->reg.num] = item->reg.level; \
			state.count--; \
		} \
		STACK_PREV(state.stack, item, on_empty); \
		xcode = item->fail.code; \
		xtext = item->fail.text; \
		state.count = item->fail.count; \
		state.level = item->fail.level; \
		state.point--; \
	} \
	while (item->fail.text == NULL); \
374
}
Guido van Rossum's avatar
Guido van Rossum committed
375 376 377

enum regexp_compiled_ops /* opcodes for compiled regexp */
{
Guido van Rossum's avatar
Guido van Rossum committed
378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398
	Cend,		      /* end of pattern reached */
	Cbol,		      /* beginning of line */
	Ceol,		      /* end of line */
	Cset,		      /* character set.  Followed by 32 bytes of set. */
	Cexact,		      /* followed by a byte to match */
	Canychar,	      /* matches any character except newline */
	Cstart_memory,	      /* set register start addr (followed by reg number) */
	Cend_memory,	      /* set register end addr (followed by reg number) */
	Cmatch_memory,	      /* match a duplicate of reg contents (regnum follows)*/
	Cjump,		      /* followed by two bytes (lsb,msb) of displacement. */
	Cstar_jump,	      /* will change to jump/update_failure_jump at runtime */
	Cfailure_jump,	      /* jump to addr on failure */
	Cupdate_failure_jump, /* update topmost failure point and jump */
	Cdummy_failure_jump,  /* push a dummy failure point and jump */
	Cbegbuf,	      /* match at beginning of buffer */
	Cendbuf,	      /* match at end of buffer */
	Cwordbeg,	      /* match at beginning of word */
	Cwordend,	      /* match at end of word */
	Cwordbound,	      /* match if at word boundary */
	Cnotwordbound,        /* match if not at word boundary */
	Csyntaxspec,	      /* matches syntax code (1 byte follows) */
399
	Cnotsyntaxspec,       /* matches if syntax code does not match (1 byte follows) */
Guido van Rossum's avatar
Guido van Rossum committed
400
	Crepeat1
Guido van Rossum's avatar
Guido van Rossum committed
401 402 403 404
};

enum regexp_syntax_op	/* syntax codes for plain and quoted characters */
{
Guido van Rossum's avatar
Guido van Rossum committed
405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
	Rend,		  /* special code for end of regexp */
	Rnormal,	  /* normal character */
	Ranychar,	  /* any character except newline */
	Rquote,		  /* the quote character */
	Rbol,		  /* match beginning of line */
	Reol,		  /* match end of line */
	Roptional,	  /* match preceding expression optionally */
	Rstar,		  /* match preceding expr zero or more times */
	Rplus,		  /* match preceding expr one or more times */
	Ror,		  /* match either of alternatives */
	Ropenpar,	  /* opening parenthesis */
	Rclosepar,	  /* closing parenthesis */
	Rmemory,	  /* match memory register */
	Rextended_memory, /* \vnn to match registers 10-99 */
	Ropenset,	  /* open set.  Internal syntax hard-coded below. */
	/* the following are gnu extensions to "normal" regexp syntax */
	Rbegbuf,	  /* beginning of buffer */
	Rendbuf,	  /* end of buffer */
	Rwordchar,	  /* word character */
	Rnotwordchar,	  /* not word character */
	Rwordbeg,	  /* beginning of word */
	Rwordend,	  /* end of word */
	Rwordbound,	  /* word bound */
	Rnotwordbound,	  /* not word bound */
	Rnum_ops
Guido van Rossum's avatar
Guido van Rossum committed
430 431 432 433
};

static int re_compile_initialized = 0;
static int regexp_syntax = 0;
434
int re_syntax = 0; /* Exported copy of regexp_syntax */
Guido van Rossum's avatar
Guido van Rossum committed
435 436 437 438 439 440 441 442 443 444 445
static unsigned char regexp_plain_ops[256];
static unsigned char regexp_quoted_ops[256];
static unsigned char regexp_precedences[Rnum_ops];
static int regexp_context_indep_ops;
static int regexp_ansi_sequences;

#define NUM_LEVELS  5    /* number of precedence levels in use */
#define MAX_NESTING 100  /* max nesting level of operators */

#define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]

446
unsigned char re_syntax_table[256];
Guido van Rossum's avatar
Guido van Rossum committed
447

448
void re_compile_initialize(void)
Guido van Rossum's avatar
Guido van Rossum committed
449
{
Guido van Rossum's avatar
Guido van Rossum committed
450
	int a;
Guido van Rossum's avatar
Guido van Rossum committed
451
  
Guido van Rossum's avatar
Guido van Rossum committed
452
	static int syntax_table_inited = 0;
Guido van Rossum's avatar
Guido van Rossum committed
453

Guido van Rossum's avatar
Guido van Rossum committed
454 455 456 457 458 459 460 461 462
	if (!syntax_table_inited)
	{
		syntax_table_inited = 1;
		memset(re_syntax_table, 0, 256);
		for (a = 'a'; a <= 'z'; a++)
			re_syntax_table[a] = Sword;
		for (a = 'A'; a <= 'Z'; a++)
			re_syntax_table[a] = Sword;
		for (a = '0'; a <= '9'; a++)
463 464 465 466 467 468 469
			re_syntax_table[a] = Sword | Sdigit | Shexdigit;
		for (a = '0'; a <= '7'; a++)
			re_syntax_table[a] |= Soctaldigit;
		for (a = 'A'; a <= 'F'; a++)
			re_syntax_table[a] |= Shexdigit;
		for (a = 'a'; a <= 'f'; a++)
			re_syntax_table[a] |= Shexdigit;
Guido van Rossum's avatar
Guido van Rossum committed
470 471 472 473
		re_syntax_table['_'] = Sword;
		for (a = 9; a <= 13; a++)
			re_syntax_table[a] = Swhitespace;
		re_syntax_table[' '] = Swhitespace;
Guido van Rossum's avatar
Guido van Rossum committed
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
	}
	re_compile_initialized = 1;
	for (a = 0; a < 256; a++)
	{
		regexp_plain_ops[a] = Rnormal;
		regexp_quoted_ops[a] = Rnormal;
	}
	for (a = '0'; a <= '9'; a++)
		regexp_quoted_ops[a] = Rmemory;
	regexp_plain_ops['\134'] = Rquote;
	if (regexp_syntax & RE_NO_BK_PARENS)
	{
		regexp_plain_ops['('] = Ropenpar;
		regexp_plain_ops[')'] = Rclosepar;
	}
	else
	{
		regexp_quoted_ops['('] = Ropenpar;
		regexp_quoted_ops[')'] = Rclosepar;
	}
	if (regexp_syntax & RE_NO_BK_VBAR)
		regexp_plain_ops['\174'] = Ror;
	else
		regexp_quoted_ops['\174'] = Ror;
	regexp_plain_ops['*'] = Rstar;
	if (regexp_syntax & RE_BK_PLUS_QM)
	{
		regexp_quoted_ops['+'] = Rplus;
		regexp_quoted_ops['?'] = Roptional;
	}
	else
	{
		regexp_plain_ops['+'] = Rplus;
		regexp_plain_ops['?'] = Roptional;
	}
	if (regexp_syntax & RE_NEWLINE_OR)
		regexp_plain_ops['\n'] = Ror;
	regexp_plain_ops['\133'] = Ropenset;
	regexp_plain_ops['\136'] = Rbol;
	regexp_plain_ops['$'] = Reol;
	regexp_plain_ops['.'] = Ranychar;
	if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
	{
		regexp_quoted_ops['w'] = Rwordchar;
		regexp_quoted_ops['W'] = Rnotwordchar;
		regexp_quoted_ops['<'] = Rwordbeg;
		regexp_quoted_ops['>'] = Rwordend;
		regexp_quoted_ops['b'] = Rwordbound;
		regexp_quoted_ops['B'] = Rnotwordbound;
		regexp_quoted_ops['`'] = Rbegbuf;
		regexp_quoted_ops['\''] = Rendbuf;
	}
	if (regexp_syntax & RE_ANSI_HEX)
		regexp_quoted_ops['v'] = Rextended_memory;
	for (a = 0; a < Rnum_ops; a++)
		regexp_precedences[a] = 4;
	if (regexp_syntax & RE_TIGHT_VBAR)
	{
		regexp_precedences[Ror] = 3;
		regexp_precedences[Rbol] = 2;
		regexp_precedences[Reol] = 2;
	}
	else
	{
		regexp_precedences[Ror] = 2;
		regexp_precedences[Rbol] = 3;
		regexp_precedences[Reol] = 3;
	}
	regexp_precedences[Rclosepar] = 1;
	regexp_precedences[Rend] = 0;
	regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
	regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
Guido van Rossum's avatar
Guido van Rossum committed
546 547
}

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
548
int re_set_syntax(int syntax)
Guido van Rossum's avatar
Guido van Rossum committed
549
{
Guido van Rossum's avatar
Guido van Rossum committed
550 551 552 553 554 555 556
	int ret;
	
	ret = regexp_syntax;
	regexp_syntax = syntax;
	re_syntax = syntax; /* Exported copy */
	re_compile_initialize();
	return ret;
557 558
}

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
559
static int hex_char_to_decimal(int ch)
560
{
Guido van Rossum's avatar
Guido van Rossum committed
561 562 563 564 565 566 567
	if (ch >= '0' && ch <= '9')
		return ch - '0';
	if (ch >= 'a' && ch <= 'f')
		return ch - 'a' + 10;
	if (ch >= 'A' && ch <= 'F')
		return ch - 'A' + 10;
	return 16;
568
}
Guido van Rossum's avatar
Guido van Rossum committed
569

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
570 571 572 573
static void re_compile_fastmap_aux(unsigned char *code, int pos,
                                   unsigned char *visited,
                                   unsigned char *can_be_null,
                                   unsigned char *fastmap)
574
{
Guido van Rossum's avatar
Guido van Rossum committed
575 576 577 578 579 580 581 582
	int a;
	int b;
	int syntaxcode;
	
	if (visited[pos])
		return;  /* we have already been here */
	visited[pos] = 1;
	for (;;)
Guido van Rossum's avatar
Guido van Rossum committed
583
		switch (code[pos++]) {
Guido van Rossum's avatar
Guido van Rossum committed
584
		case Cend:
Guido van Rossum's avatar
Guido van Rossum committed
585 586 587 588
			{
				*can_be_null = 1;
				return;
			}
Guido van Rossum's avatar
Guido van Rossum committed
589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604
		case Cbol:
		case Cbegbuf:
		case Cendbuf:
		case Cwordbeg:
		case Cwordend:
		case Cwordbound:
		case Cnotwordbound:
		{
			for (a = 0; a < 256; a++)
				fastmap[a] = 1;
			break;
		}
		case Csyntaxspec:
		{
			syntaxcode = code[pos++];
			for (a = 0; a < 256; a++)
605
				if (SYNTAX(a) & syntaxcode) 
Guido van Rossum's avatar
Guido van Rossum committed
606 607 608 609 610 611 612
					fastmap[a] = 1;
			return;
		}
		case Cnotsyntaxspec:
		{
			syntaxcode = code[pos++];
			for (a = 0; a < 256; a++)
613
				if (!(SYNTAX(a) & syntaxcode) )
Guido van Rossum's avatar
Guido van Rossum committed
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692
					fastmap[a] = 1;
			return;
		}
		case Ceol:
		{
			fastmap['\n'] = 1;
			if (*can_be_null == 0)
				*can_be_null = 2; /* can match null, but only at end of buffer*/
			return;
		}
		case Cset:
		{
			for (a = 0; a < 256/8; a++)
				if (code[pos + a] != 0)
					for (b = 0; b < 8; b++)
						if (code[pos + a] & (1 << b))
							fastmap[(a << 3) + b] = 1;
			pos += 256/8;
			return;
		}
		case Cexact:
		{
			fastmap[(unsigned char)code[pos]] = 1;
			return;
		}
		case Canychar:
		{
			for (a = 0; a < 256; a++)
				if (a != '\n')
					fastmap[a] = 1;
			return;
		}
		case Cstart_memory:
		case Cend_memory:
		{
			pos++;
			break;
		}
		case Cmatch_memory:
		{
			for (a = 0; a < 256; a++)
				fastmap[a] = 1;
			*can_be_null = 1;
			return;
		}
		case Cjump:
		case Cdummy_failure_jump:
		case Cupdate_failure_jump:
		case Cstar_jump:
		{
			a = (unsigned char)code[pos++];
			a |= (unsigned char)code[pos++] << 8;
			pos += (int)SHORT(a);
			if (visited[pos])
			{
				/* argh... the regexp contains empty loops.  This is not
				   good, as this may cause a failure stack overflow when
				   matching.  Oh well. */
				/* this path leads nowhere; pursue other paths. */
				return;
			}
			visited[pos] = 1;
			break;
		}
		case Cfailure_jump:
		{
			a = (unsigned char)code[pos++];
			a |= (unsigned char)code[pos++] << 8;
			a = pos + (int)SHORT(a);
			re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
			break;
		}
		case Crepeat1:
		{
			pos += 2;
			break;
		}
		default:
		{
693 694
		        PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
		        return;
Guido van Rossum's avatar
Guido van Rossum committed
695 696 697
			/*NOTREACHED*/
		}
		}
Guido van Rossum's avatar
Guido van Rossum committed
698 699
}

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
700 701 702
static int re_do_compile_fastmap(unsigned char *buffer, int used, int pos,
                                 unsigned char *can_be_null,
                                 unsigned char *fastmap)
Guido van Rossum's avatar
Guido van Rossum committed
703
{
704
	unsigned char small_visited[512], *visited;
705
   
Guido van Rossum's avatar
Guido van Rossum committed
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720
	if (used <= sizeof(small_visited))
		visited = small_visited;
	else
	{
		visited = malloc(used);
		if (!visited)
			return 0;
	}
	*can_be_null = 0;
	memset(fastmap, 0, 256);
	memset(visited, 0, used);
	re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
	if (visited != small_visited)
		free(visited);
	return 1;
Guido van Rossum's avatar
Guido van Rossum committed
721 722
}

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
723
void re_compile_fastmap(regexp_t bufp)
Guido van Rossum's avatar
Guido van Rossum committed
724
{
Guido van Rossum's avatar
Guido van Rossum committed
725 726 727 728 729 730 731 732 733
	if (!bufp->fastmap || bufp->fastmap_accurate)
		return;
	assert(bufp->used > 0);
	if (!re_do_compile_fastmap(bufp->buffer,
				   bufp->used,
				   0,
				   &bufp->can_be_null,
				   bufp->fastmap))
		return;
734
	if (PyErr_Occurred()) return;
Guido van Rossum's avatar
Guido van Rossum committed
735 736 737 738 739 740 741 742
	if (bufp->buffer[0] == Cbol)
		bufp->anchor = 1;   /* begline */
	else
		if (bufp->buffer[0] == Cbegbuf)
			bufp->anchor = 2; /* begbuf */
		else
			bufp->anchor = 0; /* none */
	bufp->fastmap_accurate = 1;
743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767
}

/* 
 * star is coded as:
 * 1: failure_jump 2
 *    ... code for operand of star
 *    star_jump 1
 * 2: ... code after star
 *
 * We change the star_jump to update_failure_jump if we can determine
 * that it is safe to do so; otherwise we change it to an ordinary
 * jump.
 *
 * plus is coded as
 *
 *    jump 2
 * 1: failure_jump 3
 * 2: ... code for operand of plus
 *    star_jump 1
 * 3: ... code after plus
 *
 * For star_jump considerations this is processed identically to star.
 *
 */

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
768
static int re_optimize_star_jump(regexp_t bufp, unsigned char *code)
769
{
770 771 772 773 774
	unsigned char map[256];
	unsigned char can_be_null;
	unsigned char *p1;
	unsigned char *p2;
	unsigned char ch;
Guido van Rossum's avatar
Guido van Rossum committed
775 776 777
	int a;
	int b;
	int num_instructions = 0;
778

Guido van Rossum's avatar
Guido van Rossum committed
779 780 781 782 783
	a = (unsigned char)*code++;
	a |= (unsigned char)*code++ << 8;
	a = (int)SHORT(a);
	
	p1 = code + a + 3; /* skip the failure_jump */
784 785 786 787 788 789 790
	/* Check that the jump is within the pattern */
	if (p1<bufp->buffer || bufp->buffer+bufp->used<p1)
	  {
	    PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (failure_jump opt)");
	    return 0;
	  }
	
Guido van Rossum's avatar
Guido van Rossum committed
791 792 793 794
	assert(p1[-3] == Cfailure_jump);
	p2 = code;
	/* p1 points inside loop, p2 points to after loop */
	if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
795 796
				   (int)(p2 - bufp->buffer),
				   &can_be_null, map))
Guido van Rossum's avatar
Guido van Rossum committed
797 798 799 800 801 802 803 804 805
		goto make_normal_jump;
	
	/* If we might introduce a new update point inside the
	 * loop, we can't optimize because then update_jump would
	 * update a wrong failure point.  Thus we have to be
	 * quite careful here.
	 */
	
	/* loop until we find something that consumes a character */
806
  loop_p1:
Guido van Rossum's avatar
Guido van Rossum committed
807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
	num_instructions++;
	switch (*p1++)
	{
	case Cbol:
	case Ceol:
	case Cbegbuf:
	case Cendbuf:
	case Cwordbeg:
	case Cwordend:
	case Cwordbound:
	case Cnotwordbound:
	{
		goto loop_p1;
	}
	case Cstart_memory:
	case Cend_memory:
	{
		p1++;
		goto loop_p1;
	}
	case Cexact:
	{
		ch = (unsigned char)*p1++;
		if (map[(int)ch])
			goto make_normal_jump;
		break;
	}
	case Canychar:
	{
		for (b = 0; b < 256; b++)
			if (b != '\n' && map[b])
				goto make_normal_jump;
		break;
	}
	case Cset:
	{
		for (b = 0; b < 256; b++)
			if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
				goto make_normal_jump;
		p1 += 256/8;
		break;
	}
	default:
	{
		goto make_normal_jump;
	}
	}
	/* now we know that we can't backtrack. */
	while (p1 != p2 - 3)
	{
		num_instructions++;
		switch (*p1++)
		{
		case Cend:
		{
			return 0;
		}
		case Cbol:
		case Ceol:
		case Canychar:
		case Cbegbuf:
		case Cendbuf:
		case Cwordbeg:
		case Cwordend:
		case Cwordbound:
		case Cnotwordbound:
		{
			break;
		}
		case Cset:
		{
			p1 += 256/8;
			break;
		}
		case Cexact:
		case Cstart_memory:
		case Cend_memory:
		case Cmatch_memory:
		case Csyntaxspec:
		case Cnotsyntaxspec:
		{
			p1++;
			break;
		}
		case Cjump:
		case Cstar_jump:
		case Cfailure_jump:
		case Cupdate_failure_jump:
		case Cdummy_failure_jump:
		{
			goto make_normal_jump;
		}
		default:
		{
			return 0;
		}
		}
	}
	
906
	/* make_update_jump: */
Guido van Rossum's avatar
Guido van Rossum committed
907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922
	code -= 3;
	a += 3;  /* jump to after the Cfailure_jump */
	code[0] = Cupdate_failure_jump;
	code[1] = a & 0xff;
	code[2] = a >> 8;
	if (num_instructions > 1)
		return 1;
	assert(num_instructions == 1);
	/* if the only instruction matches a single character, we can do
	 * better */
	p1 = code + 3 + a;   /* start of sole instruction */
	if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
	    *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
		code[0] = Crepeat1;
	return 1;
	
923
  make_normal_jump:
Guido van Rossum's avatar
Guido van Rossum committed
924 925 926
	code -= 3;
	*code = Cjump;
	return 1;
927 928
}

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
929
static int re_optimize(regexp_t bufp)
930
{
931
	unsigned char *code;
Guido van Rossum's avatar
Guido van Rossum committed
932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992
	
	code = bufp->buffer;
	
	while(1)
	{
		switch (*code++)
		{
		case Cend:
		{
			return 1;
		}
		case Canychar:
		case Cbol:
		case Ceol:
		case Cbegbuf:
		case Cendbuf:
		case Cwordbeg:
		case Cwordend:
		case Cwordbound:
		case Cnotwordbound:
		{
			break;
		}
		case Cset:
		{
			code += 256/8;
			break;
		}
		case Cexact:
		case Cstart_memory:
		case Cend_memory:
		case Cmatch_memory:
		case Csyntaxspec:
		case Cnotsyntaxspec:
		{
			code++;
			break;
		}
		case Cstar_jump:
		{
			if (!re_optimize_star_jump(bufp, code))
			{
				return 0;
			}
			/* fall through */
		}
		case Cupdate_failure_jump:
		case Cjump:
		case Cdummy_failure_jump:
		case Cfailure_jump:
		case Crepeat1:
		{
			code += 2;
			break;
		}
		default:
		{
			return 0;
		}
		}
	}
993 994 995 996
}

#define NEXTCHAR(var) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
997 998 999 1000
	if (pos >= size) \
		goto ends_prematurely; \
	(var) = regex[pos]; \
	pos++; \
1001 1002 1003 1004
}

#define ALLOC(amount) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
1005 1006 1007 1008 1009 1010 1011
	  if (pattern_offset+(amount) > alloc) \
	  { \
		  alloc += 256 + (amount); \
		  pattern = realloc(pattern, alloc); \
		  if (!pattern) \
			  goto out_of_memory; \
	  } \
1012
}
Guido van Rossum's avatar
Guido van Rossum committed
1013 1014 1015 1016 1017 1018 1019

#define STORE(ch) pattern[pattern_offset++] = (ch)

#define CURRENT_LEVEL_START (starts[starts_base + current_level])

#define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset

1020
#define PUSH_LEVEL_STARTS \
Guido van Rossum's avatar
Guido van Rossum committed
1021 1022 1023 1024
if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
	starts_base += NUM_LEVELS; \
else \
	goto too_complex \
Guido van Rossum's avatar
Guido van Rossum committed
1025 1026 1027

#define POP_LEVEL_STARTS starts_base -= NUM_LEVELS

1028 1029
#define PUT_ADDR(offset,addr) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
1030 1031 1032
	int disp = (addr) - (offset) - 2; \
	pattern[(offset)] = disp & 0xff; \
	pattern[(offset)+1] = (disp>>8) & 0xff; \
1033
}
Guido van Rossum's avatar
Guido van Rossum committed
1034

1035 1036
#define INSERT_JUMP(pos,type,addr) \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
1037 1038 1039 1040 1041 1042
	int a, p = (pos), t = (type), ad = (addr); \
	for (a = pattern_offset - 1; a >= p; a--) \
		pattern[a + 3] = pattern[a]; \
	pattern[p] = t; \
	PUT_ADDR(p+1,ad); \
	pattern_offset += 3; \
1043
}
Guido van Rossum's avatar
Guido van Rossum committed
1044

Guido van Rossum's avatar
Guido van Rossum committed
1045 1046
#define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))

1047 1048
#define SET_FIELDS \
{ \
Guido van Rossum's avatar
Guido van Rossum committed
1049 1050 1051
	bufp->allocated = alloc; \
	bufp->buffer = pattern; \
	bufp->used = pattern_offset; \
1052
}
Guido van Rossum's avatar
Guido van Rossum committed
1053
    
1054 1055
#define GETHEX(var) \
{ \
1056
	unsigned char gethex_ch, gethex_value; \
Guido van Rossum's avatar
Guido van Rossum committed
1057 1058 1059 1060 1061 1062 1063 1064 1065
	NEXTCHAR(gethex_ch); \
	gethex_value = hex_char_to_decimal(gethex_ch); \
	if (gethex_value == 16) \
		goto hex_error; \
	NEXTCHAR(gethex_ch); \
	gethex_ch = hex_char_to_decimal(gethex_ch); \
	if (gethex_ch == 16) \
		goto hex_error; \
	(var) = gethex_value * 16 + gethex_ch; \
1066 1067
}

Guido van Rossum's avatar
Guido van Rossum committed
1068
#define ANSI_TRANSLATE(ch) \
1069
{ \
Guido van Rossum's avatar
Guido van Rossum committed
1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127
	switch (ch) \
	{ \
	case 'a': \
	case 'A': \
	{ \
		ch = 7; /* audible bell */ \
		break; \
	} \
	case 'b': \
	case 'B': \
	{ \
		ch = 8; /* backspace */ \
		break; \
	} \
	case 'f': \
	case 'F': \
	{ \
		ch = 12; /* form feed */ \
		break; \
	} \
	case 'n': \
	case 'N': \
	{ \
		ch = 10; /* line feed */ \
		break; \
	} \
	case 'r': \
	case 'R': \
	{ \
		ch = 13; /* carriage return */ \
		break; \
	} \
	case 't': \
	case 'T': \
	{ \
	      ch = 9; /* tab */ \
	      break; \
	} \
	case 'v': \
	case 'V': \
	{ \
		ch = 11; /* vertical tab */ \
		break; \
	} \
	case 'x': /* hex code */ \
	case 'X': \
	{ \
		GETHEX(ch); \
		break; \
	} \
	default: \
	{ \
		/* other characters passed through */ \
		if (translate) \
			ch = translate[(unsigned char)ch]; \
		break; \
	} \
	} \
1128 1129
}

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
1130
char *re_compile_pattern(unsigned char *regex, int size, regexp_t bufp)
1131
{
Guido van Rossum's avatar
Guido van Rossum committed
1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143
	int a;
	int pos;
	int op;
	int current_level;
	int level;
	int opcode;
	int pattern_offset = 0, alloc;
	int starts[NUM_LEVELS * MAX_NESTING];
	int starts_base;
	int future_jumps[MAX_NESTING];
	int num_jumps;
	unsigned char ch = '\0';
1144 1145
	unsigned char *pattern;
	unsigned char *translate;
Guido van Rossum's avatar
Guido van Rossum committed
1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245
	int next_register;
	int paren_depth;
	int num_open_registers;
	int open_registers[RE_NREGS];
	int beginning_context;
	
	if (!re_compile_initialized)
		re_compile_initialize();
	bufp->used = 0;
	bufp->fastmap_accurate = 0;
	bufp->uses_registers = 1;
	bufp->num_registers = 1;
	translate = bufp->translate;
	pattern = bufp->buffer;
	alloc = bufp->allocated;
	if (alloc == 0 || pattern == NULL)
	{
		alloc = 256;
		pattern = malloc(alloc);
		if (!pattern)
			goto out_of_memory;
	}
	pattern_offset = 0;
	starts_base = 0;
	num_jumps = 0;
	current_level = 0;
	SET_LEVEL_START;
	num_open_registers = 0;
	next_register = 1;
	paren_depth = 0;
	beginning_context = 1;
	op = -1;
	/* we use Rend dummy to ensure that pending jumps are updated
	   (due to low priority of Rend) before exiting the loop. */
	pos = 0;
	while (op != Rend)
	{
		if (pos >= size)
			op = Rend;
		else
		{
			NEXTCHAR(ch);
			if (translate)
				ch = translate[(unsigned char)ch];
			op = regexp_plain_ops[(unsigned char)ch];
			if (op == Rquote)
			{
				NEXTCHAR(ch);
				op = regexp_quoted_ops[(unsigned char)ch];
				if (op == Rnormal && regexp_ansi_sequences)
					ANSI_TRANSLATE(ch);
			}
		}
		level = regexp_precedences[op];
		/* printf("ch='%c' op=%d level=%d current_level=%d
		   curlevstart=%d\n", ch, op, level, current_level,
		   CURRENT_LEVEL_START); */
		if (level > current_level)
		{
			for (current_level++; current_level < level; current_level++)
				SET_LEVEL_START;
			SET_LEVEL_START;
		}
		else
			if (level < current_level)
			{
				current_level = level;
				for (;num_jumps > 0 &&
					     future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
				     num_jumps--)
					PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
			}
		switch (op)
		{
		case Rend:
		{
			break;
		}
		case Rnormal:
		{
		  normal_char:
			opcode = Cexact;
		  store_opcode_and_arg: /* opcode & ch must be set */
			SET_LEVEL_START;
			ALLOC(2);
			STORE(opcode);
			STORE(ch);
			break;
		}
		case Ranychar:
		{
			opcode = Canychar;
		  store_opcode:
			SET_LEVEL_START;
			ALLOC(1);
			STORE(opcode);
			break;
		}
		case Rquote:
		{
1246
			Py_FatalError("Rquote");
Guido van Rossum's avatar
Guido van Rossum committed
1247 1248 1249 1250
			/*NOTREACHED*/
		}
		case Rbol:
		{
1251
			if (!beginning_context) {
Guido van Rossum's avatar
Guido van Rossum committed
1252 1253 1254 1255
				if (regexp_context_indep_ops)
					goto op_error;
				else
					goto normal_char;
1256
			}
Guido van Rossum's avatar
Guido van Rossum committed
1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269
			opcode = Cbol;
			goto store_opcode;
		}
		case Reol:
		{
			if (!((pos >= size) ||
			      ((regexp_syntax & RE_NO_BK_VBAR) ?
			       (regex[pos] == '\174') :
			       (pos+1 < size && regex[pos] == '\134' &&
				regex[pos+1] == '\174')) ||
			      ((regexp_syntax & RE_NO_BK_PARENS)?
			       (regex[pos] == ')'):
			       (pos+1 < size && regex[pos] == '\134' &&
1270
				regex[pos+1] == ')')))) {
Guido van Rossum's avatar
Guido van Rossum committed
1271 1272 1273 1274
				if (regexp_context_indep_ops)
					goto op_error;
				else
					goto normal_char;
1275
			}
Guido van Rossum's avatar
Guido van Rossum committed
1276 1277 1278 1279 1280 1281 1282
			opcode = Ceol;
			goto store_opcode;
			/* NOTREACHED */
			break;
		}
		case Roptional:
		{
1283
			if (beginning_context) {
Guido van Rossum's avatar
Guido van Rossum committed
1284 1285 1286 1287
				if (regexp_context_indep_ops)
					goto op_error;
				else
					goto normal_char;
1288
			}
Guido van Rossum's avatar
Guido van Rossum committed
1289 1290 1291 1292 1293 1294 1295 1296 1297 1298
			if (CURRENT_LEVEL_START == pattern_offset)
				break; /* ignore empty patterns for ? */
			ALLOC(3);
			INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
				    pattern_offset + 3);
			break;
		}
		case Rstar:
		case Rplus:
		{
1299
			if (beginning_context) {
Guido van Rossum's avatar
Guido van Rossum committed
1300 1301 1302 1303
				if (regexp_context_indep_ops)
					goto op_error;
				else
					goto normal_char;
1304
			}
Guido van Rossum's avatar
Guido van Rossum committed
1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384
			if (CURRENT_LEVEL_START == pattern_offset)
				break; /* ignore empty patterns for + and * */
			ALLOC(9);
			INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
				    pattern_offset + 6);
			INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
			if (op == Rplus)  /* jump over initial failure_jump */
				INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
					    CURRENT_LEVEL_START + 6);
			break;
		}
		case Ror:
		{
			ALLOC(6);
			INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
				    pattern_offset + 6);
			if (num_jumps >= MAX_NESTING)
				goto too_complex;
			STORE(Cjump);
			future_jumps[num_jumps++] = pattern_offset;
			STORE(0);
			STORE(0);
			SET_LEVEL_START;
			break;
		}
		case Ropenpar:
		{
			SET_LEVEL_START;
			if (next_register < RE_NREGS)
			{
				bufp->uses_registers = 1;
				ALLOC(2);
				STORE(Cstart_memory);
				STORE(next_register);
				open_registers[num_open_registers++] = next_register;
				bufp->num_registers++;
				next_register++;
			}
			paren_depth++;
			PUSH_LEVEL_STARTS;
			current_level = 0;
			SET_LEVEL_START;
			break;
		}
		case Rclosepar:
		{
			if (paren_depth <= 0)
				goto parenthesis_error;
			POP_LEVEL_STARTS;
			current_level = regexp_precedences[Ropenpar];
			paren_depth--;
			if (paren_depth < num_open_registers)
			{
				bufp->uses_registers = 1;
				ALLOC(2);
				STORE(Cend_memory);
				num_open_registers--;
				STORE(open_registers[num_open_registers]);
			}
			break;
		}
		case Rmemory:
		{
			if (ch == '0')
				goto bad_match_register;
			assert(ch >= '0' && ch <= '9');
			bufp->uses_registers = 1;
			opcode = Cmatch_memory;
			ch -= '0';
			goto store_opcode_and_arg;
		}
		case Rextended_memory:
		{
			NEXTCHAR(ch);
			if (ch < '0' || ch > '9')
				goto bad_match_register;
			NEXTCHAR(a);
			if (a < '0' || a > '9')
				goto bad_match_register;
			ch = 10 * (a - '0') + ch - '0';
Fredrik Lundh's avatar
Fredrik Lundh committed
1385
			if (ch == 0 || ch >= RE_NREGS)
Guido van Rossum's avatar
Guido van Rossum committed
1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396
				goto bad_match_register;
			bufp->uses_registers = 1;
			opcode = Cmatch_memory;
			goto store_opcode_and_arg;
		}
		case Ropenset:
		{
			int complement;
			int prev;
			int offset;
			int range;
Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
1397 1398
                        int firstchar;
                        
Guido van Rossum's avatar
Guido van Rossum committed
1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511
			SET_LEVEL_START;
			ALLOC(1+256/8);
			STORE(Cset);
			offset = pattern_offset;
			for (a = 0; a < 256/8; a++)
				STORE(0);
			NEXTCHAR(ch);
			if (translate)
				ch = translate[(unsigned char)ch];
			if (ch == '\136')
			{
				complement = 1;
				NEXTCHAR(ch);
				if (translate)
					ch = translate[(unsigned char)ch];
			}
			else
				complement = 0;
			prev = -1;
			range = 0;
			firstchar = 1;
			while (ch != '\135' || firstchar)
			{
				firstchar = 0;
				if (regexp_ansi_sequences && ch == '\134')
				{
					NEXTCHAR(ch);
					ANSI_TRANSLATE(ch);
				}
				if (range)
				{
					for (a = prev; a <= (int)ch; a++)
						SETBIT(pattern, offset, a);
					prev = -1;
					range = 0;
				}
				else
					if (prev != -1 && ch == '-')
						range = 1;
					else
					{
						SETBIT(pattern, offset, ch);
						prev = ch;
					}
				NEXTCHAR(ch);
				if (translate)
					ch = translate[(unsigned char)ch];
			}
			if (range)
				SETBIT(pattern, offset, '-');
			if (complement)
			{
				for (a = 0; a < 256/8; a++)
					pattern[offset+a] ^= 0xff;
			}
			break;
		}
		case Rbegbuf:
		{
			opcode = Cbegbuf;
			goto store_opcode;
		}
		case Rendbuf:
		{
			opcode = Cendbuf;
			goto store_opcode;
		}
		case Rwordchar:
		{
			opcode = Csyntaxspec;
			ch = Sword;
			goto store_opcode_and_arg;
		}
		case Rnotwordchar:
		{
			opcode = Cnotsyntaxspec;
			ch = Sword;
			goto store_opcode_and_arg;
		}
		case Rwordbeg:
		{
			opcode = Cwordbeg;
			goto store_opcode;
		}
		case Rwordend:
		{
			opcode = Cwordend;
			goto store_opcode;
		}
		case Rwordbound:
		{
			opcode = Cwordbound;
			goto store_opcode;
		}
		case Rnotwordbound:
		{
			opcode = Cnotwordbound;
			goto store_opcode;
		}
		default:
		{
			abort();
		}
		}
		beginning_context = (op == Ropenpar || op == Ror);
	}
	if (starts_base != 0)
		goto parenthesis_error;
	assert(num_jumps == 0);
	ALLOC(1);
	STORE(Cend);
	SET_FIELDS;
	if(!re_optimize(bufp))
1512
		return "Optimization error";
Guido van Rossum's avatar
Guido van Rossum committed
1513
	return NULL;
1514 1515

  op_error:
Guido van Rossum's avatar
Guido van Rossum committed
1516
	SET_FIELDS;
1517
	return "Badly placed special character";
1518 1519

  bad_match_register:
Guido van Rossum's avatar
Guido van Rossum committed
1520
	SET_FIELDS;
1521
	return "Bad match register number";
1522 1523
   
  hex_error:
Guido van Rossum's avatar
Guido van Rossum committed
1524
	SET_FIELDS;
1525
	return "Bad hexadecimal number";
1526 1527
   
  parenthesis_error:
Guido van Rossum's avatar
Guido van Rossum committed
1528
	SET_FIELDS;
1529
	return "Badly placed parenthesis";
1530 1531
   
  out_of_memory:
Guido van Rossum's avatar
Guido van Rossum committed
1532
	SET_FIELDS;
1533
	return "Out of memory";
1534 1535
   
  ends_prematurely:
Guido van Rossum's avatar
Guido van Rossum committed
1536
	SET_FIELDS;
1537
	return "Regular expression ends prematurely";
1538 1539

  too_complex:
Guido van Rossum's avatar
Guido van Rossum committed
1540
	SET_FIELDS;
1541
	return "Regular expression too complex";
Guido van Rossum's avatar
Guido van Rossum committed
1542
}
1543

Guido van Rossum's avatar
Guido van Rossum committed
1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557
#undef CHARAT
#undef NEXTCHAR
#undef GETHEX
#undef ALLOC
#undef STORE
#undef CURRENT_LEVEL_START
#undef SET_LEVEL_START
#undef PUSH_LEVEL_STARTS
#undef POP_LEVEL_STARTS
#undef PUT_ADDR
#undef INSERT_JUMP
#undef SETBIT
#undef SET_FIELDS

1558
#define PREFETCH if (text == textend) goto fail
Guido van Rossum's avatar
Guido van Rossum committed
1559

1560 1561 1562 1563
#define NEXTCHAR(var) \
PREFETCH; \
var = (unsigned char)*text++; \
if (translate) \
Guido van Rossum's avatar
Guido van Rossum committed
1564
	var = translate[var]
Guido van Rossum's avatar
Guido van Rossum committed
1565

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
1566 1567
int re_match(regexp_t bufp, unsigned char *string, int size, int pos,
             regexp_registers_t old_regs)
Guido van Rossum's avatar
Guido van Rossum committed
1568
{
1569 1570 1571 1572 1573
	unsigned char *code;
	unsigned char *translate;
	unsigned char *text;
	unsigned char *textstart;
	unsigned char *textend;
Guido van Rossum's avatar
Guido van Rossum committed
1574 1575 1576 1577 1578
	int a;
	int b;
	int ch;
	int reg;
	int match_end;
1579 1580
	unsigned char *regstart;
	unsigned char *regend;
Guido van Rossum's avatar
Guido van Rossum committed
1581 1582
	int regsize;
	match_state state;
1583
  
Guido van Rossum's avatar
Guido van Rossum committed
1584 1585
	assert(pos >= 0 && size >= 0);
	assert(pos <= size);
1586
  
Guido van Rossum's avatar
Guido van Rossum committed
1587 1588 1589
	text = string + pos;
	textstart = string;
	textend = string + size;
1590
  
Guido van Rossum's avatar
Guido van Rossum committed
1591
	code = bufp->buffer;
1592
  
Guido van Rossum's avatar
Guido van Rossum committed
1593
	translate = bufp->translate;
1594
  
Guido van Rossum's avatar
Guido van Rossum committed
1595 1596
	NEW_STATE(state, bufp->num_registers);

1597
  continue_matching:
Guido van Rossum's avatar
Guido van Rossum committed
1598 1599 1600
	switch (*code++)
	{
	case Cend:
Guido van Rossum's avatar
Guido van Rossum committed
1601
	{
Guido van Rossum's avatar
Guido van Rossum committed
1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637
		match_end = text - textstart;
		if (old_regs)
		{
			old_regs->start[0] = pos;
			old_regs->end[0] = match_end;
			if (!bufp->uses_registers)
			{
				for (a = 1; a < RE_NREGS; a++)
				{
					old_regs->start[a] = -1;
					old_regs->end[a] = -1;
				}
			}
			else
			{
				for (a = 1; a < bufp->num_registers; a++)
				{
					if ((GET_REG_START(state, a) == NULL) ||
					    (GET_REG_END(state, a) == NULL))
					{
						old_regs->start[a] = -1;
						old_regs->end[a] = -1;
						continue;
					}
					old_regs->start[a] = GET_REG_START(state, a) - textstart;
					old_regs->end[a] = GET_REG_END(state, a) - textstart;
				}
				for (; a < RE_NREGS; a++)
				{
					old_regs->start[a] = -1;
					old_regs->end[a] = -1;
				}
			}
		}
		FREE_STATE(state);
		return match_end - pos;
Guido van Rossum's avatar
Guido van Rossum committed
1638
	}
Guido van Rossum's avatar
Guido van Rossum committed
1639
	case Cbol:
1640
	{
Guido van Rossum's avatar
Guido van Rossum committed
1641 1642 1643
		if (text == textstart || text[-1] == '\n')
			goto continue_matching;
		goto fail;
1644
	}
Guido van Rossum's avatar
Guido van Rossum committed
1645
	case Ceol:
1646
	{
Guido van Rossum's avatar
Guido van Rossum committed
1647 1648 1649
		if (text == textend || *text == '\n')
			goto continue_matching;
		goto fail;
1650
	}
Guido van Rossum's avatar
Guido van Rossum committed
1651
	case Cset:
1652
	{
Guido van Rossum's avatar
Guido van Rossum committed
1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721
		NEXTCHAR(ch);
		if (code[ch/8] & (1<<(ch & 7)))
		{
			code += 256/8;
			goto continue_matching;
		}
		goto fail;
	}
	case Cexact:
	{
		NEXTCHAR(ch);
		if (ch != (unsigned char)*code++)
			goto fail;
		goto continue_matching;
	}
	case Canychar:
	{
		NEXTCHAR(ch);
		if (ch == '\n')
			goto fail;
		goto continue_matching;
	}
	case Cstart_memory:
	{
		reg = *code++;
		SET_REG_START(state, reg, text, goto error);
		goto continue_matching;
	}
	case Cend_memory:
	{
		reg = *code++;
		SET_REG_END(state, reg, text, goto error);
		goto continue_matching;
	}
	case Cmatch_memory:
	{
		reg = *code++;
		regstart = GET_REG_START(state, reg);
		regend = GET_REG_END(state, reg);
		if ((regstart == NULL) || (regend == NULL))
			goto fail;  /* or should we just match nothing? */
		regsize = regend - regstart;

		if (regsize > (textend - text))
			goto fail;
		if(translate)
		{
			for (; regstart < regend; regstart++, text++)
				if (translate[*regstart] != translate[*text])
					goto fail;
		}
		else
			for (; regstart < regend; regstart++, text++)
				if (*regstart != *text)
					goto fail;
		goto continue_matching;
	}
	case Cupdate_failure_jump:
	{
		UPDATE_FAILURE(state, text, goto error);
		/* fall to next case */
	}
	/* treat Cstar_jump just like Cjump if it hasn't been optimized */
	case Cstar_jump:
	case Cjump:
	{
		a = (unsigned char)*code++;
		a |= (unsigned char)*code++ << 8;
		code += (int)SHORT(a);
1722 1723 1724 1725 1726
		if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
		        PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cjump)");
			FREE_STATE(state);
            	        return -2;
         	}
Guido van Rossum's avatar
Guido van Rossum committed
1727 1728 1729 1730
		goto continue_matching;
	}
	case Cdummy_failure_jump:
	{
1731 1732
                unsigned char *failuredest;
	  
Guido van Rossum's avatar
Guido van Rossum committed
1733 1734 1735 1736 1737 1738
		a = (unsigned char)*code++;
		a |= (unsigned char)*code++ << 8;
		a = (int)SHORT(a);
		assert(*code == Cfailure_jump);
		b = (unsigned char)code[1];
		b |= (unsigned char)code[2] << 8;
1739 1740 1741 1742 1743 1744 1745
                failuredest = code + (int)SHORT(b) + 3;
		if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
		        PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
			FREE_STATE(state);
            	        return -2;
		}
		PUSH_FAILURE(state, failuredest, NULL, goto error);
Guido van Rossum's avatar
Guido van Rossum committed
1746
		code += a;
1747 1748 1749 1750 1751
		if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
		        PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)");
			FREE_STATE(state);
            	        return -2;
         	}
Guido van Rossum's avatar
Guido van Rossum committed
1752 1753 1754 1755 1756 1757 1758
		goto continue_matching;
	}
	case Cfailure_jump:
	{
		a = (unsigned char)*code++;
		a |= (unsigned char)*code++ << 8;
		a = (int)SHORT(a);
1759 1760 1761 1762 1763
		if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
		        PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)");
			FREE_STATE(state);
            	        return -2;
         	}
Guido van Rossum's avatar
Guido van Rossum committed
1764 1765 1766 1767 1768
		PUSH_FAILURE(state, code + a, text, goto error);
		goto continue_matching;
	}
	case Crepeat1:
	{
1769
		unsigned char *pinst;
Guido van Rossum's avatar
Guido van Rossum committed
1770 1771 1772 1773
		a = (unsigned char)*code++;
		a |= (unsigned char)*code++ << 8;
		a = (int)SHORT(a);
		pinst = code + a;
1774 1775 1776 1777 1778
		if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
		        PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Crepeat1)");
			FREE_STATE(state);
            	        return -2;
         	}
Guido van Rossum's avatar
Guido van Rossum committed
1779 1780 1781 1782 1783 1784 1785 1786 1787 1788
		/* pinst is sole instruction in loop, and it matches a
		 * single character.  Since Crepeat1 was originally a
		 * Cupdate_failure_jump, we also know that backtracking
		 * is useless: so long as the single-character
		 * expression matches, it must be used.  Also, in the
		 * case of +, we've already matched one character, so +
		 * can't fail: nothing here can cause a failure.  */
		switch (*pinst++)
		{
		case Cset:
1789 1790
		  {
		        if (translate)
Guido van Rossum's avatar
Guido van Rossum committed
1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812
			{
				while (text < textend)
				{
					ch = translate[(unsigned char)*text];
					if (pinst[ch/8] & (1<<(ch & 7)))
						text++;
					else
						break;
				}
			}
			else
			{
				while (text < textend)
				{
					ch = (unsigned char)*text;
					if (pinst[ch/8] & (1<<(ch & 7)))
						text++;
					else
						break;
				}
			}
			break;
1813
                }
Guido van Rossum's avatar
Guido van Rossum committed
1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841
		case Cexact:
		{
			ch = (unsigned char)*pinst;
			if (translate)
			{
				while (text < textend &&
				       translate[(unsigned char)*text] == ch)
					text++;
			}
			else
			{
				while (text < textend && (unsigned char)*text == ch)
					text++;
			}
			break;
		}
		case Canychar:
		{
			while (text < textend && (unsigned char)*text != '\n')
				text++;
			break;
		}
		case Csyntaxspec:
		{
			a = (unsigned char)*pinst;
			if (translate)
			{
				while (text < textend &&
1842
				       (SYNTAX(translate[*text]) & a) )
Guido van Rossum's avatar
Guido van Rossum committed
1843 1844 1845 1846
					text++;
			}
			else
			{
1847
				while (text < textend && (SYNTAX(*text) & a) )
Guido van Rossum's avatar
Guido van Rossum committed
1848 1849 1850 1851 1852 1853 1854 1855 1856 1857
					text++;
			}
			break;
		}
		case Cnotsyntaxspec:
		{
			a = (unsigned char)*pinst;
			if (translate)
			{
				while (text < textend &&
1858
				       !(SYNTAX(translate[*text]) & a) )
Guido van Rossum's avatar
Guido van Rossum committed
1859 1860 1861 1862
					text++;
			}
			else
			{
1863
				while (text < textend && !(SYNTAX(*text) & a) )
Guido van Rossum's avatar
Guido van Rossum committed
1864 1865 1866 1867 1868 1869
					text++;
			}
			break;
		}
		default:
		{
1870 1871 1872
		        FREE_STATE(state);
		        PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
		        return -2;
Guido van Rossum's avatar
Guido van Rossum committed
1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897
			/*NOTREACHED*/
		}
		}
		/* due to the funky way + and * are compiled, the top
		 * failure- stack entry at this point is actually a
		 * success entry -- update it & pop it */
		UPDATE_FAILURE(state, text, goto error);
		goto fail;      /* i.e., succeed <wink/sigh> */
	}
	case Cbegbuf:
	{
		if (text == textstart)
			goto continue_matching;
		goto fail;
	}
	case Cendbuf:
	{
		if (text == textend)
			goto continue_matching;
		goto fail;
	}
	case Cwordbeg:
	{
		if (text == textend)
			goto fail;
1898
		if (!(SYNTAX(*text) & Sword)) 
Guido van Rossum's avatar
Guido van Rossum committed
1899 1900 1901
			goto fail;
		if (text == textstart)
			goto continue_matching;
Guido van Rossum's avatar
Guido van Rossum committed
1902
		if (!(SYNTAX(text[-1]) & Sword))
Guido van Rossum's avatar
Guido van Rossum committed
1903 1904 1905 1906 1907 1908 1909
			goto continue_matching;
		goto fail;
	}
	case Cwordend:
	{
		if (text == textstart)
			goto fail;
Guido van Rossum's avatar
Guido van Rossum committed
1910
		if (!(SYNTAX(text[-1]) & Sword))
Guido van Rossum's avatar
Guido van Rossum committed
1911 1912 1913
			goto fail;
		if (text == textend)
			goto continue_matching;
1914 1915 1916
		if (!(SYNTAX(*text) & Sword))
		        goto continue_matching;
                goto fail;
Guido van Rossum's avatar
Guido van Rossum committed
1917 1918 1919 1920 1921 1922 1923 1924
	}
	case Cwordbound:
	{
		/* Note: as in gnu regexp, this also matches at the
		 * beginning and end of buffer.  */

		if (text == textstart || text == textend)
			goto continue_matching;
Guido van Rossum's avatar
Guido van Rossum committed
1925
		if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
Guido van Rossum's avatar
Guido van Rossum committed
1926 1927 1928 1929 1930 1931 1932 1933 1934
			goto continue_matching;
		goto fail;
	}
	case Cnotwordbound:
	{
		/* Note: as in gnu regexp, this never matches at the
		 * beginning and end of buffer.  */
		if (text == textstart || text == textend)
			goto fail;
Guido van Rossum's avatar
Guido van Rossum committed
1935
		if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
1936 1937
      		        goto continue_matching;
		goto fail;
Guido van Rossum's avatar
Guido van Rossum committed
1938 1939 1940 1941
	}
	case Csyntaxspec:
	{
		NEXTCHAR(ch);
Guido van Rossum's avatar
Guido van Rossum committed
1942
		if (!(SYNTAX(ch) & (unsigned char)*code++))
Guido van Rossum's avatar
Guido van Rossum committed
1943 1944 1945 1946 1947 1948
			goto fail;
		goto continue_matching;
	}
	case Cnotsyntaxspec:
	{
		NEXTCHAR(ch);
Guido van Rossum's avatar
Guido van Rossum committed
1949
		if (SYNTAX(ch) & (unsigned char)*code++)
1950
			goto fail;
Guido van Rossum's avatar
Guido van Rossum committed
1951 1952 1953 1954
		goto continue_matching;
	}
	default:
	{
1955 1956 1957
	        FREE_STATE(state);
	        PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
		return -2;
Guido van Rossum's avatar
Guido van Rossum committed
1958 1959
		/*NOTREACHED*/
	}
1960
	}
1961 1962
	
	
1963

Guido van Rossum's avatar
Guido van Rossum committed
1964
#if 0 /* This line is never reached --Guido */
Guido van Rossum's avatar
Guido van Rossum committed
1965
	abort();
1966
#endif
Guido van Rossum's avatar
Guido van Rossum committed
1967 1968 1969
	/*
	 *NOTREACHED
	 */
1970 1971

	/* Using "break;" in the above switch statement is equivalent to "goto fail;" */
1972
  fail:
Guido van Rossum's avatar
Guido van Rossum committed
1973 1974
	POP_FAILURE(state, code, text, goto done_matching, goto error);
	goto continue_matching;
1975 1976 1977 1978
  
  done_matching:
/*   if(translated != NULL) */
/*      free(translated); */
Guido van Rossum's avatar
Guido van Rossum committed
1979 1980
	FREE_STATE(state);
	return -1;
Guido van Rossum's avatar
Guido van Rossum committed
1981

1982 1983 1984
  error:
/*   if (translated != NULL) */
/*      free(translated); */
Guido van Rossum's avatar
Guido van Rossum committed
1985 1986
	FREE_STATE(state);
	return -2;
Guido van Rossum's avatar
Guido van Rossum committed
1987
}
1988
	
Guido van Rossum's avatar
Guido van Rossum committed
1989 1990 1991 1992

#undef PREFETCH
#undef NEXTCHAR

Peter Schneider-Kamp's avatar
Peter Schneider-Kamp committed
1993 1994
int re_search(regexp_t bufp, unsigned char *string, int size, int pos,
              int range, regexp_registers_t regs)
Guido van Rossum's avatar
Guido van Rossum committed
1995
{
1996 1997 1998 1999 2000
	unsigned char *fastmap;
	unsigned char *translate;
	unsigned char *text;
	unsigned char *partstart;
	unsigned char *partend;
Guido van Rossum's avatar
Guido van Rossum committed
2001 2002
	int dir;
	int ret;
2003
	unsigned char anchor;
Guido van Rossum's avatar
Guido van Rossum committed
2004
  
Guido van Rossum's avatar
Guido van Rossum committed
2005 2006
	assert(size >= 0 && pos >= 0);
	assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
Guido van Rossum's avatar
Guido van Rossum committed
2007
  
Guido van Rossum's avatar
Guido van Rossum committed
2008 2009
	fastmap = bufp->fastmap;
	translate = bufp->translate;
2010 2011 2012 2013 2014
	if (fastmap && !bufp->fastmap_accurate) {
                re_compile_fastmap(bufp);
	        if (PyErr_Occurred()) return -2;
	}
	
Guido van Rossum's avatar
Guido van Rossum committed
2015 2016 2017 2018 2019 2020 2021 2022
	anchor = bufp->anchor;
	if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
		fastmap = NULL;

	if (range < 0)
	{
		dir = -1;
		range = -range;
Guido van Rossum's avatar
Guido van Rossum committed
2023
	}
2024
	else
Guido van Rossum's avatar
Guido van Rossum committed
2025 2026
		dir = 1;

2027
	if (anchor == 2) {
Guido van Rossum's avatar
Guido van Rossum committed
2028 2029 2030 2031
		if (pos != 0)
			return -1;
		else
			range = 0;
2032
	}
Guido van Rossum's avatar
Guido van Rossum committed
2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084

	for (; range >= 0; range--, pos += dir)
	{
		if (fastmap)
		{
			if (dir == 1)
			{ /* searching forwards */

				text = string + pos;
				partend = string + size;
				partstart = text;
				if (translate)
					while (text != partend &&
					       !fastmap[(unsigned char) translate[(unsigned char)*text]])
						text++;
				else
					while (text != partend && !fastmap[(unsigned char)*text])
						text++;
				pos += text - partstart;
				range -= text - partstart;
				if (pos == size && bufp->can_be_null == 0)
					return -1;
			}
			else
			{ /* searching backwards */
				text = string + pos;
				partstart = string + pos - range;
				partend = text;
				if (translate)
					while (text != partstart &&
					       !fastmap[(unsigned char)
						       translate[(unsigned char)*text]])
						text--;
				else
					while (text != partstart &&
					       !fastmap[(unsigned char)*text])
						text--;
				pos -= partend - text;
				range -= partend - text;
			}
		}
		if (anchor == 1)
		{ /* anchored to begline */
			if (pos > 0 && (string[pos - 1] != '\n'))
				continue;
		}
		assert(pos >= 0 && pos <= size);
		ret = re_match(bufp, string, size, pos, regs);
		if (ret >= 0)
			return pos;
		if (ret == -2)
			return -2;
Guido van Rossum's avatar
Guido van Rossum committed
2085
	}
Guido van Rossum's avatar
Guido van Rossum committed
2086
	return -1;
Guido van Rossum's avatar
Guido van Rossum committed
2087
}
Guido van Rossum's avatar
Guido van Rossum committed
2088 2089 2090 2091 2092 2093 2094

/*
** Local Variables:
** mode: c
** c-file-style: "python"
** End:
*/