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 } 487