search.c

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