2 * Copyright (C) 1984-2012 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, see the README file.
12 * Routines to search a file for a pattern.
20 #define MINPOS(a,b) (((a) < (b)) ? (a) : (b))
21 #define MAXPOS(a,b) (((a) > (b)) ? (a) : (b))
24 extern int how_search;
28 extern int jump_sline;
31 extern int status_col;
32 extern void * constant ml_search;
33 extern POSITION start_attnpos;
34 extern POSITION end_attnpos;
36 extern int screen_trashed;
38 extern int hilite_search;
39 extern int size_linebuf;
41 extern int can_goto_line;
42 static int hide_hilite;
43 static POSITION prep_startpos;
44 static POSITION prep_endpos;
45 static int is_caseless;
46 static int is_ucase_pattern;
50 struct hilite *hl_next;
54 static struct hilite hilite_anchor = { NULL, NULL_POSITION, NULL_POSITION };
55 static struct hilite filter_anchor = { NULL, NULL_POSITION, NULL_POSITION };
56 #define hl_first hl_next
60 * These are the static variables that represent the "remembered"
61 * search pattern and filter pattern.
64 DEFINE_PATTERN(compiled);
70 #define info_compiled(info) ((void*)0)
72 #define info_compiled(info) ((info)->compiled)
75 static struct pattern_info search_info;
76 static struct pattern_info filter_info;
79 * Are there any uppercase letters in this string?
85 char *str_end = str + strlen(str);
90 ch = step_char(&str, +1, str_end);
98 * Compile and save a search pattern.
101 set_pattern(info, pattern, search_type)
102 struct pattern_info *info;
108 CLEAR_PATTERN(info->compiled);
109 else if (compile_pattern(pattern, search_type, &info->compiled) < 0)
112 /* Pattern compiled successfully; save the text too. */
113 if (info->text != NULL)
118 info->text = (char *) ecalloc(1, strlen(pattern)+1);
119 strcpy(info->text, pattern);
121 info->search_type = search_type;
124 * Ignore case if -I is set OR
125 * -i is set AND the pattern is all lowercase.
127 is_ucase_pattern = is_ucase(pattern);
128 if (is_ucase_pattern && caseless != OPT_ONPLUS)
131 is_caseless = caseless;
136 * Discard a saved pattern.
140 struct pattern_info *info;
142 if (info->text != NULL)
146 uncompile_pattern(&info->compiled);
151 * Initialize saved pattern to nothing.
155 struct pattern_info *info;
157 CLEAR_PATTERN(info->compiled);
159 info->search_type = 0;
163 * Initialize search variables.
168 init_pattern(&search_info);
169 init_pattern(&filter_info);
173 * Determine which text conversions to perform before pattern matching.
179 if (is_caseless || bs_mode == BS_SPECIAL)
183 if (bs_mode == BS_SPECIAL)
185 if (bs_mode != BS_CONTROL)
187 } else if (bs_mode != BS_CONTROL)
191 if (ctldisp == OPT_ONPLUS)
197 * Is there a previous (remembered) search pattern?
201 struct pattern_info *info;
204 if ((info->search_type & SRCH_NO_REGEX) == 0)
205 return (!is_null_pattern(info->compiled));
207 return (info->text != NULL);
212 * Repaint the hilites currently displayed on the screen.
213 * Repaint each line which contains highlighted text.
214 * If on==0, force all hilites off.
223 int save_hide_hilite;
228 save_hide_hilite = hide_hilite;
239 hide_hilite = save_hide_hilite;
243 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
245 pos = position(slinenum);
246 if (pos == NULL_POSITION)
248 epos = position(slinenum+1);
249 (void) forw_line(pos);
254 hide_hilite = save_hide_hilite;
258 * Clear the attn hilite.
264 POSITION old_start_attnpos;
265 POSITION old_end_attnpos;
270 if (start_attnpos == NULL_POSITION)
272 old_start_attnpos = start_attnpos;
273 old_end_attnpos = end_attnpos;
274 start_attnpos = end_attnpos = NULL_POSITION;
284 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
286 pos = position(slinenum);
287 if (pos == NULL_POSITION)
289 epos = position(slinenum+1);
290 if (pos < old_end_attnpos &&
291 (epos == NULL_POSITION || epos > old_start_attnpos))
293 (void) forw_line(pos);
305 * Hide search string highlighting.
310 if (!prev_pattern(&search_info))
312 error("No previous regular expression", NULL_PARG);
316 hide_hilite = !hide_hilite;
323 * Clear the hilite list.
327 struct hilite *anchor;
330 struct hilite *nexthl;
332 for (hl = anchor->hl_first; hl != NULL; hl = nexthl)
334 nexthl = hl->hl_next;
337 anchor->hl_first = NULL;
338 prep_startpos = prep_endpos = NULL_POSITION;
344 clr_hlist(&hilite_anchor);
350 clr_hlist(&filter_anchor);
354 * Should any characters in a specified range be highlighted?
357 is_hilited_range(pos, epos)
364 * Look at each highlight and see if any part of it falls in the range.
366 for (hl = hilite_anchor.hl_first; hl != NULL; hl = hl->hl_next)
368 if (hl->hl_endpos > pos &&
369 (epos == NULL_POSITION || epos > hl->hl_startpos))
376 * Is a line "filtered" -- that is, should it be hidden?
384 if (ch_getflags() & CH_HELPFILE)
388 * Look at each filter and see if the start position
389 * equals the start position of the line.
391 for (hl = filter_anchor.hl_first; hl != NULL; hl = hl->hl_next)
393 if (hl->hl_startpos == pos)
400 * Should any characters in a specified range be highlighted?
401 * If nohide is nonzero, don't consider hide_hilite.
404 is_hilited(pos, epos, nohide, p_matches)
412 if (p_matches != NULL)
416 start_attnpos != NULL_POSITION &&
418 (epos == NULL_POSITION || epos > start_attnpos))
420 * The attn line overlaps this range.
424 match = is_hilited_range(pos, epos);
428 if (p_matches != NULL)
430 * Report matches, even if we're hiding highlights.
434 if (hilite_search == 0)
436 * Not doing highlighting.
440 if (!nohide && hide_hilite)
442 * Highlighting is hidden.
450 * Add a new hilite to a hilite list.
453 add_hilite(anchor, hl)
454 struct hilite *anchor;
460 * Hilites are sorted in the list; find where new one belongs.
461 * Insert new one after ihl.
463 for (ihl = anchor; ihl->hl_next != NULL; ihl = ihl->hl_next)
465 if (ihl->hl_next->hl_startpos > hl->hl_startpos)
470 * Truncate hilite so it doesn't overlap any existing ones
471 * above and below it.
474 hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
475 if (ihl->hl_next != NULL)
476 hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
477 if (hl->hl_startpos >= hl->hl_endpos)
480 * Hilite was truncated out of existence.
485 hl->hl_next = ihl->hl_next;
490 * Hilight every character in a range of displayed characters.
493 create_hilites(linepos, start_index, end_index, chpos)
502 /* Start the first hilite. */
503 hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
504 hl->hl_startpos = linepos + chpos[start_index];
507 * Step through the displayed chars.
508 * If the source position (before cvt) of the char is one more
509 * than the source pos of the previous char (the usual case),
510 * just increase the size of the current hilite by one.
511 * Otherwise (there are backspaces or something involved),
512 * finish the current hilite and start a new one.
514 for (i = start_index+1; i <= end_index; i++)
516 if (chpos[i] != chpos[i-1] + 1 || i == end_index)
518 hl->hl_endpos = linepos + chpos[i-1] + 1;
519 add_hilite(&hilite_anchor, hl);
520 /* Start new hilite unless this is the last char. */
523 hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
524 hl->hl_startpos = linepos + chpos[i];
531 * Make a hilite for each string in a physical line which matches
532 * the current pattern.
533 * sp,ep delimit the first match already found.
536 hilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops)
546 char *line_end = line + line_len;
548 if (sp == NULL || ep == NULL)
551 * sp and ep delimit the first match in the line.
552 * Mark the corresponding file positions, then
553 * look for further matches and mark them.
554 * {{ This technique, of calling match_pattern on subsequent
555 * substrings of the line, may mark more than is correct
556 * if the pattern starts with "^". This bug is fixed
557 * for those regex functions that accept a notbol parameter
558 * (currently POSIX, PCRE and V8-with-regexec2). }}
562 create_hilites(linepos, sp-line, ep-line, chpos);
564 * If we matched more than zero characters,
565 * move to the first char after the string we matched.
566 * If we matched zero, just move to the next char.
570 else if (searchp != line_end)
572 else /* end of line */
574 } while (match_pattern(info_compiled(&search_info), search_info.text,
575 searchp, line_end - searchp, &sp, &ep, 1, search_info.search_type));
580 * Change the caseless-ness of searches.
581 * Updates the internal search state to reflect a change in the -i flag.
586 if (!is_ucase_pattern)
588 * Pattern did not have uppercase.
589 * Just set the search caselessness to the global caselessness.
591 is_caseless = caseless;
594 * Pattern did have uppercase.
595 * Discard the pattern; we can't change search caselessness now.
597 clear_pattern(&search_info);
602 * Find matching text which is currently on screen and highlight it.
607 struct scrpos scrpos;
610 if (scrpos.pos == NULL_POSITION)
612 prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
617 * Change highlighting parameters.
623 * Erase any highlights currently on screen.
628 if (hilite_search == OPT_ONPLUS)
630 * Display highlights.
637 * Figure out where to start a search.
640 search_pos(search_type)
649 * Start at the beginning (or end) of the file.
650 * The empty_screen() case is mainly for
651 * command line initiated searches;
652 * for example, "+/xyz" on the command line.
653 * Also for multi-file (SRCH_PAST_EOF) searches.
655 if (search_type & SRCH_FORW)
661 if (pos == NULL_POSITION)
663 (void) ch_end_seek();
672 if (how_search == OPT_ON)
675 * Search does not include current screen.
677 if (search_type & SRCH_FORW)
678 linenum = BOTTOM_PLUS_ONE;
681 } else if (how_search == OPT_ONPLUS && !(search_type & SRCH_AFTER_TARGET))
684 * Search includes all of displayed screen.
686 if (search_type & SRCH_FORW)
689 linenum = BOTTOM_PLUS_ONE;
693 * Search includes the part of current screen beyond the jump target.
694 * It starts at the jump target (if searching backwards),
695 * or at the jump target plus one (if forwards).
697 linenum = jump_sline;
698 if (search_type & SRCH_FORW)
701 linenum = adjsline(linenum);
702 pos = position(linenum);
704 pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
708 * If the line is empty, look around for a plausible starting place.
710 if (search_type & SRCH_FORW)
712 while (pos == NULL_POSITION)
714 if (++linenum >= sc_height)
716 pos = position(linenum);
720 while (pos == NULL_POSITION)
724 pos = position(linenum);
731 * Search a subset of the file, specified by start/end position.
734 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
752 POSITION linepos, oldpos;
754 linenum = find_linenum(pos);
759 * Get lines until we find a matching one or until
760 * we hit end-of-file (or beginning-of-file if we're
761 * going backwards), or until we hit the end position.
766 * A signal aborts the search.
771 if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
774 * Reached end position without a match.
783 if (search_type & SRCH_FORW)
786 * Read the next line, and save the
787 * starting position of that line in linepos.
790 pos = forw_raw_line(pos, &line, &line_len);
796 * Read the previous line and save the
797 * starting position of that line in linepos.
799 pos = back_raw_line(pos, &line, &line_len);
805 if (pos == NULL_POSITION)
808 * Reached EOF/BOF without a match.
816 * If we're using line numbers, we might as well
817 * remember the information we have now (the position
818 * and line number of the current line).
819 * Don't do it for every line because it slows down
820 * the search. Remember the line number only if
821 * we're "far" from the last place we remembered it.
823 if (linenums && abs((int)(pos - oldpos)) > 2048)
824 add_lnum(linenum, pos);
827 if (is_filtered(linepos))
831 * If it's a caseless search, convert the line to lowercase.
832 * If we're doing backspace processing, delete backspaces.
834 cvt_ops = get_cvt_ops();
835 cvt_len = cvt_length(line_len, cvt_ops);
836 cline = (char *) ecalloc(1, cvt_len);
837 chpos = cvt_alloc_chpos(cvt_len);
838 cvt_text(cline, line, chpos, &line_len, cvt_ops);
842 * Check to see if the line matches the filter pattern.
843 * If so, add an entry to the filter list.
845 if ((search_type & SRCH_FIND_ALL) && prev_pattern(&filter_info)) {
846 int line_filter = match_pattern(info_compiled(&filter_info), filter_info.text,
847 cline, line_len, &sp, &ep, 0, filter_info.search_type);
850 struct hilite *hl = (struct hilite *)
851 ecalloc(1, sizeof(struct hilite));
852 hl->hl_startpos = linepos;
854 add_hilite(&filter_anchor, hl);
860 * Test the next line to see if we have a match.
861 * We are successful if we either want a match and got one,
862 * or if we want a non-match and got one.
864 if (prev_pattern(&search_info))
866 line_match = match_pattern(info_compiled(&search_info), search_info.text,
867 cline, line_len, &sp, &ep, 0, search_type);
873 if (search_type & SRCH_FIND_ALL)
877 * We are supposed to find all matches in the range.
878 * Just add the matches in this line to the
879 * hilite list and keep searching.
881 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops);
883 } else if (--matches <= 0)
886 * Found the one match we're looking for.
890 if (hilite_search == OPT_ON)
893 * Clear the hilite list and add only
894 * the matches in this one line.
897 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops);
902 if (plinepos != NULL)
914 * search for a pattern in history. If found, compile that pattern.
917 hist_pattern(search_type)
923 set_mlist(ml_search, 0);
924 pattern = cmd_lastpattern();
928 if (set_pattern(&search_info, pattern, search_type) < 0)
932 if (hilite_search == OPT_ONPLUS && !hide_hilite)
937 #else /* CMD_HISTORY */
939 #endif /* CMD_HISTORY */
943 * Search for the n-th occurrence of a specified pattern,
944 * either forward or backward.
945 * Return the number of matches not yet found in this file
946 * (that is, n minus the number of matches found).
947 * Return -1 if the search should be aborted.
948 * Caller may continue the search in another file
949 * if less than n matches are found in this file.
952 search(search_type, pattern, n)
959 if (pattern == NULL || *pattern == '\0')
962 * A null pattern means use the previously compiled pattern.
964 search_type |= SRCH_AFTER_TARGET;
965 if (!prev_pattern(&search_info) && !hist_pattern(search_type))
967 error("No previous regular expression", NULL_PARG);
970 if ((search_type & SRCH_NO_REGEX) !=
971 (search_info.search_type & SRCH_NO_REGEX))
973 error("Please re-enter search pattern", NULL_PARG);
977 if (hilite_search == OPT_ON)
980 * Erase the highlights currently on screen.
981 * If the search fails, we'll redisplay them later.
985 if (hilite_search == OPT_ONPLUS && hide_hilite)
988 * Highlight any matches currently on screen,
989 * before we actually start the search.
999 * Compile the pattern.
1001 if (set_pattern(&search_info, pattern, search_type) < 0)
1007 * Erase the highlights currently on screen.
1008 * Also permanently delete them from the hilite list.
1014 if (hilite_search == OPT_ONPLUS)
1017 * Highlight any matches currently on screen,
1018 * before we actually start the search.
1026 * Figure out where to start the search.
1028 pos = search_pos(search_type);
1029 if (pos == NULL_POSITION)
1032 * Can't find anyplace to start searching from.
1034 if (search_type & SRCH_PAST_EOF)
1036 /* repaint(); -- why was this here? */
1037 error("Nothing to search", NULL_PARG);
1041 n = search_range(pos, NULL_POSITION, search_type, n, -1,
1042 &pos, (POSITION*)NULL);
1046 * Search was unsuccessful.
1049 if (hilite_search == OPT_ON && n > 0)
1051 * Redisplay old hilites.
1058 if (!(search_type & SRCH_NO_MOVE))
1061 * Go to the matching line.
1063 jump_loc(pos, jump_sline);
1067 if (hilite_search == OPT_ON)
1069 * Display new hilites in the matching line.
1079 * Prepare hilites in a given range of the file.
1081 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1082 * of the file that has been "prepared"; that is, scanned for matches for
1083 * the current search pattern, and hilites have been created for such matches.
1084 * If prep_startpos == NULL_POSITION, the prep region is empty.
1085 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1086 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1089 prep_hilite(spos, epos, maxlines)
1094 POSITION nprep_startpos = prep_startpos;
1095 POSITION nprep_endpos = prep_endpos;
1102 * Search beyond where we're asked to search, so the prep region covers
1103 * more than we need. Do one big search instead of a bunch of small ones.
1105 #define SEARCH_MORE (3*size_linebuf)
1107 if (!prev_pattern(&search_info) && !is_filtering())
1111 * If we're limited to a max number of lines, figure out the
1112 * file position we should stop at.
1115 max_epos = NULL_POSITION;
1119 for (i = 0; i < maxlines; i++)
1120 max_epos = forw_raw_line(max_epos, (char **)NULL, (int *)NULL);
1125 * The range that we need to search (spos,epos); and the range that
1126 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1129 if (prep_startpos == NULL_POSITION ||
1130 (epos != NULL_POSITION && epos < prep_startpos) ||
1134 * New range is not contiguous with old prep region.
1135 * Discard the old prep region and start a new one.
1139 if (epos != NULL_POSITION)
1140 epos += SEARCH_MORE;
1141 nprep_startpos = spos;
1145 * New range partially or completely overlaps old prep region.
1147 if (epos == NULL_POSITION)
1150 * New range goes to end of file.
1153 } else if (epos > prep_endpos)
1156 * New range ends after old prep region.
1157 * Extend prep region to end at end of new range.
1159 epos += SEARCH_MORE;
1160 } else /* (epos <= prep_endpos) */
1163 * New range ends within old prep region.
1164 * Truncate search to end at start of old prep region.
1166 epos = prep_startpos;
1169 if (spos < prep_startpos)
1172 * New range starts before old prep region.
1173 * Extend old prep region backwards to start at
1174 * start of new range.
1176 if (spos < SEARCH_MORE)
1179 spos -= SEARCH_MORE;
1180 nprep_startpos = spos;
1181 } else /* (spos >= prep_startpos) */
1184 * New range starts within or after old prep region.
1185 * Trim search to start at end of old prep region.
1191 if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1194 * Don't go past the max position we're allowed.
1198 if (epos == NULL_POSITION || epos > spos)
1200 int search_type = SRCH_FORW | SRCH_FIND_ALL;
1201 search_type |= (search_info.search_type & SRCH_NO_REGEX);
1202 result = search_range(spos, epos, search_type, 0,
1203 maxlines, (POSITION*)NULL, &new_epos);
1206 if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1207 nprep_endpos = new_epos;
1209 prep_startpos = nprep_startpos;
1210 prep_endpos = nprep_endpos;
1214 * Set the pattern to be used for line filtering.
1217 set_filter_pattern(pattern, search_type)
1222 if (pattern == NULL || *pattern == '\0')
1223 clear_pattern(&filter_info);
1225 set_pattern(&filter_info, pattern, search_type);
1230 * Is there a line filter in effect?
1235 if (ch_getflags() & CH_HELPFILE)
1237 return prev_pattern(&filter_info);
1243 * This function is called by the V8 regcomp to report
1244 * errors in regular expressions.