2 * Copyright (C) 1984-2022 Mark Nudelman
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.
7 * For more information, see the README file.
12 * Routines to search a file for a pattern.
19 #define MINPOS(a,b) (((a) < (b)) ? (a) : (b))
20 #define MAXPOS(a,b) (((a) > (b)) ? (a) : (b))
23 extern int how_search
;
27 extern int jump_sline
;
30 extern int status_col
;
31 extern void *ml_search
;
32 extern POSITION start_attnpos
;
33 extern POSITION end_attnpos
;
35 extern int screen_trashed
;
40 extern int hilite_search
;
41 extern int size_linebuf
;
43 extern int can_goto_line
;
44 static int hide_hilite
;
45 static POSITION prep_startpos
;
46 static POSITION prep_endpos
;
47 extern POSITION xxpos
;
50 * Structures for maintaining a set of ranges for hilites and filtered-out
51 * lines. Each range is stored as a node within a red-black tree, and we
52 * try to extend existing ranges (without creating overlaps) rather than
53 * create new nodes if possible. We remember the last node found by a
54 * search for constant-time lookup if the next search is near enough to
55 * the previous. To aid that, we overlay a secondary doubly-linked list
56 * on top of the red-black tree so we can find the preceding/succeeding
57 * nodes also in constant time.
59 * Each node is allocated from a series of pools, each pool double the size
60 * of the previous (for amortised constant time allocation). Since our only
61 * tree operations are clear and node insertion, not node removal, we don't
62 * need to maintain a usage bitmap or freelist and can just return nodes
63 * from the pool in-order until capacity is reached.
72 struct hilite_node
*parent
;
73 struct hilite_node
*left
;
74 struct hilite_node
*right
;
75 struct hilite_node
*prev
;
76 struct hilite_node
*next
;
84 struct hilite_storage
*next
;
85 struct hilite_node
*nodes
;
89 struct hilite_storage
*first
;
90 struct hilite_storage
*current
;
91 struct hilite_node
*root
;
92 struct hilite_node
*lookaside
;
94 #define HILITE_INITIALIZER() { NULL, NULL, NULL, NULL }
95 #define HILITE_LOOKASIDE_STEPS 2
97 static struct hilite_tree hilite_anchor
= HILITE_INITIALIZER();
98 static struct hilite_tree filter_anchor
= HILITE_INITIALIZER();
99 static struct pattern_info
*filter_infos
= NULL
;
104 * These are the static variables that represent the "remembered"
105 * search pattern and filter pattern.
107 struct pattern_info
{
108 PATTERN_TYPE compiled
;
111 struct pattern_info
*next
;
115 #define info_compiled(info) ((void*)0)
117 #define info_compiled(info) ((info)->compiled)
120 static struct pattern_info search_info
;
121 static int is_ucase_pattern
;
122 public int is_caseless
;
125 * Are there any uppercase letters in this string?
131 char *str_end
= str
+ strlen(str
);
134 while (str
< str_end
)
136 ch
= step_char(&str
, +1, str_end
);
144 * Discard a saved pattern.
148 struct pattern_info
*info
;
150 if (info
->text
!= NULL
)
154 uncompile_pattern(&info
->compiled
);
159 * Compile and save a search pattern.
162 set_pattern(info
, pattern
, search_type
, show_error
)
163 struct pattern_info
*info
;
169 * Ignore case if -I is set OR
170 * -i is set AND the pattern is all lowercase.
172 is_ucase_pattern
= (pattern
== NULL
) ? FALSE
: is_ucase(pattern
);
173 is_caseless
= (is_ucase_pattern
&& caseless
!= OPT_ONPLUS
) ? 0 : caseless
;
176 SET_NULL_PATTERN(info
->compiled
);
177 else if (compile_pattern(pattern
, search_type
, show_error
, &info
->compiled
) < 0)
180 /* Pattern compiled successfully; save the text too. */
181 if (info
->text
!= NULL
)
186 info
->text
= (char *) ecalloc(1, strlen(pattern
)+1);
187 strcpy(info
->text
, pattern
);
189 info
->search_type
= search_type
;
194 * Initialize saved pattern to nothing.
198 struct pattern_info
*info
;
200 SET_NULL_PATTERN(info
->compiled
);
202 info
->search_type
= 0;
207 * Initialize search variables.
210 init_search(VOID_PARAM
)
212 init_pattern(&search_info
);
216 * Determine which text conversions to perform before pattern matching.
219 get_cvt_ops(VOID_PARAM
)
223 if (is_caseless
&& !re_handles_caseless
)
225 if (bs_mode
== BS_SPECIAL
)
227 if (bs_mode
!= BS_CONTROL
)
229 if (ctldisp
== OPT_ONPLUS
)
235 * Is there a previous (remembered) search pattern?
239 struct pattern_info
*info
;
242 if ((info
->search_type
& SRCH_NO_REGEX
) == 0)
243 return (!is_null_pattern(info
->compiled
));
245 return (info
->text
!= NULL
);
250 * Repaint the hilites currently displayed on the screen.
251 * Repaint each line which contains highlighted text.
252 * If on==0, force all hilites off.
260 int save_hide_hilite
;
265 save_hide_hilite
= hide_hilite
;
276 hide_hilite
= save_hide_hilite
;
280 for (sindex
= TOP
; sindex
< TOP
+ sc_height
-1; sindex
++)
282 pos
= position(sindex
);
283 if (pos
== NULL_POSITION
)
285 (void) forw_line(pos
);
291 hide_hilite
= save_hide_hilite
;
296 * Clear the attn hilite.
299 clear_attn(VOID_PARAM
)
303 POSITION old_start_attnpos
;
304 POSITION old_end_attnpos
;
309 if (start_attnpos
== NULL_POSITION
)
311 old_start_attnpos
= start_attnpos
;
312 old_end_attnpos
= end_attnpos
;
313 start_attnpos
= end_attnpos
= NULL_POSITION
;
323 for (sindex
= TOP
; sindex
< TOP
+ sc_height
-1; sindex
++)
325 pos
= position(sindex
);
326 if (pos
== NULL_POSITION
)
328 epos
= position(sindex
+1);
329 if (pos
<= old_end_attnpos
&&
330 (epos
== NULL_POSITION
|| epos
> old_start_attnpos
))
332 (void) forw_line(pos
);
338 if (overlay_header())
346 * Toggle or clear search string highlighting.
352 clear_pattern(&search_info
);
359 if (hilite_anchor
.first
== NULL
)
361 error("No previous regular expression", NULL_PARG
);
364 hide_hilite
= !hide_hilite
;
372 * Clear the hilite list.
376 struct hilite_tree
*anchor
;
378 struct hilite_storage
*hls
;
379 struct hilite_storage
*nexthls
;
381 for (hls
= anchor
->first
; hls
!= NULL
; hls
= nexthls
)
384 free((void*)hls
->nodes
);
387 anchor
->first
= NULL
;
388 anchor
->current
= NULL
;
391 anchor
->lookaside
= NULL
;
393 prep_startpos
= prep_endpos
= NULL_POSITION
;
397 clr_hilite(VOID_PARAM
)
399 clr_hlist(&hilite_anchor
);
403 clr_filter(VOID_PARAM
)
405 clr_hlist(&filter_anchor
);
410 struct hilite_tree
*anchor
;
412 struct hilite_node
*n
= anchor
->root
;
413 while (n
!= NULL
&& n
->right
!= NULL
)
420 struct hilite_node
*n
;
427 struct hilite_node
*n
;
433 * Find the node covering pos, or the node after it if no node covers it,
434 * or return NULL if pos is after the last range. Remember the found node,
435 * to speed up subsequent searches for the same or similar positions (if
436 * we return NULL, remember the last node.)
439 hlist_find(anchor
, pos
)
440 struct hilite_tree
*anchor
;
443 struct hilite_node
*n
, *m
;
445 if (anchor
->lookaside
)
450 n
= anchor
->lookaside
;
454 if (pos
< n
->r
.hl_endpos
)
456 if (n
->prev
== NULL
|| pos
>= n
->prev
->r
.hl_endpos
)
461 } else if (n
->next
== NULL
)
469 * If we don't find the right node within a small
470 * distance, don't keep doing a linear search!
472 if (steps
>= HILITE_LOOKASIDE_STEPS
)
476 if (pos
< n
->r
.hl_endpos
)
477 anchor
->lookaside
= n
= n
->prev
;
479 anchor
->lookaside
= n
= n
->next
;
491 if (pos
< n
->r
.hl_startpos
)
501 if (pos
>= n
->r
.hl_endpos
)
503 if (n
->right
!= NULL
)
521 anchor
->lookaside
= n
;
523 anchor
->lookaside
= m
;
529 * Should any characters in a specified range be highlighted?
532 is_hilited_range(pos
, epos
)
536 struct hilite_node
*n
= hlist_find(&hilite_anchor
, pos
);
537 return (n
!= NULL
&& (epos
== NULL_POSITION
|| epos
> n
->r
.hl_startpos
));
541 * Is a line "filtered" -- that is, should it be hidden?
547 struct hilite_node
*n
;
549 if (ch_getflags() & CH_HELPFILE
)
552 n
= hlist_find(&filter_anchor
, pos
);
553 return (n
!= NULL
&& pos
>= n
->r
.hl_startpos
);
557 * If pos is hidden, return the next position which isn't, otherwise
564 struct hilite_node
*n
;
566 if (ch_getflags() & CH_HELPFILE
)
569 n
= hlist_find(&filter_anchor
, pos
);
570 while (n
!= NULL
&& pos
>= n
->r
.hl_startpos
)
572 pos
= n
->r
.hl_endpos
;
579 * If pos is hidden, return the previous position which isn't or 0 if
580 * we're filtered right to the beginning, otherwise just return pos.
586 struct hilite_node
*n
;
588 if (ch_getflags() & CH_HELPFILE
)
591 n
= hlist_find(&filter_anchor
, pos
);
592 while (n
!= NULL
&& pos
>= n
->r
.hl_startpos
)
594 pos
= n
->r
.hl_startpos
;
605 * Should any characters in a specified range be highlighted?
606 * If nohide is nonzero, don't consider hide_hilite.
609 is_hilited_attr(pos
, epos
, nohide
, p_matches
)
617 if (p_matches
!= NULL
)
621 start_attnpos
!= NULL_POSITION
&&
622 pos
<= end_attnpos
&&
623 (epos
== NULL_POSITION
|| epos
>= start_attnpos
))
625 * The attn line overlaps this range.
627 return (AT_HILITE
|AT_COLOR_ATTN
);
629 match
= is_hilited_range(pos
, epos
);
633 if (p_matches
== NULL
)
635 * Kinda kludgy way to recognize that caller is checking for
636 * hilite in status column. In this case we want to return
637 * hilite status even if hiliting is disabled or hidden.
639 return (AT_HILITE
|AT_COLOR_SEARCH
);
642 * Report matches, even if we're hiding highlights.
646 if (hilite_search
== 0)
648 * Not doing highlighting.
652 if (!nohide
&& hide_hilite
)
654 * Highlighting is hidden.
658 return (AT_HILITE
|AT_COLOR_SEARCH
);
662 * Tree node storage: get the current block of nodes if it has spare
663 * capacity, or create a new one if not.
665 static struct hilite_storage
*
666 hlist_getstorage(anchor
)
667 struct hilite_tree
*anchor
;
670 struct hilite_storage
*s
;
674 if (anchor
->current
->used
< anchor
->current
->capacity
)
675 return anchor
->current
;
676 capacity
= anchor
->current
->capacity
* 2;
679 s
= (struct hilite_storage
*) ecalloc(1, sizeof(struct hilite_storage
));
680 s
->nodes
= (struct hilite_node
*) ecalloc(capacity
, sizeof(struct hilite_node
));
681 s
->capacity
= capacity
;
685 anchor
->current
->next
= s
;
693 * Tree node storage: retrieve a new empty node to be inserted into the
696 static struct hilite_node
*
697 hlist_getnode(anchor
)
698 struct hilite_tree
*anchor
;
700 struct hilite_storage
*s
= hlist_getstorage(anchor
);
701 return &s
->nodes
[s
->used
++];
705 * Rotate the tree left around a pivot node.
708 hlist_rotate_left(anchor
, n
)
709 struct hilite_tree
*anchor
;
710 struct hilite_node
*n
;
712 struct hilite_node
*np
= n
->parent
;
713 struct hilite_node
*nr
= n
->right
;
714 struct hilite_node
*nrl
= n
->right
->left
;
736 * Rotate the tree right around a pivot node.
739 hlist_rotate_right(anchor
, n
)
740 struct hilite_tree
*anchor
;
741 struct hilite_node
*n
;
743 struct hilite_node
*np
= n
->parent
;
744 struct hilite_node
*nl
= n
->left
;
745 struct hilite_node
*nlr
= n
->left
->right
;
768 * Add a new hilite to a hilite list.
771 add_hilite(anchor
, hl
)
772 struct hilite_tree
*anchor
;
775 struct hilite_node
*p
, *n
, *u
;
777 /* Ignore empty ranges. */
778 if (hl
->hl_startpos
>= hl
->hl_endpos
)
783 /* Inserting the very first node is trivial. */
786 n
= hlist_getnode(anchor
);
789 anchor
->lookaside
= n
;
794 * Find our insertion point. If we come across any overlapping
795 * or adjoining existing ranges, shrink our range and discard
796 * if it become empty.
800 if (hl
->hl_startpos
< p
->r
.hl_startpos
)
802 if (hl
->hl_endpos
> p
->r
.hl_startpos
)
803 hl
->hl_endpos
= p
->r
.hl_startpos
;
811 if (hl
->hl_startpos
< p
->r
.hl_endpos
) {
812 hl
->hl_startpos
= p
->r
.hl_endpos
;
813 if (hl
->hl_startpos
>= hl
->hl_endpos
)
816 if (p
->right
!= NULL
)
825 * Now we're at the right leaf, again check for contiguous ranges
826 * and extend the existing node if possible to avoid the
827 * insertion. Otherwise insert a new node at the leaf.
829 if (hl
->hl_startpos
< p
->r
.hl_startpos
) {
830 if (hl
->hl_endpos
== p
->r
.hl_startpos
)
832 p
->r
.hl_startpos
= hl
->hl_startpos
;
835 if (p
->prev
!= NULL
&& p
->prev
->r
.hl_endpos
== hl
->hl_startpos
)
837 p
->prev
->r
.hl_endpos
= hl
->hl_endpos
;
841 p
->left
= n
= hlist_getnode(anchor
);
850 if (p
->r
.hl_endpos
== hl
->hl_startpos
)
852 p
->r
.hl_endpos
= hl
->hl_endpos
;
855 if (p
->next
!= NULL
&& hl
->hl_endpos
== p
->next
->r
.hl_startpos
) {
856 p
->next
->r
.hl_startpos
= hl
->hl_startpos
;
860 p
->right
= n
= hlist_getnode(anchor
);
874 * The tree is in the correct order and covers the right ranges
875 * now, but may have become unbalanced. Rebalance it using the
876 * standard red-black tree constraints and operations.
880 /* case 1 - current is root, root is always black */
881 if (n
->parent
== NULL
)
887 /* case 2 - parent is black, we can always be red */
892 * constraint: because the root must be black, if our
893 * parent is red it cannot be the root therefore we must
898 * case 3 - parent and uncle are red, repaint them black,
899 * the grandparent red, and start again at the grandparent.
901 u
= n
->parent
->parent
->left
;
903 u
= n
->parent
->parent
->right
;
904 if (u
!= NULL
&& u
->red
)
908 n
= n
->parent
->parent
;
914 * case 4 - parent is red but uncle is black, parent and
915 * grandparent on opposite sides. We need to start
916 * changing the structure now. This and case 5 will shorten
917 * our branch and lengthen the sibling, between them
920 if (n
== n
->parent
->right
&&
921 n
->parent
== n
->parent
->parent
->left
)
923 hlist_rotate_left(anchor
, n
->parent
);
925 } else if (n
== n
->parent
->left
&&
926 n
->parent
== n
->parent
->parent
->right
)
928 hlist_rotate_right(anchor
, n
->parent
);
933 * case 5 - parent is red but uncle is black, parent and
934 * grandparent on same side
937 n
->parent
->parent
->red
= 1;
938 if (n
== n
->parent
->left
)
939 hlist_rotate_right(anchor
, n
->parent
->parent
);
941 hlist_rotate_left(anchor
, n
->parent
->parent
);
947 * Highlight every character in a range of displayed characters.
950 create_hilites(linepos
, start_index
, end_index
, chpos
)
959 /* Start the first hilite. */
960 hl
.hl_startpos
= linepos
+ chpos
[start_index
];
963 * Step through the displayed chars.
964 * If the source position (before cvt) of the char is one more
965 * than the source pos of the previous char (the usual case),
966 * just increase the size of the current hilite by one.
967 * Otherwise (there are backspaces or something involved),
968 * finish the current hilite and start a new one.
970 for (i
= start_index
+1; i
<= end_index
; i
++)
972 if (chpos
[i
] != chpos
[i
-1] + 1 || i
== end_index
)
974 hl
.hl_endpos
= linepos
+ chpos
[i
-1] + 1;
975 add_hilite(&hilite_anchor
, &hl
);
976 /* Start new hilite unless this is the last char. */
979 hl
.hl_startpos
= linepos
+ chpos
[i
];
986 * Make a hilite for each string in a physical line which matches
987 * the current pattern.
988 * sp,ep delimit the first match already found.
991 hilite_line(linepos
, line
, line_len
, chpos
, sp
, ep
, cvt_ops
)
1001 char *line_end
= line
+ line_len
;
1004 * sp and ep delimit the first match in the line.
1005 * Mark the corresponding file positions, then
1006 * look for further matches and mark them.
1007 * {{ This technique, of calling match_pattern on subsequent
1008 * substrings of the line, may mark more than is correct
1009 * if the pattern starts with "^". This bug is fixed
1010 * for those regex functions that accept a notbol parameter
1011 * (currently POSIX, PCRE and V8-with-regexec2). }}
1015 if (sp
== NULL
|| ep
== NULL
)
1017 create_hilites(linepos
, sp
-line
, ep
-line
, chpos
);
1019 * If we matched more than zero characters,
1020 * move to the first char after the string we matched.
1021 * If we matched zero, just move to the next char.
1025 else if (searchp
!= line_end
)
1027 else /* end of line */
1029 } while (match_pattern(info_compiled(&search_info
), search_info
.text
,
1030 searchp
, line_end
- searchp
, &sp
, &ep
, 1, search_info
.search_type
));
1036 * Find matching text which is currently on screen and highlight it.
1039 hilite_screen(VOID_PARAM
)
1041 struct scrpos scrpos
;
1043 get_scrpos(&scrpos
, TOP
);
1044 if (scrpos
.pos
== NULL_POSITION
)
1046 prep_hilite(scrpos
.pos
, position(BOTTOM_PLUS_ONE
), -1);
1051 * Change highlighting parameters.
1054 chg_hilite(VOID_PARAM
)
1057 * Erase any highlights currently on screen.
1062 if (hilite_search
== OPT_ONPLUS
)
1064 * Display highlights.
1071 * Figure out where to start a search.
1074 search_pos(search_type
)
1083 * Start at the beginning (or end) of the file.
1084 * The empty_screen() case is mainly for
1085 * command line initiated searches;
1086 * for example, "+/xyz" on the command line.
1087 * Also for multi-file (SRCH_PAST_EOF) searches.
1089 if (search_type
& SRCH_FORW
)
1095 if (pos
== NULL_POSITION
)
1097 (void) ch_end_seek();
1106 if (how_search
== OPT_ON
)
1109 * Search does not include current screen.
1111 if (search_type
& SRCH_FORW
)
1112 sindex
= sc_height
-1; /* BOTTOM_PLUS_ONE */
1114 sindex
= 0; /* TOP */
1115 } else if (how_search
== OPT_ONPLUS
&& !(search_type
& SRCH_AFTER_TARGET
))
1118 * Search includes all of displayed screen.
1120 if (search_type
& SRCH_FORW
)
1121 sindex
= 0; /* TOP */
1123 sindex
= sc_height
-1; /* BOTTOM_PLUS_ONE */
1127 * Search includes the part of current screen beyond the jump target.
1128 * It starts at the jump target (if searching backwards),
1129 * or at the jump target plus one (if forwards).
1131 sindex
= sindex_from_sline(jump_sline
);
1132 if (search_type
& SRCH_FORW
)
1135 pos
= position(sindex
);
1137 pos
= forw_raw_line(pos
, (char **)NULL
, (int *)NULL
);
1141 * If the line is empty, look around for a plausible starting place.
1143 if (search_type
& SRCH_FORW
)
1145 while (pos
== NULL_POSITION
)
1147 if (++sindex
>= sc_height
)
1149 pos
= position(sindex
);
1153 while (pos
== NULL_POSITION
)
1157 pos
= position(sindex
);
1164 * Check to see if the line matches the filter pattern.
1165 * If so, add an entry to the filter list.
1169 matches_filters(pos
, cline
, line_len
, chpos
, linepos
, sp
, ep
)
1178 struct pattern_info
*filter
;
1180 for (filter
= filter_infos
; filter
!= NULL
; filter
= filter
->next
)
1182 int line_filter
= match_pattern(info_compiled(filter
), filter
->text
,
1183 cline
, line_len
, sp
, ep
, 0, filter
->search_type
);
1187 hl
.hl_startpos
= linepos
;
1189 add_hilite(&filter_anchor
, &hl
);
1200 * Get the position of the first char in the screen line which
1201 * puts tpos on screen.
1204 get_lastlinepos(pos
, tpos
, sheight
)
1211 for (nlines
= 0;; nlines
++)
1213 POSITION npos
= forw_line(pos
);
1216 if (nlines
< sheight
)
1217 return NULL_POSITION
;
1225 * Get the segment index of tpos in the line starting at pos.
1226 * A segment is a string of printable chars that fills the screen width.
1235 for (seg
= 0;; seg
++)
1237 POSITION npos
= forw_line_seg(pos
, FALSE
, FALSE
, TRUE
);
1245 * Search a subset of the file, specified by start/end position.
1248 search_range(pos
, endpos
, search_type
, matches
, maxlines
, plinepos
, pendpos
, plastlinepos
)
1256 POSITION
*plastlinepos
;
1267 POSITION linepos
, oldpos
;
1268 int swidth
= sc_width
- line_pfx_width();
1269 int sheight
= sc_height
- sindex_from_sline(jump_sline
);
1271 linenum
= find_linenum(pos
);
1273 /* When the search wraps around, end at starting position. */
1274 if ((search_type
& SRCH_WRAP
) && endpos
== NULL_POSITION
)
1279 * Get lines until we find a matching one or until
1280 * we hit end-of-file (or beginning-of-file if we're
1281 * going backwards), or until we hit the end position.
1286 * A signal aborts the search.
1291 if ((endpos
!= NULL_POSITION
&& !(search_type
& SRCH_WRAP
) &&
1292 (((search_type
& SRCH_FORW
) && pos
>= endpos
) ||
1293 ((search_type
& SRCH_BACK
) && pos
<= endpos
))) || maxlines
== 0)
1296 * Reached end position without a match.
1298 if (pendpos
!= NULL
)
1305 if (search_type
& SRCH_FORW
)
1308 * Read the next line, and save the
1309 * starting position of that line in linepos.
1312 pos
= forw_raw_line(pos
, &line
, &line_len
);
1318 * Read the previous line and save the
1319 * starting position of that line in linepos.
1321 pos
= back_raw_line(pos
, &line
, &line_len
);
1327 if (pos
== NULL_POSITION
)
1330 * Reached EOF/BOF without a match.
1332 if (search_type
& SRCH_WRAP
)
1335 * The search wraps around the current file, so
1336 * try to continue at BOF/EOF.
1338 if (search_type
& SRCH_FORW
)
1344 if (pos
== NULL_POSITION
)
1346 (void) ch_end_seek();
1350 if (pos
!= NULL_POSITION
) {
1352 * Wrap-around was successful. Clear
1353 * the flag so we don't wrap again, and
1354 * continue the search at new pos.
1356 search_type
&= ~SRCH_WRAP
;
1357 linenum
= find_linenum(pos
);
1361 if (pendpos
!= NULL
)
1367 * If we're using line numbers, we might as well
1368 * remember the information we have now (the position
1369 * and line number of the current line).
1370 * Don't do it for every line because it slows down
1371 * the search. Remember the line number only if
1372 * we're "far" from the last place we remembered it.
1374 if (linenums
&& abs((int)(pos
- oldpos
)) > 2048)
1375 add_lnum(linenum
, pos
);
1379 if (is_filtered(linepos
))
1384 * If it's a caseless search, convert the line to lowercase.
1385 * If we're doing backspace processing, delete backspaces.
1387 cvt_ops
= get_cvt_ops();
1388 cvt_len
= cvt_length(line_len
, cvt_ops
);
1389 cline
= (char *) ecalloc(1, cvt_len
);
1390 chpos
= cvt_alloc_chpos(cvt_len
);
1391 cvt_text(cline
, line
, chpos
, &line_len
, cvt_ops
);
1395 * If any filters are in effect, ignore non-matching lines.
1397 if (filter_infos
!= NULL
&&
1398 ((search_type
& SRCH_FIND_ALL
) ||
1399 prep_startpos
== NULL_POSITION
||
1400 linepos
< prep_startpos
|| linepos
>= prep_endpos
)) {
1401 if (matches_filters(pos
, cline
, line_len
, chpos
, linepos
, &sp
, &ep
))
1407 * Test the next line to see if we have a match.
1408 * We are successful if we either want a match and got one,
1409 * or if we want a non-match and got one.
1411 if (prev_pattern(&search_info
))
1413 line_match
= match_pattern(info_compiled(&search_info
), search_info
.text
,
1414 cline
, line_len
, &sp
, &ep
, 0, search_type
);
1420 if (search_type
& SRCH_FIND_ALL
)
1424 * We are supposed to find all matches in the range.
1425 * Just add the matches in this line to the
1426 * hilite list and keep searching.
1428 hilite_line(linepos
, cline
, line_len
, chpos
, sp
, ep
, cvt_ops
);
1430 } else if (--matches
<= 0)
1433 * Found the one match we're looking for.
1437 if (hilite_search
== OPT_ON
)
1440 * Clear the hilite list and add only
1441 * the matches in this one line.
1444 hilite_line(linepos
, cline
, line_len
, chpos
, sp
, ep
, cvt_ops
);
1450 * If necessary, shift horizontally to make sure
1451 * search match is fully visible.
1453 if (sp
!= NULL
&& ep
!= NULL
)
1455 int start_off
= sp
- cline
;
1456 int end_off
= ep
- cline
;
1457 int save_hshift
= hshift
;
1460 hshift
= 0; /* make get_seg count screen lines */
1461 sshift
= swidth
* get_seg(linepos
, linepos
+ chpos
[start_off
]);
1462 eshift
= swidth
* get_seg(linepos
, linepos
+ chpos
[end_off
]);
1463 if (sshift
>= save_hshift
&& eshift
<= save_hshift
)
1465 hshift
= save_hshift
;
1472 } else if (plastlinepos
!= NULL
)
1475 * If the line is so long that the highlighted match
1476 * won't be seen when the line is displayed normally
1477 * (starting at the first char) because it fills the whole
1478 * screen and more, scroll forward until the last char
1479 * of the match appears in the last line on the screen.
1480 * lastlinepos is the position of the first char of that last line.
1484 int end_off
= ep
- cline
;
1485 if (end_off
>= swidth
* sheight
/ 4) /* heuristic */
1486 *plastlinepos
= get_lastlinepos(linepos
, linepos
+ chpos
[end_off
], sheight
);
1491 if (plinepos
!= NULL
)
1492 *plinepos
= linepos
;
1503 * search for a pattern in history. If found, compile that pattern.
1506 hist_pattern(search_type
)
1512 set_mlist(ml_search
, 0);
1513 pattern
= cmd_lastpattern();
1514 if (pattern
== NULL
)
1517 if (set_pattern(&search_info
, pattern
, search_type
, 1) < 0)
1521 if (hilite_search
== OPT_ONPLUS
&& !hide_hilite
)
1526 #else /* CMD_HISTORY */
1528 #endif /* CMD_HISTORY */
1532 * Change the caseless-ness of searches.
1533 * Updates the internal search state to reflect a change in the -i flag.
1536 chg_caseless(VOID_PARAM
)
1538 if (!is_ucase_pattern
)
1541 * Pattern did not have uppercase.
1542 * Set the search caselessness to the global caselessness.
1544 is_caseless
= caseless
;
1546 * If regex handles caseless, we need to discard
1547 * the pattern which was compiled with the old caseless.
1549 if (!re_handles_caseless
)
1550 /* We handle caseless, so the pattern doesn't change. */
1554 * Regenerate the pattern using the new state.
1556 clear_pattern(&search_info
);
1557 (void) hist_pattern(search_info
.search_type
);
1561 * Search for the n-th occurrence of a specified pattern,
1562 * either forward or backward.
1563 * Return the number of matches not yet found in this file
1564 * (that is, n minus the number of matches found).
1565 * Return -1 if the search should be aborted.
1566 * Caller may continue the search in another file
1567 * if less than n matches are found in this file.
1570 search(search_type
, pattern
, n
)
1577 POSITION lastlinepos
= NULL_POSITION
;
1579 if (pattern
== NULL
|| *pattern
== '\0')
1582 * A null pattern means use the previously compiled pattern.
1584 search_type
|= SRCH_AFTER_TARGET
;
1585 if (!prev_pattern(&search_info
))
1587 int r
= hist_pattern(search_type
);
1589 error("No previous regular expression", NULL_PARG
);
1593 if ((search_type
& SRCH_NO_REGEX
) !=
1594 (search_info
.search_type
& SRCH_NO_REGEX
))
1596 error("Please re-enter search pattern", NULL_PARG
);
1600 if (hilite_search
== OPT_ON
|| status_col
)
1603 * Erase the highlights currently on screen.
1604 * If the search fails, we'll redisplay them later.
1608 if (hilite_search
== OPT_ONPLUS
&& hide_hilite
)
1611 * Highlight any matches currently on screen,
1612 * before we actually start the search.
1622 * Compile the pattern.
1624 int show_error
= !(search_type
& SRCH_INCR
);
1625 if (set_pattern(&search_info
, pattern
, search_type
, show_error
) < 0)
1628 if (hilite_search
|| status_col
)
1631 * Erase the highlights currently on screen.
1632 * Also permanently delete them from the hilite list.
1638 if (hilite_search
== OPT_ONPLUS
|| status_col
)
1641 * Highlight any matches currently on screen,
1642 * before we actually start the search.
1650 * Figure out where to start the search.
1652 pos
= search_pos(search_type
);
1653 opos
= position(sindex_from_sline(jump_sline
));
1654 if (pos
== NULL_POSITION
)
1657 * Can't find anyplace to start searching from.
1659 if (search_type
& SRCH_PAST_EOF
)
1662 if (hilite_search
== OPT_ON
|| status_col
)
1665 error("Nothing to search", NULL_PARG
);
1669 n
= search_range(pos
, NULL_POSITION
, search_type
, n
, -1,
1670 &pos
, (POSITION
*)NULL
, &lastlinepos
);
1674 * Search was unsuccessful.
1677 if ((hilite_search
== OPT_ON
|| status_col
) && n
> 0)
1679 * Redisplay old hilites.
1686 if (!(search_type
& SRCH_NO_MOVE
))
1689 * Go to the matching line.
1691 if (lastlinepos
!= NULL_POSITION
)
1692 jump_loc(lastlinepos
, BOTTOM
);
1693 else if (pos
!= opos
)
1694 jump_loc(pos
, jump_sline
);
1698 if (hilite_search
== OPT_ON
|| status_col
)
1700 * Display new hilites in the matching line.
1709 * Prepare hilites in a given range of the file.
1711 * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1712 * of the file that has been "prepared"; that is, scanned for matches for
1713 * the current search pattern, and hilites have been created for such matches.
1714 * If prep_startpos == NULL_POSITION, the prep region is empty.
1715 * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1716 * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1719 prep_hilite(spos
, epos
, maxlines
)
1724 POSITION nprep_startpos
= prep_startpos
;
1725 POSITION nprep_endpos
= prep_endpos
;
1732 * Search beyond where we're asked to search, so the prep region covers
1733 * more than we need. Do one big search instead of a bunch of small ones.
1735 #define SEARCH_MORE (3*size_linebuf)
1737 if (!prev_pattern(&search_info
) && !is_filtering())
1741 * Make sure our prep region always starts at the beginning of
1742 * a line. (search_range takes care of the end boundary below.)
1744 spos
= back_raw_line(spos
+1, (char **)NULL
, (int *)NULL
);
1747 * If we're limited to a max number of lines, figure out the
1748 * file position we should stop at.
1751 max_epos
= NULL_POSITION
;
1755 for (i
= 0; i
< maxlines
; i
++)
1756 max_epos
= forw_raw_line(max_epos
, (char **)NULL
, (int *)NULL
);
1761 * The range that we need to search (spos,epos); and the range that
1762 * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1765 if (prep_startpos
== NULL_POSITION
||
1766 (epos
!= NULL_POSITION
&& epos
< prep_startpos
) ||
1770 * New range is not contiguous with old prep region.
1771 * Discard the old prep region and start a new one.
1775 if (epos
!= NULL_POSITION
)
1776 epos
+= SEARCH_MORE
;
1777 nprep_startpos
= spos
;
1781 * New range partially or completely overlaps old prep region.
1783 if (epos
== NULL_POSITION
)
1786 * New range goes to end of file.
1789 } else if (epos
> prep_endpos
)
1792 * New range ends after old prep region.
1793 * Extend prep region to end at end of new range.
1795 epos
+= SEARCH_MORE
;
1796 } else /* (epos <= prep_endpos) */
1799 * New range ends within old prep region.
1800 * Truncate search to end at start of old prep region.
1802 epos
= prep_startpos
;
1805 if (spos
< prep_startpos
)
1808 * New range starts before old prep region.
1809 * Extend old prep region backwards to start at
1810 * start of new range.
1812 if (spos
< SEARCH_MORE
)
1815 spos
-= SEARCH_MORE
;
1816 nprep_startpos
= spos
;
1817 } else /* (spos >= prep_startpos) */
1820 * New range starts within or after old prep region.
1821 * Trim search to start at end of old prep region.
1827 if (epos
!= NULL_POSITION
&& max_epos
!= NULL_POSITION
&&
1830 * Don't go past the max position we're allowed.
1834 if (epos
== NULL_POSITION
|| epos
> spos
)
1836 int search_type
= SRCH_FORW
| SRCH_FIND_ALL
;
1837 search_type
|= (search_info
.search_type
& SRCH_NO_REGEX
);
1840 result
= search_range(spos
, epos
, search_type
, 0, maxlines
, (POSITION
*)NULL
, &new_epos
, (POSITION
*)NULL
);
1843 if (prep_endpos
== NULL_POSITION
|| new_epos
> prep_endpos
)
1844 nprep_endpos
= new_epos
;
1847 * Check both ends of the resulting prep region to
1848 * make sure they're not filtered. If they are,
1849 * keep going at least one more line until we find
1850 * something that isn't filtered, or hit the end.
1852 if (prep_endpos
== NULL_POSITION
|| nprep_endpos
> prep_endpos
)
1854 if (new_epos
>= nprep_endpos
&& is_filtered(new_epos
-1))
1856 spos
= nprep_endpos
;
1857 epos
= forw_raw_line(nprep_endpos
, (char **)NULL
, (int *)NULL
);
1858 if (epos
== NULL_POSITION
)
1865 if (prep_startpos
== NULL_POSITION
|| nprep_startpos
< prep_startpos
)
1867 if (nprep_startpos
> 0 && is_filtered(nprep_startpos
))
1869 epos
= nprep_startpos
;
1870 spos
= back_raw_line(nprep_startpos
, (char **)NULL
, (int *)NULL
);
1871 if (spos
== NULL_POSITION
)
1873 nprep_startpos
= spos
;
1881 prep_startpos
= nprep_startpos
;
1882 prep_endpos
= nprep_endpos
;
1886 * Set the pattern to be used for line filtering.
1889 set_filter_pattern(pattern
, search_type
)
1893 struct pattern_info
*filter
;
1896 if (pattern
== NULL
|| *pattern
== '\0')
1898 /* Clear and free all filters. */
1899 for (filter
= filter_infos
; filter
!= NULL
; )
1901 struct pattern_info
*next_filter
= filter
->next
;
1902 clear_pattern(filter
);
1904 filter
= next_filter
;
1906 filter_infos
= NULL
;
1909 /* Create a new filter and add it to the filter_infos list. */
1910 filter
= ecalloc(1, sizeof(struct pattern_info
));
1911 init_pattern(filter
);
1912 if (set_pattern(filter
, pattern
, search_type
, 1) < 0)
1917 filter
->next
= filter_infos
;
1918 filter_infos
= filter
;
1924 * Is there a line filter in effect?
1927 is_filtering(VOID_PARAM
)
1929 if (ch_getflags() & CH_HELPFILE
)
1931 return (filter_infos
!= NULL
);
1937 * This function is called by the V8 regcomp to report
1938 * errors in regular expressions.
1940 public int reg_show_error
= 1;
1948 if (!reg_show_error
)