1 Basic update algorithm:
3 1. recurse to all of our direct dependencies and
4 update their bases and tips
8 i. Compute our base's set of desired included deps:
9 The set of desired included deps for a base
10 is the union of the desired included deps for each
11 branch named in the base's branch's direct deps, plus
12 the name of every direct external dep.
13 The set of desired included deps for a branch
14 is the set of desired included deps for the branch's
15 base plus the branch name itself.
17 ii. For each source in the best order, do the following merge:
18 (Our base has sources:
19 - the branch for each direct dep
21 - the topgit base, if this is a topgit import)
23 Find the (latest) common ancestor.
25 Check for unwanted dependency removals.
26 An unwanted dependency removal is
27 A branch in the desired included deps
28 Which exists in the common ancestor's actual included deps
29 but which is missing in the source's actual included deps
30 (NB that this definition excludes dependency removals
31 which have already occurred on our base; these will be
33 For each unwanted dependency removal (ie for each such
34 branch), search as follows:
35 * An "unwanted removal commit" is a non-merge commit in the
36 history of the source, which removes the dep from the
38 * But the search stops at any point where we would have to
39 traverse a commit where .topbloke/deps is empty (which
40 stops us looking into the hitory of non-topbloke-controlled
41 branches). This can be done with git-rev-list
43 * It also stops at any point where we meet a commit which
44 does have the dep in the actual included deps. We have
46 * The the relevant unwanted removal commit for that dep is
47 the most recent unwanted removal commit, as defined.
48 Select the unwantedly removed dep whose relevant unwanted
49 removal commit is the earliest. Merge from the ancestor of
50 that relevant unwanted removal commit. Merge from the relevant
51 unwanted removal commit using -s ours.
53 Now continue to the next unwanted dependency removal.
55 (The purpose of this, and the result, is that the unwanted
56 dependency removal has gone away. Doing things in this order
57 tries to keep the unwanted dependency removal's reversions as
58 close as possible to their originating points. The
59 recursion, which processes dependencies before their clients,
60 tries to keep the reversion churn localised: client patches
61 of a patch affected by an unwanted removal will benefit from
62 that client's resolution of the situation.)
64 If there are no (more) unwanted dependency removals, merge
68 Check whether our list of dependencies has changed. If so
69 we need to restart the whole base update.
72 Check for missing or unwanted dependency inclusions. Compare
73 our base's desired included deps with our base's actual
74 included deps. In exceptional conditions, they will not
75 be identical. This can happen, for example, because a
76 dependency removal was incorporated into our base branch but
77 the removed branch was introduced as an explicit dependency.
78 This will also happen if we remove a dependency ourselves.
80 Do the unwanted inclusions first, and then the missing ones.
81 (This is because that the missing ones cannot depend on the
82 unwanted ones, as otherwise the unwanted ones would be in the
83 desired inclusions. So removing the unwanted ones first
84 reduces the chances of conflicts.)
87 * Do the comparison between desired and actual included
88 * Pick a missing inclusion, or failing that an unwanted one
89 (call this the "relevant" branch)
90 * Depth first search all of the dependencies of the
91 relevant branch; if any of these is also a missing
92 (resp. unwanted) inclusion, start again processing it
94 * Attempt to apply the appropriate diff to add (resp. remove)
95 the contents of the relevant patch (adjusted appropriately
96 for metadata, XXX??? particularly the actual inclusion list)
97 XXX if we want to add a dep we need to update the dep first
98 * Go round again looking for another discrepancy.
100 3. Update our branch.
101 Our branch has sources:
103 - the remote for our branch
104 - the topgit branch, if this is a topgit import
105 For each source in the best order, do the merge.
107 Double-check the actual dependency inclusions. In
108 particular, if we just upgraded to actual dependency tracking
109 we may need to explicitly add our branch name to the actual
110 dependency inclusion list.
112 The "best order" for merges is in order of recency of common
113 ancestor, most recent first, and if that does not distinguish,
114 merging from local branches first.
116 "Recency" refers to the order from git-rev-list --date-order.
118 Actual included deps:
120 This is tracked explicitly in .topbloke/included, one branch per
121 line. For compatibility with older versions, every time we think
122 about a base, branch or source above, we check whether
123 .topbloke/included is present.
125 If it isn't then we calculate a child commit which has a
126 .topbloke/included. In the case of a remote branch or base, we
127 substitute this child commit for the relevant remote ref but do
128 not record it in the remote ref; in the case of a local branch or
129 base, we advance the local branch or base accordingly.
131 When .topbloke/included is calculated in this way, it always gets
132 the list of desired included deps. (topgit,
133 which does not support dependency deletion, always has exactly the
134 desired deps actually included.)
136 Foreign branches cannot be removed from included and cannot
137 therefore be removed from dependency lists.
142 - removed patch must be removed from the deps of its
143 ex-children, and replaced with the deps of the removed
146 - removed patch wants not to be in list of patches "tb-list"
148 branches in refs/topbloke-tips ? yes
149 deleted patches do something to the base ? no
151 deleting empty patch: dependencies fine
152 deleting nonempty patch: if any dependencies found, their
156 - remove from views of active patches
157 - prevent new commits
158 - remove from dependencies of active patches
159 only makes sense if no active patches depend on it.
162 - just unmark the patch as deleted
166 When merging from a foreign dependency, check that it
167 does not have .topbloke metadata; LATER if it
168 does, could produce a new commit which has .topbloke removed
172 needs to be globally unique
173 so put email address in it
174 tg operations search for applicable patches
175 safe charset for patch names
177 not permitted (git-check-ref-format(1))
183 When pulling, which remotes get to update which patches ?
184 Complicated question!
186 For now, have "blessed" remotes, which we always pull and update from.
187 All these count as sources above.
189 Update operation restrictions available, which restrict use of various
190 sources above ? What about implications for correctness of merge
194 Concept of a "stack" ?
195 Unnecessary - instead, deal with leaf patches
196 Operations like "go up the stack", goes towards leaf. Hopefully unique.
197 "Down" the stack, uses a "conventional" linearisation
198 Stack reordering op ? auto adjust deps
201 When merging, we need to DTRT with our metadata.
202 Do this by running write-tree/read-tree etc. ourselves ?
203 For a source we're merging from, we make a version where the
204 metadata we shouldn't be merging is removed ?
206 Have discovered that specifying a custom merge driver for a file does
207 not have any effect if the three-way-merge looks trivial based
208 on looking at the file contents - at least, if you use git-merge.
210 Only thing which knows how to do all the gitattributes stuff and
211 conflict markers and what have you is git-merge. (git-merge-tree does
212 too but the output format is unsuitable.) "git-merge-index
213 ... git-merge-one-file" does not honour the merge drivers and is,
214 contrary to what the git docs seem to suggest but don't actually
215 state, not actualy used by git-merge.
217 OK so here is a plan:
218 Use git-merge --no-commit
219 Perhaps on a HEAD, and/or against a tree, which have been massaged
220 to make the metadata suitable as input.
221 Filtering out the "merge was successful but we aren't committing"
222 message. Use a single pipe for stdout/stderr to get interleaving
223 right; the message from git-merge is not i18n'd.
225 Check for merge success in the index and compare to exit status
226 from git-merge (which is 1 if the merge failed).
228 Print appropriate big fat warnings if we have merge conflicts in our
230 Commit, adjusting the parents of the new commit to the original
231 parents if we made the merge with special massaged parents.
232 We may still need to have custom merge drivers for metadata.
235 Strategies for each metadata file merge:
237 in base/tip same patch & branch dep -> base base -> tip
239 msg T textual merge rm from src not in src
240 deps B list merge rm from src rm from src
241 deleted T std existence merge rm from src not in src
242 patch- BT must be same rm from src must be same
243 topgit- B std exist/text merge rm from src rm from src
244 [^+]*- ?? textual merge rm from src rm from src
245 +included BT list merge rm from non-tb src list merge
246 +*- ?? textual merge rm from non-tb src textual merge
247 *[^-] ?? die, aborting all ops, if found in any tb src or branch
253 Unwanted removal search subgraphs:
258 rm impossible to undo removal, arrgh, terminates search
263 inc.. rm.. merge of a removal, search down the rm path
266 inc ??? call it an inclusion, terminate the search
269 inc merge of an inclusion, terminates search
273 inc ??? call it an inclusion, terminate search
278 rm inc inc rm irrelevant
279 rm inc inc inc.. rm rm..
283 OUR BASE SOURCE OUR IT TIP
289 / | ______________'/ \ |
291 / inc REMOVAL rm \ | elsewhere
300 / | | `------------ | ----<-------- | -.| |
302 | |`- | ------------- | ----<--------.| | |
305 | RE-INCLUDE inc rm REMOVAL |' |
309 |`-------------- | ----------. / | |
312 |`.____________ | / | |
314 | | /`--------<----------- | ---. |
317 \ RE-INCLUDE inc / | /
321 \ inc FIRST ADD DEP |/
323 \ | `------------<-------------.|
332 Merge 1* and 2*, diff against some relevant base branch commit
333 or something, and apply to proposed. ???
337 source tip is included in our base
340 * pick common ancestor
341 * compute whether merge from common anc would unwantedly remove
342 * if so we arrange that the common anc is a "rm" but our branch