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_emacs_buffer = buf;
316 regex_emacs_buffer_p = 1;
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_emacs_buffer = buf;
407 regex_emacs_buffer_p = 0;
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_emacs_buffer = current_buffer;
499 regex_emacs_buffer_p = 0;
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];
787 Lisp_Char_Table *syntax_table = XCHAR_TABLE (buf->mirror_syntax_table);
791 limit = forwardp ? BUF_ZV (buf) : BUF_BEGV (buf);
794 CHECK_INT_COERCE_MARKER (lim);
797 /* In any case, don't allow scan outside bounds of buffer. */
798 if (limit > BUF_ZV (buf)) limit = BUF_ZV (buf);
799 if (limit < BUF_BEGV (buf)) limit = BUF_BEGV (buf);
802 CHECK_STRING (string);
803 p = XSTRING_DATA (string);
804 pend = p + XSTRING_LENGTH (string);
805 memset (fastmap, 0, sizeof (fastmap));
807 Fclear_range_table (Vskip_chars_range_table);
809 if (p != pend && *p == '^')
815 /* Find the characters specified and set their elements of fastmap.
816 If syntaxp, each character counts as itself.
817 Otherwise, handle backslashes and ranges specially */
821 c = charptr_emchar (p);
825 if (c < 0400 && syntax_spec_code[c] < (unsigned char) Smax)
828 signal_simple_error ("Invalid syntax designator",
835 if (p == pend) break;
836 c = charptr_emchar (p);
839 if (p != pend && *p == '-')
844 if (p == pend) break;
845 cend = charptr_emchar (p);
846 while (c <= cend && c < 0400)
852 Fput_range_table (make_int (c), make_int (cend), Qt,
853 Vskip_chars_range_table);
861 Fput_range_table (make_int (c), make_int (c), Qt,
862 Vskip_chars_range_table);
867 if (syntaxp && fastmap['-'] != 0)
870 /* If ^ was the first character, complement the fastmap.
871 We don't complement the range table, however; we just use negate
872 in the comparisons below. */
875 for (i = 0; i < (int) (sizeof fastmap); i++)
879 Bufpos start_point = BUF_PT (buf);
883 /* All syntax designators are normal chars so nothing strange
887 while (BUF_PT (buf) < limit
888 && fastmap[(unsigned char)
890 [(int) SYNTAX (syntax_table,
892 (buf, BUF_PT (buf)))]])
893 BUF_SET_PT (buf, BUF_PT (buf) + 1);
897 while (BUF_PT (buf) > limit
898 && fastmap[(unsigned char)
900 [(int) SYNTAX (syntax_table,
902 (buf, BUF_PT (buf) - 1))]])
903 BUF_SET_PT (buf, BUF_PT (buf) - 1);
910 while (BUF_PT (buf) < limit)
912 Emchar ch = BUF_FETCH_CHAR (buf, BUF_PT (buf));
913 if ((ch < 0400) ? fastmap[ch] :
914 (NILP (Fget_range_table (make_int (ch),
915 Vskip_chars_range_table,
918 BUF_SET_PT (buf, BUF_PT (buf) + 1);
925 while (BUF_PT (buf) > limit)
927 Emchar ch = BUF_FETCH_CHAR (buf, BUF_PT (buf) - 1);
928 if ((ch < 0400) ? fastmap[ch] :
929 (NILP (Fget_range_table (make_int (ch),
930 Vskip_chars_range_table,
933 BUF_SET_PT (buf, BUF_PT (buf) - 1);
940 return make_int (BUF_PT (buf) - start_point);
944 DEFUN ("skip-chars-forward", Fskip_chars_forward, 1, 3, 0, /*
945 Move point forward, stopping before a char not in STRING, or at pos LIMIT.
946 STRING is like the inside of a `[...]' in a regular expression
947 except that `]' is never special and `\\' quotes `^', `-' or `\\'.
948 Thus, with arg "a-zA-Z", this skips letters stopping before first nonletter.
949 With arg "^a-zA-Z", skips nonletters stopping before first letter.
950 Returns the distance traveled, either zero or positive.
952 Optional argument BUFFER defaults to the current buffer.
954 (string, limit, buffer))
956 return skip_chars (decode_buffer (buffer, 0), 1, 0, string, limit);
959 DEFUN ("skip-chars-backward", Fskip_chars_backward, 1, 3, 0, /*
960 Move point backward, stopping after a char not in STRING, or at pos LIMIT.
961 See `skip-chars-forward' for details.
962 Returns the distance traveled, either zero or negative.
964 Optional argument BUFFER defaults to the current buffer.
966 (string, limit, buffer))
968 return skip_chars (decode_buffer (buffer, 0), 0, 0, string, limit);
972 DEFUN ("skip-syntax-forward", Fskip_syntax_forward, 1, 3, 0, /*
973 Move point forward across chars in specified syntax classes.
974 SYNTAX is a string of syntax code characters.
975 Stop before a char whose syntax is not in SYNTAX, or at position LIMIT.
976 If SYNTAX starts with ^, skip characters whose syntax is NOT in SYNTAX.
977 This function returns the distance traveled, either zero or positive.
979 Optional argument BUFFER defaults to the current buffer.
981 (syntax, limit, buffer))
983 return skip_chars (decode_buffer (buffer, 0), 1, 1, syntax, limit);
986 DEFUN ("skip-syntax-backward", Fskip_syntax_backward, 1, 3, 0, /*
987 Move point backward across chars in specified syntax classes.
988 SYNTAX is a string of syntax code characters.
989 Stop on reaching a char whose syntax is not in SYNTAX, or at position LIMIT.
990 If SYNTAX starts with ^, skip characters whose syntax is NOT in SYNTAX.
991 This function returns the distance traveled, either zero or negative.
993 Optional argument BUFFER defaults to the current buffer.
995 (syntax, limit, buffer))
997 return skip_chars (decode_buffer (buffer, 0), 0, 1, syntax, limit);
1001 /* Subroutines of Lisp buffer search functions. */
1004 search_command (Lisp_Object string, Lisp_Object limit, Lisp_Object noerror,
1005 Lisp_Object count, Lisp_Object buffer, int direction,
1008 /* This function has been Mule-ized, except for the trt table handling. */
1011 EMACS_INT n = direction;
1020 buf = decode_buffer (buffer, 0);
1021 CHECK_STRING (string);
1023 lim = n > 0 ? BUF_ZV (buf) : BUF_BEGV (buf);
1026 CHECK_INT_COERCE_MARKER (limit);
1028 if (n > 0 ? lim < BUF_PT (buf) : lim > BUF_PT (buf))
1029 error ("Invalid search limit (wrong side of point)");
1030 if (lim > BUF_ZV (buf))
1032 if (lim < BUF_BEGV (buf))
1033 lim = BUF_BEGV (buf);
1036 np = search_buffer (buf, string, BUF_PT (buf), lim, n, RE,
1037 (!NILP (buf->case_fold_search)
1038 ? XCASE_TABLE_CANON (buf->case_table)
1040 (!NILP (buf->case_fold_search)
1041 ? XCASE_TABLE_EQV (buf->case_table)
1047 return signal_failure (string);
1048 if (!EQ (noerror, Qt))
1050 if (lim < BUF_BEGV (buf) || lim > BUF_ZV (buf))
1052 BUF_SET_PT (buf, lim);
1054 #if 0 /* This would be clean, but maybe programs depend on
1055 a value of nil here. */
1063 if (np < BUF_BEGV (buf) || np > BUF_ZV (buf))
1066 BUF_SET_PT (buf, np);
1068 return make_int (np);
1072 trivial_regexp_p (Lisp_Object regexp)
1074 /* This function has been Mule-ized. */
1075 Bytecount len = XSTRING_LENGTH (regexp);
1076 Bufbyte *s = XSTRING_DATA (regexp);
1081 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1088 case '|': case '(': case ')': case '`': case '\'': case 'b':
1089 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1092 /* 97/2/25 jhod Added for category matches */
1095 case '1': case '2': case '3': case '4': case '5':
1096 case '6': case '7': case '8': case '9':
1104 /* Search for the n'th occurrence of STRING in BUF,
1105 starting at position BUFPOS and stopping at position BUFLIM,
1106 treating PAT as a literal string if RE is false or as
1107 a regular expression if RE is true.
1109 If N is positive, searching is forward and BUFLIM must be greater
1111 If N is negative, searching is backward and BUFLIM must be less
1114 Returns -x if only N-x occurrences found (x > 0),
1115 or else the position at the beginning of the Nth occurrence
1116 (if searching backward) or the end (if searching forward).
1118 POSIX is nonzero if we want full backtracking (POSIX style)
1119 for this pattern. 0 means backtrack only enough to get a valid match. */
1121 search_buffer (struct buffer *buf, Lisp_Object string, Bufpos bufpos,
1122 Bufpos buflim, EMACS_INT n, int RE, Lisp_Object trt,
1123 Lisp_Object inverse_trt, int posix)
1125 /* This function has been Mule-ized, except for the trt table handling. */
1126 Bytecount len = XSTRING_LENGTH (string);
1127 Bufbyte *base_pat = XSTRING_DATA (string);
1128 REGISTER EMACS_INT i, j;
1133 if (running_asynch_code)
1134 save_search_regs ();
1136 /* Null string is found at starting position. */
1139 set_search_regs (buf, bufpos, 0);
1143 /* Searching 0 times means don't move. */
1147 pos = bufpos_to_bytind (buf, bufpos);
1148 lim = bufpos_to_bytind (buf, buflim);
1149 if (RE && !trivial_regexp_p (string))
1151 struct re_pattern_buffer *bufp;
1153 bufp = compile_pattern (string, &search_regs, trt, posix,
1156 /* Get pointers and sizes of the two strings
1157 that make up the visible portion of the buffer. */
1159 p1 = BI_BUF_BEGV (buf);
1160 p2 = BI_BUF_CEILING_OF (buf, p1);
1162 s2 = BI_BUF_ZV (buf) - p2;
1168 regex_emacs_buffer = buf;
1169 regex_emacs_buffer_p = 1;
1170 val = re_search_2 (bufp,
1171 (char *) BI_BUF_BYTE_ADDRESS (buf, p1), s1,
1172 (char *) BI_BUF_BYTE_ADDRESS (buf, p2), s2,
1173 pos - BI_BUF_BEGV (buf), lim - pos, &search_regs,
1174 pos - BI_BUF_BEGV (buf));
1178 matcher_overflow ();
1182 int num_regs = search_regs.num_regs;
1183 j = BI_BUF_BEGV (buf);
1184 for (i = 0; i < num_regs; i++)
1185 if (search_regs.start[i] >= 0)
1187 search_regs.start[i] += j;
1188 search_regs.end[i] += j;
1190 XSETBUFFER (last_thing_searched, buf);
1191 /* Set pos to the new position. */
1192 pos = search_regs.start[0];
1193 fixup_search_regs_for_buffer (buf);
1194 /* And bufpos too. */
1195 bufpos = search_regs.start[0];
1207 regex_emacs_buffer = buf;
1208 regex_emacs_buffer_p = 1;
1209 val = re_search_2 (bufp,
1210 (char *) BI_BUF_BYTE_ADDRESS (buf, p1), s1,
1211 (char *) BI_BUF_BYTE_ADDRESS (buf, p2), s2,
1212 pos - BI_BUF_BEGV (buf), lim - pos, &search_regs,
1213 lim - BI_BUF_BEGV (buf));
1216 matcher_overflow ();
1220 int num_regs = search_regs.num_regs;
1221 j = BI_BUF_BEGV (buf);
1222 for (i = 0; i < num_regs; i++)
1223 if (search_regs.start[i] >= 0)
1225 search_regs.start[i] += j;
1226 search_regs.end[i] += j;
1228 XSETBUFFER (last_thing_searched, buf);
1229 /* Set pos to the new position. */
1230 pos = search_regs.end[0];
1231 fixup_search_regs_for_buffer (buf);
1232 /* And bufpos too. */
1233 bufpos = search_regs.end[0];
1243 else /* non-RE case */
1245 int charset_base = -1;
1246 int boyer_moore_ok = 1;
1248 Bufbyte *patbuf = alloca_array (Bufbyte, len * MAX_EMCHAR_LEN);
1253 Bufbyte tmp_str[MAX_EMCHAR_LEN];
1254 Emchar c, translated, inverse;
1255 Bytecount orig_bytelen, new_bytelen, inv_bytelen;
1257 /* If we got here and the RE flag is set, it's because
1258 we're dealing with a regexp known to be trivial, so the
1259 backslash just quotes the next character. */
1260 if (RE && *base_pat == '\\')
1265 c = charptr_emchar (base_pat);
1266 translated = TRANSLATE (trt, c);
1267 inverse = TRANSLATE (inverse_trt, c);
1269 orig_bytelen = charcount_to_bytecount (base_pat, 1);
1270 inv_bytelen = set_charptr_emchar (tmp_str, inverse);
1271 new_bytelen = set_charptr_emchar (tmp_str, translated);
1274 if (new_bytelen != orig_bytelen || inv_bytelen != orig_bytelen)
1276 if (translated != c || inverse != c)
1278 /* Keep track of which character set row
1279 contains the characters that need translation. */
1280 int charset_base_code = c & ~CHAR_FIELD3_MASK;
1281 if (charset_base == -1)
1282 charset_base = charset_base_code;
1283 else if (charset_base != charset_base_code)
1284 /* If two different rows appear, needing translation,
1285 then we cannot use boyer_moore search. */
1288 memcpy (pat, tmp_str, new_bytelen);
1290 base_pat += orig_bytelen;
1291 len -= orig_bytelen;
1293 #else /* not MULE */
1296 /* If we got here and the RE flag is set, it's because
1297 we're dealing with a regexp known to be trivial, so the
1298 backslash just quotes the next character. */
1299 if (RE && *base_pat == '\\')
1304 *pat++ = TRANSLATE (trt, *base_pat++);
1308 pat = base_pat = patbuf;
1310 return boyer_moore (buf, base_pat, len, pos, lim, n,
1311 trt, inverse_trt, charset_base);
1313 return simple_search (buf, base_pat, len, pos, lim, n, trt);
1317 /* Do a simple string search N times for the string PAT,
1318 whose length is LEN/LEN_BYTE,
1319 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1320 TRT is the translation table.
1322 Return the character position where the match is found.
1323 Otherwise, if M matches remained to be found, return -M.
1325 This kind of search works regardless of what is in PAT and
1326 regardless of what is in TRT. It is used in cases where
1327 boyer_moore cannot work. */
1330 simple_search (struct buffer *buf, Bufbyte *base_pat, Bytecount len_byte,
1331 Bytind idx, Bytind lim, EMACS_INT n, Lisp_Object trt)
1333 int forward = n > 0;
1334 Bytecount buf_len = 0; /* Shut up compiler. */
1341 Bytecount this_len = len_byte;
1342 Bytind this_idx = idx;
1343 Bufbyte *p = base_pat;
1347 while (this_len > 0)
1349 Emchar pat_ch, buf_ch;
1352 pat_ch = charptr_emchar (p);
1353 buf_ch = BI_BUF_FETCH_CHAR (buf, this_idx);
1355 buf_ch = TRANSLATE (trt, buf_ch);
1357 if (buf_ch != pat_ch)
1360 pat_len = charcount_to_bytecount (p, 1);
1362 this_len -= pat_len;
1363 INC_BYTIND (buf, this_idx);
1367 buf_len = this_idx - idx;
1371 INC_BYTIND (buf, idx);
1380 Bytecount this_len = len_byte;
1381 Bytind this_idx = idx;
1385 p = base_pat + len_byte;
1387 while (this_len > 0)
1389 Emchar pat_ch, buf_ch;
1392 DEC_BYTIND (buf, this_idx);
1393 pat_ch = charptr_emchar (p);
1394 buf_ch = BI_BUF_FETCH_CHAR (buf, this_idx);
1396 buf_ch = TRANSLATE (trt, buf_ch);
1398 if (buf_ch != pat_ch)
1401 this_len -= charcount_to_bytecount (p, 1);
1405 buf_len = idx - this_idx;
1409 DEC_BYTIND (buf, idx);
1416 Bufpos beg, end, retval;
1419 beg = bytind_to_bufpos (buf, idx - buf_len);
1420 retval = end = bytind_to_bufpos (buf, idx);
1424 retval = beg = bytind_to_bufpos (buf, idx);
1425 end = bytind_to_bufpos (buf, idx + buf_len);
1427 set_search_regs (buf, beg, end - beg);
1437 /* Do Boyer-Moore search N times for the string PAT,
1438 whose length is LEN/LEN_BYTE,
1439 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1440 DIRECTION says which direction we search in.
1441 TRT and INVERSE_TRT are translation tables.
1443 This kind of search works if all the characters in PAT that have
1444 nontrivial translation are the same aside from the last byte. This
1445 makes it possible to translate just the last byte of a character,
1446 and do so after just a simple test of the context.
1448 If that criterion is not satisfied, do not call this function. */
1451 boyer_moore (struct buffer *buf, Bufbyte *base_pat, Bytecount len,
1452 Bytind pos, Bytind lim, EMACS_INT n, Lisp_Object trt,
1453 Lisp_Object inverse_trt, int charset_base)
1455 /* #### Someone really really really needs to comment the workings
1456 of this junk somewhat better.
1458 BTW "BM" stands for Boyer-Moore, which is one of the standard
1459 string-searching algorithms. It's the best string-searching
1460 algorithm out there, provided that:
1462 a) You're not fazed by algorithm complexity. (Rabin-Karp, which
1463 uses hashing, is much much easier to code but not as fast.)
1464 b) You can freely move backwards in the string that you're
1467 As the comment below tries to explain (but garbles in typical
1468 programmer-ese), the idea is that you don't have to do a
1469 string match at every successive position in the text. For
1470 example, let's say the pattern is "a very long string". We
1471 compare the last character in the string (`g') with the
1472 corresponding character in the text. If it mismatches, and
1473 it is, say, `z', then we can skip forward by the entire
1474 length of the pattern because `z' does not occur anywhere
1475 in the pattern. If the mismatching character does occur
1476 in the pattern, we can usually still skip forward by more
1477 than one: e.g. if it is `l', then we can skip forward
1478 by the length of the substring "ong string" -- i.e. the
1479 largest end section of the pattern that does not contain
1480 the mismatched character. So what we do is compute, for
1481 each possible character, the distance we can skip forward
1482 (the "stride") and use it in the string matching. This
1483 is what the BM_tab holds. */
1484 REGISTER EMACS_INT *BM_tab;
1485 EMACS_INT *BM_tab_base;
1486 REGISTER Bytecount dirlen;
1489 Bytecount stride_for_teases = 0;
1490 REGISTER EMACS_INT i, j;
1491 Bufbyte *pat, *pat_end;
1492 REGISTER Bufbyte *cursor, *p_limit, *ptr2;
1493 Bufbyte simple_translate[0400];
1494 REGISTER int direction = ((n > 0) ? 1 : -1);
1496 Bufbyte translate_prev_byte = 0;
1497 Bufbyte translate_anteprev_byte = 0;
1500 EMACS_INT BM_tab_space[0400];
1501 BM_tab = &BM_tab_space[0];
1503 BM_tab = alloca_array (EMACS_INT, 256);
1506 /* The general approach is that we are going to maintain that we
1507 know the first (closest to the present position, in whatever
1508 direction we're searching) character that could possibly be
1509 the last (furthest from present position) character of a
1510 valid match. We advance the state of our knowledge by
1511 looking at that character and seeing whether it indeed
1512 matches the last character of the pattern. If it does, we
1513 take a closer look. If it does not, we move our pointer (to
1514 putative last characters) as far as is logically possible.
1515 This amount of movement, which I call a stride, will be the
1516 length of the pattern if the actual character appears nowhere
1517 in the pattern, otherwise it will be the distance from the
1518 last occurrence of that character to the end of the pattern.
1519 As a coding trick, an enormous stride is coded into the table
1520 for characters that match the last character. This allows
1521 use of only a single test, a test for having gone past the
1522 end of the permissible match region, to test for both
1523 possible matches (when the stride goes past the end
1524 immediately) and failure to match (where you get nudged past
1525 the end one stride at a time).
1527 Here we make a "mickey mouse" BM table. The stride of the
1528 search is determined only by the last character of the
1529 putative match. If that character does not match, we will
1530 stride the proper distance to propose a match that
1531 superimposes it on the last instance of a character that
1532 matches it (per trt), or misses it entirely if there is
1535 dirlen = len * direction;
1536 infinity = dirlen - (lim + pos + len + len) * direction;
1537 /* Record position after the end of the pattern. */
1538 pat_end = base_pat + len;
1540 base_pat = pat_end - 1;
1541 BM_tab_base = BM_tab;
1543 j = dirlen; /* to get it in a register */
1544 /* A character that does not appear in the pattern induces a
1545 stride equal to the pattern length. */
1546 while (BM_tab_base != BM_tab)
1553 /* We use this for translation, instead of TRT itself. We
1554 fill this in to handle the characters that actually occur
1555 in the pattern. Others don't matter anyway! */
1556 xzero (simple_translate);
1557 for (i = 0; i < 0400; i++)
1558 simple_translate[i] = i;
1560 while (i != infinity)
1562 Bufbyte *ptr = base_pat + i;
1569 Emchar ch, untranslated;
1570 int this_translated = 1;
1572 /* Is *PTR the last byte of a character? */
1573 if (pat_end - ptr == 1 || BUFBYTE_FIRST_BYTE_P (ptr[1]))
1575 Bufbyte *charstart = ptr;
1576 while (!BUFBYTE_FIRST_BYTE_P (*charstart))
1578 untranslated = charptr_emchar (charstart);
1579 if (charset_base == (untranslated & ~CHAR_FIELD3_MASK))
1581 ch = TRANSLATE (trt, untranslated);
1582 if (!BUFBYTE_FIRST_BYTE_P (*ptr))
1584 translate_prev_byte = ptr[-1];
1585 if (!BUFBYTE_FIRST_BYTE_P (translate_prev_byte))
1586 translate_anteprev_byte = ptr[-2];
1591 this_translated = 0;
1598 this_translated = 0;
1601 j = ((unsigned char) ch | 0200);
1603 j = (unsigned char) ch;
1606 stride_for_teases = BM_tab[j];
1607 BM_tab[j] = dirlen - i;
1608 /* A translation table is accompanied by its inverse --
1609 see comment following downcase_table for details */
1610 if (this_translated)
1612 Emchar starting_ch = ch;
1613 EMACS_INT starting_j = j;
1616 ch = TRANSLATE (inverse_trt, ch);
1618 j = ((unsigned char) ch | 0200);
1620 j = (unsigned char) ch;
1622 /* For all the characters that map into CH,
1623 set up simple_translate to map the last byte
1625 simple_translate[j] = starting_j;
1626 if (ch == starting_ch)
1628 BM_tab[j] = dirlen - i;
1634 k = (j = TRANSLATE (trt, j));
1636 stride_for_teases = BM_tab[j];
1637 BM_tab[j] = dirlen - i;
1638 /* A translation table is accompanied by its inverse --
1639 see comment following downcase_table for details */
1641 while ((j = TRANSLATE (inverse_trt, j)) != k)
1643 simple_translate[j] = k;
1644 BM_tab[j] = dirlen - i;
1653 stride_for_teases = BM_tab[j];
1654 BM_tab[j] = dirlen - i;
1656 /* stride_for_teases tells how much to stride if we get a
1657 match on the far character but are subsequently
1658 disappointed, by recording what the stride would have been
1659 for that character if the last character had been
1662 infinity = dirlen - infinity;
1663 pos += dirlen - ((direction > 0) ? direction : 0);
1664 /* loop invariant - pos points at where last char (first char if
1665 reverse) of pattern would align in a possible match. */
1669 Bufbyte *tail_end_ptr;
1670 /* It's been reported that some (broken) compiler thinks
1671 that Boolean expressions in an arithmetic context are
1672 unsigned. Using an explicit ?1:0 prevents this. */
1673 if ((lim - pos - ((direction > 0) ? 1 : 0)) * direction < 0)
1674 return n * (0 - direction);
1675 /* First we do the part we can by pointers (maybe
1679 limit = pos - dirlen + direction;
1680 /* XEmacs change: definitions of CEILING_OF and FLOOR_OF
1681 have changed. See buffer.h. */
1682 limit = ((direction > 0)
1683 ? BI_BUF_CEILING_OF (buf, limit) - 1
1684 : BI_BUF_FLOOR_OF (buf, limit + 1));
1685 /* LIMIT is now the last (not beyond-last!) value POS can
1686 take on without hitting edge of buffer or the gap. */
1687 limit = ((direction > 0)
1688 ? min (lim - 1, min (limit, pos + 20000))
1689 : max (lim, max (limit, pos - 20000)));
1690 tail_end = BI_BUF_CEILING_OF (buf, pos);
1691 tail_end_ptr = BI_BUF_BYTE_ADDRESS (buf, tail_end);
1693 if ((limit - pos) * direction > 20)
1695 p_limit = BI_BUF_BYTE_ADDRESS (buf, limit);
1696 ptr2 = (cursor = BI_BUF_BYTE_ADDRESS (buf, pos));
1697 /* In this loop, pos + cursor - ptr2 is the surrogate
1699 while (1) /* use one cursor setting as long as i can */
1701 if (direction > 0) /* worth duplicating */
1703 /* Use signed comparison if appropriate to make
1704 cursor+infinity sure to be > p_limit.
1705 Assuming that the buffer lies in a range of
1706 addresses that are all "positive" (as ints)
1707 or all "negative", either kind of comparison
1708 will work as long as we don't step by
1709 infinity. So pick the kind that works when
1710 we do step by infinity. */
1711 if ((EMACS_INT) (p_limit + infinity) >
1712 (EMACS_INT) p_limit)
1713 while ((EMACS_INT) cursor <=
1714 (EMACS_INT) p_limit)
1715 cursor += BM_tab[*cursor];
1717 while ((EMACS_UINT) cursor <=
1718 (EMACS_UINT) p_limit)
1719 cursor += BM_tab[*cursor];
1723 if ((EMACS_INT) (p_limit + infinity) <
1724 (EMACS_INT) p_limit)
1725 while ((EMACS_INT) cursor >=
1726 (EMACS_INT) p_limit)
1727 cursor += BM_tab[*cursor];
1729 while ((EMACS_UINT) cursor >=
1730 (EMACS_UINT) p_limit)
1731 cursor += BM_tab[*cursor];
1733 /* If you are here, cursor is beyond the end of the
1734 searched region. This can happen if you match on
1735 the far character of the pattern, because the
1736 "stride" of that character is infinity, a number
1737 able to throw you well beyond the end of the
1738 search. It can also happen if you fail to match
1739 within the permitted region and would otherwise
1740 try a character beyond that region */
1741 if ((cursor - p_limit) * direction <= len)
1742 break; /* a small overrun is genuine */
1743 cursor -= infinity; /* large overrun = hit */
1744 i = dirlen - direction;
1747 while ((i -= direction) + direction != 0)
1751 cursor -= direction;
1752 /* Translate only the last byte of a character. */
1753 if ((cursor == tail_end_ptr
1754 || BUFBYTE_FIRST_BYTE_P (cursor[1]))
1755 && (BUFBYTE_FIRST_BYTE_P (cursor[0])
1756 || (translate_prev_byte == cursor[-1]
1757 && (BUFBYTE_FIRST_BYTE_P (translate_prev_byte)
1758 || translate_anteprev_byte == cursor[-2]))))
1759 ch = simple_translate[*cursor];
1765 if (pat[i] != TRANSLATE (trt, *(cursor -= direction)))
1772 while ((i -= direction) + direction != 0)
1773 if (pat[i] != *(cursor -= direction))
1776 cursor += dirlen - i - direction; /* fix cursor */
1777 if (i + direction == 0)
1779 cursor -= direction;
1782 Bytind bytstart = (pos + cursor - ptr2 +
1785 Bufpos bufstart = bytind_to_bufpos (buf, bytstart);
1786 Bufpos bufend = bytind_to_bufpos (buf, bytstart + len);
1788 set_search_regs (buf, bufstart, bufend - bufstart);
1791 if ((n -= direction) != 0)
1792 cursor += dirlen; /* to resume search */
1794 return ((direction > 0)
1795 ? search_regs.end[0] : search_regs.start[0]);
1798 cursor += stride_for_teases; /* <sigh> we lose - */
1800 pos += cursor - ptr2;
1803 /* Now we'll pick up a clump that has to be done the hard
1804 way because it covers a discontinuity */
1806 /* XEmacs change: definitions of CEILING_OF and FLOOR_OF
1807 have changed. See buffer.h. */
1808 limit = ((direction > 0)
1809 ? BI_BUF_CEILING_OF (buf, pos - dirlen + 1) - 1
1810 : BI_BUF_FLOOR_OF (buf, pos - dirlen));
1811 limit = ((direction > 0)
1812 ? min (limit + len, lim - 1)
1813 : max (limit - len, lim));
1814 /* LIMIT is now the last value POS can have
1815 and still be valid for a possible match. */
1818 /* This loop can be coded for space rather than
1819 speed because it will usually run only once.
1820 (the reach is at most len + 21, and typically
1821 does not exceed len) */
1822 while ((limit - pos) * direction >= 0)
1823 /* *not* BI_BUF_FETCH_CHAR. We are working here
1824 with bytes, not characters. */
1825 pos += BM_tab[*BI_BUF_BYTE_ADDRESS (buf, pos)];
1826 /* now run the same tests to distinguish going off
1827 the end, a match or a phony match. */
1828 if ((pos - limit) * direction <= len)
1829 break; /* ran off the end */
1830 /* Found what might be a match.
1831 Set POS back to last (first if reverse) char pos. */
1833 i = dirlen - direction;
1834 while ((i -= direction) + direction != 0)
1842 ptr = BI_BUF_BYTE_ADDRESS (buf, pos);
1843 if ((ptr == tail_end_ptr
1844 || BUFBYTE_FIRST_BYTE_P (ptr[1]))
1845 && (BUFBYTE_FIRST_BYTE_P (ptr[0])
1846 || (translate_prev_byte == ptr[-1]
1847 && (BUFBYTE_FIRST_BYTE_P (translate_prev_byte)
1848 || translate_anteprev_byte == ptr[-2]))))
1849 ch = simple_translate[*ptr];
1856 if (pat[i] != TRANSLATE (trt,
1857 *BI_BUF_BYTE_ADDRESS (buf, pos)))
1861 /* Above loop has moved POS part or all the way back
1862 to the first char pos (last char pos if reverse).
1863 Set it once again at the last (first if reverse)
1865 pos += dirlen - i- direction;
1866 if (i + direction == 0)
1871 Bytind bytstart = (pos +
1874 Bufpos bufstart = bytind_to_bufpos (buf, bytstart);
1875 Bufpos bufend = bytind_to_bufpos (buf, bytstart + len);
1877 set_search_regs (buf, bufstart, bufend - bufstart);
1880 if ((n -= direction) != 0)
1881 pos += dirlen; /* to resume search */
1883 return ((direction > 0)
1884 ? search_regs.end[0] : search_regs.start[0]);
1887 pos += stride_for_teases;
1890 /* We have done one clump. Can we continue? */
1891 if ((lim - pos) * direction < 0)
1892 return (0 - n) * direction;
1894 return bytind_to_bufpos (buf, pos);
1897 /* Record beginning BEG and end BEG + LEN
1898 for a match just found in the current buffer. */
1901 set_search_regs (struct buffer *buf, Bufpos beg, Charcount len)
1903 /* This function has been Mule-ized. */
1904 /* Make sure we have registers in which to store
1905 the match position. */
1906 if (search_regs.num_regs == 0)
1908 search_regs.start = xnew (regoff_t);
1909 search_regs.end = xnew (regoff_t);
1910 search_regs.num_regs = 1;
1913 search_regs.start[0] = beg;
1914 search_regs.end[0] = beg + len;
1915 XSETBUFFER (last_thing_searched, buf);
1919 /* Given a string of words separated by word delimiters,
1920 compute a regexp that matches those exact words
1921 separated by arbitrary punctuation. */
1924 wordify (Lisp_Object buffer, Lisp_Object string)
1927 EMACS_INT punct_count = 0, word_count = 0;
1928 struct buffer *buf = decode_buffer (buffer, 0);
1929 Lisp_Char_Table *syntax_table = XCHAR_TABLE (buf->mirror_syntax_table);
1931 CHECK_STRING (string);
1932 len = XSTRING_CHAR_LENGTH (string);
1934 for (i = 0; i < len; i++)
1935 if (!WORD_SYNTAX_P (syntax_table, string_char (XSTRING (string), i)))
1938 if (i > 0 && WORD_SYNTAX_P (syntax_table,
1939 string_char (XSTRING (string), i - 1)))
1942 if (WORD_SYNTAX_P (syntax_table, string_char (XSTRING (string), len - 1)))
1944 if (!word_count) return build_string ("");
1947 /* The following value is an upper bound on the amount of storage we
1948 need. In non-Mule, it is exact. */
1950 (Bufbyte *) alloca (XSTRING_LENGTH (string) - punct_count +
1951 5 * (word_count - 1) + 4);
1952 Bufbyte *o = storage;
1957 for (i = 0; i < len; i++)
1959 Emchar ch = string_char (XSTRING (string), i);
1961 if (WORD_SYNTAX_P (syntax_table, ch))
1962 o += set_charptr_emchar (o, ch);
1964 && WORD_SYNTAX_P (syntax_table,
1965 string_char (XSTRING (string), i - 1))
1979 return make_string (storage, o - storage);
1983 DEFUN ("search-backward", Fsearch_backward, 1, 5, "sSearch backward: ", /*
1984 Search backward from point for STRING.
1985 Set point to the beginning of the occurrence found, and return point.
1987 Optional second argument LIMIT bounds the search; it is a buffer
1988 position. The match found must not extend before that position.
1989 The value nil is equivalent to (point-min).
1991 Optional third argument NOERROR, if t, means just return nil (no
1992 error) if the search fails. If neither nil nor t, set point to LIMIT
1995 Optional fourth argument COUNT is a repeat count--search for
1996 successive occurrences.
1998 Optional fifth argument BUFFER specifies the buffer to search in and
1999 defaults to the current buffer.
2001 See also the functions `match-beginning', `match-end' and `replace-match'.
2003 (string, limit, noerror, count, buffer))
2005 return search_command (string, limit, noerror, count, buffer, -1, 0, 0);
2008 DEFUN ("search-forward", Fsearch_forward, 1, 5, "sSearch: ", /*
2009 Search forward from point for STRING.
2010 Set point to the end of the occurrence found, and return point.
2012 Optional second argument LIMIT bounds the search; it is a buffer
2013 position. The match found must not extend after that position. The
2014 value nil is equivalent to (point-max).
2016 Optional third argument NOERROR, if t, means just return nil (no
2017 error) if the search fails. If neither nil nor t, set point to LIMIT
2020 Optional fourth argument COUNT is a repeat count--search for
2021 successive occurrences.
2023 Optional fifth argument BUFFER specifies the buffer to search in and
2024 defaults to the current buffer.
2026 See also the functions `match-beginning', `match-end' and `replace-match'.
2028 (string, limit, noerror, count, buffer))
2030 return search_command (string, limit, noerror, count, buffer, 1, 0, 0);
2033 DEFUN ("word-search-backward", Fword_search_backward, 1, 5,
2034 "sWord search backward: ", /*
2035 Search backward from point for STRING, ignoring differences in punctuation.
2036 Set point to the beginning of the occurrence found, and return point.
2038 Optional second argument LIMIT bounds the search; it is a buffer
2039 position. The match found must not extend before that position.
2040 The value nil is equivalent to (point-min).
2042 Optional third argument NOERROR, if t, means just return nil (no
2043 error) if the search fails. If neither nil nor t, set point to LIMIT
2046 Optional fourth argument COUNT is a repeat count--search for
2047 successive occurrences.
2049 Optional fifth argument BUFFER specifies the buffer to search in and
2050 defaults to the current buffer.
2052 See also the functions `match-beginning', `match-end' and `replace-match'.
2054 (string, limit, noerror, count, buffer))
2056 return search_command (wordify (buffer, string), limit, noerror, count,
2060 DEFUN ("word-search-forward", Fword_search_forward, 1, 5, "sWord search: ", /*
2061 Search forward from point for STRING, ignoring differences in punctuation.
2062 Set point to the end of the occurrence found, and return point.
2064 Optional second argument LIMIT bounds the search; it is a buffer
2065 position. The match found must not extend after that position. The
2066 value nil is equivalent to (point-max).
2068 Optional third argument NOERROR, if t, means just return nil (no
2069 error) if the search fails. If neither nil nor t, set point to LIMIT
2072 Optional fourth argument COUNT is a repeat count--search for
2073 successive occurrences.
2075 Optional fifth argument BUFFER specifies the buffer to search in and
2076 defaults to the current buffer.
2078 See also the functions `match-beginning', `match-end' and `replace-match'.
2080 (string, limit, noerror, count, buffer))
2082 return search_command (wordify (buffer, string), limit, noerror, count,
2086 DEFUN ("re-search-backward", Fre_search_backward, 1, 5,
2087 "sRE search backward: ", /*
2088 Search backward from point for match for regular expression REGEXP.
2089 Set point to the beginning of the match, and return point.
2090 The match found is the one starting last in the buffer
2091 and yet ending before the origin of the search.
2093 Optional second argument LIMIT bounds the search; it is a buffer
2094 position. The match found must not extend before that position.
2095 The value nil is equivalent to (point-min).
2097 Optional third argument NOERROR, if t, means just return nil (no
2098 error) if the search fails. If neither nil nor t, set point to LIMIT
2101 Optional fourth argument COUNT is a repeat count--search for
2102 successive occurrences.
2104 Optional fifth argument BUFFER specifies the buffer to search in and
2105 defaults to the current buffer.
2107 See also the functions `match-beginning', `match-end' and `replace-match'.
2109 (regexp, limit, noerror, count, buffer))
2111 return search_command (regexp, limit, noerror, count, buffer, -1, 1, 0);
2114 DEFUN ("re-search-forward", Fre_search_forward, 1, 5, "sRE search: ", /*
2115 Search forward from point for regular expression REGEXP.
2116 Set point to the end of the occurrence found, and return point.
2118 Optional second argument LIMIT bounds the search; it is a buffer
2119 position. The match found must not extend after that position. The
2120 value nil is equivalent to (point-max).
2122 Optional third argument NOERROR, if t, means just return nil (no
2123 error) if the search fails. If neither nil nor t, set point to LIMIT
2126 Optional fourth argument COUNT is a repeat count--search for
2127 successive occurrences.
2129 Optional fifth argument BUFFER specifies the buffer to search in and
2130 defaults to the current buffer.
2132 See also the functions `match-beginning', `match-end' and `replace-match'.
2134 (regexp, limit, noerror, count, buffer))
2136 return search_command (regexp, limit, noerror, count, buffer, 1, 1, 0);
2139 DEFUN ("posix-search-backward", Fposix_search_backward, 1, 5,
2140 "sPosix search backward: ", /*
2141 Search backward from point for match for regular expression REGEXP.
2142 Find the longest match in accord with Posix regular expression rules.
2143 Set point to the beginning of the match, and return point.
2144 The match found is the one starting last in the buffer
2145 and yet ending before the origin of the search.
2147 Optional second argument LIMIT bounds the search; it is a buffer
2148 position. The match found must not extend before that position.
2149 The value nil is equivalent to (point-min).
2151 Optional third argument NOERROR, if t, means just return nil (no
2152 error) if the search fails. If neither nil nor t, set point to LIMIT
2155 Optional fourth argument COUNT is a repeat count--search for
2156 successive occurrences.
2158 Optional fifth argument BUFFER specifies the buffer to search in and
2159 defaults to the current buffer.
2161 See also the functions `match-beginning', `match-end' and `replace-match'.
2163 (regexp, limit, noerror, count, buffer))
2165 return search_command (regexp, limit, noerror, count, buffer, -1, 1, 1);
2168 DEFUN ("posix-search-forward", Fposix_search_forward, 1, 5, "sPosix search: ", /*
2169 Search forward from point for regular expression REGEXP.
2170 Find the longest match in accord with Posix regular expression rules.
2171 Set point to the end of the occurrence found, and return point.
2173 Optional second argument LIMIT bounds the search; it is a buffer
2174 position. The match found must not extend after that position. The
2175 value nil is equivalent to (point-max).
2177 Optional third argument NOERROR, if t, means just return nil (no
2178 error) if the search fails. If neither nil nor t, set point to LIMIT
2181 Optional fourth argument COUNT is a repeat count--search for
2182 successive occurrences.
2184 Optional fifth argument BUFFER specifies the buffer to search in and
2185 defaults to the current buffer.
2187 See also the functions `match-beginning', `match-end' and `replace-match'.
2189 (regexp, limit, noerror, count, buffer))
2191 return search_command (regexp, limit, noerror, count, buffer, 1, 1, 1);
2196 free_created_dynarrs (Lisp_Object cons)
2198 Dynarr_free (get_opaque_ptr (XCAR (cons)));
2199 Dynarr_free (get_opaque_ptr (XCDR (cons)));
2200 free_opaque_ptr (XCAR (cons));
2201 free_opaque_ptr (XCDR (cons));
2202 free_cons (XCONS (cons));
2206 DEFUN ("replace-match", Freplace_match, 1, 5, 0, /*
2207 Replace text matched by last search with REPLACEMENT.
2208 If second arg FIXEDCASE is non-nil, do not alter case of replacement text.
2209 Otherwise maybe capitalize the whole text, or maybe just word initials,
2210 based on the replaced text.
2211 If the replaced text has only capital letters
2212 and has at least one multiletter word, convert REPLACEMENT to all caps.
2213 If the replaced text has at least one word starting with a capital letter,
2214 then capitalize each word in REPLACEMENT.
2216 If third arg LITERAL is non-nil, insert REPLACEMENT literally.
2217 Otherwise treat `\\' as special:
2218 `\\&' in REPLACEMENT means substitute original matched text.
2219 `\\N' means substitute what matched the Nth `\\(...\\)'.
2220 If Nth parens didn't match, substitute nothing.
2221 `\\\\' means insert one `\\'.
2222 `\\u' means upcase the next character.
2223 `\\l' means downcase the next character.
2224 `\\U' means begin upcasing all following characters.
2225 `\\L' means begin downcasing all following characters.
2226 `\\E' means terminate the effect of any `\\U' or `\\L'.
2227 Case changes made with `\\u', `\\l', `\\U', and `\\L' override
2228 all other case changes that may be made in the replaced text.
2229 FIXEDCASE and LITERAL are optional arguments.
2230 Leaves point at end of replacement text.
2232 The optional fourth argument STRING can be a string to modify.
2233 In that case, this function creates and returns a new string
2234 which is made by replacing the part of STRING that was matched.
2235 When fourth argument is a string, fifth argument STRBUFFER specifies
2236 the buffer to be used for syntax-table and case-table lookup and
2237 defaults to the current buffer. When fourth argument is not a string,
2238 the buffer that the match occurred in has automatically been remembered
2239 and you do not need to specify it.
2241 (replacement, fixedcase, literal, string, strbuffer))
2243 /* This function has been Mule-ized. */
2244 /* This function can GC */
2245 enum { nochange, all_caps, cap_initial } case_action;
2247 int some_multiletter_word;
2250 int some_nonuppercase_initial;
2254 Lisp_Char_Table *syntax_table;
2257 int_dynarr *ul_action_dynarr = 0;
2258 int_dynarr *ul_pos_dynarr = 0;
2261 CHECK_STRING (replacement);
2263 if (! NILP (string))
2265 CHECK_STRING (string);
2266 if (!EQ (last_thing_searched, Qt))
2267 error ("last thing matched was not a string");
2268 /* If the match data
2269 were abstracted into a special "match data" type instead
2270 of the typical half-assed "let the implementation be
2271 visible" form it's in, we could extend it to include
2272 the last string matched and the buffer used for that
2273 matching. But of course we can't change it as it is. */
2274 buf = decode_buffer (strbuffer, 0);
2275 XSETBUFFER (buffer, buf);
2279 if (!BUFFERP (last_thing_searched))
2280 error ("last thing matched was not a buffer");
2281 buffer = last_thing_searched;
2282 buf = XBUFFER (buffer);
2285 syntax_table = XCHAR_TABLE (buf->mirror_syntax_table);
2287 case_action = nochange; /* We tried an initialization */
2288 /* but some C compilers blew it */
2290 if (search_regs.num_regs == 0)
2291 error ("replace-match called before any match found");
2295 if (search_regs.start[0] < BUF_BEGV (buf)
2296 || search_regs.start[0] > search_regs.end[0]
2297 || search_regs.end[0] > BUF_ZV (buf))
2298 args_out_of_range (make_int (search_regs.start[0]),
2299 make_int (search_regs.end[0]));
2303 if (search_regs.start[0] < 0
2304 || search_regs.start[0] > search_regs.end[0]
2305 || search_regs.end[0] > XSTRING_CHAR_LENGTH (string))
2306 args_out_of_range (make_int (search_regs.start[0]),
2307 make_int (search_regs.end[0]));
2310 if (NILP (fixedcase))
2312 /* Decide how to casify by examining the matched text. */
2314 last = search_regs.end[0];
2316 case_action = all_caps;
2318 /* some_multiletter_word is set nonzero if any original word
2319 is more than one letter long. */
2320 some_multiletter_word = 0;
2322 some_nonuppercase_initial = 0;
2325 for (pos = search_regs.start[0]; pos < last; pos++)
2328 c = BUF_FETCH_CHAR (buf, pos);
2330 c = string_char (XSTRING (string), pos);
2332 if (LOWERCASEP (buf, c))
2334 /* Cannot be all caps if any original char is lower case */
2337 if (!WORD_SYNTAX_P (syntax_table, prevc))
2338 some_nonuppercase_initial = 1;
2340 some_multiletter_word = 1;
2342 else if (!NOCASEP (buf, c))
2345 if (!WORD_SYNTAX_P (syntax_table, prevc))
2348 some_multiletter_word = 1;
2352 /* If the initial is a caseless word constituent,
2353 treat that like a lowercase initial. */
2354 if (!WORD_SYNTAX_P (syntax_table, prevc))
2355 some_nonuppercase_initial = 1;
2361 /* Convert to all caps if the old text is all caps
2362 and has at least one multiletter word. */
2363 if (! some_lowercase && some_multiletter_word)
2364 case_action = all_caps;
2365 /* Capitalize each word, if the old text has all capitalized words. */
2366 else if (!some_nonuppercase_initial && some_multiletter_word)
2367 case_action = cap_initial;
2368 else if (!some_nonuppercase_initial && some_uppercase)
2369 /* Should x -> yz, operating on X, give Yz or YZ?
2370 We'll assume the latter. */
2371 case_action = all_caps;
2373 case_action = nochange;
2376 /* Do replacement in a string. */
2379 Lisp_Object before, after;
2381 speccount = specpdl_depth ();
2382 before = Fsubstring (string, Qzero, make_int (search_regs.start[0]));
2383 after = Fsubstring (string, make_int (search_regs.end[0]), Qnil);
2385 /* Do case substitution into REPLACEMENT if desired. */
2388 Charcount stlen = XSTRING_CHAR_LENGTH (replacement);
2390 /* XEmacs change: rewrote this loop somewhat to make it
2391 cleaner. Also added \U, \E, etc. */
2392 Charcount literal_start = 0;
2393 /* We build up the substituted string in ACCUM. */
2398 /* OK, the basic idea here is that we scan through the
2399 replacement string until we find a backslash, which
2400 represents a substring of the original string to be
2401 substituted. We then append onto ACCUM the literal
2402 text before the backslash (LASTPOS marks the
2403 beginning of this) followed by the substring of the
2404 original string that needs to be inserted. */
2405 for (strpos = 0; strpos < stlen; strpos++)
2407 /* If LITERAL_END is set, we've encountered a backslash
2408 (the end of literal text to be inserted). */
2409 Charcount literal_end = -1;
2410 /* If SUBSTART is set, we need to also insert the
2411 text from SUBSTART to SUBEND in the original string. */
2412 Charcount substart = -1;
2413 Charcount subend = -1;
2415 c = string_char (XSTRING (replacement), strpos);
2416 if (c == '\\' && strpos < stlen - 1)
2418 c = string_char (XSTRING (replacement), ++strpos);
2421 literal_end = strpos - 1;
2422 substart = search_regs.start[0];
2423 subend = search_regs.end[0];
2425 else if (c >= '1' && c <= '9' &&
2426 c <= search_regs.num_regs + '0')
2428 if (search_regs.start[c - '0'] >= 0)
2430 literal_end = strpos - 1;
2431 substart = search_regs.start[c - '0'];
2432 subend = search_regs.end[c - '0'];
2435 else if (c == 'U' || c == 'u' || c == 'L' || c == 'l' ||
2438 /* Keep track of all case changes requested, but don't
2439 make them now. Do them later so we override
2443 ul_pos_dynarr = Dynarr_new (int);
2444 ul_action_dynarr = Dynarr_new (int);
2445 record_unwind_protect
2446 (free_created_dynarrs,
2448 (make_opaque_ptr (ul_pos_dynarr),
2449 make_opaque_ptr (ul_action_dynarr)));
2451 literal_end = strpos - 1;
2452 Dynarr_add (ul_pos_dynarr,
2454 ? XSTRING_CHAR_LENGTH (accum)
2455 : 0) + (literal_end - literal_start));
2456 Dynarr_add (ul_action_dynarr, c);
2459 /* So we get just one backslash. */
2460 literal_end = strpos;
2462 if (literal_end >= 0)
2464 Lisp_Object literal_text = Qnil;
2465 Lisp_Object substring = Qnil;
2466 if (literal_end != literal_start)
2467 literal_text = Fsubstring (replacement,
2468 make_int (literal_start),
2469 make_int (literal_end));
2470 if (substart >= 0 && subend != substart)
2471 substring = Fsubstring (string,
2472 make_int (substart),
2474 if (!NILP (literal_text) || !NILP (substring))
2475 accum = concat3 (accum, literal_text, substring);
2476 literal_start = strpos + 1;
2480 if (strpos != literal_start)
2481 /* some literal text at end to be inserted */
2482 replacement = concat2 (accum, Fsubstring (replacement,
2483 make_int (literal_start),
2484 make_int (strpos)));
2486 replacement = accum;
2489 /* replacement can be nil. */
2490 if (NILP (replacement))
2491 replacement = build_string ("");
2493 if (case_action == all_caps)
2494 replacement = Fupcase (replacement, buffer);
2495 else if (case_action == cap_initial)
2496 replacement = Fupcase_initials (replacement, buffer);
2498 /* Now finally, we need to process the \U's, \E's, etc. */
2502 int cur_action = 'E';
2503 Charcount stlen = XSTRING_CHAR_LENGTH (replacement);
2506 for (strpos = 0; strpos < stlen; strpos++)
2508 Emchar curchar = string_char (XSTRING (replacement), strpos);
2509 Emchar newchar = -1;
2510 if (i < Dynarr_length (ul_pos_dynarr) &&
2511 strpos == Dynarr_at (ul_pos_dynarr, i))
2513 int new_action = Dynarr_at (ul_action_dynarr, i);
2515 if (new_action == 'u')
2516 newchar = UPCASE (buf, curchar);
2517 else if (new_action == 'l')
2518 newchar = DOWNCASE (buf, curchar);
2520 cur_action = new_action;
2524 if (cur_action == 'U')
2525 newchar = UPCASE (buf, curchar);
2526 else if (cur_action == 'L')
2527 newchar = DOWNCASE (buf, curchar);
2531 if (newchar != curchar)
2532 set_string_char (XSTRING (replacement), strpos, newchar);
2536 /* frees the Dynarrs if necessary. */
2537 unbind_to (speccount, Qnil);
2538 return concat3 (before, replacement, after);
2541 mc_count = begin_multiple_change (buf, search_regs.start[0],
2542 search_regs.end[0]);
2544 /* begin_multiple_change() records an unwind-protect, so we need to
2545 record this value now. */
2546 speccount = specpdl_depth ();
2548 /* We insert the replacement text before the old text, and then
2549 delete the original text. This means that markers at the
2550 beginning or end of the original will float to the corresponding
2551 position in the replacement. */
2552 BUF_SET_PT (buf, search_regs.start[0]);
2553 if (!NILP (literal))
2554 Finsert (1, &replacement);
2557 Charcount stlen = XSTRING_CHAR_LENGTH (replacement);
2559 struct gcpro gcpro1;
2560 GCPRO1 (replacement);
2561 for (strpos = 0; strpos < stlen; strpos++)
2563 Charcount offset = BUF_PT (buf) - search_regs.start[0];
2565 c = string_char (XSTRING (replacement), strpos);
2566 if (c == '\\' && strpos < stlen - 1)
2568 c = string_char (XSTRING (replacement), ++strpos);
2570 Finsert_buffer_substring
2572 make_int (search_regs.start[0] + offset),
2573 make_int (search_regs.end[0] + offset));
2574 else if (c >= '1' && c <= '9' &&
2575 c <= search_regs.num_regs + '0')
2577 if (search_regs.start[c - '0'] >= 1)
2578 Finsert_buffer_substring
2580 make_int (search_regs.start[c - '0'] + offset),
2581 make_int (search_regs.end[c - '0'] + offset));
2583 else if (c == 'U' || c == 'u' || c == 'L' || c == 'l' ||
2586 /* Keep track of all case changes requested, but don't
2587 make them now. Do them later so we override
2591 ul_pos_dynarr = Dynarr_new (int);
2592 ul_action_dynarr = Dynarr_new (int);
2593 record_unwind_protect
2594 (free_created_dynarrs,
2595 Fcons (make_opaque_ptr (ul_pos_dynarr),
2596 make_opaque_ptr (ul_action_dynarr)));
2598 Dynarr_add (ul_pos_dynarr, BUF_PT (buf));
2599 Dynarr_add (ul_action_dynarr, c);
2602 buffer_insert_emacs_char (buf, c);
2605 buffer_insert_emacs_char (buf, c);
2610 inslen = BUF_PT (buf) - (search_regs.start[0]);
2611 buffer_delete_range (buf, search_regs.start[0] + inslen, search_regs.end[0] +
2614 if (case_action == all_caps)
2615 Fupcase_region (make_int (BUF_PT (buf) - inslen),
2616 make_int (BUF_PT (buf)), buffer);
2617 else if (case_action == cap_initial)
2618 Fupcase_initials_region (make_int (BUF_PT (buf) - inslen),
2619 make_int (BUF_PT (buf)), buffer);
2621 /* Now go through and make all the case changes that were requested
2622 in the replacement string. */
2625 Bufpos eend = BUF_PT (buf);
2627 int cur_action = 'E';
2629 for (pos = BUF_PT (buf) - inslen; pos < eend; pos++)
2631 Emchar curchar = BUF_FETCH_CHAR (buf, pos);
2632 Emchar newchar = -1;
2633 if (i < Dynarr_length (ul_pos_dynarr) &&
2634 pos == Dynarr_at (ul_pos_dynarr, i))
2636 int new_action = Dynarr_at (ul_action_dynarr, i);
2638 if (new_action == 'u')
2639 newchar = UPCASE (buf, curchar);
2640 else if (new_action == 'l')
2641 newchar = DOWNCASE (buf, curchar);
2643 cur_action = new_action;
2647 if (cur_action == 'U')
2648 newchar = UPCASE (buf, curchar);
2649 else if (cur_action == 'L')
2650 newchar = DOWNCASE (buf, curchar);
2654 if (newchar != curchar)
2655 buffer_replace_char (buf, pos, newchar, 0, 0);
2659 /* frees the Dynarrs if necessary. */
2660 unbind_to (speccount, Qnil);
2661 end_multiple_change (buf, mc_count);
2667 match_limit (Lisp_Object num, int beginningp)
2669 /* This function has been Mule-ized. */
2674 if (n < 0 || n >= search_regs.num_regs)
2675 args_out_of_range (num, make_int (search_regs.num_regs));
2676 if (search_regs.num_regs == 0 ||
2677 search_regs.start[n] < 0)
2679 return make_int (beginningp ? search_regs.start[n] : search_regs.end[n]);
2682 DEFUN ("match-beginning", Fmatch_beginning, 1, 1, 0, /*
2683 Return position of start of text matched by last regexp search.
2684 NUM, specifies which parenthesized expression in the last regexp.
2685 Value is nil if NUMth pair didn't match, or there were less than NUM pairs.
2686 Zero means the entire text matched by the whole regexp or whole string.
2690 return match_limit (num, 1);
2693 DEFUN ("match-end", Fmatch_end, 1, 1, 0, /*
2694 Return position of end of text matched by last regexp search.
2695 NUM specifies which parenthesized expression in the last regexp.
2696 Value is nil if NUMth pair didn't match, or there were less than NUM pairs.
2697 Zero means the entire text matched by the whole regexp or whole string.
2701 return match_limit (num, 0);
2704 DEFUN ("match-data", Fmatch_data, 0, 2, 0, /*
2705 Return a list containing all info on what the last regexp search matched.
2706 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2707 All the elements are markers or nil (nil if the Nth pair didn't match)
2708 if the last match was on a buffer; integers or nil if a string was matched.
2709 Use `store-match-data' to reinstate the data in this list.
2711 If INTEGERS (the optional first argument) is non-nil, always use integers
2712 \(rather than markers) to represent buffer positions.
2713 If REUSE is a list, reuse it as part of the value. If REUSE is long enough
2714 to hold all the values, and if INTEGERS is non-nil, no consing is done.
2718 /* This function has been Mule-ized. */
2719 Lisp_Object tail, prev;
2724 if (NILP (last_thing_searched))
2725 /*error ("match-data called before any match found");*/
2728 data = alloca_array (Lisp_Object, 2 * search_regs.num_regs);
2731 for (i = 0; i < search_regs.num_regs; i++)
2733 Bufpos start = search_regs.start[i];
2736 if (EQ (last_thing_searched, Qt)
2737 || !NILP (integers))
2739 data[2 * i] = make_int (start);
2740 data[2 * i + 1] = make_int (search_regs.end[i]);
2742 else if (BUFFERP (last_thing_searched))
2744 data[2 * i] = Fmake_marker ();
2745 Fset_marker (data[2 * i],
2747 last_thing_searched);
2748 data[2 * i + 1] = Fmake_marker ();
2749 Fset_marker (data[2 * i + 1],
2750 make_int (search_regs.end[i]),
2751 last_thing_searched);
2754 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2760 data[2 * i] = data [2 * i + 1] = Qnil;
2763 return Flist (2 * len + 2, data);
2765 /* If REUSE is a list, store as many value elements as will fit
2766 into the elements of REUSE. */
2767 for (prev = Qnil, i = 0, tail = reuse; CONSP (tail); i++, tail = XCDR (tail))
2769 if (i < 2 * len + 2)
2770 XCAR (tail) = data[i];
2776 /* If we couldn't fit all value elements into REUSE,
2777 cons up the rest of them and add them to the end of REUSE. */
2778 if (i < 2 * len + 2)
2779 XCDR (prev) = Flist (2 * len + 2 - i, data + i);
2785 DEFUN ("store-match-data", Fstore_match_data, 1, 1, 0, /*
2786 Set internal data on last search match from elements of LIST.
2787 LIST should have been created by calling `match-data' previously.
2791 /* This function has been Mule-ized. */
2793 REGISTER Lisp_Object marker;
2797 if (running_asynch_code)
2798 save_search_regs ();
2800 CONCHECK_LIST (list);
2802 /* Unless we find a marker with a buffer in LIST, assume that this
2803 match data came from a string. */
2804 last_thing_searched = Qt;
2806 /* Allocate registers if they don't already exist. */
2807 length = XINT (Flength (list)) / 2;
2808 num_regs = search_regs.num_regs;
2810 if (length > num_regs)
2812 if (search_regs.num_regs == 0)
2814 search_regs.start = xnew_array (regoff_t, length);
2815 search_regs.end = xnew_array (regoff_t, length);
2819 XREALLOC_ARRAY (search_regs.start, regoff_t, length);
2820 XREALLOC_ARRAY (search_regs.end, regoff_t, length);
2823 search_regs.num_regs = length;
2826 for (i = 0; i < num_regs; i++)
2828 marker = Fcar (list);
2831 search_regs.start[i] = -1;
2836 if (MARKERP (marker))
2838 if (XMARKER (marker)->buffer == 0)
2841 XSETBUFFER (last_thing_searched, XMARKER (marker)->buffer);
2844 CHECK_INT_COERCE_MARKER (marker);
2845 search_regs.start[i] = XINT (marker);
2848 marker = Fcar (list);
2849 if (MARKERP (marker) && XMARKER (marker)->buffer == 0)
2852 CHECK_INT_COERCE_MARKER (marker);
2853 search_regs.end[i] = XINT (marker);
2861 /* If non-zero the match data have been saved in saved_search_regs
2862 during the execution of a sentinel or filter. */
2863 static int search_regs_saved;
2864 static struct re_registers saved_search_regs;
2866 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
2867 if asynchronous code (filter or sentinel) is running. */
2869 save_search_regs (void)
2871 if (!search_regs_saved)
2873 saved_search_regs.num_regs = search_regs.num_regs;
2874 saved_search_regs.start = search_regs.start;
2875 saved_search_regs.end = search_regs.end;
2876 search_regs.num_regs = 0;
2877 search_regs.start = 0;
2878 search_regs.end = 0;
2880 search_regs_saved = 1;
2884 /* Called upon exit from filters and sentinels. */
2886 restore_match_data (void)
2888 if (search_regs_saved)
2890 if (search_regs.num_regs > 0)
2892 xfree (search_regs.start);
2893 xfree (search_regs.end);
2895 search_regs.num_regs = saved_search_regs.num_regs;
2896 search_regs.start = saved_search_regs.start;
2897 search_regs.end = saved_search_regs.end;
2899 search_regs_saved = 0;
2903 /* Quote a string to inactivate reg-expr chars */
2905 DEFUN ("regexp-quote", Fregexp_quote, 1, 1, 0, /*
2906 Return a regexp string which matches exactly STRING and nothing else.
2910 REGISTER Bufbyte *in, *out, *end;
2911 REGISTER Bufbyte *temp;
2913 CHECK_STRING (string);
2915 temp = (Bufbyte *) alloca (XSTRING_LENGTH (string) * 2);
2917 /* Now copy the data into the new string, inserting escapes. */
2919 in = XSTRING_DATA (string);
2920 end = in + XSTRING_LENGTH (string);
2925 Emchar c = charptr_emchar (in);
2927 if (c == '[' || c == ']'
2928 || c == '*' || c == '.' || c == '\\'
2929 || c == '?' || c == '+'
2930 || c == '^' || c == '$')
2932 out += set_charptr_emchar (out, c);
2936 return make_string (temp, out - temp);
2939 DEFUN ("set-word-regexp", Fset_word_regexp, 1, 1, 0, /*
2940 Set the regexp to be used to match a word in regular-expression searching.
2941 #### Not yet implemented. Currently does nothing.
2942 #### Do not use this yet. Its calling interface is likely to change.
2950 /************************************************************************/
2951 /* initialization */
2952 /************************************************************************/
2955 syms_of_search (void)
2958 DEFERROR_STANDARD (Qsearch_failed, Qinvalid_operation);
2959 DEFERROR_STANDARD (Qinvalid_regexp, Qsyntax_error);
2961 DEFSUBR (Flooking_at);
2962 DEFSUBR (Fposix_looking_at);
2963 DEFSUBR (Fstring_match);
2964 DEFSUBR (Fposix_string_match);
2965 DEFSUBR (Fskip_chars_forward);
2966 DEFSUBR (Fskip_chars_backward);
2967 DEFSUBR (Fskip_syntax_forward);
2968 DEFSUBR (Fskip_syntax_backward);
2969 DEFSUBR (Fsearch_forward);
2970 DEFSUBR (Fsearch_backward);
2971 DEFSUBR (Fword_search_forward);
2972 DEFSUBR (Fword_search_backward);
2973 DEFSUBR (Fre_search_forward);
2974 DEFSUBR (Fre_search_backward);
2975 DEFSUBR (Fposix_search_forward);
2976 DEFSUBR (Fposix_search_backward);
2977 DEFSUBR (Freplace_match);
2978 DEFSUBR (Fmatch_beginning);
2979 DEFSUBR (Fmatch_end);
2980 DEFSUBR (Fmatch_data);
2981 DEFSUBR (Fstore_match_data);
2982 DEFSUBR (Fregexp_quote);
2983 DEFSUBR (Fset_word_regexp);
2987 reinit_vars_of_search (void)
2991 last_thing_searched = Qnil;
2992 staticpro_nodump (&last_thing_searched);
2994 for (i = 0; i < REGEXP_CACHE_SIZE; ++i)
2996 searchbufs[i].buf.allocated = 100;
2997 searchbufs[i].buf.buffer = (unsigned char *) xmalloc (100);
2998 searchbufs[i].buf.fastmap = searchbufs[i].fastmap;
2999 searchbufs[i].regexp = Qnil;
3000 staticpro_nodump (&searchbufs[i].regexp);
3001 searchbufs[i].next = (i == REGEXP_CACHE_SIZE-1 ? 0 : &searchbufs[i+1]);
3003 searchbuf_head = &searchbufs[0];
3007 vars_of_search (void)
3009 reinit_vars_of_search ();
3011 DEFVAR_LISP ("forward-word-regexp", &Vforward_word_regexp /*
3012 *Regular expression to be used in `forward-word'.
3013 #### Not yet implemented.
3015 Vforward_word_regexp = Qnil;
3017 DEFVAR_LISP ("backward-word-regexp", &Vbackward_word_regexp /*
3018 *Regular expression to be used in `backward-word'.
3019 #### Not yet implemented.
3021 Vbackward_word_regexp = Qnil;
3025 complex_vars_of_search (void)
3027 Vskip_chars_range_table = Fmake_range_table ();
3028 staticpro (&Vskip_chars_range_table);