DESIGN

   1 #!/usr/bin/perl
   2 # usage: nupdate [<branch name>]
   3
   4 # Basic algorithm:
   5 #
   6 #  1. recurse to all of our direct dependencies and
   7 #     update their bases and branches
   8 #
   9 #  2. Update our base.
  10 #
  11 #     i. Compute our base's set of desired included branches:
  12 #          The set of desired included branches for a base
  13 #          is the union of the desired included branches for each
  14 #          branch named in the base's branch's direct deps, plus
  15 #          the name of every direct external dep.
  16 #          The set of desired included branches for a branch
  17 #          is the set of desired included branches for the branch's
  18 #          base plus the branch name itself.
  19 #
  20 #     ii. For each source in the best order, do the following merge:
  21 #         (Our base has sources:
  22 #             - the branch for each direct dep
  23 #             - the remote base)
  24 #
  25 #        Find the common ancestor.
  26 #
  27 #        Check for unwanted dependency removals.
  28 #        An unwanted dependency removal is
  29 #           A branch in the desired included branches
  30 #           Which exists in the common ancestor's actual included branches
  31 #           but which is missing in the source's actual included branches
  32 #           (NB that this definition excludes dependency removals
  33 #           which have already occurred on our base; these will be
  34 #           reverted later.)
  35 #        For each unwanted dependency removal (ie for each such
  36 #        branch), find the most recent commit which unwantedly removed
  37 #        the dep from the source's actual included branches ("relevant
  38 #        unwanted removal commit").  (Abort if any such commit is a
  39 #        merge.)  Select the earliest relevant unwanted removal commit
  40 #        (from the set of relevant unwanted removal commits
  41 #        corresponding to the unwanted dependency removals).
  42 #        Merge from the ancestor of the relevant unwanted removal commit.
  43 #        Merge from the relevant unwanted removal commit using -s ours.
  44
  45 #        (The purpose of this, and the result, is that the unwanted
  46 #        dependency removal has gone away.  Doing things in this order
  47 #        tries to keep the unwanted dependency removal's reversions as
  48 #        close as possible to their originating points.  The
  49 #        recursion, which processes dependencies before their clients,
  50 #        tries to keep the reversion churn localised: client branches
  51 #        of a branch affected by an unwanted removal will benefit from
  52 #        that client's resolution of the situation.)
  53
  54 #        Now continue to the next unwanted dependency removal.
  55 #
  56 #        If there are no (more) unwanted dependency removals, merge
  57 #        from the source.
  58 #
  59 #     iii.
  60 #        Check for missing or unwanted dependency inclusions.  Compare
  61 #        our base's desired included branches with our base's actual
  62 #        included branches.  In exceptional conditions, they will not
  63 #        be identical.  This can happen, for example, because a
  64 #        dependency removal was incorporated into our base branch but
  65 #        the removed branch was introduced as an explicit dependency.
  66 #        This will also happen if we remove a dependency ourselves.
  67 #
  68 #        Do the unwanted inclusions first, and then the missing ones.
  69 #        (This is because that the missing ones cannot depend on the
  70 #        unwanted ones, as otherwise the unwanted ones would be in the
  71 #        desired inclusions.  So removing the unwanted ones first
  72 #        reduces the chances of conflicts.)
  73 #
  74 #        So, repeatedly:
  75 #          * Do the comparison between desired and actual included
  76 #          * Pick a missing inclusion, or failing that an unwanted one
  77 #            (call this the "relevant" branch)
  78 #          * Depth first search all of the dependencies of the
  79 #            relevant branch; if any of these is also a missing
  80 #            (resp. unwanted) inclusion, start again processing it
  81 #            instead.
  82 #          * Attempt to apply the appropriate diff to add (resp. remove)
  83 #            the contents of the relevant patch (adjusted appropriately
  84 #            for metadata, XXX??? particularly the actual inclusion list)
  85 #          * Go round again looking for another discrepancy.
  86 #
  87 #  3. Update our branch.
  88 #        Our branch has sources:
  89 #           - our base
  90 #           - the remote for our branch
  91 #        For each source in the best order, do the merge.
  92 #
  93 #        Double-check the actual dependency inclusions.  In
  94 #        particular, if we just upgraded to actual dependency tracking
  95 #        we may need to explicitly add our branch name to the actual
  96 #        dependency inclusion list.
  97 #
  98 # The "best order" for merges is in order of recency of common
  99 # ancestor, most recent first, and if that does not distinguish,
 100 # merging from local branches first.
 101 #
 102 # "Recency" refers to the order from git-rev-list --date-order.
 103 #
 104 # Actual included branches:
 105 #
 106 #   This is tracked explicitly in .topgit/included, one branch per
 107 #   line.  For compatibility with older versions, every time we think
 108 #   about a base, branch or source above, we check whether
 109 #   .topgit/included is present.
 110 #
 111 #   If it isn't then we calculate a child commit which has a
 112 #   .topgit/included.  In the case of a remote branch or base, we
 113 #   substitute this child commit for the relevant remote ref but do
 114 #   not record it in the remote ref; in the case of a local branch or
 115 #   base, we advance the local branch or base accordingly.
 116 #
 117 #   When .topgit/included is calculated in this way, it always gets
 118 #   the list of desired included branches.  (Older versions of topgit,
 119 #   which do not support dependency deletion, always have exactly the
 120 #   desired branches actually included.)
 121
 122
 123 # Branch removal:
 124 #
 125 #  - removed branch must be removed from the deps of its
 126 #    ex-children, and replaced with the deps of the removed
 127 #    branch
 128 #
 129 #  - removed branch wants not to be in list of branches "git-branch"
 130 #    et al any more
 131 #       branches in refs/top-branches ?
 132 #       deleted branches do something to the base ?
 133 #
 134 #  deleting empty branch: dependencies fine
 135 #  deleting nonempty branch: if any dependencies found, their
 136 #     updates break
 137 #
 138 #  purpose of deleting?
 139 #    - remove from views of active branches
 140 #    - prevent new commits
 141 #    - remove from dependencies of active branches
 142 #        only makes sense if no active branches depend on it.
 143
 144 # Branch naming:
 145 #  needs to be globally unique
 146 #  so put email address in it
 147 #  also "tree" or "context" name, found automatically
 148 # tg operations search for applicable branches
 149 # safe charset for branch names
 150 #   . - / 0-9 a-z
 151 # not permitted (git-check-ref-format(1))
 152 #  spc ~ ^ : ? * [ \
 153 #  @{ .lock.
 154 #  (apropos of shell)