IECS: Intent-Enforced Code Search via Extended Boolean Model

Abstract

Most code search tools seem to yield semantically correct matches, but the search results rarely meet the demands of users perfectly. These results still have to be modified manually. One major reason is that existing tools lack the ability of intent predicting to guess what else a user might do after obtaining the results. In this paper, we propose an intent-enforced code search approach (IECS) that can predict the potential intents for a query before performing code retrieval. Then it expands the query with the intents and applies the Extended Boolean Model to retrieve the relevant results without any subsequent modification. We implement SnippetGen, a code search tool performing IECS. Compared with CodeHow and Google Code Search (CS), SnippetGen outperforms them by 28.5% with a precision score of 0.846 (i.e., 84.6% of the first returned results are relevant results) when we utilize these tools to perform 70 queries on a codebase consisting of 27K projects downloaded from GitHub. We also perform a controlled experiment by asking 20 participants to complete 3 tasks with SnippetGen and CodeHow. The results confirm the effectiveness of SnippetGen in programming practice.

Keywords

Software reuse code search intent predicting query expansion

1 Introduction

To reuse the existing method with the same functionality as much as possible, many code search tools are proposed. Early code search engines, e.g., Google 1 , Krugle 2 and Koders 3 , offer only the keyword-based search with low precision [23, 25]. The later work did semantic search to enhance the accuracy of the search results, e.g., signature matching, type matching [23, 13]. But these approaches are impractical, because they require too little or too much specification. The current work supports free-text query via query expansion to promise better usability, such as the latest code search tool CodeHow [2] which expands the query with the APIs and considers the impact of the both APIs and text similarity. Although these existing code search tools seem to yield semantically correct matches [3], the search results might be too complex or too slow to meet the user demands. These results always need to be modified [4]. One major reason is that these tools lack the ability of intent predicting to guess what else a user might do after obtaining the search results.

Example: Given a query “access data from excel”, the method “ExcelToDataSet” could be returned by the standard Boolean model [1], because the method contains all the query terms with the highest term frequency such as “ExtendedProperties=Excel8.0;” and “Fill(dataset)”. Unfortunately this method is always modified, because it only accesses the data of the outdated excel2003 but fails in the most frequently-used excel2007. In this case, the user changes the line of this method from (“Microsoft.ACE.OLEDB.4.0”, “Excel8.0”) to (“Microsoft.ACE.OLEDB.12.0”, “Excel12.0”) and save it as “Excel2007ToDataSet”. Extracted from this change, T=(“Microsoft.ACE.OLEDB.12.0”, “Excel12.0”) where T is the intent consisting of two elements. When we perform the query again, we could extend the query to “Microsoft.ACE.OLEDB.12.0; Excel12.0; access data from excel” and obtain the modified method “Excel2007ToDataSet” directly. This example shows that through intent predicting, more accurate code search could be achieved.

In this paper, we propose an intent-enforced code search approach (IECS) which makes use of the intent to enhance the search rather than transform the result of the initial search to meet the user needs. For the specific method, we propose the intent extraction algorithm to extract the intents from the past records of modifications. In this process, we refine the commonly-used intents and enrich the intents with the method’s description consisting of method signature, FQN 4 and remarks. Given a query, we predict the potential intents for the query before performing code retrieval. Then we expand the query with the intents and apply the Extended Boolean Model [25] to retrieve the relevant code without any subsequent modification.

We implement SnippetGen, an IECS-supported code search tool. The front-end is a visual studio 2010 extension. The backend is supported by Sourcerer [17]. We evaluate SnippetGen against CodeHow [2] and CS [24] by performing 70 real-world queries on a codebase consisting of 27KB projects downloaded from Github. The results show that SnippetGen achieves a precision score of 0.846 which outperforms them by 28.5% when the top 1 results are inspected. We also perform a controlled experiment by asking 20 participants to complete 3 tasks with SnippetGen and CodeHow. The results confirm the effectiveness of SnippetGen in programming practices.

The contributions of this paper are as follows:

An intent-enforced code search approach (IECS) is proposed. It can predict potential intents for a query, expand the query with the intents and apply the Extended Boolean Model to retrieve the relevant code without any subsequent modification.

The refinement strategy is applied to refine the intents to ensure the appropriate intents benefit the code search.

SnippetGen, that performs IECS, is implemented. The experiment results show that SnippetGen outperforms CodeHow and CS by 28.5% with a precision score of 0.846.

The rest of this paper is organized as follows. We present the overall structure in Section 2, describe the intent-enriched and intent-enforced components in Sections 3 and 4. Then we describe in-house and controlled experiments in Sections 5 and 6. Finally, we discuss the work, introduce the related work and conclude the paper in Sections 7, 8 and 9.

2 Approach overview

