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