1 /* String search routines for GNU Emacs.
3 Copyright (C) 1985-1987, 1993-1994, 1997-1999, 2001-2013 Free Software
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 newlines 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 newlines left unfound, and return END.
639 If ALLOW_QUIT, set immediate_quit. That's good to do
640 except when inside redisplay. */
643 find_newline (ptrdiff_t start
, ptrdiff_t end
,
644 ptrdiff_t count
, ptrdiff_t *shortage
, bool allow_quit
)
646 struct region_cache
*newline_cache
;
647 ptrdiff_t end_byte
= -1;
654 end
= ZV
, end_byte
= ZV_BYTE
;
660 end
= BEGV
, end_byte
= BEGV_BYTE
;
663 end_byte
= CHAR_TO_BYTE (end
);
665 newline_cache_on_off (current_buffer
);
666 newline_cache
= current_buffer
->newline_cache
;
671 immediate_quit
= allow_quit
;
676 /* Our innermost scanning loop is very simple; it doesn't know
677 about gaps, buffer ends, or the newline cache. ceiling is
678 the position of the last character before the next such
679 obstacle --- the last character the dumb search loop should
681 ptrdiff_t ceiling_byte
= end_byte
- 1;
682 ptrdiff_t start_byte
;
685 /* If we're looking for a newline, consult the newline cache
686 to see where we can avoid some scanning. */
689 ptrdiff_t next_change
;
691 while (region_cache_forward
692 (current_buffer
, newline_cache
, start
, &next_change
))
694 immediate_quit
= allow_quit
;
696 start_byte
= CHAR_TO_BYTE (start
);
698 /* START should never be after END. */
699 if (start_byte
> ceiling_byte
)
700 start_byte
= ceiling_byte
;
702 /* Now the text after start is an unknown region, and
703 next_change is the position of the next known region. */
704 ceiling_byte
= min (CHAR_TO_BYTE (next_change
) - 1, ceiling_byte
);
707 start_byte
= CHAR_TO_BYTE (start
);
709 /* The dumb loop can only scan text stored in contiguous
710 bytes. BUFFER_CEILING_OF returns the last character
711 position that is contiguous, so the ceiling is the
712 position after that. */
713 tem
= BUFFER_CEILING_OF (start_byte
);
714 ceiling_byte
= min (tem
, ceiling_byte
);
717 /* The termination address of the dumb loop. */
718 register unsigned char *ceiling_addr
719 = BYTE_POS_ADDR (ceiling_byte
) + 1;
720 register unsigned char *cursor
721 = BYTE_POS_ADDR (start_byte
);
722 unsigned char *base
= cursor
;
724 while (cursor
< ceiling_addr
)
727 unsigned char *nl
= memchr (cursor
, '\n', ceiling_addr
- cursor
);
729 /* If we're looking for newlines, cache the fact that
730 the region from start to cursor is free of them. */
733 unsigned char *low
= cursor
;
734 unsigned char *lim
= nl
? nl
: ceiling_addr
;
735 know_region_cache (current_buffer
, newline_cache
,
736 BYTE_TO_CHAR (low
- base
+ start_byte
),
737 BYTE_TO_CHAR (lim
- base
+ start_byte
));
746 return BYTE_TO_CHAR (nl
+ 1 - base
+ start_byte
);
751 start
= BYTE_TO_CHAR (ceiling_addr
- base
+ start_byte
);
757 /* The last character to check before the next obstacle. */
758 ptrdiff_t ceiling_byte
= end_byte
;
759 ptrdiff_t start_byte
;
762 /* Consult the newline cache, if appropriate. */
765 ptrdiff_t next_change
;
767 while (region_cache_backward
768 (current_buffer
, newline_cache
, start
, &next_change
))
770 immediate_quit
= allow_quit
;
772 start_byte
= CHAR_TO_BYTE (start
);
774 /* Start should never be at or before end. */
775 if (start_byte
<= ceiling_byte
)
776 start_byte
= ceiling_byte
+ 1;
778 /* Now the text before start is an unknown region, and
779 next_change is the position of the next known region. */
780 ceiling_byte
= max (CHAR_TO_BYTE (next_change
), ceiling_byte
);
783 start_byte
= CHAR_TO_BYTE (start
);
785 /* Stop scanning before the gap. */
786 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
787 ceiling_byte
= max (tem
, ceiling_byte
);
790 /* The termination address of the dumb loop. */
791 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
792 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
793 unsigned char *base
= cursor
;
795 while (cursor
>= ceiling_addr
)
797 unsigned char *nl
= memrchr (ceiling_addr
, '\n',
798 cursor
+ 1 - ceiling_addr
);
800 /* If we're looking for newlines, cache the fact that
801 the region from after the cursor to start is free of them. */
804 unsigned char *low
= nl
? nl
: ceiling_addr
- 1;
805 unsigned char *lim
= cursor
;
806 know_region_cache (current_buffer
, newline_cache
,
807 BYTE_TO_CHAR (low
- base
+ start_byte
),
808 BYTE_TO_CHAR (lim
- base
+ start_byte
));
817 return BYTE_TO_CHAR (nl
- base
+ start_byte
);
822 start
= BYTE_TO_CHAR (ceiling_addr
- 1 - base
+ start_byte
);
828 *shortage
= count
* direction
;
832 /* Search for COUNT instances of a line boundary.
833 Start at START. If COUNT is negative, search backwards.
835 We report the resulting position by calling TEMP_SET_PT_BOTH.
837 If we find COUNT instances. we position after (always after,
838 even if scanning backwards) the COUNTth match, and return 0.
840 If we don't find COUNT instances before reaching the end of the
841 buffer (or the beginning, if scanning backwards), we return
842 the number of line boundaries left unfound, and position at
843 the limit we bumped up against.
845 If ALLOW_QUIT, set immediate_quit. That's good to do
846 except in special cases. */
849 scan_newline (ptrdiff_t start
, ptrdiff_t start_byte
,
850 ptrdiff_t limit
, ptrdiff_t limit_byte
,
851 EMACS_INT count
, bool allow_quit
)
853 int direction
= ((count
> 0) ? 1 : -1);
855 unsigned char *cursor
;
859 unsigned char *ceiling_addr
;
861 bool old_immediate_quit
= immediate_quit
;
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
));
877 unsigned char *nl
= memchr (cursor
, '\n', ceiling_addr
- cursor
);
882 immediate_quit
= old_immediate_quit
;
883 start_byte
+= nl
- base
+ 1;
884 start
= BYTE_TO_CHAR (start_byte
);
885 TEMP_SET_PT_BOTH (start
, start_byte
);
890 while (cursor
< ceiling_addr
);
892 start_byte
+= ceiling_addr
- base
;
897 while (start_byte
> limit_byte
)
899 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
900 ceiling
= max (limit_byte
, ceiling
);
901 ceiling_addr
= BYTE_POS_ADDR (ceiling
);
902 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
905 unsigned char *nl
= memrchr (ceiling_addr
, '\n',
906 cursor
- ceiling_addr
);
912 immediate_quit
= old_immediate_quit
;
913 /* Return the position AFTER the match we found. */
914 start_byte
+= nl
- base
+ 1;
915 start
= BYTE_TO_CHAR (start_byte
);
916 TEMP_SET_PT_BOTH (start
, start_byte
);
922 start_byte
+= ceiling_addr
- base
;
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 find_newline (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
= find_newline (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 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 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 eassert (BEGV
<= lim
&& lim
<= ZV
);
1013 SET_PT_BOTH (lim
, lim_byte
);
1015 #if 0 /* This would be clean, but maybe programs depend on
1016 a value of nil here. */
1024 eassert (BEGV
<= np
&& np
<= ZV
);
1027 return make_number (np
);
1030 /* Return 1 if REGEXP it matches just one constant string. */
1033 trivial_regexp_p (Lisp_Object regexp
)
1035 ptrdiff_t len
= SBYTES (regexp
);
1036 unsigned char *s
= SDATA (regexp
);
1041 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1048 case '|': case '(': case ')': case '`': case '\'': case 'b':
1049 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1050 case 'S': case '=': case '{': case '}': case '_':
1051 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1052 case '1': case '2': case '3': case '4': case '5':
1053 case '6': case '7': case '8': case '9':
1061 /* Search for the n'th occurrence of STRING in the current buffer,
1062 starting at position POS and stopping at position LIM,
1063 treating STRING as a literal string if RE is false or as
1064 a regular expression if RE is true.
1066 If N is positive, searching is forward and LIM must be greater than POS.
1067 If N is negative, searching is backward and LIM must be less than POS.
1069 Returns -x if x occurrences remain to be found (x > 0),
1070 or else the position at the beginning of the Nth occurrence
1071 (if searching backward) or the end (if searching forward).
1073 POSIX is nonzero if we want full backtracking (POSIX style)
1074 for this pattern. 0 means backtrack only enough to get a valid match. */
1076 #define TRANSLATE(out, trt, d) \
1082 temp = Faref (trt, make_number (d)); \
1083 if (INTEGERP (temp)) \
1084 out = XINT (temp); \
1093 /* Only used in search_buffer, to record the end position of the match
1094 when searching regexps and SEARCH_REGS should not be changed
1095 (i.e. Vinhibit_changing_match_data is non-nil). */
1096 static struct re_registers search_regs_1
;
1099 search_buffer (Lisp_Object string
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
1100 ptrdiff_t lim
, ptrdiff_t lim_byte
, EMACS_INT n
,
1101 int RE
, Lisp_Object trt
, Lisp_Object inverse_trt
, int posix
)
1103 ptrdiff_t len
= SCHARS (string
);
1104 ptrdiff_t len_byte
= SBYTES (string
);
1105 register ptrdiff_t i
;
1107 if (running_asynch_code
)
1108 save_search_regs ();
1110 /* Searching 0 times means don't move. */
1111 /* Null string is found at starting position. */
1112 if (len
== 0 || n
== 0)
1114 set_search_regs (pos_byte
, 0);
1118 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1120 unsigned char *p1
, *p2
;
1122 struct re_pattern_buffer
*bufp
;
1124 bufp
= compile_pattern (string
,
1125 (NILP (Vinhibit_changing_match_data
)
1126 ? &search_regs
: &search_regs_1
),
1128 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
1130 immediate_quit
= 1; /* Quit immediately if user types ^G,
1131 because letting this function finish
1132 can take too long. */
1133 QUIT
; /* Do a pending quit right away,
1134 to avoid paradoxical behavior */
1135 /* Get pointers and sizes of the two strings
1136 that make up the visible portion of the buffer. */
1139 s1
= GPT_BYTE
- BEGV_BYTE
;
1141 s2
= ZV_BYTE
- GPT_BYTE
;
1145 s2
= ZV_BYTE
- BEGV_BYTE
;
1150 s1
= ZV_BYTE
- BEGV_BYTE
;
1153 re_match_object
= Qnil
;
1159 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1160 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1161 (NILP (Vinhibit_changing_match_data
)
1162 ? &search_regs
: &search_regs_1
),
1163 /* Don't allow match past current point */
1164 pos_byte
- BEGV_BYTE
);
1167 matcher_overflow ();
1171 if (NILP (Vinhibit_changing_match_data
))
1173 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1174 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1175 if (search_regs
.start
[i
] >= 0)
1177 search_regs
.start
[i
]
1178 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1180 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1182 XSETBUFFER (last_thing_searched
, current_buffer
);
1183 /* Set pos to the new position. */
1184 pos
= search_regs
.start
[0];
1188 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1189 /* Set pos to the new position. */
1190 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1204 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1205 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1206 (NILP (Vinhibit_changing_match_data
)
1207 ? &search_regs
: &search_regs_1
),
1208 lim_byte
- BEGV_BYTE
);
1211 matcher_overflow ();
1215 if (NILP (Vinhibit_changing_match_data
))
1217 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1218 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1219 if (search_regs
.start
[i
] >= 0)
1221 search_regs
.start
[i
]
1222 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1224 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1226 XSETBUFFER (last_thing_searched
, current_buffer
);
1227 pos
= search_regs
.end
[0];
1231 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1232 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1245 else /* non-RE case */
1247 unsigned char *raw_pattern
, *pat
;
1248 ptrdiff_t raw_pattern_size
;
1249 ptrdiff_t raw_pattern_size_byte
;
1250 unsigned char *patbuf
;
1251 int multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1252 unsigned char *base_pat
;
1253 /* Set to positive if we find a non-ASCII char that need
1254 translation. Otherwise set to zero later. */
1256 int boyer_moore_ok
= 1;
1258 /* MULTIBYTE says whether the text to be searched is multibyte.
1259 We must convert PATTERN to match that, or we will not really
1260 find things right. */
1262 if (multibyte
== STRING_MULTIBYTE (string
))
1264 raw_pattern
= SDATA (string
);
1265 raw_pattern_size
= SCHARS (string
);
1266 raw_pattern_size_byte
= SBYTES (string
);
1270 raw_pattern_size
= SCHARS (string
);
1271 raw_pattern_size_byte
1272 = count_size_as_multibyte (SDATA (string
),
1274 raw_pattern
= alloca (raw_pattern_size_byte
+ 1);
1275 copy_text (SDATA (string
), raw_pattern
,
1276 SCHARS (string
), 0, 1);
1280 /* Converting multibyte to single-byte.
1282 ??? Perhaps this conversion should be done in a special way
1283 by subtracting nonascii-insert-offset from each non-ASCII char,
1284 so that only the multibyte chars which really correspond to
1285 the chosen single-byte character set can possibly match. */
1286 raw_pattern_size
= SCHARS (string
);
1287 raw_pattern_size_byte
= SCHARS (string
);
1288 raw_pattern
= alloca (raw_pattern_size
+ 1);
1289 copy_text (SDATA (string
), raw_pattern
,
1290 SBYTES (string
), 1, 0);
1293 /* Copy and optionally translate the pattern. */
1294 len
= raw_pattern_size
;
1295 len_byte
= raw_pattern_size_byte
;
1296 patbuf
= alloca (len
* MAX_MULTIBYTE_LENGTH
);
1298 base_pat
= raw_pattern
;
1301 /* Fill patbuf by translated characters in STRING while
1302 checking if we can use boyer-moore search. If TRT is
1303 non-nil, we can use boyer-moore search only if TRT can be
1304 represented by the byte array of 256 elements. For that,
1305 all non-ASCII case-equivalents of all case-sensitive
1306 characters in STRING must belong to the same character
1307 group (two characters belong to the same group iff their
1308 multibyte forms are the same except for the last byte;
1309 i.e. every 64 characters form a group; U+0000..U+003F,
1310 U+0040..U+007F, U+0080..U+00BF, ...). */
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. */
1402 int c
, translated
, inverse
;
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
;
1416 /* Check that none of C's equivalents violates the
1417 assumptions of boyer_moore. */
1418 TRANSLATE (inverse
, inverse_trt
, c
);
1421 if (inverse
>= 0200)
1428 TRANSLATE (inverse
, inverse_trt
, inverse
);
1433 len_byte
= pat
- patbuf
;
1434 pat
= base_pat
= patbuf
;
1437 return boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1441 return simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1442 pos
, pos_byte
, lim
, lim_byte
);
1446 /* Do a simple string search N times for the string PAT,
1447 whose length is LEN/LEN_BYTE,
1448 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1449 TRT is the translation table.
1451 Return the character position where the match is found.
1452 Otherwise, if M matches remained to be found, return -M.
1454 This kind of search works regardless of what is in PAT and
1455 regardless of what is in TRT. It is used in cases where
1456 boyer_moore cannot work. */
1459 simple_search (EMACS_INT n
, unsigned char *pat
,
1460 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1461 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1462 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1464 int multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1465 int forward
= n
> 0;
1466 /* Number of buffer bytes matched. Note that this may be different
1467 from len_byte in a multibyte buffer. */
1468 ptrdiff_t match_byte
= PTRDIFF_MIN
;
1470 if (lim
> pos
&& multibyte
)
1475 /* Try matching at position POS. */
1476 ptrdiff_t this_pos
= pos
;
1477 ptrdiff_t this_pos_byte
= pos_byte
;
1478 ptrdiff_t this_len
= len
;
1479 unsigned char *p
= pat
;
1480 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1483 while (this_len
> 0)
1485 int charlen
, buf_charlen
;
1488 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1489 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1491 TRANSLATE (buf_ch
, trt
, buf_ch
);
1493 if (buf_ch
!= pat_ch
)
1499 this_pos_byte
+= buf_charlen
;
1505 match_byte
= this_pos_byte
- pos_byte
;
1507 pos_byte
+= match_byte
;
1511 INC_BOTH (pos
, pos_byte
);
1521 /* Try matching at position POS. */
1522 ptrdiff_t this_pos
= pos
;
1523 ptrdiff_t this_len
= len
;
1524 unsigned char *p
= pat
;
1526 if (pos
+ len
> lim
)
1529 while (this_len
> 0)
1532 int buf_ch
= FETCH_BYTE (this_pos
);
1533 TRANSLATE (buf_ch
, trt
, buf_ch
);
1535 if (buf_ch
!= pat_ch
)
1554 /* Backwards search. */
1555 else if (lim
< pos
&& multibyte
)
1560 /* Try matching at position POS. */
1561 ptrdiff_t this_pos
= pos
;
1562 ptrdiff_t this_pos_byte
= pos_byte
;
1563 ptrdiff_t this_len
= len
;
1564 const unsigned char *p
= pat
+ len_byte
;
1566 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1569 while (this_len
> 0)
1573 DEC_BOTH (this_pos
, this_pos_byte
);
1574 PREV_CHAR_BOUNDARY (p
, pat
);
1575 pat_ch
= STRING_CHAR (p
);
1576 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1577 TRANSLATE (buf_ch
, trt
, buf_ch
);
1579 if (buf_ch
!= pat_ch
)
1587 match_byte
= pos_byte
- this_pos_byte
;
1589 pos_byte
= this_pos_byte
;
1593 DEC_BOTH (pos
, pos_byte
);
1603 /* Try matching at position POS. */
1604 ptrdiff_t this_pos
= pos
- len
;
1605 ptrdiff_t this_len
= len
;
1606 unsigned char *p
= pat
;
1611 while (this_len
> 0)
1614 int buf_ch
= FETCH_BYTE (this_pos
);
1615 TRANSLATE (buf_ch
, trt
, buf_ch
);
1617 if (buf_ch
!= pat_ch
)
1639 eassert (match_byte
!= PTRDIFF_MIN
);
1641 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1643 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1653 /* Do Boyer-Moore search N times for the string BASE_PAT,
1654 whose length is LEN_BYTE,
1655 from buffer position POS_BYTE until LIM_BYTE.
1656 DIRECTION says which direction we search in.
1657 TRT and INVERSE_TRT are translation tables.
1658 Characters in PAT are already translated by TRT.
1660 This kind of search works if all the characters in BASE_PAT that
1661 have nontrivial translation are the same aside from the last byte.
1662 This makes it possible to translate just the last byte of a
1663 character, and do so after just a simple test of the context.
1664 CHAR_BASE is nonzero if there is such a non-ASCII character.
1666 If that criterion is not satisfied, do not call this function. */
1669 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1671 Lisp_Object trt
, Lisp_Object inverse_trt
,
1672 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1675 int direction
= ((n
> 0) ? 1 : -1);
1676 register ptrdiff_t dirlen
;
1678 int stride_for_teases
= 0;
1680 register unsigned char *cursor
, *p_limit
;
1681 register ptrdiff_t i
;
1683 unsigned char *pat
, *pat_end
;
1684 int multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1686 unsigned char simple_translate
[0400];
1687 /* These are set to the preceding bytes of a byte to be translated
1688 if char_base is nonzero. As the maximum byte length of a
1689 multibyte character is 5, we have to check at most four previous
1691 int translate_prev_byte1
= 0;
1692 int translate_prev_byte2
= 0;
1693 int translate_prev_byte3
= 0;
1695 /* The general approach is that we are going to maintain that we know
1696 the first (closest to the present position, in whatever direction
1697 we're searching) character that could possibly be the last
1698 (furthest from present position) character of a valid match. We
1699 advance the state of our knowledge by looking at that character
1700 and seeing whether it indeed matches the last character of the
1701 pattern. If it does, we take a closer look. If it does not, we
1702 move our pointer (to putative last characters) as far as is
1703 logically possible. This amount of movement, which I call a
1704 stride, will be the length of the pattern if the actual character
1705 appears nowhere in the pattern, otherwise it will be the distance
1706 from the last occurrence of that character to the end of the
1707 pattern. If the amount is zero we have a possible match. */
1709 /* Here we make a "mickey mouse" BM table. The stride of the search
1710 is determined only by the last character of the putative match.
1711 If that character does not match, we will stride the proper
1712 distance to propose a match that superimposes it on the last
1713 instance of a character that matches it (per trt), or misses
1714 it entirely if there is none. */
1716 dirlen
= len_byte
* direction
;
1718 /* Record position after the end of the pattern. */
1719 pat_end
= base_pat
+ len_byte
;
1720 /* BASE_PAT points to a character that we start scanning from.
1721 It is the first character in a forward search,
1722 the last character in a backward search. */
1724 base_pat
= pat_end
- 1;
1726 /* A character that does not appear in the pattern induces a
1727 stride equal to the pattern length. */
1728 for (i
= 0; i
< 0400; i
++)
1731 /* We use this for translation, instead of TRT itself.
1732 We fill this in to handle the characters that actually
1733 occur in the pattern. Others don't matter anyway! */
1734 for (i
= 0; i
< 0400; i
++)
1735 simple_translate
[i
] = i
;
1739 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1740 byte following them are the target of translation. */
1741 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1742 int cblen
= CHAR_STRING (char_base
, str
);
1744 translate_prev_byte1
= str
[cblen
- 2];
1747 translate_prev_byte2
= str
[cblen
- 3];
1749 translate_prev_byte3
= str
[cblen
- 4];
1756 unsigned char *ptr
= base_pat
+ i
;
1760 /* If the byte currently looking at is the last of a
1761 character to check case-equivalents, set CH to that
1762 character. An ASCII character and a non-ASCII character
1763 matching with CHAR_BASE are to be checked. */
1766 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1769 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1771 unsigned char *charstart
= ptr
- 1;
1773 while (! (CHAR_HEAD_P (*charstart
)))
1775 ch
= STRING_CHAR (charstart
);
1776 if (char_base
!= (ch
& ~0x3F))
1780 if (ch
>= 0200 && multibyte
)
1781 j
= (ch
& 0x3F) | 0200;
1786 stride_for_teases
= BM_tab
[j
];
1788 BM_tab
[j
] = dirlen
- i
;
1789 /* A translation table is accompanied by its inverse -- see
1790 comment following downcase_table for details. */
1793 int starting_ch
= ch
;
1798 TRANSLATE (ch
, inverse_trt
, ch
);
1799 if (ch
>= 0200 && multibyte
)
1800 j
= (ch
& 0x3F) | 0200;
1804 /* For all the characters that map into CH,
1805 set up simple_translate to map the last byte
1807 simple_translate
[j
] = starting_j
;
1808 if (ch
== starting_ch
)
1810 BM_tab
[j
] = dirlen
- i
;
1819 stride_for_teases
= BM_tab
[j
];
1820 BM_tab
[j
] = dirlen
- i
;
1822 /* stride_for_teases tells how much to stride if we get a
1823 match on the far character but are subsequently
1824 disappointed, by recording what the stride would have been
1825 for that character if the last character had been
1828 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1829 /* loop invariant - POS_BYTE points at where last char (first
1830 char if reverse) of pattern would align in a possible match. */
1834 unsigned char *tail_end_ptr
;
1836 /* It's been reported that some (broken) compiler thinks that
1837 Boolean expressions in an arithmetic context are unsigned.
1838 Using an explicit ?1:0 prevents this. */
1839 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1841 return (n
* (0 - direction
));
1842 /* First we do the part we can by pointers (maybe nothing) */
1845 limit
= pos_byte
- dirlen
+ direction
;
1848 limit
= BUFFER_CEILING_OF (limit
);
1849 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1850 can take on without hitting edge of buffer or the gap. */
1851 limit
= min (limit
, pos_byte
+ 20000);
1852 limit
= min (limit
, lim_byte
- 1);
1856 limit
= BUFFER_FLOOR_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
= max (limit
, pos_byte
- 20000);
1860 limit
= max (limit
, lim_byte
);
1862 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1863 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1865 if ((limit
- pos_byte
) * direction
> 20)
1869 p_limit
= BYTE_POS_ADDR (limit
);
1870 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1871 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1872 while (1) /* use one cursor setting as long as i can */
1874 if (direction
> 0) /* worth duplicating */
1876 while (cursor
<= p_limit
)
1878 if (BM_tab
[*cursor
] == 0)
1880 cursor
+= BM_tab
[*cursor
];
1885 while (cursor
>= p_limit
)
1887 if (BM_tab
[*cursor
] == 0)
1889 cursor
+= BM_tab
[*cursor
];
1892 /* If you are here, cursor is beyond the end of the
1893 searched region. You fail to match within the
1894 permitted region and would otherwise try a character
1895 beyond that region. */
1899 i
= dirlen
- direction
;
1902 while ((i
-= direction
) + direction
!= 0)
1905 cursor
-= direction
;
1906 /* Translate only the last byte of a character. */
1908 || ((cursor
== tail_end_ptr
1909 || CHAR_HEAD_P (cursor
[1]))
1910 && (CHAR_HEAD_P (cursor
[0])
1911 /* Check if this is the last byte of
1912 a translatable character. */
1913 || (translate_prev_byte1
== cursor
[-1]
1914 && (CHAR_HEAD_P (translate_prev_byte1
)
1915 || (translate_prev_byte2
== cursor
[-2]
1916 && (CHAR_HEAD_P (translate_prev_byte2
)
1917 || (translate_prev_byte3
== cursor
[-3]))))))))
1918 ch
= simple_translate
[*cursor
];
1927 while ((i
-= direction
) + direction
!= 0)
1929 cursor
-= direction
;
1930 if (pat
[i
] != *cursor
)
1934 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1935 if (i
+ direction
== 0)
1937 ptrdiff_t position
, start
, end
;
1939 cursor
-= direction
;
1941 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1942 ? 1 - len_byte
: 0);
1943 set_search_regs (position
, len_byte
);
1945 if (NILP (Vinhibit_changing_match_data
))
1947 start
= search_regs
.start
[0];
1948 end
= search_regs
.end
[0];
1951 /* If Vinhibit_changing_match_data is non-nil,
1952 search_regs will not be changed. So let's
1953 compute start and end here. */
1955 start
= BYTE_TO_CHAR (position
);
1956 end
= BYTE_TO_CHAR (position
+ len_byte
);
1959 if ((n
-= direction
) != 0)
1960 cursor
+= dirlen
; /* to resume search */
1962 return direction
> 0 ? end
: start
;
1965 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1967 pos_byte
+= cursor
- p2
;
1970 /* Now we'll pick up a clump that has to be done the hard
1971 way because it covers a discontinuity. */
1973 limit
= ((direction
> 0)
1974 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1975 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1976 limit
= ((direction
> 0)
1977 ? min (limit
+ len_byte
, lim_byte
- 1)
1978 : max (limit
- len_byte
, lim_byte
));
1979 /* LIMIT is now the last value POS_BYTE can have
1980 and still be valid for a possible match. */
1983 /* This loop can be coded for space rather than
1984 speed because it will usually run only once.
1985 (the reach is at most len + 21, and typically
1986 does not exceed len). */
1987 while ((limit
- pos_byte
) * direction
>= 0)
1989 int ch
= FETCH_BYTE (pos_byte
);
1990 if (BM_tab
[ch
] == 0)
1992 pos_byte
+= BM_tab
[ch
];
1994 break; /* ran off the end */
1997 /* Found what might be a match. */
1998 i
= dirlen
- direction
;
1999 while ((i
-= direction
) + direction
!= 0)
2003 pos_byte
-= direction
;
2004 ptr
= BYTE_POS_ADDR (pos_byte
);
2005 /* Translate only the last byte of a character. */
2007 || ((ptr
== tail_end_ptr
2008 || CHAR_HEAD_P (ptr
[1]))
2009 && (CHAR_HEAD_P (ptr
[0])
2010 /* Check if this is the last byte of a
2011 translatable character. */
2012 || (translate_prev_byte1
== ptr
[-1]
2013 && (CHAR_HEAD_P (translate_prev_byte1
)
2014 || (translate_prev_byte2
== ptr
[-2]
2015 && (CHAR_HEAD_P (translate_prev_byte2
)
2016 || translate_prev_byte3
== ptr
[-3])))))))
2017 ch
= simple_translate
[*ptr
];
2023 /* Above loop has moved POS_BYTE part or all the way
2024 back to the first pos (last pos if reverse).
2025 Set it once again at the last (first if reverse) char. */
2026 pos_byte
+= dirlen
- i
- direction
;
2027 if (i
+ direction
== 0)
2029 ptrdiff_t position
, start
, end
;
2030 pos_byte
-= direction
;
2032 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2033 set_search_regs (position
, len_byte
);
2035 if (NILP (Vinhibit_changing_match_data
))
2037 start
= search_regs
.start
[0];
2038 end
= search_regs
.end
[0];
2041 /* If Vinhibit_changing_match_data is non-nil,
2042 search_regs will not be changed. So let's
2043 compute start and end here. */
2045 start
= BYTE_TO_CHAR (position
);
2046 end
= BYTE_TO_CHAR (position
+ len_byte
);
2049 if ((n
-= direction
) != 0)
2050 pos_byte
+= dirlen
; /* to resume search */
2052 return direction
> 0 ? end
: start
;
2055 pos_byte
+= stride_for_teases
;
2058 /* We have done one clump. Can we continue? */
2059 if ((lim_byte
- pos_byte
) * direction
< 0)
2060 return ((0 - n
) * direction
);
2062 return BYTE_TO_CHAR (pos_byte
);
2065 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2066 for the overall match just found in the current buffer.
2067 Also clear out the match data for registers 1 and up. */
2070 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2074 if (!NILP (Vinhibit_changing_match_data
))
2077 /* Make sure we have registers in which to store
2078 the match position. */
2079 if (search_regs
.num_regs
== 0)
2081 search_regs
.start
= xmalloc (2 * sizeof (regoff_t
));
2082 search_regs
.end
= xmalloc (2 * sizeof (regoff_t
));
2083 search_regs
.num_regs
= 2;
2086 /* Clear out the other registers. */
2087 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2089 search_regs
.start
[i
] = -1;
2090 search_regs
.end
[i
] = -1;
2093 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2094 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2095 XSETBUFFER (last_thing_searched
, current_buffer
);
2098 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2099 "MSearch backward: ",
2100 doc
: /* Search backward from point for STRING.
2101 Set point to the beginning of the occurrence found, and return point.
2102 An optional second argument bounds the search; it is a buffer position.
2103 The match found must not extend before that position.
2104 Optional third argument, if t, means if fail just return nil (no error).
2105 If not nil and not t, position at limit of search and return nil.
2106 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2107 successive occurrences. If COUNT is negative, search forward,
2108 instead of backward, for -COUNT occurrences.
2110 Search case-sensitivity is determined by the value of the variable
2111 `case-fold-search', which see.
2113 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2114 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2116 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2119 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2120 doc
: /* Search forward from point for STRING.
2121 Set point to the end of the occurrence found, and return point.
2122 An optional second argument bounds the search; it is a buffer position.
2123 The match found must not extend after that position. A value of nil is
2124 equivalent to (point-max).
2125 Optional third argument, if t, means if fail just return nil (no error).
2126 If not nil and not t, move to limit of search and return nil.
2127 Optional fourth argument COUNT, if non-nil, means to search for COUNT
2128 successive occurrences. If COUNT is negative, search backward,
2129 instead of forward, for -COUNT occurrences.
2131 Search case-sensitivity is determined by the value of the variable
2132 `case-fold-search', which see.
2134 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2135 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2137 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2140 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2141 "sRE search backward: ",
2142 doc
: /* Search backward from point for match for regular expression REGEXP.
2143 Set point to the beginning of the match, and return point.
2144 The match found is the one starting last in the buffer
2145 and yet ending before the origin of the search.
2146 An optional second argument bounds the search; it is a buffer position.
2147 The match found must start at or after that position.
2148 Optional third argument, if t, means if fail just return nil (no error).
2149 If not nil and not t, move to limit of search and return nil.
2150 Optional fourth argument is repeat count--search for successive occurrences.
2152 Search case-sensitivity is determined by the value of the variable
2153 `case-fold-search', which see.
2155 See also the functions `match-beginning', `match-end', `match-string',
2156 and `replace-match'. */)
2157 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2159 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2162 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2164 doc
: /* Search forward from point for regular expression REGEXP.
2165 Set point to the end of the occurrence found, and return point.
2166 An optional second argument bounds the search; it is a buffer position.
2167 The match found must not extend after that position.
2168 Optional third argument, if t, means if fail just return nil (no error).
2169 If not nil and not t, move to limit of search and return nil.
2170 Optional fourth argument is repeat count--search for successive occurrences.
2172 Search case-sensitivity is determined by the value of the variable
2173 `case-fold-search', which see.
2175 See also the functions `match-beginning', `match-end', `match-string',
2176 and `replace-match'. */)
2177 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2179 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2182 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2183 "sPosix search backward: ",
2184 doc
: /* Search backward from point for match for regular expression REGEXP.
2185 Find the longest match in accord with Posix regular expression rules.
2186 Set point to the beginning of the match, and return point.
2187 The match found is the one starting last in the buffer
2188 and yet ending before the origin of the search.
2189 An optional second argument bounds the search; it is a buffer position.
2190 The match found must start at or after that position.
2191 Optional third argument, if t, means if fail just return nil (no error).
2192 If not nil and not t, move to limit of search and return nil.
2193 Optional fourth argument is repeat count--search for successive occurrences.
2195 Search case-sensitivity is determined by the value of the variable
2196 `case-fold-search', which see.
2198 See also the functions `match-beginning', `match-end', `match-string',
2199 and `replace-match'. */)
2200 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2202 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2205 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2207 doc
: /* Search forward from point for regular expression REGEXP.
2208 Find the longest match in accord with Posix regular expression rules.
2209 Set point to the end of the occurrence found, and return point.
2210 An optional second argument bounds the search; it is a buffer position.
2211 The match found must not extend after that position.
2212 Optional third argument, if t, means if fail just return nil (no error).
2213 If not nil and not t, move to limit of search and return nil.
2214 Optional fourth argument is repeat count--search for successive occurrences.
2216 Search case-sensitivity is determined by the value of the variable
2217 `case-fold-search', which see.
2219 See also the functions `match-beginning', `match-end', `match-string',
2220 and `replace-match'. */)
2221 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2223 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2226 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2227 doc
: /* Replace text matched by last search with NEWTEXT.
2228 Leave point at the end of the replacement text.
2230 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2231 the replacement text. Otherwise, maybe capitalize the whole text, or
2232 maybe just word initials, based on the replaced text. If the replaced
2233 text has only capital letters and has at least one multiletter word,
2234 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2235 in the replaced text, capitalize each word in NEWTEXT.
2237 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2238 Otherwise treat `\\' as special:
2239 `\\&' in NEWTEXT means substitute original matched text.
2240 `\\N' means substitute what matched the Nth `\\(...\\)'.
2241 If Nth parens didn't match, substitute nothing.
2242 `\\\\' means insert one `\\'.
2243 `\\?' is treated literally
2244 (for compatibility with `query-replace-regexp').
2245 Any other character following `\\' signals an error.
2246 Case conversion does not apply to these substitutions.
2248 If optional fourth argument STRING is non-nil, it should be a string
2249 to act on; this should be the string on which the previous match was
2250 done via `string-match'. In this case, `replace-match' creates and
2251 returns a new string, made by copying STRING and replacing the part of
2252 STRING that was matched (the original STRING itself is not altered).
2254 The optional fifth argument SUBEXP specifies a subexpression;
2255 it says to replace just that subexpression with NEWTEXT,
2256 rather than replacing the entire matched text.
2257 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2258 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2259 NEWTEXT in place of subexp N.
2260 This is useful only after a regular expression search or match,
2261 since only regular expressions have distinguished subexpressions. */)
2262 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2264 enum { nochange
, all_caps
, cap_initial
} case_action
;
2265 register ptrdiff_t pos
, pos_byte
;
2266 int some_multiletter_word
;
2269 int some_nonuppercase_initial
;
2270 register int c
, prevc
;
2272 ptrdiff_t opoint
, newpoint
;
2274 CHECK_STRING (newtext
);
2276 if (! NILP (string
))
2277 CHECK_STRING (string
);
2279 case_action
= nochange
; /* We tried an initialization */
2280 /* but some C compilers blew it */
2282 if (search_regs
.num_regs
<= 0)
2283 error ("`replace-match' called before any match found");
2289 CHECK_NUMBER (subexp
);
2290 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2291 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2292 sub
= XINT (subexp
);
2297 if (search_regs
.start
[sub
] < BEGV
2298 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2299 || search_regs
.end
[sub
] > ZV
)
2300 args_out_of_range (make_number (search_regs
.start
[sub
]),
2301 make_number (search_regs
.end
[sub
]));
2305 if (search_regs
.start
[sub
] < 0
2306 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2307 || search_regs
.end
[sub
] > SCHARS (string
))
2308 args_out_of_range (make_number (search_regs
.start
[sub
]),
2309 make_number (search_regs
.end
[sub
]));
2312 if (NILP (fixedcase
))
2314 /* Decide how to casify by examining the matched text. */
2317 pos
= search_regs
.start
[sub
];
2318 last
= search_regs
.end
[sub
];
2321 pos_byte
= CHAR_TO_BYTE (pos
);
2323 pos_byte
= string_char_to_byte (string
, pos
);
2326 case_action
= all_caps
;
2328 /* some_multiletter_word is set nonzero if any original word
2329 is more than one letter long. */
2330 some_multiletter_word
= 0;
2332 some_nonuppercase_initial
= 0;
2339 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2340 INC_BOTH (pos
, pos_byte
);
2343 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2347 /* Cannot be all caps if any original char is lower case */
2350 if (SYNTAX (prevc
) != Sword
)
2351 some_nonuppercase_initial
= 1;
2353 some_multiletter_word
= 1;
2355 else if (uppercasep (c
))
2358 if (SYNTAX (prevc
) != Sword
)
2361 some_multiletter_word
= 1;
2365 /* If the initial is a caseless word constituent,
2366 treat that like a lowercase initial. */
2367 if (SYNTAX (prevc
) != Sword
)
2368 some_nonuppercase_initial
= 1;
2374 /* Convert to all caps if the old text is all caps
2375 and has at least one multiletter word. */
2376 if (! some_lowercase
&& some_multiletter_word
)
2377 case_action
= all_caps
;
2378 /* Capitalize each word, if the old text has all capitalized words. */
2379 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2380 case_action
= cap_initial
;
2381 else if (!some_nonuppercase_initial
&& some_uppercase
)
2382 /* Should x -> yz, operating on X, give Yz or YZ?
2383 We'll assume the latter. */
2384 case_action
= all_caps
;
2386 case_action
= nochange
;
2389 /* Do replacement in a string. */
2392 Lisp_Object before
, after
;
2394 before
= Fsubstring (string
, make_number (0),
2395 make_number (search_regs
.start
[sub
]));
2396 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2398 /* Substitute parts of the match into NEWTEXT
2402 ptrdiff_t lastpos
= 0;
2403 ptrdiff_t lastpos_byte
= 0;
2404 /* We build up the substituted string in ACCUM. */
2407 ptrdiff_t length
= SBYTES (newtext
);
2411 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2413 ptrdiff_t substart
= -1;
2414 ptrdiff_t subend
= 0;
2415 int delbackslash
= 0;
2417 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2421 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2425 substart
= search_regs
.start
[sub
];
2426 subend
= search_regs
.end
[sub
];
2428 else if (c
>= '1' && c
<= '9')
2430 if (c
- '0' < search_regs
.num_regs
2431 && 0 <= search_regs
.start
[c
- '0'])
2433 substart
= search_regs
.start
[c
- '0'];
2434 subend
= search_regs
.end
[c
- '0'];
2438 /* If that subexp did not match,
2439 replace \\N with nothing. */
2447 error ("Invalid use of `\\' in replacement text");
2451 if (pos
- 2 != lastpos
)
2452 middle
= substring_both (newtext
, lastpos
,
2454 pos
- 2, pos_byte
- 2);
2457 accum
= concat3 (accum
, middle
,
2459 make_number (substart
),
2460 make_number (subend
)));
2462 lastpos_byte
= pos_byte
;
2464 else if (delbackslash
)
2466 middle
= substring_both (newtext
, lastpos
,
2468 pos
- 1, pos_byte
- 1);
2470 accum
= concat2 (accum
, middle
);
2472 lastpos_byte
= pos_byte
;
2477 middle
= substring_both (newtext
, lastpos
,
2483 newtext
= concat2 (accum
, middle
);
2486 /* Do case substitution in NEWTEXT if desired. */
2487 if (case_action
== all_caps
)
2488 newtext
= Fupcase (newtext
);
2489 else if (case_action
== cap_initial
)
2490 newtext
= Fupcase_initials (newtext
);
2492 return concat3 (before
, newtext
, after
);
2495 /* Record point, then move (quietly) to the start of the match. */
2496 if (PT
>= search_regs
.end
[sub
])
2498 else if (PT
> search_regs
.start
[sub
])
2499 opoint
= search_regs
.end
[sub
] - ZV
;
2503 /* If we want non-literal replacement,
2504 perform substitution on the replacement string. */
2507 ptrdiff_t length
= SBYTES (newtext
);
2508 unsigned char *substed
;
2509 ptrdiff_t substed_alloc_size
, substed_len
;
2510 int buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2511 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2512 int really_changed
= 0;
2514 substed_alloc_size
= ((STRING_BYTES_BOUND
- 100) / 2 < length
2515 ? STRING_BYTES_BOUND
2516 : length
* 2 + 100);
2517 substed
= xmalloc (substed_alloc_size
);
2520 /* Go thru NEWTEXT, producing the actual text to insert in
2521 SUBSTED while adjusting multibyteness to that of the current
2524 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2526 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2527 const unsigned char *add_stuff
= NULL
;
2528 ptrdiff_t add_len
= 0;
2533 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2535 c
= multibyte_char_to_unibyte (c
);
2539 /* Note that we don't have to increment POS. */
2540 c
= SREF (newtext
, pos_byte
++);
2542 MAKE_CHAR_MULTIBYTE (c
);
2545 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2546 or set IDX to a match index, which means put that part
2547 of the buffer text into SUBSTED. */
2555 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2557 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2558 c
= multibyte_char_to_unibyte (c
);
2562 c
= SREF (newtext
, pos_byte
++);
2564 MAKE_CHAR_MULTIBYTE (c
);
2569 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2571 if (search_regs
.start
[c
- '0'] >= 1)
2575 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2579 error ("Invalid use of `\\' in replacement text");
2584 add_len
= CHAR_STRING (c
, str
);
2588 /* If we want to copy part of a previous match,
2589 set up ADD_STUFF and ADD_LEN to point to it. */
2592 ptrdiff_t begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2593 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2594 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2595 move_gap_both (search_regs
.start
[idx
], begbyte
);
2596 add_stuff
= BYTE_POS_ADDR (begbyte
);
2599 /* Now the stuff we want to add to SUBSTED
2600 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2602 /* Make sure SUBSTED is big enough. */
2603 if (substed_alloc_size
- substed_len
< add_len
)
2605 xpalloc (substed
, &substed_alloc_size
,
2606 add_len
- (substed_alloc_size
- substed_len
),
2607 STRING_BYTES_BOUND
, 1);
2609 /* Now add to the end of SUBSTED. */
2612 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2613 substed_len
+= add_len
;
2622 multibyte_chars_in_text (substed
, substed_len
);
2624 newtext
= make_multibyte_string ((char *) substed
, nchars
,
2628 newtext
= make_unibyte_string ((char *) substed
, substed_len
);
2633 /* Replace the old text with the new in the cleanest possible way. */
2634 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2636 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2638 if (case_action
== all_caps
)
2639 Fupcase_region (make_number (search_regs
.start
[sub
]),
2640 make_number (newpoint
));
2641 else if (case_action
== cap_initial
)
2642 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2643 make_number (newpoint
));
2645 /* Adjust search data for this change. */
2647 ptrdiff_t oldend
= search_regs
.end
[sub
];
2648 ptrdiff_t oldstart
= search_regs
.start
[sub
];
2649 ptrdiff_t change
= newpoint
- search_regs
.end
[sub
];
2652 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2654 if (search_regs
.start
[i
] >= oldend
)
2655 search_regs
.start
[i
] += change
;
2656 else if (search_regs
.start
[i
] > oldstart
)
2657 search_regs
.start
[i
] = oldstart
;
2658 if (search_regs
.end
[i
] >= oldend
)
2659 search_regs
.end
[i
] += change
;
2660 else if (search_regs
.end
[i
] > oldstart
)
2661 search_regs
.end
[i
] = oldstart
;
2665 /* Put point back where it was in the text. */
2667 TEMP_SET_PT (opoint
+ ZV
);
2669 TEMP_SET_PT (opoint
);
2671 /* Now move point "officially" to the start of the inserted replacement. */
2672 move_if_not_intangible (newpoint
);
2678 match_limit (Lisp_Object num
, int beginningp
)
2685 args_out_of_range (num
, make_number (0));
2686 if (search_regs
.num_regs
<= 0)
2687 error ("No match data, because no search succeeded");
2688 if (n
>= search_regs
.num_regs
2689 || search_regs
.start
[n
] < 0)
2691 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2692 : search_regs
.end
[n
]));
2695 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2696 doc
: /* Return position of start of text matched by last search.
2697 SUBEXP, a number, specifies which parenthesized expression in the last
2699 Value is nil if SUBEXPth pair didn't match, or there were less than
2701 Zero means the entire text matched by the whole regexp or whole string. */)
2702 (Lisp_Object subexp
)
2704 return match_limit (subexp
, 1);
2707 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2708 doc
: /* Return position of end of text matched by last search.
2709 SUBEXP, a number, specifies which parenthesized expression in the last
2711 Value is nil if SUBEXPth pair didn't match, or there were less than
2713 Zero means the entire text matched by the whole regexp or whole string. */)
2714 (Lisp_Object subexp
)
2716 return match_limit (subexp
, 0);
2719 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2720 doc
: /* Return a list containing all info on what the last search matched.
2721 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2722 All the elements are markers or nil (nil if the Nth pair didn't match)
2723 if the last match was on a buffer; integers or nil if a string was matched.
2724 Use `set-match-data' to reinstate the data in this list.
2726 If INTEGERS (the optional first argument) is non-nil, always use
2727 integers \(rather than markers) to represent buffer positions. In
2728 this case, and if the last match was in a buffer, the buffer will get
2729 stored as one additional element at the end of the list.
2731 If REUSE is a list, reuse it as part of the value. If REUSE is long
2732 enough to hold all the values, and if INTEGERS is non-nil, no consing
2735 If optional third arg RESEAT is non-nil, any previous markers on the
2736 REUSE list will be modified to point to nowhere.
2738 Return value is undefined if the last search failed. */)
2739 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2741 Lisp_Object tail
, prev
;
2746 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2747 if (MARKERP (XCAR (tail
)))
2749 unchain_marker (XMARKER (XCAR (tail
)));
2750 XSETCAR (tail
, Qnil
);
2753 if (NILP (last_thing_searched
))
2758 data
= alloca ((2 * search_regs
.num_regs
+ 1) * sizeof *data
);
2761 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2763 ptrdiff_t start
= search_regs
.start
[i
];
2766 if (EQ (last_thing_searched
, Qt
)
2767 || ! NILP (integers
))
2769 XSETFASTINT (data
[2 * i
], start
);
2770 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2772 else if (BUFFERP (last_thing_searched
))
2774 data
[2 * i
] = Fmake_marker ();
2775 Fset_marker (data
[2 * i
],
2776 make_number (start
),
2777 last_thing_searched
);
2778 data
[2 * i
+ 1] = Fmake_marker ();
2779 Fset_marker (data
[2 * i
+ 1],
2780 make_number (search_regs
.end
[i
]),
2781 last_thing_searched
);
2784 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2790 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2793 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2795 data
[len
] = last_thing_searched
;
2799 /* If REUSE is not usable, cons up the values and return them. */
2800 if (! CONSP (reuse
))
2801 return Flist (len
, data
);
2803 /* If REUSE is a list, store as many value elements as will fit
2804 into the elements of REUSE. */
2805 for (i
= 0, tail
= reuse
; CONSP (tail
);
2806 i
++, tail
= XCDR (tail
))
2809 XSETCAR (tail
, data
[i
]);
2811 XSETCAR (tail
, Qnil
);
2815 /* If we couldn't fit all value elements into REUSE,
2816 cons up the rest of them and add them to the end of REUSE. */
2818 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2823 /* We used to have an internal use variant of `reseat' described as:
2825 If RESEAT is `evaporate', put the markers back on the free list
2826 immediately. No other references to the markers must exist in this
2827 case, so it is used only internally on the unwind stack and
2828 save-match-data from Lisp.
2830 But it was ill-conceived: those supposedly-internal markers get exposed via
2831 the undo-list, so freeing them here is unsafe. */
2833 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2834 doc
: /* Set internal data on last search match from elements of LIST.
2835 LIST should have been created by calling `match-data' previously.
2837 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2838 (register Lisp_Object list
, Lisp_Object reseat
)
2841 register Lisp_Object marker
;
2843 if (running_asynch_code
)
2844 save_search_regs ();
2848 /* Unless we find a marker with a buffer or an explicit buffer
2849 in LIST, assume that this match data came from a string. */
2850 last_thing_searched
= Qt
;
2852 /* Allocate registers if they don't already exist. */
2854 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
2856 if (length
> search_regs
.num_regs
)
2858 ptrdiff_t num_regs
= search_regs
.num_regs
;
2859 if (PTRDIFF_MAX
< length
)
2860 memory_full (SIZE_MAX
);
2862 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
2863 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
2865 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
2867 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
2868 search_regs
.start
[i
] = -1;
2870 search_regs
.num_regs
= num_regs
;
2873 for (i
= 0; CONSP (list
); i
++)
2875 marker
= XCAR (list
);
2876 if (BUFFERP (marker
))
2878 last_thing_searched
= marker
;
2885 search_regs
.start
[i
] = -1;
2894 if (MARKERP (marker
))
2896 if (XMARKER (marker
)->buffer
== 0)
2897 XSETFASTINT (marker
, 0);
2899 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2902 CHECK_NUMBER_COERCE_MARKER (marker
);
2905 if (!NILP (reseat
) && MARKERP (m
))
2907 unchain_marker (XMARKER (m
));
2908 XSETCAR (list
, Qnil
);
2911 if ((list
= XCDR (list
), !CONSP (list
)))
2914 m
= marker
= XCAR (list
);
2916 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2917 XSETFASTINT (marker
, 0);
2919 CHECK_NUMBER_COERCE_MARKER (marker
);
2920 if ((XINT (from
) < 0
2921 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
2922 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
2923 && (XINT (marker
) < 0
2924 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
2925 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
2927 search_regs
.start
[i
] = XINT (from
);
2928 search_regs
.end
[i
] = XINT (marker
);
2932 search_regs
.start
[i
] = -1;
2935 if (!NILP (reseat
) && MARKERP (m
))
2937 unchain_marker (XMARKER (m
));
2938 XSETCAR (list
, Qnil
);
2944 for (; i
< search_regs
.num_regs
; i
++)
2945 search_regs
.start
[i
] = -1;
2951 /* If non-zero the match data have been saved in saved_search_regs
2952 during the execution of a sentinel or filter. */
2953 static int search_regs_saved
;
2954 static struct re_registers saved_search_regs
;
2955 static Lisp_Object saved_last_thing_searched
;
2957 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2958 if asynchronous code (filter or sentinel) is running. */
2960 save_search_regs (void)
2962 if (!search_regs_saved
)
2964 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2965 saved_search_regs
.start
= search_regs
.start
;
2966 saved_search_regs
.end
= search_regs
.end
;
2967 saved_last_thing_searched
= last_thing_searched
;
2968 last_thing_searched
= Qnil
;
2969 search_regs
.num_regs
= 0;
2970 search_regs
.start
= 0;
2971 search_regs
.end
= 0;
2973 search_regs_saved
= 1;
2977 /* Called upon exit from filters and sentinels. */
2979 restore_search_regs (void)
2981 if (search_regs_saved
)
2983 if (search_regs
.num_regs
> 0)
2985 xfree (search_regs
.start
);
2986 xfree (search_regs
.end
);
2988 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2989 search_regs
.start
= saved_search_regs
.start
;
2990 search_regs
.end
= saved_search_regs
.end
;
2991 last_thing_searched
= saved_last_thing_searched
;
2992 saved_last_thing_searched
= Qnil
;
2993 search_regs_saved
= 0;
2998 unwind_set_match_data (Lisp_Object list
)
3000 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3001 return Fset_match_data (list
, Qt
);
3004 /* Called to unwind protect the match data. */
3006 record_unwind_save_match_data (void)
3008 record_unwind_protect (unwind_set_match_data
,
3009 Fmatch_data (Qnil
, Qnil
, Qnil
));
3012 /* Quote a string to deactivate reg-expr chars */
3014 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3015 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3016 (Lisp_Object string
)
3018 register char *in
, *out
, *end
;
3019 register char *temp
;
3020 int backslashes_added
= 0;
3022 CHECK_STRING (string
);
3024 temp
= alloca (SBYTES (string
) * 2);
3026 /* Now copy the data into the new string, inserting escapes. */
3028 in
= SSDATA (string
);
3029 end
= in
+ SBYTES (string
);
3032 for (; in
!= end
; in
++)
3035 || *in
== '*' || *in
== '.' || *in
== '\\'
3036 || *in
== '?' || *in
== '+'
3037 || *in
== '^' || *in
== '$')
3038 *out
++ = '\\', backslashes_added
++;
3042 return make_specified_string (temp
,
3043 SCHARS (string
) + backslashes_added
,
3045 STRING_MULTIBYTE (string
));
3049 syms_of_search (void)
3053 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3055 searchbufs
[i
].buf
.allocated
= 100;
3056 searchbufs
[i
].buf
.buffer
= xmalloc (100);
3057 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3058 searchbufs
[i
].regexp
= Qnil
;
3059 searchbufs
[i
].whitespace_regexp
= Qnil
;
3060 searchbufs
[i
].syntax_table
= Qnil
;
3061 staticpro (&searchbufs
[i
].regexp
);
3062 staticpro (&searchbufs
[i
].whitespace_regexp
);
3063 staticpro (&searchbufs
[i
].syntax_table
);
3064 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3066 searchbuf_head
= &searchbufs
[0];
3068 DEFSYM (Qsearch_failed
, "search-failed");
3069 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3071 Fput (Qsearch_failed
, Qerror_conditions
,
3072 listn (CONSTYPE_PURE
, 2, Qsearch_failed
, Qerror
));
3073 Fput (Qsearch_failed
, Qerror_message
,
3074 build_pure_c_string ("Search failed"));
3076 Fput (Qinvalid_regexp
, Qerror_conditions
,
3077 listn (CONSTYPE_PURE
, 2, Qinvalid_regexp
, Qerror
));
3078 Fput (Qinvalid_regexp
, Qerror_message
,
3079 build_pure_c_string ("Invalid regexp"));
3081 last_thing_searched
= Qnil
;
3082 staticpro (&last_thing_searched
);
3084 saved_last_thing_searched
= Qnil
;
3085 staticpro (&saved_last_thing_searched
);
3087 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3088 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3089 Some commands use this for user-specified regexps.
3090 Spaces that occur inside character classes or repetition operators
3091 or other such regexp constructs are not replaced with this.
3092 A value of nil (which is the normal value) means treat spaces literally. */);
3093 Vsearch_spaces_regexp
= Qnil
;
3095 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3096 doc
: /* Internal use only.
3097 If non-nil, the primitive searching and matching functions
3098 such as `looking-at', `string-match', `re-search-forward', etc.,
3099 do not set the match data. The proper way to use this variable
3100 is to bind it with `let' around a small expression. */);
3101 Vinhibit_changing_match_data
= Qnil
;
3103 defsubr (&Slooking_at
);
3104 defsubr (&Sposix_looking_at
);
3105 defsubr (&Sstring_match
);
3106 defsubr (&Sposix_string_match
);
3107 defsubr (&Ssearch_forward
);
3108 defsubr (&Ssearch_backward
);
3109 defsubr (&Sre_search_forward
);
3110 defsubr (&Sre_search_backward
);
3111 defsubr (&Sposix_search_forward
);
3112 defsubr (&Sposix_search_backward
);
3113 defsubr (&Sreplace_match
);
3114 defsubr (&Smatch_beginning
);
3115 defsubr (&Smatch_end
);
3116 defsubr (&Smatch_data
);
3117 defsubr (&Sset_match_data
);
3118 defsubr (&Sregexp_quote
);