Reasoning about call graphs

Every program's call graph is different, so we don't memorize them like we memorize, say, language syntax. However, conscious thought about graphs is useful, especially in confusing edge cases like recursion. How many edges – calls – are there in the recursive loop? One is fine if it's justified, as in fact. Two might throw people off. With three, we should add a signpost comment warning future developers that something unusual is happening.

We also rarely think about call graphs consciously during maintenance, but we perform maintenance according to the graph even if we don't realize it. Suppose that we want to change Underscore's initial function, for example. Changing initial might break first, which uses it. We examine first: did its behavior change when we changed initial? Maybe we find that its behavior did change, and that the change is desirable – it fixed a bug. Now, we have to ask the same question again: which functions are affected by this change to first's behavior? Are any such changes desirable? And so on, expanding outward through the call graph.

The fancy computer science term for this is breadth-first search. We change the function; then we examine each of the functions that used it, noting the ones whose behavior changed; then we examine functions affected by those changes; and so on. We're following edges "backwards" here: after changing initial, we notice that first calls it – points to it in the graph – so we examine first as well.

We rarely think "I will now do a backwards breadth-first search on the call graph"; and yet, that's exactly what we find ourselves doing. If we don't do this, we'll sometimes change functions' behavior accidentally, introducing bugs.

Tracking these changes is a big maintenance burden, but thinking about the graph can reduce the cost. For example, if we avoid writing functions called from 500 different places, we won't find ourselves checking 500 call sites for impacts from a change. Or, to be more honest about software maintenance: we won't find ourselves avoiding ever changing that function. Experienced programmers intuitively distrust complex functions called from 500 places: complex functions tend to change, and a change puts all 500 of those call sites in question.

Many other call graph structures suggest danger. We've seen two: cycles across many nodes, forming a non-obvious recursive loop; and complex functions with many incoming edges – 500, say. More exist, but cataloging them is tiresome and probably not valuable.

Instead of trying to memorize a catalog of graph shapes, it's better to just keep an eye on the call graph, and on other graphs that we'll see soon. When a particular change is difficult, ask: what's the structure here? Is there some particular notable shape, or is it a just a boring tree of calls or modules? Over time, certain shapes will recur; patterns will become clear. Noticing them early can save frustration and maintenance costs later.

This is one section of The Programmer's Compendium's article on Software Structure, which contains more details and context.