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

Re: Outsider impression about merge tracking

From: Folker Schamel <schamel23_at_spinor.com>
Date: 2007-11-20 09:41:04 CET

Hi Karl!

> Folker Schamel <schamel23@spinor.com> writes:
>> I'm reluctant sending this mail, because I have a huge respect
>> for the Subversion developers. But maybe sometimes some outsider view
>> is helpful:
>>
>> I fear that subversion team is going to slap some premature merge-tracking
>> feature out.
>
> Thanks for your concerns! Of course we worry about that too, and are
> trying to make merging Do The Right Thing as much as possible.
>
>> Which in practice will causes serious headaches and dissatisfaction for users
>> due to many open issues. (Also a good documentation of the limitations
>> of merge-tracking won't prevent this.)
>>
>> And for such kind of non-trivial algorithmic problems, usually you cannot
>> fix broken implementations afterwards, but the only chance is to
>> (re)implement a clean solution from the beginning.
>
> Well, your statements are true in general, but they'll only be helpful
> if you give specific examples. Which is more work, of course; it's
> also the only way to get constructive results.
>
>> Is commercial pressure driving the subversion code base in a dead end?
>
> No. Better merging is something Subversion has needed for a long
> time; it's an area where we lag behind other version control systems
> (both proprietary and open source). We need it.
>
> While there are certainly corporations that want to see the feature
> finished, and some of them are helping to develop it (e.g., CollabNet,
> Google, et al), I don't see commercial pressure causing any problems
> here. The community is setting the deadlines and making the technical
> decisions in public forums, as always.
>
> I too am worried, but mainly about technical issues that I think are
> fixeable (e.g., issue #2897, etc). Can you be more specific?

I have the questions of Mark in mind:
http://svn.haxx.se/dev/archive-2007-11/0729.shtml
I think both
i) supporting reflected merges without filtering out a conflict resolution, and
ii) merging between branches
is important, otherwise people will complain a lot.
Currently people complain that Subversion has no merge-tracking.
Without solving i) and ii) people will complain that merge-tracking
of Subversion is fundamentally broken.

Technically, I came to two conclusions:
a) Finding an algorithm solving both i) and ii) basically seems to be
not too difficult in principle (see below). However:
b) This is *in principle not possible* with the mergeinfo scheme
you are currently using.

Therefore my conclusion:
Dead end.

***** Details about a) and b):

Issue i) can be solved by
http://svn.haxx.se/dev/archive-2007-11/0766.shtml
while ii) (combined with i) is not possible with the current mergeinfo scheme:
Currently, when merging from branchA -> branchB -> branchC,
then mergeinfo of branchC contains both the revisions committed
to branchA and branchB, eliminating the information that
merges von branchA came indirectly via branchB.
But this information seems to be *unavoidable* necessary to solve ii).
I think mergeinfo of branchC must only refer to branchB,
only indirectly referring to branchA by the mergeinfo stored at branchB.
So that mergeinfo data builds a graph.
And that graph must be processed efficiently.
(Some longer time ago, Daniel Rall pointed out correctly that
merging is a graph problem.)
In other words, the current mergeinfo scheme has not enough information locally.

A working merge algorithm for "merge FROM -r X:Y TO" could be for example:
   for each r in X:Y in reverse order:
     Check if the mergeinfo *tree* of FROM and TO have a common subtree r_sub@where_sub.
     In this case unmerge that change: merge -c -r_sub where_sub
     Add r@FROM to mergeinfo of TO. (But do *not* add mergeinfo of FROM.)
   Do a classical merge FROM -rX:Y TO.
This is the algorithm I found which is closed to Subversion philosophy.
But also this still requires a fundamentally different mergeinfo
property handling (*not* storing branchA in mergeinfo of branchC),
and probably a completely different database for that info
for efficiently doing the tree search. Otherwise merge tracking
would be horrible inefficient.

Of course, there may also exist different algorithms solving i) and ii).
But I claim that there is no algorithm (which is efficient enough)
with the current mergeinfo data scheme (where mergeinfo of branchC
contains branchA) solving i) and ii) for principle reasons.

Cheers,
Folker

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Tue Nov 20 09:41:35 2007

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