chiark / gitweb /
wip tb-list
[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 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), find the most recent commit which unwantedly removed
34        the dep from the source's actual included deps ("relevant
35        unwanted removal commit").  (Abort if any such commit is a
36        merge.)  Select the earliest relevant unwanted removal commit
37        (from the set of relevant unwanted removal commits
38        corresponding to the unwanted dependency removals).
39        Merge from the ancestor of the relevant unwanted removal commit.
40        Merge from the relevant unwanted removal commit using -s ours.
41
42        (The purpose of this, and the result, is that the unwanted
43        dependency removal has gone away.  Doing things in this order
44        tries to keep the unwanted dependency removal's reversions as
45        close as possible to their originating points.  The
46        recursion, which processes dependencies before their clients,
47        tries to keep the reversion churn localised: client patches
48        of a patch affected by an unwanted removal will benefit from
49        that client's resolution of the situation.)
50
51        Now continue to the next unwanted dependency removal.
52
53        If there are no (more) unwanted dependency removals, merge
54        from the source.
55
56     iii.
57        Check for missing or unwanted dependency inclusions.  Compare
58        our base's desired included deps with our base's actual
59        included deps.  In exceptional conditions, they will not
60        be identical.  This can happen, for example, because a
61        dependency removal was incorporated into our base branch but
62        the removed branch was introduced as an explicit dependency.
63        This will also happen if we remove a dependency ourselves.
64
65        Do the unwanted inclusions first, and then the missing ones.
66        (This is because that the missing ones cannot depend on the
67        unwanted ones, as otherwise the unwanted ones would be in the
68        desired inclusions.  So removing the unwanted ones first
69        reduces the chances of conflicts.)
70
71        So, repeatedly:
72          * Do the comparison between desired and actual included
73          * Pick a missing inclusion, or failing that an unwanted one
74            (call this the "relevant" branch)
75          * Depth first search all of the dependencies of the
76            relevant branch; if any of these is also a missing
77            (resp. unwanted) inclusion, start again processing it
78            instead.
79          * Attempt to apply the appropriate diff to add (resp. remove)
80            the contents of the relevant patch (adjusted appropriately
81            for metadata, XXX??? particularly the actual inclusion list)
82          * Go round again looking for another discrepancy.
83
84  3. Update our branch.
85        Our branch has sources:
86           - our base
87           - the remote for our branch
88        For each source in the best order, do the merge.
89
90        Double-check the actual dependency inclusions.  In
91        particular, if we just upgraded to actual dependency tracking
92        we may need to explicitly add our branch name to the actual
93        dependency inclusion list.
94
95 The "best order" for merges is in order of recency of common
96 ancestor, most recent first, and if that does not distinguish,
97 merging from local branches first.
98      
99 "Recency" refers to the order from git-rev-list --date-order.
100
101 Actual included deps:
102
103   This is tracked explicitly in .topbloke/included, one branch per
104   line.  For compatibility with older versions, every time we think
105   about a base, branch or source above, we check whether
106   .topbloke/included is present.
107
108   If it isn't then we calculate a child commit which has a
109   .topbloke/included.  In the case of a remote branch or base, we
110   substitute this child commit for the relevant remote ref but do
111   not record it in the remote ref; in the case of a local branch or
112   base, we advance the local branch or base accordingly.
113
114   When .topbloke/included is calculated in this way, it always gets
115   the list of desired included deps.  (topgit,
116   which does not support dependency deletion, always has exactly the
117   desired deps actually included.)
118
119   Foreign branches cannot be removed from included and cannot
120   therefore be removed from dependency lists.
121
122
123 Patch removal:
124
125  - removed patch must be removed from the deps of its
126    ex-children, and replaced with the deps of the removed
127    patch
128
129  - removed patch wants not to be in list of patches "tb-list"
130    et al any more
131       branches in refs/topbloke-tips ?  yes
132       deleted patches do something to the base ?  no
133
134  deleting empty patch: dependencies fine
135  deleting nonempty patch: if any dependencies found, their
136     updates break
137
138  purpose of deleting?
139    - remove from views of active patches
140    - prevent new commits
141    - remove from dependencies of active patches
142        only makes sense if no active patches depend on it.
143
144  undeleting
145    - just unmark the patch as deleted
146
147
148 Foreign branches:
149  When merging from a foreign dependency, check that it
150  does not have .topbloke metadata; LATER if it
151  does, could produce a new commit which has .topbloke removed
152  and merge from that
153
154 Patch naming:
155  needs to be globally unique
156  so put email address in it
157 tg operations search for applicable patches
158 safe charset for patch names
159   . - / 0-9 a-z
160 not permitted (git-check-ref-format(1))
161  spc ~ ^ : ? * [ \
162  @{ .lock.
163  (apropos of shell)
164
165
166 When pulling, which remotes get to update which patches ?
167 Complicated question!
168
169 For now, have "blessed" remotes, which we always pull and update from.
170 All these count as sources above.
171
172 Update operation restrictions available, which restrict use of various
173 sources above ?  What about implications for correctness of merge
174 algorithm ?
175
176
177 Concept of a "stack" ?
178 Unnecessary - instead, deal with leaf patches
179 Operations like "go up the stack", goes towards leaf.  Hopefully unique.
180 "Down" the stack, uses a "conventional" linearisation
181 Stack reordering op ?  auto adjust deps