1 /* String search routines for GNU Emacs.
2 Copyright (C) 1985, 86, 87, 93, 94, 97, 1998 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 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 ();
88 static int search_buffer ();
93 error ("Stack overflow in regexp matcher");
102 /* Compile a regexp and signal a Lisp error if anything goes wrong.
103 PATTERN is the pattern to compile.
104 CP is the place to put the result.
105 TRANSLATE is a translation table for ignoring case, or NULL for none.
106 REGP is the structure that says where to store the "register"
107 values that will result from matching this pattern.
108 If it is 0, we should compile the pattern not to record any
109 subexpression bounds.
110 POSIX is nonzero if we want full backtracking (POSIX style)
111 for this pattern. 0 means backtrack only enough to get a valid match.
112 MULTIBYTE is nonzero if we want to handle multibyte characters in
113 PATTERN. 0 means all multibyte characters are recognized just as
114 sequences of binary data. */
117 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
118 struct regexp_cache
*cp
;
120 Lisp_Object
*translate
;
121 struct re_registers
*regp
;
126 int raw_pattern_size
;
130 /* MULTIBYTE says whether the text to be searched is multibyte.
131 We must convert PATTERN to match that, or we will not really
132 find things right. */
134 if (multibyte
== STRING_MULTIBYTE (pattern
))
136 raw_pattern
= (char *) XSTRING (pattern
)->data
;
137 raw_pattern_size
= XSTRING (pattern
)->size_byte
;
141 raw_pattern_size
= count_size_as_multibyte (XSTRING (pattern
)->data
,
142 XSTRING (pattern
)->size
);
143 raw_pattern
= (char *) alloca (raw_pattern_size
+ 1);
144 copy_text (XSTRING (pattern
)->data
, raw_pattern
,
145 XSTRING (pattern
)->size
, 0, 1);
149 /* Converting multibyte to single-byte.
151 ??? Perhaps this conversion should be done in a special way
152 by subtracting nonascii-insert-offset from each non-ASCII char,
153 so that only the multibyte chars which really correspond to
154 the chosen single-byte character set can possibly match. */
155 raw_pattern_size
= XSTRING (pattern
)->size
;
156 raw_pattern
= (char *) alloca (raw_pattern_size
+ 1);
157 copy_text (XSTRING (pattern
)->data
, raw_pattern
,
158 XSTRING (pattern
)->size
, 1, 0);
162 cp
->buf
.translate
= translate
;
164 cp
->buf
.multibyte
= multibyte
;
166 old
= re_set_syntax (RE_SYNTAX_EMACS
167 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
168 val
= (char *) re_compile_pattern (raw_pattern
, raw_pattern_size
, &cp
->buf
);
172 Fsignal (Qinvalid_regexp
, Fcons (build_string (val
), Qnil
));
174 cp
->regexp
= Fcopy_sequence (pattern
);
177 /* Compile a regexp if necessary, but first check to see if there's one in
179 PATTERN is the pattern to compile.
180 TRANSLATE is a translation table for ignoring case, or NULL for none.
181 REGP is the structure that says where to store the "register"
182 values that will result from matching this pattern.
183 If it is 0, we should compile the pattern not to record any
184 subexpression bounds.
185 POSIX is nonzero if we want full backtracking (POSIX style)
186 for this pattern. 0 means backtrack only enough to get a valid match. */
188 struct re_pattern_buffer
*
189 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
191 struct re_registers
*regp
;
192 Lisp_Object
*translate
;
193 int posix
, multibyte
;
195 struct regexp_cache
*cp
, **cpp
;
197 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
200 if (XSTRING (cp
->regexp
)->size
== XSTRING (pattern
)->size
201 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
202 && cp
->buf
.translate
== translate
203 && cp
->posix
== posix
204 && cp
->buf
.multibyte
== multibyte
)
207 /* If we're at the end of the cache, compile into the last cell. */
210 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
215 /* When we get here, cp (aka *cpp) contains the compiled pattern,
216 either because we found it in the cache or because we just compiled it.
217 Move it to the front of the queue to mark it as most recently used. */
219 cp
->next
= searchbuf_head
;
222 /* Advise the searching functions about the space we have allocated
223 for register data. */
225 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
230 /* Error condition used for failing searches */
231 Lisp_Object Qsearch_failed
;
237 Fsignal (Qsearch_failed
, Fcons (arg
, Qnil
));
242 looking_at_1 (string
, posix
)
247 unsigned char *p1
, *p2
;
250 struct re_pattern_buffer
*bufp
;
252 if (running_asynch_code
)
255 CHECK_STRING (string
, 0);
256 bufp
= compile_pattern (string
, &search_regs
,
257 (!NILP (current_buffer
->case_fold_search
)
258 ? XCHAR_TABLE (DOWNCASE_TABLE
)->contents
: 0),
260 !NILP (current_buffer
->enable_multibyte_characters
));
263 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
265 /* Get pointers and sizes of the two strings
266 that make up the visible portion of the buffer. */
269 s1
= GPT_BYTE
- BEGV_BYTE
;
271 s2
= ZV_BYTE
- GPT_BYTE
;
275 s2
= ZV_BYTE
- BEGV_BYTE
;
280 s1
= ZV_BYTE
- BEGV_BYTE
;
284 re_match_object
= Qnil
;
286 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
287 PT_BYTE
- BEGV_BYTE
, &search_regs
,
288 ZV_BYTE
- BEGV_BYTE
);
292 val
= (0 <= i
? Qt
: Qnil
);
294 for (i
= 0; i
< search_regs
.num_regs
; i
++)
295 if (search_regs
.start
[i
] >= 0)
298 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
300 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
302 XSETBUFFER (last_thing_searched
, current_buffer
);
307 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
308 "Return t if text after point matches regular expression REGEXP.\n\
309 This function modifies the match data that `match-beginning',\n\
310 `match-end' and `match-data' access; save and restore the match\n\
311 data if you want to preserve them.")
315 return looking_at_1 (regexp
, 0);
318 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
319 "Return t if text after point matches regular expression REGEXP.\n\
320 Find the longest match, in accord with Posix regular expression rules.\n\
321 This function modifies the match data that `match-beginning',\n\
322 `match-end' and `match-data' access; save and restore the match\n\
323 data if you want to preserve them.")
327 return looking_at_1 (regexp
, 1);
331 string_match_1 (regexp
, string
, start
, posix
)
332 Lisp_Object regexp
, string
, start
;
336 struct re_pattern_buffer
*bufp
;
340 if (running_asynch_code
)
343 CHECK_STRING (regexp
, 0);
344 CHECK_STRING (string
, 1);
347 pos
= 0, pos_byte
= 0;
350 int len
= XSTRING (string
)->size
;
352 CHECK_NUMBER (start
, 2);
354 if (pos
< 0 && -pos
<= len
)
356 else if (0 > pos
|| pos
> len
)
357 args_out_of_range (string
, start
);
358 pos_byte
= string_char_to_byte (string
, pos
);
361 bufp
= compile_pattern (regexp
, &search_regs
,
362 (!NILP (current_buffer
->case_fold_search
)
363 ? XCHAR_TABLE (DOWNCASE_TABLE
)->contents
: 0),
365 STRING_MULTIBYTE (string
));
367 re_match_object
= string
;
369 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
370 XSTRING (string
)->size_byte
, pos_byte
,
371 XSTRING (string
)->size_byte
- pos_byte
,
374 last_thing_searched
= Qt
;
377 if (val
< 0) return Qnil
;
379 for (i
= 0; i
< search_regs
.num_regs
; i
++)
380 if (search_regs
.start
[i
] >= 0)
383 = string_byte_to_char (string
, search_regs
.start
[i
]);
385 = string_byte_to_char (string
, search_regs
.end
[i
]);
388 return make_number (string_byte_to_char (string
, val
));
391 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
392 "Return index of start of first match for REGEXP in STRING, or nil.\n\
393 If third arg START is non-nil, start search at that index in STRING.\n\
394 For index of first char beyond the match, do (match-end 0).\n\
395 `match-end' and `match-beginning' also give indices of substrings\n\
396 matched by parenthesis constructs in the pattern.")
397 (regexp
, string
, start
)
398 Lisp_Object regexp
, string
, start
;
400 return string_match_1 (regexp
, string
, start
, 0);
403 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
404 "Return index of start of first match for REGEXP in STRING, or nil.\n\
405 Find the longest match, in accord with Posix regular expression rules.\n\
406 If third arg START is non-nil, start search at that index in STRING.\n\
407 For index of first char beyond the match, do (match-end 0).\n\
408 `match-end' and `match-beginning' also give indices of substrings\n\
409 matched by parenthesis constructs in the pattern.")
410 (regexp
, string
, start
)
411 Lisp_Object regexp
, string
, start
;
413 return string_match_1 (regexp
, string
, start
, 1);
416 /* Match REGEXP against STRING, searching all of STRING,
417 and return the index of the match, or negative on failure.
418 This does not clobber the match data. */
421 fast_string_match (regexp
, string
)
422 Lisp_Object regexp
, string
;
425 struct re_pattern_buffer
*bufp
;
427 bufp
= compile_pattern (regexp
, 0, 0, 0, STRING_MULTIBYTE (string
));
429 re_match_object
= string
;
431 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
432 XSTRING (string
)->size
, 0, XSTRING (string
)->size
,
438 /* Match REGEXP against STRING, searching all of STRING ignoring case,
439 and return the index of the match, or negative on failure.
440 This does not clobber the match data.
441 We assume that STRING contains single-byte characters. */
443 extern Lisp_Object Vascii_downcase_table
;
446 fast_c_string_match_ignore_case (regexp
, string
)
451 struct re_pattern_buffer
*bufp
;
452 int len
= strlen (string
);
454 regexp
= string_make_unibyte (regexp
);
455 re_match_object
= Qt
;
456 bufp
= compile_pattern (regexp
, 0,
457 XCHAR_TABLE (Vascii_downcase_table
)->contents
, 0,
460 val
= re_search (bufp
, string
, len
, 0, len
, 0);
471 return ((a
> b
) ? a
: b
);
478 return ((a
< b
) ? a
: b
);
482 /* The newline cache: remembering which sections of text have no newlines. */
484 /* If the user has requested newline caching, make sure it's on.
485 Otherwise, make sure it's off.
486 This is our cheezy way of associating an action with the change of
487 state of a buffer-local variable. */
489 newline_cache_on_off (buf
)
492 if (NILP (buf
->cache_long_line_scans
))
494 /* It should be off. */
495 if (buf
->newline_cache
)
497 free_region_cache (buf
->newline_cache
);
498 buf
->newline_cache
= 0;
503 /* It should be on. */
504 if (buf
->newline_cache
== 0)
505 buf
->newline_cache
= new_region_cache ();
510 /* Search for COUNT instances of the character TARGET between START and END.
512 If COUNT is positive, search forwards; END must be >= START.
513 If COUNT is negative, search backwards for the -COUNTth instance;
514 END must be <= START.
515 If COUNT is zero, do anything you please; run rogue, for all I care.
517 If END is zero, use BEGV or ZV instead, as appropriate for the
518 direction indicated by COUNT.
520 If we find COUNT instances, set *SHORTAGE to zero, and return the
521 position after the COUNTth match. Note that for reverse motion
522 this is not the same as the usual convention for Emacs motion commands.
524 If we don't find COUNT instances before reaching END, set *SHORTAGE
525 to the number of TARGETs left unfound, and return END.
527 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
528 except when inside redisplay. */
530 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
537 struct region_cache
*newline_cache
;
548 if (! end
) end
= BEGV
;
551 newline_cache_on_off (current_buffer
);
552 newline_cache
= current_buffer
->newline_cache
;
557 immediate_quit
= allow_quit
;
562 /* Our innermost scanning loop is very simple; it doesn't know
563 about gaps, buffer ends, or the newline cache. ceiling is
564 the position of the last character before the next such
565 obstacle --- the last character the dumb search loop should
567 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
568 int start_byte
= CHAR_TO_BYTE (start
);
570 /* If we're looking for a newline, consult the newline cache
571 to see where we can avoid some scanning. */
572 if (target
== '\n' && newline_cache
)
576 while (region_cache_forward
577 (current_buffer
, newline_cache
, start_byte
, &next_change
))
578 start_byte
= next_change
;
579 immediate_quit
= allow_quit
;
581 /* START should never be after END. */
582 if (start_byte
> ceiling_byte
)
583 start_byte
= ceiling_byte
;
585 /* Now the text after start is an unknown region, and
586 next_change is the position of the next known region. */
587 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
590 /* The dumb loop can only scan text stored in contiguous
591 bytes. BUFFER_CEILING_OF returns the last character
592 position that is contiguous, so the ceiling is the
593 position after that. */
594 ceiling_byte
= min (BUFFER_CEILING_OF (start_byte
), ceiling_byte
);
597 /* The termination address of the dumb loop. */
598 register unsigned char *ceiling_addr
599 = BYTE_POS_ADDR (ceiling_byte
) + 1;
600 register unsigned char *cursor
601 = BYTE_POS_ADDR (start_byte
);
602 unsigned char *base
= cursor
;
604 while (cursor
< ceiling_addr
)
606 unsigned char *scan_start
= cursor
;
609 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
612 /* If we're looking for newlines, cache the fact that
613 the region from start to cursor is free of them. */
614 if (target
== '\n' && newline_cache
)
615 know_region_cache (current_buffer
, newline_cache
,
616 start_byte
+ scan_start
- base
,
617 start_byte
+ cursor
- base
);
619 /* Did we find the target character? */
620 if (cursor
< ceiling_addr
)
625 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
631 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
637 /* The last character to check before the next obstacle. */
638 int ceiling_byte
= CHAR_TO_BYTE (end
);
639 int start_byte
= CHAR_TO_BYTE (start
);
641 /* Consult the newline cache, if appropriate. */
642 if (target
== '\n' && newline_cache
)
646 while (region_cache_backward
647 (current_buffer
, newline_cache
, start_byte
, &next_change
))
648 start_byte
= next_change
;
649 immediate_quit
= allow_quit
;
651 /* Start should never be at or before end. */
652 if (start_byte
<= ceiling_byte
)
653 start_byte
= ceiling_byte
+ 1;
655 /* Now the text before start is an unknown region, and
656 next_change is the position of the next known region. */
657 ceiling_byte
= max (next_change
, ceiling_byte
);
660 /* Stop scanning before the gap. */
661 ceiling_byte
= max (BUFFER_FLOOR_OF (start_byte
- 1), ceiling_byte
);
664 /* The termination address of the dumb loop. */
665 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
666 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
667 unsigned char *base
= cursor
;
669 while (cursor
>= ceiling_addr
)
671 unsigned char *scan_start
= cursor
;
673 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
676 /* If we're looking for newlines, cache the fact that
677 the region from after the cursor to start is free of them. */
678 if (target
== '\n' && newline_cache
)
679 know_region_cache (current_buffer
, newline_cache
,
680 start_byte
+ cursor
- base
,
681 start_byte
+ scan_start
- base
);
683 /* Did we find the target character? */
684 if (cursor
>= ceiling_addr
)
689 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
695 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
701 *shortage
= count
* direction
;
705 /* Search for COUNT instances of a line boundary, which means either a
706 newline or (if selective display enabled) a carriage return.
707 Start at START. If COUNT is negative, search backwards.
709 We report the resulting position by calling TEMP_SET_PT_BOTH.
711 If we find COUNT instances. we position after (always after,
712 even if scanning backwards) the COUNTth match, and return 0.
714 If we don't find COUNT instances before reaching the end of the
715 buffer (or the beginning, if scanning backwards), we return
716 the number of line boundaries left unfound, and position at
717 the limit we bumped up against.
719 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
720 except in special cases. */
723 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
724 int start
, start_byte
;
725 int limit
, limit_byte
;
729 int direction
= ((count
> 0) ? 1 : -1);
731 register unsigned char *cursor
;
734 register int ceiling
;
735 register unsigned char *ceiling_addr
;
737 int old_immediate_quit
= immediate_quit
;
739 /* If we are not in selective display mode,
740 check only for newlines. */
741 int selective_display
= (!NILP (current_buffer
->selective_display
)
742 && !INTEGERP (current_buffer
->selective_display
));
744 /* The code that follows is like scan_buffer
745 but checks for either newline or carriage return. */
750 start_byte
= CHAR_TO_BYTE (start
);
754 while (start_byte
< limit_byte
)
756 ceiling
= BUFFER_CEILING_OF (start_byte
);
757 ceiling
= min (limit_byte
- 1, ceiling
);
758 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
759 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
762 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
765 if (cursor
!= ceiling_addr
)
769 immediate_quit
= old_immediate_quit
;
770 start_byte
= start_byte
+ cursor
- base
+ 1;
771 start
= BYTE_TO_CHAR (start_byte
);
772 TEMP_SET_PT_BOTH (start
, start_byte
);
776 if (++cursor
== ceiling_addr
)
782 start_byte
+= cursor
- base
;
787 int start_byte
= CHAR_TO_BYTE (start
);
788 while (start_byte
> limit_byte
)
790 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
791 ceiling
= max (limit_byte
, ceiling
);
792 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
793 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
796 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
799 if (cursor
!= ceiling_addr
)
803 immediate_quit
= old_immediate_quit
;
804 /* Return the position AFTER the match we found. */
805 start_byte
= start_byte
+ cursor
- base
+ 1;
806 start
= BYTE_TO_CHAR (start_byte
);
807 TEMP_SET_PT_BOTH (start
, start_byte
);
814 /* Here we add 1 to compensate for the last decrement
815 of CURSOR, which took it past the valid range. */
816 start_byte
+= cursor
- base
+ 1;
820 TEMP_SET_PT_BOTH (limit
, limit_byte
);
821 immediate_quit
= old_immediate_quit
;
823 return count
* direction
;
827 find_next_newline_no_quit (from
, cnt
)
828 register int from
, cnt
;
830 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
833 /* Like find_next_newline, but returns position before the newline,
834 not after, and only search up to TO. This isn't just
835 find_next_newline (...)-1, because you might hit TO. */
838 find_before_next_newline (from
, to
, cnt
)
842 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
850 /* Subroutines of Lisp buffer search functions. */
853 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
854 Lisp_Object string
, bound
, noerror
, count
;
865 CHECK_NUMBER (count
, 3);
869 CHECK_STRING (string
, 0);
871 lim
= n
> 0 ? ZV
: BEGV
;
874 CHECK_NUMBER_COERCE_MARKER (bound
, 1);
876 if (n
> 0 ? lim
< PT
: lim
> PT
)
877 error ("Invalid search bound (wrong side of point)");
884 np
= search_buffer (string
, PT
, lim
, n
, RE
,
885 (!NILP (current_buffer
->case_fold_search
)
886 ? XCHAR_TABLE (current_buffer
->case_canon_table
)->contents
888 (!NILP (current_buffer
->case_fold_search
)
889 ? XCHAR_TABLE (current_buffer
->case_eqv_table
)->contents
895 return signal_failure (string
);
896 if (!EQ (noerror
, Qt
))
898 if (lim
< BEGV
|| lim
> ZV
)
902 #if 0 /* This would be clean, but maybe programs depend on
903 a value of nil here. */
911 if (np
< BEGV
|| np
> ZV
)
916 return make_number (np
);
919 /* Return 1 if REGEXP it matches just one constant string. */
922 trivial_regexp_p (regexp
)
925 int len
= XSTRING (regexp
)->size
;
926 unsigned char *s
= XSTRING (regexp
)->data
;
932 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
939 case '|': case '(': case ')': case '`': case '\'': case 'b':
940 case 'B': case '<': case '>': case 'w': case 'W': case 's':
942 case 'c': case 'C': /* for categoryspec and notcategoryspec */
943 case '1': case '2': case '3': case '4': case '5':
944 case '6': case '7': case '8': case '9':
952 /* Search for the n'th occurrence of STRING in the current buffer,
953 starting at position POS and stopping at position LIM,
954 treating STRING as a literal string if RE is false or as
955 a regular expression if RE is true.
957 If N is positive, searching is forward and LIM must be greater than POS.
958 If N is negative, searching is backward and LIM must be less than POS.
960 Returns -x if only N-x occurrences found (x > 0),
961 or else the position at the beginning of the Nth occurrence
962 (if searching backward) or the end (if searching forward).
964 POSIX is nonzero if we want full backtracking (POSIX style)
965 for this pattern. 0 means backtrack only enough to get a valid match. */
968 search_buffer (string
, pos
, lim
, n
, RE
, trt
, inverse_trt
, posix
)
975 Lisp_Object
*inverse_trt
;
978 int len
= XSTRING (string
)->size
;
979 int len_byte
= XSTRING (string
)->size_byte
;
980 unsigned char *base_pat
= XSTRING (string
)->data
;
981 register int *BM_tab
;
983 register int direction
= ((n
> 0) ? 1 : -1);
985 int infinity
, limit
, k
, stride_for_teases
;
986 register unsigned char *pat
, *cursor
, *p_limit
;
988 unsigned char *p1
, *p2
;
991 if (running_asynch_code
)
994 /* Null string is found at starting position. */
997 set_search_regs (pos
, 0);
1001 /* Searching 0 times means don't move. */
1005 if (RE
&& !trivial_regexp_p (string
))
1007 struct re_pattern_buffer
*bufp
;
1009 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
,
1010 !NILP (current_buffer
->enable_multibyte_characters
));
1012 immediate_quit
= 1; /* Quit immediately if user types ^G,
1013 because letting this function finish
1014 can take too long. */
1015 QUIT
; /* Do a pending quit right away,
1016 to avoid paradoxical behavior */
1017 /* Get pointers and sizes of the two strings
1018 that make up the visible portion of the buffer. */
1021 s1
= GPT_BYTE
- BEGV_BYTE
;
1023 s2
= ZV_BYTE
- GPT_BYTE
;
1027 s2
= ZV_BYTE
- BEGV_BYTE
;
1032 s1
= ZV_BYTE
- BEGV_BYTE
;
1035 re_match_object
= Qnil
;
1040 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1041 pos
- BEGV
, lim
- pos
, &search_regs
,
1042 /* Don't allow match past current point */
1046 matcher_overflow ();
1050 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1051 if (search_regs
.start
[i
] >= 0)
1053 search_regs
.start
[i
]
1054 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1056 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1058 XSETBUFFER (last_thing_searched
, current_buffer
);
1059 /* Set pos to the new position. */
1060 pos
= search_regs
.start
[0];
1072 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1073 pos
- BEGV
, lim
- pos
, &search_regs
,
1077 matcher_overflow ();
1081 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1082 if (search_regs
.start
[i
] >= 0)
1084 search_regs
.start
[i
]
1085 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1087 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1089 XSETBUFFER (last_thing_searched
, current_buffer
);
1090 pos
= search_regs
.end
[0];
1102 else /* non-RE case */
1104 int pos_byte
= CHAR_TO_BYTE (pos
);
1105 int lim_byte
= CHAR_TO_BYTE (lim
);
1107 int BM_tab_space
[0400];
1108 BM_tab
= &BM_tab_space
[0];
1110 BM_tab
= (int *) alloca (0400 * sizeof (int));
1113 unsigned char *raw_pattern
;
1114 int raw_pattern_size
;
1115 unsigned char *patbuf
;
1116 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1118 /* MULTIBYTE says whether the text to be searched is multibyte.
1119 We must convert PATTERN to match that, or we will not really
1120 find things right. */
1122 if (multibyte
== STRING_MULTIBYTE (string
))
1124 raw_pattern
= (char *) XSTRING (string
)->data
;
1125 raw_pattern_size
= XSTRING (string
)->size_byte
;
1129 raw_pattern_size
= count_size_as_multibyte (XSTRING (string
)->data
,
1130 XSTRING (string
)->size
);
1131 raw_pattern
= (char *) alloca (raw_pattern_size
+ 1);
1132 copy_text (XSTRING (string
)->data
, raw_pattern
,
1133 XSTRING (string
)->size
, 0, 1);
1137 /* Converting multibyte to single-byte.
1139 ??? Perhaps this conversion should be done in a special way
1140 by subtracting nonascii-insert-offset from each non-ASCII char,
1141 so that only the multibyte chars which really correspond to
1142 the chosen single-byte character set can possibly match. */
1143 raw_pattern_size
= XSTRING (string
)->size
;
1144 raw_pattern
= (char *) alloca (raw_pattern_size
+ 1);
1145 copy_text (XSTRING (string
)->data
, raw_pattern
,
1146 XSTRING (string
)->size
, 1, 0);
1149 len_byte
= raw_pattern_size
;
1150 patbuf
= (unsigned char *) alloca (len_byte
);
1152 base_pat
= raw_pattern
;
1153 while (--len_byte
>= 0)
1155 /* If we got here and the RE flag is set, it's because we're
1156 dealing with a regexp known to be trivial, so the backslash
1157 just quotes the next character. */
1158 if (RE
&& *base_pat
== '\\')
1163 *pat
++ = (trt
? XINT (trt
[*base_pat
++]) : *base_pat
++);
1165 len_byte
= pat
- patbuf
;
1166 pat
= base_pat
= patbuf
;
1168 /* The general approach is that we are going to maintain that we know */
1169 /* the first (closest to the present position, in whatever direction */
1170 /* we're searching) character that could possibly be the last */
1171 /* (furthest from present position) character of a valid match. We */
1172 /* advance the state of our knowledge by looking at that character */
1173 /* and seeing whether it indeed matches the last character of the */
1174 /* pattern. If it does, we take a closer look. If it does not, we */
1175 /* move our pointer (to putative last characters) as far as is */
1176 /* logically possible. This amount of movement, which I call a */
1177 /* stride, will be the length of the pattern if the actual character */
1178 /* appears nowhere in the pattern, otherwise it will be the distance */
1179 /* from the last occurrence of that character to the end of the */
1181 /* As a coding trick, an enormous stride is coded into the table for */
1182 /* characters that match the last character. This allows use of only */
1183 /* a single test, a test for having gone past the end of the */
1184 /* permissible match region, to test for both possible matches (when */
1185 /* the stride goes past the end immediately) and failure to */
1186 /* match (where you get nudged past the end one stride at a time). */
1188 /* Here we make a "mickey mouse" BM table. The stride of the search */
1189 /* is determined only by the last character of the putative match. */
1190 /* If that character does not match, we will stride the proper */
1191 /* distance to propose a match that superimposes it on the last */
1192 /* instance of a character that matches it (per trt), or misses */
1193 /* it entirely if there is none. */
1195 dirlen
= len_byte
* direction
;
1196 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1198 pat
= (base_pat
+= len_byte
- 1);
1199 BM_tab_base
= BM_tab
;
1201 j
= dirlen
; /* to get it in a register */
1202 /* A character that does not appear in the pattern induces a */
1203 /* stride equal to the pattern length. */
1204 while (BM_tab_base
!= BM_tab
)
1212 while (i
!= infinity
)
1214 j
= pat
[i
]; i
+= direction
;
1215 if (i
== dirlen
) i
= infinity
;
1218 k
= (j
= XINT (trt
[j
]));
1220 stride_for_teases
= BM_tab
[j
];
1221 BM_tab
[j
] = dirlen
- i
;
1222 /* A translation table is accompanied by its inverse -- see */
1223 /* comment following downcase_table for details */
1224 while ((j
= (unsigned char) XINT (inverse_trt
[j
])) != k
)
1225 BM_tab
[j
] = dirlen
- i
;
1230 stride_for_teases
= BM_tab
[j
];
1231 BM_tab
[j
] = dirlen
- i
;
1233 /* stride_for_teases tells how much to stride if we get a */
1234 /* match on the far character but are subsequently */
1235 /* disappointed, by recording what the stride would have been */
1236 /* for that character if the last character had been */
1239 infinity
= dirlen
- infinity
;
1240 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1241 /* loop invariant - POS_BYTE points at where last char (first
1242 char if reverse) of pattern would align in a possible match. */
1245 /* It's been reported that some (broken) compiler thinks that
1246 Boolean expressions in an arithmetic context are unsigned.
1247 Using an explicit ?1:0 prevents this. */
1248 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1250 return (n
* (0 - direction
));
1251 /* First we do the part we can by pointers (maybe nothing) */
1254 limit
= pos_byte
- dirlen
+ direction
;
1255 limit
= ((direction
> 0)
1256 ? BUFFER_CEILING_OF (limit
)
1257 : BUFFER_FLOOR_OF (limit
));
1258 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1259 can take on without hitting edge of buffer or the gap. */
1260 limit
= ((direction
> 0)
1261 ? min (lim_byte
- 1, min (limit
, pos_byte
+ 20000))
1262 : max (lim_byte
, max (limit
, pos_byte
- 20000)));
1263 if ((limit
- pos_byte
) * direction
> 20)
1265 p_limit
= BYTE_POS_ADDR (limit
);
1266 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1267 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1268 while (1) /* use one cursor setting as long as i can */
1270 if (direction
> 0) /* worth duplicating */
1272 /* Use signed comparison if appropriate
1273 to make cursor+infinity sure to be > p_limit.
1274 Assuming that the buffer lies in a range of addresses
1275 that are all "positive" (as ints) or all "negative",
1276 either kind of comparison will work as long
1277 as we don't step by infinity. So pick the kind
1278 that works when we do step by infinity. */
1279 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1280 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1281 cursor
+= BM_tab
[*cursor
];
1283 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1284 cursor
+= BM_tab
[*cursor
];
1288 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1289 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1290 cursor
+= BM_tab
[*cursor
];
1292 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1293 cursor
+= BM_tab
[*cursor
];
1295 /* If you are here, cursor is beyond the end of the searched region. */
1296 /* This can happen if you match on the far character of the pattern, */
1297 /* because the "stride" of that character is infinity, a number able */
1298 /* to throw you well beyond the end of the search. It can also */
1299 /* happen if you fail to match within the permitted region and would */
1300 /* otherwise try a character beyond that region */
1301 if ((cursor
- p_limit
) * direction
<= len_byte
)
1302 break; /* a small overrun is genuine */
1303 cursor
-= infinity
; /* large overrun = hit */
1304 i
= dirlen
- direction
;
1307 while ((i
-= direction
) + direction
!= 0)
1308 if (pat
[i
] != XINT (trt
[*(cursor
-= direction
)]))
1313 while ((i
-= direction
) + direction
!= 0)
1314 if (pat
[i
] != *(cursor
-= direction
))
1317 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1318 if (i
+ direction
== 0)
1322 cursor
-= direction
;
1324 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1325 ? 1 - len_byte
: 0);
1326 set_search_regs (position
, len_byte
);
1328 if ((n
-= direction
) != 0)
1329 cursor
+= dirlen
; /* to resume search */
1331 return ((direction
> 0)
1332 ? search_regs
.end
[0] : search_regs
.start
[0]);
1335 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1337 pos_byte
+= cursor
- p2
;
1340 /* Now we'll pick up a clump that has to be done the hard */
1341 /* way because it covers a discontinuity */
1343 limit
= ((direction
> 0)
1344 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1345 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1346 limit
= ((direction
> 0)
1347 ? min (limit
+ len_byte
, lim_byte
- 1)
1348 : max (limit
- len_byte
, lim_byte
));
1349 /* LIMIT is now the last value POS_BYTE can have
1350 and still be valid for a possible match. */
1353 /* This loop can be coded for space rather than */
1354 /* speed because it will usually run only once. */
1355 /* (the reach is at most len + 21, and typically */
1356 /* does not exceed len) */
1357 while ((limit
- pos_byte
) * direction
>= 0)
1358 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
1359 /* now run the same tests to distinguish going off the */
1360 /* end, a match or a phony match. */
1361 if ((pos_byte
- limit
) * direction
<= len_byte
)
1362 break; /* ran off the end */
1363 /* Found what might be a match.
1364 Set POS_BYTE back to last (first if reverse) pos. */
1365 pos_byte
-= infinity
;
1366 i
= dirlen
- direction
;
1367 while ((i
-= direction
) + direction
!= 0)
1369 pos_byte
-= direction
;
1370 if (pat
[i
] != (trt
!= 0
1371 ? XINT (trt
[FETCH_BYTE (pos_byte
)])
1372 : FETCH_BYTE (pos_byte
)))
1375 /* Above loop has moved POS_BYTE part or all the way
1376 back to the first pos (last pos if reverse).
1377 Set it once again at the last (first if reverse) char. */
1378 pos_byte
+= dirlen
- i
- direction
;
1379 if (i
+ direction
== 0)
1382 pos_byte
-= direction
;
1384 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
1386 set_search_regs (position
, len_byte
);
1388 if ((n
-= direction
) != 0)
1389 pos_byte
+= dirlen
; /* to resume search */
1391 return ((direction
> 0)
1392 ? search_regs
.end
[0] : search_regs
.start
[0]);
1395 pos_byte
+= stride_for_teases
;
1398 /* We have done one clump. Can we continue? */
1399 if ((lim_byte
- pos_byte
) * direction
< 0)
1400 return ((0 - n
) * direction
);
1402 return BYTE_TO_CHAR (pos_byte
);
1406 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
1407 for a match just found in the current buffer. */
1410 set_search_regs (beg_byte
, nbytes
)
1411 int beg_byte
, nbytes
;
1413 /* Make sure we have registers in which to store
1414 the match position. */
1415 if (search_regs
.num_regs
== 0)
1417 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1418 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1419 search_regs
.num_regs
= 2;
1422 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
1423 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
1424 XSETBUFFER (last_thing_searched
, current_buffer
);
1427 /* Given a string of words separated by word delimiters,
1428 compute a regexp that matches those exact words
1429 separated by arbitrary punctuation. */
1435 register unsigned char *p
, *o
;
1436 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
1441 CHECK_STRING (string
, 0);
1442 p
= XSTRING (string
)->data
;
1443 len
= XSTRING (string
)->size
;
1445 for (i
= 0, i_byte
= 0; i
< len
; )
1449 if (STRING_MULTIBYTE (string
))
1450 FETCH_STRING_CHAR_ADVANCE (c
, string
, i
, i_byte
);
1452 c
= XSTRING (string
)->data
[i
++];
1454 if (SYNTAX (c
) != Sword
)
1457 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
1464 if (SYNTAX (prev_c
) == Sword
)
1467 return build_string ("");
1469 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
1470 val
= make_uninit_multibyte_string (len
+ adjust
,
1471 XSTRING (string
)->size_byte
+ adjust
);
1473 o
= XSTRING (val
)->data
;
1477 for (i
= 0; i
< XSTRING (val
)->size_byte
; i
++)
1478 if (SYNTAX (p
[i
]) == Sword
)
1480 else if (i
> 0 && SYNTAX (p
[i
-1]) == Sword
&& --word_count
)
1495 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
1496 "MSearch backward: ",
1497 "Search backward from point for STRING.\n\
1498 Set point to the beginning of the occurrence found, and return point.\n\
1499 An optional second argument bounds the search; it is a buffer position.\n\
1500 The match found must not extend before that position.\n\
1501 Optional third argument, if t, means if fail just return nil (no error).\n\
1502 If not nil and not t, position at limit of search and return nil.\n\
1503 Optional fourth argument is repeat count--search for successive occurrences.\n\
1504 See also the functions `match-beginning', `match-end' and `replace-match'.")
1505 (string
, bound
, noerror
, count
)
1506 Lisp_Object string
, bound
, noerror
, count
;
1508 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
1511 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
1512 "Search forward from point for STRING.\n\
1513 Set point to the end of the occurrence found, and return point.\n\
1514 An optional second argument bounds the search; it is a buffer position.\n\
1515 The match found must not extend after that position. nil is equivalent\n\
1517 Optional third argument, if t, means if fail just return nil (no error).\n\
1518 If not nil and not t, move to limit of search and return nil.\n\
1519 Optional fourth argument is repeat count--search for successive occurrences.\n\
1520 See also the functions `match-beginning', `match-end' and `replace-match'.")
1521 (string
, bound
, noerror
, count
)
1522 Lisp_Object string
, bound
, noerror
, count
;
1524 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
1527 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
1528 "sWord search backward: ",
1529 "Search backward from point for STRING, ignoring differences in punctuation.\n\
1530 Set point to the beginning of the occurrence found, and return point.\n\
1531 An optional second argument bounds the search; it is a buffer position.\n\
1532 The match found must not extend before that position.\n\
1533 Optional third argument, if t, means if fail just return nil (no error).\n\
1534 If not nil and not t, move to limit of search and return nil.\n\
1535 Optional fourth argument is repeat count--search for successive occurrences.")
1536 (string
, bound
, noerror
, count
)
1537 Lisp_Object string
, bound
, noerror
, count
;
1539 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
1542 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
1544 "Search forward from point for STRING, ignoring differences in punctuation.\n\
1545 Set point to the end of the occurrence found, and return point.\n\
1546 An optional second argument bounds the search; it is a buffer position.\n\
1547 The match found must not extend after that position.\n\
1548 Optional third argument, if t, means if fail just return nil (no error).\n\
1549 If not nil and not t, move to limit of search and return nil.\n\
1550 Optional fourth argument is repeat count--search for successive occurrences.")
1551 (string
, bound
, noerror
, count
)
1552 Lisp_Object string
, bound
, noerror
, count
;
1554 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
1557 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
1558 "sRE search backward: ",
1559 "Search backward from point for match for regular expression REGEXP.\n\
1560 Set point to the beginning of the match, and return point.\n\
1561 The match found is the one starting last in the buffer\n\
1562 and yet ending before the origin of the search.\n\
1563 An optional second argument bounds the search; it is a buffer position.\n\
1564 The match found must start at or after that position.\n\
1565 Optional third argument, if t, means if fail just return nil (no error).\n\
1566 If not nil and not t, move to limit of search and return nil.\n\
1567 Optional fourth argument is repeat count--search for successive occurrences.\n\
1568 See also the functions `match-beginning', `match-end' and `replace-match'.")
1569 (regexp
, bound
, noerror
, count
)
1570 Lisp_Object regexp
, bound
, noerror
, count
;
1572 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
1575 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
1577 "Search forward from point for regular expression REGEXP.\n\
1578 Set point to the end of the occurrence found, and return point.\n\
1579 An optional second argument bounds the search; it is a buffer position.\n\
1580 The match found must not extend after that position.\n\
1581 Optional third argument, if t, means if fail just return nil (no error).\n\
1582 If not nil and not t, move to limit of search and return nil.\n\
1583 Optional fourth argument is repeat count--search for successive occurrences.\n\
1584 See also the functions `match-beginning', `match-end' and `replace-match'.")
1585 (regexp
, bound
, noerror
, count
)
1586 Lisp_Object regexp
, bound
, noerror
, count
;
1588 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
1591 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
1592 "sPosix search backward: ",
1593 "Search backward from point for match for regular expression REGEXP.\n\
1594 Find the longest match in accord with Posix regular expression rules.\n\
1595 Set point to the beginning of the match, and return point.\n\
1596 The match found is the one starting last in the buffer\n\
1597 and yet ending before the origin of the search.\n\
1598 An optional second argument bounds the search; it is a buffer position.\n\
1599 The match found must start at or after that position.\n\
1600 Optional third argument, if t, means if fail just return nil (no error).\n\
1601 If not nil and not t, move to limit of search and return nil.\n\
1602 Optional fourth argument is repeat count--search for successive occurrences.\n\
1603 See also the functions `match-beginning', `match-end' and `replace-match'.")
1604 (regexp
, bound
, noerror
, count
)
1605 Lisp_Object regexp
, bound
, noerror
, count
;
1607 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
1610 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
1612 "Search forward from point for regular expression REGEXP.\n\
1613 Find the longest match in accord with Posix regular expression rules.\n\
1614 Set point to the end of the occurrence found, and return point.\n\
1615 An optional second argument bounds the search; it is a buffer position.\n\
1616 The match found must not extend after that position.\n\
1617 Optional third argument, if t, means if fail just return nil (no error).\n\
1618 If not nil and not t, move to limit of search and return nil.\n\
1619 Optional fourth argument is repeat count--search for successive occurrences.\n\
1620 See also the functions `match-beginning', `match-end' and `replace-match'.")
1621 (regexp
, bound
, noerror
, count
)
1622 Lisp_Object regexp
, bound
, noerror
, count
;
1624 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
1627 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
1628 "Replace text matched by last search with NEWTEXT.\n\
1629 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.\n\
1630 Otherwise maybe capitalize the whole text, or maybe just word initials,\n\
1631 based on the replaced text.\n\
1632 If the replaced text has only capital letters\n\
1633 and has at least one multiletter word, convert NEWTEXT to all caps.\n\
1634 If the replaced text has at least one word starting with a capital letter,\n\
1635 then capitalize each word in NEWTEXT.\n\n\
1636 If third arg LITERAL is non-nil, insert NEWTEXT literally.\n\
1637 Otherwise treat `\\' as special:\n\
1638 `\\&' in NEWTEXT means substitute original matched text.\n\
1639 `\\N' means substitute what matched the Nth `\\(...\\)'.\n\
1640 If Nth parens didn't match, substitute nothing.\n\
1641 `\\\\' means insert one `\\'.\n\
1642 FIXEDCASE and LITERAL are optional arguments.\n\
1643 Leaves point at end of replacement text.\n\
1645 The optional fourth argument STRING can be a string to modify.\n\
1646 In that case, this function creates and returns a new string\n\
1647 which is made by replacing the part of STRING that was matched.\n\
1649 The optional fifth argument SUBEXP specifies a subexpression of the match.\n\
1650 It says to replace just that subexpression instead of the whole match.\n\
1651 This is useful only after a regular expression search or match\n\
1652 since only regular expressions have distinguished subexpressions.")
1653 (newtext
, fixedcase
, literal
, string
, subexp
)
1654 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
1656 enum { nochange
, all_caps
, cap_initial
} case_action
;
1657 register int pos
, last
;
1658 int some_multiletter_word
;
1661 int some_nonuppercase_initial
;
1662 register int c
, prevc
;
1665 int opoint
, newpoint
;
1667 CHECK_STRING (newtext
, 0);
1669 if (! NILP (string
))
1670 CHECK_STRING (string
, 4);
1672 case_action
= nochange
; /* We tried an initialization */
1673 /* but some C compilers blew it */
1675 if (search_regs
.num_regs
<= 0)
1676 error ("replace-match called before any match found");
1682 CHECK_NUMBER (subexp
, 3);
1683 sub
= XINT (subexp
);
1684 if (sub
< 0 || sub
>= search_regs
.num_regs
)
1685 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
1690 if (search_regs
.start
[sub
] < BEGV
1691 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
1692 || search_regs
.end
[sub
] > ZV
)
1693 args_out_of_range (make_number (search_regs
.start
[sub
]),
1694 make_number (search_regs
.end
[sub
]));
1698 if (search_regs
.start
[sub
] < 0
1699 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
1700 || search_regs
.end
[sub
] > XSTRING (string
)->size
)
1701 args_out_of_range (make_number (search_regs
.start
[sub
]),
1702 make_number (search_regs
.end
[sub
]));
1705 if (NILP (fixedcase
))
1708 /* Decide how to casify by examining the matched text. */
1711 last
= CHAR_TO_BYTE (search_regs
.end
[sub
]);
1713 last
= search_regs
.end
[sub
];
1716 beg
= CHAR_TO_BYTE (search_regs
.start
[sub
]);
1718 beg
= search_regs
.start
[sub
];
1721 case_action
= all_caps
;
1723 /* some_multiletter_word is set nonzero if any original word
1724 is more than one letter long. */
1725 some_multiletter_word
= 0;
1727 some_nonuppercase_initial
= 0;
1730 for (pos
= beg
; pos
< last
; pos
++)
1733 c
= FETCH_BYTE (pos
);
1735 c
= XSTRING (string
)->data
[pos
];
1739 /* Cannot be all caps if any original char is lower case */
1742 if (SYNTAX (prevc
) != Sword
)
1743 some_nonuppercase_initial
= 1;
1745 some_multiletter_word
= 1;
1747 else if (!NOCASEP (c
))
1750 if (SYNTAX (prevc
) != Sword
)
1753 some_multiletter_word
= 1;
1757 /* If the initial is a caseless word constituent,
1758 treat that like a lowercase initial. */
1759 if (SYNTAX (prevc
) != Sword
)
1760 some_nonuppercase_initial
= 1;
1766 /* Convert to all caps if the old text is all caps
1767 and has at least one multiletter word. */
1768 if (! some_lowercase
&& some_multiletter_word
)
1769 case_action
= all_caps
;
1770 /* Capitalize each word, if the old text has all capitalized words. */
1771 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
1772 case_action
= cap_initial
;
1773 else if (!some_nonuppercase_initial
&& some_uppercase
)
1774 /* Should x -> yz, operating on X, give Yz or YZ?
1775 We'll assume the latter. */
1776 case_action
= all_caps
;
1778 case_action
= nochange
;
1781 /* Do replacement in a string. */
1784 Lisp_Object before
, after
;
1786 before
= Fsubstring (string
, make_number (0),
1787 make_number (search_regs
.start
[sub
]));
1788 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
1790 /* Substitute parts of the match into NEWTEXT
1795 int lastpos_byte
= -1;
1796 /* We build up the substituted string in ACCUM. */
1803 for (pos_byte
= 0, pos
= 0; pos_byte
< XSTRING (newtext
)->size_byte
;)
1807 int delbackslash
= 0;
1809 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
1813 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
1816 substart
= search_regs
.start
[sub
];
1817 subend
= search_regs
.end
[sub
];
1819 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
1821 if (search_regs
.start
[c
- '0'] >= 0)
1823 substart
= search_regs
.start
[c
- '0'];
1824 subend
= search_regs
.end
[c
- '0'];
1830 error ("Invalid use of `\\' in replacement text");
1834 if (pos
- 1 != lastpos
+ 1)
1835 middle
= substring_both (newtext
, lastpos
+ 1,
1837 pos
- 1, pos_byte
- 1);
1840 accum
= concat3 (accum
, middle
,
1842 make_number (substart
),
1843 make_number (subend
)));
1845 lastpos_byte
= pos_byte
;
1847 else if (delbackslash
)
1849 middle
= substring_both (newtext
, lastpos
+ 1,
1853 accum
= concat2 (accum
, middle
);
1855 lastpos_byte
= pos_byte
;
1859 if (pos
!= lastpos
+ 1)
1860 middle
= substring_both (newtext
, lastpos
+ 1,
1866 newtext
= concat2 (accum
, middle
);
1869 /* Do case substitution in NEWTEXT if desired. */
1870 if (case_action
== all_caps
)
1871 newtext
= Fupcase (newtext
);
1872 else if (case_action
== cap_initial
)
1873 newtext
= Fupcase_initials (newtext
);
1875 return concat3 (before
, newtext
, after
);
1878 /* Record point, the move (quietly) to the start of the match. */
1879 if (PT
> search_regs
.start
[sub
])
1884 TEMP_SET_PT (search_regs
.start
[sub
]);
1886 /* We insert the replacement text before the old text, and then
1887 delete the original text. This means that markers at the
1888 beginning or end of the original will float to the corresponding
1889 position in the replacement. */
1890 if (!NILP (literal
))
1891 Finsert_and_inherit (1, &newtext
);
1894 struct gcpro gcpro1
;
1897 for (pos
= 0; pos
< XSTRING (newtext
)->size
; pos
++)
1899 int offset
= PT
- search_regs
.start
[sub
];
1901 c
= XSTRING (newtext
)->data
[pos
];
1904 c
= XSTRING (newtext
)->data
[++pos
];
1906 Finsert_buffer_substring
1907 (Fcurrent_buffer (),
1908 make_number (search_regs
.start
[sub
] + offset
),
1909 make_number (search_regs
.end
[sub
] + offset
));
1910 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
1912 if (search_regs
.start
[c
- '0'] >= 1)
1913 Finsert_buffer_substring
1914 (Fcurrent_buffer (),
1915 make_number (search_regs
.start
[c
- '0'] + offset
),
1916 make_number (search_regs
.end
[c
- '0'] + offset
));
1921 error ("Invalid use of `\\' in replacement text");
1929 inslen
= PT
- (search_regs
.start
[sub
]);
1930 del_range (search_regs
.start
[sub
] + inslen
, search_regs
.end
[sub
] + inslen
);
1932 if (case_action
== all_caps
)
1933 Fupcase_region (make_number (PT
- inslen
), make_number (PT
));
1934 else if (case_action
== cap_initial
)
1935 Fupcase_initials_region (make_number (PT
- inslen
), make_number (PT
));
1939 /* Put point back where it was in the text. */
1941 TEMP_SET_PT (opoint
+ ZV
);
1943 TEMP_SET_PT (opoint
);
1945 /* Now move point "officially" to the start of the inserted replacement. */
1946 move_if_not_intangible (newpoint
);
1952 match_limit (num
, beginningp
)
1958 CHECK_NUMBER (num
, 0);
1960 if (n
< 0 || n
>= search_regs
.num_regs
)
1961 args_out_of_range (num
, make_number (search_regs
.num_regs
));
1962 if (search_regs
.num_regs
<= 0
1963 || search_regs
.start
[n
] < 0)
1965 return (make_number ((beginningp
) ? search_regs
.start
[n
]
1966 : search_regs
.end
[n
]));
1969 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
1970 "Return position of start of text matched by last search.\n\
1971 SUBEXP, a number, specifies which parenthesized expression in the last\n\
1973 Value is nil if SUBEXPth pair didn't match, or there were less than\n\
1975 Zero means the entire text matched by the whole regexp or whole string.")
1979 return match_limit (subexp
, 1);
1982 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
1983 "Return position of end of text matched by last search.\n\
1984 SUBEXP, a number, specifies which parenthesized expression in the last\n\
1986 Value is nil if SUBEXPth pair didn't match, or there were less than\n\
1988 Zero means the entire text matched by the whole regexp or whole string.")
1992 return match_limit (subexp
, 0);
1995 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 2, 0,
1996 "Return a list containing all info on what the last search matched.\n\
1997 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.\n\
1998 All the elements are markers or nil (nil if the Nth pair didn't match)\n\
1999 if the last match was on a buffer; integers or nil if a string was matched.\n\
2000 Use `store-match-data' to reinstate the data in this list.\n\
2002 If INTEGERS (the optional first argument) is non-nil, always use integers\n\
2003 \(rather than markers) to represent buffer positions.\n\
2004 If REUSE is a list, reuse it as part of the value. If REUSE is long enough\n\
2005 to hold all the values, and if INTEGERS is non-nil, no consing is done.")
2007 Lisp_Object integers
, reuse
;
2009 Lisp_Object tail
, prev
;
2013 if (NILP (last_thing_searched
))
2016 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
)
2017 * sizeof (Lisp_Object
));
2020 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2022 int start
= search_regs
.start
[i
];
2025 if (EQ (last_thing_searched
, Qt
)
2026 || ! NILP (integers
))
2028 XSETFASTINT (data
[2 * i
], start
);
2029 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2031 else if (BUFFERP (last_thing_searched
))
2033 data
[2 * i
] = Fmake_marker ();
2034 Fset_marker (data
[2 * i
],
2035 make_number (start
),
2036 last_thing_searched
);
2037 data
[2 * i
+ 1] = Fmake_marker ();
2038 Fset_marker (data
[2 * i
+ 1],
2039 make_number (search_regs
.end
[i
]),
2040 last_thing_searched
);
2043 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2049 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2052 /* If REUSE is not usable, cons up the values and return them. */
2053 if (! CONSP (reuse
))
2054 return Flist (2 * len
+ 2, data
);
2056 /* If REUSE is a list, store as many value elements as will fit
2057 into the elements of REUSE. */
2058 for (i
= 0, tail
= reuse
; CONSP (tail
);
2059 i
++, tail
= XCONS (tail
)->cdr
)
2061 if (i
< 2 * len
+ 2)
2062 XCONS (tail
)->car
= data
[i
];
2064 XCONS (tail
)->car
= Qnil
;
2068 /* If we couldn't fit all value elements into REUSE,
2069 cons up the rest of them and add them to the end of REUSE. */
2070 if (i
< 2 * len
+ 2)
2071 XCONS (prev
)->cdr
= Flist (2 * len
+ 2 - i
, data
+ i
);
2077 DEFUN ("store-match-data", Fstore_match_data
, Sstore_match_data
, 1, 1, 0,
2078 "Set internal data on last search match from elements of LIST.\n\
2079 LIST should have been created by calling `match-data' previously.")
2081 register Lisp_Object list
;
2084 register Lisp_Object marker
;
2086 if (running_asynch_code
)
2087 save_search_regs ();
2089 if (!CONSP (list
) && !NILP (list
))
2090 list
= wrong_type_argument (Qconsp
, list
);
2092 /* Unless we find a marker with a buffer in LIST, assume that this
2093 match data came from a string. */
2094 last_thing_searched
= Qt
;
2096 /* Allocate registers if they don't already exist. */
2098 int length
= XFASTINT (Flength (list
)) / 2;
2100 if (length
> search_regs
.num_regs
)
2102 if (search_regs
.num_regs
== 0)
2105 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2107 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2112 = (regoff_t
*) xrealloc (search_regs
.start
,
2113 length
* sizeof (regoff_t
));
2115 = (regoff_t
*) xrealloc (search_regs
.end
,
2116 length
* sizeof (regoff_t
));
2119 search_regs
.num_regs
= length
;
2123 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2125 marker
= Fcar (list
);
2128 search_regs
.start
[i
] = -1;
2133 if (MARKERP (marker
))
2135 if (XMARKER (marker
)->buffer
== 0)
2136 XSETFASTINT (marker
, 0);
2138 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2141 CHECK_NUMBER_COERCE_MARKER (marker
, 0);
2142 search_regs
.start
[i
] = XINT (marker
);
2145 marker
= Fcar (list
);
2146 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2147 XSETFASTINT (marker
, 0);
2149 CHECK_NUMBER_COERCE_MARKER (marker
, 0);
2150 search_regs
.end
[i
] = XINT (marker
);
2158 /* If non-zero the match data have been saved in saved_search_regs
2159 during the execution of a sentinel or filter. */
2160 static int search_regs_saved
;
2161 static struct re_registers saved_search_regs
;
2163 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2164 if asynchronous code (filter or sentinel) is running. */
2168 if (!search_regs_saved
)
2170 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2171 saved_search_regs
.start
= search_regs
.start
;
2172 saved_search_regs
.end
= search_regs
.end
;
2173 search_regs
.num_regs
= 0;
2174 search_regs
.start
= 0;
2175 search_regs
.end
= 0;
2177 search_regs_saved
= 1;
2181 /* Called upon exit from filters and sentinels. */
2183 restore_match_data ()
2185 if (search_regs_saved
)
2187 if (search_regs
.num_regs
> 0)
2189 xfree (search_regs
.start
);
2190 xfree (search_regs
.end
);
2192 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2193 search_regs
.start
= saved_search_regs
.start
;
2194 search_regs
.end
= saved_search_regs
.end
;
2196 search_regs_saved
= 0;
2200 /* Quote a string to inactivate reg-expr chars */
2202 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
2203 "Return a regexp string which matches exactly STRING and nothing else.")
2207 register unsigned char *in
, *out
, *end
;
2208 register unsigned char *temp
;
2209 int backslashes_added
= 0;
2211 CHECK_STRING (string
, 0);
2213 temp
= (unsigned char *) alloca (XSTRING (string
)->size_byte
* 2);
2215 /* Now copy the data into the new string, inserting escapes. */
2217 in
= XSTRING (string
)->data
;
2218 end
= in
+ XSTRING (string
)->size_byte
;
2221 for (; in
!= end
; in
++)
2223 if (*in
== '[' || *in
== ']'
2224 || *in
== '*' || *in
== '.' || *in
== '\\'
2225 || *in
== '?' || *in
== '+'
2226 || *in
== '^' || *in
== '$')
2227 *out
++ = '\\', backslashes_added
++;
2231 return make_multibyte_string (temp
,
2232 XSTRING (string
)->size
+ backslashes_added
,
2240 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
2242 searchbufs
[i
].buf
.allocated
= 100;
2243 searchbufs
[i
].buf
.buffer
= (unsigned char *) malloc (100);
2244 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
2245 searchbufs
[i
].regexp
= Qnil
;
2246 staticpro (&searchbufs
[i
].regexp
);
2247 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
2249 searchbuf_head
= &searchbufs
[0];
2251 Qsearch_failed
= intern ("search-failed");
2252 staticpro (&Qsearch_failed
);
2253 Qinvalid_regexp
= intern ("invalid-regexp");
2254 staticpro (&Qinvalid_regexp
);
2256 Fput (Qsearch_failed
, Qerror_conditions
,
2257 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
2258 Fput (Qsearch_failed
, Qerror_message
,
2259 build_string ("Search failed"));
2261 Fput (Qinvalid_regexp
, Qerror_conditions
,
2262 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
2263 Fput (Qinvalid_regexp
, Qerror_message
,
2264 build_string ("Invalid regexp"));
2266 last_thing_searched
= Qnil
;
2267 staticpro (&last_thing_searched
);
2269 defsubr (&Slooking_at
);
2270 defsubr (&Sposix_looking_at
);
2271 defsubr (&Sstring_match
);
2272 defsubr (&Sposix_string_match
);
2273 defsubr (&Ssearch_forward
);
2274 defsubr (&Ssearch_backward
);
2275 defsubr (&Sword_search_forward
);
2276 defsubr (&Sword_search_backward
);
2277 defsubr (&Sre_search_forward
);
2278 defsubr (&Sre_search_backward
);
2279 defsubr (&Sposix_search_forward
);
2280 defsubr (&Sposix_search_backward
);
2281 defsubr (&Sreplace_match
);
2282 defsubr (&Smatch_beginning
);
2283 defsubr (&Smatch_end
);
2284 defsubr (&Smatch_data
);
2285 defsubr (&Sstore_match_data
);
2286 defsubr (&Sregexp_quote
);