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 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 %Let $\set E_{\pc} = \bigcup_i \pendsof{S_i}{\pc}$.
   9
  10 \subsection{Notation}
  11
  12 \begin{basedescript}{
  13 \desclabelwidth{5em}
  14 \desclabelstyle{\nextlinelabel}
  15 }
  16 \item[ $\depsreqof{K}$ ]
  17 The set of direct dependencies (in the form $\py$)
  18 requested in the commit $K$ ($K \in \pn$) for the patch $\p$.
  19
  20 \item[ $\pc \succ_1 \{ \p, \pq \ldots \}$ ]
  21 The Topbloke commit set $\pc$ has as direct contributors
  22 (see below) exactly $\p, \pq, \ldots$.  This is an acyclic relation.
  23
  24 \item[ $\p \succ \pq$ ]
  25 The commit set $\p$ has as direct or indirect contributor the commit
  26 set $\pq$.
  27 This is an acyclic relation, and is the completion of $\succ_1$ into a
  28 partial order.
  29
  30 \end{basedescript}
  31
  32 \subsection{Planning phase}
  33
  34 We use a recursive planning algorith, recursing over Topbloke commit
  35 sets (ie, sets $\py$ or $\pn$).  We'll call the commit set we're
  36 processing at each step $\pc$.  We start with $\pc = \pl$
  37 where $\pl = \patchof{L}$.
  38
  39 At each recursive step
  40 we intend to merge all $\set E_{\pc} = \{ E_{\pc,j \ldots} \}$
  41 and all the direct contributors of $\pc$ (as determined below)
  42 into the existing git ref for $\pc$, to make $T_{\pc}$.
  43 The direct contributors of $\pcn$ are the Topbloke commit sets
  44 corresponding to the tip branches for the direct dependencies of
  45 $\pc$.
  46 The sole direct contributor of $\pcy$ is $\pcn$.
  47
  48 \subsubsection{Planning step for $\pc = \pcn$.}
  49
  50 FIXME DEFINE $\set E$
  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