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 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 3, 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. */
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 /* Syntax table for which the regexp applies. We need this because
46 of character classes. If this is t, then the compiled pattern is valid
47 for any syntax-table. */
48 Lisp_Object syntax_table
;
49 struct re_pattern_buffer buf
;
51 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
55 /* The instances of that struct. */
56 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
58 /* The head of the linked list; points to the most recently used buffer. */
59 struct regexp_cache
*searchbuf_head
;
62 /* Every call to re_match, etc., must pass &search_regs as the regs
63 argument unless you can show it is unnecessary (i.e., if re_match
64 is certainly going to be called again before region-around-match
67 Since the registers are now dynamically allocated, we need to make
68 sure not to refer to the Nth register before checking that it has
69 been allocated by checking search_regs.num_regs.
71 The regex code keeps track of whether it has allocated the search
72 buffer using bits in the re_pattern_buffer. This means that whenever
73 you compile a new pattern, it completely forgets whether it has
74 allocated any registers, and will allocate new registers the next
75 time you call a searching or matching function. Therefore, we need
76 to call re_set_registers after compiling a new pattern or after
77 setting the match registers, so that the regex functions will be
78 able to free or re-allocate it properly. */
79 static struct re_registers search_regs
;
81 /* The buffer in which the last search was performed, or
82 Qt if the last search was done in a string;
83 Qnil if no searching has been done yet. */
84 static Lisp_Object last_thing_searched
;
86 /* error condition signaled when regexp compile_pattern fails */
88 Lisp_Object Qinvalid_regexp
;
90 /* Error condition used for failing searches */
91 Lisp_Object Qsearch_failed
;
93 Lisp_Object Vsearch_spaces_regexp
;
95 /* If non-nil, the match data will not be changed during call to
96 searching or matching functions. This variable is for internal use
98 Lisp_Object Vinhibit_changing_match_data
;
100 static void set_search_regs ();
101 static void save_search_regs ();
102 static int simple_search ();
103 static int boyer_moore ();
104 static int search_buffer ();
105 static void matcher_overflow () NO_RETURN
;
110 error ("Stack overflow in regexp matcher");
113 /* Compile a regexp and signal a Lisp error if anything goes wrong.
114 PATTERN is the pattern to compile.
115 CP is the place to put the result.
116 TRANSLATE is a translation table for ignoring case, or nil for none.
117 REGP is the structure that says where to store the "register"
118 values that will result from matching this pattern.
119 If it is 0, we should compile the pattern not to record any
120 subexpression bounds.
121 POSIX is nonzero if we want full backtracking (POSIX style)
122 for this pattern. 0 means backtrack only enough to get a valid match.
123 MULTIBYTE is nonzero if we want to handle multibyte characters in
124 PATTERN. 0 means all multibyte characters are recognized just as
125 sequences of binary data.
127 The behavior also depends on Vsearch_spaces_regexp. */
130 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
131 struct regexp_cache
*cp
;
133 Lisp_Object translate
;
134 struct re_registers
*regp
;
138 unsigned char *raw_pattern
;
139 int raw_pattern_size
;
143 /* MULTIBYTE says whether the text to be searched is multibyte.
144 We must convert PATTERN to match that, or we will not really
145 find things right. */
147 if (multibyte
== STRING_MULTIBYTE (pattern
))
149 raw_pattern
= (unsigned char *) SDATA (pattern
);
150 raw_pattern_size
= SBYTES (pattern
);
154 raw_pattern_size
= count_size_as_multibyte (SDATA (pattern
),
156 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
157 copy_text (SDATA (pattern
), raw_pattern
,
158 SCHARS (pattern
), 0, 1);
162 /* Converting multibyte to single-byte.
164 ??? Perhaps this conversion should be done in a special way
165 by subtracting nonascii-insert-offset from each non-ASCII char,
166 so that only the multibyte chars which really correspond to
167 the chosen single-byte character set can possibly match. */
168 raw_pattern_size
= SCHARS (pattern
);
169 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
170 copy_text (SDATA (pattern
), raw_pattern
,
171 SBYTES (pattern
), 1, 0);
175 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
177 cp
->buf
.multibyte
= multibyte
;
178 cp
->whitespace_regexp
= Vsearch_spaces_regexp
;
179 /* rms: I think BLOCK_INPUT is not needed here any more,
180 because regex.c defines malloc to call xmalloc.
181 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
182 So let's turn it off. */
184 old
= re_set_syntax (RE_SYNTAX_EMACS
185 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
187 re_set_whitespace_regexp (NILP (Vsearch_spaces_regexp
) ? NULL
188 : SDATA (Vsearch_spaces_regexp
));
190 val
= (char *) re_compile_pattern ((char *)raw_pattern
,
191 raw_pattern_size
, &cp
->buf
);
193 /* If the compiled pattern hard codes some of the contents of the
194 syntax-table, it can only be reused with *this* syntax table. */
195 cp
->syntax_table
= cp
->buf
.used_syntax
? current_buffer
->syntax_table
: Qt
;
197 re_set_whitespace_regexp (NULL
);
202 xsignal1 (Qinvalid_regexp
, build_string (val
));
204 cp
->regexp
= Fcopy_sequence (pattern
);
207 /* Shrink each compiled regexp buffer in the cache
208 to the size actually used right now.
209 This is called from garbage collection. */
212 shrink_regexp_cache ()
214 struct regexp_cache
*cp
;
216 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
218 cp
->buf
.allocated
= cp
->buf
.used
;
220 = (unsigned char *) xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
224 /* Clear the regexp cache w.r.t. a particular syntax table,
225 because it was changed.
226 There is no danger of memory leak here because re_compile_pattern
227 automagically manages the memory in each re_pattern_buffer struct,
228 based on its `allocated' and `buffer' values. */
230 clear_regexp_cache ()
234 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
235 /* It's tempting to compare with the syntax-table we've actually changd,
236 but it's not sufficient because char-table inheritance mewans that
237 modifying one syntax-table can change others at the same time. */
238 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
239 searchbufs
[i
].regexp
= Qnil
;
242 /* Compile a regexp if necessary, but first check to see if there's one in
244 PATTERN is the pattern to compile.
245 TRANSLATE is a translation table for ignoring case, or nil for none.
246 REGP is the structure that says where to store the "register"
247 values that will result from matching this pattern.
248 If it is 0, we should compile the pattern not to record any
249 subexpression bounds.
250 POSIX is nonzero if we want full backtracking (POSIX style)
251 for this pattern. 0 means backtrack only enough to get a valid match. */
253 struct re_pattern_buffer
*
254 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
256 struct re_registers
*regp
;
257 Lisp_Object translate
;
258 int posix
, multibyte
;
260 struct regexp_cache
*cp
, **cpp
;
262 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
265 /* Entries are initialized to nil, and may be set to nil by
266 compile_pattern_1 if the pattern isn't valid. Don't apply
267 string accessors in those cases. However, compile_pattern_1
268 is only applied to the cache entry we pick here to reuse. So
269 nil should never appear before a non-nil entry. */
270 if (NILP (cp
->regexp
))
272 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
273 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
274 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
275 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
276 && cp
->posix
== posix
277 && cp
->buf
.multibyte
== multibyte
278 && (EQ (cp
->syntax_table
, Qt
)
279 || EQ (cp
->syntax_table
, current_buffer
->syntax_table
))
280 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
)))
283 /* If we're at the end of the cache, compile into the nil cell
284 we found, or the last (least recently used) cell with a
289 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
294 /* When we get here, cp (aka *cpp) contains the compiled pattern,
295 either because we found it in the cache or because we just compiled it.
296 Move it to the front of the queue to mark it as most recently used. */
298 cp
->next
= searchbuf_head
;
301 /* Advise the searching functions about the space we have allocated
302 for register data. */
304 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
311 looking_at_1 (string
, posix
)
316 unsigned char *p1
, *p2
;
319 struct re_pattern_buffer
*bufp
;
321 if (running_asynch_code
)
324 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
325 XCHAR_TABLE (current_buffer
->case_canon_table
)->extras
[2]
326 = current_buffer
->case_eqv_table
;
328 CHECK_STRING (string
);
329 bufp
= compile_pattern (string
,
330 (NILP (Vinhibit_changing_match_data
)
331 ? &search_regs
: NULL
),
332 (!NILP (current_buffer
->case_fold_search
)
333 ? current_buffer
->case_canon_table
: Qnil
),
335 !NILP (current_buffer
->enable_multibyte_characters
));
338 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
340 /* Get pointers and sizes of the two strings
341 that make up the visible portion of the buffer. */
344 s1
= GPT_BYTE
- BEGV_BYTE
;
346 s2
= ZV_BYTE
- GPT_BYTE
;
350 s2
= ZV_BYTE
- BEGV_BYTE
;
355 s1
= ZV_BYTE
- BEGV_BYTE
;
359 re_match_object
= Qnil
;
361 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
363 (NILP (Vinhibit_changing_match_data
)
364 ? &search_regs
: NULL
),
365 ZV_BYTE
- BEGV_BYTE
);
371 val
= (0 <= i
? Qt
: Qnil
);
372 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
373 for (i
= 0; i
< search_regs
.num_regs
; i
++)
374 if (search_regs
.start
[i
] >= 0)
377 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
379 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
382 /* Set last_thing_searched only when match data is changed. */
383 if (NILP (Vinhibit_changing_match_data
))
384 XSETBUFFER (last_thing_searched
, current_buffer
);
389 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
390 doc
: /* Return t if text after point matches regular expression REGEXP.
391 This function modifies the match data that `match-beginning',
392 `match-end' and `match-data' access; save and restore the match
393 data if you want to preserve them. */)
397 return looking_at_1 (regexp
, 0);
400 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
401 doc
: /* Return t if text after point matches regular expression REGEXP.
402 Find the longest match, in accord with Posix regular expression rules.
403 This function modifies the match data that `match-beginning',
404 `match-end' and `match-data' access; save and restore the match
405 data if you want to preserve them. */)
409 return looking_at_1 (regexp
, 1);
413 string_match_1 (regexp
, string
, start
, posix
)
414 Lisp_Object regexp
, string
, start
;
418 struct re_pattern_buffer
*bufp
;
422 if (running_asynch_code
)
425 CHECK_STRING (regexp
);
426 CHECK_STRING (string
);
429 pos
= 0, pos_byte
= 0;
432 int len
= SCHARS (string
);
434 CHECK_NUMBER (start
);
436 if (pos
< 0 && -pos
<= len
)
438 else if (0 > pos
|| pos
> len
)
439 args_out_of_range (string
, start
);
440 pos_byte
= string_char_to_byte (string
, pos
);
443 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
444 XCHAR_TABLE (current_buffer
->case_canon_table
)->extras
[2]
445 = current_buffer
->case_eqv_table
;
447 bufp
= compile_pattern (regexp
,
448 (NILP (Vinhibit_changing_match_data
)
449 ? &search_regs
: NULL
),
450 (!NILP (current_buffer
->case_fold_search
)
451 ? current_buffer
->case_canon_table
: Qnil
),
453 STRING_MULTIBYTE (string
));
455 re_match_object
= string
;
457 val
= re_search (bufp
, (char *) SDATA (string
),
458 SBYTES (string
), pos_byte
,
459 SBYTES (string
) - pos_byte
,
460 (NILP (Vinhibit_changing_match_data
)
461 ? &search_regs
: NULL
));
464 /* Set last_thing_searched only when match data is changed. */
465 if (NILP (Vinhibit_changing_match_data
))
466 last_thing_searched
= Qt
;
470 if (val
< 0) return Qnil
;
472 if (NILP (Vinhibit_changing_match_data
))
473 for (i
= 0; i
< search_regs
.num_regs
; i
++)
474 if (search_regs
.start
[i
] >= 0)
477 = string_byte_to_char (string
, search_regs
.start
[i
]);
479 = string_byte_to_char (string
, search_regs
.end
[i
]);
482 return make_number (string_byte_to_char (string
, val
));
485 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
486 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
487 Matching ignores case if `case-fold-search' is non-nil.
488 If third arg START is non-nil, start search at that index in STRING.
489 For index of first char beyond the match, do (match-end 0).
490 `match-end' and `match-beginning' also give indices of substrings
491 matched by parenthesis constructs in the pattern.
493 You can use the function `match-string' to extract the substrings
494 matched by the parenthesis constructions in REGEXP. */)
495 (regexp
, string
, start
)
496 Lisp_Object regexp
, string
, start
;
498 return string_match_1 (regexp
, string
, start
, 0);
501 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
502 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
503 Find the longest match, in accord with Posix regular expression rules.
504 Case is ignored if `case-fold-search' is non-nil in the current buffer.
505 If third arg START is non-nil, start search at that index in STRING.
506 For index of first char beyond the match, do (match-end 0).
507 `match-end' and `match-beginning' also give indices of substrings
508 matched by parenthesis constructs in the pattern. */)
509 (regexp
, string
, start
)
510 Lisp_Object regexp
, string
, start
;
512 return string_match_1 (regexp
, string
, start
, 1);
515 /* Match REGEXP against STRING, searching all of STRING,
516 and return the index of the match, or negative on failure.
517 This does not clobber the match data. */
520 fast_string_match (regexp
, string
)
521 Lisp_Object regexp
, string
;
524 struct re_pattern_buffer
*bufp
;
526 bufp
= compile_pattern (regexp
, 0, Qnil
,
527 0, STRING_MULTIBYTE (string
));
529 re_match_object
= string
;
531 val
= re_search (bufp
, (char *) SDATA (string
),
538 /* Match REGEXP against STRING, searching all of STRING ignoring case,
539 and return the index of the match, or negative on failure.
540 This does not clobber the match data.
541 We assume that STRING contains single-byte characters. */
543 extern Lisp_Object Vascii_downcase_table
;
546 fast_c_string_match_ignore_case (regexp
, string
)
551 struct re_pattern_buffer
*bufp
;
552 int len
= strlen (string
);
554 regexp
= string_make_unibyte (regexp
);
555 re_match_object
= Qt
;
556 bufp
= compile_pattern (regexp
, 0,
557 Vascii_canon_table
, 0,
560 val
= re_search (bufp
, string
, len
, 0, len
, 0);
565 /* Like fast_string_match but ignore case. */
568 fast_string_match_ignore_case (regexp
, string
)
569 Lisp_Object regexp
, string
;
572 struct re_pattern_buffer
*bufp
;
574 bufp
= compile_pattern (regexp
, 0, Vascii_canon_table
,
575 0, STRING_MULTIBYTE (string
));
577 re_match_object
= string
;
579 val
= re_search (bufp
, (char *) SDATA (string
),
586 /* The newline cache: remembering which sections of text have no newlines. */
588 /* If the user has requested newline caching, make sure it's on.
589 Otherwise, make sure it's off.
590 This is our cheezy way of associating an action with the change of
591 state of a buffer-local variable. */
593 newline_cache_on_off (buf
)
596 if (NILP (buf
->cache_long_line_scans
))
598 /* It should be off. */
599 if (buf
->newline_cache
)
601 free_region_cache (buf
->newline_cache
);
602 buf
->newline_cache
= 0;
607 /* It should be on. */
608 if (buf
->newline_cache
== 0)
609 buf
->newline_cache
= new_region_cache ();
614 /* Search for COUNT instances of the character TARGET between START and END.
616 If COUNT is positive, search forwards; END must be >= START.
617 If COUNT is negative, search backwards for the -COUNTth instance;
618 END must be <= START.
619 If COUNT is zero, do anything you please; run rogue, for all I care.
621 If END is zero, use BEGV or ZV instead, as appropriate for the
622 direction indicated by COUNT.
624 If we find COUNT instances, set *SHORTAGE to zero, and return the
625 position past the COUNTth match. Note that for reverse motion
626 this is not the same as the usual convention for Emacs motion commands.
628 If we don't find COUNT instances before reaching END, set *SHORTAGE
629 to the number of TARGETs left unfound, and return END.
631 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
632 except when inside redisplay. */
635 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
642 struct region_cache
*newline_cache
;
653 if (! end
) end
= BEGV
;
656 newline_cache_on_off (current_buffer
);
657 newline_cache
= current_buffer
->newline_cache
;
662 immediate_quit
= allow_quit
;
667 /* Our innermost scanning loop is very simple; it doesn't know
668 about gaps, buffer ends, or the newline cache. ceiling is
669 the position of the last character before the next such
670 obstacle --- the last character the dumb search loop should
672 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
673 int start_byte
= CHAR_TO_BYTE (start
);
676 /* If we're looking for a newline, consult the newline cache
677 to see where we can avoid some scanning. */
678 if (target
== '\n' && newline_cache
)
682 while (region_cache_forward
683 (current_buffer
, newline_cache
, start_byte
, &next_change
))
684 start_byte
= next_change
;
685 immediate_quit
= allow_quit
;
687 /* START should never be after END. */
688 if (start_byte
> ceiling_byte
)
689 start_byte
= ceiling_byte
;
691 /* Now the text after start is an unknown region, and
692 next_change is the position of the next known region. */
693 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
696 /* The dumb loop can only scan text stored in contiguous
697 bytes. BUFFER_CEILING_OF returns the last character
698 position that is contiguous, so the ceiling is the
699 position after that. */
700 tem
= BUFFER_CEILING_OF (start_byte
);
701 ceiling_byte
= min (tem
, ceiling_byte
);
704 /* The termination address of the dumb loop. */
705 register unsigned char *ceiling_addr
706 = BYTE_POS_ADDR (ceiling_byte
) + 1;
707 register unsigned char *cursor
708 = BYTE_POS_ADDR (start_byte
);
709 unsigned char *base
= cursor
;
711 while (cursor
< ceiling_addr
)
713 unsigned char *scan_start
= cursor
;
716 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
719 /* If we're looking for newlines, cache the fact that
720 the region from start to cursor is free of them. */
721 if (target
== '\n' && newline_cache
)
722 know_region_cache (current_buffer
, newline_cache
,
723 start_byte
+ scan_start
- base
,
724 start_byte
+ cursor
- base
);
726 /* Did we find the target character? */
727 if (cursor
< ceiling_addr
)
732 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
738 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
744 /* The last character to check before the next obstacle. */
745 int ceiling_byte
= CHAR_TO_BYTE (end
);
746 int start_byte
= CHAR_TO_BYTE (start
);
749 /* Consult the newline cache, if appropriate. */
750 if (target
== '\n' && newline_cache
)
754 while (region_cache_backward
755 (current_buffer
, newline_cache
, start_byte
, &next_change
))
756 start_byte
= next_change
;
757 immediate_quit
= allow_quit
;
759 /* Start should never be at or before end. */
760 if (start_byte
<= ceiling_byte
)
761 start_byte
= ceiling_byte
+ 1;
763 /* Now the text before start is an unknown region, and
764 next_change is the position of the next known region. */
765 ceiling_byte
= max (next_change
, ceiling_byte
);
768 /* Stop scanning before the gap. */
769 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
770 ceiling_byte
= max (tem
, ceiling_byte
);
773 /* The termination address of the dumb loop. */
774 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
775 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
776 unsigned char *base
= cursor
;
778 while (cursor
>= ceiling_addr
)
780 unsigned char *scan_start
= cursor
;
782 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
785 /* If we're looking for newlines, cache the fact that
786 the region from after the cursor to start is free of them. */
787 if (target
== '\n' && newline_cache
)
788 know_region_cache (current_buffer
, newline_cache
,
789 start_byte
+ cursor
- base
,
790 start_byte
+ scan_start
- base
);
792 /* Did we find the target character? */
793 if (cursor
>= ceiling_addr
)
798 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
804 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
810 *shortage
= count
* direction
;
814 /* Search for COUNT instances of a line boundary, which means either a
815 newline or (if selective display enabled) a carriage return.
816 Start at START. If COUNT is negative, search backwards.
818 We report the resulting position by calling TEMP_SET_PT_BOTH.
820 If we find COUNT instances. we position after (always after,
821 even if scanning backwards) the COUNTth match, and return 0.
823 If we don't find COUNT instances before reaching the end of the
824 buffer (or the beginning, if scanning backwards), we return
825 the number of line boundaries left unfound, and position at
826 the limit we bumped up against.
828 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
829 except in special cases. */
832 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
833 int start
, start_byte
;
834 int limit
, limit_byte
;
838 int direction
= ((count
> 0) ? 1 : -1);
840 register unsigned char *cursor
;
843 register int ceiling
;
844 register unsigned char *ceiling_addr
;
846 int old_immediate_quit
= immediate_quit
;
848 /* The code that follows is like scan_buffer
849 but checks for either newline or carriage return. */
854 start_byte
= CHAR_TO_BYTE (start
);
858 while (start_byte
< limit_byte
)
860 ceiling
= BUFFER_CEILING_OF (start_byte
);
861 ceiling
= min (limit_byte
- 1, ceiling
);
862 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
863 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
866 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
869 if (cursor
!= ceiling_addr
)
873 immediate_quit
= old_immediate_quit
;
874 start_byte
= start_byte
+ cursor
- base
+ 1;
875 start
= BYTE_TO_CHAR (start_byte
);
876 TEMP_SET_PT_BOTH (start
, start_byte
);
880 if (++cursor
== ceiling_addr
)
886 start_byte
+= cursor
- base
;
891 while (start_byte
> limit_byte
)
893 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
894 ceiling
= max (limit_byte
, ceiling
);
895 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
896 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
899 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
902 if (cursor
!= ceiling_addr
)
906 immediate_quit
= old_immediate_quit
;
907 /* Return the position AFTER the match we found. */
908 start_byte
= start_byte
+ cursor
- base
+ 1;
909 start
= BYTE_TO_CHAR (start_byte
);
910 TEMP_SET_PT_BOTH (start
, start_byte
);
917 /* Here we add 1 to compensate for the last decrement
918 of CURSOR, which took it past the valid range. */
919 start_byte
+= cursor
- base
+ 1;
923 TEMP_SET_PT_BOTH (limit
, limit_byte
);
924 immediate_quit
= old_immediate_quit
;
926 return count
* direction
;
930 find_next_newline_no_quit (from
, cnt
)
931 register int from
, cnt
;
933 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
936 /* Like find_next_newline, but returns position before the newline,
937 not after, and only search up to TO. This isn't just
938 find_next_newline (...)-1, because you might hit TO. */
941 find_before_next_newline (from
, to
, cnt
)
945 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
953 /* Subroutines of Lisp buffer search functions. */
956 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
957 Lisp_Object string
, bound
, noerror
, count
;
968 CHECK_NUMBER (count
);
972 CHECK_STRING (string
);
976 lim
= ZV
, lim_byte
= ZV_BYTE
;
978 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
982 CHECK_NUMBER_COERCE_MARKER (bound
);
984 if (n
> 0 ? lim
< PT
: lim
> PT
)
985 error ("Invalid search bound (wrong side of point)");
987 lim
= ZV
, lim_byte
= ZV_BYTE
;
989 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
991 lim_byte
= CHAR_TO_BYTE (lim
);
994 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
995 XCHAR_TABLE (current_buffer
->case_canon_table
)->extras
[2]
996 = current_buffer
->case_eqv_table
;
998 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
999 (!NILP (current_buffer
->case_fold_search
)
1000 ? current_buffer
->case_canon_table
1002 (!NILP (current_buffer
->case_fold_search
)
1003 ? current_buffer
->case_eqv_table
1009 xsignal1 (Qsearch_failed
, string
);
1011 if (!EQ (noerror
, Qt
))
1013 if (lim
< BEGV
|| lim
> ZV
)
1015 SET_PT_BOTH (lim
, lim_byte
);
1017 #if 0 /* This would be clean, but maybe programs depend on
1018 a value of nil here. */
1026 if (np
< BEGV
|| np
> ZV
)
1031 return make_number (np
);
1034 /* Return 1 if REGEXP it matches just one constant string. */
1037 trivial_regexp_p (regexp
)
1040 int len
= SBYTES (regexp
);
1041 unsigned char *s
= SDATA (regexp
);
1046 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1053 case '|': case '(': case ')': case '`': case '\'': case 'b':
1054 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1055 case 'S': case '=': case '{': case '}': case '_':
1056 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1057 case '1': case '2': case '3': case '4': case '5':
1058 case '6': case '7': case '8': case '9':
1066 /* Search for the n'th occurrence of STRING in the current buffer,
1067 starting at position POS and stopping at position LIM,
1068 treating STRING as a literal string if RE is false or as
1069 a regular expression if RE is true.
1071 If N is positive, searching is forward and LIM must be greater than POS.
1072 If N is negative, searching is backward and LIM must be less than POS.
1074 Returns -x if x occurrences remain to be found (x > 0),
1075 or else the position at the beginning of the Nth occurrence
1076 (if searching backward) or the end (if searching forward).
1078 POSIX is nonzero if we want full backtracking (POSIX style)
1079 for this pattern. 0 means backtrack only enough to get a valid match. */
1081 #define TRANSLATE(out, trt, d) \
1087 temp = Faref (trt, make_number (d)); \
1088 if (INTEGERP (temp)) \
1089 out = XINT (temp); \
1098 /* Only used in search_buffer, to record the end position of the match
1099 when searching regexps and SEARCH_REGS should not be changed
1100 (i.e. Vinhibit_changing_match_data is non-nil). */
1101 static struct re_registers search_regs_1
;
1104 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
1105 RE
, trt
, inverse_trt
, posix
)
1114 Lisp_Object inverse_trt
;
1117 int len
= SCHARS (string
);
1118 int len_byte
= SBYTES (string
);
1121 if (running_asynch_code
)
1122 save_search_regs ();
1124 /* Searching 0 times means don't move. */
1125 /* Null string is found at starting position. */
1126 if (len
== 0 || n
== 0)
1128 set_search_regs (pos_byte
, 0);
1132 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1134 unsigned char *p1
, *p2
;
1136 struct re_pattern_buffer
*bufp
;
1138 bufp
= compile_pattern (string
,
1139 (NILP (Vinhibit_changing_match_data
)
1140 ? &search_regs
: &search_regs_1
),
1142 !NILP (current_buffer
->enable_multibyte_characters
));
1144 immediate_quit
= 1; /* Quit immediately if user types ^G,
1145 because letting this function finish
1146 can take too long. */
1147 QUIT
; /* Do a pending quit right away,
1148 to avoid paradoxical behavior */
1149 /* Get pointers and sizes of the two strings
1150 that make up the visible portion of the buffer. */
1153 s1
= GPT_BYTE
- BEGV_BYTE
;
1155 s2
= ZV_BYTE
- GPT_BYTE
;
1159 s2
= ZV_BYTE
- BEGV_BYTE
;
1164 s1
= ZV_BYTE
- BEGV_BYTE
;
1167 re_match_object
= Qnil
;
1172 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1173 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1174 (NILP (Vinhibit_changing_match_data
)
1175 ? &search_regs
: &search_regs_1
),
1176 /* Don't allow match past current point */
1177 pos_byte
- BEGV_BYTE
);
1180 matcher_overflow ();
1184 if (NILP (Vinhibit_changing_match_data
))
1186 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1187 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1188 if (search_regs
.start
[i
] >= 0)
1190 search_regs
.start
[i
]
1191 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1193 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1195 XSETBUFFER (last_thing_searched
, current_buffer
);
1196 /* Set pos to the new position. */
1197 pos
= search_regs
.start
[0];
1201 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1202 /* Set pos to the new position. */
1203 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1216 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1217 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1218 (NILP (Vinhibit_changing_match_data
)
1219 ? &search_regs
: &search_regs_1
),
1220 lim_byte
- BEGV_BYTE
);
1223 matcher_overflow ();
1227 if (NILP (Vinhibit_changing_match_data
))
1229 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1230 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1231 if (search_regs
.start
[i
] >= 0)
1233 search_regs
.start
[i
]
1234 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1236 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1238 XSETBUFFER (last_thing_searched
, current_buffer
);
1239 pos
= search_regs
.end
[0];
1243 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1244 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1257 else /* non-RE case */
1259 unsigned char *raw_pattern
, *pat
;
1260 int raw_pattern_size
;
1261 int raw_pattern_size_byte
;
1262 unsigned char *patbuf
;
1263 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1264 unsigned char *base_pat
;
1265 /* Set to positive if we find a non-ASCII char that need
1266 translation. Otherwise set to zero later. */
1267 int charset_base
= -1;
1268 int boyer_moore_ok
= 1;
1270 /* MULTIBYTE says whether the text to be searched is multibyte.
1271 We must convert PATTERN to match that, or we will not really
1272 find things right. */
1274 if (multibyte
== STRING_MULTIBYTE (string
))
1276 raw_pattern
= (unsigned char *) SDATA (string
);
1277 raw_pattern_size
= SCHARS (string
);
1278 raw_pattern_size_byte
= SBYTES (string
);
1282 raw_pattern_size
= SCHARS (string
);
1283 raw_pattern_size_byte
1284 = count_size_as_multibyte (SDATA (string
),
1286 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1287 copy_text (SDATA (string
), raw_pattern
,
1288 SCHARS (string
), 0, 1);
1292 /* Converting multibyte to single-byte.
1294 ??? Perhaps this conversion should be done in a special way
1295 by subtracting nonascii-insert-offset from each non-ASCII char,
1296 so that only the multibyte chars which really correspond to
1297 the chosen single-byte character set can possibly match. */
1298 raw_pattern_size
= SCHARS (string
);
1299 raw_pattern_size_byte
= SCHARS (string
);
1300 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1301 copy_text (SDATA (string
), raw_pattern
,
1302 SBYTES (string
), 1, 0);
1305 /* Copy and optionally translate the pattern. */
1306 len
= raw_pattern_size
;
1307 len_byte
= raw_pattern_size_byte
;
1308 patbuf
= (unsigned char *) alloca (len_byte
);
1310 base_pat
= raw_pattern
;
1313 /* Fill patbuf by translated characters in STRING while
1314 checking if we can use boyer-moore search. If TRT is
1315 non-nil, we can use boyer-moore search only if TRT can be
1316 represented by the byte array of 256 elements. For that,
1317 all non-ASCII case-equivalents of all case-senstive
1318 characters in STRING must belong to the same charset and
1323 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1324 int c
, translated
, inverse
;
1325 int in_charlen
, charlen
;
1327 /* If we got here and the RE flag is set, it's because we're
1328 dealing with a regexp known to be trivial, so the backslash
1329 just quotes the next character. */
1330 if (RE
&& *base_pat
== '\\')
1338 c
= STRING_CHAR_AND_LENGTH (base_pat
, len_byte
, in_charlen
);
1343 charlen
= in_charlen
;
1347 /* Translate the character. */
1348 TRANSLATE (translated
, trt
, c
);
1349 charlen
= CHAR_STRING (translated
, str_base
);
1352 /* Check if C has any other case-equivalents. */
1353 TRANSLATE (inverse
, inverse_trt
, c
);
1354 /* If so, check if we can use boyer-moore. */
1355 if (c
!= inverse
&& boyer_moore_ok
)
1357 /* Check if all equivalents belong to the same
1358 charset & row. Note that the check of C
1359 itself is done by the last iteration. Note
1360 also that we don't have to check ASCII
1361 characters because boyer-moore search can
1362 always handle their translation. */
1365 if (ASCII_BYTE_P (inverse
))
1367 if (charset_base
> 0)
1374 else if (SINGLE_BYTE_CHAR_P (inverse
))
1376 /* Boyer-moore search can't handle a
1377 translation of an eight-bit
1382 else if (charset_base
< 0)
1383 charset_base
= inverse
& ~CHAR_FIELD3_MASK
;
1384 else if ((inverse
& ~CHAR_FIELD3_MASK
)
1392 TRANSLATE (inverse
, inverse_trt
, inverse
);
1396 if (charset_base
< 0)
1399 /* Store this character into the translated pattern. */
1400 bcopy (str
, pat
, charlen
);
1402 base_pat
+= in_charlen
;
1403 len_byte
-= in_charlen
;
1408 /* Unibyte buffer. */
1414 /* If we got here and the RE flag is set, it's because we're
1415 dealing with a regexp known to be trivial, so the backslash
1416 just quotes the next character. */
1417 if (RE
&& *base_pat
== '\\')
1424 TRANSLATE (translated
, trt
, c
);
1425 *pat
++ = translated
;
1429 len_byte
= pat
- patbuf
;
1430 len
= raw_pattern_size
;
1431 pat
= base_pat
= patbuf
;
1434 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1435 pos
, pos_byte
, lim
, lim_byte
,
1438 return simple_search (n
, pat
, len
, len_byte
, trt
,
1439 pos
, pos_byte
, lim
, lim_byte
);
1443 /* Do a simple string search N times for the string PAT,
1444 whose length is LEN/LEN_BYTE,
1445 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1446 TRT is the translation table.
1448 Return the character position where the match is found.
1449 Otherwise, if M matches remained to be found, return -M.
1451 This kind of search works regardless of what is in PAT and
1452 regardless of what is in TRT. It is used in cases where
1453 boyer_moore cannot work. */
1456 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1464 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1465 int forward
= n
> 0;
1467 if (lim
> pos
&& multibyte
)
1472 /* Try matching at position POS. */
1474 int this_pos_byte
= pos_byte
;
1476 int this_len_byte
= len_byte
;
1477 unsigned char *p
= pat
;
1478 if (pos
+ len
> lim
)
1481 while (this_len
> 0)
1483 int charlen
, buf_charlen
;
1486 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1487 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1488 ZV_BYTE
- this_pos_byte
,
1490 TRANSLATE (buf_ch
, trt
, buf_ch
);
1492 if (buf_ch
!= pat_ch
)
1495 this_len_byte
-= charlen
;
1499 this_pos_byte
+= buf_charlen
;
1506 pos_byte
+= len_byte
;
1510 INC_BOTH (pos
, pos_byte
);
1520 /* Try matching at position POS. */
1523 unsigned char *p
= pat
;
1525 if (pos
+ len
> lim
)
1528 while (this_len
> 0)
1531 int buf_ch
= FETCH_BYTE (this_pos
);
1532 TRANSLATE (buf_ch
, trt
, buf_ch
);
1534 if (buf_ch
!= pat_ch
)
1552 /* Backwards search. */
1553 else if (lim
< pos
&& multibyte
)
1558 /* Try matching at position POS. */
1559 int this_pos
= pos
- len
;
1560 int this_pos_byte
= pos_byte
- len_byte
;
1562 int this_len_byte
= len_byte
;
1563 unsigned char *p
= pat
;
1565 if (this_pos
< lim
|| this_pos_byte
< lim_byte
)
1568 while (this_len
> 0)
1570 int charlen
, buf_charlen
;
1573 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1574 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1575 ZV_BYTE
- this_pos_byte
,
1577 TRANSLATE (buf_ch
, trt
, buf_ch
);
1579 if (buf_ch
!= pat_ch
)
1582 this_len_byte
-= charlen
;
1585 this_pos_byte
+= buf_charlen
;
1592 pos_byte
-= len_byte
;
1596 DEC_BOTH (pos
, pos_byte
);
1606 /* Try matching at position POS. */
1607 int this_pos
= pos
- len
;
1609 unsigned char *p
= pat
;
1611 if (pos
- len
< lim
)
1614 while (this_len
> 0)
1617 int buf_ch
= FETCH_BYTE (this_pos
);
1618 TRANSLATE (buf_ch
, trt
, buf_ch
);
1620 if (buf_ch
!= pat_ch
)
1642 set_search_regs ((multibyte
? pos_byte
: pos
) - len_byte
, len_byte
);
1644 set_search_regs (multibyte
? pos_byte
: pos
, len_byte
);
1654 /* Do Boyer-Moore search N times for the string BASE_PAT,
1655 whose length is LEN/LEN_BYTE,
1656 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1657 DIRECTION says which direction we search in.
1658 TRT and INVERSE_TRT are translation tables.
1659 Characters in PAT are already translated by TRT.
1661 This kind of search works if all the characters in BASE_PAT that
1662 have nontrivial translation are the same aside from the last byte.
1663 This makes it possible to translate just the last byte of a
1664 character, and do so after just a simple test of the context.
1665 CHARSET_BASE is nonzero if there is such a non-ASCII character.
1667 If that criterion is not satisfied, do not call this function. */
1670 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1671 pos
, pos_byte
, lim
, lim_byte
, charset_base
)
1673 unsigned char *base_pat
;
1676 Lisp_Object inverse_trt
;
1681 int direction
= ((n
> 0) ? 1 : -1);
1682 register int dirlen
;
1683 int infinity
, limit
, stride_for_teases
= 0;
1684 register int *BM_tab
;
1686 register unsigned char *cursor
, *p_limit
;
1688 unsigned char *pat
, *pat_end
;
1689 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1691 unsigned char simple_translate
[0400];
1692 /* These are set to the preceding bytes of a byte to be translated
1693 if charset_base is nonzero. As the maximum byte length of a
1694 multibyte character is 4, we have to check at most three previous
1696 int translate_prev_byte1
= 0;
1697 int translate_prev_byte2
= 0;
1698 int translate_prev_byte3
= 0;
1701 int BM_tab_space
[0400];
1702 BM_tab
= &BM_tab_space
[0];
1704 BM_tab
= (int *) alloca (0400 * sizeof (int));
1706 /* The general approach is that we are going to maintain that we know */
1707 /* the first (closest to the present position, in whatever direction */
1708 /* we're searching) character that could possibly be the last */
1709 /* (furthest from present position) character of a valid match. We */
1710 /* advance the state of our knowledge by looking at that character */
1711 /* and seeing whether it indeed matches the last character of the */
1712 /* pattern. If it does, we take a closer look. If it does not, we */
1713 /* move our pointer (to putative last characters) as far as is */
1714 /* logically possible. This amount of movement, which I call a */
1715 /* stride, will be the length of the pattern if the actual character */
1716 /* appears nowhere in the pattern, otherwise it will be the distance */
1717 /* from the last occurrence of that character to the end of the */
1719 /* As a coding trick, an enormous stride is coded into the table for */
1720 /* characters that match the last character. This allows use of only */
1721 /* a single test, a test for having gone past the end of the */
1722 /* permissible match region, to test for both possible matches (when */
1723 /* the stride goes past the end immediately) and failure to */
1724 /* match (where you get nudged past the end one stride at a time). */
1726 /* Here we make a "mickey mouse" BM table. The stride of the search */
1727 /* is determined only by the last character of the putative match. */
1728 /* If that character does not match, we will stride the proper */
1729 /* distance to propose a match that superimposes it on the last */
1730 /* instance of a character that matches it (per trt), or misses */
1731 /* it entirely if there is none. */
1733 dirlen
= len_byte
* direction
;
1734 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1736 /* Record position after the end of the pattern. */
1737 pat_end
= base_pat
+ len_byte
;
1738 /* BASE_PAT points to a character that we start scanning from.
1739 It is the first character in a forward search,
1740 the last character in a backward search. */
1742 base_pat
= pat_end
- 1;
1744 BM_tab_base
= BM_tab
;
1746 j
= dirlen
; /* to get it in a register */
1747 /* A character that does not appear in the pattern induces a */
1748 /* stride equal to the pattern length. */
1749 while (BM_tab_base
!= BM_tab
)
1757 /* We use this for translation, instead of TRT itself.
1758 We fill this in to handle the characters that actually
1759 occur in the pattern. Others don't matter anyway! */
1760 bzero (simple_translate
, sizeof simple_translate
);
1761 for (i
= 0; i
< 0400; i
++)
1762 simple_translate
[i
] = i
;
1766 /* Setup translate_prev_byte1/2/3 from CHARSET_BASE. Only a
1767 byte following them are the target of translation. */
1768 int sample_char
= charset_base
| 0x20;
1769 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1770 int len
= CHAR_STRING (sample_char
, str
);
1772 translate_prev_byte1
= str
[len
- 2];
1775 translate_prev_byte2
= str
[len
- 3];
1777 translate_prev_byte3
= str
[len
- 4];
1782 while (i
!= infinity
)
1784 unsigned char *ptr
= base_pat
+ i
;
1790 /* If the byte currently looking at is the last of a
1791 character to check case-equivalents, set CH to that
1792 character. An ASCII character and a non-ASCII character
1793 matching with CHARSET_BASE are to be checked. */
1796 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1798 else if (charset_base
1799 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1801 unsigned char *charstart
= ptr
- 1;
1803 while (! (CHAR_HEAD_P (*charstart
)))
1805 ch
= STRING_CHAR (charstart
, ptr
- charstart
+ 1);
1806 if (charset_base
!= (ch
& ~CHAR_FIELD3_MASK
))
1811 j
= ((unsigned char) ch
) | 0200;
1816 stride_for_teases
= BM_tab
[j
];
1818 BM_tab
[j
] = dirlen
- i
;
1819 /* A translation table is accompanied by its inverse -- see */
1820 /* comment following downcase_table for details */
1823 int starting_ch
= ch
;
1828 TRANSLATE (ch
, inverse_trt
, ch
);
1830 j
= ((unsigned char) ch
) | 0200;
1832 j
= (unsigned char) ch
;
1834 /* For all the characters that map into CH,
1835 set up simple_translate to map the last byte
1837 simple_translate
[j
] = starting_j
;
1838 if (ch
== starting_ch
)
1840 BM_tab
[j
] = dirlen
- i
;
1849 stride_for_teases
= BM_tab
[j
];
1850 BM_tab
[j
] = dirlen
- i
;
1852 /* stride_for_teases tells how much to stride if we get a */
1853 /* match on the far character but are subsequently */
1854 /* disappointed, by recording what the stride would have been */
1855 /* for that character if the last character had been */
1858 infinity
= dirlen
- infinity
;
1859 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1860 /* loop invariant - POS_BYTE points at where last char (first
1861 char if reverse) of pattern would align in a possible match. */
1865 unsigned char *tail_end_ptr
;
1867 /* It's been reported that some (broken) compiler thinks that
1868 Boolean expressions in an arithmetic context are unsigned.
1869 Using an explicit ?1:0 prevents this. */
1870 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1872 return (n
* (0 - direction
));
1873 /* First we do the part we can by pointers (maybe nothing) */
1876 limit
= pos_byte
- dirlen
+ direction
;
1879 limit
= BUFFER_CEILING_OF (limit
);
1880 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1881 can take on without hitting edge of buffer or the gap. */
1882 limit
= min (limit
, pos_byte
+ 20000);
1883 limit
= min (limit
, lim_byte
- 1);
1887 limit
= BUFFER_FLOOR_OF (limit
);
1888 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1889 can take on without hitting edge of buffer or the gap. */
1890 limit
= max (limit
, pos_byte
- 20000);
1891 limit
= max (limit
, lim_byte
);
1893 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1894 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1896 if ((limit
- pos_byte
) * direction
> 20)
1900 p_limit
= BYTE_POS_ADDR (limit
);
1901 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1902 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1903 while (1) /* use one cursor setting as long as i can */
1905 if (direction
> 0) /* worth duplicating */
1907 /* Use signed comparison if appropriate
1908 to make cursor+infinity sure to be > p_limit.
1909 Assuming that the buffer lies in a range of addresses
1910 that are all "positive" (as ints) or all "negative",
1911 either kind of comparison will work as long
1912 as we don't step by infinity. So pick the kind
1913 that works when we do step by infinity. */
1914 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1915 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1916 cursor
+= BM_tab
[*cursor
];
1918 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1919 cursor
+= BM_tab
[*cursor
];
1923 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1924 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1925 cursor
+= BM_tab
[*cursor
];
1927 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1928 cursor
+= BM_tab
[*cursor
];
1930 /* If you are here, cursor is beyond the end of the searched region. */
1931 /* This can happen if you match on the far character of the pattern, */
1932 /* because the "stride" of that character is infinity, a number able */
1933 /* to throw you well beyond the end of the search. It can also */
1934 /* happen if you fail to match within the permitted region and would */
1935 /* otherwise try a character beyond that region */
1936 if ((cursor
- p_limit
) * direction
<= len_byte
)
1937 break; /* a small overrun is genuine */
1938 cursor
-= infinity
; /* large overrun = hit */
1939 i
= dirlen
- direction
;
1942 while ((i
-= direction
) + direction
!= 0)
1945 cursor
-= direction
;
1946 /* Translate only the last byte of a character. */
1948 || ((cursor
== tail_end_ptr
1949 || CHAR_HEAD_P (cursor
[1]))
1950 && (CHAR_HEAD_P (cursor
[0])
1951 /* Check if this is the last byte of
1952 a translable character. */
1953 || (translate_prev_byte1
== cursor
[-1]
1954 && (CHAR_HEAD_P (translate_prev_byte1
)
1955 || (translate_prev_byte2
== cursor
[-2]
1956 && (CHAR_HEAD_P (translate_prev_byte2
)
1957 || (translate_prev_byte3
== cursor
[-3]))))))))
1958 ch
= simple_translate
[*cursor
];
1967 while ((i
-= direction
) + direction
!= 0)
1969 cursor
-= direction
;
1970 if (pat
[i
] != *cursor
)
1974 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1975 if (i
+ direction
== 0)
1977 int position
, start
, end
;
1979 cursor
-= direction
;
1981 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1982 ? 1 - len_byte
: 0);
1983 set_search_regs (position
, len_byte
);
1985 if (NILP (Vinhibit_changing_match_data
))
1987 start
= search_regs
.start
[0];
1988 end
= search_regs
.end
[0];
1991 /* If Vinhibit_changing_match_data is non-nil,
1992 search_regs will not be changed. So let's
1993 compute start and end here. */
1995 start
= BYTE_TO_CHAR (position
);
1996 end
= BYTE_TO_CHAR (position
+ len_byte
);
1999 if ((n
-= direction
) != 0)
2000 cursor
+= dirlen
; /* to resume search */
2002 return direction
> 0 ? end
: start
;
2005 cursor
+= stride_for_teases
; /* <sigh> we lose - */
2007 pos_byte
+= cursor
- p2
;
2010 /* Now we'll pick up a clump that has to be done the hard */
2011 /* way because it covers a discontinuity */
2013 limit
= ((direction
> 0)
2014 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
2015 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
2016 limit
= ((direction
> 0)
2017 ? min (limit
+ len_byte
, lim_byte
- 1)
2018 : max (limit
- len_byte
, lim_byte
));
2019 /* LIMIT is now the last value POS_BYTE can have
2020 and still be valid for a possible match. */
2023 /* This loop can be coded for space rather than */
2024 /* speed because it will usually run only once. */
2025 /* (the reach is at most len + 21, and typically */
2026 /* does not exceed len) */
2027 while ((limit
- pos_byte
) * direction
>= 0)
2028 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
2029 /* now run the same tests to distinguish going off the */
2030 /* end, a match or a phony match. */
2031 if ((pos_byte
- limit
) * direction
<= len_byte
)
2032 break; /* ran off the end */
2033 /* Found what might be a match.
2034 Set POS_BYTE back to last (first if reverse) pos. */
2035 pos_byte
-= infinity
;
2036 i
= dirlen
- direction
;
2037 while ((i
-= direction
) + direction
!= 0)
2041 pos_byte
-= direction
;
2042 ptr
= BYTE_POS_ADDR (pos_byte
);
2043 /* Translate only the last byte of a character. */
2045 || ((ptr
== tail_end_ptr
2046 || CHAR_HEAD_P (ptr
[1]))
2047 && (CHAR_HEAD_P (ptr
[0])
2048 /* Check if this is the last byte of a
2049 translable character. */
2050 || (translate_prev_byte1
== ptr
[-1]
2051 && (CHAR_HEAD_P (translate_prev_byte1
)
2052 || (translate_prev_byte2
== ptr
[-2]
2053 && (CHAR_HEAD_P (translate_prev_byte2
)
2054 || translate_prev_byte3
== ptr
[-3])))))))
2055 ch
= simple_translate
[*ptr
];
2061 /* Above loop has moved POS_BYTE part or all the way
2062 back to the first pos (last pos if reverse).
2063 Set it once again at the last (first if reverse) char. */
2064 pos_byte
+= dirlen
- i
- direction
;
2065 if (i
+ direction
== 0)
2067 int position
, start
, end
;
2068 pos_byte
-= direction
;
2070 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2071 set_search_regs (position
, len_byte
);
2073 if (NILP (Vinhibit_changing_match_data
))
2075 start
= search_regs
.start
[0];
2076 end
= search_regs
.end
[0];
2079 /* If Vinhibit_changing_match_data is non-nil,
2080 search_regs will not be changed. So let's
2081 compute start and end here. */
2083 start
= BYTE_TO_CHAR (position
);
2084 end
= BYTE_TO_CHAR (position
+ len_byte
);
2087 if ((n
-= direction
) != 0)
2088 pos_byte
+= dirlen
; /* to resume search */
2090 return direction
> 0 ? end
: start
;
2093 pos_byte
+= stride_for_teases
;
2096 /* We have done one clump. Can we continue? */
2097 if ((lim_byte
- pos_byte
) * direction
< 0)
2098 return ((0 - n
) * direction
);
2100 return BYTE_TO_CHAR (pos_byte
);
2103 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2104 for the overall match just found in the current buffer.
2105 Also clear out the match data for registers 1 and up. */
2108 set_search_regs (beg_byte
, nbytes
)
2109 int beg_byte
, nbytes
;
2113 if (!NILP (Vinhibit_changing_match_data
))
2116 /* Make sure we have registers in which to store
2117 the match position. */
2118 if (search_regs
.num_regs
== 0)
2120 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2121 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2122 search_regs
.num_regs
= 2;
2125 /* Clear out the other registers. */
2126 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2128 search_regs
.start
[i
] = -1;
2129 search_regs
.end
[i
] = -1;
2132 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2133 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2134 XSETBUFFER (last_thing_searched
, current_buffer
);
2137 /* Given a string of words separated by word delimiters,
2138 compute a regexp that matches those exact words
2139 separated by arbitrary punctuation. */
2145 register unsigned char *p
, *o
;
2146 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
2151 CHECK_STRING (string
);
2153 len
= SCHARS (string
);
2155 for (i
= 0, i_byte
= 0; i
< len
; )
2159 FETCH_STRING_CHAR_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 return empty_unibyte_string
;
2176 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
2177 if (STRING_MULTIBYTE (string
))
2178 val
= make_uninit_multibyte_string (len
+ adjust
,
2182 val
= make_uninit_string (len
+ adjust
);
2189 for (i
= 0, i_byte
= 0; i
< len
; )
2192 int i_byte_orig
= i_byte
;
2194 FETCH_STRING_CHAR_ADVANCE (c
, string
, i
, i_byte
);
2196 if (SYNTAX (c
) == Sword
)
2198 bcopy (SDATA (string
) + i_byte_orig
, o
,
2199 i_byte
- i_byte_orig
);
2200 o
+= i_byte
- i_byte_orig
;
2202 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
2220 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2221 "MSearch backward: ",
2222 doc
: /* Search backward from point for STRING.
2223 Set point to the beginning of the occurrence found, and return point.
2224 An optional second argument bounds the search; it is a buffer position.
2225 The match found must not extend before that position.
2226 Optional third argument, if t, means if fail just return nil (no error).
2227 If not nil and not t, position at limit of search and return nil.
2228 Optional fourth argument is repeat count--search for successive occurrences.
2230 Search case-sensitivity is determined by the value of the variable
2231 `case-fold-search', which see.
2233 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2234 (string
, bound
, noerror
, count
)
2235 Lisp_Object string
, bound
, noerror
, count
;
2237 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2240 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2241 doc
: /* Search forward from point for STRING.
2242 Set point to the end of the occurrence found, and return point.
2243 An optional second argument bounds the search; it is a buffer position.
2244 The match found must not extend after that position. A value of nil is
2245 equivalent to (point-max).
2246 Optional third argument, if t, means if fail just return nil (no error).
2247 If not nil and not t, move to limit of search and return nil.
2248 Optional fourth argument is repeat count--search for successive occurrences.
2250 Search case-sensitivity is determined by the value of the variable
2251 `case-fold-search', which see.
2253 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2254 (string
, bound
, noerror
, count
)
2255 Lisp_Object string
, bound
, noerror
, count
;
2257 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2260 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2261 "sWord search backward: ",
2262 doc
: /* Search backward from point for STRING, ignoring differences in punctuation.
2263 Set point to the beginning of the occurrence found, and return point.
2264 An optional second argument bounds the search; it is a buffer position.
2265 The match found must not extend before that position.
2266 Optional third argument, if t, means if fail just return nil (no error).
2267 If not nil and not t, move to limit of search and return nil.
2268 Optional fourth argument is repeat count--search for successive occurrences. */)
2269 (string
, bound
, noerror
, count
)
2270 Lisp_Object string
, bound
, noerror
, count
;
2272 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
2275 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2277 doc
: /* Search forward from point for STRING, ignoring differences in punctuation.
2278 Set point to the end of the occurrence found, and return point.
2279 An optional second argument bounds the search; it is a buffer position.
2280 The match found must not extend after that position.
2281 Optional third argument, if t, means if fail just return nil (no error).
2282 If not nil and not t, move to limit of search and return nil.
2283 Optional fourth argument is repeat count--search for successive occurrences. */)
2284 (string
, bound
, noerror
, count
)
2285 Lisp_Object string
, bound
, noerror
, count
;
2287 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
2290 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2291 "sRE search backward: ",
2292 doc
: /* Search backward from point for match for regular expression REGEXP.
2293 Set point to the beginning of the match, and return point.
2294 The match found is the one starting last in the buffer
2295 and yet ending before the origin of the search.
2296 An optional second argument bounds the search; it is a buffer position.
2297 The match found must start at or after that position.
2298 Optional third argument, if t, means if fail just return nil (no error).
2299 If not nil and not t, move to limit of search and return nil.
2300 Optional fourth argument is repeat count--search for successive occurrences.
2301 See also the functions `match-beginning', `match-end', `match-string',
2302 and `replace-match'. */)
2303 (regexp
, bound
, noerror
, count
)
2304 Lisp_Object regexp
, bound
, noerror
, count
;
2306 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2309 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2311 doc
: /* Search forward from point for regular expression REGEXP.
2312 Set point to the end of the occurrence found, and return point.
2313 An optional second argument bounds the search; it is a buffer position.
2314 The match found must not extend after that position.
2315 Optional third argument, if t, means if fail just return nil (no error).
2316 If not nil and not t, move to limit of search and return nil.
2317 Optional fourth argument is repeat count--search for successive occurrences.
2318 See also the functions `match-beginning', `match-end', `match-string',
2319 and `replace-match'. */)
2320 (regexp
, bound
, noerror
, count
)
2321 Lisp_Object regexp
, bound
, noerror
, count
;
2323 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2326 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2327 "sPosix search backward: ",
2328 doc
: /* Search backward from point for match for regular expression REGEXP.
2329 Find the longest match in accord with Posix regular expression rules.
2330 Set point to the beginning of the match, and return point.
2331 The match found is the one starting last in the buffer
2332 and yet ending before the origin of the search.
2333 An optional second argument bounds the search; it is a buffer position.
2334 The match found must start at or after that position.
2335 Optional third argument, if t, means if fail just return nil (no error).
2336 If not nil and not t, move to limit of search and return nil.
2337 Optional fourth argument is repeat count--search for successive occurrences.
2338 See also the functions `match-beginning', `match-end', `match-string',
2339 and `replace-match'. */)
2340 (regexp
, bound
, noerror
, count
)
2341 Lisp_Object regexp
, bound
, noerror
, count
;
2343 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2346 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2348 doc
: /* Search forward from point for regular expression REGEXP.
2349 Find the longest match in accord with Posix regular expression rules.
2350 Set point to the end of the occurrence found, and return point.
2351 An optional second argument bounds the search; it is a buffer position.
2352 The match found must not extend after that position.
2353 Optional third argument, if t, means if fail just return nil (no error).
2354 If not nil and not t, move to limit of search and return nil.
2355 Optional fourth argument is repeat count--search for successive occurrences.
2356 See also the functions `match-beginning', `match-end', `match-string',
2357 and `replace-match'. */)
2358 (regexp
, bound
, noerror
, count
)
2359 Lisp_Object regexp
, bound
, noerror
, count
;
2361 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2364 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2365 doc
: /* Replace text matched by last search with NEWTEXT.
2366 Leave point at the end of the replacement text.
2368 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2369 Otherwise maybe capitalize the whole text, or maybe just word initials,
2370 based on the replaced text.
2371 If the replaced text has only capital letters
2372 and has at least one multiletter word, convert NEWTEXT to all caps.
2373 Otherwise if all words are capitalized in the replaced text,
2374 capitalize each word in NEWTEXT.
2376 If third arg LITERAL is non-nil, insert NEWTEXT literally.
2377 Otherwise treat `\\' as special:
2378 `\\&' in NEWTEXT means substitute original matched text.
2379 `\\N' means substitute what matched the Nth `\\(...\\)'.
2380 If Nth parens didn't match, substitute nothing.
2381 `\\\\' means insert one `\\'.
2382 Case conversion does not apply to these substitutions.
2384 FIXEDCASE and LITERAL are optional arguments.
2386 The optional fourth argument STRING can be a string to modify.
2387 This is meaningful when the previous match was done against STRING,
2388 using `string-match'. When used this way, `replace-match'
2389 creates and returns a new string made by copying STRING and replacing
2390 the part of STRING that was matched.
2392 The optional fifth argument SUBEXP specifies a subexpression;
2393 it says to replace just that subexpression with NEWTEXT,
2394 rather than replacing the entire matched text.
2395 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2396 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2397 NEWTEXT in place of subexp N.
2398 This is useful only after a regular expression search or match,
2399 since only regular expressions have distinguished subexpressions. */)
2400 (newtext
, fixedcase
, literal
, string
, subexp
)
2401 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2403 enum { nochange
, all_caps
, cap_initial
} case_action
;
2404 register int pos
, pos_byte
;
2405 int some_multiletter_word
;
2408 int some_nonuppercase_initial
;
2409 register int c
, prevc
;
2411 int opoint
, newpoint
;
2413 CHECK_STRING (newtext
);
2415 if (! NILP (string
))
2416 CHECK_STRING (string
);
2418 case_action
= nochange
; /* We tried an initialization */
2419 /* but some C compilers blew it */
2421 if (search_regs
.num_regs
<= 0)
2422 error ("`replace-match' called before any match found");
2428 CHECK_NUMBER (subexp
);
2429 sub
= XINT (subexp
);
2430 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2431 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2436 if (search_regs
.start
[sub
] < BEGV
2437 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2438 || search_regs
.end
[sub
] > ZV
)
2439 args_out_of_range (make_number (search_regs
.start
[sub
]),
2440 make_number (search_regs
.end
[sub
]));
2444 if (search_regs
.start
[sub
] < 0
2445 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2446 || search_regs
.end
[sub
] > SCHARS (string
))
2447 args_out_of_range (make_number (search_regs
.start
[sub
]),
2448 make_number (search_regs
.end
[sub
]));
2451 if (NILP (fixedcase
))
2453 /* Decide how to casify by examining the matched text. */
2456 pos
= search_regs
.start
[sub
];
2457 last
= search_regs
.end
[sub
];
2460 pos_byte
= CHAR_TO_BYTE (pos
);
2462 pos_byte
= string_char_to_byte (string
, pos
);
2465 case_action
= all_caps
;
2467 /* some_multiletter_word is set nonzero if any original word
2468 is more than one letter long. */
2469 some_multiletter_word
= 0;
2471 some_nonuppercase_initial
= 0;
2478 c
= FETCH_CHAR (pos_byte
);
2479 INC_BOTH (pos
, pos_byte
);
2482 FETCH_STRING_CHAR_ADVANCE (c
, string
, pos
, pos_byte
);
2486 /* Cannot be all caps if any original char is lower case */
2489 if (SYNTAX (prevc
) != Sword
)
2490 some_nonuppercase_initial
= 1;
2492 some_multiletter_word
= 1;
2494 else if (UPPERCASEP (c
))
2497 if (SYNTAX (prevc
) != Sword
)
2500 some_multiletter_word
= 1;
2504 /* If the initial is a caseless word constituent,
2505 treat that like a lowercase initial. */
2506 if (SYNTAX (prevc
) != Sword
)
2507 some_nonuppercase_initial
= 1;
2513 /* Convert to all caps if the old text is all caps
2514 and has at least one multiletter word. */
2515 if (! some_lowercase
&& some_multiletter_word
)
2516 case_action
= all_caps
;
2517 /* Capitalize each word, if the old text has all capitalized words. */
2518 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2519 case_action
= cap_initial
;
2520 else if (!some_nonuppercase_initial
&& some_uppercase
)
2521 /* Should x -> yz, operating on X, give Yz or YZ?
2522 We'll assume the latter. */
2523 case_action
= all_caps
;
2525 case_action
= nochange
;
2528 /* Do replacement in a string. */
2531 Lisp_Object before
, after
;
2533 before
= Fsubstring (string
, make_number (0),
2534 make_number (search_regs
.start
[sub
]));
2535 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2537 /* Substitute parts of the match into NEWTEXT
2542 int lastpos_byte
= 0;
2543 /* We build up the substituted string in ACCUM. */
2546 int length
= SBYTES (newtext
);
2550 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2554 int delbackslash
= 0;
2556 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2560 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2564 substart
= search_regs
.start
[sub
];
2565 subend
= search_regs
.end
[sub
];
2567 else if (c
>= '1' && c
<= '9')
2569 if (search_regs
.start
[c
- '0'] >= 0
2570 && c
<= search_regs
.num_regs
+ '0')
2572 substart
= search_regs
.start
[c
- '0'];
2573 subend
= search_regs
.end
[c
- '0'];
2577 /* If that subexp did not match,
2578 replace \\N with nothing. */
2586 error ("Invalid use of `\\' in replacement text");
2590 if (pos
- 2 != lastpos
)
2591 middle
= substring_both (newtext
, lastpos
,
2593 pos
- 2, pos_byte
- 2);
2596 accum
= concat3 (accum
, middle
,
2598 make_number (substart
),
2599 make_number (subend
)));
2601 lastpos_byte
= pos_byte
;
2603 else if (delbackslash
)
2605 middle
= substring_both (newtext
, lastpos
,
2607 pos
- 1, pos_byte
- 1);
2609 accum
= concat2 (accum
, middle
);
2611 lastpos_byte
= pos_byte
;
2616 middle
= substring_both (newtext
, lastpos
,
2622 newtext
= concat2 (accum
, middle
);
2625 /* Do case substitution in NEWTEXT if desired. */
2626 if (case_action
== all_caps
)
2627 newtext
= Fupcase (newtext
);
2628 else if (case_action
== cap_initial
)
2629 newtext
= Fupcase_initials (newtext
);
2631 return concat3 (before
, newtext
, after
);
2634 /* Record point, then move (quietly) to the start of the match. */
2635 if (PT
>= search_regs
.end
[sub
])
2637 else if (PT
> search_regs
.start
[sub
])
2638 opoint
= search_regs
.end
[sub
] - ZV
;
2642 /* If we want non-literal replacement,
2643 perform substitution on the replacement string. */
2646 int length
= SBYTES (newtext
);
2647 unsigned char *substed
;
2648 int substed_alloc_size
, substed_len
;
2649 int buf_multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
2650 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2651 Lisp_Object rev_tbl
;
2652 int really_changed
= 0;
2654 rev_tbl
= (!buf_multibyte
&& CHAR_TABLE_P (Vnonascii_translation_table
)
2655 ? Fchar_table_extra_slot (Vnonascii_translation_table
,
2659 substed_alloc_size
= length
* 2 + 100;
2660 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2663 /* Go thru NEWTEXT, producing the actual text to insert in
2664 SUBSTED while adjusting multibyteness to that of the current
2667 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2669 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2670 unsigned char *add_stuff
= NULL
;
2676 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2678 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2682 /* Note that we don't have to increment POS. */
2683 c
= SREF (newtext
, pos_byte
++);
2685 c
= unibyte_char_to_multibyte (c
);
2688 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2689 or set IDX to a match index, which means put that part
2690 of the buffer text into SUBSTED. */
2698 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2700 if (!buf_multibyte
&& !SINGLE_BYTE_CHAR_P (c
))
2701 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2705 c
= SREF (newtext
, pos_byte
++);
2707 c
= unibyte_char_to_multibyte (c
);
2712 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2714 if (search_regs
.start
[c
- '0'] >= 1)
2718 add_len
= 1, add_stuff
= "\\";
2722 error ("Invalid use of `\\' in replacement text");
2727 add_len
= CHAR_STRING (c
, str
);
2731 /* If we want to copy part of a previous match,
2732 set up ADD_STUFF and ADD_LEN to point to it. */
2735 int begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2736 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2737 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2738 move_gap (search_regs
.start
[idx
]);
2739 add_stuff
= BYTE_POS_ADDR (begbyte
);
2742 /* Now the stuff we want to add to SUBSTED
2743 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2745 /* Make sure SUBSTED is big enough. */
2746 if (substed_len
+ add_len
>= substed_alloc_size
)
2748 substed_alloc_size
= substed_len
+ add_len
+ 500;
2749 substed
= (unsigned char *) xrealloc (substed
,
2750 substed_alloc_size
+ 1);
2753 /* Now add to the end of SUBSTED. */
2756 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2757 substed_len
+= add_len
;
2765 int nchars
= multibyte_chars_in_text (substed
, substed_len
);
2767 newtext
= make_multibyte_string (substed
, nchars
, substed_len
);
2770 newtext
= make_unibyte_string (substed
, substed_len
);
2775 /* Replace the old text with the new in the cleanest possible way. */
2776 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2778 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2780 if (case_action
== all_caps
)
2781 Fupcase_region (make_number (search_regs
.start
[sub
]),
2782 make_number (newpoint
));
2783 else if (case_action
== cap_initial
)
2784 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2785 make_number (newpoint
));
2787 /* Adjust search data for this change. */
2789 int oldend
= search_regs
.end
[sub
];
2790 int oldstart
= search_regs
.start
[sub
];
2791 int change
= newpoint
- search_regs
.end
[sub
];
2794 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2796 if (search_regs
.start
[i
] >= oldend
)
2797 search_regs
.start
[i
] += change
;
2798 else if (search_regs
.start
[i
] > oldstart
)
2799 search_regs
.start
[i
] = oldstart
;
2800 if (search_regs
.end
[i
] >= oldend
)
2801 search_regs
.end
[i
] += change
;
2802 else if (search_regs
.end
[i
] > oldstart
)
2803 search_regs
.end
[i
] = oldstart
;
2807 /* Put point back where it was in the text. */
2809 TEMP_SET_PT (opoint
+ ZV
);
2811 TEMP_SET_PT (opoint
);
2813 /* Now move point "officially" to the start of the inserted replacement. */
2814 move_if_not_intangible (newpoint
);
2820 match_limit (num
, beginningp
)
2829 args_out_of_range (num
, make_number (0));
2830 if (search_regs
.num_regs
<= 0)
2831 error ("No match data, because no search succeeded");
2832 if (n
>= search_regs
.num_regs
2833 || search_regs
.start
[n
] < 0)
2835 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2836 : search_regs
.end
[n
]));
2839 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2840 doc
: /* Return position of start of text matched by last search.
2841 SUBEXP, a number, specifies which parenthesized expression in the last
2843 Value is nil if SUBEXPth pair didn't match, or there were less than
2845 Zero means the entire text matched by the whole regexp or whole string. */)
2849 return match_limit (subexp
, 1);
2852 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2853 doc
: /* Return position of end of text matched by last search.
2854 SUBEXP, a number, specifies which parenthesized expression in the last
2856 Value is nil if SUBEXPth pair didn't match, or there were less than
2858 Zero means the entire text matched by the whole regexp or whole string. */)
2862 return match_limit (subexp
, 0);
2865 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2866 doc
: /* Return a list containing all info on what the last search matched.
2867 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2868 All the elements are markers or nil (nil if the Nth pair didn't match)
2869 if the last match was on a buffer; integers or nil if a string was matched.
2870 Use `store-match-data' to reinstate the data in this list.
2872 If INTEGERS (the optional first argument) is non-nil, always use
2873 integers \(rather than markers) to represent buffer positions. In
2874 this case, and if the last match was in a buffer, the buffer will get
2875 stored as one additional element at the end of the list.
2877 If REUSE is a list, reuse it as part of the value. If REUSE is long
2878 enough to hold all the values, and if INTEGERS is non-nil, no consing
2881 If optional third arg RESEAT is non-nil, any previous markers on the
2882 REUSE list will be modified to point to nowhere.
2884 Return value is undefined if the last search failed. */)
2885 (integers
, reuse
, reseat
)
2886 Lisp_Object integers
, reuse
, reseat
;
2888 Lisp_Object tail
, prev
;
2893 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2894 if (MARKERP (XCAR (tail
)))
2896 unchain_marker (XMARKER (XCAR (tail
)));
2897 XSETCAR (tail
, Qnil
);
2900 if (NILP (last_thing_searched
))
2905 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
+ 1)
2906 * sizeof (Lisp_Object
));
2909 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2911 int start
= search_regs
.start
[i
];
2914 if (EQ (last_thing_searched
, Qt
)
2915 || ! NILP (integers
))
2917 XSETFASTINT (data
[2 * i
], start
);
2918 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2920 else if (BUFFERP (last_thing_searched
))
2922 data
[2 * i
] = Fmake_marker ();
2923 Fset_marker (data
[2 * i
],
2924 make_number (start
),
2925 last_thing_searched
);
2926 data
[2 * i
+ 1] = Fmake_marker ();
2927 Fset_marker (data
[2 * i
+ 1],
2928 make_number (search_regs
.end
[i
]),
2929 last_thing_searched
);
2932 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2938 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2941 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2943 data
[len
] = last_thing_searched
;
2947 /* If REUSE is not usable, cons up the values and return them. */
2948 if (! CONSP (reuse
))
2949 return Flist (len
, data
);
2951 /* If REUSE is a list, store as many value elements as will fit
2952 into the elements of REUSE. */
2953 for (i
= 0, tail
= reuse
; CONSP (tail
);
2954 i
++, tail
= XCDR (tail
))
2957 XSETCAR (tail
, data
[i
]);
2959 XSETCAR (tail
, Qnil
);
2963 /* If we couldn't fit all value elements into REUSE,
2964 cons up the rest of them and add them to the end of REUSE. */
2966 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2971 /* Internal usage only:
2972 If RESEAT is `evaporate', put the markers back on the free list
2973 immediately. No other references to the markers must exist in this case,
2974 so it is used only internally on the unwind stack and save-match-data from
2977 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2978 doc
: /* Set internal data on last search match from elements of LIST.
2979 LIST should have been created by calling `match-data' previously.
2981 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2983 register Lisp_Object list
, reseat
;
2986 register Lisp_Object marker
;
2988 if (running_asynch_code
)
2989 save_search_regs ();
2993 /* Unless we find a marker with a buffer or an explicit buffer
2994 in LIST, assume that this match data came from a string. */
2995 last_thing_searched
= Qt
;
2997 /* Allocate registers if they don't already exist. */
2999 int length
= XFASTINT (Flength (list
)) / 2;
3001 if (length
> search_regs
.num_regs
)
3003 if (search_regs
.num_regs
== 0)
3006 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
3008 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
3013 = (regoff_t
*) xrealloc (search_regs
.start
,
3014 length
* sizeof (regoff_t
));
3016 = (regoff_t
*) xrealloc (search_regs
.end
,
3017 length
* sizeof (regoff_t
));
3020 for (i
= search_regs
.num_regs
; i
< length
; i
++)
3021 search_regs
.start
[i
] = -1;
3023 search_regs
.num_regs
= length
;
3026 for (i
= 0; CONSP (list
); i
++)
3028 marker
= XCAR (list
);
3029 if (BUFFERP (marker
))
3031 last_thing_searched
= marker
;
3038 search_regs
.start
[i
] = -1;
3047 if (MARKERP (marker
))
3049 if (XMARKER (marker
)->buffer
== 0)
3050 XSETFASTINT (marker
, 0);
3052 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
3055 CHECK_NUMBER_COERCE_MARKER (marker
);
3056 from
= XINT (marker
);
3058 if (!NILP (reseat
) && MARKERP (m
))
3060 if (EQ (reseat
, Qevaporate
))
3063 unchain_marker (XMARKER (m
));
3064 XSETCAR (list
, Qnil
);
3067 if ((list
= XCDR (list
), !CONSP (list
)))
3070 m
= marker
= XCAR (list
);
3072 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
3073 XSETFASTINT (marker
, 0);
3075 CHECK_NUMBER_COERCE_MARKER (marker
);
3076 search_regs
.start
[i
] = from
;
3077 search_regs
.end
[i
] = XINT (marker
);
3079 if (!NILP (reseat
) && MARKERP (m
))
3081 if (EQ (reseat
, Qevaporate
))
3084 unchain_marker (XMARKER (m
));
3085 XSETCAR (list
, Qnil
);
3091 for (; i
< search_regs
.num_regs
; i
++)
3092 search_regs
.start
[i
] = -1;
3098 /* If non-zero the match data have been saved in saved_search_regs
3099 during the execution of a sentinel or filter. */
3100 static int search_regs_saved
;
3101 static struct re_registers saved_search_regs
;
3102 static Lisp_Object saved_last_thing_searched
;
3104 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3105 if asynchronous code (filter or sentinel) is running. */
3109 if (!search_regs_saved
)
3111 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3112 saved_search_regs
.start
= search_regs
.start
;
3113 saved_search_regs
.end
= search_regs
.end
;
3114 saved_last_thing_searched
= last_thing_searched
;
3115 last_thing_searched
= Qnil
;
3116 search_regs
.num_regs
= 0;
3117 search_regs
.start
= 0;
3118 search_regs
.end
= 0;
3120 search_regs_saved
= 1;
3124 /* Called upon exit from filters and sentinels. */
3126 restore_search_regs ()
3128 if (search_regs_saved
)
3130 if (search_regs
.num_regs
> 0)
3132 xfree (search_regs
.start
);
3133 xfree (search_regs
.end
);
3135 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3136 search_regs
.start
= saved_search_regs
.start
;
3137 search_regs
.end
= saved_search_regs
.end
;
3138 last_thing_searched
= saved_last_thing_searched
;
3139 saved_last_thing_searched
= Qnil
;
3140 search_regs_saved
= 0;
3145 unwind_set_match_data (list
)
3148 /* It is safe to free (evaporate) the markers immediately. */
3149 return Fset_match_data (list
, Qevaporate
);
3152 /* Called to unwind protect the match data. */
3154 record_unwind_save_match_data ()
3156 record_unwind_protect (unwind_set_match_data
,
3157 Fmatch_data (Qnil
, Qnil
, Qnil
));
3160 /* Quote a string to inactivate reg-expr chars */
3162 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3163 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3167 register unsigned char *in
, *out
, *end
;
3168 register unsigned char *temp
;
3169 int backslashes_added
= 0;
3171 CHECK_STRING (string
);
3173 temp
= (unsigned char *) alloca (SBYTES (string
) * 2);
3175 /* Now copy the data into the new string, inserting escapes. */
3177 in
= SDATA (string
);
3178 end
= in
+ SBYTES (string
);
3181 for (; in
!= end
; in
++)
3184 || *in
== '*' || *in
== '.' || *in
== '\\'
3185 || *in
== '?' || *in
== '+'
3186 || *in
== '^' || *in
== '$')
3187 *out
++ = '\\', backslashes_added
++;
3191 return make_specified_string (temp
,
3192 SCHARS (string
) + backslashes_added
,
3194 STRING_MULTIBYTE (string
));
3202 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3204 searchbufs
[i
].buf
.allocated
= 100;
3205 searchbufs
[i
].buf
.buffer
= (unsigned char *) xmalloc (100);
3206 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3207 searchbufs
[i
].regexp
= Qnil
;
3208 searchbufs
[i
].whitespace_regexp
= Qnil
;
3209 searchbufs
[i
].syntax_table
= Qnil
;
3210 staticpro (&searchbufs
[i
].regexp
);
3211 staticpro (&searchbufs
[i
].whitespace_regexp
);
3212 staticpro (&searchbufs
[i
].syntax_table
);
3213 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3215 searchbuf_head
= &searchbufs
[0];
3217 Qsearch_failed
= intern ("search-failed");
3218 staticpro (&Qsearch_failed
);
3219 Qinvalid_regexp
= intern ("invalid-regexp");
3220 staticpro (&Qinvalid_regexp
);
3222 Fput (Qsearch_failed
, Qerror_conditions
,
3223 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
3224 Fput (Qsearch_failed
, Qerror_message
,
3225 build_string ("Search failed"));
3227 Fput (Qinvalid_regexp
, Qerror_conditions
,
3228 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
3229 Fput (Qinvalid_regexp
, Qerror_message
,
3230 build_string ("Invalid regexp"));
3232 last_thing_searched
= Qnil
;
3233 staticpro (&last_thing_searched
);
3235 saved_last_thing_searched
= Qnil
;
3236 staticpro (&saved_last_thing_searched
);
3238 DEFVAR_LISP ("search-spaces-regexp", &Vsearch_spaces_regexp
,
3239 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3240 Some commands use this for user-specified regexps.
3241 Spaces that occur inside character classes or repetition operators
3242 or other such regexp constructs are not replaced with this.
3243 A value of nil (which is the normal value) means treat spaces literally. */);
3244 Vsearch_spaces_regexp
= Qnil
;
3246 DEFVAR_LISP ("inhibit-changing-match-data", &Vinhibit_changing_match_data
,
3247 doc
: /* Internal use only.
3248 If non-nil, the match data will not be changed during call to searching or
3249 matching functions, such as `looking-at', `string-match', `re-search-forward'
3251 Vinhibit_changing_match_data
= Qnil
;
3253 defsubr (&Slooking_at
);
3254 defsubr (&Sposix_looking_at
);
3255 defsubr (&Sstring_match
);
3256 defsubr (&Sposix_string_match
);
3257 defsubr (&Ssearch_forward
);
3258 defsubr (&Ssearch_backward
);
3259 defsubr (&Sword_search_forward
);
3260 defsubr (&Sword_search_backward
);
3261 defsubr (&Sre_search_forward
);
3262 defsubr (&Sre_search_backward
);
3263 defsubr (&Sposix_search_forward
);
3264 defsubr (&Sposix_search_backward
);
3265 defsubr (&Sreplace_match
);
3266 defsubr (&Smatch_beginning
);
3267 defsubr (&Smatch_end
);
3268 defsubr (&Smatch_data
);
3269 defsubr (&Sset_match_data
);
3270 defsubr (&Sregexp_quote
);
3273 /* arch-tag: a6059d79-0552-4f14-a2cb-d379a4e3c78f
3274 (do not change this comment) */