Re: Last mile for 1.0 again

--- Junio C Hamano <junkio@cox.net> wrote:

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