regexconvert.c

nedit 是一款linux下的开发源码的功能强大的编辑器

static const char CVSID[] = "$Id: regexConvert.c,v 1.9 2003/05/09 17:43:47 edg Exp $";
/*------------------------------------------------------------------------*
 * `CompileRE', `ExecRE', and `ConvertSubstituteRE' -- regular expression parsing
 *
 * This is a HIGHLY ALTERED VERSION of Henry Spencer's `regcomp'
 * code adapted for NEdit.
 *
 * .-------------------------------------------------------------------.
 * | ORIGINAL COPYRIGHT NOTICE:                                        |
 * |                                                                   |
 * | Copyright (c) 1986 by University of Toronto.                      |
 * | Written by Henry Spencer.  Not derived from licensed software.    |
 * |                                                                   |
 * | Permission is granted to anyone to use this software for any      |
 * | purpose on any computer system, and to redistribute it freely,    |
 * | subject to the following restrictions:                            |
 * |                                                                   |
 * | 1. The author is not responsible for the consequences of use of   |
 * |      this software, no matter how awful, even if they arise       |
 * |      from defects in it.                                          |
 * |                                                                   |
 * | 2. The origin of this software must not be misrepresented, either |
 * |      by explicit claim or by omission.                            |
 * |                                                                   |
 * | 3. Altered versions must be plainly marked as such, and must not  |
 * |      be misrepresented as being the original software.            |
 * `-------------------------------------------------------------------'
 */

#ifdef HAVE_CONFIG_H
#include "../config.h"
#endif

#include "regexConvert.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

#include <X11/Intrinsic.h>

#ifdef HAVE_DEBUG_H
#include "../debug.h"
#endif


/* Utility definitions. */

#define NSUBEXP 50

#define CONVERT_FAIL(m)  {*Error_Ptr = (m); return 0;}
#define IS_QUANTIFIER(c) ((c) == '*' || (c) == '+' || (c) == '?')
#define U_CHAR_AT(p)     ((unsigned int) *(unsigned char *)(p))

/* Flags to be passed up and down via function parameters during compile. */

#define WORST             0  /* Worst case. No assumptions can be made.*/
#define HAS_WIDTH         1  /* Known never to match null string. */
#define SIMPLE            2  /* Simple enough to be STAR/PLUS operand. */

#define NO_PAREN          0  /* Only set by initial call to "chunk". */
#define PAREN             1  /* Used for normal capturing parentheses. */

#define REG_ZERO        0UL
#define REG_ONE         1UL

/* Global work variables for `ConvertRE'. */

static unsigned char *Reg_Parse;       /* Input scan ptr (scans user's regex) */
static int            Total_Paren;     /* Parentheses, (),  counter. */
static unsigned long  Convert_Size;    /* Address of this used as flag. */
static unsigned char *Code_Emit_Ptr;   /* When Code_Emit_Ptr is set to
                                          &Compute_Size no code is emitted.
                                          Instead, the size of code that WOULD
                                          have been generated is accumulated in
                                          Convert_Size.  Otherwise,
                                          Code_Emit_Ptr points to where compiled
                                          regex code is to be written. */
static unsigned char  Compute_Size;
static char         **Error_Ptr;       /* Place to store error messages so
                                          they can be returned by `ConvertRE' */
static char           Error_Text [128];/* Sting to build error messages in. */

static unsigned char  Meta_Char [] = ".*+?[(|)^<>$";

static unsigned char *Convert_Str;

/* Forward declarations for functions used by `ConvertRE'. */

static int            alternative       (int *flag_param);
static int            chunk             (int paren, int *flag_param);
static void           emit_convert_byte (unsigned char c);
static unsigned char  literal_escape    (unsigned char c, int);
static int            atom              (int *flag_param);
static void           reg_error         (char *str);
static int            piece             (int *flag_param);

/*----------------------------------------------------------------------*
 * ConvertRE
 *
 * Compiles a regular expression into the internal format used by
 * `ExecRE'.
 *
 * Beware that the optimization and preparation code in here knows about
 * some of the structure of the compiled regexp.
 *----------------------------------------------------------------------*/

char * ConvertRE (const char *exp, char **errorText) {

   int  flags_local, pass;

   /* Set up `errorText' to receive failure reports. */

    Error_Ptr = errorText;
   *Error_Ptr = "";

   if (exp == NULL) CONVERT_FAIL ("NULL argument to `ConvertRE\'");

   Code_Emit_Ptr = &Compute_Size;
   Convert_Size  = 0UL;

   /* We can't allocate space until we know how big the compiled form will be,
      but we can't compile it (and thus know how big it is) until we've got a
      place to put the code.  So we cheat: we compile it twice, once with code
      generation turned off and size counting turned on, and once "for real".
      This also means that we don't allocate space until we are sure that the
      thing really will compile successfully, and we never have to move the
      code and thus invalidate pointers into it.  (Note that it has to be in
      one piece because free() must be able to free it all.) */

   for (pass = 1; pass <= 2; pass++) {
      /*-------------------------------------------*
       * FIRST  PASS: Determine size and legality. *
       * SECOND PASS: Emit converted code.         *
       *-------------------------------------------*/

      Reg_Parse   = (unsigned char *) exp;
      Total_Paren = 1;

      if (chunk (NO_PAREN, &flags_local) == 0) return (NULL); /* Something
                                                                 went wrong */
      emit_convert_byte ('\0');

      if (pass == 1) {
         /* Allocate memory. */

         Convert_Str =
            (unsigned char *) XtMalloc (sizeof (unsigned char) * Convert_Size);

         if (Convert_Str == NULL) {
            CONVERT_FAIL ("out of memory in `ConvertRE\'");
         }

         Code_Emit_Ptr = Convert_Str;
      }
   }

   return (char *) Convert_Str;
}

