柴玉梅，劉東昊，王黎明

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001）

0 引 言

程序切片技術(shù)是一種用于分解程序的程序分析技術(shù)，在程序開發(fā)、測試、理解等軟件過程中有著廣泛的應(yīng)用［1－2］，本文的研究可以應(yīng)用到程序理解中。程序切片的實(shí)質(zhì)是分析程序元素之間的影響關(guān)系。這項(xiàng)技術(shù)最早由M.Weiser博士于1979年在他的博士論文中建立起來，發(fā)展到現(xiàn)在程序切片技術(shù)已經(jīng)比較成熟。

當(dāng)前較為主流的軟件開發(fā)語言很多都是面向?qū)ο蟮?，有許多研究者做了大量工作。例如A.Krishnaswamy用OPDG來計(jì)算面向?qū)ο蟪绦蚯衅?。D.Liang，L.D.Larsen和M.J.Harrold用SDG來計(jì)算對(duì)象級(jí)切片和面向?qū)ο笳绦虻那衅HAO Jian－jun等人用DODG和SDN來計(jì)算面向?qū)ο蟪绦虻膭?dòng)態(tài)切片和并發(fā)切片。李必信等人提出OOAF逐層求精計(jì)算面向?qū)ο蟪绦蚯衅?］。也有對(duì)傳統(tǒng)依賴圖進(jìn)行擴(kuò)充來對(duì)Java程序做切片的［4］。A.N.Martin等人提出了針對(duì)Java程序的層次切片方法［5］。也有對(duì)面向?qū)ο蟪绦蚯衅鲗?duì)比研究的［6］。

在面向?qū)ο蟪绦蚯衅夹g(shù)中，絕大部分是語句級(jí)的切片，對(duì)對(duì)象的探討大都是融合在整個(gè)切片體系中的。李必信等人用簡化的系統(tǒng)依賴圖構(gòu)造了粗粒度的切片，粒度是方法級(jí)的，也有文章如文獻(xiàn) ［7］對(duì)李必信的粗粒度切片有一定擴(kuò)展的。D.Liang和 M.J.Harrold的對(duì)象級(jí)切片方法是基于SDG的。專門對(duì)對(duì)象間的關(guān)系的探討如文獻(xiàn) ［8］，闡述了對(duì)象間的關(guān)系類型。本文在程序切片技術(shù)思想的基礎(chǔ)上，依據(jù)對(duì)象間的關(guān)聯(lián)、組合等UML類間關(guān)系［9］構(gòu)造對(duì)象級(jí)切片，提出一種對(duì)象級(jí)粗粒度切片方法，這種對(duì)象級(jí)粗粒度切片相對(duì)于龐大的語句級(jí)切片在一定程度上有更好的可讀性和實(shí)用性，為人們分析面向?qū)ο蟪绦虻膶?duì)象框架提供了一種途徑。

1 基本概念

本節(jié)主要介紹本文算法所要用到的相關(guān)概念，并給以適度的形式化描述。

定義1 對(duì)象圖［10］：對(duì)象圖為一個(gè)二元組＜O，R＞，集合O是程序 （本文以Java程序?yàn)槔┲谐霈F(xiàn)的對(duì)象的集合。R為O×O上有特定關(guān)系的邊的集合，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的數(shù)組元素引用o’）｝；

Rr＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （（o的實(shí)例方法或構(gòu)造方法有一個(gè)局部變量r引用o’）∨ （o的實(shí)例方法或者構(gòu)造方法調(diào)用的靜態(tài)方法有一個(gè)局部變量r引用o’））∧ （﹁Rf）｝；

對(duì)象圖的構(gòu)造要用到指向分析技術(shù)［11］，本文不再詳述。

定義2 簡化對(duì)象圖［10］：簡化對(duì)象圖＜O，R’＞是對(duì)對(duì)象圖＜O，R＞中的R進(jìn)行修改得到的。R’＝R∩（﹁Rtemp）；Rtemp＝ ｛（o，o’）｜ （（o，o’）∈R）∧ （o’在o中被創(chuàng)建）∧ （o’在沒被使用的情況下就被傳遞到o之外）｝。 （說明：如returnnewA（…）；或newA（newB（…）））簡便期間，下文提到對(duì)象圖都指簡化過的對(duì)象圖。

