# HG changeset patch
# User Anton Shestakov <av6@dwimlabs.net>
# Date 1608635039 -28800
# Node ID 668817e8c00728e197a9b1c650ddb6b0e6c0c6b1
# Parent  fe9f9e528a42ee7c7f74efdd0cc9c3277071a103
rewind: walk obsmarkers and add more targets to rewind to

We're trying to save users from accidentally losing any content changes if they
try to rewind to e.g. only one component of a fold. In such case we're also
adding the rest of the components.

diff -r fe9f9e528a42 -r 668817e8c007 hgext3rd/evolve/rewind.py
--- a/hgext3rd/evolve/rewind.py	Thu Feb 18 07:39:38 2021 +0800
+++ b/hgext3rd/evolve/rewind.py	Tue Dec 22 19:03:59 2020 +0800
@@ -20,6 +20,7 @@
 from . import (
     compat,
     exthelper,
+    obshistory,
     rewriteutil,
 )
 
@@ -93,6 +94,9 @@
 
         targets = _select_rewind_targets(repo, opts)
 
+        extratargets = _walk_obsmarkers(ui, unfi, targets)
+        targets.extend(extratargets)
+
         for rev in targets:
             ctx = unfi[rev]
             ssets = obsutil.successorssets(repo, ctx.node(), cache=sscache)
@@ -188,6 +192,94 @@
     if update_target is not None and not opts.get('keep'):
         ui.status(_(b'working directory is now at %s\n') % repo[b'.'])
 
+def _walk_successors(ui, unfi, targetset):
+    """follow successors of targets and find the latest successors
+
+    We also keep track of "source": when we reach a successor by following the
+    obsmarker-graph starting from a certain target, we add `successor: target`
+    pair to `source`. But we don't care about having more than one `target`
+    (i.e. predecessor) for each `successor`, because `source` is used later on
+    for finding "new" successors that we didn't find in this function.
+    """
+    source = {}
+    latest = set()
+    for targetnode in targetset:
+        # following successors for each target node separately
+        remaining = set([targetnode])
+        while remaining:
+            current = remaining.pop()
+            markers = unfi.obsstore.successors.get(current, ())
+            for marker in markers:
+                for successor in marker[1]:
+                    if successor in source:
+                        # We have already reached this successor while
+                        # processing this or any other targetnode. This means
+                        # not every target node will get their latest successor
+                        # found if e.g. there's a fold (and that is fine).
+                        # (Also basic cycle protection.)
+                        continue
+                    source[successor] = current
+                    remaining.add(successor)
+            if not markers:
+                latest.add(current)
+
+    return latest, source
+
+def _walk_predecessors(ui, unfi, targetset, latest, source):
+    """follow predecessors of targets, validate and suggest extra targets
+
+    Skip predecessors that are only reachable by following obsmarkers with
+    "identical" flag, because these markers are for internal use and actual
+    users don't want to revive such predecessors.
+
+    Note: picking the first reached (IOW, the latest) predecessor is done on
+    purpose. We don't want rewind to assume too much, but also, and more
+    importantly, we don't want rewind to deal with any potential merge
+    conflicts. And when rewind revives one of the latest predecessors and it is
+    based on an obsolete changeset that was not revived, the revived changeset
+    will simply be an orphan, and it will be up to the user to decide how they
+    want to solve the trouble _after_ rewind is finished. This way of handling
+    rewinds that may produce merge conflicts means less chance to lose work.
+    """
+    remaining = set(latest)
+    seen = set(remaining)
+    extratargets = []
+    while remaining:
+        successor = remaining.pop()
+        markers = unfi.obsstore.predecessors.get(successor, ())
+        data = (((marker[0],), (marker,)) for marker in markers)
+        for (nodes, markers) in sorted(obshistory.groupbyfoldid(data)):
+            for node in nodes:
+                if node in seen:
+                    # basic cycle protection
+                    continue
+                if node in source:
+                    # we've been here while following successors
+                    seen.add(node)
+                    remaining.add(node)
+                elif node not in targetset:
+                    # skipping meta obsmarkers from previous rewind operations
+                    identical = [m[2] & identicalflag for m in markers]
+                    if not all(identical):
+                        extratargets.append(unfi[node].rev())
+
+    return extratargets
+
+def _walk_obsmarkers(ui, unfi, targets):
+    """walking of both successors and predecessors of changesets to rewind to
+
+    This function:
+        - traverses successors of every target, then
+        - traverses predecessors of every latest successor of each target
+        - returns reachable predecessors with content changes
+    """
+    node = unfi.changelog.node
+    targetset = set(node(target) for target in targets)
+    latest, source = _walk_successors(ui, unfi, targetset)
+    extratargets = _walk_predecessors(ui, unfi, targetset, latest, source)
+
+    return extratargets
+
 def _select_rewind_targets(repo, opts):
     """select the revisions we should rewind to
     """
