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