Infer some copy sources as additional parents

We use a literal meaning of multiple commit parents to allow us to infer
some partial repository copying as merges.  This helps us

  1) track history despite some directory reorganization
  2) link subset commits to parents
  3) infer some merges which were achieved by overwriting
     a subtree with contents from another branch

This seems to work well enough even with cvs2svn monster commits.  The
heuristics have been tuned by gut feel to work reasonably well with mono's
SVN repository. They can definitely be improved.

3 files changed, 130 insertions, 54 deletions

diff --git a/src/repository.cpp b/src/repository.cpp
index e31cf23..6758f5c 100644
--- a/src/repository.cpp
+++ b/src/repository.cpp
@@ -330,6 +330,34 @@ void Repository::Transaction::setLog(const QByteArray &l)
     log = l;
 }
 
+void Repository::Transaction::noteCopyFromBranch (const QString &branchFrom, int branchRevNum)
+{
+    Branch &brFrom = repository->branches[branchFrom];
+    if (!brFrom.created) {
+        qWarning() << branch << "is copying from branch" << branchFrom
+                    << "but the latter doesn't exist.  Continuing, assuming the files exist.";
+	return;
+    }
+
+    int closestCommit = branchRevNum;
+    if (branchRevNum != brFrom.commits.last()) {
+        QVector<int>::const_iterator it = qUpperBound(brFrom.commits, branchRevNum);
+        closestCommit = it == brFrom.commits.begin() ? branchRevNum : *--it;
+    }
+
+    if (!repository->commitMarks.contains(closestCommit)) {
+	qWarning() << "Unknown revision r" << QByteArray::number(closestCommit)
+		   << ".  Continuing, assuming the files exist.";
+	return;
+    }
+
+    qWarning() << "repository " + repository->name + " branch " + branch + " has some files copied from " + branchFrom + "@" + QByteArray::number(branchRevNum);
+
+    int mark = repository->commitMarks[closestCommit];
+    if (!merges.contains(mark))
+	merges.append(mark);
+}
+
 void Repository::Transaction::deleteFile(const QString &path)
 {
     QString pathNoSlash = path;
@@ -376,6 +404,17 @@ void Repository::Transaction::commit()
     if (CommandLineParser::instance()->contains("add-metadata"))
         message += "\nsvn path=" + svnprefix + "; revision=" + QByteArray::number(revnum) + "\n";
 
+    int parentmark = 0;
+    Branch &br = repository->branches[branch];
+    if (br.created) {
+	parentmark = repository->commitMarks[br.commits.last()];
+    } else {
+	qWarning() << "Branch" << branch << "in repository" << repository->name << "doesn't exist at revision"
+		   << revnum << "-- did you resume from the wrong revision?";
+	br.created = revnum;
+    }
+    br.commits.append(revnum);
+
     {
         QByteArray branchRef = branch;
         if (!branchRef.startsWith("refs/"))
@@ -387,20 +426,35 @@ void Repository::Transaction::commit()
         repository->commitMarks.insert(revnum, mark);
         s << "committer " << QString::fromUtf8(author) << ' ' << datetime << " -0000" << endl;
 
-        Branch &br = repository->branches[branch];
-        if (!br.created) {
-            qWarning() << "Branch" << branch << "in repository" << repository->name << "doesn't exist at revision"
-                       << revnum << "-- did you resume from the wrong revision?";
-            br.created = revnum;
-        }
-	br.commits.append(revnum);
-
         s << "data " << message.length() << endl;
     }
 
     repository->fastImport.write(message);
     repository->fastImport.putChar('\n');
 
+    // note some of the inferred merges
+    QByteArray desc = "";
+    int i = 0;
+    foreach (int merge, merges) {
+	if (merge == parentmark)
+	    continue;
+
+	// FIXME: options:
+	//   (1) ignore the 15 merges limit
+	//   (2) don't emit more than 15 merges
+	//   (3) create another commit on branch to soak up additional parents
+	// we've chosen option (2) for now, since only artificial commits
+	// created by cvs2svn seem to have this issue
+	if (++i >= 16) {
+	    qWarning() << "too many merge parents";
+	    break;
+	}
+
+	QByteArray m = " :" + QByteArray::number(merge);
+	desc += m;
+	repository->fastImport.write("merge" + m + "\n");
+    }
+
     // write the file deletions
     if (deletedFiles.contains(""))
         repository->fastImport.write("deleteall\n");
@@ -413,7 +467,7 @@ void Repository::Transaction::commit()
 
     repository->fastImport.write("\nprogress SVN r" + QByteArray::number(revnum)
                                  + " branch " + branch + " = :" + QByteArray::number(mark)
-				 /*+ " # Commit #" + QByteArray::number(repository->commitCount)*/
+				 + (desc.isEmpty() ? "" : " # merge from") + desc
 				 + "\n\n");
     printf(" %d modifications from SVN %s to %s/%s",
            deletedFiles.count() + modifiedFiles.count(), svnprefix.data(),
diff --git a/src/repository.h b/src/repository.h
index 3df9d9a..020e1f6 100644
--- a/src/repository.h
+++ b/src/repository.h
@@ -40,6 +40,8 @@ public:
         uint datetime;
         int revnum;
 
+	QVector<int> merges;
+
         QStringList deletedFiles;
         QByteArray modifiedFiles;
 
@@ -52,6 +54,8 @@ public:
         void setDateTime(uint dt);
         void setLog(const QByteArray &log);
 
+	void noteCopyFromBranch (const QString &prevbranch, int revFrom);
+
         void deleteFile(const QString &path);
         QIODevice *addFile(const QString &path, int mode, qint64 length);
     };
diff --git a/src/svn.cpp b/src/svn.cpp
index a4bf4e6..afb037e 100644
--- a/src/svn.cpp
+++ b/src/svn.cpp
@@ -595,56 +595,61 @@ int SvnRevision::exportInternal(const char *key, const svn_fs_path_change_t *cha
 //                qDebug() << "   " << qPrintable(current) << "rev" << revnum << "->"
 //                         << qPrintable(repository) << qPrintable(branch) << qPrintable(path);
 
-    if (path.isEmpty() && path_from != NULL) {
-        QString previous = QString::fromUtf8(path_from) + '/';
+    QString previous;
+    QString prevsvnprefix, prevrepository, prevbranch, prevpath;
+
+    if (path_from != NULL) {
+	QString previous = QString::fromUtf8(path_from) + '/';
         MatchRuleList::ConstIterator prevmatch =
             findMatchRule(matchRules, rev_from, previous, NoIgnoreRule);
-        if (prevmatch != matchRules.constEnd()) {
-            QString prevsvnprefix, prevrepository, prevbranch, prevpath;
+        if (prevmatch != matchRules.constEnd())
             splitPathName(*prevmatch, previous, &prevsvnprefix, &prevrepository,
                           &prevbranch, &prevpath);
+	else
+	    path_from = NULL;
+    }
 
-            if (!prevpath.isEmpty()) {
-                qDebug() << qPrintable(current) << "is a partial branch of repository"
-                         << qPrintable(prevrepository) << "branch"
-                         << qPrintable(prevbranch) << "subdir"
-                         << qPrintable(prevpath);
-            } else if (prevrepository != repository) {
-                qWarning() << qPrintable(current) << "rev" << revnum
-                           << "is a cross-repository copy (from repository"
-                           << qPrintable(prevrepository) << "branch"
-                           << qPrintable(prevbranch) << "path"
-                           << qPrintable(prevpath) << "rev" << rev_from << ")";
-            } else {
-		if (prevbranch == branch) {
-		    // same branch and same repository
-		    qDebug() << qPrintable(current) << "rev" << revnum
-			     << "is an SVN rename from"
-			     << qPrintable(previous) << "rev" << rev_from;
-		} else {
-		    // same repository but not same branch
-		    // this means this is a plain branch
-		    qDebug() << qPrintable(repository) << ": branch"
-			     << qPrintable(branch) << "is branching from"
-			     << qPrintable(prevbranch);
-		}
-                Repository *repo = repositories.value(repository, 0);
-                if (!repo) {
-                    qCritical() << "Rule" << rule
-                                << "references unknown repository" << repository;
-                    return EXIT_FAILURE;
-                }
-
-                repo->createBranch(branch, revnum, prevbranch, rev_from);
-                if (rule.annotate) {
-                    // create an annotated tag
-                    fetchRevProps();
-                    repo->createAnnotatedTag(branch, svnprefix, revnum, authorident,
-                                             epoch, log);
-                }
-                return EXIT_SUCCESS;
-            }
-        }
+    if (path.isEmpty() && path_from != NULL) {
+	if (!prevpath.isEmpty()) {
+	    qDebug() << qPrintable(current) << "is a partial branch of repository"
+		     << qPrintable(prevrepository) << "branch"
+		     << qPrintable(prevbranch) << "subdir"
+		     << qPrintable(prevpath);
+	} else if (prevrepository != repository) {
+	    qWarning() << qPrintable(current) << "rev" << revnum
+		       << "is a cross-repository copy (from repository"
+		       << qPrintable(prevrepository) << "branch"
+		       << qPrintable(prevbranch) << "path"
+		       << qPrintable(prevpath) << "rev" << rev_from << ")";
+	} else {
+	    if (prevbranch == branch) {
+		// same branch and same repository
+		qDebug() << qPrintable(current) << "rev" << revnum
+			 << "is an SVN rename from"
+			 << qPrintable(previous) << "rev" << rev_from;
+	    } else {
+		// same repository but not same branch
+		// this means this is a plain branch
+		qDebug() << qPrintable(repository) << ": branch"
+			 << qPrintable(branch) << "is branching from"
+			 << qPrintable(prevbranch);
+	    }
+	    Repository *repo = repositories.value(repository, 0);
+	    if (!repo) {
+		qCritical() << "Rule" << rule
+			    << "references unknown repository" << repository;
+		return EXIT_FAILURE;
+	    }
+
+	    repo->createBranch(branch, revnum, prevbranch, rev_from);
+	    if (rule.annotate) {
+		// create an annotated tag
+		fetchRevProps();
+		repo->createAnnotatedTag(branch, svnprefix, revnum, authorident,
+					 epoch, log);
+	    }
+	    return EXIT_SUCCESS;
+	}
     }
 
     Repository::Transaction *txn = transactions.value(repository + branch, 0);
@@ -663,6 +668,19 @@ int SvnRevision::exportInternal(const char *key, const svn_fs_path_change_t *cha
         transactions.insert(repository + branch, txn);
     }
 
+    //
+    // If this path was copied from elsewhere, use it to infer _some_
+    // merge points.  However, if the copy was from earlier in the
+    // same branch, we ignore it, since it is unlikely to improve the
+    // quality of the history.
+    //
+    // This is totally a heuristic, but is fairly useful for tracking
+    // changes across directory re-organizations and wholesale branch
+    // imports.
+    //
+    if (path_from != NULL && prevrepository == repository && prevbranch != branch)
+	txn->noteCopyFromBranch (prevbranch, rev_from);
+
     if (change->change_kind == svn_fs_path_change_replace && path_from == NULL)
         txn->deleteFile(path);
     if (change->change_kind == svn_fs_path_change_delete) {