Figure 1 presents the overall structure of SnippetGen which consists of intent-enriched, intent-enforced component. SnippetGen constructs a codebase by collecting projects from github (open source repositories) and indexes the code at the method level using Sourcerer [18]. In the intent-enriched component (as shown in Fig. 1a), SnippetGen records every code modification through the code version tracking service in the background, and exploits the intents from the past records of modifications. Given a query, SnippetGen feeds it to the intent-enforced component (as shown in Fig. 1b) and predicts the potential intents for the query by computing the semantic similarity between the intents and the query. Then SnippetGen expands the query with the potential intents to retrieve the relevant methods without any subsequent modification by considering the impact of both intents and text similarity.

Fig.1

SnippetGen: Overall structure.

Figure 2 gives a screenshot of SnippetGen user interface. After writing some methods, a user can trigger the SnippetGen search facility by right-clicking on the written methods and selecting the SnippetGen menu option (as shown in Fig. 2a). Then SnippetGen sends the query to Sourcerer which, in turn, returns relevant results in the second-level menu. When a result is selected, the code snippet is presented in the Snippet Viewer (as shown in Fig. 2b). If the result matches the user needs, he can click the accept button (as shown in Fig. 2d) to integrate the result to IDE; otherwise he can click the page turn button (as shown in Fig. 2c) to navigate the other results.

Fig.2

A screenshot of SnippetGen user interface.

3 Intent-enriched component

Our personal experience supports an underlying assumption that people are most likely to do what they have been used to do before. In this section, we propose the intent extraction algorithm to extract the intents from each methods past records of modifications. However, each method may have many intents. If SnippetGen incorporates all intent elements for expansion, it may produce even worse results than not expanding the query. Thus SnippetGen considers the refinement strategy to ensure the intents benefit the code search. Algorithm 1 describes this process procedurally in the three steps.

Algorithm 1 IntentExtraction

Input: Original Version O, a set of Modified Version M

Output: Intents

/* step 1: identify modificaion */

foreach m_i in M

∣ Δ_i=m_i-o //obtain the i-th modifications(Δ_i)

∣ add Δ_i to Δ_s; // obtain all modifications(Δ_s)

end

/* step 2: refine modification */

// identify the common modifications

Δ_c= $⋂_{i = 1}^{n}$ Δ_i such that ∀1 ≤ i ≤ n Δ_ci ⊆ Δ_i

foreach Δ_{c
_i} in Δ_c

∣ // obtain the node operations pairs(nop)

∣ from Δ_{c
_i}

∣ Δ_{c
_i} → nop:

∣ // obtain the concrete instances(ci) of types,

∣ methods, variables and constants

∣ from nop

∣ nop→ ci

∣ if abstractMatch(ci) is true

∣ ∣ // ci’s edit type or inheriting type is

∣ ∣ equivalent

∣ ∣ if ci is inconsistent with the mapper

∣ ∣ ∣ omit nop;

∣ ∣ ∣ continue;

∣ ∣ end

∣ ∣ ci = ai;//substitute the abstract

∣ ∣ identifiers(ai) for ci

∣ ∣ build the mapper (ai, ci);

∣ end

end/** step 3 extract intents */

mapper→ intents; //extract the intents from the mapper

method = method+intents; //enrich the method with the intents

Return intents

Step 1: Identifying modifications. For each method m_i, SnippetGen employs ChangeDistiller [14] to compare the AST of the m_i’s old and new versions from the past records of modifications. Then SnippetGen characterizes modifications as a sequence of node operations Δ_i consisting of node insertions, deletions, updates and moves.

Step 2: Refining modifications. SnippetGen uses the modified Longest Common Edit Operation Subsequence (LCEOS) algorithm [26] to identify common node operations pairs $Δ_{c} = ⋂_{n}^{i = 1} Δ_{i}$ such that ∀₁≤i ≤n, Δ_{c
_i} ⊆ Δ_i, by iteratively comparing the node operations pairwise. In these common node operations pairs, if one or more concrete instances of types, methods, variables and constants have the same edit type or inheriting type, despite of different names. SnippetGen thinks these instances are abstract equivalent and generalizes them with abstract identifiers $t, $m, $v and $c to enforce a consistent naming. Meanwhile, SnippetGen records the mapper between the identifiers and the concrete instances. If some subsequent node operations pairs are inconsistent with the current mapper, SnippetGen omits them.

Step 3: Extracting Intents. SnippetGen extracts the intents from the mapper and enriches the intent with the methods description consisting of method signature, FQN and remarks.

Example: Given the method ExcelToDataSet’s original version O, there are two modified versions A, B. SnippetGen employs ChangeDistiller to input (O,A) and output Δ_A = {Update (O₁F₁)}, which shows the variable “Provider” and the variable “Extended Properties” (the line1) are changed to “Microsoft.Ace.OleDb.12.0” and “Excel12.0; HDR=NO” respectively (as shown in Fig. 3a). Similarly, SnippetGen also inputs (O, B) and outputs Δ_B={Update (O₁B₁)} (as shown in Fig. 3b). Thus SnippetGen identifies the longest common node operations pairs, such that Δ_C = Δ_A ∩ Δ_B = {pair1 (Update (O₁F₁), Update (O₁S₁))}, In thesecommon node operations pairs, SnippetGen substitutes the abstract identifiers $v1 and $v2 for (“Microsoft.ACE.OLEDB.12.0”, “Excel12.0; HDR=NO”) in Δ_A, (“Microsoft.ACE.OLEDB.12.0”, “Excel12.0;”) in Δ_B (as shownin Fig. 3c). Meanwhile, it records the mapper ($v1,$v2) = (“Microsoft.Ace.OleDb.12.0”, “Excel12.0; HDR = NO”), (“Microsoft.Ace.OleDb.12.0”, “Excel12.0”). Finally, Snippet-Gen extracts the two intents from this mapper, such that T_A = (“Microsoft.ACE.OLEDB.12.0”, “Excel12.0; HDR=NO”), T_B = (“Microsoft.ACE.OLEDB.12.0”, “Excel12.0;”).

