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