1 /* $NetBSD: search.c,v 1.5 2023/10/06 05:49:49 simonb Exp $ */
2
3 /*
4 * Copyright (C) 1984-2023 Mark Nudelman
5 *
6 * You may distribute under the terms of either the GNU General Public
7 * License or the Less License, as specified in the README file.
8 *
9 * For more information, see the README file.
10 */
11
12
13 /*
14 * Routines to search a file for a pattern.
15 */
16
17 #include "less.h"
18 #include "position.h"
19 #include "charset.h"
20
21 #define MINPOS(a,b) (((a) < (b)) ? (a) : (b))
22 #define MAXPOS(a,b) (((a) > (b)) ? (a) : (b))
23
24 extern int sigs;
25 extern int how_search;
26 extern int caseless;
27 extern int linenums;
28 extern int sc_height;
29 extern int jump_sline;
30 extern int bs_mode;
31 extern int proc_backspace;
32 extern int proc_return;
33 extern int ctldisp;
34 extern int status_col;
35 extern void *ml_search;
36 extern POSITION start_attnpos;
37 extern POSITION end_attnpos;
38 extern int utf_mode;
39 extern int screen_trashed;
40 extern int sc_width;
41 extern int sc_height;
42 extern int hshift;
43 extern int nosearch_headers;
44 extern int header_lines;
45 extern int header_cols;
46 #if HILITE_SEARCH
47 extern int hilite_search;
48 extern int size_linebuf;
49 extern int squished;
50 extern int can_goto_line;
51 static int hide_hilite;
52 static POSITION prep_startpos;
53 static POSITION prep_endpos;
54 extern POSITION xxpos;
55
56 /*
57 * Structures for maintaining a set of ranges for hilites and filtered-out
58 * lines. Each range is stored as a node within a red-black tree, and we
59 * try to extend existing ranges (without creating overlaps) rather than
60 * create new nodes if possible. We remember the last node found by a
61 * search for constant-time lookup if the next search is near enough to
62 * the previous. To aid that, we overlay a secondary doubly-linked list
63 * on top of the red-black tree so we can find the preceding/succeeding
64 * nodes also in constant time.
65 *
66 * Each node is allocated from a series of pools, each pool double the size
67 * of the previous (for amortised constant time allocation). Since our only
68 * tree operations are clear and node insertion, not node removal, we don't
69 * need to maintain a usage bitmap or freelist and can just return nodes
70 * from the pool in-order until capacity is reached.
71 */
72 struct hilite
73 {
74 POSITION hl_startpos;
75 POSITION hl_endpos;
76 int hl_attr;
77 };
78 struct hilite_node
79 {
80 struct hilite_node *parent;
81 struct hilite_node *left;
82 struct hilite_node *right;
83 struct hilite_node *prev;
84 struct hilite_node *next;
85 int red;
86 struct hilite r;
87 };
88 struct hilite_storage
89 {
90 int capacity;
91 int used;
92 struct hilite_storage *next;
93 struct hilite_node *nodes;
94 };
95 struct hilite_tree
96 {
97 struct hilite_storage *first;
98 struct hilite_storage *current;
99 struct hilite_node *root;
100 struct hilite_node *lookaside;
101 };
102 #define HILITE_INITIALIZER() { NULL, NULL, NULL, NULL }
103 #define HILITE_LOOKASIDE_STEPS 2
104
105 static struct hilite_tree hilite_anchor = HILITE_INITIALIZER();
106 static struct hilite_tree filter_anchor = HILITE_INITIALIZER();
107 static struct pattern_info *filter_infos = NULL;
108
109 #endif
110
111 /*
112 * These are the static variables that represent the "remembered"
113 * search pattern and filter pattern.
114 */
115 struct pattern_info {
116 PATTERN_TYPE compiled;
117 char* text;
118 int search_type;
119 int is_ucase_pattern;
120 struct pattern_info *next;
121 };
122
123 #if NO_REGEX
124 #define info_compiled(info) ((void*)0)
125 #else
126 #define info_compiled(info) ((info)->compiled)
127 #endif
128
129 static struct pattern_info search_info;
130 public int is_caseless;
131
132 /*
133 * Are there any uppercase letters in this string?
134 */
is_ucase(char * str)135 static int is_ucase(char *str)
136 {
137 char *str_end = str + strlen(str);
138 LWCHAR ch;
139
140 while (str < str_end)
141 {
142 ch = step_char(&str, +1, str_end);
143 if (IS_UPPER(ch))
144 return (1);
145 }
146 return (0);
147 }
148
149 /*
150 * Discard a saved pattern.
151 */
clear_pattern(struct pattern_info * info)152 static void clear_pattern(struct pattern_info *info)
153 {
154 if (info->text != NULL)
155 free(info->text);
156 info->text = NULL;
157 #if !NO_REGEX
158 uncompile_pattern(&info->compiled);
159 #endif
160 }
161
162 /*
163 * Compile and save a search pattern.
164 */
set_pattern(struct pattern_info * info,char * pattern,int search_type,int show_error)165 static int set_pattern(struct pattern_info *info, char *pattern, int search_type, int show_error)
166 {
167 /*
168 * Ignore case if -I is set OR
169 * -i is set AND the pattern is all lowercase.
170 */
171 info->is_ucase_pattern = (pattern == NULL) ? FALSE : is_ucase(pattern);
172 is_caseless = (info->is_ucase_pattern && caseless != OPT_ONPLUS) ? 0 : caseless;
173 #if !NO_REGEX
174 if (pattern == NULL)
175 SET_NULL_PATTERN(info->compiled);
176 else if (compile_pattern(pattern, search_type, show_error, &info->compiled) < 0)
177 return -1;
178 #endif
179 /* Pattern compiled successfully; save the text too. */
180 if (info->text != NULL)
181 free(info->text);
182 info->text = NULL;
183 if (pattern != NULL)
184 {
185 info->text = (char *) ecalloc(1, strlen(pattern)+1);
186 strcpy(info->text, pattern);
187 }
188 info->search_type = search_type;
189 return 0;
190 }
191
192 /*
193 * Initialize saved pattern to nothing.
194 */
init_pattern(struct pattern_info * info)195 static void init_pattern(struct pattern_info *info)
196 {
197 SET_NULL_PATTERN(info->compiled);
198 info->text = NULL;
199 info->search_type = 0;
200 info->next = NULL;
201 }
202
203 /*
204 * Initialize search variables.
205 */
init_search(void)206 public void init_search(void)
207 {
208 init_pattern(&search_info);
209 }
210
211 /*
212 * Determine which text conversions to perform before pattern matching.
213 */
get_cvt_ops(int search_type)214 static int get_cvt_ops(int search_type)
215 {
216 int ops = 0;
217
218 if (is_caseless && (!re_handles_caseless || (search_type & SRCH_NO_REGEX)))
219 ops |= CVT_TO_LC;
220 if (proc_backspace == OPT_ON || (bs_mode == BS_SPECIAL && proc_backspace == OPT_OFF))
221 ops |= CVT_BS;
222 if (proc_return == OPT_ON || (bs_mode != BS_CONTROL && proc_backspace == OPT_OFF))
223 ops |= CVT_CRLF;
224 if (ctldisp == OPT_ONPLUS)
225 ops |= CVT_ANSI;
226 return (ops);
227 }
228
229 /*
230 * Is there a previous (remembered) search pattern?
231 */
prev_pattern(struct pattern_info * info)232 static int prev_pattern(struct pattern_info *info)
233 {
234 #if !NO_REGEX
235 if ((info->search_type & SRCH_NO_REGEX) == 0)
236 return (!is_null_pattern(info->compiled));
237 #endif
238 return (info->text != NULL);
239 }
240
241 #if HILITE_SEARCH
242 /*
243 * Repaint the hilites currently displayed on the screen.
244 * Repaint each line which contains highlighted text.
245 * If on==0, force all hilites off.
246 */
repaint_hilite(int on)247 public void repaint_hilite(int on)
248 {
249 int sindex;
250 POSITION pos;
251 int save_hide_hilite;
252
253 if (squished)
254 repaint();
255
256 save_hide_hilite = hide_hilite;
257 if (!on)
258 {
259 if (hide_hilite)
260 return;
261 hide_hilite = 1;
262 }
263
264 if (!can_goto_line)
265 {
266 repaint();
267 hide_hilite = save_hide_hilite;
268 return;
269 }
270
271 for (sindex = TOP; sindex < TOP + sc_height-1; sindex++)
272 {
273 pos = position(sindex);
274 if (pos == NULL_POSITION)
275 continue;
276 (void) forw_line(pos);
277 goto_line(sindex);
278 clear_eol();
279 put_line();
280 }
281 overlay_header();
282 lower_left();
283 hide_hilite = save_hide_hilite;
284 }
285 #endif
286
287 /*
288 * Clear the attn hilite.
289 */
clear_attn(void)290 public void clear_attn(void)
291 {
292 #if HILITE_SEARCH
293 int sindex;
294 POSITION old_start_attnpos;
295 POSITION old_end_attnpos;
296 POSITION pos;
297 POSITION epos;
298 int moved = 0;
299
300 if (start_attnpos == NULL_POSITION)
301 return;
302 old_start_attnpos = start_attnpos;
303 old_end_attnpos = end_attnpos;
304 start_attnpos = end_attnpos = NULL_POSITION;
305
306 if (!can_goto_line)
307 {
308 repaint();
309 return;
310 }
311 if (squished)
312 repaint();
313
314 for (sindex = TOP; sindex < TOP + sc_height-1; sindex++)
315 {
316 pos = position(sindex);
317 if (pos == NULL_POSITION)
318 continue;
319 epos = position(sindex+1);
320 if (pos <= old_end_attnpos &&
321 (epos == NULL_POSITION || epos > old_start_attnpos))
322 {
323 (void) forw_line(pos);
324 goto_line(sindex);
325 clear_eol();
326 put_line();
327 moved = 1;
328 }
329 }
330 if (overlay_header())
331 moved = 1;
332 if (moved)
333 lower_left();
334 #endif
335 }
336
337 /*
338 * Toggle or clear search string highlighting.
339 */
undo_search(int clear)340 public void undo_search(int clear)
341 {
342 clear_pattern(&search_info);
343 #if HILITE_SEARCH
344 if (clear)
345 {
346 clr_hilite();
347 } else
348 {
349 if (hilite_anchor.first == NULL)
350 {
351 error("No previous regular expression", NULL_PARG);
352 return;
353 }
354 hide_hilite = !hide_hilite;
355 }
356 repaint_hilite(1);
357 #endif
358 }
359
360 #if HILITE_SEARCH
361 /*
362 * Clear the hilite list.
363 */
clr_hlist(struct hilite_tree * anchor)364 public void clr_hlist(struct hilite_tree *anchor)
365 {
366 struct hilite_storage *hls;
367 struct hilite_storage *nexthls;
368
369 for (hls = anchor->first; hls != NULL; hls = nexthls)
370 {
371 nexthls = hls->next;
372 free((void*)hls->nodes);
373 free((void*)hls);
374 }
375 anchor->first = NULL;
376 anchor->current = NULL;
377 anchor->root = NULL;
378
379 anchor->lookaside = NULL;
380
381 prep_startpos = prep_endpos = NULL_POSITION;
382 }
383
clr_hilite(void)384 public void clr_hilite(void)
385 {
386 clr_hlist(&hilite_anchor);
387 }
388
clr_filter(void)389 public void clr_filter(void)
390 {
391 clr_hlist(&filter_anchor);
392 }
393
394 /*
395 * Find the node covering pos, or the node after it if no node covers it,
396 * or return NULL if pos is after the last range. Remember the found node,
397 * to speed up subsequent searches for the same or similar positions (if
398 * we return NULL, remember the last node.)
399 */
hlist_find(struct hilite_tree * anchor,POSITION pos)400 static struct hilite_node* hlist_find(struct hilite_tree *anchor, POSITION pos)
401 {
402 struct hilite_node *n, *m;
403
404 if (anchor->lookaside)
405 {
406 int steps = 0;
407 int hit = 0;
408
409 n = anchor->lookaside;
410
411 for (;;)
412 {
413 if (pos < n->r.hl_endpos)
414 {
415 if (n->prev == NULL || pos >= n->prev->r.hl_endpos)
416 {
417 hit = 1;
418 break;
419 }
420 } else if (n->next == NULL)
421 {
422 n = NULL;
423 hit = 1;
424 break;
425 }
426
427 /*
428 * If we don't find the right node within a small
429 * distance, don't keep doing a linear search!
430 */
431 if (steps >= HILITE_LOOKASIDE_STEPS)
432 break;
433 steps++;
434
435 if (pos < n->r.hl_endpos)
436 anchor->lookaside = n = n->prev;
437 else
438 anchor->lookaside = n = n->next;
439 }
440
441 if (hit)
442 return n;
443 }
444
445 n = anchor->root;
446 m = NULL;
447
448 while (n != NULL)
449 {
450 if (pos < n->r.hl_startpos)
451 {
452 if (n->left != NULL)
453 {
454 m = n;
455 n = n->left;
456 continue;
457 }
458 break;
459 }
460 if (pos >= n->r.hl_endpos)
461 {
462 if (n->right != NULL)
463 {
464 n = n->right;
465 continue;
466 }
467 if (m != NULL)
468 {
469 n = m;
470 } else
471 {
472 m = n;
473 n = NULL;
474 }
475 }
476 break;
477 }
478
479 if (n != NULL)
480 anchor->lookaside = n;
481 else if (m != NULL)
482 anchor->lookaside = m;
483
484 return n;
485 }
486
487 /*
488 * Should any characters in a specified range be highlighted?
489 */
hilited_range_attr(POSITION pos,POSITION epos)490 static int hilited_range_attr(POSITION pos, POSITION epos)
491 {
492 struct hilite_node *n = hlist_find(&hilite_anchor, pos);
493 if (n == NULL)
494 return 0;
495 if (epos != NULL_POSITION && epos <= n->r.hl_startpos)
496 return 0;
497 return n->r.hl_attr;
498 }
499
500 /*
501 * Is a line "filtered" -- that is, should it be hidden?
502 */
is_filtered(POSITION pos)503 public int is_filtered(POSITION pos)
504 {
505 struct hilite_node *n;
506
507 if (ch_getflags() & CH_HELPFILE)
508 return (0);
509
510 n = hlist_find(&filter_anchor, pos);
511 return (n != NULL && pos >= n->r.hl_startpos);
512 }
513
514 /*
515 * If pos is hidden, return the next position which isn't, otherwise
516 * just return pos.
517 */
next_unfiltered(POSITION pos)518 public POSITION next_unfiltered(POSITION pos)
519 {
520 struct hilite_node *n;
521
522 if (ch_getflags() & CH_HELPFILE)
523 return (pos);
524
525 n = hlist_find(&filter_anchor, pos);
526 while (n != NULL && pos >= n->r.hl_startpos)
527 {
528 pos = n->r.hl_endpos;
529 n = n->next;
530 }
531 return (pos);
532 }
533
534 /*
535 * If pos is hidden, return the previous position which isn't or 0 if
536 * we're filtered right to the beginning, otherwise just return pos.
537 */
prev_unfiltered(POSITION pos)538 public POSITION prev_unfiltered(POSITION pos)
539 {
540 struct hilite_node *n;
541
542 if (ch_getflags() & CH_HELPFILE)
543 return (pos);
544
545 n = hlist_find(&filter_anchor, pos);
546 while (n != NULL && pos >= n->r.hl_startpos)
547 {
548 pos = n->r.hl_startpos;
549 if (pos == 0)
550 break;
551 pos--;
552 n = n->prev;
553 }
554 return (pos);
555 }
556
557
558 /*
559 * Should any characters in a specified range be highlighted?
560 * If nohide is nonzero, don't consider hide_hilite.
561 */
is_hilited_attr(POSITION pos,POSITION epos,int nohide,int * p_matches)562 public int is_hilited_attr(POSITION pos, POSITION epos, int nohide, int *p_matches)
563 {
564 int attr;
565
566 if (p_matches != NULL)
567 *p_matches = 0;
568
569 if (!status_col &&
570 start_attnpos != NULL_POSITION &&
571 pos <= end_attnpos &&
572 (epos == NULL_POSITION || epos >= start_attnpos))
573 /*
574 * The attn line overlaps this range.
575 */
576 return (AT_HILITE|AT_COLOR_ATTN);
577
578 attr = hilited_range_attr(pos, epos);
579 if (attr == 0)
580 return (0);
581
582 if (p_matches == NULL)
583 /*
584 * Kinda kludgy way to recognize that caller is checking for
585 * hilite in status column. In this case we want to return
586 * hilite status even if hiliting is disabled or hidden.
587 */
588 return (attr);
589
590 /*
591 * Report matches, even if we're hiding highlights.
592 */
593 *p_matches = 1;
594
595 if (hilite_search == 0)
596 /*
597 * Not doing highlighting.
598 */
599 return (0);
600
601 if (!nohide && hide_hilite)
602 /*
603 * Highlighting is hidden.
604 */
605 return (0);
606
607 return (attr);
608 }
609
610 /*
611 * Tree node storage: get the current block of nodes if it has spare
612 * capacity, or create a new one if not.
613 */
hlist_getstorage(struct hilite_tree * anchor)614 static struct hilite_storage * hlist_getstorage(struct hilite_tree *anchor)
615 {
616 int capacity = 1;
617 struct hilite_storage *s;
618
619 if (anchor->current)
620 {
621 if (anchor->current->used < anchor->current->capacity)
622 return anchor->current;
623 capacity = anchor->current->capacity * 2;
624 }
625
626 s = (struct hilite_storage *) ecalloc(1, sizeof(struct hilite_storage));
627 s->nodes = (struct hilite_node *) ecalloc(capacity, sizeof(struct hilite_node));
628 s->capacity = capacity;
629 s->used = 0;
630 s->next = NULL;
631 if (anchor->current)
632 anchor->current->next = s;
633 else
634 anchor->first = s;
635 anchor->current = s;
636 return s;
637 }
638
639 /*
640 * Tree node storage: retrieve a new empty node to be inserted into the
641 * tree.
642 */
hlist_getnode(struct hilite_tree * anchor)643 static struct hilite_node * hlist_getnode(struct hilite_tree *anchor)
644 {
645 struct hilite_storage *s = hlist_getstorage(anchor);
646 return &s->nodes[s->used++];
647 }
648
649 /*
650 * Rotate the tree left around a pivot node.
651 */
hlist_rotate_left(struct hilite_tree * anchor,struct hilite_node * n)652 static void hlist_rotate_left(struct hilite_tree *anchor, struct hilite_node *n)
653 {
654 struct hilite_node *np = n->parent;
655 struct hilite_node *nr = n->right;
656 struct hilite_node *nrl = n->right->left;
657
658 if (np != NULL)
659 {
660 if (n == np->left)
661 np->left = nr;
662 else
663 np->right = nr;
664 } else
665 {
666 anchor->root = nr;
667 }
668 nr->left = n;
669 n->right = nrl;
670
671 nr->parent = np;
672 n->parent = nr;
673 if (nrl != NULL)
674 nrl->parent = n;
675 }
676
677 /*
678 * Rotate the tree right around a pivot node.
679 */
hlist_rotate_right(struct hilite_tree * anchor,struct hilite_node * n)680 static void hlist_rotate_right(struct hilite_tree *anchor, struct hilite_node *n)
681 {
682 struct hilite_node *np = n->parent;
683 struct hilite_node *nl = n->left;
684 struct hilite_node *nlr = n->left->right;
685
686 if (np != NULL)
687 {
688 if (n == np->right)
689 np->right = nl;
690 else
691 np->left = nl;
692 } else
693 {
694 anchor->root = nl;
695 }
696 nl->right = n;
697 n->left = nlr;
698
699 nl->parent = np;
700 n->parent = nl;
701 if (nlr != NULL)
702 nlr->parent = n;
703 }
704
705
706 /*
707 * Add a new hilite to a hilite list.
708 */
add_hilite(struct hilite_tree * anchor,struct hilite * hl)709 static void add_hilite(struct hilite_tree *anchor, struct hilite *hl)
710 {
711 struct hilite_node *p, *n, *u;
712
713 /* Ignore empty ranges. */
714 if (hl->hl_startpos >= hl->hl_endpos)
715 return;
716
717 p = anchor->root;
718
719 /* Inserting the very first node is trivial. */
720 if (p == NULL)
721 {
722 n = hlist_getnode(anchor);
723 n->r = *hl;
724 anchor->root = n;
725 anchor->lookaside = n;
726 return;
727 }
728
729 /*
730 * Find our insertion point. If we come across any overlapping
731 * or adjoining existing ranges, shrink our range and discard
732 * if it become empty.
733 */
734 for (;;)
735 {
736 if (hl->hl_startpos < p->r.hl_startpos)
737 {
738 if (hl->hl_endpos > p->r.hl_startpos && hl->hl_attr == p->r.hl_attr)
739 hl->hl_endpos = p->r.hl_startpos;
740 if (p->left != NULL)
741 {
742 p = p->left;
743 continue;
744 }
745 break;
746 }
747 if (hl->hl_startpos < p->r.hl_endpos && hl->hl_attr == p->r.hl_attr) {
748 hl->hl_startpos = p->r.hl_endpos;
749 if (hl->hl_startpos >= hl->hl_endpos)
750 return;
751 }
752 if (p->right != NULL)
753 {
754 p = p->right;
755 continue;
756 }
757 break;
758 }
759
760 /*
761 * Now we're at the right leaf, again check for contiguous ranges
762 * and extend the existing node if possible to avoid the
763 * insertion. Otherwise insert a new node at the leaf.
764 */
765 if (hl->hl_startpos < p->r.hl_startpos) {
766 if (hl->hl_attr == p->r.hl_attr)
767 {
768 if (hl->hl_endpos == p->r.hl_startpos)
769 {
770 p->r.hl_startpos = hl->hl_startpos;
771 return;
772 }
773 if (p->prev != NULL && p->prev->r.hl_endpos == hl->hl_startpos)
774 {
775 p->prev->r.hl_endpos = hl->hl_endpos;
776 return;
777 }
778 }
779 p->left = n = hlist_getnode(anchor);
780 n->next = p;
781 if (p->prev != NULL)
782 {
783 n->prev = p->prev;
784 p->prev->next = n;
785 }
786 p->prev = n;
787 } else {
788 if (hl->hl_attr == p->r.hl_attr)
789 {
790 if (p->r.hl_endpos == hl->hl_startpos)
791 {
792 p->r.hl_endpos = hl->hl_endpos;
793 return;
794 }
795 if (p->next != NULL && hl->hl_endpos == p->next->r.hl_startpos) {
796 p->next->r.hl_startpos = hl->hl_startpos;
797 return;
798 }
799 }
800 p->right = n = hlist_getnode(anchor);
801 n->prev = p;
802 if (p->next != NULL)
803 {
804 n->next = p->next;
805 p->next->prev = n;
806 }
807 p->next = n;
808 }
809 n->parent = p;
810 n->red = 1;
811 n->r = *hl;
812
813 /*
814 * The tree is in the correct order and covers the right ranges
815 * now, but may have become unbalanced. Rebalance it using the
816 * standard red-black tree constraints and operations.
817 */
818 for (;;)
819 {
820 /* case 1 - current is root, root is always black */
821 if (n->parent == NULL)
822 {
823 n->red = 0;
824 break;
825 }
826
827 /* case 2 - parent is black, we can always be red */
828 if (!n->parent->red)
829 break;
830
831 /*
832 * constraint: because the root must be black, if our
833 * parent is red it cannot be the root therefore we must
834 * have a grandparent
835 */
836
837 /*
838 * case 3 - parent and uncle are red, repaint them black,
839 * the grandparent red, and start again at the grandparent.
840 */
841 u = n->parent->parent->left;
842 if (n->parent == u)
843 u = n->parent->parent->right;
844 if (u != NULL && u->red)
845 {
846 n->parent->red = 0;
847 u->red = 0;
848 n = n->parent->parent;
849 n->red = 1;
850 continue;
851 }
852
853 /*
854 * case 4 - parent is red but uncle is black, parent and
855 * grandparent on opposite sides. We need to start
856 * changing the structure now. This and case 5 will shorten
857 * our branch and lengthen the sibling, between them
858 * restoring balance.
859 */
860 if (n == n->parent->right &&
861 n->parent == n->parent->parent->left)
862 {
863 hlist_rotate_left(anchor, n->parent);
864 n = n->left;
865 } else if (n == n->parent->left &&
866 n->parent == n->parent->parent->right)
867 {
868 hlist_rotate_right(anchor, n->parent);
869 n = n->right;
870 }
871
872 /*
873 * case 5 - parent is red but uncle is black, parent and
874 * grandparent on same side
875 */
876 n->parent->red = 0;
877 n->parent->parent->red = 1;
878 if (n == n->parent->left)
879 hlist_rotate_right(anchor, n->parent->parent);
880 else
881 hlist_rotate_left(anchor, n->parent->parent);
882 break;
883 }
884 }
885
886 /*
887 * Highlight every character in a range of displayed characters.
888 */
create_hilites(POSITION linepos,char * line,char * sp,char * ep,int attr,int * chpos)889 static void create_hilites(POSITION linepos, char *line, char *sp, char *ep, int attr, int *chpos)
890 {
891 int start_index = sp - line;
892 int end_index = ep - line;
893 struct hilite hl;
894 int i;
895
896 /* Start the first hilite. */
897 hl.hl_startpos = linepos + chpos[start_index];
898 hl.hl_attr = attr;
899
900 /*
901 * Step through the displayed chars.
902 * If the source position (before cvt) of the char is one more
903 * than the source pos of the previous char (the usual case),
904 * just increase the size of the current hilite by one.
905 * Otherwise (there are backspaces or something involved),
906 * finish the current hilite and start a new one.
907 */
908 for (i = start_index+1; i <= end_index; i++)
909 {
910 if (chpos[i] != chpos[i-1] + 1 || i == end_index)
911 {
912 hl.hl_endpos = linepos + chpos[i-1] + 1;
913 add_hilite(&hilite_anchor, &hl);
914 /* Start new hilite unless this is the last char. */
915 if (i < end_index)
916 {
917 hl.hl_startpos = linepos + chpos[i];
918 }
919 }
920 }
921 }
922
923 /*
924 * Make a hilite for each string in a physical line which matches
925 * the current pattern.
926 * sp,ep delimit the first match already found.
927 */
hilite_line(POSITION linepos,char * line,int line_len,int * chpos,char ** sp,char ** ep,int nsp,int cvt_ops)928 static void hilite_line(POSITION linepos, char *line, int line_len, int *chpos, char **sp, char **ep, int nsp, int cvt_ops)
929 {
930 char *searchp;
931 char *line_end = line + line_len;
932
933 /*
934 * sp[0] and ep[0] delimit the first match in the line.
935 * Mark the corresponding file positions, then
936 * look for further matches and mark them.
937 * {{ This technique, of calling match_pattern on subsequent
938 * substrings of the line, may mark more than is correct
939 * if the pattern starts with "^". This bug is fixed
940 * for those regex functions that accept a notbol parameter
941 * (currently POSIX, PCRE and V8-with-regexec2). }}
942 * sp[i] and ep[i] for i>0 delimit subpattern matches.
943 * Color each of them with its unique color.
944 */
945 searchp = line;
946 do {
947 char *lep = sp[0];
948 int i;
949 if (sp[0] == NULL || ep[0] == NULL)
950 break;
951 for (i = 1; i < nsp; i++)
952 {
953 if (sp[i] == NULL || ep[i] == NULL)
954 break;
955 if (ep[i] > sp[i])
956 {
957 create_hilites(linepos, line, lep, sp[i],
958 AT_HILITE | AT_COLOR_SEARCH, chpos);
959 create_hilites(linepos, line, sp[i], ep[i],
960 AT_HILITE | AT_COLOR_SUBSEARCH(i), chpos);
961 lep = ep[i];
962 }
963 }
964 create_hilites(linepos, line, lep, ep[0],
965 AT_HILITE | AT_COLOR_SEARCH, chpos);
966
967 /*
968 * If we matched more than zero characters,
969 * move to the first char after the string we matched.
970 * If we matched zero, just move to the next char.
971 */
972 if (ep[0] > searchp)
973 searchp = ep[0];
974 else if (searchp != line_end)
975 searchp++;
976 else /* end of line */
977 break;
978 } while (match_pattern(info_compiled(&search_info), search_info.text,
979 searchp, line_end - searchp, sp, ep, nsp, 1, search_info.search_type));
980 }
981 #endif
982
983 #if HILITE_SEARCH
984 /*
985 * Find matching text which is currently on screen and highlight it.
986 */
hilite_screen(void)987 static void hilite_screen(void)
988 {
989 struct scrpos scrpos;
990
991 get_scrpos(&scrpos, TOP);
992 if (scrpos.pos == NULL_POSITION)
993 return;
994 prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
995 repaint_hilite(1);
996 }
997
998 /*
999 * Change highlighting parameters.
1000 */
chg_hilite(void)1001 public void chg_hilite(void)
1002 {
1003 /*
1004 * Erase any highlights currently on screen.
1005 */
1006 clr_hilite();
1007 hide_hilite = 0;
1008
1009 if (hilite_search == OPT_ONPLUS)
1010 /*
1011 * Display highlights.
1012 */
1013 hilite_screen();
1014 }
1015 #endif
1016
1017 /*
1018 * Figure out where to start a search.
1019 */
search_pos(int search_type)1020 static POSITION search_pos(int search_type)
1021 {
1022 POSITION pos;
1023 int sindex;
1024
1025 if (empty_screen())
1026 {
1027 /*
1028 * Start at the beginning (or end) of the file.
1029 * The empty_screen() case is mainly for
1030 * command line initiated searches;
1031 * for example, "+/xyz" on the command line.
1032 * Also for multi-file (SRCH_PAST_EOF) searches.
1033 */
1034 if (search_type & SRCH_FORW)
1035 {
1036 pos = ch_zero();
1037 } else
1038 {
1039 pos = ch_length();
1040 if (pos == NULL_POSITION)
1041 {
1042 (void) ch_end_seek();
1043 pos = ch_length();
1044 }
1045 }
1046 sindex = 0;
1047 } else
1048 {
1049 int add_one = 0;
1050
1051 if (how_search == OPT_ON)
1052 {
1053 /*
1054 * Search does not include current screen.
1055 */
1056 if (search_type & SRCH_FORW)
1057 sindex = sc_height-1; /* BOTTOM_PLUS_ONE */
1058 else
1059 sindex = 0; /* TOP */
1060 } else if (how_search == OPT_ONPLUS && !(search_type & SRCH_AFTER_TARGET))
1061 {
1062 /*
1063 * Search includes all of displayed screen.
1064 */
1065 if (search_type & SRCH_FORW)
1066 sindex = 0; /* TOP */
1067 else
1068 sindex = sc_height-1; /* BOTTOM_PLUS_ONE */
1069 } else
1070 {
1071 /*
1072 * Search includes the part of current screen beyond the jump target.
1073 * It starts at the jump target (if searching backwards),
1074 * or at the jump target plus one (if forwards).
1075 */
1076 sindex = sindex_from_sline(jump_sline);
1077 if (search_type & SRCH_FORW)
1078 add_one = 1;
1079 }
1080 pos = position(sindex);
1081 if (add_one)
1082 pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
1083 }
1084
1085 /*
1086 * If the line is empty, look around for a plausible starting place.
1087 */
1088 if (search_type & SRCH_FORW)
1089 {
1090 while (pos == NULL_POSITION)
1091 {
1092 if (++sindex >= sc_height)
1093 break;
1094 pos = position(sindex);
1095 }
1096 } else
1097 {
1098 while (pos == NULL_POSITION)
1099 {
1100 if (--sindex < 0)
1101 break;
1102 pos = position(sindex);
1103 }
1104 }
1105 return (pos);
1106 }
1107
1108 /*
1109 * Check to see if the line matches the filter pattern.
1110 * If so, add an entry to the filter list.
1111 */
1112 #if HILITE_SEARCH
matches_filters(POSITION pos,char * cline,int line_len,int * chpos,POSITION linepos,char ** sp,char ** ep,int nsp)1113 static int matches_filters(POSITION pos, char *cline, int line_len, int *chpos, POSITION linepos, char **sp, char **ep, int nsp)
1114 {
1115 struct pattern_info *filter;
1116
1117 for (filter = filter_infos; filter != NULL; filter = filter->next)
1118 {
1119 int line_filter = match_pattern(info_compiled(filter), filter->text,
1120 cline, line_len, sp, ep, nsp, 0, filter->search_type);
1121 if (line_filter)
1122 {
1123 struct hilite hl;
1124 hl.hl_startpos = linepos;
1125 hl.hl_endpos = pos;
1126 add_hilite(&filter_anchor, &hl);
1127 free(cline);
1128 free(chpos);
1129 return (1);
1130 }
1131 }
1132 return (0);
1133 }
1134 #endif
1135
1136 /*
1137 * Get the position of the first char in the screen line which
1138 * puts tpos on screen.
1139 */
get_lastlinepos(POSITION pos,POSITION tpos,int sheight)1140 static POSITION get_lastlinepos(POSITION pos, POSITION tpos, int sheight)
1141 {
1142 int nlines;
1143
1144 for (nlines = 0;; nlines++)
1145 {
1146 POSITION npos = forw_line(pos);
1147 if (npos > tpos)
1148 {
1149 if (nlines < sheight)
1150 return NULL_POSITION;
1151 return pos;
1152 }
1153 pos = npos;
1154 }
1155 }
1156
1157 /*
1158 * Get the segment index of tpos in the line starting at pos.
1159 * A segment is a string of printable chars that fills the screen width.
1160 */
get_seg(POSITION pos,POSITION tpos)1161 static int get_seg(POSITION pos, POSITION tpos)
1162 {
1163 int seg;
1164
1165 for (seg = 0;; seg++)
1166 {
1167 POSITION npos = forw_line_seg(pos, FALSE, FALSE, TRUE);
1168 if (npos > tpos)
1169 return seg;
1170 pos = npos;
1171 }
1172 }
1173
1174 /*
1175 * Search a subset of the file, specified by start/end position.
1176 */
search_range(POSITION pos,POSITION endpos,int search_type,int matches,int maxlines,POSITION * plinepos,POSITION * pendpos,POSITION * plastlinepos)1177 static int search_range(POSITION pos, POSITION endpos, int search_type, int matches, int maxlines, POSITION *plinepos, POSITION *pendpos, POSITION *plastlinepos)
1178 {
1179 char *line;
1180 char *cline;
1181 int line_len;
1182 LINENUM linenum;
1183 #define NSP (NUM_SEARCH_COLORS+2)
1184 char *sp[NSP];
1185 char *ep[NSP];
1186 int line_match;
1187 int cvt_ops;
1188 int cvt_len;
1189 int *chpos;
1190 POSITION linepos, oldpos;
1191 int skip_bytes = 0;
1192 int swidth = sc_width - line_pfx_width();
1193 int sheight = sc_height - sindex_from_sline(jump_sline);
1194
1195 linenum = find_linenum(pos);
1196 if (nosearch_headers && linenum <= header_lines)
1197 {
1198 linenum = header_lines + 1;
1199 pos = find_pos(linenum);
1200 }
1201 if (pos == NULL_POSITION)
1202 return (-1);
1203 oldpos = pos;
1204 /* When the search wraps around, end at starting position. */
1205 if ((search_type & SRCH_WRAP) && endpos == NULL_POSITION)
1206 endpos = pos;
1207 for (;;)
1208 {
1209 /*
1210 * Get lines until we find a matching one or until
1211 * we hit end-of-file (or beginning-of-file if we're
1212 * going backwards), or until we hit the end position.
1213 */
1214 if (ABORT_SIGS())
1215 {
1216 /*
1217 * A signal aborts the search.
1218 */
1219 return (-1);
1220 }
1221
1222 if ((endpos != NULL_POSITION && !(search_type & SRCH_WRAP) &&
1223 (((search_type & SRCH_FORW) && pos >= endpos) ||
1224 ((search_type & SRCH_BACK) && pos <= endpos))) || maxlines == 0)
1225 {
1226 /*
1227 * Reached end position without a match.
1228 */
1229 if (pendpos != NULL)
1230 *pendpos = pos;
1231 return (matches);
1232 }
1233 if (maxlines > 0)
1234 maxlines--;
1235
1236 if (search_type & SRCH_FORW)
1237 {
1238 /*
1239 * Read the next line, and save the
1240 * starting position of that line in linepos.
1241 */
1242 linepos = pos;
1243 pos = forw_raw_line(pos, &line, &line_len);
1244 if (linenum != 0)
1245 linenum++;
1246 } else
1247 {
1248 /*
1249 * Read the previous line and save the
1250 * starting position of that line in linepos.
1251 */
1252 pos = back_raw_line(pos, &line, &line_len);
1253 linepos = pos;
1254 if (linenum != 0)
1255 linenum--;
1256 }
1257
1258 if (pos == NULL_POSITION)
1259 {
1260 /*
1261 * Reached EOF/BOF without a match.
1262 */
1263 if (search_type & SRCH_WRAP)
1264 {
1265 /*
1266 * The search wraps around the current file, so
1267 * try to continue at BOF/EOF.
1268 */
1269 if (search_type & SRCH_FORW)
1270 {
1271 pos = ch_zero();
1272 } else
1273 {
1274 pos = ch_length();
1275 if (pos == NULL_POSITION)
1276 {
1277 (void) ch_end_seek();
1278 pos = ch_length();
1279 }
1280 }
1281 if (pos != NULL_POSITION) {
1282 /*
1283 * Wrap-around was successful. Clear
1284 * the flag so we don't wrap again, and
1285 * continue the search at new pos.
1286 */
1287 search_type &= ~SRCH_WRAP;
1288 linenum = find_linenum(pos);
1289 continue;
1290 }
1291 }
1292 if (pendpos != NULL)
1293 *pendpos = oldpos;
1294 return (matches);
1295 }
1296
1297 /*
1298 * If we're using line numbers, we might as well
1299 * remember the information we have now (the position
1300 * and line number of the current line).
1301 * Don't do it for every line because it slows down
1302 * the search. Remember the line number only if
1303 * we're "far" from the last place we remembered it.
1304 */
1305 if (linenums && abs((int)(pos - oldpos)) > 2048)
1306 add_lnum(linenum, pos);
1307 oldpos = pos;
1308
1309 #if HILITE_SEARCH
1310 if (is_filtered(linepos))
1311 continue;
1312 #endif
1313 if (nosearch_headers)
1314 skip_bytes = skip_columns(header_cols, &line, &line_len);
1315
1316 /*
1317 * If it's a caseless search, convert the line to lowercase.
1318 * If we're doing backspace processing, delete backspaces.
1319 */
1320 cvt_ops = get_cvt_ops(search_type);
1321 cvt_len = cvt_length(line_len, cvt_ops);
1322 cline = (char *) ecalloc(1, cvt_len);
1323 chpos = cvt_alloc_chpos(cvt_len);
1324 cvt_text(cline, line, chpos, &line_len, cvt_ops);
1325
1326 #if HILITE_SEARCH
1327 /*
1328 * If any filters are in effect, ignore non-matching lines.
1329 */
1330 if (filter_infos != NULL &&
1331 ((search_type & SRCH_FIND_ALL) ||
1332 prep_startpos == NULL_POSITION ||
1333 linepos < prep_startpos || linepos >= prep_endpos)) {
1334 if (matches_filters(pos, cline, line_len, chpos, linepos, sp, ep, NSP))
1335 continue;
1336 }
1337 #endif
1338
1339 /*
1340 * Test the next line to see if we have a match.
1341 * We are successful if we either want a match and got one,
1342 * or if we want a non-match and got one.
1343 */
1344 if (prev_pattern(&search_info))
1345 {
1346 line_match = match_pattern(info_compiled(&search_info), search_info.text,
1347 cline, line_len, sp, ep, NSP, 0, search_type);
1348 if (line_match)
1349 {
1350 /*
1351 * Got a match.
1352 */
1353 if (search_type & SRCH_FIND_ALL)
1354 {
1355 #if HILITE_SEARCH
1356 /*
1357 * We are supposed to find all matches in the range.
1358 * Just add the matches in this line to the
1359 * hilite list and keep searching.
1360 */
1361 hilite_line(linepos + skip_bytes, cline, line_len, chpos, sp, ep, NSP, cvt_ops);
1362 #endif
1363 } else if (--matches <= 0)
1364 {
1365 /*
1366 * Found the one match we're looking for.
1367 * Return it.
1368 */
1369 #if HILITE_SEARCH
1370 if (hilite_search == OPT_ON)
1371 {
1372 /*
1373 * Clear the hilite list and add only
1374 * the matches in this one line.
1375 */
1376 clr_hilite();
1377 hilite_line(linepos + skip_bytes, cline, line_len, chpos, sp, ep, NSP, cvt_ops);
1378 }
1379 #endif
1380 if (chop_line())
1381 {
1382 /*
1383 * If necessary, shift horizontally to make sure
1384 * search match is fully visible.
1385 */
1386 if (sp[0] != NULL && ep[0] != NULL)
1387 {
1388 int start_off = sp[0] - cline;
1389 int end_off = ep[0] - cline;
1390 int save_hshift = hshift;
1391 int sshift;
1392 int eshift;
1393 hshift = 0; /* make get_seg count screen lines */
1394 sshift = swidth * get_seg(linepos, linepos + chpos[start_off]);
1395 eshift = swidth * get_seg(linepos, linepos + chpos[end_off]);
1396 if (sshift >= save_hshift && eshift <= save_hshift)
1397 {
1398 hshift = save_hshift;
1399 } else
1400 {
1401 hshift = sshift;
1402 screen_trashed = 1;
1403 }
1404 }
1405 } else if (plastlinepos != NULL)
1406 {
1407 /*
1408 * If the line is so long that the highlighted match
1409 * won't be seen when the line is displayed normally
1410 * (starting at the first char) because it fills the whole
1411 * screen and more, scroll forward until the last char
1412 * of the match appears in the last line on the screen.
1413 * lastlinepos is the position of the first char of that last line.
1414 */
1415 if (ep[0] != NULL)
1416 {
1417 int end_off = ep[0] - cline;
1418 if (end_off >= swidth * sheight / 4) /* heuristic */
1419 *plastlinepos = get_lastlinepos(linepos, linepos + chpos[end_off], sheight);
1420 }
1421 }
1422 free(cline);
1423 free(chpos);
1424 if (plinepos != NULL)
1425 *plinepos = linepos;
1426 return (0);
1427 }
1428 }
1429 }
1430 free(cline);
1431 free(chpos);
1432 }
1433 }
1434
1435 /*
1436 * search for a pattern in history. If found, compile that pattern.
1437 */
hist_pattern(int search_type)1438 static int hist_pattern(int search_type)
1439 {
1440 #if CMD_HISTORY
1441 char *pattern;
1442
1443 set_mlist(ml_search, 0);
1444 pattern = cmd_lastpattern();
1445 if (pattern == NULL)
1446 return (0);
1447
1448 if (set_pattern(&search_info, pattern, search_type, 1) < 0)
1449 return (-1);
1450
1451 #if HILITE_SEARCH
1452 if (hilite_search == OPT_ONPLUS && !hide_hilite)
1453 hilite_screen();
1454 #endif
1455
1456 return (1);
1457 #else /* CMD_HISTORY */
1458 return (0);
1459 #endif /* CMD_HISTORY */
1460 }
1461
1462 /*
1463 * Change the caseless-ness of searches.
1464 * Updates the internal search state to reflect a change in the -i flag.
1465 */
chg_caseless(void)1466 public void chg_caseless(void)
1467 {
1468 if (!search_info.is_ucase_pattern)
1469 {
1470 /*
1471 * Pattern did not have uppercase.
1472 * Set the search caselessness to the global caselessness.
1473 */
1474 is_caseless = caseless;
1475 /*
1476 * If regex handles caseless, we need to discard
1477 * the pattern which was compiled with the old caseless.
1478 */
1479 if (!re_handles_caseless)
1480 /* We handle caseless, so the pattern doesn't change. */
1481 return;
1482 }
1483 /*
1484 * Regenerate the pattern using the new state.
1485 */
1486 clear_pattern(&search_info);
1487 (void) hist_pattern(search_info.search_type);
1488 }
1489
1490 /*
1491 * Search for the n-th occurrence of a specified pattern,
1492 * either forward or backward.
1493 * Return the number of matches not yet found in this file
1494 * (that is, n minus the number of matches found).
1495 * Return -1 if the search should be aborted.
1496 * Caller may continue the search in another file
1497 * if less than n matches are found in this file.
1498 */
search(int search_type,char * pattern,int n)1499 public int search(int search_type, char *pattern, int n)
1500 {
1501 POSITION pos;
1502 POSITION opos;
1503 POSITION lastlinepos = NULL_POSITION;
1504
1505 if (pattern == NULL || *pattern == '\0')
1506 {
1507 /*
1508 * A null pattern means use the previously compiled pattern.
1509 */
1510 search_type |= SRCH_AFTER_TARGET;
1511 if (!prev_pattern(&search_info))
1512 {
1513 int r = hist_pattern(search_type);
1514 if (r == 0)
1515 error("No previous regular expression", NULL_PARG);
1516 if (r <= 0)
1517 return (-1);
1518 }
1519 if ((search_type & SRCH_NO_REGEX) !=
1520 (search_info.search_type & SRCH_NO_REGEX))
1521 {
1522 error("Please re-enter search pattern", NULL_PARG);
1523 return -1;
1524 }
1525 #if HILITE_SEARCH
1526 if (hilite_search == OPT_ON || status_col)
1527 {
1528 /*
1529 * Erase the highlights currently on screen.
1530 * If the search fails, we'll redisplay them later.
1531 */
1532 repaint_hilite(0);
1533 }
1534 if (hilite_search == OPT_ONPLUS && hide_hilite)
1535 {
1536 /*
1537 * Highlight any matches currently on screen,
1538 * before we actually start the search.
1539 */
1540 hide_hilite = 0;
1541 hilite_screen();
1542 }
1543 hide_hilite = 0;
1544 #endif
1545 } else
1546 {
1547 /*
1548 * Compile the pattern.
1549 */
1550 int show_error = !(search_type & SRCH_INCR);
1551 if (set_pattern(&search_info, pattern, search_type, show_error) < 0)
1552 return (-1);
1553 #if HILITE_SEARCH
1554 if (hilite_search || status_col)
1555 {
1556 /*
1557 * Erase the highlights currently on screen.
1558 * Also permanently delete them from the hilite list.
1559 */
1560 repaint_hilite(0);
1561 hide_hilite = 0;
1562 clr_hilite();
1563 }
1564 if (hilite_search == OPT_ONPLUS || status_col)
1565 {
1566 /*
1567 * Highlight any matches currently on screen,
1568 * before we actually start the search.
1569 */
1570 hilite_screen();
1571 }
1572 #endif
1573 }
1574
1575 /*
1576 * Figure out where to start the search.
1577 */
1578 pos = search_pos(search_type);
1579 opos = position(sindex_from_sline(jump_sline));
1580 if (pos == NULL_POSITION)
1581 {
1582 /*
1583 * Can't find anyplace to start searching from.
1584 */
1585 if (search_type & SRCH_PAST_EOF)
1586 return (n);
1587 #if HILITE_SEARCH
1588 if (hilite_search == OPT_ON || status_col)
1589 repaint_hilite(1);
1590 #endif
1591 error("Nothing to search", NULL_PARG);
1592 return (-1);
1593 }
1594
1595 n = search_range(pos, NULL_POSITION, search_type, n, -1,
1596 &pos, (POSITION*)NULL, &lastlinepos);
1597 if (n != 0)
1598 {
1599 /*
1600 * Search was unsuccessful.
1601 */
1602 #if HILITE_SEARCH
1603 if ((hilite_search == OPT_ON || status_col) && n > 0)
1604 /*
1605 * Redisplay old hilites.
1606 */
1607 repaint_hilite(1);
1608 #endif
1609 return (n);
1610 }
1611
1612 if (!(search_type & SRCH_NO_MOVE))
1613 {
1614 /*
1615 * Go to the matching line.
1616 */
1617 if (lastlinepos != NULL_POSITION)
1618 jump_loc(lastlinepos, BOTTOM);
1619 else if (pos != opos)
1620 jump_loc(pos, jump_sline);
1621 }
1622
1623 #if HILITE_SEARCH
1624 if (hilite_search == OPT_ON || status_col)
1625 /*
1626 * Display new hilites in the matching line.
1627 */
1628 repaint_hilite(1);
1629 #endif
1630 return (0);
1631 }
1632
1633 #if HILITE_SEARCH
1634 /*
1635 * Prepare hilites in a given range of the file.
1636 *
1637 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1638 * of the file that has been "prepared"; that is, scanned for matches for
1639 * the current search pattern, and hilites have been created for such matches.
1640 * If prep_startpos == NULL_POSITION, the prep region is empty.
1641 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1642 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1643 */
prep_hilite(POSITION spos,POSITION epos,int maxlines)1644 public void prep_hilite(POSITION spos, POSITION epos, int maxlines)
1645 {
1646 POSITION nprep_startpos = prep_startpos;
1647 POSITION nprep_endpos = prep_endpos;
1648 POSITION new_epos;
1649 POSITION max_epos;
1650 int result;
1651 int i;
1652
1653 /*
1654 * Search beyond where we're asked to search, so the prep region covers
1655 * more than we need. Do one big search instead of a bunch of small ones.
1656 */
1657 #define SEARCH_MORE (3*size_linebuf)
1658
1659 if (!prev_pattern(&search_info) && !is_filtering())
1660 return;
1661
1662 /*
1663 * Make sure our prep region always starts at the beginning of
1664 * a line. (search_range takes care of the end boundary below.)
1665 */
1666 spos = back_raw_line(spos+1, (char **)NULL, (int *)NULL);
1667
1668 /*
1669 * If we're limited to a max number of lines, figure out the
1670 * file position we should stop at.
1671 */
1672 if (maxlines < 0)
1673 max_epos = NULL_POSITION;
1674 else
1675 {
1676 max_epos = spos;
1677 for (i = 0; i < maxlines; i++)
1678 max_epos = forw_raw_line(max_epos, (char **)NULL, (int *)NULL);
1679 }
1680
1681 /*
1682 * Find two ranges:
1683 * The range that we need to search (spos,epos); and the range that
1684 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1685 */
1686
1687 if (prep_startpos == NULL_POSITION ||
1688 (epos != NULL_POSITION && epos < prep_startpos) ||
1689 spos > prep_endpos)
1690 {
1691 /*
1692 * New range is not contiguous with old prep region.
1693 * Discard the old prep region and start a new one.
1694 */
1695 clr_hilite();
1696 clr_filter();
1697 if (epos != NULL_POSITION)
1698 epos += SEARCH_MORE;
1699 nprep_startpos = spos;
1700 } else
1701 {
1702 /*
1703 * New range partially or completely overlaps old prep region.
1704 */
1705 if (epos == NULL_POSITION)
1706 {
1707 /*
1708 * New range goes to end of file.
1709 */
1710 ;
1711 } else if (epos > prep_endpos)
1712 {
1713 /*
1714 * New range ends after old prep region.
1715 * Extend prep region to end at end of new range.
1716 */
1717 epos += SEARCH_MORE;
1718 } else /* (epos <= prep_endpos) */
1719 {
1720 /*
1721 * New range ends within old prep region.
1722 * Truncate search to end at start of old prep region.
1723 */
1724 epos = prep_startpos;
1725 }
1726
1727 if (spos < prep_startpos)
1728 {
1729 /*
1730 * New range starts before old prep region.
1731 * Extend old prep region backwards to start at
1732 * start of new range.
1733 */
1734 if (spos < SEARCH_MORE)
1735 spos = 0;
1736 else
1737 spos -= SEARCH_MORE;
1738 nprep_startpos = spos;
1739 } else /* (spos >= prep_startpos) */
1740 {
1741 /*
1742 * New range starts within or after old prep region.
1743 * Trim search to start at end of old prep region.
1744 */
1745 spos = prep_endpos;
1746 }
1747 }
1748
1749 if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1750 epos > max_epos)
1751 /*
1752 * Don't go past the max position we're allowed.
1753 */
1754 epos = max_epos;
1755
1756 if (epos == NULL_POSITION || epos > spos)
1757 {
1758 int search_type = SRCH_FORW | SRCH_FIND_ALL;
1759 search_type |= (search_info.search_type & (SRCH_NO_REGEX|SRCH_SUBSEARCH_ALL));
1760 for (;;)
1761 {
1762 result = search_range(spos, epos, search_type, 0, maxlines, (POSITION*)NULL, &new_epos, (POSITION*)NULL);
1763 if (result < 0)
1764 return;
1765 if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1766 nprep_endpos = new_epos;
1767
1768 /*
1769 * Check both ends of the resulting prep region to
1770 * make sure they're not filtered. If they are,
1771 * keep going at least one more line until we find
1772 * something that isn't filtered, or hit the end.
1773 */
1774 if (prep_endpos == NULL_POSITION || nprep_endpos > prep_endpos)
1775 {
1776 if (new_epos >= nprep_endpos && is_filtered(new_epos-1))
1777 {
1778 spos = nprep_endpos;
1779 epos = forw_raw_line(nprep_endpos, (char **)NULL, (int *)NULL);
1780 if (epos == NULL_POSITION)
1781 break;
1782 maxlines = 1;
1783 continue;
1784 }
1785 }
1786
1787 if (prep_startpos == NULL_POSITION || nprep_startpos < prep_startpos)
1788 {
1789 if (nprep_startpos > 0 && is_filtered(nprep_startpos))
1790 {
1791 epos = nprep_startpos;
1792 spos = back_raw_line(nprep_startpos, (char **)NULL, (int *)NULL);
1793 if (spos == NULL_POSITION)
1794 break;
1795 nprep_startpos = spos;
1796 maxlines = 1;
1797 continue;
1798 }
1799 }
1800 break;
1801 }
1802 }
1803 prep_startpos = nprep_startpos;
1804 prep_endpos = nprep_endpos;
1805 }
1806
1807 /*
1808 * Set the pattern to be used for line filtering.
1809 */
set_filter_pattern(char * pattern,int search_type)1810 public void set_filter_pattern(char *pattern, int search_type)
1811 {
1812 struct pattern_info *filter;
1813
1814 clr_filter();
1815 if (pattern == NULL || *pattern == '\0')
1816 {
1817 /* Clear and free all filters. */
1818 for (filter = filter_infos; filter != NULL; )
1819 {
1820 struct pattern_info *next_filter = filter->next;
1821 clear_pattern(filter);
1822 free(filter);
1823 filter = next_filter;
1824 }
1825 filter_infos = NULL;
1826 } else
1827 {
1828 /* Create a new filter and add it to the filter_infos list. */
1829 filter = ecalloc(1, sizeof(struct pattern_info));
1830 init_pattern(filter);
1831 if (set_pattern(filter, pattern, search_type, 1) < 0)
1832 {
1833 free(filter);
1834 return;
1835 }
1836 filter->next = filter_infos;
1837 filter_infos = filter;
1838 }
1839 screen_trashed = 1;
1840 }
1841
1842 /*
1843 * Is there a line filter in effect?
1844 */
is_filtering(void)1845 public int is_filtering(void)
1846 {
1847 if (ch_getflags() & CH_HELPFILE)
1848 return (0);
1849 return (filter_infos != NULL);
1850 }
1851 #endif
1852
1853 #if HAVE_V8_REGCOMP
1854 /*
1855 * This function is called by the V8 regcomp to report
1856 * errors in regular expressions.
1857 */
1858 public int reg_show_error = 1;
1859
regerror(char * s)1860 void regerror(char *s)
1861 {
1862 PARG parg;
1863
1864 if (!reg_show_error)
1865 return;
1866 parg.p_string = s;
1867 error("%s", &parg);
1868 }
1869 #endif
1870
1871