深度程序理解視角下代碼搜索研究綜述

汶東震，張 帆，劉海峰，楊 亮，徐 博，林 原，林鴻飛

大連理工大學，遼寧 大連 116024

開發人員在面對日常工作任務時會進行大量搜索行為，從公共資源庫（包含開源社區、論壇博客等）或私有資源庫（內部軟件倉庫、源代碼平臺、社區等）搜索可復用的代碼片段、特定問題的解決方案、算法設計、軟件文檔以及軟件工具等內容，以充分利用已有的軟件開發資源和經驗，在提高軟件復用性的同時，降低開發成本并提升開發效率。Singer等人[1]于1997年針對軟件開發者行為進行跟蹤調研，相關研究結果表明代碼搜索（code search）已成為軟件開發活動中最為常見活動。

而Sadowski等人[2]研究表明，開發者平均每個工作日會構造12條查詢語句對遇到的問題進行搜索。可以看到，代碼搜索在軟件開發活動中重要性日益提高。

Liu等人[3]針對代碼搜索工具相關工作進行了文獻總結。作者從代碼倉庫組織、查詢文本、檢索模型以及評價方法角度，針對代碼搜索工具建立分類體系進行歸類。

代碼搜索從搜索形式可分為，基于自然語言查詢的代碼搜索、基于測試用例的代碼搜索[4]、面向缺陷檢測的代碼搜索、代碼克隆檢測、應用程序接口搜索等[5]。其共同點在于從用戶需求出發，結合信息檢索、程序理解以及機器學習等技術對符合用戶需求的代碼文件或片段進行定位。

其中，基于自然語言查詢的代碼搜索更為貼近開發者實際需求，是目前代碼搜索研究中的熱點。代碼搜索任務和傳統Ad-hoc任務類似，但代碼搜索任務還具有以下難點：

（1）跨模態匹配問題。代碼搜索任務中查詢和文檔分別處于不同模態。其中查詢主要以自然語言形式表達，而目標文檔則是程序語言語法約束的源代碼文本，在計算匹配時需要考慮跨模態語義鴻溝問題。

（2）查詢意圖理解問題。代碼搜索任務中查詢所表達的意圖較為多樣。其包括用戶開發需求、實現特定技術路線的構造性需求以及使用特定接口的API需求等，在構建檢索模型對用戶查詢需求進行理解時需要將軟件工程領域知識與語義理解模型結合。

（3）程序理解問題。代碼搜索模型首先需要建立對檢索對象源代碼片段的理解。其包括代碼基礎語法語義、API功能信息、代碼結構特征以及代碼功能特性等。其中標識符和程序結構是構建程序理解的核心。

可以看到，當前代碼搜索研究主要面臨的問題是如何理解程序功能以及基于程序理解的查詢意圖匹配，即基于程序理解對自然語言和代碼片段進行聯合建模。本文則從程序理解視角出發，針對近期代碼搜索研究進展進行梳理。

1 深度程序理解

1.1 程序理解

程序理解是軟件工程中的關鍵活動，1968年召開的北約軟件工程會議明確了程序理解在軟件工程中的重要性[6]。軟件工程師在進行軟件重用、維護、遷移、逆向工程等任務時都依賴對于程序的理解[7]。

在協作開發場景下，開發者需要了解軟件架構以及接口設計模式，進而對軟件功能進行開發和實現；而在軟件維護中，維護者需要了解已有項目中的主要功能和實現方法，以此為基礎才能進一步進行缺陷檢查以及修復。“理解”本質上是通過學習的手段，建立從理解的對象（如文本、源代碼等）所屬的概念域，到理解的主體（人、模型）所熟悉的概念域的（概念）映射[6]。

程序理解的主體是整個軟件系統或者部分軟件系統，旨在研究其如何運行[8]。

程序理解任務包括構建從代碼模型到應用領域問題各抽象層次上的模型[9]；利用領域知識理解軟件，構建軟件制品與使用場景之間的認知模型[10]；通過閱讀源代碼判斷其作用以及與其他構件之間的關系等。其最終目的在于支撐軟件維護、演化和再工程。

按照實現方式分類，程序理解可分為基于分析和基于學習兩種主要方法。基于分析的程序理解方法十分依賴分析者的個人知識和經驗，構建程序理解模型等價于手動構造相關特征集。這類方法往往和具體軟件系統耦合，相關經驗規則較難遷移到其他項目中。同時，隨著軟件規模的增大，分析所需資源會隨之加升高，效率會隨之降低。

1.2 深度程序理解

