1 /* String search routines for GNU Emacs.
3 Copyright (C) 1985-1987, 1993-1994, 1997-1999, 2001-2016 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"
35 #define REGEXP_CACHE_SIZE 20
37 /* If the regexp is non-nil, then the buffer contains the compiled form
38 of that regexp, suitable for searching. */
41 struct regexp_cache
*next
;
42 Lisp_Object regexp
, f_whitespace_regexp
;
43 /* Syntax table for which the regexp applies. We need this because
44 of character classes. If this is t, then the compiled pattern is valid
45 for any syntax-table. */
46 Lisp_Object syntax_table
;
47 struct re_pattern_buffer buf
;
49 /* True means regexp was compiled to do full POSIX backtracking. */
53 /* The instances of that struct. */
54 static struct regexp_cache searchbufs
[REGEXP_CACHE_SIZE
];
56 /* The head of the linked list; points to the most recently used buffer. */
57 static struct regexp_cache
*searchbuf_head
;
60 /* Every call to re_match, etc., must pass &search_regs as the regs
61 argument unless you can show it is unnecessary (i.e., if re_match
62 is certainly going to be called again before region-around-match
65 Since the registers are now dynamically allocated, we need to make
66 sure not to refer to the Nth register before checking that it has
67 been allocated by checking search_regs.num_regs.
69 The regex code keeps track of whether it has allocated the search
70 buffer using bits in the re_pattern_buffer. This means that whenever
71 you compile a new pattern, it completely forgets whether it has
72 allocated any registers, and will allocate new registers the next
73 time you call a searching or matching function. Therefore, we need
74 to call re_set_registers after compiling a new pattern or after
75 setting the match registers, so that the regex functions will be
76 able to free or re-allocate it properly. */
77 /* static struct re_registers search_regs; */
79 /* The buffer in which the last search was performed, or
80 Qt if the last search was done in a string;
81 Qnil if no searching has been done yet. */
82 /* static Lisp_Object last_thing_searched; */
84 static void set_search_regs (ptrdiff_t, ptrdiff_t);
85 static void save_search_regs (void);
86 static EMACS_INT
simple_search (EMACS_INT
, unsigned char *, ptrdiff_t,
87 ptrdiff_t, Lisp_Object
, ptrdiff_t, ptrdiff_t,
88 ptrdiff_t, ptrdiff_t);
89 static EMACS_INT
boyer_moore (EMACS_INT
, unsigned char *, ptrdiff_t,
90 Lisp_Object
, Lisp_Object
, ptrdiff_t,
92 static EMACS_INT
search_buffer (Lisp_Object
, ptrdiff_t, ptrdiff_t,
93 ptrdiff_t, ptrdiff_t, EMACS_INT
, int,
94 Lisp_Object
, Lisp_Object
, bool);
97 matcher_overflow (void)
99 error ("Stack overflow in regexp matcher");
102 /* Compile a regexp and signal a Lisp error if anything goes wrong.
103 PATTERN is the pattern to compile.
104 CP is the place to put the result.
105 TRANSLATE is a translation table for ignoring case, or nil for none.
106 POSIX is true if we want full backtracking (POSIX style) for this pattern.
107 False means backtrack only enough to get a valid match.
109 The behavior also depends on Vsearch_spaces_regexp. */
112 compile_pattern_1 (struct regexp_cache
*cp
, Lisp_Object pattern
,
113 Lisp_Object translate
, bool posix
)
115 const char *whitespace_regexp
;
119 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
121 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
122 cp
->buf
.charset_unibyte
= charset_unibyte
;
123 if (STRINGP (Vsearch_spaces_regexp
))
124 cp
->f_whitespace_regexp
= Vsearch_spaces_regexp
;
126 cp
->f_whitespace_regexp
= Qnil
;
128 /* rms: I think BLOCK_INPUT is not needed here any more,
129 because regex.c defines malloc to call xmalloc.
130 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
131 So let's turn it off. */
134 whitespace_regexp
= STRINGP (Vsearch_spaces_regexp
) ?
135 SSDATA (Vsearch_spaces_regexp
) : NULL
;
137 val
= (char *) re_compile_pattern (SSDATA (pattern
), SBYTES (pattern
),
138 posix
, whitespace_regexp
, &cp
->buf
);
140 /* If the compiled pattern hard codes some of the contents of the
141 syntax-table, it can only be reused with *this* syntax table. */
142 cp
->syntax_table
= cp
->buf
.used_syntax
? BVAR (current_buffer
, syntax_table
) : Qt
;
144 /* unblock_input (); */
146 xsignal1 (Qinvalid_regexp
, build_string (val
));
148 cp
->regexp
= Fcopy_sequence (pattern
);
151 /* Shrink each compiled regexp buffer in the cache
152 to the size actually used right now.
153 This is called from garbage collection. */
156 shrink_regexp_cache (void)
158 struct regexp_cache
*cp
;
160 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
162 cp
->buf
.allocated
= cp
->buf
.used
;
163 cp
->buf
.buffer
= xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
167 /* Clear the regexp cache w.r.t. a particular syntax table,
168 because it was changed.
169 There is no danger of memory leak here because re_compile_pattern
170 automagically manages the memory in each re_pattern_buffer struct,
171 based on its `allocated' and `buffer' values. */
173 clear_regexp_cache (void)
177 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
178 /* It's tempting to compare with the syntax-table we've actually changed,
179 but it's not sufficient because char-table inheritance means that
180 modifying one syntax-table can change others at the same time. */
181 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
182 searchbufs
[i
].regexp
= Qnil
;
185 /* Compile a regexp if necessary, but first check to see if there's one in
187 PATTERN is the pattern to compile.
188 TRANSLATE is a translation table for ignoring case, or nil for none.
189 REGP is the structure that says where to store the "register"
190 values that will result from matching this pattern.
191 If it is 0, we should compile the pattern not to record any
192 subexpression bounds.
193 POSIX is true if we want full backtracking (POSIX style) for this pattern.
194 False means backtrack only enough to get a valid match. */
196 struct re_pattern_buffer
*
197 compile_pattern (Lisp_Object pattern
, struct re_registers
*regp
,
198 Lisp_Object translate
, bool posix
, bool multibyte
)
200 struct regexp_cache
*cp
, **cpp
;
202 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
205 /* Entries are initialized to nil, and may be set to nil by
206 compile_pattern_1 if the pattern isn't valid. Don't apply
207 string accessors in those cases. However, compile_pattern_1
208 is only applied to the cache entry we pick here to reuse. So
209 nil should never appear before a non-nil entry. */
210 if (NILP (cp
->regexp
))
212 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
213 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
214 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
215 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
216 && cp
->posix
== posix
217 && (EQ (cp
->syntax_table
, Qt
)
218 || EQ (cp
->syntax_table
, BVAR (current_buffer
, syntax_table
)))
219 && !NILP (Fequal (cp
->f_whitespace_regexp
, Vsearch_spaces_regexp
))
220 && cp
->buf
.charset_unibyte
== charset_unibyte
)
223 /* If we're at the end of the cache, compile into the nil cell
224 we found, or the last (least recently used) cell with a
229 compile_pattern_1 (cp
, pattern
, translate
, posix
);
234 /* When we get here, cp (aka *cpp) contains the compiled pattern,
235 either because we found it in the cache or because we just compiled it.
236 Move it to the front of the queue to mark it as most recently used. */
238 cp
->next
= searchbuf_head
;
241 /* Advise the searching functions about the space we have allocated
242 for register data. */
244 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
246 /* The compiled pattern can be used both for multibyte and unibyte
247 target. But, we have to tell which the pattern is used for. */
248 cp
->buf
.target_multibyte
= multibyte
;
255 looking_at_1 (Lisp_Object string
, bool posix
)
258 unsigned char *p1
, *p2
;
260 register ptrdiff_t i
;
261 struct re_pattern_buffer
*bufp
;
263 if (running_asynch_code
)
266 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
267 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
268 BVAR (current_buffer
, case_eqv_table
));
270 CHECK_STRING (string
);
271 bufp
= compile_pattern (string
,
272 (NILP (Vinhibit_changing_match_data
)
273 ? &search_regs
: NULL
),
274 (!NILP (BVAR (current_buffer
, case_fold_search
))
275 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
277 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
280 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
282 /* Get pointers and sizes of the two strings
283 that make up the visible portion of the buffer. */
286 s1
= GPT_BYTE
- BEGV_BYTE
;
288 s2
= ZV_BYTE
- GPT_BYTE
;
292 s2
= ZV_BYTE
- BEGV_BYTE
;
297 s1
= ZV_BYTE
- BEGV_BYTE
;
301 re_match_object
= Qnil
;
304 /* Prevent ralloc.c from relocating the current buffer while
306 r_alloc_inhibit_buffer_relocation (1);
308 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
310 (NILP (Vinhibit_changing_match_data
)
311 ? &search_regs
: NULL
),
312 ZV_BYTE
- BEGV_BYTE
);
315 r_alloc_inhibit_buffer_relocation (0);
321 val
= (i
>= 0 ? Qt
: Qnil
);
322 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
324 for (i
= 0; i
< search_regs
.num_regs
; i
++)
325 if (search_regs
.start
[i
] >= 0)
328 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
330 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
332 /* Set last_thing_searched only when match data is changed. */
333 XSETBUFFER (last_thing_searched
, current_buffer
);
339 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
340 doc
: /* Return t if text after point matches regular expression REGEXP.
341 This function modifies the match data that `match-beginning',
342 `match-end' and `match-data' access; save and restore the match
343 data if you want to preserve them. */)
346 return looking_at_1 (regexp
, 0);
349 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
350 doc
: /* Return t if text after point matches regular expression REGEXP.
351 Find the longest match, in accord with Posix regular expression rules.
352 This function modifies the match data that `match-beginning',
353 `match-end' and `match-data' access; save and restore the match
354 data if you want to preserve them. */)
357 return looking_at_1 (regexp
, 1);
361 string_match_1 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
,
365 struct re_pattern_buffer
*bufp
;
367 ptrdiff_t pos_byte
, i
;
369 if (running_asynch_code
)
372 CHECK_STRING (regexp
);
373 CHECK_STRING (string
);
376 pos
= 0, pos_byte
= 0;
379 ptrdiff_t len
= SCHARS (string
);
381 CHECK_NUMBER (start
);
383 if (pos
< 0 && -pos
<= len
)
385 else if (0 > pos
|| pos
> len
)
386 args_out_of_range (string
, start
);
387 pos_byte
= string_char_to_byte (string
, pos
);
390 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
391 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
392 BVAR (current_buffer
, case_eqv_table
));
394 bufp
= compile_pattern (regexp
,
395 (NILP (Vinhibit_changing_match_data
)
396 ? &search_regs
: NULL
),
397 (!NILP (BVAR (current_buffer
, case_fold_search
))
398 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
400 STRING_MULTIBYTE (string
));
402 re_match_object
= string
;
404 val
= re_search (bufp
, SSDATA (string
),
405 SBYTES (string
), pos_byte
,
406 SBYTES (string
) - pos_byte
,
407 (NILP (Vinhibit_changing_match_data
)
408 ? &search_regs
: NULL
));
411 /* Set last_thing_searched only when match data is changed. */
412 if (NILP (Vinhibit_changing_match_data
))
413 last_thing_searched
= Qt
;
417 if (val
< 0) return Qnil
;
419 if (NILP (Vinhibit_changing_match_data
))
420 for (i
= 0; i
< search_regs
.num_regs
; i
++)
421 if (search_regs
.start
[i
] >= 0)
424 = string_byte_to_char (string
, search_regs
.start
[i
]);
426 = string_byte_to_char (string
, search_regs
.end
[i
]);
429 return make_number (string_byte_to_char (string
, val
));
432 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
433 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
434 Matching ignores case if `case-fold-search' is non-nil.
435 If third arg START is non-nil, start search at that index in STRING.
436 For index of first char beyond the match, do (match-end 0).
437 `match-end' and `match-beginning' also give indices of substrings
438 matched by parenthesis constructs in the pattern.
440 You can use the function `match-string' to extract the substrings
441 matched by the parenthesis constructions in REGEXP. */)
442 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
444 return string_match_1 (regexp
, string
, start
, 0);
447 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
448 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
449 Find the longest match, in accord with Posix regular expression rules.
450 Case is ignored if `case-fold-search' is non-nil in the current buffer.
451 If third arg START is non-nil, start search at that index in STRING.
452 For index of first char beyond the match, do (match-end 0).
453 `match-end' and `match-beginning' also give indices of substrings
454 matched by parenthesis constructs in the pattern. */)
455 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
457 return string_match_1 (regexp
, string
, start
, 1);
460 /* Match REGEXP against STRING using translation table TABLE,
461 searching all of STRING, and return the index of the match,
462 or negative on failure. This does not clobber the match data. */
465 fast_string_match_internal (Lisp_Object regexp
, Lisp_Object string
,
469 struct re_pattern_buffer
*bufp
;
471 bufp
= compile_pattern (regexp
, 0, table
,
472 0, STRING_MULTIBYTE (string
));
474 re_match_object
= string
;
476 val
= re_search (bufp
, SSDATA (string
),
483 /* Match REGEXP against STRING, searching all of STRING ignoring case,
484 and return the index of the match, or negative on failure.
485 This does not clobber the match data.
486 We assume that STRING contains single-byte characters. */
489 fast_c_string_match_ignore_case (Lisp_Object regexp
,
490 const char *string
, ptrdiff_t len
)
493 struct re_pattern_buffer
*bufp
;
495 regexp
= string_make_unibyte (regexp
);
496 re_match_object
= Qt
;
497 bufp
= compile_pattern (regexp
, 0,
498 Vascii_canon_table
, 0,
501 val
= re_search (bufp
, string
, len
, 0, len
, 0);
506 /* Match REGEXP against the characters after POS to LIMIT, and return
507 the number of matched characters. If STRING is non-nil, match
508 against the characters in it. In that case, POS and LIMIT are
509 indices into the string. This function doesn't modify the match
513 fast_looking_at (Lisp_Object regexp
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
514 ptrdiff_t limit
, ptrdiff_t limit_byte
, Lisp_Object string
)
517 struct re_pattern_buffer
*buf
;
518 unsigned char *p1
, *p2
;
522 if (STRINGP (string
))
525 pos_byte
= string_char_to_byte (string
, pos
);
527 limit_byte
= string_char_to_byte (string
, limit
);
531 s2
= SBYTES (string
);
532 re_match_object
= string
;
533 multibyte
= STRING_MULTIBYTE (string
);
538 pos_byte
= CHAR_TO_BYTE (pos
);
540 limit_byte
= CHAR_TO_BYTE (limit
);
541 pos_byte
-= BEGV_BYTE
;
542 limit_byte
-= BEGV_BYTE
;
544 s1
= GPT_BYTE
- BEGV_BYTE
;
546 s2
= ZV_BYTE
- GPT_BYTE
;
550 s2
= ZV_BYTE
- BEGV_BYTE
;
555 s1
= ZV_BYTE
- BEGV_BYTE
;
558 re_match_object
= Qnil
;
559 multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
562 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
565 /* Prevent ralloc.c from relocating the current buffer while
567 r_alloc_inhibit_buffer_relocation (1);
569 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
570 pos_byte
, NULL
, limit_byte
);
572 r_alloc_inhibit_buffer_relocation (0);
580 /* The newline cache: remembering which sections of text have no newlines. */
582 /* If the user has requested the long scans caching, make sure it's on.
583 Otherwise, make sure it's off.
584 This is our cheezy way of associating an action with the change of
585 state of a buffer-local variable. */
586 static struct region_cache
*
587 newline_cache_on_off (struct buffer
*buf
)
589 struct buffer
*base_buf
= buf
;
590 bool indirect_p
= false;
592 if (buf
->base_buffer
)
594 base_buf
= buf
->base_buffer
;
598 /* Don't turn on or off the cache in the base buffer, if the value
599 of cache-long-scans of the base buffer is inconsistent with that.
600 This is because doing so will just make the cache pure overhead,
601 since if we turn it on via indirect buffer, it will be
602 immediately turned off by its base buffer. */
603 if (NILP (BVAR (buf
, cache_long_scans
)))
606 || NILP (BVAR (base_buf
, cache_long_scans
)))
608 /* It should be off. */
609 if (base_buf
->newline_cache
)
611 free_region_cache (base_buf
->newline_cache
);
612 base_buf
->newline_cache
= 0;
620 || !NILP (BVAR (base_buf
, cache_long_scans
)))
622 /* It should be on. */
623 if (base_buf
->newline_cache
== 0)
624 base_buf
->newline_cache
= new_region_cache ();
626 return base_buf
->newline_cache
;
631 /* Search for COUNT newlines between START/START_BYTE and END/END_BYTE.
633 If COUNT is positive, search forwards; END must be >= START.
634 If COUNT is negative, search backwards for the -COUNTth instance;
635 END must be <= START.
636 If COUNT is zero, do anything you please; run rogue, for all I care.
638 If END is zero, use BEGV or ZV instead, as appropriate for the
639 direction indicated by COUNT.
641 If we find COUNT instances, set *SHORTAGE to zero, and return the
642 position past the COUNTth match. Note that for reverse motion
643 this is not the same as the usual convention for Emacs motion commands.
645 If we don't find COUNT instances before reaching END, set *SHORTAGE
646 to the number of newlines left unfound, and return END.
648 If BYTEPOS is not NULL, set *BYTEPOS to the byte position corresponding
649 to the returned character position.
651 If ALLOW_QUIT, set immediate_quit. That's good to do
652 except when inside redisplay. */
655 find_newline (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
656 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
657 ptrdiff_t *bytepos
, bool allow_quit
)
659 struct region_cache
*newline_cache
;
661 struct buffer
*cache_buffer
;
667 end
= ZV
, end_byte
= ZV_BYTE
;
673 end
= BEGV
, end_byte
= BEGV_BYTE
;
676 end_byte
= CHAR_TO_BYTE (end
);
678 newline_cache
= newline_cache_on_off (current_buffer
);
679 if (current_buffer
->base_buffer
)
680 cache_buffer
= current_buffer
->base_buffer
;
682 cache_buffer
= current_buffer
;
687 immediate_quit
= allow_quit
;
692 /* Our innermost scanning loop is very simple; it doesn't know
693 about gaps, buffer ends, or the newline cache. ceiling is
694 the position of the last character before the next such
695 obstacle --- the last character the dumb search loop should
697 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
699 /* If we're using the newline cache, consult it to see whether
700 we can avoid some scanning. */
703 ptrdiff_t next_change
;
707 while (start
< end
&& result
)
711 result
= region_cache_forward (cache_buffer
, newline_cache
,
712 start
, &next_change
);
715 /* When the cache revalidation is deferred,
716 next-change might point beyond ZV, which will
717 cause assertion violation in CHAR_TO_BYTE below.
718 Limit next_change to ZV to avoid that. */
719 if (next_change
> ZV
)
722 lim1
= next_change
= end
;
725 lim1
= min (next_change
, end
);
727 /* The cache returned zero for this region; see if
728 this is because the region is known and includes
729 only newlines. While at that, count any newlines
730 we bump into, and exit if we found enough off them. */
731 start_byte
= CHAR_TO_BYTE (start
);
733 && FETCH_BYTE (start_byte
) == '\n')
740 *bytepos
= start_byte
;
744 /* If we found a non-newline character before hitting
745 position where the cache will again return non-zero
746 (i.e. no newlines beyond that position), it means
747 this region is not yet known to the cache, and we
748 must resort to the "dumb loop" method. */
749 if (start
< next_change
&& !result
)
756 start_byte
= end_byte
;
759 immediate_quit
= allow_quit
;
761 /* START should never be after END. */
762 if (start_byte
> ceiling_byte
)
763 start_byte
= ceiling_byte
;
765 /* Now the text after start is an unknown region, and
766 next_change is the position of the next known region. */
767 ceiling_byte
= min (CHAR_TO_BYTE (next_change
) - 1, ceiling_byte
);
769 else if (start_byte
== -1)
770 start_byte
= CHAR_TO_BYTE (start
);
772 /* The dumb loop can only scan text stored in contiguous
773 bytes. BUFFER_CEILING_OF returns the last character
774 position that is contiguous, so the ceiling is the
775 position after that. */
776 tem
= BUFFER_CEILING_OF (start_byte
);
777 ceiling_byte
= min (tem
, ceiling_byte
);
780 /* The termination address of the dumb loop. */
781 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
782 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
784 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
785 of the base, the cursor, and the next line. */
786 ptrdiff_t base
= start_byte
- lim_byte
;
787 ptrdiff_t cursor
, next
;
789 for (cursor
= base
; cursor
< 0; cursor
= next
)
792 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
793 next
= nl
? nl
- lim_addr
: 0;
795 /* If we're using the newline cache, cache the fact that
796 the region we just traversed is free of newlines. */
797 if (newline_cache
&& cursor
!= next
)
799 know_region_cache (cache_buffer
, newline_cache
,
800 BYTE_TO_CHAR (lim_byte
+ cursor
),
801 BYTE_TO_CHAR (lim_byte
+ next
));
802 /* know_region_cache can relocate buffer text. */
803 lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
814 *bytepos
= lim_byte
+ next
;
815 return BYTE_TO_CHAR (lim_byte
+ next
);
819 start_byte
= lim_byte
;
820 start
= BYTE_TO_CHAR (start_byte
);
826 /* The last character to check before the next obstacle. */
827 ptrdiff_t tem
, ceiling_byte
= end_byte
;
829 /* Consult the newline cache, if appropriate. */
832 ptrdiff_t next_change
;
836 while (start
> end
&& result
)
840 result
= region_cache_backward (cache_buffer
, newline_cache
,
841 start
, &next_change
);
845 lim1
= next_change
= end
;
848 lim1
= max (next_change
, end
);
849 start_byte
= CHAR_TO_BYTE (start
);
851 && FETCH_BYTE (start_byte
- 1) == '\n')
856 *bytepos
= start_byte
;
862 if (start
> next_change
&& !result
)
869 start_byte
= end_byte
;
872 immediate_quit
= allow_quit
;
874 /* Start should never be at or before end. */
875 if (start_byte
<= ceiling_byte
)
876 start_byte
= ceiling_byte
+ 1;
878 /* Now the text before start is an unknown region, and
879 next_change is the position of the next known region. */
880 ceiling_byte
= max (CHAR_TO_BYTE (next_change
), ceiling_byte
);
882 else if (start_byte
== -1)
883 start_byte
= CHAR_TO_BYTE (start
);
885 /* Stop scanning before the gap. */
886 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
887 ceiling_byte
= max (tem
, ceiling_byte
);
890 /* The termination address of the dumb loop. */
891 unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
893 /* Offsets (relative to CEILING_ADDR and CEILING_BYTE) of
894 the base, the cursor, and the previous line. These
895 offsets are at least -1. */
896 ptrdiff_t base
= start_byte
- ceiling_byte
;
897 ptrdiff_t cursor
, prev
;
899 for (cursor
= base
; 0 < cursor
; cursor
= prev
)
901 unsigned char *nl
= memrchr (ceiling_addr
, '\n', cursor
);
902 prev
= nl
? nl
- ceiling_addr
: -1;
904 /* If we're looking for newlines, cache the fact that
905 this line's region is free of them. */
906 if (newline_cache
&& cursor
!= prev
+ 1)
908 know_region_cache (cache_buffer
, newline_cache
,
909 BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1),
910 BYTE_TO_CHAR (ceiling_byte
+ cursor
));
911 /* know_region_cache can relocate buffer text. */
912 ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
922 *bytepos
= ceiling_byte
+ prev
+ 1;
923 return BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1);
927 start_byte
= ceiling_byte
;
928 start
= BYTE_TO_CHAR (start_byte
);
934 *shortage
= count
* direction
;
937 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
938 eassert (*bytepos
== CHAR_TO_BYTE (start
));
943 /* Search for COUNT instances of a line boundary.
944 Start at START. If COUNT is negative, search backwards.
946 We report the resulting position by calling TEMP_SET_PT_BOTH.
948 If we find COUNT instances. we position after (always after,
949 even if scanning backwards) the COUNTth match, and return 0.
951 If we don't find COUNT instances before reaching the end of the
952 buffer (or the beginning, if scanning backwards), we return
953 the number of line boundaries left unfound, and position at
954 the limit we bumped up against.
956 If ALLOW_QUIT, set immediate_quit. That's good to do
957 except in special cases. */
960 scan_newline (ptrdiff_t start
, ptrdiff_t start_byte
,
961 ptrdiff_t limit
, ptrdiff_t limit_byte
,
962 ptrdiff_t count
, bool allow_quit
)
964 ptrdiff_t charpos
, bytepos
, shortage
;
966 charpos
= find_newline (start
, start_byte
, limit
, limit_byte
,
967 count
, &shortage
, &bytepos
, allow_quit
);
969 TEMP_SET_PT_BOTH (limit
, limit_byte
);
971 TEMP_SET_PT_BOTH (charpos
, bytepos
);
975 /* Like above, but always scan from point and report the
976 resulting position in *CHARPOS and *BYTEPOS. */
979 scan_newline_from_point (ptrdiff_t count
, ptrdiff_t *charpos
,
985 *charpos
= find_newline (PT
, PT_BYTE
, BEGV
, BEGV_BYTE
, count
- 1,
986 &shortage
, bytepos
, 1);
988 *charpos
= find_newline (PT
, PT_BYTE
, ZV
, ZV_BYTE
, count
,
989 &shortage
, bytepos
, 1);
993 /* Like find_newline, but doesn't allow QUITting and doesn't return
996 find_newline_no_quit (ptrdiff_t from
, ptrdiff_t frombyte
,
997 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
999 return find_newline (from
, frombyte
, 0, -1, cnt
, NULL
, bytepos
, 0);
1002 /* Like find_newline, but returns position before the newline, not
1003 after, and only search up to TO.
1004 This isn't just find_newline_no_quit (...)-1, because you might hit TO. */
1007 find_before_next_newline (ptrdiff_t from
, ptrdiff_t to
,
1008 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
1011 ptrdiff_t pos
= find_newline (from
, -1, to
, -1, cnt
, &shortage
, bytepos
, 1);
1016 DEC_BOTH (pos
, *bytepos
);
1023 /* Subroutines of Lisp buffer search functions. */
1026 search_command (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
,
1027 Lisp_Object count
, int direction
, int RE
, bool posix
)
1032 EMACS_INT n
= direction
;
1036 CHECK_NUMBER (count
);
1040 CHECK_STRING (string
);
1044 lim
= ZV
, lim_byte
= ZV_BYTE
;
1046 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1050 CHECK_NUMBER_COERCE_MARKER (bound
);
1052 if (n
> 0 ? lim
< PT
: lim
> PT
)
1053 error ("Invalid search bound (wrong side of point)");
1055 lim
= ZV
, lim_byte
= ZV_BYTE
;
1056 else if (lim
< BEGV
)
1057 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1059 lim_byte
= CHAR_TO_BYTE (lim
);
1062 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
1063 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
1064 BVAR (current_buffer
, case_eqv_table
));
1066 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
1067 (!NILP (BVAR (current_buffer
, case_fold_search
))
1068 ? BVAR (current_buffer
, case_canon_table
)
1070 (!NILP (BVAR (current_buffer
, case_fold_search
))
1071 ? BVAR (current_buffer
, case_eqv_table
)
1077 xsignal1 (Qsearch_failed
, string
);
1079 if (!EQ (noerror
, Qt
))
1081 eassert (BEGV
<= lim
&& lim
<= ZV
);
1082 SET_PT_BOTH (lim
, lim_byte
);
1084 #if 0 /* This would be clean, but maybe programs depend on
1085 a value of nil here. */
1093 eassert (BEGV
<= np
&& np
<= ZV
);
1096 return make_number (np
);
1099 /* Return true if REGEXP it matches just one constant string. */
1102 trivial_regexp_p (Lisp_Object regexp
)
1104 ptrdiff_t len
= SBYTES (regexp
);
1105 unsigned char *s
= SDATA (regexp
);
1110 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1117 case '|': case '(': case ')': case '`': case '\'': case 'b':
1118 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1119 case 'S': case '=': case '{': case '}': case '_':
1120 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1121 case '1': case '2': case '3': case '4': case '5':
1122 case '6': case '7': case '8': case '9':
1130 /* Search for the n'th occurrence of STRING in the current buffer,
1131 starting at position POS and stopping at position LIM,
1132 treating STRING as a literal string if RE is false or as
1133 a regular expression if RE is true.
1135 If N is positive, searching is forward and LIM must be greater than POS.
1136 If N is negative, searching is backward and LIM must be less than POS.
1138 Returns -x if x occurrences remain to be found (x > 0),
1139 or else the position at the beginning of the Nth occurrence
1140 (if searching backward) or the end (if searching forward).
1142 POSIX is nonzero if we want full backtracking (POSIX style)
1143 for this pattern. 0 means backtrack only enough to get a valid match. */
1145 #define TRANSLATE(out, trt, d) \
1151 temp = Faref (trt, make_number (d)); \
1152 if (INTEGERP (temp)) \
1153 out = XINT (temp); \
1162 /* Only used in search_buffer, to record the end position of the match
1163 when searching regexps and SEARCH_REGS should not be changed
1164 (i.e. Vinhibit_changing_match_data is non-nil). */
1165 static struct re_registers search_regs_1
;
1168 search_buffer (Lisp_Object string
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
1169 ptrdiff_t lim
, ptrdiff_t lim_byte
, EMACS_INT n
,
1170 int RE
, Lisp_Object trt
, Lisp_Object inverse_trt
, bool posix
)
1172 ptrdiff_t len
= SCHARS (string
);
1173 ptrdiff_t len_byte
= SBYTES (string
);
1174 register ptrdiff_t i
;
1176 if (running_asynch_code
)
1177 save_search_regs ();
1179 /* Searching 0 times means don't move. */
1180 /* Null string is found at starting position. */
1181 if (len
== 0 || n
== 0)
1183 set_search_regs (pos_byte
, 0);
1187 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1189 unsigned char *p1
, *p2
;
1191 struct re_pattern_buffer
*bufp
;
1193 bufp
= compile_pattern (string
,
1194 (NILP (Vinhibit_changing_match_data
)
1195 ? &search_regs
: &search_regs_1
),
1197 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
1199 immediate_quit
= 1; /* Quit immediately if user types ^G,
1200 because letting this function finish
1201 can take too long. */
1202 QUIT
; /* Do a pending quit right away,
1203 to avoid paradoxical behavior */
1204 /* Get pointers and sizes of the two strings
1205 that make up the visible portion of the buffer. */
1208 s1
= GPT_BYTE
- BEGV_BYTE
;
1210 s2
= ZV_BYTE
- GPT_BYTE
;
1214 s2
= ZV_BYTE
- BEGV_BYTE
;
1219 s1
= ZV_BYTE
- BEGV_BYTE
;
1222 re_match_object
= Qnil
;
1225 /* Prevent ralloc.c from relocating the current buffer while
1227 r_alloc_inhibit_buffer_relocation (1);
1234 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1235 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1236 (NILP (Vinhibit_changing_match_data
)
1237 ? &search_regs
: &search_regs_1
),
1238 /* Don't allow match past current point */
1239 pos_byte
- BEGV_BYTE
);
1242 matcher_overflow ();
1246 if (NILP (Vinhibit_changing_match_data
))
1248 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1249 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1250 if (search_regs
.start
[i
] >= 0)
1252 search_regs
.start
[i
]
1253 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1255 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1257 XSETBUFFER (last_thing_searched
, current_buffer
);
1258 /* Set pos to the new position. */
1259 pos
= search_regs
.start
[0];
1263 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1264 /* Set pos to the new position. */
1265 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1272 r_alloc_inhibit_buffer_relocation (0);
1282 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1283 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1284 (NILP (Vinhibit_changing_match_data
)
1285 ? &search_regs
: &search_regs_1
),
1286 lim_byte
- BEGV_BYTE
);
1289 matcher_overflow ();
1293 if (NILP (Vinhibit_changing_match_data
))
1295 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1296 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1297 if (search_regs
.start
[i
] >= 0)
1299 search_regs
.start
[i
]
1300 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1302 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1304 XSETBUFFER (last_thing_searched
, current_buffer
);
1305 pos
= search_regs
.end
[0];
1309 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1310 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1317 r_alloc_inhibit_buffer_relocation (0);
1325 r_alloc_inhibit_buffer_relocation (0);
1329 else /* non-RE case */
1331 unsigned char *raw_pattern
, *pat
;
1332 ptrdiff_t raw_pattern_size
;
1333 ptrdiff_t raw_pattern_size_byte
;
1334 unsigned char *patbuf
;
1335 bool multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1336 unsigned char *base_pat
;
1337 /* Set to positive if we find a non-ASCII char that need
1338 translation. Otherwise set to zero later. */
1340 bool boyer_moore_ok
= 1;
1343 /* MULTIBYTE says whether the text to be searched is multibyte.
1344 We must convert PATTERN to match that, or we will not really
1345 find things right. */
1347 if (multibyte
== STRING_MULTIBYTE (string
))
1349 raw_pattern
= SDATA (string
);
1350 raw_pattern_size
= SCHARS (string
);
1351 raw_pattern_size_byte
= SBYTES (string
);
1355 raw_pattern_size
= SCHARS (string
);
1356 raw_pattern_size_byte
1357 = count_size_as_multibyte (SDATA (string
),
1359 raw_pattern
= SAFE_ALLOCA (raw_pattern_size_byte
+ 1);
1360 copy_text (SDATA (string
), raw_pattern
,
1361 SCHARS (string
), 0, 1);
1365 /* Converting multibyte to single-byte.
1367 ??? Perhaps this conversion should be done in a special way
1368 by subtracting nonascii-insert-offset from each non-ASCII char,
1369 so that only the multibyte chars which really correspond to
1370 the chosen single-byte character set can possibly match. */
1371 raw_pattern_size
= SCHARS (string
);
1372 raw_pattern_size_byte
= SCHARS (string
);
1373 raw_pattern
= SAFE_ALLOCA (raw_pattern_size
+ 1);
1374 copy_text (SDATA (string
), raw_pattern
,
1375 SBYTES (string
), 1, 0);
1378 /* Copy and optionally translate the pattern. */
1379 len
= raw_pattern_size
;
1380 len_byte
= raw_pattern_size_byte
;
1381 SAFE_NALLOCA (patbuf
, MAX_MULTIBYTE_LENGTH
, len
);
1383 base_pat
= raw_pattern
;
1386 /* Fill patbuf by translated characters in STRING while
1387 checking if we can use boyer-moore search. If TRT is
1388 non-nil, we can use boyer-moore search only if TRT can be
1389 represented by the byte array of 256 elements. For that,
1390 all non-ASCII case-equivalents of all case-sensitive
1391 characters in STRING must belong to the same character
1392 group (two characters belong to the same group iff their
1393 multibyte forms are the same except for the last byte;
1394 i.e. every 64 characters form a group; U+0000..U+003F,
1395 U+0040..U+007F, U+0080..U+00BF, ...). */
1399 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1400 int c
, translated
, inverse
;
1401 int in_charlen
, charlen
;
1403 /* If we got here and the RE flag is set, it's because we're
1404 dealing with a regexp known to be trivial, so the backslash
1405 just quotes the next character. */
1406 if (RE
&& *base_pat
== '\\')
1414 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1419 charlen
= in_charlen
;
1423 /* Translate the character. */
1424 TRANSLATE (translated
, trt
, c
);
1425 charlen
= CHAR_STRING (translated
, str_base
);
1428 /* Check if C has any other case-equivalents. */
1429 TRANSLATE (inverse
, inverse_trt
, c
);
1430 /* If so, check if we can use boyer-moore. */
1431 if (c
!= inverse
&& boyer_moore_ok
)
1433 /* Check if all equivalents belong to the same
1434 group of characters. Note that the check of C
1435 itself is done by the last iteration. */
1436 int this_char_base
= -1;
1438 while (boyer_moore_ok
)
1440 if (ASCII_CHAR_P (inverse
))
1442 if (this_char_base
> 0)
1447 else if (CHAR_BYTE8_P (inverse
))
1448 /* Boyer-moore search can't handle a
1449 translation of an eight-bit
1452 else if (this_char_base
< 0)
1454 this_char_base
= inverse
& ~0x3F;
1456 char_base
= this_char_base
;
1457 else if (this_char_base
!= char_base
)
1460 else if ((inverse
& ~0x3F) != this_char_base
)
1464 TRANSLATE (inverse
, inverse_trt
, inverse
);
1469 /* Store this character into the translated pattern. */
1470 memcpy (pat
, str
, charlen
);
1472 base_pat
+= in_charlen
;
1473 len_byte
-= in_charlen
;
1476 /* If char_base is still negative we didn't find any translated
1477 non-ASCII characters. */
1483 /* Unibyte buffer. */
1487 int c
, translated
, inverse
;
1489 /* If we got here and the RE flag is set, it's because we're
1490 dealing with a regexp known to be trivial, so the backslash
1491 just quotes the next character. */
1492 if (RE
&& *base_pat
== '\\')
1499 TRANSLATE (translated
, trt
, c
);
1500 *pat
++ = translated
;
1501 /* Check that none of C's equivalents violates the
1502 assumptions of boyer_moore. */
1503 TRANSLATE (inverse
, inverse_trt
, c
);
1506 if (inverse
>= 0200)
1513 TRANSLATE (inverse
, inverse_trt
, inverse
);
1518 len_byte
= pat
- patbuf
;
1519 pat
= base_pat
= patbuf
;
1523 ? boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1526 : simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1527 pos
, pos_byte
, lim
, lim_byte
));
1533 /* Do a simple string search N times for the string PAT,
1534 whose length is LEN/LEN_BYTE,
1535 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1536 TRT is the translation table.
1538 Return the character position where the match is found.
1539 Otherwise, if M matches remained to be found, return -M.
1541 This kind of search works regardless of what is in PAT and
1542 regardless of what is in TRT. It is used in cases where
1543 boyer_moore cannot work. */
1546 simple_search (EMACS_INT n
, unsigned char *pat
,
1547 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1548 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1549 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1551 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1552 bool forward
= n
> 0;
1553 /* Number of buffer bytes matched. Note that this may be different
1554 from len_byte in a multibyte buffer. */
1555 ptrdiff_t match_byte
= PTRDIFF_MIN
;
1557 if (lim
> pos
&& multibyte
)
1562 /* Try matching at position POS. */
1563 ptrdiff_t this_pos
= pos
;
1564 ptrdiff_t this_pos_byte
= pos_byte
;
1565 ptrdiff_t this_len
= len
;
1566 unsigned char *p
= pat
;
1567 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1570 while (this_len
> 0)
1572 int charlen
, buf_charlen
;
1575 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1576 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1578 TRANSLATE (buf_ch
, trt
, buf_ch
);
1580 if (buf_ch
!= pat_ch
)
1586 this_pos_byte
+= buf_charlen
;
1592 match_byte
= this_pos_byte
- pos_byte
;
1594 pos_byte
+= match_byte
;
1598 INC_BOTH (pos
, pos_byte
);
1608 /* Try matching at position POS. */
1609 ptrdiff_t this_pos
= pos
;
1610 ptrdiff_t this_len
= len
;
1611 unsigned char *p
= pat
;
1613 if (pos
+ len
> lim
)
1616 while (this_len
> 0)
1619 int buf_ch
= FETCH_BYTE (this_pos
);
1620 TRANSLATE (buf_ch
, trt
, buf_ch
);
1622 if (buf_ch
!= pat_ch
)
1641 /* Backwards search. */
1642 else if (lim
< pos
&& multibyte
)
1647 /* Try matching at position POS. */
1648 ptrdiff_t this_pos
= pos
;
1649 ptrdiff_t this_pos_byte
= pos_byte
;
1650 ptrdiff_t this_len
= len
;
1651 const unsigned char *p
= pat
+ len_byte
;
1653 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1656 while (this_len
> 0)
1660 DEC_BOTH (this_pos
, this_pos_byte
);
1661 PREV_CHAR_BOUNDARY (p
, pat
);
1662 pat_ch
= STRING_CHAR (p
);
1663 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1664 TRANSLATE (buf_ch
, trt
, buf_ch
);
1666 if (buf_ch
!= pat_ch
)
1674 match_byte
= pos_byte
- this_pos_byte
;
1676 pos_byte
= this_pos_byte
;
1680 DEC_BOTH (pos
, pos_byte
);
1690 /* Try matching at position POS. */
1691 ptrdiff_t this_pos
= pos
- len
;
1692 ptrdiff_t this_len
= len
;
1693 unsigned char *p
= pat
;
1698 while (this_len
> 0)
1701 int buf_ch
= FETCH_BYTE (this_pos
);
1702 TRANSLATE (buf_ch
, trt
, buf_ch
);
1704 if (buf_ch
!= pat_ch
)
1726 eassert (match_byte
!= PTRDIFF_MIN
);
1728 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1730 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1740 /* Do Boyer-Moore search N times for the string BASE_PAT,
1741 whose length is LEN_BYTE,
1742 from buffer position POS_BYTE until LIM_BYTE.
1743 DIRECTION says which direction we search in.
1744 TRT and INVERSE_TRT are translation tables.
1745 Characters in PAT are already translated by TRT.
1747 This kind of search works if all the characters in BASE_PAT that
1748 have nontrivial translation are the same aside from the last byte.
1749 This makes it possible to translate just the last byte of a
1750 character, and do so after just a simple test of the context.
1751 CHAR_BASE is nonzero if there is such a non-ASCII character.
1753 If that criterion is not satisfied, do not call this function. */
1756 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1758 Lisp_Object trt
, Lisp_Object inverse_trt
,
1759 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1762 int direction
= ((n
> 0) ? 1 : -1);
1763 register ptrdiff_t dirlen
;
1765 int stride_for_teases
= 0;
1767 register unsigned char *cursor
, *p_limit
;
1768 register ptrdiff_t i
;
1770 unsigned char *pat
, *pat_end
;
1771 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1773 unsigned char simple_translate
[0400];
1774 /* These are set to the preceding bytes of a byte to be translated
1775 if char_base is nonzero. As the maximum byte length of a
1776 multibyte character is 5, we have to check at most four previous
1778 int translate_prev_byte1
= 0;
1779 int translate_prev_byte2
= 0;
1780 int translate_prev_byte3
= 0;
1782 /* The general approach is that we are going to maintain that we know
1783 the first (closest to the present position, in whatever direction
1784 we're searching) character that could possibly be the last
1785 (furthest from present position) character of a valid match. We
1786 advance the state of our knowledge by looking at that character
1787 and seeing whether it indeed matches the last character of the
1788 pattern. If it does, we take a closer look. If it does not, we
1789 move our pointer (to putative last characters) as far as is
1790 logically possible. This amount of movement, which I call a
1791 stride, will be the length of the pattern if the actual character
1792 appears nowhere in the pattern, otherwise it will be the distance
1793 from the last occurrence of that character to the end of the
1794 pattern. If the amount is zero we have a possible match. */
1796 /* Here we make a "mickey mouse" BM table. The stride of the search
1797 is determined only by the last character of the putative match.
1798 If that character does not match, we will stride the proper
1799 distance to propose a match that superimposes it on the last
1800 instance of a character that matches it (per trt), or misses
1801 it entirely if there is none. */
1803 dirlen
= len_byte
* direction
;
1805 /* Record position after the end of the pattern. */
1806 pat_end
= base_pat
+ len_byte
;
1807 /* BASE_PAT points to a character that we start scanning from.
1808 It is the first character in a forward search,
1809 the last character in a backward search. */
1811 base_pat
= pat_end
- 1;
1813 /* A character that does not appear in the pattern induces a
1814 stride equal to the pattern length. */
1815 for (i
= 0; i
< 0400; i
++)
1818 /* We use this for translation, instead of TRT itself.
1819 We fill this in to handle the characters that actually
1820 occur in the pattern. Others don't matter anyway! */
1821 for (i
= 0; i
< 0400; i
++)
1822 simple_translate
[i
] = i
;
1826 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1827 byte following them are the target of translation. */
1828 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1829 int cblen
= CHAR_STRING (char_base
, str
);
1831 translate_prev_byte1
= str
[cblen
- 2];
1834 translate_prev_byte2
= str
[cblen
- 3];
1836 translate_prev_byte3
= str
[cblen
- 4];
1843 unsigned char *ptr
= base_pat
+ i
;
1847 /* If the byte currently looking at is the last of a
1848 character to check case-equivalents, set CH to that
1849 character. An ASCII character and a non-ASCII character
1850 matching with CHAR_BASE are to be checked. */
1853 if (ASCII_CHAR_P (*ptr
) || ! multibyte
)
1856 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1858 unsigned char *charstart
= ptr
- 1;
1860 while (! (CHAR_HEAD_P (*charstart
)))
1862 ch
= STRING_CHAR (charstart
);
1863 if (char_base
!= (ch
& ~0x3F))
1867 if (ch
>= 0200 && multibyte
)
1868 j
= (ch
& 0x3F) | 0200;
1873 stride_for_teases
= BM_tab
[j
];
1875 BM_tab
[j
] = dirlen
- i
;
1876 /* A translation table is accompanied by its inverse -- see
1877 comment following downcase_table for details. */
1880 int starting_ch
= ch
;
1885 TRANSLATE (ch
, inverse_trt
, ch
);
1886 if (ch
>= 0200 && multibyte
)
1887 j
= (ch
& 0x3F) | 0200;
1891 /* For all the characters that map into CH,
1892 set up simple_translate to map the last byte
1894 simple_translate
[j
] = starting_j
;
1895 if (ch
== starting_ch
)
1897 BM_tab
[j
] = dirlen
- i
;
1906 stride_for_teases
= BM_tab
[j
];
1907 BM_tab
[j
] = dirlen
- i
;
1909 /* stride_for_teases tells how much to stride if we get a
1910 match on the far character but are subsequently
1911 disappointed, by recording what the stride would have been
1912 for that character if the last character had been
1915 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1916 /* loop invariant - POS_BYTE points at where last char (first
1917 char if reverse) of pattern would align in a possible match. */
1921 unsigned char *tail_end_ptr
;
1923 /* It's been reported that some (broken) compiler thinks that
1924 Boolean expressions in an arithmetic context are unsigned.
1925 Using an explicit ?1:0 prevents this. */
1926 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1928 return (n
* (0 - direction
));
1929 /* First we do the part we can by pointers (maybe nothing) */
1932 limit
= pos_byte
- dirlen
+ direction
;
1935 limit
= BUFFER_CEILING_OF (limit
);
1936 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1937 can take on without hitting edge of buffer or the gap. */
1938 limit
= min (limit
, pos_byte
+ 20000);
1939 limit
= min (limit
, lim_byte
- 1);
1943 limit
= BUFFER_FLOOR_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
= max (limit
, pos_byte
- 20000);
1947 limit
= max (limit
, lim_byte
);
1949 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1950 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1952 if ((limit
- pos_byte
) * direction
> 20)
1956 p_limit
= BYTE_POS_ADDR (limit
);
1957 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1958 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1959 while (1) /* use one cursor setting as long as i can */
1961 if (direction
> 0) /* worth duplicating */
1963 while (cursor
<= p_limit
)
1965 if (BM_tab
[*cursor
] == 0)
1967 cursor
+= BM_tab
[*cursor
];
1972 while (cursor
>= p_limit
)
1974 if (BM_tab
[*cursor
] == 0)
1976 cursor
+= BM_tab
[*cursor
];
1979 /* If you are here, cursor is beyond the end of the
1980 searched region. You fail to match within the
1981 permitted region and would otherwise try a character
1982 beyond that region. */
1986 i
= dirlen
- direction
;
1989 while ((i
-= direction
) + direction
!= 0)
1992 cursor
-= direction
;
1993 /* Translate only the last byte of a character. */
1995 || ((cursor
== tail_end_ptr
1996 || CHAR_HEAD_P (cursor
[1]))
1997 && (CHAR_HEAD_P (cursor
[0])
1998 /* Check if this is the last byte of
1999 a translatable character. */
2000 || (translate_prev_byte1
== cursor
[-1]
2001 && (CHAR_HEAD_P (translate_prev_byte1
)
2002 || (translate_prev_byte2
== cursor
[-2]
2003 && (CHAR_HEAD_P (translate_prev_byte2
)
2004 || (translate_prev_byte3
== cursor
[-3]))))))))
2005 ch
= simple_translate
[*cursor
];
2014 while ((i
-= direction
) + direction
!= 0)
2016 cursor
-= direction
;
2017 if (pat
[i
] != *cursor
)
2021 cursor
+= dirlen
- i
- direction
; /* fix cursor */
2022 if (i
+ direction
== 0)
2024 ptrdiff_t position
, start
, end
;
2026 ptrdiff_t cursor_off
;
2029 cursor
-= direction
;
2031 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
2032 ? 1 - len_byte
: 0);
2034 /* set_search_regs might call malloc, which could
2035 cause ralloc.c relocate buffer text. We need to
2036 update pointers into buffer text due to that. */
2037 cursor_off
= cursor
- p2
;
2039 set_search_regs (position
, len_byte
);
2041 p_limit
= BYTE_POS_ADDR (limit
);
2042 p2
= BYTE_POS_ADDR (pos_byte
);
2043 cursor
= p2
+ cursor_off
;
2046 if (NILP (Vinhibit_changing_match_data
))
2048 start
= search_regs
.start
[0];
2049 end
= search_regs
.end
[0];
2052 /* If Vinhibit_changing_match_data is non-nil,
2053 search_regs will not be changed. So let's
2054 compute start and end here. */
2056 start
= BYTE_TO_CHAR (position
);
2057 end
= BYTE_TO_CHAR (position
+ len_byte
);
2060 if ((n
-= direction
) != 0)
2061 cursor
+= dirlen
; /* to resume search */
2063 return direction
> 0 ? end
: start
;
2066 cursor
+= stride_for_teases
; /* <sigh> we lose - */
2068 pos_byte
+= cursor
- p2
;
2071 /* Now we'll pick up a clump that has to be done the hard
2072 way because it covers a discontinuity. */
2074 limit
= ((direction
> 0)
2075 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
2076 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
2077 limit
= ((direction
> 0)
2078 ? min (limit
+ len_byte
, lim_byte
- 1)
2079 : max (limit
- len_byte
, lim_byte
));
2080 /* LIMIT is now the last value POS_BYTE can have
2081 and still be valid for a possible match. */
2084 /* This loop can be coded for space rather than
2085 speed because it will usually run only once.
2086 (the reach is at most len + 21, and typically
2087 does not exceed len). */
2088 while ((limit
- pos_byte
) * direction
>= 0)
2090 int ch
= FETCH_BYTE (pos_byte
);
2091 if (BM_tab
[ch
] == 0)
2093 pos_byte
+= BM_tab
[ch
];
2095 break; /* ran off the end */
2098 /* Found what might be a match. */
2099 i
= dirlen
- direction
;
2100 while ((i
-= direction
) + direction
!= 0)
2104 pos_byte
-= direction
;
2105 ptr
= BYTE_POS_ADDR (pos_byte
);
2106 /* Translate only the last byte of a character. */
2108 || ((ptr
== tail_end_ptr
2109 || CHAR_HEAD_P (ptr
[1]))
2110 && (CHAR_HEAD_P (ptr
[0])
2111 /* Check if this is the last byte of a
2112 translatable character. */
2113 || (translate_prev_byte1
== ptr
[-1]
2114 && (CHAR_HEAD_P (translate_prev_byte1
)
2115 || (translate_prev_byte2
== ptr
[-2]
2116 && (CHAR_HEAD_P (translate_prev_byte2
)
2117 || translate_prev_byte3
== ptr
[-3])))))))
2118 ch
= simple_translate
[*ptr
];
2124 /* Above loop has moved POS_BYTE part or all the way
2125 back to the first pos (last pos if reverse).
2126 Set it once again at the last (first if reverse) char. */
2127 pos_byte
+= dirlen
- i
- direction
;
2128 if (i
+ direction
== 0)
2130 ptrdiff_t position
, start
, end
;
2131 pos_byte
-= direction
;
2133 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2134 set_search_regs (position
, len_byte
);
2136 if (NILP (Vinhibit_changing_match_data
))
2138 start
= search_regs
.start
[0];
2139 end
= search_regs
.end
[0];
2142 /* If Vinhibit_changing_match_data is non-nil,
2143 search_regs will not be changed. So let's
2144 compute start and end here. */
2146 start
= BYTE_TO_CHAR (position
);
2147 end
= BYTE_TO_CHAR (position
+ len_byte
);
2150 if ((n
-= direction
) != 0)
2151 pos_byte
+= dirlen
; /* to resume search */
2153 return direction
> 0 ? end
: start
;
2156 pos_byte
+= stride_for_teases
;
2159 /* We have done one clump. Can we continue? */
2160 if ((lim_byte
- pos_byte
) * direction
< 0)
2161 return ((0 - n
) * direction
);
2163 return BYTE_TO_CHAR (pos_byte
);
2166 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2167 for the overall match just found in the current buffer.
2168 Also clear out the match data for registers 1 and up. */
2171 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2175 if (!NILP (Vinhibit_changing_match_data
))
2178 /* Make sure we have registers in which to store
2179 the match position. */
2180 if (search_regs
.num_regs
== 0)
2182 search_regs
.start
= xmalloc (2 * sizeof (regoff_t
));
2183 search_regs
.end
= xmalloc (2 * sizeof (regoff_t
));
2184 search_regs
.num_regs
= 2;
2187 /* Clear out the other registers. */
2188 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2190 search_regs
.start
[i
] = -1;
2191 search_regs
.end
[i
] = -1;
2194 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2195 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2196 XSETBUFFER (last_thing_searched
, current_buffer
);
2199 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2200 "MSearch backward: ",
2201 doc
: /* Search backward from point for STRING.
2202 Set point to the beginning of the occurrence found, and return point.
2203 An optional second argument bounds the search; it is a buffer position.
2204 The match found must not begin before that position. A value of nil
2205 means search to the beginning of the accessible portion of the buffer.
2206 Optional third argument, if t, means if fail just return nil (no error).
2207 If not nil and not t, position at limit of search and return nil.
2208 Optional fourth argument COUNT, if a positive number, means to search
2209 for COUNT successive occurrences. If COUNT is negative, search
2210 forward, instead of backward, for -COUNT occurrences. A value of
2211 nil means the same as 1.
2212 With COUNT positive, the match found is the COUNTth to last one (or
2213 last, if COUNT is 1 or nil) in the buffer located entirely before
2214 the origin of the search; correspondingly with COUNT negative.
2216 Search case-sensitivity is determined by the value of the variable
2217 `case-fold-search', which see.
2219 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2220 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2222 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2225 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2226 doc
: /* Search forward from point for STRING.
2227 Set point to the end of the occurrence found, and return point.
2228 An optional second argument bounds the search; it is a buffer position.
2229 The match found must not end after that position. A value of nil
2230 means search to the end of the accessible portion of the buffer.
2231 Optional third argument, if t, means if fail just return nil (no error).
2232 If not nil and not t, move to limit of search and return nil.
2233 Optional fourth argument COUNT, if a positive number, means to search
2234 for COUNT successive occurrences. If COUNT is negative, search
2235 backward, instead of forward, for -COUNT occurrences. A value of
2236 nil means the same as 1.
2237 With COUNT positive, the match found is the COUNTth one (or first,
2238 if COUNT is 1 or nil) in the buffer located entirely after the
2239 origin of the search; correspondingly with COUNT negative.
2241 Search case-sensitivity is determined by the value of the variable
2242 `case-fold-search', which see.
2244 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2245 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2247 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2250 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2251 "sRE search backward: ",
2252 doc
: /* Search backward from point for match for regular expression REGEXP.
2253 Set point to the beginning of the occurrence found, and return point.
2254 An optional second argument bounds the search; it is a buffer position.
2255 The match found must not begin before that position. A value of nil
2256 means search to the beginning of the accessible portion of the buffer.
2257 Optional third argument, if t, means if fail just return nil (no error).
2258 If not nil and not t, position at limit of search and return nil.
2259 Optional fourth argument COUNT, if a positive number, means to search
2260 for COUNT successive occurrences. If COUNT is negative, search
2261 forward, instead of backward, for -COUNT occurrences. A value of
2262 nil means the same as 1.
2263 With COUNT positive, the match found is the COUNTth to last one (or
2264 last, if COUNT is 1 or nil) in the buffer located entirely before
2265 the origin of the search; correspondingly with COUNT negative.
2267 Search case-sensitivity is determined by the value of the variable
2268 `case-fold-search', which see.
2270 See also the functions `match-beginning', `match-end', `match-string',
2271 and `replace-match'. */)
2272 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2274 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2277 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2279 doc
: /* Search forward from point for regular expression REGEXP.
2280 Set point to the end of the occurrence found, and return point.
2281 An optional second argument bounds the search; it is a buffer position.
2282 The match found must not end after that position. A value of nil
2283 means search to the end of the accessible portion of the buffer.
2284 Optional third argument, if t, means if fail just return nil (no error).
2285 If not nil and not t, move to limit of search and return nil.
2286 Optional fourth argument COUNT, if a positive number, means to search
2287 for COUNT successive occurrences. If COUNT is negative, search
2288 backward, instead of forward, for -COUNT occurrences. A value of
2289 nil means the same as 1.
2290 With COUNT positive, the match found is the COUNTth one (or first,
2291 if COUNT is 1 or nil) in the buffer located entirely after the
2292 origin of the search; correspondingly with COUNT negative.
2294 Search case-sensitivity is determined by the value of the variable
2295 `case-fold-search', which see.
2297 See also the functions `match-beginning', `match-end', `match-string',
2298 and `replace-match'. */)
2299 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2301 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2304 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2305 "sPosix search backward: ",
2306 doc
: /* Search backward from point for match for regular expression REGEXP.
2307 Find the longest match in accord with Posix regular expression rules.
2308 Set point to the beginning of the occurrence found, and return point.
2309 An optional second argument bounds the search; it is a buffer position.
2310 The match found must not begin before that position. A value of nil
2311 means search to the beginning of the accessible portion of the buffer.
2312 Optional third argument, if t, means if fail just return nil (no error).
2313 If not nil and not t, position at limit of search and return nil.
2314 Optional fourth argument COUNT, if a positive number, means to search
2315 for COUNT successive occurrences. If COUNT is negative, search
2316 forward, instead of backward, for -COUNT occurrences. A value of
2317 nil means the same as 1.
2318 With COUNT positive, the match found is the COUNTth to last one (or
2319 last, if COUNT is 1 or nil) in the buffer located entirely before
2320 the origin of the search; correspondingly with COUNT negative.
2322 Search case-sensitivity is determined by the value of the variable
2323 `case-fold-search', which see.
2325 See also the functions `match-beginning', `match-end', `match-string',
2326 and `replace-match'. */)
2327 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2329 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2332 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2334 doc
: /* Search forward from point for regular expression REGEXP.
2335 Find the longest match in accord with Posix regular expression rules.
2336 Set point to the end of the occurrence found, and return point.
2337 An optional second argument bounds the search; it is a buffer position.
2338 The match found must not end after that position. A value of nil
2339 means search to the end of the accessible portion of the buffer.
2340 Optional third argument, if t, means if fail just return nil (no error).
2341 If not nil and not t, move to limit of search and return nil.
2342 Optional fourth argument COUNT, if a positive number, means to search
2343 for COUNT successive occurrences. If COUNT is negative, search
2344 backward, instead of forward, for -COUNT occurrences. A value of
2345 nil means the same as 1.
2346 With COUNT positive, the match found is the COUNTth one (or first,
2347 if COUNT is 1 or nil) in the buffer located entirely after the
2348 origin of the search; correspondingly with COUNT negative.
2350 Search case-sensitivity is determined by the value of the variable
2351 `case-fold-search', which see.
2353 See also the functions `match-beginning', `match-end', `match-string',
2354 and `replace-match'. */)
2355 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2357 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2360 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2361 doc
: /* Replace text matched by last search with NEWTEXT.
2362 Leave point at the end of the replacement text.
2364 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2365 the replacement text. Otherwise, maybe capitalize the whole text, or
2366 maybe just word initials, based on the replaced text. If the replaced
2367 text has only capital letters and has at least one multiletter word,
2368 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2369 in the replaced text, capitalize each word in NEWTEXT.
2371 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2372 Otherwise treat `\\' as special:
2373 `\\&' in NEWTEXT means substitute original matched text.
2374 `\\N' means substitute what matched the Nth `\\(...\\)'.
2375 If Nth parens didn't match, substitute nothing.
2376 `\\\\' means insert one `\\'.
2377 `\\?' is treated literally
2378 (for compatibility with `query-replace-regexp').
2379 Any other character following `\\' signals an error.
2380 Case conversion does not apply to these substitutions.
2382 If optional fourth argument STRING is non-nil, it should be a string
2383 to act on; this should be the string on which the previous match was
2384 done via `string-match'. In this case, `replace-match' creates and
2385 returns a new string, made by copying STRING and replacing the part of
2386 STRING that was matched (the original STRING itself is not altered).
2388 The optional fifth argument SUBEXP specifies a subexpression;
2389 it says to replace just that subexpression with NEWTEXT,
2390 rather than replacing the entire matched text.
2391 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2392 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2393 NEWTEXT in place of subexp N.
2394 This is useful only after a regular expression search or match,
2395 since only regular expressions have distinguished subexpressions. */)
2396 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2398 enum { nochange
, all_caps
, cap_initial
} case_action
;
2399 ptrdiff_t pos
, pos_byte
;
2400 bool some_multiletter_word
;
2401 bool some_lowercase
;
2402 bool some_uppercase
;
2403 bool some_nonuppercase_initial
;
2406 ptrdiff_t opoint
, newpoint
;
2408 CHECK_STRING (newtext
);
2410 if (! NILP (string
))
2411 CHECK_STRING (string
);
2413 case_action
= nochange
; /* We tried an initialization */
2414 /* but some C compilers blew it */
2416 if (search_regs
.num_regs
<= 0)
2417 error ("`replace-match' called before any match found");
2423 CHECK_NUMBER (subexp
);
2424 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2425 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2426 sub
= XINT (subexp
);
2431 if (search_regs
.start
[sub
] < BEGV
2432 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2433 || search_regs
.end
[sub
] > ZV
)
2434 args_out_of_range (make_number (search_regs
.start
[sub
]),
2435 make_number (search_regs
.end
[sub
]));
2439 if (search_regs
.start
[sub
] < 0
2440 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2441 || search_regs
.end
[sub
] > SCHARS (string
))
2442 args_out_of_range (make_number (search_regs
.start
[sub
]),
2443 make_number (search_regs
.end
[sub
]));
2446 if (NILP (fixedcase
))
2448 /* Decide how to casify by examining the matched text. */
2451 pos
= search_regs
.start
[sub
];
2452 last
= search_regs
.end
[sub
];
2455 pos_byte
= CHAR_TO_BYTE (pos
);
2457 pos_byte
= string_char_to_byte (string
, pos
);
2460 case_action
= all_caps
;
2462 /* some_multiletter_word is set nonzero if any original word
2463 is more than one letter long. */
2464 some_multiletter_word
= 0;
2466 some_nonuppercase_initial
= 0;
2473 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2474 INC_BOTH (pos
, pos_byte
);
2477 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2481 /* Cannot be all caps if any original char is lower case */
2484 if (SYNTAX (prevc
) != Sword
)
2485 some_nonuppercase_initial
= 1;
2487 some_multiletter_word
= 1;
2489 else if (uppercasep (c
))
2492 if (SYNTAX (prevc
) != Sword
)
2495 some_multiletter_word
= 1;
2499 /* If the initial is a caseless word constituent,
2500 treat that like a lowercase initial. */
2501 if (SYNTAX (prevc
) != Sword
)
2502 some_nonuppercase_initial
= 1;
2508 /* Convert to all caps if the old text is all caps
2509 and has at least one multiletter word. */
2510 if (! some_lowercase
&& some_multiletter_word
)
2511 case_action
= all_caps
;
2512 /* Capitalize each word, if the old text has all capitalized words. */
2513 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2514 case_action
= cap_initial
;
2515 else if (!some_nonuppercase_initial
&& some_uppercase
)
2516 /* Should x -> yz, operating on X, give Yz or YZ?
2517 We'll assume the latter. */
2518 case_action
= all_caps
;
2520 case_action
= nochange
;
2523 /* Do replacement in a string. */
2526 Lisp_Object before
, after
;
2528 before
= Fsubstring (string
, make_number (0),
2529 make_number (search_regs
.start
[sub
]));
2530 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2532 /* Substitute parts of the match into NEWTEXT
2536 ptrdiff_t lastpos
= 0;
2537 ptrdiff_t lastpos_byte
= 0;
2538 /* We build up the substituted string in ACCUM. */
2541 ptrdiff_t length
= SBYTES (newtext
);
2545 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2547 ptrdiff_t substart
= -1;
2548 ptrdiff_t subend
= 0;
2549 bool delbackslash
= 0;
2551 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2555 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2559 substart
= search_regs
.start
[sub
];
2560 subend
= search_regs
.end
[sub
];
2562 else if (c
>= '1' && c
<= '9')
2564 if (c
- '0' < search_regs
.num_regs
2565 && search_regs
.start
[c
- '0'] >= 0)
2567 substart
= search_regs
.start
[c
- '0'];
2568 subend
= search_regs
.end
[c
- '0'];
2572 /* If that subexp did not match,
2573 replace \\N with nothing. */
2581 error ("Invalid use of `\\' in replacement text");
2585 if (pos
- 2 != lastpos
)
2586 middle
= substring_both (newtext
, lastpos
,
2588 pos
- 2, pos_byte
- 2);
2591 accum
= concat3 (accum
, middle
,
2593 make_number (substart
),
2594 make_number (subend
)));
2596 lastpos_byte
= pos_byte
;
2598 else if (delbackslash
)
2600 middle
= substring_both (newtext
, lastpos
,
2602 pos
- 1, pos_byte
- 1);
2604 accum
= concat2 (accum
, middle
);
2606 lastpos_byte
= pos_byte
;
2611 middle
= substring_both (newtext
, lastpos
,
2617 newtext
= concat2 (accum
, middle
);
2620 /* Do case substitution in NEWTEXT if desired. */
2621 if (case_action
== all_caps
)
2622 newtext
= Fupcase (newtext
);
2623 else if (case_action
== cap_initial
)
2624 newtext
= Fupcase_initials (newtext
);
2626 return concat3 (before
, newtext
, after
);
2629 /* Record point, then move (quietly) to the start of the match. */
2630 if (PT
>= search_regs
.end
[sub
])
2632 else if (PT
> search_regs
.start
[sub
])
2633 opoint
= search_regs
.end
[sub
] - ZV
;
2637 /* If we want non-literal replacement,
2638 perform substitution on the replacement string. */
2641 ptrdiff_t length
= SBYTES (newtext
);
2642 unsigned char *substed
;
2643 ptrdiff_t substed_alloc_size
, substed_len
;
2644 bool buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2645 bool str_multibyte
= STRING_MULTIBYTE (newtext
);
2646 bool really_changed
= 0;
2648 substed_alloc_size
= (length
<= (STRING_BYTES_BOUND
- 100) / 2
2650 : STRING_BYTES_BOUND
);
2651 substed
= xmalloc (substed_alloc_size
);
2654 /* Go thru NEWTEXT, producing the actual text to insert in
2655 SUBSTED while adjusting multibyteness to that of the current
2658 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2660 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2661 const unsigned char *add_stuff
= NULL
;
2662 ptrdiff_t add_len
= 0;
2668 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2670 c
= CHAR_TO_BYTE8 (c
);
2674 /* Note that we don't have to increment POS. */
2675 c
= SREF (newtext
, pos_byte
++);
2677 MAKE_CHAR_MULTIBYTE (c
);
2680 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2681 or set IDX to a match index, which means put that part
2682 of the buffer text into SUBSTED. */
2690 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2692 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2693 c
= CHAR_TO_BYTE8 (c
);
2697 c
= SREF (newtext
, pos_byte
++);
2699 MAKE_CHAR_MULTIBYTE (c
);
2704 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2706 if (search_regs
.start
[c
- '0'] >= 1)
2710 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2714 error ("Invalid use of `\\' in replacement text");
2719 add_len
= CHAR_STRING (c
, str
);
2723 /* If we want to copy part of a previous match,
2724 set up ADD_STUFF and ADD_LEN to point to it. */
2727 begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2728 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2729 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2730 move_gap_both (search_regs
.start
[idx
], begbyte
);
2733 /* Now the stuff we want to add to SUBSTED
2734 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2736 /* Make sure SUBSTED is big enough. */
2737 if (substed_alloc_size
- substed_len
< add_len
)
2739 xpalloc (substed
, &substed_alloc_size
,
2740 add_len
- (substed_alloc_size
- substed_len
),
2741 STRING_BYTES_BOUND
, 1);
2743 /* We compute this after the call to xpalloc, because that
2744 could cause buffer text be relocated when ralloc.c is used. */
2746 add_stuff
= BYTE_POS_ADDR (begbyte
);
2748 /* Now add to the end of SUBSTED. */
2751 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2752 substed_len
+= add_len
;
2757 newtext
= make_specified_string ((const char *) substed
, -1,
2758 substed_len
, buf_multibyte
);
2762 /* The functions below modify the buffer, so they could trigger
2763 various modification hooks (see signal_before_change and
2764 signal_after_change). If these hooks clobber the match data we
2765 error out since otherwise this will result in confusing bugs. */
2766 ptrdiff_t sub_start
= search_regs
.start
[sub
];
2767 ptrdiff_t sub_end
= search_regs
.end
[sub
];
2768 unsigned num_regs
= search_regs
.num_regs
;
2769 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2771 /* Replace the old text with the new in the cleanest possible way. */
2772 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2773 newtext
, 1, 0, 1, 1);
2774 /* Update saved data to match adjustment made by replace_range. */
2776 ptrdiff_t change
= newpoint
- sub_end
;
2777 if (sub_start
>= sub_end
)
2778 sub_start
+= change
;
2782 if (case_action
== all_caps
)
2783 Fupcase_region (make_number (search_regs
.start
[sub
]),
2784 make_number (newpoint
),
2786 else if (case_action
== cap_initial
)
2787 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2788 make_number (newpoint
));
2790 if (search_regs
.start
[sub
] != sub_start
2791 || search_regs
.end
[sub
] != sub_end
2792 || search_regs
.num_regs
!= num_regs
)
2793 error ("Match data clobbered by buffer modification hooks");
2795 /* Put point back where it was in the text. */
2797 TEMP_SET_PT (opoint
+ ZV
);
2799 TEMP_SET_PT (opoint
);
2801 /* Now move point "officially" to the start of the inserted replacement. */
2802 move_if_not_intangible (newpoint
);
2808 match_limit (Lisp_Object num
, bool beginningp
)
2815 args_out_of_range (num
, make_number (0));
2816 if (search_regs
.num_regs
<= 0)
2817 error ("No match data, because no search succeeded");
2818 if (n
>= search_regs
.num_regs
2819 || search_regs
.start
[n
] < 0)
2821 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2822 : search_regs
.end
[n
]));
2825 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2826 doc
: /* Return position of start of text matched by last search.
2827 SUBEXP, a number, specifies which parenthesized expression in the last
2829 Value is nil if SUBEXPth pair didn't match, or there were less than
2831 Zero means the entire text matched by the whole regexp or whole string.
2833 Return value is undefined if the last search failed. */)
2834 (Lisp_Object subexp
)
2836 return match_limit (subexp
, 1);
2839 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2840 doc
: /* Return position of end of text matched by last search.
2841 SUBEXP, a number, specifies which parenthesized expression in the last
2843 Value is nil if SUBEXPth pair didn't match, or there were less than
2845 Zero means the entire text matched by the whole regexp or whole string.
2847 Return value is undefined if the last search failed. */)
2848 (Lisp_Object subexp
)
2850 return match_limit (subexp
, 0);
2853 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2854 doc
: /* Return a list describing what the last search matched.
2855 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2856 All the elements are markers or nil (nil if the Nth pair didn't match)
2857 if the last match was on a buffer; integers or nil if a string was matched.
2858 Use `set-match-data' to reinstate the data in this list.
2860 If INTEGERS (the optional first argument) is non-nil, always use
2861 integers (rather than markers) to represent buffer positions. In
2862 this case, and if the last match was in a buffer, the buffer will get
2863 stored as one additional element at the end of the list.
2865 If REUSE is a list, reuse it as part of the value. If REUSE is long
2866 enough to hold all the values, and if INTEGERS is non-nil, no consing
2869 If optional third arg RESEAT is non-nil, any previous markers on the
2870 REUSE list will be modified to point to nowhere.
2872 Return value is undefined if the last search failed. */)
2873 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2875 Lisp_Object tail
, prev
;
2880 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2881 if (MARKERP (XCAR (tail
)))
2883 unchain_marker (XMARKER (XCAR (tail
)));
2884 XSETCAR (tail
, Qnil
);
2887 if (NILP (last_thing_searched
))
2893 SAFE_NALLOCA (data
, 1, 2 * search_regs
.num_regs
+ 1);
2896 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2898 ptrdiff_t start
= search_regs
.start
[i
];
2901 if (EQ (last_thing_searched
, Qt
)
2902 || ! NILP (integers
))
2904 XSETFASTINT (data
[2 * i
], start
);
2905 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2907 else if (BUFFERP (last_thing_searched
))
2909 data
[2 * i
] = Fmake_marker ();
2910 Fset_marker (data
[2 * i
],
2911 make_number (start
),
2912 last_thing_searched
);
2913 data
[2 * i
+ 1] = Fmake_marker ();
2914 Fset_marker (data
[2 * i
+ 1],
2915 make_number (search_regs
.end
[i
]),
2916 last_thing_searched
);
2919 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2925 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2928 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2930 data
[len
] = last_thing_searched
;
2934 /* If REUSE is not usable, cons up the values and return them. */
2935 if (! CONSP (reuse
))
2936 reuse
= Flist (len
, data
);
2939 /* If REUSE is a list, store as many value elements as will fit
2940 into the elements of REUSE. */
2941 for (i
= 0, tail
= reuse
; CONSP (tail
);
2942 i
++, tail
= XCDR (tail
))
2945 XSETCAR (tail
, data
[i
]);
2947 XSETCAR (tail
, Qnil
);
2951 /* If we couldn't fit all value elements into REUSE,
2952 cons up the rest of them and add them to the end of REUSE. */
2954 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2961 /* We used to have an internal use variant of `reseat' described as:
2963 If RESEAT is `evaporate', put the markers back on the free list
2964 immediately. No other references to the markers must exist in this
2965 case, so it is used only internally on the unwind stack and
2966 save-match-data from Lisp.
2968 But it was ill-conceived: those supposedly-internal markers get exposed via
2969 the undo-list, so freeing them here is unsafe. */
2971 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2972 doc
: /* Set internal data on last search match from elements of LIST.
2973 LIST should have been created by calling `match-data' previously.
2975 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2976 (register Lisp_Object list
, Lisp_Object reseat
)
2979 register Lisp_Object marker
;
2981 if (running_asynch_code
)
2982 save_search_regs ();
2986 /* Unless we find a marker with a buffer or an explicit buffer
2987 in LIST, assume that this match data came from a string. */
2988 last_thing_searched
= Qt
;
2990 /* Allocate registers if they don't already exist. */
2992 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
2994 if (length
> search_regs
.num_regs
)
2996 ptrdiff_t num_regs
= search_regs
.num_regs
;
2997 if (PTRDIFF_MAX
< length
)
2998 memory_full (SIZE_MAX
);
3000 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
3001 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
3003 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
3005 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
3006 search_regs
.start
[i
] = -1;
3008 search_regs
.num_regs
= num_regs
;
3011 for (i
= 0; CONSP (list
); i
++)
3013 marker
= XCAR (list
);
3014 if (BUFFERP (marker
))
3016 last_thing_searched
= marker
;
3023 search_regs
.start
[i
] = -1;
3032 if (MARKERP (marker
))
3034 if (XMARKER (marker
)->buffer
== 0)
3035 XSETFASTINT (marker
, 0);
3037 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
3040 CHECK_NUMBER_COERCE_MARKER (marker
);
3043 if (!NILP (reseat
) && MARKERP (m
))
3045 unchain_marker (XMARKER (m
));
3046 XSETCAR (list
, Qnil
);
3049 if ((list
= XCDR (list
), !CONSP (list
)))
3052 m
= marker
= XCAR (list
);
3054 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
3055 XSETFASTINT (marker
, 0);
3057 CHECK_NUMBER_COERCE_MARKER (marker
);
3058 if ((XINT (from
) < 0
3059 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
3060 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
3061 && (XINT (marker
) < 0
3062 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
3063 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
3065 search_regs
.start
[i
] = XINT (from
);
3066 search_regs
.end
[i
] = XINT (marker
);
3070 search_regs
.start
[i
] = -1;
3073 if (!NILP (reseat
) && MARKERP (m
))
3075 unchain_marker (XMARKER (m
));
3076 XSETCAR (list
, Qnil
);
3082 for (; i
< search_regs
.num_regs
; i
++)
3083 search_regs
.start
[i
] = -1;
3089 /* If true the match data have been saved in saved_search_regs
3090 during the execution of a sentinel or filter. */
3091 /* static bool search_regs_saved; */
3092 /* static struct re_registers saved_search_regs; */
3093 /* static Lisp_Object saved_last_thing_searched; */
3095 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3096 if asynchronous code (filter or sentinel) is running. */
3098 save_search_regs (void)
3100 if (!search_regs_saved
)
3102 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3103 saved_search_regs
.start
= search_regs
.start
;
3104 saved_search_regs
.end
= search_regs
.end
;
3105 saved_last_thing_searched
= last_thing_searched
;
3106 last_thing_searched
= Qnil
;
3107 search_regs
.num_regs
= 0;
3108 search_regs
.start
= 0;
3109 search_regs
.end
= 0;
3111 search_regs_saved
= 1;
3115 /* Called upon exit from filters and sentinels. */
3117 restore_search_regs (void)
3119 if (search_regs_saved
)
3121 if (search_regs
.num_regs
> 0)
3123 xfree (search_regs
.start
);
3124 xfree (search_regs
.end
);
3126 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3127 search_regs
.start
= saved_search_regs
.start
;
3128 search_regs
.end
= saved_search_regs
.end
;
3129 last_thing_searched
= saved_last_thing_searched
;
3130 saved_last_thing_searched
= Qnil
;
3131 search_regs_saved
= 0;
3135 /* Called from replace-match via replace_range. */
3137 update_search_regs (ptrdiff_t oldstart
, ptrdiff_t oldend
, ptrdiff_t newend
)
3139 /* Adjust search data for this change. */
3140 ptrdiff_t change
= newend
- oldend
;
3143 for (i
= 0; i
< search_regs
.num_regs
; i
++)
3145 if (search_regs
.start
[i
] >= oldend
)
3146 search_regs
.start
[i
] += change
;
3147 else if (search_regs
.start
[i
] > oldstart
)
3148 search_regs
.start
[i
] = oldstart
;
3149 if (search_regs
.end
[i
] >= oldend
)
3150 search_regs
.end
[i
] += change
;
3151 else if (search_regs
.end
[i
] > oldstart
)
3152 search_regs
.end
[i
] = oldstart
;
3157 unwind_set_match_data (Lisp_Object list
)
3159 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3160 Fset_match_data (list
, Qt
);
3163 /* Called to unwind protect the match data. */
3165 record_unwind_save_match_data (void)
3167 record_unwind_protect (unwind_set_match_data
,
3168 Fmatch_data (Qnil
, Qnil
, Qnil
));
3171 /* Quote a string to deactivate reg-expr chars */
3173 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3174 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3175 (Lisp_Object string
)
3177 char *in
, *out
, *end
;
3179 ptrdiff_t backslashes_added
= 0;
3181 CHECK_STRING (string
);
3184 SAFE_NALLOCA (temp
, 2, SBYTES (string
));
3186 /* Now copy the data into the new string, inserting escapes. */
3188 in
= SSDATA (string
);
3189 end
= in
+ SBYTES (string
);
3192 for (; in
!= end
; in
++)
3195 || *in
== '*' || *in
== '.' || *in
== '\\'
3196 || *in
== '?' || *in
== '+'
3197 || *in
== '^' || *in
== '$')
3198 *out
++ = '\\', backslashes_added
++;
3203 = make_specified_string (temp
,
3204 SCHARS (string
) + backslashes_added
,
3206 STRING_MULTIBYTE (string
));
3211 /* Like find_newline, but doesn't use the cache, and only searches forward. */
3213 find_newline1 (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
3214 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
3215 ptrdiff_t *bytepos
, bool allow_quit
)
3220 end
= ZV
, end_byte
= ZV_BYTE
;
3225 end
= BEGV
, end_byte
= BEGV_BYTE
;
3228 end_byte
= CHAR_TO_BYTE (end
);
3233 immediate_quit
= allow_quit
;
3236 while (start
!= end
)
3238 /* Our innermost scanning loop is very simple; it doesn't know
3239 about gaps, buffer ends, or the newline cache. ceiling is
3240 the position of the last character before the next such
3241 obstacle --- the last character the dumb search loop should
3243 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
3245 if (start_byte
== -1)
3246 start_byte
= CHAR_TO_BYTE (start
);
3248 /* The dumb loop can only scan text stored in contiguous
3249 bytes. BUFFER_CEILING_OF returns the last character
3250 position that is contiguous, so the ceiling is the
3251 position after that. */
3252 tem
= BUFFER_CEILING_OF (start_byte
);
3253 ceiling_byte
= min (tem
, ceiling_byte
);
3256 /* The termination address of the dumb loop. */
3257 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
3258 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
3260 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
3261 of the base, the cursor, and the next line. */
3262 ptrdiff_t base
= start_byte
- lim_byte
;
3263 ptrdiff_t cursor
, next
;
3265 for (cursor
= base
; cursor
< 0; cursor
= next
)
3267 /* The dumb loop. */
3268 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
3269 next
= nl
? nl
- lim_addr
: 0;
3279 *bytepos
= lim_byte
+ next
;
3280 return BYTE_TO_CHAR (lim_byte
+ next
);
3284 start_byte
= lim_byte
;
3285 start
= BYTE_TO_CHAR (start_byte
);
3294 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
3295 eassert (*bytepos
== CHAR_TO_BYTE (start
));
3300 DEFUN ("newline-cache-check", Fnewline_cache_check
, Snewline_cache_check
,
3302 doc
: /* Check the newline cache of BUFFER against buffer contents.
3304 BUFFER defaults to the current buffer.
3306 Value is an array of 2 sub-arrays of buffer positions for newlines,
3307 the first based on the cache, the second based on actually scanning
3308 the buffer. If the buffer doesn't have a cache, the value is nil. */)
3309 (Lisp_Object buffer
)
3311 struct buffer
*buf
, *old
= NULL
;
3312 ptrdiff_t shortage
, nl_count_cache
, nl_count_buf
;
3313 Lisp_Object cache_newlines
, buf_newlines
, val
;
3314 ptrdiff_t from
, found
, i
;
3317 buf
= current_buffer
;
3320 CHECK_BUFFER (buffer
);
3321 buf
= XBUFFER (buffer
);
3322 old
= current_buffer
;
3324 if (buf
->base_buffer
)
3325 buf
= buf
->base_buffer
;
3327 /* If the buffer doesn't have a newline cache, return nil. */
3328 if (NILP (BVAR (buf
, cache_long_scans
))
3329 || buf
->newline_cache
== NULL
)
3332 /* find_newline can only work on the current buffer. */
3334 set_buffer_internal_1 (buf
);
3336 /* How many newlines are there according to the cache? */
3337 find_newline (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3338 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3339 nl_count_cache
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3341 /* Create vector and populate it. */
3342 cache_newlines
= make_uninit_vector (nl_count_cache
);
3346 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3348 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3350 found
= find_newline (from
, from_byte
, 0, -1, 1, &shortage
,
3352 if (shortage
!= 0 || i
>= nl_count_cache
)
3354 ASET (cache_newlines
, i
, make_number (found
- 1));
3356 /* Fill the rest of slots with an invalid position. */
3357 for ( ; i
< nl_count_cache
; i
++)
3358 ASET (cache_newlines
, i
, make_number (-1));
3361 /* Now do the same, but without using the cache. */
3362 find_newline1 (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3363 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3364 nl_count_buf
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3365 buf_newlines
= make_uninit_vector (nl_count_buf
);
3368 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3370 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3372 found
= find_newline1 (from
, from_byte
, 0, -1, 1, &shortage
,
3374 if (shortage
!= 0 || i
>= nl_count_buf
)
3376 ASET (buf_newlines
, i
, make_number (found
- 1));
3378 for ( ; i
< nl_count_buf
; i
++)
3379 ASET (buf_newlines
, i
, make_number (-1));
3382 /* Construct the value and return it. */
3383 val
= make_uninit_vector (2);
3384 ASET (val
, 0, cache_newlines
);
3385 ASET (val
, 1, buf_newlines
);
3388 set_buffer_internal_1 (old
);
3393 syms_of_search (void)
3397 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3399 searchbufs
[i
].buf
.allocated
= 100;
3400 searchbufs
[i
].buf
.buffer
= xmalloc (100);
3401 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3402 searchbufs
[i
].regexp
= Qnil
;
3403 searchbufs
[i
].f_whitespace_regexp
= Qnil
;
3404 searchbufs
[i
].syntax_table
= Qnil
;
3405 staticpro (&searchbufs
[i
].regexp
);
3406 staticpro (&searchbufs
[i
].f_whitespace_regexp
);
3407 staticpro (&searchbufs
[i
].syntax_table
);
3408 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3410 searchbuf_head
= &searchbufs
[0];
3412 /* Error condition used for failing searches. */
3413 DEFSYM (Qsearch_failed
, "search-failed");
3415 /* Error condition signaled when regexp compile_pattern fails. */
3416 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3418 Fput (Qsearch_failed
, Qerror_conditions
,
3419 listn (CONSTYPE_PURE
, 2, Qsearch_failed
, Qerror
));
3420 Fput (Qsearch_failed
, Qerror_message
,
3421 build_pure_c_string ("Search failed"));
3423 Fput (Qinvalid_regexp
, Qerror_conditions
,
3424 listn (CONSTYPE_PURE
, 2, Qinvalid_regexp
, Qerror
));
3425 Fput (Qinvalid_regexp
, Qerror_message
,
3426 build_pure_c_string ("Invalid regexp"));
3428 last_thing_searched
= Qnil
;
3429 staticpro (&last_thing_searched
);
3431 saved_last_thing_searched
= Qnil
;
3432 staticpro (&saved_last_thing_searched
);
3434 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3435 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3436 Some commands use this for user-specified regexps.
3437 Spaces that occur inside character classes or repetition operators
3438 or other such regexp constructs are not replaced with this.
3439 A value of nil (which is the normal value) means treat spaces literally. */);
3440 Vsearch_spaces_regexp
= Qnil
;
3442 DEFSYM (Qinhibit_changing_match_data
, "inhibit-changing-match-data");
3443 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3444 doc
: /* Internal use only.
3445 If non-nil, the primitive searching and matching functions
3446 such as `looking-at', `string-match', `re-search-forward', etc.,
3447 do not set the match data. The proper way to use this variable
3448 is to bind it with `let' around a small expression. */);
3449 Vinhibit_changing_match_data
= Qnil
;
3451 defsubr (&Slooking_at
);
3452 defsubr (&Sposix_looking_at
);
3453 defsubr (&Sstring_match
);
3454 defsubr (&Sposix_string_match
);
3455 defsubr (&Ssearch_forward
);
3456 defsubr (&Ssearch_backward
);
3457 defsubr (&Sre_search_forward
);
3458 defsubr (&Sre_search_backward
);
3459 defsubr (&Sposix_search_forward
);
3460 defsubr (&Sposix_search_backward
);
3461 defsubr (&Sreplace_match
);
3462 defsubr (&Smatch_beginning
);
3463 defsubr (&Smatch_end
);
3464 defsubr (&Smatch_data
);
3465 defsubr (&Sset_match_data
);
3466 defsubr (&Sregexp_quote
);
3467 defsubr (&Snewline_cache_check
);