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