-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.
- * It also stops at any point where we meet a commit which
- does have the dep in the actual included deps. We have
- to do this by hand.
- * 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 whether our list of dependencies has changed. If so
- we need to restart the whole base update.
-
- iv.
- 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.
-
-
Patch removal:
- removed patch must be removed from the deps of its
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
+ does not have .topbloke metadata
Patch naming:
needs to be globally unique
in base/tip same patch & branch dep -> base base -> tip
msg T textual merge rm from src not in src
+ patch BT must be same rm from src must be same
+ base T compute specially rm from src not in src
deps B list merge rm from src rm from src
deleted T std existence merge rm from src not in src
- patch- BT must be same rm from src must be same
- topgit- B std exist/text merge rm from src rm from src
[^+]*- ?? textual merge rm from src rm from src
+included BT list merge rm from non-tb src list merge
+ +ends BT compute specially compute specially
+*- ?? textual merge rm from non-tb src textual merge
*[^-] ?? die, aborting all ops, if found in any tb src or branch
-
-
-
-
-
-Unwanted removal search subgraphs:
-
- rm relevant removal
- inc
-
- rm impossible to undo removal, arrgh, terminates search
-inc inc..
-/ ??? \
-
- rm
-inc.. rm.. merge of a removal, search down the rm path
-/ [inc] \
-
- inc ??? call it an inclusion, terminate the search
- rm
-
- inc merge of an inclusion, terminates search
-inc.. rm..
-/ [rm] \
-
- inc ??? call it an inclusion, terminate search
-rm.. rm..
-/ ??? \
-
-
- rm inc inc rm irrelevant
- rm inc inc inc.. rm rm..
-
-
-
- OUR BASE SOURCE OUR IT TIP
- | | |
- | | |
- ADD DEP WH/ inc rm |
- NEEDS IT /| /\ |
- / | rm \ |
- / | ______________'/ \ |
- inc |' / \ | IT tip
- / inc REMOVAL rm \ | elsewhere
- / | / \ | | |
- / | inc \ | | |
- some IT | / | | | |
- | inc | | | |
- / | | | | |
- / inc | | | |
- | / | | | | |
- / / inc | | | |
- / | | `------------ | ----<-------- | -.| |
- / inc inc | | *2 |
- | |`- | ------------- | ----<--------.| | |
- | `---inc | 1* / |
- | | | | / |
- | RE-INCLUDE inc rm REMOVAL |' |
- inc \ | | | |
- | * REMOVAL rm | | |
- | | / | |
- |`-------------- | ----------. / | |
- | | inc ANC2 | |
- inc inc / | |
- |`.____________ | / | |
- | `inc ANC1 / | |
- | | /`--------<----------- | ---. |
- without inc / | \/
- | | / | /
- \ RE-INCLUDE inc / | /
- \ \ | / | /
- \ * REMOVAL rm / | /
- \ | / | /
- \ inc FIRST ADD DEP |/
- \ | \ *3
- \ | `------------<-------------.|
- \ | |
- \ without |
- \_____ | |
- `without |
- | |
- IT
-
-
- Merge 1* and 2*, diff against some relevant base branch commit
- or something, and apply to proposed. ???
-
-
-After we are done:
- source tip is included in our base
-
-Each time:
- * pick common ancestor
- * compute whether merge from common anc would unwantedly remove
- * if so we arrange that the common anc is a "rm" but our branch
- actually contains IT