对象级粗粒度切片方法

柴玉梅，刘东昊，王黎明

（郑州大学 信息工程学院，河南 郑州450001）

0 引 言

程序切片技术是一种用于分解程序的程序分析技术，在程序开发、测试、理解等软件过程中有着广泛的应用［1－2］，本文的研究可以应用到程序理解中。程序切片的实质是分析程序元素之间的影响关系。这项技术最早由M.Weiser博士于1979年在他的博士论文中建立起来，发展到现在程序切片技术已经比较成熟。

当前较为主流的软件开发语言很多都是面向对象的，有许多研究者做了大量工作。例如A.Krishnaswamy用OPDG来计算面向对象程序切片。D.Liang，L.D.Larsen和M.J.Harrold用SDG来计算对象级切片和面向对象整程序的切片。ZHAO Jian－jun等人用DODG和SDN来计算面向对象程序的动态切片和并发切片。李必信等人提出OOAF逐层求精计算面向对象程序切片［3］。也有对传统依赖图进行扩充来对Java程序做切片的［4］。A.N.Martin等人提出了针对Java程序的层次切片方法［5］。也有对面向对象程序切片作对比研究的［6］。

在面向对象程序切片技术中，绝大部分是语句级的切片，对对象的探讨大都是融合在整个切片体系中的。李必信等人用简化的系统依赖图构造了粗粒度的切片，粒度是方法级的，也有文章如文献 ［7］对李必信的粗粒度切片有一定扩展的。D.Liang和 M.J.Harrold的对象级切片方法是基于SDG的。专门对对象间的关系的探讨如文献 ［8］，阐述了对象间的关系类型。本文在程序切片技术思想的基础上，依据对象间的关联、组合等UML类间关系［9］构造对象级切片，提出一种对象级粗粒度切片方法，这种对象级粗粒度切片相对于庞大的语句级切片在一定程度上有更好的可读性和实用性，为人们分析面向对象程序的对象框架提供了一种途径。

1 基本概念

本节主要介绍本文算法所要用到的相关概念，并给以适度的形式化描述。

定义1 对象图［10］：对象图为一个二元组＜O，R＞，集合O是程序 （本文以Java程序为例）中出现的对象的集合。R为O×O上有特定关系的边的集合，R＝ ｛（o，o’）｜（o∈O）∧ （o’∈O）∧ （（（o，o’）∈Rf）∨ （（o，o’）∈R［］）∨ （（o，o’）∈Rr））｝，其中：

Rf＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （o的字段f引用o’）｝；

R［］＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （o的数组元素引用o’）｝；

Rr＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （（o的实例方法或构造方法有一个局部变量r引用o’）∨ （o的实例方法或者构造方法调用的静态方法有一个局部变量r引用o’））∧ （﹁Rf）｝；

对象图的构造要用到指向分析技术［11］，本文不再详述。

定义2 简化对象图［10］：简化对象图＜O，R’＞是对对象图＜O，R＞中的R进行修改得到的。R’＝R∩（﹁Rtemp）；Rtemp＝ ｛（o，o’）｜ （（o，o’）∈R）∧ （o’在o中被创建）∧ （o’在没被使用的情况下就被传递到o之外）｝。 （说明：如returnnewA（…）；或newA（newB（…）））简便期间，下文提到对象图都指简化过的对象图。

根据定义1和定义2可得图1中类ArrayList，Literator，Apple，Pear和main1所组成的程序P1的初始对象图和简化对象图，如图2所示。对象图中root代表P1中的main1，其它节点是程序P1中的产生的对象集合O中的元素，我们用对象名后加数字标号来区分程序中可能出现的类型相同且对象名也相同的对象。对象图中的边表示对象间的关系，图2中边root→fruit1由语句11得。边root→apple1由语句12得。边root→pear1由语句13得。边root→e1由语句16得。边e1→fruit1∈Rf由类LIterator中的字段定义得。边fruit1→e1∈Rr由语句4得，但是又由于fruit1→e1∈Rtemp，故在简化对象图中省略。边e1→apple1∈Rr由语句17得。边fruit1→apple1∈Rr由语句14得。边e1→data1∈Rr由语句7得，但是又由于e1→data1∈Rtemp故在简化对象图中省略。边fruit1→data1∈Rf由类ArrayList中的字段定义得。边data1→apple1∈R［］由语句14得。边data1→pear1∈R［］由语句15得。边fruit1→pear1∈Rr由语句15得。

