contrib/less/search.c

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