--- /dev/null
+Basic update algorithm:
+
+XXX THIS IS ALMOST ENTIRELY WRONG - SEE "THEORY" XXX
+
+ 1. recurse to all of our direct dependencies and
+ update their bases and tips
+
+ 2. Update our base.
+
+ i. Compute our base's set of desired included deps:
+ The set of desired included deps for a base
+ is the union of the desired included deps for each
+ branch named in the base's branch's direct deps, plus
+ the name of every direct external dep.
+ The set of desired included deps for a branch
+ is the set of desired included deps for the branch's
+ base plus the branch name itself.
+
+ ii. For each source in the best order, do the following merge:
+ (Our base has sources:
+ - the branch for each direct dep
+ - the remote base
+ - the topgit base, if this is a topgit import)
+
+ Find the (latest) common ancestor.
+
+ Check for unwanted dependency removals.
+ An unwanted dependency removal is
+ A branch in the desired included deps
+ Which exists in the common ancestor's actual included deps
+ but which is missing in the source's actual included deps
+ (NB that this definition excludes dependency removals
+ which have already occurred on our base; these will be
+ reverted later.)
+ For each unwanted dependency removal (ie for each such
+ branch), search as follows:
+ * An "unwanted removal commit" is a non-merge commit in the
+ history of the source, which removes the dep from the
+ actual included deps.
+ * But the search stops at any point where we would have to
+ traverse a commit where .topbloke/deps is empty (which
+ stops us looking into the hitory of non-topbloke-controlled
+ branches). This can be done with git-rev-list
+ --remove-empty.
+ * It also stops at any point where we meet a commit which
+ does have the dep in the actual included deps. We have
+ to do this by hand.
+ * The the relevant unwanted removal commit for that dep is
+ the most recent unwanted removal commit, as defined.
+ Select the unwantedly removed dep whose relevant unwanted
+ removal commit is the earliest. Merge from the ancestor of
+ that relevant unwanted removal commit. Merge from the relevant
+ unwanted removal commit using -s ours.
+
+ Now continue to the next unwanted dependency removal.
+
+ (The purpose of this, and the result, is that the unwanted
+ dependency removal has gone away. Doing things in this order
+ tries to keep the unwanted dependency removal's reversions as
+ close as possible to their originating points. The
+ recursion, which processes dependencies before their clients,
+ tries to keep the reversion churn localised: client patches
+ of a patch affected by an unwanted removal will benefit from
+ that client's resolution of the situation.)
+
+ If there are no (more) unwanted dependency removals, merge
+ from the source.
+
+ iii.
+ Check whether our list of dependencies has changed. If so
+ we need to restart the whole base update.
+
+ iv.
+ Check for missing or unwanted dependency inclusions. Compare
+ our base's desired included deps with our base's actual
+ included deps. In exceptional conditions, they will not
+ be identical. This can happen, for example, because a
+ dependency removal was incorporated into our base branch but
+ the removed branch was introduced as an explicit dependency.
+ This will also happen if we remove a dependency ourselves.
+
+ Do the unwanted inclusions first, and then the missing ones.
+ (This is because that the missing ones cannot depend on the
+ unwanted ones, as otherwise the unwanted ones would be in the
+ desired inclusions. So removing the unwanted ones first
+ reduces the chances of conflicts.)
+
+ So, repeatedly:
+ * Do the comparison between desired and actual included
+ * Pick a missing inclusion, or failing that an unwanted one
+ (call this the "relevant" branch)
+ * Depth first search all of the dependencies of the
+ relevant branch; if any of these is also a missing
+ (resp. unwanted) inclusion, start again processing it
+ instead.
+ * Attempt to apply the appropriate diff to add (resp. remove)
+ the contents of the relevant patch (adjusted appropriately
+ for metadata, XXX??? particularly the actual inclusion list)
+ XXX if we want to add a dep we need to update the dep first
+ * Go round again looking for another discrepancy.
+
+ 3. Update our branch.
+ Our branch has sources:
+ - our base
+ - the remote for our branch
+ - the topgit branch, if this is a topgit import
+ For each source in the best order, do the merge.
+
+ Double-check the actual dependency inclusions. In
+ particular, if we just upgraded to actual dependency tracking
+ we may need to explicitly add our branch name to the actual
+ dependency inclusion list.
+
+The "best order" for merges is in order of recency of common
+ancestor, most recent first, and if that does not distinguish,
+merging from local branches first.
+
+"Recency" refers to the order from git-rev-list --date-order.
~ian / topbloke.git / blobdiff