[tree-conflicts] On calculating youngest common ancestor

Stephen, Stefan:

The other day we had a conversation that caused me to recommend to you the
use of a new 1.5 RA API I'd written in your attempts to determine whether a
file which would be removed by a merge of a deletion from a branch had been
edited since the branchpoint. I can't recall the exact context, but I know
this had something to do with tree conflicts and avoiding marking *all*
merged deletions as suspect tree-conflict-wise.

Anyway, here's the API:

   svn_ra_get_location_segments()

This basically drives a custom callback, feeding it svn_location_segment_t
objects which represent a path and a range of revisions in which your target
object occupied that path.

There's a wrapper around it that de-streamifies it, too:

   svn_client__repos_location_segments()

To determine youngest common ancestor between two locations (path@rev) is
simple:

   1. fetch the location segments for path1@rev1

   2. fetch the location segments for path2@rev2

   3. compare them -- they are sorted by revision, so starting with
       each segment set's youngest revision and working toward the
       oldest, the minute you find a revision in which the path for
       that revision in both segment sets is the same, you've found
       your youngest common ancestor.

There's even a Python-bindings-based tool in the trunk to play with here.

   $ alias get-locations=./tools/examples/get-location-segments.py
   $ get-locations http://svn.collab.net/repos/svn/tags/1.4.5
   r26351-r28009: tags/1.4.5
   r26346-r26350: branches/1.4.5
   r25343-r26345: tags/1.4.4
   r25189-r25342: (null)
   r19524-r25188: branches/1.4.x
   r1-r19523: trunk
   $ get-locations http://svn.collab.net/repos/svn/trunk
   r1-r28009: trunk
   $

A little bit of data crunching shows that /trunk@19523 is the youngest
common ancestor of Subversion's own /trunk and /tags/1.4.5 directories.

WARNING: This API can be really slow against pre-1.5 servers due to having
to fallback to using svn_ra_get_logs(). It's been heavily optimized in 1.5
servers.

Another method is to call svn_ra_get_logs() on the longest common path of
the two (in my example, the root of the repository) and provide the two
relative paths ("trunk", "tags/1.4.5") as targets, then tracking the
location changes of each target over time as log feeds you data. When you
finally get to a place where both branches lived at the same path, you can
stop. (Though, unfortunately we don't yet have callback cancellation logic
in the form of graceful handling of SVN_ERR_CEASE_INVOCATION in our RA log API).

-- 
C. Michael Pilato <cmpilato@collab.net>
CollabNet   <>   www.collab.net   <>   Distributed Development On Demand