chiark / gitweb /
remove old "calculate included patches in topgit branches" idea; we are going to...
[topbloke.git] / DESIGN
1 Basic update algorithm:
2
3  1. recurse to all of our direct dependencies and
4     update their bases and tips
5
6  2. Update our base.
7
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.
16
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
20             - the remote base
21             - the topgit base, if this is a topgit import)
22
23        Find the (latest) common ancestor.
24
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
32           reverted later.)
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
37             actual included deps.
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
42             --remove-empty.
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
45             to do this by hand.
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.
52
53        Now continue to the next unwanted dependency removal.
54
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.)
63
64        If there are no (more) unwanted dependency removals, merge
65        from the source.
66
67     iii.
68        Check whether our list of dependencies has changed.  If so
69        we need to restart the whole base update.
70
71     iv.
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.
79
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.)
85
86        So, repeatedly:
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
93            instead.
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.
99
100  3. Update our branch.
101        Our branch has sources:
102           - our base
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.
106
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.
111
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.
115
116 "Recency" refers to the order from git-rev-list --date-order.
117
118
119 Patch removal:
120
121  - removed patch must be removed from the deps of its
122    ex-children, and replaced with the deps of the removed
123    patch
124
125  - removed patch wants not to be in list of patches "tb-list"
126    et al any more
127       branches in refs/topbloke-tips ?  yes
128       deleted patches do something to the base ?  no
129
130  deleting empty patch: dependencies fine
131  deleting nonempty patch: if any dependencies found, their
132     updates break
133
134  purpose of deleting?
135    - remove from views of active patches
136    - prevent new commits
137    - remove from dependencies of active patches
138        only makes sense if no active patches depend on it.
139
140  undeleting
141    - just unmark the patch as deleted
142
143
144 Foreign branches:
145  When merging from a foreign dependency, check that it
146  does not have .topbloke metadata; LATER if it
147  does, could produce a new commit which has .topbloke removed
148  and merge from that
149
150 Patch naming:
151  needs to be globally unique
152  so put email address in it
153 tg operations search for applicable patches
154 safe charset for patch names
155   . - / 0-9 a-z
156 not permitted (git-check-ref-format(1))
157  spc ~ ^ : ? * [ \
158  @{ .lock.
159  (apropos of shell)
160
161
162 When pulling, which remotes get to update which patches ?
163 Complicated question!
164
165 For now, have "blessed" remotes, which we always pull and update from.
166 All these count as sources above.
167
168 Update operation restrictions available, which restrict use of various
169 sources above ?  What about implications for correctness of merge
170 algorithm ?
171
172
173 Concept of a "stack" ?
174 Unnecessary - instead, deal with leaf patches
175 Operations like "go up the stack", goes towards leaf.  Hopefully unique.
176 "Down" the stack, uses a "conventional" linearisation
177 Stack reordering op ?  auto adjust deps
178
179
180 When merging, we need to DTRT with our metadata.
181 Do this by running write-tree/read-tree etc. ourselves ?
182 For a source we're merging from, we make a version where the
183 metadata we shouldn't be merging is removed ?
184 Or something.
185 Have discovered that specifying a custom merge driver for a file does
186 not have any effect if the three-way-merge looks trivial based
187 on looking at the file contents - at least, if you use git-merge.
188
189 Only thing which knows how to do all the gitattributes stuff and
190 conflict markers and what have you is git-merge.  (git-merge-tree does
191 too but the output format is unsuitable.)  "git-merge-index
192 ... git-merge-one-file" does not honour the merge drivers and is,
193 contrary to what the git docs seem to suggest but don't actually
194 state, not actualy used by git-merge.
195
196 OK so here is a plan:
197   Use git-merge --no-commit
198   Perhaps on a HEAD, and/or against a tree, which have been massaged
199    to make the metadata suitable as input.
200   Filtering out the "merge was successful but we aren't committing"
201   message.  Use a single pipe for stdout/stderr to get interleaving
202   right; the message from git-merge is not i18n'd.
203   Afterwards we:
204   Check for merge success in the index and compare to exit status
205   from git-merge (which is 1 if the merge failed).
206   Adjust the metadata.
207   Print appropriate big fat warnings if we have merge conflicts in our
208   metadata.
209   Commit, adjusting the parents of the new commit to the original
210   parents if we made the merge with special massaged parents.
211   We may still need to have custom merge drivers for metadata.
212
213
214 Strategies for each metadata file merge:
215
216         in base/tip     same patch & branch     dep -> base     base -> tip
217
218  msg             T      textual merge           rm from src     not in src
219  deps           B       list merge              rm from src     rm from src
220  deleted         T      std existence merge     rm from src     not in src
221  patch-         BT      must be same            rm from src     must be same
222  topgit-        B       std exist/text merge    rm from src     rm from src
223  [^+]*-         ??      textual merge           rm from src     rm from src
224  +included      BT      list merge        rm from non-tb src    list merge
225  +*-            ??      textual merge     rm from non-tb src    textual merge
226  *[^-]          ??      die, aborting all ops, if found in any tb src or branch
227
228
229
230
231
232 Unwanted removal search subgraphs:
233
234   rm            relevant removal
235   inc
236
237    rm           impossible to undo removal, arrgh, terminates search
238 inc  inc..
239 /  ???   \
240
241     rm
242 inc..  rm..     merge of a removal, search down the rm path
243 /  [inc]  \
244
245   inc           ??? call it an inclusion, terminate the search
246   rm
247
248    inc          merge of an inclusion, terminates search
249 inc..  rm..
250 /  [rm]  \
251
252    inc          ??? call it an inclusion, terminate search
253 rm..  rm..
254 /  ???    \
255
256
257   rm    inc       inc          rm       irrelevant
258   rm    inc     inc inc..    rm rm..
259
260
261
262           OUR BASE              SOURCE                 OUR IT TIP
263                 |                  |                       |
264                 |                  |                       |
265    ADD DEP WH/ inc                 rm                      |
266     NEEDS IT   /|                  /\                      |
267               / |                rm  \                     |
268              /  | ______________'/    \                    |
269           inc   |'              /      \                   |     IT tip
270            /   inc     REMOVAL rm       \                  |    elsewhere
271           /     |             /          \                 |   |   |
272          /      |           inc           \                |   |   |
273      some IT    |           /              |               |   |   |
274                 |         inc              |               |   |   |
275                /           |               |               |   |   |
276               /          inc               |               |   |   |
277              |           / |               |               |   |   |
278             /           /  inc             |               |   |   |
279            /           |   | `------------ | ----<-------- | -.|   |
280           /           inc  inc             |               |   *2  |
281           |            |`- | ------------- | ----<--------.|   |   |
282           |            `---inc             |              1*  /    |
283           |                |               |               | /     |
284           |     RE-INCLUDE inc             rm REMOVAL      |'      |
285         inc     \          |               |               |       |
286           |      * REMOVAL rm              |               |       |
287           |                |              /                |       |
288           |`-------------- | ----------. /                 |       |
289           |                |           inc ANC2            |       |
290          inc               inc         /                   |       |
291           |`.____________  |          /                    |       |
292           |              `inc ANC1   /                     |       |
293           |                |        /`--------<----------- | ---.  |
294         without            inc     /                       |     \/
295           |                |      /                        |     /
296            \    RE-INCLUDE inc   /                         |    /
297             \   \          |    /                          |   /
298              \   * REMOVAL rm  /                           |  /
299               \            |  /                            | /
300                \           inc FIRST ADD DEP               |/
301                 \          |  \                            *3
302                  \         |   `------------<-------------.|
303                   \        |                               |
304                    \       without                         |
305                     \_____ |                               |
306                           `without                         |
307                            |                               |
308                                                           IT
309
310
311   Merge 1* and 2*, diff against some relevant base branch commit
312   or something, and apply to proposed. ???
313
314
315 After we are done:
316   source tip is included in our base
317
318 Each time:
319   * pick common ancestor
320   * compute whether merge from common anc would unwantedly remove
321   * if so we arrange that the common anc is a "rm" but our branch
322     actually contains IT