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