% Třísměrný merge zdrojových souborů přes AST {#myslenky}

Základem této práce je logika přijímající a řešící kolizní stav, který vznikl při obecném řádkovém spojování, jako používá například verzovací nástroj git.

Nejdřív popíšu algoritmus obecně a v následujících kapitolách rozeberu každou část samostatně.
V první části se načítají tři vstupní soubory (báze, levá a pravá strana) a vytvoří se jejich AST. Algoritmem GumTree \cite{Falleri2014} se nalezne mapování uzlů mezi bází a levou, resp. pravou stranou. Novým algoritmem na základu \textsc{3dm} \cite{Lindholm2001} se tyto namapované stromy spojí do jednoho. Na závěr se ze vstupních souborů vyjmou ty části, které odpovídají spojenému stromu a vypíšou se jako výsledek.

\begin{figure}[H]
  \includegraphics[width=\textwidth,scale=0.5]{images/bp-merge-impl}
  \caption{Přehled kroků od vstupních souborů až po vypsání výsledku.}
\end{figure}

Hlavním přínosem této práce jsou tyto algoritmy:

- na spojování abstraktních syntaktických stromů libovolného jazyka \hyperref[spojovani-ast]{popsaného v kapitole},
- na transformaci AST zpět do kódu pomocí mapování na vstupní zdrojové kódy \hyperref[mapovani-na-kod]{v kapitole}.

K nalezení odpovídajících uzlů mezi jednou ze spojovaných větví a společnou větví se využívá algoritmu GumTree \cite{Falleri2014}, \hyperref[gumtree]{detailně popsaného v sekci}.

Algoritmus \textsc{3dm}, \hyperref[3dm]{popsaný v}, jsem v originální podobně nepoužil. Původní záměr spojit GumTree mapování a Lindholmův algoritmus z \textsc{3dm} na merge byl zmařen tím, jak moc je v \textsc{3dm} mapování a merge propojené. Definice \textit{far move}, mapování složitější než 1:1, a další z GumTree bez zbytečně složitých úprav nelze získat. Proto jsem se \textsc{3dm} pouze inspiroval, ale algoritmus navrhl nový, obecnější a tedy kompatibilní s GumTree.

Přestože cílem této práce je implementovat merge konkrétně pro jazyk PHP, jsou tyto algoritmy obecné a fungují pro AST každého jazyka. Liší se pouze výběr parseru, který je od ostatních částí striktně oddělen.

\input{myslenky/Merge.tex}