trav-alg.tex

   1 \section{Traversal phase --- algorithm}
   2
   3 (In general, unless stated otherwise below, when we generate a new
   4 commit $C$ using one of the commit kind algorith, we update
   5 $W \assign C$.  In any such case where we say we're going to Merge
   6 with $L = W$, if $R \ge W$ we do not Merge but instead simply set
   7 $W \assign R$.)
   8
   9
  10 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
  11 lowest first:
  12
  13 \begin{enumerate}
  14
  15 \item Optionally, attempt
  16  $\alg{Merge-Base}(\pc)$.  This may or may not succeed.
  17
  18 \item If this didn't succeed, or was not attempted, execute
  19  $\alg{Recreate-Base}(\pc)$.
  20
  21 \item Then in any case, execute
  22  $\alg{Merge-Tip}(\pc)$.
  23
  24 \end{enumerate}
  25
  26 After processing each $\pc$ we will have created:
  27
  28 \begin{itemize}
  29
  30 \item $\tipcn$ and $\tipcy$ such that $\baseof{\tipcy} = \tipcn$.
  31
  32 \end{itemize}
  33
  34 \subsection{$\alg{Merge-Base}(\pc)$}
  35
  36 This algorithm attempts to construct a suitably updated version of the
  37 base branch $\pcn$ using some existing version of $\pcn$ as a starting
  38 point.
  39
  40 It should be executed noninteractively.  Specifically, if any step
  41 fails with a merge conflict, the whole thing should be abandoned.
  42 This avoids asking the user to resolve confusing conflicts.  It also
  43 avoids asking the user to pointlessly resolve conflicts in situations
  44 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
  45 after all.
  46
  47 If $\pc$ has only one direct dependency, this algorithm should not be
  48 used as in that case $\alg{Recreate-Base}$ is trivial and guaranteed
  49 to generate a perfect answer, whereas this algorithm might involve
  50 merges and therefore might not produce a perfect answer if the
  51 situation is complicated.
  52
  53 Initially, set $W \iassign W^{\pcn}$.
  54
  55 \subsubsection{Bases and sources}
  56
  57 In some order, perhaps interleaving the two kinds of merge:
  58
  59 \begin{enumerate}
  60
  61 \item For each $\pd \isdirdep \pc$, find a merge base
  62 $M \le W,\; \le \tipdy$ and merge $\tipdy$ into $W$.
  63 That is, use $\alg{Merge}$ with $L = W,\; R = \tipdy$.
  64 (Dependency Merge.)
  65
  66 \item For each $S \in S^{\pcn}_i$, merge it into $W$.
  67 That is, use $\alg{Merge}$ with $L = W,\; R = S,\; M = M^{\pcn}_i$.
  68 (Base Sibling Merge.)
  69
  70 \end{enumerate}
  71
  72 \subsubsection{Fixup}
  73
  74 Execute $\alg{Fixup-Base}(W,\pc)$.
  75
  76
  77 \subsection{$\alg{Recreate-Base}(\pc)$}
  78
  79 \begin{enumerate}
  80
  81 \item
  82
  83 Choose a $\hasdep$-maximal direct dependency $\pd$ of $\pc$.
  84
  85 \item
  86
  87 Use $\alg{Create Base}$ with $L$ = $\pdy,\; \pq = \pc$ to generate $C$
  88 and set $W \iassign C$.  (Recreate Base Beginning.)
  89
  90 \item
  91
  92 Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.
  93
  94 \item
  95
  96 Declare that we contain all of the relevant information from the
  97 sources.  That is, use $\alg{Pseudo-merge}$ with $L = W, \;
  98 \set R = \{ W \} \cup \set S^{\pcn}$.
  99 (Recreate Base Final Declaration.)
 100
 101 \end{enumerate}
 102
 103 \subsubsection{$\alg{Recreate-Recurse}(\pd)$}
 104
 105 \begin{enumerate}
 106
 107 \item Is $W \haspatch \pd$ ?  If so, there is nothing to do: return.
 108
 109 \item TODO what about non-Topbloke base branches
 110
 111 \item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
 112 (Recreate Base Dependency Base Declaration.)
 113
 114 \item For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
 115 execute $\alg{Recreate-Recurse}(\pd')$.
 116
 117 \item Use $\alg{Merge}$ to apply $\pd$ to $W$.  That is,
 118 $L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
 119 (Recreate Reapply.)
 120
 121 \end{enumerate}
 122
 123
 124 \subsection{$\alg{Merge-Tip}(\pc)$}
 125
 126 \begin{enumerate}
 127
 128 \item TODO CHOOSE/REFINE W AND S as was done during Ranking for bases
 129
 130 \item $\alg{Merge}$ from $\tipcn$.  That is, $L = W, \;
 131 R = \tipcn$ and choose any suitable $M$.  (Tip Base Merge.)
 132
 133 \item For each source $S \in \set S^{\pcy}$,
 134 $\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.
 135 (Tip Source Merge.)
 136
 137 \end{enumerate}
 138
 139