--- 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 
following rev.

This alghoritm takes advantage of the fact that mostly revs belong to 2 

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) {

        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));
                // 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));
                        } else {
                                // real merge: we need reach test.
                                QStringList roots;
                                for (uint i = 0; i < r->parents.count(); i++) {

                                        // here tree walking is performed
                                        QString root = getRoot(r->parents[i], 
                                        if (!root.isEmpty())
                                rl.append(ReachInfo(*it, r->id, MERGE));
                                rl.last().roots = roots;
                // 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 

                } 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));
                        } else
                                qDebug("ASSERT getReachability: rev %s not 

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;

        getReachability(rl, file, shaHist);  // <-- here ReachList rl is 

        for (uint i = 0; i < rl.count(); i++) {

                switch(rl[i].type) { // <-- here ReachList rl is used to find 

                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, 
                case INITIAL:
                        pos = shaHist.findIndex(rl[i].sha);
                        ah.append(getFirstAnnotation(file, shaHist, pos));
                case EMPTY_MERGE:
                        diffTarget = rl[i].roots.first();
                        pos = shaHist.findIndex(diffTarget);
                        t = ah[pos]; // copy annotation from previous
                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],

                                // finally we unify the two annotations, so we 
                                // also the case of a 3-way merge
                                unify(ah.last(), scndAnn);

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


Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
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

Reply via email to