基于抽象语法树的数据泥团自动检测研究

刘宏韬 刘 伟,2 胡志刚

1(中南大学软件学院 湖南 长沙 410075)2(湖南中医药大学管理与信息工程学院 湖南 长沙 410208)

基于抽象语法树的数据泥团自动检测研究

刘宏韬1刘 伟1,2胡志刚1

1(中南大学软件学院 湖南 长沙 410075)2(湖南中医药大学管理与信息工程学院 湖南 长沙 410208)

数据泥团是一种常见的代码味道，它将带来重复代码和维护难度增加等问题。针对大部分已有的代码味道自动检测工具无法检测数据泥团，且检测类型不全面等问题，提出一种基于抽象语法树的数据泥团自动检测方法。该方法在已有检测工具的基础上，增加了新的数据泥团类型，并加入了剔除冗余数据泥团和提取子数据泥团等步骤。通过对4个开源项目进行数据泥团实验，结果表明方法具有较高的精确率，与Stench Blossom、inFusion等工具的数据泥团自动检测功能相比，能够检测出一些其他工具无法检测的数据泥团。同时，该方法具有较好的性能，执行时间与系统规模成正比。

代码味道 数据泥团 抽象语法树 源代码解析 重构

0 引 言

代码味道是指源代码中存在的一些不良实现方案。软件工程大师Martin Fowler和Kent Beck在文献[1]中初次使用“代码味道”一词来描述这些不良实现方案，文献中定义了22种常见的代码味道，包括数据泥团、重复代码、霰弹式修改等。此后，一些新的代码味道[2]被学者和研究人员陆续提出。检测、去除代码味道对于提高代码质量具有非常重要的意义[3]，去除代码味道能够改善代码的可维护性，因此应当对程序代码中的代码味道进行检测和合理重构，在不改变程序外部行为的前提下改善代码的质量。

开发人员往往在对代码味道进行重构之前，人工审查代码、检测代码味道，这样的方式效率低下，且正确率不高。近年来，自动检测代码味道已成为软件工程领域的一个研究热点。Liu等人[4-5]对泛化重构机会检测进行了研究，并基于概念关系、实现相似性等开发了一款重构时机检测工具。Maneerat等人[6]提出了从软件设计模型的角度检测代码味道，将7种机器学习的算法运用于数项代码味道数据集，并根据27个度量指标检测7种代码味道，并对各种机器学习算法在代码优化方面的性能进行了评估。此外，针对检测代码味道这一问题也诞生了一些自动化工具。PMD[7]可以检查源代码中存在的过大类、重复代码等代码味道，它允许用户自定义检测这些代码味道的阈值；CheckStyle[8]能够探测代码大小是否违规、类的设计是否良好，也能找出过长函数、过长参数列等代码味道。

本文将以源代码中数据泥团代码味道为研究对象，提出了一种精确率及性能俱佳的数据泥团自动检测算法，有助于软件开发人员快速精准地发现项目中存在的数据泥团代码味道，为进一步的数据泥团重构提供有力支持。

1 数据泥团和抽象语法树

1.1 数据泥团

数据泥团[1]是22种常见代码味道之一，它指代那些经常捆绑出现的数据，如多个类中出现了相同的数个属性，或多个方法中出现了相同的数个参数。对于类属性数据泥团，应当使用提炼类,将数据提炼到一个独立对象；对于方法参数数据泥团，应当使用引入参数对象。数据泥团的存在将增加系统的耦合度，自动检测并重构数据泥团，对数据实施集中式管理，可以提高代码的可维护性和可复用性，进而增强系统内聚性，降低耦合度，并提高代码的可读性、可扩展性等。Fontana等人[9]对现有的代码味道自动检测工作进行研究，发现对于数据泥团这一代码味道，目前仅有inFusion[10]和Stench Blossom[11]两款工具能作出自动检测。

1.2 抽象语法树

