#!/usr/bin/perl # usage: nupdate [] # 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)