高麗萍,游書偉

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)2(復(fù)旦大學(xué) 上海數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室,上海 200093)

1 引 言

移近年來互聯(lián)網(wǎng)行業(yè)的快速發(fā)展,帶來了軟件行業(yè)的繁榮,對(duì)復(fù)雜軟件的要求日益增加.軟件的規(guī)模和復(fù)雜度不斷提高,增加了軟件制作的難度,使得開發(fā)工程師們不得不或是更愿意對(duì)軟件項(xiàng)目實(shí)施協(xié)同工作.協(xié)同編程環(huán)境能夠大大提高開發(fā)人員的工作效率,降低工作難度,縮短研發(fā)周期.將計(jì)算機(jī)支持的協(xié)同工作與編程環(huán)境結(jié)合是當(dāng)下的熱門研究領(lǐng)域之一[1],過去的幾十年,已經(jīng)有許多的協(xié)同軟件研究者致力于協(xié)同編程軟件或是協(xié)同編程方法的研究上,研發(fā)了一系列的協(xié)同開發(fā)工具[1,15].

傳統(tǒng)的協(xié)同編程,往往指的是各個(gè)開發(fā)人員獨(dú)立的工作于非實(shí)時(shí)的開發(fā)環(huán)境,再通過媒介工具上傳代碼、同步代碼,實(shí)現(xiàn)協(xié)同工作.而實(shí)時(shí)協(xié)同的編程環(huán)境支持多個(gè)用戶在任意時(shí)間任何地點(diǎn)并發(fā)的編輯共享的代碼文檔,不再需要通過第三方工具同步源代碼文檔.實(shí)時(shí)的協(xié)同編程環(huán)境須滿足實(shí)時(shí),分布,無約束3個(gè)基本條件.為了滿足上述3個(gè)條件,研究人員通常采用復(fù)制式結(jié)構(gòu),每個(gè)協(xié)同站點(diǎn)將共享文檔復(fù)制到本地工作區(qū)域.實(shí)時(shí)協(xié)同文本編輯環(huán)境中共享的文檔通過OT(Operation transformation)[2,3,8]技術(shù)維護(hù)各個(gè)協(xié)同的站點(diǎn)的文本內(nèi)容一致(語法一致).實(shí)時(shí)協(xié)同編程環(huán)境是特殊的協(xié)同文本編輯環(huán)境,該環(huán)境不僅要求維護(hù)文本內(nèi)容的一致性,且在保證內(nèi)容一致性的同時(shí),需要保證文本內(nèi)容的語義正確性.文本內(nèi)容語義錯(cuò)誤通常是因?yàn)椴l(fā)的編輯操作導(dǎo)致的語義不一致.語義一致性是Sun等提出的CCI模型[8]中的一條,即意愿維護(hù),只有在所有站點(diǎn)的收斂性和意愿一致性都滿足時(shí),CSCW系統(tǒng)才算是正確的計(jì)算機(jī)支持的協(xié)同系統(tǒng).傳統(tǒng)的語義維護(hù)主要針對(duì)文本編輯器中基于字符操作的一致性,在這種編輯環(huán)境下,字符與字符之間雖然具有前后繼關(guān)系,但在屬性上沒有依賴關(guān)系[9].在編程環(huán)境下,操作具有更豐富和更廣泛的語義信息,且字符與字符之間可能存在著大量的依賴關(guān)系,由于一些操作在執(zhí)行過程中需要依賴于其它操作對(duì)象,操作的語義很有可能由于其它站點(diǎn)上的并發(fā)操作而受到影響,且協(xié)同編程系統(tǒng)中尤為強(qiáng)調(diào)語義一致性.只維護(hù)語法一致性,而忽略了語義一致性,在協(xié)同編程中可能產(chǎn)生難以維護(hù),或者較難發(fā)現(xiàn)的錯(cuò)誤,增加協(xié)同編程環(huán)境中代碼正確性的維護(hù)難度.

本文針對(duì)實(shí)時(shí)協(xié)同編程環(huán)境語義沖突消解方法展開研究.本文組織結(jié)構(gòu)如下:第2部分對(duì)研究背景與相關(guān)工作進(jìn)行介紹;第3部介紹了協(xié)同編程環(huán)境中的語義沖突場(chǎng)景、動(dòng)態(tài)依賴關(guān)系及不完整的編輯操作產(chǎn)生的編輯錯(cuò)誤;第4部分設(shè)計(jì)了實(shí)時(shí)協(xié)同編程環(huán)境的語義沖突消解算法ACAS并進(jìn)行了實(shí)例分析.第5部分,為了驗(yàn)證算法可行性,在Windows平臺(tái)下基于ACAS算法開發(fā)了支持語義沖突消解的實(shí)時(shí)協(xié)同編程原型系統(tǒng)CoCode.第6部分,對(duì)設(shè)計(jì)的控制算法和相關(guān)函數(shù)進(jìn)行了模擬仿真實(shí)驗(yàn)并給出實(shí)驗(yàn)分析結(jié)果.第7部分為全文內(nèi)容的總結(jié)及對(duì)未來工作的展望.

2 相關(guān)工作

沖突消解是實(shí)時(shí)協(xié)同編輯系統(tǒng)中重要的研究課題,是保證系統(tǒng)正確性和可用性的關(guān)鍵性技術(shù).針對(duì)實(shí)時(shí)協(xié)同編輯系統(tǒng)的沖突問題解決方法主要分為兩大類:沖突消解方法和沖突避免方法.沖突消解方法允許協(xié)同編輯過程中發(fā)生沖突,一旦有沖突發(fā)生則使用相應(yīng)的策略來消除沖突,從而保證共享文檔的一致性.近些年,沖突消解方法研究中最常用的一致性維護(hù)技術(shù)主要分為兩大類:基于操作轉(zhuǎn)換OT[2,3,8]技術(shù)和基于地址轉(zhuǎn)換(Address Space Transfor-mation,AST)[4]技術(shù),包括Ellis和Gibbs在文獻(xiàn)[2]中提出的dOPT算法,Sun和Ellis在文獻(xiàn)[2]提出的GOT和GOTO算法,Sun在文獻(xiàn)[3]提出的COT算法以及Gu等人在文獻(xiàn)[4]中提出的AST算法等.沖突避免方法是指在沖突發(fā)生前避免沖突發(fā)生,該方法一般采用加鎖的方式來避免沖突,即當(dāng)用戶對(duì)某對(duì)象進(jìn)行操作時(shí)需要先申請(qǐng)加鎖,只有申請(qǐng)成功的用戶才能操作該對(duì)象.FAN和SUN在文獻(xiàn)[1]中提出的DAL(Dedendency-based Automatic Locking)技術(shù),以動(dòng)態(tài)加鎖的方式實(shí)現(xiàn)了實(shí)時(shí)協(xié)同編程環(huán)境的語義沖突避免,并采用Shared-Locking[6]的方法處理并發(fā)加鎖的問題.該方法雖有效的避免了語義沖突的發(fā)生,但在一定程度上限制了協(xié)同編程的效率,且頻繁的加鎖與釋放鎖會(huì)加大對(duì)系統(tǒng)資源的開銷.

