Scalanie (system kontroli wersji)

Istnieją dwa rodzaje scalań: automatyczne i ręczne.

Automatyczne scalanie jest wykonywane przez system kontroli wersji, który musi połączyć zmiany wprowadzone w tym samym czasie (w sensie logicznym). Również oprogramowanie wykonuje scalanie automatyczne, jeśli pozwala na równoczesną edycję tej samej treści. Na przykład Wikipedia pozwala dwóm osobom zmieniać ten sam artykuł w tym samym czasie; jak późniejszy użytkownik zapisuje swoje zmiany, to nie nadpisuje treści już dodanych lecz obie wersje są ze sobą scalane.

Ręczne scalanie ma miejsce wtedy gdy osoba chce połączyć dwa różniące się pliki w jeden, często posługując się odpowiednimi narzędziami wspomagającymi. Na przykład jeśli dwa systemy mają nieznacznie różniące się pliki konfiguracyjne, użytkownik może je porównać i wybrać to co lepsze z jednego i drugiego uzyskując nowe i lepsze rozwiązanie (taki model nazywa się scalaniem dwustronnym). Ręczne scalanie jest również konieczne w przypadku, gdy automatyczne scalanie trafi na konflikt; na przykład niewiele systemów kontroli wersji potrafi scalić zmiany, które dotyczą tej samej linii kodu (jedna może polegać na zmianie nazwy funkcji, a druga być dodanym komentarzem). W takich przypadkach system kontroli wersji decyzję jak scalić podany fragment przekazuje użytkownikowi.

Algorytmy scalające są obszarem aktywnych badań. Wobec tego istnieje wiele różnych rozwiązań na scalanie automatyczne, które się od siebie delikatnie różnią. Najbardziej zauważalne algorytmy to scalanie trójstronne, rekursywne scalanie trójstronne, fuzzy patch application, weave merge, i patch commutation.

Scalanie trójstronne

Scalanie trójstronne (z uwzględnieniem wspólnego przodka^[1]) jest wykonywane po wcześniejszej analizie różnic między plikiem „A” i plikiem „B” z uwzględnieniem wspólnego pochodzenia obu plików. Jest to szeroko rozpowszechniona metoda, gdyż wymaga tylko jednego przodka aby zrekonstruować zmiany, które następnie mają być scalone.

Scalanie trójstronne korzysta z przodka w celu ustalenia, które fragmenty się nie zmieniły a które uległy zmianie w jednym lub obu plikach. Bloki, które nie uległy zmianom w obu nowych plikach pozostają bez zmian. Bloki, które się zmieniły tylko w jednym z plików, są wykorzystywane w tej zmienionej postaci. Bloki zmienione w obu wersjach są wykorzystane tylko wtedy gdy ich zmienione wersje są identyczne, w przeciwnym razie są oznaczane jako konflikt i pozostawione do rozwiązania przez użytkownika.

Scalanie trójstronne jest realizowane przez wszechobecny program diff3, i stanowiło podstawę innowacji, która pozwoliła zamienić systemy kontroli wersji z blokowaniem plików na nowe z mechanizmem scalającym zmiany. Jest ono intensywnie wykorzystywane przez CVS.

Rekursywne scalanie trójstronne

Powszechne użycie scalania trójstronnego w systemach kontroli wersji wykazało przypadki, w których prostolinijne zastosowanie scalania trójstronnego może prowadzić do fałszywych konfliktów a nawet czasami przywracania odrzuconych poprawek. Przykłady takich zachowań zawierają scalanie zmian na krzyż^[2] i konflikty po zmianie nazwy pliku.

Problemy z trójstronnym scalaniem pojawiają się w przypadku, gdy stany pochodne nie mają unikalnego ostatniego wspólnego przodka (LCA – ang. latest common ancestor). Aby temu zaradzić, w rekursywnym scalaniu trójstronnym tworzony jest najpierw wirtualny przodek przez scalenie nieunikalnych przodków. Metodę tę stosuje oprogramowanie Git.

Rekursywne scalanie trójstronne może być zastosowane tylko wtedy gdy narzędzie ma całkowitą wiedzę o przodkach do scalenia w postaci DAG (ang. directed acyclic graph). W efekcie nie ma ono zastosowania, jeśli pliki pochodne nie określają w pełni swoje pierwotne wersje.

Łatanie

