contrib/less/search.c

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