傳統(tǒng)的鎖方法對(duì)協(xié)同編程的限制較大,在避免語義沖突的同時(shí)限制了對(duì)其它代碼段的編輯.以并不是所有的并發(fā)操作都導(dǎo)致語義沖突為出發(fā)點(diǎn),本文針對(duì)實(shí)時(shí)協(xié)同編程環(huán)境的語義沖突、不完整的編輯帶來編輯錯(cuò)誤問題以及代碼文檔依賴圖動(dòng)態(tài)依賴關(guān)系,在SUN,FAN等人的研究基礎(chǔ)上,設(shè)計(jì)了協(xié)同編程環(huán)境下基于CAS并發(fā)處理思想的語義沖突消解方法ACAS(Automatic Compare And Swap).CAS(Compare And Swap)方法[5]是一種較為新穎的并發(fā)沖突處理技術(shù),其核心思想是通過對(duì)目標(biāo)對(duì)象設(shè)定期望值,若操作的目標(biāo)對(duì)象的期望值由于某些因素發(fā)生變化,則操作不可執(zhí)行.反之,操作可執(zhí)行.CAS方法[5]雖用于處理線程間資源同步問題,但用于語義沖突消解上同樣適用.

3 實(shí)時(shí)協(xié)同編程環(huán)境下的語義沖突消解方法

實(shí)時(shí)協(xié)同編程環(huán)境的編輯需要遵循語義一致性.語義一致性是指:共享文檔的協(xié)同編輯要符合編程語言規(guī)則,并保證解決問題的邏輯方面的正確性.在協(xié)同編程的過程中,如果存在多個(gè)用戶并發(fā)的編輯相同代碼域或是存在依賴關(guān)系的不同代碼域,都可能導(dǎo)致語義沖突的發(fā)生.協(xié)同編程環(huán)境中語義沖突的具體場(chǎng)景及相關(guān)定義在文獻(xiàn)[1]中進(jìn)行了詳細(xì)描述.為了更好的說明語義沖突,文中也進(jìn)行一些相關(guān)論述.

3.1 基本定義

獨(dú)立的代碼域是協(xié)同編程環(huán)境最基本的元素,獨(dú)立的代碼域及其相關(guān)的定義介紹如下:

定義1.基礎(chǔ)域和開放域[1].

1)基礎(chǔ)域(Basic Area,BA):一系列源代碼組成的語義有意義且獨(dú)立的代碼域;

2)開放域(Open Area,OA):基礎(chǔ)域之外的所有代碼域;

定義2.依賴關(guān)系.

基礎(chǔ)域A依賴于基礎(chǔ)域B,表示為A→B;如存在A→B,B→C,則A→C;本文中將A→B,B→C稱為直接依賴關(guān)系,A→C稱為間接依賴關(guān)系.

定義3.依賴圖.

1)每個(gè)基礎(chǔ)域?qū)?yīng)一個(gè)依賴圖結(jié)點(diǎn).

2)Node→Node,表示依賴圖之間的依賴關(guān)系.

3)依賴圖結(jié)點(diǎn)之間的依賴關(guān)系與其對(duì)應(yīng)的基礎(chǔ)域之間的依賴關(guān)系一致.基礎(chǔ)域之間的依賴關(guān)系通過依賴派生機(jī)制實(shí)時(shí)分析,建立或取消基礎(chǔ)域之間的依賴關(guān)系[1].

4)依賴圖中記錄的信息為對(duì)應(yīng)基礎(chǔ)域代碼文本內(nèi)容.

如圖1所示,圖中包含了節(jié)點(diǎn)d、c,由于節(jié)點(diǎn)d中對(duì)應(yīng)的基礎(chǔ)域中的代碼為函數(shù)List,該函數(shù)引用了節(jié)點(diǎn)c中的變量maxSize,故節(jié)點(diǎn)d,c存在依賴關(guān)系且d→c,節(jié)點(diǎn)d直接依賴于節(jié)點(diǎn)c.

文中將G(Graph)表示為一個(gè)依賴圖,G=(N),N為依賴圖中的所有結(jié)點(diǎn),表示為N={ N0,N1,…,Nn}.N0為依賴圖中的一個(gè)結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)中記錄的信息包含:結(jié)點(diǎn)id(Id),結(jié)點(diǎn)直接依賴的結(jié)點(diǎn)集合(RooNode,RN),以及對(duì)應(yīng)基礎(chǔ)域的代碼文本內(nèi)容(NodeContext,NC),表示為No=,故圖1中的結(jié)點(diǎn)d可以表為d=.

3.2 基本的操作類型

關(guān)于代碼的編輯操作:

1)insert():向基礎(chǔ)域或者開放域插入新的字符.例如:insert(1,1,x)表示在第1行的位置1上插入字符x.

2)delete():刪除基礎(chǔ)域中的字符.例如:delete(1,1,6)表示刪除第1行位置1之后的6個(gè)字符.

以代碼域?yàn)閱挝粚?duì)象的編輯操作:

1)createArea():創(chuàng)建一個(gè)新的基礎(chǔ)域,即在開放域中插入新的字符;

2)deleteArea():刪除某個(gè)基礎(chǔ)域,即刪除某個(gè)基礎(chǔ)域中的所有字符;

3)revert():將基礎(chǔ)域恢復(fù)到某個(gè)代碼域版本;

4)save():保存基礎(chǔ)域中的代碼內(nèi)容并生成相應(yīng)代碼域版本;

實(shí)際上,createArea和deleteArea只是特殊的insert 和delete操作,revert和save操作的作用將在后文中做進(jìn)一步的討論.

定義4.依賴沖突.

1)兼容關(guān)系:存在兩個(gè)編輯操作O1和O2,若O1與O2是兼容關(guān)系,表示為O1⊙O2,iff 1)O1‖O2;2)O1,O2作用于無依賴關(guān)系的不同基礎(chǔ)域.

2)排斥關(guān)系:存在兩個(gè)編輯操作O1和O2,若O1與O2是沖突關(guān)系,表示為O1?O2,iff 1)O1‖O2;2)O1,O2作用于相同或存在依賴關(guān)系的基礎(chǔ)域.

兼容的并發(fā)操作,可通過OT技術(shù)實(shí)現(xiàn)一致性維護(hù).本文主要研究語義沖突消解,由于兼容的并發(fā)操作不引起語義沖突,故不對(duì)這種情況進(jìn)行討論.若并發(fā)的操作為排斥關(guān)系,由于相互排斥的操作難以進(jìn)行操作意愿融合,故只有一個(gè)操作的編輯效果將會(huì)被保留.

3.3 協(xié)同編程環(huán)境中語義沖突的一般條件

協(xié)同編程環(huán)境中語義沖突可能發(fā)生的幾種情況.

1)協(xié)同編程人員對(duì)相同的代碼域的并發(fā)工作.

2)協(xié)同編程人員對(duì)存在依賴關(guān)系的代碼域的并發(fā)工作.

3)協(xié)同編程人員的工作導(dǎo)致依賴圖結(jié)構(gòu)發(fā)生改變.

3.4 協(xié)同編程環(huán)境中語義沖突的場(chǎng)景分析

圖2是一個(gè)未完成的c++類,該類用于實(shí)現(xiàn)線性表.圖左側(cè)為源代碼,圖右側(cè)是源代碼中基礎(chǔ)域?qū)?yīng)的依賴圖結(jié)點(diǎn).每個(gè)基礎(chǔ)域(BA)對(duì)應(yīng)一個(gè)依賴圖結(jié)點(diǎn),依賴圖之間的依賴關(guān)系對(duì)應(yīng)基礎(chǔ)域中的依賴關(guān)系.圖中空白的區(qū)域代表開放域(OA).當(dāng)協(xié)同人員工作于這個(gè)類中時(shí)將可能發(fā)生以下幾種沖突:

