3 * Copyright (C) 1984-2009 Mark Nudelman
5 * You may distribute under the terms of either the GNU General Public
6 * License or the Less License, as specified in the README file.
8 * For more information about less, or for information on how to
9 * contact the author, see the README file.
14 * Routines to search a file for a pattern.
22 #define MINPOS(a,b) (((a) < (b)) ? (a) : (b))
23 #define MAXPOS(a,b) (((a) > (b)) ? (a) : (b))
26 extern int how_search;
30 extern int jump_sline;
32 extern int less_is_more;
34 extern int status_col;
35 extern void * constant ml_search;
36 extern POSITION start_attnpos;
37 extern POSITION end_attnpos;
39 extern int screen_trashed;
41 extern int hilite_search;
42 extern int size_linebuf;
44 extern int can_goto_line;
45 static int hide_hilite;
46 static POSITION prep_startpos;
47 static POSITION prep_endpos;
48 static int is_caseless;
49 static int is_ucase_pattern;
53 struct hilite *hl_next;
57 static struct hilite hilite_anchor = { NULL, NULL_POSITION, NULL_POSITION };
58 static struct hilite filter_anchor = { NULL, NULL_POSITION, NULL_POSITION };
59 #define hl_first hl_next
63 * These are the static variables that represent the "remembered"
64 * search pattern and filter pattern.
67 DEFINE_PATTERN(compiled);
72 static struct pattern_info search_info;
73 static struct pattern_info filter_info;
76 * Compile and save a search pattern.
79 set_pattern(info, pattern, search_type)
80 struct pattern_info *info;
85 CLEAR_PATTERN(search_info.compiled);
86 else if (compile_pattern(pattern, search_type, &info->compiled) < 0)
88 /* Pattern compiled successfully; save the text too. */
89 if (info->text != NULL)
94 info->text = (char *) ecalloc(1, strlen(pattern)+1);
95 strcpy(info->text, pattern);
97 info->search_type = search_type;
102 * Discard a saved pattern.
106 struct pattern_info *info;
108 if (info->text != NULL)
111 uncompile_pattern(&info->compiled);
115 * Initialize saved pattern to nothing.
119 struct pattern_info *info;
121 CLEAR_PATTERN(info->compiled);
123 info->search_type = 0;
127 * Initialize search variables.
132 init_pattern(&search_info);
133 init_pattern(&filter_info);
137 * Determine which text conversions to perform before pattern matching.
143 if (is_caseless || bs_mode == BS_SPECIAL)
147 if (bs_mode == BS_SPECIAL)
149 if (bs_mode != BS_CONTROL)
151 } else if (bs_mode != BS_CONTROL)
155 if (ctldisp == OPT_ONPLUS)
161 * Are there any uppercase letters in this string?
167 char *str_end = str + strlen(str);
170 while (str < str_end)
172 ch = step_char(&str, +1, str_end);
180 * Is there a previous (remembered) search pattern?
184 struct pattern_info *info;
186 if (info->search_type & SRCH_NO_REGEX)
187 return (info->text != NULL);
188 return (!is_null_pattern(info->compiled));
193 * Repaint the hilites currently displayed on the screen.
194 * Repaint each line which contains highlighted text.
195 * If on==0, force all hilites off.
204 int save_hide_hilite;
209 save_hide_hilite = hide_hilite;
220 hide_hilite = save_hide_hilite;
224 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
226 pos = position(slinenum);
227 if (pos == NULL_POSITION)
229 epos = position(slinenum+1);
230 (void) forw_line(pos);
234 lower_left(); // if !oldbot
235 hide_hilite = save_hide_hilite;
239 * Clear the attn hilite.
245 POSITION old_start_attnpos;
246 POSITION old_end_attnpos;
251 if (start_attnpos == NULL_POSITION)
253 old_start_attnpos = start_attnpos;
254 old_end_attnpos = end_attnpos;
255 start_attnpos = end_attnpos = NULL_POSITION;
265 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
267 pos = position(slinenum);
268 if (pos == NULL_POSITION)
270 epos = position(slinenum+1);
271 if (pos < old_end_attnpos &&
272 (epos == NULL_POSITION || epos > old_start_attnpos))
274 (void) forw_line(pos);
286 * Hide search string highlighting.
291 if (!prev_pattern(&search_info))
293 error("No previous regular expression", NULL_PARG);
297 hide_hilite = !hide_hilite;
304 * Clear the hilite list.
308 struct hilite *anchor;
311 struct hilite *nexthl;
313 for (hl = anchor->hl_first; hl != NULL; hl = nexthl)
315 nexthl = hl->hl_next;
318 anchor->hl_first = NULL;
319 prep_startpos = prep_endpos = NULL_POSITION;
325 clr_hlist(&hilite_anchor);
331 clr_hlist(&filter_anchor);
335 * Should any characters in a specified range be highlighted?
338 is_hilited_range(pos, epos)
345 * Look at each highlight and see if any part of it falls in the range.
347 for (hl = hilite_anchor.hl_first; hl != NULL; hl = hl->hl_next)
349 if (hl->hl_endpos > pos &&
350 (epos == NULL_POSITION || epos > hl->hl_startpos))
357 * Is a line "filtered" -- that is, should it be hidden?
365 if (ch_getflags() & CH_HELPFILE)
369 * Look at each filter and see if the start position
370 * equals the start position of the line.
372 for (hl = filter_anchor.hl_first; hl != NULL; hl = hl->hl_next)
374 if (hl->hl_startpos == pos)
381 * Should any characters in a specified range be highlighted?
382 * If nohide is nonzero, don't consider hide_hilite.
385 is_hilited(pos, epos, nohide, p_matches)
393 if (p_matches != NULL)
397 start_attnpos != NULL_POSITION &&
399 (epos == NULL_POSITION || epos > start_attnpos))
401 * The attn line overlaps this range.
405 match = is_hilited_range(pos, epos);
409 if (p_matches != NULL)
411 * Report matches, even if we're hiding highlights.
415 if (hilite_search == 0)
417 * Not doing highlighting.
421 if (!nohide && hide_hilite)
423 * Highlighting is hidden.
431 * Add a new hilite to a hilite list.
434 add_hilite(anchor, hl)
435 struct hilite *anchor;
441 * Hilites are sorted in the list; find where new one belongs.
442 * Insert new one after ihl.
444 for (ihl = anchor; ihl->hl_next != NULL; ihl = ihl->hl_next)
446 if (ihl->hl_next->hl_startpos > hl->hl_startpos)
451 * Truncate hilite so it doesn't overlap any existing ones
452 * above and below it.
455 hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
456 if (ihl->hl_next != NULL)
457 hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
458 if (hl->hl_startpos >= hl->hl_endpos)
461 * Hilite was truncated out of existence.
466 hl->hl_next = ihl->hl_next;
471 * Make a hilite for each string in a physical line which matches
472 * the current pattern.
473 * sp,ep delimit the first match already found.
476 hilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops)
486 char *line_end = line + line_len;
489 if (sp == NULL || ep == NULL)
492 * sp and ep delimit the first match in the line.
493 * Mark the corresponding file positions, then
494 * look for further matches and mark them.
495 * {{ This technique, of calling match_pattern on subsequent
496 * substrings of the line, may mark more than is correct
497 * if the pattern starts with "^". This bug is fixed
498 * for those regex functions that accept a notbol parameter
499 * (currently POSIX, PCRE and V8-with-regexec2). }}
505 hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
506 hl->hl_startpos = linepos + chpos[sp-line];
507 hl->hl_endpos = linepos + chpos[ep-line];
508 add_hilite(&hilite_anchor, hl);
511 * If we matched more than zero characters,
512 * move to the first char after the string we matched.
513 * If we matched zero, just move to the next char.
517 else if (searchp != line_end)
519 else /* end of line */
521 } while (match_pattern(search_info.compiled, search_info.text,
522 searchp, line_end - searchp, &sp, &ep, 1, search_info.search_type));
527 * Change the caseless-ness of searches.
528 * Updates the internal search state to reflect a change in the -i flag.
533 if (!is_ucase_pattern)
535 * Pattern did not have uppercase.
536 * Just set the search caselessness to the global caselessness.
538 is_caseless = caseless;
541 * Pattern did have uppercase.
542 * Discard the pattern; we can't change search caselessness now.
544 clear_pattern(&search_info);
549 * Find matching text which is currently on screen and highlight it.
554 struct scrpos scrpos;
557 if (scrpos.pos == NULL_POSITION)
559 prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
564 * Change highlighting parameters.
570 * Erase any highlights currently on screen.
575 if (hilite_search == OPT_ONPLUS)
577 * Display highlights.
584 * Figure out where to start a search.
587 search_pos(search_type)
596 * Start at the beginning (or end) of the file.
597 * The empty_screen() case is mainly for
598 * command line initiated searches;
599 * for example, "+/xyz" on the command line.
600 * Also for multi-file (SRCH_PAST_EOF) searches.
602 if (search_type & SRCH_FORW)
608 if (pos == NULL_POSITION)
610 (void) ch_end_seek();
619 * Search does not include current screen.
621 if (search_type & SRCH_FORW)
622 linenum = BOTTOM_PLUS_ONE;
625 pos = position(linenum);
629 * Search includes current screen.
630 * It starts at the jump target (if searching backwards),
631 * or at the jump target plus one (if forwards).
633 linenum = adjsline(jump_sline);
634 pos = position(linenum);
635 if (search_type & SRCH_FORW)
637 pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
638 while (pos == NULL_POSITION)
640 if (++linenum >= sc_height)
642 pos = position(linenum);
646 while (pos == NULL_POSITION)
650 pos = position(linenum);
658 * Search a subset of the file, specified by start/end position.
661 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
679 POSITION linepos, oldpos;
681 linenum = find_linenum(pos);
686 * Get lines until we find a matching one or until
687 * we hit end-of-file (or beginning-of-file if we're
688 * going backwards), or until we hit the end position.
693 * A signal aborts the search.
698 if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
701 * Reached end position without a match.
710 if (search_type & SRCH_FORW)
713 * Read the next line, and save the
714 * starting position of that line in linepos.
717 pos = forw_raw_line(pos, &line, &line_len);
723 * Read the previous line and save the
724 * starting position of that line in linepos.
726 pos = back_raw_line(pos, &line, &line_len);
732 if (pos == NULL_POSITION)
735 * Reached EOF/BOF without a match.
743 * If we're using line numbers, we might as well
744 * remember the information we have now (the position
745 * and line number of the current line).
746 * Don't do it for every line because it slows down
747 * the search. Remember the line number only if
748 * we're "far" from the last place we remembered it.
750 if (linenums && abs((int)(pos - oldpos)) > 2048)
751 add_lnum(linenum, pos);
754 if (is_filtered(linepos))
758 * If it's a caseless search, convert the line to lowercase.
759 * If we're doing backspace processing, delete backspaces.
761 cvt_ops = get_cvt_ops();
762 cvt_len = cvt_length(line_len, cvt_ops);
763 cline = (char *) ecalloc(1, cvt_len);
764 chpos = cvt_alloc_chpos(cvt_len);
765 cvt_text(cline, line, chpos, &line_len, cvt_ops);
769 * Check to see if the line matches the filter pattern.
770 * If so, add an entry to the filter list.
772 if ((search_type & SRCH_FIND_ALL) && prev_pattern(&filter_info)) {
773 int line_filter = match_pattern(filter_info.compiled, filter_info.text,
774 cline, line_len, &sp, &ep, 0, filter_info.search_type);
777 struct hilite *hl = (struct hilite *)
778 ecalloc(1, sizeof(struct hilite));
779 hl->hl_startpos = linepos;
781 add_hilite(&filter_anchor, hl);
787 * Test the next line to see if we have a match.
788 * We are successful if we either want a match and got one,
789 * or if we want a non-match and got one.
791 if (prev_pattern(&search_info))
793 line_match = match_pattern(search_info.compiled, search_info.text,
794 cline, line_len, &sp, &ep, 0, search_type); //FIXME search_info.search_type
800 if (search_type & SRCH_FIND_ALL)
804 * We are supposed to find all matches in the range.
805 * Just add the matches in this line to the
806 * hilite list and keep searching.
808 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops);
810 } else if (--matches <= 0)
813 * Found the one match we're looking for.
817 if (hilite_search == OPT_ON)
820 * Clear the hilite list and add only
821 * the matches in this one line.
824 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops);
829 if (plinepos != NULL)
841 * search for a pattern in history. If found, compile that pattern.
844 hist_pattern(search_type)
850 set_mlist(ml_search, 0);
851 pattern = cmd_lastpattern();
855 if (set_pattern(&search_info, pattern, search_type) < 0)
858 is_ucase_pattern = is_ucase(pattern);
859 if (is_ucase_pattern && caseless != OPT_ONPLUS)
862 is_caseless = caseless;
865 if (hilite_search == OPT_ONPLUS && !hide_hilite)
870 #else /* CMD_HISTORY */
872 #endif /* CMD_HISTORY */
876 * Search for the n-th occurrence of a specified pattern,
877 * either forward or backward.
878 * Return the number of matches not yet found in this file
879 * (that is, n minus the number of matches found).
880 * Return -1 if the search should be aborted.
881 * Caller may continue the search in another file
882 * if less than n matches are found in this file.
885 search(search_type, pattern, n)
892 if (pattern == NULL || *pattern == '\0')
895 * A null pattern means use the previously compiled pattern.
897 if (!prev_pattern(&search_info) && !hist_pattern(search_type))
899 error("No previous regular expression", NULL_PARG);
902 if ((search_type & SRCH_NO_REGEX) !=
903 (search_info.search_type & SRCH_NO_REGEX))
905 error("Please re-enter search pattern", NULL_PARG);
909 if (hilite_search == OPT_ON)
912 * Erase the highlights currently on screen.
913 * If the search fails, we'll redisplay them later.
917 if (hilite_search == OPT_ONPLUS && hide_hilite)
920 * Highlight any matches currently on screen,
921 * before we actually start the search.
931 * Compile the pattern.
933 if (set_pattern(&search_info, pattern, search_type) < 0)
936 * Ignore case if -I is set OR
937 * -i is set AND the pattern is all lowercase.
939 is_ucase_pattern = is_ucase(pattern);
940 if (is_ucase_pattern && caseless != OPT_ONPLUS)
943 is_caseless = caseless;
948 * Erase the highlights currently on screen.
949 * Also permanently delete them from the hilite list.
955 if (hilite_search == OPT_ONPLUS)
958 * Highlight any matches currently on screen,
959 * before we actually start the search.
967 * Figure out where to start the search.
969 pos = search_pos(search_type);
970 if (pos == NULL_POSITION)
973 * Can't find anyplace to start searching from.
975 if (search_type & SRCH_PAST_EOF)
977 /* repaint(); -- why was this here? */
978 error("Nothing to search", NULL_PARG);
982 n = search_range(pos, NULL_POSITION, search_type, n, -1,
983 &pos, (POSITION*)NULL);
987 * Search was unsuccessful.
990 if (hilite_search == OPT_ON && n > 0)
992 * Redisplay old hilites.
999 if (!(search_type & SRCH_NO_MOVE))
1002 * Go to the matching line.
1004 jump_loc(pos, jump_sline);
1008 if (hilite_search == OPT_ON)
1010 * Display new hilites in the matching line.
1020 * Prepare hilites in a given range of the file.
1022 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1023 * of the file that has been "prepared"; that is, scanned for matches for
1024 * the current search pattern, and hilites have been created for such matches.
1025 * If prep_startpos == NULL_POSITION, the prep region is empty.
1026 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1027 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1030 prep_hilite(spos, epos, maxlines)
1035 POSITION nprep_startpos = prep_startpos;
1036 POSITION nprep_endpos = prep_endpos;
1043 * Search beyond where we're asked to search, so the prep region covers
1044 * more than we need. Do one big search instead of a bunch of small ones.
1046 #define SEARCH_MORE (3*size_linebuf)
1048 if (!prev_pattern(&search_info) && !is_filtering())
1052 * If we're limited to a max number of lines, figure out the
1053 * file position we should stop at.
1056 max_epos = NULL_POSITION;
1060 for (i = 0; i < maxlines; i++)
1061 max_epos = forw_raw_line(max_epos, (char **)NULL, (int *)NULL);
1066 * The range that we need to search (spos,epos); and the range that
1067 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1070 if (prep_startpos == NULL_POSITION ||
1071 (epos != NULL_POSITION && epos < prep_startpos) ||
1075 * New range is not contiguous with old prep region.
1076 * Discard the old prep region and start a new one.
1080 if (epos != NULL_POSITION)
1081 epos += SEARCH_MORE;
1082 nprep_startpos = spos;
1086 * New range partially or completely overlaps old prep region.
1088 if (epos == NULL_POSITION)
1091 * New range goes to end of file.
1094 } else if (epos > prep_endpos)
1097 * New range ends after old prep region.
1098 * Extend prep region to end at end of new range.
1100 epos += SEARCH_MORE;
1101 } else /* (epos <= prep_endpos) */
1104 * New range ends within old prep region.
1105 * Truncate search to end at start of old prep region.
1107 epos = prep_startpos;
1110 if (spos < prep_startpos)
1113 * New range starts before old prep region.
1114 * Extend old prep region backwards to start at
1115 * start of new range.
1117 if (spos < SEARCH_MORE)
1120 spos -= SEARCH_MORE;
1121 nprep_startpos = spos;
1122 } else /* (spos >= prep_startpos) */
1125 * New range starts within or after old prep region.
1126 * Trim search to start at end of old prep region.
1132 if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1135 * Don't go past the max position we're allowed.
1139 if (epos == NULL_POSITION || epos > spos)
1141 int search_type = SRCH_FORW | SRCH_FIND_ALL;
1142 search_type |= (search_info.search_type & SRCH_NO_REGEX);
1143 result = search_range(spos, epos, search_type, 0,
1144 maxlines, (POSITION*)NULL, &new_epos);
1147 if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1148 nprep_endpos = new_epos;
1150 prep_startpos = nprep_startpos;
1151 prep_endpos = nprep_endpos;
1155 * Set the pattern to be used for line filtering.
1158 set_filter_pattern(pattern, search_type)
1163 if (pattern == NULL || *pattern == '\0')
1164 clear_pattern(&filter_info);
1166 set_pattern(&filter_info, pattern, search_type);
1171 * Is there a line filter in effect?
1176 if (ch_getflags() & CH_HELPFILE)
1178 return prev_pattern(&filter_info);
1184 * This function is called by the V8 regcomp to report
1185 * errors in regular expressions.