comparison src/search.c @ 89483:2f877ed80fa6

*** empty log message ***

88123:375f2633d815

#include <config.h>
#include "lisp.h"
#include "syntax.h"
#include "category.h"
#include "buffer.h"
#include "charset.h"
#include "region-cache.h"
#include "commands.h"
#include "blockinput.h"
#include "intervals.h"

   values that will result from matching this pattern.
   If it is 0, we should compile the pattern not to record any
   subexpression bounds.
   POSIX is nonzero if we want full backtracking (POSIX style)
   for this pattern.  0 means backtrack only enough to get a valid match.
   MULTIBYTE is nonzero if we want to handle multibyte characters in
   PATTERN.  0 means all multibyte characters are recognized just as
   sequences of binary data.  */

static void
compile_pattern_1 (cp, pattern, translate, regp, posix, multibyte)
     struct regexp_cache *cp;
     Lisp_Object pattern;
     Lisp_Object translate;
     struct re_registers *regp;
     int posix;
     int multibyte;
{
  unsigned char *raw_pattern;
  int raw_pattern_size;
  char *val;
  reg_syntax_t old;

  /* MULTIBYTE says whether the text to be searched is multibyte.
     We must convert PATTERN to match that, or we will not really
     find things right.  */

  if (multibyte == STRING_MULTIBYTE (pattern))
    {
      raw_pattern = (unsigned char *) SDATA (pattern);
      raw_pattern_size = SBYTES (pattern);
    }
  else if (multibyte)
    {
      raw_pattern_size = count_size_as_multibyte (SDATA (pattern),
						  SCHARS (pattern));
      raw_pattern = (unsigned char *) alloca (raw_pattern_size + 1);
      copy_text (SDATA (pattern), raw_pattern,
		 SCHARS (pattern), 0, 1);
    }
  else
    {
      /* Converting multibyte to single-byte.

	 ??? Perhaps this conversion should be done in a special way
	 by subtracting nonascii-insert-offset from each non-ASCII char,
	 so that only the multibyte chars which really correspond to
	 the chosen single-byte character set can possibly match.  */
      raw_pattern_size = SCHARS (pattern);
      raw_pattern = (unsigned char *) alloca (raw_pattern_size + 1);
      copy_text (SDATA (pattern), raw_pattern,
		 SBYTES (pattern), 1, 0);
    }

  cp->regexp = Qnil;
  cp->buf.translate = (! NILP (translate) ? translate : make_number (0));
  cp->posix = posix;
  cp->buf.multibyte = multibyte;
  BLOCK_INPUT;
  old = re_set_syntax (RE_SYNTAX_EMACS
		       | (posix ? 0 : RE_NO_POSIX_BACKTRACKING));
  val = (char *) re_compile_pattern ((char *)raw_pattern,
				     raw_pattern_size, &cp->buf);
  re_set_syntax (old);
  UNBLOCK_INPUT;
  if (val)
    Fsignal (Qinvalid_regexp, Fcons (build_string (val), Qnil));

      if (SCHARS (cp->regexp) == SCHARS (pattern)
	  && STRING_MULTIBYTE (cp->regexp) == STRING_MULTIBYTE (pattern)
	  && !NILP (Fstring_equal (cp->regexp, pattern))
	  && EQ (cp->buf.translate, (! NILP (translate) ? translate : make_number (0)))
	  && cp->posix == posix
	  && cp->buf.multibyte == multibyte)
	break;

      /* If we're at the end of the cache, compile into the nil cell
	 we found, or the last (least recently used) cell with a
	 string value.  */

      int raw_pattern_size;
      int raw_pattern_size_byte;
      unsigned char *patbuf;
      int multibyte = !NILP (current_buffer->enable_multibyte_characters);
      unsigned char *base_pat = SDATA (string);
      int charset_base = -1;
      int boyer_moore_ok = 1;

      /* MULTIBYTE says whether the text to be searched is multibyte.
	 We must convert PATTERN to match that, or we will not really
	 find things right.  */

	}

      /* Copy and optionally translate the pattern.  */
      len = raw_pattern_size;
      len_byte = raw_pattern_size_byte;
      patbuf = (unsigned char *) alloca (len_byte);
      pat = patbuf;
      base_pat = raw_pattern;
      if (multibyte)
	{
	  while (--len >= 0)
	    {
	      unsigned char str[MAX_MULTIBYTE_LENGTH];
	      int c, translated, inverse;
	      int in_charlen, charlen;

	      /* If we got here and the RE flag is set, it's because we're
		 dealing with a regexp known to be trivial, so the backslash
		 just quotes the next character.  */
	      if (RE && *base_pat == '\\')

	      c = STRING_CHAR_AND_LENGTH (base_pat, len_byte, in_charlen);

	      /* Translate the character, if requested.  */
	      TRANSLATE (translated, trt, c);
	      /* If translation changed the byte-length, go back
		 to the original character.  */
	      charlen = CHAR_STRING (translated, str);
	      if (in_charlen != charlen)
		{
		  translated = c;
		  charlen = CHAR_STRING (c, str);
		}

	      /* If we are searching for something strange,
		 an invalid multibyte code, don't use boyer-moore.  */
	      if (! ASCII_BYTE_P (translated)
		  && (charlen == 1 /* 8bit code */
		      || charlen != in_charlen /* invalid multibyte code */
		      ))
		boyer_moore_ok = 0;

	      TRANSLATE (inverse, inverse_trt, c);

	      /* Did this char actually get translated?
		 Would any other char get translated into it?  */
	      if (translated != c || inverse != c)
		{
		  /* Keep track of which character set row
		     contains the characters that need translation.  */
		  int charset_base_code = c & ~CHAR_FIELD3_MASK;
		  int inverse_charset_base = inverse & ~CHAR_FIELD3_MASK;

		  if (charset_base_code != inverse_charset_base)
		    boyer_moore_ok = 0;
		  else if (charset_base == -1)
		    charset_base = charset_base_code;
		  else if (charset_base != charset_base_code)
		    /* If two different rows appear, needing translation,
		       then we cannot use boyer_moore search.  */
		    boyer_moore_ok = 0;
		}

	      /* Store this character into the translated pattern.  */
	      bcopy (str, pat, charlen);
	      pat += charlen;
	      base_pat += in_charlen;
	      len_byte -= in_charlen;
	    }
	}
      else
	{
	  /* Unibyte buffer.  */
	  charset_base = 0;
	  while (--len >= 0)
	    {
	      int c, translated;

	      /* If we got here and the RE flag is set, it's because we're

      pat = base_pat = patbuf;

      if (boyer_moore_ok)
	return boyer_moore (n, pat, len, len_byte, trt, inverse_trt,
			    pos, pos_byte, lim, lim_byte,
			    charset_base);
      else
	return simple_search (n, pat, len, len_byte, trt,
			      pos, pos_byte, lim, lim_byte);
    }
}

   If that criterion is not satisfied, do not call this function.  */

static int
boyer_moore (n, base_pat, len, len_byte, trt, inverse_trt,
	     pos, pos_byte, lim, lim_byte, charset_base)
     int n;
     unsigned char *base_pat;
     int len, len_byte;
     Lisp_Object trt;
     Lisp_Object inverse_trt;
     int pos, pos_byte;
     int lim, lim_byte;
     int charset_base;
{
  int direction = ((n > 0) ? 1 : -1);
  register int dirlen;
  int infinity, limit, stride_for_teases = 0;
  register int *BM_tab;

	    {
	      unsigned char *charstart = ptr;
	      while (! CHAR_HEAD_P (*charstart))
		charstart--;
	      untranslated = STRING_CHAR (charstart, ptr - charstart + 1);
	      if (charset_base == (untranslated & ~CHAR_FIELD3_MASK))
		{
		  TRANSLATE (ch, trt, untranslated);
		  if (! CHAR_HEAD_P (*ptr))
		    {
		      translate_prev_byte = ptr[-1];

	    {
	      ch = *ptr;
	      this_translated = 0;
	    }

	  if (ch > 0400)
	    j = ((unsigned char) ch) | 0200;
	  else
	    j = (unsigned char) ch;

	  if (i == infinity)
	    stride_for_teases = BM_tab[j];

	      int starting_ch = ch;
	      int starting_j = j;
	      while (1)
		{
		  TRANSLATE (ch, inverse_trt, ch);
		  if (ch > 0400)
		    j = ((unsigned char) ch) | 0200;
		  else
		    j = (unsigned char) ch;

		  /* For all the characters that map into CH,
		     set up simple_translate to map the last byte

  for (i = 0, i_byte = 0; i < len; )
    {
      int c;

      FETCH_STRING_CHAR_ADVANCE (c, string, i, i_byte);

      if (SYNTAX (c) != Sword)
	{
	  punct_count++;
	  if (i > 0 && SYNTAX (prev_c) == Sword)

  for (i = 0, i_byte = 0; i < len; )
    {
      int c;
      int i_byte_orig = i_byte;

      FETCH_STRING_CHAR_ADVANCE (c, string, i, i_byte);

      if (SYNTAX (c) == Sword)
	{
	  bcopy (SDATA (string) + i_byte_orig, o,
		 i_byte - i_byte_orig);

      while (pos < last)
	{
	  if (NILP (string))
	    {
	      c = FETCH_CHAR (pos_byte);
	      INC_BOTH (pos, pos_byte);
	    }
	  else
	    FETCH_STRING_CHAR_ADVANCE (c, string, pos, pos_byte);

	  if (LOWERCASEP (c))
	    {
	      /* Cannot be all caps if any original char is lower case */

      int buf_multibyte = !NILP (current_buffer->enable_multibyte_characters);
      int str_multibyte = STRING_MULTIBYTE (newtext);
      Lisp_Object rev_tbl;
      int really_changed = 0;

      rev_tbl= (!buf_multibyte && CHAR_TABLE_P (Vnonascii_translation_table)
		? Fchar_table_extra_slot (Vnonascii_translation_table,
					  make_number (0))
		: Qnil);

      substed_alloc_size = length * 2 + 100;
      substed = (unsigned char *) xmalloc (substed_alloc_size + 1);
      substed_len = 0;

	      if (str_multibyte)
		{
		  FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c, newtext,
						      pos, pos_byte);
		  if (!buf_multibyte && !SINGLE_BYTE_CHAR_P (c))
		    c = multibyte_char_to_unibyte (c, rev_tbl);
		}
	      else
		{
		  c = SREF (newtext, pos_byte++);

89483:2f877ed80fa6

#include <config.h>
#include "lisp.h"
#include "syntax.h"
#include "category.h"
#include "buffer.h"
#include "character.h"
#include "region-cache.h"
#include "commands.h"
#include "blockinput.h"
#include "intervals.h"

   values that will result from matching this pattern.
   If it is 0, we should compile the pattern not to record any
   subexpression bounds.
   POSIX is nonzero if we want full backtracking (POSIX style)
   for this pattern.  0 means backtrack only enough to get a valid match.
   MULTIBYTE is nonzero iff a target of match is a multibyte buffer or
   string.  */

static void
compile_pattern_1 (cp, pattern, translate, regp, posix, multibyte)
     struct regexp_cache *cp;
     Lisp_Object pattern;
     Lisp_Object translate;
     struct re_registers *regp;
     int posix;
     int multibyte;
{
  char *val;
  reg_syntax_t old;

  cp->regexp = Qnil;
  cp->buf.translate = (! NILP (translate) ? translate : make_number (0));
  cp->posix = posix;
  cp->buf.multibyte = STRING_MULTIBYTE (pattern);
  cp->buf.target_multibyte = multibyte;
  BLOCK_INPUT;
  old = re_set_syntax (RE_SYNTAX_EMACS
		       | (posix ? 0 : RE_NO_POSIX_BACKTRACKING));
  val = (char *) re_compile_pattern ((char *) SDATA (pattern),
				     SBYTES (pattern), &cp->buf);
  re_set_syntax (old);
  UNBLOCK_INPUT;
  if (val)
    Fsignal (Qinvalid_regexp, Fcons (build_string (val), Qnil));

      if (SCHARS (cp->regexp) == SCHARS (pattern)
	  && STRING_MULTIBYTE (cp->regexp) == STRING_MULTIBYTE (pattern)
	  && !NILP (Fstring_equal (cp->regexp, pattern))
	  && EQ (cp->buf.translate, (! NILP (translate) ? translate : make_number (0)))
	  && cp->posix == posix
	  && cp->buf.target_multibyte == multibyte)
	break;

      /* If we're at the end of the cache, compile into the nil cell
	 we found, or the last (least recently used) cell with a
	 string value.  */

      int raw_pattern_size;
      int raw_pattern_size_byte;
      unsigned char *patbuf;
      int multibyte = !NILP (current_buffer->enable_multibyte_characters);
      unsigned char *base_pat = SDATA (string);
      /* High bits of char; 0 for ASCII characters, (CHAR & ~0x3F)
	 otherwise.  Characters of the same high bits have the same
	 sequence of bytes but last.  To do the BM search, all
	 characters in STRING must have the same high bits (including
	 their case translations).  */
      int char_high_bits = -1;
      int boyer_moore_ok = 1;

      /* MULTIBYTE says whether the text to be searched is multibyte.
	 We must convert PATTERN to match that, or we will not really
	 find things right.  */

	}

      /* Copy and optionally translate the pattern.  */
      len = raw_pattern_size;
      len_byte = raw_pattern_size_byte;
      patbuf = (unsigned char *) alloca (len * MAX_MULTIBYTE_LENGTH);
      pat = patbuf;
      base_pat = raw_pattern;
      if (multibyte)
	{
	  while (--len >= 0)
	    {
	      int c, translated, inverse;
	      int in_charlen;

	      /* If we got here and the RE flag is set, it's because we're
		 dealing with a regexp known to be trivial, so the backslash
		 just quotes the next character.  */
	      if (RE && *base_pat == '\\')

	      c = STRING_CHAR_AND_LENGTH (base_pat, len_byte, in_charlen);

	      /* Translate the character, if requested.  */
	      TRANSLATE (translated, trt, c);
	      TRANSLATE (inverse, inverse_trt, c);

	      /* Did this char actually get translated?
		 Would any other char get translated into it?  */
	      if (translated != c || inverse != c)
		{
		  /* Keep track of which character set row
		     contains the characters that need translation.  */
		  int this_high_bit = ASCII_CHAR_P (c) ? 0 : (c & ~0x3F);
		  int c1 = inverse != c ? inverse : translated;
		  int trt_high_bit = ASCII_CHAR_P (c1) ? 0 : (c1 & ~0x3F);

		  if (this_high_bit != trt_high_bit)
		    boyer_moore_ok = 0;
		  else if (char_high_bits == -1)
		    char_high_bits = this_high_bit;
		  else if (char_high_bits != this_high_bit)
		    /* If two different rows appear, needing translation,
		       then we cannot use boyer_moore search.  */
		    boyer_moore_ok = 0;
		}

	      /* Store this character into the translated pattern.  */
	      CHAR_STRING_ADVANCE (translated, pat);
	      base_pat += in_charlen;
	      len_byte -= in_charlen;
	    }
	}
      else
	{
	  /* Unibyte buffer.  */
	  char_high_bits = 0;
	  while (--len >= 0)
	    {
	      int c, translated;

	      /* If we got here and the RE flag is set, it's because we're

      pat = base_pat = patbuf;

      if (boyer_moore_ok)
	return boyer_moore (n, pat, len, len_byte, trt, inverse_trt,
			    pos, pos_byte, lim, lim_byte,
			    char_high_bits);
      else
	return simple_search (n, pat, len, len_byte, trt,
			      pos, pos_byte, lim, lim_byte);
    }
}

   If that criterion is not satisfied, do not call this function.  */

static int
boyer_moore (n, base_pat, len, len_byte, trt, inverse_trt,
	     pos, pos_byte, lim, lim_byte, char_high_bits)
     int n;
     unsigned char *base_pat;
     int len, len_byte;
     Lisp_Object trt;
     Lisp_Object inverse_trt;
     int pos, pos_byte;
     int lim, lim_byte;
     int char_high_bits;
{
  int direction = ((n > 0) ? 1 : -1);
  register int dirlen;
  int infinity, limit, stride_for_teases = 0;
  register int *BM_tab;

	    {
	      unsigned char *charstart = ptr;
	      while (! CHAR_HEAD_P (*charstart))
		charstart--;
	      untranslated = STRING_CHAR (charstart, ptr - charstart + 1);
	      if (char_high_bits
		  == (ASCII_CHAR_P (untranslated) ? 0 : untranslated & ~0x3F))
		{
		  TRANSLATE (ch, trt, untranslated);
		  if (! CHAR_HEAD_P (*ptr))
		    {
		      translate_prev_byte = ptr[-1];

	    {
	      ch = *ptr;
	      this_translated = 0;
	    }

	  if (this_translated
	      && ch >= 0200)
	    j = (ch & 0x3F) | 0200;
	  else
	    j = (unsigned char) ch;

	  if (i == infinity)
	    stride_for_teases = BM_tab[j];

	      int starting_ch = ch;
	      int starting_j = j;
	      while (1)
		{
		  TRANSLATE (ch, inverse_trt, ch);
		  if (ch > 0200)
		    j = (ch & 0x3F) | 0200;
		  else
		    j = (unsigned char) ch;

		  /* For all the characters that map into CH,
		     set up simple_translate to map the last byte

  for (i = 0, i_byte = 0; i < len; )
    {
      int c;

      FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c, string, i, i_byte);

      if (SYNTAX (c) != Sword)
	{
	  punct_count++;
	  if (i > 0 && SYNTAX (prev_c) == Sword)

  for (i = 0, i_byte = 0; i < len; )
    {
      int c;
      int i_byte_orig = i_byte;

      FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c, string, i, i_byte);

      if (SYNTAX (c) == Sword)
	{
	  bcopy (SDATA (string) + i_byte_orig, o,
		 i_byte - i_byte_orig);

      while (pos < last)
	{
	  if (NILP (string))
	    {
	      c = FETCH_CHAR_AS_MULTIBYTE (pos_byte);
	      INC_BOTH (pos, pos_byte);
	    }
	  else
	    FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c, string, pos, pos_byte);

	  if (LOWERCASEP (c))
	    {
	      /* Cannot be all caps if any original char is lower case */

      int buf_multibyte = !NILP (current_buffer->enable_multibyte_characters);
      int str_multibyte = STRING_MULTIBYTE (newtext);
      Lisp_Object rev_tbl;
      int really_changed = 0;

      rev_tbl = Qnil;

      substed_alloc_size = length * 2 + 100;
      substed = (unsigned char *) xmalloc (substed_alloc_size + 1);
      substed_len = 0;

	      if (str_multibyte)
		{
		  FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c, newtext,
						      pos, pos_byte);
		  if (!buf_multibyte && !ASCII_CHAR_P (c))
		    c = multibyte_char_to_unibyte (c, rev_tbl);
		}
	      else
		{
		  c = SREF (newtext, pos_byte++);