定义3 所有权模型［13］：所有权模型是J.Potter等人提出的，这个模型是建立在 “所有即决定”这一概念的基础上。

我们举例说明对象间的组合关系：设oi，oj∈O，oi中有一个字段f，f指向oj。若程序的执行中，所有对f的访问都经oi对象，则说oi对象所有 （own）oj，oi和oj是一种一对一组合关系 （compositionrelationship）。若f为集合类型，则oi和oj是一种一对多组合关系。

一般地，设oi∈O，oj∈O，ok∈O，若有oi→oj，则在对象图 （objectgraph）中不存在ok是以下两种情形之一的情况下，oi排它的所有 （own）oj。这两种情形是：①ok→oj且oi→oj且ok→oi；②ok→oj且oi→oj且oi→ok。若oi排它的所有oj则添加oj到oi的组合集CS（oi）中。识别组合关系的具体细节见文献 ［10，12－13］，其正确性见文献 ［14］。

2 对象级切片

由于程序的对象图可以展示对象间的访问关系，在对象图的基础上做切片得到的对象级粗粒度切片在复杂程序的理解上有一定作用，本节给出一个对象级粗粒度切片算法。该算法基于基本的切片思想，即程序中指定位置的元素可以影响到程序中的哪些元素，以及程序中的哪些元素可以影响到指定位置的元素，对本文来说元素就是对象，这些元素之间存在的是关联关系。由于组合关系是最强的一种语义级关系，将对象间的组合关系结合到对象级切片中能够使我们更清晰方便的理解程序结构。

设程序P的对象级切片准则为一个二元组C＝＜n，o＞，其中n为程序语句n处，o∈O为语句n处的指定对象（O是程序P中出现的对象集合）。设对象图OG为依据定义1和定义2对程序P构建的对象间的关联关系图。设集合ForeS（o）为程序P相对于切片准则C＝＜n，o＞的前向对象级切片。设集合BackS（o）为程序P相对于切片准则C＝＜n，o＞的后向对象级切片。设集合CS（o’）为和对象o’有组合关系且组合到o’的对象的集合，其中o’∈O和切片准则中的o没有必然联系。设集合SS（o）为精简的BackS（o），即结合了CS（o’）的BackS（o）。

前向切片ForeS（o）包含且仅包含对象o能影响到的对象，后向切片BackS（o）包含且仅包含那些可以影响到对象o的对象。前向切片ForeS（o）和后向切片BackS（o）的获取是建立在程序P的对象图OG基础上的。本文还引入文献 ［10］中对象间组合关系的识别，由定义3获取对象图上的所有组合关系CS（o’），并将对象间的组合关系整合到对象切片BackS（o）中从而获得对象o的精简后向切片SS（o）。

算法得到集合ForeS（o），BackS（o），CS（o’），SS（o）后，还可以结合对象图OG还原他们所含的对象之间的引用关系。

算法：对象级粗粒度切片算法

注：本文的前向切片和后向切片和传统程序切片比如文献 ［15］里所述的保持相同的含义，而不是相对于本文的对象图的边方向来说的。

3 实例分析

由图1中的类ArrayList，Literator，Book，Status，Borrower，Manager和main2组成程序P2。程序P2的对象图如图3所示，我们用对象名后加数字来区分相同类的不同对象。root代表main2，borrower1代表在语句31处实例化的对象，status1在语句19处实例化，book2在语句20处实例化，manager1在语句32处实例化，status2在语句26处实例化，book1在语句30处实例化，books1在语句25处实例化，literator1在语句4处实例化，data1在语句1处实例化。

图3 程序P2的对象图及其中的组合关系

我们举例来说明对象级粗粒度切片，由对象级粗粒度切片算法可得程序P2关于切片准则C＝＜25，books1＞的前向切片ForeS（books1）包含books1可以影响到的那些对象，在对象图上来说就是books1可以通过边 ｛manager1→books1｝，影响到对象manager1，可以通过边 ｛literator1→books1｝影响到对象literator1，可以通过边 ｛manager1→books1，root→manager1｝影响到root。故由算法步骤3可得到books1的前向切 片ForeS（books1）＝ ｛books1，manager1，literator1，root｝。我们还可以由算法得到P2关于切片准则C＝＜32，manager1＞的后向切片BackS（manager1）＝ ｛manager1，books1，book1，book2，data1，literator1，status2｝。图3的组合关 系CS（o’） 有CS（borrower1） ＝ ｛status1｝；CS（manager1）＝ ｛books1，data1，literator1 ，status2｝；CS（books1）＝ ｛data1｝。再由算法步骤4可得程序P2关于切片准则C＝＜32，manager1＞的精简后向切片SS（manager1）＝｛manager1，books1，book1，book2，literator1，status2｝。

