# A Survey of Source Code Search: A 3-Dimensional Perspective

Weisong Sun<EMAIL_ADDRESS><EMAIL_ADDRESS>0000-0001-9236-8264 State Key Laboratory for Novel Software Technology,
Nanjing UniversityNanjingJiangsuChina210093 School of Computer Science and
Engineering, Nanyang Technological University50 Nanyang AvenueSingapore639798
,  Chunrong Fang<EMAIL_ADDRESS>0000-0002-9930-7111 State Key
Laboratory for Novel Software Technology, Nanjing
UniversityNanjingJiangsuChina210093 ,  Yifei Ge<EMAIL_ADDRESS>0009-0009-0957-854X State Key Laboratory for Novel Software Technology,
Nanjing UniversityNanjingJiangsuChina210093 ,  Yuling Hu
<EMAIL_ADDRESS>0009-0001-0168-8842 State Key Laboratory for Novel
Software Technology, Nanjing UniversityNanjingJiangsuChina210093 ,  Yuchen
Chen<EMAIL_ADDRESS>0000-0002-3380-5564 State Key Laboratory for Novel
Software Technology, Nanjing UniversityNanjingJiangsuChina210093 ,  Quanjun
Zhang<EMAIL_ADDRESS>0000-0002-2495-3805 State Key Laboratory
for Novel Software Technology, Nanjing UniversityNanjingJiangsuChina210093 ,
Xiuting Ge<EMAIL_ADDRESS>0000-0003-3683-7374 State Key
Laboratory for Novel Software Technology, Nanjing
UniversityNanjingJiangsuChina210093 ,  Yang Liu<EMAIL_ADDRESS>0000-0001-7300-9215 School of Computer Science and Engineering, Nanyang
Technological University50 Nanyang AvenueSingapore639798 and  Zhenyu Chen
<EMAIL_ADDRESS>0000-0002-9592-7022 State Key Laboratory for Novel Software
Technology, Nanjing UniversityNanjingJiangsuChina210093

(2023)

###### Abstract.

(Source) code search is widely concerned by software engineering researchers
because it can improve the productivity and quality of software development.
Given a functionality requirement usually described in a natural language
sentence, a code search system can retrieve code snippets that satisfy the
requirement from a large-scale code corpus, e.g., GitHub. To realize effective
and efficient code search, many techniques have been proposed successively.
These techniques improve code search performance mainly by optimizing three
core components, including query understanding component, code understanding
component, and query-code matching component. In this paper, we provide a
3-dimensional perspective survey for code search. Specifically, we categorize
existing code search studies into query-end optimization techniques, code-end
optimization techniques, and match-end optimization techniques according to
the specific components they optimize. Considering that each end can be
optimized independently and contributes to the code search performance, we
treat each end as a dimension. Therefore, this survey is 3-dimensional in
nature, and it provides a comprehensive summary of each dimension in detail.
To understand the research trends of the three dimensions in existing code
search studies, we systematically review 68 relevant literatures. Different
from existing code search surveys that only focus on the query end or code end
or introduce various aspects shallowly (including codebase, evaluation
metrics, modeling technique, etc.), our survey provides a more nuanced
analysis and review of the evolution and development of the underlying
techniques used in the three ends. Based on a systematic review and summary of
existing work, we outline several open challenges and opportunities at the
three ends that remain to be addressed in future work.

source code search, deep learning, query-end optimization, code-end
optimization, match-end optimization

††copyright: acmcopyright††journalyear: 2023††doi:
10.1145/1122445.1122456††journal: TOSEM††journalvolume: 0††journalnumber:
0††article: 1††publicationmonth: 0††ccs: Software and its engineering Search-
based software engineering

##  1\. Introduction

Software development is usually a repetitive task, where the same or similar
implementations exist in established open-source projects (e.g., GitHub
repositories (GitHub, 2008)) or online forums (e.g., Stack Overflow (Inc;,
2008)). Software developers on average spend about 19 percent of their
development time in searching the relative code over a large-scale codebase,
because they can reuse or modify previously written code snippets to improve
the efficiency of project development (Brandt et al., 2009). (Source) code
search aims to retrieve relevant code in large-scale code corpora for a
developer’s given query requirements. Reusing the retrieved high-quality code
can effectively improve the productivity and quality of software development,
which makes code search receive widespread attention from software engineering
researchers. Besides, code search provides more opportunities for code reuse,
which is an earlier concept than code search (Standish, 1984; Frakes and
Nejmeh, 1987; Sun et al., 2022). Code reuse aims to modify an existing code
into a new code according to the requirements, while code search makes it
possible to find the available one. In other words, code reuse can be realized
through code search, further proving the considerable research value and
significance of code search.

The most ideal code search can convert the query target input into the most
relevant code snippet and return it to the user (Liu et al., 2018; Gu et al.,
2018). In fact, many developers currently rely on Google, Baidu, and other
search engines for code search, but the search results are arrestingly
unsatisfactory. The search logic or methods used by common search engines are
not suitable for matching natural language and code pairs. In most cases, the
search results are not available for developers to refer to, which will take
them more time to change or choose a better query (Cambronero et al., 2019;
Nie et al., 2016; Karnalim, 2018). Given the importance of code search, there
is great interest in implementing better methods for retrieving relevant code
snippets from the code corpus, depending on the developer’s intent expressed
as a search query.

Code search can be narrowly defined as a technique that takes as input a
natural language query given by a user, then selects the closest or possible
answer from the code corpus and returns it to the developer as an output. Of
course, there exist a few individual code search techniques that take some
non-natural language queries as input or return the output into other forms
such as API interface (Mar et al., 2011) or I/O examples (Stolee et al.,
2016). In this paper, we mainly study the mainstream code search scenario,
where the query is natural language text and the search results are
method/function code snippets. By organizing and conducting a statistical
analysis of articles on code search that fit our main study, we can get a
glimpse of the development history of code search techniques. Around the
1960s, the concept of code search emerged (Polydoros and Weber, 1984;
Kobayashi and Niimi, 1989; Floyd and Kinser, 1990). Subsequently, with the
development of open-source platforms, the number of papers related to code
search has risen rapidly since 2009, and dozens of related papers appear in
the field every year. Over the past nearly sixty years, many techniques have
been successfully applied in code search, and there are also surveys and
summaries of these techniques (Liu et al., 2022; Rahman and Roy, 2021; Grazia
and Pradel, 2022). These surveys either only focus on the query or code-end
optimization or shallowly introduce various aspects of code search tools,
including codebase, evaluation metrics, modeling techniques, etc. For example,
Rahman et al. (Rahman and Roy, 2021) explore the application of automatic
composition query technology in code search, mainly reflected in the
classification of algorithms, assessment of the quality of results and the
future constraints and challenges of query reformulation. Another existing
survey conducted by Liu et al. (Liu et al., 2022) focuses on analyzing the
existing code search tools, discusses and learns from the specific search
content of the tools, and proposes relevant indicators for evaluating code
search tools. In the latest survey completed by Luca et al. (Grazia and
Pradel, 2022) in 2022, the code search process, including query processing,
code search models training, search results sorting and pruning are discussed
and summarized.

However, a systematic review of various optimization techniques involved in
different core components in code search techniques is still lacking. From the
view of technical composition, both early and recent code search techniques
are composed of three core components, including a query understanding
component, a code understanding component, and a query-code matching
component. The query understanding component and the code understanding
component are responsible for mining and representing the features of the
query and code snippet, respectively. The query-code matching component is
responsible for ranking a set of candidate code snippets according to how
closely their representations semantically match the query. The lack of a
systematic review of the optimization techniques involved in these components
hinders developers/researchers from identifying technology trends for each
core component, as well as the challenges and opportunities faced in
optimizing different components.

In this survey, we propose a novel approach for summarizing code search
techniques from a 3-dimensional perspective. Specifically, according to the
specific components they optimize, we first classify existing code search
techniques into three categories: query-end optimization techniques, code-end
optimization techniques, and match-end optimization techniques. Each end
exposes a perspective through which we can understand and dissect the
essential optimizations/improvements made by existing code search techniques.
Therefore, this survey investigates code search techniques from three
perspectives, referred to as a 3-dimensional perspective. Then, we perform a
systematic literature review of the optimization techniques proposed in the
three ends. We carefully select 68 representative papers from the 1,427
candidates. Among these 44 papers propose solutions for query-end
optimization, 50 papers for code-end optimization, and 52 for match-end
optimization. Since some papers may propose optimization techniques for
multiple ends, there will be some overlapping papers in the three ends.
Finally, we tease out the development history of optimization techniques
proposed for each end and summarize the development trends. Building on a
thorough review of optimization techniques proposed in existing code search
papers, we outline persistent challenges that necessitate further attention.
Additionally, we present potential research opportunities in the code search
field.

The main contributions of this survey include:

  * •

We propose a novel systematic review of 2,191 code search techniques published
in journal papers, conference papers, and arxiv papers up to September 30,
2023, as a starting point for future code search research.

  * •

We analyze 68 different code search techniques and conduct analysis from a
3-dimensional perspective to explore these techniques’ innovations in the
query-end optimization, code-end optimization, and match-end optimization.
This survey will help subsequent researchers to enumerate their
characteristics.

  * •

We divide code search techniques into three categories according to the
specific components they optimize, and analyze the evolution of techniques in
each category over time as a basis for further comparison and benchmarking.

  * •

We highlight opportunities and challenges in code search research based on our
findings to stimulate further research in this field. Some resources,
datasets, and code can be found at https://github.com/wssun/SourceCodeSearch.

Structure of the paper: The remainder of this survey is organized as follows.
Section 2 briefly introduces the background of code search. Section 3 presents
the survey methodology that we follow. Section 4, 5, and 6 summarize the key
research questions we investigate and their answers in this study. Section 7
discusses the challenges for the road ahead on code search techniques and
presents the potential research opportunities for future work. Section 8 shows
the potential threats that may affect the validity of this review. Finally,
Section 9 provides a conclusion of this survey.

##  2\. Background

In this section, we will introduce the background of code search, including
code search definition and code search techniques.

###  2.1. Code Search

Since the existing works improve and implement the code search task using
different techniques, there is no formal problem definition for the code
search task. In this paper, we survey a wide range of code search research,
including early information retrieval (IR)-based code search research and
recent deep learning (DL)-based code search research. To the best of our
knowledge, there is no strict definition of general code search. We
investigate the widely-studied code search scenario, where the query given by
the developer is a short natural language text, and the search result is a
code snippet of a method/function (Linstead et al., 2009; Liu et al., 2022;
Satter and Sakib, 2016; Gu et al., 2018; Feng et al., 2020; Gu et al., 2021;
Sun et al., 2022). Formally, let $q=\\{w_{1},w_{2},\cdots,w_{m}\\}$ be a query
given by the developer, where $w_{i}$ is the $i$-th word in $q$;
$S=\\{s_{1},s_{2},\cdots,s_{n}\\}$ be a large-scale code corpus, where $s$ is
a code snippet; code search is defined as follows.

###### Definition 0 (Code Search).

Code search is the task of retrieving a code snippet $s\in S$ for $q$ that
satisfies the following conditions:

  * •

$\forall s^{\prime}\in S,s^{\prime}\neq s$

  * •

$\bm{q}=\Phi(q)$

  * •

$\bm{s}=\Psi(s),\bm{s^{\prime}}=\Psi(s^{\prime})$

  * •

$sim(\bm{q},\bm{s^{\prime}})\leq sim(\bm{q},\bm{s})$

where $\Phi(\cdot)$ and $\Psi(\cdot)$ are functions designed to represent
features of query and code snippet, respectively. $sim(\cdot)$ is a function
that measures the similarity between two feature representations of the query
and code snippet.

Figure 1. Examples of code search

We focus on investigating free-text code search where queries given by
developers are free-form natural language text and search results are method-
level code snippets. This is the most practical, common, and widely researched
code search application scenario (Cambronero et al., 2019; Liu et al., 2022).
Figure 1 shows two examples of code search. In both examples, queries are
natural language descriptions and code snippets are methods written in
programming languages (e.g., Java and C/C++). From Figure 1(a) and (c), we can
observe that the former ($q_{1}$) wants to find a code snippet calculating the
factorial of a number, while the latter ($q_{2}$) aims to retrieve a code
snippet implementing the functionality of counting the number of digits in an
integer value. Obviously, the two queries have different intents or
requirements. The query understanding component is responsible for capturing
the intents/semantics in the natural language query. Figure 1(b) and (d) show
two code snippets. All code search systems require a code understanding
component, which is responsible for capturing the semantics in the programming
language code snippet. Intuitively, a good code search technique requires
understanding the semantics of both the query and the code snippet. Only in
this way, can it retrieve the code snippets that satisfy the query intents.

###  2.2. Code Search Techniques

Figure 2. Overall framework of the code search technique

Figure 2 shows the overall framework of the code search technique. The goal of
the code search technique is to retrieve relevant code from a large-scale code
corpus according to the intent of the developers’ query. A typical code search
system/tool contains three components: a query understanding component, a code
understanding component, and a query-code matching component. The query
understanding component is responsible for processing the natural language
queries given by developers, such as mining and representing the key
information (also called features/semantics) from the query. The code
understanding component is responsible for processing the programming language
code snippets in the code corpus, such as mining and representing features
from the code snippets. The query-code matching component is responsible for
ranking code snippets according to how well they semantically match the query.
So, to implement effective and efficient code search, existing works have
proposed various techniques to optimize these three components. In this
survey, according to the specific components they optimize, we divide the
existing code search studies into the following three categories: query-end
optimization techniques, code-end optimization techniques, and match-end
optimization techniques.