情況1.并發(fā)的編輯相同的基礎(chǔ)域?qū)е碌恼Z義沖突

如圖2的(a)部分所示,依賴圖結(jié)點(diǎn)G為L(zhǎng)ist類中的方法Delete,在相同時(shí)間段,存在兩個(gè)用戶u0,u1并發(fā)的編輯結(jié)點(diǎn)b對(duì)應(yīng)的基礎(chǔ)域.

1)在站點(diǎn)0上,用戶u0將Delete函數(shù)的返回值類型由int類型修改為void類型.

2)在站點(diǎn)1上,用戶u1在Delete函數(shù)的函數(shù)體中添加了 return data[location].

首先,在各自工作的站點(diǎn)上,兩個(gè)用戶對(duì)結(jié)點(diǎn)b的編輯并未引起錯(cuò)誤,當(dāng)兩個(gè)站點(diǎn)上的操作發(fā)送到對(duì)端,通過OT技術(shù)進(jìn)行一致性維護(hù)處理后,得到的結(jié)果雖然滿足了文本內(nèi)容的一致性,卻導(dǎo)致了編程語言規(guī)則錯(cuò)誤.經(jīng)過用戶u0修改后的Delete方法不能有返回值,即通過OT技術(shù)處理后得到的代碼內(nèi)容違背了用戶的編輯意愿,語義沖突發(fā)生.

圖1 List類的依賴關(guān)系圖Fig.1 Dependency graph of class list

情況2.并發(fā)的編輯存在相互依賴的基礎(chǔ)域?qū)е抡Z義沖突.如圖2的(b)部分所示,在某一時(shí)刻,用戶u0與用戶u1并發(fā)的工作于結(jié)點(diǎn)a,與結(jié)點(diǎn)d且結(jié)點(diǎn)d依賴于結(jié)點(diǎn)a.

圖2 邏輯錯(cuò)誤場(chǎng)景Fig.2 Logical error situation

1)在站點(diǎn)0上,用戶u0修改變量data的數(shù)據(jù)類型,將data修改為int型的數(shù)組容器.

2)在站點(diǎn)1上,用戶u1為指針變量data開辟內(nèi)存空間

在各自的站點(diǎn)上,兩位用戶的編輯并未引起錯(cuò)誤,但當(dāng)用戶的編程操作發(fā)送到對(duì)端時(shí),語義沖突發(fā)生.沖突的原因在于用戶u1對(duì)結(jié)點(diǎn)b的編輯基于結(jié)點(diǎn)a的代碼,而用戶u0修改了結(jié)點(diǎn)a中的代碼.在代碼同步時(shí)無法兼容兩個(gè)用戶的編輯操作從而導(dǎo)致語義沖突.

上述兩個(gè)案例中的語義沖突都導(dǎo)致了編程語言規(guī)則錯(cuò)誤,錯(cuò)誤能由編譯器捕捉,錯(cuò)誤容易發(fā)現(xiàn).在下文案例中,當(dāng)兩個(gè)站點(diǎn)的編輯操作廣播到對(duì)端時(shí),雖然未發(fā)生編程語言規(guī)則錯(cuò)誤,卻引起了編程邏輯錯(cuò)誤,是一種較為特殊的語義沖突場(chǎng)景.如圖3所示:

1)在站點(diǎn)0上,用戶u0增加了一行代碼邏輯location-=1.對(duì)變量location的值減1.

2)在站點(diǎn)1上,用戶u1增加了一行代碼location++,對(duì)變量location的值加1.

圖3 邏輯錯(cuò)誤場(chǎng)景Fig.3 Logical error situation

用戶u0實(shí)現(xiàn)Get方法返回在location-1位置上的數(shù)據(jù),而用戶u1的編輯操作卻實(shí)現(xiàn)了獲得locaiton+1位置上的數(shù)據(jù).并發(fā)的編輯操作到達(dá)對(duì)端站點(diǎn)時(shí),并未導(dǎo)致編程語言錯(cuò)誤.但是由于用于對(duì)相同的變量的編輯,產(chǎn)生編輯意愿重疊,從而實(shí)際實(shí)現(xiàn)的編程效果并未遵循用戶的編輯意愿,導(dǎo)致了編程語言邏輯錯(cuò)誤,語義沖突發(fā)生.

以上列舉的3個(gè)案例是實(shí)時(shí)協(xié)同編程環(huán)境中比較有代表性的案例,語義沖突的情況還有很多,本文不在一一列舉,情況3導(dǎo)致的語義沖突在3.5節(jié)中進(jìn)行相關(guān)分析.

3.5 依賴圖的動(dòng)態(tài)變化分析

由于代碼文檔的高復(fù)雜性及依賴圖結(jié)構(gòu)的動(dòng)態(tài)變化,極大的增加語義一致性的維護(hù)難度.對(duì)于基礎(chǔ)域的編輯操作可能產(chǎn)生新的依賴關(guān)系,即調(diào)用新的方法,或是引用了新的參數(shù),或者取消原有的依賴關(guān)系(刪除了調(diào)用的方法,或是刪除了引用).基于對(duì)代碼域的編輯,編輯操作對(duì)依賴圖結(jié)構(gòu)依賴關(guān)系的影響可以分為3種情況:

1)編輯操作產(chǎn)生了新的依賴關(guān)系,依賴圖結(jié)構(gòu)發(fā)生改變.

2)編輯操作消除了部分或全部依賴關(guān)系,依賴圖結(jié)構(gòu)發(fā)生變化.

3)編輯操作消除了部分或全部依賴關(guān)系,且產(chǎn)生了新的依賴關(guān)系,依賴圖結(jié)構(gòu)發(fā)生改變.

情況1.如圖4中的(a)部分所示,該部分左側(cè)結(jié)點(diǎn)C是一個(gè)獨(dú)立的基礎(chǔ)域,用戶u0對(duì)節(jié)點(diǎn)C的編輯產(chǎn)生了新的依賴關(guān)系C→B.右側(cè)中用戶u1對(duì)結(jié)點(diǎn)B的編輯產(chǎn)生了新的依賴關(guān)系B→C;

情況2.如圖4的(b)部分所示,(a)部分中左側(cè)用戶u0對(duì)結(jié)點(diǎn)C的編輯取消了對(duì)結(jié)點(diǎn)B的依賴.右側(cè)中用戶u1對(duì)于依賴圖結(jié)點(diǎn)B的編輯取消了對(duì)結(jié)點(diǎn)C的依賴.

情況3.如圖4的(c)部分所示,用戶u0關(guān)于結(jié)點(diǎn)C的編輯操作即取消了原有的依賴關(guān)系,且增加了新的依賴關(guān)系.

