A Type-Directed Approach to Program Repair

Thu 16 July 2015

Programmers working in modern object-oriented languages often need to compose several large, complicated libraries together with in-house code while developing enterprise software. As these libraries evolve, legacy code that depends on deprecated declarations sometimes breaks. Many transformations can break legacy code. For example, changing the name or signature of a function, changing the type hierarchy, or removing a deprecated declaration will leave behind expressions that are well-formed, but ill-typed. While such code will still reflect the programmer's intent, it will no longer compile, and will need correction.

Due to the size of these libraries, it is also common for a programmer to call a function incorrectly, or be unsure how to construct a new object. This is particularly common outside an IDE setting. Ill-typed code of this variety also reflects the programmer's intent, as the components she wishes to compose are all present, although the composition itself is malformed.

We have designed an algorithm to compute plausible corrections to this class of well-formed, but ill-typed expressions. While the theoretical underpinnings apply to any statically-typed language, we have chosen Java as the experimental target, and have provided an example implementation as a plugin to the Oracle Java Compiler.

We are currently in the process of experimentally evaluating our algorithm. Our preliminary implementation has produced promising results. As an illustration, our tool simultaneously introduced a missing parameter, wrapped extra parameters in a temporary object, and interchanged parameters that appeared in the wrong order all across multiple nested function calls.

In summary, the contributions of this project are a novel approach to code repair based on type constraints, an efficient encoding of type constraints via the synthesis graph data structure, a compiler plugin that automatically suggests a list of corrections for ill-typed expressions.