1 /* 2 * Copyright (C) 1984-2014 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 78 struct hilite r; 79 }; 80 struct hilite_storage 81 { 82 int capacity; 83 int used; 84 struct hilite_storage *next; 85 }; 86 struct hilite_tree 87 { 88 struct hilite_storage *first; 89 struct hilite_storage *current; 90 struct hilite_node *root; 91 92 struct hilite_node *lookaside; 93 }; 94 #define HILITE_INITIALIZER() { NULL, NULL, NULL, NULL } 95 #define HILITE_LOOKASIDE_STEPS 2 96 97 static struct hilite_tree hilite_anchor = HILITE_INITIALIZER(); 98 static struct hilite_tree filter_anchor = HILITE_INITIALIZER(); 99 100 #endif 101 102 /* 103 * These are the static variables that represent the "remembered" 104 * search pattern and filter pattern. 105 */ 106 struct pattern_info { 107 DEFINE_PATTERN(compiled); 108 char* text; 109 int search_type; 110 }; 111 112 #if NO_REGEX 113 #define info_compiled(info) ((void*)0) 114 #else 115 #define info_compiled(info) ((info)->compiled) 116 #endif 117 118 static struct pattern_info search_info; 119 static struct pattern_info filter_info; 120 121 /* 122 * Are there any uppercase letters in this string? 123 */ 124 static int 125 is_ucase(str) 126 char *str; 127 { 128 char *str_end = str + strlen(str); 129 LWCHAR ch; 130 131 while (str < str_end) 132 { 133 ch = step_char(&str, +1, str_end); 134 if (IS_UPPER(ch)) 135 return (1); 136 } 137 return (0); 138 } 139 140 /* 141 * Compile and save a search pattern. 142 */ 143 static int 144 set_pattern(info, pattern, search_type) 145 struct pattern_info *info; 146 char *pattern; 147 int search_type; 148 { 149 #if !NO_REGEX 150 if (pattern == NULL) 151 CLEAR_PATTERN(info->compiled); 152 else if (compile_pattern(pattern, search_type, &info->compiled) < 0) 153 return -1; 154 #endif 155 /* Pattern compiled successfully; save the text too. */ 156 if (info->text != NULL) 157 free(info->text); 158 info->text = NULL; 159 if (pattern != NULL) 160 { 161 info->text = (char *) ecalloc(1, strlen(pattern)+1); 162 strcpy(info->text, pattern); 163 } 164 info->search_type = search_type; 165 166 /* 167 * Ignore case if -I is set OR 168 * -i is set AND the pattern is all lowercase. 169 */ 170 is_ucase_pattern = is_ucase(pattern); 171 if (is_ucase_pattern && caseless != OPT_ONPLUS) 172 is_caseless = 0; 173 else 174 is_caseless = caseless; 175 return 0; 176 } 177 178 /* 179 * Discard a saved pattern. 180 */ 181 static void 182 clear_pattern(info) 183 struct pattern_info *info; 184 { 185 if (info->text != NULL) 186 free(info->text); 187 info->text = NULL; 188 #if !NO_REGEX 189 uncompile_pattern(&info->compiled); 190 #endif 191 } 192 193 /* 194 * Initialize saved pattern to nothing. 195 */ 196 static void 197 init_pattern(info) 198 struct pattern_info *info; 199 { 200 CLEAR_PATTERN(info->compiled); 201 info->text = NULL; 202 info->search_type = 0; 203 } 204 205 /* 206 * Initialize search variables. 207 */ 208 public void 209 init_search() 210 { 211 init_pattern(&search_info); 212 init_pattern(&filter_info); 213 } 214 215 /* 216 * Determine which text conversions to perform before pattern matching. 217 */ 218 static int 219 get_cvt_ops() 220 { 221 int ops = 0; 222 if (is_caseless || bs_mode == BS_SPECIAL) 223 { 224 if (is_caseless) 225 ops |= CVT_TO_LC; 226 if (bs_mode == BS_SPECIAL) 227 ops |= CVT_BS; 228 if (bs_mode != BS_CONTROL) 229 ops |= CVT_CRLF; 230 } else if (bs_mode != BS_CONTROL) 231 { 232 ops |= CVT_CRLF; 233 } 234 if (ctldisp == OPT_ONPLUS) 235 ops |= CVT_ANSI; 236 return (ops); 237 } 238 239 /* 240 * Is there a previous (remembered) search pattern? 241 */ 242 static int 243 prev_pattern(info) 244 struct pattern_info *info; 245 { 246 #if !NO_REGEX 247 if ((info->search_type & SRCH_NO_REGEX) == 0) 248 return (!is_null_pattern(info->compiled)); 249 #endif 250 return (info->text != NULL); 251 } 252 253 #if HILITE_SEARCH 254 /* 255 * Repaint the hilites currently displayed on the screen. 256 * Repaint each line which contains highlighted text. 257 * If on==0, force all hilites off. 258 */ 259 public void 260 repaint_hilite(on) 261 int on; 262 { 263 int slinenum; 264 POSITION pos; 265 int save_hide_hilite; 266 267 if (squished) 268 repaint(); 269 270 save_hide_hilite = hide_hilite; 271 if (!on) 272 { 273 if (hide_hilite) 274 return; 275 hide_hilite = 1; 276 } 277 278 if (!can_goto_line) 279 { 280 repaint(); 281 hide_hilite = save_hide_hilite; 282 return; 283 } 284 285 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++) 286 { 287 pos = position(slinenum); 288 if (pos == NULL_POSITION) 289 continue; 290 (void) forw_line(pos); 291 goto_line(slinenum); 292 put_line(); 293 } 294 lower_left(); 295 hide_hilite = save_hide_hilite; 296 } 297 298 /* 299 * Clear the attn hilite. 300 */ 301 public void 302 clear_attn() 303 { 304 int slinenum; 305 POSITION old_start_attnpos; 306 POSITION old_end_attnpos; 307 POSITION pos; 308 POSITION epos; 309 int moved = 0; 310 311 if (start_attnpos == NULL_POSITION) 312 return; 313 old_start_attnpos = start_attnpos; 314 old_end_attnpos = end_attnpos; 315 start_attnpos = end_attnpos = NULL_POSITION; 316 317 if (!can_goto_line) 318 { 319 repaint(); 320 return; 321 } 322 if (squished) 323 repaint(); 324 325 for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++) 326 { 327 pos = position(slinenum); 328 if (pos == NULL_POSITION) 329 continue; 330 epos = position(slinenum+1); 331 if (pos < old_end_attnpos && 332 (epos == NULL_POSITION || epos > old_start_attnpos)) 333 { 334 (void) forw_line(pos); 335 goto_line(slinenum); 336 put_line(); 337 moved = 1; 338 } 339 } 340 if (moved) 341 lower_left(); 342 } 343 #endif 344 345 /* 346 * Hide search string highlighting. 347 */ 348 public void 349 undo_search() 350 { 351 if (!prev_pattern(&search_info)) 352 { 353 error("No previous regular expression", NULL_PARG); 354 return; 355 } 356 #if HILITE_SEARCH 357 hide_hilite = !hide_hilite; 358 repaint_hilite(1); 359 #endif 360 } 361 362 #if HILITE_SEARCH 363 /* 364 * Clear the hilite list. 365 */ 366 public void 367 clr_hlist(anchor) 368 struct hilite_tree *anchor; 369 { 370 struct hilite_storage *hls; 371 struct hilite_storage *nexthls; 372 373 for (hls = anchor->first; hls != NULL; hls = nexthls) 374 { 375 nexthls = hls->next; 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 int allocsize = sizeof(struct hilite_storage); 655 struct hilite_storage *s; 656 657 if (anchor->current) 658 { 659 if (anchor->current->used < anchor->current->capacity) 660 return anchor->current; 661 capacity = anchor->current->capacity * 2; 662 } 663 allocsize += capacity * sizeof(struct hilite_node); 664 s = ecalloc(1, allocsize); 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 686 struct hilite_node *n = ((struct hilite_node*)(s+1))+s->used; 687 s->used++; 688 return n; 689 } 690 691 /* 692 * Rotate the tree left around a pivot node. 693 */ 694 static void 695 hlist_rotate_left(anchor, n) 696 struct hilite_tree *anchor; 697 struct hilite_node *n; 698 { 699 struct hilite_node *np = n->parent; 700 struct hilite_node *nr = n->right; 701 struct hilite_node *nrl = n->right->left; 702 703 if (np != NULL) 704 { 705 if (n == np->left) 706 np->left = nr; 707 else 708 np->right = nr; 709 } else 710 { 711 anchor->root = nr; 712 } 713 nr->left = n; 714 n->right = nrl; 715 716 nr->parent = np; 717 n->parent = nr; 718 if (nrl != NULL) 719 nrl->parent = n; 720 } 721 722 /* 723 * Rotate the tree right around a pivot node. 724 */ 725 static void 726 hlist_rotate_right(anchor, n) 727 struct hilite_tree *anchor; 728 struct hilite_node *n; 729 { 730 struct hilite_node *np = n->parent; 731 struct hilite_node *nl = n->left; 732 struct hilite_node *nlr = n->left->right; 733 734 if (np != NULL) 735 { 736 if (n == np->right) 737 np->right = nl; 738 else 739 np->left = nl; 740 } else 741 { 742 anchor->root = nl; 743 } 744 nl->right = n; 745 n->left = nlr; 746 747 nl->parent = np; 748 n->parent = nl; 749 if (nlr != NULL) 750 nlr->parent = n; 751 } 752 753 754 /* 755 * Add a new hilite to a hilite list. 756 */ 757 static void 758 add_hilite(anchor, hl) 759 struct hilite_tree *anchor; 760 struct hilite *hl; 761 { 762 struct hilite_node *p, *n, *u; 763 764 /* Ignore empty ranges. */ 765 if (hl->hl_startpos >= hl->hl_endpos) 766 return; 767 768 p = anchor->root; 769 770 /* Inserting the very first node is trivial. */ 771 if (p == NULL) 772 { 773 n = hlist_getnode(anchor); 774 n->r = *hl; 775 anchor->root = n; 776 anchor->lookaside = n; 777 return; 778 } 779 780 /* 781 * Find our insertion point. If we come across any overlapping 782 * or adjoining existing ranges, shrink our range and discard 783 * if it become empty. 784 */ 785 for (;;) 786 { 787 if (hl->hl_startpos < p->r.hl_startpos) 788 { 789 if (hl->hl_endpos > p->r.hl_startpos) 790 hl->hl_endpos = p->r.hl_startpos; 791 if (p->left != NULL) 792 { 793 p = p->left; 794 continue; 795 } 796 break; 797 } 798 if (hl->hl_startpos < p->r.hl_endpos) { 799 hl->hl_startpos = p->r.hl_endpos; 800 if (hl->hl_startpos >= hl->hl_endpos) 801 return; 802 } 803 if (p->right != NULL) 804 { 805 p = p->right; 806 continue; 807 } 808 break; 809 } 810 811 /* 812 * Now we're at the right leaf, again check for contiguous ranges 813 * and extend the existing node if possible to avoid the 814 * insertion. Otherwise insert a new node at the leaf. 815 */ 816 if (hl->hl_startpos < p->r.hl_startpos) { 817 if (hl->hl_endpos == p->r.hl_startpos) 818 { 819 p->r.hl_startpos = hl->hl_startpos; 820 return; 821 } 822 if (p->prev != NULL && p->prev->r.hl_endpos == hl->hl_startpos) 823 { 824 p->prev->r.hl_endpos = hl->hl_endpos; 825 return; 826 } 827 828 p->left = n = hlist_getnode(anchor); 829 n->next = p; 830 if (p->prev != NULL) 831 { 832 n->prev = p->prev; 833 p->prev->next = n; 834 } 835 p->prev = n; 836 } else { 837 if (p->r.hl_endpos == hl->hl_startpos) 838 { 839 p->r.hl_endpos = hl->hl_endpos; 840 return; 841 } 842 if (p->next != NULL && hl->hl_endpos == p->next->r.hl_startpos) { 843 p->next->r.hl_startpos = hl->hl_startpos; 844 return; 845 } 846 847 p->right = n = hlist_getnode(anchor); 848 n->prev = p; 849 if (p->next != NULL) 850 { 851 n->next = p->next; 852 p->next->prev = n; 853 } 854 p->next = n; 855 } 856 n->parent = p; 857 n->red = 1; 858 n->r = *hl; 859 860 /* 861 * The tree is in the correct order and covers the right ranges 862 * now, but may have become unbalanced. Rebalance it using the 863 * standard red-black tree constraints and operations. 864 */ 865 for (;;) 866 { 867 /* case 1 - current is root, root is always black */ 868 if (n->parent == NULL) 869 { 870 n->red = 0; 871 break; 872 } 873 874 /* case 2 - parent is black, we can always be red */ 875 if (!n->parent->red) 876 break; 877 878 /* 879 * constraint: because the root must be black, if our 880 * parent is red it cannot be the root therefore we must 881 * have a grandparent 882 */ 883 884 /* 885 * case 3 - parent and uncle are red, repaint them black, 886 * the grandparent red, and start again at the grandparent. 887 */ 888 u = n->parent->parent->left; 889 if (n->parent == u) 890 u = n->parent->parent->right; 891 if (u != NULL && u->red) 892 { 893 n->parent->red = 0; 894 u->red = 0; 895 n = n->parent->parent; 896 n->red = 1; 897 continue; 898 } 899 900 /* 901 * case 4 - parent is red but uncle is black, parent and 902 * grandparent on opposite sides. We need to start 903 * changing the structure now. This and case 5 will shorten 904 * our branch and lengthen the sibling, between them 905 * restoring balance. 906 */ 907 if (n == n->parent->right && 908 n->parent == n->parent->parent->left) 909 { 910 hlist_rotate_left(anchor, n->parent); 911 n = n->left; 912 } else if (n == n->parent->left && 913 n->parent == n->parent->parent->right) 914 { 915 hlist_rotate_right(anchor, n->parent); 916 n = n->right; 917 } 918 919 /* 920 * case 5 - parent is red but uncle is black, parent and 921 * grandparent on same side 922 */ 923 n->parent->red = 0; 924 n->parent->parent->red = 1; 925 if (n == n->parent->left) 926 hlist_rotate_right(anchor, n->parent->parent); 927 else 928 hlist_rotate_left(anchor, n->parent->parent); 929 break; 930 } 931 } 932 933 /* 934 * Hilight every character in a range of displayed characters. 935 */ 936 static void 937 create_hilites(linepos, start_index, end_index, chpos) 938 POSITION linepos; 939 int start_index; 940 int end_index; 941 int *chpos; 942 { 943 struct hilite hl; 944 int i; 945 946 /* Start the first hilite. */ 947 hl.hl_startpos = linepos + chpos[start_index]; 948 949 /* 950 * Step through the displayed chars. 951 * If the source position (before cvt) of the char is one more 952 * than the source pos of the previous char (the usual case), 953 * just increase the size of the current hilite by one. 954 * Otherwise (there are backspaces or something involved), 955 * finish the current hilite and start a new one. 956 */ 957 for (i = start_index+1; i <= end_index; i++) 958 { 959 if (chpos[i] != chpos[i-1] + 1 || i == end_index) 960 { 961 hl.hl_endpos = linepos + chpos[i-1] + 1; 962 add_hilite(&hilite_anchor, &hl); 963 /* Start new hilite unless this is the last char. */ 964 if (i < end_index) 965 { 966 hl.hl_startpos = linepos + chpos[i]; 967 } 968 } 969 } 970 } 971 972 /* 973 * Make a hilite for each string in a physical line which matches 974 * the current pattern. 975 * sp,ep delimit the first match already found. 976 */ 977 static void 978 hilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops) 979 POSITION linepos; 980 char *line; 981 int line_len; 982 int *chpos; 983 char *sp; 984 char *ep; 985 int cvt_ops; 986 { 987 char *searchp; 988 char *line_end = line + line_len; 989 990 if (sp == NULL || ep == NULL) 991 return; 992 /* 993 * sp and ep delimit the first match in the line. 994 * Mark the corresponding file positions, then 995 * look for further matches and mark them. 996 * {{ This technique, of calling match_pattern on subsequent 997 * substrings of the line, may mark more than is correct 998 * if the pattern starts with "^". This bug is fixed 999 * for those regex functions that accept a notbol parameter 1000 * (currently POSIX, PCRE and V8-with-regexec2). }} 1001 */ 1002 searchp = line; 1003 do { 1004 create_hilites(linepos, sp-line, ep-line, chpos); 1005 /* 1006 * If we matched more than zero characters, 1007 * move to the first char after the string we matched. 1008 * If we matched zero, just move to the next char. 1009 */ 1010 if (ep > searchp) 1011 searchp = ep; 1012 else if (searchp != line_end) 1013 searchp++; 1014 else /* end of line */ 1015 break; 1016 } while (match_pattern(info_compiled(&search_info), search_info.text, 1017 searchp, line_end - searchp, &sp, &ep, 1, search_info.search_type)); 1018 } 1019 #endif 1020 1021 /* 1022 * Change the caseless-ness of searches. 1023 * Updates the internal search state to reflect a change in the -i flag. 1024 */ 1025 public void 1026 chg_caseless() 1027 { 1028 if (!is_ucase_pattern) 1029 /* 1030 * Pattern did not have uppercase. 1031 * Just set the search caselessness to the global caselessness. 1032 */ 1033 is_caseless = caseless; 1034 else 1035 /* 1036 * Pattern did have uppercase. 1037 * Discard the pattern; we can't change search caselessness now. 1038 */ 1039 clear_pattern(&search_info); 1040 } 1041 1042 #if HILITE_SEARCH 1043 /* 1044 * Find matching text which is currently on screen and highlight it. 1045 */ 1046 static void 1047 hilite_screen() 1048 { 1049 struct scrpos scrpos; 1050 1051 get_scrpos(&scrpos); 1052 if (scrpos.pos == NULL_POSITION) 1053 return; 1054 prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1); 1055 repaint_hilite(1); 1056 } 1057 1058 /* 1059 * Change highlighting parameters. 1060 */ 1061 public void 1062 chg_hilite() 1063 { 1064 /* 1065 * Erase any highlights currently on screen. 1066 */ 1067 clr_hilite(); 1068 hide_hilite = 0; 1069 1070 if (hilite_search == OPT_ONPLUS) 1071 /* 1072 * Display highlights. 1073 */ 1074 hilite_screen(); 1075 } 1076 #endif 1077 1078 /* 1079 * Figure out where to start a search. 1080 */ 1081 static POSITION 1082 search_pos(search_type) 1083 int search_type; 1084 { 1085 POSITION pos; 1086 int linenum; 1087 1088 if (empty_screen()) 1089 { 1090 /* 1091 * Start at the beginning (or end) of the file. 1092 * The empty_screen() case is mainly for 1093 * command line initiated searches; 1094 * for example, "+/xyz" on the command line. 1095 * Also for multi-file (SRCH_PAST_EOF) searches. 1096 */ 1097 if (search_type & SRCH_FORW) 1098 { 1099 pos = ch_zero(); 1100 } else 1101 { 1102 pos = ch_length(); 1103 if (pos == NULL_POSITION) 1104 { 1105 (void) ch_end_seek(); 1106 pos = ch_length(); 1107 } 1108 } 1109 linenum = 0; 1110 } else 1111 { 1112 int add_one = 0; 1113 1114 if (how_search == OPT_ON) 1115 { 1116 /* 1117 * Search does not include current screen. 1118 */ 1119 if (search_type & SRCH_FORW) 1120 linenum = BOTTOM_PLUS_ONE; 1121 else 1122 linenum = TOP; 1123 } else if (how_search == OPT_ONPLUS && !(search_type & SRCH_AFTER_TARGET)) 1124 { 1125 /* 1126 * Search includes all of displayed screen. 1127 */ 1128 if (search_type & SRCH_FORW) 1129 linenum = TOP; 1130 else 1131 linenum = BOTTOM_PLUS_ONE; 1132 } else 1133 { 1134 /* 1135 * Search includes the part of current screen beyond the jump target. 1136 * It starts at the jump target (if searching backwards), 1137 * or at the jump target plus one (if forwards). 1138 */ 1139 linenum = jump_sline; 1140 if (search_type & SRCH_FORW) 1141 add_one = 1; 1142 } 1143 linenum = adjsline(linenum); 1144 pos = position(linenum); 1145 if (add_one) 1146 pos = forw_raw_line(pos, (char **)NULL, (int *)NULL); 1147 } 1148 1149 /* 1150 * If the line is empty, look around for a plausible starting place. 1151 */ 1152 if (search_type & SRCH_FORW) 1153 { 1154 while (pos == NULL_POSITION) 1155 { 1156 if (++linenum >= sc_height) 1157 break; 1158 pos = position(linenum); 1159 } 1160 } else 1161 { 1162 while (pos == NULL_POSITION) 1163 { 1164 if (--linenum < 0) 1165 break; 1166 pos = position(linenum); 1167 } 1168 } 1169 return (pos); 1170 } 1171 1172 /* 1173 * Search a subset of the file, specified by start/end position. 1174 */ 1175 static int 1176 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos) 1177 POSITION pos; 1178 POSITION endpos; 1179 int search_type; 1180 int matches; 1181 int maxlines; 1182 POSITION *plinepos; 1183 POSITION *pendpos; 1184 { 1185 char *line; 1186 char *cline; 1187 int line_len; 1188 LINENUM linenum; 1189 char *sp, *ep; 1190 int line_match; 1191 int cvt_ops; 1192 int cvt_len; 1193 int *chpos; 1194 POSITION linepos, oldpos; 1195 1196 linenum = find_linenum(pos); 1197 oldpos = pos; 1198 for (;;) 1199 { 1200 /* 1201 * Get lines until we find a matching one or until 1202 * we hit end-of-file (or beginning-of-file if we're 1203 * going backwards), or until we hit the end position. 1204 */ 1205 if (ABORT_SIGS()) 1206 { 1207 /* 1208 * A signal aborts the search. 1209 */ 1210 return (-1); 1211 } 1212 1213 if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0) 1214 { 1215 /* 1216 * Reached end position without a match. 1217 */ 1218 if (pendpos != NULL) 1219 *pendpos = pos; 1220 return (matches); 1221 } 1222 if (maxlines > 0) 1223 maxlines--; 1224 1225 if (search_type & SRCH_FORW) 1226 { 1227 /* 1228 * Read the next line, and save the 1229 * starting position of that line in linepos. 1230 */ 1231 linepos = pos; 1232 pos = forw_raw_line(pos, &line, &line_len); 1233 if (linenum != 0) 1234 linenum++; 1235 } else 1236 { 1237 /* 1238 * Read the previous line and save the 1239 * starting position of that line in linepos. 1240 */ 1241 pos = back_raw_line(pos, &line, &line_len); 1242 linepos = pos; 1243 if (linenum != 0) 1244 linenum--; 1245 } 1246 1247 if (pos == NULL_POSITION) 1248 { 1249 /* 1250 * Reached EOF/BOF without a match. 1251 */ 1252 if (pendpos != NULL) 1253 *pendpos = oldpos; 1254 return (matches); 1255 } 1256 1257 /* 1258 * If we're using line numbers, we might as well 1259 * remember the information we have now (the position 1260 * and line number of the current line). 1261 * Don't do it for every line because it slows down 1262 * the search. Remember the line number only if 1263 * we're "far" from the last place we remembered it. 1264 */ 1265 if (linenums && abs((int)(pos - oldpos)) > 2048) 1266 add_lnum(linenum, pos); 1267 oldpos = pos; 1268 1269 if (is_filtered(linepos)) 1270 continue; 1271 1272 /* 1273 * If it's a caseless search, convert the line to lowercase. 1274 * If we're doing backspace processing, delete backspaces. 1275 */ 1276 cvt_ops = get_cvt_ops(); 1277 cvt_len = cvt_length(line_len, cvt_ops); 1278 cline = (char *) ecalloc(1, cvt_len); 1279 chpos = cvt_alloc_chpos(cvt_len); 1280 cvt_text(cline, line, chpos, &line_len, cvt_ops); 1281 1282 #if HILITE_SEARCH 1283 /* 1284 * Check to see if the line matches the filter pattern. 1285 * If so, add an entry to the filter list. 1286 */ 1287 if (((search_type & SRCH_FIND_ALL) || 1288 prep_startpos == NULL_POSITION || 1289 linepos < prep_startpos || linepos >= prep_endpos) && 1290 prev_pattern(&filter_info)) { 1291 int line_filter = match_pattern(info_compiled(&filter_info), filter_info.text, 1292 cline, line_len, &sp, &ep, 0, filter_info.search_type); 1293 if (line_filter) 1294 { 1295 struct hilite hl; 1296 hl.hl_startpos = linepos; 1297 hl.hl_endpos = pos; 1298 add_hilite(&filter_anchor, &hl); 1299 continue; 1300 } 1301 } 1302 #endif 1303 1304 /* 1305 * Test the next line to see if we have a match. 1306 * We are successful if we either want a match and got one, 1307 * or if we want a non-match and got one. 1308 */ 1309 if (prev_pattern(&search_info)) 1310 { 1311 line_match = match_pattern(info_compiled(&search_info), search_info.text, 1312 cline, line_len, &sp, &ep, 0, search_type); 1313 if (line_match) 1314 { 1315 /* 1316 * Got a match. 1317 */ 1318 if (search_type & SRCH_FIND_ALL) 1319 { 1320 #if HILITE_SEARCH 1321 /* 1322 * We are supposed to find all matches in the range. 1323 * Just add the matches in this line to the 1324 * hilite list and keep searching. 1325 */ 1326 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops); 1327 #endif 1328 } else if (--matches <= 0) 1329 { 1330 /* 1331 * Found the one match we're looking for. 1332 * Return it. 1333 */ 1334 #if HILITE_SEARCH 1335 if (hilite_search == OPT_ON) 1336 { 1337 /* 1338 * Clear the hilite list and add only 1339 * the matches in this one line. 1340 */ 1341 clr_hilite(); 1342 hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops); 1343 } 1344 #endif 1345 free(cline); 1346 free(chpos); 1347 if (plinepos != NULL) 1348 *plinepos = linepos; 1349 return (0); 1350 } 1351 } 1352 } 1353 free(cline); 1354 free(chpos); 1355 } 1356 } 1357 1358 /* 1359 * search for a pattern in history. If found, compile that pattern. 1360 */ 1361 static int 1362 hist_pattern(search_type) 1363 int search_type; 1364 { 1365 #if CMD_HISTORY 1366 char *pattern; 1367 1368 set_mlist(ml_search, 0); 1369 pattern = cmd_lastpattern(); 1370 if (pattern == NULL) 1371 return (0); 1372 1373 if (set_pattern(&search_info, pattern, search_type) < 0) 1374 return (0); 1375 1376 #if HILITE_SEARCH 1377 if (hilite_search == OPT_ONPLUS && !hide_hilite) 1378 hilite_screen(); 1379 #endif 1380 1381 return (1); 1382 #else /* CMD_HISTORY */ 1383 return (0); 1384 #endif /* CMD_HISTORY */ 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