added missing files to MANIFEST

[deps.git] / README

                graph-includes toolkit
                ======================

IN SHORT
--------

Graph-includes creates a graph of dependencies between source-files
and/or groups of source-files, with an emphasis on getting readable
and usable graphs even for large projects.

Usability of the dependency graphs are currently improved by:
- customizable grouping of several source files into a single node
- transitive reduction of the graph

It currently supports graphing the C/C++ #include relationship, using
graphviz.


IMPORTANT NOTICE
----------------

This tool has evolved from a 50-line script written for a particular
project (Battle for Wesnoth).  Although it has been generalized much,
there are still somewhat ad-hoc heuristics harcoded here and there,
especially in the default project class (see class descriptions below).

Although work is under way to make this tool as generic as possible,
work still has to be done at all levels.  It is still under
development, and may not suit your needs (at least, not yet).


INSTALLATION INSTRUCTIONS
-------------------------

Like standard perl packages.  Eg:

$ perl Makefile.PL prefix=/usr/local
$ make
$ su
# make install


New versions can be found at http://ydirson.free.fr/soft/graph-includes/.


HOW TO TAKE ADVANTAGE OF THIS TOOL TO IMPROVE YOUR CODE
-------------------------------------------------------

1. on the spirit of dependency cleanup

When developping a project of medium size (we'll talk mostly C/C++
here, but that will apply to most languages), expecially with many
people writing code, it is quite easy to get to a point where each
file (out of several tens of hundreds of files) depends on too many
other files.

The most obvious relation is the #include one.  The more #includes a
file has, the more time it takes to build - especially when those
included files #include themselves a bunch of other files.  For a
project of about 100 files, just producing a graph of all those files,
with arrows representing the #include dependencies, will usually give
an unreadable graph, and will show very little about possible
improvements.

A less obvious relation appears more clearly when you consider not
files by themselves, but the set of files made of an interface and the
matching implementation.  Let's consider two such sets, made of the
files a.h, a.c, b.h, b.c.  a.c includes b.h, and b.c includes a.h, and
each implementation, following good practice, includes its own
interface.  A simple dependency graph as described above would show
such a graph:

        a.c -> b.h              
           \  /|
            \/
            /\
           /  \|
        b.c -> a.h

If OTOH we represent those sets of files instead of the files
themselves, we now have something like:

        a <--> b

This shows much more clearly that those two modules are intrinsicately
related.  In many cases, this will express that whenever you use the
a.o file resulting from the build of a.c, you'll need to link b.o as
well, and vice versa.  This will be the case when each file uses the
headers to get function prototypes.  Then hunting for abusive
dependencies will allow, for example, to select with finer grain which
of those modules of code will need to go into which executable, thus
producing lighter executables.

In other cases, headers would just have been used to access a type
definition from b.h, and the associated b.o would not be needed.  In
such cases, you may want to consider splitting such "low-level"
declarations into their own headers.  Not only this would simplify the
graph, allowing you to get a better grasp on your source code, but it
can also lead to faster compilations, since each file will be able
include less unrelated definitions.


2. possible strategies to help locating abusive dependencies

More to be written.



COMMAND-LINE USAGE
------------------

See "graph-includes --help".

1. output type

The default output is a .dot file on standard output, suitable for
formatting by dot (from the graphviz toolkit), or interactive editing
by dotty (also from graphviz).

You can ask graph-includes to do the formatting for you, eg. using
"--output=<file>.<suffix>".  It will run "dot -T<suffix>", so that
"--output=mydeps.ps" or "--output=mydeps.jpg" will have the expected
behaviour.  If your suffix is not known to dot, it will complain
itself, so asking for --output=foo.bar will cause a message like:

Warning: language bar not recognized, use one of: canon cmap cmapx dia dot fig gd gd2 gif hpgl imap ismap jpeg jpg mif mp pcl pic plain plain-ext png ps ps2 svg svgz vrml vtx wbmp xdot

If you intend to print the result on paper, the default layout will
likely be too large.  You can use --paper=a4 to select parameters that
will produce a smaller graph and spilt it into pages.  This flag also
changes the default output format to postscript.  Be warned that dot
may not honor the page-splitting parameter for all output formats.