互聯網上大量開源代碼的出現為基于學習的程序理解方法提供了充分的數據保證[11]。而近期Hindle等人[12]和Allmanis等人[13]研究表明，程序源代碼具有和自然語言相似的特性，這種自然性（naturalness）為結合統計模型尤其是深度模型進行源代碼分析理解提供了理論依據。Tu等人[14]針對源代碼局部性（localness）對統計建模的影響進行了深入分析。Chen等人[15]則對深度源代碼建模中的進展和挑戰進行了詳細梳理。

基于深度學習的程序理解框架如圖1所示。其主要包含兩個階段，首先根據任務不同構建源代碼文本的對應表示形式，在此基礎上通過深度模型構建源代碼特征向量并應用于具體任務中。

圖1 基于深度神經網絡的代碼理解框架Fig.1 Framework of source code comprehension on basis of deep neural network model

具體而言，程序源代碼首先會根據任務被轉換為字符序列（char sequence）、詞序列（token sequence）、API序列（API sequence）、抽象語法樹（abstract syntax tree，AST）、函數調用圖（function call graph，FCP）以及控制流圖（control flow graph）等多種形式。

在此基礎上，源代碼不同表示通過神經網絡轉換為特征向量后被用于具體任務。

源代碼不同表示形式特點以及適用任務如表1所示。基于詞的表示[16]的程序建模和自然語言理解模型建模類似，實現簡單易于遷移。但由于開發者自定義標識符情況的存在[17-18]，基于詞的代碼建模方法往往會受到詞表外詞（out of vocabulary，OOV）問題困擾。基于字符序列的建模能夠解決OOV問題，但是基于字符符號的表示方式難以學習到詞義，因此在表示能力方面較弱。代碼中包含的API往往設計規范，同時用詞較為固定，因此針對API序列進行學習在代碼搜索和摘要任務上都有著良好的效果[19]。

表1 代碼理解中間形式Table 1 Intermediate representation for source code comprehension

可以看到，單純使用詞序列作為源代碼的表示形式存在表示能力不足的問題，因此結合多模態方法[20]建模源代碼逐漸走入研究者的視野。基于語法樹的代碼建模能夠改善序列建模中對于程序結構學習不充分的問題。但現有研究大多采用序列采樣的方式[21-22]從語法樹中獲取節點序列進行表示，對于樹結構的利用尚不充分。Wang等人[23]提出一種改進方法用于將語法樹信息融合代碼表示方法，語法樹作為代碼序列的平行語料，在與源代碼序列對齊的基礎上與自然語言片段進行建模，提高了源代碼搜索任務效果。

而圖神經網絡在自然語言文本結構上的建模能力也激發了其在代碼建模上的探索[24]。源代碼數據相比于自然語言文本更易構建圖表示形式，因此結合圖結構的程序理解模型有著較好的前景[25]。

可以看到，深度代碼理解研究是眾多軟件工程任務的基礎，不同表示形式所帶來的特征向量能夠為代碼搜索任務提供充足的特征信息。下一章則從深度程序理解視角針對代碼搜索任務進行定義。

2 代碼搜索與文檔搜索

代碼搜索是信息檢索和程序理解的交叉研究，與文檔搜索技術類似，二者在諸如查詢理解、文檔索引、文檔排序等多種技術中有著較多共性。但從搜索對象來看，由于源代碼自身特性，對于代碼的理解包括兩個方面，即代碼的使用場景以及代碼算法原理。

以“冒泡排序”為查詢，文檔搜索和代碼搜索的結果示例如表2所示。可以看到，文檔搜索結果中往往包含原始關鍵詞以及圍繞關鍵詞展開的一系列概念介紹和組合。而在代碼搜索結果中，則重點關注這一算法的具體實現以及代碼的正確性。

表2 代碼搜索與文檔搜索異同Table 2 Differences between code search and documents search

二者的核心差異在于如何實現文檔（代碼）的理解。同時，基于源代碼功能特點、應用場景、功能實現方式等特性將代碼與用戶意圖匹配，是兩種搜索方式最大差異。

從形式化角度看，此處記Q為查詢文本，C為源代碼片段。如公式（1）所示，RQ(Q)為查詢文本的表示模型，將用戶查詢轉化為向量形式的中間表示。

相應的如公式（2）所示，RC(C)為程序理解模型，其將輸入的代碼片段轉化為特征向量，進而對代碼結構和語義進行表示。

查詢文本和代碼片段分別通過RQ和RC被表示為中間形式φ，從這兩種特征向量出發計算二者匹配性質。如公式（3）所示，M(φQ,φC)表示相關度計算模型，結合向量距離等方式計算查詢和代碼片段匹配程度。

