Extracting a Unified Directory Treeto Compare Similar Software Products
Yusuke Sakaguchi, Takashi Ishio, Tetsuya Kanda, Katsuro Inoue
Graduate School of Information Science and Technology, Osaka University, Japan{s-yusuke, ishio, t-kanda, inoue}@ist.osaka-u.ac.jp

Abstract—Source code is often reused in software development. Although developers can avoid re-implementing featuresin existing products, doing so may result in a large number ofsimilar software products. To understand the commonalities andvariabilities of similar products, comparing their source codeis critical. However, a product may change its own directory
structure, even if the products share the same source code withother products. Hence, comparing source code among products
in a systematic manner is difficult.
In this paper, we propose a technique to extract and visualize
a unified directory tree to compare the source code of similar
products. This tree includes all directories of given products
and merges corresponding directories into a single node. Sincea node in a tree corresponds to multiple directories in products,
developers can easily compare the contents of products. In
our study, we implemented the visualization as a GUI tool. In
addition, we conducted a case study using four Android products
to demonstrate the tool’s ability to assist developers in accessing
the source code of multiple products.

I. I NTRODUCTION
In software development, source code reuse is a common
practice to reduce the cost of development. Developers often
create a new product by copying and modifying an existing one
or importing libraries [1], [2]. Furthermore, they often reuse
the developed product to create yet another new product. Thismethod of code reuse is called a “clone-and-own” approach.
Since the clone-and-own approach is common, the industry
already maintains a large number of derived software products.
Although Software Product Line Engineering is promising
for managing such software products, the construction of asoftware product line from existing products requires thatdevelopers understand the commonalities and variabilities ofthem [3].
Source code comparison is an important step in understanding the features of products [4]. In general, since a
directory of a product (e.g. a Java package) is assumed torepresent a feature, comparing multiple products in units ofdirectories is efficient [5], [6]. Duszynski et al. [7] proposedcomparing corresponding directories among similar products.
They visualized the numbers of the lines of both common
and product-specific source code. However, developers must
know the correspondence of directories before comparison; if
directories have been moved or renamed among the products,
determining correspondences may be difficult. Some existing
techniques [8], [9] can extract corresponding directories be-

978-1-4673-7525-2/15/$31.00 c 2015 IEEE

tween two similar products, but they cannot analyze more than
two products at any one time.
In this paper, we propose a technique to extract andvisualize automatically a unified directory tree representing
corresponding directories among products. A unified directory
tree includes all directories including source code of given
products. Since a directory may be moved or renamed, we
regard directories that include similar files as corresponding.
We merge similar directories into a single node in a unified
tree so that developers can easily compare their contents.
In our study, we implemented a tool that automaticallyextracts a unified directory tree from the given source codeof products. The tool translates directory trees into a single
connected graph and then extracts a spanning tree on thegraph. The resulting tree is visualized using a tree view
widget. Similar to existing file managers, selecting a directorynode in the tree then our tool shows the details of the node.
Since a node represents multiple directories of products, ourtool provides a table of files summarizing the contents ofdirectories. Developers can examine file similarities on thetable, and compare pairs of files using an external source code
differencing tool if necessary.
We conducted a case study with four open source archivesof the Android operating system provided by two companies.
The viewer enables us to compare multiple products in unitsof directories.
The reminder of the paper is organized as follows. Section
II describes the background of our study. Section III illustrates
the manner in which we visualize source code of similar
products in a single unified directory tree. Section IV presents
the case study. We conclude the paper in Section V.
II. BACKGROUND
Clone-and-own reuse is a popular method of enhancing an
existing product. Dubinsky et al. [10] reported that industrial
developers tend to copy source code from existing products.
Hemel et al. [11] analyzed industrial variants of Linux kernels
using a code clone detection technique.
Duszynski et al. [7] proposed a visualization technique todistinguish common source code in products from productspecific code. Since their technique assumes input products
have the same directory structure, developers must manuallyinvestigate directory structures to identify moved or renamed
directories.

165

VISSOFT 2015, Bremen, Germany

