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/>. */
27 #include "character.h"
30 #include "region-cache.h"
32 #include "blockinput.h"
33 #include "intervals.h"
35 #include <sys/types.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. */
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
;
52 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
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
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,
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. */
121 compile_pattern_1 (struct regexp_cache
*cp
, Lisp_Object pattern
, Lisp_Object translate
, int posix
)
127 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
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
;
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. */
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
));
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
);
159 /* unblock_input (); */
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. */
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. */
188 clear_regexp_cache (void)
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
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
)
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
))
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
)
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
243 compile_pattern_1 (cp
, pattern
, translate
, posix
);
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. */
252 cp
->next
= searchbuf_head
;
255 /* Advise the searching functions about the space we have allocated
256 for register data. */
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
;
269 looking_at_1 (Lisp_Object string
, int posix
)
272 unsigned char *p1
, *p2
;
274 register ptrdiff_t i
;
275 struct re_pattern_buffer
*bufp
;
277 if (running_asynch_code
)
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
),
291 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
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. */
300 s1
= GPT_BYTE
- BEGV_BYTE
;
302 s2
= ZV_BYTE
- GPT_BYTE
;
306 s2
= ZV_BYTE
- BEGV_BYTE
;
311 s1
= ZV_BYTE
- BEGV_BYTE
;
315 re_match_object
= Qnil
;
317 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
319 (NILP (Vinhibit_changing_match_data
)
320 ? &search_regs
: NULL
),
321 ZV_BYTE
- BEGV_BYTE
);
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)
333 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
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
);
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. */)
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. */)
363 return looking_at_1 (regexp
, 1);
367 string_match_1 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
, int posix
)
370 struct re_pattern_buffer
*bufp
;
372 ptrdiff_t pos_byte
, i
;
374 if (running_asynch_code
)
377 CHECK_STRING (regexp
);
378 CHECK_STRING (string
);
381 pos
= 0, pos_byte
= 0;
384 ptrdiff_t len
= SCHARS (string
);
386 CHECK_NUMBER (start
);
388 if (pos
< 0 && -pos
<= len
)
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
),
405 STRING_MULTIBYTE (string
));
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
));
416 /* Set last_thing_searched only when match data is changed. */
417 if (NILP (Vinhibit_changing_match_data
))
418 last_thing_searched
= Qt
;
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)
429 = string_byte_to_char (string
, search_regs
.start
[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. */
470 fast_string_match (Lisp_Object regexp
, Lisp_Object string
)
473 struct re_pattern_buffer
*bufp
;
475 bufp
= compile_pattern (regexp
, 0, Qnil
,
476 0, STRING_MULTIBYTE (string
));
478 re_match_object
= string
;
480 val
= re_search (bufp
, SSDATA (string
),
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. */
493 fast_c_string_match_ignore_case (Lisp_Object regexp
,
494 const char *string
, ptrdiff_t len
)
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,
505 val
= re_search (bufp
, string
, len
, 0, len
, 0);
510 /* Like fast_string_match but ignore case. */
513 fast_string_match_ignore_case (Lisp_Object regexp
, Lisp_Object string
)
516 struct re_pattern_buffer
*bufp
;
518 bufp
= compile_pattern (regexp
, 0, Vascii_canon_table
,
519 0, STRING_MULTIBYTE (string
));
521 re_match_object
= string
;
523 val
= re_search (bufp
, SSDATA (string
),
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
537 fast_looking_at (Lisp_Object regexp
, ptrdiff_t pos
, ptrdiff_t pos_byte
, ptrdiff_t limit
, ptrdiff_t limit_byte
, Lisp_Object string
)
540 struct re_pattern_buffer
*buf
;
541 unsigned char *p1
, *p2
;
545 if (STRINGP (string
))
548 pos_byte
= string_char_to_byte (string
, pos
);
550 limit_byte
= string_char_to_byte (string
, limit
);
554 s2
= SBYTES (string
);
555 re_match_object
= string
;
556 multibyte
= STRING_MULTIBYTE (string
);
561 pos_byte
= CHAR_TO_BYTE (pos
);
563 limit_byte
= CHAR_TO_BYTE (limit
);
564 pos_byte
-= BEGV_BYTE
;
565 limit_byte
-= BEGV_BYTE
;
567 s1
= GPT_BYTE
- BEGV_BYTE
;
569 s2
= ZV_BYTE
- GPT_BYTE
;
573 s2
= ZV_BYTE
- BEGV_BYTE
;
578 s1
= ZV_BYTE
- BEGV_BYTE
;
581 re_match_object
= Qnil
;
582 multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
585 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
587 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
588 pos_byte
, NULL
, limit_byte
);
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. */
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;
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. */
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
;
657 if (! end
) end
= BEGV
;
660 newline_cache_on_off (current_buffer
);
661 newline_cache
= current_buffer
->newline_cache
;
666 immediate_quit
= allow_quit
;
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
676 ptrdiff_t ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
677 ptrdiff_t start_byte
;
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
;
686 while (region_cache_forward
687 (current_buffer
, newline_cache
, 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
);
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
;
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
)
740 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
746 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
752 /* The last character to check before the next obstacle. */
753 ptrdiff_t ceiling_byte
= CHAR_TO_BYTE (end
);
754 ptrdiff_t start_byte
;
757 /* Consult the newline cache, if appropriate. */
758 if (target
== '\n' && newline_cache
)
760 ptrdiff_t next_change
;
762 while (region_cache_backward
763 (current_buffer
, newline_cache
, 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
);
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
)
810 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
816 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
822 *shortage
= count
* direction
;
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. */
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
;
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. */
864 start_byte
= CHAR_TO_BYTE (start
);
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
));
876 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
879 if (cursor
!= ceiling_addr
)
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
);
890 if (++cursor
== ceiling_addr
)
896 start_byte
+= cursor
- base
;
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);
909 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
912 if (cursor
!= ceiling_addr
)
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
);
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
;
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. */
950 find_before_next_newline (ptrdiff_t from
, ptrdiff_t to
, ptrdiff_t cnt
)
953 ptrdiff_t pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
961 /* Subroutines of Lisp buffer search functions. */
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
;
970 EMACS_INT n
= direction
;
974 CHECK_NUMBER (count
);
978 CHECK_STRING (string
);
982 lim
= ZV
, lim_byte
= ZV_BYTE
;
984 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
988 CHECK_NUMBER_COERCE_MARKER (bound
);
990 if (n
> 0 ? lim
< PT
: lim
> PT
)
991 error ("Invalid search bound (wrong side of point)");
993 lim
= ZV
, lim_byte
= ZV_BYTE
;
995 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
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
)
1008 (!NILP (BVAR (current_buffer
, case_fold_search
))
1009 ? BVAR (current_buffer
, case_eqv_table
)
1015 xsignal1 (Qsearch_failed
, string
);
1017 if (!EQ (noerror
, Qt
))
1019 if (lim
< BEGV
|| lim
> ZV
)
1021 SET_PT_BOTH (lim
, lim_byte
);
1023 #if 0 /* This would be clean, but maybe programs depend on
1024 a value of nil here. */
1032 if (np
< BEGV
|| np
> ZV
)
1037 return make_number (np
);
1040 /* Return 1 if REGEXP it matches just one constant string. */
1043 trivial_regexp_p (Lisp_Object regexp
)
1045 ptrdiff_t len
= SBYTES (regexp
);
1046 unsigned char *s
= SDATA (regexp
);
1051 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
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':
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) \
1092 temp = Faref (trt, make_number (d)); \
1093 if (INTEGERP (temp)) \
1094 out = XINT (temp); \
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
;
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);
1128 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1130 unsigned char *p1
, *p2
;
1132 struct re_pattern_buffer
*bufp
;
1134 bufp
= compile_pattern (string
,
1135 (NILP (Vinhibit_changing_match_data
)
1136 ? &search_regs
: &search_regs_1
),
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. */
1149 s1
= GPT_BYTE
- BEGV_BYTE
;
1151 s2
= ZV_BYTE
- GPT_BYTE
;
1155 s2
= ZV_BYTE
- BEGV_BYTE
;
1160 s1
= ZV_BYTE
- BEGV_BYTE
;
1163 re_match_object
= Qnil
;
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
);
1177 matcher_overflow ();
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
);
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];
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
);
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
);
1221 matcher_overflow ();
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
);
1234 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1236 XSETBUFFER (last_thing_searched
, current_buffer
);
1237 pos
= search_regs
.end
[0];
1241 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1242 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
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. */
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
);
1280 raw_pattern_size
= SCHARS (string
);
1281 raw_pattern_size_byte
1282 = count_size_as_multibyte (SDATA (string
),
1284 raw_pattern
= alloca (raw_pattern_size_byte
+ 1);
1285 copy_text (SDATA (string
), raw_pattern
,
1286 SCHARS (string
), 0, 1);
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
);
1308 base_pat
= raw_pattern
;
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 character
1317 group (every 64 characters form a group; U+0000..U+003F,
1318 U+0040..U+007F, U+0080..U+00BF, ...). */
1322 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1323 int c
, translated
, inverse
;
1324 int in_charlen
, charlen
;
1326 /* If we got here and the RE flag is set, it's because we're
1327 dealing with a regexp known to be trivial, so the backslash
1328 just quotes the next character. */
1329 if (RE
&& *base_pat
== '\\')
1337 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1342 charlen
= in_charlen
;
1346 /* Translate the character. */
1347 TRANSLATE (translated
, trt
, c
);
1348 charlen
= CHAR_STRING (translated
, str_base
);
1351 /* Check if C has any other case-equivalents. */
1352 TRANSLATE (inverse
, inverse_trt
, c
);
1353 /* If so, check if we can use boyer-moore. */
1354 if (c
!= inverse
&& boyer_moore_ok
)
1356 /* Check if all equivalents belong to the same
1357 group of characters. Note that the check of C
1358 itself is done by the last iteration. */
1359 int this_char_base
= -1;
1361 while (boyer_moore_ok
)
1363 if (ASCII_BYTE_P (inverse
))
1365 if (this_char_base
> 0)
1370 else if (CHAR_BYTE8_P (inverse
))
1371 /* Boyer-moore search can't handle a
1372 translation of an eight-bit
1375 else if (this_char_base
< 0)
1377 this_char_base
= inverse
& ~0x3F;
1379 char_base
= this_char_base
;
1380 else if (this_char_base
!= char_base
)
1383 else if ((inverse
& ~0x3F) != this_char_base
)
1387 TRANSLATE (inverse
, inverse_trt
, inverse
);
1392 /* Store this character into the translated pattern. */
1393 memcpy (pat
, str
, charlen
);
1395 base_pat
+= in_charlen
;
1396 len_byte
-= in_charlen
;
1399 /* If char_base is still negative we didn't find any translated
1400 non-ASCII characters. */
1406 /* Unibyte buffer. */
1410 int c
, translated
, inverse
;
1412 /* If we got here and the RE flag is set, it's because we're
1413 dealing with a regexp known to be trivial, so the backslash
1414 just quotes the next character. */
1415 if (RE
&& *base_pat
== '\\')
1422 TRANSLATE (translated
, trt
, c
);
1423 *pat
++ = translated
;
1424 /* Check that none of C's equivalents violates the
1425 assumptions of boyer_moore. */
1426 TRANSLATE (inverse
, inverse_trt
, c
);
1429 if (inverse
>= 0200)
1436 TRANSLATE (inverse
, inverse_trt
, inverse
);
1441 len_byte
= pat
- patbuf
;
1442 pat
= base_pat
= patbuf
;
1445 return boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1449 return simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1450 pos
, pos_byte
, lim
, lim_byte
);
1454 /* Do a simple string search N times for the string PAT,
1455 whose length is LEN/LEN_BYTE,
1456 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1457 TRT is the translation table.
1459 Return the character position where the match is found.
1460 Otherwise, if M matches remained to be found, return -M.
1462 This kind of search works regardless of what is in PAT and
1463 regardless of what is in TRT. It is used in cases where
1464 boyer_moore cannot work. */
1467 simple_search (EMACS_INT n
, unsigned char *pat
,
1468 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1469 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1470 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1472 int multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1473 int forward
= n
> 0;
1474 /* Number of buffer bytes matched. Note that this may be different
1475 from len_byte in a multibyte buffer. */
1476 ptrdiff_t match_byte
= PTRDIFF_MIN
;
1478 if (lim
> pos
&& multibyte
)
1483 /* Try matching at position POS. */
1484 ptrdiff_t this_pos
= pos
;
1485 ptrdiff_t this_pos_byte
= pos_byte
;
1486 ptrdiff_t this_len
= len
;
1487 unsigned char *p
= pat
;
1488 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1491 while (this_len
> 0)
1493 int charlen
, buf_charlen
;
1496 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1497 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1499 TRANSLATE (buf_ch
, trt
, buf_ch
);
1501 if (buf_ch
!= pat_ch
)
1507 this_pos_byte
+= buf_charlen
;
1513 match_byte
= this_pos_byte
- pos_byte
;
1515 pos_byte
+= match_byte
;
1519 INC_BOTH (pos
, pos_byte
);
1529 /* Try matching at position POS. */
1530 ptrdiff_t this_pos
= pos
;
1531 ptrdiff_t this_len
= len
;
1532 unsigned char *p
= pat
;
1534 if (pos
+ len
> lim
)
1537 while (this_len
> 0)
1540 int buf_ch
= FETCH_BYTE (this_pos
);
1541 TRANSLATE (buf_ch
, trt
, buf_ch
);
1543 if (buf_ch
!= pat_ch
)
1562 /* Backwards search. */
1563 else if (lim
< pos
&& multibyte
)
1568 /* Try matching at position POS. */
1569 ptrdiff_t this_pos
= pos
;
1570 ptrdiff_t this_pos_byte
= pos_byte
;
1571 ptrdiff_t this_len
= len
;
1572 const unsigned char *p
= pat
+ len_byte
;
1574 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1577 while (this_len
> 0)
1581 DEC_BOTH (this_pos
, this_pos_byte
);
1582 PREV_CHAR_BOUNDARY (p
, pat
);
1583 pat_ch
= STRING_CHAR (p
);
1584 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1585 TRANSLATE (buf_ch
, trt
, buf_ch
);
1587 if (buf_ch
!= pat_ch
)
1595 match_byte
= pos_byte
- this_pos_byte
;
1597 pos_byte
= this_pos_byte
;
1601 DEC_BOTH (pos
, pos_byte
);
1611 /* Try matching at position POS. */
1612 ptrdiff_t this_pos
= pos
- len
;
1613 ptrdiff_t this_len
= len
;
1614 unsigned char *p
= pat
;
1619 while (this_len
> 0)
1622 int buf_ch
= FETCH_BYTE (this_pos
);
1623 TRANSLATE (buf_ch
, trt
, buf_ch
);
1625 if (buf_ch
!= pat_ch
)
1647 eassert (match_byte
!= PTRDIFF_MIN
);
1649 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1651 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1661 /* Do Boyer-Moore search N times for the string BASE_PAT,
1662 whose length is LEN_BYTE,
1663 from buffer position POS_BYTE until LIM_BYTE.
1664 DIRECTION says which direction we search in.
1665 TRT and INVERSE_TRT are translation tables.
1666 Characters in PAT are already translated by TRT.
1668 This kind of search works if all the characters in BASE_PAT that
1669 have nontrivial translation are the same aside from the last byte.
1670 This makes it possible to translate just the last byte of a
1671 character, and do so after just a simple test of the context.
1672 CHAR_BASE is nonzero if there is such a non-ASCII character.
1674 If that criterion is not satisfied, do not call this function. */
1677 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1679 Lisp_Object trt
, Lisp_Object inverse_trt
,
1680 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1683 int direction
= ((n
> 0) ? 1 : -1);
1684 register ptrdiff_t dirlen
;
1686 int stride_for_teases
= 0;
1688 register unsigned char *cursor
, *p_limit
;
1689 register ptrdiff_t i
;
1691 unsigned char *pat
, *pat_end
;
1692 int multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1694 unsigned char simple_translate
[0400];
1695 /* These are set to the preceding bytes of a byte to be translated
1696 if char_base is nonzero. As the maximum byte length of a
1697 multibyte character is 5, we have to check at most four previous
1699 int translate_prev_byte1
= 0;
1700 int translate_prev_byte2
= 0;
1701 int translate_prev_byte3
= 0;
1703 /* The general approach is that we are going to maintain that we know
1704 the first (closest to the present position, in whatever direction
1705 we're searching) character that could possibly be the last
1706 (furthest from present position) character of a valid match. We
1707 advance the state of our knowledge by looking at that character
1708 and seeing whether it indeed matches the last character of the
1709 pattern. If it does, we take a closer look. If it does not, we
1710 move our pointer (to putative last characters) as far as is
1711 logically possible. This amount of movement, which I call a
1712 stride, will be the length of the pattern if the actual character
1713 appears nowhere in the pattern, otherwise it will be the distance
1714 from the last occurrence of that character to the end of the
1715 pattern. If the amount is zero we have a possible match. */
1717 /* Here we make a "mickey mouse" BM table. The stride of the search
1718 is determined only by the last character of the putative match.
1719 If that character does not match, we will stride the proper
1720 distance to propose a match that superimposes it on the last
1721 instance of a character that matches it (per trt), or misses
1722 it entirely if there is none. */
1724 dirlen
= len_byte
* direction
;
1726 /* Record position after the end of the pattern. */
1727 pat_end
= base_pat
+ len_byte
;
1728 /* BASE_PAT points to a character that we start scanning from.
1729 It is the first character in a forward search,
1730 the last character in a backward search. */
1732 base_pat
= pat_end
- 1;
1734 /* A character that does not appear in the pattern induces a
1735 stride equal to the pattern length. */
1736 for (i
= 0; i
< 0400; i
++)
1739 /* We use this for translation, instead of TRT itself.
1740 We fill this in to handle the characters that actually
1741 occur in the pattern. Others don't matter anyway! */
1742 for (i
= 0; i
< 0400; i
++)
1743 simple_translate
[i
] = i
;
1747 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1748 byte following them are the target of translation. */
1749 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1750 int cblen
= CHAR_STRING (char_base
, str
);
1752 translate_prev_byte1
= str
[cblen
- 2];
1755 translate_prev_byte2
= str
[cblen
- 3];
1757 translate_prev_byte3
= str
[cblen
- 4];
1764 unsigned char *ptr
= base_pat
+ i
;
1768 /* If the byte currently looking at is the last of a
1769 character to check case-equivalents, set CH to that
1770 character. An ASCII character and a non-ASCII character
1771 matching with CHAR_BASE are to be checked. */
1774 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1777 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1779 unsigned char *charstart
= ptr
- 1;
1781 while (! (CHAR_HEAD_P (*charstart
)))
1783 ch
= STRING_CHAR (charstart
);
1784 if (char_base
!= (ch
& ~0x3F))
1788 if (ch
>= 0200 && multibyte
)
1789 j
= (ch
& 0x3F) | 0200;
1794 stride_for_teases
= BM_tab
[j
];
1796 BM_tab
[j
] = dirlen
- i
;
1797 /* A translation table is accompanied by its inverse -- see
1798 comment following downcase_table for details. */
1801 int starting_ch
= ch
;
1806 TRANSLATE (ch
, inverse_trt
, ch
);
1807 if (ch
>= 0200 && multibyte
)
1808 j
= (ch
& 0x3F) | 0200;
1812 /* For all the characters that map into CH,
1813 set up simple_translate to map the last byte
1815 simple_translate
[j
] = starting_j
;
1816 if (ch
== starting_ch
)
1818 BM_tab
[j
] = dirlen
- i
;
1827 stride_for_teases
= BM_tab
[j
];
1828 BM_tab
[j
] = dirlen
- i
;
1830 /* stride_for_teases tells how much to stride if we get a
1831 match on the far character but are subsequently
1832 disappointed, by recording what the stride would have been
1833 for that character if the last character had been
1836 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1837 /* loop invariant - POS_BYTE points at where last char (first
1838 char if reverse) of pattern would align in a possible match. */
1842 unsigned char *tail_end_ptr
;
1844 /* It's been reported that some (broken) compiler thinks that
1845 Boolean expressions in an arithmetic context are unsigned.
1846 Using an explicit ?1:0 prevents this. */
1847 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1849 return (n
* (0 - direction
));
1850 /* First we do the part we can by pointers (maybe nothing) */
1853 limit
= pos_byte
- dirlen
+ direction
;
1856 limit
= BUFFER_CEILING_OF (limit
);
1857 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1858 can take on without hitting edge of buffer or the gap. */
1859 limit
= min (limit
, pos_byte
+ 20000);
1860 limit
= min (limit
, lim_byte
- 1);
1864 limit
= BUFFER_FLOOR_OF (limit
);
1865 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1866 can take on without hitting edge of buffer or the gap. */
1867 limit
= max (limit
, pos_byte
- 20000);
1868 limit
= max (limit
, lim_byte
);
1870 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1871 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1873 if ((limit
- pos_byte
) * direction
> 20)
1877 p_limit
= BYTE_POS_ADDR (limit
);
1878 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1879 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1880 while (1) /* use one cursor setting as long as i can */
1882 if (direction
> 0) /* worth duplicating */
1884 while (cursor
<= p_limit
)
1886 if (BM_tab
[*cursor
] == 0)
1888 cursor
+= BM_tab
[*cursor
];
1893 while (cursor
>= p_limit
)
1895 if (BM_tab
[*cursor
] == 0)
1897 cursor
+= BM_tab
[*cursor
];
1900 /* If you are here, cursor is beyond the end of the
1901 searched region. You fail to match within the
1902 permitted region and would otherwise try a character
1903 beyond that region. */
1907 i
= dirlen
- direction
;
1910 while ((i
-= direction
) + direction
!= 0)
1913 cursor
-= direction
;
1914 /* Translate only the last byte of a character. */
1916 || ((cursor
== tail_end_ptr
1917 || CHAR_HEAD_P (cursor
[1]))
1918 && (CHAR_HEAD_P (cursor
[0])
1919 /* Check if this is the last byte of
1920 a translatable character. */
1921 || (translate_prev_byte1
== cursor
[-1]
1922 && (CHAR_HEAD_P (translate_prev_byte1
)
1923 || (translate_prev_byte2
== cursor
[-2]
1924 && (CHAR_HEAD_P (translate_prev_byte2
)
1925 || (translate_prev_byte3
== cursor
[-3]))))))))
1926 ch
= simple_translate
[*cursor
];
1935 while ((i
-= direction
) + direction
!= 0)
1937 cursor
-= direction
;
1938 if (pat
[i
] != *cursor
)
1942 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1943 if (i
+ direction
== 0)
1945 ptrdiff_t position
, start
, end
;
1947 cursor
-= direction
;
1949 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1950 ? 1 - len_byte
: 0);
1951 set_search_regs (position
, len_byte
);
1953 if (NILP (Vinhibit_changing_match_data
))
1955 start
= search_regs
.start
[0];
1956 end
= search_regs
.end
[0];
1959 /* If Vinhibit_changing_match_data is non-nil,
1960 search_regs will not be changed. So let's
1961 compute start and end here. */
1963 start
= BYTE_TO_CHAR (position
);
1964 end
= BYTE_TO_CHAR (position
+ len_byte
);
1967 if ((n
-= direction
) != 0)
1968 cursor
+= dirlen
; /* to resume search */
1970 return direction
> 0 ? end
: start
;
1973 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1975 pos_byte
+= cursor
- p2
;
1978 /* Now we'll pick up a clump that has to be done the hard
1979 way because it covers a discontinuity. */
1981 limit
= ((direction
> 0)
1982 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1983 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1984 limit
= ((direction
> 0)
1985 ? min (limit
+ len_byte
, lim_byte
- 1)
1986 : max (limit
- len_byte
, lim_byte
));
1987 /* LIMIT is now the last value POS_BYTE can have
1988 and still be valid for a possible match. */
1991 /* This loop can be coded for space rather than
1992 speed because it will usually run only once.
1993 (the reach is at most len + 21, and typically
1994 does not exceed len). */
1995 while ((limit
- pos_byte
) * direction
>= 0)
1997 int ch
= FETCH_BYTE (pos_byte
);
1998 if (BM_tab
[ch
] == 0)
2000 pos_byte
+= BM_tab
[ch
];
2002 break; /* ran off the end */
2005 /* Found what might be a match. */
2006 i
= dirlen
- direction
;
2007 while ((i
-= direction
) + direction
!= 0)
2011 pos_byte
-= direction
;
2012 ptr
= BYTE_POS_ADDR (pos_byte
);
2013 /* Translate only the last byte of a character. */
2015 || ((ptr
== tail_end_ptr
2016 || CHAR_HEAD_P (ptr
[1]))
2017 && (CHAR_HEAD_P (ptr
[0])
2018 /* Check if this is the last byte of a
2019 translatable character. */
2020 || (translate_prev_byte1
== ptr
[-1]
2021 && (CHAR_HEAD_P (translate_prev_byte1
)
2022 || (translate_prev_byte2
== ptr
[-2]
2023 && (CHAR_HEAD_P (translate_prev_byte2
)
2024 || translate_prev_byte3
== ptr
[-3])))))))
2025 ch
= simple_translate
[*ptr
];
2031 /* Above loop has moved POS_BYTE part or all the way
2032 back to the first pos (last pos if reverse).
2033 Set it once again at the last (first if reverse) char. */
2034 pos_byte
+= dirlen
- i
- direction
;
2035 if (i
+ direction
== 0)
2037 ptrdiff_t position
, start
, end
;
2038 pos_byte
-= direction
;
2040 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2041 set_search_regs (position
, len_byte
);
2043 if (NILP (Vinhibit_changing_match_data
))
2045 start
= search_regs
.start
[0];
2046 end
= search_regs
.end
[0];
2049 /* If Vinhibit_changing_match_data is non-nil,
2050 search_regs will not be changed. So let's
2051 compute start and end here. */
2053 start
= BYTE_TO_CHAR (position
);
2054 end
= BYTE_TO_CHAR (position
+ len_byte
);
2057 if ((n
-= direction
) != 0)
2058 pos_byte
+= dirlen
; /* to resume search */
2060 return direction
> 0 ? end
: start
;
2063 pos_byte
+= stride_for_teases
;
2066 /* We have done one clump. Can we continue? */
2067 if ((lim_byte
- pos_byte
) * direction
< 0)
2068 return ((0 - n
) * direction
);
2070 return BYTE_TO_CHAR (pos_byte
);
2073 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2074 for the overall match just found in the current buffer.
2075 Also clear out the match data for registers 1 and up. */
2078 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2082 if (!NILP (Vinhibit_changing_match_data
))
2085 /* Make sure we have registers in which to store
2086 the match position. */
2087 if (search_regs
.num_regs
== 0)
2089 search_regs
.start
= xmalloc (2 * sizeof (regoff_t
));
2090 search_regs
.end
= xmalloc (2 * sizeof (regoff_t
));
2091 search_regs
.num_regs
= 2;
2094 /* Clear out the other registers. */
2095 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2097 search_regs
.start
[i
] = -1;
2098 search_regs
.end
[i
] = -1;
2101 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2102 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2103 XSETBUFFER (last_thing_searched
, current_buffer
);
2106 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2107 "MSearch backward: ",
2108 doc
: /* Search backward from point for STRING.
2109 Set point to the beginning of the occurrence found, and return point.
2110 An optional second argument bounds the search; it is a buffer position.
2111 The match found must not extend before that position.
2112 Optional third argument, if t, means if fail just return nil (no error).
2113 If not nil and not t, position at limit of search and return nil.
2114 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2115 successive occurrences. If COUNT is negative, search forward,
2116 instead of backward, for -COUNT occurrences.
2118 Search case-sensitivity is determined by the value of the variable
2119 `case-fold-search', which see.
2121 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2122 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2124 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2127 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2128 doc
: /* Search forward from point for STRING.
2129 Set point to the end of the occurrence found, and return point.
2130 An optional second argument bounds the search; it is a buffer position.
2131 The match found must not extend after that position. A value of nil is
2132 equivalent to (point-max).
2133 Optional third argument, if t, means if fail just return nil (no error).
2134 If not nil and not t, move to limit of search and return nil.
2135 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2136 successive occurrences. If COUNT is negative, search backward,
2137 instead of forward, for -COUNT occurrences.
2139 Search case-sensitivity is determined by the value of the variable
2140 `case-fold-search', which see.
2142 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2143 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2145 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2148 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2149 "sRE search backward: ",
2150 doc
: /* Search backward from point for match for regular expression REGEXP.
2151 Set point to the beginning of the match, and return point.
2152 The match found is the one starting last in the buffer
2153 and yet ending before the origin of the search.
2154 An optional second argument bounds the search; it is a buffer position.
2155 The match found must start at or after that position.
2156 Optional third argument, if t, means if fail just return nil (no error).
2157 If not nil and not t, move to limit of search and return nil.
2158 Optional fourth argument is repeat count--search for successive occurrences.
2160 Search case-sensitivity is determined by the value of the variable
2161 `case-fold-search', which see.
2163 See also the functions `match-beginning', `match-end', `match-string',
2164 and `replace-match'. */)
2165 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2167 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2170 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2172 doc
: /* Search forward from point for regular expression REGEXP.
2173 Set point to the end of the occurrence found, and return point.
2174 An optional second argument bounds the search; it is a buffer position.
2175 The match found must not extend after that position.
2176 Optional third argument, if t, means if fail just return nil (no error).
2177 If not nil and not t, move to limit of search and return nil.
2178 Optional fourth argument is repeat count--search for successive occurrences.
2180 Search case-sensitivity is determined by the value of the variable
2181 `case-fold-search', which see.
2183 See also the functions `match-beginning', `match-end', `match-string',
2184 and `replace-match'. */)
2185 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2187 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2190 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2191 "sPosix search backward: ",
2192 doc
: /* Search backward from point for match for regular expression REGEXP.
2193 Find the longest match in accord with Posix regular expression rules.
2194 Set point to the beginning of the match, and return point.
2195 The match found is the one starting last in the buffer
2196 and yet ending before the origin of the search.
2197 An optional second argument bounds the search; it is a buffer position.
2198 The match found must start at or after that position.
2199 Optional third argument, if t, means if fail just return nil (no error).
2200 If not nil and not t, move to limit of search and return nil.
2201 Optional fourth argument is repeat count--search for successive occurrences.
2203 Search case-sensitivity is determined by the value of the variable
2204 `case-fold-search', which see.
2206 See also the functions `match-beginning', `match-end', `match-string',
2207 and `replace-match'. */)
2208 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2210 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2213 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2215 doc
: /* Search forward from point for regular expression REGEXP.
2216 Find the longest match in accord with Posix regular expression rules.
2217 Set point to the end of the occurrence found, and return point.
2218 An optional second argument bounds the search; it is a buffer position.
2219 The match found must not extend after that position.
2220 Optional third argument, if t, means if fail just return nil (no error).
2221 If not nil and not t, move to limit of search and return nil.
2222 Optional fourth argument is repeat count--search for successive occurrences.
2224 Search case-sensitivity is determined by the value of the variable
2225 `case-fold-search', which see.
2227 See also the functions `match-beginning', `match-end', `match-string',
2228 and `replace-match'. */)
2229 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2231 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2234 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2235 doc
: /* Replace text matched by last search with NEWTEXT.
2236 Leave point at the end of the replacement text.
2238 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2239 the replacement text. Otherwise, maybe capitalize the whole text, or
2240 maybe just word initials, based on the replaced text. If the replaced
2241 text has only capital letters and has at least one multiletter word,
2242 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2243 in the replaced text, capitalize each word in NEWTEXT.
2245 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2246 Otherwise treat `\\' as special:
2247 `\\&' in NEWTEXT means substitute original matched text.
2248 `\\N' means substitute what matched the Nth `\\(...\\)'.
2249 If Nth parens didn't match, substitute nothing.
2250 `\\\\' means insert one `\\'.
2251 `\\?' is treated literally
2252 (for compatibility with `query-replace-regexp').
2253 Any other character following `\\' signals an error.
2254 Case conversion does not apply to these substitutions.
2256 If optional fourth argument STRING is non-nil, it should be a string
2257 to act on; this should be the string on which the previous match was
2258 done via `string-match'. In this case, `replace-match' creates and
2259 returns a new string, made by copying STRING and replacing the part of
2260 STRING that was matched (the original STRING itself is not altered).
2262 The optional fifth argument SUBEXP specifies a subexpression;
2263 it says to replace just that subexpression with NEWTEXT,
2264 rather than replacing the entire matched text.
2265 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2266 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2267 NEWTEXT in place of subexp N.
2268 This is useful only after a regular expression search or match,
2269 since only regular expressions have distinguished subexpressions. */)
2270 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2272 enum { nochange
, all_caps
, cap_initial
} case_action
;
2273 register ptrdiff_t pos
, pos_byte
;
2274 int some_multiletter_word
;
2277 int some_nonuppercase_initial
;
2278 register int c
, prevc
;
2280 ptrdiff_t opoint
, newpoint
;
2282 CHECK_STRING (newtext
);
2284 if (! NILP (string
))
2285 CHECK_STRING (string
);
2287 case_action
= nochange
; /* We tried an initialization */
2288 /* but some C compilers blew it */
2290 if (search_regs
.num_regs
<= 0)
2291 error ("`replace-match' called before any match found");
2297 CHECK_NUMBER (subexp
);
2298 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2299 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2300 sub
= XINT (subexp
);
2305 if (search_regs
.start
[sub
] < BEGV
2306 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2307 || search_regs
.end
[sub
] > ZV
)
2308 args_out_of_range (make_number (search_regs
.start
[sub
]),
2309 make_number (search_regs
.end
[sub
]));
2313 if (search_regs
.start
[sub
] < 0
2314 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2315 || search_regs
.end
[sub
] > SCHARS (string
))
2316 args_out_of_range (make_number (search_regs
.start
[sub
]),
2317 make_number (search_regs
.end
[sub
]));
2320 if (NILP (fixedcase
))
2322 /* Decide how to casify by examining the matched text. */
2325 pos
= search_regs
.start
[sub
];
2326 last
= search_regs
.end
[sub
];
2329 pos_byte
= CHAR_TO_BYTE (pos
);
2331 pos_byte
= string_char_to_byte (string
, pos
);
2334 case_action
= all_caps
;
2336 /* some_multiletter_word is set nonzero if any original word
2337 is more than one letter long. */
2338 some_multiletter_word
= 0;
2340 some_nonuppercase_initial
= 0;
2347 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2348 INC_BOTH (pos
, pos_byte
);
2351 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2355 /* Cannot be all caps if any original char is lower case */
2358 if (SYNTAX (prevc
) != Sword
)
2359 some_nonuppercase_initial
= 1;
2361 some_multiletter_word
= 1;
2363 else if (uppercasep (c
))
2366 if (SYNTAX (prevc
) != Sword
)
2369 some_multiletter_word
= 1;
2373 /* If the initial is a caseless word constituent,
2374 treat that like a lowercase initial. */
2375 if (SYNTAX (prevc
) != Sword
)
2376 some_nonuppercase_initial
= 1;
2382 /* Convert to all caps if the old text is all caps
2383 and has at least one multiletter word. */
2384 if (! some_lowercase
&& some_multiletter_word
)
2385 case_action
= all_caps
;
2386 /* Capitalize each word, if the old text has all capitalized words. */
2387 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2388 case_action
= cap_initial
;
2389 else if (!some_nonuppercase_initial
&& some_uppercase
)
2390 /* Should x -> yz, operating on X, give Yz or YZ?
2391 We'll assume the latter. */
2392 case_action
= all_caps
;
2394 case_action
= nochange
;
2397 /* Do replacement in a string. */
2400 Lisp_Object before
, after
;
2402 before
= Fsubstring (string
, make_number (0),
2403 make_number (search_regs
.start
[sub
]));
2404 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2406 /* Substitute parts of the match into NEWTEXT
2410 ptrdiff_t lastpos
= 0;
2411 ptrdiff_t lastpos_byte
= 0;
2412 /* We build up the substituted string in ACCUM. */
2415 ptrdiff_t length
= SBYTES (newtext
);
2419 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2421 ptrdiff_t substart
= -1;
2422 ptrdiff_t subend
= 0;
2423 int delbackslash
= 0;
2425 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2429 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2433 substart
= search_regs
.start
[sub
];
2434 subend
= search_regs
.end
[sub
];
2436 else if (c
>= '1' && c
<= '9')
2438 if (c
- '0' < search_regs
.num_regs
2439 && 0 <= search_regs
.start
[c
- '0'])
2441 substart
= search_regs
.start
[c
- '0'];
2442 subend
= search_regs
.end
[c
- '0'];
2446 /* If that subexp did not match,
2447 replace \\N with nothing. */
2455 error ("Invalid use of `\\' in replacement text");
2459 if (pos
- 2 != lastpos
)
2460 middle
= substring_both (newtext
, lastpos
,
2462 pos
- 2, pos_byte
- 2);
2465 accum
= concat3 (accum
, middle
,
2467 make_number (substart
),
2468 make_number (subend
)));
2470 lastpos_byte
= pos_byte
;
2472 else if (delbackslash
)
2474 middle
= substring_both (newtext
, lastpos
,
2476 pos
- 1, pos_byte
- 1);
2478 accum
= concat2 (accum
, middle
);
2480 lastpos_byte
= pos_byte
;
2485 middle
= substring_both (newtext
, lastpos
,
2491 newtext
= concat2 (accum
, middle
);
2494 /* Do case substitution in NEWTEXT if desired. */
2495 if (case_action
== all_caps
)
2496 newtext
= Fupcase (newtext
);
2497 else if (case_action
== cap_initial
)
2498 newtext
= Fupcase_initials (newtext
);
2500 return concat3 (before
, newtext
, after
);
2503 /* Record point, then move (quietly) to the start of the match. */
2504 if (PT
>= search_regs
.end
[sub
])
2506 else if (PT
> search_regs
.start
[sub
])
2507 opoint
= search_regs
.end
[sub
] - ZV
;
2511 /* If we want non-literal replacement,
2512 perform substitution on the replacement string. */
2515 ptrdiff_t length
= SBYTES (newtext
);
2516 unsigned char *substed
;
2517 ptrdiff_t substed_alloc_size
, substed_len
;
2518 int buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2519 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2520 int really_changed
= 0;
2522 substed_alloc_size
= ((STRING_BYTES_BOUND
- 100) / 2 < length
2523 ? STRING_BYTES_BOUND
2524 : length
* 2 + 100);
2525 substed
= xmalloc (substed_alloc_size
);
2528 /* Go thru NEWTEXT, producing the actual text to insert in
2529 SUBSTED while adjusting multibyteness to that of the current
2532 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2534 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2535 const unsigned char *add_stuff
= NULL
;
2536 ptrdiff_t add_len
= 0;
2541 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2543 c
= multibyte_char_to_unibyte (c
);
2547 /* Note that we don't have to increment POS. */
2548 c
= SREF (newtext
, pos_byte
++);
2550 MAKE_CHAR_MULTIBYTE (c
);
2553 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2554 or set IDX to a match index, which means put that part
2555 of the buffer text into SUBSTED. */
2563 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2565 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2566 c
= multibyte_char_to_unibyte (c
);
2570 c
= SREF (newtext
, pos_byte
++);
2572 MAKE_CHAR_MULTIBYTE (c
);
2577 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2579 if (search_regs
.start
[c
- '0'] >= 1)
2583 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2587 error ("Invalid use of `\\' in replacement text");
2592 add_len
= CHAR_STRING (c
, str
);
2596 /* If we want to copy part of a previous match,
2597 set up ADD_STUFF and ADD_LEN to point to it. */
2600 ptrdiff_t begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2601 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2602 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2603 move_gap (search_regs
.start
[idx
]);
2604 add_stuff
= BYTE_POS_ADDR (begbyte
);
2607 /* Now the stuff we want to add to SUBSTED
2608 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2610 /* Make sure SUBSTED is big enough. */
2611 if (substed_alloc_size
- substed_len
< add_len
)
2613 xpalloc (substed
, &substed_alloc_size
,
2614 add_len
- (substed_alloc_size
- substed_len
),
2615 STRING_BYTES_BOUND
, 1);
2617 /* Now add to the end of SUBSTED. */
2620 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2621 substed_len
+= add_len
;
2630 multibyte_chars_in_text (substed
, substed_len
);
2632 newtext
= make_multibyte_string ((char *) substed
, nchars
,
2636 newtext
= make_unibyte_string ((char *) substed
, substed_len
);
2641 /* Replace the old text with the new in the cleanest possible way. */
2642 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2644 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2646 if (case_action
== all_caps
)
2647 Fupcase_region (make_number (search_regs
.start
[sub
]),
2648 make_number (newpoint
));
2649 else if (case_action
== cap_initial
)
2650 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2651 make_number (newpoint
));
2653 /* Adjust search data for this change. */
2655 ptrdiff_t oldend
= search_regs
.end
[sub
];
2656 ptrdiff_t oldstart
= search_regs
.start
[sub
];
2657 ptrdiff_t change
= newpoint
- search_regs
.end
[sub
];
2660 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2662 if (search_regs
.start
[i
] >= oldend
)
2663 search_regs
.start
[i
] += change
;
2664 else if (search_regs
.start
[i
] > oldstart
)
2665 search_regs
.start
[i
] = oldstart
;
2666 if (search_regs
.end
[i
] >= oldend
)
2667 search_regs
.end
[i
] += change
;
2668 else if (search_regs
.end
[i
] > oldstart
)
2669 search_regs
.end
[i
] = oldstart
;
2673 /* Put point back where it was in the text. */
2675 TEMP_SET_PT (opoint
+ ZV
);
2677 TEMP_SET_PT (opoint
);
2679 /* Now move point "officially" to the start of the inserted replacement. */
2680 move_if_not_intangible (newpoint
);
2686 match_limit (Lisp_Object num
, int beginningp
)
2693 args_out_of_range (num
, make_number (0));
2694 if (search_regs
.num_regs
<= 0)
2695 error ("No match data, because no search succeeded");
2696 if (n
>= search_regs
.num_regs
2697 || search_regs
.start
[n
] < 0)
2699 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2700 : search_regs
.end
[n
]));
2703 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2704 doc
: /* Return position of start of text matched by last search.
2705 SUBEXP, a number, specifies which parenthesized expression in the last
2707 Value is nil if SUBEXPth pair didn't match, or there were less than
2709 Zero means the entire text matched by the whole regexp or whole string. */)
2710 (Lisp_Object subexp
)
2712 return match_limit (subexp
, 1);
2715 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2716 doc
: /* Return position of end of text matched by last search.
2717 SUBEXP, a number, specifies which parenthesized expression in the last
2719 Value is nil if SUBEXPth pair didn't match, or there were less than
2721 Zero means the entire text matched by the whole regexp or whole string. */)
2722 (Lisp_Object subexp
)
2724 return match_limit (subexp
, 0);
2727 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2728 doc
: /* Return a list containing all info on what the last search matched.
2729 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2730 All the elements are markers or nil (nil if the Nth pair didn't match)
2731 if the last match was on a buffer; integers or nil if a string was matched.
2732 Use `set-match-data' to reinstate the data in this list.
2734 If INTEGERS (the optional first argument) is non-nil, always use
2735 integers \(rather than markers) to represent buffer positions. In
2736 this case, and if the last match was in a buffer, the buffer will get
2737 stored as one additional element at the end of the list.
2739 If REUSE is a list, reuse it as part of the value. If REUSE is long
2740 enough to hold all the values, and if INTEGERS is non-nil, no consing
2743 If optional third arg RESEAT is non-nil, any previous markers on the
2744 REUSE list will be modified to point to nowhere.
2746 Return value is undefined if the last search failed. */)
2747 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2749 Lisp_Object tail
, prev
;
2754 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2755 if (MARKERP (XCAR (tail
)))
2757 unchain_marker (XMARKER (XCAR (tail
)));
2758 XSETCAR (tail
, Qnil
);
2761 if (NILP (last_thing_searched
))
2766 data
= alloca ((2 * search_regs
.num_regs
+ 1) * sizeof *data
);
2769 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2771 ptrdiff_t start
= search_regs
.start
[i
];
2774 if (EQ (last_thing_searched
, Qt
)
2775 || ! NILP (integers
))
2777 XSETFASTINT (data
[2 * i
], start
);
2778 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2780 else if (BUFFERP (last_thing_searched
))
2782 data
[2 * i
] = Fmake_marker ();
2783 Fset_marker (data
[2 * i
],
2784 make_number (start
),
2785 last_thing_searched
);
2786 data
[2 * i
+ 1] = Fmake_marker ();
2787 Fset_marker (data
[2 * i
+ 1],
2788 make_number (search_regs
.end
[i
]),
2789 last_thing_searched
);
2792 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2798 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2801 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2803 data
[len
] = last_thing_searched
;
2807 /* If REUSE is not usable, cons up the values and return them. */
2808 if (! CONSP (reuse
))
2809 return Flist (len
, data
);
2811 /* If REUSE is a list, store as many value elements as will fit
2812 into the elements of REUSE. */
2813 for (i
= 0, tail
= reuse
; CONSP (tail
);
2814 i
++, tail
= XCDR (tail
))
2817 XSETCAR (tail
, data
[i
]);
2819 XSETCAR (tail
, Qnil
);
2823 /* If we couldn't fit all value elements into REUSE,
2824 cons up the rest of them and add them to the end of REUSE. */
2826 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2831 /* We used to have an internal use variant of `reseat' described as:
2833 If RESEAT is `evaporate', put the markers back on the free list
2834 immediately. No other references to the markers must exist in this
2835 case, so it is used only internally on the unwind stack and
2836 save-match-data from Lisp.
2838 But it was ill-conceived: those supposedly-internal markers get exposed via
2839 the undo-list, so freeing them here is unsafe. */
2841 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2842 doc
: /* Set internal data on last search match from elements of LIST.
2843 LIST should have been created by calling `match-data' previously.
2845 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2846 (register Lisp_Object list
, Lisp_Object reseat
)
2849 register Lisp_Object marker
;
2851 if (running_asynch_code
)
2852 save_search_regs ();
2856 /* Unless we find a marker with a buffer or an explicit buffer
2857 in LIST, assume that this match data came from a string. */
2858 last_thing_searched
= Qt
;
2860 /* Allocate registers if they don't already exist. */
2862 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
2864 if (length
> search_regs
.num_regs
)
2866 ptrdiff_t num_regs
= search_regs
.num_regs
;
2867 if (PTRDIFF_MAX
< length
)
2868 memory_full (SIZE_MAX
);
2870 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
2871 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
2873 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
2875 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
2876 search_regs
.start
[i
] = -1;
2878 search_regs
.num_regs
= num_regs
;
2881 for (i
= 0; CONSP (list
); i
++)
2883 marker
= XCAR (list
);
2884 if (BUFFERP (marker
))
2886 last_thing_searched
= marker
;
2893 search_regs
.start
[i
] = -1;
2902 if (MARKERP (marker
))
2904 if (XMARKER (marker
)->buffer
== 0)
2905 XSETFASTINT (marker
, 0);
2907 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2910 CHECK_NUMBER_COERCE_MARKER (marker
);
2913 if (!NILP (reseat
) && MARKERP (m
))
2915 unchain_marker (XMARKER (m
));
2916 XSETCAR (list
, Qnil
);
2919 if ((list
= XCDR (list
), !CONSP (list
)))
2922 m
= marker
= XCAR (list
);
2924 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2925 XSETFASTINT (marker
, 0);
2927 CHECK_NUMBER_COERCE_MARKER (marker
);
2928 if ((XINT (from
) < 0
2929 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
2930 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
2931 && (XINT (marker
) < 0
2932 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
2933 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
2935 search_regs
.start
[i
] = XINT (from
);
2936 search_regs
.end
[i
] = XINT (marker
);
2940 search_regs
.start
[i
] = -1;
2943 if (!NILP (reseat
) && MARKERP (m
))
2945 unchain_marker (XMARKER (m
));
2946 XSETCAR (list
, Qnil
);
2952 for (; i
< search_regs
.num_regs
; i
++)
2953 search_regs
.start
[i
] = -1;
2959 /* If non-zero the match data have been saved in saved_search_regs
2960 during the execution of a sentinel or filter. */
2961 static int search_regs_saved
;
2962 static struct re_registers saved_search_regs
;
2963 static Lisp_Object saved_last_thing_searched
;
2965 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2966 if asynchronous code (filter or sentinel) is running. */
2968 save_search_regs (void)
2970 if (!search_regs_saved
)
2972 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2973 saved_search_regs
.start
= search_regs
.start
;
2974 saved_search_regs
.end
= search_regs
.end
;
2975 saved_last_thing_searched
= last_thing_searched
;
2976 last_thing_searched
= Qnil
;
2977 search_regs
.num_regs
= 0;
2978 search_regs
.start
= 0;
2979 search_regs
.end
= 0;
2981 search_regs_saved
= 1;
2985 /* Called upon exit from filters and sentinels. */
2987 restore_search_regs (void)
2989 if (search_regs_saved
)
2991 if (search_regs
.num_regs
> 0)
2993 xfree (search_regs
.start
);
2994 xfree (search_regs
.end
);
2996 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2997 search_regs
.start
= saved_search_regs
.start
;
2998 search_regs
.end
= saved_search_regs
.end
;
2999 last_thing_searched
= saved_last_thing_searched
;
3000 saved_last_thing_searched
= Qnil
;
3001 search_regs_saved
= 0;
3006 unwind_set_match_data (Lisp_Object list
)
3008 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3009 return Fset_match_data (list
, Qt
);
3012 /* Called to unwind protect the match data. */
3014 record_unwind_save_match_data (void)
3016 record_unwind_protect (unwind_set_match_data
,
3017 Fmatch_data (Qnil
, Qnil
, Qnil
));
3020 /* Quote a string to deactivate reg-expr chars */
3022 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3023 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3024 (Lisp_Object string
)
3026 register char *in
, *out
, *end
;
3027 register char *temp
;
3028 int backslashes_added
= 0;
3030 CHECK_STRING (string
);
3032 temp
= alloca (SBYTES (string
) * 2);
3034 /* Now copy the data into the new string, inserting escapes. */
3036 in
= SSDATA (string
);
3037 end
= in
+ SBYTES (string
);
3040 for (; in
!= end
; in
++)
3043 || *in
== '*' || *in
== '.' || *in
== '\\'
3044 || *in
== '?' || *in
== '+'
3045 || *in
== '^' || *in
== '$')
3046 *out
++ = '\\', backslashes_added
++;
3050 return make_specified_string (temp
,
3051 SCHARS (string
) + backslashes_added
,
3053 STRING_MULTIBYTE (string
));
3057 syms_of_search (void)
3061 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3063 searchbufs
[i
].buf
.allocated
= 100;
3064 searchbufs
[i
].buf
.buffer
= xmalloc (100);
3065 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3066 searchbufs
[i
].regexp
= Qnil
;
3067 searchbufs
[i
].whitespace_regexp
= Qnil
;
3068 searchbufs
[i
].syntax_table
= Qnil
;
3069 staticpro (&searchbufs
[i
].regexp
);
3070 staticpro (&searchbufs
[i
].whitespace_regexp
);
3071 staticpro (&searchbufs
[i
].syntax_table
);
3072 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3074 searchbuf_head
= &searchbufs
[0];
3076 DEFSYM (Qsearch_failed
, "search-failed");
3077 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3079 Fput (Qsearch_failed
, Qerror_conditions
,
3080 listn (CONSTYPE_PURE
, 2, Qsearch_failed
, Qerror
));
3081 Fput (Qsearch_failed
, Qerror_message
,
3082 build_pure_c_string ("Search failed"));
3084 Fput (Qinvalid_regexp
, Qerror_conditions
,
3085 listn (CONSTYPE_PURE
, 2, Qinvalid_regexp
, Qerror
));
3086 Fput (Qinvalid_regexp
, Qerror_message
,
3087 build_pure_c_string ("Invalid regexp"));
3089 last_thing_searched
= Qnil
;
3090 staticpro (&last_thing_searched
);
3092 saved_last_thing_searched
= Qnil
;
3093 staticpro (&saved_last_thing_searched
);
3095 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3096 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3097 Some commands use this for user-specified regexps.
3098 Spaces that occur inside character classes or repetition operators
3099 or other such regexp constructs are not replaced with this.
3100 A value of nil (which is the normal value) means treat spaces literally. */);
3101 Vsearch_spaces_regexp
= Qnil
;
3103 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3104 doc
: /* Internal use only.
3105 If non-nil, the primitive searching and matching functions
3106 such as `looking-at', `string-match', `re-search-forward', etc.,
3107 do not set the match data. The proper way to use this variable
3108 is to bind it with `let' around a small expression. */);
3109 Vinhibit_changing_match_data
= Qnil
;
3111 defsubr (&Slooking_at
);
3112 defsubr (&Sposix_looking_at
);
3113 defsubr (&Sstring_match
);
3114 defsubr (&Sposix_string_match
);
3115 defsubr (&Ssearch_forward
);
3116 defsubr (&Ssearch_backward
);
3117 defsubr (&Sre_search_forward
);
3118 defsubr (&Sre_search_backward
);
3119 defsubr (&Sposix_search_forward
);
3120 defsubr (&Sposix_search_backward
);
3121 defsubr (&Sreplace_match
);
3122 defsubr (&Smatch_beginning
);
3123 defsubr (&Smatch_end
);
3124 defsubr (&Smatch_data
);
3125 defsubr (&Sset_match_data
);
3126 defsubr (&Sregexp_quote
);