圖4列舉了依賴關(guān)系動(dòng)態(tài)變化的3種情況.在協(xié)同編程環(huán)境中基礎(chǔ)域被調(diào)用、引用或是取消調(diào)用、引用的情況十分普遍,故支持動(dòng)態(tài)依賴關(guān)系的語義一致性維護(hù)在協(xié)同編程環(huán)境中是轉(zhuǎn)關(guān)重要.值得強(qiáng)調(diào)的是,動(dòng)態(tài)依賴圖語義一致性維護(hù)難點(diǎn)在于并發(fā)的編輯可能導(dǎo)致各個(gè)站點(diǎn)上的依賴圖不一致問題,而操作的發(fā)送只基于當(dāng)前站點(diǎn)的依賴圖結(jié)構(gòu),當(dāng)操作到達(dá)其它站點(diǎn)若按原站點(diǎn)的依賴圖結(jié)構(gòu)執(zhí)行亦可能導(dǎo)致語義錯(cuò)誤.

圖4 動(dòng)態(tài)依賴圖Fig.4 Dynamic depency graph

3.6 不完整的編輯操作

不完整的編輯操作指的是編輯還未完成或是編輯操作在編譯器上存在不符合編程語言規(guī)則的情況.通常,不完整的編輯操作直接導(dǎo)致編程語言規(guī)則錯(cuò)誤,且編譯器中實(shí)時(shí)的出現(xiàn)錯(cuò)誤提醒.不完整的編輯操作大致可以分為兩種情況:

1)基礎(chǔ)域中的內(nèi)容編輯未完成或是不符合編程語言規(guī)則.

2)對(duì)于基礎(chǔ)域的編輯操作,破壞了原有的依賴關(guān)系,導(dǎo)致了編程語言規(guī)則錯(cuò)誤(破壞了原有的依賴關(guān)系,且符合編程語言規(guī)則的編輯操作,不屬于不完整的編譯操作的范疇).

情況1.如圖5的(a)部分所示,在站點(diǎn)0上,用戶u0向list類中添加方法void clear(){,但是符號(hào)‘{’少匹配了符號(hào) ‘}’,違背了編程語言規(guī)則,即用戶u0新添加的代碼存在編程語言規(guī)則錯(cuò)誤.且站點(diǎn)1執(zhí)行了用戶u0的存在編程語言錯(cuò)誤的編輯操作導(dǎo)致該站點(diǎn)也出現(xiàn)編程語言規(guī)則錯(cuò)誤.廣播存在錯(cuò)誤的操作可能帶來許多不必要的麻煩.例如,若存在多個(gè)用戶發(fā)現(xiàn)用戶u0的錯(cuò)誤代碼,且并發(fā)的進(jìn)行了修改,無形中增加了并發(fā)編輯及語義沖突的概率,降低了協(xié)同的效率.

圖5 不完整的編輯操作Fig.5 Incompleted editing operation

情況2.如圖5的(b)部分所示,站點(diǎn)0上用戶u0將結(jié)點(diǎn)b中的變量length修改為m_length,由于該操作破壞了原有的依賴關(guān)系(結(jié)點(diǎn)e丟失依賴節(jié)點(diǎn)b),故對(duì)length的修改將引起所有引用變量length的基礎(chǔ)域發(fā)生編程語言規(guī)則錯(cuò)誤.在站點(diǎn)1上執(zhí)行用戶u0的編程操作將出現(xiàn)與站點(diǎn)0上相同的錯(cuò)誤.用戶需將結(jié)點(diǎn)e中變量length也修改為m_length或者是刪除變量length,才能消除錯(cuò)誤.若將結(jié)點(diǎn)b,e的變量length都修改為m_length,再打包發(fā)送結(jié)點(diǎn)b,e的編輯操作集合到其它站點(diǎn),將避免上述不完整的編輯導(dǎo)致的編程語言規(guī)則錯(cuò)誤.上述兩種情況都將視為不完整的編輯操作.廣播錯(cuò)誤操作可能造成許多沒有必要的麻煩.通常不完整的編輯操作產(chǎn)生的錯(cuò)誤能得到編譯器錯(cuò)誤警告,并不是難以避免的,明知存在錯(cuò)誤卻仍發(fā)送錯(cuò)誤的操作是不符合常理的,且廣播存在錯(cuò)誤的編輯操作到其它站點(diǎn)上,勢(shì)必導(dǎo)致其它站點(diǎn)上的代碼發(fā)生錯(cuò)誤.從開發(fā)者的角度來說,提交或廣播的代碼應(yīng)該是完整的(不存在編程語言錯(cuò)誤),不完整的代碼很難讓協(xié)同工作者明白,接收到新的代碼的作用、有無意義.若不完整的代碼存在錯(cuò)誤甚至可能影響了協(xié)同工作者的編碼.故發(fā)送的編輯操作一定是完整的編輯操作.不完整的編程操作源于用戶的編輯行為違背了編程語言規(guī)則,且并不是并發(fā)沖突導(dǎo)致的,故無需特殊的檢查條件,只需判斷此時(shí)編譯器是否報(bào)錯(cuò)即可.

3.7 編輯操作的發(fā)送

文中對(duì)代碼域的編輯自動(dòng)發(fā)送設(shè)定為當(dāng)用戶開始工作于某個(gè)代碼域視為工作開始,當(dāng)用戶離開當(dāng)前代碼域或是進(jìn)入新的代碼域視為完成編輯工作,編輯操作自動(dòng)發(fā)送.當(dāng)用戶離開當(dāng)前代碼域或進(jìn)入新的代碼域,若編輯操作為不完整的編輯操作,該代碼域的編輯操作不發(fā)送.發(fā)送的編輯操作應(yīng)當(dāng)是對(duì)應(yīng)是代碼域?yàn)橥瓿蔂顟B(tài)下的編輯操作集合(完整的編輯操作).編輯操作在未發(fā)送前,操作集合存儲(chǔ)在本地編輯隊(duì)列(EditQueue)中等待發(fā)送.例如,圖6的(a)部分對(duì)應(yīng)圖1中l(wèi)ist類中添加clear方法,操作O1=insert(void clear(){;,20,0),操作O2=insert(},20,14).關(guān)于依賴圖結(jié)點(diǎn)i的操作集合為EditQueue_i={O1,O2}.以此類推,圖6中的(b)部分中修改結(jié)點(diǎn)b的完整編輯操作集合應(yīng)當(dāng)為EditQueue_b={O3}與EditQueue_e={O4}.

圖6 完整的編輯操作Fig.6 Complete editing operation

4 自動(dòng)比較與交換沖突消解方法(ACAS)

文中通過幾個(gè)較有代表性的案例,分析語義沖突可能產(chǎn)生以及動(dòng)態(tài)依賴語義沖突發(fā)生的場(chǎng)景.從上述的案例中我們不難發(fā)現(xiàn)協(xié)同編程系統(tǒng)無法判斷非編程語言規(guī)則錯(cuò)誤的操作是否存在語義沖突,若編輯操作為排斥關(guān)系,只保留一個(gè)操作,其它編輯操作將會(huì)被拒絕,又或是被保存.考慮操作不兼容的問題及減少協(xié)同編輯限制,本文基于SUN,FAN等人的研究,在網(wǎng)絡(luò)穩(wěn)定的前提下,采用復(fù)制式結(jié)構(gòu),結(jié)合CAS的并發(fā)控制思想以及依賴圖的動(dòng)態(tài)變化場(chǎng)景設(shè)計(jì)了實(shí)時(shí)協(xié)同編程環(huán)境的語義沖突消解方法ACAS.

4.1 ACAS算法設(shè)計(jì)