根據(jù)定義1和定義2可得圖1中類ArrayList，Literator，Apple，Pear和main1所組成的程序P1的初始對(duì)象圖和簡化對(duì)象圖，如圖2所示。對(duì)象圖中root代表P1中的main1，其它節(jié)點(diǎn)是程序P1中的產(chǎn)生的對(duì)象集合O中的元素，我們用對(duì)象名后加數(shù)字標(biāo)號(hào)來區(qū)分程序中可能出現(xiàn)的類型相同且對(duì)象名也相同的對(duì)象。對(duì)象圖中的邊表示對(duì)象間的關(guān)系，圖2中邊root→fruit1由語句11得。邊root→apple1由語句12得。邊root→pear1由語句13得。邊root→e1由語句16得。邊e1→fruit1∈Rf由類LIterator中的字段定義得。邊f(xié)ruit1→e1∈Rr由語句4得，但是又由于fruit1→e1∈Rtemp，故在簡化對(duì)象圖中省略。邊e1→apple1∈Rr由語句17得。邊f(xié)ruit1→apple1∈Rr由語句14得。邊e1→data1∈Rr由語句7得，但是又由于e1→data1∈Rtemp故在簡化對(duì)象圖中省略。邊f(xié)ruit1→data1∈Rf由類ArrayList中的字段定義得。邊data1→apple1∈R［］由語句14得。邊data1→pear1∈R［］由語句15得。邊f(xié)ruit1→pear1∈Rr由語句15得。

定義3 所有權(quán)模型［13］：所有權(quán)模型是J.Potter等人提出的，這個(gè)模型是建立在 “所有即決定”這一概念的基礎(chǔ)上。

我們舉例說明對(duì)象間的組合關(guān)系：設(shè)oi，oj∈O，oi中有一個(gè)字段f，f指向oj。若程序的執(zhí)行中，所有對(duì)f的訪問都經(jīng)oi對(duì)象，則說oi對(duì)象所有 （own）oj，oi和oj是一種一對(duì)一組合關(guān)系 （compositionrelationship）。若f為集合類型，則oi和oj是一種一對(duì)多組合關(guān)系。

一般地，設(shè)oi∈O，oj∈O，ok∈O，若有oi→oj，則在對(duì)象圖 （objectgraph）中不存在ok是以下兩種情形之一的情況下，oi排它的所有 （own）oj。這兩種情形是：①ok→oj且oi→oj且ok→oi；②ok→oj且oi→oj且oi→ok。若oi排它的所有oj則添加oj到oi的組合集CS（oi）中。識(shí)別組合關(guān)系的具體細(xì)節(jié)見文獻(xiàn) ［10，12－13］，其正確性見文獻(xiàn) ［14］。

2 對(duì)象級(jí)切片

由于程序的對(duì)象圖可以展示對(duì)象間的訪問關(guān)系，在對(duì)象圖的基礎(chǔ)上做切片得到的對(duì)象級(jí)粗粒度切片在復(fù)雜程序的理解上有一定作用，本節(jié)給出一個(gè)對(duì)象級(jí)粗粒度切片算法。該算法基于基本的切片思想，即程序中指定位置的元素可以影響到程序中的哪些元素，以及程序中的哪些元素可以影響到指定位置的元素，對(duì)本文來說元素就是對(duì)象，這些元素之間存在的是關(guān)聯(lián)關(guān)系。由于組合關(guān)系是最強(qiáng)的一種語義級(jí)關(guān)系，將對(duì)象間的組合關(guān)系結(jié)合到對(duì)象級(jí)切片中能夠使我們更清晰方便的理解程序結(jié)構(gòu)。

設(shè)程序P的對(duì)象級(jí)切片準(zhǔn)則為一個(gè)二元組C＝＜n，o＞，其中n為程序語句n處，o∈O為語句n處的指定對(duì)象（O是程序P中出現(xiàn)的對(duì)象集合）。設(shè)對(duì)象圖OG為依據(jù)定義1和定義2對(duì)程序P構(gòu)建的對(duì)象間的關(guān)聯(lián)關(guān)系圖。設(shè)集合ForeS（o）為程序P相對(duì)于切片準(zhǔn)則C＝＜n，o＞的前向?qū)ο蠹?jí)切片。設(shè)集合BackS（o）為程序P相對(duì)于切片準(zhǔn)則C＝＜n，o＞的后向?qū)ο蠹?jí)切片。設(shè)集合CS（o’）為和對(duì)象o’有組合關(guān)系且組合到o’的對(duì)象的集合，其中o’∈O和切片準(zhǔn)則中的o沒有必然聯(lián)系。設(shè)集合SS（o）為精簡的BackS（o），即結(jié)合了CS（o’）的BackS（o）。

前向切片F(xiàn)oreS（o）包含且僅包含對(duì)象o能影響到的對(duì)象，后向切片BackS（o）包含且僅包含那些可以影響到對(duì)象o的對(duì)象。前向切片F(xiàn)oreS（o）和后向切片BackS（o）的獲取是建立在程序P的對(duì)象圖OG基礎(chǔ)上的。本文還引入文獻(xiàn) ［10］中對(duì)象間組合關(guān)系的識(shí)別，由定義3獲取對(duì)象圖上的所有組合關(guān)系CS（o’），并將對(duì)象間的組合關(guān)系整合到對(duì)象切片BackS（o）中從而獲得對(duì)象o的精簡后向切片SS（o）。

