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