Query-end Optimization. Given a query, query-end optimization aims to produce
a query representation that not only preserves the core semantics of the query
but also facilitates the computing of matching components, thereby improving
the effectiveness and efficiency of code search. The query understanding
component produces such a representation through two sequential steps: query
feature mining and query feature representation. The query feature mining step
treats the raw query given by the developer as input and extracts the
important features from the raw query. Considering that the raw query may be
of low quality and contains few useful features, existing works propose a
variety of techniques to automatically optimize the quality of the features
extracted from the raw queries (Lu et al., 2015; Nie et al., 2016; Lu et al.,
2018; Rahman and Roy, 2021; Wang et al., 2022). In this survey, we investigate
four classic techniques for optimizing query quality, including query
reduction, query replacement, query expansion, and query transformation
(details are described in Section 4.1). The query feature representation step
takes in the features extracted by the query feature mining step and produces
a semantic-preserving feature representation. Such a representation will be
used to rank a large number of code snippets in the query-code matching
component. From another perspective, query representation techniques are
equally important. They also determine the final performance of the code
search techniques, because accurate representation of semantic features in
queries can assist code search models in retrieving code snippets correctly.
Existing works propose many techniques to optimize the process of feature
representation (Sachdev et al., 2018). We divide the query representation
methods utilized in existing technologies into two categories: IR-based
feature representation and DL-based feature representation. IR-based
representation methods always regard queries as vectors or plain texts, which
can be utilized easily to optimize the query-end by the researchers. DL-based
feature representation methods apply deep neural networks to encode the query.
They are frequently adopted by existing code search techniques because they
yield better semantic representations of queries. Details of query feature
representation are described in Section 4.2.

Code-end Optimization.  Given a code snippet, code-end optimization aims to
produce a code representation that not only preserves the core semantics of
the code but is also convenient for subsequent query-code matching computing,
thereby improving the effectiveness and efficiency of code search. Like the
query understanding component, the code understanding component produces such
code representation through two sequential steps: code feature mining and code
feature representation. The code feature mining step treats the raw code
snippet in the code corpus as input and extracts its important features.
Considering that the raw code snippet may be complex and contains noise
features, existing works propose a variety of techniques to automatically
optimize the quality of the features extracted from the raw code snippets (Gu
et al., 2018; Allamanis et al., 2018; Cambronero et al., 2019; Wan et al.,
2019; Wang et al., 2020b; Ling et al., 2021; Zeng et al., 2023; Yu et al.,
2022). It is a common practice to characterize code features from two aspects:
textual features and structural features. In this survey, we investigate three
textual features and four structural features commonly used in code search
works (details are described in Section 5.1). The code feature will be further
passed into the code representation step to produce semantic-preserving
feature representations. Such a representation will be used to rank a large
number of code snippets in the query-code matching component. To make the
resulting representation as semantically preserving as possible, existing
works propose many techniques to optimize the process of code feature
representation (Sachdev et al., 2018). Like query feature representation, we
also divide code feature representation techniques into two categories: IR-
based feature representation and DL-based feature representation. IR-based
feature representation treats the code primarily as text, supplemented by
additional information to represent it more comprehensively. DL-based feature
representation techniques apply deep neural networks to embed the code
features. Details of code feature representation are described in Section 5.2.

Match-end Optimization. Given a query representation and a set of code
representations, match-end optimization aims to rank code representations
based on their relevance to the query representation. Different techniques
adopt different methods to calculate the relevance scores. In this survey, we
investigate three widely used matching methods, including text-based matching,
vector distance-based matching, and classification-based matching. Text-based
matching methods measure the relevance scores by calculating the distance
between the keyword-based or IR-based query feature representation and the
keyword-based or IR-based code feature representation. Vector-based matching
methods measure the relevance scores by calculating the distance between the
query feature vectors (including embeddings) and the code feature vectors.
Vectors are produced by traditional IR techniques or advanced DL techniques.
Classification-based matching methods measure the relevance scores by using
neural network classifiers to predict the probability of semantic relevance of
the query embeddings and the code embeddings.

##  3\. Survey Methodology

We follow the guidelines for the systematic literature review (SLR) in
software engineering (Staffs et al., 2007; Kitchenham and Brereton, 2013a;
Petersen et al., 2015) to conduct this survey. We start this survey by asking
three research questions and then comprehensively analyze the various
optimization techniques used in code search.

###  3.1. Research Questions

The research questions are one of the most important contents of the
literature review, which guide us to clarify the research direction and thus
conduct a purposeful investigation. In this survey, we want to explore,
classify, and summarize the various optimization techniques used in code
search to date in query-end optimization, code-end optimization, and match-end
optimization. These three dimensions are the core components of the code
search techniques and the main perspectives for researching code search
techniques in this survey. Therefore, we investigate the following three
research questions (RQs):

  * •

RQ1. What are the query-end optimization techniques in code search studies?
The purpose of this RQ is to investigate which techniques are applied to query
processing (including query feature mining and query feature representation)
and the development trend of query-end optimization techniques.

  * •

RQ2. What are the code-end optimization techniques in code search studies?
This RQ aims to investigate which code features are used in code-end
optimization techniques, how they represent involved code features, and the
development trend of code-end optimization techniques.

  * •

RQ3. What are the match-end optimization techniques in code search studies?
The goal of this RQ is to investigate how match-end optimization techniques
match the representations of the query and code features to rank the expected
code snippet in a higher rank and the development trend of match-end
optimization techniques.

In the process of seeking the answers to these questions, we also find the
deficiencies and limitations of the existing code search techniques. As a
reference, we put forward some suggestions and directions for future research.

Figure 3. Selection of research studies

###  3.2. Search Strategy

Collecting published papers requires selecting appropriate publication
databases and searching keywords. In this survey, we selected six widely
available electronic databases, including DBLP publication database
111https://dblp.uni-trier.de, Google scholar database
222https://scholar.google.com/, IEEE Explore database
333https://ieeexplore.ieee.org/, ACM Digital Library 444https://dl.acm.org/,
Web of Science database 555https://www.webofscience.com/, and ArXiv database
666https://arxiv.org/. It is worth noting that, considering that some
researchers are willing to disclose the latest research techniques on ArXiv in
advance, we also collected the code search papers that have been made public
on ArXiv but not accepted by any journal or conference. In terms of selecting
searching keywords, we referred to the PIO (Population + Intervention +
Outcome) criteria (Kitchenham and Brereton, 2013b) and used the population
terms and intervention terms from code search field to construct keywords, as
in previous studies (Rahman and Roy, 2021). Population terms covered all
aspects of the research topic. In this survey, we used “Code Search”, “Code
Retrieval”, “Code Recommendation”, and “Code Reuse” as the population terms.
Intervention terms focus on a specific aspect of the research topic. We used
“Query Expansion”, “Query Reduction”, and “Query Transformation” as the
intervention terms for RQ1. Relevant papers up to September 30, 2023, were
included in our search results. As Figure 3 shows, we retrieved 2,191 relevant
papers from six databases in total as Outcome after removing duplicated
studies.

###  3.3. Study Selection

Once those candidate studies were collected, we made a gradual selection
according to the filter conditions (C) we carefully set up.

  * •

C1. eliminating book, thesis, and short papers (our definition of short essay
papers: less than five pages); only needing journals and conferences.

  * •

C2. only selecting technical papers, excluding technical reports, empirical
studies, and surveys.

  * •

C3. choosing the papers about the field of code search, and also needing to
meet the requirements that have a technical innovation in one of the ends.

According to the three conditions, manual experiments were carried out to
select the final range from the candidate papers. The first manual experiment
obtained the page number and published source of the whole paper. We obtained
a total of 1,427 papers (including 708 conference papers, 645 journal papers,
and 74 arxiv papers) according to the requirements of Condition C1. In the
second manual experiment, we judged whether the remaining papers meet
Conditions C2 and C3 based on the title, abstract, and approach part.

Figure 4. 1,427 code search papers from 1965 to 2023. Please replace the data
in this figure with our data.

We grouped the collected 1,427 papers by year of publication, and the
statistical results are shown in Figure 4. It is observed that the number of
relevant papers has increased significantly since 2005, indicating that the
problem of code search has received significant attention.

(a) Group by Year

(b) Group by Venue

Figure 5. 68 papers on code search discussed in this article

After screening all the conditions, we finally identified a total of code
search studies related to our research. For this study, we carefully selected
representative papers from the candidates and conducted a systematic analysis,
and finally, 68 studies are selected. According to the three questions we
raised above, these papers are divided into three relevant categories, among
which 44 papers are related to RQ1; 50 papers are related to RQ2; and 52
papers are related to RQ3. Since some papers may propose optimization
techniques for multiple ends, there will be some overlapping papers in the
three RQs. It should be noted that we will focus on introducing the
optimization techniques proposed by each paper on the corresponding end in
different RQs. Figure 5(a) presents the number of papers we discuss per year
of publication, illustrating the increasing relevance of the topic. Figure
5(b) shows that 47.1% of them were published in conference proceedings,
accounting for the largest proportion, followed by Journal (39.7%) and ArXiv
(13.2%).

##  4\. Answering RQ1: What are the query-end optimization methods in code
search studies?

In the realm of code search, the quality of a query is paramount as it
directly influences the quality of the search results (Rahman et al., 2016,
2019). A low-quality query, characterized by the use of uncommon abbreviations
or redundant and noisy phrases, may result in the retrieval of suboptimal code
snippets. As a countermeasure, researchers have progressively proposed a
variety of optimization techniques aimed at optimizing and understanding user
queries. These endeavors collectively serve to enhance the performance of code
search. In a nutshell, query-end optimization endeavors to elevate the quality
of user queries, consequently heightening the quality of code search.

As shown in Figure 2, the optimization techniques employed at the query end
can be mainly categorized into two facets: feature mining from the user query
and subsequent representation of these extracted query features. For query
feature mining, existing efforts predominantly fall within three categories:
query reduction, query expansion, and query transformation. Query reduction
improves the quality of the user query by eliminating redundant content (Liu
et al., 2019). Query expansion is to enrich the user query by incorporating
available information, such as software-specific expansion words sourced from
Stack Overflow (Lu et al., 2015; Nie et al., 2016). Query transformation first
transforms the user query into an alternative form, such as API (Raghothaman
et al., 2016), and then retrieves related code snippets using the transformed
form. Figure 6 lists some representative works of the three types of query
feature mining techniques at various temporal junctures. More details of these
techniques are discussed in Section 4.1. As for query feature representation,
existing endeavors are generally classified into two classes: IR-based methods
and DL-based methods. The main difference between the two lies in the adoption
of different techniques to embed the natural language4 query and generate the
corresponding vector representations. Figure 7 presents some notable works of
the two categories of query feature representation techniques across different
points in time. More details of query feature representation are discussed in
Section 4.2. In the following subsections, we will intricately introduce the
three types of query feature mining techniques and the two categories of query
feature representation techniques aforementioned in detail. Additionally, we
will succinctly encapsulate their trajectories of development and emerging
trends.

for tree= grow=east, reversed=true, anchor=base west, parent anchor=east,
child anchor=west, base=left, font=, rectangle, draw=black, rounded corners,
align=left, minimum width=4em, edge+=darkgray, line width=1pt, s sep=3pt,
inner xsep=2pt, inner ysep=3pt, line width=1pt, , where level=1text
width=10em, font=, where level=2text width=4.5em, font=, where level=3text
width=4.5em, font=, where level=4text width=4.5em, font=, where level=5text
width=4.5em, font=, where level=6text width=4.5em, font=, where level=7text
width=4.5em, font=, where level=8text width=4.5em, font=, where level=9text
width=4.5em, font=, [Query
Feature
Mining [ Query Reduction
(§4.1.2) [ [ (Yu et al., 2016) [ [ [ (Huang et al., 2019) [ [ [ [ (Wang et
al., 2023)]]]]]]]]] ] [ Query Expansion
(§4.1.2) [(Lv et al., 2015; Lu et al., 2015) [ (Nie et al., 2016) [ (Yang and
Huang, 2017) [(Lu et al., 2018; Zhang et al., 2018)
(Karnalim, 2018; Huang et al., 2018) [(Liu et al., 2019; Huang et al., 2019) [
(Hu et al., 2020b) [ (Cai et al., 2021) [ [ (Mao et al., 2023) ]]]]]]]]] ] [
Query Transformation
(§4.1.3) [ [ [ [ (Sirres et al., 2018) [ [ [ (Ling et al., 2021) [ (Wang et
al., 2022) [ (Tang et al., 2023) ]]]]]]]]] ] ]

(year)201520162017201820192020202120222023

Figure 6. Evolution of feature mining techniques in query end

###  4.1. Query Feature Mining

####  4.1.1. Query Reduction

As mentioned earlier, query reduction strives to eliminate superfluous
components from the query, which contributes to the code search technique to
grasp the core intent of the query accurately, thereby enhancing performance.
Existing studies (Haiduc et al., 2013; Rahman and Roy, 2016) find that the
keywords that occur in more than 25% of the documents in a corpus are less
discriminating. Thereby, the key of query reduction is to remove the
redundant, noisy, ambiguous, or less discriminating keywords (Rahman and Roy,
2021), making the results of code search more reasonable and suitable for
users to reuse. The first line of Figure 6 shows the code search papers that
employ query reduction to reformulate user queries. It can be seen intuitively
that query reduction is less common for code search. In the following, we will
detail how these two code search works perform query reduction.

Yu et al. (Yu et al., 2016) propose an information retrieval-based technique
called APIBook to help users search the code of API methods. Given a user
query also called “API description” in their paper, APIBook extracts semantic
information and type information from the query. The extracted information
will be used for matching later. The semantic information of an API
description refers to the meaning of words in the API description. They use
nouns, verbs, and adjectives as the semantic information of the API
description. The type information of an API description refers to the
information that concerns types, such as “String” and “StringBuilder”. In
simple terms, they perform query reduction by removing content other than
semantic and type information, such as stop words, prepositions, and adverbs.

