From 97ed131fce2ba8de7454b00eef6a9adcd09e7fa0 Mon Sep 17 00:00:00 2001 From: Ian Jackson Date: Wed, 22 Feb 2012 21:43:58 +0000 Subject: [PATCH] Move old update algorith, which is very wrong according to new THEORY, into its own file, and deprecate it --- DESIGN | 118 ----------------------------------------------- UPDATE-ALGORITHM | 118 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 118 insertions(+), 118 deletions(-) create mode 100644 UPDATE-ALGORITHM diff --git a/DESIGN b/DESIGN index 4465057..135cb6d 100644 --- a/DESIGN +++ b/DESIGN @@ -1,121 +1,3 @@ -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 diff --git a/UPDATE-ALGORITHM b/UPDATE-ALGORITHM new file mode 100644 index 0000000..2fdb42c --- /dev/null +++ b/UPDATE-ALGORITHM @@ -0,0 +1,118 @@ +Basic update algorithm: + +XXX THIS IS ALMOST ENTIRELY WRONG - SEE "THEORY" XXX + + 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. -- 2.30.2