chiark / gitweb /
update some docs for new metadata/theory
[topbloke.git] / DESIGN
diff --git a/DESIGN b/DESIGN
index f032250..66252ce 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)
+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
+
+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
+ patch         BT      must be same            rm from src     must be same
+ base           T      compute specially       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
+ [^+]*-                ??      textual merge           rm from src     rm from src
+ +included     BT      list merge        rm from non-tb src    list merge
+ +ends         BT      compute specially       compute specially
+ +*-           ??      textual merge     rm from non-tb src    textual merge
+ *[^-]         ??      die, aborting all ops, if found in any tb src or branch