1 /* String search routines for GNU Emacs.
2 Copyright (C) 1985, 1986, 1987, 1993, 1994, 1997, 1998, 1999, 2001, 2002,
3 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 Free Software Foundation, Inc.
6 This file is part of GNU Emacs.
8 GNU Emacs is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
13 GNU Emacs is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
28 #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 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
59 /* The head of the linked list; points to the most recently used buffer. */
60 struct regexp_cache
*searchbuf_head
;
63 /* error condition signaled when regexp compile_pattern fails */
65 Lisp_Object Qinvalid_regexp
;
67 /* Error condition used for failing searches */
68 Lisp_Object Qsearch_failed
;
70 Lisp_Object impl_Vsearch_spaces_regexp
;
72 /* If non-nil, the match data will not be changed during call to
73 searching or matching functions. This variable is for internal use
75 Lisp_Object impl_Vinhibit_changing_match_data
;
77 static void set_search_regs
P_ ((EMACS_INT
, EMACS_INT
));
78 static void save_search_regs
P_ ((void));
79 static EMACS_INT simple_search
P_ ((int, unsigned char *, int, int,
80 Lisp_Object
, EMACS_INT
, EMACS_INT
,
81 EMACS_INT
, EMACS_INT
));
82 static EMACS_INT boyer_moore
P_ ((int, unsigned char *, int, int,
83 Lisp_Object
, Lisp_Object
,
85 EMACS_INT
, EMACS_INT
, int));
86 static EMACS_INT search_buffer
P_ ((Lisp_Object
, EMACS_INT
, EMACS_INT
,
87 EMACS_INT
, EMACS_INT
, int, int,
88 Lisp_Object
, Lisp_Object
, int));
89 static void matcher_overflow () NO_RETURN
;
94 error ("Stack overflow in regexp matcher");
97 /* Compile a regexp and signal a Lisp error if anything goes wrong.
98 PATTERN is the pattern to compile.
99 CP is the place to put the result.
100 TRANSLATE is a translation table for ignoring case, or nil for none.
101 REGP is the structure that says where to store the "register"
102 values that will result from matching this pattern.
103 If it is 0, we should compile the pattern not to record any
104 subexpression bounds.
105 POSIX is nonzero if we want full backtracking (POSIX style)
106 for this pattern. 0 means backtrack only enough to get a valid match.
108 The behavior also depends on Vsearch_spaces_regexp. */
111 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
)
112 struct regexp_cache
*cp
;
114 Lisp_Object translate
;
115 struct re_registers
*regp
;
122 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
124 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
125 cp
->buf
.charset_unibyte
= charset_unibyte
;
126 if (STRINGP (Vsearch_spaces_regexp
))
127 cp
->whitespace_regexp
= Vsearch_spaces_regexp
;
129 cp
->whitespace_regexp
= Qnil
;
131 /* rms: I think BLOCK_INPUT is not needed here any more,
132 because regex.c defines malloc to call xmalloc.
133 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
134 So let's turn it off. */
136 old
= re_set_syntax (RE_SYNTAX_EMACS
137 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
139 if (STRINGP (Vsearch_spaces_regexp
))
140 re_set_whitespace_regexp (SDATA (Vsearch_spaces_regexp
));
142 re_set_whitespace_regexp (NULL
);
144 val
= (char *) re_compile_pattern ((char *) SDATA (pattern
),
145 SBYTES (pattern
), &cp
->buf
);
147 /* If the compiled pattern hard codes some of the contents of the
148 syntax-table, it can only be reused with *this* syntax table. */
149 cp
->syntax_table
= cp
->buf
.used_syntax
? BUF_SYNTAX_TABLE (current_buffer
) : Qt
;
151 re_set_whitespace_regexp (NULL
);
156 xsignal1 (Qinvalid_regexp
, build_string (val
));
158 cp
->regexp
= Fcopy_sequence (pattern
);
161 /* Shrink each compiled regexp buffer in the cache
162 to the size actually used right now.
163 This is called from garbage collection. */
166 shrink_regexp_cache ()
168 struct regexp_cache
*cp
;
170 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
172 cp
->buf
.allocated
= cp
->buf
.used
;
174 = (unsigned char *) xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
178 /* Clear the regexp cache w.r.t. a particular syntax table,
179 because it was changed.
180 There is no danger of memory leak here because re_compile_pattern
181 automagically manages the memory in each re_pattern_buffer struct,
182 based on its `allocated' and `buffer' values. */
184 clear_regexp_cache ()
188 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
189 /* It's tempting to compare with the syntax-table we've actually changed,
190 but it's not sufficient because char-table inheritance means that
191 modifying one syntax-table can change others at the same time. */
192 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
193 searchbufs
[i
].regexp
= Qnil
;
196 /* Compile a regexp if necessary, but first check to see if there's one in
198 PATTERN is the pattern to compile.
199 TRANSLATE is a translation table for ignoring case, or nil for none.
200 REGP is the structure that says where to store the "register"
201 values that will result from matching this pattern.
202 If it is 0, we should compile the pattern not to record any
203 subexpression bounds.
204 POSIX is nonzero if we want full backtracking (POSIX style)
205 for this pattern. 0 means backtrack only enough to get a valid match. */
207 struct re_pattern_buffer
*
208 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
210 struct re_registers
*regp
;
211 Lisp_Object translate
;
212 int posix
, 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
, BUF_SYNTAX_TABLE (current_buffer
)))
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
, regp
, 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 mulitbyte 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 (string
, posix
)
274 unsigned char *p1
, *p2
;
277 struct re_pattern_buffer
*bufp
;
279 if (running_asynch_code
)
282 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
283 XCHAR_TABLE (BUF_CASE_CANON_TABLE (current_buffer
))->extras
[2]
284 = BUF_CASE_EQV_TABLE (current_buffer
);
286 CHECK_STRING (string
);
287 bufp
= compile_pattern (string
,
288 (NILP (Vinhibit_changing_match_data
)
289 ? &search_regs
: NULL
),
290 (!NILP (BUF_CASE_FOLD_SEARCH (current_buffer
))
291 ? BUF_CASE_CANON_TABLE (current_buffer
) : Qnil
),
293 !NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
)));
296 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
298 /* Get pointers and sizes of the two strings
299 that make up the visible portion of the buffer. */
302 s1
= GPT_BYTE
- BEGV_BYTE
;
304 s2
= ZV_BYTE
- GPT_BYTE
;
308 s2
= ZV_BYTE
- BEGV_BYTE
;
313 s1
= ZV_BYTE
- BEGV_BYTE
;
317 re_match_object
= Qnil
;
319 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
321 (NILP (Vinhibit_changing_match_data
)
322 ? &search_regs
: NULL
),
323 ZV_BYTE
- BEGV_BYTE
);
329 val
= (0 <= i
? Qt
: Qnil
);
330 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
331 for (i
= 0; i
< search_regs
.num_regs
; i
++)
332 if (search_regs
.start
[i
] >= 0)
335 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
337 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
340 /* Set last_thing_searched only when match data is changed. */
341 if (NILP (Vinhibit_changing_match_data
))
342 XSETBUFFER (last_thing_searched
, current_buffer
);
347 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
348 doc
: /* Return t if text after point matches regular expression REGEXP.
349 This function modifies the match data that `match-beginning',
350 `match-end' and `match-data' access; save and restore the match
351 data if you want to preserve them. */)
355 return looking_at_1 (regexp
, 0);
358 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
359 doc
: /* Return t if text after point matches regular expression REGEXP.
360 Find the longest match, in accord with Posix regular expression rules.
361 This function modifies the match data that `match-beginning',
362 `match-end' and `match-data' access; save and restore the match
363 data if you want to preserve them. */)
367 return looking_at_1 (regexp
, 1);
371 string_match_1 (regexp
, string
, start
, posix
)
372 Lisp_Object regexp
, string
, start
;
376 struct re_pattern_buffer
*bufp
;
377 EMACS_INT pos
, pos_byte
;
380 if (running_asynch_code
)
383 CHECK_STRING (regexp
);
384 CHECK_STRING (string
);
387 pos
= 0, pos_byte
= 0;
390 int len
= SCHARS (string
);
392 CHECK_NUMBER (start
);
394 if (pos
< 0 && -pos
<= len
)
396 else if (0 > pos
|| pos
> len
)
397 args_out_of_range (string
, start
);
398 pos_byte
= string_char_to_byte (string
, pos
);
401 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
402 XCHAR_TABLE (BUF_CASE_CANON_TABLE (current_buffer
))->extras
[2]
403 = BUF_CASE_EQV_TABLE (current_buffer
);
405 bufp
= compile_pattern (regexp
,
406 (NILP (Vinhibit_changing_match_data
)
407 ? &search_regs
: NULL
),
408 (!NILP (BUF_CASE_FOLD_SEARCH (current_buffer
))
409 ? BUF_CASE_CANON_TABLE (current_buffer
) : Qnil
),
411 STRING_MULTIBYTE (string
));
413 re_match_object
= string
;
415 val
= re_search (bufp
, (char *) SDATA (string
),
416 SBYTES (string
), pos_byte
,
417 SBYTES (string
) - pos_byte
,
418 (NILP (Vinhibit_changing_match_data
)
419 ? &search_regs
: NULL
));
422 /* Set last_thing_searched only when match data is changed. */
423 if (NILP (Vinhibit_changing_match_data
))
424 last_thing_searched
= Qt
;
428 if (val
< 0) return Qnil
;
430 if (NILP (Vinhibit_changing_match_data
))
431 for (i
= 0; i
< search_regs
.num_regs
; i
++)
432 if (search_regs
.start
[i
] >= 0)
435 = string_byte_to_char (string
, search_regs
.start
[i
]);
437 = string_byte_to_char (string
, search_regs
.end
[i
]);
440 return make_number (string_byte_to_char (string
, val
));
443 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
444 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
445 Matching ignores case if `case-fold-search' is non-nil.
446 If third arg START is non-nil, start search at that index in STRING.
447 For index of first char beyond the match, do (match-end 0).
448 `match-end' and `match-beginning' also give indices of substrings
449 matched by parenthesis constructs in the pattern.
451 You can use the function `match-string' to extract the substrings
452 matched by the parenthesis constructions in REGEXP. */)
453 (regexp
, string
, start
)
454 Lisp_Object regexp
, string
, start
;
456 return string_match_1 (regexp
, string
, start
, 0);
459 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
460 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
461 Find the longest match, in accord with Posix regular expression rules.
462 Case is ignored if `case-fold-search' is non-nil in the current buffer.
463 If third arg START is non-nil, start search at that index in STRING.
464 For index of first char beyond the match, do (match-end 0).
465 `match-end' and `match-beginning' also give indices of substrings
466 matched by parenthesis constructs in the pattern. */)
467 (regexp
, string
, start
)
468 Lisp_Object regexp
, string
, start
;
470 return string_match_1 (regexp
, string
, start
, 1);
473 /* Match REGEXP against STRING, searching all of STRING,
474 and return the index of the match, or negative on failure.
475 This does not clobber the match data. */
478 fast_string_match (regexp
, string
)
479 Lisp_Object regexp
, string
;
482 struct re_pattern_buffer
*bufp
;
484 bufp
= compile_pattern (regexp
, 0, Qnil
,
485 0, STRING_MULTIBYTE (string
));
487 re_match_object
= string
;
489 val
= re_search (bufp
, (char *) SDATA (string
),
496 /* Match REGEXP against STRING, searching all of STRING ignoring case,
497 and return the index of the match, or negative on failure.
498 This does not clobber the match data.
499 We assume that STRING contains single-byte characters. */
501 extern Lisp_Object Vascii_downcase_table
;
504 fast_c_string_match_ignore_case (regexp
, string
)
509 struct re_pattern_buffer
*bufp
;
510 int len
= strlen (string
);
512 regexp
= string_make_unibyte (regexp
);
513 re_match_object
= Qt
;
514 bufp
= compile_pattern (regexp
, 0,
515 Vascii_canon_table
, 0,
518 val
= re_search (bufp
, string
, len
, 0, len
, 0);
523 /* Like fast_string_match but ignore case. */
526 fast_string_match_ignore_case (regexp
, string
)
527 Lisp_Object regexp
, string
;
530 struct re_pattern_buffer
*bufp
;
532 bufp
= compile_pattern (regexp
, 0, Vascii_canon_table
,
533 0, STRING_MULTIBYTE (string
));
535 re_match_object
= string
;
537 val
= re_search (bufp
, (char *) SDATA (string
),
544 /* Match REGEXP against the characters after POS to LIMIT, and return
545 the number of matched characters. If STRING is non-nil, match
546 against the characters in it. In that case, POS and LIMIT are
547 indices into the string. This function doesn't modify the match
551 fast_looking_at (regexp
, pos
, pos_byte
, limit
, limit_byte
, string
)
553 EMACS_INT pos
, pos_byte
, limit
, limit_byte
;
557 struct re_pattern_buffer
*buf
;
558 unsigned char *p1
, *p2
;
562 if (STRINGP (string
))
565 pos_byte
= string_char_to_byte (string
, pos
);
567 limit_byte
= string_char_to_byte (string
, limit
);
571 s2
= SBYTES (string
);
572 re_match_object
= string
;
573 multibyte
= STRING_MULTIBYTE (string
);
578 pos_byte
= CHAR_TO_BYTE (pos
);
580 limit_byte
= CHAR_TO_BYTE (limit
);
581 pos_byte
-= BEGV_BYTE
;
582 limit_byte
-= BEGV_BYTE
;
584 s1
= GPT_BYTE
- BEGV_BYTE
;
586 s2
= ZV_BYTE
- GPT_BYTE
;
590 s2
= ZV_BYTE
- BEGV_BYTE
;
595 s1
= ZV_BYTE
- BEGV_BYTE
;
598 re_match_object
= Qnil
;
599 multibyte
= ! NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
));
602 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
604 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
605 pos_byte
, NULL
, limit_byte
);
612 /* The newline cache: remembering which sections of text have no newlines. */
614 /* If the user has requested newline caching, make sure it's on.
615 Otherwise, make sure it's off.
616 This is our cheezy way of associating an action with the change of
617 state of a buffer-local variable. */
619 newline_cache_on_off (buf
)
622 if (NILP (BUF_CACHE_LONG_LINE_SCANS (buf
)))
624 /* It should be off. */
625 if (buf
->newline_cache
)
627 free_region_cache (buf
->newline_cache
);
628 buf
->newline_cache
= 0;
633 /* It should be on. */
634 if (buf
->newline_cache
== 0)
635 buf
->newline_cache
= new_region_cache ();
640 /* Search for COUNT instances of the character TARGET between START and END.
642 If COUNT is positive, search forwards; END must be >= START.
643 If COUNT is negative, search backwards for the -COUNTth instance;
644 END must be <= START.
645 If COUNT is zero, do anything you please; run rogue, for all I care.
647 If END is zero, use BEGV or ZV instead, as appropriate for the
648 direction indicated by COUNT.
650 If we find COUNT instances, set *SHORTAGE to zero, and return the
651 position past the COUNTth match. Note that for reverse motion
652 this is not the same as the usual convention for Emacs motion commands.
654 If we don't find COUNT instances before reaching END, set *SHORTAGE
655 to the number of TARGETs left unfound, and return END.
657 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
658 except when inside redisplay. */
661 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
663 EMACS_INT start
, end
;
668 struct region_cache
*newline_cache
;
679 if (! end
) end
= BEGV
;
682 newline_cache_on_off (current_buffer
);
683 newline_cache
= current_buffer
->newline_cache
;
688 immediate_quit
= allow_quit
;
693 /* Our innermost scanning loop is very simple; it doesn't know
694 about gaps, buffer ends, or the newline cache. ceiling is
695 the position of the last character before the next such
696 obstacle --- the last character the dumb search loop should
698 EMACS_INT ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
699 EMACS_INT start_byte
= CHAR_TO_BYTE (start
);
702 /* If we're looking for a newline, consult the newline cache
703 to see where we can avoid some scanning. */
704 if (target
== '\n' && newline_cache
)
708 while (region_cache_forward
709 (current_buffer
, newline_cache
, start_byte
, &next_change
))
710 start_byte
= next_change
;
711 immediate_quit
= allow_quit
;
713 /* START should never be after END. */
714 if (start_byte
> ceiling_byte
)
715 start_byte
= ceiling_byte
;
717 /* Now the text after start is an unknown region, and
718 next_change is the position of the next known region. */
719 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
722 /* The dumb loop can only scan text stored in contiguous
723 bytes. BUFFER_CEILING_OF returns the last character
724 position that is contiguous, so the ceiling is the
725 position after that. */
726 tem
= BUFFER_CEILING_OF (start_byte
);
727 ceiling_byte
= min (tem
, ceiling_byte
);
730 /* The termination address of the dumb loop. */
731 register unsigned char *ceiling_addr
732 = BYTE_POS_ADDR (ceiling_byte
) + 1;
733 register unsigned char *cursor
734 = BYTE_POS_ADDR (start_byte
);
735 unsigned char *base
= cursor
;
737 while (cursor
< ceiling_addr
)
739 unsigned char *scan_start
= cursor
;
742 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
745 /* If we're looking for newlines, cache the fact that
746 the region from start to cursor is free of them. */
747 if (target
== '\n' && newline_cache
)
748 know_region_cache (current_buffer
, newline_cache
,
749 start_byte
+ scan_start
- base
,
750 start_byte
+ cursor
- base
);
752 /* Did we find the target character? */
753 if (cursor
< ceiling_addr
)
758 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
764 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
770 /* The last character to check before the next obstacle. */
771 EMACS_INT ceiling_byte
= CHAR_TO_BYTE (end
);
772 EMACS_INT start_byte
= CHAR_TO_BYTE (start
);
775 /* Consult the newline cache, if appropriate. */
776 if (target
== '\n' && newline_cache
)
780 while (region_cache_backward
781 (current_buffer
, newline_cache
, start_byte
, &next_change
))
782 start_byte
= next_change
;
783 immediate_quit
= allow_quit
;
785 /* Start should never be at or before end. */
786 if (start_byte
<= ceiling_byte
)
787 start_byte
= ceiling_byte
+ 1;
789 /* Now the text before start is an unknown region, and
790 next_change is the position of the next known region. */
791 ceiling_byte
= max (next_change
, ceiling_byte
);
794 /* Stop scanning before the gap. */
795 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
796 ceiling_byte
= max (tem
, ceiling_byte
);
799 /* The termination address of the dumb loop. */
800 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
801 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
802 unsigned char *base
= cursor
;
804 while (cursor
>= ceiling_addr
)
806 unsigned char *scan_start
= cursor
;
808 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
811 /* If we're looking for newlines, cache the fact that
812 the region from after the cursor to start is free of them. */
813 if (target
== '\n' && newline_cache
)
814 know_region_cache (current_buffer
, newline_cache
,
815 start_byte
+ cursor
- base
,
816 start_byte
+ scan_start
- base
);
818 /* Did we find the target character? */
819 if (cursor
>= ceiling_addr
)
824 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
830 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
836 *shortage
= count
* direction
;
840 /* Search for COUNT instances of a line boundary, which means either a
841 newline or (if selective display enabled) a carriage return.
842 Start at START. If COUNT is negative, search backwards.
844 We report the resulting position by calling TEMP_SET_PT_BOTH.
846 If we find COUNT instances. we position after (always after,
847 even if scanning backwards) the COUNTth match, and return 0.
849 If we don't find COUNT instances before reaching the end of the
850 buffer (or the beginning, if scanning backwards), we return
851 the number of line boundaries left unfound, and position at
852 the limit we bumped up against.
854 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
855 except in special cases. */
858 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
859 EMACS_INT start
, start_byte
;
860 EMACS_INT limit
, limit_byte
;
864 int direction
= ((count
> 0) ? 1 : -1);
866 register unsigned char *cursor
;
870 register unsigned char *ceiling_addr
;
872 int old_immediate_quit
= immediate_quit
;
874 /* The code that follows is like scan_buffer
875 but checks for either newline or carriage return. */
880 start_byte
= CHAR_TO_BYTE (start
);
884 while (start_byte
< limit_byte
)
886 ceiling
= BUFFER_CEILING_OF (start_byte
);
887 ceiling
= min (limit_byte
- 1, ceiling
);
888 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
889 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
892 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
895 if (cursor
!= ceiling_addr
)
899 immediate_quit
= old_immediate_quit
;
900 start_byte
= start_byte
+ cursor
- base
+ 1;
901 start
= BYTE_TO_CHAR (start_byte
);
902 TEMP_SET_PT_BOTH (start
, start_byte
);
906 if (++cursor
== ceiling_addr
)
912 start_byte
+= cursor
- base
;
917 while (start_byte
> limit_byte
)
919 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
920 ceiling
= max (limit_byte
, ceiling
);
921 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
922 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
925 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
928 if (cursor
!= ceiling_addr
)
932 immediate_quit
= old_immediate_quit
;
933 /* Return the position AFTER the match we found. */
934 start_byte
= start_byte
+ cursor
- base
+ 1;
935 start
= BYTE_TO_CHAR (start_byte
);
936 TEMP_SET_PT_BOTH (start
, start_byte
);
943 /* Here we add 1 to compensate for the last decrement
944 of CURSOR, which took it past the valid range. */
945 start_byte
+= cursor
- base
+ 1;
949 TEMP_SET_PT_BOTH (limit
, limit_byte
);
950 immediate_quit
= old_immediate_quit
;
952 return count
* direction
;
956 find_next_newline_no_quit (from
, cnt
)
960 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
963 /* Like find_next_newline, but returns position before the newline,
964 not after, and only search up to TO. This isn't just
965 find_next_newline (...)-1, because you might hit TO. */
968 find_before_next_newline (from
, to
, cnt
)
973 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
981 /* Subroutines of Lisp buffer search functions. */
984 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
985 Lisp_Object string
, bound
, noerror
, count
;
996 CHECK_NUMBER (count
);
1000 CHECK_STRING (string
);
1004 lim
= ZV
, lim_byte
= ZV_BYTE
;
1006 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1010 CHECK_NUMBER_COERCE_MARKER (bound
);
1012 if (n
> 0 ? lim
< PT
: lim
> PT
)
1013 error ("Invalid search bound (wrong side of point)");
1015 lim
= ZV
, lim_byte
= ZV_BYTE
;
1016 else if (lim
< BEGV
)
1017 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1019 lim_byte
= CHAR_TO_BYTE (lim
);
1022 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
1023 XCHAR_TABLE (BUF_CASE_CANON_TABLE (current_buffer
))->extras
[2]
1024 = BUF_CASE_EQV_TABLE (current_buffer
);
1026 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
1027 (!NILP (BUF_CASE_FOLD_SEARCH (current_buffer
))
1028 ? BUF_CASE_CANON_TABLE (current_buffer
)
1030 (!NILP (BUF_CASE_FOLD_SEARCH (current_buffer
))
1031 ? BUF_CASE_EQV_TABLE (current_buffer
)
1037 xsignal1 (Qsearch_failed
, string
);
1039 if (!EQ (noerror
, Qt
))
1041 if (lim
< BEGV
|| lim
> ZV
)
1043 SET_PT_BOTH (lim
, lim_byte
);
1045 #if 0 /* This would be clean, but maybe programs depend on
1046 a value of nil here. */
1054 if (np
< BEGV
|| np
> ZV
)
1059 return make_number (np
);
1062 /* Return 1 if REGEXP it matches just one constant string. */
1065 trivial_regexp_p (regexp
)
1068 int len
= SBYTES (regexp
);
1069 unsigned char *s
= SDATA (regexp
);
1074 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1081 case '|': case '(': case ')': case '`': case '\'': case 'b':
1082 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1083 case 'S': case '=': case '{': case '}': case '_':
1084 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1085 case '1': case '2': case '3': case '4': case '5':
1086 case '6': case '7': case '8': case '9':
1094 /* Search for the n'th occurrence of STRING in the current buffer,
1095 starting at position POS and stopping at position LIM,
1096 treating STRING as a literal string if RE is false or as
1097 a regular expression if RE is true.
1099 If N is positive, searching is forward and LIM must be greater than POS.
1100 If N is negative, searching is backward and LIM must be less than POS.
1102 Returns -x if x occurrences remain to be found (x > 0),
1103 or else the position at the beginning of the Nth occurrence
1104 (if searching backward) or the end (if searching forward).
1106 POSIX is nonzero if we want full backtracking (POSIX style)
1107 for this pattern. 0 means backtrack only enough to get a valid match. */
1109 #define TRANSLATE(out, trt, d) \
1115 temp = Faref (trt, make_number (d)); \
1116 if (INTEGERP (temp)) \
1117 out = XINT (temp); \
1126 /* Only used in search_buffer, to record the end position of the match
1127 when searching regexps and SEARCH_REGS should not be changed
1128 (i.e. Vinhibit_changing_match_data is non-nil). */
1129 static struct re_registers search_regs_1
;
1132 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
1133 RE
, trt
, inverse_trt
, posix
)
1142 Lisp_Object inverse_trt
;
1145 int len
= SCHARS (string
);
1146 int len_byte
= SBYTES (string
);
1149 if (running_asynch_code
)
1150 save_search_regs ();
1152 /* Searching 0 times means don't move. */
1153 /* Null string is found at starting position. */
1154 if (len
== 0 || n
== 0)
1156 set_search_regs (pos_byte
, 0);
1160 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1162 unsigned char *p1
, *p2
;
1164 struct re_pattern_buffer
*bufp
;
1166 bufp
= compile_pattern (string
,
1167 (NILP (Vinhibit_changing_match_data
)
1168 ? &search_regs
: &search_regs_1
),
1170 !NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
)));
1172 immediate_quit
= 1; /* Quit immediately if user types ^G,
1173 because letting this function finish
1174 can take too long. */
1175 QUIT
; /* Do a pending quit right away,
1176 to avoid paradoxical behavior */
1177 /* Get pointers and sizes of the two strings
1178 that make up the visible portion of the buffer. */
1181 s1
= GPT_BYTE
- BEGV_BYTE
;
1183 s2
= ZV_BYTE
- GPT_BYTE
;
1187 s2
= ZV_BYTE
- BEGV_BYTE
;
1192 s1
= ZV_BYTE
- BEGV_BYTE
;
1195 re_match_object
= Qnil
;
1200 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1201 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1202 (NILP (Vinhibit_changing_match_data
)
1203 ? &search_regs
: &search_regs_1
),
1204 /* Don't allow match past current point */
1205 pos_byte
- BEGV_BYTE
);
1208 matcher_overflow ();
1212 if (NILP (Vinhibit_changing_match_data
))
1214 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1215 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1216 if (search_regs
.start
[i
] >= 0)
1218 search_regs
.start
[i
]
1219 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1221 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1223 XSETBUFFER (last_thing_searched
, current_buffer
);
1224 /* Set pos to the new position. */
1225 pos
= search_regs
.start
[0];
1229 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1230 /* Set pos to the new position. */
1231 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1244 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1245 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1246 (NILP (Vinhibit_changing_match_data
)
1247 ? &search_regs
: &search_regs_1
),
1248 lim_byte
- BEGV_BYTE
);
1251 matcher_overflow ();
1255 if (NILP (Vinhibit_changing_match_data
))
1257 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1258 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1259 if (search_regs
.start
[i
] >= 0)
1261 search_regs
.start
[i
]
1262 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1264 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1266 XSETBUFFER (last_thing_searched
, current_buffer
);
1267 pos
= search_regs
.end
[0];
1271 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1272 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1285 else /* non-RE case */
1287 unsigned char *raw_pattern
, *pat
;
1288 int raw_pattern_size
;
1289 int raw_pattern_size_byte
;
1290 unsigned char *patbuf
;
1291 int multibyte
= !NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
));
1292 unsigned char *base_pat
;
1293 /* Set to positive if we find a non-ASCII char that need
1294 translation. Otherwise set to zero later. */
1296 int boyer_moore_ok
= 1;
1298 /* MULTIBYTE says whether the text to be searched is multibyte.
1299 We must convert PATTERN to match that, or we will not really
1300 find things right. */
1302 if (multibyte
== STRING_MULTIBYTE (string
))
1304 raw_pattern
= (unsigned char *) SDATA (string
);
1305 raw_pattern_size
= SCHARS (string
);
1306 raw_pattern_size_byte
= SBYTES (string
);
1310 raw_pattern_size
= SCHARS (string
);
1311 raw_pattern_size_byte
1312 = count_size_as_multibyte (SDATA (string
),
1314 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1315 copy_text (SDATA (string
), raw_pattern
,
1316 SCHARS (string
), 0, 1);
1320 /* Converting multibyte to single-byte.
1322 ??? Perhaps this conversion should be done in a special way
1323 by subtracting nonascii-insert-offset from each non-ASCII char,
1324 so that only the multibyte chars which really correspond to
1325 the chosen single-byte character set can possibly match. */
1326 raw_pattern_size
= SCHARS (string
);
1327 raw_pattern_size_byte
= SCHARS (string
);
1328 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1329 copy_text (SDATA (string
), raw_pattern
,
1330 SBYTES (string
), 1, 0);
1333 /* Copy and optionally translate the pattern. */
1334 len
= raw_pattern_size
;
1335 len_byte
= raw_pattern_size_byte
;
1336 patbuf
= (unsigned char *) alloca (len
* MAX_MULTIBYTE_LENGTH
);
1338 base_pat
= raw_pattern
;
1341 /* Fill patbuf by translated characters in STRING while
1342 checking if we can use boyer-moore search. If TRT is
1343 non-nil, we can use boyer-moore search only if TRT can be
1344 represented by the byte array of 256 elements. For that,
1345 all non-ASCII case-equivalents of all case-senstive
1346 characters in STRING must belong to the same charset and
1351 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1352 int c
, translated
, inverse
;
1353 int in_charlen
, charlen
;
1355 /* If we got here and the RE flag is set, it's because we're
1356 dealing with a regexp known to be trivial, so the backslash
1357 just quotes the next character. */
1358 if (RE
&& *base_pat
== '\\')
1366 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1371 charlen
= in_charlen
;
1375 /* Translate the character. */
1376 TRANSLATE (translated
, trt
, c
);
1377 charlen
= CHAR_STRING (translated
, str_base
);
1380 /* Check if C has any other case-equivalents. */
1381 TRANSLATE (inverse
, inverse_trt
, c
);
1382 /* If so, check if we can use boyer-moore. */
1383 if (c
!= inverse
&& boyer_moore_ok
)
1385 /* Check if all equivalents belong to the same
1386 group of characters. Note that the check of C
1387 itself is done by the last iteration. */
1388 int this_char_base
= -1;
1390 while (boyer_moore_ok
)
1392 if (ASCII_BYTE_P (inverse
))
1394 if (this_char_base
> 0)
1399 else if (CHAR_BYTE8_P (inverse
))
1400 /* Boyer-moore search can't handle a
1401 translation of an eight-bit
1404 else if (this_char_base
< 0)
1406 this_char_base
= inverse
& ~0x3F;
1408 char_base
= this_char_base
;
1409 else if (this_char_base
!= char_base
)
1412 else if ((inverse
& ~0x3F) != this_char_base
)
1416 TRANSLATE (inverse
, inverse_trt
, inverse
);
1421 /* Store this character into the translated pattern. */
1422 bcopy (str
, pat
, charlen
);
1424 base_pat
+= in_charlen
;
1425 len_byte
-= in_charlen
;
1428 /* If char_base is still negative we didn't find any translated
1429 non-ASCII characters. */
1435 /* Unibyte buffer. */
1441 /* If we got here and the RE flag is set, it's because we're
1442 dealing with a regexp known to be trivial, so the backslash
1443 just quotes the next character. */
1444 if (RE
&& *base_pat
== '\\')
1451 TRANSLATE (translated
, trt
, c
);
1452 *pat
++ = translated
;
1456 len_byte
= pat
- patbuf
;
1457 len
= raw_pattern_size
;
1458 pat
= base_pat
= patbuf
;
1461 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1462 pos
, pos_byte
, lim
, lim_byte
,
1465 return simple_search (n
, pat
, len
, len_byte
, trt
,
1466 pos
, pos_byte
, lim
, lim_byte
);
1470 /* Do a simple string search N times for the string PAT,
1471 whose length is LEN/LEN_BYTE,
1472 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1473 TRT is the translation table.
1475 Return the character position where the match is found.
1476 Otherwise, if M matches remained to be found, return -M.
1478 This kind of search works regardless of what is in PAT and
1479 regardless of what is in TRT. It is used in cases where
1480 boyer_moore cannot work. */
1483 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1488 EMACS_INT pos
, pos_byte
;
1489 EMACS_INT lim
, lim_byte
;
1491 int multibyte
= ! NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
));
1492 int forward
= n
> 0;
1493 /* Number of buffer bytes matched. Note that this may be different
1494 from len_byte in a multibyte buffer. */
1497 if (lim
> pos
&& multibyte
)
1502 /* Try matching at position POS. */
1503 EMACS_INT this_pos
= pos
;
1504 EMACS_INT this_pos_byte
= pos_byte
;
1506 unsigned char *p
= pat
;
1507 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1510 while (this_len
> 0)
1512 int charlen
, buf_charlen
;
1515 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1516 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1518 TRANSLATE (buf_ch
, trt
, buf_ch
);
1520 if (buf_ch
!= pat_ch
)
1526 this_pos_byte
+= buf_charlen
;
1532 match_byte
= this_pos_byte
- pos_byte
;
1534 pos_byte
+= match_byte
;
1538 INC_BOTH (pos
, pos_byte
);
1548 /* Try matching at position POS. */
1549 EMACS_INT this_pos
= pos
;
1551 unsigned char *p
= pat
;
1553 if (pos
+ len
> lim
)
1556 while (this_len
> 0)
1559 int buf_ch
= FETCH_BYTE (this_pos
);
1560 TRANSLATE (buf_ch
, trt
, buf_ch
);
1562 if (buf_ch
!= pat_ch
)
1581 /* Backwards search. */
1582 else if (lim
< pos
&& multibyte
)
1587 /* Try matching at position POS. */
1588 EMACS_INT this_pos
= pos
;
1589 EMACS_INT this_pos_byte
= pos_byte
;
1591 const unsigned char *p
= pat
+ len_byte
;
1593 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1596 while (this_len
> 0)
1601 DEC_BOTH (this_pos
, this_pos_byte
);
1602 PREV_CHAR_BOUNDARY (p
, pat
);
1603 pat_ch
= STRING_CHAR (p
);
1604 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1605 TRANSLATE (buf_ch
, trt
, buf_ch
);
1607 if (buf_ch
!= pat_ch
)
1615 match_byte
= pos_byte
- this_pos_byte
;
1617 pos_byte
= this_pos_byte
;
1621 DEC_BOTH (pos
, pos_byte
);
1631 /* Try matching at position POS. */
1632 EMACS_INT this_pos
= pos
- len
;
1634 unsigned char *p
= pat
;
1639 while (this_len
> 0)
1642 int buf_ch
= FETCH_BYTE (this_pos
);
1643 TRANSLATE (buf_ch
, trt
, buf_ch
);
1645 if (buf_ch
!= pat_ch
)
1668 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1670 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1680 /* Do Boyer-Moore search N times for the string BASE_PAT,
1681 whose length is LEN/LEN_BYTE,
1682 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1683 DIRECTION says which direction we search in.
1684 TRT and INVERSE_TRT are translation tables.
1685 Characters in PAT are already translated by TRT.
1687 This kind of search works if all the characters in BASE_PAT that
1688 have nontrivial translation are the same aside from the last byte.
1689 This makes it possible to translate just the last byte of a
1690 character, and do so after just a simple test of the context.
1691 CHAR_BASE is nonzero if there is such a non-ASCII character.
1693 If that criterion is not satisfied, do not call this function. */
1696 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1697 pos
, pos_byte
, lim
, lim_byte
, char_base
)
1699 unsigned char *base_pat
;
1702 Lisp_Object inverse_trt
;
1703 EMACS_INT pos
, pos_byte
;
1704 EMACS_INT lim
, lim_byte
;
1707 int direction
= ((n
> 0) ? 1 : -1);
1708 register int dirlen
;
1710 int stride_for_teases
= 0;
1712 register unsigned char *cursor
, *p_limit
;
1714 unsigned char *pat
, *pat_end
;
1715 int multibyte
= ! NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
));
1717 unsigned char simple_translate
[0400];
1718 /* These are set to the preceding bytes of a byte to be translated
1719 if char_base is nonzero. As the maximum byte length of a
1720 multibyte character is 5, we have to check at most four previous
1722 int translate_prev_byte1
= 0;
1723 int translate_prev_byte2
= 0;
1724 int translate_prev_byte3
= 0;
1725 int translate_prev_byte4
= 0;
1727 /* The general approach is that we are going to maintain that we know
1728 the first (closest to the present position, in whatever direction
1729 we're searching) character that could possibly be the last
1730 (furthest from present position) character of a valid match. We
1731 advance the state of our knowledge by looking at that character
1732 and seeing whether it indeed matches the last character of the
1733 pattern. If it does, we take a closer look. If it does not, we
1734 move our pointer (to putative last characters) as far as is
1735 logically possible. This amount of movement, which I call a
1736 stride, will be the length of the pattern if the actual character
1737 appears nowhere in the pattern, otherwise it will be the distance
1738 from the last occurrence of that character to the end of the
1739 pattern. If the amount is zero we have a possible match. */
1741 /* Here we make a "mickey mouse" BM table. The stride of the search
1742 is determined only by the last character of the putative match.
1743 If that character does not match, we will stride the proper
1744 distance to propose a match that superimposes it on the last
1745 instance of a character that matches it (per trt), or misses
1746 it entirely if there is none. */
1748 dirlen
= len_byte
* direction
;
1750 /* Record position after the end of the pattern. */
1751 pat_end
= base_pat
+ len_byte
;
1752 /* BASE_PAT points to a character that we start scanning from.
1753 It is the first character in a forward search,
1754 the last character in a backward search. */
1756 base_pat
= pat_end
- 1;
1758 /* A character that does not appear in the pattern induces a
1759 stride equal to the pattern length. */
1760 for (i
= 0; i
< 0400; i
++)
1763 /* We use this for translation, instead of TRT itself.
1764 We fill this in to handle the characters that actually
1765 occur in the pattern. Others don't matter anyway! */
1766 for (i
= 0; i
< 0400; i
++)
1767 simple_translate
[i
] = i
;
1771 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1772 byte following them are the target of translation. */
1773 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1774 int len
= CHAR_STRING (char_base
, str
);
1776 translate_prev_byte1
= str
[len
- 2];
1779 translate_prev_byte2
= str
[len
- 3];
1782 translate_prev_byte3
= str
[len
- 4];
1784 translate_prev_byte4
= str
[len
- 5];
1792 unsigned char *ptr
= base_pat
+ i
;
1796 /* If the byte currently looking at is the last of a
1797 character to check case-equivalents, set CH to that
1798 character. An ASCII character and a non-ASCII character
1799 matching with CHAR_BASE are to be checked. */
1802 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1805 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1807 unsigned char *charstart
= ptr
- 1;
1809 while (! (CHAR_HEAD_P (*charstart
)))
1811 ch
= STRING_CHAR (charstart
);
1812 if (char_base
!= (ch
& ~0x3F))
1817 j
= (ch
& 0x3F) | 0200;
1822 stride_for_teases
= BM_tab
[j
];
1824 BM_tab
[j
] = dirlen
- i
;
1825 /* A translation table is accompanied by its inverse -- see */
1826 /* comment following downcase_table for details */
1829 int starting_ch
= ch
;
1834 TRANSLATE (ch
, inverse_trt
, ch
);
1836 j
= (ch
& 0x3F) | 0200;
1840 /* For all the characters that map into CH,
1841 set up simple_translate to map the last byte
1843 simple_translate
[j
] = starting_j
;
1844 if (ch
== starting_ch
)
1846 BM_tab
[j
] = dirlen
- i
;
1855 stride_for_teases
= BM_tab
[j
];
1856 BM_tab
[j
] = dirlen
- i
;
1858 /* stride_for_teases tells how much to stride if we get a
1859 match on the far character but are subsequently
1860 disappointed, by recording what the stride would have been
1861 for that character if the last character had been
1864 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1865 /* loop invariant - POS_BYTE points at where last char (first
1866 char if reverse) of pattern would align in a possible match. */
1870 unsigned char *tail_end_ptr
;
1872 /* It's been reported that some (broken) compiler thinks that
1873 Boolean expressions in an arithmetic context are unsigned.
1874 Using an explicit ?1:0 prevents this. */
1875 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1877 return (n
* (0 - direction
));
1878 /* First we do the part we can by pointers (maybe nothing) */
1881 limit
= pos_byte
- dirlen
+ direction
;
1884 limit
= BUFFER_CEILING_OF (limit
);
1885 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1886 can take on without hitting edge of buffer or the gap. */
1887 limit
= min (limit
, pos_byte
+ 20000);
1888 limit
= min (limit
, lim_byte
- 1);
1892 limit
= BUFFER_FLOOR_OF (limit
);
1893 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1894 can take on without hitting edge of buffer or the gap. */
1895 limit
= max (limit
, pos_byte
- 20000);
1896 limit
= max (limit
, lim_byte
);
1898 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1899 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1901 if ((limit
- pos_byte
) * direction
> 20)
1905 p_limit
= BYTE_POS_ADDR (limit
);
1906 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1907 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1908 while (1) /* use one cursor setting as long as i can */
1910 if (direction
> 0) /* worth duplicating */
1912 while (cursor
<= p_limit
)
1914 if (BM_tab
[*cursor
] == 0)
1916 cursor
+= BM_tab
[*cursor
];
1921 while (cursor
>= p_limit
)
1923 if (BM_tab
[*cursor
] == 0)
1925 cursor
+= BM_tab
[*cursor
];
1928 /* If you are here, cursor is beyond the end of the
1929 searched region. You fail to match within the
1930 permitted region and would otherwise try a character
1931 beyond that region. */
1935 i
= dirlen
- direction
;
1938 while ((i
-= direction
) + direction
!= 0)
1941 cursor
-= direction
;
1942 /* Translate only the last byte of a character. */
1944 || ((cursor
== tail_end_ptr
1945 || CHAR_HEAD_P (cursor
[1]))
1946 && (CHAR_HEAD_P (cursor
[0])
1947 /* Check if this is the last byte of
1948 a translable character. */
1949 || (translate_prev_byte1
== cursor
[-1]
1950 && (CHAR_HEAD_P (translate_prev_byte1
)
1951 || (translate_prev_byte2
== cursor
[-2]
1952 && (CHAR_HEAD_P (translate_prev_byte2
)
1953 || (translate_prev_byte3
== cursor
[-3]))))))))
1954 ch
= simple_translate
[*cursor
];
1963 while ((i
-= direction
) + direction
!= 0)
1965 cursor
-= direction
;
1966 if (pat
[i
] != *cursor
)
1970 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1971 if (i
+ direction
== 0)
1973 EMACS_INT position
, start
, end
;
1975 cursor
-= direction
;
1977 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1978 ? 1 - len_byte
: 0);
1979 set_search_regs (position
, len_byte
);
1981 if (NILP (Vinhibit_changing_match_data
))
1983 start
= search_regs
.start
[0];
1984 end
= search_regs
.end
[0];
1987 /* If Vinhibit_changing_match_data is non-nil,
1988 search_regs will not be changed. So let's
1989 compute start and end here. */
1991 start
= BYTE_TO_CHAR (position
);
1992 end
= BYTE_TO_CHAR (position
+ len_byte
);
1995 if ((n
-= direction
) != 0)
1996 cursor
+= dirlen
; /* to resume search */
1998 return direction
> 0 ? end
: start
;
2001 cursor
+= stride_for_teases
; /* <sigh> we lose - */
2003 pos_byte
+= cursor
- p2
;
2006 /* Now we'll pick up a clump that has to be done the hard
2007 way because it covers a discontinuity. */
2009 limit
= ((direction
> 0)
2010 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
2011 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
2012 limit
= ((direction
> 0)
2013 ? min (limit
+ len_byte
, lim_byte
- 1)
2014 : max (limit
- len_byte
, lim_byte
));
2015 /* LIMIT is now the last value POS_BYTE can have
2016 and still be valid for a possible match. */
2019 /* This loop can be coded for space rather than
2020 speed because it will usually run only once.
2021 (the reach is at most len + 21, and typically
2022 does not exceed len). */
2023 while ((limit
- pos_byte
) * direction
>= 0)
2025 int ch
= FETCH_BYTE (pos_byte
);
2026 if (BM_tab
[ch
] == 0)
2028 pos_byte
+= BM_tab
[ch
];
2030 break; /* ran off the end */
2033 /* Found what might be a match. */
2034 i
= dirlen
- direction
;
2035 while ((i
-= direction
) + direction
!= 0)
2039 pos_byte
-= direction
;
2040 ptr
= BYTE_POS_ADDR (pos_byte
);
2041 /* Translate only the last byte of a character. */
2043 || ((ptr
== tail_end_ptr
2044 || CHAR_HEAD_P (ptr
[1]))
2045 && (CHAR_HEAD_P (ptr
[0])
2046 /* Check if this is the last byte of a
2047 translable character. */
2048 || (translate_prev_byte1
== ptr
[-1]
2049 && (CHAR_HEAD_P (translate_prev_byte1
)
2050 || (translate_prev_byte2
== ptr
[-2]
2051 && (CHAR_HEAD_P (translate_prev_byte2
)
2052 || translate_prev_byte3
== ptr
[-3])))))))
2053 ch
= simple_translate
[*ptr
];
2059 /* Above loop has moved POS_BYTE part or all the way
2060 back to the first pos (last pos if reverse).
2061 Set it once again at the last (first if reverse) char. */
2062 pos_byte
+= dirlen
- i
- direction
;
2063 if (i
+ direction
== 0)
2065 EMACS_INT position
, start
, end
;
2066 pos_byte
-= direction
;
2068 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2069 set_search_regs (position
, len_byte
);
2071 if (NILP (Vinhibit_changing_match_data
))
2073 start
= search_regs
.start
[0];
2074 end
= search_regs
.end
[0];
2077 /* If Vinhibit_changing_match_data is non-nil,
2078 search_regs will not be changed. So let's
2079 compute start and end here. */
2081 start
= BYTE_TO_CHAR (position
);
2082 end
= BYTE_TO_CHAR (position
+ len_byte
);
2085 if ((n
-= direction
) != 0)
2086 pos_byte
+= dirlen
; /* to resume search */
2088 return direction
> 0 ? end
: start
;
2091 pos_byte
+= stride_for_teases
;
2094 /* We have done one clump. Can we continue? */
2095 if ((lim_byte
- pos_byte
) * direction
< 0)
2096 return ((0 - n
) * direction
);
2098 return BYTE_TO_CHAR (pos_byte
);
2101 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2102 for the overall match just found in the current buffer.
2103 Also clear out the match data for registers 1 and up. */
2106 set_search_regs (beg_byte
, nbytes
)
2107 EMACS_INT beg_byte
, nbytes
;
2111 if (!NILP (Vinhibit_changing_match_data
))
2114 /* Make sure we have registers in which to store
2115 the match position. */
2116 if (search_regs
.num_regs
== 0)
2118 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2119 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2120 search_regs
.num_regs
= 2;
2123 /* Clear out the other registers. */
2124 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2126 search_regs
.start
[i
] = -1;
2127 search_regs
.end
[i
] = -1;
2130 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2131 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2132 XSETBUFFER (last_thing_searched
, current_buffer
);
2135 /* Given STRING, a string of words separated by word delimiters,
2136 compute a regexp that matches those exact words separated by
2137 arbitrary punctuation. If LAX is nonzero, the end of the string
2138 need not match a word boundary unless it ends in whitespace. */
2141 wordify (string
, lax
)
2145 register unsigned char *p
, *o
;
2146 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
2149 int adjust
, whitespace_at_end
;
2151 CHECK_STRING (string
);
2153 len
= SCHARS (string
);
2155 for (i
= 0, i_byte
= 0; i
< len
; )
2159 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
2161 if (SYNTAX (c
) != Sword
)
2164 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
2171 if (SYNTAX (prev_c
) == Sword
)
2174 whitespace_at_end
= 0;
2177 whitespace_at_end
= 1;
2180 return empty_unibyte_string
;
2182 adjust
= - punct_count
+ 5 * (word_count
- 1)
2183 + ((lax
&& !whitespace_at_end
) ? 2 : 4);
2184 if (STRING_MULTIBYTE (string
))
2185 val
= make_uninit_multibyte_string (len
+ adjust
,
2189 val
= make_uninit_string (len
+ adjust
);
2196 for (i
= 0, i_byte
= 0; i
< len
; )
2199 int i_byte_orig
= i_byte
;
2201 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
2203 if (SYNTAX (c
) == Sword
)
2205 bcopy (SDATA (string
) + i_byte_orig
, o
,
2206 i_byte
- i_byte_orig
);
2207 o
+= i_byte
- i_byte_orig
;
2209 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
2221 if (!lax
|| whitespace_at_end
)
2230 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2231 "MSearch backward: ",
2232 doc
: /* Search backward from point for STRING.
2233 Set point to the beginning of the occurrence found, and return point.
2234 An optional second argument bounds the search; it is a buffer position.
2235 The match found must not extend before that position.
2236 Optional third argument, if t, means if fail just return nil (no error).
2237 If not nil and not t, position at limit of search and return nil.
2238 Optional fourth argument is repeat count--search for successive occurrences.
2240 Search case-sensitivity is determined by the value of the variable
2241 `case-fold-search', which see.
2243 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2244 (string
, bound
, noerror
, count
)
2245 Lisp_Object string
, bound
, noerror
, count
;
2247 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2250 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2251 doc
: /* Search forward from point for STRING.
2252 Set point to the end of the occurrence found, and return point.
2253 An optional second argument bounds the search; it is a buffer position.
2254 The match found must not extend after that position. A value of nil is
2255 equivalent to (point-max).
2256 Optional third argument, if t, means if fail just return nil (no error).
2257 If not nil and not t, move to limit of search and return nil.
2258 Optional fourth argument is repeat count--search for successive occurrences.
2260 Search case-sensitivity is determined by the value of the variable
2261 `case-fold-search', which see.
2263 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2264 (string
, bound
, noerror
, count
)
2265 Lisp_Object string
, bound
, noerror
, count
;
2267 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2270 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2271 "sWord search backward: ",
2272 doc
: /* Search backward from point for STRING, ignoring differences in punctuation.
2273 Set point to the beginning of the occurrence found, and return point.
2274 An optional second argument bounds the search; it is a buffer position.
2275 The match found must not extend before that position.
2276 Optional third argument, if t, means if fail just return nil (no error).
2277 If not nil and not t, move to limit of search and return nil.
2278 Optional fourth argument is repeat count--search for successive occurrences. */)
2279 (string
, bound
, noerror
, count
)
2280 Lisp_Object string
, bound
, noerror
, count
;
2282 return search_command (wordify (string
, 0), bound
, noerror
, count
, -1, 1, 0);
2285 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2287 doc
: /* Search forward from point for STRING, ignoring differences in punctuation.
2288 Set point to the end of the occurrence found, and return point.
2289 An optional second argument bounds the search; it is a buffer position.
2290 The match found must not extend after that position.
2291 Optional third argument, if t, means if fail just return nil (no error).
2292 If not nil and not t, move to limit of search and return nil.
2293 Optional fourth argument is repeat count--search for successive occurrences. */)
2294 (string
, bound
, noerror
, count
)
2295 Lisp_Object string
, bound
, noerror
, count
;
2297 return search_command (wordify (string
, 0), bound
, noerror
, count
, 1, 1, 0);
2300 DEFUN ("word-search-backward-lax", Fword_search_backward_lax
, Sword_search_backward_lax
, 1, 4,
2301 "sWord search backward: ",
2302 doc
: /* Search backward from point for STRING, ignoring differences in punctuation.
2303 Set point to the beginning of the occurrence found, and return point.
2305 Unlike `word-search-backward', the end of STRING need not match a word
2306 boundary unless it ends in whitespace.
2308 An optional second argument bounds the search; it is a buffer position.
2309 The match found must not extend before that position.
2310 Optional third argument, if t, means if fail just return nil (no error).
2311 If not nil and not t, move to limit of search and return nil.
2312 Optional fourth argument is repeat count--search for successive occurrences. */)
2313 (string
, bound
, noerror
, count
)
2314 Lisp_Object string
, bound
, noerror
, count
;
2316 return search_command (wordify (string
, 1), bound
, noerror
, count
, -1, 1, 0);
2319 DEFUN ("word-search-forward-lax", Fword_search_forward_lax
, Sword_search_forward_lax
, 1, 4,
2321 doc
: /* Search forward from point for STRING, ignoring differences in punctuation.
2322 Set point to the end of the occurrence found, and return point.
2324 Unlike `word-search-forward', the end of STRING need not match a word
2325 boundary unless it ends in whitespace.
2327 An optional second argument bounds the search; it is a buffer position.
2328 The match found must not extend after that position.
2329 Optional third argument, if t, means if fail just return nil (no error).
2330 If not nil and not t, move to limit of search and return nil.
2331 Optional fourth argument is repeat count--search for successive occurrences. */)
2332 (string
, bound
, noerror
, count
)
2333 Lisp_Object string
, bound
, noerror
, count
;
2335 return search_command (wordify (string
, 1), bound
, noerror
, count
, 1, 1, 0);
2338 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2339 "sRE search backward: ",
2340 doc
: /* Search backward from point for match for regular expression REGEXP.
2341 Set point to the beginning of the match, and return point.
2342 The match found is the one starting last in the buffer
2343 and yet ending before the origin of the search.
2344 An optional second argument bounds the search; it is a buffer position.
2345 The match found must start at or after that position.
2346 Optional third argument, if t, means if fail just return nil (no error).
2347 If not nil and not t, move to limit of search and return nil.
2348 Optional fourth argument is repeat count--search for successive occurrences.
2349 See also the functions `match-beginning', `match-end', `match-string',
2350 and `replace-match'. */)
2351 (regexp
, bound
, noerror
, count
)
2352 Lisp_Object regexp
, bound
, noerror
, count
;
2354 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2357 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2359 doc
: /* Search forward from point for regular expression REGEXP.
2360 Set point to the end of the occurrence found, and return point.
2361 An optional second argument bounds the search; it is a buffer position.
2362 The match found must not extend after that position.
2363 Optional third argument, if t, means if fail just return nil (no error).
2364 If not nil and not t, move to limit of search and return nil.
2365 Optional fourth argument is repeat count--search for successive occurrences.
2366 See also the functions `match-beginning', `match-end', `match-string',
2367 and `replace-match'. */)
2368 (regexp
, bound
, noerror
, count
)
2369 Lisp_Object regexp
, bound
, noerror
, count
;
2371 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2374 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2375 "sPosix search backward: ",
2376 doc
: /* Search backward from point for match for regular expression REGEXP.
2377 Find the longest match in accord with Posix regular expression rules.
2378 Set point to the beginning of the match, and return point.
2379 The match found is the one starting last in the buffer
2380 and yet ending before the origin of the search.
2381 An optional second argument bounds the search; it is a buffer position.
2382 The match found must start at or after that position.
2383 Optional third argument, if t, means if fail just return nil (no error).
2384 If not nil and not t, move to limit of search and return nil.
2385 Optional fourth argument is repeat count--search for successive occurrences.
2386 See also the functions `match-beginning', `match-end', `match-string',
2387 and `replace-match'. */)
2388 (regexp
, bound
, noerror
, count
)
2389 Lisp_Object regexp
, bound
, noerror
, count
;
2391 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2394 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2396 doc
: /* Search forward from point for regular expression REGEXP.
2397 Find the longest match in accord with Posix regular expression rules.
2398 Set point to the end of the occurrence found, and return point.
2399 An optional second argument bounds the search; it is a buffer position.
2400 The match found must not extend after that position.
2401 Optional third argument, if t, means if fail just return nil (no error).
2402 If not nil and not t, move to limit of search and return nil.
2403 Optional fourth argument is repeat count--search for successive occurrences.
2404 See also the functions `match-beginning', `match-end', `match-string',
2405 and `replace-match'. */)
2406 (regexp
, bound
, noerror
, count
)
2407 Lisp_Object regexp
, bound
, noerror
, count
;
2409 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2412 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2413 doc
: /* Replace text matched by last search with NEWTEXT.
2414 Leave point at the end of the replacement text.
2416 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2417 Otherwise maybe capitalize the whole text, or maybe just word initials,
2418 based on the replaced text.
2419 If the replaced text has only capital letters
2420 and has at least one multiletter word, convert NEWTEXT to all caps.
2421 Otherwise if all words are capitalized in the replaced text,
2422 capitalize each word in NEWTEXT.
2424 If third arg LITERAL is non-nil, insert NEWTEXT literally.
2425 Otherwise treat `\\' as special:
2426 `\\&' in NEWTEXT means substitute original matched text.
2427 `\\N' means substitute what matched the Nth `\\(...\\)'.
2428 If Nth parens didn't match, substitute nothing.
2429 `\\\\' means insert one `\\'.
2430 Case conversion does not apply to these substitutions.
2432 FIXEDCASE and LITERAL are optional arguments.
2434 The optional fourth argument STRING can be a string to modify.
2435 This is meaningful when the previous match was done against STRING,
2436 using `string-match'. When used this way, `replace-match'
2437 creates and returns a new string made by copying STRING and replacing
2438 the part of STRING that was matched.
2440 The optional fifth argument SUBEXP specifies a subexpression;
2441 it says to replace just that subexpression with NEWTEXT,
2442 rather than replacing the entire matched text.
2443 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2444 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2445 NEWTEXT in place of subexp N.
2446 This is useful only after a regular expression search or match,
2447 since only regular expressions have distinguished subexpressions. */)
2448 (newtext
, fixedcase
, literal
, string
, subexp
)
2449 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2451 enum { nochange
, all_caps
, cap_initial
} case_action
;
2452 register int pos
, pos_byte
;
2453 int some_multiletter_word
;
2456 int some_nonuppercase_initial
;
2457 register int c
, prevc
;
2459 EMACS_INT opoint
, newpoint
;
2461 CHECK_STRING (newtext
);
2463 if (! NILP (string
))
2464 CHECK_STRING (string
);
2466 case_action
= nochange
; /* We tried an initialization */
2467 /* but some C compilers blew it */
2469 if (search_regs
.num_regs
<= 0)
2470 error ("`replace-match' called before any match found");
2476 CHECK_NUMBER (subexp
);
2477 sub
= XINT (subexp
);
2478 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2479 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2484 if (search_regs
.start
[sub
] < BEGV
2485 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2486 || search_regs
.end
[sub
] > ZV
)
2487 args_out_of_range (make_number (search_regs
.start
[sub
]),
2488 make_number (search_regs
.end
[sub
]));
2492 if (search_regs
.start
[sub
] < 0
2493 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2494 || search_regs
.end
[sub
] > SCHARS (string
))
2495 args_out_of_range (make_number (search_regs
.start
[sub
]),
2496 make_number (search_regs
.end
[sub
]));
2499 if (NILP (fixedcase
))
2501 /* Decide how to casify by examining the matched text. */
2504 pos
= search_regs
.start
[sub
];
2505 last
= search_regs
.end
[sub
];
2508 pos_byte
= CHAR_TO_BYTE (pos
);
2510 pos_byte
= string_char_to_byte (string
, pos
);
2513 case_action
= all_caps
;
2515 /* some_multiletter_word is set nonzero if any original word
2516 is more than one letter long. */
2517 some_multiletter_word
= 0;
2519 some_nonuppercase_initial
= 0;
2526 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2527 INC_BOTH (pos
, pos_byte
);
2530 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2534 /* Cannot be all caps if any original char is lower case */
2537 if (SYNTAX (prevc
) != Sword
)
2538 some_nonuppercase_initial
= 1;
2540 some_multiletter_word
= 1;
2542 else if (UPPERCASEP (c
))
2545 if (SYNTAX (prevc
) != Sword
)
2548 some_multiletter_word
= 1;
2552 /* If the initial is a caseless word constituent,
2553 treat that like a lowercase initial. */
2554 if (SYNTAX (prevc
) != Sword
)
2555 some_nonuppercase_initial
= 1;
2561 /* Convert to all caps if the old text is all caps
2562 and has at least one multiletter word. */
2563 if (! some_lowercase
&& some_multiletter_word
)
2564 case_action
= all_caps
;
2565 /* Capitalize each word, if the old text has all capitalized words. */
2566 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2567 case_action
= cap_initial
;
2568 else if (!some_nonuppercase_initial
&& some_uppercase
)
2569 /* Should x -> yz, operating on X, give Yz or YZ?
2570 We'll assume the latter. */
2571 case_action
= all_caps
;
2573 case_action
= nochange
;
2576 /* Do replacement in a string. */
2579 Lisp_Object before
, after
;
2581 before
= Fsubstring (string
, make_number (0),
2582 make_number (search_regs
.start
[sub
]));
2583 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2585 /* Substitute parts of the match into NEWTEXT
2589 EMACS_INT lastpos
= 0;
2590 EMACS_INT lastpos_byte
= 0;
2591 /* We build up the substituted string in ACCUM. */
2594 int length
= SBYTES (newtext
);
2598 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2602 int delbackslash
= 0;
2604 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2608 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2612 substart
= search_regs
.start
[sub
];
2613 subend
= search_regs
.end
[sub
];
2615 else if (c
>= '1' && c
<= '9')
2617 if (search_regs
.start
[c
- '0'] >= 0
2618 && c
<= search_regs
.num_regs
+ '0')
2620 substart
= search_regs
.start
[c
- '0'];
2621 subend
= search_regs
.end
[c
- '0'];
2625 /* If that subexp did not match,
2626 replace \\N with nothing. */
2634 error ("Invalid use of `\\' in replacement text");
2638 if (pos
- 2 != lastpos
)
2639 middle
= substring_both (newtext
, lastpos
,
2641 pos
- 2, pos_byte
- 2);
2644 accum
= concat3 (accum
, middle
,
2646 make_number (substart
),
2647 make_number (subend
)));
2649 lastpos_byte
= pos_byte
;
2651 else if (delbackslash
)
2653 middle
= substring_both (newtext
, lastpos
,
2655 pos
- 1, pos_byte
- 1);
2657 accum
= concat2 (accum
, middle
);
2659 lastpos_byte
= pos_byte
;
2664 middle
= substring_both (newtext
, lastpos
,
2670 newtext
= concat2 (accum
, middle
);
2673 /* Do case substitution in NEWTEXT if desired. */
2674 if (case_action
== all_caps
)
2675 newtext
= Fupcase (newtext
);
2676 else if (case_action
== cap_initial
)
2677 newtext
= Fupcase_initials (newtext
);
2679 return concat3 (before
, newtext
, after
);
2682 /* Record point, then move (quietly) to the start of the match. */
2683 if (PT
>= search_regs
.end
[sub
])
2685 else if (PT
> search_regs
.start
[sub
])
2686 opoint
= search_regs
.end
[sub
] - ZV
;
2690 /* If we want non-literal replacement,
2691 perform substitution on the replacement string. */
2694 int length
= SBYTES (newtext
);
2695 unsigned char *substed
;
2696 int substed_alloc_size
, substed_len
;
2697 int buf_multibyte
= !NILP (BUF_ENABLE_MULTIBYTE_CHARACTERS (current_buffer
));
2698 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2699 Lisp_Object rev_tbl
;
2700 int really_changed
= 0;
2704 substed_alloc_size
= length
* 2 + 100;
2705 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2708 /* Go thru NEWTEXT, producing the actual text to insert in
2709 SUBSTED while adjusting multibyteness to that of the current
2712 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2714 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2715 unsigned char *add_stuff
= NULL
;
2721 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2723 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2727 /* Note that we don't have to increment POS. */
2728 c
= SREF (newtext
, pos_byte
++);
2730 MAKE_CHAR_MULTIBYTE (c
);
2733 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2734 or set IDX to a match index, which means put that part
2735 of the buffer text into SUBSTED. */
2743 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2745 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2746 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2750 c
= SREF (newtext
, pos_byte
++);
2752 MAKE_CHAR_MULTIBYTE (c
);
2757 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2759 if (search_regs
.start
[c
- '0'] >= 1)
2763 add_len
= 1, add_stuff
= "\\";
2767 error ("Invalid use of `\\' in replacement text");
2772 add_len
= CHAR_STRING (c
, str
);
2776 /* If we want to copy part of a previous match,
2777 set up ADD_STUFF and ADD_LEN to point to it. */
2780 EMACS_INT begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2781 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2782 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2783 move_gap (search_regs
.start
[idx
]);
2784 add_stuff
= BYTE_POS_ADDR (begbyte
);
2787 /* Now the stuff we want to add to SUBSTED
2788 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2790 /* Make sure SUBSTED is big enough. */
2791 if (substed_len
+ add_len
>= substed_alloc_size
)
2793 substed_alloc_size
= substed_len
+ add_len
+ 500;
2794 substed
= (unsigned char *) xrealloc (substed
,
2795 substed_alloc_size
+ 1);
2798 /* Now add to the end of SUBSTED. */
2801 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2802 substed_len
+= add_len
;
2810 int nchars
= multibyte_chars_in_text (substed
, substed_len
);
2812 newtext
= make_multibyte_string (substed
, nchars
, substed_len
);
2815 newtext
= make_unibyte_string (substed
, substed_len
);
2820 /* Replace the old text with the new in the cleanest possible way. */
2821 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2823 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2825 if (case_action
== all_caps
)
2826 Fupcase_region (make_number (search_regs
.start
[sub
]),
2827 make_number (newpoint
));
2828 else if (case_action
== cap_initial
)
2829 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2830 make_number (newpoint
));
2832 /* Adjust search data for this change. */
2834 EMACS_INT oldend
= search_regs
.end
[sub
];
2835 EMACS_INT oldstart
= search_regs
.start
[sub
];
2836 EMACS_INT change
= newpoint
- search_regs
.end
[sub
];
2839 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2841 if (search_regs
.start
[i
] >= oldend
)
2842 search_regs
.start
[i
] += change
;
2843 else if (search_regs
.start
[i
] > oldstart
)
2844 search_regs
.start
[i
] = oldstart
;
2845 if (search_regs
.end
[i
] >= oldend
)
2846 search_regs
.end
[i
] += change
;
2847 else if (search_regs
.end
[i
] > oldstart
)
2848 search_regs
.end
[i
] = oldstart
;
2852 /* Put point back where it was in the text. */
2854 TEMP_SET_PT (opoint
+ ZV
);
2856 TEMP_SET_PT (opoint
);
2858 /* Now move point "officially" to the start of the inserted replacement. */
2859 move_if_not_intangible (newpoint
);
2865 match_limit (num
, beginningp
)
2874 args_out_of_range (num
, make_number (0));
2875 if (search_regs
.num_regs
<= 0)
2876 error ("No match data, because no search succeeded");
2877 if (n
>= search_regs
.num_regs
2878 || search_regs
.start
[n
] < 0)
2880 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2881 : search_regs
.end
[n
]));
2884 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2885 doc
: /* Return position of start of text matched by last search.
2886 SUBEXP, a number, specifies which parenthesized expression in the last
2888 Value is nil if SUBEXPth pair didn't match, or there were less than
2890 Zero means the entire text matched by the whole regexp or whole string. */)
2894 return match_limit (subexp
, 1);
2897 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2898 doc
: /* Return position of end of text matched by last search.
2899 SUBEXP, a number, specifies which parenthesized expression in the last
2901 Value is nil if SUBEXPth pair didn't match, or there were less than
2903 Zero means the entire text matched by the whole regexp or whole string. */)
2907 return match_limit (subexp
, 0);
2910 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2911 doc
: /* Return a list containing all info on what the last search matched.
2912 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2913 All the elements are markers or nil (nil if the Nth pair didn't match)
2914 if the last match was on a buffer; integers or nil if a string was matched.
2915 Use `set-match-data' to reinstate the data in this list.
2917 If INTEGERS (the optional first argument) is non-nil, always use
2918 integers \(rather than markers) to represent buffer positions. In
2919 this case, and if the last match was in a buffer, the buffer will get
2920 stored as one additional element at the end of the list.
2922 If REUSE is a list, reuse it as part of the value. If REUSE is long
2923 enough to hold all the values, and if INTEGERS is non-nil, no consing
2926 If optional third arg RESEAT is non-nil, any previous markers on the
2927 REUSE list will be modified to point to nowhere.
2929 Return value is undefined if the last search failed. */)
2930 (integers
, reuse
, reseat
)
2931 Lisp_Object integers
, reuse
, reseat
;
2933 Lisp_Object tail
, prev
;
2938 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2939 if (MARKERP (XCAR (tail
)))
2941 unchain_marker (XMARKER (XCAR (tail
)));
2942 XSETCAR (tail
, Qnil
);
2945 if (NILP (last_thing_searched
))
2950 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
+ 1)
2951 * sizeof (Lisp_Object
));
2954 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2956 int start
= search_regs
.start
[i
];
2959 if (EQ (last_thing_searched
, Qt
)
2960 || ! NILP (integers
))
2962 XSETFASTINT (data
[2 * i
], start
);
2963 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2965 else if (BUFFERP (last_thing_searched
))
2967 data
[2 * i
] = Fmake_marker ();
2968 Fset_marker (data
[2 * i
],
2969 make_number (start
),
2970 last_thing_searched
);
2971 data
[2 * i
+ 1] = Fmake_marker ();
2972 Fset_marker (data
[2 * i
+ 1],
2973 make_number (search_regs
.end
[i
]),
2974 last_thing_searched
);
2977 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2983 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2986 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2988 data
[len
] = last_thing_searched
;
2992 /* If REUSE is not usable, cons up the values and return them. */
2993 if (! CONSP (reuse
))
2994 return Flist (len
, data
);
2996 /* If REUSE is a list, store as many value elements as will fit
2997 into the elements of REUSE. */
2998 for (i
= 0, tail
= reuse
; CONSP (tail
);
2999 i
++, tail
= XCDR (tail
))
3002 XSETCAR (tail
, data
[i
]);
3004 XSETCAR (tail
, Qnil
);
3008 /* If we couldn't fit all value elements into REUSE,
3009 cons up the rest of them and add them to the end of REUSE. */
3011 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
3016 /* We used to have an internal use variant of `reseat' described as:
3018 If RESEAT is `evaporate', put the markers back on the free list
3019 immediately. No other references to the markers must exist in this
3020 case, so it is used only internally on the unwind stack and
3021 save-match-data from Lisp.
3023 But it was ill-conceived: those supposedly-internal markers get exposed via
3024 the undo-list, so freeing them here is unsafe. */
3026 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
3027 doc
: /* Set internal data on last search match from elements of LIST.
3028 LIST should have been created by calling `match-data' previously.
3030 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
3032 register Lisp_Object list
, reseat
;
3035 register Lisp_Object marker
;
3037 if (running_asynch_code
)
3038 save_search_regs ();
3042 /* Unless we find a marker with a buffer or an explicit buffer
3043 in LIST, assume that this match data came from a string. */
3044 last_thing_searched
= Qt
;
3046 /* Allocate registers if they don't already exist. */
3048 int length
= XFASTINT (Flength (list
)) / 2;
3050 if (length
> search_regs
.num_regs
)
3052 if (search_regs
.num_regs
== 0)
3055 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
3057 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
3062 = (regoff_t
*) xrealloc (search_regs
.start
,
3063 length
* sizeof (regoff_t
));
3065 = (regoff_t
*) xrealloc (search_regs
.end
,
3066 length
* sizeof (regoff_t
));
3069 for (i
= search_regs
.num_regs
; i
< length
; i
++)
3070 search_regs
.start
[i
] = -1;
3072 search_regs
.num_regs
= length
;
3075 for (i
= 0; CONSP (list
); i
++)
3077 marker
= XCAR (list
);
3078 if (BUFFERP (marker
))
3080 last_thing_searched
= marker
;
3087 search_regs
.start
[i
] = -1;
3096 if (MARKERP (marker
))
3098 if (XMARKER (marker
)->buffer
== 0)
3099 XSETFASTINT (marker
, 0);
3101 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
3104 CHECK_NUMBER_COERCE_MARKER (marker
);
3105 from
= XINT (marker
);
3107 if (!NILP (reseat
) && MARKERP (m
))
3109 unchain_marker (XMARKER (m
));
3110 XSETCAR (list
, Qnil
);
3113 if ((list
= XCDR (list
), !CONSP (list
)))
3116 m
= marker
= XCAR (list
);
3118 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
3119 XSETFASTINT (marker
, 0);
3121 CHECK_NUMBER_COERCE_MARKER (marker
);
3122 search_regs
.start
[i
] = from
;
3123 search_regs
.end
[i
] = XINT (marker
);
3125 if (!NILP (reseat
) && MARKERP (m
))
3127 unchain_marker (XMARKER (m
));
3128 XSETCAR (list
, Qnil
);
3134 for (; i
< search_regs
.num_regs
; i
++)
3135 search_regs
.start
[i
] = -1;
3141 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3142 if asynchronous code (filter or sentinel) is running. */
3146 if (!search_regs_saved
)
3148 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3149 saved_search_regs
.start
= search_regs
.start
;
3150 saved_search_regs
.end
= search_regs
.end
;
3151 saved_last_thing_searched
= last_thing_searched
;
3152 last_thing_searched
= Qnil
;
3153 search_regs
.num_regs
= 0;
3154 search_regs
.start
= 0;
3155 search_regs
.end
= 0;
3157 search_regs_saved
= 1;
3161 /* Called upon exit from filters and sentinels. */
3163 restore_search_regs ()
3165 if (search_regs_saved
)
3167 if (search_regs
.num_regs
> 0)
3169 xfree (search_regs
.start
);
3170 xfree (search_regs
.end
);
3172 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3173 search_regs
.start
= saved_search_regs
.start
;
3174 search_regs
.end
= saved_search_regs
.end
;
3175 last_thing_searched
= saved_last_thing_searched
;
3176 saved_last_thing_searched
= Qnil
;
3177 search_regs_saved
= 0;
3182 unwind_set_match_data (list
)
3185 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3186 return Fset_match_data (list
, Qt
);
3189 /* Called to unwind protect the match data. */
3191 record_unwind_save_match_data ()
3193 record_unwind_protect (unwind_set_match_data
,
3194 Fmatch_data (Qnil
, Qnil
, Qnil
));
3197 /* Quote a string to inactivate reg-expr chars */
3199 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3200 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3204 register unsigned char *in
, *out
, *end
;
3205 register unsigned char *temp
;
3206 int backslashes_added
= 0;
3208 CHECK_STRING (string
);
3210 temp
= (unsigned char *) alloca (SBYTES (string
) * 2);
3212 /* Now copy the data into the new string, inserting escapes. */
3214 in
= SDATA (string
);
3215 end
= in
+ SBYTES (string
);
3218 for (; in
!= end
; in
++)
3221 || *in
== '*' || *in
== '.' || *in
== '\\'
3222 || *in
== '?' || *in
== '+'
3223 || *in
== '^' || *in
== '$')
3224 *out
++ = '\\', backslashes_added
++;
3228 return make_specified_string (temp
,
3229 SCHARS (string
) + backslashes_added
,
3231 STRING_MULTIBYTE (string
));
3239 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3241 searchbufs
[i
].buf
.allocated
= 100;
3242 searchbufs
[i
].buf
.buffer
= (unsigned char *) xmalloc (100);
3243 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3244 searchbufs
[i
].regexp
= Qnil
;
3245 searchbufs
[i
].whitespace_regexp
= Qnil
;
3246 searchbufs
[i
].syntax_table
= Qnil
;
3247 staticpro (&searchbufs
[i
].regexp
);
3248 staticpro (&searchbufs
[i
].whitespace_regexp
);
3249 staticpro (&searchbufs
[i
].syntax_table
);
3250 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3252 searchbuf_head
= &searchbufs
[0];
3254 Qsearch_failed
= intern_c_string ("search-failed");
3255 staticpro (&Qsearch_failed
);
3256 Qinvalid_regexp
= intern_c_string ("invalid-regexp");
3257 staticpro (&Qinvalid_regexp
);
3259 Fput (Qsearch_failed
, Qerror_conditions
,
3260 pure_cons (Qsearch_failed
, pure_cons (Qerror
, Qnil
)));
3261 Fput (Qsearch_failed
, Qerror_message
,
3262 make_pure_c_string ("Search failed"));
3264 Fput (Qinvalid_regexp
, Qerror_conditions
,
3265 pure_cons (Qinvalid_regexp
, pure_cons (Qerror
, Qnil
)));
3266 Fput (Qinvalid_regexp
, Qerror_message
,
3267 make_pure_c_string ("Invalid regexp"));
3269 last_thing_searched
= Qnil
;
3270 saved_last_thing_searched
= Qnil
;
3272 DEFVAR_LISP ("search-spaces-regexp", &Vsearch_spaces_regexp
,
3273 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3274 Some commands use this for user-specified regexps.
3275 Spaces that occur inside character classes or repetition operators
3276 or other such regexp constructs are not replaced with this.
3277 A value of nil (which is the normal value) means treat spaces literally. */);
3278 Vsearch_spaces_regexp
= Qnil
;
3280 DEFVAR_LISP ("inhibit-changing-match-data", &Vinhibit_changing_match_data
,
3281 doc
: /* Internal use only.
3282 If non-nil, the primitive searching and matching functions
3283 such as `looking-at', `string-match', `re-search-forward', etc.,
3284 do not set the match data. The proper way to use this variable
3285 is to bind it with `let' around a small expression. */);
3286 Vinhibit_changing_match_data
= Qnil
;
3288 defsubr (&Slooking_at
);
3289 defsubr (&Sposix_looking_at
);
3290 defsubr (&Sstring_match
);
3291 defsubr (&Sposix_string_match
);
3292 defsubr (&Ssearch_forward
);
3293 defsubr (&Ssearch_backward
);
3294 defsubr (&Sword_search_forward
);
3295 defsubr (&Sword_search_backward
);
3296 defsubr (&Sword_search_forward_lax
);
3297 defsubr (&Sword_search_backward_lax
);
3298 defsubr (&Sre_search_forward
);
3299 defsubr (&Sre_search_backward
);
3300 defsubr (&Sposix_search_forward
);
3301 defsubr (&Sposix_search_backward
);
3302 defsubr (&Sreplace_match
);
3303 defsubr (&Smatch_beginning
);
3304 defsubr (&Smatch_end
);
3305 defsubr (&Smatch_data
);
3306 defsubr (&Sset_match_data
);
3307 defsubr (&Sregexp_quote
);
3310 /* arch-tag: a6059d79-0552-4f14-a2cb-d379a4e3c78f
3311 (do not change this comment) */