contrib/less/search.c

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