2.1. API Member Set Search and its Effects

It is common that many API method calls are combined to implement a particular functionality in an application. Figure 1 shows a code segment of a typical Android application program. There are several methods and a named constant that belong to Android APIs, used in the program. Among them, getDefaultSensor, registerListener, unregisterListener, and TYPE_PROXIMITY are cooperating to implement a sensor-related functionality. On the other hand, DataToFileWriter, writeToFile, and closeFiles are used for accessing files. You can see from the figure a couple of facts that are common for Android applications: (1) multiple method calls from separate method definitions are cooperating for implementing a particular functionality, and (2) although groups of API members are used for implementing relatively independent functionalities, call/used sites of them are mixed and scattered all over the source code. These properties that are typical of event-driven programs make it a burden to separate a code segment that implements a single functionality from Android programs, leading the difficulty of building and maintaining Android applications.

Figure 1

Common pattern of Android programs composed of API method calls.

If developers can easily obtain in advance the sets of API members that should be used to implement a specific feature, the user can avoid spending much time to decide which API methods to use and can write code focusing only on how to combine API methods in the set. Searching for the API methods that satisfies several conditions such as cooperability with other API methods may be much more laborious than just arranging elements in a fixed set of API methods. Tools that can recommend suitable sets of API members seem to be of great help for application developers.

2.2. Realizing API Member Set Search

Application Programming Interface member set search systems should be based on the mining of open source repositories because the result should be up-to-date and full of variety. However, a search system based on a naive ranking capability would make the user stray in the sea of similar API member sets on the recommended list that is output as the result of searching.

