Edu Sanchez

Linking a call to its method without a compiler

The graph in Semantic Graph is only as good as its CALLS edges. If a call from OrderController.submit to OrderService.placeOrder is missing, the impact analysis in the first post will happily tell you nothing reaches placeOrder. Getting those edges right, across nine languages and a few hundred repositories, is where most of the effort went.

This post is about how a call in the source becomes an edge in the graph, and about the cases where it does not.

Why not use a compiler

The honest answer to “how do you know what a call points at” is that a compiler knows. It has the types, the imports, the classpath and the generics. If you can run the compiler, use it.

We could not. Nine languages means nine toolchains. Hundreds of repositories means hundreds of build setups, many of them depending on internal artifacts that the indexer has no access to. A full build per repository, per commit, on an indexer that has to finish in minutes, was never going to happen.

So Semantic Graph parses without building. Every language goes through tree-sitter, which gives you a concrete syntax tree from the source text alone. It does not care whether the code compiles. It is fast, it recovers from syntax errors, and it has a grammar for every language we use.

The cost is that tree-sitter has no idea what type anything is. It sees service.placeOrder(order) and can tell you there is a method call named placeOrder on something called service. What service is, and therefore which placeOrder this is, is our problem.

What the parser writes down

There is one parser per language, between a few hundred and fifteen hundred lines each, about eight thousand lines in total. They all produce the same shape: a ParsedFile with imports and a list of ParsedClass, each with fields and a list of ParsedMethod. The method carries the parts that matter later. Its parameters and local variables with their declared types. Its return type. And a list of raw call expressions, as strings.

The call extraction is a tree walk. Here is the Java one, cut down:

def _walk(n):
    if n.type == "method_invocation":
        obj = n.child_by_field_name("object")
        name = n.child_by_field_name("name")
        if obj:
            calls.append(f"{_receiver(obj)}.{_text(name)}")   # service.placeOrder
        else:
            calls.append(_text(name))                         # validate
    elif n.type == "object_creation_expression":
        calls.append(f"new:{_text(n.child_by_field_name('type'))}")  # new:OrderService
    for child in n.children:
        _walk(child)

Three shapes come out of it. A qualified call like service.placeOrder. A bare call like validate. A constructor like new:OrderService. The parser does not try to resolve any of them. It records what it saw and moves on.

That split is deliberate. Parsing runs in a process pool, one file at a time, with no knowledge of any other file. Resolution needs the whole repository. So resolution happens later, in a separate pass, against the graph.

Two passes, and the phantom in between

Indexing a repository has two phases. The first writes every file into the graph with what the parser knows: classes, methods, fields, and edges for the things that are unambiguous, like HAS_METHOD or DECLARES.

Some edges point at things that may not exist yet. OrderServiceImpl implements OrderService needs an OrderService node, but the file that declares it may not have been written. So the writer creates a placeholder: a node with the right label and a name, but no fqn. We call them phantom nodes.

The second phase, resolve_references, runs once every file in the repository is in. Its first job is to find every phantom that now has a real counterpart, and move the edge:

MATCH (source)-[r:IMPLEMENTS]->(phantom)
WHERE phantom.fqn IS NULL AND phantom.name IS NOT NULL
MATCH (real:Interface)
WHERE real.name = phantom.name
  AND real.fqn IS NOT NULL
  AND real.project = source.project
MERGE (source)-[:IMPLEMENTS]->(real)
DELETE r

The same index-time / resolve-time split shows up everywhere in the code, always for the same reason: the target may not be written yet.

Resolving a qualified call

Now the interesting part. The resolver loads a few maps from the graph into memory. Which class each method belongs to. The declared type of every field, per class. The parameter types and return type of every method. The inheritance tree, and which classes implement each interface. Then it works through the raw calls in plain Python, no Cypher, so the logic is unit-testable.

For service.placeOrder, the receiver service is looked up in the caller’s variables: its own parameters, its class’s fields, and the fields of every parent class. If service is declared as OrderService, the call resolves to OrderService.placeOrder, and because OrderService is an interface with two implementations, the edge fans out to both. That fan-out is a choice. For impact analysis, a false extra caller is cheaper than a missed one.

