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 .topgit/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   .topgit/included is present.
 107
 108   If it isn't then we calculate a child commit which has a
 109   .topgit/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 .topgit/included is calculated in this way, it always gets
 115   the list of desired included branches.  (Older versions of topgit,
 116   which do not support dependency deletion, always have exactly the
 117   desired branches actually included.)
 118
 119
 120 Branch removal:
 121
 122  - removed branch must be removed from the deps of its
 123    ex-children, and replaced with the deps of the removed
 124    branch
 125
 126  - removed branch wants not to be in list of branches "git-branch"
 127    et al any more
 128       branches in refs/top-branches ?  yes
 129       deleted branches do something to the base ?  no
 130
 131  deleting empty branch: dependencies fine
 132  deleting nonempty branch: if any dependencies found, their
 133     updates break
 134
 135  purpose of deleting?
 136    - remove from views of active branches
 137    - prevent new commits
 138    - remove from dependencies of active branches
 139        only makes sense if no active branches depend on it.
 140
 141  undeleting
 142    - just unmark the branch as deleted
 143
 144 Branch naming:
 145  needs to be globally unique
 146  so put email address in it
 147 tg operations search for applicable branches
 148 safe charset for branch names
 149   . - / 0-9 a-z
 150 not permitted (git-check-ref-format(1))
 151  spc ~ ^ : ? * [ \
 152  @{ .lock.
 153  (apropos of shell)
 154
 155
 156 When pulling, which remotes get to update which branches ?
 157 Complicated question!
 158
 159 For now, have "blessed" remotes, which we always pull and update from.
 160 All these count as sources above.
 161
 162 Update operation restrictions available, which restrict use of various
 163 sources above ?  What about implications for correctness of merge
 164 algorithm ?
 165
 166
 167 Concept of a "stack" ?
 168 Unnecessary - instead, deal with leaf branches
 169 Operations like "go up the stack", goes towards leaf.  Hopefully unique.
 170 "Down" the stack, uses a "conventional" linearisation
 171 Stack reordering op ?  auto adjust deps