4.1.1 依賴圖結(jié)點(diǎn)標(biāo)識(shí)碼(Tag)

本文對(duì)每個(gè)基礎(chǔ)域添加標(biāo)識(shí)碼,標(biāo)識(shí)碼用于對(duì)比分析基礎(chǔ)域的變化情況.通過判斷標(biāo)識(shí)碼的變化情況,分析編輯操作是否存在語義沖突發(fā)生.標(biāo)識(shí)碼為一個(gè)三維向量,例如Tag(0,0,0).向量中,左值表示為UpStreamTag(UST),中值為DownStreamTag(DST),右值為SelfAreaTag(SAT).依賴圖結(jié)點(diǎn)的標(biāo)識(shí)碼為對(duì)應(yīng)基礎(chǔ)域的標(biāo)識(shí)碼.

1)UpStreamTag:該基礎(chǔ)域依賴的其它基礎(chǔ)域的編輯操作會(huì)導(dǎo)致UST自加.

2)DownStreamTag:依賴于該基礎(chǔ)域的所有基礎(chǔ)域的編輯操作會(huì)引起DST自加.

3)SelfAreaTag:編輯操作在當(dāng)前的基礎(chǔ)域執(zhí)行后SAT自加.

標(biāo)識(shí)碼只有在編輯操作成功執(zhí)行后才能自加.

例如:C→B→A,假設(shè)結(jié)點(diǎn)A、B、C的標(biāo)識(shí)碼都為(0,0,0).當(dāng)基礎(chǔ)域B完成編輯工作.結(jié)點(diǎn)B的SAT發(fā)生改變,此時(shí)的基礎(chǔ)域B的標(biāo)識(shí)碼為(0,0,1),由于結(jié)點(diǎn)C依賴于結(jié)點(diǎn)B,因此結(jié)點(diǎn)C的UST發(fā)生改變,結(jié)點(diǎn)C的標(biāo)識(shí)碼更新為(1,0,0).即結(jié)點(diǎn)B的編輯操作執(zhí)行后,影響SAT的同時(shí),影響結(jié)點(diǎn)A的DST,結(jié)點(diǎn)B的UST.

4.1.2 相同結(jié)點(diǎn)標(biāo)識(shí)碼的比較

存在兩種站點(diǎn)i,j.兩個(gè)站點(diǎn)上相同的結(jié)點(diǎn)x的標(biāo)識(shí)碼為(1,1,1).

Ti =(1,1,1),Tj=(1,1,1)證明在站點(diǎn)j和站點(diǎn)i標(biāo)識(shí)碼不變,沒有影響結(jié)點(diǎn)x的操作.

Ti =(1,1,1),Tj=(1,1,2)證明在站點(diǎn)j上的結(jié)點(diǎn)x已經(jīng)發(fā)生變化.Ti=(1,1,1),Tj=(2,1,1)證明在站點(diǎn)j上的結(jié)點(diǎn)x的依賴的其它結(jié)點(diǎn)發(fā)生變化.

Ti=(1,1,1),Tj=(1,2,1)證明在站點(diǎn)j上依賴于結(jié)點(diǎn)x的其它結(jié)點(diǎn)發(fā)生變化.

標(biāo)識(shí)碼相同時(shí),證明該結(jié)點(diǎn)未被修改.若標(biāo)識(shí)碼不相同,可能存在語義沖突的情況,在依賴圖結(jié)構(gòu)不變的前提下,存在語義沖突,需要進(jìn)行沖突消解.若依賴圖結(jié)構(gòu)發(fā)生改變,需要通過對(duì)依賴圖結(jié)構(gòu)進(jìn)行分析后,判斷語義沖突是否發(fā)生后,再進(jìn)行相應(yīng)處理.

4.1.3 基礎(chǔ)域狀態(tài)

本文對(duì)基礎(chǔ)域添加了二個(gè)狀態(tài).每個(gè)基礎(chǔ)域都有一個(gè)相對(duì)應(yīng)的工作狀態(tài).基礎(chǔ)域的工作狀態(tài)分為兩類:

1)Editing:基礎(chǔ)域處于編輯狀態(tài).

2)Completed:基礎(chǔ)域處于完成編輯狀態(tài).

當(dāng)用戶進(jìn)入某個(gè)基礎(chǔ)域,該基礎(chǔ)域的工作狀態(tài),變?yōu)镋diting.當(dāng)用戶離開該基礎(chǔ)域或進(jìn)入新的基礎(chǔ)域,且產(chǎn)生的編輯操作為完整的編輯操作將視為代碼編輯完成,基礎(chǔ)域的工作狀態(tài)變?yōu)镃ompleted.

定義5.編輯操作優(yōu)先.

1)假設(shè)存在兩個(gè)基礎(chǔ)域A、B,且B依賴于A,且并發(fā)的兩個(gè)操作O1,O2分別作用于基礎(chǔ)域A,B,操作O1優(yōu)先于操作O2.操作O1優(yōu)先更新的原因在于,若無并發(fā)的編輯操作,通常對(duì)基礎(chǔ)域A的編輯可能影響到基礎(chǔ)域B,而不論基礎(chǔ)域B如何變化,對(duì)基礎(chǔ)域A都不產(chǎn)生影響.

2)存在一個(gè)基礎(chǔ)域A,如果存在對(duì)基礎(chǔ)域A的并發(fā)的編輯操作.在編輯操作不改變依賴圖結(jié)構(gòu)的前提下,優(yōu)先執(zhí)行優(yōu)先高的操作(站點(diǎn)號(hào)越小優(yōu)先級(jí)越高).為避免單純使用優(yōu)先級(jí)在動(dòng)態(tài)依賴圖中帶來的代碼文本不一致問題,若編輯操作導(dǎo)致了依賴圖結(jié)構(gòu)發(fā)生變化,優(yōu)先執(zhí)行依賴圖結(jié)點(diǎn)中依賴關(guān)系數(shù)較少的編輯操作.

定義6.編輯操作等待.

1)如果在某一基礎(chǔ)域正處于Editing狀態(tài),其它站點(diǎn)關(guān)于該基礎(chǔ)域的編輯到達(dá)時(shí)進(jìn)行操作等待,直到該基礎(chǔ)域編輯完成.

2)若基礎(chǔ)域的編輯操作標(biāo)識(shí)碼SAT大于當(dāng)前基礎(chǔ)域的標(biāo)識(shí)碼,證明該操作為未來操作,需進(jìn)行操作等待.

4.1.4 代碼域內(nèi)容的撤銷與恢復(fù)

考慮到依賴關(guān)系動(dòng)態(tài)變化及語義沖突導(dǎo)致編輯操作不兼容的問題,存在一些不得不撤銷的編輯操作.很容易想到是采用OT技術(shù)的歷史緩存進(jìn)行undo-redo操作,但歷史緩存數(shù)量較大時(shí),undo-redo不是一個(gè)特別高效的方法.為了提高代碼文檔內(nèi)容撤銷與恢復(fù)的效率,文中采用版本技術(shù)記錄編輯操作,并通過版本覆蓋的方式恢復(fù)代碼,且多余的版本將被刪除或是被保存.

定義7.代碼域版本(DepencyGraphicVersion).

