Analyse the dependencies in an ASDF system

asdf-dependency-grovel

Basic Overview
==============

First, I'll give a brief overview of how asdf-dependency-grovel (ADG) works, so
that you'll be better able to understand the nitty-gritty details that come
later.


Constituents
------------

A "constituent" represents a piece of the codebase.  Constituents are arranged
into a tree, with the children of a constituent representing disjoint pieces of
their parent constituent.  The constituent objects are used to store
information about dependencies between different parts of the codebase.

ADG's constituent system is designed to be quite flexible at representing
different shapes and sizes of codebases, but in most cases (including QPX), the
constituent tree will have exactly three levels.  At the top, there is a single
root constituent that represents the whole codebase.  The root constituent has
as children one constituent for each file in the codebase -- these are called
"file-constituents".  Each file-constituent has as children one constituent for
each top-level form in the file -- these are called "form-constituents".  The
goal of ADG is to determine the dependencies between the various
form-constituents, which allows it not only to infer dependencies between
files, but also to determine how the top-level forms could be reorganized
between files so has to eliminate file-level dependency cycles.


Provisions and Uses
-------------------

ADG detects dependencies through the use of the `signal-provider' and
`signal-user' functions.  When a form "provides" something -- for example, a
defun form provides the function being defined -- then ADG will call the
signal-provider function with the name of the thing being provided (as a
symbol) and a symbol indicating what kind of thing was provided.  This will
cause that "provision" -- that is, the name/kind pair -- to be added to the
current constituent's set of provisions.  Similarly, when a form "uses"
something (at compile time), ADG will call the signal-user function with the
name and kind of the thing used, which adds the use to the current
constituent's list of uses.  In general, if constituent A provides X and
constituent B uses X, then we conclude that B depends on A.  This is ADG's
fundamental mechanism for determining dependencies.

This approach is relatively easy to implement, and usually works, but it is
also flawed.  Suppose that we have three forms: A, B, and C.  Forms A and B are
both (defconstant +sqrt2+ 1.41), and form C is (defvar *foo* +sqrt2+).  ADG
will call (signal-provider '+sqrt2+ 'defconstant) for each of forms A and B,
and will call (signal-user '+sqrt2+ 'defconstant) for form C (as well as
calling (signal-provider '*foo* 'defvar)).  ADG will then conclude that form C
depends on _both_ A and B, when in reality, Common Lisp allows it to depend on
_either_ of A or B, since defconstants may be repeated as long as they all have
the same value for the constant.  ADG simply doesn't try to handle this case
correctly, largely because doing so would complicate some of the later stages
with relatively little benefit.

Finally, it should be noted that ADG detects provisions and uses heuristically,
and as a result, will frequently have both false negatives and false positives
when detecting dependencies (we'll see later on why this is, sadly,
unavoidable).  The main trick to making ADG work is to balance these so that
the wrong answer it comes up with is still good enough to successfully
eliminate the dependency cycles in the particular codebase of interest.


Cycle Resolution
----------------

Once ADG has collected all the provisions and uses for each constituent, it
builds a directed graph with form-constituents as nodes and dependencies as
edges.  We will assume that the resulting graph will be acyclic, which should
be true if the code was able to compile and if the dependency detection didn't
have too many false positives.

The goal in this stage is to eliminate dependency cycles between files.  We
could do this by splitting _every_ form into its own file, but that would
create a huge mess.  Or, we could merge everything into one file, but that is a
similarly degenerate solution.  Or, we could drastically rearrange the code,
but that too would be confusing to the poor humans to organized these forms
into each of these files for a reason.  The compromise the ADG takes is to only
ever split existing files into pieces (not to merge anything), and try to make
as few splits as possible.

To do this, ADG starts with the graph of form-constituents, and treats each
form-constituent as though it were a separate file; it then merges together
pairs of nodes into supernodes as much as possible, subject to the constraints
that 1) it may only merge nodes that originally came from the same file, and 2)
it must never perform merges that would introduce a cycle into the graph.  As
it turns out, perfectly minimizing the number of nodes in the final graph is
NP-hard, so ADG uses a greedy algorithm that seems to make for a reasonable
approximation.

