search.c

/* String search routines for GNU Emacs.

Copyright (C) 1985-1987, 1993-1994, 1997-1999, 2001-2013 Free Software
Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs 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 3 of the License, or
(at your option) any later version.

GNU Emacs 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 GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */


#include <config.h>

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

#include <sys/types.h>
#include "regex.h"

#define REGEXP_CACHE_SIZE 20

/* If the regexp is non-nil, then the buffer contains the compiled form
   of that regexp, suitable for searching.  */
struct regexp_cache
{
  struct regexp_cache *next;
  Lisp_Object regexp, whitespace_regexp;
  /* Syntax table for which the regexp applies.  We need this because
     of character classes.  If this is t, then the compiled pattern is valid
     for any syntax-table.  */
  Lisp_Object syntax_table;
  struct re_pattern_buffer buf;
  char fastmap[0400];
  /* True means regexp was compiled to do full POSIX backtracking.  */
  bool posix;
};

/* The instances of that struct.  */
static struct regexp_cache searchbufs[REGEXP_CACHE_SIZE];

/* The head of the linked list; points to the most recently used buffer.  */
static struct regexp_cache *searchbuf_head;


/* Every call to re_match, etc., must pass &search_regs as the regs
   argument unless you can show it is unnecessary (i.e., if re_match
   is certainly going to be called again before region-around-match
   can be called).

   Since the registers are now dynamically allocated, we need to make
   sure not to refer to the Nth register before checking that it has
   been allocated by checking search_regs.num_regs.

   The regex code keeps track of whether it has allocated the search
   buffer using bits in the re_pattern_buffer.  This means that whenever
   you compile a new pattern, it completely forgets whether it has
   allocated any registers, and will allocate new registers the next
   time you call a searching or matching function.  Therefore, we need
   to call re_set_registers after compiling a new pattern or after
   setting the match registers, so that the regex functions will be
   able to free or re-allocate it properly.  */
static struct re_registers search_regs;

/* The buffer in which the last search was performed, or
   Qt if the last search was done in a string;
   Qnil if no searching has been done yet.  */
static Lisp_Object last_thing_searched;

/* Error condition signaled when regexp compile_pattern fails.  */
static Lisp_Object Qinvalid_regexp;

/* Error condition used for failing searches.  */
static Lisp_Object Qsearch_failed;

static void set_search_regs (ptrdiff_t, ptrdiff_t);
static void save_search_regs (void);
static EMACS_INT simple_search (EMACS_INT, unsigned char *, ptrdiff_t,
				ptrdiff_t, Lisp_Object, ptrdiff_t, ptrdiff_t,
                                ptrdiff_t, ptrdiff_t);
static EMACS_INT boyer_moore (EMACS_INT, unsigned char *, ptrdiff_t,
                              Lisp_Object, Lisp_Object, ptrdiff_t,
                              ptrdiff_t, int);
static EMACS_INT search_buffer (Lisp_Object, ptrdiff_t, ptrdiff_t,
                                ptrdiff_t, ptrdiff_t, EMACS_INT, int,
                                Lisp_Object, Lisp_Object, bool);

static _Noreturn void
matcher_overflow (void)
{
  error ("Stack overflow in regexp matcher");
}

/* Compile a regexp and signal a Lisp error if anything goes wrong.
   PATTERN is the pattern to compile.
   CP is the place to put the result.
   TRANSLATE is a translation table for ignoring case, or nil for none.
   POSIX is true if we want full backtracking (POSIX style) for this pattern.
   False means backtrack only enough to get a valid match.

   The behavior also depends on Vsearch_spaces_regexp.  */