数据泥团的检测工作基于对抽象语法树AST(Abstract Syntax Tree)的分析，将指定项目源代码转换成抽象语法树之后，再收集数据泥团检测的相关信息。抽象语法树是一种常用的程序代码的中间表示形式。

本文使用Java语言为例，Eclipse JDT提供了Eclipse AST[12]用于将Java源代码解析为抽象语法树，并能对其进行节点的创建、修改。Eclipse AST中ASTNode类作为所有Java语法结构节点的父类，它的子类如TypeDeclaration(类声明)、MethodDeclaration(方法声明)等都对相应的语法结构进行了明确地描述，并提供了大量的方法用于访问该节点的属性，如类名、方法参数列表等。此外，还提供了一个ASTVisitor类用于定义AST的抽象访问者，在该类中声明了一组访问各类AST节点的方法，用于对各种类型的节点实施相应的操作。

2 数据泥团自动检测算法

考虑到检测数据泥团后的重构流程，本文所检测的单个数据泥团将包含两部分：

(1) 数据集 (Datum) 单个数据泥团所包含的数据。

(2) 位置集 (Location) 该数据泥团出现的位置。

本文主要针对数据类型、名称(部分包括初始值)完全相同的情况，数据泥团中的数据将以如表1格式的字符串进行存储。

表1 数据字符串格式

数据集来自对类属性和方法参数的收集、计算和筛选，其中筛选主要依据以下两项度量指标：

(1) 重复度 (Repeat) 数据泥团出现的次数。

(2) 规模 (Size) 数据泥团的大小。

考虑到使用者检测数据泥团需求的不同，数据泥团的重复度下限(minRepeat)和规模下限(minSize)两项阈值将作为参数传入，若一候选数据泥团重复度和规模均不小于重复度下限和规模下限(即Repeat≥minRepeat & Size≥minSize)，则将其判定为一个数据泥团，使用者可以根据需求自定义重复度和规模阈值以查找所需的数据泥团。

图1 数据泥团自动检测流程图

数据泥团自动检测流程如图1所示，其中步骤解释如下：

(1) 将源代码解析为AST。

(2) 收集数据信息 遍历AST中每一个类节点(TypeDeclaration)、匿名类节点(AnonymousClassDeclaration)和方法节点(MethodDeclaration)，对符合规模下限的类属性和方法参数进行整理，得到数据信息列表。数据信息包含数据集和位置两部分，数据集即所对应的类属性或方法参数以表1中的字符串格式存储的字符串集合，位置即所对应的类或方法所在的位置。

(3) 构建候选数据泥团集 对数据信息列表中的每两个数据信息p和q进行集合运算，将符合规模下限的结果存储为数据泥团A，得到候选数据泥团集。其中A.datum = p.datum ∩ q.datum。之后需对候选数据泥团集按照数据集的规模，从大到小排序，以确保规模较大的数据泥团优先被检测。

(4) 合并重复数据泥团 对于候选数据泥团集中的每两个候选数据泥团A和B，如果A和B两者数据集相同，则将B的位置集合并到A的位置集中，并从候选数据泥团集中删除B。

(5) 剔除冗余数据泥团 假设候选数据泥团集中存在{a, b}和{b, c}，它们都存在于方法func(a, b, c)，若将{a, b}确定为数据泥团并封装为数据类A，则原参数列表将被修改为func(A, c)，参数列表中将不再存在数据泥团{b, c}，因此需要从候选数据泥团中删除{b, c}。

(6) 提取子数据泥团 假设重复度阈值为2，func(a, b, c)中存在的数据泥团{a, b}被封装成数据类A，原参数列表将被修改为func(A, c)，若{A, c}仍为满足阈值要求的数据泥团并被封装为类B，则需将{a, b}作为{A, c}的子数据泥团，即在重构时B继承A，且原参数列表修改为func(B)。

(7) 筛选数据泥团 根据输入的规模下限和重复度下限对候选数据泥团集进行筛选，以得到最终数据泥团检测结果。

数据泥团自动检测算法伪代码如表2所示。

