**
** The lower 20 bits of the hash are the length of the
** line.  If any line is longer than 1048575 characters,
** the file is considered binary.
*/
typedef struct DLine DLine;
struct DLine {
  const char *z;        /* The text of the line */
  unsigned int h;       /* Hash of the line */
  unsigned int iNext;   /* Index+1 of next line with same the same hash */

  /* an array of DLine elements services two purposes.  The fields
  ** above are one per line of input text.  But each entry is also
  ** a bucket in a hash table. */
  unsigned int iHash;   /* First entry+1 in the hash array */
};

/*
** Maximum length of a line in a text file.  (8192)
*/
#define LENGTH_MASK_SZ  13
#define LENGTH_MASK     ((1<<LENGTH_MASK_SZ)-1)

/*
** A context for running a diff.
*/
typedef struct DContext DContext;
struct DContext {
  int *aEdit;        /* Array of copy/delete/insert triples */
  int nEdit;         /* Number of integers (3x num of triples) in aEdit[] */
  int nEditAlloc;    /* Space allocated for aEdit[] */
  DLine *aFrom;      /* File on left side of the diff */
  int nFrom;         /* Number of lines in aFrom[] */
  DLine *aTo;        /* File on right side of the diff */
  int nTo;           /* Number of lines in aTo[] */
};

/*
** Return an array of DLine objects containing a pointer to the
** start of each line and a hash of that line.  The lower 
** bits of the hash store the length of each line.
**
** Trailing whitespace is removed from each line.
**
** Return 0 if the file is binary or contains a line that is
** too long.
*/
static DLine *break_into_lines(char *z, int *pnLine){
  int nLine, i, j, k, x;
  unsigned int h, h2;
  DLine *a;

  /* Count the number of lines.  Allocate space to hold
  ** the returned array.
  */
  for(i=j=0, nLine=1; z[i]; i++, j++){
    int c = z[i];
    if( c==0 ){
      return 0;
    }
    if( c=='\n' && z[i+1]!=0 ){
      nLine++;
      if( j>LENGTH_MASK ){
        return 0;
      }
      j = 0;
    }
  }
  if( j>LENGTH_MASK ){
    return 0;
  }
  a = malloc( nLine*sizeof(a[0]) );
  if( a==0 ) fossil_panic("out of memory");
  memset(a, 0, nLine*sizeof(a[0]) );

  /* Fill in the array */
  for(i=0; i<nLine; i++){
    a[i].z = z;
    for(j=0; z[j] && z[j]!='\n'; j++){}
    for(k=j; k>0 && isspace(z[k-1]); k--){}
    for(h=0, x=0; x<k; x++){
      h = h ^ (h<<2) ^ z[x];
    }
    a[i].h = h = (h<<LENGTH_MASK_SZ) | k;;
    h2 = h % nLine;
    a[i].iNext = a[h2].iHash;
    a[h2].iHash = i+1;
    z += j+1;
  }

  /* Return results */
  *pnLine = nLine;
  return a;
}

*/
static void appendDiffLine(Blob *pOut, char *zPrefix, DLine *pLine){
  blob_append(pOut, zPrefix, 1);
  blob_append(pOut, pLine->z, pLine->h & LENGTH_MASK);
  blob_append(pOut, "\n", 1);
}

/*
** Expand the size of aEdit[] array to hold nEdit elements.
*/
static void expandEdit(DContext *p, int nEdit){
  int *a;
  a = realloc(p->aEdit, nEdit*sizeof(int));
  if( a==0 ){
    free( p->aEdit );
    p->nEdit = 0;
    nEdit = 0;
  }
  p->aEdit = a;
  p->nEditAlloc = nEdit;
}

/*
** Append a new COPY/DELETE/INSERT triple.
*/
static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){
  /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
  if( p->nEdit>=3 ){
    if( p->aEdit[p->nEdit-1]==0 ){
      if( p->aEdit[p->nEdit-2]==0 ){
        p->aEdit[p->nEdit-3] += nCopy;
        p->aEdit[p->nEdit-2] += nDel;
        p->aEdit[p->nEdit-1] += nIns;
        return;
      }
      if( nCopy==0 ){
        p->aEdit[p->nEdit-2] += nDel;
        p->aEdit[p->nEdit-1] += nIns;
        return;
      }
    }
    if( nCopy==0 && nDel==0 ){
      p->aEdit[p->nEdit-1] += nIns;
      return;
    }
  }  
  if( p->nEdit+3>p->nEditAlloc ){
    expandEdit(p, p->nEdit*2 + 15);
    if( p->aEdit==0 ) return;
  }
  p->aEdit[p->nEdit++] = nCopy;
  p->aEdit[p->nEdit++] = nDel;
  p->aEdit[p->nEdit++] = nIns;
}