diff -r fe9f9e528a42 -r 668817e8c007 tests/test-rewind.t
--- a/tests/test-rewind.t	Thu Feb 18 07:39:38 2021 +0800
+++ b/tests/test-rewind.t	Tue Dec 22 19:03:59 2020 +0800
@@ -8,6 +8,7 @@
   > publish = false
   > [alias]
   > glf = log -GT "{rev}: {desc} ({files})"
+  > glhf = log -GT "{rev}:{node|short} {desc} ({files})"
   > [extensions]
   > evolve =
   > EOF
@@ -666,16 +667,13 @@
   rewinding 4535d0af405c to 2 changesets: a0316c4c5417 9576e80d6851
   $ hg rewind --to '9576e80d6851' --hidden --dry-run
   rewinding 4535d0af405c to 2 changesets: a0316c4c5417 9576e80d6851
-
-XXX this should also give us 2 changesets
-
   $ hg rewind --to 'a0316c4c5417' --hidden --dry-run
-  rewinding 4535d0af405c to 1 changesets: a0316c4c5417
+  rewinding 4535d0af405c to 2 changesets: a0316c4c5417 9576e80d6851
 
   $ hg rewind --to '9576e80d6851' --exact --hidden --dry-run
-  rewinding 4535d0af405c to 1 changesets: 9576e80d6851
+  rewinding 4535d0af405c to 2 changesets: a0316c4c5417 9576e80d6851
   $ hg rewind --to 'a0316c4c5417' --exact --hidden --dry-run
-  rewinding 4535d0af405c to 1 changesets: a0316c4c5417
+  rewinding 4535d0af405c to 2 changesets: a0316c4c5417 9576e80d6851
 
 actual rewind
 
@@ -1198,3 +1196,311 @@
   $ hg rewind --keep --to 'desc("amended")' --hidden
   abort: uncommitted changes
   [20]
