Repairing Regex-Dependent String Functions

Regex-dependent string functions are string functions that take regular expressions (regexes) as parameters and are popular means of manipulating strings. They are frequently used for, e.g., string transformation and substring search. Despite the importance, writing these functions is far from easy. To rectify this situation, recent research made significant progress by proposing automated methods for synthesizing regexes based on Programming by Examples (PBE). However, there still is a gap between these methods and the goal of synthesizing regex-dependent string functions. First, the existing methods focus on whole-string matching, whereas most regex-dependent string functions adopt substring matching. Second, the existing methods focus only on the regex, but many commonly used regex-dependent string functions, such as replace and replaceAll, also take as parameter a replacement to specify how the substrings matched to the regex will be replaced. This paper fills the gap by presenting the first PBE-based method for repairing regex-dependent string functions. Like the recent methods for regex synthesis, our algorithm builds on enumerative search with pruning and SMT constraint solving, but with extensions to support substring matching and replacement. The main challenge is the large search space. We address the challenge by novel ideas such as incorporation of origin information in examples to identify the locations of substrings to be matched, a new substring-context-aware pruning technique, and a novel use of SMT constraints to insert captures that can be referred from the replacement. Additionally, we identify a novel necessary and sufficient condition that can be used to detect and filter unrepairable instances. We implemented our algorithm as a prototype tool called R2-DS and evaluated it on real-world benchmarks. Results show that our algorithm efficiently repairs the bugs in the real world and finds high-quality repairs. CCS CONCEPTS • Software and its engineering → Software notations and tools; • Theory of computation → Regular languages.