/*----------------------------------------------------------------------*
 * chunk                                                                *
 *                                                                      *
 * Process main body of regex or process a parenthesized "thing".       *
 *                                                                      *
 * Caller must absorb opening parenthesis.
 *----------------------------------------------------------------------*/

static int chunk (int paren, int *flag_param) {

   register int   this_branch;
            int   flags_local;

   *flag_param = HAS_WIDTH;  /* Tentatively. */

   /* Make an OPEN node, if parenthesized. */

   if (paren == PAREN) {
      if (Total_Paren >= NSUBEXP) {
         sprintf (Error_Text, "number of ()'s > %d", (int) NSUBEXP);
         CONVERT_FAIL (Error_Text);
      }

      Total_Paren++;
   }

   /* Pick up the branches, linking them together. */

   do {
      this_branch = alternative (&flags_local);

      if (this_branch == 0) return 0;

      /* If any alternative could be zero width, consider the whole
         parenthisized thing to be zero width. */

      if (!(flags_local & HAS_WIDTH)) *flag_param &= ~HAS_WIDTH;

      /* Are there more alternatives to process? */

      if (*Reg_Parse != '|') break;

      emit_convert_byte ('|');

      Reg_Parse++;
   } while (1);

   /* Check for proper termination. */

   if (paren != NO_PAREN && *Reg_Parse != ')') {
      CONVERT_FAIL ("missing right parenthesis \')\'");

   } else if (paren != NO_PAREN) {
      emit_convert_byte (')');
      Reg_Parse++;

   } else if (paren == NO_PAREN && *Reg_Parse != '\0') {
      if (*Reg_Parse == ')') {
         CONVERT_FAIL ("missing left parenthesis \'(\'");
      } else {
         CONVERT_FAIL ("junk on end");  /* "Can't happen" - NOTREACHED */
      }
   }

   return 1;
}

/*----------------------------------------------------------------------*
 * alternative - Processes one alternative of an '|' operator.
 *----------------------------------------------------------------------*/

static int alternative (int *flag_param) {

   int  ret_val;
   int  flags_local;

   *flag_param = WORST;  /* Tentatively. */

   /* Loop until we hit the start of the next alternative, the end of this set
      of alternatives (end of parentheses), or the end of the regex. */

   while (*Reg_Parse != '|' && *Reg_Parse != ')' && *Reg_Parse != '\0') {
      ret_val = piece (&flags_local);

      if (ret_val == 0) return 0; /* Something went wrong. */

      *flag_param |= flags_local & HAS_WIDTH;
   }

   return 1;
}

/*----------------------------------------------------------------------*
 * piece - something followed by possible '*', '+', or '?'.
 *----------------------------------------------------------------------*/

static int piece (int *flag_param) {

   register int            ret_val;
   register unsigned char  op_code;
            unsigned long  min_val = REG_ZERO;
            int            flags_local;

   ret_val = atom (&flags_local);

   if (ret_val == 0) return 0;  /* Something went wrong. */

   op_code = *Reg_Parse;

   if (!IS_QUANTIFIER (op_code)) {
      *flag_param = flags_local;

      return (ret_val);
   }

   Reg_Parse++;

   if (op_code == '+') min_val = REG_ONE;

   /* It is dangerous to apply certain quantifiers to a possibly zero width
      item. */

   if (!(flags_local & HAS_WIDTH) && min_val > REG_ZERO) {
      sprintf (Error_Text, "%c operand could be empty", op_code);

      CONVERT_FAIL (Error_Text);
   }

   *flag_param = (min_val > REG_ZERO) ? (WORST | HAS_WIDTH) : WORST;

   if ( !((op_code == '*') || (op_code == '+') || (op_code == '?')) ) {
      /* We get here if the IS_QUANTIFIER macro is not coordinated properly
         with this function. */

      CONVERT_FAIL ("internal error #2, `piece\'");
   }

   if (IS_QUANTIFIER (*Reg_Parse)) {
      sprintf (Error_Text, "nested quantifiers, %c%c", op_code, *Reg_Parse);

      CONVERT_FAIL (Error_Text);
   }

   emit_convert_byte (op_code);

   return (ret_val);
}

/*----------------------------------------------------------------------*
 * atom - Process one regex item at the lowest level
 *----------------------------------------------------------------------*/

static int atom (int *flag_param) {
   int            ret_val = 1;
   unsigned char  test;
   int            flags_local;

   *flag_param = WORST;  /* Tentatively. */