contrib/less/search.c

   1 /* $FreeBSD$ */
   2 /*
   3  * Copyright (C) 1984-2000  Mark Nudelman
   4  *
   5  * You may distribute under the terms of either the GNU General Public
   6  * License or the Less License, as specified in the README file.
   7  *
   8  * For more information about less, or for information on how to
   9  * contact the author, see the README file.
  10  */
  11
  12
  13 /*
  14  * Routines to search a file for a pattern.
  15  */
  16
  17 #include "less.h"
  18 #include "position.h"
  19
  20 #define MINPOS(a,b)     (((a) < (b)) ? (a) : (b))
  21 #define MAXPOS(a,b)     (((a) > (b)) ? (a) : (b))
  22
  23 #if HAVE_POSIX_REGCOMP
  24 #include <regex.h>
  25 #ifdef REG_EXTENDED
  26 #define REGCOMP_FLAG    (more_mode ? 0 : REG_EXTENDED)
  27 #else
  28 #define REGCOMP_FLAG    0
  29 #endif
  30 #endif
  31 #if HAVE_PCRE
  32 #include <pcre.h>
  33 #endif
  34 #if HAVE_RE_COMP
  35 char *re_comp();
  36 int re_exec();
  37 #endif
  38 #if HAVE_REGCMP
  39 char *regcmp();
  40 char *regex();
  41 extern char *__loc1;
  42 #endif
  43 #if HAVE_V8_REGCOMP
  44 #include "regexp.h"
  45 #endif
  46
  47 static int match();
  48
  49 extern int sigs;
  50 extern int how_search;
  51 extern int caseless;
  52 extern int linenums;
  53 extern int sc_height;
  54 extern int jump_sline;
  55 extern int bs_mode;
  56 extern int more_mode;
  57 extern int status_col;
  58 extern POSITION start_attnpos;
  59 extern POSITION end_attnpos;
  60 #if HILITE_SEARCH
  61 extern int hilite_search;
  62 extern int screen_trashed;
  63 extern int size_linebuf;
  64 extern int squished;
  65 extern int can_goto_line;
  66 static int hide_hilite;
  67 static POSITION prep_startpos;
  68 static POSITION prep_endpos;
  69
  70 struct hilite
  71 {
  72         struct hilite *hl_next;
  73         POSITION hl_startpos;
  74         POSITION hl_endpos;
  75 };
  76 static struct hilite hilite_anchor = { NULL, NULL_POSITION, NULL_POSITION };
  77 #define hl_first        hl_next
  78 #endif
  79
  80 /*
  81  * These are the static variables that represent the "remembered"
  82  * search pattern.
  83  */
  84 #if HAVE_POSIX_REGCOMP
  85 static regex_t *regpattern = NULL;
  86 #endif
  87 #if HAVE_PCRE
  88 pcre *regpattern = NULL;
  89 #endif
  90 #if HAVE_RE_COMP
  91 int re_pattern = 0;
  92 #endif
  93 #if HAVE_REGCMP
  94 static char *cpattern = NULL;
  95 #endif
  96 #if HAVE_V8_REGCOMP
  97 static struct regexp *regpattern = NULL;
  98 #endif
  99
 100 static int is_caseless;
 101 static int is_ucase_pattern;
 102 static int last_search_type;
 103 static char *last_pattern = NULL;
 104
 105 /*
 106  * Convert text.  Perform one or more of these transformations:
 107  */
 108 #define CVT_TO_LC       01      /* Convert upper-case to lower-case */
 109 #define CVT_BS          02      /* Do backspace processing */
 110 #define CVT_CRLF        04      /* Remove CR after LF */
 111
 112         static void
 113 cvt_text(odst, osrc, ops)
 114         char *odst;
 115         char *osrc;
 116         int ops;
 117 {
 118         register char *dst;
 119         register char *src;
 120
 121         for (src = osrc, dst = odst;  *src != '\0';  src++, dst++)
 122         {
 123                 if ((ops & CVT_TO_LC) && isupper((unsigned char) *src))
 124                         /* Convert uppercase to lowercase. */
 125                         *dst = tolower((unsigned char) *src);
 126                 else if ((ops & CVT_BS) && *src == '\b' && dst > odst)
 127                         /* Delete BS and preceding char. */
 128                         dst -= 2;
 129                 else
 130                         /* Just copy. */
 131                         *dst = *src;
 132         }
 133         if ((ops & CVT_CRLF) && dst > odst && dst[-1] == '\r')
 134                 dst--;
 135         *dst = '\0';
 136 }
 137
 138 /*
 139  * Are there any uppercase letters in this string?
 140  */
 141         static int
 142 is_ucase(s)
 143         char *s;
 144 {
 145         register char *p;
 146
 147         for (p = s;  *p != '\0';  p++)
 148                 if (isupper((unsigned char) *p))
 149                         return (1);
 150         return (0);
 151 }
 152
 153 /*
 154  * Is there a previous (remembered) search pattern?
 155  */
 156         static int
 157 prev_pattern()
 158 {
 159         if (last_search_type & SRCH_NO_REGEX)
 160                 return (last_pattern != NULL);
 161 #if HAVE_POSIX_REGCOMP
 162         return (regpattern != NULL);
 163 #endif
 164 #if HAVE_PCRE
 165         return (regpattern != NULL);
 166 #endif
 167 #if HAVE_RE_COMP
 168         return (re_pattern != 0);
 169 #endif
 170 #if HAVE_REGCMP
 171         return (cpattern != NULL);
 172 #endif
 173 #if HAVE_V8_REGCOMP
 174         return (regpattern != NULL);
 175 #endif
 176 #if NO_REGEX
 177         return (last_pattern != NULL);
 178 #endif
 179 }
 180
 181 #if HILITE_SEARCH
 182 /*
 183  * Repaint the hilites currently displayed on the screen.
 184  * Repaint each line which contains highlighted text.
 185  * If on==0, force all hilites off.
 186  */
 187         public void
 188 repaint_hilite(on)
 189         int on;
 190 {
 191         int slinenum;
 192         POSITION pos;
 193         POSITION epos;
 194         int save_hide_hilite;
 195
 196         if (squished)
 197                 repaint();
 198
 199         save_hide_hilite = hide_hilite;
 200         if (!on)
 201         {
 202                 if (hide_hilite)
 203                         return;
 204                 hide_hilite = 1;
 205         }
 206
 207         if (!can_goto_line)
 208         {
 209                 repaint();
 210                 hide_hilite = save_hide_hilite;
 211                 return;
 212         }
 213
 214         for (slinenum = TOP;  slinenum < TOP + sc_height-1;  slinenum++)
 215         {
 216                 pos = position(slinenum);
 217                 if (pos == NULL_POSITION)
 218                         continue;
 219                 epos = position(slinenum+1);
 220                 /*
 221                  * If any character in the line is highlighted,
 222                  * repaint the line.
 223                  */
 224                 if (is_hilited(pos, epos, 1))
 225                 {
 226                         (void) forw_line(pos);
 227                         goto_line(slinenum);
 228                         put_line();
 229                 }
 230         }
 231         hide_hilite = save_hide_hilite;
 232 }
 233
 234 /*
 235  * Clear the attn hilite.
 236  */
 237         public void
 238 clear_attn()
 239 {
 240         int slinenum;
 241         POSITION old_start_attnpos;
 242         POSITION old_end_attnpos;
 243         POSITION pos;
 244         POSITION epos;
 245
 246         if (start_attnpos == NULL_POSITION)
 247                 return;
 248         old_start_attnpos = start_attnpos;
 249         old_end_attnpos = end_attnpos;
 250         start_attnpos = end_attnpos = NULL_POSITION;
 251
 252         if (!can_goto_line)
 253         {
 254                 repaint();
 255                 return;
 256         }
 257         if (squished)
 258                 repaint();
 259
 260         for (slinenum = TOP;  slinenum < TOP + sc_height-1;  slinenum++)
 261         {
 262                 pos = position(slinenum);
 263                 if (pos == NULL_POSITION)
 264                         continue;
 265                 epos = position(slinenum+1);
 266                 if (pos < old_end_attnpos &&
 267                      (epos == NULL_POSITION || epos > old_start_attnpos))
 268                 {
 269                         (void) forw_line(pos);
 270                         goto_line(slinenum);
 271                         put_line();
 272                 }
 273         }
 274 }
 275 #endif
 276
 277 /*
 278  * Hide search string highlighting.
 279  */
 280         public void
 281 undo_search()
 282 {
 283         if (!prev_pattern())
 284         {
 285                 error("No previous regular expression", NULL_PARG);
 286                 return;
 287         }
 288 #if HILITE_SEARCH
 289         hide_hilite = !hide_hilite;
 290         repaint_hilite(1);
 291 #endif
 292 }
 293
 294 /*
 295  * Compile a search pattern, for future use by match_pattern.
 296  */
 297         static int
 298 compile_pattern(pattern, search_type)
 299         char *pattern;
 300         int search_type;
 301 {
 302         if ((search_type & SRCH_NO_REGEX) == 0)
 303         {
 304 #if HAVE_POSIX_REGCOMP
 305                 regex_t *s = (regex_t *) ecalloc(1, sizeof(regex_t));
 306                 if (regcomp(s, pattern, REGCOMP_FLAG))
 307                 {
 308                         free(s);
 309                         error("Invalid pattern", NULL_PARG);
 310                         return (-1);
 311                 }
 312                 if (regpattern != NULL)
 313                         regfree(regpattern);
 314                 regpattern = s;
 315 #endif
 316 #if HAVE_PCRE
 317                 pcre *comp;
 318                 const char *errstring;
 319                 int erroffset;
 320                 PARG parg;
 321                 comp = pcre_compile(pattern, 0,
 322                                 &errstring, &erroffset, NULL);
 323                 if (comp == NULL)
 324                 {
 325                         parg.p_string = (char *) errstring;
 326                         error("%s", &parg);
 327                         return (-1);
 328                 }
 329                 regpattern = comp;
 330 #endif
 331 #if HAVE_RE_COMP
 332                 PARG parg;
 333                 if ((parg.p_string = re_comp(pattern)) != NULL)
 334                 {
 335                         error("%s", &parg);
 336                         return (-1);
 337                 }
 338                 re_pattern = 1;
 339 #endif
 340 #if HAVE_REGCMP
 341                 char *s;
 342                 if ((s = regcmp(pattern, 0)) == NULL)
 343                 {
 344                         error("Invalid pattern", NULL_PARG);
 345                         return (-1);
 346                 }
 347                 if (cpattern != NULL)
 348                         free(cpattern);
 349                 cpattern = s;
 350 #endif
 351 #if HAVE_V8_REGCOMP
 352                 struct regexp *s;
 353                 if ((s = regcomp(pattern)) == NULL)
 354                 {
 355                         /*
 356                          * regcomp has already printed an error message
 357                          * via regerror().
 358                          */
 359                         return (-1);
 360                 }
 361                 if (regpattern != NULL)
 362                         free(regpattern);
 363                 regpattern = s;
 364 #endif
 365         }
 366
 367         if (last_pattern != NULL)
 368                 free(last_pattern);
 369         last_pattern = (char *) calloc(1, strlen(pattern)+1);
 370         if (last_pattern != NULL)
 371                 strcpy(last_pattern, pattern);
 372
 373         last_search_type = search_type;
 374         return (0);
 375 }
 376
 377 /*
 378  * Forget that we have a compiled pattern.
 379  */
 380         static void
 381 uncompile_pattern()
 382 {
 383 #if HAVE_POSIX_REGCOMP
 384         if (regpattern != NULL)
 385                 regfree(regpattern);
 386         regpattern = NULL;
 387 #endif
 388 #if HAVE_PCRE
 389         if (regpattern != NULL)
 390                 pcre_free(regpattern);
 391         regpattern = NULL;
 392 #endif
 393 #if HAVE_RE_COMP
 394         re_pattern = 0;
 395 #endif
 396 #if HAVE_REGCMP
 397         if (cpattern != NULL)
 398                 free(cpattern);
 399         cpattern = NULL;
 400 #endif
 401 #if HAVE_V8_REGCOMP
 402         if (regpattern != NULL)
 403                 free(regpattern);
 404         regpattern = NULL;
 405 #endif
 406         last_pattern = NULL;
 407 }
 408
 409 /*
 410  * Perform a pattern match with the previously compiled pattern.
 411  * Set sp and ep to the start and end of the matched string.
 412  */
 413         static int
 414 match_pattern(line, sp, ep, notbol)
 415         char *line;
 416         char **sp;
 417         char **ep;
 418         int notbol;
 419 {
 420         int matched;
 421
 422         if (last_search_type & SRCH_NO_REGEX)
 423                 return (match(last_pattern, line, sp, ep));
 424
 425 #if HAVE_POSIX_REGCOMP
 426         {
 427                 regmatch_t rm;
 428                 int flags = (notbol) ? REG_NOTBOL : 0;
 429                 matched = !regexec(regpattern, line, 1, &rm, flags);
 430                 if (!matched)
 431                         return (0);
 432 #ifndef __WATCOMC__
 433                 *sp = line + rm.rm_so;
 434                 *ep = line + rm.rm_eo;
 435 #else
 436                 *sp = rm.rm_sp;
 437                 *ep = rm.rm_ep;
 438 #endif
 439         }
 440 #endif
 441 #if HAVE_PCRE
 442         {
 443                 int flags = (notbol) ? PCRE_NOTBOL : 0;
 444                 int ovector[3];
 445                 matched = pcre_exec(regpattern, NULL, line, strlen(line),
 446                         0, flags, ovector, 3) >= 0;
 447                 if (!matched)
 448                         return (0);
 449                 *sp = line + ovector[0];
 450                 *ep = line + ovector[1];
 451         }
 452 #endif
 453 #if HAVE_RE_COMP
 454         matched = (re_exec(line) == 1);
 455         /*
 456          * re_exec doesn't seem to provide a way to get the matched string.
 457          */
 458         *sp = *ep = NULL;
 459 #endif
 460 #if HAVE_REGCMP
 461         *ep = regex(cpattern, line);
 462         matched = (*ep != NULL);
 463         if (!matched)
 464                 return (0);
 465         *sp = __loc1;
 466 #endif
 467 #if HAVE_V8_REGCOMP
 468 #if HAVE_REGEXEC2
 469         matched = regexec2(regpattern, line, notbol);
 470 #else
 471         matched = regexec(regpattern, line);
 472 #endif
 473         if (!matched)
 474                 return (0);
 475         *sp = regpattern->startp[0];
 476         *ep = regpattern->endp[0];
 477 #endif
 478 #if NO_REGEX
 479         matched = match(last_pattern, line, sp, ep);
 480 #endif
 481         return (matched);
 482 }
 483
 484 #if HILITE_SEARCH
 485 /*
 486  * Clear the hilite list.
 487  */
 488         public void
 489 clr_hilite()
 490 {
 491         struct hilite *hl;
 492         struct hilite *nexthl;
 493
 494         for (hl = hilite_anchor.hl_first;  hl != NULL;  hl = nexthl)
 495         {
 496                 nexthl = hl->hl_next;
 497                 free((void*)hl);
 498         }
 499         hilite_anchor.hl_first = NULL;
 500         prep_startpos = prep_endpos = NULL_POSITION;
 501 }
 502
 503 /*
 504  * Should any characters in a specified range be highlighted?
 505  * If nohide is nonzero, don't consider hide_hilite.
 506  */
 507         public int
 508 is_hilited(pos, epos, nohide)
 509         POSITION pos;
 510         POSITION epos;
 511         int nohide;
 512 {
 513         struct hilite *hl;
 514
 515         if (!status_col &&
 516             start_attnpos != NULL_POSITION &&
 517             pos < end_attnpos &&
 518              (epos == NULL_POSITION || epos > start_attnpos))
 519                 /*
 520                  * The attn line overlaps this range.
 521                  */
 522                 return (1);
 523
 524         if (hilite_search == 0)
 525                 /*
 526                  * Not doing highlighting.
 527                  */
 528                 return (0);
 529
 530         if (!nohide && hide_hilite)
 531                 /*
 532                  * Highlighting is hidden.
 533                  */
 534                 return (0);
 535
 536         /*
 537          * Look at each highlight and see if any part of it falls in the range.
 538          */
 539         for (hl = hilite_anchor.hl_first;  hl != NULL;  hl = hl->hl_next)
 540         {
 541                 if (hl->hl_endpos > pos &&
 542                     (epos == NULL_POSITION || epos > hl->hl_startpos))
 543                         return (1);
 544         }
 545         return (0);
 546 }
 547
 548 /*
 549  * Add a new hilite to a hilite list.
 550  */
 551         static void
 552 add_hilite(anchor, hl)
 553         struct hilite *anchor;
 554         struct hilite *hl;
 555 {
 556         struct hilite *ihl;
 557
 558         /*
 559          * Hilites are sorted in the list; find where new one belongs.
 560          * Insert new one after ihl.
 561          */
 562         for (ihl = anchor;  ihl->hl_next != NULL;  ihl = ihl->hl_next)
 563         {
 564                 if (ihl->hl_next->hl_startpos > hl->hl_startpos)
 565                         break;
 566         }
 567
 568         /*
 569          * Truncate hilite so it doesn't overlap any existing ones
 570          * above and below it.
 571          */
 572         if (ihl != anchor)
 573                 hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
 574         if (ihl->hl_next != NULL)
 575                 hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
 576         if (hl->hl_startpos >= hl->hl_endpos)
 577         {
 578                 /*
 579                  * Hilite was truncated out of existence.
 580                  */
 581                 free(hl);
 582                 return;
 583         }
 584         hl->hl_next = ihl->hl_next;
 585         ihl->hl_next = hl;
 586 }
 587
 588 /*
 589  * Adjust hl_startpos & hl_endpos to account for backspace processing.
 590  */
 591         static void
 592 adj_hilite(anchor, linepos)
 593         struct hilite *anchor;
 594         POSITION linepos;
 595 {
 596         char *line;
 597         struct hilite *hl;
 598         int checkstart;
 599         POSITION opos;
 600         POSITION npos;
 601
 602         /*
 603          * The line was already scanned and hilites were added (in hilite_line).
 604          * But it was assumed that each char position in the line
 605          * correponds to one char position in the file.
 606          * This may not be true if there are backspaces in the line.
 607          * Get the raw line again.  Look at each character.
 608          */
 609         (void) forw_raw_line(linepos, &line);
 610         opos = npos = linepos;
 611         hl = anchor->hl_first;
 612         checkstart = TRUE;
 613         while (hl != NULL)
 614         {
 615                 /*
 616                  * See if we need to adjust the current hl_startpos or
 617                  * hl_endpos.  After adjusting startpos[i], move to endpos[i].
 618                  * After adjusting endpos[i], move to startpos[i+1].
 619                  * The hilite list must be sorted thus:
 620                  * startpos[0] < endpos[0] <= startpos[1] < endpos[1] <= etc.
 621                  */
 622                 if (checkstart && hl->hl_startpos == opos)
 623                 {
 624                         hl->hl_startpos = npos;
 625                         checkstart = FALSE;
 626                         continue; /* {{ not really necessary }} */
 627                 } else if (!checkstart && hl->hl_endpos == opos)
 628                 {
 629                         hl->hl_endpos = npos;
 630                         checkstart = TRUE;
 631                         hl = hl->hl_next;
 632                         continue; /* {{ necessary }} */
 633                 }
 634                 if (*line == '\0')
 635                         break;
 636                 opos++;
 637                 npos++;
 638                 line++;
 639                 while (line[0] == '\b' && line[1] != '\0')
 640                 {
 641                         /*
 642                          * Found a backspace.  The file position moves
 643                          * forward by 2 relative to the processed line
 644                          * which was searched in hilite_line.
 645                          */
 646                         npos += 2;
 647                         line += 2;
 648                 }
 649         }
 650 }
 651
 652 /*
 653  * Make a hilite for each string in a physical line which matches
 654  * the current pattern.
 655  * sp,ep delimit the first match already found.
 656  */
 657         static void
 658 hilite_line(linepos, line, sp, ep)
 659         POSITION linepos;
 660         char *line;
 661         char *sp;
 662         char *ep;
 663 {
 664         char *searchp;
 665         struct hilite *hl;
 666         struct hilite hilites;
 667
 668         if (sp == NULL || ep == NULL)
 669                 return;
 670         /*
 671          * sp and ep delimit the first match in the line.
 672          * Mark the corresponding file positions, then
 673          * look for further matches and mark them.
 674          * {{ This technique, of calling match_pattern on subsequent
 675          *    substrings of the line, may mark more than is correct
 676          *    if the pattern starts with "^".  This bug is fixed
 677          *    for those regex functions that accept a notbol parameter
 678          *    (currently POSIX and V8-with-regexec2). }}
 679          */
 680         searchp = line;
 681         /*
 682          * Put the hilites into a temporary list until they're adjusted.
 683          */
 684         hilites.hl_first = NULL;
 685         do {
 686                 if (ep > sp)
 687                 {
 688                         /*
 689                          * Assume that each char position in the "line"
 690                          * buffer corresponds to one char position in the file.
 691                          * This is not quite true; we need to adjust later.
 692                          */
 693                         hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
 694                         hl->hl_startpos = linepos + (sp-line);
 695                         hl->hl_endpos = linepos + (ep-line);
 696                         add_hilite(&hilites, hl);
 697                 }
 698                 /*
 699                  * If we matched more than zero characters,
 700                  * move to the first char after the string we matched.
 701                  * If we matched zero, just move to the next char.
 702                  */
 703                 if (ep > searchp)
 704                         searchp = ep;
 705                 else if (*searchp != '\0')
 706                         searchp++;
 707                 else /* end of line */
 708                         break;
 709         } while (match_pattern(searchp, &sp, &ep, 1));
 710
 711         if (bs_mode == BS_SPECIAL)
 712         {
 713                 /*
 714                  * If there were backspaces in the original line, they
 715                  * were removed, and hl_startpos/hl_endpos are not correct.
 716                  * {{ This is very ugly. }}
 717                  */
 718                 adj_hilite(&hilites, linepos);
 719         }
 720         /*
 721          * Now put the hilites into the real list.
 722          */
 723         while ((hl = hilites.hl_next) != NULL)
 724         {
 725                 hilites.hl_next = hl->hl_next;
 726                 add_hilite(&hilite_anchor, hl);
 727         }
 728 }
 729 #endif
 730
 731 /*
 732  * Change the caseless-ness of searches.
 733  * Updates the internal search state to reflect a change in the -i flag.
 734  */
 735         public void
 736 chg_caseless()
 737 {
 738         if (!is_ucase_pattern)
 739                 /*
 740                  * Pattern did not have uppercase.
 741                  * Just set the search caselessness to the global caselessness.
 742                  */
 743                 is_caseless = caseless;
 744         else
 745                 /*
 746                  * Pattern did have uppercase.
 747                  * Discard the pattern; we can't change search caselessness now.
 748                  */
 749                 uncompile_pattern();
 750 }
 751
 752 #if HILITE_SEARCH
 753 /*
 754  * Find matching text which is currently on screen and highlight it.
 755  */
 756         static void
 757 hilite_screen()
 758 {
 759         struct scrpos scrpos;
 760
 761         get_scrpos(&scrpos);
 762         if (scrpos.pos == NULL_POSITION)
 763                 return;
 764         prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
 765         repaint_hilite(1);
 766 }
 767
 768 /*
 769  * Change highlighting parameters.
 770  */
 771         public void
 772 chg_hilite()
 773 {
 774         /*
 775          * Erase any highlights currently on screen.
 776          */
 777         clr_hilite();
 778         hide_hilite = 0;
 779
 780         if (hilite_search == OPT_ONPLUS)
 781                 /*
 782                  * Display highlights.
 783                  */
 784                 hilite_screen();
 785 }
 786 #endif
 787
 788 /*
 789  * Figure out where to start a search.
 790  */
 791         static POSITION
 792 search_pos(search_type)
 793         int search_type;
 794 {
 795         POSITION pos;
 796         int linenum;
 797
 798         if (empty_screen())
 799         {
 800                 /*
 801                  * Start at the beginning (or end) of the file.
 802                  * The empty_screen() case is mainly for
 803                  * command line initiated searches;
 804                  * for example, "+/xyz" on the command line.
 805                  * Also for multi-file (SRCH_PAST_EOF) searches.
 806                  */
 807                 if (search_type & SRCH_FORW)
 808                 {
 809                         return (ch_zero());
 810                 } else
 811                 {
 812                         pos = ch_length();
 813                         if (pos == NULL_POSITION)
 814                         {
 815                                 (void) ch_end_seek();
 816                                 pos = ch_length();
 817                         }
 818                         return (pos);
 819                 }
 820         }
 821         if (how_search)
 822         {
 823                 /*
 824                  * Search does not include current screen.
 825                  */
 826                 if (search_type & SRCH_FORW)
 827                         linenum = BOTTOM_PLUS_ONE;
 828                 else
 829                         linenum = TOP;
 830                 pos = position(linenum);
 831         } else
 832         {
 833                 /*
 834                  * Search includes current screen.
 835                  * It starts at the jump target (if searching backwards),
 836                  * or at the jump target plus one (if forwards).
 837                  */
 838                 linenum = adjsline(jump_sline);
 839                 pos = position(linenum);
 840                 if (search_type & SRCH_FORW)
 841                 {
 842                         pos = forw_raw_line(pos, (char **)NULL);
 843                         while (pos == NULL_POSITION)
 844                         {
 845                                 if (++linenum >= sc_height)
 846                                         break;
 847                                 pos = position(linenum);
 848                         }
 849                 } else
 850                 {
 851                         while (pos == NULL_POSITION)
 852                         {
 853                                 if (--linenum < 0)
 854                                         break;
 855                                 pos = position(linenum);
 856                         }
 857                 }
 858         }
 859         return (pos);
 860 }
 861
 862 /*
 863  * Search a subset of the file, specified by start/end position.
 864  */
 865         static int
 866 search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
 867         POSITION pos;
 868         POSITION endpos;
 869         int search_type;
 870         int matches;
 871         int maxlines;
 872         POSITION *plinepos;
 873         POSITION *pendpos;
 874 {
 875         char *line;
 876         int linenum;
 877         char *sp, *ep;
 878         int line_match;
 879         POSITION linepos, oldpos;
 880
 881         linenum = find_linenum(pos);
 882         oldpos = pos;
 883         for (;;)
 884         {
 885                 /*
 886                  * Get lines until we find a matching one or until
 887                  * we hit end-of-file (or beginning-of-file if we're
 888                  * going backwards), or until we hit the end position.
 889                  */
 890                 if (ABORT_SIGS())
 891                 {
 892                         /*
 893                          * A signal aborts the search.
 894                          */
 895                         return (-1);
 896                 }
 897
 898                 if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
 899                 {
 900                         /*
 901                          * Reached end position without a match.
 902                          */
 903                         if (pendpos != NULL)
 904                                 *pendpos = pos;
 905                         return (matches);
 906                 }
 907                 if (maxlines > 0)
 908                         maxlines--;
 909
 910                 if (search_type & SRCH_FORW)
 911                 {
 912                         /*
 913                          * Read the next line, and save the
 914                          * starting position of that line in linepos.
 915                          */
 916                         linepos = pos;
 917                         pos = forw_raw_line(pos, &line);
 918                         if (linenum != 0)
 919                                 linenum++;
 920                 } else
 921                 {
 922                         /*
 923                          * Read the previous line and save the
 924                          * starting position of that line in linepos.
 925                          */
 926                         pos = back_raw_line(pos, &line);
 927                         linepos = pos;
 928                         if (linenum != 0)
 929                                 linenum--;
 930                 }
 931
 932                 if (pos == NULL_POSITION)
 933                 {
 934                         /*
 935                          * Reached EOF/BOF without a match.
 936                          */
 937                         if (pendpos != NULL)
 938                                 *pendpos = oldpos;
 939                         return (matches);
 940                 }
 941
 942                 /*
 943                  * If we're using line numbers, we might as well
 944                  * remember the information we have now (the position
 945                  * and line number of the current line).
 946                  * Don't do it for every line because it slows down
 947                  * the search.  Remember the line number only if
 948                  * we're "far" from the last place we remembered it.
 949                  */
 950                 if (linenums && abs((int)(pos - oldpos)) > 1024)
 951                         add_lnum(linenum, pos);
 952                 oldpos = pos;
 953
 954                 /*
 955                  * If it's a caseless search, convert the line to lowercase.
 956                  * If we're doing backspace processing, delete backspaces.
 957                  */
 958                 if (is_caseless || bs_mode == BS_SPECIAL)
 959                 {
 960                         int ops = 0;
 961                         if (is_caseless)
 962                                 ops |= CVT_TO_LC;
 963                         if (bs_mode == BS_SPECIAL)
 964                                 ops |= CVT_BS;
 965                         if (bs_mode != BS_CONTROL)
 966                                 ops |= CVT_CRLF;
 967                         cvt_text(line, line, ops);
 968                 } else if (bs_mode != BS_CONTROL)
 969                 {
 970                         cvt_text(line, line, CVT_CRLF);
 971                 }
 972
 973                 /*
 974                  * Test the next line to see if we have a match.
 975                  * We are successful if we either want a match and got one,
 976                  * or if we want a non-match and got one.
 977                  */
 978                 line_match = match_pattern(line, &sp, &ep, 0);
 979                 line_match = (!(search_type & SRCH_NO_MATCH) && line_match) ||
 980                                 ((search_type & SRCH_NO_MATCH) && !line_match);
 981                 if (!line_match)
 982                         continue;
 983                 /*
 984                  * Got a match.
 985                  */
 986                 if (search_type & SRCH_FIND_ALL)
 987                 {
 988 #if HILITE_SEARCH
 989                         /*
 990                          * We are supposed to find all matches in the range.
 991                          * Just add the matches in this line to the
 992                          * hilite list and keep searching.
 993                          */
 994                         if (line_match)
 995                                 hilite_line(linepos, line, sp, ep);
 996 #endif
 997                 } else if (--matches <= 0)
 998                 {
 999                         /*
1000                          * Found the one match we're looking for.
1001                          * Return it.
1002                          */
1003 #if HILITE_SEARCH
1004                         if (hilite_search == 1)
1005                         {
1006                                 /*
1007                                  * Clear the hilite list and add only
1008                                  * the matches in this one line.
1009                                  */
1010                                 clr_hilite();
1011                                 if (line_match)
1012                                         hilite_line(linepos, line, sp, ep);
1013                         }
1014 #endif
1015                         if (plinepos != NULL)
1016                                 *plinepos = linepos;
1017                         return (0);
1018                 }
1019         }
1020 }
1021
1022 /*
1023  * Search for the n-th occurrence of a specified pattern,
1024  * either forward or backward.
1025  * Return the number of matches not yet found in this file
1026  * (that is, n minus the number of matches found).
1027  * Return -1 if the search should be aborted.
1028  * Caller may continue the search in another file
1029  * if less than n matches are found in this file.
1030  */
1031         public int
1032 search(search_type, pattern, n)
1033         int search_type;
1034         char *pattern;
1035         int n;
1036 {
1037         POSITION pos;
1038         int ucase;
1039
1040         if (pattern == NULL || *pattern == '\0')
1041         {
1042                 /*
1043                  * A null pattern means use the previously compiled pattern.
1044                  */
1045                 if (!prev_pattern())
1046                 {
1047                         error("No previous regular expression", NULL_PARG);
1048                         return (-1);
1049                 }
1050                 if ((search_type & SRCH_NO_REGEX) !=
1051                     (last_search_type & SRCH_NO_REGEX))
1052                 {
1053                         error("Please re-enter search pattern", NULL_PARG);
1054                         return -1;
1055                 }
1056 #if HILITE_SEARCH
1057                 if (hilite_search == OPT_ON)
1058                 {
1059                         /*
1060                          * Erase the highlights currently on screen.
1061                          * If the search fails, we'll redisplay them later.
1062                          */
1063                         repaint_hilite(0);
1064                 }
1065                 if (hilite_search == OPT_ONPLUS && hide_hilite)
1066                 {
1067                         /*
1068                          * Highlight any matches currently on screen,
1069                          * before we actually start the search.
1070                          */
1071                         hide_hilite = 0;
1072                         hilite_screen();
1073                 }
1074                 hide_hilite = 0;
1075 #endif
1076         } else
1077         {
1078                 /*
1079                  * Compile the pattern.
1080                  */
1081                 ucase = is_ucase(pattern);
1082                 if (caseless == OPT_ONPLUS)
1083                         cvt_text(pattern, pattern, CVT_TO_LC);
1084                 if (compile_pattern(pattern, search_type) < 0)
1085                         return (-1);
1086                 /*
1087                  * Ignore case if -I is set OR
1088                  * -i is set AND the pattern is all lowercase.
1089                  */
1090                 is_ucase_pattern = ucase;
1091                 if (is_ucase_pattern && caseless != OPT_ONPLUS)
1092                         is_caseless = 0;
1093                 else
1094                         is_caseless = caseless;
1095 #if HILITE_SEARCH
1096                 if (hilite_search)
1097                 {
1098                         /*
1099                          * Erase the highlights currently on screen.
1100                          * Also permanently delete them from the hilite list.
1101                          */
1102                         repaint_hilite(0);
1103                         hide_hilite = 0;
1104                         clr_hilite();
1105                 }
1106                 if (hilite_search == OPT_ONPLUS)
1107                 {
1108                         /*
1109                          * Highlight any matches currently on screen,
1110                          * before we actually start the search.
1111                          */
1112                         hilite_screen();
1113                 }
1114 #endif
1115         }
1116
1117         /*
1118          * Figure out where to start the search.
1119          */
1120         pos = search_pos(search_type);
1121         if (pos == NULL_POSITION)
1122         {
1123                 /*
1124                  * Can't find anyplace to start searching from.
1125                  */
1126                 if (search_type & SRCH_PAST_EOF)
1127                         return (n);
1128                 /* repaint(); -- why was this here? */
1129                 error("Nothing to search", NULL_PARG);
1130                 return (-1);
1131         }
1132
1133         n = search_range(pos, NULL_POSITION, search_type, n, -1,
1134                         &pos, (POSITION*)NULL);
1135         if (n != 0)
1136         {
1137                 /*
1138                  * Search was unsuccessful.
1139                  */
1140 #if HILITE_SEARCH
1141                 if (hilite_search == OPT_ON && n > 0)
1142                         /*
1143                          * Redisplay old hilites.
1144                          */
1145                         repaint_hilite(1);
1146 #endif
1147                 return (n);
1148         }
1149
1150         if (!(search_type & SRCH_NO_MOVE))
1151         {
1152                 /*
1153                  * Go to the matching line.
1154                  */
1155                 jump_loc(pos, jump_sline);
1156         }
1157
1158 #if HILITE_SEARCH
1159         if (hilite_search == OPT_ON)
1160                 /*
1161                  * Display new hilites in the matching line.
1162                  */
1163                 repaint_hilite(1);
1164 #endif
1165         return (0);
1166 }
1167
1168
1169 #if HILITE_SEARCH
1170 /*
1171  * Prepare hilites in a given range of the file.
1172  *
1173  * The pair (prep_startpos,prep_endpos) delimits a contiguous region
1174  * of the file that has been "prepared"; that is, scanned for matches for
1175  * the current search pattern, and hilites have been created for such matches.
1176  * If prep_startpos == NULL_POSITION, the prep region is empty.
1177  * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
1178  * prep_hilite asks that the range (spos,epos) be covered by the prep region.
1179  */
1180         public void
1181 prep_hilite(spos, epos, maxlines)
1182         POSITION spos;
1183         POSITION epos;
1184         int maxlines;
1185 {
1186         POSITION nprep_startpos = prep_startpos;
1187         POSITION nprep_endpos = prep_endpos;
1188         POSITION new_epos;
1189         POSITION max_epos;
1190         int result;
1191         int i;
1192 /*
1193  * Search beyond where we're asked to search, so the prep region covers
1194  * more than we need.  Do one big search instead of a bunch of small ones.
1195  */
1196 #define SEARCH_MORE (3*size_linebuf)
1197
1198         if (!prev_pattern())
1199                 return;
1200
1201         /*
1202          * If we're limited to a max number of lines, figure out the
1203          * file position we should stop at.
1204          */
1205         if (maxlines < 0)
1206                 max_epos = NULL_POSITION;
1207         else
1208         {
1209                 max_epos = spos;
1210                 for (i = 0;  i < maxlines;  i++)
1211                         max_epos = forw_raw_line(max_epos, (char **)NULL);
1212         }
1213
1214         /*
1215          * Find two ranges:
1216          * The range that we need to search (spos,epos); and the range that
1217          * the "prep" region will then cover (nprep_startpos,nprep_endpos).
1218          */
1219
1220         if (prep_startpos == NULL_POSITION ||
1221             (epos != NULL_POSITION && epos < prep_startpos) ||
1222             spos > prep_endpos)
1223         {
1224                 /*
1225                  * New range is not contiguous with old prep region.
1226                  * Discard the old prep region and start a new one.
1227                  */
1228                 clr_hilite();
1229                 if (epos != NULL_POSITION)
1230                         epos += SEARCH_MORE;
1231                 nprep_startpos = spos;
1232         } else
1233         {
1234                 /*
1235                  * New range partially or completely overlaps old prep region.
1236                  */
1237                 if (epos == NULL_POSITION)
1238                 {
1239                         /*
1240                          * New range goes to end of file.
1241                          */
1242                         ;
1243                 } else if (epos > prep_endpos)
1244                 {
1245                         /*
1246                          * New range ends after old prep region.
1247                          * Extend prep region to end at end of new range.
1248                          */
1249                         epos += SEARCH_MORE;
1250                 } else /* (epos <= prep_endpos) */
1251                 {
1252                         /*
1253                          * New range ends within old prep region.
1254                          * Truncate search to end at start of old prep region.
1255                          */
1256                         epos = prep_startpos;
1257                 }
1258
1259                 if (spos < prep_startpos)
1260                 {
1261                         /*
1262                          * New range starts before old prep region.
1263                          * Extend old prep region backwards to start at
1264                          * start of new range.
1265                          */
1266                         if (spos < SEARCH_MORE)
1267                                 spos = 0;
1268                         else
1269                                 spos -= SEARCH_MORE;
1270                         nprep_startpos = spos;
1271                 } else /* (spos >= prep_startpos) */
1272                 {
1273                         /*
1274                          * New range starts within or after old prep region.
1275                          * Trim search to start at end of old prep region.
1276                          */
1277                         spos = prep_endpos;
1278                 }
1279         }
1280
1281         if (epos != NULL_POSITION && max_epos != NULL_POSITION &&
1282             epos > max_epos)
1283                 /*
1284                  * Don't go past the max position we're allowed.
1285                  */
1286                 epos = max_epos;
1287
1288         if (epos == NULL_POSITION || epos > spos)
1289         {
1290                 result = search_range(spos, epos, SRCH_FORW|SRCH_FIND_ALL, 0,
1291                                 maxlines, (POSITION*)NULL, &new_epos);
1292                 if (result < 0)
1293                         return;
1294                 if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
1295                         nprep_endpos = new_epos;
1296         }
1297         prep_startpos = nprep_startpos;
1298         prep_endpos = nprep_endpos;
1299 }
1300 #endif
1301
1302 /*
1303  * Simple pattern matching function.
1304  * It supports no metacharacters like *, etc.
1305  */
1306         static int
1307 match(pattern, buf, pfound, pend)
1308         char *pattern, *buf;
1309         char **pfound, **pend;
1310 {
1311         register char *pp, *lp;
1312
1313         for ( ;  *buf != '\0';  buf++)
1314         {
1315                 for (pp = pattern, lp = buf;  *pp == *lp;  pp++, lp++)
1316                         if (*pp == '\0' || *lp == '\0')
1317                                 break;
1318                 if (*pp == '\0')
1319                 {
1320                         if (pfound != NULL)
1321                                 *pfound = buf;
1322                         if (pend != NULL)
1323                                 *pend = lp;
1324                         return (1);
1325                 }
1326         }
1327         return (0);
1328 }
1329
1330 #if HAVE_V8_REGCOMP
1331 /*
1332  * This function is called by the V8 regcomp to report
1333  * errors in regular expressions.
1334  */
1335         void
1336 regerror(s)
1337         char *s;
1338 {
1339         PARG parg;
1340
1341         parg.p_string = s;
1342         error("%s", &parg);
1343 }
1344 #endif
1345