Re: Moves in FSFS

On 19.09.2013 12:09, Julian Foad wrote:
> Branko Čibej wrote:
>> On 17.09.2013 12:55, Julian Foad wrote:
>> [...]
>>> Start with
>>>
>>> r10:
>>> trunk
>>> /A
>>> /B
>>>
>>> branch the trunk:
>>>
>>> r20:
>>> trunk
>>> /A
>>> /B
>>> branch
>>> /A (pointer to /trunk/A)
>>> /B (pointer to /trunk/B)
>>>
>>> modify branch/A:
>>>
>>> r30:
>>> trunk
>>> /A
>>> /B
>>> branch
>>> /A
>>> /B (pointer to /trunk/B)
>>>
>>> Now let's say we're diffing branch_at_20 and branch_at_30. I want to be
>>> able to report a mapping between each path in branch_at_20 and the path
>>> in r30 corresponding to "the same node", where "the same node" is to
>>> be defined in some way that makes sense for tracking moves. In this
>>> simple example, there are not even any moves, and so I want the move-
>>> tracking code to be able to deduce the following 1:1 path-mapping
>>> between branch_at_20 and branch_at_20:
>>>
>>> PATH_at_20 PATH_at_30
>>> branch <-> branch
>>> branch/A <-> branch/A
>>> branch/B <-> branch/B
>>>
>>> It certainly must not report a simple (node-id, copy-id) correspondence,
>>> because that would look something like:
>>>
>>> PATH_at_20 PATH_at_30
>>> branch <-> branch
>>> branch/A <-> trunk/A # or (nil) as it's out of tree-scope
>>> (nil) <-> branch/A
>>> branch/B <-> branch/B
>>> which breaks the mapping between branch/A_at_20 and branch/A_at_30.
>> I'm confused. What are you trying to solve here?
> The query I'm trying to solve is: for the paths I can see in 'branch' in r20, tell me where they are in r30.
>
> The example I gave above is the simplest case, the degenerate case, as they have not even been moved, but a typical interesting case is the above plus some moves:
>
> r40: move A to C, and move B to D
>
> So the repository in r40 looks like:
>
> r40:
> trunk
> /A
> /B
> branch
> /C
> /D
>
> Now we query: for each path in 'branch' in r20, where is "it" (the same node-line) in r40? The query is to be answered without scanning all intervening revisions sequentially.

Fine, but this has nothing at all to do with moves. It's the
forward-history search problem, which the current storage model cannot
solve easily because of immutable revision files. We'd need an
additional index that inverts the predecessor links. AUIU FSX is
designed to solve that, as is the metadata-ng model.

Note that any history scanning we do today is a linear scan through the
predecessor links. I don't know why you're trying to optimize that as
part of the move design.

-- Brane

-- 
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane_at_wandisco.com