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