/* Extended regular expression matching and search library.
   Copyright (C) 1985, 1989-90 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.  */


/* To test, compile with -Dtest.  This Dtestable feature turns this into
   a self-contained program which reads a pattern, describes how it
   compiles, then reads a string and searches for it.
   
   On the other hand, if you compile with both -Dtest and -Dcanned you
   can run some tests we've already thought of.  */

/* AIX requires the alloca decl to be the first thing in the file. */
#ifdef __GNUC__
#define alloca __builtin_alloca
#else
#ifdef sparc
#include <alloca.h>
#else
#ifdef _AIX
#pragma alloca
#else
char *alloca ();
#endif
#endif
#endif

#ifdef emacs

/* The `emacs' switch turns on certain special matching commands
  that make sense only in emacs. */

#include "config.h"
#include "lisp.h"
#include "buffer.h"
#include "syntax.h"

#else  /* not emacs */

#if defined (USG) || defined (STDC_HEADERS)
#ifndef BSTRING
#include <string.h>
#define bcopy(s,d,n)	memcpy((d),(s),(n))
#define bcmp(s1,s2,n)	memcmp((s1),(s2),(n))
#define bzero(s,n)	memset((s),0,(n))
#endif
#endif

#ifdef STDC_HEADERS
#include <stdlib.h>
#else
char *malloc ();
char *realloc ();
#endif

/* Define the syntax stuff, so we can do the \<, \>, etc.  */

/* This must be nonzero for the wordchar and notwordchar pattern
   commands in re_match_2.  */
#ifndef Sword 
#define Sword 1
#endif

#define SYNTAX(c) re_syntax_table[c]


#ifdef SYNTAX_TABLE

char *re_syntax_table;

#else /* not SYNTAX_TABLE */

static char re_syntax_table[256];


static void
init_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;

   done = 1;
}

#endif /* SYNTAX_TABLE */
#endif /* emacs */

/* We write fatal error messages on standard error.  */
#include <stdio.h>

/* isalpha(3) etc. are used for the character classes.  */
#include <ctype.h>
/* Sequents are missing isgraph.  */
#ifndef isgraph
#define isgraph(c) (isprint((c)) && !isspace((c)))
#endif

/* Get the interface, including the syntax bits.  */
#include "regex.h"


/* These are the command codes that appear in compiled regular
   expressions, one per byte.  Some command codes 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.
   
   The value of `exactn' is needed in search.c (search_buffer) in emacs.
   So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
   `exactn' we use here must also be 1.  */

enum regexpcode
  {
    unused=0,
    exactn=1, /* Followed by one byte giving n, then by n literal bytes.  */
    begline,  /* Fail unless at beginning of line.  */
    endline,  /* Fail unless at end of line.  */
    jump,     /* Followed by two bytes giving relative address to jump to.  */
    on_failure_jump,	 /* Followed by two bytes giving relative address of 
			    place to resume at in case of failure.  */
    finalize_jump,	 /* Throw away latest failure point and then jump to 
			    address.  */
    maybe_finalize_jump, /* Like jump but finalize if safe to do so.
			    This is used to jump back to the beginning
			    of a repeat.  If the command that follows
			    this jump is clearly incompatible with the
			    one at the beginning of the repeat, such that
			    we can be sure that there is no use backtracking
			    out of repetitions already completed,
			    then we finalize.  */
    dummy_failure_jump,  /* Jump, 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
                            use it as an intermediary kind of jump when
                            compiling an or construct.  */
    succeed_n,	 /* Used like on_failure_jump except has to succeed n times;
		    then gets turned into an on_failure_jump. The relative
                    address following it is useless until then.  The
                    address is followed by two bytes containing n.  */
    jump_n,	 /* Similar to jump, but jump n times only; also the relative
		    address following is in turn followed by yet two more bytes
                    containing n.  */
    set_number_at,	/* Set the following relative location to the
			   subsequent number.  */
    anychar,	 /* Matches any (more or less) one character.  */
    charset,     /* 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_not, /* Same parameters as charset, but match any character
                    that is not one of those specified.  */
    start_memory, /* Start remembering the text that is matched, for
		    storing in a memory register.  Followed by one
                    byte containing the register number.  Register numbers
                    must be in the range 0 through RE_NREGS.  */
    stop_memory, /* Stop remembering the text that is matched
		    and store it in a memory register.  Followed by
                    one byte containing the register number. Register
                    numbers must be in the range 0 through RE_NREGS.  */
    duplicate,   /* Match a duplicate of something remembered.
		    Followed by one byte containing the index of the memory 
                    register.  */
    before_dot,	 /* Succeeds if before point.  */
    at_dot,	 /* Succeeds if at point.  */
    after_dot,	 /* Succeeds if after point.  */
    begbuf,      /* Succeeds if at beginning of buffer.  */
    endbuf,      /* Succeeds if at end of buffer.  */
    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.  */
    syntaxspec,  /* Matches any character whose syntax is specified.
		    followed by a byte which contains a syntax code,
                    e.g., Sword.  */
    notsyntaxspec /* Matches any character whose syntax differs from
                     that specified.  */
  };

 
