strategy.tex

   1 Here we describe the update algorithm.  This is responsible for
   2 refreshing patches against updated versions of their dependencies,
   3 for merging different versions of the various braches created by
   4 distributed development, and for implementing decisions to add and
   5 remove dependencies from patches.
   6
   7 Broadly speaking the update proceeds as follows: during the Ranking
   8 phase we construct the intended graph of dependencies between patches
   9 (and incidentally select a merge order for the base branch of each
  10 patch).  Then during the Traversal phase we walk that graph from the
  11 bottom up, constructing for each patch by a series of merges and other
  12 operations first a new base branch head commit and then a new tip
  13 branch head commit.  These new head commits are maximums - that is,
  14 each has as ancestors all of its branches' sources and indeed all
  15 relevant commits in that branch.
  16
  17 We have two possible strategies for constructing new base branch
  18 heads: we can either Merge (works incrementally even if there the
  19 patch has multiple dependencies, but may sometimes not be possible) or
  20 we can Regenerate (trivial if there is a single dependency, and is
  21 always possible, but may involve the user re-resolving conflicts if
  22 there are multiple dependencies).
  23
  24 \section{Notation}
  25
  26 \begin{basedescript}{
  27 \desclabelwidth{5em}
  28 \desclabelstyle{\nextlinelabel}
  29 }
  30 \item[ $\depsreqof{K}$ ]
  31 The set of direct dependencies (in the form $\py$)
  32 requested in the commit $K$ ($K \in \pn$) for the patch $\p$.
  33
  34 \item[ $\pc \hasdirdep \p$ ]
  35 The patch $\pc$ has as a direct dependency the
  36 patch $\p$.  This is an acyclic relation.
  37
  38 \item[ $\p \hasdep \pq$ ]
  39 The patch $\p$ has as direct or indirect dependency the
  40 patch $\pq$.
  41 Acyclic; the completion of $\hasdirdep$ into a
  42 partial order.
  43
  44 \item[ $\pendsof{\set J}{\p}$ ]
  45 Convenience notation for
  46 the $\le$-maximal elements of $\bigcup_{J \in \set J} \pendsof{J}{\p}$
  47 (where $\set J$ is some set of commits).
  48
  49 \item[ $\pendsof{\set X}{\p} \le T$ ]
  50 Convenience notation for
  51 $\bigforall_{E \in \pendsof{\set X}{\p}} E \le T$
  52
  53 \item[ $\allsrcs$ ]
  54 $\bigcup_{\p \in \allpatches} \set H^{\pn} \cup \set H^{\py}$.
  55 All the input commits to the update algorithm.  (See below.)
  56
  57 %\item[ $\set E_{\pc}$ ]
  58 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
  59 %All the ends of $\pc$ in the sources.
  60
  61 %\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
  62 %The git ref for the Topbloke commit set $\pc$: respectively,
  63 %the original, current, updated, and final values.
  64
  65 \end{basedescript}
  66
  67 \stdsection{Inputs to the update algorithm}
  68
  69 \begin{basedescript}{
  70 \desclabelwidth{5em}
  71 \desclabelstyle{\nextlinelabel}
  72 }
  73 \item[ $\pc_0$ ]
  74 The topmost patch which we are trying to update.  This and
  75 all of its dependencies will be updated.
  76
  77 \item[ $h : \pc^{+/-} \mapsto \set H^{\pc^{+/-}}$ ]
  78 Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
  79 These are the heads which will be merged and used in this update.
  80 This will include the current local and remote git refs, as desired.
  81
  82 \item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
  83 Function to allow explicit adjustment of the direct dependencies
  84 of $\pc$.  It is provided with a putative set of direct dependencies
  85 $\Gamma$ computed as an appropriate merge of the dependencies requested by the
  86 sources and should return the complete actual set $\Gamma'$ of direct
  87 dependencies to use.  This allows the specification of any desired
  88 (acyclic) relations $\hasdirdep$ and $\hasdep$.
  89
  90 \end{basedescript}
  91
  92 \stdsection{Important variables and values in the update algorithm}
  93
  94 \begin{basedescript}{
  95 \desclabelwidth{5em}
  96 \desclabelstyle{\nextlinelabel}
  97 }
  98 \item[ $\Gamma_{\pc}$ ]
  99 The desired direct dependencies of $\pc$, a set of patches.
 100
 101 \item[ $\allpatches$ ]
 102 The set of all the patches we are dealing with (constructed
 103 during the update algorithm).
 104
 105 \item[ $\tipcn, \tipcy$ ]
 106 The new tips of the git branches $\pcn$ and $\pcy$, containing
 107 all the appropriate commits (and the appropriate other patches),
 108 as generated by the Traversal phase of the update algorithm.
 109
 110 \end{basedescript}
 111
 112 \stdsection{ WIP tip satisfaction, reachable commits }
 113
 114 Set of all reachable commits, O.
 115
 116 A reachable commit is one we might refer to explicitly in any of these
 117 algorithms, and any ancestor of such a commit.  We explicitly
 118 enumerate all of the input commits (U).  And each commit we generate
 119 will be descended from zero or more of these.
 120
 121 Naturally this set varies over time as we generate more commits.  We
 122 write O_pyn for the set of reachable commits at the point where we
 123 have just generated T_pyn.
 124
 125 We preserve/ensure
 126   Tip_Pyn >= pendsof( O_pyn, Pyn )
 127 (Tip_pyn is computed during traversal for the patch p)
 128
 129 We ensure this property by:
 130   - we do not generate any commits for pyn other than
 131     during traversal for pyn
 132   - so at the start of traversal pendsof ( O, pyn) = pendsof (U, pyn)
 133   - the traversal steps will takes those pends
 134
 135   - during traversal for the patch set pyn
 136     pendsof
 137
 138   - arranging that during traversal for the patch set pyn
 139
 140 , we firstly
 141     compute a tip_pyn which is >= pendsof(O) as follows:
 142       there is a set of relevant ends
 143               pendsof(U,
 144
 145       we initially set T
 146
 147     by virtue of it being  >= pendsof(U) \cup
 148     all lower tip_qyn
 149  -
 150
 151 We do this by:
 152  - firstly, Tip_pyn is only valid af
 153
 154
 155 Set of all reachable commits in a particular patch set.
 156  This consists of
 157   - input commits
 158   -
 159