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