# Inferring Pluggable Types with Machine Learning

Kazi Amanul Islam Siddiqui  Department of Computer Science
New Jersey Institute of Technology
Newark, USA
<EMAIL_ADDRESS>Martin Kellogg  Department of Computer Science
New Jersey Institute of Technology
Newark, USA
<EMAIL_ADDRESS>
###### Abstract

Pluggable type systems allow programmers to extend the type system of a
programming language to enforce semantic properties defined by the programmer.
Pluggable type systems are difficult to deploy in legacy codebases because
they require programmers to write type annotations manually. This paper
investigates how to use machine learning to infer type qualifiers
automatically. We propose a novel representation, NaP-AST, that encodes
minimal dataflow hints for the effective inference of type qualifiers. We
evaluate several model architectures for inferring type qualifiers, including
Graph Transformer Network, Graph Convolutional Network and Large Language
Model. We further validated these models by applying them to 12 open-source
programs from a prior evaluation of the NullAway pluggable typechecker,
lowering warnings in all but one unannotated project. We discovered that GTN
shows the best performance, with a recall of .89 and precision of 0.6.
Furthermore, we conduct a study to estimate the number of Java classes needed
for good performance of the trained model. For our feasibility study,
performance improved around 16k classes, and deteriorated due to overfitting
around 22k classes.

###### Index Terms:

component, formatting, style, styling, insert

##  I Introduction

When programmers write code, they are often aware of semantic properties that
a variable must adhere to but which are not checked by the type system of
their programming language. Pluggable type systems are a method of adding
custom _type qualifiers_ to a language. A pluggable typechecker statically
checks these user-defined qualifiers and warns about potential violations at
compile time. For example, PUnits [1] adds qualifiers for scientific units,
while Uber’s NullAway [2], Meta’s NullSafe [3], and the Checker Framework [4,
5] enforce programs do not crash due to null-pointer dereferences with a
@Nullable qualifier. A key barrier to bringing legacy codebases into
compliance with a typechecker is that developers must write these qualifiers
into their code to see the full benefit of the tools. The state of the
practice when deploying a new typechecker on a legacy codebase remains manual
annotation: that is, in practice, type qualifiers are written by hand. The
high cost of this manual process discourages developers from using these
systems, despite their promise to improve code quality. This paper addresses
the problem of bringing a legacy codebase into compliance with a typechecker
by automatically inferring type qualifiers.

Recently, researchers have proposed using machine learning to solve a similar
problem: inferring type annotations for untyped Python or TypeScript programs
[6, 7, 8, 9, 10, 11]. This problem shares a key feature with our problem of
inferring type qualifiers for a legacy codebase: in both cases, the programs
were written _without feedback from the typechecker_ , so we expect the
programs not to typecheck cleanly (with any set of annotations). Experimental
results suggest that these techniques outperform traditional deductive type
inference techniques, so in this paper we investigate whether a similar
approach can work for the problem of inferring pluggable types.

However, techniques for inferring types in Python or JavaScript programs are
not immediately transferrable to our setting, because of three key
differences. First, when inferring types for Python or JavaScript, the
property of interest is _known in advance_ : the type system is fixed (it
enforces “tradtional” type safety: objects do not try to perform invalid
operations). A key advantage of pluggable type systems is their
customizability: each type system enforces its own rules. So, we require a way
to customize our inference approach that does not require us to start over
from scratch for each new type system. Second, for a given pluggable type
system, the space of possible type qualifiers is fixed: for example, a
typechecker for preventing null dereferences might only contain the qualifiers
@NonNull and @Nullable. By constrast, when inferring types for e.g., Python,
the space of possible types is infinite and has a long tail, because of the
presence of user-defined types. That is, in the standard setting the type
_system_ is fixed and the number of types is infinite; but in the pluggable
types setting there are infinitely-many possible type systems, but each has a
_finite_ , known universe of types. Third, machine learning is data hungry:
approaches for popular languages like Python can assume the existence of a
large corpus of human-written types in open-source software. By contrast, the
customizability of pluggable types means that most type systems have few
users: in fact, pluggable type systems are sometimes designed only for a
single program! So, to apply machine learning techniques to the pluggable type
inference setting, we need to understand how much data is actually required to
make them effective. These differences inspired us to investigate three high-
level research questions:

  * •

RQ1: What _kind of ML model_ should we use, and how should we post-process its
output?

  * •

RQ2: How should we _encode_ the program in a type-system-specific way to train
the model?

  * •

RQ3: How much _data_ do we need to make that model effective at inferring
qualifiers in practice?

The results of our investigation of these questions allows us to propose a
general pipeline for training an ML model to infer type qualifiers for a given
pluggable type system.

The state-of-the-art models [12, 6, 7] for inferring types in Python and
JavaScript leverage the _type dependence graph_ , a graph that encodes the
type system’s semantics and which is therefore unsuitable for representing
pluggable type systems because each type system has its own rules. Prior works
used a variety of model architectures, including graph models and text-based
models. For example, Typilus [12] learns a type space, STIR [6] uses a BiLSTM
for incomplete code, and Type5 [7] uses a pre-trained seq2seq model. The
differences between the pluggable types setting and the Python/JavaScript
setting, however, inspired us to investigate RQ1 by evaluating a set of
relatively-simple models. In particular, we eschew time-series models like
BiLSTM (which are effective for sequential data, like recognizing the content
of a video, but very expensive during training and inference) because we
hypothesize that they may not be needed to predict pluggable type qualifiers.
We considered two graph models and one text-based model. The two graph models
are a baseline [13] graph convolutional network (GCN) model [14] and a more-
capable graph transformer network (GTN) model [15], which extends the GCN’s
capabilities by adding the ability to reason about multiple edge types (i.e.,
hypergraphs). The text-based model is a large language model (LLM) [16]; LLMs
have performed well on coding tasks recently, but they operate in reduced
context because of their token limit.

To investigate RQ2, we considered two techniques: 1) prompt the LLM about
which program locations should be annotated with a type qualifier, and 2)
develop a novel training methodology for building a type-system-specific graph
encoding. The first technique was relatively ineffective, so we pursued the
second. Our graph encoding methodology uses ablation studies to retain
information that is useful for predicting the type qualifiers used by a
particular type system. This process results in a novel program encoding that
we call a _Name-augmented, Pruned Abstract Syntax Tree_ (NaP-AST), which we
describe in section III. A NaP-AST encodes the parts of the program’s
structure that are relevant to the type system of interest, along with name
information that ties related program elements together, into a graph that is
a suitable input to a graph-based model.

To evaluate these models and encodings, we conducted a feasibility study. Of
the commonly used type qualifiers, those for nullability in Java are the most
common. We therefore conducted our feasibility study on nullness: if there is
not enough data for Java nullness type qualifiers to train an effective model,
there is not enough data to train an effective model for _any_ pluggable type
system. First, we collected a dataset from Github of Java classes, each of
which uses one of 31 different @Nullable annotations. After cleaning, this
dataset contains 32,370 classes; more details about the dataset and its
collection are presented in section IV. We then used our methodology for
building a NaP-AST encoding to derive a NaP-AST encoding for nullness. Then,
we trained the three models using this dataset: the two graph models (a GCN
and a GTN) using the derived NaP-AST encoding, and the text-based LLM using
syntax-based code chunking. We then compared their performance on 12 open-
source projects that had previously been annotated for the popular NullAway
typechecker [2]. The GTN outperformed the other models we evaluated: the GCN
requires additional postprocessing to reach acceptable performance, while the
LLM is too limited in token capacity to be effective on large projects. Our
best model (the GTN) achieves 89% recall of the human-written type qualifiers
and 60% precision; its inferred annotations eliminate 60% of the NullAway
warnings that a human would need to triage (a proxy for human effort). Our
success for nullability suggests that our approach may be effective with other
type qualifiers, but unfortunately we lack enough data for any other type
qualifier to test this hypothesis.

However, to assist future researchers or practitioners who would like to train
a similar model for another type qualifier (and answer RQ3), we explore how
much training data one needs for adequate performance. We rebuilt our best
model with random samples of the dataset and re-ran the evaluation to show how
much data it needs before it acheives good performance. We found that around
16k human-annotated classes were needed: a large but not impossible-to-reach
number. We counted 217,922 annotations in these classes.

The primary contributions of our paper are:

  * •

A novel methodology to construct a per-type-system graph encoding of programs
(NaP-ASTs) to train deep-learning graph models like GCNs and GTNs (section
III);

  * •

