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
  12 Notation:
  13
  14  $\pc \succ_1 \{ \p, \pq \ldots \}$
  15  the Topbloke commit set $py$ has as direct contributors exactly
  16  $\p, \pq, \ldots$.  This is an acyclic relation.
  17
  18  Extend this into the partial order $\succ$.
  19
  20 $\py \succ \pq$
  21
  22
  23 We intend to merge all $\set E_{\pc} = \{ E_{\pc,j \ldots} \}$
  24 and all the direct contributors of $\pc$ (as determined below)
  25 into the existing git ref for $\pc$, to make $T_{\pc}$.
  26 The direct contributors of $\pcn$ are the topbloke commit sets
  27 corresponding to the tip branches for the direct dependencies of
  28 $\pc$.
  29 The sole direct contributor of $\pcy$ is $\pcn$.
  30
  31
  32 For $\pc = \pcn$, choose an (arbitrary, but ideally somehow optimal in
  33 a way not discussed here) ordering of $\set E_{\pc}$, $E_j$ (for
  34 $j = 1 \ldots m$).  Remove from that set (and ordering) any $E_j$ which
  35 are $\le$ and $\neq$ some other $E_k$.
  36
  37 Notation: write $\depsreqof{K}$ to mean the direct dependencies
  38 (in the form $\py$) requested in the commit $K$.
  39
  40 Initially let $T_{\pc,0}$ be the git ref for $\pcn$.  And let
  41 $\set D_0 = \depsreqof{T_{\pc,0}}$.
  42 For each $E_j$ starting with $j=1$ choose a corresponding intended
  43 merge base $M_j$ such that $M_j \le E_j \land M_j \le T_{\pc,j-1}$.
  44 Calculate $\set D_j$ as the 3-way merge of the sets $\set D_{j-1}$ and
  45 $\depsreqof{E_j}$ using as a base $\depsreqof{M_j}$.  This will
  46 generate $D_m$ as the putative direct contributors for $\pcn$.
  47
  48 However, the invocation may specify that certain direct dependencies
  49 are definitely to be included, or excluded.  As a result the set
  50 of actual direct contributors is some arbitrary set of patches.
  51
  52
  53
  54
  55
  56
  57 Imagine that we will merge the direct
  58
  59 with $M=M_j, L=T_{\pc,j-1}, R=E_j$,
  60 and calculate what the resulting desired direct dependencies file
  61 (ie, the set of patches $\set D_j$)
  62 would be.  Eventually we
  63
  64 So, formally, we select somehow an order of sources $S_i$.  For each
  65
  66
  67 Make use of the following recursive algorithm, Plan
  68
  69
  70
  71
  72  recursively make a plan to merge all $E = \pends$
  73
  74 Specifically, in