static void
compile_pattern_1 (struct regexp_cache *cp, Lisp_Object pattern,
		   Lisp_Object translate, bool posix)
{
  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.charset_unibyte = charset_unibyte;
  if (STRINGP (Vsearch_spaces_regexp))
    cp->whitespace_regexp = Vsearch_spaces_regexp;
  else
    cp->whitespace_regexp = Qnil;

  /* rms: I think BLOCK_INPUT is not needed here any more,
     because regex.c defines malloc to call xmalloc.
     Using BLOCK_INPUT here means the debugger won't run if an error occurs.
     So let's turn it off.  */
  /*  BLOCK_INPUT;  */
  old = re_set_syntax (RE_SYNTAX_EMACS
		       | (posix ? 0 : RE_NO_POSIX_BACKTRACKING));

  if (STRINGP (Vsearch_spaces_regexp))
    re_set_whitespace_regexp (SSDATA (Vsearch_spaces_regexp));
  else
    re_set_whitespace_regexp (NULL);

  val = (char *) re_compile_pattern (SSDATA (pattern),
				     SBYTES (pattern), &cp->buf);

  /* If the compiled pattern hard codes some of the contents of the
     syntax-table, it can only be reused with *this* syntax table.  */
  cp->syntax_table = cp->buf.used_syntax ? BVAR (current_buffer, syntax_table) : Qt;

  re_set_whitespace_regexp (NULL);

  re_set_syntax (old);
  /* unblock_input ();  */
  if (val)
    xsignal1 (Qinvalid_regexp, build_string (val));

  cp->regexp = Fcopy_sequence (pattern);
}

/* Shrink each compiled regexp buffer in the cache
   to the size actually used right now.
   This is called from garbage collection.  */

void
shrink_regexp_cache (void)
{
  struct regexp_cache *cp;

  for (cp = searchbuf_head; cp != 0; cp = cp->next)
    {
      cp->buf.allocated = cp->buf.used;
      cp->buf.buffer = xrealloc (cp->buf.buffer, cp->buf.used);
    }
}

/* Clear the regexp cache w.r.t. a particular syntax table,
   because it was changed.
   There is no danger of memory leak here because re_compile_pattern
   automagically manages the memory in each re_pattern_buffer struct,
   based on its `allocated' and `buffer' values.  */
void
clear_regexp_cache (void)
{
  int i;

  for (i = 0; i < REGEXP_CACHE_SIZE; ++i)
    /* It's tempting to compare with the syntax-table we've actually changed,
       but it's not sufficient because char-table inheritance means that
       modifying one syntax-table can change others at the same time.  */
    if (!EQ (searchbufs[i].syntax_table, Qt))
      searchbufs[i].regexp = Qnil;
}

/* Compile a regexp if necessary, but first check to see if there's one in
   the cache.
   PATTERN is the pattern to compile.
   TRANSLATE is a translation table for ignoring case, or nil for none.
   REGP is the structure that says where to store the "register"
   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 true if we want full backtracking (POSIX style) for this pattern.
   False means backtrack only enough to get a valid match.  */

struct re_pattern_buffer *
compile_pattern (Lisp_Object pattern, struct re_registers *regp,
		 Lisp_Object translate, bool posix, bool multibyte)
{
  struct regexp_cache *cp, **cpp;

  for (cpp = &searchbuf_head; ; cpp = &cp->next)
    {
      cp = *cpp;
      /* Entries are initialized to nil, and may be set to nil by
	 compile_pattern_1 if the pattern isn't valid.  Don't apply
	 string accessors in those cases.  However, compile_pattern_1
	 is only applied to the cache entry we pick here to reuse.  So
	 nil should never appear before a non-nil entry.  */
      if (NILP (cp->regexp))
	goto compile_it;
      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
	  && (EQ (cp->syntax_table, Qt)
	      || EQ (cp->syntax_table, BVAR (current_buffer, syntax_table)))
	  && !NILP (Fequal (cp->whitespace_regexp, Vsearch_spaces_regexp))
	  && cp->buf.charset_unibyte == charset_unibyte)
	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.  */
      if (cp->next == 0)
	{
	compile_it:
	  compile_pattern_1 (cp, pattern, translate, posix);
	  break;
	}
    }

  /* When we get here, cp (aka *cpp) contains the compiled pattern,
     either because we found it in the cache or because we just compiled it.
     Move it to the front of the queue to mark it as most recently used.  */
  *cpp = cp->next;
  cp->next = searchbuf_head;
  searchbuf_head = cp;

  /* Advise the searching functions about the space we have allocated
     for register data.  */
  if (regp)
    re_set_registers (&cp->buf, regp, regp->num_regs, regp->start, regp->end);

  /* The compiled pattern can be used both for multibyte and unibyte
     target.  But, we have to tell which the pattern is used for. */
  cp->buf.target_multibyte = multibyte;

  return &cp->buf;
}