A dataset of 32,370 Java classes annotated with @Nullable that enables our
feasibility study (section IV);

  * •

A comparison of three model architectures (GCN, GTN, and LLM) that shows that
the GTN is best for the problem of inferring pluggable types in our
feasibility study (section VI-A), with open-source models and data;

  * •

A study of the amount of data required by our best GTN model on the task of
inferring type qualifiers for adequate performance (section VI-B).

##  II Background: Model Architectures

This section provides background on the three considered models: graph
convolutional networks (GCNs), graph transformer networks (GTNs), and large
language models (LLMs). We focus on the model architectures and their salient
features with respect to type qualifier inference, and also introduce the
specific models that we use in our experiments.

###  II-A Graph Models

####  II-A1 GCN

Graph Convolutional Networks (GCNs) are a class of neural networks designed
for graph data. Type qualifier prediction can be modeled as a graph data task
because ASTs can be represented as a graph. GCNs use _graph convolution_ , a
propagation rule that updates the feature representation of each node by
aggregating features from its neighbors (and the node itself). For AST
prediction, GCNs can be particularly effective due to explicitly modeling
local context: ASTs are inherently hierarchical and structured, where the
context around a node (e.g., its parent or children nodes) significantly
influences it. GCNs leverage this local structure efficiently. They are also
efficient in learning spatial features, which have been helpful for ASTs [17].

A more specialized graph neural network model might outperform a GCN by
adapting to heterogeneous relationships. If different types of connections
between AST nodes (e.g., data flow vs. control flow) play a significant role,
models within the broader GNN category designed to handle such heterogeneity
might be more effective. We investigate this possibility by comparing GCN with
such a model, GTN. Certain GNN architectures might also be better suited for
incorporating global context or long-range dependencies within the AST, which
could encode dataflow information.

####  II-A2 GTN

GCNs assume that the provided graphs are homogeneous, i.e., they consist of
one type of nodes and edges. However, in uses cases like source code
annotation distinct edge types can alter the importance of each node. Taking
advantage of heterogenous graphs allows us to layer additional hints over bare
ASTs. This paper uses it to add a layer connecting names across an AST, which
provides dataflow hints.

To do so, we use the FastGTN model [18], which uses the meta-path, a multi-hop
sequence of connected nodes and edges in the graph with heterogeneous edge
types. Instead of ignoring the edge type information, breaking down a
heterogeneous graph into homogeneous graph by its meta-paths allows the model
to preserve this information. A Graph Transformer Network (GTN) [18] learns
the most informative meta-paths automatically for each task in an end-to-end
manner by selecting adjacency matrices through a 1x1 convolution with weights
from a softmax function. The GTN can learn arbitrary meta-paths with respect
to edge types and path length. GTNs consider multiple types of meta-paths
simultaneously by generating multiple graph structures: they set the output
channels of a 1x1 filter to the number of channels. After stacking $k$ GT
layers, multi-layer GNNs are applied to each channel of the output tensor. The
final node representations can be used for downstream tasks, by applying dense
layers followed by a softmax layer to the node representations.

A weakness of GTNs is that they are not scalable because of the high
computational cost and memory requirements when calculating and storing new
adjacency matrices at each layer. To address this, FastGTNs implicitly
transform the graph structures without storing the new adjacency matrices of
meta-paths, avoiding the need for explicit multiplications of large adjacency
matrices. This reduces the computational cost and memory usage while keeping
FastGTNs mathematically identical to GTNs. Even FastGTNs have serious
scalability limitations, which motivates our pruning strategies discussed in
section III; note that the primary scalability challenge for GTNs is fitting
the $n$-by-$n$ adjacency matrix they require into memory (where $n$ is the
size of the input)—even with “large” inputs, both training and prediction with
FastGTNs is relatively quick (see further discussion in section VI-A3).

####  II-A3 GCN vs GTN

The GTN is a generalization of a GCN that supports distinct edge types. This
allows the GTN to distinguish the AST and the name layer. While GCNs do not
automatically support this heterogeneous operation, they are a good baseline
for studies exploring advanced graph learning techniques [13]. because they
can integrate local neighborhood information through the graph convolution
operation.

###  II-B Text-based Model: the Large Language Model (LLM)

Magicoder [16] is a fully open-source, state-of-the-art LLM trained on a
dataset created from 75,000 synthetic instruction data generated using the
OSS-INSTRUCT approach. OSS-INSTRUCT involves generating coding problems from
real world snippets, ensuring diversity by incorporating a wide variety of
challenges, and enhancing the controllability of the output. Since Magicoder
has outperformed GPT 3.5 using only open source training samples, it is a
suitable baseline for comparison with other techniques.

The LLM approach leverages a vast knowledge base, ensuring a diverse
understanding of coding patterns and practices, significantly beneficial for
inferring type qualifiers by understanding the broader context and nuances in
code. LLMs have recently been used to great effect in a number of software
engineering domains [19]. The model’s limitation is that if certain edge cases
or less common programming constructs are underrepresented, the model’s
inference capability might be constrained for those scenarios. Crucially, LLMs
may struggle with deep semantic understanding of code, they are only
predicting the next token in a sequence. In practice, there are other limits
for using LLMs. For example, Magicoder limits its output to 2048 tokens.

##  III Encodings

This section details how we encoded the input programs for the two kinds of
models we consider: the graph-based models via our novel type-system-specific
NaP-AST encoding (which is described via the methodology to construct a NaP-
AST encoding for an arbitrary type system in section III-A) and the text-based
models via prompting (section III-B).

###  III-A Graph-based Encoding: the NaP-AST

This section describes our novel methodology for building a type-system-
specific program encoding for the graph models (GCN and GTN), which we call a
_Name-Augmented, Pruned Abstract Syntax Tree_ (NaP-AST). The encoding only
includes information relevant to the given type system, but is in a form
suitable for training a deep learning model. The overall methodology for NaP-
AST construction is shown in fig. 1.

1\. AST Extraction2\. Pruning3\. Name Augmentation4\. Statement Pruning5\.
Clustering6\. Training7\. Prediction8\. Post-processing Figure 1: Order of
steps in NaP-AST construction: 1. Extract AST (section III-A1). 2\. Prune
irrelevant nodes or types via proof (section III-A2) and via ablation studies.
(section III-A3) 3\. Augment the pruned AST by connecting the variables with
identical names (section III-A4). 4\. Prune irrelevant statements on the basis
of relevance (section III-A5). 5\. Cluster the ASTs by graph structure
(section III-A6). 6/7. Train or predict (section III-A7). 8\. If predicting,
post-process to ensure consistency (section III-A8).

The base of a NaP-AST is the program’s Abstract Syntax Tree (AST). The first
step (section III-A1) to construct a NaP-AST is to augment the AST with
additional nodes that model information traditionally stored in the AST
directly (for example, whether a declaration is public or private), thereby
making that information available to the deep learning model later. This is
necessary because the internal complexity of the AST data structure produced
by JavaParser is not visible to the deep learning model.

Figure 2: In heterogeneous graphs (i.e. having multiple edge types), a meta-
path is a sequence of connected nodes and edges, where each edge has a
distinct type.

The next step in constructing a NaP-AST is pruning information that is not
relevant to the property of interest from the graph produced by the previous
step. We do this by conducting a series of targeted ablation experiments: we
iteratively remove particular types of AST nodes (and all associated edges)
from the NaP-AST and retrain a preliminary model. Node types whose removal
does not negatively impact the F1 score of the preliminary model are removed
from all NaP-ASTs. Shrinking the size of the NaP-AST by removing irrelevant
information is critical to the scalability of our approach, since the model
architectures we consider are highly sensitive to the size of the input graph.
There are three pruning phases:

  1. 1.

prune nodes that are provably unrelated to the property of interest (section
III-A2).

  2. 2.

use an ablation experiment to prune _node types_ that are unrelated to the
target property (section III-A3). This pruning step occurs _before_ name
augmentation when processing the AST for a particular class.

  3. 3.

use an ablation experiment on program statement node types to prune _entire
subtrees_ under each type of node, as well as related nodes (section III-A5).
This pruning step occurs _after_ name augmentation when processing the AST for
a particular class, so we defer discussing it until after we introduce the
name-augmentation step.

Each pruning phase is theoretically optional, but we found that all three were
necessary to produce NaP-AST graphs that are small enough to realistically
train a deep learning model when we conducted our feasibility study.

