The call graph

A call graph records which functions call which. Each function is a node, and every place one function invokes another is a directed edge from the caller to the callee. Follow those edges forward from a function and you find everything it depends on to do its job. Follow them backward and you find everything that depends on it.

What a call edge is

A program is mostly functions calling other functions. A function does a small, named piece of work, and to do it, it usually asks other functions to do smaller pieces. When function checkout needs to charge a card, it does not do the charging itself. It calls chargeCard. That single act, one function invoking another, is what a call edge records.

The edge has a direction, and the direction is the whole point. It runs from the caller to the callee, from checkout to chargeCard, because the relationship is not symmetric. checkout depends on chargeCard to get its work done. The reverse is not true: chargeCard has no idea who called it and does not depend on checkout at all. An arrow captures that. A plain line would lose it. Build up one such arrow for every call in the codebase and you have the call graph: every function as a node, every invocation as a directed edge.

Forward and backward are two different questions

Because the edges point, you can walk the call graph in two directions, and each direction answers a different and important question. This is the single most useful thing the call graph gives you, so it is worth being slow and precise about it.

Walking forward means following the arrows in the direction they point, from a function to the functions it calls, then to the functions those call, and so on. The functions a given function calls are called its callees. Walking forward gathers everything a function depends on, directly and indirectly, all the way down to the smallest helpers. This is the reachability question read one way: starting here, what can I reach? If you want to understand everything that has to work correctly for one function to succeed, you walk forward.

Walking backward means following the arrows against their direction, from a function to the functions that call it, then to whatever calls those, and so on. The functions that call a given function are called its callers. Walking backward gathers everything that depends on a function, directly and indirectly, all the way up to the entry points where work begins. This is the reachability question read the other way: who can reach here? If you want to know what might be affected by changing one function, you walk backward.

Callees flow forward and answer what this depends on. Callers flow backward and answer what depends on this. Same graph, same edges, opposite directions of travel, and the two answers are rarely the same set. Keeping them straight is most of the skill of reading a call graph.

Forward from a function is everything it needs. Backward from a function is everything that needs it. The call graph is the one structure that answers both by walking the same edges two ways.

A worked example

Make it concrete with a small online store. There is an entry point, handleRequest, that receives a web request. It calls checkout. checkout calls three functions in turn: validateCart to make sure the order is sane, chargeCard to take payment, and sendReceipt to email the customer. Both chargeCard and sendReceipthappen to call the same low level helper, formatMoney, to turn a raw amount into a tidy string like a price. The edges look like this.

handleRequest -> checkout
checkout      -> validateCart
checkout      -> chargeCard
checkout      -> sendReceipt
chargeCard    -> formatMoney
sendReceipt   -> formatMoney

Now ask a forward question. What does checkout depend on? Walk forward from it. Directly it reaches validateCart, chargeCard, and sendReceipt. Continuing along the arrows, chargeCard and sendReceipt both reach formatMoney. So checkout depends on four functions in all. If any of them is broken, checkout can misbehave.

Now ask a backward question, the one that matters before a change. You are about to edit formatMoney, maybe to change how it rounds. What could you affect? Walk backward from it. Its direct callers are chargeCard and sendReceipt. Their caller is checkout. Its caller is handleRequest. So a change to one tiny formatting helper can reach all the way up to the request handler, and it touches both the payment path and the email path. That is not obvious from reading formatMoney on its own, where it looks harmless. The backward walk is what makes the real reach visible, and it is exactly the walk a person cannot reliably do in their head once the graph has thousands of nodes.

How far the walk goes

A natural worry about the backward walk is where it stops. If you keep following callers, do you eventually drag in the whole program and learn nothing? In practice, no, and the reason is worth understanding. The walk stops on its own at the functions that nothing else calls. Those are usually the entry points: the request handler, the scheduled job, the command a user runs, the test. Work in a program begins at an entry point and flows down through calls, so walking backward from any function leads up to the entry points that can set it in motion, and there the arrows run out.