表2 自动检测算法伪代码

该算法根据所处理内容的不同，可划分为两个部分进行时间复杂度的分析。第一部分为数据信息的收集，该部分主要将代码源文件转换到抽象语法树并进行遍历进而收集数据信息，因此不难得知数据信息收集过程的时间复杂度为O(n)，n为源代码文件的数量，即理论上运行时间随着源代码文件数量的增加而线性增加。第二部分为数据泥团的检测，该部分主要针对第一部分中所收集的数据信息进行集合运算等一系列的处理，根据算法分析可知时间复杂度基本为O(n2)，n为第一部分中所收集的数据信息的数量，即理论上运行时间与数据信息数的平方成正比。

3 实验结果分析

本文算法已嵌入到前期研究工作所开发的一款Eclipse插件SCORT[13]中。为了测试数据泥团的自动检测效果，本文选取了同样具有数据泥团自动检测功能的工具inFusion和Stench Blossom与SCORT进行比较，三款工具检测效果如表3所示。

表3 数据泥团自动检测工具对比

由检测效果可知：Stench Blossom[14]作为Eclipse插件，其检测结果实时呈现在编辑器中，效率较慢，且只能针对当前编译单元(即当前打开的文件)进行检测，检测效果一般；inFusion作为一款定期升级的商业软件，检测效果较好，且能针对整个工程进行检测，与SCORT检测效果相近，SCORT所检测的数据泥团类型更为全面。为了验证本文所述数据泥团的自动检测算法的执行效率和正确性，本文选取四个开源项目进行实验，并为了与检测效果相近的inFusion工具对比，因此使用与inFusion相同的阈值(即minRepeat=3、minSize=5)。本文选取了四个开源Java 项目，这四个项目规模和类型不一，基本信息如表4所示。

表4 待测项目基本信息

3.1 数据泥团检测算法执行效率实验

实验首先使用SCORT工具对四个项目进行数据泥团的检测，并对算法执行时间进行分析。对于每一个项目，数据泥团自动检测算法均执行5次，然后分别计算算法两个部分的平均时间。数据泥团检测实验在一台安装Windows 7操作系统的PC机上进行，其配置为：双核2.00 GHz，2 GB DDR2 RAM。数据泥团自动检测算法包括数据信息的收集和数据泥团的检测两个部分，表4中四个待测项目的数据信息收集平均时间如表5所示。

表5 数据信息收集平均时间

由表5可知，随着系统规模的增大(源文件数量的增加)，数据信息收集的平均执行时间也逐步增加，以源代码文件数为X轴，数据信息收集程序的执行时间为Y轴，可得图2所示源文件数-数据信息收集执行时间图。

图2 源文件数-数据信息收集执行时间图

图2中虚线为对实验结果进行拟合的线性趋势线，拟合方程为y=6.3957x+574.97，R2=0.9996。在数据信息收集部分，主要是将项目中的所有源文件转换为抽象语法树，并在抽象语法树中根据条件收集数据信息，因此该部分执行时间与源文件数量关系密切。因此从图2中可以看到，执行时间与系统规模(源文件数量)成正比，随系统规模的增大执行时间增加，整体呈现线性关系，算法具有良好的性能。

考虑到数据泥团的检测部分算法执行速度较快，因此该部分实验将时间精确到纳秒进行统计，并在表4中四个项目的基础上追加六个开源项目，总共十个开源项目的数据泥团检测部分执行时间如表6所示。

表6 数据泥团检测平均时间

由表6可知，随着算法第一部分所收集的数据信息的数量增加，数据泥团检测的平均执行时间也逐步增加，以数据信息数为X轴，数据泥团检测程序的执行时间为Y轴，可得图3所示数据信息数-数据泥团检测执行时间图。

图3 数据信息数-数据泥团检测执行时间图

