Нұсқаларды біріктіру: автоматты және қолмен әдістері
Merge (version control)
Нұсқаларды басқарудағы біріктіру – файлдарға жасалған өзгерістерді үйлестіру. Автоматты немесе қолмен, қақтығыстарды шешіп, біртұтас нұсқаны құруға көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Версияны басқаруда біріктіру (немесе интеграция) – файлдардың нұсқамен бақыланатын жинағына енгізілген әр түрлі өзгерістерді үйлестіретін маңызды операция. Көбінесе, бұл қажеттілік туындайды, егер файл екі тәуелсіз тармақта өзгертіліп, содан кейін біріктірілсе. Нәтижесінде, екі жиын өзгерісті қамтитын файлдардың біртұтас жинағы құрылады. Кейбір жағдайларда, өзгерістерді қайта құруға жеткілікті тарих ақпараты болса және өзгерістер қақтығыс тудырмаса, біріктіру автоматты түрде жүзеге асырылуы мүмкін. Ал басқа жағдайларда, түпкі файлдарда қандай өзгерістер болу керектігін адам анықтауы тиіс. Көптеген нұсқаны басқару бағдарламалық құралдары біріктіру мүмкіндіктерін ұсынады.
In version control, merging (also called integration) is a fundamental operation that reconciles multiple changes made to a version controlled collection of files. Most often, it is necessary when a file is modified on two independent branches and subsequently merged. The result is a single collection of files that contains both sets of changes. In some cases, the merge can be performed automatically, because there is sufficient history information to reconstruct the changes, and the changes do not conflict. In other cases, a person must decide exactly what the resulting files should contain. Many revision control software tools include merge capabilities.
Бірігу түрлері
Құрамалардың екі түрі бар: құрылымсыз және құрылымды.
There are two types of merges: unstructured and structured.
Жұмыс ағыны
Автоматты біріктіру – нұсқауды басқару бағдарламалық қамтамасы бір мезгілде (логикалық тұрғыдан) жасалған өзгерістерді келістіргенде атқаратын әрекет. Сондай-ақ, бір мазмұнды бір уақытта өңдеуге рұқсат беретін басқа бағдарламалық жасақтамалар да автоматты біріктіруді қолданады. Мысалы, Уикипедия екі адамға бір мақаланы бірден өңдеуге мүмкіндік береді; екінші өңдеуші сақтағанда, олардың өзгерістері бұрынғы өзгерістерді жаңартудың орнына мақалаға біріктіріледі. Қолмен біріктіру – адамдар егер файлдардағы айырмашылықтарды келістіруге тиіс болса (мүмкін біріктіру құралдарының көмегімен) қолданатын тәсіл. Мысалы, егер екі жүйеде конфигурациялық файлдың сәл өзгеше нұсқалары болса және пайдаланушы екеуінде де қажетті өзгерістерді алғысы келсе, бұл әдетте конфигурациялық файлдарды қолмен біріктіру арқылы және екі дереккөзден қажетті өзгерістерді таңдау арқылы жүзеге асырылады (бұл екіталай біріктіру деп те аталады). Автоматты біріктіру өзгерістерлер қақтығысқа ұшырағанда қолмен біріктіру қажет болады; мысалы, өте сирек автоматты біріктіру құралдары кодтың бір жолына екі өзгерісті біріктіре алады (мысалы, функцияның атын өзгерту және түсініктеме қосу). Мұндай жағдайларда нұсқауды басқару жүйелері пайдаланушыға жоспарланған біріктіру нәтижесін анықтау үшін жүгінеді.
Automatic merging is what version control software does when it reconciles changes that have happened simultaneously (in a logical sense). Also, other pieces of software deploy automatic merging if they allow for editing the same content simultaneously. For instance, Wikipedia allows two people to edit the same article at the same time; when the latter contributor saves, their changes are merged into the article instead of overwriting the previous set of changes. Manual merging is what people have to resort to (possibly assisted by merging tools) when they have to reconcile files that differ. For instance, if two systems have slightly differing versions of a configuration file and a user wants to have the good stuff in both, this can usually be achieved by merging the configuration files by hand, and picking the wanted changes from both sources (this is also called two way merging). Manual merging is also required when automatic merging runs into a change conflict; for instance, very few automatic merge tools can merge two changes to the same line of code (say, one that changes a function name, and another that adds a comment). In these cases, revision control systems resort to the user to specify the intended merge result.
Біріктіру алгоритмдері
Автоматты біріктіруге қатысты көптеген әртүрлі тәсілдер бар, олардың арасында көзге көрінбейтін айырмашылықтар бар. Көзге түсетін біріктіру алгоритмдеріне үш жолды біріктіру, рекурсивті үш жолды біріктіру, шамалы жапсырманы қолдану, тоқу арқылы біріктіру және жапсырма алмастыру жатады.
There are many different approaches to automatic merging, with subtle differences. The more notable merge algorithms include three way merge, recursive three way merge, fuzzy patch application, weave merge, and patch commutation.
Үшжақты бірігу
Үш жолды біріктіру "А" файлы мен "В" файлы арасындағы автоматты айырмашылықтарды талдағаннан кейін, сондай-ақ екі файлдың – "С" файлының бастауын немесе ортақ ата-бабасын ескере отырып жүзеге асырылады. Бұл шамалы дәлдіктегі біріктіру әдісі, бірақ кеңінен қолданылады, себебі біріктірілуге тиіс өзгерістерді қалпына келтіру үшін тек бір ортақ ата-баба ғана қажет. Үш жолды біріктіруді қара мәтінде (жолдар тізбегі) немесе құрылымдық ағаштарда жасауға болады. Үш жолды біріктіру үш файлдың екеуінде ғана бірдей болатын бөлімдерді іздейді. Мұндай жағдайда бөлімнің екі нұсқасы болады, ортақ ата-баба "С" нұсқасы жойылады, ал ерекшеленетін нұсқасы шығысқа сақталады. Егер "А" мен "В" келіссе, нәтиже сол күйінде шығарылады. "А" және "С" файлында бірдей бөлім "В" файлындағы өзгертілген нұсқаны шығарады, ал "В" және "С" файлында бірдей бөлім "А" файлындағы нұсқаны шығарады. Үш файлдың барлығында да әртүрлі бөлімдер қайшылық ретінде белгіленеді және оларды шешу пайдаланушыға жүктеледі. Үш жолды біріктіруді diff3 бағдарламасы іске асырады және бұл файлдық құлыптауға негіделген нұсқаларды басқару жүйелерінен біріктіруге негіделген нұсқаларды басқару жүйелеріне көшуге мүмкіндік берген маңызды жаңалық болды. Бұл жүйе Concurrent Versions System (CVS) жүйесінде кеңінен қолданылады.
A three way merge is performed after an automated difference analysis between a file "A" and a file "B" while also considering the origin, or common ancestor, of both files "C". It is a rough merging method, but widely applicable since it only requires one common ancestor to reconstruct the changes that are to be merged. Three way merge can be done on raw text (sequence of lines) or on structured trees. The three way merge looks for sections which are the same in only two of the three files. In this case, there are two versions of the section, and the version which is in the common ancestor "C" is discarded, while the version that differs is preserved in the output. If "A" and "B" agree, that is what appears in the output. A section that is the same in "A" and "C" outputs the changed version in "B", and likewise a section that is the same in "B" and "C" outputs the version in "A". Sections that are different in all three files are marked as a conflict situation and left for the user to resolve. Three way merging is implemented by the ubiquitous diff3 program, and was the central innovation that allowed the switch from file locking based revision control systems to merge based revision control systems. It is extensively used by the Concurrent Versions System (CVS).
Үш жолды рекурсивті біріктіру
Үш жолды біріктіруге негізделген нұсқаларды басқару құралдары кеңінен таралған, бірақ бұл техника негізінен біріктірілетін нұсқалардың ортақ ата-тегін табуға байланысты. Әсіресе "қырлы-сырлы біріктіру" сияқты қиын жағдайлар бар, онда өзгертілген нұсқалардың бірегей соңғы ортақ ата-тегі болмайды. Ақыртымызға орай, мұндай жағдайда ең көп дегенде екі мүмкін ата-тегі бар екені көрсетіледі, ал рекурсивті үш жолды біріктіру бірінші кезекте бірегей емес ата-тегтерді біріктіру арқылы жасанды ата-тег құрады. Бұл біріктірудің өзі сол мәселеге ұшырауы мүмкін, сондықтан алгоритм оларды рекурсивті түрде біріктіреді. Нұсқалар тарихында шектеулі болғандықтан, процесс әрқашан аяқталады деп кепілдік беріледі. Бұл техниканы Git нұсқаларды басқару құралы қолданады. (Git-тің рекурсивті біріктіруді іске асыруы басқа да қиын жағдайларды шешеді, мысалы, бір нұсқада өзгертілген және екінші нұсқада аты өзгертілген файл, бірақ бұл оның үш жолды біріктіруді іске асыруының кеңейтілген мүмкіндіктері; үш нұсқаны біріктіру әдісінің бөлігі емес.) Рекурсивті үш жолды біріктіруді тек құрал біріктірілетін туындылардың толық ата-тегі туралы мәліметтерге ие болған жағдайларда ғана қолдануға болады. Сондықтан, туындылар немесе біріктірулер өздерінің басты нұсқаларын толық көрсетпеген жағдайларда оны қолдануға болмайды.
Three way merge based revision control tools are widespread, but the technique fundamentally depends on finding a common ancestor of the versions to be merged. There are awkward cases, particularly the "criss cross merge", where a unique last common ancestor of the modified versions does not exist. Fortunately, in this case it can be shown that there are at most two possible candidate ancestors, and recursive three way merge constructs a virtual ancestor by merging the non unique ancestors first. This merge can itself suffer the same problem, so the algorithm recursively merges them. Since there is a finite number of versions in the history, the process is guaranteed to eventually terminate. This technique is used by the Git revision control tool. (Git's recursive merge implementation also handles other awkward cases, like a file being modified in one version and renamed in the other, but those are extensions to its three way merge implementation; not part of the technique for finding three versions to merge.) Recursive three way merge can only be used in situations where the tool has knowledge about the total ancestry directed acyclic graph (DAG) of the derivatives to be merged. Consequently, it cannot be used in situations where derivatives or merges do not fully specify their parent(s).
Жапсырманы жапсыру
Жаңарту – файлға енгізілген өзгерістердің сипаттамасын қамтитын файл. Unix жүйесінде мәтіндік файлдарға енгізілген өзгерістерді "diff u" форматындағы жаңартулар түрінде тарату дәстүрі қалыптасқан. Бұл форматты жаңарту бағдарламасы мәтіндік файлға немесе мәтіндік файлдарды қамтитын каталог құрылымына өзгерістерді қайта қолдануға (немесе жоюға) пайдаланады. Дегенмен, жаңарту бағдарламасы жаңарту жасау үшін пайдаланылған бастапқы файлға толық сәйкес келмейтін файлға жаңартуды қолдану мүмкіндігін де ұсынады. Бұл процеске «шала қолдану» дейді, ол үш тармақты біріктірудің асимметриялық түріне әкеледі, егер жаңарту бағдарламасы оларды қолдануға орын таба алмаса, жаңартудағы өзгерістер жойылады. CVS diff3 скрипттері жиынтығынан басталып, GNU arch жаңарту бағдарламасы да скрипттер жиынтығынан бастау алды. Алайда, шала қолдану әдісі сенімділігі төмен, кейде жеткілікті контексті жоқ (әсіресе жаңа файл құратын) жаңартуларды қате қолдануы мүмкін, ал кейде екі түрлі нұсқасы да жасаған жоюларын қолданбайды.
A patch is a file that contains a description of changes to a file. In the Unix world, there has been a tradition to disseminate changes to text files as patches in the format that is produced by "diff u". This format can then be used by the patch program to re apply (or remove) the changes into (or from) a text file, or a directory structure containing text files. However, the patch program also has some facilities to apply the patch into a file that is not exactly similar as the origin file that was used to produce the patch. This process is called fuzzy patch application, and results in a kind of asymmetric three way merge, where the changes in the patch are discarded if the patch program cannot find a place in which to apply them. Like CVS started as a set of scripts on diff3, GNU arch started as a set of scripts on patch. However, fuzzy patch application is a relatively untrustworthy method, sometimes misapplying patches that have too little context (especially ones that create a new file), sometimes refusing to apply deletions that both derivatives have done.
Жапсырманы ауыстыру
Пач коммутациясы Darcs жүйесінде өзгерістерді біріктіру үшін қолданылады, сондай-ақ git жүйесінде де іске асырылады (бірақ "rebasing" деп аталады). Патч коммутациясы арқылы біріктіру дегеніміз – патчтардың (яғни, өзгерістердің сипаттамаларының) ретін өзгерту, осылайша олар сызықтық тарихты құрайды. Егер екі патч ортақ жағдайға байланысты жасалса, біріктіру кезінде олардың біреуі екіншісінің негізінде жасалғандай етіп қайта жазылады. Патч коммутациясы үшін туынды файлдар жасалған нақты өзгерістерді сақтау немесе қайта құру қажет. Осы нақты өзгерістерден, олардың біреуін екіншісіне негіздеу үшін қалай өзгерту керектігін есептеуге болады. Мысалы, егер A патчы F файлының 7-жолынан кейін "X" жолын, ал B патчы F файлының 310-жолынан кейін "Y" жолын қосса, егер B патчы A патчына негізделсе, оны қайта жазу қажет: "Y" жолын F файлының 311-жолынан кейін қосу керек, себебі A патчы қосылған жол жол нөмірін бірге жылдырады. Патч коммутациясы кеңінен зерттелді, бірақ патч коммутациясындағы біріктіру қақтығыстарын шешу алгоритмдері әлі де зерттеу мәселесі болып табылады. Дегенмен, патч коммутациясы "дұрыс" біріктіру нәтижелерін беретінін дәлелдеуге болады, ал басқа біріктіру стратегиялары көбінесе пайдаланушылардың көруін қалайтынын табуға бағытталған эвристикалық тәсілдер болып табылады. Unix жүйесіндегі flipdiff бағдарламасы, "patchutils" пакетінен, diff u командасымен жасалған дәстүрлі патчтар үшін патч коммутациясын іске асырады.
Patch commutation is used in Darcs to merge changes, and is also implemented in git (but called "rebasing"). Patch commutation merge means changing the order of patches (i. e. descriptions of changes) so that they form a linear history. In effect, when two patches are made in the context of a common situation, upon merging, one of them is rewritten so that it appears to be done in the context of the other. Patch commutation requires that the exact changes that made derivative files are stored or can be reconstructed. From these exact changes it is possible to compute how one of them should be changed in order to rebase it on the other. For instance, if patch A adds line "X" after line 7 of file F and patch B adds line "Y" after line 310 of file F, B has to be rewritten if it is rebased on A: the line must be added on line 311 of file F, because the line added in A offsets the line numbers by one. Patch commutation has been studied a great deal formally, but the algorithms for dealing with merge conflicts in patch commutation still remain open research questions. However, patch commutation can be proven to produce "correct" merge results where other merge strategies are mostly heuristics that try to produce what users want to see. The Unix program flipdiff from the "patchutils" package implements patch commutation for traditional patches produced by diff u.
Ұстасу біріктірілуі
Weave merge – екі файлдың ортақ ата-тегін пайдаланбайтын алгоритм. Оның орнына, файлдардың туынды нұсқаларындағы жекелеген жолдардың қосылуы мен жойылуын қадағалайды және осы ақпарат негізінде біріктірілген файлды құрайды. Weave merge, туынды файлдардағы әрбір жол үшін келесі ақпаратты жинайды: оған дейінгі жолдар, одан кейінгі жолдар және ол туындының тарихының қандай да бір кезеңінде жойылған-жойылмағаны. Егер туындының біреуінде жол жойылған болса, ол біріктірілген нұсқада болуы керек емес. Ал қалған жолдар біріктірілген нұсқада болуы тиіс. Жолдар тарихтың белгілі бір кезеңінде оған дейінгі барлық жолдардан кейін және одан кейінгі барлық жолдардан бұрын орналасатындай ретпен сұрыпталады. Егер осы шектеулер барлық жолдарды толық ретке келтірмесе, бір-біріне қатысты реті анықталмаған жолдар – қақтығыс тудыратын қосымшалар болып табылады. Weave merge коммерциялық BitKeeper нұсқауларын басқару құралында қолданылған және үш таңбалы біріктіру қате немесе нашар нәтижелер беретін кейбір қиын жағдайларды шеше алады. Бұл GNU Bazaar нұсқауларын басқару құралының біріктіру опцияларының бірі және Codeville-де қолданылады.
Weave merge is an algorithm that does not make use of a common ancestor for two files. Instead, it tracks how single lines are added and deleted in derivative versions of files, and produces the merged file on this information. For each line in the derivative files, weave merge collects the following information: which lines precede it, which follow it, and whether it was deleted at some stage of either derivative's history. If either derivative has had the line deleted at some point, it must not be present in the merged version. For other lines, they must be present in the merged version. The lines are sorted into an order where each line is after all lines that have preceded it at some point in history, and before all lines that have followed it at some point in history. If these constraints do not give a total ordering for all lines, then the lines that do not have an ordering with respect to each other are additions that conflict. Weave merge was apparently used by the commercial revision control tool BitKeeper and can handle some of the problem cases where a three way merge produces wrong or bad results. It is also one of the merge options of the GNU Bazaar revision control tool, and is used in Codeville.