dist/nvi/common/search.c

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