chiark / gitweb /
metadata merging plan
[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
22        Find the (latest) common ancestor.
23
24        Check for unwanted dependency removals.  
25        An unwanted dependency removal is
26           A branch in the desired included deps
27           Which exists in the common ancestor's actual included deps
28           but which is missing in the source's actual included deps
29           (NB that this definition excludes dependency removals
30           which have already occurred on our base; these will be
31           reverted later.)
32        For each unwanted dependency removal (ie for each such
33        branch), search as follows:
34           * An "unwanted removal commit" is a non-merge commit in the
35             history of the source, which removes the dep from the
36             actual included deps.
37           * But the search stops at any point where we would have to
38             traverse a commit where .topbloke/deps is empty (which
39             stops us looking into the hitory of non-topbloke-controlled
40             branches).  This can be done with git-rev-list
41             --remove-empty.
42           * The the relevant unwanted removal commit for that dep is
43             the most recent unwanted removal commit, as defined.
44        Select the unwantedly removed dep whose relevant unwanted
45        removal commit is the earliest.  Merge from the ancestor of
46        that relevant unwanted removal commit.  Merge from the relevant
47        unwanted removal commit using -s ours.
48
49        Now continue to the next unwanted dependency removal.
50
51        (The purpose of this, and the result, is that the unwanted
52        dependency removal has gone away.  Doing things in this order
53        tries to keep the unwanted dependency removal's reversions as
54        close as possible to their originating points.  The
55        recursion, which processes dependencies before their clients,
56        tries to keep the reversion churn localised: client patches
57        of a patch affected by an unwanted removal will benefit from
58        that client's resolution of the situation.)
59
60        If there are no (more) unwanted dependency removals, merge
61        from the source.
62
63     iii.
64        Check for missing or unwanted dependency inclusions.  Compare
65        our base's desired included deps with our base's actual
66        included deps.  In exceptional conditions, they will not
67        be identical.  This can happen, for example, because a
68        dependency removal was incorporated into our base branch but
69        the removed branch was introduced as an explicit dependency.
70        This will also happen if we remove a dependency ourselves.
71
72        Do the unwanted inclusions first, and then the missing ones.
73        (This is because that the missing ones cannot depend on the
74        unwanted ones, as otherwise the unwanted ones would be in the
75        desired inclusions.  So removing the unwanted ones first
76        reduces the chances of conflicts.)
77
78        So, repeatedly:
79          * Do the comparison between desired and actual included
80          * Pick a missing inclusion, or failing that an unwanted one
81            (call this the "relevant" branch)
82          * Depth first search all of the dependencies of the
83            relevant branch; if any of these is also a missing
84            (resp. unwanted) inclusion, start again processing it
85            instead.
86          * Attempt to apply the appropriate diff to add (resp. remove)
87            the contents of the relevant patch (adjusted appropriately
88            for metadata, XXX??? particularly the actual inclusion list)
89          * Go round again looking for another discrepancy.
90
91  3. Update our branch.
92        Our branch has sources:
93           - our base
94           - the remote for our branch
95        For each source in the best order, do the merge.
96
97        Double-check the actual dependency inclusions.  In
98        particular, if we just upgraded to actual dependency tracking
99        we may need to explicitly add our branch name to the actual
100        dependency inclusion list.
101
102 The "best order" for merges is in order of recency of common
103 ancestor, most recent first, and if that does not distinguish,
104 merging from local branches first.
105      
106 "Recency" refers to the order from git-rev-list --date-order.
107
108 Actual included deps:
109
110   This is tracked explicitly in .topbloke/included, one branch per
111   line.  For compatibility with older versions, every time we think
112   about a base, branch or source above, we check whether
113   .topbloke/included is present.
114
115   If it isn't then we calculate a child commit which has a
116   .topbloke/included.  In the case of a remote branch or base, we
117   substitute this child commit for the relevant remote ref but do
118   not record it in the remote ref; in the case of a local branch or
119   base, we advance the local branch or base accordingly.
120
121   When .topbloke/included is calculated in this way, it always gets
122   the list of desired included deps.  (topgit,
123   which does not support dependency deletion, always has exactly the
124   desired deps actually included.)
125
126   Foreign branches cannot be removed from included and cannot
127   therefore be removed from dependency lists.
128
129
130 Patch removal:
131
132  - removed patch must be removed from the deps of its
133    ex-children, and replaced with the deps of the removed
134    patch
135
136  - removed patch wants not to be in list of patches "tb-list"
137    et al any more
138       branches in refs/topbloke-tips ?  yes
139       deleted patches do something to the base ?  no
140
141  deleting empty patch: dependencies fine
142  deleting nonempty patch: if any dependencies found, their
143     updates break
144
145  purpose of deleting?
146    - remove from views of active patches
147    - prevent new commits
148    - remove from dependencies of active patches
149        only makes sense if no active patches depend on it.
150
151  undeleting
152    - just unmark the patch as deleted
153
154
155 Foreign branches:
156  When merging from a foreign dependency, check that it
157  does not have .topbloke metadata; LATER if it
158  does, could produce a new commit which has .topbloke removed
159  and merge from that
160
161 Patch naming:
162  needs to be globally unique
163  so put email address in it
164 tg operations search for applicable patches
165 safe charset for patch names
166   . - / 0-9 a-z
167 not permitted (git-check-ref-format(1))
168  spc ~ ^ : ? * [ \
169  @{ .lock.
170  (apropos of shell)
171
172
173 When pulling, which remotes get to update which patches ?
174 Complicated question!
175
176 For now, have "blessed" remotes, which we always pull and update from.
177 All these count as sources above.
178
179 Update operation restrictions available, which restrict use of various
180 sources above ?  What about implications for correctness of merge
181 algorithm ?
182
183
184 Concept of a "stack" ?
185 Unnecessary - instead, deal with leaf patches
186 Operations like "go up the stack", goes towards leaf.  Hopefully unique.
187 "Down" the stack, uses a "conventional" linearisation
188 Stack reordering op ?  auto adjust deps
189
190
191 When merging, we need to DTRT with our metadata.
192 Do this by running write-tree/read-tree etc. ourselves ?
193 For a source we're merging from, we make a version where the
194 metadata we shouldn't be merging is removed ?
195 Or something.
196 Have discovered that specifying a custom merge driver for a file does
197 not have any effect if the three-way-merge looks trivial based
198 on looking at the file contents - at least, if you use git-merge.
199
200 Only thing which knows how to do all the gitattributes stuff and
201 conflict markers and what have you is git-merge.  (git-merge-tree does
202 too but the output format is unsuitable.)  "git-merge-index
203 ... git-merge-one-file" does not honour the merge drivers and is,
204 contrary to what the git docs seem to suggest but don't actually
205 state, not actualy used by git-merge.
206
207 OK so here is a plan:
208   Use git-merge --no-commit
209   Perhaps on a HEAD, and/or against a tree, which have been massaged
210    to make the metadata suitable as input.
211   Filtering out the "merge was successful but we aren't committing"
212   message.  Use a single pipe for stdout/stderr to get interleaving
213   right; the message from git-merge is not i18n'd.
214   Afterwards we:
215   Check for merge success in the index and compare to exit status
216   from git-merge (which is 1 if the merge failed).
217   Adjust the metadata.
218   Print appropriate big fat warnings if we have merge conflicts in our 
219   metadata.
220   Commit, adjusting the parents of the new commit to the original
221   parents if we made the merge with special massaged parents.
222   We may still need to have custom merge drivers for metadata.
223
224
225 Strategies for each metadata file merge:
226
227         in base/tip     same patch's tip        dep -> base     base -> tip
228
229  msg             T      textual merge           rm from src     not in src
230  deps            T      list merge              rm from src     not in src
231  deleted         T      std existence merge     rm from src     not in src
232  patch-         BT      must be same            rm from src     must be same
233  topgit-         T      must be same            rm from src     not in src
234  [^+]*-         ??      textual merge           rm from src     rm from src
235  +included      BT      list merge        rm from non-tb src    list merge
236  +*-            ??      textual merge     rm from non-tb src    textual merge
237  *[^-]          ??      die, aborting all ops, if found in any tb src or branch