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"
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
)
116 const char *whitespace_regexp
;
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. */
135 whitespace_regexp
= STRINGP (Vsearch_spaces_regexp
) ?
136 SSDATA (Vsearch_spaces_regexp
) : NULL
;
138 val
= (char *) re_compile_pattern (SSDATA (pattern
), SBYTES (pattern
),
139 posix
, whitespace_regexp
, &cp
->buf
);
141 /* If the compiled pattern hard codes some of the contents of the
142 syntax-table, it can only be reused with *this* syntax table. */
143 cp
->syntax_table
= cp
->buf
.used_syntax
? BVAR (current_buffer
, syntax_table
) : Qt
;
145 /* unblock_input (); */
147 xsignal1 (Qinvalid_regexp
, build_string (val
));
149 cp
->regexp
= Fcopy_sequence (pattern
);
152 /* Shrink each compiled regexp buffer in the cache
153 to the size actually used right now.
154 This is called from garbage collection. */
157 shrink_regexp_cache (void)
159 struct regexp_cache
*cp
;
161 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
163 cp
->buf
.allocated
= cp
->buf
.used
;
164 cp
->buf
.buffer
= xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
168 /* Clear the regexp cache w.r.t. a particular syntax table,
169 because it was changed.
170 There is no danger of memory leak here because re_compile_pattern
171 automagically manages the memory in each re_pattern_buffer struct,
172 based on its `allocated' and `buffer' values. */
174 clear_regexp_cache (void)
178 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
179 /* It's tempting to compare with the syntax-table we've actually changed,
180 but it's not sufficient because char-table inheritance means that
181 modifying one syntax-table can change others at the same time. */
182 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
183 searchbufs
[i
].regexp
= Qnil
;
186 /* Compile a regexp if necessary, but first check to see if there's one in
188 PATTERN is the pattern to compile.
189 TRANSLATE is a translation table for ignoring case, or nil for none.
190 REGP is the structure that says where to store the "register"
191 values that will result from matching this pattern.
192 If it is 0, we should compile the pattern not to record any
193 subexpression bounds.
194 POSIX is true if we want full backtracking (POSIX style) for this pattern.
195 False means backtrack only enough to get a valid match. */
197 struct re_pattern_buffer
*
198 compile_pattern (Lisp_Object pattern
, struct re_registers
*regp
,
199 Lisp_Object translate
, bool posix
, bool multibyte
)
201 struct regexp_cache
*cp
, **cpp
;
203 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
206 /* Entries are initialized to nil, and may be set to nil by
207 compile_pattern_1 if the pattern isn't valid. Don't apply
208 string accessors in those cases. However, compile_pattern_1
209 is only applied to the cache entry we pick here to reuse. So
210 nil should never appear before a non-nil entry. */
211 if (NILP (cp
->regexp
))
213 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
214 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
215 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
216 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
217 && cp
->posix
== posix
218 && (EQ (cp
->syntax_table
, Qt
)
219 || EQ (cp
->syntax_table
, BVAR (current_buffer
, syntax_table
)))
220 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
))
221 && cp
->buf
.charset_unibyte
== charset_unibyte
)
224 /* If we're at the end of the cache, compile into the nil cell
225 we found, or the last (least recently used) cell with a
230 compile_pattern_1 (cp
, pattern
, translate
, posix
);
235 /* When we get here, cp (aka *cpp) contains the compiled pattern,
236 either because we found it in the cache or because we just compiled it.
237 Move it to the front of the queue to mark it as most recently used. */
239 cp
->next
= searchbuf_head
;
242 /* Advise the searching functions about the space we have allocated
243 for register data. */
245 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
247 /* The compiled pattern can be used both for multibyte and unibyte
248 target. But, we have to tell which the pattern is used for. */
249 cp
->buf
.target_multibyte
= multibyte
;
256 looking_at_1 (Lisp_Object string
, bool posix
)
259 unsigned char *p1
, *p2
;
261 register ptrdiff_t i
;
262 struct re_pattern_buffer
*bufp
;
264 if (running_asynch_code
)
267 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
268 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
269 BVAR (current_buffer
, case_eqv_table
));
271 CHECK_STRING (string
);
272 bufp
= compile_pattern (string
,
273 (NILP (Vinhibit_changing_match_data
)
274 ? &search_regs
: NULL
),
275 (!NILP (BVAR (current_buffer
, case_fold_search
))
276 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
278 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
281 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
283 /* Get pointers and sizes of the two strings
284 that make up the visible portion of the buffer. */
287 s1
= GPT_BYTE
- BEGV_BYTE
;
289 s2
= ZV_BYTE
- GPT_BYTE
;
293 s2
= ZV_BYTE
- BEGV_BYTE
;
298 s1
= ZV_BYTE
- BEGV_BYTE
;
302 re_match_object
= Qnil
;
305 /* Prevent ralloc.c from relocating the current buffer while
307 r_alloc_inhibit_buffer_relocation (1);
309 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
311 (NILP (Vinhibit_changing_match_data
)
312 ? &search_regs
: NULL
),
313 ZV_BYTE
- BEGV_BYTE
);
316 r_alloc_inhibit_buffer_relocation (0);
322 val
= (i
>= 0 ? Qt
: Qnil
);
323 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
325 for (i
= 0; i
< search_regs
.num_regs
; i
++)
326 if (search_regs
.start
[i
] >= 0)
329 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
331 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
333 /* Set last_thing_searched only when match data is changed. */
334 XSETBUFFER (last_thing_searched
, current_buffer
);
340 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
341 doc
: /* Return t if text after point matches regular expression REGEXP.
342 This function modifies the match data that `match-beginning',
343 `match-end' and `match-data' access; save and restore the match
344 data if you want to preserve them. */)
347 return looking_at_1 (regexp
, 0);
350 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
351 doc
: /* Return t if text after point matches regular expression REGEXP.
352 Find the longest match, in accord with Posix regular expression rules.
353 This function modifies the match data that `match-beginning',
354 `match-end' and `match-data' access; save and restore the match
355 data if you want to preserve them. */)
358 return looking_at_1 (regexp
, 1);
362 string_match_1 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
,
366 struct re_pattern_buffer
*bufp
;
368 ptrdiff_t pos_byte
, i
;
370 if (running_asynch_code
)
373 CHECK_STRING (regexp
);
374 CHECK_STRING (string
);
377 pos
= 0, pos_byte
= 0;
380 ptrdiff_t len
= SCHARS (string
);
382 CHECK_NUMBER (start
);
384 if (pos
< 0 && -pos
<= len
)
386 else if (0 > pos
|| pos
> len
)
387 args_out_of_range (string
, start
);
388 pos_byte
= string_char_to_byte (string
, pos
);
391 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
392 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
393 BVAR (current_buffer
, case_eqv_table
));
395 bufp
= compile_pattern (regexp
,
396 (NILP (Vinhibit_changing_match_data
)
397 ? &search_regs
: NULL
),
398 (!NILP (BVAR (current_buffer
, case_fold_search
))
399 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
401 STRING_MULTIBYTE (string
));
403 re_match_object
= string
;
405 val
= re_search (bufp
, SSDATA (string
),
406 SBYTES (string
), pos_byte
,
407 SBYTES (string
) - pos_byte
,
408 (NILP (Vinhibit_changing_match_data
)
409 ? &search_regs
: NULL
));
412 /* Set last_thing_searched only when match data is changed. */
413 if (NILP (Vinhibit_changing_match_data
))
414 last_thing_searched
= Qt
;
418 if (val
< 0) return Qnil
;
420 if (NILP (Vinhibit_changing_match_data
))
421 for (i
= 0; i
< search_regs
.num_regs
; i
++)
422 if (search_regs
.start
[i
] >= 0)
425 = string_byte_to_char (string
, search_regs
.start
[i
]);
427 = string_byte_to_char (string
, search_regs
.end
[i
]);
430 return make_number (string_byte_to_char (string
, val
));
433 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
434 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
435 Matching ignores case if `case-fold-search' is non-nil.
436 If third arg START is non-nil, start search at that index in STRING.
437 For index of first char beyond the match, do (match-end 0).
438 `match-end' and `match-beginning' also give indices of substrings
439 matched by parenthesis constructs in the pattern.
441 You can use the function `match-string' to extract the substrings
442 matched by the parenthesis constructions in REGEXP. */)
443 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
445 return string_match_1 (regexp
, string
, start
, 0);
448 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
449 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
450 Find the longest match, in accord with Posix regular expression rules.
451 Case is ignored if `case-fold-search' is non-nil in the current buffer.
452 If third arg START is non-nil, start search at that index in STRING.
453 For index of first char beyond the match, do (match-end 0).
454 `match-end' and `match-beginning' also give indices of substrings
455 matched by parenthesis constructs in the pattern. */)
456 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
458 return string_match_1 (regexp
, string
, start
, 1);
461 /* Match REGEXP against STRING using translation table TABLE,
462 searching all of STRING, and return the index of the match,
463 or negative on failure. This does not clobber the match data. */
466 fast_string_match_internal (Lisp_Object regexp
, Lisp_Object string
,
470 struct re_pattern_buffer
*bufp
;
472 bufp
= compile_pattern (regexp
, 0, table
,
473 0, STRING_MULTIBYTE (string
));
475 re_match_object
= string
;
477 val
= re_search (bufp
, SSDATA (string
),
484 /* Match REGEXP against STRING, searching all of STRING ignoring case,
485 and return the index of the match, or negative on failure.
486 This does not clobber the match data.
487 We assume that STRING contains single-byte characters. */
490 fast_c_string_match_ignore_case (Lisp_Object regexp
,
491 const char *string
, ptrdiff_t len
)
494 struct re_pattern_buffer
*bufp
;
496 regexp
= string_make_unibyte (regexp
);
497 re_match_object
= Qt
;
498 bufp
= compile_pattern (regexp
, 0,
499 Vascii_canon_table
, 0,
502 val
= re_search (bufp
, string
, len
, 0, len
, 0);
507 /* Match REGEXP against the characters after POS to LIMIT, and return
508 the number of matched characters. If STRING is non-nil, match
509 against the characters in it. In that case, POS and LIMIT are
510 indices into the string. This function doesn't modify the match
514 fast_looking_at (Lisp_Object regexp
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
515 ptrdiff_t limit
, ptrdiff_t limit_byte
, Lisp_Object string
)
518 struct re_pattern_buffer
*buf
;
519 unsigned char *p1
, *p2
;
523 if (STRINGP (string
))
526 pos_byte
= string_char_to_byte (string
, pos
);
528 limit_byte
= string_char_to_byte (string
, limit
);
532 s2
= SBYTES (string
);
533 re_match_object
= string
;
534 multibyte
= STRING_MULTIBYTE (string
);
539 pos_byte
= CHAR_TO_BYTE (pos
);
541 limit_byte
= CHAR_TO_BYTE (limit
);
542 pos_byte
-= BEGV_BYTE
;
543 limit_byte
-= BEGV_BYTE
;
545 s1
= GPT_BYTE
- BEGV_BYTE
;
547 s2
= ZV_BYTE
- GPT_BYTE
;
551 s2
= ZV_BYTE
- BEGV_BYTE
;
556 s1
= ZV_BYTE
- BEGV_BYTE
;
559 re_match_object
= Qnil
;
560 multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
563 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
566 /* Prevent ralloc.c from relocating the current buffer while
568 r_alloc_inhibit_buffer_relocation (1);
570 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
571 pos_byte
, NULL
, limit_byte
);
573 r_alloc_inhibit_buffer_relocation (0);
581 /* The newline cache: remembering which sections of text have no newlines. */
583 /* If the user has requested the long scans caching, make sure it's on.
584 Otherwise, make sure it's off.
585 This is our cheezy way of associating an action with the change of
586 state of a buffer-local variable. */
587 static struct region_cache
*
588 newline_cache_on_off (struct buffer
*buf
)
590 struct buffer
*base_buf
= buf
;
591 bool indirect_p
= false;
593 if (buf
->base_buffer
)
595 base_buf
= buf
->base_buffer
;
599 /* Don't turn on or off the cache in the base buffer, if the value
600 of cache-long-scans of the base buffer is inconsistent with that.
601 This is because doing so will just make the cache pure overhead,
602 since if we turn it on via indirect buffer, it will be
603 immediately turned off by its base buffer. */
604 if (NILP (BVAR (buf
, cache_long_scans
)))
607 || NILP (BVAR (base_buf
, cache_long_scans
)))
609 /* It should be off. */
610 if (base_buf
->newline_cache
)
612 free_region_cache (base_buf
->newline_cache
);
613 base_buf
->newline_cache
= 0;
621 || !NILP (BVAR (base_buf
, cache_long_scans
)))
623 /* It should be on. */
624 if (base_buf
->newline_cache
== 0)
625 base_buf
->newline_cache
= new_region_cache ();
627 return base_buf
->newline_cache
;
632 /* Search for COUNT newlines between START/START_BYTE and END/END_BYTE.
634 If COUNT is positive, search forwards; END must be >= START.
635 If COUNT is negative, search backwards for the -COUNTth instance;
636 END must be <= START.
637 If COUNT is zero, do anything you please; run rogue, for all I care.
639 If END is zero, use BEGV or ZV instead, as appropriate for the
640 direction indicated by COUNT.
642 If we find COUNT instances, set *SHORTAGE to zero, and return the
643 position past the COUNTth match. Note that for reverse motion
644 this is not the same as the usual convention for Emacs motion commands.
646 If we don't find COUNT instances before reaching END, set *SHORTAGE
647 to the number of newlines left unfound, and return END.
649 If BYTEPOS is not NULL, set *BYTEPOS to the byte position corresponding
650 to the returned character position.
652 If ALLOW_QUIT, set immediate_quit. That's good to do
653 except when inside redisplay. */
656 find_newline (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
657 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
658 ptrdiff_t *bytepos
, bool allow_quit
)
660 struct region_cache
*newline_cache
;
662 struct buffer
*cache_buffer
;
668 end
= ZV
, end_byte
= ZV_BYTE
;
674 end
= BEGV
, end_byte
= BEGV_BYTE
;
677 end_byte
= CHAR_TO_BYTE (end
);
679 newline_cache
= newline_cache_on_off (current_buffer
);
680 if (current_buffer
->base_buffer
)
681 cache_buffer
= current_buffer
->base_buffer
;
683 cache_buffer
= current_buffer
;
688 immediate_quit
= allow_quit
;
693 /* Our innermost scanning loop is very simple; it doesn't know
694 about gaps, buffer ends, or the newline cache. ceiling is
695 the position of the last character before the next such
696 obstacle --- the last character the dumb search loop should
698 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
700 /* If we're using the newline cache, consult it to see whether
701 we can avoid some scanning. */
704 ptrdiff_t next_change
;
708 while (start
< end
&& result
)
712 result
= region_cache_forward (cache_buffer
, newline_cache
,
713 start
, &next_change
);
716 /* When the cache revalidation is deferred,
717 next-change might point beyond ZV, which will
718 cause assertion violation in CHAR_TO_BYTE below.
719 Limit next_change to ZV to avoid that. */
720 if (next_change
> ZV
)
723 lim1
= next_change
= end
;
726 lim1
= min (next_change
, end
);
728 /* The cache returned zero for this region; see if
729 this is because the region is known and includes
730 only newlines. While at that, count any newlines
731 we bump into, and exit if we found enough off them. */
732 start_byte
= CHAR_TO_BYTE (start
);
734 && FETCH_BYTE (start_byte
) == '\n')
741 *bytepos
= start_byte
;
745 /* If we found a non-newline character before hitting
746 position where the cache will again return non-zero
747 (i.e. no newlines beyond that position), it means
748 this region is not yet known to the cache, and we
749 must resort to the "dumb loop" method. */
750 if (start
< next_change
&& !result
)
757 start_byte
= end_byte
;
760 immediate_quit
= allow_quit
;
762 /* START should never be after END. */
763 if (start_byte
> ceiling_byte
)
764 start_byte
= ceiling_byte
;
766 /* Now the text after start is an unknown region, and
767 next_change is the position of the next known region. */
768 ceiling_byte
= min (CHAR_TO_BYTE (next_change
) - 1, ceiling_byte
);
770 else if (start_byte
== -1)
771 start_byte
= CHAR_TO_BYTE (start
);
773 /* The dumb loop can only scan text stored in contiguous
774 bytes. BUFFER_CEILING_OF returns the last character
775 position that is contiguous, so the ceiling is the
776 position after that. */
777 tem
= BUFFER_CEILING_OF (start_byte
);
778 ceiling_byte
= min (tem
, ceiling_byte
);
781 /* The termination address of the dumb loop. */
782 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
783 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
785 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
786 of the base, the cursor, and the next line. */
787 ptrdiff_t base
= start_byte
- lim_byte
;
788 ptrdiff_t cursor
, next
;
790 for (cursor
= base
; cursor
< 0; cursor
= next
)
793 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
794 next
= nl
? nl
- lim_addr
: 0;
796 /* If we're using the newline cache, cache the fact that
797 the region we just traversed is free of newlines. */
798 if (newline_cache
&& cursor
!= next
)
800 know_region_cache (cache_buffer
, newline_cache
,
801 BYTE_TO_CHAR (lim_byte
+ cursor
),
802 BYTE_TO_CHAR (lim_byte
+ next
));
803 /* know_region_cache can relocate buffer text. */
804 lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
815 *bytepos
= lim_byte
+ next
;
816 return BYTE_TO_CHAR (lim_byte
+ next
);
820 start_byte
= lim_byte
;
821 start
= BYTE_TO_CHAR (start_byte
);
827 /* The last character to check before the next obstacle. */
828 ptrdiff_t tem
, ceiling_byte
= end_byte
;
830 /* Consult the newline cache, if appropriate. */
833 ptrdiff_t next_change
;
837 while (start
> end
&& result
)
841 result
= region_cache_backward (cache_buffer
, newline_cache
,
842 start
, &next_change
);
846 lim1
= next_change
= end
;
849 lim1
= max (next_change
, end
);
850 start_byte
= CHAR_TO_BYTE (start
);
852 && FETCH_BYTE (start_byte
- 1) == '\n')
857 *bytepos
= start_byte
;
863 if (start
> next_change
&& !result
)
870 start_byte
= end_byte
;
873 immediate_quit
= allow_quit
;
875 /* Start should never be at or before end. */
876 if (start_byte
<= ceiling_byte
)
877 start_byte
= ceiling_byte
+ 1;
879 /* Now the text before start is an unknown region, and
880 next_change is the position of the next known region. */
881 ceiling_byte
= max (CHAR_TO_BYTE (next_change
), ceiling_byte
);
883 else if (start_byte
== -1)
884 start_byte
= CHAR_TO_BYTE (start
);
886 /* Stop scanning before the gap. */
887 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
888 ceiling_byte
= max (tem
, ceiling_byte
);
891 /* The termination address of the dumb loop. */
892 unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
894 /* Offsets (relative to CEILING_ADDR and CEILING_BYTE) of
895 the base, the cursor, and the previous line. These
896 offsets are at least -1. */
897 ptrdiff_t base
= start_byte
- ceiling_byte
;
898 ptrdiff_t cursor
, prev
;
900 for (cursor
= base
; 0 < cursor
; cursor
= prev
)
902 unsigned char *nl
= memrchr (ceiling_addr
, '\n', cursor
);
903 prev
= nl
? nl
- ceiling_addr
: -1;
905 /* If we're looking for newlines, cache the fact that
906 this line's region is free of them. */
907 if (newline_cache
&& cursor
!= prev
+ 1)
909 know_region_cache (cache_buffer
, newline_cache
,
910 BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1),
911 BYTE_TO_CHAR (ceiling_byte
+ cursor
));
912 /* know_region_cache can relocate buffer text. */
913 ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
923 *bytepos
= ceiling_byte
+ prev
+ 1;
924 return BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1);
928 start_byte
= ceiling_byte
;
929 start
= BYTE_TO_CHAR (start_byte
);
935 *shortage
= count
* direction
;
938 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
939 eassert (*bytepos
== CHAR_TO_BYTE (start
));
944 /* Search for COUNT instances of a line boundary.
945 Start at START. If COUNT is negative, search backwards.
947 We report the resulting position by calling TEMP_SET_PT_BOTH.
949 If we find COUNT instances. we position after (always after,
950 even if scanning backwards) the COUNTth match, and return 0.
952 If we don't find COUNT instances before reaching the end of the
953 buffer (or the beginning, if scanning backwards), we return
954 the number of line boundaries left unfound, and position at
955 the limit we bumped up against.
957 If ALLOW_QUIT, set immediate_quit. That's good to do
958 except in special cases. */
961 scan_newline (ptrdiff_t start
, ptrdiff_t start_byte
,
962 ptrdiff_t limit
, ptrdiff_t limit_byte
,
963 ptrdiff_t count
, bool allow_quit
)
965 ptrdiff_t charpos
, bytepos
, shortage
;
967 charpos
= find_newline (start
, start_byte
, limit
, limit_byte
,
968 count
, &shortage
, &bytepos
, allow_quit
);
970 TEMP_SET_PT_BOTH (limit
, limit_byte
);
972 TEMP_SET_PT_BOTH (charpos
, bytepos
);
976 /* Like above, but always scan from point and report the
977 resulting position in *CHARPOS and *BYTEPOS. */
980 scan_newline_from_point (ptrdiff_t count
, ptrdiff_t *charpos
,
986 *charpos
= find_newline (PT
, PT_BYTE
, BEGV
, BEGV_BYTE
, count
- 1,
987 &shortage
, bytepos
, 1);
989 *charpos
= find_newline (PT
, PT_BYTE
, ZV
, ZV_BYTE
, count
,
990 &shortage
, bytepos
, 1);
994 /* Like find_newline, but doesn't allow QUITting and doesn't return
997 find_newline_no_quit (ptrdiff_t from
, ptrdiff_t frombyte
,
998 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
1000 return find_newline (from
, frombyte
, 0, -1, cnt
, NULL
, bytepos
, 0);
1003 /* Like find_newline, but returns position before the newline, not
1004 after, and only search up to TO.
1005 This isn't just find_newline_no_quit (...)-1, because you might hit TO. */
1008 find_before_next_newline (ptrdiff_t from
, ptrdiff_t to
,
1009 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
1012 ptrdiff_t pos
= find_newline (from
, -1, to
, -1, cnt
, &shortage
, bytepos
, 1);
1017 DEC_BOTH (pos
, *bytepos
);
1024 /* Subroutines of Lisp buffer search functions. */
1027 search_command (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
,
1028 Lisp_Object count
, int direction
, int RE
, bool posix
)
1033 EMACS_INT n
= direction
;
1037 CHECK_NUMBER (count
);
1041 CHECK_STRING (string
);
1045 lim
= ZV
, lim_byte
= ZV_BYTE
;
1047 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1051 CHECK_NUMBER_COERCE_MARKER (bound
);
1053 if (n
> 0 ? lim
< PT
: lim
> PT
)
1054 error ("Invalid search bound (wrong side of point)");
1056 lim
= ZV
, lim_byte
= ZV_BYTE
;
1057 else if (lim
< BEGV
)
1058 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1060 lim_byte
= CHAR_TO_BYTE (lim
);
1063 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
1064 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
1065 BVAR (current_buffer
, case_eqv_table
));
1067 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
1068 (!NILP (BVAR (current_buffer
, case_fold_search
))
1069 ? BVAR (current_buffer
, case_canon_table
)
1071 (!NILP (BVAR (current_buffer
, case_fold_search
))
1072 ? BVAR (current_buffer
, case_eqv_table
)
1078 xsignal1 (Qsearch_failed
, string
);
1080 if (!EQ (noerror
, Qt
))
1082 eassert (BEGV
<= lim
&& lim
<= ZV
);
1083 SET_PT_BOTH (lim
, lim_byte
);
1085 #if 0 /* This would be clean, but maybe programs depend on
1086 a value of nil here. */
1094 eassert (BEGV
<= np
&& np
<= ZV
);
1097 return make_number (np
);
1100 /* Return true if REGEXP it matches just one constant string. */
1103 trivial_regexp_p (Lisp_Object regexp
)
1105 ptrdiff_t len
= SBYTES (regexp
);
1106 unsigned char *s
= SDATA (regexp
);
1111 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1118 case '|': case '(': case ')': case '`': case '\'': case 'b':
1119 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1120 case 'S': case '=': case '{': case '}': case '_':
1121 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1122 case '1': case '2': case '3': case '4': case '5':
1123 case '6': case '7': case '8': case '9':
1131 /* Search for the n'th occurrence of STRING in the current buffer,
1132 starting at position POS and stopping at position LIM,
1133 treating STRING as a literal string if RE is false or as
1134 a regular expression if RE is true.
1136 If N is positive, searching is forward and LIM must be greater than POS.
1137 If N is negative, searching is backward and LIM must be less than POS.
1139 Returns -x if x occurrences remain to be found (x > 0),
1140 or else the position at the beginning of the Nth occurrence
1141 (if searching backward) or the end (if searching forward).
1143 POSIX is nonzero if we want full backtracking (POSIX style)
1144 for this pattern. 0 means backtrack only enough to get a valid match. */
1146 #define TRANSLATE(out, trt, d) \
1152 temp = Faref (trt, make_number (d)); \
1153 if (INTEGERP (temp)) \
1154 out = XINT (temp); \
1163 /* Only used in search_buffer, to record the end position of the match
1164 when searching regexps and SEARCH_REGS should not be changed
1165 (i.e. Vinhibit_changing_match_data is non-nil). */
1166 static struct re_registers search_regs_1
;
1169 search_buffer (Lisp_Object string
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
1170 ptrdiff_t lim
, ptrdiff_t lim_byte
, EMACS_INT n
,
1171 int RE
, Lisp_Object trt
, Lisp_Object inverse_trt
, bool posix
)
1173 ptrdiff_t len
= SCHARS (string
);
1174 ptrdiff_t len_byte
= SBYTES (string
);
1175 register ptrdiff_t i
;
1177 if (running_asynch_code
)
1178 save_search_regs ();
1180 /* Searching 0 times means don't move. */
1181 /* Null string is found at starting position. */
1182 if (len
== 0 || n
== 0)
1184 set_search_regs (pos_byte
, 0);
1188 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1190 unsigned char *p1
, *p2
;
1192 struct re_pattern_buffer
*bufp
;
1194 bufp
= compile_pattern (string
,
1195 (NILP (Vinhibit_changing_match_data
)
1196 ? &search_regs
: &search_regs_1
),
1198 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
1200 immediate_quit
= 1; /* Quit immediately if user types ^G,
1201 because letting this function finish
1202 can take too long. */
1203 QUIT
; /* Do a pending quit right away,
1204 to avoid paradoxical behavior */
1205 /* Get pointers and sizes of the two strings
1206 that make up the visible portion of the buffer. */
1209 s1
= GPT_BYTE
- BEGV_BYTE
;
1211 s2
= ZV_BYTE
- GPT_BYTE
;
1215 s2
= ZV_BYTE
- BEGV_BYTE
;
1220 s1
= ZV_BYTE
- BEGV_BYTE
;
1223 re_match_object
= Qnil
;
1226 /* Prevent ralloc.c from relocating the current buffer while
1228 r_alloc_inhibit_buffer_relocation (1);
1235 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1236 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1237 (NILP (Vinhibit_changing_match_data
)
1238 ? &search_regs
: &search_regs_1
),
1239 /* Don't allow match past current point */
1240 pos_byte
- BEGV_BYTE
);
1243 matcher_overflow ();
1247 if (NILP (Vinhibit_changing_match_data
))
1249 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1250 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1251 if (search_regs
.start
[i
] >= 0)
1253 search_regs
.start
[i
]
1254 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1256 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1258 XSETBUFFER (last_thing_searched
, current_buffer
);
1259 /* Set pos to the new position. */
1260 pos
= search_regs
.start
[0];
1264 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1265 /* Set pos to the new position. */
1266 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1273 r_alloc_inhibit_buffer_relocation (0);
1283 val
= re_search_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
1284 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1285 (NILP (Vinhibit_changing_match_data
)
1286 ? &search_regs
: &search_regs_1
),
1287 lim_byte
- BEGV_BYTE
);
1290 matcher_overflow ();
1294 if (NILP (Vinhibit_changing_match_data
))
1296 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1297 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1298 if (search_regs
.start
[i
] >= 0)
1300 search_regs
.start
[i
]
1301 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1303 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1305 XSETBUFFER (last_thing_searched
, current_buffer
);
1306 pos
= search_regs
.end
[0];
1310 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1311 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1318 r_alloc_inhibit_buffer_relocation (0);
1326 r_alloc_inhibit_buffer_relocation (0);
1330 else /* non-RE case */
1332 unsigned char *raw_pattern
, *pat
;
1333 ptrdiff_t raw_pattern_size
;
1334 ptrdiff_t raw_pattern_size_byte
;
1335 unsigned char *patbuf
;
1336 bool multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1337 unsigned char *base_pat
;
1338 /* Set to positive if we find a non-ASCII char that need
1339 translation. Otherwise set to zero later. */
1341 bool boyer_moore_ok
= 1;
1344 /* MULTIBYTE says whether the text to be searched is multibyte.
1345 We must convert PATTERN to match that, or we will not really
1346 find things right. */
1348 if (multibyte
== STRING_MULTIBYTE (string
))
1350 raw_pattern
= SDATA (string
);
1351 raw_pattern_size
= SCHARS (string
);
1352 raw_pattern_size_byte
= SBYTES (string
);
1356 raw_pattern_size
= SCHARS (string
);
1357 raw_pattern_size_byte
1358 = count_size_as_multibyte (SDATA (string
),
1360 raw_pattern
= SAFE_ALLOCA (raw_pattern_size_byte
+ 1);
1361 copy_text (SDATA (string
), raw_pattern
,
1362 SCHARS (string
), 0, 1);
1366 /* Converting multibyte to single-byte.
1368 ??? Perhaps this conversion should be done in a special way
1369 by subtracting nonascii-insert-offset from each non-ASCII char,
1370 so that only the multibyte chars which really correspond to
1371 the chosen single-byte character set can possibly match. */
1372 raw_pattern_size
= SCHARS (string
);
1373 raw_pattern_size_byte
= SCHARS (string
);
1374 raw_pattern
= SAFE_ALLOCA (raw_pattern_size
+ 1);
1375 copy_text (SDATA (string
), raw_pattern
,
1376 SBYTES (string
), 1, 0);
1379 /* Copy and optionally translate the pattern. */
1380 len
= raw_pattern_size
;
1381 len_byte
= raw_pattern_size_byte
;
1382 SAFE_NALLOCA (patbuf
, MAX_MULTIBYTE_LENGTH
, len
);
1384 base_pat
= raw_pattern
;
1387 /* Fill patbuf by translated characters in STRING while
1388 checking if we can use boyer-moore search. If TRT is
1389 non-nil, we can use boyer-moore search only if TRT can be
1390 represented by the byte array of 256 elements. For that,
1391 all non-ASCII case-equivalents of all case-sensitive
1392 characters in STRING must belong to the same character
1393 group (two characters belong to the same group iff their
1394 multibyte forms are the same except for the last byte;
1395 i.e. every 64 characters form a group; U+0000..U+003F,
1396 U+0040..U+007F, U+0080..U+00BF, ...). */
1400 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1401 int c
, translated
, inverse
;
1402 int in_charlen
, charlen
;
1404 /* If we got here and the RE flag is set, it's because we're
1405 dealing with a regexp known to be trivial, so the backslash
1406 just quotes the next character. */
1407 if (RE
&& *base_pat
== '\\')
1415 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1420 charlen
= in_charlen
;
1424 /* Translate the character. */
1425 TRANSLATE (translated
, trt
, c
);
1426 charlen
= CHAR_STRING (translated
, str_base
);
1429 /* Check if C has any other case-equivalents. */
1430 TRANSLATE (inverse
, inverse_trt
, c
);
1431 /* If so, check if we can use boyer-moore. */
1432 if (c
!= inverse
&& boyer_moore_ok
)
1434 /* Check if all equivalents belong to the same
1435 group of characters. Note that the check of C
1436 itself is done by the last iteration. */
1437 int this_char_base
= -1;
1439 while (boyer_moore_ok
)
1441 if (ASCII_CHAR_P (inverse
))
1443 if (this_char_base
> 0)
1448 else if (CHAR_BYTE8_P (inverse
))
1449 /* Boyer-moore search can't handle a
1450 translation of an eight-bit
1453 else if (this_char_base
< 0)
1455 this_char_base
= inverse
& ~0x3F;
1457 char_base
= this_char_base
;
1458 else if (this_char_base
!= char_base
)
1461 else if ((inverse
& ~0x3F) != this_char_base
)
1465 TRANSLATE (inverse
, inverse_trt
, inverse
);
1470 /* Store this character into the translated pattern. */
1471 memcpy (pat
, str
, charlen
);
1473 base_pat
+= in_charlen
;
1474 len_byte
-= in_charlen
;
1477 /* If char_base is still negative we didn't find any translated
1478 non-ASCII characters. */
1484 /* Unibyte buffer. */
1488 int c
, translated
, inverse
;
1490 /* If we got here and the RE flag is set, it's because we're
1491 dealing with a regexp known to be trivial, so the backslash
1492 just quotes the next character. */
1493 if (RE
&& *base_pat
== '\\')
1500 TRANSLATE (translated
, trt
, c
);
1501 *pat
++ = translated
;
1502 /* Check that none of C's equivalents violates the
1503 assumptions of boyer_moore. */
1504 TRANSLATE (inverse
, inverse_trt
, c
);
1507 if (inverse
>= 0200)
1514 TRANSLATE (inverse
, inverse_trt
, inverse
);
1519 len_byte
= pat
- patbuf
;
1520 pat
= base_pat
= patbuf
;
1524 ? boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1527 : simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1528 pos
, pos_byte
, lim
, lim_byte
));
1534 /* Do a simple string search N times for the string PAT,
1535 whose length is LEN/LEN_BYTE,
1536 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1537 TRT is the translation table.
1539 Return the character position where the match is found.
1540 Otherwise, if M matches remained to be found, return -M.
1542 This kind of search works regardless of what is in PAT and
1543 regardless of what is in TRT. It is used in cases where
1544 boyer_moore cannot work. */
1547 simple_search (EMACS_INT n
, unsigned char *pat
,
1548 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1549 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1550 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1552 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1553 bool forward
= n
> 0;
1554 /* Number of buffer bytes matched. Note that this may be different
1555 from len_byte in a multibyte buffer. */
1556 ptrdiff_t match_byte
= PTRDIFF_MIN
;
1558 if (lim
> pos
&& multibyte
)
1563 /* Try matching at position POS. */
1564 ptrdiff_t this_pos
= pos
;
1565 ptrdiff_t this_pos_byte
= pos_byte
;
1566 ptrdiff_t this_len
= len
;
1567 unsigned char *p
= pat
;
1568 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1571 while (this_len
> 0)
1573 int charlen
, buf_charlen
;
1576 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1577 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1579 TRANSLATE (buf_ch
, trt
, buf_ch
);
1581 if (buf_ch
!= pat_ch
)
1587 this_pos_byte
+= buf_charlen
;
1593 match_byte
= this_pos_byte
- pos_byte
;
1595 pos_byte
+= match_byte
;
1599 INC_BOTH (pos
, pos_byte
);
1609 /* Try matching at position POS. */
1610 ptrdiff_t this_pos
= pos
;
1611 ptrdiff_t this_len
= len
;
1612 unsigned char *p
= pat
;
1614 if (pos
+ len
> lim
)
1617 while (this_len
> 0)
1620 int buf_ch
= FETCH_BYTE (this_pos
);
1621 TRANSLATE (buf_ch
, trt
, buf_ch
);
1623 if (buf_ch
!= pat_ch
)
1642 /* Backwards search. */
1643 else if (lim
< pos
&& multibyte
)
1648 /* Try matching at position POS. */
1649 ptrdiff_t this_pos
= pos
;
1650 ptrdiff_t this_pos_byte
= pos_byte
;
1651 ptrdiff_t this_len
= len
;
1652 const unsigned char *p
= pat
+ len_byte
;
1654 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1657 while (this_len
> 0)
1661 DEC_BOTH (this_pos
, this_pos_byte
);
1662 PREV_CHAR_BOUNDARY (p
, pat
);
1663 pat_ch
= STRING_CHAR (p
);
1664 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1665 TRANSLATE (buf_ch
, trt
, buf_ch
);
1667 if (buf_ch
!= pat_ch
)
1675 match_byte
= pos_byte
- this_pos_byte
;
1677 pos_byte
= this_pos_byte
;
1681 DEC_BOTH (pos
, pos_byte
);
1691 /* Try matching at position POS. */
1692 ptrdiff_t this_pos
= pos
- len
;
1693 ptrdiff_t this_len
= len
;
1694 unsigned char *p
= pat
;
1699 while (this_len
> 0)
1702 int buf_ch
= FETCH_BYTE (this_pos
);
1703 TRANSLATE (buf_ch
, trt
, buf_ch
);
1705 if (buf_ch
!= pat_ch
)
1727 eassert (match_byte
!= PTRDIFF_MIN
);
1729 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1731 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1741 /* Do Boyer-Moore search N times for the string BASE_PAT,
1742 whose length is LEN_BYTE,
1743 from buffer position POS_BYTE until LIM_BYTE.
1744 DIRECTION says which direction we search in.
1745 TRT and INVERSE_TRT are translation tables.
1746 Characters in PAT are already translated by TRT.
1748 This kind of search works if all the characters in BASE_PAT that
1749 have nontrivial translation are the same aside from the last byte.
1750 This makes it possible to translate just the last byte of a
1751 character, and do so after just a simple test of the context.
1752 CHAR_BASE is nonzero if there is such a non-ASCII character.
1754 If that criterion is not satisfied, do not call this function. */
1757 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1759 Lisp_Object trt
, Lisp_Object inverse_trt
,
1760 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1763 int direction
= ((n
> 0) ? 1 : -1);
1764 register ptrdiff_t dirlen
;
1766 int stride_for_teases
= 0;
1768 register unsigned char *cursor
, *p_limit
;
1769 register ptrdiff_t i
;
1771 unsigned char *pat
, *pat_end
;
1772 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1774 unsigned char simple_translate
[0400];
1775 /* These are set to the preceding bytes of a byte to be translated
1776 if char_base is nonzero. As the maximum byte length of a
1777 multibyte character is 5, we have to check at most four previous
1779 int translate_prev_byte1
= 0;
1780 int translate_prev_byte2
= 0;
1781 int translate_prev_byte3
= 0;
1783 /* The general approach is that we are going to maintain that we know
1784 the first (closest to the present position, in whatever direction
1785 we're searching) character that could possibly be the last
1786 (furthest from present position) character of a valid match. We
1787 advance the state of our knowledge by looking at that character
1788 and seeing whether it indeed matches the last character of the
1789 pattern. If it does, we take a closer look. If it does not, we
1790 move our pointer (to putative last characters) as far as is
1791 logically possible. This amount of movement, which I call a
1792 stride, will be the length of the pattern if the actual character
1793 appears nowhere in the pattern, otherwise it will be the distance
1794 from the last occurrence of that character to the end of the
1795 pattern. If the amount is zero we have a possible match. */
1797 /* Here we make a "mickey mouse" BM table. The stride of the search
1798 is determined only by the last character of the putative match.
1799 If that character does not match, we will stride the proper
1800 distance to propose a match that superimposes it on the last
1801 instance of a character that matches it (per trt), or misses
1802 it entirely if there is none. */
1804 dirlen
= len_byte
* direction
;
1806 /* Record position after the end of the pattern. */
1807 pat_end
= base_pat
+ len_byte
;
1808 /* BASE_PAT points to a character that we start scanning from.
1809 It is the first character in a forward search,
1810 the last character in a backward search. */
1812 base_pat
= pat_end
- 1;
1814 /* A character that does not appear in the pattern induces a
1815 stride equal to the pattern length. */
1816 for (i
= 0; i
< 0400; i
++)
1819 /* We use this for translation, instead of TRT itself.
1820 We fill this in to handle the characters that actually
1821 occur in the pattern. Others don't matter anyway! */
1822 for (i
= 0; i
< 0400; i
++)
1823 simple_translate
[i
] = i
;
1827 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1828 byte following them are the target of translation. */
1829 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1830 int cblen
= CHAR_STRING (char_base
, str
);
1832 translate_prev_byte1
= str
[cblen
- 2];
1835 translate_prev_byte2
= str
[cblen
- 3];
1837 translate_prev_byte3
= str
[cblen
- 4];
1844 unsigned char *ptr
= base_pat
+ i
;
1848 /* If the byte currently looking at is the last of a
1849 character to check case-equivalents, set CH to that
1850 character. An ASCII character and a non-ASCII character
1851 matching with CHAR_BASE are to be checked. */
1854 if (ASCII_CHAR_P (*ptr
) || ! multibyte
)
1857 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1859 unsigned char *charstart
= ptr
- 1;
1861 while (! (CHAR_HEAD_P (*charstart
)))
1863 ch
= STRING_CHAR (charstart
);
1864 if (char_base
!= (ch
& ~0x3F))
1868 if (ch
>= 0200 && multibyte
)
1869 j
= (ch
& 0x3F) | 0200;
1874 stride_for_teases
= BM_tab
[j
];
1876 BM_tab
[j
] = dirlen
- i
;
1877 /* A translation table is accompanied by its inverse -- see
1878 comment following downcase_table for details. */
1881 int starting_ch
= ch
;
1886 TRANSLATE (ch
, inverse_trt
, ch
);
1887 if (ch
>= 0200 && multibyte
)
1888 j
= (ch
& 0x3F) | 0200;
1892 /* For all the characters that map into CH,
1893 set up simple_translate to map the last byte
1895 simple_translate
[j
] = starting_j
;
1896 if (ch
== starting_ch
)
1898 BM_tab
[j
] = dirlen
- i
;
1907 stride_for_teases
= BM_tab
[j
];
1908 BM_tab
[j
] = dirlen
- i
;
1910 /* stride_for_teases tells how much to stride if we get a
1911 match on the far character but are subsequently
1912 disappointed, by recording what the stride would have been
1913 for that character if the last character had been
1916 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1917 /* loop invariant - POS_BYTE points at where last char (first
1918 char if reverse) of pattern would align in a possible match. */
1922 unsigned char *tail_end_ptr
;
1924 /* It's been reported that some (broken) compiler thinks that
1925 Boolean expressions in an arithmetic context are unsigned.
1926 Using an explicit ?1:0 prevents this. */
1927 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1929 return (n
* (0 - direction
));
1930 /* First we do the part we can by pointers (maybe nothing) */
1933 limit
= pos_byte
- dirlen
+ direction
;
1936 limit
= BUFFER_CEILING_OF (limit
);
1937 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1938 can take on without hitting edge of buffer or the gap. */
1939 limit
= min (limit
, pos_byte
+ 20000);
1940 limit
= min (limit
, lim_byte
- 1);
1944 limit
= BUFFER_FLOOR_OF (limit
);
1945 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1946 can take on without hitting edge of buffer or the gap. */
1947 limit
= max (limit
, pos_byte
- 20000);
1948 limit
= max (limit
, lim_byte
);
1950 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1951 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1953 if ((limit
- pos_byte
) * direction
> 20)
1957 p_limit
= BYTE_POS_ADDR (limit
);
1958 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1959 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1960 while (1) /* use one cursor setting as long as i can */
1962 if (direction
> 0) /* worth duplicating */
1964 while (cursor
<= p_limit
)
1966 if (BM_tab
[*cursor
] == 0)
1968 cursor
+= BM_tab
[*cursor
];
1973 while (cursor
>= p_limit
)
1975 if (BM_tab
[*cursor
] == 0)
1977 cursor
+= BM_tab
[*cursor
];
1980 /* If you are here, cursor is beyond the end of the
1981 searched region. You fail to match within the
1982 permitted region and would otherwise try a character
1983 beyond that region. */
1987 i
= dirlen
- direction
;
1990 while ((i
-= direction
) + direction
!= 0)
1993 cursor
-= direction
;
1994 /* Translate only the last byte of a character. */
1996 || ((cursor
== tail_end_ptr
1997 || CHAR_HEAD_P (cursor
[1]))
1998 && (CHAR_HEAD_P (cursor
[0])
1999 /* Check if this is the last byte of
2000 a translatable character. */
2001 || (translate_prev_byte1
== cursor
[-1]
2002 && (CHAR_HEAD_P (translate_prev_byte1
)
2003 || (translate_prev_byte2
== cursor
[-2]
2004 && (CHAR_HEAD_P (translate_prev_byte2
)
2005 || (translate_prev_byte3
== cursor
[-3]))))))))
2006 ch
= simple_translate
[*cursor
];
2015 while ((i
-= direction
) + direction
!= 0)
2017 cursor
-= direction
;
2018 if (pat
[i
] != *cursor
)
2022 cursor
+= dirlen
- i
- direction
; /* fix cursor */
2023 if (i
+ direction
== 0)
2025 ptrdiff_t position
, start
, end
;
2027 ptrdiff_t cursor_off
;
2030 cursor
-= direction
;
2032 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
2033 ? 1 - len_byte
: 0);
2035 /* set_search_regs might call malloc, which could
2036 cause ralloc.c relocate buffer text. We need to
2037 update pointers into buffer text due to that. */
2038 cursor_off
= cursor
- p2
;
2040 set_search_regs (position
, len_byte
);
2042 p_limit
= BYTE_POS_ADDR (limit
);
2043 p2
= BYTE_POS_ADDR (pos_byte
);
2044 cursor
= p2
+ cursor_off
;
2047 if (NILP (Vinhibit_changing_match_data
))
2049 start
= search_regs
.start
[0];
2050 end
= search_regs
.end
[0];
2053 /* If Vinhibit_changing_match_data is non-nil,
2054 search_regs will not be changed. So let's
2055 compute start and end here. */
2057 start
= BYTE_TO_CHAR (position
);
2058 end
= BYTE_TO_CHAR (position
+ len_byte
);
2061 if ((n
-= direction
) != 0)
2062 cursor
+= dirlen
; /* to resume search */
2064 return direction
> 0 ? end
: start
;
2067 cursor
+= stride_for_teases
; /* <sigh> we lose - */
2069 pos_byte
+= cursor
- p2
;
2072 /* Now we'll pick up a clump that has to be done the hard
2073 way because it covers a discontinuity. */
2075 limit
= ((direction
> 0)
2076 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
2077 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
2078 limit
= ((direction
> 0)
2079 ? min (limit
+ len_byte
, lim_byte
- 1)
2080 : max (limit
- len_byte
, lim_byte
));
2081 /* LIMIT is now the last value POS_BYTE can have
2082 and still be valid for a possible match. */
2085 /* This loop can be coded for space rather than
2086 speed because it will usually run only once.
2087 (the reach is at most len + 21, and typically
2088 does not exceed len). */
2089 while ((limit
- pos_byte
) * direction
>= 0)
2091 int ch
= FETCH_BYTE (pos_byte
);
2092 if (BM_tab
[ch
] == 0)
2094 pos_byte
+= BM_tab
[ch
];
2096 break; /* ran off the end */
2099 /* Found what might be a match. */
2100 i
= dirlen
- direction
;
2101 while ((i
-= direction
) + direction
!= 0)
2105 pos_byte
-= direction
;
2106 ptr
= BYTE_POS_ADDR (pos_byte
);
2107 /* Translate only the last byte of a character. */
2109 || ((ptr
== tail_end_ptr
2110 || CHAR_HEAD_P (ptr
[1]))
2111 && (CHAR_HEAD_P (ptr
[0])
2112 /* Check if this is the last byte of a
2113 translatable character. */
2114 || (translate_prev_byte1
== ptr
[-1]
2115 && (CHAR_HEAD_P (translate_prev_byte1
)
2116 || (translate_prev_byte2
== ptr
[-2]
2117 && (CHAR_HEAD_P (translate_prev_byte2
)
2118 || translate_prev_byte3
== ptr
[-3])))))))
2119 ch
= simple_translate
[*ptr
];
2125 /* Above loop has moved POS_BYTE part or all the way
2126 back to the first pos (last pos if reverse).
2127 Set it once again at the last (first if reverse) char. */
2128 pos_byte
+= dirlen
- i
- direction
;
2129 if (i
+ direction
== 0)
2131 ptrdiff_t position
, start
, end
;
2132 pos_byte
-= direction
;
2134 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2135 set_search_regs (position
, len_byte
);
2137 if (NILP (Vinhibit_changing_match_data
))
2139 start
= search_regs
.start
[0];
2140 end
= search_regs
.end
[0];
2143 /* If Vinhibit_changing_match_data is non-nil,
2144 search_regs will not be changed. So let's
2145 compute start and end here. */
2147 start
= BYTE_TO_CHAR (position
);
2148 end
= BYTE_TO_CHAR (position
+ len_byte
);
2151 if ((n
-= direction
) != 0)
2152 pos_byte
+= dirlen
; /* to resume search */
2154 return direction
> 0 ? end
: start
;
2157 pos_byte
+= stride_for_teases
;
2160 /* We have done one clump. Can we continue? */
2161 if ((lim_byte
- pos_byte
) * direction
< 0)
2162 return ((0 - n
) * direction
);
2164 return BYTE_TO_CHAR (pos_byte
);
2167 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2168 for the overall match just found in the current buffer.
2169 Also clear out the match data for registers 1 and up. */
2172 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2176 if (!NILP (Vinhibit_changing_match_data
))
2179 /* Make sure we have registers in which to store
2180 the match position. */
2181 if (search_regs
.num_regs
== 0)
2183 search_regs
.start
= xmalloc (2 * sizeof (regoff_t
));
2184 search_regs
.end
= xmalloc (2 * sizeof (regoff_t
));
2185 search_regs
.num_regs
= 2;
2188 /* Clear out the other registers. */
2189 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2191 search_regs
.start
[i
] = -1;
2192 search_regs
.end
[i
] = -1;
2195 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2196 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2197 XSETBUFFER (last_thing_searched
, current_buffer
);
2200 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2201 "MSearch backward: ",
2202 doc
: /* Search backward from point for STRING.
2203 Set point to the beginning of the occurrence found, and return point.
2204 An optional second argument bounds the search; it is a buffer position.
2205 The match found must not begin before that position. A value of nil
2206 means search to the beginning of the accessible portion of the buffer.
2207 Optional third argument, if t, means if fail just return nil (no error).
2208 If not nil and not t, position at limit of search and return nil.
2209 Optional fourth argument COUNT, if a positive number, means to search
2210 for COUNT successive occurrences. If COUNT is negative, search
2211 forward, instead of backward, for -COUNT occurrences. A value of
2212 nil means the same as 1.
2213 With COUNT positive, the match found is the COUNTth to last one (or
2214 last, if COUNT is 1 or nil) in the buffer located entirely before
2215 the origin of the search; correspondingly with COUNT negative.
2217 Search case-sensitivity is determined by the value of the variable
2218 `case-fold-search', which see.
2220 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2221 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2223 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2226 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2227 doc
: /* Search forward from point for STRING.
2228 Set point to the end of the occurrence found, and return point.
2229 An optional second argument bounds the search; it is a buffer position.
2230 The match found must not end after that position. A value of nil
2231 means search to the end of the accessible portion of the buffer.
2232 Optional third argument, if t, means if fail just return nil (no error).
2233 If not nil and not t, move to limit of search and return nil.
2234 Optional fourth argument COUNT, if a positive number, means to search
2235 for COUNT successive occurrences. If COUNT is negative, search
2236 backward, instead of forward, for -COUNT occurrences. A value of
2237 nil means the same as 1.
2238 With COUNT positive, the match found is the COUNTth one (or first,
2239 if COUNT is 1 or nil) in the buffer located entirely after the
2240 origin of the search; correspondingly with COUNT negative.
2242 Search case-sensitivity is determined by the value of the variable
2243 `case-fold-search', which see.
2245 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2246 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2248 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2251 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2252 "sRE search backward: ",
2253 doc
: /* Search backward from point for match for regular expression REGEXP.
2254 Set point to the beginning of the occurrence found, and return point.
2255 An optional second argument bounds the search; it is a buffer position.
2256 The match found must not begin before that position. A value of nil
2257 means search to the beginning of the accessible portion of the buffer.
2258 Optional third argument, if t, means if fail just return nil (no error).
2259 If not nil and not t, position at limit of search and return nil.
2260 Optional fourth argument COUNT, if a positive number, means to search
2261 for COUNT successive occurrences. If COUNT is negative, search
2262 forward, instead of backward, for -COUNT occurrences. A value of
2263 nil means the same as 1.
2264 With COUNT positive, the match found is the COUNTth to last one (or
2265 last, if COUNT is 1 or nil) in the buffer located entirely before
2266 the origin of the search; correspondingly with COUNT negative.
2268 Search case-sensitivity is determined by the value of the variable
2269 `case-fold-search', which see.
2271 See also the functions `match-beginning', `match-end', `match-string',
2272 and `replace-match'. */)
2273 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2275 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2278 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2280 doc
: /* Search forward from point for regular expression REGEXP.
2281 Set point to the end of the occurrence found, and return point.
2282 An optional second argument bounds the search; it is a buffer position.
2283 The match found must not end after that position. A value of nil
2284 means search to the end of the accessible portion of the buffer.
2285 Optional third argument, if t, means if fail just return nil (no error).
2286 If not nil and not t, move to limit of search and return nil.
2287 Optional fourth argument COUNT, if a positive number, means to search
2288 for COUNT successive occurrences. If COUNT is negative, search
2289 backward, instead of forward, for -COUNT occurrences. A value of
2290 nil means the same as 1.
2291 With COUNT positive, the match found is the COUNTth one (or first,
2292 if COUNT is 1 or nil) in the buffer located entirely after the
2293 origin of the search; correspondingly with COUNT negative.
2295 Search case-sensitivity is determined by the value of the variable
2296 `case-fold-search', which see.
2298 See also the functions `match-beginning', `match-end', `match-string',
2299 and `replace-match'. */)
2300 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2302 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2305 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2306 "sPosix search backward: ",
2307 doc
: /* Search backward from point for match for regular expression REGEXP.
2308 Find the longest match in accord with Posix regular expression rules.
2309 Set point to the beginning of the occurrence found, and return point.
2310 An optional second argument bounds the search; it is a buffer position.
2311 The match found must not begin before that position. A value of nil
2312 means search to the beginning of the accessible portion of the buffer.
2313 Optional third argument, if t, means if fail just return nil (no error).
2314 If not nil and not t, position at limit of search and return nil.
2315 Optional fourth argument COUNT, if a positive number, means to search
2316 for COUNT successive occurrences. If COUNT is negative, search
2317 forward, instead of backward, for -COUNT occurrences. A value of
2318 nil means the same as 1.
2319 With COUNT positive, the match found is the COUNTth to last one (or
2320 last, if COUNT is 1 or nil) in the buffer located entirely before
2321 the origin of the search; correspondingly with COUNT negative.
2323 Search case-sensitivity is determined by the value of the variable
2324 `case-fold-search', which see.
2326 See also the functions `match-beginning', `match-end', `match-string',
2327 and `replace-match'. */)
2328 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2330 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2333 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2335 doc
: /* Search forward from point for regular expression REGEXP.
2336 Find the longest match in accord with Posix regular expression rules.
2337 Set point to the end of the occurrence found, and return point.
2338 An optional second argument bounds the search; it is a buffer position.
2339 The match found must not end after that position. A value of nil
2340 means search to the end of the accessible portion of the buffer.
2341 Optional third argument, if t, means if fail just return nil (no error).
2342 If not nil and not t, move to limit of search and return nil.
2343 Optional fourth argument COUNT, if a positive number, means to search
2344 for COUNT successive occurrences. If COUNT is negative, search
2345 backward, instead of forward, for -COUNT occurrences. A value of
2346 nil means the same as 1.
2347 With COUNT positive, the match found is the COUNTth one (or first,
2348 if COUNT is 1 or nil) in the buffer located entirely after the
2349 origin of the search; correspondingly with COUNT negative.
2351 Search case-sensitivity is determined by the value of the variable
2352 `case-fold-search', which see.
2354 See also the functions `match-beginning', `match-end', `match-string',
2355 and `replace-match'. */)
2356 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2358 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2361 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2362 doc
: /* Replace text matched by last search with NEWTEXT.
2363 Leave point at the end of the replacement text.
2365 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2366 the replacement text. Otherwise, maybe capitalize the whole text, or
2367 maybe just word initials, based on the replaced text. If the replaced
2368 text has only capital letters and has at least one multiletter word,
2369 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2370 in the replaced text, capitalize each word in NEWTEXT.
2372 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2373 Otherwise treat `\\' as special:
2374 `\\&' in NEWTEXT means substitute original matched text.
2375 `\\N' means substitute what matched the Nth `\\(...\\)'.
2376 If Nth parens didn't match, substitute nothing.
2377 `\\\\' means insert one `\\'.
2378 `\\?' is treated literally
2379 (for compatibility with `query-replace-regexp').
2380 Any other character following `\\' signals an error.
2381 Case conversion does not apply to these substitutions.
2383 If optional fourth argument STRING is non-nil, it should be a string
2384 to act on; this should be the string on which the previous match was
2385 done via `string-match'. In this case, `replace-match' creates and
2386 returns a new string, made by copying STRING and replacing the part of
2387 STRING that was matched (the original STRING itself is not altered).
2389 The optional fifth argument SUBEXP specifies a subexpression;
2390 it says to replace just that subexpression with NEWTEXT,
2391 rather than replacing the entire matched text.
2392 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2393 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2394 NEWTEXT in place of subexp N.
2395 This is useful only after a regular expression search or match,
2396 since only regular expressions have distinguished subexpressions. */)
2397 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2399 enum { nochange
, all_caps
, cap_initial
} case_action
;
2400 ptrdiff_t pos
, pos_byte
;
2401 bool some_multiletter_word
;
2402 bool some_lowercase
;
2403 bool some_uppercase
;
2404 bool some_nonuppercase_initial
;
2407 ptrdiff_t opoint
, newpoint
;
2409 CHECK_STRING (newtext
);
2411 if (! NILP (string
))
2412 CHECK_STRING (string
);
2414 case_action
= nochange
; /* We tried an initialization */
2415 /* but some C compilers blew it */
2417 if (search_regs
.num_regs
<= 0)
2418 error ("`replace-match' called before any match found");
2424 CHECK_NUMBER (subexp
);
2425 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2426 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2427 sub
= XINT (subexp
);
2432 if (search_regs
.start
[sub
] < BEGV
2433 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2434 || search_regs
.end
[sub
] > ZV
)
2435 args_out_of_range (make_number (search_regs
.start
[sub
]),
2436 make_number (search_regs
.end
[sub
]));
2440 if (search_regs
.start
[sub
] < 0
2441 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2442 || search_regs
.end
[sub
] > SCHARS (string
))
2443 args_out_of_range (make_number (search_regs
.start
[sub
]),
2444 make_number (search_regs
.end
[sub
]));
2447 if (NILP (fixedcase
))
2449 /* Decide how to casify by examining the matched text. */
2452 pos
= search_regs
.start
[sub
];
2453 last
= search_regs
.end
[sub
];
2456 pos_byte
= CHAR_TO_BYTE (pos
);
2458 pos_byte
= string_char_to_byte (string
, pos
);
2461 case_action
= all_caps
;
2463 /* some_multiletter_word is set nonzero if any original word
2464 is more than one letter long. */
2465 some_multiletter_word
= 0;
2467 some_nonuppercase_initial
= 0;
2474 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2475 INC_BOTH (pos
, pos_byte
);
2478 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2482 /* Cannot be all caps if any original char is lower case */
2485 if (SYNTAX (prevc
) != Sword
)
2486 some_nonuppercase_initial
= 1;
2488 some_multiletter_word
= 1;
2490 else if (uppercasep (c
))
2493 if (SYNTAX (prevc
) != Sword
)
2496 some_multiletter_word
= 1;
2500 /* If the initial is a caseless word constituent,
2501 treat that like a lowercase initial. */
2502 if (SYNTAX (prevc
) != Sword
)
2503 some_nonuppercase_initial
= 1;
2509 /* Convert to all caps if the old text is all caps
2510 and has at least one multiletter word. */
2511 if (! some_lowercase
&& some_multiletter_word
)
2512 case_action
= all_caps
;
2513 /* Capitalize each word, if the old text has all capitalized words. */
2514 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2515 case_action
= cap_initial
;
2516 else if (!some_nonuppercase_initial
&& some_uppercase
)
2517 /* Should x -> yz, operating on X, give Yz or YZ?
2518 We'll assume the latter. */
2519 case_action
= all_caps
;
2521 case_action
= nochange
;
2524 /* Do replacement in a string. */
2527 Lisp_Object before
, after
;
2529 before
= Fsubstring (string
, make_number (0),
2530 make_number (search_regs
.start
[sub
]));
2531 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2533 /* Substitute parts of the match into NEWTEXT
2537 ptrdiff_t lastpos
= 0;
2538 ptrdiff_t lastpos_byte
= 0;
2539 /* We build up the substituted string in ACCUM. */
2542 ptrdiff_t length
= SBYTES (newtext
);
2546 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2548 ptrdiff_t substart
= -1;
2549 ptrdiff_t subend
= 0;
2550 bool delbackslash
= 0;
2552 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2556 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2560 substart
= search_regs
.start
[sub
];
2561 subend
= search_regs
.end
[sub
];
2563 else if (c
>= '1' && c
<= '9')
2565 if (c
- '0' < search_regs
.num_regs
2566 && search_regs
.start
[c
- '0'] >= 0)
2568 substart
= search_regs
.start
[c
- '0'];
2569 subend
= search_regs
.end
[c
- '0'];
2573 /* If that subexp did not match,
2574 replace \\N with nothing. */
2582 error ("Invalid use of `\\' in replacement text");
2586 if (pos
- 2 != lastpos
)
2587 middle
= substring_both (newtext
, lastpos
,
2589 pos
- 2, pos_byte
- 2);
2592 accum
= concat3 (accum
, middle
,
2594 make_number (substart
),
2595 make_number (subend
)));
2597 lastpos_byte
= pos_byte
;
2599 else if (delbackslash
)
2601 middle
= substring_both (newtext
, lastpos
,
2603 pos
- 1, pos_byte
- 1);
2605 accum
= concat2 (accum
, middle
);
2607 lastpos_byte
= pos_byte
;
2612 middle
= substring_both (newtext
, lastpos
,
2618 newtext
= concat2 (accum
, middle
);
2621 /* Do case substitution in NEWTEXT if desired. */
2622 if (case_action
== all_caps
)
2623 newtext
= Fupcase (newtext
);
2624 else if (case_action
== cap_initial
)
2625 newtext
= Fupcase_initials (newtext
);
2627 return concat3 (before
, newtext
, after
);
2630 /* Record point, then move (quietly) to the start of the match. */
2631 if (PT
>= search_regs
.end
[sub
])
2633 else if (PT
> search_regs
.start
[sub
])
2634 opoint
= search_regs
.end
[sub
] - ZV
;
2638 /* If we want non-literal replacement,
2639 perform substitution on the replacement string. */
2642 ptrdiff_t length
= SBYTES (newtext
);
2643 unsigned char *substed
;
2644 ptrdiff_t substed_alloc_size
, substed_len
;
2645 bool buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2646 bool str_multibyte
= STRING_MULTIBYTE (newtext
);
2647 bool really_changed
= 0;
2649 substed_alloc_size
= (length
<= (STRING_BYTES_BOUND
- 100) / 2
2651 : STRING_BYTES_BOUND
);
2652 substed
= xmalloc (substed_alloc_size
);
2655 /* Go thru NEWTEXT, producing the actual text to insert in
2656 SUBSTED while adjusting multibyteness to that of the current
2659 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2661 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2662 const unsigned char *add_stuff
= NULL
;
2663 ptrdiff_t add_len
= 0;
2669 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2671 c
= CHAR_TO_BYTE8 (c
);
2675 /* Note that we don't have to increment POS. */
2676 c
= SREF (newtext
, pos_byte
++);
2678 MAKE_CHAR_MULTIBYTE (c
);
2681 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2682 or set IDX to a match index, which means put that part
2683 of the buffer text into SUBSTED. */
2691 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2693 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2694 c
= CHAR_TO_BYTE8 (c
);
2698 c
= SREF (newtext
, pos_byte
++);
2700 MAKE_CHAR_MULTIBYTE (c
);
2705 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2707 if (search_regs
.start
[c
- '0'] >= 1)
2711 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2715 error ("Invalid use of `\\' in replacement text");
2720 add_len
= CHAR_STRING (c
, str
);
2724 /* If we want to copy part of a previous match,
2725 set up ADD_STUFF and ADD_LEN to point to it. */
2728 begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2729 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2730 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2731 move_gap_both (search_regs
.start
[idx
], begbyte
);
2734 /* Now the stuff we want to add to SUBSTED
2735 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2737 /* Make sure SUBSTED is big enough. */
2738 if (substed_alloc_size
- substed_len
< add_len
)
2740 xpalloc (substed
, &substed_alloc_size
,
2741 add_len
- (substed_alloc_size
- substed_len
),
2742 STRING_BYTES_BOUND
, 1);
2744 /* We compute this after the call to xpalloc, because that
2745 could cause buffer text be relocated when ralloc.c is used. */
2747 add_stuff
= BYTE_POS_ADDR (begbyte
);
2749 /* Now add to the end of SUBSTED. */
2752 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2753 substed_len
+= add_len
;
2758 newtext
= make_specified_string ((const char *) substed
, -1,
2759 substed_len
, buf_multibyte
);
2763 /* The functions below modify the buffer, so they could trigger
2764 various modification hooks (see signal_before_change and
2765 signal_after_change). If these hooks clobber the match data we
2766 error out since otherwise this will result in confusing bugs. */
2767 ptrdiff_t sub_start
= search_regs
.start
[sub
];
2768 ptrdiff_t sub_end
= search_regs
.end
[sub
];
2769 unsigned num_regs
= search_regs
.num_regs
;
2770 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2772 /* Replace the old text with the new in the cleanest possible way. */
2773 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2774 newtext
, 1, 0, 1, 1);
2775 /* Update saved data to match adjustment made by replace_range. */
2777 ptrdiff_t change
= newpoint
- sub_end
;
2778 if (sub_start
>= sub_end
)
2779 sub_start
+= change
;
2783 if (case_action
== all_caps
)
2784 Fupcase_region (make_number (search_regs
.start
[sub
]),
2785 make_number (newpoint
),
2787 else if (case_action
== cap_initial
)
2788 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2789 make_number (newpoint
));
2791 if (search_regs
.start
[sub
] != sub_start
2792 || search_regs
.end
[sub
] != sub_end
2793 || search_regs
.num_regs
!= num_regs
)
2794 error ("Match data clobbered by buffer modification hooks");
2796 /* Put point back where it was in the text. */
2798 TEMP_SET_PT (opoint
+ ZV
);
2800 TEMP_SET_PT (opoint
);
2802 /* Now move point "officially" to the start of the inserted replacement. */
2803 move_if_not_intangible (newpoint
);
2809 match_limit (Lisp_Object num
, bool beginningp
)
2816 args_out_of_range (num
, make_number (0));
2817 if (search_regs
.num_regs
<= 0)
2818 error ("No match data, because no search succeeded");
2819 if (n
>= search_regs
.num_regs
2820 || search_regs
.start
[n
] < 0)
2822 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2823 : search_regs
.end
[n
]));
2826 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2827 doc
: /* Return position of start of text matched by last search.
2828 SUBEXP, a number, specifies which parenthesized expression in the last
2830 Value is nil if SUBEXPth pair didn't match, or there were less than
2832 Zero means the entire text matched by the whole regexp or whole string.
2834 Return value is undefined if the last search failed. */)
2835 (Lisp_Object subexp
)
2837 return match_limit (subexp
, 1);
2840 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2841 doc
: /* Return position of end of text matched by last search.
2842 SUBEXP, a number, specifies which parenthesized expression in the last
2844 Value is nil if SUBEXPth pair didn't match, or there were less than
2846 Zero means the entire text matched by the whole regexp or whole string.
2848 Return value is undefined if the last search failed. */)
2849 (Lisp_Object subexp
)
2851 return match_limit (subexp
, 0);
2854 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2855 doc
: /* Return a list describing what the last search matched.
2856 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2857 All the elements are markers or nil (nil if the Nth pair didn't match)
2858 if the last match was on a buffer; integers or nil if a string was matched.
2859 Use `set-match-data' to reinstate the data in this list.
2861 If INTEGERS (the optional first argument) is non-nil, always use
2862 integers (rather than markers) to represent buffer positions. In
2863 this case, and if the last match was in a buffer, the buffer will get
2864 stored as one additional element at the end of the list.
2866 If REUSE is a list, reuse it as part of the value. If REUSE is long
2867 enough to hold all the values, and if INTEGERS is non-nil, no consing
2870 If optional third arg RESEAT is non-nil, any previous markers on the
2871 REUSE list will be modified to point to nowhere.
2873 Return value is undefined if the last search failed. */)
2874 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2876 Lisp_Object tail
, prev
;
2881 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2882 if (MARKERP (XCAR (tail
)))
2884 unchain_marker (XMARKER (XCAR (tail
)));
2885 XSETCAR (tail
, Qnil
);
2888 if (NILP (last_thing_searched
))
2894 SAFE_NALLOCA (data
, 1, 2 * search_regs
.num_regs
+ 1);
2897 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2899 ptrdiff_t start
= search_regs
.start
[i
];
2902 if (EQ (last_thing_searched
, Qt
)
2903 || ! NILP (integers
))
2905 XSETFASTINT (data
[2 * i
], start
);
2906 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2908 else if (BUFFERP (last_thing_searched
))
2910 data
[2 * i
] = Fmake_marker ();
2911 Fset_marker (data
[2 * i
],
2912 make_number (start
),
2913 last_thing_searched
);
2914 data
[2 * i
+ 1] = Fmake_marker ();
2915 Fset_marker (data
[2 * i
+ 1],
2916 make_number (search_regs
.end
[i
]),
2917 last_thing_searched
);
2920 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2926 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2929 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2931 data
[len
] = last_thing_searched
;
2935 /* If REUSE is not usable, cons up the values and return them. */
2936 if (! CONSP (reuse
))
2937 reuse
= Flist (len
, data
);
2940 /* If REUSE is a list, store as many value elements as will fit
2941 into the elements of REUSE. */
2942 for (i
= 0, tail
= reuse
; CONSP (tail
);
2943 i
++, tail
= XCDR (tail
))
2946 XSETCAR (tail
, data
[i
]);
2948 XSETCAR (tail
, Qnil
);
2952 /* If we couldn't fit all value elements into REUSE,
2953 cons up the rest of them and add them to the end of REUSE. */
2955 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2962 /* We used to have an internal use variant of `reseat' described as:
2964 If RESEAT is `evaporate', put the markers back on the free list
2965 immediately. No other references to the markers must exist in this
2966 case, so it is used only internally on the unwind stack and
2967 save-match-data from Lisp.
2969 But it was ill-conceived: those supposedly-internal markers get exposed via
2970 the undo-list, so freeing them here is unsafe. */
2972 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2973 doc
: /* Set internal data on last search match from elements of LIST.
2974 LIST should have been created by calling `match-data' previously.
2976 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2977 (register Lisp_Object list
, Lisp_Object reseat
)
2980 register Lisp_Object marker
;
2982 if (running_asynch_code
)
2983 save_search_regs ();
2987 /* Unless we find a marker with a buffer or an explicit buffer
2988 in LIST, assume that this match data came from a string. */
2989 last_thing_searched
= Qt
;
2991 /* Allocate registers if they don't already exist. */
2993 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
2995 if (length
> search_regs
.num_regs
)
2997 ptrdiff_t num_regs
= search_regs
.num_regs
;
2998 if (PTRDIFF_MAX
< length
)
2999 memory_full (SIZE_MAX
);
3001 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
3002 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
3004 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
3006 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
3007 search_regs
.start
[i
] = -1;
3009 search_regs
.num_regs
= num_regs
;
3012 for (i
= 0; CONSP (list
); i
++)
3014 marker
= XCAR (list
);
3015 if (BUFFERP (marker
))
3017 last_thing_searched
= marker
;
3024 search_regs
.start
[i
] = -1;
3033 if (MARKERP (marker
))
3035 if (XMARKER (marker
)->buffer
== 0)
3036 XSETFASTINT (marker
, 0);
3038 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
3041 CHECK_NUMBER_COERCE_MARKER (marker
);
3044 if (!NILP (reseat
) && MARKERP (m
))
3046 unchain_marker (XMARKER (m
));
3047 XSETCAR (list
, Qnil
);
3050 if ((list
= XCDR (list
), !CONSP (list
)))
3053 m
= marker
= XCAR (list
);
3055 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
3056 XSETFASTINT (marker
, 0);
3058 CHECK_NUMBER_COERCE_MARKER (marker
);
3059 if ((XINT (from
) < 0
3060 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
3061 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
3062 && (XINT (marker
) < 0
3063 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
3064 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
3066 search_regs
.start
[i
] = XINT (from
);
3067 search_regs
.end
[i
] = XINT (marker
);
3071 search_regs
.start
[i
] = -1;
3074 if (!NILP (reseat
) && MARKERP (m
))
3076 unchain_marker (XMARKER (m
));
3077 XSETCAR (list
, Qnil
);
3083 for (; i
< search_regs
.num_regs
; i
++)
3084 search_regs
.start
[i
] = -1;
3090 /* If true the match data have been saved in saved_search_regs
3091 during the execution of a sentinel or filter. */
3092 static bool search_regs_saved
;
3093 static struct re_registers saved_search_regs
;
3094 static Lisp_Object saved_last_thing_searched
;
3096 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3097 if asynchronous code (filter or sentinel) is running. */
3099 save_search_regs (void)
3101 if (!search_regs_saved
)
3103 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3104 saved_search_regs
.start
= search_regs
.start
;
3105 saved_search_regs
.end
= search_regs
.end
;
3106 saved_last_thing_searched
= last_thing_searched
;
3107 last_thing_searched
= Qnil
;
3108 search_regs
.num_regs
= 0;
3109 search_regs
.start
= 0;
3110 search_regs
.end
= 0;
3112 search_regs_saved
= 1;
3116 /* Called upon exit from filters and sentinels. */
3118 restore_search_regs (void)
3120 if (search_regs_saved
)
3122 if (search_regs
.num_regs
> 0)
3124 xfree (search_regs
.start
);
3125 xfree (search_regs
.end
);
3127 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3128 search_regs
.start
= saved_search_regs
.start
;
3129 search_regs
.end
= saved_search_regs
.end
;
3130 last_thing_searched
= saved_last_thing_searched
;
3131 saved_last_thing_searched
= Qnil
;
3132 search_regs_saved
= 0;
3136 /* Called from replace-match via replace_range. */
3138 update_search_regs (ptrdiff_t oldstart
, ptrdiff_t oldend
, ptrdiff_t newend
)
3140 /* Adjust search data for this change. */
3141 ptrdiff_t change
= newend
- oldend
;
3144 for (i
= 0; i
< search_regs
.num_regs
; i
++)
3146 if (search_regs
.start
[i
] >= oldend
)
3147 search_regs
.start
[i
] += change
;
3148 else if (search_regs
.start
[i
] > oldstart
)
3149 search_regs
.start
[i
] = oldstart
;
3150 if (search_regs
.end
[i
] >= oldend
)
3151 search_regs
.end
[i
] += change
;
3152 else if (search_regs
.end
[i
] > oldstart
)
3153 search_regs
.end
[i
] = oldstart
;
3158 unwind_set_match_data (Lisp_Object list
)
3160 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3161 Fset_match_data (list
, Qt
);
3164 /* Called to unwind protect the match data. */
3166 record_unwind_save_match_data (void)
3168 record_unwind_protect (unwind_set_match_data
,
3169 Fmatch_data (Qnil
, Qnil
, Qnil
));
3172 /* Quote a string to deactivate reg-expr chars */
3174 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3175 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3176 (Lisp_Object string
)
3178 char *in
, *out
, *end
;
3180 ptrdiff_t backslashes_added
= 0;
3182 CHECK_STRING (string
);
3185 SAFE_NALLOCA (temp
, 2, SBYTES (string
));
3187 /* Now copy the data into the new string, inserting escapes. */
3189 in
= SSDATA (string
);
3190 end
= in
+ SBYTES (string
);
3193 for (; in
!= end
; in
++)
3196 || *in
== '*' || *in
== '.' || *in
== '\\'
3197 || *in
== '?' || *in
== '+'
3198 || *in
== '^' || *in
== '$')
3199 *out
++ = '\\', backslashes_added
++;
3204 = make_specified_string (temp
,
3205 SCHARS (string
) + backslashes_added
,
3207 STRING_MULTIBYTE (string
));
3212 /* Like find_newline, but doesn't use the cache, and only searches forward. */
3214 find_newline1 (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
3215 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
3216 ptrdiff_t *bytepos
, bool allow_quit
)
3221 end
= ZV
, end_byte
= ZV_BYTE
;
3226 end
= BEGV
, end_byte
= BEGV_BYTE
;
3229 end_byte
= CHAR_TO_BYTE (end
);
3234 immediate_quit
= allow_quit
;
3237 while (start
!= end
)
3239 /* Our innermost scanning loop is very simple; it doesn't know
3240 about gaps, buffer ends, or the newline cache. ceiling is
3241 the position of the last character before the next such
3242 obstacle --- the last character the dumb search loop should
3244 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
3246 if (start_byte
== -1)
3247 start_byte
= CHAR_TO_BYTE (start
);
3249 /* The dumb loop can only scan text stored in contiguous
3250 bytes. BUFFER_CEILING_OF returns the last character
3251 position that is contiguous, so the ceiling is the
3252 position after that. */
3253 tem
= BUFFER_CEILING_OF (start_byte
);
3254 ceiling_byte
= min (tem
, ceiling_byte
);
3257 /* The termination address of the dumb loop. */
3258 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
3259 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
3261 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
3262 of the base, the cursor, and the next line. */
3263 ptrdiff_t base
= start_byte
- lim_byte
;
3264 ptrdiff_t cursor
, next
;
3266 for (cursor
= base
; cursor
< 0; cursor
= next
)
3268 /* The dumb loop. */
3269 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
3270 next
= nl
? nl
- lim_addr
: 0;
3280 *bytepos
= lim_byte
+ next
;
3281 return BYTE_TO_CHAR (lim_byte
+ next
);
3285 start_byte
= lim_byte
;
3286 start
= BYTE_TO_CHAR (start_byte
);
3295 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
3296 eassert (*bytepos
== CHAR_TO_BYTE (start
));
3301 DEFUN ("newline-cache-check", Fnewline_cache_check
, Snewline_cache_check
,
3303 doc
: /* Check the newline cache of BUFFER against buffer contents.
3305 BUFFER defaults to the current buffer.
3307 Value is an array of 2 sub-arrays of buffer positions for newlines,
3308 the first based on the cache, the second based on actually scanning
3309 the buffer. If the buffer doesn't have a cache, the value is nil. */)
3310 (Lisp_Object buffer
)
3312 struct buffer
*buf
, *old
= NULL
;
3313 ptrdiff_t shortage
, nl_count_cache
, nl_count_buf
;
3314 Lisp_Object cache_newlines
, buf_newlines
, val
;
3315 ptrdiff_t from
, found
, i
;
3318 buf
= current_buffer
;
3321 CHECK_BUFFER (buffer
);
3322 buf
= XBUFFER (buffer
);
3323 old
= current_buffer
;
3325 if (buf
->base_buffer
)
3326 buf
= buf
->base_buffer
;
3328 /* If the buffer doesn't have a newline cache, return nil. */
3329 if (NILP (BVAR (buf
, cache_long_scans
))
3330 || buf
->newline_cache
== NULL
)
3333 /* find_newline can only work on the current buffer. */
3335 set_buffer_internal_1 (buf
);
3337 /* How many newlines are there according to the cache? */
3338 find_newline (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3339 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3340 nl_count_cache
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3342 /* Create vector and populate it. */
3343 cache_newlines
= make_uninit_vector (nl_count_cache
);
3347 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3349 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3351 found
= find_newline (from
, from_byte
, 0, -1, 1, &shortage
,
3353 if (shortage
!= 0 || i
>= nl_count_cache
)
3355 ASET (cache_newlines
, i
, make_number (found
- 1));
3357 /* Fill the rest of slots with an invalid position. */
3358 for ( ; i
< nl_count_cache
; i
++)
3359 ASET (cache_newlines
, i
, make_number (-1));
3362 /* Now do the same, but without using the cache. */
3363 find_newline1 (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3364 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3365 nl_count_buf
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3366 buf_newlines
= make_uninit_vector (nl_count_buf
);
3369 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3371 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3373 found
= find_newline1 (from
, from_byte
, 0, -1, 1, &shortage
,
3375 if (shortage
!= 0 || i
>= nl_count_buf
)
3377 ASET (buf_newlines
, i
, make_number (found
- 1));
3379 for ( ; i
< nl_count_buf
; i
++)
3380 ASET (buf_newlines
, i
, make_number (-1));
3383 /* Construct the value and return it. */
3384 val
= make_uninit_vector (2);
3385 ASET (val
, 0, cache_newlines
);
3386 ASET (val
, 1, buf_newlines
);
3389 set_buffer_internal_1 (old
);
3394 syms_of_search (void)
3398 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3400 searchbufs
[i
].buf
.allocated
= 100;
3401 searchbufs
[i
].buf
.buffer
= xmalloc (100);
3402 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3403 searchbufs
[i
].regexp
= Qnil
;
3404 searchbufs
[i
].whitespace_regexp
= Qnil
;
3405 searchbufs
[i
].syntax_table
= Qnil
;
3406 staticpro (&searchbufs
[i
].regexp
);
3407 staticpro (&searchbufs
[i
].whitespace_regexp
);
3408 staticpro (&searchbufs
[i
].syntax_table
);
3409 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3411 searchbuf_head
= &searchbufs
[0];
3413 /* Error condition used for failing searches. */
3414 DEFSYM (Qsearch_failed
, "search-failed");
3416 /* Error condition signaled when regexp compile_pattern fails. */
3417 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3419 Fput (Qsearch_failed
, Qerror_conditions
,
3420 listn (CONSTYPE_PURE
, 2, Qsearch_failed
, Qerror
));
3421 Fput (Qsearch_failed
, Qerror_message
,
3422 build_pure_c_string ("Search failed"));
3424 Fput (Qinvalid_regexp
, Qerror_conditions
,
3425 listn (CONSTYPE_PURE
, 2, Qinvalid_regexp
, Qerror
));
3426 Fput (Qinvalid_regexp
, Qerror_message
,
3427 build_pure_c_string ("Invalid regexp"));
3429 last_thing_searched
= Qnil
;
3430 staticpro (&last_thing_searched
);
3432 saved_last_thing_searched
= Qnil
;
3433 staticpro (&saved_last_thing_searched
);
3435 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3436 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3437 Some commands use this for user-specified regexps.
3438 Spaces that occur inside character classes or repetition operators
3439 or other such regexp constructs are not replaced with this.
3440 A value of nil (which is the normal value) means treat spaces literally. */);
3441 Vsearch_spaces_regexp
= Qnil
;
3443 DEFSYM (Qinhibit_changing_match_data
, "inhibit-changing-match-data");
3444 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3445 doc
: /* Internal use only.
3446 If non-nil, the primitive searching and matching functions
3447 such as `looking-at', `string-match', `re-search-forward', etc.,
3448 do not set the match data. The proper way to use this variable
3449 is to bind it with `let' around a small expression. */);
3450 Vinhibit_changing_match_data
= Qnil
;
3452 defsubr (&Slooking_at
);
3453 defsubr (&Sposix_looking_at
);
3454 defsubr (&Sstring_match
);
3455 defsubr (&Sposix_string_match
);
3456 defsubr (&Ssearch_forward
);
3457 defsubr (&Ssearch_backward
);
3458 defsubr (&Sre_search_forward
);
3459 defsubr (&Sre_search_backward
);
3460 defsubr (&Sposix_search_forward
);
3461 defsubr (&Sposix_search_backward
);
3462 defsubr (&Sreplace_match
);
3463 defsubr (&Smatch_beginning
);
3464 defsubr (&Smatch_end
);
3465 defsubr (&Smatch_data
);
3466 defsubr (&Sset_match_data
);
3467 defsubr (&Sregexp_quote
);
3468 defsubr (&Snewline_cache_check
);