In this paper we compare two approaches to discover recurrent fragments in source code: clone detection and frequent subtree mining. We apply both approaches to a mediumsized Java case and compare qualitatively and quantitatively their results in terms of what types of code fragments are detected, as well as their size, relevance, coverage, and level of detail. We conclude that both approaches are complementary, while existing overlap may be used for cross-validation of the approaches.
Index terms| clone detection, pattern mining,
frequent subtree mining, code clones, type 3 clones,
duplicate code.
Recurrent code fragments are often considered as
symptoms of bad design [
Several techniques have been proposed to detect recurrent code fragments. This paper compares two such approaches: clone detection and pattern mining. Clone detection entails that fragments of code are compared to each other line by line or statement by statement, in order to nd similar fragments, often with certain groups of tokens being excluded from the match. Pattern mining, in particular frequent subtree mining, is the problem of nding all subtrees occurring frequently in other trees, in our case abstract syntax trees (ASTs), with a support that is above a given threshold.
Since clone detection is more lightweight than pattern mining, a relevant question is whether pattern mining is worth the additional e ort, by providing alternative, richer or larger patterns, or whether it is largely redundant with respect to clone detection. To perform this comparison, we conduct a case study where we compare the approaches from two angles: to what extent do mined patterns correspond to detected clones, and how well do clones match to mined patterns?
For each direction we investigate what code fragments are found by one approach that are not found by the other. For those fragments found by both approaches we compare their coverage, size, and level of detail. This analysis allows us to make interesting observations regarding the similarity and di erences of both approaches, and to draw conclusions regarding the strengths of either approach. 2
To compare both approaches, we apply them to a medium-sized Java project: JHotDraw [5]. We selected JHotDraw version 7.5.1, which is part of the Qualitas Corpus [6], a curated collection of opensource Java software systems meant to be used for empirical studies of code artefacts [7]. JHotDraw is a two-dimensional graphics framework for structured drawing editors. It consists of 428 les and is known to make good use of design patterns [8]. Previous studies have used earlier versions of JHotDraw to look for recurrent code regularities [9, 10]. All this makes us con dent that it is an interesting case on which to conduct our comparison. 3 We now explain both approaches, their corresponding tools and used con guration, and provide some raw data and statistics on their results when applying them to JHotDraw. 3.1
Code cloning is an active eld of study: many detection techniques and tools were proposed [11]. Di erent clone types allow a di erent granularity of variance between cloned fragments [12].
Type 1 clones allow variance in structure and whitespace only.
Type 2 clones allow variance in identi er names. Type 3 clones allow complete statements to vary. We identify two useful concepts regarding code clones [12]: Clone instance: A single cloned fragment. Clone class: A set of similar clone instances, referred to hereafter as a clone.
We detect clones using our CloneRefactor tool1. This tool supports several clone type de nitions, but for this study we only considered type 3 clones. We used the following detection settings for our comparison:
With these settings we detected 136 clone classes each having 9.2 instances on average. Each of these instances span 6.8 lines on average. This makes up for a total of 8.559 out of 39.403 lines cloned (i.e., 21.7% of the system is cloned). About half of these 1Available on GitHub: https://github.com/SimonBaars/ CloneRefactor clones are found in method bodies, other clones were found in constructors or exceed the boundaries of a single method. Detecting these results in the analysed JHotDraw system took 38.7 seconds on a Macbook Air (this is relatively fast compared to pattern mining). 3.2
Our pattern mining tool is based on an extension of
the existing FREQT tree mining algorithm [
The threshold values of the di erent constraints above were determined experimentally by applying the tool on several Java cases and manually analysing the quality of the patterns mined. Since mining is quite computationally intensive, in order for our mining algorithm to nish within reasonable memory and time bounds, we have to split the codebase on which we work into separate folds, and run the miner on one fold at a time.2 For JHotDraw, we created 4 folds, and found 156 patterns in total for the con guration above. The size of the AST fragments of the mined patterns varied between 15 and 207 nodes, with an average size of 36. The mining took 33 minutes on a middle grade tower PC. We noticed, not surprisingly, 2This does imply that some patterns that occur across folds may not be found, if their frequency within a single fold does not surpass the minimum support threshold. The less and larger the folds, the less this problem occurs. that the bigger the pattern size, the more interesting it tends to be. 4
We now describe how we compared both approaches and then report on the results of our comparison. 4.1
We compared the results of both approaches through (1) manual comparison: the pattern mining team exhaustively went over all clones to look for possible matching patterns and (2) automated comparison: the clone detection team formalized an automated method to compare clones and patterns. 4.1.1
Per clone class we manually investigated 3 • the overlap and coverage (in #classes, #LOC, #occurrences/ class) when (at least) one pattern matches it; • if there was a matching pattern, we also looked for similar patterns occurring multiple times; • the relevance/usefulness/richness of the pattern for a software developer (this is a subjective criterion), in terms of a rating -/0/+. 4.1.2
Using a script4, we nd for each pattern the clone class that is the most similar and vice versa. These results help analysing to what extent one approach is redundant over the other: if a large percentage of clones closely resembles most patterns (or vice versa) this would be the case.
In the automated comparison we rst determine the locations of all 156 patterns and 136 clones. These locations consist of the le and range of each instance in a pattern/clone. For clones, this range is simply the begin and end line of a code fragment that exists elsewhere. To simplify the comparison, we chose to compare on a line-level and not take into account the begin and end column of ranges. For patterns, each separate AST node that belongs to the pattern (highlighted in orange in Fig. 3) has its own range (line and columns). For simplicity, we consider the range of a pattern instance to be the begin line of the rst AST 3You can nd the full manual analysis here: https: //github.com/CelineDknp/CloneVSPatternAnalysis/blob/ master/CloneVSPatternAnalysis.txt
4Source code available at https://github.com/SimonBaars/ CloneRefactor/tree/master/src/main/java/com/simonbaars/ clonerefactor/scripts/intimals node in the pattern and the end line that of the last AST node in the pattern.
To compare the patterns and clones at these locations we de ne a similarity metric for clones and patterns. For each pattern, we search for the clone with the highest similarity and vice versa by comparing each clone instance of each clone class to each pattern instance of each pattern. We then use the following formula to determine the similarity percentage between a clone instance and pattern instance: similarity(pi; ci) = 2 match(pi; ci) size(pi) + size(ci) (1) where pi is a pattern instance, ci is a clone instance, match is the function that yields the number of matching lines between two instances and size is the function that yields the number of lines in a code fragment. If a pattern and a clone do not intersect, the result of match will be 0, meaning no similarity at all. Given a clone instance, we compute the instance similarity by seeking the pattern instance that maximizes the similarity function (so we nd the pattern instance most similar to a clone instance): instanceSim(p; ci) = max(fsimilarity(pi; ci) j pi 2 pg) (2) where p is a set of pattern instances. Next, we calculate the similarity at the clone class level by summing the instance similarities of all instances in a clone class: classSim(p; c) = sum( instanceSim(p; ci) size(p) + size(c) (3) where c is a clone class. We compute which of the C=136 clone classes is most similar to a pattern p as the maximum similarity across all clone classes: size(ci) ci 2 c ) collectionSim(p; C) = max(fclassSim(p; c) j c 2 Cg) (4) Finally, we collect per pattern the most similar clone class: overallSim(P; C) = fcollectionSim(p; C) j p 2 P g (5) where P is the set of all 156 identi ed patterns. Using this method, we can nd which pattern is most similar to a clone and vice versa (by using the respective symmetric relations). 4.2 4.2.1
The rst thing the pattern team noticed when exploring the clones was that out of 90 clones for which there was no matching pattern, 42 occurred in less 50% 40%
We quickly realised that this behavior is caused by the C0 constraint (minimum support), which considers patterns occurring in at least ve di erent code les rather than having ve di erent occurrences. This is a result of the way the miner was con gured to have a manageable amount of patterns, and concluded that it might not have been the best t for this comparison. For future comparisons with code clone detection tools that often nd multiple clone instances in a given le, we will need to change the con guration to avoid this issue.
A second reason why some clones are not matched by patterns, results from the fact that for the mining process to nish correctly, we need to divide the code base into smaller folds. But if there is a clone that spans over 5 les but that are not all in the same fold, the pattern may still be discarded because it would not have a high enough support value for either fold. We found 13 clones that did not match a pattern for this reason. (The mining team knew this limitation 5% 3% 0-10
10% 4% 10-20 try { ((JInternalFrame)allFrames[i]) .setMaximum(false); } catch (PropertyVetoException e) {
e.printStackTrace();
The 35 other clones for which there was no matching pattern are either too small to t the constraints of the miner, or cannot really be considered as a pattern. For example, some clones consist of the end of one function along with the start of another one, like in the following snippet. //Start of function not in clone isClampRGB = b; } public boolean isClampRGBValues() {
return isClampRGB; //End of function not in clone
When analysing clone instances that did match mined patterns, the pattern mining team observed that we tend to have two types of matches.
A rst type is where the pattern is broader, so that it includes multiple clones. For example, Fig. 3 shows pattern 46 of fold 4, which actually matches 4 di erent clone classes, one for each case block.
A second type of match is when we have multiple patterns for a single clone class. In such cases, the clone usually corresponds to a speci c part of multiple patterns that are similar, or to related patterns across folds. For example, the following code snippet occurs in our patterns 60, 78, 111 and 115 of fold 4. @Override public void transform(AffineTransform tx) { Point2D.Double anchor = getStartPoint(); Point2D.Double lead = getEndPoint(); setBounds( (Point2D.Double) tx.transform(anchor,
anchor), (Point2D.Double) tx.transform(lead,
lead)); }
Finally, using our rating of how relevant a developer considers a pattern, we observed that out of a total of 46 clones that where matched by a pattern, 41 were considered interesting, leading us to conclude that many of the results found by both methods can be considered as useful to developers.
Using the automated analysis method described in Section 4.1.2 we collected interesting statistical data on the similarity of the clones and patterns found by both tools.
When looking into the percentage of clones and patterns that intersect each other (see Fig. 1), we observe that 40% of clones do not match any patterns.5 For 11% of the clones, all clone instances intersect with the pattern instances. 43% of the patterns do not intersect with any clones. For 4% of the patterns, all pattern instances intersect with the clone instances.
When manually inspecting the 11% of clone classes of which all instances intersect with patterns, we nd that most of the clone instances in the clone classes are contained within a pattern. Patterns are often larger because they allow more variance in a fragment of code. Because of that, patterns often capture additional information surrounding a clone. This is why there is a large di erence between clone to pattern and pattern to clone at 100% intersecting instances (see Fig. 1).
Fig. 2 shows how many clones and patterns are similar to each other. The same percentages of clones/patterns that do not intersect can be found here as 0% similar. However, here we see the categories gradually decreasing towards 100% (no clone/pattern combination is actually 100% similar). By far, most clone/pattern combinations are less than 50% similar: 92% of clones and 96% of patterns. This leaves only 8% of clones and 4% of patterns with a similarity higher than 50%. 5
Before presenting our analysis of these results, we emphasize that this experiment was only an initial comparison between the two approaches. Further validation on other case studies, with improved settings, and by researchers other than the original tool creators, are required. Nevertheless, the results obtained already allowed us to reach some interesting insights. 5.1
In cases where both approaches found similar code fragments, the overlap was not always complete. Sometimes one approach (often code cloning) found more fragments than the other, or (typically pattern mining) found larger or richer code fragments. Combining both approaches to complement each other's results would be an interesting research direction.
5This percentage would very likely become signi cantly larger if we would resolve the issue we encountered with the C0 constraint; requiring the patterns to occur in di erent code les. The results of the automated comparison show that, although most clones share some relation with some patterns, there are only very few clones where this relation is particularly strong. Often, patterns are found in completely di erent parts than where clones are found, or they brie y intersect instead of matching completely.
This shows that clone detection does, for the largest part, nd di erent results than pattern mining. This indicates that both approaches are not redundant over one another, instead complementing each other. 6
As recurrent code fragments are often considered symptoms of bad design, several detection techniques have been proposed. Comparative studies across emerging techniques could shed further light into the trade-o s between time complexity and quality of results. We set out to compare two such approaches: clone detection and pattern mining, since clone detection seems more lightweight and a relevant question is whether pattern mining is worth the additional e ort. Our automated comparison method involves several levels of data aggregation and is symmetric with respect to the comparison direction: patterns to clone classes and vice versa.
Our ndings indicate that the two approaches are rather complementary. About half of the clones/patterns share no relation with each other. In the cases that clone detection and pattern mining are not 100% similar but do intersect, often the pattern is larger than the clone. This is because patterns allow for more structural variance in recurrent fragments than clone detection. The main reason that sometimes clones are larger than patterns is that patterns seem constrained to a single subtree, whereas clones can span several methods and even exceed class boundaries if they are all similar.
Part of this work was conducted in the context of an industry-university research project, funded by the Belgian Innoviris TeamUp project INTiMALS (2017TEAM-UP-7). [3] Magiel Bruntink, Arie Van Deursen, Remco Van Engelen, and Tom Tourwe. On the use of clone detection for identifying crosscutting concern code. IEEE Transactions on Software Engineering, 31(10):804{818, 2005. [4] Peri Tarr, Harold Ossher, William Harrison, and Stanley M. Sutton. N degrees of separation: Multi-dimensional separation of concerns. In Proceedings of the 1999 International Conference on Software Engineering, pages 107{119. IEEE, 1999. [5] Erich Gamma and Thomas Eggenschwiler. Jhotdraw, 2004. [6] Ewan Tempero. Qualitas [http://qualitascorpus.com/; October-2019].
Corpus, accessed 2013.
31[7] Jolita Savolskyte. Review of the jhotdraw framework, 2004. Technical University HamburgHarburg. [8] Henrik B rbak Christensen. Frameworks: Putting design patterns into perspective. In Proceedings of the 9th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, ITiCSE '04, pages 142{145.
ACM, 2004. [9] Andy Kellens, Kim Mens, and Paolo Tonella.
A survey of automated code-level aspect mining techniques. In Awais Rashid and Mehmet Aksit, editors, Transactions on Aspect-Oriented Software Development IV, pages 143{162. Springer, 2007. [10] Angela Lozano, Andy Kellens, Kim Mens, and Gabriela Arevalo. Mining source code for structural regularities. In Proceedings of the 2010 17th Working Conference on Reverse Engineering, pages 22{31. IEEE Computer Society, 2010. [11] Je rey Svajlenko and Chanchal K Roy. Evaluating modern clone detection tools. In 2014 IEEE International Conference on Software Maintenance and Evolution, pages 321{330. IEEE, 2014. [12] Chanchal Kumar Roy and James R Cordy. A survey on software clone detection research. Queen's School of Computing TR, 541(115):64{68, 2007.