2 * Copyright (C) 1984-2009 Mark Nudelman
4 * You may distribute under the terms of either the GNU General Public
5 * License or the Less License, as specified in the README file.
7 * For more information about less, or for information on how to
8 * contact the author, see the README file.
13 * Routines to search a file for a pattern.
21 #define MINPOS(a,b) (((a) < (b)) ? (a) : (b))
22 #define MAXPOS(a,b) (((a) > (b)) ? (a) : (b))
25 extern int how_search
;
29 extern int jump_sline
;
32 extern int status_col
;
33 extern void * constant ml_search
;
34 extern POSITION start_attnpos
;
35 extern POSITION end_attnpos
;
37 extern int screen_trashed
;
39 extern int hilite_search
;
40 extern int size_linebuf
;
42 extern int can_goto_line
;
43 static int hide_hilite
;
44 static POSITION prep_startpos
;
45 static POSITION prep_endpos
;
46 static int is_caseless
;
47 static int is_ucase_pattern
;
51 struct hilite
*hl_next
;
55 static struct hilite hilite_anchor
= { NULL
, NULL_POSITION
, NULL_POSITION
};
56 static struct hilite filter_anchor
= { NULL
, NULL_POSITION
, NULL_POSITION
};
57 #define hl_first hl_next
61 * These are the static variables that represent the "remembered"
62 * search pattern and filter pattern.
65 DEFINE_PATTERN(compiled
);
70 static struct pattern_info search_info
;
71 static struct pattern_info filter_info
;
74 * Compile and save a search pattern.
77 set_pattern(info
, pattern
, search_type
)
78 struct pattern_info
*info
;
83 CLEAR_PATTERN(search_info
.compiled
);
84 else if (compile_pattern(pattern
, search_type
, &info
->compiled
) < 0)
86 /* Pattern compiled successfully; save the text too. */
87 if (info
->text
!= NULL
)
92 info
->text
= (char *) ecalloc(1, strlen(pattern
)+1);
93 strcpy(info
->text
, pattern
);
95 info
->search_type
= search_type
;
100 * Discard a saved pattern.
104 struct pattern_info
*info
;
106 if (info
->text
!= NULL
)
109 uncompile_pattern(&info
->compiled
);
113 * Initialize saved pattern to nothing.
117 struct pattern_info
*info
;
119 CLEAR_PATTERN(info
->compiled
);
121 info
->search_type
= 0;
125 * Initialize search variables.
130 init_pattern(&search_info
);
131 init_pattern(&filter_info
);
135 * Determine which text conversions to perform before pattern matching.
141 if (is_caseless
|| bs_mode
== BS_SPECIAL
)
145 if (bs_mode
== BS_SPECIAL
)
147 if (bs_mode
!= BS_CONTROL
)
149 } else if (bs_mode
!= BS_CONTROL
)
153 if (ctldisp
== OPT_ONPLUS
)
159 * Are there any uppercase letters in this string?
165 char *str_end
= str
+ strlen(str
);
168 while (str
< str_end
)
170 ch
= step_char(&str
, +1, str_end
);
178 * Is there a previous (remembered) search pattern?
182 struct pattern_info
*info
;
184 if (info
->search_type
& SRCH_NO_REGEX
)
185 return (info
->text
!= NULL
);
186 return (!is_null_pattern(info
->compiled
));
191 * Repaint the hilites currently displayed on the screen.
192 * Repaint each line which contains highlighted text.
193 * If on==0, force all hilites off.
202 int save_hide_hilite
;
207 save_hide_hilite
= hide_hilite
;
218 hide_hilite
= save_hide_hilite
;
222 for (slinenum
= TOP
; slinenum
< TOP
+ sc_height
-1; slinenum
++)
224 pos
= position(slinenum
);
225 if (pos
== NULL_POSITION
)
227 epos
= position(slinenum
+1);
228 (void) forw_line(pos
);
232 lower_left(); // if !oldbot
233 hide_hilite
= save_hide_hilite
;
237 * Clear the attn hilite.
243 POSITION old_start_attnpos
;
244 POSITION old_end_attnpos
;
249 if (start_attnpos
== NULL_POSITION
)
251 old_start_attnpos
= start_attnpos
;
252 old_end_attnpos
= end_attnpos
;
253 start_attnpos
= end_attnpos
= NULL_POSITION
;
263 for (slinenum
= TOP
; slinenum
< TOP
+ sc_height
-1; slinenum
++)
265 pos
= position(slinenum
);
266 if (pos
== NULL_POSITION
)
268 epos
= position(slinenum
+1);
269 if (pos
< old_end_attnpos
&&
270 (epos
== NULL_POSITION
|| epos
> old_start_attnpos
))
272 (void) forw_line(pos
);
284 * Hide search string highlighting.
289 if (!prev_pattern(&search_info
))
291 error("No previous regular expression", NULL_PARG
);
295 hide_hilite
= !hide_hilite
;
302 * Clear the hilite list.
306 struct hilite
*anchor
;
309 struct hilite
*nexthl
;
311 for (hl
= anchor
->hl_first
; hl
!= NULL
; hl
= nexthl
)
313 nexthl
= hl
->hl_next
;
316 anchor
->hl_first
= NULL
;
317 prep_startpos
= prep_endpos
= NULL_POSITION
;
323 clr_hlist(&hilite_anchor
);
329 clr_hlist(&filter_anchor
);
333 * Should any characters in a specified range be highlighted?
336 is_hilited_range(pos
, epos
)
343 * Look at each highlight and see if any part of it falls in the range.
345 for (hl
= hilite_anchor
.hl_first
; hl
!= NULL
; hl
= hl
->hl_next
)
347 if (hl
->hl_endpos
> pos
&&
348 (epos
== NULL_POSITION
|| epos
> hl
->hl_startpos
))
355 * Is a line "filtered" -- that is, should it be hidden?
363 if (ch_getflags() & CH_HELPFILE
)
367 * Look at each filter and see if the start position
368 * equals the start position of the line.
370 for (hl
= filter_anchor
.hl_first
; hl
!= NULL
; hl
= hl
->hl_next
)
372 if (hl
->hl_startpos
== pos
)
379 * Should any characters in a specified range be highlighted?
380 * If nohide is nonzero, don't consider hide_hilite.
383 is_hilited(pos
, epos
, nohide
, p_matches
)
391 if (p_matches
!= NULL
)
395 start_attnpos
!= NULL_POSITION
&&
397 (epos
== NULL_POSITION
|| epos
> start_attnpos
))
399 * The attn line overlaps this range.
403 match
= is_hilited_range(pos
, epos
);
407 if (p_matches
!= NULL
)
409 * Report matches, even if we're hiding highlights.
413 if (hilite_search
== 0)
415 * Not doing highlighting.
419 if (!nohide
&& hide_hilite
)
421 * Highlighting is hidden.
429 * Add a new hilite to a hilite list.
432 add_hilite(anchor
, hl
)
433 struct hilite
*anchor
;
439 * Hilites are sorted in the list; find where new one belongs.
440 * Insert new one after ihl.
442 for (ihl
= anchor
; ihl
->hl_next
!= NULL
; ihl
= ihl
->hl_next
)
444 if (ihl
->hl_next
->hl_startpos
> hl
->hl_startpos
)
449 * Truncate hilite so it doesn't overlap any existing ones
450 * above and below it.
453 hl
->hl_startpos
= MAXPOS(hl
->hl_startpos
, ihl
->hl_endpos
);
454 if (ihl
->hl_next
!= NULL
)
455 hl
->hl_endpos
= MINPOS(hl
->hl_endpos
, ihl
->hl_next
->hl_startpos
);
456 if (hl
->hl_startpos
>= hl
->hl_endpos
)
459 * Hilite was truncated out of existence.
464 hl
->hl_next
= ihl
->hl_next
;
469 * Make a hilite for each string in a physical line which matches
470 * the current pattern.
471 * sp,ep delimit the first match already found.
474 hilite_line(linepos
, line
, line_len
, chpos
, sp
, ep
, cvt_ops
)
484 char *line_end
= line
+ line_len
;
487 if (sp
== NULL
|| ep
== NULL
)
490 * sp and ep delimit the first match in the line.
491 * Mark the corresponding file positions, then
492 * look for further matches and mark them.
493 * {{ This technique, of calling match_pattern on subsequent
494 * substrings of the line, may mark more than is correct
495 * if the pattern starts with "^". This bug is fixed
496 * for those regex functions that accept a notbol parameter
497 * (currently POSIX, PCRE and V8-with-regexec2). }}
503 hl
= (struct hilite
*) ecalloc(1, sizeof(struct hilite
));
504 hl
->hl_startpos
= linepos
+ chpos
[sp
-line
];
505 hl
->hl_endpos
= linepos
+ chpos
[ep
-line
];
506 add_hilite(&hilite_anchor
, hl
);
509 * If we matched more than zero characters,
510 * move to the first char after the string we matched.
511 * If we matched zero, just move to the next char.
515 else if (searchp
!= line_end
)
517 else /* end of line */
519 } while (match_pattern(search_info
.compiled
, search_info
.text
,
520 searchp
, line_end
- searchp
, &sp
, &ep
, 1, search_info
.search_type
));
525 * Change the caseless-ness of searches.
526 * Updates the internal search state to reflect a change in the -i flag.
531 if (!is_ucase_pattern
)
533 * Pattern did not have uppercase.
534 * Just set the search caselessness to the global caselessness.
536 is_caseless
= caseless
;
539 * Pattern did have uppercase.
540 * Discard the pattern; we can't change search caselessness now.
542 clear_pattern(&search_info
);
547 * Find matching text which is currently on screen and highlight it.
552 struct scrpos scrpos
;
555 if (scrpos
.pos
== NULL_POSITION
)
557 prep_hilite(scrpos
.pos
, position(BOTTOM_PLUS_ONE
), -1);
562 * Change highlighting parameters.
568 * Erase any highlights currently on screen.
573 if (hilite_search
== OPT_ONPLUS
)
575 * Display highlights.
582 * Figure out where to start a search.
585 search_pos(search_type
)
594 * Start at the beginning (or end) of the file.
595 * The empty_screen() case is mainly for
596 * command line initiated searches;
597 * for example, "+/xyz" on the command line.
598 * Also for multi-file (SRCH_PAST_EOF) searches.
600 if (search_type
& SRCH_FORW
)
606 if (pos
== NULL_POSITION
)
608 (void) ch_end_seek();
617 * Search does not include current screen.
619 if (search_type
& SRCH_FORW
)
620 linenum
= BOTTOM_PLUS_ONE
;
623 pos
= position(linenum
);
627 * Search includes current screen.
628 * It starts at the jump target (if searching backwards),
629 * or at the jump target plus one (if forwards).
631 linenum
= adjsline(jump_sline
);
632 pos
= position(linenum
);
633 if (search_type
& SRCH_FORW
)
635 pos
= forw_raw_line(pos
, (char **)NULL
, (int *)NULL
);
636 while (pos
== NULL_POSITION
)
638 if (++linenum
>= sc_height
)
640 pos
= position(linenum
);
644 while (pos
== NULL_POSITION
)
648 pos
= position(linenum
);
656 * Search a subset of the file, specified by start/end position.
659 search_range(pos
, endpos
, search_type
, matches
, maxlines
, plinepos
, pendpos
)
677 POSITION linepos
, oldpos
;
679 linenum
= find_linenum(pos
);
684 * Get lines until we find a matching one or until
685 * we hit end-of-file (or beginning-of-file if we're
686 * going backwards), or until we hit the end position.
691 * A signal aborts the search.
696 if ((endpos
!= NULL_POSITION
&& pos
>= endpos
) || maxlines
== 0)
699 * Reached end position without a match.
708 if (search_type
& SRCH_FORW
)
711 * Read the next line, and save the
712 * starting position of that line in linepos.
715 pos
= forw_raw_line(pos
, &line
, &line_len
);
721 * Read the previous line and save the
722 * starting position of that line in linepos.
724 pos
= back_raw_line(pos
, &line
, &line_len
);
730 if (pos
== NULL_POSITION
)
733 * Reached EOF/BOF without a match.
741 * If we're using line numbers, we might as well
742 * remember the information we have now (the position
743 * and line number of the current line).
744 * Don't do it for every line because it slows down
745 * the search. Remember the line number only if
746 * we're "far" from the last place we remembered it.
748 if (linenums
&& abs((int)(pos
- oldpos
)) > 2048)
749 add_lnum(linenum
, pos
);
752 if (is_filtered(linepos
))
756 * If it's a caseless search, convert the line to lowercase.
757 * If we're doing backspace processing, delete backspaces.
759 cvt_ops
= get_cvt_ops();
760 cvt_len
= cvt_length(line_len
, cvt_ops
);
761 cline
= (char *) ecalloc(1, cvt_len
);
762 chpos
= cvt_alloc_chpos(cvt_len
);
763 cvt_text(cline
, line
, chpos
, &line_len
, cvt_ops
);
767 * Check to see if the line matches the filter pattern.
768 * If so, add an entry to the filter list.
770 if ((search_type
& SRCH_FIND_ALL
) && prev_pattern(&filter_info
)) {
771 int line_filter
= match_pattern(filter_info
.compiled
, filter_info
.text
,
772 cline
, line_len
, &sp
, &ep
, 0, filter_info
.search_type
);
775 struct hilite
*hl
= (struct hilite
*)
776 ecalloc(1, sizeof(struct hilite
));
777 hl
->hl_startpos
= linepos
;
779 add_hilite(&filter_anchor
, hl
);
785 * Test the next line to see if we have a match.
786 * We are successful if we either want a match and got one,
787 * or if we want a non-match and got one.
789 if (prev_pattern(&search_info
))
791 line_match
= match_pattern(search_info
.compiled
, search_info
.text
,
792 cline
, line_len
, &sp
, &ep
, 0, search_type
); //FIXME search_info.search_type
798 if (search_type
& SRCH_FIND_ALL
)
802 * We are supposed to find all matches in the range.
803 * Just add the matches in this line to the
804 * hilite list and keep searching.
806 hilite_line(linepos
, cline
, line_len
, chpos
, sp
, ep
, cvt_ops
);
808 } else if (--matches
<= 0)
811 * Found the one match we're looking for.
815 if (hilite_search
== OPT_ON
)
818 * Clear the hilite list and add only
819 * the matches in this one line.
822 hilite_line(linepos
, cline
, line_len
, chpos
, sp
, ep
, cvt_ops
);
827 if (plinepos
!= NULL
)
839 * search for a pattern in history. If found, compile that pattern.
842 hist_pattern(search_type
)
848 set_mlist(ml_search
, 0);
849 pattern
= cmd_lastpattern();
853 if (set_pattern(&search_info
, pattern
, search_type
) < 0)
856 is_ucase_pattern
= is_ucase(pattern
);
857 if (is_ucase_pattern
&& caseless
!= OPT_ONPLUS
)
860 is_caseless
= caseless
;
863 if (hilite_search
== OPT_ONPLUS
&& !hide_hilite
)
868 #else /* CMD_HISTORY */
870 #endif /* CMD_HISTORY */
874 * Search for the n-th occurrence of a specified pattern,
875 * either forward or backward.
876 * Return the number of matches not yet found in this file
877 * (that is, n minus the number of matches found).
878 * Return -1 if the search should be aborted.
879 * Caller may continue the search in another file
880 * if less than n matches are found in this file.
883 search(search_type
, pattern
, n
)
890 if (pattern
== NULL
|| *pattern
== '\0')
893 * A null pattern means use the previously compiled pattern.
895 if (!prev_pattern(&search_info
) && !hist_pattern(search_type
))
897 error("No previous regular expression", NULL_PARG
);
900 if ((search_type
& SRCH_NO_REGEX
) !=
901 (search_info
.search_type
& SRCH_NO_REGEX
))
903 error("Please re-enter search pattern", NULL_PARG
);
907 if (hilite_search
== OPT_ON
)
910 * Erase the highlights currently on screen.
911 * If the search fails, we'll redisplay them later.
915 if (hilite_search
== OPT_ONPLUS
&& hide_hilite
)
918 * Highlight any matches currently on screen,
919 * before we actually start the search.
929 * Compile the pattern.
931 if (set_pattern(&search_info
, pattern
, search_type
) < 0)
934 * Ignore case if -I is set OR
935 * -i is set AND the pattern is all lowercase.
937 is_ucase_pattern
= is_ucase(pattern
);
938 if (is_ucase_pattern
&& caseless
!= OPT_ONPLUS
)
941 is_caseless
= caseless
;
946 * Erase the highlights currently on screen.
947 * Also permanently delete them from the hilite list.
953 if (hilite_search
== OPT_ONPLUS
)
956 * Highlight any matches currently on screen,
957 * before we actually start the search.
965 * Figure out where to start the search.
967 pos
= search_pos(search_type
);
968 if (pos
== NULL_POSITION
)
971 * Can't find anyplace to start searching from.
973 if (search_type
& SRCH_PAST_EOF
)
975 /* repaint(); -- why was this here? */
976 error("Nothing to search", NULL_PARG
);
980 n
= search_range(pos
, NULL_POSITION
, search_type
, n
, -1,
981 &pos
, (POSITION
*)NULL
);
985 * Search was unsuccessful.
988 if (hilite_search
== OPT_ON
&& n
> 0)
990 * Redisplay old hilites.
997 if (!(search_type
& SRCH_NO_MOVE
))
1000 * Go to the matching line.
1002 jump_loc(pos
, jump_sline
);
1006 if (hilite_search
== OPT_ON
)
1008 * Display new hilites in the matching line.
1018 * Prepare hilites in a given range of the file.
1020 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1021 * of the file that has been "prepared"; that is, scanned for matches for
1022 * the current search pattern, and hilites have been created for such matches.
1023 * If prep_startpos == NULL_POSITION, the prep region is empty.
1024 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1025 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1028 prep_hilite(spos
, epos
, maxlines
)
1033 POSITION nprep_startpos
= prep_startpos
;
1034 POSITION nprep_endpos
= prep_endpos
;
1041 * Search beyond where we're asked to search, so the prep region covers
1042 * more than we need. Do one big search instead of a bunch of small ones.
1044 #define SEARCH_MORE (3*size_linebuf)
1046 if (!prev_pattern(&search_info
) && !is_filtering())
1050 * If we're limited to a max number of lines, figure out the
1051 * file position we should stop at.
1054 max_epos
= NULL_POSITION
;
1058 for (i
= 0; i
< maxlines
; i
++)
1059 max_epos
= forw_raw_line(max_epos
, (char **)NULL
, (int *)NULL
);
1064 * The range that we need to search (spos,epos); and the range that
1065 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1068 if (prep_startpos
== NULL_POSITION
||
1069 (epos
!= NULL_POSITION
&& epos
< prep_startpos
) ||
1073 * New range is not contiguous with old prep region.
1074 * Discard the old prep region and start a new one.
1078 if (epos
!= NULL_POSITION
)
1079 epos
+= SEARCH_MORE
;
1080 nprep_startpos
= spos
;
1084 * New range partially or completely overlaps old prep region.
1086 if (epos
== NULL_POSITION
)
1089 * New range goes to end of file.
1092 } else if (epos
> prep_endpos
)
1095 * New range ends after old prep region.
1096 * Extend prep region to end at end of new range.
1098 epos
+= SEARCH_MORE
;
1099 } else /* (epos <= prep_endpos) */
1102 * New range ends within old prep region.
1103 * Truncate search to end at start of old prep region.
1105 epos
= prep_startpos
;
1108 if (spos
< prep_startpos
)
1111 * New range starts before old prep region.
1112 * Extend old prep region backwards to start at
1113 * start of new range.
1115 if (spos
< SEARCH_MORE
)
1118 spos
-= SEARCH_MORE
;
1119 nprep_startpos
= spos
;
1120 } else /* (spos >= prep_startpos) */
1123 * New range starts within or after old prep region.
1124 * Trim search to start at end of old prep region.
1130 if (epos
!= NULL_POSITION
&& max_epos
!= NULL_POSITION
&&
1133 * Don't go past the max position we're allowed.
1137 if (epos
== NULL_POSITION
|| epos
> spos
)
1139 int search_type
= SRCH_FORW
| SRCH_FIND_ALL
;
1140 search_type
|= (search_info
.search_type
& SRCH_NO_REGEX
);
1141 result
= search_range(spos
, epos
, search_type
, 0,
1142 maxlines
, (POSITION
*)NULL
, &new_epos
);
1145 if (prep_endpos
== NULL_POSITION
|| new_epos
> prep_endpos
)
1146 nprep_endpos
= new_epos
;
1148 prep_startpos
= nprep_startpos
;
1149 prep_endpos
= nprep_endpos
;
1153 * Set the pattern to be used for line filtering.
1156 set_filter_pattern(pattern
, search_type
)
1161 if (pattern
== NULL
|| *pattern
== '\0')
1162 clear_pattern(&filter_info
);
1164 set_pattern(&filter_info
, pattern
, search_type
);
1169 * Is there a line filter in effect?
1174 if (ch_getflags() & CH_HELPFILE
)
1176 return prev_pattern(&filter_info
);
1182 * This function is called by the V8 regcomp to report
1183 * errors in regular expressions.