Skip to content
Multigrid

Extracting a Call Graph From a Codebase

10 min read · updated August 11, 2026

A static call graph is an approximation with a known direction of error, and a tool that does not tell you which direction is not usable. This one builds the graph in about sixty lines and then says exactly what it is missing.

What edge you are extracting

“A calls B” can mean at least three things and they have different truth conditions. May-call: some execution might invoke B from A. Must-call: every execution does. Does-call: an observed execution did, which is dynamic analysis and requires running the program.

A syntactic extractor like the one below computes something narrower than may-call: it reports a call expression whose callee name it can match to a definition it has seen. That both over-approximates — calls inside branches that never execute are still edges — and under-approximates, because anything indirect is invisible. Both errors are acceptable for search ranking and code navigation. Neither is acceptable for dead-code elimination or security reachability analysis, where a missed edge is a wrong answer with consequences.

Be clear too about the node the edge connects. A call graph whose nodes are functions is what you want for navigation. A call graph whose nodes are files is much easier to build and answers a different, coarser question. And a call graph whose nodes are call sites — distinguishing the two places in a function that both call save() — is what you need for anything path-sensitive, and it multiplies the node count several-fold. The script below uses functions as nodes and collapses repeated calls into one edge, which is the right choice for search and the wrong one for tracing a specific execution.

Setup

  1. Install the parser and one grammar: pip install tree-sitter tree-sitter-python. The grammar packages ship compiled, so there is no build step.
  2. Point the script at a directory of Python files. Anything with a handful of modules works; a project with 20–200 functions makes the output readable.
  3. Run it. It prints the edges and the calls it could not resolve, which is the more interesting half of the output.

The script

# callgraph.py — build a call graph with tree-sitter
import sys, pathlib
from collections import defaultdict
import tree_sitter_python as tspython
from tree_sitter import Language, Parser, Query, QueryCursor

PY = Language(tspython.language())
parser = Parser(PY)

DEFS = Query(PY, """
(function_definition name: (identifier) @def.name) @def.node
""")

CALLS = Query(PY, """
(call function: (identifier) @call.name) @call.node
(call function: (attribute attribute: (identifier) @call.name)) @call.node
""")

def qualified(node, path, src):
    """Walk up to build Module.Class.func for a definition node."""
    parts = []
    cur = node
    while cur is not None:
        if cur.type in ("function_definition", "class_definition"):
            name = cur.child_by_field_name("name")
            if name is not None:
                parts.append(src[name.start_byte:name.end_byte].decode())
        cur = cur.parent
    parts.append(path.stem)
    return ".".join(reversed(parts))

def enclosing_def(node):
    cur = node.parent
    while cur is not None and cur.type != "function_definition":
        cur = cur.parent
    return cur

definitions = {}          # short name -> [qualified names]
edges = defaultdict(set)
unresolved = defaultdict(int)
trees = []

root = pathlib.Path(sys.argv[1])
for path in sorted(root.rglob("*.py")):
    src = path.read_bytes()
    tree = parser.parse(src)
    trees.append((path, src, tree))
    for _, caps in QueryCursor(DEFS).matches(tree.root_node):
        node = caps["def.node"][0]
        name = caps["def.name"][0]
        short = src[name.start_byte:name.end_byte].decode()
        definitions.setdefault(short, []).append(qualified(node, path, src))

for path, src, tree in trees:
    for _, caps in QueryCursor(CALLS).matches(tree.root_node):
        node = caps["call.node"][0]
        name = caps["call.name"][0]
        callee = src[name.start_byte:name.end_byte].decode()
        owner = enclosing_def(node)
        caller = qualified(owner, path, src) if owner else f"{path.stem}.<module>"
        targets = definitions.get(callee)
        if targets is None:
            unresolved[callee] += 1          # builtin, third-party, or dynamic
        elif len(targets) == 1:
            edges[caller].add(targets[0])
        else:
            for t in targets:                # ambiguous: same name, many defs
                edges[caller].add(t + "  [ambiguous]")

