Mercurial > hg
annotate mercurial/helptext/internals/bid-merge.txt @ 45203:ae5c1a3bc339
commitctx: extract the function in a dedicated module
the function have few callers (< 15) is quite long a mostly independent from the
repository itself. It seems like a good candidate to reduce the bloatness of the
localrepository class. Extracting it will help us cleaning the code up and
splitting it into more reasonable-size function.
We don't use a copy trick because the amount of code extract is quite small
(<5%) and the de-indent means every single line change anyway. So this is not
deemed valuable to do so.
This is part of a larger refactoring/cleanup of the commitctx code to clarify
and augment the logic gathering metadata useful for copy tracing. The current
code is a tad too long and entangled to make such update easy.
Differential Revision: https://phab.mercurial-scm.org/D8709
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Mon, 06 Jul 2020 23:14:52 +0200 |
parents | 79f6f9fa18c1 |
children |
rev | line source |
---|---|
45059
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
1 Bid merge is a feature introduced in Mercurial 3.0, a merge algorithm for |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
2 dealing with complicated merges. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
3 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
4 Bid merge is controled by the `merge.preferancestor` configuration option. The |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
5 default is set to `merge.preferancetors=*` and enable bid merge. Mercurial will |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
6 perform a bid merge in the cases where a merge otherwise would emit a note: |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
7 using X as ancestor of X and X message. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
8 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
9 Problem it is solving |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
10 ===================== |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
11 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
12 Mercurial's core merge algorithm is the traditional "three-way merge". This |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
13 algorithm combines all the changes in two changesets relative to a common |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
14 ancestor. But with complex DAGs, it is often possible to have more than one |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
15 "best" common ancestor, with no easy way to distinguish between them. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
16 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
17 For example, C and D has 2 common ancestors in the following graph:: |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
18 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
19 C D |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
20 |\ /| |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
21 | x | |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
22 |/ \| |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
23 A B |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
24 \ / |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
25 R |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
26 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
27 Mercurial used to arbitrarily chooses the first of these, which can result in |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
28 various issues: |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
29 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
30 * unexpected hard 3-way merges that would have been completely trivial if |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
31 another ancestor had been used |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
32 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
33 * conflicts that have already been resolved may reappear |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
34 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
35 * changes that have been reversed can silently oscillate |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
36 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
37 One common problem is a merge which with the "right" ancestor would be trivial |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
38 to resolve because only one side changed. Using another ancestor where the same |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
39 lines are different, it will give an annoying 3-way merge. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
40 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
41 Other systems like Git have attacked some of these problems with a so-called |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
42 "recursive" merge strategy, that internally merges all the possible ancestors |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
43 to produce a single "virtual" ancestor to merge against. This is awkward as the |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
44 internal merge itself may involve conflicts (and possibly even multiple levels |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
45 of recursion), which either requires choosing a conflict disposition (e.g. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
46 always choose the local version) or exposing the user to extremely confusing |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
47 merge prompts for old revisions. Generating the virtual merge also potentially |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
48 involves invoking filters and extensions. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
49 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
50 Concept |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
51 ======= |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
52 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
53 (Bid merge is pretty much the same as Consensus merge.) |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
54 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
55 Bid merge is a strategy that attempts to sensibly combine the results of the |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
56 multiple possible three-way merges directly without producing a virtual |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
57 ancestor. The basic idea is that for each ancestor, we perform a top-level |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
58 manifest merge and generate a list of proposed actions, which we consider |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
59 "bids". We then make an "auction" among all the bids for each file and pick the |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
60 most favourable. Some files might be trivial to merge with one ancestor, other |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
61 files with another ancestor. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
62 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
63 The most obvious advantage of considering multiple ancestors is the case where |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
64 some of the bids for a file is a "real" (interactive) merge but where one or |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
65 more bids just take on of the parent revisions. A bid for just taking an |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
66 existing revision is very simple and low risk and is an obvious winner. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
67 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
68 The auction algorithm for merging the bids is so far very simple: |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
69 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
70 * If there is consensus from all the ancestors, there is no doubt what to do. A |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
71 clever result will be indistinguishable from just picking a random bid. The |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
72 consensus case is thus not only trivial, it is also already handled |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
73 perfectly. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
74 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
75 * If "keep local" or "get from other" actions is an option (and there is only |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
76 one such option), just do it. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
77 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
78 * If the auction doesn't have a single clear winner, pick one of the bids |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
79 "randomly" - just as it would have done if only one ancestor was considered. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
80 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
81 This meta merge algorithm has room for future improvements, especially for |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
82 doing better than picking a random bid. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
83 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
84 Some observations |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
85 ================= |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
86 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
87 Experience with bid merge shows that many merges that actually have a very |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
88 simple solution (because only one side changed) only can be solved efficiently |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
89 when we start looking at file content in filemerge ... and it thus also |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
90 requires all ancestors passed to filemerge. That is because Mercurial includes |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
91 the history in filelog hashes. A file with changes that ends up not changing |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
92 the content (could be change + backout or graft + merge or criss cross merges) |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
93 still shows up as a changed file to manifestmerge. (The git data model has an |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
94 advantage here when it uses hashes of content without history.) One way to |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
95 handle that would be to refactor manifestmerge, mergestate/resolve and |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
96 filemerge so they become more of the same thing. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
97 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
98 There is also cases where different conflicting chunks could benefit from using |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
99 multiple ancestors in filemerge - but that will require merge tools with fancy |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
100 support for using multiple ancestors in 3+-way merge. That is left as an |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
101 exercise for another day. That seems to be a case where "recursive merge" has |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
102 an advantage. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
103 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
104 The current manifest merge actions are very low level imperative and not |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
105 symmetrical. They do not only describe how two manifests should be merged, they |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
106 also describe a strategy for changing a context from a state where it is one of |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
107 the parents to the state where it is the result of the merge with the other |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
108 parent. I can imagine that manifestmerge could be simplified (and made more |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
109 suitable for in memory merges) by separating the abstract merge actions from |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
110 the actual file system operation actions. A more clever wcontext could perhaps |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
111 also take care of some of the branchmerge special cases. |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
112 |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
113 We assume that the definition of Mercurial manifest merge will make sure that |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
114 exactly the same files will be produced, no matter which ancestor is used. That |
79f6f9fa18c1
documentation: add some internals documentation about bid merge
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
115 assumption might be wrong in very rare cases that really not is a problem. |