strategy.tex

   1 \section{Strategy}
   2
   3 We start with some commits $S_0 \ldots S_n$
   4 (where $S_0 = L$ and is the current git ref for $\pl$).
   5
   6 %Let $\set E_{\pc} = \bigcup_i \pendsof{S_i}{\pc}$.
   7
   8 Invoke Plan $\patchof \pl$ where the algorithm Plan $\pc$ is as
   9 follows:
  10
  11 Notation:
  12
  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.
  16
  17  Extend this into the partial order $\succ$.
  18
  19 $\py \succ \pq$
  20
  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$.
  28
  29
  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$.
  34
  35 Notation: write $\depsreqof{K}$ to mean the direct dependencies
  36 (in the form $\py$) requested in the commit $K$.
  37
  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$.
  45
  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.
  49
  50
  51
  52
  53
  54
  55 Imagine that we will merge the direct
  56
  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
  61
  62 So, formally, we select somehow an order of sources $S_i$.  For each
  63
  64
  65 Make use of the following recursive algorithm, Plan
  66
  67
  68
  69
  70  recursively make a plan to merge all $E = \pends$
  71
  72 Specifically, in