1 /* String search routines for GNU Emacs.
2 Copyright (C) 1985, 86,87,93,94,97,98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU Emacs.
6 GNU Emacs is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Emacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Emacs; see the file COPYING. If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
28 #include "region-cache.h"
30 #include "blockinput.h"
31 #include "intervals.h"
33 #include <sys/types.h>
36 #define min(a, b) ((a) < (b) ? (a) : (b))
37 #define max(a, b) ((a) > (b) ? (a) : (b))
39 #define REGEXP_CACHE_SIZE 20
41 /* If the regexp is non-nil, then the buffer contains the compiled form
42 of that regexp, suitable for searching. */
45 struct regexp_cache
*next
;
47 struct re_pattern_buffer buf
;
49 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
53 /* The instances of that struct. */
54 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
56 /* The head of the linked list; points to the most recently used buffer. */
57 struct regexp_cache
*searchbuf_head
;
60 /* Every call to re_match, etc., must pass &search_regs as the regs
61 argument unless you can show it is unnecessary (i.e., if re_match
62 is certainly going to be called again before region-around-match
65 Since the registers are now dynamically allocated, we need to make
66 sure not to refer to the Nth register before checking that it has
67 been allocated by checking search_regs.num_regs.
69 The regex code keeps track of whether it has allocated the search
70 buffer using bits in the re_pattern_buffer. This means that whenever
71 you compile a new pattern, it completely forgets whether it has
72 allocated any registers, and will allocate new registers the next
73 time you call a searching or matching function. Therefore, we need
74 to call re_set_registers after compiling a new pattern or after
75 setting the match registers, so that the regex functions will be
76 able to free or re-allocate it properly. */
77 static struct re_registers search_regs
;
79 /* The buffer in which the last search was performed, or
80 Qt if the last search was done in a string;
81 Qnil if no searching has been done yet. */
82 static Lisp_Object last_thing_searched
;
84 /* error condition signaled when regexp compile_pattern fails */
86 Lisp_Object Qinvalid_regexp
;
88 static void set_search_regs ();
89 static void save_search_regs ();
90 static int simple_search ();
91 static int boyer_moore ();
92 static int search_buffer ();
97 error ("Stack overflow in regexp matcher");
100 /* Compile a regexp and signal a Lisp error if anything goes wrong.
101 PATTERN is the pattern to compile.
102 CP is the place to put the result.
103 TRANSLATE is a translation table for ignoring case, or nil for none.
104 REGP is the structure that says where to store the "register"
105 values that will result from matching this pattern.
106 If it is 0, we should compile the pattern not to record any
107 subexpression bounds.
108 POSIX is nonzero if we want full backtracking (POSIX style)
109 for this pattern. 0 means backtrack only enough to get a valid match.
110 MULTIBYTE is nonzero if we want to handle multibyte characters in
111 PATTERN. 0 means all multibyte characters are recognized just as
112 sequences of binary data. */
115 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
116 struct regexp_cache
*cp
;
118 Lisp_Object translate
;
119 struct re_registers
*regp
;
123 unsigned char *raw_pattern
;
124 int raw_pattern_size
;
128 /* MULTIBYTE says whether the text to be searched is multibyte.
129 We must convert PATTERN to match that, or we will not really
130 find things right. */
132 if (multibyte
== STRING_MULTIBYTE (pattern
))
134 raw_pattern
= (unsigned char *) XSTRING (pattern
)->data
;
135 raw_pattern_size
= STRING_BYTES (XSTRING (pattern
));
139 raw_pattern_size
= count_size_as_multibyte (XSTRING (pattern
)->data
,
140 XSTRING (pattern
)->size
);
141 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
142 copy_text (XSTRING (pattern
)->data
, raw_pattern
,
143 XSTRING (pattern
)->size
, 0, 1);
147 /* Converting multibyte to single-byte.
149 ??? Perhaps this conversion should be done in a special way
150 by subtracting nonascii-insert-offset from each non-ASCII char,
151 so that only the multibyte chars which really correspond to
152 the chosen single-byte character set can possibly match. */
153 raw_pattern_size
= XSTRING (pattern
)->size
;
154 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
155 copy_text (XSTRING (pattern
)->data
, raw_pattern
,
156 STRING_BYTES (XSTRING (pattern
)), 1, 0);
160 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
162 cp
->buf
.multibyte
= multibyte
;
164 old
= re_set_syntax (RE_SYNTAX_EMACS
165 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
166 val
= (char *) re_compile_pattern ((char *)raw_pattern
,
167 raw_pattern_size
, &cp
->buf
);
171 Fsignal (Qinvalid_regexp
, Fcons (build_string (val
), Qnil
));
173 cp
->regexp
= Fcopy_sequence (pattern
);
176 /* Shrink each compiled regexp buffer in the cache
177 to the size actually used right now.
178 This is called from garbage collection. */
181 shrink_regexp_cache ()
183 struct regexp_cache
*cp
;
185 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
187 cp
->buf
.allocated
= cp
->buf
.used
;
189 = (unsigned char *) realloc (cp
->buf
.buffer
, cp
->buf
.used
);
193 /* Compile a regexp if necessary, but first check to see if there's one in
195 PATTERN is the pattern to compile.
196 TRANSLATE is a translation table for ignoring case, or nil for none.
197 REGP is the structure that says where to store the "register"
198 values that will result from matching this pattern.
199 If it is 0, we should compile the pattern not to record any
200 subexpression bounds.
201 POSIX is nonzero if we want full backtracking (POSIX style)
202 for this pattern. 0 means backtrack only enough to get a valid match. */
204 struct re_pattern_buffer
*
205 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
207 struct re_registers
*regp
;
208 Lisp_Object translate
;
209 int posix
, multibyte
;
211 struct regexp_cache
*cp
, **cpp
;
213 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
216 /* Entries are initialized to nil, and may be set to nil by
217 compile_pattern_1 if the pattern isn't valid. Don't apply
218 XSTRING in those cases. However, compile_pattern_1 is only
219 applied to the cache entry we pick here to reuse. So nil
220 should never appear before a non-nil entry. */
221 if (NILP (cp
->regexp
))
223 if (XSTRING (cp
->regexp
)->size
== XSTRING (pattern
)->size
224 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
225 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
226 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
227 && cp
->posix
== posix
228 && cp
->buf
.multibyte
== multibyte
)
231 /* If we're at the end of the cache, compile into the nil cell
232 we found, or the last (least recently used) cell with a
237 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
242 /* When we get here, cp (aka *cpp) contains the compiled pattern,
243 either because we found it in the cache or because we just compiled it.
244 Move it to the front of the queue to mark it as most recently used. */
246 cp
->next
= searchbuf_head
;
249 /* Advise the searching functions about the space we have allocated
250 for register data. */
252 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
257 /* Error condition used for failing searches */
258 Lisp_Object Qsearch_failed
;
264 Fsignal (Qsearch_failed
, Fcons (arg
, Qnil
));
269 looking_at_1 (string
, posix
)
274 unsigned char *p1
, *p2
;
277 struct re_pattern_buffer
*bufp
;
279 if (running_asynch_code
)
282 CHECK_STRING (string
, 0);
283 bufp
= compile_pattern (string
, &search_regs
,
284 (!NILP (current_buffer
->case_fold_search
)
285 ? DOWNCASE_TABLE
: Qnil
),
287 !NILP (current_buffer
->enable_multibyte_characters
));
290 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
292 /* Get pointers and sizes of the two strings
293 that make up the visible portion of the buffer. */
296 s1
= GPT_BYTE
- BEGV_BYTE
;
298 s2
= ZV_BYTE
- GPT_BYTE
;
302 s2
= ZV_BYTE
- BEGV_BYTE
;
307 s1
= ZV_BYTE
- BEGV_BYTE
;
311 re_match_object
= Qnil
;
313 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
314 PT_BYTE
- BEGV_BYTE
, &search_regs
,
315 ZV_BYTE
- BEGV_BYTE
);
321 val
= (0 <= i
? Qt
: Qnil
);
323 for (i
= 0; i
< search_regs
.num_regs
; i
++)
324 if (search_regs
.start
[i
] >= 0)
327 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
329 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
331 XSETBUFFER (last_thing_searched
, current_buffer
);
335 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
336 "Return t if text after point matches regular expression REGEXP.\n\
337 This function modifies the match data that `match-beginning',\n\
338 `match-end' and `match-data' access; save and restore the match\n\
339 data if you want to preserve them.")
343 return looking_at_1 (regexp
, 0);
346 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
347 "Return t if text after point matches regular expression REGEXP.\n\
348 Find the longest match, in accord with Posix regular expression rules.\n\
349 This function modifies the match data that `match-beginning',\n\
350 `match-end' and `match-data' access; save and restore the match\n\
351 data if you want to preserve them.")
355 return looking_at_1 (regexp
, 1);
359 string_match_1 (regexp
, string
, start
, posix
)
360 Lisp_Object regexp
, string
, start
;
364 struct re_pattern_buffer
*bufp
;
368 if (running_asynch_code
)
371 CHECK_STRING (regexp
, 0);
372 CHECK_STRING (string
, 1);
375 pos
= 0, pos_byte
= 0;
378 int len
= XSTRING (string
)->size
;
380 CHECK_NUMBER (start
, 2);
382 if (pos
< 0 && -pos
<= len
)
384 else if (0 > pos
|| pos
> len
)
385 args_out_of_range (string
, start
);
386 pos_byte
= string_char_to_byte (string
, pos
);
389 bufp
= compile_pattern (regexp
, &search_regs
,
390 (!NILP (current_buffer
->case_fold_search
)
391 ? DOWNCASE_TABLE
: Qnil
),
393 STRING_MULTIBYTE (string
));
395 re_match_object
= string
;
397 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
398 STRING_BYTES (XSTRING (string
)), pos_byte
,
399 STRING_BYTES (XSTRING (string
)) - pos_byte
,
402 last_thing_searched
= Qt
;
405 if (val
< 0) return Qnil
;
407 for (i
= 0; i
< search_regs
.num_regs
; i
++)
408 if (search_regs
.start
[i
] >= 0)
411 = string_byte_to_char (string
, search_regs
.start
[i
]);
413 = string_byte_to_char (string
, search_regs
.end
[i
]);
416 return make_number (string_byte_to_char (string
, val
));
419 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
420 "Return index of start of first match for REGEXP in STRING, or nil.\n\
421 Case is ignored if `case-fold-search' is non-nil in the current buffer.\n\
422 If third arg START is non-nil, start search at that index in STRING.\n\
423 For index of first char beyond the match, do (match-end 0).\n\
424 `match-end' and `match-beginning' also give indices of substrings\n\
425 matched by parenthesis constructs in the pattern.")
426 (regexp
, string
, start
)
427 Lisp_Object regexp
, string
, start
;
429 return string_match_1 (regexp
, string
, start
, 0);
432 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
433 "Return index of start of first match for REGEXP in STRING, or nil.\n\
434 Find the longest match, in accord with Posix regular expression rules.\n\
435 Case is ignored if `case-fold-search' is non-nil in the current buffer.\n\
436 If third arg START is non-nil, start search at that index in STRING.\n\
437 For index of first char beyond the match, do (match-end 0).\n\
438 `match-end' and `match-beginning' also give indices of substrings\n\
439 matched by parenthesis constructs in the pattern.")
440 (regexp
, string
, start
)
441 Lisp_Object regexp
, string
, start
;
443 return string_match_1 (regexp
, string
, start
, 1);
446 /* Match REGEXP against STRING, searching all of STRING,
447 and return the index of the match, or negative on failure.
448 This does not clobber the match data. */
451 fast_string_match (regexp
, string
)
452 Lisp_Object regexp
, string
;
455 struct re_pattern_buffer
*bufp
;
457 bufp
= compile_pattern (regexp
, 0, Qnil
,
458 0, STRING_MULTIBYTE (string
));
460 re_match_object
= string
;
462 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
463 STRING_BYTES (XSTRING (string
)), 0,
464 STRING_BYTES (XSTRING (string
)), 0);
469 /* Match REGEXP against STRING, searching all of STRING ignoring case,
470 and return the index of the match, or negative on failure.
471 This does not clobber the match data.
472 We assume that STRING contains single-byte characters. */
474 extern Lisp_Object Vascii_downcase_table
;
477 fast_c_string_match_ignore_case (regexp
, string
)
482 struct re_pattern_buffer
*bufp
;
483 int len
= strlen (string
);
485 regexp
= string_make_unibyte (regexp
);
486 re_match_object
= Qt
;
487 bufp
= compile_pattern (regexp
, 0,
488 Vascii_downcase_table
, 0,
491 val
= re_search (bufp
, string
, len
, 0, len
, 0);
496 /* The newline cache: remembering which sections of text have no newlines. */
498 /* If the user has requested newline caching, make sure it's on.
499 Otherwise, make sure it's off.
500 This is our cheezy way of associating an action with the change of
501 state of a buffer-local variable. */
503 newline_cache_on_off (buf
)
506 if (NILP (buf
->cache_long_line_scans
))
508 /* It should be off. */
509 if (buf
->newline_cache
)
511 free_region_cache (buf
->newline_cache
);
512 buf
->newline_cache
= 0;
517 /* It should be on. */
518 if (buf
->newline_cache
== 0)
519 buf
->newline_cache
= new_region_cache ();
524 /* Search for COUNT instances of the character TARGET between START and END.
526 If COUNT is positive, search forwards; END must be >= START.
527 If COUNT is negative, search backwards for the -COUNTth instance;
528 END must be <= START.
529 If COUNT is zero, do anything you please; run rogue, for all I care.
531 If END is zero, use BEGV or ZV instead, as appropriate for the
532 direction indicated by COUNT.
534 If we find COUNT instances, set *SHORTAGE to zero, and return the
535 position after the COUNTth match. Note that for reverse motion
536 this is not the same as the usual convention for Emacs motion commands.
538 If we don't find COUNT instances before reaching END, set *SHORTAGE
539 to the number of TARGETs left unfound, and return END.
541 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
542 except when inside redisplay. */
545 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
552 struct region_cache
*newline_cache
;
563 if (! end
) end
= BEGV
;
566 newline_cache_on_off (current_buffer
);
567 newline_cache
= current_buffer
->newline_cache
;
572 immediate_quit
= allow_quit
;
577 /* Our innermost scanning loop is very simple; it doesn't know
578 about gaps, buffer ends, or the newline cache. ceiling is
579 the position of the last character before the next such
580 obstacle --- the last character the dumb search loop should
582 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
583 int start_byte
= CHAR_TO_BYTE (start
);
586 /* If we're looking for a newline, consult the newline cache
587 to see where we can avoid some scanning. */
588 if (target
== '\n' && newline_cache
)
592 while (region_cache_forward
593 (current_buffer
, newline_cache
, start_byte
, &next_change
))
594 start_byte
= next_change
;
595 immediate_quit
= allow_quit
;
597 /* START should never be after END. */
598 if (start_byte
> ceiling_byte
)
599 start_byte
= ceiling_byte
;
601 /* Now the text after start is an unknown region, and
602 next_change is the position of the next known region. */
603 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
606 /* The dumb loop can only scan text stored in contiguous
607 bytes. BUFFER_CEILING_OF returns the last character
608 position that is contiguous, so the ceiling is the
609 position after that. */
610 tem
= BUFFER_CEILING_OF (start_byte
);
611 ceiling_byte
= min (tem
, ceiling_byte
);
614 /* The termination address of the dumb loop. */
615 register unsigned char *ceiling_addr
616 = BYTE_POS_ADDR (ceiling_byte
) + 1;
617 register unsigned char *cursor
618 = BYTE_POS_ADDR (start_byte
);
619 unsigned char *base
= cursor
;
621 while (cursor
< ceiling_addr
)
623 unsigned char *scan_start
= cursor
;
626 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
629 /* If we're looking for newlines, cache the fact that
630 the region from start to cursor is free of them. */
631 if (target
== '\n' && newline_cache
)
632 know_region_cache (current_buffer
, newline_cache
,
633 start_byte
+ scan_start
- base
,
634 start_byte
+ cursor
- base
);
636 /* Did we find the target character? */
637 if (cursor
< ceiling_addr
)
642 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
648 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
654 /* The last character to check before the next obstacle. */
655 int ceiling_byte
= CHAR_TO_BYTE (end
);
656 int start_byte
= CHAR_TO_BYTE (start
);
659 /* Consult the newline cache, if appropriate. */
660 if (target
== '\n' && newline_cache
)
664 while (region_cache_backward
665 (current_buffer
, newline_cache
, start_byte
, &next_change
))
666 start_byte
= next_change
;
667 immediate_quit
= allow_quit
;
669 /* Start should never be at or before end. */
670 if (start_byte
<= ceiling_byte
)
671 start_byte
= ceiling_byte
+ 1;
673 /* Now the text before start is an unknown region, and
674 next_change is the position of the next known region. */
675 ceiling_byte
= max (next_change
, ceiling_byte
);
678 /* Stop scanning before the gap. */
679 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
680 ceiling_byte
= max (tem
, ceiling_byte
);
683 /* The termination address of the dumb loop. */
684 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
685 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
686 unsigned char *base
= cursor
;
688 while (cursor
>= ceiling_addr
)
690 unsigned char *scan_start
= cursor
;
692 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
695 /* If we're looking for newlines, cache the fact that
696 the region from after the cursor to start is free of them. */
697 if (target
== '\n' && newline_cache
)
698 know_region_cache (current_buffer
, newline_cache
,
699 start_byte
+ cursor
- base
,
700 start_byte
+ scan_start
- base
);
702 /* Did we find the target character? */
703 if (cursor
>= ceiling_addr
)
708 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
714 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
720 *shortage
= count
* direction
;
724 /* Search for COUNT instances of a line boundary, which means either a
725 newline or (if selective display enabled) a carriage return.
726 Start at START. If COUNT is negative, search backwards.
728 We report the resulting position by calling TEMP_SET_PT_BOTH.
730 If we find COUNT instances. we position after (always after,
731 even if scanning backwards) the COUNTth match, and return 0.
733 If we don't find COUNT instances before reaching the end of the
734 buffer (or the beginning, if scanning backwards), we return
735 the number of line boundaries left unfound, and position at
736 the limit we bumped up against.
738 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
739 except in special cases. */
742 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
743 int start
, start_byte
;
744 int limit
, limit_byte
;
748 int direction
= ((count
> 0) ? 1 : -1);
750 register unsigned char *cursor
;
753 register int ceiling
;
754 register unsigned char *ceiling_addr
;
756 int old_immediate_quit
= immediate_quit
;
758 /* If we are not in selective display mode,
759 check only for newlines. */
760 int selective_display
= (!NILP (current_buffer
->selective_display
)
761 && !INTEGERP (current_buffer
->selective_display
));
763 /* The code that follows is like scan_buffer
764 but checks for either newline or carriage return. */
769 start_byte
= CHAR_TO_BYTE (start
);
773 while (start_byte
< limit_byte
)
775 ceiling
= BUFFER_CEILING_OF (start_byte
);
776 ceiling
= min (limit_byte
- 1, ceiling
);
777 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
778 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
781 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
784 if (cursor
!= ceiling_addr
)
788 immediate_quit
= old_immediate_quit
;
789 start_byte
= start_byte
+ cursor
- base
+ 1;
790 start
= BYTE_TO_CHAR (start_byte
);
791 TEMP_SET_PT_BOTH (start
, start_byte
);
795 if (++cursor
== ceiling_addr
)
801 start_byte
+= cursor
- base
;
806 while (start_byte
> limit_byte
)
808 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
809 ceiling
= max (limit_byte
, ceiling
);
810 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
811 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
814 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
817 if (cursor
!= ceiling_addr
)
821 immediate_quit
= old_immediate_quit
;
822 /* Return the position AFTER the match we found. */
823 start_byte
= start_byte
+ cursor
- base
+ 1;
824 start
= BYTE_TO_CHAR (start_byte
);
825 TEMP_SET_PT_BOTH (start
, start_byte
);
832 /* Here we add 1 to compensate for the last decrement
833 of CURSOR, which took it past the valid range. */
834 start_byte
+= cursor
- base
+ 1;
838 TEMP_SET_PT_BOTH (limit
, limit_byte
);
839 immediate_quit
= old_immediate_quit
;
841 return count
* direction
;
845 find_next_newline_no_quit (from
, cnt
)
846 register int from
, cnt
;
848 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
851 /* Like find_next_newline, but returns position before the newline,
852 not after, and only search up to TO. This isn't just
853 find_next_newline (...)-1, because you might hit TO. */
856 find_before_next_newline (from
, to
, cnt
)
860 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
868 /* Subroutines of Lisp buffer search functions. */
871 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
872 Lisp_Object string
, bound
, noerror
, count
;
883 CHECK_NUMBER (count
, 3);
887 CHECK_STRING (string
, 0);
891 lim
= ZV
, lim_byte
= ZV_BYTE
;
893 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
897 CHECK_NUMBER_COERCE_MARKER (bound
, 1);
899 if (n
> 0 ? lim
< PT
: lim
> PT
)
900 error ("Invalid search bound (wrong side of point)");
902 lim
= ZV
, lim_byte
= ZV_BYTE
;
904 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
906 lim_byte
= CHAR_TO_BYTE (lim
);
909 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
910 (!NILP (current_buffer
->case_fold_search
)
911 ? current_buffer
->case_canon_table
913 (!NILP (current_buffer
->case_fold_search
)
914 ? current_buffer
->case_eqv_table
920 return signal_failure (string
);
921 if (!EQ (noerror
, Qt
))
923 if (lim
< BEGV
|| lim
> ZV
)
925 SET_PT_BOTH (lim
, lim_byte
);
927 #if 0 /* This would be clean, but maybe programs depend on
928 a value of nil here. */
936 if (np
< BEGV
|| np
> ZV
)
941 return make_number (np
);
944 /* Return 1 if REGEXP it matches just one constant string. */
947 trivial_regexp_p (regexp
)
950 int len
= STRING_BYTES (XSTRING (regexp
));
951 unsigned char *s
= XSTRING (regexp
)->data
;
956 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
963 case '|': case '(': case ')': case '`': case '\'': case 'b':
964 case 'B': case '<': case '>': case 'w': case 'W': case 's':
965 case 'S': case '=': case '{': case '}':
966 case 'c': case 'C': /* for categoryspec and notcategoryspec */
967 case '1': case '2': case '3': case '4': case '5':
968 case '6': case '7': case '8': case '9':
976 /* Search for the n'th occurrence of STRING in the current buffer,
977 starting at position POS and stopping at position LIM,
978 treating STRING as a literal string if RE is false or as
979 a regular expression if RE is true.
981 If N is positive, searching is forward and LIM must be greater than POS.
982 If N is negative, searching is backward and LIM must be less than POS.
984 Returns -x if x occurrences remain to be found (x > 0),
985 or else the position at the beginning of the Nth occurrence
986 (if searching backward) or the end (if searching forward).
988 POSIX is nonzero if we want full backtracking (POSIX style)
989 for this pattern. 0 means backtrack only enough to get a valid match. */
991 #define TRANSLATE(out, trt, d) \
997 temp = Faref (trt, make_number (d)); \
998 if (INTEGERP (temp)) \
1009 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
1010 RE
, trt
, inverse_trt
, posix
)
1019 Lisp_Object inverse_trt
;
1022 int len
= XSTRING (string
)->size
;
1023 int len_byte
= STRING_BYTES (XSTRING (string
));
1026 if (running_asynch_code
)
1027 save_search_regs ();
1029 /* Searching 0 times means don't move. */
1030 /* Null string is found at starting position. */
1031 if (len
== 0 || n
== 0)
1033 set_search_regs (pos_byte
, 0);
1037 if (RE
&& !trivial_regexp_p (string
))
1039 unsigned char *p1
, *p2
;
1041 struct re_pattern_buffer
*bufp
;
1043 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
,
1044 !NILP (current_buffer
->enable_multibyte_characters
));
1046 immediate_quit
= 1; /* Quit immediately if user types ^G,
1047 because letting this function finish
1048 can take too long. */
1049 QUIT
; /* Do a pending quit right away,
1050 to avoid paradoxical behavior */
1051 /* Get pointers and sizes of the two strings
1052 that make up the visible portion of the buffer. */
1055 s1
= GPT_BYTE
- BEGV_BYTE
;
1057 s2
= ZV_BYTE
- GPT_BYTE
;
1061 s2
= ZV_BYTE
- BEGV_BYTE
;
1066 s1
= ZV_BYTE
- BEGV_BYTE
;
1069 re_match_object
= Qnil
;
1074 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1075 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1077 /* Don't allow match past current point */
1078 pos_byte
- BEGV_BYTE
);
1081 matcher_overflow ();
1085 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1086 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1087 if (search_regs
.start
[i
] >= 0)
1089 search_regs
.start
[i
]
1090 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1092 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1094 XSETBUFFER (last_thing_searched
, current_buffer
);
1095 /* Set pos to the new position. */
1096 pos
= search_regs
.start
[0];
1108 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1109 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1111 lim_byte
- BEGV_BYTE
);
1114 matcher_overflow ();
1118 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1119 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1120 if (search_regs
.start
[i
] >= 0)
1122 search_regs
.start
[i
]
1123 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1125 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1127 XSETBUFFER (last_thing_searched
, current_buffer
);
1128 pos
= search_regs
.end
[0];
1140 else /* non-RE case */
1142 unsigned char *raw_pattern
, *pat
;
1143 int raw_pattern_size
;
1144 int raw_pattern_size_byte
;
1145 unsigned char *patbuf
;
1146 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1147 unsigned char *base_pat
= XSTRING (string
)->data
;
1148 int charset_base
= -1;
1149 int boyer_moore_ok
= 1;
1151 /* MULTIBYTE says whether the text to be searched is multibyte.
1152 We must convert PATTERN to match that, or we will not really
1153 find things right. */
1155 if (multibyte
== STRING_MULTIBYTE (string
))
1157 raw_pattern
= (unsigned char *) XSTRING (string
)->data
;
1158 raw_pattern_size
= XSTRING (string
)->size
;
1159 raw_pattern_size_byte
= STRING_BYTES (XSTRING (string
));
1163 raw_pattern_size
= XSTRING (string
)->size
;
1164 raw_pattern_size_byte
1165 = count_size_as_multibyte (XSTRING (string
)->data
,
1167 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1168 copy_text (XSTRING (string
)->data
, raw_pattern
,
1169 XSTRING (string
)->size
, 0, 1);
1173 /* Converting multibyte to single-byte.
1175 ??? Perhaps this conversion should be done in a special way
1176 by subtracting nonascii-insert-offset from each non-ASCII char,
1177 so that only the multibyte chars which really correspond to
1178 the chosen single-byte character set can possibly match. */
1179 raw_pattern_size
= XSTRING (string
)->size
;
1180 raw_pattern_size_byte
= XSTRING (string
)->size
;
1181 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1182 copy_text (XSTRING (string
)->data
, raw_pattern
,
1183 STRING_BYTES (XSTRING (string
)), 1, 0);
1186 /* Copy and optionally translate the pattern. */
1187 len
= raw_pattern_size
;
1188 len_byte
= raw_pattern_size_byte
;
1189 patbuf
= (unsigned char *) alloca (len_byte
);
1191 base_pat
= raw_pattern
;
1196 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1197 int c
, translated
, inverse
;
1198 int in_charlen
, charlen
;
1200 /* If we got here and the RE flag is set, it's because we're
1201 dealing with a regexp known to be trivial, so the backslash
1202 just quotes the next character. */
1203 if (RE
&& *base_pat
== '\\')
1210 c
= STRING_CHAR_AND_LENGTH (base_pat
, len_byte
, in_charlen
);
1212 /* Translate the character, if requested. */
1213 TRANSLATE (translated
, trt
, c
);
1214 /* If translation changed the byte-length, go back
1215 to the original character. */
1216 charlen
= CHAR_STRING (translated
, str
);
1217 if (in_charlen
!= charlen
)
1220 charlen
= CHAR_STRING (c
, str
);
1223 /* If we are searching for something strange,
1224 an invalid multibyte code, don't use boyer-moore. */
1225 if (! ASCII_BYTE_P (translated
)
1226 && (charlen
== 1 /* 8bit code */
1227 || charlen
!= in_charlen
/* invalid multibyte code */
1231 TRANSLATE (inverse
, inverse_trt
, c
);
1233 /* Did this char actually get translated?
1234 Would any other char get translated into it? */
1235 if (translated
!= c
|| inverse
!= c
)
1237 /* Keep track of which character set row
1238 contains the characters that need translation. */
1239 int charset_base_code
= c
& ~CHAR_FIELD3_MASK
;
1240 int inverse_charset_base
= inverse
& ~CHAR_FIELD3_MASK
;
1242 if (charset_base_code
!= inverse_charset_base
)
1244 else if (charset_base
== -1)
1245 charset_base
= charset_base_code
;
1246 else if (charset_base
!= charset_base_code
)
1247 /* If two different rows appear, needing translation,
1248 then we cannot use boyer_moore search. */
1252 /* Store this character into the translated pattern. */
1253 bcopy (str
, pat
, charlen
);
1255 base_pat
+= in_charlen
;
1256 len_byte
-= in_charlen
;
1261 /* Unibyte buffer. */
1267 /* If we got here and the RE flag is set, it's because we're
1268 dealing with a regexp known to be trivial, so the backslash
1269 just quotes the next character. */
1270 if (RE
&& *base_pat
== '\\')
1276 TRANSLATE (translated
, trt
, c
);
1277 *pat
++ = translated
;
1281 len_byte
= pat
- patbuf
;
1282 len
= raw_pattern_size
;
1283 pat
= base_pat
= patbuf
;
1286 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1287 pos
, pos_byte
, lim
, lim_byte
,
1290 return simple_search (n
, pat
, len
, len_byte
, trt
,
1291 pos
, pos_byte
, lim
, lim_byte
);
1295 /* Do a simple string search N times for the string PAT,
1296 whose length is LEN/LEN_BYTE,
1297 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1298 TRT is the translation table.
1300 Return the character position where the match is found.
1301 Otherwise, if M matches remained to be found, return -M.
1303 This kind of search works regardless of what is in PAT and
1304 regardless of what is in TRT. It is used in cases where
1305 boyer_moore cannot work. */
1308 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1316 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1317 int forward
= n
> 0;
1319 if (lim
> pos
&& multibyte
)
1324 /* Try matching at position POS. */
1326 int this_pos_byte
= pos_byte
;
1328 int this_len_byte
= len_byte
;
1329 unsigned char *p
= pat
;
1330 if (pos
+ len
> lim
)
1333 while (this_len
> 0)
1335 int charlen
, buf_charlen
;
1338 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1339 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1340 ZV_BYTE
- this_pos_byte
,
1342 TRANSLATE (buf_ch
, trt
, buf_ch
);
1344 if (buf_ch
!= pat_ch
)
1347 this_len_byte
-= charlen
;
1351 this_pos_byte
+= buf_charlen
;
1358 pos_byte
+= len_byte
;
1362 INC_BOTH (pos
, pos_byte
);
1372 /* Try matching at position POS. */
1375 unsigned char *p
= pat
;
1377 if (pos
+ len
> lim
)
1380 while (this_len
> 0)
1383 int buf_ch
= FETCH_BYTE (this_pos
);
1384 TRANSLATE (buf_ch
, trt
, buf_ch
);
1386 if (buf_ch
!= pat_ch
)
1404 /* Backwards search. */
1405 else if (lim
< pos
&& multibyte
)
1410 /* Try matching at position POS. */
1411 int this_pos
= pos
- len
;
1412 int this_pos_byte
= pos_byte
- len_byte
;
1414 int this_len_byte
= len_byte
;
1415 unsigned char *p
= pat
;
1417 if (pos
- len
< lim
)
1420 while (this_len
> 0)
1422 int charlen
, buf_charlen
;
1425 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1426 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1427 ZV_BYTE
- this_pos_byte
,
1429 TRANSLATE (buf_ch
, trt
, buf_ch
);
1431 if (buf_ch
!= pat_ch
)
1434 this_len_byte
-= charlen
;
1437 this_pos_byte
+= buf_charlen
;
1444 pos_byte
-= len_byte
;
1448 DEC_BOTH (pos
, pos_byte
);
1458 /* Try matching at position POS. */
1459 int this_pos
= pos
- len
;
1461 unsigned char *p
= pat
;
1463 if (pos
- len
< lim
)
1466 while (this_len
> 0)
1469 int buf_ch
= FETCH_BYTE (this_pos
);
1470 TRANSLATE (buf_ch
, trt
, buf_ch
);
1472 if (buf_ch
!= pat_ch
)
1494 set_search_regs ((multibyte
? pos_byte
: pos
) - len_byte
, len_byte
);
1496 set_search_regs (multibyte
? pos_byte
: pos
, len_byte
);
1506 /* Do Boyer-Moore search N times for the string PAT,
1507 whose length is LEN/LEN_BYTE,
1508 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1509 DIRECTION says which direction we search in.
1510 TRT and INVERSE_TRT are translation tables.
1512 This kind of search works if all the characters in PAT that have
1513 nontrivial translation are the same aside from the last byte. This
1514 makes it possible to translate just the last byte of a character,
1515 and do so after just a simple test of the context.
1517 If that criterion is not satisfied, do not call this function. */
1520 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1521 pos
, pos_byte
, lim
, lim_byte
, charset_base
)
1523 unsigned char *base_pat
;
1526 Lisp_Object inverse_trt
;
1531 int direction
= ((n
> 0) ? 1 : -1);
1532 register int dirlen
;
1533 int infinity
, limit
, stride_for_teases
= 0;
1534 register int *BM_tab
;
1536 register unsigned char *cursor
, *p_limit
;
1538 unsigned char *pat
, *pat_end
;
1539 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1541 unsigned char simple_translate
[0400];
1542 int translate_prev_byte
= 0;
1543 int translate_anteprev_byte
= 0;
1546 int BM_tab_space
[0400];
1547 BM_tab
= &BM_tab_space
[0];
1549 BM_tab
= (int *) alloca (0400 * sizeof (int));
1551 /* The general approach is that we are going to maintain that we know */
1552 /* the first (closest to the present position, in whatever direction */
1553 /* we're searching) character that could possibly be the last */
1554 /* (furthest from present position) character of a valid match. We */
1555 /* advance the state of our knowledge by looking at that character */
1556 /* and seeing whether it indeed matches the last character of the */
1557 /* pattern. If it does, we take a closer look. If it does not, we */
1558 /* move our pointer (to putative last characters) as far as is */
1559 /* logically possible. This amount of movement, which I call a */
1560 /* stride, will be the length of the pattern if the actual character */
1561 /* appears nowhere in the pattern, otherwise it will be the distance */
1562 /* from the last occurrence of that character to the end of the */
1564 /* As a coding trick, an enormous stride is coded into the table for */
1565 /* characters that match the last character. This allows use of only */
1566 /* a single test, a test for having gone past the end of the */
1567 /* permissible match region, to test for both possible matches (when */
1568 /* the stride goes past the end immediately) and failure to */
1569 /* match (where you get nudged past the end one stride at a time). */
1571 /* Here we make a "mickey mouse" BM table. The stride of the search */
1572 /* is determined only by the last character of the putative match. */
1573 /* If that character does not match, we will stride the proper */
1574 /* distance to propose a match that superimposes it on the last */
1575 /* instance of a character that matches it (per trt), or misses */
1576 /* it entirely if there is none. */
1578 dirlen
= len_byte
* direction
;
1579 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1581 /* Record position after the end of the pattern. */
1582 pat_end
= base_pat
+ len_byte
;
1583 /* BASE_PAT points to a character that we start scanning from.
1584 It is the first character in a forward search,
1585 the last character in a backward search. */
1587 base_pat
= pat_end
- 1;
1589 BM_tab_base
= BM_tab
;
1591 j
= dirlen
; /* to get it in a register */
1592 /* A character that does not appear in the pattern induces a */
1593 /* stride equal to the pattern length. */
1594 while (BM_tab_base
!= BM_tab
)
1602 /* We use this for translation, instead of TRT itself.
1603 We fill this in to handle the characters that actually
1604 occur in the pattern. Others don't matter anyway! */
1605 bzero (simple_translate
, sizeof simple_translate
);
1606 for (i
= 0; i
< 0400; i
++)
1607 simple_translate
[i
] = i
;
1610 while (i
!= infinity
)
1612 unsigned char *ptr
= base_pat
+ i
;
1620 int this_translated
= 1;
1623 /* Is *PTR the last byte of a character? */
1624 && (pat_end
- ptr
== 1 || CHAR_HEAD_P (ptr
[1])))
1626 unsigned char *charstart
= ptr
;
1627 while (! CHAR_HEAD_P (*charstart
))
1629 untranslated
= STRING_CHAR (charstart
, ptr
- charstart
+ 1);
1630 if (charset_base
== (untranslated
& ~CHAR_FIELD3_MASK
))
1632 TRANSLATE (ch
, trt
, untranslated
);
1633 if (! CHAR_HEAD_P (*ptr
))
1635 translate_prev_byte
= ptr
[-1];
1636 if (! CHAR_HEAD_P (translate_prev_byte
))
1637 translate_anteprev_byte
= ptr
[-2];
1642 this_translated
= 0;
1646 else if (!multibyte
)
1647 TRANSLATE (ch
, trt
, *ptr
);
1651 this_translated
= 0;
1655 j
= ((unsigned char) ch
) | 0200;
1657 j
= (unsigned char) ch
;
1660 stride_for_teases
= BM_tab
[j
];
1662 BM_tab
[j
] = dirlen
- i
;
1663 /* A translation table is accompanied by its inverse -- see */
1664 /* comment following downcase_table for details */
1665 if (this_translated
)
1667 int starting_ch
= ch
;
1671 TRANSLATE (ch
, inverse_trt
, ch
);
1673 j
= ((unsigned char) ch
) | 0200;
1675 j
= (unsigned char) ch
;
1677 /* For all the characters that map into CH,
1678 set up simple_translate to map the last byte
1680 simple_translate
[j
] = starting_j
;
1681 if (ch
== starting_ch
)
1683 BM_tab
[j
] = dirlen
- i
;
1692 stride_for_teases
= BM_tab
[j
];
1693 BM_tab
[j
] = dirlen
- i
;
1695 /* stride_for_teases tells how much to stride if we get a */
1696 /* match on the far character but are subsequently */
1697 /* disappointed, by recording what the stride would have been */
1698 /* for that character if the last character had been */
1701 infinity
= dirlen
- infinity
;
1702 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1703 /* loop invariant - POS_BYTE points at where last char (first
1704 char if reverse) of pattern would align in a possible match. */
1708 unsigned char *tail_end_ptr
;
1710 /* It's been reported that some (broken) compiler thinks that
1711 Boolean expressions in an arithmetic context are unsigned.
1712 Using an explicit ?1:0 prevents this. */
1713 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1715 return (n
* (0 - direction
));
1716 /* First we do the part we can by pointers (maybe nothing) */
1719 limit
= pos_byte
- dirlen
+ direction
;
1722 limit
= BUFFER_CEILING_OF (limit
);
1723 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1724 can take on without hitting edge of buffer or the gap. */
1725 limit
= min (limit
, pos_byte
+ 20000);
1726 limit
= min (limit
, lim_byte
- 1);
1730 limit
= BUFFER_FLOOR_OF (limit
);
1731 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1732 can take on without hitting edge of buffer or the gap. */
1733 limit
= max (limit
, pos_byte
- 20000);
1734 limit
= max (limit
, lim_byte
);
1736 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1737 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1739 if ((limit
- pos_byte
) * direction
> 20)
1743 p_limit
= BYTE_POS_ADDR (limit
);
1744 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1745 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1746 while (1) /* use one cursor setting as long as i can */
1748 if (direction
> 0) /* worth duplicating */
1750 /* Use signed comparison if appropriate
1751 to make cursor+infinity sure to be > p_limit.
1752 Assuming that the buffer lies in a range of addresses
1753 that are all "positive" (as ints) or all "negative",
1754 either kind of comparison will work as long
1755 as we don't step by infinity. So pick the kind
1756 that works when we do step by infinity. */
1757 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1758 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1759 cursor
+= BM_tab
[*cursor
];
1761 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1762 cursor
+= BM_tab
[*cursor
];
1766 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1767 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1768 cursor
+= BM_tab
[*cursor
];
1770 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1771 cursor
+= BM_tab
[*cursor
];
1773 /* If you are here, cursor is beyond the end of the searched region. */
1774 /* This can happen if you match on the far character of the pattern, */
1775 /* because the "stride" of that character is infinity, a number able */
1776 /* to throw you well beyond the end of the search. It can also */
1777 /* happen if you fail to match within the permitted region and would */
1778 /* otherwise try a character beyond that region */
1779 if ((cursor
- p_limit
) * direction
<= len_byte
)
1780 break; /* a small overrun is genuine */
1781 cursor
-= infinity
; /* large overrun = hit */
1782 i
= dirlen
- direction
;
1785 while ((i
-= direction
) + direction
!= 0)
1788 cursor
-= direction
;
1789 /* Translate only the last byte of a character. */
1791 || ((cursor
== tail_end_ptr
1792 || CHAR_HEAD_P (cursor
[1]))
1793 && (CHAR_HEAD_P (cursor
[0])
1794 || (translate_prev_byte
== cursor
[-1]
1795 && (CHAR_HEAD_P (translate_prev_byte
)
1796 || translate_anteprev_byte
== cursor
[-2])))))
1797 ch
= simple_translate
[*cursor
];
1806 while ((i
-= direction
) + direction
!= 0)
1808 cursor
-= direction
;
1809 if (pat
[i
] != *cursor
)
1813 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1814 if (i
+ direction
== 0)
1818 cursor
-= direction
;
1820 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1821 ? 1 - len_byte
: 0);
1822 set_search_regs (position
, len_byte
);
1824 if ((n
-= direction
) != 0)
1825 cursor
+= dirlen
; /* to resume search */
1827 return ((direction
> 0)
1828 ? search_regs
.end
[0] : search_regs
.start
[0]);
1831 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1833 pos_byte
+= cursor
- p2
;
1836 /* Now we'll pick up a clump that has to be done the hard */
1837 /* way because it covers a discontinuity */
1839 limit
= ((direction
> 0)
1840 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1841 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1842 limit
= ((direction
> 0)
1843 ? min (limit
+ len_byte
, lim_byte
- 1)
1844 : max (limit
- len_byte
, lim_byte
));
1845 /* LIMIT is now the last value POS_BYTE can have
1846 and still be valid for a possible match. */
1849 /* This loop can be coded for space rather than */
1850 /* speed because it will usually run only once. */
1851 /* (the reach is at most len + 21, and typically */
1852 /* does not exceed len) */
1853 while ((limit
- pos_byte
) * direction
>= 0)
1854 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
1855 /* now run the same tests to distinguish going off the */
1856 /* end, a match or a phony match. */
1857 if ((pos_byte
- limit
) * direction
<= len_byte
)
1858 break; /* ran off the end */
1859 /* Found what might be a match.
1860 Set POS_BYTE back to last (first if reverse) pos. */
1861 pos_byte
-= infinity
;
1862 i
= dirlen
- direction
;
1863 while ((i
-= direction
) + direction
!= 0)
1867 pos_byte
-= direction
;
1868 ptr
= BYTE_POS_ADDR (pos_byte
);
1869 /* Translate only the last byte of a character. */
1871 || ((ptr
== tail_end_ptr
1872 || CHAR_HEAD_P (ptr
[1]))
1873 && (CHAR_HEAD_P (ptr
[0])
1874 || (translate_prev_byte
== ptr
[-1]
1875 && (CHAR_HEAD_P (translate_prev_byte
)
1876 || translate_anteprev_byte
== ptr
[-2])))))
1877 ch
= simple_translate
[*ptr
];
1883 /* Above loop has moved POS_BYTE part or all the way
1884 back to the first pos (last pos if reverse).
1885 Set it once again at the last (first if reverse) char. */
1886 pos_byte
+= dirlen
- i
- direction
;
1887 if (i
+ direction
== 0)
1890 pos_byte
-= direction
;
1892 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
1894 set_search_regs (position
, len_byte
);
1896 if ((n
-= direction
) != 0)
1897 pos_byte
+= dirlen
; /* to resume search */
1899 return ((direction
> 0)
1900 ? search_regs
.end
[0] : search_regs
.start
[0]);
1903 pos_byte
+= stride_for_teases
;
1906 /* We have done one clump. Can we continue? */
1907 if ((lim_byte
- pos_byte
) * direction
< 0)
1908 return ((0 - n
) * direction
);
1910 return BYTE_TO_CHAR (pos_byte
);
1913 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
1914 for the overall match just found in the current buffer.
1915 Also clear out the match data for registers 1 and up. */
1918 set_search_regs (beg_byte
, nbytes
)
1919 int beg_byte
, nbytes
;
1923 /* Make sure we have registers in which to store
1924 the match position. */
1925 if (search_regs
.num_regs
== 0)
1927 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1928 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1929 search_regs
.num_regs
= 2;
1932 /* Clear out the other registers. */
1933 for (i
= 1; i
< search_regs
.num_regs
; i
++)
1935 search_regs
.start
[i
] = -1;
1936 search_regs
.end
[i
] = -1;
1939 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
1940 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
1941 XSETBUFFER (last_thing_searched
, current_buffer
);
1944 /* Given a string of words separated by word delimiters,
1945 compute a regexp that matches those exact words
1946 separated by arbitrary punctuation. */
1952 register unsigned char *p
, *o
;
1953 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
1958 CHECK_STRING (string
, 0);
1959 p
= XSTRING (string
)->data
;
1960 len
= XSTRING (string
)->size
;
1962 for (i
= 0, i_byte
= 0; i
< len
; )
1966 FETCH_STRING_CHAR_ADVANCE (c
, string
, i
, i_byte
);
1968 if (SYNTAX (c
) != Sword
)
1971 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
1978 if (SYNTAX (prev_c
) == Sword
)
1981 return build_string ("");
1983 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
1984 if (STRING_MULTIBYTE (string
))
1985 val
= make_uninit_multibyte_string (len
+ adjust
,
1986 STRING_BYTES (XSTRING (string
))
1989 val
= make_uninit_string (len
+ adjust
);
1991 o
= XSTRING (val
)->data
;
1996 for (i
= 0, i_byte
= 0; i
< len
; )
1999 int i_byte_orig
= i_byte
;
2001 FETCH_STRING_CHAR_ADVANCE (c
, string
, i
, i_byte
);
2003 if (SYNTAX (c
) == Sword
)
2005 bcopy (&XSTRING (string
)->data
[i_byte_orig
], o
,
2006 i_byte
- i_byte_orig
);
2007 o
+= i_byte
- i_byte_orig
;
2009 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
2027 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2028 "MSearch backward: ",
2029 "Search backward from point for STRING.\n\
2030 Set point to the beginning of the occurrence found, and return point.\n\
2031 An optional second argument bounds the search; it is a buffer position.\n\
2032 The match found must not extend before that position.\n\
2033 Optional third argument, if t, means if fail just return nil (no error).\n\
2034 If not nil and not t, position at limit of search and return nil.\n\
2035 Optional fourth argument is repeat count--search for successive occurrences.\n\
2037 Search case-sensitivity is determined by the value of the variable\n\
2038 `case-fold-search', which see.\n\
2040 See also the functions `match-beginning', `match-end' and `replace-match'.")
2041 (string
, bound
, noerror
, count
)
2042 Lisp_Object string
, bound
, noerror
, count
;
2044 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2047 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2048 "Search forward from point for STRING.\n\
2049 Set point to the end of the occurrence found, and return point.\n\
2050 An optional second argument bounds the search; it is a buffer position.\n\
2051 The match found must not extend after that position. nil is equivalent\n\
2053 Optional third argument, if t, means if fail just return nil (no error).\n\
2054 If not nil and not t, move to limit of search and return nil.\n\
2055 Optional fourth argument is repeat count--search for successive occurrences.\n\
2057 Search case-sensitivity is determined by the value of the variable\n\
2058 `case-fold-search', which see.\n\
2060 See also the functions `match-beginning', `match-end' and `replace-match'.")
2061 (string
, bound
, noerror
, count
)
2062 Lisp_Object string
, bound
, noerror
, count
;
2064 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2067 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2068 "sWord search backward: ",
2069 "Search backward from point for STRING, ignoring differences in punctuation.\n\
2070 Set point to the beginning of the occurrence found, and return point.\n\
2071 An optional second argument bounds the search; it is a buffer position.\n\
2072 The match found must not extend before that position.\n\
2073 Optional third argument, if t, means if fail just return nil (no error).\n\
2074 If not nil and not t, move to limit of search and return nil.\n\
2075 Optional fourth argument is repeat count--search for successive occurrences.")
2076 (string
, bound
, noerror
, count
)
2077 Lisp_Object string
, bound
, noerror
, count
;
2079 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
2082 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2084 "Search forward from point for STRING, ignoring differences in punctuation.\n\
2085 Set point to the end of the occurrence found, and return point.\n\
2086 An optional second argument bounds the search; it is a buffer position.\n\
2087 The match found must not extend after that position.\n\
2088 Optional third argument, if t, means if fail just return nil (no error).\n\
2089 If not nil and not t, move to limit of search and return nil.\n\
2090 Optional fourth argument is repeat count--search for successive occurrences.")
2091 (string
, bound
, noerror
, count
)
2092 Lisp_Object string
, bound
, noerror
, count
;
2094 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
2097 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2098 "sRE search backward: ",
2099 "Search backward from point for match for regular expression REGEXP.\n\
2100 Set point to the beginning of the match, and return point.\n\
2101 The match found is the one starting last in the buffer\n\
2102 and yet ending before the origin of the search.\n\
2103 An optional second argument bounds the search; it is a buffer position.\n\
2104 The match found must start at or after that position.\n\
2105 Optional third argument, if t, means if fail just return nil (no error).\n\
2106 If not nil and not t, move to limit of search and return nil.\n\
2107 Optional fourth argument is repeat count--search for successive occurrences.\n\
2108 See also the functions `match-beginning', `match-end', `match-string',\n\
2109 and `replace-match'.")
2110 (regexp
, bound
, noerror
, count
)
2111 Lisp_Object regexp
, bound
, noerror
, count
;
2113 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2116 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2118 "Search forward from point for regular expression REGEXP.\n\
2119 Set point to the end of the occurrence found, and return point.\n\
2120 An optional second argument bounds the search; it is a buffer position.\n\
2121 The match found must not extend after that position.\n\
2122 Optional third argument, if t, means if fail just return nil (no error).\n\
2123 If not nil and not t, move to limit of search and return nil.\n\
2124 Optional fourth argument is repeat count--search for successive occurrences.\n\
2125 See also the functions `match-beginning', `match-end', `match-string',\n\
2126 and `replace-match'.")
2127 (regexp
, bound
, noerror
, count
)
2128 Lisp_Object regexp
, bound
, noerror
, count
;
2130 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2133 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2134 "sPosix search backward: ",
2135 "Search backward from point for match for regular expression REGEXP.\n\
2136 Find the longest match in accord with Posix regular expression rules.\n\
2137 Set point to the beginning of the match, and return point.\n\
2138 The match found is the one starting last in the buffer\n\
2139 and yet ending before the origin of the search.\n\
2140 An optional second argument bounds the search; it is a buffer position.\n\
2141 The match found must start at or after that position.\n\
2142 Optional third argument, if t, means if fail just return nil (no error).\n\
2143 If not nil and not t, move to limit of search and return nil.\n\
2144 Optional fourth argument is repeat count--search for successive occurrences.\n\
2145 See also the functions `match-beginning', `match-end', `match-string',\n\
2146 and `replace-match'.")
2147 (regexp
, bound
, noerror
, count
)
2148 Lisp_Object regexp
, bound
, noerror
, count
;
2150 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2153 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2155 "Search forward from point for regular expression REGEXP.\n\
2156 Find the longest match in accord with Posix regular expression rules.\n\
2157 Set point to the end of the occurrence found, and return point.\n\
2158 An optional second argument bounds the search; it is a buffer position.\n\
2159 The match found must not extend after that position.\n\
2160 Optional third argument, if t, means if fail just return nil (no error).\n\
2161 If not nil and not t, move to limit of search and return nil.\n\
2162 Optional fourth argument is repeat count--search for successive occurrences.\n\
2163 See also the functions `match-beginning', `match-end', `match-string',\n\
2164 and `replace-match'.")
2165 (regexp
, bound
, noerror
, count
)
2166 Lisp_Object regexp
, bound
, noerror
, count
;
2168 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2171 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2172 "Replace text matched by last search with NEWTEXT.\n\
2173 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.\n\
2174 Otherwise maybe capitalize the whole text, or maybe just word initials,\n\
2175 based on the replaced text.\n\
2176 If the replaced text has only capital letters\n\
2177 and has at least one multiletter word, convert NEWTEXT to all caps.\n\
2178 If the replaced text has at least one word starting with a capital letter,\n\
2179 then capitalize each word in NEWTEXT.\n\n\
2180 If third arg LITERAL is non-nil, insert NEWTEXT literally.\n\
2181 Otherwise treat `\\' as special:\n\
2182 `\\&' in NEWTEXT means substitute original matched text.\n\
2183 `\\N' means substitute what matched the Nth `\\(...\\)'.\n\
2184 If Nth parens didn't match, substitute nothing.\n\
2185 `\\\\' means insert one `\\'.\n\
2186 FIXEDCASE and LITERAL are optional arguments.\n\
2187 Leaves point at end of replacement text.\n\
2189 The optional fourth argument STRING can be a string to modify.\n\
2190 This is meaningful when the previous match was done against STRING,\n\
2191 using `string-match'. When used this way, `replace-match'\n\
2192 creates and returns a new string made by copying STRING and replacing\n\
2193 the part of STRING that was matched.\n\
2195 The optional fifth argument SUBEXP specifies a subexpression;\n\
2196 it says to replace just that subexpression with NEWTEXT,\n\
2197 rather than replacing the entire matched text.\n\
2198 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;\n\
2199 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts\n\
2200 NEWTEXT in place of subexp N.\n\
2201 This is useful only after a regular expression search or match,\n\
2202 since only regular expressions have distinguished subexpressions.")
2203 (newtext
, fixedcase
, literal
, string
, subexp
)
2204 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2206 enum { nochange
, all_caps
, cap_initial
} case_action
;
2207 register int pos
, pos_byte
;
2208 int some_multiletter_word
;
2211 int some_nonuppercase_initial
;
2212 register int c
, prevc
;
2215 int opoint
, newpoint
;
2217 CHECK_STRING (newtext
, 0);
2219 if (! NILP (string
))
2220 CHECK_STRING (string
, 4);
2222 case_action
= nochange
; /* We tried an initialization */
2223 /* but some C compilers blew it */
2225 if (search_regs
.num_regs
<= 0)
2226 error ("replace-match called before any match found");
2232 CHECK_NUMBER (subexp
, 3);
2233 sub
= XINT (subexp
);
2234 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2235 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2240 if (search_regs
.start
[sub
] < BEGV
2241 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2242 || search_regs
.end
[sub
] > ZV
)
2243 args_out_of_range (make_number (search_regs
.start
[sub
]),
2244 make_number (search_regs
.end
[sub
]));
2248 if (search_regs
.start
[sub
] < 0
2249 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2250 || search_regs
.end
[sub
] > XSTRING (string
)->size
)
2251 args_out_of_range (make_number (search_regs
.start
[sub
]),
2252 make_number (search_regs
.end
[sub
]));
2255 if (NILP (fixedcase
))
2257 /* Decide how to casify by examining the matched text. */
2260 pos
= search_regs
.start
[sub
];
2261 last
= search_regs
.end
[sub
];
2264 pos_byte
= CHAR_TO_BYTE (pos
);
2266 pos_byte
= string_char_to_byte (string
, pos
);
2269 case_action
= all_caps
;
2271 /* some_multiletter_word is set nonzero if any original word
2272 is more than one letter long. */
2273 some_multiletter_word
= 0;
2275 some_nonuppercase_initial
= 0;
2282 c
= FETCH_CHAR (pos_byte
);
2283 INC_BOTH (pos
, pos_byte
);
2286 FETCH_STRING_CHAR_ADVANCE (c
, string
, pos
, pos_byte
);
2290 /* Cannot be all caps if any original char is lower case */
2293 if (SYNTAX (prevc
) != Sword
)
2294 some_nonuppercase_initial
= 1;
2296 some_multiletter_word
= 1;
2298 else if (!NOCASEP (c
))
2301 if (SYNTAX (prevc
) != Sword
)
2304 some_multiletter_word
= 1;
2308 /* If the initial is a caseless word constituent,
2309 treat that like a lowercase initial. */
2310 if (SYNTAX (prevc
) != Sword
)
2311 some_nonuppercase_initial
= 1;
2317 /* Convert to all caps if the old text is all caps
2318 and has at least one multiletter word. */
2319 if (! some_lowercase
&& some_multiletter_word
)
2320 case_action
= all_caps
;
2321 /* Capitalize each word, if the old text has all capitalized words. */
2322 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2323 case_action
= cap_initial
;
2324 else if (!some_nonuppercase_initial
&& some_uppercase
)
2325 /* Should x -> yz, operating on X, give Yz or YZ?
2326 We'll assume the latter. */
2327 case_action
= all_caps
;
2329 case_action
= nochange
;
2332 /* Do replacement in a string. */
2335 Lisp_Object before
, after
;
2337 before
= Fsubstring (string
, make_number (0),
2338 make_number (search_regs
.start
[sub
]));
2339 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2341 /* Substitute parts of the match into NEWTEXT
2346 int lastpos_byte
= 0;
2347 /* We build up the substituted string in ACCUM. */
2350 int length
= STRING_BYTES (XSTRING (newtext
));
2354 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2358 int delbackslash
= 0;
2360 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2364 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2368 substart
= search_regs
.start
[sub
];
2369 subend
= search_regs
.end
[sub
];
2371 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2373 if (search_regs
.start
[c
- '0'] >= 0)
2375 substart
= search_regs
.start
[c
- '0'];
2376 subend
= search_regs
.end
[c
- '0'];
2382 error ("Invalid use of `\\' in replacement text");
2386 if (pos
- 2 != lastpos
)
2387 middle
= substring_both (newtext
, lastpos
,
2389 pos
- 2, pos_byte
- 2);
2392 accum
= concat3 (accum
, middle
,
2394 make_number (substart
),
2395 make_number (subend
)));
2397 lastpos_byte
= pos_byte
;
2399 else if (delbackslash
)
2401 middle
= substring_both (newtext
, lastpos
,
2403 pos
- 1, pos_byte
- 1);
2405 accum
= concat2 (accum
, middle
);
2407 lastpos_byte
= pos_byte
;
2412 middle
= substring_both (newtext
, lastpos
,
2418 newtext
= concat2 (accum
, middle
);
2421 /* Do case substitution in NEWTEXT if desired. */
2422 if (case_action
== all_caps
)
2423 newtext
= Fupcase (newtext
);
2424 else if (case_action
== cap_initial
)
2425 newtext
= Fupcase_initials (newtext
);
2427 return concat3 (before
, newtext
, after
);
2430 /* Record point, then move (quietly) to the start of the match. */
2431 if (PT
>= search_regs
.end
[sub
])
2433 else if (PT
> search_regs
.start
[sub
])
2434 opoint
= search_regs
.end
[sub
] - ZV
;
2438 TEMP_SET_PT (search_regs
.start
[sub
]);
2440 /* We insert the replacement text before the old text, and then
2441 delete the original text. This means that markers at the
2442 beginning or end of the original will float to the corresponding
2443 position in the replacement. */
2444 if (!NILP (literal
))
2445 Finsert_and_inherit (1, &newtext
);
2448 int length
= STRING_BYTES (XSTRING (newtext
));
2449 unsigned char *substed
;
2450 int substed_alloc_size
, substed_len
;
2451 int buf_multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
2452 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2453 Lisp_Object rev_tbl
;
2455 rev_tbl
= (!buf_multibyte
&& CHAR_TABLE_P (Vnonascii_translation_table
)
2456 ? Fchar_table_extra_slot (Vnonascii_translation_table
,
2460 substed_alloc_size
= length
* 2 + 100;
2461 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2464 /* Go thru NEWTEXT, producing the actual text to insert in
2465 SUBSTED while adjusting multibyteness to that of the current
2468 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2470 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2471 unsigned char *add_stuff
= NULL
;
2477 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2479 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2483 /* Note that we don't have to increment POS. */
2484 c
= XSTRING (newtext
)->data
[pos_byte
++];
2486 c
= unibyte_char_to_multibyte (c
);
2489 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2490 or set IDX to a match index, which means put that part
2491 of the buffer text into SUBSTED. */
2497 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2499 if (!buf_multibyte
&& !SINGLE_BYTE_CHAR_P (c
))
2500 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2504 c
= XSTRING (newtext
)->data
[pos_byte
++];
2506 c
= unibyte_char_to_multibyte (c
);
2511 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2513 if (search_regs
.start
[c
- '0'] >= 1)
2517 add_len
= 1, add_stuff
= "\\";
2521 error ("Invalid use of `\\' in replacement text");
2526 add_len
= CHAR_STRING (c
, str
);
2530 /* If we want to copy part of a previous match,
2531 set up ADD_STUFF and ADD_LEN to point to it. */
2534 int begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2535 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2536 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2537 move_gap (search_regs
.start
[idx
]);
2538 add_stuff
= BYTE_POS_ADDR (begbyte
);
2541 /* Now the stuff we want to add to SUBSTED
2542 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2544 /* Make sure SUBSTED is big enough. */
2545 if (substed_len
+ add_len
>= substed_alloc_size
)
2547 substed_alloc_size
= substed_len
+ add_len
+ 500;
2548 substed
= (unsigned char *) xrealloc (substed
,
2549 substed_alloc_size
+ 1);
2552 /* Now add to the end of SUBSTED. */
2555 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2556 substed_len
+= add_len
;
2560 /* Now insert what we accumulated. */
2561 insert_and_inherit (substed
, substed_len
);
2566 inslen
= PT
- (search_regs
.start
[sub
]);
2567 del_range (search_regs
.start
[sub
] + inslen
, search_regs
.end
[sub
] + inslen
);
2569 if (case_action
== all_caps
)
2570 Fupcase_region (make_number (PT
- inslen
), make_number (PT
));
2571 else if (case_action
== cap_initial
)
2572 Fupcase_initials_region (make_number (PT
- inslen
), make_number (PT
));
2576 /* Put point back where it was in the text. */
2578 TEMP_SET_PT (opoint
+ ZV
);
2580 TEMP_SET_PT (opoint
);
2582 /* Now move point "officially" to the start of the inserted replacement. */
2583 move_if_not_intangible (newpoint
);
2589 match_limit (num
, beginningp
)
2595 CHECK_NUMBER (num
, 0);
2597 if (n
< 0 || n
>= search_regs
.num_regs
)
2598 args_out_of_range (num
, make_number (search_regs
.num_regs
));
2599 if (search_regs
.num_regs
<= 0
2600 || search_regs
.start
[n
] < 0)
2602 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2603 : search_regs
.end
[n
]));
2606 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2607 "Return position of start of text matched by last search.\n\
2608 SUBEXP, a number, specifies which parenthesized expression in the last\n\
2610 Value is nil if SUBEXPth pair didn't match, or there were less than\n\
2612 Zero means the entire text matched by the whole regexp or whole string.")
2616 return match_limit (subexp
, 1);
2619 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2620 "Return position of end of text matched by last search.\n\
2621 SUBEXP, a number, specifies which parenthesized expression in the last\n\
2623 Value is nil if SUBEXPth pair didn't match, or there were less than\n\
2625 Zero means the entire text matched by the whole regexp or whole string.")
2629 return match_limit (subexp
, 0);
2632 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 2, 0,
2633 "Return a list containing all info on what the last search matched.\n\
2634 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.\n\
2635 All the elements are markers or nil (nil if the Nth pair didn't match)\n\
2636 if the last match was on a buffer; integers or nil if a string was matched.\n\
2637 Use `store-match-data' to reinstate the data in this list.\n\
2639 If INTEGERS (the optional first argument) is non-nil, always use integers\n\
2640 \(rather than markers) to represent buffer positions.\n\
2641 If REUSE is a list, reuse it as part of the value. If REUSE is long enough\n\
2642 to hold all the values, and if INTEGERS is non-nil, no consing is done.")
2644 Lisp_Object integers
, reuse
;
2646 Lisp_Object tail
, prev
;
2650 if (NILP (last_thing_searched
))
2655 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
)
2656 * sizeof (Lisp_Object
));
2659 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2661 int start
= search_regs
.start
[i
];
2664 if (EQ (last_thing_searched
, Qt
)
2665 || ! NILP (integers
))
2667 XSETFASTINT (data
[2 * i
], start
);
2668 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2670 else if (BUFFERP (last_thing_searched
))
2672 data
[2 * i
] = Fmake_marker ();
2673 Fset_marker (data
[2 * i
],
2674 make_number (start
),
2675 last_thing_searched
);
2676 data
[2 * i
+ 1] = Fmake_marker ();
2677 Fset_marker (data
[2 * i
+ 1],
2678 make_number (search_regs
.end
[i
]),
2679 last_thing_searched
);
2682 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2688 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2691 /* If REUSE is not usable, cons up the values and return them. */
2692 if (! CONSP (reuse
))
2693 return Flist (2 * len
+ 2, data
);
2695 /* If REUSE is a list, store as many value elements as will fit
2696 into the elements of REUSE. */
2697 for (i
= 0, tail
= reuse
; CONSP (tail
);
2698 i
++, tail
= XCDR (tail
))
2700 if (i
< 2 * len
+ 2)
2701 XCAR (tail
) = data
[i
];
2707 /* If we couldn't fit all value elements into REUSE,
2708 cons up the rest of them and add them to the end of REUSE. */
2709 if (i
< 2 * len
+ 2)
2710 XCDR (prev
) = Flist (2 * len
+ 2 - i
, data
+ i
);
2716 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 1, 0,
2717 "Set internal data on last search match from elements of LIST.\n\
2718 LIST should have been created by calling `match-data' previously.")
2720 register Lisp_Object list
;
2723 register Lisp_Object marker
;
2725 if (running_asynch_code
)
2726 save_search_regs ();
2728 if (!CONSP (list
) && !NILP (list
))
2729 list
= wrong_type_argument (Qconsp
, list
);
2731 /* Unless we find a marker with a buffer in LIST, assume that this
2732 match data came from a string. */
2733 last_thing_searched
= Qt
;
2735 /* Allocate registers if they don't already exist. */
2737 int length
= XFASTINT (Flength (list
)) / 2;
2739 if (length
> search_regs
.num_regs
)
2741 if (search_regs
.num_regs
== 0)
2744 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2746 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2751 = (regoff_t
*) xrealloc (search_regs
.start
,
2752 length
* sizeof (regoff_t
));
2754 = (regoff_t
*) xrealloc (search_regs
.end
,
2755 length
* sizeof (regoff_t
));
2758 for (i
= search_regs
.num_regs
; i
< length
; i
++)
2759 search_regs
.start
[i
] = -1;
2761 search_regs
.num_regs
= length
;
2765 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2767 marker
= Fcar (list
);
2770 search_regs
.start
[i
] = -1;
2777 if (MARKERP (marker
))
2779 if (XMARKER (marker
)->buffer
== 0)
2780 XSETFASTINT (marker
, 0);
2782 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2785 CHECK_NUMBER_COERCE_MARKER (marker
, 0);
2786 from
= XINT (marker
);
2789 marker
= Fcar (list
);
2790 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2791 XSETFASTINT (marker
, 0);
2793 CHECK_NUMBER_COERCE_MARKER (marker
, 0);
2794 search_regs
.start
[i
] = from
;
2795 search_regs
.end
[i
] = XINT (marker
);
2803 /* If non-zero the match data have been saved in saved_search_regs
2804 during the execution of a sentinel or filter. */
2805 static int search_regs_saved
;
2806 static struct re_registers saved_search_regs
;
2808 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2809 if asynchronous code (filter or sentinel) is running. */
2813 if (!search_regs_saved
)
2815 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2816 saved_search_regs
.start
= search_regs
.start
;
2817 saved_search_regs
.end
= search_regs
.end
;
2818 search_regs
.num_regs
= 0;
2819 search_regs
.start
= 0;
2820 search_regs
.end
= 0;
2822 search_regs_saved
= 1;
2826 /* Called upon exit from filters and sentinels. */
2828 restore_match_data ()
2830 if (search_regs_saved
)
2832 if (search_regs
.num_regs
> 0)
2834 xfree (search_regs
.start
);
2835 xfree (search_regs
.end
);
2837 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2838 search_regs
.start
= saved_search_regs
.start
;
2839 search_regs
.end
= saved_search_regs
.end
;
2841 search_regs_saved
= 0;
2845 /* Quote a string to inactivate reg-expr chars */
2847 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
2848 "Return a regexp string which matches exactly STRING and nothing else.")
2852 register unsigned char *in
, *out
, *end
;
2853 register unsigned char *temp
;
2854 int backslashes_added
= 0;
2856 CHECK_STRING (string
, 0);
2858 temp
= (unsigned char *) alloca (STRING_BYTES (XSTRING (string
)) * 2);
2860 /* Now copy the data into the new string, inserting escapes. */
2862 in
= XSTRING (string
)->data
;
2863 end
= in
+ STRING_BYTES (XSTRING (string
));
2866 for (; in
!= end
; in
++)
2868 if (*in
== '[' || *in
== ']'
2869 || *in
== '*' || *in
== '.' || *in
== '\\'
2870 || *in
== '?' || *in
== '+'
2871 || *in
== '^' || *in
== '$')
2872 *out
++ = '\\', backslashes_added
++;
2876 return make_specified_string (temp
,
2877 XSTRING (string
)->size
+ backslashes_added
,
2879 STRING_MULTIBYTE (string
));
2887 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
2889 searchbufs
[i
].buf
.allocated
= 100;
2890 searchbufs
[i
].buf
.buffer
= (unsigned char *) malloc (100);
2891 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
2892 searchbufs
[i
].regexp
= Qnil
;
2893 staticpro (&searchbufs
[i
].regexp
);
2894 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
2896 searchbuf_head
= &searchbufs
[0];
2898 Qsearch_failed
= intern ("search-failed");
2899 staticpro (&Qsearch_failed
);
2900 Qinvalid_regexp
= intern ("invalid-regexp");
2901 staticpro (&Qinvalid_regexp
);
2903 Fput (Qsearch_failed
, Qerror_conditions
,
2904 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
2905 Fput (Qsearch_failed
, Qerror_message
,
2906 build_string ("Search failed"));
2908 Fput (Qinvalid_regexp
, Qerror_conditions
,
2909 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
2910 Fput (Qinvalid_regexp
, Qerror_message
,
2911 build_string ("Invalid regexp"));
2913 last_thing_searched
= Qnil
;
2914 staticpro (&last_thing_searched
);
2916 defsubr (&Slooking_at
);
2917 defsubr (&Sposix_looking_at
);
2918 defsubr (&Sstring_match
);
2919 defsubr (&Sposix_string_match
);
2920 defsubr (&Ssearch_forward
);
2921 defsubr (&Ssearch_backward
);
2922 defsubr (&Sword_search_forward
);
2923 defsubr (&Sword_search_backward
);
2924 defsubr (&Sre_search_forward
);
2925 defsubr (&Sre_search_backward
);
2926 defsubr (&Sposix_search_forward
);
2927 defsubr (&Sposix_search_backward
);
2928 defsubr (&Sreplace_match
);
2929 defsubr (&Smatch_beginning
);
2930 defsubr (&Smatch_end
);
2931 defsubr (&Smatch_data
);
2932 defsubr (&Sset_match_data
);
2933 defsubr (&Sregexp_quote
);