=head1 NAME

makeppgraph -- Graphical analysis of the dependency graph

=for vc $Id: makeppgraph.pod,v 1.13 2009/02/21 11:25:31 pfeiffer Exp $

=head1 SYNOPSIS

B<makeppgraph> S<[ I<option> ... ]> S<[ I<pattern> ... ]>

B<mppg> S<[ I<option> ... ]> S<[ I<pattern> ... ]>

=head1 DESCRIPTION

They say "A picture is worth a thousand words".  So let's draw your dependency
or include graph from various viewpoints.  Check out the gallery
L<http://makepp.sourceforge.net/gallery/> to get some ideas of what you can
do.

Each node represents a source file or a target, colored according to file name
patterns.  A file's node is rectangular.  A phony target's node is oval.  Each
solid edge represents a direct dependency.  Alternately or additionally you
can display include relationships as dotted lines.  For a more detailed but
not so pretty textual view see L<makepplog|makepplog>.

But beware, even for a small build the complexity can be staggering!  This is
because with F<.o> files and system includes you easily have twice as many
nodes as source files.  But that is nothing -- the number of edges often far
exceeds that of nodes, due to multiple include statements.  A crossing-free
layout is usually impossible.

In real projects the complexity becomes insane.  Techniques like template
based source file generation, preprocessors (e.g. embedded SQL, interface
definition languages, Qt library) or publishing of files to central
directories (e.g. to have only one C<-I> or C<-L> option) make the graph
explode.  Even if edges are just one pixel wide, you end up with broad black
stripes of criss-crossing edges.

Once you realize what really goes on, if you're lucky, you may be able to find
a way of simplifying your build setup.  But before you get there, you must
drastically reduce the amount of information you display.  To that end there
are various selection, L<renaming and merging|/REWRITING> possibilities in
C<makeppgraph>.  When you fail to strike a balance between reducing the graph
so far that it becomes sensibly displayable, while still showing what you want
to see, you may fall back to a textual graph.


=head1 OUTPUT FORMATS

Graph layouting, display and manipulation are complex tasks, which are beyond
the scope of C<makeppgraph>.  Instead it produces input files for specialized
tools.  It creates an output file replacing or adding the appropriate suffix
to its first input file.  If that is F<.makepp/log>, the default, the output
file will skip the F<.makepp> directory, leading to F<log.udg>.  If the first
input is F<-> (stdin), the output goes to stdout.

=head2 uDrawZ<>(Graph)

With uDrawZ<>(Graph) L<http://www.informatik.uni-bremen.de/uDrawGraph/> you get
a fairly modern GUI, which allows to select parents or children, find the other
end of an edge, or hide subgraphs.  Tweaking the options like the node
distances, and using splines for edges can make the graph prettier.

While the above features make this a tremendously useful tool, there are a few
small hitches:

=over

=item *

It is quite memory hungry, such that, after a longish meditation, it may crash
without having displayed anything -- a clear sign that you must reduce the
number of nodes and/or edges further.

=item *

It strongly separates graph attributes and display options.  This means that
you can't put into a generated graph the fact that it is to be oriented
sideways (which is generally necessary here because, even when renamed to
something short, filenames are much wider than tall).  As a workaround, if you
don't want to make it your default, or choose orientation from the menu every
time, they propose a little starter script:

    export UDG_HOME=/where/ever/uDrawGraph-3.1
    TMP=`mktemp -t udg.XXXXXX` || exit 1
    trap "rm -f $TMP" EXIT
    echo "[menu(file(open_graph(\"${1-log.udg}\"))),menu(layout(orientation(left_right)))]" >$TMP
    $UDG_HOME/bin/uDrawGraph -init $TMP

=item *

It doesn't yet support node border colors.  Due to this C<--because> displays
double borders when they should be red.

=item *

When merging several files into one node leads to self edges both with
C<--dependencies> and C<--includes>, only one of these will be displayed,
randomly dotted or drawn through and with a label of C<2*>.

=back

=head2 Graphviz

Graphviz L<http://www.graphviz.org/> consists of several command line tools,
which allow many more export formats than uDrawZ<>(Graph).  That includes not
only static image formats but also input for designer programs like dia.
There is a utility C<twopi> for creating a radial layout, which is nice if
your graph comes close to a true tree, i.e. your dependencies fan out, but few
nodes have common dependencies with others.  There are a few viewers
available, none of which helps you to navigate along the structure of the
graph:

=over

