/*
** 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);
}
}