#!/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)
