A user base class imported from another module resolves only if its module is translated first

[khatchad]

Summary

A user class whose base is imported from another analysed module gets that base as its superclass only when the base's module is translated before the subclass's module. Otherwise the subclass silently falls to object, with no MissingType recorded, so no later pass can repair it. Modules are translated in the iteration order of the module collection handed to the engine, so the class hierarchy, and with it the call graph, depends on how the embedding client constructs its module collection.

This is construction dependence, not nondeterminism. A given client gets the same graph on every run, because its collection iterates the same way every time. Two clients analysing the same files get two different graphs, each internally stable and reproducible, and nothing announces the difference. A flake disagrees with itself and so gets noticed. This cannot, which is why every instrument that looks for order effects by looking for instability under repetition passes it.

Measured on master c94b03d0a.

The Mechanism

PythonCAstToIRTranslator.defineType chooses the superclass as the first non-missing supertype that has an entry in walaTypeNames:

Set<CAstType> present =
    cls.getSupertypes().stream().filter(t -> !(t instanceof MissingType)).collect(Collectors.toSet());
TypeName superName =
    present.stream()
        .map(walaTypeNames::get)
        .filter(name -> name != null)
        .findFirst()
        .orElseGet(() -> summaryShellSuperName(cls).orElse(PythonTypes.object.getName()));

Two facts make this order-sensitive.

1. The parser's type dictionary is one CAstTypeDictionaryImpl shared by every module in the analysis, and visitClassDef maps each class under its simple name at parse time. The loader parses every module before translating any, so at translation time types.getCAstTypeFor("MessagePassing") hits in every order. The base is therefore never a MissingType.
2. The registry walaTypeNames is filled by defineType itself, when the base's own module is translated. A base whose module comes later in the collection has no entry yet.

The null-entry skip was added for #657 on the reading that a null entry means the base name mis-resolved to a same-named class in another module. A null entry also means the base's module has simply not been translated yet, and the two cases are indistinguishable at that point. In the second case the class is defined with object as its superclass and an empty missing-type set, so the summary-shell fallback never engages and nothing downstream can tell the class was ever declared with a base.

Measured

A public graph neural network library (used here as the example) declares class MessagePassing(tf.keras.layers.Layer) in messagepassing.py and class TextGCNConvolution(MessagePassing) and class GraphSAGEConvolution(MessagePassing) in two sibling modules that import it by name. The same 94 files, the same python path, one SourceURLModule per file, and a LinkedHashSet whose only difference between the two arms is the sort direction of the file paths:

Module order	Call-graph nodes	TextGCNConvolution superclass	MessagePassing._aggregate_function nodes	MessagePassing.propagate nodes	MessagePassing.__init__ nodes
Ascending path order	13938	Lobject	0	0	0
Descending path order	16274	Lscript nlpgnn/gnn/messagepassing.py/MessagePassing	46	30	22

ASCII sorts GSConv.py and TGCNConv.py before messagepassing.py, so ascending order translates both subclasses before their base. A trace inside defineType shows the two lookups directly. Ascending order:

PROBEDEF define=script nlpgnn/gnn/GSConv.py/GraphSAGEConvolution supers=[MessagePassing:dictHit:registered=false ] chosen=Lobject
PROBEDEF define=script nlpgnn/gnn/TGCNConv.py/TextGCNConvolution supers=[MessagePassing:dictHit:registered=false ] chosen=Lobject
PROBEDEF define=script nlpgnn/gnn/messagepassing.py/MessagePassing supers=[tf.keras.layers.Layer:MISSING:registered=false ] chosen=Ltensorflow/keras/layers/Layer

Descending order:

PROBEDEF define=script nlpgnn/gnn/messagepassing.py/MessagePassing supers=[tf.keras.layers.Layer:MISSING:registered=false ] chosen=Ltensorflow/keras/layers/Layer
PROBEDEF define=script nlpgnn/gnn/TGCNConv.py/TextGCNConvolution supers=[MessagePassing:dictHit:registered=true ] chosen=Lscript nlpgnn/gnn/messagepassing.py/MessagePassing
PROBEDEF define=script nlpgnn/gnn/GSConv.py/GraphSAGEConvolution supers=[MessagePassing:dictHit:registered=true ] chosen=Lscript nlpgnn/gnn/messagepassing.py/MessagePassing

The dictionary hit in both orders. Only the registration differed. Both predictions were written down before the runs and both landed.

Two further arms show where real clients land. The whole-project test harness builds a HashSet of URL modules and, for these files, reproduces the ascending result byte for byte. An embedding client that walks the project directory and builds one SourceFileModule per script, keyed on the absolute path, reproduces the descending result byte for byte, and its logs have reported 46 nodes for _aggregate_function across several engine versions and several independent runs. Neither client chose its order, both are legitimate callers, and each is stable on its own. A third hash order resolved exactly one of the two subclasses.

A Reading Tested And Refuted