相關性分數ψ越大表明當前代碼片段樣本與用戶意圖匹配程度越高。如公式（4）所示，假定有Ca和Cb兩個代碼片段，Oa和Ob分別表示文檔在結果列表中的順序。則代碼片段Ca和Cb與查詢文本Q之間的相關性分數大小ψa和ψb關系決定排序位置，相關性分數越大，則在結果列表中的位置越靠前。

可以看到，代碼搜索任務難點在于建立對源代碼片段的理解，在此基礎上實現用戶查詢意圖和代碼片段功能語義之間的匹配。

傳統的基于信息檢索模型的方法中，通常將代碼視為普通的自然語言文檔，在簡單分詞、去除停用詞以及詞干化[26]處理之后，結合自然語言模型對用戶查詢和代碼文檔進行向量化，最后計算二者的相似性。

Lucia等人[27]提出基于文本正規化的方法進行代碼和文檔之間的溯源。Hill等人[28]將方法名信息引入檢索模型中增強代碼檢索結果表現。Lv等人[29]則結合API理解改進基于信息檢索的代碼搜索系統，其實現簡單明了，是常用的研究基線。

Arwan等人[30]將主題模型和Tfidf模型[31]結合引入源代碼和查詢表示，提升了查詢和代碼匹配的準確性。Bajracharya等人[32]重新歸類了代碼搜索特征，并按照語義類別不同重新分配了特征權重，提高了檢索效果。Niu等人[33]提出結合排序學習的代碼搜索方法。Jiang等人[34]在此基礎上對代碼搜索特征體系進一步擴充，并將其與排序學習結合。

深度代碼搜索研究則結合深度程序理解研究構建檢索模型。Jiang等人[35]率先研究了源代碼和自然語言之間的語義鴻溝問題。如圖2所示，查詢文本和代碼片段通過自然語言模型和程序理解模型獲得特征表示。獲取特征向量后，通過深度模型構建匹配關系。

圖2 深度代碼搜索研究框架Fig.2 Research framework of deep code search

自然語言模型部分，詞表示方面，常用word2vector模型[35]、glove模型[36]以及fasttext模型[37]進行表示；上下文表示方面常用Elmo模型[38]、Bert模型[39]等直接對句子建模獲取表示。

匹配模型部分，Mitra等人[40]和Xu等人[41]研究了將排序學習訓練目標與深度模型相結合，即神經信息檢索模型。Wang等人[42]針對神經檢索模型中的損失函數進行了總結，對比學習排序（contrastive learning）、三元排序（triplet loss）等方法逐漸受到關注。Wang等人[43]則結合強化學習改進查詢理解，進而提高檢索效果。

程序表示模型部分，Allamanis等人[44]進行了較為詳細的總結和歸類。早期研究將代碼片段看作普通文本，結合自然語言建模方法，對詞序列[45]和API序列進行建模；隨后一些工作逐漸重視代碼結構特性，提出結合抽象語法樹[46-48]的代碼結構建模方法；而源代碼較強的圖結構使得近期結合圖神經網絡源代碼建模研究正逐步受到重視。

3 深度代碼搜索

本章從深度程序理解模型角度對當前代碼搜索研究進展進行梳理。

如表3所示，在論文選擇依據方面，本文使用code search、code retrieval作為關鍵字進行搜索，涵蓋軟件工程、自然語言處理、神經計算等領域。最終，在相關會議、期刊以及預發表平臺Arxiv上收集到與深度代碼搜索相關的研究共40余篇論文。在此基礎上，針對本文剔除了案例研究型論文、系統設計型論文以及沒有明確評價指標的研究論文，最終留下27篇進行匯總。

表3 深度代碼搜索模型對比Table 3 Comparison between deep code search models

分析維度包括源代碼表示形式、深度模型結構、模型評估所使用數據集以及評價指標四個部分。源代碼表示形式從深度程序理解視角出發規劃，主要包括詞序列表示、API序列表示、樹結構（主要是抽象語法樹）和圖結構（函數調用圖、語法樹子圖等）。深度模型結構方面包括卷積網絡（CNN）、循環網絡（LSTM）、Transformer、注意力機制等。

Gu等人[19]對深度代碼搜索進行了早期探索，其首先對API的搜索和生成進行了研究，并在此基礎上提出了深度代碼搜索模型CodeNN，奠定了深度代碼搜索模型的基礎框架。而Li等人[16]則結合詞向量以無監督方式對源代碼進行建模，代碼文本被處理為詞序列后通過詞向量構建篇章表示并在此基礎上實現匹配檢索。Chen等人[15]在此基礎上進一步詳細研究了自然語言和API之間的語義鴻溝問題。而Liu等人[3]則結合Li等人方法為代碼搜索工具增添模糊查詢能力。

