src/find.c

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