算法得到集合ForeS（o），BackS（o），CS（o’），SS（o）后，還可以結(jié)合對(duì)象圖OG還原他們所含的對(duì)象之間的引用關(guān)系。

算法：對(duì)象級(jí)粗粒度切片算法

注：本文的前向切片和后向切片和傳統(tǒng)程序切片比如文獻(xiàn) ［15］里所述的保持相同的含義，而不是相對(duì)于本文的對(duì)象圖的邊方向來說的。

3 實(shí)例分析

由圖1中的類ArrayList，Literator，Book，Status，Borrower，Manager和main2組成程序P2。程序P2的對(duì)象圖如圖3所示，我們用對(duì)象名后加數(shù)字來區(qū)分相同類的不同對(duì)象。root代表main2，borrower1代表在語句31處實(shí)例化的對(duì)象，status1在語句19處實(shí)例化，book2在語句20處實(shí)例化，manager1在語句32處實(shí)例化，status2在語句26處實(shí)例化，book1在語句30處實(shí)例化，books1在語句25處實(shí)例化，literator1在語句4處實(shí)例化，data1在語句1處實(shí)例化。

圖3 程序P2的對(duì)象圖及其中的組合關(guān)系

我們舉例來說明對(duì)象級(jí)粗粒度切片，由對(duì)象級(jí)粗粒度切片算法可得程序P2關(guān)于切片準(zhǔn)則C＝＜25，books1＞的前向切片F(xiàn)oreS（books1）包含books1可以影響到的那些對(duì)象，在對(duì)象圖上來說就是books1可以通過邊 ｛manager1→books1｝，影響到對(duì)象manager1，可以通過邊 ｛literator1→books1｝影響到對(duì)象literator1，可以通過邊 ｛manager1→books1，root→manager1｝影響到root。故由算法步驟3可得到books1的前向切 片F(xiàn)oreS（books1）＝ ｛books1，manager1，literator1，root｝。我們還可以由算法得到P2關(guān)于切片準(zhǔn)則C＝＜32，manager1＞的后向切片BackS（manager1）＝ ｛manager1，books1，book1，book2，data1，literator1，status2｝。圖3的組合關(guān) 系CS（o’） 有CS（borrower1） ＝ ｛status1｝；CS（manager1）＝ ｛books1，data1，literator1 ，status2｝；CS（books1）＝ ｛data1｝。再由算法步驟4可得程序P2關(guān)于切片準(zhǔn)則C＝＜32，manager1＞的精簡后向切片SS（manager1）＝｛manager1，books1，book1，book2，literator1，status2｝。

4 結(jié)束語

本文提出了一種對(duì)象級(jí)粗粒度程序切片方法，可以獲取對(duì)象級(jí)程序切片，該切片沒有基于傳統(tǒng)的程序依賴圖和系統(tǒng)依賴圖。由于本文切片粒度比語句級(jí)切片大，故存在不精確性，但是顯然這種粗粒度切片效率和可理解性較語句級(jí)切片有優(yōu)勢，鑒于面向?qū)ο蟮幕窘Y(jié)構(gòu)是對(duì)象，這種對(duì)象級(jí)粒度的切片是有其實(shí)用意義的。該算法更多的是提出一種方法思想，下一步將研究除了關(guān)聯(lián)、組合等關(guān)系外的其它對(duì)象間關(guān)系的切片。本文的概念都是建立在面向?qū)ο筇卣鞅容^明顯的Java程序的基礎(chǔ)上，對(duì)其它面向?qū)ο笳Z言的有待研究。

［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）.［孫繼榮，李志蜀，王莉.程序切片技術(shù)在軟件測試中的應(yīng)用 ［J］.計(jì)算機(jī)應(yīng)用研究，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）.［納榮.在程序理解中使用切片技術(shù) ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2003，24 （1）：30－32.］

［3］LI Bixin.Program slicing technique and its applications ［M］.Beijing：Science Press，2006：252－287 （in Chinese）.［李必信.程序切片技術(shù)及其應(yīng)用 ［M］.北京：科學(xué)出版社，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程序靜態(tài)切片的方法 ［J］.計(jì)算機(jī)技術(shù)與自動(dòng)化，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）.［王曉華，顧逸東，陳蔚薇，等.面向?qū)ο笾髁髑衅硎痉ǖ谋容^研究 ［J］.計(jì)算機(jī)工程與設(shè)計(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ì)算面向?qū)ο蟪绦蚯衅夹g(shù)研究 ［J］.山東大學(xué)學(xué)報(bào)，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）.［劉坤，姜淑娟，劉蕾.面向?qū)ο蟪绦蛑袑?duì)象關(guān)系的描述方法 ［J］.計(jì)算機(jī)工程與設(shè)計(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）.［易彤.前向切片與后向切片之間關(guān)系的研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44 （12）：42－44.］