從Gu等人工作出發，一系列嘗試將不同深度模型架構應用于代碼搜索任務中。Li等人[50]初步嘗試了將注意力機制引入代碼匹配計算中。Wang等人[53]則使用CNN構造多層注意力網絡捕獲源代碼深度語義。Sinha等人[54]則將孿生網絡應用于代碼搜索任務中以增強查詢和代碼之間的匹配能力。Ling等人[22]將關鍵詞匹配和句法模式學習相分離，提出在新的代碼庫上泛化性更強的自適應深度代碼搜索模型。Zhao等人[61]則將對抗學習應用于訓練過程中，提升了代碼與查詢文本的匹配度。

單純序列建模方法難以利用源代碼的結構信息，Haldar等人[58]和Sun等人[56]使用抽象語法樹來信息增強代碼表示能力。Gu等人[62]在此基礎上結合語法樹建模源代碼中的語義依賴。Fang等人[66]則首次將自注意力網絡用于代碼搜索，Wang等人[23]在此基礎上結合自注意力網絡對源代碼序列信息和結構信息進行統一建模。

圖是源代碼中普遍存在的結構，Ling等人[52]從語法樹出發構建子圖以對代碼中不同節點之間關系進行建模。之后使用關系圖卷積網絡建模對查詢和代碼特征向量進行相互增強，最后提高檢索效果。Wan等人[45]則將源代碼不同表示方法視為多模態任務，將代碼序列、語法樹以及圖三者融合對代碼進行語義建模表示。最終結果取得了SOTA效果，證實融合序列和結構語義在代碼理解任務上具有實際效果。

而在預訓練模型方面，隨著Bert[67]等基于Transformer預訓練模型在自然語言處理領域各項任務上取得SOTA結果。部分研究者也開始關注源代碼的預訓練效果。Feng等人[59]結合對比學習訓練范式，在代碼文本上進行Bert模型訓練。Kanade等人[68]則聚焦于Python代碼進行了Bert模型訓練，并提出CuBert模型。Guo等人[25]將代碼結構加入與訓練過程中，提出GraphCodeBert，結合圖結構增強了Transformer在預訓練代碼時的表達能力。而Ishtiaq等人[69]則在CodeBert等模型基礎上通過代碼搜索任務對與訓練模型在具體代碼理解任務上的效果進行了實際驗證。結果表明，基于Transformer的預訓練語言模型在代碼理解任務上同樣具備良好效果。

4 數據集和評估方法

4.1 評價指標

代碼搜索任務評價指標和信息檢索任務一致，主要考慮結果的兩個方面，即檢索結果的相關性以及相關結果的排名次序。

精確度P@K計算方法如公式（5）所示，衡量檢索結果中相關文檔數量占檢索結果的比重，其中K表示一次檢索過程中得到的文檔數目。

召回率R@K計算方法如公式（6）所示，其主要衡量檢索結果中相關文檔數目占總體相關文檔的比重，K表示一次檢索中得到的文檔數目。

可以看到，精確度和召回率指標能夠衡量前K個檢索結果中相關文檔比率的情況。

平均倒數排名（mean reciprocal rank，MRR）引入相關文檔在結果中順序進行結果評價。如公式（7）所示Ranki表示相關文檔在檢索結果中的次序。

如公式（8）所示，平均精確度（average precision）將精確度和文檔次序相結合。其中m表示當前檢索結果中相關文檔總數，N表示檢索結果總數，P(k)對應為本次檢索結果中前k個結果的精確度（即P@K），rel(k)為一個指示函數，當第k個文檔相關時為1否則為0。

MAP指標則將API在所有查詢Q上計算了平均。

折扣累積增益（DCG）則將相關性等級引入評價。如公式（9）所示。rel(k)衡量第k個文檔的相似性分數，如1～4整數階段式分數，分母處取當前次序相關的對數作為折扣因子。

而歸一化折扣累計增益NDCG指標則使用最優排列結果下的DCG分數對其歸一化。除以上指標外，還有Frank評價描述在檢索列表中首個相關結果在列表中次序。

4.2 評估數據集

本文針對2016年至今的代碼搜索研究工作進行梳理，對其中用于評估模型效果的數據集進行了總結。選擇標準方面，數據集必須公開可用，同時至少有兩篇以上工作都使用該數據集對模型進行評價。