static Lisp_Object
looking_at_1 (Lisp_Object string, bool posix)
{
  Lisp_Object val;
  unsigned char *p1, *p2;
  ptrdiff_t s1, s2;
  register ptrdiff_t i;
  struct re_pattern_buffer *bufp;

  if (running_asynch_code)
    save_search_regs ();

  /* This is so set_image_of_range_1 in regex.c can find the EQV table.  */
  set_char_table_extras (BVAR (current_buffer, case_canon_table), 2,
			 BVAR (current_buffer, case_eqv_table));

  CHECK_STRING (string);
  bufp = compile_pattern (string,
			  (NILP (Vinhibit_changing_match_data)
			   ? &search_regs : NULL),
			  (!NILP (BVAR (current_buffer, case_fold_search))
			   ? BVAR (current_buffer, case_canon_table) : Qnil),
			  posix,
			  !NILP (BVAR (current_buffer, enable_multibyte_characters)));

  immediate_quit = 1;
  QUIT;			/* Do a pending quit right away, to avoid paradoxical behavior */

  /* Get pointers and sizes of the two strings
     that make up the visible portion of the buffer. */

  p1 = BEGV_ADDR;
  s1 = GPT_BYTE - BEGV_BYTE;
  p2 = GAP_END_ADDR;
  s2 = ZV_BYTE - GPT_BYTE;
  if (s1 < 0)
    {
      p2 = p1;
      s2 = ZV_BYTE - BEGV_BYTE;
      s1 = 0;
    }
  if (s2 < 0)
    {
      s1 = ZV_BYTE - BEGV_BYTE;
      s2 = 0;
    }

  re_match_object = Qnil;

  i = re_match_2 (bufp, (char *) p1, s1, (char *) p2, s2,
		  PT_BYTE - BEGV_BYTE,
		  (NILP (Vinhibit_changing_match_data)
		   ? &search_regs : NULL),
		  ZV_BYTE - BEGV_BYTE);
  immediate_quit = 0;

  if (i == -2)
    matcher_overflow ();

  val = (i >= 0 ? Qt : Qnil);
  if (NILP (Vinhibit_changing_match_data) && i >= 0)
    for (i = 0; i < search_regs.num_regs; i++)
      if (search_regs.start[i] >= 0)
	{
	  search_regs.start[i]
	    = BYTE_TO_CHAR (search_regs.start[i] + BEGV_BYTE);
	  search_regs.end[i]
	    = BYTE_TO_CHAR (search_regs.end[i] + BEGV_BYTE);
	}

  /* Set last_thing_searched only when match data is changed.  */
  if (NILP (Vinhibit_changing_match_data))
    XSETBUFFER (last_thing_searched, current_buffer);

  return val;
}

DEFUN ("looking-at", Flooking_at, Slooking_at, 1, 1, 0,
       doc: /* Return t if text after point matches regular expression REGEXP.
This function modifies the match data that `match-beginning',
`match-end' and `match-data' access; save and restore the match
data if you want to preserve them.  */)
  (Lisp_Object regexp)
{
  return looking_at_1 (regexp, 0);
}

DEFUN ("posix-looking-at", Fposix_looking_at, Sposix_looking_at, 1, 1, 0,
       doc: /* Return t if text after point matches regular expression REGEXP.
Find the longest match, in accord with Posix regular expression rules.
This function modifies the match data that `match-beginning',
`match-end' and `match-data' access; save and restore the match
data if you want to preserve them.  */)
  (Lisp_Object regexp)
{
  return looking_at_1 (regexp, 1);
}