4 结束语

本文提出了一种对象级粗粒度程序切片方法，可以获取对象级程序切片，该切片没有基于传统的程序依赖图和系统依赖图。由于本文切片粒度比语句级切片大，故存在不精确性，但是显然这种粗粒度切片效率和可理解性较语句级切片有优势，鉴于面向对象的基本结构是对象，这种对象级粒度的切片是有其实用意义的。该算法更多的是提出一种方法思想，下一步将研究除了关联、组合等关系外的其它对象间关系的切片。本文的概念都是建立在面向对象特征比较明显的Java程序的基础上，对其它面向对象语言的有待研究。

［1］SUN Jirong，LI Zhishu，WANG Li.Overview of software testing based on program slice ［J］.Application Research of Computers，2007，24 （5）：210－213 （in Chinese）.［孙继荣，李志蜀，王莉.程序切片技术在软件测试中的应用 ［J］.计算机应用研究，2007，24 （5）：210－213.］

［2］NA Rong.Using slicing technique in program comprehension［J］.Computer Engineering and Design，2003，24 （1）：30－32（in Chinese）.［纳荣.在程序理解中使用切片技术 ［J］.计算机工程与设计，2003，24 （1）：30－32.］

［3］LI Bixin.Program slicing technique and its applications ［M］.Beijing：Science Press，2006：252－287 （in Chinese）.［李必信.程序切片技术及其应用 ［M］.北京：科学出版社，2006：252－287.］

［4］Hammer C，Snelting G.An improved slicer for Java ［C］.New York：Proceedings of the 5th ACM SIGPLAN－SIGSOFT Workshop on Program Analysis for Software Tools and Engineering，2004：17－22.

［5］Martin A N，ZHANG Dafang，MIAO Li.A method of static Shavhg of Java program ［J］.Computing Technology and Automation，2005，24 （3）：69－71 （in Chinese）.［Martin A N，张大方，缪力.一种Java程序静态切片的方法 ［J］.计算机技术与自动化，2005，24 （3）：69－71.］

［6］WANG Xiaohua，GU Yidong，CHEN Weiwei，et al.Comparison and research of main object oriented slicing representation ［J］.Computer Engineering and Design，2008，29 （5）：1264－1267（in Chinese）.［王晓华，顾逸东，陈蔚薇，等.面向对象主流切片表示法的比较研究 ［J］.计算机工程与设计，2008，29 （5）：1264－1267.］

［7］DU Lin，JIANG Haiyan.A study of computing object－oriented program slicing technology ［J］.Journal of Shandong University，2008，38 （6）：41－47 （in Chinese）.［杜林，江海燕.计算面向对象程序切片技术研究 ［J］.山东大学学报，2008，38 （6）：41－47.］

［8］LIU Kun，JIANG Shujuan，LIU Lei.Description method of object relationships in object－ oriented program ［J］.Computer Engineering and Design，2008，29 （20）：5250－5252 （in Chinese）.［刘坤，姜淑娟，刘蕾.面向对象程序中对象关系的描述方法 ［J］.计算机工程与设计，2008，29 （20）：5250－5252.］

［9］Rumbaugh J，Jacobson I，Booch G.The unified modeling language reference manual［M］.2nd ed.Addison－Wesley，2004.

［10］Milanova A.Precise identification of composition relationships for UML class diagrams［C］.Proceedings of the 20th IEEE／ACM International Conference on Automated Software Engineering，2005：76－85.

［11］Sridharan M，Bodik R.Refinement－based context－sensitive point to analysis for Java［C］.New York，NY，USA：Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation，2006：387－400.

［12］Milanova A.Composition inference for UML class diagrams ［J］.Automated Software Engineering，2007，14 （2）：179－213.

［13］LIU Y，Milanova A.Ownership and immutability inference for UML－based object access control ［C］.29th International Conference on Software Engineering，2007：323－332.

［14］LIU Y，Milanova A.UML－based alias control［R］.Technical Report RPI／DCS－06－10Rensselaer Polytechnic Institute，2006.

［15］YI Tong.Relationship between forward slices and backward slices［J］.Computer Engineering and Applications，2008，44 （12）：42－44（in Chinese）.［易彤.前向切片与后向切片之间关系的研究 ［J］.计算机工程与应用，2008，44 （12）：42－44.］