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