/* Number of failure points to allocate space for initially,
   when matching.  If this number is exceeded, more space is allocated,
   so it is not a hard limit.  */

#ifndef NFAILURES
#define NFAILURES 80
#endif

#ifdef CHAR_UNSIGNED
#define SIGN_EXTEND_CHAR(c) ((c)>(char)127?(c)-256:(c)) /* for IBM RT */
#endif
#ifndef SIGN_EXTEND_CHAR
#define SIGN_EXTEND_CHAR(x) (x)
#endif
 

/* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
#define STORE_NUMBER(destination, number)				\
  { (destination)[0] = (number) & 0377;					\
    (destination)[1] = (number) >> 8; }
  
/* Same as STORE_NUMBER, except increment the destination pointer to
   the byte after where the number is stored.  Watch out that values for
   DESTINATION such as p + 1 won't work, whereas p will.  */
#define STORE_NUMBER_AND_INCR(destination, number)			\
  { STORE_NUMBER(destination, number);					\
    (destination) += 2; }


/* Put into DESTINATION a number stored in two contingous bytes starting
   at SOURCE.  */
#define EXTRACT_NUMBER(destination, source)				\
  { (destination) = *(source) & 0377;					\
    (destination) += SIGN_EXTEND_CHAR (*(char *)((source) + 1)) << 8; }

/* Same as EXTRACT_NUMBER, except increment the pointer for source to
   point to second byte of SOURCE.  Note that SOURCE has to be a value
   such as p, not, e.g., p + 1. */
#define EXTRACT_NUMBER_AND_INCR(destination, source)			\
  { EXTRACT_NUMBER (destination, source);				\
    (source) += 2; }


/* Specify the precise syntax of regexps for compilation.  This provides
   for compatibility for various utilities which historically have
   different, incompatible syntaxes.
   
   The argument SYNTAX is a bit-mask comprised of the various bits
   defined in regex.h.  */

int
re_set_syntax (syntax)
  int syntax;
{
  int ret;

  ret = obscure_syntax;
  obscure_syntax = syntax;
  return ret;
}

/* Set by re_set_syntax to the current regexp syntax to recognize.  */
int obscure_syntax = 0;



/* Macros for re_compile_pattern, which is found below these definitions.  */

#define CHAR_CLASS_MAX_LENGTH  6

/* Fetch the next character in the uncompiled pattern, translating it if
   necessary.  */
#define PATFETCH(c)							\
  {if (p == pend) goto end_of_pattern;					\
  c = * (unsigned char *) p++;						\
  if (translate) c = translate[c]; }

/* Fetch the next character in the uncompiled pattern, with no
   translation.  */
#define PATFETCH_RAW(c)							\
 {if (p == pend) goto end_of_pattern;					\
  c = * (unsigned char *) p++; }

#define PATUNFETCH p--


