initial commitHEADmaster

1 files changed, 205 insertions, 0 deletions

diff --git a/src/pivot.c b/src/pivot.c
new file mode 100644
index 0000000..a7b21c5
--- /dev/null
+++ b/src/pivot.c
@@ -0,0 +1,205 @@
+/*
+** Copyright (c) 2007 D. Richard Hipp
+**
+** This program is free software; you can redistribute it and/or
+** modify it under the terms of the Simplified BSD License (also
+** known as the "2-Clause License" or "FreeBSD License".)
+
+** This program is distributed in the hope that it will be useful,
+** but without any warranty; without even the implied warranty of
+** merchantability or fitness for a particular purpose.
+**
+** Author contact information:
+**   drh@hwaci.com
+**   http://www.hwaci.com/drh/
+**
+*******************************************************************************
+**
+** This file contains code used to find the most recent common
+** ancestor of time versions of the same file.  We call this
+** common ancestor the "pivot" in a 3-way merge.
+*/
+#include "config.h"
+#include "pivot.h"
+#include <assert.h>
+
+
+/*
+** Set the primary file.  The primary version is one of the two
+** files that have a common ancestor.  The other file is the secondary.
+** There can be multiple secondaries but only a single primary.
+** The primary must be set first.
+**
+** In the merge algorithm, the file being merged in is the primary.
+** The current check-out or other files that have been merged into
+** the current check-out are the secondaries.
+**
+** The act of setting the primary resets the pivot-finding algorithm.
+*/
+void pivot_set_primary(int rid){
+  /* Set up table used to do the search */
+  db_multi_exec(
+    "CREATE TEMP TABLE IF NOT EXISTS aqueue("
+    "  rid INTEGER,"              /* The record id for this version */
+    "  mtime REAL,"               /* Time when this version was created */
+    "  pending BOOLEAN,"          /* True if we have not check this one yet */
+    "  src BOOLEAN,"               /* 1 for primary.  0 for others */
+    "  PRIMARY KEY(rid,src)"
+    ") WITHOUT ROWID;"
+    "DELETE FROM aqueue;"
+    "CREATE INDEX IF NOT EXISTS aqueue_idx1 ON aqueue(pending, mtime);"
+  );
+
+  /* Insert the primary record */
+  db_multi_exec(
+    "INSERT INTO aqueue(rid, mtime, pending, src)"
+    "  SELECT %d, mtime, 1, 1 FROM event WHERE objid=%d AND type='ci' LIMIT 1",
+    rid, rid
+  );
+}
+
+/*
+** Set a secondary file.  The primary file must be set first.  There
+** must be at least one secondary but there can be more than one if
+** desired.
+*/
+void pivot_set_secondary(int rid){
+  /* Insert the secondary record */
+  db_multi_exec(
+    "INSERT OR IGNORE INTO aqueue(rid, mtime, pending, src)"
+    "  SELECT %d, mtime, 1, 0 FROM event WHERE objid=%d AND type='ci'",
+    rid, rid
+  );
+}
+
+/*
+** Find the most recent common ancestor of the primary and one of
+** the secondaries.  Return its rid.  Return 0 if no common ancestor
+** can be found.
+**
+** If ignoreMerges is true, follow only "primary" parent links.
+*/
+int pivot_find(int ignoreMerges){
+  Stmt q1, q2, u1, i1;
+  int rid = 0;
+
+  /* aqueue must contain at least one primary and one other.  Otherwise
+  ** we abort early
+  */
+  if( db_int(0, "SELECT count(distinct src) FROM aqueue")<2 ){
+    fossil_fatal("lack both primary and secondary files");
+  }
+
+  /* Prepare queries we will be needing
+  **
+  ** The first query finds the oldest pending version on the aqueue.  This
+  ** will be next one searched.
+  */
+  db_prepare(&q1, "SELECT rid FROM aqueue WHERE pending"
+                  " ORDER BY pending DESC, mtime DESC");
+
+  /* Check to see if the record :rid is a common ancestor.  The result
+  ** set contains one or more rows if it is and is the empty set if it
+  ** is not.
+  */
+  db_prepare(&q2,
+    "SELECT 1 FROM aqueue A, plink, aqueue B"
+    " WHERE plink.pid=:rid"
+    "   AND plink.cid=B.rid"
+    "   AND A.rid=:rid"
+    "   AND A.src!=B.src %s",
+    ignoreMerges ? "AND plink.isprim" : ""
+  );
+
+  /* Mark the :rid record has having been checked.  It is not the
+  ** common ancestor.
+  */
+  db_prepare(&u1,
+    "UPDATE aqueue SET pending=0 WHERE rid=:rid"
+  );
+
+  /* Add to the queue all ancestors of :rid.
+  */
+  db_prepare(&i1,
+    "REPLACE INTO aqueue "
+    "SELECT plink.pid,"
+    "       coalesce((SELECT mtime FROM event X WHERE X.objid=plink.pid), 0.0),"
+    "       1,"
+    "       aqueue.src "
+    "  FROM plink, aqueue"
+    " WHERE plink.cid=:rid"
+    "   AND aqueue.rid=:rid %s",
+    ignoreMerges ? "AND plink.isprim" : ""
+  );
+
+  while( db_step(&q1)==SQLITE_ROW ){
+    rid = db_column_int(&q1, 0);
+    db_reset(&q1);
+    db_bind_int(&q2, ":rid", rid);
+    if( db_step(&q2)==SQLITE_ROW ){
+       break;
+    }
+    db_reset(&q2);
+    db_bind_int(&i1, ":rid", rid);
+    db_exec(&i1);
+    db_bind_int(&u1, ":rid", rid);
+    db_exec(&u1);
+    rid = 0;
+  }
+  db_finalize(&q1);
+  db_finalize(&q2);
+  db_finalize(&i1);
+  db_finalize(&u1);
+  return rid;
+}
+
+/*
+** COMMAND: merge-base
+**
+** Usage: %fossil merge-base ?options? PRIMARY SECONDARY ...
+**
+** Find a common ancestor given two or more check-in versions to
+** hypothetically merge.
+**
+** Options:
+**    --ignore-merges       Ignore merges for discovering name pivots
+*/
+void merge_base_cmd(void){
+  int i, rid;
+  int ignoreMerges = find_option("ignore-merges",0,0)!=0;
+  int showDetails = find_option("details",0,0)!=0
+    /* intentionally undocumented */;
+  if( g.argc<4 ){
+    usage("?options? PRIMARY SECONDARY ...");
+  }
+  db_must_be_within_tree();
+  pivot_set_primary(name_to_rid(g.argv[2]));
+  for(i=3; i<g.argc; i++){
+    pivot_set_secondary(name_to_rid(g.argv[i]));
+  }
+  rid = pivot_find(ignoreMerges);
+  if( rid==0 ){
+    puts("No common ancestor found.");
+  }else{
+    printf("pivot=%s\n",
+           db_text("?","SELECT uuid FROM blob WHERE rid=%d",rid));
+  }
+  if( showDetails ){
+    Stmt q;
+    db_prepare(&q,
+      "SELECT substr(uuid,1,12), aqueue.rid, datetime(aqueue.mtime),"
+             " aqueue.pending, aqueue.src\n"
+      "  FROM aqueue JOIN blob ON aqueue.rid=blob.rid\n"
+      " ORDER BY aqueue.mtime DESC"
+    );
+    while( db_step(&q)==SQLITE_ROW ){
+      printf("\"%s\",%d,\"%s\",%d,%d\n",
+        db_column_text(&q, 0),
+        db_column_int(&q, 1),
+        db_column_text(&q, 2),
+        db_column_int(&q, 3),
+        db_column_int(&q, 4));
+    }
+    db_finalize(&q);
+  }
+}