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
54char	block[BUFSIZ + 2];		/* leave room for end-of-block mark */
55int	blocklen;			/* length of disk block read */
56char	blockmark;			/* mark character to be searched for */
57long	blocknumber;			/* block number */
58char	*blockp;			/* pointer to current char in block */
59char	lastfilepath[PATHLEN + 1];	/* last file that full path was */
60					/* computed for */
61
62static	char	cpattern[PATLEN + 1];	/* compressed pattern */
63static	long	lastfcnoffset;		/* last function name offset */
64static	long	postingsfound;		/* retrieved number of postings */
65static	char	*regexp;		/* regular expression */
66static	POSTING	*postingp;		/* retrieved posting set pointer */
67static	long	searchcount;		/* count of files searched */
68static	long	starttime;		/* start time for progress messages */
69
70static POSTING *getposting(void);
71static void putsource(FILE *output);
72static void putref(char *file, char *function);
73static void findcalledbysub(char *file);
74static void findterm(void);
75static void fileprogress(void);
76static void putpostingref(POSTING *p);
77static void putline(FILE *output);
78static char *strtolower(char *s);
79static char *filepath(char *file);
80
81/* find the symbol in the cross-reference */
82
83void
84findsymbol(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;
224matched:
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			}
240notmatched:
241			cp = blockp;
242		}
243	}
244	blockp = cp;
245}
246
247/* find the function definition or #define */
248
249void
250finddef(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 */
342matched:
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
361void
362findallfcns(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
393void
394findcalledby(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
442static void
443findcalledbysub(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
480void
481findcalling(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
547void
548findassignments(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
630char *
631findgreppat(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
652char *
653findegreppat(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
678void
679findfile(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
698void
699findinclude(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
741FINDINIT
742findinit(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
838void
839findcleanup(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
850static void
851findterm(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
937static void
938fileprogress(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
948void
949initprogress(void)
950{
951	searchcount = 0;
952	starttime = time((long *)NULL);
953}
954
955/* display the progress every three seconds */
956
957void
958progress(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
973BOOL
974match(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
997BOOL
998matchrest(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
1018static POSTING *
1019getposting(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
1034static void
1035putpostingref(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
1054static void
1055putref(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
1075static void
1076putsource(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
1119static void
1120putline(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
1154void
1155getstring(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
1180char *
1181scanpast(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
1201char *
1202readblock(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
1223long
1224dbseek(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
1244static char *
1245strtolower(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
1264static char *
1265filepath(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}
1301