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.
7 * This code is derived from software contributed to Berkeley by
8 * David Hitz of Auspex Systems, Inc.
10 * See the LICENSE file for redistribution information.
16 static const char sccsid[] = "$Id: ex_tag.c,v 10.54 2012/04/12 07:17:30 zy Exp $";
19 #include <sys/types.h>
21 #include <sys/queue.h>
24 #include <bitstring.h>
35 #include "../common/common.h"
39 static char *binary_search(char *, char *, char *);
40 static int compare(char *, char *, char *);
41 static void ctag_file(SCR *, TAGF *, char *, char **, size_t *);
42 static int ctag_search(SCR *, CHAR_T *, size_t, char *);
43 static int ctag_sfile(SCR *, TAGF *, TAGQ *, char *);
44 static TAGQ *ctag_slist(SCR *, CHAR_T *);
45 static char *linear_search(char *, char *, char *, long);
46 static int tag_copy(SCR *, TAG *, TAG **);
47 static int tag_pop(SCR *, TAGQ *, int);
48 static int tagf_copy(SCR *, TAGF *, TAGF **);
49 static int tagf_free(SCR *, TAGF *);
50 static int tagq_copy(SCR *, TAGQ *, TAGQ **);
54 * The tag code can be entered from main, e.g., "vi -t tag".
56 * PUBLIC: int ex_tag_first(SCR *, CHAR_T *);
59 ex_tag_first(SCR *sp, CHAR_T *tagarg)
63 /* Build an argument for the ex :tag command. */
64 ex_cinit(sp, &cmd, C_TAG, 0, OOBLNO, OOBLNO, 0);
65 argv_exp0(sp, &cmd, tagarg, STRLEN(tagarg));
69 * Historic vi went ahead and created a temporary file when it failed
70 * to find the tag. We match historic practice, but don't distinguish
71 * between real error and failure to find the tag.
73 if (ex_tag_push(sp, &cmd))
76 /* Display tags in the center of the screen. */
77 F_CLR(sp, SC_SCR_TOP);
78 F_SET(sp, SC_SCR_CENTER);
87 * Enter a new TAGQ context based on a ctag string.
89 * PUBLIC: int ex_tag_push(SCR *, EXCMD *);
92 ex_tag_push(SCR *sp, EXCMD *cmdp)
101 if (exp->tag_last != NULL)
104 if ((exp->tag_last = v_wstrdup(sp, cmdp->argv[0]->bp,
105 cmdp->argv[0]->len)) == NULL) {
106 msgq(sp, M_SYSERR, NULL);
110 /* Taglength may limit the number of characters. */
112 O_VAL(sp, O_TAGLENGTH)) != 0 && STRLEN(exp->tag_last) > tl)
113 exp->tag_last[tl] = '\0';
116 if (exp->tag_last == NULL) {
117 msgq(sp, M_ERR, "158|No previous tag entered");
125 /* Get the tag information. */
126 if ((tqp = ctag_slist(sp, exp->tag_last)) == NULL)
129 if (tagq_push(sp, tqp, F_ISSET(cmdp, E_NEWSCREEN),
130 FL_ISSET(cmdp->iflags, E_C_FORCE)))
138 * Switch context to the next TAG.
140 * PUBLIC: int ex_tag_next(SCR *, EXCMD *);
143 ex_tag_next(SCR *sp, EXCMD *cmdp)
152 if ((tqp = TAILQ_FIRST(exp->tq)) == NULL) {
153 tag_msg(sp, TAG_EMPTY, NULL);
156 if ((tp = TAILQ_NEXT(tqp->current, q)) == NULL) {
157 msgq(sp, M_ERR, "282|Already at the last tag of this group");
160 if (ex_tag_nswitch(sp, tp, FL_ISSET(cmdp->iflags, E_C_FORCE)))
164 if (F_ISSET(tqp, TAG_CSCOPE))
165 (void)cscope_search(sp, tqp, tp);
167 (void)ctag_search(sp, tp->search, tp->slen, tqp->tag);
168 if (tqp->current->msg) {
169 INT2CHAR(sp, tqp->current->msg, tqp->current->mlen + 1,
171 msgq(sp, M_INFO, "%s", np);
178 * Switch context to the next TAG.
180 * PUBLIC: int ex_tag_prev(SCR *, EXCMD *);
183 ex_tag_prev(SCR *sp, EXCMD *cmdp)
192 if ((tqp = TAILQ_FIRST(exp->tq)) == NULL) {
193 tag_msg(sp, TAG_EMPTY, NULL);
196 if ((tp = TAILQ_PREV(tqp->current, _tagqh, q)) == NULL) {
197 msgq(sp, M_ERR, "255|Already at the first tag of this group");
200 if (ex_tag_nswitch(sp, tp, FL_ISSET(cmdp->iflags, E_C_FORCE)))
204 if (F_ISSET(tqp, TAG_CSCOPE))
205 (void)cscope_search(sp, tqp, tp);
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,
211 msgq(sp, M_INFO, "%s", np);
218 * Switch context to the specified TAG.
220 * PUBLIC: int ex_tag_nswitch(SCR *, TAG *, int);
223 ex_tag_nswitch(SCR *sp, TAG *tp, int force)
225 /* Get a file structure. */
226 if (tp->frp == NULL && (tp->frp = file_add(sp, tp->fname)) == NULL)
229 /* If not changing files, return, we're done. */
230 if (tp->frp == sp->frp)
233 /* Check for permission to leave. */
234 if (file_m1(sp, force, FS_ALL | FS_POSSIBLE))
237 /* Initialize the new file. */
238 if (file_init(sp, tp->frp, NULL, FS_SETALT))
241 /* Display tags in the center of the screen. */
242 F_CLR(sp, SC_SCR_TOP);
243 F_SET(sp, SC_SCR_CENTER);
246 F_SET(sp, SC_FSWITCH);
252 * Switch context to the specified TAG in a new screen.
254 * PUBLIC: int ex_tag_Nswitch(SCR *, TAG *, int);
257 ex_tag_Nswitch(SCR *sp, TAG *tp, int force)
261 /* Get a file structure. */
262 if (tp->frp == NULL && (tp->frp = file_add(sp, tp->fname)) == NULL)
265 /* Get a new screen. */
266 if (screen_init(sp->gp, sp, &new))
268 if (vs_split(sp, new, 0)) {
269 (void)file_end(new, new->ep, 1);
270 (void)screen_end(new);
274 /* Get a backing file. */
275 if (tp->frp == sp->frp) {
276 /* Copy file state. */
281 new->frp->flags = sp->frp->flags;
282 } else if (file_init(new, tp->frp, NULL, force)) {
283 (void)vs_discard(new, NULL);
284 (void)screen_end(new);
288 /* Create the argument list. */
289 new->cargv = new->argv = ex_buildargv(sp, NULL, tp->frp->name);
291 /* Display tags in the center of the screen. */
292 F_CLR(new, SC_SCR_TOP);
293 F_SET(new, SC_SCR_CENTER);
297 F_SET(sp, SC_SSWITCH);
304 * :tagp[op][!] [number | file]
306 * Pop to a previous TAGQ context.
308 * PUBLIC: int ex_tag_pop(SCR *, EXCMD *);
311 ex_tag_pop(SCR *sp, EXCMD *cmdp)
320 /* Check for an empty stack. */
322 if (TAILQ_EMPTY(exp->tq)) {
323 tag_msg(sp, TAG_EMPTY, NULL);
327 /* Find the last TAG structure that we're going to DISCARD! */
328 switch (cmdp->argc) {
329 case 0: /* Pop one tag. */
330 dtqp = TAILQ_FIRST(exp->tq);
332 case 1: /* Name or number. */
333 INT2CHAR(sp, cmdp->argv[0]->bp, cmdp->argv[0]->len+1,
335 off = strtol(arg, &p, 10);
339 /* Number: pop that many queue entries. */
342 TAILQ_FOREACH(tqp, exp->tq, q)
343 if (--off <= 1) break;
346 "159|Less than %s entries on the tags stack; use :display t[ags]",
353 /* File argument: pop to that queue entry. */
354 filearg: arglen = strlen(arg);
355 for (tqp = TAILQ_FIRST(exp->tq); tqp;
356 dtqp = tqp, tqp = TAILQ_NEXT(tqp, q)) {
357 /* Don't pop to the current file. */
358 if (tqp == TAILQ_FIRST(exp->tq))
360 p = tqp->current->frp->name;
361 if ((t = strrchr(p, '/')) == NULL)
365 if (!strncmp(arg, t, arglen))
369 msgq_str(sp, M_ERR, arg,
370 "160|No file %s on the tags stack to return to; use :display t[ags]");
373 if (tqp == TAILQ_FIRST(exp->tq))
380 return (tag_pop(sp, dtqp, FL_ISSET(cmdp->iflags, E_C_FORCE)));
384 * ex_tag_top -- :tagt[op][!]
385 * Clear the tag stack.
387 * PUBLIC: int ex_tag_top(SCR *, EXCMD *);
390 ex_tag_top(SCR *sp, EXCMD *cmdp)
396 /* Check for an empty stack. */
397 if (TAILQ_EMPTY(exp->tq)) {
398 tag_msg(sp, TAG_EMPTY, NULL);
402 /* Return to the oldest information. */
403 return (tag_pop(sp, TAILQ_PREV(TAILQ_LAST(exp->tq, _tqh), _tqh, q),
404 FL_ISSET(cmdp->iflags, E_C_FORCE)));
409 * Pop up to and including the specified TAGQ context.
412 tag_pop(SCR *sp, TAGQ *dtqp, int force)
421 * Update the cursor from the saved TAG information of the TAG
422 * structure we're moving to.
424 tp = TAILQ_NEXT(dtqp, q)->current;
425 if (tp->frp == sp->frp) {
429 if (file_m1(sp, force, FS_ALL | FS_POSSIBLE))
432 tp->frp->lno = tp->lno;
433 tp->frp->cno = tp->cno;
434 F_SET(sp->frp, FR_CURSORSET);
435 if (file_init(sp, tp->frp, NULL, FS_SETALT))
438 F_SET(sp, SC_FSWITCH);
441 /* Pop entries off the queue up to and including dtqp. */
443 tqp = TAILQ_FIRST(exp->tq);
444 if (tagq_free(sp, tqp))
446 } while (tqp != dtqp);
449 * If only a single tag left, we've returned to the first tag point,
450 * and the stack is now empty.
452 if (TAILQ_NEXT(TAILQ_FIRST(exp->tq), q) == NULL)
453 tagq_free(sp, TAILQ_FIRST(exp->tq));
460 * Display the list of tags.
462 * PUBLIC: int ex_tag_display(SCR *);
465 ex_tag_display(SCR *sp)
475 if (TAILQ_EMPTY(exp->tq)) {
476 tag_msg(sp, TAG_EMPTY, NULL);
481 * We give the file name 20 columns and the search string the rest.
482 * If there's not enough room, we don't do anything special, it's
483 * not worth the effort, it just makes the display more confusing.
485 * We also assume that characters in file names map 1-1 to printing
486 * characters. This might not be true, but I don't think it's worth
487 * fixing. (The obvious fix is to pass the filenames through the
488 * msg_print function.)
490 #define L_NAME 30 /* Name. */
491 #define L_SLOP 4 /* Leading number plus trailing *. */
492 #define L_SPACE 5 /* Spaces after name, before tag. */
493 #define L_TAG 20 /* Tag. */
494 if (sp->cols <= L_NAME + L_SLOP) {
495 msgq(sp, M_ERR, "292|Display too small.");
500 * Display the list of tags for each queue entry. The first entry
501 * is numbered, and the current tag entry has an asterisk appended.
503 for (cnt = 1, tqp = TAILQ_FIRST(exp->tq); !INTERRUPTED(sp) &&
504 tqp != NULL; ++cnt, tqp = TAILQ_NEXT(tqp, q))
505 TAILQ_FOREACH(tp, tqp->tagq, q) {
506 if (tp == TAILQ_FIRST(tqp->tagq))
507 (void)ex_printf(sp, "%2d ", cnt);
509 (void)ex_printf(sp, " ");
510 p = tp->frp == NULL ? tp->fname : tp->frp->name;
511 if ((len = strlen(p)) > L_NAME) {
512 len = len - (L_NAME - 4);
513 (void)ex_printf(sp, " ... %*.*s",
514 L_NAME - 4, L_NAME - 4, p + len);
517 " %*.*s", L_NAME, L_NAME, p);
518 if (tqp->current == tp)
519 (void)ex_printf(sp, "*");
521 if (tp == TAILQ_FIRST(tqp->tagq) && tqp->tag != NULL &&
522 (sp->cols - L_NAME) >= L_TAG + L_SPACE) {
523 len = strlen(tqp->tag);
524 if (len > sp->cols - (L_NAME + L_SPACE))
525 len = sp->cols - (L_NAME + L_SPACE);
526 (void)ex_printf(sp, "%s%.*s",
527 tqp->current == tp ? " " : " ",
530 (void)ex_printf(sp, "\n");
537 * Copy a screen's tag structures.
539 * PUBLIC: int ex_tag_copy(SCR *, SCR *);
542 ex_tag_copy(SCR *orig, SCR *sp)
544 EX_PRIVATE *oexp, *nexp;
552 /* Copy tag queue and tags stack. */
553 TAILQ_FOREACH(aqp, oexp->tq, q) {
554 if (tagq_copy(sp, aqp, &tqp))
556 TAILQ_FOREACH(ap, aqp->tagq, q) {
557 if (tag_copy(sp, ap, &tp))
559 /* Set the current pointer. */
560 if (aqp->current == ap)
562 TAILQ_INSERT_TAIL(tqp->tagq, tp, q);
564 TAILQ_INSERT_TAIL(nexp->tq, tqp, q);
567 /* Copy list of tag files. */
568 TAILQ_FOREACH(atfp, oexp->tagfq, q) {
569 if (tagf_copy(sp, atfp, &tfp))
571 TAILQ_INSERT_TAIL(nexp->tagfq, tfp, q);
574 /* Copy the last tag. */
575 if (oexp->tag_last != NULL &&
576 (nexp->tag_last = v_wstrdup(sp, oexp->tag_last,
577 STRLEN(oexp->tag_last))) == NULL) {
578 msgq(sp, M_SYSERR, NULL);
586 * Copy a TAGF structure and return it in new memory.
589 tagf_copy(SCR *sp, TAGF *otfp, TAGF **tfpp)
593 MALLOC_RET(sp, tfp, TAGF *, sizeof(TAGF));
596 /* XXX: Allocate as part of the TAGF structure!!! */
597 if ((tfp->name = strdup(otfp->name)) == NULL)
606 * Copy a TAGQ structure and return it in new memory.
609 tagq_copy(SCR *sp, TAGQ *otqp, TAGQ **tqpp)
615 if (otqp->tag != NULL)
616 len += otqp->tlen + 1;
617 MALLOC_RET(sp, tqp, TAGQ *, len);
618 memcpy(tqp, otqp, len);
620 TAILQ_INIT(tqp->tagq);
622 if (otqp->tag != NULL)
631 * Copy a TAG structure and return it in new memory.
634 tag_copy(SCR *sp, TAG *otp, TAG **tpp)
640 if (otp->fname != NULL)
641 len += otp->fnlen + 1;
642 if (otp->search != NULL)
643 len += otp->slen + 1;
644 if (otp->msg != NULL)
645 len += otp->mlen + 1;
646 MALLOC_RET(sp, tp, TAG *, len);
647 memcpy(tp, otp, len);
649 if (otp->fname != NULL)
650 tp->fname = (char *)tp->buf;
651 if (otp->search != NULL)
652 tp->search = tp->buf + (otp->search - otp->buf);
653 if (otp->msg != NULL)
654 tp->msg = tp->buf + (otp->msg - otp->buf);
662 * Free a TAGF structure.
665 tagf_free(SCR *sp, TAGF *tfp)
670 TAILQ_REMOVE(exp->tagfq, tfp, q);
678 * Free a TAGQ structure (and associated TAG structures).
680 * PUBLIC: int tagq_free(SCR *, TAGQ *);
683 tagq_free(SCR *sp, TAGQ *tqp)
689 while ((tp = TAILQ_FIRST(tqp->tagq)) != NULL) {
690 TAILQ_REMOVE(tqp->tagq, tp, q);
695 * If allocated and then the user failed to switch files, the TAGQ
696 * structure was never attached to any list.
698 if (TAILQ_ENTRY_ISVALID(tqp, q))
699 TAILQ_REMOVE(exp->tq, tqp, q);
705 * PUBLIC: int tagq_push(SCR*, TAGQ*, int, int );
708 tagq_push(SCR *sp, TAGQ *tqp, int new_screen, int force)
723 * Allocate all necessary memory before swapping screens. Initialize
724 * flags so we know what to free.
728 if (TAILQ_EMPTY(exp->tq)) {
729 /* Initialize the `local context' tag queue structure. */
730 CALLOC_GOTO(sp, rtqp, TAGQ *, 1, sizeof(TAGQ));
731 TAILQ_INIT(rtqp->tagq);
733 /* Initialize and link in its tag structure. */
734 CALLOC_GOTO(sp, rtp, TAG *, 1, sizeof(TAG));
735 TAILQ_INSERT_HEAD(rtqp->tagq, rtp, q);
740 * Stick the current context information in a convenient place, we're
741 * about to lose it. Note, if we're called on editor startup, there
742 * will be no FREF structure.
747 istmp = frp == NULL ||
748 (F_ISSET(frp, FR_TMPFILE) && !new_screen);
750 /* Try to switch to the preset tag. */
752 if (ex_tag_Nswitch(sp, tqp->current, force))
755 /* Everything else gets done in the new screen. */
759 if (ex_tag_nswitch(sp, tqp->current, force))
763 * If this is the first tag, put a `current location' queue entry
764 * in place, so we can pop all the way back to the current mark.
765 * Note, it doesn't point to much of anything, it's a placeholder.
767 if (TAILQ_EMPTY(exp->tq)) {
768 TAILQ_INSERT_HEAD(exp->tq, rtqp, q);
770 rtqp = TAILQ_FIRST(exp->tq);
772 /* Link the new TAGQ structure into place. */
773 TAILQ_INSERT_HEAD(exp->tq, tqp, q);
775 (void)ctag_search(sp,
776 tqp->current->search, tqp->current->slen, tqp->tag);
777 if (tqp->current->msg) {
778 INT2CHAR(sp, tqp->current->msg, tqp->current->mlen + 1,
780 msgq(sp, M_INFO, "%s", np);
784 * Move the current context from the temporary save area into the
787 * If we were in a temporary file, we don't have a context to which
788 * we can return, so just make it be the same as what we're moving
789 * to. It will be a little odd that ^T doesn't change anything, but
790 * I don't think it's a big deal.
793 rtqp->current->frp = sp->frp;
794 rtqp->current->lno = sp->lno;
795 rtqp->current->cno = sp->cno;
797 rtqp->current->frp = frp;
798 rtqp->current->lno = lno;
799 rtqp->current->cno = cno;
815 * A few common messages.
817 * PUBLIC: void tag_msg(SCR *, tagmsg_t, char *);
820 tag_msg(SCR *sp, tagmsg_t msg, char *tag)
824 msgq_str(sp, M_ERR, tag,
825 "164|%s: the tag's line number is past the end of the file");
828 msgq(sp, M_INFO, "165|The tags stack is empty");
831 msgq_str(sp, M_ERR, tag, "166|%s: search pattern not found");
840 * Create a new list of ctag files.
842 * PUBLIC: int ex_tagf_alloc(SCR *, char *);
845 ex_tagf_alloc(SCR *sp, char *str)
852 /* Free current queue. */
854 while ((tfp = TAILQ_FIRST(exp->tagfq)) != NULL)
857 /* Create new queue. */
858 for (p = t = str;; ++p) {
859 if (*p == '\0' || cmdskip(*p)) {
861 MALLOC_RET(sp, tfp, TAGF *, sizeof(TAGF));
862 MALLOC(sp, tfp->name, char *, len + 1);
863 if (tfp->name == NULL) {
867 memcpy(tfp->name, t, len);
868 tfp->name[len] = '\0';
870 TAILQ_INSERT_TAIL(exp->tagfq, tfp, q);
879 /* Free previous queue. */
882 * Free the ex tag information.
884 * PUBLIC: int ex_tag_free(SCR *);
893 /* Free up tag information. */
895 while ((tqp = TAILQ_FIRST(exp->tq)) != NULL)
897 while ((tfp = TAILQ_FIRST(exp->tagfq)) != NULL)
899 if (exp->tag_last != NULL)
906 * Search a file for a tag.
909 ctag_search(SCR *sp, CHAR_T *search, size_t slen, char *tag)
918 * The historic tags file format (from a long, long time ago...)
919 * used a line number, not a search string. I got complaints, so
920 * people are still using the format. POSIX 1003.2 permits it.
922 if (ISDIGIT(search[0])) {
923 INT2CHAR(sp, search, slen+1, np, nlen);
925 if (!db_exist(sp, m.lno)) {
926 tag_msg(sp, TAG_BADLNO, tag);
931 * Search for the tag; cheap fallback for C functions
932 * if the name is the same but the arguments have changed.
936 if (f_search(sp, &m, &m,
937 search, slen, NULL, SEARCH_FILE | SEARCH_TAG)) {
938 INT2CHAR(sp, search, slen, np, nlen);
939 if ((p = strrchr(np, '(')) != NULL) {
941 if (f_search(sp, &m, &m, search, slen,
942 NULL, SEARCH_FILE | SEARCH_TAG))
945 notfound: tag_msg(sp, TAG_SEARCH, tag);
951 * Historically, tags set the search direction if it wasn't
954 if (sp->searchdir == NOTSET)
955 sp->searchdir = FORWARD;
960 * Tags move to the first non-blank, NOT the search pattern start.
964 (void)nonblank(sp, sp->lno, &sp->cno);
970 * Search the list of tags files for a tag, and return tag queue.
973 ctag_slist(SCR *sp, CHAR_T *tag)
985 /* Allocate and initialize the tag queue structure. */
986 INT2CHAR(sp, tag, STRLEN(tag) + 1, np, nlen);
988 CALLOC_GOTO(sp, tqp, TAGQ *, 1, sizeof(TAGQ) + len + 1);
989 TAILQ_INIT(tqp->tagq);
991 memcpy(tqp->tag, np, (tqp->tlen = len) + 1);
994 * Find the tag, only display missing file messages once, and
995 * then only if we didn't find the tag.
997 TAILQ_FOREACH(tfp, exp->tagfq, q)
998 if (ctag_sfile(sp, tfp, tqp, tqp->tag)) {
1000 F_SET(tfp, TAGF_ERR);
1002 F_CLR(tfp, TAGF_ERR | TAGF_ERR_WARN);
1004 /* Check to see if we found anything. */
1005 if (TAILQ_EMPTY(tqp->tagq)) {
1006 msgq_str(sp, M_ERR, tqp->tag, "162|%s: tag not found");
1008 TAILQ_FOREACH(tfp, exp->tagfq, q)
1009 if (F_ISSET(tfp, TAGF_ERR) &&
1010 !F_ISSET(tfp, TAGF_ERR_WARN)) {
1011 errno = tfp->errnum;
1012 msgq_str(sp, M_SYSERR, tfp->name, "%s");
1013 F_SET(tfp, TAGF_ERR_WARN);
1027 * Search a tags file for a tag, adding any found to the tag queue.
1030 ctag_sfile(SCR *sp, TAGF *tfp, TAGQ *tqp, char *tname)
1034 size_t dlen, nlen = 0, slen;
1035 int fd, i, nf1, nf2;
1036 char *back, *front, *map, *p, *search, *t;
1037 char *cname = NULL, *dname = NULL, *name = NULL;
1042 if ((fd = open(tfp->name, O_RDONLY, 0)) < 0) {
1043 tfp->errnum = errno;
1047 if (fstat(fd, &sb) != 0 ||
1048 (map = mmap(NULL, sb.st_size, PROT_READ | PROT_WRITE,
1049 MAP_PRIVATE, fd, 0)) == MAP_FAILED) {
1050 tfp->errnum = errno;
1055 tl = O_VAL(sp, O_TAGLENGTH);
1057 back = front + sb.st_size;
1058 front = binary_search(tname, front, back);
1059 front = linear_search(tname, front, back, tl);
1064 * Initialize and link in the tag structure(s). The historic ctags
1065 * file format only permitted a single tag location per tag. The
1066 * obvious extension to permit multiple tags locations per tag is to
1067 * output multiple records in the standard format. Unfortunately,
1068 * this won't work correctly with historic ex/vi implementations,
1069 * because their binary search assumes that there's only one record
1070 * per tag, and so will use a random tag entry if there si more than
1071 * one. This code handles either format.
1073 * The tags file is in the following format:
1075 * <tag> <filename> <line number> | <pattern>
1077 * Figure out how long everything is so we can allocate in one swell
1078 * foop, but discard anything that looks wrong.
1081 /* Nul-terminate the end of the line. */
1082 for (p = front; p < back && *p != '\n'; ++p);
1083 if (p == back || *p != '\n')
1087 /* Update the pointers for the next time. */
1092 /* Break the line into tokens. */
1093 for (i = 0; i < 2 && (t = strsep(&p, "\t ")) != NULL; ++i)
1098 case 1: /* Filename. */
1100 nlen = strlen(name);
1104 /* Check for corruption. */
1105 if (i != 2 || p == NULL || t == NULL)
1108 /* The rest of the string is the search pattern. */
1110 if ((slen = strlen(p)) == 0) {
1111 corrupt: p = msg_print(sp, tname, &nf1);
1112 t = msg_print(sp, tfp->name, &nf2);
1113 msgq(sp, M_ERR, "163|%s: corrupted tag in %s", p, t);
1115 FREE_SPACE(sp, p, 0);
1117 FREE_SPACE(sp, t, 0);
1121 /* Check for passing the last entry. */
1122 if (tl ? strncmp(tname, cname, tl) : strcmp(tname, cname))
1125 /* Resolve the file name. */
1126 ctag_file(sp, tfp, name, &dname, &dlen);
1129 TAG *, 1, sizeof(TAG) + dlen + 2 + nlen + 1 +
1130 (slen + 1) * sizeof(CHAR_T));
1131 tp->fname = (char *)tp->buf;
1132 if (dlen == 1 && *dname == '.')
1134 else if (dlen != 0) {
1135 memcpy(tp->fname, dname, dlen);
1136 tp->fname[dlen] = '/';
1139 memcpy(tp->fname + dlen, name, nlen + 1);
1140 tp->fnlen = dlen + nlen;
1141 tp->search = (CHAR_T*)(tp->fname + tp->fnlen + 1);
1142 CHAR2INT(sp, search, slen + 1, wp, wlen);
1143 MEMCPY(tp->search, wp, (tp->slen = slen) + 1);
1144 TAILQ_INSERT_TAIL(tqp->tagq, tp, q);
1146 /* Try to preset the tag within the current file. */
1147 if (sp->frp != NULL && sp->frp->name != NULL &&
1148 tqp->current == NULL && !strcmp(tp->fname, sp->frp->name))
1152 if (tqp->current == NULL)
1153 tqp->current = TAILQ_FIRST(tqp->tagq);
1156 done: if (munmap(map, sb.st_size))
1157 msgq(sp, M_SYSERR, "munmap");
1159 msgq(sp, M_SYSERR, "close");
1165 * Search for the right path to this file.
1168 ctag_file(SCR *sp, TAGF *tfp, char *name, char **dirp, size_t *dlenp)
1175 * If the tag file path is a relative path, see if it exists. If it
1176 * doesn't, look relative to the tags file path. It's okay for a tag
1177 * file to not exist, and historically, vi simply displayed a "new"
1178 * file. However, if the path exists relative to the tag file, it's
1179 * pretty clear what's happening, so we may as well get it right.
1182 if (name[0] != '/' &&
1183 stat(name, &sb) && (p = strrchr(tfp->name, '/')) != NULL) {
1185 if ((buf = join(tfp->name, name)) == NULL) {
1186 msgq(sp, M_SYSERR, NULL);
1189 if (stat(buf, &sb) == 0) {
1191 *dlenp = strlen(*dirp);
1199 * Binary search for "string" in memory between "front" and "back".
1201 * This routine is expected to return a pointer to the start of a line at
1202 * *or before* the first word matching "string". Relaxing the constraint
1203 * this way simplifies the algorithm.
1206 * front points to the beginning of a line at or before the first
1209 * back points to the beginning of a line at or after the first
1212 * Base of the Invariants.
1216 * Advancing the Invariants:
1218 * p = first newline after halfway point from front to back.
1220 * If the string at "p" is not greater than the string to match,
1221 * p is the new front. Otherwise it is the new back.
1225 * The definition of the routine allows it return at any point,
1226 * since front is always at or before the line to print.
1228 * In fact, it returns when the chosen "p" equals "back". This
1229 * implies that there exists a string is least half as long as
1230 * (back - front), which in turn implies that a linear search will
1231 * be no more expensive than the cost of simply printing a string or two.
1233 * Trying to continue with binary search at this point would be
1234 * more trouble than it's worth.
1240 #define SKIP_PAST_NEWLINE(p, back) \
1241 while (p < back && *p++ != '\n') continue;
1244 binary_search(char *string, char *front, char *back)
1248 p = front + (back - front) / 2;
1249 SKIP_PAST_NEWLINE(p, back);
1252 if (compare(string, p, back) == GREATER)
1256 p = front + (back - front) / 2;
1257 SKIP_PAST_NEWLINE(p, back);
1263 * Find the first line that starts with string, linearly searching from front
1266 * Return NULL for no such line.
1268 * This routine assumes:
1270 * o front points at the first character in a line.
1271 * o front is before or at the first line to be printed.
1274 linear_search(char *string, char *front, char *back, long tl)
1277 while (front < back) {
1278 end = tl && back-front > tl ? front+tl : back;
1279 switch (compare(string, front, end)) {
1280 case EQUAL: /* Found it. */
1282 case LESS: /* No such string. */
1284 case GREATER: /* Keep going. */
1287 SKIP_PAST_NEWLINE(front, back);
1293 * Return LESS, GREATER, or EQUAL depending on how the string1 compares
1294 * with string2 (s1 ??? s2).
1296 * o Matches up to len(s1) are EQUAL.
1297 * o Matches up to len(s2) are GREATER.
1299 * The string "s1" is null terminated. The string s2 is '\t', space, (or
1300 * "back") terminated.
1303 * Reasonably modern ctags programs use tabs as separators, not spaces.
1304 * However, historic programs did use spaces, and, I got complaints.
1307 compare(char *s1, char *s2, char *back)
1309 for (; *s1 && s2 < back && (*s2 != '\t' && *s2 != ' '); ++s1, ++s2)
1311 return (*s1 < *s2 ? LESS : GREATER);
1312 return (*s1 ? GREATER : s2 < back &&
1313 (*s2 != '\t' && *s2 != ' ') ? LESS : EQUAL);