1 /* String search routines for GNU Emacs.
2 Copyright (C) 1985, 1986, 1987, 1993, 1994 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"
32 #include <sys/types.h>
35 #define REGEXP_CACHE_SIZE 20
37 /* If the regexp is non-nil, then the buffer contains the compiled form
38 of that regexp, suitable for searching. */
41 struct regexp_cache
*next
;
43 struct re_pattern_buffer buf
;
45 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
49 /* The instances of that struct. */
50 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
52 /* The head of the linked list; points to the most recently used buffer. */
53 struct regexp_cache
*searchbuf_head
;
56 /* Every call to re_match, etc., must pass &search_regs as the regs
57 argument unless you can show it is unnecessary (i.e., if re_match
58 is certainly going to be called again before region-around-match
61 Since the registers are now dynamically allocated, we need to make
62 sure not to refer to the Nth register before checking that it has
63 been allocated by checking search_regs.num_regs.
65 The regex code keeps track of whether it has allocated the search
66 buffer using bits in the re_pattern_buffer. This means that whenever
67 you compile a new pattern, it completely forgets whether it has
68 allocated any registers, and will allocate new registers the next
69 time you call a searching or matching function. Therefore, we need
70 to call re_set_registers after compiling a new pattern or after
71 setting the match registers, so that the regex functions will be
72 able to free or re-allocate it properly. */
73 static struct re_registers search_regs
;
75 /* The buffer in which the last search was performed, or
76 Qt if the last search was done in a string;
77 Qnil if no searching has been done yet. */
78 static Lisp_Object last_thing_searched
;
80 /* error condition signaled when regexp compile_pattern fails */
82 Lisp_Object Qinvalid_regexp
;
84 static void set_search_regs ();
85 static void save_search_regs ();
87 static int search_buffer ();
92 error ("Stack overflow in regexp matcher");
101 /* Compile a regexp and signal a Lisp error if anything goes wrong.
102 PATTERN is the pattern to compile.
103 CP is the place to put the result.
104 TRANSLATE is a translation table for ignoring case, or NULL for none.
105 REGP is the structure that says where to store the "register"
106 values that will result from matching this pattern.
107 If it is 0, we should compile the pattern not to record any
108 subexpression bounds.
109 POSIX is nonzero if we want full backtracking (POSIX style)
110 for this pattern. 0 means backtrack only enough to get a valid match.
111 MULTIBYTE is nonzero if we want to handle multibyte characters in
112 PATTERN. 0 means all multibyte characters are recognized just as
113 sequences of binary data. */
116 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
117 struct regexp_cache
*cp
;
119 Lisp_Object
*translate
;
120 struct re_registers
*regp
;
128 cp
->buf
.translate
= translate
;
130 cp
->buf
.multibyte
= multibyte
;
132 old
= re_set_syntax (RE_SYNTAX_EMACS
133 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
134 val
= (CONST
char *) re_compile_pattern ((char *) XSTRING (pattern
)->data
,
135 XSTRING (pattern
)->size
, &cp
->buf
);
139 Fsignal (Qinvalid_regexp
, Fcons (build_string (val
), Qnil
));
141 cp
->regexp
= Fcopy_sequence (pattern
);
144 /* Compile a regexp if necessary, but first check to see if there's one in
146 PATTERN is the pattern to compile.
147 TRANSLATE is a translation table for ignoring case, or NULL for none.
148 REGP is the structure that says where to store the "register"
149 values that will result from matching this pattern.
150 If it is 0, we should compile the pattern not to record any
151 subexpression bounds.
152 POSIX is nonzero if we want full backtracking (POSIX style)
153 for this pattern. 0 means backtrack only enough to get a valid match. */
155 struct re_pattern_buffer
*
156 compile_pattern (pattern
, regp
, translate
, posix
)
158 struct re_registers
*regp
;
159 Lisp_Object
*translate
;
162 struct regexp_cache
*cp
, **cpp
;
163 /* Should we check it here, or add an argument `multibyte' to this
165 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
167 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
170 if (XSTRING (cp
->regexp
)->size
== XSTRING (pattern
)->size
171 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
172 && cp
->buf
.translate
== translate
173 && cp
->posix
== posix
174 && cp
->buf
.multibyte
== multibyte
)
177 /* If we're at the end of the cache, compile into the last cell. */
180 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
185 /* When we get here, cp (aka *cpp) contains the compiled pattern,
186 either because we found it in the cache or because we just compiled it.
187 Move it to the front of the queue to mark it as most recently used. */
189 cp
->next
= searchbuf_head
;
192 /* Advise the searching functions about the space we have allocated
193 for register data. */
195 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
200 /* Error condition used for failing searches */
201 Lisp_Object Qsearch_failed
;
207 Fsignal (Qsearch_failed
, Fcons (arg
, Qnil
));
212 looking_at_1 (string
, posix
)
217 unsigned char *p1
, *p2
;
220 struct re_pattern_buffer
*bufp
;
222 if (running_asynch_code
)
225 CHECK_STRING (string
, 0);
226 bufp
= compile_pattern (string
, &search_regs
,
227 (!NILP (current_buffer
->case_fold_search
)
228 ? DOWNCASE_TABLE
: 0),
232 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
234 /* Get pointers and sizes of the two strings
235 that make up the visible portion of the buffer. */
253 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
254 PT
- BEGV
, &search_regs
,
259 val
= (0 <= i
? Qt
: Qnil
);
260 for (i
= 0; i
< search_regs
.num_regs
; i
++)
261 if (search_regs
.start
[i
] >= 0)
263 search_regs
.start
[i
] += BEGV
;
264 search_regs
.end
[i
] += BEGV
;
266 XSETBUFFER (last_thing_searched
, current_buffer
);
271 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
272 "Return t if text after point matches regular expression REGEXP.\n\
273 This function modifies the match data that `match-beginning',\n\
274 `match-end' and `match-data' access; save and restore the match\n\
275 data if you want to preserve them.")
279 return looking_at_1 (regexp
, 0);
282 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
283 "Return t if text after point matches regular expression REGEXP.\n\
284 Find the longest match, in accord with Posix regular expression rules.\n\
285 This function modifies the match data that `match-beginning',\n\
286 `match-end' and `match-data' access; save and restore the match\n\
287 data if you want to preserve them.")
291 return looking_at_1 (regexp
, 1);
295 string_match_1 (regexp
, string
, start
, posix
)
296 Lisp_Object regexp
, string
, start
;
301 struct re_pattern_buffer
*bufp
;
303 if (running_asynch_code
)
306 CHECK_STRING (regexp
, 0);
307 CHECK_STRING (string
, 1);
313 int len
= XSTRING (string
)->size
;
315 CHECK_NUMBER (start
, 2);
317 if (s
< 0 && -s
<= len
)
319 else if (0 > s
|| s
> len
)
320 args_out_of_range (string
, start
);
323 bufp
= compile_pattern (regexp
, &search_regs
,
324 (!NILP (current_buffer
->case_fold_search
)
325 ? DOWNCASE_TABLE
: 0),
328 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
329 XSTRING (string
)->size
, s
, XSTRING (string
)->size
- s
,
332 last_thing_searched
= Qt
;
335 if (val
< 0) return Qnil
;
336 return make_number (val
);
339 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
340 "Return index of start of first match for REGEXP in STRING, or nil.\n\
341 If third arg START is non-nil, start search at that index in STRING.\n\
342 For index of first char beyond the match, do (match-end 0).\n\
343 `match-end' and `match-beginning' also give indices of substrings\n\
344 matched by parenthesis constructs in the pattern.")
345 (regexp
, string
, start
)
346 Lisp_Object regexp
, string
, start
;
348 return string_match_1 (regexp
, string
, start
, 0);
351 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
352 "Return index of start of first match for REGEXP in STRING, or nil.\n\
353 Find the longest match, in accord with Posix regular expression rules.\n\
354 If third arg START is non-nil, start search at that index in STRING.\n\
355 For index of first char beyond the match, do (match-end 0).\n\
356 `match-end' and `match-beginning' also give indices of substrings\n\
357 matched by parenthesis constructs in the pattern.")
358 (regexp
, string
, start
)
359 Lisp_Object regexp
, string
, start
;
361 return string_match_1 (regexp
, string
, start
, 1);
364 /* Match REGEXP against STRING, searching all of STRING,
365 and return the index of the match, or negative on failure.
366 This does not clobber the match data. */
369 fast_string_match (regexp
, string
)
370 Lisp_Object regexp
, string
;
373 struct re_pattern_buffer
*bufp
;
375 bufp
= compile_pattern (regexp
, 0, 0, 0);
377 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
378 XSTRING (string
)->size
, 0, XSTRING (string
)->size
,
384 /* Match REGEXP against STRING, searching all of STRING ignoring case,
385 and return the index of the match, or negative on failure.
386 This does not clobber the match data. */
388 extern Lisp_Object Vascii_downcase_table
;
391 fast_string_match_ignore_case (regexp
, string
)
396 struct re_pattern_buffer
*bufp
;
397 int len
= strlen (string
);
399 bufp
= compile_pattern (regexp
, 0,
400 XCHAR_TABLE (Vascii_downcase_table
)->contents
, 0);
402 val
= re_search (bufp
, string
, len
, 0, len
, 0);
413 return ((a
> b
) ? a
: b
);
420 return ((a
< b
) ? a
: b
);
424 /* The newline cache: remembering which sections of text have no newlines. */
426 /* If the user has requested newline caching, make sure it's on.
427 Otherwise, make sure it's off.
428 This is our cheezy way of associating an action with the change of
429 state of a buffer-local variable. */
431 newline_cache_on_off (buf
)
434 if (NILP (buf
->cache_long_line_scans
))
436 /* It should be off. */
437 if (buf
->newline_cache
)
439 free_region_cache (buf
->newline_cache
);
440 buf
->newline_cache
= 0;
445 /* It should be on. */
446 if (buf
->newline_cache
== 0)
447 buf
->newline_cache
= new_region_cache ();
452 /* Search for COUNT instances of the character TARGET between START and END.
454 If COUNT is positive, search forwards; END must be >= START.
455 If COUNT is negative, search backwards for the -COUNTth instance;
456 END must be <= START.
457 If COUNT is zero, do anything you please; run rogue, for all I care.
459 If END is zero, use BEGV or ZV instead, as appropriate for the
460 direction indicated by COUNT.
462 If we find COUNT instances, set *SHORTAGE to zero, and return the
463 position after the COUNTth match. Note that for reverse motion
464 this is not the same as the usual convention for Emacs motion commands.
466 If we don't find COUNT instances before reaching END, set *SHORTAGE
467 to the number of TARGETs left unfound, and return END.
469 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
470 except when inside redisplay. */
472 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
479 struct region_cache
*newline_cache
;
490 if (! end
) end
= BEGV
;
493 newline_cache_on_off (current_buffer
);
494 newline_cache
= current_buffer
->newline_cache
;
499 immediate_quit
= allow_quit
;
504 /* Our innermost scanning loop is very simple; it doesn't know
505 about gaps, buffer ends, or the newline cache. ceiling is
506 the position of the last character before the next such
507 obstacle --- the last character the dumb search loop should
509 register int ceiling
= end
- 1;
511 /* If we're looking for a newline, consult the newline cache
512 to see where we can avoid some scanning. */
513 if (target
== '\n' && newline_cache
)
517 while (region_cache_forward
518 (current_buffer
, newline_cache
, start
, &next_change
))
520 immediate_quit
= allow_quit
;
522 /* start should never be after end. */
526 /* Now the text after start is an unknown region, and
527 next_change is the position of the next known region. */
528 ceiling
= min (next_change
- 1, ceiling
);
531 /* The dumb loop can only scan text stored in contiguous
532 bytes. BUFFER_CEILING_OF returns the last character
533 position that is contiguous, so the ceiling is the
534 position after that. */
535 ceiling
= min (BUFFER_CEILING_OF (start
), ceiling
);
538 /* The termination address of the dumb loop. */
539 register unsigned char *ceiling_addr
= POS_ADDR (ceiling
) + 1;
540 register unsigned char *cursor
= POS_ADDR (start
);
541 unsigned char *base
= cursor
;
543 while (cursor
< ceiling_addr
)
545 unsigned char *scan_start
= cursor
;
548 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
551 /* If we're looking for newlines, cache the fact that
552 the region from start to cursor is free of them. */
553 if (target
== '\n' && newline_cache
)
554 know_region_cache (current_buffer
, newline_cache
,
555 start
+ scan_start
- base
,
556 start
+ cursor
- base
);
558 /* Did we find the target character? */
559 if (cursor
< ceiling_addr
)
564 return (start
+ cursor
- base
+ 1);
570 start
+= cursor
- base
;
576 /* The last character to check before the next obstacle. */
577 register int ceiling
= end
;
579 /* Consult the newline cache, if appropriate. */
580 if (target
== '\n' && newline_cache
)
584 while (region_cache_backward
585 (current_buffer
, newline_cache
, start
, &next_change
))
587 immediate_quit
= allow_quit
;
589 /* Start should never be at or before end. */
593 /* Now the text before start is an unknown region, and
594 next_change is the position of the next known region. */
595 ceiling
= max (next_change
, ceiling
);
598 /* Stop scanning before the gap. */
599 ceiling
= max (BUFFER_FLOOR_OF (start
- 1), ceiling
);
602 /* The termination address of the dumb loop. */
603 register unsigned char *ceiling_addr
= POS_ADDR (ceiling
);
604 register unsigned char *cursor
= POS_ADDR (start
- 1);
605 unsigned char *base
= cursor
;
607 while (cursor
>= ceiling_addr
)
609 unsigned char *scan_start
= cursor
;
611 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
614 /* If we're looking for newlines, cache the fact that
615 the region from after the cursor to start is free of them. */
616 if (target
== '\n' && newline_cache
)
617 know_region_cache (current_buffer
, newline_cache
,
618 start
+ cursor
- base
,
619 start
+ scan_start
- base
);
621 /* Did we find the target character? */
622 if (cursor
>= ceiling_addr
)
627 return (start
+ cursor
- base
);
633 start
+= cursor
- base
;
639 *shortage
= count
* direction
;
644 find_next_newline_no_quit (from
, cnt
)
645 register int from
, cnt
;
647 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
651 find_next_newline (from
, cnt
)
652 register int from
, cnt
;
654 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 1);
658 /* Like find_next_newline, but returns position before the newline,
659 not after, and only search up to TO. This isn't just
660 find_next_newline (...)-1, because you might hit TO. */
662 find_before_next_newline (from
, to
, cnt
)
666 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
674 Lisp_Object
skip_chars ();
676 DEFUN ("skip-chars-forward", Fskip_chars_forward
, Sskip_chars_forward
, 1, 2, 0,
677 "Move point forward, stopping before a char not in STRING, or at pos LIM.\n\
678 STRING is like the inside of a `[...]' in a regular expression\n\
679 except that `]' is never special and `\\' quotes `^', `-' or `\\'.\n\
680 Thus, with arg \"a-zA-Z\", this skips letters stopping before first nonletter.\n\
681 With arg \"^a-zA-Z\", skips nonletters stopping before first letter.\n\
682 Returns the distance traveled, either zero or positive.")
684 Lisp_Object string
, lim
;
686 return skip_chars (1, 0, string
, lim
);
689 DEFUN ("skip-chars-backward", Fskip_chars_backward
, Sskip_chars_backward
, 1, 2, 0,
690 "Move point backward, stopping after a char not in STRING, or at pos LIM.\n\
691 See `skip-chars-forward' for details.\n\
692 Returns the distance traveled, either zero or negative.")
694 Lisp_Object string
, lim
;
696 return skip_chars (0, 0, string
, lim
);
699 DEFUN ("skip-syntax-forward", Fskip_syntax_forward
, Sskip_syntax_forward
, 1, 2, 0,
700 "Move point forward across chars in specified syntax classes.\n\
701 SYNTAX is a string of syntax code characters.\n\
702 Stop before a char whose syntax is not in SYNTAX, or at position LIM.\n\
703 If SYNTAX starts with ^, skip characters whose syntax is NOT in SYNTAX.\n\
704 This function returns the distance traveled, either zero or positive.")
706 Lisp_Object syntax
, lim
;
708 return skip_chars (1, 1, syntax
, lim
);
711 DEFUN ("skip-syntax-backward", Fskip_syntax_backward
, Sskip_syntax_backward
, 1, 2, 0,
712 "Move point backward across chars in specified syntax classes.\n\
713 SYNTAX is a string of syntax code characters.\n\
714 Stop on reaching a char whose syntax is not in SYNTAX, or at position LIM.\n\
715 If SYNTAX starts with ^, skip characters whose syntax is NOT in SYNTAX.\n\
716 This function returns the distance traveled, either zero or negative.")
718 Lisp_Object syntax
, lim
;
720 return skip_chars (0, 1, syntax
, lim
);
724 skip_chars (forwardp
, syntaxp
, string
, lim
)
725 int forwardp
, syntaxp
;
726 Lisp_Object string
, lim
;
728 register unsigned char *p
, *pend
;
729 register unsigned char c
;
731 unsigned char fastmap
[0400];
732 /* If SYNTAXP is 0, STRING may contain multi-byte form of characters
733 of which codes don't fit in FASTMAP. In that case, we set the
734 first byte of multibyte form (i.e. base leading-code) in FASTMAP
735 and set the actual ranges of characters in CHAR_RANGES. In the
736 form "X-Y" of STRING, both X and Y must belong to the same
737 character set because a range striding across character sets is
740 = (int *) alloca (XSTRING (string
)->size
* (sizeof (int)) * 2);
741 int n_char_ranges
= 0;
744 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
746 CHECK_STRING (string
, 0);
749 XSETINT (lim
, forwardp
? ZV
: BEGV
);
751 CHECK_NUMBER_COERCE_MARKER (lim
, 1);
753 /* In any case, don't allow scan outside bounds of buffer. */
754 /* jla turned this off, for no known reason.
755 bfox turned the ZV part on, and rms turned the
756 BEGV part back on. */
758 XSETFASTINT (lim
, ZV
);
759 if (XINT (lim
) < BEGV
)
760 XSETFASTINT (lim
, BEGV
);
762 p
= XSTRING (string
)->data
;
763 pend
= p
+ XSTRING (string
)->size
;
764 bzero (fastmap
, sizeof fastmap
);
766 if (p
!= pend
&& *p
== '^')
771 /* Find the characters specified and set their elements of fastmap.
772 If syntaxp, each character counts as itself.
773 Otherwise, handle backslashes and ranges specially. */
780 ch
= STRING_CHAR (p
, pend
- p
);
781 p
+= BYTES_BY_CHAR_HEAD (*p
);
789 fastmap
[syntax_spec_code
[c
]] = 1;
794 if (p
== pend
) break;
797 if (p
!= pend
&& *p
== '-')
802 if (p
== pend
) break;
803 if (SINGLE_BYTE_CHAR_P (ch
))
811 fastmap
[c
] = 1; /* C is the base leading-code. */
812 ch2
= STRING_CHAR (p
, pend
- p
);
814 char_ranges
[n_char_ranges
++] = ch
,
815 char_ranges
[n_char_ranges
++] = ch2
;
817 p
+= multibyte
? BYTES_BY_CHAR_HEAD (*p
) : 1;
822 if (!SINGLE_BYTE_CHAR_P (ch
))
823 char_ranges
[n_char_ranges
++] = ch
,
824 char_ranges
[n_char_ranges
++] = ch
;
829 /* If ^ was the first character, complement the fastmap. In
830 addition, as all multibyte characters have possibility of
831 matching, set all entries for base leading codes, which is
832 harmless even if SYNTAXP is 1. */
835 for (i
= 0; i
< sizeof fastmap
; i
++)
837 if (!multibyte
|| !BASE_LEADING_CODE_P (i
))
844 int start_point
= PT
;
853 while (pos
< XINT (lim
)
854 && fastmap
[(int) SYNTAX (FETCH_CHAR (pos
))])
857 while (pos
< XINT (lim
)
858 && fastmap
[(int) SYNTAX (FETCH_BYTE (pos
))])
864 while (pos
> XINT (lim
))
868 if (!fastmap
[(int) SYNTAX (FETCH_CHAR (pos
))])
875 while (pos
> XINT (lim
)
876 && fastmap
[(int) SYNTAX (FETCH_BYTE (pos
- 1))])
885 while (pos
< XINT (lim
) && fastmap
[(c
= FETCH_BYTE (pos
))])
887 if (!BASE_LEADING_CODE_P (c
))
889 else if (n_char_ranges
)
891 /* We much check CHAR_RANGES for a multibyte
893 ch
= FETCH_MULTIBYTE_CHAR (pos
);
894 for (i
= 0; i
< n_char_ranges
; i
+= 2)
895 if ((ch
>= char_ranges
[i
] && ch
<= char_ranges
[i
+ 1]))
897 if (!(negate
^ (i
< n_char_ranges
)))
909 while (pos
< XINT (lim
) && fastmap
[FETCH_BYTE (pos
)])
915 while (pos
> XINT (lim
))
919 if (fastmap
[(c
= FETCH_BYTE (pos
))])
921 if (!BASE_LEADING_CODE_P (c
))
923 else if (n_char_ranges
)
925 /* We much check CHAR_RANGES for a multibyte
927 ch
= FETCH_MULTIBYTE_CHAR (pos
);
928 for (i
= 0; i
< n_char_ranges
; i
+= 2)
929 if (ch
>= char_ranges
[i
] && ch
<= char_ranges
[i
+ 1])
931 if (!(negate
^ (i
< n_char_ranges
)))
951 while (pos
> XINT (lim
) && fastmap
[FETCH_BYTE (pos
- 1)])
956 /* INC_POS or DEC_POS might have moved POS over LIM. */
957 && (forwardp
? (pos
> XINT (lim
)) : (pos
< XINT (lim
))))
963 return make_number (PT
- start_point
);
967 /* Subroutines of Lisp buffer search functions. */
970 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
971 Lisp_Object string
, bound
, noerror
, count
;
982 CHECK_NUMBER (count
, 3);
986 CHECK_STRING (string
, 0);
988 lim
= n
> 0 ? ZV
: BEGV
;
991 CHECK_NUMBER_COERCE_MARKER (bound
, 1);
993 if (n
> 0 ? lim
< PT
: lim
> PT
)
994 error ("Invalid search bound (wrong side of point)");
1001 np
= search_buffer (string
, PT
, lim
, n
, RE
,
1002 (!NILP (current_buffer
->case_fold_search
)
1003 ? XCHAR_TABLE (current_buffer
->case_canon_table
)->contents
1005 (!NILP (current_buffer
->case_fold_search
)
1006 ? XCHAR_TABLE (current_buffer
->case_eqv_table
)->contents
1012 return signal_failure (string
);
1013 if (!EQ (noerror
, Qt
))
1015 if (lim
< BEGV
|| lim
> ZV
)
1019 #if 0 /* This would be clean, but maybe programs depend on
1020 a value of nil here. */
1028 if (np
< BEGV
|| np
> ZV
)
1033 return make_number (np
);
1037 trivial_regexp_p (regexp
)
1040 int len
= XSTRING (regexp
)->size
;
1041 unsigned char *s
= XSTRING (regexp
)->data
;
1047 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1054 case '|': case '(': case ')': case '`': case '\'': case 'b':
1055 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1057 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1058 case '1': case '2': case '3': case '4': case '5':
1059 case '6': case '7': case '8': case '9':
1067 /* Search for the n'th occurrence of STRING in the current buffer,
1068 starting at position POS and stopping at position LIM,
1069 treating STRING as a literal string if RE is false or as
1070 a regular expression if RE is true.
1072 If N is positive, searching is forward and LIM must be greater than POS.
1073 If N is negative, searching is backward and LIM must be less than POS.
1075 Returns -x if only N-x occurrences found (x > 0),
1076 or else the position at the beginning of the Nth occurrence
1077 (if searching backward) or the end (if searching forward).
1079 POSIX is nonzero if we want full backtracking (POSIX style)
1080 for this pattern. 0 means backtrack only enough to get a valid match. */
1083 search_buffer (string
, pos
, lim
, n
, RE
, trt
, inverse_trt
, posix
)
1090 Lisp_Object
*inverse_trt
;
1093 int len
= XSTRING (string
)->size
;
1094 unsigned char *base_pat
= XSTRING (string
)->data
;
1095 register int *BM_tab
;
1097 register int direction
= ((n
> 0) ? 1 : -1);
1098 register int dirlen
;
1099 int infinity
, limit
, k
, stride_for_teases
;
1100 register unsigned char *pat
, *cursor
, *p_limit
;
1102 unsigned char *p1
, *p2
;
1105 if (running_asynch_code
)
1106 save_search_regs ();
1108 /* Null string is found at starting position. */
1111 set_search_regs (pos
, 0);
1115 /* Searching 0 times means don't move. */
1119 if (RE
&& !trivial_regexp_p (string
))
1121 struct re_pattern_buffer
*bufp
;
1123 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
);
1125 immediate_quit
= 1; /* Quit immediately if user types ^G,
1126 because letting this function finish
1127 can take too long. */
1128 QUIT
; /* Do a pending quit right away,
1129 to avoid paradoxical behavior */
1130 /* Get pointers and sizes of the two strings
1131 that make up the visible portion of the buffer. */
1151 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1152 pos
- BEGV
, lim
- pos
, &search_regs
,
1153 /* Don't allow match past current point */
1157 matcher_overflow ();
1162 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1163 if (search_regs
.start
[i
] >= 0)
1165 search_regs
.start
[i
] += j
;
1166 search_regs
.end
[i
] += j
;
1168 XSETBUFFER (last_thing_searched
, current_buffer
);
1169 /* Set pos to the new position. */
1170 pos
= search_regs
.start
[0];
1182 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1183 pos
- BEGV
, lim
- pos
, &search_regs
,
1187 matcher_overflow ();
1192 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1193 if (search_regs
.start
[i
] >= 0)
1195 search_regs
.start
[i
] += j
;
1196 search_regs
.end
[i
] += j
;
1198 XSETBUFFER (last_thing_searched
, current_buffer
);
1199 pos
= search_regs
.end
[0];
1211 else /* non-RE case */
1214 int BM_tab_space
[0400];
1215 BM_tab
= &BM_tab_space
[0];
1217 BM_tab
= (int *) alloca (0400 * sizeof (int));
1220 unsigned char *patbuf
= (unsigned char *) alloca (len
);
1224 /* If we got here and the RE flag is set, it's because we're
1225 dealing with a regexp known to be trivial, so the backslash
1226 just quotes the next character. */
1227 if (RE
&& *base_pat
== '\\')
1232 *pat
++ = (trt
? trt
[*base_pat
++] : *base_pat
++);
1235 pat
= base_pat
= patbuf
;
1237 /* The general approach is that we are going to maintain that we know */
1238 /* the first (closest to the present position, in whatever direction */
1239 /* we're searching) character that could possibly be the last */
1240 /* (furthest from present position) character of a valid match. We */
1241 /* advance the state of our knowledge by looking at that character */
1242 /* and seeing whether it indeed matches the last character of the */
1243 /* pattern. If it does, we take a closer look. If it does not, we */
1244 /* move our pointer (to putative last characters) as far as is */
1245 /* logically possible. This amount of movement, which I call a */
1246 /* stride, will be the length of the pattern if the actual character */
1247 /* appears nowhere in the pattern, otherwise it will be the distance */
1248 /* from the last occurrence of that character to the end of the */
1250 /* As a coding trick, an enormous stride is coded into the table for */
1251 /* characters that match the last character. This allows use of only */
1252 /* a single test, a test for having gone past the end of the */
1253 /* permissible match region, to test for both possible matches (when */
1254 /* the stride goes past the end immediately) and failure to */
1255 /* match (where you get nudged past the end one stride at a time). */
1257 /* Here we make a "mickey mouse" BM table. The stride of the search */
1258 /* is determined only by the last character of the putative match. */
1259 /* If that character does not match, we will stride the proper */
1260 /* distance to propose a match that superimposes it on the last */
1261 /* instance of a character that matches it (per trt), or misses */
1262 /* it entirely if there is none. */
1264 dirlen
= len
* direction
;
1265 infinity
= dirlen
- (lim
+ pos
+ len
+ len
) * direction
;
1267 pat
= (base_pat
+= len
- 1);
1268 BM_tab_base
= BM_tab
;
1270 j
= dirlen
; /* to get it in a register */
1271 /* A character that does not appear in the pattern induces a */
1272 /* stride equal to the pattern length. */
1273 while (BM_tab_base
!= BM_tab
)
1281 while (i
!= infinity
)
1283 j
= pat
[i
]; i
+= direction
;
1284 if (i
== dirlen
) i
= infinity
;
1289 stride_for_teases
= BM_tab
[j
];
1290 BM_tab
[j
] = dirlen
- i
;
1291 /* A translation table is accompanied by its inverse -- see */
1292 /* comment following downcase_table for details */
1293 while ((j
= (unsigned char) inverse_trt
[j
]) != k
)
1294 BM_tab
[j
] = dirlen
- i
;
1299 stride_for_teases
= BM_tab
[j
];
1300 BM_tab
[j
] = dirlen
- i
;
1302 /* stride_for_teases tells how much to stride if we get a */
1303 /* match on the far character but are subsequently */
1304 /* disappointed, by recording what the stride would have been */
1305 /* for that character if the last character had been */
1308 infinity
= dirlen
- infinity
;
1309 pos
+= dirlen
- ((direction
> 0) ? direction
: 0);
1310 /* loop invariant - pos points at where last char (first char if reverse)
1311 of pattern would align in a possible match. */
1314 /* It's been reported that some (broken) compiler thinks that
1315 Boolean expressions in an arithmetic context are unsigned.
1316 Using an explicit ?1:0 prevents this. */
1317 if ((lim
- pos
- ((direction
> 0) ? 1 : 0)) * direction
< 0)
1318 return (n
* (0 - direction
));
1319 /* First we do the part we can by pointers (maybe nothing) */
1322 limit
= pos
- dirlen
+ direction
;
1323 limit
= ((direction
> 0)
1324 ? BUFFER_CEILING_OF (limit
)
1325 : BUFFER_FLOOR_OF (limit
));
1326 /* LIMIT is now the last (not beyond-last!) value
1327 POS can take on without hitting edge of buffer or the gap. */
1328 limit
= ((direction
> 0)
1329 ? min (lim
- 1, min (limit
, pos
+ 20000))
1330 : max (lim
, max (limit
, pos
- 20000)));
1331 if ((limit
- pos
) * direction
> 20)
1333 p_limit
= POS_ADDR (limit
);
1334 p2
= (cursor
= POS_ADDR (pos
));
1335 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1336 while (1) /* use one cursor setting as long as i can */
1338 if (direction
> 0) /* worth duplicating */
1340 /* Use signed comparison if appropriate
1341 to make cursor+infinity sure to be > p_limit.
1342 Assuming that the buffer lies in a range of addresses
1343 that are all "positive" (as ints) or all "negative",
1344 either kind of comparison will work as long
1345 as we don't step by infinity. So pick the kind
1346 that works when we do step by infinity. */
1347 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1348 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1349 cursor
+= BM_tab
[*cursor
];
1351 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1352 cursor
+= BM_tab
[*cursor
];
1356 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1357 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1358 cursor
+= BM_tab
[*cursor
];
1360 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1361 cursor
+= BM_tab
[*cursor
];
1363 /* If you are here, cursor is beyond the end of the searched region. */
1364 /* This can happen if you match on the far character of the pattern, */
1365 /* because the "stride" of that character is infinity, a number able */
1366 /* to throw you well beyond the end of the search. It can also */
1367 /* happen if you fail to match within the permitted region and would */
1368 /* otherwise try a character beyond that region */
1369 if ((cursor
- p_limit
) * direction
<= len
)
1370 break; /* a small overrun is genuine */
1371 cursor
-= infinity
; /* large overrun = hit */
1372 i
= dirlen
- direction
;
1375 while ((i
-= direction
) + direction
!= 0)
1376 if (pat
[i
] != trt
[*(cursor
-= direction
)])
1381 while ((i
-= direction
) + direction
!= 0)
1382 if (pat
[i
] != *(cursor
-= direction
))
1385 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1386 if (i
+ direction
== 0)
1388 cursor
-= direction
;
1390 set_search_regs (pos
+ cursor
- p2
+ ((direction
> 0)
1394 if ((n
-= direction
) != 0)
1395 cursor
+= dirlen
; /* to resume search */
1397 return ((direction
> 0)
1398 ? search_regs
.end
[0] : search_regs
.start
[0]);
1401 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1406 /* Now we'll pick up a clump that has to be done the hard */
1407 /* way because it covers a discontinuity */
1409 limit
= ((direction
> 0)
1410 ? BUFFER_CEILING_OF (pos
- dirlen
+ 1)
1411 : BUFFER_FLOOR_OF (pos
- dirlen
- 1));
1412 limit
= ((direction
> 0)
1413 ? min (limit
+ len
, lim
- 1)
1414 : max (limit
- len
, lim
));
1415 /* LIMIT is now the last value POS can have
1416 and still be valid for a possible match. */
1419 /* This loop can be coded for space rather than */
1420 /* speed because it will usually run only once. */
1421 /* (the reach is at most len + 21, and typically */
1422 /* does not exceed len) */
1423 while ((limit
- pos
) * direction
>= 0)
1424 pos
+= BM_tab
[FETCH_BYTE (pos
)];
1425 /* now run the same tests to distinguish going off the */
1426 /* end, a match or a phony match. */
1427 if ((pos
- limit
) * direction
<= len
)
1428 break; /* ran off the end */
1429 /* Found what might be a match.
1430 Set POS back to last (first if reverse) char pos. */
1432 i
= dirlen
- direction
;
1433 while ((i
-= direction
) + direction
!= 0)
1436 if (pat
[i
] != (trt
!= 0
1437 ? trt
[FETCH_BYTE (pos
)]
1438 : FETCH_BYTE (pos
)))
1441 /* Above loop has moved POS part or all the way
1442 back to the first char pos (last char pos if reverse).
1443 Set it once again at the last (first if reverse) char. */
1444 pos
+= dirlen
- i
- direction
;
1445 if (i
+ direction
== 0)
1449 set_search_regs (pos
+ ((direction
> 0) ? 1 - len
: 0),
1452 if ((n
-= direction
) != 0)
1453 pos
+= dirlen
; /* to resume search */
1455 return ((direction
> 0)
1456 ? search_regs
.end
[0] : search_regs
.start
[0]);
1459 pos
+= stride_for_teases
;
1462 /* We have done one clump. Can we continue? */
1463 if ((lim
- pos
) * direction
< 0)
1464 return ((0 - n
) * direction
);
1470 /* Record beginning BEG and end BEG + LEN
1471 for a match just found in the current buffer. */
1474 set_search_regs (beg
, len
)
1477 /* Make sure we have registers in which to store
1478 the match position. */
1479 if (search_regs
.num_regs
== 0)
1481 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1482 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1483 search_regs
.num_regs
= 2;
1486 search_regs
.start
[0] = beg
;
1487 search_regs
.end
[0] = beg
+ len
;
1488 XSETBUFFER (last_thing_searched
, current_buffer
);
1491 /* Given a string of words separated by word delimiters,
1492 compute a regexp that matches those exact words
1493 separated by arbitrary punctuation. */
1499 register unsigned char *p
, *o
;
1500 register int i
, len
, punct_count
= 0, word_count
= 0;
1503 CHECK_STRING (string
, 0);
1504 p
= XSTRING (string
)->data
;
1505 len
= XSTRING (string
)->size
;
1507 for (i
= 0; i
< len
; i
++)
1508 if (SYNTAX (p
[i
]) != Sword
)
1511 if (i
> 0 && SYNTAX (p
[i
-1]) == Sword
) word_count
++;
1513 if (SYNTAX (p
[len
-1]) == Sword
) word_count
++;
1514 if (!word_count
) return build_string ("");
1516 val
= make_string (p
, len
- punct_count
+ 5 * (word_count
- 1) + 4);
1518 o
= XSTRING (val
)->data
;
1522 for (i
= 0; i
< len
; i
++)
1523 if (SYNTAX (p
[i
]) == Sword
)
1525 else if (i
> 0 && SYNTAX (p
[i
-1]) == Sword
&& --word_count
)
1540 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
1541 "sSearch backward: ",
1542 "Search backward from point for STRING.\n\
1543 Set point to the beginning of the occurrence found, and return point.\n\
1544 An optional second argument bounds the search; it is a buffer position.\n\
1545 The match found must not extend before that position.\n\
1546 Optional third argument, if t, means if fail just return nil (no error).\n\
1547 If not nil and not t, position at limit of search and return nil.\n\
1548 Optional fourth argument is repeat count--search for successive occurrences.\n\
1549 See also the functions `match-beginning', `match-end' and `replace-match'.")
1550 (string
, bound
, noerror
, count
)
1551 Lisp_Object string
, bound
, noerror
, count
;
1553 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
1556 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "sSearch: ",
1557 "Search forward from point for STRING.\n\
1558 Set point to the end of the occurrence found, and return point.\n\
1559 An optional second argument bounds the search; it is a buffer position.\n\
1560 The match found must not extend after that position. nil is equivalent\n\
1562 Optional third argument, if t, means if fail just return nil (no error).\n\
1563 If not nil and not t, move to limit of search and return nil.\n\
1564 Optional fourth argument is repeat count--search for successive occurrences.\n\
1565 See also the functions `match-beginning', `match-end' and `replace-match'.")
1566 (string
, bound
, noerror
, count
)
1567 Lisp_Object string
, bound
, noerror
, count
;
1569 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
1572 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
1573 "sWord search backward: ",
1574 "Search backward from point for STRING, ignoring differences in punctuation.\n\
1575 Set point to the beginning of the occurrence found, and return point.\n\
1576 An optional second argument bounds the search; it is a buffer position.\n\
1577 The match found must not extend before that position.\n\
1578 Optional third argument, if t, means if fail just return nil (no error).\n\
1579 If not nil and not t, move to limit of search and return nil.\n\
1580 Optional fourth argument is repeat count--search for successive occurrences.")
1581 (string
, bound
, noerror
, count
)
1582 Lisp_Object string
, bound
, noerror
, count
;
1584 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
1587 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
1589 "Search forward from point for STRING, ignoring differences in punctuation.\n\
1590 Set point to the end of the occurrence found, and return point.\n\
1591 An optional second argument bounds the search; it is a buffer position.\n\
1592 The match found must not extend after that position.\n\
1593 Optional third argument, if t, means if fail just return nil (no error).\n\
1594 If not nil and not t, move to limit of search and return nil.\n\
1595 Optional fourth argument is repeat count--search for successive occurrences.")
1596 (string
, bound
, noerror
, count
)
1597 Lisp_Object string
, bound
, noerror
, count
;
1599 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
1602 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
1603 "sRE search backward: ",
1604 "Search backward from point for match for regular expression REGEXP.\n\
1605 Set point to the beginning of the match, and return point.\n\
1606 The match found is the one starting last in the buffer\n\
1607 and yet ending before the origin of the search.\n\
1608 An optional second argument bounds the search; it is a buffer position.\n\
1609 The match found must start at or after that position.\n\
1610 Optional third argument, if t, means if fail just return nil (no error).\n\
1611 If not nil and not t, move to limit of search and return nil.\n\
1612 Optional fourth argument is repeat count--search for successive occurrences.\n\
1613 See also the functions `match-beginning', `match-end' and `replace-match'.")
1614 (regexp
, bound
, noerror
, count
)
1615 Lisp_Object regexp
, bound
, noerror
, count
;
1617 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
1620 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
1622 "Search forward from point for regular expression REGEXP.\n\
1623 Set point to the end of the occurrence found, and return point.\n\
1624 An optional second argument bounds the search; it is a buffer position.\n\
1625 The match found must not extend after that position.\n\
1626 Optional third argument, if t, means if fail just return nil (no error).\n\
1627 If not nil and not t, move to limit of search and return nil.\n\
1628 Optional fourth argument is repeat count--search for successive occurrences.\n\
1629 See also the functions `match-beginning', `match-end' and `replace-match'.")
1630 (regexp
, bound
, noerror
, count
)
1631 Lisp_Object regexp
, bound
, noerror
, count
;
1633 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
1636 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
1637 "sPosix search backward: ",
1638 "Search backward from point for match for regular expression REGEXP.\n\
1639 Find the longest match in accord with Posix regular expression rules.\n\
1640 Set point to the beginning of the match, and return point.\n\
1641 The match found is the one starting last in the buffer\n\
1642 and yet ending before the origin of the search.\n\
1643 An optional second argument bounds the search; it is a buffer position.\n\
1644 The match found must start at or after that position.\n\
1645 Optional third argument, if t, means if fail just return nil (no error).\n\
1646 If not nil and not t, move to limit of search and return nil.\n\
1647 Optional fourth argument is repeat count--search for successive occurrences.\n\
1648 See also the functions `match-beginning', `match-end' and `replace-match'.")
1649 (regexp
, bound
, noerror
, count
)
1650 Lisp_Object regexp
, bound
, noerror
, count
;
1652 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
1655 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
1657 "Search forward from point for regular expression REGEXP.\n\
1658 Find the longest match in accord with Posix regular expression rules.\n\
1659 Set point to the end of the occurrence found, and return point.\n\
1660 An optional second argument bounds the search; it is a buffer position.\n\
1661 The match found must not extend after that position.\n\
1662 Optional third argument, if t, means if fail just return nil (no error).\n\
1663 If not nil and not t, move to limit of search and return nil.\n\
1664 Optional fourth argument is repeat count--search for successive occurrences.\n\
1665 See also the functions `match-beginning', `match-end' and `replace-match'.")
1666 (regexp
, bound
, noerror
, count
)
1667 Lisp_Object regexp
, bound
, noerror
, count
;
1669 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
1672 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
1673 "Replace text matched by last search with NEWTEXT.\n\
1674 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.\n\
1675 Otherwise maybe capitalize the whole text, or maybe just word initials,\n\
1676 based on the replaced text.\n\
1677 If the replaced text has only capital letters\n\
1678 and has at least one multiletter word, convert NEWTEXT to all caps.\n\
1679 If the replaced text has at least one word starting with a capital letter,\n\
1680 then capitalize each word in NEWTEXT.\n\n\
1681 If third arg LITERAL is non-nil, insert NEWTEXT literally.\n\
1682 Otherwise treat `\\' as special:\n\
1683 `\\&' in NEWTEXT means substitute original matched text.\n\
1684 `\\N' means substitute what matched the Nth `\\(...\\)'.\n\
1685 If Nth parens didn't match, substitute nothing.\n\
1686 `\\\\' means insert one `\\'.\n\
1687 FIXEDCASE and LITERAL are optional arguments.\n\
1688 Leaves point at end of replacement text.\n\
1690 The optional fourth argument STRING can be a string to modify.\n\
1691 In that case, this function creates and returns a new string\n\
1692 which is made by replacing the part of STRING that was matched.\n\
1694 The optional fifth argument SUBEXP specifies a subexpression of the match.\n\
1695 It says to replace just that subexpression instead of the whole match.\n\
1696 This is useful only after a regular expression search or match\n\
1697 since only regular expressions have distinguished subexpressions.")
1698 (newtext
, fixedcase
, literal
, string
, subexp
)
1699 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
1701 enum { nochange
, all_caps
, cap_initial
} case_action
;
1702 register int pos
, last
;
1703 int some_multiletter_word
;
1706 int some_nonuppercase_initial
;
1707 register int c
, prevc
;
1711 CHECK_STRING (newtext
, 0);
1713 if (! NILP (string
))
1714 CHECK_STRING (string
, 4);
1716 case_action
= nochange
; /* We tried an initialization */
1717 /* but some C compilers blew it */
1719 if (search_regs
.num_regs
<= 0)
1720 error ("replace-match called before any match found");
1726 CHECK_NUMBER (subexp
, 3);
1727 sub
= XINT (subexp
);
1728 if (sub
< 0 || sub
>= search_regs
.num_regs
)
1729 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
1734 if (search_regs
.start
[sub
] < BEGV
1735 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
1736 || search_regs
.end
[sub
] > ZV
)
1737 args_out_of_range (make_number (search_regs
.start
[sub
]),
1738 make_number (search_regs
.end
[sub
]));
1742 if (search_regs
.start
[sub
] < 0
1743 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
1744 || search_regs
.end
[sub
] > XSTRING (string
)->size
)
1745 args_out_of_range (make_number (search_regs
.start
[sub
]),
1746 make_number (search_regs
.end
[sub
]));
1749 if (NILP (fixedcase
))
1751 /* Decide how to casify by examining the matched text. */
1753 last
= search_regs
.end
[sub
];
1755 case_action
= all_caps
;
1757 /* some_multiletter_word is set nonzero if any original word
1758 is more than one letter long. */
1759 some_multiletter_word
= 0;
1761 some_nonuppercase_initial
= 0;
1764 for (pos
= search_regs
.start
[sub
]; pos
< last
; pos
++)
1767 c
= FETCH_BYTE (pos
);
1769 c
= XSTRING (string
)->data
[pos
];
1773 /* Cannot be all caps if any original char is lower case */
1776 if (SYNTAX (prevc
) != Sword
)
1777 some_nonuppercase_initial
= 1;
1779 some_multiletter_word
= 1;
1781 else if (!NOCASEP (c
))
1784 if (SYNTAX (prevc
) != Sword
)
1787 some_multiletter_word
= 1;
1791 /* If the initial is a caseless word constituent,
1792 treat that like a lowercase initial. */
1793 if (SYNTAX (prevc
) != Sword
)
1794 some_nonuppercase_initial
= 1;
1800 /* Convert to all caps if the old text is all caps
1801 and has at least one multiletter word. */
1802 if (! some_lowercase
&& some_multiletter_word
)
1803 case_action
= all_caps
;
1804 /* Capitalize each word, if the old text has all capitalized words. */
1805 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
1806 case_action
= cap_initial
;
1807 else if (!some_nonuppercase_initial
&& some_uppercase
)
1808 /* Should x -> yz, operating on X, give Yz or YZ?
1809 We'll assume the latter. */
1810 case_action
= all_caps
;
1812 case_action
= nochange
;
1815 /* Do replacement in a string. */
1818 Lisp_Object before
, after
;
1820 before
= Fsubstring (string
, make_number (0),
1821 make_number (search_regs
.start
[sub
]));
1822 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
1824 /* Do case substitution into NEWTEXT if desired. */
1828 /* We build up the substituted string in ACCUM. */
1834 for (pos
= 0; pos
< XSTRING (newtext
)->size
; pos
++)
1838 int delbackslash
= 0;
1840 c
= XSTRING (newtext
)->data
[pos
];
1843 c
= XSTRING (newtext
)->data
[++pos
];
1846 substart
= search_regs
.start
[sub
];
1847 subend
= search_regs
.end
[sub
];
1849 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
1851 if (search_regs
.start
[c
- '0'] >= 0)
1853 substart
= search_regs
.start
[c
- '0'];
1854 subend
= search_regs
.end
[c
- '0'];
1862 if (pos
- 1 != lastpos
+ 1)
1863 middle
= Fsubstring (newtext
,
1864 make_number (lastpos
+ 1),
1865 make_number (pos
- 1));
1868 accum
= concat3 (accum
, middle
,
1869 Fsubstring (string
, make_number (substart
),
1870 make_number (subend
)));
1873 else if (delbackslash
)
1875 middle
= Fsubstring (newtext
, make_number (lastpos
+ 1),
1877 accum
= concat2 (accum
, middle
);
1882 if (pos
!= lastpos
+ 1)
1883 middle
= Fsubstring (newtext
, make_number (lastpos
+ 1),
1888 newtext
= concat2 (accum
, middle
);
1891 if (case_action
== all_caps
)
1892 newtext
= Fupcase (newtext
);
1893 else if (case_action
== cap_initial
)
1894 newtext
= Fupcase_initials (newtext
);
1896 return concat3 (before
, newtext
, after
);
1899 /* We insert the replacement text before the old text, and then
1900 delete the original text. This means that markers at the
1901 beginning or end of the original will float to the corresponding
1902 position in the replacement. */
1903 SET_PT (search_regs
.start
[sub
]);
1904 if (!NILP (literal
))
1905 Finsert_and_inherit (1, &newtext
);
1908 struct gcpro gcpro1
;
1911 for (pos
= 0; pos
< XSTRING (newtext
)->size
; pos
++)
1913 int offset
= PT
- search_regs
.start
[sub
];
1915 c
= XSTRING (newtext
)->data
[pos
];
1918 c
= XSTRING (newtext
)->data
[++pos
];
1920 Finsert_buffer_substring
1921 (Fcurrent_buffer (),
1922 make_number (search_regs
.start
[sub
] + offset
),
1923 make_number (search_regs
.end
[sub
] + offset
));
1924 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
1926 if (search_regs
.start
[c
- '0'] >= 1)
1927 Finsert_buffer_substring
1928 (Fcurrent_buffer (),
1929 make_number (search_regs
.start
[c
- '0'] + offset
),
1930 make_number (search_regs
.end
[c
- '0'] + offset
));
1941 inslen
= PT
- (search_regs
.start
[sub
]);
1942 del_range (search_regs
.start
[sub
] + inslen
, search_regs
.end
[sub
] + inslen
);
1944 if (case_action
== all_caps
)
1945 Fupcase_region (make_number (PT
- inslen
), make_number (PT
));
1946 else if (case_action
== cap_initial
)
1947 Fupcase_initials_region (make_number (PT
- inslen
), make_number (PT
));
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
;
2210 CHECK_STRING (string
, 0);
2212 temp
= (unsigned char *) alloca (XSTRING (string
)->size
* 2);
2214 /* Now copy the data into the new string, inserting escapes. */
2216 in
= XSTRING (string
)->data
;
2217 end
= in
+ XSTRING (string
)->size
;
2220 for (; in
!= end
; in
++)
2222 if (*in
== '[' || *in
== ']'
2223 || *in
== '*' || *in
== '.' || *in
== '\\'
2224 || *in
== '?' || *in
== '+'
2225 || *in
== '^' || *in
== '$')
2230 return make_string (temp
, out
- temp
);
2237 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
2239 searchbufs
[i
].buf
.allocated
= 100;
2240 searchbufs
[i
].buf
.buffer
= (unsigned char *) malloc (100);
2241 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
2242 searchbufs
[i
].regexp
= Qnil
;
2243 staticpro (&searchbufs
[i
].regexp
);
2244 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
2246 searchbuf_head
= &searchbufs
[0];
2248 Qsearch_failed
= intern ("search-failed");
2249 staticpro (&Qsearch_failed
);
2250 Qinvalid_regexp
= intern ("invalid-regexp");
2251 staticpro (&Qinvalid_regexp
);
2253 Fput (Qsearch_failed
, Qerror_conditions
,
2254 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
2255 Fput (Qsearch_failed
, Qerror_message
,
2256 build_string ("Search failed"));
2258 Fput (Qinvalid_regexp
, Qerror_conditions
,
2259 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
2260 Fput (Qinvalid_regexp
, Qerror_message
,
2261 build_string ("Invalid regexp"));
2263 last_thing_searched
= Qnil
;
2264 staticpro (&last_thing_searched
);
2266 defsubr (&Slooking_at
);
2267 defsubr (&Sposix_looking_at
);
2268 defsubr (&Sstring_match
);
2269 defsubr (&Sposix_string_match
);
2270 defsubr (&Sskip_chars_forward
);
2271 defsubr (&Sskip_chars_backward
);
2272 defsubr (&Sskip_syntax_forward
);
2273 defsubr (&Sskip_syntax_backward
);
2274 defsubr (&Ssearch_forward
);
2275 defsubr (&Ssearch_backward
);
2276 defsubr (&Sword_search_forward
);
2277 defsubr (&Sword_search_backward
);
2278 defsubr (&Sre_search_forward
);
2279 defsubr (&Sre_search_backward
);
2280 defsubr (&Sposix_search_forward
);
2281 defsubr (&Sposix_search_backward
);
2282 defsubr (&Sreplace_match
);
2283 defsubr (&Smatch_beginning
);
2284 defsubr (&Smatch_end
);
2285 defsubr (&Smatch_data
);
2286 defsubr (&Sstore_match_data
);
2287 defsubr (&Sregexp_quote
);