/*
** Given a diff context in which the aEdit[] array has been filled
** in, compute a context diff into pOut.
*/
static void contextDiff(DContext *p, Blob *pOut, int nContext){
  DLine *A;     /* Left side of the diff */
  DLine *B;     /* Right side of the diff */  
  int a = 0;    /* Index of next line in A[] */
  int b = 0;    /* Index of next line in B[] */
  int *R;       /* Array of COPY/DELETE/INSERT triples */
  int r;        /* Index into R[] */
  int nr;       /* Number of COPY/DELETE/INSERT triples to process */
  int mxr;      /* Maximum value for r */
  int na, nb;   /* Number of lines shown from A and B */
  int i, j;     /* Loop counters */
  int m;        /* Number of lines to output */
  int skip;     /* Number of lines to skip */

  A = p->aFrom;
  B = p->aTo;
  R = p->aEdit;
  mxr = p->nEdit;
  if( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
  for(r=0; r<mxr; r += 3*nr){
    /* Figure out how many triples to show in a single block */
    for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<nContext*2; nr++){}
    DEBUG( printf("r=%d nr=%d\n", r, nr); )

    /* For the current block comprising nr triples, figure out
    ** how many lines of A and B are to be displayed
    */
    if( R[r]>nContext ){
      na = nb = nContext;
      skip = R[r] - nContext;
    }else{
      na = nb = R[r];
      skip = 0;
    }
    for(i=0; i<nr; i++){
      na += R[r+i*3+1];
      nb += R[r+i*3+2];
    }
    if( R[r+nr*3]>nContext ){
      na += nContext;
      nb += nContext;
    }else{
      na += R[r+nr*3];
      nb += R[r+nr*3];
    }
    for(i=1; i<nr; i++){
      na += R[r+i*3];
      nb += R[r+i*3];
    }
    blob_appendf(pOut,"@@ -%d,%d +%d,%d @@\n", a+skip+1, na, b+skip+1, nb);

    /* Show the initial common area */
    a += skip;
    b += skip;
    m = R[r] - skip;
    for(j=0; j<m; j++){
      appendDiffLine(pOut, " ", &A[a+j]);
    }
    a += m;
    b += m;

    /* Show the differences */
    for(i=0; i<nr; i++){
      m = R[r+i*3+1];
      for(j=0; j<m; j++){
        appendDiffLine(pOut, "-", &A[a+j]);
      }
      a += m;
      m = R[r+i*3+2];
      for(j=0; j<m; j++){
        appendDiffLine(pOut, "+", &B[b+j]);
      }
      b += m;
      if( i<nr-1 ){
        m = R[r+i*3+3];
        for(j=0; j<m; j++){
          appendDiffLine(pOut, " ", &B[b+j]);
        }
        b += m;
        a += m;
      }
    }

    /* Show the final common area */
    assert( nr==i );
    m = R[r+nr*3];
    if( m>nContext ) m = nContext;
    for(j=0; j<m; j++){
      appendDiffLine(pOut, " ", &B[b+j]);
    }
  }
}

