search.c

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