The last part of NaP-AST construction is augmenting the graph with edges that
encode program elements that have the same name, which is described in section
III-A4. The goal of this step is to encode basic dataflow information in a way
that is visible to a deep learning model. For example, this stage enables a
model to determine that a parameter checked against null in a method should be
annotated as @Nullable by connecting the check to the parameter’s declaration.

Throughout this section, we assume the existence of a training dataset of
human-annotated code that contains type qualifiers for the type system of
interest. We discuss whether such datasets exist for real type qualifiers in
section IV.

####  III-A1 Abstract Syntax Tree Extraction

For each class in the training dataset, we first generate its Abstract Syntax
Tree (AST). Traversing the AST, we generate a graph consisting of nodes and
edges. Unlike HiTyper’s Type Dependency Graph [9], we have not attempted to
build a graph of type dependencies. We have been able to obtain good results
without creating a complex data structure. We think this is because pluggable
type systems are much simpler than the type system of a language. Each node is
represented by a node id, node type and a special field indicating whether the
node contained a type qualifier in the input data (and if, which type
qualifier). Any actual AST nodes for the type qualifiers generated by the
parser are discarded, so that the human-written type qualifiers are not
visible to the model during training. Edges in this graph are parent-child
connections represented as an adjacency list.

The graph contains two types of edges: parent-child, and child-parent.
Representing the internals of each block or statement by a different edge type
prevents relevant properties from leaking out into proximate but otherwise
unrelated nodes in the AST. On the other hand, we do want statements using the
same variables to be proximate in the graph. We achieve this later using the
name layer described in section III-A4.

We then add additional, useful information that is traditionally stored in the
AST nodes themselves—in particular, modifiers (e.g., public, static, etc.) —to
the graph’s structure, which makes it available to the models during training.
We created a single node in the graph for each modifier and connected the
modifiers to the relevant nodes using a multi-hot vector encoding. While this
may seem like an implementation detail, we mention it here because practical
parsers often store this important information not in the AST itself but in
fields that are lost if naïvely converted to a graph where each node has one
type. We can overcome this issue by representing both the node type and the
modifier using multi-hot encoding.

####  III-A2 Pruning Phase 1: Remove Provably-Unrelated Information

When considering a particular type system, we usually know that some parts of
the program are definitely completely irrelevant to the property of interest.
If we formalize that notion at the AST level, irrelevant parts of the program
can be immediately removed from the AST. For example, a pluggable type system
that tracks whether integers are non-negative (which would be useful as e.g.,
part of a larger system for typechecking array accesses) need not consider
parts of the program that do not interact with integers. Therefore, the first
pruning stage of NaP-AST construction is to remove any nodes that are provably
irrelevant. The set of nodes that are irrelevant will differ when constructing
a NaP-AST for each different type system; this pruning stage exists to allow
someone following our methodology to build an inference model for a new type
system to prune anything they know is irrelevant right away, before the more
complex pruning stages.

####  III-A3 Pruning Phase 2: Ablation by Node Type

Like some Java types are irrelevant for predicting pluggable types, so are
some AST node types. For example, MemberValuePair and IntersectionType nodes
produced by JavaParser would be irrelevant for predicting non-compound types.
To summarize the AST further, we conduct an ablation study on node types. For
each node type, we drop it and calculate the F1 score on a held-out test set.
We did the same test by dropping random nodes. For node types which get a
higher F1 score than dropping random nodes, we drop them from the AST.

####  III-A4 Name Augmentation

To inform the model of the identity of a candidate node, we layer a graph with
different node and edge types on top of the graph derived from the AST in
previous steps. This layer connects the names of the variables to nodes that
make use of those variables, using different node and edge types. This
improves accuracy by allowing the model to connect _uses_ of names to their
_declarations_. Since type annotations need to be placed on declarations, this
step is critical: the model must know that a particular test or assignment is
related to a specific declaration. For example, fig. 3 shows an example for a
variable named "x", which is connected as a separate graph layered over the
pruned AST.

The names are connected using a different edge type. The second set of edges
are stored in a different adjacency matrix.

This layer can be viewed as encoding a simplistic dataflow analysis, or
alternately as enabling the model to reason about basic dataflow. We chose to
add this graph layer at the encoding stage rather than running a dataflow
analysis directly because it was simpler, and in our experiments it appears to
work well in practice. Future work could investigate making dataflow
information available to model directly as an alternative to our name
augmentation strategy.

MethodDeclarationParameterAssignExpr"x" Figure 3: Name Augmentation. This
diagram shows the pruned AST as yellow nodes, and a node ("x") in the name
layer in green. All the nodes that use the same name are connected by a second
edge and node type.

####  III-A5 Pruning Phase 3: Ablation of Statement Subtrees

Even after the pruning phases described above, after name augmentation the
resulting graph is prohibitively large to train the graph-based models in
section II. So, we need another pruning strategy. Our key insight at this
stage is that many statements in the program are irrelevant to the property of
interest. For example, parts of the program that do not include any null
literals are unlikely to be related to nullability. However, dropping _all_
such statements hurts model performance (as measure by F1 score) too much, so
we performed an ablation study to determine which kinds of statements are safe
to prune. Our goal at this stage is to prune statements, their corresponding
subtrees, and any other related nodes. We use the name-augmentation layer
added to the graph in section III-A4 to determine which non-subtree nodes are
related to a statement: when we prune a statement and its subtree, we also
prune any node that is directly connected to the statement’s subtree via a
name layer.

####  III-A6 Clustering

In most machine learning projects, one cleans the dataset by pruning outliers.
Instead of trying to visualize the different kinds of graphs so that we can
prune outliers by hand, we clustered the dataset using k-means clustering and
trained a separate model for each cluster. We chose a value of k=5 by minimum
within-cluster variation with the elbow method [20]. This method raised the
overall F1 score by an average of approximately 0.5, so it is critically-
important to overall model performance.

####  III-A7 Prediction

A graph-based model typically makes a prediction for a single input graph (in
our case, a NaP-AST representing a single class) at a time. However, program
elements defined in one class are sometimes used in other classes in ways that
impact their nullability. To capture this phenomenon, we employ a _conjoined
prediction_ strategy: for each pair of classes in a target project, we predict
the nullability of all of their elements together, using JavaParser’s symbol
solver to connect the name layers of the NaP-ASTs if they have any elements in
common. The final prediction for an element’s nullability is the average of
the predictions across all pairs of classes. This technique increases the
consistency of the model’s prediction across classes: conjoined prediction
helps when an element is used in more than one class, but makes no difference
for elements that are not used in the other class for which predictions are
being made concurrently. In other words, this conjoined prediction strategy
allows the model to reason (in a limited way) about inter-class dataflow.

####  III-A8 Post-processing

Deep learning methods are good for finding recommendations through hidden
patterns in the data. Unfortunately, their outputs are not guaranteed to be
internally consistent. Post-processing steps remove obvious inconsistencies:
they certainly do not guarantee that the model’s outputs will be sensible.
They should, however, be conservative in a sense: the annotations they add or
remove from the model’s output must be guaranteed to make the resulting
annotation set for the whole program more consistent.

###  III-B Text Encoding

To have Magicoder place annotations, we could not provide it with complete
source files, because many were too large. We extracted segments of program
text that fit in its 2048 token limit (alongside our prompt) using simple
rules requiring the resulting text be syntactically complete. Without these
rules, Magicoder will break most code trying to fix syntactic errors. Our
prompting code’s rules try to include ending braces and complete loops,
methods or files where possible.

For each extracted segment, we gave a simple prompt, "Add $ANNOannotations to
the following Java code snippet where having them wouldimprove code quality.
Enclose code in ‘‘‘java...‘‘‘" (where $ANNO is the literal name of the desired
annotation: @Nullable in our feasibility study). If "‘‘‘java...‘‘‘" was in the
output, the part of the output contained within was written back into the
appropriate location in the program. Otherwise, we wrote back the original
unannotated code.

This prompting strategy is relatively primitive. There are two reasons for
this: first, the prompt is competing for space in the token limit with the
code. A longer prompt requires us to provide less code at a time to the model,
reducing the model’s performance. Second, the LLM’s performance was poor
enough relative to the graph-based models in our preliminary experiments that
it did not seem worthwhile to further optimize it. It can therefore be
regarded as a baseline in the experiments in the following sections.

##  IV Dataset

To evaluate the encodings in section III and to answer our other two research
questions—i.e., which model is best suited to the task and how much data is
actually required—we performed a feasibility study on the most popular
pluggable type system: preventing null-pointer dereferences in Java using a
@Nullable annotation. Multiple typecheckers for preventing this problem exist
and have been deployed in industry, including Uber’s NullAway [2], Meta’s
NullSafe [3], and the Checker Framework’s Nullness Checker [4, 5].

