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