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