contrib/less/search.c

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