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
)
120 cp
->buf
.translate
= (! NILP (translate
) ? translate
: make_number (0));
122 cp
->buf
.multibyte
= STRING_MULTIBYTE (pattern
);
123 cp
->buf
.charset_unibyte
= charset_unibyte
;
124 if (STRINGP (Vsearch_spaces_regexp
))
125 cp
->whitespace_regexp
= Vsearch_spaces_regexp
;
127 cp
->whitespace_regexp
= Qnil
;
129 /* rms: I think BLOCK_INPUT is not needed here any more,
130 because regex.c defines malloc to call xmalloc.
131 Using BLOCK_INPUT here means the debugger won't run if an error occurs.
132 So let's turn it off. */
134 old
= re_set_syntax (RE_SYNTAX_EMACS
135 | (posix
? 0 : RE_NO_POSIX_BACKTRACKING
));
137 if (STRINGP (Vsearch_spaces_regexp
))
138 re_set_whitespace_regexp (SSDATA (Vsearch_spaces_regexp
));
140 re_set_whitespace_regexp (NULL
);
142 val
= (char *) re_compile_pattern (SSDATA (pattern
),
143 SBYTES (pattern
), &cp
->buf
);
145 /* If the compiled pattern hard codes some of the contents of the
146 syntax-table, it can only be reused with *this* syntax table. */
147 cp
->syntax_table
= cp
->buf
.used_syntax
? BVAR (current_buffer
, syntax_table
) : Qt
;
149 re_set_whitespace_regexp (NULL
);
152 /* unblock_input (); */
154 xsignal1 (Qinvalid_regexp
, build_string (val
));
156 cp
->regexp
= Fcopy_sequence (pattern
);
159 /* Shrink each compiled regexp buffer in the cache
160 to the size actually used right now.
161 This is called from garbage collection. */
164 shrink_regexp_cache (void)
166 struct regexp_cache
*cp
;
168 for (cp
= searchbuf_head
; cp
!= 0; cp
= cp
->next
)
170 cp
->buf
.allocated
= cp
->buf
.used
;
171 cp
->buf
.buffer
= xrealloc (cp
->buf
.buffer
, cp
->buf
.used
);
175 /* Clear the regexp cache w.r.t. a particular syntax table,
176 because it was changed.
177 There is no danger of memory leak here because re_compile_pattern
178 automagically manages the memory in each re_pattern_buffer struct,
179 based on its `allocated' and `buffer' values. */
181 clear_regexp_cache (void)
185 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
186 /* It's tempting to compare with the syntax-table we've actually changed,
187 but it's not sufficient because char-table inheritance means that
188 modifying one syntax-table can change others at the same time. */
189 if (!EQ (searchbufs
[i
].syntax_table
, Qt
))
190 searchbufs
[i
].regexp
= Qnil
;
193 /* Compile a regexp if necessary, but first check to see if there's one in
195 PATTERN is the pattern to compile.
196 TRANSLATE is a translation table for ignoring case, or nil for none.
197 REGP is the structure that says where to store the "register"
198 values that will result from matching this pattern.
199 If it is 0, we should compile the pattern not to record any
200 subexpression bounds.
201 POSIX is true if we want full backtracking (POSIX style) for this pattern.
202 False means backtrack only enough to get a valid match. */
204 struct re_pattern_buffer
*
205 compile_pattern (Lisp_Object pattern
, struct re_registers
*regp
,
206 Lisp_Object translate
, bool posix
, bool multibyte
)
208 struct regexp_cache
*cp
, **cpp
;
210 for (cpp
= &searchbuf_head
; ; cpp
= &cp
->next
)
213 /* Entries are initialized to nil, and may be set to nil by
214 compile_pattern_1 if the pattern isn't valid. Don't apply
215 string accessors in those cases. However, compile_pattern_1
216 is only applied to the cache entry we pick here to reuse. So
217 nil should never appear before a non-nil entry. */
218 if (NILP (cp
->regexp
))
220 if (SCHARS (cp
->regexp
) == SCHARS (pattern
)
221 && STRING_MULTIBYTE (cp
->regexp
) == STRING_MULTIBYTE (pattern
)
222 && !NILP (Fstring_equal (cp
->regexp
, pattern
))
223 && EQ (cp
->buf
.translate
, (! NILP (translate
) ? translate
: make_number (0)))
224 && cp
->posix
== posix
225 && (EQ (cp
->syntax_table
, Qt
)
226 || EQ (cp
->syntax_table
, BVAR (current_buffer
, syntax_table
)))
227 && !NILP (Fequal (cp
->whitespace_regexp
, Vsearch_spaces_regexp
))
228 && cp
->buf
.charset_unibyte
== charset_unibyte
)
231 /* If we're at the end of the cache, compile into the nil cell
232 we found, or the last (least recently used) cell with a
237 compile_pattern_1 (cp
, pattern
, translate
, posix
);
242 /* When we get here, cp (aka *cpp) contains the compiled pattern,
243 either because we found it in the cache or because we just compiled it.
244 Move it to the front of the queue to mark it as most recently used. */
246 cp
->next
= searchbuf_head
;
249 /* Advise the searching functions about the space we have allocated
250 for register data. */
252 re_set_registers (&cp
->buf
, regp
, regp
->num_regs
, regp
->start
, regp
->end
);
254 /* The compiled pattern can be used both for multibyte and unibyte
255 target. But, we have to tell which the pattern is used for. */
256 cp
->buf
.target_multibyte
= multibyte
;
263 looking_at_1 (Lisp_Object string
, bool posix
)
266 unsigned char *p1
, *p2
;
268 register ptrdiff_t i
;
269 struct re_pattern_buffer
*bufp
;
271 if (running_asynch_code
)
274 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
275 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
276 BVAR (current_buffer
, case_eqv_table
));
278 CHECK_STRING (string
);
279 bufp
= compile_pattern (string
,
280 (NILP (Vinhibit_changing_match_data
)
281 ? &search_regs
: NULL
),
282 (!NILP (BVAR (current_buffer
, case_fold_search
))
283 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
285 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
288 QUIT
; /* Do a pending quit right away, to avoid paradoxical behavior */
290 /* Get pointers and sizes of the two strings that make up the
291 visible portion of the buffer. Note that we can use pointers
292 here, unlike in search_buffer, because we only call re_match_2
293 once, after which we never use the pointers again. */
296 s1
= GPT_BYTE
- BEGV_BYTE
;
298 s2
= ZV_BYTE
- GPT_BYTE
;
302 s2
= ZV_BYTE
- BEGV_BYTE
;
307 s1
= ZV_BYTE
- BEGV_BYTE
;
311 re_match_object
= Qnil
;
313 i
= re_match_2 (bufp
, (char *) p1
, s1
, (char *) p2
, s2
,
315 (NILP (Vinhibit_changing_match_data
)
316 ? &search_regs
: NULL
),
317 ZV_BYTE
- BEGV_BYTE
);
323 val
= (i
>= 0 ? Qt
: Qnil
);
324 if (NILP (Vinhibit_changing_match_data
) && i
>= 0)
326 for (i
= 0; i
< search_regs
.num_regs
; i
++)
327 if (search_regs
.start
[i
] >= 0)
330 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
332 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
334 /* Set last_thing_searched only when match data is changed. */
335 XSETBUFFER (last_thing_searched
, current_buffer
);
341 DEFUN ("looking-at", Flooking_at
, Slooking_at
, 1, 1, 0,
342 doc
: /* Return t if text after point matches regular expression REGEXP.
343 This function modifies the match data that `match-beginning',
344 `match-end' and `match-data' access; save and restore the match
345 data if you want to preserve them. */)
348 return looking_at_1 (regexp
, 0);
351 DEFUN ("posix-looking-at", Fposix_looking_at
, Sposix_looking_at
, 1, 1, 0,
352 doc
: /* Return t if text after point matches regular expression REGEXP.
353 Find the longest match, in accord with Posix regular expression rules.
354 This function modifies the match data that `match-beginning',
355 `match-end' and `match-data' access; save and restore the match
356 data if you want to preserve them. */)
359 return looking_at_1 (regexp
, 1);
363 string_match_1 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
,
367 struct re_pattern_buffer
*bufp
;
369 ptrdiff_t pos_byte
, i
;
371 if (running_asynch_code
)
374 CHECK_STRING (regexp
);
375 CHECK_STRING (string
);
378 pos
= 0, pos_byte
= 0;
381 ptrdiff_t len
= SCHARS (string
);
383 CHECK_NUMBER (start
);
385 if (pos
< 0 && -pos
<= len
)
387 else if (0 > pos
|| pos
> len
)
388 args_out_of_range (string
, start
);
389 pos_byte
= string_char_to_byte (string
, pos
);
392 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
393 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
394 BVAR (current_buffer
, case_eqv_table
));
396 bufp
= compile_pattern (regexp
,
397 (NILP (Vinhibit_changing_match_data
)
398 ? &search_regs
: NULL
),
399 (!NILP (BVAR (current_buffer
, case_fold_search
))
400 ? BVAR (current_buffer
, case_canon_table
) : Qnil
),
402 STRING_MULTIBYTE (string
));
404 re_match_object
= string
;
406 val
= re_search (bufp
, SSDATA (string
),
407 SBYTES (string
), pos_byte
,
408 SBYTES (string
) - pos_byte
,
409 (NILP (Vinhibit_changing_match_data
)
410 ? &search_regs
: NULL
));
412 re_match_object
= Qnil
; /* Stop protecting string from GC. */
414 /* Set last_thing_searched only when match data is changed. */
415 if (NILP (Vinhibit_changing_match_data
))
416 last_thing_searched
= Qt
;
420 if (val
< 0) return Qnil
;
422 if (NILP (Vinhibit_changing_match_data
))
423 for (i
= 0; i
< search_regs
.num_regs
; i
++)
424 if (search_regs
.start
[i
] >= 0)
427 = string_byte_to_char (string
, search_regs
.start
[i
]);
429 = string_byte_to_char (string
, search_regs
.end
[i
]);
432 return make_number (string_byte_to_char (string
, val
));
435 DEFUN ("string-match", Fstring_match
, Sstring_match
, 2, 3, 0,
436 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
437 Matching ignores case if `case-fold-search' is non-nil.
438 If third arg START is non-nil, start search at that index in STRING.
439 For index of first char beyond the match, do (match-end 0).
440 `match-end' and `match-beginning' also give indices of substrings
441 matched by parenthesis constructs in the pattern.
443 You can use the function `match-string' to extract the substrings
444 matched by the parenthesis constructions in REGEXP. */)
445 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
447 return string_match_1 (regexp
, string
, start
, 0);
450 DEFUN ("posix-string-match", Fposix_string_match
, Sposix_string_match
, 2, 3, 0,
451 doc
: /* Return index of start of first match for REGEXP in STRING, or nil.
452 Find the longest match, in accord with Posix regular expression rules.
453 Case is ignored if `case-fold-search' is non-nil in the current buffer.
454 If third arg START is non-nil, start search at that index in STRING.
455 For index of first char beyond the match, do (match-end 0).
456 `match-end' and `match-beginning' also give indices of substrings
457 matched by parenthesis constructs in the pattern. */)
458 (Lisp_Object regexp
, Lisp_Object string
, Lisp_Object start
)
460 return string_match_1 (regexp
, string
, start
, 1);
463 /* Match REGEXP against STRING using translation table TABLE,
464 searching all of STRING, and return the index of the match,
465 or negative on failure. This does not clobber the match data. */
468 fast_string_match_internal (Lisp_Object regexp
, Lisp_Object string
,
472 struct re_pattern_buffer
*bufp
;
474 bufp
= compile_pattern (regexp
, 0, table
,
475 0, STRING_MULTIBYTE (string
));
477 re_match_object
= string
;
479 val
= re_search (bufp
, SSDATA (string
),
483 re_match_object
= Qnil
; /* Stop protecting string from GC. */
487 /* Match REGEXP against STRING, searching all of STRING ignoring case,
488 and return the index of the match, or negative on failure.
489 This does not clobber the match data.
490 We assume that STRING contains single-byte characters. */
493 fast_c_string_match_ignore_case (Lisp_Object regexp
,
494 const char *string
, ptrdiff_t len
)
497 struct re_pattern_buffer
*bufp
;
499 regexp
= string_make_unibyte (regexp
);
500 re_match_object
= Qt
;
501 bufp
= compile_pattern (regexp
, 0,
502 Vascii_canon_table
, 0,
505 val
= re_search (bufp
, string
, len
, 0, len
, 0);
510 /* Match REGEXP against the characters after POS to LIMIT, and return
511 the number of matched characters. If STRING is non-nil, match
512 against the characters in it. In that case, POS and LIMIT are
513 indices into the string. This function doesn't modify the match
517 fast_looking_at (Lisp_Object regexp
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
518 ptrdiff_t limit
, ptrdiff_t limit_byte
, Lisp_Object string
)
521 struct re_pattern_buffer
*buf
;
522 unsigned char *p1
, *p2
;
526 if (STRINGP (string
))
529 pos_byte
= string_char_to_byte (string
, pos
);
531 limit_byte
= string_char_to_byte (string
, limit
);
535 s2
= SBYTES (string
);
536 re_match_object
= string
;
537 multibyte
= STRING_MULTIBYTE (string
);
542 pos_byte
= CHAR_TO_BYTE (pos
);
544 limit_byte
= CHAR_TO_BYTE (limit
);
545 pos_byte
-= BEGV_BYTE
;
546 limit_byte
-= BEGV_BYTE
;
548 s1
= GPT_BYTE
- BEGV_BYTE
;
550 s2
= ZV_BYTE
- GPT_BYTE
;
554 s2
= ZV_BYTE
- BEGV_BYTE
;
559 s1
= ZV_BYTE
- BEGV_BYTE
;
562 re_match_object
= Qnil
;
563 multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
566 buf
= compile_pattern (regexp
, 0, Qnil
, 0, multibyte
);
568 len
= re_match_2 (buf
, (char *) p1
, s1
, (char *) p2
, s2
,
569 pos_byte
, NULL
, limit_byte
);
571 re_match_object
= Qnil
; /* Stop protecting string from GC. */
577 /* The newline cache: remembering which sections of text have no newlines. */
579 /* If the user has requested the long scans caching, make sure it's on.
580 Otherwise, make sure it's off.
581 This is our cheezy way of associating an action with the change of
582 state of a buffer-local variable. */
583 static struct region_cache
*
584 newline_cache_on_off (struct buffer
*buf
)
586 struct buffer
*base_buf
= buf
;
587 bool indirect_p
= false;
589 if (buf
->base_buffer
)
591 base_buf
= buf
->base_buffer
;
595 /* Don't turn on or off the cache in the base buffer, if the value
596 of cache-long-scans of the base buffer is inconsistent with that.
597 This is because doing so will just make the cache pure overhead,
598 since if we turn it on via indirect buffer, it will be
599 immediately turned off by its base buffer. */
600 if (NILP (BVAR (buf
, cache_long_scans
)))
603 || NILP (BVAR (base_buf
, cache_long_scans
)))
605 /* It should be off. */
606 if (base_buf
->newline_cache
)
608 free_region_cache (base_buf
->newline_cache
);
609 base_buf
->newline_cache
= 0;
617 || !NILP (BVAR (base_buf
, cache_long_scans
)))
619 /* It should be on. */
620 if (base_buf
->newline_cache
== 0)
621 base_buf
->newline_cache
= new_region_cache ();
623 return base_buf
->newline_cache
;
628 /* Search for COUNT newlines between START/START_BYTE and END/END_BYTE.
630 If COUNT is positive, search forwards; END must be >= START.
631 If COUNT is negative, search backwards for the -COUNTth instance;
632 END must be <= START.
633 If COUNT is zero, do anything you please; run rogue, for all I care.
635 If END is zero, use BEGV or ZV instead, as appropriate for the
636 direction indicated by COUNT.
638 If we find COUNT instances, set *SHORTAGE to zero, and return the
639 position past the COUNTth match. Note that for reverse motion
640 this is not the same as the usual convention for Emacs motion commands.
642 If we don't find COUNT instances before reaching END, set *SHORTAGE
643 to the number of newlines left unfound, and return END.
645 If BYTEPOS is not NULL, set *BYTEPOS to the byte position corresponding
646 to the returned character position.
648 If ALLOW_QUIT, set immediate_quit. That's good to do
649 except when inside redisplay. */
652 find_newline (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
653 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
654 ptrdiff_t *bytepos
, bool allow_quit
)
656 struct region_cache
*newline_cache
;
658 struct buffer
*cache_buffer
;
664 end
= ZV
, end_byte
= ZV_BYTE
;
670 end
= BEGV
, end_byte
= BEGV_BYTE
;
673 end_byte
= CHAR_TO_BYTE (end
);
675 newline_cache
= newline_cache_on_off (current_buffer
);
676 if (current_buffer
->base_buffer
)
677 cache_buffer
= current_buffer
->base_buffer
;
679 cache_buffer
= current_buffer
;
684 immediate_quit
= allow_quit
;
689 /* Our innermost scanning loop is very simple; it doesn't know
690 about gaps, buffer ends, or the newline cache. ceiling is
691 the position of the last character before the next such
692 obstacle --- the last character the dumb search loop should
694 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
696 /* If we're using the newline cache, consult it to see whether
697 we can avoid some scanning. */
700 ptrdiff_t next_change
;
704 while (start
< end
&& result
)
708 result
= region_cache_forward (cache_buffer
, newline_cache
,
709 start
, &next_change
);
712 /* When the cache revalidation is deferred,
713 next-change might point beyond ZV, which will
714 cause assertion violation in CHAR_TO_BYTE below.
715 Limit next_change to ZV to avoid that. */
716 if (next_change
> ZV
)
719 lim1
= next_change
= end
;
722 lim1
= min (next_change
, end
);
724 /* The cache returned zero for this region; see if
725 this is because the region is known and includes
726 only newlines. While at that, count any newlines
727 we bump into, and exit if we found enough off them. */
728 start_byte
= CHAR_TO_BYTE (start
);
730 && FETCH_BYTE (start_byte
) == '\n')
737 *bytepos
= start_byte
;
741 /* If we found a non-newline character before hitting
742 position where the cache will again return non-zero
743 (i.e. no newlines beyond that position), it means
744 this region is not yet known to the cache, and we
745 must resort to the "dumb loop" method. */
746 if (start
< next_change
&& !result
)
753 start_byte
= end_byte
;
756 immediate_quit
= allow_quit
;
758 /* START should never be after END. */
759 if (start_byte
> ceiling_byte
)
760 start_byte
= ceiling_byte
;
762 /* Now the text after start is an unknown region, and
763 next_change is the position of the next known region. */
764 ceiling_byte
= min (CHAR_TO_BYTE (next_change
) - 1, ceiling_byte
);
766 else if (start_byte
== -1)
767 start_byte
= CHAR_TO_BYTE (start
);
769 /* The dumb loop can only scan text stored in contiguous
770 bytes. BUFFER_CEILING_OF returns the last character
771 position that is contiguous, so the ceiling is the
772 position after that. */
773 tem
= BUFFER_CEILING_OF (start_byte
);
774 ceiling_byte
= min (tem
, ceiling_byte
);
777 /* The termination address of the dumb loop. */
778 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
779 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
781 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
782 of the base, the cursor, and the next line. */
783 ptrdiff_t base
= start_byte
- lim_byte
;
784 ptrdiff_t cursor
, next
;
786 for (cursor
= base
; cursor
< 0; cursor
= next
)
789 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
790 next
= nl
? nl
- lim_addr
: 0;
792 /* If we're using the newline cache, cache the fact that
793 the region we just traversed is free of newlines. */
794 if (newline_cache
&& cursor
!= next
)
796 know_region_cache (cache_buffer
, newline_cache
,
797 BYTE_TO_CHAR (lim_byte
+ cursor
),
798 BYTE_TO_CHAR (lim_byte
+ next
));
799 /* know_region_cache can relocate buffer text. */
800 lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
811 *bytepos
= lim_byte
+ next
;
812 return BYTE_TO_CHAR (lim_byte
+ next
);
816 start_byte
= lim_byte
;
817 start
= BYTE_TO_CHAR (start_byte
);
823 /* The last character to check before the next obstacle. */
824 ptrdiff_t tem
, ceiling_byte
= end_byte
;
826 /* Consult the newline cache, if appropriate. */
829 ptrdiff_t next_change
;
833 while (start
> end
&& result
)
837 result
= region_cache_backward (cache_buffer
, newline_cache
,
838 start
, &next_change
);
842 lim1
= next_change
= end
;
845 lim1
= max (next_change
, end
);
846 start_byte
= CHAR_TO_BYTE (start
);
848 && FETCH_BYTE (start_byte
- 1) == '\n')
853 *bytepos
= start_byte
;
859 if (start
> next_change
&& !result
)
866 start_byte
= end_byte
;
869 immediate_quit
= allow_quit
;
871 /* Start should never be at or before end. */
872 if (start_byte
<= ceiling_byte
)
873 start_byte
= ceiling_byte
+ 1;
875 /* Now the text before start is an unknown region, and
876 next_change is the position of the next known region. */
877 ceiling_byte
= max (CHAR_TO_BYTE (next_change
), ceiling_byte
);
879 else if (start_byte
== -1)
880 start_byte
= CHAR_TO_BYTE (start
);
882 /* Stop scanning before the gap. */
883 tem
= BUFFER_FLOOR_OF (start_byte
- 1);
884 ceiling_byte
= max (tem
, ceiling_byte
);
887 /* The termination address of the dumb loop. */
888 unsigned char *ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
890 /* Offsets (relative to CEILING_ADDR and CEILING_BYTE) of
891 the base, the cursor, and the previous line. These
892 offsets are at least -1. */
893 ptrdiff_t base
= start_byte
- ceiling_byte
;
894 ptrdiff_t cursor
, prev
;
896 for (cursor
= base
; 0 < cursor
; cursor
= prev
)
898 unsigned char *nl
= memrchr (ceiling_addr
, '\n', cursor
);
899 prev
= nl
? nl
- ceiling_addr
: -1;
901 /* If we're looking for newlines, cache the fact that
902 this line's region is free of them. */
903 if (newline_cache
&& cursor
!= prev
+ 1)
905 know_region_cache (cache_buffer
, newline_cache
,
906 BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1),
907 BYTE_TO_CHAR (ceiling_byte
+ cursor
));
908 /* know_region_cache can relocate buffer text. */
909 ceiling_addr
= BYTE_POS_ADDR (ceiling_byte
);
919 *bytepos
= ceiling_byte
+ prev
+ 1;
920 return BYTE_TO_CHAR (ceiling_byte
+ prev
+ 1);
924 start_byte
= ceiling_byte
;
925 start
= BYTE_TO_CHAR (start_byte
);
931 *shortage
= count
* direction
;
934 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
935 eassert (*bytepos
== CHAR_TO_BYTE (start
));
940 /* Search for COUNT instances of a line boundary.
941 Start at START. If COUNT is negative, search backwards.
943 We report the resulting position by calling TEMP_SET_PT_BOTH.
945 If we find COUNT instances. we position after (always after,
946 even if scanning backwards) the COUNTth match, and return 0.
948 If we don't find COUNT instances before reaching the end of the
949 buffer (or the beginning, if scanning backwards), we return
950 the number of line boundaries left unfound, and position at
951 the limit we bumped up against.
953 If ALLOW_QUIT, set immediate_quit. That's good to do
954 except in special cases. */
957 scan_newline (ptrdiff_t start
, ptrdiff_t start_byte
,
958 ptrdiff_t limit
, ptrdiff_t limit_byte
,
959 ptrdiff_t count
, bool allow_quit
)
961 ptrdiff_t charpos
, bytepos
, shortage
;
963 charpos
= find_newline (start
, start_byte
, limit
, limit_byte
,
964 count
, &shortage
, &bytepos
, allow_quit
);
966 TEMP_SET_PT_BOTH (limit
, limit_byte
);
968 TEMP_SET_PT_BOTH (charpos
, bytepos
);
972 /* Like above, but always scan from point and report the
973 resulting position in *CHARPOS and *BYTEPOS. */
976 scan_newline_from_point (ptrdiff_t count
, ptrdiff_t *charpos
,
982 *charpos
= find_newline (PT
, PT_BYTE
, BEGV
, BEGV_BYTE
, count
- 1,
983 &shortage
, bytepos
, 1);
985 *charpos
= find_newline (PT
, PT_BYTE
, ZV
, ZV_BYTE
, count
,
986 &shortage
, bytepos
, 1);
990 /* Like find_newline, but doesn't allow QUITting and doesn't return
993 find_newline_no_quit (ptrdiff_t from
, ptrdiff_t frombyte
,
994 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
996 return find_newline (from
, frombyte
, 0, -1, cnt
, NULL
, bytepos
, 0);
999 /* Like find_newline, but returns position before the newline, not
1000 after, and only search up to TO.
1001 This isn't just find_newline_no_quit (...)-1, because you might hit TO. */
1004 find_before_next_newline (ptrdiff_t from
, ptrdiff_t to
,
1005 ptrdiff_t cnt
, ptrdiff_t *bytepos
)
1008 ptrdiff_t pos
= find_newline (from
, -1, to
, -1, cnt
, &shortage
, bytepos
, 1);
1013 DEC_BOTH (pos
, *bytepos
);
1020 /* Subroutines of Lisp buffer search functions. */
1023 search_command (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
,
1024 Lisp_Object count
, int direction
, int RE
, bool posix
)
1029 EMACS_INT n
= direction
;
1033 CHECK_NUMBER (count
);
1037 CHECK_STRING (string
);
1041 lim
= ZV
, lim_byte
= ZV_BYTE
;
1043 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1047 CHECK_NUMBER_COERCE_MARKER (bound
);
1049 if (n
> 0 ? lim
< PT
: lim
> PT
)
1050 error ("Invalid search bound (wrong side of point)");
1052 lim
= ZV
, lim_byte
= ZV_BYTE
;
1053 else if (lim
< BEGV
)
1054 lim
= BEGV
, lim_byte
= BEGV_BYTE
;
1056 lim_byte
= CHAR_TO_BYTE (lim
);
1059 /* This is so set_image_of_range_1 in regex.c can find the EQV table. */
1060 set_char_table_extras (BVAR (current_buffer
, case_canon_table
), 2,
1061 BVAR (current_buffer
, case_eqv_table
));
1063 np
= search_buffer (string
, PT
, PT_BYTE
, lim
, lim_byte
, n
, RE
,
1064 (!NILP (BVAR (current_buffer
, case_fold_search
))
1065 ? BVAR (current_buffer
, case_canon_table
)
1067 (!NILP (BVAR (current_buffer
, case_fold_search
))
1068 ? BVAR (current_buffer
, case_eqv_table
)
1074 xsignal1 (Qsearch_failed
, string
);
1076 if (!EQ (noerror
, Qt
))
1078 eassert (BEGV
<= lim
&& lim
<= ZV
);
1079 SET_PT_BOTH (lim
, lim_byte
);
1081 #if 0 /* This would be clean, but maybe programs depend on
1082 a value of nil here. */
1090 eassert (BEGV
<= np
&& np
<= ZV
);
1093 return make_number (np
);
1096 /* Return true if REGEXP it matches just one constant string. */
1099 trivial_regexp_p (Lisp_Object regexp
)
1101 ptrdiff_t len
= SBYTES (regexp
);
1102 unsigned char *s
= SDATA (regexp
);
1107 case '.': case '*': case '+': case '?': case '[': case '^': case '$':
1114 case '|': case '(': case ')': case '`': case '\'': case 'b':
1115 case 'B': case '<': case '>': case 'w': case 'W': case 's':
1116 case 'S': case '=': case '{': case '}': case '_':
1117 case 'c': case 'C': /* for categoryspec and notcategoryspec */
1118 case '1': case '2': case '3': case '4': case '5':
1119 case '6': case '7': case '8': case '9':
1127 /* Search for the n'th occurrence of STRING in the current buffer,
1128 starting at position POS and stopping at position LIM,
1129 treating STRING as a literal string if RE is false or as
1130 a regular expression if RE is true.
1132 If N is positive, searching is forward and LIM must be greater than POS.
1133 If N is negative, searching is backward and LIM must be less than POS.
1135 Returns -x if x occurrences remain to be found (x > 0),
1136 or else the position at the beginning of the Nth occurrence
1137 (if searching backward) or the end (if searching forward).
1139 POSIX is nonzero if we want full backtracking (POSIX style)
1140 for this pattern. 0 means backtrack only enough to get a valid match. */
1142 #define TRANSLATE(out, trt, d) \
1148 temp = Faref (trt, make_number (d)); \
1149 if (INTEGERP (temp)) \
1150 out = XINT (temp); \
1159 /* Only used in search_buffer, to record the end position of the match
1160 when searching regexps and SEARCH_REGS should not be changed
1161 (i.e. Vinhibit_changing_match_data is non-nil). */
1162 static struct re_registers search_regs_1
;
1165 search_buffer (Lisp_Object string
, ptrdiff_t pos
, ptrdiff_t pos_byte
,
1166 ptrdiff_t lim
, ptrdiff_t lim_byte
, EMACS_INT n
,
1167 int RE
, Lisp_Object trt
, Lisp_Object inverse_trt
, bool posix
)
1169 ptrdiff_t len
= SCHARS (string
);
1170 ptrdiff_t len_byte
= SBYTES (string
);
1171 register ptrdiff_t i
;
1173 if (running_asynch_code
)
1174 save_search_regs ();
1176 /* Searching 0 times means don't move. */
1177 /* Null string is found at starting position. */
1178 if (len
== 0 || n
== 0)
1180 set_search_regs (pos_byte
, 0);
1184 if (RE
&& !(trivial_regexp_p (string
) && NILP (Vsearch_spaces_regexp
)))
1186 unsigned char *base
;
1187 ptrdiff_t off1
, off2
, s1
, s2
;
1188 struct re_pattern_buffer
*bufp
;
1190 bufp
= compile_pattern (string
,
1191 (NILP (Vinhibit_changing_match_data
)
1192 ? &search_regs
: &search_regs_1
),
1194 !NILP (BVAR (current_buffer
, enable_multibyte_characters
)));
1196 immediate_quit
= 1; /* Quit immediately if user types ^G,
1197 because letting this function finish
1198 can take too long. */
1199 QUIT
; /* Do a pending quit right away,
1200 to avoid paradoxical behavior */
1201 /* Get offsets and sizes of the two strings that make up the
1202 visible portion of the buffer. We compute offsets instead of
1203 pointers because re_search_2 may call malloc and therefore
1204 change the buffer text address. */
1206 base
= current_buffer
->text
->beg
;
1207 off1
= BEGV_ADDR
- base
;
1208 s1
= GPT_BYTE
- BEGV_BYTE
;
1209 off2
= GAP_END_ADDR
- base
;
1210 s2
= ZV_BYTE
- GPT_BYTE
;
1214 s2
= ZV_BYTE
- BEGV_BYTE
;
1219 s1
= ZV_BYTE
- BEGV_BYTE
;
1222 re_match_object
= Qnil
;
1228 val
= re_search_2 (bufp
,
1229 (char*) (base
+ off1
), s1
,
1230 (char*) (base
+ off2
), s2
,
1231 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1232 (NILP (Vinhibit_changing_match_data
)
1233 ? &search_regs
: &search_regs_1
),
1234 /* Don't allow match past current point */
1235 pos_byte
- BEGV_BYTE
);
1236 /* Update 'base' due to possible relocation inside re_search_2. */
1237 base
= current_buffer
->text
->beg
;
1240 matcher_overflow ();
1244 if (NILP (Vinhibit_changing_match_data
))
1246 pos_byte
= search_regs
.start
[0] + BEGV_BYTE
;
1247 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1248 if (search_regs
.start
[i
] >= 0)
1250 search_regs
.start
[i
]
1251 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1253 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1255 XSETBUFFER (last_thing_searched
, current_buffer
);
1256 /* Set pos to the new position. */
1257 pos
= search_regs
.start
[0];
1261 pos_byte
= search_regs_1
.start
[0] + BEGV_BYTE
;
1262 /* Set pos to the new position. */
1263 pos
= BYTE_TO_CHAR (search_regs_1
.start
[0] + BEGV_BYTE
);
1277 val
= re_search_2 (bufp
,
1278 (char*) (base
+ off1
), s1
,
1279 (char*) (base
+ off2
), s2
,
1280 pos_byte
- BEGV_BYTE
, lim_byte
- pos_byte
,
1281 (NILP (Vinhibit_changing_match_data
)
1282 ? &search_regs
: &search_regs_1
),
1283 lim_byte
- BEGV_BYTE
);
1284 /* Update 'base' due to possible relocation inside re_search_2. */
1285 base
= current_buffer
->text
->beg
;
1288 matcher_overflow ();
1292 if (NILP (Vinhibit_changing_match_data
))
1294 pos_byte
= search_regs
.end
[0] + BEGV_BYTE
;
1295 for (i
= 0; i
< search_regs
.num_regs
; i
++)
1296 if (search_regs
.start
[i
] >= 0)
1298 search_regs
.start
[i
]
1299 = BYTE_TO_CHAR (search_regs
.start
[i
] + BEGV_BYTE
);
1301 = BYTE_TO_CHAR (search_regs
.end
[i
] + BEGV_BYTE
);
1303 XSETBUFFER (last_thing_searched
, current_buffer
);
1304 pos
= search_regs
.end
[0];
1308 pos_byte
= search_regs_1
.end
[0] + BEGV_BYTE
;
1309 pos
= BYTE_TO_CHAR (search_regs_1
.end
[0] + BEGV_BYTE
);
1322 else /* non-RE case */
1324 unsigned char *raw_pattern
, *pat
;
1325 ptrdiff_t raw_pattern_size
;
1326 ptrdiff_t raw_pattern_size_byte
;
1327 unsigned char *patbuf
;
1328 bool multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1329 unsigned char *base_pat
;
1330 /* Set to positive if we find a non-ASCII char that need
1331 translation. Otherwise set to zero later. */
1333 bool boyer_moore_ok
= 1;
1336 /* MULTIBYTE says whether the text to be searched is multibyte.
1337 We must convert PATTERN to match that, or we will not really
1338 find things right. */
1340 if (multibyte
== STRING_MULTIBYTE (string
))
1342 raw_pattern
= SDATA (string
);
1343 raw_pattern_size
= SCHARS (string
);
1344 raw_pattern_size_byte
= SBYTES (string
);
1348 raw_pattern_size
= SCHARS (string
);
1349 raw_pattern_size_byte
1350 = count_size_as_multibyte (SDATA (string
),
1352 raw_pattern
= SAFE_ALLOCA (raw_pattern_size_byte
+ 1);
1353 copy_text (SDATA (string
), raw_pattern
,
1354 SCHARS (string
), 0, 1);
1358 /* Converting multibyte to single-byte.
1360 ??? Perhaps this conversion should be done in a special way
1361 by subtracting nonascii-insert-offset from each non-ASCII char,
1362 so that only the multibyte chars which really correspond to
1363 the chosen single-byte character set can possibly match. */
1364 raw_pattern_size
= SCHARS (string
);
1365 raw_pattern_size_byte
= SCHARS (string
);
1366 raw_pattern
= SAFE_ALLOCA (raw_pattern_size
+ 1);
1367 copy_text (SDATA (string
), raw_pattern
,
1368 SBYTES (string
), 1, 0);
1371 /* Copy and optionally translate the pattern. */
1372 len
= raw_pattern_size
;
1373 len_byte
= raw_pattern_size_byte
;
1374 SAFE_NALLOCA (patbuf
, MAX_MULTIBYTE_LENGTH
, len
);
1376 base_pat
= raw_pattern
;
1379 /* Fill patbuf by translated characters in STRING while
1380 checking if we can use boyer-moore search. If TRT is
1381 non-nil, we can use boyer-moore search only if TRT can be
1382 represented by the byte array of 256 elements. For that,
1383 all non-ASCII case-equivalents of all case-sensitive
1384 characters in STRING must belong to the same character
1385 group (two characters belong to the same group iff their
1386 multibyte forms are the same except for the last byte;
1387 i.e. every 64 characters form a group; U+0000..U+003F,
1388 U+0040..U+007F, U+0080..U+00BF, ...). */
1392 unsigned char str_base
[MAX_MULTIBYTE_LENGTH
], *str
;
1393 int c
, translated
, inverse
;
1394 int in_charlen
, charlen
;
1396 /* If we got here and the RE flag is set, it's because we're
1397 dealing with a regexp known to be trivial, so the backslash
1398 just quotes the next character. */
1399 if (RE
&& *base_pat
== '\\')
1407 c
= STRING_CHAR_AND_LENGTH (base_pat
, in_charlen
);
1412 charlen
= in_charlen
;
1416 /* Translate the character. */
1417 TRANSLATE (translated
, trt
, c
);
1418 charlen
= CHAR_STRING (translated
, str_base
);
1421 /* Check if C has any other case-equivalents. */
1422 TRANSLATE (inverse
, inverse_trt
, c
);
1423 /* If so, check if we can use boyer-moore. */
1424 if (c
!= inverse
&& boyer_moore_ok
)
1426 /* Check if all equivalents belong to the same
1427 group of characters. Note that the check of C
1428 itself is done by the last iteration. */
1429 int this_char_base
= -1;
1431 while (boyer_moore_ok
)
1433 if (ASCII_CHAR_P (inverse
))
1435 if (this_char_base
> 0)
1440 else if (CHAR_BYTE8_P (inverse
))
1441 /* Boyer-moore search can't handle a
1442 translation of an eight-bit
1445 else if (this_char_base
< 0)
1447 this_char_base
= inverse
& ~0x3F;
1449 char_base
= this_char_base
;
1450 else if (this_char_base
!= char_base
)
1453 else if ((inverse
& ~0x3F) != this_char_base
)
1457 TRANSLATE (inverse
, inverse_trt
, inverse
);
1462 /* Store this character into the translated pattern. */
1463 memcpy (pat
, str
, charlen
);
1465 base_pat
+= in_charlen
;
1466 len_byte
-= in_charlen
;
1469 /* If char_base is still negative we didn't find any translated
1470 non-ASCII characters. */
1476 /* Unibyte buffer. */
1480 int c
, translated
, inverse
;
1482 /* If we got here and the RE flag is set, it's because we're
1483 dealing with a regexp known to be trivial, so the backslash
1484 just quotes the next character. */
1485 if (RE
&& *base_pat
== '\\')
1492 TRANSLATE (translated
, trt
, c
);
1493 *pat
++ = translated
;
1494 /* Check that none of C's equivalents violates the
1495 assumptions of boyer_moore. */
1496 TRANSLATE (inverse
, inverse_trt
, c
);
1499 if (inverse
>= 0200)
1506 TRANSLATE (inverse
, inverse_trt
, inverse
);
1511 len_byte
= pat
- patbuf
;
1512 pat
= base_pat
= patbuf
;
1516 ? boyer_moore (n
, pat
, len_byte
, trt
, inverse_trt
,
1519 : simple_search (n
, pat
, raw_pattern_size
, len_byte
, trt
,
1520 pos
, pos_byte
, lim
, lim_byte
));
1526 /* Do a simple string search N times for the string PAT,
1527 whose length is LEN/LEN_BYTE,
1528 from buffer position POS/POS_BYTE until LIM/LIM_BYTE.
1529 TRT is the translation table.
1531 Return the character position where the match is found.
1532 Otherwise, if M matches remained to be found, return -M.
1534 This kind of search works regardless of what is in PAT and
1535 regardless of what is in TRT. It is used in cases where
1536 boyer_moore cannot work. */
1539 simple_search (EMACS_INT n
, unsigned char *pat
,
1540 ptrdiff_t len
, ptrdiff_t len_byte
, Lisp_Object trt
,
1541 ptrdiff_t pos
, ptrdiff_t pos_byte
,
1542 ptrdiff_t lim
, ptrdiff_t lim_byte
)
1544 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1545 bool forward
= n
> 0;
1546 /* Number of buffer bytes matched. Note that this may be different
1547 from len_byte in a multibyte buffer. */
1548 ptrdiff_t match_byte
= PTRDIFF_MIN
;
1550 if (lim
> pos
&& multibyte
)
1555 /* Try matching at position POS. */
1556 ptrdiff_t this_pos
= pos
;
1557 ptrdiff_t this_pos_byte
= pos_byte
;
1558 ptrdiff_t this_len
= len
;
1559 unsigned char *p
= pat
;
1560 if (pos
+ len
> lim
|| pos_byte
+ len_byte
> lim_byte
)
1563 while (this_len
> 0)
1565 int charlen
, buf_charlen
;
1568 pat_ch
= STRING_CHAR_AND_LENGTH (p
, charlen
);
1569 buf_ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (this_pos_byte
),
1571 TRANSLATE (buf_ch
, trt
, buf_ch
);
1573 if (buf_ch
!= pat_ch
)
1579 this_pos_byte
+= buf_charlen
;
1585 match_byte
= this_pos_byte
- pos_byte
;
1587 pos_byte
+= match_byte
;
1591 INC_BOTH (pos
, pos_byte
);
1601 /* Try matching at position POS. */
1602 ptrdiff_t this_pos
= pos
;
1603 ptrdiff_t this_len
= len
;
1604 unsigned char *p
= pat
;
1606 if (pos
+ len
> lim
)
1609 while (this_len
> 0)
1612 int buf_ch
= FETCH_BYTE (this_pos
);
1613 TRANSLATE (buf_ch
, trt
, buf_ch
);
1615 if (buf_ch
!= pat_ch
)
1634 /* Backwards search. */
1635 else if (lim
< pos
&& multibyte
)
1640 /* Try matching at position POS. */
1641 ptrdiff_t this_pos
= pos
;
1642 ptrdiff_t this_pos_byte
= pos_byte
;
1643 ptrdiff_t this_len
= len
;
1644 const unsigned char *p
= pat
+ len_byte
;
1646 if (this_pos
- len
< lim
|| (pos_byte
- len_byte
) < lim_byte
)
1649 while (this_len
> 0)
1653 DEC_BOTH (this_pos
, this_pos_byte
);
1654 PREV_CHAR_BOUNDARY (p
, pat
);
1655 pat_ch
= STRING_CHAR (p
);
1656 buf_ch
= STRING_CHAR (BYTE_POS_ADDR (this_pos_byte
));
1657 TRANSLATE (buf_ch
, trt
, buf_ch
);
1659 if (buf_ch
!= pat_ch
)
1667 match_byte
= pos_byte
- this_pos_byte
;
1669 pos_byte
= this_pos_byte
;
1673 DEC_BOTH (pos
, pos_byte
);
1683 /* Try matching at position POS. */
1684 ptrdiff_t this_pos
= pos
- len
;
1685 ptrdiff_t this_len
= len
;
1686 unsigned char *p
= pat
;
1691 while (this_len
> 0)
1694 int buf_ch
= FETCH_BYTE (this_pos
);
1695 TRANSLATE (buf_ch
, trt
, buf_ch
);
1697 if (buf_ch
!= pat_ch
)
1719 eassert (match_byte
!= PTRDIFF_MIN
);
1721 set_search_regs ((multibyte
? pos_byte
: pos
) - match_byte
, match_byte
);
1723 set_search_regs (multibyte
? pos_byte
: pos
, match_byte
);
1733 /* Do Boyer-Moore search N times for the string BASE_PAT,
1734 whose length is LEN_BYTE,
1735 from buffer position POS_BYTE until LIM_BYTE.
1736 DIRECTION says which direction we search in.
1737 TRT and INVERSE_TRT are translation tables.
1738 Characters in PAT are already translated by TRT.
1740 This kind of search works if all the characters in BASE_PAT that
1741 have nontrivial translation are the same aside from the last byte.
1742 This makes it possible to translate just the last byte of a
1743 character, and do so after just a simple test of the context.
1744 CHAR_BASE is nonzero if there is such a non-ASCII character.
1746 If that criterion is not satisfied, do not call this function. */
1749 boyer_moore (EMACS_INT n
, unsigned char *base_pat
,
1751 Lisp_Object trt
, Lisp_Object inverse_trt
,
1752 ptrdiff_t pos_byte
, ptrdiff_t lim_byte
,
1755 int direction
= ((n
> 0) ? 1 : -1);
1756 register ptrdiff_t dirlen
;
1758 int stride_for_teases
= 0;
1760 register unsigned char *cursor
, *p_limit
;
1761 register ptrdiff_t i
;
1763 unsigned char *pat
, *pat_end
;
1764 bool multibyte
= ! NILP (BVAR (current_buffer
, enable_multibyte_characters
));
1766 unsigned char simple_translate
[0400];
1767 /* These are set to the preceding bytes of a byte to be translated
1768 if char_base is nonzero. As the maximum byte length of a
1769 multibyte character is 5, we have to check at most four previous
1771 int translate_prev_byte1
= 0;
1772 int translate_prev_byte2
= 0;
1773 int translate_prev_byte3
= 0;
1775 /* The general approach is that we are going to maintain that we know
1776 the first (closest to the present position, in whatever direction
1777 we're searching) character that could possibly be the last
1778 (furthest from present position) character of a valid match. We
1779 advance the state of our knowledge by looking at that character
1780 and seeing whether it indeed matches the last character of the
1781 pattern. If it does, we take a closer look. If it does not, we
1782 move our pointer (to putative last characters) as far as is
1783 logically possible. This amount of movement, which I call a
1784 stride, will be the length of the pattern if the actual character
1785 appears nowhere in the pattern, otherwise it will be the distance
1786 from the last occurrence of that character to the end of the
1787 pattern. If the amount is zero we have a possible match. */
1789 /* Here we make a "mickey mouse" BM table. The stride of the search
1790 is determined only by the last character of the putative match.
1791 If that character does not match, we will stride the proper
1792 distance to propose a match that superimposes it on the last
1793 instance of a character that matches it (per trt), or misses
1794 it entirely if there is none. */
1796 dirlen
= len_byte
* direction
;
1798 /* Record position after the end of the pattern. */
1799 pat_end
= base_pat
+ len_byte
;
1800 /* BASE_PAT points to a character that we start scanning from.
1801 It is the first character in a forward search,
1802 the last character in a backward search. */
1804 base_pat
= pat_end
- 1;
1806 /* A character that does not appear in the pattern induces a
1807 stride equal to the pattern length. */
1808 for (i
= 0; i
< 0400; i
++)
1811 /* We use this for translation, instead of TRT itself.
1812 We fill this in to handle the characters that actually
1813 occur in the pattern. Others don't matter anyway! */
1814 for (i
= 0; i
< 0400; i
++)
1815 simple_translate
[i
] = i
;
1819 /* Setup translate_prev_byte1/2/3/4 from CHAR_BASE. Only a
1820 byte following them are the target of translation. */
1821 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
1822 int cblen
= CHAR_STRING (char_base
, str
);
1824 translate_prev_byte1
= str
[cblen
- 2];
1827 translate_prev_byte2
= str
[cblen
- 3];
1829 translate_prev_byte3
= str
[cblen
- 4];
1836 unsigned char *ptr
= base_pat
+ i
;
1840 /* If the byte currently looking at is the last of a
1841 character to check case-equivalents, set CH to that
1842 character. An ASCII character and a non-ASCII character
1843 matching with CHAR_BASE are to be checked. */
1846 if (ASCII_CHAR_P (*ptr
) || ! multibyte
)
1849 && ((pat_end
- ptr
) == 1 || CHAR_HEAD_P (ptr
[1])))
1851 unsigned char *charstart
= ptr
- 1;
1853 while (! (CHAR_HEAD_P (*charstart
)))
1855 ch
= STRING_CHAR (charstart
);
1856 if (char_base
!= (ch
& ~0x3F))
1860 if (ch
>= 0200 && multibyte
)
1861 j
= (ch
& 0x3F) | 0200;
1866 stride_for_teases
= BM_tab
[j
];
1868 BM_tab
[j
] = dirlen
- i
;
1869 /* A translation table is accompanied by its inverse -- see
1870 comment following downcase_table for details. */
1873 int starting_ch
= ch
;
1878 TRANSLATE (ch
, inverse_trt
, ch
);
1879 if (ch
>= 0200 && multibyte
)
1880 j
= (ch
& 0x3F) | 0200;
1884 /* For all the characters that map into CH,
1885 set up simple_translate to map the last byte
1887 simple_translate
[j
] = starting_j
;
1888 if (ch
== starting_ch
)
1890 BM_tab
[j
] = dirlen
- i
;
1899 stride_for_teases
= BM_tab
[j
];
1900 BM_tab
[j
] = dirlen
- i
;
1902 /* stride_for_teases tells how much to stride if we get a
1903 match on the far character but are subsequently
1904 disappointed, by recording what the stride would have been
1905 for that character if the last character had been
1908 pos_byte
+= dirlen
- ((direction
> 0) ? direction
: 0);
1909 /* loop invariant - POS_BYTE points at where last char (first
1910 char if reverse) of pattern would align in a possible match. */
1914 unsigned char *tail_end_ptr
;
1916 /* It's been reported that some (broken) compiler thinks that
1917 Boolean expressions in an arithmetic context are unsigned.
1918 Using an explicit ?1:0 prevents this. */
1919 if ((lim_byte
- pos_byte
- ((direction
> 0) ? 1 : 0)) * direction
1921 return (n
* (0 - direction
));
1922 /* First we do the part we can by pointers (maybe nothing) */
1925 limit
= pos_byte
- dirlen
+ direction
;
1928 limit
= BUFFER_CEILING_OF (limit
);
1929 /* LIMIT is now the last (not beyond-last!) value POS_BYTE
1930 can take on without hitting edge of buffer or the gap. */
1931 limit
= min (limit
, pos_byte
+ 20000);
1932 limit
= min (limit
, lim_byte
- 1);
1936 limit
= BUFFER_FLOOR_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
= max (limit
, pos_byte
- 20000);
1940 limit
= max (limit
, lim_byte
);
1942 tail_end
= BUFFER_CEILING_OF (pos_byte
) + 1;
1943 tail_end_ptr
= BYTE_POS_ADDR (tail_end
);
1945 if ((limit
- pos_byte
) * direction
> 20)
1949 p_limit
= BYTE_POS_ADDR (limit
);
1950 p2
= (cursor
= BYTE_POS_ADDR (pos_byte
));
1951 /* In this loop, pos + cursor - p2 is the surrogate for pos. */
1952 while (1) /* use one cursor setting as long as i can */
1954 if (direction
> 0) /* worth duplicating */
1956 while (cursor
<= p_limit
)
1958 if (BM_tab
[*cursor
] == 0)
1960 cursor
+= BM_tab
[*cursor
];
1965 while (cursor
>= p_limit
)
1967 if (BM_tab
[*cursor
] == 0)
1969 cursor
+= BM_tab
[*cursor
];
1972 /* If you are here, cursor is beyond the end of the
1973 searched region. You fail to match within the
1974 permitted region and would otherwise try a character
1975 beyond that region. */
1979 i
= dirlen
- direction
;
1982 while ((i
-= direction
) + direction
!= 0)
1985 cursor
-= direction
;
1986 /* Translate only the last byte of a character. */
1988 || ((cursor
== tail_end_ptr
1989 || CHAR_HEAD_P (cursor
[1]))
1990 && (CHAR_HEAD_P (cursor
[0])
1991 /* Check if this is the last byte of
1992 a translatable character. */
1993 || (translate_prev_byte1
== cursor
[-1]
1994 && (CHAR_HEAD_P (translate_prev_byte1
)
1995 || (translate_prev_byte2
== cursor
[-2]
1996 && (CHAR_HEAD_P (translate_prev_byte2
)
1997 || (translate_prev_byte3
== cursor
[-3]))))))))
1998 ch
= simple_translate
[*cursor
];
2007 while ((i
-= direction
) + direction
!= 0)
2009 cursor
-= direction
;
2010 if (pat
[i
] != *cursor
)
2014 cursor
+= dirlen
- i
- direction
; /* fix cursor */
2015 if (i
+ direction
== 0)
2017 ptrdiff_t position
, start
, end
;
2019 cursor
-= direction
;
2021 position
= pos_byte
+ cursor
- p2
+ ((direction
> 0)
2022 ? 1 - len_byte
: 0);
2023 set_search_regs (position
, len_byte
);
2025 if (NILP (Vinhibit_changing_match_data
))
2027 start
= search_regs
.start
[0];
2028 end
= search_regs
.end
[0];
2031 /* If Vinhibit_changing_match_data is non-nil,
2032 search_regs will not be changed. So let's
2033 compute start and end here. */
2035 start
= BYTE_TO_CHAR (position
);
2036 end
= BYTE_TO_CHAR (position
+ len_byte
);
2039 if ((n
-= direction
) != 0)
2040 cursor
+= dirlen
; /* to resume search */
2042 return direction
> 0 ? end
: start
;
2045 cursor
+= stride_for_teases
; /* <sigh> we lose - */
2047 pos_byte
+= cursor
- p2
;
2050 /* Now we'll pick up a clump that has to be done the hard
2051 way because it covers a discontinuity. */
2053 limit
= ((direction
> 0)
2054 ? BUFFER_CEILING_OF (pos_byte
- dirlen
+ 1)
2055 : BUFFER_FLOOR_OF (pos_byte
- dirlen
- 1));
2056 limit
= ((direction
> 0)
2057 ? min (limit
+ len_byte
, lim_byte
- 1)
2058 : max (limit
- len_byte
, lim_byte
));
2059 /* LIMIT is now the last value POS_BYTE can have
2060 and still be valid for a possible match. */
2063 /* This loop can be coded for space rather than
2064 speed because it will usually run only once.
2065 (the reach is at most len + 21, and typically
2066 does not exceed len). */
2067 while ((limit
- pos_byte
) * direction
>= 0)
2069 int ch
= FETCH_BYTE (pos_byte
);
2070 if (BM_tab
[ch
] == 0)
2072 pos_byte
+= BM_tab
[ch
];
2074 break; /* ran off the end */
2077 /* Found what might be a match. */
2078 i
= dirlen
- direction
;
2079 while ((i
-= direction
) + direction
!= 0)
2083 pos_byte
-= direction
;
2084 ptr
= BYTE_POS_ADDR (pos_byte
);
2085 /* Translate only the last byte of a character. */
2087 || ((ptr
== tail_end_ptr
2088 || CHAR_HEAD_P (ptr
[1]))
2089 && (CHAR_HEAD_P (ptr
[0])
2090 /* Check if this is the last byte of a
2091 translatable character. */
2092 || (translate_prev_byte1
== ptr
[-1]
2093 && (CHAR_HEAD_P (translate_prev_byte1
)
2094 || (translate_prev_byte2
== ptr
[-2]
2095 && (CHAR_HEAD_P (translate_prev_byte2
)
2096 || translate_prev_byte3
== ptr
[-3])))))))
2097 ch
= simple_translate
[*ptr
];
2103 /* Above loop has moved POS_BYTE part or all the way
2104 back to the first pos (last pos if reverse).
2105 Set it once again at the last (first if reverse) char. */
2106 pos_byte
+= dirlen
- i
- direction
;
2107 if (i
+ direction
== 0)
2109 ptrdiff_t position
, start
, end
;
2110 pos_byte
-= direction
;
2112 position
= pos_byte
+ ((direction
> 0) ? 1 - len_byte
: 0);
2113 set_search_regs (position
, len_byte
);
2115 if (NILP (Vinhibit_changing_match_data
))
2117 start
= search_regs
.start
[0];
2118 end
= search_regs
.end
[0];
2121 /* If Vinhibit_changing_match_data is non-nil,
2122 search_regs will not be changed. So let's
2123 compute start and end here. */
2125 start
= BYTE_TO_CHAR (position
);
2126 end
= BYTE_TO_CHAR (position
+ len_byte
);
2129 if ((n
-= direction
) != 0)
2130 pos_byte
+= dirlen
; /* to resume search */
2132 return direction
> 0 ? end
: start
;
2135 pos_byte
+= stride_for_teases
;
2138 /* We have done one clump. Can we continue? */
2139 if ((lim_byte
- pos_byte
) * direction
< 0)
2140 return ((0 - n
) * direction
);
2142 return BYTE_TO_CHAR (pos_byte
);
2145 /* Record beginning BEG_BYTE and end BEG_BYTE + NBYTES
2146 for the overall match just found in the current buffer.
2147 Also clear out the match data for registers 1 and up. */
2150 set_search_regs (ptrdiff_t beg_byte
, ptrdiff_t nbytes
)
2154 if (!NILP (Vinhibit_changing_match_data
))
2157 /* Make sure we have registers in which to store
2158 the match position. */
2159 if (search_regs
.num_regs
== 0)
2161 search_regs
.start
= xmalloc (2 * sizeof (regoff_t
));
2162 search_regs
.end
= xmalloc (2 * sizeof (regoff_t
));
2163 search_regs
.num_regs
= 2;
2166 /* Clear out the other registers. */
2167 for (i
= 1; i
< search_regs
.num_regs
; i
++)
2169 search_regs
.start
[i
] = -1;
2170 search_regs
.end
[i
] = -1;
2173 search_regs
.start
[0] = BYTE_TO_CHAR (beg_byte
);
2174 search_regs
.end
[0] = BYTE_TO_CHAR (beg_byte
+ nbytes
);
2175 XSETBUFFER (last_thing_searched
, current_buffer
);
2178 DEFUN ("search-backward", Fsearch_backward
, Ssearch_backward
, 1, 4,
2179 "MSearch backward: ",
2180 doc
: /* Search backward from point for STRING.
2181 Set point to the beginning of the occurrence found, and return point.
2182 An optional second argument bounds the search; it is a buffer position.
2183 The match found must not begin before that position. A value of nil
2184 means search to the beginning of the accessible portion of the buffer.
2185 Optional third argument, if t, means if fail just return nil (no error).
2186 If not nil and not t, position at limit of search and return nil.
2187 Optional fourth argument COUNT, if a positive number, means to search
2188 for COUNT successive occurrences. If COUNT is negative, search
2189 forward, instead of backward, for -COUNT occurrences. A value of
2190 nil means the same as 1.
2191 With COUNT positive, the match found is the COUNTth to last one (or
2192 last, if COUNT is 1 or nil) in the buffer located entirely before
2193 the origin of the search; correspondingly with COUNT negative.
2195 Search case-sensitivity is determined by the value of the variable
2196 `case-fold-search', which see.
2198 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2199 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2201 return search_command (string
, bound
, noerror
, count
, -1, 0, 0);
2204 DEFUN ("search-forward", Fsearch_forward
, Ssearch_forward
, 1, 4, "MSearch: ",
2205 doc
: /* Search forward from point for STRING.
2206 Set point to the end of the occurrence found, and return point.
2207 An optional second argument bounds the search; it is a buffer position.
2208 The match found must not end after that position. A value of nil
2209 means search to the end of the accessible portion of the buffer.
2210 Optional third argument, if t, means if fail just return nil (no error).
2211 If not nil and not t, move to limit of search and return nil.
2212 Optional fourth argument COUNT, if a positive number, means to search
2213 for COUNT successive occurrences. If COUNT is negative, search
2214 backward, instead of forward, for -COUNT occurrences. A value of
2215 nil means the same as 1.
2216 With COUNT positive, the match found is the COUNTth one (or first,
2217 if COUNT is 1 or nil) in the buffer located entirely after the
2218 origin of the search; correspondingly with COUNT negative.
2220 Search case-sensitivity is determined by the value of the variable
2221 `case-fold-search', which see.
2223 See also the functions `match-beginning', `match-end' and `replace-match'. */)
2224 (Lisp_Object string
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2226 return search_command (string
, bound
, noerror
, count
, 1, 0, 0);
2229 DEFUN ("re-search-backward", Fre_search_backward
, Sre_search_backward
, 1, 4,
2230 "sRE search backward: ",
2231 doc
: /* Search backward from point for match for regular expression REGEXP.
2232 Set point to the beginning of the occurrence found, and return point.
2233 An optional second argument bounds the search; it is a buffer position.
2234 The match found must not begin before that position. A value of nil
2235 means search to the beginning of the accessible portion of the buffer.
2236 Optional third argument, if t, means if fail just return nil (no error).
2237 If not nil and not t, position at limit of search and return nil.
2238 Optional fourth argument COUNT, if a positive number, means to search
2239 for COUNT successive occurrences. If COUNT is negative, search
2240 forward, instead of backward, for -COUNT occurrences. A value of
2241 nil means the same as 1.
2242 With COUNT positive, the match found is the COUNTth to last one (or
2243 last, if COUNT is 1 or nil) in the buffer located entirely before
2244 the origin of the search; correspondingly with COUNT negative.
2246 Search case-sensitivity is determined by the value of the variable
2247 `case-fold-search', which see.
2249 See also the functions `match-beginning', `match-end', `match-string',
2250 and `replace-match'. */)
2251 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2253 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 0);
2256 DEFUN ("re-search-forward", Fre_search_forward
, Sre_search_forward
, 1, 4,
2258 doc
: /* Search forward from point for regular expression REGEXP.
2259 Set point to the end of the occurrence found, and return point.
2260 An optional second argument bounds the search; it is a buffer position.
2261 The match found must not end after that position. A value of nil
2262 means search to the end of the accessible portion of the buffer.
2263 Optional third argument, if t, means if fail just return nil (no error).
2264 If not nil and not t, move to limit of search and return nil.
2265 Optional fourth argument COUNT, if a positive number, means to search
2266 for COUNT successive occurrences. If COUNT is negative, search
2267 backward, instead of forward, for -COUNT occurrences. A value of
2268 nil means the same as 1.
2269 With COUNT positive, the match found is the COUNTth one (or first,
2270 if COUNT is 1 or nil) in the buffer located entirely after the
2271 origin of the search; correspondingly with COUNT negative.
2273 Search case-sensitivity is determined by the value of the variable
2274 `case-fold-search', which see.
2276 See also the functions `match-beginning', `match-end', `match-string',
2277 and `replace-match'. */)
2278 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2280 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 0);
2283 DEFUN ("posix-search-backward", Fposix_search_backward
, Sposix_search_backward
, 1, 4,
2284 "sPosix search backward: ",
2285 doc
: /* Search backward from point for match for regular expression REGEXP.
2286 Find the longest match in accord with Posix regular expression rules.
2287 Set point to the beginning of the occurrence found, and return point.
2288 An optional second argument bounds the search; it is a buffer position.
2289 The match found must not begin before that position. A value of nil
2290 means search to the beginning of the accessible portion of the buffer.
2291 Optional third argument, if t, means if fail just return nil (no error).
2292 If not nil and not t, position at limit of search and return nil.
2293 Optional fourth argument COUNT, if a positive number, means to search
2294 for COUNT successive occurrences. If COUNT is negative, search
2295 forward, instead of backward, for -COUNT occurrences. A value of
2296 nil means the same as 1.
2297 With COUNT positive, the match found is the COUNTth to last one (or
2298 last, if COUNT is 1 or nil) in the buffer located entirely before
2299 the origin of the search; correspondingly with COUNT negative.
2301 Search case-sensitivity is determined by the value of the variable
2302 `case-fold-search', which see.
2304 See also the functions `match-beginning', `match-end', `match-string',
2305 and `replace-match'. */)
2306 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2308 return search_command (regexp
, bound
, noerror
, count
, -1, 1, 1);
2311 DEFUN ("posix-search-forward", Fposix_search_forward
, Sposix_search_forward
, 1, 4,
2313 doc
: /* Search forward from point for regular expression REGEXP.
2314 Find the longest match in accord with Posix regular expression rules.
2315 Set point to the end of the occurrence found, and return point.
2316 An optional second argument bounds the search; it is a buffer position.
2317 The match found must not end after that position. A value of nil
2318 means search to the end of the accessible portion of the buffer.
2319 Optional third argument, if t, means if fail just return nil (no error).
2320 If not nil and not t, move to limit of search and return nil.
2321 Optional fourth argument COUNT, if a positive number, means to search
2322 for COUNT successive occurrences. If COUNT is negative, search
2323 backward, instead of forward, for -COUNT occurrences. A value of
2324 nil means the same as 1.
2325 With COUNT positive, the match found is the COUNTth one (or first,
2326 if COUNT is 1 or nil) in the buffer located entirely after the
2327 origin of the search; correspondingly with COUNT negative.
2329 Search case-sensitivity is determined by the value of the variable
2330 `case-fold-search', which see.
2332 See also the functions `match-beginning', `match-end', `match-string',
2333 and `replace-match'. */)
2334 (Lisp_Object regexp
, Lisp_Object bound
, Lisp_Object noerror
, Lisp_Object count
)
2336 return search_command (regexp
, bound
, noerror
, count
, 1, 1, 1);
2339 DEFUN ("replace-match", Freplace_match
, Sreplace_match
, 1, 5, 0,
2340 doc
: /* Replace text matched by last search with NEWTEXT.
2341 Leave point at the end of the replacement text.
2343 If optional second arg FIXEDCASE is non-nil, do not alter the case of
2344 the replacement text. Otherwise, maybe capitalize the whole text, or
2345 maybe just word initials, based on the replaced text. If the replaced
2346 text has only capital letters and has at least one multiletter word,
2347 convert NEWTEXT to all caps. Otherwise if all words are capitalized
2348 in the replaced text, capitalize each word in NEWTEXT.
2350 If optional third arg LITERAL is non-nil, insert NEWTEXT literally.
2351 Otherwise treat `\\' as special:
2352 `\\&' in NEWTEXT means substitute original matched text.
2353 `\\N' means substitute what matched the Nth `\\(...\\)'.
2354 If Nth parens didn't match, substitute nothing.
2355 `\\\\' means insert one `\\'.
2356 `\\?' is treated literally
2357 (for compatibility with `query-replace-regexp').
2358 Any other character following `\\' signals an error.
2359 Case conversion does not apply to these substitutions.
2361 If optional fourth argument STRING is non-nil, it should be a string
2362 to act on; this should be the string on which the previous match was
2363 done via `string-match'. In this case, `replace-match' creates and
2364 returns a new string, made by copying STRING and replacing the part of
2365 STRING that was matched (the original STRING itself is not altered).
2367 The optional fifth argument SUBEXP specifies a subexpression;
2368 it says to replace just that subexpression with NEWTEXT,
2369 rather than replacing the entire matched text.
2370 This is, in a vague sense, the inverse of using `\\N' in NEWTEXT;
2371 `\\N' copies subexp N into NEWTEXT, but using N as SUBEXP puts
2372 NEWTEXT in place of subexp N.
2373 This is useful only after a regular expression search or match,
2374 since only regular expressions have distinguished subexpressions. */)
2375 (Lisp_Object newtext
, Lisp_Object fixedcase
, Lisp_Object literal
, Lisp_Object string
, Lisp_Object subexp
)
2377 enum { nochange
, all_caps
, cap_initial
} case_action
;
2378 ptrdiff_t pos
, pos_byte
;
2379 bool some_multiletter_word
;
2380 bool some_lowercase
;
2381 bool some_uppercase
;
2382 bool some_nonuppercase_initial
;
2385 ptrdiff_t opoint
, newpoint
;
2387 CHECK_STRING (newtext
);
2389 if (! NILP (string
))
2390 CHECK_STRING (string
);
2392 case_action
= nochange
; /* We tried an initialization */
2393 /* but some C compilers blew it */
2395 if (search_regs
.num_regs
<= 0)
2396 error ("`replace-match' called before any match found");
2402 CHECK_NUMBER (subexp
);
2403 if (! (0 <= XINT (subexp
) && XINT (subexp
) < search_regs
.num_regs
))
2404 args_out_of_range (subexp
, make_number (search_regs
.num_regs
));
2405 sub
= XINT (subexp
);
2410 if (search_regs
.start
[sub
] < BEGV
2411 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2412 || search_regs
.end
[sub
] > ZV
)
2413 args_out_of_range (make_number (search_regs
.start
[sub
]),
2414 make_number (search_regs
.end
[sub
]));
2418 if (search_regs
.start
[sub
] < 0
2419 || search_regs
.start
[sub
] > search_regs
.end
[sub
]
2420 || search_regs
.end
[sub
] > SCHARS (string
))
2421 args_out_of_range (make_number (search_regs
.start
[sub
]),
2422 make_number (search_regs
.end
[sub
]));
2425 if (NILP (fixedcase
))
2427 /* Decide how to casify by examining the matched text. */
2430 pos
= search_regs
.start
[sub
];
2431 last
= search_regs
.end
[sub
];
2434 pos_byte
= CHAR_TO_BYTE (pos
);
2436 pos_byte
= string_char_to_byte (string
, pos
);
2439 case_action
= all_caps
;
2441 /* some_multiletter_word is set nonzero if any original word
2442 is more than one letter long. */
2443 some_multiletter_word
= 0;
2445 some_nonuppercase_initial
= 0;
2452 c
= FETCH_CHAR_AS_MULTIBYTE (pos_byte
);
2453 INC_BOTH (pos
, pos_byte
);
2456 FETCH_STRING_CHAR_AS_MULTIBYTE_ADVANCE (c
, string
, pos
, pos_byte
);
2460 /* Cannot be all caps if any original char is lower case */
2463 if (SYNTAX (prevc
) != Sword
)
2464 some_nonuppercase_initial
= 1;
2466 some_multiletter_word
= 1;
2468 else if (uppercasep (c
))
2471 if (SYNTAX (prevc
) != Sword
)
2474 some_multiletter_word
= 1;
2478 /* If the initial is a caseless word constituent,
2479 treat that like a lowercase initial. */
2480 if (SYNTAX (prevc
) != Sword
)
2481 some_nonuppercase_initial
= 1;
2487 /* Convert to all caps if the old text is all caps
2488 and has at least one multiletter word. */
2489 if (! some_lowercase
&& some_multiletter_word
)
2490 case_action
= all_caps
;
2491 /* Capitalize each word, if the old text has all capitalized words. */
2492 else if (!some_nonuppercase_initial
&& some_multiletter_word
)
2493 case_action
= cap_initial
;
2494 else if (!some_nonuppercase_initial
&& some_uppercase
)
2495 /* Should x -> yz, operating on X, give Yz or YZ?
2496 We'll assume the latter. */
2497 case_action
= all_caps
;
2499 case_action
= nochange
;
2502 /* Do replacement in a string. */
2505 Lisp_Object before
, after
;
2507 before
= Fsubstring (string
, make_number (0),
2508 make_number (search_regs
.start
[sub
]));
2509 after
= Fsubstring (string
, make_number (search_regs
.end
[sub
]), Qnil
);
2511 /* Substitute parts of the match into NEWTEXT
2515 ptrdiff_t lastpos
= 0;
2516 ptrdiff_t lastpos_byte
= 0;
2517 /* We build up the substituted string in ACCUM. */
2520 ptrdiff_t length
= SBYTES (newtext
);
2524 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2526 ptrdiff_t substart
= -1;
2527 ptrdiff_t subend
= 0;
2528 bool delbackslash
= 0;
2530 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2534 FETCH_STRING_CHAR_ADVANCE (c
, newtext
, pos
, pos_byte
);
2538 substart
= search_regs
.start
[sub
];
2539 subend
= search_regs
.end
[sub
];
2541 else if (c
>= '1' && c
<= '9')
2543 if (c
- '0' < search_regs
.num_regs
2544 && search_regs
.start
[c
- '0'] >= 0)
2546 substart
= search_regs
.start
[c
- '0'];
2547 subend
= search_regs
.end
[c
- '0'];
2551 /* If that subexp did not match,
2552 replace \\N with nothing. */
2560 error ("Invalid use of `\\' in replacement text");
2564 if (pos
- 2 != lastpos
)
2565 middle
= substring_both (newtext
, lastpos
,
2567 pos
- 2, pos_byte
- 2);
2570 accum
= concat3 (accum
, middle
,
2572 make_number (substart
),
2573 make_number (subend
)));
2575 lastpos_byte
= pos_byte
;
2577 else if (delbackslash
)
2579 middle
= substring_both (newtext
, lastpos
,
2581 pos
- 1, pos_byte
- 1);
2583 accum
= concat2 (accum
, middle
);
2585 lastpos_byte
= pos_byte
;
2590 middle
= substring_both (newtext
, lastpos
,
2596 newtext
= concat2 (accum
, middle
);
2599 /* Do case substitution in NEWTEXT if desired. */
2600 if (case_action
== all_caps
)
2601 newtext
= Fupcase (newtext
);
2602 else if (case_action
== cap_initial
)
2603 newtext
= Fupcase_initials (newtext
);
2605 return concat3 (before
, newtext
, after
);
2608 /* Record point, then move (quietly) to the start of the match. */
2609 if (PT
>= search_regs
.end
[sub
])
2611 else if (PT
> search_regs
.start
[sub
])
2612 opoint
= search_regs
.end
[sub
] - ZV
;
2616 /* If we want non-literal replacement,
2617 perform substitution on the replacement string. */
2620 ptrdiff_t length
= SBYTES (newtext
);
2621 unsigned char *substed
;
2622 ptrdiff_t substed_alloc_size
, substed_len
;
2623 bool buf_multibyte
= !NILP (BVAR (current_buffer
, enable_multibyte_characters
));
2624 bool str_multibyte
= STRING_MULTIBYTE (newtext
);
2625 bool really_changed
= 0;
2627 substed_alloc_size
= (length
<= (STRING_BYTES_BOUND
- 100) / 2
2629 : STRING_BYTES_BOUND
);
2630 substed
= xmalloc (substed_alloc_size
);
2633 /* Go thru NEWTEXT, producing the actual text to insert in
2634 SUBSTED while adjusting multibyteness to that of the current
2637 for (pos_byte
= 0, pos
= 0; pos_byte
< length
;)
2639 unsigned char str
[MAX_MULTIBYTE_LENGTH
];
2640 const unsigned char *add_stuff
= NULL
;
2641 ptrdiff_t add_len
= 0;
2646 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
, pos
, pos_byte
);
2648 c
= CHAR_TO_BYTE8 (c
);
2652 /* Note that we don't have to increment POS. */
2653 c
= SREF (newtext
, pos_byte
++);
2655 MAKE_CHAR_MULTIBYTE (c
);
2658 /* Either set ADD_STUFF and ADD_LEN to the text to put in SUBSTED,
2659 or set IDX to a match index, which means put that part
2660 of the buffer text into SUBSTED. */
2668 FETCH_STRING_CHAR_ADVANCE_NO_CHECK (c
, newtext
,
2670 if (!buf_multibyte
&& !ASCII_CHAR_P (c
))
2671 c
= CHAR_TO_BYTE8 (c
);
2675 c
= SREF (newtext
, pos_byte
++);
2677 MAKE_CHAR_MULTIBYTE (c
);
2682 else if (c
>= '1' && c
<= '9' && c
- '0' < search_regs
.num_regs
)
2684 if (search_regs
.start
[c
- '0'] >= 1)
2688 add_len
= 1, add_stuff
= (unsigned char *) "\\";
2692 error ("Invalid use of `\\' in replacement text");
2697 add_len
= CHAR_STRING (c
, str
);
2701 /* If we want to copy part of a previous match,
2702 set up ADD_STUFF and ADD_LEN to point to it. */
2705 ptrdiff_t begbyte
= CHAR_TO_BYTE (search_regs
.start
[idx
]);
2706 add_len
= CHAR_TO_BYTE (search_regs
.end
[idx
]) - begbyte
;
2707 if (search_regs
.start
[idx
] < GPT
&& GPT
< search_regs
.end
[idx
])
2708 move_gap_both (search_regs
.start
[idx
], begbyte
);
2709 add_stuff
= BYTE_POS_ADDR (begbyte
);
2712 /* Now the stuff we want to add to SUBSTED
2713 is invariably ADD_LEN bytes starting at ADD_STUFF. */
2715 /* Make sure SUBSTED is big enough. */
2716 if (substed_alloc_size
- substed_len
< add_len
)
2718 xpalloc (substed
, &substed_alloc_size
,
2719 add_len
- (substed_alloc_size
- substed_len
),
2720 STRING_BYTES_BOUND
, 1);
2722 /* Now add to the end of SUBSTED. */
2725 memcpy (substed
+ substed_len
, add_stuff
, add_len
);
2726 substed_len
+= add_len
;
2731 newtext
= make_specified_string ((const char *) substed
, -1,
2732 substed_len
, buf_multibyte
);
2736 /* The functions below modify the buffer, so they could trigger
2737 various modification hooks (see signal_before_change and
2738 signal_after_change). If these hooks clobber the match data we
2739 error out since otherwise this will result in confusing bugs. */
2740 ptrdiff_t sub_start
= search_regs
.start
[sub
];
2741 ptrdiff_t sub_end
= search_regs
.end
[sub
];
2742 unsigned num_regs
= search_regs
.num_regs
;
2743 newpoint
= search_regs
.start
[sub
] + SCHARS (newtext
);
2745 /* Replace the old text with the new in the cleanest possible way. */
2746 replace_range (search_regs
.start
[sub
], search_regs
.end
[sub
],
2747 newtext
, 1, 0, 1, 1);
2748 /* Update saved data to match adjustment made by replace_range. */
2750 ptrdiff_t change
= newpoint
- sub_end
;
2751 if (sub_start
>= sub_end
)
2752 sub_start
+= change
;
2756 if (case_action
== all_caps
)
2757 Fupcase_region (make_number (search_regs
.start
[sub
]),
2758 make_number (newpoint
));
2759 else if (case_action
== cap_initial
)
2760 Fupcase_initials_region (make_number (search_regs
.start
[sub
]),
2761 make_number (newpoint
));
2763 if (search_regs
.start
[sub
] != sub_start
2764 || search_regs
.end
[sub
] != sub_end
2765 || search_regs
.num_regs
!= num_regs
)
2766 error ("Match data clobbered by buffer modification hooks");
2768 /* Put point back where it was in the text. */
2770 TEMP_SET_PT (opoint
+ ZV
);
2772 TEMP_SET_PT (opoint
);
2774 /* Now move point "officially" to the start of the inserted replacement. */
2775 move_if_not_intangible (newpoint
);
2781 match_limit (Lisp_Object num
, bool beginningp
)
2788 args_out_of_range (num
, make_number (0));
2789 if (search_regs
.num_regs
<= 0)
2790 error ("No match data, because no search succeeded");
2791 if (n
>= search_regs
.num_regs
2792 || search_regs
.start
[n
] < 0)
2794 return (make_number ((beginningp
) ? search_regs
.start
[n
]
2795 : search_regs
.end
[n
]));
2798 DEFUN ("match-beginning", Fmatch_beginning
, Smatch_beginning
, 1, 1, 0,
2799 doc
: /* Return position of start of text matched by last search.
2800 SUBEXP, a number, specifies which parenthesized expression in the last
2802 Value is nil if SUBEXPth pair didn't match, or there were less than
2804 Zero means the entire text matched by the whole regexp or whole string.
2806 Return value is undefined if the last search failed. */)
2807 (Lisp_Object subexp
)
2809 return match_limit (subexp
, 1);
2812 DEFUN ("match-end", Fmatch_end
, Smatch_end
, 1, 1, 0,
2813 doc
: /* Return position of end of text matched by last search.
2814 SUBEXP, a number, specifies which parenthesized expression in the last
2816 Value is nil if SUBEXPth pair didn't match, or there were less than
2818 Zero means the entire text matched by the whole regexp or whole string.
2820 Return value is undefined if the last search failed. */)
2821 (Lisp_Object subexp
)
2823 return match_limit (subexp
, 0);
2826 DEFUN ("match-data", Fmatch_data
, Smatch_data
, 0, 3, 0,
2827 doc
: /* Return a list describing what the last search matched.
2828 Element 2N is `(match-beginning N)'; element 2N + 1 is `(match-end N)'.
2829 All the elements are markers or nil (nil if the Nth pair didn't match)
2830 if the last match was on a buffer; integers or nil if a string was matched.
2831 Use `set-match-data' to reinstate the data in this list.
2833 If INTEGERS (the optional first argument) is non-nil, always use
2834 integers (rather than markers) to represent buffer positions. In
2835 this case, and if the last match was in a buffer, the buffer will get
2836 stored as one additional element at the end of the list.
2838 If REUSE is a list, reuse it as part of the value. If REUSE is long
2839 enough to hold all the values, and if INTEGERS is non-nil, no consing
2842 If optional third arg RESEAT is non-nil, any previous markers on the
2843 REUSE list will be modified to point to nowhere.
2845 Return value is undefined if the last search failed. */)
2846 (Lisp_Object integers
, Lisp_Object reuse
, Lisp_Object reseat
)
2848 Lisp_Object tail
, prev
;
2853 for (tail
= reuse
; CONSP (tail
); tail
= XCDR (tail
))
2854 if (MARKERP (XCAR (tail
)))
2856 unchain_marker (XMARKER (XCAR (tail
)));
2857 XSETCAR (tail
, Qnil
);
2860 if (NILP (last_thing_searched
))
2866 SAFE_NALLOCA (data
, 1, 2 * search_regs
.num_regs
+ 1);
2869 for (i
= 0; i
< search_regs
.num_regs
; i
++)
2871 ptrdiff_t start
= search_regs
.start
[i
];
2874 if (EQ (last_thing_searched
, Qt
)
2875 || ! NILP (integers
))
2877 XSETFASTINT (data
[2 * i
], start
);
2878 XSETFASTINT (data
[2 * i
+ 1], search_regs
.end
[i
]);
2880 else if (BUFFERP (last_thing_searched
))
2882 data
[2 * i
] = Fmake_marker ();
2883 Fset_marker (data
[2 * i
],
2884 make_number (start
),
2885 last_thing_searched
);
2886 data
[2 * i
+ 1] = Fmake_marker ();
2887 Fset_marker (data
[2 * i
+ 1],
2888 make_number (search_regs
.end
[i
]),
2889 last_thing_searched
);
2892 /* last_thing_searched must always be Qt, a buffer, or Qnil. */
2898 data
[2 * i
] = data
[2 * i
+ 1] = Qnil
;
2901 if (BUFFERP (last_thing_searched
) && !NILP (integers
))
2903 data
[len
] = last_thing_searched
;
2907 /* If REUSE is not usable, cons up the values and return them. */
2908 if (! CONSP (reuse
))
2909 reuse
= Flist (len
, data
);
2912 /* If REUSE is a list, store as many value elements as will fit
2913 into the elements of REUSE. */
2914 for (i
= 0, tail
= reuse
; CONSP (tail
);
2915 i
++, tail
= XCDR (tail
))
2918 XSETCAR (tail
, data
[i
]);
2920 XSETCAR (tail
, Qnil
);
2924 /* If we couldn't fit all value elements into REUSE,
2925 cons up the rest of them and add them to the end of REUSE. */
2927 XSETCDR (prev
, Flist (len
- i
, data
+ i
));
2934 /* We used to have an internal use variant of `reseat' described as:
2936 If RESEAT is `evaporate', put the markers back on the free list
2937 immediately. No other references to the markers must exist in this
2938 case, so it is used only internally on the unwind stack and
2939 save-match-data from Lisp.
2941 But it was ill-conceived: those supposedly-internal markers get exposed via
2942 the undo-list, so freeing them here is unsafe. */
2944 DEFUN ("set-match-data", Fset_match_data
, Sset_match_data
, 1, 2, 0,
2945 doc
: /* Set internal data on last search match from elements of LIST.
2946 LIST should have been created by calling `match-data' previously.
2948 If optional arg RESEAT is non-nil, make markers on LIST point nowhere. */)
2949 (register Lisp_Object list
, Lisp_Object reseat
)
2952 register Lisp_Object marker
;
2954 if (running_asynch_code
)
2955 save_search_regs ();
2959 /* Unless we find a marker with a buffer or an explicit buffer
2960 in LIST, assume that this match data came from a string. */
2961 last_thing_searched
= Qt
;
2963 /* Allocate registers if they don't already exist. */
2965 EMACS_INT length
= XFASTINT (Flength (list
)) / 2;
2967 if (length
> search_regs
.num_regs
)
2969 ptrdiff_t num_regs
= search_regs
.num_regs
;
2970 if (PTRDIFF_MAX
< length
)
2971 memory_full (SIZE_MAX
);
2973 xpalloc (search_regs
.start
, &num_regs
, length
- num_regs
,
2974 min (PTRDIFF_MAX
, UINT_MAX
), sizeof (regoff_t
));
2976 xrealloc (search_regs
.end
, num_regs
* sizeof (regoff_t
));
2978 for (i
= search_regs
.num_regs
; i
< num_regs
; i
++)
2979 search_regs
.start
[i
] = -1;
2981 search_regs
.num_regs
= num_regs
;
2984 for (i
= 0; CONSP (list
); i
++)
2986 marker
= XCAR (list
);
2987 if (BUFFERP (marker
))
2989 last_thing_searched
= marker
;
2996 search_regs
.start
[i
] = -1;
3005 if (MARKERP (marker
))
3007 if (XMARKER (marker
)->buffer
== 0)
3008 XSETFASTINT (marker
, 0);
3010 XSETBUFFER (last_thing_searched
, XMARKER (marker
)->buffer
);
3013 CHECK_NUMBER_COERCE_MARKER (marker
);
3016 if (!NILP (reseat
) && MARKERP (m
))
3018 unchain_marker (XMARKER (m
));
3019 XSETCAR (list
, Qnil
);
3022 if ((list
= XCDR (list
), !CONSP (list
)))
3025 m
= marker
= XCAR (list
);
3027 if (MARKERP (marker
) && XMARKER (marker
)->buffer
== 0)
3028 XSETFASTINT (marker
, 0);
3030 CHECK_NUMBER_COERCE_MARKER (marker
);
3031 if ((XINT (from
) < 0
3032 ? TYPE_MINIMUM (regoff_t
) <= XINT (from
)
3033 : XINT (from
) <= TYPE_MAXIMUM (regoff_t
))
3034 && (XINT (marker
) < 0
3035 ? TYPE_MINIMUM (regoff_t
) <= XINT (marker
)
3036 : XINT (marker
) <= TYPE_MAXIMUM (regoff_t
)))
3038 search_regs
.start
[i
] = XINT (from
);
3039 search_regs
.end
[i
] = XINT (marker
);
3043 search_regs
.start
[i
] = -1;
3046 if (!NILP (reseat
) && MARKERP (m
))
3048 unchain_marker (XMARKER (m
));
3049 XSETCAR (list
, Qnil
);
3055 for (; i
< search_regs
.num_regs
; i
++)
3056 search_regs
.start
[i
] = -1;
3062 /* If true the match data have been saved in saved_search_regs
3063 during the execution of a sentinel or filter. */
3064 static bool search_regs_saved
;
3065 static struct re_registers saved_search_regs
;
3066 static Lisp_Object saved_last_thing_searched
;
3068 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
3069 if asynchronous code (filter or sentinel) is running. */
3071 save_search_regs (void)
3073 if (!search_regs_saved
)
3075 saved_search_regs
.num_regs
= search_regs
.num_regs
;
3076 saved_search_regs
.start
= search_regs
.start
;
3077 saved_search_regs
.end
= search_regs
.end
;
3078 saved_last_thing_searched
= last_thing_searched
;
3079 last_thing_searched
= Qnil
;
3080 search_regs
.num_regs
= 0;
3081 search_regs
.start
= 0;
3082 search_regs
.end
= 0;
3084 search_regs_saved
= 1;
3088 /* Called upon exit from filters and sentinels. */
3090 restore_search_regs (void)
3092 if (search_regs_saved
)
3094 if (search_regs
.num_regs
> 0)
3096 xfree (search_regs
.start
);
3097 xfree (search_regs
.end
);
3099 search_regs
.num_regs
= saved_search_regs
.num_regs
;
3100 search_regs
.start
= saved_search_regs
.start
;
3101 search_regs
.end
= saved_search_regs
.end
;
3102 last_thing_searched
= saved_last_thing_searched
;
3103 saved_last_thing_searched
= Qnil
;
3104 search_regs_saved
= 0;
3108 /* Called from replace-match via replace_range. */
3110 update_search_regs (ptrdiff_t oldstart
, ptrdiff_t oldend
, ptrdiff_t newend
)
3112 /* Adjust search data for this change. */
3113 ptrdiff_t change
= newend
- oldend
;
3116 for (i
= 0; i
< search_regs
.num_regs
; i
++)
3118 if (search_regs
.start
[i
] >= oldend
)
3119 search_regs
.start
[i
] += change
;
3120 else if (search_regs
.start
[i
] > oldstart
)
3121 search_regs
.start
[i
] = oldstart
;
3122 if (search_regs
.end
[i
] >= oldend
)
3123 search_regs
.end
[i
] += change
;
3124 else if (search_regs
.end
[i
] > oldstart
)
3125 search_regs
.end
[i
] = oldstart
;
3130 unwind_set_match_data (Lisp_Object list
)
3132 /* It is NOT ALWAYS safe to free (evaporate) the markers immediately. */
3133 Fset_match_data (list
, Qt
);
3136 /* Called to unwind protect the match data. */
3138 record_unwind_save_match_data (void)
3140 record_unwind_protect (unwind_set_match_data
,
3141 Fmatch_data (Qnil
, Qnil
, Qnil
));
3144 /* Quote a string to deactivate reg-expr chars */
3146 DEFUN ("regexp-quote", Fregexp_quote
, Sregexp_quote
, 1, 1, 0,
3147 doc
: /* Return a regexp string which matches exactly STRING and nothing else. */)
3148 (Lisp_Object string
)
3150 char *in
, *out
, *end
;
3152 ptrdiff_t backslashes_added
= 0;
3154 CHECK_STRING (string
);
3157 SAFE_NALLOCA (temp
, 2, SBYTES (string
));
3159 /* Now copy the data into the new string, inserting escapes. */
3161 in
= SSDATA (string
);
3162 end
= in
+ SBYTES (string
);
3165 for (; in
!= end
; in
++)
3168 || *in
== '*' || *in
== '.' || *in
== '\\'
3169 || *in
== '?' || *in
== '+'
3170 || *in
== '^' || *in
== '$')
3171 *out
++ = '\\', backslashes_added
++;
3176 = make_specified_string (temp
,
3177 SCHARS (string
) + backslashes_added
,
3179 STRING_MULTIBYTE (string
));
3184 /* Like find_newline, but doesn't use the cache, and only searches forward. */
3186 find_newline1 (ptrdiff_t start
, ptrdiff_t start_byte
, ptrdiff_t end
,
3187 ptrdiff_t end_byte
, ptrdiff_t count
, ptrdiff_t *shortage
,
3188 ptrdiff_t *bytepos
, bool allow_quit
)
3193 end
= ZV
, end_byte
= ZV_BYTE
;
3198 end
= BEGV
, end_byte
= BEGV_BYTE
;
3201 end_byte
= CHAR_TO_BYTE (end
);
3206 immediate_quit
= allow_quit
;
3209 while (start
!= end
)
3211 /* Our innermost scanning loop is very simple; it doesn't know
3212 about gaps, buffer ends, or the newline cache. ceiling is
3213 the position of the last character before the next such
3214 obstacle --- the last character the dumb search loop should
3216 ptrdiff_t tem
, ceiling_byte
= end_byte
- 1;
3218 if (start_byte
== -1)
3219 start_byte
= CHAR_TO_BYTE (start
);
3221 /* The dumb loop can only scan text stored in contiguous
3222 bytes. BUFFER_CEILING_OF returns the last character
3223 position that is contiguous, so the ceiling is the
3224 position after that. */
3225 tem
= BUFFER_CEILING_OF (start_byte
);
3226 ceiling_byte
= min (tem
, ceiling_byte
);
3229 /* The termination address of the dumb loop. */
3230 unsigned char *lim_addr
= BYTE_POS_ADDR (ceiling_byte
) + 1;
3231 ptrdiff_t lim_byte
= ceiling_byte
+ 1;
3233 /* Nonpositive offsets (relative to LIM_ADDR and LIM_BYTE)
3234 of the base, the cursor, and the next line. */
3235 ptrdiff_t base
= start_byte
- lim_byte
;
3236 ptrdiff_t cursor
, next
;
3238 for (cursor
= base
; cursor
< 0; cursor
= next
)
3240 /* The dumb loop. */
3241 unsigned char *nl
= memchr (lim_addr
+ cursor
, '\n', - cursor
);
3242 next
= nl
? nl
- lim_addr
: 0;
3252 *bytepos
= lim_byte
+ next
;
3253 return BYTE_TO_CHAR (lim_byte
+ next
);
3257 start_byte
= lim_byte
;
3258 start
= BYTE_TO_CHAR (start_byte
);
3267 *bytepos
= start_byte
== -1 ? CHAR_TO_BYTE (start
) : start_byte
;
3268 eassert (*bytepos
== CHAR_TO_BYTE (start
));
3273 DEFUN ("newline-cache-check", Fnewline_cache_check
, Snewline_cache_check
,
3275 doc
: /* Check the newline cache of BUFFER against buffer contents.
3277 BUFFER defaults to the current buffer.
3279 Value is an array of 2 sub-arrays of buffer positions for newlines,
3280 the first based on the cache, the second based on actually scanning
3281 the buffer. If the buffer doesn't have a cache, the value is nil. */)
3282 (Lisp_Object buffer
)
3284 struct buffer
*buf
, *old
= NULL
;
3285 ptrdiff_t shortage
, nl_count_cache
, nl_count_buf
;
3286 Lisp_Object cache_newlines
, buf_newlines
, val
;
3287 ptrdiff_t from
, found
, i
;
3290 buf
= current_buffer
;
3293 CHECK_BUFFER (buffer
);
3294 buf
= XBUFFER (buffer
);
3295 old
= current_buffer
;
3297 if (buf
->base_buffer
)
3298 buf
= buf
->base_buffer
;
3300 /* If the buffer doesn't have a newline cache, return nil. */
3301 if (NILP (BVAR (buf
, cache_long_scans
))
3302 || buf
->newline_cache
== NULL
)
3305 /* find_newline can only work on the current buffer. */
3307 set_buffer_internal_1 (buf
);
3309 /* How many newlines are there according to the cache? */
3310 find_newline (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3311 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3312 nl_count_cache
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3314 /* Create vector and populate it. */
3315 cache_newlines
= make_uninit_vector (nl_count_cache
);
3319 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3321 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3323 found
= find_newline (from
, from_byte
, 0, -1, 1, &shortage
,
3325 if (shortage
!= 0 || i
>= nl_count_cache
)
3327 ASET (cache_newlines
, i
, make_number (found
- 1));
3329 /* Fill the rest of slots with an invalid position. */
3330 for ( ; i
< nl_count_cache
; i
++)
3331 ASET (cache_newlines
, i
, make_number (-1));
3334 /* Now do the same, but without using the cache. */
3335 find_newline1 (BEGV
, BEGV_BYTE
, ZV
, ZV_BYTE
,
3336 TYPE_MAXIMUM (ptrdiff_t), &shortage
, NULL
, true);
3337 nl_count_buf
= TYPE_MAXIMUM (ptrdiff_t) - shortage
;
3338 buf_newlines
= make_uninit_vector (nl_count_buf
);
3341 for (from
= BEGV
, found
= from
, i
= 0; from
< ZV
; from
= found
, i
++)
3343 ptrdiff_t from_byte
= CHAR_TO_BYTE (from
);
3345 found
= find_newline1 (from
, from_byte
, 0, -1, 1, &shortage
,
3347 if (shortage
!= 0 || i
>= nl_count_buf
)
3349 ASET (buf_newlines
, i
, make_number (found
- 1));
3351 for ( ; i
< nl_count_buf
; i
++)
3352 ASET (buf_newlines
, i
, make_number (-1));
3355 /* Construct the value and return it. */
3356 val
= make_uninit_vector (2);
3357 ASET (val
, 0, cache_newlines
);
3358 ASET (val
, 1, buf_newlines
);
3361 set_buffer_internal_1 (old
);
3366 syms_of_search (void)
3370 for (i
= 0; i
< REGEXP_CACHE_SIZE
; ++i
)
3372 searchbufs
[i
].buf
.allocated
= 100;
3373 searchbufs
[i
].buf
.buffer
= xmalloc (100);
3374 searchbufs
[i
].buf
.fastmap
= searchbufs
[i
].fastmap
;
3375 searchbufs
[i
].regexp
= Qnil
;
3376 searchbufs
[i
].whitespace_regexp
= Qnil
;
3377 searchbufs
[i
].syntax_table
= Qnil
;
3378 staticpro (&searchbufs
[i
].regexp
);
3379 staticpro (&searchbufs
[i
].whitespace_regexp
);
3380 staticpro (&searchbufs
[i
].syntax_table
);
3381 searchbufs
[i
].next
= (i
== REGEXP_CACHE_SIZE
-1 ? 0 : &searchbufs
[i
+1]);
3383 searchbuf_head
= &searchbufs
[0];
3385 /* Error condition used for failing searches. */
3386 DEFSYM (Qsearch_failed
, "search-failed");
3388 /* Error condition signaled when regexp compile_pattern fails. */
3389 DEFSYM (Qinvalid_regexp
, "invalid-regexp");
3391 Fput (Qsearch_failed
, Qerror_conditions
,
3392 listn (CONSTYPE_PURE
, 2, Qsearch_failed
, Qerror
));
3393 Fput (Qsearch_failed
, Qerror_message
,
3394 build_pure_c_string ("Search failed"));
3396 Fput (Qinvalid_regexp
, Qerror_conditions
,
3397 listn (CONSTYPE_PURE
, 2, Qinvalid_regexp
, Qerror
));
3398 Fput (Qinvalid_regexp
, Qerror_message
,
3399 build_pure_c_string ("Invalid regexp"));
3401 last_thing_searched
= Qnil
;
3402 staticpro (&last_thing_searched
);
3404 saved_last_thing_searched
= Qnil
;
3405 staticpro (&saved_last_thing_searched
);
3407 DEFVAR_LISP ("search-spaces-regexp", Vsearch_spaces_regexp
,
3408 doc
: /* Regexp to substitute for bunches of spaces in regexp search.
3409 Some commands use this for user-specified regexps.
3410 Spaces that occur inside character classes or repetition operators
3411 or other such regexp constructs are not replaced with this.
3412 A value of nil (which is the normal value) means treat spaces literally. */);
3413 Vsearch_spaces_regexp
= Qnil
;
3415 DEFSYM (Qinhibit_changing_match_data
, "inhibit-changing-match-data");
3416 DEFVAR_LISP ("inhibit-changing-match-data", Vinhibit_changing_match_data
,
3417 doc
: /* Internal use only.
3418 If non-nil, the primitive searching and matching functions
3419 such as `looking-at', `string-match', `re-search-forward', etc.,
3420 do not set the match data. The proper way to use this variable
3421 is to bind it with `let' around a small expression. */);
3422 Vinhibit_changing_match_data
= Qnil
;
3424 defsubr (&Slooking_at
);
3425 defsubr (&Sposix_looking_at
);
3426 defsubr (&Sstring_match
);
3427 defsubr (&Sposix_string_match
);
3428 defsubr (&Ssearch_forward
);
3429 defsubr (&Ssearch_backward
);
3430 defsubr (&Sre_search_forward
);
3431 defsubr (&Sre_search_backward
);
3432 defsubr (&Sposix_search_forward
);
3433 defsubr (&Sposix_search_backward
);
3434 defsubr (&Sreplace_match
);
3435 defsubr (&Smatch_beginning
);
3436 defsubr (&Smatch_end
);
3437 defsubr (&Smatch_data
);
3438 defsubr (&Sset_match_data
);
3439 defsubr (&Sregexp_quote
);
3440 defsubr (&Snewline_cache_check
);