Figure 2 shows an example of the result of an API member set search obtained by using the CAPIS system [7] (http://capis.ca.info.hiroshima-cu.ac.jp:8090/). CAPIS treats API member sets as a kind of text documents and ranks each one by using the TF-IDF (term frequency-inverse document frequency) measure. This approach would be effective for the ordinary document search where each document is sufficiently large and contains many kinds of words so that each one is rather distinguishable form others. The results in Figure 2 shows numbers of similar API member sets that are related to the given keywords of “text” and “view”. It would be difficult for the user to scan the lengthy list to select the one that should correspond to the functionality the user had desired to implement.

Figure 2

Screenshot of CAPIS, an API member set search tool.

As can be seen from the example in Figure 2, the search results of API method sets in a one-dimensional list format is not suitable for the user to effectively utilize the search results. One reason for this is that the search target is not a single API method to invoke but a set of API methods to combine. That is, a query expressed by a small number of search terms cannot be specific enough to pinpoint a suitable set of API calls in the large database obtained from open source repositories.

In order to alleviate the situation and realize an effective API member set search, we focus on the relevance of each API member in a set to restructure API member sets to construct a kind of search tree. We observe that there are a couple of cases: (1) a few members in an API member sets play important roles and the others are not, and (2) an API member set consists of several loosely related groups of closely related members. To refine and reorganize API member sets, we carry out the frequent pattern mining to extract inclusion relations mediated by newly produced subsets. The inclusion graphs constructed from the inclusion relations among API member sets are directly usable for API member set search; the user (or an algorithm) can trace the edges from a suitably small start point to an appropriate one, checking if the addition of a few API members is reasonable, step-by-step.

2.3. Designing API Member Set Search System

In this paper, we propose an API member set search system. The system consists of two parts; one is for collecting API usage information from open source repositories, extracting inclusion relations among API member sets by using the frequent pattern mining, and constructing inclusion graphs as a database for the API member set search, and the other is a GUI for the search system. We describe each part in Sections 3 and 4, respectively, in detail.

3.1. Various Roles of API Methods

Each API method in a set of API methods that are required to implement a specific functionality might be roughly classified into two groups based on the roles for each set, i.e., those that play a central role and inevitable to implement the functionality and those that are used to just extend and/or adjust the behavior of the functionality. The former API methods are considered to appear in common in API member sets for a specific functionality, while the others are not. The more important a method is for a functionality, the more often it seems to appear in API member sets related to the functionality. From the observation, we can expect that the API member sets that are related to the same functionality can be organized to extract their hierarchical relationships by analyzing inclusion relations. The hierarchical relationships of sets can be represented by using a graph structure.

3.2. Extraction of Hierarchical Relationships by using Frequent Pattern Mining

The frequent pattern mining [12] is considered to be effective in constructing the hierarchical graph structures. The frequent pattern mining is a method to extract frequently appearing subsets from a set of input item sets. We can obtain the hierarchical relations by analyzing the inclusion relations among the sets.

Applying the frequent pattern mining to the sets of API method sets might reveal the fact that, e.g., a particular couple of methods are always used simultaneously. In order to obtain those kinds of facts in the inclusion graphs, we use FP-Close algorithm [13] while carrying out the frequent pattern mining so that such kind of important pairs are not treated separately. For example, API methods registerListener and unregisterListener are a representative pair of the kind. Closed itemsets generated by the FP-Close algorithm should contain both of the two or none of them if the two methods are always used together.

3.3. Usability of Inclusion Graphs among API Method Sets

From the subsets obtained by applying the frequent pattern mining to the original API member sets and analyzing the inclusion relationships among sets, we can obtain, for example, the graph structure depicted in Figure 3 from the five API member sets shown in Figure 2. Rectangles and ovals in Figure 3 represent API member sets and the differences between adjacent sets, respectively. Directed edges between rectangles through ovals are drawn such that when API member set A is a subset of B, there is always a path from A to B. The seven API member sets in Figure 3 are closed itemsets obtained from five sets in Figure 1. Among them, two are newly created API method set. Although what is shown in Figure 3 is a single tree, the result of the application of the frequent pattern mining to API member sets is, in general, a set of graphs.

Figure 3

Inclusion relations among API member sets represented as a graph.

Inclusion graphs are apparently useful for guiding searching for an appropriate API member set. For example, presenting a graph of Figure 3 to the developer would help him/her search for the right API member set by first selecting important API methods and then modifying the set by checking if some API methods should be added or deleted for the functionality to be implemented. Compared with the task of selecting the target set from the API member sets expressed in a one-dimensional form such as a list, it is considered that the burden on the developer is greatly reduced. However, there might be a problem since the graph of Figure 3 could become quite huge. In order to construct an API method set search system that uses the inclusion graphs directly, a specially arranged GUI would be inevitable. The graph representation of the inclusion relations can also be utilized by recommendation systems of API member sets by algorithmizing the procedure of tracing the edges of an inclusion graph.

4.1. Overview of the Tool

We propose an API Member Set Search System with an interactive interface for developers to search API member sets efficiently. By using the system, the user can search for an API member set consisting of API methods that are inevitable to implement the functionality in his/her mind. In order to support the task of selecting one from a large number of API member sets collected from open source repositories, the system extracts the inclusion relationships among API member sets to obtain inclusion graphs such as the one shown in Figure 3. By tracing this graph, the user can search for an appropriate set of API methods as if collecting a set of API methods adding one-by-one in order of appearance frequently. However, the generated graphs could become huge in general. The proposed system offers a way to trace the tree structure easily and effectively by using the mouse.

The GUI of the system is as shown in Figure 4. The left pane of the window is used for listing tag clouds where each tag cloud is linked to a graph of API member sets. We expect that, by using tag cloud representations for describing overviews of functionalities, the user can intuitively select the right graph corresponding to the sets of API methods that are closely related to the functionality the user desire to implement.

Figure 4

Screenshot of the API member set search tool.

When the user selects a tag cloud, the root node and its neighboring parts of the corresponding API member set graph is drawn in the right pane. Only one API member set (in a rectangle) is shown in the right pane at a time. The rectangle node in Figure 4 corresponds to the set Z in Figure 3. Oval nodes in the periphery indicate the difference between the central API member set and the sets connected in a parent–child relationship (we call those oval nodes Diffnodes). The user can intuitively grasp the differences between API member sets by looking at the small number of API methods in Diffnodes. When the user clicks a Diffnode, corresponding API member set is drawn in the center of the right pane. Thus, the user can trace the inclusion graph transferring the focus from one API member set to another. The lower part of Figure 4 illustrates a transfer of the focus from set Z to set Y in Figure 3.

As shown in Figure 4, each rectangle’s frequency information is available. Numbers in and out of the parentheses are the number of source files and the number of API member sets that include the members in each rectangle, respectively. Numbers attached to Diffnodes are the same as the numbers attached to the hidden rectangles that should exist beyond the Diffnodes.

For example, We can see the rectangle shown in the center of the lower part of Figure 4 is labeled as “46(0)”, meaning that there are a total of 46 source files that include calls for both “findViewById” and “setText”, but no API member set consisting of only these two API methods exists, meaning that the child node beyond the Diffnode is a closed itemset generated by the frequent pattern mining.

4.2. System Structure

The structure of the proposed tool is illustrated in Figure 5. As shown in Figure 5, our tool consists of two parts; the Database Constructor and the Browser.

Figure 5

Overall structure of the API member set search system.

In the Database Constructor, three components are combined to construct the database for facilitating the API member set search. First, API member sets are extracted from a set of source files by the API Member Set Extractor. The grouping is carried out by using a dependency analysis; similar techniques have been used elsewhere, e.g., in the SSS system [14]. The obtained sets of API member sets are gathered and undergo the frequent pattern mining [12] by the API Member Set Graph Generator. In the process, obtained closed itemsets are analyzed to construct inclusion graphs of API sets. The frequency information is used to annotate nodes of the graphs.

The major part of the Database Builder’s job is to index multiple graphs by using a list of annotations where each annotation is represented in the form of a tag cloud. Tag cloud generation is described in the next section.

The Browser is a GUI through which the user can interact with the system. The behavior of the GUI is as outlined in Section 4.1.

4.3. Tag Cloud Annotation Generation for Each Inclusion Graph

There might be multiple inclusion graphs constructed by the API Member Set Graph Generator. Some graphs could have multiple root nodes that have no parents. Each of these root nodes likely corresponds to an important API member set for implementing a particular functionality. We treat the root nodes of multiple graphs as starting points of searching.

We will explain the way to generate tag cloud annotations corresponding to all root nodes. First, we extract class names and method names from the names of API methods that make up the root node of each graph and extract words by them. Second, we apply the morphological analysis to the extracted words to normalize each word and weight them by using the TF–IDF method regarding that each set of words constructs a document.

The generated list of tag cloud annotations is shown to the user and used for deciding from which node to start tracing the inclusion graphs.

4.4. Implementation of the Prototype

We have implemented a prototype of the API member set search system. We used Java language to write the prototype. SPMF [15] is used for the frequent pattern mining in API Member Set Graph Generator, and Apache Lucene (https://lucene.apache.org/core/) libraries are used to build Database Builder.

5.1. Datasets Used for the Experiments

We use two kinds of datasets in the experiments:

Google Samples: The set of API methods obtained from Google Samples (https://github.com/googlesamples). It contains 6112 API member sets extracted from 158 Android Java projects, obtained in January 2017.

Github: The set of API methods collected from Android projects on Github. The dataset was collected in July 2019. A selected part of the set is used as a dataset in each experiment. In all cases, the size of the dataset is larger than that of Google Samples.

In both cases, the minimum support threshold is set to 0 while applying the frequent pattern mining. All experiments were performed on a MacBook Pro (CPU: Intel Core i7 3.5 GHz, Memory: 16 GB).

5.2. Usability of the Tool: Search for API Member Sets by Tracing Inclusion Graphs

We conducted several attempts of the API member set search to retrieve information that should be useful for implementing the Android components listed in Table 1. The dataset from Google Samples was used for each search. In fact, all the experimental results were similar. We show the usability of the tool by describing how the tool would be used for searching for an API member set to implement the AlertDialog component.

Suppose that you are to implement the AlertDialog pop-up shown in Figure 6a and search for the set of APIs required for implementing using the tool. An AlertDialog pop-up in Figure 6a consists of a title, a message, and a clickable button. Search for the AlertDialog component would be carried out smoothly and intuitively as follows.

Figure 6

AlertDialog component of the Android API. (a) AlertDialog on the Android screen. (b) AlertDialog implemented by combining API methods.

You might choose a tag cloud with the words {Builder, Alert, Dialog} to start searching. Then the tool would display an API member set that includes a single API method AlertDialog.Builder.Builder, which is at the root of the inclusion graph shown in Figure 7.

Figure 7

Searching for an API member set by tracing an inclusion graph.

In Figure 7, we can see a path from the root to the box at the lower left, on which API method names shown in Diffnodes include words such as “title”, “message”, “button”, and “click”, which indicate that they are related to the components that make up parts shown in Figure 6a. We can easily reach to the lower left box taking frequency information into account; in fact, the number on the lowermost Diffnode in Figure 6a indicates that taking a further step would not gain the appropriateness of the set very much.

Figure 6b shows an example of a code segment that uses all API methods in the obtained set.

5.3. Constructing an Inclusion Graph: the More You Pay, the More You Get

The frequent pattern mining is known to be a computationally expensive method. Table 2 summarizes the effect of putting a restriction on the maximum size of API member sets while processing the data form Google Samples. The numbers in parentheses in Table 2 show the percentages against the leftmost numbers. As shown in Table 2, we can see that the time required to construct the database for API member set search significantly decreases when the maximum size of each API member set is limited. The negative effect of the limitation of maximum API member set size might look small in Table 2. However, the lost information includes that on API methods related to major classes as listed in Table 3.

All the listed classes in Table 3 tend to require to combine many API methods to realize a specific functionality. Table 3 shows the number of API method sets that include indispensable API methods to implement each functionality. A set of functionality, such as Camera, which requires many API methods to implement and which can often be combined with other functionalities, is heavily influenced by the size limitations.

The loss shown in Table 3 might be attributed to the fact that there are too few sample projects that use cameras or music recording facilities in Google Samples. However, it might not be a good idea to limit the size of the set because there is a risk of losing some amount of important information.

5.4. Searching Github: a Larger Source of Information

Although Google Samples contains many informative examples for developing Android applications, the set of examples does not cover all of the Android APIs and some functionalities are barely involved. In this section, we describe what happens when you use a dataset obtained from a wider range of Github.

Figure 8 shows the distribution of the API method sets obtained from Google Samples and Github. All API method sets counted in Figure 8 are related to the Android components listed in Table 1 (498 projects on Github). Figure 8 illustrates that Github offers a richer variety of data. Figure 9a and b shows the same situation of searching API method sets related to the WakeLock component. Comparing Figure 9a and b, you can see that the API method usages demonstrated in Google Samples are quite limited. Figure 10 shows one of the extreme cases where Google Samples can not offer a candidate but Github presents a promising set with modification choices.

Figure 8

Distribution of the sizes of API member sets related to the components in Table 2.

Figure 9

Parts of API member set graphs related to a WakeLock component. (a) Based on Google Samples. (b) Based on Github.

Figure 10

Part of an API member set graph related to the MediaRecorder component based on Github.

As such, larger dataset leads a better performance in general. The proposed tool appears to be able to make the most use of larger dataset.