代碼搜索常用評估數據集，如表4所示。其中共涉及七篇工作。數據集構造方面，目前工作主要通過自動化抽取方式構建大規模代碼片段——自然語言文本組合作為訓練數據。在自動標注基礎上結合負采樣方法構建驗證數據。模型評估使用常見代碼搜索問題作為查詢，在構建的代碼庫上進行精細標注。

表4 代碼搜索任務評估數據集Table 4 Evaluation datasets for code search task

按照數據標注劃分，其中CSN和ROSF數據嚴格進行了相關性等級標注；DCS、NCS和CosBench首先篩選了自然語言查詢，之后在代碼庫上標注了相關代碼片段。

按照評價指標劃分，CNS和ROSF可以使用NDCG進行評價；StaQC主要結合文本分類指標進行評價；其余數據集大多采用MRR、P@K以及Frank指標進行評估。

按照編程語言劃分，DCS、NCS、ROSF、CosBench數據集主要包含Java編程語言代碼數據（涵蓋安卓）。CoNaLa數據則結合Stackoverflow社區數據挖掘以及人工標注，構建了含有Java和Python編程語言的數據。StaQC數據集主要包含Python和SQL兩種標注結果。CodeSearchNet數據集則包含Java、Python、Php、Ruby、Go、Javascript六種編程語言，覆蓋編程語言范圍最廣。

按照任務劃分，StaQC將代碼搜索任務轉換為相關文檔分類問題，因此可結合文本分類方法進行研究；CSN和ROSF數據標注等級信息充分，可結合排序學習方法進行研究；其余數據集中包含的代碼片段——自然語言組合可被用于代碼摘要任務以及基于摘要技術的代碼搜索研究。

4.3 結果對比

本節在數據集和評價指標介紹基礎上，從模型效果角度對近期代碼搜索實驗工作進行梳理，重點側重基于深度模型的代碼搜索方法。評價指標則涵蓋Recall、Precision、MRR、MAP、NDCG。統計時，提出數據集的相關文獻Baseline相應在文獻一欄中加粗注明。部分數據集如StaQC數據集提出時使用分類指標作Baseline，因此此處未注明。

具體結果如表5所示，本文按照數據集、相關文獻以及評價指標對結果進行了組織。從數據集角度來看，StaQC數據集應用最為廣泛，相對影響力較大。DCS數據集上的實驗相對更為充分，不同文獻基本覆蓋了所有的評價指標。從評價指標角度看，MRR指標是目前代碼搜索模型驗證時的常用指標。而從編程語言角度來看，目前研究較多的編程語言為Java。

表5 代碼搜索模型結果對比Table 5 Comparison of code search model results

5 未來研究展望

代碼搜索研究正逐漸受到學界重視，本文從深度程序理解視角出發對代碼搜索近期進展進行了梳理，而未來還可以從以下方面對該問題進行研究：

（1）穩定可復現的評價方法。當前多數研究中未開放評估數據集，而開放的數據集中存在著標注不一致等問題。Liu等人[73]研究表明數據集和開源代碼問題使得深度模型的結果可復現性存在諸多問題。未來研究中應嘗試構建一致明確的數據集和評價方法以及平臺，以促進代碼搜索研究。

（2）深入研究程序表示技術。源代碼的理解和建模是代碼搜索任務的關鍵。大多數模型采用序列建模方式對源代碼進行特征抽取表示，少數工作將樹、圖結構數據簡單進行了拼接融合以引入代碼結構信息。在未來研究中可以嘗試結合圖神經網絡對代碼進行更加深入的結構建模。

（3）多模態源代碼建模方法。源代碼由標識符和編程語言特定的關鍵字組成。其中編程語言特定的關鍵字提供了代碼的結構信息，而代碼標識符則提供了更為充分的自然語言信息。未來研究中可以將兩種模態數據相結合，對代碼的結構語義以及自然語義進行統一建模，進而用于代碼搜索任務。

（4）代碼搜索研究應用問題。當前代碼搜索研究重點關注基于深度代碼建模方法的重排序問題。而代碼搜索工具研究則更加關注代碼數據的采集、清洗和管理。代碼搜索研究中一些數據處理方法和效果優化方法與實際應用系統之間并不適用。未來研究中可以從實際應用目的出發設計搜索模型。

6 總結

本文首先以深度程序理解視角切入對代碼搜索任務進行了定義。其次，以此為基礎總結得出深度代碼搜索兩種研究范式，并進行梳理相關研究成果。同時，本文總結整理了代碼搜索任務常見的評估方法。最后結合本文研究結果，對未來研究進行了展望。