chiark / gitweb /
1 \section{Strategy}
3 We start with some commits \$S_0 \ldots S_n\$
4 (where \$S_0 = L\$ and is the current git ref for \$\pl\$).
6 %Let \$\set E_{\pc} = \bigcup_i \pendsof{S_i}{\pc}\$.
8 Invoke Plan \$\patchof \pl\$ where the algorithm Plan \$\pc\$ is as
9 follows:
11 Notation:
13  \$\pc \succ_1 \{ \p, \pq \ldots \}\$
14  the Topbloke commit set \$py\$ has as direct contributors exactly
15  \$\p, \pq, \ldots\$.  This is an acyclic relation.
17  Extend this into the partial order \$\succ\$.
19 \$\py \succ \pq\$
21 We intend to merge all \$\set E_{\pc} = \{ E_{\pc,j \ldots} \}\$
22 and all the direct contributors of \$\pc\$ (as determined below)
23 into the existing git ref for \$\pc\$, to make \$T_{\pc}\$.
24 The direct contributors of \$\pcn\$ are the topbloke commit sets
25 corresponding to the tip branches for the direct dependencies of
26 \$\pc\$.
27 The sole direct contributor of \$\pcy\$ is \$\pcn\$.
30 For \$\pc = \pcn\$, choose an (arbitrary, but ideally somehow optimal in
31 a way not discussed here) ordering of \$\set E_{\pc}\$, \$E_j\$ (for
32 \$j = 1 \ldots m\$).  Remove from that set (and ordering) any \$E_j\$ which
33 are \$\le\$ and \$\neq\$ some other \$E_k\$.
35 Notation: write \$\depsreqof{K}\$ to mean the direct dependencies
36 (in the form \$\py\$) requested in the commit \$K\$.
38 Initially let \$T_{\pc,0}\$ be the git ref for \$\pcn\$.  And let
39 \$\set D_0 = \depsreqof{T_{\pc,0}}\$.
40 For each \$E_j\$ starting with \$j=1\$ choose a corresponding intended
41 merge base \$M_j\$ such that \$M_j \le E_j \land M_j \le T_{\pc,j-1}\$.
42 Calculate \$D_j\$ as the 3-way merge of the sets \$D_{j-1}\$ and
43 \$\depsreqof{E_j}\$ using as a base \$\depsreqof{M_j}\$.  This will
44 generate \$D_m\$ as the putative direct contributors for \$\pcn\$.
46 However, the invocation may specify that certain direct dependencies
47 are definitely to be included, or excluded.  As a result the set
48 of actual direct contributors is some arbitrary set of patches.
55 Imagine that we will merge the direct
57 with \$M=M_j, L=T_{\pc,j-1}, R=E_j\$,
58 and calculate what the resulting desired direct dependencies file
59 (ie, the set of patches \$\set D_j\$)
60 would be.  Eventually we
62 So, formally, we select somehow an order of sources \$S_i\$.  For each
65 Make use of the following recursive algorithm, Plan
70  recursively make a plan to merge all \$E = \pends\$
72 Specifically, in