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