common/search.c

   1 /*-
   2  * Copyright (c) 1992, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  * Copyright (c) 1992, 1993, 1994, 1995, 1996
   5  *      Keith Bostic.  All rights reserved.
   6  *
   7  * See the LICENSE file for redistribution information.
   8  */
   9
  10 #include "config.h"
  11
  12 #ifndef lint
  13 static const char sccsid[] = "$Id: search.c,v 10.31 2001/06/25 15:19:12 skimo Exp $ (Berkeley) $Date: 2001/06/25 15:19:12 $";
  14 #endif /* not lint */
  15
  16 #include <sys/types.h>
  17 #include <sys/queue.h>
  18
  19 #include <bitstring.h>
  20 #include <ctype.h>
  21 #include <errno.h>
  22 #include <limits.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <unistd.h>
  27
  28 #include "common.h"
  29
  30 typedef enum { S_EMPTY, S_EOF, S_NOPREV, S_NOTFOUND, S_SOF, S_WRAP } smsg_t;
  31
  32 static void     search_msg __P((SCR *, smsg_t));
  33 static int      search_init __P((SCR *, dir_t, CHAR_T *, size_t, CHAR_T **, u_int));
  34
  35 /*
  36  * search_init --
  37  *      Set up a search.
  38  */
  39 static int
  40 search_init(SCR *sp, dir_t dir, CHAR_T *ptrn, size_t plen, CHAR_T **epp, u_int flags)
  41 {
  42         db_recno_t lno;
  43         int delim;
  44         CHAR_T *p, *t;
  45
  46         /* If the file is empty, it's a fast search. */
  47         if (sp->lno <= 1) {
  48                 if (db_last(sp, &lno))
  49                         return (1);
  50                 if (lno == 0) {
  51                         if (LF_ISSET(SEARCH_MSG))
  52                                 search_msg(sp, S_EMPTY);
  53                         return (1);
  54                 }
  55         }
  56
  57         if (LF_ISSET(SEARCH_PARSE)) {           /* Parse the string. */
  58                 /*
  59                  * Use the saved pattern if no pattern specified, or if only
  60                  * one or two delimiter characters specified.
  61                  *
  62                  * !!!
  63                  * Historically, only the pattern itself was saved, vi didn't
  64                  * preserve addressing or delta information.
  65                  */
  66                 if (ptrn == NULL)
  67                         goto prev;
  68                 if (plen == 1) {
  69                         if (epp != NULL)
  70                                 *epp = ptrn + 1;
  71                         goto prev;
  72                 }
  73                 if (ptrn[0] == ptrn[1]) {
  74                         if (epp != NULL)
  75                                 *epp = ptrn + 2;
  76
  77                         /* Complain if we don't have a previous pattern. */
  78 prev:                   if (sp->re == NULL) {
  79                                 search_msg(sp, S_NOPREV);
  80                                 return (1);
  81                         }
  82                         /* Re-compile the search pattern if necessary. */
  83                         if (!F_ISSET(sp, SC_RE_SEARCH) && re_compile(sp,
  84                             sp->re, sp->re_len, NULL, NULL, &sp->re_c,
  85                             SEARCH_CSEARCH | SEARCH_MSG))
  86                                 return (1);
  87
  88                         /* Set the search direction. */
  89                         if (LF_ISSET(SEARCH_SET))
  90                                 sp->searchdir = dir;
  91                         return (0);
  92                 }
  93
  94                 /*
  95                  * Set the delimiter, and move forward to the terminating
  96                  * delimiter, handling escaped delimiters.
  97                  *
  98                  * QUOTING NOTE:
  99                  * Only discard an escape character if it escapes a delimiter.
 100                  */
 101                 for (delim = *ptrn, p = t = ++ptrn;; *t++ = *p++) {
 102                         if (--plen == 0 || p[0] == delim) {
 103                                 if (plen != 0)
 104                                         ++p;
 105                                 break;
 106                         }
 107                         if (plen > 1 && p[0] == '\\' && p[1] == delim) {
 108                                 ++p;
 109                                 --plen;
 110                         }
 111                 }
 112                 if (epp != NULL)
 113                         *epp = p;
 114
 115                 plen = t - ptrn;
 116         }
 117
 118         /* Compile the RE. */
 119         if (re_compile(sp, ptrn, plen, &sp->re, &sp->re_len, &sp->re_c,
 120             SEARCH_CSEARCH | LF_ISSET(SEARCH_CSCOPE | SEARCH_EXTEND |
 121             SEARCH_IC | SEARCH_LITERAL | SEARCH_MSG | SEARCH_TAG)))
 122                 return (1);
 123
 124         /* Set the search direction. */
 125         if (LF_ISSET(SEARCH_SET))
 126                 sp->searchdir = dir;
 127
 128         return (0);
 129 }
 130
 131 /*
 132  * f_search --
 133  *      Do a forward search.
 134  *
 135  * PUBLIC: int f_search __P((SCR *,
 136  * PUBLIC:    MARK *, MARK *, CHAR_T *, size_t, CHAR_T **, u_int));
 137  */
 138 int
 139 f_search(SCR *sp, MARK *fm, MARK *rm, CHAR_T *ptrn, size_t plen, CHAR_T **eptrn, u_int flags)
 140 {
 141         busy_t btype;
 142         db_recno_t lno;
 143         regmatch_t match[1];
 144         size_t coff, len;
 145         int cnt, eval, rval, wrapped;
 146         CHAR_T *l;
 147
 148         if (search_init(sp, FORWARD, ptrn, plen, eptrn, flags))
 149                 return (1);
 150
 151         /* Figure out if we're going to wrap. */
 152         if (!LF_ISSET(SEARCH_NOOPT) && O_ISSET(sp, O_WRAPSCAN))
 153                 LF_SET(SEARCH_WRAP);
 154
 155         if (LF_ISSET(SEARCH_FIRST)) {
 156                 lno = 1;
 157                 coff = 0;
 158         } else {
 159                 if (db_get(sp, fm->lno, DBG_FATAL, &l, &len))
 160                         return (1);
 161                 lno = fm->lno;
 162
 163                 /*
 164                  * If doing incremental search, start searching at the previous
 165                  * column, so that we search a minimal distance and still match
 166                  * special patterns, e.g., \< for beginning of a word.
 167                  *
 168                  * Otherwise, start searching immediately after the cursor.  If
 169                  * at the end of the line, start searching on the next line.
 170                  * This is incompatible (read bug fix) with the historic vi --
 171                  * searches for the '$' pattern never moved forward, and the
 172                  * "-t foo" didn't work if the 'f' was the first character in
 173                  * the file.
 174                  */
 175                 if (LF_ISSET(SEARCH_INCR)) {
 176                         if ((coff = fm->cno) != 0)
 177                                 --coff;
 178                 } else if (fm->cno + 1 >= len) {
 179                         coff = 0;
 180                         lno = fm->lno + 1;
 181                         if (db_get(sp, lno, 0, &l, &len)) {
 182                                 if (!LF_ISSET(SEARCH_WRAP)) {
 183                                         if (LF_ISSET(SEARCH_MSG))
 184                                                 search_msg(sp, S_EOF);
 185                                         return (1);
 186                                 }
 187                                 lno = 1;
 188                         }
 189                 } else
 190                         coff = fm->cno + 1;
 191         }
 192
 193         btype = BUSY_ON;
 194         for (cnt = INTERRUPT_CHECK, rval = 1, wrapped = 0;; ++lno, coff = 0) {
 195                 if (cnt-- == 0) {
 196                         if (INTERRUPTED(sp))
 197                                 break;
 198                         if (LF_ISSET(SEARCH_MSG)) {
 199                                 search_busy(sp, btype);
 200                                 btype = BUSY_UPDATE;
 201                         }
 202                         cnt = INTERRUPT_CHECK;
 203                 }
 204                 if (wrapped && lno > fm->lno || db_get(sp, lno, 0, &l, &len)) {
 205                         if (wrapped) {
 206                                 if (LF_ISSET(SEARCH_MSG))
 207                                         search_msg(sp, S_NOTFOUND);
 208                                 break;
 209                         }
 210                         if (!LF_ISSET(SEARCH_WRAP)) {
 211                                 if (LF_ISSET(SEARCH_MSG))
 212                                         search_msg(sp, S_EOF);
 213                                 break;
 214                         }
 215                         lno = 0;
 216                         wrapped = 1;
 217                         continue;
 218                 }
 219
 220                 /* If already at EOL, just keep going. */
 221                 if (len != 0 && coff == len)
 222                         continue;
 223
 224                 /* Set the termination. */
 225                 match[0].rm_so = coff;
 226                 match[0].rm_eo = len;
 227
 228 #if defined(DEBUG) && 0
 229                 vtrace(sp, "F search: %lu from %u to %u\n",
 230                     lno, coff, len != 0 ? len - 1 : len);
 231 #endif
 232                 /* Search the line. */
 233                 eval = regexec(&sp->re_c, l, 1, match,
 234                     (match[0].rm_so == 0 ? 0 : REG_NOTBOL) | REG_STARTEND);
 235                 if (eval == REG_NOMATCH)
 236                         continue;
 237                 if (eval != 0) {
 238                         if (LF_ISSET(SEARCH_MSG))
 239                                 re_error(sp, eval, &sp->re_c);
 240                         else
 241                                 (void)sp->gp->scr_bell(sp);
 242                         break;
 243                 }
 244
 245                 /* Warn if the search wrapped. */
 246                 if (wrapped && LF_ISSET(SEARCH_WMSG))
 247                         search_msg(sp, S_WRAP);
 248
 249 #if defined(DEBUG) && 0
 250                 vtrace(sp, "F search: %qu to %qu\n",
 251                     match[0].rm_so, match[0].rm_eo);
 252 #endif
 253                 rm->lno = lno;
 254                 rm->cno = match[0].rm_so;
 255
 256                 /*
 257                  * If a change command, it's possible to move beyond the end
 258                  * of a line.  Historic vi generally got this wrong (e.g. try
 259                  * "c?$<cr>").  Not all that sure this gets it right, there
 260                  * are lots of strange cases.
 261                  */
 262                 if (!LF_ISSET(SEARCH_EOL) && rm->cno >= len)
 263                         rm->cno = len != 0 ? len - 1 : 0;
 264
 265                 rval = 0;
 266                 break;
 267         }
 268
 269         if (LF_ISSET(SEARCH_MSG))
 270                 search_busy(sp, BUSY_OFF);
 271         return (rval);
 272 }
 273
 274 /*
 275  * b_search --
 276  *      Do a backward search.
 277  *
 278  * PUBLIC: int b_search __P((SCR *,
 279  * PUBLIC:    MARK *, MARK *, CHAR_T *, size_t, CHAR_T **, u_int));
 280  */
 281 int
 282 b_search(SCR *sp, MARK *fm, MARK *rm, CHAR_T *ptrn, size_t plen, CHAR_T **eptrn, u_int flags)
 283 {
 284         busy_t btype;
 285         db_recno_t lno;
 286         regmatch_t match[1];
 287         size_t coff, last, len;
 288         int cnt, eval, rval, wrapped;
 289         CHAR_T *l;
 290
 291         if (search_init(sp, BACKWARD, ptrn, plen, eptrn, flags))
 292                 return (1);
 293
 294         /* Figure out if we're going to wrap. */
 295         if (!LF_ISSET(SEARCH_NOOPT) && O_ISSET(sp, O_WRAPSCAN))
 296                 LF_SET(SEARCH_WRAP);
 297
 298         /*
 299          * If doing incremental search, set the "starting" position past the
 300          * current column, so that we search a minimal distance and still
 301          * match special patterns, e.g., \> for the end of a word.  This is
 302          * safe when the cursor is at the end of a line because we only use
 303          * it for comparison with the location of the match.
 304          *
 305          * Otherwise, start searching immediately before the cursor.  If in
 306          * the first column, start search on the previous line.
 307          */
 308         if (LF_ISSET(SEARCH_INCR)) {
 309                 lno = fm->lno;
 310                 coff = fm->cno + 1;
 311         } else {
 312                 if (fm->cno == 0) {
 313                         if (fm->lno == 1 && !LF_ISSET(SEARCH_WRAP)) {
 314                                 if (LF_ISSET(SEARCH_MSG))
 315                                         search_msg(sp, S_SOF);
 316                                 return (1);
 317                         }
 318                         lno = fm->lno - 1;
 319                 } else
 320                         lno = fm->lno;
 321                 coff = fm->cno;
 322         }
 323
 324         btype = BUSY_ON;
 325         for (cnt = INTERRUPT_CHECK, rval = 1, wrapped = 0;; --lno, coff = 0) {
 326                 if (cnt-- == 0) {
 327                         if (INTERRUPTED(sp))
 328                                 break;
 329                         if (LF_ISSET(SEARCH_MSG)) {
 330                                 search_busy(sp, btype);
 331                                 btype = BUSY_UPDATE;
 332                         }
 333                         cnt = INTERRUPT_CHECK;
 334                 }
 335                 if (wrapped && lno < fm->lno || lno == 0) {
 336                         if (wrapped) {
 337                                 if (LF_ISSET(SEARCH_MSG))
 338                                         search_msg(sp, S_NOTFOUND);
 339                                 break;
 340                         }
 341                         if (!LF_ISSET(SEARCH_WRAP)) {
 342                                 if (LF_ISSET(SEARCH_MSG))
 343                                         search_msg(sp, S_SOF);
 344                                 break;
 345                         }
 346                         if (db_last(sp, &lno))
 347                                 break;
 348                         if (lno == 0) {
 349                                 if (LF_ISSET(SEARCH_MSG))
 350                                         search_msg(sp, S_EMPTY);
 351                                 break;
 352                         }
 353                         ++lno;
 354                         wrapped = 1;
 355                         continue;
 356                 }
 357
 358                 if (db_get(sp, lno, 0, &l, &len))
 359                         break;
 360
 361                 /* Set the termination. */
 362                 match[0].rm_so = 0;
 363                 match[0].rm_eo = len;
 364
 365 #if defined(DEBUG) && 0
 366                 vtrace(sp,
 367                     "B search: %lu from 0 to %qu\n", lno, match[0].rm_eo);
 368 #endif
 369                 /* Search the line. */
 370                 eval = regexec(&sp->re_c, l, 1, match,
 371                     (match[0].rm_eo == len ? 0 : REG_NOTEOL) | REG_STARTEND);
 372                 if (eval == REG_NOMATCH)
 373                         continue;
 374                 if (eval != 0) {
 375                         if (LF_ISSET(SEARCH_MSG))
 376                                 re_error(sp, eval, &sp->re_c);
 377                         else
 378                                 (void)sp->gp->scr_bell(sp);
 379                         break;
 380                 }
 381
 382                 /* Check for a match starting past the cursor. */
 383                 if (coff != 0 && match[0].rm_so >= coff)
 384                         continue;
 385
 386                 /* Warn if the search wrapped. */
 387                 if (wrapped && LF_ISSET(SEARCH_WMSG))
 388                         search_msg(sp, S_WRAP);
 389
 390 #if defined(DEBUG) && 0
 391                 vtrace(sp, "B found: %qu to %qu\n",
 392                     match[0].rm_so, match[0].rm_eo);
 393 #endif
 394                 /*
 395                  * We now have the first match on the line.  Step through the
 396                  * line character by character until find the last acceptable
 397                  * match.  This is painful, we need a better interface to regex
 398                  * to make this work.
 399                  */
 400                 for (;;) {
 401                         last = match[0].rm_so++;
 402                         if (match[0].rm_so >= len)
 403                                 break;
 404                         match[0].rm_eo = len;
 405                         eval = regexec(&sp->re_c, l, 1, match,
 406                             (match[0].rm_so == 0 ? 0 : REG_NOTBOL) |
 407                             REG_STARTEND);
 408                         if (eval == REG_NOMATCH)
 409                                 break;
 410                         if (eval != 0) {
 411                                 if (LF_ISSET(SEARCH_MSG))
 412                                         re_error(sp, eval, &sp->re_c);
 413                                 else
 414                                         (void)sp->gp->scr_bell(sp);
 415                                 goto err;
 416                         }
 417                         if (coff && match[0].rm_so >= coff)
 418                                 break;
 419                 }
 420                 rm->lno = lno;
 421
 422                 /* See comment in f_search(). */
 423                 if (!LF_ISSET(SEARCH_EOL) && last >= len)
 424                         rm->cno = len != 0 ? len - 1 : 0;
 425                 else
 426                         rm->cno = last;
 427                 rval = 0;
 428                 break;
 429         }
 430
 431 err:    if (LF_ISSET(SEARCH_MSG))
 432                 search_busy(sp, BUSY_OFF);
 433         return (rval);
 434 }
 435
 436 /*
 437  * search_msg --
 438  *      Display one of the search messages.
 439  */
 440 static void
 441 search_msg(SCR *sp, smsg_t msg)
 442 {
 443         switch (msg) {
 444         case S_EMPTY:
 445                 msgq(sp, M_ERR, "072|File empty; nothing to search");
 446                 break;
 447         case S_EOF:
 448                 msgq(sp, M_ERR,
 449                     "073|Reached end-of-file without finding the pattern");
 450                 break;
 451         case S_NOPREV:
 452                 msgq(sp, M_ERR, "074|No previous search pattern");
 453                 break;
 454         case S_NOTFOUND:
 455                 msgq(sp, M_ERR, "075|Pattern not found");
 456                 break;
 457         case S_SOF:
 458                 msgq(sp, M_ERR,
 459                     "076|Reached top-of-file without finding the pattern");
 460                 break;
 461         case S_WRAP:
 462                 msgq(sp, M_ERR, "077|Search wrapped");
 463                 break;
 464         default:
 465                 abort();
 466         }
 467 }
 468
 469 /*
 470  * search_busy --
 471  *      Put up the busy searching message.
 472  *
 473  * PUBLIC: void search_busy __P((SCR *, busy_t));
 474  */
 475 void
 476 search_busy(SCR *sp, busy_t btype)
 477 {
 478         sp->gp->scr_busy(sp, "078|Searching...", btype);
 479 }