Models of code can learn distributed representations of a program's syntax and semantics to predict many non-trivial properties of a program. Recent state-of-the-art models leverage highly structured representations of programs, such as trees, graphs and paths therein (e.g. data-flow relations), which are precise and abundantly available for code. This provides a strong inductive bias towards semantically meaningful relations, yielding more generalizable representations than classical sequence-based models. Unfortunately, these models primarily rely on graph-based message passing to represent relations in code, which makes them de facto local due to the high cost of message-passing steps, quite in contrast to modern, global sequence-based models, such as the Transformer. In this work, we bridge this divide between global and structured models by introducing two new hybrid model families that are both global and incorporate structural bias: Graph Sandwiches, which wrap traditional (gated) graph message-passing layers in sequential message-passing layers; and Graph Relational Embedding Attention Transformers (GREAT for short), which bias traditional Transformers with relational information from graph edge types. By studying a popular, non-trivial program repair task, variable-misuse identification, we explore the relative merits of traditional and hybrid model families for code representation. Starting with a  graph-based model that already improves upon the prior state-of-the-art for this task by 20%, we show that our proposed hybrid models improve an additional 10-15%, while training both faster and using fewer parameters. Well-trained models of source code can learn complex properties of a program, such as its implicit type structure (Hellendoorn et al., 2018) , naming conventions (Allamanis et al., 2015) , and potential bugs and repairs (Vasic et al., 2019) . This requires learning to represent a program's latent, semantic properties based on its source. Initial representations of source code relied on sequential models from natural-language processing, such as n-gram language models (Hindle et al., 2012; Allamanis & Sutton, 2013; Hellendoorn & Devanbu, 2017) and Recurrent Neural Networks (RNNs) (White et al., 2015) , but these models struggle to capture the complexity of source code. Source code is rich in structured information, such as a program's abstract syntax tree, data and control flow. Allamanis et al. (2018b) proposed to model some of this structure directly, providing a powerful inductive bias towards semantically meaningful relations in the code. Their Gated Graph Neural Network (GGNN) model for embedding programs was shown to learn better, more generalizable representations faster than classical RNN-based sequence models. However, the debate on effective modeling of code is far from settled. Graph neural networks typically rely on synchronous message passing, which makes them inherently local, requiring many iterations of message passing to aggregate information from distant parts of the code. However, state-of-the-art graph neural networks for code often use as few as eight message-passing iterations (Allamanis et al., 2018b; Fernandes et al., 2018) , primarily for computational reasons: program graphs can be very large, and training time grows linearly with the number of message passes. This is in contrast to, e.g., Transformer models (Vaswani et al., 2017) , which allow program-wide information flow at every step, yet lack the powerful inductive bias from knowing the code's structure. This leads us to a basic research question: is there a fundamental dichotomy between global, unstructured and local, structured models? Our answer is an emphatic no. Our starting point is the sequence-to-pointer model of Vasic et al. (2019) , which is state-of-the-art for the task of localizing and repairing a particular type of bug. As a sequence model, their architecture can (at least potentially) propagate information globally, but it lacks access to the known semantic structure of code. To this end, we replace the sequence encoder of Vasic et al. (2019) with a GGNN, yielding a new graph-to-mutlihead-pointer model. Remarkably, this model alone yields a 20% improvement over the state of the art, though at the cost of being significantly larger than the sequence model. Motivated by this result, we propose two new families of models that efficiently combine longerdistance information, such as the sequence model can represent, with the semantic structural information available to the GGNN. One family, the Graph Sandwich, alternates between message passing and sequential information flow through a chain of nodes within the graph; the other, the Graph Relational Embedding Attention Transformer (GREAT), generalizes the relative position embeddings in Transformers by Shaw et al. (2018) to convey structural relations instead. We show that our proposed model families outperform all prior results, as well as our new, already stronger baseline by an additional 10% each, while training both substantially faster and using fewer parameters. We demonstrate that models leveraging richly structured representations of source code do not have to be confined to local contexts. Instead, models that leverage only limited message passing in combination with global models learn much more powerful representations faster. We proposed two different architectures for combining local and global information: sandwich models that combine two different message-passing schedules and achieve highly competitive models quickly, and the GREAT model which adds information from a sparse graph to a Transformer to achieve stateof-the-art results. In the process, we raise the state-of-the-art performance on the VarMisuse bug localization and repair task by over 30%.
Models of source code that combine global and structural features learn more powerful representations of programs. A new method to model the source code for the bug repairing task using a sandwich model like [RNN GNN RNN] which significantly improves localization and repair accuracy.