DESIGN

   1 Basic update algorithm:
   2
   3  1. recurse to all of our direct dependencies and
   4     update their bases and branches
   5
   6  2. Update our base.
   7
   8     i. Compute our base's set of desired included branches:
   9          The set of desired included branches for a base
  10          is the union of the desired included branches for each
  11          branch named in the base's branch's direct deps, plus
  12          the name of every direct external dep.
  13          The set of desired included branches for a branch
  14          is the set of desired included branches for the branch's
  15          base plus the branch name itself.
  16
  17     ii. For each source in the best order, do the following merge:
  18         (Our base has sources:
  19             - the branch for each direct dep
  20             - the remote base)
  21
  22        Find the common ancestor.
  23
  24        Check for unwanted dependency removals.
  25        An unwanted dependency removal is
  26           A branch in the desired included branches
  27           Which exists in the common ancestor's actual included branches
  28           but which is missing in the source's actual included branches
  29           (NB that this definition excludes dependency removals
  30           which have already occurred on our base; these will be
  31           reverted later.)
  32        For each unwanted dependency removal (ie for each such
  33        branch), find the most recent commit which unwantedly removed
  34        the dep from the source's actual included branches ("relevant
  35        unwanted removal commit").  (Abort if any such commit is a
  36        merge.)  Select the earliest relevant unwanted removal commit
  37        (from the set of relevant unwanted removal commits
  38        corresponding to the unwanted dependency removals).
  39        Merge from the ancestor of the relevant unwanted removal commit.
  40        Merge from the relevant unwanted removal commit using -s ours.
  41
  42        (The purpose of this, and the result, is that the unwanted
  43        dependency removal has gone away.  Doing things in this order
  44        tries to keep the unwanted dependency removal's reversions as
  45        close as possible to their originating points.  The
  46        recursion, which processes dependencies before their clients,
  47        tries to keep the reversion churn localised: client branches
  48        of a branch affected by an unwanted removal will benefit from
  49        that client's resolution of the situation.)
  50
  51        Now continue to the next unwanted dependency removal.
  52
  53        If there are no (more) unwanted dependency removals, merge
  54        from the source.
  55
  56     iii.
  57        Check for missing or unwanted dependency inclusions.  Compare
  58        our base's desired included branches with our base's actual
  59        included branches.  In exceptional conditions, they will not
  60        be identical.  This can happen, for example, because a
  61        dependency removal was incorporated into our base branch but
  62        the removed branch was introduced as an explicit dependency.
  63        This will also happen if we remove a dependency ourselves.
  64
  65        Do the unwanted inclusions first, and then the missing ones.
  66        (This is because that the missing ones cannot depend on the
  67        unwanted ones, as otherwise the unwanted ones would be in the
  68        desired inclusions.  So removing the unwanted ones first
  69        reduces the chances of conflicts.)
  70
  71        So, repeatedly:
  72          * Do the comparison between desired and actual included
  73          * Pick a missing inclusion, or failing that an unwanted one
  74            (call this the "relevant" branch)
  75          * Depth first search all of the dependencies of the
  76            relevant branch; if any of these is also a missing
  77            (resp. unwanted) inclusion, start again processing it
  78            instead.
  79          * Attempt to apply the appropriate diff to add (resp. remove)
  80            the contents of the relevant patch (adjusted appropriately
  81            for metadata, XXX??? particularly the actual inclusion list)
  82          * Go round again looking for another discrepancy.
  83
  84  3. Update our branch.
  85        Our branch has sources:
  86           - our base
  87           - the remote for our branch
  88        For each source in the best order, do the merge.
  89
  90        Double-check the actual dependency inclusions.  In
  91        particular, if we just upgraded to actual dependency tracking
  92        we may need to explicitly add our branch name to the actual
  93        dependency inclusion list.
  94
  95 The "best order" for merges is in order of recency of common
  96 ancestor, most recent first, and if that does not distinguish,
  97 merging from local branches first.
  98
  99 "Recency" refers to the order from git-rev-list --date-order.
 100
 101 Actual included branches:
 102
 103   This is tracked explicitly in .topbloke/included, one branch per
 104   line.  For compatibility with older versions, every time we think
 105   about a base, branch or source above, we check whether
 106   .topbloke/included is present.
 107
 108   If it isn't then we calculate a child commit which has a
 109   .topbloke/included.  In the case of a remote branch or base, we
 110   substitute this child commit for the relevant remote ref but do
 111   not record it in the remote ref; in the case of a local branch or
 112   base, we advance the local branch or base accordingly.
 113
 114   When .topbloke/included is calculated in this way, it always gets
 115   the list of desired included branches.  (topgit,
 116   which does not support dependency deletion, always has exactly the
 117   desired branches actually included.)
 118
 119   Non-topbloke-controlled branches are never recorded in included.
 120
 121
 122 Branch removal:
 123
 124  - removed branch must be removed from the deps of its
 125    ex-children, and replaced with the deps of the removed
 126    branch
 127
 128  - removed branch wants not to be in list of branches "git-branch"
 129    et al any more
 130       branches in refs/top-branches ?  yes
 131       deleted branches do something to the base ?  no
 132
 133  deleting empty branch: dependencies fine
 134  deleting nonempty branch: if any dependencies found, their
 135     updates break
 136
 137  purpose of deleting?
 138    - remove from views of active branches
 139    - prevent new commits
 140    - remove from dependencies of active branches
 141        only makes sense if no active branches depend on it.
 142
 143  undeleting
 144    - just unmark the branch as deleted
 145
 146 Branch naming:
 147  needs to be globally unique
 148  so put email address in it
 149 tg operations search for applicable branches
 150 safe charset for branch names
 151   . - / 0-9 a-z
 152 not permitted (git-check-ref-format(1))
 153  spc ~ ^ : ? * [ \
 154  @{ .lock.
 155  (apropos of shell)
 156
 157
 158 When pulling, which remotes get to update which branches ?
 159 Complicated question!
 160
 161 For now, have "blessed" remotes, which we always pull and update from.
 162 All these count as sources above.
 163
 164 Update operation restrictions available, which restrict use of various
 165 sources above ?  What about implications for correctness of merge
 166 algorithm ?
 167
 168
 169 Concept of a "stack" ?
 170 Unnecessary - instead, deal with leaf branches
 171 Operations like "go up the stack", goes towards leaf.  Hopefully unique.
 172 "Down" the stack, uses a "conventional" linearisation
 173 Stack reordering op ?  auto adjust deps