代碼域的版本以基礎(chǔ)域?yàn)榛締挝?每個(gè)基礎(chǔ)域都有其對(duì)應(yīng)的代碼域版本.在每個(gè)站點(diǎn)上,用戶創(chuàng)建一個(gè)新的基礎(chǔ)域,或者在某個(gè)代碼域成功執(zhí)行的操作都會(huì)創(chuàng)建一個(gè)新的代碼域版本,存儲(chǔ)在本地,組成基礎(chǔ)域的歷史版本.代碼域的版本號(hào)為其所對(duì)應(yīng)的基礎(chǔ)域的標(biāo)識(shí)碼的值.若存在代碼域版本恢復(fù)的情況,該基礎(chǔ)域的標(biāo)識(shí)碼及相關(guān)標(biāo)識(shí)碼需伴隨著版本恢復(fù)回退至原先的值.

基礎(chǔ)域的版本存儲(chǔ)是有十分有意義的,復(fù)雜軟件的開發(fā)往往具有較長(zhǎng)的開發(fā)周期及龐大的代碼量,可能需要對(duì)代碼進(jìn)行反復(fù)的修改.存儲(chǔ)代碼版本,開發(fā)人員可以通過歷史版本,查看代碼修改歷史,能夠直觀的判斷之前的修改目的,甚至當(dāng)代碼出錯(cuò)時(shí)判斷出錯(cuò)原因,以及不再需要擔(dān)心代碼內(nèi)容丟失或是難以恢復(fù).

如圖7所示,在站點(diǎn)0上,結(jié)點(diǎn)i當(dāng)前的代碼域版本為版本(0,0,0).當(dāng)用戶u0編輯了結(jié)點(diǎn)i,若操作成功執(zhí)行,將生產(chǎn)新的代碼域版本(0,0,1).假設(shè)此時(shí)存在其它用戶的編輯操作與用戶u0的操作存在語義沖突,且操作相互排斥,需要撤銷用戶u0的編輯操作,此時(shí)只需要執(zhí)行revert操作將代碼版本恢復(fù)至未修改前的版本(0,0,0)即可.用戶u0的操作產(chǎn)生的結(jié)點(diǎn)i版本(0,0,1)將會(huì)被刪除或被保存.從用戶體驗(yàn)的角度考慮,若保存用戶u0生成的版本(0,0,1),相當(dāng)于保存了用戶u0的工作,通過版本對(duì)比,分析當(dāng)前節(jié)點(diǎn)i版本與用戶u0的版本存在的差異,保存代碼版本能更好的幫助用戶工作.從節(jié)約資源的角度考慮,結(jié)點(diǎn)i已經(jīng)恢復(fù)至版本(0,0,0),此時(shí)版本(0,0,1)是無效版本(產(chǎn)生語義沖突的代碼域版本),刪除即可.文中采用的方式是將無效的代碼版本保存.

4.1.5 操作請(qǐng)求

文中將操作請(qǐng)求定義為一個(gè)二元組,s(site)表示站點(diǎn)id,NQ(Node Queue)={Node0,Node1.NodeN}表示用戶完整編輯操作下各個(gè)結(jié)點(diǎn)的操作集合.

Node為一個(gè)結(jié)構(gòu)體其中包含了以下信息:

1)Id:結(jié)點(diǎn)id,通過id在依賴圖中找到該節(jié)點(diǎn).

2)Tag:結(jié)點(diǎn)標(biāo)識(shí)碼,用于判斷語義沖突是否發(fā)生.

3)EditType:關(guān)于基礎(chǔ)域的編輯類型,新建一個(gè)基礎(chǔ)域用1表示,刪除基礎(chǔ)域用-1表示,編輯基礎(chǔ)域表示為0.

4)EditQueue:用于保存基礎(chǔ)域的編輯操作集合.

5)RootNode:未編輯前,結(jié)點(diǎn)直接依賴的其它結(jié)點(diǎn)集合,用于判斷依賴圖結(jié)構(gòu)是否發(fā)生變化.

6)NewDepency:記錄新增的依賴結(jié)點(diǎn)或減少的依賴結(jié)點(diǎn),新增的結(jié)點(diǎn)表示為+Nodeid,減少標(biāo)識(shí)為-Nodeid,在依賴圖結(jié)構(gòu)發(fā)生變化時(shí)用于判斷語義沖突是否發(fā)生.

7)NodeVersion:記錄當(dāng)前基礎(chǔ)域的版本號(hào),用于語義沖突發(fā)生時(shí),進(jìn)行代碼域版本恢復(fù).

4.1.6 ACAS的數(shù)據(jù)結(jié)構(gòu)

如文中將代碼文本劃分成多個(gè)代碼域,存在代碼的基礎(chǔ)域?qū)?yīng)一個(gè)標(biāo)識(shí)碼和編輯狀態(tài).ACAS表中記錄代碼文檔中所有基礎(chǔ)域?qū)?yīng)的依賴圖節(jié)點(diǎn)信息.ACAS表中記錄節(jié)點(diǎn)信息隨著節(jié)點(diǎn)狀態(tài)的動(dòng)態(tài)變化而改變.如圖8所示,圖左表示代碼文檔的劃分,圖右側(cè)為ACAS table,表中記錄節(jié)點(diǎn)A、B此時(shí)的標(biāo)識(shí)碼狀態(tài)和編輯狀態(tài)(C:Completed,E(Editing).

圖8 ACAS數(shù)據(jù)結(jié)構(gòu)Fig.8 Data structure of ACAS

4.1.7 編輯操作執(zhí)行許可條件檢查

1)基礎(chǔ)域工作狀態(tài)為Completed.

2)基礎(chǔ)域的標(biāo)識(shí)碼中除DST外其它標(biāo)識(shí)碼需相等.

只有符合上述兩個(gè)條件的操作才能成功執(zhí)行.

4.1.8 ACAS算法設(shè)計(jì)

結(jié)合編輯操作執(zhí)行許可檢查條件,ACAS算法設(shè)計(jì)描述如下:

Algorithm 1:用于獲得操作落入的代碼域,如代碼域?yàn)橐粋€(gè)空白區(qū)域,需要新建一個(gè)基礎(chǔ)域,并將基礎(chǔ)域的編輯狀態(tài)更新為editing.由于用戶在進(jìn)行編碼過程中,可能收到來自其它站點(diǎn)上工作于相同代碼域的用戶并發(fā)操作,而導(dǎo)致語義沖突.為了消除這種情況帶來的語義沖突,處在編輯狀態(tài)下的代碼域不接受其它站點(diǎn)的編輯操作直到編輯完成,其它站點(diǎn)的編輯操作,需等待本地編輯完成后才能執(zhí)行.

Algorithm 1.GetWorkArea(O)

w:=GetArea(O);

if(w==NULL)

Area temp=CreateArea();

temp.workStaus=editing;

else w.tagStaus=editing;

Alogrithm2:對(duì)本地的編輯操作進(jìn)行更新檢查.代碼域處在editing狀態(tài)時(shí),收到的遠(yuǎn)程站點(diǎn)的操作將會(huì)被保存在等待隊(duì)列中等待執(zhí)行.故本地生成的操作在發(fā)送之前需要判斷等待隊(duì)列是否為空,若等待隊(duì)列為空,本地生成的操作成功發(fā)送,否則,編輯操作不發(fā)送,保存本地上已經(jīng)執(zhí)行編輯操作并撤銷這些操作.之后,執(zhí)行等待隊(duì)列中的操作.

