contrib/less-4/search.c

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