3 * Copyright (C) 1984-2011 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 * Are there any uppercase letters in this string?
82 char *str_end = str + strlen(str);
87 ch = step_char(&str, +1, str_end);
95 * Compile and save a search pattern.
98 set_pattern(info, pattern, search_type)
99 struct pattern_info *info;
104 CLEAR_PATTERN(search_info.compiled);
105 else if (compile_pattern(pattern, search_type, &info->compiled) < 0)
107 /* Pattern compiled successfully; save the text too. */
108 if (info->text != NULL)
113 info->text = (char *) ecalloc(1, strlen(pattern)+1);
114 strcpy(info->text, pattern);
116 info->search_type = search_type;
119 * Ignore case if -I is set OR
120 * -i is set AND the pattern is all lowercase.
122 is_ucase_pattern = is_ucase(pattern);
123 if (is_ucase_pattern && caseless != OPT_ONPLUS)
126 is_caseless = caseless;
131 * Discard a saved pattern.
135 struct pattern_info *info;
137 if (info->text != NULL)
140 uncompile_pattern(&info->compiled);
144 * Initialize saved pattern to nothing.
148 struct pattern_info *info;
150 CLEAR_PATTERN(info->compiled);
152 info->search_type = 0;
156 * Initialize search variables.
161 init_pattern(&search_info);
162 init_pattern(&filter_info);
166 * Determine which text conversions to perform before pattern matching.
172 if (is_caseless || bs_mode == BS_SPECIAL)
176 if (bs_mode == BS_SPECIAL)
178 if (bs_mode != BS_CONTROL)
180 } else if (bs_mode != BS_CONTROL)
184 if (ctldisp == OPT_ONPLUS)
190 * Is there a previous (remembered) search pattern?
194 struct pattern_info *info;
196 if (info->search_type & SRCH_NO_REGEX)
197 return (info->text != NULL);
198 return (!is_null_pattern(info->compiled));
203 * Repaint the hilites currently displayed on the screen.
204 * Repaint each line which contains highlighted text.
205 * If on==0, force all hilites off.
214 int save_hide_hilite;
219 save_hide_hilite = hide_hilite;
230 hide_hilite = save_hide_hilite;
234 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
236 pos = position(slinenum);
237 if (pos == NULL_POSITION)
239 epos = position(slinenum+1);
240 (void) forw_line(pos);
245 hide_hilite = save_hide_hilite;
249 * Clear the attn hilite.
255 POSITION old_start_attnpos;
256 POSITION old_end_attnpos;
261 if (start_attnpos == NULL_POSITION)
263 old_start_attnpos = start_attnpos;
264 old_end_attnpos = end_attnpos;
265 start_attnpos = end_attnpos = NULL_POSITION;
275 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
277 pos = position(slinenum);
278 if (pos == NULL_POSITION)
280 epos = position(slinenum+1);
281 if (pos < old_end_attnpos &&
282 (epos == NULL_POSITION || epos > old_start_attnpos))
284 (void) forw_line(pos);
296 * Hide search string highlighting.
301 if (!prev_pattern(&search_info))
303 error("No previous regular expression", NULL_PARG);
307 hide_hilite = !hide_hilite;
314 * Clear the hilite list.
318 struct hilite *anchor;
321 struct hilite *nexthl;
323 for (hl = anchor->hl_first; hl != NULL; hl = nexthl)
325 nexthl = hl->hl_next;
328 anchor->hl_first = NULL;
329 prep_startpos = prep_endpos = NULL_POSITION;
335 clr_hlist(&hilite_anchor);
341 clr_hlist(&filter_anchor);
345 * Should any characters in a specified range be highlighted?
348 is_hilited_range(pos, epos)
355 * Look at each highlight and see if any part of it falls in the range.
357 for (hl = hilite_anchor.hl_first; hl != NULL; hl = hl->hl_next)
359 if (hl->hl_endpos > pos &&
360 (epos == NULL_POSITION || epos > hl->hl_startpos))
367 * Is a line "filtered" -- that is, should it be hidden?
375 if (ch_getflags() & CH_HELPFILE)
379 * Look at each filter and see if the start position
380 * equals the start position of the line.
382 for (hl = filter_anchor.hl_first; hl != NULL; hl = hl->hl_next)
384 if (hl->hl_startpos == pos)
391 * Should any characters in a specified range be highlighted?
392 * If nohide is nonzero, don't consider hide_hilite.
395 is_hilited(pos, epos, nohide, p_matches)
403 if (p_matches != NULL)
407 start_attnpos != NULL_POSITION &&
409 (epos == NULL_POSITION || epos > start_attnpos))
411 * The attn line overlaps this range.
415 match = is_hilited_range(pos, epos);
419 if (p_matches != NULL)
421 * Report matches, even if we're hiding highlights.
425 if (hilite_search == 0)
427 * Not doing highlighting.
431 if (!nohide && hide_hilite)
433 * Highlighting is hidden.
441 * Add a new hilite to a hilite list.
444 add_hilite(anchor, hl)
445 struct hilite *anchor;
451 * Hilites are sorted in the list; find where new one belongs.
452 * Insert new one after ihl.
454 for (ihl = anchor; ihl->hl_next != NULL; ihl = ihl->hl_next)
456 if (ihl->hl_next->hl_startpos > hl->hl_startpos)
461 * Truncate hilite so it doesn't overlap any existing ones
462 * above and below it.
465 hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
466 if (ihl->hl_next != NULL)
467 hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
468 if (hl->hl_startpos >= hl->hl_endpos)
471 * Hilite was truncated out of existence.
476 hl->hl_next = ihl->hl_next;
481 * Make a hilite for each string in a physical line which matches
482 * the current pattern.
483 * sp,ep delimit the first match already found.
486 hilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops)
496 char *line_end = line + line_len;
499 if (sp == NULL || ep == NULL)
502 * sp and ep delimit the first match in the line.
503 * Mark the corresponding file positions, then
504 * look for further matches and mark them.
505 * {{ This technique, of calling match_pattern on subsequent
506 * substrings of the line, may mark more than is correct
507 * if the pattern starts with "^". This bug is fixed
508 * for those regex functions that accept a notbol parameter
509 * (currently POSIX, PCRE and V8-with-regexec2). }}
515 hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
516 hl->hl_startpos = linepos + chpos[sp-line];
517 hl->hl_endpos = linepos + chpos[ep-line];
518 add_hilite(&hilite_anchor, hl);
521 * If we matched more than zero characters,
522 * move to the first char after the string we matched.
523 * If we matched zero, just move to the next char.
527 else if (searchp != line_end)
529 else /* end of line */
531 } while (match_pattern(search_info.compiled, search_info.text,
532 searchp, line_end - searchp, &sp, &ep, 1, search_info.search_type));
537 * Change the caseless-ness of searches.
538 * Updates the internal search state to reflect a change in the -i flag.
543 if (!is_ucase_pattern)
545 * Pattern did not have uppercase.
546 * Just set the search caselessness to the global caselessness.
548 is_caseless = caseless;
551 * Pattern did have uppercase.
552 * Discard the pattern; we can't change search caselessness now.
554 clear_pattern(&search_info);
559 * Find matching text which is currently on screen and highlight it.
564 struct scrpos scrpos;
567 if (scrpos.pos == NULL_POSITION)
569 prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
574 * Change highlighting parameters.
580 * Erase any highlights currently on screen.
585 if (hilite_search == OPT_ONPLUS)
587 * Display highlights.
594 * Figure out where to start a search.
597 search_pos(search_type)
606 * Start at the beginning (or end) of the file.
607 * The empty_screen() case is mainly for
608 * command line initiated searches;
609 * for example, "+/xyz" on the command line.
610 * Also for multi-file (SRCH_PAST_EOF) searches.
612 if (search_type & SRCH_FORW)
618 if (pos == NULL_POSITION)
620 (void) ch_end_seek();
629 if (how_search == OPT_ON)
632 * Search does not include current screen.
634 if (search_type & SRCH_FORW)
635 linenum = BOTTOM_PLUS_ONE;
638 } else if (how_search == OPT_ONPLUS && !(search_type & SRCH_AFTER_TARGET))
641 * Search includes all of displayed screen.
643 if (search_type & SRCH_FORW)
646 linenum = BOTTOM_PLUS_ONE;
650 * Search includes the part of current screen beyond the jump target.
651 * It starts at the jump target (if searching backwards),
652 * or at the jump target plus one (if forwards).
654 linenum = jump_sline;
655 if (search_type & SRCH_FORW)
658 linenum = adjsline(linenum);
659 pos = position(linenum);
661 pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
665 * If the line is empty, look around for a plausible starting place.
667 if (search_type & SRCH_FORW)
669 while (pos == NULL_POSITION)
671 if (++linenum >= sc_height)
673 pos = position(linenum);
677 while (pos == NULL_POSITION)
681 pos = position(linenum);
688 * Search a subset of the file, specified by start/end position.
691 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
709 POSITION linepos, oldpos;
711 linenum = find_linenum(pos);
716 * Get lines until we find a matching one or until
717 * we hit end-of-file (or beginning-of-file if we're
718 * going backwards), or until we hit the end position.
723 * A signal aborts the search.
728 if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
731 * Reached end position without a match.
740 if (search_type & SRCH_FORW)
743 * Read the next line, and save the
744 * starting position of that line in linepos.
747 pos = forw_raw_line(pos, &line, &line_len);
753 * Read the previous line and save the
754 * starting position of that line in linepos.
756 pos = back_raw_line(pos, &line, &line_len);
762 if (pos == NULL_POSITION)
765 * Reached EOF/BOF without a match.
773 * If we're using line numbers, we might as well
774 * remember the information we have now (the position
775 * and line number of the current line).
776 * Don't do it for every line because it slows down
777 * the search. Remember the line number only if
778 * we're "far" from the last place we remembered it.
780 if (linenums && abs((int)(pos - oldpos)) > 2048)
781 add_lnum(linenum, pos);
784 if (is_filtered(linepos))
788 * If it's a caseless search, convert the line to lowercase.
789 * If we're doing backspace processing, delete backspaces.
791 cvt_ops = get_cvt_ops();
792 cvt_len = cvt_length(line_len, cvt_ops);
793 cline = (char *) ecalloc(1, cvt_len);
794 chpos = cvt_alloc_chpos(cvt_len);
795 cvt_text(cline, line, chpos, &line_len, cvt_ops);
799 * Check to see if the line matches the filter pattern.
800 * If so, add an entry to the filter list.
802 if ((search_type & SRCH_FIND_ALL) && prev_pattern(&filter_info)) {
803 int line_filter = match_pattern(filter_info.compiled, filter_info.text,
804 cline, line_len, &sp, &ep, 0, filter_info.search_type);
807 struct hilite *hl = (struct hilite *)
808 ecalloc(1, sizeof(struct hilite));
809 hl->hl_startpos = linepos;
811 add_hilite(&filter_anchor, hl);
817 * Test the next line to see if we have a match.
818 * We are successful if we either want a match and got one,
819 * or if we want a non-match and got one.
821 if (prev_pattern(&search_info))
823 line_match = match_pattern(search_info.compiled, search_info.text,
824 cline, line_len, &sp, &ep, 0, search_type);
830 if (search_type & SRCH_FIND_ALL)
834 * We are supposed to find all matches in the range.
835 * Just add the matches in this line to the
836 * hilite list and keep searching.
838 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops);
840 } else if (--matches <= 0)
843 * Found the one match we're looking for.
847 if (hilite_search == OPT_ON)
850 * Clear the hilite list and add only
851 * the matches in this one line.
854 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops);
859 if (plinepos != NULL)
871 * search for a pattern in history. If found, compile that pattern.
874 hist_pattern(search_type)
880 set_mlist(ml_search, 0);
881 pattern = cmd_lastpattern();
885 if (set_pattern(&search_info, pattern, search_type) < 0)
889 if (hilite_search == OPT_ONPLUS && !hide_hilite)
894 #else /* CMD_HISTORY */
896 #endif /* CMD_HISTORY */
900 * Search for the n-th occurrence of a specified pattern,
901 * either forward or backward.
902 * Return the number of matches not yet found in this file
903 * (that is, n minus the number of matches found).
904 * Return -1 if the search should be aborted.
905 * Caller may continue the search in another file
906 * if less than n matches are found in this file.
909 search(search_type, pattern, n)
916 if (pattern == NULL || *pattern == '\0')
919 * A null pattern means use the previously compiled pattern.
921 search_type |= SRCH_AFTER_TARGET;
922 if (!prev_pattern(&search_info) && !hist_pattern(search_type))
924 error("No previous regular expression", NULL_PARG);
927 if ((search_type & SRCH_NO_REGEX) !=
928 (search_info.search_type & SRCH_NO_REGEX))
930 error("Please re-enter search pattern", NULL_PARG);
934 if (hilite_search == OPT_ON)
937 * Erase the highlights currently on screen.
938 * If the search fails, we'll redisplay them later.
942 if (hilite_search == OPT_ONPLUS && hide_hilite)
945 * Highlight any matches currently on screen,
946 * before we actually start the search.
956 * Compile the pattern.
958 if (set_pattern(&search_info, pattern, search_type) < 0)
964 * Erase the highlights currently on screen.
965 * Also permanently delete them from the hilite list.
971 if (hilite_search == OPT_ONPLUS)
974 * Highlight any matches currently on screen,
975 * before we actually start the search.
983 * Figure out where to start the search.
985 pos = search_pos(search_type);
986 if (pos == NULL_POSITION)
989 * Can't find anyplace to start searching from.
991 if (search_type & SRCH_PAST_EOF)
993 /* repaint(); -- why was this here? */
994 error("Nothing to search", NULL_PARG);
998 n = search_range(pos, NULL_POSITION, search_type, n, -1,
999 &pos, (POSITION*)NULL);
1003 * Search was unsuccessful.
1006 if (hilite_search == OPT_ON && n > 0)
1008 * Redisplay old hilites.
1015 if (!(search_type & SRCH_NO_MOVE))
1018 * Go to the matching line.
1020 jump_loc(pos, jump_sline);
1024 if (hilite_search == OPT_ON)
1026 * Display new hilites in the matching line.
1036 * Prepare hilites in a given range of the file.
1038 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1039 * of the file that has been "prepared"; that is, scanned for matches for
1040 * the current search pattern, and hilites have been created for such matches.
1041 * If prep_startpos == NULL_POSITION, the prep region is empty.
1042 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1043 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1046 prep_hilite(spos, epos, maxlines)
1051 POSITION nprep_startpos = prep_startpos;
1052 POSITION nprep_endpos = prep_endpos;
1059 * Search beyond where we're asked to search, so the prep region covers
1060 * more than we need. Do one big search instead of a bunch of small ones.
1062 #define SEARCH_MORE (3*size_linebuf)
1064 if (!prev_pattern(&search_info) && !is_filtering())
1068 * If we're limited to a max number of lines, figure out the
1069 * file position we should stop at.
1072 max_epos = NULL_POSITION;
1076 for (i = 0; i < maxlines; i++)
1077 max_epos = forw_raw_line(max_epos, (char **)NULL, (int *)NULL);
1082 * The range that we need to search (spos,epos); and the range that
1083 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1086 if (prep_startpos == NULL_POSITION ||
1087 (epos != NULL_POSITION && epos < prep_startpos) ||
1091 * New range is not contiguous with old prep region.
1092 * Discard the old prep region and start a new one.
1096 if (epos != NULL_POSITION)
1097 epos += SEARCH_MORE;
1098 nprep_startpos = spos;
1102 * New range partially or completely overlaps old prep region.
1104 if (epos == NULL_POSITION)
1107 * New range goes to end of file.
1110 } else if (epos > prep_endpos)
1113 * New range ends after old prep region.
1114 * Extend prep region to end at end of new range.
1116 epos += SEARCH_MORE;
1117 } else /* (epos <= prep_endpos) */
1120 * New range ends within old prep region.
1121 * Truncate search to end at start of old prep region.
1123 epos = prep_startpos;
1126 if (spos < prep_startpos)
1129 * New range starts before old prep region.
1130 * Extend old prep region backwards to start at
1131 * start of new range.
1133 if (spos < SEARCH_MORE)
1136 spos -= SEARCH_MORE;
1137 nprep_startpos = spos;
1138 } else /* (spos >= prep_startpos) */
1141 * New range starts within or after old prep region.
1142 * Trim search to start at end of old prep region.
1148 if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1151 * Don't go past the max position we're allowed.
1155 if (epos == NULL_POSITION || epos > spos)
1157 int search_type = SRCH_FORW | SRCH_FIND_ALL;
1158 search_type |= (search_info.search_type & SRCH_NO_REGEX);
1159 result = search_range(spos, epos, search_type, 0,
1160 maxlines, (POSITION*)NULL, &new_epos);
1163 if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1164 nprep_endpos = new_epos;
1166 prep_startpos = nprep_startpos;
1167 prep_endpos = nprep_endpos;
1171 * Set the pattern to be used for line filtering.
1174 set_filter_pattern(pattern, search_type)
1179 if (pattern == NULL || *pattern == '\0')
1180 clear_pattern(&filter_info);
1182 set_pattern(&filter_info, pattern, search_type);
1187 * Is there a line filter in effect?
1192 if (ch_getflags() & CH_HELPFILE)
1194 return prev_pattern(&filter_info);
1200 * This function is called by the V8 regcomp to report
1201 * errors in regular expressions.