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