trerules.c

这是一个C程序分析工具

/*************************************************************
   Copyright (c) 1993-1995 by Paul Long  All rights reserved.
**************************************************************/

/*************************************************************
   trerules.c  This source file contains a set of rules for
               the MTREE call-hierarchy tool.
**************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "metre.h"


/* Manifest constants. */

/* Function from which to build call tree if not main or first function. */
#define ROOT_FUNC_OPT_CHAR    'r'
/* Number of columns to indent for each level. */
#define INDENTION_OPT_CHAR    'c'
/* Use alternate graphic characters for tree lines. */
#define ALT_GRAPH_OPT_CHAR    'g'
/* Don't print tree lines. */
#define NO_GRAPH_OPT_CHAR     'n'
/* Print table of contents? */
#define TOC_OPT_CHAR          't'
/* Ignore library calls? */
#define IGNORE_LIB_OPT_CHAR   'l'
/* Width allotted to file-name section in left margin. */
#define FILE_WIDTH_OPT_CHAR   'm'

/* Number of columns to indent if not specified or in error. */
#define DEFAULT_INDENTION  4
#define DEFAULT_FILE_WIDTH 12

#define GREATEST_STRING "~"

#define TOC_INDENT               4
#define DOT_SPACES_RIGHT_MARGIN  70

/* Defines for diagnostics that are generated by the rules, not the parser. */
#define F_MEMORY           0, "Out of memory"
#define F_INTERNAL         1, "Internal error"
#define W_DUP_FUNC         0, "Duplicate function definition for %s ignored"
#define W_NO_FUNCS         1, "No functions from which to build call tree"
#define W_FUNC_NOT_FOUND   2, "%s not found; using %s"
#define W_INDENTION        3, "Invalid indention specified; using %d"

#define DIM_OF(x)          (sizeof (x) / sizeof (x[0]))

/* Characters used for tree lines. */
#define PRI_T_CHAR    '+'     /* ASCII characters. */
#define PRI_HORZ_CHAR '-'
#define PRI_VERT_CHAR '|'
#define PRI_TURN_CHAR '`'
#define ALT_T_CHAR    '\303'  /* IBM graphic characters. */
#define ALT_HORZ_CHAR '\304'
#define ALT_VERT_CHAR '\263'
#define ALT_TURN_CHAR '\300'

/* Whether call location is recorded. (Location currently not used.) */
#define CALL_LOCATION   FALSE


/* Structure definitions. */

/*
   Represents a function call in the list of calls attached to each
   function structure.
*/
typedef struct call {
   struct call *next;
   char *name;
#if CALL_LOCATION
   char *file;
   unsigned line;
#endif
} CALL;

/* Represents a function definition. */
typedef struct function {
   struct function *next;
   char *name;
   char *file;
   unsigned line;
   CALL *calls;               /* List of functions that are called from
                                 within this function. Only one entry
                                 per function regardless of how many
                                 times it is called. */
   BOOLEAN visited;           /* Has this function definition been
                                 visited? Used to detect secondary
                                 roots after the main tree has been
                                 printed. */
} FUNCTION;

/*
   Represents a stack frame in the call hierarchy. Used to determine
   recursive calls.
*/
typedef struct frame {
   struct frame *next;
   FUNCTION *function;
   BOOLEAN last_call;         /* Is the call that this represents the
                                 last entry in the calling function's
                                 call list? Used for drawing tree
                                 diagram.
                              */
} FRAME;


/* Function prototypes for local functions. */

static void check_options(void);
static void print_trees(void);
static void consider_function(void);
static void add_function(void);
static void consider_call(void);
static FUNCTION *get_root(void);
static void print_calls(FUNCTION *);
static void print_call_line(FUNCTION *);
static void print_tree_line(FRAME *);
static void push_call(FUNCTION *);
static BOOLEAN is_last_call(FRAME *, char *);
static void pop_call(void);
static BOOLEAN recursive_call(FUNCTION *);
static void print_toc(void);
static void print_toc_dots(char *);
static int cmpstr(const char *, const char * const *);
static BOOLEAN library_call(char *);
static void print_indent(int, int);
static FUNCTION *lookup_function(FUNCTION *, char *);


/* Local data definitions. */

/* Head of linked list of function definitions. */
static FUNCTION *functions = NULL;

/*
   Pointer to the structure of the function currently being parsed
   which is always at the end of the functions linked list.
*/
static FUNCTION *current_function = NULL;

/* Head of call stack; used for detecting recursion. */
static FRAME *stack = NULL;

/* Number of columns to indent in tree for each call level. */
static unsigned indention;

/* "Graphical" characters to use when drawing call tree. */
static char t_char, horz_char, vert_char, turn_char;

/* Whether to ignore calls to Standard C library functions. */
static BOOLEAN ignore_library_calls;

/*
   Width of tree left margin within which is printed the name of the
   file within which each function is defined. 
*/
static unsigned file_width;

/*
   Line on which the last declaration occured. Used for determining on
   what line a function is defined.
*/
static unsigned last_decl_lineno = 0;

/* Has function definition already been encountered with this name? */
static BOOLEAN duplicate_function = FALSE;


/* Function definitions. */