Fig.3

The process of intent extraction.

4 Intent-enforced component

Given a query, SnippetGen predicts the potential intent for the query and incorporates the impact of both intent and textual description on code retrieval.

4.1 Predicting intents

For each method m_i, SnippetGen uses standard tokenization, stop word removal, identifier splitting and stemming to convert the query and the intents into a bag of words [25]. Note that the intent here contains intent itself, method signature, FQN and remarks. Then SnippetGen computes textually semantic similarity scores using the standard Vector Space Model (VSM) [14], and returns the top i potentially semantic intent scores denoted as: $Intent = {{intent}_{1}, {intent}_{2} \dots, {intent}_{n}}$

In VSM, the query and the intents are represented by a vector. The term frequency (tf) of a word is the number of times the word appears in the query or the intents normalized by the total number of words in the query or the intents. The inverse document frequency (idf) of a word is the logarithm of the total number of documents (i.e, the number of intents in the codebase) divided by the number of documents that contain the word.

Example: Given a query “access data from excel”, the tf frequency of words access, data and excel are 0.33, 0.33, 0.33 respectively. Also, let the words access, data and excel appear in 270,872, 154,029, and 800,672 intents and there are totally 7,916,458 intents in the code base, so the inverse document frequencies for the words calculated by the equation $idf (w, D) = lg \frac{| D |}{| {d \in D : w \in d} |}$ are 1.46, 1.71, and 0.99, respectively, where w is a word in the query and d is an intent in the code base D. Finally, the TFIDF scores are 0.48, 0.54, and 0.33 for access, data and excel, respectively.

4.2 Expanding query

A query Q_t containing n terms is defined as: $Q_{t} = {t_{1}, t_{2}, \dots t_{n}}$

For a code snippet, we define the following three features: $F = (f_{1}, f_{2}, f_{3})$

f₁ stands for the intent.

f₂ stands for the FQN, which gives a brief summarization of the methods functionality.

f₃ stands for the method body containing source code statements that implements a functionality.

A query can be expressed in terms of f_i:t_i where t_i ∈ Q_t and f_i ∈ F_t. It means to search a field f_i that contains the term t_i. SnippetGen constructs a Boolean query expression for retrieving code snippets that match the query in terms of text similarity: $\begin{matrix} q_{text} & = & (f_{2} : t_{1} \lor f_{3} : t_{1}) \land (f_{2} : t_{2} \lor f_{3} : t_{2}) \\ \dots \land (f_{2} : t_{n} \lor f_{3} : t_{n}) \end{matrix}$

This query expression retrieves methods that contain the terms t₁, t₂, ⋯, t_n in fields f₂ (FQN) and f₃ (Method Body).

Having obtained k potentially relevant intents, SnippetGen tokenizes the intent and gets a keyword list A_i. Then it constructs Boolean query expressions as follows: $\begin{matrix} q_{{intent}_{i}} & = & f_{1} : {intent}_{i} \land (f_{2} : t_{1} \lor f_{3} : t_{1}) \\ \land (f_{2} : t_{2} \lor f_{3} : t_{2}) \dots \land (f_{2} : t_{k} \lor f_{3} : t_{k}) \end{matrix}$ where t_k ∈ (Q_t - A_i). This query expression searches for methods that contain the intent_i in fields f₁(intent) as well as other query terms in fields f₂ (FQN) and f₃ (Method Body). Note that we remove the terms that appear in A_i from the query Q_t. Because the impact of these terms have been considered in the intent_i element.

A method may be retrieved by more than one query expressions defined above. SnippetGen combines the query expressions into an expanded query for retrieving methods: $q_{expand} = (q_{{intent}_{1}}, q_{{intent}_{2}}, \dots q_{{intent}_{k}}, q_{text})$

Example: Given the query “how to access data from excel”, the query terms Q_t = (access, data, excel). The potentially relevant intent is “Microsoft, Ace, OleDb, 12.0, Excel12.0, HDR=NO”. The associated query expressions are as follows: $\begin{matrix} q_{{intent}_{1}} \\ = (f_{1} : Microsoft, Ace, OleDb, 12.0, Excel 12.0, \\ HDR = NO) \land (f_{2} : access \lor f_{3} : access) \\ \land (f_{2} : data \lor f_{3} : data) \\ q_{text} \\ = (f_{2} : access \lor f_{3} : access) \\ \land (f_{2} : data \lor f_{3} : data) \\ \land (f_{2} : excel \lor f_{3} : excel) \end{matrix}$

