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
);
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
;
179 = (unsigned char *) xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
183 /* Clear the regexp cache w.r.t. a particular syntax table,
184 because it was changed.
185 There is no danger of memory leak here because re_compile_pattern
186 automagically manages the memory in each re_pattern_buffer struct,
187 based on its `allocated' and `buffer' values. */
189 clear_regexp_cache (void)
193 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
194 /* It's tempting to compare with the syntax-table we've actually changed,
195 but it's not sufficient because char-table inheritance means that
196 modifying one syntax-table can change others at the same time. */
197 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
198 searchbufs
[i
].regexp
= Qnil
;
201 /* Compile a regexp if necessary, but first check to see if there's one in
203 PATTERN is the pattern to compile.
204 TRANSLATE is a translation table for ignoring case, or nil for none.
205 REGP is the structure that says where to store the "register"
206 values that will result from matching this pattern.
207 If it is 0, we should compile the pattern not to record any
208 subexpression bounds.
209 POSIX is nonzero if we want full backtracking (POSIX style)
210 for this pattern. 0 means backtrack only enough to get a valid match. */
212 struct re_pattern_buffer
*
213 compile_pattern (Lisp_Object pattern
, struct re_registers
*regp
, Lisp_Object translate
, int posix
, int multibyte
)
215 struct regexp_cache
*cp
, **cpp
;
217 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
220 /* Entries are initialized to nil, and may be set to nil by
221 compile_pattern_1 if the pattern isn't valid. Don't apply
222 string accessors in those cases. However, compile_pattern_1
223 is only applied to the cache entry we pick here to reuse. So
224 nil should never appear before a non-nil entry. */
225 if (NILP (cp
->regexp
))
227 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
228 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
229 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
230 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
231 && cp
->posix
== posix
232 && (EQ (cp
->syntax_table
, Qt
)
233 || EQ (cp
->syntax_table
, BVAR (current_buffer
, syntax_table
)))
234 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
))
235 && cp
->buf
.charset_unibyte
== charset_unibyte
)
238 /* If we're at the end of the cache, compile into the nil cell
239 we found, or the last (least recently used) cell with a
244 compile_pattern_1 (cp
, pattern
, translate
, posix
);
249 /* When we get here, cp (aka *cpp) contains the compiled pattern,
250 either because we found it in the cache or because we just compiled it.
251 Move it to the front of the queue to mark it as most recently used. */
253 cp
->next
= searchbuf_head
;
256 /* Advise the searching functions about the space we have allocated
257 for register data. */
259 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
261 /* The compiled pattern can be used both for multibyte and unibyte
262 target. But, we have to tell which the pattern is used for. */
263 cp
->buf
.target_multibyte
= multibyte
;
270 looking_at_1 (Lisp_Object string
, int posix
)
273 unsigned char *p1
, *p2
;
275 register ptrdiff_t i
;
276 struct re_pattern_buffer
*bufp
;
278 if (running_asynch_code
)
281 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
282 XCHAR_TABLE (BVAR (current_buffer
, case_canon_table
))->extras
[2]
283 = BVAR (current_buffer
, case_eqv_table
);
285 CHECK_STRING (string
);
286 bufp
= compile_pattern (string
,
287 (NILP (Vinhibit_changing_match_data
)
288 ? &search_regs
: NULL
),
289 (!NILP (BVAR (current_buffer
, case_fold_search
))
290 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
292 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
295 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
297 /* Get pointers and sizes of the two strings
298 that make up the visible portion of the buffer. */
301 s1
= GPT_BYTE
- BEGV_BYTE
;
303 s2
= ZV_BYTE
- GPT_BYTE
;
307 s2
= ZV_BYTE
- BEGV_BYTE
;
312 s1
= ZV_BYTE
- BEGV_BYTE
;
316 re_match_object
= Qnil
;
318 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
320 (NILP (Vinhibit_changing_match_data
)
321 ? &search_regs
: NULL
),
322 ZV_BYTE
- BEGV_BYTE
);
328 val
= (0 <= i
? Qt
: Qnil
);
329 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
330 for (i
= 0; i
< search_regs
.num_regs
; i
++)
331 if (search_regs
.start
[i
] >= 0)
334 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
336 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
339 /* Set last_thing_searched only when match data is changed. */
340 if (NILP (Vinhibit_changing_match_data
))
341 XSETBUFFER (last_thing_searched
, current_buffer
);
346 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
347 doc
: /* Return t if text after point matches regular expression REGEXP.
348 This function modifies the match data that `match-beginning',
349 `match-end' and `match-data' access; save and restore the match
350 data if you want to preserve them. */)
353 return looking_at_1 (regexp
, 0);
356 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
357 doc
: /* Return t if text after point matches regular expression REGEXP.
358 Find the longest match, in accord with Posix regular expression rules.
359 This function modifies the match data that `match-beginning',
360 `match-end' and `match-data' access; save and restore the match
361 data if you want to preserve them. */)
364 return looking_at_1 (regexp
, 1);
368 string_match_1 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
, int posix
)
371 struct re_pattern_buffer
*bufp
;
373 ptrdiff_t pos_byte
, i
;
375 if (running_asynch_code
)
378 CHECK_STRING (regexp
);
379 CHECK_STRING (string
);
382 pos
= 0, pos_byte
= 0;
385 ptrdiff_t len
= SCHARS (string
);
387 CHECK_NUMBER (start
);
389 if (pos
< 0 && -pos
<= len
)
391 else if (0 > pos
|| pos
> len
)
392 args_out_of_range (string
, start
);
393 pos_byte
= string_char_to_byte (string
, pos
);
396 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
397 XCHAR_TABLE (BVAR (current_buffer
, case_canon_table
))->extras
[2]
398 = BVAR (current_buffer
, case_eqv_table
);
400 bufp
= compile_pattern (regexp
,
401 (NILP (Vinhibit_changing_match_data
)
402 ? &search_regs
: NULL
),
403 (!NILP (BVAR (current_buffer
, case_fold_search
))
404 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
406 STRING_MULTIBYTE (string
));
408 re_match_object
= string
;
410 val
= re_search (bufp
, SSDATA (string
),
411 SBYTES (string
), pos_byte
,
412 SBYTES (string
) - pos_byte
,
413 (NILP (Vinhibit_changing_match_data
)
414 ? &search_regs
: NULL
));
417 /* Set last_thing_searched only when match data is changed. */
418 if (NILP (Vinhibit_changing_match_data
))
419 last_thing_searched
= Qt
;
423 if (val
< 0) return Qnil
;
425 if (NILP (Vinhibit_changing_match_data
))
426 for (i
= 0; i
< search_regs
.num_regs
; i
++)
427 if (search_regs
.start
[i
] >= 0)
430 = string_byte_to_char (string
, search_regs
.start
[i
]);
432 = string_byte_to_char (string
, search_regs
.end
[i
]);
435 return make_number (string_byte_to_char (string
, val
));
438 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
439 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
440 Matching ignores case if `case-fold-search' is non-nil.
441 If third arg START is non-nil, start search at that index in STRING.
442 For index of first char beyond the match, do (match-end 0).
443 `match-end' and `match-beginning' also give indices of substrings
444 matched by parenthesis constructs in the pattern.
446 You can use the function `match-string' to extract the substrings
447 matched by the parenthesis constructions in REGEXP. */)
448 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
450 return string_match_1 (regexp
, string
, start
, 0);
453 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
454 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
455 Find the longest match, in accord with Posix regular expression rules.
456 Case is ignored if `case-fold-search' is non-nil in the current buffer.
457 If third arg START is non-nil, start search at that index in STRING.
458 For index of first char beyond the match, do (match-end 0).
459 `match-end' and `match-beginning' also give indices of substrings
460 matched by parenthesis constructs in the pattern. */)
461 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
463 return string_match_1 (regexp
, string
, start
, 1);
466 /* Match REGEXP against STRING, searching all of STRING,
467 and return the index of the match, or negative on failure.
468 This does not clobber the match data. */
471 fast_string_match (Lisp_Object regexp
, Lisp_Object string
)
474 struct re_pattern_buffer
*bufp
;
476 bufp
= compile_pattern (regexp
, 0, Qnil
,
477 0, STRING_MULTIBYTE (string
));
479 re_match_object
= string
;
481 val
= re_search (bufp
, SSDATA (string
),
488 /* Match REGEXP against STRING, searching all of STRING ignoring case,
489 and return the index of the match, or negative on failure.
490 This does not clobber the match data.
491 We assume that STRING contains single-byte characters. */
494 fast_c_string_match_ignore_case (Lisp_Object regexp
, const char *string
)
497 struct re_pattern_buffer
*bufp
;
498 size_t len
= strlen (string
);
500 regexp
= string_make_unibyte (regexp
);
501 re_match_object
= Qt
;
502 bufp
= compile_pattern (regexp
, 0,
503 Vascii_canon_table
, 0,
506 val
= re_search (bufp
, string
, len
, 0, len
, 0);
511 /* Like fast_string_match but ignore case. */
514 fast_string_match_ignore_case (Lisp_Object regexp
, Lisp_Object string
)
517 struct re_pattern_buffer
*bufp
;
519 bufp
= compile_pattern (regexp
, 0, Vascii_canon_table
,
520 0, STRING_MULTIBYTE (string
));
522 re_match_object
= string
;
524 val
= re_search (bufp
, SSDATA (string
),
531 /* Match REGEXP against the characters after POS to LIMIT, and return
532 the number of matched characters. If STRING is non-nil, match
533 against the characters in it. In that case, POS and LIMIT are
534 indices into the string. This function doesn't modify the match
538 fast_looking_at (Lisp_Object regexp
, ptrdiff_t pos
, ptrdiff_t pos_byte
, ptrdiff_t limit
, ptrdiff_t limit_byte
, Lisp_Object string
)
541 struct re_pattern_buffer
*buf
;
542 unsigned char *p1
, *p2
;
546 if (STRINGP (string
))
549 pos_byte
= string_char_to_byte (string
, pos
);
551 limit_byte
= string_char_to_byte (string
, limit
);
555 s2
= SBYTES (string
);
556 re_match_object
= string
;
557 multibyte
= STRING_MULTIBYTE (string
);
562 pos_byte
= CHAR_TO_BYTE (pos
);
564 limit_byte
= CHAR_TO_BYTE (limit
);
565 pos_byte
-= BEGV_BYTE
;
566 limit_byte
-= BEGV_BYTE
;
568 s1
= GPT_BYTE
- BEGV_BYTE
;
570 s2
= ZV_BYTE
- GPT_BYTE
;
574 s2
= ZV_BYTE
- BEGV_BYTE
;
579 s1
= ZV_BYTE
- BEGV_BYTE
;
582 re_match_object
= Qnil
;
583 multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
586 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
588 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
589 pos_byte
, NULL
, limit_byte
);
596 /* The newline cache: remembering which sections of text have no newlines. */
598 /* If the user has requested newline caching, make sure it's on.
599 Otherwise, make sure it's off.
600 This is our cheezy way of associating an action with the change of
601 state of a buffer-local variable. */
603 newline_cache_on_off (struct buffer
*buf
)
605 if (NILP (BVAR (buf
, cache_long_line_scans
)))
607 /* It should be off. */
608 if (buf
->newline_cache
)
610 free_region_cache (buf
->newline_cache
);
611 buf
->newline_cache
= 0;
616 /* It should be on. */
617 if (buf
->newline_cache
== 0)
618 buf
->newline_cache
= new_region_cache ();
623 /* Search for COUNT instances of the character TARGET between START and END.
625 If COUNT is positive, search forwards; END must be >= START.
626 If COUNT is negative, search backwards for the -COUNTth instance;
627 END must be <= START.
628 If COUNT is zero, do anything you please; run rogue, for all I care.
630 If END is zero, use BEGV or ZV instead, as appropriate for the
631 direction indicated by COUNT.
633 If we find COUNT instances, set *SHORTAGE to zero, and return the
634 position past the COUNTth match. Note that for reverse motion
635 this is not the same as the usual convention for Emacs motion commands.
637 If we don't find COUNT instances before reaching END, set *SHORTAGE
638 to the number of TARGETs left unfound, and return END.
640 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
641 except when inside redisplay. */
644 scan_buffer (register int target
, ptrdiff_t start
, ptrdiff_t end
,
645 ptrdiff_t count
, ptrdiff_t *shortage
, int allow_quit
)
647 struct region_cache
*newline_cache
;
658 if (! end
) end
= BEGV
;
661 newline_cache_on_off (current_buffer
);
662 newline_cache
= current_buffer
->newline_cache
;
667 immediate_quit
= allow_quit
;
672 /* Our innermost scanning loop is very simple; it doesn't know
673 about gaps, buffer ends, or the newline cache. ceiling is
674 the position of the last character before the next such
675 obstacle --- the last character the dumb search loop should
677 ptrdiff_t ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
678 ptrdiff_t start_byte
= CHAR_TO_BYTE (start
);
681 /* If we're looking for a newline, consult the newline cache
682 to see where we can avoid some scanning. */
683 if (target
== '\n' && newline_cache
)
685 ptrdiff_t next_change
;
687 while (region_cache_forward
688 (current_buffer
, newline_cache
, start_byte
, &next_change
))
689 start_byte
= next_change
;
690 immediate_quit
= allow_quit
;
692 /* START should never be after END. */
693 if (start_byte
> ceiling_byte
)
694 start_byte
= ceiling_byte
;
696 /* Now the text after start is an unknown region, and
697 next_change is the position of the next known region. */
698 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
701 /* The dumb loop can only scan text stored in contiguous
702 bytes. BUFFER_CEILING_OF returns the last character
703 position that is contiguous, so the ceiling is the
704 position after that. */
705 tem
= BUFFER_CEILING_OF (start_byte
);
706 ceiling_byte
= min (tem
, ceiling_byte
);
709 /* The termination address of the dumb loop. */
710 register unsigned char *ceiling_addr
711 = BYTE_POS_ADDR (ceiling_byte
) + 1;
712 register unsigned char *cursor
713 = BYTE_POS_ADDR (start_byte
);
714 unsigned char *base
= cursor
;
716 while (cursor
< ceiling_addr
)
718 unsigned char *scan_start
= cursor
;
721 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
724 /* If we're looking for newlines, cache the fact that
725 the region from start to cursor is free of them. */
726 if (target
== '\n' && newline_cache
)
727 know_region_cache (current_buffer
, newline_cache
,
728 BYTE_TO_CHAR (start_byte
+ scan_start
- base
),
729 BYTE_TO_CHAR (start_byte
+ cursor
- base
));
731 /* Did we find the target character? */
732 if (cursor
< ceiling_addr
)
737 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
743 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
749 /* The last character to check before the next obstacle. */
750 ptrdiff_t ceiling_byte
= CHAR_TO_BYTE (end
);
751 ptrdiff_t start_byte
= CHAR_TO_BYTE (start
);
754 /* Consult the newline cache, if appropriate. */
755 if (target
== '\n' && newline_cache
)
757 ptrdiff_t next_change
;
759 while (region_cache_backward
760 (current_buffer
, newline_cache
, start_byte
, &next_change
))
761 start_byte
= next_change
;
762 immediate_quit
= allow_quit
;
764 /* Start should never be at or before end. */
765 if (start_byte
<= ceiling_byte
)
766 start_byte
= ceiling_byte
+ 1;
768 /* Now the text before start is an unknown region, and
769 next_change is the position of the next known region. */
770 ceiling_byte
= max (next_change
, ceiling_byte
);
773 /* Stop scanning before the gap. */
774 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
775 ceiling_byte
= max (tem
, ceiling_byte
);
778 /* The termination address of the dumb loop. */
779 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
780 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
781 unsigned char *base
= cursor
;
783 while (cursor
>= ceiling_addr
)
785 unsigned char *scan_start
= cursor
;
787 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
790 /* If we're looking for newlines, cache the fact that
791 the region from after the cursor to start is free of them. */
792 if (target
== '\n' && newline_cache
)
793 know_region_cache (current_buffer
, newline_cache
,
794 BYTE_TO_CHAR (start_byte
+ cursor
- base
),
795 BYTE_TO_CHAR (start_byte
+ scan_start
- base
));
797 /* Did we find the target character? */
798 if (cursor
>= ceiling_addr
)
803 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
809 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
815 *shortage
= count
* direction
;
819 /* Search for COUNT instances of a line boundary, which means either a
820 newline or (if selective display enabled) a carriage return.
821 Start at START. If COUNT is negative, search backwards.
823 We report the resulting position by calling TEMP_SET_PT_BOTH.
825 If we find COUNT instances. we position after (always after,
826 even if scanning backwards) the COUNTth match, and return 0.
828 If we don't find COUNT instances before reaching the end of the
829 buffer (or the beginning, if scanning backwards), we return
830 the number of line boundaries left unfound, and position at
831 the limit we bumped up against.
833 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
834 except in special cases. */
837 scan_newline (ptrdiff_t start
, ptrdiff_t start_byte
,
838 ptrdiff_t limit
, ptrdiff_t limit_byte
,
839 register EMACS_INT count
, int allow_quit
)
841 int direction
= ((count
> 0) ? 1 : -1);
843 register unsigned char *cursor
;
847 register unsigned char *ceiling_addr
;
849 int old_immediate_quit
= immediate_quit
;
851 /* The code that follows is like scan_buffer
852 but checks for either newline or carriage return. */
857 start_byte
= CHAR_TO_BYTE (start
);
861 while (start_byte
< limit_byte
)
863 ceiling
= BUFFER_CEILING_OF (start_byte
);
864 ceiling
= min (limit_byte
- 1, ceiling
);
865 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
866 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
869 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
872 if (cursor
!= ceiling_addr
)
876 immediate_quit
= old_immediate_quit
;
877 start_byte
= start_byte
+ cursor
- base
+ 1;
878 start
= BYTE_TO_CHAR (start_byte
);
879 TEMP_SET_PT_BOTH (start
, start_byte
);
883 if (++cursor
== ceiling_addr
)
889 start_byte
+= cursor
- base
;
894 while (start_byte
> limit_byte
)
896 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
897 ceiling
= max (limit_byte
, ceiling
);
898 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
899 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
902 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
905 if (cursor
!= ceiling_addr
)
909 immediate_quit
= old_immediate_quit
;
910 /* Return the position AFTER the match we found. */
911 start_byte
= start_byte
+ cursor
- base
+ 1;
912 start
= BYTE_TO_CHAR (start_byte
);
913 TEMP_SET_PT_BOTH (start
, start_byte
);
920 /* Here we add 1 to compensate for the last decrement
921 of CURSOR, which took it past the valid range. */
922 start_byte
+= cursor
- base
+ 1;
926 TEMP_SET_PT_BOTH (limit
, limit_byte
);
927 immediate_quit
= old_immediate_quit
;
929 return count
* direction
;
933 find_next_newline_no_quit (ptrdiff_t from
, ptrdiff_t cnt
)
935 return scan_buffer ('\n', from
, 0, cnt
, (ptrdiff_t *) 0, 0);
938 /* Like find_next_newline, but returns position before the newline,
939 not after, and only search up to TO. This isn't just
940 find_next_newline (...)-1, because you might hit TO. */
943 find_before_next_newline (ptrdiff_t from
, ptrdiff_t to
, ptrdiff_t cnt
)
946 ptrdiff_t pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
954 /* Subroutines of Lisp buffer search functions. */
957 search_command (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
,
958 Lisp_Object count
, int direction
, int RE
, int posix
)
960 register EMACS_INT np
;
963 EMACS_INT n
= direction
;
967 CHECK_NUMBER (count
);
971 CHECK_STRING (string
);
975 lim
= ZV
, lim_byte
= ZV_BYTE
;
977 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
981 CHECK_NUMBER_COERCE_MARKER (bound
);
983 if (n
> 0 ? lim
< PT
: lim
> PT
)
984 error ("Invalid search bound (wrong side of point)");
986 lim
= ZV
, lim_byte
= ZV_BYTE
;
988 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
990 lim_byte
= CHAR_TO_BYTE (lim
);
993 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
994 XCHAR_TABLE (BVAR (current_buffer
, case_canon_table
))->extras
[2]
995 = BVAR (current_buffer
, case_eqv_table
);
997 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
998 (!NILP (BVAR (current_buffer
, case_fold_search
))
999 ? BVAR (current_buffer
, case_canon_table
)
1001 (!NILP (BVAR (current_buffer
, case_fold_search
))
1002 ? BVAR (current_buffer
, case_eqv_table
)
1008 xsignal1 (Qsearch_failed
, string
);
1010 if (!EQ (noerror
, Qt
))
1012 if (lim
< BEGV
|| lim
> ZV
)
1014 SET_PT_BOTH (lim
, lim_byte
);
1016 #if 0 /* This would be clean, but maybe programs depend on
1017 a value of nil here. */
1025 if (np
< BEGV
|| np
> ZV
)
1030 return make_number (np
);
1033 /* Return 1 if REGEXP it matches just one constant string. */
1036 trivial_regexp_p (Lisp_Object regexp
)
1038 ptrdiff_t len
= SBYTES (regexp
);
1039 unsigned char *s
= SDATA (regexp
);
1044 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1051 case '|': case '(': case ')': case '`': case '\'': case 'b':
1052 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1053 case 'S': case '=': case '{': case '}': case '_':
1054 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1055 case '1': case '2': case '3': case '4': case '5':
1056 case '6': case '7': case '8': case '9':
1064 /* Search for the n'th occurrence of STRING in the current buffer,
1065 starting at position POS and stopping at position LIM,
1066 treating STRING as a literal string if RE is false or as
1067 a regular expression if RE is true.
1069 If N is positive, searching is forward and LIM must be greater than POS.
1070 If N is negative, searching is backward and LIM must be less than POS.
1072 Returns -x if x occurrences remain to be found (x > 0),
1073 or else the position at the beginning of the Nth occurrence
1074 (if searching backward) or the end (if searching forward).
1076 POSIX is nonzero if we want full backtracking (POSIX style)
1077 for this pattern. 0 means backtrack only enough to get a valid match. */
1079 #define TRANSLATE(out, trt, d) \
1085 temp = Faref (trt, make_number (d)); \
1086 if (INTEGERP (temp)) \
1087 out = XINT (temp); \
1096 /* Only used in search_buffer, to record the end position of the match
1097 when searching regexps and SEARCH_REGS should not be changed
1098 (i.e. Vinhibit_changing_match_data is non-nil). */
1099 static struct re_registers search_regs_1
;
1102 search_buffer (Lisp_Object string
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
1103 ptrdiff_t lim
, ptrdiff_t lim_byte
, EMACS_INT n
,
1104 int RE
, Lisp_Object trt
, Lisp_Object inverse_trt
, int posix
)
1106 ptrdiff_t len
= SCHARS (string
);
1107 ptrdiff_t len_byte
= SBYTES (string
);
1108 register ptrdiff_t i
;
1110 if (running_asynch_code
)
1111 save_search_regs ();
1113 /* Searching 0 times means don't move. */
1114 /* Null string is found at starting position. */
1115 if (len
== 0 || n
== 0)
1117 set_search_regs (pos_byte
, 0);
1121 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1123 unsigned char *p1
, *p2
;
1125 struct re_pattern_buffer
*bufp
;
1127 bufp
= compile_pattern (string
,
1128 (NILP (Vinhibit_changing_match_data
)
1129 ? &search_regs
: &search_regs_1
),
1131 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
1133 immediate_quit
= 1; /* Quit immediately if user types ^G,
1134 because letting this function finish
1135 can take too long. */
1136 QUIT
; /* Do a pending quit right away,
1137 to avoid paradoxical behavior */
1138 /* Get pointers and sizes of the two strings
1139 that make up the visible portion of the buffer. */
1142 s1
= GPT_BYTE
- BEGV_BYTE
;
1144 s2
= ZV_BYTE
- GPT_BYTE
;
1148 s2
= ZV_BYTE
- BEGV_BYTE
;
1153 s1
= ZV_BYTE
- BEGV_BYTE
;
1156 re_match_object
= Qnil
;
1162 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1163 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1164 (NILP (Vinhibit_changing_match_data
)
1165 ? &search_regs
: &search_regs_1
),
1166 /* Don't allow match past current point */
1167 pos_byte
- BEGV_BYTE
);
1170 matcher_overflow ();
1174 if (NILP (Vinhibit_changing_match_data
))
1176 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1177 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1178 if (search_regs
.start
[i
] >= 0)
1180 search_regs
.start
[i
]
1181 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1183 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1185 XSETBUFFER (last_thing_searched
, current_buffer
);
1186 /* Set pos to the new position. */
1187 pos
= search_regs
.start
[0];
1191 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1192 /* Set pos to the new position. */
1193 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1207 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1208 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1209 (NILP (Vinhibit_changing_match_data
)
1210 ? &search_regs
: &search_regs_1
),
1211 lim_byte
- BEGV_BYTE
);
1214 matcher_overflow ();
1218 if (NILP (Vinhibit_changing_match_data
))
1220 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1221 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1222 if (search_regs
.start
[i
] >= 0)
1224 search_regs
.start
[i
]
1225 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1227 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1229 XSETBUFFER (last_thing_searched
, current_buffer
);
1230 pos
= search_regs
.end
[0];
1234 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1235 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1248 else /* non-RE case */
1250 unsigned char *raw_pattern
, *pat
;
1251 ptrdiff_t raw_pattern_size
;
1252 ptrdiff_t raw_pattern_size_byte
;
1253 unsigned char *patbuf
;
1254 int multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1255 unsigned char *base_pat
;
1256 /* Set to positive if we find a non-ASCII char that need
1257 translation. Otherwise set to zero later. */
1259 int boyer_moore_ok
= 1;
1261 /* MULTIBYTE says whether the text to be searched is multibyte.
1262 We must convert PATTERN to match that, or we will not really
1263 find things right. */
1265 if (multibyte
== STRING_MULTIBYTE (string
))
1267 raw_pattern
= SDATA (string
);
1268 raw_pattern_size
= SCHARS (string
);
1269 raw_pattern_size_byte
= SBYTES (string
);
1273 raw_pattern_size
= SCHARS (string
);
1274 raw_pattern_size_byte
1275 = count_size_as_multibyte (SDATA (string
),
1277 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1278 copy_text (SDATA (string
), raw_pattern
,
1279 SCHARS (string
), 0, 1);
1283 /* Converting multibyte to single-byte.
1285 ??? Perhaps this conversion should be done in a special way
1286 by subtracting nonascii-insert-offset from each non-ASCII char,
1287 so that only the multibyte chars which really correspond to
1288 the chosen single-byte character set can possibly match. */
1289 raw_pattern_size
= SCHARS (string
);
1290 raw_pattern_size_byte
= SCHARS (string
);
1291 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1292 copy_text (SDATA (string
), raw_pattern
,
1293 SBYTES (string
), 1, 0);
1296 /* Copy and optionally translate the pattern. */
1297 len
= raw_pattern_size
;
1298 len_byte
= raw_pattern_size_byte
;
1299 patbuf
= (unsigned char *) alloca (len
* MAX_MULTIBYTE_LENGTH
);
1301 base_pat
= raw_pattern
;
1304 /* Fill patbuf by translated characters in STRING while
1305 checking if we can use boyer-moore search. If TRT is
1306 non-nil, we can use boyer-moore search only if TRT can be
1307 represented by the byte array of 256 elements. For that,
1308 all non-ASCII case-equivalents of all case-sensitive
1309 characters in STRING must belong to the same charset and
1314 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1315 int c
, translated
, inverse
;
1316 int in_charlen
, charlen
;
1318 /* If we got here and the RE flag is set, it's because we're
1319 dealing with a regexp known to be trivial, so the backslash
1320 just quotes the next character. */
1321 if (RE
&& *base_pat
== '\\')
1329 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1334 charlen
= in_charlen
;
1338 /* Translate the character. */
1339 TRANSLATE (translated
, trt
, c
);
1340 charlen
= CHAR_STRING (translated
, str_base
);
1343 /* Check if C has any other case-equivalents. */
1344 TRANSLATE (inverse
, inverse_trt
, c
);
1345 /* If so, check if we can use boyer-moore. */
1346 if (c
!= inverse
&& boyer_moore_ok
)
1348 /* Check if all equivalents belong to the same
1349 group of characters. Note that the check of C
1350 itself is done by the last iteration. */
1351 int this_char_base
= -1;
1353 while (boyer_moore_ok
)
1355 if (ASCII_BYTE_P (inverse
))
1357 if (this_char_base
> 0)
1362 else if (CHAR_BYTE8_P (inverse
))
1363 /* Boyer-moore search can't handle a
1364 translation of an eight-bit
1367 else if (this_char_base
< 0)
1369 this_char_base
= inverse
& ~0x3F;
1371 char_base
= this_char_base
;
1372 else if (this_char_base
!= char_base
)
1375 else if ((inverse
& ~0x3F) != this_char_base
)
1379 TRANSLATE (inverse
, inverse_trt
, inverse
);
1384 /* Store this character into the translated pattern. */
1385 memcpy (pat
, str
, charlen
);
1387 base_pat
+= in_charlen
;
1388 len_byte
-= in_charlen
;
1391 /* If char_base is still negative we didn't find any translated
1392 non-ASCII characters. */
1398 /* Unibyte buffer. */
1404 /* If we got here and the RE flag is set, it's because we're
1405 dealing with a regexp known to be trivial, so the backslash
1406 just quotes the next character. */
1407 if (RE
&& *base_pat
== '\\')
1414 TRANSLATE (translated
, trt
, c
);
1415 *pat
++ = translated
;
1419 len_byte
= pat
- patbuf
;
1420 pat
= base_pat
= patbuf
;
1423 return boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1427 return simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1428 pos
, pos_byte
, lim
, lim_byte
);
1432 /* Do a simple string search N times for the string PAT,
1433 whose length is LEN/LEN_BYTE,
1434 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1435 TRT is the translation table.
1437 Return the character position where the match is found.
1438 Otherwise, if M matches remained to be found, return -M.
1440 This kind of search works regardless of what is in PAT and
1441 regardless of what is in TRT. It is used in cases where
1442 boyer_moore cannot work. */
1445 simple_search (EMACS_INT n
, unsigned char *pat
,
1446 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1447 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1448 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1450 int multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1451 int forward
= n
> 0;
1452 /* Number of buffer bytes matched. Note that this may be different
1453 from len_byte in a multibyte buffer. */
1454 ptrdiff_t match_byte
;
1456 if (lim
> pos
&& multibyte
)
1461 /* Try matching at position POS. */
1462 ptrdiff_t this_pos
= pos
;
1463 ptrdiff_t this_pos_byte
= pos_byte
;
1464 ptrdiff_t this_len
= len
;
1465 unsigned char *p
= pat
;
1466 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1469 while (this_len
> 0)
1471 int charlen
, buf_charlen
;
1474 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1475 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1477 TRANSLATE (buf_ch
, trt
, buf_ch
);
1479 if (buf_ch
!= pat_ch
)
1485 this_pos_byte
+= buf_charlen
;
1491 match_byte
= this_pos_byte
- pos_byte
;
1493 pos_byte
+= match_byte
;
1497 INC_BOTH (pos
, pos_byte
);
1507 /* Try matching at position POS. */
1508 ptrdiff_t this_pos
= pos
;
1509 ptrdiff_t this_len
= len
;
1510 unsigned char *p
= pat
;
1512 if (pos
+ len
> lim
)
1515 while (this_len
> 0)
1518 int buf_ch
= FETCH_BYTE (this_pos
);
1519 TRANSLATE (buf_ch
, trt
, buf_ch
);
1521 if (buf_ch
!= pat_ch
)
1540 /* Backwards search. */
1541 else if (lim
< pos
&& multibyte
)
1546 /* Try matching at position POS. */
1547 ptrdiff_t this_pos
= pos
;
1548 ptrdiff_t this_pos_byte
= pos_byte
;
1549 ptrdiff_t this_len
= len
;
1550 const unsigned char *p
= pat
+ len_byte
;
1552 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1555 while (this_len
> 0)
1559 DEC_BOTH (this_pos
, this_pos_byte
);
1560 PREV_CHAR_BOUNDARY (p
, pat
);
1561 pat_ch
= STRING_CHAR (p
);
1562 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1563 TRANSLATE (buf_ch
, trt
, buf_ch
);
1565 if (buf_ch
!= pat_ch
)
1573 match_byte
= pos_byte
- this_pos_byte
;
1575 pos_byte
= this_pos_byte
;
1579 DEC_BOTH (pos
, pos_byte
);
1589 /* Try matching at position POS. */
1590 ptrdiff_t this_pos
= pos
- len
;
1591 ptrdiff_t this_len
= len
;
1592 unsigned char *p
= pat
;
1597 while (this_len
> 0)
1600 int buf_ch
= FETCH_BYTE (this_pos
);
1601 TRANSLATE (buf_ch
, trt
, buf_ch
);
1603 if (buf_ch
!= pat_ch
)
1626 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1628 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1638 /* Do Boyer-Moore search N times for the string BASE_PAT,
1639 whose length is LEN_BYTE,
1640 from buffer position POS_BYTE until LIM_BYTE.
1641 DIRECTION says which direction we search in.
1642 TRT and INVERSE_TRT are translation tables.
1643 Characters in PAT are already translated by TRT.
1645 This kind of search works if all the characters in BASE_PAT that
1646 have nontrivial translation are the same aside from the last byte.
1647 This makes it possible to translate just the last byte of a
1648 character, and do so after just a simple test of the context.
1649 CHAR_BASE is nonzero if there is such a non-ASCII character.
1651 If that criterion is not satisfied, do not call this function. */
1654 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1656 Lisp_Object trt
, Lisp_Object inverse_trt
,
1657 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1660 int direction
= ((n
> 0) ? 1 : -1);
1661 register ptrdiff_t dirlen
;
1663 int stride_for_teases
= 0;
1665 register unsigned char *cursor
, *p_limit
;
1666 register ptrdiff_t i
;
1668 unsigned char *pat
, *pat_end
;
1669 int multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1671 unsigned char simple_translate
[0400];
1672 /* These are set to the preceding bytes of a byte to be translated
1673 if char_base is nonzero. As the maximum byte length of a
1674 multibyte character is 5, we have to check at most four previous
1676 int translate_prev_byte1
= 0;
1677 int translate_prev_byte2
= 0;
1678 int translate_prev_byte3
= 0;
1680 /* The general approach is that we are going to maintain that we know
1681 the first (closest to the present position, in whatever direction
1682 we're searching) character that could possibly be the last
1683 (furthest from present position) character of a valid match. We
1684 advance the state of our knowledge by looking at that character
1685 and seeing whether it indeed matches the last character of the
1686 pattern. If it does, we take a closer look. If it does not, we
1687 move our pointer (to putative last characters) as far as is
1688 logically possible. This amount of movement, which I call a
1689 stride, will be the length of the pattern if the actual character
1690 appears nowhere in the pattern, otherwise it will be the distance
1691 from the last occurrence of that character to the end of the
1692 pattern. If the amount is zero we have a possible match. */
1694 /* Here we make a "mickey mouse" BM table. The stride of the search
1695 is determined only by the last character of the putative match.
1696 If that character does not match, we will stride the proper
1697 distance to propose a match that superimposes it on the last
1698 instance of a character that matches it (per trt), or misses
1699 it entirely if there is none. */
1701 dirlen
= len_byte
* direction
;
1703 /* Record position after the end of the pattern. */
1704 pat_end
= base_pat
+ len_byte
;
1705 /* BASE_PAT points to a character that we start scanning from.
1706 It is the first character in a forward search,
1707 the last character in a backward search. */
1709 base_pat
= pat_end
- 1;
1711 /* A character that does not appear in the pattern induces a
1712 stride equal to the pattern length. */
1713 for (i
= 0; i
< 0400; i
++)
1716 /* We use this for translation, instead of TRT itself.
1717 We fill this in to handle the characters that actually
1718 occur in the pattern. Others don't matter anyway! */
1719 for (i
= 0; i
< 0400; i
++)
1720 simple_translate
[i
] = i
;
1724 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1725 byte following them are the target of translation. */
1726 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1727 int cblen
= CHAR_STRING (char_base
, str
);
1729 translate_prev_byte1
= str
[cblen
- 2];
1732 translate_prev_byte2
= str
[cblen
- 3];
1734 translate_prev_byte3
= str
[cblen
- 4];
1741 unsigned char *ptr
= base_pat
+ i
;
1745 /* If the byte currently looking at is the last of a
1746 character to check case-equivalents, set CH to that
1747 character. An ASCII character and a non-ASCII character
1748 matching with CHAR_BASE are to be checked. */
1751 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1754 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1756 unsigned char *charstart
= ptr
- 1;
1758 while (! (CHAR_HEAD_P (*charstart
)))
1760 ch
= STRING_CHAR (charstart
);
1761 if (char_base
!= (ch
& ~0x3F))
1765 if (ch
>= 0200 && multibyte
)
1766 j
= (ch
& 0x3F) | 0200;
1771 stride_for_teases
= BM_tab
[j
];
1773 BM_tab
[j
] = dirlen
- i
;
1774 /* A translation table is accompanied by its inverse -- see
1775 comment following downcase_table for details. */
1778 int starting_ch
= ch
;
1783 TRANSLATE (ch
, inverse_trt
, ch
);
1784 if (ch
>= 0200 && multibyte
)
1785 j
= (ch
& 0x3F) | 0200;
1789 /* For all the characters that map into CH,
1790 set up simple_translate to map the last byte
1792 simple_translate
[j
] = starting_j
;
1793 if (ch
== starting_ch
)
1795 BM_tab
[j
] = dirlen
- i
;
1804 stride_for_teases
= BM_tab
[j
];
1805 BM_tab
[j
] = dirlen
- i
;
1807 /* stride_for_teases tells how much to stride if we get a
1808 match on the far character but are subsequently
1809 disappointed, by recording what the stride would have been
1810 for that character if the last character had been
1813 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1814 /* loop invariant - POS_BYTE points at where last char (first
1815 char if reverse) of pattern would align in a possible match. */
1819 unsigned char *tail_end_ptr
;
1821 /* It's been reported that some (broken) compiler thinks that
1822 Boolean expressions in an arithmetic context are unsigned.
1823 Using an explicit ?1:0 prevents this. */
1824 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1826 return (n
* (0 - direction
));
1827 /* First we do the part we can by pointers (maybe nothing) */
1830 limit
= pos_byte
- dirlen
+ direction
;
1833 limit
= BUFFER_CEILING_OF (limit
);
1834 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1835 can take on without hitting edge of buffer or the gap. */
1836 limit
= min (limit
, pos_byte
+ 20000);
1837 limit
= min (limit
, lim_byte
- 1);
1841 limit
= BUFFER_FLOOR_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
= max (limit
, pos_byte
- 20000);
1845 limit
= max (limit
, lim_byte
);
1847 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1848 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1850 if ((limit
- pos_byte
) * direction
> 20)
1854 p_limit
= BYTE_POS_ADDR (limit
);
1855 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1856 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1857 while (1) /* use one cursor setting as long as i can */
1859 if (direction
> 0) /* worth duplicating */
1861 while (cursor
<= p_limit
)
1863 if (BM_tab
[*cursor
] == 0)
1865 cursor
+= BM_tab
[*cursor
];
1870 while (cursor
>= p_limit
)
1872 if (BM_tab
[*cursor
] == 0)
1874 cursor
+= BM_tab
[*cursor
];
1877 /* If you are here, cursor is beyond the end of the
1878 searched region. You fail to match within the
1879 permitted region and would otherwise try a character
1880 beyond that region. */
1884 i
= dirlen
- direction
;
1887 while ((i
-= direction
) + direction
!= 0)
1890 cursor
-= direction
;
1891 /* Translate only the last byte of a character. */
1893 || ((cursor
== tail_end_ptr
1894 || CHAR_HEAD_P (cursor
[1]))
1895 && (CHAR_HEAD_P (cursor
[0])
1896 /* Check if this is the last byte of
1897 a translatable character. */
1898 || (translate_prev_byte1
== cursor
[-1]
1899 && (CHAR_HEAD_P (translate_prev_byte1
)
1900 || (translate_prev_byte2
== cursor
[-2]
1901 && (CHAR_HEAD_P (translate_prev_byte2
)
1902 || (translate_prev_byte3
== cursor
[-3]))))))))
1903 ch
= simple_translate
[*cursor
];
1912 while ((i
-= direction
) + direction
!= 0)
1914 cursor
-= direction
;
1915 if (pat
[i
] != *cursor
)
1919 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1920 if (i
+ direction
== 0)
1922 ptrdiff_t position
, start
, end
;
1924 cursor
-= direction
;
1926 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1927 ? 1 - len_byte
: 0);
1928 set_search_regs (position
, len_byte
);
1930 if (NILP (Vinhibit_changing_match_data
))
1932 start
= search_regs
.start
[0];
1933 end
= search_regs
.end
[0];
1936 /* If Vinhibit_changing_match_data is non-nil,
1937 search_regs will not be changed. So let's
1938 compute start and end here. */
1940 start
= BYTE_TO_CHAR (position
);
1941 end
= BYTE_TO_CHAR (position
+ len_byte
);
1944 if ((n
-= direction
) != 0)
1945 cursor
+= dirlen
; /* to resume search */
1947 return direction
> 0 ? end
: start
;
1950 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1952 pos_byte
+= cursor
- p2
;
1955 /* Now we'll pick up a clump that has to be done the hard
1956 way because it covers a discontinuity. */
1958 limit
= ((direction
> 0)
1959 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1960 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1961 limit
= ((direction
> 0)
1962 ? min (limit
+ len_byte
, lim_byte
- 1)
1963 : max (limit
- len_byte
, lim_byte
));
1964 /* LIMIT is now the last value POS_BYTE can have
1965 and still be valid for a possible match. */
1968 /* This loop can be coded for space rather than
1969 speed because it will usually run only once.
1970 (the reach is at most len + 21, and typically
1971 does not exceed len). */
1972 while ((limit
- pos_byte
) * direction
>= 0)
1974 int ch
= FETCH_BYTE (pos_byte
);
1975 if (BM_tab
[ch
] == 0)
1977 pos_byte
+= BM_tab
[ch
];
1979 break; /* ran off the end */
1982 /* Found what might be a match. */
1983 i
= dirlen
- direction
;
1984 while ((i
-= direction
) + direction
!= 0)
1988 pos_byte
-= direction
;
1989 ptr
= BYTE_POS_ADDR (pos_byte
);
1990 /* Translate only the last byte of a character. */
1992 || ((ptr
== tail_end_ptr
1993 || CHAR_HEAD_P (ptr
[1]))
1994 && (CHAR_HEAD_P (ptr
[0])
1995 /* Check if this is the last byte of a
1996 translatable character. */
1997 || (translate_prev_byte1
== ptr
[-1]
1998 && (CHAR_HEAD_P (translate_prev_byte1
)
1999 || (translate_prev_byte2
== ptr
[-2]
2000 && (CHAR_HEAD_P (translate_prev_byte2
)
2001 || translate_prev_byte3
== ptr
[-3])))))))
2002 ch
= simple_translate
[*ptr
];
2008 /* Above loop has moved POS_BYTE part or all the way
2009 back to the first pos (last pos if reverse).
2010 Set it once again at the last (first if reverse) char. */
2011 pos_byte
+= dirlen
- i
- direction
;
2012 if (i
+ direction
== 0)
2014 ptrdiff_t position
, start
, end
;
2015 pos_byte
-= direction
;
2017 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2018 set_search_regs (position
, len_byte
);
2020 if (NILP (Vinhibit_changing_match_data
))
2022 start
= search_regs
.start
[0];
2023 end
= search_regs
.end
[0];
2026 /* If Vinhibit_changing_match_data is non-nil,
2027 search_regs will not be changed. So let's
2028 compute start and end here. */
2030 start
= BYTE_TO_CHAR (position
);
2031 end
= BYTE_TO_CHAR (position
+ len_byte
);
2034 if ((n
-= direction
) != 0)
2035 pos_byte
+= dirlen
; /* to resume search */
2037 return direction
> 0 ? end
: start
;
2040 pos_byte
+= stride_for_teases
;
2043 /* We have done one clump. Can we continue? */
2044 if ((lim_byte
- pos_byte
) * direction
< 0)
2045 return ((0 - n
) * direction
);
2047 return BYTE_TO_CHAR (pos_byte
);
2050 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2051 for the overall match just found in the current buffer.
2052 Also clear out the match data for registers 1 and up. */
2055 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2059 if (!NILP (Vinhibit_changing_match_data
))
2062 /* Make sure we have registers in which to store
2063 the match position. */
2064 if (search_regs
.num_regs
== 0)
2066 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2067 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2068 search_regs
.num_regs
= 2;
2071 /* Clear out the other registers. */
2072 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2074 search_regs
.start
[i
] = -1;
2075 search_regs
.end
[i
] = -1;
2078 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2079 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2080 XSETBUFFER (last_thing_searched
, current_buffer
);
2083 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2084 "MSearch backward: ",
2085 doc
: /* Search backward from point for STRING.
2086 Set point to the beginning of the occurrence found, and return point.
2087 An optional second argument bounds the search; it is a buffer position.
2088 The match found must not extend before that position.
2089 Optional third argument, if t, means if fail just return nil (no error).
2090 If not nil and not t, position at limit of search and return nil.
2091 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2092 successive occurrences. If COUNT is negative, search forward,
2093 instead of backward, for -COUNT occurrences.
2095 Search case-sensitivity is determined by the value of the variable
2096 `case-fold-search', which see.
2098 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2099 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2101 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2104 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2105 doc
: /* Search forward from point for STRING.
2106 Set point to the end of the occurrence found, and return point.
2107 An optional second argument bounds the search; it is a buffer position.
2108 The match found must not extend after that position. A value of nil is
2109 equivalent to (point-max).
2110 Optional third argument, if t, means if fail just return nil (no error).
2111 If not nil and not t, move to limit of search and return nil.
2112 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2113 successive occurrences. If COUNT is negative, search backward,
2114 instead of forward, for -COUNT occurrences.
2116 Search case-sensitivity is determined by the value of the variable
2117 `case-fold-search', which see.
2119 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2120 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2122 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2125 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2126 "sRE search backward: ",
2127 doc
: /* Search backward from point for match for regular expression REGEXP.
2128 Set point to the beginning of the match, and return point.
2129 The match found is the one starting last in the buffer
2130 and yet ending before the origin of the search.
2131 An optional second argument bounds the search; it is a buffer position.
2132 The match found must start at or after that position.
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 is repeat count--search for successive occurrences.
2137 Search case-sensitivity is determined by the value of the variable
2138 `case-fold-search', which see.
2140 See also the functions `match-beginning', `match-end', `match-string',
2141 and `replace-match'. */)
2142 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2144 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2147 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2149 doc
: /* Search forward from point for regular expression REGEXP.
2150 Set point to the end of the occurrence found, and return point.
2151 An optional second argument bounds the search; it is a buffer position.
2152 The match found must not extend after that position.
2153 Optional third argument, if t, means if fail just return nil (no error).
2154 If not nil and not t, move to limit of search and return nil.
2155 Optional fourth argument is repeat count--search for successive occurrences.
2157 Search case-sensitivity is determined by the value of the variable
2158 `case-fold-search', which see.
2160 See also the functions `match-beginning', `match-end', `match-string',
2161 and `replace-match'. */)
2162 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2164 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2167 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2168 "sPosix search backward: ",
2169 doc
: /* Search backward from point for match for regular expression REGEXP.
2170 Find the longest match in accord with Posix regular expression rules.
2171 Set point to the beginning of the match, and return point.
2172 The match found is the one starting last in the buffer
2173 and yet ending before the origin of the search.
2174 An optional second argument bounds the search; it is a buffer position.
2175 The match found must start at or 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, 1);
2190 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2192 doc
: /* Search forward from point for regular expression REGEXP.
2193 Find the longest match in accord with Posix regular expression rules.
2194 Set point to the end of the occurrence found, and return point.
2195 An optional second argument bounds the search; it is a buffer position.
2196 The match found must not extend after that position.
2197 Optional third argument, if t, means if fail just return nil (no error).
2198 If not nil and not t, move to limit of search and return nil.
2199 Optional fourth argument is repeat count--search for successive occurrences.
2201 Search case-sensitivity is determined by the value of the variable
2202 `case-fold-search', which see.
2204 See also the functions `match-beginning', `match-end', `match-string',
2205 and `replace-match'. */)
2206 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2208 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2211 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2212 doc
: /* Replace text matched by last search with NEWTEXT.
2213 Leave point at the end of the replacement text.
2215 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2216 Otherwise maybe capitalize the whole text, or maybe just word initials,
2217 based on the replaced text.
2218 If the replaced text has only capital letters
2219 and has at least one multiletter word, convert NEWTEXT to all caps.
2220 Otherwise if all words are capitalized in the replaced text,
2221 capitalize each word in NEWTEXT.
2223 If third arg LITERAL is non-nil, insert NEWTEXT literally.
2224 Otherwise treat `\\' as special:
2225 `\\&' in NEWTEXT means substitute original matched text.
2226 `\\N' means substitute what matched the Nth `\\(...\\)'.
2227 If Nth parens didn't match, substitute nothing.
2228 `\\\\' means insert one `\\'.
2229 Case conversion does not apply to these substitutions.
2231 FIXEDCASE and LITERAL are optional arguments.
2233 The optional fourth argument STRING can be a string to modify.
2234 This is meaningful when the previous match was done against STRING,
2235 using `string-match'. When used this way, `replace-match'
2236 creates and returns a new string made by copying STRING and replacing
2237 the part of STRING that was matched.
2239 The optional fifth argument SUBEXP specifies a subexpression;
2240 it says to replace just that subexpression with NEWTEXT,
2241 rather than replacing the entire matched text.
2242 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2243 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2244 NEWTEXT in place of subexp N.
2245 This is useful only after a regular expression search or match,
2246 since only regular expressions have distinguished subexpressions. */)
2247 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2249 enum { nochange
, all_caps
, cap_initial
} case_action
;
2250 register ptrdiff_t pos
, pos_byte
;
2251 int some_multiletter_word
;
2254 int some_nonuppercase_initial
;
2255 register int c
, prevc
;
2257 ptrdiff_t opoint
, newpoint
;
2259 CHECK_STRING (newtext
);
2261 if (! NILP (string
))
2262 CHECK_STRING (string
);
2264 case_action
= nochange
; /* We tried an initialization */
2265 /* but some C compilers blew it */
2267 if (search_regs
.num_regs
<= 0)
2268 error ("`replace-match' called before any match found");
2274 CHECK_NUMBER (subexp
);
2275 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2276 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2277 sub
= XINT (subexp
);
2282 if (search_regs
.start
[sub
] < BEGV
2283 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2284 || search_regs
.end
[sub
] > ZV
)
2285 args_out_of_range (make_number (search_regs
.start
[sub
]),
2286 make_number (search_regs
.end
[sub
]));
2290 if (search_regs
.start
[sub
] < 0
2291 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2292 || search_regs
.end
[sub
] > SCHARS (string
))
2293 args_out_of_range (make_number (search_regs
.start
[sub
]),
2294 make_number (search_regs
.end
[sub
]));
2297 if (NILP (fixedcase
))
2299 /* Decide how to casify by examining the matched text. */
2302 pos
= search_regs
.start
[sub
];
2303 last
= search_regs
.end
[sub
];
2306 pos_byte
= CHAR_TO_BYTE (pos
);
2308 pos_byte
= string_char_to_byte (string
, pos
);
2311 case_action
= all_caps
;
2313 /* some_multiletter_word is set nonzero if any original word
2314 is more than one letter long. */
2315 some_multiletter_word
= 0;
2317 some_nonuppercase_initial
= 0;
2324 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2325 INC_BOTH (pos
, pos_byte
);
2328 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2332 /* Cannot be all caps if any original char is lower case */
2335 if (SYNTAX (prevc
) != Sword
)
2336 some_nonuppercase_initial
= 1;
2338 some_multiletter_word
= 1;
2340 else if (uppercasep (c
))
2343 if (SYNTAX (prevc
) != Sword
)
2346 some_multiletter_word
= 1;
2350 /* If the initial is a caseless word constituent,
2351 treat that like a lowercase initial. */
2352 if (SYNTAX (prevc
) != Sword
)
2353 some_nonuppercase_initial
= 1;
2359 /* Convert to all caps if the old text is all caps
2360 and has at least one multiletter word. */
2361 if (! some_lowercase
&& some_multiletter_word
)
2362 case_action
= all_caps
;
2363 /* Capitalize each word, if the old text has all capitalized words. */
2364 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2365 case_action
= cap_initial
;
2366 else if (!some_nonuppercase_initial
&& some_uppercase
)
2367 /* Should x -> yz, operating on X, give Yz or YZ?
2368 We'll assume the latter. */
2369 case_action
= all_caps
;
2371 case_action
= nochange
;
2374 /* Do replacement in a string. */
2377 Lisp_Object before
, after
;
2379 before
= Fsubstring (string
, make_number (0),
2380 make_number (search_regs
.start
[sub
]));
2381 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2383 /* Substitute parts of the match into NEWTEXT
2387 ptrdiff_t lastpos
= 0;
2388 ptrdiff_t lastpos_byte
= 0;
2389 /* We build up the substituted string in ACCUM. */
2392 ptrdiff_t length
= SBYTES (newtext
);
2396 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2398 ptrdiff_t substart
= -1;
2399 ptrdiff_t subend
= 0;
2400 int delbackslash
= 0;
2402 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2406 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2410 substart
= search_regs
.start
[sub
];
2411 subend
= search_regs
.end
[sub
];
2413 else if (c
>= '1' && c
<= '9')
2415 if (c
- '0' < search_regs
.num_regs
2416 && 0 <= search_regs
.start
[c
- '0'])
2418 substart
= search_regs
.start
[c
- '0'];
2419 subend
= search_regs
.end
[c
- '0'];
2423 /* If that subexp did not match,
2424 replace \\N with nothing. */
2432 error ("Invalid use of `\\' in replacement text");
2436 if (pos
- 2 != lastpos
)
2437 middle
= substring_both (newtext
, lastpos
,
2439 pos
- 2, pos_byte
- 2);
2442 accum
= concat3 (accum
, middle
,
2444 make_number (substart
),
2445 make_number (subend
)));
2447 lastpos_byte
= pos_byte
;
2449 else if (delbackslash
)
2451 middle
= substring_both (newtext
, lastpos
,
2453 pos
- 1, pos_byte
- 1);
2455 accum
= concat2 (accum
, middle
);
2457 lastpos_byte
= pos_byte
;
2462 middle
= substring_both (newtext
, lastpos
,
2468 newtext
= concat2 (accum
, middle
);
2471 /* Do case substitution in NEWTEXT if desired. */
2472 if (case_action
== all_caps
)
2473 newtext
= Fupcase (newtext
);
2474 else if (case_action
== cap_initial
)
2475 newtext
= Fupcase_initials (newtext
);
2477 return concat3 (before
, newtext
, after
);
2480 /* Record point, then move (quietly) to the start of the match. */
2481 if (PT
>= search_regs
.end
[sub
])
2483 else if (PT
> search_regs
.start
[sub
])
2484 opoint
= search_regs
.end
[sub
] - ZV
;
2488 /* If we want non-literal replacement,
2489 perform substitution on the replacement string. */
2492 ptrdiff_t length
= SBYTES (newtext
);
2493 unsigned char *substed
;
2494 ptrdiff_t substed_alloc_size
, substed_len
;
2495 int buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2496 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2497 int really_changed
= 0;
2499 substed_alloc_size
= ((STRING_BYTES_BOUND
- 100) / 2 < length
2500 ? STRING_BYTES_BOUND
2501 : length
* 2 + 100);
2502 substed
= (unsigned char *) xmalloc (substed_alloc_size
);
2505 /* Go thru NEWTEXT, producing the actual text to insert in
2506 SUBSTED while adjusting multibyteness to that of the current
2509 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2511 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2512 const unsigned char *add_stuff
= NULL
;
2513 ptrdiff_t add_len
= 0;
2518 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2520 c
= multibyte_char_to_unibyte (c
);
2524 /* Note that we don't have to increment POS. */
2525 c
= SREF (newtext
, pos_byte
++);
2527 MAKE_CHAR_MULTIBYTE (c
);
2530 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2531 or set IDX to a match index, which means put that part
2532 of the buffer text into SUBSTED. */
2540 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2542 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2543 c
= multibyte_char_to_unibyte (c
);
2547 c
= SREF (newtext
, pos_byte
++);
2549 MAKE_CHAR_MULTIBYTE (c
);
2554 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2556 if (search_regs
.start
[c
- '0'] >= 1)
2560 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2564 error ("Invalid use of `\\' in replacement text");
2569 add_len
= CHAR_STRING (c
, str
);
2573 /* If we want to copy part of a previous match,
2574 set up ADD_STUFF and ADD_LEN to point to it. */
2577 ptrdiff_t begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2578 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2579 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2580 move_gap (search_regs
.start
[idx
]);
2581 add_stuff
= BYTE_POS_ADDR (begbyte
);
2584 /* Now the stuff we want to add to SUBSTED
2585 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2587 /* Make sure SUBSTED is big enough. */
2588 if (substed_alloc_size
- substed_len
< add_len
)
2590 xpalloc (substed
, &substed_alloc_size
,
2591 add_len
- (substed_alloc_size
- substed_len
),
2592 STRING_BYTES_BOUND
, 1);
2594 /* Now add to the end of SUBSTED. */
2597 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2598 substed_len
+= add_len
;
2607 multibyte_chars_in_text (substed
, substed_len
);
2609 newtext
= make_multibyte_string ((char *) substed
, nchars
,
2613 newtext
= make_unibyte_string ((char *) substed
, substed_len
);
2618 /* Replace the old text with the new in the cleanest possible way. */
2619 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2621 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2623 if (case_action
== all_caps
)
2624 Fupcase_region (make_number (search_regs
.start
[sub
]),
2625 make_number (newpoint
));
2626 else if (case_action
== cap_initial
)
2627 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2628 make_number (newpoint
));
2630 /* Adjust search data for this change. */
2632 ptrdiff_t oldend
= search_regs
.end
[sub
];
2633 ptrdiff_t oldstart
= search_regs
.start
[sub
];
2634 ptrdiff_t change
= newpoint
- search_regs
.end
[sub
];
2637 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2639 if (search_regs
.start
[i
] >= oldend
)
2640 search_regs
.start
[i
] += change
;
2641 else if (search_regs
.start
[i
] > oldstart
)
2642 search_regs
.start
[i
] = oldstart
;
2643 if (search_regs
.end
[i
] >= oldend
)
2644 search_regs
.end
[i
] += change
;
2645 else if (search_regs
.end
[i
] > oldstart
)
2646 search_regs
.end
[i
] = oldstart
;
2650 /* Put point back where it was in the text. */
2652 TEMP_SET_PT (opoint
+ ZV
);
2654 TEMP_SET_PT (opoint
);
2656 /* Now move point "officially" to the start of the inserted replacement. */
2657 move_if_not_intangible (newpoint
);
2663 match_limit (Lisp_Object num
, int beginningp
)
2670 args_out_of_range (num
, make_number (0));
2671 if (search_regs
.num_regs
<= 0)
2672 error ("No match data, because no search succeeded");
2673 if (n
>= search_regs
.num_regs
2674 || search_regs
.start
[n
] < 0)
2676 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2677 : search_regs
.end
[n
]));
2680 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2681 doc
: /* Return position of start of text matched by last search.
2682 SUBEXP, a number, specifies which parenthesized expression in the last
2684 Value is nil if SUBEXPth pair didn't match, or there were less than
2686 Zero means the entire text matched by the whole regexp or whole string. */)
2687 (Lisp_Object subexp
)
2689 return match_limit (subexp
, 1);
2692 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2693 doc
: /* Return position of end of text matched by last search.
2694 SUBEXP, a number, specifies which parenthesized expression in the last
2696 Value is nil if SUBEXPth pair didn't match, or there were less than
2698 Zero means the entire text matched by the whole regexp or whole string. */)
2699 (Lisp_Object subexp
)
2701 return match_limit (subexp
, 0);
2704 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2705 doc
: /* Return a list containing all info on what the last search matched.
2706 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2707 All the elements are markers or nil (nil if the Nth pair didn't match)
2708 if the last match was on a buffer; integers or nil if a string was matched.
2709 Use `set-match-data' to reinstate the data in this list.
2711 If INTEGERS (the optional first argument) is non-nil, always use
2712 integers \(rather than markers) to represent buffer positions. In
2713 this case, and if the last match was in a buffer, the buffer will get
2714 stored as one additional element at the end of the list.
2716 If REUSE is a list, reuse it as part of the value. If REUSE is long
2717 enough to hold all the values, and if INTEGERS is non-nil, no consing
2720 If optional third arg RESEAT is non-nil, any previous markers on the
2721 REUSE list will be modified to point to nowhere.
2723 Return value is undefined if the last search failed. */)
2724 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2726 Lisp_Object tail
, prev
;
2731 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2732 if (MARKERP (XCAR (tail
)))
2734 unchain_marker (XMARKER (XCAR (tail
)));
2735 XSETCAR (tail
, Qnil
);
2738 if (NILP (last_thing_searched
))
2743 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
+ 1)
2744 * sizeof (Lisp_Object
));
2747 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2749 ptrdiff_t start
= search_regs
.start
[i
];
2752 if (EQ (last_thing_searched
, Qt
)
2753 || ! NILP (integers
))
2755 XSETFASTINT (data
[2 * i
], start
);
2756 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2758 else if (BUFFERP (last_thing_searched
))
2760 data
[2 * i
] = Fmake_marker ();
2761 Fset_marker (data
[2 * i
],
2762 make_number (start
),
2763 last_thing_searched
);
2764 data
[2 * i
+ 1] = Fmake_marker ();
2765 Fset_marker (data
[2 * i
+ 1],
2766 make_number (search_regs
.end
[i
]),
2767 last_thing_searched
);
2770 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2776 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2779 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2781 data
[len
] = last_thing_searched
;
2785 /* If REUSE is not usable, cons up the values and return them. */
2786 if (! CONSP (reuse
))
2787 return Flist (len
, data
);
2789 /* If REUSE is a list, store as many value elements as will fit
2790 into the elements of REUSE. */
2791 for (i
= 0, tail
= reuse
; CONSP (tail
);
2792 i
++, tail
= XCDR (tail
))
2795 XSETCAR (tail
, data
[i
]);
2797 XSETCAR (tail
, Qnil
);
2801 /* If we couldn't fit all value elements into REUSE,
2802 cons up the rest of them and add them to the end of REUSE. */
2804 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2809 /* We used to have an internal use variant of `reseat' described as:
2811 If RESEAT is `evaporate', put the markers back on the free list
2812 immediately. No other references to the markers must exist in this
2813 case, so it is used only internally on the unwind stack and
2814 save-match-data from Lisp.
2816 But it was ill-conceived: those supposedly-internal markers get exposed via
2817 the undo-list, so freeing them here is unsafe. */
2819 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2820 doc
: /* Set internal data on last search match from elements of LIST.
2821 LIST should have been created by calling `match-data' previously.
2823 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2824 (register Lisp_Object list
, Lisp_Object reseat
)
2827 register Lisp_Object marker
;
2829 if (running_asynch_code
)
2830 save_search_regs ();
2834 /* Unless we find a marker with a buffer or an explicit buffer
2835 in LIST, assume that this match data came from a string. */
2836 last_thing_searched
= Qt
;
2838 /* Allocate registers if they don't already exist. */
2840 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
2842 if (length
> search_regs
.num_regs
)
2844 ptrdiff_t num_regs
= search_regs
.num_regs
;
2845 if (PTRDIFF_MAX
< length
)
2846 memory_full (SIZE_MAX
);
2848 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
2849 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
2851 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
2853 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
2854 search_regs
.start
[i
] = -1;
2856 search_regs
.num_regs
= num_regs
;
2859 for (i
= 0; CONSP (list
); i
++)
2861 marker
= XCAR (list
);
2862 if (BUFFERP (marker
))
2864 last_thing_searched
= marker
;
2871 search_regs
.start
[i
] = -1;
2880 if (MARKERP (marker
))
2882 if (XMARKER (marker
)->buffer
== 0)
2883 XSETFASTINT (marker
, 0);
2885 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2888 CHECK_NUMBER_COERCE_MARKER (marker
);
2891 if (!NILP (reseat
) && MARKERP (m
))
2893 unchain_marker (XMARKER (m
));
2894 XSETCAR (list
, Qnil
);
2897 if ((list
= XCDR (list
), !CONSP (list
)))
2900 m
= marker
= XCAR (list
);
2902 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2903 XSETFASTINT (marker
, 0);
2905 CHECK_NUMBER_COERCE_MARKER (marker
);
2906 if ((XINT (from
) < 0
2907 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
2908 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
2909 && (XINT (marker
) < 0
2910 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
2911 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
2913 search_regs
.start
[i
] = XINT (from
);
2914 search_regs
.end
[i
] = XINT (marker
);
2918 search_regs
.start
[i
] = -1;
2921 if (!NILP (reseat
) && MARKERP (m
))
2923 unchain_marker (XMARKER (m
));
2924 XSETCAR (list
, Qnil
);
2930 for (; i
< search_regs
.num_regs
; i
++)
2931 search_regs
.start
[i
] = -1;
2937 /* If non-zero the match data have been saved in saved_search_regs
2938 during the execution of a sentinel or filter. */
2939 static int search_regs_saved
;
2940 static struct re_registers saved_search_regs
;
2941 static Lisp_Object saved_last_thing_searched
;
2943 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2944 if asynchronous code (filter or sentinel) is running. */
2946 save_search_regs (void)
2948 if (!search_regs_saved
)
2950 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2951 saved_search_regs
.start
= search_regs
.start
;
2952 saved_search_regs
.end
= search_regs
.end
;
2953 saved_last_thing_searched
= last_thing_searched
;
2954 last_thing_searched
= Qnil
;
2955 search_regs
.num_regs
= 0;
2956 search_regs
.start
= 0;
2957 search_regs
.end
= 0;
2959 search_regs_saved
= 1;
2963 /* Called upon exit from filters and sentinels. */
2965 restore_search_regs (void)
2967 if (search_regs_saved
)
2969 if (search_regs
.num_regs
> 0)
2971 xfree (search_regs
.start
);
2972 xfree (search_regs
.end
);
2974 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2975 search_regs
.start
= saved_search_regs
.start
;
2976 search_regs
.end
= saved_search_regs
.end
;
2977 last_thing_searched
= saved_last_thing_searched
;
2978 saved_last_thing_searched
= Qnil
;
2979 search_regs_saved
= 0;
2984 unwind_set_match_data (Lisp_Object list
)
2986 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
2987 return Fset_match_data (list
, Qt
);
2990 /* Called to unwind protect the match data. */
2992 record_unwind_save_match_data (void)
2994 record_unwind_protect (unwind_set_match_data
,
2995 Fmatch_data (Qnil
, Qnil
, Qnil
));
2998 /* Quote a string to deactivate reg-expr chars */
3000 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3001 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3002 (Lisp_Object string
)
3004 register char *in
, *out
, *end
;
3005 register char *temp
;
3006 int backslashes_added
= 0;
3008 CHECK_STRING (string
);
3010 temp
= (char *) alloca (SBYTES (string
) * 2);
3012 /* Now copy the data into the new string, inserting escapes. */
3014 in
= SSDATA (string
);
3015 end
= in
+ SBYTES (string
);
3018 for (; in
!= end
; in
++)
3021 || *in
== '*' || *in
== '.' || *in
== '\\'
3022 || *in
== '?' || *in
== '+'
3023 || *in
== '^' || *in
== '$')
3024 *out
++ = '\\', backslashes_added
++;
3028 return make_specified_string (temp
,
3029 SCHARS (string
) + backslashes_added
,
3031 STRING_MULTIBYTE (string
));
3035 syms_of_search (void)
3039 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3041 searchbufs
[i
].buf
.allocated
= 100;
3042 searchbufs
[i
].buf
.buffer
= (unsigned char *) xmalloc (100);
3043 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3044 searchbufs
[i
].regexp
= Qnil
;
3045 searchbufs
[i
].whitespace_regexp
= Qnil
;
3046 searchbufs
[i
].syntax_table
= Qnil
;
3047 staticpro (&searchbufs
[i
].regexp
);
3048 staticpro (&searchbufs
[i
].whitespace_regexp
);
3049 staticpro (&searchbufs
[i
].syntax_table
);
3050 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3052 searchbuf_head
= &searchbufs
[0];
3054 DEFSYM (Qsearch_failed
, "search-failed");
3055 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3057 Fput (Qsearch_failed
, Qerror_conditions
,
3058 pure_cons (Qsearch_failed
, pure_cons (Qerror
, Qnil
)));
3059 Fput (Qsearch_failed
, Qerror_message
,
3060 make_pure_c_string ("Search failed"));
3062 Fput (Qinvalid_regexp
, Qerror_conditions
,
3063 pure_cons (Qinvalid_regexp
, pure_cons (Qerror
, Qnil
)));
3064 Fput (Qinvalid_regexp
, Qerror_message
,
3065 make_pure_c_string ("Invalid regexp"));
3067 last_thing_searched
= Qnil
;
3068 staticpro (&last_thing_searched
);
3070 saved_last_thing_searched
= Qnil
;
3071 staticpro (&saved_last_thing_searched
);
3073 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3074 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3075 Some commands use this for user-specified regexps.
3076 Spaces that occur inside character classes or repetition operators
3077 or other such regexp constructs are not replaced with this.
3078 A value of nil (which is the normal value) means treat spaces literally. */);
3079 Vsearch_spaces_regexp
= Qnil
;
3081 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3082 doc
: /* Internal use only.
3083 If non-nil, the primitive searching and matching functions
3084 such as `looking-at', `string-match', `re-search-forward', etc.,
3085 do not set the match data. The proper way to use this variable
3086 is to bind it with `let' around a small expression. */);
3087 Vinhibit_changing_match_data
= Qnil
;
3089 defsubr (&Slooking_at
);
3090 defsubr (&Sposix_looking_at
);
3091 defsubr (&Sstring_match
);
3092 defsubr (&Sposix_string_match
);
3093 defsubr (&Ssearch_forward
);
3094 defsubr (&Ssearch_backward
);
3095 defsubr (&Sre_search_forward
);
3096 defsubr (&Sre_search_backward
);
3097 defsubr (&Sposix_search_forward
);
3098 defsubr (&Sposix_search_backward
);
3099 defsubr (&Sreplace_match
);
3100 defsubr (&Smatch_beginning
);
3101 defsubr (&Smatch_end
);
3102 defsubr (&Smatch_data
);
3103 defsubr (&Sset_match_data
);
3104 defsubr (&Sregexp_quote
);