/* Extended regular expression matching and search library,   version 0.12.   (Implements POSIX draft P10003.2/D11.2, except for   internationalization features.)   Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.   This program is free software; you can redistribute it and/or modify   it under the terms of the GNU General Public License as published by   the Free Software Foundation; either version 2, or (at your option)   any later version.   This program is distributed in the hope that it will be useful,   but WITHOUT ANY WARRANTY; without even the implied warranty of   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the   GNU General Public License for more details.   You should have received a copy of the GNU General Public License   along with this program; if not, write to the Free Software   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  *//* AIX requires this to be the first thing in the file. */#if defined (_AIX) && !defined (REGEX_MALLOC)  #pragma alloca#endif#define _GNU_SOURCE#ifdef HAVE_CONFIG_H#include <config.h>#endif/* We need this for `regex.h', and perhaps for the Emacs include files.  */#include <sys/types.h>/* This is for other GNU distributions with internationalized messages.  */#if HAVE_LIBINTL_H || defined (_LIBC)# include <libintl.h>#else# define gettext(msgid) (msgid)#endif/* The `emacs' switch turns on certain matching commands   that make sense only in Emacs. */#ifdef emacs#include "lisp.h"#include "buffer.h"#include "syntax.h"#else  /* not emacs *//* If we are not linking with Emacs proper,   we can't use the relocating allocator   even if config.h says that we can.  */#undef REL_ALLOC#include <stdlib.h>/* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.   If nothing else has been done, use the method below.  */#ifdef INHIBIT_STRING_HEADER#if !(defined (HAVE_BZERO) && defined (HAVE_BCOPY))#if !defined (bzero) && !defined (bcopy)#undef INHIBIT_STRING_HEADER#endif#endif#endif/* This is the normal way of making sure we have a bcopy and a bzero.   This is used in most programs--a few other programs avoid this   by defining INHIBIT_STRING_HEADER.  */#ifndef INHIBIT_STRING_HEADER/*#if defined (HAVE_STRING_H) || defined (STDC_HEADERS) || defined (_LIBC)*/#include <string.h>#ifndef bcmp#define bcmp(s1, s2, n)	memcmp ((s1), (s2), (n))#endif#ifndef bcopy#define bcopy(s, d, n)	memcpy ((d), (s), (n))#endif#ifndef bzero#define bzero(s, n)	memset ((s), 0, (n))#endif/*#else#include <strings.h>#endif*/#endif/* Define the syntax stuff for \<, \>, etc.  *//* This must be nonzero for the wordchar and notwordchar pattern   commands in re_match_2.  */#ifndef Sword #define Sword 1#endif#ifdef SWITCH_ENUM_BUG#define SWITCH_ENUM_CAST(x) ((int)(x))#else#define SWITCH_ENUM_CAST(x) (x)#endif#ifdef SYNTAX_TABLEextern char *re_syntax_table;#else /* not SYNTAX_TABLE *//* How many characters in the character set.  */#define CHAR_SET_SIZE 256static char re_syntax_table[CHAR_SET_SIZE];static voidinit_syntax_once (){   register int c;   static int done = 0;   if (done)	return;   bzero (re_syntax_table, sizeof re_syntax_table);   for (c = 'a'; c <= 'z'; c++)	re_syntax_table[c] = Sword;   for (c = 'A'; c <= 'Z'; c++)	re_syntax_table[c] = Sword;   for (c = '0'; c <= '9'; c++)	re_syntax_table[c] = Sword;   re_syntax_table['_'] = Sword;   done = 1;}#endif /* not SYNTAX_TABLE */#define SYNTAX(c) re_syntax_table[c]#endif /* not emacs *//* Get the interface, including the syntax bits.  */#include "regex.h"/* isalpha etc. are used for the character classes.  */#include <ctype.h>/* Jim Meyering writes:   "... Some ctype macros are valid only for character codes that   isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when   using /bin/cc or gcc but without giving an ansi option).  So, all   ctype uses should be through macros like ISPRINT...  If   STDC_HEADERS is defined, then autoconf has verified that the ctype   macros don't need to be guarded with references to isascii. ...   Defining isascii to 1 should let any compiler worth its salt   eliminate the && through constant folding."  */#if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))#define ISASCII(c) 1#else#define ISASCII(c) isascii(c)#endif#ifdef isblank#define ISBLANK(c) (ISASCII (c) && isblank (c))#else#define ISBLANK(c) ((c) == ' ' || (c) == '\t')#endif#ifdef isgraph#define ISGRAPH(c) (ISASCII (c) && isgraph (c))#else#define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))#endif#define ISPRINT(c) (ISASCII (c) && isprint (c))#define ISDIGIT(c) (ISASCII (c) && isdigit (c))#define ISALNUM(c) (ISASCII (c) && isalnum (c))#define ISALPHA(c) (ISASCII (c) && isalpha (c))#define ISCNTRL(c) (ISASCII (c) && iscntrl (c))#define ISLOWER(c) (ISASCII (c) && islower (c))#define ISPUNCT(c) (ISASCII (c) && ispunct (c))#define ISSPACE(c) (ISASCII (c) && isspace (c))#define ISUPPER(c) (ISASCII (c) && isupper (c))#define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))#ifndef NULL#define NULL (void *)0#endif/* We remove any previous definition of `SIGN_EXTEND_CHAR',   since ours (we hope) works properly with all combinations of   machines, compilers, `char' and `unsigned char' argument types.   (Per Bothner suggested the basic approach.)  */#undef SIGN_EXTEND_CHAR#if __STDC__#define SIGN_EXTEND_CHAR(c) ((signed char) (c))#else  /* not __STDC__ *//* As in Harbison and Steele.  */#define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)#endif/* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we   use `alloca' instead of `malloc'.  This is because using malloc in   re_search* or re_match* could cause memory leaks when C-g is used in   Emacs; also, malloc is slower and causes storage fragmentation.  On   the other hand, malloc is more portable, and easier to debug.        Because we sometimes use alloca, some routines have to be macros,   not functions -- `alloca'-allocated space disappears at the end of the   function it is called in.  */#ifdef REGEX_MALLOC#define REGEX_ALLOCATE malloc#define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)#define REGEX_FREE free#else /* not REGEX_MALLOC  *//* Emacs already defines alloca, sometimes.  */#ifndef alloca/* Make alloca work the best possible way.  */#ifdef __GNUC__#define alloca __builtin_alloca#else /* not __GNUC__ */#if HAVE_ALLOCA_H#include <alloca.h>#else /* not __GNUC__ or HAVE_ALLOCA_H */#ifndef _AIX /* Already did AIX, up at the top.  */char *alloca ();#endif /* not _AIX */#endif /* not HAVE_ALLOCA_H */ #endif /* not __GNUC__ */#endif /* not alloca */#define REGEX_ALLOCATE alloca/* Assumes a `char *destination' variable.  */#define REGEX_REALLOCATE(source, osize, nsize)				\  (destination = (char *) alloca (nsize),				\   bcopy (source, destination, osize),					\   destination)/* No need to do anything to free, after alloca.  */#define REGEX_FREE(arg) ((void)0) /* Do nothing!  But inhibit gcc warning.  */#endif /* not REGEX_MALLOC *//* Define how to allocate the failure stack.  */#ifdef REL_ALLOC#define REGEX_ALLOCATE_STACK(size)				\  r_alloc (&failure_stack_ptr, (size))#define REGEX_REALLOCATE_STACK(source, osize, nsize)		\  r_re_alloc (&failure_stack_ptr, (nsize))#define REGEX_FREE_STACK(ptr)					\  r_alloc_free (&failure_stack_ptr)#else /* not REL_ALLOC */#ifdef REGEX_MALLOC#define REGEX_ALLOCATE_STACK malloc#define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)#define REGEX_FREE_STACK free#else /* not REGEX_MALLOC */#define REGEX_ALLOCATE_STACK alloca#define REGEX_REALLOCATE_STACK(source, osize, nsize)			\   REGEX_REALLOCATE (source, osize, nsize)/* No need to explicitly free anything.  */#define REGEX_FREE_STACK(arg)#endif /* not REGEX_MALLOC */#endif /* not REL_ALLOC *//* True if `size1' is non-NULL and PTR is pointing anywhere inside   `string1' or just past its end.  This works if PTR is NULL, which is   a good thing.  */#define FIRST_STRING_P(ptr) 					\  (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)/* (Re)Allocate N items of type T using malloc, or fail.  */#define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))#define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))#define RETALLOC_IF(addr, n, t) \  if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)#define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))#define BYTEWIDTH 8 /* In bits.  */#define STREQ(s1, s2) ((strcmp (s1, s2) == 0))#undef MAX#undef MIN#define MAX(a, b) ((a) > (b) ? (a) : (b))#define MIN(a, b) ((a) < (b) ? (a) : (b))typedef char boolean;#define false 0#define true 1static int re_match_2_internal ();/* These are the command codes that appear in compiled regular   expressions.  Some opcodes are followed by argument bytes.  A   command code can specify any interpretation whatsoever for its   arguments.  Zero bytes may appear in the compiled regular expression.  */typedef enum{  no_op = 0,  /* Succeed right away--no more backtracking.  */  succeed,	   /* Followed by one byte giving n, then by n literal bytes.  */  exactn,	   /* Matches any (more or less) character.  */  anychar,	   /* Matches any one char belonging to specified set.  First		 following byte is number of bitmap bytes.  Then come bytes		 for a bitmap saying which chars are in.  Bits in each byte		 are ordered low-bit-first.  A character is in the set if its		 bit is 1.  A character too large to have a bit in the map is		 automatically not in the set.  */  charset,	   /* Same parameters as charset, but match any character that is		 not one of those specified.  */  charset_not,	   /* Start remembering the text that is matched, for storing in a		 register.  Followed by one byte with the register number, in		 the range 0 to one less than the pattern buffer's re_nsub		 field.  Then followed by one byte with the number of groups		 inner to this one.  (This last has to be part of the		 start_memory only because we need it in the on_failure_jump		 of re_match_2.)  */  start_memory,	   /* Stop remembering the text that is matched and store it in a		 memory register.  Followed by one byte with the register		 number, in the range 0 to one less than `re_nsub' in the		 pattern buffer, and one byte with the number of inner groups,		 just like `start_memory'.  (We need the number of inner		 groups here because we don't have any easy way of finding the		 corresponding start_memory when we're at a stop_memory.)  */  stop_memory,	   /* Match a duplicate of something remembered. Followed by one		 byte containing the register number.  */  duplicate,	   /* Fail unless at beginning of line.  */  begline,	   /* Fail unless at end of line.  */  endline,	   /* Succeeds if at beginning of buffer (if emacs) or at beginning		 of string to be matched (if not).  */  begbuf,	   /* Analogously, for end of buffer/string.  */  endbuf, 	   /* Followed by two byte relative address to which to jump.  */  jump, 	/* Same as jump, but marks the end of an alternative.  */  jump_past_alt,	   /* Followed by two-byte relative address of place to resume at		 in case of failure.  */  on_failure_jump,		   /* Like on_failure_jump, but pushes a placeholder instead of the		 current string position when executed.  */  on_failure_keep_string_jump,  	   /* Throw away latest failure point and then jump to following		 two-byte relative address.  */  pop_failure_jump,	   /* Change to pop_failure_jump if know won't have to backtrack to		 match; otherwise change to jump.  This is used to jump		 back to the beginning of a repeat.  If what follows this jump		 clearly won't match what the repeat does, such that we can be		 sure that there is no use backtracking out of repetitions		 already matched, then we change it to a pop_failure_jump.		 Followed by two-byte address.  */  maybe_pop_jump,	   /* Jump to following two-byte address, and push a dummy failure		 point. This failure point will be thrown away if an attempt		 is made to use it for a failure.  A `+' construct makes this		 before the first repeat.  Also used as an intermediary kind		 of jump when compiling an alternative.  */  dummy_failure_jump,	/* Push a dummy failure point and continue.  Used at the end of	   alternatives.  */  push_dummy_failure,	   /* Followed by two-byte relative address and two-byte number n.		 After matching N times, jump to the address upon failure.  */  succeed_n,	   /* Followed by two-byte relative address, and two-byte number n.		 Jump to the address N times, then fail.  */  jump_n,	   /* Set the following two-byte relative address to the		 subsequent two-byte number.  The address *includes* the two		 bytes of number.  */  set_number_at,  wordchar,	/* Matches any word-constituent character.  */  notwordchar,	/* Matches any char that is not a word-constituent.  */  wordbeg,	/* Succeeds if at word beginning.  */  wordend,	/* Succeeds if at word end.  */  wordbound,	/* Succeeds if at a word boundary.  */  notwordbound	/* Succeeds if not at a word boundary.  */#ifdef emacs  ,before_dot,	/* Succeeds if before point.  */