chiark / gitweb /
update some docs for new metadata/theory
[topbloke.git] / DESIGN
diff --git a/DESIGN b/DESIGN
index a3e5c97..66252ce 100644 (file)
--- a/DESIGN
+++ b/DESIGN
@@ -1,132 +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 (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.
-          * 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 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
@@ -154,9 +25,7 @@ Patch removal:
 
 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
+ does not have .topbloke metadata
 
 Patch naming:
  needs to be globally unique
@@ -215,7 +84,7 @@ OK so here is a plan:
   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 
+  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.
@@ -224,14 +93,15 @@ OK so here is a plan:
 
 Strategies for each metadata file merge:
 
-       in base/tip     same patch's tip        dep -> base     base -> tip
+       in base/tip     same patch & branch     dep -> base     base -> tip
 
  msg            T      textual merge           rm from src     not in src
- deps           T      list 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
- patch-                BT      must be same            rm from src     must be same
- topgit-        T      must be same            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