Łata to plik, który zawiera opis zmian dla pliku. W systemach Unix stało się tradycją rozpowszechnianie zmian w plikach tekstowych w postaci wyników polecenia diff -u. Następnie przy pomocy polecenia patch^[3] można takie zmiany dodać (albo usunąć) w pliku tekstowym lub drzewie katalogów zawierającego pliki tekstowe.

Jednakże program „łatający” korzysta z pewnych ułatwień pozwalających zastosować zmiany na plikach, które nie są identyczne z pierwotnymi plikami, z których łata została wygenerowana. Proces ten nazywany jest „łataniem rozmytym” (ang. fuzzy patch application)^[4] i objawia się swego rodzaju niesymetrycznym scalaniem trójstronnym, w którym zmiany z łaty są ignorowane jeśli program łatający nie potrafi znaleźć miejsca, w którym należy je nanieść.

Tak jak CVS miał swoje początki jako zbiór skryptów z poleceniem diff3, tak GNU arch zaczął jako skrypt z poleceniem patch. Jednak łatanie rozmyte jest metodą względnie niepewną, czasami umieszczając poprawki, które mają zbyt mały kontekst, w nieprawidłowym miejscu (zwłaszcza te, które tworzą nowy plik) lub nie usuwają tekstu przeznaczonego do skasowania.

Scalanie splotowe

Scalanie splotowe to algorytm, który nie korzysta z przodka obu plików. W zamian śledzi jak pojedyncze linie są dodawane i usuwane w potomnych wersjach pliku i dzięki tej informacji tworzy scalony plik.

Dla każdej linii w potomnym pliku, scalanie splotowe zbiera następujące dane: które linie ją poprzedzają, które następują po niej i czy była skasowana w jakimś etapie historii wersji. Jeśli jakikolwiek wariant miał tę linię usuniętą to nie może się ona pojawić w wersji scalonej. Pozostałe linie muszą być obecne w wersji scalonej.

Linie są sortowane według kolejności, w której każda linia jest po wszystkich liniach, które ją poprzedzały w jakimś punkcie historii i przed wszystkimi liniami, które występowały po niej też w jakimś punkcie historii. Jeśli to ograniczenie nie pozwala posortować wszystkich linii, to linie, które nie udało się posortować względem siebie stanowią konflikt.

Scalanie splotowe było najwyraźniej używane w komercyjnej wersji BitKeeper i radziło sobie z problematycznymi przypadkami, w których scalanie trójstronne dawało błędne lub złe wyniki. Jest ono również jedną z opcji scalania w GNU Bazaar^[5] oraz jest stosowane przez Codeville.

Zmiana bazy

Scalanie przez zmianę bazy jest zaimplementowane w oprogramowaniu git (polecenie rebase^[6]) oraz w Darcs (zwane jako ang. patch commutation^[7]). Scalanie przez zmianę bazy oznacza zmienianie kolejności łat (np. opisów zmian) w taki sposób, że tworzą liniową historię. W efekcie, kiedy dwie łaty są zrobione w tej samej sytuacji, po scalaniu, jedna z nich będzie przekształcona w taki sposób, że objawi się jakby była wykonana w kontekście tej drugiej.

Zmiana bazy wymaga aby dokładne zmiany, które tworzą pliki pochodne, były przechowane lub mogły być odtworzone. Z takich dokładnych zmian jest możliwe określenie jak jedna z nich powinna być zmieniona aby następnie uporządkować ją względem drugiej. Na przykład jeśli łata A dodaje linię „X” po linii 7 pliku F a łata B dodaje linię „Y” po linii 310 pliku F, B musi być przepisane jeśli następuje zmiana bazy względem A: dodana linia musi być umieszczona po linii 311 pliku F, ponieważ linia dodana przez A przesuwa numery linii o jeden.

Zmiana bazy została poddana wielu formalnym badaniom, lecz algorytmy radzące sobie z konfliktami przy zmianie bazy wciąż pozostawiają otwarte pytania badawcze. Jednak można udowodnić, że zmiana bazy dostarcza „prawidłowe” wyniki scalania podczas gdy inne strategie są głównie heurystyczne i starają się dostarczyć to, co użytkownik chce zobaczyć.

W systemie Unix program flipdiff z pakietu „patchutils” dostarcza metodę scalania przez zmianę bazy dla tradycyjnych łat utworzonych przez diff -u.