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