图3中虚线为对实验结果进行拟合的线性趋势线，拟合方程为y=263.87x2+218990x+6E+06，R2=0.9719。在数据泥团检测部分，主要是对前段算法所收集的数据信息进行集合运算，因此执行时间与该项目所收集的数据信息关系密切。从图3中的趋势线可以看到，执行时间与数据信息数的平方成正比。总体看来，本文中的数据泥团自动检测算法执行效率与系统规模成正比，执行时间随着系统规模的增加而增加，算法具有较好的执行效率。

3.2 数据泥团检测算法性能实验

为了更好地评价数据泥团检测结果，本文使用精确率(Precision)和召回率(Recall)来分析算法的性能，并结合人工审查判断检测结果是否正确，精确率和召回率分别表示为：

Precision=TP/(TP+FP)

(1)

Recall=TP/(TP+FN)

(2)

其中，真阳性TP(True Positive)表示工具检测到的正确数据泥团数量；假阳性FP(False Positive)表示工具检测到的错误数据泥团数量，即人工审查后发现检测出的数据泥团是错误的；假阴性FN(False Negative)表示工具没有检测到，但人工审查后发现应当作为数据泥团检测的数量。通过对检测出的数据泥团进行逐个审查可以得到TP和FP值。

而对于FN值，由于人工查找正确的数据泥团难度较大，因此，实验将既有成熟的代码检测工具inFusion检测结果视为人工查找到的正确的数据泥团。SCORT和inFusion对表4中四个项目的数据泥团检测结果如表7所示。

表7 SCORT与inFusion的数据泥团检测结果

根据表7得到TP、FP和FN值，并计算出相应的精确率和召回率，结果如表8所示。

表8 数据泥团自动检测精确率与召回率

对于SCORT和inFusion两款工具检测结果的差异，以及召回率进行分析。表7中，两款工具对于项目TinyUML的检测结果相同；在项目Ice Hockey Manager的检测结果中，SCORT检测到了2个类属性数据泥团，而inFusion由于没有该项功能，因此没有检测结果；项目Abbot的检测结果中，SCORT检测到7个数据泥团，剔除了4个inFusion结果中存在的冗余数据泥团，另外检测出3个来自于重写方法的数据泥团，这些方法所在的类存在于同一继承树；项目Robocode的检测结果中，SCORT检测到13个数据泥团，剔除了3个inFusion结果中存在的冗余数据泥团，另外检测出1个来自于重写方法的数据泥团，以及1个类属性数据泥团。

经分析发现，检测结果存在差异的主要原因为SCORT与inFusion工具所使用的算法的目的和对“数据泥团”概念的认识不一。inFusion工具目的在于度量和评估软件的质量，且它所检测的数据泥团仅为方法参数；SCORT目的在于检测重构时机，便于日后的重构工作，因此将冗余数据泥团情况进行处理，并且SCORT所检测的数据泥团包括了方法参数和类成员属性。对于来自同一继承树的类成员属性，以及来自重写方法的参数，本文都认为是需重构的数据泥团。SCORT相较于inFusion所检测的数据泥团类型更为全面，更符合数据泥团的定义。

4 结 语

代码味道的自动探测与优化对于提高软件质量具有重要意义，但针对“数据泥团”这一代码味道的检测算法和工具较少。本文研究了一套基于抽象语法树的数据泥团自动检测算法，该算法在以往研究成果的基础上增加了检测类成员属性所组成的数据泥团，并提出剔除冗余数据泥团、提取子数据泥团，为日后的自动重构工作做好铺垫。

通过对4个开源项目进行数据泥团检测实验，结果表明，该方法精确率非常高，能够正确检测出源代码中所有的数据泥团，实验项目的数据泥团检测精确率可达100%，并消除了所有的假阳性实例，与已有方法相比，其结果更全面；算法执行效率较高，执行时间与系统规模成正比，适用于各种规模的系统。

本文算法将类成员属性与方法参数分开处理，且以字符串形式完全匹配而进行数据泥团的检测，但在实际软件开发过程中有着同时存在于属性和参数的数据泥团，或变量名并不完全相同的数据泥团，在后续工作中，将逐步改进上述问题。此外，还将实现对数据泥团的自动重构，例如将其自动封装为数据类。

