X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke.git;a=blobdiff_plain;f=DESIGN;h=e4066e4a8143a5320557e5b2a3941e82af0c4ef0;hp=bac524ca7bbefad5bf8a38b2536209ca4fb55578;hb=e0dce6d313d0ee510f00238de8abda944f8d6155;hpb=94f53550123b9311a10d0e43ada446d4e3a9f144 diff --git a/DESIGN b/DESIGN index bac524c..e4066e4 100644 --- a/DESIGN +++ b/DESIGN @@ -1,151 +1,37 @@ -Basic update 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 +Patch removal: + + - removed patch must be removed from the deps of its ex-children, and replaced with the deps of the removed - branch + patch - - removed branch wants not to be in list of branches "git-branch" + - removed patch wants not to be in list of patches "tb-list" et al any more - branches in refs/top-branches ? yes - deleted branches do something to the base ? no + branches in refs/topbloke-tips ? yes + deleted patches do something to the base ? no - deleting empty branch: dependencies fine - deleting nonempty branch: if any dependencies found, their + deleting empty patch: dependencies fine + deleting nonempty patch: if any dependencies found, their updates break purpose of deleting? - - remove from views of active branches + - remove from views of active patches - prevent new commits - - remove from dependencies of active branches - only makes sense if no active branches depend on it. + - remove from dependencies of active patches + only makes sense if no active patches depend on it. undeleting - - just unmark the branch as deleted + - just unmark the patch as deleted + + +Foreign branches: + When merging from a foreign dependency, check that it + does not have .topbloke metadata -Branch naming: +Patch naming: needs to be globally unique so put email address in it -tg operations search for applicable branches -safe charset for branch names +tg operations search for applicable patches +safe charset for patch names . - / 0-9 a-z not permitted (git-check-ref-format(1)) spc ~ ^ : ? * [ \ @@ -153,7 +39,7 @@ not permitted (git-check-ref-format(1)) (apropos of shell) -When pulling, which remotes get to update which branches ? +When pulling, which remotes get to update which patches ? Complicated question! For now, have "blessed" remotes, which we always pull and update from. @@ -165,7 +51,152 @@ algorithm ? Concept of a "stack" ? -Unnecessary - instead, deal with leaf branches +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