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. */
27 #include "character.h"
28 #include "region-cache.h"
30 #include "blockinput.h"
31 #include "intervals.h"
33 #include <sys/types.h>
36 #define REGEXP_CACHE_SIZE 20
38 /* If the regexp is non-nil, then the buffer contains the compiled form
39 of that regexp, suitable for searching. */
42 struct regexp_cache
*next
;
44 struct re_pattern_buffer buf
;
46 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
50 /* The instances of that struct. */
51 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
53 /* The head of the linked list; points to the most recently used buffer. */
54 struct regexp_cache
*searchbuf_head
;
57 /* Every call to re_match, etc., must pass &search_regs as the regs
58 argument unless you can show it is unnecessary (i.e., if re_match
59 is certainly going to be called again before region-around-match
62 Since the registers are now dynamically allocated, we need to make
63 sure not to refer to the Nth register before checking that it has
64 been allocated by checking search_regs.num_regs.
66 The regex code keeps track of whether it has allocated the search
67 buffer using bits in the re_pattern_buffer. This means that whenever
68 you compile a new pattern, it completely forgets whether it has
69 allocated any registers, and will allocate new registers the next
70 time you call a searching or matching function. Therefore, we need
71 to call re_set_registers after compiling a new pattern or after
72 setting the match registers, so that the regex functions will be
73 able to free or re-allocate it properly. */
74 static struct re_registers search_regs
;
76 /* The buffer in which the last search was performed, or
77 Qt if the last search was done in a string;
78 Qnil if no searching has been done yet. */
79 static Lisp_Object last_thing_searched
;
81 /* error condition signaled when regexp compile_pattern fails */
83 Lisp_Object Qinvalid_regexp
;
85 static void set_search_regs ();
86 static void save_search_regs ();
87 static int simple_search ();
88 static int boyer_moore ();
89 static int search_buffer ();
94 error ("Stack overflow in regexp matcher");
97 /* Compile a regexp and signal a Lisp error if anything goes wrong.
98 PATTERN is the pattern to compile.
99 CP is the place to put the result.
100 TRANSLATE is a translation table for ignoring case, or nil for none.
101 REGP is the structure that says where to store the "register"
102 values that will result from matching this pattern.
103 If it is 0, we should compile the pattern not to record any
104 subexpression bounds.
105 POSIX is nonzero if we want full backtracking (POSIX style)
106 for this pattern. 0 means backtrack only enough to get a valid match.
107 MULTIBYTE is nonzero if we want to handle multibyte characters in
108 the target. 0 means all multibyte characters are recognized just as
109 sequences of binary data. */
112 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
113 struct regexp_cache
*cp
;
115 Lisp_Object translate
;
116 struct re_registers
*regp
;
124 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
126 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
127 cp
->buf
.target_multibyte
= multibyte
;
129 old
= re_set_syntax (RE_SYNTAX_EMACS
130 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
131 val
= (char *) re_compile_pattern ((char *) (XSTRING (pattern
)->data
),
132 STRING_BYTES (XSTRING (pattern
)),
137 Fsignal (Qinvalid_regexp
, Fcons (build_string (val
), Qnil
));
139 cp
->regexp
= Fcopy_sequence (pattern
);
142 /* Shrink each compiled regexp buffer in the cache
143 to the size actually used right now.
144 This is called from garbage collection. */
147 shrink_regexp_cache ()
149 struct regexp_cache
*cp
;
151 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
153 cp
->buf
.allocated
= cp
->buf
.used
;
155 = (unsigned char *) realloc (cp
->buf
.buffer
, cp
->buf
.used
);
159 /* Compile a regexp if necessary, but first check to see if there's one in
161 PATTERN is the pattern to compile.
162 TRANSLATE is a translation table for ignoring case, or nil for none.
163 REGP is the structure that says where to store the "register"
164 values that will result from matching this pattern.
165 If it is 0, we should compile the pattern not to record any
166 subexpression bounds.
167 POSIX is nonzero if we want full backtracking (POSIX style)
168 for this pattern. 0 means backtrack only enough to get a valid match. */
170 struct re_pattern_buffer
*
171 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
173 struct re_registers
*regp
;
174 Lisp_Object translate
;
175 int posix
, multibyte
;
177 struct regexp_cache
*cp
, **cpp
;
179 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
182 /* Entries are initialized to nil, and may be set to nil by
183 compile_pattern_1 if the pattern isn't valid. Don't apply
184 XSTRING in those cases. However, compile_pattern_1 is only
185 applied to the cache entry we pick here to reuse. So nil
186 should never appear before a non-nil entry. */
187 if (NILP (cp
->regexp
))
189 if (XSTRING (cp
->regexp
)->size
== XSTRING (pattern
)->size
190 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
191 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
192 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
193 && cp
->posix
== posix
194 && cp
->buf
.target_multibyte
== multibyte
)
197 /* If we're at the end of the cache, compile into the nil cell
198 we found, or the last (least recently used) cell with a
203 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
208 /* When we get here, cp (aka *cpp) contains the compiled pattern,
209 either because we found it in the cache or because we just compiled it.
210 Move it to the front of the queue to mark it as most recently used. */
212 cp
->next
= searchbuf_head
;
215 /* Advise the searching functions about the space we have allocated
216 for register data. */
218 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
223 /* Error condition used for failing searches */
224 Lisp_Object Qsearch_failed
;
230 Fsignal (Qsearch_failed
, Fcons (arg
, Qnil
));
235 looking_at_1 (string
, posix
)
240 unsigned char *p1
, *p2
;
243 struct re_pattern_buffer
*bufp
;
245 if (running_asynch_code
)
248 CHECK_STRING (string
);
249 bufp
= compile_pattern (string
, &search_regs
,
250 (!NILP (current_buffer
->case_fold_search
)
251 ? DOWNCASE_TABLE
: Qnil
),
253 !NILP (current_buffer
->enable_multibyte_characters
));
256 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
258 /* Get pointers and sizes of the two strings
259 that make up the visible portion of the buffer. */
262 s1
= GPT_BYTE
- BEGV_BYTE
;
264 s2
= ZV_BYTE
- GPT_BYTE
;
268 s2
= ZV_BYTE
- BEGV_BYTE
;
273 s1
= ZV_BYTE
- BEGV_BYTE
;
277 re_match_object
= Qnil
;
279 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
280 PT_BYTE
- BEGV_BYTE
, &search_regs
,
281 ZV_BYTE
- BEGV_BYTE
);
287 val
= (0 <= i
? Qt
: Qnil
);
289 for (i
= 0; i
< search_regs
.num_regs
; i
++)
290 if (search_regs
.start
[i
] >= 0)
293 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
295 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
297 XSETBUFFER (last_thing_searched
, current_buffer
);
301 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
302 doc
: /* Return t if text after point matches regular expression REGEXP.
303 This function modifies the match data that `match-beginning',
304 `match-end' and `match-data' access; save and restore the match
305 data if you want to preserve them. */)
309 return looking_at_1 (regexp
, 0);
312 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
313 doc
: /* Return t if text after point matches regular expression REGEXP.
314 Find the longest match, in accord with Posix regular expression rules.
315 This function modifies the match data that `match-beginning',
316 `match-end' and `match-data' access; save and restore the match
317 data if you want to preserve them. */)
321 return looking_at_1 (regexp
, 1);
325 string_match_1 (regexp
, string
, start
, posix
)
326 Lisp_Object regexp
, string
, start
;
330 struct re_pattern_buffer
*bufp
;
334 if (running_asynch_code
)
337 CHECK_STRING (regexp
);
338 CHECK_STRING (string
);
341 pos
= 0, pos_byte
= 0;
344 int len
= XSTRING (string
)->size
;
346 CHECK_NUMBER (start
);
348 if (pos
< 0 && -pos
<= len
)
350 else if (0 > pos
|| pos
> len
)
351 args_out_of_range (string
, start
);
352 pos_byte
= string_char_to_byte (string
, pos
);
355 bufp
= compile_pattern (regexp
, &search_regs
,
356 (!NILP (current_buffer
->case_fold_search
)
357 ? DOWNCASE_TABLE
: Qnil
),
359 STRING_MULTIBYTE (string
));
361 re_match_object
= string
;
363 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
364 STRING_BYTES (XSTRING (string
)), pos_byte
,
365 STRING_BYTES (XSTRING (string
)) - pos_byte
,
368 last_thing_searched
= Qt
;
371 if (val
< 0) return Qnil
;
373 for (i
= 0; i
< search_regs
.num_regs
; i
++)
374 if (search_regs
.start
[i
] >= 0)
377 = string_byte_to_char (string
, search_regs
.start
[i
]);
379 = string_byte_to_char (string
, search_regs
.end
[i
]);
382 return make_number (string_byte_to_char (string
, val
));
385 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
386 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
387 Case is ignored if `case-fold-search' is non-nil in the current buffer.
388 If third arg START is non-nil, start search at that index in STRING.
389 For index of first char beyond the match, do (match-end 0).
390 `match-end' and `match-beginning' also give indices of substrings
391 matched by parenthesis constructs in the pattern. */)
392 (regexp
, string
, start
)
393 Lisp_Object regexp
, string
, start
;
395 return string_match_1 (regexp
, string
, start
, 0);
398 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
399 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
400 Find the longest match, in accord with Posix regular expression rules.
401 Case is ignored if `case-fold-search' is non-nil in the current buffer.
402 If third arg START is non-nil, start search at that index in STRING.
403 For index of first char beyond the match, do (match-end 0).
404 `match-end' and `match-beginning' also give indices of substrings
405 matched by parenthesis constructs in the pattern. */)
406 (regexp
, string
, start
)
407 Lisp_Object regexp
, string
, start
;
409 return string_match_1 (regexp
, string
, start
, 1);
412 /* Match REGEXP against STRING, searching all of STRING,
413 and return the index of the match, or negative on failure.
414 This does not clobber the match data. */
417 fast_string_match (regexp
, string
)
418 Lisp_Object regexp
, string
;
421 struct re_pattern_buffer
*bufp
;
423 bufp
= compile_pattern (regexp
, 0, Qnil
,
424 0, STRING_MULTIBYTE (string
));
426 re_match_object
= string
;
428 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
429 STRING_BYTES (XSTRING (string
)), 0,
430 STRING_BYTES (XSTRING (string
)), 0);
435 /* Match REGEXP against STRING, searching all of STRING ignoring case,
436 and return the index of the match, or negative on failure.
437 This does not clobber the match data.
438 We assume that STRING contains single-byte characters. */
440 extern Lisp_Object Vascii_downcase_table
;
443 fast_c_string_match_ignore_case (regexp
, string
)
448 struct re_pattern_buffer
*bufp
;
449 int len
= strlen (string
);
451 regexp
= string_make_unibyte (regexp
);
452 re_match_object
= Qt
;
453 bufp
= compile_pattern (regexp
, 0,
454 Vascii_downcase_table
, 0,
457 val
= re_search (bufp
, string
, len
, 0, len
, 0);
462 /* The newline cache: remembering which sections of text have no newlines. */
464 /* If the user has requested newline caching, make sure it's on.
465 Otherwise, make sure it's off.
466 This is our cheezy way of associating an action with the change of
467 state of a buffer-local variable. */
469 newline_cache_on_off (buf
)
472 if (NILP (buf
->cache_long_line_scans
))
474 /* It should be off. */
475 if (buf
->newline_cache
)
477 free_region_cache (buf
->newline_cache
);
478 buf
->newline_cache
= 0;
483 /* It should be on. */
484 if (buf
->newline_cache
== 0)
485 buf
->newline_cache
= new_region_cache ();
490 /* Search for COUNT instances of the character TARGET between START and END.
492 If COUNT is positive, search forwards; END must be >= START.
493 If COUNT is negative, search backwards for the -COUNTth instance;
494 END must be <= START.
495 If COUNT is zero, do anything you please; run rogue, for all I care.
497 If END is zero, use BEGV or ZV instead, as appropriate for the
498 direction indicated by COUNT.
500 If we find COUNT instances, set *SHORTAGE to zero, and return the
501 position after the COUNTth match. Note that for reverse motion
502 this is not the same as the usual convention for Emacs motion commands.
504 If we don't find COUNT instances before reaching END, set *SHORTAGE
505 to the number of TARGETs left unfound, and return END.
507 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
508 except when inside redisplay. */
511 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
518 struct region_cache
*newline_cache
;
529 if (! end
) end
= BEGV
;
532 newline_cache_on_off (current_buffer
);
533 newline_cache
= current_buffer
->newline_cache
;
538 immediate_quit
= allow_quit
;
543 /* Our innermost scanning loop is very simple; it doesn't know
544 about gaps, buffer ends, or the newline cache. ceiling is
545 the position of the last character before the next such
546 obstacle --- the last character the dumb search loop should
548 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
549 int start_byte
= CHAR_TO_BYTE (start
);
552 /* If we're looking for a newline, consult the newline cache
553 to see where we can avoid some scanning. */
554 if (target
== '\n' && newline_cache
)
558 while (region_cache_forward
559 (current_buffer
, newline_cache
, start_byte
, &next_change
))
560 start_byte
= next_change
;
561 immediate_quit
= allow_quit
;
563 /* START should never be after END. */
564 if (start_byte
> ceiling_byte
)
565 start_byte
= ceiling_byte
;
567 /* Now the text after start is an unknown region, and
568 next_change is the position of the next known region. */
569 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
572 /* The dumb loop can only scan text stored in contiguous
573 bytes. BUFFER_CEILING_OF returns the last character
574 position that is contiguous, so the ceiling is the
575 position after that. */
576 tem
= BUFFER_CEILING_OF (start_byte
);
577 ceiling_byte
= min (tem
, ceiling_byte
);
580 /* The termination address of the dumb loop. */
581 register unsigned char *ceiling_addr
582 = BYTE_POS_ADDR (ceiling_byte
) + 1;
583 register unsigned char *cursor
584 = BYTE_POS_ADDR (start_byte
);
585 unsigned char *base
= cursor
;
587 while (cursor
< ceiling_addr
)
589 unsigned char *scan_start
= cursor
;
592 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
595 /* If we're looking for newlines, cache the fact that
596 the region from start to cursor is free of them. */
597 if (target
== '\n' && newline_cache
)
598 know_region_cache (current_buffer
, newline_cache
,
599 start_byte
+ scan_start
- base
,
600 start_byte
+ cursor
- base
);
602 /* Did we find the target character? */
603 if (cursor
< ceiling_addr
)
608 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
614 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
620 /* The last character to check before the next obstacle. */
621 int ceiling_byte
= CHAR_TO_BYTE (end
);
622 int start_byte
= CHAR_TO_BYTE (start
);
625 /* Consult the newline cache, if appropriate. */
626 if (target
== '\n' && newline_cache
)
630 while (region_cache_backward
631 (current_buffer
, newline_cache
, start_byte
, &next_change
))
632 start_byte
= next_change
;
633 immediate_quit
= allow_quit
;
635 /* Start should never be at or before end. */
636 if (start_byte
<= ceiling_byte
)
637 start_byte
= ceiling_byte
+ 1;
639 /* Now the text before start is an unknown region, and
640 next_change is the position of the next known region. */
641 ceiling_byte
= max (next_change
, ceiling_byte
);
644 /* Stop scanning before the gap. */
645 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
646 ceiling_byte
= max (tem
, ceiling_byte
);
649 /* The termination address of the dumb loop. */
650 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
651 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
652 unsigned char *base
= cursor
;
654 while (cursor
>= ceiling_addr
)
656 unsigned char *scan_start
= cursor
;
658 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
661 /* If we're looking for newlines, cache the fact that
662 the region from after the cursor to start is free of them. */
663 if (target
== '\n' && newline_cache
)
664 know_region_cache (current_buffer
, newline_cache
,
665 start_byte
+ cursor
- base
,
666 start_byte
+ scan_start
- base
);
668 /* Did we find the target character? */
669 if (cursor
>= ceiling_addr
)
674 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
680 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
686 *shortage
= count
* direction
;
690 /* Search for COUNT instances of a line boundary, which means either a
691 newline or (if selective display enabled) a carriage return.
692 Start at START. If COUNT is negative, search backwards.
694 We report the resulting position by calling TEMP_SET_PT_BOTH.
696 If we find COUNT instances. we position after (always after,
697 even if scanning backwards) the COUNTth match, and return 0.
699 If we don't find COUNT instances before reaching the end of the
700 buffer (or the beginning, if scanning backwards), we return
701 the number of line boundaries left unfound, and position at
702 the limit we bumped up against.
704 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
705 except in special cases. */
708 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
709 int start
, start_byte
;
710 int limit
, limit_byte
;
714 int direction
= ((count
> 0) ? 1 : -1);
716 register unsigned char *cursor
;
719 register int ceiling
;
720 register unsigned char *ceiling_addr
;
722 int old_immediate_quit
= immediate_quit
;
724 /* The code that follows is like scan_buffer
725 but checks for either newline or carriage return. */
730 start_byte
= CHAR_TO_BYTE (start
);
734 while (start_byte
< limit_byte
)
736 ceiling
= BUFFER_CEILING_OF (start_byte
);
737 ceiling
= min (limit_byte
- 1, ceiling
);
738 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
739 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
742 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
745 if (cursor
!= ceiling_addr
)
749 immediate_quit
= old_immediate_quit
;
750 start_byte
= start_byte
+ cursor
- base
+ 1;
751 start
= BYTE_TO_CHAR (start_byte
);
752 TEMP_SET_PT_BOTH (start
, start_byte
);
756 if (++cursor
== ceiling_addr
)
762 start_byte
+= cursor
- base
;
767 while (start_byte
> limit_byte
)
769 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
770 ceiling
= max (limit_byte
, ceiling
);
771 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
772 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
775 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
778 if (cursor
!= ceiling_addr
)
782 immediate_quit
= old_immediate_quit
;
783 /* Return the position AFTER the match we found. */
784 start_byte
= start_byte
+ cursor
- base
+ 1;
785 start
= BYTE_TO_CHAR (start_byte
);
786 TEMP_SET_PT_BOTH (start
, start_byte
);
793 /* Here we add 1 to compensate for the last decrement
794 of CURSOR, which took it past the valid range. */
795 start_byte
+= cursor
- base
+ 1;
799 TEMP_SET_PT_BOTH (limit
, limit_byte
);
800 immediate_quit
= old_immediate_quit
;
802 return count
* direction
;
806 find_next_newline_no_quit (from
, cnt
)
807 register int from
, cnt
;
809 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
812 /* Like find_next_newline, but returns position before the newline,
813 not after, and only search up to TO. This isn't just
814 find_next_newline (...)-1, because you might hit TO. */
817 find_before_next_newline (from
, to
, cnt
)
821 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
829 /* Subroutines of Lisp buffer search functions. */
832 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
833 Lisp_Object string
, bound
, noerror
, count
;
844 CHECK_NUMBER (count
);
848 CHECK_STRING (string
);
852 lim
= ZV
, lim_byte
= ZV_BYTE
;
854 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
858 CHECK_NUMBER_COERCE_MARKER (bound
);
860 if (n
> 0 ? lim
< PT
: lim
> PT
)
861 error ("Invalid search bound (wrong side of point)");
863 lim
= ZV
, lim_byte
= ZV_BYTE
;
865 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
867 lim_byte
= CHAR_TO_BYTE (lim
);
870 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
871 (!NILP (current_buffer
->case_fold_search
)
872 ? current_buffer
->case_canon_table
874 (!NILP (current_buffer
->case_fold_search
)
875 ? current_buffer
->case_eqv_table
881 return signal_failure (string
);
882 if (!EQ (noerror
, Qt
))
884 if (lim
< BEGV
|| lim
> ZV
)
886 SET_PT_BOTH (lim
, lim_byte
);
888 #if 0 /* This would be clean, but maybe programs depend on
889 a value of nil here. */
897 if (np
< BEGV
|| np
> ZV
)
902 return make_number (np
);
905 /* Return 1 if REGEXP it matches just one constant string. */
908 trivial_regexp_p (regexp
)
911 int len
= STRING_BYTES (XSTRING (regexp
));
912 unsigned char *s
= XSTRING (regexp
)->data
;
917 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
924 case '|': case '(': case ')': case '`': case '\'': case 'b':
925 case 'B': case '<': case '>': case 'w': case 'W': case 's':
926 case 'S': case '=': case '{': case '}':
927 case 'c': case 'C': /* for categoryspec and notcategoryspec */
928 case '1': case '2': case '3': case '4': case '5':
929 case '6': case '7': case '8': case '9':
937 /* Search for the n'th occurrence of STRING in the current buffer,
938 starting at position POS and stopping at position LIM,
939 treating STRING as a literal string if RE is false or as
940 a regular expression if RE is true.
942 If N is positive, searching is forward and LIM must be greater than POS.
943 If N is negative, searching is backward and LIM must be less than POS.
945 Returns -x if x occurrences remain to be found (x > 0),
946 or else the position at the beginning of the Nth occurrence
947 (if searching backward) or the end (if searching forward).
949 POSIX is nonzero if we want full backtracking (POSIX style)
950 for this pattern. 0 means backtrack only enough to get a valid match. */
952 #define TRANSLATE(out, trt, d) \
958 temp = Faref (trt, make_number (d)); \
959 if (INTEGERP (temp)) \
970 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
971 RE
, trt
, inverse_trt
, posix
)
980 Lisp_Object inverse_trt
;
983 int len
= XSTRING (string
)->size
;
984 int len_byte
= STRING_BYTES (XSTRING (string
));
987 if (running_asynch_code
)
990 /* Searching 0 times means don't move. */
991 /* Null string is found at starting position. */
992 if (len
== 0 || n
== 0)
994 set_search_regs (pos_byte
, 0);
998 if (RE
&& !trivial_regexp_p (string
))
1000 unsigned char *p1
, *p2
;
1002 struct re_pattern_buffer
*bufp
;
1004 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
,
1005 !NILP (current_buffer
->enable_multibyte_characters
));
1007 immediate_quit
= 1; /* Quit immediately if user types ^G,
1008 because letting this function finish
1009 can take too long. */
1010 QUIT
; /* Do a pending quit right away,
1011 to avoid paradoxical behavior */
1012 /* Get pointers and sizes of the two strings
1013 that make up the visible portion of the buffer. */
1016 s1
= GPT_BYTE
- BEGV_BYTE
;
1018 s2
= ZV_BYTE
- GPT_BYTE
;
1022 s2
= ZV_BYTE
- BEGV_BYTE
;
1027 s1
= ZV_BYTE
- BEGV_BYTE
;
1030 re_match_object
= Qnil
;
1035 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1036 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1038 /* Don't allow match past current point */
1039 pos_byte
- BEGV_BYTE
);
1042 matcher_overflow ();
1046 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1047 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1048 if (search_regs
.start
[i
] >= 0)
1050 search_regs
.start
[i
]
1051 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1053 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1055 XSETBUFFER (last_thing_searched
, current_buffer
);
1056 /* Set pos to the new position. */
1057 pos
= search_regs
.start
[0];
1069 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1070 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1072 lim_byte
- BEGV_BYTE
);
1075 matcher_overflow ();
1079 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1080 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1081 if (search_regs
.start
[i
] >= 0)
1083 search_regs
.start
[i
]
1084 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1086 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1088 XSETBUFFER (last_thing_searched
, current_buffer
);
1089 pos
= search_regs
.end
[0];
1101 else /* non-RE case */
1103 unsigned char *raw_pattern
, *pat
;
1104 int raw_pattern_size
;
1105 int raw_pattern_size_byte
;
1106 unsigned char *patbuf
;
1107 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1108 unsigned char *base_pat
= XSTRING (string
)->data
;
1109 /* High bits of char, calculated by (CHAR & 0x3F). Characters
1110 of the same high bits have the same sequence of bytes but
1111 last. To do the BM search, all characters in STRING must
1112 have the same high bits (including their case
1114 int char_high_bits
= -1;
1115 int boyer_moore_ok
= 1;
1117 /* MULTIBYTE says whether the text to be searched is multibyte.
1118 We must convert PATTERN to match that, or we will not really
1119 find things right. */
1121 if (multibyte
== STRING_MULTIBYTE (string
))
1123 raw_pattern
= (unsigned char *) XSTRING (string
)->data
;
1124 raw_pattern_size
= XSTRING (string
)->size
;
1125 raw_pattern_size_byte
= STRING_BYTES (XSTRING (string
));
1129 raw_pattern_size
= XSTRING (string
)->size
;
1130 raw_pattern_size_byte
1131 = count_size_as_multibyte (XSTRING (string
)->data
,
1133 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1134 copy_text (XSTRING (string
)->data
, raw_pattern
,
1135 XSTRING (string
)->size
, 0, 1);
1139 /* Converting multibyte to single-byte.
1141 ??? Perhaps this conversion should be done in a special way
1142 by subtracting nonascii-insert-offset from each non-ASCII char,
1143 so that only the multibyte chars which really correspond to
1144 the chosen single-byte character set can possibly match. */
1145 raw_pattern_size
= XSTRING (string
)->size
;
1146 raw_pattern_size_byte
= XSTRING (string
)->size
;
1147 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1148 copy_text (XSTRING (string
)->data
, raw_pattern
,
1149 STRING_BYTES (XSTRING (string
)), 1, 0);
1152 /* Copy and optionally translate the pattern. */
1153 len
= raw_pattern_size
;
1154 len_byte
= raw_pattern_size_byte
;
1155 patbuf
= (unsigned char *) alloca (len
* MAX_MULTIBYTE_LENGTH
);
1157 base_pat
= raw_pattern
;
1162 int c
, translated
, inverse
;
1165 /* If we got here and the RE flag is set, it's because we're
1166 dealing with a regexp known to be trivial, so the backslash
1167 just quotes the next character. */
1168 if (RE
&& *base_pat
== '\\')
1175 c
= STRING_CHAR_AND_LENGTH (base_pat
, len_byte
, in_charlen
);
1177 /* Translate the character, if requested. */
1178 TRANSLATE (translated
, trt
, c
);
1179 TRANSLATE (inverse
, inverse_trt
, c
);
1181 /* Did this char actually get translated?
1182 Would any other char get translated into it? */
1183 if (translated
!= c
|| inverse
!= c
)
1185 /* Keep track of which character set row
1186 contains the characters that need translation. */
1187 int this_high_bit
= c
& ~0x3F;
1188 int trt_high_bit
= ((inverse
!= c
? inverse
: translated
)
1191 if (this_high_bit
!= trt_high_bit
)
1193 else if (char_high_bits
== -1)
1194 char_high_bits
= this_high_bit
;
1195 else if (char_high_bits
!= this_high_bit
)
1196 /* If two different rows appear, needing translation,
1197 then we cannot use boyer_moore search. */
1201 /* Store this character into the translated pattern. */
1202 CHAR_STRING_ADVANCE (translated
, pat
);
1203 base_pat
+= in_charlen
;
1204 len_byte
-= in_charlen
;
1209 /* Unibyte buffer. */
1215 /* If we got here and the RE flag is set, it's because we're
1216 dealing with a regexp known to be trivial, so the backslash
1217 just quotes the next character. */
1218 if (RE
&& *base_pat
== '\\')
1224 TRANSLATE (translated
, trt
, c
);
1225 *pat
++ = translated
;
1229 len_byte
= pat
- patbuf
;
1230 len
= raw_pattern_size
;
1231 pat
= base_pat
= patbuf
;
1234 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1235 pos
, pos_byte
, lim
, lim_byte
,
1238 return simple_search (n
, pat
, len
, len_byte
, trt
,
1239 pos
, pos_byte
, lim
, lim_byte
);
1243 /* Do a simple string search N times for the string PAT,
1244 whose length is LEN/LEN_BYTE,
1245 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1246 TRT is the translation table.
1248 Return the character position where the match is found.
1249 Otherwise, if M matches remained to be found, return -M.
1251 This kind of search works regardless of what is in PAT and
1252 regardless of what is in TRT. It is used in cases where
1253 boyer_moore cannot work. */
1256 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1264 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1265 int forward
= n
> 0;
1267 if (lim
> pos
&& multibyte
)
1272 /* Try matching at position POS. */
1274 int this_pos_byte
= pos_byte
;
1276 int this_len_byte
= len_byte
;
1277 unsigned char *p
= pat
;
1278 if (pos
+ len
> lim
)
1281 while (this_len
> 0)
1283 int charlen
, buf_charlen
;
1286 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1287 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1288 ZV_BYTE
- this_pos_byte
,
1290 TRANSLATE (buf_ch
, trt
, buf_ch
);
1292 if (buf_ch
!= pat_ch
)
1295 this_len_byte
-= charlen
;
1299 this_pos_byte
+= buf_charlen
;
1306 pos_byte
+= len_byte
;
1310 INC_BOTH (pos
, pos_byte
);
1320 /* Try matching at position POS. */
1323 unsigned char *p
= pat
;
1325 if (pos
+ len
> lim
)
1328 while (this_len
> 0)
1331 int buf_ch
= FETCH_BYTE (this_pos
);
1332 TRANSLATE (buf_ch
, trt
, buf_ch
);
1334 if (buf_ch
!= pat_ch
)
1352 /* Backwards search. */
1353 else if (lim
< pos
&& multibyte
)
1358 /* Try matching at position POS. */
1359 int this_pos
= pos
- len
;
1360 int this_pos_byte
= pos_byte
- len_byte
;
1362 int this_len_byte
= len_byte
;
1363 unsigned char *p
= pat
;
1365 if (pos
- len
< lim
)
1368 while (this_len
> 0)
1370 int charlen
, buf_charlen
;
1373 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1374 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1375 ZV_BYTE
- this_pos_byte
,
1377 TRANSLATE (buf_ch
, trt
, buf_ch
);
1379 if (buf_ch
!= pat_ch
)
1382 this_len_byte
-= charlen
;
1385 this_pos_byte
+= buf_charlen
;
1392 pos_byte
-= len_byte
;
1396 DEC_BOTH (pos
, pos_byte
);
1406 /* Try matching at position POS. */
1407 int this_pos
= pos
- len
;
1409 unsigned char *p
= pat
;
1411 if (pos
- len
< lim
)
1414 while (this_len
> 0)
1417 int buf_ch
= FETCH_BYTE (this_pos
);
1418 TRANSLATE (buf_ch
, trt
, buf_ch
);
1420 if (buf_ch
!= pat_ch
)
1442 set_search_regs ((multibyte
? pos_byte
: pos
) - len_byte
, len_byte
);
1444 set_search_regs (multibyte
? pos_byte
: pos
, len_byte
);
1454 /* Do Boyer-Moore search N times for the string PAT,
1455 whose length is LEN/LEN_BYTE,
1456 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1457 DIRECTION says which direction we search in.
1458 TRT and INVERSE_TRT are translation tables.
1460 This kind of search works if all the characters in PAT that have
1461 nontrivial translation are the same aside from the last byte. This
1462 makes it possible to translate just the last byte of a character,
1463 and do so after just a simple test of the context.
1465 If that criterion is not satisfied, do not call this function. */
1468 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1469 pos
, pos_byte
, lim
, lim_byte
, char_high_bits
)
1471 unsigned char *base_pat
;
1474 Lisp_Object inverse_trt
;
1479 int direction
= ((n
> 0) ? 1 : -1);
1480 register int dirlen
;
1481 int infinity
, limit
, stride_for_teases
= 0;
1482 register int *BM_tab
;
1484 register unsigned char *cursor
, *p_limit
;
1486 unsigned char *pat
, *pat_end
;
1487 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1489 unsigned char simple_translate
[0400];
1490 int translate_prev_byte
= 0;
1491 int translate_anteprev_byte
= 0;
1494 int BM_tab_space
[0400];
1495 BM_tab
= &BM_tab_space
[0];
1497 BM_tab
= (int *) alloca (0400 * sizeof (int));
1499 /* The general approach is that we are going to maintain that we know */
1500 /* the first (closest to the present position, in whatever direction */
1501 /* we're searching) character that could possibly be the last */
1502 /* (furthest from present position) character of a valid match. We */
1503 /* advance the state of our knowledge by looking at that character */
1504 /* and seeing whether it indeed matches the last character of the */
1505 /* pattern. If it does, we take a closer look. If it does not, we */
1506 /* move our pointer (to putative last characters) as far as is */
1507 /* logically possible. This amount of movement, which I call a */
1508 /* stride, will be the length of the pattern if the actual character */
1509 /* appears nowhere in the pattern, otherwise it will be the distance */
1510 /* from the last occurrence of that character to the end of the */
1512 /* As a coding trick, an enormous stride is coded into the table for */
1513 /* characters that match the last character. This allows use of only */
1514 /* a single test, a test for having gone past the end of the */
1515 /* permissible match region, to test for both possible matches (when */
1516 /* the stride goes past the end immediately) and failure to */
1517 /* match (where you get nudged past the end one stride at a time). */
1519 /* Here we make a "mickey mouse" BM table. The stride of the search */
1520 /* is determined only by the last character of the putative match. */
1521 /* If that character does not match, we will stride the proper */
1522 /* distance to propose a match that superimposes it on the last */
1523 /* instance of a character that matches it (per trt), or misses */
1524 /* it entirely if there is none. */
1526 dirlen
= len_byte
* direction
;
1527 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1529 /* Record position after the end of the pattern. */
1530 pat_end
= base_pat
+ len_byte
;
1531 /* BASE_PAT points to a character that we start scanning from.
1532 It is the first character in a forward search,
1533 the last character in a backward search. */
1535 base_pat
= pat_end
- 1;
1537 BM_tab_base
= BM_tab
;
1539 j
= dirlen
; /* to get it in a register */
1540 /* A character that does not appear in the pattern induces a */
1541 /* stride equal to the pattern length. */
1542 while (BM_tab_base
!= BM_tab
)
1550 /* We use this for translation, instead of TRT itself.
1551 We fill this in to handle the characters that actually
1552 occur in the pattern. Others don't matter anyway! */
1553 bzero (simple_translate
, sizeof simple_translate
);
1554 for (i
= 0; i
< 0400; i
++)
1555 simple_translate
[i
] = i
;
1558 while (i
!= infinity
)
1560 unsigned char *ptr
= base_pat
+ i
;
1568 int this_translated
= 1;
1571 /* Is *PTR the last byte of a character? */
1572 && (pat_end
- ptr
== 1 || CHAR_HEAD_P (ptr
[1])))
1574 unsigned char *charstart
= ptr
;
1575 while (! CHAR_HEAD_P (*charstart
))
1577 untranslated
= STRING_CHAR (charstart
, ptr
- charstart
+ 1);
1578 if (char_high_bits
== (untranslated
& ~0x3F))
1580 TRANSLATE (ch
, trt
, untranslated
);
1581 if (! CHAR_HEAD_P (*ptr
))
1583 translate_prev_byte
= ptr
[-1];
1584 if (! CHAR_HEAD_P (translate_prev_byte
))
1585 translate_anteprev_byte
= ptr
[-2];
1590 this_translated
= 0;
1594 else if (!multibyte
)
1595 TRANSLATE (ch
, trt
, *ptr
);
1599 this_translated
= 0;
1604 j
= (ch
& 0x3F) | 0200;
1606 j
= (unsigned char) ch
;
1609 stride_for_teases
= BM_tab
[j
];
1611 BM_tab
[j
] = dirlen
- i
;
1612 /* A translation table is accompanied by its inverse -- see */
1613 /* comment following downcase_table for details */
1614 if (this_translated
)
1616 int starting_ch
= ch
;
1620 TRANSLATE (ch
, inverse_trt
, ch
);
1622 j
= (ch
& 0x3F) | 0200;
1624 j
= (unsigned char) ch
;
1626 /* For all the characters that map into CH,
1627 set up simple_translate to map the last byte
1629 simple_translate
[j
] = starting_j
;
1630 if (ch
== starting_ch
)
1632 BM_tab
[j
] = dirlen
- i
;
1641 stride_for_teases
= BM_tab
[j
];
1642 BM_tab
[j
] = dirlen
- i
;
1644 /* stride_for_teases tells how much to stride if we get a */
1645 /* match on the far character but are subsequently */
1646 /* disappointed, by recording what the stride would have been */
1647 /* for that character if the last character had been */
1650 infinity
= dirlen
- infinity
;
1651 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1652 /* loop invariant - POS_BYTE points at where last char (first
1653 char if reverse) of pattern would align in a possible match. */
1657 unsigned char *tail_end_ptr
;
1659 /* It's been reported that some (broken) compiler thinks that
1660 Boolean expressions in an arithmetic context are unsigned.
1661 Using an explicit ?1:0 prevents this. */
1662 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1664 return (n
* (0 - direction
));
1665 /* First we do the part we can by pointers (maybe nothing) */
1668 limit
= pos_byte
- dirlen
+ direction
;
1671 limit
= BUFFER_CEILING_OF (limit
);
1672 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1673 can take on without hitting edge of buffer or the gap. */
1674 limit
= min (limit
, pos_byte
+ 20000);
1675 limit
= min (limit
, lim_byte
- 1);
1679 limit
= BUFFER_FLOOR_OF (limit
);
1680 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1681 can take on without hitting edge of buffer or the gap. */
1682 limit
= max (limit
, pos_byte
- 20000);
1683 limit
= max (limit
, lim_byte
);
1685 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1686 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1688 if ((limit
- pos_byte
) * direction
> 20)
1692 p_limit
= BYTE_POS_ADDR (limit
);
1693 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1694 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1695 while (1) /* use one cursor setting as long as i can */
1697 if (direction
> 0) /* worth duplicating */
1699 /* Use signed comparison if appropriate
1700 to make cursor+infinity sure to be > p_limit.
1701 Assuming that the buffer lies in a range of addresses
1702 that are all "positive" (as ints) or all "negative",
1703 either kind of comparison will work as long
1704 as we don't step by infinity. So pick the kind
1705 that works when we do step by infinity. */
1706 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1707 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1708 cursor
+= BM_tab
[*cursor
];
1710 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1711 cursor
+= BM_tab
[*cursor
];
1715 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1716 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1717 cursor
+= BM_tab
[*cursor
];
1719 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1720 cursor
+= BM_tab
[*cursor
];
1722 /* If you are here, cursor is beyond the end of the searched region. */
1723 /* This can happen if you match on the far character of the pattern, */
1724 /* because the "stride" of that character is infinity, a number able */
1725 /* to throw you well beyond the end of the search. It can also */
1726 /* happen if you fail to match within the permitted region and would */
1727 /* otherwise try a character beyond that region */
1728 if ((cursor
- p_limit
) * direction
<= len_byte
)
1729 break; /* a small overrun is genuine */
1730 cursor
-= infinity
; /* large overrun = hit */
1731 i
= dirlen
- direction
;
1734 while ((i
-= direction
) + direction
!= 0)
1737 cursor
-= direction
;
1738 /* Translate only the last byte of a character. */
1740 || ((cursor
== tail_end_ptr
1741 || CHAR_HEAD_P (cursor
[1]))
1742 && (CHAR_HEAD_P (cursor
[0])
1743 || (translate_prev_byte
== cursor
[-1]
1744 && (CHAR_HEAD_P (translate_prev_byte
)
1745 || translate_anteprev_byte
== cursor
[-2])))))
1746 ch
= simple_translate
[*cursor
];
1755 while ((i
-= direction
) + direction
!= 0)
1757 cursor
-= direction
;
1758 if (pat
[i
] != *cursor
)
1762 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1763 if (i
+ direction
== 0)
1767 cursor
-= direction
;
1769 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1770 ? 1 - len_byte
: 0);
1771 set_search_regs (position
, len_byte
);
1773 if ((n
-= direction
) != 0)
1774 cursor
+= dirlen
; /* to resume search */
1776 return ((direction
> 0)
1777 ? search_regs
.end
[0] : search_regs
.start
[0]);
1780 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1782 pos_byte
+= cursor
- p2
;
1785 /* Now we'll pick up a clump that has to be done the hard */
1786 /* way because it covers a discontinuity */
1788 limit
= ((direction
> 0)
1789 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1790 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1791 limit
= ((direction
> 0)
1792 ? min (limit
+ len_byte
, lim_byte
- 1)
1793 : max (limit
- len_byte
, lim_byte
));
1794 /* LIMIT is now the last value POS_BYTE can have
1795 and still be valid for a possible match. */
1798 /* This loop can be coded for space rather than */
1799 /* speed because it will usually run only once. */
1800 /* (the reach is at most len + 21, and typically */
1801 /* does not exceed len) */
1802 while ((limit
- pos_byte
) * direction
>= 0)
1803 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
1804 /* now run the same tests to distinguish going off the */
1805 /* end, a match or a phony match. */
1806 if ((pos_byte
- limit
) * direction
<= len_byte
)
1807 break; /* ran off the end */
1808 /* Found what might be a match.
1809 Set POS_BYTE back to last (first if reverse) pos. */
1810 pos_byte
-= infinity
;
1811 i
= dirlen
- direction
;
1812 while ((i
-= direction
) + direction
!= 0)
1816 pos_byte
-= direction
;
1817 ptr
= BYTE_POS_ADDR (pos_byte
);
1818 /* Translate only the last byte of a character. */
1820 || ((ptr
== tail_end_ptr
1821 || CHAR_HEAD_P (ptr
[1]))
1822 && (CHAR_HEAD_P (ptr
[0])
1823 || (translate_prev_byte
== ptr
[-1]
1824 && (CHAR_HEAD_P (translate_prev_byte
)
1825 || translate_anteprev_byte
== ptr
[-2])))))
1826 ch
= simple_translate
[*ptr
];
1832 /* Above loop has moved POS_BYTE part or all the way
1833 back to the first pos (last pos if reverse).
1834 Set it once again at the last (first if reverse) char. */
1835 pos_byte
+= dirlen
- i
- direction
;
1836 if (i
+ direction
== 0)
1839 pos_byte
-= direction
;
1841 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
1843 set_search_regs (position
, len_byte
);
1845 if ((n
-= direction
) != 0)
1846 pos_byte
+= dirlen
; /* to resume search */
1848 return ((direction
> 0)
1849 ? search_regs
.end
[0] : search_regs
.start
[0]);
1852 pos_byte
+= stride_for_teases
;
1855 /* We have done one clump. Can we continue? */
1856 if ((lim_byte
- pos_byte
) * direction
< 0)
1857 return ((0 - n
) * direction
);
1859 return BYTE_TO_CHAR (pos_byte
);
1862 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
1863 for the overall match just found in the current buffer.
1864 Also clear out the match data for registers 1 and up. */
1867 set_search_regs (beg_byte
, nbytes
)
1868 int beg_byte
, nbytes
;
1872 /* Make sure we have registers in which to store
1873 the match position. */
1874 if (search_regs
.num_regs
== 0)
1876 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1877 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1878 search_regs
.num_regs
= 2;
1881 /* Clear out the other registers. */
1882 for (i
= 1; i
< search_regs
.num_regs
; i
++)
1884 search_regs
.start
[i
] = -1;
1885 search_regs
.end
[i
] = -1;
1888 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
1889 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
1890 XSETBUFFER (last_thing_searched
, current_buffer
);
1893 /* Given a string of words separated by word delimiters,
1894 compute a regexp that matches those exact words
1895 separated by arbitrary punctuation. */
1901 register unsigned char *p
, *o
;
1902 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
1907 CHECK_STRING (string
);
1908 p
= XSTRING (string
)->data
;
1909 len
= XSTRING (string
)->size
;
1911 for (i
= 0, i_byte
= 0; i
< len
; )
1915 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
1917 if (SYNTAX (c
) != Sword
)
1920 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
1927 if (SYNTAX (prev_c
) == Sword
)
1930 return empty_string
;
1932 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
1933 if (STRING_MULTIBYTE (string
))
1934 val
= make_uninit_multibyte_string (len
+ adjust
,
1935 STRING_BYTES (XSTRING (string
))
1938 val
= make_uninit_string (len
+ adjust
);
1940 o
= XSTRING (val
)->data
;
1945 for (i
= 0, i_byte
= 0; i
< len
; )
1948 int i_byte_orig
= i_byte
;
1950 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, i
, i_byte
);
1952 if (SYNTAX (c
) == Sword
)
1954 bcopy (&XSTRING (string
)->data
[i_byte_orig
], o
,
1955 i_byte
- i_byte_orig
);
1956 o
+= i_byte
- i_byte_orig
;
1958 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
1976 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
1977 "MSearch backward: ",
1978 doc
: /* Search backward from point for STRING.
1979 Set point to the beginning of the occurrence found, and return point.
1980 An optional second argument bounds the search; it is a buffer position.
1981 The match found must not extend before that position.
1982 Optional third argument, if t, means if fail just return nil (no error).
1983 If not nil and not t, position at limit of search and return nil.
1984 Optional fourth argument is repeat count--search for successive occurrences.
1986 Search case-sensitivity is determined by the value of the variable
1987 `case-fold-search', which see.
1989 See also the functions `match-beginning', `match-end' and `replace-match'. */)
1990 (string
, bound
, noerror
, count
)
1991 Lisp_Object string
, bound
, noerror
, count
;
1993 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
1996 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
1997 doc
: /* Search forward from point for STRING.
1998 Set point to the end of the occurrence found, and return point.
1999 An optional second argument bounds the search; it is a buffer position.
2000 The match found must not extend after that position. nil is equivalent
2002 Optional third argument, if t, means if fail just return nil (no error).
2003 If not nil and not t, move to limit of search and return nil.
2004 Optional fourth argument is repeat count--search for successive occurrences.
2006 Search case-sensitivity is determined by the value of the variable
2007 `case-fold-search', which see.
2009 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2010 (string
, bound
, noerror
, count
)
2011 Lisp_Object string
, bound
, noerror
, count
;
2013 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2016 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2017 "sWord search backward: ",
2018 doc
: /* Search backward from point for STRING, ignoring differences in punctuation.
2019 Set point to the beginning of the occurrence found, and return point.
2020 An optional second argument bounds the search; it is a buffer position.
2021 The match found must not extend before that position.
2022 Optional third argument, if t, means if fail just return nil (no error).
2023 If not nil and not t, move to limit of search and return nil.
2024 Optional fourth argument is repeat count--search for successive occurrences. */)
2025 (string
, bound
, noerror
, count
)
2026 Lisp_Object string
, bound
, noerror
, count
;
2028 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
2031 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2033 doc
: /* Search forward from point for STRING, ignoring differences in punctuation.
2034 Set point to the end of the occurrence found, and return point.
2035 An optional second argument bounds the search; it is a buffer position.
2036 The match found must not extend after that position.
2037 Optional third argument, if t, means if fail just return nil (no error).
2038 If not nil and not t, move to limit of search and return nil.
2039 Optional fourth argument is repeat count--search for successive occurrences. */)
2040 (string
, bound
, noerror
, count
)
2041 Lisp_Object string
, bound
, noerror
, count
;
2043 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
2046 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2047 "sRE search backward: ",
2048 doc
: /* Search backward from point for match for regular expression REGEXP.
2049 Set point to the beginning of the match, and return point.
2050 The match found is the one starting last in the buffer
2051 and yet ending before the origin of the search.
2052 An optional second argument bounds the search; it is a buffer position.
2053 The match found must start at or after that position.
2054 Optional third argument, if t, means if fail just return nil (no error).
2055 If not nil and not t, move to limit of search and return nil.
2056 Optional fourth argument is repeat count--search for successive occurrences.
2057 See also the functions `match-beginning', `match-end', `match-string',
2058 and `replace-match'. */)
2059 (regexp
, bound
, noerror
, count
)
2060 Lisp_Object regexp
, bound
, noerror
, count
;
2062 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2065 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2067 doc
: /* Search forward from point for regular expression REGEXP.
2068 Set point to the end of the occurrence found, and return point.
2069 An optional second argument bounds the search; it is a buffer position.
2070 The match found must not extend after that position.
2071 Optional third argument, if t, means if fail just return nil (no error).
2072 If not nil and not t, move to limit of search and return nil.
2073 Optional fourth argument is repeat count--search for successive occurrences.
2074 See also the functions `match-beginning', `match-end', `match-string',
2075 and `replace-match'. */)
2076 (regexp
, bound
, noerror
, count
)
2077 Lisp_Object regexp
, bound
, noerror
, count
;
2079 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2082 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2083 "sPosix search backward: ",
2084 doc
: /* Search backward from point for match for regular expression REGEXP.
2085 Find the longest match in accord with Posix regular expression rules.
2086 Set point to the beginning of the match, and return point.
2087 The match found is the one starting last in the buffer
2088 and yet ending before the origin of the search.
2089 An optional second argument bounds the search; it is a buffer position.
2090 The match found must start at or after that position.
2091 Optional third argument, if t, means if fail just return nil (no error).
2092 If not nil and not t, move to limit of search and return nil.
2093 Optional fourth argument is repeat count--search for successive occurrences.
2094 See also the functions `match-beginning', `match-end', `match-string',
2095 and `replace-match'. */)
2096 (regexp
, bound
, noerror
, count
)
2097 Lisp_Object regexp
, bound
, noerror
, count
;
2099 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2102 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2104 doc
: /* Search forward from point for regular expression REGEXP.
2105 Find the longest match in accord with Posix regular expression rules.
2106 Set point to the end of the occurrence found, and return point.
2107 An optional second argument bounds the search; it is a buffer position.
2108 The match found must not extend after that position.
2109 Optional third argument, if t, means if fail just return nil (no error).
2110 If not nil and not t, move to limit of search and return nil.
2111 Optional fourth argument is repeat count--search for successive occurrences.
2112 See also the functions `match-beginning', `match-end', `match-string',
2113 and `replace-match'. */)
2114 (regexp
, bound
, noerror
, count
)
2115 Lisp_Object regexp
, bound
, noerror
, count
;
2117 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2120 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2121 doc
: /* Replace text matched by last search with NEWTEXT.
2122 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2123 Otherwise maybe capitalize the whole text, or maybe just word initials,
2124 based on the replaced text.
2125 If the replaced text has only capital letters
2126 and has at least one multiletter word, convert NEWTEXT to all caps.
2127 If the replaced text has at least one word starting with a capital letter,
2128 then capitalize each word in NEWTEXT.
2130 If third arg LITERAL is non-nil, insert NEWTEXT literally.
2131 Otherwise treat `\\' as special:
2132 `\\&' in NEWTEXT means substitute original matched text.
2133 `\\N' means substitute what matched the Nth `\\(...\\)'.
2134 If Nth parens didn't match, substitute nothing.
2135 `\\\\' means insert one `\\'.
2136 FIXEDCASE and LITERAL are optional arguments.
2137 Leaves point at end of replacement text.
2139 The optional fourth argument STRING can be a string to modify.
2140 This is meaningful when the previous match was done against STRING,
2141 using `string-match'. When used this way, `replace-match'
2142 creates and returns a new string made by copying STRING and replacing
2143 the part of STRING that was matched.
2145 The optional fifth argument SUBEXP specifies a subexpression;
2146 it says to replace just that subexpression with NEWTEXT,
2147 rather than replacing the entire matched text.
2148 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2149 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2150 NEWTEXT in place of subexp N.
2151 This is useful only after a regular expression search or match,
2152 since only regular expressions have distinguished subexpressions. */)
2153 (newtext
, fixedcase
, literal
, string
, subexp
)
2154 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2156 enum { nochange
, all_caps
, cap_initial
} case_action
;
2157 register int pos
, pos_byte
;
2158 int some_multiletter_word
;
2161 int some_nonuppercase_initial
;
2162 register int c
, prevc
;
2164 int opoint
, newpoint
;
2166 CHECK_STRING (newtext
);
2168 if (! NILP (string
))
2169 CHECK_STRING (string
);
2171 case_action
= nochange
; /* We tried an initialization */
2172 /* but some C compilers blew it */
2174 if (search_regs
.num_regs
<= 0)
2175 error ("replace-match called before any match found");
2181 CHECK_NUMBER (subexp
);
2182 sub
= XINT (subexp
);
2183 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2184 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2189 if (search_regs
.start
[sub
] < BEGV
2190 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2191 || search_regs
.end
[sub
] > ZV
)
2192 args_out_of_range (make_number (search_regs
.start
[sub
]),
2193 make_number (search_regs
.end
[sub
]));
2197 if (search_regs
.start
[sub
] < 0
2198 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2199 || search_regs
.end
[sub
] > XSTRING (string
)->size
)
2200 args_out_of_range (make_number (search_regs
.start
[sub
]),
2201 make_number (search_regs
.end
[sub
]));
2204 if (NILP (fixedcase
))
2206 /* Decide how to casify by examining the matched text. */
2209 pos
= search_regs
.start
[sub
];
2210 last
= search_regs
.end
[sub
];
2213 pos_byte
= CHAR_TO_BYTE (pos
);
2215 pos_byte
= string_char_to_byte (string
, pos
);
2218 case_action
= all_caps
;
2220 /* some_multiletter_word is set nonzero if any original word
2221 is more than one letter long. */
2222 some_multiletter_word
= 0;
2224 some_nonuppercase_initial
= 0;
2231 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2232 INC_BOTH (pos
, pos_byte
);
2235 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2239 /* Cannot be all caps if any original char is lower case */
2242 if (SYNTAX (prevc
) != Sword
)
2243 some_nonuppercase_initial
= 1;
2245 some_multiletter_word
= 1;
2247 else if (!NOCASEP (c
))
2250 if (SYNTAX (prevc
) != Sword
)
2253 some_multiletter_word
= 1;
2257 /* If the initial is a caseless word constituent,
2258 treat that like a lowercase initial. */
2259 if (SYNTAX (prevc
) != Sword
)
2260 some_nonuppercase_initial
= 1;
2266 /* Convert to all caps if the old text is all caps
2267 and has at least one multiletter word. */
2268 if (! some_lowercase
&& some_multiletter_word
)
2269 case_action
= all_caps
;
2270 /* Capitalize each word, if the old text has all capitalized words. */
2271 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2272 case_action
= cap_initial
;
2273 else if (!some_nonuppercase_initial
&& some_uppercase
)
2274 /* Should x -> yz, operating on X, give Yz or YZ?
2275 We'll assume the latter. */
2276 case_action
= all_caps
;
2278 case_action
= nochange
;
2281 /* Do replacement in a string. */
2284 Lisp_Object before
, after
;
2286 before
= Fsubstring (string
, make_number (0),
2287 make_number (search_regs
.start
[sub
]));
2288 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2290 /* Substitute parts of the match into NEWTEXT
2295 int lastpos_byte
= 0;
2296 /* We build up the substituted string in ACCUM. */
2299 int length
= STRING_BYTES (XSTRING (newtext
));
2303 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2307 int delbackslash
= 0;
2309 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2313 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2317 substart
= search_regs
.start
[sub
];
2318 subend
= search_regs
.end
[sub
];
2320 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2322 if (search_regs
.start
[c
- '0'] >= 0)
2324 substart
= search_regs
.start
[c
- '0'];
2325 subend
= search_regs
.end
[c
- '0'];
2331 error ("Invalid use of `\\' in replacement text");
2335 if (pos
- 2 != lastpos
)
2336 middle
= substring_both (newtext
, lastpos
,
2338 pos
- 2, pos_byte
- 2);
2341 accum
= concat3 (accum
, middle
,
2343 make_number (substart
),
2344 make_number (subend
)));
2346 lastpos_byte
= pos_byte
;
2348 else if (delbackslash
)
2350 middle
= substring_both (newtext
, lastpos
,
2352 pos
- 1, pos_byte
- 1);
2354 accum
= concat2 (accum
, middle
);
2356 lastpos_byte
= pos_byte
;
2361 middle
= substring_both (newtext
, lastpos
,
2367 newtext
= concat2 (accum
, middle
);
2370 /* Do case substitution in NEWTEXT if desired. */
2371 if (case_action
== all_caps
)
2372 newtext
= Fupcase (newtext
);
2373 else if (case_action
== cap_initial
)
2374 newtext
= Fupcase_initials (newtext
);
2376 return concat3 (before
, newtext
, after
);
2379 /* Record point, then move (quietly) to the start of the match. */
2380 if (PT
>= search_regs
.end
[sub
])
2382 else if (PT
> search_regs
.start
[sub
])
2383 opoint
= search_regs
.end
[sub
] - ZV
;
2387 /* If we want non-literal replacement,
2388 perform substitution on the replacement string. */
2391 int length
= STRING_BYTES (XSTRING (newtext
));
2392 unsigned char *substed
;
2393 int substed_alloc_size
, substed_len
;
2394 int buf_multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
2395 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2396 Lisp_Object rev_tbl
;
2397 int really_changed
= 0;
2401 substed_alloc_size
= length
* 2 + 100;
2402 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2405 /* Go thru NEWTEXT, producing the actual text to insert in
2406 SUBSTED while adjusting multibyteness to that of the current
2409 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2411 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2412 unsigned char *add_stuff
= NULL
;
2418 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2420 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2424 /* Note that we don't have to increment POS. */
2425 c
= XSTRING (newtext
)->data
[pos_byte
++];
2427 c
= unibyte_char_to_multibyte (c
);
2430 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2431 or set IDX to a match index, which means put that part
2432 of the buffer text into SUBSTED. */
2440 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2442 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2443 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2447 c
= XSTRING (newtext
)->data
[pos_byte
++];
2449 c
= unibyte_char_to_multibyte (c
);
2454 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2456 if (search_regs
.start
[c
- '0'] >= 1)
2460 add_len
= 1, add_stuff
= "\\";
2464 error ("Invalid use of `\\' in replacement text");
2469 add_len
= CHAR_STRING (c
, str
);
2473 /* If we want to copy part of a previous match,
2474 set up ADD_STUFF and ADD_LEN to point to it. */
2477 int begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2478 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2479 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2480 move_gap (search_regs
.start
[idx
]);
2481 add_stuff
= BYTE_POS_ADDR (begbyte
);
2484 /* Now the stuff we want to add to SUBSTED
2485 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2487 /* Make sure SUBSTED is big enough. */
2488 if (substed_len
+ add_len
>= substed_alloc_size
)
2490 substed_alloc_size
= substed_len
+ add_len
+ 500;
2491 substed
= (unsigned char *) xrealloc (substed
,
2492 substed_alloc_size
+ 1);
2495 /* Now add to the end of SUBSTED. */
2498 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2499 substed_len
+= add_len
;
2504 newtext
= make_string (substed
, substed_len
);
2509 /* Replace the old text with the new in the cleanest possible way. */
2510 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2512 newpoint
= search_regs
.start
[sub
] + XSTRING (newtext
)->size
;
2514 if (case_action
== all_caps
)
2515 Fupcase_region (make_number (search_regs
.start
[sub
]),
2516 make_number (newpoint
));
2517 else if (case_action
== cap_initial
)
2518 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2519 make_number (newpoint
));
2521 /* Put point back where it was in the text. */
2523 TEMP_SET_PT (opoint
+ ZV
);
2525 TEMP_SET_PT (opoint
);
2527 /* Now move point "officially" to the start of the inserted replacement. */
2528 move_if_not_intangible (newpoint
);
2534 match_limit (num
, beginningp
)
2542 if (n
< 0 || n
>= search_regs
.num_regs
)
2543 args_out_of_range (num
, make_number (search_regs
.num_regs
));
2544 if (search_regs
.num_regs
<= 0
2545 || search_regs
.start
[n
] < 0)
2547 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2548 : search_regs
.end
[n
]));
2551 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2552 doc
: /* Return position of start of text matched by last search.
2553 SUBEXP, a number, specifies which parenthesized expression in the last
2555 Value is nil if SUBEXPth pair didn't match, or there were less than
2557 Zero means the entire text matched by the whole regexp or whole string. */)
2561 return match_limit (subexp
, 1);
2564 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2565 doc
: /* Return position of end of text matched by last search.
2566 SUBEXP, a number, specifies which parenthesized expression in the last
2568 Value is nil if SUBEXPth pair didn't match, or there were less than
2570 Zero means the entire text matched by the whole regexp or whole string. */)
2574 return match_limit (subexp
, 0);
2577 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 2, 0,
2578 doc
: /* Return a list containing all info on what the last search matched.
2579 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2580 All the elements are markers or nil (nil if the Nth pair didn't match)
2581 if the last match was on a buffer; integers or nil if a string was matched.
2582 Use `store-match-data' to reinstate the data in this list.
2584 If INTEGERS (the optional first argument) is non-nil, always use integers
2585 \(rather than markers) to represent buffer positions.
2586 If REUSE is a list, reuse it as part of the value. If REUSE is long enough
2587 to hold all the values, and if INTEGERS is non-nil, no consing is done. */)
2589 Lisp_Object integers
, reuse
;
2591 Lisp_Object tail
, prev
;
2595 if (NILP (last_thing_searched
))
2600 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
)
2601 * sizeof (Lisp_Object
));
2604 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2606 int start
= search_regs
.start
[i
];
2609 if (EQ (last_thing_searched
, Qt
)
2610 || ! NILP (integers
))
2612 XSETFASTINT (data
[2 * i
], start
);
2613 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2615 else if (BUFFERP (last_thing_searched
))
2617 data
[2 * i
] = Fmake_marker ();
2618 Fset_marker (data
[2 * i
],
2619 make_number (start
),
2620 last_thing_searched
);
2621 data
[2 * i
+ 1] = Fmake_marker ();
2622 Fset_marker (data
[2 * i
+ 1],
2623 make_number (search_regs
.end
[i
]),
2624 last_thing_searched
);
2627 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2633 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2636 /* If REUSE is not usable, cons up the values and return them. */
2637 if (! CONSP (reuse
))
2638 return Flist (2 * len
+ 2, data
);
2640 /* If REUSE is a list, store as many value elements as will fit
2641 into the elements of REUSE. */
2642 for (i
= 0, tail
= reuse
; CONSP (tail
);
2643 i
++, tail
= XCDR (tail
))
2645 if (i
< 2 * len
+ 2)
2646 XSETCAR (tail
, data
[i
]);
2648 XSETCAR (tail
, Qnil
);
2652 /* If we couldn't fit all value elements into REUSE,
2653 cons up the rest of them and add them to the end of REUSE. */
2654 if (i
< 2 * len
+ 2)
2655 XSETCDR (prev
, Flist (2 * len
+ 2 - i
, data
+ i
));
2661 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 1, 0,
2662 doc
: /* Set internal data on last search match from elements of LIST.
2663 LIST should have been created by calling `match-data' previously. */)
2665 register Lisp_Object list
;
2668 register Lisp_Object marker
;
2670 if (running_asynch_code
)
2671 save_search_regs ();
2673 if (!CONSP (list
) && !NILP (list
))
2674 list
= wrong_type_argument (Qconsp
, list
);
2676 /* Unless we find a marker with a buffer in LIST, assume that this
2677 match data came from a string. */
2678 last_thing_searched
= Qt
;
2680 /* Allocate registers if they don't already exist. */
2682 int length
= XFASTINT (Flength (list
)) / 2;
2684 if (length
> search_regs
.num_regs
)
2686 if (search_regs
.num_regs
== 0)
2689 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2691 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2696 = (regoff_t
*) xrealloc (search_regs
.start
,
2697 length
* sizeof (regoff_t
));
2699 = (regoff_t
*) xrealloc (search_regs
.end
,
2700 length
* sizeof (regoff_t
));
2703 for (i
= search_regs
.num_regs
; i
< length
; i
++)
2704 search_regs
.start
[i
] = -1;
2706 search_regs
.num_regs
= length
;
2710 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2712 marker
= Fcar (list
);
2715 search_regs
.start
[i
] = -1;
2722 if (MARKERP (marker
))
2724 if (XMARKER (marker
)->buffer
== 0)
2725 XSETFASTINT (marker
, 0);
2727 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2730 CHECK_NUMBER_COERCE_MARKER (marker
);
2731 from
= XINT (marker
);
2734 marker
= Fcar (list
);
2735 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2736 XSETFASTINT (marker
, 0);
2738 CHECK_NUMBER_COERCE_MARKER (marker
);
2739 search_regs
.start
[i
] = from
;
2740 search_regs
.end
[i
] = XINT (marker
);
2748 /* If non-zero the match data have been saved in saved_search_regs
2749 during the execution of a sentinel or filter. */
2750 static int search_regs_saved
;
2751 static struct re_registers saved_search_regs
;
2753 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2754 if asynchronous code (filter or sentinel) is running. */
2758 if (!search_regs_saved
)
2760 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2761 saved_search_regs
.start
= search_regs
.start
;
2762 saved_search_regs
.end
= search_regs
.end
;
2763 search_regs
.num_regs
= 0;
2764 search_regs
.start
= 0;
2765 search_regs
.end
= 0;
2767 search_regs_saved
= 1;
2771 /* Called upon exit from filters and sentinels. */
2773 restore_match_data ()
2775 if (search_regs_saved
)
2777 if (search_regs
.num_regs
> 0)
2779 xfree (search_regs
.start
);
2780 xfree (search_regs
.end
);
2782 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2783 search_regs
.start
= saved_search_regs
.start
;
2784 search_regs
.end
= saved_search_regs
.end
;
2786 search_regs_saved
= 0;
2790 /* Quote a string to inactivate reg-expr chars */
2792 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
2793 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
2797 register unsigned char *in
, *out
, *end
;
2798 register unsigned char *temp
;
2799 int backslashes_added
= 0;
2801 CHECK_STRING (string
);
2803 temp
= (unsigned char *) alloca (STRING_BYTES (XSTRING (string
)) * 2);
2805 /* Now copy the data into the new string, inserting escapes. */
2807 in
= XSTRING (string
)->data
;
2808 end
= in
+ STRING_BYTES (XSTRING (string
));
2811 for (; in
!= end
; in
++)
2813 if (*in
== '[' || *in
== ']'
2814 || *in
== '*' || *in
== '.' || *in
== '\\'
2815 || *in
== '?' || *in
== '+'
2816 || *in
== '^' || *in
== '$')
2817 *out
++ = '\\', backslashes_added
++;
2821 return make_specified_string (temp
,
2822 XSTRING (string
)->size
+ backslashes_added
,
2824 STRING_MULTIBYTE (string
));
2832 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
2834 searchbufs
[i
].buf
.allocated
= 100;
2835 searchbufs
[i
].buf
.buffer
= (unsigned char *) malloc (100);
2836 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
2837 searchbufs
[i
].regexp
= Qnil
;
2838 staticpro (&searchbufs
[i
].regexp
);
2839 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
2841 searchbuf_head
= &searchbufs
[0];
2843 Qsearch_failed
= intern ("search-failed");
2844 staticpro (&Qsearch_failed
);
2845 Qinvalid_regexp
= intern ("invalid-regexp");
2846 staticpro (&Qinvalid_regexp
);
2848 Fput (Qsearch_failed
, Qerror_conditions
,
2849 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
2850 Fput (Qsearch_failed
, Qerror_message
,
2851 build_string ("Search failed"));
2853 Fput (Qinvalid_regexp
, Qerror_conditions
,
2854 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
2855 Fput (Qinvalid_regexp
, Qerror_message
,
2856 build_string ("Invalid regexp"));
2858 last_thing_searched
= Qnil
;
2859 staticpro (&last_thing_searched
);
2861 defsubr (&Slooking_at
);
2862 defsubr (&Sposix_looking_at
);
2863 defsubr (&Sstring_match
);
2864 defsubr (&Sposix_string_match
);
2865 defsubr (&Ssearch_forward
);
2866 defsubr (&Ssearch_backward
);
2867 defsubr (&Sword_search_forward
);
2868 defsubr (&Sword_search_backward
);
2869 defsubr (&Sre_search_forward
);
2870 defsubr (&Sre_search_backward
);
2871 defsubr (&Sposix_search_forward
);
2872 defsubr (&Sposix_search_backward
);
2873 defsubr (&Sreplace_match
);
2874 defsubr (&Smatch_beginning
);
2875 defsubr (&Smatch_end
);
2876 defsubr (&Smatch_data
);
2877 defsubr (&Sset_match_data
);
2878 defsubr (&Sregexp_quote
);