static Lisp_Object
string_match_1 (Lisp_Object regexp, Lisp_Object string, Lisp_Object start,
		bool posix)
{
  ptrdiff_t val;
  struct re_pattern_buffer *bufp;
  EMACS_INT pos;
  ptrdiff_t pos_byte, i;

  if (running_asynch_code)
    save_search_regs ();

  CHECK_STRING (regexp);
  CHECK_STRING (string);

  if (NILP (start))
    pos = 0, pos_byte = 0;
  else
    {
      ptrdiff_t len = SCHARS (string);

      CHECK_NUMBER (start);
      pos = XINT (start);
      if (pos < 0 && -pos <= len)
	pos = len + pos;
      else if (0 > pos || pos > len)
	args_out_of_range (string, start);
      pos_byte = string_char_to_byte (string, pos);
    }

  /* This is so set_image_of_range_1 in regex.c can find the EQV table.  */
  set_char_table_extras (BVAR (current_buffer, case_canon_table), 2,
			 BVAR (current_buffer, case_eqv_table));

  bufp = compile_pattern (regexp,
			  (NILP (Vinhibit_changing_match_data)
			   ? &search_regs : NULL),
			  (!NILP (BVAR (current_buffer, case_fold_search))
			   ? BVAR (current_buffer, case_canon_table) : Qnil),
			  posix,
			  STRING_MULTIBYTE (string));
  immediate_quit = 1;
  re_match_object = string;

  val = re_search (bufp, SSDATA (string),
		   SBYTES (string), pos_byte,
		   SBYTES (string) - pos_byte,
		   (NILP (Vinhibit_changing_match_data)
		    ? &search_regs : NULL));
  immediate_quit = 0;

  /* Set last_thing_searched only when match data is changed.  */
  if (NILP (Vinhibit_changing_match_data))
    last_thing_searched = Qt;

  if (val == -2)
    matcher_overflow ();
  if (val < 0) return Qnil;

  if (NILP (Vinhibit_changing_match_data))
    for (i = 0; i < search_regs.num_regs; i++)
      if (search_regs.start[i] >= 0)
	{
	  search_regs.start[i]
	    = string_byte_to_char (string, search_regs.start[i]);
	  search_regs.end[i]
	    = string_byte_to_char (string, search_regs.end[i]);
	}

  return make_number (string_byte_to_char (string, val));
}

DEFUN ("string-match", Fstring_match, Sstring_match, 2, 3, 0,
       doc: /* Return index of start of first match for REGEXP in STRING, or nil.
Matching ignores case if `case-fold-search' is non-nil.
If third arg START is non-nil, start search at that index in STRING.
For index of first char beyond the match, do (match-end 0).
`match-end' and `match-beginning' also give indices of substrings
matched by parenthesis constructs in the pattern.

You can use the function `match-string' to extract the substrings
matched by the parenthesis constructions in REGEXP. */)
  (Lisp_Object regexp, Lisp_Object string, Lisp_Object start)
{
  return string_match_1 (regexp, string, start, 0);
}

DEFUN ("posix-string-match", Fposix_string_match, Sposix_string_match, 2, 3, 0,
       doc: /* Return index of start of first match for REGEXP in STRING, or nil.
Find the longest match, in accord with Posix regular expression rules.
Case is ignored if `case-fold-search' is non-nil in the current buffer.
If third arg START is non-nil, start search at that index in STRING.
For index of first char beyond the match, do (match-end 0).
`match-end' and `match-beginning' also give indices of substrings
matched by parenthesis constructs in the pattern.  */)
  (Lisp_Object regexp, Lisp_Object string, Lisp_Object start)
{
  return string_match_1 (regexp, string, start, 1);
}

/* Match REGEXP against STRING, searching all of STRING,
   and return the index of the match, or negative on failure.
   This does not clobber the match data.  */

ptrdiff_t
fast_string_match (Lisp_Object regexp, Lisp_Object string)
{
  ptrdiff_t val;
  struct re_pattern_buffer *bufp;

  bufp = compile_pattern (regexp, 0, Qnil,
			  0, STRING_MULTIBYTE (string));
  immediate_quit = 1;
  re_match_object = string;

  val = re_search (bufp, SSDATA (string),
		   SBYTES (string), 0,
		   SBYTES (string), 0);
  immediate_quit = 0;
  return val;
}

/* Match REGEXP against STRING, searching all of STRING ignoring case,
   and return the index of the match, or negative on failure.
   This does not clobber the match data.
   We assume that STRING contains single-byte characters.  */