Huang et al. (Huang et al., 2019) propose a deep learning-based method called
QESC for effective query expansion. Although only query expansion is
emphasized in the title of the paper, QESC also performs query reduction.
Therefore, it can be said that QESC employs a combination of query expansion
and query reduction to optimize query feature mining. In this section, we
focus on how QESC performs query reduction, and the content of query expansion
is introduced in Section 4.1.2. Specifically, they decompose the code search
into two steps: first-pass retrieval and second-pass retrieval. In the first-
pass retrieval, on receiving a query, the search engine produces the initial
query results. They train an inference model based on the Deep Belief Network
(Hinton et al., 2006), which can infer the fine-grained changed code terms
that will most likely occur in the initial results. They represent a code term
by a triplet of ($\langle label\rangle,\langle role\rangle,\langle
operation\rangle$). $\langle label\rangle$ represents the textual information
of Abstract Syntax Tree (AST) nodes. $\langle role\rangle$ has two options
that decide if a term is changed or dependent. $\langle operation\rangle$ has
three operations that decide if a term is unchanged, new, or deleted. In the
second-pass retrieval, they reformulate the query with the selected changed
terms. If the $\langle operation\rangle$ of the term is “deleted”, they see it
as an irrelevant term and remove its $\langle label\rangle$ from the query. In
short, QESC performs query reduction by deleting irrelevant terms identified
by the inference model.

Wang et al. (Wang et al., 2023) find the existing code search tools usually
return a ranked list of candidate code snippets without any explanations,
making the developers often find it hard to choose the desired results and
build confidence on them. To address this issue, they propose XCoS, an
explainable code search approach based on query scoping and knowledge graph.
Query scoping essentially performs the process of query reduction, aiming to
extract different parts from a query, including functionalities, functional
constraints, and nonfunctional constraints. Specifically, given a query, XCoS
first removes the starting words for a question, such as “how to” and “how can
I”. Then XCoS uses an NLP tool spaCy to analyze the part of speech and
dependence tree of the remaining query. After that XCoS extracts different
parts from the query using linguistic rules. The linguistic rules for the code
search query are borrowed from the NLP field where linguistic rules are
commonly used to extract functionality and constraints (Hussain et al., 2008;
Treude et al., 2015; Pandita et al., 2016). To build linguistic rules, they
randomly sample 50 question titles as a validation dataset to iteratively
refine and validate the rules by observing the extraction results. In the
rules, VERB, DOBJ, PREP, POBJ, and MOD denote verb, direct object,
preposition, preposition object, and modifier, respectively. Based on these
rules, they summarize that Functionality: VERB or VERB DOBJ; Functional
Constraint: PREP POBJ, to VERB DOBJ, or using DOBJ; Nonfunctional Constraint:
adverbs, adverb clauses, relative clauses, or phrases such as in MOD way that
are used to modify or qualify the functionalities or functional constraints.
XCoS composes the functionality part and functional constraint part together
to retrieve code snippets. The knowledge graph is used to guide the generation
of explanations for code snippets and its construction is an offline task. In
practice, given a query, XCoS first identifies different parts (i.e.,
functionalities, functional constraints, nonfunctional constraints) from it
and uses the expressions of functionalities and functional constraints to
search the codebase. It then links both the query and the candidate code
snippets to the concepts in the knowledge graph and generates explanations
based on the association paths between these two parts of concepts together
with relevant descriptions.

####  4.1.2. Query Expansion

Query expansion is to expand the user’s original query through the inclusion
of other available information, such as synonymous words. This approach serves
as a strategy for reformulating queries, particularly in cases where the
original query yields a poor retrieval result. Originally, in the field of
information retrieval, query expansion was used for cross-language information
retrieval (Cao et al., 2007), the words/terms suggested by query expansion
techniques can rich retrieval code results. Given the effective promotion of
search performance, the researchers in the software engineering community
introduce them to code search tasks. The second line Figure 6 presents the
code search papers that leverage query expansion to enrich user queries. It is
apparent that, compared with query reduction, query expansion has garnered
extensive attention and application within code search. Subsequently, we will
discuss how these code search endeavors conduct query expansion.

Lv et al. (Lv et al., 2015) find that one major limitation of existing code
search tools is the lack of query understanding. These tools often adopt
conventional text similarity matching techniques to retrieve relevant code
snippets. They do not consider query understanding, which could lead to
inaccurate return results. Therefore, they propose CodeHow, a code search
approach that considers both API understanding and text similarity matching.
CodeHow understands a query by identifying the APIs that the query may refer
to. CodeHow expands the user query with the identified APIs and applies the
Extended Boolean model to retrieve the code snippets that match the expanded
query. Specifically, CodeHow decomposes code search into two phases, i.e., the
API understanding phase and the code retrieval phase. In the API understanding
phase, CodeHow first collects the description of each API in the API library
from its online documentation. It then calculates two similarity values, one
between the API description and the query, and one between the API name and
the query. Finally, it returns the potentially relevant APIs that match the
query according to two similarity values. In the code retrieval phase, CodeHow
constructs a Boolean query expression for retrieving code snippets that match
the query in terms of text similarity. It retrieves code snippets that contain
the potentially relevant API as well as other query terms in the method body
and method name. CodeHow also constructs Boolean query expressions for each
API recommended in the API understanding phase, which are intended to search
for code snippets that contain the potentially relevant API. The query
expressions above are combined to obtain an expanded query expression for
retrieving code snippets. Finally, the expanded query expression is passed to
an Extended Boolean Model as the input, which will return relevant code
snippets according to their similarity to the expanded query expression.

To overcome the term mismatch problem inherent in text retrieval-based
techniques, Nie et al. (Nie et al., 2016) propose Query Expansion based on
Crowd Knowledge (QECK) to improve the performance of code search.
Specifically, given a query, QECK ranks all Question & Answer (Q&A) pairs
collected from Stack Overflow 777https://stackoverflow.com/ using the
information retrieval model Lucene 888http://lucene.apache.org. The top-$m$
Q&A pairs are identified as the Pseudo Relevance Feedback (PRF) documents,
which will be treated as relevant to the query. Then, QECK identifies useful
expansion words from PRF Q&A pairs. Each word in PRF Q&A pairs is assigned an
expansion weight. According to the weights of words, top-$n$ words are
selected as useful expansion words and added to the original query to generate
the expanded queries. Finally, QECK ranks all code snippets in the corpus for
the expanded query, and the top $k$ code snippets are recommended to
developers as the search results.

Yang et al. (Yang and Huang, 2017) discover a significant issue where code
search results are often modified manually. This phenomenon is caused by the
inability to predict intent accurately with code search tools. To address this
problem, they propose an intent-enforced code search approach called IECS.
IECS can predict potential intents for a query before performing code
retrieval. It utilizes intent to enhance the search to meet user needs.
Specifically, IECS extracts intents from the given query by the intent
extraction algorithm. This algorithm first uses the AST to identify
modifications from the past method records. It then records the mapper between
the identifiers and the concrete instances according to the modifications.
After that, IECS can extract the intents from the mapper. Finally, it expands
the query with intents and applies the Extended Boolean Model to retrieve the
relevant code without any subsequent modification.

Zhang et al. (Zhang et al., 2018) find that the proportion of identifiers
(e.g., class and method names) plays a key role in retrieving relevant code
examples from code search engines. Therefore, they propose to perform query
expansion by recommending semantically related identifiers (particularly
Application Program Interface (API) class-names) to expand natural-language
queries. Specifically, they first use the continuous bag-of-words model (CBOW)
(Mikolov et al., 2013a) to extract vector representations that are used to map
natural-language queries with identifiers. Then based on similarities between
vector representations of the query and API class-names, they find relevant
API class-names (identifiers) from the corpus to expand the given query.
Finally, they retrieve code snippets from the corpus by executing the expanded
query.

Lu et al. (Lu et al., 2018) find that formulating (e.g., exchanging, adding,
and deleting) the related words identified based only on the positional
proximity is not enough to optimize the query. The presence of word relations
prevalent within the source code, such as compound words and synonyms, are
useful for query reformulation. Therefore, they propose a novel method called
INQRES to interactively leverage these word relations to expand the query.
Specifically, given a query, INQRES first extracts meaningful keywords from
it. Then INQRES expands the keywords based on identifiers from the source
code, meaningful words from the comments, and synonyms from the WordNet
thesaurus (Leacock and Chodorow, 1998). To find related expansion words from
the three sources, INQRES excavates five word relations in the source code,
including the Inheritance Relation (InR), Implementation Relation (ImR),
Synonym Relation (SynR), Same-word Relation (SamR) and Compound Relation
(ComR). All extracted word relations are saved in a word set called word-
relation library (WRLib). Then, WRLib is used to extend the related words in
the search query. If some words in the query also occur in WRLib, the related
words are recommended, which are annotated by the relation level (SynR-1,
SynR-SamR-2, etc.), which consists of the type of word relations and the grade
of the relation between the recommended words and the query words. All
extended related words are sorted based on the grade of relation level and
their frequency used in the source code. After ranking all the related words,
they further demonstrate them using the “AND” or “OR” relation for developers
to understand and select. Inspired by code search engines where the developers
often use the “advanced search” to optimize the query results, that is, query
words are combined with the “AND” and “OR” relations, INQRES builds “AND” and
“OR” relations in an interactive way for the developer to select suitable
words for query expansion. SynR and SamR indicate similar relations between
words and thus the words in these two sets are defined as the “OR” relation.
The meanings of ComR, InR, and ImR are complementary, and thus the words in
these two sets are defined as the “AND” relation. In INQRES, all related words
are shown in an interface. Users are empowered to evaluate the relevance of
these words to the original query. Those deemed relevant are recognized as
valid and subsequently incorporated into the original query. INQRES can
iteratively use the expanded query to identify other effective related words
in a similar way, until the search results are satisfied.

Code tokenization is a key preprocessing step in code search techniques, which
aims to convert query or code snippet into lexicons. Karnalim (Karnalim, 2018)
find that most code search techniques rely on programming-language-dependent
features to extract source code lexicons. However, these techniques would
require manual updates to accommodate new programming languages, a process
that can consume a significant amount of time. To handle this issue, Karnalim
proposes a language-agnostic code retrieval approach. It does not rely on
programming-language-dependent features. Instead, it relies on the Keyword &
Identifier lexical pattern which are typically similar across various
programming languages. The recognized lexicons are classified by lexicon
categorization based on Keyword & Identifier lexical pattern. This lexical
pattern is selected as the main concern, because its rules are similar in most
programming languages. This pattern is also adapted to query expansion.
Specifically, the keyphrases found on the most descriptive paragraph are
regarded as the query expansion candidates. They are selected from top-K
retrieved documents and limited by lexical pattern. A lexicon is only viewed
as a candidate if its category is similar to the category of the query term,
either a keyword-like or identifier-like lexicon. After that, the candidates
are sorted by the importance score which is weighted by term frequency and
one-to-many association. Finally, the query expansion candidates are used to
improve the code search performance, which expands the query based on terms
found in top-K retrieved source codes.

NCS (Sachdev et al., 2018) is a useful code search tool that can correctly
search repositories of existing source code for code snippets. However, Liu et
al. (Liu et al., 2019) find that the performance of NCS regresses with shorter
queries. To address this issue, they explore an additional way of using neural
networks in code search. They develop NQE, a neural model that takes in a set
of keywords and predicts a set of keywords to expand the query to NCS. NQE
with NCS can perform better than using NCS alone. Specifically, NQE is an
encoder-decoder model, given a query as input, which outputs the most likely
sets of expanded keywords. NQE learns to predict keywords that co-occur with
the query keywords in the underlying corpus, which helps productively expand
the query. Besides, beam search is also utilized to obtain the top-k most
likely sequences of method names. This enhances the performance of NQE in
finding the most relevant keywords for expanding the query.

Huang et al. (Huang et al., 2019) find a potential issue where expanded
queries may inadvertently include irrelevant terms. This phenomenon, known as
the “overexpansion problem”, can lead to confusion within the search engine
and subsequently result in worse outcomes. To avoid the overexpansion problem,
they propose a novel query expansion algorithm based on the semantics of
change sequences, named QESC. Change sequences are generated from the commits
of each method. They contain the changed terms (the new or the deleted code
terms) as well as dependent terms (the unchanged code terms). As we mentioned
earlier, DBN is trained on the change sequences. Then, QESC uses the DBN to
generate changed terms which are composed of operation, label, and role. If
the operation of the term is new, it means the term is relevant to the
original query, promoting QESC to expand the query with its label. According
to the obtained changed terms, QESC guarantees the expanded terms are relevant
to the original query, and second-pass retrieval with an expanded query will
perform better. The same approach has been applied to the query expansion
technique with code changes (QECC) (Huang et al., 2018) to improve the ability
to infer the expansion words. Similar to QESC, QECC also extracts (changes,
contexts) pairs from the abstract syntax trees (ASTs) of changed methods,
which are used to detect changes and extract contexts. However, the difference
between the two lies in the output of the inference model, the association-
based inference model trained by QECC can directly infer the suggested words
to expand the query. Precisely, upon receiving a query, QECC retrieves initial
results from the code corpus. Subsequently, the model extracts the contexts of
these initial results and deduces potential expansion words by assessing the
basis of initial results. Ultimately, the model constructs an expanded query
by incorporating these expansion words into the original query. This expanded
query is then utilized to execute a final search within the code corpus.

Questions and Answers (Q&A) from programming forums that contain abundant
exchanging knowledge about programming issues are crucial resources for code
retrieval and annotation. However, Hu et al. (Hu et al., 2020b) find that
mining software repositories in such open and unrestricted forums is
challenging, since the posts can be arbitrary and noisy. To overcome this
challenge, they propose Code-Description Mining Framework (CodeMF), an
unsupervised framework to eliminate noisy posts and extract high-quality
software repositories from programming forums. Specifically, CodeMF is the
combination of two proposed frameworks kernel principal component analysis
(KPCA) and wavelet time-frequency transform feature fusion (WTFF) which are
applied in extracting high-quality software repositories. KPCA is the
principal component analysis tool used to reduce the dimension of features
collected from the software repositories, and then further extract high-
quality mappings between query-code pairs. Regarding the novel framework WTFF,
it transforms the multiple dimension features into a time-frequency domain
through wavelet transformation to reduce the computational complexity. This
helps to extract the principal components of the software repository features
more easily. Finally, CodeMF leverages the QECK (Nie et al., 2016) to retrieve
the code snippets. As we introduced above, QECK uses the Q&A context-text
pairs to expand the NL queries. CodeMF enhances the Q&A Pairs Search Engine
which is a crucial component of QECK. Thus, it offers high-quality expanded
keywords, leading to improved code search performance.