Once ADG has finished merging the graph, it sorts the nodes in that graph
topologically to create a new file order.  In order to protect against false
negatives in the dependency detection, ADG uses a _stable_ topological sort,
keeping the files as close to the original file order as possible (thus, if
file B depends on file A and ADG didn't notice, there's still a good chance
that file B won't load until after file A in the new file order).


File Splitting
--------------

Once ADG has determined how to split the files and what order to put the new
files in, we can run its output through a program that will automatically
divide up the actually files.  Here we have to deal with one hitch -- ADG
doesn't really understand the significance of in-package forms, and will treat
them just as any other form, to be put one one piece or another of a split
file.  To deal with this, the program that actually splits up the files will
check for pieces of files that don't have the in-package declaration; for each
such piece, it will check the _original_ file to see if it has only a single
in-package form, and if so, it will copy that form to the top of the split
piece.  If the file has multiple in-package forms (an unusal case), then the
program simply prints a warning, indicating that a human should do it manually.
Fortunately, there are usually no such warnings.




How it _Really_ Works
=====================

Now that you have a basic idea of what ADG does, let's take a look at the nasty
details of how it detects provisions and uses.  Beware -- this will be an
adventuresome journey into just how annoying Common Lisp can be as a language.


Fine-Grain Instrumented Load
----------------------------

The first piece of trickery is how ADG can keep track of which top-level form
in the file it is working with, so that it can instantiate the constituents
correctly.  ADG provides a drop-in replacement for the load function called
fine-grain-instrumented-load that does this.  Intuitively, this simply needs to
pass the file through the Lisp reader to get a list of forms, and then eval
each form in a new form-constituent.  However, the Common Lisp spec requires a
variety of particular, subtle behaviors from the load function, which makes it
much more difficult to provide a portable, drop-in replacement.  Thus, ADG
simply uses a modified copy of the load function from the SBCL source code.
That makes it unportable, but oh, well.  The replacement load function
instantiates a new form-constituent for each top-level form, and also
preprocesses each form before eval-ing it (this step is described in later
sections).  Finally, the replacement load function keeps track of some
anciliary data, such as the index of the form in the file (e.g. 1st form, 2nd
form, etc.), which serves to uniquely identify the form, and the position of
the form in the file as an index into the character stream, which aids in the
automatic file splitting later on.


The Macroexpand-Hook and Handlers
---------------------------------

The primary mechanism that ADG uses to find dependencies is a custom
*macroexpand-hook*.  This is a function that Common Lisp will call whenever it
is about to expand a macro; this gives ADG an opportunity to examine the macro
form, or even to alter it.

In general, when the code expands a macro foo, ADG calls (signal-user 'foo
'defmacro) to indicate that a macro is being used.  However, ADG also has a
number of "handlers" which it uses to give special treatment to a number of
standard Common Lisp macros.  For example, defmacro is itself a macro, and when
ADG's macroexpand-hook sees a defmacro of a macro foo, it calls
(signal-provider 'foo 'defmacro).  When ADG sees a defun macro for a function
foo, it calls (signal-provider 'foo 'defun) and also alters the function
definition to include a call to (signal-user 'foo 'defun), so that if the
function is called at compile time, it will signal a use of the function.  When
ADG sees a defstruct macro, it does all kinds of squirrelly things, because
defstruct is a horrible mess; among the things it does is to insert code after
the defstruct to "retroactively" instrument the accessor functions that are
automatically generated by the defstruct macro.  There are a wide variety of
other handlers defined in ADG, and more can be easily added if necessary.

It should be noted that it is largely a fortunate coincidence that many of the
things that we are interested in (e.g. defmacro, defun, defvar, etc.) happen to
be defined as macros in Common Lisp, and can thus be caught by the
macroexpand-hook.  There are other things we might be interested in, such as
eval-when, that are defined as special forms; we have no easy way to detect
these without walking the code "manually".  (Incidentally, _Common Lisp: The
Language_, second edition, describes a facility called *evalhook* that allows a
user-defined function to be called on _every_ subform as it is evaluated.  Such
a facility would be extremely useful for ADG.  Unfortunately, that facility is
no longer part of the Common Lisp spec, and is not supported by SBCL.)


Detecting Variable Uses
-----------------------

It is generally easy for ADG to detect when global variables (or constants) are
provided, as the macroexpand-hook will notice defvar and defparameter (and
defconstant) forms (ADG treats defvar and defparameter as essentially
equivalent for the purposes of dependency detection -- when it sees a
defparameter form, it signals a provision of kind defvar).  What is harder is
to detect when a global variable or constant is being used at compile time.

The trouble is that there are a lot of different ways to "use" a global
variable at compile time.  You could read the variable and use its value at
compile time.  You could alter the value of the variable at compile time with
setf or setq.  You could dynamically rebind the variable at compile time with
let.  You could even quote the variable name and pass it to a function like
boundp or constantp, at compile time.  And yes, QPX does all of the above.

There are several clever strategies that don't work.  One is to instrument
defvars so that the variable name is actually symbol-macro that expands to some
code that signals a use of the variable and then returns the value.  You can
even write a setf function so that setf will work with such macros.
Unfortunately, this doesn't work with let forms or quoted symbols, since those
are not subject to symbol-macroexpansion.  Another neat idea would be to use
some kind of alternative environment object that could somehow detect when
global variables (or other things!) are being used.  However, there is
explicitly no portable way to do this, and I can't even find a non-portable way
to do it in SBCL.

In the end, what ADG actually does is incredibly stupid.  When it sees a
defvar, not only does it signal a provision, but it adds the symbol to a set
called *suspected-variables*.  Before evaluating each form, ADG performs a
preprocessing step that, among other things (see later sections), walks all the
symbols in the form, looking for ones that are in *suspected-variables*; if it
finds any, then it assumes that that is a use of the variable, and makes an
appropriate call to signal-user.  Of course, this results in a number of false
positives, since many of those appearances will not be relevant at compile
time.  However, amazingly, it seems to be good enough.


The Readtable and Constituent Transfers
---------------------------------------

This is where things start to get a little more hairy.

QPX contains a large number of sharpdot (#.) forms.  These indicate a form that
is to be evaluated at read-time, and the result to be inserted into the code in
place of the sharpdot form.  Of course, these sharpdot forms may well make use
of functions defined in other files, in which case there is a dependency
between the top-level form containing the sharpdot and the top-level form that
provided the function (or whatever) that the sharpdot form used -- in
particular, we must ensure that when we split up and reorder the files, the
file in which the providing form ends up must come before the file in which the
sharpdot ends up.

The trouble is that the evaluation happens while the file is being read, which
is before ADG is able to break the file up into top-level forms and set the
*current-constituent* variable to each form-constituent in turn.  Thus, if the
evaluation of the sharpdot invokes any signal-user calls, the use will not be
added to the correct constituent.

ADG solves this by using a modified *readtable* with a replacement sharpdot
reader macro function (as well as other replacement reader macros -- more on
that later).  The new sharpdot sets the *current-constituent* variable to a
newly instantiated "temp-constituent" object -- a constituent that has no
parent -- before evaluating the form.  Thus, this temp-constituent will catch
any use (or provision) signals caused by the evaluation of the sharpdot form.
Then, the replacement sharpdot function must return a piece of data containing
both the result of the evaluation (which should be inserted into the code) as
well as the temp-constituent object.  When we get around to evaluating the
top-level form in which the sharpdot appeared, we will "transfer" the signals
from the temp-constituent to the new *current-constituent*, so that the form in
which the sharpdot appears will have the proper dependencies.

Now, what should the sharpdot function return to allow us to make this
transfer?  An obvious answer is to have it return a macro call that, when it
expands, performs the transfer and the returns the result value.  Thus, the
sharpdot reader macro function would return something like
`(with-transfer-constituent ,temp-constituent ,result).  Since macroexpansion
won't happen until we evaluate the top-level form in question, and thus when we
have the proper *current-constituent* in place, this seems workable.  The
trouble is that sharpdots may appear in places that are not subject to
macroexpansion.  Instead, we will have the sharpdot reader macro function
return the with-transfer-constituent list as before, but we will perform our
own macroexpansion-like operation during the form preprocessing step described
in the previous section that deals with appearances of
with-transfer-constituent anywhere in the form.

Walking a form and replacing with-transfer-constituent lists is actually much
trickier than it sounds, because there are a number of edge cases.  For
example, one might think that when walking a subform that is a list, one could
simply check each item of the list to see if the item is a list beginning with
the symbol 'with-transfer-constituent.  Not so.  Someone might write something
like (progn . #.(loop ...)), in which case the 'with-transfer-constituent
symbol will appear as the second item in a list.  Yes, that code is legal Lisp.
Yes, QPX does that.  A lot.

All told, this strategy for dealing with sharpdots works pretty well, but it
opens up a can of worms -- there are a handful of very nasty, very subtle
issues that I won't go into here (but that are documented in the code).
Suffice to say that these issues are largely the result of certain parts of
Common Lisp, particularly backquotes and compiler macros, being underspecified
in perilous ways.


Manual Annotations
------------------

Despite all the heuristics ADG uses to try to find dependencies, sometimes you
have to give it some hints.  This is a slightly dicey game, and requires some
familiary with ADG to know how to make it work, but when carefully done it can
help tremendously.

One all too common case is to have a global variable that is a hash table, and
have one file that populates the hash table at compile time, and another file
that requires the hash table to be populated in order to compile.  There's not
really any way for ADG to understand this dependency, but it's usually easy to
annotate manually: the function that adds an entry to the table can make a call
to signal-provider with some appropriate tag, and the function that expects the
entry to be there can call signal-user.  ADG adds the symbol :groveling to
*featuresa* when it's running, so you can use code like

  #+groveling(asdf-dependency-grovel:signal-user foo-key 'foo-table-entry)

to ensure that the codebase won't be affected when you're not using ADG.

Another possible problem is when there are two adjacent forms that should be
kept together, but ADG fails to understand this and happens to try to split
them into separate files.  One example from QPX is code that looks like:

  (defvar *foo*)
  (with-build-version :foobar-3
    (setf *foo* (make-hash-table)))

These are two separate top-level forms, but splitting them up can cause
breakage, and ADG is easily confused by defvar dependencies.  A simple solution
is to simply wrap these two forms into a progn, thus making them a single
top-level form and preventing ADG from splitting them:

  (progn
    (defvar *foo*)
    (with-build-version :foobar-3
      (setf *foo* (make-hash-table))))




How to Use ADG
==============

*** more here ***



--------------------------------------------------------------------------------

First, let's worry about other reader macros.  Sharpdots can appear just about
anywhere, including inside other reader macros.  For example, you could write
something like #+#.(stuff).  Yes, QPX does that too.  Fortunately, that's no
trouble -- we just need to replace other reader macros in the readtable so that
the perform the proper preprocessing step before doing their thing.  While
we're at it, we can instrument sharpquote to signal a use of the function in
question; of course, like sharpdot, it'll have to return a
with-transfer-constituent form so that the signal can get properly transferred
in the preprocessing step.  That's easy enough, until we get to the next issue.

How about backquotes?  What happens when you write `(foo #'(setf ,bar)) after
we replace sharpquote as above?  Actually, the behavior is not portably
defined, because Common Lisp doesn't specify how backquote works, only what it
does when evaluated (in particular, the value of (car (quote `(a ,b))) is
undefined in Common Lisp).  In SBCL, I've found that that snippet causes quotes
to appear in unexpected places, causing the with-transfer-constituent
replacement to get confused.  Mercifully, this sort of thing actually doesn't
seem to crop up in QPX (although it does in QRES), and ADG currently makes no
attempt to deal with it.

Now, how about compiler macros?  Compiler macros have the useful (but not well
specified) property that if a compiler macro function returns the same form
unchanged, then compiler-macroexpansion of that form halts, even though the
resulting form is of course still a valid compiler macro.  Thus, when
performing with-transfer-constituent replacement, we must be


asdf

ASDF-DEPENDENCY-GROVEL will analyse the actual dependencies in an ASDF system.
Based on an analysis with file granularity ,
it can output an optimized system definition,
based on which compilation can be parallelized.
Based on an analysis with form granularity,
it can output a summary from which you can untangle
the circularities in your build.

asdf-dependency-grovel

Upstream URL

Author

License

asdf-dependency-grovel

Version:

Authors:

Dependencies:

test-serial-system

Version:

Authors:

Dependencies:

Dependencies (0)

Dependents (0)