3

我一直在閱讀Ira D. Baxter等人的題爲Clone Detection using Abstract Syntax Trees的論文。有從紙張一個段落,我抄錄如下:使用子樹查找類似的代碼段

原則,發現樹克隆 很簡單:每個子樹比較 所有其他子樹平等。在 的實踐中,出現了幾個問題: 未遂克隆檢測,亞克隆 和規模。 ...

在定位未遂 克隆,散列的完整的子樹 失敗,正是因爲良好的散列 功能包括 樹中的所有元素,因此排序髮辮輕微 差異爲不同的桶。我們 通過選擇 人爲壞哈希函數解決了這個問題。此功能必須這樣一種方式,主要性能 人希望找到似是而非的克隆 保留特徵 。臨近想念克隆 通常通過複製和粘貼 創建程序,然後按小 修改。這些修改 通常會生成與 複製的代碼片段關聯的樹形狀的小改動。因此,我們 爭辯說,這種幾乎錯過 克隆往往只有一些不同的小子樹 。基於這個觀察, 忽略小型子樹的散列函數是一個好選擇。 在這裏介紹的實驗 ,我們使用了哈希函數 忽略只有 標識符名稱(葉樹)。 因此,我們的哈希函數把樹 是相似的模標識符 到相同的散列桶的 比較。

我試圖實施本文討論的技術,但我堅持試圖理解這一段(不幸的是在本文開頭)。我明白段落的意思,但作者沒有提到要選擇什麼樣的散列函數或如何實際散列AST。有人可以從實施的角度以一個簡單的例子來解釋嗎?

回答

7

作者自己應該回答的陰影。不是很好的StackOverflow: - ?

散列函數的重點在於您選擇哪一個並不重要,只要它將輸入值平均分配到大量存儲桶中即可。您需要一個可應用於整個樹的散列函數;通常的技術是以任何可能的方式序列化樹(例如,通過按順序訪問樹),然後將散列函數應用於產生的值的流(樹節點)。 (這個想法來自於檢測常見子表達式的編譯器文獻,這是原始CloneDR的靈感)。如果不清楚,您需要花費更多的精力來理解散列函數如何應用於複雜的數據結構。 hashing上的維基百科是一個很好的開始;如果這還不夠,你需要找到一本關於算法的書並進行研究。

您提供給散列函數的內容取決於您。我在本文中提到的一點是,您可以計算忽略AST的標識符樹葉的散列函數,這會導致樹具有相同結構但標識符不同的散列到同一個存儲桶。因此,相似的模標識符的樹很容易匹配,因爲它們發生在相同的散列桶中。

當然,還有更多的整個克隆檢測算法只匹配樹模標識符。您需要擔心匹配參數化的序列(這是本文的重點),報告結果,當然您需要一個高質量的語言解析器來處理任何您喜歡應用的語言。

您可以看到多種不同語言的CloneDR的結果。

+1

SO搜索引擎非常好,或者我非常幸運能夠得到作者的回覆。無論哪種方式,這對我來說都是雙贏的:)你的解釋澄清了我的問題。作爲最終的請求,我會在閱讀完畢後向你的論文推薦任何後續工作嗎? (在開發人員戴帽子之前,您認爲我應該熟悉這方面的任何最先進的工作)。順便說一下,一篇非常棒的論文! – Legend 2011-04-12 02:21:02

+1

@傳奇:克隆檢測識字的好指標可以在http://students.cis.uab.edu/tairasr/clones/literature/找到。自從我的論文發表以來,寫了很多。大部分的論點是a)你如何檢測克隆,b)你如何使它很好地擴展。 Elmar Juergen的論文在縮放方面表現出色,但他放棄參數化可以很好地擴展。我很高興地說,還有其他的樹木檢測論文,但是CloneDR幾乎經受住了時間的考驗。商業版本並不像文章那樣工作,但細節將不會公佈。 – 2011-04-12 02:38:32

+0

@Legend:如果您想聽聽最新的技術,您需要參加五月份在夏威夷舉行的軟件工程國際會議上的軟件克隆研討會。此外,它是一次旅行的絕佳選擇: - }在那裏見! – 2011-04-12 02:47:50

2

如果你知道兩個AST的是要確保他們有相同的哈希值也是「克隆」到你的人的眼睛。

例如,散列每個標識符到一個常數和每一個串到另一個恆定,以避免由可變重命名得到欺騙,而不是實際使用標識符名稱作爲散列的材料部分。

或者使用可交換表達式的交換散列,即,確保a + b和b + a獲得相同的散列值。

hash VariableName = 0x12345678 
hash IntegerConstant = 0xff77ff77 
hash x + y = (hash x) + (hash y) 
hash (x) = (hash x) <<< 13 
hash x * y = (hash x) xor (hash y) 

等等:

涉及變量,整數,運營商和括號算術表達式實施例

+1

+1謝謝你的解釋antti.huima。 – Legend 2011-04-12 02:21:32