1 /* $NetBSD: ex_tag.c,v 1.12 2014/08/22 21:28:20 aymeric 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 * This code is derived from software contributed to Berkeley by
9 * David Hitz of Auspex Systems, Inc.
10 *
11 * See the LICENSE file for redistribution information.
12 */
13
14 #include "config.h"
15
16 #include <sys/cdefs.h>
17 #if 0
18 #ifndef lint
19 static const char sccsid[] = "Id: ex_tag.c,v 10.50 2004/03/16 14:09:11 skimo Exp (Berkeley) Date: 2004/03/16 14:09:11 ";
20 #endif /* not lint */
21 #else
22 __RCSID("$NetBSD: ex_tag.c,v 1.12 2014/08/22 21:28:20 aymeric Exp $");
23 #endif
24
25 #include <sys/param.h>
26 #include <sys/types.h> /* XXX: param.h may not have included types.h */
27
28 #ifdef HAVE_SYS_MMAN_H
29 #include <sys/mman.h>
30 #endif
31
32 #include <sys/queue.h>
33 #include <sys/stat.h>
34 #include <sys/time.h>
35
36 #include <bitstring.h>
37 #include <ctype.h>
38 #include <errno.h>
39 #include <fcntl.h>
40 #include <limits.h>
41 #include <stddef.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <unistd.h>
46
47 #include "../common/common.h"
48 #include "../vi/vi.h"
49 #include "tag.h"
50
51 static char *binary_search __P((char *, char *, char *));
52 static int compare __P((char *, char *, char *));
53 static void ctag_file __P((SCR *, TAGF *, char *, char **, size_t *));
54 static int ctag_search __P((SCR *, CHAR_T *, size_t, char *));
55 #ifdef GTAGS
56 static int getentry __P((char *, char **, char **, char **));
57 static TAGQ *gtag_slist __P((SCR *, CHAR_T *, int));
58 #endif
59 static int ctag_sfile __P((SCR *, TAGF *, TAGQ *, char *));
60 static TAGQ *ctag_slist __P((SCR *, CHAR_T *));
61 static char *linear_search __P((char *, char *, char *, unsigned long));
62 static int tag_copy __P((SCR *, TAG *, TAG **));
63 static int tag_pop __P((SCR *, TAGQ *, int));
64 static int tagf_copy __P((SCR *, TAGF *, TAGF **));
65 static int tagf_free __P((SCR *, TAGF *));
66 static int tagq_copy __P((SCR *, TAGQ *, TAGQ **));
67
68 /*
69 * ex_tag_first --
70 * The tag code can be entered from main, e.g., "vi -t tag".
71 *
72 * PUBLIC: int ex_tag_first __P((SCR *, const CHAR_T *));
73 */
74 int
ex_tag_first(SCR * sp,const CHAR_T * tagarg)75 ex_tag_first(SCR *sp, const CHAR_T *tagarg)
76 {
77 EXCMD cmd;
78
79 /* Build an argument for the ex :tag command. */
80 ex_cinit(sp, &cmd, C_TAG, 0, OOBLNO, OOBLNO, 0);
81 argv_exp0(sp, &cmd, tagarg, STRLEN(tagarg));
82
83 /*
84 * XXX
85 * Historic vi went ahead and created a temporary file when it failed
86 * to find the tag. We match historic practice, but don't distinguish
87 * between real error and failure to find the tag.
88 */
89 if (ex_tag_push(sp, &cmd))
90 return (0);
91
92 /* Display tags in the center of the screen. */
93 F_CLR(sp, SC_SCR_TOP);
94 F_SET(sp, SC_SCR_CENTER);
95
96 return (0);
97 }
98
99 #ifdef GTAGS
100 /*
101 * ex_rtag_push -- ^]
102 * :rtag[!] [string]
103 *
104 * Enter a new TAGQ context based on a ctag string.
105 *
106 * PUBLIC: int ex_rtag_push __P((SCR *, EXCMD *));
107 */
108 int
ex_rtag_push(SCR * sp,EXCMD * cmdp)109 ex_rtag_push(SCR *sp, EXCMD *cmdp)
110 {
111 F_SET(cmdp, E_REFERENCE);
112 return ex_tag_push(sp, cmdp);
113 }
114 #endif
115
116 /*
117 * ex_tag_push -- ^]
118 * :tag[!] [string]
119 *
120 * Enter a new TAGQ context based on a ctag string.
121 *
122 * PUBLIC: int ex_tag_push __P((SCR *, EXCMD *));
123 */
124 int
ex_tag_push(SCR * sp,EXCMD * cmdp)125 ex_tag_push(SCR *sp, EXCMD *cmdp)
126 {
127 EX_PRIVATE *exp;
128 TAGQ *tqp;
129 unsigned long tl;
130
131 exp = EXP(sp);
132 switch (cmdp->argc) {
133 case 1:
134 if (exp->tag_last != NULL)
135 free(exp->tag_last);
136
137 if ((exp->tag_last = v_wstrdup(sp, cmdp->argv[0]->bp,
138 cmdp->argv[0]->len)) == NULL) {
139 msgq(sp, M_SYSERR, NULL);
140 return (1);
141 }
142
143 /* Taglength may limit the number of characters. */
144 if ((tl =
145 O_VAL(sp, O_TAGLENGTH)) != 0 && STRLEN(exp->tag_last) > tl)
146 exp->tag_last[tl] = '\0';
147 break;
148 case 0:
149 if (exp->tag_last == NULL) {
150 msgq(sp, M_ERR, "158|No previous tag entered");
151 return (1);
152 }
153 break;
154 default:
155 abort();
156 }
157
158 /* Get the tag information. */
159 #ifdef GTAGS
160 if (O_ISSET(sp, O_GTAGSMODE)) {
161 if ((tqp = gtag_slist(sp, exp->tag_last,
162 F_ISSET(cmdp, E_REFERENCE))) == NULL)
163 return (1);
164 } else
165 #endif
166 if ((tqp = ctag_slist(sp, exp->tag_last)) == NULL)
167 return (1);
168
169 if (tagq_push(sp, tqp, F_ISSET(cmdp, E_NEWSCREEN),
170 FL_ISSET(cmdp->iflags, E_C_FORCE)))
171 return 1;
172
173 return 0;
174 }
175
176 /*
177 * ex_tag_next --
178 * Switch context to the next TAG.
179 *
180 * PUBLIC: int ex_tag_next __P((SCR *, EXCMD *));
181 */
182 int
ex_tag_next(SCR * sp,EXCMD * cmdp)183 ex_tag_next(SCR *sp, EXCMD *cmdp)
184 {
185 EX_PRIVATE *exp;
186 TAG *tp;
187 TAGQ *tqp;
188 const char *np;
189 size_t nlen;
190
191 exp = EXP(sp);
192 if ((tqp = TAILQ_FIRST(&exp->tq)) == NULL) {
193 tag_msg(sp, TAG_EMPTY, NULL);
194 return (1);
195 }
196 if ((tp = TAILQ_NEXT(tqp->current, q)) == NULL) {
197 msgq(sp, M_ERR, "282|Already at the last tag of this group");
198 return (1);
199 }
200 if (ex_tag_nswitch(sp, tp, FL_ISSET(cmdp->iflags, E_C_FORCE)))
201 return (1);
202 tqp->current = tp;
203
204 if (F_ISSET(tqp, TAG_CSCOPE))
205 (void)cscope_search(sp, tqp, tp);
206 else
207 (void)ctag_search(sp, tp->search, tp->slen, tqp->tag);
208 if (tqp->current->msg) {
209 INT2CHAR(sp, tqp->current->msg, tqp->current->mlen + 1,
210 np, nlen);
211 msgq(sp, M_INFO, "%s", np);
212 }
213 return (0);
214 }
215
216 /*
217 * ex_tag_prev --
218 * Switch context to the next TAG.
219 *
220 * PUBLIC: int ex_tag_prev __P((SCR *, EXCMD *));
221 */
222 int
ex_tag_prev(SCR * sp,EXCMD * cmdp)223 ex_tag_prev(SCR *sp, EXCMD *cmdp)
224 {
225 EX_PRIVATE *exp;
226 TAG *tp;
227 TAGQ *tqp;
228 const char *np;
229 size_t nlen;
230
231 exp = EXP(sp);
232 if ((tqp = TAILQ_FIRST(&exp->tq)) == NULL) {
233 tag_msg(sp, TAG_EMPTY, NULL);
234 return (0);
235 }
236 if ((tp = TAILQ_PREV(tqp->current, _tagqh, q)) == NULL) {
237 msgq(sp, M_ERR, "255|Already at the first tag of this group");
238 return (1);
239 }
240 if (ex_tag_nswitch(sp, tp, FL_ISSET(cmdp->iflags, E_C_FORCE)))
241 return (1);
242 tqp->current = tp;
243
244 if (F_ISSET(tqp, TAG_CSCOPE))
245 (void)cscope_search(sp, tqp, tp);
246 else
247 (void)ctag_search(sp, tp->search, tp->slen, tqp->tag);
248 if (tqp->current->msg) {
249 INT2CHAR(sp, tqp->current->msg, tqp->current->mlen + 1,
250 np, nlen);
251 msgq(sp, M_INFO, "%s", np);
252 }
253 return (0);
254 }
255
256 /*
257 * ex_tag_nswitch --
258 * Switch context to the specified TAG.
259 *
260 * PUBLIC: int ex_tag_nswitch __P((SCR *, TAG *, int));
261 */
262 int
ex_tag_nswitch(SCR * sp,TAG * tp,int force)263 ex_tag_nswitch(SCR *sp, TAG *tp, int force)
264 {
265 /* Get a file structure. */
266 if (tp->frp == NULL && (tp->frp = file_add(sp, tp->fname)) == NULL)
267 return (1);
268
269 /* If not changing files, return, we're done. */
270 if (tp->frp == sp->frp)
271 return (0);
272
273 /* Check for permission to leave. */
274 if (file_m1(sp, force, FS_ALL | FS_POSSIBLE))
275 return (1);
276
277 /* Initialize the new file. */
278 if (file_init(sp, tp->frp, NULL, FS_SETALT))
279 return (1);
280
281 /* Display tags in the center of the screen. */
282 F_CLR(sp, SC_SCR_TOP);
283 F_SET(sp, SC_SCR_CENTER);
284
285 /* Switch. */
286 F_SET(sp, SC_FSWITCH);
287 return (0);
288 }
289
290 /*
291 * ex_tag_Nswitch --
292 * Switch context to the specified TAG in a new screen.
293 *
294 * PUBLIC: int ex_tag_Nswitch __P((SCR *, TAG *, int));
295 */
296 int
ex_tag_Nswitch(SCR * sp,TAG * tp,int force)297 ex_tag_Nswitch(SCR *sp, TAG *tp, int force)
298 {
299 SCR *new;
300
301 /* Get a file structure. */
302 if (tp->frp == NULL && (tp->frp = file_add(sp, tp->fname)) == NULL)
303 return (1);
304
305 /* Get a new screen. */
306 if (screen_init(sp->gp, sp, &new))
307 return (1);
308 if (vs_split(sp, new, 0)) {
309 (void)file_end(new, new->ep, 1);
310 (void)screen_fini(new);
311 return (1);
312 }
313
314 /* Get a backing file. */
315 if (tp->frp == sp->frp) {
316 /* Copy file state. */
317 new->ep = sp->ep;
318 ++new->ep->refcnt;
319 TAILQ_INSERT_HEAD(&new->ep->scrq, new, eq);
320
321 new->frp = tp->frp;
322 new->frp->flags = sp->frp->flags;
323 } else if (file_init(new, tp->frp, NULL, force)) {
324 (void)vs_discard(new, NULL);
325 (void)screen_end(new);
326 return (1);
327 }
328
329 /* Create the argument list. */
330 new->cargv = new->argv = ex_buildargv(sp, NULL, tp->frp->name);
331
332 /* Display tags in the center of the screen. */
333 F_CLR(new, SC_SCR_TOP);
334 F_SET(new, SC_SCR_CENTER);
335
336 /* Switch. */
337 sp->nextdisp = new;
338 F_SET(sp, SC_SSWITCH);
339
340 return (0);
341 }
342
343 /*
344 * ex_tag_pop -- ^T
345 * :tagp[op][!] [number | file]
346 *
347 * Pop to a previous TAGQ context.
348 *
349 * PUBLIC: int ex_tag_pop __P((SCR *, EXCMD *));
350 */
351 int
ex_tag_pop(SCR * sp,EXCMD * cmdp)352 ex_tag_pop(SCR *sp, EXCMD *cmdp)
353 {
354 EX_PRIVATE *exp;
355 TAGQ *tqp, *dtqp = NULL;
356 size_t arglen;
357 long off;
358 const char *arg;
359 char *p, *t;
360 size_t nlen;
361
362 /* Check for an empty stack. */
363 exp = EXP(sp);
364 if (TAILQ_EMPTY(&exp->tq)) {
365 tag_msg(sp, TAG_EMPTY, NULL);
366 return (1);
367 }
368
369 /* Find the last TAG structure that we're going to DISCARD! */
370 switch (cmdp->argc) {
371 case 0: /* Pop one tag. */
372 dtqp = TAILQ_FIRST(&exp->tq);
373 break;
374 case 1: /* Name or number. */
375 INT2CHAR(sp, cmdp->argv[0]->bp, cmdp->argv[0]->len+1,
376 arg, nlen);
377 off = strtol(arg, &p, 10);
378 if (*p != '\0')
379 goto filearg;
380
381 /* Number: pop that many queue entries. */
382 if (off < 1)
383 return (0);
384 TAILQ_FOREACH(tqp, &exp->tq, q)
385 if (--off <= 1)
386 break;
387 if (tqp == NULL) {
388 msgq(sp, M_ERR,
389 "159|Less than %s entries on the tags stack; use :display t[ags]",
390 arg);
391 return (1);
392 }
393 dtqp = tqp;
394 break;
395
396 /* File argument: pop to that queue entry. */
397 filearg: arglen = strlen(arg);
398 for (tqp = TAILQ_FIRST(&exp->tq);
399 tqp != NULL;
400 dtqp = tqp, tqp = TAILQ_NEXT(tqp, q)) {
401 /* Don't pop to the current file. */
402 if (tqp == TAILQ_FIRST(&exp->tq))
403 continue;
404 p = tqp->current->frp->name;
405 if ((t = strrchr(p, '/')) == NULL)
406 t = p;
407 else
408 ++t;
409 if (!strncmp(arg, t, arglen))
410 break;
411 }
412 if (tqp == NULL) {
413 msgq_str(sp, M_ERR, arg,
414 "160|No file %s on the tags stack to return to; use :display t[ags]");
415 return (1);
416 }
417 break;
418 default:
419 abort();
420 }
421
422 return (tag_pop(sp, dtqp, FL_ISSET(cmdp->iflags, E_C_FORCE)));
423 }
424
425 /*
426 * ex_tag_top -- :tagt[op][!]
427 * Clear the tag stack.
428 *
429 * PUBLIC: int ex_tag_top __P((SCR *, EXCMD *));
430 */
431 int
ex_tag_top(SCR * sp,EXCMD * cmdp)432 ex_tag_top(SCR *sp, EXCMD *cmdp)
433 {
434 EX_PRIVATE *exp;
435 TAGQ *tqp;
436
437 exp = EXP(sp);
438
439 /* Check for an empty stack. */
440 if (TAILQ_EMPTY(&exp->tq)) {
441 tag_msg(sp, TAG_EMPTY, NULL);
442 return (1);
443 }
444
445 /* Return to the oldest information. */
446 tqp = TAILQ_LAST(&exp->tq, _tqh);
447 tqp = TAILQ_PREV(tqp, _tqh, q);
448 return tag_pop(sp, tqp, FL_ISSET(cmdp->iflags, E_C_FORCE));
449 }
450
451 /*
452 * tag_pop --
453 * Pop up to and including the specified TAGQ context.
454 */
455 static int
tag_pop(SCR * sp,TAGQ * dtqp,int force)456 tag_pop(SCR *sp, TAGQ *dtqp, int force)
457 {
458 EX_PRIVATE *exp;
459 TAG *tp;
460 TAGQ *tqp;
461
462 exp = EXP(sp);
463
464 /*
465 * Update the cursor from the saved TAG information of the TAG
466 * structure we're moving to.
467 */
468 tp = TAILQ_NEXT(dtqp, q)->current;
469 if (tp->frp == sp->frp) {
470 sp->lno = tp->lno;
471 sp->cno = tp->cno;
472 } else {
473 if (file_m1(sp, force, FS_ALL | FS_POSSIBLE))
474 return (1);
475
476 tp->frp->lno = tp->lno;
477 tp->frp->cno = tp->cno;
478 F_SET(sp->frp, FR_CURSORSET);
479 if (file_init(sp, tp->frp, NULL, FS_SETALT))
480 return (1);
481
482 F_SET(sp, SC_FSWITCH);
483 }
484
485 /* Pop entries off the queue up to and including dtqp. */
486 do {
487 tqp = TAILQ_FIRST(&exp->tq);
488 if (tagq_free(sp, tqp))
489 return (0);
490 } while (tqp != dtqp);
491
492 /*
493 * If only a single tag left, we've returned to the first tag point,
494 * and the stack is now empty.
495 */
496 if (TAILQ_NEXT(TAILQ_FIRST(&exp->tq), q) == NULL)
497 tagq_free(sp, TAILQ_FIRST(&exp->tq));
498
499 return (0);
500 }
501
502 /*
503 * ex_tag_display --
504 * Display the list of tags.
505 *
506 * PUBLIC: int ex_tag_display __P((SCR *));
507 */
508 int
ex_tag_display(SCR * sp)509 ex_tag_display(SCR *sp)
510 {
511 EX_PRIVATE *exp;
512 TAG *tp;
513 TAGQ *tqp;
514 int cnt;
515 size_t len;
516 char *p;
517
518 exp = EXP(sp);
519 if (TAILQ_EMPTY(&exp->tq)) {
520 tag_msg(sp, TAG_EMPTY, NULL);
521 return (0);
522 }
523
524 /*
525 * We give the file name 20 columns and the search string the rest.
526 * If there's not enough room, we don't do anything special, it's
527 * not worth the effort, it just makes the display more confusing.
528 *
529 * We also assume that characters in file names map 1-1 to printing
530 * characters. This might not be true, but I don't think it's worth
531 * fixing. (The obvious fix is to pass the filenames through the
532 * msg_print function.)
533 */
534 #define L_NAME 30 /* Name. */
535 #define L_SLOP 4 /* Leading number plus trailing *. */
536 #define L_SPACE 5 /* Spaces after name, before tag. */
537 #define L_TAG 20 /* Tag. */
538 if (sp->cols <= L_NAME + L_SLOP) {
539 msgq(sp, M_ERR, "292|Display too small.");
540 return (0);
541 }
542
543 /*
544 * Display the list of tags for each queue entry. The first entry
545 * is numbered, and the current tag entry has an asterisk appended.
546 */
547 for (cnt = 1, tqp = TAILQ_FIRST(&exp->tq); !INTERRUPTED(sp) &&
548 tqp != NULL; ++cnt, tqp = TAILQ_NEXT(tqp, q))
549 TAILQ_FOREACH(tp, &tqp->tagq, q) {
550 if (tp == TAILQ_FIRST(&tqp->tagq))
551 (void)ex_printf(sp, "%2d ", cnt);
552 else
553 (void)ex_printf(sp, " ");
554 p = tp->frp == NULL ? tp->fname : tp->frp->name;
555 if ((len = strlen(p)) > L_NAME) {
556 len = len - (L_NAME - 4);
557 (void)ex_printf(sp, " ... %*.*s",
558 L_NAME - 4, L_NAME - 4, p + len);
559 } else
560 (void)ex_printf(sp,
561 " %*.*s", L_NAME, L_NAME, p);
562 if (tqp->current == tp)
563 (void)ex_printf(sp, "*");
564
565 if (tp == TAILQ_FIRST(&tqp->tagq) && tqp->tag != NULL &&
566 (sp->cols - L_NAME) >= L_TAG + L_SPACE) {
567 len = strlen(tqp->tag);
568 if (len > sp->cols - (L_NAME + L_SPACE))
569 len = sp->cols - (L_NAME + L_SPACE);
570 (void)ex_printf(sp, "%s%.*s",
571 tqp->current == tp ? " " : " ",
572 (int)len, tqp->tag);
573 }
574 (void)ex_printf(sp, "\n");
575 }
576 return (0);
577 }
578
579 /*
580 * ex_tag_copy --
581 * Copy a screen's tag structures.
582 *
583 * PUBLIC: int ex_tag_copy __P((SCR *, SCR *));
584 */
585 int
ex_tag_copy(SCR * orig,SCR * sp)586 ex_tag_copy(SCR *orig, SCR *sp)
587 {
588 EX_PRIVATE *oexp, *nexp;
589 TAGQ *aqp, *tqp;
590 TAG *ap, *tp;
591 TAGF *atfp, *tfp;
592
593 oexp = EXP(orig);
594 nexp = EXP(sp);
595
596 /* Copy tag queue and tags stack. */
597 TAILQ_FOREACH(aqp, &oexp->tq, q) {
598 if (tagq_copy(sp, aqp, &tqp))
599 return (1);
600 TAILQ_FOREACH(ap, &aqp->tagq, q) {
601 if (tag_copy(sp, ap, &tp))
602 return (1);
603 /* Set the current pointer. */
604 if (aqp->current == ap)
605 tqp->current = tp;
606 TAILQ_INSERT_TAIL(&tqp->tagq, tp, q);
607 }
608 TAILQ_INSERT_TAIL(&nexp->tq, tqp, q);
609 F_SET(tqp, TAG_IS_LINKED);
610 }
611
612 /* Copy list of tag files. */
613
614 TAILQ_FOREACH(atfp, &oexp->tagfq, q) {
615 if (tagf_copy(sp, atfp, &tfp))
616 return (1);
617 TAILQ_INSERT_TAIL(&nexp->tagfq, tfp, q);
618 }
619
620 /* Copy the last tag. */
621 if (oexp->tag_last != NULL &&
622 (nexp->tag_last = v_wstrdup(sp, oexp->tag_last,
623 STRLEN(oexp->tag_last))) == NULL) {
624 msgq(sp, M_SYSERR, NULL);
625 return (1);
626 }
627 return (0);
628 }
629
630 /*
631 * tagf_copy --
632 * Copy a TAGF structure and return it in new memory.
633 */
634 static int
tagf_copy(SCR * sp,TAGF * otfp,TAGF ** tfpp)635 tagf_copy(SCR *sp, TAGF *otfp, TAGF **tfpp)
636 {
637 TAGF *tfp;
638
639 MALLOC_RET(sp, tfp, TAGF *, sizeof(TAGF));
640 *tfp = *otfp;
641
642 /* XXX: Allocate as part of the TAGF structure!!! */
643 if ((tfp->name = strdup(otfp->name)) == NULL)
644 return (1);
645
646 *tfpp = tfp;
647 return (0);
648 }
649
650 /*
651 * tagq_copy --
652 * Copy a TAGQ structure and return it in new memory.
653 */
654 static int
tagq_copy(SCR * sp,TAGQ * otqp,TAGQ ** tqpp)655 tagq_copy(SCR *sp, TAGQ *otqp, TAGQ **tqpp)
656 {
657 TAGQ *tqp;
658 size_t len;
659
660 len = sizeof(TAGQ);
661 if (otqp->tag != NULL)
662 len += otqp->tlen + 1;
663 MALLOC_RET(sp, tqp, TAGQ *, len);
664 memcpy(tqp, otqp, len);
665
666 TAILQ_INIT(&tqp->tagq);
667 tqp->current = NULL;
668 if (otqp->tag != NULL)
669 tqp->tag = tqp->buf;
670
671 *tqpp = tqp;
672 return (0);
673 }
674
675 /*
676 * tag_copy --
677 * Copy a TAG structure and return it in new memory.
678 */
679 static int
tag_copy(SCR * sp,TAG * otp,TAG ** tpp)680 tag_copy(SCR *sp, TAG *otp, TAG **tpp)
681 {
682 TAG *tp;
683 size_t len;
684
685 len = sizeof(TAG);
686 if (otp->fname != NULL)
687 len += otp->fnlen + 1;
688 if (otp->search != NULL)
689 len += otp->slen + 1;
690 if (otp->msg != NULL)
691 len += otp->mlen + 1;
692 MALLOC_RET(sp, tp, TAG *, len);
693 memcpy(tp, otp, len);
694
695 if (otp->fname != NULL)
696 tp->fname = (char *)tp->buf;
697 if (otp->search != NULL)
698 tp->search = tp->buf + (otp->search - otp->buf);
699 if (otp->msg != NULL)
700 tp->msg = tp->buf + (otp->msg - otp->buf);
701
702 *tpp = tp;
703 return (0);
704 }
705
706 /*
707 * tagf_free --
708 * Free a TAGF structure.
709 */
710 static int
tagf_free(SCR * sp,TAGF * tfp)711 tagf_free(SCR *sp, TAGF *tfp)
712 {
713 EX_PRIVATE *exp;
714
715 exp = EXP(sp);
716 TAILQ_REMOVE(&exp->tagfq, tfp, q);
717 free(tfp->name);
718 free(tfp);
719 return (0);
720 }
721
722 /*
723 * tagq_free --
724 * Free a TAGQ structure (and associated TAG structures).
725 *
726 * PUBLIC: int tagq_free __P((SCR *, TAGQ *));
727 */
728 int
tagq_free(SCR * sp,TAGQ * tqp)729 tagq_free(SCR *sp, TAGQ *tqp)
730 {
731 EX_PRIVATE *exp;
732 TAG *tp;
733
734 exp = EXP(sp);
735 while ((tp = TAILQ_FIRST(&tqp->tagq)) != NULL) {
736 TAILQ_REMOVE(&tqp->tagq, tp, q);
737 free(tp);
738 }
739 /*
740 * !!!
741 * If allocated and then the user failed to switch files, the TAGQ
742 * structure was never attached to any list.
743 */
744 if (F_ISSET(tqp, TAG_IS_LINKED))
745 TAILQ_REMOVE(&exp->tq, tqp, q);
746 free(tqp);
747 return (0);
748 }
749
750 /*
751 * PUBLIC: int tagq_push __P((SCR*, TAGQ*, int, int ));
752 */
753 int
tagq_push(SCR * sp,TAGQ * tqp,int new_screen,int force)754 tagq_push(SCR *sp, TAGQ *tqp, int new_screen, int force)
755 {
756 EX_PRIVATE *exp;
757 FREF *frp;
758 TAG *rtp;
759 TAGQ *rtqp;
760 db_recno_t lno;
761 size_t cno;
762 int istmp;
763 const char *np;
764 size_t nlen;
765
766 exp = EXP(sp);
767
768 /*
769 * Allocate all necessary memory before swapping screens. Initialize
770 * flags so we know what to free.
771 */
772 rtp = NULL;
773 rtqp = NULL;
774 if (TAILQ_EMPTY(&exp->tq)) {
775 /* Initialize the `local context' tag queue structure. */
776 CALLOC_GOTO(sp, rtqp, TAGQ *, 1, sizeof(TAGQ));
777 TAILQ_INIT(&rtqp->tagq);
778
779 /* Initialize and link in its tag structure. */
780 CALLOC_GOTO(sp, rtp, TAG *, 1, sizeof(TAG));
781 TAILQ_INSERT_HEAD(&rtqp->tagq, rtp, q);
782 rtqp->current = rtp;
783 }
784
785 /*
786 * Stick the current context information in a convenient place, we're
787 * about to lose it. Note, if we're called on editor startup, there
788 * will be no FREF structure.
789 */
790 frp = sp->frp;
791 lno = sp->lno;
792 cno = sp->cno;
793 istmp = frp == NULL || (F_ISSET(frp, FR_TMPFILE) && !new_screen);
794
795 /* Try to switch to the tag. */
796 if (new_screen) {
797 if (ex_tag_Nswitch(sp, TAILQ_FIRST(&tqp->tagq), force))
798 goto err;
799
800 /* Everything else gets done in the new screen. */
801 sp = sp->nextdisp;
802 exp = EXP(sp);
803 } else
804 if (ex_tag_nswitch(sp, TAILQ_FIRST(&tqp->tagq), force))
805 goto err;
806
807 /*
808 * If this is the first tag, put a `current location' queue entry
809 * in place, so we can pop all the way back to the current mark.
810 * Note, it doesn't point to much of anything, it's a placeholder.
811 */
812 if (TAILQ_EMPTY(&exp->tq)) {
813 TAILQ_INSERT_HEAD(&exp->tq, rtqp, q);
814 F_SET(rtqp, TAG_IS_LINKED);
815 } else {
816 free(rtqp);
817 rtqp = TAILQ_FIRST(&exp->tq);
818 }
819
820 /* Link the new TAGQ structure into place. */
821 TAILQ_INSERT_HEAD(&exp->tq, tqp, q);
822 F_SET(tqp, TAG_IS_LINKED);
823
824 (void)ctag_search(sp,
825 tqp->current->search, tqp->current->slen, tqp->tag);
826 if (tqp->current->msg) {
827 INT2CHAR(sp, tqp->current->msg, tqp->current->mlen + 1,
828 np, nlen);
829 msgq(sp, M_INFO, "%s", np);
830 }
831
832 /*
833 * Move the current context from the temporary save area into the
834 * right structure.
835 *
836 * If we were in a temporary file, we don't have a context to which
837 * we can return, so just make it be the same as what we're moving
838 * to. It will be a little odd that ^T doesn't change anything, but
839 * I don't think it's a big deal.
840 */
841 if (istmp) {
842 rtqp->current->frp = sp->frp;
843 rtqp->current->lno = sp->lno;
844 rtqp->current->cno = sp->cno;
845 } else {
846 rtqp->current->frp = frp;
847 rtqp->current->lno = lno;
848 rtqp->current->cno = cno;
849 }
850 return (0);
851
852 err:
853 alloc_err:
854 if (rtqp != NULL)
855 free(rtqp);
856 if (rtp != NULL)
857 free(rtp);
858 tagq_free(sp, tqp);
859 return (1);
860 }
861
862 /*
863 * tag_msg
864 * A few common messages.
865 *
866 * PUBLIC: void tag_msg __P((SCR *, tagmsg_t, char *));
867 */
868 void
tag_msg(SCR * sp,tagmsg_t msg,char * tag)869 tag_msg(SCR *sp, tagmsg_t msg, char *tag)
870 {
871 switch (msg) {
872 case TAG_BADLNO:
873 msgq_str(sp, M_ERR, tag,
874 "164|%s: the tag's line number is past the end of the file");
875 break;
876 case TAG_EMPTY:
877 msgq(sp, M_INFO, "165|The tags stack is empty");
878 break;
879 case TAG_SEARCH:
880 msgq_str(sp, M_ERR, tag, "166|%s: search pattern not found");
881 break;
882 default:
883 abort();
884 }
885 }
886
887 /*
888 * ex_tagf_alloc --
889 * Create a new list of ctag files.
890 *
891 * PUBLIC: int ex_tagf_alloc __P((SCR *, const char *));
892 */
893 int
ex_tagf_alloc(SCR * sp,const char * str)894 ex_tagf_alloc(SCR *sp, const char *str)
895 {
896 EX_PRIVATE *exp;
897 TAGF *tfp;
898 size_t len;
899 const char *p, *t;
900
901 /* Free current queue. */
902 exp = EXP(sp);
903 while ((tfp = TAILQ_FIRST(&exp->tagfq)) != NULL)
904 tagf_free(sp, tfp);
905
906 /* Create new queue. */
907 for (p = t = str;; ++p) {
908 if (*p == '\0' || isblank((unsigned char)*p)) {
909 if ((len = p - t) > 1) {
910 MALLOC_RET(sp, tfp, TAGF *, sizeof(TAGF));
911 MALLOC(sp, tfp->name, char *, len + 1);
912 if (tfp->name == NULL) {
913 free(tfp);
914 return (1);
915 }
916 memcpy(tfp->name, t, len);
917 tfp->name[len] = '\0';
918 tfp->flags = 0;
919 TAILQ_INSERT_TAIL(&exp->tagfq, tfp, q);
920 }
921 t = p + 1;
922 }
923 if (*p == '\0')
924 break;
925 }
926 return (0);
927 }
928 /* Free previous queue. */
929 /*
930 * ex_tag_free --
931 * Free the ex tag information.
932 *
933 * PUBLIC: int ex_tag_free __P((SCR *));
934 */
935 int
ex_tag_free(SCR * sp)936 ex_tag_free(SCR *sp)
937 {
938 EX_PRIVATE *exp;
939 TAGF *tfp;
940 TAGQ *tqp;
941
942 /* Free up tag information. */
943 exp = EXP(sp);
944 while ((tqp = TAILQ_FIRST(&exp->tq)) != NULL)
945 tagq_free(sp, tqp);
946 while ((tfp = TAILQ_FIRST(&exp->tagfq)) != NULL)
947 tagf_free(sp, tfp);
948 if (exp->tag_last != NULL)
949 free(exp->tag_last);
950 return (0);
951 }
952
953 /*
954 * ctag_search --
955 * Search a file for a tag.
956 */
957 static int
ctag_search(SCR * sp,CHAR_T * search,size_t slen,char * tag)958 ctag_search(SCR *sp, CHAR_T *search, size_t slen, char *tag)
959 {
960 MARK m;
961 char *p;
962 const char *np;
963 size_t nlen;
964
965 /*
966 * !!!
967 * The historic tags file format (from a long, long time ago...)
968 * used a line number, not a search string. I got complaints, so
969 * people are still using the format. POSIX 1003.2 permits it.
970 */
971 if (ISDIGIT((UCHAR_T)search[0])) {
972 INT2CHAR(sp, search, slen+1, np, nlen);
973 m.lno = atoi(np);
974 if (!db_exist(sp, m.lno)) {
975 tag_msg(sp, TAG_BADLNO, tag);
976 return (1);
977 }
978 } else {
979 /*
980 * Search for the tag; cheap fallback for C functions
981 * if the name is the same but the arguments have changed.
982 */
983 m.lno = 1;
984 m.cno = 0;
985 if (f_search(sp, &m, &m,
986 search, slen, NULL,
987 SEARCH_FIRST | SEARCH_TAG | SEARCH_PARSE)) {
988 INT2CHAR(sp, search, slen, np, nlen);
989 if ((p = strrchr(np, '(')) != NULL) {
990 slen = p - np;
991 if (f_search(sp, &m, &m, search, slen,
992 NULL, SEARCH_FIRST | SEARCH_TAG))
993 goto notfound;
994 } else {
995 notfound: tag_msg(sp, TAG_SEARCH, tag);
996 return (1);
997 }
998 }
999 /*
1000 * !!!
1001 * Historically, tags set the search direction if it wasn't
1002 * already set.
1003 */
1004 if (sp->searchdir == NOTSET)
1005 sp->searchdir = FORWARD;
1006 }
1007
1008 /*
1009 * !!!
1010 * Tags move to the first non-blank, NOT the search pattern start.
1011 */
1012 sp->lno = m.lno;
1013 sp->cno = 0;
1014 (void)nonblank(sp, sp->lno, &sp->cno);
1015 return (0);
1016 }
1017
1018 #ifdef GTAGS
1019 /*
1020 * getentry --
1021 * get tag information from current line.
1022 *
1023 * gtags temporary file format.
1024 * <tag> <lineno> <file> <image>
1025 *
1026 * sample.
1027 * +------------------------------------------------
1028 * |main 30 main.c main(argc, argv)
1029 * |func 21 subr.c func(arg)
1030 */
1031 static int
getentry(char * buf,char ** tag,char ** file,char ** line)1032 getentry(char *buf, char **tag, char **file, char **line)
1033 {
1034 char *p = buf;
1035
1036 for (*tag = p; *p && !isspace((unsigned char)*p); p++) /* tag name */
1037 ;
1038 if (*p == 0)
1039 goto err;
1040 *p++ = 0;
1041 for (; *p && isspace((unsigned char)*p); p++) /* (skip blanks) */
1042 ;
1043 if (*p == 0)
1044 goto err;
1045 *line = p; /* line no */
1046 for (*line = p; *p && !isspace((unsigned char)*p); p++)
1047 ;
1048 if (*p == 0)
1049 goto err;
1050 *p++ = 0;
1051 for (; *p && isspace((unsigned char)*p); p++) /* (skip blanks) */
1052 ;
1053 if (*p == 0)
1054 goto err;
1055 *file = p; /* file name */
1056 for (*file = p; *p && !isspace((unsigned char)*p); p++)
1057 ;
1058 if (*p == 0)
1059 goto err;
1060 *p = 0;
1061
1062 /* value check */
1063 if (strlen(*tag) && strlen(*line) && strlen(*file) && atoi(*line) > 0)
1064 return 1; /* OK */
1065 err:
1066 return 0; /* ERROR */
1067 }
1068
1069 /*
1070 * gtag_slist --
1071 * Search the list of tags files for a tag, and return tag queue.
1072 */
1073 static TAGQ *
gtag_slist(SCR * sp,CHAR_T * tag,int ref)1074 gtag_slist(SCR *sp, CHAR_T *tag, int ref)
1075 {
1076 TAGQ *tqp;
1077 size_t len, nlen, slen, wlen;
1078 TAG *tp;
1079 const char *np;
1080 char *name, *file, *search;
1081 char command[BUFSIZ];
1082 char buf[BUFSIZ];
1083 const CHAR_T *wp;
1084 FILE *fp;
1085
1086 /* Allocate and initialize the tag queue structure. */
1087 INT2CHAR(sp, tag, STRLEN(tag) + 1, np, nlen);
1088 len = nlen - 1;
1089 CALLOC_GOTO(sp, tqp, TAGQ *, 1, sizeof(TAGQ) + len + 1);
1090 TAILQ_INIT(&tqp->tagq);
1091 tqp->tag = tqp->buf;
1092 memcpy(tqp->tag, np, (tqp->tlen = len) + 1);
1093
1094 /*
1095 * Find the tag, only display missing file messages once, and
1096 * then only if we didn't find the tag.
1097 */
1098 snprintf(command, sizeof(command), "global -%s '%s'", ref ? "rx" : "x",
1099 np);
1100 if ((fp = popen(command, "r")) != NULL) {
1101 while (fgets(buf, sizeof(buf), fp)) {
1102 if (buf[strlen(buf)-1] == '\n') /* chop(buf) */
1103 buf[strlen(buf)-1] = 0;
1104 else
1105 while (fgetc(fp) != '\n')
1106 ;
1107 if (getentry(buf, &name, &file, &search) == 0) {
1108 break;
1109 }
1110 slen = strlen(search);
1111 CALLOC_GOTO(sp, tp,
1112 TAG *, 1, sizeof(TAG) + strlen(file) + 1 +
1113 (slen + 1) * sizeof(CHAR_T));
1114 tp->fname = (char *)tp->buf;
1115 strcpy(tp->fname, file);
1116 tp->fnlen = strlen(file);
1117 tp->search = (CHAR_T *)(tp->fname + tp->fnlen + 1);
1118 CHAR2INT(sp, search, slen + 1, wp, wlen);
1119 MEMCPYW(tp->search, wp, (tp->slen = slen) + 1);
1120 TAILQ_INSERT_TAIL(&tqp->tagq, tp, q);
1121 }
1122 pclose(fp);
1123 }
1124
1125 /* Check to see if we found anything. */
1126 if (TAILQ_EMPTY(&tqp->tagq)) {
1127 msgq_str(sp, M_ERR, np, "162|%s: tag not found");
1128 free(tqp);
1129 return (NULL);
1130 }
1131
1132 tqp->current = TAILQ_FIRST(&tqp->tagq);
1133 return (tqp);
1134
1135 alloc_err:
1136 free(tqp);
1137 return (NULL);
1138 }
1139 #endif
1140
1141 /*
1142 * ctag_slist --
1143 * Search the list of tags files for a tag, and return tag queue.
1144 */
1145 static TAGQ *
ctag_slist(SCR * sp,CHAR_T * tag)1146 ctag_slist(SCR *sp, CHAR_T *tag)
1147 {
1148 EX_PRIVATE *exp;
1149 TAGF *tfp;
1150 TAGQ *tqp;
1151 size_t len;
1152 int echk;
1153 const char *np;
1154 size_t nlen;
1155
1156 exp = EXP(sp);
1157
1158 /* Allocate and initialize the tag queue structure. */
1159 INT2CHAR(sp, tag, STRLEN(tag) + 1, np, nlen);
1160 len = nlen - 1;
1161 CALLOC_GOTO(sp, tqp, TAGQ *, 1, sizeof(TAGQ) + len + 1);
1162 TAILQ_INIT(&tqp->tagq);
1163 tqp->tag = tqp->buf;
1164 memcpy(tqp->tag, np, (tqp->tlen = len) + 1);
1165
1166 /*
1167 * Find the tag, only display missing file messages once, and
1168 * then only if we didn't find the tag.
1169 */
1170 echk = 0;
1171 TAILQ_FOREACH(tfp, &exp->tagfq, q)
1172 if (ctag_sfile(sp, tfp, tqp, tqp->tag)) {
1173 echk = 1;
1174 F_SET(tfp, TAGF_ERR);
1175 } else
1176 F_CLR(tfp, TAGF_ERR | TAGF_ERR_WARN);
1177
1178 /* Check to see if we found anything. */
1179 if (TAILQ_EMPTY(&tqp->tagq)) {
1180 msgq_str(sp, M_ERR, tqp->tag, "162|%s: tag not found");
1181 if (echk)
1182 TAILQ_FOREACH(tfp, &exp->tagfq, q)
1183 if (F_ISSET(tfp, TAGF_ERR) &&
1184 !F_ISSET(tfp, TAGF_ERR_WARN)) {
1185 errno = tfp->errnum;
1186 msgq_str(sp, M_SYSERR, tfp->name, "%s");
1187 F_SET(tfp, TAGF_ERR_WARN);
1188 }
1189 free(tqp);
1190 return (NULL);
1191 }
1192
1193 tqp->current = TAILQ_FIRST(&tqp->tagq);
1194 return (tqp);
1195
1196 alloc_err:
1197 return (NULL);
1198 }
1199
1200 /*
1201 * ctag_sfile --
1202 * Search a tags file for a tag, adding any found to the tag queue.
1203 */
1204 static int
ctag_sfile(SCR * sp,TAGF * tfp,TAGQ * tqp,char * tname)1205 ctag_sfile(SCR *sp, TAGF *tfp, TAGQ *tqp, char *tname)
1206 {
1207 struct stat sb;
1208 TAG *tp;
1209 size_t dlen, nlen = 0, slen;
1210 int fd, i, nf1, nf2;
1211 char *back, *front, *map, *p, *search, *t;
1212 char *cname = NULL, *dname = NULL, *name = NULL;
1213 const CHAR_T *wp;
1214 size_t wlen;
1215 unsigned long tl;
1216
1217 if ((fd = open(tfp->name, O_RDONLY, 0)) < 0) {
1218 tfp->errnum = errno;
1219 return (1);
1220 }
1221
1222 /*
1223 * XXX
1224 * Some old BSD systems require MAP_FILE as an argument when mapping
1225 * regular files.
1226 */
1227 #ifndef MAP_FILE
1228 #define MAP_FILE 0
1229 #endif
1230 /*
1231 * XXX
1232 * We'd like to test if the file is too big to mmap. Since we don't
1233 * know what size or type off_t's or size_t's are, what the largest
1234 * unsigned integral type is, or what random insanity the local C
1235 * compiler will perpetrate, doing the comparison in a portable way
1236 * is flatly impossible. Hope mmap fails if the file is too large.
1237 */
1238 if (fstat(fd, &sb) != 0 ||
1239 (map = mmap(NULL, (size_t)sb.st_size, PROT_READ | PROT_WRITE,
1240 MAP_FILE | MAP_PRIVATE, fd, (off_t)0)) == (caddr_t)-1) {
1241 tfp->errnum = errno;
1242 (void)close(fd);
1243 return (1);
1244 }
1245
1246 tl = O_VAL(sp, O_TAGLENGTH);
1247 front = map;
1248 back = front + sb.st_size;
1249 front = binary_search(tname, front, back);
1250 front = linear_search(tname, front, back, tl);
1251 if (front == NULL)
1252 goto done;
1253
1254 /*
1255 * Initialize and link in the tag structure(s). The historic ctags
1256 * file format only permitted a single tag location per tag. The
1257 * obvious extension to permit multiple tags locations per tag is to
1258 * output multiple records in the standard format. Unfortunately,
1259 * this won't work correctly with historic ex/vi implementations,
1260 * because their binary search assumes that there's only one record
1261 * per tag, and so will use a random tag entry if there si more than
1262 * one. This code handles either format.
1263 *
1264 * The tags file is in the following format:
1265 *
1266 * <tag> <filename> <line number> | <pattern>
1267 *
1268 * Figure out how long everything is so we can allocate in one swell
1269 * foop, but discard anything that looks wrong.
1270 */
1271 for (;;) {
1272 /* Nul-terminate the end of the line. */
1273 for (p = front; p < back && *p != '\n'; ++p);
1274 if (p == back || *p != '\n')
1275 break;
1276 *p = '\0';
1277
1278 /* Update the pointers for the next time. */
1279 t = p + 1;
1280 p = front;
1281 front = t;
1282
1283 /* Break the line into tokens. */
1284 for (i = 0; i < 2 && (t = strsep(&p, "\t ")) != NULL; ++i)
1285 switch (i) {
1286 case 0: /* Tag. */
1287 cname = t;
1288 break;
1289 case 1: /* Filename. */
1290 name = t;
1291 nlen = strlen(name);
1292 break;
1293 }
1294
1295 /* Check for corruption. */
1296 if (i != 2 || p == NULL || t == NULL)
1297 goto corrupt;
1298
1299 /* The rest of the string is the search pattern. */
1300 search = p;
1301 if ((slen = strlen(p)) == 0) {
1302 corrupt: p = msg_print(sp, tname, &nf1);
1303 t = msg_print(sp, tfp->name, &nf2);
1304 msgq(sp, M_ERR, "163|%s: corrupted tag in %s", p, t);
1305 if (nf1)
1306 FREE_SPACE(sp, p, 0);
1307 if (nf2)
1308 FREE_SPACE(sp, t, 0);
1309 continue;
1310 }
1311
1312 /* Check for passing the last entry. */
1313 if (tl ? strncmp(tname, cname, tl) : strcmp(tname, cname))
1314 break;
1315
1316 /* Resolve the file name. */
1317 ctag_file(sp, tfp, name, &dname, &dlen);
1318
1319 CALLOC_GOTO(sp, tp,
1320 TAG *, 1, sizeof(TAG) + dlen + 2 + nlen + 1 +
1321 (slen + 1) * sizeof(CHAR_T));
1322 tp->fname = (char *)tp->buf;
1323 if (dlen != 0) {
1324 memcpy(tp->fname, dname, dlen);
1325 tp->fname[dlen] = '/';
1326 ++dlen;
1327 }
1328 memcpy(tp->fname + dlen, name, nlen + 1);
1329 tp->fnlen = dlen + nlen;
1330 tp->search = (CHAR_T*)(tp->fname + tp->fnlen + 1);
1331 CHAR2INT(sp, search, slen + 1, wp, wlen);
1332 MEMCPYW(tp->search, wp, (tp->slen = slen) + 1);
1333 TAILQ_INSERT_TAIL(&tqp->tagq, tp, q);
1334 }
1335
1336 alloc_err:
1337 done: if (munmap(map, (size_t)sb.st_size))
1338 msgq(sp, M_SYSERR, "munmap");
1339 if (close(fd))
1340 msgq(sp, M_SYSERR, "close");
1341 return (0);
1342 }
1343
1344 /*
1345 * ctag_file --
1346 * Search for the right path to this file.
1347 */
1348 static void
ctag_file(SCR * sp,TAGF * tfp,char * name,char ** dirp,size_t * dlenp)1349 ctag_file(SCR *sp, TAGF *tfp, char *name, char **dirp, size_t *dlenp)
1350 {
1351 struct stat sb;
1352 char *p, buf[MAXPATHLEN];
1353
1354 /*
1355 * !!!
1356 * If the tag file path is a relative path, see if it exists. If it
1357 * doesn't, look relative to the tags file path. It's okay for a tag
1358 * file to not exist, and historically, vi simply displayed a "new"
1359 * file. However, if the path exists relative to the tag file, it's
1360 * pretty clear what's happening, so we may as well get it right.
1361 */
1362 *dlenp = 0;
1363 if (name[0] != '/' &&
1364 stat(name, &sb) && (p = strrchr(tfp->name, '/')) != NULL) {
1365 *p = '\0';
1366 (void)snprintf(buf, sizeof(buf), "%s/%s", tfp->name, name);
1367 if (stat(buf, &sb) == 0) {
1368 *dirp = tfp->name;
1369 *dlenp = strlen(*dirp);
1370 }
1371 *p = '/';
1372 }
1373 }
1374
1375 /*
1376 * Binary search for "string" in memory between "front" and "back".
1377 *
1378 * This routine is expected to return a pointer to the start of a line at
1379 * *or before* the first word matching "string". Relaxing the constraint
1380 * this way simplifies the algorithm.
1381 *
1382 * Invariants:
1383 * front points to the beginning of a line at or before the first
1384 * matching string.
1385 *
1386 * back points to the beginning of a line at or after the first
1387 * matching line.
1388 *
1389 * Base of the Invariants.
1390 * front = NULL;
1391 * back = EOF;
1392 *
1393 * Advancing the Invariants:
1394 *
1395 * p = first newline after halfway point from front to back.
1396 *
1397 * If the string at "p" is not greater than the string to match,
1398 * p is the new front. Otherwise it is the new back.
1399 *
1400 * Termination:
1401 *
1402 * The definition of the routine allows it return at any point,
1403 * since front is always at or before the line to print.
1404 *
1405 * In fact, it returns when the chosen "p" equals "back". This
1406 * implies that there exists a string is least half as long as
1407 * (back - front), which in turn implies that a linear search will
1408 * be no more expensive than the cost of simply printing a string or two.
1409 *
1410 * Trying to continue with binary search at this point would be
1411 * more trouble than it's worth.
1412 */
1413 #define EQUAL 0
1414 #define GREATER 1
1415 #define LESS (-1)
1416
1417 #define SKIP_PAST_NEWLINE(p, back) while (p < back && *p++ != '\n') continue;
1418
1419 static char *
binary_search(register char * string,register char * front,register char * back)1420 binary_search(register char *string, register char *front, register char *back)
1421 {
1422 register char *p;
1423
1424 p = front + (back - front) / 2;
1425 SKIP_PAST_NEWLINE(p, back);
1426
1427 while (p != back) {
1428 if (compare(string, p, back) == GREATER)
1429 front = p;
1430 else
1431 back = p;
1432 p = front + (back - front) / 2;
1433 SKIP_PAST_NEWLINE(p, back);
1434 }
1435 return (front);
1436 }
1437
1438 /*
1439 * Find the first line that starts with string, linearly searching from front
1440 * to back.
1441 *
1442 * Return NULL for no such line.
1443 *
1444 * This routine assumes:
1445 *
1446 * o front points at the first character in a line.
1447 * o front is before or at the first line to be printed.
1448 */
1449 static char *
linear_search(char * string,char * front,char * back,unsigned long tl)1450 linear_search(char *string, char *front, char *back, unsigned long tl)
1451 {
1452 char *end;
1453 while (front < back) {
1454 end = tl && (unsigned long)(back-front) > tl ? front+tl : back;
1455 switch (compare(string, front, end)) {
1456 case EQUAL: /* Found it. */
1457 return (front);
1458 case LESS: /* No such string. */
1459 return (NULL);
1460 case GREATER: /* Keep going. */
1461 break;
1462 }
1463 SKIP_PAST_NEWLINE(front, back);
1464 }
1465 return (NULL);
1466 }
1467
1468 /*
1469 * Return LESS, GREATER, or EQUAL depending on how the string1 compares
1470 * with string2 (s1 ??? s2).
1471 *
1472 * o Matches up to len(s1) are EQUAL.
1473 * o Matches up to len(s2) are GREATER.
1474 *
1475 * The string "s1" is null terminated. The string s2 is '\t', space, (or
1476 * "back") terminated.
1477 *
1478 * !!!
1479 * Reasonably modern ctags programs use tabs as separators, not spaces.
1480 * However, historic programs did use spaces, and, I got complaints.
1481 */
1482 static int
compare(register char * s1,register char * s2,register char * back)1483 compare(register char *s1, register char *s2, register char *back)
1484 {
1485 for (; *s1 && s2 < back && (*s2 != '\t' && *s2 != ' '); ++s1, ++s2)
1486 if (*s1 != *s2)
1487 return (*s1 < *s2 ? LESS : GREATER);
1488 return (*s1 ? GREATER : s2 < back &&
1489 (*s2 != '\t' && *s2 != ' ') ? LESS : EQUAL);
1490 }
1491