contrib/less/search.c

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