92:
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.
28:
684:
158:
199:
106:
373:(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.
415:
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
380:
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
376:
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
165:
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
91:
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, Knowledge allows two people to
411:
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
169:
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
356:
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.
311:(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.)
70:
Unstructured merge operates on raw text, typically using lines of text as atomic units. This is what Unix tools (diff/patch) and CVS tools (SVN, Git) use. This is limited, as a line of text does not represent the structure of source code.
148:
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.
43:(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
377:
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.
341:
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
330:
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 "
170:
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".
180:
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
290:
265:
345:, 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.
240:
220:
192:
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.
50:
In some cases, the merge can be performed automatically, because there is sufficient history information to reconstruct the changes, and the changes do not
304:
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
778:
54:. In other cases, a person must decide exactly what the resulting files should contain. Many revision control software tools include merge capabilities.
318:(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).
580:
811:
296:
Fortunately, in this case it can be shown that there are at most two possible candidate ancestors, and recursive three-way merge constructs a
423:
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
195:
There are awkward cases, particularly the "criss-cross merge", where a unique last common ancestor of the modified versions does not exist.
17:
1108:
914:
648:
573:
292:
are successively modified versions. The solution is shown in the right half: a virtual ancestor (the dashed circle) is created.
1026:
1016:
436:
979:
817:
759:
404:
Weave merge is an algorithm that does not make use of a common ancestor for two files. Instead, it tracks how single
1137:
566:
173:
Sections that are different in all three files are marked as a conflict situation and left for the user to resolve.
1115:
1101:
526:
338:
to re-apply (or remove) the changes into (or from) a text file, or a directory structure containing text files.
847:
498:
314:
Recursive three-way merge can only be used in situations where the tool has knowledge about the total ancestry
615:
544:
300:
by merging the non-unique ancestors first. This merge can itself suffer the same problem, so the algorithm
118:
1082:
446:
166:
that are to be merged. Three way merge can be done on raw text (sequence of lines) or on structured trees.
128:
202:
The "Criss-cross-merge" problem in software version control. In the left half 2 areas are being modified,
1067:
1021:
870:
854:
408:
are added and deleted in derivative versions of files, and produces the merged file on this information.
47:
and subsequently merged. The result is a single collection of files that contains both sets of changes.
705:
683:
629:
181:
51:
27:
122:
1142:
1038:
465:
623:
315:
763:
753:
988:
841:
640:
80:
44:
8:
973:
953:
792:
749:
270:
245:
127:
Please expand the section to include this information. Further details may exist on the
1055:
771:
533:(Mailing list). Message-ID <Pine.LNX.4.44.0504271254120.4678-100000@wax.eds.org>.
504:
225:
205:
598:
Years, where available, indicate the date of first stable release. Systems with names
921:
893:
723:
494:
389:
327:
835:
508:
486:
1062:
589:
79:
Structured merge tools, or AST merge, turn the source code into a fully resolved
36:
31:
Example history graph of a version-controlled project, with merges as red arrows
1050:
805:
370:
305:
157:
161:
C is the origin, A and B are derivatives of C, and D is the new output version
1131:
799:
785:
478:
490:
1087:
1043:
829:
558:
388:
from the "patchutils" package implements patch commutation for traditional
335:
995:
740:
419:
Weave merge was apparently used by the commercial revision control tool
198:
941:
900:
522:
424:
412:
version. For other lines, they must be present in the merged version.
83:. This allows for a fine-grained merge that avoid spurious conflicts.
1033:
947:
886:
420:
301:
1077:
934:
823:
654:
353:
105:
907:
711:
483:
Proceedings of the 2004 ACM symposium on
Document engineering
366:
349:
177:
62:
There are two types of merges: unstructured and structured.
717:
667:
660:
602:
are no longer maintained or have planned end-of-life dates.
441:
393:
331:
927:
485:. New York, New York, USA: ACM Press. pp. 1–10.
273:
248:
228:
208:
416:respect to each other are additions that conflict.
176:Three-way merging is implemented by the ubiquitous
427:revision control tool, and is used in Codeville.
284:
259:
234:
214:
1129:
125:) and the not-quite-weave merge BitKeeper uses.
574:
369:to merge changes, and is also implemented in
588:
187:
581:
567:
321:
476:
348:Like CVS started as a set of scripts on
197:
156:
26:
545:"Some properties of Darcs patch theory"
381:try to produce what users want to see.
14:
1130:
334:-u". This format can then be used by
562:
521:
479:"A three-way merge for XML documents"
65:
360:
99:
437:Comparison of file comparison tools
95:
74:
24:
152:
57:
25:
1154:
682:
104:
537:
515:
470:
459:
399:
13:
1:
466:Help:Edit conflict#Prevention
452:
365:Patch commutation is used in
527:"The criss-cross merge case"
447:Branching (revision control)
7:
430:
86:
10:
1159:
477:Lindholm, Tancred (2004).
182:Concurrent Versions System
1096:
1009:
963:
878:
869:
733:
698:
691:
680:
639:
614:
607:
596:
188:Recursive three-way merge
1138:Configuration management
590:Version control software
117:about Bazaar LCA merge (
18:Merge (revision control)
818:Software Change Manager
491:10.1145/1030397.1030399
343:fuzzy patch application
322:Fuzzy patch application
308:revision control tool.
316:directed acyclic graph
293:
286:
261:
236:
216:
162:
115:is missing information
32:
287:
262:
237:
217:
201:
160:
30:
271:
246:
226:
206:
285:{\displaystyle X''}
294:
282:
260:{\displaystyle X'}
257:
232:
212:
163:
66:Unstructured merge
33:
1125:
1124:
1051:Delta compression
1005:
1004:
865:
864:
855:Visual SourceSafe
708:(1986, 1990 in C)
678:
677:
384:The Unix program
361:Patch commutation
336:the patch program
235:{\displaystyle Y}
215:{\displaystyle X}
146:
145:
16:(Redirected from
1150:
982:(via Git) (2014)
976:(via Git) (2013)
879:Free/open-source
876:
875:
699:Free/open-source
696:
695:
686:
616:Free/open-source
612:
611:
583:
576:
569:
560:
559:
553:
551:
549:
541:
535:
534:
519:
513:
512:
474:
468:
463:
387:
298:virtual ancestor
291:
289:
288:
283:
281:
266:
264:
263:
258:
256:
241:
239:
238:
233:
221:
219:
218:
213:
141:
138:
132:
108:
100:
96:Merge algorithms
75:Structured merge
21:
1158:
1157:
1153:
1152:
1151:
1149:
1148:
1147:
1143:Version control
1128:
1127:
1126:
1121:
1092:
1063:File comparison
1001:
959:
861:
729:
718:QVCS Enterprise
687:
674:
635:
603:
592:
587:
557:
556:
547:
543:
542:
538:
520:
516:
501:
475:
471:
464:
460:
455:
433:
402:
385:
363:
324:
274:
272:
269:
268:
249:
247:
244:
243:
227:
224:
223:
207:
204:
203:
190:
155:
153:Three-way merge
142:
136:
133:
126:
109:
98:
89:
77:
68:
60:
58:Types of merges
37:version control
23:
22:
15:
12:
11:
5:
1156:
1146:
1145:
1140:
1123:
1122:
1120:
1119:
1112:
1105:
1097:
1094:
1093:
1091:
1090:
1085:
1080:
1075:
1070:
1065:
1060:
1059:
1058:
1048:
1047:
1046:
1036:
1031:
1030:
1029:
1019:
1013:
1011:
1007:
1006:
1003:
1002:
1000:
999:
993:
985:
984:
983:
977:
967:
965:
961:
960:
958:
957:
951:
945:
939:
931:
925:
919:
911:
905:
897:
891:
882:
880:
873:
867:
866:
863:
862:
860:
859:
851:
845:
839:
833:
827:
821:
815:
809:
806:Perforce Helix
803:
797:
789:
783:
775:
769:
768:
767:
757:
744:
737:
735:
731:
730:
728:
727:
721:
715:
709:
702:
700:
693:
689:
688:
681:
679:
676:
675:
673:
672:
664:
658:
652:
645:
643:
637:
636:
634:
633:
627:
620:
618:
609:
605:
604:
597:
594:
593:
586:
585:
578:
571:
563:
555:
554:
536:
525:(2005-04-28).
514:
499:
469:
457:
456:
454:
451:
450:
449:
444:
439:
432:
429:
401:
398:
362:
359:
323:
320:
280:
277:
255:
252:
231:
211:
189:
186:
154:
151:
144:
143:
112:
110:
103:
97:
94:
88:
85:
76:
73:
67:
64:
59:
56:
9:
6:
4:
3:
2:
1155:
1144:
1141:
1139:
1136:
1135:
1133:
1118:
1117:
1113:
1111:
1110:
1106:
1104:
1103:
1099:
1098:
1095:
1089:
1086:
1084:
1081:
1079:
1076:
1074:
1071:
1069:
1066:
1064:
1061:
1057:
1054:
1053:
1052:
1049:
1045:
1042:
1041:
1040:
1037:
1035:
1032:
1028:
1025:
1024:
1023:
1020:
1018:
1015:
1014:
1012:
1008:
997:
994:
991:
990:
986:
981:
978:
975:
972:
971:
970:Azure DevOps
969:
968:
966:
962:
955:
952:
949:
946:
943:
940:
937:
936:
932:
929:
926:
923:
920:
917:
916:
912:
909:
906:
903:
902:
898:
895:
892:
889:
888:
884:
883:
881:
877:
874:
872:
868:
857:
856:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
794:
790:
787:
786:Dimensions CM
784:
781:
780:
776:
773:
770:
765:
761:
758:
755:
751:
748:
747:
746:Azure DevOps
745:
742:
739:
738:
736:
732:
725:
722:
719:
716:
713:
710:
707:
704:
703:
701:
697:
694:
692:Client–server
690:
685:
670:
669:
665:
662:
659:
656:
653:
650:
649:The Librarian
647:
646:
644:
642:
638:
631:
628:
625:
622:
621:
619:
617:
613:
610:
606:
601:
595:
591:
584:
579:
577:
572:
570:
565:
564:
561:
552:, corollary 2
546:
540:
532:
528:
524:
518:
510:
506:
502:
496:
492:
488:
484:
480:
473:
467:
462:
458:
448:
445:
443:
440:
438:
435:
434:
428:
426:
422:
417:
413:
409:
407:
397:
395:
391:
382:
378:
374:
372:
368:
358:
355:
351:
346:
344:
339:
337:
333:
329:
319:
317:
312:
309:
307:
303:
299:
278:
275:
253:
250:
229:
209:
200:
196:
193:
185:
183:
179:
174:
171:
167:
159:
150:
140:
130:
124:
120:
116:
113:This section
111:
107:
102:
101:
93:
84:
82:
72:
63:
55:
53:
48:
46:
42:
38:
29:
19:
1114:
1107:
1100:
1072:
987:
933:
913:
899:
885:
853:
842:Team Concert
830:Surround SCM
791:
777:
666:
599:
539:
530:
517:
482:
472:
461:
418:
414:
410:
405:
403:
392:produced by
383:
379:
375:
364:
347:
342:
340:
325:
313:
310:
297:
295:
194:
191:
175:
172:
168:
164:
147:
137:January 2020
134:
114:
90:
78:
69:
61:
49:
40:
34:
1056:Interleaved
996:Plastic SCM
964:Proprietary
871:Distributed
741:AccuRev SCM
734:Proprietary
641:Proprietary
523:Cohen, Bram
400:Weave merge
302:recursively
1132:Categories
1109:Comparison
1083:Repository
942:GNU Bazaar
901:Code Co-op
724:Subversion
608:Local only
600:in italics
500:1581139381
453:References
425:GNU Bazaar
1034:Changeset
948:Mercurial
887:BitKeeper
800:Integrity
772:ClearCase
421:BitKeeper
129:talk page
1102:Category
1078:Monorepo
1017:Baseline
1010:Concepts
989:TeamWare
980:Services
954:Monotone
935:GNU arch
824:StarTeam
814:(1980s?)
766:) (2014)
760:Services
756:) (2005)
655:Panvalet
431:See also
386:flipdiff
354:GNU arch
279:″
254:′
87:Workflow
52:conflict
45:branches
836:Synergy
820:(1970s)
788:(1980s)
657:(1970s)
509:2863413
390:patches
184:(CVS).
41:merging
1039:Commit
1022:Branch
998:(2006)
992:(1992)
974:Server
956:(2003)
950:(2005)
944:(2005)
938:(2001)
930:(2005)
924:(2007)
922:Fossil
918:(2002)
910:(2002)
904:(1997)
896:(2017)
894:Breezy
890:(2000)
858:(1994)
850:(2003)
844:(2008)
838:(1990)
832:(2002)
826:(1995)
808:(1995)
802:(2001)
796:(1984)
782:(1994)
774:(1992)
750:Server
743:(2002)
726:(2000)
720:(1998)
714:(1998)
671:(1991)
663:(1985)
651:(1969)
632:(1973)
626:(1982)
507:
497:
1073:Merge
1044:Gated
1027:Trunk
908:Darcs
848:Vault
762:(via
752:(via
712:CVSNT
548:(PDF)
505:S2CID
406:lines
367:Darcs
350:diff3
328:patch
178:diff3
1116:List
1068:Fork
915:DCVS
812:SCLM
793:DSEE
779:CMVC
764:TFVC
754:TFVC
668:QVCS
661:PVCS
630:SCCS
495:ISBN
442:diff
396:-u.
394:diff
332:diff
267:and
222:and
123:file
119:tree
1088:Tag
928:Git
706:CVS
624:RCS
531:Git
487:doi
371:git
306:Git
81:AST
35:In
1134::
529:.
503:.
493:.
481:.
352:,
326:A
242:.
39:,
582:e
575:t
568:v
550:.
511:.
489::
276:X
251:X
230:Y
210:X
139:)
135:(
131:.
121:/
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
