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