[1] Fowler M. Refactoring: improving the design of existing code[M]. Massachusetts: Addison-Wesley, 1999.

[2] Kerievsky J. Refactoring to patterns[M]. Massachusetts: Addison-Wesley, 2004.

[3] Emden E V, Moonen L. Java quality assurance by detecting code smells[C]//Proceedings of the Ninth Working Conference on Reverse Engineering (WCRE' 02), 2002: 97-106.

[4] Liu H, Ma Z, Shao W, et al. Schedule of bad smell detection and resolution: a new way to save effort[J]. IEEE Transactions on Software Engineering, 2012, 38(1): 220-235.

[5] Liu H, Niu Z, Ma Z, et al. Identification of generalization refactoring opportunities[J]. Automated Software Engineering, 2013, 20(1): 81-110.

[6] Maneerat N, Muenchaisri P. Bad-smell prediction from software design model using machine learning techniques[C]//Computer Science and Software Engineering (JCSSE), 2011 Eighth International Joint Conference on. IEEE, 2011: 331-336.

[7] Dangel A, Pelisse R. PMD[CP/OL]. (2013-05-01) [2013-05-04]. http://sourceforge.net/projects/pmd/.

[8] Burn O. CheckStyle[CP/OL]. (2012-10-12) [2013-05-04]. http://sourceforge.net/projects/checkstyle/.

[9] Fontana F A, Braione P, Zanoni M. Automatic detection of bad smells in code: An experimental assessment[J]. Journal of Object Technology, 2012, 11(2): 1-38.

[10] Intooitus SRL. inFusion[CP/OL]. (2012-10-31) [2013-05-04]. http://www.intooitus.com/products/infusion.

[11] Murphy-Hill E. Stench Blossom[CP/OL]. http://people.engr.ncsu.edu/ermurph3/tools.html.

[12] Thomas K, Eye M G, Olivier T. Eclipse corner article: abstract syntax tree[EB/OL]. (2006-11-20) [2013-05-04]. http:// www.eclipse.org/articles/article.php?file=Article-JavaCodeManipulation_AST/index.html.

[13] 刘伟, 刘宏韬, 胡志刚. 代码缺陷与代码味道的自动探测与优化研究[J]. 计算机应用研究, 2014, 31(1): 170-176.

[14] Murphy-Hill E, Black A P. An interactive ambient visualization for code smells[C]//Proceedings of the 5th International Symposium on Software Visualization. ACM, 2010: 5-14.

RESEARCH OF AUTOMATIC DETECTION FOR DATA CLUMPS BASED ON ABSTRACT SYNTAX TREE

Liu Hongtao1Liu Wei1,2Hu Zhigang11(SchoolofSoftware,CentralSouthUniversity,Changsha410075,Hunan,China)

2(SchoolofManagementandInformationEngineering,HunanUniversityofChineseMedicine,Changsha410208,Hunan,China)

Data Clumps is a common code smell, it will lead to issues such as duplicated code and increased difficulty in maintenance. As most existing code smell automatic detection tools fail to detect data clumps, and the detection type is not complete, a data clumps automatic detection based on abstract syntax tree is proposed. On the basis of existing detection tools, adding new types of data clumps to the algorithm, with some new steps as redundant data elimination and sub-data clumps extraction. Experiments are executed on 4 open source projects. Results show that the approach has high accuracy, and it is able to detect data clumps which other tools failed to detect, such as Stench Blossom, inFusion, etc. In addition, this approach has good efficiency and the execution time is directly proportionate to the size of system.

Code smell Data clumps Abstract syntax tree Source code parsing Refactoring

2015-12-03。国家自然科学基金项目(61272148)。刘宏韬，硕士生，主研领域：软件工程。刘伟，高工。胡志刚，教授。

TP311.5

A

10.3969/j.issn.1000-386x.2017.01.003