* lisp/files.el (dir-locals-read-from-file): Check file non-empty
[emacs.git] / src / search.c
blobaacdbe33eef2fcef7d444e942f14bc96c1a03ce8
1 /* String search routines for GNU Emacs.
3 Copyright (C) 1985-1987, 1993-1994, 1997-1999, 2001-2012
4 Free Software Foundation, Inc.
6 This file is part of GNU Emacs.
8 GNU Emacs is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
13 GNU Emacs is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
22 #include <config.h>
24 #include "lisp.h"
25 #include "syntax.h"
26 #include "category.h"
27 #include "character.h"
28 #include "buffer.h"
29 #include "charset.h"
30 #include "region-cache.h"
31 #include "commands.h"
32 #include "blockinput.h"
33 #include "intervals.h"
35 #include <sys/types.h>
36 #include "regex.h"
38 #define REGEXP_CACHE_SIZE 20
40 /* If the regexp is non-nil, then the buffer contains the compiled form
41 of that regexp, suitable for searching. */
42 struct regexp_cache
44 struct regexp_cache *next;
45 Lisp_Object regexp, whitespace_regexp;
46 /* Syntax table for which the regexp applies. We need this because
47 of character classes. If this is t, then the compiled pattern is valid
48 for any syntax-table. */
49 Lisp_Object syntax_table;
50 struct re_pattern_buffer buf;
51 char fastmap[0400];
52 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
53 char posix;
56 /* The instances of that struct. */
57 static struct regexp_cache searchbufs[REGEXP_CACHE_SIZE];
59 /* The head of the linked list; points to the most recently used buffer. */
60 static struct regexp_cache *searchbuf_head;
63 /* Every call to re_match, etc., must pass &search_regs as the regs
64 argument unless you can show it is unnecessary (i.e., if re_match
65 is certainly going to be called again before region-around-match
66 can be called).
68 Since the registers are now dynamically allocated, we need to make
69 sure not to refer to the Nth register before checking that it has
70 been allocated by checking search_regs.num_regs.
72 The regex code keeps track of whether it has allocated the search
73 buffer using bits in the re_pattern_buffer. This means that whenever
74 you compile a new pattern, it completely forgets whether it has
75 allocated any registers, and will allocate new registers the next
76 time you call a searching or matching function. Therefore, we need
77 to call re_set_registers after compiling a new pattern or after
78 setting the match registers, so that the regex functions will be
79 able to free or re-allocate it properly. */
80 static struct re_registers search_regs;
82 /* The buffer in which the last search was performed, or
83 Qt if the last search was done in a string;
84 Qnil if no searching has been done yet. */
85 static Lisp_Object last_thing_searched;
87 /* Error condition signaled when regexp compile_pattern fails. */
88 static Lisp_Object Qinvalid_regexp;
90 /* Error condition used for failing searches. */
91 static Lisp_Object Qsearch_failed;
93 static void set_search_regs (ptrdiff_t, ptrdiff_t);
94 static void save_search_regs (void);
95 static EMACS_INT simple_search (EMACS_INT, unsigned char *, ptrdiff_t,
96 ptrdiff_t, Lisp_Object, ptrdiff_t, ptrdiff_t,
97 ptrdiff_t, ptrdiff_t);
98 static EMACS_INT boyer_moore (EMACS_INT, unsigned char *, ptrdiff_t,
99 Lisp_Object, Lisp_Object, ptrdiff_t,
100 ptrdiff_t, int);
101 static EMACS_INT search_buffer (Lisp_Object, ptrdiff_t, ptrdiff_t,
102 ptrdiff_t, ptrdiff_t, EMACS_INT, int,
103 Lisp_Object, Lisp_Object, int);
105 static _Noreturn void
106 matcher_overflow (void)
108 error ("Stack overflow in regexp matcher");
111 /* Compile a regexp and signal a Lisp error if anything goes wrong.
112 PATTERN is the pattern to compile.
113 CP is the place to put the result.
114 TRANSLATE is a translation table for ignoring case, or nil for none.
115 POSIX is nonzero if we want full backtracking (POSIX style)
116 for this pattern. 0 means backtrack only enough to get a valid match.
118 The behavior also depends on Vsearch_spaces_regexp. */
120 static void
121 compile_pattern_1 (struct regexp_cache *cp, Lisp_Object pattern, Lisp_Object translate, int posix)
123 char *val;
124 reg_syntax_t old;
126 cp->regexp = Qnil;
127 cp->buf.translate = (! NILP (translate) ? translate : make_number (0));
128 cp->posix = posix;
129 cp->buf.multibyte = STRING_MULTIBYTE (pattern);
130 cp->buf.charset_unibyte = charset_unibyte;
131 if (STRINGP (Vsearch_spaces_regexp))
132 cp->whitespace_regexp = Vsearch_spaces_regexp;
133 else
134 cp->whitespace_regexp = Qnil;
136 /* rms: I think BLOCK_INPUT is not needed here any more,
137 because regex.c defines malloc to call xmalloc.
138 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
139 So let's turn it off. */
140 /* BLOCK_INPUT; */
141 old = re_set_syntax (RE_SYNTAX_EMACS
142 | (posix ? 0 : RE_NO_POSIX_BACKTRACKING));
144 if (STRINGP (Vsearch_spaces_regexp))
145 re_set_whitespace_regexp (SSDATA (Vsearch_spaces_regexp));
146 else
147 re_set_whitespace_regexp (NULL);
149 val = (char *) re_compile_pattern (SSDATA (pattern),
150 SBYTES (pattern), &cp->buf);
152 /* If the compiled pattern hard codes some of the contents of the
153 syntax-table, it can only be reused with *this* syntax table. */
154 cp->syntax_table = cp->buf.used_syntax ? BVAR (current_buffer, syntax_table) : Qt;
156 re_set_whitespace_regexp (NULL);
158 re_set_syntax (old);
159 /* unblock_input (); */
160 if (val)
161 xsignal1 (Qinvalid_regexp, build_string (val));
163 cp->regexp = Fcopy_sequence (pattern);
166 /* Shrink each compiled regexp buffer in the cache
167 to the size actually used right now.
168 This is called from garbage collection. */
170 void
171 shrink_regexp_cache (void)
173 struct regexp_cache *cp;
175 for (cp = searchbuf_head; cp != 0; cp = cp->next)
177 cp->buf.allocated = cp->buf.used;
178 cp->buf.buffer = xrealloc (cp->buf.buffer, cp->buf.used);
182 /* Clear the regexp cache w.r.t. a particular syntax table,
183 because it was changed.
184 There is no danger of memory leak here because re_compile_pattern
185 automagically manages the memory in each re_pattern_buffer struct,
186 based on its `allocated' and `buffer' values. */
187 void
188 clear_regexp_cache (void)
190 int i;
192 for (i = 0; i < REGEXP_CACHE_SIZE; ++i)
193 /* It's tempting to compare with the syntax-table we've actually changed,
194 but it's not sufficient because char-table inheritance means that
195 modifying one syntax-table can change others at the same time. */
196 if (!EQ (searchbufs[i].syntax_table, Qt))
197 searchbufs[i].regexp = Qnil;
200 /* Compile a regexp if necessary, but first check to see if there's one in
201 the cache.
202 PATTERN is the pattern to compile.
203 TRANSLATE is a translation table for ignoring case, or nil for none.
204 REGP is the structure that says where to store the "register"
205 values that will result from matching this pattern.
206 If it is 0, we should compile the pattern not to record any
207 subexpression bounds.
208 POSIX is nonzero if we want full backtracking (POSIX style)
209 for this pattern. 0 means backtrack only enough to get a valid match. */
211 struct re_pattern_buffer *
212 compile_pattern (Lisp_Object pattern, struct re_registers *regp, Lisp_Object translate, int posix, int multibyte)
214 struct regexp_cache *cp, **cpp;
216 for (cpp = &searchbuf_head; ; cpp = &cp->next)
218 cp = *cpp;
219 /* Entries are initialized to nil, and may be set to nil by
220 compile_pattern_1 if the pattern isn't valid. Don't apply
221 string accessors in those cases. However, compile_pattern_1
222 is only applied to the cache entry we pick here to reuse. So
223 nil should never appear before a non-nil entry. */
224 if (NILP (cp->regexp))
225 goto compile_it;
226 if (SCHARS (cp->regexp) == SCHARS (pattern)
227 && STRING_MULTIBYTE (cp->regexp) == STRING_MULTIBYTE (pattern)
228 && !NILP (Fstring_equal (cp->regexp, pattern))
229 && EQ (cp->buf.translate, (! NILP (translate) ? translate : make_number (0)))
230 && cp->posix == posix
231 && (EQ (cp->syntax_table, Qt)
232 || EQ (cp->syntax_table, BVAR (current_buffer, syntax_table)))
233 && !NILP (Fequal (cp->whitespace_regexp, Vsearch_spaces_regexp))
234 && cp->buf.charset_unibyte == charset_unibyte)
235 break;
237 /* If we're at the end of the cache, compile into the nil cell
238 we found, or the last (least recently used) cell with a
239 string value. */
240 if (cp->next == 0)
242 compile_it:
243 compile_pattern_1 (cp, pattern, translate, posix);
244 break;
248 /* When we get here, cp (aka *cpp) contains the compiled pattern,
249 either because we found it in the cache or because we just compiled it.
250 Move it to the front of the queue to mark it as most recently used. */
251 *cpp = cp->next;
252 cp->next = searchbuf_head;
253 searchbuf_head = cp;
255 /* Advise the searching functions about the space we have allocated
256 for register data. */
257 if (regp)
258 re_set_registers (&cp->buf, regp, regp->num_regs, regp->start, regp->end);
260 /* The compiled pattern can be used both for multibyte and unibyte
261 target. But, we have to tell which the pattern is used for. */
262 cp->buf.target_multibyte = multibyte;
264 return &cp->buf;
268 static Lisp_Object
269 looking_at_1 (Lisp_Object string, int posix)
271 Lisp_Object val;
272 unsigned char *p1, *p2;
273 ptrdiff_t s1, s2;
274 register ptrdiff_t i;
275 struct re_pattern_buffer *bufp;
277 if (running_asynch_code)
278 save_search_regs ();
280 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
281 set_char_table_extras (BVAR (current_buffer, case_canon_table), 2,
282 BVAR (current_buffer, case_eqv_table));
284 CHECK_STRING (string);
285 bufp = compile_pattern (string,
286 (NILP (Vinhibit_changing_match_data)
287 ? &search_regs : NULL),
288 (!NILP (BVAR (current_buffer, case_fold_search))
289 ? BVAR (current_buffer, case_canon_table) : Qnil),
290 posix,
291 !NILP (BVAR (current_buffer, enable_multibyte_characters)));
293 immediate_quit = 1;
294 QUIT; /* Do a pending quit right away, to avoid paradoxical behavior */
296 /* Get pointers and sizes of the two strings
297 that make up the visible portion of the buffer. */
299 p1 = BEGV_ADDR;
300 s1 = GPT_BYTE - BEGV_BYTE;
301 p2 = GAP_END_ADDR;
302 s2 = ZV_BYTE - GPT_BYTE;
303 if (s1 < 0)
305 p2 = p1;
306 s2 = ZV_BYTE - BEGV_BYTE;
307 s1 = 0;
309 if (s2 < 0)
311 s1 = ZV_BYTE - BEGV_BYTE;
312 s2 = 0;
315 re_match_object = Qnil;
317 i = re_match_2 (bufp, (char *) p1, s1, (char *) p2, s2,
318 PT_BYTE - BEGV_BYTE,
319 (NILP (Vinhibit_changing_match_data)
320 ? &search_regs : NULL),
321 ZV_BYTE - BEGV_BYTE);
322 immediate_quit = 0;
324 if (i == -2)
325 matcher_overflow ();
327 val = (0 <= i ? Qt : Qnil);
328 if (NILP (Vinhibit_changing_match_data) && i >= 0)
329 for (i = 0; i < search_regs.num_regs; i++)
330 if (search_regs.start[i] >= 0)
332 search_regs.start[i]
333 = BYTE_TO_CHAR (search_regs.start[i] + BEGV_BYTE);
334 search_regs.end[i]
335 = BYTE_TO_CHAR (search_regs.end[i] + BEGV_BYTE);
338 /* Set last_thing_searched only when match data is changed. */
339 if (NILP (Vinhibit_changing_match_data))
340 XSETBUFFER (last_thing_searched, current_buffer);
342 return val;
345 DEFUN ("looking-at", Flooking_at, Slooking_at, 1, 1, 0,
346 doc: /* Return t if text after point matches regular expression REGEXP.
347 This function modifies the match data that `match-beginning',
348 `match-end' and `match-data' access; save and restore the match
349 data if you want to preserve them. */)
350 (Lisp_Object regexp)
352 return looking_at_1 (regexp, 0);
355 DEFUN ("posix-looking-at", Fposix_looking_at, Sposix_looking_at, 1, 1, 0,
356 doc: /* Return t if text after point matches regular expression REGEXP.
357 Find the longest match, in accord with Posix regular expression rules.
358 This function modifies the match data that `match-beginning',
359 `match-end' and `match-data' access; save and restore the match
360 data if you want to preserve them. */)
361 (Lisp_Object regexp)
363 return looking_at_1 (regexp, 1);
366 static Lisp_Object
367 string_match_1 (Lisp_Object regexp, Lisp_Object string, Lisp_Object start, int posix)
369 ptrdiff_t val;
370 struct re_pattern_buffer *bufp;
371 EMACS_INT pos;
372 ptrdiff_t pos_byte, i;
374 if (running_asynch_code)
375 save_search_regs ();
377 CHECK_STRING (regexp);
378 CHECK_STRING (string);
380 if (NILP (start))
381 pos = 0, pos_byte = 0;
382 else
384 ptrdiff_t len = SCHARS (string);
386 CHECK_NUMBER (start);
387 pos = XINT (start);
388 if (pos < 0 && -pos <= len)
389 pos = len + pos;
390 else if (0 > pos || pos > len)
391 args_out_of_range (string, start);
392 pos_byte = string_char_to_byte (string, pos);
395 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
396 set_char_table_extras (BVAR (current_buffer, case_canon_table), 2,
397 BVAR (current_buffer, case_eqv_table));
399 bufp = compile_pattern (regexp,
400 (NILP (Vinhibit_changing_match_data)
401 ? &search_regs : NULL),
402 (!NILP (BVAR (current_buffer, case_fold_search))
403 ? BVAR (current_buffer, case_canon_table) : Qnil),
404 posix,
405 STRING_MULTIBYTE (string));
406 immediate_quit = 1;
407 re_match_object = string;
409 val = re_search (bufp, SSDATA (string),
410 SBYTES (string), pos_byte,
411 SBYTES (string) - pos_byte,
412 (NILP (Vinhibit_changing_match_data)
413 ? &search_regs : NULL));
414 immediate_quit = 0;
416 /* Set last_thing_searched only when match data is changed. */
417 if (NILP (Vinhibit_changing_match_data))
418 last_thing_searched = Qt;
420 if (val == -2)
421 matcher_overflow ();
422 if (val < 0) return Qnil;
424 if (NILP (Vinhibit_changing_match_data))
425 for (i = 0; i < search_regs.num_regs; i++)
426 if (search_regs.start[i] >= 0)
428 search_regs.start[i]
429 = string_byte_to_char (string, search_regs.start[i]);
430 search_regs.end[i]
431 = string_byte_to_char (string, search_regs.end[i]);
434 return make_number (string_byte_to_char (string, val));
437 DEFUN ("string-match", Fstring_match, Sstring_match, 2, 3, 0,
438 doc: /* Return index of start of first match for REGEXP in STRING, or nil.
439 Matching ignores case if `case-fold-search' is non-nil.
440 If third arg START is non-nil, start search at that index in STRING.
441 For index of first char beyond the match, do (match-end 0).
442 `match-end' and `match-beginning' also give indices of substrings
443 matched by parenthesis constructs in the pattern.
445 You can use the function `match-string' to extract the substrings
446 matched by the parenthesis constructions in REGEXP. */)
447 (Lisp_Object regexp, Lisp_Object string, Lisp_Object start)
449 return string_match_1 (regexp, string, start, 0);
452 DEFUN ("posix-string-match", Fposix_string_match, Sposix_string_match, 2, 3, 0,
453 doc: /* Return index of start of first match for REGEXP in STRING, or nil.
454 Find the longest match, in accord with Posix regular expression rules.
455 Case is ignored if `case-fold-search' is non-nil in the current buffer.
456 If third arg START is non-nil, start search at that index in STRING.
457 For index of first char beyond the match, do (match-end 0).
458 `match-end' and `match-beginning' also give indices of substrings
459 matched by parenthesis constructs in the pattern. */)
460 (Lisp_Object regexp, Lisp_Object string, Lisp_Object start)
462 return string_match_1 (regexp, string, start, 1);
465 /* Match REGEXP against STRING, searching all of STRING,
466 and return the index of the match, or negative on failure.
467 This does not clobber the match data. */
469 ptrdiff_t
470 fast_string_match (Lisp_Object regexp, Lisp_Object string)
472 ptrdiff_t val;
473 struct re_pattern_buffer *bufp;
475 bufp = compile_pattern (regexp, 0, Qnil,
476 0, STRING_MULTIBYTE (string));
477 immediate_quit = 1;
478 re_match_object = string;
480 val = re_search (bufp, SSDATA (string),
481 SBYTES (string), 0,
482 SBYTES (string), 0);
483 immediate_quit = 0;
484 return val;
487 /* Match REGEXP against STRING, searching all of STRING ignoring case,
488 and return the index of the match, or negative on failure.
489 This does not clobber the match data.
490 We assume that STRING contains single-byte characters. */
492 ptrdiff_t
493 fast_c_string_match_ignore_case (Lisp_Object regexp,
494 const char *string, ptrdiff_t len)
496 ptrdiff_t val;
497 struct re_pattern_buffer *bufp;
499 regexp = string_make_unibyte (regexp);
500 re_match_object = Qt;
501 bufp = compile_pattern (regexp, 0,
502 Vascii_canon_table, 0,
504 immediate_quit = 1;
505 val = re_search (bufp, string, len, 0, len, 0);
506 immediate_quit = 0;
507 return val;
510 /* Like fast_string_match but ignore case. */
512 ptrdiff_t
513 fast_string_match_ignore_case (Lisp_Object regexp, Lisp_Object string)
515 ptrdiff_t val;
516 struct re_pattern_buffer *bufp;
518 bufp = compile_pattern (regexp, 0, Vascii_canon_table,
519 0, STRING_MULTIBYTE (string));
520 immediate_quit = 1;
521 re_match_object = string;
523 val = re_search (bufp, SSDATA (string),
524 SBYTES (string), 0,
525 SBYTES (string), 0);
526 immediate_quit = 0;
527 return val;
530 /* Match REGEXP against the characters after POS to LIMIT, and return
531 the number of matched characters. If STRING is non-nil, match
532 against the characters in it. In that case, POS and LIMIT are
533 indices into the string. This function doesn't modify the match
534 data. */
536 ptrdiff_t
537 fast_looking_at (Lisp_Object regexp, ptrdiff_t pos, ptrdiff_t pos_byte, ptrdiff_t limit, ptrdiff_t limit_byte, Lisp_Object string)
539 int multibyte;
540 struct re_pattern_buffer *buf;
541 unsigned char *p1, *p2;
542 ptrdiff_t s1, s2;
543 ptrdiff_t len;
545 if (STRINGP (string))
547 if (pos_byte < 0)
548 pos_byte = string_char_to_byte (string, pos);
549 if (limit_byte < 0)
550 limit_byte = string_char_to_byte (string, limit);
551 p1 = NULL;
552 s1 = 0;
553 p2 = SDATA (string);
554 s2 = SBYTES (string);
555 re_match_object = string;
556 multibyte = STRING_MULTIBYTE (string);
558 else
560 if (pos_byte < 0)
561 pos_byte = CHAR_TO_BYTE (pos);
562 if (limit_byte < 0)
563 limit_byte = CHAR_TO_BYTE (limit);
564 pos_byte -= BEGV_BYTE;
565 limit_byte -= BEGV_BYTE;
566 p1 = BEGV_ADDR;
567 s1 = GPT_BYTE - BEGV_BYTE;
568 p2 = GAP_END_ADDR;
569 s2 = ZV_BYTE - GPT_BYTE;
570 if (s1 < 0)
572 p2 = p1;
573 s2 = ZV_BYTE - BEGV_BYTE;
574 s1 = 0;
576 if (s2 < 0)
578 s1 = ZV_BYTE - BEGV_BYTE;
579 s2 = 0;
581 re_match_object = Qnil;
582 multibyte = ! NILP (BVAR (current_buffer, enable_multibyte_characters));
585 buf = compile_pattern (regexp, 0, Qnil, 0, multibyte);
586 immediate_quit = 1;
587 len = re_match_2 (buf, (char *) p1, s1, (char *) p2, s2,
588 pos_byte, NULL, limit_byte);
589 immediate_quit = 0;
591 return len;
595 /* The newline cache: remembering which sections of text have no newlines. */
597 /* If the user has requested newline caching, make sure it's on.
598 Otherwise, make sure it's off.
599 This is our cheezy way of associating an action with the change of
600 state of a buffer-local variable. */
601 static void
602 newline_cache_on_off (struct buffer *buf)
604 if (NILP (BVAR (buf, cache_long_line_scans)))
606 /* It should be off. */
607 if (buf->newline_cache)
609 free_region_cache (buf->newline_cache);
610 buf->newline_cache = 0;
613 else
615 /* It should be on. */
616 if (buf->newline_cache == 0)
617 buf->newline_cache = new_region_cache ();
622 /* Search for COUNT instances of the character TARGET between START and END.
624 If COUNT is positive, search forwards; END must be >= START.
625 If COUNT is negative, search backwards for the -COUNTth instance;
626 END must be <= START.
627 If COUNT is zero, do anything you please; run rogue, for all I care.
629 If END is zero, use BEGV or ZV instead, as appropriate for the
630 direction indicated by COUNT.
632 If we find COUNT instances, set *SHORTAGE to zero, and return the
633 position past the COUNTth match. Note that for reverse motion
634 this is not the same as the usual convention for Emacs motion commands.
636 If we don't find COUNT instances before reaching END, set *SHORTAGE
637 to the number of TARGETs left unfound, and return END.
639 If ALLOW_QUIT, set immediate_quit. That's good to do
640 except when inside redisplay. */
642 ptrdiff_t
643 scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
644 ptrdiff_t count, ptrdiff_t *shortage, bool allow_quit)
646 struct region_cache *newline_cache;
647 int direction;
649 if (count > 0)
651 direction = 1;
652 if (! end) end = ZV;
654 else
656 direction = -1;
657 if (! end) end = BEGV;
660 newline_cache_on_off (current_buffer);
661 newline_cache = current_buffer->newline_cache;
663 if (shortage != 0)
664 *shortage = 0;
666 immediate_quit = allow_quit;
668 if (count > 0)
669 while (start != end)
671 /* Our innermost scanning loop is very simple; it doesn't know
672 about gaps, buffer ends, or the newline cache. ceiling is
673 the position of the last character before the next such
674 obstacle --- the last character the dumb search loop should
675 examine. */
676 ptrdiff_t ceiling_byte = CHAR_TO_BYTE (end) - 1;
677 ptrdiff_t start_byte;
678 ptrdiff_t tem;
680 /* If we're looking for a newline, consult the newline cache
681 to see where we can avoid some scanning. */
682 if (target == '\n' && newline_cache)
684 ptrdiff_t next_change;
685 immediate_quit = 0;
686 while (region_cache_forward
687 (current_buffer, newline_cache, start, &next_change))
688 start = next_change;
689 immediate_quit = allow_quit;
691 start_byte = CHAR_TO_BYTE (start);
693 /* START should never be after END. */
694 if (start_byte > ceiling_byte)
695 start_byte = ceiling_byte;
697 /* Now the text after start is an unknown region, and
698 next_change is the position of the next known region. */
699 ceiling_byte = min (CHAR_TO_BYTE (next_change) - 1, ceiling_byte);
701 else
702 start_byte = CHAR_TO_BYTE (start);
704 /* The dumb loop can only scan text stored in contiguous
705 bytes. BUFFER_CEILING_OF returns the last character
706 position that is contiguous, so the ceiling is the
707 position after that. */
708 tem = BUFFER_CEILING_OF (start_byte);
709 ceiling_byte = min (tem, ceiling_byte);
712 /* The termination address of the dumb loop. */
713 register unsigned char *ceiling_addr
714 = BYTE_POS_ADDR (ceiling_byte) + 1;
715 register unsigned char *cursor
716 = BYTE_POS_ADDR (start_byte);
717 unsigned char *base = cursor;
719 while (cursor < ceiling_addr)
721 unsigned char *scan_start = cursor;
723 /* The dumb loop. */
724 while (*cursor != target && ++cursor < ceiling_addr)
727 /* If we're looking for newlines, cache the fact that
728 the region from start to cursor is free of them. */
729 if (target == '\n' && newline_cache)
730 know_region_cache (current_buffer, newline_cache,
731 BYTE_TO_CHAR (start_byte + scan_start - base),
732 BYTE_TO_CHAR (start_byte + cursor - base));
734 /* Did we find the target character? */
735 if (cursor < ceiling_addr)
737 if (--count == 0)
739 immediate_quit = 0;
740 return BYTE_TO_CHAR (start_byte + cursor - base + 1);
742 cursor++;
746 start = BYTE_TO_CHAR (start_byte + cursor - base);
749 else
750 while (start > end)
752 /* The last character to check before the next obstacle. */
753 ptrdiff_t ceiling_byte = CHAR_TO_BYTE (end);
754 ptrdiff_t start_byte;
755 ptrdiff_t tem;
757 /* Consult the newline cache, if appropriate. */
758 if (target == '\n' && newline_cache)
760 ptrdiff_t next_change;
761 immediate_quit = 0;
762 while (region_cache_backward
763 (current_buffer, newline_cache, start, &next_change))
764 start = next_change;
765 immediate_quit = allow_quit;
767 start_byte = CHAR_TO_BYTE (start);
769 /* Start should never be at or before end. */
770 if (start_byte <= ceiling_byte)
771 start_byte = ceiling_byte + 1;
773 /* Now the text before start is an unknown region, and
774 next_change is the position of the next known region. */
775 ceiling_byte = max (CHAR_TO_BYTE (next_change), ceiling_byte);
777 else
778 start_byte = CHAR_TO_BYTE (start);
780 /* Stop scanning before the gap. */
781 tem = BUFFER_FLOOR_OF (start_byte - 1);
782 ceiling_byte = max (tem, ceiling_byte);
785 /* The termination address of the dumb loop. */
786 register unsigned char *ceiling_addr = BYTE_POS_ADDR (ceiling_byte);
787 register unsigned char *cursor = BYTE_POS_ADDR (start_byte - 1);
788 unsigned char *base = cursor;
790 while (cursor >= ceiling_addr)
792 unsigned char *scan_start = cursor;
794 while (*cursor != target && --cursor >= ceiling_addr)
797 /* If we're looking for newlines, cache the fact that
798 the region from after the cursor to start is free of them. */
799 if (target == '\n' && newline_cache)
800 know_region_cache (current_buffer, newline_cache,
801 BYTE_TO_CHAR (start_byte + cursor - base),
802 BYTE_TO_CHAR (start_byte + scan_start - base));
804 /* Did we find the target character? */
805 if (cursor >= ceiling_addr)
807 if (++count >= 0)
809 immediate_quit = 0;
810 return BYTE_TO_CHAR (start_byte + cursor - base);
812 cursor--;
816 start = BYTE_TO_CHAR (start_byte + cursor - base);
820 immediate_quit = 0;
821 if (shortage != 0)
822 *shortage = count * direction;
823 return start;
826 /* Search for COUNT instances of a line boundary, which means either a
827 newline or (if selective display enabled) a carriage return.
828 Start at START. If COUNT is negative, search backwards.
830 We report the resulting position by calling TEMP_SET_PT_BOTH.
832 If we find COUNT instances. we position after (always after,
833 even if scanning backwards) the COUNTth match, and return 0.
835 If we don't find COUNT instances before reaching the end of the
836 buffer (or the beginning, if scanning backwards), we return
837 the number of line boundaries left unfound, and position at
838 the limit we bumped up against.
840 If ALLOW_QUIT, set immediate_quit. That's good to do
841 except in special cases. */
843 EMACS_INT
844 scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
845 ptrdiff_t limit, ptrdiff_t limit_byte,
846 EMACS_INT count, bool allow_quit)
848 int direction = ((count > 0) ? 1 : -1);
850 unsigned char *cursor;
851 unsigned char *base;
853 ptrdiff_t ceiling;
854 unsigned char *ceiling_addr;
856 bool old_immediate_quit = immediate_quit;
858 /* The code that follows is like scan_buffer
859 but checks for either newline or carriage return. */
861 if (allow_quit)
862 immediate_quit++;
864 start_byte = CHAR_TO_BYTE (start);
866 if (count > 0)
868 while (start_byte < limit_byte)
870 ceiling = BUFFER_CEILING_OF (start_byte);
871 ceiling = min (limit_byte - 1, ceiling);
872 ceiling_addr = BYTE_POS_ADDR (ceiling) + 1;
873 base = (cursor = BYTE_POS_ADDR (start_byte));
874 while (1)
876 while (*cursor != '\n' && ++cursor != ceiling_addr)
879 if (cursor != ceiling_addr)
881 if (--count == 0)
883 immediate_quit = old_immediate_quit;
884 start_byte = start_byte + cursor - base + 1;
885 start = BYTE_TO_CHAR (start_byte);
886 TEMP_SET_PT_BOTH (start, start_byte);
887 return 0;
889 else
890 if (++cursor == ceiling_addr)
891 break;
893 else
894 break;
896 start_byte += cursor - base;
899 else
901 while (start_byte > limit_byte)
903 ceiling = BUFFER_FLOOR_OF (start_byte - 1);
904 ceiling = max (limit_byte, ceiling);
905 ceiling_addr = BYTE_POS_ADDR (ceiling) - 1;
906 base = (cursor = BYTE_POS_ADDR (start_byte - 1) + 1);
907 while (1)
909 while (--cursor != ceiling_addr && *cursor != '\n')
912 if (cursor != ceiling_addr)
914 if (++count == 0)
916 immediate_quit = old_immediate_quit;
917 /* Return the position AFTER the match we found. */
918 start_byte = start_byte + cursor - base + 1;
919 start = BYTE_TO_CHAR (start_byte);
920 TEMP_SET_PT_BOTH (start, start_byte);
921 return 0;
924 else
925 break;
927 /* Here we add 1 to compensate for the last decrement
928 of CURSOR, which took it past the valid range. */
929 start_byte += cursor - base + 1;
933 TEMP_SET_PT_BOTH (limit, limit_byte);
934 immediate_quit = old_immediate_quit;
936 return count * direction;
939 ptrdiff_t
940 find_next_newline_no_quit (ptrdiff_t from, ptrdiff_t cnt)
942 return scan_buffer ('\n', from, 0, cnt, (ptrdiff_t *) 0, 0);
945 /* Like find_next_newline, but returns position before the newline,
946 not after, and only search up to TO. This isn't just
947 find_next_newline (...)-1, because you might hit TO. */
949 ptrdiff_t
950 find_before_next_newline (ptrdiff_t from, ptrdiff_t to, ptrdiff_t cnt)
952 ptrdiff_t shortage;
953 ptrdiff_t pos = scan_buffer ('\n', from, to, cnt, &shortage, 1);
955 if (shortage == 0)
956 pos--;
958 return pos;
961 /* Subroutines of Lisp buffer search functions. */
963 static Lisp_Object
964 search_command (Lisp_Object string, Lisp_Object bound, Lisp_Object noerror,
965 Lisp_Object count, int direction, int RE, int posix)
967 register EMACS_INT np;
968 EMACS_INT lim;
969 ptrdiff_t lim_byte;
970 EMACS_INT n = direction;
972 if (!NILP (count))
974 CHECK_NUMBER (count);
975 n *= XINT (count);
978 CHECK_STRING (string);
979 if (NILP (bound))
981 if (n > 0)
982 lim = ZV, lim_byte = ZV_BYTE;
983 else
984 lim = BEGV, lim_byte = BEGV_BYTE;
986 else
988 CHECK_NUMBER_COERCE_MARKER (bound);
989 lim = XINT (bound);
990 if (n > 0 ? lim < PT : lim > PT)
991 error ("Invalid search bound (wrong side of point)");
992 if (lim > ZV)
993 lim = ZV, lim_byte = ZV_BYTE;
994 else if (lim < BEGV)
995 lim = BEGV, lim_byte = BEGV_BYTE;
996 else
997 lim_byte = CHAR_TO_BYTE (lim);
1000 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
1001 set_char_table_extras (BVAR (current_buffer, case_canon_table), 2,
1002 BVAR (current_buffer, case_eqv_table));
1004 np = search_buffer (string, PT, PT_BYTE, lim, lim_byte, n, RE,
1005 (!NILP (BVAR (current_buffer, case_fold_search))
1006 ? BVAR (current_buffer, case_canon_table)
1007 : Qnil),
1008 (!NILP (BVAR (current_buffer, case_fold_search))
1009 ? BVAR (current_buffer, case_eqv_table)
1010 : Qnil),
1011 posix);
1012 if (np <= 0)
1014 if (NILP (noerror))
1015 xsignal1 (Qsearch_failed, string);
1017 if (!EQ (noerror, Qt))
1019 if (lim < BEGV || lim > ZV)
1020 emacs_abort ();
1021 SET_PT_BOTH (lim, lim_byte);
1022 return Qnil;
1023 #if 0 /* This would be clean, but maybe programs depend on
1024 a value of nil here. */
1025 np = lim;
1026 #endif
1028 else
1029 return Qnil;
1032 if (np < BEGV || np > ZV)
1033 emacs_abort ();
1035 SET_PT (np);
1037 return make_number (np);
1040 /* Return 1 if REGEXP it matches just one constant string. */
1042 static int
1043 trivial_regexp_p (Lisp_Object regexp)
1045 ptrdiff_t len = SBYTES (regexp);
1046 unsigned char *s = SDATA (regexp);
1047 while (--len >= 0)
1049 switch (*s++)
1051 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1052 return 0;
1053 case '\\':
1054 if (--len < 0)
1055 return 0;
1056 switch (*s++)
1058 case '|': case '(': case ')': case '`': case '\'': case 'b':
1059 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1060 case 'S': case '=': case '{': case '}': case '_':
1061 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1062 case '1': case '2': case '3': case '4': case '5':
1063 case '6': case '7': case '8': case '9':
1064 return 0;
1068 return 1;
1071 /* Search for the n'th occurrence of STRING in the current buffer,
1072 starting at position POS and stopping at position LIM,
1073 treating STRING as a literal string if RE is false or as
1074 a regular expression if RE is true.
1076 If N is positive, searching is forward and LIM must be greater than POS.
1077 If N is negative, searching is backward and LIM must be less than POS.
1079 Returns -x if x occurrences remain to be found (x > 0),
1080 or else the position at the beginning of the Nth occurrence
1081 (if searching backward) or the end (if searching forward).
1083 POSIX is nonzero if we want full backtracking (POSIX style)
1084 for this pattern. 0 means backtrack only enough to get a valid match. */
1086 #define TRANSLATE(out, trt, d) \
1087 do \
1089 if (! NILP (trt)) \
1091 Lisp_Object temp; \
1092 temp = Faref (trt, make_number (d)); \
1093 if (INTEGERP (temp)) \
1094 out = XINT (temp); \
1095 else \
1096 out = d; \
1098 else \
1099 out = d; \
1101 while (0)
1103 /* Only used in search_buffer, to record the end position of the match
1104 when searching regexps and SEARCH_REGS should not be changed
1105 (i.e. Vinhibit_changing_match_data is non-nil). */
1106 static struct re_registers search_regs_1;
1108 static EMACS_INT
1109 search_buffer (Lisp_Object string, ptrdiff_t pos, ptrdiff_t pos_byte,
1110 ptrdiff_t lim, ptrdiff_t lim_byte, EMACS_INT n,
1111 int RE, Lisp_Object trt, Lisp_Object inverse_trt, int posix)
1113 ptrdiff_t len = SCHARS (string);
1114 ptrdiff_t len_byte = SBYTES (string);
1115 register ptrdiff_t i;
1117 if (running_asynch_code)
1118 save_search_regs ();
1120 /* Searching 0 times means don't move. */
1121 /* Null string is found at starting position. */
1122 if (len == 0 || n == 0)
1124 set_search_regs (pos_byte, 0);
1125 return pos;
1128 if (RE && !(trivial_regexp_p (string) && NILP (Vsearch_spaces_regexp)))
1130 unsigned char *p1, *p2;
1131 ptrdiff_t s1, s2;
1132 struct re_pattern_buffer *bufp;
1134 bufp = compile_pattern (string,
1135 (NILP (Vinhibit_changing_match_data)
1136 ? &search_regs : &search_regs_1),
1137 trt, posix,
1138 !NILP (BVAR (current_buffer, enable_multibyte_characters)));
1140 immediate_quit = 1; /* Quit immediately if user types ^G,
1141 because letting this function finish
1142 can take too long. */
1143 QUIT; /* Do a pending quit right away,
1144 to avoid paradoxical behavior */
1145 /* Get pointers and sizes of the two strings
1146 that make up the visible portion of the buffer. */
1148 p1 = BEGV_ADDR;
1149 s1 = GPT_BYTE - BEGV_BYTE;
1150 p2 = GAP_END_ADDR;
1151 s2 = ZV_BYTE - GPT_BYTE;
1152 if (s1 < 0)
1154 p2 = p1;
1155 s2 = ZV_BYTE - BEGV_BYTE;
1156 s1 = 0;
1158 if (s2 < 0)
1160 s1 = ZV_BYTE - BEGV_BYTE;
1161 s2 = 0;
1163 re_match_object = Qnil;
1165 while (n < 0)
1167 ptrdiff_t val;
1169 val = re_search_2 (bufp, (char *) p1, s1, (char *) p2, s2,
1170 pos_byte - BEGV_BYTE, lim_byte - pos_byte,
1171 (NILP (Vinhibit_changing_match_data)
1172 ? &search_regs : &search_regs_1),
1173 /* Don't allow match past current point */
1174 pos_byte - BEGV_BYTE);
1175 if (val == -2)
1177 matcher_overflow ();
1179 if (val >= 0)
1181 if (NILP (Vinhibit_changing_match_data))
1183 pos_byte = search_regs.start[0] + BEGV_BYTE;
1184 for (i = 0; i < search_regs.num_regs; i++)
1185 if (search_regs.start[i] >= 0)
1187 search_regs.start[i]
1188 = BYTE_TO_CHAR (search_regs.start[i] + BEGV_BYTE);
1189 search_regs.end[i]
1190 = BYTE_TO_CHAR (search_regs.end[i] + BEGV_BYTE);
1192 XSETBUFFER (last_thing_searched, current_buffer);
1193 /* Set pos to the new position. */
1194 pos = search_regs.start[0];
1196 else
1198 pos_byte = search_regs_1.start[0] + BEGV_BYTE;
1199 /* Set pos to the new position. */
1200 pos = BYTE_TO_CHAR (search_regs_1.start[0] + BEGV_BYTE);
1203 else
1205 immediate_quit = 0;
1206 return (n);
1208 n++;
1210 while (n > 0)
1212 ptrdiff_t val;
1214 val = re_search_2 (bufp, (char *) p1, s1, (char *) p2, s2,
1215 pos_byte - BEGV_BYTE, lim_byte - pos_byte,
1216 (NILP (Vinhibit_changing_match_data)
1217 ? &search_regs : &search_regs_1),
1218 lim_byte - BEGV_BYTE);
1219 if (val == -2)
1221 matcher_overflow ();
1223 if (val >= 0)
1225 if (NILP (Vinhibit_changing_match_data))
1227 pos_byte = search_regs.end[0] + BEGV_BYTE;
1228 for (i = 0; i < search_regs.num_regs; i++)
1229 if (search_regs.start[i] >= 0)
1231 search_regs.start[i]
1232 = BYTE_TO_CHAR (search_regs.start[i] + BEGV_BYTE);
1233 search_regs.end[i]
1234 = BYTE_TO_CHAR (search_regs.end[i] + BEGV_BYTE);
1236 XSETBUFFER (last_thing_searched, current_buffer);
1237 pos = search_regs.end[0];
1239 else
1241 pos_byte = search_regs_1.end[0] + BEGV_BYTE;
1242 pos = BYTE_TO_CHAR (search_regs_1.end[0] + BEGV_BYTE);
1245 else
1247 immediate_quit = 0;
1248 return (0 - n);
1250 n--;
1252 immediate_quit = 0;
1253 return (pos);
1255 else /* non-RE case */
1257 unsigned char *raw_pattern, *pat;
1258 ptrdiff_t raw_pattern_size;
1259 ptrdiff_t raw_pattern_size_byte;
1260 unsigned char *patbuf;
1261 int multibyte = !NILP (BVAR (current_buffer, enable_multibyte_characters));
1262 unsigned char *base_pat;
1263 /* Set to positive if we find a non-ASCII char that need
1264 translation. Otherwise set to zero later. */
1265 int char_base = -1;
1266 int boyer_moore_ok = 1;
1268 /* MULTIBYTE says whether the text to be searched is multibyte.
1269 We must convert PATTERN to match that, or we will not really
1270 find things right. */
1272 if (multibyte == STRING_MULTIBYTE (string))
1274 raw_pattern = SDATA (string);
1275 raw_pattern_size = SCHARS (string);
1276 raw_pattern_size_byte = SBYTES (string);
1278 else if (multibyte)
1280 raw_pattern_size = SCHARS (string);
1281 raw_pattern_size_byte
1282 = count_size_as_multibyte (SDATA (string),
1283 raw_pattern_size);
1284 raw_pattern = alloca (raw_pattern_size_byte + 1);
1285 copy_text (SDATA (string), raw_pattern,
1286 SCHARS (string), 0, 1);
1288 else
1290 /* Converting multibyte to single-byte.
1292 ??? Perhaps this conversion should be done in a special way
1293 by subtracting nonascii-insert-offset from each non-ASCII char,
1294 so that only the multibyte chars which really correspond to
1295 the chosen single-byte character set can possibly match. */
1296 raw_pattern_size = SCHARS (string);
1297 raw_pattern_size_byte = SCHARS (string);
1298 raw_pattern = alloca (raw_pattern_size + 1);
1299 copy_text (SDATA (string), raw_pattern,
1300 SBYTES (string), 1, 0);
1303 /* Copy and optionally translate the pattern. */
1304 len = raw_pattern_size;
1305 len_byte = raw_pattern_size_byte;
1306 patbuf = alloca (len * MAX_MULTIBYTE_LENGTH);
1307 pat = patbuf;
1308 base_pat = raw_pattern;
1309 if (multibyte)
1311 /* Fill patbuf by translated characters in STRING while
1312 checking if we can use boyer-moore search. If TRT is
1313 non-nil, we can use boyer-moore search only if TRT can be
1314 represented by the byte array of 256 elements. For that,
1315 all non-ASCII case-equivalents of all case-sensitive
1316 characters in STRING must belong to the same charset and
1317 row. */
1319 while (--len >= 0)
1321 unsigned char str_base[MAX_MULTIBYTE_LENGTH], *str;
1322 int c, translated, inverse;
1323 int in_charlen, charlen;
1325 /* If we got here and the RE flag is set, it's because we're
1326 dealing with a regexp known to be trivial, so the backslash
1327 just quotes the next character. */
1328 if (RE && *base_pat == '\\')
1330 len--;
1331 raw_pattern_size--;
1332 len_byte--;
1333 base_pat++;
1336 c = STRING_CHAR_AND_LENGTH (base_pat, in_charlen);
1338 if (NILP (trt))
1340 str = base_pat;
1341 charlen = in_charlen;
1343 else
1345 /* Translate the character. */
1346 TRANSLATE (translated, trt, c);
1347 charlen = CHAR_STRING (translated, str_base);
1348 str = str_base;
1350 /* Check if C has any other case-equivalents. */
1351 TRANSLATE (inverse, inverse_trt, c);
1352 /* If so, check if we can use boyer-moore. */
1353 if (c != inverse && boyer_moore_ok)
1355 /* Check if all equivalents belong to the same
1356 group of characters. Note that the check of C
1357 itself is done by the last iteration. */
1358 int this_char_base = -1;
1360 while (boyer_moore_ok)
1362 if (ASCII_BYTE_P (inverse))
1364 if (this_char_base > 0)
1365 boyer_moore_ok = 0;
1366 else
1367 this_char_base = 0;
1369 else if (CHAR_BYTE8_P (inverse))
1370 /* Boyer-moore search can't handle a
1371 translation of an eight-bit
1372 character. */
1373 boyer_moore_ok = 0;
1374 else if (this_char_base < 0)
1376 this_char_base = inverse & ~0x3F;
1377 if (char_base < 0)
1378 char_base = this_char_base;
1379 else if (this_char_base != char_base)
1380 boyer_moore_ok = 0;
1382 else if ((inverse & ~0x3F) != this_char_base)
1383 boyer_moore_ok = 0;
1384 if (c == inverse)
1385 break;
1386 TRANSLATE (inverse, inverse_trt, inverse);
1391 /* Store this character into the translated pattern. */
1392 memcpy (pat, str, charlen);
1393 pat += charlen;
1394 base_pat += in_charlen;
1395 len_byte -= in_charlen;
1398 /* If char_base is still negative we didn't find any translated
1399 non-ASCII characters. */
1400 if (char_base < 0)
1401 char_base = 0;
1403 else
1405 /* Unibyte buffer. */
1406 char_base = 0;
1407 while (--len >= 0)
1409 int c, translated;
1411 /* If we got here and the RE flag is set, it's because we're
1412 dealing with a regexp known to be trivial, so the backslash
1413 just quotes the next character. */
1414 if (RE && *base_pat == '\\')
1416 len--;
1417 raw_pattern_size--;
1418 base_pat++;
1420 c = *base_pat++;
1421 TRANSLATE (translated, trt, c);
1422 *pat++ = translated;
1426 len_byte = pat - patbuf;
1427 pat = base_pat = patbuf;
1429 if (boyer_moore_ok)
1430 return boyer_moore (n, pat, len_byte, trt, inverse_trt,
1431 pos_byte, lim_byte,
1432 char_base);
1433 else
1434 return simple_search (n, pat, raw_pattern_size, len_byte, trt,
1435 pos, pos_byte, lim, lim_byte);
1439 /* Do a simple string search N times for the string PAT,
1440 whose length is LEN/LEN_BYTE,
1441 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1442 TRT is the translation table.
1444 Return the character position where the match is found.
1445 Otherwise, if M matches remained to be found, return -M.
1447 This kind of search works regardless of what is in PAT and
1448 regardless of what is in TRT. It is used in cases where
1449 boyer_moore cannot work. */
1451 static EMACS_INT
1452 simple_search (EMACS_INT n, unsigned char *pat,
1453 ptrdiff_t len, ptrdiff_t len_byte, Lisp_Object trt,
1454 ptrdiff_t pos, ptrdiff_t pos_byte,
1455 ptrdiff_t lim, ptrdiff_t lim_byte)
1457 int multibyte = ! NILP (BVAR (current_buffer, enable_multibyte_characters));
1458 int forward = n > 0;
1459 /* Number of buffer bytes matched. Note that this may be different
1460 from len_byte in a multibyte buffer. */
1461 ptrdiff_t match_byte = PTRDIFF_MIN;
1463 if (lim > pos && multibyte)
1464 while (n > 0)
1466 while (1)
1468 /* Try matching at position POS. */
1469 ptrdiff_t this_pos = pos;
1470 ptrdiff_t this_pos_byte = pos_byte;
1471 ptrdiff_t this_len = len;
1472 unsigned char *p = pat;
1473 if (pos + len > lim || pos_byte + len_byte > lim_byte)
1474 goto stop;
1476 while (this_len > 0)
1478 int charlen, buf_charlen;
1479 int pat_ch, buf_ch;
1481 pat_ch = STRING_CHAR_AND_LENGTH (p, charlen);
1482 buf_ch = STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte),
1483 buf_charlen);
1484 TRANSLATE (buf_ch, trt, buf_ch);
1486 if (buf_ch != pat_ch)
1487 break;
1489 this_len--;
1490 p += charlen;
1492 this_pos_byte += buf_charlen;
1493 this_pos++;
1496 if (this_len == 0)
1498 match_byte = this_pos_byte - pos_byte;
1499 pos += len;
1500 pos_byte += match_byte;
1501 break;
1504 INC_BOTH (pos, pos_byte);
1507 n--;
1509 else if (lim > pos)
1510 while (n > 0)
1512 while (1)
1514 /* Try matching at position POS. */
1515 ptrdiff_t this_pos = pos;
1516 ptrdiff_t this_len = len;
1517 unsigned char *p = pat;
1519 if (pos + len > lim)
1520 goto stop;
1522 while (this_len > 0)
1524 int pat_ch = *p++;
1525 int buf_ch = FETCH_BYTE (this_pos);
1526 TRANSLATE (buf_ch, trt, buf_ch);
1528 if (buf_ch != pat_ch)
1529 break;
1531 this_len--;
1532 this_pos++;
1535 if (this_len == 0)
1537 match_byte = len;
1538 pos += len;
1539 break;
1542 pos++;
1545 n--;
1547 /* Backwards search. */
1548 else if (lim < pos && multibyte)
1549 while (n < 0)
1551 while (1)
1553 /* Try matching at position POS. */
1554 ptrdiff_t this_pos = pos;
1555 ptrdiff_t this_pos_byte = pos_byte;
1556 ptrdiff_t this_len = len;
1557 const unsigned char *p = pat + len_byte;
1559 if (this_pos - len < lim || (pos_byte - len_byte) < lim_byte)
1560 goto stop;
1562 while (this_len > 0)
1564 int pat_ch, buf_ch;
1566 DEC_BOTH (this_pos, this_pos_byte);
1567 PREV_CHAR_BOUNDARY (p, pat);
1568 pat_ch = STRING_CHAR (p);
1569 buf_ch = STRING_CHAR (BYTE_POS_ADDR (this_pos_byte));
1570 TRANSLATE (buf_ch, trt, buf_ch);
1572 if (buf_ch != pat_ch)
1573 break;
1575 this_len--;
1578 if (this_len == 0)
1580 match_byte = pos_byte - this_pos_byte;
1581 pos = this_pos;
1582 pos_byte = this_pos_byte;
1583 break;
1586 DEC_BOTH (pos, pos_byte);
1589 n++;
1591 else if (lim < pos)
1592 while (n < 0)
1594 while (1)
1596 /* Try matching at position POS. */
1597 ptrdiff_t this_pos = pos - len;
1598 ptrdiff_t this_len = len;
1599 unsigned char *p = pat;
1601 if (this_pos < lim)
1602 goto stop;
1604 while (this_len > 0)
1606 int pat_ch = *p++;
1607 int buf_ch = FETCH_BYTE (this_pos);
1608 TRANSLATE (buf_ch, trt, buf_ch);
1610 if (buf_ch != pat_ch)
1611 break;
1612 this_len--;
1613 this_pos++;
1616 if (this_len == 0)
1618 match_byte = len;
1619 pos -= len;
1620 break;
1623 pos--;
1626 n++;
1629 stop:
1630 if (n == 0)
1632 eassert (match_byte != PTRDIFF_MIN);
1633 if (forward)
1634 set_search_regs ((multibyte ? pos_byte : pos) - match_byte, match_byte);
1635 else
1636 set_search_regs (multibyte ? pos_byte : pos, match_byte);
1638 return pos;
1640 else if (n > 0)
1641 return -n;
1642 else
1643 return n;
1646 /* Do Boyer-Moore search N times for the string BASE_PAT,
1647 whose length is LEN_BYTE,
1648 from buffer position POS_BYTE until LIM_BYTE.
1649 DIRECTION says which direction we search in.
1650 TRT and INVERSE_TRT are translation tables.
1651 Characters in PAT are already translated by TRT.
1653 This kind of search works if all the characters in BASE_PAT that
1654 have nontrivial translation are the same aside from the last byte.
1655 This makes it possible to translate just the last byte of a
1656 character, and do so after just a simple test of the context.
1657 CHAR_BASE is nonzero if there is such a non-ASCII character.
1659 If that criterion is not satisfied, do not call this function. */
1661 static EMACS_INT
1662 boyer_moore (EMACS_INT n, unsigned char *base_pat,
1663 ptrdiff_t len_byte,
1664 Lisp_Object trt, Lisp_Object inverse_trt,
1665 ptrdiff_t pos_byte, ptrdiff_t lim_byte,
1666 int char_base)
1668 int direction = ((n > 0) ? 1 : -1);
1669 register ptrdiff_t dirlen;
1670 ptrdiff_t limit;
1671 int stride_for_teases = 0;
1672 int BM_tab[0400];
1673 register unsigned char *cursor, *p_limit;
1674 register ptrdiff_t i;
1675 register int j;
1676 unsigned char *pat, *pat_end;
1677 int multibyte = ! NILP (BVAR (current_buffer, enable_multibyte_characters));
1679 unsigned char simple_translate[0400];
1680 /* These are set to the preceding bytes of a byte to be translated
1681 if char_base is nonzero. As the maximum byte length of a
1682 multibyte character is 5, we have to check at most four previous
1683 bytes. */
1684 int translate_prev_byte1 = 0;
1685 int translate_prev_byte2 = 0;
1686 int translate_prev_byte3 = 0;
1688 /* The general approach is that we are going to maintain that we know
1689 the first (closest to the present position, in whatever direction
1690 we're searching) character that could possibly be the last
1691 (furthest from present position) character of a valid match. We
1692 advance the state of our knowledge by looking at that character
1693 and seeing whether it indeed matches the last character of the
1694 pattern. If it does, we take a closer look. If it does not, we
1695 move our pointer (to putative last characters) as far as is
1696 logically possible. This amount of movement, which I call a
1697 stride, will be the length of the pattern if the actual character
1698 appears nowhere in the pattern, otherwise it will be the distance
1699 from the last occurrence of that character to the end of the
1700 pattern. If the amount is zero we have a possible match. */
1702 /* Here we make a "mickey mouse" BM table. The stride of the search
1703 is determined only by the last character of the putative match.
1704 If that character does not match, we will stride the proper
1705 distance to propose a match that superimposes it on the last
1706 instance of a character that matches it (per trt), or misses
1707 it entirely if there is none. */
1709 dirlen = len_byte * direction;
1711 /* Record position after the end of the pattern. */
1712 pat_end = base_pat + len_byte;
1713 /* BASE_PAT points to a character that we start scanning from.
1714 It is the first character in a forward search,
1715 the last character in a backward search. */
1716 if (direction < 0)
1717 base_pat = pat_end - 1;
1719 /* A character that does not appear in the pattern induces a
1720 stride equal to the pattern length. */
1721 for (i = 0; i < 0400; i++)
1722 BM_tab[i] = dirlen;
1724 /* We use this for translation, instead of TRT itself.
1725 We fill this in to handle the characters that actually
1726 occur in the pattern. Others don't matter anyway! */
1727 for (i = 0; i < 0400; i++)
1728 simple_translate[i] = i;
1730 if (char_base)
1732 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1733 byte following them are the target of translation. */
1734 unsigned char str[MAX_MULTIBYTE_LENGTH];
1735 int cblen = CHAR_STRING (char_base, str);
1737 translate_prev_byte1 = str[cblen - 2];
1738 if (cblen > 2)
1740 translate_prev_byte2 = str[cblen - 3];
1741 if (cblen > 3)
1742 translate_prev_byte3 = str[cblen - 4];
1746 i = 0;
1747 while (i != dirlen)
1749 unsigned char *ptr = base_pat + i;
1750 i += direction;
1751 if (! NILP (trt))
1753 /* If the byte currently looking at is the last of a
1754 character to check case-equivalents, set CH to that
1755 character. An ASCII character and a non-ASCII character
1756 matching with CHAR_BASE are to be checked. */
1757 int ch = -1;
1759 if (ASCII_BYTE_P (*ptr) || ! multibyte)
1760 ch = *ptr;
1761 else if (char_base
1762 && ((pat_end - ptr) == 1 || CHAR_HEAD_P (ptr[1])))
1764 unsigned char *charstart = ptr - 1;
1766 while (! (CHAR_HEAD_P (*charstart)))
1767 charstart--;
1768 ch = STRING_CHAR (charstart);
1769 if (char_base != (ch & ~0x3F))
1770 ch = -1;
1773 if (ch >= 0200 && multibyte)
1774 j = (ch & 0x3F) | 0200;
1775 else
1776 j = *ptr;
1778 if (i == dirlen)
1779 stride_for_teases = BM_tab[j];
1781 BM_tab[j] = dirlen - i;
1782 /* A translation table is accompanied by its inverse -- see
1783 comment following downcase_table for details. */
1784 if (ch >= 0)
1786 int starting_ch = ch;
1787 int starting_j = j;
1789 while (1)
1791 TRANSLATE (ch, inverse_trt, ch);
1792 if (ch >= 0200 && multibyte)
1793 j = (ch & 0x3F) | 0200;
1794 else
1795 j = ch;
1797 /* For all the characters that map into CH,
1798 set up simple_translate to map the last byte
1799 into STARTING_J. */
1800 simple_translate[j] = starting_j;
1801 if (ch == starting_ch)
1802 break;
1803 BM_tab[j] = dirlen - i;
1807 else
1809 j = *ptr;
1811 if (i == dirlen)
1812 stride_for_teases = BM_tab[j];
1813 BM_tab[j] = dirlen - i;
1815 /* stride_for_teases tells how much to stride if we get a
1816 match on the far character but are subsequently
1817 disappointed, by recording what the stride would have been
1818 for that character if the last character had been
1819 different. */
1821 pos_byte += dirlen - ((direction > 0) ? direction : 0);
1822 /* loop invariant - POS_BYTE points at where last char (first
1823 char if reverse) of pattern would align in a possible match. */
1824 while (n != 0)
1826 ptrdiff_t tail_end;
1827 unsigned char *tail_end_ptr;
1829 /* It's been reported that some (broken) compiler thinks that
1830 Boolean expressions in an arithmetic context are unsigned.
1831 Using an explicit ?1:0 prevents this. */
1832 if ((lim_byte - pos_byte - ((direction > 0) ? 1 : 0)) * direction
1833 < 0)
1834 return (n * (0 - direction));
1835 /* First we do the part we can by pointers (maybe nothing) */
1836 QUIT;
1837 pat = base_pat;
1838 limit = pos_byte - dirlen + direction;
1839 if (direction > 0)
1841 limit = BUFFER_CEILING_OF (limit);
1842 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1843 can take on without hitting edge of buffer or the gap. */
1844 limit = min (limit, pos_byte + 20000);
1845 limit = min (limit, lim_byte - 1);
1847 else
1849 limit = BUFFER_FLOOR_OF (limit);
1850 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1851 can take on without hitting edge of buffer or the gap. */
1852 limit = max (limit, pos_byte - 20000);
1853 limit = max (limit, lim_byte);
1855 tail_end = BUFFER_CEILING_OF (pos_byte) + 1;
1856 tail_end_ptr = BYTE_POS_ADDR (tail_end);
1858 if ((limit - pos_byte) * direction > 20)
1860 unsigned char *p2;
1862 p_limit = BYTE_POS_ADDR (limit);
1863 p2 = (cursor = BYTE_POS_ADDR (pos_byte));
1864 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1865 while (1) /* use one cursor setting as long as i can */
1867 if (direction > 0) /* worth duplicating */
1869 while (cursor <= p_limit)
1871 if (BM_tab[*cursor] == 0)
1872 goto hit;
1873 cursor += BM_tab[*cursor];
1876 else
1878 while (cursor >= p_limit)
1880 if (BM_tab[*cursor] == 0)
1881 goto hit;
1882 cursor += BM_tab[*cursor];
1885 /* If you are here, cursor is beyond the end of the
1886 searched region. You fail to match within the
1887 permitted region and would otherwise try a character
1888 beyond that region. */
1889 break;
1891 hit:
1892 i = dirlen - direction;
1893 if (! NILP (trt))
1895 while ((i -= direction) + direction != 0)
1897 int ch;
1898 cursor -= direction;
1899 /* Translate only the last byte of a character. */
1900 if (! multibyte
1901 || ((cursor == tail_end_ptr
1902 || CHAR_HEAD_P (cursor[1]))
1903 && (CHAR_HEAD_P (cursor[0])
1904 /* Check if this is the last byte of
1905 a translatable character. */
1906 || (translate_prev_byte1 == cursor[-1]
1907 && (CHAR_HEAD_P (translate_prev_byte1)
1908 || (translate_prev_byte2 == cursor[-2]
1909 && (CHAR_HEAD_P (translate_prev_byte2)
1910 || (translate_prev_byte3 == cursor[-3]))))))))
1911 ch = simple_translate[*cursor];
1912 else
1913 ch = *cursor;
1914 if (pat[i] != ch)
1915 break;
1918 else
1920 while ((i -= direction) + direction != 0)
1922 cursor -= direction;
1923 if (pat[i] != *cursor)
1924 break;
1927 cursor += dirlen - i - direction; /* fix cursor */
1928 if (i + direction == 0)
1930 ptrdiff_t position, start, end;
1932 cursor -= direction;
1934 position = pos_byte + cursor - p2 + ((direction > 0)
1935 ? 1 - len_byte : 0);
1936 set_search_regs (position, len_byte);
1938 if (NILP (Vinhibit_changing_match_data))
1940 start = search_regs.start[0];
1941 end = search_regs.end[0];
1943 else
1944 /* If Vinhibit_changing_match_data is non-nil,
1945 search_regs will not be changed. So let's
1946 compute start and end here. */
1948 start = BYTE_TO_CHAR (position);
1949 end = BYTE_TO_CHAR (position + len_byte);
1952 if ((n -= direction) != 0)
1953 cursor += dirlen; /* to resume search */
1954 else
1955 return direction > 0 ? end : start;
1957 else
1958 cursor += stride_for_teases; /* <sigh> we lose - */
1960 pos_byte += cursor - p2;
1962 else
1963 /* Now we'll pick up a clump that has to be done the hard
1964 way because it covers a discontinuity. */
1966 limit = ((direction > 0)
1967 ? BUFFER_CEILING_OF (pos_byte - dirlen + 1)
1968 : BUFFER_FLOOR_OF (pos_byte - dirlen - 1));
1969 limit = ((direction > 0)
1970 ? min (limit + len_byte, lim_byte - 1)
1971 : max (limit - len_byte, lim_byte));
1972 /* LIMIT is now the last value POS_BYTE can have
1973 and still be valid for a possible match. */
1974 while (1)
1976 /* This loop can be coded for space rather than
1977 speed because it will usually run only once.
1978 (the reach is at most len + 21, and typically
1979 does not exceed len). */
1980 while ((limit - pos_byte) * direction >= 0)
1982 int ch = FETCH_BYTE (pos_byte);
1983 if (BM_tab[ch] == 0)
1984 goto hit2;
1985 pos_byte += BM_tab[ch];
1987 break; /* ran off the end */
1989 hit2:
1990 /* Found what might be a match. */
1991 i = dirlen - direction;
1992 while ((i -= direction) + direction != 0)
1994 int ch;
1995 unsigned char *ptr;
1996 pos_byte -= direction;
1997 ptr = BYTE_POS_ADDR (pos_byte);
1998 /* Translate only the last byte of a character. */
1999 if (! multibyte
2000 || ((ptr == tail_end_ptr
2001 || CHAR_HEAD_P (ptr[1]))
2002 && (CHAR_HEAD_P (ptr[0])
2003 /* Check if this is the last byte of a
2004 translatable character. */
2005 || (translate_prev_byte1 == ptr[-1]
2006 && (CHAR_HEAD_P (translate_prev_byte1)
2007 || (translate_prev_byte2 == ptr[-2]
2008 && (CHAR_HEAD_P (translate_prev_byte2)
2009 || translate_prev_byte3 == ptr[-3])))))))
2010 ch = simple_translate[*ptr];
2011 else
2012 ch = *ptr;
2013 if (pat[i] != ch)
2014 break;
2016 /* Above loop has moved POS_BYTE part or all the way
2017 back to the first pos (last pos if reverse).
2018 Set it once again at the last (first if reverse) char. */
2019 pos_byte += dirlen - i - direction;
2020 if (i + direction == 0)
2022 ptrdiff_t position, start, end;
2023 pos_byte -= direction;
2025 position = pos_byte + ((direction > 0) ? 1 - len_byte : 0);
2026 set_search_regs (position, len_byte);
2028 if (NILP (Vinhibit_changing_match_data))
2030 start = search_regs.start[0];
2031 end = search_regs.end[0];
2033 else
2034 /* If Vinhibit_changing_match_data is non-nil,
2035 search_regs will not be changed. So let's
2036 compute start and end here. */
2038 start = BYTE_TO_CHAR (position);
2039 end = BYTE_TO_CHAR (position + len_byte);
2042 if ((n -= direction) != 0)
2043 pos_byte += dirlen; /* to resume search */
2044 else
2045 return direction > 0 ? end : start;
2047 else
2048 pos_byte += stride_for_teases;
2051 /* We have done one clump. Can we continue? */
2052 if ((lim_byte - pos_byte) * direction < 0)
2053 return ((0 - n) * direction);
2055 return BYTE_TO_CHAR (pos_byte);
2058 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2059 for the overall match just found in the current buffer.
2060 Also clear out the match data for registers 1 and up. */
2062 static void
2063 set_search_regs (ptrdiff_t beg_byte, ptrdiff_t nbytes)
2065 ptrdiff_t i;
2067 if (!NILP (Vinhibit_changing_match_data))
2068 return;
2070 /* Make sure we have registers in which to store
2071 the match position. */
2072 if (search_regs.num_regs == 0)
2074 search_regs.start = xmalloc (2 * sizeof (regoff_t));
2075 search_regs.end = xmalloc (2 * sizeof (regoff_t));
2076 search_regs.num_regs = 2;
2079 /* Clear out the other registers. */
2080 for (i = 1; i < search_regs.num_regs; i++)
2082 search_regs.start[i] = -1;
2083 search_regs.end[i] = -1;
2086 search_regs.start[0] = BYTE_TO_CHAR (beg_byte);
2087 search_regs.end[0] = BYTE_TO_CHAR (beg_byte + nbytes);
2088 XSETBUFFER (last_thing_searched, current_buffer);
2091 DEFUN ("search-backward", Fsearch_backward, Ssearch_backward, 1, 4,
2092 "MSearch backward: ",
2093 doc: /* Search backward from point for STRING.
2094 Set point to the beginning of the occurrence found, and return point.
2095 An optional second argument bounds the search; it is a buffer position.
2096 The match found must not extend before that position.
2097 Optional third argument, if t, means if fail just return nil (no error).
2098 If not nil and not t, position at limit of search and return nil.
2099 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2100 successive occurrences. If COUNT is negative, search forward,
2101 instead of backward, for -COUNT occurrences.
2103 Search case-sensitivity is determined by the value of the variable
2104 `case-fold-search', which see.
2106 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2107 (Lisp_Object string, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
2109 return search_command (string, bound, noerror, count, -1, 0, 0);
2112 DEFUN ("search-forward", Fsearch_forward, Ssearch_forward, 1, 4, "MSearch: ",
2113 doc: /* Search forward from point for STRING.
2114 Set point to the end of the occurrence found, and return point.
2115 An optional second argument bounds the search; it is a buffer position.
2116 The match found must not extend after that position. A value of nil is
2117 equivalent to (point-max).
2118 Optional third argument, if t, means if fail just return nil (no error).
2119 If not nil and not t, move to limit of search and return nil.
2120 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2121 successive occurrences. If COUNT is negative, search backward,
2122 instead of forward, for -COUNT occurrences.
2124 Search case-sensitivity is determined by the value of the variable
2125 `case-fold-search', which see.
2127 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2128 (Lisp_Object string, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
2130 return search_command (string, bound, noerror, count, 1, 0, 0);
2133 DEFUN ("re-search-backward", Fre_search_backward, Sre_search_backward, 1, 4,
2134 "sRE search backward: ",
2135 doc: /* Search backward from point for match for regular expression REGEXP.
2136 Set point to the beginning of the match, and return point.
2137 The match found is the one starting last in the buffer
2138 and yet ending before the origin of the search.
2139 An optional second argument bounds the search; it is a buffer position.
2140 The match found must start at or after that position.
2141 Optional third argument, if t, means if fail just return nil (no error).
2142 If not nil and not t, move to limit of search and return nil.
2143 Optional fourth argument is repeat count--search for successive occurrences.
2145 Search case-sensitivity is determined by the value of the variable
2146 `case-fold-search', which see.
2148 See also the functions `match-beginning', `match-end', `match-string',
2149 and `replace-match'. */)
2150 (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
2152 return search_command (regexp, bound, noerror, count, -1, 1, 0);
2155 DEFUN ("re-search-forward", Fre_search_forward, Sre_search_forward, 1, 4,
2156 "sRE search: ",
2157 doc: /* Search forward from point for regular expression REGEXP.
2158 Set point to the end of the occurrence found, and return point.
2159 An optional second argument bounds the search; it is a buffer position.
2160 The match found must not extend after that position.
2161 Optional third argument, if t, means if fail just return nil (no error).
2162 If not nil and not t, move to limit of search and return nil.
2163 Optional fourth argument is repeat count--search for successive occurrences.
2165 Search case-sensitivity is determined by the value of the variable
2166 `case-fold-search', which see.
2168 See also the functions `match-beginning', `match-end', `match-string',
2169 and `replace-match'. */)
2170 (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
2172 return search_command (regexp, bound, noerror, count, 1, 1, 0);
2175 DEFUN ("posix-search-backward", Fposix_search_backward, Sposix_search_backward, 1, 4,
2176 "sPosix search backward: ",
2177 doc: /* Search backward from point for match for regular expression REGEXP.
2178 Find the longest match in accord with Posix regular expression rules.
2179 Set point to the beginning of the match, and return point.
2180 The match found is the one starting last in the buffer
2181 and yet ending before the origin of the search.
2182 An optional second argument bounds the search; it is a buffer position.
2183 The match found must start at or after that position.
2184 Optional third argument, if t, means if fail just return nil (no error).
2185 If not nil and not t, move to limit of search and return nil.
2186 Optional fourth argument is repeat count--search for successive occurrences.
2188 Search case-sensitivity is determined by the value of the variable
2189 `case-fold-search', which see.
2191 See also the functions `match-beginning', `match-end', `match-string',
2192 and `replace-match'. */)
2193 (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
2195 return search_command (regexp, bound, noerror, count, -1, 1, 1);
2198 DEFUN ("posix-search-forward", Fposix_search_forward, Sposix_search_forward, 1, 4,
2199 "sPosix search: ",
2200 doc: /* Search forward from point for regular expression REGEXP.
2201 Find the longest match in accord with Posix regular expression rules.
2202 Set point to the end of the occurrence found, and return point.
2203 An optional second argument bounds the search; it is a buffer position.
2204 The match found must not extend after that position.
2205 Optional third argument, if t, means if fail just return nil (no error).
2206 If not nil and not t, move to limit of search and return nil.
2207 Optional fourth argument is repeat count--search for successive occurrences.
2209 Search case-sensitivity is determined by the value of the variable
2210 `case-fold-search', which see.
2212 See also the functions `match-beginning', `match-end', `match-string',
2213 and `replace-match'. */)
2214 (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
2216 return search_command (regexp, bound, noerror, count, 1, 1, 1);
2219 DEFUN ("replace-match", Freplace_match, Sreplace_match, 1, 5, 0,
2220 doc: /* Replace text matched by last search with NEWTEXT.
2221 Leave point at the end of the replacement text.
2223 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2224 the replacement text. Otherwise, maybe capitalize the whole text, or
2225 maybe just word initials, based on the replaced text. If the replaced
2226 text has only capital letters and has at least one multiletter word,
2227 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2228 in the replaced text, capitalize each word in NEWTEXT.
2230 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2231 Otherwise treat `\\' as special:
2232 `\\&' in NEWTEXT means substitute original matched text.
2233 `\\N' means substitute what matched the Nth `\\(...\\)'.
2234 If Nth parens didn't match, substitute nothing.
2235 `\\\\' means insert one `\\'.
2236 `\\?' is treated literally
2237 (for compatibility with `query-replace-regexp').
2238 Any other character following `\\' signals an error.
2239 Case conversion does not apply to these substitutions.
2241 If optional fourth argument STRING is non-nil, it should be a string
2242 to act on; this should be the string on which the previous match was
2243 done via `string-match'. In this case, `replace-match' creates and
2244 returns a new string, made by copying STRING and replacing the part of
2245 STRING that was matched (the original STRING itself is not altered).
2247 The optional fifth argument SUBEXP specifies a subexpression;
2248 it says to replace just that subexpression with NEWTEXT,
2249 rather than replacing the entire matched text.
2250 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2251 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2252 NEWTEXT in place of subexp N.
2253 This is useful only after a regular expression search or match,
2254 since only regular expressions have distinguished subexpressions. */)
2255 (Lisp_Object newtext, Lisp_Object fixedcase, Lisp_Object literal, Lisp_Object string, Lisp_Object subexp)
2257 enum { nochange, all_caps, cap_initial } case_action;
2258 register ptrdiff_t pos, pos_byte;
2259 int some_multiletter_word;
2260 int some_lowercase;
2261 int some_uppercase;
2262 int some_nonuppercase_initial;
2263 register int c, prevc;
2264 ptrdiff_t sub;
2265 ptrdiff_t opoint, newpoint;
2267 CHECK_STRING (newtext);
2269 if (! NILP (string))
2270 CHECK_STRING (string);
2272 case_action = nochange; /* We tried an initialization */
2273 /* but some C compilers blew it */
2275 if (search_regs.num_regs <= 0)
2276 error ("`replace-match' called before any match found");
2278 if (NILP (subexp))
2279 sub = 0;
2280 else
2282 CHECK_NUMBER (subexp);
2283 if (! (0 <= XINT (subexp) && XINT (subexp) < search_regs.num_regs))
2284 args_out_of_range (subexp, make_number (search_regs.num_regs));
2285 sub = XINT (subexp);
2288 if (NILP (string))
2290 if (search_regs.start[sub] < BEGV
2291 || search_regs.start[sub] > search_regs.end[sub]
2292 || search_regs.end[sub] > ZV)
2293 args_out_of_range (make_number (search_regs.start[sub]),
2294 make_number (search_regs.end[sub]));
2296 else
2298 if (search_regs.start[sub] < 0
2299 || search_regs.start[sub] > search_regs.end[sub]
2300 || search_regs.end[sub] > SCHARS (string))
2301 args_out_of_range (make_number (search_regs.start[sub]),
2302 make_number (search_regs.end[sub]));
2305 if (NILP (fixedcase))
2307 /* Decide how to casify by examining the matched text. */
2308 ptrdiff_t last;
2310 pos = search_regs.start[sub];
2311 last = search_regs.end[sub];
2313 if (NILP (string))
2314 pos_byte = CHAR_TO_BYTE (pos);
2315 else
2316 pos_byte = string_char_to_byte (string, pos);
2318 prevc = '\n';
2319 case_action = all_caps;
2321 /* some_multiletter_word is set nonzero if any original word
2322 is more than one letter long. */
2323 some_multiletter_word = 0;
2324 some_lowercase = 0;
2325 some_nonuppercase_initial = 0;
2326 some_uppercase = 0;
2328 while (pos < last)
2330 if (NILP (string))
2332 c = FETCH_CHAR_AS_MULTIBYTE (pos_byte);
2333 INC_BOTH (pos, pos_byte);
2335 else
2336 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c, string, pos, pos_byte);
2338 if (lowercasep (c))
2340 /* Cannot be all caps if any original char is lower case */
2342 some_lowercase = 1;
2343 if (SYNTAX (prevc) != Sword)
2344 some_nonuppercase_initial = 1;
2345 else
2346 some_multiletter_word = 1;
2348 else if (uppercasep (c))
2350 some_uppercase = 1;
2351 if (SYNTAX (prevc) != Sword)
2353 else
2354 some_multiletter_word = 1;
2356 else
2358 /* If the initial is a caseless word constituent,
2359 treat that like a lowercase initial. */
2360 if (SYNTAX (prevc) != Sword)
2361 some_nonuppercase_initial = 1;
2364 prevc = c;
2367 /* Convert to all caps if the old text is all caps
2368 and has at least one multiletter word. */
2369 if (! some_lowercase && some_multiletter_word)
2370 case_action = all_caps;
2371 /* Capitalize each word, if the old text has all capitalized words. */
2372 else if (!some_nonuppercase_initial && some_multiletter_word)
2373 case_action = cap_initial;
2374 else if (!some_nonuppercase_initial && some_uppercase)
2375 /* Should x -> yz, operating on X, give Yz or YZ?
2376 We'll assume the latter. */
2377 case_action = all_caps;
2378 else
2379 case_action = nochange;
2382 /* Do replacement in a string. */
2383 if (!NILP (string))
2385 Lisp_Object before, after;
2387 before = Fsubstring (string, make_number (0),
2388 make_number (search_regs.start[sub]));
2389 after = Fsubstring (string, make_number (search_regs.end[sub]), Qnil);
2391 /* Substitute parts of the match into NEWTEXT
2392 if desired. */
2393 if (NILP (literal))
2395 ptrdiff_t lastpos = 0;
2396 ptrdiff_t lastpos_byte = 0;
2397 /* We build up the substituted string in ACCUM. */
2398 Lisp_Object accum;
2399 Lisp_Object middle;
2400 ptrdiff_t length = SBYTES (newtext);
2402 accum = Qnil;
2404 for (pos_byte = 0, pos = 0; pos_byte < length;)
2406 ptrdiff_t substart = -1;
2407 ptrdiff_t subend = 0;
2408 int delbackslash = 0;
2410 FETCH_STRING_CHAR_ADVANCE (c, newtext, pos, pos_byte);
2412 if (c == '\\')
2414 FETCH_STRING_CHAR_ADVANCE (c, newtext, pos, pos_byte);
2416 if (c == '&')
2418 substart = search_regs.start[sub];
2419 subend = search_regs.end[sub];
2421 else if (c >= '1' && c <= '9')
2423 if (c - '0' < search_regs.num_regs
2424 && 0 <= search_regs.start[c - '0'])
2426 substart = search_regs.start[c - '0'];
2427 subend = search_regs.end[c - '0'];
2429 else
2431 /* If that subexp did not match,
2432 replace \\N with nothing. */
2433 substart = 0;
2434 subend = 0;
2437 else if (c == '\\')
2438 delbackslash = 1;
2439 else if (c != '?')
2440 error ("Invalid use of `\\' in replacement text");
2442 if (substart >= 0)
2444 if (pos - 2 != lastpos)
2445 middle = substring_both (newtext, lastpos,
2446 lastpos_byte,
2447 pos - 2, pos_byte - 2);
2448 else
2449 middle = Qnil;
2450 accum = concat3 (accum, middle,
2451 Fsubstring (string,
2452 make_number (substart),
2453 make_number (subend)));
2454 lastpos = pos;
2455 lastpos_byte = pos_byte;
2457 else if (delbackslash)
2459 middle = substring_both (newtext, lastpos,
2460 lastpos_byte,
2461 pos - 1, pos_byte - 1);
2463 accum = concat2 (accum, middle);
2464 lastpos = pos;
2465 lastpos_byte = pos_byte;
2469 if (pos != lastpos)
2470 middle = substring_both (newtext, lastpos,
2471 lastpos_byte,
2472 pos, pos_byte);
2473 else
2474 middle = Qnil;
2476 newtext = concat2 (accum, middle);
2479 /* Do case substitution in NEWTEXT if desired. */
2480 if (case_action == all_caps)
2481 newtext = Fupcase (newtext);
2482 else if (case_action == cap_initial)
2483 newtext = Fupcase_initials (newtext);
2485 return concat3 (before, newtext, after);
2488 /* Record point, then move (quietly) to the start of the match. */
2489 if (PT >= search_regs.end[sub])
2490 opoint = PT - ZV;
2491 else if (PT > search_regs.start[sub])
2492 opoint = search_regs.end[sub] - ZV;
2493 else
2494 opoint = PT;
2496 /* If we want non-literal replacement,
2497 perform substitution on the replacement string. */
2498 if (NILP (literal))
2500 ptrdiff_t length = SBYTES (newtext);
2501 unsigned char *substed;
2502 ptrdiff_t substed_alloc_size, substed_len;
2503 int buf_multibyte = !NILP (BVAR (current_buffer, enable_multibyte_characters));
2504 int str_multibyte = STRING_MULTIBYTE (newtext);
2505 int really_changed = 0;
2507 substed_alloc_size = ((STRING_BYTES_BOUND - 100) / 2 < length
2508 ? STRING_BYTES_BOUND
2509 : length * 2 + 100);
2510 substed = xmalloc (substed_alloc_size);
2511 substed_len = 0;
2513 /* Go thru NEWTEXT, producing the actual text to insert in
2514 SUBSTED while adjusting multibyteness to that of the current
2515 buffer. */
2517 for (pos_byte = 0, pos = 0; pos_byte < length;)
2519 unsigned char str[MAX_MULTIBYTE_LENGTH];
2520 const unsigned char *add_stuff = NULL;
2521 ptrdiff_t add_len = 0;
2522 ptrdiff_t idx = -1;
2524 if (str_multibyte)
2526 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c, newtext, pos, pos_byte);
2527 if (!buf_multibyte)
2528 c = multibyte_char_to_unibyte (c);
2530 else
2532 /* Note that we don't have to increment POS. */
2533 c = SREF (newtext, pos_byte++);
2534 if (buf_multibyte)
2535 MAKE_CHAR_MULTIBYTE (c);
2538 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2539 or set IDX to a match index, which means put that part
2540 of the buffer text into SUBSTED. */
2542 if (c == '\\')
2544 really_changed = 1;
2546 if (str_multibyte)
2548 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c, newtext,
2549 pos, pos_byte);
2550 if (!buf_multibyte && !ASCII_CHAR_P (c))
2551 c = multibyte_char_to_unibyte (c);
2553 else
2555 c = SREF (newtext, pos_byte++);
2556 if (buf_multibyte)
2557 MAKE_CHAR_MULTIBYTE (c);
2560 if (c == '&')
2561 idx = sub;
2562 else if (c >= '1' && c <= '9' && c - '0' < search_regs.num_regs)
2564 if (search_regs.start[c - '0'] >= 1)
2565 idx = c - '0';
2567 else if (c == '\\')
2568 add_len = 1, add_stuff = (unsigned char *) "\\";
2569 else
2571 xfree (substed);
2572 error ("Invalid use of `\\' in replacement text");
2575 else
2577 add_len = CHAR_STRING (c, str);
2578 add_stuff = str;
2581 /* If we want to copy part of a previous match,
2582 set up ADD_STUFF and ADD_LEN to point to it. */
2583 if (idx >= 0)
2585 ptrdiff_t begbyte = CHAR_TO_BYTE (search_regs.start[idx]);
2586 add_len = CHAR_TO_BYTE (search_regs.end[idx]) - begbyte;
2587 if (search_regs.start[idx] < GPT && GPT < search_regs.end[idx])
2588 move_gap (search_regs.start[idx]);
2589 add_stuff = BYTE_POS_ADDR (begbyte);
2592 /* Now the stuff we want to add to SUBSTED
2593 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2595 /* Make sure SUBSTED is big enough. */
2596 if (substed_alloc_size - substed_len < add_len)
2597 substed =
2598 xpalloc (substed, &substed_alloc_size,
2599 add_len - (substed_alloc_size - substed_len),
2600 STRING_BYTES_BOUND, 1);
2602 /* Now add to the end of SUBSTED. */
2603 if (add_stuff)
2605 memcpy (substed + substed_len, add_stuff, add_len);
2606 substed_len += add_len;
2610 if (really_changed)
2612 if (buf_multibyte)
2614 ptrdiff_t nchars =
2615 multibyte_chars_in_text (substed, substed_len);
2617 newtext = make_multibyte_string ((char *) substed, nchars,
2618 substed_len);
2620 else
2621 newtext = make_unibyte_string ((char *) substed, substed_len);
2623 xfree (substed);
2626 /* Replace the old text with the new in the cleanest possible way. */
2627 replace_range (search_regs.start[sub], search_regs.end[sub],
2628 newtext, 1, 0, 1);
2629 newpoint = search_regs.start[sub] + SCHARS (newtext);
2631 if (case_action == all_caps)
2632 Fupcase_region (make_number (search_regs.start[sub]),
2633 make_number (newpoint));
2634 else if (case_action == cap_initial)
2635 Fupcase_initials_region (make_number (search_regs.start[sub]),
2636 make_number (newpoint));
2638 /* Adjust search data for this change. */
2640 ptrdiff_t oldend = search_regs.end[sub];
2641 ptrdiff_t oldstart = search_regs.start[sub];
2642 ptrdiff_t change = newpoint - search_regs.end[sub];
2643 ptrdiff_t i;
2645 for (i = 0; i < search_regs.num_regs; i++)
2647 if (search_regs.start[i] >= oldend)
2648 search_regs.start[i] += change;
2649 else if (search_regs.start[i] > oldstart)
2650 search_regs.start[i] = oldstart;
2651 if (search_regs.end[i] >= oldend)
2652 search_regs.end[i] += change;
2653 else if (search_regs.end[i] > oldstart)
2654 search_regs.end[i] = oldstart;
2658 /* Put point back where it was in the text. */
2659 if (opoint <= 0)
2660 TEMP_SET_PT (opoint + ZV);
2661 else
2662 TEMP_SET_PT (opoint);
2664 /* Now move point "officially" to the start of the inserted replacement. */
2665 move_if_not_intangible (newpoint);
2667 return Qnil;
2670 static Lisp_Object
2671 match_limit (Lisp_Object num, int beginningp)
2673 EMACS_INT n;
2675 CHECK_NUMBER (num);
2676 n = XINT (num);
2677 if (n < 0)
2678 args_out_of_range (num, make_number (0));
2679 if (search_regs.num_regs <= 0)
2680 error ("No match data, because no search succeeded");
2681 if (n >= search_regs.num_regs
2682 || search_regs.start[n] < 0)
2683 return Qnil;
2684 return (make_number ((beginningp) ? search_regs.start[n]
2685 : search_regs.end[n]));
2688 DEFUN ("match-beginning", Fmatch_beginning, Smatch_beginning, 1, 1, 0,
2689 doc: /* Return position of start of text matched by last search.
2690 SUBEXP, a number, specifies which parenthesized expression in the last
2691 regexp.
2692 Value is nil if SUBEXPth pair didn't match, or there were less than
2693 SUBEXP pairs.
2694 Zero means the entire text matched by the whole regexp or whole string. */)
2695 (Lisp_Object subexp)
2697 return match_limit (subexp, 1);
2700 DEFUN ("match-end", Fmatch_end, Smatch_end, 1, 1, 0,
2701 doc: /* Return position of end of text matched by last search.
2702 SUBEXP, a number, specifies which parenthesized expression in the last
2703 regexp.
2704 Value is nil if SUBEXPth pair didn't match, or there were less than
2705 SUBEXP pairs.
2706 Zero means the entire text matched by the whole regexp or whole string. */)
2707 (Lisp_Object subexp)
2709 return match_limit (subexp, 0);
2712 DEFUN ("match-data", Fmatch_data, Smatch_data, 0, 3, 0,
2713 doc: /* Return a list containing all info on what the last search matched.
2714 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2715 All the elements are markers or nil (nil if the Nth pair didn't match)
2716 if the last match was on a buffer; integers or nil if a string was matched.
2717 Use `set-match-data' to reinstate the data in this list.
2719 If INTEGERS (the optional first argument) is non-nil, always use
2720 integers \(rather than markers) to represent buffer positions. In
2721 this case, and if the last match was in a buffer, the buffer will get
2722 stored as one additional element at the end of the list.
2724 If REUSE is a list, reuse it as part of the value. If REUSE is long
2725 enough to hold all the values, and if INTEGERS is non-nil, no consing
2726 is done.
2728 If optional third arg RESEAT is non-nil, any previous markers on the
2729 REUSE list will be modified to point to nowhere.
2731 Return value is undefined if the last search failed. */)
2732 (Lisp_Object integers, Lisp_Object reuse, Lisp_Object reseat)
2734 Lisp_Object tail, prev;
2735 Lisp_Object *data;
2736 ptrdiff_t i, len;
2738 if (!NILP (reseat))
2739 for (tail = reuse; CONSP (tail); tail = XCDR (tail))
2740 if (MARKERP (XCAR (tail)))
2742 unchain_marker (XMARKER (XCAR (tail)));
2743 XSETCAR (tail, Qnil);
2746 if (NILP (last_thing_searched))
2747 return Qnil;
2749 prev = Qnil;
2751 data = alloca ((2 * search_regs.num_regs + 1) * sizeof *data);
2753 len = 0;
2754 for (i = 0; i < search_regs.num_regs; i++)
2756 ptrdiff_t start = search_regs.start[i];
2757 if (start >= 0)
2759 if (EQ (last_thing_searched, Qt)
2760 || ! NILP (integers))
2762 XSETFASTINT (data[2 * i], start);
2763 XSETFASTINT (data[2 * i + 1], search_regs.end[i]);
2765 else if (BUFFERP (last_thing_searched))
2767 data[2 * i] = Fmake_marker ();
2768 Fset_marker (data[2 * i],
2769 make_number (start),
2770 last_thing_searched);
2771 data[2 * i + 1] = Fmake_marker ();
2772 Fset_marker (data[2 * i + 1],
2773 make_number (search_regs.end[i]),
2774 last_thing_searched);
2776 else
2777 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2778 emacs_abort ();
2780 len = 2 * i + 2;
2782 else
2783 data[2 * i] = data[2 * i + 1] = Qnil;
2786 if (BUFFERP (last_thing_searched) && !NILP (integers))
2788 data[len] = last_thing_searched;
2789 len++;
2792 /* If REUSE is not usable, cons up the values and return them. */
2793 if (! CONSP (reuse))
2794 return Flist (len, data);
2796 /* If REUSE is a list, store as many value elements as will fit
2797 into the elements of REUSE. */
2798 for (i = 0, tail = reuse; CONSP (tail);
2799 i++, tail = XCDR (tail))
2801 if (i < len)
2802 XSETCAR (tail, data[i]);
2803 else
2804 XSETCAR (tail, Qnil);
2805 prev = tail;
2808 /* If we couldn't fit all value elements into REUSE,
2809 cons up the rest of them and add them to the end of REUSE. */
2810 if (i < len)
2811 XSETCDR (prev, Flist (len - i, data + i));
2813 return reuse;
2816 /* We used to have an internal use variant of `reseat' described as:
2818 If RESEAT is `evaporate', put the markers back on the free list
2819 immediately. No other references to the markers must exist in this
2820 case, so it is used only internally on the unwind stack and
2821 save-match-data from Lisp.
2823 But it was ill-conceived: those supposedly-internal markers get exposed via
2824 the undo-list, so freeing them here is unsafe. */
2826 DEFUN ("set-match-data", Fset_match_data, Sset_match_data, 1, 2, 0,
2827 doc: /* Set internal data on last search match from elements of LIST.
2828 LIST should have been created by calling `match-data' previously.
2830 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2831 (register Lisp_Object list, Lisp_Object reseat)
2833 ptrdiff_t i;
2834 register Lisp_Object marker;
2836 if (running_asynch_code)
2837 save_search_regs ();
2839 CHECK_LIST (list);
2841 /* Unless we find a marker with a buffer or an explicit buffer
2842 in LIST, assume that this match data came from a string. */
2843 last_thing_searched = Qt;
2845 /* Allocate registers if they don't already exist. */
2847 EMACS_INT length = XFASTINT (Flength (list)) / 2;
2849 if (length > search_regs.num_regs)
2851 ptrdiff_t num_regs = search_regs.num_regs;
2852 if (PTRDIFF_MAX < length)
2853 memory_full (SIZE_MAX);
2854 search_regs.start =
2855 xpalloc (search_regs.start, &num_regs, length - num_regs,
2856 min (PTRDIFF_MAX, UINT_MAX), sizeof (regoff_t));
2857 search_regs.end =
2858 xrealloc (search_regs.end, num_regs * sizeof (regoff_t));
2860 for (i = search_regs.num_regs; i < num_regs; i++)
2861 search_regs.start[i] = -1;
2863 search_regs.num_regs = num_regs;
2866 for (i = 0; CONSP (list); i++)
2868 marker = XCAR (list);
2869 if (BUFFERP (marker))
2871 last_thing_searched = marker;
2872 break;
2874 if (i >= length)
2875 break;
2876 if (NILP (marker))
2878 search_regs.start[i] = -1;
2879 list = XCDR (list);
2881 else
2883 Lisp_Object from;
2884 Lisp_Object m;
2886 m = marker;
2887 if (MARKERP (marker))
2889 if (XMARKER (marker)->buffer == 0)
2890 XSETFASTINT (marker, 0);
2891 else
2892 XSETBUFFER (last_thing_searched, XMARKER (marker)->buffer);
2895 CHECK_NUMBER_COERCE_MARKER (marker);
2896 from = marker;
2898 if (!NILP (reseat) && MARKERP (m))
2900 unchain_marker (XMARKER (m));
2901 XSETCAR (list, Qnil);
2904 if ((list = XCDR (list), !CONSP (list)))
2905 break;
2907 m = marker = XCAR (list);
2909 if (MARKERP (marker) && XMARKER (marker)->buffer == 0)
2910 XSETFASTINT (marker, 0);
2912 CHECK_NUMBER_COERCE_MARKER (marker);
2913 if ((XINT (from) < 0
2914 ? TYPE_MINIMUM (regoff_t) <= XINT (from)
2915 : XINT (from) <= TYPE_MAXIMUM (regoff_t))
2916 && (XINT (marker) < 0
2917 ? TYPE_MINIMUM (regoff_t) <= XINT (marker)
2918 : XINT (marker) <= TYPE_MAXIMUM (regoff_t)))
2920 search_regs.start[i] = XINT (from);
2921 search_regs.end[i] = XINT (marker);
2923 else
2925 search_regs.start[i] = -1;
2928 if (!NILP (reseat) && MARKERP (m))
2930 unchain_marker (XMARKER (m));
2931 XSETCAR (list, Qnil);
2934 list = XCDR (list);
2937 for (; i < search_regs.num_regs; i++)
2938 search_regs.start[i] = -1;
2941 return Qnil;
2944 /* If non-zero the match data have been saved in saved_search_regs
2945 during the execution of a sentinel or filter. */
2946 static int search_regs_saved;
2947 static struct re_registers saved_search_regs;
2948 static Lisp_Object saved_last_thing_searched;
2950 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2951 if asynchronous code (filter or sentinel) is running. */
2952 static void
2953 save_search_regs (void)
2955 if (!search_regs_saved)
2957 saved_search_regs.num_regs = search_regs.num_regs;
2958 saved_search_regs.start = search_regs.start;
2959 saved_search_regs.end = search_regs.end;
2960 saved_last_thing_searched = last_thing_searched;
2961 last_thing_searched = Qnil;
2962 search_regs.num_regs = 0;
2963 search_regs.start = 0;
2964 search_regs.end = 0;
2966 search_regs_saved = 1;
2970 /* Called upon exit from filters and sentinels. */
2971 void
2972 restore_search_regs (void)
2974 if (search_regs_saved)
2976 if (search_regs.num_regs > 0)
2978 xfree (search_regs.start);
2979 xfree (search_regs.end);
2981 search_regs.num_regs = saved_search_regs.num_regs;
2982 search_regs.start = saved_search_regs.start;
2983 search_regs.end = saved_search_regs.end;
2984 last_thing_searched = saved_last_thing_searched;
2985 saved_last_thing_searched = Qnil;
2986 search_regs_saved = 0;
2990 static Lisp_Object
2991 unwind_set_match_data (Lisp_Object list)
2993 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
2994 return Fset_match_data (list, Qt);
2997 /* Called to unwind protect the match data. */
2998 void
2999 record_unwind_save_match_data (void)
3001 record_unwind_protect (unwind_set_match_data,
3002 Fmatch_data (Qnil, Qnil, Qnil));
3005 /* Quote a string to deactivate reg-expr chars */
3007 DEFUN ("regexp-quote", Fregexp_quote, Sregexp_quote, 1, 1, 0,
3008 doc: /* Return a regexp string which matches exactly STRING and nothing else. */)
3009 (Lisp_Object string)
3011 register char *in, *out, *end;
3012 register char *temp;
3013 int backslashes_added = 0;
3015 CHECK_STRING (string);
3017 temp = alloca (SBYTES (string) * 2);
3019 /* Now copy the data into the new string, inserting escapes. */
3021 in = SSDATA (string);
3022 end = in + SBYTES (string);
3023 out = temp;
3025 for (; in != end; in++)
3027 if (*in == '['
3028 || *in == '*' || *in == '.' || *in == '\\'
3029 || *in == '?' || *in == '+'
3030 || *in == '^' || *in == '$')
3031 *out++ = '\\', backslashes_added++;
3032 *out++ = *in;
3035 return make_specified_string (temp,
3036 SCHARS (string) + backslashes_added,
3037 out - temp,
3038 STRING_MULTIBYTE (string));
3041 void
3042 syms_of_search (void)
3044 register int i;
3046 for (i = 0; i < REGEXP_CACHE_SIZE; ++i)
3048 searchbufs[i].buf.allocated = 100;
3049 searchbufs[i].buf.buffer = xmalloc (100);
3050 searchbufs[i].buf.fastmap = searchbufs[i].fastmap;
3051 searchbufs[i].regexp = Qnil;
3052 searchbufs[i].whitespace_regexp = Qnil;
3053 searchbufs[i].syntax_table = Qnil;
3054 staticpro (&searchbufs[i].regexp);
3055 staticpro (&searchbufs[i].whitespace_regexp);
3056 staticpro (&searchbufs[i].syntax_table);
3057 searchbufs[i].next = (i == REGEXP_CACHE_SIZE-1 ? 0 : &searchbufs[i+1]);
3059 searchbuf_head = &searchbufs[0];
3061 DEFSYM (Qsearch_failed, "search-failed");
3062 DEFSYM (Qinvalid_regexp, "invalid-regexp");
3064 Fput (Qsearch_failed, Qerror_conditions,
3065 listn (CONSTYPE_PURE, 2, Qsearch_failed, Qerror));
3066 Fput (Qsearch_failed, Qerror_message,
3067 build_pure_c_string ("Search failed"));
3069 Fput (Qinvalid_regexp, Qerror_conditions,
3070 listn (CONSTYPE_PURE, 2, Qinvalid_regexp, Qerror));
3071 Fput (Qinvalid_regexp, Qerror_message,
3072 build_pure_c_string ("Invalid regexp"));
3074 last_thing_searched = Qnil;
3075 staticpro (&last_thing_searched);
3077 saved_last_thing_searched = Qnil;
3078 staticpro (&saved_last_thing_searched);
3080 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp,
3081 doc: /* Regexp to substitute for bunches of spaces in regexp search.
3082 Some commands use this for user-specified regexps.
3083 Spaces that occur inside character classes or repetition operators
3084 or other such regexp constructs are not replaced with this.
3085 A value of nil (which is the normal value) means treat spaces literally. */);
3086 Vsearch_spaces_regexp = Qnil;
3088 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data,
3089 doc: /* Internal use only.
3090 If non-nil, the primitive searching and matching functions
3091 such as `looking-at', `string-match', `re-search-forward', etc.,
3092 do not set the match data. The proper way to use this variable
3093 is to bind it with `let' around a small expression. */);
3094 Vinhibit_changing_match_data = Qnil;
3096 defsubr (&Slooking_at);
3097 defsubr (&Sposix_looking_at);
3098 defsubr (&Sstring_match);
3099 defsubr (&Sposix_string_match);
3100 defsubr (&Ssearch_forward);
3101 defsubr (&Ssearch_backward);
3102 defsubr (&Sre_search_forward);
3103 defsubr (&Sre_search_backward);
3104 defsubr (&Sposix_search_forward);
3105 defsubr (&Sposix_search_backward);
3106 defsubr (&Sreplace_match);
3107 defsubr (&Smatch_beginning);
3108 defsubr (&Smatch_end);
3109 defsubr (&Smatch_data);
3110 defsubr (&Sset_match_data);
3111 defsubr (&Sregexp_quote);