Yoshimura et al. [8] extracted corresponding directories
between two products by using code clone detection in order
to merge two similar products. However, this approach has notbeen designed for comparing more than two products. Holten
et al. [9] proposed a visualization that compares a pair of
directory trees. It visualizes the manner in which directories in
two products correspond to one another. Although it provides
a global overview of structural differences, the technique does
not aim to compare multiple products. A file-level rename
tracking has been proposed by Lavoie et al. [12]. The technique identifies the most similar source file pairs between
versions. We use file similarity at a directory level.
Beck et al. [13] proposed an asymmetric visualization tocompare a pair of directory trees. It visualizes a primary
directory tree in a large plot and embeds a secondary directory
tree in the nodes of the primary tree. It enables developers to
identify similarities between two directory trees. Our tool does
not directly visualize similarities. Instead, our visualization
facilitates file comparison among directory trees.
Lin et al. [14] proposed a source code comparison tool thatis specialized for multiple instances of code clones. Although
the tool visualizes commonalities among code clones on a codefragment level, it is not a tool used to investigate directorylevel similarities.
III. V ISUALIZATION
We visualize the source code of similar products in a single
unified directory tree. We use as input a set of directories
R = {r1 , r2 , · · · , r|R| }, where ri is the root of a directory tree
containing the source code of a product. We regard a directory
tree as a directed graph. We obtain a unified directory tree fromgiven directory trees through the following three steps.
1) Create a node for each set of directories that containsimilar source files,
2) Connect nodes with weighted arcs representing subdirectory relationships in products, and
3) Extract a directed spanning tree from the resultant graph.
We implement a viewer for a unified directory tree, which
provides several features to investigate and compare source
files in the directory tree.
A. Directory Tree Extraction
To enable developers to compare similar source files across
software products, we create a node for each set of directories
that include similar files. We introduce a content similarity
metric sim(d1 , d2 ) for two directories d1 and d2 in different
products. The single node represents d1 and d2 if sim(d1 , d2 )is equal to or greater than a predetermined threshold th.
Although sim(d1 , d2 ) ≥ th and sim(d2 , d3 ) ≥ th does
not always imply that sim(d1 , d3 ) ≥ th, we assign thesame node to represent all of them so that developers cananalyze the differences among the directories. We use D(n)to represent a set of directories represented by a node n.
The content similarity sim(d1 , d2 ) between two directories is

p1
p2

p3

src

src

src

a

c
a

b

c

a

b

b

Fig. 1. Example directory trees of products

defined according to the following, using the Jaccard similarity
coefficient:|L(d1 ) ∩ L(d2 )|sim(d1 , d2 ) =|L(d1 ) ∪ L(d2 )|where L(d) is a set of lines extracted from all non-binary
files directly contained in a directory d. Since developers maychange the source code layout and line separator characters,
we remove white space characters from lines.
For example, consider three products p1, p2, and p3, eachconsisting of three components a, b, and c. The components
are stored in different directory trees as shown in Fig. 1. In thiscase, we introduce three nodes na, nb, and nc to represent
the component directories as follows.
D(na)

=

{p1/src/a, p2/src/a, p3/src/a}

D(nb)

=

{p1/src/a/b, p2/src/b, p3/src/b}

D(nc)

=

{p1/src/c, p2/src/c}

The source code of a software product is usually organized
into directories without files. For example, the src directory
in a Java program contains only subdirectories that represent
Java package names. We assign a single node to represent
such directories if their subdirectories are represented by thesame node. In other words, if two directories d1 and d2 arerepresented by a single node n (d1 , d2 ∈ D(n)), their parent
directories dp1 and dp2 are represented by a common parent
node. In the case of the example directory trees, we merge
src directories in the products into a single node, even if
they possess no source files.
To ensure that the resultant graph is a connected graph, we
introduce the root node r that represents all root directories
of products, irrespective of product similarity. The root node
represents the root of a unified directory tree to be extracted.
The created nodes are connected using weighted arcs. Givena pair of nodes n1 and n2 , we compute their weight according
to the following:
w(n1 , n2 ) = |{(d1 , d2 ) : d1 ∈ D(n1 ) ∧ d2 ∈ D(n2 )∧subdir(d1 , d2 )}|where a predicate subdir(d1 , d2 ) means that d1 is a parent
directory of d2 . If w(n1 , n2 ) > 0, an arc connects two nodes
with the weight, and if w(n1 , n2 ) = 0, no arc exists because

166

The most time-consuming aspect of our algorithm is calculating sim, and its complexity is O(|d|2 ) where |d| is thenumber of input directories. In general, |d| is much smaller
than the number of input file |f |. Therefore, our algorithm hasless complexity than when performing file-to-file comparisons.

