3 * Copyright (C) 1984-2002 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.
20 #define MINPOS(a,b) (((a) < (b)) ? (a) : (b))
21 #define MAXPOS(a,b) (((a) > (b)) ? (a) : (b))
23 #if HAVE_POSIX_REGCOMP
26 #define REGCOMP_FLAG (more_mode ? 0 : REG_EXTENDED)
28 #define REGCOMP_FLAG 0
50 extern int how_search;
54 extern int jump_sline;
58 extern int status_col;
59 extern POSITION start_attnpos;
60 extern POSITION end_attnpos;
62 extern int hilite_search;
63 extern int screen_trashed;
64 extern int size_linebuf;
66 extern int can_goto_line;
67 static int hide_hilite;
68 static POSITION prep_startpos;
69 static POSITION prep_endpos;
73 struct hilite *hl_next;
77 static struct hilite hilite_anchor = { NULL, NULL_POSITION, NULL_POSITION };
78 #define hl_first hl_next
82 * These are the static variables that represent the "remembered"
85 #if HAVE_POSIX_REGCOMP
86 static regex_t *regpattern = NULL;
89 pcre *regpattern = NULL;
95 static char *cpattern = NULL;
98 static struct regexp *regpattern = NULL;
101 static int is_caseless;
102 static int is_ucase_pattern;
103 static int last_search_type;
104 static char *last_pattern = NULL;
107 * Convert text. Perform one or more of these transformations:
109 #define CVT_TO_LC 01 /* Convert upper-case to lower-case */
110 #define CVT_BS 02 /* Do backspace processing */
111 #define CVT_CRLF 04 /* Remove CR after LF */
112 #define CVT_ANSI 010 /* Remove ANSI escape sequences */
115 cvt_text(odst, osrc, ops)
123 for (src = osrc, dst = odst; *src != '\0'; src++)
125 if ((ops & CVT_TO_LC) && isupper((unsigned char) *src))
126 /* Convert uppercase to lowercase. */
127 *dst++ = tolower((unsigned char) *src);
128 else if ((ops & CVT_BS) && *src == '\b' && dst > odst)
129 /* Delete BS and preceding char. */
131 else if ((ops & CVT_ANSI) && *src == ESC)
133 /* Skip to end of ANSI escape sequence. */
134 while (src[1] != '\0')
135 if (is_ansi_end(*++src))
141 if ((ops & CVT_CRLF) && dst > odst && dst[-1] == '\r')
147 * Determine which conversions to perform.
153 if (is_caseless || bs_mode == BS_SPECIAL)
157 if (bs_mode == BS_SPECIAL)
159 if (bs_mode != BS_CONTROL)
161 } else if (bs_mode != BS_CONTROL)
165 if (ctldisp == OPT_ONPLUS)
171 * Are there any uppercase letters in this string?
179 for (p = s; *p != '\0'; p++)
180 if (isupper((unsigned char) *p))
186 * Is there a previous (remembered) search pattern?
191 if (last_search_type & SRCH_NO_REGEX)
192 return (last_pattern != NULL);
193 #if HAVE_POSIX_REGCOMP
194 return (regpattern != NULL);
197 return (regpattern != NULL);
200 return (re_pattern != 0);
203 return (cpattern != NULL);
206 return (regpattern != NULL);
209 return (last_pattern != NULL);
215 * Repaint the hilites currently displayed on the screen.
216 * Repaint each line which contains highlighted text.
217 * If on==0, force all hilites off.
226 int save_hide_hilite;
231 save_hide_hilite = hide_hilite;
242 hide_hilite = save_hide_hilite;
246 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
248 pos = position(slinenum);
249 if (pos == NULL_POSITION)
251 epos = position(slinenum+1);
253 * If any character in the line is highlighted,
256 if (is_hilited(pos, epos, 1))
258 (void) forw_line(pos);
263 hide_hilite = save_hide_hilite;
267 * Clear the attn hilite.
273 POSITION old_start_attnpos;
274 POSITION old_end_attnpos;
278 if (start_attnpos == NULL_POSITION)
280 old_start_attnpos = start_attnpos;
281 old_end_attnpos = end_attnpos;
282 start_attnpos = end_attnpos = NULL_POSITION;
292 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++)
294 pos = position(slinenum);
295 if (pos == NULL_POSITION)
297 epos = position(slinenum+1);
298 if (pos < old_end_attnpos &&
299 (epos == NULL_POSITION || epos > old_start_attnpos))
301 (void) forw_line(pos);
310 * Hide search string highlighting.
317 error("No previous regular expression", NULL_PARG);
321 hide_hilite = !hide_hilite;
327 * Compile a search pattern, for future use by match_pattern.
330 compile_pattern(pattern, search_type)
334 if ((search_type & SRCH_NO_REGEX) == 0)
336 #if HAVE_POSIX_REGCOMP
337 regex_t *s = (regex_t *) ecalloc(1, sizeof(regex_t));
338 if (regcomp(s, pattern, REGCOMP_FLAG))
341 error("Invalid pattern", NULL_PARG);
344 if (regpattern != NULL)
350 const char *errstring;
353 comp = pcre_compile(pattern, 0,
354 &errstring, &erroffset, NULL);
357 parg.p_string = (char *) errstring;
365 if ((parg.p_string = re_comp(pattern)) != NULL)
374 if ((s = regcmp(pattern, 0)) == NULL)
376 error("Invalid pattern", NULL_PARG);
379 if (cpattern != NULL)
385 if ((s = regcomp(pattern)) == NULL)
388 * regcomp has already printed an error message
393 if (regpattern != NULL)
399 if (last_pattern != NULL)
401 last_pattern = (char *) calloc(1, strlen(pattern)+1);
402 if (last_pattern != NULL)
403 strcpy(last_pattern, pattern);
405 last_search_type = search_type;
410 * Forget that we have a compiled pattern.
415 #if HAVE_POSIX_REGCOMP
416 if (regpattern != NULL)
421 if (regpattern != NULL)
422 pcre_free(regpattern);
429 if (cpattern != NULL)
434 if (regpattern != NULL)
442 * Perform a pattern match with the previously compiled pattern.
443 * Set sp and ep to the start and end of the matched string.
446 match_pattern(line, sp, ep, notbol)
454 if (last_search_type & SRCH_NO_REGEX)
455 return (match(last_pattern, line, sp, ep));
457 #if HAVE_POSIX_REGCOMP
460 int flags = (notbol) ? REG_NOTBOL : 0;
461 matched = !regexec(regpattern, line, 1, &rm, flags);
465 *sp = line + rm.rm_so;
466 *ep = line + rm.rm_eo;
475 int flags = (notbol) ? PCRE_NOTBOL : 0;
477 matched = pcre_exec(regpattern, NULL, line, strlen(line),
478 0, flags, ovector, 3) >= 0;
481 *sp = line + ovector[0];
482 *ep = line + ovector[1];
486 matched = (re_exec(line) == 1);
488 * re_exec doesn't seem to provide a way to get the matched string.
493 *ep = regex(cpattern, line);
494 matched = (*ep != NULL);
501 matched = regexec2(regpattern, line, notbol);
503 matched = regexec(regpattern, line);
507 *sp = regpattern->startp[0];
508 *ep = regpattern->endp[0];
511 matched = match(last_pattern, line, sp, ep);
518 * Clear the hilite list.
524 struct hilite *nexthl;
526 for (hl = hilite_anchor.hl_first; hl != NULL; hl = nexthl)
528 nexthl = hl->hl_next;
531 hilite_anchor.hl_first = NULL;
532 prep_startpos = prep_endpos = NULL_POSITION;
536 * Should any characters in a specified range be highlighted?
537 * If nohide is nonzero, don't consider hide_hilite.
540 is_hilited(pos, epos, nohide)
548 start_attnpos != NULL_POSITION &&
550 (epos == NULL_POSITION || epos > start_attnpos))
552 * The attn line overlaps this range.
556 if (hilite_search == 0)
558 * Not doing highlighting.
562 if (!nohide && hide_hilite)
564 * Highlighting is hidden.
569 * Look at each highlight and see if any part of it falls in the range.
571 for (hl = hilite_anchor.hl_first; hl != NULL; hl = hl->hl_next)
573 if (hl->hl_endpos > pos &&
574 (epos == NULL_POSITION || epos > hl->hl_startpos))
581 * Add a new hilite to a hilite list.
584 add_hilite(anchor, hl)
585 struct hilite *anchor;
591 * Hilites are sorted in the list; find where new one belongs.
592 * Insert new one after ihl.
594 for (ihl = anchor; ihl->hl_next != NULL; ihl = ihl->hl_next)
596 if (ihl->hl_next->hl_startpos > hl->hl_startpos)
601 * Truncate hilite so it doesn't overlap any existing ones
602 * above and below it.
605 hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
606 if (ihl->hl_next != NULL)
607 hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
608 if (hl->hl_startpos >= hl->hl_endpos)
611 * Hilite was truncated out of existence.
616 hl->hl_next = ihl->hl_next;
621 * Adjust hl_startpos & hl_endpos to account for backspace processing.
624 adj_hilite(anchor, linepos, cvt_ops)
625 struct hilite *anchor;
636 * The line was already scanned and hilites were added (in hilite_line).
637 * But it was assumed that each char position in the line
638 * correponds to one char position in the file.
639 * This may not be true if there are backspaces in the line.
640 * Get the raw line again. Look at each character.
642 (void) forw_raw_line(linepos, &line);
643 opos = npos = linepos;
644 hl = anchor->hl_first;
649 * See if we need to adjust the current hl_startpos or
650 * hl_endpos. After adjusting startpos[i], move to endpos[i].
651 * After adjusting endpos[i], move to startpos[i+1].
652 * The hilite list must be sorted thus:
653 * startpos[0] < endpos[0] <= startpos[1] < endpos[1] <= etc.
655 if (checkstart && hl->hl_startpos == opos)
657 hl->hl_startpos = npos;
659 continue; /* {{ not really necessary }} */
660 } else if (!checkstart && hl->hl_endpos == opos)
662 hl->hl_endpos = npos;
665 continue; /* {{ necessary }} */
669 if (cvt_ops & CVT_ANSI)
671 while (line[0] == ESC)
674 * Found an ESC. The file position moves
675 * forward past the entire ANSI escape sequence.
679 while (*line != '\0')
682 if (is_ansi_end(*line++))
690 if (cvt_ops & CVT_BS)
692 while (line[0] == '\b' && line[1] != '\0')
695 * Found a backspace. The file position moves
696 * forward by 2 relative to the processed line
697 * which was searched in hilite_line.
707 * Make a hilite for each string in a physical line which matches
708 * the current pattern.
709 * sp,ep delimit the first match already found.
712 hilite_line(linepos, line, sp, ep, cvt_ops)
721 struct hilite hilites;
723 if (sp == NULL || ep == NULL)
726 * sp and ep delimit the first match in the line.
727 * Mark the corresponding file positions, then
728 * look for further matches and mark them.
729 * {{ This technique, of calling match_pattern on subsequent
730 * substrings of the line, may mark more than is correct
731 * if the pattern starts with "^". This bug is fixed
732 * for those regex functions that accept a notbol parameter
733 * (currently POSIX and V8-with-regexec2). }}
737 * Put the hilites into a temporary list until they're adjusted.
739 hilites.hl_first = NULL;
744 * Assume that each char position in the "line"
745 * buffer corresponds to one char position in the file.
746 * This is not quite true; we need to adjust later.
748 hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
749 hl->hl_startpos = linepos + (sp-line);
750 hl->hl_endpos = linepos + (ep-line);
751 add_hilite(&hilites, hl);
754 * If we matched more than zero characters,
755 * move to the first char after the string we matched.
756 * If we matched zero, just move to the next char.
760 else if (*searchp != '\0')
762 else /* end of line */
764 } while (match_pattern(searchp, &sp, &ep, 1));
767 * If there were backspaces in the original line, they
768 * were removed, and hl_startpos/hl_endpos are not correct.
769 * {{ This is very ugly. }}
771 adj_hilite(&hilites, linepos, cvt_ops);
774 * Now put the hilites into the real list.
776 while ((hl = hilites.hl_next) != NULL)
778 hilites.hl_next = hl->hl_next;
779 add_hilite(&hilite_anchor, hl);
785 * Change the caseless-ness of searches.
786 * Updates the internal search state to reflect a change in the -i flag.
791 if (!is_ucase_pattern)
793 * Pattern did not have uppercase.
794 * Just set the search caselessness to the global caselessness.
796 is_caseless = caseless;
799 * Pattern did have uppercase.
800 * Discard the pattern; we can't change search caselessness now.
807 * Find matching text which is currently on screen and highlight it.
812 struct scrpos scrpos;
815 if (scrpos.pos == NULL_POSITION)
817 prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
822 * Change highlighting parameters.
828 * Erase any highlights currently on screen.
833 if (hilite_search == OPT_ONPLUS)
835 * Display highlights.
842 * Figure out where to start a search.
845 search_pos(search_type)
854 * Start at the beginning (or end) of the file.
855 * The empty_screen() case is mainly for
856 * command line initiated searches;
857 * for example, "+/xyz" on the command line.
858 * Also for multi-file (SRCH_PAST_EOF) searches.
860 if (search_type & SRCH_FORW)
866 if (pos == NULL_POSITION)
868 (void) ch_end_seek();
877 * Search does not include current screen.
879 if (search_type & SRCH_FORW)
880 linenum = BOTTOM_PLUS_ONE;
883 pos = position(linenum);
887 * Search includes current screen.
888 * It starts at the jump target (if searching backwards),
889 * or at the jump target plus one (if forwards).
891 linenum = adjsline(jump_sline);
892 pos = position(linenum);
893 if (search_type & SRCH_FORW)
895 pos = forw_raw_line(pos, (char **)NULL);
896 while (pos == NULL_POSITION)
898 if (++linenum >= sc_height)
900 pos = position(linenum);
904 while (pos == NULL_POSITION)
908 pos = position(linenum);
916 * Search a subset of the file, specified by start/end position.
919 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
933 POSITION linepos, oldpos;
935 linenum = find_linenum(pos);
940 * Get lines until we find a matching one or until
941 * we hit end-of-file (or beginning-of-file if we're
942 * going backwards), or until we hit the end position.
947 * A signal aborts the search.
952 if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
955 * Reached end position without a match.
964 if (search_type & SRCH_FORW)
967 * Read the next line, and save the
968 * starting position of that line in linepos.
971 pos = forw_raw_line(pos, &line);
977 * Read the previous line and save the
978 * starting position of that line in linepos.
980 pos = back_raw_line(pos, &line);
986 if (pos == NULL_POSITION)
989 * Reached EOF/BOF without a match.
997 * If we're using line numbers, we might as well
998 * remember the information we have now (the position
999 * and line number of the current line).
1000 * Don't do it for every line because it slows down
1001 * the search. Remember the line number only if
1002 * we're "far" from the last place we remembered it.
1004 if (linenums && abs((int)(pos - oldpos)) > 1024)
1005 add_lnum(linenum, pos);
1009 * If it's a caseless search, convert the line to lowercase.
1010 * If we're doing backspace processing, delete backspaces.
1012 cvt_ops = get_cvt_ops();
1013 cvt_text(line, line, cvt_ops);
1016 * Test the next line to see if we have a match.
1017 * We are successful if we either want a match and got one,
1018 * or if we want a non-match and got one.
1020 line_match = match_pattern(line, &sp, &ep, 0);
1021 line_match = (!(search_type & SRCH_NO_MATCH) && line_match) ||
1022 ((search_type & SRCH_NO_MATCH) && !line_match);
1028 if (search_type & SRCH_FIND_ALL)
1032 * We are supposed to find all matches in the range.
1033 * Just add the matches in this line to the
1034 * hilite list and keep searching.
1037 hilite_line(linepos, line, sp, ep, cvt_ops);
1039 } else if (--matches <= 0)
1042 * Found the one match we're looking for.
1046 if (hilite_search == 1)
1049 * Clear the hilite list and add only
1050 * the matches in this one line.
1054 hilite_line(linepos, line, sp, ep, cvt_ops);
1057 if (plinepos != NULL)
1058 *plinepos = linepos;
1065 * Search for the n-th occurrence of a specified pattern,
1066 * either forward or backward.
1067 * Return the number of matches not yet found in this file
1068 * (that is, n minus the number of matches found).
1069 * Return -1 if the search should be aborted.
1070 * Caller may continue the search in another file
1071 * if less than n matches are found in this file.
1074 search(search_type, pattern, n)
1082 if (pattern == NULL || *pattern == '\0')
1085 * A null pattern means use the previously compiled pattern.
1087 if (!prev_pattern())
1089 error("No previous regular expression", NULL_PARG);
1092 if ((search_type & SRCH_NO_REGEX) !=
1093 (last_search_type & SRCH_NO_REGEX))
1095 error("Please re-enter search pattern", NULL_PARG);
1099 if (hilite_search == OPT_ON)
1102 * Erase the highlights currently on screen.
1103 * If the search fails, we'll redisplay them later.
1107 if (hilite_search == OPT_ONPLUS && hide_hilite)
1110 * Highlight any matches currently on screen,
1111 * before we actually start the search.
1121 * Compile the pattern.
1123 ucase = is_ucase(pattern);
1124 if (caseless == OPT_ONPLUS)
1125 cvt_text(pattern, pattern, CVT_TO_LC);
1126 if (compile_pattern(pattern, search_type) < 0)
1129 * Ignore case if -I is set OR
1130 * -i is set AND the pattern is all lowercase.
1132 is_ucase_pattern = ucase;
1133 if (is_ucase_pattern && caseless != OPT_ONPLUS)
1136 is_caseless = caseless;
1141 * Erase the highlights currently on screen.
1142 * Also permanently delete them from the hilite list.
1148 if (hilite_search == OPT_ONPLUS)
1151 * Highlight any matches currently on screen,
1152 * before we actually start the search.
1160 * Figure out where to start the search.
1162 pos = search_pos(search_type);
1163 if (pos == NULL_POSITION)
1166 * Can't find anyplace to start searching from.
1168 if (search_type & SRCH_PAST_EOF)
1170 /* repaint(); -- why was this here? */
1171 error("Nothing to search", NULL_PARG);
1175 n = search_range(pos, NULL_POSITION, search_type, n, -1,
1176 &pos, (POSITION*)NULL);
1180 * Search was unsuccessful.
1183 if (hilite_search == OPT_ON && n > 0)
1185 * Redisplay old hilites.
1192 if (!(search_type & SRCH_NO_MOVE))
1195 * Go to the matching line.
1197 jump_loc(pos, jump_sline);
1201 if (hilite_search == OPT_ON)
1203 * Display new hilites in the matching line.
1213 * Prepare hilites in a given range of the file.
1215 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1216 * of the file that has been "prepared"; that is, scanned for matches for
1217 * the current search pattern, and hilites have been created for such matches.
1218 * If prep_startpos == NULL_POSITION, the prep region is empty.
1219 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1220 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1223 prep_hilite(spos, epos, maxlines)
1228 POSITION nprep_startpos = prep_startpos;
1229 POSITION nprep_endpos = prep_endpos;
1235 * Search beyond where we're asked to search, so the prep region covers
1236 * more than we need. Do one big search instead of a bunch of small ones.
1238 #define SEARCH_MORE (3*size_linebuf)
1240 if (!prev_pattern())
1244 * If we're limited to a max number of lines, figure out the
1245 * file position we should stop at.
1248 max_epos = NULL_POSITION;
1252 for (i = 0; i < maxlines; i++)
1253 max_epos = forw_raw_line(max_epos, (char **)NULL);
1258 * The range that we need to search (spos,epos); and the range that
1259 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1262 if (prep_startpos == NULL_POSITION ||
1263 (epos != NULL_POSITION && epos < prep_startpos) ||
1267 * New range is not contiguous with old prep region.
1268 * Discard the old prep region and start a new one.
1271 if (epos != NULL_POSITION)
1272 epos += SEARCH_MORE;
1273 nprep_startpos = spos;
1277 * New range partially or completely overlaps old prep region.
1279 if (epos == NULL_POSITION)
1282 * New range goes to end of file.
1285 } else if (epos > prep_endpos)
1288 * New range ends after old prep region.
1289 * Extend prep region to end at end of new range.
1291 epos += SEARCH_MORE;
1292 } else /* (epos <= prep_endpos) */
1295 * New range ends within old prep region.
1296 * Truncate search to end at start of old prep region.
1298 epos = prep_startpos;
1301 if (spos < prep_startpos)
1304 * New range starts before old prep region.
1305 * Extend old prep region backwards to start at
1306 * start of new range.
1308 if (spos < SEARCH_MORE)
1311 spos -= SEARCH_MORE;
1312 nprep_startpos = spos;
1313 } else /* (spos >= prep_startpos) */
1316 * New range starts within or after old prep region.
1317 * Trim search to start at end of old prep region.
1323 if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1326 * Don't go past the max position we're allowed.
1330 if (epos == NULL_POSITION || epos > spos)
1332 result = search_range(spos, epos, SRCH_FORW|SRCH_FIND_ALL, 0,
1333 maxlines, (POSITION*)NULL, &new_epos);
1336 if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1337 nprep_endpos = new_epos;
1339 prep_startpos = nprep_startpos;
1340 prep_endpos = nprep_endpos;
1345 * Simple pattern matching function.
1346 * It supports no metacharacters like *, etc.
1349 match(pattern, buf, pfound, pend)
1350 char *pattern, *buf;
1351 char **pfound, **pend;
1353 register char *pp, *lp;
1355 for ( ; *buf != '\0'; buf++)
1357 for (pp = pattern, lp = buf; *pp == *lp; pp++, lp++)
1358 if (*pp == '\0' || *lp == '\0')
1374 * This function is called by the V8 regcomp to report
1375 * errors in regular expressions.