chiark / gitweb /
50efed7c8598cbf61a0e9b349b9dece2e3634267
1 \section{Strategy}
3 When we are trying to do a merge of some kind, in general,
4 we want to merge some source commits $S_0 \ldots S_n$.
5 We'll write $S_0 = L$.  We require that $L$ is the current git ref
6 for $\patchof{L}$.
8 \subsection{Notation}
10 \begin{basedescript}{
11 \desclabelwidth{5em}
12 \desclabelstyle{\nextlinelabel}
13 }
14 \item[ $\depsreqof{K}$ ]
15 The set of direct dependencies (in the form $\py$)
16 requested in the commit $K$ ($K \in \pn$) for the patch $\p$.
18 \item[ $\pc \succ_1 \{ \p, \pq \ldots \}$ ]
19 The Topbloke commit set $\pc$ has as direct contributors
20 (see below) exactly $\p, \pq, \ldots$.  This is an acyclic relation.
22 \item[ $\p \succ \pq$ ]
23 The commit set $\p$ has as direct or indirect contributor the commit
24 set $\pq$.
25 This is an acyclic relation, and is the completion of $\succ_1$ into a
26 partial order.
28 \item[ $\set E_{\pc}$ ]
29 $\bigcup_i \pendsof{S_i}{\pc}$.
30 All the ends of $\pc$ in the sources.
32 \end{basedescript}
34 \subsection{Planning phase}
36 We use a recursive planning algorith, recursing over Topbloke commit
37 sets (ie, sets $\py$ or $\pn$).  We'll call the commit set we're
38 processing at each step $\pc$.  We start with $\pc = \pl$
39 where $\pl = \patchof{L}$.
41 At each recursive step
42 we intend to merge all $\set E_{\pc} = \{ E_{\pc,j \ldots} \}$
43 and all the direct contributors of $\pc$ (as determined below)
44 into the existing git ref for $\pc$, to make $T_{\pc}$.
45 The direct contributors of $\pcn$ are the Topbloke commit sets
46 corresponding to the tip branches for the direct dependencies of
47 $\pc$.
48 The sole direct contributor of $\pcy$ is $\pcn$.
50 \subsubsection{Planning step for $\pc = \pcn$.}
52 Choose an (arbitrary, but ideally somehow optimal in
53 a way not discussed here) ordering of $\set E_{\pc}$, $E_j$ (for
54 $j = 1 \ldots m$).  Remove from that set (and ordering) any $E_j$ which
55 are $\le$ and $\neq$ some other $E_k$.
57 Initially let $T_{\pc,0}$ be the git ref for $\pcn$.  And let
58 $\set D_0 = \depsreqof{T_{\pc,0}}$.
59 For each $E_j$ starting with $j=1$ choose a corresponding intended
60 merge base $M_j$ such that $M_j \le E_j \land M_j \le T_{\pc,j-1}$.
61 Calculate $\set D_j$ as the 3-way merge of the sets $\set D_{j-1}$ and
62 $\depsreqof{E_j}$ using as a base $\depsreqof{M_j}$.  This will
63 generate $D_m$ as the putative direct contributors for $\pcn$.
65 However, the invocation may specify that certain direct dependencies
66 are definitely to be included, or excluded.  As a result the set
67 of actual direct contributors is some arbitrary set of patches.
74 Imagine that we will merge the direct
76 with $M=M_j, L=T_{\pc,j-1}, R=E_j$,
77 and calculate what the resulting desired direct dependencies file
78 (ie, the set of patches $\set D_j$)
79 would be.  Eventually we
81 So, formally, we select somehow an order of sources $S_i$.  For each
84 Make use of the following recursive algorithm, Plan
89  recursively make a plan to merge all $E = \pends$
91 Specifically, in