Show More
@@ -0,0 +1,115 b'' | |||
|
1 | Bid merge is a feature introduced in Mercurial 3.0, a merge algorithm for | |
|
2 | dealing with complicated merges. | |
|
3 | ||
|
4 | Bid merge is controled by the `merge.preferancestor` configuration option. The | |
|
5 | default is set to `merge.preferancetors=*` and enable bid merge. Mercurial will | |
|
6 | perform a bid merge in the cases where a merge otherwise would emit a note: | |
|
7 | using X as ancestor of X and X message. | |
|
8 | ||
|
9 | Problem it is solving | |
|
10 | ===================== | |
|
11 | ||
|
12 | Mercurial's core merge algorithm is the traditional "three-way merge". This | |
|
13 | algorithm combines all the changes in two changesets relative to a common | |
|
14 | ancestor. But with complex DAGs, it is often possible to have more than one | |
|
15 | "best" common ancestor, with no easy way to distinguish between them. | |
|
16 | ||
|
17 | For example, C and D has 2 common ancestors in the following graph:: | |
|
18 | ||
|
19 | C D | |
|
20 | |\ /| | |
|
21 | | x | | |
|
22 | |/ \| | |
|
23 | A B | |
|
24 | \ / | |
|
25 | R | |
|
26 | ||
|
27 | Mercurial used to arbitrarily chooses the first of these, which can result in | |
|
28 | various issues: | |
|
29 | ||
|
30 | * unexpected hard 3-way merges that would have been completely trivial if | |
|
31 | another ancestor had been used | |
|
32 | ||
|
33 | * conflicts that have already been resolved may reappear | |
|
34 | ||
|
35 | * changes that have been reversed can silently oscillate | |
|
36 | ||
|
37 | One common problem is a merge which with the "right" ancestor would be trivial | |
|
38 | to resolve because only one side changed. Using another ancestor where the same | |
|
39 | lines are different, it will give an annoying 3-way merge. | |
|
40 | ||
|
41 | Other systems like Git have attacked some of these problems with a so-called | |
|
42 | "recursive" merge strategy, that internally merges all the possible ancestors | |
|
43 | to produce a single "virtual" ancestor to merge against. This is awkward as the | |
|
44 | internal merge itself may involve conflicts (and possibly even multiple levels | |
|
45 | of recursion), which either requires choosing a conflict disposition (e.g. | |
|
46 | always choose the local version) or exposing the user to extremely confusing | |
|
47 | merge prompts for old revisions. Generating the virtual merge also potentially | |
|
48 | involves invoking filters and extensions. | |
|
49 | ||
|
50 | Concept | |
|
51 | ======= | |
|
52 | ||
|
53 | (Bid merge is pretty much the same as Consensus merge.) | |
|
54 | ||
|
55 | Bid merge is a strategy that attempts to sensibly combine the results of the | |
|
56 | multiple possible three-way merges directly without producing a virtual | |
|
57 | ancestor. The basic idea is that for each ancestor, we perform a top-level | |
|
58 | manifest merge and generate a list of proposed actions, which we consider | |
|
59 | "bids". We then make an "auction" among all the bids for each file and pick the | |
|
60 | most favourable. Some files might be trivial to merge with one ancestor, other | |
|
61 | files with another ancestor. | |
|
62 | ||
|
63 | The most obvious advantage of considering multiple ancestors is the case where | |
|
64 | some of the bids for a file is a "real" (interactive) merge but where one or | |
|
65 | more bids just take on of the parent revisions. A bid for just taking an | |
|
66 | existing revision is very simple and low risk and is an obvious winner. | |
|
67 | ||
|
68 | The auction algorithm for merging the bids is so far very simple: | |
|
69 | ||
|
70 | * If there is consensus from all the ancestors, there is no doubt what to do. A | |
|
71 | clever result will be indistinguishable from just picking a random bid. The | |
|
72 | consensus case is thus not only trivial, it is also already handled | |
|
73 | perfectly. | |
|
74 | ||
|
75 | * If "keep local" or "get from other" actions is an option (and there is only | |
|
76 | one such option), just do it. | |
|
77 | ||
|
78 | * If the auction doesn't have a single clear winner, pick one of the bids | |
|
79 | "randomly" - just as it would have done if only one ancestor was considered. | |
|
80 | ||
|
81 | This meta merge algorithm has room for future improvements, especially for | |
|
82 | doing better than picking a random bid. | |
|
83 | ||
|
84 | Some observations | |
|
85 | ================= | |
|
86 | ||
|
87 | Experience with bid merge shows that many merges that actually have a very | |
|
88 | simple solution (because only one side changed) only can be solved efficiently | |
|
89 | when we start looking at file content in filemerge ... and it thus also | |
|
90 | requires all ancestors passed to filemerge. That is because Mercurial includes | |
|
91 | the history in filelog hashes. A file with changes that ends up not changing | |
|
92 | the content (could be change + backout or graft + merge or criss cross merges) | |
|
93 | still shows up as a changed file to manifestmerge. (The git data model has an | |
|
94 | advantage here when it uses hashes of content without history.) One way to | |
|
95 | handle that would be to refactor manifestmerge, mergestate/resolve and | |
|
96 | filemerge so they become more of the same thing. | |
|
97 | ||
|
98 | There is also cases where different conflicting chunks could benefit from using | |
|
99 | multiple ancestors in filemerge - but that will require merge tools with fancy | |
|
100 | support for using multiple ancestors in 3+-way merge. That is left as an | |
|
101 | exercise for another day. That seems to be a case where "recursive merge" has | |
|
102 | an advantage. | |
|
103 | ||
|
104 | The current manifest merge actions are very low level imperative and not | |
|
105 | symmetrical. They do not only describe how two manifests should be merged, they | |
|
106 | also describe a strategy for changing a context from a state where it is one of | |
|
107 | the parents to the state where it is the result of the merge with the other | |
|
108 | parent. I can imagine that manifestmerge could be simplified (and made more | |
|
109 | suitable for in memory merges) by separating the abstract merge actions from | |
|
110 | the actual file system operation actions. A more clever wcontext could perhaps | |
|
111 | also take care of some of the branchmerge special cases. | |
|
112 | ||
|
113 | We assume that the definition of Mercurial manifest merge will make sure that | |
|
114 | exactly the same files will be produced, no matter which ancestor is used. That | |
|
115 | assumption might be wrong in very rare cases that really not is a problem. |
@@ -345,6 +345,11 b' def loaddoc(topic, subdir=None):' | |||
|
345 | 345 | |
|
346 | 346 | internalstable = sorted( |
|
347 | 347 | [ |
|
348 | ( | |
|
349 | [b'bid-merge'], | |
|
350 | _(b'Bid Merge Algorithm'), | |
|
351 | loaddoc(b'bid-merge', subdir=b'internals'), | |
|
352 | ), | |
|
348 | 353 | ([b'bundle2'], _(b'Bundle2'), loaddoc(b'bundle2', subdir=b'internals')), |
|
349 | 354 | ([b'bundles'], _(b'Bundles'), loaddoc(b'bundles', subdir=b'internals')), |
|
350 | 355 | ([b'cbor'], _(b'CBOR'), loaddoc(b'cbor', subdir=b'internals')), |
@@ -1094,6 +1094,7 b' internals topic renders index of availab' | |||
|
1094 | 1094 | |
|
1095 | 1095 | To access a subtopic, use "hg help internals.{subtopic-name}" |
|
1096 | 1096 | |
|
1097 | bid-merge Bid Merge Algorithm | |
|
1097 | 1098 | bundle2 Bundle2 |
|
1098 | 1099 | bundles Bundles |
|
1099 | 1100 | cbor CBOR |
@@ -3439,6 +3440,13 b' Sub-topic indexes rendered properly' | |||
|
3439 | 3440 | <tr><td colspan="2"><h2><a name="topics" href="#topics">Topics</a></h2></td></tr> |
|
3440 | 3441 | |
|
3441 | 3442 | <tr><td> |
|
3443 | <a href="/help/internals.bid-merge"> | |
|
3444 | bid-merge | |
|
3445 | </a> | |
|
3446 | </td><td> | |
|
3447 | Bid Merge Algorithm | |
|
3448 | </td></tr> | |
|
3449 | <tr><td> | |
|
3442 | 3450 | <a href="/help/internals.bundle2"> |
|
3443 | 3451 | bundle2 |
|
3444 | 3452 | </a> |
General Comments 0
You need to be logged in to leave comments.
Login now