+
+  $ cd ..
+
+Extra cases related to folds
+============================
+
+folding with a changeset created after the rewind target
+
+..      B0 ⇠\
+..      |    ⇠ AB2
+.. A0 ⇠ A1 ⇠/
+
+this simple test case introduces the idea of making rewind consider different
+evolutions of fold components: "parent" evolution of A has more predecessors
+
+  $ hg init extra-fold-case-1
+  $ cd extra-fold-case-1
+
+  $ echo R > R
+  $ hg ci -qAm R
+  $ echo A > A
+  $ hg ci -qAm A0
+  $ hg amend -m A1
+  $ echo B > B
+  $ hg ci -qAm B0
+  $ hg fold -r 'desc("A1")::' -m AB2 --exact -q
+
+  $ hg glhf --hidden
+  @  4:7f9a5314ef94 AB2 (A B)
+  |
+  | x  3:16429ed4b6cb B0 (B)
+  | |
+  | x  2:3748b241cad8 A1 (A)
+  |/
+  | x  1:fa8956746c52 A0 (A)
+  |/
+  o  0:167e04d3d1b2 R (R)
+  
+
+target selection
+
+when rewinding from a fold, rewind to all of its components (at various points
+in their evolution) to not lose work
+
+  $ hg rewind --hidden --to 'desc("A0")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: fa8956746c52 16429ed4b6cb
+  $ hg rewind --hidden --to 'desc("B0")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: 3748b241cad8 16429ed4b6cb
+  $ hg rewind --from 'desc("AB2")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: 3748b241cad8 16429ed4b6cb
+
+  $ cd ..
+
+folding with a changeset we rebased onto
+
+.. A0 ⇠ A1 ⇠\
+..      |    ⇠ AB2
+..      B0 ⇠/
+
+similar to the previous case, but this time evolution of A has more
+predecessors and at some point starts to be based on B
+
+  $ hg init extra-fold-case-2
+  $ cd extra-fold-case-2
+
+  $ echo R > R
+  $ hg ci -qAm R
+  $ echo A > A
+  $ hg ci -qAm A0
+  $ hg up 'desc("R")' -q
+  $ echo B > B
+  $ hg ci -qAm B0
+  $ echo A > A
+  $ hg ci -qAm A1
+  $ hg prune -r 'desc("A0")' -s 'desc("A1")'
+  1 changesets pruned
+
+  $ hg fold -r 'desc("B0")::' -m AB2 --exact -q
+
+  $ hg glhf --hidden
+  @  4:1988e9fe9517 AB2 (A B)
+  |
+  | x  3:7175ff74409b A1 (A)
+  | |
+  | x  2:d6ed1d624918 B0 (B)
+  |/
+  | x  1:fa8956746c52 A0 (A)
+  |/
+  o  0:167e04d3d1b2 R (R)
+  
+
+target selection
+
+when rewinding from a fold, rewind to all of its components (at various points
+in their evolution) to not lose work
+
+  $ hg rewind --hidden --to 'desc("A0")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: fa8956746c52 d6ed1d624918
+  $ hg rewind --hidden --to 'desc("B0")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: d6ed1d624918 7175ff74409b
+  $ hg rewind --from 'desc("AB2")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: d6ed1d624918 7175ff74409b
+
+  $ cd ..
+
+folding with a changeset that rebased on us
+
+.. B0 ⇠⇠⇠⇠ B1 ⇠\
+.. |       |    ⇠ AB2
+.. |  A0 ⇠ A1 ⇠/
+
+now evolutions of A and B have the same amount of changesets, but at point 0
+they aren't yet related
+
+  $ hg init extra-fold-case-3
+  $ cd extra-fold-case-3
+
+  $ echo R > R
+  $ hg ci -qAm R
+  $ echo A > A
+  $ hg ci -qAm A0
+  $ hg amend -m A1
+  $ hg up 'desc("R")' -q
+  $ echo B > B
+  $ hg ci -qAm B0
+  $ hg up 'desc("A1")' -q
+  $ echo B > B
+  $ hg ci -qAm B1
+  $ hg prune -r 'desc("B0")' -s 'desc("B1")'
+  1 changesets pruned
+
+  $ hg fold -r 'desc("A1")::' -m AB2 --exact -q
+
+  $ hg glhf --hidden
+  @  5:7f9a5314ef94 AB2 (A B)
+  |
+  | x  4:fe7a7d317e16 B1 (B)
+  | |
+  +---x  3:d6ed1d624918 B0 (B)
+  | |
+  | x  2:3748b241cad8 A1 (A)
+  |/
+  | x  1:fa8956746c52 A0 (A)
+  |/
+  o  0:167e04d3d1b2 R (R)
+  
+
+target selection
+
+  $ hg rewind --hidden --to 'desc("A0")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: fa8956746c52 fe7a7d317e16
+  $ hg rewind --hidden --to 'desc("B0")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: 3748b241cad8 d6ed1d624918
+  $ hg rewind --hidden --to 'desc("A1")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: 3748b241cad8 fe7a7d317e16
+  $ hg rewind --hidden --to 'desc("B1")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: 3748b241cad8 fe7a7d317e16
+  $ hg rewind --from 'desc("AB2")' --dry-run
+  rewinding 7f9a5314ef94 to 2 changesets: 3748b241cad8 fe7a7d317e16
+
+actual rewind
+
+  $ hg rewind --hidden --to 'desc("A0")'
+  1 new orphan changesets
+  rewound to 2 changesets
+  (1 changesets obsoleted)
+  working directory is now at e492d2f9be46
+
+after rewind to A0:
+- A0' and B1' are successors to AB2 (split using rewind)
+- A0' is a successor of A0 (operation: rewind)
+- A0' is a child of R (just like A0)
+- B1' is a successor of B1 (operation: rewind)
+- B1' is a child of A1 (just like B1), and therefore an orphan
+
+  $ hg obslog -a
+  o    54b340ce1d87 (6) A0
+  |\     split(description, meta, parent, content) from 7f9a5314ef94 using rewind by test (Thu Jan 01 00:00:06 1970 +0000)
+  | |    meta-changed(meta) from fa8956746c52 using rewind by test (Thu Jan 01 00:00:06 1970 +0000)
+  | |
+  +---@  e492d2f9be46 (7) B1
+  | | |    split(description, meta, parent, content) from 7f9a5314ef94 using rewind by test (Thu Jan 01 00:00:06 1970 +0000)
+  | | |    meta-changed(meta) from fe7a7d317e16 using rewind by test (Thu Jan 01 00:00:06 1970 +0000)
+  | | |
+  x---+  7f9a5314ef94 (5) AB2
+  | | |    folded(description, parent, content) from 3748b241cad8, fe7a7d317e16 using fold by test (Thu Jan 01 00:00:06 1970 +0000)
+  | | |
+  x | |  3748b241cad8 (2) A1
+  |/ /     reworded(description) from fa8956746c52 using amend by test (Thu Jan 01 00:00:06 1970 +0000)
+  | |
+  | x  fe7a7d317e16 (4) B1
+  | |    rewritten(description, parent) from d6ed1d624918 using prune by test (Thu Jan 01 00:00:06 1970 +0000)
+  | |
+  | x  d6ed1d624918 (3) B0
+  |
+  x  fa8956746c52 (1) A0
+  
+  $ hg glhf
+  @  7:e492d2f9be46 B1 (B)
+  |
+  | o  6:54b340ce1d87 A0 (A)
+  | |
+  x |  2:3748b241cad8 A1 (A)
+  |/
+  o  0:167e04d3d1b2 R (R)
+  
+
+  $ hg debugobsolete --exclusive -r 'first(head())'
+  7f9a5314ef94f5856ee90661268194cc5ce9b332 54b340ce1d87f3593fd9de2a742e7b444e5136ed e492d2f9be46b73c0cfa51709e92db864b8f3ed9 0 (Thu Jan 01 00:00:06 1970 +0000) {'ef1': '15', 'operation': 'rewind', 'user': 'test'}
+  fa8956746c5294ce3351309133b450c5930f30f5 54b340ce1d87f3593fd9de2a742e7b444e5136ed 4 (Thu Jan 01 00:00:06 1970 +0000) {'ef1': '2', 'operation': 'rewind', 'user': 'test'}
+  $ hg debugobsolete --exclusive -r 'last(head())'
+  7f9a5314ef94f5856ee90661268194cc5ce9b332 54b340ce1d87f3593fd9de2a742e7b444e5136ed e492d2f9be46b73c0cfa51709e92db864b8f3ed9 0 (Thu Jan 01 00:00:06 1970 +0000) {'ef1': '15', 'operation': 'rewind', 'user': 'test'}
+  fe7a7d317e168a15e8aa43131b54d3256443d728 e492d2f9be46b73c0cfa51709e92db864b8f3ed9 4 (Thu Jan 01 00:00:06 1970 +0000) {'ef1': '2', 'operation': 'rewind', 'user': 'test'}
+
+  $ cd ..
+
+simple fold with a missing part
+
+.. B0 ⇠ (B1) ⇠\
+.. |     |     ⇠ AB2
+.. A0 ⇠  A1  ⇠/
+
+a stack was rewritten, but then a part of it became unknown locally
+
+  $ hg init extra-fold-case-4
+  $ cd extra-fold-case-4
+
+  $ echo R > R
+  $ hg ci -qAm R
+  $ echo A > A
+  $ hg ci -qAm A0
+  $ echo B > B
+  $ hg ci -qAm B0
+  $ hg up 'desc("R")' -q
+  $ echo A > A
+  $ hg ci -qAm A1
+  $ echo B > B
+  $ hg ci -qAm B1
+  $ hg prune -r 'desc("A0")+desc("B0")' -s 'desc("A1")+desc("B1")' --biject
+  2 changesets pruned
+
+  $ hg fold -r 'desc("A1") + desc("B1")' -m AB2 --exact -q
+
+  $ hg glhf --hidden
+  @  5:1988e9fe9517 AB2 (A B)
+  |
+  | x  4:25210d726f52 B1 (B)
+  | |
+  | x  3:9c76368ab336 A1 (A)
+  |/
+  | x  2:a07c12c45197 B0 (B)
+  | |
+  | x  1:fa8956746c52 A0 (A)
+  |/
+  o  0:167e04d3d1b2 R (R)
+  
+
+target selection
+
+  $ hg rewind --hidden --to 'desc("A0")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: fa8956746c52 25210d726f52
+  $ hg rewind --hidden --to 'desc("A1")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: 9c76368ab336 25210d726f52
+  $ hg rewind --hidden --to 'desc("B1")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: 9c76368ab336 25210d726f52
+
+because B0 is a child of A0, we use A0 instead of A1 unless --exact is given
+
+XXX the semantic of --exact might need clarification here,
+XXX for example, shouln't --exact make sure we only rewind to the `--to` target ?
+
+  $ hg rewind --hidden --to 'desc("B0")' --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: fa8956746c52 a07c12c45197
+  $ hg rewind --hidden --to 'desc("B0")' --exact --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: a07c12c45197 9c76368ab336
+
+stripping one of the fold parts
+
+  $ hg strip --config extensions.strip= -r 'desc("B1")' --hidden -q
+
+  $ hg glhf --hidden
+  @  4:1988e9fe9517 AB2 (A B)
+  |
+  | x  3:9c76368ab336 A1 (A)
+  |/
+  | x  2:a07c12c45197 B0 (B)
+  | |
+  | x  1:fa8956746c52 A0 (A)
+  |/
+  o  0:167e04d3d1b2 R (R)
+  
+
+target selection
+
+the obvious challenge here is to somehow work around the missing fold
+component, but we can't do much because it is one of the latest predecessors of
+AB2 fold
+
+in future we might have a way to allow rewind to skip changesets unknown
+locally and still proceed (and lose the least amount of work possible)
+
+  $ hg rewind --hidden --to 'desc("A0")+desc("B0")' --exact --dry-run
+  rewinding 1988e9fe9517 to 2 changesets: fa8956746c52 a07c12c45197
+  $ hg rewind --hidden --to 'desc("A1")' --exact --dry-run
+  abort: unknown revision '25210d726f527e03f1f148bb8048d571512146d9'
+  [255]
+
+  $ cd ..