1 /* $NetBSD: search.c,v 1.4 2017/11/22 16:17:30 rin 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.4 2017/11/22 16:17:30 rin 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 = 0; 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 wrapped = 1; 195 } 196 } else 197 coff = fm->cno + 1; 198 } 199 200 btype = BUSY_ON; 201 for (cnt = INTERRUPT_CHECK, rval = 1;; ++lno, coff = 0) { 202 if (cnt-- == 0) { 203 if (INTERRUPTED(sp)) 204 break; 205 if (LF_ISSET(SEARCH_MSG)) { 206 search_busy(sp, btype); 207 btype = BUSY_UPDATE; 208 } 209 cnt = INTERRUPT_CHECK; 210 } 211 if ((wrapped && lno > fm->lno) || 212 db_get(sp, lno, 0, &l, &len)) { 213 if (wrapped) { 214 if (LF_ISSET(SEARCH_MSG)) 215 search_msg(sp, S_NOTFOUND); 216 break; 217 } 218 if (!LF_ISSET(SEARCH_WRAP)) { 219 if (LF_ISSET(SEARCH_MSG)) 220 search_msg(sp, S_EOF); 221 break; 222 } 223 lno = 0; 224 wrapped = 1; 225 continue; 226 } 227 228 /* If already at EOL, just keep going. */ 229 if (len != 0 && coff == len) 230 continue; 231 232 /* Set the termination. */ 233 match[0].rm_so = coff; 234 match[0].rm_eo = len; 235 236 #if defined(DEBUG) && 0 237 vtrace(sp, "F search: %lu from %u to %u\n", 238 lno, coff, len != 0 ? len - 1 : len); 239 #endif 240 /* Search the line. */ 241 eval = regexec(&sp->re_c, l, 1, match, 242 (match[0].rm_so == 0 ? 0 : REG_NOTBOL) | REG_STARTEND); 243 if (eval == REG_NOMATCH) 244 continue; 245 if (eval != 0) { 246 if (LF_ISSET(SEARCH_MSG)) 247 re_error(sp, eval, &sp->re_c); 248 else 249 (void)sp->gp->scr_bell(sp); 250 break; 251 } 252 253 /* Warn if the search wrapped. */ 254 if (wrapped && LF_ISSET(SEARCH_WMSG)) 255 search_msg(sp, S_WRAP); 256 257 #if defined(DEBUG) && 0 258 vtrace(sp, "F search: %qu to %qu\n", 259 match[0].rm_so, match[0].rm_eo); 260 #endif 261 rm->lno = lno; 262 rm->cno = match[0].rm_so; 263 264 /* 265 * If a change command, it's possible to move beyond the end 266 * of a line. Historic vi generally got this wrong (e.g. try 267 * "c?$<cr>"). Not all that sure this gets it right, there 268 * are lots of strange cases. 269 */ 270 if (!LF_ISSET(SEARCH_EOL) && rm->cno >= len) 271 rm->cno = len != 0 ? len - 1 : 0; 272 273 rval = 0; 274 break; 275 } 276 277 if (LF_ISSET(SEARCH_MSG)) 278 search_busy(sp, BUSY_OFF); 279 return (rval); 280 } 281 282 /* 283 * b_search -- 284 * Do a backward search. 285 * 286 * PUBLIC: int b_search __P((SCR *, 287 * PUBLIC: MARK *, MARK *, CHAR_T *, size_t, CHAR_T **, u_int)); 288 */ 289 int 290 b_search(SCR *sp, MARK *fm, MARK *rm, CHAR_T *ptrn, size_t plen, CHAR_T **eptrn, u_int flags) 291 { 292 busy_t btype; 293 db_recno_t lno; 294 regmatch_t match[1]; 295 size_t coff, last, len; 296 int cnt, eval, rval, wrapped; 297 CHAR_T *l; 298 299 if (search_init(sp, BACKWARD, ptrn, plen, eptrn, flags)) 300 return (1); 301 302 /* Figure out if we're going to wrap. */ 303 if (!LF_ISSET(SEARCH_NOOPT) && O_ISSET(sp, O_WRAPSCAN)) 304 LF_SET(SEARCH_WRAP); 305 306 /* 307 * If doing incremental search, set the "starting" position past the 308 * current column, so that we search a minimal distance and still 309 * match special patterns, e.g., \> for the end of a word. This is 310 * safe when the cursor is at the end of a line because we only use 311 * it for comparison with the location of the match. 312 * 313 * Otherwise, start searching immediately before the cursor. If in 314 * the first column, start search on the previous line. 315 */ 316 if (LF_ISSET(SEARCH_INCR)) { 317 lno = fm->lno; 318 coff = fm->cno + 1; 319 } else { 320 if (fm->cno == 0) { 321 if (fm->lno == 1 && !LF_ISSET(SEARCH_WRAP)) { 322 if (LF_ISSET(SEARCH_MSG)) 323 search_msg(sp, S_SOF); 324 return (1); 325 } 326 lno = fm->lno - 1; 327 } else 328 lno = fm->lno; 329 coff = fm->cno; 330 } 331 332 btype = BUSY_ON; 333 for (cnt = INTERRUPT_CHECK, rval = 1, wrapped = 0;; --lno, coff = 0) { 334 if (cnt-- == 0) { 335 if (INTERRUPTED(sp)) 336 break; 337 if (LF_ISSET(SEARCH_MSG)) { 338 search_busy(sp, btype); 339 btype = BUSY_UPDATE; 340 } 341 cnt = INTERRUPT_CHECK; 342 } 343 if ((wrapped && lno < fm->lno) || lno == 0) { 344 if (wrapped) { 345 if (LF_ISSET(SEARCH_MSG)) 346 search_msg(sp, S_NOTFOUND); 347 break; 348 } 349 if (!LF_ISSET(SEARCH_WRAP)) { 350 if (LF_ISSET(SEARCH_MSG)) 351 search_msg(sp, S_SOF); 352 break; 353 } 354 if (db_last(sp, &lno)) 355 break; 356 if (lno == 0) { 357 if (LF_ISSET(SEARCH_MSG)) 358 search_msg(sp, S_EMPTY); 359 break; 360 } 361 ++lno; 362 wrapped = 1; 363 continue; 364 } 365 366 if (db_get(sp, lno, 0, &l, &len)) 367 break; 368 369 /* Set the termination. */ 370 match[0].rm_so = 0; 371 match[0].rm_eo = len; 372 373 #if defined(DEBUG) && 0 374 vtrace(sp, 375 "B search: %lu from 0 to %qu\n", lno, match[0].rm_eo); 376 #endif 377 /* Search the line. */ 378 eval = regexec(&sp->re_c, l, 1, match, 379 ((size_t)match[0].rm_eo == len ? 0 : REG_NOTEOL) | REG_STARTEND); 380 if (eval == REG_NOMATCH) 381 continue; 382 if (eval != 0) { 383 if (LF_ISSET(SEARCH_MSG)) 384 re_error(sp, eval, &sp->re_c); 385 else 386 (void)sp->gp->scr_bell(sp); 387 break; 388 } 389 390 /* Check for a match starting past the cursor. */ 391 if (coff != 0 && (size_t)match[0].rm_so >= coff) 392 continue; 393 394 /* Warn if the search wrapped. */ 395 if (wrapped && LF_ISSET(SEARCH_WMSG)) 396 search_msg(sp, S_WRAP); 397 398 #if defined(DEBUG) && 0 399 vtrace(sp, "B found: %qu to %qu\n", 400 match[0].rm_so, match[0].rm_eo); 401 #endif 402 /* 403 * We now have the first match on the line. Step through the 404 * line character by character until find the last acceptable 405 * match. This is painful, we need a better interface to regex 406 * to make this work. 407 */ 408 for (;;) { 409 last = match[0].rm_so++; 410 if ((size_t)match[0].rm_so >= len) 411 break; 412 match[0].rm_eo = len; 413 eval = regexec(&sp->re_c, l, 1, match, 414 (match[0].rm_so == 0 ? 0 : REG_NOTBOL) | 415 REG_STARTEND); 416 if (eval == REG_NOMATCH) 417 break; 418 if (eval != 0) { 419 if (LF_ISSET(SEARCH_MSG)) 420 re_error(sp, eval, &sp->re_c); 421 else 422 (void)sp->gp->scr_bell(sp); 423 goto err; 424 } 425 if (coff && (size_t)match[0].rm_so >= coff) 426 break; 427 } 428 rm->lno = lno; 429 430 /* See comment in f_search(). */ 431 if (!LF_ISSET(SEARCH_EOL) && last >= len) 432 rm->cno = len != 0 ? len - 1 : 0; 433 else 434 rm->cno = last; 435 rval = 0; 436 break; 437 } 438 439 err: if (LF_ISSET(SEARCH_MSG)) 440 search_busy(sp, BUSY_OFF); 441 return (rval); 442 } 443 444 /* 445 * search_msg -- 446 * Display one of the search messages. 447 */ 448 static void 449 search_msg(SCR *sp, smsg_t msg) 450 { 451 switch (msg) { 452 case S_EMPTY: 453 msgq(sp, M_ERR, "072|File empty; nothing to search"); 454 break; 455 case S_EOF: 456 msgq(sp, M_ERR, 457 "073|Reached end-of-file without finding the pattern"); 458 break; 459 case S_NOPREV: 460 msgq(sp, M_ERR, "074|No previous search pattern"); 461 break; 462 case S_NOTFOUND: 463 msgq(sp, M_ERR, "075|Pattern not found"); 464 break; 465 case S_SOF: 466 msgq(sp, M_ERR, 467 "076|Reached top-of-file without finding the pattern"); 468 break; 469 case S_WRAP: 470 msgq(sp, M_ERR, "077|Search wrapped"); 471 break; 472 default: 473 abort(); 474 } 475 } 476 477 /* 478 * search_busy -- 479 * Put up the busy searching message. 480 * 481 * PUBLIC: void search_busy __P((SCR *, busy_t)); 482 */ 483 void 484 search_busy(SCR *sp, busy_t btype) 485 { 486 sp->gp->scr_busy(sp, "078|Searching...", btype); 487 } 488