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