chiark / gitweb /
50efed7c8598cbf61a0e9b349b9dece2e3634267
[topbloke-formulae.git] / strategy.tex
1 \section{Strategy}
2
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}$.
7
8 \subsection{Notation}
9
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$.
17
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.
21
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.
27
28 \item[ $\set E_{\pc}$ ]
29 $ \bigcup_i \pendsof{S_i}{\pc} $.
30 All the ends of $\pc$ in the sources.
31
32 \end{basedescript}
33
34 \subsection{Planning phase}
35
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}$.
40
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$.
49
50 \subsubsection{Planning step for $\pc = \pcn$.}
51
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$.
56
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$.
64
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.
68
69
70
71
72
73
74 Imagine that we will merge the direct 
75
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 
80
81 So, formally, we select somehow an order of sources $S_i$.  For each 
82
83
84 Make use of the following recursive algorithm, Plan 
85
86
87
88
89  recursively make a plan to merge all $E = \pends$
90
91 Specifically, in