search.c

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