chiark / gitweb /
remove comment markers now it's a text file
authorIan Jackson <ijackson@chiark.greenend.org.uk>
Wed, 11 Jan 2012 21:44:01 +0000 (21:44 +0000)
committerIan Jackson <ijackson@chiark.greenend.org.uk>
Wed, 11 Jan 2012 21:44:01 +0000 (21:44 +0000)
DESIGN

diff --git a/DESIGN b/DESIGN
index f032250..b1c06eb 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 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)