náhled|Příklad grafu historie projektu s kontrolou verzí, kde sloučení jsou vyznačena červenými šipkami Ve správě verzí (version control) je merge (sloučení, též nazývané integrace) základní operace, která slaďuje změny provedené v kolekci souborů řízených správou verzí. Nejtypičtěji je nutná tehdy, když je soubor upraven ve dvou nezávislých větvích (branch) a následně sloučen. Výsledkem je jediná kolekce souborů obsahující obě sady změn.

V některých případech lze merge provést automaticky, protože je k dispozici dostatečná historie informací pro rekonstrukci změn a tyto změny si neodporují. V jiných případech musí člověk rozhodnout, jak přesně mají výsledné soubory vypadat. Většina nástrojů pro správu verzí zahrnuje funkce pro sloučení.

Typy merge Existují dva typy sloučení: nestrukturované a strukturované.

Nestrukturovaný merge pracuje s čistým textem, typicky používá řádky textu jako atomické jednotky. Takový přístup používají unixové nástroje (diff/patch) a nástroje CVS (SVN, Git). Toto je omezené, protože řádek textu nereprezentuje strukturu zdrojového kódu.

Strukturované nástroje pro merge, neboli AST merge, převádějí zdrojový kód na plně rozlišený abstraktní syntaktický strom (AST). To umožňuje jemnozrnné sloučení, které se vyhýbá falešným konfliktům.

Automatický merge Automatický merge je to, co software pro správu verzí provádí, když slaďuje změny, ke kterým došlo současně (v logickém smyslu). Také jiný software nasazuje automatické sloučení, pokud umožňuje současnou úpravu stejného obsahu. Například Wikipedie umožňuje dvěma lidem editovat stejný článek současně; když pozdější přispěvatel uloží, jeho změny jsou sloučeny do článku místo přepsání předchozí sady změn.

Manuální merge Manuální merge je to, k čemu se lidé uchylují (případně s pomocí nástrojů pro sloučení), když musí srovnat soubory, které se liší.

Například manuální merge se použije, pokud dva systémy mají mírně odlišné verze konfiguračního souboru a uživatel potřebuje změny z obou verzí. Získání požadovaných změn lze obvykle dosáhnout sloučením konfiguračních souborů ručním výběrem požadovaných změn z obou zdrojů (toto se také nazývá dvoucestné sloučení, anglicky two-way merge).

Manuální merge je rovněž nutný, když automatické sloučení narazí na konflikt změn (merge conflict). Například jen málo automatických nástrojů pro merge dokáže sloučit dvě změny na stejném řádku kódu (například když jeden merge změní název funkce na tomtéž řádku, kde jiný merge přidá komentář). V takovém případě se systémy správy verzí uchylují k manuálnímu sloučení, které provádí uživatel.

Algoritmy pro merge Existuje mnoho různých přístupů k automatickému sloučení s jemnými rozdíly. Mezi nejvýznamnější algoritmy patří: třícestný merge (three-way merge), rekurzivní třícestný merge, fuzzy aplikace patchů, weave merge a komutace patchů. alt=Diagram of a three way merge|náhled|C je počátek souřadnicové soustavy, A a B jsou derivace C a D je nová výstupní verze.

Třícestný merge (three-way merge) Třícestný merge se provádí po automatické analýze rozdílů mezi souborem „A" a souborem „B" s přihlédnutím k jejich společnému předku „C". Jde o hrubou, ale široce použitelnou metodu sloučení, protože vyžaduje pouze jednoho společného předka pro rekonstrukci změn. Třícestný merge lze provádět nad čistým textem (sekvencí řádků) i nad strukturovanými stromy.

Třícestný merge hledá sekce, které jsou shodné pouze ve dvou ze tří souborů. V takovém případě existují dvě verze dané sekce – verze ze společného předka „C" je zahozena a verze, která se liší, je zachována ve výstupu. Konkrétně:

Pokud se „A" a „B" shodují, jejich verze se objeví ve výstupu. Sekce shodná v „A" a „C" vygeneruje změněnou verzi z „B". Sekce shodná v „B" a „C" vygeneruje verzi z „A". Sekce, které se liší ve všech třech souborech, jsou označeny jako konflikt a ponechány uživateli k vyřešení.

Třícestný merge je implementován všudypřítomným programem diff3 a byl ústřední inovací, která umožnila přechod od systémů správy verzí založených na zamykání souborů k systémům založeným na sloučení. Extenzivně ho využívá systém CVS (Concurrent Versions System).

Rekurzivní třícestné merge Nástroje založené na třícestném merge jsou rozšířené, ale technika zásadně závisí na nalezení společného předka verzí určených ke sloučení. Existují problémové případy, zejména tzv. criss-cross merge (křížové sloučení), kde unikátní poslední společný předek modifikovaných verzí neexistuje. náhled|Problém „křížového sloučení“ ve správě verzí softwaru. V levé polovině se upravují 2 oblasti, a . a jsou postupně upravené verze. Řešení je znázorněno v pravé polovině: je vytvořen virtuální předek (čárkovaný kruh). V takovém případě lze ukázat, že existují nejvýše dva možní kandidáti na předka, a rekurzivní třícestný merge sestaví virtuálního předka tím, že nejprve sloučí neunikátní předky. Toto sloučení samo může trpět stejným problémem, takže algoritmus je rekurzivně sloučí. Protože počet verzí v historii je konečný, zakončení procesu je zaručeno. Tuto techniku používá systém správy verzí Git .

