Re: Tree conflicts - resolution.txt

On Tue, 2008-06-10 at 22:14 +0100, Julian Foad wrote:
> I've been analysing how tree conflicts can be resolved, and written up
> the results in notes/tree-conflicts/resolution.txt
> <http://svn.collab.net/repos/svn/trunk/notes/tree-conflicts/resolution.txt>.

I've made a major update to this doc. It would be really helpful if
anyone could read through and let me know how it sounds.

I'll paste it in-line for convenience.

Thanks.
- Julian

[[[
                           Resolving Tree Conflicts
                           ========================

Resolution of tree conflicts includes:

  (i) A known state of the WC after the conflict is raised.

  (ii) Constructing the desired result from the conflicted state.

  (iii) Marking as resolved (both "svn resolve" and interactive).

I. STATE OF THE WC AFTER CONFLICT IS RAISED
===========================================

When a tree conflict is raised, the "old" and "theirs" and "mine"
versions should be stored locally in the WC in such a way that

  (a) Subversion can turn one of them into a final outcome when told
        svn resolve --accept=theirs TARGET

  (b) the user can examine them and combine them to create a final
      outcome, using commands like
        svn proplist TARGET.theirs
        svn merge TARGET.theirs OTHERFILE TARGET

WC State is defined in terms of what file content and what scheduling
is stored for each of ".working" (the active WC file/dir during
resolving), ".mine" (the previous working file/dir, as preserved for
reference), and ".theirs" (the type and resulting content of the
incoming change).

The expected state for each case is defined in the "WC State" sections
inside the "Resolution Recipes" section.

Principles
----------

* When "svn update" or "svn switch" raises a tree conflict, it shall
  update the victim's "base" version from OLD to THEIRS, and leave the
  "working" version in a state that would be committable (but for the
  explicit check that prevents committing an item marked as in conflict)
  and that, if committed, would restore the item to how it looked in
  "mine". This may involve changing the scheduling of the item, e.g. to
  be re-added if "update" applied a delete.

  When "svn merge" raises a tree conflict, it shall not change the
  working content or scheduling of the victim.

* An update from rX to rY followed by an update back to rX should have
  no overall effect on the local modifications scheduled in the WC.
  Likewise a switch to a different URL_at_REV and a switch back to the
  original one. Likewise a merge followed by a merge of the reverse
  change.

Q. How do we store the "theirs" tree in the WC, especially in the case
where it's a tree and needs to be constructed anew because it comes
(as an Add or Mod) onto a WC item that's Del or not present? What I
mean is to persuade the normal "update" or "merge" code paths to
construct a new WC directory named "TARGET.theirs" on the fly and then
recurse into it applying the incoming mods.

(Need to list the cases where constructing such a new WC tree will be
necessary.)

II. CONSTRUCTING THE DESIRED RESULT
===================================

For cases where the user needs to merge the two conflicting changes
(as opposed to choosing just one and ignoring the other), we need:

  * Recipes for the user to follow
    - see the "Tree Conflict Resolution Recipes" section.

  * Enhanced facilites for merging changes from conflicting partial
    results into the desired result.
    - see the "Arbitrary Merge Facility Required" section.

Tree Conflict Resolution Recipes
================================

This section sets out, for each type of tree conflict, the resolutions
that I expect would be commonly wanted, either giving a useful result
directly or as building blocks for more complex resolutions.

The aim is to provide in each of the selected cases a sufficiently
clear recipe for a user to resolve most tree conflicts that they
encounter. Such a user is expected to be fairly proficient in using
Subversion but not to have any knowledge of the way tree conflicts are
handled internally.

Under each type of conflict are the following subsections:

  "WC State" describes the state in which the WC should be left when
  the conflict is raised, according to the principles set out in
  section I.

  "Some use cases" lists some likely use cases by which a user might
  encounter such a conflict, concentrating on cases that want a
  resolution other than "THEIRS" or "MINE".

  "Options" lists resolution options that ought to be available. The
  resolution options "THEIRS" and "MINE" should be available in every
  case (so that a user can resolve a whole tree at once with one of
  those options) and should be implemented internally. Any other
  options listed here may be recipes for the user to apply manually.
  These recipes are starting from the state in which the WC should be
  left by Subversion after raising a conflict.

The "WC State" subsection is intended as design requirements, not for
the end user. I have not yet attempted to implement this as part of
tree-conflict detection, and have no idea to what extent this is
currently achieved in the tree-conflicts branch.

The other two subsections are intended as the basis of material for
end users to read.

Principles
----------

* We shall assume the ability to examine the source-left ("old") and
  source- right ("theirs") and target ("mine") tree states as well as
  the source diffs.

  In a merge, we shall not assume or attempt to make use of any
  ancestral relationship between the target and the source.

Renames and Replacements
------------------------

An incoming rename is treated here as its two constituent actions - an
incoming delete and an incoming add - separately.

In an incoming replacement, the delete is assumed to come before the
add. (Currently, they may sometimes come the wrong way around. I have
not analysed the cases in which this can happen, nor the
consequences.)

Where the ability to schedule a replacement of one node kind with
another is implied, this ability may not be supported (and currently
is not supported) by the working copy library. Such cases will
therefore be unsupported. This is not seen as a deficiency inherent in
tree conflict handling, but as a separate deficiency that restricts
tree conflict handling in certain cases.

Meaning of "Choose Theirs" and "Choose Mine"
--------------------------------------------

There is a subtle difference between the meanings of "Choose Theirs"
and "Choose Mine" as applied to an update or switch compared with when
the terms are applied to a merge.

For update and switch, the final state resulting from the incoming
change is already existing in the history of the branch we're working
on, and is going to be our WC's new "base" version, so we can't choose
to "ignore" this incoming change. The request to "Choose Mine" means
"Schedule the item to be changed from its new base state back to how
my version of it looked before this operation". This may involve
changing the scheduling of the item. The request to "Choose Theirs"
simply means "Discard my pending changes so as to keep their version
of it".

For a merge, however, the final state of the incoming change is not
going to be the new base state of the branch we're working on, and so
we _can_ choose to ignore it if we so wish. Also, "my" version is a
combination of historical and working-copy changes, so we cannot in
general choose to ignore this, we can only schedule changes that
reverse it. In a merge, then, "Choose Mine" means "Leave my version of
the item as it is" (which does not involve any change of scheduling),
while "Choose Theirs" means "Overwrite my version with a copy of Their
version of the item" (which may involve scheduling an add or
delete). The potential alternative meaning, "Make Their change", is
not viable: it is what Subversion already tried to do, and it
resulted in the very conflict we're now trying to resolve.

Recipes
=======

up/sw: Add onto Add
-------------------

WC State:
  .working: sched=Normal/Replace, content=.mine
  .mine: sched=Add[w/hist], content=Something
  .theirs: action=Add[w/hist], content=Something

Some use cases:
  - I have already applied the patch - their item is identical to mine.
    -> want to do it just once -> THEIRS.
  - Two different new items happened to be given the same name.
    -> accept theirs & rename mine -> RENAME-MINE.
  - I was doing roughly the same thing but the item is a bit different.
    -> merge the two items -> manual 2-way merge (or 3-way if both are
       w/hist and it's the same copy-from source).

Options:
  THEIRS: As usual, like "svn revert TARGET".
  MINE: My content as a scheduled modification, or as a scheduled
          replace* if "my" node-kind (or copy-from?) differs.
  RENAME-MINE: Add "my" content under a different name, and then accept
          "their" add:
    - Choose a new name for mine.
    - svn rename TARGET NEWNAME
    - svn revert TARGET

If identical (node-kind, content, props, copyfrom-info?):
  Recommend choosing THEIRS.

up/sw: Del onto Del
-------------------

WC State:
  .working: sched=unversioned, content=None
  .mine: sched=Del, content=None
  .theirs: action=Del, content=None

Some use cases:
  - Already applied the patch
    -> want to do it just once -> THEIRS.
  - Renamed to two different names
    -> want to undo Their renaming and make it like Mine, as if we had
    a "Choose Mine" option that worked on whole rename operations. ->
    RENAME.

Options:
  THEIRS: As usual (but has no effect in this case)
  MINE: As usual (but has no effect in this case)
  RENAME:
    - svn rename THEIR-NEW-NAME MY-NEW-NAME
    And take care to notice if there were any modifications made at
    the same time as the renames; if so, these might need merging.

Note: In an update or switch, THEIRS and MINE are from the same OLD
base, so there is no possibility that the item we are deleting locally
is different from the item the incoming change is deleting.

up/sw: Mod onto Del
-------------------

WC State:
  .working: sched=Del, content=None
  .mine: sched=Del, content=None
  .theirs: action=Mod, content=Something

Some use cases:
  - Locally renamed
    -> want to apply the incoming mod to a different item -> ELSEWHERE.

Options:
  THEIRS: As usual.
  MINE: Leave it deleted.
  ELSEWHERE1: Apply their mod onto my renamed item. (Mine is the
master.)
    - Determine a way to obtain the incoming diff and apply it to the
      new name, e.g. one of these:
      - svn merge -r OLDREV:NEWREV TARGET(URL?) NEWNAME
        (should be possible for "up" always, "sw" never, "merge"
sometimes)
      - svn merge -r old:theirs TARGET NEWNAME [*1]
  ELSEWHERE2: Reapply my Rename [+mod] onto theirs. (Theirs is the
master.)
    - mv NEWNAME TMP
    - svn revert NEWNAME / rm -rf NEWNAME
    - Move TARGET.theirs to NEWNAME. Here's one way to do that:
      - svn resolve --accept=theirs TARGET
      - svn rename TARGET NEWNAME
      - svn resolve --accept=mine TARGET
    - svn merge TARGET_at_old TMP_at_working NEWNAME [*1]

up/sw: Del onto Mod
-------------------

WC State:
  .working: sched=Add, content=.mine
  .mine: sched=Normal, content=Something
  .theirs: action=Del, content=None

Some use cases:
  - The incoming change is (part of) a rename
    -> want to transfer my local mod to the renamed item ->
MOVE-MY-MODS.

Options:
  THEIRS: As usual.
  MINE: Schedule for Add.
  MOVE-MY-MODS: Reapply my mod onto their renamed item. (Theirs is the
master.)
    - Determine their new name.
    - Wait till up/sw has processed the new-named item.
    - svn merge -r OLD:MINE TARGET THEIRNEWNAME [*1]
    - svn revert TARGET
  MOVE-MY-MODS2: Apply their rename[+mod] onto my item. (Mine is the
master.)
    - svn merge TARGET_at_old THEIRNEWNAME TARGET [*1]
    - svn revert THEIRNEWNAME
    - svn rename TARGET THEIRNEWNAME

merge: Add onto Something (Identical or Different-Content or
Different-Kind)
-------------------------

WC State:
  .working: =.mine
  .mine: sched=(not Del), content=Something
  .theirs: action=Add[w/hist?], content=Something

Some use cases:
  Same as for "up/sw: Add onto Add", plus one more:
  - Two different new items happened to be given the same name.
    -> keep mine & rename theirs -> RENAME-THEIRS.

Options:
  THEIRS: Schedule local mods (if any change needed) to replace mine
    with theirs. (If copyfrom differs, should we schedule Replace or
not?)
  MINE: (Nothing to do.)
  RENAME-MINE: Add "my" content under a new name, and accept "their"
    add under the original name. (Theirs is the master.)
    - Choose a new name for mine.
    - svn rename TARGET NEWNAME
    - svn resolve --accept=theirs TARGET
  RENAME-THEIRS: Add theirs under a new name. (Mine is the master.)
    - Choose a new name for theirs.
    - svn rename TARGET.theirs NEWNAME [*1]
    - svn resolve --accept=mine TARGET

If identical (node-kind, content, props, copyfrom-info?):
  Recommend choosing THEIRS.

merge: Del onto Nothing Here
----------------------------

WC State:
  .working: =.mine
  .mine: sched=(Del/unversioned), content=None
  .theirs: action=Del, content=None

Some use cases:
  - User's process is wrong: maybe something else needed to be merged
    first.
    -> want to revert this whole merge.
  - Already applied the patch or merged the change without recording
    the fact.
    -> want to do it once -> MINE.
  - The item being deleted (or renamed) in the source has been renamed
    in the target branch.
    -> want to delete/rename something else -> ELSEWHERE.

Options:
  THEIRS: Nothing to do - same result as MINE.
  MINE: (Nothing to do.)
  ELSEWHERE: Leave TARGET as it is, and
    - Find the new name(s).
    - svn delete MYNEWNAME
      or
      svn rename MYNEWNAME THEIRNEWNAME

merge: Del onto Not Same Kind
-----------------------------

WC State:
  .working: =.mine
  .mine: sched=(not Del), content=TheOtherKind
  .theirs: action=Del, content=None

Some use cases:
  - User's process is wrong: maybe something else needed to be merged
    first.
    -> want to revert this whole merge.

Options:
  THEIRS:
    - svn delete TARGET
  MINE: (Nothing to do.)

merge: Del onto Not Same Content
--------------------------------

WC State:
  .working: =.mine
  .mine: sched=(not Del), content=SameKind
  .theirs: action=Del, content=None

Some use cases:
  - The content was intentionally divergent, and we still want to
    delete it.
    -> THEIRS.
  - The content was intentionally divergent, and the source node is
    being renamed (and possibly modified at the same time).
    -> Apply the incoming rename (possibly +mod) onto mine -> RENAME.

Options:
  THEIRS:
    - svn delete TARGET
  MINE: (Nothing to do.)
  RENAME1: Apply their rename [+mod] onto mine. (Mine is the master.)
    - Find the incoming new name.
    - Wait till the new name has been processed (added).
    - svn merge TARGET.old THEIRNEWNAME TARGET [*1]
    - svn revert THEIRNEWNAME
    - svn rename TARGET THEIRNEWNAME
  RENAME2: Reapply my mods onto their renamed item. (Theirs is the
  master.)
    - Find the incoming new name.
    - Wait till the new name has been processed (added).
    - svn merge -r old:mine TARGET THEIRNEWNAME [*1]
    - svn resolve --accept=theirs TARGET

merge: Mod onto Nothing Here
----------------------------

WC State:
  .working: =.mine
  .mine: sched=(Del/unversioned), content=None
  .theirs: action=Mod, content=Something

Some use cases:
  - The item was renamed locally
    -> apply the incoming mod elsewhere -> ELSEWHERE.

Options:
  THEIRS: Re-schedule the target to come back.
    - copy TARGET.theirs TARGET
    - svn add TARGET
  MINE: (Nothing to do.)
  ELSEWHERE1: Apply their mod onto mine. (Mine is the master.)
    - Find the new name.
    - Wait till the new name has been processed (added).
    - svn merge -r OLD:THEIRS TARGET NEWNAME [*1]
  ELSEWHERE2: Apply my rename[+mod] onto Theirs. (Theirs is the master.)
    - svn merge -r BASE:WC NEWNAME TARGET.theirs [*1]
    - mv TARGET.theirs NEWNAME

merge: Mod onto Not Same Kind
-----------------------------

WC State:
  .working: =.mine
  .mine: sched=(not Del), content=TheOtherKind
  .theirs: action=Mod, content=Something

Options:
  THEIRS: Not supported. Throw an error. (Want to schedule the target
  to replace with theirs, but WC doesn't support this.)
  MINE: (Nothing to do.)

Note [*1]: These commands are not yet supported.

Arbitrary Merge Facility Required
=================================

To enable the user to resolve a "Rename onto Mod" or "Mod onto Rename"
conflict efficiently and flexible, we need the ability to merge the
difference between two arbitrary WC items into another WC item. The
two source items:

  - may have different names;
  - may be related by copyfrom info in one that in some way refers to
  the other;
  - may be pre-resolution conflict results like TARGET.mine or
  TARGET_at_mine.

Two ways this could be achieved:

1. Make use of history-sensitive merging by referring to the two items
   through special revision kinds "old" "theirs" "mine":

     svn merge -r old:theirs TARGET NEWNAME

2. Use non-history-sensitive merging on arbitrary files
   "<TARGET>.old" "<TARGET>.theirs" "<TARGET>.mine":

     svn merge TARGET.old TARGET.theirs NEWNAME

Q. How can we most easily implement an extension of "svn merge" that
achieves a copyfrom-history-sensitive diff (between WC items) rather
than an unaware diff?

III. MARKING AS RESOLVED
========================

Primary APIs:

  libsvn_wc/adm_ops.c:resolve_conflict_on_entry()

Pre-tree-conflicts, the "resolve" functions in client through to WC
layers all end up calling resolve_conflict_on_entry() on each item. It
marks all text conflicts and property conflicts on the item as
resolved. It also can select and copy into place one of the available
file-text choices, but doesn't appear to have any such support for
property conflicts.

On the tree conflicts branch, (till branch@{2008-05-29} at least) this
function assumes it will be passed the path to the parent dir of some
conflict victims, and it simply clears tree conflict data about all
victims from the entries file.

Plan

----
Separate the different functions that resolve_conflict_on_entry()
performs, making it more modular and "orthogonal".
Make the tree conflict functions operate on one victim rather than on
a whole parent directory having conflicts on any number of victims.
Make these new functions public so that the caller can compose the
various actions (copying, marking as resolved, notifying, and
recursing) in whatever order it wants.
Create the following new functions:
  * Copy one of the simple outcomes (old, mine, theirs) onto the
  target.
    select_conflict_outcome(path, svn_wc_conflict_choice_t, ...);
    select_tree_conflict_outcome(victim_path,
svn_wc_conflict_choice_t, ...);
    - Copies the user's choice onto the "working" version of the item.
    - For tree conflicts, also includes changing the scheduling of the
    item.
    - This operation, and certainly the choice part of it, is
    logically above the WC layer, except for knowledge of where the
    files to choose from are stored.
  * Mark conflicts as resolved on a (victim) path.
    svn_wc_mark_conflict_resolved(path, ...);
    - Mark text and property conflicts on one item as resolved.
    svn_wc_mark_tree_conflict_resolved(victim_path, ...);
    - Mark the tree conflict on one victim as resolved.
  * Support for resolver callback? - where/how?
]]]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe_at_subversion.tigris.org
For additional commands, e-mail: dev-help_at_subversion.tigris.org