/* If the buffer isn't allocated when it comes in, use this.  */
#define INIT_BUF_SIZE  28

/* Make sure we have at least N more bytes of space in buffer.  */
#define GET_BUFFER_SPACE(n)						\
  {								        \
    while (b - bufp->buffer + (n) >= bufp->allocated)			\
      EXTEND_BUFFER;							\
  }

/* Make sure we have one more byte of buffer space and then add CH to it.  */
#define BUFPUSH(ch)							\
  {									\
    GET_BUFFER_SPACE (1);						\
    *b++ = (char) (ch);							\
  }
  
/* Extend the buffer by twice its current size via reallociation and
   reset the pointers that pointed into the old allocation to point to
   the correct places in the new allocation.  If extending the buffer
   results in it being larger than 1 << 16, then flag memory exhausted.  */
#define EXTEND_BUFFER							\
  { char *old_buffer = bufp->buffer;					\
    if (bufp->allocated == (1L<<16)) goto too_big;			\
    bufp->allocated *= 2;						\
    if (bufp->allocated > (1L<<16)) bufp->allocated = (1L<<16);		\
    bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated);	\
    if (bufp->buffer == 0)						\
      goto memory_exhausted;						\
    b = (b - old_buffer) + bufp->buffer;				\
    if (fixup_jump)							\
      fixup_jump = (fixup_jump - old_buffer) + bufp->buffer;		\
    if (laststart)							\
      laststart = (laststart - old_buffer) + bufp->buffer;		\
    begalt = (begalt - old_buffer) + bufp->buffer;			\
    if (pending_exact)							\
      pending_exact = (pending_exact - old_buffer) + bufp->buffer;	\
  }

/* Set the bit for character C in a character set list.  */
#define SET_LIST_BIT(c)  (b[(c) / BYTEWIDTH] |= 1 << ((c) % BYTEWIDTH))

/* Get the next unsigned number in the uncompiled pattern.  */
#define GET_UNSIGNED_NUMBER(num) 					\
  { if (p != pend) 							\
      { 								\
        PATFETCH (c); 							\
	while (isdigit (c)) 						\
	  { 								\
	    if (num < 0) 						\
	       num = 0; 						\
            num = num * 10 + c - '0'; 					\
	    if (p == pend) 						\
	       break; 							\
	    PATFETCH (c); 						\
	  } 								\
        } 								\
  }

/* Subroutines for re_compile_pattern.  */
static void store_jump (), insert_jump (), store_jump_n (),
	    insert_jump_n (), insert_op_2 ();


/* re_compile_pattern takes a regular-expression string
   and converts it into a buffer full of byte commands for matching.

   PATTERN   is the address of the pattern string
   SIZE      is the length of it.
   BUFP	    is a  struct re_pattern_buffer *  which points to the info
	     on where to store the byte commands.
	     This structure contains a  char *  which points to the
	     actual space, which should have been obtained with malloc.
	     re_compile_pattern may use realloc to grow the buffer space.

   The number of bytes of commands can be found out by looking in
   the `struct re_pattern_buffer' that bufp pointed to, after
   re_compile_pattern returns. */

char *
re_compile_pattern (pattern, size, bufp)
     char *pattern;
     int size;
     struct re_pattern_buffer *bufp;
{
  register char *b = bufp->buffer;
  register char *p = pattern;
  char *pend = pattern + size;
  register unsigned c, c1;
  char *p1;
  unsigned char *translate = (unsigned char *) bufp->translate;

  /* Address of the count-byte of the most recently inserted `exactn'
     command.  This makes it possible to tell whether a new exact-match
     character can be added to that command or requires a new `exactn'
     command.  */
     
  char *pending_exact = 0;

  /* Address of the place where a forward-jump should go to the end of
     the containing expression.  Each alternative of an `or', except the
     last, ends with a forward-jump of this sort.  */

  char *fixup_jump = 0;

  /* Address of start of the most recently finished expression.
     This tells postfix * where to find the start of its operand.  */

  char *laststart = 0;