[topbloke.git] / DESIGN

Basic update algorithm:

 1. recurse to all of our direct dependencies and
    update their bases and tips

 2. Update our base.

    i. Compute our base's set of desired included deps:
         The set of desired included deps for a base
         is the union of the desired included deps for each
         branch named in the base's branch's direct deps, plus
         the name of every direct external dep.
         The set of desired included deps for a branch
         is the set of desired included deps for the branch's
         base plus the branch name itself.

    ii. For each source in the best order, do the following merge:
        (Our base has sources:
            - the branch for each direct dep
            - the remote base
            - the topgit base, if this is a topgit import)

       Find the (latest) common ancestor.

       Check for unwanted dependency removals.
       An unwanted dependency removal is
          A branch in the desired included deps
          Which exists in the common ancestor's actual included deps
          but which is missing in the source's actual included deps
          (NB that this definition excludes dependency removals
          which have already occurred on our base; these will be
          reverted later.)
       For each unwanted dependency removal (ie for each such
       branch), search as follows:
          * An "unwanted removal commit" is a non-merge commit in the
            history of the source, which removes the dep from the
            actual included deps.
          * But the search stops at any point where we would have to
            traverse a commit where .topbloke/deps is empty (which
            stops us looking into the hitory of non-topbloke-controlled
            branches).  This can be done with git-rev-list
            --remove-empty.
          * It also stops at any point where we meet a commit which
            does have the dep in the actual included deps.  We have
            to do this by hand.
          * The the relevant unwanted removal commit for that dep is
            the most recent unwanted removal commit, as defined.
       Select the unwantedly removed dep whose relevant unwanted
       removal commit is the earliest.  Merge from the ancestor of
       that relevant unwanted removal commit.  Merge from the relevant
       unwanted removal commit using -s ours.

       Now continue to the next unwanted dependency removal.

       (The purpose of this, and the result, is that the unwanted
       dependency removal has gone away.  Doing things in this order
       tries to keep the unwanted dependency removal's reversions as
       close as possible to their originating points.  The
       recursion, which processes dependencies before their clients,
       tries to keep the reversion churn localised: client patches
       of a patch affected by an unwanted removal will benefit from
       that client's resolution of the situation.)

       If there are no (more) unwanted dependency removals, merge
       from the source.

    iii.
       Check whether our list of dependencies has changed.  If so
       we need to restart the whole base update.

    iv.
       Check for missing or unwanted dependency inclusions.  Compare
       our base's desired included deps with our base's actual
       included deps.  In exceptional conditions, they will not
       be identical.  This can happen, for example, because a
       dependency removal was incorporated into our base branch but
       the removed branch was introduced as an explicit dependency.
       This will also happen if we remove a dependency ourselves.

       Do the unwanted inclusions first, and then the missing ones.
       (This is because that the missing ones cannot depend on the
       unwanted ones, as otherwise the unwanted ones would be in the
       desired inclusions.  So removing the unwanted ones first
       reduces the chances of conflicts.)

       So, repeatedly:
         * Do the comparison between desired and actual included
         * Pick a missing inclusion, or failing that an unwanted one
           (call this the "relevant" branch)
         * Depth first search all of the dependencies of the
           relevant branch; if any of these is also a missing
           (resp. unwanted) inclusion, start again processing it
           instead.
         * Attempt to apply the appropriate diff to add (resp. remove)
           the contents of the relevant patch (adjusted appropriately
           for metadata, XXX??? particularly the actual inclusion list)
           XXX if we want to add a dep we need to update the dep first
         * Go round again looking for another discrepancy.

 3. Update our branch.
       Our branch has sources:
          - our base
          - the remote for our branch
          - the topgit branch, if this is a topgit import
       For each source in the best order, do the merge.

       Double-check the actual dependency inclusions.  In
       particular, if we just upgraded to actual dependency tracking
       we may need to explicitly add our branch name to the actual
       dependency inclusion list.

The "best order" for merges is in order of recency of common
ancestor, most recent first, and if that does not distinguish,
merging from local branches first.

"Recency" refers to the order from git-rev-list --date-order.


Patch removal:

 - removed patch must be removed from the deps of its
   ex-children, and replaced with the deps of the removed
   patch

 - removed patch wants not to be in list of patches "tb-list"
   et al any more
      branches in refs/topbloke-tips ?  yes
      deleted patches do something to the base ?  no

 deleting empty patch: dependencies fine
 deleting nonempty patch: if any dependencies found, their
    updates break

 purpose of deleting?
   - remove from views of active patches
   - prevent new commits
   - remove from dependencies of active patches
       only makes sense if no active patches depend on it.

 undeleting
   - just unmark the patch as deleted


Foreign branches:
 When merging from a foreign dependency, check that it
 does not have .topbloke metadata; LATER if it
 does, could produce a new commit which has .topbloke removed
 and merge from that

Patch naming:
 needs to be globally unique
 so put email address in it
tg operations search for applicable patches
safe charset for patch names
  . - / 0-9 a-z
not permitted (git-check-ref-format(1))
 spc ~ ^ : ? * [ \
 @{ .lock.
 (apropos of shell)


When pulling, which remotes get to update which patches ?
Complicated question!

For now, have "blessed" remotes, which we always pull and update from.
All these count as sources above.

Update operation restrictions available, which restrict use of various
sources above ?  What about implications for correctness of merge
algorithm ?


Concept of a "stack" ?
Unnecessary - instead, deal with leaf patches
Operations like "go up the stack", goes towards leaf.  Hopefully unique.
"Down" the stack, uses a "conventional" linearisation
Stack reordering op ?  auto adjust deps


When merging, we need to DTRT with our metadata.
Do this by running write-tree/read-tree etc. ourselves ?
For a source we're merging from, we make a version where the
metadata we shouldn't be merging is removed ?
Or something.
Have discovered that specifying a custom merge driver for a file does
not have any effect if the three-way-merge looks trivial based
on looking at the file contents - at least, if you use git-merge.

Only thing which knows how to do all the gitattributes stuff and
conflict markers and what have you is git-merge.  (git-merge-tree does
too but the output format is unsuitable.)  "git-merge-index
... git-merge-one-file" does not honour the merge drivers and is,
contrary to what the git docs seem to suggest but don't actually
state, not actualy used by git-merge.

OK so here is a plan:
  Use git-merge --no-commit
  Perhaps on a HEAD, and/or against a tree, which have been massaged
   to make the metadata suitable as input.
  Filtering out the "merge was successful but we aren't committing"
  message.  Use a single pipe for stdout/stderr to get interleaving
  right; the message from git-merge is not i18n'd.
  Afterwards we:
  Check for merge success in the index and compare to exit status
  from git-merge (which is 1 if the merge failed).
  Adjust the metadata.
  Print appropriate big fat warnings if we have merge conflicts in our
  metadata.
  Commit, adjusting the parents of the new commit to the original
  parents if we made the merge with special massaged parents.
  We may still need to have custom merge drivers for metadata.


Strategies for each metadata file merge:

        in base/tip     same patch & branch     dep -> base     base -> tip

 msg             T      textual merge           rm from src     not in src
 deps           B       list merge              rm from src     rm from src
 deleted         T      std existence merge     rm from src     not in src
 patch-         BT      must be same            rm from src     must be same
 topgit-        B       std exist/text merge    rm from src     rm from src
 [^+]*-         ??      textual merge           rm from src     rm from src
 +included      BT      list merge        rm from non-tb src    list merge
 +*-            ??      textual merge     rm from non-tb src    textual merge
 *[^-]          ??      die, aborting all ops, if found in any tb src or branch





Unwanted removal search subgraphs:

  rm            relevant removal
  inc

   rm           impossible to undo removal, arrgh, terminates search
inc  inc..
/  ???   \

    rm
inc..  rm..     merge of a removal, search down the rm path
/  [inc]  \

  inc           ??? call it an inclusion, terminate the search
  rm

   inc          merge of an inclusion, terminates search
inc..  rm..
/  [rm]  \

   inc          ??? call it an inclusion, terminate search
rm..  rm..
/  ???    \


  rm    inc       inc          rm       irrelevant
  rm    inc     inc inc..    rm rm..



          OUR BASE              SOURCE                 OUR IT TIP
                |                  |                       |
                |                  |                       |
   ADD DEP WH/ inc                 rm                      |
    NEEDS IT   /|                  /\                      |
              / |                rm  \                     |
             /  | ______________'/    \                    |
          inc   |'              /      \                   |     IT tip
           /   inc     REMOVAL rm       \                  |    elsewhere
          /     |             /          \                 |   |   |
         /      |           inc           \                |   |   |
     some IT    |           /              |               |   |   |
                |         inc              |               |   |   |
               /           |               |               |   |   |
              /          inc               |               |   |   |
             |           / |               |               |   |   |
            /           /  inc             |               |   |   |
           /           |   | `------------ | ----<-------- | -.|   |
          /           inc  inc             |               |   *2  |
          |            |`- | ------------- | ----<--------.|   |   |
          |            `---inc             |              1*  /    |
          |                |               |               | /     |
          |     RE-INCLUDE inc             rm REMOVAL      |'      |
        inc     \          |               |               |       |
          |      * REMOVAL rm              |               |       |
          |                |              /                |       |
          |`-------------- | ----------. /                 |       |
          |                |           inc ANC2            |       |
         inc               inc         /                   |       |
          |`.____________  |          /                    |       |
          |              `inc ANC1   /                     |       |
          |                |        /`--------<----------- | ---.  |
        without            inc     /                       |     \/
          |                |      /                        |     /
           \    RE-INCLUDE inc   /                         |    /
            \   \          |    /                          |   /
             \   * REMOVAL rm  /                           |  /
              \            |  /                            | /
               \           inc FIRST ADD DEP               |/
                \          |  \                            *3
                 \         |   `------------<-------------.|
                  \        |                               |
                   \       without                         |
                    \_____ |                               |
                          `without                         |
                           |                               |
                                                          IT


  Merge 1* and 2*, diff against some relevant base branch commit
  or something, and apply to proposed. ???


After we are done:
  source tip is included in our base

Each time:
  * pick common ancestor
  * compute whether merge from common anc would unwantedly remove
  * if so we arrange that the common anc is a "rm" but our branch
    actually contains IT