X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke.git;a=blobdiff_plain;f=DESIGN;h=135cb6d342fd1635fcf647a7457a80b209916159;hp=b7c677d51e5bd7c7e943214739cbae8cd135bd46;hb=97ed131fce2ba8de7454b00eef6a9adcd09e7fa0;hpb=f188259a4c10646773fe0bbde14aadd419f341c9 diff --git a/DESIGN b/DESIGN index b7c677d..135cb6d 100644 --- a/DESIGN +++ b/DESIGN @@ -1,125 +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) - - Find the 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), find the most recent commit which unwantedly removed - the dep from the source's actual included deps ("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 patches - of a patch 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 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) - * 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 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 @@ -179,3 +57,148 @@ 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