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