SHA1 Hash:	4c22ae52fd85027ef5651c64eecbcc50e79e333f
Date:	2007-11-25 17:13:14
User:	drh
Comment:	Changes to the diff algorithm to put bounds on run-time for very large files with many differences. (This came up on the previous check-in when you try to diff the two versions of sqlite3.c.)
Timelines:	ancestors | descendants | both | trunk
Other Links:	files | ZIP archive | manifest

• branch=trunk inherited from [a28c83647d]
• sym-trunk inherited from [a28c83647d]

Modified src/diff.c from [0027a16891] to [562003166f].

@@ -110,10 +110,20 @@
 static int same_dline(DLine *pA, DLine *pB){
   return pA->h==pB->h && memcmp(pA->z,pB->z,pA->h & LENGTH_MASK)==0;
 }
 
 /*
+** Append a single line of "diff" output to pOut.
+*/
+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);
+}
+
+
+/*
 ** 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,
@@ -237,10 +247,11 @@
     return 0;
   }
 
   szM = 0;
   MAX = X>Y ? X : Y;
+  if( MAX>2000 ) MAX = 2000;
   for(d=0; go && d<=MAX; d++){
     if( szM<d+1 ){
       szM += szM + 10;
       M = realloc(M, sizeof(M[0])*szM);
       if( M==0 ){
@@ -414,31 +425,31 @@
       /* Show the initial common area */
       a += skip;
       b += skip;
       m = R[r] - skip;
       for(j=0; j<m; j++){
-        blob_appendf(pOut," %.*s\n", A[a+j].h & LENGTH_MASK, A[a+j].z);
+        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++){
-          blob_appendf(pOut,"-%.*s\n", A[a+j].h & LENGTH_MASK, A[a+j].z);
+          appendDiffLine(pOut, "-", &A[a+j]);
         }
         a += m;
         m = R[r+i*3+2];
         for(j=0; j<m; j++){
-          blob_appendf(pOut,"+%.*s\n", B[b+j].h & LENGTH_MASK, B[b+j].z);
+          appendDiffLine(pOut, "+", &B[b+j]);
         }
         b += m;
         if( i<nr-1 ){
           m = R[r+i*3+3];
           for(j=0; j<m; j++){
-            blob_appendf(pOut," %.*s\n", B[b+j].h & LENGTH_MASK, B[b+j].z);
+            appendDiffLine(pOut, " ", &B[b+j]);
           }
           b += m;
           a += m;
         }
       }
@@ -446,11 +457,11 @@
       /* 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," %.*s\n", B[b+j].h & LENGTH_MASK, B[b+j].z);
+        appendDiffLine(pOut, " ", &B[b+j]);
       }
     }
     free(R);
     R = 0;
   }