A Type-Directed Approach to Program Repair - …

1 A Type-Directed Approach to Program RepairAlex Reinking and Ruzica PiskacYale enterprise software often requires composing several li-braries together with a large body of in-house code. Large APIs introduce a steeplearning curve for new developers as a result of their complex object-oriented un-derpinnings. While the written code in general reflects a programmer s intent, dueto evolutions in an API, code can often become ill-typed, yet still syntactically-correct. Such code fragments will no longer compile, and will need to be describe an algorithm that automatically repairs such errors, and discuss itsapplication to common problems in software IntroductionWhile coding, a developer often knows the approximate structure of the expression sheis working on, but may yet write code that does not compile because some fragmentsare not well-typed. Such mistakes occur mainly because modern libraries often evolveinto complex application programming interfaces (APIs) that provide a large number ofdeclarations.

2 It is difficult, if not impossible, to learn the specifics of every declarationand its this paper we propose an Approach that takes ill-typed expressions and automat-ically suggests several well-typed corrections. The suggested code snippets follow thestructure outlined in the original expression as closely as possible, and are ranked basedon their similarity to the original code. This Approach can also be seen as code fact, our proposed method extends the synthesis functionality described in [3, 6, 10].In light of Program Repair , plain expression synthesis can be seen as a Repair of theempty have implemented an early prototype of our algorithm, and empirically tested iton synthesis and Repair benchmarks. The initial evaluation strongly supports the idea ofa graph-based Type-Directed Approach to code Repair and snippet synthesis. Compared tothe results reported in [3], our Approach outperforms on similar benchmarks, sometimesby several orders of magnitude, while still producing high-quality Related WorkOur work is largely inspired by two synthesis tools: Prospector [6] and InSynth [3, 4].

3 Prospector is a tool for synthesizing code snippets containing only unary API basic synthesis algorithm used in [6] encodes method signatures using a we also encode function information in a graph structure, our synthesis graphis more general. As explained in Sec. , we distinguish nodes into types and functions,2 Alex Reinking and Ruzica Piskacas opposed to just types . In a way, the connections to each function node models itssuccinct type as described in [3]. While our Approach acts as a generalization of boththese tools, we significantly extend their capability. Our algorithm can Repair ill-typedexpressions, as and locating errors in code [1, 8] play an important role in the processof increasing software reliability. While our Approach suggests repairs based only ona given ill-typed expression and its environment, other tools that tackle this problem[2, 5, 7, 9] additionally require test cases, code contracts and/or symbolic Motivating Example: Correcting Multiple ErrorsIn this section, we show how our algorithm efficiently repairs ill-typed , such expressions might poorly reflect the structure of the desired expres-sion, while still retaining other useful information.

4 This is the case when the correctstructure is obscured by passing too many or too few arguments to a function, or bypassing them in the wrong following code fragment attempts to read a compressed file though a bufferedstream while using an extensive number of calls to the standard Java API. The developerattempts to instantiate anInputStreamobject:int buffSize = 1024, compLevel = ;String fileName = " ";InputStream input =new BufferedInputStream(buffSize, new DeflaterInputStream(new FileInputStream(), compLevel, true)); // errorIn this example, the single variable assignment contains three errors. First, the construc-tor for theFileInputStreamrequires at least one argument, yet has received none;second, theDeflaterInputStreamconstructor has been passed too many arguments;and finally, theBufferedInputStreamhas been passed valid arguments, but in thewrong Repair this expression, our algorithm proceeds from the bottom, viewed as a parsetree, up to the top-level.

5 Thus, it begins by correcting the innermost sub-expression:new FileInputStream(). From the entire available code, our Repair algorithm re-turnsnew FileInputStream(fileName)as the closest match. To Repair code, weconsider the visible user-defined values along with the standard libraries, favoring thevalues that appear closest to the point in the Program where the Repair was applying this Repair , the Repair proceeds to correct theDeflaterInputStreamcall. Since all of its arguments are well-typed, the Repair will attempt to re-use themwhile synthesizing a replacement. After searching through the space of possible repairs,the algorithm finds the following snippet:new DeflaterInputStream(new FileInputStream(fileName), newDeflater(compLevel, true))A Type-Directed Approach to Program Repair3 Here, the Repair wraps the extra arguments in a call to theDeflaterconstructor fromthe Java API. Notice that even thoughDeflaterwas not previously present in the ex-pression, our Repair algorithm was able to discover it by examining the valid constructorcalls for , the algorithm rebuilds the overall expression by interchanging the argu-ments in the top-level expression to arrive at the final, correct result:new BufferedInputStream(new DeflaterInputStream(new FileInputStream(fileName),new Deflater(compLevel, true)),buffSize);As we discuss in Sec.

6 5, the whole search and Repair takes under a second to The Synthesis Graph ConstructionOur algorithm operates by searching through a data structure we call thesynthesisgraph. Each node of the synthesis graph corresponds to either a value-producing lan-guage entity, such as a function, variable, constant, or literal, or to a type in the therefore divide nodes into two setsVt(type nodes) andVf(function nodes). Sincevariables, constants, and literals can be considered functions taking the empty set totheir value, they belong toVf. From every function node, there is an out-edge to thetype it produces, and for each distinct type that the function takes as an argument, thereis an incoming edge into the function node to the type node. Importantly, this meansthat a function on three input parameters of the same type will have in-degree addition, we assign to every edge a cost, which is a subjective measure that guidesthe search towards desirable traits.

