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