Newer
Older
V této kapitole je nejprve popsán společný teoretický základ všech algoritmů. Navazuje shrnutí implementací současných diff algoritmů a jejich využití ve verzovacích nástrojích. Následně je rozebrán základ pro jemnější a tedy přesnější porovnávání na úrovni abstraktních syntaktických stromů.
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Teoretický základ pro textové algoritmy
\input{research/Jazyk.tex}
\iffalse
\input{research/EditScript.tex}
\fi
\input{research/LCS.tex}
\input{research/Diff2.tex}
\input{research/Diff3.tex}
# Současné implementace diff algoritmů
\input{research/GNU.tex}
\input{research/libxdiff.tex}
\input{research/GoogleDMP.tex}
# Definice merge algoritmu
\input{research/Merge.tex}
\input{research/3WayMerge.tex}
# Současné verzovací nástroje
Pro studii běžně používaných merge algoritmů se zaměřím na tyto verzovací systémy: Apache Subversion (SVN), Mercurial a Git. Proprietární software Microsoft Team Foundation Server, Perforce Helix a další zkoumat nemůžu. Dále se nebudu věnovat méně známým open-source nástrojům jako například Bazaar (který obsahoval první implementaci Patience Diff, ale tento algoritmus je popsán v \hyperref[patience-diff]{kapitole o Gitu}).
\input{research/SVN.tex}
\input{research/Git.tex}
\input{research/Mercurial.tex}
# Teorie pro nové diff/merge algoritmy
Současné algoritmy používané ve verzovacích systémech nedostačují. Manuální řešení kolizí je náchylné na chybu a nedá se běžně reprodukovat (výjimkou je git, který utilitou \textsc{rerere} umí řešení kolizí přehrávat opakovaně). Programátoři se typicky snaží kolizím vyhnout a rozdělují si podle toho v týmu práci, omezují svou práci s větvemi a podobně. Chytřejší algoritmy, popsané v následujících dvou kapitolách, nabízí alternativní přístup k 3-way merge problému.
\input{research/AST.tex}
\input{research/OT.tex}
\input{research/FastMatch.tex}
# Nejnovější diff/merge algoritmy
\input{research/ChangeDistilling.tex}
\input{research/3dm.tex}
\input{research/GumTree.tex}