Algorithm 2.LocalUpdateCheck()

if(waitQueue()==NULL) return success;

else stop boardcast;

save()and revert(t);

for_each(auto x:waitQueue()) do x;

Algorithm 3:若編輯操作在基礎(chǔ)域上成功執(zhí)行,在本地站點(diǎn)上將會(huì)立即生成一個(gè)新的基礎(chǔ)域版本.如:執(zhí)行save操作或是對(duì)基礎(chǔ)域的成功修改也生成一個(gè)新的代碼域版本存在本地,版本號(hào)為立即生效后的標(biāo)識(shí)碼的值.代碼版本用于記錄代碼的編輯歷史以及代碼的恢復(fù).

Algorithm 3.createNewVersion(tag)

if(update_success) createNewVersion(tag);

if(save(tag)) createSaveVersion(tag);

Algorithm 4:檢查操作編輯類型,若是創(chuàng)建一個(gè)新的基礎(chǔ)域,操作立即執(zhí)行.否則,檢查操作請(qǐng)求的標(biāo)識(shí)碼與本地將要執(zhí)行該操作的結(jié)點(diǎn)標(biāo)識(shí)碼是否相同,如果標(biāo)識(shí)碼相同,操作執(zhí)行,如果不同,根據(jù)標(biāo)識(shí)碼變化類型進(jìn)行相應(yīng)處理.

Algorithm 4.RemoteUpdateCheck()

if(Node.editType ==1) return success;

if(equal(tag)) return success;

switch(change_type(tag)){

case UST_Change:UpStreamTagChange();

case SAT_Change:SelfAreaTagChange();

case DST_Change:DownStreamTagChange();

default:error(“type error”);break;}

Algorithm 5:由于代碼文檔的復(fù)雜性,編輯操作可能導(dǎo)致依賴圖結(jié)構(gòu)發(fā)生變化而導(dǎo)致語義沖突發(fā)生,故在遠(yuǎn)程站點(diǎn)上操作的執(zhí)行需要檢測(cè)基礎(chǔ)域的依賴情況是否變化.首先判斷NewDepency(ND,用于記錄編輯操作產(chǎn)生的新依賴關(guān)系)是否為空,如為空,編輯操作未導(dǎo)致依賴圖結(jié)構(gòu)變化,語義沖突發(fā)生,編輯拒絕.如果發(fā)生改變,若增加了新的依賴域,需要考慮增加的依賴域的標(biāo)識(shí)碼是否發(fā)生改變,若標(biāo)識(shí)碼改變,則操作被拒絕.如果依賴域減少了,減少的依賴域不應(yīng)該在對(duì)編輯操作將要執(zhí)行的結(jié)點(diǎn)標(biāo)識(shí)碼產(chǎn)生影響,判斷UST變化的值是否受到減少的依賴域的影響.排除減少的依賴域的影響后,若標(biāo)識(shí)碼相同,則證明不存在語義沖突.若UST的改變不存在語義沖突,再檢查其它標(biāo)識(shí)碼的變化情況,若其他標(biāo)識(shí)碼未改變,則更新成功.

Algorithm 5.UpStreamTagChange()

if(ND.isEmpty())return reject;//(R==Remote)

