DESIGN

   1 Basic update algorithm:
   2
   3  1. recurse to all of our direct dependencies and
   4     update their bases and tips
   5
   6  2. Update our base.
   7
   8     i. Compute our base's set of desired included deps:
   9          The set of desired included deps for a base
  10          is the union of the desired included deps 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 deps for a branch
  14          is the set of desired included deps 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             - the topgit base, if this is a topgit import)
  22
  23        Find the (latest) common ancestor.
  24
  25        Check for unwanted dependency removals.
  26        An unwanted dependency removal is
  27           A branch in the desired included deps
  28           Which exists in the common ancestor's actual included deps
  29           but which is missing in the source's actual included deps
  30           (NB that this definition excludes dependency removals
  31           which have already occurred on our base; these will be
  32           reverted later.)
  33        For each unwanted dependency removal (ie for each such
  34        branch), search as follows:
  35           * An "unwanted removal commit" is a non-merge commit in the
  36             history of the source, which removes the dep from the
  37             actual included deps.
  38           * But the search stops at any point where we would have to
  39             traverse a commit where .topbloke/deps is empty (which
  40             stops us looking into the hitory of non-topbloke-controlled
  41             branches).  This can be done with git-rev-list
  42             --remove-empty.
  43           * The the relevant unwanted removal commit for that dep is
  44             the most recent unwanted removal commit, as defined.
  45        Select the unwantedly removed dep whose relevant unwanted
  46        removal commit is the earliest.  Merge from the ancestor of
  47        that relevant unwanted removal commit.  Merge from the relevant
  48        unwanted removal commit using -s ours.
  49
  50        Now continue to the next unwanted dependency removal.
  51
  52        (The purpose of this, and the result, is that the unwanted
  53        dependency removal has gone away.  Doing things in this order
  54        tries to keep the unwanted dependency removal's reversions as
  55        close as possible to their originating points.  The
  56        recursion, which processes dependencies before their clients,
  57        tries to keep the reversion churn localised: client patches
  58        of a patch affected by an unwanted removal will benefit from
  59        that client's resolution of the situation.)
  60
  61        If there are no (more) unwanted dependency removals, merge
  62        from the source.
  63
  64     iii.
  65        Check whether our list of dependencies has changed.  If so
  66        we need to restart the whole base update.
  67
  68     iv.
  69        Check for missing or unwanted dependency inclusions.  Compare
  70        our base's desired included deps with our base's actual
  71        included deps.  In exceptional conditions, they will not
  72        be identical.  This can happen, for example, because a
  73        dependency removal was incorporated into our base branch but
  74        the removed branch was introduced as an explicit dependency.
  75        This will also happen if we remove a dependency ourselves.
  76
  77        Do the unwanted inclusions first, and then the missing ones.
  78        (This is because that the missing ones cannot depend on the
  79        unwanted ones, as otherwise the unwanted ones would be in the
  80        desired inclusions.  So removing the unwanted ones first
  81        reduces the chances of conflicts.)
  82
  83        So, repeatedly:
  84          * Do the comparison between desired and actual included
  85          * Pick a missing inclusion, or failing that an unwanted one
  86            (call this the "relevant" branch)
  87          * Depth first search all of the dependencies of the
  88            relevant branch; if any of these is also a missing
  89            (resp. unwanted) inclusion, start again processing it
  90            instead.
  91          * Attempt to apply the appropriate diff to add (resp. remove)
  92            the contents of the relevant patch (adjusted appropriately
  93            for metadata, XXX??? particularly the actual inclusion list)
  94            XXX if we want to add a dep we need to update the dep first
  95          * Go round again looking for another discrepancy.
  96
  97  3. Update our branch.
  98        Our branch has sources:
  99           - our base
 100           - the remote for our branch
 101           - the topgit branch, if this is a topgit import
 102        For each source in the best order, do the merge.
 103
 104        Double-check the actual dependency inclusions.  In
 105        particular, if we just upgraded to actual dependency tracking
 106        we may need to explicitly add our branch name to the actual
 107        dependency inclusion list.
 108
 109 The "best order" for merges is in order of recency of common
 110 ancestor, most recent first, and if that does not distinguish,
 111 merging from local branches first.
 112
 113 "Recency" refers to the order from git-rev-list --date-order.
 114
 115 Actual included deps:
 116
 117   This is tracked explicitly in .topbloke/included, one branch per
 118   line.  For compatibility with older versions, every time we think
 119   about a base, branch or source above, we check whether
 120   .topbloke/included is present.
 121
 122   If it isn't then we calculate a child commit which has a
 123   .topbloke/included.  In the case of a remote branch or base, we
 124   substitute this child commit for the relevant remote ref but do
 125   not record it in the remote ref; in the case of a local branch or
 126   base, we advance the local branch or base accordingly.
 127
 128   When .topbloke/included is calculated in this way, it always gets
 129   the list of desired included deps.  (topgit,
 130   which does not support dependency deletion, always has exactly the
 131   desired deps actually included.)
 132
 133   Foreign branches cannot be removed from included and cannot
 134   therefore be removed from dependency lists.
 135
 136
 137 Patch removal:
 138
 139  - removed patch must be removed from the deps of its
 140    ex-children, and replaced with the deps of the removed
 141    patch
 142
 143  - removed patch wants not to be in list of patches "tb-list"
 144    et al any more
 145       branches in refs/topbloke-tips ?  yes
 146       deleted patches do something to the base ?  no
 147
 148  deleting empty patch: dependencies fine
 149  deleting nonempty patch: if any dependencies found, their
 150     updates break
 151
 152  purpose of deleting?
 153    - remove from views of active patches
 154    - prevent new commits
 155    - remove from dependencies of active patches
 156        only makes sense if no active patches depend on it.
 157
 158  undeleting
 159    - just unmark the patch as deleted
 160
 161
 162 Foreign branches:
 163  When merging from a foreign dependency, check that it
 164  does not have .topbloke metadata; LATER if it
 165  does, could produce a new commit which has .topbloke removed
 166  and merge from that
 167
 168 Patch naming:
 169  needs to be globally unique
 170  so put email address in it
 171 tg operations search for applicable patches
 172 safe charset for patch names
 173   . - / 0-9 a-z
 174 not permitted (git-check-ref-format(1))
 175  spc ~ ^ : ? * [ \
 176  @{ .lock.
 177  (apropos of shell)
 178
 179
 180 When pulling, which remotes get to update which patches ?
 181 Complicated question!
 182
 183 For now, have "blessed" remotes, which we always pull and update from.
 184 All these count as sources above.
 185
 186 Update operation restrictions available, which restrict use of various
 187 sources above ?  What about implications for correctness of merge
 188 algorithm ?
 189
 190
 191 Concept of a "stack" ?
 192 Unnecessary - instead, deal with leaf patches
 193 Operations like "go up the stack", goes towards leaf.  Hopefully unique.
 194 "Down" the stack, uses a "conventional" linearisation
 195 Stack reordering op ?  auto adjust deps
 196
 197
 198 When merging, we need to DTRT with our metadata.
 199 Do this by running write-tree/read-tree etc. ourselves ?
 200 For a source we're merging from, we make a version where the
 201 metadata we shouldn't be merging is removed ?
 202 Or something.
 203 Have discovered that specifying a custom merge driver for a file does
 204 not have any effect if the three-way-merge looks trivial based
 205 on looking at the file contents - at least, if you use git-merge.
 206
 207 Only thing which knows how to do all the gitattributes stuff and
 208 conflict markers and what have you is git-merge.  (git-merge-tree does
 209 too but the output format is unsuitable.)  "git-merge-index
 210 ... git-merge-one-file" does not honour the merge drivers and is,
 211 contrary to what the git docs seem to suggest but don't actually
 212 state, not actualy used by git-merge.
 213
 214 OK so here is a plan:
 215   Use git-merge --no-commit
 216   Perhaps on a HEAD, and/or against a tree, which have been massaged
 217    to make the metadata suitable as input.
 218   Filtering out the "merge was successful but we aren't committing"
 219   message.  Use a single pipe for stdout/stderr to get interleaving
 220   right; the message from git-merge is not i18n'd.
 221   Afterwards we:
 222   Check for merge success in the index and compare to exit status
 223   from git-merge (which is 1 if the merge failed).
 224   Adjust the metadata.
 225   Print appropriate big fat warnings if we have merge conflicts in our
 226   metadata.
 227   Commit, adjusting the parents of the new commit to the original
 228   parents if we made the merge with special massaged parents.
 229   We may still need to have custom merge drivers for metadata.
 230
 231
 232 Strategies for each metadata file merge:
 233
 234         in base/tip     same patch's tip        dep -> base     base -> tip
 235
 236  msg             T      textual merge           rm from src     not in src
 237  deps            T      list merge              rm from src     not in src
 238  deleted         T      std existence merge     rm from src     not in src
 239  patch-         BT      must be same            rm from src     must be same
 240  topgit-         T      must be same            rm from src     not in src
 241  [^+]*-         ??      textual merge           rm from src     rm from src
 242  +included      BT      list merge        rm from non-tb src    list merge
 243  +*-            ??      textual merge     rm from non-tb src    textual merge
 244  *[^-]          ??      die, aborting all ops, if found in any tb src or branch