Code autopsy.
A mystery unsolved.
When last examined, the structure of Apache Ant looked odd.
Something didn't quite fit.
The problem concerns function transitive dependencies: Ant boasts a shocking 504776 of the little blighters.
That is, if you line-up all of Ant's functions on which there are no dependencies and try to trace all source code paths from them - essentially enumerating all the system's transitive dependencies - you will find half a million different function chains.
Half a million.
By comparison, JUnit has 2700 transitive dependencies. Of course Ant sprawls three-times larger than JUnit, Ant having 4500 functions, JUnit, 1300. The relationship, furthermore, between number of functions and number of function transitive dependencies is complex so you might expect that three-times the number of functions might account for five-times the number of transitive dependencies, say, or perhaps ten-times. But increasing that number by two orders of magnitude?
A strangeness lies here.
Nor is this a mere academic curiosity. Each time a programmer updates a function a non-zero probability exists that such an update will cause ripple-effect changes to other dependent functions, with consequent increased potential costs. Oddly-soaring numbers of transitive dependencies certainly do not reduce such potential costs. Corporate responsibility demands an explanation.
So let us drag Ant's carcass to the mortuary and indulge in a gratuitous montage of serious-looking physicians, slicing scalpels and bloodied organs being weighed in stainless-steel scales, all to a painfully-hip soundtrack.
Amplification.
Actually, even before we look at Ant, let us take a quick peek at some of the quirks of transitive dependencies. Consider a single-class system comprising the functions shown in figure 1.
Figure 1: A simple system.
In figure 1, we have four transitive dependencies, all arranged in the noble and classic sunburst pattern:
- {
a(),c(),d()} - {
a(),c(),f()} - {
a(),c(),g()} - {
a(),c(),e()}
Why investigate so trivial a system before delving into the monster? Well, hand-carving half a million transitive dependencies from flawless digital marble sounds inordinately time-consuming. What if some combinatorial effect lurks out-of-sight? What if, rather then having the programmer explicitly create these transitive dependencies, some configurations of functions amplify the number of transitive dependencies beyond those, "Intentionally," created?
These are the configurations we seek, those in which adding a single dependency yields more than one extra transitive dependency. In figure 1, for instance, what happens if we add another function, h(), called by c()? This is shown in figure 2.
Figure 2: Extra function called.
Figure 2 now yields five transitive dependencies:
- {
a(),c(),d()} - {
a(),c(),h()} - {
a(),c(),f()} - {
a(),c(),g()} - {
a(),c(),e()}
Thus by adding one more dependency we have added just one more transitive dependency. No amplification has occurred here.
Consider, however, if we add a new function, b(), which calls c() rather then being called by it.
Figure 3: A new function creating amplification.
Suddenly figure 3 shows ten transitive dependencies, twice as many as figure 2 even though we have added only one new function and one new dependency. Though precisely the effect we sought, this strikes, now lying limp before us, as underwhelming. The extra five transitive dependencies stem from the calling of a function which in turn has five dependencies. Is this not obvious?
Subtlety moves beneath the surface, however. For the programmer has had to create a new function to trigger the amplification and to create - on what we see now as figure 3's key-stone, function c() - a new dependency. Both entail a deliberacy and explicitness that a wary programmer might notice, were that programmer concerned by such matters.
Yet some cases operate on more devious levels, perhaps most pernicious being those with links to the shady underworld of circular dependencies.
You might think that simply adding a dependency from d() back to b() would trigger all sorts of circular shenanigans but it does not. Spoiklin Soice, producer of these diagrams, must like all such dependency analyzers ensure against infinite loops where circular dependencies arise, and so dependency on a function which already resides in the transitive dependency being analyzed causes analysis to terminate, marking that transitive dependency as circular.
The, "Trick," is to include a dependency on the hub that does not come directly from the two parent functions, a() or b(), and this alas happens all too often.
Figure 4: A pre-circular trap is set.
Figure 4 shows the same functions as figure 3 only with an extra dependency added, that of a() on h(). This triggers no amplification and creates just one extra transitive dependency: where figure 3 had ten, figure 4 has eleven. In the next figure, however, we shall see the effect of introducing our circular dependency between h() and the hub, c().
Figure 5: A circular amplification.
Figure 5 demonstrates the amplification caused by the new circular dependency. Where figure 4 has eleven transitive dependencies, the addition of just one more dependency - and no new functions - in figure 5 now creates fifteen transitive dependencies. (Note: not sixteen transitive dependencies. Why?)
All this, observe, in a trivial system of eight functions which despite its size offers a non-trivial challenge to predicting transitive dependency amplification. This phenomenon, again, concerns the real-world problem of cost-management in the face of geometrically-increased ripple-effect vectors in real software products. Imagine how much more painful this problem grows in a system of a thousand functions, or four-thousand.
To wit ...
Once more into the Ant.
Despite the mind-shredding complexity of the Ant's five-hundred-and-four thousand, seven-hundred-and-seventy-six transitive dependencies, finding a place to pierce the insanity-maze proves unproblematic. One function sticks out.
That function is Path.list() and through it cascade 356440 transitive dependencies, more than half of the entire system's burden. Here we discover our hub, our typhoid Mary.
Figure 6: Path.list()
You may not think, just by looking at list() in figure 6, that it was such a bully. Yes, sixteen functions depend on it and it depends on seventeen others, so it's not shy of company but that hardly singles it out for special treatment.
Nor is it what you might call a, "Looker."
Take a glance for yourself though it is displayed here entirely for completeness; don't bother trying to unravel it:
/**
* Returns all path elements defined by this and nested path objects.
* @return list of path elements.
*/
public String[] list() {
if (!isChecked()) {
// make sure we don't have a circular reference here
Stack stk = new Stack();
stk.push(this);
dieOnCircularReference(stk, getProject());
}
Vector result = new Vector(2 * elements.size());
for (int i = 0; i < elements.size(); i++) {
Object o = elements.elementAt(i);
if (o instanceof Reference) {
Reference r = (Reference) o;
o = r.getReferencedObject(getProject());
// we only support references to paths right now
if (!(o instanceof Path)) {
String msg = r.getRefId() + " doesn\'t denote a path " + o;
throw new BuildException(msg);
}
}
if (o instanceof String) {
// obtained via append
addUnlessPresent(result, (String) o);
} else if (o instanceof PathElement) {
String[] parts = ((PathElement) o).getParts();
if (parts == null) {
throw new BuildException("You must either set location or"
+ " path on ");
}
for (int j = 0; j < parts.length; j++) {
addUnlessPresent(result, parts[j]);
}
} else if (o instanceof Path) {
Path p = (Path) o;
if (p.getProject() == null) {
p.setProject(getProject());
}
String[] parts = p.list();
for (int j = 0; j < parts.length; j++) {
addUnlessPresent(result, parts[j]);
}
} else if (o instanceof DirSet) {
DirSet dset = (DirSet) o;
DirectoryScanner ds = dset.getDirectoryScanner(getProject());
String[] s = ds.getIncludedDirectories();
File dir = dset.getDir(getProject());
addUnlessPresent(result, dir, s);
} else if (o instanceof FileSet) {
FileSet fs = (FileSet) o;
DirectoryScanner ds = fs.getDirectoryScanner(getProject());
String[] s = ds.getIncludedFiles();
File dir = fs.getDir(getProject());
addUnlessPresent(result, dir, s);
} else if (o instanceof FileList) {
FileList fl = (FileList) o;
String[] s = fl.getFiles(getProject());
File dir = fl.getDir(getProject());
addUnlessPresent(result, dir, s);
}
}
String[] res = new String[result.size()];
result.copyInto(res);
return res;
}
Again: nasty though not obviously 356440-transitive-dependencies nasty.
But wait, wait, wait: we can distill the problem if we cheat a little. Let us pretend that the list() function appears not as it does above but finds itself reduced to the following:
/**
* Returns all path elements defined by this and nested path objects.
* @return list of path elements.
*/
public String[] list() {
Object o = elements.elementAt(0);
DirSet dset = (DirSet) o;
DirectoryScanner ds = dset.getDirectoryScanner(getProject());
return null;
}
Yes, this function now makes no sense, even returning a lethal null that would certainly bring Ant tumbling down. This, however, is not an analysis of Ant's user-experience realisation but of its structure and structural analyses pull odd stunts like this all time, in this instance performing a local structural reduction, run-time consequences be damned. With the cartoonish refactoring above, the number of Ant's transitive dependencies falls from 504776 to 450259.
You might think it impressive that dropping a few dozen lines of code could slash 50000 transitive dependencies but the beast remains: four-hundred-and-fifty thousand transitive dependencies still weave a mat incomprehensible. Now consider what happens now if delete that single line:
DirectoryScanner ds = dset.getDirectoryScanner(getProject());
The number of transitive dependencies plummets to 149014.
That single line of code generates three-hundred thousand transitive dependencies, surely the greatest example of amplification since the bouncing-baby universe finished inflating.
And why? Because getDirectoryScanner() has a transitive dependency on list(): they reside in the same transitive dependency, so once list() invokes getDirectoryScanner() a long tortuous circuit completes connecting chain after chain of amplifying functions, feeding back on themselves, cascading mindlessly.
At which specific functions between getDirectoryScanner() and list() do these amplifications take place? Who can say? The answer requires even more meticulous tracing, perhaps hours tugging ligaments to see which twitching organs are ultimately connected.
And herein lies the point: poorly-structured systems impede dependency analysis and this translates directly to a difficulty in predicting update costs.
Are poorly-structured systems always more costly to update than well-structured systems? Of course not, but the cost of updating poorly-structured systems is always more difficult to predict.
Ant finds itself in this situation because it has broken at least two tenets of good structure: it has too many circular dependencies and it is too deep.
But finding a cure was never part of this analysis's remit: we wanted to find the source of the disease and even in this task a conclusive identification remains elusive. With some slicing and drilling and cautious speculation, however, we are at least within a House-hunch.
(Note that the version of Ant discussed here is 1.6.0 and in a later version list() has been refactored yet even that version has a similarly-enormous number of transitive dependencies, so whatever refactoring has been done merely moved the amplifiers elsewhere.)
Summary.
Ant remains a great piece of software, providing fantastic value to businesses world-wide. It continues to deserve its place one of the most-popular building tools of the day.
This analysis, however, concerned itself not with Ant the user-experienced tool but Ant the structure and attempted to explain why Ant contains a number of transitive dependencies vastly disproportionate to its size.
Photo credit attribution.
CC Image PICT0039.JPG courtesy of the_lost_drones on Flickr.