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