chiark / gitweb /
remove old "calculate included patches in topgit branches" idea; we are going to...
[topbloke.git] / DESIGN
diff --git a/DESIGN b/DESIGN
index f032250..4465057 100644 (file)
--- a/DESIGN
+++ b/DESIGN
-#!/usr/bin/perl
-# usage: nupdate [<branch name>]
-
-# Basic algorithm:
-#
-#  1. recurse to all of our direct dependencies and
-#     update their bases and branches
-#
-#  2. Update our base.
-#
-#     i. Compute our base's set of desired included branches:
-#          The set of desired included branches for a base
-#          is the union of the desired included branches 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 branches for a branch
-#          is the set of desired included branches 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)
-#
-#        Find the common ancestor.
-#
-#        Check for unwanted dependency removals.  
-#        An unwanted dependency removal is
-#           A branch in the desired included branches
-#           Which exists in the common ancestor's actual included branches
-#           but which is missing in the source's actual included branches
-#           (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), find the most recent commit which unwantedly removed
-#        the dep from the source's actual included branches ("relevant
-#        unwanted removal commit").  (Abort if any such commit is a
-#        merge.)  Select the earliest relevant unwanted removal commit
-#        (from the set of relevant unwanted removal commits
-#        corresponding to the unwanted dependency removals).
-#        Merge from the ancestor of the relevant unwanted removal commit.
-#        Merge from the relevant unwanted removal commit using -s ours.
-
-#        (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 branches
-#        of a branch affected by an unwanted removal will benefit from
-#        that client's resolution of the situation.)
-
-#        Now continue to the next unwanted dependency removal.
-#
-#        If there are no (more) unwanted dependency removals, merge
-#        from the source.
-#
-#     iii.
-#        Check for missing or unwanted dependency inclusions.  Compare
-#        our base's desired included branches with our base's actual
-#        included branches.  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)
-#          * Go round again looking for another discrepancy.
-#
-#  3. Update our branch.
-#        Our branch has sources:
-#           - our base
-#           - the remote for our branch
-#        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.
-#
-# Actual included branches:
-#
-#   This is tracked explicitly in .topgit/included, one branch per
-#   line.  For compatibility with older versions, every time we think
-#   about a base, branch or source above, we check whether
-#   .topgit/included is present.
-#
-#   If it isn't then we calculate a child commit which has a
-#   .topgit/included.  In the case of a remote branch or base, we
-#   substitute this child commit for the relevant remote ref but do
-#   not record it in the remote ref; in the case of a local branch or
-#   base, we advance the local branch or base accordingly.
-# 
-#   When .topgit/included is calculated in this way, it always gets
-#   the list of desired included branches.  (Older versions of topgit,
-#   which do not support dependency deletion, always have exactly the
-#   desired branches actually included.)
-
-
-# Branch removal:
-#
-#  - removed branch must be removed from the deps of its
-#    ex-children, and replaced with the deps of the removed
-#    branch
-#
-#  - removed branch wants not to be in list of branches "git-branch"
-#    et al any more
-#       branches in refs/top-branches ?
-#       deleted branches do something to the base ?
-#
-#  deleting empty branch: dependencies fine
-#  deleting nonempty branch: if any dependencies found, their
-#     updates break
-#
-#  purpose of deleting?
-#    - remove from views of active branches
-#    - prevent new commits
-#    - remove from dependencies of active branches
-#        only makes sense if no active branches depend on it.
-
-# Branch naming:
-#  needs to be globally unique
-#  so put email address in it
-#  also "tree" or "context" name, found automatically
-# tg operations search for applicable branches
-# safe charset for branch names
-#   . - / 0-9 a-z
-# not permitted (git-check-ref-format(1))
-#  spc ~ ^ : ? * [ \
-#  @{ .lock.
-#  (apropos of shell)
+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