=item dotty

Its own display tool, dotty, has the advantage over uDrawZ<>(Graph) that you
can freely drag the nodes, without being restricted to the level assigned by
the layout.  When your screen is full of edges, dragging one node gives you a
nice impression of where the edges of that node lead to.  But it also loses
information when you modify it.  Apart from that it is an antiquated Xlib
tool.  It also displays an annoying little circle on the middle of each edge,
and no option seems to get rid of it.

=item ZGRViewer

ZGRViewer L<http://zvtm.sourceforge.net/zgrviewer.html> is a separately
downloadable Java viewer which has comfortable zooming and panning.  The graph
is only viewable, no moving of nodes.  There are five buttons in the view
area, which offer additional fancy semi-3D zoom variations, but, unlike the
basic functionality, they can be extremely slow depending on your Java setup.
For my Sun Linux Java, the following gave a tremendous boost:

    export J2D_PIXMAPS=shared USE_DGA_PIXMAPS=1

=item Grappa

Grappa is a separately downloadable Java 1.2 viewer.  There is no wrapper
shell script, the jar contains no manifest, none of the sources contain a main
function, and with the appletviewer it produced two tall windows which hang
with a "starting applet" message, so I don't know how to test this.  It can be
tried on a demo web site as an applet.

Selecting an edge makes it bold red, so you can manually scroll its other end
into view without loosing it out of sight.  Other than that and zooming and
deleting nodes it seems to have no useful features.  It ignores valid
hexadecimal color specifications.

=item SVG

SVG, one of the file types the backends can export to, is already quite old.
But some browsers still have problems with it.  When embedding it with an
object tag only Opera scales it, others clip it, which is useless for a
thumbnail.  When viewed as a document of it's own, only Opera and Konqueoror
allow scaling it, while Firefox scales only the labels.  Even though the
labels are text, no browser can search for them.  IE6 doesn't have a clue,
unless you install a plugin.  A dedicated application, like Inkscape, can
serve you better.

=back

=head2 HTML

This is a simple unordered list tree format that can be perused with any
browser.  You should have JavaScript and CSS, which allows folding subtrees
and seeing colors.  Usually your graph will not be a tree, which is worked
around by repeating nodes in every subtree needed, but as a link to the first
occurrence where you can see all its attributes.  Due to IE's limited Unicode
support, vertical arrows are used for include relations, instead of the usual
dotted arrows.

=head2 Textual Graph

