Fossil

** text files.
*/
#include "config.h"
#include "diff.h"
#include <assert.h>


#if INTERFACE
/*
** Allowed flag parameters to the text_diff() and html_sbsdiff() funtions:
*/
#define DIFF_CONTEXT_MASK  0x0000fff  /* Lines of context.  Default if 0 */
#define DIFF_WIDTH_MASK    0x00ff000  /* side-by-side column width */
#define DIFF_IGNORE_EOLWS  0x0100000  /* Ignore end-of-line whitespace */
#define DIFF_SIDEBYSIDE    0x0200000  /* Generate a side-by-side diff */
#define DIFF_NEWFILE       0x0400000  /* Missing files are as empty files */

#endif /* INTERFACE */

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

/*

    m = R[r+nr*3];
    if( m>nContext ) m = nContext;
    for(j=0; j<m; j++){
      appendDiffLine(pOut, " ", &B[b+j]);
    }
  }
}

/*
** Append spaces to a blob
*/
static void appendSpace(Blob *pOut, int n){
  const char z100[101] = 
     "                                                  "
     "                                                  ";
  while( n>100 ){
    blob_append(pOut, z100, 100); n -= 100;
  }
  if( n>0 ){
    blob_append(pOut, z100, n);
  }
}

/*
** Append text to a sbs diff output
*/
static void appendSbsLine(Blob *pOut, DLine *pLine, int width, int pad){
  int sz = pLine->h & LENGTH_MASK;
  if( sz<width ){
    blob_append(pOut, pLine->z, sz);
    if( pad ) appendSpace(pOut, width-sz);
  }else{
    blob_append(pOut, pLine->z, width);
  }
}


/*
** Given a diff context in which the aEdit[] array has been filled
** in, compute a side-by-side diff into pOut.
*/
static void sbsDiff(DContext *p, Blob *pOut, int nContext, int width){
  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, ma, mb;/* Number of lines to output */
  int skip;     /* Number of lines to skip */
  char zFormat[50];  /* Output format */

  sqlite3_snprintf(sizeof(zFormat), zFormat,
                   "%%4d %%%d.%ds %%c %%4d %%.%ds\n",
                   width, width, width);
  A = p->aFrom;
  B = p->aTo;
  R = p->aEdit;
  mxr = p->nEdit;
  while( 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++){}
    /* 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];
    }
    /*
     * If the patch changes an empty file or results in an empty file,
     * the block header must use 0,0 as position indicator and not 1,0.
     * Otherwise, patch would be confused and may reject the diff.
     */
    blob_appendf(pOut,"@@ -%d,%d +%d,%d @@\n",
      na ? a+skip+1 : 0, na,
      nb ? b+skip+1 : 0, nb);

    /* Show the initial common area */
    a += skip;
    b += skip;
    m = R[r] - skip;
    for(j=0; j<m; j++){
      blob_appendf(pOut, "%6d ", a+j);
      appendSbsLine(pOut, &A[a+j], width, 1);
      blob_appendf(pOut, "   %6d ", b+j);
      appendSbsLine(pOut, &B[b+j], width, 0);
      blob_append(pOut, "\n", 1);
    }
    a += m;
    b += m;

    /* Show the differences */
    for(i=0; i<nr; i++){
      ma = R[r+i*3+1];
      mb = R[r+i*3+2];
      m = ma<mb ? ma : mb;
      for(j=0; j<m; j++){
        blob_appendf(pOut, "%6d ", a+j);
        appendSbsLine(pOut, &A[a+j], width, 1);
        blob_appendf(pOut, " | %6d ", b+j);
        appendSbsLine(pOut, &B[b+j], width, 0);
        blob_append(pOut, "\n", 1);
      }
      a += m;
      b += m;
      ma -= m;
      mb -= m;
      for(j=0; j<ma; j++){
        blob_appendf(pOut, "%6d ", a+j);
        appendSbsLine(pOut, &A[a+j], width, 1);
        blob_append(pOut, " <\n", 3);
      }
      a += ma;
      for(j=0; j<mb; j++){
        appendSpace(pOut, width+7);
        blob_appendf(pOut, " > %6d", b+j);
        appendSbsLine(pOut, &B[b+j], width, 0);
        blob_append(pOut, "\n", 1);
      }
      b += mb;
      if( i<nr-1 ){
        m = R[r+i*3+3];
        for(j=0; j<m; j++){
          blob_appendf(pOut, "%6d ", a+j);
          appendSbsLine(pOut, &A[a+j], width, 1);
          blob_appendf(pOut, "   %6d ", b+j);
          appendSbsLine(pOut, &B[b+j], width, 0);
          blob_append(pOut, "\n", 1);
        }
        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++){
      blob_appendf(pOut, "%6d ", a+j);
      appendSbsLine(pOut, &A[a+j], width, 1);
      blob_appendf(pOut, "   %6d ", b+j);
      appendSbsLine(pOut, &B[b+j], width, 0);
      blob_append(pOut, "\n", 1);
    }
  }
}