ptrdiff_t
fast_c_string_match_ignore_case (Lisp_Object regexp,
				 const char *string, ptrdiff_t len)
{
  ptrdiff_t val;
  struct re_pattern_buffer *bufp;

  regexp = string_make_unibyte (regexp);
  re_match_object = Qt;
  bufp = compile_pattern (regexp, 0,
			  Vascii_canon_table, 0,
			  0);
  immediate_quit = 1;
  val = re_search (bufp, string, len, 0, len, 0);
  immediate_quit = 0;
  return val;
}

/* Like fast_string_match but ignore case.  */

ptrdiff_t
fast_string_match_ignore_case (Lisp_Object regexp, Lisp_Object string)
{
  ptrdiff_t val;
  struct re_pattern_buffer *bufp;

  bufp = compile_pattern (regexp, 0, Vascii_canon_table,
			  0, STRING_MULTIBYTE (string));
  immediate_quit = 1;
  re_match_object = string;

  val = re_search (bufp, SSDATA (string),
		   SBYTES (string), 0,
		   SBYTES (string), 0);
  immediate_quit = 0;
  return val;
}

/* Match REGEXP against the characters after POS to LIMIT, and return
   the number of matched characters.  If STRING is non-nil, match
   against the characters in it.  In that case, POS and LIMIT are
   indices into the string.  This function doesn't modify the match
   data.  */

ptrdiff_t
fast_looking_at (Lisp_Object regexp, ptrdiff_t pos, ptrdiff_t pos_byte,
		 ptrdiff_t limit, ptrdiff_t limit_byte, Lisp_Object string)
{
  bool multibyte;
  struct re_pattern_buffer *buf;
  unsigned char *p1, *p2;
  ptrdiff_t s1, s2;
  ptrdiff_t len;

  if (STRINGP (string))
    {
      if (pos_byte < 0)
	pos_byte = string_char_to_byte (string, pos);
      if (limit_byte < 0)
	limit_byte = string_char_to_byte (string, limit);
      p1 = NULL;
      s1 = 0;
      p2 = SDATA (string);
      s2 = SBYTES (string);
      re_match_object = string;
      multibyte = STRING_MULTIBYTE (string);
    }
  else
    {
      if (pos_byte < 0)
	pos_byte = CHAR_TO_BYTE (pos);
      if (limit_byte < 0)
	limit_byte = CHAR_TO_BYTE (limit);
      pos_byte -= BEGV_BYTE;
      limit_byte -= BEGV_BYTE;
      p1 = BEGV_ADDR;
      s1 = GPT_BYTE - BEGV_BYTE;
      p2 = GAP_END_ADDR;
      s2 = ZV_BYTE - GPT_BYTE;
      if (s1 < 0)
	{
	  p2 = p1;
	  s2 = ZV_BYTE - BEGV_BYTE;
	  s1 = 0;
	}
      if (s2 < 0)
	{
	  s1 = ZV_BYTE - BEGV_BYTE;
	  s2 = 0;
	}
      re_match_object = Qnil;
      multibyte = ! NILP (BVAR (current_buffer, enable_multibyte_characters));
    }

  buf = compile_pattern (regexp, 0, Qnil, 0, multibyte);
  immediate_quit = 1;
  len = re_match_2 (buf, (char *) p1, s1, (char *) p2, s2,
		    pos_byte, NULL, limit_byte);
  immediate_quit = 0;

  return len;
}


/* The newline cache: remembering which sections of text have no newlines.  */

/* If the user has requested newline caching, make sure it's on.
   Otherwise, make sure it's off.
   This is our cheezy way of associating an action with the change of
   state of a buffer-local variable.  */
static void
newline_cache_on_off (struct buffer *buf)
{
  if (NILP (BVAR (buf, cache_long_line_scans)))
    {
      /* It should be off.  */
      if (buf->newline_cache)
        {
          free_region_cache (buf->newline_cache);
          buf->newline_cache = 0;
        }
    }
  else
    {
      /* It should be on.  */
      if (buf->newline_cache == 0)
        buf->newline_cache = new_region_cache ();
    }
}