This is a simple indentation-based format that can be perused with any text
viewer.  This means you can usually study much bigger graphs than with the
other formats.  In Emacs you can use outline and foldout for very powerful
graph navigation with this little wrapper mode:

    (define-derived-mode textgraph-mode outline-mode "Graph"
      (view-mode)
      (set (make-local-variable 'outline-regexp) " *.")
      (set (make-local-variable 'outline-level)
	   (lambda () (/ (- (match-end 0) (match-beginning 0) -1) 2)))
      (set (make-local-variable 'outline-font-lock-keywords)
           '(("^ *\\(?:{[a-z,]+} \\)?\\([^{\n]+\\)" (1 (outline-font-lock-face) nil t))))
      (setq imenu-generic-expression
	    '((nil "^ *\\(?:{[a-z,]+} \\)?\\(.+?\\)\\(?:{[a-z,]+}\\)?$" 1))))

The lines can have comma separated annotations between braces, unless you also
give the C<-p, --plain> option.  When these come before the target they
pertain to the relationship with the parent, i.e. the previous line indented
less.  When they come after the target, they pertain to the target itself.
They are as follows:

=over

=item because

When this comes before a target, the parent was built because of this one.
When it comes after, the target had some inherent reason for being rebuilt.

=item bidirectional

This dependency or inclusion goes in both directions.

=item include

The parent includes this file.  This annotation is only given when also
showing dependencies.

=item phony

This is a phony target.

=item repeated

The information about this target and its children was already given earlier
on.

=back


=head1 OPTIONS

If you give no patterns, makeppgraph will start operating with all the nodes
it can extract from makepp's log.  When given one or more patterns (using
C<?>, C<*>, C<**> and/or C<[...]>), it will match those in the file system and
operate on any that also occur in the log.  For these it will by default
select "upwards", i.e. all targets that depend on and/or include any of them
and "downwards", i.e. all targets and/or sources, which any of them depends on
and/or includes.  (The directions are metaphorical, because the graph is best
displayed from left "top" to right "bottom" due to the width of the nodes.)

=over

=item -A filename

=item --args-file=filename

=item --arguments-file=filename

Read the file and parse it as possibly quoted whitespace- and/or newline-separated options.

=item -b

=item --because

=item --build-reasons

If a node was rebuilt because of a dependency, then that edge is shown in red.
Alas makepp applies optimizations to detect when a target needs rebuilding,
such that it often can't say which file triggered the rebuild.  If the node
was rebuilt for a reason not attributed to another file, then the node's
border is red.  With uDrawZ<>(Graph) a double border is used instead, as it
doesn't support border color.

=item -D

=item --dependencies

Draw a graph of the dependency relationship determined by makepp.  This is the
default unless C<-i, --includes> is also given.

=item -d

=item --down

=item --downwards

This option is only meaningful if you provide one or more patterns.  It will
then only select the targets and/or sources which the matched files depend on,
or which they include.

=item -g

=item --graphviz

=item --dot

Produce a Graphviz F<.dot> file, instead of the default uDrawZ<>(Graph) F<.udg>
file.

=item -h

=item --html

Produce a browser F<.html> file, instead of the default uDrawZ<>(Graph)
F<.udg> file.

=item -I dir

=item --include=dir

=item --include-dir=dir

Add I<dir> to Perl load path C<@INC>.

=item -i

=item --includes

Instead of dependencies (or with C<-D, --dependencies> additionally to them)
draw a graph of include relationships.  This will only have been logged as far
as it needed to be analyzed.  To get the full picture you need a fresh full
build.

=item -l filename

=item --log=filename

=item --log-file=filename

The I<filename> is to where makepp wrote its log.  It may also be a directory,
in which a file called F<.makepp/log> or F<log> will be searched.  To read
from stdin, you must give F<-> as a I<filename>.  When this option is not
given, it defaults to the current directory.

This option can be given multiple times, e.g. for merging all the logs from
C<--traditional-recursive-make>.  But the dependencies you hid from makepp
through the evil recursion paradigm can't of course show up here.

=item -M module[=arg,...]

=item --module=module[=arg,...]

Load module and import any functions it exports.

=item -m perlcode

=item --merge=perlcode

Perform I<perlcode> for every target and its dependencies.  See
L<merging|/Merging> for details about this option.

=item -o filename

=item --output=filename

Write the output to this file.

=item -p

=item --plain

Don't use attributes like colors or dotted lines.  This is especially useful
for uncluttering C<-t, --text> output.  In that format bidrectional edges will
be lost unless you combine this with C<-s, --separate-directions>.

=item -r perlcode

=item --rename=perlcode

Perform I<perlcode> for every target and its dependencies.  See
L<renaming|/Renaming> for details about this option.

=item -s

=item --separate-directions

Draw two separate arrows, instead of each double ended arrow, to make them
easier to spot.

=item -t

=item --text

Produce a human readable F<.txt> file, instead of the default uDrawZ<>(Graph)
F<.udg> file.

=item -u

=item --up

=item --upwards

This option is only meaningful if you provide one or more patterns.  It will
then only select the targets which depend on and/or include the matched files.

=item --version

Print out the version number.

=back


=head1 REWRITING

The techniques in this chapter are usually essential to get a reasonably sized
graph.  As they are formulated as Perl code, knowing the language is helpful.
But you should be able to achieve quite a lot with the examples here or in the
gallery L<http://makepp.sourceforge.net/gallery/>.

=head2 Renaming

This is the first name rewriting that occurs, if the C<-r, --rename> option is
given.  For every name encountered, perlcode gets called.  It gets a filename
in C<$_>, and it may modify it.  This is often needed, bacause makepp logs
fully qualified file names, so one node can easily be half a screen wide.

For one thing, you can rewrite names to C<undef> or the empty string.  This
will eliminate the node from the graph.  Note that eliminating a node in this
first stage will break a chain of dependency if this node was in the middle.

You can also rewrite various names to the same string, coercing them all into
the same node, which accumulates the combined dependencies and dependees.

On the other hand you can just rename names to (usually) shorter names, so as
to reduce the width of nodes, which can be far to wide with absolute
filenames.  There are a few predefined functions in package C<Mpp::Rewrite>,
in which your code also runs, you can use for this.  These return true if they
did something so you can combine them as in:

    --rename='cwd( 1 ) || &home || &usr'

=over

=item &cwd

=item cwd number

=item cwd number, name[, separator]

Removes the current working directory from the beginning of path.  With a
number, also replaces parent directories that many levels up with the right
number of F<../> directories, where applicable.  In this case you can give an
alternate I<name>, like a piled up ':' instead of '..' and additionally an
alternate I<separator> like '' instead of '/'.  In the first case you might
get F<:/:/a/b>, in the second an even shorter F<::a/b> instead of
F<../../a/b>.  Passing a number is useful if you draw in stuff from
neighbouring trees.  Or you have a F<src> directory, where most of the action
is, so you call makeppgraph there, but want to see the relation to your other
directories too.

If you give no C<--rename> option, C<&cwd> is the default.  Should you want no
renaming, you can give some I<perlcode> like C<--rename=1> that does nothing.

=item &dir

This one is a great reducer of graph complexity.  It reduces every file to its
directory.  That amounts to the question: "Files from which directory depend
on files from which other directory?"  Note that while the dependency graph is
always acyclic (else makepp wouldn't know where to start building), that is
not true of this reduced view.  E.g. if F<dir1/a> depends on F<dir2/b> and F<dir2/a>
on F<dir1/b> that will display as a mutual dependency between F<dir1> and F<dir2>.
Since a cyclic graph has no obvious starting point, the layout may be odd.

Unlike the other functions in this section, this is not exclusive with the
others.  So you may not want to logically combine it:

    --rename='&dir; &cwd || &home'

=item &home

Replaces your home directory with F<~/>.

=item &makepp

Replaces the makepp installation directory with F<|m|>.

=item &suf

=item suf number

This one is also a great reducer of graph complexity.  It reduces every file
that has a suffix to an asterisk and that suffix.  So you can see which kinds
of files depend on which other kinds.  With an argument of C<0> it leaves the
first character of the directory, provided it is one of C</>, C<~> or C<|> (as
put in by C<&home> or C<&usr> if you called those first).  With a positive argument, it
leaves that many directory levels at the beginning.  With a negative argument, it
removes that many directory levels at the end.  So for F</a/b/c/d/e/x.y> you get:

    &suf	*.y
    suf 0	/*.y
    suf 1	/a/*.y
    suf 2	/a/b/*.y
    suf -1	/a/b/c/d/*.y
    suf -2	/a/b/c/*.y

For a relative F<a/b/c/d/e/x.y> you get:

    &suf	*.y
    suf 0	*.y
    suf 1	a/*.y
    suf -1	a/b/c/d/*.y

=item &usr

Under F</>, F</B<u>sr>, F</B<u>sr/B<l>ocal>, F</B<u>sr/B<X>11>,
F</B<u>sr/B<X>11R6>, F</B<u>sr/B<X>11R7> or F</B<o>pt>, for any of the
directories F<B<b>in>, F<B<e>tc>, F<B<i>nclude>, F<B<l>ib> or F<B<s>hare>, the
initials of these words are concatenated between bars.

E.g. F</B<u>sr/B<l>ocal/B<b>in/foobar> becomes F<|ulb|foobar> or
F</B<u>sr/B<i>nclude/net/if.h> becomes F<|ui|net/if.h>.  Note that `l' stands
for `local' when between two letters and for `lib' as the last letter.

=back


=head2 Merging

This is the second name rewriting that occurs, if the C<-m, --merge> option is
given.  This API is still under development!  Currently the target is passed
in C<$_> and the dependency as an argument.  If perlcode returns a value, that
value replaces both the target and the dependency, merging them into one node.
A few predefined functions can help you:

=over

=item c2o

For any C/C++ source and the resulting F<.o> file, merge them into one node,
by adding to the source path a suffix of C<E<gt>o> like
F<some/where/foo.ccE<gt>o>, even if the F<.o> file is in another directory.

=item exe

For any F<.o> file and the resulting executable of the same notdir basename
without a suffix or with F<.exe>, merge them into one node, by adding an
asterisk to the F<.o> file.  This will not currently work together with
F<c2o>.

=item x2

For any pair of files with the same name, usually a header or library
published to a central directory, merge them into one node, by adding F<*2> to
the dependency.

=back


=head1 ENVIRONMENT

Makeppgraph looks at the following environment variable:

=over 4

=item MAKEPPGRAPHFLAGS

Any flags in this environment variable are interpreted as command line options
before any explicit options.  Quotes are interpreted like in makefiles.

=back

=head1 AUTHOR

Daniel Pfeiffer (occitan@esperanto.org)