Cai et al. (Cai et al., 2021) find the retrieved source code from the existing
code search techniques is not compatible with local programming language since
the evolution and production of multiple versions of libraries. To solve this
issue, they propose DCSE, a deep code search model based on evolving
information. Specifically, DCSE first deeply excavates evolved code tokens and
evolution descriptions in the code evolution process. It then treats evolved
code tokens and evolution descriptions as one feature of source code and code
descriptions, respectively. Therefore, DCSE can retrieve the source code that
is compatible with the local programming language. DCSE embeds source code and
its code descriptions into a high-dimensional shared vector space. It
retrieves the initial result using the given query from the repositories. If
the initial search result is incompatible with the local programming language,
users could add the error report of IDE to query for a second-time search.
This is due to the error report being semantically related to the evolution
description while evolution description is one feature of code description, so
the distance between the expanded query vector and the compatible source code
vector will be closer. Finally, DCSE can leverage the expanded query to
retrieve the compatible source code.

Query reformulation is a widely utilized technology that can be regarded as
similar to query expansion for enriching user requirements and enhancing the
outcomes of code search. However, Mao et al. (Mao et al., 2023) find that
training a query reformulation model requires a large parallel corpus of query
pairs (i.e., the original query and a reformulated query) that are
confidential and not publicly available. This restricts the practicality of
query reformulation in software development processes. Therefore, they propose
SSQR, a self-supervised query reformulation method that does not rely on any
parallel query corpus. Specifically, SSQR treats query reformulation as a
masked language modeling task conducted on an extensive unannotated corpus of
queries. SSQR extends T5 (Raffel et al., 2020) (a sequence-to-sequence model-
based on Transformer) with a new pre-training objective named corrupted query
completion (CQC), which randomly masks words within a complete query and
trains T5 to predict the masked content. Subsequently, for a given query to be
reformulated, SSQR identifies potential locations for expansion and leverages
the pre-trained T5 model to generate the appropriate content to fill these
gaps. In this way, SSQR enhances the performance of code search from the
unsupervised query reformulation.

####  4.1.3. Query Transformation

Considering the gap in syntax and structure between the query in natural
language and the code snippet in programming language, there are naturally
some obstacles if directly matched between them. To address this issue, some
researchers believe that finding an intermediate pattern to bridge this gap
holds promise as a viable solution. They successively propose some query
transformation techniques, which can convert natural language queries into
other forms or augment with those forms, such as Q&A posts and other
customized forms (Sirres et al., 2018; Wang et al., 2022). In short, query
transformation turns the direct matching problem between query and code into
an indirect one. From the third line of Figure 6, it is observed that the
research enthusiasm for both query transformation and query reduction is
comparable but notably lower than that observed for query expansion. The
subsequent sections will delve into a detailed discussion of how these works
conduct the process of query transformation.

Sirres et al. (Sirres et al., 2018) find a significant issue where source code
terms such as method names and variable types are often different from
conceptual words mentioned in a query. This is called a mismatch problem which
occurs from the poorly documented or non-explicit names of source code. To
reduce this mismatch problem, they present COCABU, a novel approach that
leverages common developer questions and the associated expert answers to
transform the augmented queries from the original user queries according to
the relevant Q&A sites. Specifically, in the first step of COCABU, the search
proxy takes an original query as input and returns a set of relevant posts
collected from developer Q&A sites as an output. The obtained Q&A posts are
used to find out how natural language concepts can be translated into program
elements, that is, to collect potential translation rules. These translation
rules can alleviate the vocabulary mismatch problem between user queries and
source code. To transform the original query into the augmented query, the
code query generator module extracts structural code entities from code
snippets in Q&A sites. Besides, the code query generator only considers the
accepted answers in Q&A sites. Thereafter, based on the Lucene search engine,
COCABU preserves the terms from search results and combines them with the
types of structural code entities collected from Q&A sites (e.g.,
unqualified/partially qualified method invocations or classes) to form the
augmented query. Finally, the code search engine takes an augmented query
produced by the code query generator and provides a list of search results to
the developer.

Ling et al. (Ling et al., 2021) find most of code search techniques ignore the
deep structured features when processing both queries and code snippets. To
address this problem, they propose an end-to-end deep graph matching and
searching (DGMS) model based on graph neural networks for the task of semantic
code retrieval. Considering the rich, important semantic structure information
within the queries and code snippets, DGMS builds the graph-structured data to
represent that structure information. Specifically, for the natural language
query text, DGMS builds the text graph based on the constituency parse tree
(Eisenstein, 2019) and word ordering features. These features provide both
constituent and ordering information of sentences to establish the graph-
structured data. In a nutshell, DGMS performs query transformation by
converting the query text into a text graph. For code snippets, DGMS also
generates corresponding code graphs. After transforming both queries and code
snippets into unified graph-structured data, DGMS uses the proposed graph
matching and searching model to retrieve the best matching code snippet.

Wang et al. (Wang et al., 2022) find that the user query is relatively shorter
than the code description (also known as code comments) and limited in
context. It implies a knowledge gap between the query and the code
description. The code description contains more semantic keywords like code
snippets rather than the query. However, existing research ignores this gap,
resulting in low code search accuracy for code search models trained based on
code descriptions rather than real queries. To reduce the impact of the
knowledge gap, Wang et al. propose a query-enriched code search model called
QueCos. QueCos performs query transformation by generating the corresponding
code descriptions from the given query. Those descriptions are utilized for
improving the code search performance. Specifically, QueCos collects the code-
description pairs dataset from the GitHub. The designed crawler saves the code
snippets referred in the Stack Overflow posts and the corresponding code
descriptions. Then, a query semantic enriching model is designed to generate
the corresponding descriptions for queries based on the collected dataset,
during which reinforcement learning is adopted to enable the code snippets
retrieved by the generated descriptions to be ranked higher. The generated
descriptions are treated as semantically enriched queries and not necessarily
to be exactly close to the ground-truth descriptions. Finally, both the
semantically enriched queries and original queries are employed for the
ultimate code search.

Existing code search techniques have primarily relied on intricate matching
and attention-based mechanisms. However, Tang et al. (Tang et al., 2023) find
that those techniques often lead to computational and memory inefficiencies,
posing a significant challenge to their real-world applicability. To tackle
this challenge, they propose a novel technique, the Hyperbolic Code QA
Matching (HyCoQA). HyCoQA leverages the unique properties of Hyperbolic space
to express connections between code snippets and their corresponding queries.
Specifically, HyCoQA transforms the code search task into a Q&A pair matching
paradigm. It constructs a dataset with triple matches characterized as
’$\langle$negative code, description, positive code$\rangle$’. In this case,
the primary objective is to maximize the margin between the scores of the
correct Q&A pair and the negative Q&A pair, ensuring that the retrieve system
can robustly differentiate between accurate and inaccurate solutions based on
the given description. Thus, these triple matches are subsequently processed
via a static BERT embedding layer, yielding initial embeddings. A novel
mathematical concept, hyperbolic geometry is used by HyCoQA. Unlike
traditional Euclidean spaces, hyperbolic spaces excel at depicting
hierarchical structures, which often underlie the relationship between code
and its corresponding natural language description. Therefore, HyCoQA utilizes
a hyperbolic embedder to transform the initial embeddings into hyperbolic
space, calculating distances between the codes and descriptions. The process
concludes by implementing a scoring layer based on these distances and
leveraging hinge loss for model training.

for tree= grow=east, reversed=true, anchor=base west, parent anchor=east,child
anchor=west,font=, rectangle, draw=black, rounded corners, base=left,
align=left, minimum width=4em, edge+=darkgray, line width=1pt, s sep=3pt,
inner xsep=2pt, inner ysep=3pt, line width=1pt, ver/.style=rotate=90, child
anchor=north, parent anchor=south, anchor=center, , where level=1text
width=7em, font=, where level=2text width=4.5em, font=, where level=3text
width=4.5em, font=, where level=4text width=4.5em, font=, where level=5text
width=4.5em, font=, where level=6text width=4.5em, font=, where level=7text
width=4.5em, font=, where level=8text width=4.5em, font=, where level=9text
width=4.5em, font=, [Query
Feature
Representation, text width=7em [IR-based
Representation
(§4.2.1) [ (Lv et al., 2015) [(Nie et al., 2016; Niu et al., 2016) [ (Yang and
Huang, 2017) [(Lu et al., 2018; Sirres et al., 2018)
(Zhang et al., 2018) [ (Rahman et al., 2019) [ (Hu et al., 2020b) [[ (Wu and
Yan, 2022) []]] ] ] ] ] ] ] ] [DL-based
Representation
(§4.2.2) [ [ [ [(Sachdev et al., 2018; Gu et al., 2018) [ (Wan et al., 2019)
[(Ling et al., 2020; Shuai et al., 2020)
(Sun et al., 2020; de Rezende Martins and Gerosa, 2020)
(Gu et al., 2020; Ren et al., 2020)
(Zhu et al., 2020) [(Cai et al., 2021; Meng, 2021)
(Gu et al., 2021; Xu et al., 2021)
(Fang et al., 2021) [(Kong et al., 2022a; Cheng and Kuang, 2022)
(Wang et al., 2022; Kong et al., 2022b)
(Deng et al., 2022; Yu et al., 2022)
(Zhao and Liu, 2022) [(Cai et al., 2023; Zeng et al., 2023)
(Tang et al., 2023; Mao et al., 2023)] ] ] ] ] ] ] ] ] ] ]

(year)201520162017201820192020202120222023

Figure 7. Evolution of feature representation techniques in query end

###  4.2. Query Feature Representation

####  4.2.1. IR-based Feature Representation

Information retrieval (IR) is the technique of finding relevant information
from large amounts of information according to the needs of users (Singhal,
2001). In the field of code retrieval (i.e., code search), the IR technique
has naturally been introduced by researchers. There are many mature IR-based
methods to handle natural language queries. Those methods represent queries as
vectors or plain texts, and researchers utilize these representations to
optimize the query end, thereby enhancing the final results of code search.
Generally speaking, traditional IR methods represent queries as some form of
index (such as keyword terms and vectors), which can reflect the semantic
information contained within queries. Thereby, the code search model can
utilize these representations to optimize the query end and improve the final
performance. The first line of Figure 7 showcases the code search works that
adopt IR-based techniques to represent query features. It is observed that
most early code search efforts employ IR techniques to represent queries. This
demonstrates that IR technology is simple and effective in feature
representation, and we will describe these works in detail later.

Plain text is a common feature representation method in the field of
information retrieval, which refers to preprocessed text from the query. The
plain text representation can be used to optimize the query end. As mentioned
in Section 4.1, CodeHow (Lv et al., 2015) expands the query with the APIs and
performs code retrieval. To find the related APIs, CodeHow needs to represent
the descriptions of AIPs and the given query before calculating their
similarity. Therefore, Codehow utilizes plain text as the representation of
features used in traditional IR methods, while preprocessing of the text is
required before generating the plain text representation. In the preprocessing
stage, CodeHow finds some words that appear very often and do not have a
definite meaning, called stop words (e.g., on, the, are, etc.). To reduce the
impact of those meaningless words in the queries and descriptions, they remove
those stop words after adopting the text normalization. Thereafter, they also
perform stemming. The goal of those preprocessing steps is to represent the
text into keyword terms that can be used to compute the similarity by VSM. In
the code retrieve stage, the method of representing the queries expanded with
APIs is also similar to the preprocessing stage. The expanded queries,
represented in the form of plain text, are used for BM to match with code
snippets.

Nie et al. (Nie et al., 2016) also employ plain text to represent query
features and query expansion word features. As mentioned in Section 4.1.2,
they propose a query expansion tool called QECK. In QECK, there are two times
of feature representation. The first one involves representing the original
query for first-pass retrieval, while the second one involves representing the
expanded candidate words to select the most suitable ones. These two instances
of feature representation both utilize plain text. In this way, QECK directly
processes the text into the search without converting it into vectors.
Specifically, the original text is split by Camel-case and separators (e.g.,
‘_’). Then, it filters these words by removing the stop words. Besides, the
remaining words are handled by stemming. After the preprocessing, the obtained
plain text can be used to retrieve the code snippets. Lu et al. (Lu et al.,
2018) and Hu et al. (Hu et al., 2020b) also utilize a similar feature
representation rule to extract the plain text representation for user queries.
They regard the processed plain text representation as a keyword set that can
retrieve the code more easily.

In order to extract the plain text representation of queries more accurately,
Rahman et al. (Rahman et al., 2019) propose a Part-of-Speech (POS) tagging on
the query before normal preprocessing. POS can extract meaningful words such
as nouns and verbs from the query. Once a query is submitted, they first
perform POS and then apply standard natural language preprocessing (i.e., stop
word removal, splitting, and stemming) on the query to extract the stemmed
words. This more precise query feature representation can further enhance the
final performance of code retrieval.

Using traditional IR methods to represent queries, whether expanded or
reduced, as vectors is also a common approach. For example, the use of VSM as
a method for representing queries as vectors has been applied in many
techniques. For example, Sirres et al. (Sirres et al., 2018) and Niu et al.
(Niu et al., 2016) use the VSM to determine the relevancy of the user query.
It represents the query as a vector where the term is computed by the TF-IDF
weighting.