The size of what you gather is a real signal, not noise. A helper reached from one narrow entry point has a small backward set, and changing it is contained. A helper reached from a hundred entry points has a large one, and changing it is a bigger commitment. In the store example, walking back from formatMoney reached both the payment path and the email path, which is precisely the fact you wanted to know before editing it. The count of what a backward walk gathers is, roughly, how load bearing a function is, and the call graph is what makes that count something you can read off rather than guess at.

One subtlety keeps the walk honest: you must remember where you have already been. Real call graphs contain loops, because functions can call each other in a cycle and a function can even call itself, which is called recursion. If the walk did not keep a note of the nodes it had already visited, a loop would send it around forever. Keeping that visited set is what lets the walk terminate and lets it report each affected function once rather than many times. It is the same care any graph walk needs, and it is why a careful tool gives a clean answer where a naive one would spin.

Why name matching gets this wrong

The worked example only works because each edge points at the one function actually being called. The fastest way to ruin a call graph is to build its edges by matching names, and it is worth seeing exactly how that fails, because the failure is quiet.

Suppose the store has three different functions called validate: one on the cart, one on a user’s address, one on a discount code. They are separate functions that share a common, sensible name. Now somewhere the code calls validate. A name matcher sees the call and sees three functions with that name, and it cannot tell which is meant, so it draws edges to all three. Two of those three edges are fiction. The call reached exactly one of them, and the graph now claims two relationships that never happen.

Walk that polluted graph and it lies in both directions. Forward, it says the caller depends on address validation and discount validation when it depends on neither. Backward, ask who calls the address validator and it names a caller that actually calls the cart validator. You go check code that was never in danger and you trust code that was. The tool did not crash. It gave you a confident, wrong answer, and confident wrong answers are the expensive kind. A correct call edge has to be resolved, worked out by the same rules the language uses to decide which validate a given call reaches, rather than guessed from the shared name.

The edges that are genuinely hard

Honesty requires admitting that not every call edge can be resolved with certainty, and the reasons are built into how modern languages work. Two situations make some edges hard, and no tool escapes them completely.

The first is dynamic dispatch. In most languages you can call a method on an object without the code stating exactly which version will run, because the version depends on the object’s actual type at that moment, which can vary as the program runs. If several classes each provide their own save, and the code calls save on something whose exact class is only known while running, then the honest answer is that the call could reach any of those versions. The edge is not one arrow but a small set of possible arrows, and narrowing it down means reasoning about which types can actually arrive there.

The second is higher-order functions, where functions are passed around as values. A function can accept another function as an argument and call it without ever naming it, referring to it only as, say, the callback it was handed. At the call site there is no name to resolve at all, because the thing being called was decided somewhere else and delivered as a value. To draw the edge you have to trace where that function value came from, which can wind back through several other functions.

The right response to these is not to pretend they are easy and not to give up. It is to resolve every edge you can with certainty, and to represent the genuinely uncertain ones as a set of possibilities rather than inventing a single false arrow. A call graph that is honest about its uncertainty is far more useful than one that hides it, because you can see where to look harder, instead of being quietly misled.

The backbone of impact analysis

Pull the threads together and you can see why the call graph is the backbone of impact analysis, which is the discipline of working out what a change will affect before you make it. Nearly every impact question is a backward walk over call edges. What depends on this function? Walk backward. What is the full set of code that could be affected if this behaves differently? Keep walking backward until you run out of callers. The reach you gather is the blast radius of the change, and the call graph is the structure that produces it.

This is why the call graph is not one feature among many but the spine that impact analysis hangs on. Without it, working out what a change affects is guesswork built on searching for a name and hoping you found the right places. With it, the question becomes a walk with a definite answer, as good as the edges are honest. That is also why the resolving of edges and the honest handling of the hard ones matter so much: the walk is only as trustworthy as the arrows it follows.

Where this connects

The call graph is one slice of the larger code knowledge graph, the slice whose edges are calls, and it sits alongside the other slices as part of that whole. The reason a call edge must point at one specific function rather than any function sharing its name comes down to how names bind to definitions, which is the subject of symbols, scope and binding. The backward walk that gathers everything a change can reach is exactly what blast radius describes and names. And the general practice of learning a program’s structure by analyzing its code without running it, which is how call edges are recovered in the first place, is static analysis. Each of those is a natural next step from here.