r: {p1, p2, p3}3
nsrc: {p1/src, p2/src, p3/src}
3na: {p1/src/a, p2/src/a, p3/src/a}

2
2

B. Aligning the tree with a specific productnc: {p1/src/c, p2/src/c}

Our algorithm as previously described evenly unifies directory trees. In other words, a unified directory tree may bedifferent from all input products. If developers have expertisein a specific product, aligning directories of other products toa specific well-known product is reasonable. To support suchdevelopers, we introduce an extended weight for targeting a
specific product. Given a target product P and an arc between
nodes n1 and n2 , we compute the weight according to thefollowing:∞
if ∃d1 ∈ D(n1 ), d2 ∈ D(n2 ) :
d1 ∈ P ∧ d2 ∈ P ∧w(n1 , n2 , P ) =subdir(d1 , d2 )w(n1 , n2 ) otherwise.

1
nb: {p1/src/a/b, p2/src/b, p3/src/b}

Fig. 2. A unified directory graph for the example directory trees

r: {p1, p2, p3}

nsrc: {p1/src, p2/src, p3/src}

na:{p1/src/a,p2/src/a,p3/src/a}nb:{p1/src/a/b,
p2/src/b,
p3/src/b}

nc:{p1/src/c,
p2/src/c}

With this weight function, arcs representing a subdirectory
relationship in the target product is always selected in the
spanning tree extraction process. In addition, arcs connecting
directories unique to other products are selected.

Fig. 3. A unified directory tree for the example directory trees

C. Directory Viewer
no parent-subdirectory relationships exist among nodes n1 andn2 . Because a node representing a directory has arcs to nodes
representing its subdirectories, all nodes are reachable from theroot node r. As a result of this step, the example directory trees
are translated into a directed graph as shown in Fig. 2. Since
directory b is a subdirectory of a in p1 but a subdirectoryof src in p2 and p3, the corresponding node nb has two
incoming arcs that indicate the relationships.
We extract a directed spanning tree from the resultant graph.
The extraction process is a simple greedy loop according to
the following.
1) Initialize a spanning tree V = {r}, E = φ, where V
represents a set of vertices and E represents a set of
selected arcs.
2) Select the arc (t, n) having the maximum weight w(t, n)among t ∈ V, n ∈/ V . If the weights are identical, selectthat which is closest to r.
3) Update V ← V ∪ {n}, E ← E ∪ {(t, n)}4) Repeat Steps 2 and 3 until V includes all nodes. Finally,
E includes arcs of the spanning tree.
Given the graph shown in Fig. 2, the algorithm produces atree as shown in Fig. 3. The tree includes arcs from nsrc tona, nb, and nc and ignores an edge from na to nb. Thus,
the resultant unified tree is the same as the directory tree of
p2. The directory p1/src/a/b is virtually regarded as a
subdirectory of src, because two other products have similar
directories at that location.

We implemented a visualization tool for a unified directorytree. The viewer enables developers to explore a unified
directory tree and examine differences of directories in anode. Fig. 4 is a screenshot of the tool. The tool contains
product selection buttons on the top to align a unified tree
to a particular product. The remaining area consist of threeviews: a tree, a file list, and a file matrix.
1) Tree View: The tree view shows the unified directorytree. Our algorithm unifies the inputs into a single tree. Thus,
this view shows only a single tree and users are free tocompare multiple large trees. A node in the view represents a
node in the tree. The name of each node is based on directory
names in the node. If a node corresponds to several directories,
the tree view uses the most popular name among them.
A node also reveals the number of directories x and numberof variants y included as (y in x). The number of variants
indicates the number of directories that include different filecontents from one another. For example, (2 in 3) means thisnode has three directories but one of them has different content
from the other directories, whereas (1 in 3) means this node
has three directories with the same file content. The numberof variants is based on file contents directly contained in the
directories represented by the node. Thus, the (1 in 3) node
may have a subdirectory with variants. If a node contains
multiple variants, the node is colored in blue.
In addition, if a node contains a “moved” directory, that is,
if a directory in the node has a different name or a different
file path than the tree node, then the node is marked by “*”.

167

Fig. 4. An overview of the Directory Viewer

