search.c

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