usr/src/tools/cscope-fast/find.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*      Copyright (c) 1988 AT&T */
  23 /*        All Rights Reserved   */
  24
  25
  26 /*
  27  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
  28  * Use is subject to license terms.
  29  */
  30
  31 #pragma ident   "%Z%%M% %I%     %E% SMI"
  32
  33 /*
  34  *      cscope - interactive C symbol or text cross-reference
  35  *
  36  *      searching functions
  37  */
  38
  39 #include <unistd.h>
  40 #include <stdio.h>
  41 #include <libgen.h>
  42 #include "global.h"
  43 #include "vp.h"
  44
  45 /*
  46  * most of these functions have been optimized so their innermost loops have
  47  * only one test for the desired character by putting the char and
  48  * an end-of-block marker (\0) at the end of the disk block buffer.
  49  * When the inner loop exits on the char, an outer loop will see if
  50  * the char is followed by a \0.  If so, it will read the next block
  51  * and restart the inner loop.
  52  */
  53
  54 char    block[BUFSIZ + 2];              /* leave room for end-of-block mark */
  55 int     blocklen;                       /* length of disk block read */
  56 char    blockmark;                      /* mark character to be searched for */
  57 long    blocknumber;                    /* block number */
  58 char    *blockp;                        /* pointer to current char in block */
  59 char    lastfilepath[PATHLEN + 1];      /* last file that full path was */
  60                                         /* computed for */
  61
  62 static  char    cpattern[PATLEN + 1];   /* compressed pattern */
  63 static  long    lastfcnoffset;          /* last function name offset */
  64 static  long    postingsfound;          /* retrieved number of postings */
  65 static  char    *regexp;                /* regular expression */
  66 static  POSTING *postingp;              /* retrieved posting set pointer */
  67 static  long    searchcount;            /* count of files searched */
  68 static  long    starttime;              /* start time for progress messages */
  69
  70 static POSTING *getposting(void);
  71 static void putsource(FILE *output);
  72 static void putref(char *file, char *function);
  73 static void findcalledbysub(char *file);
  74 static void findterm(void);
  75 static void fileprogress(void);
  76 static void putpostingref(POSTING *p);
  77 static void putline(FILE *output);
  78 static char *strtolower(char *s);
  79 static char *filepath(char *file);
  80
  81 /* find the symbol in the cross-reference */
  82
  83 void
  84 findsymbol(void)
  85 {
  86         char    file[PATHLEN + 1];      /* source file name */
  87         char    function[PATLEN + 1];   /* function name */
  88         char    macro[PATLEN + 1];      /* macro name */
  89         char    symbol[PATLEN + 1];     /* symbol name */
  90         char    *cp;
  91         char    c;
  92         char    *s;
  93
  94         if (invertedindex == YES) {
  95                 long    lastline = 0;
  96                 POSTING *p;
  97
  98                 findterm();
  99                 while ((p = getposting()) != NULL) {
 100                         if (p->type != INCLUDE && p->lineoffset != lastline) {
 101                                 putpostingref(p);
 102                                 lastline = p->lineoffset;
 103                         }
 104                 }
 105                 return;
 106         }
 107         (void) scanpast('\t');          /* find the end of the header */
 108         skiprefchar();                  /* skip the file marker */
 109         getstring(file);                /* save the file name */
 110         *function = '\0';
 111         /* a macro can be inside a function, but not vice versa */
 112         *macro = '\0';
 113
 114         /* find the next symbol */
 115         /* note: this code was expanded in-line for speed */
 116         /* while (scanpast('\n') != NULL) { */
 117         /* other macros were replaced by code using cp instead of blockp */
 118         cp = blockp;
 119         for (;;) {
 120                 setmark('\n');
 121                 do {    /* innermost loop optimized to only one test */
 122                         while (*cp != '\n') {
 123                                 ++cp;
 124                         }
 125                 } while (*(cp + 1) == '\0' && (cp = readblock()) != NULL);
 126
 127                 /* skip the found character */
 128                 if (cp != NULL && *(++cp + 1) == '\0') {
 129                         cp = readblock();
 130                 }
 131                 if (cp == NULL) {
 132                         break;
 133                 }
 134                 /* look for a source file or function name */
 135                 if (*cp == '\t') {
 136                         blockp = cp;
 137                         switch (getrefchar()) {
 138
 139                         case NEWFILE:           /* file name */
 140
 141                                 /* save the name */
 142                                 skiprefchar();
 143                                 getstring(file);
 144
 145                                 /* check for the end of the symbols */
 146                                 if (*file == '\0') {
 147                                         return;
 148                                 }
 149                                 fileprogress();
 150                                 /* FALLTHROUGH */
 151
 152                         case FCNEND:            /* function end */
 153                                 *function = '\0';
 154                                 goto notmatched;        /* don't match name */
 155
 156                         case FCNDEF:            /* function name */
 157                                 s = function;
 158                                 break;
 159
 160                         case DEFINE:            /* could be a macro */
 161                                 if (fileversion >= 10) {
 162                                         s = macro;
 163                                 } else {
 164                                         s = symbol;
 165                                 }
 166                                 break;
 167
 168                         case DEFINEEND:
 169                                 *macro = '\0';
 170                                 goto notmatched;        /* don't match name */
 171
 172                         case INCLUDE:           /* #include file */
 173                                 goto notmatched;        /* don't match name */
 174                         default:                /* other symbol */
 175                                 s = symbol;
 176                         }
 177                         /* save the name */
 178                         skiprefchar();
 179                         getstring(s);
 180
 181                         /* see if this is a regular expression pattern */
 182                         if (regexp != NULL) {
 183                                 if (caseless == YES) {
 184                                         s = strtolower(s);
 185                                 }
 186                                 if (*s != '\0' && regex(regexp, s) != NULL) {
 187                                         goto matched;
 188                                 }
 189                         }
 190                         /* match the symbol to the text pattern */
 191                         else if (strequal(pattern, s)) {
 192                                 goto matched;
 193                         }
 194                         goto notmatched;
 195                 }
 196                 /* if this is a regular expression pattern */
 197                 if (regexp != NULL) {
 198                         c = *cp;
 199                         if (c & 0200) { /* digraph char? */
 200                                 c = dichar1[(c & 0177) / 8];
 201                         }
 202                         /* if this is a symbol */
 203                         if (isalpha(c) || c == '_') {
 204                                 blockp = cp;
 205                                 getstring(symbol);
 206                                 s = symbol;
 207                                 if (caseless == YES) {
 208                                         s = strtolower(s);
 209                                 }
 210                                 /* match the symbol to the regular expression */
 211                                 if (regex(regexp, s) != NULL) {
 212                                         goto matched;
 213                                 }
 214                                 goto notmatched;
 215                         }
 216                 }
 217                 /* match the character to the text pattern */
 218                 else if (*cp == cpattern[0]) {
 219                         blockp = cp;
 220
 221                         /* match the rest of the symbol to the text pattern */
 222                         if (matchrest()) {
 223                                 s = NULL;
 224 matched:
 225                                 /*
 226                                  * output the file, calling function or macro,
 227                                  * and source line
 228                                  */
 229                                 if (*macro != '\0' && s != macro) {
 230                                         putref(file, macro);
 231                                 } else if (s != function) {
 232                                         putref(file, function);
 233                                 } else {
 234                                         putref(file, "");
 235                                 }
 236                                 if (blockp == NULL) {
 237                                         return;
 238                                 }
 239                         }
 240 notmatched:
 241                         cp = blockp;
 242                 }
 243         }
 244         blockp = cp;
 245 }
 246
 247 /* find the function definition or #define */
 248
 249 void
 250 finddef(void)
 251 {
 252         char    file[PATHLEN + 1];      /* source file name */
 253         char    function[PATLEN + 1];   /* function name */
 254         char    macro[PATLEN + 1];      /* macro name */
 255         char    symbol[PATLEN + 1];     /* symbol name */
 256         char    *s;
 257
 258         if (invertedindex == YES) {
 259                 POSTING *p;
 260
 261                 findterm();
 262                 while ((p = getposting()) != NULL) {
 263                         switch (p->type) {
 264                         case DEFINE:            /* could be a macro */
 265                         case FCNDEF:
 266                         case CLASSDEF:
 267                         case ENUMDEF:
 268                         case MEMBERDEF:
 269                         case STRUCTDEF:
 270                         case TYPEDEF:
 271                         case UNIONDEF:
 272                         case GLOBALDEF:         /* other global definition */
 273                         case LOCALDEF:          /* other local definition */
 274                         case PARAMETER:
 275                                 putpostingref(p);
 276                         }
 277                 }
 278                 return;
 279         }
 280         /* find the next file name or definition */
 281         *function = '\0';
 282         /* a macro can be inside a function, but not vice versa */
 283         *macro = '\0';
 284
 285         while (scanpast('\t') != NULL) {
 286                 switch (*blockp) {
 287
 288                 case NEWFILE:
 289                         skiprefchar();  /* save file name */
 290                         getstring(file);
 291                         if (*file == '\0') {    /* if end of symbols */
 292                                 return;
 293                         }
 294                         fileprogress();
 295                         /* FALLTHROUGH */
 296
 297                 case FCNEND:            /* function end */
 298                         *function = '\0';
 299                         break;
 300
 301                 case FCNDEF:            /* function name */
 302                         s = function;
 303                         goto def;
 304
 305                 case DEFINE:            /* could be a macro */
 306                         if (fileversion >= 10) {
 307                                 s = macro;
 308                         } else {
 309                                 s = symbol;
 310                         }
 311                         goto def;
 312
 313                 case DEFINEEND:
 314                         *macro = '\0';
 315                         break;
 316
 317                 case CLASSDEF:
 318                 case ENUMDEF:
 319                 case MEMBERDEF:
 320                 case STRUCTDEF:
 321                 case TYPEDEF:
 322                 case UNIONDEF:
 323                 case GLOBALDEF:         /* other global definition */
 324                 case LOCALDEF:          /* other local definition */
 325                 case PARAMETER:
 326                         s = symbol;
 327                 def:
 328                         /* save the name */
 329                         skiprefchar();
 330                         getstring(s);
 331
 332                         /* see if this is a regular expression pattern */
 333                         if (regexp != NULL) {
 334                                 if (caseless == YES) {
 335                                         s = strtolower(s);
 336                                 }
 337                                 if (*s != '\0' && regex(regexp, s) != NULL) {
 338                                         goto matched;
 339                                 }
 340                         } else if (strequal(pattern, s)) {
 341                                 /* match the symbol to the text pattern */
 342 matched:
 343                                 /*
 344                                  * output the file, calling function or macro,
 345                                  * and source line
 346                                  */
 347                                 if (*macro != '\0' && s != macro) {
 348                                         putref(file, macro);
 349                                 } else if (s != function) {
 350                                         putref(file, function);
 351                                 } else {
 352                                         putref(file, "");
 353                                 }
 354                         }
 355                 }
 356         }
 357 }
 358
 359 /* find all function definitions (used by samuel only) */
 360
 361 void
 362 findallfcns(void)
 363 {
 364         char    file[PATHLEN + 1];      /* source file name */
 365         char    function[PATLEN + 1];   /* function name */
 366
 367         /* find the next file name or definition */
 368         while (scanpast('\t') != NULL) {
 369                 switch (*blockp) {
 370                 case NEWFILE:
 371                         skiprefchar();  /* save file name */
 372                         getstring(file);
 373                         if (*file == '\0') {    /* if end of symbols */
 374                                 return;
 375                         }
 376                         fileprogress();
 377                         break;
 378
 379                 case FCNDEF:
 380                 case CLASSDEF:
 381                         skiprefchar();  /* save function name */
 382                         getstring(function);
 383
 384                         /* output the file, function and source line */
 385                         putref(file, function);
 386                         break;
 387                 }
 388         }
 389 }
 390
 391 /* find the functions called by this function */
 392
 393 void
 394 findcalledby(void)
 395 {
 396         char    file[PATHLEN + 1];      /* source file name */
 397
 398         if (invertedindex == YES) {
 399                 POSTING *p;
 400
 401                 findterm();
 402                 while ((p = getposting()) != NULL) {
 403                         switch (p->type) {
 404                         case DEFINE:            /* could be a macro */
 405                         case FCNDEF:
 406                                 if (dbseek(p->lineoffset) != -1 &&
 407                                     scanpast('\t') != NULL) {   /* skip def */
 408                                         findcalledbysub(srcfiles[p->fileindex]);
 409                                 }
 410                         }
 411                 }
 412                 return;
 413         }
 414         /* find the function definition(s) */
 415         while (scanpast('\t') != NULL) {
 416                 switch (*blockp) {
 417                 case NEWFILE:
 418                         skiprefchar();  /* save file name */
 419                         getstring(file);
 420                         if (*file == '\0') {    /* if end of symbols */
 421                                 return;
 422                         }
 423                         fileprogress();
 424                         break;
 425
 426                 case DEFINE:            /* could be a macro */
 427                         if (fileversion < 10) {
 428                                 break;
 429                         }
 430                         /* FALLTHROUGH */
 431
 432                 case FCNDEF:
 433                         skiprefchar();  /* match name to pattern */
 434                         if (match()) {
 435                                 findcalledbysub(file);
 436                         }
 437                         break;
 438                 }
 439         }
 440 }
 441
 442 static void
 443 findcalledbysub(char *file)
 444 {
 445         /* find the next function call or the end of this function */
 446         while (scanpast('\t') != NULL) {
 447                 switch (*blockp) {
 448                 case DEFINE:            /* #define inside a function */
 449                         if (fileversion >= 10) {        /* skip it */
 450                                 while (scanpast('\t') != NULL &&
 451                                     *blockp != DEFINEEND)
 452                                         ;
 453                         }
 454                         break;
 455                 case FCNCALL:           /* function call */
 456
 457                         /* output the file name */
 458                         (void) fprintf(refsfound, "%s ", filepath(file));
 459
 460                         /* output the function name */
 461                         skiprefchar();
 462                         putline(refsfound);
 463                         (void) putc(' ', refsfound);
 464
 465                         /* output the source line */
 466                         putsource(refsfound);
 467                         break;
 468
 469                 case DEFINEEND:         /* #define end */
 470                 case FCNEND:            /* function end */
 471                 case FCNDEF:            /* function end (pre 9.5) */
 472                 case NEWFILE:           /* file end */
 473                         return;
 474                 }
 475         }
 476 }
 477
 478 /* find the functions calling this function */
 479
 480 void
 481 findcalling(void)
 482 {
 483         char    file[PATHLEN + 1];      /* source file name */
 484         char    function[PATLEN + 1];   /* function name */
 485         char    macro[PATLEN + 1];      /* macro name */
 486
 487         if (invertedindex == YES) {
 488                 POSTING *p;
 489
 490                 findterm();
 491                 while ((p = getposting()) != NULL) {
 492                         if (p->type == FCNCALL) {
 493                                 putpostingref(p);
 494                         }
 495                 }
 496                 return;
 497         }
 498         /* find the next file name or function definition */
 499         /* a macro can be inside a function, but not vice versa */
 500         *macro = '\0';
 501
 502         while (scanpast('\t') != NULL) {
 503                 switch (*blockp) {
 504                 case NEWFILE:           /* save file name */
 505                         skiprefchar();
 506                         getstring(file);
 507                         if (*file == '\0') {    /* if end of symbols */
 508                                 return;
 509                         }
 510                         fileprogress();
 511                         /* FALLTHROUGH */
 512                 case FCNEND:            /* function end */
 513                         *function = '\0';
 514                         break;
 515                 case DEFINE:            /* could be a macro */
 516                         if (fileversion >= 10) {
 517                                 skiprefchar();
 518                                 getstring(macro);
 519                         }
 520                         break;
 521
 522                 case DEFINEEND:
 523                         *macro = '\0';
 524                         break;
 525
 526                 case FCNDEF:            /* save calling function name */
 527                         skiprefchar();
 528                         getstring(function);
 529                         break;
 530                 case FCNCALL:           /* match function called to pattern */
 531                         skiprefchar();
 532                         if (match()) {
 533                                 /* output the file, calling function or */
 534                                 /* macro, and source */
 535                                 if (*macro != '\0') {
 536                                         putref(file, macro);
 537                                 } else {
 538                                         putref(file, function);
 539                                 }
 540                         }
 541                 }
 542         }
 543 }
 544
 545 /* find direct assignment to, and increment and decrement of, this variable */
 546
 547 void
 548 findassignments(void)
 549 {
 550         char    file[PATHLEN + 1];      /* source file name */
 551         char    function[PATLEN + 1];   /* function name */
 552         char    macro[PATLEN + 1];      /* macro name */
 553
 554         if (fileversion < 13) {
 555                 putmsg("Database built with cscope version < 13 does not "
 556                     "have assignment information");
 557                 (void) sleep(3);
 558                 return;
 559         }
 560 #if CTRACE
 561         ctroff();
 562 #endif
 563         if (invertedindex == YES) {
 564                 POSTING *p;
 565
 566                 findterm();
 567                 while ((p = getposting()) != NULL) {
 568                         switch (p->type) {
 569                         case ASSIGNMENT:
 570                         case GLOBALDEF:         /* can have initializer */
 571                         case LOCALDEF:          /* can have initializer */
 572                         case PARAMETER:         /* initial value */
 573                                 putpostingref(p);
 574                         }
 575                 }
 576                 return;
 577         }
 578         /* find the next file name or function definition */
 579         /* a macro can be inside a function, but not vice versa */
 580         *macro = '\0';
 581
 582         while (scanpast('\t') != NULL) {
 583                 switch (*blockp) {
 584                 case NEWFILE:           /* save file name */
 585                         skiprefchar();
 586                         getstring(file);
 587                         if (*file == '\0') {    /* if end of symbols */
 588                                 return;
 589                         }
 590                         fileprogress();
 591                         /* FALLTHROUGH */
 592                 case FCNEND:            /* function end */
 593                         *function = '\0';
 594                         break;
 595                 case DEFINE:            /* could be a macro */
 596                         if (fileversion >= 10) {
 597                                 skiprefchar();
 598                                 getstring(macro);
 599                         }
 600                         break;
 601
 602                 case DEFINEEND:
 603                         *macro = '\0';
 604                         break;
 605
 606                 case FCNDEF:            /* save calling function name */
 607                         skiprefchar();
 608                         getstring(function);
 609                         break;
 610                 case ASSIGNMENT:        /* match assignment to pattern */
 611                 case GLOBALDEF:         /* can have initializer */
 612                 case LOCALDEF:          /* can have initializer */
 613                 case PARAMETER:         /* initial value */
 614                         skiprefchar();
 615                         if (match()) {
 616                                 /* output the file, calling function or */
 617                                 /* macro, and source */
 618                                 if (*macro != '\0') {
 619                                         putref(file, macro);
 620                                 } else {
 621                                         putref(file, function);
 622                                 }
 623                         }
 624                 }
 625         }
 626 }
 627
 628 /* find the grep pattern in the source files */
 629
 630 char *
 631 findgreppat(void)
 632 {
 633         char    egreppat[2 * PATLEN];
 634         char    *cp, *pp;
 635
 636         /* translate egrep special characters in the regular expression */
 637         cp = egreppat;
 638         for (pp = pattern; *pp != '\0'; ++pp) {
 639                 if (strchr("+?|()", *pp) != NULL) {
 640                         *cp++ = '\\';
 641                 }
 642                 *cp++ = *pp;
 643         }
 644         *cp = '\0';
 645
 646         /* search the source files */
 647         return (findegreppat(egreppat));
 648 }
 649
 650 /* find this regular expression in the source files */
 651
 652 char *
 653 findegreppat(char *egreppat)
 654 {
 655         int     i;
 656         char    *egreperror;
 657         char    msg[MSGLEN + 1];
 658
 659         /* compile the pattern */
 660         if ((egreperror = egrepinit(egreppat)) == NULL) {
 661
 662                 /* search the files */
 663                 for (i = 0; i < nsrcfiles; ++i) {
 664                         char *file = filepath(srcfiles[i]);
 665                         fileprogress();
 666                         if (egrep(file, refsfound, "%s <unknown> %ld ") < 0) {
 667                                 (void) sprintf(msg, "Cannot open file %s",
 668                                     file);
 669                                 putmsg2(msg);
 670                         }
 671                 }
 672         }
 673         return (egreperror);
 674 }
 675
 676 /* find matching file names */
 677
 678 void
 679 findfile(void)
 680 {
 681         int     i;
 682         char    *s;
 683
 684         for (i = 0; i < nsrcfiles; ++i) {
 685                 s = srcfiles[i];
 686                 if (caseless == YES) {
 687                         s = strtolower(s);
 688                 }
 689                 if (regex(regexp, s) != NULL) {
 690                         (void) fprintf(refsfound, "%s <unknown> 1 <unknown>\n",
 691                                 filepath(srcfiles[i]));
 692                 }
 693         }
 694 }
 695
 696 /* find files #including this file */
 697
 698 void
 699 findinclude(void)
 700 {
 701         char    file[PATHLEN + 1];      /* source file name */
 702
 703         if (invertedindex == YES) {
 704                 POSTING *p;
 705
 706                 findterm();
 707                 while ((p = getposting()) != NULL) {
 708                         if (p->type == INCLUDE) {
 709                                 putpostingref(p);
 710                         }
 711                 }
 712                 return;
 713         }
 714         /* find the next file name or function definition */
 715         while (scanpast('\t') != NULL) {
 716                 switch (*blockp) {
 717
 718                 case NEWFILE:           /* save file name */
 719                         skiprefchar();
 720                         getstring(file);
 721                         if (*file == '\0') {    /* if end of symbols */
 722                                 return;
 723                         }
 724                         fileprogress();
 725                         break;
 726
 727                 case INCLUDE:           /* match function called to pattern */
 728                         skiprefchar();
 729                         /* skip global or local #include marker */
 730                         skiprefchar();
 731                         if (match()) {
 732                                 /* output the file and source line */
 733                                 putref(file, "");
 734                         }
 735                 }
 736         }
 737 }
 738
 739 /* initialize */
 740
 741 FINDINIT
 742 findinit(void)
 743 {
 744         char    buf[PATLEN + 3];
 745         BOOL    isregexp = NO;
 746         int     i;
 747         char    *s;
 748         unsigned c;
 749
 750         /* remove trailing white space */
 751         for (s = pattern + strlen(pattern) - 1; isspace(*s); --s) {
 752                 *s = '\0';
 753         }
 754         /* allow a partial match for a file name */
 755         if (field == FILENAME || field == INCLUDES) {
 756                 /* allow types.h to match #include <sys/types.h> */
 757                 if (invertedindex == YES && field == INCLUDES &&
 758                     strncmp(pattern, ".*", 2) != 0) {
 759                         (void) sprintf(pattern, ".*%s", strcpy(buf, pattern));
 760                 }
 761                 if ((regexp = regcmp(pattern, (char *)NULL)) == NULL) {
 762                         return (REGCMPERROR);
 763                 }
 764                 return (NOERROR);
 765         }
 766         /* see if the pattern is a regular expression */
 767         if (strpbrk(pattern, "^.[{*+$") != NULL) {
 768                 isregexp = YES;
 769         } else {
 770                 /* check for a valid C symbol */
 771                 s = pattern;
 772                 if (!isalpha(*s) && *s != '_') {
 773                         return (NOTSYMBOL);
 774                 }
 775                 while (*++s != '\0') {
 776                         if (!isalnum(*s) && *s != '_') {
 777                                 return (NOTSYMBOL);
 778                         }
 779                 }
 780                 /*
 781                  * look for use of the -T option (truncate symbol to 8
 782                  * characters) on a database not built with -T
 783                  */
 784                 if (truncatesyms == YES && isuptodate == YES &&
 785                     dbtruncated == NO && s - pattern >= 8) {
 786                         (void) strcpy(pattern + 8, ".*");
 787                         isregexp = YES;
 788                 }
 789         }
 790         /* if this is a regular expression or letter case is to be ignored */
 791         /* or there is an inverted index */
 792         if (isregexp == YES || caseless == YES || invertedindex == YES) {
 793
 794                 /* remove a leading ^ */
 795                 s = pattern;
 796                 if (*s == '^') {
 797                         (void) strcpy(newpat, s + 1);
 798                         (void) strcpy(s, newpat);
 799                 }
 800                 /* remove a trailing $ */
 801                 i = strlen(s) - 1;
 802                 if (s[i] == '$') {
 803                         s[i] = '\0';
 804                 }
 805                 /* if requested, try to truncate a C symbol pattern */
 806                 if (truncatesyms == YES && strpbrk(s, "[{*+") == NULL) {
 807                         s[8] = '\0';
 808                 }
 809                 /* must be an exact match */
 810                 /*
 811                  * note: regcmp doesn't recognize ^*keypad$ as an syntax error
 812                  * unless it is given as a single arg
 813                  */
 814                 (void) sprintf(buf, "^%s$", s);
 815                 if ((regexp = regcmp(buf, (char *)NULL)) == NULL) {
 816                         return (REGCMPERROR);
 817                 }
 818         } else {
 819                 /* if requested, truncate a C symbol pattern */
 820                 if (truncatesyms == YES && field <= CALLING) {
 821                         pattern[8] = '\0';
 822                 }
 823                 /* compress the string pattern for matching */
 824                 s = cpattern;
 825                 for (i = 0; (c = pattern[i]) != '\0'; ++i) {
 826                         if (dicode1[c] && dicode2[(unsigned)pattern[i + 1]]) {
 827                                 c = (0200 - 2) + dicode1[c] +
 828                                     dicode2[(unsigned)pattern[i + 1]];
 829                                 ++i;
 830                         }
 831                         *s++ = (char)c;
 832                 }
 833                 *s = '\0';
 834         }
 835         return (NOERROR);
 836 }
 837
 838 void
 839 findcleanup(void)
 840 {
 841         /* discard any regular expression */
 842         if (regexp != NULL) {
 843                 free(regexp);
 844                 regexp = NULL;
 845         }
 846 }
 847
 848 /* find this term, which can be a regular expression */
 849
 850 static void
 851 findterm(void)
 852 {
 853         char    *s;
 854         int     len;
 855         char    prefix[PATLEN + 1];
 856         char    term[PATLEN + 1];
 857
 858         npostings = 0;          /* will be non-zero after database built */
 859         lastfcnoffset = 0;      /* clear the last function name found */
 860         boolclear();            /* clear the posting set */
 861
 862         /* get the string prefix (if any) of the regular expression */
 863         (void) strcpy(prefix, pattern);
 864         if ((s = strpbrk(prefix, ".[{*+")) != NULL) {
 865                 *s = '\0';
 866         }
 867         /* if letter case is to be ignored */
 868         if (caseless == YES) {
 869
 870                 /*
 871                  * convert the prefix to upper case because it is lexically
 872                  * less than lower case
 873                  */
 874                 s = prefix;
 875                 while (*s != '\0') {
 876                         *s = toupper(*s);
 877                         ++s;
 878                 }
 879         }
 880         /* find the term lexically >= the prefix */
 881         (void) invfind(&invcontrol, prefix);
 882         if (caseless == YES) {  /* restore lower case */
 883                 (void) strcpy(prefix, strtolower(prefix));
 884         }
 885         /*
 886          * a null prefix matches the null term in the inverted index,
 887          * so move to the first real term
 888          */
 889         if (*prefix == '\0') {
 890                 (void) invforward(&invcontrol);
 891         }
 892         len = strlen(prefix);
 893         do {
 894                 (void) invterm(&invcontrol, term);      /* get the term */
 895                 s = term;
 896                 if (caseless == YES) {
 897                         s = strtolower(s);      /* make it lower case */
 898                 }
 899                 /* if it matches */
 900                 if (regex(regexp, s) != NULL) {
 901                         /* add it's postings to the set */
 902                         if ((postingp = boolfile(&invcontrol,
 903                             &npostings, OR)) == NULL) {
 904                                 break;
 905                         }
 906                 } else if (len > 0) {
 907                         /* if there is a prefix */
 908
 909                         /*
 910                          * if ignoring letter case and the term is out of the
 911                          * range of possible matches
 912                          */
 913                         if (caseless == YES) {
 914                                 if (strncmp(term, prefix, len) > 0) {
 915                                         break;  /* stop searching */
 916                                 }
 917                         }
 918                         /* if using letter case and the prefix doesn't match */
 919                         else if (strncmp(term, prefix, len) != 0) {
 920                                 break;  /* stop searching */
 921                         }
 922                 }
 923                 /* display progress about every three seconds */
 924                 if (++searchcount % 50 == 0) {
 925                         progress("%ld of %ld symbols matched",
 926                             searchcount, totalterms);
 927                 }
 928         } while (invforward(&invcontrol));      /* while didn't wrap around */
 929
 930         /* initialize the progress message for retrieving the references */
 931         initprogress();
 932         postingsfound = npostings;
 933 }
 934
 935 /* display the file search progress about every three seconds */
 936
 937 static void
 938 fileprogress(void)
 939 {
 940         if (++searchcount % 10 == 0) {
 941                 progress("%ld of %ld files searched", searchcount,
 942                     (long)nsrcfiles);
 943         }
 944 }
 945
 946 /* initialize the progress message */
 947
 948 void
 949 initprogress(void)
 950 {
 951         searchcount = 0;
 952         starttime = time((long *)NULL);
 953 }
 954
 955 /* display the progress every three seconds */
 956
 957 void
 958 progress(char *format, long n1, long n2)
 959 {
 960         char    msg[MSGLEN + 1];
 961         long    now;
 962
 963         /* print after 2 seconds so the average is nearer 3 seconds */
 964         if (linemode == NO && (now = time((long *)NULL)) - starttime >= 2) {
 965                 starttime = now;
 966                 (void) sprintf(msg, format, n1, n2);
 967                 putmsg(msg);
 968         }
 969 }
 970
 971 /* match the pattern to the string */
 972
 973 BOOL
 974 match(void)
 975 {
 976         char    string[PATLEN + 1];
 977         char    *s;
 978
 979         /* see if this is a regular expression pattern */
 980         if (regexp != NULL) {
 981                 getstring(string);
 982                 if (*string == '\0') {
 983                         return (NO);
 984                 }
 985                 s = string;
 986                 if (caseless == YES) {
 987                         s = strtolower(s);
 988                 }
 989                 return (regex(regexp, s) ? YES : NO);
 990         }
 991         /* it is a string pattern */
 992         return ((BOOL)(*blockp == cpattern[0] && matchrest()));
 993 }
 994
 995 /* match the rest of the pattern to the name */
 996
 997 BOOL
 998 matchrest(void)
 999 {
1000         int     i = 1;
1001
1002         skiprefchar();
1003         do {
1004                 while (*blockp == cpattern[i]) {
1005                         ++blockp;
1006                         ++i;
1007                 }
1008         } while (*(blockp + 1) == '\0' && readblock() != NULL);
1009
1010         if (*blockp == '\n' && cpattern[i] == '\0') {
1011                 return (YES);
1012         }
1013         return (NO);
1014 }
1015
1016 /* get the next posting for this term */
1017
1018 static POSTING *
1019 getposting(void)
1020 {
1021         if (npostings-- <= 0) {
1022                 return (NULL);
1023         }
1024         /* display progress about every three seconds */
1025         if (++searchcount % 100 == 0) {
1026                 progress("%ld of %ld possible references retrieved",
1027                     searchcount, postingsfound);
1028         }
1029         return (postingp++);
1030 }
1031
1032 /* put the posting reference into the file */
1033
1034 static void
1035 putpostingref(POSTING *p)
1036 {
1037         static  char    function[PATLEN + 1];   /* function name */
1038
1039         if (p->fcnoffset == 0) {
1040                 *function = '\0';
1041         } else if (p->fcnoffset != lastfcnoffset) {
1042                 if (dbseek(p->fcnoffset) != -1) {
1043                         getstring(function);
1044                         lastfcnoffset = p->fcnoffset;
1045                 }
1046         }
1047         if (dbseek(p->lineoffset) != -1) {
1048                 putref(srcfiles[p->fileindex], function);
1049         }
1050 }
1051
1052 /* put the reference into the file */
1053
1054 static void
1055 putref(char *file, char *function)
1056 {
1057         FILE    *output;
1058
1059         /* put global references first */
1060         if (*function == '\0') {
1061                 function = "<global>";
1062                 output = refsfound;
1063         } else {
1064                 output = nonglobalrefs;
1065         }
1066         if (fprintf(output, "%s %s ", filepath(file), function) == EOF) {
1067                 cannotwrite(temp1);
1068                 /* NOTREACHED */
1069         }
1070         putsource(output);
1071 }
1072
1073 /* put the source line into the file */
1074
1075 static void
1076 putsource(FILE *output)
1077 {
1078         char    *cp, nextc = '\0';
1079
1080         if (fileversion <= 5) {
1081                 (void) scanpast(' ');
1082                 putline(output);
1083                 (void) putc('\n', output);
1084                 return;
1085         }
1086         /* scan back to the beginning of the source line */
1087         cp = blockp;
1088         while (*cp != '\n' || nextc != '\n') {
1089                 nextc = *cp;
1090                 if (--cp < block) {
1091                         /* read the previous block */
1092                         (void) dbseek((blocknumber - 1) * BUFSIZ);
1093                         cp = &block[BUFSIZ - 1];
1094                 }
1095         }
1096         /* there must be a double newline followed by a line number */
1097         blockp = cp;
1098         setmark(' ');   /* so getrefchar doesn't skip the last block char */
1099         if (*blockp != '\n' || getrefchar() != '\n' ||
1100             !isdigit(getrefchar()) && fileversion >= 12) {
1101                 putmsg("Internal error: cannot get source line from database");
1102                 myexit(1);
1103         }
1104         /* until a double newline is found */
1105         do {
1106                 /* skip a symbol type */
1107                 if (*blockp == '\t') {
1108                         skiprefchar();
1109                         skiprefchar();
1110                 }
1111                 /* output a piece of the source line */
1112                 putline(output);
1113         } while (blockp != NULL && getrefchar() != '\n');
1114         (void) putc('\n', output);
1115 }
1116
1117 /* put the rest of the cross-reference line into the file */
1118
1119 static void
1120 putline(FILE *output)
1121 {
1122         char    *cp;
1123         unsigned c;
1124
1125         setmark('\n');
1126         cp = blockp;
1127         do {
1128                 while ((c = *cp) != '\n') {
1129                         /* check for a compressed digraph */
1130                         if (c & 0200) {
1131                                 c &= 0177;
1132                                 (void) putc(dichar1[c / 8], output);
1133                                 (void) putc(dichar2[c & 7], output);
1134                         } else if (c < ' ') {
1135                                 /* a compressed keyword */
1136                                 (void) fputs(keyword[c].text, output);
1137                                 if (keyword[c].delim != '\0') {
1138                                         (void) putc(' ', output);
1139                                 }
1140                                 if (keyword[c].delim == '(') {
1141                                         (void) putc('(', output);
1142                                 }
1143                         } else {
1144                                 (void) putc((int)c, output);
1145                         }
1146                         ++cp;
1147                 }
1148         } while (*(cp + 1) == '\0' && (cp = readblock()) != NULL);
1149         blockp = cp;
1150 }
1151
1152 /* put the rest of the cross-reference line into the string */
1153
1154 void
1155 getstring(char *s)
1156 {
1157         char    *cp;
1158         unsigned c;
1159
1160         setmark('\n');
1161         cp = blockp;
1162         do {
1163                 while ((c = *cp) != '\n') {
1164                         if (c & 0200) {
1165                                 c &= 0177;
1166                                 *s++ = dichar1[c / 8];
1167                                 *s++ = dichar2[c & 7];
1168                         } else {
1169                                 *s++ = (char)c;
1170                         }
1171                         ++cp;
1172                 }
1173         } while (*(cp + 1) == '\0' && (cp = readblock()) != NULL);
1174         blockp = cp;
1175         *s = '\0';
1176 }
1177
1178 /* scan past the next occurence of this character in the cross-reference */
1179
1180 char *
1181 scanpast(int c)
1182 {
1183         char    *cp;
1184
1185         setmark(c);
1186         cp = blockp;
1187         do {    /* innermost loop optimized to only one test */
1188                 while (*cp != c) {
1189                         ++cp;
1190                 }
1191         } while (*(cp + 1) == '\0' && (cp = readblock()) != NULL);
1192         blockp = cp;
1193         if (cp != NULL) {
1194                 skiprefchar();  /* skip the found character */
1195         }
1196         return (blockp);
1197 }
1198
1199 /* read a block of the cross-reference */
1200
1201 char *
1202 readblock(void)
1203 {
1204         /* read the next block */
1205         blocklen = read(symrefs, block, BUFSIZ);
1206         blockp = block;
1207
1208         /* add the search character and end-of-block mark */
1209         block[blocklen] = blockmark;
1210         block[blocklen + 1] = '\0';
1211
1212         /* return NULL on end-of-file */
1213         if (blocklen == 0) {
1214                 blockp = NULL;
1215         } else {
1216                 ++blocknumber;
1217         }
1218         return (blockp);
1219 }
1220
1221 /* seek to the database offset */
1222
1223 long
1224 dbseek(long offset)
1225 {
1226         long    n;
1227         int     rc = 0;
1228
1229         if ((n = offset / BUFSIZ) != blocknumber) {
1230                 if ((rc = lseek(symrefs, n * BUFSIZ, 0)) == -1) {
1231                         myperror("Lseek failed");
1232                         (void) sleep(3);
1233                         return (rc);
1234                 }
1235                 (void) readblock();
1236                 blocknumber = n;
1237         }
1238         blockp = block + offset % BUFSIZ;
1239         return (rc);
1240 }
1241
1242 /* convert the string to lower case */
1243
1244 static char *
1245 strtolower(char *s)
1246 {
1247         static char buf[PATLEN + 1];
1248         char *lp = buf;
1249
1250         while (*s != '\0') {
1251                 /*
1252                  * note: s in not incremented in this line because the BSD
1253                  * compatibility tolower macro evaluates its argument twice
1254                  */
1255                 *lp++ = tolower(*s);
1256                 ++s;
1257         }
1258         *lp = '\0';
1259         return (buf);
1260 }
1261
1262 /* if needed, convert a relative path to a full path */
1263
1264 static char *
1265 filepath(char *file)
1266 {
1267         static  char    path[PATHLEN + 1];
1268         int     i;
1269
1270         if (*file != '/') {
1271
1272                 /* if same file as last time, return the same path */
1273                 if (strequal(file, lastfilepath)) {
1274                         return (path);
1275                 }
1276                 (void) strcpy(lastfilepath, file);
1277
1278                 /* if requested, prepend a path to a relative file path */
1279                 if (prependpath != NULL) {
1280                         (void) sprintf(path, "%s/%s", prependpath, file);
1281                         return (path);
1282                 }
1283                 /*
1284                  * if the database was built with a view path, return a
1285                  * full path so "cscope -d -f" does not have to be called
1286                  * from the build directory with the same view path
1287                  */
1288                 if (dbvpndirs > 1) {
1289                         for (i = 0; i < dbvpndirs; i++) {
1290                                 (void) sprintf(path,
1291                                     "%s/%s", dbvpdirs[i], file);
1292                                 if (access(path, READ) != -1) {
1293                                         return (path);
1294                                 }
1295                         }
1296                 }
1297                 (void) strcpy(path, file);      /* for lastfilepath check */
1298         }
1299         return (file);
1300 }