/* Search for COUNT newlines between START/START_BYTE and END/END_BYTE.

   If COUNT is positive, search forwards; END must be >= START.
   If COUNT is negative, search backwards for the -COUNTth instance;
      END must be <= START.
   If COUNT is zero, do anything you please; run rogue, for all I care.

   If END is zero, use BEGV or ZV instead, as appropriate for the
   direction indicated by COUNT.

   If we find COUNT instances, set *SHORTAGE to zero, and return the
   position past the COUNTth match.  Note that for reverse motion
   this is not the same as the usual convention for Emacs motion commands.

   If we don't find COUNT instances before reaching END, set *SHORTAGE
   to the number of newlines left unfound, and return END.

   If BYTEPOS is not NULL, set *BYTEPOS to the byte position corresponding
   to the returned character position.

   If ALLOW_QUIT, set immediate_quit.  That's good to do
   except when inside redisplay.  */

ptrdiff_t
find_newline (ptrdiff_t start, ptrdiff_t start_byte, ptrdiff_t end,
	      ptrdiff_t end_byte, ptrdiff_t count, ptrdiff_t *shortage,
	      ptrdiff_t *bytepos, bool allow_quit)
{
  struct region_cache *newline_cache;
  int direction;

  if (count > 0)
    {
      direction = 1;
      if (!end)
	end = ZV, end_byte = ZV_BYTE;
    }
  else
    {
      direction = -1;
      if (!end)
	end = BEGV, end_byte = BEGV_BYTE;
    }
  if (end_byte == -1)
    end_byte = CHAR_TO_BYTE (end);

  newline_cache_on_off (current_buffer);
  newline_cache = current_buffer->newline_cache;

  if (shortage != 0)
    *shortage = 0;

  immediate_quit = allow_quit;

  if (count > 0)
    while (start != end)
      {
        /* Our innermost scanning loop is very simple; it doesn't know
           about gaps, buffer ends, or the newline cache.  ceiling is
           the position of the last character before the next such
           obstacle --- the last character the dumb search loop should
           examine.  */
	ptrdiff_t tem, ceiling_byte = end_byte - 1;

        /* If we're looking for a newline, consult the newline cache
           to see where we can avoid some scanning.  */
        if (newline_cache)
          {
            ptrdiff_t next_change;
            immediate_quit = 0;
            while (region_cache_forward
                   (current_buffer, newline_cache, start, &next_change))
              start = next_change;
            immediate_quit = allow_quit;

	    start_byte = CHAR_TO_BYTE (start);

            /* START should never be after END.  */
            if (start_byte > ceiling_byte)
              start_byte = ceiling_byte;

            /* Now the text after start is an unknown region, and
               next_change is the position of the next known region. */
            ceiling_byte = min (CHAR_TO_BYTE (next_change) - 1, ceiling_byte);
          }
	else if (start_byte == -1)
	  start_byte = CHAR_TO_BYTE (start);

        /* The dumb loop can only scan text stored in contiguous
           bytes. BUFFER_CEILING_OF returns the last character
           position that is contiguous, so the ceiling is the
           position after that.  */
	tem = BUFFER_CEILING_OF (start_byte);
	ceiling_byte = min (tem, ceiling_byte);

        {
          /* The termination address of the dumb loop.  */
          register unsigned char *ceiling_addr
	    = BYTE_POS_ADDR (ceiling_byte) + 1;
          register unsigned char *cursor
	    = BYTE_POS_ADDR (start_byte);
          unsigned char *base = cursor;

          while (cursor < ceiling_addr)
            {
              /* The dumb loop.  */
	      unsigned char *nl = memchr (cursor, '\n', ceiling_addr - cursor);

              /* If we're looking for newlines, cache the fact that
                 the region from start to cursor is free of them. */
              if (newline_cache)
		{
		  unsigned char *low = cursor;
		  unsigned char *lim = nl ? nl : ceiling_addr;
		  know_region_cache (current_buffer, newline_cache,
				     BYTE_TO_CHAR (low - base + start_byte),
				     BYTE_TO_CHAR (lim - base + start_byte));
		}

              if (! nl)
		break;

	      if (--count == 0)
		{
		  immediate_quit = 0;
		  if (bytepos)
		    *bytepos = nl + 1 - base + start_byte;
		  return BYTE_TO_CHAR (nl + 1 - base + start_byte);
		}
	      cursor = nl + 1;
            }

	  start_byte += ceiling_addr - base;
	  start = BYTE_TO_CHAR (start_byte);
        }
      }
  else
    while (start > end)
      {
        /* The last character to check before the next obstacle.  */
	ptrdiff_t tem, ceiling_byte = end_byte;

        /* Consult the newline cache, if appropriate.  */
        if (newline_cache)
          {
            ptrdiff_t next_change;
            immediate_quit = 0;
            while (region_cache_backward
                   (current_buffer, newline_cache, start, &next_change))
              start = next_change;
            immediate_quit = allow_quit;

	    start_byte = CHAR_TO_BYTE (start);

            /* Start should never be at or before end.  */
            if (start_byte <= ceiling_byte)
              start_byte = ceiling_byte + 1;

            /* Now the text before start is an unknown region, and
               next_change is the position of the next known region. */
            ceiling_byte = max (CHAR_TO_BYTE (next_change), ceiling_byte);
          }
	else if (start_byte == -1)
	  start_byte = CHAR_TO_BYTE (start);

        /* Stop scanning before the gap.  */
	tem = BUFFER_FLOOR_OF (start_byte - 1);
	ceiling_byte = max (tem, ceiling_byte);

        {
          /* The termination address of the dumb loop.  */
          register unsigned char *ceiling_addr = BYTE_POS_ADDR (ceiling_byte);
          register unsigned char *cursor = BYTE_POS_ADDR (start_byte - 1);
          unsigned char *base = cursor;

          while (cursor >= ceiling_addr)
            {
	      unsigned char *nl = memrchr (ceiling_addr, '\n',
					   cursor + 1 - ceiling_addr);

              /* If we're looking for newlines, cache the fact that
                 the region from after the cursor to start is free of them.  */
              if (newline_cache)
		{
		  unsigned char *low = nl ? nl : ceiling_addr - 1;
		  unsigned char *lim = cursor;
		  know_region_cache (current_buffer, newline_cache,
				     BYTE_TO_CHAR (low - base + start_byte),
				     BYTE_TO_CHAR (lim - base + start_byte));
		}

              if (! nl)
		break;

	      if (++count >= 0)
		{
		  immediate_quit = 0;
		  if (bytepos)
		    *bytepos = nl - base + start_byte;
		  return BYTE_TO_CHAR (nl - base + start_byte);
		}
	      cursor = nl - 1;
            }

	  start_byte += ceiling_addr - 1 - base;
	  start = BYTE_TO_CHAR (start_byte);
        }
      }

  immediate_quit = 0;
  if (shortage)
    *shortage = count * direction;
  if (bytepos)
    {
      *bytepos = start_byte == -1 ? CHAR_TO_BYTE (start) : start_byte;
      eassert (*bytepos == CHAR_TO_BYTE (start));
    }
  return start;
}

