contrib/nvi/ex/ex_tag.c

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