7 Such traits could include smaller expressions orlower memory usage, similar to [4]. The cost of an expression is defined to be an accu-mulation of the costs of the edges it Synthesis ProcedureWe now outline the synthesis portion of our algorithm, Algorithm 1. The algorithmtakes as input the synthesis graphG pVtYVf,Eq, the type of expression to synthe-size , and two the number of expressions to synthesize,andCmaxis an upper bound on the cost of an expression. The synthesis algorithm re-turns a list of expressions of type . The first two steps can be done using Dijkstra salgorithm. The types inV1tare explored in reverse order to avoid performing expensiverecomputations. The loop findsNexpressions of type with the shortest cost-distanceto inG1and stores them insnips. This way, GetExpressions is able to reuse thesecomputations without reducing the search we describe the GetExpressions procedure, whose task is to find theNbestsnippets of type inG1within a prescribed cost boundCnow.

8 The procedure oper-ates recursively, and it checks thesnipstable to see whether it can reuse the existingcomputations. To compute candidates for PVt, the procedure looks at its outgoing4 Alex Reinking and Ruzica PiskacAlgorithm 1:Synthesis Algorithminput:G pVtYVf,Eq, PVt,Cmax,Noutput:exprs, the list of expressions1G1 pV1tYV1f,E1q subgraph ofGreachable withinCmaxfrom ;2 SortV1tin descending distance away from ;3snips Hash table mapping types to snippets ;4foreach PV1tdo5snips[ ] GetExpressions(G1,snips, ,Cmax Dist( ),N) ;6exprs snips[ ] ;ProcedureGetExpressions(G1 pV1tYV1f,E1q, snips, ,Cnow,N)1if PKeys(snips)then returnsnipsr s;2results H;3foreachgPV1fof the formg:p 1 kq do4ifCost(g) Cnowthen continue;5 For alli, letsi GetExpressions(G1,snips, i,Cnow Cost(g),N) ;6foreachargsPs1 skdo7ifCost(g(args)) Cnowthen8 Addg(args) toresults;9while|results| Ndo10 Remove the most costly entry fromresults;11returnresultsneighbors, which are all functions whose output is of type.

9 For each function thatdoes not immediately break the cost constraint, GetExpressions attempts to synthesizesubexpressions for each of its arguments recursively. This only needs to be done oncefor each type. Then, for every possible set of arguments to the function, it adds the al-lowable expressions to the results. Furthermore, it pushes out the worst few results ifthe size of the set would Repair AlgorithmFinally, we describe the Repair algorithm, Algorithm 2. The key step in our approachis biasing the previously-described synthesis procedures towards the correctly-typedsubexpressions of the broken expression. The intuition for this is that the search shouldbe directed to favor those components that the programmer intended to use. To do this,we adjust theCostfunction used by GetExpressions to assign the lowest possible costto the well- types subexpressions. Informally, we call these zero-cost subexpressions reinforced . This lowers the weights of results that contain these expressions, thusimproving their ranking among the returned scheme has a few advantages: first, it will very strongly prefer those expres-sions that occurred as part of the given incorrect expression; second, in cases wheremore than one of the same type is required, it will favor using multiple, distinct subex-A Type-Directed Approach to Program Repair5pressions; and finally, if no expressions are given, thenCostactually remains this modification in place, the Repair algorithm proceeds from the bottom each broken sub-expression in the input, we first reinforce each of its well-typedsubexpressions and then initiate a synthesis for the desired type of the current subex-pression.

10 If any of its children are ill-typed, we recurse and Repair them that this means the repaired subexpressions will also be reinforced. Thisbehavior is desirable because it favors reusing the subexpressions generated once therepair synthesizes a higher level. Additionally, the recursion guarantees that reinforcinga subexpression will not interfere with a synthesis that occurs at the same level as thatsubexpression. Although this algorithm, as described, returns up toNpossible repairs,Algorithm 2: Repair Algorithminput:G pVtYVf,Eq, the synthesis graph;expr, the broken expression;Cmax, themaximum allowable cost;N, the number of repairs to synthesizeoutput:repairs, a list1ifexpris well-typedthen return[expr];2 Writeexprasexprpx1,..,xkqwherexiare its subexpressions of type i;3foreachxP tx1,..,xkudo4x Repair (G,x,Cmax,N) ;// Replacexwith a list of eitheritself or its possible corrections5foreachsubsPx1 .. xkdo6 Reinforce all expressions insubs;7 Add all results of Synthesize (G, ,Cmax,N) torepairs;8 Clear reinforcements ;9repairs BestNresults inrepairsin our preliminary implementation, the first returned result was mostly the correct one,so we speculate that settingNreally low might be acceptable in a practical Preliminary EvaluationWe empirically evaluated our Approach on benchmarks based on those found in [4].