From eacdc5333e25e51df71366d5a55ae8a6b0c5eb86 Mon Sep 17 00:00:00 2001
From: Ian Jackson <ijackson@chiark.greenend.org.uk>
Date: Sat, 12 May 2012 00:21:12 +0100
Subject: [PATCH] strategy: new, wip

---
 article.tex  |  2 ++
 strategy.tex | 81 +++++++++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 73 insertions(+), 10 deletions(-)

diff --git a/article.tex b/article.tex
index add5d52..052ed36 100644
--- a/article.tex
+++ b/article.tex
@@ -92,6 +92,8 @@
 \newcommand{\baseof}[1]{\base ( #1 ) }
 \newcommand{\depsreqof}[1]{\depsreq ( #1 ) }
 
+\newcommand{\allpatches}{\Upsilon}
+
 \newcommand{\eqntag}[2]{ #2 \tag*{\mbox{#1}} }
 \newcommand{\eqn}[2]{ #2 \tag*{\mbox{\bf #1}} }
 
diff --git a/strategy.tex b/strategy.tex
index eff0adf..6f5de70 100644
--- a/strategy.tex
+++ b/strategy.tex
@@ -1,10 +1,27 @@
-When we are trying to do an update of some kind, in general,
-for each patch $\pc$
-we want to merge some source commits $S \in \set S_{\pc}$.
-We require $\patchof{S} = \pc$,
-and $\tipcc \in \set S_{\pc}$.
-
-\stdsection{Notation}
+Here we describe the update algorithm.  This is responsible for
+refreshing patches against updated versions of their dependencies,
+for merging different versions of the various braches created by
+distributed development, and for implementing decisions to add and
+remove dependencies from patches.
+
+Broadly speaking the update proceeds as follows: during the Ranking
+phase we construct the intended graph of dependencies between patches
+(which involves select a merge order for the base branch of each
+patch).  Then during the Traversal phase we walk that graph from the
+bottom up, constructing for each patch by a series of merges and other
+operations first a new base branch head commit and then a new tip
+branch head commit.  These new head commits are maximums - that is,
+each has as ancestors all of its branches' sources and indeed all
+relevant commits in that branch.
+
+We have two possible strategies for constructing new base branch
+heads: we can either Merge (works incrementally even if there the
+patch has multiple dependencies, but may sometimes not be possible) or
+we can Regenerate (trivial if there is a single dependency, and is
+always possible, but may involve the user re-resolving conflicts if
+there are multiple dependencies).
+
+\section{Notation}
 
 \begin{basedescript}{
 \desclabelwidth{5em}
@@ -24,16 +41,60 @@ set $\pq$.
 Acyclic; the completion of $\hasdirdep$ into a
 partial order.
 
+\item[ $\pendsof{\set J}{\p}$ ]
+Convenience notation for
+the maximal elements of $\bigcup_{J \in \set J} \pendsof{J}{\p}$
+(where $\set J$ is some set of commits).
+
+\item[ $\pendsof{\set X}{\p} \le T$ ]
+Convenience notation for
+$\bigforall_{E \in \pendsof{\set X}{\p}} E \le T$
+
 %\item[ $\set E_{\pc}$ ]
 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
 %All the ends of $\pc$ in the sources.
 
-\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
-The git ref for the Topbloke commit set $\pc$: respectively,
-the original, current, updated, and final values.
+%\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
+%The git ref for the Topbloke commit set $\pc$: respectively,
+%the original, current, updated, and final values.
+
+\end{basedescript}
+
+\stdsection{Inputs to the update algorithm}
+
+\begin{basedescript}{
+\desclabelwidth{5em}
+\desclabelstyle{\nextlinelabel}
+}
+\item[ $\pc_0$ ]
+The topmost patch which we are trying to update.  This and
+all of its dependencies will be updated.
+
+\item[ $h : \pc^{+/-} \mapsto \set H_{\pc^{+/-}}$ ]
+Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
+This will include the current local and remote git refs, as desired.
+
+\item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
+Function to allow explicit adjustment of the direct dependencies
+of $\pc$.  It is provided with a putative set of direct dependencies
+$\Gamma$ computed as an appropriate merge of the dependencies requested by the
+sources and should return the complete actual set $\Gamma'$ of direct
+dependencies to use.  This allows the specification of any desired
+(acyclic) relation $\hasdirdep$.
 
 \end{basedescript}
 
+\section{Ranking phase}
+
+We start with $\allpatches = \{ \}$.  We repeat
+{\bf Rank-Recurse}($\pc_0$) until $\allpatches$ is unchanged.
+
+{\bf Rank-Recurse}($\pc$) is:
+\begin{enumerate}
+\item foo
+\item bar
+\end{enumerate}
+
 \section{Planning phase}
 
 The results of the planning phase consist of: 
-- 
2.30.2