Fossil

** This file also contains logic used to compute the closure of filename
** changes that have occurred across multiple check-ins.
*/
#include "config.h"
#include "bisect.h"
#include <assert.h>

#if INTERFACE
/* Nodes for the shortest path algorithm.
*/

struct BisectNode {
  int rid;                 /* ID for this node */
  int fromIsParent;        /* True if pFrom is the parent of rid */
  BisectNode *pFrom;       /* Node we came from */
  union {
    BisectNode *pPeer;       /* List of nodes of the same generation */
    BisectNode *pTo;         /* Next on path from beginning to end */
  } u;
  BisectNode *pAll;        /* List of all nodes */
};
#endif

/*
** Local variables for this module
*/
static struct {
  BisectNode *pCurrent;   /* Current generation of nodes */
  BisectNode *pAll;       /* All nodes */

  bag_insert(&bisect.seen, rid);
  return p;
}

/*
** Reset memory used by the shortest path algorithm.
*/
void bisect_reset(void){
  BisectNode *p;
  while( bisect.pAll ){
    p = bisect.pAll;
    bisect.pAll = p->pAll;
    fossil_free(p);
  }
  bag_clear(&bisect.seen);
  bisect.pCurrent = 0;
  bisect.pAll = 0;
  bisect.pEnd = 0;
  bisect.nStep = 0;
}

/*
** Compute the shortest path from iFrom to iTo
**
** If directOnly is true, then use only the "primary" links from parent to
** child.  In other words, ignore merges.
*/
BisectNode *bisect_shortest_path(int iFrom, int iTo, int directOnly){
  Stmt s;
  BisectNode *pPrev;
  BisectNode *p;

  bisect_reset();
  bisect.pStart = bisect_new_node(iFrom, 0, 0);
  if( iTo==iFrom ) return bisect.pStart;

  bisect_reset();
  return 0;
}

/*
** Construct the path from bisect.pStart to bisect.pEnd in the u.pTo fields.
*/
BisectNode *bisect_reverse_path(void){
  BisectNode *p;
  for(p=bisect.pEnd; p && p->pFrom; p = p->pFrom){
    p->pFrom->u.pTo = p;
  }
  bisect.pEnd->u.pTo = 0;
  assert( p==bisect.pStart );
  return p;
}

/*
** COMMAND:  test-shortest-path
**
** Usage: %fossil test-shortest-path ?--no-merge? VERSION1 VERSION2
**

    if( p->u.pTo ){
      printf(" is a %s of\n", p->u.pTo->fromIsParent ? "parent" : "child");
    }else{
      printf("\n");
    }
  }
}

/*
** WEBPAGE:  path
**
** example:  /path?from=trunk&to=experimental&nomerge
**
** Show a timeline of all changes along a path between two versions.
*/
void path_page(void){
  login_check_credentials();
  if( !g.okRead ){ login_needed(); return; }
}

/*
** Find the shortest path between bad and good.
*/
static BisectNode *bisect_path(void){
  BisectNode *p;
  bisect.bad = db_lget_int("bisect-bad", 0);

**    r=TAGID        show check-ins related to tagid
**    u=USER         only if belonging to this user
**    y=TYPE         'ci', 'w', 't', 'e'
**    s=TEXT         string search (comment and brief)
**    ng             Suppress the graph if present
**    nd             Suppress "divider" lines
**    f=RID          Show family (immediate parents and children) of RID
**    from=RID       Path from...
**    to=RID           ... to this
**    nomerge          ... avoid merge links on the path
**
** p= and d= can appear individually or together.  If either p= or d=
** appear, then u=, y=, a=, and b= are ignored.
**
** If a= and b= appear, only a= is used.  If neither appear, the most
** recent events are choosen.
**

  const char *zSearch = P("s");      /* Search string */
  int useDividers = P("nd")==0;      /* Show dividers if "nd" is missing */
  int tagid;                         /* Tag ID */
  int tmFlags;                       /* Timeline flags */
  const char *zThisTag = 0;          /* Suppress links to this tag */
  const char *zThisUser = 0;         /* Suppress links to this user */
  HQuery url;                        /* URL for various branch links */
  int from_rid = name_to_rid(P("from"));  /* from= for path timelines */
  int to_rid = name_to_rid(P("to"));      /* to= for path timelines */
  int noMerge = P("nomerge")!=0;          /* Do not follow merge links */

  /* To view the timeline, must have permission to read project data.
  */
  login_check_credentials();
  if( !g.okRead && !g.okRdTkt && !g.okRdWiki ){ login_needed(); return; }
  if( zTagName && g.okRead ){
    tagid = db_int(0, "SELECT tagid FROM tag WHERE tagname='sym-%q'", zTagName);

  timeline_temp_table();
  blob_zero(&sql);
  blob_zero(&desc);
  blob_append(&sql, "INSERT OR IGNORE INTO timeline ", -1);
  blob_append(&sql, timeline_query_for_www(), -1);
  url_initialize(&url, "timeline");
  if( !useDividers ) url_add_parameter(&url, "nd", 0);
  if( from_rid && to_rid && g.okRead ){
    /* If from= and to= are present, display all nodes on a path connecting
    ** the two */
    BisectNode *p;
    const char *z;

    bisect_shortest_path(from_rid, to_rid, noMerge);
    p = bisect_reverse_path();
    blob_append(&sql, " AND event.objid IN (0", -1);
    while( p ){
      blob_appendf(&sql, ",%d", p->rid);
      p = p->u.pTo;
    }
    blob_append(&sql, ")", -1);
    bisect_reset();
    blob_append(&desc, "All nodes on the path from ", -1);
    z = P("from");
    if( g.okHistory ){
      blob_appendf(&desc, "<a href='%s/info/%h'>[%h]</a>",  g.zTop, z, z);
    }else{
      blob_appendf(&desc, "[%h]", z);
    }
    blob_append(&desc, " and ", -1);
    z = P("to");
    if( g.okHistory ){
      blob_appendf(&desc, "<a href='%s/info/%h'>[%h]</a>.",  g.zTop, z, z);
    }else{
      blob_appendf(&desc, "[%h].", z);
    }
    db_multi_exec("%s", blob_str(&sql));

  }else if( (p_rid || d_rid) && g.okRead ){
    /* If p= or d= is present, ignore all other parameters other than n= */
    char *zUuid;
    int np, nd;

    if( p_rid && d_rid ){
      if( p_rid!=d_rid ) p_rid = d_rid;
      if( P("n")==0 ) nEntry = 10;

    if( g.okHistory ){
      blob_appendf(&desc, "<a href='%s/info/%s'>[%.10s]</a>",
                   g.zTop, zUuid, zUuid);
    }else{
      blob_appendf(&desc, "[%.10s]", zUuid);
    }
  }else{
    /* Otherwise, a timeline based on a span of time */
    int n;
    const char *zEType = "timeline item";
    char *zDate;
    char *zNEntry = mprintf("%d", nEntry);
    url_add_parameter(&url, "n", zNEntry);
    if( tagid>0 ){
      blob_appendf(&sql,