Another widely used IR method is the bag-of-words model (BOW) (Mikolov et al.,
2013a). BOW represents a text document as a collection of vocabulary,
disregarding the sequence and context of words, only focusing on the frequency
of word occurrences within the document. For example, Wu et al. (Wu and Yan,
2022) employ the BOW to represent each term in a normalized query and generate
the term vector to represent the semantic feature. In BOW, text is regarded as
an unordered collection of vocabulary, disregarding its grammar and context.
Feature information of query is obtained using the TF-IDF, which calculates
the term frequency (TF) and inverse document frequency (IDF). Thereafter, the
query vectors are calculated by summing up the vectors of each term. Yang et
al. (Yang and Huang, 2017) also adopt BOW to represent the query feature.
After the normal preprocessing, they convert the query and the intents into a
BOW model. The output from the BOW model is regarded as the representation of
the query. To map queries with identifiers that are used to expand the
queries, Zhang et al. (Zhang et al., 2018) utilize the continues bag-of-words
model (CBOW) to convert the original query into a vector representation. The
continuous bag-of-words model is an improved version of the traditional BOW
model. Unlike the BOW model, which focuses solely on the frequency of words
within a document, the CBOW model pays attention to the vocabulary information
in the context. Therefore, the semantic features represented by the query
vectors generated through CBOW are more accurate.

####  4.2.2. DL-based Feature Representation

DL-based feature representation applies deep neural networks to encode the
given feature data to produce semantic-preserving numerical vector
representations (also known as embeddings). It has also been widely used to
optimize query feature representation in code search. When code search
techniques apply DL techniques/models to transform queries into embeddings,
models will extract fine-grained semantic and structural information in
queries. The second line of Figure 7 presents the code search techniques that
apply DL techniques to represent queries. These techniques transfer different
neural networks/models from the natural language processing (NLP) or computer
vision (CV) fields to encode queries. We will introduce these techniques in
subsequent paragraphs.

Ling et al. (Ling et al., 2020) and Kong et al. (Kong et al., 2022a) utilize
FastText (Bojanowski et al., 2017) to build word vector representations.
FastText is an open-source model released by Facebook. Researchers can
directly download pre-trained FastText models from open-source repositories to
represent the queries they need to process. Besides, FastText employs CBOW and
Skip-gram models to learn word vector representations. It focuses on the
context of words, generating dense, low-dimensional vectors for each word.
Therefore, word representations learned by FastText are more reliable and
effective.

Sachdev et al. (Sachdev et al., 2018) are among the first researchers to adopt
DL techniques to represent query features. They propose a neural code search
tool named NCS. In NCS, query feature representation is decomposed into two
steps: 1) building word embeddings and 2) building document embeddings. NCS
treats a query as a document. In step 1), NCS uses a variant of the Word2vec
model, called FastText (Bojanowski et al., 2017) to build word vector
representations (i.e., embeddings). It employs the continuous skip-gram model
with a window size of 5, i.e., all pairs of words within a distance of 5 are
considered nearby words. In step 2), NCS expresses the intent of the query in
the same high–dimensional vector space as the word embeddings, by aggregating
the representations of all the words extracted from the query. The authors
found that building document embeddings by simply averaging word embeddings
does not work well for their purposes. Therefore, they further tried three
variants of the combination method: i. Average over all the words; ii. Average
over the unique words in each document; iii. Weighted average of all unique
words in a document according to the following equations.

(1) $\displaystyle v_{d}=u\left(\sum_{w\in
d}{u(v_{w})\cdot\text{tfidf}(w,d,C)}\right)$ (2)
$\displaystyle\text{tfidf}(w,d,C)=\frac{1+\log\text{tf}(w,d)}{\log|C|/\text{df}(w,C)}$

where $d$ is a multiset of words representing a document; $C$ is the corpus
containing all documents; $u$ is a normalizing function where
$u(v)=\frac{v}{|v|}$; tfidf, short for term frequency–inverse document
frequency, is a function that assigns a weight for a given word in a given
document (Mitra and Craswell, 2017). A word has a higher weight if it appears
frequently in the document but is also penalized if it appears in too many
documents in the corpus. Their experiments show that the weighted average
method works significantly better than the others.

Recurrent Neural Network (RNN) is also widely used to encode queries. For
example, Gu et al. (Gu et al., 2018) utilize an RNN to represent query
features. It is known that RNN has a recurrent structure within the network
where hidden layers are recurrently used for computation. Therefore, unlike
traditional feed-forward neural networks, RNN can encode sequential queries
using its internal memory. The hidden state represents the feature of the
query as the final output of RNN. The query representation through RNN can be
computed as:

(3) $\displaystyle h_{i}=\tanh\left(W\left[h_{i-1},w_{i}\right]\right)$

where each hidden state $h_{i}$ is generated from the previous hidden state
$h_{i-1}$ and $w_{i}$ is the one-hot representation of each word in query;
while $W$ is the matrix of trainable parameters in the RNN, while
$\tanh(\cdot)$ is a non-linearity activation function of the RNN.

Wan et al. (Wan et al., 2019) propose a comprehensive multi-model
representation method for source code called MMAN. To match with the source
code representation, MMAN exploits the standard LSTM to learn the
representation of the given query. In MMAN, building a query feature
representation consists of two steps: 1) embedding the query into a vector and
2) generating the hidden state from LSTM. In step 1), MMAN builds a word
embedding layer that uses the one-hot embedding function to compute the given
query into embedding. In step 2), MMAN applies an LSTM to represent the query.
As an improved version of RNN, LSTM can better capture long-term dependencies.
Each LSTM unit contains an input gate, a memory cell, and an output gate. The
unit receives the embedding from step 1) and generates the hidden state given
to the next unit. The last hidden state can be used as the query feature
representation denoted $h_{i}^{query}$. It can be computed as:

(4) $\displaystyle
h_{i}^{query}=\mathbf{LSTM}\left(h_{i-1}^{query},w(q_{i})\right)$

where $w(\cdot)$ is the word embedding layer to embed each word into a vector;
$q$ is the input of the word embedding layer which donates the query; the last
hidden state $h_{d}^{query}$ is the final output of the LSTM. Due to its
outstanding performance and efficiency, LSTM is also widely employed by other
code search techniques for query feature representation. For instance, CSSAM
(Cai et al., 2023) and DCSE (Cai et al., 2021) all follow almost the same
process as MMAN.

Unlike NCS in building document embeddings step, CARLCS-CNN (Shuai et al.,
2020), CoNCRA (de Rezende Martins and Gerosa, 2020), and CSRS (Cheng and
Kuang, 2022) introduce the use of the convolutional neural network (CNN) for
query feature representation extraction after obtaining the word embedding. As
for the query, it is usually short, but it contains informative keywords that
reflect the intention of the user. Therefore, CNN is suitable for extracting
query feature representation from word embedding. The feature representation
$D$ of a query can be computed as:

(5) $\displaystyle v_{i}=f\left(W_{i}\ast E_{i:i+h-1}+b\right)$ (6)
$\displaystyle\mathrm{D}_{\mathrm{h}}=\left[v_{1},v_{2},\ldots,v_{d}\right]$
(7)
$\displaystyle\mathrm{D}=\mathrm{D}_{\mathrm{1}}\oplus\ldots\oplus\mathrm{D}_{\mathrm{n}}$

where $E$ is the embedding of the query; while $W$ is the convolution kernels
for convolution operation; and $f$ is a non-linear function such as the
hyperbolic tangent. After generating the feature scores $v$, the embedding
matrix $D_{h}$ can also be obtained. Thereafter, the final feature
representation $D$ is accomplished by merging all the embedding matrices.

Differing slightly from the aforementioned methods, EAGCS (Zhao and Liu, 2022)
and CRaDLe (Gu et al., 2020) incorporate a maxpooling layer after LSTM. They
take the hidden states generated by each LSTM unit and feed them into the
maxpooling layer to obtain the final query representation. The purpose of
adding a maxpooling layer is to perform further feature extraction, obtaining
the significant features. Therefore, the final representation of the query,
denoted $\bm{v}^{query}$, can be formulated as:

(8)
$\displaystyle\bm{v}^{query}=\mathbf{maxpooling}\left(\left[h_{1},\dots,h_{i}\right]\right)$

where $\mathbf{maxpooling}(\cdot)$ refers to maxpooling layer; the $h$ is the
hidden state from each LSTM unit and calculated by Equation (4).

As a variant of the traditional LSTM, bi-directional LSTM (Bi-LSTM) is also
employed by Ren et al. (Ren et al., 2020), Wang et al. (Wang et al., 2022),
and Meng (Meng, 2021) to generate query feature representations. Unlike the
traditional LSTM, Bi-LSTM simultaneously considers the past and future
information at each time step in the sequence to better capture contextual
relationships. Bi-LSTM consists of two LSTM layers, one processing the input
sequence from left to right in terms of time steps (i.e., forward LSTM), and
the other processing the input sequence from right to left (i.e., backward
LSTM). The outputs of these two LSTM layers are concatenated to form a
representation that incorporates bidirectional contextual information. The
final feature representation generated by Bi-LSTM for the query can be
formalized as:

(9)
$\displaystyle\bm{v}^{query}=h_{q}=\left[\overrightarrow{h}_{q},\overleftarrow{h}_{q}\right]$

where $\overrightarrow{h}_{q}$ and $\overleftarrow{h}_{q}$ are the forward and
backward hidden states produced by the final layer of LSTM.

Considering the self-attention mechanism is suitable for capturing the
structural and semantic features within query sequences, Fang et al. (Fang et
al., 2021), Zhu et al. (Zhu et al., 2020), Gu et al. (Gu et al., 2021), Kong
et al. (Kong et al., 2022b), and Sun et al. (Sun et al., 2020) utilize the
self-attention mechanism to extract features and generate representations. The
framework they designed for constructing the query feature representation by
the self-attention mechanism can be divided into two steps: 1) generating word
embedding of query and 2) obtaining feature representation from the self-
attention mechanism. In step 1), the framework applies a word embedding tool
to build the embedding layer. Sun et al. and Kong et al. select the one-hot
code to represent the word embedding of the query. The rest of the techniques
exploit the well-known word embedding tool, called word2vec
999https://github.com/danielfrg/word2vec/. Word2vec uses the CBOW to embed
words. Compared with one-hot representation, distributed representation
produced by word2vec can build semantic relations between different words. In
step 2), the word embedding generated by the embedding layer is further
embedded by the self-attention mechanism. The self-attention mechanism can
effectively extract features from the query and generate the feature
representations. The following equation simply summarizes the above process of
generating a query feature representation through the embedding layer and
attention mechanism.

(10)
$\displaystyle\bm{v}^{query}=\mathbf{Att}\left(E\left(s^{query}\right)\right)$

where $s^{query}$ is the given query treated as a list of words; while
$E(\cdot)$ represents a word embedding layer; $\bm{v}^{query}$ is the final
output of attention mechanism.

To fully understand the relationships between query and code, Deng et al.
(Deng et al., 2022) propose a code search model named FcarCS. The approach of
representing query features in FcarCS is similar to the aforementioned self-
attention framework, but it replaces the self-attention mechanism with the co-
attention mechanism as the feature-extracted tool. FcarCS constructs a new
fine-grained co-attention mechanism to learn interdependent representations
for each code and query, respectively. The workflow of this co-attention
mechanism can be divided into computing semantic association, extracting
semantic information, and calculating semantic vector parts. According to
those steps, the co-attention mechanism establishes dynamic attention
relationships between queries and code snippets. Therefore, it can explore
more fine-grained semantic correlations between each code snippet and query,
and enrich the query feature representations.

There also exists an architecture that utilizes both attention mechanisms and
a co-attention mechanism to generate query feature representations. To bridge
the semantic gap between code snippet and query effectively and efficiently,
Xu et al. (Xu et al., 2021) propose a two-stage attention-based model for code
search, called TabCS. The first stage leverages attention mechanisms to
extract semantics from queries considering their textual features. The second
stage leverages a co-attention mechanism to capture the semantic correlation
between queries and code snippets. Therefore, the co-attention mechanism
contributes to better query representation.

Zeng et al. (Zeng et al., 2023) also propose an embedding module similar to
MD-JEnn, but they replace Bi-LSTM with LSTM. They utilize the structure of an
LSTM layer along with an attention layer to accurately extract feature
representations containing keyword information from user queries. Besides, Hu
et al. (Hu et al., 2020a) design a similar structure to obtain feature
representation. However, instead of using one-hot representation or pre-
trained word2vec embeddings to generate the word embedding, they use a
structure embeddings matrix to incorporate word-level structure information
and get the structure embeddings of queries.

Yu et al. (Yu et al., 2022) propose a novel deep neural network named Method-
Description-Joint Embedding Neural Network (MD-JEnn), which uses a joint
embedding technique to model the semantic relation between code snippets and
descriptions. The description embedding module (DE-Module) is a component of
MD-JEnn that embeds natural language descriptions (queries) into vectors. The
word embedding model and Bi-LSTM are used in MD-JEnn to embed queries into
query vectors first. Since some words in a description are important, it is
necessary to assign higher weights to these important words. Thus, MD-JEnn
introduces an attention mechanism to aggregate the query vectors of the
description into a feature-represented vector by calculating a scalar weight
for each vector of the description word. The individual vectors are aggregated
to a feature-represented vector $\bm{v}$ via attention:

(11) $\displaystyle\small
a_{i}=\frac{\exp{({\widetilde{h_{i}}}^{\intercal}\cdot\alpha)}}{\sum_{j=1}^{n}\exp{({\widetilde{h_{j}}}^{\intercal}\cdot\alpha)}}$
(12)
$\displaystyle\small\bm{v}=\sum_{i=1}^{n}\alpha_{i}\cdot\widetilde{h}_{i}$

where $h$ is the the hidden states of the previous Bi-LSTM layer, which
represents the query vector and $\alpha_{i}$ is a learnable matrix initialized
in random, $\alpha_{i}$ also represents the attention weight of each
$\widetilde{h}_{i}$.