/* Set of rules that define the behavior of this call-hierarchy tool. */
void rules(void)
{
   /* Whether we are within a function definition. */
   static BOOLEAN is_within_function = FALSE;

   if (prj.need_cmd_name)
      cmd_name("MTREE");

   /* Addendum to main help info when -h is specified. */
   if (prj.help)
   {
      fprintf(out_fp, "-%cxxx       Root function name         "
             "-%cN         Indent columns per level [%d]\n",
            ROOT_FUNC_OPT_CHAR, INDENTION_OPT_CHAR, DEFAULT_INDENTION);
      fprintf(out_fp, "-%c          Alternate-character tree   "
             "-%c          Print table of contents\n",
            ALT_GRAPH_OPT_CHAR, TOC_OPT_CHAR);
      fprintf(out_fp, "-%c          No tree                    "
             "-%c          Ignore library calls\n",
            NO_GRAPH_OPT_CHAR, IGNORE_LIB_OPT_CHAR);
      fprintf(out_fp, "-%cN         File name margin [%d]\n",
            FILE_WIDTH_OPT_CHAR, DEFAULT_FILE_WIDTH);
   }

   /* Project initialization. Check starting command-line options. */
   if (prj.begin)
      check_options();

   /* Generate output. */
   if (prj.end)
      if (functions == NULL)
         warn(W_NO_FUNCS);
      else
      {
         /* Print primary and secondary call trees. */
         print_trees();

         /* Optionally print table of contents. */
         if (option(TOC_OPT_CHAR))
            print_toc();
      }

   /* Function definition. */
   if (fcn.begin) {
      consider_function();

      is_within_function = TRUE;
   }

   if (fcn.end)
      is_within_function = FALSE;

   /*
      Is this what appears to be a function call (not simply a macro
      invokation outside a function definition) that is not within a
      duplicate function definition? If so, if this is a library call,
      am I supposed to ignore it?
   */
   if (grm.is_call && is_within_function && !duplicate_function &&
         !(ignore_library_calls && library_call(last_identifier())))
      consider_call();

   /*
      Remember line on which every base-level declarator is declared in
      case we learn later that it is a function definition.
   */
   if (grm.is_declarator)
      last_decl_lineno = lineno();
}

/* Check starting command-line options. */
static void check_options(void)
{
   char *indention_str;
   char *file_width_str;

   /*
      Get width of left margin within which file names are printed.
      Zero means do not print file names at all.
   */
   if ((file_width_str = str_option(FILE_WIDTH_OPT_CHAR)) == NULL)
      file_width = DEFAULT_FILE_WIDTH;
   else
      file_width = atoi(file_width_str);

   ignore_library_calls = option(IGNORE_LIB_OPT_CHAR);

   /*
      Get how many columns to indent in the tree diagram for each
      call level.
   */
   if ((indention_str = str_option(INDENTION_OPT_CHAR)) == NULL)
      indention = DEFAULT_INDENTION;
   else if ((indention = atoi(indention_str)) < 1)
      warn(W_INDENTION, indention = DEFAULT_INDENTION);

   /* Determine which set of "line" characters to use for the call tree. */
   if (option(NO_GRAPH_OPT_CHAR))
      /* No tree */
      t_char = horz_char = vert_char = turn_char = ' ';
   else if (option(ALT_GRAPH_OPT_CHAR))
   {
      /* Use alternate character set (IBM graphic characters). */
      t_char      = ALT_T_CHAR;
      horz_char   = ALT_HORZ_CHAR;
      vert_char   = ALT_VERT_CHAR;
      turn_char   = ALT_TURN_CHAR;
   }
   else
   {
      /* Use ASCII characters to simulate lines. */
      t_char      = PRI_T_CHAR;
      horz_char   = PRI_HORZ_CHAR;
      vert_char   = PRI_VERT_CHAR;
      turn_char   = PRI_TURN_CHAR;
   }
}

/* Print call tree for primary and secondary roots. */
static void print_trees(void)
{
   FUNCTION *function;

   /* Print the primary, possibly only, call tree. */
   fprintf(out_fp, "\nCall Hierarchies\n");
   print_calls(get_root());
   fprintf(out_fp, "\n");

   /*
      For each function that was not part of primary tree, print its
      tree. This is intended for libraries without a single root.
   */
   for (function = functions; function != NULL; function = function->next)
      if (!function->visited) {
         print_calls(function);
         fprintf(out_fp, "\n");
      }
}

/* If not a duplicate function definition, add it to the functions list. */
static void consider_function(void)
{
   /*
      Search for a function that has the same name as this one.
      Remember so can ignore calls within this function.
   */
   duplicate_function = lookup_function(functions, fcn_name()) != NULL;

   /* If duplicate definition, print warning and ignore. */
   if (duplicate_function)
      warn(W_DUP_FUNC, fcn_name());
   else
      add_function();
}

/* Add current function to functions list. */
static void add_function(void)
{
   FUNCTION *function;

   if ((function = (FUNCTION *)malloc(sizeof *function)) == NULL)
      fatal(F_MEMORY);

   /* Add this function to the list of functions. */
   if (functions == NULL)
      functions = function;
   else
      current_function->next = function;
   current_function = function;
   current_function->next = NULL;

   /*
      Attach buffers containing function name and file name to function
      structure.
   */
   current_function->name = (char *)malloc(strlen(fcn_name()) + 1);
   if (current_function->name == NULL)
      fatal(F_MEMORY);

   strcpy(current_function->name, fcn_name());

   current_function->file = (char *)malloc(strlen(mod_name()) + 1);
   if (current_function->file == NULL)
      fatal(F_MEMORY);

   strcpy(current_function->file, mod_name());

   /*
      Line on which this function is defined (line on which identifier
      appears).
   */
   current_function->line = last_decl_lineno;

   current_function->calls = NULL;
   current_function->visited = FALSE;
}

/* If not a duplicate call from within the current function, add it to list. */
static void consider_call(void)
{
   CALL *temp_call, *prev_call;

   assert(current_function != NULL);
   assert(last_identifier() != NULL);

   /* Search for a call to the same function as this call. */
   for (temp_call = current_function->calls, prev_call = NULL;