The first challenge in predicting nullability annotations is collecting
training data. Each nullability checker has its own set of annotations.
Further, there are annotations provided by frameworks (e.g., the JSR 305
nullability annotations in the JDK, or those provided by Android) that do not
have an associated checking tool. This fragmentation in the ecosystem means
that for any single nullability checker or annotation, there may not be
sufficient training data to build an effective model. (This mirrors the
general situation for pluggable typecheckers, wherein most checkers are used
by a relatively small number of projects, leading to a paucity of training
data when considering whether training a model is practical.)

Our key insight in dataset preparation is that the various nullability tools
all use similar definitions of @Nullable: it universally means “this element
may or may not be null.” Since the most widely-used pluggable typecheckers use
@NonNull as the default type for unannotated code (e.g., both NullAway [2] and
the Checker Framework [4, 5] use this defaulting scheme), bringing a program
into compliance with a typechecker usually requires a human to write mostly or
only @Nullable annotations. The consequence of this defaulting scheme is that
we can restrict a model’s goal to the prediction of only @Nullable
annotations: we do not need to directly predict @NonNull or any of the other,
more complex annotations used by various checking tools. In turn, the need to
only predict @Nullable means that we can _combine_ training data that uses
different @Nullable annotations, as long as those annotations have the same
semantics. We used every annotation in the comprehensive list of @Nullable
annotations with the same semantics in the Checker Framework’s manual [21].

We used the search feature of Sourcegraph’s CLI tool [22]to collect Java
classes that import various @Nullable annotations. We searched for @Nullable
annotations by themselves. However, this approach led to a dataset where
Jetbrains projects were overrepresented. We think this happened because
Jetbrains has the most popular projects that use the @Nullable annotation. We
switched to searching for a variety of Nullable imports to gather a diverse
dataset. We do not require code in our training set be checked by some
nullability tool: instead, we try to model where a human would write a
nullability annotation. E.g., @Nullable annotations that a human wrote as
documentation are also useful as training data.

Some classes, despite importing a nullability annotation, did not actually
contain any such annotations. After selecting only those classes that did, we
removed very small and very large classes. We removed very small classes
because in initial experiments, we found that keeping them in the training set
harms model performance: it assumes that all small classes have all @Nullable
members. We also removed classes that were too large to fit our training
pipeline. After all of these removals, we were left with 32,370 classes; we
removed 60,292 classes in total. Each class in this dataset contains one or
more @Nullable annotations.

##  V NaP-ASTs for Nullability

With the dataset in section IV, we trained the graph-based models (GCN and
GTN) by following the NaP-AST encoding method described in section III-A. Our
code, dataset, and experimental scripts are open-source and available [23]. We
call the resulting models NullGCN and NullGTN.

###  V-A NaP-AST Pruning

In this section, we describe the specific pruning strategies that we used for
each pruning phase described in section III-A.

####  V-A1 Phase 1: Pruning by Proof

Since primitive types cannot store null values in Java, we exclude them from
the nodes that the model is trained on. Nullability is relevant to most of the
program, but we expect that for other pluggable type systems that target rarer
problems, this step could prune dramatically-larger parts of the program. For
example, an instantiation of our methodology for a type system that detects
resource leaks could remove all parts of the program that definitely do not
manipulate resources (i.e., most of the program!).

####  V-A2 Phase 2: Pruning by Node Type

First, we conducted an ablation study over node types. We dropped each node
type and calculated the F1 score of a preliminary model on held-out testing
data.The results are plotted in fig. 4 (test runs were repeated 50 times each
to control for the statistical nature of the models). Note “<random>” in red
in fig. 4: this represents dropping nodes at random from the graph, without
regard to their type. We discarded all nodes of the types that appear to the
left of “<random>” in fig. 4: that is, node types whose removal damages the
model’s predictive ability less than removing random nodes. We connect the
children of dropped nodes to their parents.

For example, since humans often write @Nullable annotations on method
declaration nodes (to indicate nullable return types), dropping them
dramatically reduces the F1 score to about 0.66 . By contrast, node types like
MemberValuePair and IntersectionType seem to have no measurable impact on the
performance of the model, which makes sense: value pairs are unrelated to
reasoning about nullness. As another example, IntersectionType nodes indicate
a generic type construct—which is entirely orthogonal to nullness.

Dropping some node types suprisingly drops the F1 score (if
ClassOrInterfaceDeclaration is dropped, for example, the F1 score falls to
0.76). We determined via manual investigation that nodes of this type help
group the methods of nested classes, so even though they are rarely or never
nullable themselves, retaining them is important to model performance. Another
node type that helps group nodes together is BlockStmt; dropping them reduces
the F1 score to 0.77.

InstanceOfExprArrayInitializerExprTypeExprMethodCallExprForStmtVariableDeclaratorUnaryExprVarTypeNullLiteralExprNormalAnnotationExprIfStmtLambdaExprArrayCreationLevelEnclosedExprBinaryExprImportDeclarationExplCtorInvocStmtReturnStmtTryStmtForEachStmtIntegerLiteralExprWildcardTypeConstructorDeclarationLineCommentConditionalExprObjectCreationExprArrayType<random>ArrayCreationExprArrayAccessExprCharLiteralExprIntersectionTypeAssignExprSingleMemAnnoExprMemberValuePairClassExprParameterEnumDeclarationBlockStmtTypeParameterClassOrInterfaceDeclModifierThisExprMethodDeclaration$0.6$$0.7$$0.8$$0.9$Node
TypeF1 after dropping Figure 4:  Ablation study to decide which node types can
be dropped without affecting the F1 score. Only node types that performed
worse than dropping random nodes (in red) were retained in later models.

####  V-A3 Phase 3: Pruning By Subtree

Using a preliminary model, we conducted an ablation study to determine which
kinds of statement nodes we can remove, if the corresponding subtree does not
contain a NullLiteralExpr node. In the ablation study, we pruned all such
subtrees under a particular kind of statement node (and all nodes connected to
that subtree via a name layer), for each kind of statement. The resulting F1
scores for the preliminary model appear in fig. 5. Our NaP-AST construction
procedure prunes the subtrees and name-connected nodes for the types of
statement nodes that appear to the left of the “<random>” entry (in red) in
fig. 5: that is, those statement types that are less useful to the model than
a random statement. For example, a nullability NaP-AST will not contain a for
loop (ForStmt in fig. 5) nor nodes for any of the variables manipulated in
that loop unless there is a null literal within the loop. However, all
expression statements (not within the subtree of another pruned statement)
will be preserved, whether or not the ExpressionStmt node for the statement
has a null literal in one of its subtrees—removing expression statements
damages model performace too much.

ForStmtBlockStmtLocalClassDeclStmtSynchronizedStmtForEachStmtCatchClauseWhileStmtLabeledStmtAssertStmtThrowStmt<random>ExplCtorInvocStmtReturnStmtIfStmtContinueStmtSwitchStmtTryStmtExpressionStmt$0.8$$0.85$$0.9$$0.95$Node TypeF1 after dropping Figure 5: Results of the ablation study described in section III-A5 by statement type. Subtrees of nodes of the types to the left of “<random>”, and nodes connected to those subtrees by the name layer, are pruned from the NaP-AST. TABLE I: NullAway benchmark results. “War.” means “Warnings.” “Red. %” means “reduction percentage”: that is, the reduction in warnings achieved by NullGTN vs. the unannotated code. | NullGCN: | Magicoder: | NullGTN:
---|---|---|---
Project | War. | Red. % | Precision | Recall | War. | Red. % | Precision | Recall | War. | Red. % | Precision | Recall
ColdSnap | 2 | 99% | 4 | 8 | Broken | NA | NA | NA | 2 | 99% | 15 | 90
QRContact | 0 | - | 0 | 0 | Broken | NA | NA | NA | 0 | - | 11 | 61
caffeine | 117 | -11% | 83 | 44 | 6 | 94% | 0 | 0 | 73 | 30% | 85 | 95
jib | 122 | -20% | 84 | 19 | Broken | NA | NA | NA | 101 | 0% | 62 | 91
keyvaluestore | 44 | -450% | 13 | 70 | Broken | NA | NA | NA | 4 | 50% | 22 | 100
meal-planner | 11 | -1000% | 0 | 0 | Broken | NA | NA | NA | 1 | 0% | 10 | 100
uLeak | 6 | 50% | 37 | 100 | 12 | 0% | 0 | 0 | 8 | 33% | 75 | 100
AutoDispose | 30 | -1400% | 3 | 11 | Broken | NA | 0 | 0 | 2 | 0% | 0 | 0
picasso | 0 | - | 81 | 44 | 0 | - | 25 | 1 | 0 | - | 0 | 0
RIBs | 0 | 100% | 100 | 100 | 1 | 0% | 0 | 0 | 1 | 0% | 0 | 0
skaffold-tools-for-java | 1 | 0% | 100 | 83 | 1 | 0% | 0 | 0 | 1 | 0% | 0 | 0
butterknife | 4 | 0% | 100 | 50 | 4 | 0% | 100 | 50 | 0 | 100% | 100 | 100
Totals | 337 | 31% | .51 | .32 | NA | NA | .2 | .03 | 193 | 60% | .6 | .89

