control flow (branches and loops)and data flow (variables and their dependencies).All concrete transformation operations g1(1)=(01.socket) are performed by gadgets extracted from the source code 92(1,2)=(1.getIoChannel().keyFor( Such a separation of concerns not only maximally reuses 02.getPoller().getSelector())) existing source code,but also gives considerable flexibility to 93(1)=((KeyAttachment)01.attachment()) implement diverse transformers.This design also facilitates our 1class DSUHelper 2 static void transform(SocketProcessor*obj,SocketProcessor stale){ later heuristic synthesis algorithm to prioritize likely relevant v1 =(NioChannel)g1(stale); object transformers by measuring both the structural complexity 4 if (v1 !null){ of a synthesized transformer and its "naturalness"in gadget v2 =(SelectionKey)g2(v1,v1); 6 if (v2 !null){ use. v3 =(KeyAttachment)g3(v2); One final note is that we restrict branch/loop conditions to be either of e,!e,e ==null,or e !null,where expression 9 e is either a variable or a gadget application.Theoretically. 1 obj.ka va; 11] any condition can be expressed by negation()and nested 12] branch (A),but both our DSL and synthesis algorithm favor simple branch/loop conditions that reuse existing source code Fig.6:A field transformer for field ka in the motivating snippets. example written in our DSL,and extracted gadgets.All used B.Gadget Extraction variables were initialized with default values,e.g.,v3=null. In gadget extraction,trade-offs must be made to balance the DSL's expressiveness and its synthesis difficulty.In an imprac- Algorithm 1:The transformer synthesis framework tical extreme,one can include all Java language constructs as 1 Function SYNTHESIS(G) gadgets.This allows our DSL to be essentially equivalent to the 2 Q←-{>}： while Q≠ado vanilla Java.However,synthesizing Java programs directly for p← arg min cost(p'); object transformation is considerably difficult and not practical. P'EQ The key trade-off we made is to only extract complete source- iflb走p then code statements as gadgets.We argue that no matter how many yield p: times method invocations,arithmetic/logical operations,etc. Q←QUDc(p)\{p} are performed in a statement,they should either be all used or entirely not used in an object transformer.The intuition behind this treatment is simple:each statement should contain a logically inseparable action in a well-maintained project for class method gadgets (methodName()),static field best readability and maintainability. gadgets (ClassName.fieldName),static method gadgets Gadgets are extracted by iterating over all statements in all (ClassName.methodName()),and object creation gad- application classes in both the old and new version source code gets (new className()).These rules are also addition- using the following rules: ally applied for the Java Standard Library for extracting 1)For a statement's associated expression (i.e..the right- potentially useful API calls,e.g.,container operations. hand side of an assignment or an if/while condition), Figure 6 gives a transformer example for field ka in our we parse it into an abstract syntax tree (AST)and replace motivating example (Figure 1).Three used gadgets g,92. each variable or constant node with a placeholder to and g3 are extracted using rules #4,#1,and #1,respectively. be a gadget.This rule yields g,g2.and g5 in Figure 5. This transformer is equivalent to the manually provided one in 2)For each statement,we consider its contained constants Figure 1. potentially useful in synthesizing object transformers. One could expect that our DSL and gadget extraction rules Therefore,each constant literal in the statement is also suffice for object transformer synthesis.Unfortunately,there extracted as a gadget.This rule yields g3 in Figure 5. can be millions of gadgets extracted from a large codebase. 3)For each statement,we also extract it into a gadget where Certainly,not all gadget combinations are equally relevant to a only variable nodes are replaced by placeholders,i.e.,given upgrade.The relevance of a gadget to the class change keeping all constants as-is in the gadget compared with and the similarity between a gadget combination and existing the first rule.This is because constants may be inseparable source code would serve as the guidance for efficient object from the statement's computational logic.This rule yields transformer synthesis,which is described as follows. 94 in Figure 5. 4)For each class in both old and new versions of the V.AUTOMATIC SYNTHESIS OF OBJECT TRANSFORMERS source code,we extract class field gadgets (fieldName), Conceptually,object transformer synthesis is simple:a 6There can be occasions that a statement consists of multiple actions.e.ga systematic enumeration of all syntactically correct programs chain of method invocations.We optimistically believe that the desired action will eventually find a correct transformer(Section V-A).This will independently appear elsewhere in the codebase. section presents our heuristic search algorithm for efficiently pri-control flow (branches and loops) and data flow (variables and their dependencies). All concrete transformation operations are performed by gadgets extracted from the source code. Such a separation of concerns not only maximally reuses existing source code, but also gives considerable flexibility to implement diverse transformers. This design also facilitates our later heuristic synthesis algorithm to prioritize likely relevant object transformers by measuring both the structural complexity of a synthesized transformer and its “naturalness” in gadget use. One final note is that we restrict branch/loop conditions to be either of e, !e, e == null, or e != null, where expression e is either a variable or a gadget application. Theoretically, any condition can be expressed by negation (¬) and nested branch (∧), but both our DSL and synthesis algorithm favor simple branch/loop conditions that reuse existing source code snippets. B. Gadget Extraction In gadget extraction, trade-offs must be made to balance the DSL’s expressiveness and its synthesis difficulty. In an imprac￾tical extreme, one can include all Java language constructs as gadgets. This allows our DSL to be essentially equivalent to the vanilla Java. However, synthesizing Java programs directly for object transformation is considerably difficult and not practical. The key trade-off we made is to only extract complete source￾code statements as gadgets. We argue that no matter how many times method invocations, arithmetic/logical operations, etc. are performed in a statement, they should either be all used or entirely not used in an object transformer. The intuition behind this treatment is simple: each statement should contain a logically inseparable action in a well-maintained project for best readability and maintainability6 . Gadgets are extracted by iterating over all statements in all application classes in both the old and new version source code using the following rules: 1) For a statement’s associated expression (i.e., the right￾hand side of an assignment or an if/while condition), we parse it into an abstract syntax tree (AST) and replace each variable or constant node with a placeholder i to be a gadget. This rule yields g1, g2, and g5 in Figure 5. 2) For each statement, we consider its contained constants potentially useful in synthesizing object transformers. Therefore, each constant literal in the statement is also extracted as a gadget. This rule yields g3 in Figure 5. 3) For each statement, we also extract it into a gadget where only variable nodes are replaced by placeholders, i.e., keeping all constants as-is in the gadget compared with the first rule. This is because constants may be inseparable from the statement’s computational logic. This rule yields g4 in Figure 5. 4) For each class in both old and new versions of the source code, we extract class field gadgets h.fieldNamei, 6There can be occasions that a statement consists of multiple actions, e.g., a chain of method invocations. We optimistically believe that the desired action will independently appear elsewhere in the codebase. g1(1) = h1.socketi g2(1, 2) = h1.getIOChannel().keyFor( 2.getPoller().getSelector())i g3(1) = h(KeyAttachment) 1.attachment()i 1 class DSUHelper { 2 static void transform(SocketProcessor? obj, SocketProcessor stale) { 3 v1 = (NioChannel) g1(stale); 4 if (v1 != null) { 5 v2 = (SelectionKey) g2(v1, v1); 6 if (v2 != null) { 7 v3 = (KeyAttachment) g3(v2); 8 } 9 } 10 obj.ka = v3; 11 } 12 } Fig. 6: A field transformer for field ka in the motivating example written in our DSL, and extracted gadgets. All used variables were initialized with default values, e.g., v3 = null. Algorithm 1: The transformer synthesis framework 1 Function SYNTHESIS(G) 2 Q ← {|.}; 3 while Q 6= ∅ do 4 p ← arg min p0∈Q cost(p 0 ); 5 if |. /∈ p then 6 yield p; 7 Q ← Q ∪ DG(p) \ {p} class method gadgets h.methodName(~)i, static field gadgets hClassName.fieldNamei, static method gadgets hClassName.methodName(~)i, and object creation gad￾gets hnew ClassName(~)i. These rules are also addition￾ally applied for the Java Standard Library for extracting potentially useful API calls, e.g., container operations. Figure 6 gives a transformer example for field ka in our motivating example (Figure 1). Three used gadgets g1, g2, and g3 are extracted using rules #4, #1, and #1, respectively. This transformer is equivalent to the manually provided one in Figure 1. One could expect that our DSL and gadget extraction rules suffice for object transformer synthesis. Unfortunately, there can be millions of gadgets extracted from a large codebase. Certainly, not all gadget combinations are equally relevant to a given upgrade. The relevance of a gadget to the class change and the similarity between a gadget combination and existing source code would serve as the guidance for efficient object transformer synthesis, which is described as follows. V. AUTOMATIC SYNTHESIS OF OBJECT TRANSFORMERS Conceptually, object transformer synthesis is simple: a systematic enumeration of all syntactically correct programs will eventually find a correct transformer (Section V-A). This section presents our heuristic search algorithm for efficiently pri-