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