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