/*
** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
** file and lines iS2 through iE2-1 of the aTo[] file.  Locate a sequence
** of lines in these two blocks that are exactly the same.  Return
** the bounds of the matching sequence.
*/
static void longestCommonSequence(
  DContext *p,
  int iS1, int iE1,
  int iS2, int iE2,
  int *piSX, int *piEX,
  int *piSY, int *piEY
){
  int bestScore = -1000000000;
  int i, j;
  int iSX, iSY, iEX, iEY;
  int score, skew, dist, mid;

  *piSX = iS1;
  *piEX = iS1;
  *piSY = iS2;
  *piEY = iS2;
  mid = (iE1 + iS1)/2;
  for(i=iS1; i<iE1; i++){
    int limit = 0;
    j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
    while( j>0 
      && (j-1<iS2 || j>=iE2 || !same_dline(&p->aFrom[i], &p->aTo[j-1]))
    ){
      if( limit++ > 10 ){
        j = 0;
        break;
      }
      j = p->aTo[j-1].iNext;
    }
    if( j==0 ) continue;
    iSX = i;
    iSY = j-1;
    while( iSX>iS1 && iSY>iS2 && same_dline(&p->aFrom[iSX-1],&p->aTo[iSY-1]) ){
      iSX--;
      iSY--;
    }
    iEX = i+1;
    iEY = j;
    while( iEX<iE1 && iEY<iE2 && same_dline(&p->aFrom[iEX],&p->aTo[iEY]) ){
      iEX++;
      iEY++;
    }
    skew = (iSX-iS1) - (iSY-iS2);
    if( skew<0 ) skew = -skew;
    dist = (iSX+iEX)/2 - mid;
    if( dist<0 ) dist = -dist;
    score = (iEX - iSX) - 0.05*skew - 0.05*dist;
    if( score>bestScore ){
      bestScore = score;
      *piSX = iSX;
      *piSY = iSY;
      *piEX = iEX;
      *piEY = iEY;
    }
  }
  /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n", 
     iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY);  */
}

/*
** Do a single step in the difference.  Compute a sequence of
** copy/delete/insert steps that will convert lines iS1 through iE1-1 of
** the input into lines iS2 through iE2-1 of the output and write
** that sequence into the difference context.
*/
static void diff_step(DContext *p, int iS1, int iE1, int iS2, int iE2){
  int iSX, iEX, iSY, iEY;

  if( iE1<=iS1 ){
    if( iE2>iS2 ){
      appendTriple(p, 0, 0, iE2-iS2);
    }
    return;
  }
  if( iE2<=iS2 ){
    appendTriple(p, 0, iE1-iS1, 0);
    return;
  }

  /* Find the longest matching segment between the two sequences */
  longestCommonSequence(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);

  if( iEX>iSX ){
    /* Recursively diff either side of the matching segment */
    diff_step(p, iS1, iSX, iS2, iSY);
    if( iEX>iSX ){
      appendTriple(p, iEX - iSX, 0, 0);
    }
    diff_step(p, iEX, iE1, iEY, iE2);
  }else{
    appendTriple(p, 0, iE1-iS1, iE2-iS2);
  }
}

/*
** Generate a report of the differences between files pA and pB.
** If pOut is not NULL then a unified diff is appended there.  It
** is assumed that pOut has already been initialized.  If pOut is
** NULL, then a pointer to an array of integers is returned.  
** The integers come in triples.  For each triple,
** the elements are the number of lines copied, the number of
** lines deleted, and the number of lines inserted.  The vector
** is terminated by a triple of all zeros.
**
** This diff utility does not work on binary files.  If a binary
** file is encountered, 0 is returned and pOut is written with
** text "cannot compute difference between binary files".
*/
int *text_diff(
  Blob *pA_Blob,   /* FROM file */
  Blob *pB_Blob,   /* TO file */
  Blob *pOut,      /* Write unified diff here if not NULL */
  int nContext     /* Amount of context to unified diff */
){
  DContext c;
  int mnE, iS, iE1, iE2;

  memset(&c, 0, sizeof(c));
  c.aFrom = break_into_lines(blob_str(pA_Blob), &c.nFrom);
  c.aTo = break_into_lines(blob_str(pB_Blob), &c.nTo);
  if( c.aFrom==0 || c.aTo==0 ){
    free(c.aFrom);
    free(c.aTo);
    if( pOut ){
      blob_appendf(pOut, "cannot compute difference between binary files\n");
    }
    return 0;
  }

  /* Carve off the common header and footer */
  iE1 = c.nFrom;
  iE2 = c.nTo;
  while( iE1>0 && iE2>0 && same_dline(&c.aFrom[iE1-1], &c.aTo[iE2-1]) ){
    iE1--;
    iE2--;
  }
  mnE = iE1<iE2 ? iE1 : iE2;
  for(iS=0; iS<mnE && same_dline(&c.aFrom[iS],&c.aTo[iS]); iS++){}

  /* do the difference */
  if( iS>0 ){
    appendTriple(&c, iS, 0, 0);
  }
  diff_step(&c, iS, iE1, iS, iE2);
  if( iE1<c.nFrom ){
    appendTriple(&c, c.nFrom - iE1, 0, 0);
  }

  expandEdit(&c, c.nEdit+3);
  if( c.aEdit ){
    c.aEdit[c.nEdit++] = 0;
    c.aEdit[c.nEdit++] = 0;
    c.aEdit[c.nEdit++] = 0;
  }

  if( pOut ){
    /* Compute a context diff if requested */
    contextDiff(&c, pOut, nContext);
    free(c.aFrom);
    free(c.aTo);
    free(c.aEdit);
    return 0;
  }else{
    /* If a context diff is not requested, then return the
    ** array of COPY/DELETE/INSERT triples after terminating the
    ** array with a triple of all zeros.
    */
    free(c.aFrom);
    free(c.aTo);
    return c.aEdit;
  }
}

