external/bsd/nvi/dist/common/search.c

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