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

Re: Revision Reconciliation Algorithm

From: C. Michael Pilato <cmpilato_at_collab.net>
Date: 2007-12-29 03:59:39 CET

David Glasser wrote:
> On Dec 27, 2007 12:12 PM, Sharmarke Aden <aden.list@gmail.com> wrote:
>> Hi, I'm trying to understand how Subversion determines the changes
>> that have occurred between two revision and I was wondering if someone
>> in here could help understand how it all works. For example, say the
>> latest (head) revision in the svn repository is 210 and my working
>> copy is 103. My question is how does subversion calculate all the
>> adds/updates/removes my working copy needs to bring it's revision
>> state to 210? What algorithm or techniques does subversion use to
>> calculate deltas between two revisions and how efficient is it?
>
> It's tough to answer this without knowing how much you're familiar
> with the architecture. The filesystem is stored as a DAG. The update
> algorithm essentially just takes the difference ("delta") between two
> directories, by walking down the tree and comparing the contents of
> each directory. If a node in the DAG (directory or file) hasn't
> changed at all, it can be skipped without continuing down. The actual
> algorithm can be found in libsvn_repos/reporter.c; a simpler algorithm
> is in libsvn_repos/delta.c, but this isn't what we actually use (since
> it doesn't deal with things like mixed-revision working copies).

Just for the sake of accuracy, the reason we don't use libsvn_repos/delta.c
has nothing to do with its ability to be correct in a mixed-rev working copy
situation. (We used that code for quite a long time with mixed-rev working
copies before reporter.c's version ever came into being.) It has to do with
the fact that that code operates on versioned filesystem transactions and
revisions, and it was decided some time ago that it was silly to generate an
honest-to-goodness-yet-temporary Subversion repository transaction to
represent the state of the working copy when we could use a much more
efficient representation that lived outside the repository.

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

Received on Sat Dec 29 03:59:50 2007

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