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