1 /* $OpenBSD: search.c,v 1.8 2006/01/08 21:05:39 miod Exp $ */ 2 3 /*- 4 * Copyright (c) 1992, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * Copyright (c) 1992, 1993, 1994, 1995, 1996 7 * Keith Bostic. All rights reserved. 8 * 9 * See the LICENSE file for redistribution information. 10 */ 11 12 #include "config.h" 13 14 #ifndef lint 15 static const char sccsid[] = "@(#)search.c 10.25 (Berkeley) 6/30/96"; 16 #endif /* not lint */ 17 18 #include <sys/types.h> 19 #include <sys/queue.h> 20 21 #include <bitstring.h> 22 #include <ctype.h> 23 #include <errno.h> 24 #include <limits.h> 25 #include <stdio.h> 26 #include <stdlib.h> 27 #include <string.h> 28 #include <unistd.h> 29 30 #include "common.h" 31 32 typedef enum { S_EMPTY, S_EOF, S_NOPREV, S_NOTFOUND, S_SOF, S_WRAP } smsg_t; 33 34 static void search_msg(SCR *, smsg_t); 35 static int search_init(SCR *, dir_t, char *, size_t, char **, u_int); 36 37 /* 38 * search_init -- 39 * Set up a search. 40 */ 41 static int 42 search_init(sp, dir, ptrn, plen, epp, flags) 43 SCR *sp; 44 dir_t dir; 45 char *ptrn, **epp; 46 size_t plen; 47 u_int flags; 48 { 49 recno_t lno; 50 int delim; 51 char *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(SCR *, MARK *, MARK *, char *, size_t, char **, u_int); 146 */ 147 int 148 f_search(sp, fm, rm, ptrn, plen, eptrn, flags) 149 SCR *sp; 150 MARK *fm, *rm; 151 char *ptrn, **eptrn; 152 size_t plen; 153 u_int flags; 154 { 155 busy_t btype; 156 recno_t lno; 157 regmatch_t match[1]; 158 size_t coff, len; 159 int cnt, eval, rval, wrapped; 160 char *l; 161 162 if (search_init(sp, FORWARD, ptrn, plen, eptrn, flags)) 163 return (1); 164 165 if (LF_ISSET(SEARCH_FILE)) { 166 lno = 1; 167 coff = 0; 168 } else { 169 if (db_get(sp, fm->lno, DBG_FATAL, &l, &len)) 170 return (1); 171 lno = fm->lno; 172 173 /* 174 * If doing incremental search, start searching at the previous 175 * column, so that we search a minimal distance and still match 176 * special patterns, e.g., \< for beginning of a word. 177 * 178 * Otherwise, start searching immediately after the cursor. If 179 * at the end of the line, start searching on the next line. 180 * This is incompatible (read bug fix) with the historic vi -- 181 * searches for the '$' pattern never moved forward, and the 182 * "-t foo" didn't work if the 'f' was the first character in 183 * the file. 184 */ 185 if (LF_ISSET(SEARCH_INCR)) { 186 if ((coff = fm->cno) != 0) 187 --coff; 188 } else if (fm->cno + 1 >= len) { 189 coff = 0; 190 lno = fm->lno + 1; 191 if (db_get(sp, lno, 0, &l, &len)) { 192 if (!O_ISSET(sp, O_WRAPSCAN)) { 193 if (LF_ISSET(SEARCH_MSG)) 194 search_msg(sp, S_EOF); 195 return (1); 196 } 197 lno = 1; 198 } 199 } else 200 coff = fm->cno + 1; 201 } 202 203 btype = BUSY_ON; 204 for (cnt = INTERRUPT_CHECK, rval = 1, wrapped = 0;; ++lno, coff = 0) { 205 if (cnt-- == 0) { 206 if (INTERRUPTED(sp)) 207 break; 208 if (LF_ISSET(SEARCH_MSG)) { 209 search_busy(sp, btype); 210 btype = BUSY_UPDATE; 211 } 212 cnt = INTERRUPT_CHECK; 213 } 214 if ((wrapped && lno > fm->lno) || db_get(sp, lno, 0, &l, &len)) { 215 if (wrapped) { 216 if (LF_ISSET(SEARCH_MSG)) 217 search_msg(sp, S_NOTFOUND); 218 break; 219 } 220 if (!O_ISSET(sp, O_WRAPSCAN)) { 221 if (LF_ISSET(SEARCH_MSG)) 222 search_msg(sp, S_EOF); 223 break; 224 } 225 lno = 0; 226 wrapped = 1; 227 continue; 228 } 229 230 /* If already at EOL, just keep going. */ 231 if (len != 0 && coff == len) 232 continue; 233 234 /* Set the termination. */ 235 match[0].rm_so = coff; 236 match[0].rm_eo = len; 237 238 #if defined(DEBUG) && 0 239 TRACE(sp, "F search: %lu from %u to %u\n", 240 lno, coff, len != 0 ? len - 1 : len); 241 #endif 242 /* Search the line. */ 243 eval = regexec(&sp->re_c, l, 1, match, 244 (match[0].rm_so == 0 ? 0 : REG_NOTBOL) | REG_STARTEND); 245 if (eval == REG_NOMATCH) 246 continue; 247 if (eval != 0) { 248 if (LF_ISSET(SEARCH_MSG)) 249 re_error(sp, eval, &sp->re_c); 250 else 251 (void)sp->gp->scr_bell(sp); 252 break; 253 } 254 255 /* Warn if the search wrapped. */ 256 if (wrapped && LF_ISSET(SEARCH_WMSG)) 257 search_msg(sp, S_WRAP); 258 259 #if defined(DEBUG) && 0 260 TRACE(sp, "F search: %qu to %qu\n", 261 match[0].rm_so, match[0].rm_eo); 262 #endif 263 rm->lno = lno; 264 rm->cno = match[0].rm_so; 265 266 /* 267 * If a change command, it's possible to move beyond the end 268 * of a line. Historic vi generally got this wrong (e.g. try 269 * "c?$<cr>"). Not all that sure this gets it right, there 270 * are lots of strange cases. 271 */ 272 if (!LF_ISSET(SEARCH_EOL) && rm->cno >= len) 273 rm->cno = len != 0 ? len - 1 : 0; 274 275 rval = 0; 276 break; 277 } 278 279 if (LF_ISSET(SEARCH_MSG)) 280 search_busy(sp, BUSY_OFF); 281 return (rval); 282 } 283 284 /* 285 * b_search -- 286 * Do a backward search. 287 * 288 * PUBLIC: int b_search(SCR *, MARK *, MARK *, char *, size_t, char **, u_int); 289 */ 290 int 291 b_search(sp, fm, rm, ptrn, plen, eptrn, flags) 292 SCR *sp; 293 MARK *fm, *rm; 294 char *ptrn, **eptrn; 295 size_t plen; 296 u_int flags; 297 { 298 busy_t btype; 299 recno_t lno; 300 regmatch_t match[1]; 301 size_t coff, last, len; 302 int cnt, eval, rval, wrapped; 303 char *l; 304 305 if (search_init(sp, BACKWARD, ptrn, plen, eptrn, flags)) 306 return (1); 307 308 /* 309 * If doing incremental search, set the "starting" position past the 310 * current column, so that we search a minimal distance and still 311 * match special patterns, e.g., \> for the end of a word. This is 312 * safe when the cursor is at the end of a line because we only use 313 * it for comparison with the location of the match. 314 * 315 * Otherwise, start searching immediately before the cursor. If in 316 * the first column, start search on the previous line. 317 */ 318 if (LF_ISSET(SEARCH_INCR)) { 319 lno = fm->lno; 320 coff = fm->cno + 1; 321 } else { 322 if (fm->cno == 0) { 323 if (fm->lno == 1 && !O_ISSET(sp, O_WRAPSCAN)) { 324 if (LF_ISSET(SEARCH_MSG)) 325 search_msg(sp, S_SOF); 326 return (1); 327 } 328 lno = fm->lno - 1; 329 } else 330 lno = fm->lno; 331 coff = fm->cno; 332 } 333 334 btype = BUSY_ON; 335 for (cnt = INTERRUPT_CHECK, rval = 1, wrapped = 0;; --lno, coff = 0) { 336 if (cnt-- == 0) { 337 if (INTERRUPTED(sp)) 338 break; 339 if (LF_ISSET(SEARCH_MSG)) { 340 search_busy(sp, btype); 341 btype = BUSY_UPDATE; 342 } 343 cnt = INTERRUPT_CHECK; 344 } 345 if ((wrapped && lno < fm->lno) || lno == 0) { 346 if (wrapped) { 347 if (LF_ISSET(SEARCH_MSG)) 348 search_msg(sp, S_NOTFOUND); 349 break; 350 } 351 if (!O_ISSET(sp, O_WRAPSCAN)) { 352 if (LF_ISSET(SEARCH_MSG)) 353 search_msg(sp, S_SOF); 354 break; 355 } 356 if (db_last(sp, &lno)) 357 break; 358 if (lno == 0) { 359 if (LF_ISSET(SEARCH_MSG)) 360 search_msg(sp, S_EMPTY); 361 break; 362 } 363 ++lno; 364 wrapped = 1; 365 continue; 366 } 367 368 if (db_get(sp, lno, 0, &l, &len)) 369 break; 370 371 /* Set the termination. */ 372 match[0].rm_so = 0; 373 match[0].rm_eo = len; 374 375 #if defined(DEBUG) && 0 376 TRACE(sp, "B search: %lu from 0 to %qu\n", lno, match[0].rm_eo); 377 #endif 378 /* Search the line. */ 379 eval = regexec(&sp->re_c, l, 1, match, 380 (match[0].rm_eo == len ? 0 : REG_NOTEOL) | REG_STARTEND); 381 if (eval == REG_NOMATCH) 382 continue; 383 if (eval != 0) { 384 if (LF_ISSET(SEARCH_MSG)) 385 re_error(sp, eval, &sp->re_c); 386 else 387 (void)sp->gp->scr_bell(sp); 388 break; 389 } 390 391 /* Check for a match starting past the cursor. */ 392 if (coff != 0 && match[0].rm_so >= coff) 393 continue; 394 395 /* Warn if the search wrapped. */ 396 if (wrapped && LF_ISSET(SEARCH_WMSG)) 397 search_msg(sp, S_WRAP); 398 399 #if defined(DEBUG) && 0 400 TRACE(sp, "B found: %qu to %qu\n", 401 match[0].rm_so, match[0].rm_eo); 402 #endif 403 /* 404 * We now have the first match on the line. Step through the 405 * line character by character until find the last acceptable 406 * match. This is painful, we need a better interface to regex 407 * to make this work. 408 */ 409 for (;;) { 410 last = match[0].rm_so++; 411 if (match[0].rm_so >= len) 412 break; 413 match[0].rm_eo = len; 414 eval = regexec(&sp->re_c, l, 1, match, 415 (match[0].rm_so == 0 ? 0 : REG_NOTBOL) | 416 REG_STARTEND); 417 if (eval == REG_NOMATCH) 418 break; 419 if (eval != 0) { 420 if (LF_ISSET(SEARCH_MSG)) 421 re_error(sp, eval, &sp->re_c); 422 else 423 (void)sp->gp->scr_bell(sp); 424 goto err; 425 } 426 if (coff && match[0].rm_so >= coff) 427 break; 428 } 429 rm->lno = lno; 430 431 /* See comment in f_search(). */ 432 if (!LF_ISSET(SEARCH_EOL) && last >= len) 433 rm->cno = len != 0 ? len - 1 : 0; 434 else 435 rm->cno = last; 436 rval = 0; 437 break; 438 } 439 440 err: if (LF_ISSET(SEARCH_MSG)) 441 search_busy(sp, BUSY_OFF); 442 return (rval); 443 } 444 445 /* 446 * search_msg -- 447 * Display one of the search messages. 448 */ 449 static void 450 search_msg(sp, msg) 451 SCR *sp; 452 smsg_t msg; 453 { 454 switch (msg) { 455 case S_EMPTY: 456 msgq(sp, M_ERR, "072|File empty; nothing to search"); 457 break; 458 case S_EOF: 459 msgq(sp, M_ERR, 460 "073|Reached end-of-file without finding the pattern"); 461 break; 462 case S_NOPREV: 463 msgq(sp, M_ERR, "074|No previous search pattern"); 464 break; 465 case S_NOTFOUND: 466 msgq(sp, M_ERR, "075|Pattern not found"); 467 break; 468 case S_SOF: 469 msgq(sp, M_ERR, 470 "076|Reached top-of-file without finding the pattern"); 471 break; 472 case S_WRAP: 473 msgq(sp, M_ERR, "077|Search wrapped"); 474 break; 475 default: 476 abort(); 477 } 478 } 479 480 /* 481 * search_busy -- 482 * Put up the busy searching message. 483 * 484 * PUBLIC: void search_busy(SCR *, busy_t); 485 */ 486 void 487 search_busy(sp, btype) 488 SCR *sp; 489 busy_t btype; 490 { 491 sp->gp->scr_busy(sp, "078|Searching...", btype); 492 } 493