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 recipies, 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 $\tipcn$ and $\tipcy$
  27 such that:
  28
  29 \statement{Correct Base}{
  30   \baseof{\tipcy} = \tipcn
  31 }
  32 \statement{Tip Exceeds Inputs}{
  33   \tipcy \ge \pendsof{\allsrcs}{\pcy}
  34 }
  35 \statement{Base Exceeds Inputs' Bases}{
  36   \bigforall_{E \in \pendsof{\allsrcs}{\pcy}} \tipcn \ge \baseof{E}
  37 }
  38 \statement{Base Exceeds Base Inputs}{
  39   \bigforall_{H \in \set H^{\pn}} \tipcn \ge H
  40 }
  41
  42 \subsection{$\alg{Merge-Base}(\pc)$}
  43
  44 This algorithm attempts to construct a suitably updated version of the
  45 base branch $\pcn$ using some existing version of $\pcn$ as a starting
  46 point.
  47
  48 It should be executed noninteractively.  Specifically, if any step
  49 fails with a merge conflict, the whole thing should be abandoned.
  50 This avoids asking the user to resolve confusing conflicts.  It also
  51 avoids asking the user to pointlessly resolve conflicts in situations
  52 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
  53 after all.
  54
  55 If $\pc$ has only one direct dependency, this algorithm should not be
  56 used as in that case $\alg{Recreate-Base}$ is trivial and guaranteed
  57 to generate a perfect answer, whereas this algorithm might involve
  58 merges and therefore might not produce a perfect answer if the
  59 situation is complicated.
  60
  61 Initially, set $W \iassign W^{\pcn}$.
  62
  63 \subsubsection{Bases and sources}
  64
  65 In some order, perhaps interleaving the two kinds of merge:
  66
  67 \begin{enumerate}
  68
  69 \item For each $\hasdep$-maximal $\pd \isdirdep \pc$, find a merge base
  70 $M \le W,\; \le \tipdy$ and merge $\tipdy$ into $W$.
  71 That is, use $\alg{Merge}$ with $L = W,\; R = \tipdy$.
  72 (Base Dependency Merge.)
  73
  74 \item For each $S \in S^{\pcn}_i$, merge it into $W$.
  75 That is, use $\alg{Merge}$ with $L = W,\; R = S,\; M = M^{\pcn}_i$.
  76 (Base Sibling Merge.)
  77
  78 \end{enumerate}
  79
  80 \subsubsection{Fixup}
  81
  82 Execute $\alg{Fixup-Base}(W,\pc)$.
  83
  84 \subsubsection{Result}
  85
  86 If all of that was successful, let $\tipcn = W$.
  87
  88 \subsection{$\alg{Recreate-Base}(\pc)$}
  89
  90 \begin{enumerate}
  91
  92 \item
  93
  94 Choose a $\hasdep$-maximal direct dependency $\pd$ of $\pc$.
  95
  96 \item
  97
  98 Use $\alg{Create Base}$ with $L$ = $\pdy,\; \pq = \pc$ to generate $C$
  99 and set $W \iassign C$.  (Recreate Base Beginning.)
 100
 101 \item
 102
 103 Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.
 104
 105 \item
 106
 107 Declare that we contain all of the relevant information from the
 108 sources.  That is, use $\alg{Pseudo-Merge}$ with $L = W, \;
 109 \set R = \{ W \} \cup \set S^{\pcn}$.
 110 (Recreate Base Final Declaration.)
 111
 112 \end{enumerate}
 113
 114 \subsubsection{$\alg{Recreate-Recurse}(\pd)$}
 115
 116 \begin{enumerate}
 117
 118 \item Is $W \haspatch \pd$ ?  If so, there is nothing to do: return.
 119
 120 \item TODO what about non-Topbloke base branches
 121
 122 \item For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
 123 execute $\alg{Recreate-Recurse}(\pd')$.
 124
 125 \item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
 126 (Recreate Base Dependency Base Declaration.)
 127
 128 \item Use $\alg{Merge}$ to apply $\pd$ to $W$.  That is,
 129 $L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
 130 (Recreate Reapply.)
 131
 132 \end{enumerate}
 133
 134
 135 \subsection{$\alg{Merge-Tip}(\pc)$}
 136
 137 \begin{enumerate}
 138
 139 \item TODO CHOOSE/REFINE W AND S as was done during Ranking for bases
 140
 141 \item $\alg{Merge}$ from $\tipcn$.  That is, $L = W, \;
 142 R = \tipcn$ and choose any suitable $M$.  (Tip Base Merge.)
 143
 144 \item For each source $S \in \set S^{\pcy}$,
 145 $\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.
 146 (Tip Source Merge.)
 147
 148 \end{enumerate}
 149
 150