-#!/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 tips
+
+ 2. Update our base.
+
+ i. Compute our base's set of desired included deps:
+ The set of desired included deps for a base
+ is the union of the desired included deps 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 deps for a branch
+ is the set of desired included deps 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
+ - the topgit base, if this is a topgit import)
+
+ Find the (latest) common ancestor.
+
+ Check for unwanted dependency removals.
+ An unwanted dependency removal is
+ A branch in the desired included deps
+ Which exists in the common ancestor's actual included deps
+ but which is missing in the source's actual included deps
+ (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), search as follows:
+ * An "unwanted removal commit" is a non-merge commit in the
+ history of the source, which removes the dep from the
+ actual included deps.
+ * But the search stops at any point where we would have to
+ traverse a commit where .topbloke/deps is empty (which
+ stops us looking into the hitory of non-topbloke-controlled
+ branches). This can be done with git-rev-list
+ --remove-empty.
+ * The the relevant unwanted removal commit for that dep is
+ the most recent unwanted removal commit, as defined.
+ Select the unwantedly removed dep whose relevant unwanted
+ removal commit is the earliest. Merge from the ancestor of
+ that relevant unwanted removal commit. Merge from the relevant
+ unwanted removal commit using -s ours.
+
+ Now continue to the next unwanted dependency removal.
+
+ (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 patches
+ of a patch affected by an unwanted removal will benefit from
+ that client's resolution of the situation.)
+
+ 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 deps with our base's actual
+ included deps. 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)
+ XXX if we want to add a dep we need to update the dep first
+ * Go round again looking for another discrepancy.
+
+ 3. Update our branch.
+ Our branch has sources:
+ - our base
+ - the remote for our branch
+ - the topgit branch, if this is a topgit import
+ 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 deps:
+
+ This is tracked explicitly in .topbloke/included, one branch per
+ line. For compatibility with older versions, every time we think
+ about a base, branch or source above, we check whether
+ .topbloke/included is present.
+
+ If it isn't then we calculate a child commit which has a
+ .topbloke/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 .topbloke/included is calculated in this way, it always gets
+ the list of desired included deps. (topgit,
+ which does not support dependency deletion, always has exactly the
+ desired deps actually included.)
+
+ Foreign branches cannot be removed from included and cannot
+ therefore be removed from dependency lists.
+
+
+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; LATER if it
+ does, could produce a new commit which has .topbloke removed
+ and merge from that
+
+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's tip dep -> base base -> tip
+
+ msg T textual merge rm from src not in src
+ deps T list merge rm from src not in src
+ deleted T std existence merge rm from src not in src
+ patch- BT must be same rm from src must be same
+ topgit- T must be same 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
+ +*- ?? textual merge rm from non-tb src textual merge
+ *[^-] ?? die, aborting all ops, if found in any tb src or branch
~ian / topbloke.git / blobdiff