X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke.git;a=blobdiff_plain;f=DESIGN;h=97f06810fe75996cfdfb35d656934e591a376465;hp=f032250c295f473bf16685cdc8a56ee0d5e68263;hb=5ae399ddff45b6edb446ee5d9b779fb91985e439;hpb=8debeeef9d26615d056db30d41848928c30dd10e diff --git a/DESIGN b/DESIGN index f032250..97f0681 100644 --- a/DESIGN +++ b/DESIGN @@ -1,154 +1,343 @@ -#!/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) +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. + +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 & branch dep -> base base -> tip + + msg T textual merge 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 + +*- ?? 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