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