Tang et al. (Tang et al., 2023) leverage the unique properties of Hyperbolic
space to express the feature of user queries. Unlike traditional Euclidean
spaces, hyperbolic spaces excel at depicting hierarchical structures.
Therefore, they first exploit the BERT (Devlin et al., 2019) (a pre-trained
NLP model) as the embedding layer to embed the original query. Thereafter,
they use an advanced hyperbolic embedder to encode the query embedding into
hyperbolic spaces as the final representation. This representation can express
the feature of the query deeply and easily to match with the code snippets.

SSQR (Mao et al., 2023) utilizes masked language modeling task (MLM) to
conduct the extensive unannotated corpus of queries to reformulate queries.
SSQR takes the T5 (Raffel et al., 2020) (a pre-trained NLP model) as the
backbone model for the MLM task since it has a sequence-to-sequence
architecture. The queries are converted into the embeddings by the MLM and
masked out a span of 15% consecutive words from a randomly selected position.
The purpose of the MLM task is to encourage the model to learn contextual
relationships and better understand the semantics of language by inferring
missing words in a given context. Following MLM training, the T5 model can
accurately capture the semantic meanings of each word in the queries and
generate high-quality query embeddings. Therefore, these query embeddings are
used for the final code retrieval.

Summary for RQ1: Existing code search techniques mainly optimize the query end
from two aspects: query feature mining and query feature representation. For
query feature mining methods, query reduction, query expansion, and query
transformation continue to receive attention. Among them, query expansion
overall is the most, followed by query transformation, and query reduction.
Compared with query reduction, research on query transformation has become
more popular in recent years and continues to be a hot trend. For query
feature representation methods, most early code search techniques apply
information retrieval techniques (e.g., plain text, bag of words, and TF-IDF)
to represent query features. In recent years, with the emergence of deep
learning technology, most researchers have turned to using neural networks
(e.g., FastText, CNN, RNN, LSTM, Bi-LSTM, BERT, and T5) and attention
mechanisms (e.g., self-attention and co-attention mechanisms) to represent
query features, and this phenomenon will obviously continue.

##  5\. Answering RQ2: What are the code-end optimization methods in code
search studies?

Understanding code semantics also plays an important role in code search. Only
by correctly understanding what a code snippet is doing can we better match it
to the query. As a human-readable text written in a specific programming
language, code snippet contains semantic information not only in the text but
also in its structure, such as AST. To learn about the semantics of the code
snippet more comprehensively, it is often necessary to leverage such semantic
information and convert it into other representations that can be used to
match queries at a later stage. As a result, many code-end optimization
techniques have been proposed to capture and understand the semantics of the
code snippet to improve the effectiveness and efficiency of code search.

As illustrated in Figure 2, similar to the query end, the optimization
techniques devised for the code end can likewise be divided into two primary
parts: code feature mining and code feature representation. For code feature
mining, existing works mainly focus on mining textual and structural features
of the code snippet. The textual features include method names, API sequences,
and tokens. The structural features, also referred to as intermediate
representations, encompass abstract syntax tree (AST), data flow graph (DFG),
control flow graph (CFG), program dependence graph (PDG), and variable-based
flow graph (VFG). Details of the above textual and structural features are
discussed in Section 5.1. For code feature representation, similar to the
query end, the techniques used to represent code features can also be divided
into two major classes, i.e., IR-based feature representation and DL-based
feature representation. Details of these code feature representation methods
are discussed in Section 5.2. In the following subsections, we will discuss
these code features and their representation ways in detail, extract their
commonalities, find their differences, and summarize the development trends.

for tree= grow=east, reversed=true, anchor=base west, parent anchor=east,
child anchor=west, base=center, font=, rectangle, draw=black, rounded corners,
align=left,minimum width=4em, edge+=darkgray, line width=1pt, s sep=3pt, inner
xsep=2pt, inner ysep=3pt, line width=1pt, ver/.style=rotate=90, child
anchor=north, parent anchor=south, anchor=center, , where level=1text
width=10em, font=,, where level=2text width=4.5em, font=,, where level=3text
width=4.5em, font=,, where level=4text width=4.5em, font=,, where level=5text
width=4.5em, font=,, where level=6text width=4.5em, font=,, where level=7text
width=4.5em, font=,, where level=8text width=4.5em, font=,, where level=9text
width=4.5em, font=,, [Code
Feature
Mining [Code textual
feature mining (§5.1.1) [method
name [ [(Gu et al., 2018; Sachdev et al., 2018) [ (Wan et al., 2019) [(Shuai
et al., 2020; Ren et al., 2020) [(Xu et al., 2021; Meng, 2021)
(Cai et al., 2021; Liu et al., 2021a)
(Fang et al., 2021) [(Yu et al., 2022; Cheng and Kuang, 2022)
(Deng et al., 2022; Wang et al., 2022)
(Kong et al., 2022b, a)[] ]]]]]]] [API
sequence [ [ (Gu et al., 2018) [ (Rahman et al., 2019) [ (Shuai et al., 2020)
[(Xu et al., 2021; Du et al., 2021)
(Fang et al., 2021; Cai et al., 2021) [(Deng et al., 2022; Kong et al., 2022a)
(Cheng and Kuang, 2022; Kong et al., 2022b)[] ]]]]]]] [tokens [ (Lv et al.,
2015) [(Gu et al., 2018; Chen and Zhou, 2018)
(Zhang et al., 2018; Sirres et al., 2018) [(Wan et al., 2019; Yao et al.,
2019) [(Shuai et al., 2020; Ling et al., 2020)
(Haldar et al., 2020; Ren et al., 2020)
(de Rezende Martins and Gerosa, 2020; Wang et al., 2020a)
(Zhu et al., 2020; Feng et al., 2020) [(Gu et al., 2021; Meng, 2021)
(Liu et al., 2021a; Cai et al., 2021)
(Xu et al., 2021; Fang et al., 2021) [(Yu et al., 2022; Wu and Yan, 2022)
(Cheng and Kuang, 2022; Deng et al., 2022)
(Kong et al., 2022b; Gu et al., 2022)
(Wang et al., 2022; Niu et al., 2022) [(Cai et al., 2023; Tang et al., 2023)]
]]]]]]] ] [Code structural
feature mining (§5.1.2) [AST [ [ [ (Wan et al., 2019) [(Haldar et al., 2020;
Gu et al., 2020)
(Hu et al., 2020a; Sun et al., 2020) [(Xu et al., 2021; Gu et al., 2021)
(Meng, 2021) [ (Niu et al., 2022)[] ]]]]]]] [DFG [ [ [ (Wan et al., 2019) [
(Gu et al., 2020) [ (Guo et al., 2021) [ [ (Cai et al., 2023)] ]]]]]]] [CFG [
[ [ (Wan et al., 2019) [ (Gu et al., 2020)[[[] ]]]]]]] [PDG [ [ [ [ (Gu et
al., 2020) [ [ (Zhao and Liu, 2022)[] ]]]]]]] [others [ [ [ [ [ (Ling et al.,
2021) [ (Yu et al., 2022) [(Zeng et al., 2023; Liu et al., 2023)] ]]]]]]] ] ]

(year)2015201820192020202120222023

Figure 8. Evolution of feature mining techniques in code end

###  5.1. Code Feature Mining

####  5.1.1. Code Textual Feature Mining

The code snippets we discuss in this survey are at the method (function)
level. A method-level code snippet usually consists of a method name,
parameters (optional) and a method body. In code search, commonly used code
textual features include method name, API sequence, and tokens, all of which
contain semantic information (Kong et al., 2022b).

Method name. The method name often outlines the functionality (semantics) of a
code snippet (at the method level) (Shuai et al., 2020). Therefore, it plays
an important role in understanding the code snippet. As shown in the first
line of Figure 8, many works (Gu et al., 2018; Sachdev et al., 2018; Wan et
al., 2019; Shuai et al., 2020; Ren et al., 2020; Xu et al., 2021; Liu et al.,
2021a; Meng, 2021; Cai et al., 2021; Fang et al., 2021; Yu et al., 2022; Kong
et al., 2022a, b; Deng et al., 2022; Cheng and Kuang, 2022; Wang et al., 2022)
mine and utilize this feature. The extraction of method names is relatively
simple and intuitive, and some works describe this process in detail. For
example, CodeMatcher (Liu et al., 2021a) develops a tool called JAnalyzer
101010https://github.com/liuchaoss/janalyzer, which transforms a method into
an AST with the Javaparser 111111https://github.com/javaparser/javaparser
library and then extracts method name by traversing the AST. CodeHunter (Kong
et al., 2022a) first uses JDT (i.e., Eclipse Java Development Tools) to
construct the AST of the source code, and then invokes the
$\mathtt{getName()}$ method in the MethodDeclaration class to obtain the
method name. Considering that a method name typically consists of multiple
words, it is a common practice to split the camel–case (camelCase) or
snake–case (snake_case) concatenated method names into multiple separate
tokens for later embedding.

API sequence. API (Application Programming Interface) is of great significance
in code search. It refers to a predefined and encapsulated function. Rather
than implementing a method from scratch, programmers often invocate APIs in
their code to facilitate their development activities (Gu et al., 2016).
What’s more, the naming of an API usually briefly describes its functionality
(semantics), so the API sequence extracted from a code snippet can help code
search models understand how this code snippet is implemented. As illustrated
in the second line of Figure 8, many works (Gu et al., 2018; Rahman et al.,
2019; Shuai et al., 2020; Xu et al., 2021; Cai et al., 2021; Fang et al.,
2021; Du et al., 2021; Kong et al., 2022a, b; Deng et al., 2022; Cheng and
Kuang, 2022) make use of this feature. Next, we will introduce two ways to
extract API sequences. Rahman et al. (Rahman et al., 2019) extract API
sequences from Stack Overflow posts with island parsing techniques. They first
isolate code snippets from the HTML source of each answer from Stack Overflow
using ¡$code$¿ tags, and then use a regular expression for Java class to
extract the API class tokens having camel case notation. DeepCS (Gu et al.,
2018), CodeHunter (Kong et al., 2022a), and DCSE (Cai et al., 2021) follow the
method described in DeepAPI (Gu et al., 2016) to extract an API sequence from
each Java method. They all employ the Eclipse JDT compiler to parse and
traverse the AST. After obtaining the AST, the API sequence is generated by
the following rules (Gu et al., 2018; Kong et al., 2022b):

  * •

For a constructor invocation $\mathtt{new~{}C()}$, they produce
$\mathtt{C.new}$.

  * •

For a method call $\mathtt{o.m()}$ where $\mathtt{o}$ is an instance of class
$\mathtt{C}$, they create $\mathtt{C.m}$.

  * •

For a method call passed as a parameter, they append the method before the
calling method.

  * •

For a statement sequence $s_{1};s_{2};\dots;s_{N}$, they extract the API
sequence $a_{i}$ from each statement $s_{i}$ and concatenate them to form the
API sequence $a_{1}\text{-}a_{2}\text{-}\dots\text{-}a_{N}$.

  * •

For conditional statements such as $if(s_{1})\\{s_{2};\\}else\\{s_{3};\\}$,
they produce a sequence from all possible branches,
i.e.,$a_{1}\text{-}a_{2}\text{-}a_{3}$, where $a_{i}$ is the API sequence
extracted from the statement $s_{i}$.

  * •

For loop statements such as $while(s_{1})\\{s_{2};\\}$, they generate a
sequence $a_{1}\text{-}a_{2}$, where $a_{1}$ and $a_{2}$ are API sequences
extracted from statement $s_{1}$ and $s_{2}$, respectively.

Tokens. Tokens are bags of words that are parsed from the method body of a
code snippet. They include useful information such as constant names, variable
names, and comments written by the developer. Usually, data preprocessing for
tokens removes duplicate words, stop words, and keywords in the programming
language, which improves the quality of tokens. As a result, as presented in
the third line of Figure 8, almost all code search techniques (Lv et al.,
2015; Gu et al., 2018; Chen and Zhou, 2018; Sirres et al., 2018; Zhang et al.,
2018; Wan et al., 2019; Yao et al., 2019; Shuai et al., 2020; Ren et al.,
2020; Wang et al., 2020a; de Rezende Martins and Gerosa, 2020; Haldar et al.,
2020; Ling et al., 2020; Feng et al., 2020; Zhu et al., 2020; Cai et al.,
2021; Xu et al., 2021; Gu et al., 2021; Fang et al., 2021; Meng, 2021; Liu et
al., 2021a; Yu et al., 2022; Wu and Yan, 2022; Cai et al., 2023; Kong et al.,
2022b; Deng et al., 2022; Cheng and Kuang, 2022; Niu et al., 2022; Wang et
al., 2022; Gu et al., 2022; Tang et al., 2023) take advantage of this feature.
Most of them tokenize code snippets through camel case splitting or snake case
splitting. Zhang et al. (Zhang et al., 2018) focus on query-end optimization
and aim to extend natural-language queries with API class-names, so they keep
them intact.

####  5.1.2. Code Structural Feature Mining

In code search, commonly used code structural features include AST, DFG, CFG,
PDG, and other structural features.

