quoted
quoted
quoted
quoted
"DB" == Daniel Barkalow [off-list ref] writes:
DB> [perl script]
quoted
How does this work, and what do we do about merges?
DB> I've got that part, but I'm not clear on how the rename/copy and complete
DB> rewrite stuff works.
Rename/copy is simply about what files to use when comparing
between two trees. If you are tracking file F and find that a
commit created that file by renaming what was originally G, then
you compare old G and this F and assign blame for common lines
to the ancestor of that commit (that had those lines in G), and
take responsibility of the rest yourself (or assign blame for
them to other parents).
Rewrite is easier. If diff-tree -B says it is a complete
rewrite, instead of assigning blame for lines that you are the
current suspect to any of your parents, you take blame for all
of them yourself, without comparing the file with the parent to
assign blame line-by-line.
--- Junio C Hamano <junkio@cox.net> wrote:
quoted
quoted
quoted
quoted
quoted
"DB" == Daniel Barkalow [off-list ref] writes:
DB> [perl script]
quoted
quoted
How does this work, and what do we do about merges?
Checking diffs of all the parents can be computational expensive.
I'am developing a different alghoritm for qgit, where I know,
before to run annotate all the revs that changed a given file.
The revs are saved in the shaHist list according to git-rev-list --merge-order.
The algoritm operates form the oldest to the newst calculating annotation for each
following rev.
This alghoritm takes advantage of the fact that mostly revs belong to 2 categories:
1) revs of the same development-sequence (e.g. connected without merges)
2) empty merges, i.e. merges where the file we are interested in
is listed in only one merging branch
If a rev in shaHist does not belong to above categories a reach analisys must be performed
in order to find the direct ancestor among all the previous revs in the list.
So starting from shaHist a ReachList rl is populated by getReachability():
void Annotate::getReachability(ReachList& rl, const QString& file, const QStringList& shaHist) {
rl.clear();
QStringList::const_iterator it = shaHist.begin();
Rev* r = revLookup(*it);
rl.append(ReachInfo(*it, r->id, INITIAL));
for (it++; it != shaHist.end(); it++) {
Rev* r = revLookup(*it);
// initial revision case
if (r->parents.count() == 0) {
rl.append(ReachInfo(*it, r->id, INITIAL));
continue;
}
// merge case
if (r->parents.count() > 1) {
// check empty merges diffing against previous in list
QString prevSha = rl.last().sha;
QString d = getFileDiff(*it, prevSha, file);
if (d.isEmpty()) {
rl.append(ReachInfo(*it, r->id, EMPTY_MERGE));
rl.last().roots.append(prevSha);
} else {
// real merge: we need reach test.
QStringList roots;
roots.clear();
for (uint i = 0; i < r->parents.count(); i++) {
// here tree walking is performed
QString root = getRoot(r->parents[i], rl);
if (!root.isEmpty())
roots.append(root);
}
rl.append(ReachInfo(*it, r->id, MERGE));
rl.last().roots = roots;
}
}
continue;
}
// normal case: a revision with a single parent
if (r->id == rl.last().id) { // same development sequence
QString prevSha = rl.last().sha;
rl.append(ReachInfo(*it, r->id, SAME_BR)); // same branch
rl.last().roots.append(prevSha);
} else { // different development sequence
QString root = getRoot(*it, rl); // <-- here tree walking is performed
if (!root.isEmpty()) {
rl.append(ReachInfo(*it, r->id, DIFF_BR));
rl.last().roots.append(root);
} else
qDebug("ASSERT getReachability: rev %s not reachable",
(*it).latin1());
}
}
}
Then ReachList rl is then used to compute correct annotations:
void Annotate::run(const QString& file, const QStringList& shaHist, AnnotateHistory& ah) {
QString d, diffTarget;
QStringList t;
int pos;
ReachList rl;
ah.clear();
getReachability(rl, file, shaHist); // <-- here ReachList rl is calculated
for (uint i = 0; i < rl.count(); i++) {
switch(rl[i].type) { // <-- here ReachList rl is used to find annotations
case SAME_BR:
case DIFF_BR:
diffTarget = rl[i].roots.first();
d = getFileDiff(rl[i].sha, diffTarget, file);
pos = shaHist.findIndex(diffTarget);
ah.append(processDiff(d, ah[pos], getAuthor(rl[i].sha, shaHist)));
break;
case INITIAL:
pos = shaHist.findIndex(rl[i].sha);
ah.append(getFirstAnnotation(file, shaHist, pos));
break;
case EMPTY_MERGE:
diffTarget = rl[i].roots.first();
pos = shaHist.findIndex(diffTarget);
t = ah[pos]; // copy annotation from previous
ah.append(t);
break;
case MERGE:
// append annotation calculated on first root
diffTarget = rl[i].roots.first();
d = getFileDiff(rl[i].sha, diffTarget, file);
pos = shaHist.findIndex(diffTarget);
ah.append(processDiff(d, ah[pos], "Merge"));
// update annotation with all the others roots
for (uint j = 1; j < rl[i].roots.count(); j++) {
diffTarget = rl[i].roots[j];
d = getFileDiff(rl[i].sha, diffTarget, file);
pos = shaHist.findIndex(diffTarget);
// create an annotation calculated between root[i] and
// the merge.
QStringList scndAnn = processDiff(d, ah[pos],
getAuthor(diffTarget, shaHist));
// finally we unify the two annotations, so we catch
// also the case of a 3-way merge
unify(ah.last(), scndAnn);
}
break;
}
}
}
Advantage of this algorithm is that reach analisys, i.e. tree walking, is
done, statistically, only for a small subset of revs.
Another side benefit is that correct annotation is calculated for each rev and
not only for newest one.
Of course there are issues:
1) A ordered list of revs (file history) must be known in advance. This is not a problem
for qgit because file history is calculated while loading revs.
2) Does not takes in account file renames.
Hope this notes can help in ongoing discussion
Marco
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com