4.3 Retrieving code snippets

To retrieve relevant methods given the queries, we adopt the Extended Boolean model (EBM) [9], which combines the characteristics of the VSM and Boolean model. In EBM, a document d is represented as a vector. Given a query expression q_expand = (q_{intent
₁}, q_{intent
₂} ⋯ q_{intent
_k}, q_text), a generalized disjunctive and a generalized conjunctive query are defined as follows: $\begin{matrix} q_{expand - and} = q_{text} & \land & q_{{intent}_{1}} \land q_{{intent}_{2}} \\ \land \dots \land q_{{intent}_{k}} \\ q_{expand - or} = q_{text} & \lor & q_{{intent}_{1}} \lor q_{{intent}_{2}} \\ \lor \dots \lor q_{{intent}_{k}} \end{matrix}$

The similarity between the expanded query q_expand and a document d is computed using p-norm [25] and ranked according to Equations (1) and (2): $\begin{matrix} sim (q_{or}, d) \\ = {(\frac{w_{t_{1}, q}^{p} w_{t_{1}, d}^{p} + w_{t_{2}, q}^{p} w_{t_{2}, d}^{p} + \dots w_{t_{n}, q}^{p} w_{t_{n}, d}^{p}}{w_{t_{1}, q}^{p} + w_{t_{2}, q}^{p} + \dots w_{t_{n}, q}^{p}})}^{\frac{1}{p}} \end{matrix}$ (1) $\begin{matrix} sim (q_{and}, d) \\ = 1 - (\frac{w_{t_{1}, q}^{p} (1 - w_{t_{1}, d}) + \dots w_{t_{n}, q}^{p} (1 - w_{t_{n}, d})}{w_{t_{1}, q}^{p} + \dots w_{t_{n}, q}^{p}})^{\frac{1}{p}} \end{matrix}$ (2) where 1) w_{t_i,q} represents the weight of expanded query term q_i. For the query term related to (f₃: t), its weight is set to 1. For the term related to (f₁: intent _i ) or (f₂: t), its weight is set to 1.5. Because matches in fields f₁ (intent) or f₂ (FQN) are ranked more important than matches in f₃ (Method Body); 2) w_{t_i,d} represents the weight of expanded query term q_i in document d, which is defined as follows:

