Source-linked AI summary
Aroma: Code Recommendation via Structural Code Search
Sifei Luan, Di Yang, Celeste Barnaby, Koushik Sen, Satish Chandra
TL;DR
Programmers need help extending partial code with functionality and customary handling, but existing search and pattern-based tools have important coverage or aggregation limits. Aroma performs structural code search over large corpora, then prunes, clusters, and intersects retrieved methods to recommend concise shared snippets. It retrieved the original method as the top-ranked result for 99.1% of contiguous and 98.3% of non-contiguous queries, while exactly recommending the withheld code in 37 of 50 Stack Overflow cases.
Problem
Programmers need to extend partial code with complete functionality, customary extensions, and error handling, while existing tools either return unaggregated results or depend on limited mined patterns.
Method
Aroma indexes a large code corpus, searches structurally for method bodies containing a partial snippet, then prunes, clusters, and intersects results into concise recommendations.
Results
99.1% of contiguous queries and 98.3% of non-contiguous queries retrieved the original method as the top-ranked result; Aroma also exactly recommended the withheld code in 37 of 50 cases.
Takeaways & Limitations
Aroma provides useful code recommendations from large corpora without requiring a fixed library of mined patterns, and supports implementations in four programming languages.
Takeaways & Limitations
When matched method bodies are mostly different, clusters can have size 1, so Aroma performs no intersection and recommends full method bodies without pruning.
Abstract
from arXiv · showhide
Programmers often write code that has similarity to existing code written somewhere. A tool that could help programmers to search such similar code would be immensely useful. Such a tool could help programmers to extend partially written code snippets to completely implement necessary functionality, help to discover extensions to the partial code which are commonly included by other programmers, help to cross-check against similar code written by other programmers, or help to add extra code which would fix common mistakes and errors. We propose Aroma, a tool and technique for code recommendation via structural code search. Aroma indexes a huge code corpus including thousands of open-source projects, takes a partial code snippet as input, searches the corpus for method bodies containing the partial code snippet, and clusters and intersects the results of the search to recommend a small set of succinct code snippets which both contain the query snippet and appear as part of several methods in the corpus. We evaluated Aroma on 2000 randomly selected queries created from the corpus, as well as 64 queries derived from code snippets obtained from Stack Overflow, a popular website for discussing code. We implemented Aroma for 4 different languages, and developed an IDE plugin for Aroma. Furthermore, we conducted a study where we asked 12 programmers to complete programming tasks using Aroma, and collected their feedback. Our results indicate that Aroma is capable of retrieving and recommending relevant code snippets efficiently.
1 INTRODUCTION
Aroma addresses the need to extend partial code with customary setup, error handling, and library calls by searching structurally similar code and synthesizing concise recommendations. It is designed to aggregate similar results, work beyond pre-mined patterns, and produce recommendations quickly across several languages.
- Motivation: Aroma targets programmers who need to complete partial code with proper setup, error handling, and appropriate library calls.The motivating bitmap-decoding example illustrates how recommendations can expose customary extensions found in related projects.
- Approach: Unlike code-to-code search, Aroma aggregates similar retrieved snippets and carves out common concise code; unlike pattern-based completion, it is not limited to previously mined patterns.These distinctions address both result redundancy and the restricted coverage of fixed pattern libraries.
- Approach: Aroma searches a large code corpus for method bodies approximately containing a query snippet, then prunes, clusters, and intersects results into succinct recommendations.Its structural search accounts for code structure rather than treating the query as ordinary text.
- Advantages: Aroma recommendations are generated by intersecting several similar-looking snippets, increasing the likelihood that they are idiomatic rather than one-off.The recommendation is therefore derived from shared code across multiple methods, not simply copied from one method body.
- Advantages: Aroma can create recommendations from millions of methods within a couple of seconds on a multi-core server and has implementations for Hack, Java, JavaScript, and Python.Its generic parse-tree algorithm supports deployment across the four reported programming languages.
- Evaluation: In 37 of 50 partial-snippet cases, Aroma recommended the exact original code snippet; the remaining recommendations were alternative snippets that were still useful.The evaluation used Android Java snippets obtained from Stack Overflow.
2 THE OPPORTUNITY FOR AROMA
New code frequently resembles existing repository code, and Aroma measures this opportunity by searching recent changesets for structurally similar methods. Using manually calibrated similarity scores, 35.3% of changesets had a result meeting the threshold for meaningful similarity.
- New code often resembles code already present in a large repository, motivating recommendations based on existing implementations.
- The experiment collected short changesets from commits submitted during a two-day period to focus on code added or modified within single methods.Changesets shorter than two lines or longer than seven lines were filtered out.
- For the first 1000 changesets, Aroma searched for repository methods containing structurally similar code and recorded each top-ranked method's similarity score.The score measures the percentage of query features also found in the search result.
- Manual judgments showed a clear separation in similarity scores between pairs labeled semantically similar and not similar.The manually labeled sample contained 50 changeset–method pairs.
- 0.71 was selected as the threshold, and 35.3% of changesets had a most-similar result at or above it.Such results were judged meaningful enough that programmers could adapt the existing code with minimal effort.
3 ALGORITHM
Aroma represents code with language-independent simplified parse trees, extracts structural features, and uses search, pruning, clustering, and intersection to generate recommendations. Its feature design captures local structure and variable usage while sparse computation and greedy pruning support efficient retrieval and reranking.
- Search: Aroma’s light-weight search computes query-method overlap from intersected structural features, while sparse multiplication makes this phase finish in less than a second on the evaluation corpus.The corpus contains over 37 million unique features, and the feature vectors are very sparse.
- Definitions: Aroma parses method bodies into simplified parse trees containing non-keyword tokens, keyword tokens, and nested simplified parse trees.The representation avoids language-specific grammar rule names and can be used across programming languages.
- Featurization: Aroma extracts structural features whose shared collections indicate similarity while their non-exhaustiveness tolerates some differences between related snippets.Parent and sibling features capture local parse-tree relations without fully reconstructing the tree.
- Featurization: Variable usage features preserve relationships between repeated uses of the same local variable after local names are replaced with #VAR.The features relate consecutive usage contexts, such as the parent-node label and child position for each occurrence.
- Prune, Rerank, Cluster, and Intersect: After search, Aroma prunes methods to obtain snippets common to the query and method, reranks them, then clusters and intersects snippets to form recommendations.The greedy pruning algorithm can rarely miss the best intersection, although the reranked results feed the clustering and intersection phase.
4 EVALUATION OF AROMA’S CODE RECOMMENDATION CAPABILITIES
Aroma was evaluated on Stack Overflow-derived Android snippets to assess whether its recommendations help programmers extend partial code with common configurations, checks, operations, and related statements. Among 50 objectively assessable partial queries, recommendations frequently matched or usefully extended the original code.
- 64 Stack Overflow code snippets were evaluated, with 50 suitable for objective partial-snippet assessment after excluding single-statement snippets.The evaluation used snippets from popular Android questions and top-voted answers.
- Aroma recommendations commonly add object configurations, defensive checks, operations on computed values, or statements that commonly appear alongside the query.These categories include configurations, null or exception handling, related API operations, and correlated statements.
- Rarely, dissimilar matching method bodies produce clusters of size 1, so Aroma returns the full method body without intersection or pruning.
- 59 of 64 query snippets (92%) received at least one useful recommendation in the first four categories.The authors manually inspected and categorized recommendations, with independent verification by other authors.
4.4 Comparison with Pattern-Oriented Code Completion
Aroma was compared with pattern-oriented completion using 15 manually curated Android API usage patterns. It reproduced 14 of 15 original usage patterns and could recommend snippets beyond previously mined patterns.
- 14 of 15 Android API usage patterns received Aroma recommendations containing the original usage pattern.The patterns came from a dataset curated from Stack Overflow posts and Android documentation.
- Aroma can recommend code snippets that do not correspond to previously mined patterns.
5 EVALUATION OF SEARCH RECALL
The search-recall evaluation tested Aroma on contiguous and non-contiguous partial snippets and compared it with clone detection and conventional search. Aroma reliably retrieved the original method, while pruning was identified as essential for precise ranking.
- Aroma’s benchmark used 1,000 contiguous and 1,000 non-contiguous partial queries sampled from method bodies.Contiguous queries used the first five lines; non-contiguous queries used five randomly sampled lines.
- Aroma retrieved the original method within the top 100 results for every benchmark query.Recall@100 is relevant because the first 100 reranked methods feed the clustering phase.
- 99.1% of contiguous and 98.3% of non-contiguous queries ranked the original method first.
- Bootstrapped confidence intervals were 99.34% ± 0.25% for contiguous Recall@1 and 98.71% ± 0.49% for non-contiguous Recall@1.The corresponding Recall@100 intervals were 99.97% ± 0.03% and 99.80% ± 0.26%.
- SourcererCC achieved 12.2% and 7.7% recall for contiguous and non-contiguous queries, respectively.The comparison used the same benchmark queries, but SourcererCC did not provide ranking scores for ranked recall.
- Conventional search techniques had considerably lower recall, showing that pruning is essential for precise ranked results.Without pruning, overlapping features or keywords can place methods that do not contain the query above the original method.
6 AROMA IN DEPLOYMENT
Aroma was deployed across Hack, Java, JavaScript, and Python through a language-agnostic architecture and IDE plugins. Its recall remained comparable across supported languages, and its response time was suitable for interactive use.
- Aroma was implemented for Hack, JavaScript, and Python in addition to Java, using language-specific parsers with shared generic-tree processing.Pruning, clustering, and intersection operate on simplified parse trees across languages.
- Recall rates for the additional languages were on par with Aroma’s Java performance on the open-source corpus.Non-contiguous samples were not generated for JavaScript or Python because of HTML embedding and indentation-dependent structure.
- Aroma was implemented as an IDE plugin for Hack, Java, JavaScript, and Python.The plugin displays recommendations within the development environment.
- Feature-vector indexing took 20 minutes on average on a 24-core server, with incremental indexing proposed for larger codebases.
7 INITIAL DEVELOPER EXPERIENCE
A study of 12 Hack programmers found that Aroma was generally useful for completing short programming tasks, though its value varied with participants’ familiarity and existing search practices.
- Study design: 12 Hack programmers completed four programming tasks each, using Aroma for two randomly selected tasks and not using it for the other two.Each task included a functionality description and incomplete code, with participants asked to write 4 to 10 lines.
- Usefulness: 6 participants found Aroma always useful, while 6 found it sometimes useful.When asked whether they wished Aroma had been available for tasks where it was prohibited, 6 answered yes, 4 sometimes, and 2 no.
- Reported benefits: Participants valued Aroma for quickly discovering usage patterns and finding answers.One participant said general patterns were useful, while another reported that BigGrep took longer for the same goal.
- Reported benefits: One participant considered Aroma more capable for multi-line queries and queries without exact string matches.This feedback identifies structural or non-exact matching as a perceived advantage over simpler search.
- Reported limitations: Some participants found Aroma unnecessary when they already knew the relevant libraries or could obtain comparable information through BigGrep.These responses indicate that prior familiarity and existing search tools moderated the perceived value of clustered recommendations.
8 RELATED WORK
Code-to-code search tools retrieve code related to a code snippet, but they differ in whether they target semantic similarity and how they obtain related results.
- Code-to-code search: FaCoY and Krugle take a code snippet as a query and retrieve relevant snippets from a corpus.FaCoY specifically aims to find semantically similar results.
- FaCoY: FaCoY first searches Stack Overflow for natural-language descriptions of the query, then finds related posts and similar code.
- Comparison: These tools retrieve similar code at different syntactic and semantic levels.
Code Search Engines.
Earlier code search engines primarily build code examples from keyword-based queries, with some methods intersecting results or enriching queries using documentation and structural entities.
- Keyword-based search: Keyword-based code search research includes systems that improve retrieval through varied query and corpus techniques.Examples include test-case search in CodeGenie, API-documentation inlining in SNIFF, and API augmentation in CodeHow and CoCaBu.
- Recommendation techniques: SNIFF intersects search results to provide recommendations, but targets natural-language queries.Its clustering algorithm is discussed further in the paper, while its recommendations are not presented as code-to-code search.
- Terminology: BigGrep is a version of grep that searches an entire codebase.
- Scope boundary: Prior techniques focus on creating code examples from keyword queries rather than supporting code-to-code search and recommendation.A developer survey identifies finding code examples or related APIs as the top reason for code search.
Clone Detectors.
Clone detectors target syntactically identical or highly similar code, while newer approaches explore semantic, gapped, and large-gapped clones; code completion systems mine structural coding patterns to generate suggestions.
- Clone detection: SourcererCC detects Type 1, 2, and 3 clones using tokens and scales to large projects with high precision and recall.It is contrasted with NiCad, Deckard, and CCFinder, which also support Type 3 clones.
- Extended clone types: Recent clone detection work targets semantically similar, gapped, and large-gapped clones.These techniques may excel for particular clone types but sacrifice precision and recall for Type 1 to 3 clones.
- Code completion: Pattern-oriented code completion mines graph-represented coding patterns before searching for input code to produce completion suggestions.GraPacc uses GrouMiner to mine the patterns and then searches for matching input code.
Pattern Mining and Code Completion.
Prior work improves API documentation and examples through synthesis, augmentation, slicing, or natural-language-driven structured call generation.
- Buse and Weimer synthesize API usage examples using data flow analysis, clustering, and pattern abstraction.
- Subramanian et al. augment API documentation with up-to-date source code examples.
- MUSE generates method-specific code examples through static slicing, while SWIM synthesizes structured call sequences from natural-language queries.
9 CONCLUSION
Aroma indexes code, retrieves method bodies containing a query snippet, and clusters and intersects them into succinct recommendations. Evaluations found useful recommendations, highly accurate retrieval, and positive programmer feedback across multiple settings.
- Aroma indexes a large code corpus, retrieves method bodies containing a snippet, and clusters and intersects them into succinct code recommendations.
- 37 out of 50 half-snippet queries exactly recovered the remaining half of the code snippet.
- 99.1% of contiguous queries and 98.3% of non-contiguous queries retrieved the original method as the top-ranked result.
- Many participants used Aroma to identify common patterns in unfamiliar libraries, and a majority found it useful for completing programming tasks.
- Aroma identifies common additions or modifications to input snippets and presents them concisely to programmers.