/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/*
Copyright 2013-2021 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt
SPDX-License-Identifier: BSD-2-Clause-FreeBSD
SPDX-FileCopyrightText: 2021 The Libfossil Authors
SPDX-ArtifactOfProjectName: Libfossil
SPDX-FileType: Code
Heavily indebted to the Fossil SCM project (https://fossil-scm.org).
*/
/**********************************************************************
This file contains routines related to working with "paths" through
Fossil SCM version history.
*/
#include "fossil-scm/internal.h"
#include "fossil-scm/vpath.h"
#include <assert.h>
/* Only for debugging */
#include <stdio.h>
#define MARKER(pfexp) \
do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__); \
printf pfexp; \
} while(0)
static const fsl_vpath_node fsl_vpath_node_empty = {0,0,0,0,0,{0},0};
const fsl_vpath fsl_vpath_empty = fsl_vpath_empty_m;
void fsl_vpath_clear(fsl_vpath *path){
fsl_vpath_node * p;
while(path->pAll){
p = path->pAll;
path->pAll = p->pAll;
fsl_free(p);
}
fsl_id_bag_clear(&path->seen);
*path = fsl_vpath_empty;
}
fsl_vpath_node * fsl_vpath_first(fsl_vpath *p){
return p->pStart;
}
fsl_vpath_node * fsl_vpath_last(fsl_vpath *p){
return p->pEnd;
}
int fsl_vpath_length(fsl_vpath const * p){
return p->nStep;
}
fsl_vpath_node * fsl_vpath_next(fsl_vpath_node *p){
return p->u.pTo;
}
fsl_vpath_node * fsl_vpath_midpoint(fsl_vpath * path){
if( path->nStep<2 ) return 0;
else{
fsl_vpath_node *p;
int i;
int const max = path->nStep/2;
for(p=path->pEnd, i=0; p && i<max; p=p->pFrom, i++){}
return p;
}
}
void fsl_vpath_reverse(fsl_vpath * path){
fsl_vpath_node *p;
assert( path->pEnd!=0 );
for(p=path->pEnd; p && p->pFrom; p = p->pFrom){
p->pFrom->u.pTo = p;
}
path->pEnd->u.pTo = 0;
assert( p==path->pStart );
}
/**
Adds a new node to path and returns it. Returns 0 on allocation error.
path must not be 0. rid must be greater than 0. pFrom may be 0. If
pFrom is not 0 then isParent must be true if pFrom is a parent of
rid.
On success, sets the returned node as path->pCurrent, sets its
pFrom to the given pFrom, and sets rc->u.pPeer to the prior
path->pCurrent value.
*/
static fsl_vpath_node * fsl_vpath_new_node(fsl_vpath * path, fsl_id_t rid,
fsl_vpath_node * pFrom, bool isParent){
fsl_vpath_node * rc = 0;
assert(path);
assert(rid>0);
if(0 != fsl_id_bag_insert(&path->seen, rid)) return 0;
rc = (fsl_vpath_node*)fsl_malloc(sizeof(fsl_vpath_node));
if(!rc){
fsl_id_bag_remove(&path->seen, rid);
return 0;
}
*rc = fsl_vpath_node_empty;
rc->rid = rid;
rc->fromIsParent = pFrom ? isParent : 0;
rc->pFrom = pFrom;
rc->u.pPeer = path->pCurrent;
path->pCurrent = rc;
rc->pAll = path->pAll;
path->pAll = rc;
return rc;
}
int fsl_vpath_shortest( fsl_cx * const f, fsl_vpath * const path,
fsl_id_t iFrom, fsl_id_t iTo,
bool directOnly, bool oneWayOnly ){
fsl_stmt s = fsl_stmt_empty;
fsl_db * db = fsl_needs_repo(f);
int rc = 0;
fsl_vpath_node * pPrev;
fsl_vpath_node * p;
assert(db);
if(!db) return FSL_RC_NOT_A_REPO;
else if(iFrom<=0){
return fsl_cx_err_set(f, FSL_RC_RANGE,
"Invalid 'from' RID: %d", (int)iFrom);
}else if(iTo<=0){
/*
Possible TODO: if iTo==0, use... what? Checkout? Tip of current
checkout branch? Trunk? The multitude of options make it impossible
to decide :/.
*/
return fsl_cx_err_set(f, FSL_RC_RANGE,
"Invalid 'to' RID: %d", (int)iTo);
}
fsl_vpath_clear(path);
path->pStart = fsl_vpath_new_node(path, iFrom, 0, 0);
if(!path->pStart){
return fsl_cx_err_set(f, FSL_RC_OOM, 0);
}
if( iTo == iFrom ){
path->pEnd = path->pStart;
return 0;
}
if( oneWayOnly ){
if(directOnly){
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1 AND isprim");
}else{
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1");
}
}else if( directOnly ){
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1 AND isprim "
"UNION ALL "
"SELECT pid, 0 FROM plink WHERE cid=?1 AND isprim");
}else{
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1 "
"UNION ALL "
"SELECT pid, 0 FROM plink WHERE cid=?1");
}
if(rc){
fsl_cx_uplift_db_error(f, db);
assert(f->error.code);
goto end;
}
while(path->pCurrent){
++path->nStep;
pPrev = path->pCurrent;
path->pCurrent = 0;
while( pPrev ){
rc = fsl_stmt_bind_id(&s, 1, pPrev->rid);
assert(0==rc);
while( FSL_RC_STEP_ROW == fsl_stmt_step(&s) ){
fsl_id_t const cid = fsl_stmt_g_id(&s, 0);
int const isParent = fsl_stmt_g_int32(&s, 1);
assert((cid>0) && "fsl_id_bag_find() asserts this.");
if( fsl_id_bag_contains(&path->seen, cid) ) continue;
p = fsl_vpath_new_node(path, cid, pPrev, isParent ? 1 : 0);
if(!p){
rc = fsl_cx_err_set(f, FSL_RC_OOM, 0);
goto end;
}
if( cid == iTo ){
fsl_stmt_finalize(&s);
path->pEnd = p;
fsl_vpath_reverse( path );
return 0;
}
}
fsl_stmt_reset(&s);
pPrev = pPrev->u.pPeer;
}
}
end:
fsl_stmt_finalize(&s);
fsl_vpath_clear(path);
return rc;
}
/**
Creates, if needed, the [ancestor] table, else clears its
contents. Returns 0 on success, non-0 on db error (in which case
f's error state is updated).
*/
static int fsl__init_ancestor(fsl_cx * const f){
fsl_db * const db = fsl_cx_db_repo(f);
int rc;
if(db){
rc = fsl_db_exec_multi(db,
"CREATE TEMP TABLE IF NOT EXISTS ancestor("
" rid INT UNIQUE,"
" generation INTEGER PRIMARY KEY"
");"
"DELETE FROM TEMP.ancestor;");
}else{
rc = fsl_cx_err_set(f, FSL_RC_NOT_A_REPO,
"Cannot compute ancestors without an "
"opened repository.");
}
return rc ? fsl_cx_uplift_db_error2(f, db, rc) : 0;
}
int fsl_compute_direct_ancestors(fsl_cx * const f, fsl_id_t rid){
int rc = fsl__init_ancestor(f);
fsl_db * const db = rc ? NULL : fsl_needs_repo(f);
if(rc) return rc;
assert(db);
return fsl_db_exec_multi(db,
"WITH RECURSIVE g(x,i) AS ("
" VALUES(%" FSL_ID_T_PFMT ",1)"
" UNION ALL"
" SELECT plink.pid, g.i+1 FROM plink, g"
" WHERE plink.cid=g.x AND plink.isprim)"
"INSERT INTO ancestor(rid,generation) SELECT x,i FROM g;",
rid
);
}
int fsl_vpath_shortest_store_in_ancestor(fsl_cx * const f,
fsl_id_t iFrom,
fsl_id_t iTo,
uint32_t *pSteps){
int rc;
fsl_vpath path = fsl_vpath_empty;
fsl_stmt ins = fsl_stmt_empty;
fsl_db * const db = fsl_needs_repo(f);
fsl_vpath_node * node;
int32_t gen = 0;
if(!db) return FSL_RC_NOT_A_REPO;
rc = fsl_vpath_shortest(f, &path, iFrom, iTo, true, false);
if(rc) goto end;
rc = fsl__init_ancestor(f);
if(rc) goto end;
rc = fsl_db_prepare(db, &ins,
"INSERT INTO TEMP.ancestor(rid, generation) "
"VALUES(?,?)");
if(rc) goto dberr;
for(node = fsl_vpath_first(&path);
node; node = fsl_vpath_next(node)){
rc = fsl_stmt_bind_step(&ins, "Ri", node->rid, ++gen);
if(rc) goto dberr;
}
end:
if(0==rc && pSteps) *pSteps = (uint32_t)gen;
fsl_stmt_finalize(&ins);
fsl_vpath_clear(&path);
return rc;
dberr:
assert(rc!=0);
return fsl_cx_uplift_db_error2(f, db, rc);
}
/*
** A record of a file rename operation.
*/
typedef struct NameChange NameChange;
struct NameChange {
fsl_id_t origName; /* Original name of file */
fsl_id_t curName; /* Current name of the file */
fsl_id_t newName; /* Name of file in next version */
NameChange *pNext; /* List of all name changes */
};
const NameChange NameChange_empty = {0,0,0,0};
int fsl__find_filename_changes(
fsl_cx * const f,
fsl_id_t iFrom, /* Ancestor check-in */
fsl_id_t iTo, /* Recent check-in */
bool revOK, /* OK to move backwards (child->parent) if true */
uint32_t *pnChng, /* Number of name changes along the path */
fsl_id_t **aiChng /* Name changes */
){
fsl_vpath_node *p = 0; /* For looping over path from iFrom to iTo */
NameChange *pAll = 0; /* List of all name changes seen so far */
NameChange *pChng = 0; /* For looping through the name change list */
uint32_t nChng = 0; /* Number of files whose names have changed */
fsl_id_t *aChng = 0; /* Two integers per name change */
fsl_stmt q1 = fsl_stmt_empty; /* Query of name changes */
fsl_db * const db = fsl_needs_repo(f);
fsl_vpath path = fsl_vpath_empty;
int rc = 0;
if(!db) return FSL_RC_NOT_A_REPO;
*pnChng = 0;
*aiChng = 0;
if(iFrom<=0){
return fsl_cx_err_set(f, FSL_RC_MISUSE,
"Invalid 'from' RID: %" FSL_ID_T_PFMT, iFrom);
}else if(0==iTo){
return fsl_cx_err_set(f, FSL_RC_MISUSE,
"Invalid 'to' RID: %" FSL_ID_T_PFMT, iTo);
}
if( iFrom==iTo ) return 0;
rc = fsl_vpath_shortest(f, &path, iFrom, iTo, true, !revOK);
if(rc) goto end;
else if(!path.pStart){
goto end;
}
fsl_vpath_reverse(&path);
rc = fsl_db_prepare(db, &q1,
"SELECT pfnid, fnid FROM mlink"
" WHERE mid=?1 AND (pfnid>0 OR fid==0)"
" ORDER BY pfnid"
);
if(rc) goto dberr;
for(p=path.pStart; p; p=p->u.pTo){
fsl_id_t fnid = 0, pfnid = 0;
if( !p->fromIsParent && (p->u.pTo==0 || p->u.pTo->fromIsParent) ){
/* Skip nodes where the parent is not on the path */
continue;
}
fsl_stmt_bind_id(&q1, 1, p->rid);
while( FSL_RC_STEP_ROW==fsl_stmt_step(&q1) ){
pfnid = fsl_stmt_g_id(&q1, 0);
fnid = fsl_stmt_g_id(&q1, 1);
if( pfnid==0 ){
pfnid = fnid;
fnid = 0;
}
if( !p->fromIsParent ){
fsl_id_t const t = fnid;
fnid = pfnid;
pfnid = t;
}
#if 0
if( zDebug ){
fossil_print("%s at %d%s %.10z: %d[%z] -> %d[%z]\n",
zDebug, p->rid, p->fromIsParent ? ">" : "<",
db_text(0, "SELECT uuid FROM blob WHERE rid=%d", p->rid),
pfnid,
db_text(0, "SELECT name FROM filename WHERE fnid=%d", pfnid),
fnid,
db_text(0, "SELECT name FROM filename WHERE fnid=%d", fnid));
}
#endif
for(pChng=pAll; pChng; pChng=pChng->pNext){
if( pChng->curName==pfnid ){
pChng->newName = fnid;
break;
}
}
if( pChng==0 && fnid>0 ){
pChng = (NameChange*)fsl_malloc( sizeof(NameChange) );
if(!pChng){
rc = FSL_RC_OOM;
goto end;
}
pChng->pNext = pAll;
pAll = pChng;
pChng->origName = pfnid;
pChng->curName = pfnid;
pChng->newName = fnid;
++nChng;
}
}
for(pChng=pAll; pChng; pChng=pChng->pNext){
pChng->curName = pChng->newName;
}
fsl_stmt_reset(&q1);
}
if( nChng ){
/* Count effective changes. */
uint32_t n;
for(pChng=pAll, n=0; pChng; pChng=pChng->pNext){
if( pChng->newName==0 ) continue;
if( pChng->origName==0 ) continue;
++n;
}
nChng = n;
}
if(nChng){
uint32_t i;
aChng = (fsl_id_t*)fsl_malloc( nChng*2*sizeof(fsl_id_t) );
if(!aChng){
rc = FSL_RC_OOM;
goto end;
}
for(pChng=pAll, i=0; pChng; pChng=pChng->pNext){
if( pChng->newName==0 ) continue;
if( pChng->origName==0 ) continue;
aChng[i] = pChng->origName;
aChng[i+1] = pChng->newName;
#if 0
if( zDebug ){
fossil_print("%s summary %d[%z] -> %d[%z]\n",
zDebug,
aChng[i],
db_text(0, "SELECT name FROM filename WHERE fnid=%d", aChng[i]),
aChng[i+1],
db_text(0, "SELECT name FROM filename WHERE fnid=%d", aChng[i+1]));
}
#endif
i += 2;
}
assert(nChng==i/2);
*pnChng = i/2;
*aiChng = aChng;
while( pAll ){
pChng = pAll;
pAll = pAll->pNext;
fsl_free(pChng);
}
}else{
*pnChng = 0;
*aiChng = 0;
}
end:
fsl_stmt_finalize(&q1);
if(rc){
assert(!aChng);
}
fsl_vpath_clear(&path);
return rc;
dberr:
assert(rc);
rc = fsl_cx_uplift_db_error2(f, db, rc);
goto end;
}
#undef MARKER