Chained calls go through return types. getService().placeOrder(order) looks up getService in the return-type map of the caller’s class and its parents, gets OrderService, and continues from there. factory.create().run() resolves the field, then the return type of create, then run.

this.method() becomes a bare call. super.method() resolves against the parent classes. Array indexing is stripped. Casts and parentheses are unwrapped before the receiver is read.

And there is a noise list per language. toString, equals, hashCode, get, size and a few dozen more are dropped before resolution. Not because they are wrong. An edge from every method to String.toString makes the graph heavier and the impact analysis noisier, and nobody has ever asked what breaks if they change toString.

Resolving a bare call

A bare validate() is harder, because there is no receiver to look up. The resolver goes through seven tiers, in order, and takes the first match:

  1. A method called validate in the same class.
  2. A method called validate in an ancestor class, found by walking EXTENDS upwards.
  3. A method called validate on an interface the class implements.
  4. A class imported by name that has a validate. import com.example.Validator then validate() on it.
  5. A static import. import static com.example.Validator.validate.
  6. A wildcard import. import com.example.util.* and any class in that package with a validate.
  7. Another function in the same source file.

The seventh tier exists because of TypeScript and JavaScript. Those parsers turn each top-level function into its own node. A call to a sibling function in the same module then matches none of the class-based tiers, even though it is the most local resolution possible. It runs last, so it only rescues calls the other tiers left unresolved and changes nothing for the JVM languages.

Anything that falls through all seven is counted, not guessed. The resolver reports total_raw_calls, calls_created, noise_filtered and unresolved for every run, and the unresolved number is the one I watch.

Crossing repositories

Within one repository the resolver has every class. Across repositories it does not, and this is where the value of the graph is, because the dangerous calls are the ones into a shared library maintained by another team.

A separate pass, resolve_cross_project, runs after all repositories in a product are indexed. For each repository it reads the imports that point at classes which exist in a different repository, and resolves the qualified calls against those. C++ is the special case. Its imports are file paths, so it matches the header’s file name against class names in other repositories instead.

The pass is not incremental. It deletes every cross-repository CALLS and INSTANTIATES edge and recreates them. That sounds expensive, and it used to take minutes. After the query work described in the previous post it takes seconds, so we stopped worrying about it.

Code that is not code

Some of the most important edges in the graph do not come from a call expression at all.

One of our codebases has a set of Groovy scripts that are loaded at run time by a class asking the classpath for a glob pattern. Nothing references those scripts by name. Parsed on their own, they are orphans that never show up in any blast radius. So the indexer reads the resource pattern out of the loader’s source and stores it on the loader’s node. The resolve pass then expands it into a LOADS edge per matching script, once the files exist. Ask what breaks if you change the loader and the scripts appear, labelled as loaded.

Tests are linked the same way, by convention rather than by call. OrderServiceTest.java gets a TESTS edge to OrderService.java, in every language, so the impact analysis can tell you which tests to run.

And a method inside a DSL block that assigns a property gets a SETS edge to it. A field that is only ever written from a Groovy script still answers “what touches this”.

There is also a small metric called degraded_units. When a parser hits a grammar gap and falls back to a coarser reading of a block, it counts it. The count is logged per repository so that silence never reads as full coverage. That one exists because I was fooled by it once.

Where it gives up

Reflection. Dependency injection by string name. Dispatch through a generic that the parser cannot see. Anything resolved at run time by a framework we did not teach the parser about. Those calls end up in unresolved, and the API says so instead of guessing.

The name-based tiers can also produce false positives. Tier six, the wildcard import, will link validate() to any validate in that package. I accepted that. For the question this graph exists to answer, one extra caller in the list costs a minute of reading. One missing caller costs an incident.

The way I kept the balance honest was iteration. I ran the parsers over our real repositories, again and again, and went into the graph to check by hand. Are the calls there? Does the interface resolve to the right implementation? Does the Groovy script show up? Every time the answer was no, the case became a fixture and a test. There are around 1,600 of them now, and most of the parser ones started as something the graph got wrong.

The next post moves up to the API, and to why an agent gets one endpoint that does sixteen things instead of sixteen endpoints.

All posts