2) File List View: A file list view shows a table of files contained in a selected node. The first column denotes filenames.
The second and subsequent columns correspond to directories
contained in the node. Each cell shows the hash value of afile in a directory. A gray value indicates that the files of thesame name have the same content. A black value indicatesthat some differences exist among the files.
The list can be sorted by either filename or colors of hashvalues so that developers can focus on files with multiple
variants.
The full paths of the directories shown are listed at thebottom of the table. Clicking a path opens the directory using
a default file manager (e.g., Explorer in Microsoft Windows).
3) File Matrix View: A file matrix view shows the similarityof files having the same file name selected in a file list
view. Rows and columns correspond to directories (i.e., likethe columns of the file list view). A cell (i, j) shows thesim(fi , fj ) between files in the selected directories. The cellis colored using color scale white (sim = 1) to yellow(sim = 0.5) to red (sim = 0). Developers can quickly see
the amount of differences in files among the input products.
After one of the cells is selected, an external diff tool (e.g.,
WinMerge 1 ) is executed in order to compare two files.
IV. C ASE S TUDY
We demonstrate the proposed method using four variants ofAndroid’s source code released in the fourth quarter of 2013,
including three products designed by Fujitsu and one by Sony.
They all employ a Qualcomm MSM8974 CPU, Android 4.2
series OS. The list of inputs is shown in Table I.
Because these products use similar software versions, we
expect that most parts of the source code are similar whereassome product specific parts are different. In addition, we
expect that some directories and files in SO-01F are different
from other Fujitsu products. In this case study, we show how
to explore the code of these products using our tool.
We specified four directories as input for our tool. We
ran the tool on a machine equipped with two Intel Xeon
E5507 processors (2.27 GHz, 4 cores) and 24 GB RAM.
1 http://winmerge.org

Approximately 42 minutes were required to read files, compute
similarity among directories, and extract a unified directory
tree for the products. The tool used a predetermined similarity
threshold th = 0.8.
The resultant unified directory tree comprises 9,037 nodes,
and 245 nodes contain moved or renamed directories. In
addition, 673 nodes contain different contents from otherproducts.
Looking into the /kernel directory (Fig. 5), we observedthat several files have different contents. For example, files
AndroidKernel.mk and Makefile in SO-01F are different from other Fujitsu products. Makefile in Fujitsu products are only slightly customized and similarity to SO-01F is95.01%. By contrast, the similarity of AndroidKernel.mk
is 40.52% as shown in the file matrix view in Fig. 5. We
found that developer-specific options for the kernel build ismainly written in this file. The file MAINTAINERS of F-01F
is different from others. Although they all use the same kernel
version, some files in F-01F lack some non-ASCII characters(e.g., umlaut). It seems that the characters are accidentallyreplaced by a developmental environment.
Because the /vendor directory in Fujitsu products containcompletely different files from /vendor in SO-01F, thedirectories are shown as independent nodes in the unified
tree. Similarly, the content of the /external/chronium
directory in Fujitsu products is distinguished from the SO01F version. For example, a file Android.mk is removed
from the Fujitsu code. By contrast, common subdirectories of/external/chronium are nearly similar among the four
products. Therefore, common subdirectories are merged into
nodes in Fujitsu’s /external/chronium node. Another/external/chronium node for SO-01F retains only subdirectories unique to the version.
The node /external/llvm contains six directories
from Fujitsu products, three from /external/llvm, andthree from /external/llvm/projects/sample. The
sample directories are accidentally merged because the directories share similar files such as configure files.
In the case study, we explored the unified directory structure
as if it is a single product, and we easily focused on the168TABLE I
L IST OF I NPUT P RODUCTS . A LL OF THEM ARE VARIANTS OF A NDROID 4.2.
Product

VendorMobile Network Operator

Release#Dirs#Files#Lines

FJL22
301F
F-01F
SO-01F

FujitsuFujitsuFujitsuSony

au
SoftBank
NTT DOCOMONTT DOCOMO

Nov. 2013
Dec. 2013
Oct. 2013
Oct. 2013

7,683
7,708
7,582
5,840

107,945
108,334
105,397
90,736

26,178,588
25,629,778
25,740,695
22,225,611

Fig. 5. Output for /kernel directory and similarity matrix for AndroidKernel.mk.

