1 /* String search routines for GNU Emacs.
2 Copyright (C) 1985, 1986, 1987, 1993, 1994, 1997, 1998, 1999, 2002, 2003,
3 2004, 2005 Free Software Foundation, Inc.
5 This file is part of GNU Emacs.
7 GNU Emacs is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU Emacs is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Emacs; see the file COPYING. If not, write to
19 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
28 #include "character.h"
29 #include "region-cache.h"
31 #include "blockinput.h"
32 #include "intervals.h"
34 #include <sys/types.h>
37 #define REGEXP_CACHE_SIZE 20
39 /* If the regexp is non-nil, then the buffer contains the compiled form
40 of that regexp, suitable for searching. */
43 struct regexp_cache
*next
;
44 Lisp_Object regexp
, whitespace_regexp
;
45 struct re_pattern_buffer buf
;
47 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
51 /* The instances of that struct. */
52 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
54 /* The head of the linked list; points to the most recently used buffer. */
55 struct regexp_cache
*searchbuf_head
;
58 /* Every call to re_match, etc., must pass &search_regs as the regs
59 argument unless you can show it is unnecessary (i.e., if re_match
60 is certainly going to be called again before region-around-match
63 Since the registers are now dynamically allocated, we need to make
64 sure not to refer to the Nth register before checking that it has
65 been allocated by checking search_regs.num_regs.
67 The regex code keeps track of whether it has allocated the search
68 buffer using bits in the re_pattern_buffer. This means that whenever
69 you compile a new pattern, it completely forgets whether it has
70 allocated any registers, and will allocate new registers the next
71 time you call a searching or matching function. Therefore, we need
72 to call re_set_registers after compiling a new pattern or after
73 setting the match registers, so that the regex functions will be
74 able to free or re-allocate it properly. */
75 static struct re_registers search_regs
;
77 /* The buffer in which the last search was performed, or
78 Qt if the last search was done in a string;
79 Qnil if no searching has been done yet. */
80 static Lisp_Object last_thing_searched
;
82 /* error condition signaled when regexp compile_pattern fails */
84 Lisp_Object Qinvalid_regexp
;
86 Lisp_Object Vsearch_spaces_regexp
;
88 static void set_search_regs ();
89 static void save_search_regs ();
90 static int simple_search ();
91 static int boyer_moore ();
92 static int search_buffer ();
97 error ("Stack overflow in regexp matcher");
100 /* Compile a regexp and signal a Lisp error if anything goes wrong.
101 PATTERN is the pattern to compile.
102 CP is the place to put the result.
103 TRANSLATE is a translation table for ignoring case, or nil for none.
104 REGP is the structure that says where to store the "register"
105 values that will result from matching this pattern.
106 If it is 0, we should compile the pattern not to record any
107 subexpression bounds.
108 POSIX is nonzero if we want full backtracking (POSIX style)
109 for this pattern. 0 means backtrack only enough to get a valid match.
110 MULTIBYTE is nonzero iff a target of match is a multibyte buffer or
113 The behavior also depends on Vsearch_spaces_regexp. */
116 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
117 struct regexp_cache
*cp
;
119 Lisp_Object translate
;
120 struct re_registers
*regp
;
128 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
130 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
131 cp
->buf
.target_multibyte
= multibyte
;
132 cp
->whitespace_regexp
= Vsearch_spaces_regexp
;
134 old
= re_set_syntax (RE_SYNTAX_EMACS
135 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
136 re_set_whitespace_regexp (NILP (Vsearch_spaces_regexp
) ? NULL
137 : SDATA (Vsearch_spaces_regexp
));
139 val
= (char *) re_compile_pattern ((char *) SDATA (pattern
),
140 SBYTES (pattern
), &cp
->buf
);
142 re_set_whitespace_regexp (NULL
);
147 Fsignal (Qinvalid_regexp
, Fcons (build_string (val
), Qnil
));
149 cp
->regexp
= Fcopy_sequence (pattern
);
152 /* Shrink each compiled regexp buffer in the cache
153 to the size actually used right now.
154 This is called from garbage collection. */
157 shrink_regexp_cache ()
159 struct regexp_cache
*cp
;
161 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
163 cp
->buf
.allocated
= cp
->buf
.used
;
165 = (unsigned char *) xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
169 /* Compile a regexp if necessary, but first check to see if there's one in
171 PATTERN is the pattern to compile.
172 TRANSLATE is a translation table for ignoring case, or nil for none.
173 REGP is the structure that says where to store the "register"
174 values that will result from matching this pattern.
175 If it is 0, we should compile the pattern not to record any
176 subexpression bounds.
177 POSIX is nonzero if we want full backtracking (POSIX style)
178 for this pattern. 0 means backtrack only enough to get a valid match. */
180 struct re_pattern_buffer
*
181 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
183 struct re_registers
*regp
;
184 Lisp_Object translate
;
185 int posix
, multibyte
;
187 struct regexp_cache
*cp
, **cpp
;
189 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
192 /* Entries are initialized to nil, and may be set to nil by
193 compile_pattern_1 if the pattern isn't valid. Don't apply
194 string accessors in those cases. However, compile_pattern_1
195 is only applied to the cache entry we pick here to reuse. So
196 nil should never appear before a non-nil entry. */
197 if (NILP (cp
->regexp
))
199 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
200 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
201 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
202 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
203 && cp
->posix
== posix
204 && cp
->buf
.target_multibyte
== multibyte
205 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
)))
208 /* If we're at the end of the cache, compile into the nil cell
209 we found, or the last (least recently used) cell with a
214 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
219 /* When we get here, cp (aka *cpp) contains the compiled pattern,
220 either because we found it in the cache or because we just compiled it.
221 Move it to the front of the queue to mark it as most recently used. */
223 cp
->next
= searchbuf_head
;
226 /* Advise the searching functions about the space we have allocated
227 for register data. */
229 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
234 /* Error condition used for failing searches */
235 Lisp_Object Qsearch_failed
;
241 Fsignal (Qsearch_failed
, Fcons (arg
, Qnil
));
246 looking_at_1 (string
, posix
)
251 unsigned char *p1
, *p2
;
254 struct re_pattern_buffer
*bufp
;
256 if (running_asynch_code
)
259 CHECK_STRING (string
);
260 bufp
= compile_pattern (string
, &search_regs
,
261 (!NILP (current_buffer
->case_fold_search
)
262 ? current_buffer
->case_canon_table
: Qnil
),
264 !NILP (current_buffer
->enable_multibyte_characters
));
267 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
269 /* Get pointers and sizes of the two strings
270 that make up the visible portion of the buffer. */
273 s1
= GPT_BYTE
- BEGV_BYTE
;
275 s2
= ZV_BYTE
- GPT_BYTE
;
279 s2
= ZV_BYTE
- BEGV_BYTE
;
284 s1
= ZV_BYTE
- BEGV_BYTE
;
288 re_match_object
= Qnil
;
290 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
291 PT_BYTE
- BEGV_BYTE
, &search_regs
,
292 ZV_BYTE
- BEGV_BYTE
);
298 val
= (0 <= i
? Qt
: Qnil
);
300 for (i
= 0; i
< search_regs
.num_regs
; i
++)
301 if (search_regs
.start
[i
] >= 0)
304 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
306 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
308 XSETBUFFER (last_thing_searched
, current_buffer
);
312 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
313 doc
: /* Return t if text after point matches regular expression REGEXP.
314 This function modifies the match data that `match-beginning',
315 `match-end' and `match-data' access; save and restore the match
316 data if you want to preserve them. */)
320 return looking_at_1 (regexp
, 0);
323 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
324 doc
: /* Return t if text after point matches regular expression REGEXP.
325 Find the longest match, in accord with Posix regular expression rules.
326 This function modifies the match data that `match-beginning',
327 `match-end' and `match-data' access; save and restore the match
328 data if you want to preserve them. */)
332 return looking_at_1 (regexp
, 1);
336 string_match_1 (regexp
, string
, start
, posix
)
337 Lisp_Object regexp
, string
, start
;
341 struct re_pattern_buffer
*bufp
;
345 if (running_asynch_code
)
348 CHECK_STRING (regexp
);
349 CHECK_STRING (string
);
352 pos
= 0, pos_byte
= 0;
355 int len
= SCHARS (string
);
357 CHECK_NUMBER (start
);
359 if (pos
< 0 && -pos
<= len
)
361 else if (0 > pos
|| pos
> len
)
362 args_out_of_range (string
, start
);
363 pos_byte
= string_char_to_byte (string
, pos
);
366 bufp
= compile_pattern (regexp
, &search_regs
,
367 (!NILP (current_buffer
->case_fold_search
)
368 ? current_buffer
->case_canon_table
: Qnil
),
370 STRING_MULTIBYTE (string
));
372 re_match_object
= string
;
374 val
= re_search (bufp
, (char *) SDATA (string
),
375 SBYTES (string
), pos_byte
,
376 SBYTES (string
) - pos_byte
,
379 last_thing_searched
= Qt
;
382 if (val
< 0) return Qnil
;
384 for (i
= 0; i
< search_regs
.num_regs
; i
++)
385 if (search_regs
.start
[i
] >= 0)
388 = string_byte_to_char (string
, search_regs
.start
[i
]);
390 = string_byte_to_char (string
, search_regs
.end
[i
]);
393 return make_number (string_byte_to_char (string
, val
));
396 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
397 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
398 Matching ignores case if `case-fold-search' is non-nil.
399 If third arg START is non-nil, start search at that index in STRING.
400 For index of first char beyond the match, do (match-end 0).
401 `match-end' and `match-beginning' also give indices of substrings
402 matched by parenthesis constructs in the pattern.
404 You can use the function `match-string' to extract the substrings
405 matched by the parenthesis constructions in REGEXP. */)
406 (regexp
, string
, start
)
407 Lisp_Object regexp
, string
, start
;
409 return string_match_1 (regexp
, string
, start
, 0);
412 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
413 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
414 Find the longest match, in accord with Posix regular expression rules.
415 Case is ignored if `case-fold-search' is non-nil in the current buffer.
416 If third arg START is non-nil, start search at that index in STRING.
417 For index of first char beyond the match, do (match-end 0).
418 `match-end' and `match-beginning' also give indices of substrings
419 matched by parenthesis constructs in the pattern. */)
420 (regexp
, string
, start
)
421 Lisp_Object regexp
, string
, start
;
423 return string_match_1 (regexp
, string
, start
, 1);
426 /* Match REGEXP against STRING, searching all of STRING,
427 and return the index of the match, or negative on failure.
428 This does not clobber the match data. */
431 fast_string_match (regexp
, string
)
432 Lisp_Object regexp
, string
;
435 struct re_pattern_buffer
*bufp
;
437 bufp
= compile_pattern (regexp
, 0, Qnil
,
438 0, STRING_MULTIBYTE (string
));
440 re_match_object
= string
;
442 val
= re_search (bufp
, (char *) SDATA (string
),
449 /* Match REGEXP against STRING, searching all of STRING ignoring case,
450 and return the index of the match, or negative on failure.
451 This does not clobber the match data.
452 We assume that STRING contains single-byte characters. */
454 extern Lisp_Object Vascii_downcase_table
;
457 fast_c_string_match_ignore_case (regexp
, string
)
462 struct re_pattern_buffer
*bufp
;
463 int len
= strlen (string
);
465 regexp
= string_make_unibyte (regexp
);
466 re_match_object
= Qt
;
467 bufp
= compile_pattern (regexp
, 0,
468 Vascii_canon_table
, 0,
471 val
= re_search (bufp
, string
, len
, 0, len
, 0);
476 /* Like fast_string_match but ignore case. */
479 fast_string_match_ignore_case (regexp
, string
)
480 Lisp_Object regexp
, string
;
483 struct re_pattern_buffer
*bufp
;
485 bufp
= compile_pattern (regexp
, 0, Vascii_canon_table
,
486 0, STRING_MULTIBYTE (string
));
488 re_match_object
= string
;
490 val
= re_search (bufp
, (char *) SDATA (string
),
497 /* The newline cache: remembering which sections of text have no newlines. */
499 /* If the user has requested newline caching, make sure it's on.
500 Otherwise, make sure it's off.
501 This is our cheezy way of associating an action with the change of
502 state of a buffer-local variable. */
504 newline_cache_on_off (buf
)
507 if (NILP (buf
->cache_long_line_scans
))
509 /* It should be off. */
510 if (buf
->newline_cache
)
512 free_region_cache (buf
->newline_cache
);
513 buf
->newline_cache
= 0;
518 /* It should be on. */
519 if (buf
->newline_cache
== 0)
520 buf
->newline_cache
= new_region_cache ();
525 /* Search for COUNT instances of the character TARGET between START and END.
527 If COUNT is positive, search forwards; END must be >= START.
528 If COUNT is negative, search backwards for the -COUNTth instance;
529 END must be <= START.
530 If COUNT is zero, do anything you please; run rogue, for all I care.
532 If END is zero, use BEGV or ZV instead, as appropriate for the
533 direction indicated by COUNT.
535 If we find COUNT instances, set *SHORTAGE to zero, and return the
536 position past the COUNTth match. Note that for reverse motion
537 this is not the same as the usual convention for Emacs motion commands.
539 If we don't find COUNT instances before reaching END, set *SHORTAGE
540 to the number of TARGETs left unfound, and return END.
542 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
543 except when inside redisplay. */
546 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
553 struct region_cache
*newline_cache
;
564 if (! end
) end
= BEGV
;
567 newline_cache_on_off (current_buffer
);
568 newline_cache
= current_buffer
->newline_cache
;
573 immediate_quit
= allow_quit
;
578 /* Our innermost scanning loop is very simple; it doesn't know
579 about gaps, buffer ends, or the newline cache. ceiling is
580 the position of the last character before the next such
581 obstacle --- the last character the dumb search loop should
583 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
584 int start_byte
= CHAR_TO_BYTE (start
);
587 /* If we're looking for a newline, consult the newline cache
588 to see where we can avoid some scanning. */
589 if (target
== '\n' && newline_cache
)
593 while (region_cache_forward
594 (current_buffer
, newline_cache
, start_byte
, &next_change
))
595 start_byte
= next_change
;
596 immediate_quit
= allow_quit
;
598 /* START should never be after END. */
599 if (start_byte
> ceiling_byte
)
600 start_byte
= ceiling_byte
;
602 /* Now the text after start is an unknown region, and
603 next_change is the position of the next known region. */
604 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
607 /* The dumb loop can only scan text stored in contiguous
608 bytes. BUFFER_CEILING_OF returns the last character
609 position that is contiguous, so the ceiling is the
610 position after that. */
611 tem
= BUFFER_CEILING_OF (start_byte
);
612 ceiling_byte
= min (tem
, ceiling_byte
);
615 /* The termination address of the dumb loop. */
616 register unsigned char *ceiling_addr
617 = BYTE_POS_ADDR (ceiling_byte
) + 1;
618 register unsigned char *cursor
619 = BYTE_POS_ADDR (start_byte
);
620 unsigned char *base
= cursor
;
622 while (cursor
< ceiling_addr
)
624 unsigned char *scan_start
= cursor
;
627 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
630 /* If we're looking for newlines, cache the fact that
631 the region from start to cursor is free of them. */
632 if (target
== '\n' && newline_cache
)
633 know_region_cache (current_buffer
, newline_cache
,
634 start_byte
+ scan_start
- base
,
635 start_byte
+ cursor
- base
);
637 /* Did we find the target character? */
638 if (cursor
< ceiling_addr
)
643 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
649 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
655 /* The last character to check before the next obstacle. */
656 int ceiling_byte
= CHAR_TO_BYTE (end
);
657 int start_byte
= CHAR_TO_BYTE (start
);
660 /* Consult the newline cache, if appropriate. */
661 if (target
== '\n' && newline_cache
)
665 while (region_cache_backward
666 (current_buffer
, newline_cache
, start_byte
, &next_change
))
667 start_byte
= next_change
;
668 immediate_quit
= allow_quit
;
670 /* Start should never be at or before end. */
671 if (start_byte
<= ceiling_byte
)
672 start_byte
= ceiling_byte
+ 1;
674 /* Now the text before start is an unknown region, and
675 next_change is the position of the next known region. */
676 ceiling_byte
= max (next_change
, ceiling_byte
);
679 /* Stop scanning before the gap. */
680 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
681 ceiling_byte
= max (tem
, ceiling_byte
);
684 /* The termination address of the dumb loop. */
685 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
686 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
687 unsigned char *base
= cursor
;
689 while (cursor
>= ceiling_addr
)
691 unsigned char *scan_start
= cursor
;
693 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
696 /* If we're looking for newlines, cache the fact that
697 the region from after the cursor to start is free of them. */
698 if (target
== '\n' && newline_cache
)
699 know_region_cache (current_buffer
, newline_cache
,
700 start_byte
+ cursor
- base
,
701 start_byte
+ scan_start
- base
);
703 /* Did we find the target character? */
704 if (cursor
>= ceiling_addr
)
709 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
715 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
721 *shortage
= count
* direction
;
725 /* Search for COUNT instances of a line boundary, which means either a
726 newline or (if selective display enabled) a carriage return.
727 Start at START. If COUNT is negative, search backwards.
729 We report the resulting position by calling TEMP_SET_PT_BOTH.
731 If we find COUNT instances. we position after (always after,
732 even if scanning backwards) the COUNTth match, and return 0.
734 If we don't find COUNT instances before reaching the end of the
735 buffer (or the beginning, if scanning backwards), we return
736 the number of line boundaries left unfound, and position at
737 the limit we bumped up against.
739 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
740 except in special cases. */
743 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
744 int start
, start_byte
;
745 int limit
, limit_byte
;
749 int direction
= ((count
> 0) ? 1 : -1);
751 register unsigned char *cursor
;
754 register int ceiling
;
755 register unsigned char *ceiling_addr
;
757 int old_immediate_quit
= immediate_quit
;
759 /* The code that follows is like scan_buffer
760 but checks for either newline or carriage return. */
765 start_byte
= CHAR_TO_BYTE (start
);
769 while (start_byte
< limit_byte
)
771 ceiling
= BUFFER_CEILING_OF (start_byte
);
772 ceiling
= min (limit_byte
- 1, ceiling
);
773 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
774 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
777 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
780 if (cursor
!= ceiling_addr
)
784 immediate_quit
= old_immediate_quit
;
785 start_byte
= start_byte
+ cursor
- base
+ 1;
786 start
= BYTE_TO_CHAR (start_byte
);
787 TEMP_SET_PT_BOTH (start
, start_byte
);
791 if (++cursor
== ceiling_addr
)
797 start_byte
+= cursor
- base
;
802 while (start_byte
> limit_byte
)
804 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
805 ceiling
= max (limit_byte
, ceiling
);
806 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
807 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
810 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
813 if (cursor
!= ceiling_addr
)
817 immediate_quit
= old_immediate_quit
;
818 /* Return the position AFTER the match we found. */
819 start_byte
= start_byte
+ cursor
- base
+ 1;
820 start
= BYTE_TO_CHAR (start_byte
);
821 TEMP_SET_PT_BOTH (start
, start_byte
);
828 /* Here we add 1 to compensate for the last decrement
829 of CURSOR, which took it past the valid range. */
830 start_byte
+= cursor
- base
+ 1;
834 TEMP_SET_PT_BOTH (limit
, limit_byte
);
835 immediate_quit
= old_immediate_quit
;
837 return count
* direction
;
841 find_next_newline_no_quit (from
, cnt
)
842 register int from
, cnt
;
844 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
847 /* Like find_next_newline, but returns position before the newline,
848 not after, and only search up to TO. This isn't just
849 find_next_newline (...)-1, because you might hit TO. */
852 find_before_next_newline (from
, to
, cnt
)
856 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
864 /* Subroutines of Lisp buffer search functions. */
867 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
868 Lisp_Object string
, bound
, noerror
, count
;
879 CHECK_NUMBER (count
);
883 CHECK_STRING (string
);
887 lim
= ZV
, lim_byte
= ZV_BYTE
;
889 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
893 CHECK_NUMBER_COERCE_MARKER (bound
);
895 if (n
> 0 ? lim
< PT
: lim
> PT
)
896 error ("Invalid search bound (wrong side of point)");
898 lim
= ZV
, lim_byte
= ZV_BYTE
;
900 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
902 lim_byte
= CHAR_TO_BYTE (lim
);
905 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
906 (!NILP (current_buffer
->case_fold_search
)
907 ? current_buffer
->case_canon_table
909 (!NILP (current_buffer
->case_fold_search
)
910 ? current_buffer
->case_eqv_table
916 return signal_failure (string
);
917 if (!EQ (noerror
, Qt
))
919 if (lim
< BEGV
|| lim
> ZV
)
921 SET_PT_BOTH (lim
, lim_byte
);
923 #if 0 /* This would be clean, but maybe programs depend on
924 a value of nil here. */
932 if (np
< BEGV
|| np
> ZV
)
937 return make_number (np
);
940 /* Return 1 if REGEXP it matches just one constant string. */
943 trivial_regexp_p (regexp
)
946 int len
= SBYTES (regexp
);
947 unsigned char *s
= SDATA (regexp
);
952 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
959 case '|': case '(': case ')': case '`': case '\'': case 'b':
960 case 'B': case '<': case '>': case 'w': case 'W': case 's':
961 case 'S': case '=': case '{': case '}': case '_':
962 case 'c': case 'C': /* for categoryspec and notcategoryspec */
963 case '1': case '2': case '3': case '4': case '5':
964 case '6': case '7': case '8': case '9':
972 /* Search for the n'th occurrence of STRING in the current buffer,
973 starting at position POS and stopping at position LIM,
974 treating STRING as a literal string if RE is false or as
975 a regular expression if RE is true.
977 If N is positive, searching is forward and LIM must be greater than POS.
978 If N is negative, searching is backward and LIM must be less than POS.
980 Returns -x if x occurrences remain to be found (x > 0),
981 or else the position at the beginning of the Nth occurrence
982 (if searching backward) or the end (if searching forward).
984 POSIX is nonzero if we want full backtracking (POSIX style)
985 for this pattern. 0 means backtrack only enough to get a valid match. */
987 #define TRANSLATE(out, trt, d) \
993 temp = Faref (trt, make_number (d)); \
994 if (INTEGERP (temp)) \
1005 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
1006 RE
, trt
, inverse_trt
, posix
)
1015 Lisp_Object inverse_trt
;
1018 int len
= SCHARS (string
);
1019 int len_byte
= SBYTES (string
);
1022 if (running_asynch_code
)
1023 save_search_regs ();
1025 /* Searching 0 times means don't move. */
1026 /* Null string is found at starting position. */
1027 if (len
== 0 || n
== 0)
1029 set_search_regs (pos_byte
, 0);
1033 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1035 unsigned char *p1
, *p2
;
1037 struct re_pattern_buffer
*bufp
;
1039 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
,
1040 !NILP (current_buffer
->enable_multibyte_characters
));
1042 immediate_quit
= 1; /* Quit immediately if user types ^G,
1043 because letting this function finish
1044 can take too long. */
1045 QUIT
; /* Do a pending quit right away,
1046 to avoid paradoxical behavior */
1047 /* Get pointers and sizes of the two strings
1048 that make up the visible portion of the buffer. */
1051 s1
= GPT_BYTE
- BEGV_BYTE
;
1053 s2
= ZV_BYTE
- GPT_BYTE
;
1057 s2
= ZV_BYTE
- BEGV_BYTE
;
1062 s1
= ZV_BYTE
- BEGV_BYTE
;
1065 re_match_object
= Qnil
;
1070 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1071 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1073 /* Don't allow match past current point */
1074 pos_byte
- BEGV_BYTE
);
1077 matcher_overflow ();
1081 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1082 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1083 if (search_regs
.start
[i
] >= 0)
1085 search_regs
.start
[i
]
1086 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1088 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1090 XSETBUFFER (last_thing_searched
, current_buffer
);
1091 /* Set pos to the new position. */
1092 pos
= search_regs
.start
[0];
1104 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1105 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1107 lim_byte
- BEGV_BYTE
);
1110 matcher_overflow ();
1114 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1115 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1116 if (search_regs
.start
[i
] >= 0)
1118 search_regs
.start
[i
]
1119 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1121 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1123 XSETBUFFER (last_thing_searched
, current_buffer
);
1124 pos
= search_regs
.end
[0];
1136 else /* non-RE case */
1138 unsigned char *raw_pattern
, *pat
;
1139 int raw_pattern_size
;
1140 int raw_pattern_size_byte
;
1141 unsigned char *patbuf
;
1142 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1143 unsigned char *base_pat
= SDATA (string
);
1144 /* Set to positive if we find a non-ASCII char that need
1145 translation. Otherwise set to zero later. */
1147 int boyer_moore_ok
= 1;
1149 /* MULTIBYTE says whether the text to be searched is multibyte.
1150 We must convert PATTERN to match that, or we will not really
1151 find things right. */
1153 if (multibyte
== STRING_MULTIBYTE (string
))
1155 raw_pattern
= (unsigned char *) SDATA (string
);
1156 raw_pattern_size
= SCHARS (string
);
1157 raw_pattern_size_byte
= SBYTES (string
);
1161 raw_pattern_size
= SCHARS (string
);
1162 raw_pattern_size_byte
1163 = count_size_as_multibyte (SDATA (string
),
1165 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1166 copy_text (SDATA (string
), raw_pattern
,
1167 SCHARS (string
), 0, 1);
1171 /* Converting multibyte to single-byte.
1173 ??? Perhaps this conversion should be done in a special way
1174 by subtracting nonascii-insert-offset from each non-ASCII char,
1175 so that only the multibyte chars which really correspond to
1176 the chosen single-byte character set can possibly match. */
1177 raw_pattern_size
= SCHARS (string
);
1178 raw_pattern_size_byte
= SCHARS (string
);
1179 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1180 copy_text (SDATA (string
), raw_pattern
,
1181 SBYTES (string
), 1, 0);
1184 /* Copy and optionally translate the pattern. */
1185 len
= raw_pattern_size
;
1186 len_byte
= raw_pattern_size_byte
;
1187 patbuf
= (unsigned char *) alloca (len
* MAX_MULTIBYTE_LENGTH
);
1189 base_pat
= raw_pattern
;
1192 /* Fill patbuf by translated characters in STRING while
1193 checking if we can use boyer-moore search. If TRT is
1194 non-nil, we can use boyer-moore search only if TRT can be
1195 represented by the byte array of 256 elements. For that,
1196 all non-ASCII case-equivalents of all case-senstive
1197 characters in STRING must belong to the same charset and
1202 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1203 int c
, translated
, inverse
;
1204 int in_charlen
, charlen
;
1206 /* If we got here and the RE flag is set, it's because we're
1207 dealing with a regexp known to be trivial, so the backslash
1208 just quotes the next character. */
1209 if (RE
&& *base_pat
== '\\')
1216 c
= STRING_CHAR_AND_LENGTH (base_pat
, len_byte
, in_charlen
);
1221 charlen
= in_charlen
;
1225 /* Translate the character. */
1226 TRANSLATE (translated
, trt
, c
);
1227 charlen
= CHAR_STRING (translated
, str_base
);
1230 /* Check if C has any other case-equivalents. */
1231 TRANSLATE (inverse
, inverse_trt
, c
);
1232 /* If so, check if we can use boyer-moore. */
1233 if (c
!= inverse
&& boyer_moore_ok
)
1235 /* Check if all equivalents belong to the same
1236 group of characters. Note that the check of C
1237 itself is done by the last iteration. */
1238 int this_char_base
= -1;
1240 while (boyer_moore_ok
)
1242 if (ASCII_BYTE_P (inverse
))
1244 if (this_char_base
> 0)
1250 char_base
= this_char_base
;
1253 else if (CHAR_BYTE8_P (inverse
))
1254 /* Boyer-moore search can't handle a
1255 translation of an eight-bit
1258 else if (this_char_base
< 0)
1260 this_char_base
= inverse
& ~0x3F;
1262 char_base
= this_char_base
;
1263 else if (char_base
> 0
1264 && this_char_base
!= char_base
)
1267 else if ((inverse
& ~0x3F) != this_char_base
)
1271 TRANSLATE (inverse
, inverse_trt
, inverse
);
1278 /* Store this character into the translated pattern. */
1279 bcopy (str
, pat
, charlen
);
1281 base_pat
+= in_charlen
;
1282 len_byte
-= in_charlen
;
1287 /* Unibyte buffer. */
1293 /* If we got here and the RE flag is set, it's because we're
1294 dealing with a regexp known to be trivial, so the backslash
1295 just quotes the next character. */
1296 if (RE
&& *base_pat
== '\\')
1303 TRANSLATE (translated
, trt
, c
);
1304 *pat
++ = translated
;
1308 len_byte
= pat
- patbuf
;
1309 len
= raw_pattern_size
;
1310 pat
= base_pat
= patbuf
;
1313 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1314 pos
, pos_byte
, lim
, lim_byte
,
1317 return simple_search (n
, pat
, len
, len_byte
, trt
,
1318 pos
, pos_byte
, lim
, lim_byte
);
1322 /* Do a simple string search N times for the string PAT,
1323 whose length is LEN/LEN_BYTE,
1324 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1325 TRT is the translation table.
1327 Return the character position where the match is found.
1328 Otherwise, if M matches remained to be found, return -M.
1330 This kind of search works regardless of what is in PAT and
1331 regardless of what is in TRT. It is used in cases where
1332 boyer_moore cannot work. */
1335 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1343 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1344 int forward
= n
> 0;
1345 /* Number of buffer bytes matched. Note that this may be different
1346 from len_byte in a multibyte buffer. */
1349 if (lim
> pos
&& multibyte
)
1354 /* Try matching at position POS. */
1356 int this_pos_byte
= pos_byte
;
1358 int this_len_byte
= len_byte
;
1359 unsigned char *p
= pat
;
1360 if (pos
+ len
> lim
)
1363 while (this_len
> 0)
1365 int charlen
, buf_charlen
;
1368 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1369 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1370 ZV_BYTE
- this_pos_byte
,
1372 TRANSLATE (buf_ch
, trt
, buf_ch
);
1374 if (buf_ch
!= pat_ch
)
1377 this_len_byte
-= charlen
;
1381 this_pos_byte
+= buf_charlen
;
1387 match_byte
= this_pos_byte
- pos_byte
;
1389 pos_byte
+= match_byte
;
1393 INC_BOTH (pos
, pos_byte
);
1403 /* Try matching at position POS. */
1406 unsigned char *p
= pat
;
1408 if (pos
+ len
> lim
)
1411 while (this_len
> 0)
1414 int buf_ch
= FETCH_BYTE (this_pos
);
1415 TRANSLATE (buf_ch
, trt
, buf_ch
);
1417 if (buf_ch
!= pat_ch
)
1436 /* Backwards search. */
1437 else if (lim
< pos
&& multibyte
)
1442 /* Try matching at position POS. */
1443 int this_pos
= pos
- len
;
1446 int this_len_byte
= len_byte
;
1447 unsigned char *p
= pat
;
1449 if (pos
- len
< lim
)
1451 this_pos_byte
= CHAR_TO_BYTE (this_pos
);
1452 match_byte
= pos_byte
- this_pos_byte
;
1454 while (this_len
> 0)
1456 int charlen
, buf_charlen
;
1459 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1460 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1461 ZV_BYTE
- this_pos_byte
,
1463 TRANSLATE (buf_ch
, trt
, buf_ch
);
1465 if (buf_ch
!= pat_ch
)
1468 this_len_byte
-= charlen
;
1471 this_pos_byte
+= buf_charlen
;
1478 pos_byte
-= match_byte
;
1482 DEC_BOTH (pos
, pos_byte
);
1492 /* Try matching at position POS. */
1493 int this_pos
= pos
- len
;
1495 unsigned char *p
= pat
;
1497 if (pos
- len
< lim
)
1500 while (this_len
> 0)
1503 int buf_ch
= FETCH_BYTE (this_pos
);
1504 TRANSLATE (buf_ch
, trt
, buf_ch
);
1506 if (buf_ch
!= pat_ch
)
1529 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1531 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1541 /* Do Boyer-Moore search N times for the string BASE_PAT,
1542 whose length is LEN/LEN_BYTE,
1543 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1544 DIRECTION says which direction we search in.
1545 TRT and INVERSE_TRT are translation tables.
1546 Characters in PAT are already translated by TRT.
1548 This kind of search works if all the characters in BASE_PAT that
1549 have nontrivial translation are the same aside from the last byte.
1550 This makes it possible to translate just the last byte of a
1551 character, and do so after just a simple test of the context.
1552 CHAR_BASE is nonzero iff there is such a non-ASCII character.
1554 If that criterion is not satisfied, do not call this function. */
1557 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1558 pos
, pos_byte
, lim
, lim_byte
, char_base
)
1560 unsigned char *base_pat
;
1563 Lisp_Object inverse_trt
;
1568 int direction
= ((n
> 0) ? 1 : -1);
1569 register int dirlen
;
1570 int infinity
, limit
, stride_for_teases
= 0;
1571 register int *BM_tab
;
1573 register unsigned char *cursor
, *p_limit
;
1575 unsigned char *pat
, *pat_end
;
1576 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1578 unsigned char simple_translate
[0400];
1579 /* These are set to the preceding bytes of a byte to be translated
1580 if char_base is nonzero. As the maximum byte length of a
1581 multibyte character is 5, we have to check at most four previous
1583 int translate_prev_byte1
= 0;
1584 int translate_prev_byte2
= 0;
1585 int translate_prev_byte3
= 0;
1586 int translate_prev_byte4
= 0;
1589 int BM_tab_space
[0400];
1590 BM_tab
= &BM_tab_space
[0];
1592 BM_tab
= (int *) alloca (0400 * sizeof (int));
1594 /* The general approach is that we are going to maintain that we know */
1595 /* the first (closest to the present position, in whatever direction */
1596 /* we're searching) character that could possibly be the last */
1597 /* (furthest from present position) character of a valid match. We */
1598 /* advance the state of our knowledge by looking at that character */
1599 /* and seeing whether it indeed matches the last character of the */
1600 /* pattern. If it does, we take a closer look. If it does not, we */
1601 /* move our pointer (to putative last characters) as far as is */
1602 /* logically possible. This amount of movement, which I call a */
1603 /* stride, will be the length of the pattern if the actual character */
1604 /* appears nowhere in the pattern, otherwise it will be the distance */
1605 /* from the last occurrence of that character to the end of the */
1607 /* As a coding trick, an enormous stride is coded into the table for */
1608 /* characters that match the last character. This allows use of only */
1609 /* a single test, a test for having gone past the end of the */
1610 /* permissible match region, to test for both possible matches (when */
1611 /* the stride goes past the end immediately) and failure to */
1612 /* match (where you get nudged past the end one stride at a time). */
1614 /* Here we make a "mickey mouse" BM table. The stride of the search */
1615 /* is determined only by the last character of the putative match. */
1616 /* If that character does not match, we will stride the proper */
1617 /* distance to propose a match that superimposes it on the last */
1618 /* instance of a character that matches it (per trt), or misses */
1619 /* it entirely if there is none. */
1621 dirlen
= len_byte
* direction
;
1622 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1624 /* Record position after the end of the pattern. */
1625 pat_end
= base_pat
+ len_byte
;
1626 /* BASE_PAT points to a character that we start scanning from.
1627 It is the first character in a forward search,
1628 the last character in a backward search. */
1630 base_pat
= pat_end
- 1;
1632 BM_tab_base
= BM_tab
;
1634 j
= dirlen
; /* to get it in a register */
1635 /* A character that does not appear in the pattern induces a */
1636 /* stride equal to the pattern length. */
1637 while (BM_tab_base
!= BM_tab
)
1645 /* We use this for translation, instead of TRT itself.
1646 We fill this in to handle the characters that actually
1647 occur in the pattern. Others don't matter anyway! */
1648 bzero (simple_translate
, sizeof simple_translate
);
1649 for (i
= 0; i
< 0400; i
++)
1650 simple_translate
[i
] = i
;
1654 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1655 byte following them are the target of translation. */
1656 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1657 int len
= CHAR_STRING (char_base
, str
);
1659 translate_prev_byte1
= str
[len
- 2];
1662 translate_prev_byte2
= str
[len
- 3];
1665 translate_prev_byte3
= str
[len
- 4];
1667 translate_prev_byte4
= str
[len
- 5];
1673 while (i
!= infinity
)
1675 unsigned char *ptr
= base_pat
+ i
;
1681 /* If the byte currently looking at is the last of a
1682 character to check case-equivalents, set CH to that
1683 character. An ASCII character and a non-ASCII character
1684 matching with CHAR_BASE are to be checked. */
1687 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1690 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1692 unsigned char *charstart
= ptr
- 1;
1694 while (! (CHAR_HEAD_P (*charstart
)))
1696 ch
= STRING_CHAR (charstart
, ptr
- charstart
+ 1);
1697 if (char_base
!= (ch
& ~0x3F))
1702 j
= (ch
& 0x3F) | 0200;
1707 stride_for_teases
= BM_tab
[j
];
1709 BM_tab
[j
] = dirlen
- i
;
1710 /* A translation table is accompanied by its inverse -- see */
1711 /* comment following downcase_table for details */
1714 int starting_ch
= ch
;
1719 TRANSLATE (ch
, inverse_trt
, ch
);
1721 j
= (ch
& 0x3F) | 0200;
1725 /* For all the characters that map into CH,
1726 set up simple_translate to map the last byte
1728 simple_translate
[j
] = starting_j
;
1729 if (ch
== starting_ch
)
1731 BM_tab
[j
] = dirlen
- i
;
1740 stride_for_teases
= BM_tab
[j
];
1741 BM_tab
[j
] = dirlen
- i
;
1743 /* stride_for_teases tells how much to stride if we get a */
1744 /* match on the far character but are subsequently */
1745 /* disappointed, by recording what the stride would have been */
1746 /* for that character if the last character had been */
1749 infinity
= dirlen
- infinity
;
1750 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1751 /* loop invariant - POS_BYTE points at where last char (first
1752 char if reverse) of pattern would align in a possible match. */
1756 unsigned char *tail_end_ptr
;
1758 /* It's been reported that some (broken) compiler thinks that
1759 Boolean expressions in an arithmetic context are unsigned.
1760 Using an explicit ?1:0 prevents this. */
1761 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1763 return (n
* (0 - direction
));
1764 /* First we do the part we can by pointers (maybe nothing) */
1767 limit
= pos_byte
- dirlen
+ direction
;
1770 limit
= BUFFER_CEILING_OF (limit
);
1771 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1772 can take on without hitting edge of buffer or the gap. */
1773 limit
= min (limit
, pos_byte
+ 20000);
1774 limit
= min (limit
, lim_byte
- 1);
1778 limit
= BUFFER_FLOOR_OF (limit
);
1779 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1780 can take on without hitting edge of buffer or the gap. */
1781 limit
= max (limit
, pos_byte
- 20000);
1782 limit
= max (limit
, lim_byte
);
1784 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1785 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1787 if ((limit
- pos_byte
) * direction
> 20)
1791 p_limit
= BYTE_POS_ADDR (limit
);
1792 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1793 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1794 while (1) /* use one cursor setting as long as i can */
1796 if (direction
> 0) /* worth duplicating */
1798 /* Use signed comparison if appropriate
1799 to make cursor+infinity sure to be > p_limit.
1800 Assuming that the buffer lies in a range of addresses
1801 that are all "positive" (as ints) or all "negative",
1802 either kind of comparison will work as long
1803 as we don't step by infinity. So pick the kind
1804 that works when we do step by infinity. */
1805 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1806 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1807 cursor
+= BM_tab
[*cursor
];
1809 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1810 cursor
+= BM_tab
[*cursor
];
1814 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1815 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1816 cursor
+= BM_tab
[*cursor
];
1818 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1819 cursor
+= BM_tab
[*cursor
];
1821 /* If you are here, cursor is beyond the end of the searched region. */
1822 /* This can happen if you match on the far character of the pattern, */
1823 /* because the "stride" of that character is infinity, a number able */
1824 /* to throw you well beyond the end of the search. It can also */
1825 /* happen if you fail to match within the permitted region and would */
1826 /* otherwise try a character beyond that region */
1827 if ((cursor
- p_limit
) * direction
<= len_byte
)
1828 break; /* a small overrun is genuine */
1829 cursor
-= infinity
; /* large overrun = hit */
1830 i
= dirlen
- direction
;
1833 while ((i
-= direction
) + direction
!= 0)
1836 cursor
-= direction
;
1837 /* Translate only the last byte of a character. */
1839 || ((cursor
== tail_end_ptr
1840 || CHAR_HEAD_P (cursor
[1]))
1841 && (CHAR_HEAD_P (cursor
[0])
1842 /* Check if this is the last byte of
1843 a translable character. */
1844 || (translate_prev_byte1
== cursor
[-1]
1845 && (CHAR_HEAD_P (translate_prev_byte1
)
1846 || (translate_prev_byte2
== cursor
[-2]
1847 && (CHAR_HEAD_P (translate_prev_byte2
)
1848 || (translate_prev_byte3
== cursor
[-3]))))))))
1849 ch
= simple_translate
[*cursor
];
1858 while ((i
-= direction
) + direction
!= 0)
1860 cursor
-= direction
;
1861 if (pat
[i
] != *cursor
)
1865 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1866 if (i
+ direction
== 0)
1870 cursor
-= direction
;
1872 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1873 ? 1 - len_byte
: 0);
1874 set_search_regs (position
, len_byte
);
1876 if ((n
-= direction
) != 0)
1877 cursor
+= dirlen
; /* to resume search */
1879 return ((direction
> 0)
1880 ? search_regs
.end
[0] : search_regs
.start
[0]);
1883 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1885 pos_byte
+= cursor
- p2
;
1888 /* Now we'll pick up a clump that has to be done the hard */
1889 /* way because it covers a discontinuity */
1891 limit
= ((direction
> 0)
1892 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1893 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1894 limit
= ((direction
> 0)
1895 ? min (limit
+ len_byte
, lim_byte
- 1)
1896 : max (limit
- len_byte
, lim_byte
));
1897 /* LIMIT is now the last value POS_BYTE can have
1898 and still be valid for a possible match. */
1901 /* This loop can be coded for space rather than */
1902 /* speed because it will usually run only once. */
1903 /* (the reach is at most len + 21, and typically */
1904 /* does not exceed len) */
1905 while ((limit
- pos_byte
) * direction
>= 0)
1906 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
1907 /* now run the same tests to distinguish going off the */
1908 /* end, a match or a phony match. */
1909 if ((pos_byte
- limit
) * direction
<= len_byte
)
1910 break; /* ran off the end */
1911 /* Found what might be a match.
1912 Set POS_BYTE back to last (first if reverse) pos. */
1913 pos_byte
-= infinity
;
1914 i
= dirlen
- direction
;
1915 while ((i
-= direction
) + direction
!= 0)
1919 pos_byte
-= direction
;
1920 ptr
= BYTE_POS_ADDR (pos_byte
);
1921 /* Translate only the last byte of a character. */
1923 || ((ptr
== tail_end_ptr
1924 || CHAR_HEAD_P (ptr
[1]))
1925 && (CHAR_HEAD_P (ptr
[0])
1926 /* Check if this is the last byte of a
1927 translable character. */
1928 || (translate_prev_byte1
== ptr
[-1]
1929 && (CHAR_HEAD_P (translate_prev_byte1
)
1930 || (translate_prev_byte2
== ptr
[-2]
1931 && (CHAR_HEAD_P (translate_prev_byte2
)
1932 || translate_prev_byte3
== ptr
[-3])))))))
1933 ch
= simple_translate
[*ptr
];
1939 /* Above loop has moved POS_BYTE part or all the way
1940 back to the first pos (last pos if reverse).
1941 Set it once again at the last (first if reverse) char. */
1942 pos_byte
+= dirlen
- i
- direction
;
1943 if (i
+ direction
== 0)
1946 pos_byte
-= direction
;
1948 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
1950 set_search_regs (position
, len_byte
);
1952 if ((n
-= direction
) != 0)
1953 pos_byte
+= dirlen
; /* to resume search */
1955 return ((direction
> 0)
1956 ? search_regs
.end
[0] : search_regs
.start
[0]);
1959 pos_byte
+= stride_for_teases
;
1962 /* We have done one clump. Can we continue? */
1963 if ((lim_byte
- pos_byte
) * direction
< 0)
1964 return ((0 - n
) * direction
);
1966 return BYTE_TO_CHAR (pos_byte
);
1969 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
1970 for the overall match just found in the current buffer.
1971 Also clear out the match data for registers 1 and up. */
1974 set_search_regs (beg_byte
, nbytes
)
1975 int beg_byte
, nbytes
;
1979 /* Make sure we have registers in which to store
1980 the match position. */
1981 if (search_regs
.num_regs
== 0)
1983 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1984 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1985 search_regs
.num_regs
= 2;
1988 /* Clear out the other registers. */
1989 for (i
= 1; i
< search_regs
.num_regs
; i
++)
1991 search_regs
.start
[i
] = -1;
1992 search_regs
.end
[i
] = -1;
1995 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
1996 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
1997 XSETBUFFER (last_thing_searched
, current_buffer
);
2000 /* Given a string of words separated by word delimiters,
2001 compute a regexp that matches those exact words
2002 separated by arbitrary punctuation. */
2008 register unsigned char *p
, *o
;
2009 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
2014 CHECK_STRING (string
);
2016 len
= SCHARS (string
);
2018 for (i
= 0, i_byte
= 0; i
< len
; )
2022 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
2024 if (SYNTAX (c
) != Sword
)
2027 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
2034 if (SYNTAX (prev_c
) == Sword
)
2037 return empty_string
;
2039 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
2040 if (STRING_MULTIBYTE (string
))
2041 val
= make_uninit_multibyte_string (len
+ adjust
,
2045 val
= make_uninit_string (len
+ adjust
);
2052 for (i
= 0, i_byte
= 0; i
< len
; )
2055 int i_byte_orig
= i_byte
;
2057 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
2059 if (SYNTAX (c
) == Sword
)
2061 bcopy (SDATA (string
) + i_byte_orig
, o
,
2062 i_byte
- i_byte_orig
);
2063 o
+= i_byte
- i_byte_orig
;
2065 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
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 is repeat count--search for successive occurrences.
2093 Search case-sensitivity is determined by the value of the variable
2094 `case-fold-search', which see.
2096 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2097 (string
, bound
, noerror
, count
)
2098 Lisp_Object string
, bound
, noerror
, count
;
2100 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2103 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2104 doc
: /* Search forward from point for STRING.
2105 Set point to the end of the occurrence found, and return point.
2106 An optional second argument bounds the search; it is a buffer position.
2107 The match found must not extend after that position. nil is equivalent
2109 Optional third argument, if t, means if fail just return nil (no error).
2110 If not nil and not t, move to limit of search and return nil.
2111 Optional fourth argument is repeat count--search for successive occurrences.
2113 Search case-sensitivity is determined by the value of the variable
2114 `case-fold-search', which see.
2116 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2117 (string
, bound
, noerror
, count
)
2118 Lisp_Object string
, bound
, noerror
, count
;
2120 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2123 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2124 "sWord search backward: ",
2125 doc
: /* Search backward from point for STRING, ignoring differences in punctuation.
2126 Set point to the beginning of the occurrence found, and return point.
2127 An optional second argument bounds the search; it is a buffer position.
2128 The match found must not extend before that position.
2129 Optional third argument, if t, means if fail just return nil (no error).
2130 If not nil and not t, move to limit of search and return nil.
2131 Optional fourth argument is repeat count--search for successive occurrences. */)
2132 (string
, bound
, noerror
, count
)
2133 Lisp_Object string
, bound
, noerror
, count
;
2135 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
2138 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2140 doc
: /* Search forward from point for STRING, ignoring differences in punctuation.
2141 Set point to the end of the occurrence found, and return point.
2142 An optional second argument bounds the search; it is a buffer position.
2143 The match found must not extend after that position.
2144 Optional third argument, if t, means if fail just return nil (no error).
2145 If not nil and not t, move to limit of search and return nil.
2146 Optional fourth argument is repeat count--search for successive occurrences. */)
2147 (string
, bound
, noerror
, count
)
2148 Lisp_Object string
, bound
, noerror
, count
;
2150 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
2153 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2154 "sRE search backward: ",
2155 doc
: /* Search backward from point for match for regular expression REGEXP.
2156 Set point to the beginning of the match, and return point.
2157 The match found is the one starting last in the buffer
2158 and yet ending before the origin of the search.
2159 An optional second argument bounds the search; it is a buffer position.
2160 The match found must start at or after that position.
2161 Optional third argument, if t, means if fail just return nil (no error).
2162 If not nil and not t, move to limit of search and return nil.
2163 Optional fourth argument is repeat count--search for successive occurrences.
2164 See also the functions `match-beginning', `match-end', `match-string',
2165 and `replace-match'. */)
2166 (regexp
, bound
, noerror
, count
)
2167 Lisp_Object regexp
, bound
, noerror
, count
;
2169 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2172 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2174 doc
: /* Search forward from point for regular expression REGEXP.
2175 Set point to the end of the occurrence found, and return point.
2176 An optional second argument bounds the search; it is a buffer position.
2177 The match found must not extend after that position.
2178 Optional third argument, if t, means if fail just return nil (no error).
2179 If not nil and not t, move to limit of search and return nil.
2180 Optional fourth argument is repeat count--search for successive occurrences.
2181 See also the functions `match-beginning', `match-end', `match-string',
2182 and `replace-match'. */)
2183 (regexp
, bound
, noerror
, count
)
2184 Lisp_Object regexp
, bound
, noerror
, count
;
2186 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2189 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2190 "sPosix search backward: ",
2191 doc
: /* Search backward from point for match for regular expression REGEXP.
2192 Find the longest match in accord with Posix regular expression rules.
2193 Set point to the beginning of the match, and return point.
2194 The match found is the one starting last in the buffer
2195 and yet ending before the origin of the search.
2196 An optional second argument bounds the search; it is a buffer position.
2197 The match found must start at or after that position.
2198 Optional third argument, if t, means if fail just return nil (no error).
2199 If not nil and not t, move to limit of search and return nil.
2200 Optional fourth argument is repeat count--search for successive occurrences.
2201 See also the functions `match-beginning', `match-end', `match-string',
2202 and `replace-match'. */)
2203 (regexp
, bound
, noerror
, count
)
2204 Lisp_Object regexp
, bound
, noerror
, count
;
2206 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2209 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2211 doc
: /* Search forward from point for regular expression REGEXP.
2212 Find the longest match in accord with Posix regular expression rules.
2213 Set point to the end of the occurrence found, and return point.
2214 An optional second argument bounds the search; it is a buffer position.
2215 The match found must not extend after that position.
2216 Optional third argument, if t, means if fail just return nil (no error).
2217 If not nil and not t, move to limit of search and return nil.
2218 Optional fourth argument is repeat count--search for successive occurrences.
2219 See also the functions `match-beginning', `match-end', `match-string',
2220 and `replace-match'. */)
2221 (regexp
, bound
, noerror
, count
)
2222 Lisp_Object regexp
, bound
, noerror
, count
;
2224 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2227 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2228 doc
: /* Replace text matched by last search with NEWTEXT.
2229 Leave point at the end of the replacement text.
2231 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2232 Otherwise maybe capitalize the whole text, or maybe just word initials,
2233 based on the replaced text.
2234 If the replaced text has only capital letters
2235 and has at least one multiletter word, convert NEWTEXT to all caps.
2236 Otherwise if all words are capitalized in the replaced text,
2237 capitalize each word in NEWTEXT.
2239 If third arg LITERAL is non-nil, insert NEWTEXT literally.
2240 Otherwise treat `\\' as special:
2241 `\\&' in NEWTEXT means substitute original matched text.
2242 `\\N' means substitute what matched the Nth `\\(...\\)'.
2243 If Nth parens didn't match, substitute nothing.
2244 `\\\\' means insert one `\\'.
2245 Case conversion does not apply to these substitutions.
2247 FIXEDCASE and LITERAL are optional arguments.
2249 The optional fourth argument STRING can be a string to modify.
2250 This is meaningful when the previous match was done against STRING,
2251 using `string-match'. When used this way, `replace-match'
2252 creates and returns a new string made by copying STRING and replacing
2253 the part of STRING that was matched.
2255 The optional fifth argument SUBEXP specifies a subexpression;
2256 it says to replace just that subexpression with NEWTEXT,
2257 rather than replacing the entire matched text.
2258 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2259 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2260 NEWTEXT in place of subexp N.
2261 This is useful only after a regular expression search or match,
2262 since only regular expressions have distinguished subexpressions. */)
2263 (newtext
, fixedcase
, literal
, string
, subexp
)
2264 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2266 enum { nochange
, all_caps
, cap_initial
} case_action
;
2267 register int pos
, pos_byte
;
2268 int some_multiletter_word
;
2271 int some_nonuppercase_initial
;
2272 register int c
, prevc
;
2274 int opoint
, newpoint
;
2276 CHECK_STRING (newtext
);
2278 if (! NILP (string
))
2279 CHECK_STRING (string
);
2281 case_action
= nochange
; /* We tried an initialization */
2282 /* but some C compilers blew it */
2284 if (search_regs
.num_regs
<= 0)
2285 error ("`replace-match' called before any match found");
2291 CHECK_NUMBER (subexp
);
2292 sub
= XINT (subexp
);
2293 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2294 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2299 if (search_regs
.start
[sub
] < BEGV
2300 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2301 || search_regs
.end
[sub
] > ZV
)
2302 args_out_of_range (make_number (search_regs
.start
[sub
]),
2303 make_number (search_regs
.end
[sub
]));
2307 if (search_regs
.start
[sub
] < 0
2308 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2309 || search_regs
.end
[sub
] > SCHARS (string
))
2310 args_out_of_range (make_number (search_regs
.start
[sub
]),
2311 make_number (search_regs
.end
[sub
]));
2314 if (NILP (fixedcase
))
2316 /* Decide how to casify by examining the matched text. */
2319 pos
= search_regs
.start
[sub
];
2320 last
= search_regs
.end
[sub
];
2323 pos_byte
= CHAR_TO_BYTE (pos
);
2325 pos_byte
= string_char_to_byte (string
, pos
);
2328 case_action
= all_caps
;
2330 /* some_multiletter_word is set nonzero if any original word
2331 is more than one letter long. */
2332 some_multiletter_word
= 0;
2334 some_nonuppercase_initial
= 0;
2341 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2342 INC_BOTH (pos
, pos_byte
);
2345 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2349 /* Cannot be all caps if any original char is lower case */
2352 if (SYNTAX (prevc
) != Sword
)
2353 some_nonuppercase_initial
= 1;
2355 some_multiletter_word
= 1;
2357 else if (!NOCASEP (c
))
2360 if (SYNTAX (prevc
) != Sword
)
2363 some_multiletter_word
= 1;
2367 /* If the initial is a caseless word constituent,
2368 treat that like a lowercase initial. */
2369 if (SYNTAX (prevc
) != Sword
)
2370 some_nonuppercase_initial
= 1;
2376 /* Convert to all caps if the old text is all caps
2377 and has at least one multiletter word. */
2378 if (! some_lowercase
&& some_multiletter_word
)
2379 case_action
= all_caps
;
2380 /* Capitalize each word, if the old text has all capitalized words. */
2381 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2382 case_action
= cap_initial
;
2383 else if (!some_nonuppercase_initial
&& some_uppercase
)
2384 /* Should x -> yz, operating on X, give Yz or YZ?
2385 We'll assume the latter. */
2386 case_action
= all_caps
;
2388 case_action
= nochange
;
2391 /* Do replacement in a string. */
2394 Lisp_Object before
, after
;
2396 before
= Fsubstring (string
, make_number (0),
2397 make_number (search_regs
.start
[sub
]));
2398 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2400 /* Substitute parts of the match into NEWTEXT
2405 int lastpos_byte
= 0;
2406 /* We build up the substituted string in ACCUM. */
2409 int length
= SBYTES (newtext
);
2413 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2417 int delbackslash
= 0;
2419 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2423 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2427 substart
= search_regs
.start
[sub
];
2428 subend
= search_regs
.end
[sub
];
2430 else if (c
>= '1' && c
<= '9')
2432 if (search_regs
.start
[c
- '0'] >= 0
2433 && c
<= search_regs
.num_regs
+ '0')
2435 substart
= search_regs
.start
[c
- '0'];
2436 subend
= search_regs
.end
[c
- '0'];
2440 /* If that subexp did not match,
2441 replace \\N with nothing. */
2449 error ("Invalid use of `\\' in replacement text");
2453 if (pos
- 2 != lastpos
)
2454 middle
= substring_both (newtext
, lastpos
,
2456 pos
- 2, pos_byte
- 2);
2459 accum
= concat3 (accum
, middle
,
2461 make_number (substart
),
2462 make_number (subend
)));
2464 lastpos_byte
= pos_byte
;
2466 else if (delbackslash
)
2468 middle
= substring_both (newtext
, lastpos
,
2470 pos
- 1, pos_byte
- 1);
2472 accum
= concat2 (accum
, middle
);
2474 lastpos_byte
= pos_byte
;
2479 middle
= substring_both (newtext
, lastpos
,
2485 newtext
= concat2 (accum
, middle
);
2488 /* Do case substitution in NEWTEXT if desired. */
2489 if (case_action
== all_caps
)
2490 newtext
= Fupcase (newtext
);
2491 else if (case_action
== cap_initial
)
2492 newtext
= Fupcase_initials (newtext
);
2494 return concat3 (before
, newtext
, after
);
2497 /* Record point, then move (quietly) to the start of the match. */
2498 if (PT
>= search_regs
.end
[sub
])
2500 else if (PT
> search_regs
.start
[sub
])
2501 opoint
= search_regs
.end
[sub
] - ZV
;
2505 /* If we want non-literal replacement,
2506 perform substitution on the replacement string. */
2509 int length
= SBYTES (newtext
);
2510 unsigned char *substed
;
2511 int substed_alloc_size
, substed_len
;
2512 int buf_multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
2513 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2514 Lisp_Object rev_tbl
;
2515 int really_changed
= 0;
2519 substed_alloc_size
= length
* 2 + 100;
2520 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2523 /* Go thru NEWTEXT, producing the actual text to insert in
2524 SUBSTED while adjusting multibyteness to that of the current
2527 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2529 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2530 unsigned char *add_stuff
= NULL
;
2536 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2538 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2542 /* Note that we don't have to increment POS. */
2543 c
= SREF (newtext
, pos_byte
++);
2545 c
= unibyte_char_to_multibyte (c
);
2548 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2549 or set IDX to a match index, which means put that part
2550 of the buffer text into SUBSTED. */
2558 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2560 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2561 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2565 c
= SREF (newtext
, pos_byte
++);
2567 c
= unibyte_char_to_multibyte (c
);
2572 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2574 if (search_regs
.start
[c
- '0'] >= 1)
2578 add_len
= 1, add_stuff
= "\\";
2582 error ("Invalid use of `\\' in replacement text");
2587 add_len
= CHAR_STRING (c
, str
);
2591 /* If we want to copy part of a previous match,
2592 set up ADD_STUFF and ADD_LEN to point to it. */
2595 int begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2596 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2597 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2598 move_gap (search_regs
.start
[idx
]);
2599 add_stuff
= BYTE_POS_ADDR (begbyte
);
2602 /* Now the stuff we want to add to SUBSTED
2603 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2605 /* Make sure SUBSTED is big enough. */
2606 if (substed_len
+ add_len
>= substed_alloc_size
)
2608 substed_alloc_size
= substed_len
+ add_len
+ 500;
2609 substed
= (unsigned char *) xrealloc (substed
,
2610 substed_alloc_size
+ 1);
2613 /* Now add to the end of SUBSTED. */
2616 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2617 substed_len
+= add_len
;
2625 int nchars
= multibyte_chars_in_text (substed
, substed_len
);
2627 newtext
= make_multibyte_string (substed
, nchars
, substed_len
);
2630 newtext
= make_unibyte_string (substed
, substed_len
);
2635 /* Replace the old text with the new in the cleanest possible way. */
2636 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2638 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2640 if (case_action
== all_caps
)
2641 Fupcase_region (make_number (search_regs
.start
[sub
]),
2642 make_number (newpoint
));
2643 else if (case_action
== cap_initial
)
2644 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2645 make_number (newpoint
));
2647 /* Adjust search data for this change. */
2649 int oldend
= search_regs
.end
[sub
];
2650 int oldstart
= search_regs
.start
[sub
];
2651 int change
= newpoint
- search_regs
.end
[sub
];
2654 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2656 if (search_regs
.start
[i
] >= oldend
)
2657 search_regs
.start
[i
] += change
;
2658 else if (search_regs
.start
[i
] > oldstart
)
2659 search_regs
.start
[i
] = oldstart
;
2660 if (search_regs
.end
[i
] >= oldend
)
2661 search_regs
.end
[i
] += change
;
2662 else if (search_regs
.end
[i
] > oldstart
)
2663 search_regs
.end
[i
] = oldstart
;
2667 /* Put point back where it was in the text. */
2669 TEMP_SET_PT (opoint
+ ZV
);
2671 TEMP_SET_PT (opoint
);
2673 /* Now move point "officially" to the start of the inserted replacement. */
2674 move_if_not_intangible (newpoint
);
2680 match_limit (num
, beginningp
)
2689 args_out_of_range (num
, make_number (0));
2690 if (search_regs
.num_regs
<= 0)
2691 error ("No match data, because no search succeeded");
2692 if (n
>= search_regs
.num_regs
2693 || search_regs
.start
[n
] < 0)
2695 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2696 : search_regs
.end
[n
]));
2699 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2700 doc
: /* Return position of start of text matched by last search.
2701 SUBEXP, a number, specifies which parenthesized expression in the last
2703 Value is nil if SUBEXPth pair didn't match, or there were less than
2705 Zero means the entire text matched by the whole regexp or whole string. */)
2709 return match_limit (subexp
, 1);
2712 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2713 doc
: /* Return position of end of text matched by last search.
2714 SUBEXP, a number, specifies which parenthesized expression in the last
2716 Value is nil if SUBEXPth pair didn't match, or there were less than
2718 Zero means the entire text matched by the whole regexp or whole string. */)
2722 return match_limit (subexp
, 0);
2725 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2726 doc
: /* Return a list containing all info on what the last search matched.
2727 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2728 All the elements are markers or nil (nil if the Nth pair didn't match)
2729 if the last match was on a buffer; integers or nil if a string was matched.
2730 Use `store-match-data' to reinstate the data in this list.
2732 If INTEGERS (the optional first argument) is non-nil, always use
2733 integers \(rather than markers) to represent buffer positions. In
2734 this case, and if the last match was in a buffer, the buffer will get
2735 stored as one additional element at the end of the list.
2737 If REUSE is a list, reuse it as part of the value. If REUSE is long
2738 enough to hold all the values, and if INTEGERS is non-nil, no consing
2741 If optional third arg RESEAT is non-nil, any previous markers on the
2742 REUSE list will be modified to point to nowhere.
2744 Return value is undefined if the last search failed. */)
2745 (integers
, reuse
, reseat
)
2746 Lisp_Object integers
, reuse
, reseat
;
2748 Lisp_Object tail
, prev
;
2753 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2754 if (MARKERP (XCAR (tail
)))
2756 unchain_marker (XMARKER (XCAR (tail
)));
2757 XSETCAR (tail
, Qnil
);
2760 if (NILP (last_thing_searched
))
2765 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
+ 1)
2766 * sizeof (Lisp_Object
));
2769 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2771 int start
= search_regs
.start
[i
];
2774 if (EQ (last_thing_searched
, Qt
)
2775 || ! NILP (integers
))
2777 XSETFASTINT (data
[2 * i
], start
);
2778 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2780 else if (BUFFERP (last_thing_searched
))
2782 data
[2 * i
] = Fmake_marker ();
2783 Fset_marker (data
[2 * i
],
2784 make_number (start
),
2785 last_thing_searched
);
2786 data
[2 * i
+ 1] = Fmake_marker ();
2787 Fset_marker (data
[2 * i
+ 1],
2788 make_number (search_regs
.end
[i
]),
2789 last_thing_searched
);
2792 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2798 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2801 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2803 data
[len
] = last_thing_searched
;
2807 /* If REUSE is not usable, cons up the values and return them. */
2808 if (! CONSP (reuse
))
2809 return Flist (len
, data
);
2811 /* If REUSE is a list, store as many value elements as will fit
2812 into the elements of REUSE. */
2813 for (i
= 0, tail
= reuse
; CONSP (tail
);
2814 i
++, tail
= XCDR (tail
))
2817 XSETCAR (tail
, data
[i
]);
2819 XSETCAR (tail
, Qnil
);
2823 /* If we couldn't fit all value elements into REUSE,
2824 cons up the rest of them and add them to the end of REUSE. */
2826 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2831 /* Internal usage only:
2832 If RESEAT is `evaporate', put the markers back on the free list
2833 immediately. No other references to the markers must exist in this case,
2834 so it is used only internally on the unwind stack and save-match-data from
2837 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2838 doc
: /* Set internal data on last search match from elements of LIST.
2839 LIST should have been created by calling `match-data' previously.
2841 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2843 register Lisp_Object list
, reseat
;
2846 register Lisp_Object marker
;
2848 if (running_asynch_code
)
2849 save_search_regs ();
2851 if (!CONSP (list
) && !NILP (list
))
2852 list
= wrong_type_argument (Qconsp
, list
);
2854 /* Unless we find a marker with a buffer or an explicit buffer
2855 in LIST, assume that this match data came from a string. */
2856 last_thing_searched
= Qt
;
2858 /* Allocate registers if they don't already exist. */
2860 int length
= XFASTINT (Flength (list
)) / 2;
2862 if (length
> search_regs
.num_regs
)
2864 if (search_regs
.num_regs
== 0)
2867 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2869 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2874 = (regoff_t
*) xrealloc (search_regs
.start
,
2875 length
* sizeof (regoff_t
));
2877 = (regoff_t
*) xrealloc (search_regs
.end
,
2878 length
* sizeof (regoff_t
));
2881 for (i
= search_regs
.num_regs
; i
< length
; i
++)
2882 search_regs
.start
[i
] = -1;
2884 search_regs
.num_regs
= length
;
2887 for (i
= 0; CONSP (list
); i
++)
2889 marker
= XCAR (list
);
2890 if (BUFFERP (marker
))
2892 last_thing_searched
= marker
;
2899 search_regs
.start
[i
] = -1;
2908 if (MARKERP (marker
))
2910 if (XMARKER (marker
)->buffer
== 0)
2911 XSETFASTINT (marker
, 0);
2913 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2916 CHECK_NUMBER_COERCE_MARKER (marker
);
2917 from
= XINT (marker
);
2919 if (!NILP (reseat
) && MARKERP (m
))
2921 if (EQ (reseat
, Qevaporate
))
2924 unchain_marker (XMARKER (m
));
2925 XSETCAR (list
, Qnil
);
2928 if ((list
= XCDR (list
), !CONSP (list
)))
2931 m
= marker
= XCAR (list
);
2933 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2934 XSETFASTINT (marker
, 0);
2936 CHECK_NUMBER_COERCE_MARKER (marker
);
2937 search_regs
.start
[i
] = from
;
2938 search_regs
.end
[i
] = XINT (marker
);
2940 if (!NILP (reseat
) && MARKERP (m
))
2942 if (EQ (reseat
, Qevaporate
))
2945 unchain_marker (XMARKER (m
));
2946 XSETCAR (list
, Qnil
);
2952 for (; i
< search_regs
.num_regs
; i
++)
2953 search_regs
.start
[i
] = -1;
2959 /* If non-zero the match data have been saved in saved_search_regs
2960 during the execution of a sentinel or filter. */
2961 static int search_regs_saved
;
2962 static struct re_registers saved_search_regs
;
2963 static Lisp_Object saved_last_thing_searched
;
2965 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2966 if asynchronous code (filter or sentinel) is running. */
2970 if (!search_regs_saved
)
2972 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2973 saved_search_regs
.start
= search_regs
.start
;
2974 saved_search_regs
.end
= search_regs
.end
;
2975 saved_last_thing_searched
= last_thing_searched
;
2976 last_thing_searched
= Qnil
;
2977 search_regs
.num_regs
= 0;
2978 search_regs
.start
= 0;
2979 search_regs
.end
= 0;
2981 search_regs_saved
= 1;
2985 /* Called upon exit from filters and sentinels. */
2987 restore_search_regs ()
2989 if (search_regs_saved
)
2991 if (search_regs
.num_regs
> 0)
2993 xfree (search_regs
.start
);
2994 xfree (search_regs
.end
);
2996 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2997 search_regs
.start
= saved_search_regs
.start
;
2998 search_regs
.end
= saved_search_regs
.end
;
2999 last_thing_searched
= saved_last_thing_searched
;
3000 saved_last_thing_searched
= Qnil
;
3001 search_regs_saved
= 0;
3006 unwind_set_match_data (list
)
3009 /* It is safe to free (evaporate) the markers immediately. */
3010 return Fset_match_data (list
, Qevaporate
);
3013 /* Called to unwind protect the match data. */
3015 record_unwind_save_match_data ()
3017 record_unwind_protect (unwind_set_match_data
,
3018 Fmatch_data (Qnil
, Qnil
, Qnil
));
3021 /* Quote a string to inactivate reg-expr chars */
3023 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3024 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3028 register unsigned char *in
, *out
, *end
;
3029 register unsigned char *temp
;
3030 int backslashes_added
= 0;
3032 CHECK_STRING (string
);
3034 temp
= (unsigned char *) alloca (SBYTES (string
) * 2);
3036 /* Now copy the data into the new string, inserting escapes. */
3038 in
= SDATA (string
);
3039 end
= in
+ SBYTES (string
);
3042 for (; in
!= end
; in
++)
3044 if (*in
== '[' || *in
== ']'
3045 || *in
== '*' || *in
== '.' || *in
== '\\'
3046 || *in
== '?' || *in
== '+'
3047 || *in
== '^' || *in
== '$')
3048 *out
++ = '\\', backslashes_added
++;
3052 return make_specified_string (temp
,
3053 SCHARS (string
) + backslashes_added
,
3055 STRING_MULTIBYTE (string
));
3063 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3065 searchbufs
[i
].buf
.allocated
= 100;
3066 searchbufs
[i
].buf
.buffer
= (unsigned char *) xmalloc (100);
3067 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3068 searchbufs
[i
].regexp
= Qnil
;
3069 searchbufs
[i
].whitespace_regexp
= Qnil
;
3070 staticpro (&searchbufs
[i
].regexp
);
3071 staticpro (&searchbufs
[i
].whitespace_regexp
);
3072 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3074 searchbuf_head
= &searchbufs
[0];
3076 Qsearch_failed
= intern ("search-failed");
3077 staticpro (&Qsearch_failed
);
3078 Qinvalid_regexp
= intern ("invalid-regexp");
3079 staticpro (&Qinvalid_regexp
);
3081 Fput (Qsearch_failed
, Qerror_conditions
,
3082 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
3083 Fput (Qsearch_failed
, Qerror_message
,
3084 build_string ("Search failed"));
3086 Fput (Qinvalid_regexp
, Qerror_conditions
,
3087 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
3088 Fput (Qinvalid_regexp
, Qerror_message
,
3089 build_string ("Invalid regexp"));
3091 last_thing_searched
= Qnil
;
3092 staticpro (&last_thing_searched
);
3094 saved_last_thing_searched
= Qnil
;
3095 staticpro (&saved_last_thing_searched
);
3097 DEFVAR_LISP ("search-spaces-regexp", &Vsearch_spaces_regexp
,
3098 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3099 Some commands use this for user-specified regexps.
3100 Spaces that occur inside character classes or repetition operators
3101 or other such regexp constructs are not replaced with this.
3102 A value of nil (which is the normal value) means treat spaces literally. */);
3103 Vsearch_spaces_regexp
= Qnil
;
3105 defsubr (&Slooking_at
);
3106 defsubr (&Sposix_looking_at
);
3107 defsubr (&Sstring_match
);
3108 defsubr (&Sposix_string_match
);
3109 defsubr (&Ssearch_forward
);
3110 defsubr (&Ssearch_backward
);
3111 defsubr (&Sword_search_forward
);
3112 defsubr (&Sword_search_backward
);
3113 defsubr (&Sre_search_forward
);
3114 defsubr (&Sre_search_backward
);
3115 defsubr (&Sposix_search_forward
);
3116 defsubr (&Sposix_search_backward
);
3117 defsubr (&Sreplace_match
);
3118 defsubr (&Smatch_beginning
);
3119 defsubr (&Smatch_end
);
3120 defsubr (&Smatch_data
);
3121 defsubr (&Sset_match_data
);
3122 defsubr (&Sregexp_quote
);
3125 /* arch-tag: a6059d79-0552-4f14-a2cb-d379a4e3c78f
3126 (do not change this comment) */