chiark / gitweb /
update some docs for new metadata/theory
[topbloke.git] / DESIGN
diff --git a/DESIGN b/DESIGN
index 4465057..66252ce 100644 (file)
--- 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
@@ -143,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
@@ -216,107 +96,12 @@ 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
- 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
+ +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
-
-
-
-
-
-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