--- Junio C Hamano <[EMAIL PROTECTED]> wrote:
> >>>>> "DB" == Daniel Barkalow <[EMAIL PROTECTED]> writes:
>
> DB> [perl script]
>
> >> 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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
