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 2, or (at your option)
12 GNU Emacs is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Emacs; see the file COPYING. If not, write to
19 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
28 #include "character.h"
29 #include "region-cache.h"
31 #include "blockinput.h"
32 #include "intervals.h"
34 #include <sys/types.h>
37 #define REGEXP_CACHE_SIZE 20
39 /* If the regexp is non-nil, then the buffer contains the compiled form
40 of that regexp, suitable for searching. */
43 struct regexp_cache
*next
;
44 Lisp_Object regexp
, whitespace_regexp
;
45 /* 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 static void set_search_regs ();
96 static void save_search_regs ();
97 static int simple_search ();
98 static int boyer_moore ();
99 static int search_buffer ();
100 static void matcher_overflow () NO_RETURN
;
105 error ("Stack overflow in regexp matcher");
108 /* Compile a regexp and signal a Lisp error if anything goes wrong.
109 PATTERN is the pattern to compile.
110 CP is the place to put the result.
111 TRANSLATE is a translation table for ignoring case, or nil for none.
112 REGP is the structure that says where to store the "register"
113 values that will result from matching this pattern.
114 If it is 0, we should compile the pattern not to record any
115 subexpression bounds.
116 POSIX is nonzero if we want full backtracking (POSIX style)
117 for this pattern. 0 means backtrack only enough to get a valid match.
118 MULTIBYTE is nonzero iff a target of match is a multibyte buffer or
121 The behavior also depends on Vsearch_spaces_regexp. */
124 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
125 struct regexp_cache
*cp
;
127 Lisp_Object translate
;
128 struct re_registers
*regp
;
136 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
138 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
139 cp
->buf
.target_multibyte
= multibyte
;
140 cp
->whitespace_regexp
= Vsearch_spaces_regexp
;
141 /* rms: I think BLOCK_INPUT is not needed here any more,
142 because regex.c defines malloc to call xmalloc.
143 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
144 So let's turn it off. */
146 old
= re_set_syntax (RE_SYNTAX_EMACS
147 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
148 re_set_whitespace_regexp (NILP (Vsearch_spaces_regexp
) ? NULL
149 : SDATA (Vsearch_spaces_regexp
));
151 val
= (char *) re_compile_pattern ((char *) SDATA (pattern
),
152 SBYTES (pattern
), &cp
->buf
);
154 /* If the compiled pattern hard codes some of the contents of the
155 syntax-table, it can only be reused with *this* syntax table. */
156 cp
->syntax_table
= cp
->buf
.used_syntax
? current_buffer
->syntax_table
: Qt
;
158 re_set_whitespace_regexp (NULL
);
163 xsignal1 (Qinvalid_regexp
, build_string (val
));
165 cp
->regexp
= Fcopy_sequence (pattern
);
168 /* Shrink each compiled regexp buffer in the cache
169 to the size actually used right now.
170 This is called from garbage collection. */
173 shrink_regexp_cache ()
175 struct regexp_cache
*cp
;
177 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
179 cp
->buf
.allocated
= cp
->buf
.used
;
181 = (unsigned char *) xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
185 /* Clear the regexp cache w.r.t. a particular syntax table,
186 because it was changed.
187 There is no danger of memory leak here because re_compile_pattern
188 automagically manages the memory in each re_pattern_buffer struct,
189 based on its `allocated' and `buffer' values. */
191 clear_regexp_cache ()
195 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
196 /* It's tempting to compare with the syntax-table we've actually changd,
197 but it's not sufficient because char-table inheritance mewans that
198 modifying one syntax-table can change others at the same time. */
199 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
200 searchbufs
[i
].regexp
= Qnil
;
203 /* Compile a regexp if necessary, but first check to see if there's one in
205 PATTERN is the pattern to compile.
206 TRANSLATE is a translation table for ignoring case, or nil for none.
207 REGP is the structure that says where to store the "register"
208 values that will result from matching this pattern.
209 If it is 0, we should compile the pattern not to record any
210 subexpression bounds.
211 POSIX is nonzero if we want full backtracking (POSIX style)
212 for this pattern. 0 means backtrack only enough to get a valid match. */
214 struct re_pattern_buffer
*
215 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
217 struct re_registers
*regp
;
218 Lisp_Object translate
;
219 int posix
, multibyte
;
221 struct regexp_cache
*cp
, **cpp
;
223 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
226 /* Entries are initialized to nil, and may be set to nil by
227 compile_pattern_1 if the pattern isn't valid. Don't apply
228 string accessors in those cases. However, compile_pattern_1
229 is only applied to the cache entry we pick here to reuse. So
230 nil should never appear before a non-nil entry. */
231 if (NILP (cp
->regexp
))
233 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
234 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
235 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
236 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
237 && cp
->posix
== posix
238 && cp
->buf
.target_multibyte
== multibyte
239 && (EQ (cp
->syntax_table
, Qt
)
240 || EQ (cp
->syntax_table
, current_buffer
->syntax_table
))
241 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
)))
244 /* If we're at the end of the cache, compile into the nil cell
245 we found, or the last (least recently used) cell with a
250 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
255 /* When we get here, cp (aka *cpp) contains the compiled pattern,
256 either because we found it in the cache or because we just compiled it.
257 Move it to the front of the queue to mark it as most recently used. */
259 cp
->next
= searchbuf_head
;
262 /* Advise the searching functions about the space we have allocated
263 for register data. */
265 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
272 looking_at_1 (string
, posix
)
277 unsigned char *p1
, *p2
;
280 struct re_pattern_buffer
*bufp
;
282 if (running_asynch_code
)
285 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
286 XCHAR_TABLE (current_buffer
->case_canon_table
)->extras
[2]
287 = current_buffer
->case_eqv_table
;
289 CHECK_STRING (string
);
290 bufp
= compile_pattern (string
, &search_regs
,
291 (!NILP (current_buffer
->case_fold_search
)
292 ? current_buffer
->case_canon_table
: Qnil
),
294 !NILP (current_buffer
->enable_multibyte_characters
));
297 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
299 /* Get pointers and sizes of the two strings
300 that make up the visible portion of the buffer. */
303 s1
= GPT_BYTE
- BEGV_BYTE
;
305 s2
= ZV_BYTE
- GPT_BYTE
;
309 s2
= ZV_BYTE
- BEGV_BYTE
;
314 s1
= ZV_BYTE
- BEGV_BYTE
;
318 re_match_object
= Qnil
;
320 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
321 PT_BYTE
- BEGV_BYTE
, &search_regs
,
322 ZV_BYTE
- BEGV_BYTE
);
328 val
= (0 <= i
? Qt
: Qnil
);
330 for (i
= 0; i
< search_regs
.num_regs
; i
++)
331 if (search_regs
.start
[i
] >= 0)
334 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
336 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
338 XSETBUFFER (last_thing_searched
, current_buffer
);
342 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
343 doc
: /* Return t if text after point matches regular expression REGEXP.
344 This function modifies the match data that `match-beginning',
345 `match-end' and `match-data' access; save and restore the match
346 data if you want to preserve them. */)
350 return looking_at_1 (regexp
, 0);
353 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
354 doc
: /* Return t if text after point matches regular expression REGEXP.
355 Find the longest match, in accord with Posix regular expression rules.
356 This function modifies the match data that `match-beginning',
357 `match-end' and `match-data' access; save and restore the match
358 data if you want to preserve them. */)
362 return looking_at_1 (regexp
, 1);
366 string_match_1 (regexp
, string
, start
, posix
)
367 Lisp_Object regexp
, string
, start
;
371 struct re_pattern_buffer
*bufp
;
375 if (running_asynch_code
)
378 CHECK_STRING (regexp
);
379 CHECK_STRING (string
);
382 pos
= 0, pos_byte
= 0;
385 int len
= SCHARS (string
);
387 CHECK_NUMBER (start
);
389 if (pos
< 0 && -pos
<= len
)
391 else if (0 > pos
|| pos
> len
)
392 args_out_of_range (string
, start
);
393 pos_byte
= string_char_to_byte (string
, pos
);
396 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
397 XCHAR_TABLE (current_buffer
->case_canon_table
)->extras
[2]
398 = current_buffer
->case_eqv_table
;
400 bufp
= compile_pattern (regexp
, &search_regs
,
401 (!NILP (current_buffer
->case_fold_search
)
402 ? current_buffer
->case_canon_table
: Qnil
),
404 STRING_MULTIBYTE (string
));
406 re_match_object
= string
;
408 val
= re_search (bufp
, (char *) SDATA (string
),
409 SBYTES (string
), pos_byte
,
410 SBYTES (string
) - pos_byte
,
413 last_thing_searched
= Qt
;
416 if (val
< 0) return Qnil
;
418 for (i
= 0; i
< search_regs
.num_regs
; i
++)
419 if (search_regs
.start
[i
] >= 0)
422 = string_byte_to_char (string
, search_regs
.start
[i
]);
424 = string_byte_to_char (string
, search_regs
.end
[i
]);
427 return make_number (string_byte_to_char (string
, val
));
430 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
431 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
432 Matching ignores case if `case-fold-search' is non-nil.
433 If third arg START is non-nil, start search at that index in STRING.
434 For index of first char beyond the match, do (match-end 0).
435 `match-end' and `match-beginning' also give indices of substrings
436 matched by parenthesis constructs in the pattern.
438 You can use the function `match-string' to extract the substrings
439 matched by the parenthesis constructions in REGEXP. */)
440 (regexp
, string
, start
)
441 Lisp_Object regexp
, string
, start
;
443 return string_match_1 (regexp
, string
, start
, 0);
446 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
447 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
448 Find the longest match, in accord with Posix regular expression rules.
449 Case is ignored if `case-fold-search' is non-nil in the current buffer.
450 If third arg START is non-nil, start search at that index in STRING.
451 For index of first char beyond the match, do (match-end 0).
452 `match-end' and `match-beginning' also give indices of substrings
453 matched by parenthesis constructs in the pattern. */)
454 (regexp
, string
, start
)
455 Lisp_Object regexp
, string
, start
;
457 return string_match_1 (regexp
, string
, start
, 1);
460 /* Match REGEXP against STRING, searching all of STRING,
461 and return the index of the match, or negative on failure.
462 This does not clobber the match data. */
465 fast_string_match (regexp
, string
)
466 Lisp_Object regexp
, string
;
469 struct re_pattern_buffer
*bufp
;
471 bufp
= compile_pattern (regexp
, 0, Qnil
,
472 0, STRING_MULTIBYTE (string
));
474 re_match_object
= string
;
476 val
= re_search (bufp
, (char *) SDATA (string
),
483 /* Match REGEXP against STRING, searching all of STRING ignoring case,
484 and return the index of the match, or negative on failure.
485 This does not clobber the match data.
486 We assume that STRING contains single-byte characters. */
488 extern Lisp_Object Vascii_downcase_table
;
491 fast_c_string_match_ignore_case (regexp
, string
)
496 struct re_pattern_buffer
*bufp
;
497 int len
= strlen (string
);
499 regexp
= string_make_unibyte (regexp
);
500 re_match_object
= Qt
;
501 bufp
= compile_pattern (regexp
, 0,
502 Vascii_canon_table
, 0,
505 val
= re_search (bufp
, string
, len
, 0, len
, 0);
510 /* Like fast_string_match but ignore case. */
513 fast_string_match_ignore_case (regexp
, string
)
514 Lisp_Object regexp
, string
;
517 struct re_pattern_buffer
*bufp
;
519 bufp
= compile_pattern (regexp
, 0, Vascii_canon_table
,
520 0, STRING_MULTIBYTE (string
));
522 re_match_object
= string
;
524 val
= re_search (bufp
, (char *) SDATA (string
),
531 /* The newline cache: remembering which sections of text have no newlines. */
533 /* If the user has requested newline caching, make sure it's on.
534 Otherwise, make sure it's off.
535 This is our cheezy way of associating an action with the change of
536 state of a buffer-local variable. */
538 newline_cache_on_off (buf
)
541 if (NILP (buf
->cache_long_line_scans
))
543 /* It should be off. */
544 if (buf
->newline_cache
)
546 free_region_cache (buf
->newline_cache
);
547 buf
->newline_cache
= 0;
552 /* It should be on. */
553 if (buf
->newline_cache
== 0)
554 buf
->newline_cache
= new_region_cache ();
559 /* Search for COUNT instances of the character TARGET between START and END.
561 If COUNT is positive, search forwards; END must be >= START.
562 If COUNT is negative, search backwards for the -COUNTth instance;
563 END must be <= START.
564 If COUNT is zero, do anything you please; run rogue, for all I care.
566 If END is zero, use BEGV or ZV instead, as appropriate for the
567 direction indicated by COUNT.
569 If we find COUNT instances, set *SHORTAGE to zero, and return the
570 position past the COUNTth match. Note that for reverse motion
571 this is not the same as the usual convention for Emacs motion commands.
573 If we don't find COUNT instances before reaching END, set *SHORTAGE
574 to the number of TARGETs left unfound, and return END.
576 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
577 except when inside redisplay. */
580 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
587 struct region_cache
*newline_cache
;
598 if (! end
) end
= BEGV
;
601 newline_cache_on_off (current_buffer
);
602 newline_cache
= current_buffer
->newline_cache
;
607 immediate_quit
= allow_quit
;
612 /* Our innermost scanning loop is very simple; it doesn't know
613 about gaps, buffer ends, or the newline cache. ceiling is
614 the position of the last character before the next such
615 obstacle --- the last character the dumb search loop should
617 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
618 int start_byte
= CHAR_TO_BYTE (start
);
621 /* If we're looking for a newline, consult the newline cache
622 to see where we can avoid some scanning. */
623 if (target
== '\n' && newline_cache
)
627 while (region_cache_forward
628 (current_buffer
, newline_cache
, start_byte
, &next_change
))
629 start_byte
= next_change
;
630 immediate_quit
= allow_quit
;
632 /* START should never be after END. */
633 if (start_byte
> ceiling_byte
)
634 start_byte
= ceiling_byte
;
636 /* Now the text after start is an unknown region, and
637 next_change is the position of the next known region. */
638 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
641 /* The dumb loop can only scan text stored in contiguous
642 bytes. BUFFER_CEILING_OF returns the last character
643 position that is contiguous, so the ceiling is the
644 position after that. */
645 tem
= BUFFER_CEILING_OF (start_byte
);
646 ceiling_byte
= min (tem
, ceiling_byte
);
649 /* The termination address of the dumb loop. */
650 register unsigned char *ceiling_addr
651 = BYTE_POS_ADDR (ceiling_byte
) + 1;
652 register unsigned char *cursor
653 = BYTE_POS_ADDR (start_byte
);
654 unsigned char *base
= cursor
;
656 while (cursor
< ceiling_addr
)
658 unsigned char *scan_start
= cursor
;
661 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
664 /* If we're looking for newlines, cache the fact that
665 the region from start to cursor is free of them. */
666 if (target
== '\n' && newline_cache
)
667 know_region_cache (current_buffer
, newline_cache
,
668 start_byte
+ scan_start
- base
,
669 start_byte
+ cursor
- base
);
671 /* Did we find the target character? */
672 if (cursor
< ceiling_addr
)
677 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
683 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
689 /* The last character to check before the next obstacle. */
690 int ceiling_byte
= CHAR_TO_BYTE (end
);
691 int start_byte
= CHAR_TO_BYTE (start
);
694 /* Consult the newline cache, if appropriate. */
695 if (target
== '\n' && newline_cache
)
699 while (region_cache_backward
700 (current_buffer
, newline_cache
, start_byte
, &next_change
))
701 start_byte
= next_change
;
702 immediate_quit
= allow_quit
;
704 /* Start should never be at or before end. */
705 if (start_byte
<= ceiling_byte
)
706 start_byte
= ceiling_byte
+ 1;
708 /* Now the text before start is an unknown region, and
709 next_change is the position of the next known region. */
710 ceiling_byte
= max (next_change
, ceiling_byte
);
713 /* Stop scanning before the gap. */
714 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
715 ceiling_byte
= max (tem
, ceiling_byte
);
718 /* The termination address of the dumb loop. */
719 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
720 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
721 unsigned char *base
= cursor
;
723 while (cursor
>= ceiling_addr
)
725 unsigned char *scan_start
= cursor
;
727 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
730 /* If we're looking for newlines, cache the fact that
731 the region from after the cursor to start is free of them. */
732 if (target
== '\n' && newline_cache
)
733 know_region_cache (current_buffer
, newline_cache
,
734 start_byte
+ cursor
- base
,
735 start_byte
+ scan_start
- base
);
737 /* Did we find the target character? */
738 if (cursor
>= ceiling_addr
)
743 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
749 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
755 *shortage
= count
* direction
;
759 /* Search for COUNT instances of a line boundary, which means either a
760 newline or (if selective display enabled) a carriage return.
761 Start at START. If COUNT is negative, search backwards.
763 We report the resulting position by calling TEMP_SET_PT_BOTH.
765 If we find COUNT instances. we position after (always after,
766 even if scanning backwards) the COUNTth match, and return 0.
768 If we don't find COUNT instances before reaching the end of the
769 buffer (or the beginning, if scanning backwards), we return
770 the number of line boundaries left unfound, and position at
771 the limit we bumped up against.
773 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
774 except in special cases. */
777 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
778 int start
, start_byte
;
779 int limit
, limit_byte
;
783 int direction
= ((count
> 0) ? 1 : -1);
785 register unsigned char *cursor
;
788 register int ceiling
;
789 register unsigned char *ceiling_addr
;
791 int old_immediate_quit
= immediate_quit
;
793 /* The code that follows is like scan_buffer
794 but checks for either newline or carriage return. */
799 start_byte
= CHAR_TO_BYTE (start
);
803 while (start_byte
< limit_byte
)
805 ceiling
= BUFFER_CEILING_OF (start_byte
);
806 ceiling
= min (limit_byte
- 1, ceiling
);
807 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
808 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
811 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
814 if (cursor
!= ceiling_addr
)
818 immediate_quit
= old_immediate_quit
;
819 start_byte
= start_byte
+ cursor
- base
+ 1;
820 start
= BYTE_TO_CHAR (start_byte
);
821 TEMP_SET_PT_BOTH (start
, start_byte
);
825 if (++cursor
== ceiling_addr
)
831 start_byte
+= cursor
- base
;
836 while (start_byte
> limit_byte
)
838 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
839 ceiling
= max (limit_byte
, ceiling
);
840 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
841 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
844 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
847 if (cursor
!= ceiling_addr
)
851 immediate_quit
= old_immediate_quit
;
852 /* Return the position AFTER the match we found. */
853 start_byte
= start_byte
+ cursor
- base
+ 1;
854 start
= BYTE_TO_CHAR (start_byte
);
855 TEMP_SET_PT_BOTH (start
, start_byte
);
862 /* Here we add 1 to compensate for the last decrement
863 of CURSOR, which took it past the valid range. */
864 start_byte
+= cursor
- base
+ 1;
868 TEMP_SET_PT_BOTH (limit
, limit_byte
);
869 immediate_quit
= old_immediate_quit
;
871 return count
* direction
;
875 find_next_newline_no_quit (from
, cnt
)
876 register int from
, cnt
;
878 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
881 /* Like find_next_newline, but returns position before the newline,
882 not after, and only search up to TO. This isn't just
883 find_next_newline (...)-1, because you might hit TO. */
886 find_before_next_newline (from
, to
, cnt
)
890 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
898 /* Subroutines of Lisp buffer search functions. */
901 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
902 Lisp_Object string
, bound
, noerror
, count
;
913 CHECK_NUMBER (count
);
917 CHECK_STRING (string
);
921 lim
= ZV
, lim_byte
= ZV_BYTE
;
923 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
927 CHECK_NUMBER_COERCE_MARKER (bound
);
929 if (n
> 0 ? lim
< PT
: lim
> PT
)
930 error ("Invalid search bound (wrong side of point)");
932 lim
= ZV
, lim_byte
= ZV_BYTE
;
934 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
936 lim_byte
= CHAR_TO_BYTE (lim
);
939 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
940 XCHAR_TABLE (current_buffer
->case_canon_table
)->extras
[2]
941 = current_buffer
->case_eqv_table
;
943 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
944 (!NILP (current_buffer
->case_fold_search
)
945 ? current_buffer
->case_canon_table
947 (!NILP (current_buffer
->case_fold_search
)
948 ? current_buffer
->case_eqv_table
954 xsignal1 (Qsearch_failed
, string
);
956 if (!EQ (noerror
, Qt
))
958 if (lim
< BEGV
|| lim
> ZV
)
960 SET_PT_BOTH (lim
, lim_byte
);
962 #if 0 /* This would be clean, but maybe programs depend on
963 a value of nil here. */
971 if (np
< BEGV
|| np
> ZV
)
976 return make_number (np
);
979 /* Return 1 if REGEXP it matches just one constant string. */
982 trivial_regexp_p (regexp
)
985 int len
= SBYTES (regexp
);
986 unsigned char *s
= SDATA (regexp
);
991 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
998 case '|': case '(': case ')': case '`': case '\'': case 'b':
999 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1000 case 'S': case '=': case '{': case '}': case '_':
1001 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1002 case '1': case '2': case '3': case '4': case '5':
1003 case '6': case '7': case '8': case '9':
1011 /* Search for the n'th occurrence of STRING in the current buffer,
1012 starting at position POS and stopping at position LIM,
1013 treating STRING as a literal string if RE is false or as
1014 a regular expression if RE is true.
1016 If N is positive, searching is forward and LIM must be greater than POS.
1017 If N is negative, searching is backward and LIM must be less than POS.
1019 Returns -x if x occurrences remain to be found (x > 0),
1020 or else the position at the beginning of the Nth occurrence
1021 (if searching backward) or the end (if searching forward).
1023 POSIX is nonzero if we want full backtracking (POSIX style)
1024 for this pattern. 0 means backtrack only enough to get a valid match. */
1026 #define TRANSLATE(out, trt, d) \
1032 temp = Faref (trt, make_number (d)); \
1033 if (INTEGERP (temp)) \
1034 out = XINT (temp); \
1044 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
1045 RE
, trt
, inverse_trt
, posix
)
1054 Lisp_Object inverse_trt
;
1057 int len
= SCHARS (string
);
1058 int len_byte
= SBYTES (string
);
1061 if (running_asynch_code
)
1062 save_search_regs ();
1064 /* Searching 0 times means don't move. */
1065 /* Null string is found at starting position. */
1066 if (len
== 0 || n
== 0)
1068 set_search_regs (pos_byte
, 0);
1072 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1074 unsigned char *p1
, *p2
;
1076 struct re_pattern_buffer
*bufp
;
1078 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
,
1079 !NILP (current_buffer
->enable_multibyte_characters
));
1081 immediate_quit
= 1; /* Quit immediately if user types ^G,
1082 because letting this function finish
1083 can take too long. */
1084 QUIT
; /* Do a pending quit right away,
1085 to avoid paradoxical behavior */
1086 /* Get pointers and sizes of the two strings
1087 that make up the visible portion of the buffer. */
1090 s1
= GPT_BYTE
- BEGV_BYTE
;
1092 s2
= ZV_BYTE
- GPT_BYTE
;
1096 s2
= ZV_BYTE
- BEGV_BYTE
;
1101 s1
= ZV_BYTE
- BEGV_BYTE
;
1104 re_match_object
= Qnil
;
1109 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1110 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1112 /* Don't allow match past current point */
1113 pos_byte
- BEGV_BYTE
);
1116 matcher_overflow ();
1120 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1121 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1122 if (search_regs
.start
[i
] >= 0)
1124 search_regs
.start
[i
]
1125 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1127 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1129 XSETBUFFER (last_thing_searched
, current_buffer
);
1130 /* Set pos to the new position. */
1131 pos
= search_regs
.start
[0];
1143 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1144 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1146 lim_byte
- BEGV_BYTE
);
1149 matcher_overflow ();
1153 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1154 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1155 if (search_regs
.start
[i
] >= 0)
1157 search_regs
.start
[i
]
1158 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1160 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1162 XSETBUFFER (last_thing_searched
, current_buffer
);
1163 pos
= search_regs
.end
[0];
1175 else /* non-RE case */
1177 unsigned char *raw_pattern
, *pat
;
1178 int raw_pattern_size
;
1179 int raw_pattern_size_byte
;
1180 unsigned char *patbuf
;
1181 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1182 unsigned char *base_pat
;
1183 /* Set to positive if we find a non-ASCII char that need
1184 translation. Otherwise set to zero later. */
1186 int boyer_moore_ok
= 1;
1188 /* MULTIBYTE says whether the text to be searched is multibyte.
1189 We must convert PATTERN to match that, or we will not really
1190 find things right. */
1192 if (multibyte
== STRING_MULTIBYTE (string
))
1194 raw_pattern
= (unsigned char *) SDATA (string
);
1195 raw_pattern_size
= SCHARS (string
);
1196 raw_pattern_size_byte
= SBYTES (string
);
1200 raw_pattern_size
= SCHARS (string
);
1201 raw_pattern_size_byte
1202 = count_size_as_multibyte (SDATA (string
),
1204 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1205 copy_text (SDATA (string
), raw_pattern
,
1206 SCHARS (string
), 0, 1);
1210 /* Converting multibyte to single-byte.
1212 ??? Perhaps this conversion should be done in a special way
1213 by subtracting nonascii-insert-offset from each non-ASCII char,
1214 so that only the multibyte chars which really correspond to
1215 the chosen single-byte character set can possibly match. */
1216 raw_pattern_size
= SCHARS (string
);
1217 raw_pattern_size_byte
= SCHARS (string
);
1218 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1219 copy_text (SDATA (string
), raw_pattern
,
1220 SBYTES (string
), 1, 0);
1223 /* Copy and optionally translate the pattern. */
1224 len
= raw_pattern_size
;
1225 len_byte
= raw_pattern_size_byte
;
1226 patbuf
= (unsigned char *) alloca (len
* MAX_MULTIBYTE_LENGTH
);
1228 base_pat
= raw_pattern
;
1231 /* Fill patbuf by translated characters in STRING while
1232 checking if we can use boyer-moore search. If TRT is
1233 non-nil, we can use boyer-moore search only if TRT can be
1234 represented by the byte array of 256 elements. For that,
1235 all non-ASCII case-equivalents of all case-senstive
1236 characters in STRING must belong to the same charset and
1241 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1242 int c
, translated
, inverse
;
1243 int in_charlen
, charlen
;
1245 /* If we got here and the RE flag is set, it's because we're
1246 dealing with a regexp known to be trivial, so the backslash
1247 just quotes the next character. */
1248 if (RE
&& *base_pat
== '\\')
1256 c
= STRING_CHAR_AND_LENGTH (base_pat
, len_byte
, in_charlen
);
1261 charlen
= in_charlen
;
1265 /* Translate the character. */
1266 TRANSLATE (translated
, trt
, c
);
1267 charlen
= CHAR_STRING (translated
, str_base
);
1270 /* Check if C has any other case-equivalents. */
1271 TRANSLATE (inverse
, inverse_trt
, c
);
1272 /* If so, check if we can use boyer-moore. */
1273 if (c
!= inverse
&& boyer_moore_ok
)
1275 /* Check if all equivalents belong to the same
1276 group of characters. Note that the check of C
1277 itself is done by the last iteration. */
1278 int this_char_base
= -1;
1280 while (boyer_moore_ok
)
1282 if (ASCII_BYTE_P (inverse
))
1284 if (this_char_base
> 0)
1290 char_base
= this_char_base
;
1293 else if (CHAR_BYTE8_P (inverse
))
1294 /* Boyer-moore search can't handle a
1295 translation of an eight-bit
1298 else if (this_char_base
< 0)
1300 this_char_base
= inverse
& ~0x3F;
1302 char_base
= this_char_base
;
1303 else if (char_base
> 0
1304 && this_char_base
!= char_base
)
1307 else if ((inverse
& ~0x3F) != this_char_base
)
1311 TRANSLATE (inverse
, inverse_trt
, inverse
);
1318 /* Store this character into the translated pattern. */
1319 bcopy (str
, pat
, charlen
);
1321 base_pat
+= in_charlen
;
1322 len_byte
-= in_charlen
;
1327 /* Unibyte buffer. */
1333 /* If we got here and the RE flag is set, it's because we're
1334 dealing with a regexp known to be trivial, so the backslash
1335 just quotes the next character. */
1336 if (RE
&& *base_pat
== '\\')
1343 TRANSLATE (translated
, trt
, c
);
1344 *pat
++ = translated
;
1348 len_byte
= pat
- patbuf
;
1349 len
= raw_pattern_size
;
1350 pat
= base_pat
= patbuf
;
1353 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1354 pos
, pos_byte
, lim
, lim_byte
,
1357 return simple_search (n
, pat
, len
, len_byte
, trt
,
1358 pos
, pos_byte
, lim
, lim_byte
);
1362 /* Do a simple string search N times for the string PAT,
1363 whose length is LEN/LEN_BYTE,
1364 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1365 TRT is the translation table.
1367 Return the character position where the match is found.
1368 Otherwise, if M matches remained to be found, return -M.
1370 This kind of search works regardless of what is in PAT and
1371 regardless of what is in TRT. It is used in cases where
1372 boyer_moore cannot work. */
1375 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1383 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1384 int forward
= n
> 0;
1385 /* Number of buffer bytes matched. Note that this may be different
1386 from len_byte in a multibyte buffer. */
1389 if (lim
> pos
&& multibyte
)
1394 /* Try matching at position POS. */
1396 int this_pos_byte
= pos_byte
;
1398 int this_len_byte
= len_byte
;
1399 unsigned char *p
= pat
;
1400 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1403 while (this_len
> 0)
1405 int charlen
, buf_charlen
;
1408 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1409 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1410 ZV_BYTE
- this_pos_byte
,
1412 TRANSLATE (buf_ch
, trt
, buf_ch
);
1414 if (buf_ch
!= pat_ch
)
1417 this_len_byte
-= charlen
;
1421 this_pos_byte
+= buf_charlen
;
1427 match_byte
= this_pos_byte
- pos_byte
;
1429 pos_byte
+= match_byte
;
1433 INC_BOTH (pos
, pos_byte
);
1443 /* Try matching at position POS. */
1446 unsigned char *p
= pat
;
1448 if (pos
+ len
> lim
)
1451 while (this_len
> 0)
1454 int buf_ch
= FETCH_BYTE (this_pos
);
1455 TRANSLATE (buf_ch
, trt
, buf_ch
);
1457 if (buf_ch
!= pat_ch
)
1476 /* Backwards search. */
1477 else if (lim
< pos
&& multibyte
)
1482 /* Try matching at position POS. */
1483 int this_pos
= pos
- len
;
1486 int this_len_byte
= len_byte
;
1487 unsigned char *p
= pat
;
1489 if (this_pos
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1491 this_pos_byte
= CHAR_TO_BYTE (this_pos
);
1492 match_byte
= pos_byte
- this_pos_byte
;
1494 while (this_len
> 0)
1496 int charlen
, buf_charlen
;
1499 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1500 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1501 ZV_BYTE
- this_pos_byte
,
1503 TRANSLATE (buf_ch
, trt
, buf_ch
);
1505 if (buf_ch
!= pat_ch
)
1508 this_len_byte
-= charlen
;
1511 this_pos_byte
+= buf_charlen
;
1518 pos_byte
-= match_byte
;
1522 DEC_BOTH (pos
, pos_byte
);
1532 /* Try matching at position POS. */
1533 int this_pos
= pos
- len
;
1535 unsigned char *p
= pat
;
1540 while (this_len
> 0)
1543 int buf_ch
= FETCH_BYTE (this_pos
);
1544 TRANSLATE (buf_ch
, trt
, buf_ch
);
1546 if (buf_ch
!= pat_ch
)
1569 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1571 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1581 /* Do Boyer-Moore search N times for the string BASE_PAT,
1582 whose length is LEN/LEN_BYTE,
1583 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1584 DIRECTION says which direction we search in.
1585 TRT and INVERSE_TRT are translation tables.
1586 Characters in PAT are already translated by TRT.
1588 This kind of search works if all the characters in BASE_PAT that
1589 have nontrivial translation are the same aside from the last byte.
1590 This makes it possible to translate just the last byte of a
1591 character, and do so after just a simple test of the context.
1592 CHAR_BASE is nonzero iff there is such a non-ASCII character.
1594 If that criterion is not satisfied, do not call this function. */
1597 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1598 pos
, pos_byte
, lim
, lim_byte
, char_base
)
1600 unsigned char *base_pat
;
1603 Lisp_Object inverse_trt
;
1608 int direction
= ((n
> 0) ? 1 : -1);
1609 register int dirlen
;
1610 int infinity
, limit
, stride_for_teases
= 0;
1611 register int *BM_tab
;
1613 register unsigned char *cursor
, *p_limit
;
1615 unsigned char *pat
, *pat_end
;
1616 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1618 unsigned char simple_translate
[0400];
1619 /* These are set to the preceding bytes of a byte to be translated
1620 if char_base is nonzero. As the maximum byte length of a
1621 multibyte character is 5, we have to check at most four previous
1623 int translate_prev_byte1
= 0;
1624 int translate_prev_byte2
= 0;
1625 int translate_prev_byte3
= 0;
1626 int translate_prev_byte4
= 0;
1629 int BM_tab_space
[0400];
1630 BM_tab
= &BM_tab_space
[0];
1632 BM_tab
= (int *) alloca (0400 * sizeof (int));
1634 /* The general approach is that we are going to maintain that we know */
1635 /* the first (closest to the present position, in whatever direction */
1636 /* we're searching) character that could possibly be the last */
1637 /* (furthest from present position) character of a valid match. We */
1638 /* advance the state of our knowledge by looking at that character */
1639 /* and seeing whether it indeed matches the last character of the */
1640 /* pattern. If it does, we take a closer look. If it does not, we */
1641 /* move our pointer (to putative last characters) as far as is */
1642 /* logically possible. This amount of movement, which I call a */
1643 /* stride, will be the length of the pattern if the actual character */
1644 /* appears nowhere in the pattern, otherwise it will be the distance */
1645 /* from the last occurrence of that character to the end of the */
1647 /* As a coding trick, an enormous stride is coded into the table for */
1648 /* characters that match the last character. This allows use of only */
1649 /* a single test, a test for having gone past the end of the */
1650 /* permissible match region, to test for both possible matches (when */
1651 /* the stride goes past the end immediately) and failure to */
1652 /* match (where you get nudged past the end one stride at a time). */
1654 /* Here we make a "mickey mouse" BM table. The stride of the search */
1655 /* is determined only by the last character of the putative match. */
1656 /* If that character does not match, we will stride the proper */
1657 /* distance to propose a match that superimposes it on the last */
1658 /* instance of a character that matches it (per trt), or misses */
1659 /* it entirely if there is none. */
1661 dirlen
= len_byte
* direction
;
1662 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1664 /* Record position after the end of the pattern. */
1665 pat_end
= base_pat
+ len_byte
;
1666 /* BASE_PAT points to a character that we start scanning from.
1667 It is the first character in a forward search,
1668 the last character in a backward search. */
1670 base_pat
= pat_end
- 1;
1672 BM_tab_base
= BM_tab
;
1674 j
= dirlen
; /* to get it in a register */
1675 /* A character that does not appear in the pattern induces a */
1676 /* stride equal to the pattern length. */
1677 while (BM_tab_base
!= BM_tab
)
1685 /* We use this for translation, instead of TRT itself.
1686 We fill this in to handle the characters that actually
1687 occur in the pattern. Others don't matter anyway! */
1688 bzero (simple_translate
, sizeof simple_translate
);
1689 for (i
= 0; i
< 0400; i
++)
1690 simple_translate
[i
] = i
;
1694 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1695 byte following them are the target of translation. */
1696 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1697 int len
= CHAR_STRING (char_base
, str
);
1699 translate_prev_byte1
= str
[len
- 2];
1702 translate_prev_byte2
= str
[len
- 3];
1705 translate_prev_byte3
= str
[len
- 4];
1707 translate_prev_byte4
= str
[len
- 5];
1713 while (i
!= infinity
)
1715 unsigned char *ptr
= base_pat
+ i
;
1721 /* If the byte currently looking at is the last of a
1722 character to check case-equivalents, set CH to that
1723 character. An ASCII character and a non-ASCII character
1724 matching with CHAR_BASE are to be checked. */
1727 if (ASCII_BYTE_P (*ptr
) || ! multibyte
)
1730 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1732 unsigned char *charstart
= ptr
- 1;
1734 while (! (CHAR_HEAD_P (*charstart
)))
1736 ch
= STRING_CHAR (charstart
, ptr
- charstart
+ 1);
1737 if (char_base
!= (ch
& ~0x3F))
1742 j
= (ch
& 0x3F) | 0200;
1747 stride_for_teases
= BM_tab
[j
];
1749 BM_tab
[j
] = dirlen
- i
;
1750 /* A translation table is accompanied by its inverse -- see */
1751 /* comment following downcase_table for details */
1754 int starting_ch
= ch
;
1759 TRANSLATE (ch
, inverse_trt
, ch
);
1761 j
= (ch
& 0x3F) | 0200;
1765 /* For all the characters that map into CH,
1766 set up simple_translate to map the last byte
1768 simple_translate
[j
] = starting_j
;
1769 if (ch
== starting_ch
)
1771 BM_tab
[j
] = dirlen
- i
;
1780 stride_for_teases
= BM_tab
[j
];
1781 BM_tab
[j
] = dirlen
- i
;
1783 /* stride_for_teases tells how much to stride if we get a */
1784 /* match on the far character but are subsequently */
1785 /* disappointed, by recording what the stride would have been */
1786 /* for that character if the last character had been */
1789 infinity
= dirlen
- infinity
;
1790 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1791 /* loop invariant - POS_BYTE points at where last char (first
1792 char if reverse) of pattern would align in a possible match. */
1796 unsigned char *tail_end_ptr
;
1798 /* It's been reported that some (broken) compiler thinks that
1799 Boolean expressions in an arithmetic context are unsigned.
1800 Using an explicit ?1:0 prevents this. */
1801 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1803 return (n
* (0 - direction
));
1804 /* First we do the part we can by pointers (maybe nothing) */
1807 limit
= pos_byte
- dirlen
+ direction
;
1810 limit
= BUFFER_CEILING_OF (limit
);
1811 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1812 can take on without hitting edge of buffer or the gap. */
1813 limit
= min (limit
, pos_byte
+ 20000);
1814 limit
= min (limit
, lim_byte
- 1);
1818 limit
= BUFFER_FLOOR_OF (limit
);
1819 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1820 can take on without hitting edge of buffer or the gap. */
1821 limit
= max (limit
, pos_byte
- 20000);
1822 limit
= max (limit
, lim_byte
);
1824 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1825 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1827 if ((limit
- pos_byte
) * direction
> 20)
1831 p_limit
= BYTE_POS_ADDR (limit
);
1832 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1833 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1834 while (1) /* use one cursor setting as long as i can */
1836 if (direction
> 0) /* worth duplicating */
1838 /* Use signed comparison if appropriate
1839 to make cursor+infinity sure to be > p_limit.
1840 Assuming that the buffer lies in a range of addresses
1841 that are all "positive" (as ints) or all "negative",
1842 either kind of comparison will work as long
1843 as we don't step by infinity. So pick the kind
1844 that works when we do step by infinity. */
1845 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1846 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1847 cursor
+= BM_tab
[*cursor
];
1849 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1850 cursor
+= BM_tab
[*cursor
];
1854 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1855 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1856 cursor
+= BM_tab
[*cursor
];
1858 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1859 cursor
+= BM_tab
[*cursor
];
1861 /* If you are here, cursor is beyond the end of the searched region. */
1862 /* This can happen if you match on the far character of the pattern, */
1863 /* because the "stride" of that character is infinity, a number able */
1864 /* to throw you well beyond the end of the search. It can also */
1865 /* happen if you fail to match within the permitted region and would */
1866 /* otherwise try a character beyond that region */
1867 if ((cursor
- p_limit
) * direction
<= len_byte
)
1868 break; /* a small overrun is genuine */
1869 cursor
-= infinity
; /* large overrun = hit */
1870 i
= dirlen
- direction
;
1873 while ((i
-= direction
) + direction
!= 0)
1876 cursor
-= direction
;
1877 /* Translate only the last byte of a character. */
1879 || ((cursor
== tail_end_ptr
1880 || CHAR_HEAD_P (cursor
[1]))
1881 && (CHAR_HEAD_P (cursor
[0])
1882 /* Check if this is the last byte of
1883 a translable character. */
1884 || (translate_prev_byte1
== cursor
[-1]
1885 && (CHAR_HEAD_P (translate_prev_byte1
)
1886 || (translate_prev_byte2
== cursor
[-2]
1887 && (CHAR_HEAD_P (translate_prev_byte2
)
1888 || (translate_prev_byte3
== cursor
[-3]))))))))
1889 ch
= simple_translate
[*cursor
];
1898 while ((i
-= direction
) + direction
!= 0)
1900 cursor
-= direction
;
1901 if (pat
[i
] != *cursor
)
1905 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1906 if (i
+ direction
== 0)
1910 cursor
-= direction
;
1912 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1913 ? 1 - len_byte
: 0);
1914 set_search_regs (position
, len_byte
);
1916 if ((n
-= direction
) != 0)
1917 cursor
+= dirlen
; /* to resume search */
1919 return ((direction
> 0)
1920 ? search_regs
.end
[0] : search_regs
.start
[0]);
1923 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1925 pos_byte
+= cursor
- p2
;
1928 /* Now we'll pick up a clump that has to be done the hard */
1929 /* way because it covers a discontinuity */
1931 limit
= ((direction
> 0)
1932 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1933 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1934 limit
= ((direction
> 0)
1935 ? min (limit
+ len_byte
, lim_byte
- 1)
1936 : max (limit
- len_byte
, lim_byte
));
1937 /* LIMIT is now the last value POS_BYTE can have
1938 and still be valid for a possible match. */
1941 /* This loop can be coded for space rather than */
1942 /* speed because it will usually run only once. */
1943 /* (the reach is at most len + 21, and typically */
1944 /* does not exceed len) */
1945 while ((limit
- pos_byte
) * direction
>= 0)
1946 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
1947 /* now run the same tests to distinguish going off the */
1948 /* end, a match or a phony match. */
1949 if ((pos_byte
- limit
) * direction
<= len_byte
)
1950 break; /* ran off the end */
1951 /* Found what might be a match.
1952 Set POS_BYTE back to last (first if reverse) pos. */
1953 pos_byte
-= infinity
;
1954 i
= dirlen
- direction
;
1955 while ((i
-= direction
) + direction
!= 0)
1959 pos_byte
-= direction
;
1960 ptr
= BYTE_POS_ADDR (pos_byte
);
1961 /* Translate only the last byte of a character. */
1963 || ((ptr
== tail_end_ptr
1964 || CHAR_HEAD_P (ptr
[1]))
1965 && (CHAR_HEAD_P (ptr
[0])
1966 /* Check if this is the last byte of a
1967 translable character. */
1968 || (translate_prev_byte1
== ptr
[-1]
1969 && (CHAR_HEAD_P (translate_prev_byte1
)
1970 || (translate_prev_byte2
== ptr
[-2]
1971 && (CHAR_HEAD_P (translate_prev_byte2
)
1972 || translate_prev_byte3
== ptr
[-3])))))))
1973 ch
= simple_translate
[*ptr
];
1979 /* Above loop has moved POS_BYTE part or all the way
1980 back to the first pos (last pos if reverse).
1981 Set it once again at the last (first if reverse) char. */
1982 pos_byte
+= dirlen
- i
- direction
;
1983 if (i
+ direction
== 0)
1986 pos_byte
-= direction
;
1988 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
1990 set_search_regs (position
, len_byte
);
1992 if ((n
-= direction
) != 0)
1993 pos_byte
+= dirlen
; /* to resume search */
1995 return ((direction
> 0)
1996 ? search_regs
.end
[0] : search_regs
.start
[0]);
1999 pos_byte
+= stride_for_teases
;
2002 /* We have done one clump. Can we continue? */
2003 if ((lim_byte
- pos_byte
) * direction
< 0)
2004 return ((0 - n
) * direction
);
2006 return BYTE_TO_CHAR (pos_byte
);
2009 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2010 for the overall match just found in the current buffer.
2011 Also clear out the match data for registers 1 and up. */
2014 set_search_regs (beg_byte
, nbytes
)
2015 int beg_byte
, nbytes
;
2019 /* Make sure we have registers in which to store
2020 the match position. */
2021 if (search_regs
.num_regs
== 0)
2023 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2024 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
2025 search_regs
.num_regs
= 2;
2028 /* Clear out the other registers. */
2029 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2031 search_regs
.start
[i
] = -1;
2032 search_regs
.end
[i
] = -1;
2035 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2036 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2037 XSETBUFFER (last_thing_searched
, current_buffer
);
2040 /* Given a string of words separated by word delimiters,
2041 compute a regexp that matches those exact words
2042 separated by arbitrary punctuation. */
2048 register unsigned char *p
, *o
;
2049 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
2054 CHECK_STRING (string
);
2056 len
= SCHARS (string
);
2058 for (i
= 0, i_byte
= 0; i
< len
; )
2062 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
2064 if (SYNTAX (c
) != Sword
)
2067 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
2074 if (SYNTAX (prev_c
) == Sword
)
2077 return empty_string
;
2079 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
2080 if (STRING_MULTIBYTE (string
))
2081 val
= make_uninit_multibyte_string (len
+ adjust
,
2085 val
= make_uninit_string (len
+ adjust
);
2092 for (i
= 0, i_byte
= 0; i
< len
; )
2095 int i_byte_orig
= i_byte
;
2097 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
2099 if (SYNTAX (c
) == Sword
)
2101 bcopy (SDATA (string
) + i_byte_orig
, o
,
2102 i_byte
- i_byte_orig
);
2103 o
+= i_byte
- i_byte_orig
;
2105 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
2123 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2124 "MSearch backward: ",
2125 doc
: /* Search backward from point for STRING.
2126 Set point to the beginning of the occurrence found, and return point.
2127 An optional second argument bounds the search; it is a buffer position.
2128 The match found must not extend before that position.
2129 Optional third argument, if t, means if fail just return nil (no error).
2130 If not nil and not t, position at limit of search and return nil.
2131 Optional fourth argument is repeat count--search for successive occurrences.
2133 Search case-sensitivity is determined by the value of the variable
2134 `case-fold-search', which see.
2136 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2137 (string
, bound
, noerror
, count
)
2138 Lisp_Object string
, bound
, noerror
, count
;
2140 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2143 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2144 doc
: /* Search forward from point for STRING.
2145 Set point to the end of the occurrence found, and return point.
2146 An optional second argument bounds the search; it is a buffer position.
2147 The match found must not extend after that position. A value of nil is
2148 equivalent to (point-max).
2149 Optional third argument, if t, means if fail just return nil (no error).
2150 If not nil and not t, move to limit of search and return nil.
2151 Optional fourth argument is repeat count--search for successive occurrences.
2153 Search case-sensitivity is determined by the value of the variable
2154 `case-fold-search', which see.
2156 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2157 (string
, bound
, noerror
, count
)
2158 Lisp_Object string
, bound
, noerror
, count
;
2160 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2163 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2164 "sWord search backward: ",
2165 doc
: /* Search backward from point for STRING, ignoring differences in punctuation.
2166 Set point to the beginning of the occurrence found, and return point.
2167 An optional second argument bounds the search; it is a buffer position.
2168 The match found must not extend before that position.
2169 Optional third argument, if t, means if fail just return nil (no error).
2170 If not nil and not t, move to limit of search and return nil.
2171 Optional fourth argument is repeat count--search for successive occurrences. */)
2172 (string
, bound
, noerror
, count
)
2173 Lisp_Object string
, bound
, noerror
, count
;
2175 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
2178 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2180 doc
: /* Search forward from point for STRING, ignoring differences in punctuation.
2181 Set point to the end of the occurrence found, and return point.
2182 An optional second argument bounds the search; it is a buffer position.
2183 The match found must not extend after that position.
2184 Optional third argument, if t, means if fail just return nil (no error).
2185 If not nil and not t, move to limit of search and return nil.
2186 Optional fourth argument is repeat count--search for successive occurrences. */)
2187 (string
, bound
, noerror
, count
)
2188 Lisp_Object string
, bound
, noerror
, count
;
2190 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
2193 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2194 "sRE search backward: ",
2195 doc
: /* Search backward from point for match for regular expression REGEXP.
2196 Set point to the beginning of the match, and return point.
2197 The match found is the one starting last in the buffer
2198 and yet ending before the origin of the search.
2199 An optional second argument bounds the search; it is a buffer position.
2200 The match found must start at or after that position.
2201 Optional third argument, if t, means if fail just return nil (no error).
2202 If not nil and not t, move to limit of search and return nil.
2203 Optional fourth argument is repeat count--search for successive occurrences.
2204 See also the functions `match-beginning', `match-end', `match-string',
2205 and `replace-match'. */)
2206 (regexp
, bound
, noerror
, count
)
2207 Lisp_Object regexp
, bound
, noerror
, count
;
2209 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2212 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2214 doc
: /* Search forward from point for regular expression REGEXP.
2215 Set point to the end of the occurrence found, and return point.
2216 An optional second argument bounds the search; it is a buffer position.
2217 The match found must not extend after that position.
2218 Optional third argument, if t, means if fail just return nil (no error).
2219 If not nil and not t, move to limit of search and return nil.
2220 Optional fourth argument is repeat count--search for successive occurrences.
2221 See also the functions `match-beginning', `match-end', `match-string',
2222 and `replace-match'. */)
2223 (regexp
, bound
, noerror
, count
)
2224 Lisp_Object regexp
, bound
, noerror
, count
;
2226 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2229 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2230 "sPosix search backward: ",
2231 doc
: /* Search backward from point for match for regular expression REGEXP.
2232 Find the longest match in accord with Posix regular expression rules.
2233 Set point to the beginning of the match, and return point.
2234 The match found is the one starting last in the buffer
2235 and yet ending before the origin of the search.
2236 An optional second argument bounds the search; it is a buffer position.
2237 The match found must start at or after that position.
2238 Optional third argument, if t, means if fail just return nil (no error).
2239 If not nil and not t, move to limit of search and return nil.
2240 Optional fourth argument is repeat count--search for successive occurrences.
2241 See also the functions `match-beginning', `match-end', `match-string',
2242 and `replace-match'. */)
2243 (regexp
, bound
, noerror
, count
)
2244 Lisp_Object regexp
, bound
, noerror
, count
;
2246 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2249 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2251 doc
: /* Search forward from point for regular expression REGEXP.
2252 Find the longest match in accord with Posix regular expression rules.
2253 Set point to the end of the occurrence found, and return point.
2254 An optional second argument bounds the search; it is a buffer position.
2255 The match found must not extend after that position.
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.
2259 See also the functions `match-beginning', `match-end', `match-string',
2260 and `replace-match'. */)
2261 (regexp
, bound
, noerror
, count
)
2262 Lisp_Object regexp
, bound
, noerror
, count
;
2264 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2267 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2268 doc
: /* Replace text matched by last search with NEWTEXT.
2269 Leave point at the end of the replacement text.
2271 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2272 Otherwise maybe capitalize the whole text, or maybe just word initials,
2273 based on the replaced text.
2274 If the replaced text has only capital letters
2275 and has at least one multiletter word, convert NEWTEXT to all caps.
2276 Otherwise if all words are capitalized in the replaced text,
2277 capitalize each word in NEWTEXT.
2279 If third arg LITERAL is non-nil, insert NEWTEXT literally.
2280 Otherwise treat `\\' as special:
2281 `\\&' in NEWTEXT means substitute original matched text.
2282 `\\N' means substitute what matched the Nth `\\(...\\)'.
2283 If Nth parens didn't match, substitute nothing.
2284 `\\\\' means insert one `\\'.
2285 Case conversion does not apply to these substitutions.
2287 FIXEDCASE and LITERAL are optional arguments.
2289 The optional fourth argument STRING can be a string to modify.
2290 This is meaningful when the previous match was done against STRING,
2291 using `string-match'. When used this way, `replace-match'
2292 creates and returns a new string made by copying STRING and replacing
2293 the part of STRING that was matched.
2295 The optional fifth argument SUBEXP specifies a subexpression;
2296 it says to replace just that subexpression with NEWTEXT,
2297 rather than replacing the entire matched text.
2298 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2299 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2300 NEWTEXT in place of subexp N.
2301 This is useful only after a regular expression search or match,
2302 since only regular expressions have distinguished subexpressions. */)
2303 (newtext
, fixedcase
, literal
, string
, subexp
)
2304 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2306 enum { nochange
, all_caps
, cap_initial
} case_action
;
2307 register int pos
, pos_byte
;
2308 int some_multiletter_word
;
2311 int some_nonuppercase_initial
;
2312 register int c
, prevc
;
2314 int opoint
, newpoint
;
2316 CHECK_STRING (newtext
);
2318 if (! NILP (string
))
2319 CHECK_STRING (string
);
2321 case_action
= nochange
; /* We tried an initialization */
2322 /* but some C compilers blew it */
2324 if (search_regs
.num_regs
<= 0)
2325 error ("`replace-match' called before any match found");
2331 CHECK_NUMBER (subexp
);
2332 sub
= XINT (subexp
);
2333 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2334 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2339 if (search_regs
.start
[sub
] < BEGV
2340 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2341 || search_regs
.end
[sub
] > ZV
)
2342 args_out_of_range (make_number (search_regs
.start
[sub
]),
2343 make_number (search_regs
.end
[sub
]));
2347 if (search_regs
.start
[sub
] < 0
2348 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2349 || search_regs
.end
[sub
] > SCHARS (string
))
2350 args_out_of_range (make_number (search_regs
.start
[sub
]),
2351 make_number (search_regs
.end
[sub
]));
2354 if (NILP (fixedcase
))
2356 /* Decide how to casify by examining the matched text. */
2359 pos
= search_regs
.start
[sub
];
2360 last
= search_regs
.end
[sub
];
2363 pos_byte
= CHAR_TO_BYTE (pos
);
2365 pos_byte
= string_char_to_byte (string
, pos
);
2368 case_action
= all_caps
;
2370 /* some_multiletter_word is set nonzero if any original word
2371 is more than one letter long. */
2372 some_multiletter_word
= 0;
2374 some_nonuppercase_initial
= 0;
2381 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2382 INC_BOTH (pos
, pos_byte
);
2385 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2389 /* Cannot be all caps if any original char is lower case */
2392 if (SYNTAX (prevc
) != Sword
)
2393 some_nonuppercase_initial
= 1;
2395 some_multiletter_word
= 1;
2397 else if (UPPERCASEP (c
))
2400 if (SYNTAX (prevc
) != Sword
)
2403 some_multiletter_word
= 1;
2407 /* If the initial is a caseless word constituent,
2408 treat that like a lowercase initial. */
2409 if (SYNTAX (prevc
) != Sword
)
2410 some_nonuppercase_initial
= 1;
2416 /* Convert to all caps if the old text is all caps
2417 and has at least one multiletter word. */
2418 if (! some_lowercase
&& some_multiletter_word
)
2419 case_action
= all_caps
;
2420 /* Capitalize each word, if the old text has all capitalized words. */
2421 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2422 case_action
= cap_initial
;
2423 else if (!some_nonuppercase_initial
&& some_uppercase
)
2424 /* Should x -> yz, operating on X, give Yz or YZ?
2425 We'll assume the latter. */
2426 case_action
= all_caps
;
2428 case_action
= nochange
;
2431 /* Do replacement in a string. */
2434 Lisp_Object before
, after
;
2436 before
= Fsubstring (string
, make_number (0),
2437 make_number (search_regs
.start
[sub
]));
2438 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2440 /* Substitute parts of the match into NEWTEXT
2445 int lastpos_byte
= 0;
2446 /* We build up the substituted string in ACCUM. */
2449 int length
= SBYTES (newtext
);
2453 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2457 int delbackslash
= 0;
2459 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2463 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2467 substart
= search_regs
.start
[sub
];
2468 subend
= search_regs
.end
[sub
];
2470 else if (c
>= '1' && c
<= '9')
2472 if (search_regs
.start
[c
- '0'] >= 0
2473 && c
<= search_regs
.num_regs
+ '0')
2475 substart
= search_regs
.start
[c
- '0'];
2476 subend
= search_regs
.end
[c
- '0'];
2480 /* If that subexp did not match,
2481 replace \\N with nothing. */
2489 error ("Invalid use of `\\' in replacement text");
2493 if (pos
- 2 != lastpos
)
2494 middle
= substring_both (newtext
, lastpos
,
2496 pos
- 2, pos_byte
- 2);
2499 accum
= concat3 (accum
, middle
,
2501 make_number (substart
),
2502 make_number (subend
)));
2504 lastpos_byte
= pos_byte
;
2506 else if (delbackslash
)
2508 middle
= substring_both (newtext
, lastpos
,
2510 pos
- 1, pos_byte
- 1);
2512 accum
= concat2 (accum
, middle
);
2514 lastpos_byte
= pos_byte
;
2519 middle
= substring_both (newtext
, lastpos
,
2525 newtext
= concat2 (accum
, middle
);
2528 /* Do case substitution in NEWTEXT if desired. */
2529 if (case_action
== all_caps
)
2530 newtext
= Fupcase (newtext
);
2531 else if (case_action
== cap_initial
)
2532 newtext
= Fupcase_initials (newtext
);
2534 return concat3 (before
, newtext
, after
);
2537 /* Record point, then move (quietly) to the start of the match. */
2538 if (PT
>= search_regs
.end
[sub
])
2540 else if (PT
> search_regs
.start
[sub
])
2541 opoint
= search_regs
.end
[sub
] - ZV
;
2545 /* If we want non-literal replacement,
2546 perform substitution on the replacement string. */
2549 int length
= SBYTES (newtext
);
2550 unsigned char *substed
;
2551 int substed_alloc_size
, substed_len
;
2552 int buf_multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
2553 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2554 Lisp_Object rev_tbl
;
2555 int really_changed
= 0;
2559 substed_alloc_size
= length
* 2 + 100;
2560 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2563 /* Go thru NEWTEXT, producing the actual text to insert in
2564 SUBSTED while adjusting multibyteness to that of the current
2567 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2569 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2570 unsigned char *add_stuff
= NULL
;
2576 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2578 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2582 /* Note that we don't have to increment POS. */
2583 c
= SREF (newtext
, pos_byte
++);
2585 c
= unibyte_char_to_multibyte (c
);
2588 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2589 or set IDX to a match index, which means put that part
2590 of the buffer text into SUBSTED. */
2598 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2600 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2601 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2605 c
= SREF (newtext
, pos_byte
++);
2607 c
= unibyte_char_to_multibyte (c
);
2612 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2614 if (search_regs
.start
[c
- '0'] >= 1)
2618 add_len
= 1, add_stuff
= "\\";
2622 error ("Invalid use of `\\' in replacement text");
2627 add_len
= CHAR_STRING (c
, str
);
2631 /* If we want to copy part of a previous match,
2632 set up ADD_STUFF and ADD_LEN to point to it. */
2635 int begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2636 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2637 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2638 move_gap (search_regs
.start
[idx
]);
2639 add_stuff
= BYTE_POS_ADDR (begbyte
);
2642 /* Now the stuff we want to add to SUBSTED
2643 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2645 /* Make sure SUBSTED is big enough. */
2646 if (substed_len
+ add_len
>= substed_alloc_size
)
2648 substed_alloc_size
= substed_len
+ add_len
+ 500;
2649 substed
= (unsigned char *) xrealloc (substed
,
2650 substed_alloc_size
+ 1);
2653 /* Now add to the end of SUBSTED. */
2656 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2657 substed_len
+= add_len
;
2665 int nchars
= multibyte_chars_in_text (substed
, substed_len
);
2667 newtext
= make_multibyte_string (substed
, nchars
, substed_len
);
2670 newtext
= make_unibyte_string (substed
, substed_len
);
2675 /* Replace the old text with the new in the cleanest possible way. */
2676 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2678 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2680 if (case_action
== all_caps
)
2681 Fupcase_region (make_number (search_regs
.start
[sub
]),
2682 make_number (newpoint
));
2683 else if (case_action
== cap_initial
)
2684 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2685 make_number (newpoint
));
2687 /* Adjust search data for this change. */
2689 int oldend
= search_regs
.end
[sub
];
2690 int oldstart
= search_regs
.start
[sub
];
2691 int change
= newpoint
- search_regs
.end
[sub
];
2694 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2696 if (search_regs
.start
[i
] >= oldend
)
2697 search_regs
.start
[i
] += change
;
2698 else if (search_regs
.start
[i
] > oldstart
)
2699 search_regs
.start
[i
] = oldstart
;
2700 if (search_regs
.end
[i
] >= oldend
)
2701 search_regs
.end
[i
] += change
;
2702 else if (search_regs
.end
[i
] > oldstart
)
2703 search_regs
.end
[i
] = oldstart
;
2707 /* Put point back where it was in the text. */
2709 TEMP_SET_PT (opoint
+ ZV
);
2711 TEMP_SET_PT (opoint
);
2713 /* Now move point "officially" to the start of the inserted replacement. */
2714 move_if_not_intangible (newpoint
);
2720 match_limit (num
, beginningp
)
2729 args_out_of_range (num
, make_number (0));
2730 if (search_regs
.num_regs
<= 0)
2731 error ("No match data, because no search succeeded");
2732 if (n
>= search_regs
.num_regs
2733 || search_regs
.start
[n
] < 0)
2735 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2736 : search_regs
.end
[n
]));
2739 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2740 doc
: /* Return position of start of text matched by last search.
2741 SUBEXP, a number, specifies which parenthesized expression in the last
2743 Value is nil if SUBEXPth pair didn't match, or there were less than
2745 Zero means the entire text matched by the whole regexp or whole string. */)
2749 return match_limit (subexp
, 1);
2752 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2753 doc
: /* Return position of end of text matched by last search.
2754 SUBEXP, a number, specifies which parenthesized expression in the last
2756 Value is nil if SUBEXPth pair didn't match, or there were less than
2758 Zero means the entire text matched by the whole regexp or whole string. */)
2762 return match_limit (subexp
, 0);
2765 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2766 doc
: /* Return a list containing all info on what the last search matched.
2767 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2768 All the elements are markers or nil (nil if the Nth pair didn't match)
2769 if the last match was on a buffer; integers or nil if a string was matched.
2770 Use `store-match-data' to reinstate the data in this list.
2772 If INTEGERS (the optional first argument) is non-nil, always use
2773 integers \(rather than markers) to represent buffer positions. In
2774 this case, and if the last match was in a buffer, the buffer will get
2775 stored as one additional element at the end of the list.
2777 If REUSE is a list, reuse it as part of the value. If REUSE is long
2778 enough to hold all the values, and if INTEGERS is non-nil, no consing
2781 If optional third arg RESEAT is non-nil, any previous markers on the
2782 REUSE list will be modified to point to nowhere.
2784 Return value is undefined if the last search failed. */)
2785 (integers
, reuse
, reseat
)
2786 Lisp_Object integers
, reuse
, reseat
;
2788 Lisp_Object tail
, prev
;
2793 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2794 if (MARKERP (XCAR (tail
)))
2796 unchain_marker (XMARKER (XCAR (tail
)));
2797 XSETCAR (tail
, Qnil
);
2800 if (NILP (last_thing_searched
))
2805 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
+ 1)
2806 * sizeof (Lisp_Object
));
2809 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2811 int start
= search_regs
.start
[i
];
2814 if (EQ (last_thing_searched
, Qt
)
2815 || ! NILP (integers
))
2817 XSETFASTINT (data
[2 * i
], start
);
2818 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2820 else if (BUFFERP (last_thing_searched
))
2822 data
[2 * i
] = Fmake_marker ();
2823 Fset_marker (data
[2 * i
],
2824 make_number (start
),
2825 last_thing_searched
);
2826 data
[2 * i
+ 1] = Fmake_marker ();
2827 Fset_marker (data
[2 * i
+ 1],
2828 make_number (search_regs
.end
[i
]),
2829 last_thing_searched
);
2832 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2838 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2841 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2843 data
[len
] = last_thing_searched
;
2847 /* If REUSE is not usable, cons up the values and return them. */
2848 if (! CONSP (reuse
))
2849 return Flist (len
, data
);
2851 /* If REUSE is a list, store as many value elements as will fit
2852 into the elements of REUSE. */
2853 for (i
= 0, tail
= reuse
; CONSP (tail
);
2854 i
++, tail
= XCDR (tail
))
2857 XSETCAR (tail
, data
[i
]);
2859 XSETCAR (tail
, Qnil
);
2863 /* If we couldn't fit all value elements into REUSE,
2864 cons up the rest of them and add them to the end of REUSE. */
2866 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2871 /* Internal usage only:
2872 If RESEAT is `evaporate', put the markers back on the free list
2873 immediately. No other references to the markers must exist in this case,
2874 so it is used only internally on the unwind stack and save-match-data from
2877 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2878 doc
: /* Set internal data on last search match from elements of LIST.
2879 LIST should have been created by calling `match-data' previously.
2881 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2883 register Lisp_Object list
, reseat
;
2886 register Lisp_Object marker
;
2888 if (running_asynch_code
)
2889 save_search_regs ();
2893 /* Unless we find a marker with a buffer or an explicit buffer
2894 in LIST, assume that this match data came from a string. */
2895 last_thing_searched
= Qt
;
2897 /* Allocate registers if they don't already exist. */
2899 int length
= XFASTINT (Flength (list
)) / 2;
2901 if (length
> search_regs
.num_regs
)
2903 if (search_regs
.num_regs
== 0)
2906 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2908 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2913 = (regoff_t
*) xrealloc (search_regs
.start
,
2914 length
* sizeof (regoff_t
));
2916 = (regoff_t
*) xrealloc (search_regs
.end
,
2917 length
* sizeof (regoff_t
));
2920 for (i
= search_regs
.num_regs
; i
< length
; i
++)
2921 search_regs
.start
[i
] = -1;
2923 search_regs
.num_regs
= length
;
2926 for (i
= 0; CONSP (list
); i
++)
2928 marker
= XCAR (list
);
2929 if (BUFFERP (marker
))
2931 last_thing_searched
= marker
;
2938 search_regs
.start
[i
] = -1;
2947 if (MARKERP (marker
))
2949 if (XMARKER (marker
)->buffer
== 0)
2950 XSETFASTINT (marker
, 0);
2952 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2955 CHECK_NUMBER_COERCE_MARKER (marker
);
2956 from
= XINT (marker
);
2958 if (!NILP (reseat
) && MARKERP (m
))
2960 if (EQ (reseat
, Qevaporate
))
2963 unchain_marker (XMARKER (m
));
2964 XSETCAR (list
, Qnil
);
2967 if ((list
= XCDR (list
), !CONSP (list
)))
2970 m
= marker
= XCAR (list
);
2972 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2973 XSETFASTINT (marker
, 0);
2975 CHECK_NUMBER_COERCE_MARKER (marker
);
2976 search_regs
.start
[i
] = from
;
2977 search_regs
.end
[i
] = XINT (marker
);
2979 if (!NILP (reseat
) && MARKERP (m
))
2981 if (EQ (reseat
, Qevaporate
))
2984 unchain_marker (XMARKER (m
));
2985 XSETCAR (list
, Qnil
);
2991 for (; i
< search_regs
.num_regs
; i
++)
2992 search_regs
.start
[i
] = -1;
2998 /* If non-zero the match data have been saved in saved_search_regs
2999 during the execution of a sentinel or filter. */
3000 static int search_regs_saved
;
3001 static struct re_registers saved_search_regs
;
3002 static Lisp_Object saved_last_thing_searched
;
3004 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3005 if asynchronous code (filter or sentinel) is running. */
3009 if (!search_regs_saved
)
3011 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3012 saved_search_regs
.start
= search_regs
.start
;
3013 saved_search_regs
.end
= search_regs
.end
;
3014 saved_last_thing_searched
= last_thing_searched
;
3015 last_thing_searched
= Qnil
;
3016 search_regs
.num_regs
= 0;
3017 search_regs
.start
= 0;
3018 search_regs
.end
= 0;
3020 search_regs_saved
= 1;
3024 /* Called upon exit from filters and sentinels. */
3026 restore_search_regs ()
3028 if (search_regs_saved
)
3030 if (search_regs
.num_regs
> 0)
3032 xfree (search_regs
.start
);
3033 xfree (search_regs
.end
);
3035 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3036 search_regs
.start
= saved_search_regs
.start
;
3037 search_regs
.end
= saved_search_regs
.end
;
3038 last_thing_searched
= saved_last_thing_searched
;
3039 saved_last_thing_searched
= Qnil
;
3040 search_regs_saved
= 0;
3045 unwind_set_match_data (list
)
3048 /* It is safe to free (evaporate) the markers immediately. */
3049 return Fset_match_data (list
, Qevaporate
);
3052 /* Called to unwind protect the match data. */
3054 record_unwind_save_match_data ()
3056 record_unwind_protect (unwind_set_match_data
,
3057 Fmatch_data (Qnil
, Qnil
, Qnil
));
3060 /* Quote a string to inactivate reg-expr chars */
3062 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3063 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3067 register unsigned char *in
, *out
, *end
;
3068 register unsigned char *temp
;
3069 int backslashes_added
= 0;
3071 CHECK_STRING (string
);
3073 temp
= (unsigned char *) alloca (SBYTES (string
) * 2);
3075 /* Now copy the data into the new string, inserting escapes. */
3077 in
= SDATA (string
);
3078 end
= in
+ SBYTES (string
);
3081 for (; in
!= end
; in
++)
3084 || *in
== '*' || *in
== '.' || *in
== '\\'
3085 || *in
== '?' || *in
== '+'
3086 || *in
== '^' || *in
== '$')
3087 *out
++ = '\\', backslashes_added
++;
3091 return make_specified_string (temp
,
3092 SCHARS (string
) + backslashes_added
,
3094 STRING_MULTIBYTE (string
));
3102 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3104 searchbufs
[i
].buf
.allocated
= 100;
3105 searchbufs
[i
].buf
.buffer
= (unsigned char *) xmalloc (100);
3106 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3107 searchbufs
[i
].regexp
= Qnil
;
3108 searchbufs
[i
].whitespace_regexp
= Qnil
;
3109 searchbufs
[i
].syntax_table
= Qnil
;
3110 staticpro (&searchbufs
[i
].regexp
);
3111 staticpro (&searchbufs
[i
].whitespace_regexp
);
3112 staticpro (&searchbufs
[i
].syntax_table
);
3113 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3115 searchbuf_head
= &searchbufs
[0];
3117 Qsearch_failed
= intern ("search-failed");
3118 staticpro (&Qsearch_failed
);
3119 Qinvalid_regexp
= intern ("invalid-regexp");
3120 staticpro (&Qinvalid_regexp
);
3122 Fput (Qsearch_failed
, Qerror_conditions
,
3123 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
3124 Fput (Qsearch_failed
, Qerror_message
,
3125 build_string ("Search failed"));
3127 Fput (Qinvalid_regexp
, Qerror_conditions
,
3128 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
3129 Fput (Qinvalid_regexp
, Qerror_message
,
3130 build_string ("Invalid regexp"));
3132 last_thing_searched
= Qnil
;
3133 staticpro (&last_thing_searched
);
3135 saved_last_thing_searched
= Qnil
;
3136 staticpro (&saved_last_thing_searched
);
3138 DEFVAR_LISP ("search-spaces-regexp", &Vsearch_spaces_regexp
,
3139 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3140 Some commands use this for user-specified regexps.
3141 Spaces that occur inside character classes or repetition operators
3142 or other such regexp constructs are not replaced with this.
3143 A value of nil (which is the normal value) means treat spaces literally. */);
3144 Vsearch_spaces_regexp
= Qnil
;
3146 defsubr (&Slooking_at
);
3147 defsubr (&Sposix_looking_at
);
3148 defsubr (&Sstring_match
);
3149 defsubr (&Sposix_string_match
);
3150 defsubr (&Ssearch_forward
);
3151 defsubr (&Ssearch_backward
);
3152 defsubr (&Sword_search_forward
);
3153 defsubr (&Sword_search_backward
);
3154 defsubr (&Sre_search_forward
);
3155 defsubr (&Sre_search_backward
);
3156 defsubr (&Sposix_search_forward
);
3157 defsubr (&Sposix_search_backward
);
3158 defsubr (&Sreplace_match
);
3159 defsubr (&Smatch_beginning
);
3160 defsubr (&Smatch_end
);
3161 defsubr (&Smatch_data
);
3162 defsubr (&Sset_match_data
);
3163 defsubr (&Sregexp_quote
);
3166 /* arch-tag: a6059d79-0552-4f14-a2cb-d379a4e3c78f
3167 (do not change this comment) */