contrib/less/search.c

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