UPDATE-ALGORITHM

   1 Basic update algorithm:
   2
   3 XXX THIS IS ALMOST ENTIRELY WRONG - SEE "THEORY" XXX
   4
   5  1. recurse to all of our direct dependencies and
   6     update their bases and tips
   7
   8  2. Update our base.
   9
  10     i. Compute our base's set of desired included deps:
  11          The set of desired included deps for a base
  12          is the union of the desired included deps for each
  13          branch named in the base's branch's direct deps, plus
  14          the name of every direct external dep.
  15          The set of desired included deps for a branch
  16          is the set of desired included deps for the branch's
  17          base plus the branch name itself.
  18
  19     ii. For each source in the best order, do the following merge:
  20         (Our base has sources:
  21             - the branch for each direct dep
  22             - the remote base
  23             - the topgit base, if this is a topgit import)
  24
  25        Find the (latest) common ancestor.
  26
  27        Check for unwanted dependency removals.
  28        An unwanted dependency removal is
  29           A branch in the desired included deps
  30           Which exists in the common ancestor's actual included deps
  31           but which is missing in the source's actual included deps
  32           (NB that this definition excludes dependency removals
  33           which have already occurred on our base; these will be
  34           reverted later.)
  35        For each unwanted dependency removal (ie for each such
  36        branch), search as follows:
  37           * An "unwanted removal commit" is a non-merge commit in the
  38             history of the source, which removes the dep from the
  39             actual included deps.
  40           * But the search stops at any point where we would have to
  41             traverse a commit where .topbloke/deps is empty (which
  42             stops us looking into the hitory of non-topbloke-controlled
  43             branches).  This can be done with git-rev-list
  44             --remove-empty.
  45           * It also stops at any point where we meet a commit which
  46             does have the dep in the actual included deps.  We have
  47             to do this by hand.
  48           * The the relevant unwanted removal commit for that dep is
  49             the most recent unwanted removal commit, as defined.
  50        Select the unwantedly removed dep whose relevant unwanted
  51        removal commit is the earliest.  Merge from the ancestor of
  52        that relevant unwanted removal commit.  Merge from the relevant
  53        unwanted removal commit using -s ours.
  54
  55        Now continue to the next unwanted dependency removal.
  56
  57        (The purpose of this, and the result, is that the unwanted
  58        dependency removal has gone away.  Doing things in this order
  59        tries to keep the unwanted dependency removal's reversions as
  60        close as possible to their originating points.  The
  61        recursion, which processes dependencies before their clients,
  62        tries to keep the reversion churn localised: client patches
  63        of a patch affected by an unwanted removal will benefit from
  64        that client's resolution of the situation.)
  65
  66        If there are no (more) unwanted dependency removals, merge
  67        from the source.
  68
  69     iii.
  70        Check whether our list of dependencies has changed.  If so
  71        we need to restart the whole base update.
  72
  73     iv.
  74        Check for missing or unwanted dependency inclusions.  Compare
  75        our base's desired included deps with our base's actual
  76        included deps.  In exceptional conditions, they will not
  77        be identical.  This can happen, for example, because a
  78        dependency removal was incorporated into our base branch but
  79        the removed branch was introduced as an explicit dependency.
  80        This will also happen if we remove a dependency ourselves.
  81
  82        Do the unwanted inclusions first, and then the missing ones.
  83        (This is because that the missing ones cannot depend on the
  84        unwanted ones, as otherwise the unwanted ones would be in the
  85        desired inclusions.  So removing the unwanted ones first
  86        reduces the chances of conflicts.)
  87
  88        So, repeatedly:
  89          * Do the comparison between desired and actual included
  90          * Pick a missing inclusion, or failing that an unwanted one
  91            (call this the "relevant" branch)
  92          * Depth first search all of the dependencies of the
  93            relevant branch; if any of these is also a missing
  94            (resp. unwanted) inclusion, start again processing it
  95            instead.
  96          * Attempt to apply the appropriate diff to add (resp. remove)
  97            the contents of the relevant patch (adjusted appropriately
  98            for metadata, XXX??? particularly the actual inclusion list)
  99            XXX if we want to add a dep we need to update the dep first
 100          * Go round again looking for another discrepancy.
 101
 102  3. Update our branch.
 103        Our branch has sources:
 104           - our base
 105           - the remote for our branch
 106           - the topgit branch, if this is a topgit import
 107        For each source in the best order, do the merge.
 108
 109        Double-check the actual dependency inclusions.  In
 110        particular, if we just upgraded to actual dependency tracking
 111        we may need to explicitly add our branch name to the actual
 112        dependency inclusion list.
 113
 114 The "best order" for merges is in order of recency of common
 115 ancestor, most recent first, and if that does not distinguish,
 116 merging from local branches first.
 117
 118 "Recency" refers to the order from git-rev-list --date-order.