#if 0  /********** Disabled and replaced by code above ************/

/*
** Generate a report of the differences between files pA and pB.
** If pOut is not NULL then a unified diff is appended there.  It
** is assumed that pOut has already been initialized.  If pOut is
** NULL, then a pointer to an array of integers is returned.  
** The integers come in triples.  For each triple,

  /* We no longer need the A[] and B[] vectors */
  free(A);
  free(B);

  /* Return the result */
  return R;
}
#endif /***************** End of the Wagner/Myers algorithm ************/

/*
** COMMAND: test-rawdiff
*/
void test_rawdiff_cmd(void){
  Blob a, b;
  int r;

/*
** Copyright (c) 2007 D. Richard Hipp
** Copyright (c) 2008 Stephan Beal
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,

void tagview_menu_entry(
  const char *zTitle,
  const char *zLink,
  const char *zDesc
){
  @ <tr><td valign="top" align="right">
  if( zLink && zLink[0] ){
    @ <a href="%s(g.zBaseURL)/%s(zLink)">%h(zTitle)</a>
  }else{
    @ %h(zTitle)
  }
  @ </td><td valign="top">%h(zDesc)</td></tr>
}




static void tagview_page_list_tags( char const * like )
{
  Stmt st;
  char * likeclause = 0;
  const int limit = 10;
  char * limitstr = 0;
  if( like && strlen(like) )
  {
    likeclause = mprintf( "AND t.tagname LIKE '%%%%%q%%%%'", like );
    @ <h2>Tags matching [%s(likeclause)]:</h2>
  }
  else
  {
    limitstr = mprintf( "LIMIT %d", limit );

    @ <h2>%d(limit) most recent tags:</h2>
  }

  @ <table cellpadding='4px' border='1'><tbody>
  @ <tr>
  @ <th>Tag ID</th>
  @ <th>Tag name</th>
  @ <th>Timestamp</th>
  @ <th>Version</th>
  @ </tr>
  char * sql = mprintf( 
    "SELECT t.tagid, t.tagname, DATETIME(tx.mtime), b.uuid "
    "FROM tag t, tagxref tx, blob b "
    "WHERE (t.tagid=tx.tagid) and (tx.srcid=b.rid) "
    "AND (tx.tagtype != 0) %s "
    "ORDER BY tx.mtime DESC %s",
    likeclause ? likeclause : " ",
    limitstr ? limitstr : " "
    );
  db_prepare( &st, sql );
  if( likeclause ) free( likeclause );
  free( sql );
  while( SQLITE_ROW == db_step(&st) ){

    int tagid = db_column_int( &st, 0 );
    char const * tagname = db_column_text( &st, 1 );
    char const * tagtime = db_column_text( &st, 2 );
    char const * uuid = db_column_text( &st, 3 );
    const int offset = 10;
    char shortname[offset+1];
    shortname[offset] = '\0';
    memcpy( shortname, uuid, offset );
    @ <tr>
    @ <td><tt>
    @ <a href='%s(g.zBaseURL)/tagview?tagid=%d(tagid)'>%d(tagid)</a>
    @ </tt></td>
    @ <td><tt><a href='%s(g.zBaseURL)/tagview/%q(tagname)'>%s(tagname)</a></tt></td>
    @ <td align='center'><tt>%s(tagtime)</tt></td>
    @ <td><tt>
    @ <a href='%s(g.zBaseURL)/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a>
    @ </tt></td></tr>
  }
  db_finalize( &st );
  @ </tbody></table>
  @ <hr/>TODOs include:
  @ <ul>
  @  <li>Page through long tags lists.</li>
  @  <li>Refactor the internal report routines to be reusable.</li>
  @  <li>Allow different sorting.</li>
  @  <li>Selectively filter out wiki/ticket/baseline</li>
  @  <li>?</li>
  @ </ul>

}

static void tagview_page_search_miniform(void){
  char const * like = P("like");
  @ <div style='font-size:smaller'>
  @ <form action='/tagview' method='post'>
  @ Search for tags: 
  @ <input type='text' name='like' value='%s((like?like:""))' size='10'/>
  @ <input type='submit'/>
  @ </form>
  @ </div>
}


static void tagview_page_default(void){
  tagview_page_list_tags( 0 );
}

static void tagview_page_tag_by_id( int tagid )
{
  Stmt st;
  char * sql = mprintf( 
    "SELECT DISTINCT (t.tagname), DATETIME(tx.mtime), b.uuid "
    "FROM tag t, tagxref tx, blob b "
    "WHERE (t.tagid=%d) AND (t.tagid=tx.tagid) AND (tx.srcid=b.rid) "
    "ORDER BY tx.mtime DESC",
  tagid);
  db_prepare( &st, sql );
  free( sql );
  @ <h2>Tag ID %d(tagid):</h2>
  @ <table cellpadding='4px' border='1'><tbody>
  @ <tr><th>Tag name</th><th>Timestamp</th><th>Version</th></tr>
  while( SQLITE_ROW == db_step(&st) )
  {
    char const * tagname = db_column_text( &st, 0 );
    char const * tagtime = db_column_text( &st, 1 );
    char const * uuid = db_column_text( &st, 2 );
    const int offset = 10;
    char shortname[offset+1];
    shortname[offset] = '\0';
    memcpy( shortname, uuid, offset );
    @ <tr>
    @ <td><tt><a href='%s(g.zBaseURL)/tagview/%q(tagname)'>%s(tagname)</a></tt></td>
    @ <td align='center'><tt>%s(tagtime)</tt></td>
    @ <td><tt>
    @ <a href='%s(g.zBaseURL)/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a>
    @ </tt></td></tr>
  }
  @ </tbody></table>
  db_finalize( &st );
}

static void tagview_page_tag_by_name( char const * tagname )
{
  Stmt st;
  char * sql = mprintf( 
    "SELECT DISTINCT t.tagid, DATETIME(tx.mtime), b.uuid "
    "FROM tag t, tagxref tx, blob b "
    "WHERE (t.tagname='%q') AND (t.tagid=tx.tagid) AND (tx.srcid=b.rid) "
    "ORDER BY tx.mtime DESC",
    tagname);
  db_prepare( &st, sql );
  free( sql );
  @ <h2>Tag '%s(tagname)':</h2>
  @ <table cellpadding='4px' border='1'><tbody>
  @ <tr><th>Tag ID</th><th>Timestamp</th><th>Version</th></tr>
  while( SQLITE_ROW == db_step(&st) )
  {
    int tagid = db_column_int( &st, 0 );
    char const * tagtime = db_column_text( &st, 1 );
    char const * uuid = db_column_text( &st, 2 );
    const int offset = 10;
    char shortname[offset+1];
    shortname[offset] = '\0';
    memcpy( shortname, uuid, offset );
    @ <tr>
    @ <td><tt><a href='%s(g.zBaseURL)/tagview?tagid=%d(tagid)'>%d(tagid)</a></tt></td>
    @ <td align='center'><tt>%s(tagtime)</tt></td>
    @ <td><tt>
    @ <a href='%s(g.zBaseURL)/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a>
    @ </tt></td></tr>
  }
  @ </tbody></table>
  db_finalize( &st );
}


/*
** WEBPAGE: /tagview
*/
void tagview_page(void){

  login_check_credentials();
  if( !g.okSetup ){
    login_needed();
  }
  style_header("Tags");
  tagview_page_search_miniform();
  @ <hr/>
  char const * check = 0;
  if( 0 != (check = P("tagid")) )
  {
    tagview_page_tag_by_id( atoi(check) );
  }
  else if( 0 != (check = P("like")) )
  {
    tagview_page_list_tags( check );
  }
  else if( 0 != (check = P("name")) )
  {
    tagview_page_tag_by_name( check );
  }
  else
  {
    tagview_page_default();
  }
  style_footer();
}