1 /* String search routines for XEmacs.
2 Copyright (C) 1985, 1986, 1987, 1992-1995 Free Software Foundation, Inc.
3 Copyright (C) 1995 Sun Microsystems, Inc.
5 This file is part of XEmacs.
7 XEmacs is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 XEmacs is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with XEmacs; see the file COPYING. If not, write to
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
22 /* Synched up with: FSF 19.29, except for region-cache stuff. */
24 /* Hacked on for Mule by Ben Wing, December 1994 and August 1995. */
26 /* This file has been Mule-ized except for the TRT stuff. */
34 #ifdef REGION_CACHE_NEEDS_WORK
35 #include "region-cache.h"
39 #include <sys/types.h>
44 #define TRANSLATE(table, pos) \
45 (!NILP (table) ? TRT_TABLE_OF (table, (Emchar) pos) : pos)
47 #define REGEXP_CACHE_SIZE 20
49 /* If the regexp is non-nil, then the buffer contains the compiled form
50 of that regexp, suitable for searching. */
53 struct regexp_cache *next;
55 struct re_pattern_buffer buf;
57 /* Nonzero means regexp was compiled to do full POSIX backtracking. */
61 /* The instances of that struct. */
62 static struct regexp_cache searchbufs[REGEXP_CACHE_SIZE];
64 /* The head of the linked list; points to the most recently used buffer. */
65 static struct regexp_cache *searchbuf_head;
68 /* Every call to re_match, etc., must pass &search_regs as the regs
69 argument unless you can show it is unnecessary (i.e., if re_match
70 is certainly going to be called again before region-around-match
73 Since the registers are now dynamically allocated, we need to make
74 sure not to refer to the Nth register before checking that it has
75 been allocated by checking search_regs.num_regs.
77 The regex code keeps track of whether it has allocated the search
78 buffer using bits in the re_pattern_buffer. This means that whenever
79 you compile a new pattern, it completely forgets whether it has
80 allocated any registers, and will allocate new registers the next
81 time you call a searching or matching function. Therefore, we need
82 to call re_set_registers after compiling a new pattern or after
83 setting the match registers, so that the regex functions will be
84 able to free or re-allocate it properly. */
86 /* Note: things get trickier under Mule because the values returned from
87 the regexp routines are in Bytinds but we need them to be in Bufpos's.
88 We take the easy way out for the moment and just convert them immediately.
89 We could be more clever by not converting them until necessary, but
90 that gets real ugly real fast since the buffer might have changed and
91 the positions might be out of sync or out of range.
93 static struct re_registers search_regs;
95 /* The buffer in which the last search was performed, or
96 Qt if the last search was done in a string;
97 Qnil if no searching has been done yet. */
98 static Lisp_Object last_thing_searched;
100 /* error condition signalled when regexp compile_pattern fails */
102 Lisp_Object Qinvalid_regexp;
104 /* Regular expressions used in forward/backward-word */
105 Lisp_Object Vforward_word_regexp, Vbackward_word_regexp;
107 /* range table for use with skip_chars. Only needed for Mule. */
108 Lisp_Object Vskip_chars_range_table;
110 static void set_search_regs (struct buffer *buf, Bufpos beg, Charcount len);
111 static void save_search_regs (void);
112 static Bufpos simple_search (struct buffer *buf, Bufbyte *base_pat,
113 Bytecount len, Bytind pos, Bytind lim,
114 EMACS_INT n, Lisp_Object trt);
115 static Bufpos boyer_moore (struct buffer *buf, Bufbyte *base_pat,
116 Bytecount len, Bytind pos, Bytind lim,
117 EMACS_INT n, Lisp_Object trt,
118 Lisp_Object inverse_trt, int charset_base);
119 static Bufpos search_buffer (struct buffer *buf, Lisp_Object str,
120 Bufpos bufpos, Bufpos buflim, EMACS_INT n, int RE,
121 Lisp_Object trt, Lisp_Object inverse_trt,
125 matcher_overflow (void)
127 error ("Stack overflow in regexp matcher");
130 /* Compile a regexp and signal a Lisp error if anything goes wrong.
131 PATTERN is the pattern to compile.
132 CP is the place to put the result.
133 TRANSLATE is a translation table for ignoring case, or NULL for none.
134 REGP is the structure that says where to store the "register"
135 values that will result from matching this pattern.
136 If it is 0, we should compile the pattern not to record any
137 subexpression bounds.
138 POSIX is nonzero if we want full backtracking (POSIX style)
139 for this pattern. 0 means backtrack only enough to get a valid match. */
142 compile_pattern_1 (struct regexp_cache *cp, Lisp_Object pattern,
143 Lisp_Object translate, struct re_registers *regp, int posix,
150 cp->buf.translate = translate;
152 old = re_set_syntax (RE_SYNTAX_EMACS
153 | (posix ? 0 : RE_NO_POSIX_BACKTRACKING));
155 re_compile_pattern ((char *) XSTRING_DATA (pattern),
156 XSTRING_LENGTH (pattern), &cp->buf);
160 maybe_signal_error (Qinvalid_regexp, list1 (build_string (val)),
165 cp->regexp = Fcopy_sequence (pattern);
169 /* Compile a regexp if necessary, but first check to see if there's one in
171 PATTERN is the pattern to compile.
172 TRANSLATE is a translation table for ignoring case, or NULL for none.
173 REGP is the structure that says where to store the "register"
174 values that will result from matching this pattern.
175 If it is 0, we should compile the pattern not to record any
176 subexpression bounds.
177 POSIX is nonzero if we want full backtracking (POSIX style)
178 for this pattern. 0 means backtrack only enough to get a valid match. */
180 struct re_pattern_buffer *
181 compile_pattern (Lisp_Object pattern, struct re_registers *regp,
182 Lisp_Object translate, int posix, Error_behavior errb)
184 struct regexp_cache *cp, **cpp;
186 for (cpp = &searchbuf_head; ; cpp = &cp->next)
189 if (!NILP (Fstring_equal (cp->regexp, pattern))
190 && EQ (cp->buf.translate, translate)
191 && cp->posix == posix)
194 /* If we're at the end of the cache, compile into the last cell. */
197 if (!compile_pattern_1 (cp, pattern, translate, regp, posix,
204 /* When we get here, cp (aka *cpp) contains the compiled pattern,
205 either because we found it in the cache or because we just compiled it.
206 Move it to the front of the queue to mark it as most recently used. */
208 cp->next = searchbuf_head;
211 /* Advise the searching functions about the space we have allocated
212 for register data. */
214 re_set_registers (&cp->buf, regp, regp->num_regs, regp->start, regp->end);
219 /* Error condition used for failing searches */
220 Lisp_Object Qsearch_failed;
223 signal_failure (Lisp_Object arg)
226 Fsignal (Qsearch_failed, list1 (arg));
227 return Qnil; /* Not reached. */
230 /* Convert the search registers from Bytinds to Bufpos's. Needs to be
231 done after each regexp match that uses the search regs.
233 We could get a potential speedup by not converting the search registers
234 until it's really necessary, e.g. when match-data or replace-match is
235 called. However, this complexifies the code a lot (e.g. the buffer
236 could have changed and the Bytinds stored might be invalid) and is
237 probably not a great time-saver. */
240 fixup_search_regs_for_buffer (struct buffer *buf)
243 int num_regs = search_regs.num_regs;
245 for (i = 0; i < num_regs; i++)
247 if (search_regs.start[i] >= 0)
248 search_regs.start[i] = bytind_to_bufpos (buf, search_regs.start[i]);
249 if (search_regs.end[i] >= 0)
250 search_regs.end[i] = bytind_to_bufpos (buf, search_regs.end[i]);
254 /* Similar but for strings. */
256 fixup_search_regs_for_string (Lisp_Object string)
259 int num_regs = search_regs.num_regs;
261 /* #### bytecount_to_charcount() is not that efficient. This function
262 could be faster if it did its own conversion (using INC_CHARPTR()
263 and such), because the register ends are likely to be somewhat ordered.
264 (Even if not, you could sort them.)
266 Think about this if this function is a time hog, which it's probably
268 for (i = 0; i < num_regs; i++)
270 if (search_regs.start[i] > 0)
272 search_regs.start[i] =
273 bytecount_to_charcount (XSTRING_DATA (string),
274 search_regs.start[i]);
276 if (search_regs.end[i] > 0)
279 bytecount_to_charcount (XSTRING_DATA (string),
287 looking_at_1 (Lisp_Object string, struct buffer *buf, int posix)
289 /* This function has been Mule-ized, except for the trt table handling. */
294 struct re_pattern_buffer *bufp;
296 if (running_asynch_code)
299 CHECK_STRING (string);
300 bufp = compile_pattern (string, &search_regs,
301 (!NILP (buf->case_fold_search)
302 ? XCASE_TABLE_DOWNCASE (buf->case_table) : Qnil),
307 /* Get pointers and sizes of the two strings
308 that make up the visible portion of the buffer. */
310 p1 = BI_BUF_BEGV (buf);
311 p2 = BI_BUF_CEILING_OF (buf, p1);
313 s2 = BI_BUF_ZV (buf) - p2;
315 regex_match_object = Qnil;
316 regex_emacs_buffer = buf;
317 i = re_match_2 (bufp, (char *) BI_BUF_BYTE_ADDRESS (buf, p1),
318 s1, (char *) BI_BUF_BYTE_ADDRESS (buf, p2), s2,
319 BI_BUF_PT (buf) - BI_BUF_BEGV (buf), &search_regs,
320 BI_BUF_ZV (buf) - BI_BUF_BEGV (buf));
325 val = (0 <= i ? Qt : Qnil);
329 int num_regs = search_regs.num_regs;
330 for (i = 0; i < num_regs; i++)
331 if (search_regs.start[i] >= 0)
333 search_regs.start[i] += BI_BUF_BEGV (buf);
334 search_regs.end[i] += BI_BUF_BEGV (buf);
337 XSETBUFFER (last_thing_searched, buf);
338 fixup_search_regs_for_buffer (buf);
342 DEFUN ("looking-at", Flooking_at, 1, 2, 0, /*
343 Return t if text after point matches regular expression REGEXP.
344 This function modifies the match data that `match-beginning',
345 `match-end' and `match-data' access; save and restore the match
346 data if you want to preserve them.
348 Optional argument BUFFER defaults to the current buffer.
352 return looking_at_1 (regexp, decode_buffer (buffer, 0), 0);
355 DEFUN ("posix-looking-at", Fposix_looking_at, 1, 2, 0, /*
356 Return t if text after point matches regular expression REGEXP.
357 Find the longest match, in accord with Posix regular expression rules.
358 This function modifies the match data that `match-beginning',
359 `match-end' and `match-data' access; save and restore the match
360 data if you want to preserve them.
362 Optional argument BUFFER defaults to the current buffer.
366 return looking_at_1 (regexp, decode_buffer (buffer, 0), 1);
370 string_match_1 (Lisp_Object regexp, Lisp_Object string, Lisp_Object start,
371 struct buffer *buf, int posix)
373 /* This function has been Mule-ized, except for the trt table handling. */
376 struct re_pattern_buffer *bufp;
378 if (running_asynch_code)
381 CHECK_STRING (regexp);
382 CHECK_STRING (string);
388 Charcount len = XSTRING_CHAR_LENGTH (string);
392 if (s < 0 && -s <= len)
394 else if (0 > s || s > len)
395 args_out_of_range (string, start);
399 bufp = compile_pattern (regexp, &search_regs,
400 (!NILP (buf->case_fold_search)
401 ? XCASE_TABLE_DOWNCASE (buf->case_table) : Qnil),
405 Bytecount bis = charcount_to_bytecount (XSTRING_DATA (string), s);
406 regex_match_object = string;
407 regex_emacs_buffer = buf;
408 val = re_search (bufp, (char *) XSTRING_DATA (string),
409 XSTRING_LENGTH (string), bis,
410 XSTRING_LENGTH (string) - bis,
415 if (val < 0) return Qnil;
416 last_thing_searched = Qt;
417 fixup_search_regs_for_string (string);
418 return make_int (bytecount_to_charcount (XSTRING_DATA (string), val));
421 DEFUN ("string-match", Fstring_match, 2, 4, 0, /*
422 Return index of start of first match for REGEXP in STRING, or nil.
423 If third arg START is non-nil, start search at that index in STRING.
424 For index of first char beyond the match, do (match-end 0).
425 `match-end' and `match-beginning' also give indices of substrings
426 matched by parenthesis constructs in the pattern.
428 Optional arg BUFFER controls how case folding is done (according to
429 the value of `case-fold-search' in that buffer and that buffer's case
430 tables) and defaults to the current buffer.
432 (regexp, string, start, buffer))
434 return string_match_1 (regexp, string, start, decode_buffer (buffer, 0), 0);
437 DEFUN ("posix-string-match", Fposix_string_match, 2, 4, 0, /*
438 Return index of start of first match for REGEXP in STRING, or nil.
439 Find the longest match, in accord with Posix regular expression rules.
440 If third arg START is non-nil, start search at that index in STRING.
441 For index of first char beyond the match, do (match-end 0).
442 `match-end' and `match-beginning' also give indices of substrings
443 matched by parenthesis constructs in the pattern.
445 Optional arg BUFFER controls how case folding is done (according to
446 the value of `case-fold-search' in that buffer and that buffer's case
447 tables) and defaults to the current buffer.
449 (regexp, string, start, buffer))
451 return string_match_1 (regexp, string, start, decode_buffer (buffer, 0), 1);
454 /* Match REGEXP against STRING, searching all of STRING,
455 and return the index of the match, or negative on failure.
456 This does not clobber the match data. */
459 fast_string_match (Lisp_Object regexp, const Bufbyte *nonreloc,
460 Lisp_Object reloc, Bytecount offset,
461 Bytecount length, int case_fold_search,
462 Error_behavior errb, int no_quit)
464 /* This function has been Mule-ized, except for the trt table handling. */
466 Bufbyte *newnonreloc = (Bufbyte *) nonreloc;
467 struct re_pattern_buffer *bufp;
469 bufp = compile_pattern (regexp, 0,
471 ? XCASE_TABLE_DOWNCASE (current_buffer->case_table)
475 return -1; /* will only do this when errb != ERROR_ME */
479 no_quit_in_re_search = 1;
481 fixup_internal_substring (nonreloc, reloc, offset, &length);
486 newnonreloc = XSTRING_DATA (reloc);
489 /* QUIT could relocate RELOC. Therefore we must alloca()
490 and copy. No way around this except some serious
491 rewriting of re_search(). */
492 newnonreloc = (Bufbyte *) alloca (length);
493 memcpy (newnonreloc, XSTRING_DATA (reloc), length);
497 /* #### evil current-buffer dependency */
498 regex_match_object = reloc;
499 regex_emacs_buffer = current_buffer;
500 val = re_search (bufp, (char *) newnonreloc + offset, length, 0,
503 no_quit_in_re_search = 0;
508 fast_lisp_string_match (Lisp_Object regex, Lisp_Object string)
510 return fast_string_match (regex, 0, string, 0, -1, 0, ERROR_ME, 0);
514 #ifdef REGION_CACHE_NEEDS_WORK
515 /* The newline cache: remembering which sections of text have no newlines. */
517 /* If the user has requested newline caching, make sure it's on.
518 Otherwise, make sure it's off.
519 This is our cheezy way of associating an action with the change of
520 state of a buffer-local variable. */
522 newline_cache_on_off (struct buffer *buf)
524 if (NILP (buf->cache_long_line_scans))
526 /* It should be off. */
527 if (buf->newline_cache)
529 free_region_cache (buf->newline_cache);
530 buf->newline_cache = 0;
535 /* It should be on. */
536 if (buf->newline_cache == 0)
537 buf->newline_cache = new_region_cache ();
542 /* Search in BUF for COUNT instances of the character TARGET between
545 If COUNT is positive, search forwards; END must be >= START.
546 If COUNT is negative, search backwards for the -COUNTth instance;
547 END must be <= START.
548 If COUNT is zero, do anything you please; run rogue, for all I care.
550 If END is zero, use BEGV or ZV instead, as appropriate for the
551 direction indicated by COUNT.
553 If we find COUNT instances, set *SHORTAGE to zero, and return the
554 position after the COUNTth match. Note that for reverse motion
555 this is not the same as the usual convention for Emacs motion commands.
557 If we don't find COUNT instances before reaching END, set *SHORTAGE
558 to the number of TARGETs left unfound, and return END.
560 If ALLOW_QUIT is non-zero, call QUIT periodically. */
563 bi_scan_buffer (struct buffer *buf, Emchar target, Bytind st, Bytind en,
564 EMACS_INT count, EMACS_INT *shortage, int allow_quit)
566 /* This function has been Mule-ized. */
567 Bytind lim = en > 0 ? en :
568 ((count > 0) ? BI_BUF_ZV (buf) : BI_BUF_BEGV (buf));
570 /* #### newline cache stuff in this function not yet ported */
580 /* Due to the Mule representation of characters in a buffer,
581 we can simply search for characters in the range 0 - 127
582 directly. For other characters, we do it the "hard" way.
583 Note that this way works for all characters but the other
587 while (st < lim && count > 0)
589 if (BI_BUF_FETCH_CHAR (buf, st) == target)
591 INC_BYTIND (buf, st);
597 while (st < lim && count > 0)
602 ceil = BI_BUF_CEILING_OF (buf, st);
603 ceil = min (lim, ceil);
604 bufptr = (Bufbyte *) memchr (BI_BUF_BYTE_ADDRESS (buf, st),
605 (int) target, ceil - st);
609 st = BI_BUF_PTR_BYTE_POS (buf, bufptr) + 1;
627 while (st > lim && count < 0)
629 DEC_BYTIND (buf, st);
630 if (BI_BUF_FETCH_CHAR (buf, st) == target)
637 while (st > lim && count < 0)
643 floor = BI_BUF_FLOOR_OF (buf, st);
644 floor = max (lim, floor);
645 /* No memrchr() ... */
646 bufptr = BI_BUF_BYTE_ADDRESS_BEFORE (buf, st);
647 floorptr = BI_BUF_BYTE_ADDRESS (buf, floor);
648 while (bufptr >= floorptr)
651 /* At this point, both ST and BUFPTR refer to the same
652 character. When the loop terminates, ST will
653 always point to the last character we tried. */
654 if (* (unsigned char *) bufptr == (unsigned char) target)
672 /* We found the character we were looking for; we have to return
673 the position *after* it due to the strange way that the return
675 INC_BYTIND (buf, st);
682 scan_buffer (struct buffer *buf, Emchar target, Bufpos start, Bufpos end,
683 EMACS_INT count, EMACS_INT *shortage, int allow_quit)
686 Bytind bi_start, bi_end;
688 bi_start = bufpos_to_bytind (buf, start);
690 bi_end = bufpos_to_bytind (buf, end);
693 bi_retval = bi_scan_buffer (buf, target, bi_start, bi_end, count,
694 shortage, allow_quit);
695 return bytind_to_bufpos (buf, bi_retval);
699 bi_find_next_newline_no_quit (struct buffer *buf, Bytind from, int count)
701 return bi_scan_buffer (buf, '\n', from, 0, count, 0, 0);
705 find_next_newline_no_quit (struct buffer *buf, Bufpos from, int count)
707 return scan_buffer (buf, '\n', from, 0, count, 0, 0);
711 find_next_newline (struct buffer *buf, Bufpos from, int count)
713 return scan_buffer (buf, '\n', from, 0, count, 0, 1);
717 bi_find_next_emchar_in_string (Lisp_String* str, Emchar target, Bytind st,
720 /* This function has been Mule-ized. */
721 Bytind lim = string_length (str) -1;
722 Bufbyte* s = string_data (str);
727 /* Due to the Mule representation of characters in a buffer,
728 we can simply search for characters in the range 0 - 127
729 directly. For other characters, we do it the "hard" way.
730 Note that this way works for all characters but the other
734 while (st < lim && count > 0)
736 if (string_char (str, st) == target)
738 INC_CHARBYTIND (s, st);
744 while (st < lim && count > 0)
746 Bufbyte *bufptr = (Bufbyte *) memchr (charptr_n_addr (s, st),
747 (int) target, lim - st);
751 st = (Bytind)(bufptr - s) + 1;
760 /* Like find_next_newline, but returns position before the newline,
761 not after, and only search up to TO. This isn't just
762 find_next_newline (...)-1, because you might hit TO. */
764 find_before_next_newline (struct buffer *buf, Bufpos from, Bufpos to, int count)
767 Bufpos pos = scan_buffer (buf, '\n', from, to, count, &shortage, 1);
776 skip_chars (struct buffer *buf, int forwardp, int syntaxp,
777 Lisp_Object string, Lisp_Object lim)
779 /* This function has been Mule-ized. */
780 REGISTER Bufbyte *p, *pend;
782 /* We store the first 256 chars in an array here and the rest in
784 unsigned char fastmap[0400];
788 Lisp_Char_Table *syntax_table = XCHAR_TABLE (buf->mirror_syntax_table);
793 limit = forwardp ? BUF_ZV (buf) : BUF_BEGV (buf);
796 CHECK_INT_COERCE_MARKER (lim);
799 /* In any case, don't allow scan outside bounds of buffer. */
800 if (limit > BUF_ZV (buf)) limit = BUF_ZV (buf);
801 if (limit < BUF_BEGV (buf)) limit = BUF_BEGV (buf);
804 CHECK_STRING (string);
805 p = XSTRING_DATA (string);
806 pend = p + XSTRING_LENGTH (string);
807 memset (fastmap, 0, sizeof (fastmap));
809 Fclear_range_table (Vskip_chars_range_table);
811 if (p != pend && *p == '^')
817 /* Find the characters specified and set their elements of fastmap.
818 If syntaxp, each character counts as itself.
819 Otherwise, handle backslashes and ranges specially */
823 c = charptr_emchar (p);
827 if (c < 0400 && syntax_spec_code[c] < (unsigned char) Smax)
830 signal_simple_error ("Invalid syntax designator",
837 if (p == pend) break;
838 c = charptr_emchar (p);
841 if (p != pend && *p == '-')
846 if (p == pend) break;
847 cend = charptr_emchar (p);
848 while (c <= cend && c < 0400)
854 Fput_range_table (make_int (c), make_int (cend), Qt,
855 Vskip_chars_range_table);
863 Fput_range_table (make_int (c), make_int (c), Qt,
864 Vskip_chars_range_table);
869 if (syntaxp && fastmap['-'] != 0)
872 /* If ^ was the first character, complement the fastmap.
873 We don't complement the range table, however; we just use negate
874 in the comparisons below. */
877 for (i = 0; i < (int) (sizeof fastmap); i++)
881 Bufpos start_point = BUF_PT (buf);
885 SETUP_SYNTAX_CACHE_FOR_BUFFER (buf, BUF_PT (buf), forwardp ? 1 : -1);
886 /* All syntax designators are normal chars so nothing strange
890 while (BUF_PT (buf) < limit
891 && fastmap[(unsigned char)
893 [(int) SYNTAX_FROM_CACHE (syntax_table,
895 (buf, BUF_PT (buf)))]])
897 BUF_SET_PT (buf, BUF_PT (buf) + 1);
898 UPDATE_SYNTAX_CACHE_FORWARD (BUF_PT (buf));
903 while (BUF_PT (buf) > limit
904 && fastmap[(unsigned char)
906 [(int) SYNTAX_FROM_CACHE (syntax_table,
908 (buf, BUF_PT (buf) - 1))]])
910 BUF_SET_PT (buf, BUF_PT (buf) - 1);
911 UPDATE_SYNTAX_CACHE_BACKWARD (BUF_PT (buf) - 1);
919 while (BUF_PT (buf) < limit)
921 Emchar ch = BUF_FETCH_CHAR (buf, BUF_PT (buf));
922 if ((ch < 0400) ? fastmap[ch] :
923 (NILP (Fget_range_table (make_int (ch),
924 Vskip_chars_range_table,
927 BUF_SET_PT (buf, BUF_PT (buf) + 1);
934 while (BUF_PT (buf) > limit)
936 Emchar ch = BUF_FETCH_CHAR (buf, BUF_PT (buf) - 1);
937 if ((ch < 0400) ? fastmap[ch] :
938 (NILP (Fget_range_table (make_int (ch),
939 Vskip_chars_range_table,
942 BUF_SET_PT (buf, BUF_PT (buf) - 1);
949 return make_int (BUF_PT (buf) - start_point);
953 DEFUN ("skip-chars-forward", Fskip_chars_forward, 1, 3, 0, /*
954 Move point forward, stopping before a char not in STRING, or at pos LIMIT.
955 STRING is like the inside of a `[...]' in a regular expression
956 except that `]' is never special and `\\' quotes `^', `-' or `\\'.
957 Thus, with arg "a-zA-Z", this skips letters stopping before first nonletter.
958 With arg "^a-zA-Z", skips nonletters stopping before first letter.
959 Returns the distance traveled, either zero or positive.
961 Optional argument BUFFER defaults to the current buffer.
963 (string, limit, buffer))
965 return skip_chars (decode_buffer (buffer, 0), 1, 0, string, limit);
968 DEFUN ("skip-chars-backward", Fskip_chars_backward, 1, 3, 0, /*
969 Move point backward, stopping after a char not in STRING, or at pos LIMIT.
970 See `skip-chars-forward' for details.
971 Returns the distance traveled, either zero or negative.
973 Optional argument BUFFER defaults to the current buffer.
975 (string, limit, buffer))
977 return skip_chars (decode_buffer (buffer, 0), 0, 0, string, limit);
981 DEFUN ("skip-syntax-forward", Fskip_syntax_forward, 1, 3, 0, /*
982 Move point forward across chars in specified syntax classes.
983 SYNTAX is a string of syntax code characters.
984 Stop before a char whose syntax is not in SYNTAX, or at position LIMIT.
985 If SYNTAX starts with ^, skip characters whose syntax is NOT in SYNTAX.
986 This function returns the distance traveled, either zero or positive.
988 Optional argument BUFFER defaults to the current buffer.
990 (syntax, limit, buffer))
992 return skip_chars (decode_buffer (buffer, 0), 1, 1, syntax, limit);
995 DEFUN ("skip-syntax-backward", Fskip_syntax_backward, 1, 3, 0, /*
996 Move point backward across chars in specified syntax classes.
997 SYNTAX is a string of syntax code characters.
998 Stop on reaching a char whose syntax is not in SYNTAX, or at position LIMIT.
999 If SYNTAX starts with ^, skip characters whose syntax is NOT in SYNTAX.
1000 This function returns the distance traveled, either zero or negative.
1002 Optional argument BUFFER defaults to the current buffer.
1004 (syntax, limit, buffer))
1006 return skip_chars (decode_buffer (buffer, 0), 0, 1, syntax, limit);
1010 /* Subroutines of Lisp buffer search functions. */
1013 search_command (Lisp_Object string, Lisp_Object limit, Lisp_Object noerror,
1014 Lisp_Object count, Lisp_Object buffer, int direction,
1017 /* This function has been Mule-ized, except for the trt table handling. */
1020 EMACS_INT n = direction;
1029 buf = decode_buffer (buffer, 0);
1030 CHECK_STRING (string);
1032 lim = n > 0 ? BUF_ZV (buf) : BUF_BEGV (buf);
1035 CHECK_INT_COERCE_MARKER (limit);
1037 if (n > 0 ? lim < BUF_PT (buf) : lim > BUF_PT (buf))
1038 error ("Invalid search limit (wrong side of point)");
1039 if (lim > BUF_ZV (buf))
1041 if (lim < BUF_BEGV (buf))
1042 lim = BUF_BEGV (buf);
1045 np = search_buffer (buf, string, BUF_PT (buf), lim, n, RE,
1046 (!NILP (buf->case_fold_search)
1047 ? XCASE_TABLE_CANON (buf->case_table)
1049 (!NILP (buf->case_fold_search)
1050 ? XCASE_TABLE_EQV (buf->case_table)
1056 return signal_failure (string);
1057 if (!EQ (noerror, Qt))
1059 if (lim < BUF_BEGV (buf) || lim > BUF_ZV (buf))
1061 BUF_SET_PT (buf, lim);
1063 #if 0 /* This would be clean, but maybe programs depend on
1064 a value of nil here. */
1072 if (np < BUF_BEGV (buf) || np > BUF_ZV (buf))
1075 BUF_SET_PT (buf, np);
1077 return make_int (np);
1081 trivial_regexp_p (Lisp_Object regexp)
1083 /* This function has been Mule-ized. */
1084 Bytecount len = XSTRING_LENGTH (regexp);
1085 Bufbyte *s = XSTRING_DATA (regexp);
1090 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1097 case '|': case '(': case ')': case '`': case '\'': case 'b':
1098 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1101 /* 97/2/25 jhod Added for category matches */
1104 case '1': case '2': case '3': case '4': case '5':
1105 case '6': case '7': case '8': case '9':
1113 /* Search for the n'th occurrence of STRING in BUF,
1114 starting at position BUFPOS and stopping at position BUFLIM,
1115 treating PAT as a literal string if RE is false or as
1116 a regular expression if RE is true.
1118 If N is positive, searching is forward and BUFLIM must be greater
1120 If N is negative, searching is backward and BUFLIM must be less
1123 Returns -x if only N-x occurrences found (x > 0),
1124 or else the position at the beginning of the Nth occurrence
1125 (if searching backward) or the end (if searching forward).
1127 POSIX is nonzero if we want full backtracking (POSIX style)
1128 for this pattern. 0 means backtrack only enough to get a valid match. */
1130 search_buffer (struct buffer *buf, Lisp_Object string, Bufpos bufpos,
1131 Bufpos buflim, EMACS_INT n, int RE, Lisp_Object trt,
1132 Lisp_Object inverse_trt, int posix)
1134 /* This function has been Mule-ized, except for the trt table handling. */
1135 Bytecount len = XSTRING_LENGTH (string);
1136 Bufbyte *base_pat = XSTRING_DATA (string);
1137 REGISTER EMACS_INT i, j;
1142 if (running_asynch_code)
1143 save_search_regs ();
1145 /* Null string is found at starting position. */
1148 set_search_regs (buf, bufpos, 0);
1152 /* Searching 0 times means don't move. */
1156 pos = bufpos_to_bytind (buf, bufpos);
1157 lim = bufpos_to_bytind (buf, buflim);
1158 if (RE && !trivial_regexp_p (string))
1160 struct re_pattern_buffer *bufp;
1162 bufp = compile_pattern (string, &search_regs, trt, posix,
1165 /* Get pointers and sizes of the two strings
1166 that make up the visible portion of the buffer. */
1168 p1 = BI_BUF_BEGV (buf);
1169 p2 = BI_BUF_CEILING_OF (buf, p1);
1171 s2 = BI_BUF_ZV (buf) - p2;
1172 regex_match_object = Qnil;
1178 regex_emacs_buffer = buf;
1179 val = re_search_2 (bufp,
1180 (char *) BI_BUF_BYTE_ADDRESS (buf, p1), s1,
1181 (char *) BI_BUF_BYTE_ADDRESS (buf, p2), s2,
1182 pos - BI_BUF_BEGV (buf), lim - pos, &search_regs,
1183 pos - BI_BUF_BEGV (buf));
1187 matcher_overflow ();
1191 int num_regs = search_regs.num_regs;
1192 j = BI_BUF_BEGV (buf);
1193 for (i = 0; i < num_regs; i++)
1194 if (search_regs.start[i] >= 0)
1196 search_regs.start[i] += j;
1197 search_regs.end[i] += j;
1199 XSETBUFFER (last_thing_searched, buf);
1200 /* Set pos to the new position. */
1201 pos = search_regs.start[0];
1202 fixup_search_regs_for_buffer (buf);
1203 /* And bufpos too. */
1204 bufpos = search_regs.start[0];
1216 regex_emacs_buffer = buf;
1217 val = re_search_2 (bufp,
1218 (char *) BI_BUF_BYTE_ADDRESS (buf, p1), s1,
1219 (char *) BI_BUF_BYTE_ADDRESS (buf, p2), s2,
1220 pos - BI_BUF_BEGV (buf), lim - pos, &search_regs,
1221 lim - BI_BUF_BEGV (buf));
1224 matcher_overflow ();
1228 int num_regs = search_regs.num_regs;
1229 j = BI_BUF_BEGV (buf);
1230 for (i = 0; i < num_regs; i++)
1231 if (search_regs.start[i] >= 0)
1233 search_regs.start[i] += j;
1234 search_regs.end[i] += j;
1236 XSETBUFFER (last_thing_searched, buf);
1237 /* Set pos to the new position. */
1238 pos = search_regs.end[0];
1239 fixup_search_regs_for_buffer (buf);
1240 /* And bufpos too. */
1241 bufpos = search_regs.end[0];
1251 else /* non-RE case */
1253 int charset_base = -1;
1254 int boyer_moore_ok = 1;
1256 Bufbyte *patbuf = alloca_array (Bufbyte, len * MAX_EMCHAR_LEN);
1261 Bufbyte tmp_str[MAX_EMCHAR_LEN];
1262 Emchar c, translated, inverse;
1263 Bytecount orig_bytelen, new_bytelen, inv_bytelen;
1265 /* If we got here and the RE flag is set, it's because
1266 we're dealing with a regexp known to be trivial, so the
1267 backslash just quotes the next character. */
1268 if (RE && *base_pat == '\\')
1273 c = charptr_emchar (base_pat);
1274 translated = TRANSLATE (trt, c);
1275 inverse = TRANSLATE (inverse_trt, c);
1277 orig_bytelen = charcount_to_bytecount (base_pat, 1);
1278 inv_bytelen = set_charptr_emchar (tmp_str, inverse);
1279 new_bytelen = set_charptr_emchar (tmp_str, translated);
1282 if (new_bytelen != orig_bytelen || inv_bytelen != orig_bytelen)
1284 if (translated != c || inverse != c)
1286 /* Keep track of which character set row
1287 contains the characters that need translation. */
1288 int charset_base_code = c & ~CHAR_FIELD3_MASK;
1289 if (charset_base == -1)
1290 charset_base = charset_base_code;
1291 else if (charset_base != charset_base_code)
1292 /* If two different rows appear, needing translation,
1293 then we cannot use boyer_moore search. */
1296 memcpy (pat, tmp_str, new_bytelen);
1298 base_pat += orig_bytelen;
1299 len -= orig_bytelen;
1301 #else /* not MULE */
1304 /* If we got here and the RE flag is set, it's because
1305 we're dealing with a regexp known to be trivial, so the
1306 backslash just quotes the next character. */
1307 if (RE && *base_pat == '\\')
1312 *pat++ = TRANSLATE (trt, *base_pat++);
1316 pat = base_pat = patbuf;
1318 return boyer_moore (buf, base_pat, len, pos, lim, n,
1319 trt, inverse_trt, charset_base);
1321 return simple_search (buf, base_pat, len, pos, lim, n, trt);
1325 /* Do a simple string search N times for the string PAT,
1326 whose length is LEN/LEN_BYTE,
1327 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1328 TRT is the translation table.
1330 Return the character position where the match is found.
1331 Otherwise, if M matches remained to be found, return -M.
1333 This kind of search works regardless of what is in PAT and
1334 regardless of what is in TRT. It is used in cases where
1335 boyer_moore cannot work. */
1338 simple_search (struct buffer *buf, Bufbyte *base_pat, Bytecount len_byte,
1339 Bytind idx, Bytind lim, EMACS_INT n, Lisp_Object trt)
1341 int forward = n > 0;
1342 Bytecount buf_len = 0; /* Shut up compiler. */
1349 Bytecount this_len = len_byte;
1350 Bytind this_idx = idx;
1351 Bufbyte *p = base_pat;
1355 while (this_len > 0)
1357 Emchar pat_ch, buf_ch;
1360 pat_ch = charptr_emchar (p);
1361 buf_ch = BI_BUF_FETCH_CHAR (buf, this_idx);
1363 buf_ch = TRANSLATE (trt, buf_ch);
1365 if (buf_ch != pat_ch)
1368 pat_len = charcount_to_bytecount (p, 1);
1370 this_len -= pat_len;
1371 INC_BYTIND (buf, this_idx);
1375 buf_len = this_idx - idx;
1379 INC_BYTIND (buf, idx);
1388 Bytecount this_len = len_byte;
1389 Bytind this_idx = idx;
1393 p = base_pat + len_byte;
1395 while (this_len > 0)
1397 Emchar pat_ch, buf_ch;
1400 DEC_BYTIND (buf, this_idx);
1401 pat_ch = charptr_emchar (p);
1402 buf_ch = BI_BUF_FETCH_CHAR (buf, this_idx);
1404 buf_ch = TRANSLATE (trt, buf_ch);
1406 if (buf_ch != pat_ch)
1409 this_len -= charcount_to_bytecount (p, 1);
1413 buf_len = idx - this_idx;
1417 DEC_BYTIND (buf, idx);
1424 Bufpos beg, end, retval;
1427 beg = bytind_to_bufpos (buf, idx - buf_len);
1428 retval = end = bytind_to_bufpos (buf, idx);
1432 retval = beg = bytind_to_bufpos (buf, idx);
1433 end = bytind_to_bufpos (buf, idx + buf_len);
1435 set_search_regs (buf, beg, end - beg);
1445 /* Do Boyer-Moore search N times for the string PAT,
1446 whose length is LEN/LEN_BYTE,
1447 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1448 DIRECTION says which direction we search in.
1449 TRT and INVERSE_TRT are translation tables.
1451 This kind of search works if all the characters in PAT that have
1452 nontrivial translation are the same aside from the last byte. This
1453 makes it possible to translate just the last byte of a character,
1454 and do so after just a simple test of the context.
1456 If that criterion is not satisfied, do not call this function. */
1459 boyer_moore (struct buffer *buf, Bufbyte *base_pat, Bytecount len,
1460 Bytind pos, Bytind lim, EMACS_INT n, Lisp_Object trt,
1461 Lisp_Object inverse_trt, int charset_base)
1463 /* #### Someone really really really needs to comment the workings
1464 of this junk somewhat better.
1466 BTW "BM" stands for Boyer-Moore, which is one of the standard
1467 string-searching algorithms. It's the best string-searching
1468 algorithm out there, provided that:
1470 a) You're not fazed by algorithm complexity. (Rabin-Karp, which
1471 uses hashing, is much much easier to code but not as fast.)
1472 b) You can freely move backwards in the string that you're
1475 As the comment below tries to explain (but garbles in typical
1476 programmer-ese), the idea is that you don't have to do a
1477 string match at every successive position in the text. For
1478 example, let's say the pattern is "a very long string". We
1479 compare the last character in the string (`g') with the
1480 corresponding character in the text. If it mismatches, and
1481 it is, say, `z', then we can skip forward by the entire
1482 length of the pattern because `z' does not occur anywhere
1483 in the pattern. If the mismatching character does occur
1484 in the pattern, we can usually still skip forward by more
1485 than one: e.g. if it is `l', then we can skip forward
1486 by the length of the substring "ong string" -- i.e. the
1487 largest end section of the pattern that does not contain
1488 the mismatched character. So what we do is compute, for
1489 each possible character, the distance we can skip forward
1490 (the "stride") and use it in the string matching. This
1491 is what the BM_tab holds. */
1492 REGISTER EMACS_INT *BM_tab;
1493 EMACS_INT *BM_tab_base;
1494 REGISTER Bytecount dirlen;
1497 Bytecount stride_for_teases = 0;
1498 REGISTER EMACS_INT i, j;
1499 Bufbyte *pat, *pat_end;
1500 REGISTER Bufbyte *cursor, *p_limit, *ptr2;
1501 Bufbyte simple_translate[0400];
1502 REGISTER int direction = ((n > 0) ? 1 : -1);
1504 Bufbyte translate_prev_byte = 0;
1505 Bufbyte translate_anteprev_byte = 0;
1508 EMACS_INT BM_tab_space[0400];
1509 BM_tab = &BM_tab_space[0];
1511 BM_tab = alloca_array (EMACS_INT, 256);
1514 /* The general approach is that we are going to maintain that we
1515 know the first (closest to the present position, in whatever
1516 direction we're searching) character that could possibly be
1517 the last (furthest from present position) character of a
1518 valid match. We advance the state of our knowledge by
1519 looking at that character and seeing whether it indeed
1520 matches the last character of the pattern. If it does, we
1521 take a closer look. If it does not, we move our pointer (to
1522 putative last characters) as far as is logically possible.
1523 This amount of movement, which I call a stride, will be the
1524 length of the pattern if the actual character appears nowhere
1525 in the pattern, otherwise it will be the distance from the
1526 last occurrence of that character to the end of the pattern.
1527 As a coding trick, an enormous stride is coded into the table
1528 for characters that match the last character. This allows
1529 use of only a single test, a test for having gone past the
1530 end of the permissible match region, to test for both
1531 possible matches (when the stride goes past the end
1532 immediately) and failure to match (where you get nudged past
1533 the end one stride at a time).
1535 Here we make a "mickey mouse" BM table. The stride of the
1536 search is determined only by the last character of the
1537 putative match. If that character does not match, we will
1538 stride the proper distance to propose a match that
1539 superimposes it on the last instance of a character that
1540 matches it (per trt), or misses it entirely if there is
1543 dirlen = len * direction;
1544 infinity = dirlen - (lim + pos + len + len) * direction;
1545 /* Record position after the end of the pattern. */
1546 pat_end = base_pat + len;
1548 base_pat = pat_end - 1;
1549 BM_tab_base = BM_tab;
1551 j = dirlen; /* to get it in a register */
1552 /* A character that does not appear in the pattern induces a
1553 stride equal to the pattern length. */
1554 while (BM_tab_base != BM_tab)
1561 /* We use this for translation, instead of TRT itself. We
1562 fill this in to handle the characters that actually occur
1563 in the pattern. Others don't matter anyway! */
1564 xzero (simple_translate);
1565 for (i = 0; i < 0400; i++)
1566 simple_translate[i] = i;
1568 while (i != infinity)
1570 Bufbyte *ptr = base_pat + i;
1577 Emchar ch, untranslated;
1578 int this_translated = 1;
1580 /* Is *PTR the last byte of a character? */
1581 if (pat_end - ptr == 1 || BUFBYTE_FIRST_BYTE_P (ptr[1]))
1583 Bufbyte *charstart = ptr;
1584 while (!BUFBYTE_FIRST_BYTE_P (*charstart))
1586 untranslated = charptr_emchar (charstart);
1587 if (charset_base == (untranslated & ~CHAR_FIELD3_MASK))
1589 ch = TRANSLATE (trt, untranslated);
1590 if (!BUFBYTE_FIRST_BYTE_P (*ptr))
1592 translate_prev_byte = ptr[-1];
1593 if (!BUFBYTE_FIRST_BYTE_P (translate_prev_byte))
1594 translate_anteprev_byte = ptr[-2];
1599 this_translated = 0;
1606 this_translated = 0;
1609 j = ((unsigned char) ch | 0200);
1611 j = (unsigned char) ch;
1614 stride_for_teases = BM_tab[j];
1615 BM_tab[j] = dirlen - i;
1616 /* A translation table is accompanied by its inverse --
1617 see comment following downcase_table for details */
1618 if (this_translated)
1620 Emchar starting_ch = ch;
1621 EMACS_INT starting_j = j;
1624 ch = TRANSLATE (inverse_trt, ch);
1626 j = ((unsigned char) ch | 0200);
1628 j = (unsigned char) ch;
1630 /* For all the characters that map into CH,
1631 set up simple_translate to map the last byte
1633 simple_translate[j] = starting_j;
1634 if (ch == starting_ch)
1636 BM_tab[j] = dirlen - i;
1642 k = (j = TRANSLATE (trt, j));
1644 stride_for_teases = BM_tab[j];
1645 BM_tab[j] = dirlen - i;
1646 /* A translation table is accompanied by its inverse --
1647 see comment following downcase_table for details */
1649 while ((j = TRANSLATE (inverse_trt, j)) != k)
1651 simple_translate[j] = k;
1652 BM_tab[j] = dirlen - i;
1661 stride_for_teases = BM_tab[j];
1662 BM_tab[j] = dirlen - i;
1664 /* stride_for_teases tells how much to stride if we get a
1665 match on the far character but are subsequently
1666 disappointed, by recording what the stride would have been
1667 for that character if the last character had been
1670 infinity = dirlen - infinity;
1671 pos += dirlen - ((direction > 0) ? direction : 0);
1672 /* loop invariant - pos points at where last char (first char if
1673 reverse) of pattern would align in a possible match. */
1677 Bufbyte *tail_end_ptr;
1678 /* It's been reported that some (broken) compiler thinks
1679 that Boolean expressions in an arithmetic context are
1680 unsigned. Using an explicit ?1:0 prevents this. */
1681 if ((lim - pos - ((direction > 0) ? 1 : 0)) * direction < 0)
1682 return n * (0 - direction);
1683 /* First we do the part we can by pointers (maybe
1687 limit = pos - dirlen + direction;
1688 /* XEmacs change: definitions of CEILING_OF and FLOOR_OF
1689 have changed. See buffer.h. */
1690 limit = ((direction > 0)
1691 ? BI_BUF_CEILING_OF (buf, limit) - 1
1692 : BI_BUF_FLOOR_OF (buf, limit + 1));
1693 /* LIMIT is now the last (not beyond-last!) value POS can
1694 take on without hitting edge of buffer or the gap. */
1695 limit = ((direction > 0)
1696 ? min (lim - 1, min (limit, pos + 20000))
1697 : max (lim, max (limit, pos - 20000)));
1698 tail_end = BI_BUF_CEILING_OF (buf, pos);
1699 tail_end_ptr = BI_BUF_BYTE_ADDRESS (buf, tail_end);
1701 if ((limit - pos) * direction > 20)
1703 p_limit = BI_BUF_BYTE_ADDRESS (buf, limit);
1704 ptr2 = (cursor = BI_BUF_BYTE_ADDRESS (buf, pos));
1705 /* In this loop, pos + cursor - ptr2 is the surrogate
1707 while (1) /* use one cursor setting as long as i can */
1709 if (direction > 0) /* worth duplicating */
1711 /* Use signed comparison if appropriate to make
1712 cursor+infinity sure to be > p_limit.
1713 Assuming that the buffer lies in a range of
1714 addresses that are all "positive" (as ints)
1715 or all "negative", either kind of comparison
1716 will work as long as we don't step by
1717 infinity. So pick the kind that works when
1718 we do step by infinity. */
1719 if ((EMACS_INT) (p_limit + infinity) >
1720 (EMACS_INT) p_limit)
1721 while ((EMACS_INT) cursor <=
1722 (EMACS_INT) p_limit)
1723 cursor += BM_tab[*cursor];
1725 while ((EMACS_UINT) cursor <=
1726 (EMACS_UINT) p_limit)
1727 cursor += BM_tab[*cursor];
1731 if ((EMACS_INT) (p_limit + infinity) <
1732 (EMACS_INT) p_limit)
1733 while ((EMACS_INT) cursor >=
1734 (EMACS_INT) p_limit)
1735 cursor += BM_tab[*cursor];
1737 while ((EMACS_UINT) cursor >=
1738 (EMACS_UINT) p_limit)
1739 cursor += BM_tab[*cursor];
1741 /* If you are here, cursor is beyond the end of the
1742 searched region. This can happen if you match on
1743 the far character of the pattern, because the
1744 "stride" of that character is infinity, a number
1745 able to throw you well beyond the end of the
1746 search. It can also happen if you fail to match
1747 within the permitted region and would otherwise
1748 try a character beyond that region */
1749 if ((cursor - p_limit) * direction <= len)
1750 break; /* a small overrun is genuine */
1751 cursor -= infinity; /* large overrun = hit */
1752 i = dirlen - direction;
1755 while ((i -= direction) + direction != 0)
1759 cursor -= direction;
1760 /* Translate only the last byte of a character. */
1761 if ((cursor == tail_end_ptr
1762 || BUFBYTE_FIRST_BYTE_P (cursor[1]))
1763 && (BUFBYTE_FIRST_BYTE_P (cursor[0])
1764 || (translate_prev_byte == cursor[-1]
1765 && (BUFBYTE_FIRST_BYTE_P (translate_prev_byte)
1766 || translate_anteprev_byte == cursor[-2]))))
1767 ch = simple_translate[*cursor];
1773 if (pat[i] != TRANSLATE (trt, *(cursor -= direction)))
1780 while ((i -= direction) + direction != 0)
1781 if (pat[i] != *(cursor -= direction))
1784 cursor += dirlen - i - direction; /* fix cursor */
1785 if (i + direction == 0)
1787 cursor -= direction;
1790 Bytind bytstart = (pos + cursor - ptr2 +
1793 Bufpos bufstart = bytind_to_bufpos (buf, bytstart);
1794 Bufpos bufend = bytind_to_bufpos (buf, bytstart + len);
1796 set_search_regs (buf, bufstart, bufend - bufstart);
1799 if ((n -= direction) != 0)
1800 cursor += dirlen; /* to resume search */
1802 return ((direction > 0)
1803 ? search_regs.end[0] : search_regs.start[0]);
1806 cursor += stride_for_teases; /* <sigh> we lose - */
1808 pos += cursor - ptr2;
1811 /* Now we'll pick up a clump that has to be done the hard
1812 way because it covers a discontinuity */
1814 /* XEmacs change: definitions of CEILING_OF and FLOOR_OF
1815 have changed. See buffer.h. */
1816 limit = ((direction > 0)
1817 ? BI_BUF_CEILING_OF (buf, pos - dirlen + 1) - 1
1818 : BI_BUF_FLOOR_OF (buf, pos - dirlen));
1819 limit = ((direction > 0)
1820 ? min (limit + len, lim - 1)
1821 : max (limit - len, lim));
1822 /* LIMIT is now the last value POS can have
1823 and still be valid for a possible match. */
1826 /* This loop can be coded for space rather than
1827 speed because it will usually run only once.
1828 (the reach is at most len + 21, and typically
1829 does not exceed len) */
1830 while ((limit - pos) * direction >= 0)
1831 /* *not* BI_BUF_FETCH_CHAR. We are working here
1832 with bytes, not characters. */
1833 pos += BM_tab[*BI_BUF_BYTE_ADDRESS (buf, pos)];
1834 /* now run the same tests to distinguish going off
1835 the end, a match or a phony match. */
1836 if ((pos - limit) * direction <= len)
1837 break; /* ran off the end */
1838 /* Found what might be a match.
1839 Set POS back to last (first if reverse) char pos. */
1841 i = dirlen - direction;
1842 while ((i -= direction) + direction != 0)
1850 ptr = BI_BUF_BYTE_ADDRESS (buf, pos);
1851 if ((ptr == tail_end_ptr
1852 || BUFBYTE_FIRST_BYTE_P (ptr[1]))
1853 && (BUFBYTE_FIRST_BYTE_P (ptr[0])
1854 || (translate_prev_byte == ptr[-1]
1855 && (BUFBYTE_FIRST_BYTE_P (translate_prev_byte)
1856 || translate_anteprev_byte == ptr[-2]))))
1857 ch = simple_translate[*ptr];
1864 if (pat[i] != TRANSLATE (trt,
1865 *BI_BUF_BYTE_ADDRESS (buf, pos)))
1869 /* Above loop has moved POS part or all the way back
1870 to the first char pos (last char pos if reverse).
1871 Set it once again at the last (first if reverse)
1873 pos += dirlen - i- direction;
1874 if (i + direction == 0)
1879 Bytind bytstart = (pos +
1882 Bufpos bufstart = bytind_to_bufpos (buf, bytstart);
1883 Bufpos bufend = bytind_to_bufpos (buf, bytstart + len);
1885 set_search_regs (buf, bufstart, bufend - bufstart);
1888 if ((n -= direction) != 0)
1889 pos += dirlen; /* to resume search */
1891 return ((direction > 0)
1892 ? search_regs.end[0] : search_regs.start[0]);
1895 pos += stride_for_teases;
1898 /* We have done one clump. Can we continue? */
1899 if ((lim - pos) * direction < 0)
1900 return (0 - n) * direction;
1902 return bytind_to_bufpos (buf, pos);
1905 /* Record beginning BEG and end BEG + LEN
1906 for a match just found in the current buffer. */
1909 set_search_regs (struct buffer *buf, Bufpos beg, Charcount len)
1911 /* This function has been Mule-ized. */
1912 /* Make sure we have registers in which to store
1913 the match position. */
1914 if (search_regs.num_regs == 0)
1916 search_regs.start = xnew (regoff_t);
1917 search_regs.end = xnew (regoff_t);
1918 search_regs.num_regs = 1;
1921 search_regs.start[0] = beg;
1922 search_regs.end[0] = beg + len;
1923 XSETBUFFER (last_thing_searched, buf);
1927 /* Given a string of words separated by word delimiters,
1928 compute a regexp that matches those exact words
1929 separated by arbitrary punctuation. */
1932 wordify (Lisp_Object buffer, Lisp_Object string)
1935 EMACS_INT punct_count = 0, word_count = 0;
1936 struct buffer *buf = decode_buffer (buffer, 0);
1937 Lisp_Char_Table *syntax_table = XCHAR_TABLE (buf->mirror_syntax_table);
1939 CHECK_STRING (string);
1940 len = XSTRING_CHAR_LENGTH (string);
1942 for (i = 0; i < len; i++)
1943 if (!WORD_SYNTAX_P (syntax_table, string_char (XSTRING (string), i)))
1946 if (i > 0 && WORD_SYNTAX_P (syntax_table,
1947 string_char (XSTRING (string), i - 1)))
1950 if (WORD_SYNTAX_P (syntax_table, string_char (XSTRING (string), len - 1)))
1952 if (!word_count) return build_string ("");
1955 /* The following value is an upper bound on the amount of storage we
1956 need. In non-Mule, it is exact. */
1958 (Bufbyte *) alloca (XSTRING_LENGTH (string) - punct_count +
1959 5 * (word_count - 1) + 4);
1960 Bufbyte *o = storage;
1965 for (i = 0; i < len; i++)
1967 Emchar ch = string_char (XSTRING (string), i);
1969 if (WORD_SYNTAX_P (syntax_table, ch))
1970 o += set_charptr_emchar (o, ch);
1972 && WORD_SYNTAX_P (syntax_table,
1973 string_char (XSTRING (string), i - 1))
1987 return make_string (storage, o - storage);
1991 DEFUN ("search-backward", Fsearch_backward, 1, 5, "sSearch backward: ", /*
1992 Search backward from point for STRING.
1993 Set point to the beginning of the occurrence found, and return point.
1995 Optional second argument LIMIT bounds the search; it is a buffer
1996 position. The match found must not extend before that position.
1997 The value nil is equivalent to (point-min).
1999 Optional third argument NOERROR, if t, means just return nil (no
2000 error) if the search fails. If neither nil nor t, set point to LIMIT
2003 Optional fourth argument COUNT is a repeat count--search for
2004 successive occurrences.
2006 Optional fifth argument BUFFER specifies the buffer to search in and
2007 defaults to the current buffer.
2009 See also the functions `match-beginning', `match-end' and `replace-match'.
2011 (string, limit, noerror, count, buffer))
2013 return search_command (string, limit, noerror, count, buffer, -1, 0, 0);
2016 DEFUN ("search-forward", Fsearch_forward, 1, 5, "sSearch: ", /*
2017 Search forward from point for STRING.
2018 Set point to the end of the occurrence found, and return point.
2020 Optional second argument LIMIT bounds the search; it is a buffer
2021 position. The match found must not extend after that position. The
2022 value nil is equivalent to (point-max).
2024 Optional third argument NOERROR, if t, means just return nil (no
2025 error) if the search fails. If neither nil nor t, set point to LIMIT
2028 Optional fourth argument COUNT is a repeat count--search for
2029 successive occurrences.
2031 Optional fifth argument BUFFER specifies the buffer to search in and
2032 defaults to the current buffer.
2034 See also the functions `match-beginning', `match-end' and `replace-match'.
2036 (string, limit, noerror, count, buffer))
2038 return search_command (string, limit, noerror, count, buffer, 1, 0, 0);
2041 DEFUN ("word-search-backward", Fword_search_backward, 1, 5,
2042 "sWord search backward: ", /*
2043 Search backward from point for STRING, ignoring differences in punctuation.
2044 Set point to the beginning of the occurrence found, and return point.
2046 Optional second argument LIMIT bounds the search; it is a buffer
2047 position. The match found must not extend before that position.
2048 The value nil is equivalent to (point-min).
2050 Optional third argument NOERROR, if t, means just return nil (no
2051 error) if the search fails. If neither nil nor t, set point to LIMIT
2054 Optional fourth argument COUNT is a repeat count--search for
2055 successive occurrences.
2057 Optional fifth argument BUFFER specifies the buffer to search in and
2058 defaults to the current buffer.
2060 See also the functions `match-beginning', `match-end' and `replace-match'.
2062 (string, limit, noerror, count, buffer))
2064 return search_command (wordify (buffer, string), limit, noerror, count,
2068 DEFUN ("word-search-forward", Fword_search_forward, 1, 5, "sWord search: ", /*
2069 Search forward from point for STRING, ignoring differences in punctuation.
2070 Set point to the end of the occurrence found, and return point.
2072 Optional second argument LIMIT bounds the search; it is a buffer
2073 position. The match found must not extend after that position. The
2074 value nil is equivalent to (point-max).
2076 Optional third argument NOERROR, if t, means just return nil (no
2077 error) if the search fails. If neither nil nor t, set point to LIMIT
2080 Optional fourth argument COUNT is a repeat count--search for
2081 successive occurrences.
2083 Optional fifth argument BUFFER specifies the buffer to search in and
2084 defaults to the current buffer.
2086 See also the functions `match-beginning', `match-end' and `replace-match'.
2088 (string, limit, noerror, count, buffer))
2090 return search_command (wordify (buffer, string), limit, noerror, count,
2094 DEFUN ("re-search-backward", Fre_search_backward, 1, 5,
2095 "sRE search backward: ", /*
2096 Search backward from point for match for regular expression REGEXP.
2097 Set point to the beginning of the match, and return point.
2098 The match found is the one starting last in the buffer
2099 and yet ending before the origin of the search.
2101 Optional second argument LIMIT bounds the search; it is a buffer
2102 position. The match found must not extend before that position.
2103 The value nil is equivalent to (point-min).
2105 Optional third argument NOERROR, if t, means just return nil (no
2106 error) if the search fails. If neither nil nor t, set point to LIMIT
2109 Optional fourth argument COUNT is a repeat count--search for
2110 successive occurrences.
2112 Optional fifth argument BUFFER specifies the buffer to search in and
2113 defaults to the current buffer.
2115 See also the functions `match-beginning', `match-end' and `replace-match'.
2117 (regexp, limit, noerror, count, buffer))
2119 return search_command (regexp, limit, noerror, count, buffer, -1, 1, 0);
2122 DEFUN ("re-search-forward", Fre_search_forward, 1, 5, "sRE search: ", /*
2123 Search forward from point for regular expression REGEXP.
2124 Set point to the end of the occurrence found, and return point.
2126 Optional second argument LIMIT bounds the search; it is a buffer
2127 position. The match found must not extend after that position. The
2128 value nil is equivalent to (point-max).
2130 Optional third argument NOERROR, if t, means just return nil (no
2131 error) if the search fails. If neither nil nor t, set point to LIMIT
2134 Optional fourth argument COUNT is a repeat count--search for
2135 successive occurrences.
2137 Optional fifth argument BUFFER specifies the buffer to search in and
2138 defaults to the current buffer.
2140 See also the functions `match-beginning', `match-end' and `replace-match'.
2142 (regexp, limit, noerror, count, buffer))
2144 return search_command (regexp, limit, noerror, count, buffer, 1, 1, 0);
2147 DEFUN ("posix-search-backward", Fposix_search_backward, 1, 5,
2148 "sPosix search backward: ", /*
2149 Search backward from point for match for regular expression REGEXP.
2150 Find the longest match in accord with Posix regular expression rules.
2151 Set point to the beginning of the match, and return point.
2152 The match found is the one starting last in the buffer
2153 and yet ending before the origin of the search.
2155 Optional second argument LIMIT bounds the search; it is a buffer
2156 position. The match found must not extend before that position.
2157 The value nil is equivalent to (point-min).
2159 Optional third argument NOERROR, if t, means just return nil (no
2160 error) if the search fails. If neither nil nor t, set point to LIMIT
2163 Optional fourth argument COUNT is a repeat count--search for
2164 successive occurrences.
2166 Optional fifth argument BUFFER specifies the buffer to search in and
2167 defaults to the current buffer.
2169 See also the functions `match-beginning', `match-end' and `replace-match'.
2171 (regexp, limit, noerror, count, buffer))
2173 return search_command (regexp, limit, noerror, count, buffer, -1, 1, 1);
2176 DEFUN ("posix-search-forward", Fposix_search_forward, 1, 5, "sPosix search: ", /*
2177 Search forward from point for regular expression REGEXP.
2178 Find the longest match in accord with Posix regular expression rules.
2179 Set point to the end of the occurrence found, and return point.
2181 Optional second argument LIMIT bounds the search; it is a buffer
2182 position. The match found must not extend after that position. The
2183 value nil is equivalent to (point-max).
2185 Optional third argument NOERROR, if t, means just return nil (no
2186 error) if the search fails. If neither nil nor t, set point to LIMIT
2189 Optional fourth argument COUNT is a repeat count--search for
2190 successive occurrences.
2192 Optional fifth argument BUFFER specifies the buffer to search in and
2193 defaults to the current buffer.
2195 See also the functions `match-beginning', `match-end' and `replace-match'.
2197 (regexp, limit, noerror, count, buffer))
2199 return search_command (regexp, limit, noerror, count, buffer, 1, 1, 1);
2204 free_created_dynarrs (Lisp_Object cons)
2206 Dynarr_free (get_opaque_ptr (XCAR (cons)));
2207 Dynarr_free (get_opaque_ptr (XCDR (cons)));
2208 free_opaque_ptr (XCAR (cons));
2209 free_opaque_ptr (XCDR (cons));
2210 free_cons (XCONS (cons));
2214 DEFUN ("replace-match", Freplace_match, 1, 5, 0, /*
2215 Replace text matched by last search with REPLACEMENT.
2216 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2217 Otherwise maybe capitalize the whole text, or maybe just word initials,
2218 based on the replaced text.
2219 If the replaced text has only capital letters
2220 and has at least one multiletter word, convert REPLACEMENT to all caps.
2221 If the replaced text has at least one word starting with a capital letter,
2222 then capitalize each word in REPLACEMENT.
2224 If third arg LITERAL is non-nil, insert REPLACEMENT literally.
2225 Otherwise treat `\\' as special:
2226 `\\&' in REPLACEMENT means substitute original matched text.
2227 `\\N' means substitute what matched the Nth `\\(...\\)'.
2228 If Nth parens didn't match, substitute nothing.
2229 `\\\\' means insert one `\\'.
2230 `\\u' means upcase the next character.
2231 `\\l' means downcase the next character.
2232 `\\U' means begin upcasing all following characters.
2233 `\\L' means begin downcasing all following characters.
2234 `\\E' means terminate the effect of any `\\U' or `\\L'.
2235 Case changes made with `\\u', `\\l', `\\U', and `\\L' override
2236 all other case changes that may be made in the replaced text.
2237 FIXEDCASE and LITERAL are optional arguments.
2238 Leaves point at end of replacement text.
2240 The optional fourth argument STRING can be a string to modify.
2241 In that case, this function creates and returns a new string
2242 which is made by replacing the part of STRING that was matched.
2243 When fourth argument is a string, fifth argument STRBUFFER specifies
2244 the buffer to be used for syntax-table and case-table lookup and
2245 defaults to the current buffer. When fourth argument is not a string,
2246 the buffer that the match occurred in has automatically been remembered
2247 and you do not need to specify it.
2249 (replacement, fixedcase, literal, string, strbuffer))
2251 /* This function has been Mule-ized. */
2252 /* This function can GC */
2253 enum { nochange, all_caps, cap_initial } case_action;
2255 int some_multiletter_word;
2258 int some_nonuppercase_initial;
2262 Lisp_Char_Table *syntax_table;
2265 int_dynarr *ul_action_dynarr = 0;
2266 int_dynarr *ul_pos_dynarr = 0;
2269 CHECK_STRING (replacement);
2271 if (! NILP (string))
2273 CHECK_STRING (string);
2274 if (!EQ (last_thing_searched, Qt))
2275 error ("last thing matched was not a string");
2276 /* If the match data
2277 were abstracted into a special "match data" type instead
2278 of the typical half-assed "let the implementation be
2279 visible" form it's in, we could extend it to include
2280 the last string matched and the buffer used for that
2281 matching. But of course we can't change it as it is. */
2282 buf = decode_buffer (strbuffer, 0);
2283 XSETBUFFER (buffer, buf);
2287 if (!BUFFERP (last_thing_searched))
2288 error ("last thing matched was not a buffer");
2289 buffer = last_thing_searched;
2290 buf = XBUFFER (buffer);
2293 syntax_table = XCHAR_TABLE (buf->mirror_syntax_table);
2295 case_action = nochange; /* We tried an initialization */
2296 /* but some C compilers blew it */
2298 if (search_regs.num_regs == 0)
2299 error ("replace-match called before any match found");
2303 if (search_regs.start[0] < BUF_BEGV (buf)
2304 || search_regs.start[0] > search_regs.end[0]
2305 || search_regs.end[0] > BUF_ZV (buf))
2306 args_out_of_range (make_int (search_regs.start[0]),
2307 make_int (search_regs.end[0]));
2311 if (search_regs.start[0] < 0
2312 || search_regs.start[0] > search_regs.end[0]
2313 || search_regs.end[0] > XSTRING_CHAR_LENGTH (string))
2314 args_out_of_range (make_int (search_regs.start[0]),
2315 make_int (search_regs.end[0]));
2318 if (NILP (fixedcase))
2320 /* Decide how to casify by examining the matched text. */
2322 last = search_regs.end[0];
2324 case_action = all_caps;
2326 /* some_multiletter_word is set nonzero if any original word
2327 is more than one letter long. */
2328 some_multiletter_word = 0;
2330 some_nonuppercase_initial = 0;
2333 for (pos = search_regs.start[0]; pos < last; pos++)
2336 c = BUF_FETCH_CHAR (buf, pos);
2338 c = string_char (XSTRING (string), pos);
2340 if (LOWERCASEP (buf, c))
2342 /* Cannot be all caps if any original char is lower case */
2345 if (!WORD_SYNTAX_P (syntax_table, prevc))
2346 some_nonuppercase_initial = 1;
2348 some_multiletter_word = 1;
2350 else if (!NOCASEP (buf, c))
2353 if (!WORD_SYNTAX_P (syntax_table, prevc))
2356 some_multiletter_word = 1;
2360 /* If the initial is a caseless word constituent,
2361 treat that like a lowercase initial. */
2362 if (!WORD_SYNTAX_P (syntax_table, prevc))
2363 some_nonuppercase_initial = 1;
2369 /* Convert to all caps if the old text is all caps
2370 and has at least one multiletter word. */
2371 if (! some_lowercase && some_multiletter_word)
2372 case_action = all_caps;
2373 /* Capitalize each word, if the old text has all capitalized words. */
2374 else if (!some_nonuppercase_initial && some_multiletter_word)
2375 case_action = cap_initial;
2376 else if (!some_nonuppercase_initial && some_uppercase)
2377 /* Should x -> yz, operating on X, give Yz or YZ?
2378 We'll assume the latter. */
2379 case_action = all_caps;
2381 case_action = nochange;
2384 /* Do replacement in a string. */
2387 Lisp_Object before, after;
2389 speccount = specpdl_depth ();
2390 before = Fsubstring (string, Qzero, make_int (search_regs.start[0]));
2391 after = Fsubstring (string, make_int (search_regs.end[0]), Qnil);
2393 /* Do case substitution into REPLACEMENT if desired. */
2396 Charcount stlen = XSTRING_CHAR_LENGTH (replacement);
2398 /* XEmacs change: rewrote this loop somewhat to make it
2399 cleaner. Also added \U, \E, etc. */
2400 Charcount literal_start = 0;
2401 /* We build up the substituted string in ACCUM. */
2406 /* OK, the basic idea here is that we scan through the
2407 replacement string until we find a backslash, which
2408 represents a substring of the original string to be
2409 substituted. We then append onto ACCUM the literal
2410 text before the backslash (LASTPOS marks the
2411 beginning of this) followed by the substring of the
2412 original string that needs to be inserted. */
2413 for (strpos = 0; strpos < stlen; strpos++)
2415 /* If LITERAL_END is set, we've encountered a backslash
2416 (the end of literal text to be inserted). */
2417 Charcount literal_end = -1;
2418 /* If SUBSTART is set, we need to also insert the
2419 text from SUBSTART to SUBEND in the original string. */
2420 Charcount substart = -1;
2421 Charcount subend = -1;
2423 c = string_char (XSTRING (replacement), strpos);
2424 if (c == '\\' && strpos < stlen - 1)
2426 c = string_char (XSTRING (replacement), ++strpos);
2429 literal_end = strpos - 1;
2430 substart = search_regs.start[0];
2431 subend = search_regs.end[0];
2433 else if (c >= '1' && c <= '9' &&
2434 c <= search_regs.num_regs + '0')
2436 if (search_regs.start[c - '0'] >= 0)
2438 literal_end = strpos - 1;
2439 substart = search_regs.start[c - '0'];
2440 subend = search_regs.end[c - '0'];
2443 else if (c == 'U' || c == 'u' || c == 'L' || c == 'l' ||
2446 /* Keep track of all case changes requested, but don't
2447 make them now. Do them later so we override
2451 ul_pos_dynarr = Dynarr_new (int);
2452 ul_action_dynarr = Dynarr_new (int);
2453 record_unwind_protect
2454 (free_created_dynarrs,
2456 (make_opaque_ptr (ul_pos_dynarr),
2457 make_opaque_ptr (ul_action_dynarr)));
2459 literal_end = strpos - 1;
2460 Dynarr_add (ul_pos_dynarr,
2462 ? XSTRING_CHAR_LENGTH (accum)
2463 : 0) + (literal_end - literal_start));
2464 Dynarr_add (ul_action_dynarr, c);
2467 /* So we get just one backslash. */
2468 literal_end = strpos;
2470 if (literal_end >= 0)
2472 Lisp_Object literal_text = Qnil;
2473 Lisp_Object substring = Qnil;
2474 if (literal_end != literal_start)
2475 literal_text = Fsubstring (replacement,
2476 make_int (literal_start),
2477 make_int (literal_end));
2478 if (substart >= 0 && subend != substart)
2479 substring = Fsubstring (string,
2480 make_int (substart),
2482 if (!NILP (literal_text) || !NILP (substring))
2483 accum = concat3 (accum, literal_text, substring);
2484 literal_start = strpos + 1;
2488 if (strpos != literal_start)
2489 /* some literal text at end to be inserted */
2490 replacement = concat2 (accum, Fsubstring (replacement,
2491 make_int (literal_start),
2492 make_int (strpos)));
2494 replacement = accum;
2497 /* replacement can be nil. */
2498 if (NILP (replacement))
2499 replacement = build_string ("");
2501 if (case_action == all_caps)
2502 replacement = Fupcase (replacement, buffer);
2503 else if (case_action == cap_initial)
2504 replacement = Fupcase_initials (replacement, buffer);
2506 /* Now finally, we need to process the \U's, \E's, etc. */
2510 int cur_action = 'E';
2511 Charcount stlen = XSTRING_CHAR_LENGTH (replacement);
2514 for (strpos = 0; strpos < stlen; strpos++)
2516 Emchar curchar = string_char (XSTRING (replacement), strpos);
2517 Emchar newchar = -1;
2518 if (i < Dynarr_length (ul_pos_dynarr) &&
2519 strpos == Dynarr_at (ul_pos_dynarr, i))
2521 int new_action = Dynarr_at (ul_action_dynarr, i);
2523 if (new_action == 'u')
2524 newchar = UPCASE (buf, curchar);
2525 else if (new_action == 'l')
2526 newchar = DOWNCASE (buf, curchar);
2528 cur_action = new_action;
2532 if (cur_action == 'U')
2533 newchar = UPCASE (buf, curchar);
2534 else if (cur_action == 'L')
2535 newchar = DOWNCASE (buf, curchar);
2539 if (newchar != curchar)
2540 set_string_char (XSTRING (replacement), strpos, newchar);
2544 /* frees the Dynarrs if necessary. */
2545 unbind_to (speccount, Qnil);
2546 return concat3 (before, replacement, after);
2549 mc_count = begin_multiple_change (buf, search_regs.start[0],
2550 search_regs.end[0]);
2552 /* begin_multiple_change() records an unwind-protect, so we need to
2553 record this value now. */
2554 speccount = specpdl_depth ();
2556 /* We insert the replacement text before the old text, and then
2557 delete the original text. This means that markers at the
2558 beginning or end of the original will float to the corresponding
2559 position in the replacement. */
2560 BUF_SET_PT (buf, search_regs.start[0]);
2561 if (!NILP (literal))
2562 Finsert (1, &replacement);
2565 Charcount stlen = XSTRING_CHAR_LENGTH (replacement);
2567 struct gcpro gcpro1;
2568 GCPRO1 (replacement);
2569 for (strpos = 0; strpos < stlen; strpos++)
2571 Charcount offset = BUF_PT (buf) - search_regs.start[0];
2573 c = string_char (XSTRING (replacement), strpos);
2574 if (c == '\\' && strpos < stlen - 1)
2576 c = string_char (XSTRING (replacement), ++strpos);
2578 Finsert_buffer_substring
2580 make_int (search_regs.start[0] + offset),
2581 make_int (search_regs.end[0] + offset));
2582 else if (c >= '1' && c <= '9' &&
2583 c <= search_regs.num_regs + '0')
2585 if (search_regs.start[c - '0'] >= 1)
2586 Finsert_buffer_substring
2588 make_int (search_regs.start[c - '0'] + offset),
2589 make_int (search_regs.end[c - '0'] + offset));
2591 else if (c == 'U' || c == 'u' || c == 'L' || c == 'l' ||
2594 /* Keep track of all case changes requested, but don't
2595 make them now. Do them later so we override
2599 ul_pos_dynarr = Dynarr_new (int);
2600 ul_action_dynarr = Dynarr_new (int);
2601 record_unwind_protect
2602 (free_created_dynarrs,
2603 Fcons (make_opaque_ptr (ul_pos_dynarr),
2604 make_opaque_ptr (ul_action_dynarr)));
2606 Dynarr_add (ul_pos_dynarr, BUF_PT (buf));
2607 Dynarr_add (ul_action_dynarr, c);
2610 buffer_insert_emacs_char (buf, c);
2613 buffer_insert_emacs_char (buf, c);
2618 inslen = BUF_PT (buf) - (search_regs.start[0]);
2619 buffer_delete_range (buf, search_regs.start[0] + inslen, search_regs.end[0] +
2622 if (case_action == all_caps)
2623 Fupcase_region (make_int (BUF_PT (buf) - inslen),
2624 make_int (BUF_PT (buf)), buffer);
2625 else if (case_action == cap_initial)
2626 Fupcase_initials_region (make_int (BUF_PT (buf) - inslen),
2627 make_int (BUF_PT (buf)), buffer);
2629 /* Now go through and make all the case changes that were requested
2630 in the replacement string. */
2633 Bufpos eend = BUF_PT (buf);
2635 int cur_action = 'E';
2637 for (pos = BUF_PT (buf) - inslen; pos < eend; pos++)
2639 Emchar curchar = BUF_FETCH_CHAR (buf, pos);
2640 Emchar newchar = -1;
2641 if (i < Dynarr_length (ul_pos_dynarr) &&
2642 pos == Dynarr_at (ul_pos_dynarr, i))
2644 int new_action = Dynarr_at (ul_action_dynarr, i);
2646 if (new_action == 'u')
2647 newchar = UPCASE (buf, curchar);
2648 else if (new_action == 'l')
2649 newchar = DOWNCASE (buf, curchar);
2651 cur_action = new_action;
2655 if (cur_action == 'U')
2656 newchar = UPCASE (buf, curchar);
2657 else if (cur_action == 'L')
2658 newchar = DOWNCASE (buf, curchar);
2662 if (newchar != curchar)
2663 buffer_replace_char (buf, pos, newchar, 0, 0);
2667 /* frees the Dynarrs if necessary. */
2668 unbind_to (speccount, Qnil);
2669 end_multiple_change (buf, mc_count);
2675 match_limit (Lisp_Object num, int beginningp)
2677 /* This function has been Mule-ized. */
2682 if (n < 0 || n >= search_regs.num_regs)
2683 args_out_of_range (num, make_int (search_regs.num_regs));
2684 if (search_regs.num_regs == 0 ||
2685 search_regs.start[n] < 0)
2687 return make_int (beginningp ? search_regs.start[n] : search_regs.end[n]);
2690 DEFUN ("match-beginning", Fmatch_beginning, 1, 1, 0, /*
2691 Return position of start of text matched by last regexp search.
2692 NUM, specifies which parenthesized expression in the last regexp.
2693 Value is nil if NUMth pair didn't match, or there were less than NUM pairs.
2694 Zero means the entire text matched by the whole regexp or whole string.
2698 return match_limit (num, 1);
2701 DEFUN ("match-end", Fmatch_end, 1, 1, 0, /*
2702 Return position of end of text matched by last regexp search.
2703 NUM specifies which parenthesized expression in the last regexp.
2704 Value is nil if NUMth pair didn't match, or there were less than NUM pairs.
2705 Zero means the entire text matched by the whole regexp or whole string.
2709 return match_limit (num, 0);
2712 DEFUN ("match-data", Fmatch_data, 0, 2, 0, /*
2713 Return a list containing all info on what the last regexp search matched.
2714 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2715 All the elements are markers or nil (nil if the Nth pair didn't match)
2716 if the last match was on a buffer; integers or nil if a string was matched.
2717 Use `store-match-data' to reinstate the data in this list.
2719 If INTEGERS (the optional first argument) is non-nil, always use integers
2720 \(rather than markers) to represent buffer positions.
2721 If REUSE is a list, reuse it as part of the value. If REUSE is long enough
2722 to hold all the values, and if INTEGERS is non-nil, no consing is done.
2726 /* This function has been Mule-ized. */
2727 Lisp_Object tail, prev;
2732 if (NILP (last_thing_searched))
2733 /*error ("match-data called before any match found");*/
2736 data = alloca_array (Lisp_Object, 2 * search_regs.num_regs);
2739 for (i = 0; i < search_regs.num_regs; i++)
2741 Bufpos start = search_regs.start[i];
2744 if (EQ (last_thing_searched, Qt)
2745 || !NILP (integers))
2747 data[2 * i] = make_int (start);
2748 data[2 * i + 1] = make_int (search_regs.end[i]);
2750 else if (BUFFERP (last_thing_searched))
2752 data[2 * i] = Fmake_marker ();
2753 Fset_marker (data[2 * i],
2755 last_thing_searched);
2756 data[2 * i + 1] = Fmake_marker ();
2757 Fset_marker (data[2 * i + 1],
2758 make_int (search_regs.end[i]),
2759 last_thing_searched);
2762 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2768 data[2 * i] = data [2 * i + 1] = Qnil;
2771 return Flist (2 * len + 2, data);
2773 /* If REUSE is a list, store as many value elements as will fit
2774 into the elements of REUSE. */
2775 for (prev = Qnil, i = 0, tail = reuse; CONSP (tail); i++, tail = XCDR (tail))
2777 if (i < 2 * len + 2)
2778 XCAR (tail) = data[i];
2784 /* If we couldn't fit all value elements into REUSE,
2785 cons up the rest of them and add them to the end of REUSE. */
2786 if (i < 2 * len + 2)
2787 XCDR (prev) = Flist (2 * len + 2 - i, data + i);
2793 DEFUN ("store-match-data", Fstore_match_data, 1, 1, 0, /*
2794 Set internal data on last search match from elements of LIST.
2795 LIST should have been created by calling `match-data' previously.
2799 /* This function has been Mule-ized. */
2801 REGISTER Lisp_Object marker;
2805 if (running_asynch_code)
2806 save_search_regs ();
2808 CONCHECK_LIST (list);
2810 /* Unless we find a marker with a buffer in LIST, assume that this
2811 match data came from a string. */
2812 last_thing_searched = Qt;
2814 /* Allocate registers if they don't already exist. */
2815 length = XINT (Flength (list)) / 2;
2816 num_regs = search_regs.num_regs;
2818 if (length > num_regs)
2820 if (search_regs.num_regs == 0)
2822 search_regs.start = xnew_array (regoff_t, length);
2823 search_regs.end = xnew_array (regoff_t, length);
2827 XREALLOC_ARRAY (search_regs.start, regoff_t, length);
2828 XREALLOC_ARRAY (search_regs.end, regoff_t, length);
2831 search_regs.num_regs = length;
2834 for (i = 0; i < num_regs; i++)
2836 marker = Fcar (list);
2839 search_regs.start[i] = -1;
2844 if (MARKERP (marker))
2846 if (XMARKER (marker)->buffer == 0)
2849 XSETBUFFER (last_thing_searched, XMARKER (marker)->buffer);
2852 CHECK_INT_COERCE_MARKER (marker);
2853 search_regs.start[i] = XINT (marker);
2856 marker = Fcar (list);
2857 if (MARKERP (marker) && XMARKER (marker)->buffer == 0)
2860 CHECK_INT_COERCE_MARKER (marker);
2861 search_regs.end[i] = XINT (marker);
2869 /* If non-zero the match data have been saved in saved_search_regs
2870 during the execution of a sentinel or filter. */
2871 static int search_regs_saved;
2872 static struct re_registers saved_search_regs;
2874 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2875 if asynchronous code (filter or sentinel) is running. */
2877 save_search_regs (void)
2879 if (!search_regs_saved)
2881 saved_search_regs.num_regs = search_regs.num_regs;
2882 saved_search_regs.start = search_regs.start;
2883 saved_search_regs.end = search_regs.end;
2884 search_regs.num_regs = 0;
2885 search_regs.start = 0;
2886 search_regs.end = 0;
2888 search_regs_saved = 1;
2892 /* Called upon exit from filters and sentinels. */
2894 restore_match_data (void)
2896 if (search_regs_saved)
2898 if (search_regs.num_regs > 0)
2900 xfree (search_regs.start);
2901 xfree (search_regs.end);
2903 search_regs.num_regs = saved_search_regs.num_regs;
2904 search_regs.start = saved_search_regs.start;
2905 search_regs.end = saved_search_regs.end;
2907 search_regs_saved = 0;
2911 /* Quote a string to inactivate reg-expr chars */
2913 DEFUN ("regexp-quote", Fregexp_quote, 1, 1, 0, /*
2914 Return a regexp string which matches exactly STRING and nothing else.
2918 REGISTER Bufbyte *in, *out, *end;
2919 REGISTER Bufbyte *temp;
2921 CHECK_STRING (string);
2923 temp = (Bufbyte *) alloca (XSTRING_LENGTH (string) * 2);
2925 /* Now copy the data into the new string, inserting escapes. */
2927 in = XSTRING_DATA (string);
2928 end = in + XSTRING_LENGTH (string);
2933 Emchar c = charptr_emchar (in);
2935 if (c == '[' || c == ']'
2936 || c == '*' || c == '.' || c == '\\'
2937 || c == '?' || c == '+'
2938 || c == '^' || c == '$')
2940 out += set_charptr_emchar (out, c);
2944 return make_string (temp, out - temp);
2947 DEFUN ("set-word-regexp", Fset_word_regexp, 1, 1, 0, /*
2948 Set the regexp to be used to match a word in regular-expression searching.
2949 #### Not yet implemented. Currently does nothing.
2950 #### Do not use this yet. Its calling interface is likely to change.
2958 /************************************************************************/
2959 /* initialization */
2960 /************************************************************************/
2963 syms_of_search (void)
2966 DEFERROR_STANDARD (Qsearch_failed, Qinvalid_operation);
2967 DEFERROR_STANDARD (Qinvalid_regexp, Qsyntax_error);
2969 DEFSUBR (Flooking_at);
2970 DEFSUBR (Fposix_looking_at);
2971 DEFSUBR (Fstring_match);
2972 DEFSUBR (Fposix_string_match);
2973 DEFSUBR (Fskip_chars_forward);
2974 DEFSUBR (Fskip_chars_backward);
2975 DEFSUBR (Fskip_syntax_forward);
2976 DEFSUBR (Fskip_syntax_backward);
2977 DEFSUBR (Fsearch_forward);
2978 DEFSUBR (Fsearch_backward);
2979 DEFSUBR (Fword_search_forward);
2980 DEFSUBR (Fword_search_backward);
2981 DEFSUBR (Fre_search_forward);
2982 DEFSUBR (Fre_search_backward);
2983 DEFSUBR (Fposix_search_forward);
2984 DEFSUBR (Fposix_search_backward);
2985 DEFSUBR (Freplace_match);
2986 DEFSUBR (Fmatch_beginning);
2987 DEFSUBR (Fmatch_end);
2988 DEFSUBR (Fmatch_data);
2989 DEFSUBR (Fstore_match_data);
2990 DEFSUBR (Fregexp_quote);
2991 DEFSUBR (Fset_word_regexp);
2995 reinit_vars_of_search (void)
2999 last_thing_searched = Qnil;
3000 staticpro_nodump (&last_thing_searched);
3002 for (i = 0; i < REGEXP_CACHE_SIZE; ++i)
3004 searchbufs[i].buf.allocated = 100;
3005 searchbufs[i].buf.buffer = (unsigned char *) xmalloc (100);
3006 searchbufs[i].buf.fastmap = searchbufs[i].fastmap;
3007 searchbufs[i].regexp = Qnil;
3008 staticpro_nodump (&searchbufs[i].regexp);
3009 searchbufs[i].next = (i == REGEXP_CACHE_SIZE-1 ? 0 : &searchbufs[i+1]);
3011 searchbuf_head = &searchbufs[0];
3015 vars_of_search (void)
3017 reinit_vars_of_search ();
3019 DEFVAR_LISP ("forward-word-regexp", &Vforward_word_regexp /*
3020 *Regular expression to be used in `forward-word'.
3021 #### Not yet implemented.
3023 Vforward_word_regexp = Qnil;
3025 DEFVAR_LISP ("backward-word-regexp", &Vbackward_word_regexp /*
3026 *Regular expression to be used in `backward-word'.
3027 #### Not yet implemented.
3029 Vbackward_word_regexp = Qnil;
3033 complex_vars_of_search (void)
3035 Vskip_chars_range_table = Fmake_range_table ();
3036 staticpro (&Vskip_chars_range_table);