Since the transitive reduction can take time, you may like the
--verbose switch, which will show a progress bar.


2. what to draw

The files to be analyzed are given as non-option arguments, and are
typically generated by a "find" command.  Eg:

        $ graph-includes `find src -name '*.[ch]'`

In order to tell the #include resolver where to look for included
files, you can use the cpp-like -I (aka. --Include) flag.  Eg:

        $ graph-includes -I src `find src -name '*.[ch]'`

Dependencies not found in the project (ie. files appearing in #include
but not given on command-line) are listed as "not found" in the
graph-includes.report file for diagnostics purposes, unless they are
found in a system directory.  System directories are declared in a
similar fashion, with the --sysInclude option.  Eg:

        $ graph-includes -I src -sysI /usr/include `find src -name '*.[ch]'`

To avoid having useless information on the graph,
--prefixstrip=<prefix> can be used to avoid repeating a given prefix
in all node labels.  Typically:

        $ graph-includes --prefixstrip=src/ `find src -name '*.[ch]'`

Files will be grouped in a hierarchy of groups, level 0 groups
typically containing just one file.  Groups are defined by the
selected project class, selected by the --class=<class> option.  See
below for descriptions of the project classes available by default,
and for instructions to write customized project classes.

The range of group levels to be drawn is selected with
--group=<min>-<max>, which defaults to 1-1.  Eg, for class "default",
whose group levels are defined as:

0: one file per group
1: what/ever.* go into a "what/ever" group (usually interface + implementation)
2: what/* go into a "what" group, supposing directories denote modules of some sort

Group levels below "min" or above "max" are not displayed as nodes.
Groups of level "min" are drawn as nodes of the graph.  If "max" is
strictly greater than "min", then groups of levels "min+1" through
"max" are drawn as box clusters containing lower-level groups.

Since such a way of grouping nodes will not improve the readability in
projects where the inter-groups dependencies have not been cleaned up
yet, higher-level groups can instead be colored, using a class-defined
color scheme, possibly modified by "--color <n>:<label>=<color>[,<label>=<color>...]"
options, where <n> is the group level in which the group name <label> will
receive a background of the specified color, which can be defined
either by a named X11 color (like "blue" or "palegreen"), or by a RGB
color using the standard X11 "#RRGGBB" syntax.


For those wanting to see what edges the transitive reduction dropped,
the --showdropped will add them to the graph in a different color.  Be
prepared for your computer room to get a noticeable temperature
increase for anything else than a small set of files with only few
dependencies.

OTOH, --focus=<node-label> will do the same, but only for the
dependencies of a specified node.  That should prevent the nasty
effects described above, and will be useful for various purposes,
including debugging the transitive reducer.  The node-label refers to
a node in the lowest group-level drawn, ie. the "min" argument to
--group.

People still getting cold may also like to circumvent the
transitive-reduction engine completely, using --alldeps.  The author
assumes no responsibility for losses of mental health induced by
trying to make any serious use of the resulting graph.


EXISTING PROJECT CLASSES
------------------------

1. class "default"

As implied by its name, it is the one which will be used unless you
use the --class option.  Although it is the default one, it may still
be quite rough at the moment, still using some ad-hoc heuristics, and
will be improved in the near future.  Here are its main
characteristics:

 - looks at C-style #include lines
 - creates level-1 groups for all files sharing the same path and
   (disregarding the suffix) filename.  Eg, files "foo/bar.c" and
   "foo/bar.h" would be grouped in a "foo/bar" level-1 group.
   In clear, it won't connect include files if they are all located
   in an include/ directory.
 - creates by-directory level-2 groups.  Eg. in the above example, a
   group "foo" would exist at level-2.


2. class "uniqueincludes"

Built on top of the default class, it is meant for projects where file
names are kept unique across all directories.  If the ad-hoc #include
processing of the default class does not suit your project, it is the
only out-of-the-box alternative available today.  Here are its main
characteristics:

 - provides a single grouping level based on filenames, disregarding
   all the directory hierarchy.

Note that it is not meant for general use, as:

 - it will group any files with the same name in the same level-0
   group, possibly causing confusion.
 - it does not make any directory name appear in the node names


DEFINING YOUR OWN PROJECT CLASS
-------------------------------

See graphincludes::project::wesnoth in the examples/ dir as an example.

Keep in mind that the API is not frozen yet, and will probably be
overhauled more than once before an official API gets blessed.


CAVEATS
-------

- this script only handles explicitely-declared dependencies, it
  won't detect it if eg. a prototype cut'n'paste was used instead of
  using the correct #include, but you shouldn't do that anyway :)


TODO
----

- misc improvements
 - automate --help production (see Pod::Usage ?)
 - make default project-class consider multiple levels of directories
   as group levels, but only if they (consistently ?) have multiple
   subgroups ?
 - write more documentation
 - continue merging the verbose/debug behaviour into the global report file.
 - write a linux-kernel class as example :)
 - use an existing source of paper formats (libpaper, LC_PAPER, whatever)
 - find out how to use this damn Exporter mechanism for
   graphincludes::params, or find another way of getting rid of those
   "used only once" warnings.
 - maybe use graphviz' tred(1) to check our transitive reductions.
 - write a testsuite.
- modularization (finish the restructuring into a cleaner and more modular design)
  + allow coloring other things than just level 2
  - write a perl extractor
  - graph output syntax (allow to generate tulip graphs)
  - provide a simple hash-based filelabel implementation
  + find the accessory classes as easily as possible (like nagios-plugins ?)
  - separate styling from project classes
  - allow to define several views in a project-class, several of which
    can be generated by default.
  - find out whether we can declare protocols/pure-virtual-classes in
    some way, to cleanup the class graph
  - generalize --prefix-strip
  - give consistent access to all commonly-needed features through
    command-line and class customization
  - ensure in the testsuite that all provided non-abstract classes are
    self-contained
- write an openc++-based dependency extractor
 - extract more fine-grained dependency (depending on a header does
   not necessarily imply depending on code)
 - handle (warn about) the case where the declarations for a given
   implementation file are scattered in more than one header
 - detect undeclared dependencies (eg. manually inserted prototypes)
 - check necessity of declared includes
- presentation
  - generalize the special_edge() mechanism (use a hash of edge attributes ?)
  - allow different node shapes when mixing high-level nodes with
    lower-level ones through the default singleton groups
    (special_node mechanism similar to the special_edge one ?)
  + optionally show labels or count for files (subnodes) in a node and
    color arcs according to them
  - optionally show external deps (deps on files not on command-line)
  - limit graph to one or more given group(s) of files (specified by <level>:<label>)
  - draw cycles in a given color
  - draw a specific path
  - allow setting fg color for a specific group level
  - provide automatic coloring schemes
  - color intra-group edges with the same color as nodes (post-processing ?)
  - allow to request drawing of who in a high-level node points to
    another node (ie. violates some constraint)
  + label edges with the number of explicit inclusions flowing through them
  - propagate excuses in some way when they are dropped by the transitive reducer
  - provide tools for automatic grouping (eg. using cycles, or selected external deps)
  - investigate candidate tools for hyperbolic layout ?
- CLI improvements
  + recursive directory search to avoid long command-lines
  - provide an initial list of system directories to avoid repeating them (ask compiler)
- provide an interactive tool to help understanding a project's
  structure.  Maybe with graphviz' lefty, or as a specialized tulip
  gui ?
- bugs
  - --showdropped mode draws too many edges as dropped (ie. does not
    consider marked edges as dropped when deciding whether to consider
    subsequent edges as dropped)
  - when showing only 3-3, colors from level 2 get propagated to level-3 groups
  - transitive reduction may not be complete, some more edges could
    possibly be dropped - wesnoth tree at 2005-03-25 exhibits the problem
    with the "display -> builder -> animated -> image" path


LICENSE
-------

    Copyright (c) 2005 Yann Dirson <ydirson@altern.org>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License, version 2,
    as published by the Free Software Foundation.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.