####  V-A4 Post-processing

We added four nullability-specific post-processing steps to ensure internal
consistency.

##### Returning Nullable Fields

Our first post-processing step is a simplistic dataflow analysis: when a
method returns a field that the model has marked as @Nullable, the method’s
return type should be @Nullable, too. This post-processing step is especially
important for getters, which the models otherwise rarely predict are nullable.

##### Consistency between Arguments and Parameters

Our next post-processing step is similar in spirit: at a call-site where an
argument is a read of a field that the model predicted is @Nullable, we change
the corresponding parameter to @Nullable in the method declaration. We have
observed, qualitatively, that these models tend to do a poor job predicting
whether parameters are nullable, relative to other kinds of program elements
like fields; we conjecture that the reason for this behavior is that nullable
fields are often directly assigned null, but many methods with nullable
parameters are never directly called with null literal arguments.

##### Stream Parameters

Since the models use piece-wise boundaries in a continuous, higher dimensional
space, their impressionistic understanding of Java syntax occasionally puts
annotations where they cause compilation errors. For example, a model might
place a @Nullable annotation in a stream parameter, where Java’s syntax does
not permit one. We observed this in practice, so we added a post-processing
step to remove these @Nullable annotations.

##### Inheritance

A method’s inferred parameter or return types in the same inheritance
hierarchy may not match. We remove @Nullable annotations in
superclasses/interfaces no such annotation was inferred in the subclass.

###  V-B Training

We split the nodes with @Nullable annotations into 60% training, 20%
validation, and 20% test datasets. To create a balanced dataset, we had to
combine each set with an equal number of nodes without @Nullable annotations.
To do this, we took the annotated nodes in the dataset and subjected them to
the 60-20-20 split. We combined the training and validation sets with
unannotated nodes of equal number from the same classes, and put all remaining
nodes in the test set.

TABLE II: GTN hyperparameters Hyperparameter | Value
---|---
GT Layers | 5
FGTN Layers | 2
Epochs | 10/batch
Learning Rate | 0.01
Channel Agg. | Mean
# of Channels | 2
Non-local weight | -2
k-Hop | 9

We trained the GTN on a cluster with Intel Xeon E5-2630-v4 CPUs (2.2 GHz), 2
GPUs and 50 GB RAM. Since the adjacency matrices that we use to represent the
AST are sparse, they take up a lot of space on the GPU. So, we were only able
to train a sample consisting of 1.15% of our dataset at a time. We thus chose
batch training, which allows us to train the GTN on the full dataset over a
longer period of time. We fixed the input size to 8000 nodes, and only trained
on as many classes at a time as fit into that space. The GCN’s training (and
all the experiments in section VI) were run on an AWS g4dn.xlarge instance and
a Deep Learning PyTorch AMI.

####  V-B1 Hyperparameters

After some trial and error, we used a simple 2 layer GCN with batching. The
GTN’s trained hyperparameters are in table II. These hyperparameters were
chosen by manual grid search. For this dataset, non-local weight of -2
performs well independent of other variables. Since we trained a large dataset
in batches, we chose a low initial learning rate and used weight decay
throughout the training process to avoid overfitting.

###  V-C Thresholding during Deployment

The models are trained on an equal number of nodes that are nullable and non-
null, and all of its training data was sourced from classes that contained at
least one nullable member. Model predictions reflect this: averaged over many
pieces of code, the model’s average nullability prediction is about half
nullable elements and half non-null elements. In real code, however, there are
many more non-null elements than nullable elements: in fact, real code
contains many classes that have no nullable members at all! To account for
this, when applying each model, we use a _thresholding_ strategy: we only
actually mark elements as nullable (by writing an @Nullable annotation) when
the model is very confident in that element’s nullability. In our experiments
with real projects in section VI-A, we applied a threshold of 90% confidence.
In a deployment of one of these models on a previously-unannotated codebase
(which is our envisioned deployment scenario), we recommend using a similar
threshold.

##  VI Experiments and Results

We address the research questions from section I:

  * •

RQ1: What _kind of ML model_ should we use, and how should we post-process its
output?

  * •

RQ2: How should we _encode_ the program in a type-system-specific way to train
the model?

  * •

RQ3: How much _data_ do we need to make that model effective at inferring
qualifiers in practice?

We performed two experiments. The first is a large-scale evaluation of each
model’s ability to infer ground-truth, human-written annotations on real open-
source projects from a previous study of a nullability checker (section VI-A)
to answer RQ1 and RQ2. The second experiment (section VI-B) evaluated how much
training data the best model from section VI-A required for good performance,
to answer RQ3.

###  VI-A NullAway Benchmark

We ran all three models on the open-source benchmark the paper about the
NullAway pluggable typechecker [2]. This benchmark (from their artifact [24])
is a collection of 18 projects from GitHub in 2019; each was annotated with
nullability annotations when the artifact was published. The artifact also
includes an evaluation tool to run NullAway on these projects. Two of these
repositories no longer exist;we could build the project and run NullAway on 14
of the remaining 16; two more projects no longer use @Nullable annotations (in
the branches pulled by the artifact’s evaluation tool).We consider the
remaining 12 projects that we can typecheck using NullAway; however, we note
that of these projects, 3 of the 12 do not typecheck with no warnings, even
with the human-written annotations. We assume that this is because of either
changes in the projects or changes in NullAway itself.

We checked each benchmark project with NullAway in three configurations: 1)
with the human-written annotations that came with the projects, 2) after
removing the human-written annotations from each project, and 3) after using
each model to re-annotate the code. We measured two proxies for human
annotation effort: each model’s precision/recall with respect to the human-
written annotations (which are erased before passing the projects to each
model) and the reduction in the warnings that NullAway issues using our
annotations versus the unannotated code. The results appear in table I.

####  VI-A1 NullGCN

We trained NullGCN using PyTorch and the PyTorch Geometric library. It uses
two convolutional layers, dropout regularization, negative log-likelihood loss
function and the Adam optimizer. It achieves an accuracy of 0.6 on the test
set during training. On the full NullAway benchmark, NullGCN’s performance is
not particularly good: its recall is 32%, precision is 51%, and warning
reduction is only 31%. While this is better than no inference at all, this
result suggests to us that the hypergraph structure of the GTN (which does
much better) is important to modeling where humans write annotations: the same
graph is not as useful if the edges are not known to be of different types.

####  VI-A2 Magicoder LLM

We use Magicoder to reannotate the NullAway benchmark projects. Magicoder uses
text for input and output, we did not use the NaP-AST encoding.Magicoder seems
to perform well on one project (caffeine). However, it often breaks the code
in unpredictable ways by making seemingly-nonsensical changes. Even when this
does not occur, the LLM’s token limit is too restrictive for it to be
effective on most large projects. These problems together lead to its low
precision (20%) and recall (3%). While Magicoder appears to do well on the
seemingly-difficult caffeine project in table I, the results are difficult to
credit: while the resulting code builds with NullAway, and NullAway issues
only 6 warnings on it (a seeming warning reduction of 94%!), the structure of
the code was altered too much to tell which node goes where: that is, we
cannot even compute precision and recall, because Magicoder’s edits to
caffeine are too extensive. The LLM did not follow the prompt to not change
the code except for placing annotations.

####  VI-A3 NullGTN

