1 /* String search routines for GNU Emacs.
3 Copyright (C) 1985-1987, 1993-1994, 1997-1999, 2001-2017 Free Software
6 This file is part of GNU Emacs.
8 GNU Emacs is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or (at
11 your option) any later version.
13 GNU Emacs is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
25 #include "character.h"
29 #include "region-cache.h"
30 #include "blockinput.h"
31 #include "intervals.h"
33 #include <sys/types.h>
36 #define REGEXP_CACHE_SIZE 20
38 /* If the regexp is non-nil, then the buffer contains the compiled form
39 of that regexp, suitable for searching. */
42 struct regexp_cache
*next
;
43 Lisp_Object regexp
, whitespace_regexp
;
44 /* Syntax table for which the regexp applies. We need this because
45 of character classes. If this is t, then the compiled pattern is valid
46 for any syntax-table. */
47 Lisp_Object syntax_table
;
48 struct re_pattern_buffer buf
;
50 /* True means regexp was compiled to do full POSIX backtracking. */
54 /* The instances of that struct. */
55 static struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
57 /* The head of the linked list; points to the most recently used buffer. */
58 static struct regexp_cache
*searchbuf_head
;
61 /* Every call to re_match, etc., must pass &search_regs as the regs
62 argument unless you can show it is unnecessary (i.e., if re_match
63 is certainly going to be called again before region-around-match
66 Since the registers are now dynamically allocated, we need to make
67 sure not to refer to the Nth register before checking that it has
68 been allocated by checking search_regs.num_regs.
70 The regex code keeps track of whether it has allocated the search
71 buffer using bits in the re_pattern_buffer. This means that whenever
72 you compile a new pattern, it completely forgets whether it has
73 allocated any registers, and will allocate new registers the next
74 time you call a searching or matching function. Therefore, we need
75 to call re_set_registers after compiling a new pattern or after
76 setting the match registers, so that the regex functions will be
77 able to free or re-allocate it properly. */
78 static struct re_registers search_regs
;
80 /* The buffer in which the last search was performed, or
81 Qt if the last search was done in a string;
82 Qnil if no searching has been done yet. */
83 static Lisp_Object last_thing_searched
;
85 static void set_search_regs (ptrdiff_t, ptrdiff_t);
86 static void save_search_regs (void);
87 static EMACS_INT
simple_search (EMACS_INT
, unsigned char *, ptrdiff_t,
88 ptrdiff_t, Lisp_Object
, ptrdiff_t, ptrdiff_t,
89 ptrdiff_t, ptrdiff_t);
90 static EMACS_INT
boyer_moore (EMACS_INT
, unsigned char *, ptrdiff_t,
91 Lisp_Object
, Lisp_Object
, ptrdiff_t,
93 static EMACS_INT
search_buffer (Lisp_Object
, ptrdiff_t, ptrdiff_t,
94 ptrdiff_t, ptrdiff_t, EMACS_INT
, int,
95 Lisp_Object
, Lisp_Object
, bool);
98 matcher_overflow (void)
100 error ("Stack overflow in regexp matcher");
103 /* Compile a regexp and signal a Lisp error if anything goes wrong.
104 PATTERN is the pattern to compile.
105 CP is the place to put the result.
106 TRANSLATE is a translation table for ignoring case, or nil for none.
107 POSIX is true if we want full backtracking (POSIX style) for this pattern.
108 False means backtrack only enough to get a valid match.
110 The behavior also depends on Vsearch_spaces_regexp. */
113 compile_pattern_1 (struct regexp_cache
*cp
, Lisp_Object pattern
,
114 Lisp_Object translate
, bool posix
)
120 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
122 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
123 cp
->buf
.charset_unibyte
= charset_unibyte
;
124 if (STRINGP (Vsearch_spaces_regexp
))
125 cp
->whitespace_regexp
= Vsearch_spaces_regexp
;
127 cp
->whitespace_regexp
= Qnil
;
129 /* rms: I think BLOCK_INPUT is not needed here any more,
130 because regex.c defines malloc to call xmalloc.
131 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
132 So let's turn it off. */
134 old
= re_set_syntax (RE_SYNTAX_EMACS
135 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
137 if (STRINGP (Vsearch_spaces_regexp
))
138 re_set_whitespace_regexp (SSDATA (Vsearch_spaces_regexp
));
140 re_set_whitespace_regexp (NULL
);
142 val
= (char *) re_compile_pattern (SSDATA (pattern
),
143 SBYTES (pattern
), &cp
->buf
);
145 /* If the compiled pattern hard codes some of the contents of the
146 syntax-table, it can only be reused with *this* syntax table. */
147 cp
->syntax_table
= cp
->buf
.used_syntax
? BVAR (current_buffer
, syntax_table
) : Qt
;
149 re_set_whitespace_regexp (NULL
);
152 /* unblock_input (); */
154 xsignal1 (Qinvalid_regexp
, build_string (val
));
156 cp
->regexp
= Fcopy_sequence (pattern
);
159 /* Shrink each compiled regexp buffer in the cache
160 to the size actually used right now.
161 This is called from garbage collection. */
164 shrink_regexp_cache (void)
166 struct regexp_cache
*cp
;
168 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
170 cp
->buf
.allocated
= cp
->buf
.used
;
171 cp
->buf
.buffer
= xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
175 /* Clear the regexp cache w.r.t. a particular syntax table,
176 because it was changed.
177 There is no danger of memory leak here because re_compile_pattern
178 automagically manages the memory in each re_pattern_buffer struct,
179 based on its `allocated' and `buffer' values. */
181 clear_regexp_cache (void)
185 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
186 /* It's tempting to compare with the syntax-table we've actually changed,
187 but it's not sufficient because char-table inheritance means that
188 modifying one syntax-table can change others at the same time. */
189 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
190 searchbufs
[i
].regexp
= Qnil
;
193 /* Compile a regexp if necessary, but first check to see if there's one in
195 PATTERN is the pattern to compile.
196 TRANSLATE is a translation table for ignoring case, or nil for none.
197 REGP is the structure that says where to store the "register"
198 values that will result from matching this pattern.
199 If it is 0, we should compile the pattern not to record any
200 subexpression bounds.
201 POSIX is true if we want full backtracking (POSIX style) for this pattern.
202 False means backtrack only enough to get a valid match. */
204 struct re_pattern_buffer
*
205 compile_pattern (Lisp_Object pattern
, struct re_registers
*regp
,
206 Lisp_Object translate
, bool posix
, bool multibyte
)
208 struct regexp_cache
*cp
, **cpp
;
210 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
213 /* Entries are initialized to nil, and may be set to nil by
214 compile_pattern_1 if the pattern isn't valid. Don't apply
215 string accessors in those cases. However, compile_pattern_1
216 is only applied to the cache entry we pick here to reuse. So
217 nil should never appear before a non-nil entry. */
218 if (NILP (cp
->regexp
))
220 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
221 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
222 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
223 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
224 && cp
->posix
== posix
225 && (EQ (cp
->syntax_table
, Qt
)
226 || EQ (cp
->syntax_table
, BVAR (current_buffer
, syntax_table
)))
227 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
))
228 && cp
->buf
.charset_unibyte
== charset_unibyte
)
231 /* If we're at the end of the cache, compile into the nil cell
232 we found, or the last (least recently used) cell with a
237 compile_pattern_1 (cp
, pattern
, translate
, posix
);
242 /* When we get here, cp (aka *cpp) contains the compiled pattern,
243 either because we found it in the cache or because we just compiled it.
244 Move it to the front of the queue to mark it as most recently used. */
246 cp
->next
= searchbuf_head
;
249 /* Advise the searching functions about the space we have allocated
250 for register data. */
252 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
254 /* The compiled pattern can be used both for multibyte and unibyte
255 target. But, we have to tell which the pattern is used for. */
256 cp
->buf
.target_multibyte
= multibyte
;
263 looking_at_1 (Lisp_Object string
, bool posix
)
266 unsigned char *p1
, *p2
;
268 register ptrdiff_t i
;
269 struct re_pattern_buffer
*bufp
;
271 if (running_asynch_code
)
274 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
275 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
276 BVAR (current_buffer
, case_eqv_table
));
278 CHECK_STRING (string
);
279 bufp
= compile_pattern (string
,
280 (NILP (Vinhibit_changing_match_data
)
281 ? &search_regs
: NULL
),
282 (!NILP (BVAR (current_buffer
, case_fold_search
))
283 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
285 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
288 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
290 /* Get pointers and sizes of the two strings
291 that make up the visible portion of the buffer. */
294 s1
= GPT_BYTE
- BEGV_BYTE
;
296 s2
= ZV_BYTE
- GPT_BYTE
;
300 s2
= ZV_BYTE
- BEGV_BYTE
;
305 s1
= ZV_BYTE
- BEGV_BYTE
;
309 re_match_object
= Qnil
;
312 /* Prevent ralloc.c from relocating the current buffer while
314 r_alloc_inhibit_buffer_relocation (1);
316 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
318 (NILP (Vinhibit_changing_match_data
)
319 ? &search_regs
: NULL
),
320 ZV_BYTE
- BEGV_BYTE
);
323 r_alloc_inhibit_buffer_relocation (0);
329 val
= (i
>= 0 ? Qt
: Qnil
);
330 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
332 for (i
= 0; i
< search_regs
.num_regs
; i
++)
333 if (search_regs
.start
[i
] >= 0)
336 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
338 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
340 /* Set last_thing_searched only when match data is changed. */
341 XSETBUFFER (last_thing_searched
, current_buffer
);
347 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
348 doc
: /* Return t if text after point matches regular expression REGEXP.
349 This function modifies the match data that `match-beginning',
350 `match-end' and `match-data' access; save and restore the match
351 data if you want to preserve them. */)
354 return looking_at_1 (regexp
, 0);
357 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
358 doc
: /* Return t if text after point matches regular expression REGEXP.
359 Find the longest match, in accord with Posix regular expression rules.
360 This function modifies the match data that `match-beginning',
361 `match-end' and `match-data' access; save and restore the match
362 data if you want to preserve them. */)
365 return looking_at_1 (regexp
, 1);
369 string_match_1 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
,
373 struct re_pattern_buffer
*bufp
;
375 ptrdiff_t pos_byte
, i
;
377 if (running_asynch_code
)
380 CHECK_STRING (regexp
);
381 CHECK_STRING (string
);
384 pos
= 0, pos_byte
= 0;
387 ptrdiff_t len
= SCHARS (string
);
389 CHECK_NUMBER (start
);
391 if (pos
< 0 && -pos
<= len
)
393 else if (0 > pos
|| pos
> len
)
394 args_out_of_range (string
, start
);
395 pos_byte
= string_char_to_byte (string
, pos
);
398 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
399 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
400 BVAR (current_buffer
, case_eqv_table
));
402 bufp
= compile_pattern (regexp
,
403 (NILP (Vinhibit_changing_match_data
)
404 ? &search_regs
: NULL
),
405 (!NILP (BVAR (current_buffer
, case_fold_search
))
406 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
408 STRING_MULTIBYTE (string
));
410 re_match_object
= string
;
412 val
= re_search (bufp
, SSDATA (string
),
413 SBYTES (string
), pos_byte
,
414 SBYTES (string
) - pos_byte
,
415 (NILP (Vinhibit_changing_match_data
)
416 ? &search_regs
: NULL
));
419 /* Set last_thing_searched only when match data is changed. */
420 if (NILP (Vinhibit_changing_match_data
))
421 last_thing_searched
= Qt
;
425 if (val
< 0) return Qnil
;
427 if (NILP (Vinhibit_changing_match_data
))
428 for (i
= 0; i
< search_regs
.num_regs
; i
++)
429 if (search_regs
.start
[i
] >= 0)
432 = string_byte_to_char (string
, search_regs
.start
[i
]);
434 = string_byte_to_char (string
, search_regs
.end
[i
]);
437 return make_number (string_byte_to_char (string
, val
));
440 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
441 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
442 Matching ignores case if `case-fold-search' is non-nil.
443 If third arg START is non-nil, start search at that index in STRING.
444 For index of first char beyond the match, do (match-end 0).
445 `match-end' and `match-beginning' also give indices of substrings
446 matched by parenthesis constructs in the pattern.
448 You can use the function `match-string' to extract the substrings
449 matched by the parenthesis constructions in REGEXP. */)
450 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
452 return string_match_1 (regexp
, string
, start
, 0);
455 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
456 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
457 Find the longest match, in accord with Posix regular expression rules.
458 Case is ignored if `case-fold-search' is non-nil in the current buffer.
459 If third arg START is non-nil, start search at that index in STRING.
460 For index of first char beyond the match, do (match-end 0).
461 `match-end' and `match-beginning' also give indices of substrings
462 matched by parenthesis constructs in the pattern. */)
463 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
465 return string_match_1 (regexp
, string
, start
, 1);
468 /* Match REGEXP against STRING using translation table TABLE,
469 searching all of STRING, and return the index of the match,
470 or negative on failure. This does not clobber the match data. */
473 fast_string_match_internal (Lisp_Object regexp
, Lisp_Object string
,
477 struct re_pattern_buffer
*bufp
;
479 bufp
= compile_pattern (regexp
, 0, table
,
480 0, STRING_MULTIBYTE (string
));
482 re_match_object
= string
;
484 val
= re_search (bufp
, SSDATA (string
),
491 /* Match REGEXP against STRING, searching all of STRING ignoring case,
492 and return the index of the match, or negative on failure.
493 This does not clobber the match data.
494 We assume that STRING contains single-byte characters. */
497 fast_c_string_match_ignore_case (Lisp_Object regexp
,
498 const char *string
, ptrdiff_t len
)
501 struct re_pattern_buffer
*bufp
;
503 regexp
= string_make_unibyte (regexp
);
504 re_match_object
= Qt
;
505 bufp
= compile_pattern (regexp
, 0,
506 Vascii_canon_table
, 0,
509 val
= re_search (bufp
, string
, len
, 0, len
, 0);
514 /* Match REGEXP against the characters after POS to LIMIT, and return
515 the number of matched characters. If STRING is non-nil, match
516 against the characters in it. In that case, POS and LIMIT are
517 indices into the string. This function doesn't modify the match
521 fast_looking_at (Lisp_Object regexp
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
522 ptrdiff_t limit
, ptrdiff_t limit_byte
, Lisp_Object string
)
525 struct re_pattern_buffer
*buf
;
526 unsigned char *p1
, *p2
;
530 if (STRINGP (string
))
533 pos_byte
= string_char_to_byte (string
, pos
);
535 limit_byte
= string_char_to_byte (string
, limit
);
539 s2
= SBYTES (string
);
540 re_match_object
= string
;
541 multibyte
= STRING_MULTIBYTE (string
);
546 pos_byte
= CHAR_TO_BYTE (pos
);
548 limit_byte
= CHAR_TO_BYTE (limit
);
549 pos_byte
-= BEGV_BYTE
;
550 limit_byte
-= BEGV_BYTE
;
552 s1
= GPT_BYTE
- BEGV_BYTE
;
554 s2
= ZV_BYTE
- GPT_BYTE
;
558 s2
= ZV_BYTE
- BEGV_BYTE
;
563 s1
= ZV_BYTE
- BEGV_BYTE
;
566 re_match_object
= Qnil
;
567 multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
570 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
573 /* Prevent ralloc.c from relocating the current buffer while
575 r_alloc_inhibit_buffer_relocation (1);
577 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
578 pos_byte
, NULL
, limit_byte
);
580 r_alloc_inhibit_buffer_relocation (0);
588 /* The newline cache: remembering which sections of text have no newlines. */
590 /* If the user has requested the long scans caching, make sure it's on.
591 Otherwise, make sure it's off.
592 This is our cheezy way of associating an action with the change of
593 state of a buffer-local variable. */
594 static struct region_cache
*
595 newline_cache_on_off (struct buffer
*buf
)
597 struct buffer
*base_buf
= buf
;
598 bool indirect_p
= false;
600 if (buf
->base_buffer
)
602 base_buf
= buf
->base_buffer
;
606 /* Don't turn on or off the cache in the base buffer, if the value
607 of cache-long-scans of the base buffer is inconsistent with that.
608 This is because doing so will just make the cache pure overhead,
609 since if we turn it on via indirect buffer, it will be
610 immediately turned off by its base buffer. */
611 if (NILP (BVAR (buf
, cache_long_scans
)))
614 || NILP (BVAR (base_buf
, cache_long_scans
)))
616 /* It should be off. */
617 if (base_buf
->newline_cache
)
619 free_region_cache (base_buf
->newline_cache
);
620 base_buf
->newline_cache
= 0;
628 || !NILP (BVAR (base_buf
, cache_long_scans
)))
630 /* It should be on. */
631 if (base_buf
->newline_cache
== 0)
632 base_buf
->newline_cache
= new_region_cache ();
634 return base_buf
->newline_cache
;
639 /* Search for COUNT newlines between START/START_BYTE and END/END_BYTE.
641 If COUNT is positive, search forwards; END must be >= START.
642 If COUNT is negative, search backwards for the -COUNTth instance;
643 END must be <= START.
644 If COUNT is zero, do anything you please; run rogue, for all I care.
646 If END is zero, use BEGV or ZV instead, as appropriate for the
647 direction indicated by COUNT.
649 If we find COUNT instances, set *SHORTAGE to zero, and return the
650 position past the COUNTth match. Note that for reverse motion
651 this is not the same as the usual convention for Emacs motion commands.
653 If we don't find COUNT instances before reaching END, set *SHORTAGE
654 to the number of newlines left unfound, and return END.
656 If BYTEPOS is not NULL, set *BYTEPOS to the byte position corresponding
657 to the returned character position.
659 If ALLOW_QUIT, set immediate_quit. That's good to do
660 except when inside redisplay. */
663 find_newline (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
664 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
665 ptrdiff_t *bytepos
, bool allow_quit
)
667 struct region_cache
*newline_cache
;
669 struct buffer
*cache_buffer
;
675 end
= ZV
, end_byte
= ZV_BYTE
;
681 end
= BEGV
, end_byte
= BEGV_BYTE
;
684 end_byte
= CHAR_TO_BYTE (end
);
686 newline_cache
= newline_cache_on_off (current_buffer
);
687 if (current_buffer
->base_buffer
)
688 cache_buffer
= current_buffer
->base_buffer
;
690 cache_buffer
= current_buffer
;
695 immediate_quit
= allow_quit
;
700 /* Our innermost scanning loop is very simple; it doesn't know
701 about gaps, buffer ends, or the newline cache. ceiling is
702 the position of the last character before the next such
703 obstacle --- the last character the dumb search loop should
705 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
707 /* If we're using the newline cache, consult it to see whether
708 we can avoid some scanning. */
711 ptrdiff_t next_change
;
715 while (start
< end
&& result
)
719 result
= region_cache_forward (cache_buffer
, newline_cache
,
720 start
, &next_change
);
723 /* When the cache revalidation is deferred,
724 next-change might point beyond ZV, which will
725 cause assertion violation in CHAR_TO_BYTE below.
726 Limit next_change to ZV to avoid that. */
727 if (next_change
> ZV
)
730 lim1
= next_change
= end
;
733 lim1
= min (next_change
, end
);
735 /* The cache returned zero for this region; see if
736 this is because the region is known and includes
737 only newlines. While at that, count any newlines
738 we bump into, and exit if we found enough off them. */
739 start_byte
= CHAR_TO_BYTE (start
);
741 && FETCH_BYTE (start_byte
) == '\n')
748 *bytepos
= start_byte
;
752 /* If we found a non-newline character before hitting
753 position where the cache will again return non-zero
754 (i.e. no newlines beyond that position), it means
755 this region is not yet known to the cache, and we
756 must resort to the "dumb loop" method. */
757 if (start
< next_change
&& !result
)
764 start_byte
= end_byte
;
767 immediate_quit
= allow_quit
;
769 /* START should never be after END. */
770 if (start_byte
> ceiling_byte
)
771 start_byte
= ceiling_byte
;
773 /* Now the text after start is an unknown region, and
774 next_change is the position of the next known region. */
775 ceiling_byte
= min (CHAR_TO_BYTE (next_change
) - 1, ceiling_byte
);
777 else if (start_byte
== -1)
778 start_byte
= CHAR_TO_BYTE (start
);
780 /* The dumb loop can only scan text stored in contiguous
781 bytes. BUFFER_CEILING_OF returns the last character
782 position that is contiguous, so the ceiling is the
783 position after that. */
784 tem
= BUFFER_CEILING_OF (start_byte
);
785 ceiling_byte
= min (tem
, ceiling_byte
);
788 /* The termination address of the dumb loop. */
789 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
790 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
792 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
793 of the base, the cursor, and the next line. */
794 ptrdiff_t base
= start_byte
- lim_byte
;
795 ptrdiff_t cursor
, next
;
797 for (cursor
= base
; cursor
< 0; cursor
= next
)
800 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
801 next
= nl
? nl
- lim_addr
: 0;
803 /* If we're using the newline cache, cache the fact that
804 the region we just traversed is free of newlines. */
805 if (newline_cache
&& cursor
!= next
)
807 know_region_cache (cache_buffer
, newline_cache
,
808 BYTE_TO_CHAR (lim_byte
+ cursor
),
809 BYTE_TO_CHAR (lim_byte
+ next
));
810 /* know_region_cache can relocate buffer text. */
811 lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
822 *bytepos
= lim_byte
+ next
;
823 return BYTE_TO_CHAR (lim_byte
+ next
);
827 start_byte
= lim_byte
;
828 start
= BYTE_TO_CHAR (start_byte
);
834 /* The last character to check before the next obstacle. */
835 ptrdiff_t tem
, ceiling_byte
= end_byte
;
837 /* Consult the newline cache, if appropriate. */
840 ptrdiff_t next_change
;
844 while (start
> end
&& result
)
848 result
= region_cache_backward (cache_buffer
, newline_cache
,
849 start
, &next_change
);
853 lim1
= next_change
= end
;
856 lim1
= max (next_change
, end
);
857 start_byte
= CHAR_TO_BYTE (start
);
859 && FETCH_BYTE (start_byte
- 1) == '\n')
864 *bytepos
= start_byte
;
870 if (start
> next_change
&& !result
)
877 start_byte
= end_byte
;
880 immediate_quit
= allow_quit
;
882 /* Start should never be at or before end. */
883 if (start_byte
<= ceiling_byte
)
884 start_byte
= ceiling_byte
+ 1;
886 /* Now the text before start is an unknown region, and
887 next_change is the position of the next known region. */
888 ceiling_byte
= max (CHAR_TO_BYTE (next_change
), ceiling_byte
);
890 else if (start_byte
== -1)
891 start_byte
= CHAR_TO_BYTE (start
);
893 /* Stop scanning before the gap. */
894 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
895 ceiling_byte
= max (tem
, ceiling_byte
);
898 /* The termination address of the dumb loop. */
899 unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
901 /* Offsets (relative to CEILING_ADDR and CEILING_BYTE) of
902 the base, the cursor, and the previous line. These
903 offsets are at least -1. */
904 ptrdiff_t base
= start_byte
- ceiling_byte
;
905 ptrdiff_t cursor
, prev
;
907 for (cursor
= base
; 0 < cursor
; cursor
= prev
)
909 unsigned char *nl
= memrchr (ceiling_addr
, '\n', cursor
);
910 prev
= nl
? nl
- ceiling_addr
: -1;
912 /* If we're looking for newlines, cache the fact that
913 this line's region is free of them. */
914 if (newline_cache
&& cursor
!= prev
+ 1)
916 know_region_cache (cache_buffer
, newline_cache
,
917 BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1),
918 BYTE_TO_CHAR (ceiling_byte
+ cursor
));
919 /* know_region_cache can relocate buffer text. */
920 ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
930 *bytepos
= ceiling_byte
+ prev
+ 1;
931 return BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1);
935 start_byte
= ceiling_byte
;
936 start
= BYTE_TO_CHAR (start_byte
);
942 *shortage
= count
* direction
;
945 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
946 eassert (*bytepos
== CHAR_TO_BYTE (start
));
951 /* Search for COUNT instances of a line boundary.
952 Start at START. If COUNT is negative, search backwards.
954 We report the resulting position by calling TEMP_SET_PT_BOTH.
956 If we find COUNT instances. we position after (always after,
957 even if scanning backwards) the COUNTth match, and return 0.
959 If we don't find COUNT instances before reaching the end of the
960 buffer (or the beginning, if scanning backwards), we return
961 the number of line boundaries left unfound, and position at
962 the limit we bumped up against.
964 If ALLOW_QUIT, set immediate_quit. That's good to do
965 except in special cases. */
968 scan_newline (ptrdiff_t start
, ptrdiff_t start_byte
,
969 ptrdiff_t limit
, ptrdiff_t limit_byte
,
970 ptrdiff_t count
, bool allow_quit
)
972 ptrdiff_t charpos
, bytepos
, shortage
;
974 charpos
= find_newline (start
, start_byte
, limit
, limit_byte
,
975 count
, &shortage
, &bytepos
, allow_quit
);
977 TEMP_SET_PT_BOTH (limit
, limit_byte
);
979 TEMP_SET_PT_BOTH (charpos
, bytepos
);
983 /* Like above, but always scan from point and report the
984 resulting position in *CHARPOS and *BYTEPOS. */
987 scan_newline_from_point (ptrdiff_t count
, ptrdiff_t *charpos
,
993 *charpos
= find_newline (PT
, PT_BYTE
, BEGV
, BEGV_BYTE
, count
- 1,
994 &shortage
, bytepos
, 1);
996 *charpos
= find_newline (PT
, PT_BYTE
, ZV
, ZV_BYTE
, count
,
997 &shortage
, bytepos
, 1);
1001 /* Like find_newline, but doesn't allow QUITting and doesn't return
1004 find_newline_no_quit (ptrdiff_t from
, ptrdiff_t frombyte
,
1005 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
1007 return find_newline (from
, frombyte
, 0, -1, cnt
, NULL
, bytepos
, 0);
1010 /* Like find_newline, but returns position before the newline, not
1011 after, and only search up to TO.
1012 This isn't just find_newline_no_quit (...)-1, because you might hit TO. */
1015 find_before_next_newline (ptrdiff_t from
, ptrdiff_t to
,
1016 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
1019 ptrdiff_t pos
= find_newline (from
, -1, to
, -1, cnt
, &shortage
, bytepos
, 1);
1024 DEC_BOTH (pos
, *bytepos
);
1031 /* Subroutines of Lisp buffer search functions. */
1034 search_command (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
,
1035 Lisp_Object count
, int direction
, int RE
, bool posix
)
1040 EMACS_INT n
= direction
;
1044 CHECK_NUMBER (count
);
1048 CHECK_STRING (string
);
1052 lim
= ZV
, lim_byte
= ZV_BYTE
;
1054 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1058 CHECK_NUMBER_COERCE_MARKER (bound
);
1060 if (n
> 0 ? lim
< PT
: lim
> PT
)
1061 error ("Invalid search bound (wrong side of point)");
1063 lim
= ZV
, lim_byte
= ZV_BYTE
;
1064 else if (lim
< BEGV
)
1065 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1067 lim_byte
= CHAR_TO_BYTE (lim
);
1070 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
1071 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
1072 BVAR (current_buffer
, case_eqv_table
));
1074 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
1075 (!NILP (BVAR (current_buffer
, case_fold_search
))
1076 ? BVAR (current_buffer
, case_canon_table
)
1078 (!NILP (BVAR (current_buffer
, case_fold_search
))
1079 ? BVAR (current_buffer
, case_eqv_table
)
1085 xsignal1 (Qsearch_failed
, string
);
1087 if (!EQ (noerror
, Qt
))
1089 eassert (BEGV
<= lim
&& lim
<= ZV
);
1090 SET_PT_BOTH (lim
, lim_byte
);
1092 #if 0 /* This would be clean, but maybe programs depend on
1093 a value of nil here. */
1101 eassert (BEGV
<= np
&& np
<= ZV
);
1104 return make_number (np
);
1107 /* Return true if REGEXP it matches just one constant string. */
1110 trivial_regexp_p (Lisp_Object regexp
)
1112 ptrdiff_t len
= SBYTES (regexp
);
1113 unsigned char *s
= SDATA (regexp
);
1118 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1125 case '|': case '(': case ')': case '`': case '\'': case 'b':
1126 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1127 case 'S': case '=': case '{': case '}': case '_':
1128 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1129 case '1': case '2': case '3': case '4': case '5':
1130 case '6': case '7': case '8': case '9':
1138 /* Search for the n'th occurrence of STRING in the current buffer,
1139 starting at position POS and stopping at position LIM,
1140 treating STRING as a literal string if RE is false or as
1141 a regular expression if RE is true.
1143 If N is positive, searching is forward and LIM must be greater than POS.
1144 If N is negative, searching is backward and LIM must be less than POS.
1146 Returns -x if x occurrences remain to be found (x > 0),
1147 or else the position at the beginning of the Nth occurrence
1148 (if searching backward) or the end (if searching forward).
1150 POSIX is nonzero if we want full backtracking (POSIX style)
1151 for this pattern. 0 means backtrack only enough to get a valid match. */
1153 #define TRANSLATE(out, trt, d) \
1159 temp = Faref (trt, make_number (d)); \
1160 if (INTEGERP (temp)) \
1161 out = XINT (temp); \
1170 /* Only used in search_buffer, to record the end position of the match
1171 when searching regexps and SEARCH_REGS should not be changed
1172 (i.e. Vinhibit_changing_match_data is non-nil). */
1173 static struct re_registers search_regs_1
;
1176 search_buffer (Lisp_Object string
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
1177 ptrdiff_t lim
, ptrdiff_t lim_byte
, EMACS_INT n
,
1178 int RE
, Lisp_Object trt
, Lisp_Object inverse_trt
, bool posix
)
1180 ptrdiff_t len
= SCHARS (string
);
1181 ptrdiff_t len_byte
= SBYTES (string
);
1182 register ptrdiff_t i
;
1184 if (running_asynch_code
)
1185 save_search_regs ();
1187 /* Searching 0 times means don't move. */
1188 /* Null string is found at starting position. */
1189 if (len
== 0 || n
== 0)
1191 set_search_regs (pos_byte
, 0);
1195 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1197 unsigned char *p1
, *p2
;
1199 struct re_pattern_buffer
*bufp
;
1201 bufp
= compile_pattern (string
,
1202 (NILP (Vinhibit_changing_match_data
)
1203 ? &search_regs
: &search_regs_1
),
1205 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
1207 immediate_quit
= 1; /* Quit immediately if user types ^G,
1208 because letting this function finish
1209 can take too long. */
1210 QUIT
; /* Do a pending quit right away,
1211 to avoid paradoxical behavior */
1212 /* Get pointers and sizes of the two strings
1213 that make up the visible portion of the buffer. */
1216 s1
= GPT_BYTE
- BEGV_BYTE
;
1218 s2
= ZV_BYTE
- GPT_BYTE
;
1222 s2
= ZV_BYTE
- BEGV_BYTE
;
1227 s1
= ZV_BYTE
- BEGV_BYTE
;
1230 re_match_object
= Qnil
;
1233 /* Prevent ralloc.c from relocating the current buffer while
1235 r_alloc_inhibit_buffer_relocation (1);
1242 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1243 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1244 (NILP (Vinhibit_changing_match_data
)
1245 ? &search_regs
: &search_regs_1
),
1246 /* Don't allow match past current point */
1247 pos_byte
- BEGV_BYTE
);
1250 matcher_overflow ();
1254 if (NILP (Vinhibit_changing_match_data
))
1256 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1257 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1258 if (search_regs
.start
[i
] >= 0)
1260 search_regs
.start
[i
]
1261 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1263 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1265 XSETBUFFER (last_thing_searched
, current_buffer
);
1266 /* Set pos to the new position. */
1267 pos
= search_regs
.start
[0];
1271 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1272 /* Set pos to the new position. */
1273 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1280 r_alloc_inhibit_buffer_relocation (0);
1290 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1291 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1292 (NILP (Vinhibit_changing_match_data
)
1293 ? &search_regs
: &search_regs_1
),
1294 lim_byte
- BEGV_BYTE
);
1297 matcher_overflow ();
1301 if (NILP (Vinhibit_changing_match_data
))
1303 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1304 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1305 if (search_regs
.start
[i
] >= 0)
1307 search_regs
.start
[i
]
1308 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1310 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1312 XSETBUFFER (last_thing_searched
, current_buffer
);
1313 pos
= search_regs
.end
[0];
1317 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1318 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1325 r_alloc_inhibit_buffer_relocation (0);
1333 r_alloc_inhibit_buffer_relocation (0);
1337 else /* non-RE case */
1339 unsigned char *raw_pattern
, *pat
;
1340 ptrdiff_t raw_pattern_size
;
1341 ptrdiff_t raw_pattern_size_byte
;
1342 unsigned char *patbuf
;
1343 bool multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1344 unsigned char *base_pat
;
1345 /* Set to positive if we find a non-ASCII char that need
1346 translation. Otherwise set to zero later. */
1348 bool boyer_moore_ok
= 1;
1351 /* MULTIBYTE says whether the text to be searched is multibyte.
1352 We must convert PATTERN to match that, or we will not really
1353 find things right. */
1355 if (multibyte
== STRING_MULTIBYTE (string
))
1357 raw_pattern
= SDATA (string
);
1358 raw_pattern_size
= SCHARS (string
);
1359 raw_pattern_size_byte
= SBYTES (string
);
1363 raw_pattern_size
= SCHARS (string
);
1364 raw_pattern_size_byte
1365 = count_size_as_multibyte (SDATA (string
),
1367 raw_pattern
= SAFE_ALLOCA (raw_pattern_size_byte
+ 1);
1368 copy_text (SDATA (string
), raw_pattern
,
1369 SCHARS (string
), 0, 1);
1373 /* Converting multibyte to single-byte.
1375 ??? Perhaps this conversion should be done in a special way
1376 by subtracting nonascii-insert-offset from each non-ASCII char,
1377 so that only the multibyte chars which really correspond to
1378 the chosen single-byte character set can possibly match. */
1379 raw_pattern_size
= SCHARS (string
);
1380 raw_pattern_size_byte
= SCHARS (string
);
1381 raw_pattern
= SAFE_ALLOCA (raw_pattern_size
+ 1);
1382 copy_text (SDATA (string
), raw_pattern
,
1383 SBYTES (string
), 1, 0);
1386 /* Copy and optionally translate the pattern. */
1387 len
= raw_pattern_size
;
1388 len_byte
= raw_pattern_size_byte
;
1389 SAFE_NALLOCA (patbuf
, MAX_MULTIBYTE_LENGTH
, len
);
1391 base_pat
= raw_pattern
;
1394 /* Fill patbuf by translated characters in STRING while
1395 checking if we can use boyer-moore search. If TRT is
1396 non-nil, we can use boyer-moore search only if TRT can be
1397 represented by the byte array of 256 elements. For that,
1398 all non-ASCII case-equivalents of all case-sensitive
1399 characters in STRING must belong to the same character
1400 group (two characters belong to the same group iff their
1401 multibyte forms are the same except for the last byte;
1402 i.e. every 64 characters form a group; U+0000..U+003F,
1403 U+0040..U+007F, U+0080..U+00BF, ...). */
1407 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1408 int c
, translated
, inverse
;
1409 int in_charlen
, charlen
;
1411 /* If we got here and the RE flag is set, it's because we're
1412 dealing with a regexp known to be trivial, so the backslash
1413 just quotes the next character. */
1414 if (RE
&& *base_pat
== '\\')
1422 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1427 charlen
= in_charlen
;
1431 /* Translate the character. */
1432 TRANSLATE (translated
, trt
, c
);
1433 charlen
= CHAR_STRING (translated
, str_base
);
1436 /* Check if C has any other case-equivalents. */
1437 TRANSLATE (inverse
, inverse_trt
, c
);
1438 /* If so, check if we can use boyer-moore. */
1439 if (c
!= inverse
&& boyer_moore_ok
)
1441 /* Check if all equivalents belong to the same
1442 group of characters. Note that the check of C
1443 itself is done by the last iteration. */
1444 int this_char_base
= -1;
1446 while (boyer_moore_ok
)
1448 if (ASCII_CHAR_P (inverse
))
1450 if (this_char_base
> 0)
1455 else if (CHAR_BYTE8_P (inverse
))
1456 /* Boyer-moore search can't handle a
1457 translation of an eight-bit
1460 else if (this_char_base
< 0)
1462 this_char_base
= inverse
& ~0x3F;
1464 char_base
= this_char_base
;
1465 else if (this_char_base
!= char_base
)
1468 else if ((inverse
& ~0x3F) != this_char_base
)
1472 TRANSLATE (inverse
, inverse_trt
, inverse
);
1477 /* Store this character into the translated pattern. */
1478 memcpy (pat
, str
, charlen
);
1480 base_pat
+= in_charlen
;
1481 len_byte
-= in_charlen
;
1484 /* If char_base is still negative we didn't find any translated
1485 non-ASCII characters. */
1491 /* Unibyte buffer. */
1495 int c
, translated
, inverse
;
1497 /* If we got here and the RE flag is set, it's because we're
1498 dealing with a regexp known to be trivial, so the backslash
1499 just quotes the next character. */
1500 if (RE
&& *base_pat
== '\\')
1507 TRANSLATE (translated
, trt
, c
);
1508 *pat
++ = translated
;
1509 /* Check that none of C's equivalents violates the
1510 assumptions of boyer_moore. */
1511 TRANSLATE (inverse
, inverse_trt
, c
);
1514 if (inverse
>= 0200)
1521 TRANSLATE (inverse
, inverse_trt
, inverse
);
1526 len_byte
= pat
- patbuf
;
1527 pat
= base_pat
= patbuf
;
1531 ? boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1534 : simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1535 pos
, pos_byte
, lim
, lim_byte
));
1541 /* Do a simple string search N times for the string PAT,
1542 whose length is LEN/LEN_BYTE,
1543 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1544 TRT is the translation table.
1546 Return the character position where the match is found.
1547 Otherwise, if M matches remained to be found, return -M.
1549 This kind of search works regardless of what is in PAT and
1550 regardless of what is in TRT. It is used in cases where
1551 boyer_moore cannot work. */
1554 simple_search (EMACS_INT n
, unsigned char *pat
,
1555 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1556 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1557 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1559 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1560 bool forward
= n
> 0;
1561 /* Number of buffer bytes matched. Note that this may be different
1562 from len_byte in a multibyte buffer. */
1563 ptrdiff_t match_byte
= PTRDIFF_MIN
;
1565 if (lim
> pos
&& multibyte
)
1570 /* Try matching at position POS. */
1571 ptrdiff_t this_pos
= pos
;
1572 ptrdiff_t this_pos_byte
= pos_byte
;
1573 ptrdiff_t this_len
= len
;
1574 unsigned char *p
= pat
;
1575 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1578 while (this_len
> 0)
1580 int charlen
, buf_charlen
;
1583 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1584 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1586 TRANSLATE (buf_ch
, trt
, buf_ch
);
1588 if (buf_ch
!= pat_ch
)
1594 this_pos_byte
+= buf_charlen
;
1600 match_byte
= this_pos_byte
- pos_byte
;
1602 pos_byte
+= match_byte
;
1606 INC_BOTH (pos
, pos_byte
);
1616 /* Try matching at position POS. */
1617 ptrdiff_t this_pos
= pos
;
1618 ptrdiff_t this_len
= len
;
1619 unsigned char *p
= pat
;
1621 if (pos
+ len
> lim
)
1624 while (this_len
> 0)
1627 int buf_ch
= FETCH_BYTE (this_pos
);
1628 TRANSLATE (buf_ch
, trt
, buf_ch
);
1630 if (buf_ch
!= pat_ch
)
1649 /* Backwards search. */
1650 else if (lim
< pos
&& multibyte
)
1655 /* Try matching at position POS. */
1656 ptrdiff_t this_pos
= pos
;
1657 ptrdiff_t this_pos_byte
= pos_byte
;
1658 ptrdiff_t this_len
= len
;
1659 const unsigned char *p
= pat
+ len_byte
;
1661 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1664 while (this_len
> 0)
1668 DEC_BOTH (this_pos
, this_pos_byte
);
1669 PREV_CHAR_BOUNDARY (p
, pat
);
1670 pat_ch
= STRING_CHAR (p
);
1671 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1672 TRANSLATE (buf_ch
, trt
, buf_ch
);
1674 if (buf_ch
!= pat_ch
)
1682 match_byte
= pos_byte
- this_pos_byte
;
1684 pos_byte
= this_pos_byte
;
1688 DEC_BOTH (pos
, pos_byte
);
1698 /* Try matching at position POS. */
1699 ptrdiff_t this_pos
= pos
- len
;
1700 ptrdiff_t this_len
= len
;
1701 unsigned char *p
= pat
;
1706 while (this_len
> 0)
1709 int buf_ch
= FETCH_BYTE (this_pos
);
1710 TRANSLATE (buf_ch
, trt
, buf_ch
);
1712 if (buf_ch
!= pat_ch
)
1734 eassert (match_byte
!= PTRDIFF_MIN
);
1736 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1738 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1748 /* Do Boyer-Moore search N times for the string BASE_PAT,
1749 whose length is LEN_BYTE,
1750 from buffer position POS_BYTE until LIM_BYTE.
1751 DIRECTION says which direction we search in.
1752 TRT and INVERSE_TRT are translation tables.
1753 Characters in PAT are already translated by TRT.
1755 This kind of search works if all the characters in BASE_PAT that
1756 have nontrivial translation are the same aside from the last byte.
1757 This makes it possible to translate just the last byte of a
1758 character, and do so after just a simple test of the context.
1759 CHAR_BASE is nonzero if there is such a non-ASCII character.
1761 If that criterion is not satisfied, do not call this function. */
1764 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1766 Lisp_Object trt
, Lisp_Object inverse_trt
,
1767 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1770 int direction
= ((n
> 0) ? 1 : -1);
1771 register ptrdiff_t dirlen
;
1773 int stride_for_teases
= 0;
1775 register unsigned char *cursor
, *p_limit
;
1776 register ptrdiff_t i
;
1778 unsigned char *pat
, *pat_end
;
1779 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1781 unsigned char simple_translate
[0400];
1782 /* These are set to the preceding bytes of a byte to be translated
1783 if char_base is nonzero. As the maximum byte length of a
1784 multibyte character is 5, we have to check at most four previous
1786 int translate_prev_byte1
= 0;
1787 int translate_prev_byte2
= 0;
1788 int translate_prev_byte3
= 0;
1790 /* The general approach is that we are going to maintain that we know
1791 the first (closest to the present position, in whatever direction
1792 we're searching) character that could possibly be the last
1793 (furthest from present position) character of a valid match. We
1794 advance the state of our knowledge by looking at that character
1795 and seeing whether it indeed matches the last character of the
1796 pattern. If it does, we take a closer look. If it does not, we
1797 move our pointer (to putative last characters) as far as is
1798 logically possible. This amount of movement, which I call a
1799 stride, will be the length of the pattern if the actual character
1800 appears nowhere in the pattern, otherwise it will be the distance
1801 from the last occurrence of that character to the end of the
1802 pattern. If the amount is zero we have a possible match. */
1804 /* Here we make a "mickey mouse" BM table. The stride of the search
1805 is determined only by the last character of the putative match.
1806 If that character does not match, we will stride the proper
1807 distance to propose a match that superimposes it on the last
1808 instance of a character that matches it (per trt), or misses
1809 it entirely if there is none. */
1811 dirlen
= len_byte
* direction
;
1813 /* Record position after the end of the pattern. */
1814 pat_end
= base_pat
+ len_byte
;
1815 /* BASE_PAT points to a character that we start scanning from.
1816 It is the first character in a forward search,
1817 the last character in a backward search. */
1819 base_pat
= pat_end
- 1;
1821 /* A character that does not appear in the pattern induces a
1822 stride equal to the pattern length. */
1823 for (i
= 0; i
< 0400; i
++)
1826 /* We use this for translation, instead of TRT itself.
1827 We fill this in to handle the characters that actually
1828 occur in the pattern. Others don't matter anyway! */
1829 for (i
= 0; i
< 0400; i
++)
1830 simple_translate
[i
] = i
;
1834 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1835 byte following them are the target of translation. */
1836 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1837 int cblen
= CHAR_STRING (char_base
, str
);
1839 translate_prev_byte1
= str
[cblen
- 2];
1842 translate_prev_byte2
= str
[cblen
- 3];
1844 translate_prev_byte3
= str
[cblen
- 4];
1851 unsigned char *ptr
= base_pat
+ i
;
1855 /* If the byte currently looking at is the last of a
1856 character to check case-equivalents, set CH to that
1857 character. An ASCII character and a non-ASCII character
1858 matching with CHAR_BASE are to be checked. */
1861 if (ASCII_CHAR_P (*ptr
) || ! multibyte
)
1864 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1866 unsigned char *charstart
= ptr
- 1;
1868 while (! (CHAR_HEAD_P (*charstart
)))
1870 ch
= STRING_CHAR (charstart
);
1871 if (char_base
!= (ch
& ~0x3F))
1875 if (ch
>= 0200 && multibyte
)
1876 j
= (ch
& 0x3F) | 0200;
1881 stride_for_teases
= BM_tab
[j
];
1883 BM_tab
[j
] = dirlen
- i
;
1884 /* A translation table is accompanied by its inverse -- see
1885 comment following downcase_table for details. */
1888 int starting_ch
= ch
;
1893 TRANSLATE (ch
, inverse_trt
, ch
);
1894 if (ch
>= 0200 && multibyte
)
1895 j
= (ch
& 0x3F) | 0200;
1899 /* For all the characters that map into CH,
1900 set up simple_translate to map the last byte
1902 simple_translate
[j
] = starting_j
;
1903 if (ch
== starting_ch
)
1905 BM_tab
[j
] = dirlen
- i
;
1914 stride_for_teases
= BM_tab
[j
];
1915 BM_tab
[j
] = dirlen
- i
;
1917 /* stride_for_teases tells how much to stride if we get a
1918 match on the far character but are subsequently
1919 disappointed, by recording what the stride would have been
1920 for that character if the last character had been
1923 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1924 /* loop invariant - POS_BYTE points at where last char (first
1925 char if reverse) of pattern would align in a possible match. */
1929 unsigned char *tail_end_ptr
;
1931 /* It's been reported that some (broken) compiler thinks that
1932 Boolean expressions in an arithmetic context are unsigned.
1933 Using an explicit ?1:0 prevents this. */
1934 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1936 return (n
* (0 - direction
));
1937 /* First we do the part we can by pointers (maybe nothing) */
1940 limit
= pos_byte
- dirlen
+ direction
;
1943 limit
= BUFFER_CEILING_OF (limit
);
1944 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1945 can take on without hitting edge of buffer or the gap. */
1946 limit
= min (limit
, pos_byte
+ 20000);
1947 limit
= min (limit
, lim_byte
- 1);
1951 limit
= BUFFER_FLOOR_OF (limit
);
1952 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1953 can take on without hitting edge of buffer or the gap. */
1954 limit
= max (limit
, pos_byte
- 20000);
1955 limit
= max (limit
, lim_byte
);
1957 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1958 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1960 if ((limit
- pos_byte
) * direction
> 20)
1964 p_limit
= BYTE_POS_ADDR (limit
);
1965 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1966 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1967 while (1) /* use one cursor setting as long as i can */
1969 if (direction
> 0) /* worth duplicating */
1971 while (cursor
<= p_limit
)
1973 if (BM_tab
[*cursor
] == 0)
1975 cursor
+= BM_tab
[*cursor
];
1980 while (cursor
>= p_limit
)
1982 if (BM_tab
[*cursor
] == 0)
1984 cursor
+= BM_tab
[*cursor
];
1987 /* If you are here, cursor is beyond the end of the
1988 searched region. You fail to match within the
1989 permitted region and would otherwise try a character
1990 beyond that region. */
1994 i
= dirlen
- direction
;
1997 while ((i
-= direction
) + direction
!= 0)
2000 cursor
-= direction
;
2001 /* Translate only the last byte of a character. */
2003 || ((cursor
== tail_end_ptr
2004 || CHAR_HEAD_P (cursor
[1]))
2005 && (CHAR_HEAD_P (cursor
[0])
2006 /* Check if this is the last byte of
2007 a translatable character. */
2008 || (translate_prev_byte1
== cursor
[-1]
2009 && (CHAR_HEAD_P (translate_prev_byte1
)
2010 || (translate_prev_byte2
== cursor
[-2]
2011 && (CHAR_HEAD_P (translate_prev_byte2
)
2012 || (translate_prev_byte3
== cursor
[-3]))))))))
2013 ch
= simple_translate
[*cursor
];
2022 while ((i
-= direction
) + direction
!= 0)
2024 cursor
-= direction
;
2025 if (pat
[i
] != *cursor
)
2029 cursor
+= dirlen
- i
- direction
; /* fix cursor */
2030 if (i
+ direction
== 0)
2032 ptrdiff_t position
, start
, end
;
2034 ptrdiff_t cursor_off
;
2037 cursor
-= direction
;
2039 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
2040 ? 1 - len_byte
: 0);
2042 /* set_search_regs might call malloc, which could
2043 cause ralloc.c relocate buffer text. We need to
2044 update pointers into buffer text due to that. */
2045 cursor_off
= cursor
- p2
;
2047 set_search_regs (position
, len_byte
);
2049 p_limit
= BYTE_POS_ADDR (limit
);
2050 p2
= BYTE_POS_ADDR (pos_byte
);
2051 cursor
= p2
+ cursor_off
;
2054 if (NILP (Vinhibit_changing_match_data
))
2056 start
= search_regs
.start
[0];
2057 end
= search_regs
.end
[0];
2060 /* If Vinhibit_changing_match_data is non-nil,
2061 search_regs will not be changed. So let's
2062 compute start and end here. */
2064 start
= BYTE_TO_CHAR (position
);
2065 end
= BYTE_TO_CHAR (position
+ len_byte
);
2068 if ((n
-= direction
) != 0)
2069 cursor
+= dirlen
; /* to resume search */
2071 return direction
> 0 ? end
: start
;
2074 cursor
+= stride_for_teases
; /* <sigh> we lose - */
2076 pos_byte
+= cursor
- p2
;
2079 /* Now we'll pick up a clump that has to be done the hard
2080 way because it covers a discontinuity. */
2082 limit
= ((direction
> 0)
2083 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
2084 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
2085 limit
= ((direction
> 0)
2086 ? min (limit
+ len_byte
, lim_byte
- 1)
2087 : max (limit
- len_byte
, lim_byte
));
2088 /* LIMIT is now the last value POS_BYTE can have
2089 and still be valid for a possible match. */
2092 /* This loop can be coded for space rather than
2093 speed because it will usually run only once.
2094 (the reach is at most len + 21, and typically
2095 does not exceed len). */
2096 while ((limit
- pos_byte
) * direction
>= 0)
2098 int ch
= FETCH_BYTE (pos_byte
);
2099 if (BM_tab
[ch
] == 0)
2101 pos_byte
+= BM_tab
[ch
];
2103 break; /* ran off the end */
2106 /* Found what might be a match. */
2107 i
= dirlen
- direction
;
2108 while ((i
-= direction
) + direction
!= 0)
2112 pos_byte
-= direction
;
2113 ptr
= BYTE_POS_ADDR (pos_byte
);
2114 /* Translate only the last byte of a character. */
2116 || ((ptr
== tail_end_ptr
2117 || CHAR_HEAD_P (ptr
[1]))
2118 && (CHAR_HEAD_P (ptr
[0])
2119 /* Check if this is the last byte of a
2120 translatable character. */
2121 || (translate_prev_byte1
== ptr
[-1]
2122 && (CHAR_HEAD_P (translate_prev_byte1
)
2123 || (translate_prev_byte2
== ptr
[-2]
2124 && (CHAR_HEAD_P (translate_prev_byte2
)
2125 || translate_prev_byte3
== ptr
[-3])))))))
2126 ch
= simple_translate
[*ptr
];
2132 /* Above loop has moved POS_BYTE part or all the way
2133 back to the first pos (last pos if reverse).
2134 Set it once again at the last (first if reverse) char. */
2135 pos_byte
+= dirlen
- i
- direction
;
2136 if (i
+ direction
== 0)
2138 ptrdiff_t position
, start
, end
;
2139 pos_byte
-= direction
;
2141 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2142 set_search_regs (position
, len_byte
);
2144 if (NILP (Vinhibit_changing_match_data
))
2146 start
= search_regs
.start
[0];
2147 end
= search_regs
.end
[0];
2150 /* If Vinhibit_changing_match_data is non-nil,
2151 search_regs will not be changed. So let's
2152 compute start and end here. */
2154 start
= BYTE_TO_CHAR (position
);
2155 end
= BYTE_TO_CHAR (position
+ len_byte
);
2158 if ((n
-= direction
) != 0)
2159 pos_byte
+= dirlen
; /* to resume search */
2161 return direction
> 0 ? end
: start
;
2164 pos_byte
+= stride_for_teases
;
2167 /* We have done one clump. Can we continue? */
2168 if ((lim_byte
- pos_byte
) * direction
< 0)
2169 return ((0 - n
) * direction
);
2171 return BYTE_TO_CHAR (pos_byte
);
2174 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2175 for the overall match just found in the current buffer.
2176 Also clear out the match data for registers 1 and up. */
2179 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2183 if (!NILP (Vinhibit_changing_match_data
))
2186 /* Make sure we have registers in which to store
2187 the match position. */
2188 if (search_regs
.num_regs
== 0)
2190 search_regs
.start
= xmalloc (2 * sizeof (regoff_t
));
2191 search_regs
.end
= xmalloc (2 * sizeof (regoff_t
));
2192 search_regs
.num_regs
= 2;
2195 /* Clear out the other registers. */
2196 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2198 search_regs
.start
[i
] = -1;
2199 search_regs
.end
[i
] = -1;
2202 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2203 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2204 XSETBUFFER (last_thing_searched
, current_buffer
);
2207 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2208 "MSearch backward: ",
2209 doc
: /* Search backward from point for STRING.
2210 Set point to the beginning of the occurrence found, and return point.
2211 An optional second argument bounds the search; it is a buffer position.
2212 The match found must not begin before that position. A value of nil
2213 means search to the beginning of the accessible portion of the buffer.
2214 Optional third argument, if t, means if fail just return nil (no error).
2215 If not nil and not t, position at limit of search and return nil.
2216 Optional fourth argument COUNT, if a positive number, means to search
2217 for COUNT successive occurrences. If COUNT is negative, search
2218 forward, instead of backward, for -COUNT occurrences. A value of
2219 nil means the same as 1.
2220 With COUNT positive, the match found is the COUNTth to last one (or
2221 last, if COUNT is 1 or nil) in the buffer located entirely before
2222 the origin of the search; correspondingly with COUNT negative.
2224 Search case-sensitivity is determined by the value of the variable
2225 `case-fold-search', which see.
2227 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2228 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2230 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2233 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2234 doc
: /* Search forward from point for STRING.
2235 Set point to the end of the occurrence found, and return point.
2236 An optional second argument bounds the search; it is a buffer position.
2237 The match found must not end after that position. A value of nil
2238 means search to the end of the accessible portion of the buffer.
2239 Optional third argument, if t, means if fail just return nil (no error).
2240 If not nil and not t, move to limit of search and return nil.
2241 Optional fourth argument COUNT, if a positive number, means to search
2242 for COUNT successive occurrences. If COUNT is negative, search
2243 backward, instead of forward, for -COUNT occurrences. A value of
2244 nil means the same as 1.
2245 With COUNT positive, the match found is the COUNTth one (or first,
2246 if COUNT is 1 or nil) in the buffer located entirely after the
2247 origin of the search; correspondingly with COUNT negative.
2249 Search case-sensitivity is determined by the value of the variable
2250 `case-fold-search', which see.
2252 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2253 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2255 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2258 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2259 "sRE search backward: ",
2260 doc
: /* Search backward from point for match for regular expression REGEXP.
2261 Set point to the beginning of the occurrence found, and return point.
2262 An optional second argument bounds the search; it is a buffer position.
2263 The match found must not begin before that position. A value of nil
2264 means search to the beginning of the accessible portion of the buffer.
2265 Optional third argument, if t, means if fail just return nil (no error).
2266 If not nil and not t, position at limit of search and return nil.
2267 Optional fourth argument COUNT, if a positive number, means to search
2268 for COUNT successive occurrences. If COUNT is negative, search
2269 forward, instead of backward, for -COUNT occurrences. A value of
2270 nil means the same as 1.
2271 With COUNT positive, the match found is the COUNTth to last one (or
2272 last, if COUNT is 1 or nil) in the buffer located entirely before
2273 the origin of the search; correspondingly with COUNT negative.
2275 Search case-sensitivity is determined by the value of the variable
2276 `case-fold-search', which see.
2278 See also the functions `match-beginning', `match-end', `match-string',
2279 and `replace-match'. */)
2280 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2282 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2285 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2287 doc
: /* Search forward from point for regular expression REGEXP.
2288 Set point to the end of the occurrence found, and return point.
2289 An optional second argument bounds the search; it is a buffer position.
2290 The match found must not end after that position. A value of nil
2291 means search to the end of the accessible portion of the buffer.
2292 Optional third argument, if t, means if fail just return nil (no error).
2293 If not nil and not t, move to limit of search and return nil.
2294 Optional fourth argument COUNT, if a positive number, means to search
2295 for COUNT successive occurrences. If COUNT is negative, search
2296 backward, instead of forward, for -COUNT occurrences. A value of
2297 nil means the same as 1.
2298 With COUNT positive, the match found is the COUNTth one (or first,
2299 if COUNT is 1 or nil) in the buffer located entirely after the
2300 origin of the search; correspondingly with COUNT negative.
2302 Search case-sensitivity is determined by the value of the variable
2303 `case-fold-search', which see.
2305 See also the functions `match-beginning', `match-end', `match-string',
2306 and `replace-match'. */)
2307 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2309 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2312 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2313 "sPosix search backward: ",
2314 doc
: /* Search backward from point for match for regular expression REGEXP.
2315 Find the longest match in accord with Posix regular expression rules.
2316 Set point to the beginning of the occurrence found, and return point.
2317 An optional second argument bounds the search; it is a buffer position.
2318 The match found must not begin before that position. A value of nil
2319 means search to the beginning of the accessible portion of the buffer.
2320 Optional third argument, if t, means if fail just return nil (no error).
2321 If not nil and not t, position at limit of search and return nil.
2322 Optional fourth argument COUNT, if a positive number, means to search
2323 for COUNT successive occurrences. If COUNT is negative, search
2324 forward, instead of backward, for -COUNT occurrences. A value of
2325 nil means the same as 1.
2326 With COUNT positive, the match found is the COUNTth to last one (or
2327 last, if COUNT is 1 or nil) in the buffer located entirely before
2328 the origin of the search; correspondingly with COUNT negative.
2330 Search case-sensitivity is determined by the value of the variable
2331 `case-fold-search', which see.
2333 See also the functions `match-beginning', `match-end', `match-string',
2334 and `replace-match'. */)
2335 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2337 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2340 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2342 doc
: /* Search forward from point for regular expression REGEXP.
2343 Find the longest match in accord with Posix regular expression rules.
2344 Set point to the end of the occurrence found, and return point.
2345 An optional second argument bounds the search; it is a buffer position.
2346 The match found must not end after that position. A value of nil
2347 means search to the end of the accessible portion of the buffer.
2348 Optional third argument, if t, means if fail just return nil (no error).
2349 If not nil and not t, move to limit of search and return nil.
2350 Optional fourth argument COUNT, if a positive number, means to search
2351 for COUNT successive occurrences. If COUNT is negative, search
2352 backward, instead of forward, for -COUNT occurrences. A value of
2353 nil means the same as 1.
2354 With COUNT positive, the match found is the COUNTth one (or first,
2355 if COUNT is 1 or nil) in the buffer located entirely after the
2356 origin of the search; correspondingly with COUNT negative.
2358 Search case-sensitivity is determined by the value of the variable
2359 `case-fold-search', which see.
2361 See also the functions `match-beginning', `match-end', `match-string',
2362 and `replace-match'. */)
2363 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2365 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2368 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2369 doc
: /* Replace text matched by last search with NEWTEXT.
2370 Leave point at the end of the replacement text.
2372 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2373 the replacement text. Otherwise, maybe capitalize the whole text, or
2374 maybe just word initials, based on the replaced text. If the replaced
2375 text has only capital letters and has at least one multiletter word,
2376 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2377 in the replaced text, capitalize each word in NEWTEXT.
2379 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2380 Otherwise treat `\\' as special:
2381 `\\&' in NEWTEXT means substitute original matched text.
2382 `\\N' means substitute what matched the Nth `\\(...\\)'.
2383 If Nth parens didn't match, substitute nothing.
2384 `\\\\' means insert one `\\'.
2385 `\\?' is treated literally
2386 (for compatibility with `query-replace-regexp').
2387 Any other character following `\\' signals an error.
2388 Case conversion does not apply to these substitutions.
2390 If optional fourth argument STRING is non-nil, it should be a string
2391 to act on; this should be the string on which the previous match was
2392 done via `string-match'. In this case, `replace-match' creates and
2393 returns a new string, made by copying STRING and replacing the part of
2394 STRING that was matched (the original STRING itself is not altered).
2396 The optional fifth argument SUBEXP specifies a subexpression;
2397 it says to replace just that subexpression with NEWTEXT,
2398 rather than replacing the entire matched text.
2399 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2400 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2401 NEWTEXT in place of subexp N.
2402 This is useful only after a regular expression search or match,
2403 since only regular expressions have distinguished subexpressions. */)
2404 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2406 enum { nochange
, all_caps
, cap_initial
} case_action
;
2407 ptrdiff_t pos
, pos_byte
;
2408 bool some_multiletter_word
;
2409 bool some_lowercase
;
2410 bool some_uppercase
;
2411 bool some_nonuppercase_initial
;
2414 ptrdiff_t opoint
, newpoint
;
2416 CHECK_STRING (newtext
);
2418 if (! NILP (string
))
2419 CHECK_STRING (string
);
2421 case_action
= nochange
; /* We tried an initialization */
2422 /* but some C compilers blew it */
2424 if (search_regs
.num_regs
<= 0)
2425 error ("`replace-match' called before any match found");
2431 CHECK_NUMBER (subexp
);
2432 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2433 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2434 sub
= XINT (subexp
);
2439 if (search_regs
.start
[sub
] < BEGV
2440 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2441 || search_regs
.end
[sub
] > ZV
)
2442 args_out_of_range (make_number (search_regs
.start
[sub
]),
2443 make_number (search_regs
.end
[sub
]));
2447 if (search_regs
.start
[sub
] < 0
2448 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2449 || search_regs
.end
[sub
] > SCHARS (string
))
2450 args_out_of_range (make_number (search_regs
.start
[sub
]),
2451 make_number (search_regs
.end
[sub
]));
2454 if (NILP (fixedcase
))
2456 /* Decide how to casify by examining the matched text. */
2459 pos
= search_regs
.start
[sub
];
2460 last
= search_regs
.end
[sub
];
2463 pos_byte
= CHAR_TO_BYTE (pos
);
2465 pos_byte
= string_char_to_byte (string
, pos
);
2468 case_action
= all_caps
;
2470 /* some_multiletter_word is set nonzero if any original word
2471 is more than one letter long. */
2472 some_multiletter_word
= 0;
2474 some_nonuppercase_initial
= 0;
2481 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2482 INC_BOTH (pos
, pos_byte
);
2485 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2489 /* Cannot be all caps if any original char is lower case */
2492 if (SYNTAX (prevc
) != Sword
)
2493 some_nonuppercase_initial
= 1;
2495 some_multiletter_word
= 1;
2497 else if (uppercasep (c
))
2500 if (SYNTAX (prevc
) != Sword
)
2503 some_multiletter_word
= 1;
2507 /* If the initial is a caseless word constituent,
2508 treat that like a lowercase initial. */
2509 if (SYNTAX (prevc
) != Sword
)
2510 some_nonuppercase_initial
= 1;
2516 /* Convert to all caps if the old text is all caps
2517 and has at least one multiletter word. */
2518 if (! some_lowercase
&& some_multiletter_word
)
2519 case_action
= all_caps
;
2520 /* Capitalize each word, if the old text has all capitalized words. */
2521 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2522 case_action
= cap_initial
;
2523 else if (!some_nonuppercase_initial
&& some_uppercase
)
2524 /* Should x -> yz, operating on X, give Yz or YZ?
2525 We'll assume the latter. */
2526 case_action
= all_caps
;
2528 case_action
= nochange
;
2531 /* Do replacement in a string. */
2534 Lisp_Object before
, after
;
2536 before
= Fsubstring (string
, make_number (0),
2537 make_number (search_regs
.start
[sub
]));
2538 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2540 /* Substitute parts of the match into NEWTEXT
2544 ptrdiff_t lastpos
= 0;
2545 ptrdiff_t lastpos_byte
= 0;
2546 /* We build up the substituted string in ACCUM. */
2549 ptrdiff_t length
= SBYTES (newtext
);
2553 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2555 ptrdiff_t substart
= -1;
2556 ptrdiff_t subend
= 0;
2557 bool delbackslash
= 0;
2559 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2563 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2567 substart
= search_regs
.start
[sub
];
2568 subend
= search_regs
.end
[sub
];
2570 else if (c
>= '1' && c
<= '9')
2572 if (c
- '0' < search_regs
.num_regs
2573 && search_regs
.start
[c
- '0'] >= 0)
2575 substart
= search_regs
.start
[c
- '0'];
2576 subend
= search_regs
.end
[c
- '0'];
2580 /* If that subexp did not match,
2581 replace \\N with nothing. */
2589 error ("Invalid use of `\\' in replacement text");
2593 if (pos
- 2 != lastpos
)
2594 middle
= substring_both (newtext
, lastpos
,
2596 pos
- 2, pos_byte
- 2);
2599 accum
= concat3 (accum
, middle
,
2601 make_number (substart
),
2602 make_number (subend
)));
2604 lastpos_byte
= pos_byte
;
2606 else if (delbackslash
)
2608 middle
= substring_both (newtext
, lastpos
,
2610 pos
- 1, pos_byte
- 1);
2612 accum
= concat2 (accum
, middle
);
2614 lastpos_byte
= pos_byte
;
2619 middle
= substring_both (newtext
, lastpos
,
2625 newtext
= concat2 (accum
, middle
);
2628 /* Do case substitution in NEWTEXT if desired. */
2629 if (case_action
== all_caps
)
2630 newtext
= Fupcase (newtext
);
2631 else if (case_action
== cap_initial
)
2632 newtext
= Fupcase_initials (newtext
);
2634 return concat3 (before
, newtext
, after
);
2637 /* Record point, then move (quietly) to the start of the match. */
2638 if (PT
>= search_regs
.end
[sub
])
2640 else if (PT
> search_regs
.start
[sub
])
2641 opoint
= search_regs
.end
[sub
] - ZV
;
2645 /* If we want non-literal replacement,
2646 perform substitution on the replacement string. */
2649 ptrdiff_t length
= SBYTES (newtext
);
2650 unsigned char *substed
;
2651 ptrdiff_t substed_alloc_size
, substed_len
;
2652 bool buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2653 bool str_multibyte
= STRING_MULTIBYTE (newtext
);
2654 bool really_changed
= 0;
2656 substed_alloc_size
= (length
<= (STRING_BYTES_BOUND
- 100) / 2
2658 : STRING_BYTES_BOUND
);
2659 substed
= xmalloc (substed_alloc_size
);
2662 /* Go thru NEWTEXT, producing the actual text to insert in
2663 SUBSTED while adjusting multibyteness to that of the current
2666 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2668 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2669 const unsigned char *add_stuff
= NULL
;
2670 ptrdiff_t add_len
= 0;
2676 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2678 c
= CHAR_TO_BYTE8 (c
);
2682 /* Note that we don't have to increment POS. */
2683 c
= SREF (newtext
, pos_byte
++);
2685 MAKE_CHAR_MULTIBYTE (c
);
2688 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2689 or set IDX to a match index, which means put that part
2690 of the buffer text into SUBSTED. */
2698 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2700 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2701 c
= CHAR_TO_BYTE8 (c
);
2705 c
= SREF (newtext
, pos_byte
++);
2707 MAKE_CHAR_MULTIBYTE (c
);
2712 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2714 if (search_regs
.start
[c
- '0'] >= 1)
2718 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2722 error ("Invalid use of `\\' in replacement text");
2727 add_len
= CHAR_STRING (c
, str
);
2731 /* If we want to copy part of a previous match,
2732 set up ADD_STUFF and ADD_LEN to point to it. */
2735 begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2736 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2737 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2738 move_gap_both (search_regs
.start
[idx
], begbyte
);
2741 /* Now the stuff we want to add to SUBSTED
2742 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2744 /* Make sure SUBSTED is big enough. */
2745 if (substed_alloc_size
- substed_len
< add_len
)
2747 xpalloc (substed
, &substed_alloc_size
,
2748 add_len
- (substed_alloc_size
- substed_len
),
2749 STRING_BYTES_BOUND
, 1);
2751 /* We compute this after the call to xpalloc, because that
2752 could cause buffer text be relocated when ralloc.c is used. */
2754 add_stuff
= BYTE_POS_ADDR (begbyte
);
2756 /* Now add to the end of SUBSTED. */
2759 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2760 substed_len
+= add_len
;
2765 newtext
= make_specified_string ((const char *) substed
, -1,
2766 substed_len
, buf_multibyte
);
2770 /* The functions below modify the buffer, so they could trigger
2771 various modification hooks (see signal_before_change and
2772 signal_after_change). If these hooks clobber the match data we
2773 error out since otherwise this will result in confusing bugs. */
2774 ptrdiff_t sub_start
= search_regs
.start
[sub
];
2775 ptrdiff_t sub_end
= search_regs
.end
[sub
];
2776 unsigned num_regs
= search_regs
.num_regs
;
2777 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2779 /* Replace the old text with the new in the cleanest possible way. */
2780 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2781 newtext
, 1, 0, 1, 1);
2782 /* Update saved data to match adjustment made by replace_range. */
2784 ptrdiff_t change
= newpoint
- sub_end
;
2785 if (sub_start
>= sub_end
)
2786 sub_start
+= change
;
2790 if (case_action
== all_caps
)
2791 Fupcase_region (make_number (search_regs
.start
[sub
]),
2792 make_number (newpoint
));
2793 else if (case_action
== cap_initial
)
2794 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2795 make_number (newpoint
));
2797 if (search_regs
.start
[sub
] != sub_start
2798 || search_regs
.end
[sub
] != sub_end
2799 || search_regs
.num_regs
!= num_regs
)
2800 error ("Match data clobbered by buffer modification hooks");
2802 /* Put point back where it was in the text. */
2804 TEMP_SET_PT (opoint
+ ZV
);
2806 TEMP_SET_PT (opoint
);
2808 /* Now move point "officially" to the start of the inserted replacement. */
2809 move_if_not_intangible (newpoint
);
2815 match_limit (Lisp_Object num
, bool beginningp
)
2822 args_out_of_range (num
, make_number (0));
2823 if (search_regs
.num_regs
<= 0)
2824 error ("No match data, because no search succeeded");
2825 if (n
>= search_regs
.num_regs
2826 || search_regs
.start
[n
] < 0)
2828 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2829 : search_regs
.end
[n
]));
2832 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2833 doc
: /* Return position of start of text matched by last search.
2834 SUBEXP, a number, specifies which parenthesized expression in the last
2836 Value is nil if SUBEXPth pair didn't match, or there were less than
2838 Zero means the entire text matched by the whole regexp or whole string.
2840 Return value is undefined if the last search failed. */)
2841 (Lisp_Object subexp
)
2843 return match_limit (subexp
, 1);
2846 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2847 doc
: /* Return position of end of text matched by last search.
2848 SUBEXP, a number, specifies which parenthesized expression in the last
2850 Value is nil if SUBEXPth pair didn't match, or there were less than
2852 Zero means the entire text matched by the whole regexp or whole string.
2854 Return value is undefined if the last search failed. */)
2855 (Lisp_Object subexp
)
2857 return match_limit (subexp
, 0);
2860 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2861 doc
: /* Return a list describing what the last search matched.
2862 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2863 All the elements are markers or nil (nil if the Nth pair didn't match)
2864 if the last match was on a buffer; integers or nil if a string was matched.
2865 Use `set-match-data' to reinstate the data in this list.
2867 If INTEGERS (the optional first argument) is non-nil, always use
2868 integers (rather than markers) to represent buffer positions. In
2869 this case, and if the last match was in a buffer, the buffer will get
2870 stored as one additional element at the end of the list.
2872 If REUSE is a list, reuse it as part of the value. If REUSE is long
2873 enough to hold all the values, and if INTEGERS is non-nil, no consing
2876 If optional third arg RESEAT is non-nil, any previous markers on the
2877 REUSE list will be modified to point to nowhere.
2879 Return value is undefined if the last search failed. */)
2880 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2882 Lisp_Object tail
, prev
;
2887 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2888 if (MARKERP (XCAR (tail
)))
2890 unchain_marker (XMARKER (XCAR (tail
)));
2891 XSETCAR (tail
, Qnil
);
2894 if (NILP (last_thing_searched
))
2900 SAFE_NALLOCA (data
, 1, 2 * search_regs
.num_regs
+ 1);
2903 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2905 ptrdiff_t start
= search_regs
.start
[i
];
2908 if (EQ (last_thing_searched
, Qt
)
2909 || ! NILP (integers
))
2911 XSETFASTINT (data
[2 * i
], start
);
2912 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2914 else if (BUFFERP (last_thing_searched
))
2916 data
[2 * i
] = Fmake_marker ();
2917 Fset_marker (data
[2 * i
],
2918 make_number (start
),
2919 last_thing_searched
);
2920 data
[2 * i
+ 1] = Fmake_marker ();
2921 Fset_marker (data
[2 * i
+ 1],
2922 make_number (search_regs
.end
[i
]),
2923 last_thing_searched
);
2926 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2932 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2935 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2937 data
[len
] = last_thing_searched
;
2941 /* If REUSE is not usable, cons up the values and return them. */
2942 if (! CONSP (reuse
))
2943 reuse
= Flist (len
, data
);
2946 /* If REUSE is a list, store as many value elements as will fit
2947 into the elements of REUSE. */
2948 for (i
= 0, tail
= reuse
; CONSP (tail
);
2949 i
++, tail
= XCDR (tail
))
2952 XSETCAR (tail
, data
[i
]);
2954 XSETCAR (tail
, Qnil
);
2958 /* If we couldn't fit all value elements into REUSE,
2959 cons up the rest of them and add them to the end of REUSE. */
2961 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2968 /* We used to have an internal use variant of `reseat' described as:
2970 If RESEAT is `evaporate', put the markers back on the free list
2971 immediately. No other references to the markers must exist in this
2972 case, so it is used only internally on the unwind stack and
2973 save-match-data from Lisp.
2975 But it was ill-conceived: those supposedly-internal markers get exposed via
2976 the undo-list, so freeing them here is unsafe. */
2978 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2979 doc
: /* Set internal data on last search match from elements of LIST.
2980 LIST should have been created by calling `match-data' previously.
2982 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2983 (register Lisp_Object list
, Lisp_Object reseat
)
2986 register Lisp_Object marker
;
2988 if (running_asynch_code
)
2989 save_search_regs ();
2993 /* Unless we find a marker with a buffer or an explicit buffer
2994 in LIST, assume that this match data came from a string. */
2995 last_thing_searched
= Qt
;
2997 /* Allocate registers if they don't already exist. */
2999 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
3001 if (length
> search_regs
.num_regs
)
3003 ptrdiff_t num_regs
= search_regs
.num_regs
;
3004 if (PTRDIFF_MAX
< length
)
3005 memory_full (SIZE_MAX
);
3007 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
3008 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
3010 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
3012 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
3013 search_regs
.start
[i
] = -1;
3015 search_regs
.num_regs
= num_regs
;
3018 for (i
= 0; CONSP (list
); i
++)
3020 marker
= XCAR (list
);
3021 if (BUFFERP (marker
))
3023 last_thing_searched
= marker
;
3030 search_regs
.start
[i
] = -1;
3039 if (MARKERP (marker
))
3041 if (XMARKER (marker
)->buffer
== 0)
3042 XSETFASTINT (marker
, 0);
3044 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
3047 CHECK_NUMBER_COERCE_MARKER (marker
);
3050 if (!NILP (reseat
) && MARKERP (m
))
3052 unchain_marker (XMARKER (m
));
3053 XSETCAR (list
, Qnil
);
3056 if ((list
= XCDR (list
), !CONSP (list
)))
3059 m
= marker
= XCAR (list
);
3061 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
3062 XSETFASTINT (marker
, 0);
3064 CHECK_NUMBER_COERCE_MARKER (marker
);
3065 if ((XINT (from
) < 0
3066 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
3067 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
3068 && (XINT (marker
) < 0
3069 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
3070 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
3072 search_regs
.start
[i
] = XINT (from
);
3073 search_regs
.end
[i
] = XINT (marker
);
3077 search_regs
.start
[i
] = -1;
3080 if (!NILP (reseat
) && MARKERP (m
))
3082 unchain_marker (XMARKER (m
));
3083 XSETCAR (list
, Qnil
);
3089 for (; i
< search_regs
.num_regs
; i
++)
3090 search_regs
.start
[i
] = -1;
3096 /* If true the match data have been saved in saved_search_regs
3097 during the execution of a sentinel or filter. */
3098 static bool search_regs_saved
;
3099 static struct re_registers saved_search_regs
;
3100 static Lisp_Object saved_last_thing_searched
;
3102 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3103 if asynchronous code (filter or sentinel) is running. */
3105 save_search_regs (void)
3107 if (!search_regs_saved
)
3109 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3110 saved_search_regs
.start
= search_regs
.start
;
3111 saved_search_regs
.end
= search_regs
.end
;
3112 saved_last_thing_searched
= last_thing_searched
;
3113 last_thing_searched
= Qnil
;
3114 search_regs
.num_regs
= 0;
3115 search_regs
.start
= 0;
3116 search_regs
.end
= 0;
3118 search_regs_saved
= 1;
3122 /* Called upon exit from filters and sentinels. */
3124 restore_search_regs (void)
3126 if (search_regs_saved
)
3128 if (search_regs
.num_regs
> 0)
3130 xfree (search_regs
.start
);
3131 xfree (search_regs
.end
);
3133 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3134 search_regs
.start
= saved_search_regs
.start
;
3135 search_regs
.end
= saved_search_regs
.end
;
3136 last_thing_searched
= saved_last_thing_searched
;
3137 saved_last_thing_searched
= Qnil
;
3138 search_regs_saved
= 0;
3142 /* Called from replace-match via replace_range. */
3144 update_search_regs (ptrdiff_t oldstart
, ptrdiff_t oldend
, ptrdiff_t newend
)
3146 /* Adjust search data for this change. */
3147 ptrdiff_t change
= newend
- oldend
;
3150 for (i
= 0; i
< search_regs
.num_regs
; i
++)
3152 if (search_regs
.start
[i
] >= oldend
)
3153 search_regs
.start
[i
] += change
;
3154 else if (search_regs
.start
[i
] > oldstart
)
3155 search_regs
.start
[i
] = oldstart
;
3156 if (search_regs
.end
[i
] >= oldend
)
3157 search_regs
.end
[i
] += change
;
3158 else if (search_regs
.end
[i
] > oldstart
)
3159 search_regs
.end
[i
] = oldstart
;
3164 unwind_set_match_data (Lisp_Object list
)
3166 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3167 Fset_match_data (list
, Qt
);
3170 /* Called to unwind protect the match data. */
3172 record_unwind_save_match_data (void)
3174 record_unwind_protect (unwind_set_match_data
,
3175 Fmatch_data (Qnil
, Qnil
, Qnil
));
3178 /* Quote a string to deactivate reg-expr chars */
3180 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3181 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3182 (Lisp_Object string
)
3184 char *in
, *out
, *end
;
3186 ptrdiff_t backslashes_added
= 0;
3188 CHECK_STRING (string
);
3191 SAFE_NALLOCA (temp
, 2, SBYTES (string
));
3193 /* Now copy the data into the new string, inserting escapes. */
3195 in
= SSDATA (string
);
3196 end
= in
+ SBYTES (string
);
3199 for (; in
!= end
; in
++)
3202 || *in
== '*' || *in
== '.' || *in
== '\\'
3203 || *in
== '?' || *in
== '+'
3204 || *in
== '^' || *in
== '$')
3205 *out
++ = '\\', backslashes_added
++;
3210 = make_specified_string (temp
,
3211 SCHARS (string
) + backslashes_added
,
3213 STRING_MULTIBYTE (string
));
3218 /* Like find_newline, but doesn't use the cache, and only searches forward. */
3220 find_newline1 (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
3221 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
3222 ptrdiff_t *bytepos
, bool allow_quit
)
3227 end
= ZV
, end_byte
= ZV_BYTE
;
3232 end
= BEGV
, end_byte
= BEGV_BYTE
;
3235 end_byte
= CHAR_TO_BYTE (end
);
3240 immediate_quit
= allow_quit
;
3243 while (start
!= end
)
3245 /* Our innermost scanning loop is very simple; it doesn't know
3246 about gaps, buffer ends, or the newline cache. ceiling is
3247 the position of the last character before the next such
3248 obstacle --- the last character the dumb search loop should
3250 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
3252 if (start_byte
== -1)
3253 start_byte
= CHAR_TO_BYTE (start
);
3255 /* The dumb loop can only scan text stored in contiguous
3256 bytes. BUFFER_CEILING_OF returns the last character
3257 position that is contiguous, so the ceiling is the
3258 position after that. */
3259 tem
= BUFFER_CEILING_OF (start_byte
);
3260 ceiling_byte
= min (tem
, ceiling_byte
);
3263 /* The termination address of the dumb loop. */
3264 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
3265 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
3267 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
3268 of the base, the cursor, and the next line. */
3269 ptrdiff_t base
= start_byte
- lim_byte
;
3270 ptrdiff_t cursor
, next
;
3272 for (cursor
= base
; cursor
< 0; cursor
= next
)
3274 /* The dumb loop. */
3275 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
3276 next
= nl
? nl
- lim_addr
: 0;
3286 *bytepos
= lim_byte
+ next
;
3287 return BYTE_TO_CHAR (lim_byte
+ next
);
3291 start_byte
= lim_byte
;
3292 start
= BYTE_TO_CHAR (start_byte
);
3301 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
3302 eassert (*bytepos
== CHAR_TO_BYTE (start
));
3307 DEFUN ("newline-cache-check", Fnewline_cache_check
, Snewline_cache_check
,
3309 doc
: /* Check the newline cache of BUFFER against buffer contents.
3311 BUFFER defaults to the current buffer.
3313 Value is an array of 2 sub-arrays of buffer positions for newlines,
3314 the first based on the cache, the second based on actually scanning
3315 the buffer. If the buffer doesn't have a cache, the value is nil. */)
3316 (Lisp_Object buffer
)
3318 struct buffer
*buf
, *old
= NULL
;
3319 ptrdiff_t shortage
, nl_count_cache
, nl_count_buf
;
3320 Lisp_Object cache_newlines
, buf_newlines
, val
;
3321 ptrdiff_t from
, found
, i
;
3324 buf
= current_buffer
;
3327 CHECK_BUFFER (buffer
);
3328 buf
= XBUFFER (buffer
);
3329 old
= current_buffer
;
3331 if (buf
->base_buffer
)
3332 buf
= buf
->base_buffer
;
3334 /* If the buffer doesn't have a newline cache, return nil. */
3335 if (NILP (BVAR (buf
, cache_long_scans
))
3336 || buf
->newline_cache
== NULL
)
3339 /* find_newline can only work on the current buffer. */
3341 set_buffer_internal_1 (buf
);
3343 /* How many newlines are there according to the cache? */
3344 find_newline (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3345 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3346 nl_count_cache
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3348 /* Create vector and populate it. */
3349 cache_newlines
= make_uninit_vector (nl_count_cache
);
3353 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3355 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3357 found
= find_newline (from
, from_byte
, 0, -1, 1, &shortage
,
3359 if (shortage
!= 0 || i
>= nl_count_cache
)
3361 ASET (cache_newlines
, i
, make_number (found
- 1));
3363 /* Fill the rest of slots with an invalid position. */
3364 for ( ; i
< nl_count_cache
; i
++)
3365 ASET (cache_newlines
, i
, make_number (-1));
3368 /* Now do the same, but without using the cache. */
3369 find_newline1 (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3370 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3371 nl_count_buf
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3372 buf_newlines
= make_uninit_vector (nl_count_buf
);
3375 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3377 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3379 found
= find_newline1 (from
, from_byte
, 0, -1, 1, &shortage
,
3381 if (shortage
!= 0 || i
>= nl_count_buf
)
3383 ASET (buf_newlines
, i
, make_number (found
- 1));
3385 for ( ; i
< nl_count_buf
; i
++)
3386 ASET (buf_newlines
, i
, make_number (-1));
3389 /* Construct the value and return it. */
3390 val
= make_uninit_vector (2);
3391 ASET (val
, 0, cache_newlines
);
3392 ASET (val
, 1, buf_newlines
);
3395 set_buffer_internal_1 (old
);
3400 syms_of_search (void)
3404 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3406 searchbufs
[i
].buf
.allocated
= 100;
3407 searchbufs
[i
].buf
.buffer
= xmalloc (100);
3408 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3409 searchbufs
[i
].regexp
= Qnil
;
3410 searchbufs
[i
].whitespace_regexp
= Qnil
;
3411 searchbufs
[i
].syntax_table
= Qnil
;
3412 staticpro (&searchbufs
[i
].regexp
);
3413 staticpro (&searchbufs
[i
].whitespace_regexp
);
3414 staticpro (&searchbufs
[i
].syntax_table
);
3415 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3417 searchbuf_head
= &searchbufs
[0];
3419 /* Error condition used for failing searches. */
3420 DEFSYM (Qsearch_failed
, "search-failed");
3422 /* Error condition signaled when regexp compile_pattern fails. */
3423 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3425 Fput (Qsearch_failed
, Qerror_conditions
,
3426 listn (CONSTYPE_PURE
, 2, Qsearch_failed
, Qerror
));
3427 Fput (Qsearch_failed
, Qerror_message
,
3428 build_pure_c_string ("Search failed"));
3430 Fput (Qinvalid_regexp
, Qerror_conditions
,
3431 listn (CONSTYPE_PURE
, 2, Qinvalid_regexp
, Qerror
));
3432 Fput (Qinvalid_regexp
, Qerror_message
,
3433 build_pure_c_string ("Invalid regexp"));
3435 last_thing_searched
= Qnil
;
3436 staticpro (&last_thing_searched
);
3438 saved_last_thing_searched
= Qnil
;
3439 staticpro (&saved_last_thing_searched
);
3441 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3442 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3443 Some commands use this for user-specified regexps.
3444 Spaces that occur inside character classes or repetition operators
3445 or other such regexp constructs are not replaced with this.
3446 A value of nil (which is the normal value) means treat spaces literally. */);
3447 Vsearch_spaces_regexp
= Qnil
;
3449 DEFSYM (Qinhibit_changing_match_data
, "inhibit-changing-match-data");
3450 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3451 doc
: /* Internal use only.
3452 If non-nil, the primitive searching and matching functions
3453 such as `looking-at', `string-match', `re-search-forward', etc.,
3454 do not set the match data. The proper way to use this variable
3455 is to bind it with `let' around a small expression. */);
3456 Vinhibit_changing_match_data
= Qnil
;
3458 defsubr (&Slooking_at
);
3459 defsubr (&Sposix_looking_at
);
3460 defsubr (&Sstring_match
);
3461 defsubr (&Sposix_string_match
);
3462 defsubr (&Ssearch_forward
);
3463 defsubr (&Ssearch_backward
);
3464 defsubr (&Sre_search_forward
);
3465 defsubr (&Sre_search_backward
);
3466 defsubr (&Sposix_search_forward
);
3467 defsubr (&Sposix_search_backward
);
3468 defsubr (&Sreplace_match
);
3469 defsubr (&Smatch_beginning
);
3470 defsubr (&Smatch_end
);
3471 defsubr (&Smatch_data
);
3472 defsubr (&Sset_match_data
);
3473 defsubr (&Sregexp_quote
);
3474 defsubr (&Snewline_cache_check
);