One candidate explanation for the 46 nodes was a method analysed as a synthetic entry point, with parameters that exist and receive nothing. It does not hold. Every one of the 46 nodes has callers, every caller is the method's own trampoline, and no arm produced a node without a resolved call. In the descending graph the inherited method is reached by ordinary dispatch through the resolved base.

Consequences

• Every node count, every reachability claim, and every parameter state taken from a whole-project analysis carries the module order it was taken under. A test harness and an embedding client analysing the same files can disagree by thousands of nodes without either being wrong about its own graph.
• Resolve imported/cross-module base classes instead of falling back to Lobject #571 describes a cross-module base becoming a MissingType that falls to object. That description is true of one module order and false of the other, which is a different and stronger claim than the one it makes. The issue stays open for its symptom.
• Both graphs are the analysis, depending on who built the modules. A pin, a census, or a node count is therefore a statement about a construction, not about the engine alone, until the order dependence is removed.
• The order-invariance job in CI perturbs the type resolver's order, not the module order. It also looks for instability under repetition, and this defect is stable under repetition by construction, so no such job could catch it.
• The neighbouring lookup was checked. The import-binding registry introduced for A layer's add_weight-created weight has an empty points-to set where call reads it, in every context of the vendored Conv1d, so neither the matmul's dtype rule nor its feed can use it #938 has the same publish-then-read shape, but it publishes during the parse phase of every module and reads only at translation time, so under the loader's parse-all-then-translate contract it is order-robust by construction. It is also tested both ways in a five-file fixture with a certified break. The registry here, walaTypeNames, is filled during translation and read during translation, which is the difference.

Fix Directions

Any of these removes the order dependence. Choosing among them is a separate decision.

• A barrier: register every class's WALA type name in a first pass over all top-level entities, and resolve superclasses in a second pass, so walaTypeNames is complete before any lookup.
• Resolve the superclass by the base's own composed entity name instead of by a registry filled during translation.
• Translate modules in import-dependency order.

Whichever is taken, the null-entry skip from #657 needs to distinguish "mis-resolved" from "not yet translated", since today it treats both as "no base".

Reproduction

A test in the v2 package that builds the engine twice over the same whole-project fixture with a LinkedHashSet of SourceURLModules, once in ascending and once in descending path order, and reads callGraph.getNodes(...) for Lscript nlpgnn/gnn/messagepassing.py/MessagePassing/_aggregate_function through AstMethodReference.fnSelector. The two counts are 0 and 46 on master c94b03d0a. The same harness, with the order fixed, is the regression guard.

[khatchad]

Two measurements that bear on the choice among the three directions.

The Barrier Direction Is Three Registries, Not One

Pre-registering every class's type name before translation links every superclass in both module orders, but the inherited method still has no call-graph node in the order that translates the subclass first. The class-object emission's inherited-member propagation reads two more things that exist only once the base's module has been translated: the base's class definition in the loader and the base's emitted member list. On the largest whole-project fixture, names alone grow the graph from 13938 to 14294 nodes. Names, definitions and member lists together give 16274, the graph a directory-walking client analyses. So the barrier direction means defining every class and computing every class's inherited member list ahead of translation, and any later per-class registry has to join them or the defect reopens. Resolving the superclass by the base's composed name alone is the names-only row, and it leaves the method nodes missing.

Dependency-Ordered Translation Has No Reachable Residual

Translating a base's module before its subclass's module needs no registry, and its only residual is a cycle in the base-dependency graph, where it would fall back to the given order. That residual is unreachable for module-level code by Python's own semantics: a base must be bound when the class statement executes, and in a cycle one of the two modules is still partially initialised, so the program does not run.

a.py:  from b import B      b.py:  from a import A
       class A(B): ...             class B: ...
                                   class C(A): ...

$ python3.10 -c "import a"
ImportError: cannot import name 'A' from partially initialized module 'a' (most likely due to a circular import)

Measured as well as argued: a pass over every multi-module fixture project in the repository (104 of them, 11 with cross-module base edges) finds no cycle. The only way to construct one that runs is a base import deferred into a function body, which is the construct of #945 and does not dispatch today in any order.

So the comparison is: three pre-filled registries and an unconditional guarantee, against no registries and a limit reachable only through a construct that cannot execute in its ordinary form. The scoped base resolution of #946 computes, for every class, which script its base comes from, which is exactly the dependency edge the ordering needs, so the two fixes share one mechanism.

[khatchad]

Landed on master as ponder-lab@7167da714, the squash of ponder-lab#868, together with the fixes for #946 and #945. The three fixes were separate commits in the pull request so that a regression bisects to one of them, and the squash collapsed them on master. They remain reachable at the pull request's head ref: git fetch origin refs/pull/868/head recovers the five-commit chain (scoped lookup, ordering, nested-class dispatch, the loader's per-analysis reset, the class-path fixtures) as walkable history.

This issue stays open until the emitted types are next regenerated and the affected rows move.