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