chiark / gitweb /
update some docs for new metadata/theory
[topbloke.git] / DESIGN
diff --git a/DESIGN b/DESIGN
index f68272b..66252ce 100644 (file)
--- a/DESIGN
+++ b/DESIGN
-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 .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 branches.  (topgit,
-  which does not support dependency deletion, always has exactly the
-  desired branches actually included.)
-
-  Non-topbloke-controlled branches are never recorded in 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/included or .topbloke/flags; if it
- does, could produce a new commit which has .topbloke removed
- and merge from that
+ 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 ~ ^ : ? * [ \
@@ -162,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.
@@ -174,7 +51,57 @@ 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
+ 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
+ [^+]*-                ??      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