We built our GTN model (NullGTN) by modifying a fork of the original code
[25]. It takes an average of about 16 hours to train the model. The largest
input source code we evaluated (6,470 non-comment, non-blank lines) took about
5 minutes for inference. NullGTN achieved an F1 score of .95 on the test set
during training. On the NullAway Benchmark, NullGTN discovered 89% of the
human-written type qualifiers—most of them, with a precision of 60%. However,
this only eliminated 60% of the NullAway warnings that a human would need to
resolve to adapt these benchmarks to use NullAway—a large amount, but far from
all of the warnings. One source of NullGTN’s inability to reduce warnings
further is imprecision, which leads to extra annotations, which leads to extra
warnings. Another cause of low warning reduction for NullGTN is interactions
with libraries. NullGTN has no model of what libraries do, and unlike an LLM
it cannot guess based on e.g., the names of library methods. Both the jib and
caffeine projects (where NullGTN fails to remove many warnings despite good
recall) use libraries extensively: caffeine heavily uses Google Guava, while
jib is a modular system with many APIs and plugins, which the model was
unaware of.

Overall, these results are encouraging: NullGTN makes a good start on bringing
these benchmarks into compliance with NullAway, and finds the vast majority
(89%) of the annotations that the developers themselves keep in their
codebases. Our answer to RQ2 is therefore positive: NullGTN can make
significant progress towards annotating a codebase for a typechecker, and many
of the annotations that it produces are remarkably similar to those a human
developer would write.

102030405060708090100$200$$400$$600$Training percentageWarnings Figure 6:
Number of warnings by percentage of data trained.

###  VI-B RQ3: How much _data_ do we need to make that model effective at
inferring qualifiers in practice?

We rebuilt the GTN model with random samples of the dataset at 10% increments
(10%, 20%, …) and ran the evaluation to see how much data is required for good
results. The number of warnings by percentage of data trained is shown in fig.
6. What we see is a classic diagram of the model improving with training data
until 60%. Performance then worsens after 70% with overfitting. In our
feasibility study, performance is maximized from training around 50% of the
dataset: around 16,000 classes. This estimate gives us a recommendation to
calibrate the dataset size for similar tasks.

##  VII Limitations and Threats to Validity

###  VII-A Threats to the Validity of Our Experiments

One threat to our NullAway experiment (section VI-A) is that the quality of
the human annotations that we used as ground truth is somewhat questionable:
they do not remove all NullAway warnings on 3 of the projects, which may
distort our results. Another threat is the use of proxies for human effort:
precision/recall of human-written annotations and reduction in warning count
may both be poor proxies for effort. For example, even though NullGTN finds
most of the annotations a human would write, those it fails to find might be
the most difficult or complex to write. Another threat comes from the choice
of benchmarks: we use programs that have been, at some point, annotated by a
human to typecheck with NullAway, so that we have ground truth for our recall
computation. However, in a deployment of NullGTN, we expect that the program
would never have been human-annotated. Programs which have never been
annotated might be trickier for inference, since human annotators might also
change code to simplify the process of annotation (and those changes might
stay in the code, even if the annotations themselves are later removed). The
use of NullAway itself is also a threat to external validity
(generalizability): our approach may not be as effective at inferring
annotations that are useful for some other nullness analysis, such as Meta’s
NullSafe.

Our approach may not generalize beyond Java and beyond nullability. In theory,
our approach should be applicable on other languages beyond Java, but
evaluating that is beyond the scope of this work. We expect that the NaP-AST
construction procedure in section III-A and a FastGTN architecture will be
applicable to other pluggable typecheckers that prove the absence of other
sorts of problems in Java, if a dataset of type qualifiers for those checkers
were available. However, we cannot test whether this is effective in practice,
since as far as we are aware sufficient training data does not exist for
typecheckers that target problems other than nullability: there is at least an
order of magnitude more code annotated for nullability than for any other
typechecker in open-source, and in section VI-B we showed that NullGTN
required about half of all the data we collected before it became effective.

###  VII-B Other Limitations of Our Approach

All machine-learning-based techniques share one serious limitation: there are
no guarantees that the annotations that it infers are correct. In our
experiments, NullGTN demonstrated close alignment with human-written ground
truth annotations—with a recall of 89%. Though there is also no guarantee that
human-written annotations are correct, we believe that NullGTN’s ability to
hew so closely to developers’ annotations suggests that this problem will be
minor in a practical deployment: whether a human or NullGTN writes an
incorrect annotation, a sound typechecker will reject it.

##  VIII Related Work

The most closely-related work to ours is a recent approach for “error-driven”
inference of nullability annotations for pluggable typecheckers [26]. The key
idea of this appraoch is to treat the typechecker as a “black box” and use its
error messages to drive inference: for example, if the checker warns that a
return expression is nullable but that a return type is declared as nonnull,
this approach could infer that an @Nullable annotation should logically be
placed on the return type. In experiments using NullAway, this approach was
shown to reduce the number of warnings emitted by the checker by 69.5% (vs.
our 60%); they did not measure precision/recall of ground-truth annotations.
However, our techniques are different: they relies on the checker’s output,
while we rely on where humans have written nullability annotations
historically (i.e., the training data for our model). In methodology, the two
approaches are orthogonal; we hope to profitably combine them in future work,
since the differing approaches mean that they probably infer _different_
subsets of nullability annotations. Another closely related approach
bootstraps global inference from the local inference that is built into most
pluggable typechecking frameworks [27]. This approach, though not specific to
nullness, also uses a fundamentally different approach and might be profitably
combined with ours in future work: it works deductively, unlike our approach.

Some prior works [1, 28] use constraint-based type inference for pluggable
types. These approaches do not support nullness (they are specific to a units-
of-measurement type system), and cannot be readily applied to other pluggable
type systems: each constraint-based inference approach is unique. Our
methodology, by contrast, could be applied to any type system, if training
data were available: a model developer would need to repeat our ablation
experiments to drop appropriate nodes from the NaP-AST, but otherwise could
reuse our infrastructure. Prior approaches for explaining type inference
errors [29, 30, 31, 32] and for gradual type migration [33] suffer the same
problems as other constraint-based appraoches (i.e., do not apply easily to
new type systems). There is also prior work that involves the user in type
inference [34], which is complementary to ours. The Daikon invariant detector
[35] can insert @Nullable annotations at program locations that can be null at
run time [36]. Like any dynamic approach, it is inherently limited by the
quality of program’s test suite.

There is a lot of work on inference of static types for dynamically-typed
languages such as Python or JavaScript using machine learning [37, 38, 6, 7,
8, 9, 10, 11]. These approaches are not directly applicable to our problem,
since they do not reason about nullability, but about the base type system,
and their models and encodings are specialized to that problem.

There is a large literature on type inference and type reconstruction
algorithms based on constraint solving [39, Chapter 22]. These techniques
build and then solve a system of constraints; the specific constraints are
type-system-dependent, which makes this approach unsuitable for pluggable
types: determining the constraints to solve would require translating the
typechecker’s logic into the logic of the constraint solver, which effectively
would require re-implementing the typechecker. Recent work [40] has proposed
an extension to the classic constraint-based type inference approach Algorithm
W [41] that enables reasoning about nullability. However, extending this to
the mainstream object-oriented languages (and their associated nullability
checkers) is an open-problem.