/* Search for COUNT instances of a line boundary.
   Start at START.  If COUNT is negative, search backwards.

   We report the resulting position by calling TEMP_SET_PT_BOTH.

   If we find COUNT instances. we position after (always after,
   even if scanning backwards) the COUNTth match, and return 0.

   If we don't find COUNT instances before reaching the end of the
   buffer (or the beginning, if scanning backwards), we return
   the number of line boundaries left unfound, and position at
   the limit we bumped up against.

   If ALLOW_QUIT, set immediate_quit.  That's good to do
   except in special cases.  */

EMACS_INT
scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
	      ptrdiff_t limit, ptrdiff_t limit_byte,
	      EMACS_INT count, bool allow_quit)
{
  int direction = ((count > 0) ? 1 : -1);

  unsigned char *cursor;
  unsigned char *base;

  ptrdiff_t ceiling;
  unsigned char *ceiling_addr;

  bool old_immediate_quit = immediate_quit;

  if (allow_quit)
    immediate_quit++;

  if (count > 0)
    {
      while (start_byte < limit_byte)
	{
	  ceiling =  BUFFER_CEILING_OF (start_byte);
	  ceiling = min (limit_byte - 1, ceiling);
	  ceiling_addr = BYTE_POS_ADDR (ceiling) + 1;
	  base = (cursor = BYTE_POS_ADDR (start_byte));

	  do
	    {
	      unsigned char *nl = memchr (cursor, '\n', ceiling_addr - cursor);
	      if (! nl)
		break;
	      if (--count == 0)