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