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
search_init(SCR * sp,dir_t dir,CHAR_T * ptrn,size_t plen,CHAR_T ** epp,u_int flags)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
f_search(SCR * sp,MARK * fm,MARK * rm,CHAR_T * ptrn,size_t plen,CHAR_T ** eptrn,u_int flags)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
b_search(SCR * sp,MARK * fm,MARK * rm,CHAR_T * ptrn,size_t plen,CHAR_T ** eptrn,u_int flags)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
search_msg(SCR * sp,smsg_t msg)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
search_busy(SCR * sp,busy_t btype)483 search_busy(SCR *sp, busy_t btype)
484 {
485 sp->gp->scr_busy(sp, "078|Searching...", btype);
486 }
487