1 /* String search routines for GNU Emacs.
2 Copyright (C) 1985, 86,87,93,94,97,98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU Emacs.
6 GNU Emacs is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Emacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Emacs; see the file COPYING. If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
28 #include "region-cache.h"
30 #include "blockinput.h"
31 #include "intervals.h"
33 #include <sys/types.h>
36 #define REGEXP_CACHE_SIZE 20
38 /* If the regexp is non-nil, then the buffer contains the compiled form
39 of that regexp, suitable for searching. */
42 struct regexp_cache
*next
;
44 struct re_pattern_buffer buf
;
46 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
50 /* The instances of that struct. */
51 struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
53 /* The head of the linked list; points to the most recently used buffer. */
54 struct regexp_cache
*searchbuf_head
;
57 /* Every call to re_match, etc., must pass &search_regs as the regs
58 argument unless you can show it is unnecessary (i.e., if re_match
59 is certainly going to be called again before region-around-match
62 Since the registers are now dynamically allocated, we need to make
63 sure not to refer to the Nth register before checking that it has
64 been allocated by checking search_regs.num_regs.
66 The regex code keeps track of whether it has allocated the search
67 buffer using bits in the re_pattern_buffer. This means that whenever
68 you compile a new pattern, it completely forgets whether it has
69 allocated any registers, and will allocate new registers the next
70 time you call a searching or matching function. Therefore, we need
71 to call re_set_registers after compiling a new pattern or after
72 setting the match registers, so that the regex functions will be
73 able to free or re-allocate it properly. */
74 static struct re_registers search_regs
;
76 /* The buffer in which the last search was performed, or
77 Qt if the last search was done in a string;
78 Qnil if no searching has been done yet. */
79 static Lisp_Object last_thing_searched
;
81 /* error condition signaled when regexp compile_pattern fails */
83 Lisp_Object Qinvalid_regexp
;
85 static void set_search_regs ();
86 static void save_search_regs ();
87 static int simple_search ();
88 static int boyer_moore ();
89 static int search_buffer ();
94 error ("Stack overflow in regexp matcher");
97 /* Compile a regexp and signal a Lisp error if anything goes wrong.
98 PATTERN is the pattern to compile.
99 CP is the place to put the result.
100 TRANSLATE is a translation table for ignoring case, or nil for none.
101 REGP is the structure that says where to store the "register"
102 values that will result from matching this pattern.
103 If it is 0, we should compile the pattern not to record any
104 subexpression bounds.
105 POSIX is nonzero if we want full backtracking (POSIX style)
106 for this pattern. 0 means backtrack only enough to get a valid match.
107 MULTIBYTE is nonzero if we want to handle multibyte characters in
108 PATTERN. 0 means all multibyte characters are recognized just as
109 sequences of binary data. */
112 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
)
113 struct regexp_cache
*cp
;
115 Lisp_Object translate
;
116 struct re_registers
*regp
;
120 unsigned char *raw_pattern
;
121 int raw_pattern_size
;
125 /* MULTIBYTE says whether the text to be searched is multibyte.
126 We must convert PATTERN to match that, or we will not really
127 find things right. */
129 if (multibyte
== STRING_MULTIBYTE (pattern
))
131 raw_pattern
= (unsigned char *) XSTRING (pattern
)->data
;
132 raw_pattern_size
= STRING_BYTES (XSTRING (pattern
));
136 raw_pattern_size
= count_size_as_multibyte (XSTRING (pattern
)->data
,
137 XSTRING (pattern
)->size
);
138 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
139 copy_text (XSTRING (pattern
)->data
, raw_pattern
,
140 XSTRING (pattern
)->size
, 0, 1);
144 /* Converting multibyte to single-byte.
146 ??? Perhaps this conversion should be done in a special way
147 by subtracting nonascii-insert-offset from each non-ASCII char,
148 so that only the multibyte chars which really correspond to
149 the chosen single-byte character set can possibly match. */
150 raw_pattern_size
= XSTRING (pattern
)->size
;
151 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
152 copy_text (XSTRING (pattern
)->data
, raw_pattern
,
153 STRING_BYTES (XSTRING (pattern
)), 1, 0);
157 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
159 cp
->buf
.multibyte
= multibyte
;
161 old
= re_set_syntax (RE_SYNTAX_EMACS
162 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
163 val
= (char *) re_compile_pattern ((char *)raw_pattern
,
164 raw_pattern_size
, &cp
->buf
);
168 Fsignal (Qinvalid_regexp
, Fcons (build_string (val
), Qnil
));
170 cp
->regexp
= Fcopy_sequence (pattern
);
173 /* Shrink each compiled regexp buffer in the cache
174 to the size actually used right now.
175 This is called from garbage collection. */
178 shrink_regexp_cache ()
180 struct regexp_cache
*cp
;
182 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
184 cp
->buf
.allocated
= cp
->buf
.used
;
186 = (unsigned char *) realloc (cp
->buf
.buffer
, cp
->buf
.used
);
190 /* Compile a regexp if necessary, but first check to see if there's one in
192 PATTERN is the pattern to compile.
193 TRANSLATE is a translation table for ignoring case, or nil for none.
194 REGP is the structure that says where to store the "register"
195 values that will result from matching this pattern.
196 If it is 0, we should compile the pattern not to record any
197 subexpression bounds.
198 POSIX is nonzero if we want full backtracking (POSIX style)
199 for this pattern. 0 means backtrack only enough to get a valid match. */
201 struct re_pattern_buffer
*
202 compile_pattern (pattern
, regp
, translate
, posix
, multibyte
)
204 struct re_registers
*regp
;
205 Lisp_Object translate
;
206 int posix
, multibyte
;
208 struct regexp_cache
*cp
, **cpp
;
210 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
213 /* Entries are initialized to nil, and may be set to nil by
214 compile_pattern_1 if the pattern isn't valid. Don't apply
215 XSTRING in those cases. However, compile_pattern_1 is only
216 applied to the cache entry we pick here to reuse. So nil
217 should never appear before a non-nil entry. */
218 if (NILP (cp
->regexp
))
220 if (XSTRING (cp
->regexp
)->size
== XSTRING (pattern
)->size
221 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
222 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
223 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
224 && cp
->posix
== posix
225 && cp
->buf
.multibyte
== multibyte
)
228 /* If we're at the end of the cache, compile into the nil cell
229 we found, or the last (least recently used) cell with a
234 compile_pattern_1 (cp
, pattern
, translate
, regp
, posix
, multibyte
);
239 /* When we get here, cp (aka *cpp) contains the compiled pattern,
240 either because we found it in the cache or because we just compiled it.
241 Move it to the front of the queue to mark it as most recently used. */
243 cp
->next
= searchbuf_head
;
246 /* Advise the searching functions about the space we have allocated
247 for register data. */
249 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
254 /* Error condition used for failing searches */
255 Lisp_Object Qsearch_failed
;
261 Fsignal (Qsearch_failed
, Fcons (arg
, Qnil
));
266 looking_at_1 (string
, posix
)
271 unsigned char *p1
, *p2
;
274 struct re_pattern_buffer
*bufp
;
276 if (running_asynch_code
)
279 CHECK_STRING (string
, 0);
280 bufp
= compile_pattern (string
, &search_regs
,
281 (!NILP (current_buffer
->case_fold_search
)
282 ? DOWNCASE_TABLE
: Qnil
),
284 !NILP (current_buffer
->enable_multibyte_characters
));
287 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
289 /* Get pointers and sizes of the two strings
290 that make up the visible portion of the buffer. */
293 s1
= GPT_BYTE
- BEGV_BYTE
;
295 s2
= ZV_BYTE
- GPT_BYTE
;
299 s2
= ZV_BYTE
- BEGV_BYTE
;
304 s1
= ZV_BYTE
- BEGV_BYTE
;
308 re_match_object
= Qnil
;
310 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
311 PT_BYTE
- BEGV_BYTE
, &search_regs
,
312 ZV_BYTE
- BEGV_BYTE
);
318 val
= (0 <= i
? Qt
: Qnil
);
320 for (i
= 0; i
< search_regs
.num_regs
; i
++)
321 if (search_regs
.start
[i
] >= 0)
324 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
326 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
328 XSETBUFFER (last_thing_searched
, current_buffer
);
332 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
333 "Return t if text after point matches regular expression REGEXP.\n\
334 This function modifies the match data that `match-beginning',\n\
335 `match-end' and `match-data' access; save and restore the match\n\
336 data if you want to preserve them.")
340 return looking_at_1 (regexp
, 0);
343 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
344 "Return t if text after point matches regular expression REGEXP.\n\
345 Find the longest match, in accord with Posix regular expression rules.\n\
346 This function modifies the match data that `match-beginning',\n\
347 `match-end' and `match-data' access; save and restore the match\n\
348 data if you want to preserve them.")
352 return looking_at_1 (regexp
, 1);
356 string_match_1 (regexp
, string
, start
, posix
)
357 Lisp_Object regexp
, string
, start
;
361 struct re_pattern_buffer
*bufp
;
365 if (running_asynch_code
)
368 CHECK_STRING (regexp
, 0);
369 CHECK_STRING (string
, 1);
372 pos
= 0, pos_byte
= 0;
375 int len
= XSTRING (string
)->size
;
377 CHECK_NUMBER (start
, 2);
379 if (pos
< 0 && -pos
<= len
)
381 else if (0 > pos
|| pos
> len
)
382 args_out_of_range (string
, start
);
383 pos_byte
= string_char_to_byte (string
, pos
);
386 bufp
= compile_pattern (regexp
, &search_regs
,
387 (!NILP (current_buffer
->case_fold_search
)
388 ? DOWNCASE_TABLE
: Qnil
),
390 STRING_MULTIBYTE (string
));
392 re_match_object
= string
;
394 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
395 STRING_BYTES (XSTRING (string
)), pos_byte
,
396 STRING_BYTES (XSTRING (string
)) - pos_byte
,
399 last_thing_searched
= Qt
;
402 if (val
< 0) return Qnil
;
404 for (i
= 0; i
< search_regs
.num_regs
; i
++)
405 if (search_regs
.start
[i
] >= 0)
408 = string_byte_to_char (string
, search_regs
.start
[i
]);
410 = string_byte_to_char (string
, search_regs
.end
[i
]);
413 return make_number (string_byte_to_char (string
, val
));
416 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
417 "Return index of start of first match for REGEXP in STRING, or nil.\n\
418 Case is ignored if `case-fold-search' is non-nil in the current buffer.\n\
419 If third arg START is non-nil, start search at that index in STRING.\n\
420 For index of first char beyond the match, do (match-end 0).\n\
421 `match-end' and `match-beginning' also give indices of substrings\n\
422 matched by parenthesis constructs in the pattern.")
423 (regexp
, string
, start
)
424 Lisp_Object regexp
, string
, start
;
426 return string_match_1 (regexp
, string
, start
, 0);
429 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
430 "Return index of start of first match for REGEXP in STRING, or nil.\n\
431 Find the longest match, in accord with Posix regular expression rules.\n\
432 Case is ignored if `case-fold-search' is non-nil in the current buffer.\n\
433 If third arg START is non-nil, start search at that index in STRING.\n\
434 For index of first char beyond the match, do (match-end 0).\n\
435 `match-end' and `match-beginning' also give indices of substrings\n\
436 matched by parenthesis constructs in the pattern.")
437 (regexp
, string
, start
)
438 Lisp_Object regexp
, string
, start
;
440 return string_match_1 (regexp
, string
, start
, 1);
443 /* Match REGEXP against STRING, searching all of STRING,
444 and return the index of the match, or negative on failure.
445 This does not clobber the match data. */
448 fast_string_match (regexp
, string
)
449 Lisp_Object regexp
, string
;
452 struct re_pattern_buffer
*bufp
;
454 bufp
= compile_pattern (regexp
, 0, Qnil
,
455 0, STRING_MULTIBYTE (string
));
457 re_match_object
= string
;
459 val
= re_search (bufp
, (char *) XSTRING (string
)->data
,
460 STRING_BYTES (XSTRING (string
)), 0,
461 STRING_BYTES (XSTRING (string
)), 0);
466 /* Match REGEXP against STRING, searching all of STRING ignoring case,
467 and return the index of the match, or negative on failure.
468 This does not clobber the match data.
469 We assume that STRING contains single-byte characters. */
471 extern Lisp_Object Vascii_downcase_table
;
474 fast_c_string_match_ignore_case (regexp
, string
)
479 struct re_pattern_buffer
*bufp
;
480 int len
= strlen (string
);
482 regexp
= string_make_unibyte (regexp
);
483 re_match_object
= Qt
;
484 bufp
= compile_pattern (regexp
, 0,
485 Vascii_downcase_table
, 0,
488 val
= re_search (bufp
, string
, len
, 0, len
, 0);
493 /* The newline cache: remembering which sections of text have no newlines. */
495 /* If the user has requested newline caching, make sure it's on.
496 Otherwise, make sure it's off.
497 This is our cheezy way of associating an action with the change of
498 state of a buffer-local variable. */
500 newline_cache_on_off (buf
)
503 if (NILP (buf
->cache_long_line_scans
))
505 /* It should be off. */
506 if (buf
->newline_cache
)
508 free_region_cache (buf
->newline_cache
);
509 buf
->newline_cache
= 0;
514 /* It should be on. */
515 if (buf
->newline_cache
== 0)
516 buf
->newline_cache
= new_region_cache ();
521 /* Search for COUNT instances of the character TARGET between START and END.
523 If COUNT is positive, search forwards; END must be >= START.
524 If COUNT is negative, search backwards for the -COUNTth instance;
525 END must be <= START.
526 If COUNT is zero, do anything you please; run rogue, for all I care.
528 If END is zero, use BEGV or ZV instead, as appropriate for the
529 direction indicated by COUNT.
531 If we find COUNT instances, set *SHORTAGE to zero, and return the
532 position after the COUNTth match. Note that for reverse motion
533 this is not the same as the usual convention for Emacs motion commands.
535 If we don't find COUNT instances before reaching END, set *SHORTAGE
536 to the number of TARGETs left unfound, and return END.
538 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
539 except when inside redisplay. */
542 scan_buffer (target
, start
, end
, count
, shortage
, allow_quit
)
549 struct region_cache
*newline_cache
;
560 if (! end
) end
= BEGV
;
563 newline_cache_on_off (current_buffer
);
564 newline_cache
= current_buffer
->newline_cache
;
569 immediate_quit
= allow_quit
;
574 /* Our innermost scanning loop is very simple; it doesn't know
575 about gaps, buffer ends, or the newline cache. ceiling is
576 the position of the last character before the next such
577 obstacle --- the last character the dumb search loop should
579 int ceiling_byte
= CHAR_TO_BYTE (end
) - 1;
580 int start_byte
= CHAR_TO_BYTE (start
);
583 /* If we're looking for a newline, consult the newline cache
584 to see where we can avoid some scanning. */
585 if (target
== '\n' && newline_cache
)
589 while (region_cache_forward
590 (current_buffer
, newline_cache
, start_byte
, &next_change
))
591 start_byte
= next_change
;
592 immediate_quit
= allow_quit
;
594 /* START should never be after END. */
595 if (start_byte
> ceiling_byte
)
596 start_byte
= ceiling_byte
;
598 /* Now the text after start is an unknown region, and
599 next_change is the position of the next known region. */
600 ceiling_byte
= min (next_change
- 1, ceiling_byte
);
603 /* The dumb loop can only scan text stored in contiguous
604 bytes. BUFFER_CEILING_OF returns the last character
605 position that is contiguous, so the ceiling is the
606 position after that. */
607 tem
= BUFFER_CEILING_OF (start_byte
);
608 ceiling_byte
= min (tem
, ceiling_byte
);
611 /* The termination address of the dumb loop. */
612 register unsigned char *ceiling_addr
613 = BYTE_POS_ADDR (ceiling_byte
) + 1;
614 register unsigned char *cursor
615 = BYTE_POS_ADDR (start_byte
);
616 unsigned char *base
= cursor
;
618 while (cursor
< ceiling_addr
)
620 unsigned char *scan_start
= cursor
;
623 while (*cursor
!= target
&& ++cursor
< ceiling_addr
)
626 /* If we're looking for newlines, cache the fact that
627 the region from start to cursor is free of them. */
628 if (target
== '\n' && newline_cache
)
629 know_region_cache (current_buffer
, newline_cache
,
630 start_byte
+ scan_start
- base
,
631 start_byte
+ cursor
- base
);
633 /* Did we find the target character? */
634 if (cursor
< ceiling_addr
)
639 return BYTE_TO_CHAR (start_byte
+ cursor
- base
+ 1);
645 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
651 /* The last character to check before the next obstacle. */
652 int ceiling_byte
= CHAR_TO_BYTE (end
);
653 int start_byte
= CHAR_TO_BYTE (start
);
656 /* Consult the newline cache, if appropriate. */
657 if (target
== '\n' && newline_cache
)
661 while (region_cache_backward
662 (current_buffer
, newline_cache
, start_byte
, &next_change
))
663 start_byte
= next_change
;
664 immediate_quit
= allow_quit
;
666 /* Start should never be at or before end. */
667 if (start_byte
<= ceiling_byte
)
668 start_byte
= ceiling_byte
+ 1;
670 /* Now the text before start is an unknown region, and
671 next_change is the position of the next known region. */
672 ceiling_byte
= max (next_change
, ceiling_byte
);
675 /* Stop scanning before the gap. */
676 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
677 ceiling_byte
= max (tem
, ceiling_byte
);
680 /* The termination address of the dumb loop. */
681 register unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
682 register unsigned char *cursor
= BYTE_POS_ADDR (start_byte
- 1);
683 unsigned char *base
= cursor
;
685 while (cursor
>= ceiling_addr
)
687 unsigned char *scan_start
= cursor
;
689 while (*cursor
!= target
&& --cursor
>= ceiling_addr
)
692 /* If we're looking for newlines, cache the fact that
693 the region from after the cursor to start is free of them. */
694 if (target
== '\n' && newline_cache
)
695 know_region_cache (current_buffer
, newline_cache
,
696 start_byte
+ cursor
- base
,
697 start_byte
+ scan_start
- base
);
699 /* Did we find the target character? */
700 if (cursor
>= ceiling_addr
)
705 return BYTE_TO_CHAR (start_byte
+ cursor
- base
);
711 start
= BYTE_TO_CHAR (start_byte
+ cursor
- base
);
717 *shortage
= count
* direction
;
721 /* Search for COUNT instances of a line boundary, which means either a
722 newline or (if selective display enabled) a carriage return.
723 Start at START. If COUNT is negative, search backwards.
725 We report the resulting position by calling TEMP_SET_PT_BOTH.
727 If we find COUNT instances. we position after (always after,
728 even if scanning backwards) the COUNTth match, and return 0.
730 If we don't find COUNT instances before reaching the end of the
731 buffer (or the beginning, if scanning backwards), we return
732 the number of line boundaries left unfound, and position at
733 the limit we bumped up against.
735 If ALLOW_QUIT is non-zero, set immediate_quit. That's good to do
736 except in special cases. */
739 scan_newline (start
, start_byte
, limit
, limit_byte
, count
, allow_quit
)
740 int start
, start_byte
;
741 int limit
, limit_byte
;
745 int direction
= ((count
> 0) ? 1 : -1);
747 register unsigned char *cursor
;
750 register int ceiling
;
751 register unsigned char *ceiling_addr
;
753 int old_immediate_quit
= immediate_quit
;
755 /* If we are not in selective display mode,
756 check only for newlines. */
757 int selective_display
= (!NILP (current_buffer
->selective_display
)
758 && !INTEGERP (current_buffer
->selective_display
));
760 /* The code that follows is like scan_buffer
761 but checks for either newline or carriage return. */
766 start_byte
= CHAR_TO_BYTE (start
);
770 while (start_byte
< limit_byte
)
772 ceiling
= BUFFER_CEILING_OF (start_byte
);
773 ceiling
= min (limit_byte
- 1, ceiling
);
774 ceiling_addr
= BYTE_POS_ADDR (ceiling
) + 1;
775 base
= (cursor
= BYTE_POS_ADDR (start_byte
));
778 while (*cursor
!= '\n' && ++cursor
!= ceiling_addr
)
781 if (cursor
!= ceiling_addr
)
785 immediate_quit
= old_immediate_quit
;
786 start_byte
= start_byte
+ cursor
- base
+ 1;
787 start
= BYTE_TO_CHAR (start_byte
);
788 TEMP_SET_PT_BOTH (start
, start_byte
);
792 if (++cursor
== ceiling_addr
)
798 start_byte
+= cursor
- base
;
803 while (start_byte
> limit_byte
)
805 ceiling
= BUFFER_FLOOR_OF (start_byte
- 1);
806 ceiling
= max (limit_byte
, ceiling
);
807 ceiling_addr
= BYTE_POS_ADDR (ceiling
) - 1;
808 base
= (cursor
= BYTE_POS_ADDR (start_byte
- 1) + 1);
811 while (--cursor
!= ceiling_addr
&& *cursor
!= '\n')
814 if (cursor
!= ceiling_addr
)
818 immediate_quit
= old_immediate_quit
;
819 /* Return the position AFTER the match we found. */
820 start_byte
= start_byte
+ cursor
- base
+ 1;
821 start
= BYTE_TO_CHAR (start_byte
);
822 TEMP_SET_PT_BOTH (start
, start_byte
);
829 /* Here we add 1 to compensate for the last decrement
830 of CURSOR, which took it past the valid range. */
831 start_byte
+= cursor
- base
+ 1;
835 TEMP_SET_PT_BOTH (limit
, limit_byte
);
836 immediate_quit
= old_immediate_quit
;
838 return count
* direction
;
842 find_next_newline_no_quit (from
, cnt
)
843 register int from
, cnt
;
845 return scan_buffer ('\n', from
, 0, cnt
, (int *) 0, 0);
848 /* Like find_next_newline, but returns position before the newline,
849 not after, and only search up to TO. This isn't just
850 find_next_newline (...)-1, because you might hit TO. */
853 find_before_next_newline (from
, to
, cnt
)
857 int pos
= scan_buffer ('\n', from
, to
, cnt
, &shortage
, 1);
865 /* Subroutines of Lisp buffer search functions. */
868 search_command (string
, bound
, noerror
, count
, direction
, RE
, posix
)
869 Lisp_Object string
, bound
, noerror
, count
;
880 CHECK_NUMBER (count
, 3);
884 CHECK_STRING (string
, 0);
888 lim
= ZV
, lim_byte
= ZV_BYTE
;
890 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
894 CHECK_NUMBER_COERCE_MARKER (bound
, 1);
896 if (n
> 0 ? lim
< PT
: lim
> PT
)
897 error ("Invalid search bound (wrong side of point)");
899 lim
= ZV
, lim_byte
= ZV_BYTE
;
901 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
903 lim_byte
= CHAR_TO_BYTE (lim
);
906 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
907 (!NILP (current_buffer
->case_fold_search
)
908 ? current_buffer
->case_canon_table
910 (!NILP (current_buffer
->case_fold_search
)
911 ? current_buffer
->case_eqv_table
917 return signal_failure (string
);
918 if (!EQ (noerror
, Qt
))
920 if (lim
< BEGV
|| lim
> ZV
)
922 SET_PT_BOTH (lim
, lim_byte
);
924 #if 0 /* This would be clean, but maybe programs depend on
925 a value of nil here. */
933 if (np
< BEGV
|| np
> ZV
)
938 return make_number (np
);
941 /* Return 1 if REGEXP it matches just one constant string. */
944 trivial_regexp_p (regexp
)
947 int len
= STRING_BYTES (XSTRING (regexp
));
948 unsigned char *s
= XSTRING (regexp
)->data
;
953 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
960 case '|': case '(': case ')': case '`': case '\'': case 'b':
961 case 'B': case '<': case '>': case 'w': case 'W': case 's':
962 case 'S': case '=': case '{': case '}':
963 case 'c': case 'C': /* for categoryspec and notcategoryspec */
964 case '1': case '2': case '3': case '4': case '5':
965 case '6': case '7': case '8': case '9':
973 /* Search for the n'th occurrence of STRING in the current buffer,
974 starting at position POS and stopping at position LIM,
975 treating STRING as a literal string if RE is false or as
976 a regular expression if RE is true.
978 If N is positive, searching is forward and LIM must be greater than POS.
979 If N is negative, searching is backward and LIM must be less than POS.
981 Returns -x if x occurrences remain to be found (x > 0),
982 or else the position at the beginning of the Nth occurrence
983 (if searching backward) or the end (if searching forward).
985 POSIX is nonzero if we want full backtracking (POSIX style)
986 for this pattern. 0 means backtrack only enough to get a valid match. */
988 #define TRANSLATE(out, trt, d) \
994 temp = Faref (trt, make_number (d)); \
995 if (INTEGERP (temp)) \
1006 search_buffer (string
, pos
, pos_byte
, lim
, lim_byte
, n
,
1007 RE
, trt
, inverse_trt
, posix
)
1016 Lisp_Object inverse_trt
;
1019 int len
= XSTRING (string
)->size
;
1020 int len_byte
= STRING_BYTES (XSTRING (string
));
1023 if (running_asynch_code
)
1024 save_search_regs ();
1026 /* Searching 0 times means don't move. */
1027 /* Null string is found at starting position. */
1028 if (len
== 0 || n
== 0)
1030 set_search_regs (pos_byte
, 0);
1034 if (RE
&& !trivial_regexp_p (string
))
1036 unsigned char *p1
, *p2
;
1038 struct re_pattern_buffer
*bufp
;
1040 bufp
= compile_pattern (string
, &search_regs
, trt
, posix
,
1041 !NILP (current_buffer
->enable_multibyte_characters
));
1043 immediate_quit
= 1; /* Quit immediately if user types ^G,
1044 because letting this function finish
1045 can take too long. */
1046 QUIT
; /* Do a pending quit right away,
1047 to avoid paradoxical behavior */
1048 /* Get pointers and sizes of the two strings
1049 that make up the visible portion of the buffer. */
1052 s1
= GPT_BYTE
- BEGV_BYTE
;
1054 s2
= ZV_BYTE
- GPT_BYTE
;
1058 s2
= ZV_BYTE
- BEGV_BYTE
;
1063 s1
= ZV_BYTE
- BEGV_BYTE
;
1066 re_match_object
= Qnil
;
1071 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1072 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1074 /* Don't allow match past current point */
1075 pos_byte
- BEGV_BYTE
);
1078 matcher_overflow ();
1082 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1083 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1084 if (search_regs
.start
[i
] >= 0)
1086 search_regs
.start
[i
]
1087 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1089 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1091 XSETBUFFER (last_thing_searched
, current_buffer
);
1092 /* Set pos to the new position. */
1093 pos
= search_regs
.start
[0];
1105 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1106 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1108 lim_byte
- BEGV_BYTE
);
1111 matcher_overflow ();
1115 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1116 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1117 if (search_regs
.start
[i
] >= 0)
1119 search_regs
.start
[i
]
1120 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1122 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1124 XSETBUFFER (last_thing_searched
, current_buffer
);
1125 pos
= search_regs
.end
[0];
1137 else /* non-RE case */
1139 unsigned char *raw_pattern
, *pat
;
1140 int raw_pattern_size
;
1141 int raw_pattern_size_byte
;
1142 unsigned char *patbuf
;
1143 int multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
1144 unsigned char *base_pat
= XSTRING (string
)->data
;
1145 int charset_base
= -1;
1146 int boyer_moore_ok
= 1;
1148 /* MULTIBYTE says whether the text to be searched is multibyte.
1149 We must convert PATTERN to match that, or we will not really
1150 find things right. */
1152 if (multibyte
== STRING_MULTIBYTE (string
))
1154 raw_pattern
= (unsigned char *) XSTRING (string
)->data
;
1155 raw_pattern_size
= XSTRING (string
)->size
;
1156 raw_pattern_size_byte
= STRING_BYTES (XSTRING (string
));
1160 raw_pattern_size
= XSTRING (string
)->size
;
1161 raw_pattern_size_byte
1162 = count_size_as_multibyte (XSTRING (string
)->data
,
1164 raw_pattern
= (unsigned char *) alloca (raw_pattern_size_byte
+ 1);
1165 copy_text (XSTRING (string
)->data
, raw_pattern
,
1166 XSTRING (string
)->size
, 0, 1);
1170 /* Converting multibyte to single-byte.
1172 ??? Perhaps this conversion should be done in a special way
1173 by subtracting nonascii-insert-offset from each non-ASCII char,
1174 so that only the multibyte chars which really correspond to
1175 the chosen single-byte character set can possibly match. */
1176 raw_pattern_size
= XSTRING (string
)->size
;
1177 raw_pattern_size_byte
= XSTRING (string
)->size
;
1178 raw_pattern
= (unsigned char *) alloca (raw_pattern_size
+ 1);
1179 copy_text (XSTRING (string
)->data
, raw_pattern
,
1180 STRING_BYTES (XSTRING (string
)), 1, 0);
1183 /* Copy and optionally translate the pattern. */
1184 len
= raw_pattern_size
;
1185 len_byte
= raw_pattern_size_byte
;
1186 patbuf
= (unsigned char *) alloca (len_byte
);
1188 base_pat
= raw_pattern
;
1193 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1194 int c
, translated
, inverse
;
1195 int in_charlen
, charlen
;
1197 /* If we got here and the RE flag is set, it's because we're
1198 dealing with a regexp known to be trivial, so the backslash
1199 just quotes the next character. */
1200 if (RE
&& *base_pat
== '\\')
1207 c
= STRING_CHAR_AND_LENGTH (base_pat
, len_byte
, in_charlen
);
1209 /* Translate the character, if requested. */
1210 TRANSLATE (translated
, trt
, c
);
1211 /* If translation changed the byte-length, go back
1212 to the original character. */
1213 charlen
= CHAR_STRING (translated
, str
);
1214 if (in_charlen
!= charlen
)
1217 charlen
= CHAR_STRING (c
, str
);
1220 /* If we are searching for something strange,
1221 an invalid multibyte code, don't use boyer-moore. */
1222 if (! ASCII_BYTE_P (translated
)
1223 && (charlen
== 1 /* 8bit code */
1224 || charlen
!= in_charlen
/* invalid multibyte code */
1228 TRANSLATE (inverse
, inverse_trt
, c
);
1230 /* Did this char actually get translated?
1231 Would any other char get translated into it? */
1232 if (translated
!= c
|| inverse
!= c
)
1234 /* Keep track of which character set row
1235 contains the characters that need translation. */
1236 int charset_base_code
= c
& ~CHAR_FIELD3_MASK
;
1237 if (charset_base
== -1)
1238 charset_base
= charset_base_code
;
1239 else if (charset_base
!= charset_base_code
)
1240 /* If two different rows appear, needing translation,
1241 then we cannot use boyer_moore search. */
1245 /* Store this character into the translated pattern. */
1246 bcopy (str
, pat
, charlen
);
1248 base_pat
+= in_charlen
;
1249 len_byte
-= in_charlen
;
1254 /* Unibyte buffer. */
1260 /* If we got here and the RE flag is set, it's because we're
1261 dealing with a regexp known to be trivial, so the backslash
1262 just quotes the next character. */
1263 if (RE
&& *base_pat
== '\\')
1269 TRANSLATE (translated
, trt
, c
);
1270 *pat
++ = translated
;
1274 len_byte
= pat
- patbuf
;
1275 len
= raw_pattern_size
;
1276 pat
= base_pat
= patbuf
;
1279 return boyer_moore (n
, pat
, len
, len_byte
, trt
, inverse_trt
,
1280 pos
, pos_byte
, lim
, lim_byte
,
1283 return simple_search (n
, pat
, len
, len_byte
, trt
,
1284 pos
, pos_byte
, lim
, lim_byte
);
1288 /* Do a simple string search N times for the string PAT,
1289 whose length is LEN/LEN_BYTE,
1290 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1291 TRT is the translation table.
1293 Return the character position where the match is found.
1294 Otherwise, if M matches remained to be found, return -M.
1296 This kind of search works regardless of what is in PAT and
1297 regardless of what is in TRT. It is used in cases where
1298 boyer_moore cannot work. */
1301 simple_search (n
, pat
, len
, len_byte
, trt
, pos
, pos_byte
, lim
, lim_byte
)
1309 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1310 int forward
= n
> 0;
1312 if (lim
> pos
&& multibyte
)
1317 /* Try matching at position POS. */
1319 int this_pos_byte
= pos_byte
;
1321 int this_len_byte
= len_byte
;
1322 unsigned char *p
= pat
;
1323 if (pos
+ len
> lim
)
1326 while (this_len
> 0)
1328 int charlen
, buf_charlen
;
1331 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1332 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1333 ZV_BYTE
- this_pos_byte
,
1335 TRANSLATE (buf_ch
, trt
, buf_ch
);
1337 if (buf_ch
!= pat_ch
)
1340 this_len_byte
-= charlen
;
1344 this_pos_byte
+= buf_charlen
;
1351 pos_byte
+= len_byte
;
1355 INC_BOTH (pos
, pos_byte
);
1365 /* Try matching at position POS. */
1368 unsigned char *p
= pat
;
1370 if (pos
+ len
> lim
)
1373 while (this_len
> 0)
1376 int buf_ch
= FETCH_BYTE (this_pos
);
1377 TRANSLATE (buf_ch
, trt
, buf_ch
);
1379 if (buf_ch
!= pat_ch
)
1397 /* Backwards search. */
1398 else if (lim
< pos
&& multibyte
)
1403 /* Try matching at position POS. */
1404 int this_pos
= pos
- len
;
1405 int this_pos_byte
= pos_byte
- len_byte
;
1407 int this_len_byte
= len_byte
;
1408 unsigned char *p
= pat
;
1410 if (pos
- len
< lim
)
1413 while (this_len
> 0)
1415 int charlen
, buf_charlen
;
1418 pat_ch
= STRING_CHAR_AND_LENGTH (p
, this_len_byte
, charlen
);
1419 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1420 ZV_BYTE
- this_pos_byte
,
1422 TRANSLATE (buf_ch
, trt
, buf_ch
);
1424 if (buf_ch
!= pat_ch
)
1427 this_len_byte
-= charlen
;
1430 this_pos_byte
+= buf_charlen
;
1437 pos_byte
-= len_byte
;
1441 DEC_BOTH (pos
, pos_byte
);
1451 /* Try matching at position POS. */
1452 int this_pos
= pos
- len
;
1454 unsigned char *p
= pat
;
1456 if (pos
- len
< lim
)
1459 while (this_len
> 0)
1462 int buf_ch
= FETCH_BYTE (this_pos
);
1463 TRANSLATE (buf_ch
, trt
, buf_ch
);
1465 if (buf_ch
!= pat_ch
)
1487 set_search_regs ((multibyte
? pos_byte
: pos
) - len_byte
, len_byte
);
1489 set_search_regs (multibyte
? pos_byte
: pos
, len_byte
);
1499 /* Do Boyer-Moore search N times for the string PAT,
1500 whose length is LEN/LEN_BYTE,
1501 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1502 DIRECTION says which direction we search in.
1503 TRT and INVERSE_TRT are translation tables.
1505 This kind of search works if all the characters in PAT that have
1506 nontrivial translation are the same aside from the last byte. This
1507 makes it possible to translate just the last byte of a character,
1508 and do so after just a simple test of the context.
1510 If that criterion is not satisfied, do not call this function. */
1513 boyer_moore (n
, base_pat
, len
, len_byte
, trt
, inverse_trt
,
1514 pos
, pos_byte
, lim
, lim_byte
, charset_base
)
1516 unsigned char *base_pat
;
1519 Lisp_Object inverse_trt
;
1524 int direction
= ((n
> 0) ? 1 : -1);
1525 register int dirlen
;
1526 int infinity
, limit
, stride_for_teases
= 0;
1527 register int *BM_tab
;
1529 register unsigned char *cursor
, *p_limit
;
1531 unsigned char *pat
, *pat_end
;
1532 int multibyte
= ! NILP (current_buffer
->enable_multibyte_characters
);
1534 unsigned char simple_translate
[0400];
1535 int translate_prev_byte
= 0;
1536 int translate_anteprev_byte
= 0;
1539 int BM_tab_space
[0400];
1540 BM_tab
= &BM_tab_space
[0];
1542 BM_tab
= (int *) alloca (0400 * sizeof (int));
1544 /* The general approach is that we are going to maintain that we know */
1545 /* the first (closest to the present position, in whatever direction */
1546 /* we're searching) character that could possibly be the last */
1547 /* (furthest from present position) character of a valid match. We */
1548 /* advance the state of our knowledge by looking at that character */
1549 /* and seeing whether it indeed matches the last character of the */
1550 /* pattern. If it does, we take a closer look. If it does not, we */
1551 /* move our pointer (to putative last characters) as far as is */
1552 /* logically possible. This amount of movement, which I call a */
1553 /* stride, will be the length of the pattern if the actual character */
1554 /* appears nowhere in the pattern, otherwise it will be the distance */
1555 /* from the last occurrence of that character to the end of the */
1557 /* As a coding trick, an enormous stride is coded into the table for */
1558 /* characters that match the last character. This allows use of only */
1559 /* a single test, a test for having gone past the end of the */
1560 /* permissible match region, to test for both possible matches (when */
1561 /* the stride goes past the end immediately) and failure to */
1562 /* match (where you get nudged past the end one stride at a time). */
1564 /* Here we make a "mickey mouse" BM table. The stride of the search */
1565 /* is determined only by the last character of the putative match. */
1566 /* If that character does not match, we will stride the proper */
1567 /* distance to propose a match that superimposes it on the last */
1568 /* instance of a character that matches it (per trt), or misses */
1569 /* it entirely if there is none. */
1571 dirlen
= len_byte
* direction
;
1572 infinity
= dirlen
- (lim_byte
+ pos_byte
+ len_byte
+ len_byte
) * direction
;
1574 /* Record position after the end of the pattern. */
1575 pat_end
= base_pat
+ len_byte
;
1576 /* BASE_PAT points to a character that we start scanning from.
1577 It is the first character in a forward search,
1578 the last character in a backward search. */
1580 base_pat
= pat_end
- 1;
1582 BM_tab_base
= BM_tab
;
1584 j
= dirlen
; /* to get it in a register */
1585 /* A character that does not appear in the pattern induces a */
1586 /* stride equal to the pattern length. */
1587 while (BM_tab_base
!= BM_tab
)
1595 /* We use this for translation, instead of TRT itself.
1596 We fill this in to handle the characters that actually
1597 occur in the pattern. Others don't matter anyway! */
1598 bzero (simple_translate
, sizeof simple_translate
);
1599 for (i
= 0; i
< 0400; i
++)
1600 simple_translate
[i
] = i
;
1603 while (i
!= infinity
)
1605 unsigned char *ptr
= base_pat
+ i
;
1613 int this_translated
= 1;
1616 /* Is *PTR the last byte of a character? */
1617 && (pat_end
- ptr
== 1 || CHAR_HEAD_P (ptr
[1])))
1619 unsigned char *charstart
= ptr
;
1620 while (! CHAR_HEAD_P (*charstart
))
1622 untranslated
= STRING_CHAR (charstart
, ptr
- charstart
+ 1);
1623 if (charset_base
== (untranslated
& ~CHAR_FIELD3_MASK
))
1625 TRANSLATE (ch
, trt
, untranslated
);
1626 if (! CHAR_HEAD_P (*ptr
))
1628 translate_prev_byte
= ptr
[-1];
1629 if (! CHAR_HEAD_P (translate_prev_byte
))
1630 translate_anteprev_byte
= ptr
[-2];
1635 this_translated
= 0;
1639 else if (!multibyte
)
1640 TRANSLATE (ch
, trt
, *ptr
);
1644 this_translated
= 0;
1648 j
= ((unsigned char) ch
) | 0200;
1650 j
= (unsigned char) ch
;
1653 stride_for_teases
= BM_tab
[j
];
1655 BM_tab
[j
] = dirlen
- i
;
1656 /* A translation table is accompanied by its inverse -- see */
1657 /* comment following downcase_table for details */
1658 if (this_translated
)
1660 int starting_ch
= ch
;
1664 TRANSLATE (ch
, inverse_trt
, ch
);
1666 j
= ((unsigned char) ch
) | 0200;
1668 j
= (unsigned char) ch
;
1670 /* For all the characters that map into CH,
1671 set up simple_translate to map the last byte
1673 simple_translate
[j
] = starting_j
;
1674 if (ch
== starting_ch
)
1676 BM_tab
[j
] = dirlen
- i
;
1685 stride_for_teases
= BM_tab
[j
];
1686 BM_tab
[j
] = dirlen
- i
;
1688 /* stride_for_teases tells how much to stride if we get a */
1689 /* match on the far character but are subsequently */
1690 /* disappointed, by recording what the stride would have been */
1691 /* for that character if the last character had been */
1694 infinity
= dirlen
- infinity
;
1695 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1696 /* loop invariant - POS_BYTE points at where last char (first
1697 char if reverse) of pattern would align in a possible match. */
1701 unsigned char *tail_end_ptr
;
1703 /* It's been reported that some (broken) compiler thinks that
1704 Boolean expressions in an arithmetic context are unsigned.
1705 Using an explicit ?1:0 prevents this. */
1706 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1708 return (n
* (0 - direction
));
1709 /* First we do the part we can by pointers (maybe nothing) */
1712 limit
= pos_byte
- dirlen
+ direction
;
1715 limit
= BUFFER_CEILING_OF (limit
);
1716 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1717 can take on without hitting edge of buffer or the gap. */
1718 limit
= min (limit
, pos_byte
+ 20000);
1719 limit
= min (limit
, lim_byte
- 1);
1723 limit
= BUFFER_FLOOR_OF (limit
);
1724 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1725 can take on without hitting edge of buffer or the gap. */
1726 limit
= max (limit
, pos_byte
- 20000);
1727 limit
= max (limit
, lim_byte
);
1729 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1730 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1732 if ((limit
- pos_byte
) * direction
> 20)
1736 p_limit
= BYTE_POS_ADDR (limit
);
1737 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1738 /* In this loop, pos + cursor - p2 is the surrogate for pos */
1739 while (1) /* use one cursor setting as long as i can */
1741 if (direction
> 0) /* worth duplicating */
1743 /* Use signed comparison if appropriate
1744 to make cursor+infinity sure to be > p_limit.
1745 Assuming that the buffer lies in a range of addresses
1746 that are all "positive" (as ints) or all "negative",
1747 either kind of comparison will work as long
1748 as we don't step by infinity. So pick the kind
1749 that works when we do step by infinity. */
1750 if ((EMACS_INT
) (p_limit
+ infinity
) > (EMACS_INT
) p_limit
)
1751 while ((EMACS_INT
) cursor
<= (EMACS_INT
) p_limit
)
1752 cursor
+= BM_tab
[*cursor
];
1754 while ((EMACS_UINT
) cursor
<= (EMACS_UINT
) p_limit
)
1755 cursor
+= BM_tab
[*cursor
];
1759 if ((EMACS_INT
) (p_limit
+ infinity
) < (EMACS_INT
) p_limit
)
1760 while ((EMACS_INT
) cursor
>= (EMACS_INT
) p_limit
)
1761 cursor
+= BM_tab
[*cursor
];
1763 while ((EMACS_UINT
) cursor
>= (EMACS_UINT
) p_limit
)
1764 cursor
+= BM_tab
[*cursor
];
1766 /* If you are here, cursor is beyond the end of the searched region. */
1767 /* This can happen if you match on the far character of the pattern, */
1768 /* because the "stride" of that character is infinity, a number able */
1769 /* to throw you well beyond the end of the search. It can also */
1770 /* happen if you fail to match within the permitted region and would */
1771 /* otherwise try a character beyond that region */
1772 if ((cursor
- p_limit
) * direction
<= len_byte
)
1773 break; /* a small overrun is genuine */
1774 cursor
-= infinity
; /* large overrun = hit */
1775 i
= dirlen
- direction
;
1778 while ((i
-= direction
) + direction
!= 0)
1781 cursor
-= direction
;
1782 /* Translate only the last byte of a character. */
1784 || ((cursor
== tail_end_ptr
1785 || CHAR_HEAD_P (cursor
[1]))
1786 && (CHAR_HEAD_P (cursor
[0])
1787 || (translate_prev_byte
== cursor
[-1]
1788 && (CHAR_HEAD_P (translate_prev_byte
)
1789 || translate_anteprev_byte
== cursor
[-2])))))
1790 ch
= simple_translate
[*cursor
];
1799 while ((i
-= direction
) + direction
!= 0)
1801 cursor
-= direction
;
1802 if (pat
[i
] != *cursor
)
1806 cursor
+= dirlen
- i
- direction
; /* fix cursor */
1807 if (i
+ direction
== 0)
1811 cursor
-= direction
;
1813 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
1814 ? 1 - len_byte
: 0);
1815 set_search_regs (position
, len_byte
);
1817 if ((n
-= direction
) != 0)
1818 cursor
+= dirlen
; /* to resume search */
1820 return ((direction
> 0)
1821 ? search_regs
.end
[0] : search_regs
.start
[0]);
1824 cursor
+= stride_for_teases
; /* <sigh> we lose - */
1826 pos_byte
+= cursor
- p2
;
1829 /* Now we'll pick up a clump that has to be done the hard */
1830 /* way because it covers a discontinuity */
1832 limit
= ((direction
> 0)
1833 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
1834 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
1835 limit
= ((direction
> 0)
1836 ? min (limit
+ len_byte
, lim_byte
- 1)
1837 : max (limit
- len_byte
, lim_byte
));
1838 /* LIMIT is now the last value POS_BYTE can have
1839 and still be valid for a possible match. */
1842 /* This loop can be coded for space rather than */
1843 /* speed because it will usually run only once. */
1844 /* (the reach is at most len + 21, and typically */
1845 /* does not exceed len) */
1846 while ((limit
- pos_byte
) * direction
>= 0)
1847 pos_byte
+= BM_tab
[FETCH_BYTE (pos_byte
)];
1848 /* now run the same tests to distinguish going off the */
1849 /* end, a match or a phony match. */
1850 if ((pos_byte
- limit
) * direction
<= len_byte
)
1851 break; /* ran off the end */
1852 /* Found what might be a match.
1853 Set POS_BYTE back to last (first if reverse) pos. */
1854 pos_byte
-= infinity
;
1855 i
= dirlen
- direction
;
1856 while ((i
-= direction
) + direction
!= 0)
1860 pos_byte
-= direction
;
1861 ptr
= BYTE_POS_ADDR (pos_byte
);
1862 /* Translate only the last byte of a character. */
1864 || ((ptr
== tail_end_ptr
1865 || CHAR_HEAD_P (ptr
[1]))
1866 && (CHAR_HEAD_P (ptr
[0])
1867 || (translate_prev_byte
== ptr
[-1]
1868 && (CHAR_HEAD_P (translate_prev_byte
)
1869 || translate_anteprev_byte
== ptr
[-2])))))
1870 ch
= simple_translate
[*ptr
];
1876 /* Above loop has moved POS_BYTE part or all the way
1877 back to the first pos (last pos if reverse).
1878 Set it once again at the last (first if reverse) char. */
1879 pos_byte
+= dirlen
- i
- direction
;
1880 if (i
+ direction
== 0)
1883 pos_byte
-= direction
;
1885 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
1887 set_search_regs (position
, len_byte
);
1889 if ((n
-= direction
) != 0)
1890 pos_byte
+= dirlen
; /* to resume search */
1892 return ((direction
> 0)
1893 ? search_regs
.end
[0] : search_regs
.start
[0]);
1896 pos_byte
+= stride_for_teases
;
1899 /* We have done one clump. Can we continue? */
1900 if ((lim_byte
- pos_byte
) * direction
< 0)
1901 return ((0 - n
) * direction
);
1903 return BYTE_TO_CHAR (pos_byte
);
1906 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
1907 for the overall match just found in the current buffer.
1908 Also clear out the match data for registers 1 and up. */
1911 set_search_regs (beg_byte
, nbytes
)
1912 int beg_byte
, nbytes
;
1916 /* Make sure we have registers in which to store
1917 the match position. */
1918 if (search_regs
.num_regs
== 0)
1920 search_regs
.start
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1921 search_regs
.end
= (regoff_t
*) xmalloc (2 * sizeof (regoff_t
));
1922 search_regs
.num_regs
= 2;
1925 /* Clear out the other registers. */
1926 for (i
= 1; i
< search_regs
.num_regs
; i
++)
1928 search_regs
.start
[i
] = -1;
1929 search_regs
.end
[i
] = -1;
1932 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
1933 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
1934 XSETBUFFER (last_thing_searched
, current_buffer
);
1937 /* Given a string of words separated by word delimiters,
1938 compute a regexp that matches those exact words
1939 separated by arbitrary punctuation. */
1945 register unsigned char *p
, *o
;
1946 register int i
, i_byte
, len
, punct_count
= 0, word_count
= 0;
1951 CHECK_STRING (string
, 0);
1952 p
= XSTRING (string
)->data
;
1953 len
= XSTRING (string
)->size
;
1955 for (i
= 0, i_byte
= 0; i
< len
; )
1959 FETCH_STRING_CHAR_ADVANCE (c
, string
, i
, i_byte
);
1961 if (SYNTAX (c
) != Sword
)
1964 if (i
> 0 && SYNTAX (prev_c
) == Sword
)
1971 if (SYNTAX (prev_c
) == Sword
)
1974 return empty_string
;
1976 adjust
= - punct_count
+ 5 * (word_count
- 1) + 4;
1977 if (STRING_MULTIBYTE (string
))
1978 val
= make_uninit_multibyte_string (len
+ adjust
,
1979 STRING_BYTES (XSTRING (string
))
1982 val
= make_uninit_string (len
+ adjust
);
1984 o
= XSTRING (val
)->data
;
1989 for (i
= 0, i_byte
= 0; i
< len
; )
1992 int i_byte_orig
= i_byte
;
1994 FETCH_STRING_CHAR_ADVANCE (c
, string
, i
, i_byte
);
1996 if (SYNTAX (c
) == Sword
)
1998 bcopy (&XSTRING (string
)->data
[i_byte_orig
], o
,
1999 i_byte
- i_byte_orig
);
2000 o
+= i_byte
- i_byte_orig
;
2002 else if (i
> 0 && SYNTAX (prev_c
) == Sword
&& --word_count
)
2020 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2021 "MSearch backward: ",
2022 "Search backward from point for STRING.\n\
2023 Set point to the beginning of the occurrence found, and return point.\n\
2024 An optional second argument bounds the search; it is a buffer position.\n\
2025 The match found must not extend before that position.\n\
2026 Optional third argument, if t, means if fail just return nil (no error).\n\
2027 If not nil and not t, position at limit of search and return nil.\n\
2028 Optional fourth argument is repeat count--search for successive occurrences.\n\
2030 Search case-sensitivity is determined by the value of the variable\n\
2031 `case-fold-search', which see.\n\
2033 See also the functions `match-beginning', `match-end' and `replace-match'.")
2034 (string
, bound
, noerror
, count
)
2035 Lisp_Object string
, bound
, noerror
, count
;
2037 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2040 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2041 "Search forward from point for STRING.\n\
2042 Set point to the end of the occurrence found, and return point.\n\
2043 An optional second argument bounds the search; it is a buffer position.\n\
2044 The match found must not extend after that position. nil is equivalent\n\
2046 Optional third argument, if t, means if fail just return nil (no error).\n\
2047 If not nil and not t, move to limit of search and return nil.\n\
2048 Optional fourth argument is repeat count--search for successive occurrences.\n\
2050 Search case-sensitivity is determined by the value of the variable\n\
2051 `case-fold-search', which see.\n\
2053 See also the functions `match-beginning', `match-end' and `replace-match'.")
2054 (string
, bound
, noerror
, count
)
2055 Lisp_Object string
, bound
, noerror
, count
;
2057 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2060 DEFUN ("word-search-backward", Fword_search_backward
, Sword_search_backward
, 1, 4,
2061 "sWord search backward: ",
2062 "Search backward from point for STRING, ignoring differences in punctuation.\n\
2063 Set point to the beginning of the occurrence found, and return point.\n\
2064 An optional second argument bounds the search; it is a buffer position.\n\
2065 The match found must not extend before that position.\n\
2066 Optional third argument, if t, means if fail just return nil (no error).\n\
2067 If not nil and not t, move to limit of search and return nil.\n\
2068 Optional fourth argument is repeat count--search for successive occurrences.")
2069 (string
, bound
, noerror
, count
)
2070 Lisp_Object string
, bound
, noerror
, count
;
2072 return search_command (wordify (string
), bound
, noerror
, count
, -1, 1, 0);
2075 DEFUN ("word-search-forward", Fword_search_forward
, Sword_search_forward
, 1, 4,
2077 "Search forward from point for STRING, ignoring differences in punctuation.\n\
2078 Set point to the end of the occurrence found, and return point.\n\
2079 An optional second argument bounds the search; it is a buffer position.\n\
2080 The match found must not extend after that position.\n\
2081 Optional third argument, if t, means if fail just return nil (no error).\n\
2082 If not nil and not t, move to limit of search and return nil.\n\
2083 Optional fourth argument is repeat count--search for successive occurrences.")
2084 (string
, bound
, noerror
, count
)
2085 Lisp_Object string
, bound
, noerror
, count
;
2087 return search_command (wordify (string
), bound
, noerror
, count
, 1, 1, 0);
2090 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2091 "sRE search backward: ",
2092 "Search backward from point for match for regular expression REGEXP.\n\
2093 Set point to the beginning of the match, and return point.\n\
2094 The match found is the one starting last in the buffer\n\
2095 and yet ending before the origin of the search.\n\
2096 An optional second argument bounds the search; it is a buffer position.\n\
2097 The match found must start at or after that position.\n\
2098 Optional third argument, if t, means if fail just return nil (no error).\n\
2099 If not nil and not t, move to limit of search and return nil.\n\
2100 Optional fourth argument is repeat count--search for successive occurrences.\n\
2101 See also the functions `match-beginning', `match-end', `match-string',\n\
2102 and `replace-match'.")
2103 (regexp
, bound
, noerror
, count
)
2104 Lisp_Object regexp
, bound
, noerror
, count
;
2106 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2109 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2111 "Search forward from point for regular expression REGEXP.\n\
2112 Set point to the end of the occurrence found, and return point.\n\
2113 An optional second argument bounds the search; it is a buffer position.\n\
2114 The match found must not extend after that position.\n\
2115 Optional third argument, if t, means if fail just return nil (no error).\n\
2116 If not nil and not t, move to limit of search and return nil.\n\
2117 Optional fourth argument is repeat count--search for successive occurrences.\n\
2118 See also the functions `match-beginning', `match-end', `match-string',\n\
2119 and `replace-match'.")
2120 (regexp
, bound
, noerror
, count
)
2121 Lisp_Object regexp
, bound
, noerror
, count
;
2123 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2126 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2127 "sPosix search backward: ",
2128 "Search backward from point for match for regular expression REGEXP.\n\
2129 Find the longest match in accord with Posix regular expression rules.\n\
2130 Set point to the beginning of the match, and return point.\n\
2131 The match found is the one starting last in the buffer\n\
2132 and yet ending before the origin of the search.\n\
2133 An optional second argument bounds the search; it is a buffer position.\n\
2134 The match found must start at or after that position.\n\
2135 Optional third argument, if t, means if fail just return nil (no error).\n\
2136 If not nil and not t, move to limit of search and return nil.\n\
2137 Optional fourth argument is repeat count--search for successive occurrences.\n\
2138 See also the functions `match-beginning', `match-end', `match-string',\n\
2139 and `replace-match'.")
2140 (regexp
, bound
, noerror
, count
)
2141 Lisp_Object regexp
, bound
, noerror
, count
;
2143 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2146 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2148 "Search forward from point for regular expression REGEXP.\n\
2149 Find the longest match in accord with Posix regular expression rules.\n\
2150 Set point to the end of the occurrence found, and return point.\n\
2151 An optional second argument bounds the search; it is a buffer position.\n\
2152 The match found must not extend after that position.\n\
2153 Optional third argument, if t, means if fail just return nil (no error).\n\
2154 If not nil and not t, move to limit of search and return nil.\n\
2155 Optional fourth argument is repeat count--search for successive occurrences.\n\
2156 See also the functions `match-beginning', `match-end', `match-string',\n\
2157 and `replace-match'.")
2158 (regexp
, bound
, noerror
, count
)
2159 Lisp_Object regexp
, bound
, noerror
, count
;
2161 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2164 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2165 "Replace text matched by last search with NEWTEXT.\n\
2166 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.\n\
2167 Otherwise maybe capitalize the whole text, or maybe just word initials,\n\
2168 based on the replaced text.\n\
2169 If the replaced text has only capital letters\n\
2170 and has at least one multiletter word, convert NEWTEXT to all caps.\n\
2171 If the replaced text has at least one word starting with a capital letter,\n\
2172 then capitalize each word in NEWTEXT.\n\n\
2173 If third arg LITERAL is non-nil, insert NEWTEXT literally.\n\
2174 Otherwise treat `\\' as special:\n\
2175 `\\&' in NEWTEXT means substitute original matched text.\n\
2176 `\\N' means substitute what matched the Nth `\\(...\\)'.\n\
2177 If Nth parens didn't match, substitute nothing.\n\
2178 `\\\\' means insert one `\\'.\n\
2179 FIXEDCASE and LITERAL are optional arguments.\n\
2180 Leaves point at end of replacement text.\n\
2182 The optional fourth argument STRING can be a string to modify.\n\
2183 This is meaningful when the previous match was done against STRING,\n\
2184 using `string-match'. When used this way, `replace-match'\n\
2185 creates and returns a new string made by copying STRING and replacing\n\
2186 the part of STRING that was matched.\n\
2188 The optional fifth argument SUBEXP specifies a subexpression;\n\
2189 it says to replace just that subexpression with NEWTEXT,\n\
2190 rather than replacing the entire matched text.\n\
2191 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;\n\
2192 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts\n\
2193 NEWTEXT in place of subexp N.\n\
2194 This is useful only after a regular expression search or match,\n\
2195 since only regular expressions have distinguished subexpressions.")
2196 (newtext
, fixedcase
, literal
, string
, subexp
)
2197 Lisp_Object newtext
, fixedcase
, literal
, string
, subexp
;
2199 enum { nochange
, all_caps
, cap_initial
} case_action
;
2200 register int pos
, pos_byte
;
2201 int some_multiletter_word
;
2204 int some_nonuppercase_initial
;
2205 register int c
, prevc
;
2208 int opoint
, newpoint
;
2210 CHECK_STRING (newtext
, 0);
2212 if (! NILP (string
))
2213 CHECK_STRING (string
, 4);
2215 case_action
= nochange
; /* We tried an initialization */
2216 /* but some C compilers blew it */
2218 if (search_regs
.num_regs
<= 0)
2219 error ("replace-match called before any match found");
2225 CHECK_NUMBER (subexp
, 3);
2226 sub
= XINT (subexp
);
2227 if (sub
< 0 || sub
>= search_regs
.num_regs
)
2228 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2233 if (search_regs
.start
[sub
] < BEGV
2234 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2235 || search_regs
.end
[sub
] > ZV
)
2236 args_out_of_range (make_number (search_regs
.start
[sub
]),
2237 make_number (search_regs
.end
[sub
]));
2241 if (search_regs
.start
[sub
] < 0
2242 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2243 || search_regs
.end
[sub
] > XSTRING (string
)->size
)
2244 args_out_of_range (make_number (search_regs
.start
[sub
]),
2245 make_number (search_regs
.end
[sub
]));
2248 if (NILP (fixedcase
))
2250 /* Decide how to casify by examining the matched text. */
2253 pos
= search_regs
.start
[sub
];
2254 last
= search_regs
.end
[sub
];
2257 pos_byte
= CHAR_TO_BYTE (pos
);
2259 pos_byte
= string_char_to_byte (string
, pos
);
2262 case_action
= all_caps
;
2264 /* some_multiletter_word is set nonzero if any original word
2265 is more than one letter long. */
2266 some_multiletter_word
= 0;
2268 some_nonuppercase_initial
= 0;
2275 c
= FETCH_CHAR (pos_byte
);
2276 INC_BOTH (pos
, pos_byte
);
2279 FETCH_STRING_CHAR_ADVANCE (c
, string
, pos
, pos_byte
);
2283 /* Cannot be all caps if any original char is lower case */
2286 if (SYNTAX (prevc
) != Sword
)
2287 some_nonuppercase_initial
= 1;
2289 some_multiletter_word
= 1;
2291 else if (!NOCASEP (c
))
2294 if (SYNTAX (prevc
) != Sword
)
2297 some_multiletter_word
= 1;
2301 /* If the initial is a caseless word constituent,
2302 treat that like a lowercase initial. */
2303 if (SYNTAX (prevc
) != Sword
)
2304 some_nonuppercase_initial
= 1;
2310 /* Convert to all caps if the old text is all caps
2311 and has at least one multiletter word. */
2312 if (! some_lowercase
&& some_multiletter_word
)
2313 case_action
= all_caps
;
2314 /* Capitalize each word, if the old text has all capitalized words. */
2315 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2316 case_action
= cap_initial
;
2317 else if (!some_nonuppercase_initial
&& some_uppercase
)
2318 /* Should x -> yz, operating on X, give Yz or YZ?
2319 We'll assume the latter. */
2320 case_action
= all_caps
;
2322 case_action
= nochange
;
2325 /* Do replacement in a string. */
2328 Lisp_Object before
, after
;
2330 before
= Fsubstring (string
, make_number (0),
2331 make_number (search_regs
.start
[sub
]));
2332 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2334 /* Substitute parts of the match into NEWTEXT
2339 int lastpos_byte
= 0;
2340 /* We build up the substituted string in ACCUM. */
2343 int length
= STRING_BYTES (XSTRING (newtext
));
2347 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2351 int delbackslash
= 0;
2353 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2357 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2361 substart
= search_regs
.start
[sub
];
2362 subend
= search_regs
.end
[sub
];
2364 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2366 if (search_regs
.start
[c
- '0'] >= 0)
2368 substart
= search_regs
.start
[c
- '0'];
2369 subend
= search_regs
.end
[c
- '0'];
2375 error ("Invalid use of `\\' in replacement text");
2379 if (pos
- 2 != lastpos
)
2380 middle
= substring_both (newtext
, lastpos
,
2382 pos
- 2, pos_byte
- 2);
2385 accum
= concat3 (accum
, middle
,
2387 make_number (substart
),
2388 make_number (subend
)));
2390 lastpos_byte
= pos_byte
;
2392 else if (delbackslash
)
2394 middle
= substring_both (newtext
, lastpos
,
2396 pos
- 1, pos_byte
- 1);
2398 accum
= concat2 (accum
, middle
);
2400 lastpos_byte
= pos_byte
;
2405 middle
= substring_both (newtext
, lastpos
,
2411 newtext
= concat2 (accum
, middle
);
2414 /* Do case substitution in NEWTEXT if desired. */
2415 if (case_action
== all_caps
)
2416 newtext
= Fupcase (newtext
);
2417 else if (case_action
== cap_initial
)
2418 newtext
= Fupcase_initials (newtext
);
2420 return concat3 (before
, newtext
, after
);
2423 /* Record point, then move (quietly) to the start of the match. */
2424 if (PT
>= search_regs
.end
[sub
])
2426 else if (PT
> search_regs
.start
[sub
])
2427 opoint
= search_regs
.end
[sub
] - ZV
;
2431 TEMP_SET_PT (search_regs
.start
[sub
]);
2433 /* We insert the replacement text before the old text, and then
2434 delete the original text. This means that markers at the
2435 beginning or end of the original will float to the corresponding
2436 position in the replacement. */
2437 if (!NILP (literal
))
2438 Finsert_and_inherit (1, &newtext
);
2441 int length
= STRING_BYTES (XSTRING (newtext
));
2442 unsigned char *substed
;
2443 int substed_alloc_size
, substed_len
;
2444 int buf_multibyte
= !NILP (current_buffer
->enable_multibyte_characters
);
2445 int str_multibyte
= STRING_MULTIBYTE (newtext
);
2446 Lisp_Object rev_tbl
;
2448 rev_tbl
= (!buf_multibyte
&& CHAR_TABLE_P (Vnonascii_translation_table
)
2449 ? Fchar_table_extra_slot (Vnonascii_translation_table
,
2453 substed_alloc_size
= length
* 2 + 100;
2454 substed
= (unsigned char *) xmalloc (substed_alloc_size
+ 1);
2457 /* Go thru NEWTEXT, producing the actual text to insert in
2458 SUBSTED while adjusting multibyteness to that of the current
2461 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2463 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2464 unsigned char *add_stuff
= NULL
;
2470 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2472 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2476 /* Note that we don't have to increment POS. */
2477 c
= XSTRING (newtext
)->data
[pos_byte
++];
2479 c
= unibyte_char_to_multibyte (c
);
2482 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2483 or set IDX to a match index, which means put that part
2484 of the buffer text into SUBSTED. */
2490 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2492 if (!buf_multibyte
&& !SINGLE_BYTE_CHAR_P (c
))
2493 c
= multibyte_char_to_unibyte (c
, rev_tbl
);
2497 c
= XSTRING (newtext
)->data
[pos_byte
++];
2499 c
= unibyte_char_to_multibyte (c
);
2504 else if (c
>= '1' && c
<= '9' && c
<= search_regs
.num_regs
+ '0')
2506 if (search_regs
.start
[c
- '0'] >= 1)
2510 add_len
= 1, add_stuff
= "\\";
2514 error ("Invalid use of `\\' in replacement text");
2519 add_len
= CHAR_STRING (c
, str
);
2523 /* If we want to copy part of a previous match,
2524 set up ADD_STUFF and ADD_LEN to point to it. */
2527 int begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2528 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2529 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2530 move_gap (search_regs
.start
[idx
]);
2531 add_stuff
= BYTE_POS_ADDR (begbyte
);
2534 /* Now the stuff we want to add to SUBSTED
2535 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2537 /* Make sure SUBSTED is big enough. */
2538 if (substed_len
+ add_len
>= substed_alloc_size
)
2540 substed_alloc_size
= substed_len
+ add_len
+ 500;
2541 substed
= (unsigned char *) xrealloc (substed
,
2542 substed_alloc_size
+ 1);
2545 /* Now add to the end of SUBSTED. */
2548 bcopy (add_stuff
, substed
+ substed_len
, add_len
);
2549 substed_len
+= add_len
;
2553 /* Now insert what we accumulated. */
2554 insert_and_inherit (substed
, substed_len
);
2559 inslen
= PT
- (search_regs
.start
[sub
]);
2560 del_range (search_regs
.start
[sub
] + inslen
, search_regs
.end
[sub
] + inslen
);
2562 if (case_action
== all_caps
)
2563 Fupcase_region (make_number (PT
- inslen
), make_number (PT
));
2564 else if (case_action
== cap_initial
)
2565 Fupcase_initials_region (make_number (PT
- inslen
), make_number (PT
));
2569 /* Put point back where it was in the text. */
2571 TEMP_SET_PT (opoint
+ ZV
);
2573 TEMP_SET_PT (opoint
);
2575 /* Now move point "officially" to the start of the inserted replacement. */
2576 move_if_not_intangible (newpoint
);
2582 match_limit (num
, beginningp
)
2588 CHECK_NUMBER (num
, 0);
2590 if (n
< 0 || n
>= search_regs
.num_regs
)
2591 args_out_of_range (num
, make_number (search_regs
.num_regs
));
2592 if (search_regs
.num_regs
<= 0
2593 || search_regs
.start
[n
] < 0)
2595 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2596 : search_regs
.end
[n
]));
2599 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2600 "Return position of start of text matched by last search.\n\
2601 SUBEXP, a number, specifies which parenthesized expression in the last\n\
2603 Value is nil if SUBEXPth pair didn't match, or there were less than\n\
2605 Zero means the entire text matched by the whole regexp or whole string.")
2609 return match_limit (subexp
, 1);
2612 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2613 "Return position of end of text matched by last search.\n\
2614 SUBEXP, a number, specifies which parenthesized expression in the last\n\
2616 Value is nil if SUBEXPth pair didn't match, or there were less than\n\
2618 Zero means the entire text matched by the whole regexp or whole string.")
2622 return match_limit (subexp
, 0);
2625 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 2, 0,
2626 "Return a list containing all info on what the last search matched.\n\
2627 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.\n\
2628 All the elements are markers or nil (nil if the Nth pair didn't match)\n\
2629 if the last match was on a buffer; integers or nil if a string was matched.\n\
2630 Use `store-match-data' to reinstate the data in this list.\n\
2632 If INTEGERS (the optional first argument) is non-nil, always use integers\n\
2633 \(rather than markers) to represent buffer positions.\n\
2634 If REUSE is a list, reuse it as part of the value. If REUSE is long enough\n\
2635 to hold all the values, and if INTEGERS is non-nil, no consing is done.")
2637 Lisp_Object integers
, reuse
;
2639 Lisp_Object tail
, prev
;
2643 if (NILP (last_thing_searched
))
2648 data
= (Lisp_Object
*) alloca ((2 * search_regs
.num_regs
)
2649 * sizeof (Lisp_Object
));
2652 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2654 int start
= search_regs
.start
[i
];
2657 if (EQ (last_thing_searched
, Qt
)
2658 || ! NILP (integers
))
2660 XSETFASTINT (data
[2 * i
], start
);
2661 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2663 else if (BUFFERP (last_thing_searched
))
2665 data
[2 * i
] = Fmake_marker ();
2666 Fset_marker (data
[2 * i
],
2667 make_number (start
),
2668 last_thing_searched
);
2669 data
[2 * i
+ 1] = Fmake_marker ();
2670 Fset_marker (data
[2 * i
+ 1],
2671 make_number (search_regs
.end
[i
]),
2672 last_thing_searched
);
2675 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2681 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2684 /* If REUSE is not usable, cons up the values and return them. */
2685 if (! CONSP (reuse
))
2686 return Flist (2 * len
+ 2, data
);
2688 /* If REUSE is a list, store as many value elements as will fit
2689 into the elements of REUSE. */
2690 for (i
= 0, tail
= reuse
; CONSP (tail
);
2691 i
++, tail
= XCDR (tail
))
2693 if (i
< 2 * len
+ 2)
2694 XCAR (tail
) = data
[i
];
2700 /* If we couldn't fit all value elements into REUSE,
2701 cons up the rest of them and add them to the end of REUSE. */
2702 if (i
< 2 * len
+ 2)
2703 XCDR (prev
) = Flist (2 * len
+ 2 - i
, data
+ i
);
2709 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 1, 0,
2710 "Set internal data on last search match from elements of LIST.\n\
2711 LIST should have been created by calling `match-data' previously.")
2713 register Lisp_Object list
;
2716 register Lisp_Object marker
;
2718 if (running_asynch_code
)
2719 save_search_regs ();
2721 if (!CONSP (list
) && !NILP (list
))
2722 list
= wrong_type_argument (Qconsp
, list
);
2724 /* Unless we find a marker with a buffer in LIST, assume that this
2725 match data came from a string. */
2726 last_thing_searched
= Qt
;
2728 /* Allocate registers if they don't already exist. */
2730 int length
= XFASTINT (Flength (list
)) / 2;
2732 if (length
> search_regs
.num_regs
)
2734 if (search_regs
.num_regs
== 0)
2737 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2739 = (regoff_t
*) xmalloc (length
* sizeof (regoff_t
));
2744 = (regoff_t
*) xrealloc (search_regs
.start
,
2745 length
* sizeof (regoff_t
));
2747 = (regoff_t
*) xrealloc (search_regs
.end
,
2748 length
* sizeof (regoff_t
));
2751 for (i
= search_regs
.num_regs
; i
< length
; i
++)
2752 search_regs
.start
[i
] = -1;
2754 search_regs
.num_regs
= length
;
2758 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2760 marker
= Fcar (list
);
2763 search_regs
.start
[i
] = -1;
2770 if (MARKERP (marker
))
2772 if (XMARKER (marker
)->buffer
== 0)
2773 XSETFASTINT (marker
, 0);
2775 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
2778 CHECK_NUMBER_COERCE_MARKER (marker
, 0);
2779 from
= XINT (marker
);
2782 marker
= Fcar (list
);
2783 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
2784 XSETFASTINT (marker
, 0);
2786 CHECK_NUMBER_COERCE_MARKER (marker
, 0);
2787 search_regs
.start
[i
] = from
;
2788 search_regs
.end
[i
] = XINT (marker
);
2796 /* If non-zero the match data have been saved in saved_search_regs
2797 during the execution of a sentinel or filter. */
2798 static int search_regs_saved
;
2799 static struct re_registers saved_search_regs
;
2801 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2802 if asynchronous code (filter or sentinel) is running. */
2806 if (!search_regs_saved
)
2808 saved_search_regs
.num_regs
= search_regs
.num_regs
;
2809 saved_search_regs
.start
= search_regs
.start
;
2810 saved_search_regs
.end
= search_regs
.end
;
2811 search_regs
.num_regs
= 0;
2812 search_regs
.start
= 0;
2813 search_regs
.end
= 0;
2815 search_regs_saved
= 1;
2819 /* Called upon exit from filters and sentinels. */
2821 restore_match_data ()
2823 if (search_regs_saved
)
2825 if (search_regs
.num_regs
> 0)
2827 xfree (search_regs
.start
);
2828 xfree (search_regs
.end
);
2830 search_regs
.num_regs
= saved_search_regs
.num_regs
;
2831 search_regs
.start
= saved_search_regs
.start
;
2832 search_regs
.end
= saved_search_regs
.end
;
2834 search_regs_saved
= 0;
2838 /* Quote a string to inactivate reg-expr chars */
2840 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
2841 "Return a regexp string which matches exactly STRING and nothing else.")
2845 register unsigned char *in
, *out
, *end
;
2846 register unsigned char *temp
;
2847 int backslashes_added
= 0;
2849 CHECK_STRING (string
, 0);
2851 temp
= (unsigned char *) alloca (STRING_BYTES (XSTRING (string
)) * 2);
2853 /* Now copy the data into the new string, inserting escapes. */
2855 in
= XSTRING (string
)->data
;
2856 end
= in
+ STRING_BYTES (XSTRING (string
));
2859 for (; in
!= end
; in
++)
2861 if (*in
== '[' || *in
== ']'
2862 || *in
== '*' || *in
== '.' || *in
== '\\'
2863 || *in
== '?' || *in
== '+'
2864 || *in
== '^' || *in
== '$')
2865 *out
++ = '\\', backslashes_added
++;
2869 return make_specified_string (temp
,
2870 XSTRING (string
)->size
+ backslashes_added
,
2872 STRING_MULTIBYTE (string
));
2880 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
2882 searchbufs
[i
].buf
.allocated
= 100;
2883 searchbufs
[i
].buf
.buffer
= (unsigned char *) malloc (100);
2884 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
2885 searchbufs
[i
].regexp
= Qnil
;
2886 staticpro (&searchbufs
[i
].regexp
);
2887 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
2889 searchbuf_head
= &searchbufs
[0];
2891 Qsearch_failed
= intern ("search-failed");
2892 staticpro (&Qsearch_failed
);
2893 Qinvalid_regexp
= intern ("invalid-regexp");
2894 staticpro (&Qinvalid_regexp
);
2896 Fput (Qsearch_failed
, Qerror_conditions
,
2897 Fcons (Qsearch_failed
, Fcons (Qerror
, Qnil
)));
2898 Fput (Qsearch_failed
, Qerror_message
,
2899 build_string ("Search failed"));
2901 Fput (Qinvalid_regexp
, Qerror_conditions
,
2902 Fcons (Qinvalid_regexp
, Fcons (Qerror
, Qnil
)));
2903 Fput (Qinvalid_regexp
, Qerror_message
,
2904 build_string ("Invalid regexp"));
2906 last_thing_searched
= Qnil
;
2907 staticpro (&last_thing_searched
);
2909 defsubr (&Slooking_at
);
2910 defsubr (&Sposix_looking_at
);
2911 defsubr (&Sstring_match
);
2912 defsubr (&Sposix_string_match
);
2913 defsubr (&Ssearch_forward
);
2914 defsubr (&Ssearch_backward
);
2915 defsubr (&Sword_search_forward
);
2916 defsubr (&Sword_search_backward
);
2917 defsubr (&Sre_search_forward
);
2918 defsubr (&Sre_search_backward
);
2919 defsubr (&Sposix_search_forward
);
2920 defsubr (&Sposix_search_backward
);
2921 defsubr (&Sreplace_match
);
2922 defsubr (&Smatch_beginning
);
2923 defsubr (&Smatch_end
);
2924 defsubr (&Smatch_data
);
2925 defsubr (&Sset_match_data
);
2926 defsubr (&Sregexp_quote
);