Fossil

Check-in [91af24e6]
Login

Check-in [91af24e6]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add the /doc/trunk/www/blame.wiki document briefly describing the algorithm used to compute "blame" in Fossil.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 91af24e6c942da9d2b7faa14443f7aad908ec182
User & Date: drh 2015-12-13 02:55:09
Context
2015-12-13
03:13
Fix one error and add an additional note to the article on the annotate algorithm. ... (check-in: 9828493c user: drh tags: trunk)
02:55
Add the /doc/trunk/www/blame.wiki document briefly describing the algorithm used to compute "blame" in Fossil. ... (check-in: 91af24e6 user: drh tags: trunk)
02:11
Enhance the /finfo webpage so that when it is showing the ancestors of a particular check-in, it only shows direct ancestors, the same as the /annotate and /blame pages. ... (check-in: f8db2c74 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Added www/blame.wiki.




















































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<title>The Annotate Algorithm</title>

<h2>1.0 Introduction</h2>

The [/help?cmd=annotate|fossil annotate],
[/help?cmd=blame|fossil blame], and
[/help?cmd=praise|fossil praise] commands, and the
[/help?cmd=/annotate|/annotate],
[/help?cmd=/blame|/blame], and
[/help?cmd=/praise|/praise] web pages are all used to show the most
recent check-in that modified each line of a particular file.
This article overviews the algorithm used to compute the annotation
for a file in Fossil.

<h2>2.0 Algorithm</h2>

<ol type='1'>
<li>Locate the check-in that contains the file that is to be
    annotated.  Call this check-in C0.
<li>Find all direct ancestors of C0.  A direct ancestor is the closure
    of the primary parent of C0.  Merged in branches are not part of
    the direct ancestors of C0.
<li>Prune the list of ancestors of C0 so that it contains only 
    check-in in which the file to be annotated was modified.
<li>Load the complete text of the file to be annotated from check-in C0.
    Call this version of the file F0.
<li>Parse F0 into lines.  Mark each line as "unchanged".
<li>For each ancestor of C0 on the pruned list (call the ancestor CX), 
    beginning with the most
    recent ancestor and moving toward the oldest ancestor, do the
    following steps:
<ol type='a'>
<li>Load the text for the file to be annotated as it existed in check-in CX.
    Call this text FX.
<li>Compute a diff going from FX to F0.
<li>For each line of F0 that is changed in the diff and which was previously
    marked "unchanged", update the mark to indicated that line
    was modified by CX.
</ol>
<li>Show each line of F0 together with its change mark, appropriately
    formatted.
</ol>

<h2>3.0 Discussion and Notes</h2>

The time-consuming part of this algorithm is step 6b - computing the
diff from all historical versions of the file to the version of the file
under analysis.  For a large file that has many historical changes, this
can take several seconds.  For this reason, the default 
[/help?cmd=/annotate|/annotate] webpage only shows those lines that where
changed by the 20 most recent modifications to the file.  This allows
the loop on step 6 to terminate after only 19 diffs instead of the hundreds
or thousands of diffs that might be required for a frequently modified file.

As currently implemented (2015-12-12) the annotate algorithm does not
follow files across name changes.  File name change information is 
available in the database, and so the algorithm could be enhanced to follow
files across name changes by modifications to step 2.
Changes to www/mkindex.tcl.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

15
16
17
18
19
20
21
#!/bin/sh
#
# Run this TCL script to generate a WIKI page that contains a
# permuted index of the various documentation files.
#
#    tclsh mkindex.tcl >permutedindex.html
#

set doclist {
  adding_code.wiki {Adding New Features To Fossil}
  adding_code.wiki {Hacking Fossil}
  antibot.wiki {Defense against Spiders and Bots}
  bugtheory.wiki {Bug Tracking In Fossil}
  branching.wiki {Branching, Forking, Merging, and Tagging}

  build.wiki {Compiling and Installing Fossil}
  checkin_names.wiki {Check-in And Version Names}
  checkin.wiki {Check-in Checklist}
  changes.wiki {Fossil Changelog}
  copyright-release.html {Contributor License Agreement}
  concepts.wiki {Fossil Core Concepts}
  contribute.wiki {Contributing Code or Documentation To The Fossil Project}












|

>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/bin/sh
#
# Run this TCL script to generate a WIKI page that contains a
# permuted index of the various documentation files.
#
#    tclsh mkindex.tcl >permutedindex.html
#

set doclist {
  adding_code.wiki {Adding New Features To Fossil}
  adding_code.wiki {Hacking Fossil}
  antibot.wiki {Defense against Spiders and Bots}
  blame.wiki {The Annotate/Blame Algorithm Of Fossil}
  branching.wiki {Branching, Forking, Merging, and Tagging}
  bugtheory.wiki {Bug Tracking In Fossil}
  build.wiki {Compiling and Installing Fossil}
  checkin_names.wiki {Check-in And Version Names}
  checkin.wiki {Check-in Checklist}
  changes.wiki {Fossil Changelog}
  copyright-release.html {Contributor License Agreement}
  concepts.wiki {Fossil Core Concepts}
  contribute.wiki {Contributing Code or Documentation To The Fossil Project}
Changes to www/permutedindex.html.
22
23
24
25
26
27
28


29
30
31
32
33
34
35
<li><a href="fiveminutes.wiki">5 Minutes as a Single User &mdash; Update and Running in</a></li>
<li><a href="fossil-from-msvc.wiki">2010 IDE &mdash; Integrating Fossil in the Microsoft Express</a></li>
<li><a href="tech_overview.wiki">A Technical Overview Of The Design And Implementation Of Fossil</a></li>
<li><a href="adding_code.wiki">Adding New Features To Fossil</a></li>
<li><a href="antibot.wiki">against Spiders and Bots &mdash; Defense</a></li>
<li><a href="copyright-release.html">Agreement &mdash; Contributor License</a></li>
<li><a href="delta_encoder_algorithm.wiki">Algorithm &mdash; Fossil Delta Encoding</a></li>


<li><a href="customskin.md">Appearance of Web Pages &mdash; Theming: Customizing The</a></li>
<li><a href="fiveminutes.wiki">as a Single User &mdash; Update and Running in 5 Minutes</a></li>
<li><a href="faq.wiki">Asked Questions &mdash; Frequently</a></li>
<li><a href="password.wiki">Authentication &mdash; Password Management And</a></li>
<li><a href="antibot.wiki">Bots &mdash; Defense against Spiders and</a></li>
<li><a href="private.wiki">Branches &mdash; Creating, Syncing, and Deleting Private</a></li>
<li><a href="branching.wiki">Branching, Forking, Merging, and Tagging</a></li>







>
>







22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<li><a href="fiveminutes.wiki">5 Minutes as a Single User &mdash; Update and Running in</a></li>
<li><a href="fossil-from-msvc.wiki">2010 IDE &mdash; Integrating Fossil in the Microsoft Express</a></li>
<li><a href="tech_overview.wiki">A Technical Overview Of The Design And Implementation Of Fossil</a></li>
<li><a href="adding_code.wiki">Adding New Features To Fossil</a></li>
<li><a href="antibot.wiki">against Spiders and Bots &mdash; Defense</a></li>
<li><a href="copyright-release.html">Agreement &mdash; Contributor License</a></li>
<li><a href="delta_encoder_algorithm.wiki">Algorithm &mdash; Fossil Delta Encoding</a></li>
<li><a href="blame.wiki">Algorithm Of Fossil &mdash; The Annotate/Blame</a></li>
<li><a href="blame.wiki">Annotate/Blame Algorithm Of Fossil &mdash; The</a></li>
<li><a href="customskin.md">Appearance of Web Pages &mdash; Theming: Customizing The</a></li>
<li><a href="fiveminutes.wiki">as a Single User &mdash; Update and Running in 5 Minutes</a></li>
<li><a href="faq.wiki">Asked Questions &mdash; Frequently</a></li>
<li><a href="password.wiki">Authentication &mdash; Password Management And</a></li>
<li><a href="antibot.wiki">Bots &mdash; Defense against Spiders and</a></li>
<li><a href="private.wiki">Branches &mdash; Creating, Syncing, and Deleting Private</a></li>
<li><a href="branching.wiki">Branching, Forking, Merging, and Tagging</a></li>
170
171
172
173
174
175
176

177
178
179
180
181
182
183
<li><a href="private.wiki">Syncing, and Deleting Private Branches &mdash; Creating,</a></li>
<li><a href="custom_ticket.wiki">System &mdash; Customizing The Ticket</a></li>
<li><a href="tickets.wiki">System &mdash; The Fossil Ticket</a></li>
<li><a href="branching.wiki">Tagging &mdash; Branching, Forking, Merging, and</a></li>
<li><a href="tech_overview.wiki">Technical Overview Of The Design And Implementation Of Fossil &mdash; A</a></li>
<li><a href="../test/release-checklist.wiki">Testing Checklist &mdash; Pre-Release</a></li>
<li><a href="th1.md">TH1 Scripting Language &mdash; The</a></li>

<li><a href="makefile.wiki">The Fossil Build Process</a></li>
<li><a href="sync.wiki">The Fossil Sync Protocol</a></li>
<li><a href="tickets.wiki">The Fossil Ticket System</a></li>
<li><a href="webui.wiki">The Fossil Web Interface</a></li>
<li><a href="th1.md">The TH1 Scripting Language</a></li>
<li><a href="customskin.md">Theming: Customizing The Appearance of Web Pages</a></li>
<li><a href="customgraph.md">Theming: Customizing the Timeline Graph</a></li>







>







172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
<li><a href="private.wiki">Syncing, and Deleting Private Branches &mdash; Creating,</a></li>
<li><a href="custom_ticket.wiki">System &mdash; Customizing The Ticket</a></li>
<li><a href="tickets.wiki">System &mdash; The Fossil Ticket</a></li>
<li><a href="branching.wiki">Tagging &mdash; Branching, Forking, Merging, and</a></li>
<li><a href="tech_overview.wiki">Technical Overview Of The Design And Implementation Of Fossil &mdash; A</a></li>
<li><a href="../test/release-checklist.wiki">Testing Checklist &mdash; Pre-Release</a></li>
<li><a href="th1.md">TH1 Scripting Language &mdash; The</a></li>
<li><a href="blame.wiki">The Annotate/Blame Algorithm Of Fossil</a></li>
<li><a href="makefile.wiki">The Fossil Build Process</a></li>
<li><a href="sync.wiki">The Fossil Sync Protocol</a></li>
<li><a href="tickets.wiki">The Fossil Ticket System</a></li>
<li><a href="webui.wiki">The Fossil Web Interface</a></li>
<li><a href="th1.md">The TH1 Scripting Language</a></li>
<li><a href="customskin.md">Theming: Customizing The Appearance of Web Pages</a></li>
<li><a href="customgraph.md">Theming: Customizing the Timeline Graph</a></li>