$\begin{matrix} w_{t, d} \\ = {\begin{matrix} intent . score (if term is a intent) \\ 0.5 + (1 - 0.5) \times f_{t, d} \times \frac{{idf}_{t}}{\max_{i} {idf}_{t}} (otherwise) \end{matrix} \end{matrix}$ (3)

In Equation (3), if the term is an intent (such as “Microsoft,Ace,OleDb,12.0,Excel12.0, HDR=NO”), the weight is the intent score. If the term is not an intent (such as “access”), its weight is measured by the normalized term frequency. f_t,d isthe frequency of the term t in method d, and idf_tis the inverse document frequency of the term t, The constant 0.5 is used for balancing the term weight.

5 In-house experiment

To evaluate SnippetGen, we present our experimental setting, evaluation metrics and experimental results in this section.

5.1 Experimental setting

First, we construct the codebase consists of 27KB projects downloaded from github, containing about 11.7 million source code files and 11.4 million functions written in C#. Second, we collect 70 real-world queries created by Portfolio’s author [12]. Third, we implement the front-end of SnippetGen as a Microsoft Visual Studio 2010 extension and deploy the backend of SnippetGen as a Microsoft Azure cloud service which is performed by Sourcerer running on five Azure virtual machines (including 1 master node and 4 workers). Forth, we employ 20 participants. 6 participants are graduate students who have at least of two years of C# programming experience. The others are PhD students who have 3-6 years of C# programming experience. Each participant is asked to use SnippetGen to address a number of queries reported in Portfolios user study and examine the top 20 search results for each query.

5.2 Research questions

To investigate the overall effectiveness of our approach and the benefit of distinctive features of our approach, we have identified the following research questions:

RQ1: How effective is SnippetGen?

This RQ evaluates the precision of SnippetGen in retrieving relevant code. To answer this question, each participant runs SnippetGen, CodeHow and Google Code Search (CS), using the 3-4 queries and manually inspect the top 20 results returned from each query to judge whether they are relevantor not.

CodeHow is the latest query-expanded code search tool and performs better than all Lucene-based code search tools [24]. Participants use CodeHow and enter the query conditions directly to retrieve the results. CS represents conventional keywords-based code search web applications. Participants should go to the website, look for implementations and extract them by copying and pasting results into the workspace.

RQ2: Is the refinement strategy effective?

One distinctive feature of our approach versus existing code search tools is the refinement strategy (Section 3). It tries to refine the intents. Answers to this research question help us evaluate whether this feature ensure the refined intents benefit the code search or not. To answer this question, we compare two versions of SnippetGen, one with the refinement strategy and the other without the refinement strategy (referred to as SnippetGen_noRS). In the implementation of SnippetGen_noRS. we omit the refinement strategy and expand the query with the all intent elements directly regardless of whether or not the intent is appropriate.

RQ3: Is the Extended Boolean model effective?

Another distinctive feature of our approach versus existing code search tools is the Extended Boolean model used in code retrieval (Section 4). Answers to this research question will shed light on whether this feature is useful for code search or not. To answer this question, we implement a variant of SnippetGen (referred to as SnippetGen_noEB), which uses Apache Lucene to retrieve methods. We compare SnippetGen (using the EBM) and SnippetGen_noEB (using Lucene).

5.3 Evaluation metrics

To evaluate the effectiveness of SnippetGen, we make use of the Precision@k metric: $Precision @ k = \frac{1}{| Q |} \sum_{| Q |}^{i = 1} \frac{{relevant}_{i},_{k}}{k}$ (4) where relevant_i,k represents the relevant methods for query i in the top k returned results, Q is a set of queries. Precision@k takes an average on all queries whose relevant answers could be found by inspecting the top k (k = 1, 5, 10, 20) of the returned methods. A better code search tool should allow developers to discover the needed code by examining fewer returned results. The higher the metric value, the higher the accuracy is.

We also make use of Normalized Discounted Cumulative Gain (NDCG) [17] to measure the precision of a code search based on the graded relevance of the results of a set of queries. It varies from 0.0 to 1.0, with 1.0 representing the ideal ranking of the results. The higher the NDCG value, the higher the accuracy is.

5.4 Experimental results

RQ1: The Overall Effectiveness of SnippetGen

We compare SnippetGen with CodeHow and CS by performing the 70 queries. As Table 1 shows, when the top 1 results are inspected, SnippetGen achieves a precision score of 0.846, which means that 84.6% of the first returned results are relevant methods without any subsequent modification. When the top 5 results are inspected, SnippetGen achieves a precision score of 0.861. These results are considered satisfactory. Note that only the results, which both receive relevant feedback and need not to be modified subsequently, are labeled as relevant. Thus the precision of CodeHow and CS is lower than previous papers, such as ref [2, 10].

Table 1
The comparison among SnippetGen, CodeHow and CS

SnippetGen CodeHow CS

Precision@1 0.846 0.658 0.421

Precision@5 0.861 0.518 0.368

Precision@10 0.792 0.465 0.346

Precision@20 0.762 0.402 0.283

NDCG 0.873 0.712 0.682

	SnippetGen	CodeHow	CS
Precision@1	0.846	0.658	0.421
Precision@5	0.861	0.518	0.368
Precision@10	0.792	0.465	0.346
Precision@20	0.762	0.402	0.283
NDCG	0.873	0.712	0.682

Next we pick out CodeHow for comparative analysis, because CodeHow is the latest code search tool proposed in 2015. As Table 1 shows, CodeHow achieves a score of 0.658 when the top 1 results are inspected. SnippetGen achieves 28.5%, 66.2%, 70.3%, and 89.5% improvements in terms of Precision@1, Precision@5, Precision@10, and Precision@20, respectively. In terms of NDCG, SnippetGen obtains a score of 0.873, which also outperforms the CodeHow (0.712) by 22.6%. In the same way, SnippetGen performs better than CS.

Figure 4 shows the percentage of queries that SnippetGen performs better/worse than CodeHow. When the top 1 returned results are examined, SnippetGen wins in 36% of the queries and loses in 18% of the queries. In terms of the top 5 results, SnippetGen wins in 61% of the queries and loses in only 7% of the queries. The results confirm that the improvement achieved by SnippetGen is statistically significant.

Fig.4

The percentage of queries that SnippetGen performs better/worse than CodeHow code search.

To analyze the reason for the lost cases, we continue to explore what factors are correlated with the accuracy of SnippetGen. We depict the two lost cases (i.e., T1 “Convert utc time to local time” and T2 “How to get Color from Hexadecimal color code”) as shown in Fig. 5(a), which shows that the more method’s past modifications provided, the less common subset is likely to be shared among these modifications, which results in that accuracy can go down. For the draw, the methods are never modified. In this case, SnippetGen should be similar to what other tools could achieve. Different from Fig. 5(a), we depict the two promising cases (i.e., T3 “access data from excel” and T4 “find regular LINQ expressions”) as shown in Fig. 5(b), which shows that the more method’s past modifications provided, the higher accuracy is. It illustrates when methods are similar, adding the modifications may not decrease the number of common modifications, but may induce more identifier abstraction and produce more sufficient intents.

Fig.5

The accuracy of SnippetGen.

The above results illustrate that the accuracy of SnippetGen varies with the similarity and number of past modifications, and the similarity takes precedence over the number. Too many modifications or too few is not good for the accuracy. The more similar modifications are, the higher accuracy is.

RQ2: The Effectiveness of the refinement strategy

To answer this question, we compare SnippetGen with SnippetGen_noRS. As Fig. 5 shows, SnippetGen_noRS achieves precision scores of 0.44, 0.41, 0.43, and 0.41 when the top 1, 5, 10, 20 results are inspected, respectively. SnippetGen achieves 84%, 85%, 83%, and 81% improvement in terms of Precision@1, Precision@5, Precision@10, and Precision@20, respectively. In terms of NDCG, SnippetGen achieves a 43.7% improvement compared with SnippetGen_noRS. The result indicates that the improvement achieved by the refinement strategy is statistically significant.

RQ3: The Effectiveness of the Extended Boolean model

To answer this question, we compare SnippetGen with SnippetGen_noEB. As Fig. 6 shows, SnippetGen_noEB achieves precision scores of 0.72, 0.69, 0.61 and 0.51 when the top 1, 5, 10, 20 returned results are inspected, respectively. SnippetGen outperforms SnippetGen_noEB in terms of Precision@1, Precision@5, Precision@10, and Precision@20. In terms of NDCG, SnippetGen achieves a 24.2% improvement compared with SnippetGen_noEB. The result confirms that the improvement achieved by the Extended Boolean model is statistically significant.

Fig.6

The comparison between SnippetGen and SnippetGen_noRS.

Fig.7

The comparison between SnippetGen and SnippetGen_noEB.

6 A controlled experiment

To evaluate the effectiveness of snippetGen in practice, we still assign 20 participants from the in-house experiment into 5 groups and design 3 programming tasks as follows:

Task 1: LogCat C implement a useful log tool for Android. Main functions: line numbers printing, function calls, Json parsing, XML parsing and Log saving. 5

Task 2: ExcelDataReader C implement a lightweight library written in C# for reading Microsoft Excel files and offers multiple data access and database admin commands. 6

Task 3: Network sockets C implement the endpoints of internet connections between an Android client device and a Java server app over a local network. 7

Each team chooses a task by a lottery and completes the task using SnippetGen and the latest code search tool CodeHow. During the experiment, participants utilized both code search tools, entered a series of queries and searched for the methods that are needed to complete the tasks. To evaluate the accuracy of the two code search tools in retrieving methods based on user queries, we recorded the number of queries the participants used, as well as the methods they examined for completing the tasks. We also asked them to examine the top 10 returned results for each query, and mark which of them need not to be modified manually and are helpful for completing the tasks.

Our results show that the participants entered in total 95 queries to each code search tool during the experiment. Table 2 shows SnippetGen returns around 13%–24% more relevant results than CodeHow for 3 tasks. SnippetGen also outperforms CodeHow in terms of NDCG, which measures the rank of the first relevant returned result.

Table 2
The user study results

Percentage of Useful Results NDCG

SnippetGen CodeHow SnippetGen CodeHow

Task 1 57.5 47.9 0.894 0.784

Task 2 38.5 31.1 0.615 0.496

Task 3 54.9 46.5 0.767 0.679

	Percentage of Useful Results	NDCG
Task 1	57.5	47.9	0.894	0.784
Task 2	38.5	31.1	0.615	0.496
Task 3	54.9	46.5	0.767	0.679

In addition, we conducted a survey by asking 20 participants if SnippetGen is helpful for their programming tasks. 16 (80.45%) participants stated that the more they use SnippetGen, the quicker they write code. 6 (30%) graduate students stated that SnippetGen helps them to come up-to-speed and perform difficult tasks far beyond their technical capabilities, just as the experienced team members have been used to do before. Overall, the user study confirms the usefulness and effectiveness of SnippetGen in programming practice.

7 Discussions

7.1 The incorrect return results

Although SnippetGen is effective, it still cannot locate relevant code for all the queries. One unsuccessful query example is “Convert utc time to local time”. We find that some returned results are actually about “Convert local time to utc time”. Similar examples include “How to change RGB color to HSV”. Because our approach cannot distinguish semantic meanings of different orders of the intent. These examples show the importance of understanding the semantic meanings of potentially relevant code’s intent. In the future, we will perform deeper natural language analysis to achieve better understanding of query and codes intent.

7.2 The quality of the intent

Through the analysis to intent-enriched component, we have obtained the following insights.

Intent Source: The intent is extracted from each methods past records of modifications. No modifications, no intent to occur. It results in SnppetGen not predicting the intents by matching semantic similarity between the query and the intent. According to our user study, the methods without intent make up 25.7% to 38.4% of methods’ volume in codebase. If the method carries no intent, SnippetGen should be similar to what other tools could achieve.

Intent Sensitivity: The intent is closely related to past records of modifications. However, the intent varies inconsistently with the number of the modifications. The more modifications are provided, the fewer common subset is likely to be shared, which results in the problems of over generalization. The fewer modifications are provided, the more common subset is, which results in the problems of overspecification.

Our experiments illustrate that the intent strictly depends on the similarity of the methods past modifications. If the modifications are diverse, SnippetGen extracts the fewer common modifications and obtains the insufficient intent. If the modifications are similar, SnippetGen extracts the more common modifications and obtains the sufficient intent.

To reach the maximum similarity, SnippetGen tries two ways. First, it applies the heuristic algorithm to pick out the most similar modifications from all modifications dynamically. No matter how many times the method is modified, the intent still remains or becomes more sufficient despite a big difference between some modifications. Second, SnippetGen can use the threshold t_s = 0.6 in LCEOS (as shown in the process of identifying common intent) to tolerate inexact matches between modifications. If SnippetGen fails to find any common edit operation between two modifications, it generalizes all concrete instances of types, methods, variables and constants with the abstract identifiers $t, $m,$v and $c, to match edit type or inheriting type.

Intent Refinement: Our work is a query expansion problem whose key factor is the choice of appropriate synonyms. In our case, a method has many intents and each intent has many elements. If SnippetGen incorporates all intent elements for expansion, it may produce even worse results than not expanding the query. Thus we propose the intent refinement strategy to pick out the most commonly-used intents to benefit the code search. However, it might reduce the predictive coverage, because this refinement would result in a loss of the intent information. The number of intents and the number of elements in each intent both decrease through a series of refinement experiences, such as identifying the common node operations pairs and omitting inconsistent node operations. The loss prevents SnippetGen from performing comprehensive search and predicting individual intents for a query.

7.3 Threats to validity

We have identified the following threats to validity:

Threats to internal validity: our empirical study involves human subjects. The limited number and the programming capabilities of the human subjects may bias the results. The process of determining the relevance of a method could be also subjective. We will to conduct experiments and user studies involving more subjects, API methods and programming tasks to further reduce this threat.

Threats to external validity: we have used 70 queries in our in-house experiment. Although these queries are real-world queries collected from Portfolios author [16], admittedly they do not cover all types of queries that a developer may ask. Although our codebase consists of 27KB projects and 11.4 million methods, it is just a tiny sample of all available source code. We will reduce the threats to external threats by investigating more queries over a much larger codebase.

8 Related work

8.1 Code search

Early code search engines are the keywords-based information retrieval techniques [5]. For example, Google (codesearch.google.com), Koders (koders.com) and Krugle (krugle.org) offer only a keyword-based search and file-level retrieval. They generally have limited utility in looking for appropriate code fragments for a particular application. Tools such as Blueprint [15] and Assisme [20] use general search engines to search for results and automatically extract the relevant code snippets from the returned results. However, Stylos and Myers [16] observed that the search results of these code search engines seem inaccurate, because they are not designed to specifically support programming tasks.

To improve the accuracy, later work did semantic search. Originally, the work by Wing looked at matching function signatures [24], but was extended to match more complete formal semantics using prolog and Larchbased [10]. However, these techniques were impractical and did not to really succeed because either they attempted to do too little or too much. Other works in this area such as Specifications signature or type matching does not really find items of interest.

To promise better usability, recent work support free-text query via query expansion either by using an appropriate ontology [7, 8], natural language [22], or collaborative feedback [21]. These existing code search tools seem to yield semantically correct matches, but the search results might be too complex or too slow to meet the user needs. These results still has to be modified [4]. However, SnippetGen could retrieve the more relevant methods without any subsequent modification. Because this tool has the ability of intent predicting and can guess what else the user might do after obtaining the results.

8.2 Query expansion

A query expansion is a commonly-used technology to support free-text query. When the user input is usually vague, adding one or more synonyms of the words appearing in the user queries can enhance the precision of the search result. However, it was observed that automatically expanding a query with inappropriate synonyms may produce even worse results than not expanding the query [18]. The key factor of the query expansion is the choice of appropriate synonyms. Recently, several approaches have been proposed to improve the effectiveness of code search via query expansion.

McMillan et al. propose Portfolio that takes natural language descriptions as “synonyms” and outputs a list of functions or code fragments along with corresponding call graphs [7, 11]. Shaowei Wang recommends code fragments from a short textual query as “synonyms” and proposes a new and specialized query expansion algorithm (instead of using Rocchio) which incorporates structural information and employs parameter tuning. Wang et al. [6] proposed an active code search approach which incorporates user feedback as “synonyms” to refine the query. Dietrich et al. [8] proposed an approach that utilizes feedback and trace ability links to improve the efficacy of future queries. Currently, Fei et al. [2] propose a latest code search technique that could understand the APIs a user query refers to and considers both text similarity and potential APIs.

Our work is viewed as a query expansion, but we differ from others, because we first propose to incorporate intent as “synonyms” for expansion and consider the impact of both potential intents and text similarity on code search. Besides, we propose the refinement strategy in the intent extraction algorithm. This strategy can pick out the appropriate intents which benefit the code search.

9 Conclusion

In this paper, an intent-enforced code search approach (IECS) is proposed. It predicts the intent before performing code retrieval and applies EBM to retrieve the relevant code without any subsequent modification.

In the future, we plan to address the issues discussed in Section 7. Then we plan to either introduce similarity choosing heuristic algorithm to ensure a sufficient intent, or employ the deep learning approach to make the intent become self-improvement in the intent-enriched component. Also in the intent-enforced component, we adopt the deep learning approach for the large-scale codebase to improve search performance. Moreover, we introduce structured call sequences to capture code-usage patterns from method call sequences at a fine-granularity level to synthesize the relevant code with the higher precision.

Footnotes

codesearch.google.com

krugle.org

koders.com

Fully Qualified Name.

https://github.com.codepath android_guides wiki Sending and Receiving Data with Sockets

Acknowledgments

This work was supported by the key scientific research projects of Henan Province in 2015 under Grant No. 15A520022 and High Talent Scientific Research Project. We thank QingHuang for his contribution to this project. We thank all participates in experiments who provided us helpful comments.

References

Niu

, Keivanloo

and Zou

, Learning to rank code examples for code search engines, Empirical Software Engineering (2016), 1–33.

LvF., , et al., CodeHow: Effective Code Search Based on API Understanding and Extended Boolean Model (E), IEEE/ACM International Conference on Automated Software Engineering2015, pp. 260–270.

ChenK., , et al., Automatic semantic modeling of indoor scenes from lowquality RGB-D data using contextual information, Acm Transactions on Graphics33(6) (2014), 1–12.

GalensonJ., , et al., CodeHint: Dynamic and Interactive Synthesis of Methods, International Conference on Software Engineering2014, pp. 653–663.

Fafalios

and Tzitzikas

, Post-Analysis of Keyword-Based Search Results Using Entity Mining, Linked Data, and Link Analysis at Query Time, IEEE International Conference on Semantic Computing2014, pp. 36–43.

Wang

, Lo

and Jiang

, Active code search: Incorporating user feedback to improve code search relevance, Acm/IEEE International Conference on Automated Software Engineering2014, pp. 677–682.

Mcmillan

, et al., Portfolio: Searching for relevant functions and their usages in millions of lines of code, Acm Transactions on Software Engineering & Methodology22(4) (2013), 402–418.

Dietrich

, Cleland-Huang

and Shin

, Learning effective query transformations for enhanced requirements trace retrieval, IEEE/acm International Conference on Automated Software Engineering2013, pp. 586–591.

Carpineto

and Romano

, A survey of automatic query expansion in information retrieval, Acm Computing Surveys44(1) (2012), 159–170.

10.

Mcmillan

, et al., Portfolio: Finding Relevant Functions and Their Usage, International Conference on Software Engineering2011, pp. 111–120.

11.

McMillan

, Grechanik

, Poshyvanyk

, Xie

and Fu

, Portfolio: Finding relevant functions and their usage, In ICSE (2011).

12.

Baeza-Yates

and Ribeiro-Neto

, Modern Information Retrieval: The Concepts and Technology behind Search, Addison-Wesley, 2011.

13.

Biggerstaff

T.J.

, Mitbander

B.G.

and Webster

D.E.

, Program understanding and the concept assignment problem, Communications of the Acm (2010), 482–498.

14.

Fluri

, Wursch

, Pinzger

and Gall.

H.C.

, Change distillingł tree differencing for fine-grained source code change extraction, IEEE Transactions on Software Engineering33(11) (2007).

15.

Stylos

B.J.

and Myers

B.A.

, A Web-Search Tool for Finding API Components and Examples, Proceedings of the Visual Languages and Human-Centric Computing2010, pp. 195–202.

16.

Thummalapenta

B.S.

and Xie

, PARSEWeb: A Programming Assistant for Reusing Open Source Code on the Web, Proc IEEE/ACM Intl Conf Automated Software Eng (ASE 07), ACM Press, 2010.

17.

Linstead

, et al., Sourcerer: Mining and searching internet-scale software repositories, Data Mining & Knowledge Discovery18(2) (2009), 300–336.

18.

Sridhara

, et al., Identifying Word Relations in Software: A Comparative Study of Semantic Similarity Tools, The IEEE International Conference on Program Comprehension2008, pp. 123–132.

19.

Hoffmann

, Fogarty

and Weld

D.S.

, Assieme: Finding and leveraging implicit references in a web search interface for users. ACM Symposium on User Interface Software and Technology, Newport, Rhode Island, Usa, (2007), pp. 13–22.

20.

Vanderlei

T.A.

, et al., A cooperative classification mechanism for search and retrieval software components, Mccarthy, 2007, pp. 866–871.

21.

Chou

S.C.

and Chen

Y.C.

, Retrieving reusable components with variation points from software product lines, Information Processing Letters99(3) (2006), 106–110.

22.

Hayes

J.H.

, Dekhtyar

and Sundaram

S.K.

, Advancing candidate link generation for requirements tracing: The study of methods, IEEE Transactions on Software Engineering32(32) (2006), 4–19.

23.

Zaremski

A.M.

and Wing

J.M.

, Signature matching: A key to reuse, Acm Sigsoft Software Engineering Notes18(5) (1993), 182–190.

24.

Maarek

Y.S.

, Berry

D.M.

and Kaiser

G.E.

, An information retrieval approach for automatically constructing software libraries, IEEE Transactions on Software Engineering17(8) (1991), 800–813.

25.

Salton

, Fox

E.A.

and Wu

, Extended boolean information retrieval, Commun ACM, vol. 26, (1983), pp. 1022–1036.

26.

Hunt

J.W.

and Szymanski

T.G.

, A fast algorithm for computing longest common subsequences, CACM20(5) (1977), 350–353.