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