contrib/less-4/search.c

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