directories having differences. Although four Android sourcecode archives included 28,813 total directories, the unified tree
covered the entire structure in 9,037 nodes. Because directories
are represented by independent nodes if they have different
contents, we did not analyze such directories. In addition,
since subdirectories are merged independently of their parent
directories, we focused on the comparison of similar files insuch subdirectories.
V. C ONCLUSION
Source code comparison is crucial to understanding commonalities and variabilities among products. In this study,
we presented a technique to extract a unified directory treethat includes all directories of multiple software products. We
implemented a viewer of the tree and conducted a case study
using four Android products. The tool enables developers to
identify different files easily among products and comparethem.
For a future work, we want to evaluate the quality ofan extracted unified tree. Furthermore, we want to conduct
a controlled experiment on the effectiveness of the tool forsource code comparison tasks.
ACKNOWLEDGMENT
This work is supported by Japan Society for the Promotionof Science, Grant-in-Aid for Scientific Research (S) “Collecting, Analyzing, and Evaluating Software Assets for Effective Reuse”(No.25220003) and Osaka University Programfor Promoting International Joint Research, “Software License
Evolution Analysis.”
R EFERENCES[1] J. Rubin, A. Kirshin, G. Botterweck, and M. Chechik, “Managing forked
product variants,” in Proceedings of the 16th International Software
Product Line Conference, 2012, pp. 156–160.

[2] N. Kawamitsu, T. Ishio, T. Kanda, R. G. Kula, C. De Roover, andK. Inoue, “Identifying source code reuse across repositories using lcsbased source code similarity,” in Proceedings of the 14th International
Working Conference on Source Code Analysis and Manipulation, 2014,
pp. 305–314.
[3] J. Bosch, “Maturity and evolution in software product lines: Approaches,
artefacts and organization,” in Proceedings of the 2nd Conference
Software Product Line Conference, 2002, pp. 257–271.
[4] C. W. Krueger, “Easing the transition to software mass customization,”in Revised Papers from the 4th International Workshop on Software
Product-Family Engineering, 2002, pp. 282–293.
[5] M. de Jonge, “Build-level components,” IEEE Transactions on Software
Engineering, vol. 31, no. 7, pp. 588–600, 2005.
[6] ——, “Multi-level component composition,” in Proceedings of the 2ndGroningen Workshop Software Variability Modeling, no. 2004-7, 2004.
[7] S. Duszynski, J. Knodel, and M. Becker, “Analyzing the source codeof multiple software variants for reuse potential,” in Proceedings of the
18th Working Conference on Reverse Engineering, 2011, pp. 303–307.
[8] K. Yoshimura, D. Ganesan, and D. Muthig, “Assessing merge potential
of existing engine control systems into a product line,” in Proceedingsof the International Workshop on Software Engineering for Automotive
Systems, 2006, pp. 61–67.
[9] D. Holten and J. J. van Wijk, “Visual comparison of hierarchicallyorganized data,” in Proceedings of the 10th Joint Eurographics / IEEE
- VGTC Conference on Visualization, 2008, pp. 759–766.
[10] Y. Dubinsky, J. Rubin, T. Berger, S. Duszynski, M. Becker, and K. Czarnecki, “An exploratory study of cloning in industrial software productlines,” in Proceedings of the 17th European Conference on Software
Maintenance and Reengineering, 2013, pp. 25–34.
[11] A. Hemel and R. Koschke, “Reverse engineering variability in sourcecode using clone detection: A case study for linux variants of consumer
electronic devices,” in Proceedings of the 19th Working Conference on
Reverse Engineering, 2012, pp. 357–366.
[12] T. Lavoie, F. Khomh, E. Merlo, and Y. Zou, “Inferring repository
file structure modifications using nearest-neighbor clone detection,” inProceedings of the 19th Working Conference on Reverse Engineering,
2012, pp. 325–334.
[13] F. Beck, F.-J. Wiszniewsky, M. Burch, S. Diehl, and D. Weiskopf,“Asymmetric visual hierarchy comparison with nested icicle plots,” inProceedings of the 1st International Workshop on Graph Visualizationin Practice, 2014.
[14] Y. Lin, Z. Xing, Y. Xue, Y. Liu, X. Peng, J. Sun, and W. Zhao, “Detecting
differences across multiple instances of code clones,” in Proceedings ofthe 36th International Conference on Software Engeneering, 2014, pp.
164–174.

169