for caller in sorted(edges):
    for callee in sorted(edges[caller]):
        print(f"{caller} -> {callee}")

print("\nunresolved callees (top 15):", file=sys.stderr)
for name, n in sorted(unresolved.items(), key=lambda kv: -kv[1])[:15]:
    print(f"  {name}  x{n}", file=sys.stderr)
$ python callgraph.py ./src
billing.charge_order -> billing.apply_tax
billing.charge_order -> tax.lookup_rate
billing.apply_tax -> tax.lookup_rate
api.post_order -> billing.charge_order

unresolved callees (top 15):
  round x7
  len x5
  requests.get x2

Resolving a call to a definition

The two-query structure is doing the real work. The definitions pass builds a name table before any call is examined, because a call can appear before its callee’s definition in file order and in a different file. Only then does the calls pass run.

Two details in the query are worth reading closely. The CALLS query has two patterns because Python spells a call two ways: foo() has an identifier as the function, while obj.foo() has an attribute whose attribute: field holds the method name. A one-pattern query misses every method call, which in object-oriented code is most of them, and the resulting graph looks plausible while being mostly empty. And enclosing_def walks upward from the call node rather than tracking state during a downward traversal, which handles nested functions and comprehensions correctly with no bookkeeping.

Matching a call to a definition by short name is the deliberate simplification, and the [ambiguous] marker is how the script admits it. A repository with four methods called run gets four edges from every call to run, at most one of which is real. Count the ambiguous fraction of your edges before trusting the graph: if it is small, name matching was adequate; if it is a third, you need real name resolution, and PyCG — Salis and colleagues, ICSE 2021 (“PyCG: Practical Call Graph Generation in Python”) — implements the analysis this script deliberately skips.

The unresolved histogram is not a defect report, and it is worth reading rather than suppressing. Most entries in it are builtins and third-party functions, which are correctly outside a graph of your own code — round and len in the sample output are not missing edges, they are calls that leave the corpus. What you are looking for in that list is a name that plainly belongs to your project and still failed to resolve, because that indicates either a file the walker never visited or a definition form the query does not match: a class defined with a metaclass, a function produced by a decorator factory, or a method assigned rather than declared. Each such pattern is a one-line addition to the definitions query, and fixing the top two or three usually accounts for most of the gap.

Scaling this beyond a small project changes little in the logic and a lot in the bookkeeping. The definitions pass must complete over the whole corpus before the calls pass begins, so both passes hold state proportional to the number of symbols rather than the number of files, which is fine — a million symbols is a modest dictionary. What does not scale is holding every parse tree in memory, as the script above does for clarity. Parse twice instead, or persist the definitions table between passes.

The edges this cannot see

State these in whatever you build on top of the graph, because a user who thinks the graph is complete will draw false conclusions from it.

  • Dynamic dispatch. getattr(obj, name)(), globals()[name](), a handler looked up in a dict by a string key. The callee name does not appear as a token anywhere.
  • Higher-order calls. A function passed as an argument and invoked inside the callee. The edge exists at runtime and is not written down at either site.
  • Framework entry points. A route handler, a Celery task, a signal receiver, a pytest fixture. Nothing in your code calls them; the framework does, usually via a decorator that registers them. They appear as unreachable roots.
  • Cross-language and cross-process edges. An HTTP call, a queue message, a subprocess, a call into C. The graph stops at the language boundary, which in a service-oriented system means it stops before the interesting part.
  • Inheritance. A call to self.process() may land in any subclass override. Without a class hierarchy the script resolves it to whichever definitions share the name.

For search ranking that incompleteness is tolerable, because a missing edge costs you some recall on neighbourhood expansion and nothing else. Two cheap improvements pay for themselves: index decorator names so framework entry points can be labelled rather than reported as dead, and record the unresolved-callee histogram permanently. A sudden jump in it after a refactor is a reliable signal that the graph has quietly stopped describing the code.

Related