## References

  * [1] T. Xiang, J. Y. Luo, and W. Dietl, “Precise inference of expressive units of measurement types,” in _OOPSLA 2020, Object-Oriented Programming Systems, Languages, and Applications_ , Chicago, IL, USA, Nov. 2020.
  * [2] S. Banerjee, L. Clapp, and M. Sridharan, “NullAway: Practical type-based null safety for Java,” in _ESEC/FSE 2019: The ACM 27th joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_ , Tallinn, Estonia, Aug. 2019, pp. 740–750.
  * [3] A. Pianykh, I. Zorin, and D. Lyubarskiy, “Retrofitting null-safety onto Java at Meta,” https://engineering.fb.com/2022/11/22/developer-tools/meta-java-nullsafe/, Nov. 2022.
  * [4] M. M. Papi, M. Ali, T. L. Correa Jr., J. H. Perkins, and M. D. Ernst, “Practical pluggable types for Java,” in _ISSTA 2008, Proceedings of the 2008 International Symposium on Software Testing and Analysis_ , Seattle, WA, USA, Jul. 2008, pp. 201–212.
  * [5] W. Dietl, S. Dietzel, M. D. Ernst, K. Muşlu, and T. Schiller, “Building and using pluggable type-checkers,” in _ICSE 2011, Proceedings of the 33rd International Conference on Software Engineering_ , Waikiki, Hawaii, USA, May 2011, pp. 681–690.
  * [6] Y. Peng, J. Xie, Q. Yang, H. Guo, Q. Li, J. Xue, and M. Yuan, “Statistical type inference for incomplete programs,” in _Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2023, pp. 720–732.
  * [7] J. Wei, G. Durrett, and I. Dillig, “Typet5: Seq2seq type inference using static analysis,” _arXiv preprint arXiv:2303.09564_ , 2023.
  * [8] Y. Peng, C. Wang, W. Wang, C. Gao, and M. R. Lyu, “Generative type inference for python,” in _2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 2023, pp. 988–999.
  * [9] Y. Peng, C. Gao, Z. Li, B. Gao, D. Lo, Q. Zhang, and M. Lyu, “Static inference meets deep learning: a hybrid type inference approach for Python,” in _ICSE 2022, Proceedings of the 43rd International Conference on Software Engineering_ , Pittsburgh, PA, USA, May 2022, pp. 2019–2030.
  * [10] A. M. Mir, E. Latoškinas, S. Proksch, and G. Gousios, “Type4py: Practical deep similarity learning-based type inference for python,” in _Proceedings of the 44th International Conference on Software Engineering_ , 2022, pp. 2241–2252.
  * [11] S. Cui, G. Zhao, Z. Dai, L. Wang, R. Huang, and J. Huang, “Pyinfer: Deep learning semantic type inference for python variables,” _arXiv preprint arXiv:2106.14316_ , 2021.
  * [12] M. Allamanis, E. T. Barr, S. Ducousso, and Z. Gao, “Typilus: Neural type hints,” in _Proceedings of the 41st acm sigplan conference on programming language design and implementation_ , 2020, pp. 91–105.
  * [13] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger, “Simplifying graph convolutional networks,” in _International conference on machine learning_. PMLR, 2019, pp. 6861–6871.
  * [14] S. Zhang, H. Tong, J. Xu, and R. Maciejewski, “Graph convolutional networks: a comprehensive review,” _Computational Social Networks_ , vol. 6, no. 1, pp. 1–23, 2019.
  * [15] S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim, “Graph transformer networks,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [16] Y. Wei, Z. Wang, J. Liu, Y. Ding, and L. Zhang, “Magicoder: Source code is all you need,” _arXiv preprint arXiv:2312.02120_ , 2023.
  * [17] J. Zhang, X. Wang, H. Zhang, H. Sun, K. Wang, and X. Liu, “A novel neural source code representation based on abstract syntax tree,” in _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_. IEEE, 2019, pp. 783–794.
  * [18] S. Yun, M. Jeong, S. Yoo, S. Lee, S. Y. Sean, R. Kim, J. Kang, and H. J. Kim, “Graph transformer networks: Learning meta-path graphs to improve gnns,” _Neural Networks_ , vol. 153, pp. 104–119, 2022.
  * [19] I. Ozkaya, “Application of large language models to software engineering tasks: Opportunities, risks, and implications,” _IEEE Software_ , vol. 40, no. 3, pp. 4–8, 2023.
  * [20] M. Cui _et al._ , “Introduction to the k-means clustering algorithm based on the elbow method,” _Accounting, Auditing and Finance_ , vol. 1, no. 1, pp. 5–8, 2020.
  * [21] “The Checker Framework Manual: Section 3.7: Other tools for nullness checking,” https://checkerframework.org/manual//#nullness-related-work, 2024, accessed 22 March 2024.
  * [22] Q. Slack and B. Liu, “Sourcegraph,” 2013, search tool: https://docs.sourcegraph.com/cli/references/search. [Online]. Available: https://about.sourcegraph.com/
  * [23] Anonymous Authors, “Code for "inferring pluggable types with machine learning",” https://anonymous.4open.science/r/PTML-F14F, dataset at https://anonymous.4open.science/r/dataset-D60D/.
  * [24] S. Banerjee, L. Clapp, and M. Sridharan, “Artifact for "nullaway: Practical type-based null safety for java",” 2019. [Online]. Available: https://doi.org/10.5281/zenodo.3267950
  * [25] S. Yun, “Graph transformer networks,” https://github.com/seongjunyun/Graph_Transformer_Networks, 2023, accessed 22 March 2024.
  * [26] N. Karimipour, J. Pham, L. Clapp, and M. Sridharan, “Practical inference of nullability types,” in _Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_ , 2023.
  * [27] M. Kellogg, D. Daskiewicz, L. N. D. Nguyen, M. Ahmed, and M. D. Ernst, “Pluggable type inference for free,” in _ASE 2023: Proceedings of the 38th Annual International Conference on Automated Software Engineering_ , Luxembourg, Sep. 2023.
  * [28] J. Li, “A general pluggable type inference framework and its use for data-flow analysis,” Master’s thesis, U. of Waterloo, Waterloo, Ontario, Canada, 2017.
  * [29] B. S. Lerner, M. Flower, D. Grossman, and C. Chambers, “Searching for type-error messages,” in _PLDI 2007: Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation_ , San Diego, CA, USA, Jun. 2007, pp. 425–434.
  * [30] Z. Pavlinovic, T. King, and T. Wies, “Finding minimum type error sources,” in _OOPSLA 2014, Object-Oriented Programming Systems, Languages, and Applications_ , Portland, OR, USA, Oct. 2014, p. 525–542.
  * [31] C. Loncaric, S. Chandra, C. Schlesinger, and M. Sridharan, “A practical framework for type inference error explanation,” in _OOPSLA 2016, Object-Oriented Programming Systems, Languages, and Applications_ , Amsterdam, Nov. 2016, pp. 781–799.
  * [32] D. Zhang, A. C. Myers, D. Vytiniotis, and S. Peyton-Jones, “SHErrLoc: A static holistic error locator,” vol. 39, no. 4, 2017.
  * [33] L. Phipps-Costin, C. J. Anderson, M. Greenberg, and A. Guha, “Solver-based gradual type migration,” in _OOPSLA 2021, Object-Oriented Programming Systems, Languages, and Applications_ , Chicago, IL, USA, Oct. 2021.
  * [34] M. Vakilian, A. Phaosawasdi, M. D. Ernst, and R. E. Johnson, “Cascade: A universal programmer-assisted type qualifier inference tool,” in _ICSE 2015, Proceedings of the 37th International Conference on Software Engineering_ , Florence, Italy, May 2015, pp. 234–245.
  * [35] M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, and C. Xiao, “The Daikon system for dynamic detection of likely invariants,” vol. 69, no. 1–3, pp. 35–45, Dec. 2007.
  * [36] The Daikon developers, “Annotatenullable,” http://plse.cs.washington.edu/daikon/download/doc/daikon.html#AnnotateNullable, 2023, accessed 20 September 2023.
  * [37] Z. Xu, X. Zhang, L. Chen, K. Pei, and B. Xu, “Python probabilistic type inference with natural language support,” in _FSE 2016: Proceedings of the ACM SIGSOFT 24th Symposium on the Foundations of Software Engineering_ , Seattle, WA, USA, Nov. 2016, pp. 607–618.
  * [38] M. Pradel, G. Gousios, J. Liu, and S. Chandra, “TypeWriter: neural type prediction with search-based validation,” in _ESEC/FSE 2020: The ACM 28th joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_ , Sacramento, CA, USA, Nov. 2020, pp. 209–220.
  * [39] B. C. Pierce, _Types and Programming Languages_. Cambridge, MA, USA: MIT Press, 2002.
  * [40] M. Madsen and J. van de Pol, “Relational nullable types with boolean unification,” _Proceedings of the ACM on Programming Languages_ , vol. 5, no. OOPSLA, pp. 1–28, 2021.
  * [41] L. Damas and R. Milner, “Principal type-schemes for functional programs,” in _$9^{th}$ Symp. Principles of Programming Languages_. ACM, 1982, pp. 207–212.


