Return to BSD News archive
Received: by minnie.vk1xwt.ampr.org with NNTP
id AA1956 ; Tue, 23 Feb 93 19:00:13 EST
Newsgroups: comp.os.386bsd.apps
Path: sserve!manuel.anu.edu.au!munnari.oz.au!news.Hawaii.Edu!ames!elroy.jpl.nasa.gov!usc!wupost!csus.edu!netcom.com!alm
From: alm@netcom.com (Andrew Moore)
Subject: C flow-analysis generator [source]
Message-ID: <1993Feb23.001703.22216@netcom.com>
Summary: graphs function call hierarchy
Keywords: C flow-analysis call hierarchy
Organization: Netcom - Online Communication Services (408 241-9760 guest)
Date: Tue, 23 Feb 1993 00:17:03 GMT
Lines: 2075
This is a reworked version of the calls(1) program for printing the
function call hierarchy of a C program. A sample script prints
the 386BSD kernel hierarchy.
The source is also available on ref.tfs.com as ~alm/calls.shar.
-Andrew Moore <alm@netcom.com>
# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# calls.1
# calls.sh
# sample.sh
# prcc.c
# prcg.c
# Makefile
#
echo x - calls.1
sed 's/^X//' >calls.1 << 'END-of-calls.1'
X.TH CALLS 1 PUBLIC
X.SH NAME
Xcalls \- print a function call hierarchy
X.SH SYNOPSIS
Xcalls [-agivx] [-dn] [-wn] [-rname] [cpp-opts] files
X.SH DESCRIPTION
XThe
X.B calls
Xcommand reads
X.I files
Xas C program source and prints to the standard output an
Xenumerated
X.I call graph
Xshowing the function call hierarchy of the program.
XIf invoked with the
X.I \-v
Xoption, it attempts to track references to external variables as well.
XThe names of functions and variables in a calling function are printed
Xonly once and in the order they occur.
X.P
XThe first reference to a function
X.I name
Xis printed with the name of the file
Xand line number where it is defined, i.e.,
X.sp
X.RS
Xname {file.c n},
X.RE
X.sp
Xor if
X.I name
Xis a variable:
X.sp
X.RS
Xname {v file.c n}.
X.RE
X.sp
XSubsequent references to
X.I name
Xare printed as:
X.sp
X.RS
Xname ... {mm},
X.RE
X.sp
Xwhere mm is the line number of
X.IR name 's
Xfirst occurrence in the call graph.
XExternal functions and variables are printed with a null source, i.e.,
X.sp
X.RS
Xname {}.
X.RE
X.sp
XAn ellipsis precedes the name of a function called recursively, e.g.,
X.sp
X.RS
X ... name ... {mm}
X.RE
X.SS OPTIONS
X.TP 20
X-a
XPrint a separate call graph for each function.
X.TP 20
X.BI -d nn
XPrint the call graph to at most depth
X.IR nn .
X.TP 20
X-g
XAdd to the list of C keywords GNU CC keywords.
X.TP 20
X-i
XPrint an inverted graph of depth 2, i.e., for each function (or
Xvariable if used with the
X.I \-v
Xoption), print a list of functions which call it.
X.TP 20
X.BI -r name
XPrint a call graph with function
X.I name
Xas root. This option may be repeated.
X.TP 20
X-v
XTry to track references to global variables in addition to function
Xcalls.
X.TP 20
X.BI -w nn
XPrint the graph to fit in
X.I nn
Xcolumns. The default is 132 columns.
X.TP 20
X-x
XPrint each sub-graph in full. This overrides the default format
Xwhere subsequent references are abbreviated as described above.
X.TP 20
X.BI -Dmacro
X.TP 20
X.BI -Umacro
X.TP 20
X.BI -Idir
XInvoke cpp with the corresponding options.
X
X.SH AUTHORS
XThe graph printing command
X.I prcg
Xis essentially the one in
XM. M. Taylor's
X.IR calls (1)
Xas posted to the Usenet newsgroup comp.sources.unix.
XA new parser,
X.IR prcc ,
Xis based on Steven Kirkendall's
X.IR ctags (1)
Xcommand which is distributed with the vi-clone
X.IR elvis (1).
X.br
X.SH BUGS
XAn extern variable declaration is overridden by an actual (global) variable
Xdeclaration. A complaint is written to stderr whether there is a conflict
Xor not.
X.P
XFunction parameters are ignored. If these parameters share the names
Xof global variables, then references to them are flagged as external
Xreferences.
X.P
XThe
X.I static
Xqualifier is ignored. Only the first definition of a function or
Xvariable is recognized.
END-of-calls.1
echo x - calls.sh
sed 's/^X//' >calls.sh << 'END-of-calls.sh'
X:
X# calls - print a function call hierarchy
X
XCPP="cc -E"
XPRCC=prcc
XPRCG=prcg
X
Xwhile getopts D:I:U:d:ir:vw:x c; do
X case $c in
X D)
X CPP="$CPP -D$OPTARG"
X ;;
X I)
X CPP="$CPP -I$OPTARG"
X ;;
X U)
X CPP="$CPP -U$OPTARG"
X ;;
X a)
X PRCG="$PRCG -a"
X ;;
X d)
X PRCG="$PRCG -d$OPTARG"
X ;;
X g) PRCC="$PRCC -g"
X ;;
X i)
X PRCG="$PRCG -i"
X invert=1
X ;;
X r)
X PRCG="$PRCG -r$OPTARG"
X ;;
X v)
X PRCC="$PRCC -v"
X ;;
X w)
X PRCG="$PRCG -w$OPTARG"
X ;;
X x)
X PRCG="$PRCG -x"
X ;;
X \?)
X echo "calls [-agivx] [-d n] [-r fn] [-w n] [cpp-opts] files" >&2
X exit 2
X ;;
X esac
Xdone
Xshift `expr $OPTIND - 1`
X
X[ X$1 = X ] && { echo "calls [options] files" >&2; exit 2; }
X
Xif [ X$invert = X ]; then
X $CPP $* |
X $PRCC |
X $PRCG
Xelse
X $CPP $* |
X $PRCC |
X sed 's/\(.* \)\(.* \)/\2\1/' |
X sort +0 -1 +2 |
X uniq |
X $PRCG
Xfi
END-of-calls.sh
echo x - sample.sh
sed 's/^X//' >sample.sh << 'END-of-sample.sh'
X:
X# This script prints the function call hierarchy of the 386BSD kernel source.
X# It creates three files in the working directory:
X# 386BSD-calls.sh - a script to parse the kernel source
X# 386BSD.t - table generated by 386BSD-calls.sh
X# 386BSD.g - graph of the kernel's function call hierarchy
X# To run it, create a kernel Makefile, i.e.,
X# $ cd /sys/i386/conf
X# $ config SYSTEM_NAME
X# $ cd /sys/compile/SYSTEM_NAME
X# $ make clean
X# $ make depend
X# Then copy this script to /sys/compile/SYSTEM_NAME and run it:
X# $ cp ~public/calls/sample.sh .
X# $ sh sample.sh
X
Xtrap 'rm -f 386BSD.t 386BSD.g 386BSD-calls.sh; exit 2' 1 2 3 15
X
X# make a script, 386BSD-calls.sh, to parse the 386BSD kernel source
Xecho ':' >386BSD-calls.sh
Xecho '# This script parses the 386BSD kernel source to 386BSD.t' >>386BSD-calls.sh
Xecho '>386BSD.t' >>386BSD-calls.sh
X#echo '>err.tmp' >>386BSD-calls.sh
Xmake -n |
Xsed '1,2d;/^echo/,$d;s/^cc[ ]\(.*$\)/cc -E \1 | prcc -gv >>386BSD.t 2>\/dev\/null/' \
X>>386BSD-calls.sh
X#sed '1,2d;/^echo/,$d;s/^cc[ ]\(.*$\)/cc -E \1 | prcc -gv >>386BSD.t 2>>err.tmp/' \
X#>>386BSD-calls.sh
X
X# run the parse script
Xsh 386BSD-calls.sh
X
X# print the parse graph
Xprcg <386BSD.t >386BSD.g
Xexpand -4 386BSD.g | more
X
X# or, print an inverted parse graph
X# sed 's/\(.* \)\(.* \)/\2\1/' 386BSD.t |
X# sort +0 -1 +2 |
X# uniq |
X# prcg -i >386BSD.ig
END-of-sample.sh
echo x - prcc.c
sed 's/^X//' >prcc.c << 'END-of-prcc.c'
X/* prcc.c: This file contains the parser for the calls command. */
X
X/* This program is a modification of Steve Kirkendall's ctags(1) which
X is distributed as part of his vi-clone elvis. */
X
X#include <stdio.h>
X#include <ctype.h>
X
X#ifdef __STDC__
X# include <string.h>
X# include <stdlib.h>
X#endif
X
X#ifndef FALSE
X# define FALSE 0
X# define TRUE 1
X#endif
X
X#ifndef PATH_MAX
X# define PATH_MAX 1024
X#endif
X
X#ifndef __P
X# ifndef __STDC__
X# define __P(proto) ()
X# else
X# define __P(proto) proto
X# endif
X#endif
X
Xtypedef struct ns /* name structure */
X{
X struct ns *next;
X char *name;
X} name_t;
X
X#define NAME_MAX 32 /* maximun identifier name length */
X#define TAG_MAX (NAME_MAX * 2 + PATH_MAX + 20) /* maximum tag length */
X#define TAG_STACKSIZE 20 /* tag stack size */
X
Xextern void complain __P((int));
Xextern int cpp_getc __P((void));
Xextern int cpp_open __P((char *));
Xextern int cpp_ungetc __P((int));
Xextern void ctags __P((void));
Xextern int file_getc __P((void));
Xextern int file_open __P((char *));
Xextern int file_ungetc __P((int));
Xextern void free_list __P((name_t **));
Xextern int lex_gettoken __P((void));
Xextern void main __P((int, char **));
Xextern void maketag __P((int, int));
Xextern int name_in_list __P((name_t *));
Xextern int name_from_list __P((name_t **));
Xextern int name_redefined __P((int));
Xextern int name_to_list __P((name_t **));
Xextern void per_file_cleanup __P((void));
Xextern void per_file_init __P((void));
Xextern int tag_pop __P((char *));
Xextern int tag_push __P((char *));
X
X/* -------------------------------------------------------------------------- */
X/* Some global variables */
X
X/* The following boolean variables are set according to command line flags */
Xint incl_vars; /* -v include variables */
Xint gnu_keywords; /* -g includes GNU keywords */
X
X/* -------------------------------------------------------------------------- */
X/* These are used for reading a source file. It keeps track of line numbers */
X
Xchar file_name[PATH_MAX]; /* name of the current file */
XFILE *file_fp; /* stream used for reading the file */
Xlong file_lnum; /* line number in the current file */
Xint file_afternl; /* boolean: was previous character a newline? */
Xint file_prevch; /* a single character that was ungotten */
X
X/* -------------------------------------------------------------------------- */
X
Xchar *usage = "usage: %s [-gv] file ...\n";
Xchar *pgm;
X
Xvoid
Xmain(argc, argv)
X int argc;
X char **argv;
X{
X extern int optind;
X extern char *optarg;
X
X int c;
X
X pgm = argv[0];
X
X /* parse the option flags */
X while ((c = getopt(argc, argv, "gv")) != EOF)
X switch (c)
X {
X case 'g':
X gnu_keywords = TRUE;
X break;
X case 'v':
X incl_vars = TRUE;
X break;
X default:
X fprintf(stderr, usage, pgm);
X exit(2);
X }
X argv += optind;
X do
X {
X /* can't open file */
X if (!cpp_open(*argv ? *argv++ : "-"))
X {
X break; /* least the error goes unnoticed */
X }
X
X /* initialize name lists */
X per_file_init();
X
X /* process file */
X ctags();
X
X /* free name lists */
X per_file_cleanup();
X } while (*argv);
X
X /* flush tag stack */
X maketag(0, 0);
X exit(0);
X /*NOTREACHED*/
X}
X
X
X/* -------------------------------------------------------------------------- */
X/* This is the parser. It locates tag candidates, and then decides
X whether to generate a tag for them. */
X
X/* These are C tokens after which a parenthesis is valid
X which would otherwise be tagged as function names. The
X reserved words which are not listed are break, continue,
X default and goto. */
Xchar *reserved[] =
X{
X "EXTERN", "FORWARD", "PRIVATE",
X "auto", "case", "char", "const", "do", "double", "else",
X "entry", "enum", "extern", "float", "for", "fortran",
X "if", "int", "long", "private", "register", "return", "short",
X "signed", "sizeof", "static", "struct", "switch", "typedef",
X "union", "unsigned", "void", "volatile", "while",
X 0
X};
X
Xchar *gnu_reserved[] =
X{
X "asm", "__asm__",
X "__const__",
X "__extension__",
X "inline", "__inline__",
X "__signed__",
X "typeof", "__typeof__",
X "__volatile__",
X};
X
X/* list of reserved words */
Xname_t *keyword;
X
Xenum lex_tokens /* token types */
X{
X DELETED,
X BODY,
X BODYEND,
X LBRACKET,
X RBRACKET,
X ARGS,
X ARGSEND,
X COMMA,
X SEMICOLON,
X COLON,
X KSTATIC,
X KEXTERN,
X KSTRUCT,
X KTYPEDEF,
X TYPESPEC,
X NAME,
X STRUREF,
X ASSIGN,
X OPERATOR
X};
X
X
X/* Basic types for initializing type specifier list */
Xchar *type[] =
X{
X "char", "double", "enum", "float", "int", "long", "short",
X "signed", "struct", "union", "unsigned", "void",
X 0
X};
X
X/* A type specifer list prevents declarations such as: int (*func())();
X from being parsed as calls */
Xname_t *type_specifier;
X
X/* A functions-previously-defined list assures that functions are defined
X only once. */
Xname_t *func_defined;
X
X/* A functions/variables-previously-called list assures that calls are
X printed only once per function definition. */
Xname_t *per_func_ref;
X
X/* Three variables lists to track global/extern/local variable
X declarations. */
Xname_t *variable;
Xname_t *extern_var;
Xname_t *per_func_var;
X
Xint gotname; /* boolean: does lex_name contain a tag candidate? */
Xint blockno; /* marks the extent of a scope */
Xint listno; /* marks the extent of a parameter list */
Xint func_seen; /* boolean: true if function is redefined */
X
X/* This function parses a source file and prints function calls. */
Xvoid
Xctags()
X{
X int initializer = FALSE; /* initialization list */
X int prev; /* the previous token from the source file */
X int token = SEMICOLON; /* the current token from the source file */
X int scope = 0; /* normally 0, but could be KTYPEDEF or KSTATIC */
X int scopeno = 0; /* block number upon entering a scope */
X int structdeclr = FALSE; /* struct/union/enum declaration */
X int structno = 0; /* block number upon entering struct */
X int typedeclr = FALSE; /* type declaration */
X
X /* reset */
X gotname = FALSE;
X
X /* parse until the end of the file */
X while (prev = token, (token = lex_gettoken()) != EOF)
X {
X /* scope keyword? */
X if (token == KTYPEDEF || token == KSTATIC || token == KEXTERN)
X {
X /* set scope */
X scope = token;
X scopeno = blockno;
X gotname = FALSE;
X continue;
X }
X
X /* type declaration */
X if (token == KSTRUCT || token == TYPESPEC)
X {
X typedeclr = TRUE;
X gotname = FALSE;
X continue;
X }
X
X /* (not STRUREF) NAME: NAME is tag? */
X if (token == NAME && prev != STRUREF && prev != KSTRUCT)
X {
X gotname = TRUE;
X continue;
X }
X
X /* ASSIGN BODY: initilizer */
X if (token == BODY && prev == ASSIGN)
X {
X gotname = FALSE;
X
X /* global */
X if (blockno == 1)
X {
X initializer = TRUE;
X }
X continue;
X }
X
X /* [NAME] BODY (no ARGS): struct declr [NAME is a struct tag] */
X if (token == BODY && prev != ARGS)
X {
X gotname = FALSE;
X
X /* not already in struct/union/enum */
X if (!structdeclr)
X {
X structno = blockno;
X }
X structdeclr = TRUE;
X continue;
X }
X
X /* NAME ARGS BODY: NAME is function */
X if (gotname && prev == ARGS && token == BODY)
X {
X gotname = FALSE;
X typedeclr = FALSE;
X structdeclr = FALSE;
X
X /* no name clash */
X if (!(func_seen = name_redefined(0)))
X {
X /* KSTATIC okay -- make a tag */
X maketag(scope, 0);
X }
X scope = 0;
X continue;
X }
X
X /* NAME ARGS in BODY (not global initializer):
X NAME is function call? */
X if (gotname && token == ARGS && blockno && !initializer)
X {
X gotname = FALSE;
X
X /* not function declaration */
X if (!typedeclr)
X {
X /* make a tag */
X maketag(scope, 1);
X }
X continue;
X }
X
X /* TYPE ARGSEND: type cast */
X if (typedeclr && !gotname && token == ARGSEND)
X {
X typedeclr = FALSE;
X continue;
X }
X
X
X /* KTYPEDEF NAME (not struct tag): new type specifier */
X if (gotname && scope == KTYPEDEF && !structdeclr)
X {
X gotname = FALSE;
X
X /* global */
X if (!blockno)
X {
X /* no name clash */
X if (!name_redefined(0))
X {
X /* add specifier to type list */
X name_to_list(&type_specifier);
X }
X }
X }
X
X
X /* TYPE NAME (no ARGS) [SEMICOLON,COMMA,ARGSEND,ASSIGN]:
X NAME is type declr */
X if (typedeclr && gotname && prev != ARGS && (token == SEMICOLON
X || token == COMMA || token == ARGSEND || token == ASSIGN
X || token == LBRACKET || token == OPERATOR))
X {
X gotname = FALSE;
X
X /* global */
X if (!blockno)
X {
X /* -v flag and not extern and (no name clash ||
X name only extern) [name on extern variable
X list is removed] */
X if (incl_vars && scope != KEXTERN
X && (!name_redefined(1) || name_in_list(extern_var)
X && name_from_list(&extern_var)))
X {
X /* make a tag */
X maketag(ASSIGN, 0);
X }
X /* (not -v flag || extern) && no name clash */
X else if ((!incl_vars || scope == KEXTERN)
X && !name_redefined(1))
X {
X /* add name to global variables list */
X name_to_list(&extern_var);
X }
X }
X /* not in struct/union/enum and no name clash */
X else if (!structdeclr && !name_in_list(per_func_var))
X {
X /* add name to per-function variables list */
X name_to_list(&per_func_var);
X }
X }
X
X /* (no TYPE) NAME in BODY (not global initializer):
X var/label reference */
X if (!typedeclr && gotname && blockno && !initializer)
X {
X gotname = FALSE;
X
X /* -v flag set and global variable reference */
X if (incl_vars && (name_in_list(variable) || name_in_list(extern_var)))
X {
X maketag(NAME, 0);
X }
X }
X
X /* delimiter */
X if (token == OPERATOR || token == ASSIGN || token == BODYEND
X || token == ARGSEND || token == COLON || token == COMMA
X || token == LBRACKET || token == RBRACKET)
X {
X gotname = FALSE;
X
X /* assignment */
X if (token == ASSIGN)
X {
X /* reset */
X typedeclr = FALSE;
X
X }
X
X /* body end and end of struct definition */
X if (token == BODYEND && structno == blockno + 1)
X {
X /* reset */
X structdeclr = FALSE;
X }
X
X /* end of global compound */
X if (token == BODYEND && !blockno)
X {
X /* reset */
X initializer = FALSE;
X func_seen = 0;
X free_list(&per_func_var);
X free_list(&per_func_ref);
X }
X continue;
X }
X
X /* semicolon */
X if (token == SEMICOLON)
X {
X /* reset */
X gotname = FALSE;
X typedeclr = FALSE;
X
X /* end of scope */
X if (scopeno == blockno)
X {
X scope = 0;
X }
X }
X
X /* The source file will be automatically closed */
X }
X}
X
Xchar lex_name[NAME_MAX]; /* the name of a "NAME" token */
X
X/* This function generates a tag for the object in lex_name */
Xvoid
Xmaketag(scope, iscall)
X int scope; /* 0 if global, or KSTATIC if static */
X int iscall; /* function call? */
X{
X static char caller_name[NAME_MAX]; /* name of caller function */
X char tag[TAG_MAX], buf[TAG_MAX]; /* tag buffers */
X
X /* external declaration or lex_name is a keyword */
X if (func_seen || scope == KEXTERN || name_in_list(per_func_ref))
X {
X /* whoa! never output tag for redefined function or
X an extern declr or keyword, and only output a tag
X for variable/call reference once per function */
X return;
X }
X
X /* global variable declaration */
X if (scope == ASSIGN)
X {
X /* add name to global variables list */
X name_to_list(&variable);
X }
X
X /* variable reference */
X else if (scope == NAME)
X {
X /* add lex_name to calls made in this function */
X name_to_list(&per_func_ref);
X }
X
X /* new function definition */
X else if (!iscall)
X {
X /* update caller function name */
X strcpy(caller_name, lex_name);
X
X /* add name to function defined list */
X name_to_list(&func_defined);
X }
X
X /* function call */
X else
X {
X /* add lex_name to references made in this function */
X name_to_list(&per_func_ref);
X }
X
X /* make tag */
X sprintf(tag, iscall ? "%s\t%s\t{}"
X : (scope == NAME) ? "%s\t%s\t{v}"
X : (scope == ASSIGN) ? "%s\t%s\t{v %s %ld}"
X : "%s\t%s\t{%s %ld}",
X (scope == ASSIGN) ? lex_name
X : caller_name, lex_name, file_name, file_lnum);
X
X /* nested call */
X if (listno)
X {
X /* push new tag onto tag stack */
X tag_push(tag);
X }
X
X /* function definition or first call in current expression */
X else
X {
X /* first call in expression */
X if (iscall)
X {
X listno = 1;
X }
X
X /* print tags from previous expression */
X while (tag_pop(buf))
X {
X printf("%s\n", buf);
X }
X
X /* push new tag onto tag stack */
X tag_push(tag);
X }
X}
X
Xchar *tag_stack[TAG_STACKSIZE];
Xint tag_sp = 0;
X
X/* pushes buffer onto tag stack */
Xtag_push(b)
X char *b;
X{
X if (tag_sp < TAG_STACKSIZE
X && (tag_stack[tag_sp] = (char *) malloc(strlen(b) + 1)) != NULL)
X {
X strcpy(tag_stack[tag_sp++], b);
X return 1;
X }
X return 0;
X}
X
X/* pops value off tag stack to buffer */
Xtag_pop(b)
X char *b;
X{
X if (tag_sp)
X {
X strcpy(b, tag_stack[--tag_sp]);
X free(tag_stack[tag_sp]);
X return 1;
X }
X return 0;
X}
X
X
X
X/* -------------------------------------------------------------------------- */
X/* This is the lexical analyser. It gets characters from the
X preprocessor, and gives tokens to the parser. Some special codes
X are...
X
X (deleted) / *...* / (comments)
X (deleted) //...\n (comments)
X (deleted) [...] (array subscript, when ... contains no ])
X BODY { ('{' can occur anywhere)
X BODYEND } (end of a body)
X LBRACKET [ ()
X LBRACKET ] ()
X ARGS ( (in function block, args of a function call)
X ARGSEND ) (end of args)
X ARGS (...{ (args of a function defintion --- ANSI or K&R)
X ARGS (...)...; (args of an extern/forward function declaration)
X ARGS (...)..., (args of an extern/forward function declaration)
X ARGS (...]..., (args of an extern/forward function declaration)
X COMMA , (separate declarations that have same scope)
X SEMICOLON ; (separate declarations that have different scope)
X KSTRUCT struct ()
X KSTRUCT union ()
X KSTRUCT enum ()
X KTYPEDEF typedef (the "typedef" keyword)
X KSTATIC static (the "static" keyword)
X KSTATIC private (the "static" keyword)
X KSTATIC PRIVATE (the "static" keyword)
X KEXTERN extern (the "extern" keyword)
X KEXTERN extern (the "extern" keyword)
X STRUREF . (direct structure reference operator)
X STRUREF -> (indirect structure reference operator)
X ASSIGN = (assignment operator, esp. initializer)
X OPERATOR (any constant or operator or part of an operator)
X TYPESPEC [a-z]+ (type specifier, including typedefs)
X NAME [a-z]+ (really any valid name that isn't reserved word) */
X
X/* returns token of next item in input */
Xlex_gettoken()
X{
X static int expanded = 0; /* boolean: ARGSEND expanded? */
X
X int ch; /* a character from the preprocessor */
X int oc; /* previous character from the preprocessor */
X int token; /* the token that we'll return */
X int lp = 0; /* lex_name index */
X
X /* loop until we get a token that isn't "DELETED" */
X do
X {
X /* process the character */
X switch (ch = cpp_nonwhite())
X {
X case ',':
X token = COMMA;
X break;
X
X case ';':
X token = SEMICOLON;
X break;
X
X case ':':
X token = COLON;
X break;
X
X case '\'':
X /* skip to matching '\'' */
X while ((ch = cpp_getc()) != '\'' && ch != EOF)
X {
X if (ch == '\\') ch = cpp_getc();
X }
X token = DELETED;
X break;
X
X case '\"':
X /* skip to matching '\"' */
X while ((ch = cpp_getc()) != '\"' && ch != EOF)
X {
X if (ch == '\\') ch = cpp_getc();
X }
X token = DELETED;
X break;
X
X case '(':
X /* entering list */
X if (listno) listno++;
X
X /* in block -- function call? */
X if (blockno)
X {
X token = ARGS;
X break;
X }
X
X /* indirect declarator or parenthized expression */
X else if ((ch = cpp_nonwhite()) == '*' || !gotname)
X {
X cpp_ungetc(ch);
X token = DELETED;
X break;
X }
X
X /* function declarator with parameter list */
X else if (ch != ')')
X {
X
X /* read past parameter list */
X for (lp = 1; lp && (ch = cpp_nonwhite()) != EOF;)
X {
X ch == '(' && lp++ || ch == ')' && lp--;
X }
X }
X
X /* read to end of declarator, i.e., past )...[](... */
X while ((ch = cpp_nonwhite()) == ')' || ch == '[' || ch == '(')
X switch (ch)
X {
X case '(':
X for (lp = 1; lp && (ch = cpp_nonwhite()) != EOF;)
X {
X ch == '(' && lp++ || ch == ')' && lp--;
X }
X break;
X case '[':
X for (lp = 1; lp && (ch = cpp_nonwhite()) != EOF;)
X {
X ch == '[' && lp++ || ch == ']' && lp--;
X }
X break;
X }
X
X /* type declarations following declarator */
X if (ch != ',' && ch != ';' && ch != '{')
X {
X /* read until ... ;{ */ /*}}}*/
X for (oc = ch; ((ch = cpp_nonwhite()) != '{'
X || oc != ';') && ch != EOF; oc = ch)
X ;
X }
X cpp_ungetc(ch);
X token = ARGS;
X break;
X
X case ')':
X /* expand ARGSEND to COMMA ARGSEND - allows
X proper handling of variable references at end
X of parameter lists */
X if (expanded)
X {
X /* leaving parameter list */
X expanded = 0;
X if (listno) listno--;
X token = ARGSEND;
X }
X else
X {
X expanded = 1;
X cpp_ungetc(ch);
X token = COMMA;
X }
X break;
X
X case '[':
X token = LBRACKET;
X break;
X
X case ']':
X token = RBRACKET;
X break;
X
X case '{':
X /* entering block */
X blockno++;
X token = BODY;
X break;
X
X case '}':
X /* leaving block */
X blockno--;
X token = BODYEND;
X break;
X
X case EOF:
X func_seen = 0;
X lex_name[0] = '\0';
X token = EOF;
X break;
X
X default:
X /* is this the start of a name/keyword? */
X if (isalpha(ch) || ch == '_')
X {
X /* collect the whole word */
X lex_name[0] = ch;
X for (lp = 1; (isalnum(ch = cpp_getc())
X || ch == '_') && lp < NAME_MAX - 1;)
X {
X lex_name[lp++] = ch;
X }
X lex_name[lp] = '\0';
X
X /* junk remainder of word */
X while (isalnum(ch) || ch == '_')
X {
X ch = cpp_getc();
X }
X cpp_ungetc(ch);
X
X /* is it a reserved word? */
X if (!strcmp(lex_name, "typedef"))
X {
X token = KTYPEDEF;
X }
X else if (!strcmp(lex_name, "static")
X || !strcmp(lex_name, "private")
X || !strcmp(lex_name, "PRIVATE"))
X {
X token = KSTATIC;
X }
X else if (!strcmp(lex_name, "extern")
X || !strcmp(lex_name, "EXTERN")
X || !strcmp(lex_name, "FORWARD"))
X {
X token = KEXTERN;
X }
X else if (!strcmp(lex_name, "struct")
X || !strcmp(lex_name, "union")
X || !strcmp(lex_name, "enum"))
X {
X token = KSTRUCT;
X }
X else if (name_in_list(type_specifier))
X {
X token = TYPESPEC;
X }
X else if (!name_in_list(keyword))
X {
X token = NAME;
X }
X else
X {
X token = DELETED;
X }
X }
X
X /* structure reference operator */
X else if (ch == '.')
X {
X token = STRUREF;
X }
X
X /* indirect reference or assignment operator? */
X else
X {
X token = OPERATOR;
X lp = cpp_getc();
X
X /* assignment (esp., initializer) */
X if (ch == '=' && lp != '=')
X {
X token = ASSIGN;
X cpp_ungetc(lp);
X }
X
X /* indirect reference */
X else if (ch == '-' && lp == '>')
X {
X token = STRUREF;
X }
X
X /* any other other operator or constant */
X else
X {
X cpp_ungetc(lp);
X }
X }
X
X } /* end switch(ch) */
X
X } while (token == DELETED);
X
X return token;
X}
X
X/* -------------------------------------------------------------------------- */
X/* This section handles preprocessor directives. It strips out all of the
X directives, and may emit a tag for #define directives. */
X
Xint cpp_afternl; /* boolean: look for '#' character? */
Xint cpp_prevch; /* an ungotten character, if any */
Xint cpp_refsok; /* boolean: can we echo characters out to "refs"? */
X
X/* This function opens the file & resets variables */
Xcpp_open(name)
X char *name; /* name of source file to be opened */
X{
X /* use the lower-level file_open function to open the file */
X if (file_open(name))
X {
X /* reset variables */
X cpp_afternl = TRUE;
X cpp_refsok = TRUE;
X return 1;
X }
X return 0;
X}
X
X/* returns next nonwhite-space character */
Xcpp_nonwhite()
X{
X int ch;
X int next;
X
X while ((ch = cpp_getc()) != EOF && (isspace(ch) || ch == '/'))
X if (ch == '/')
X switch (ch = cpp_getc())
X {
X case '*':
X ch = cpp_getc();
X next = cpp_getc();
X while (next != EOF && (ch != '*' || next != '/'))
X {
X ch = next;
X next = cpp_getc();
X }
X break;
X case '/':
X while ((ch = cpp_getc()) != '\n' && ch != EOF)
X ;
X break;
X default:
X cpp_ungetc(ch);
X return '/';
X }
X return ch;
X}
X
X
X/* This function returns the next character which isn't part of a directive */
Xcpp_getc()
X{
X int ch; /* the next input character */
X int i = 0;
X char buf[PATH_MAX]; /* path name of source file */
X char *scan;
X
X /* if we have an ungotten character, then return it */
X if (ch = cpp_prevch)
X {
X cpp_prevch = 0;
X return ch;
X }
X
X /* Get a character from the file. Return it if not special '#' */
X if ((ch = file_getc()) == '\n')
X {
X cpp_afternl = TRUE;
X return ch;
X }
X else if (ch != '#' || !cpp_afternl)
X {
X /* normal character. Any non-whitespace should turn off
X afternl */
X if (ch != ' ' && ch != '\t')
X {
X cpp_afternl = FALSE;
X }
X return ch;
X }
X
X /* Yikes! We found a directive */
X
X /* skip whitespace */
X while ((ch = file_getc()) == ' ' || ch == '\t')
X {
X ; /* do nothing */
X
X }
X
X /* # directive followed by a digit */
X if (isdigit(ch))
X {
X /* assert: directive of the form: # nn "filename" */
X
X /* update line number */
X file_lnum = ch - '0';
X while (isdigit(ch = file_getc()))
X {
X file_lnum = file_lnum * 10 + ch - '0';
X }
X
X /* adjust line number for newline of directive */
X file_lnum--;
X
X /* skip to path name */
X while ((ch = file_getc()) != '\"' && ch != EOF)
X {
X ; /* do nothing */
X }
X
X /* collect whole path */
X while ((ch = file_getc()) != '\"' && ch != EOF && i < PATH_MAX-1)
X {
X file_name[i++] = ch;
X }
X file_name[i] = '\0';
X }
X
X /* skip to the end of the directive -- a newline that isn't
X preceded by a '\' character. */
X while (ch != '\n' && ch != EOF)
X {
X if (ch == '\\')
X {
X ch = file_getc();
X }
X ch = file_getc();
X }
X
X /* return the newline that we found at the end of the directive */
X return ch;
X}
X
X
X/* This puts a character back into the input queue for the source file */
Xcpp_ungetc(ch)
X int ch; /* a character to be ungotten */
X{
X return cpp_prevch = ch;
X}
X
X/* -------------------------------------------------------------------------- */
X
X/* This function opens a file, and resets the line counter. If it fails, it
X it will display an error message and leave the file_fp set to NULL. */
Xfile_open(name)
X char *name; /* name of file to be opened */
X{
X /* if another file was already open, then close it */
X if (file_fp)
X {
X fclose(file_fp);
X }
X
X /* cannot open file */
X if (!(file_fp = !strcmp(name, "-") ? stdin : fopen(name, "r")))
X {
X perror(name);
X return 0;
X }
X
X /* reset the name & line number */
X strcpy(file_name, name);
X file_lnum = 0L;
X file_afternl = TRUE;
X return 1;
X}
X
X/* This function reads a single character from the stream. If the
X *previous* character was a newline, then it also increments
X file_lnum and sets file_offset. */
Xfile_getc()
X{
X int ch;
X
X /* if there is an ungotten character, then return it. */
X if (file_prevch)
X {
X ch = file_prevch;
X file_prevch = 0;
X return ch;
X }
X
X /* if previous character was a newline, then we're starting a line */
X if (file_afternl)
X {
X file_afternl = FALSE;
X file_lnum++;
X }
X
X /* Get a character. If no file is open, then return EOF */
X ch = (file_fp ? getc(file_fp) : EOF);
X
X /* if it is a newline, then remember that fact */
X if (ch == '\n')
X {
X file_afternl = TRUE;
X }
X
X /* return the character */
X return ch;
X}
X
X/* This function ungets a character from the current source file */
Xfile_ungetc(ch)
X int ch; /* character to be ungotten */
X{
X return file_prevch = ch;
X}
X
X/* -------------------------------------------------------------------------- */
X
X/* initialize per-file name lists */
Xvoid
Xper_file_init()
X{
X char **p;
X
X for (p = type; *p; p++)
X {
X /* add type to type specifier list */
X strcpy(lex_name, *p);
X name_to_list(&type_specifier);
X }
X
X for (p = reserved; *p; p++)
X {
X /* add reserved word to keyword list */
X strcpy(lex_name, *p);
X name_to_list(&keyword);
X }
X
X if (gnu_keywords)
X {
X for (p = gnu_reserved; *p; p++)
X {
X strcpy(lex_name, *p);
X name_to_list(&keyword);
X }
X }
X}
X
X/* free per-file name lists */
Xvoid
Xper_file_cleanup()
X{
X free_list(&type_specifier);
X free_list(&keyword);
X free_list(&variable);
X free_list(&extern_var);
X}
X
X/* check lex_name for (potential) name space conflict */
Xname_redefined(isvar)
X int isvar;
X{
X /* name redefined */
X if (name_in_list(func_defined) || name_in_list(type_specifier)
X || name_in_list(extern_var) || name_in_list(variable))
X {
X complain(isvar);
X return 1;
X }
X return 0;
X}
X
X
X/* add lex_name to a list; return 0 on error */
Xname_to_list(lp)
X name_t **lp; /* list pointer */
X{
X name_t *p;
X
X /* name structure and name buffer alloc'd */
X if ((p = (name_t *) malloc(sizeof(name_t))) != NULL
X && (p->name = (char *) malloc(strlen(lex_name) + 1)) != NULL)
X {
X /* initialize name structure */
X strcpy(p->name, lex_name);
X
X /* add structure to head of list */
X p->next = *lp;
X *lp = p;
X return 1;
X }
X return 0;
X}
X
X/* remove lex_name from a list; lex_name must be on list */
Xname_from_list(lp)
X name_t **lp; /* list pointer */
X{
X name_t *q, *p = *lp;
X
X if (strcmp((*lp)->name, lex_name) == 0)
X {
X *lp = (*lp)->next;
X free(p->name);
X free(p);
X }
X else
X {
X for (; strcmp(p->next->name, lex_name); p = p->next)
X ;
X q = p->next;
X p->next = p->next->next;
X free(q->name);
X free(q);
X }
X return 1;
X}
X
X
X/* return 1 if lex_name in list rl, otherwise 0 */
Xname_in_list(l)
X name_t *l;
X{
X for (; l; l = l->next)
X {
X if (!strcmp(lex_name, l->name))
X return 1;
X }
X return 0;
X}
X
X
X/* free a list's memory */
Xvoid
Xfree_list(lp)
X name_t **lp;
X{
X name_t *l = *lp;
X name_t *t;
X
X for (; l; l = t)
X {
X t = l->next;
X free(l->name);
X free(l);
X }
X *lp = NULL;
X}
X
Xvoid
Xcomplain(isvar)
X int isvar;
X{
X fprintf(stderr, isvar ? "%s: cannot redefine: %s\t{v %s %ld}\n"
X : "%s: cannot redefine: %s\t{%s %ld}\n", pgm, lex_name,
X file_name, file_lnum);
X}
END-of-prcc.c
echo x - prcg.c
sed 's/^X//' >prcg.c << 'END-of-prcg.c'
X/* This file contains code for building and printing a directed cyclic
X graph as part of the calls program. */
X
X/* ex:set sw=4: */
X/* Author: M.M. Taylor, DCIEM, Toronto, Canada.
X 22/Jan/81, Alexis Kwan (HCR at DCIEM).
X 12-Jun-84, Kevin Szabo
X 8/8/84, Tony Hansen, AT&T-IS, pegasus!hansen. */
X
X#include <stdio.h>
X#include <stdlib.h>
X#include <ctype.h>
X#include <string.h>
X
X#ifndef PATH_MAX
X# define PATH_MAX 1024 /* max pathname length */
X#endif
X#define NAME_MAX 32 /* max identifier length */
X#define BUF_MAX (NAME_MAX * 2 + PATH_MAX + 20) /* max line buffer length */
X#define DEPTH_MAX 200 /* max path length */
X#define TABSIZE 8 /* tab size */
X#define MARGIN 20 /* right margin of paper */
X#define PAPERWIDTH (14*TABSIZE + MARGIN) /* tabbing limits */
X
X
X/* name list node */
Xstruct name_node
X{
X struct name_node *next; /* next name list node */
X struct imm_node *imm_list; /* node's immediate list */
X long name_visited; /* set if node previously visited */
X int is_arc_head; /* set if node is an arc head */
X char *imm_name; /* name of first imm_list node */
X char *imm_ref; /* reference to first imm_list node */
X};
X
X/* immediate list node */
Xstruct imm_node
X{
X struct imm_node *next; /* next immediate list node */
X struct name_node *name_node_p; /* node's name node pointer */
X};
X
X/* forward declarations */
Xint active __P((struct name_node *));
Xint build_dcg __P((void));
Xint backup __P((void));
Xstruct imm_node *create_arc_node __P((char *, char *));
Xint get_arc __P((char *, char **, char **));
Xstruct imm_node *get_imm_node __P((void));
Xstruct imm_node *link_arc_node __P((char *, struct imm_node *));
Xint main __P((int, char **));
Xint makeactive __P((struct name_node *));
Xstruct name_node *name_to_nlist __P((char *, char *));
Xstruct name_node *nlist_contains __P((char *));
Xstruct imm_node *node_to_arc __P((struct name_node *, struct imm_node *));
Xint print_dcg __P((int, char **));
Xint print_name __P((struct name_node *, int));
X
X/* The name list (nlist) contains names (e.g., function/variable) in
X lexicographical order. Each name node has its own list (imm_list) of
X immediates (e.g., callers/callees). The immediate nodes do not
X themselves have names; instead, each node has a pointer to its name
X (node) in the name list. The nodes and pointers form the vertices and
X edges, respectively, of a directed cyclic graph (DCG).
X
X The prcg program builds a DCG by inserting names pairs from the input
X as arcs into the graph. Printing the DCG is done by a preorder
X traversal from a root name node. Paths are defined by the immediate
X list of the root name node, and, recursively, by the immediate lists
X of its immediates. */
Xstruct name_node *nlist; /* name list */
Xchar *dashes; /* separators for deep nestings */
X
X/* The following options are available :
X
X -a print a separate graph for each name (default: no)
X -d nn print graphs to at most depth `nn' (default: 200)
X -r root print graph only for `root' (default: each root name)
X -x print each sub-graph in full (default: no)
X -w nn print graph to fit in `nn' columns (default: 132 columns) */
X
X/* option flags */
Xint graph_all = 0; /* print a graph for each name */
Xint maxdepth = DEPTH_MAX; /* print to at most depth `maxdepth' */
Xint expand_all = 0; /* print each sub-graph in full */
Xint ntabs = ((PAPERWIDTH - MARGIN)/TABSIZE); /* how wide to go */
Xint select_roots = 0; /* print graph for selected names */
X
Xchar *arglist = "ad:r:ixw:"; /* valid options */
Xchar *usage = "usage: %s [-ax] [-d depth] [-r root] [-w paperwidth]\n";
Xchar *pgm; /* argv[0] */
X
Xmain(argc, argv)
X int argc;
X char *argv[];
X{
X extern char *optarg;
X extern int optind;
X
X register int c, i;
X register int width = PAPERWIDTH;
X
X pgm = argv[0];
X
X while ((c = getopt (argc, argv, arglist)) != EOF)
X switch (c)
X {
X case 'a':
X graph_all = 1;
X break;
X case 'd':
X if ((maxdepth = atoi(optarg)) > DEPTH_MAX)
X maxdepth = DEPTH_MAX;
X break;
X case 'i':
X expand_all = 1;
X graph_all = 1;
X maxdepth = 2;
X break;
X case 'r':
X select_roots = 1;
X break;
X case 'w':
X if ((width = atoi(optarg)) <= 0)
X width = PAPERWIDTH;
X break;
X case 'x':
X expand_all = 1;
X break;
X case '?':
X (void) fprintf (stderr, usage, pgm);
X exit (1);
X }
X ntabs = (width - MARGIN)/TABSIZE;
X
X /* initialize the dashed separator list for deep nesting */
X/* for (i = 0; (i < width) && (i < 1024); i += 2)
X {
X _dashes[i] = '-';
X _dashes[i+1] = ' ';
X }
X if (i < 1024)
X _dashes[i] = '\0';
X else
X _dashes[1023] = '\0';
X dashes = _dashes;
X*/
X build_dcg();
X print_dcg(argc, argv);
X exit(0);
X}
X
X/* Name pairs in the input are expected in blocks of the form:
X
X name1a --> name2aa
X name1a --> name2ab
X name1a --> name2ac
X .
X .
X .
X name1b --> name2ba
X name1b --> name2bb
X name1b --> name2bc
X .
X .
X .
X
X For a distinct name1, only the first block of name pairs is valid. A
X graph can be inverted by reversing the relation between name pairs,
X i.e., by putting name2 first:
X
X name2 --> name1
X
X Unless a block contains only a single name pair, then an initial
X name1-name1 pair is effectively ignored. A name1-name1 pair after the
X first represents a cycle - i.e., a node which points to itself. A
X block consisting of a single name1-name1 pair represents a non-cyclic,
X possibly disconnected, node. */
X
Xstruct imm_node *imm_tail; /* immediate list tail */
X
X/* Get name pairs from the input, and insert them as arcs to the DCG: an
X arc tail is the head of a linearly linked list (the immediate list) of
X arc heads to which it is connected (logically). */
Xbuild_dcg()
X{
X char arc_tail[BUF_MAX]; /* line buffer and arc tail name */
X char *arc_head; /* arc head name */
X char *arc_ref; /* arc reference */
X register int connected;
X
X while ((connected = get_arc(arc_tail, &arc_head, &arc_ref)) != -1)
X if (!connected)
X imm_tail = create_arc_node(arc_tail, arc_ref);
X else if (connected && imm_tail)
X imm_tail = link_arc_node(arc_head, imm_tail);
X else
X fprintf(stderr, "%s: cannot redefine: %s\n", pgm, arc_tail);
X}
X
X
Xchar tail_name[NAME_MAX] = ""; /* previous arc tail name */
X
X/* Read from stdin a name pair and a reference in the form
X `name1<tab>name2<tab>reference<newline>.' Return 1 if the tail of arc
X name1 --> name2 (i.e., name1) is the tail the previous arc,
X otherwise 0. */
Xget_arc(buf, ip, rp)
X char *buf;
X char **ip;
X char **rp;
X{
X
X /* line read and data format okay */
X if (fgets(buf, BUF_MAX, stdin) != NULL
X && (*ip = strchr(buf, '\t')) != NULL
X && (*rp = strchr(*ip + 1, '\t')) != NULL)
X {
X /* null-terminate name1 and name2 substrings */
X *(*rp)++ = *(*ip)++ = '\0';
X
X /* arc tail not previous tail */
X if (strcmp(buf, tail_name))
X {
X /* update arc tail name */
X strcpy(tail_name, buf);
X
X /* name pair is an arc (as opposed to a node) */
X if (strcmp(buf, *ip))
X {
X /* create an arc tail node */
X imm_tail = create_arc_node(buf, *rp);
X
X /* arc */
X return 1;
X }
X /* node */
X return 0;
X }
X /* arc */
X return 1;
X }
X /* eof */
X return -1;
X}
X
X
X/* Given a name (s), if it is not already on the name list, create a node
X for it there. Otherwise, retrieve the name list node. Create an arc
X tail (i.e., imm_list) node and link it to the new/retrieved name
X node (via the name node's imm_list pointer). Return a pointer to the
X arc tail node. */
Xstruct imm_node *
Xcreate_arc_node(s, t)
X char *s;
X char *t;
X{
X struct name_node *np;
X struct imm_node *ip;
X
X /* name already on name list */
X if (np = nlist_contains(s))
X {
X /* arc tail node installed && arc reference realloc'd */
X if ((ip = node_to_arc(np, (struct imm_node *) 0)) != 0
X && (np->imm_ref = realloc(np->imm_ref, strlen(t) + 1)) != NULL)
X {
X /* update arc reference */
X
X strcpy(np->imm_ref, t);
X return ip;
X }
X return (struct imm_node *) 0;
X }
X /* add name to name list and install arc tail node */
X return node_to_arc(name_to_nlist(s, t), (struct imm_node *) 0);
X}
X
X
Xchar *nil = " "; /* should be "", but 386BSD 0.1 bus errors XXX */
X
X/* Given a name (s), if it is not already on the name list, create a node
X for it there. Otherwise, retrieve the name list node. Create an arc
X head (i.e., imm_list) node and link it to the tail of the current
X immediate list. Return a pointer to the arc head node. */
Xstruct imm_node *
Xlink_arc_node(s, tail)
X char *s;
X struct imm_node *tail;
X{
X register struct name_node *p;
X register struct imm_node *ip = 0;
X
X /* (name already on name list or added name) and installed new arc
X and name != arc tail's name */
X if (((p = nlist_contains(s)) != 0 || (p = name_to_nlist(s, nil)) != 0)
X && (ip = node_to_arc(p, tail)) != 0 && strcmp(s, tail_name))
X p->is_arc_head = 1; /* arc head node */
X return ip;
X}
X
X/* Allocate memory for a name list node. Insert the node in the name
X list in lexicographical order by name. Return a pointer to the node. */
Xstruct name_node *
Xname_to_nlist(s, t)
X char *s;
X char *t;
X{
X register struct name_node *np, *p;
X
X /* name structure, name and arc reference alloc'd */
X if ((np = (struct name_node *) malloc(sizeof(struct name_node))) != 0
X && (np->imm_name = (char *) malloc(strlen(s) + 1)) != NULL
X && (np->imm_ref = (char *) malloc(strlen(t) + 1)) != NULL)
X {
X /* initialize name structure */
X strcpy(np->imm_name, s);
X strcpy(np->imm_ref, t);
X np->imm_list = (struct imm_node *) 0;
X np->is_arc_head = 0;
X np->name_visited = 0;
X
X /* no name list, or name less than head of name list */
X if (nlist == 0 || strcmp(nlist->imm_name, s) > 0)
X {
X /* add node to head of name list */
X np->next = nlist;
X nlist = np;
X }
X else
X {
X /* insert node in lexicographical order in name list */
X for (p = nlist; p->next; p = p->next)
X if (strcmp(p->next->imm_name, s) > 0)
X break;
X np->next = p->next;
X p->next = np;
X }
X return np;
X }
X return (struct name_node *) 0;
X}
X
X
X/* Create an immediate node (imm_p) with a pointer (name_node_p) to its
X name list node (np). If the given immediate list pointer (ip) is NULL,
X the new immediate node is an arc tail, and it is pointed to by its
X name list node. Otherwise, the new immediate node is an arc head and
X is linked after the given immediate list pointer. Return a pointer to
X the new immediate node. */
Xstruct imm_node *
Xnode_to_arc(np, ip)
X struct name_node *np;
X struct imm_node *ip;
X{
X register struct imm_node *imm_p;
X
X /* null name or (dummy && an immediate exists) or null immediate */
X if (np == 0 || (!ip && np->imm_list) || (imm_p = get_imm_node()) == 0)
X return (struct imm_node *) 0;
X imm_p->name_node_p = np;
X return ip ? (ip->next = imm_p) : (np->imm_list = imm_p);
X}
X
X/* Return pointer to alloc'd and initialized immediate node. */
Xstruct imm_node *
Xget_imm_node()
X{
X register struct imm_node *rp;
X
X /* immediate node alloc'd */
X if ((rp = (struct imm_node *) malloc(sizeof(struct imm_node))) != 0)
X {
X /* initialize immediate node */
X rp->next = (struct imm_node *) 0;
X return rp;
X }
X return (struct imm_node *) 0;
X}
X
X/* Preorder traverse the DCG, printing the names of nodes as they
X are visited. */
Xprint_dcg(argc, argv)
X int argc;
X char **argv;
X{
X register int c;
X register struct name_node *root_p;
X
X /* root node(s) specified */
X if (select_roots)
X
X /* restart argument list; print only specified names */
X for (optind = 1; (c = getopt(argc, argv, arglist)) != EOF;)
X {
X if (c == 'r')
X if (root_p = nlist_contains(optarg))
X print_name(root_p, 1);
X else
X (void) fprintf (stderr, "%s: not found: %s\n", pgm, optarg);
X }
X else
X
X /* print_name everything */
X for (root_p = nlist ; root_p; root_p = root_p->next)
X if (graph_all || !root_p->is_arc_head)
X print_name(root_p, 1);
X}
X
X
X/* Print one tab for each level of recursion, then the name of an unvisited
X immediate. Go to the immediate's immediate list and, recursively,
X print the name of an unvisited immediate. When the current path is
X exhausted, back track to an immediate list with unvisited nodes and
X continue with the next unvisited immediate.
X
X While travering the DCG, maintain an active list of nodes in the current
X path. If an active node is revisited, terminate the path and print a
X `cycle' mark. */
Xprint_name(node, tabc)
X struct name_node *node;
X int tabc;
X{
X static long line = 0; /* line number */
X
X register int i, tabd, tabstar, tflag;
X register struct imm_node *imm_p;
X
X if (tabc > maxdepth)
X return;
X printf ("%ld", ++line);
X if (!makeactive(node))
X printf (" * nesting is too deep\n");
X else
X {
X tabstar= 0;
X tabd = tabc;
X for ( ; tabd > ntabs; tabstar++)
X tabd = tabd - ntabs;
X if (tabstar > 0)
X {
X printf (" ");
X for (i = 0 ; i < tabstar ; i++ )
X printf ("<");
X }
X if (tabd == 0)
X printf (" ");
X else
X for (i = 0 ; i < tabd ; i++ )
X printf ("\t");
X
X /* cycle found */
X if (active(node))
X printf ("... %s ... {%ld}\n", node->imm_name, node->name_visited);
X else
X {
X if (node->imm_list)
X {
X printf ("%s", node->imm_name);
X imm_p = node->imm_list->next;
X if (expand_all || !node->name_visited)
X {
X printf (" %s", node->imm_ref);
X ++tabc;
X if (!node->name_visited)
X node->name_visited = line;
X/* if (tabc > ntabs && tabc%ntabs==1 && imm_p)
X {
X printf("%s\n", dashes);
X tflag = 1;
X }
X else
X tflag = 0;
X*/
X for (; imm_p; imm_p = imm_p->next)
X print_name(imm_p->name_node_p, tabc);
X/* if (tflag)
X {
X printf("%s\n", dashes);
X tflag = 0;
X }
X*/
X }
X else
X printf(" ... {%ld}\n", node->name_visited);
X }
X /* library or external call */
X else
X printf("%s {}\n", node->imm_name);
X }
X backup ();
X }
X return;
X}
X
Xstruct name_node *active_node[DEPTH_MAX]; /* current path */
Xint active_p = 0; /* current path size */
X
X/* makeactive simply puts a pointer to the nameblock into a stack with
X maximum depth DEPTH_MAX. the error return only happens for stack
X overflow. */
Xmakeactive(node)
X struct name_node *node;
X{
X if (active_p < DEPTH_MAX)
X {
X active_node[active_p] = node;
X active_p++;
X return 1;
X }
X return 0;
X}
X
X/* backup removes an item from the active stack */
Xbackup()
X{
X if (active_p)
X active_node [active_p--] = 0;
X}
X
X/* active checks whether the pointer which is its argument has already
X occurred on the active list, and returns 1 if so. */
Xactive(node)
X struct name_node *node;
X{
X register int i;
X
X for (i = 0; i < active_p-1 ; i++)
X if (node == active_node[i])
X return 1;
X return 0;
X}
X
X/* accepts a pointer to a name and sees if the name is on the name list.
X If so, it returns a pointer to the nameblock. Otherwise it returns
X zero. If the name from argv is > NAME_MAX-1, then it is truncated. */
Xstruct name_node *
Xnlist_contains(s)
X char *s;
X{
X register struct name_node *np = nlist;
X
X if (strlen(s) > NAME_MAX - 1)
X s[NAME_MAX - 1] = '\0';
X
X for (np = nlist; np; np = np->next)
X if (strcmp (s, np->imm_name) == 0)
X return np;
X return 0;
X}
END-of-prcg.c
echo x - Makefile
sed 's/^X//' >Makefile << 'END-of-Makefile'
X# @(#)Makefile 5.2 (Berkeley) 1/11/92
X
XPROG= calls
XCFLAGS=-g
XSRCS= prcc.c prcg.c
XINSTALL=-c
XDESTDIR=/usr/local/bin/
XMANDIR= /usr/local/man/cat1/
XBINMODE=555
XBINOWN= bin
XBINGRP= bin
X
X${PROG}: prcg prcc calls.sh
X cp ${PROG}.sh ${PROG}
X nroff -mandoc ${PROG}.1 >${PROG}.0
X
Xprcg: prcg.o
X ${CC} ${CFLAGS} -o $@ $>
X
Xprcc: prcc.o
X ${CC} ${CFLAGS} -o $@ $>
X
Xinstall: installprog installman
X @:
X
Xinstallprog: ${PROG} prcg prcc
X install ${INSTALL} -m ${BINMODE} -o ${BINOWN} -g ${BINGRP} \
X $> ${DESTDIR}
X
Xinstallman: ${PROG}.0
X install ${INSTALL} -m ${BINMODE} -o ${BINOWN} -g ${BINGRP} \
X $> ${MANDIR}
X
Xclean:
X rm -rf *.tmp core.* ${PROG}{,.o,.0} prcc{,.o} prcg{,.o}
X
Xshar:
X shar *.{1,sh} prcc.c prcg.c Makefile >calls.shar
END-of-Makefile
exit