strategy.tex

   1 When we are trying to do a merge of some kind, in general,
   2 we want to merge some source commits $S_0 \ldots S_n$.
   3 We'll write $S_0 = L$.  We require that $L$ is the current git ref
   4 for $\patchof{L}$.
   5
   6 \stdsection{Notation}
   7
   8 \begin{basedescript}{
   9 \desclabelwidth{5em}
  10 \desclabelstyle{\nextlinelabel}
  11 }
  12 \item[ $\depsreqof{K}$ ]
  13 The set of direct dependencies (in the form $\py$)
  14 requested in the commit $K$ ($K \in \pn$) for the patch $\p$.
  15
  16 \item[ $\pc \succ_1 \{ \p, \pq \ldots \}$ ]
  17 The Topbloke commit set $\pc$ has as direct contributors
  18 (see below) exactly $\p, \pq, \ldots$.  This is an acyclic relation.
  19
  20 \item[ $\p \succ \pq$ ]
  21 The commit set $\p$ has as direct or indirect contributor the commit
  22 set $\pq$.
  23 This is an acyclic relation, and is the completion of $\succ_1$ into a
  24 partial order.
  25
  26 \item[ $\set E_{\pc}$ ]
  27 $ \bigcup_i \pendsof{S_i}{\pc} $.
  28 All the ends of $\pc$ in the sources.
  29
  30 \end{basedescript}
  31
  32 \section{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 \subsection{Planning step for $\pc = \pcn$.}
  49
  50 Choose an (arbitrary, but ideally somehow optimal in
  51 a way not discussed here) ordering of $\set E_{\pc}$, $E_j$ (for
  52 $j = 1 \ldots m$).  Remove from that set (and ordering) any $E_j$ which
  53 are $\le$ and $\neq$ some other $E_k$.
  54
  55 Initially let $T_{\pc,0}$ be the git ref for $\pcn$.  And let
  56 $\set D_0 = \depsreqof{T_{\pc,0}}$.
  57 For each $E_j$ starting with $j=1$ choose a corresponding intended
  58 merge base $M_j$ such that $M_j \le E_j \land M_j \le T_{\pc,j-1}$.
  59 Calculate $\set D_j$ as the 3-way merge of the sets $\set D_{j-1}$ and
  60 $\depsreqof{E_j}$ using as a base $\depsreqof{M_j}$.  This will
  61 generate $D_m$ as the putative direct contributors for $\pcn$.
  62
  63 However, the invocation may specify that certain direct dependencies
  64 are definitely to be included, or excluded.  As a result the set
  65 of actual direct contributors is some arbitrary set of patches.
  66
  67
  68
  69
  70
  71
  72 Imagine that we will merge the direct
  73
  74 with $M=M_j, L=T_{\pc,j-1}, R=E_j$,
  75 and calculate what the resulting desired direct dependencies file
  76 (ie, the set of patches $\set D_j$)
  77 would be.  Eventually we
  78
  79 So, formally, we select somehow an order of sources $S_i$.  For each
  80
  81
  82 Make use of the following recursive algorithm, Plan
  83
  84
  85
  86
  87  recursively make a plan to merge all $E = \pends$
  88
  89 Specifically, in