AST. Abstract syntax tree (AST) abstractly represents the syntactic structure
of a code snippet in the form of a tree (Wan et al., 2019). Each node in the
tree denotes a structure in the code snippet, such as loop structure,
conditional judgment structure, method call, and variable declaration (Xu et
al., 2021). There is no doubt that AST is very helpful in understanding the
code as these structures denote the logic of the code. Consequently, AST is
the most commonly used structural feature in code search techniques (Wan et
al., 2019; Gu et al., 2020; Sun et al., 2020; Hu et al., 2020a; Haldar et al.,
2020; Xu et al., 2021; Gu et al., 2021; Meng, 2021; Niu et al., 2022). They
use various different AST parsing tools to generate AST. For instance, MMAN
(Wan et al., 2019) parses C code into AST via an open source tool named Clang
121212http://clang.llvm.org/. PSCS (Sun et al., 2020) extracts AST paths using
PathMiner (Kovalenko et al., 2019), an open source java library for mining
path-based representations of code. At-CodeSM (Meng, 2021) employs javalang to
generate an AST from the code snippet. SPT-Code (Niu et al., 2022) first uses
an AST parser 131313https://tree-sitter.github.io/tree-sitter/ to get the AST.
Then, it utilizes a simplified version of structure-based traversal (SBT) (Hu
et al., 2018) called XML-like SBT (X-SBT) to traverse the AST and parse it
into a sequence. By employing SBT, the resulting sequence can be reduced by
more than half in length.

DFG. Data flow graph (DFG) is a type of intermediate representation. DFG
refers to the data flow of a program, which describes how the data in a piece
of code flows and how it is processed. Many code search works (Wan et al.,
2019; Gu et al., 2020; Guo et al., 2021; Cai et al., 2023) use DFG as a
feature to capture the data dependencies between code elements. For instance,
Hu et al. (Cai et al., 2023) establish a code semantic representation graph
(CSRG) based on AST and DFG, which is a graph structure more compact than AST.
GraphCodeBERT (Guo et al., 2021) is a pre-trained model for programming
language, which utilizes data flow in the pre-training stage. It first parses
a code $C$ into an AST, whose terminals (leaves) are used to identify the
variable sequence, denoted as $V=\\{v_{1},v_{2},\dots,v_{k}\\}$. Then, it
takes each variable as a node of the graph, and a direct edge
$\epsilon=\langle v_{i},v_{j}\rangle$ from $v_{i}$ to $v_{j}$ means that the
value of $j$-th variable comes from $i$-th variable. Taking $x=expr$ as an
example, $expr$ is an expression (e.g., $(a+b)*c$), edges from all variables
in $expr$ to $x$ are added into the graph. The set of directed edges is
denoted as $E=\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{l}\\}$ and the
graph $\mathcal{G}(C)=(V,E)$ is data flow used to represent dependency
relation between variables of the code.

CFG. Control flow graph (CFG) is another type of intermediate representation
of the code feature. CFG means the computation and control flow of a program,
which has the function of representing all possible execution paths for the
program. CFG is also a code feature commonly used by code search techniques
(Wan et al., 2019; Gu et al., 2020) to capture control dependencies between
code elements. For example, Wan et al. (Wan et al., 2019) directly make use of
the CFG of a code snippet in their code search model. They first parse C
functions into CFGs via an open-source tool named SVF (Sui and Xue, 2016)
141414https://github.com/SVF-tools/SVF. Then, for nodes with the same
statement, they keep the nodes that appear first in the output of SVF, remove
their child nodes, and connect the children of their child nodes to them. For
nodes without statements, they delete them and link their child nodes to their
parent nodes.

PDG. Program dependence graph (PDG) can represent the data dependencies and
control dependencies of each operation in a program (Ferrante et al., 1987).
It is built on AST, but not as deep as AST in structure, and reserves only the
execution paths that will affect the execution results (Gu et al., 2020). Gu
et al. (Gu et al., 2020) utilize PDG to extract code structures. They propose
CRaDLe, a code retrieval model based on semantic dependency learning, to learn
the matching relationship between the code and description pairs which helps
to retrieve the related code snippets. Zhao et al. (Zhao and Liu, 2022)
establish a statement-level advanced program dependence graph (APDG), which
introduces the statement execution information and control logic missed in
PDG. Based on APDG, they propose EAGCS, a novel code search approach that
largely enhances the expression of structural and semantic information in
source code. APDG helps EAGCS to learn a deeper understanding of code vectors
which improves the performance of retrieving code snippets from given query.

Others. Some code search techniques define new structural features based on
those above. For instance, a variable-based flow graph (VFG) is proposed by
Zeng et al. in their work DeGraphCS (Zeng et al., 2023). They think that
tokens and structural features cannot accurately express the in-depth
semantics of source code. To overcome this limitation, they propose VFG, which
integrates tokens, data flow, and control flow. VFG is constructed on LLVM IR
instructions. Specifically, to construct VFG, they first extract the
identifiers in each LLVM IR instruction as nodes. Then, they build data
dependencies and control dependencies between nodes according to different
types of instructions. The data dependencies are built based on the address
operation instructions (e.g., “load”) and the computation-related
constructions (e.g., “add”). The control dependencies are constructed based on
the jump instructions (e.g., “br”) and address operation instructions.
Finally, they apply an optimization mechanism to remove the redundant nodes
without changing the semantic information.

DGMS (Ling et al., 2021) and GraphSearchNet (Liu et al., 2023) both construct
a program graph to represent the source code, which helps them precisely learn
unified semantic relation representation of the source code and queries. Given
a code snippet $c$, a program graph is a multi-edged directed graph
$g(V,\bm{A})\in\mathcal{G}$ extracted from $c$. $V$ is a set of nodes built on
the AST and $\bm{A}\in\\{0,1\\}^{k\times m\times m}$ is the adjacency matrix
representing the relationships between the nodes (i.e., the edges), where $k$
and $m$ are the total number of edge types and nodes in $g$, respectively.
Particularly, the leaf nodes of AST correspond to the identifier in the code
snippet, and the non-leaf nodes represent different compilation units such as
“Assign”, “BinOp”, “Expr”. In addition, GraphSearchNet also builds the
syntactic edges (i.e., “NextToken”, “SubToken”) and data-flow edges (i.e.,
“ComputedFrom”, “LastUse”, “LastWrite”) based on AST nodes, which can
represent the code snippet.

Noticing that the API sequence generated by traversing the AST tree ignores
semantics contained in the structure of the code snippet, SQ-DeepCS (Yu et
al., 2022) introduces a novel method called _program slice_ to preserve
structural information. To generate a program slice, first, the AST of a code
snippet is parsed, and then different processing methods are applied to
different statements extracted from the code snippet. Taking the loop
statement as an example, the program slice reserves its judgment conditions
and loop body and adds the $for$ keyword. For instance,
$for(c1;c2;c3)\\{s4;\\}$ is converted to $for(p2)\\{p4;\\}$, where $p2$ and
$p4$ are the program slices of condition $c2$ and statement $s4$.

for tree= grow=east, reversed=true, anchor=base west, parent anchor=east,
child anchor=west, base=left, font=, rectangle, draw=black, rounded corners,
align=left, minimum width=4em, edge+=darkgray, line width=1pt, s sep=3pt,
inner xsep=2pt, inner ysep=3pt, line width=1pt, ver/.style=rotate=90, child
anchor=north, parent anchor=south, anchor=center, , where level=1text
width=7em, font=,, where level=2text width=4.5em, font=,, where level=3text
width=4.5em, font=,, where level=4text width=4.5em, font=,, where level=5text
width=4.5em, font=,, where level=6text width=4.5em, font=,, where level=7text
width=4.5em, font=,, where level=8text width=4.5em, font=,, where level=9text
width=4.5em, font=,, [Code
Feature
Represention, text width=7em [IR-based
Representation
(§5.2.1) [ (Linstead et al., 2009) [ (McMillan et al., 2011) [ (Lv et al.,
2015) [ (Niu et al., 2016) [[ (Jiang et al., 2019) [(Chen et al., 2020; Fu et
al., 2020) [ (Abid et al., 2021)[[]]]]]]]]] ] ] [DL-based
Representation
(§5.2.2) [[[[[(Gu et al., 2018; Zhang et al., 2018) [ (Wan et al., 2019)
[(Shuai et al., 2020; Haldar et al., 2020)
(Gu et al., 2020; Wang et al., 2020a) [(Xu et al., 2021; Gu et al., 2021)
(Ling et al., 2021; Guo et al., 2021)
(Cai et al., 2021) [ (Yu et al., 2022) [(Tang et al., 2023; Liu et al.,
2023)]]]]]]]]]] ] ]

(year)2009201120152016201820192020202120222023

Figure 9. Evolution of feature representation techniques in code end

###  5.2. Code Feature Representation

####  5.2.1. IR-based Feature Representation

As mentioned earlier, code Search is a successful application of IR where the
information retrieved is code snippets. The core idea of IR-based code search
methods is to treat source code as text, so the code and the query can be
matched by their textual similarity. The first line of Figure 9 presents the
code search works that adopt IR-based techniques to represent code features.
We will describe these studies in detail later.

While an approach based entirely on IR was effective in the early days, as
time goes by, researchers have come to realize that treating code as just
plain text does not provide a comprehensive understanding of its semantics. As
a result, later techniques combine it with some additional information, such
as the relational representations of code (Linstead et al., 2009), API (Lv et
al., 2015; Abid et al., 2021), comment (Fu et al., 2020) and keywords (Chen et
al., 2020), etc. Another research (McMillan et al., 2011) aims at making it
easier for developers to make use of the code snippet retrieved by showing
other possibly related functions and the call graph between them. In this
section, we will introduce several typical IR-based code feature
representation techniques.

In most applications of mining and searching software corpora, the code’s
structural aspects, as well as the relevant metadata surrounding it, are
always ignored. To utilize this information, Linstead (Linstead et al., 2009)
et al. propose Sourcer, which combines standard text IR techniques with
source-specific heuristics and a relational representation of code. It employs
a relational database consisting of two tables to store the data: (1) program
entities: uniquely identifiable elements from the source code; and (2) their
relations: any dependency between two entities. In addition, they also store
compact representations of attributes for fast retrieval of search results,
including keywords from FQNs and comments, and fingerprints used to support
structural searches of source code. All entity keywords and metadata are
indexed using Lucene to support fast search. In this way, Sourcerer provides a
comprehensive, multi-modal platform for searching and finding reusable
software components.

Niu et al. (Niu et al., 2016) propose a code search approach that utilizes a
machine learning technique to automatically train a ranking schema. They
represent each code snippet as a 12-dimension vector, each dimension denotes
the value of a feature extracted from the code snippet. The 12 features are
classified into four categories: similarity, popularity, code metrics, and
context. The similarity is the textual similarity between a query and
candidate code snippets, computed by the Vector Space Model (VSM) (Salton et
al., 1975). The popularity category has two features: frequency and
probability. Frequency is the number of times that the frequent method call
sequence of a candidate code snippet occurs in the corpus, while probability
is the likelihood of following the method call sequence in a candidate code
example. The code metrics category contains eight features that only reflect
characteristics of a code snippet regardless of the query, including the line
length, the average number of identifiers per line, and so on. The context
similarity refers to the similarity between the context of the query and the
candidate code snippets.

Similar to Niu et al. (Niu et al., 2016), Jiang et al. (Jiang et al., 2019)
also leverages textual and structural features like the textual similarity
between a query and a candidate code snippet and line length of a code snippet
to represent the code. Besides, they also consider the topic similarity
between a query and a code snippet since a code snippet can be considered as a
textual document describing one or more technical topics. They first generate
a term-by-document matrix $M$, given a collection of code snippets and
queries. Then, they employ Latent Dirichlet Allocation (LDA) (Blei et al.,
2003) to identify the latent variables (topics) hidden in the data and
generate as output a topic-by-document matrix. A generic entry $\theta_{ij}$
of this matrix denotes the probability of the $j^{th}$ document to belong to
the $i^{th}$ topic. Finally, the topic similarity between a query and a code
snippet can be calculated based on this matrix.

####  5.2.2. DL-based Feature Representation

DL-based feature representation on the code-end optimizes the capture and
representation of code features (semantics) by introducing advanced deep
learning techniques, thereby improving the performance of code search. In this
technique, both queries and code snippets are transformed to feature vector
representations (also called embeddings). Embedding learns to represent
entities (e.g., words, sentences, and graphs) as vectors with the aim of
making vector representations of similar entities close to each other (Mikolov
et al., 2013a; Mikolov et al., 2013b). These embeddings are randomly
initialized and then fixed via an end-to-end supervised training paradigm. The
purpose of embedding training in code search is to bridge the lexical gap
between code snippets in programming languages and queries in natural
language, so as to better understand the semantics of the code snippets. In
the task of code search, both code and query are embedded into a unified
vector space through Joint Embedding, which is a technique to jointly embed
heterogeneous data. As a result, similar concepts with different modalities
are close to each other in this space and the code relevant to a query can be
measured by the distance between their vector representations, such as their
cosine similarity (Gu et al., 2018).

In 2018, Gu et al. (Gu et al., 2018) first introduced deep learning to the
field of code search. They propose a novel deep neural network called CODEnn
to learn a unified vector representation of both code snippets and natural
language queries. Based on CODEnn, they develope a prototype named DeepCS to
support code retrieval. After DeepCS, many DL-based feature representation
techniques have sprung up. In this section, we will first discuss how they
leverage advanced deep learning techniques to represent a single feature of a
code snippet, and how they integrate these features to build high-performance
code search models.

To begin with, we will introduce the representation methods for the textual
features of a code snippet as mentioned in Section 5.1.1.

For the method name, DeepCS (Gu et al., 2018) and SQ-DeepCS (Yu et al., 2022)
both use a Recurrent Neural Network (RNN) to encode the sequence of the tokens
obtained by splitting the method name, as RNN can capture the semantics of
sequence information well. It is computed using the same formula (3) mentioned
in Section 4.2.2. DCSE (Cai et al., 2021) employs Bi-LSTM to learn the
semantic information since the method name has word order. Empirically finding
that the average length of each method name sequence is only 2 or 3 in its
training data, CARLCS-CNN (Shuai et al., 2020) applies a Convolutional Neural
Networks (CNN) instead of RNN, which is supposed to be good at extracting
robust and abstract features. Therefore, in CARLCS-CNN, the representation of
the method name is calculated as:

