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