EdSynth: Synthesizing API Sequences with Conditionals and Loops
Zijiang Yang, Jinru Hua, Kaiyuan Wang, Sarfraz Khurshid · 2018
Good API design enables many clients to effectively use the core functionality implemented by the APIs. For real-world applications however, correctly using the APIs and identifying what methods to use and how to invoke them appropriately can be challenging. Researchers have developed a number of API synthesis approaches that enable a semantically rich form of API completion where the client provides a description of desired functionality, e.g., in the form of test suites, and the automatic tools create method sequences using the desired APIs based on the given correctness criteria (e.g., all given tests pass). However, existing API synthesis approaches are largely limited to creating single basic blocks of code and do not readily handle multiple blocks in the presence of loops (or recursion) and complex test executions. A key issue with handling multiple blocks is the very large space of possible method sequences and their combinations. This paper introduces EdSynth, an API synthesis approach that explores the sequence spaces on-demand during the test execution; that is, the given tests not only provide a validation mechanism - as is common in test-driven API synthesis - but also play a vital role in guiding the space exploration by helping prune much of it. EdSynth follows the spirit of recent work on test-execution-driven synthesis and lazily initializes candidates during the execution of given tests where the part of the candidate completion that is actually executed directly determines the generation of future candidates. To further optimize the space exploration, EdSynth ranks API candidates based on a set of pre-defined heuristics. We evaluate EdSynth's ability to synthesize complex APIs in the presence of conditional statements, loops and multiple basic blocks. The experimental results show that EdSynth is effective at handling synthesis tasks with multiple API sequences in both the conditions and bodies of loops/branches; moreover, when applied to synthesis of straight-line code, EdSynth compares well with a state-of-the-art API synthesis tool that only handles straight-line code. The experiments show that EdSynth's ranking strategies help reduce synthesis time by 43%.