* Garratt  _et al._ (2023) Samuel J. Garratt, Zack Weinstein, and Ehud Altman, “Measurements Conspire Nonlocally to Restructure Critical Quantum States,” Physical Review X 13, 021026 (2023).
  * Garratt and Altman (2023) Samuel J. Garratt and Ehud Altman, “Probing post-measurement entanglement without post-selection,”  (2023), 10.48550/arXiv.2305.20092.
  * Huang (2022) Hsin-Yuan Huang, “Learning quantum states from their classical shadows,” Nature Reviews Physics 4, 81–81 (2022).
  * Struchalin  _et al._ (2021) G.I. Struchalin, Ya. A. Zagorovskii, E.V. Kovlakov, S.S. Straupe, and S.P. Kulik, “Experimental Estimation of Quantum State Properties from Classical Shadows,” PRX Quantum 2, 010307 (2021).
  * Chen  _et al._ (2021) Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia, “Robust Shadow Estimation,” PRX Quantum 2, 030348 (2021).
  * Koh and Grewal (2022) Dax Enshan Koh and Sabee Grewal, “Classical Shadows With Noise,” Quantum 6, 776 (2022).
  * Huang  _et al._ (2021) Hsin-Yuan Huang, Richard Kueng, and John Preskill, “Efficient Estimation of Pauli Observables by Derandomization,” Physical Review Letters 127, 030503 (2021).
  * Acharya  _et al._ (2021) Atithi Acharya, Siddhartha Saha, and Anirvan M. Sengupta, “Shadow tomography based on informationally complete positive operator-valued measure,” Physical Review A 104, 052418 (2021).
  * Nguyen  _et al._ (2022) H. Chau Nguyen, Jan Lennart Bonsel, Jonathan Steinberg, and Otfried Guhne, “Optimizing Shadow Tomography with Generalized Measurements,” Physical Review Letters 129, 220502 (2022).
  * Wan  _et al._ (2023) Kianna Wan, William J. Huggins, Joonho Lee, and Ryan Babbush, “Matchgate Shadows for Fermionic Quantum Simulation,” Communications in Mathematical Physics 404, 629–700 (2023).
  * Hu  _et al._ (2023) Hong-Ye Hu, Soonwon Choi, and Yi-Zhuang You, “Classical shadow tomography with locally scrambled quantum dynamics,” Physical Review Research 5, 023027 (2023).
  * Akhtar  _et al._ (2023a) Ahmed A. Akhtar, Hong-Ye Hu, and Yi-Zhuang You, “Scalable and Flexible Classical Shadow Tomography with Tensor Networks,” Quantum 7, 1026 (2023a).
  * Bertoni  _et al._ (2022) Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, and Hakop Pashayan, “Shallow shadows: Expectation estimation using low-depth random Clifford circuits,”  (2022), 10.48550/arXiv.2209.12924.
  * Arienzo  _et al._ (2022) Mirko Arienzo, Markus Heinrich, Ingo Roth, and Martin Kliesch, “Closed-form analytic expressions for shadow estimation with brickwork circuits,”  (2022), 10.48550/arXiv.2211.09835.
  * Ippoliti  _et al._ (2023) Matteo Ippoliti, Yaodong Li, Tibor Rakovszky, and Vedika Khemani, “Operator Relaxation and the Optimal Depth of Classical Shadows,” Physical Review Letters 130, 230403 (2023).
  * Ippoliti (2023) Matteo Ippoliti, “Classical shadows based on locally-entangled measurements,”  (2023), 10.48550/arXiv.2305.10723.
  * Tran  _et al._ (2023) Minh C. Tran, Daniel K. Mark, Wen Wei Ho, and Soonwon Choi, “Measuring Arbitrary Physical Properties in Analog Quantum Simulation,” Physical Review X 13, 011049 (2023).
  * Shivam  _et al._ (2023) Saumya Shivam, Curt W. von Keyserlingk, and Shivaji L. Sondhi, “On classical and hybrid shadows of quantum states,” SciPost Physics 14, 094 (2023).
  * McGinley and Fava (2023) Max McGinley and Michele Fava, “Shadow Tomography from Emergent State Designs in Analog Quantum Simulators,” Physical Review Letters 131, 160601 (2023).
  * Dall’Arno (2014) Michele Dall’Arno, “Accessible information and informational power of quantum 2-designs,” Physical Review A 90, 052311 (2014).
  * Dall’Arno  _et al._ (2014) Michele Dall’Arno, Francesco Buscemi, and Masanao Ozawa, “Tight bounds on accessible information and informational power,” Journal of Physics A: Mathematical and Theoretical 47, 235302 (2014).
  * Hausladen and Wootters (1994) Paul Hausladen and William K. Wootters, “A ’Pretty Good’ Measurement for Distinguishing Quantum States,” Journal of Modern Optics 41, 2385–2390 (1994).
  * Jozsa  _et al._ (1994) Richard Jozsa, Daniel Robb, and William K. Wootters, “Lower bound for accessible information in quantum mechanics,” Physical Review A 49, 668–677 (1994).
  * Petz (1986) Denes Petz, “Sufficient subalgebras and the relative entropy of states of a von Neumann algebra,” Communications in Mathematical Physics 105, 123–131 (1986).
  * Barnum and Knill (2002) H. Barnum and E. Knill, “Reversing quantum dynamics with near-optimal quantum and classical fidelity,” Journal of Mathematical Physics 43, 2097–2106 (2002).
  * Wilde (2015) Mark M. Wilde, “Recoverability in quantum information theory,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471, 20150338 (2015).
  * Penington  _et al._ (2022) Geoff Penington, Stephen H. Shenker, Douglas Stanford, and Zhenbin Yang, “Replica wormholes and the black hole interior,” Journal of High Energy Physics 2022, 205 (2022).
  * Vasseur  _et al._ (2019) Romain Vasseur, Andrew C. Potter, Yi-Zhuang You, and Andreas W. W. Ludwig, “Entanglement transitions from holographic random tensor networks,” Physical Review B 100, 134203 (2019).
  * Jian  _et al._ (2020) Chao-Ming Jian, Yi-Zhuang You, Romain Vasseur, and Andreas W. W. Ludwig, “Measurement-induced criticality in random quantum circuits,” Physical Review B 101, 104302 (2020).
  * Bu  _et al._ (2022) Kaifeng Bu, Dax Enshan Koh, Roy J. Garcia, and Arthur Jaffe, “Classical shadows with Pauli-invariant unitary ensembles,”  (2022), 10.48550/arXiv.2202.03272.
  * Barratt  _et al._ (2022b) Fergus Barratt, Utkarsh Agrawal, Sarang Gopalakrishnan, David A. Huse, Romain Vasseur, and Andrew C. Potter, “Field Theory of Charge Sharpening in Symmetric Monitored Quantum Circuits,” Physical Review Letters 129, 120604 (2022b).
  * Buchhold  _et al._ (2021) M. Buchhold, Y. Minoguchi, A. Altland, and S. Diehl, “Effective Theory for the Measurement-Induced Phase Transition of Dirac Fermions,” Physical Review X 11, 041004 (2021).
  * Akhtar  _et al._ (2023b) Ahmed A. Akhtar, Hong-Ye Hu, and Yi-Zhuang You, “Measurement-Induced Criticality is Tomographically Optimal,”  (2023b), 10.48550/arXiv.2308.01653.
  * Cotler  _et al._ (2023) Jordan S. Cotler, Daniel K. Mark, Hsin-Yuan Huang, Felipe Hernandez, Joonhee Choi, Adam L. Shaw, Manuel Endres, and Soonwon Choi, “Emergent Quantum State Designs from Individual Many-Body Wave Functions,” PRX Quantum 4, 010311 (2023).
  * Choi  _et al._ (2023) Joonhee Choi, Adam L. Shaw, Ivaylo S. Madjarov, Xin Xie, Ran Finkelstein, Jacob P. Covey, Jordan S. Cotler, Daniel K. Mark, _et al._ , “Preparing random states and benchmarking with many-body quantum chaos,” Nature 613, 468–473 (2023).
  * Ippoliti and Ho (2022) Matteo Ippoliti and Wen Wei Ho, “Solvable model of deep thermalization with distinct design times,” Quantum 6, 886 (2022).
  * Ng and Mandayam (2010) Hui Khoon Ng and Prabha Mandayam, “Simple approach to approximate quantum error correction based on the transpose channel,” Physical Review A 81, 062342 (2010).
  * Cotler  _et al._ (2019) Jordan Cotler, Patrick Hayden, Geoffrey Penington, Grant Salton, Brian Swingle, and Michael Walter, “Entanglement Wedge Reconstruction via Universal Recovery Channels,” Physical Review X 9, 031011 (2019).
  * Fuchs and Sasaki (2003) Christopher A. Fuchs and Masahide Sasaki, “Squeezing quantum information through a classical channel: measuring the ”quantumness” of a set of quantum states,” Quantum Information & Computation 3, 377–404 (2003).
  * Fuchs (2004) Christopher A. Fuchs, “On the quantumness of a hilbert space,” Quantum Information & Computation 4, 467–478 (2004).
  * Kostenberger (2021) Georg Kostenberger, “Weingarten Calculus,”  (2021), 10.48550/arXiv.2101.00921.