/*
** Compute the optimal longest common subsequence (LCS) using an
** exhaustive search.  This version of the LCS is only used for
** shorter input strings since runtime is O(N*N) where N is the
** input string length.
*/

** 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 diff here if not NULL */
  int diffFlags    /* DIFF_* flags defined above */

){
  int ignoreEolWs; /* Ignore whitespace at the end of lines */
  int nContext;    /* Amount of context to display */	
  DContext c;

  nContext = diffFlags & DIFF_CONTEXT_MASK;
  if( nContext==0 ) nContext = 5;
  ignoreEolWs = (diffFlags & DIFF_IGNORE_EOLWS)!=0;

  /* Prepare the input files */
  memset(&c, 0, sizeof(c));
  c.aFrom = break_into_lines(blob_str(pA_Blob), blob_size(pA_Blob),
                             &c.nFrom, ignoreEolWs);
  c.aTo = break_into_lines(blob_str(pB_Blob), blob_size(pB_Blob),
                           &c.nTo, ignoreEolWs);
  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;
  }

  /* Compute the difference */
  diff_all(&c);

  if( pOut ){
    /* Compute a context or side-by-side diff into pOut */
    if( diffFlags & DIFF_SIDEBYSIDE ){
      int width = (diffFlags & DIFF_WIDTH_MASK)/(DIFF_CONTEXT_MASK+1);
      if( width==0 ) width = 80;
      sbsDiff(&c, pOut, nContext, width);
    }else{
      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.

  iFrom=iTo=0;
  i=0;
  while( i<c.nEdit ){
    int j;
    /* Copied lines */
    for( j=0; j<c.aEdit[i]; j++){
      /* Hide lines which are copied and are further away from block boundaries
      ** than nContext lines. For each block with hidden lines, show a row
      ** notifying the user about the hidden rows.
      */
      if( j<nContext || j>c.aEdit[i]-nContext-1 ){
        @ <tr>
      }else if( j==nContext && j<c.aEdit[i]-nContext-1 ){
        @ <tr>
        @ <td class="meta" colspan="5" style="white-space: nowrap;">

  int i;
  int *R;
  if( g.argc<4 ) usage("FILE1 FILE2 ...");
  blob_read_from_file(&a, g.argv[2]);
  for(i=3; i<g.argc; i++){
    if( i>3 ) fossil_print("-------------------------------\n");
    blob_read_from_file(&b, g.argv[i]);
    R = text_diff(&a, &b, 0, 0);
    for(r=0; R[r] || R[r+1] || R[r+2]; r += 3){
      fossil_print(" copy %4d  delete %4d  insert %4d\n", R[r], R[r+1], R[r+2]);
    }
    /* free(R); */
    blob_reset(&b);
  }
}

/*
** COMMAND: test-udiff
*/
void test_udiff_cmd(void){
  Blob a, b, out;
  int diffFlag = find_option("sbs",0,0)!=0 ? DIFF_SIDEBYSIDE : 0;
  int nContext = 5;
  const char *z;
  if( (z = find_option("context","c",1))!=0 && atoi(z)>0 ){
    nContext = atoi(z);
  }
  if( nContext<=0 ) nContext = 5;
  if( (nContext&DIFF_CONTEXT_MASK)!=nContext ) nContext = DIFF_CONTEXT_MASK;
  if( g.argc!=4 ) usage("[--sbs] [--context N] FILE1 FILE2");
  blob_read_from_file(&a, g.argv[2]);
  blob_read_from_file(&b, g.argv[3]);
  blob_zero(&out);
  text_diff(&a, &b, &out, nContext | diffFlag);
  blob_write_to_file(&out, "-");
}

/**************************************************************************
** The basic difference engine is above.  What follows is the annotation
** engine.  Both are in the same file since they share many components.
*/

**
** This file contains code used to implement the "diff" command
*/
#include "config.h"
#include "diffcmd.h"
#include <assert.h>







/*
** Output the results of a diff.  Output goes to stdout for command-line
** or to the CGI/HTTP result buffer for web pages.
*/
static void diff_printf(const char *zFormat, ...){
  va_list ap;
  va_start(ap, zFormat);

** command zDiffCmd to do the diffing.
*/
void diff_file(
  Blob *pFile1,             /* In memory content to compare from */
  const char *zFile2,       /* On disk content to compare to */
  const char *zName,        /* Display name of the file */
  const char *zDiffCmd,     /* Command for comparison */
  int diffFlags             /* Flags to control the diff */
){
  if( zDiffCmd==0 ){
    Blob out;                 /* Diff output text */
    Blob file2;               /* Content of zFile2 */
    const char *zName2;       /* Name of zFile2 for display */

    /* Read content of zFile2 into memory */

        blob_read_from_file(&file2, zFile2);
      }
      zName2 = zName;
    }

    /* Compute and output the differences */
    blob_zero(&out);
    text_diff(pFile1, &file2, &out, diffFlags);
    if( blob_size(&out) ){
      diff_printf("--- %s\n+++ %s\n", zName, zName2);
      diff_printf("%s\n", blob_str(&out));
    }

    /* Release memory resources */
    blob_reset(&file2);

** command zDiffCmd to do the diffing.
*/
void diff_file_mem(
  Blob *pFile1,             /* In memory content to compare from */
  Blob *pFile2,             /* In memory content to compare to */
  const char *zName,        /* Display name of the file */
  const char *zDiffCmd,     /* Command for comparison */
  int diffFlags             /* Diff flags */
){
  if( zDiffCmd==0 ){
    Blob out;      /* Diff output text */

    blob_zero(&out);
    text_diff(pFile1, pFile2, &out, diffFlags);
    diff_printf("--- %s\n+++ %s\n", zName, zName);
    diff_printf("%s\n", blob_str(&out));

    /* Release memory resources */
    blob_reset(&out);
  }else{
    Blob cmd;

/*
** Do a diff against a single file named in zFileTreeName from version zFrom
** against the same file on disk.
*/
static void diff_one_against_disk(
  const char *zFrom,        /* Name of file */
  const char *zDiffCmd,     /* Use this "diff" command */
  int diffFlags,            /* Diff control flags */
  const char *zFileTreeName
){
  Blob fname;
  Blob content;
  int isLink;
  file_tree_name(zFileTreeName, &fname, 1);
  historical_version_of_file(zFrom, blob_str(&fname), &content, &isLink, 0, 0);
  if( !isLink != !file_wd_islink(zFrom) ){
    diff_printf("cannot compute difference between symlink and regular file\n");
  }else{
    diff_file(&content, zFileTreeName, zFileTreeName, zDiffCmd, diffFlags);
  }
  blob_reset(&content);
  blob_reset(&fname);
}

/*
** Run a diff between the version zFrom and files on disk.  zFrom might
** be NULL which means to simply show the difference between the edited
** files on disk and the check-out on which they are based.
*/
static void diff_all_against_disk(
  const char *zFrom,        /* Version to difference from */
  const char *zDiffCmd,     /* Use this diff command.  NULL for built-in */
  int diffFlags             /* Flags controlling diff output */
){
  int vid;
  Blob sql;
  Stmt q;

  int asNewFile;            /* Treat non-existant files as empty files */


  asNewFile = (diffFlags & DIFF_NEWFILE)!=0;
  vid = db_lget_int("checkout", 0);
  vfile_check_signature(vid, 1, 0);
  blob_zero(&sql);
  db_begin_transaction();
  if( zFrom ){
    int rid = name_to_typed_rid(zFrom, "ci");

      }
      if( srcid>0 ){
        content_get(srcid, &content);
      }else{
        blob_zero(&content);
      }
      diff_print_index(zPathname);
      diff_file(&content, zFullName, zPathname, zDiffCmd, diffFlags);
      blob_reset(&content);
    }
    free(zToFree);
  }
  db_finalize(&q);
  db_end_transaction(1);  /* ROLLBACK */
}

/*
** Output the differences between two versions of a single file.
** zFrom and zTo are the check-ins containing the two file versions.
*/
static void diff_one_two_versions(
  const char *zFrom,
  const char *zTo,
  const char *zDiffCmd,
  int diffFlags,
  const char *zFileTreeName
){
  char *zName;
  Blob fname;
  Blob v1, v2;
  int isLink1, isLink2;
  file_tree_name(zFileTreeName, &fname, 1);
  zName = blob_str(&fname);
  historical_version_of_file(zFrom, zName, &v1, &isLink1, 0, 0);
  historical_version_of_file(zTo, zName, &v2, &isLink2, 0, 0);
  if( isLink1 != isLink2 ){
    diff_printf("--- %s\n+++ %s\n", zName, zName);
    diff_printf("cannot compute difference between symlink and regular file\n");
  }else{
    diff_file_mem(&v1, &v2, zName, zDiffCmd, diffFlags);
  }
  blob_reset(&v1);
  blob_reset(&v2);
  blob_reset(&fname);
}

/*
** Show the difference between two files identified by ManifestFile
** entries.
*/
static void diff_manifest_entry(
  struct ManifestFile *pFrom,
  struct ManifestFile *pTo,
  const char *zDiffCmd,
  int diffFlags
){
  Blob f1, f2;
  int rid;
  const char *zName =  pFrom ? pFrom->zName : pTo->zName;
  diff_print_index(zName);
  if( pFrom ){
    rid = uuid_to_rid(pFrom->zUuid, 0);
    content_get(rid, &f1);
  }else{
    blob_zero(&f1);
  }
  if( pTo ){
    rid = uuid_to_rid(pTo->zUuid, 0);
    content_get(rid, &f2);
  }else{
    blob_zero(&f2);
  }
  diff_file_mem(&f1, &f2, zName, zDiffCmd, diffFlags);
  blob_reset(&f1);
  blob_reset(&f2);
}

/*
** Output the differences between two check-ins.
*/
static void diff_all_two_versions(
  const char *zFrom,
  const char *zTo,
  const char *zDiffCmd,
  int diffFlags
){
  Manifest *pFrom, *pTo;
  ManifestFile *pFromFile, *pToFile;

  int asNewFlag = (diffFlags & DIFF_NEWFILE)!=0 ? 1 : 0;

  pFrom = manifest_get_by_name(zFrom, 0);
  manifest_file_rewind(pFrom);
  pFromFile = manifest_file_next(pFrom,0);
  pTo = manifest_get_by_name(zTo, 0);
  manifest_file_rewind(pTo);

      cmp = -1;
    }else{
      cmp = fossil_strcmp(pFromFile->zName, pToFile->zName);
    }
    if( cmp<0 ){
      diff_printf("DELETED %s\n", pFromFile->zName);
      if( asNewFlag ){
        diff_manifest_entry(pFromFile, 0, zDiffCmd, diffFlags);
      }
      pFromFile = manifest_file_next(pFrom,0);
    }else if( cmp>0 ){
      diff_printf("ADDED   %s\n", pToFile->zName);
      if( asNewFlag ){
        diff_manifest_entry(0, pToFile, zDiffCmd, diffFlags);
      }
      pToFile = manifest_file_next(pTo,0);
    }else if( fossil_strcmp(pFromFile->zUuid, pToFile->zUuid)==0 ){
      /* No changes */
      pFromFile = manifest_file_next(pFrom,0);
      pToFile = manifest_file_next(pTo,0);
    }else{
      /* diff_printf("CHANGED %s\n", pFromFile->zName); */
      diff_manifest_entry(pFromFile, pToFile, zDiffCmd, diffFlags);
      pFromFile = manifest_file_next(pFrom,0);
      pToFile = manifest_file_next(pTo,0);
    }
  }
  manifest_destroy(pFrom);
  manifest_destroy(pTo);
}

** the "setting" command.  If no external diff program is configured, then
** the "-i" option is a no-op.  The "-i" option converts "gdiff" into "diff".
**
** The "-N" or "--new-file" option causes the complete text of added or
** deleted files to be displayed.
**
** Options:
**   --context|-c N      Use N lines of context 
**   --from|-r VERSION   select VERSION as source for the diff
**   --new-file|-N       output complete text of added or deleted files
**   -i                  use internal diff logic
**   --to VERSION        select VERSION as target for the diff
**   --side-by-side|-y   side-by-side diff
**   --width|-W N        Width of lines in side-by-side diff 
*/
void diff_cmd(void){
  int isGDiff;               /* True for gdiff.  False for normal diff */
  int isInternDiff;          /* True for internal diff */
  int hasNFlag;              /* True if -N or --new-file flag is used */
  const char *zFrom;         /* Source version number */
  const char *zTo;           /* Target version number */
  const char *zDiffCmd = 0;  /* External diff command. NULL for internal diff */
  int diffFlags = 0;         /* Flags to control the DIFF */
  const char *z;
  int f;

  isGDiff = g.argv[1][0]=='g';
  isInternDiff = find_option("internal","i",0)!=0;
  zFrom = find_option("from", "r", 1);
  zTo = find_option("to", 0, 1);
  hasNFlag = find_option("new-file","N",0)!=0;
  if( find_option("side-by-side","y",0)!=0 ) diffFlags |= DIFF_SIDEBYSIDE;
  if( (z = find_option("context","c",1))!=0 && (f = atoi(z))>0 ){
    if( f > DIFF_CONTEXT_MASK ) f = DIFF_CONTEXT_MASK;
    diffFlags |= f;
  }
  if( (z = find_option("width","W",1))!=0 && (f = atoi(z))>0 ){
    f *= DIFF_CONTEXT_MASK+1;
    if( f > DIFF_WIDTH_MASK ) f = DIFF_CONTEXT_MASK;
    diffFlags |= f;
  }


  if( hasNFlag ) diffFlags |= DIFF_NEWFILE;
  if( zTo==0 ){
    db_must_be_within_tree();
    verify_all_options();
    if( !isInternDiff ){

  if( zTo ){
    toid = uuid_to_rid(zTo, 0);
    content_get(toid, &to);
  }else{
    blob_zero(&to);
  }
  blob_zero(&out);
  text_diff(&from, &to, &out, DIFF_IGNORE_EOLWS | 5);
  @ %h(blob_str(&out))
  blob_reset(&from);
  blob_reset(&to);
  blob_reset(&out);  
}

  }else{
    blob_zero(&diff);
    pOut = &diff;
  }
  if( !sideBySide || isPatch ){
    content_get(v1, &c1);
    content_get(v2, &c2);
    text_diff(&c1, &c2, pOut, 4 | 0);
    blob_reset(&c1);
    blob_reset(&c2);
  }
  if( !isPatch ){
    style_header("Diff");
    style_submenu_element("Patch", "Patch", "%s/fdiff?v1=%T&v2=%T&patch",
                          g.zTop, P("v1"), P("v2"));

  ** and pPivot => pV2 (into aC2).  Each of the aC1 and aC2 arrays is
  ** an array of integer triples.  Within each triple, the first integer
  ** is the number of lines of text to copy directly from the pivot,
  ** the second integer is the number of lines of text to omit from the
  ** pivot, and the third integer is the number of lines of text that are
  ** inserted.  The edit array ends with a triple of 0,0,0.
  */
  aC1 = text_diff(pPivot, pV1, 0, 0);
  aC2 = text_diff(pPivot, pV2, 0, 0);
  if( aC1==0 || aC2==0 ){
    free(aC1);
    free(aC2);
    return -1;
  }

  blob_rewind(pV1);        /* Rewind inputs:  Needed to reconstruct output */

  if( pW1==0 ) fossil_redirect_home();
  blob_init(&w1, pW1->zWiki, -1);
  blob_zero(&w2);
  if( rid2 && (pW2 = manifest_get(rid2, CFTYPE_WIKI))!=0 ){
    blob_init(&w2, pW2->zWiki, -1);
  }
  blob_zero(&d);
  text_diff(&w2, &w1, &d, 5 | DIFF_IGNORE_EOLWS);
  @ <pre>
  @ %h(blob_str(&d))
  @ </pre>
  manifest_destroy(pW1);
  manifest_destroy(pW2);
  style_footer();
}