xref: /freebsd/contrib/less/search.c (revision f856af0466c076beef4ea9b15d088e1119a945b8)
1 /* $FreeBSD$ */
2 /*
3  * Copyright (C) 1984-2005  Mark Nudelman
4  *
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.
7  *
8  * For more information about less, or for information on how to
9  * contact the author, see the README file.
10  */
11 
12 
13 /*
14  * Routines to search a file for a pattern.
15  */
16 
17 #include "less.h"
18 #include "position.h"
19 
20 #define	MINPOS(a,b)	(((a) < (b)) ? (a) : (b))
21 #define	MAXPOS(a,b)	(((a) > (b)) ? (a) : (b))
22 
23 #if HAVE_POSIX_REGCOMP
24 #include <regex.h>
25 #ifdef REG_EXTENDED
26 #define	REGCOMP_FLAG	(more_mode ? 0 : REG_EXTENDED)
27 #else
28 #define	REGCOMP_FLAG	0
29 #endif
30 #endif
31 #if HAVE_PCRE
32 #include <pcre.h>
33 #endif
34 #if HAVE_RE_COMP
35 char *re_comp();
36 int re_exec();
37 #endif
38 #if HAVE_REGCMP
39 char *regcmp();
40 char *regex();
41 extern char *__loc1;
42 #endif
43 #if HAVE_V8_REGCOMP
44 #include "regexp.h"
45 #endif
46 
47 static int match();
48 
49 extern int sigs;
50 extern int how_search;
51 extern int caseless;
52 extern int linenums;
53 extern int sc_height;
54 extern int jump_sline;
55 extern int bs_mode;
56 extern int more_mode;
57 extern int ctldisp;
58 extern int status_col;
59 extern POSITION start_attnpos;
60 extern POSITION end_attnpos;
61 #if HILITE_SEARCH
62 extern int hilite_search;
63 extern int screen_trashed;
64 extern int size_linebuf;
65 extern int squished;
66 extern int can_goto_line;
67 static int hide_hilite;
68 static POSITION prep_startpos;
69 static POSITION prep_endpos;
70 
71 struct hilite
72 {
73 	struct hilite *hl_next;
74 	POSITION hl_startpos;
75 	POSITION hl_endpos;
76 };
77 static struct hilite hilite_anchor = { NULL, NULL_POSITION, NULL_POSITION };
78 #define	hl_first	hl_next
79 #endif
80 
81 /*
82  * These are the static variables that represent the "remembered"
83  * search pattern.
84  */
85 #if HAVE_POSIX_REGCOMP
86 static regex_t *regpattern = NULL;
87 #endif
88 #if HAVE_PCRE
89 pcre *regpattern = NULL;
90 #endif
91 #if HAVE_RE_COMP
92 int re_pattern = 0;
93 #endif
94 #if HAVE_REGCMP
95 static char *cpattern = NULL;
96 #endif
97 #if HAVE_V8_REGCOMP
98 static struct regexp *regpattern = NULL;
99 #endif
100 
101 static int is_caseless;
102 static int is_ucase_pattern;
103 static int last_search_type;
104 static char *last_pattern = NULL;
105 
106 /*
107  * Convert text.  Perform one or more of these transformations:
108  */
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 */
113 
114 	static void
115 cvt_text(odst, osrc, ops)
116 	char *odst;
117 	char *osrc;
118 	int ops;
119 {
120 	register char *dst;
121 	register char *src;
122 
123 	for (src = osrc, dst = odst;  *src != '\0';  src++)
124 	{
125 		if ((ops & CVT_TO_LC) && IS_UPPER(*src))
126 			/* Convert uppercase to lowercase. */
127 			*dst++ = TO_LOWER(*src);
128 		else if ((ops & CVT_BS) && *src == '\b' && dst > odst)
129 			/* Delete BS and preceding char. */
130 			dst--;
131 		else if ((ops & CVT_ANSI) && *src == ESC)
132 		{
133 			/* Skip to end of ANSI escape sequence. */
134 			while (src[1] != '\0')
135 				if (!is_ansi_middle(*++src))
136 					break;
137 		} else
138 			/* Just copy. */
139 			*dst++ = *src;
140 	}
141 	if ((ops & CVT_CRLF) && dst > odst && dst[-1] == '\r')
142 		dst--;
143 	*dst = '\0';
144 }
145 
146 /*
147  * Determine which conversions to perform.
148  */
149 	static int
150 get_cvt_ops()
151 {
152 	int ops = 0;
153 	if (is_caseless || bs_mode == BS_SPECIAL)
154 	{
155 		if (is_caseless)
156 			ops |= CVT_TO_LC;
157 		if (bs_mode == BS_SPECIAL)
158 			ops |= CVT_BS;
159 		if (bs_mode != BS_CONTROL)
160 			ops |= CVT_CRLF;
161 	} else if (bs_mode != BS_CONTROL)
162 	{
163 		ops |= CVT_CRLF;
164 	}
165 	if (ctldisp == OPT_ONPLUS)
166 		ops |= CVT_ANSI;
167 	return (ops);
168 }
169 
170 /*
171  * Are there any uppercase letters in this string?
172  */
173 	static int
174 is_ucase(s)
175 	char *s;
176 {
177 	register char *p;
178 
179 	for (p = s;  *p != '\0';  p++)
180 		if (IS_UPPER(*p))
181 			return (1);
182 	return (0);
183 }
184 
185 /*
186  * Is there a previous (remembered) search pattern?
187  */
188 	static int
189 prev_pattern()
190 {
191 	if (last_search_type & SRCH_NO_REGEX)
192 		return (last_pattern != NULL);
193 #if HAVE_POSIX_REGCOMP
194 	return (regpattern != NULL);
195 #endif
196 #if HAVE_PCRE
197 	return (regpattern != NULL);
198 #endif
199 #if HAVE_RE_COMP
200 	return (re_pattern != 0);
201 #endif
202 #if HAVE_REGCMP
203 	return (cpattern != NULL);
204 #endif
205 #if HAVE_V8_REGCOMP
206 	return (regpattern != NULL);
207 #endif
208 #if NO_REGEX
209 	return (last_pattern != NULL);
210 #endif
211 }
212 
213 #if HILITE_SEARCH
214 /*
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.
218  */
219 	public void
220 repaint_hilite(on)
221 	int on;
222 {
223 	int slinenum;
224 	POSITION pos;
225 	POSITION epos;
226 	int save_hide_hilite;
227 
228 	if (squished)
229 		repaint();
230 
231 	save_hide_hilite = hide_hilite;
232 	if (!on)
233 	{
234 		if (hide_hilite)
235 			return;
236 		hide_hilite = 1;
237 	}
238 
239 	if (!can_goto_line)
240 	{
241 		repaint();
242 		hide_hilite = save_hide_hilite;
243 		return;
244 	}
245 
246 	for (slinenum = TOP;  slinenum < TOP + sc_height-1;  slinenum++)
247 	{
248 		pos = position(slinenum);
249 		if (pos == NULL_POSITION)
250 			continue;
251 		epos = position(slinenum+1);
252 #if 0
253 		/*
254 		 * If any character in the line is highlighted,
255 		 * repaint the line.
256 		 *
257 		 * {{ This doesn't work -- if line is drawn with highlights
258 		 * which should be erased (e.g. toggle -i with status column),
259 		 * we must redraw the line even if it has no highlights.
260 		 * For now, just repaint every line. }}
261 		 */
262 		if (is_hilited(pos, epos, 1, NULL))
263 #endif
264 		{
265 			(void) forw_line(pos);
266 			goto_line(slinenum);
267 			put_line();
268 		}
269 	}
270 	hide_hilite = save_hide_hilite;
271 }
272 
273 /*
274  * Clear the attn hilite.
275  */
276 	public void
277 clear_attn()
278 {
279 	int slinenum;
280 	POSITION old_start_attnpos;
281 	POSITION old_end_attnpos;
282 	POSITION pos;
283 	POSITION epos;
284 
285 	if (start_attnpos == NULL_POSITION)
286 		return;
287 	old_start_attnpos = start_attnpos;
288 	old_end_attnpos = end_attnpos;
289 	start_attnpos = end_attnpos = NULL_POSITION;
290 
291 	if (!can_goto_line)
292 	{
293 		repaint();
294 		return;
295 	}
296 	if (squished)
297 		repaint();
298 
299 	for (slinenum = TOP;  slinenum < TOP + sc_height-1;  slinenum++)
300 	{
301 		pos = position(slinenum);
302 		if (pos == NULL_POSITION)
303 			continue;
304 		epos = position(slinenum+1);
305 		if (pos < old_end_attnpos &&
306 		     (epos == NULL_POSITION || epos > old_start_attnpos))
307 		{
308 			(void) forw_line(pos);
309 			goto_line(slinenum);
310 			put_line();
311 		}
312 	}
313 }
314 #endif
315 
316 /*
317  * Hide search string highlighting.
318  */
319 	public void
320 undo_search()
321 {
322 	if (!prev_pattern())
323 	{
324 		error("No previous regular expression", NULL_PARG);
325 		return;
326 	}
327 #if HILITE_SEARCH
328 	hide_hilite = !hide_hilite;
329 	repaint_hilite(1);
330 #endif
331 }
332 
333 /*
334  * Compile a search pattern, for future use by match_pattern.
335  */
336 	static int
337 compile_pattern(pattern, search_type)
338 	char *pattern;
339 	int search_type;
340 {
341 	if ((search_type & SRCH_NO_REGEX) == 0)
342 	{
343 #if HAVE_POSIX_REGCOMP
344 		regex_t *s = (regex_t *) ecalloc(1, sizeof(regex_t));
345 		if (regcomp(s, pattern, REGCOMP_FLAG))
346 		{
347 			free(s);
348 			error("Invalid pattern", NULL_PARG);
349 			return (-1);
350 		}
351 		if (regpattern != NULL)
352 			regfree(regpattern);
353 		regpattern = s;
354 #endif
355 #if HAVE_PCRE
356 		pcre *comp;
357 		const char *errstring;
358 		int erroffset;
359 		PARG parg;
360 		comp = pcre_compile(pattern, 0,
361 				&errstring, &erroffset, NULL);
362 		if (comp == NULL)
363 		{
364 			parg.p_string = (char *) errstring;
365 			error("%s", &parg);
366 			return (-1);
367 		}
368 		regpattern = comp;
369 #endif
370 #if HAVE_RE_COMP
371 		PARG parg;
372 		if ((parg.p_string = re_comp(pattern)) != NULL)
373 		{
374 			error("%s", &parg);
375 			return (-1);
376 		}
377 		re_pattern = 1;
378 #endif
379 #if HAVE_REGCMP
380 		char *s;
381 		if ((s = regcmp(pattern, 0)) == NULL)
382 		{
383 			error("Invalid pattern", NULL_PARG);
384 			return (-1);
385 		}
386 		if (cpattern != NULL)
387 			free(cpattern);
388 		cpattern = s;
389 #endif
390 #if HAVE_V8_REGCOMP
391 		struct regexp *s;
392 		if ((s = regcomp(pattern)) == NULL)
393 		{
394 			/*
395 			 * regcomp has already printed an error message
396 			 * via regerror().
397 			 */
398 			return (-1);
399 		}
400 		if (regpattern != NULL)
401 			free(regpattern);
402 		regpattern = s;
403 #endif
404 	}
405 
406 	if (last_pattern != NULL)
407 		free(last_pattern);
408 	last_pattern = (char *) calloc(1, strlen(pattern)+1);
409 	if (last_pattern != NULL)
410 		strcpy(last_pattern, pattern);
411 
412 	last_search_type = search_type;
413 	return (0);
414 }
415 
416 /*
417  * Forget that we have a compiled pattern.
418  */
419 	static void
420 uncompile_pattern()
421 {
422 #if HAVE_POSIX_REGCOMP
423 	if (regpattern != NULL)
424 		regfree(regpattern);
425 	regpattern = NULL;
426 #endif
427 #if HAVE_PCRE
428 	if (regpattern != NULL)
429 		pcre_free(regpattern);
430 	regpattern = NULL;
431 #endif
432 #if HAVE_RE_COMP
433 	re_pattern = 0;
434 #endif
435 #if HAVE_REGCMP
436 	if (cpattern != NULL)
437 		free(cpattern);
438 	cpattern = NULL;
439 #endif
440 #if HAVE_V8_REGCOMP
441 	if (regpattern != NULL)
442 		free(regpattern);
443 	regpattern = NULL;
444 #endif
445 	last_pattern = NULL;
446 }
447 
448 /*
449  * Perform a pattern match with the previously compiled pattern.
450  * Set sp and ep to the start and end of the matched string.
451  */
452 	static int
453 match_pattern(line, sp, ep, notbol)
454 	char *line;
455 	char **sp;
456 	char **ep;
457 	int notbol;
458 {
459 	int matched;
460 
461 	if (last_search_type & SRCH_NO_REGEX)
462 		return (match(last_pattern, line, sp, ep));
463 
464 #if HAVE_POSIX_REGCOMP
465 	{
466 		regmatch_t rm;
467 		int flags = (notbol) ? REG_NOTBOL : 0;
468 		matched = !regexec(regpattern, line, 1, &rm, flags);
469 		if (!matched)
470 			return (0);
471 #ifndef __WATCOMC__
472 		*sp = line + rm.rm_so;
473 		*ep = line + rm.rm_eo;
474 #else
475 		*sp = rm.rm_sp;
476 		*ep = rm.rm_ep;
477 #endif
478 	}
479 #endif
480 #if HAVE_PCRE
481 	{
482 		int flags = (notbol) ? PCRE_NOTBOL : 0;
483 		int ovector[3];
484 		matched = pcre_exec(regpattern, NULL, line, strlen(line),
485 			0, flags, ovector, 3) >= 0;
486 		if (!matched)
487 			return (0);
488 		*sp = line + ovector[0];
489 		*ep = line + ovector[1];
490 	}
491 #endif
492 #if HAVE_RE_COMP
493 	matched = (re_exec(line) == 1);
494 	/*
495 	 * re_exec doesn't seem to provide a way to get the matched string.
496 	 */
497 	*sp = *ep = NULL;
498 #endif
499 #if HAVE_REGCMP
500 	*ep = regex(cpattern, line);
501 	matched = (*ep != NULL);
502 	if (!matched)
503 		return (0);
504 	*sp = __loc1;
505 #endif
506 #if HAVE_V8_REGCOMP
507 #if HAVE_REGEXEC2
508 	matched = regexec2(regpattern, line, notbol);
509 #else
510 	matched = regexec(regpattern, line);
511 #endif
512 	if (!matched)
513 		return (0);
514 	*sp = regpattern->startp[0];
515 	*ep = regpattern->endp[0];
516 #endif
517 #if NO_REGEX
518 	matched = match(last_pattern, line, sp, ep);
519 #endif
520 	return (matched);
521 }
522 
523 #if HILITE_SEARCH
524 /*
525  * Clear the hilite list.
526  */
527 	public void
528 clr_hilite()
529 {
530 	struct hilite *hl;
531 	struct hilite *nexthl;
532 
533 	for (hl = hilite_anchor.hl_first;  hl != NULL;  hl = nexthl)
534 	{
535 		nexthl = hl->hl_next;
536 		free((void*)hl);
537 	}
538 	hilite_anchor.hl_first = NULL;
539 	prep_startpos = prep_endpos = NULL_POSITION;
540 }
541 
542 /*
543  * Should any characters in a specified range be highlighted?
544  */
545 	static int
546 is_hilited_range(pos, epos)
547 	POSITION pos;
548 	POSITION epos;
549 {
550 	struct hilite *hl;
551 
552 	/*
553 	 * Look at each highlight and see if any part of it falls in the range.
554 	 */
555 	for (hl = hilite_anchor.hl_first;  hl != NULL;  hl = hl->hl_next)
556 	{
557 		if (hl->hl_endpos > pos &&
558 		    (epos == NULL_POSITION || epos > hl->hl_startpos))
559 			return (1);
560 	}
561 	return (0);
562 }
563 
564 /*
565  * Should any characters in a specified range be highlighted?
566  * If nohide is nonzero, don't consider hide_hilite.
567  */
568 	public int
569 is_hilited(pos, epos, nohide, p_matches)
570 	POSITION pos;
571 	POSITION epos;
572 	int nohide;
573 	int *p_matches;
574 {
575 	int match;
576 
577 	if (p_matches != NULL)
578 		*p_matches = 0;
579 
580 	if (!status_col &&
581 	    start_attnpos != NULL_POSITION &&
582 	    pos < end_attnpos &&
583 	     (epos == NULL_POSITION || epos > start_attnpos))
584 		/*
585 		 * The attn line overlaps this range.
586 		 */
587 		return (1);
588 
589 	match = is_hilited_range(pos, epos);
590 	if (!match)
591 		return (0);
592 
593 	if (p_matches != NULL)
594 		/*
595 		 * Report matches, even if we're hiding highlights.
596 		 */
597 		*p_matches = 1;
598 
599 	if (hilite_search == 0)
600 		/*
601 		 * Not doing highlighting.
602 		 */
603 		return (0);
604 
605 	if (!nohide && hide_hilite)
606 		/*
607 		 * Highlighting is hidden.
608 		 */
609 		return (0);
610 
611 	return (1);
612 }
613 
614 /*
615  * Add a new hilite to a hilite list.
616  */
617 	static void
618 add_hilite(anchor, hl)
619 	struct hilite *anchor;
620 	struct hilite *hl;
621 {
622 	struct hilite *ihl;
623 
624 	/*
625 	 * Hilites are sorted in the list; find where new one belongs.
626 	 * Insert new one after ihl.
627 	 */
628 	for (ihl = anchor;  ihl->hl_next != NULL;  ihl = ihl->hl_next)
629 	{
630 		if (ihl->hl_next->hl_startpos > hl->hl_startpos)
631 			break;
632 	}
633 
634 	/*
635 	 * Truncate hilite so it doesn't overlap any existing ones
636 	 * above and below it.
637 	 */
638 	if (ihl != anchor)
639 		hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
640 	if (ihl->hl_next != NULL)
641 		hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
642 	if (hl->hl_startpos >= hl->hl_endpos)
643 	{
644 		/*
645 		 * Hilite was truncated out of existence.
646 		 */
647 		free(hl);
648 		return;
649 	}
650 	hl->hl_next = ihl->hl_next;
651 	ihl->hl_next = hl;
652 }
653 
654 	static void
655 adj_hilite_ansi(cvt_ops, line, npos)
656 	int cvt_ops;
657 	char **line;
658 	POSITION *npos;
659 {
660 	if (cvt_ops & CVT_ANSI)
661 		while (**line == ESC)
662 		{
663 			/*
664 			 * Found an ESC.  The file position moves
665 			 * forward past the entire ANSI escape sequence.
666 			 */
667 			(*line)++;
668 			(*npos)++;
669 			while (**line != '\0')
670 			{
671 				(*npos)++;
672 				if (!is_ansi_middle(*(*line)++))
673 					break;
674 			}
675 		}
676 }
677 
678 /*
679  * Adjust hl_startpos & hl_endpos to account for backspace processing.
680  */
681 	static void
682 adj_hilite(anchor, linepos, cvt_ops)
683 	struct hilite *anchor;
684 	POSITION linepos;
685 	int cvt_ops;
686 {
687 	char *line;
688 	struct hilite *hl;
689 	int checkstart;
690 	POSITION opos;
691 	POSITION npos;
692 
693 	/*
694 	 * The line was already scanned and hilites were added (in hilite_line).
695 	 * But it was assumed that each char position in the line
696 	 * correponds to one char position in the file.
697 	 * This may not be true if there are backspaces in the line.
698 	 * Get the raw line again.  Look at each character.
699 	 */
700 	(void) forw_raw_line(linepos, &line);
701 	opos = npos = linepos;
702 	hl = anchor->hl_first;
703 	checkstart = TRUE;
704 	while (hl != NULL)
705 	{
706 		/*
707 		 * See if we need to adjust the current hl_startpos or
708 		 * hl_endpos.  After adjusting startpos[i], move to endpos[i].
709 		 * After adjusting endpos[i], move to startpos[i+1].
710 		 * The hilite list must be sorted thus:
711 		 * startpos[0] < endpos[0] <= startpos[1] < endpos[1] <= etc.
712 		 */
713 		if (checkstart && hl->hl_startpos == opos)
714 		{
715 			hl->hl_startpos = npos;
716 			checkstart = FALSE;
717 			continue; /* {{ not really necessary }} */
718 		} else if (!checkstart && hl->hl_endpos == opos)
719 		{
720 			hl->hl_endpos = npos;
721 			checkstart = TRUE;
722 			hl = hl->hl_next;
723 			continue; /* {{ necessary }} */
724 		}
725 		if (*line == '\0')
726 			break;
727 		adj_hilite_ansi(cvt_ops, &line, &npos);
728 		opos++;
729 		npos++;
730 		line++;
731 		if (cvt_ops & CVT_BS)
732 		{
733 			while (*line == '\b')
734 			{
735 				npos++;
736 				line++;
737 				adj_hilite_ansi(cvt_ops, &line, &npos);
738 				if (*line == '\0')
739 				{
740 					--npos;
741 					--line;
742 					break;
743 				}
744 				/*
745 				 * Found a backspace.  The file position moves
746 				 * forward by 2 relative to the processed line
747 				 * which was searched in hilite_line.
748 				 */
749 				npos++;
750 				line++;
751 			}
752 		}
753 	}
754 }
755 
756 /*
757  * Make a hilite for each string in a physical line which matches
758  * the current pattern.
759  * sp,ep delimit the first match already found.
760  */
761 	static void
762 hilite_line(linepos, line, sp, ep, cvt_ops)
763 	POSITION linepos;
764 	char *line;
765 	char *sp;
766 	char *ep;
767 	int cvt_ops;
768 {
769 	char *searchp;
770 	struct hilite *hl;
771 	struct hilite hilites;
772 
773 	if (sp == NULL || ep == NULL)
774 		return;
775 	/*
776 	 * sp and ep delimit the first match in the line.
777 	 * Mark the corresponding file positions, then
778 	 * look for further matches and mark them.
779 	 * {{ This technique, of calling match_pattern on subsequent
780 	 *    substrings of the line, may mark more than is correct
781 	 *    if the pattern starts with "^".  This bug is fixed
782 	 *    for those regex functions that accept a notbol parameter
783 	 *    (currently POSIX and V8-with-regexec2). }}
784 	 */
785 	searchp = line;
786 	/*
787 	 * Put the hilites into a temporary list until they're adjusted.
788 	 */
789 	hilites.hl_first = NULL;
790 	do {
791 		if (ep > sp)
792 		{
793 			/*
794 			 * Assume that each char position in the "line"
795 			 * buffer corresponds to one char position in the file.
796 			 * This is not quite true; we need to adjust later.
797 			 */
798 			hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
799 			hl->hl_startpos = linepos + (sp-line);
800 			hl->hl_endpos = linepos + (ep-line);
801 			add_hilite(&hilites, hl);
802 		}
803 		/*
804 		 * If we matched more than zero characters,
805 		 * move to the first char after the string we matched.
806 		 * If we matched zero, just move to the next char.
807 		 */
808 		if (ep > searchp)
809 			searchp = ep;
810 		else if (*searchp != '\0')
811 			searchp++;
812 		else /* end of line */
813 			break;
814 	} while (match_pattern(searchp, &sp, &ep, 1));
815 
816 	/*
817 	 * If there were backspaces in the original line, they
818 	 * were removed, and hl_startpos/hl_endpos are not correct.
819 	 * {{ This is very ugly. }}
820 	 */
821 	adj_hilite(&hilites, linepos, cvt_ops);
822 
823 	/*
824 	 * Now put the hilites into the real list.
825 	 */
826 	while ((hl = hilites.hl_next) != NULL)
827 	{
828 		hilites.hl_next = hl->hl_next;
829 		add_hilite(&hilite_anchor, hl);
830 	}
831 }
832 #endif
833 
834 /*
835  * Change the caseless-ness of searches.
836  * Updates the internal search state to reflect a change in the -i flag.
837  */
838 	public void
839 chg_caseless()
840 {
841 	if (!is_ucase_pattern)
842 		/*
843 		 * Pattern did not have uppercase.
844 		 * Just set the search caselessness to the global caselessness.
845 		 */
846 		is_caseless = caseless;
847 	else
848 		/*
849 		 * Pattern did have uppercase.
850 		 * Discard the pattern; we can't change search caselessness now.
851 		 */
852 		uncompile_pattern();
853 }
854 
855 #if HILITE_SEARCH
856 /*
857  * Find matching text which is currently on screen and highlight it.
858  */
859 	static void
860 hilite_screen()
861 {
862 	struct scrpos scrpos;
863 
864 	get_scrpos(&scrpos);
865 	if (scrpos.pos == NULL_POSITION)
866 		return;
867 	prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
868 	repaint_hilite(1);
869 }
870 
871 /*
872  * Change highlighting parameters.
873  */
874 	public void
875 chg_hilite()
876 {
877 	/*
878 	 * Erase any highlights currently on screen.
879 	 */
880 	clr_hilite();
881 	hide_hilite = 0;
882 
883 	if (hilite_search == OPT_ONPLUS)
884 		/*
885 		 * Display highlights.
886 		 */
887 		hilite_screen();
888 }
889 #endif
890 
891 /*
892  * Figure out where to start a search.
893  */
894 	static POSITION
895 search_pos(search_type)
896 	int search_type;
897 {
898 	POSITION pos;
899 	int linenum;
900 
901 	if (empty_screen())
902 	{
903 		/*
904 		 * Start at the beginning (or end) of the file.
905 		 * The empty_screen() case is mainly for
906 		 * command line initiated searches;
907 		 * for example, "+/xyz" on the command line.
908 		 * Also for multi-file (SRCH_PAST_EOF) searches.
909 		 */
910 		if (search_type & SRCH_FORW)
911 		{
912 			return (ch_zero());
913 		} else
914 		{
915 			pos = ch_length();
916 			if (pos == NULL_POSITION)
917 			{
918 				(void) ch_end_seek();
919 				pos = ch_length();
920 			}
921 			return (pos);
922 		}
923 	}
924 	if (how_search)
925 	{
926 		/*
927 		 * Search does not include current screen.
928 		 */
929 		if (search_type & SRCH_FORW)
930 			linenum = BOTTOM_PLUS_ONE;
931 		else
932 			linenum = TOP;
933 		pos = position(linenum);
934 	} else
935 	{
936 		/*
937 		 * Search includes current screen.
938 		 * It starts at the jump target (if searching backwards),
939 		 * or at the jump target plus one (if forwards).
940 		 */
941 		linenum = adjsline(jump_sline);
942 		pos = position(linenum);
943 		if (search_type & SRCH_FORW)
944 		{
945 			pos = forw_raw_line(pos, (char **)NULL);
946 			while (pos == NULL_POSITION)
947 			{
948 				if (++linenum >= sc_height)
949 					break;
950 				pos = position(linenum);
951 			}
952 		} else
953 		{
954 			while (pos == NULL_POSITION)
955 			{
956 				if (--linenum < 0)
957 					break;
958 				pos = position(linenum);
959 			}
960 		}
961 	}
962 	return (pos);
963 }
964 
965 /*
966  * Search a subset of the file, specified by start/end position.
967  */
968 	static int
969 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
970 	POSITION pos;
971 	POSITION endpos;
972 	int search_type;
973 	int matches;
974 	int maxlines;
975 	POSITION *plinepos;
976 	POSITION *pendpos;
977 {
978 	char *line;
979 	LINENUM linenum;
980 	char *sp, *ep;
981 	int line_match;
982 	int cvt_ops;
983 	POSITION linepos, oldpos;
984 
985 	linenum = find_linenum(pos);
986 	oldpos = pos;
987 	for (;;)
988 	{
989 		/*
990 		 * Get lines until we find a matching one or until
991 		 * we hit end-of-file (or beginning-of-file if we're
992 		 * going backwards), or until we hit the end position.
993 		 */
994 		if (ABORT_SIGS())
995 		{
996 			/*
997 			 * A signal aborts the search.
998 			 */
999 			return (-1);
1000 		}
1001 
1002 		if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
1003 		{
1004 			/*
1005 			 * Reached end position without a match.
1006 			 */
1007 			if (pendpos != NULL)
1008 				*pendpos = pos;
1009 			return (matches);
1010 		}
1011 		if (maxlines > 0)
1012 			maxlines--;
1013 
1014 		if (search_type & SRCH_FORW)
1015 		{
1016 			/*
1017 			 * Read the next line, and save the
1018 			 * starting position of that line in linepos.
1019 			 */
1020 			linepos = pos;
1021 			pos = forw_raw_line(pos, &line);
1022 			if (linenum != 0)
1023 				linenum++;
1024 		} else
1025 		{
1026 			/*
1027 			 * Read the previous line and save the
1028 			 * starting position of that line in linepos.
1029 			 */
1030 			pos = back_raw_line(pos, &line);
1031 			linepos = pos;
1032 			if (linenum != 0)
1033 				linenum--;
1034 		}
1035 
1036 		if (pos == NULL_POSITION)
1037 		{
1038 			/*
1039 			 * Reached EOF/BOF without a match.
1040 			 */
1041 			if (pendpos != NULL)
1042 				*pendpos = oldpos;
1043 			return (matches);
1044 		}
1045 
1046 		/*
1047 		 * If we're using line numbers, we might as well
1048 		 * remember the information we have now (the position
1049 		 * and line number of the current line).
1050 		 * Don't do it for every line because it slows down
1051 		 * the search.  Remember the line number only if
1052 		 * we're "far" from the last place we remembered it.
1053 		 */
1054 		if (linenums && abs((int)(pos - oldpos)) > 1024)
1055 			add_lnum(linenum, pos);
1056 		oldpos = pos;
1057 
1058 		/*
1059 		 * If it's a caseless search, convert the line to lowercase.
1060 		 * If we're doing backspace processing, delete backspaces.
1061 		 */
1062 		cvt_ops = get_cvt_ops();
1063 		cvt_text(line, line, cvt_ops);
1064 
1065 		/*
1066 		 * Test the next line to see if we have a match.
1067 		 * We are successful if we either want a match and got one,
1068 		 * or if we want a non-match and got one.
1069 		 */
1070 		line_match = match_pattern(line, &sp, &ep, 0);
1071 		line_match = (!(search_type & SRCH_NO_MATCH) && line_match) ||
1072 				((search_type & SRCH_NO_MATCH) && !line_match);
1073 		if (!line_match)
1074 			continue;
1075 		/*
1076 		 * Got a match.
1077 		 */
1078 		if (search_type & SRCH_FIND_ALL)
1079 		{
1080 #if HILITE_SEARCH
1081 			/*
1082 			 * We are supposed to find all matches in the range.
1083 			 * Just add the matches in this line to the
1084 			 * hilite list and keep searching.
1085 			 */
1086 			if (line_match)
1087 				hilite_line(linepos, line, sp, ep, cvt_ops);
1088 #endif
1089 		} else if (--matches <= 0)
1090 		{
1091 			/*
1092 			 * Found the one match we're looking for.
1093 			 * Return it.
1094 			 */
1095 #if HILITE_SEARCH
1096 			if (hilite_search == OPT_ON)
1097 			{
1098 				/*
1099 				 * Clear the hilite list and add only
1100 				 * the matches in this one line.
1101 				 */
1102 				clr_hilite();
1103 				if (line_match)
1104 					hilite_line(linepos, line, sp, ep, cvt_ops);
1105 			}
1106 #endif
1107 			if (plinepos != NULL)
1108 				*plinepos = linepos;
1109 			return (0);
1110 		}
1111 	}
1112 }
1113 
1114 /*
1115  * Search for the n-th occurrence of a specified pattern,
1116  * either forward or backward.
1117  * Return the number of matches not yet found in this file
1118  * (that is, n minus the number of matches found).
1119  * Return -1 if the search should be aborted.
1120  * Caller may continue the search in another file
1121  * if less than n matches are found in this file.
1122  */
1123 	public int
1124 search(search_type, pattern, n)
1125 	int search_type;
1126 	char *pattern;
1127 	int n;
1128 {
1129 	POSITION pos;
1130 	int ucase;
1131 
1132 	if (pattern == NULL || *pattern == '\0')
1133 	{
1134 		/*
1135 		 * A null pattern means use the previously compiled pattern.
1136 		 */
1137 		if (!prev_pattern())
1138 		{
1139 			error("No previous regular expression", NULL_PARG);
1140 			return (-1);
1141 		}
1142 		if ((search_type & SRCH_NO_REGEX) !=
1143 		    (last_search_type & SRCH_NO_REGEX))
1144 		{
1145 			error("Please re-enter search pattern", NULL_PARG);
1146 			return -1;
1147 		}
1148 #if HILITE_SEARCH
1149 		if (hilite_search == OPT_ON)
1150 		{
1151 			/*
1152 			 * Erase the highlights currently on screen.
1153 			 * If the search fails, we'll redisplay them later.
1154 			 */
1155 			repaint_hilite(0);
1156 		}
1157 		if (hilite_search == OPT_ONPLUS && hide_hilite)
1158 		{
1159 			/*
1160 			 * Highlight any matches currently on screen,
1161 			 * before we actually start the search.
1162 			 */
1163 			hide_hilite = 0;
1164 			hilite_screen();
1165 		}
1166 		hide_hilite = 0;
1167 #endif
1168 	} else
1169 	{
1170 		/*
1171 		 * Compile the pattern.
1172 		 */
1173 		ucase = is_ucase(pattern);
1174 		if (caseless == OPT_ONPLUS)
1175 			cvt_text(pattern, pattern, CVT_TO_LC);
1176 		if (compile_pattern(pattern, search_type) < 0)
1177 			return (-1);
1178 		/*
1179 		 * Ignore case if -I is set OR
1180 		 * -i is set AND the pattern is all lowercase.
1181 		 */
1182 		is_ucase_pattern = ucase;
1183 		if (is_ucase_pattern && caseless != OPT_ONPLUS)
1184 			is_caseless = 0;
1185 		else
1186 			is_caseless = caseless;
1187 #if HILITE_SEARCH
1188 		if (hilite_search)
1189 		{
1190 			/*
1191 			 * Erase the highlights currently on screen.
1192 			 * Also permanently delete them from the hilite list.
1193 			 */
1194 			repaint_hilite(0);
1195 			hide_hilite = 0;
1196 			clr_hilite();
1197 		}
1198 		if (hilite_search == OPT_ONPLUS)
1199 		{
1200 			/*
1201 			 * Highlight any matches currently on screen,
1202 			 * before we actually start the search.
1203 			 */
1204 			hilite_screen();
1205 		}
1206 #endif
1207 	}
1208 
1209 	/*
1210 	 * Figure out where to start the search.
1211 	 */
1212 	pos = search_pos(search_type);
1213 	if (pos == NULL_POSITION)
1214 	{
1215 		/*
1216 		 * Can't find anyplace to start searching from.
1217 		 */
1218 		if (search_type & SRCH_PAST_EOF)
1219 			return (n);
1220 		/* repaint(); -- why was this here? */
1221 		error("Nothing to search", NULL_PARG);
1222 		return (-1);
1223 	}
1224 
1225 	n = search_range(pos, NULL_POSITION, search_type, n, -1,
1226 			&pos, (POSITION*)NULL);
1227 	if (n != 0)
1228 	{
1229 		/*
1230 		 * Search was unsuccessful.
1231 		 */
1232 #if HILITE_SEARCH
1233 		if (hilite_search == OPT_ON && n > 0)
1234 			/*
1235 			 * Redisplay old hilites.
1236 			 */
1237 			repaint_hilite(1);
1238 #endif
1239 		return (n);
1240 	}
1241 
1242 	if (!(search_type & SRCH_NO_MOVE))
1243 	{
1244 		/*
1245 		 * Go to the matching line.
1246 		 */
1247 		jump_loc(pos, jump_sline);
1248 	}
1249 
1250 #if HILITE_SEARCH
1251 	if (hilite_search == OPT_ON)
1252 		/*
1253 		 * Display new hilites in the matching line.
1254 		 */
1255 		repaint_hilite(1);
1256 #endif
1257 	return (0);
1258 }
1259 
1260 
1261 #if HILITE_SEARCH
1262 /*
1263  * Prepare hilites in a given range of the file.
1264  *
1265  * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1266  * of the file that has been "prepared"; that is, scanned for matches for
1267  * the current search pattern, and hilites have been created for such matches.
1268  * If prep_startpos == NULL_POSITION, the prep region is empty.
1269  * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1270  * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1271  */
1272 	public void
1273 prep_hilite(spos, epos, maxlines)
1274 	POSITION spos;
1275 	POSITION epos;
1276 	int maxlines;
1277 {
1278 	POSITION nprep_startpos = prep_startpos;
1279 	POSITION nprep_endpos = prep_endpos;
1280 	POSITION new_epos;
1281 	POSITION max_epos;
1282 	int result;
1283 	int i;
1284 /*
1285  * Search beyond where we're asked to search, so the prep region covers
1286  * more than we need.  Do one big search instead of a bunch of small ones.
1287  */
1288 #define	SEARCH_MORE (3*size_linebuf)
1289 
1290 	if (!prev_pattern())
1291 		return;
1292 
1293 	/*
1294 	 * If we're limited to a max number of lines, figure out the
1295 	 * file position we should stop at.
1296 	 */
1297 	if (maxlines < 0)
1298 		max_epos = NULL_POSITION;
1299 	else
1300 	{
1301 		max_epos = spos;
1302 		for (i = 0;  i < maxlines;  i++)
1303 			max_epos = forw_raw_line(max_epos, (char **)NULL);
1304 	}
1305 
1306 	/*
1307 	 * Find two ranges:
1308 	 * The range that we need to search (spos,epos); and the range that
1309 	 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1310 	 */
1311 
1312 	if (prep_startpos == NULL_POSITION ||
1313 	    (epos != NULL_POSITION && epos < prep_startpos) ||
1314 	    spos > prep_endpos)
1315 	{
1316 		/*
1317 		 * New range is not contiguous with old prep region.
1318 		 * Discard the old prep region and start a new one.
1319 		 */
1320 		clr_hilite();
1321 		if (epos != NULL_POSITION)
1322 			epos += SEARCH_MORE;
1323 		nprep_startpos = spos;
1324 	} else
1325 	{
1326 		/*
1327 		 * New range partially or completely overlaps old prep region.
1328 		 */
1329 		if (epos == NULL_POSITION)
1330 		{
1331 			/*
1332 			 * New range goes to end of file.
1333 			 */
1334 			;
1335 		} else if (epos > prep_endpos)
1336 		{
1337 			/*
1338 			 * New range ends after old prep region.
1339 			 * Extend prep region to end at end of new range.
1340 			 */
1341 			epos += SEARCH_MORE;
1342 		} else /* (epos <= prep_endpos) */
1343 		{
1344 			/*
1345 			 * New range ends within old prep region.
1346 			 * Truncate search to end at start of old prep region.
1347 			 */
1348 			epos = prep_startpos;
1349 		}
1350 
1351 		if (spos < prep_startpos)
1352 		{
1353 			/*
1354 			 * New range starts before old prep region.
1355 			 * Extend old prep region backwards to start at
1356 			 * start of new range.
1357 			 */
1358 			if (spos < SEARCH_MORE)
1359 				spos = 0;
1360 			else
1361 				spos -= SEARCH_MORE;
1362 			nprep_startpos = spos;
1363 		} else /* (spos >= prep_startpos) */
1364 		{
1365 			/*
1366 			 * New range starts within or after old prep region.
1367 			 * Trim search to start at end of old prep region.
1368 			 */
1369 			spos = prep_endpos;
1370 		}
1371 	}
1372 
1373 	if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1374 	    epos > max_epos)
1375 		/*
1376 		 * Don't go past the max position we're allowed.
1377 		 */
1378 		epos = max_epos;
1379 
1380 	if (epos == NULL_POSITION || epos > spos)
1381 	{
1382 		result = search_range(spos, epos, SRCH_FORW|SRCH_FIND_ALL, 0,
1383 				maxlines, (POSITION*)NULL, &new_epos);
1384 		if (result < 0)
1385 			return;
1386 		if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1387 			nprep_endpos = new_epos;
1388 	}
1389 	prep_startpos = nprep_startpos;
1390 	prep_endpos = nprep_endpos;
1391 }
1392 #endif
1393 
1394 /*
1395  * Simple pattern matching function.
1396  * It supports no metacharacters like *, etc.
1397  */
1398 	static int
1399 match(pattern, buf, pfound, pend)
1400 	char *pattern, *buf;
1401 	char **pfound, **pend;
1402 {
1403 	register char *pp, *lp;
1404 
1405 	for ( ;  *buf != '\0';  buf++)
1406 	{
1407 		for (pp = pattern, lp = buf;  *pp == *lp;  pp++, lp++)
1408 			if (*pp == '\0' || *lp == '\0')
1409 				break;
1410 		if (*pp == '\0')
1411 		{
1412 			if (pfound != NULL)
1413 				*pfound = buf;
1414 			if (pend != NULL)
1415 				*pend = lp;
1416 			return (1);
1417 		}
1418 	}
1419 	return (0);
1420 }
1421 
1422 #if HAVE_V8_REGCOMP
1423 /*
1424  * This function is called by the V8 regcomp to report
1425  * errors in regular expressions.
1426  */
1427 	void
1428 regerror(s)
1429 	char *s;
1430 {
1431 	PARG parg;
1432 
1433 	parg.p_string = s;
1434 	error("%s", &parg);
1435 }
1436 #endif
1437 
1438