LCOV - code coverage report
Current view: top level - libpkg - diff.c (source / functions) Hit Total Coverage
Test: rapport Lines: 138 213 64.8 %
Date: 2021-12-10 16:22:55 Functions: 9 10 90.0 %
Branches: 72 138 52.2 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            : ** Copyright (c) 2007 D. Richard Hipp
       3                 :            : **
       4                 :            : ** This program is free software; you can redistribute it and/or
       5                 :            : ** modify it under the terms of the Simplified BSD License (also
       6                 :            : ** known as the "2-Clause License" or "FreeBSD License".)
       7                 :            : 
       8                 :            : ** This program is distributed in the hope that it will be useful,
       9                 :            : ** but without any warranty; without even the implied warranty of
      10                 :            : ** merchantability or fitness for a particular purpose.
      11                 :            : **
      12                 :            : ** Author contact information:
      13                 :            : **   drh@hwaci.com
      14                 :            : **   http://www.hwaci.com/drh/
      15                 :            : **
      16                 :            : *******************************************************************************
      17                 :            : **
      18                 :            : ** This file contains code used to compute a "diff" between two
      19                 :            : ** text files.
      20                 :            : */
      21                 :            : #include <sys/types.h>
      22                 :            : 
      23                 :            : #include <string.h>
      24                 :            : #include <stdlib.h>
      25                 :            : 
      26                 :            : #include "private/utils.h"
      27                 :            : #include "xmalloc.h"
      28                 :            : 
      29                 :            : /*
      30                 :            : ** Maximum length of a line in a text file, in bytes.  (2**13 = 8192 bytes)
      31                 :            : */
      32                 :            : #define LENGTH_MASK_SZ  13
      33                 :            : #define LENGTH_MASK     ((1<<LENGTH_MASK_SZ)-1)
      34                 :            : 
      35                 :            : /*
      36                 :            : ** Information about each line of a file being diffed.
      37                 :            : **
      38                 :            : ** The lower LENGTH_MASK_SZ bits of the hash (DLine.h) are the length
      39                 :            : ** of the line.  If any line is longer than LENGTH_MASK characters,
      40                 :            : ** the file is considered binary.
      41                 :            : */
      42                 :            : typedef struct DLine DLine;
      43                 :            : struct DLine {
      44                 :            :   const char *z;        /* The text of the line */
      45                 :            :   unsigned int h;       /* Hash of the line */
      46                 :            :   unsigned short indent;  /* Indent of the line. Only !=0 with -w/-Z option */
      47                 :            :   unsigned short n;     /* number of bytes */
      48                 :            :   unsigned int iNext;   /* 1+(Index of next line with same the same hash) */
      49                 :            : 
      50                 :            :   /* an array of DLine elements serves two purposes.  The fields
      51                 :            :   ** above are one per line of input text.  But each entry is also
      52                 :            :   ** a bucket in a hash table, as follows: */
      53                 :            :   unsigned int iHash;   /* 1+(first entry in the hash chain) */
      54                 :            : };
      55                 :            : 
      56                 :            : /*
      57                 :            : ** Length of a dline
      58                 :            : */
      59                 :            : #define LENGTH(X)   ((X)->n)
      60                 :            : 
      61                 :            : /*
      62                 :            : ** A context for running a raw diff.
      63                 :            : **
      64                 :            : ** The aEdit[] array describes the raw diff.  Each triple of integers in
      65                 :            : ** aEdit[] means:
      66                 :            : **
      67                 :            : **   (1) COPY:   Number of lines aFrom and aTo have in common
      68                 :            : **   (2) DELETE: Number of lines found only in aFrom
      69                 :            : **   (3) INSERT: Number of lines found only in aTo
      70                 :            : **
      71                 :            : ** The triples repeat until all lines of both aFrom and aTo are accounted
      72                 :            : ** for.
      73                 :            : */
      74                 :            : typedef struct DContext DContext;
      75                 :            : struct DContext {
      76                 :            :   int *aEdit;        /* Array of copy/delete/insert triples */
      77                 :            :   int nEdit;         /* Number of integers (3x num of triples) in aEdit[] */
      78                 :            :   int nEditAlloc;    /* Space allocated for aEdit[] */
      79                 :            :   DLine *aFrom;      /* File on left side of the diff */
      80                 :            :   int nFrom;         /* Number of lines in aFrom[] */
      81                 :            :   DLine *aTo;        /* File on right side of the diff */
      82                 :            :   int nTo;           /* Number of lines in aTo[] */
      83                 :            :   int (*same_fn)(const DLine *, const DLine *); /* Function to be used for comparing */
      84                 :            : };
      85                 :            : 
      86                 :            : /*
      87                 :            : ** Return an array of DLine objects containing a pointer to the
      88                 :            : ** start of each line and a hash of that line.  The lower
      89                 :            : ** bits of the hash store the length of each line.
      90                 :            : **
      91                 :            : ** Trailing whitespace is removed from each line.  2010-08-20:  Not any
      92                 :            : ** more.  If trailing whitespace is ignored, the "patch" command gets
      93                 :            : ** confused by the diff output.  Ticket [a9f7b23c2e376af5b0e5b]
      94                 :            : **
      95                 :            : ** Return 0 if the file is binary or contains a line that is
      96                 :            : ** too long.
      97                 :            : **
      98                 :            : ** Profiling show that in most cases this routine consumes the bulk of
      99                 :            : ** the CPU time on a diff.
     100                 :            : */
     101                 :        256 : static DLine *break_into_lines(char *z, int *pnLine){
     102                 :            :   int nLine, i, j, k, s, x;
     103                 :            :   unsigned int h, h2;
     104                 :            :   DLine *a;
     105                 :            : 
     106                 :        256 :   int n = strlen(z);
     107                 :            :   /* Count the number of lines.  Allocate space to hold
     108                 :            :   ** the returned array.
     109                 :            :   */
     110         [ +  + ]:       3768 :   for(i=j=0, nLine=1; i<n; i++, j++){
     111                 :       3512 :     int c = z[i];
     112         [ +  - ]:       3512 :     if( c==0 ){
     113                 :          0 :       return 0;
     114                 :            :     }
     115   [ +  +  +  + ]:       3512 :     if( c=='\n' && z[i+1]!=0 ){
     116                 :        342 :       nLine++;
     117         [ +  - ]:        342 :       if( j>LENGTH_MASK ){
     118                 :          0 :         return 0;
     119                 :            :       }
     120                 :        342 :       j = 0;
     121                 :        342 :     }
     122                 :       3512 :   }
     123         [ -  + ]:        256 :   if( j>LENGTH_MASK ){
     124                 :          0 :     return 0;
     125                 :            :   }
     126                 :        256 :   a = xcalloc(nLine, sizeof(a[0]) );
     127         [ -  + ]:        256 :   if( n==0 ){
     128                 :          0 :     *pnLine = 0;
     129                 :          0 :     return a;
     130                 :            :   }
     131                 :            : 
     132                 :            :   /* Fill in the array */
     133         [ +  + ]:        854 :   for(i=0; i<nLine; i++){
     134   [ +  +  +  + ]:       3655 :     for(j=0; z[j] && z[j]!='\n'; j++){}
     135                 :        598 :     a[i].z = z;
     136                 :        598 :     k = j;
     137                 :        598 :     a[i].n = k;
     138                 :        598 :     s = 0;
     139         [ +  + ]:       3655 :     for(h=0, x=s; x<k; x++){
     140                 :       3057 :       h = h ^ (h<<2) ^ z[x];
     141                 :       3057 :     }
     142                 :        598 :     a[i].indent = s;
     143                 :        598 :     a[i].h = h = (h<<LENGTH_MASK_SZ) | (k-s);
     144                 :        598 :     h2 = h % nLine;
     145                 :        598 :     a[i].iNext = a[h2].iHash;
     146                 :        598 :     a[h2].iHash = i+1;
     147                 :        598 :     z += j+1;
     148                 :        598 :   }
     149                 :            : 
     150                 :            :   /* Return results */
     151                 :        256 :   *pnLine = nLine;
     152                 :        256 :   return a;
     153                 :        256 : }
     154                 :            : 
     155                 :            : /*
     156                 :            : ** Return true if two DLine elements are identical.
     157                 :            : */
     158                 :        405 : static int same_dline(const DLine *pA, const DLine *pB){
     159         [ +  + ]:        405 :   return pA->h==pB->h && memcmp(pA->z,pB->z, pA->h&LENGTH_MASK)==0;
     160                 :            : }
     161                 :            : 
     162                 :            : 
     163                 :            : /*
     164                 :            : ** Minimum of two values
     165                 :            : */
     166         [ #  # ]:          0 : static int minInt(int a, int b){ return a<b ? a : b; }
     167                 :            : 
     168                 :            : /*
     169                 :            : ** Compute the optimal longest common subsequence (LCS) using an
     170                 :            : ** exhaustive search.  This version of the LCS is only used for
     171                 :            : ** shorter input strings since runtime is O(N*N) where N is the
     172                 :            : ** input string length.
     173                 :            : */
     174                 :         33 : static void optimalLCS(
     175                 :            :   DContext *p,               /* Two files being compared */
     176                 :            :   int iS1, int iE1,          /* Range of lines in p->aFrom[] */
     177                 :            :   int iS2, int iE2,          /* Range of lines in p->aTo[] */
     178                 :            :   int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
     179                 :            :   int *piSY, int *piEY       /* Write p->aTo[] common segment here */
     180                 :            : ){
     181                 :         33 :   int mxLength = 0;          /* Length of longest common subsequence */
     182                 :            :   int i, j;                  /* Loop counters */
     183                 :            :   int k;                     /* Length of a candidate subsequence */
     184                 :         33 :   int iSXb = iS1;            /* Best match so far */
     185                 :         33 :   int iSYb = iS2;            /* Best match so far */
     186                 :            : 
     187         [ +  + ]:         66 :   for(i=iS1; i<iE1-mxLength; i++){
     188         [ +  + ]:         66 :     for(j=iS2; j<iE2-mxLength; j++){
     189         [ -  + ]:         33 :       if( !p->same_fn(&p->aFrom[i], &p->aTo[j]) ) continue;
     190   [ #  #  #  # ]:          0 :       if( mxLength && !p->same_fn(&p->aFrom[i+mxLength], &p->aTo[j+mxLength]) ){
     191                 :          0 :         continue;
     192                 :            :       }
     193                 :          0 :       k = 1;
     194   [ #  #  #  #  :          0 :       while( i+k<iE1 && j+k<iE2 && p->same_fn(&p->aFrom[i+k],&p->aTo[j+k]) ){
                   #  # ]
     195                 :          0 :         k++;
     196                 :            :       }
     197         [ #  # ]:          0 :       if( k>mxLength ){
     198                 :          0 :         iSXb = i;
     199                 :          0 :         iSYb = j;
     200                 :          0 :         mxLength = k;
     201                 :          0 :       }
     202                 :          0 :     }
     203                 :         33 :   }
     204                 :         33 :   *piSX = iSXb;
     205                 :         33 :   *piEX = iSXb + mxLength;
     206                 :         33 :   *piSY = iSYb;
     207                 :         33 :   *piEY = iSYb + mxLength;
     208                 :         33 : }
     209                 :            : 
     210                 :            : /*
     211                 :            : ** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
     212                 :            : ** file and lines iS2 through iE2-1 of the aTo[] file.  Locate a sequence
     213                 :            : ** of lines in these two blocks that are exactly the same.  Return
     214                 :            : ** the bounds of the matching sequence.
     215                 :            : **
     216                 :            : ** If there are two or more possible answers of the same length, the
     217                 :            : ** returned sequence should be the one closest to the center of the
     218                 :            : ** input range.
     219                 :            : **
     220                 :            : ** Ideally, the common sequence should be the longest possible common
     221                 :            : ** sequence.  However, an exact computation of LCS is O(N*N) which is
     222                 :            : ** way too slow for larger files.  So this routine uses an O(N)
     223                 :            : ** heuristic approximation based on hashing that usually works about
     224                 :            : ** as well.  But if the O(N) algorithm doesn't get a good solution
     225                 :            : ** and N is not too large, we fall back to an exact solution by
     226                 :            : ** calling optimalLCS().
     227                 :            : */
     228                 :         33 : static void longestCommonSequence(
     229                 :            :   DContext *p,               /* Two files being compared */
     230                 :            :   int iS1, int iE1,          /* Range of lines in p->aFrom[] */
     231                 :            :   int iS2, int iE2,          /* Range of lines in p->aTo[] */
     232                 :            :   int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
     233                 :            :   int *piSY, int *piEY       /* Write p->aTo[] common segment here */
     234                 :            : ){
     235                 :            :   int i, j, k;               /* Loop counters */
     236                 :            :   int n;                     /* Loop limit */
     237                 :            :   DLine *pA, *pB;            /* Pointers to lines */
     238                 :            :   int iSX, iSY, iEX, iEY;    /* Current match */
     239                 :         33 :   int skew = 0;              /* How lopsided is the match */
     240                 :         33 :   int dist = 0;              /* Distance of match from center */
     241                 :            :   int mid;                   /* Center of the span */
     242                 :            :   int iSXb, iSYb, iEXb, iEYb;   /* Best match so far */
     243                 :            :   int iSXp, iSYp, iEXp, iEYp;   /* Previous match */
     244                 :            :   int64_t bestScore;      /* Best score so far */
     245                 :            :   int64_t score;          /* Score for current candidate LCS */
     246                 :            :   int span;                     /* combined width of the input sequences */
     247                 :            : 
     248                 :         33 :   span = (iE1 - iS1) + (iE2 - iS2);
     249                 :         33 :   bestScore = -10000;
     250                 :         33 :   iSXb = iSXp = iS1;
     251                 :         33 :   iEXb = iEXp = iS1;
     252                 :         33 :   iSYb = iSYp = iS2;
     253                 :         33 :   iEYb = iEYp = iS2;
     254                 :         33 :   mid = (iE1 + iS1)/2;
     255         [ +  + ]:         66 :   for(i=iS1; i<iE1; i++){
     256                 :         33 :     int limit = 0;
     257                 :         33 :     j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
     258         [ +  + ]:         99 :     while( j>0
     259   [ +  +  +  +  :         66 :       && (j-1<iS2 || j>=iE2 || !p->same_fn(&p->aFrom[i], &p->aTo[j-1]))
                   +  - ]
     260                 :            :     ){
     261         [ +  - ]:         33 :       if( limit++ > 10 ){
     262                 :          0 :         j = 0;
     263                 :          0 :         break;
     264                 :            :       }
     265                 :         33 :       j = p->aTo[j-1].iNext;
     266                 :            :     }
     267         [ -  + ]:         33 :     if( j==0 ) continue;
     268   [ #  #  #  #  :          0 :     if( i<iEXb && j>=iSYb && j<iEYb ) continue;
                   #  # ]
     269   [ #  #  #  #  :          0 :     if( i<iEXp && j>=iSYp && j<iEYp ) continue;
                   #  # ]
     270                 :          0 :     iSX = i;
     271                 :          0 :     iSY = j-1;
     272                 :          0 :     pA = &p->aFrom[iSX-1];
     273                 :          0 :     pB = &p->aTo[iSY-1];
     274                 :          0 :     n = minInt(iSX-iS1, iSY-iS2);
     275   [ #  #  #  # ]:          0 :     for(k=0; k<n && p->same_fn(pA,pB); k++, pA--, pB--){}
     276                 :          0 :     iSX -= k;
     277                 :          0 :     iSY -= k;
     278                 :          0 :     iEX = i+1;
     279                 :          0 :     iEY = j;
     280                 :          0 :     pA = &p->aFrom[iEX];
     281                 :          0 :     pB = &p->aTo[iEY];
     282                 :          0 :     n = minInt(iE1-iEX, iE2-iEY);
     283   [ #  #  #  # ]:          0 :     for(k=0; k<n && p->same_fn(pA,pB); k++, pA++, pB++){}
     284                 :          0 :     iEX += k;
     285                 :          0 :     iEY += k;
     286                 :          0 :     skew = (iSX-iS1) - (iSY-iS2);
     287         [ #  # ]:          0 :     if( skew<0 ) skew = -skew;
     288                 :          0 :     dist = (iSX+iEX)/2 - mid;
     289         [ #  # ]:          0 :     if( dist<0 ) dist = -dist;
     290                 :          0 :     score = (iEX - iSX)*(int64_t)span - (skew + dist);
     291         [ #  # ]:          0 :     if( score>bestScore ){
     292                 :          0 :       bestScore = score;
     293                 :          0 :       iSXb = iSX;
     294                 :          0 :       iSYb = iSY;
     295                 :          0 :       iEXb = iEX;
     296                 :          0 :       iEYb = iEY;
     297         [ #  # ]:          0 :     }else if( iEX>iEXp ){
     298                 :          0 :       iSXp = iSX;
     299                 :          0 :       iSYp = iSY;
     300                 :          0 :       iEXp = iEX;
     301                 :          0 :       iEYp = iEY;
     302                 :          0 :     }
     303                 :          0 :   }
     304   [ +  -  +  - ]:         33 :   if( iSXb==iEXb && (iE1-iS1)*(iE2-iS2)<400 ){
     305                 :            :     /* If no common sequence is found using the hashing heuristic and
     306                 :            :     ** the input is not too big, use the expensive exact solution */
     307                 :         33 :     optimalLCS(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
     308                 :         33 :   }else{
     309                 :          0 :     *piSX = iSXb;
     310                 :          0 :     *piSY = iSYb;
     311                 :          0 :     *piEX = iEXb;
     312                 :          0 :     *piEY = iEYb;
     313                 :            :   }
     314                 :         33 : }
     315                 :            : 
     316                 :            : /*
     317                 :            : ** Expand the size of aEdit[] array to hold at least nEdit elements.
     318                 :            : */
     319                 :        256 : static void expandEdit(DContext *p, int nEdit){
     320                 :        256 :   p->aEdit = xrealloc(p->aEdit, nEdit*sizeof(int));
     321                 :        256 :   p->nEditAlloc = nEdit;
     322                 :        256 : }
     323                 :            : 
     324                 :            : /*
     325                 :            : ** Append a new COPY/DELETE/INSERT triple.
     326                 :            : */
     327                 :        254 : static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){
     328                 :            :   /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
     329         [ +  + ]:        254 :   if( p->nEdit>=3 ){
     330         [ +  + ]:        126 :     if( p->aEdit[p->nEdit-1]==0 ){
     331         [ -  + ]:        106 :       if( p->aEdit[p->nEdit-2]==0 ){
     332                 :        106 :         p->aEdit[p->nEdit-3] += nCopy;
     333                 :        106 :         p->aEdit[p->nEdit-2] += nDel;
     334                 :        106 :         p->aEdit[p->nEdit-1] += nIns;
     335                 :        106 :         return;
     336                 :            :       }
     337         [ #  # ]:          0 :       if( nCopy==0 ){
     338                 :          0 :         p->aEdit[p->nEdit-2] += nDel;
     339                 :          0 :         p->aEdit[p->nEdit-1] += nIns;
     340                 :          0 :         return;
     341                 :            :       }
     342                 :          0 :     }
     343   [ -  +  #  # ]:         20 :     if( nCopy==0 && nDel==0 ){
     344                 :          0 :       p->aEdit[p->nEdit-1] += nIns;
     345                 :          0 :       return;
     346                 :            :     }
     347                 :         20 :   }
     348         [ +  + ]:        148 :   if( p->nEdit+3>p->nEditAlloc ){
     349                 :        128 :     expandEdit(p, p->nEdit*2 + 15);
     350         [ +  - ]:        128 :     if( p->aEdit==0 ) return;
     351                 :        128 :   }
     352                 :        148 :   p->aEdit[p->nEdit++] = nCopy;
     353                 :        148 :   p->aEdit[p->nEdit++] = nDel;
     354                 :        148 :   p->aEdit[p->nEdit++] = nIns;
     355                 :        254 : }
     356                 :            : 
     357                 :            : /*
     358                 :            : ** Do a single step in the difference.  Compute a sequence of
     359                 :            : ** copy/delete/insert steps that will convert lines iS1 through iE1-1 of
     360                 :            : ** the input into lines iS2 through iE2-1 of the output and write
     361                 :            : ** that sequence into the difference context.
     362                 :            : **
     363                 :            : ** The algorithm is to find a block of common text near the middle
     364                 :            : ** of the two segments being diffed.  Then recursively compute
     365                 :            : ** differences on the blocks before and after that common segment.
     366                 :            : ** Special cases apply if either input segment is empty or if the
     367                 :            : ** two segments have no text in common.
     368                 :            : */
     369                 :        128 : static void diff_step(DContext *p, int iS1, int iE1, int iS2, int iE2){
     370                 :            :   int iSX, iEX, iSY, iEY;
     371                 :            : 
     372         [ +  + ]:        128 :   if( iE1<=iS1 ){
     373                 :            :     /* The first segment is empty */
     374         [ +  + ]:         82 :     if( iE2>iS2 ){
     375                 :         67 :       appendTriple(p, 0, 0, iE2-iS2);
     376                 :         67 :     }
     377                 :         82 :     return;
     378                 :            :   }
     379         [ +  + ]:         46 :   if( iE2<=iS2 ){
     380                 :            :     /* The second segment is empty */
     381                 :         13 :     appendTriple(p, 0, iE1-iS1, 0);
     382                 :         13 :     return;
     383                 :            :   }
     384                 :            : 
     385                 :            :   /* Find the longest matching segment between the two sequences */
     386                 :         33 :   longestCommonSequence(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);
     387                 :            : 
     388         [ -  + ]:         33 :   if( iEX>iSX ){
     389                 :            :     /* A common segment has been found.
     390                 :            :     ** Recursively diff either side of the matching segment */
     391                 :          0 :     diff_step(p, iS1, iSX, iS2, iSY);
     392         [ #  # ]:          0 :     if( iEX>iSX ){
     393                 :          0 :       appendTriple(p, iEX - iSX, 0, 0);
     394                 :          0 :     }
     395                 :          0 :     diff_step(p, iEX, iE1, iEY, iE2);
     396                 :          0 :   }else{
     397                 :            :     /* The two segments have nothing in common.  Delete the first then
     398                 :            :     ** insert the second. */
     399                 :         33 :     appendTriple(p, 0, iE1-iS1, iE2-iS2);
     400                 :            :   }
     401                 :        128 : }
     402                 :            : 
     403                 :            : /*
     404                 :            : ** Compute the differences between two files already loaded into
     405                 :            : ** the DContext structure.
     406                 :            : **
     407                 :            : ** A divide and conquer technique is used.  We look for a large
     408                 :            : ** block of common text that is in the middle of both files.  Then
     409                 :            : ** compute the difference on those parts of the file before and
     410                 :            : ** after the common block.  This technique is fast, but it does
     411                 :            : ** not necessarily generate the minimum difference set.  On the
     412                 :            : ** other hand, we do not need a minimum difference set, only one
     413                 :            : ** that makes sense to human readers, which this algorithm does.
     414                 :            : **
     415                 :            : ** Any common text at the beginning and end of the two files is
     416                 :            : ** removed before starting the divide-and-conquer algorithm.
     417                 :            : */
     418                 :        128 : static void diff_all(DContext *p){
     419                 :            :   int mnE, iS, iE1, iE2;
     420                 :            : 
     421                 :            :   /* Carve off the common header and footer */
     422                 :        128 :   iE1 = p->nFrom;
     423                 :        128 :   iE2 = p->nTo;
     424   [ +  +  -  +  :        204 :   while( iE1>0 && iE2>0 && p->same_fn(&p->aFrom[iE1-1], &p->aTo[iE2-1]) ){
                   +  + ]
     425                 :         76 :     iE1--;
     426                 :         76 :     iE2--;
     427                 :            :   }
     428         [ +  + ]:        128 :   mnE = iE1<iE2 ? iE1 : iE2;
     429   [ +  +  +  + ]:        278 :   for(iS=0; iS<mnE && p->same_fn(&p->aFrom[iS],&p->aTo[iS]); iS++){}
     430                 :            : 
     431                 :            :   /* do the difference */
     432         [ +  + ]:        128 :   if( iS>0 ){
     433                 :        106 :     appendTriple(p, iS, 0, 0);
     434                 :        106 :   }
     435                 :        128 :   diff_step(p, iS, iE1, iS, iE2);
     436         [ +  + ]:        128 :   if( iE1<p->nFrom ){
     437                 :         35 :     appendTriple(p, p->nFrom - iE1, 0, 0);
     438                 :         35 :   }
     439                 :            : 
     440                 :            :   /* Terminate the COPY/DELETE/INSERT triples with three zeros */
     441                 :        128 :   expandEdit(p, p->nEdit+3);
     442         [ -  + ]:        128 :   if( p->aEdit ){
     443                 :        128 :     p->aEdit[p->nEdit++] = 0;
     444                 :        128 :     p->aEdit[p->nEdit++] = 0;
     445                 :        128 :     p->aEdit[p->nEdit++] = 0;
     446                 :        128 :   }
     447                 :        128 : }
     448                 :            : 
     449                 :            : /*
     450                 :            : ** Generate a report of the differences between files pA and pB.
     451                 :            : ** If pOut is not NULL then a unified diff is appended there.  It
     452                 :            : ** is assumed that pOut has already been initialized.  If pOut is
     453                 :            : ** NULL, then a pointer to an array of integers is returned.
     454                 :            : ** The integers come in triples.  For each triple,
     455                 :            : ** the elements are the number of lines copied, the number of
     456                 :            : ** lines deleted, and the number of lines inserted.  The vector
     457                 :            : ** is terminated by a triple of all zeros.
     458                 :            : **
     459                 :            : ** This diff utility does not work on binary files.  If a binary
     460                 :            : ** file is encountered, 0 is returned and pOut is written with
     461                 :            : ** text "cannot compute difference between binary files".
     462                 :            : */
     463                 :            : int *
     464                 :        128 : text_diff(
     465                 :            :   char *pA,   /* FROM file */
     466                 :            :   char *pB   /* TO file */
     467                 :            : ){
     468                 :            :   DContext c;
     469                 :            : 
     470                 :            :   /* Prepare the input files */
     471                 :        128 :   memset(&c, 0, sizeof(c));
     472                 :        128 :   c.same_fn = same_dline;
     473                 :        128 :   c.aFrom = break_into_lines(pA, &c.nFrom);
     474                 :        128 :   c.aTo = break_into_lines(pB, &c.nTo);
     475   [ +  -  +  - ]:        128 :   if( c.aFrom==0 || c.aTo==0 ){
     476                 :          0 :     free(c.aFrom);
     477                 :          0 :     free(c.aTo);
     478                 :          0 :     return 0;
     479                 :            :   }
     480                 :            : 
     481                 :            :   /* Compute the difference */
     482                 :        128 :   diff_all(&c);
     483                 :            :     /* If a context diff is not requested, then return the
     484                 :            :     ** array of COPY/DELETE/INSERT triples.
     485                 :            :     */
     486                 :        128 :     free(c.aFrom);
     487                 :        128 :     free(c.aTo);
     488                 :        128 :     return c.aEdit;
     489                 :        128 : }

Generated by: LCOV version 1.15