[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: FSFS successor ID design draft

From: Stefan Sperling <stsp_at_elego.de>
Date: Mon, 29 Aug 2011 16:54:56 +0200

On Fri, Aug 26, 2011 at 08:59:21AM -0400, C. Michael Pilato wrote:
> On 08/26/2011 08:51 AM, Ivan Zhakov wrote:
> > Mike, thanks for the answer, but I still don't understand how
> > successor ID information could help us with move handling?
>
> (Honestly, I don't either. I was taking Stefan's word for it.)

I don't have a proper design for this, just some vague ideas.
I believe that it will work.

The following (untested :) pseudo code shows what the server could
do to find out which nodes to report as moved from A to B within
the delta between LEFT_PATH_at_LEFT_REV and RIGHT_PATH_at_RIGHT_REV.

This doesn't strictly require a successor ID cache.
The IDs could also be computed at run-time if this is feasible.

It should be possible to produce the same result with just copyfrom
information and looping over added nodes instead of deleted nodes.
However it seems solving it that way is a lot less straightforward
(well, at least I cannot seem to wrap my brain around it...)
A successor ID cache has more uses besides this one, so it's worth
adding anyway even if we find another way of generating the moved_nodes
list below.

The following converts somewhat freely between paths and node-revision-id
In reality there would be more abstraction layers.

[[[
  deleted_nodes = nodes which appear in LEFT_PATH_at_LEFT_REV but not in
                  RIGHT_PATH_at_RIGHT_REV
  added_nodes = nodes which appear in RIGHT_PATH_at_RIGHT_REV but not in
                LEFT_PATH_at_LEFT_REV
  moved_nodes = []
  # A 'node' in this context is a repos_relpath
  for each node in deleted_nodes {
    node_rev_id = get_node_node_rev_id(node_at_LEFT_REV)
    successors = get_successors_in_rev_range(node_rev_id,
                                             [LEFT_REV, RIGHT_REV])
    lines_of_history = 0
    copied_successor = NULL
  
    # Look for copies among successors. Ignore copies to other branches.
    # Assume successor IDs are sorted in order, by revision.
    previous_s = node_rev_id
    for s in successors {
      if repos_relpath(s) is [a child of] LEFT_PATH or RIGHT_PATH {
        if get_copy_id(previous_s) != get_copy_id(s) {
            if copied_successor == NULL {
            copied_successor = s
              lines_of_history++
            } else if s is successor of copied_successor {
            copied_successor = s
            } else {
            lines_of_history++
            break
          }
        }
      }
      previous_s = s
    }
  
    # If a single copied successor is among added nodes, the node was moved
    if copied_successor and lines_of_history == 1:
      if added_nodes[repos_relpath(copied_successor)] != NULL:
        moved_from_repos_relpath = node
        moved_to_repos_relpath = repos_relpath(copied_successor)
        moved_nodes += (moved_from_repos_relpath, moved_to_repos_relpath)
  }
]]]

The moved_nodes list gives us the server-side op-roots of moves.
The editor driver still needs to use this smartly to make it useful.
I think it should send "move" commands upfront, e.g. right after open_root().
The client needs to move nodes in its working copy before other changes are
applied. The driver should also adjust paths of moved-along children properly.

Is there anything wrong with this?

Any ideas about how to solve this without using successors?
Received on 2011-08-29 16:55:36 CEST

This is an archived mail posted to the Subversion Dev mailing list.