|
1
|
<title>The Annotate Algorithm</title> |
|
2
|
|
|
3
|
<h2>1.0 Introduction</h2> |
|
4
|
|
|
5
|
The [/help/annotate|fossil annotate], |
|
6
|
[/help/blame|fossil blame], and |
|
7
|
[/help/praise|fossil praise] commands, and the |
|
8
|
[/help/www/annotate|/annotate], |
|
9
|
[/help/www/blame|/blame], and |
|
10
|
[/help/www/praise|/praise] web pages are all used to show the most |
|
11
|
recent check-in that modified each line of a particular file. |
|
12
|
This article overviews the algorithm used to compute the annotation |
|
13
|
for a file in Fossil. |
|
14
|
|
|
15
|
<h2>2.0 Algorithm</h2> |
|
16
|
|
|
17
|
<ol type='1'> |
|
18
|
<li>Locate the check-in that contains the file that is to be |
|
19
|
annotated. Call this check-in C0. |
|
20
|
<li>Find all direct ancestors of C0. A direct ancestor is the closure |
|
21
|
of the primary parent of C0. Merged in branches are not part of |
|
22
|
the direct ancestors of C0. |
|
23
|
<li>Prune the list of ancestors of C0 so that it contains only |
|
24
|
check-ins in which the file to be annotated was modified. |
|
25
|
<li>Load the complete text of the file to be annotated from check-in C0. |
|
26
|
Call this version of the file F0. |
|
27
|
<li>Parse F0 into lines. Mark each line as "unchanged". |
|
28
|
<li>For each ancestor of C0 on the pruned list (call the ancestor CX), |
|
29
|
beginning with the most |
|
30
|
recent ancestor and moving toward the oldest ancestor, do the |
|
31
|
following steps: |
|
32
|
<ol type='a'> |
|
33
|
<li>Load the text for the file to be annotated as it existed in check-in CX. |
|
34
|
Call this text FX. |
|
35
|
<li>Compute a diff going from FX to F0. |
|
36
|
<li>For each line of F0 that is changed in the diff and which was previously |
|
37
|
marked "unchanged", update the mark to indicated that line |
|
38
|
was modified by CX. |
|
39
|
</ol> |
|
40
|
<li>Show each line of F0 together with its change mark, appropriately |
|
41
|
formatted. |
|
42
|
</ol> |
|
43
|
|
|
44
|
<h2>3.0 Discussion and Notes</h2> |
|
45
|
|
|
46
|
The time-consuming part of this algorithm is step 6b - computing the |
|
47
|
diff from all historical versions of the file to the version of the file |
|
48
|
under analysis. For a large file that has many historical changes, this |
|
49
|
can take several seconds. For this reason, the default |
|
50
|
[/help/www/annotate|/annotate] webpage only shows those lines that were |
|
51
|
changed by the 20 most recent modifications to the file. This allows |
|
52
|
the loop on step 6 to terminate after only 19 diffs instead of the hundreds |
|
53
|
or thousands of diffs that might be required for a frequently modified file. |
|
54
|
|
|
55
|
As currently implemented (as of 2015-12-12) the annotate algorithm does not |
|
56
|
follow files across name changes. File name change information is |
|
57
|
available in the database, and so the algorithm could be enhanced to follow |
|
58
|
files across name changes by modifications to step 3. |
|
59
|
|
|
60
|
Step 2 is interesting in that it is |
|
61
|
[/artifact/6cb824a0417?ln=196-201 | implemented] using a |
|
62
|
[https://www.sqlite.org/lang_with.html#recursivecte|recursive common table expression]. |
|
63
|
|