(13)
$\displaystyle\bm{m}_{1:n}=\bm{m}_{1}\oplus\bm{m}_{2}\oplus\dots\oplus\bm{m}_{n}$
(14) $\displaystyle\bm{c}_{i}=f\left(W_{M}*\bm{m}_{i:i+h-1}+\bm{b}\right)$
(15) $\displaystyle M_{h}=[\bm{c}_{1},\bm{c}_{2},\dots,\bm{c}_{n-h+1}]$

where $\bm{m}_{i}\in\mathbb{R}^{k}$ is the $k$-dimensional word vector;
$\oplus$ is the concatenation operator; $W_{M}\in\mathbb{R}^{k\times h}$ is a
filter involved in the convolution operation, which is applied to a window of
$h$ words to produce a feature; $\bm{b}\in\mathbb{R}$ is a bias term; $*$ is
the convolution operator and $f$ is a non-linear function such as the
hyperbolic tangent; $M_{h}$ is a feature map produced after applying the
filter to each possible window of words in the method name. What’s more,
CARLCS-CNN uses three types of filters with varying window sizes $h$ from 2 to
4, with the number of each type of filter set to $d$. Then, it completes the
convolution operation through these filters to extract three distinctive
feature maps, i.e.,
$M_{h_{1}},M_{h_{2}},M_{h_{3}}\in\mathbb{R}^{d\times(n-h+1)}$, respectively,
and finally concatenates them into a feature matrix $M$:

(16) $\displaystyle M=M_{h_{1}}\oplus M_{h_{2}}\oplus M_{h_{3}}$

TabCS (Xu et al., 2021) utilizes attention mechanism-based search models to
improve the efficiency of training and testing. Let
$\bm{m}_{i}\in\mathbb{R}^{k}$ be a $k$-dimensional word initial vector
corresponding to the $i$-th word in a method name. Given a sequence of length
n {$\bm{m}_{1},\dots,\bm{m}_{n}$}, the attention weight for each $\bm{m}_{i}$
is computed as follows:

(17)
$\displaystyle\alpha_{m_{i}}=\frac{exp(\bm{a}_{m_{i}}\cdot\bm{m}_{i}^{T})}{\sum_{i=1}^{n}exp(\bm{a}_{m_{i}}\cdot\bm{m}_{i}^{T})}$

where the attention vector $\bm{a}_{m_{i}}$ is optimized during model
training. The attention weight for each initial vector is computed by applying
the softmax function to the product of the initial vectors and attention
vectors. Then, it multiplies each initial vector with its corresponding
attention weight, and concatenates the resulting weighted vectors:

(18) $\displaystyle
M=\alpha_{m_{1}}\bm{a}_{1}\oplus\alpha_{m_{2}}\bm{a}_{2}\oplus\dots\oplus\alpha_{m_{n}}\bm{a}_{n}$

For the API sequence, similar to the handling of the method name, DeepCS (Gu
et al., 2018) encodes it into a vector representation using an RNN with
maxpooling. In view of the dynamic sequential features of the API sequence,
CARLCS-CNN (Shuai et al., 2020) implements Bi-LSTM to do the embedding, using
the formula (9) mentioned in Section 4.2.2. Then, the API sequence is encoded
by concatenating all the output hidden states to a feature matrix. Finally,
TabCS (Xu et al., 2021) performs an attention mechanism on the randomly
initialized feature matrix of the API sequence, the same as its process to the
method name and tokens.

For the tokens, considering that tokens are the informative keywords of code,
CARLCS-CNN (Shuai et al., 2020) uses CNN to encode them. COSEA (Wang et al.,
2020a) also leverages CNN, since CNN has the natural ability to capture
locality information which can be used for capturing code blocks’ information.
Moreover, COSEA utilizes layer-wise attention to learn the code semantic
representation. After transforming a code snippet into embedding vectors, the
model can get longer and longer code block representation through
convolutional modules. Finally, attentive pooling is performed on these block
representations and the ultimate semantic embedding of the code snippet is
obtained.

DeepCS (Gu et al., 2018) and SQ-DeepCS (Yu et al., 2022) simply encode tokens
via a multilayer perceptron (MLP), i.e., the conventional fully connected
layer, as tokens are unordered in the source code. Let
$\bm{\tau}_{i}\in\mathbb{R}^{d}$ represent the embedded representation of the
token $\tau_{i}$, $\bm{W}^{\Gamma}$ represent the matrix of trainable
parameters in the MLP, the embedding vector $\bm{h}_{i}$ of the $i$-th token
is computed as:

(19) $\displaystyle\bm{h}_{i}=\tanh(\bm{W}^{\Gamma}\bm{\tau}_{i}),\forall
i=1,2,\dots,N_{\Gamma}$

Next, the individual vectors are summarized to a single vector $t$ through
maxpooling:

(20)
$\displaystyle\bm{t}=\text{maxpooling}([\bm{h}_{1},\dots,\bm{h}_{N_{\Gamma}}])$

Zhang et al. (Zhang et al., 2018) use Word2vec
151515https://code.google.com/archive/p/word2vec/ to extract vector
representations of tokens, which is an efficient implementation of the
continuous bag-of-words model (CBOW) (Mikolov et al., 2013a). Considering that
not all tokens contribute equally to the final semantic representation of code
snippet, MMAN (Wan et al., 2019) introduces the attention mechanism on tokens
to extract the ones that are more important to the representation of a
sequence of code tokens after encoding them via LSTM. The specific calculation
process of LSTM and attention mechanism refer to formulas (4) and (17),
respectively. HyCoQA (Tang et al., 2023) transforms tokenized code snippets
into numerical representations through a BERT embedding layer (Devlin et al.,
2019), because the word vectors generated by BERT can be dynamically adapted
to the context provided by neighboring words.

Next, we will introduce the representation methods for the structural features
of a code snippet as mentioned in Section 5.1.2.

For the AST, MT-CAT (Haldar et al., 2020) converts the AST representation of a
code snippet by the deterministic parser to a string using SBT (Hu et al.,
2018), and then applies FastText (Bojanowski et al., 2017) as the word
embedding module to map a string to an embedding. TabCS (Xu et al., 2021)
converts tree nodes into initial vector embeddings by building vocabularies.
Then, since only part of the nodes can reflect the method’s function, TabCS
performs an attention mechanism and concatenates the weighted vectors into a
feature matrix, which extracts the important nodes. The final concatenation is
the feature matrix of the AST. The computation process can be referred to
formulas (17) and (18), where the word sequence $\\{m_{1},\dots,m_{n}\\}$ is
replaced by a node sequence $\\{\bm{ast}_{1},\dots,\bm{ast}_{n}\\}$.
Multimodal (Gu et al., 2021) transforms the AST into a novel tree structure
named Simplified Semantic Tree (SST) to make the tree structure semantically
better for code search, and then serializes SST to a linear token sequence by
sampling tree-paths (Alon et al., 2018; Kim et al., 2021) or traversing tree-
structures (Hu et al., 2018; Chen et al., 2018). Finally, multimodal adopts a
SelfAtt model to encode the tree sequence. The SelfAtt model is a transformer-
based model that leverages a self-attention mechanism and BERT’s positional
embedding to learn from contextual information (Vaswani et al., 2017; Devlin
et al., 2019). MMAN (Wan et al., 2019) utilizes Tree-LSTM whose unit contains
multiple forget gates and adopts the hidden state of the root node as the AST
modality representation. Considering a node $N$ with the value $x_{i}$ in its
one-hot encoding representation, and it has a left child $N_{L}$ and a right
child $N_{R}$. The Tree-LSTM recursively computes the embedding for $N$ from
the bottom up. Assume that the left child and the right child maintain the
LSTM state $(\mathbf{h}_{L},\mathbf{c}_{L})$ and
$(\mathbf{h}_{R},\mathbf{c}_{R})$, respectively, then the LSTM state $(h,c)$
of $N$ is computed as:

(21)
$\displaystyle\left.\left.(\mathbf{h}_{i}^{ast},\mathbf{c}_{i}^{ast})=\text{LSTM}\left(\left(\begin{bmatrix}\mathbf{h}_{iL}^{ast};\mathbf{h}_{iR}^{ast}\end{bmatrix}\right.\right.,\begin{bmatrix}\mathbf{c}_{iL}^{ast};\mathbf{c}_{iR}^{ast}\end{bmatrix}\right),w(x_{i})\right)$

where $i=1,\dots,|x|$ and $[\cdot;\cdot]$ means the concatenation of two
vectors.

For the CFG, as it is a directed graph, MMAN (Wan et al., 2019) applies a
gated graph neural network (GGNN) to represent it, which is a neural network
architecture developed for graphs. Define a graph as
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, where $\mathcal{V}$ is a set of
vertices $(v,\ell_{v})$ and $\mathcal{E}$ is a set of edges
$(v_{i},v_{j},\ell_{e})$. $\ell_{v}$ and $\ell_{e}$ are labels of vertex and
edge, respectively. In the code search scenario, each vertex is the node of
CFG, and each edge denotes the control flow of code. GGNN learns the graph
representation through the following procedures: First, the hidden state for
each vertex $v\in\mathcal{V}$ is initialized as
$\mathbf{h}_{v,0}^{cfg}=w(\ell_{v})$, where $w$ is the one-hot embedding
function. Then, for each round $t$, each vertex receives the vector
$\mathbf{m}_{v,t+1}$, which is the “message” aggregated from its neighbours.
It can be formulated as follows:

(22) $\displaystyle
m_{v,t+1}=\sum_{v^{\prime}\in\mathcal{N}(v)}\mathbf{W}_{\ell_{e}}\mathbf{h}_{v^{\prime},t}$

where $\mathcal{N}(v)$ are the neighbours of vertex $v$. Message from each
neighbour is mapped into a shared space via $\mathbf{W}_{\ell_{e}}$ in round
$t$. GGNN updates each vertex $v$’s hidden state using the gated recurrent
unit (GRU) (Chung et al., 2014), which can be formulated as follows:

(23)
$\displaystyle\mathbf{h}_{v,t+1}^{cfg}=\mathrm{GRU}(\mathbf{h}_{v,t}^{cfg},\mathbf{m}_{v,t+1})$

Finally, after $T$ rounds of iteration, the embedding representation of the
CFG is obtained by aggregating the hidden state of all vertices.

For the DFG, given a source code $C=\\{c_{1},c_{2},\dots,c_{n}\\}$ with its
comment $W=\\{w_{1},w_{2},...,w_{m}\\}$, GraphCodeBERT (Guo et al., 2021)
first obtains the data flow graph. $\mathcal{G}(C)=(V,E)$ as discussed in
Section 5.1.2. Next, it concatenates the comment, source code, and the set of
variables $V$ in the DFG as the sequence input, and converts the sequence into
an input vector by summing the corresponding token and position embeddings.
Then, the model applies N transformer layers over the input vector to produce
contextual representations. Specifically, it defines a graph-guided masked
attention function to incorporate the graph structure into a transformer. At
last, after being pre-trained on three tasks, namely masked language modeling,
edge prediction, and node alignment, GraphCodeBERT can be applied to some
downstream tasks, such as code search.

For the PDG, CRaDLe (Gu et al., 2020) first constructs a dependency matrix
$\Upsilon\in\\{0,1\\}^{(l)\times(l)}$ according to the extracted PDG, where
$l$ is the number of statements in the code snippet. The element $v_{ij}=1$ if
the $i$-th statement has a data/control dependency on the $j$-th statement;
otherwise $v_{ij}=0$. Then, it uses a one layer MLP to encode the matrix
$\Upsilon$ according to the formula (19). Note that $\bm{\tau}_{i}$ in the
formula (19) is replaced by $v_{i}$, and $\bm{h}_{i}$ is the embedding of the
dependency information for each statement here. After that, CRaDLe
concatenates the dependency embedding with statement-level token embedding to
get the representation of the statement. Next, it adopts Bi-LSTM to encode the
sequence of the statement embeddings and uses the same encoder to get the
description embeddings. Finally, after calculating the cosine distance, the
model will rank the code snippets and return the higher ranked ones to the
programmer.

For the program graph, DGMS (Ling et al., 2021) adopts one variant of
GNNs—Relational Graph Convolutional Networks (RGCNs) to learn its node
embedding. Particularly, given the program graph of a code snippet
$G_{e}=(\mathcal{V}_{e},\mathcal{E}_{e},\mathcal{R}_{e})$ with nodes
$e_{i}\in\mathcal{V}_{e}$ and edges $(e_{i},r,e_{j})\in\mathcal{E}_{e}$, where
$r\in\mathcal{R}_{e}$ represents edge type, RGCN calculates the updated
embedding vector $\bm{e}_{i}$ of each node $e_{i}\in\mathcal{V}_{e}$ as
follows:

(24)
$\displaystyle\bm{e}_{i}^{(l+1)}=\mathrm{ReLU}\Bigg{(}W_{\Theta}^{(l)}\bm{e}_{i}^{(l)}+\sum_{r\in\mathcal{R}_{e}}\sum_{j\in\mathcal{N}_{i}^{r}}\frac{1}{|\mathcal{N}_{i}^{r}|}W_{r}^{(l)}\bm{e}_{j}^{(l)}\Bigg{)}$

where $\bm{e}_{i}^{(l+1)}$ is the updated embedding vector of node $e_{i}$ in
the $(l+1)$th layer of RGCN, $\mathcal{N}_{i}^{e}$ is the set of the neighbors
of node $e_{i}$ under the edge type $r\in\mathcal{R}_{e}$, $W_{\Theta}^{(l)}$
and $W_{r}^{(l)}$ are parameters of the RGCN model to be learned. Thus, the
node embeddings $\bm{X}_{e}=\\{\bm{e}_{j}\\}_{j=1}^{N}\in\mathbb{R}^{(N,d)}$
for the program graph $G_{e}$ is obtained, where $d$ represents the embedding
dimensions of each node.

GraphSearchNet (Liu et al., 2023) introduces a Bidirectional Gated Graph
Neural Network (BiGGNN) to encode the program graph, which learns node