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

RE: svn blame

From: Bill Tutt <rassilon_at_lyra.org>
Date: 2002-08-13 08:11:05 CEST

> From: Daniel Berlin [mailto:dberlin@dberlin.org]
> >
> > Why does your delta-window foo have _anything_ to do with this at
> You do understand how cvs annotate works, and of the diff format, no?
> If you did, it would be immediately clear why a delta-window that is a
> combination of delta windows would be a problem for cvs annotate.
> But let me spell it out for you:
> cvs annotate works by simply tracking, as it combines deltas, which
> came from which deltas (and thus, which lines came from which
> Our delta combiner currently does not.
> Thus, it is impossible, given a combined delta, to determine the
origin of
> a given line.
> Now, the statement that this poses a problem is not quite correct.
> The reason why is, however right.
> It's just as easy/hard to do annotate as it was before, you just do it
> a different place.
> The reason why annotate is difficult for us is because RCS uses a line
> based format, and svndiff is byte based, it is more difficult to
> And formatting is where the real work is. But the actual process of
> getting the data necessary for annoate is not really difficult.
> to associate it
> with lines is a bit tricky.
> But, anyway. Here's how stuff looks: Each revision's delta is simply
> linked, in the database, to the delta of the revision before it (In
> order to simplify getting all the deltas needed to generate a given
> revision).
> Thus, you have something that looks like (in the database. First
> element of the list is the key, second is the data, third is the
> link to another window or NULL.)
> (foo <delta data> bar)
> (bar <delta data> baz)
> (baz <delta data> NULL)
> Where you have a revision->delta mapping somewhere (for a given file)
> so:
> (1.3 foo)
> (1.2 bar)
> (1.1 baz)
> How to do annotate off this is quite clear, actually, with, or without
> delta combiner.
> Without a delta combiner, each delta would be applied seperately, but
> would have no idea, unless you looked, that revision 1.2 started when
> hit the delta window "bar".
> We don't know, or care about this, in order to get the text of
> 1.3, we just walk the windows.
> So, to show there's really no problem, and that the delta combiner
> make it easier or harder, ....
> Before, you would have to perform the following steps:
> 1. For each revision starting from 1, up to the revision we need to
> annotate to, grab the name of the delta window that starts that
> Make a nice mapping structure so that you can lookup "foo", and it'll
> "1.3"
> 2. As you apply deltas, and generate byte, each range of bytes
> gets marked with the revision number associated with that window (if
> If
> you don't find it in the map, it means it doesn't delineate a new
> revision, and we assign it the previous number), which we lookup.
> 3.Now you must transform the byte ranges into *lines*, so it looks
> This is done by looking at the actual content, and figuring out where
> line would break.
> Each line is assigned the newest revision that touches something on
> line.
> 4. Boom, yer dnone.
> With a delta combiner, it's the same first step, but the second step's
> tracking needs to be performed *in the delta combiner* (since now
> is what is effectively applying the deltas to generate a combined one,
> it just does so *without* actually executing the commands),
> or else, you have to avoid the delta combinator, and do step two.
> Doing it in the delta combiner depends on how exactly your combiner

Err, well yeah that works in theory. Heck, you can even start to come up
with rules about how such a thing might look like.

i.e. Delta(N) = Delta(Source, Delta(N-1), Target)

Where producing a Delta(N) that has byte range annotations on it
requires the DeltaOperations of the previous delta to help drive the
old/new decision making process necessary in something like svndiff that
copies from source. (For the moment ignore the copies against target,
because as the existing combiner proves, target compresses aren't
necessary, and are able to be transformed into source copies and new

However, IIRC, our svndiff format doesn't do a svndiff of an entire
file. If we did, our life would be so much easier. We do deltas of a
specific chunk sizes of the file. This is what I was referring to by
delta-window. Our current combiner code doesn't handle sliding
delta-windows (and it's not clear that it should) so adding three or
four odd bytes will end up marking some initial bytes of the next
delta-window incorrectly as new, when really it's delta-window

Have any ideas to help with that problem? If you do, I'm sure everybody
(me, Brane, Greg Hudson) a bunch of other folks would love to hear them.


To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Tue Aug 13 08:11:36 2002

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

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.