else{

for_each(auto x:ND){

if(x.changeType==del && x∈R_x.rootNode){

times=|x.UST-R_x.UST|+|x.SAT-R_x.SAT|;

if(times !=|operation.UST-target.UST|) return reject;

else if(x.changeType==add){

if(x.tag !=Rx.tag) return reject;}

if(SAT_Change) SelfAreaTagChange();

if(DST_Change) DownStreamTagChange();}}

return success;

Algorithm 6:若SAT改變,證明存在對(duì)相同代碼域的并發(fā)操作,通過標(biāo)識(shí)碼在遠(yuǎn)程站點(diǎn)中的請(qǐng)求日志找到并發(fā)的操作,對(duì)比操作之間的優(yōu)先級(jí),若操作請(qǐng)求的優(yōu)先級(jí)大于當(dāng)前站點(diǎn)的操作,則進(jìn)行版本恢復(fù),并撤銷該并發(fā)操作對(duì)站點(diǎn)標(biāo)識(shí)碼的影響.同時(shí)檢查DST是否改變,若DST未改變,進(jìn)行DST變化檢查.

Algorithm 6.SelfAreaTagChange

Rrequest = Log.find(tag);

if(Rrequset.Prop < operation.Prop){

revert(tag);

if(DST_Change) DownStreamTagChange();

return success;}

return reject;

Algorithm 7:若DST改變了,證明DownStreamNode中存在語義沖突的編輯操作.由于依賴關(guān)系的動(dòng)態(tài)性,只比較編輯結(jié)點(diǎn)的標(biāo)識(shí)碼已經(jīng)無法確定可能產(chǎn)生語義沖突的基礎(chǔ)域.需要通過對(duì)比站點(diǎn)間的DownStreamNode的SAT的變化情況來確定是哪些代碼域的編輯操作導(dǎo)致了DST的變化.若DowmStreamNode中結(jié)點(diǎn)的SAT不一致則證明語義沖突存在,應(yīng)撤銷導(dǎo)致SAT變化的編輯操作,消除沖突.

Algorithm 7.DownStreamTagChange()

subtract=operation.DST-RNode.DST;

for_each(auto x:DSNode && substract){

if(x.Version==Rx.Version)continue;

else{ temp-=Rx.Version-x.Version;

save()and revert();}

if(subtract)return success;}

return success;

4.2 實(shí)例分析

本小節(jié)著重介紹一個(gè)語義一致性維護(hù)的綜合性案例,描述上小節(jié)中控制函數(shù)是如何維護(hù)協(xié)同編程環(huán)境下的語義沖突.

如圖9所示,站點(diǎn)1、2、3上的操作O1、O2、O3分別作用于結(jié)點(diǎn)A,結(jié)點(diǎn)C和結(jié)點(diǎn)E.操作O1對(duì)結(jié)點(diǎn)A進(jìn)行了修改,操作O2取消了結(jié)點(diǎn)C對(duì)結(jié)點(diǎn)A的依賴,故結(jié)點(diǎn)A的任何變化都不在對(duì)結(jié)點(diǎn)E產(chǎn)生影響.操作O3取消了結(jié)點(diǎn)E對(duì)結(jié)點(diǎn)C的依賴.當(dāng)操作O1到達(dá)站點(diǎn)2,3時(shí),通過Algorithm4判斷標(biāo)識(shí)碼未發(fā)生改變,不存在語義沖突,操作O1成功執(zhí)行.操作O2到達(dá)站點(diǎn)1時(shí)檢測(cè)到結(jié)點(diǎn)C的UST發(fā)生改變,可能存在語義沖突,由于依賴圖結(jié)構(gòu)發(fā)生改變,通過Algorithm5處理后回退結(jié)點(diǎn)C的標(biāo)識(shí)碼,此時(shí)結(jié)點(diǎn)C的標(biāo)識(shí)碼與操作O2的標(biāo)識(shí)碼相同,無語義沖突,操作O2成功執(zhí)行.同理操作O3也成功執(zhí)行.操作O4,O5,O6,分別作用于站點(diǎn)1的結(jié)點(diǎn)D,站點(diǎn)2的結(jié)點(diǎn)D,站點(diǎn)3的結(jié)點(diǎn)A.當(dāng)操作O4到達(dá)站點(diǎn)2時(shí)檢測(cè)到結(jié)點(diǎn)D的SAT發(fā)生改變,此時(shí)語義沖突發(fā)生,通過Algotihm6

圖9 案例分析Fig.9 Case analysis

處理后,撤銷操作O5對(duì)結(jié)點(diǎn)D的影響,執(zhí)行操作O4.操作O5到達(dá)其他站點(diǎn)時(shí)根據(jù)定義,操作將會(huì)被拒絕,由于操作O6工作于獨(dú)立的基礎(chǔ)域不產(chǎn)生語義沖突,操作成功執(zhí)行.經(jīng)過ACAS方法進(jìn)行語義沖突消解后獲得代碼文檔滿足收斂性.

5 CoCode原型系統(tǒng)

為了驗(yàn)證ACAS算法及相關(guān)函數(shù)的可行性與正確性,本文在Windows平臺(tái)下使用VS2015,C++語言編碼開發(fā)了實(shí)時(shí)協(xié)同編程環(huán)境的原型系統(tǒng)CoCode.前端模塊功能基于QT框架實(shí)現(xiàn),后臺(tái)服務(wù)器端邏輯基于SeaStar異步通信框架實(shí)現(xiàn)相關(guān)業(yè)務(wù)功能與通信事件的監(jiān)聽.本文在多臺(tái)設(shè)備上安裝了CoCode原型系統(tǒng),登入的用戶可通過圖10左側(cè)的文件目錄訪問不同或相同的代碼文檔并進(jìn)行協(xié)同編輯.圖10的中部為協(xié)同編碼區(qū)域,用戶所在的編輯代碼行將存在顏色高亮.圖10右側(cè)為OnLineEditor模塊與Information模塊.OnlineEditor模塊記錄參與協(xié)同編輯工作的所有在線用戶.Information模塊用于記錄用戶實(shí)時(shí)交流信息、代碼提交的反饋信息及代碼域內(nèi)容變更的提醒信息.圖10的下方為當(dāng)前代碼的輸出顯示框,上方為系統(tǒng)菜單欄,其中包含了create、save、undo、redo、build、run、submit、download等功能.

圖10 原型系統(tǒng)CoCodeFig.10 CoCode prototype system

6 實(shí)驗(yàn)分析

復(fù)雜軟件的開發(fā)往往需要較長(zhǎng)的周期,需要較多的開發(fā)人員參與,且軟件的源代碼文檔數(shù)量較多.實(shí)驗(yàn)不考慮開發(fā)周期因素,將從開發(fā)人員數(shù)與源代碼文檔數(shù)兩方面著手進(jìn)行實(shí)驗(yàn)分析,本文將ACAS方法與DAL方法應(yīng)用于協(xié)同編程環(huán)境進(jìn)行效率對(duì)比分析.DAL方法不考慮出現(xiàn)shared-locking[7]時(shí)依賴于用戶交流維護(hù)代碼文檔的情況的前提下,針對(duì)兩種方法處理語義沖突的一致性維護(hù)時(shí)間進(jìn)行對(duì)比.針對(duì)一致性維護(hù)時(shí)間與協(xié)同站點(diǎn)數(shù)量做了相關(guān)的測(cè)試,仿真協(xié)同編程環(huán)境的語義沖突消解及一致性維護(hù)實(shí)驗(yàn).

實(shí)驗(yàn)1.以共享文檔為實(shí)驗(yàn)對(duì)象,對(duì)共享文檔劃分代碼域及依賴關(guān)系構(gòu)建依賴關(guān)系表,通過修改表中數(shù)據(jù)實(shí)現(xiàn)ACAS方法中標(biāo)識(shí)碼的改變或是DAL中基礎(chǔ)域的鎖的狀態(tài)改變,表中數(shù)據(jù)的修改即標(biāo)識(shí)相對(duì)應(yīng)的代碼域發(fā)生變化.從實(shí)驗(yàn)結(jié)果圖11可以看出ACAS方法語義沖突消解的處理時(shí)間略小于DAL方法,但相比于DAL方法,ACAS采用了版本恢復(fù)的方法增加了空間復(fù)雜度.同時(shí)可以看出不論是ACAS方法或是DAL方法,在文件數(shù)量固定的情況下,隨著協(xié)同站點(diǎn)數(shù)量的增加,一致性的維護(hù)時(shí)間都稍有提高,站點(diǎn)數(shù)量對(duì)協(xié)同編程環(huán)境下的一致性維護(hù)具有一定的影響.同時(shí)為了驗(yàn)證代碼文檔數(shù)及站點(diǎn)數(shù)對(duì)ACAS方法的一致性維護(hù)時(shí)間的影響,本文進(jìn)行了實(shí)驗(yàn)2.

圖11 ACAS方法與DAL方法對(duì)比圖Fig.11 Contrast of ACAS and DAL

實(shí)驗(yàn)2.對(duì)3種不同協(xié)同站點(diǎn)數(shù)在協(xié)同文檔數(shù)量相同情況下驗(yàn)證ACAS方法的一致性維護(hù)效率,前提條件及實(shí)驗(yàn)方法與實(shí)驗(yàn)1相同,通過增加協(xié)同編輯文件的數(shù)量檢驗(yàn)協(xié)同工作的一致性維護(hù)時(shí)間.由圖12可知,在代碼文檔相同時(shí),站點(diǎn)數(shù)越多一致性維護(hù)時(shí)間越長(zhǎng).若站點(diǎn)數(shù)相同時(shí),一致性維護(hù)時(shí)間隨著協(xié)同編輯的文檔個(gè)數(shù)增加不斷減少,且趨于平穩(wěn).通過實(shí)驗(yàn)分析,可以推斷的是,基于ACAS方法的實(shí)時(shí)協(xié)同編程環(huán)境較為適用于小型團(tuán)隊(duì)的系統(tǒng)開發(fā)工作.

圖12 文檔數(shù)與站點(diǎn)數(shù)的對(duì)比圖Fig.12 Contrast chart of files and sites

7 總結(jié)與展望

ACAS方法是實(shí)時(shí)協(xié)同編程環(huán)境下的一種新的語義沖突消解方法.本文深入分析協(xié)同編程環(huán)境的動(dòng)態(tài)依賴關(guān)系帶來的語義不一致問題,及不完整的編輯操作帶來的編程錯(cuò)誤,在P2P環(huán)境下基于CAS的并發(fā)控制思想設(shè)計(jì)了ACAS算法,并通過標(biāo)識(shí)碼對(duì)比函數(shù)及相關(guān)沖突消解方法實(shí)現(xiàn)了語義沖突檢測(cè)與語義沖突消解.為了驗(yàn)證該算法的可行性與正確性,在Windows平臺(tái)下開發(fā)了實(shí)時(shí)協(xié)同編程環(huán)境的原型系統(tǒng)CoCode并進(jìn)行了相關(guān)仿真實(shí)驗(yàn),以有效的實(shí)現(xiàn)多用戶間的協(xié)同工作.

由于代碼文檔的復(fù)雜性,ACAS方法在一些較為特殊的應(yīng)用場(chǎng)景下然存在一些問題,在未來的工作中,將致力于完善ACAS方法,以及實(shí)現(xiàn)多文件之間的語義沖突消解的研究.