% Soudobé merge algoritmy a publikované alternativy {#research}

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ů.

# 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}