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[ $\set E_{\pc}$ ]
  54 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
  55 %All the ends of $\pc$ in the sources.
  56
  57 %\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
  58 %The git ref for the Topbloke commit set $\pc$: respectively,
  59 %the original, current, updated, and final values.
  60
  61 \end{basedescript}
  62
  63 \stdsection{Inputs to the update algorithm}
  64
  65 \begin{basedescript}{
  66 \desclabelwidth{5em}
  67 \desclabelstyle{\nextlinelabel}
  68 }
  69 \item[ $\pc_0$ ]
  70 The topmost patch which we are trying to update.  This and
  71 all of its dependencies will be updated.
  72
  73 \item[ $h : \pc^{+/-} \mapsto \set H_{\pc^{+/-}}$ ]
  74 Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
  75 These are the heads which will be merged and used in this update.
  76 This will include the current local and remote git refs, as desired.
  77
  78 \item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
  79 Function to allow explicit adjustment of the direct dependencies
  80 of $\pc$.  It is provided with a putative set of direct dependencies
  81 $\Gamma$ computed as an appropriate merge of the dependencies requested by the
  82 sources and should return the complete actual set $\Gamma'$ of direct
  83 dependencies to use.  This allows the specification of any desired
  84 (acyclic) relations $\hasdirdep$ and $\hasdep$.
  85
  86 \end{basedescript}
  87
  88 \stdsection{Important variables and values in the update algorithm}
  89
  90 \begin{basedescript}{
  91 \desclabelwidth{5em}
  92 \desclabelstyle{\nextlinelabel}
  93 }
  94 \item[ $\Gamma_{\pc}$ ]
  95 The desired direct dependencies of $\pc$, a set of patches.
  96
  97 \item[ $\allpatches$ ]
  98 The set of all the patches we are dealing with (constructed
  99 during the update algorithm).
 100
 101 \end{basedescript}
 102
 103 \section{Ranking phase}
 104
 105 We run the following algorithm:
 106 \begin{enumerate}
 107 \item Set $\allpatches = \{ \}$.
 108 \item Repeatedly:
 109 \begin{enumerate}
 110 \item Clear out the graph $\hasdirdep$ so it has no edges.
 111 \item Execute $\alg{Rank-Recurse}(\pc_0)$
 112 \item Until $\allpatches$ remains unchanged.
 113 \end{enumerate}
 114 \end{enumerate}
 115
 116 $\alg{Rank-Recurse}(\pc)$ is:
 117 \begin{enumerate}
 118
 119 \item If we have already done $\alg{Rank-Recurse}(\pc)$ in this
 120 ranking iteration, do nothing.  Otherwise:
 121
 122 \item Add $\pc$ to $\allpatches$ if it is not there already.
 123
 124 \item Set
 125 $$
 126   \set S \iassign h(\pcn)
 127      \cup
 128         \bigcup_{\p \in \allpatches}
 129         \bigcup_{H \in h(\pn) \lor H \in h(\py)}
 130          \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \}
 131 $$
 132
 133 and $W \iassign w(h(\pcn))$
 134
 135 \item While $\exists_{S \in \set S} S \ge W$,
 136 update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$
 137
 138 (This will often remove $W$ from $\set S$.  Afterwards, $\set S$
 139 is a collection of heads to be merged into $W$.)
 140
 141 \item Choose an ordering of $\set S$, $S_i$ for $i=1 \ldots n$.
 142
 143 \item For each $S_i$ in turn, choose a corresponding $M_i$
 144 such that $$
 145    M_i \le S_i \land \left[
 146    M_i \le W \lor \bigexists_{j<i} M_i \le S_j
 147    \right]
 148 $$
 149
 150 \item Set $\Gamma \iassign \depsreqof{W}$.
 151
 152 If there are multiple candidates we prefer $M_i \in \pcn$
 153 if available.
 154
 155 \item For each $i \ldots 1..n$, update our putative direct
 156 dependencies:
 157 $$
 158 \Gamma \assign \setmergeof{
 159     \Gamma
 160   }{
 161     \begin{cases}
 162      M_i \in \pcn :     & \depsreqof{M_i} \\
 163      M_i \not\in \pcn : & \{ \}
 164     \end{cases}
 165   }{
 166     \depsreqof{S_i}
 167   }
 168 $$
 169
 170 TODO define $\setmerge$
 171
 172 \item Finalise our putative direct dependencies
 173 $
 174 \Gamma \assign g(\pc, \Gamma)
 175 $
 176
 177 \item For each direct dependency $\pd \in \Gamma$,
 178
 179 \begin{enumerate}
 180 \item Add an edge $\pc \hasdirdep \pd$ to the digraph (adding nodes
 181 as necessary).
 182 If this results in a cycle, abort entirely (as the function $g$ is
 183 inappropriate; a different $g$ could work).
 184 \item Run $\alg{Rank-Recurse}(\pd)$.
 185 \end{enumerate}
 186
 187 \end{enumerate}
 188
 189 \subsection{Results of the ranking phase}
 190
 191 By the end of the ranking phase, we have recorded the following
 192 information:
 193
 194 \begin{itemize}
 195 \item
 196 $ \allpatches, \hasdirdep $ and hence the completion of $\hasdirdep$
 197 into the partial order $\hasdep$.
 198
 199 \item
 200 For each $\pc \in \allpatches$,
 201 the base branch starting point commit $W^{\pcn} = W$.
 202
 203 \item
 204 For each $\pc$,
 205 the direct dependencies $\Gamma^{\pc} = \Gamma$.
 206
 207 \item
 208 For each $\pc$,
 209 the ordered set of base branch sources $\set S^{\pcn} = \set S,
 210 S^{\pcn}_i = S_i$
 211 and corresponding merge bases $M^{\pcn}_i = M_i$.
 212
 213 \end{itemize}
 214
 215 \subsection{Proof of termination}
 216
 217 $\alg{Rank-Recurse}(\pc)$ recurses but only downwards through the
 218 finite graph $\hasdirdep$, so it must terminate.
 219
 220 The whole ranking algorithm iterates but each iteration involves
 221 adding one or more patches to $\allpatches$.  Since there are
 222 finitely many patches and we never remove anything from $\allpatches$
 223 this must complete eventually.
 224
 225 $\qed$
 226
 227 \section{Traversal phase}
 228
 229 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
 230 lowest first:
 231
 232 \begin{enumerate}
 233
 234 \item Optionally, attempt
 235  $\alg{Merge-Base}(\pc)$.  This may or may not succeed.
 236
 237 \item If this didn't succeed, or was not attempted, execute
 238  $\alg{Recreate-Base}(\pc)$.
 239
 240 \item Then in any case, execute
 241  $\alg{Merge-Tip}(\pc)$.
 242
 243 \end{enumerate}
 244
 245 After processing each $\pc$ we will have created:
 246
 247 \begin{itemize}
 248
 249 \item tip
 250
 251 \end{itemize}
 252
 253 \subsection{$\alg{Merge-Base}(\pc)$}
 254
 255 This algorithm attempts to construct a suitably updated version of the
 256 base branch $\pcn$.
 257
 258 It should be executed noninteractively.  Specifically, if any step
 259 fails with a merge conflict, the whole thing should be abandoned.
 260 This avoids asking the user to resolve confusing conflicts.  It also
 261 avoids asking the user to pointlessly resolve conflicts in situations
 262 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
 263 after all.
 264
 265 \subsubsection{Bases and sources}
 266
 267 In some order, perhaps interleaving the two kinds of merge:
 268
 269 \begin{enumerate}
 270
 271 \item For each $\pd \isdirdep \pc$, merge $\pd$
 272
 273 \item
 274
 275 \end{enumerate}
 276
 277
 278