contrib/less-394/search.c

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