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