(Implementace rekurzivního merge v Gitu také zvládá další složité případy, jako například úpravu souboru v jedné verzi a jeho přejmenování v druhé, ale to jsou rozšíření implementace třícestného merge, nikoli součást techniky pro nalezení tří verzí ke sloučení.)

Rekurzivní třícestný merge lze použít pouze v situacích, kdy má nástroj znalost celého orientovaného acyklického grafu (DAG – directed acyclic graph) původu derivovaných verzí. V důsledku toho jej nelze použít v situacích, kde derivované verze či sloučení plně nespecifikují své rodičovské verze.

Fuzzy aplikace patchů Patch je soubor obsahující popis změn v souboru. V unixovém světě existuje tradice šířit změny textových souborů jako patche ve formátu, který produkuje příkaz „diff -u“. Tento formát pak může být použit programem patch k opětovnému aplikování (nebo odstranění) změn do (nebo z) textového souboru či adresářové struktury obsahující textové soubory.

Program patch však má také určité schopnosti aplikovat patch na soubor, který není přesně shodný s původním souborem použitým k vytvoření patche. Tento proces se nazývá fuzzy aplikace patche a výsledkem je druh asymetrického třícestného merge, kde jsou změny z patche zahozeny, pokud program patch nenajde místo, kam je aplikovat.

Stejně jako CVS začínal jako sada skriptů nad diff3, GNU arch začínal jako sada skriptů nad programem patch. Fuzzy aplikace patche je však relativně nespolehlivá metoda – někdy špatně aplikuje patche s příliš malým kontextem (zejména ty, které vytvářejí nový soubor) a někdy odmítá aplikovat smazání, která provedla obě derivované verze.

Komutace patchů (patch commutation) Komutace patchů se používá v systému Darcs pro sloučení změn a je také implementována v Gitu (kde se nazývá „rebaseing“). Komutace patchů znamená změnu pořadí patchů (tj. popisů změn) tak, aby tvořily lineární historii. V praxi to znamená, že když jsou dva patche vytvořeny v kontextu společné situace, při sloučení je jeden z nich přepsán tak, aby vypadal, jako by byl proveden v kontextu druhého.

Komutace patchů vyžaduje, aby přesné změny, které vytvořily derivované soubory, byly uloženy nebo mohly být rekonstruovány. Z těchto přesných změn je možné vypočítat, jak by měl být jeden z nich změněn, aby byl přezaložen (rebased) na druhý. Například pokud patch A přidá řádek „X" za řádek 7 souboru F a patch B přidá řádek „Y" za řádek 310 souboru F, pak B musí být přepsán, pokud je přezaložen na A: řádek musí být přidán na řádek 311, protože řádek přidaný v A posunul čísla řádků o jedničku.

Komutace patchů byla formálně značně studována, ale algoritmy pro řešení merge konfliktů při komutaci patchů zůstávají otevřenými výzkumnými otázkami. Komutace patchů však může být prokázána jako produkující „správné" výsledky sloučení, zatímco jiné strategie sloučení jsou převážně heuristiky, které se snaží vytvořit to, co uživatelé očekávají.

Unixový program flipdiff z balíčku „patchutils“ implementuje komutaci patchů pro tradiční patche vytvořené příkazem „diff -u“.

Weave merge (tkání) Weave merge je algoritmus, který nevyžaduje společného předka dvou souborů. Namísto toho sleduje, jak jsou jednotlivé řádky přidávány a mazány v derivovaných verzích souborů, a na základě těchto informací vytváří sloučený soubor.

Pro každý řádek v derivovaných souborech weave merge shromažďuje následující informace: které řádky mu předcházejí, které po něm následují a zda byl v nějaké fázi historie kterékoliv derivované verze smazán. Pokud byl řádek v kterékoliv derivované verzi smazán, nesmí být přítomen ve sloučené verzi. Ostatní řádky musí ve sloučené verzi být přítomny.

Řádky jsou seřazeny do pořadí, kde každý řádek následuje po všech řádcích, které mu v historii předcházely, a předchází všem řádkům, které po něm následovaly. Pokud tato omezení nepředstavují úplné uspořádání pro všechny řádky, pak řádky bez vzájemného uspořádání jsou konfliktující přídavky.

Weave merge byl zjevně používán komerčním systémem správy verzí BitKeeper a dokáže zvládnout některé problémové případy, kde třícestný merge produkuje špatné nebo nevhodné výsledky. Je také jednou z možností sloučení v nástroji GNU Bazaar a používá se v systému Codeville.

Odkazy Reference

Související články Git diff Verzování CVS

Kategorie:Systémy pro správu verzí