0000: 2f 2a 0a 2a 2a 20 43 6f 70 79 72 69 67 68 74 20 /*.** Copyright
0010: 28 63 29 20 32 30 30 37 20 44 2e 20 52 69 63 68 (c) 2007 D. Rich
0020: 61 72 64 20 48 69 70 70 0a 2a 2a 0a 2a 2a 20 54 ard Hipp.**.** T
0030: 68 69 73 20 70 72 6f 67 72 61 6d 20 69 73 20 66 his program is f
0040: 72 65 65 20 73 6f 66 74 77 61 72 65 3b 20 79 6f ree software; yo
0050: 75 20 63 61 6e 20 72 65 64 69 73 74 72 69 62 75 u can redistribu
0060: 74 65 20 69 74 20 61 6e 64 2f 6f 72 0a 2a 2a 20 te it and/or.**
0070: 6d 6f 64 69 66 79 20 69 74 20 75 6e 64 65 72 20 modify it under
0080: 74 68 65 20 74 65 72 6d 73 20 6f 66 20 74 68 65 the terms of the
0090: 20 47 4e 55 20 47 65 6e 65 72 61 6c 20 50 75 62 GNU General Pub
00a0: 6c 69 63 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 76 lic.** License v
00b0: 65 72 73 69 6f 6e 20 32 20 61 73 20 70 75 62 6c ersion 2 as publ
00c0: 69 73 68 65 64 20 62 79 20 74 68 65 20 46 72 65 ished by the Fre
00d0: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
00e0: 61 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 ation..**.** Thi
00f0: 73 20 70 72 6f 67 72 61 6d 20 69 73 20 64 69 73 s program is dis
0100: 74 72 69 62 75 74 65 64 20 69 6e 20 74 68 65 20 tributed in the
0110: 68 6f 70 65 20 74 68 61 74 20 69 74 20 77 69 6c hope that it wil
0120: 6c 20 62 65 20 75 73 65 66 75 6c 2c 0a 2a 2a 20 l be useful,.**
0130: 62 75 74 20 57 49 54 48 4f 55 54 20 41 4e 59 20 but WITHOUT ANY
0140: 57 41 52 52 41 4e 54 59 3b 20 77 69 74 68 6f 75 WARRANTY; withou
0150: 74 20 65 76 65 6e 20 74 68 65 20 69 6d 70 6c 69 t even the impli
0160: 65 64 20 77 61 72 72 61 6e 74 79 20 6f 66 0a 2a ed warranty of.*
0170: 2a 20 4d 45 52 43 48 41 4e 54 41 42 49 4c 49 54 * MERCHANTABILIT
0180: 59 20 6f 72 20 46 49 54 4e 45 53 53 20 46 4f 52 Y or FITNESS FOR
0190: 20 41 20 50 41 52 54 49 43 55 4c 41 52 20 50 55 A PARTICULAR PU
01a0: 52 50 4f 53 45 2e 20 20 53 65 65 20 74 68 65 20 RPOSE. See the
01b0: 47 4e 55 0a 2a 2a 20 47 65 6e 65 72 61 6c 20 50 GNU.** General P
01c0: 75 62 6c 69 63 20 4c 69 63 65 6e 73 65 20 66 6f ublic License fo
01d0: 72 20 6d 6f 72 65 20 64 65 74 61 69 6c 73 2e 0a r more details..
01e0: 2a 2a 20 0a 2a 2a 20 59 6f 75 20 73 68 6f 75 6c ** .** You shoul
01f0: 64 20 68 61 76 65 20 72 65 63 65 69 76 65 64 20 d have received
0200: 61 20 63 6f 70 79 20 6f 66 20 74 68 65 20 47 4e a copy of the GN
0210: 55 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 U General Public
0220: 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 61 6c 6f 6e .** License alon
0230: 67 20 77 69 74 68 20 74 68 69 73 20 6c 69 62 72 g with this libr
0240: 61 72 79 3b 20 69 66 20 6e 6f 74 2c 20 77 72 69 ary; if not, wri
0250: 74 65 20 74 6f 20 74 68 65 0a 2a 2a 20 46 72 65 te to the.** Fre
0260: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
0270: 61 74 69 6f 6e 2c 20 49 6e 63 2e 2c 20 35 39 20 ation, Inc., 59
0280: 54 65 6d 70 6c 65 20 50 6c 61 63 65 20 2d 20 53 Temple Place - S
0290: 75 69 74 65 20 33 33 30 2c 0a 2a 2a 20 42 6f 73 uite 330,.** Bos
02a0: 74 6f 6e 2c 20 4d 41 20 20 30 32 31 31 31 2d 31 ton, MA 02111-1
02b0: 33 30 37 2c 20 55 53 41 2e 0a 2a 2a 0a 2a 2a 20 307, USA..**.**
02c0: 41 75 74 68 6f 72 20 63 6f 6e 74 61 63 74 20 69 Author contact i
02d0: 6e 66 6f 72 6d 61 74 69 6f 6e 3a 0a 2a 2a 20 20 nformation:.**
02e0: 20 64 72 68 40 68 77 61 63 69 2e 63 6f 6d 0a 2a drh@hwaci.com.*
02f0: 2a 20 20 20 68 74 74 70 3a 2f 2f 77 77 77 2e 68 * http://www.h
0300: 77 61 63 69 2e 63 6f 6d 2f 64 72 68 2f 0a 2a 2a waci.com/drh/.**
0310: 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a .***************
0320: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0330: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0340: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0350: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0360: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 .**.** This file
0370: 20 63 6f 6e 74 61 69 6e 73 20 63 6f 64 65 20 75 contains code u
0380: 73 65 64 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 sed to implement
0390: 20 22 64 69 66 66 22 20 6f 70 65 72 61 74 6f 72 "diff" operator
03a0: 73 2e 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 s..*/.#include "
03b0: 63 6f 6e 66 69 67 2e 68 22 0a 23 69 6e 63 6c 75 config.h".#inclu
03c0: 64 65 20 22 64 69 66 66 2e 68 22 0a 23 69 6e 63 de "diff.h".#inc
03d0: 6c 75 64 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a lude <assert.h>.
03e0: 0a 2f 2a 0a 2a 2a 20 49 6e 66 6f 72 6d 61 74 69 ./*.** Informati
03f0: 6f 6e 20 61 62 6f 75 74 20 65 61 63 68 20 6c 69 on about each li
0400: 6e 65 20 6f 66 20 61 20 66 69 6c 65 20 62 65 69 ne of a file bei
0410: 6e 67 20 64 69 66 66 65 64 2e 0a 2a 2f 0a 74 79 ng diffed..*/.ty
0420: 70 65 64 65 66 20 73 74 72 75 63 74 20 44 4c 69 pedef struct DLi
0430: 6e 65 20 44 4c 69 6e 65 3b 0a 73 74 72 75 63 74 ne DLine;.struct
0440: 20 44 4c 69 6e 65 20 7b 0a 20 20 63 6f 6e 73 74 DLine {. const
0450: 20 63 68 61 72 20 2a 7a 3b 20 20 20 20 2f 2a 20 char *z; /*
0460: 54 68 65 20 74 65 78 74 20 6f 66 20 74 68 65 20 The text of the
0470: 6c 69 6e 65 20 2a 2f 0a 20 20 75 6e 73 69 67 6e line */. unsign
0480: 65 64 20 69 6e 74 20 68 3b 20 20 20 2f 2a 20 48 ed int h; /* H
0490: 61 73 68 20 6f 66 20 74 68 65 20 6c 69 6e 65 20 ash of the line
04a0: 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 42 72 65 */.};../*.** Bre
04b0: 61 6b 20 61 20 62 6c 6f 62 20 69 6e 74 6f 20 6c ak a blob into l
04c0: 69 6e 65 73 20 62 79 20 63 6f 6e 76 65 72 74 69 ines by converti
04d0: 6e 67 20 65 61 63 68 20 5c 6e 20 69 6e 74 6f 20 ng each \n into
04e0: 61 20 5c 30 30 30 20 61 6e 64 0a 2a 2a 20 63 72 a \000 and.** cr
04f0: 65 61 74 69 6e 67 20 70 6f 69 6e 74 65 72 73 20 eating pointers
0500: 74 6f 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 to the beginning
0510: 20 6f 66 20 65 61 63 68 20 6c 69 6e 65 2e 0a 2a of each line..*
0520: 2f 0a 73 74 61 74 69 63 20 44 4c 69 6e 65 20 2a /.static DLine *
0530: 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e 65 73 break_into_lines
0540: 28 63 68 61 72 20 2a 7a 2c 20 69 6e 74 20 2a 70 (char *z, int *p
0550: 6e 4c 69 6e 65 29 7b 0a 20 20 69 6e 74 20 6e 4c nLine){. int nL
0560: 69 6e 65 2c 20 69 2c 20 6a 3b 0a 20 20 75 6e 73 ine, i, j;. uns
0570: 69 67 6e 65 64 20 69 6e 74 20 68 3b 0a 20 20 44 igned int h;. D
0580: 4c 69 6e 65 20 2a 61 3b 0a 20 20 66 6f 72 28 69 Line *a;. for(i
0590: 3d 30 2c 20 6e 4c 69 6e 65 3d 31 3b 20 7a 5b 69 =0, nLine=1; z[i
05a0: 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 28 ]; i++){. if(
05b0: 20 7a 5b 69 5d 3d 3d 27 5c 6e 27 20 29 20 6e 4c z[i]=='\n' ) nL
05c0: 69 6e 65 2b 2b 3b 0a 20 20 7d 0a 20 20 61 20 3d ine++;. }. a =
05d0: 20 6d 61 6c 6c 6f 63 28 20 6e 4c 69 6e 65 2a 73 malloc( nLine*s
05e0: 69 7a 65 6f 66 28 61 5b 30 5d 29 20 29 3b 0a 20 izeof(a[0]) );.
05f0: 20 69 66 28 20 61 3d 3d 30 20 29 20 66 6f 73 73 if( a==0 ) foss
0600: 69 6c 5f 70 61 6e 69 63 28 22 6f 75 74 20 6f 66 il_panic("out of
0610: 20 6d 65 6d 6f 72 79 22 29 3b 0a 20 20 61 5b 30 memory");. a[0
0620: 5d 2e 7a 20 3d 20 7a 3b 0a 20 20 66 6f 72 28 69 ].z = z;. for(i
0630: 3d 30 2c 20 6a 3d 30 2c 20 68 3d 30 3b 20 7a 5b =0, j=0, h=0; z[
0640: 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 i]; i++){. if
0650: 28 20 7a 5b 69 5d 3d 3d 27 5c 6e 27 20 29 7b 0a ( z[i]=='\n' ){.
0660: 20 20 20 20 20 20 61 5b 6a 5d 2e 68 20 3d 20 68 a[j].h = h
0670: 3b 0a 20 20 20 20 20 20 6a 2b 2b 3b 0a 20 20 20 ;. j++;.
0680: 20 20 20 61 5b 6a 5d 2e 7a 20 3d 20 26 7a 5b 69 a[j].z = &z[i
0690: 2b 31 5d 3b 0a 20 20 20 20 20 20 7a 5b 69 5d 20 +1];. z[i]
06a0: 3d 20 30 3b 0a 20 20 20 20 20 20 68 20 3d 20 30 = 0;. h = 0
06b0: 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 ;. }else{.
06c0: 20 20 20 68 20 3d 20 68 20 5e 20 28 68 3c 3c 32 h = h ^ (h<<2
06d0: 29 20 5e 20 7a 5b 69 5d 3b 0a 20 20 20 20 7d 0a ) ^ z[i];. }.
06e0: 20 20 7d 0a 20 20 61 5b 6a 5d 2e 68 20 3d 20 68 }. a[j].h = h
06f0: 3b 0a 20 20 2a 70 6e 4c 69 6e 65 20 3d 20 6a 2b ;. *pnLine = j+
0700: 31 3b 0a 20 20 72 65 74 75 72 6e 20 61 3b 0a 7d 1;. return a;.}
0710: 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 74 ../*.** Return t
0720: 72 75 65 20 69 66 20 74 77 6f 20 44 4c 69 6e 65 rue if two DLine
0730: 20 65 6c 65 6d 65 6e 74 73 20 61 72 65 20 69 64 elements are id
0740: 65 6e 74 69 63 61 6c 2e 0a 2a 2f 0a 73 74 61 74 entical..*/.stat
0750: 69 63 20 69 6e 74 20 73 61 6d 65 5f 64 6c 69 6e ic int same_dlin
0760: 65 28 44 4c 69 6e 65 20 2a 70 41 2c 20 44 4c 69 e(DLine *pA, DLi
0770: 6e 65 20 2a 70 42 29 7b 0a 20 20 72 65 74 75 72 ne *pB){. retur
0780: 6e 20 70 41 2d 3e 68 3d 3d 70 42 2d 3e 68 20 26 n pA->h==pB->h &
0790: 26 20 73 74 72 63 6d 70 28 70 41 2d 3e 7a 2c 70 & strcmp(pA->z,p
07a0: 42 2d 3e 7a 29 3d 3d 30 3b 0a 7d 0a 0a 2f 2a 0a B->z)==0;.}../*.
07b0: 2a 2a 20 47 65 6e 65 72 61 74 65 20 61 20 75 6e ** Generate a un
07c0: 69 66 69 65 64 20 64 69 66 66 20 6f 66 20 74 77 ified diff of tw
07d0: 6f 20 62 6c 6f 62 73 2e 20 20 54 68 65 20 74 65 o blobs. The te
07e0: 78 74 20 6f 66 20 74 68 65 20 6f 72 69 67 69 6e xt of the origin
07f0: 61 6c 0a 2a 2a 20 74 77 6f 20 62 6c 6f 62 73 20 al.** two blobs
0800: 69 73 20 64 65 73 74 72 6f 79 65 64 20 62 79 20 is destroyed by
0810: 74 68 65 20 64 69 66 66 69 6e 67 20 70 72 6f 63 the diffing proc
0820: 65 73 73 2e 0a 2a 2f 0a 76 6f 69 64 20 75 6e 69 ess..*/.void uni
0830: 66 69 65 64 5f 64 69 66 66 28 42 6c 6f 62 20 2a fied_diff(Blob *
0840: 70 41 2c 20 42 6c 6f 62 20 2a 70 42 2c 20 69 6e pA, Blob *pB, in
0850: 74 20 6e 43 6f 6e 74 65 78 74 2c 20 42 6c 6f 62 t nContext, Blob
0860: 20 2a 70 4f 75 74 29 7b 0a 20 20 44 4c 69 6e 65 *pOut){. DLine
0870: 20 2a 70 44 41 2c 20 2a 70 44 42 2c 20 2a 41 2c *pDA, *pDB, *A,
0880: 20 2a 42 3b 0a 20 20 69 6e 74 20 6e 41 2c 20 6e *B;. int nA, n
0890: 42 2c 20 6e 41 70 31 3b 0a 20 20 69 6e 74 20 78 B, nAp1;. int x
08a0: 2c 20 79 3b 0a 20 20 69 6e 74 20 63 6e 74 3b 0a , y;. int cnt;.
08b0: 20 20 69 6e 74 20 69 2c 20 69 53 74 61 72 74 3b int i, iStart;
08c0: 0a 20 20 69 6e 74 20 2a 6d 3b 0a 0a 20 20 2f 2a . int *m;.. /*
08d0: 20 42 72 65 61 6b 20 74 68 65 20 74 77 6f 20 66 Break the two f
08e0: 69 6c 65 73 20 62 65 69 6e 67 20 64 69 66 66 65 iles being diffe
08f0: 64 20 69 6e 74 6f 20 69 6e 64 69 76 69 64 75 61 d into individua
0900: 6c 20 6c 69 6e 65 73 2e 0a 20 20 2a 2a 20 43 6f l lines.. ** Co
0910: 6d 70 75 74 65 20 68 61 73 68 65 73 20 6f 6e 20 mpute hashes on
0920: 65 61 63 68 20 6c 69 6e 65 20 66 6f 72 20 66 61 each line for fa
0930: 73 74 20 63 6f 6d 70 61 72 69 73 6f 6e 2e 0a 20 st comparison..
0940: 20 2a 2f 0a 20 20 70 44 41 20 3d 20 62 72 65 61 */. pDA = brea
0950: 6b 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f k_into_lines(blo
0960: 62 5f 73 74 72 28 70 41 29 2c 20 26 6e 41 29 3b b_str(pA), &nA);
0970: 0a 20 20 70 44 42 20 3d 20 62 72 65 61 6b 5f 69 . pDB = break_i
0980: 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 nto_lines(blob_s
0990: 74 72 28 70 42 29 2c 20 26 6e 42 29 3b 0a 0a 20 tr(pB), &nB);..
09a0: 20 2f 2a 20 52 65 6d 6f 76 65 20 63 6f 6d 6d 6f /* Remove commo
09b0: 6e 20 70 72 65 66 69 78 20 61 6e 64 20 73 75 66 n prefix and suf
09c0: 66 69 78 20 74 6f 20 68 65 6c 70 20 72 65 64 75 fix to help redu
09d0: 63 65 20 74 68 65 20 76 61 6c 75 65 0a 20 20 2a ce the value. *
09e0: 2a 20 6f 66 20 4e 20 69 6e 20 74 68 65 20 4f 28 * of N in the O(
09f0: 4e 5e 32 29 20 6d 69 6e 69 6d 75 6d 20 65 64 69 N^2) minimum edi
0a00: 74 20 64 69 73 74 61 6e 63 65 20 61 6c 67 6f 72 t distance algor
0a10: 69 74 68 6d 2e 0a 20 20 2a 2f 0a 20 20 66 6f 72 ithm.. */. for
0a20: 28 69 3d 30 3b 20 69 3c 6e 41 20 26 26 20 69 3c (i=0; i<nA && i<
0a30: 6e 42 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e 65 nB && same_dline
0a40: 28 26 70 44 41 5b 69 5d 2c 26 70 44 42 5b 69 5d (&pDA[i],&pDB[i]
0a50: 29 3b 20 69 2b 2b 29 7b 7d 0a 20 20 69 20 2d 3d ); i++){}. i -=
0a60: 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 69 66 28 nContext;. if(
0a70: 20 69 3c 30 20 29 20 69 20 3d 20 30 3b 0a 20 20 i<0 ) i = 0;.
0a80: 69 53 74 61 72 74 20 3d 20 69 3b 0a 20 20 41 20 iStart = i;. A
0a90: 3d 20 26 70 44 41 5b 69 53 74 61 72 74 5d 3b 0a = &pDA[iStart];.
0aa0: 20 20 42 20 3d 20 26 70 44 42 5b 69 53 74 61 72 B = &pDB[iStar
0ab0: 74 5d 3b 0a 20 20 6e 41 20 2d 3d 20 69 53 74 61 t];. nA -= iSta
0ac0: 72 74 3b 0a 20 20 6e 42 20 2d 3d 20 69 53 74 61 rt;. nB -= iSta
0ad0: 72 74 3b 0a 20 20 66 6f 72 28 69 3d 31 3b 20 69 rt;. for(i=1; i
0ae0: 3c 6e 41 20 26 26 20 69 3c 6e 42 20 26 26 20 73 <nA && i<nB && s
0af0: 61 6d 65 5f 64 6c 69 6e 65 28 26 41 5b 6e 41 2d ame_dline(&A[nA-
0b00: 69 5d 2c 26 42 5b 6e 42 2d 69 5d 29 3b 20 69 2b i],&B[nB-i]); i+
0b10: 2b 29 7b 7d 0a 20 20 69 20 2d 3d 20 6e 43 6f 6e +){}. i -= nCon
0b20: 74 65 78 74 3b 0a 20 20 69 66 28 20 69 3c 31 20 text;. if( i<1
0b30: 29 20 69 20 3d 20 31 3b 0a 20 20 69 2d 2d 3b 0a ) i = 1;. i--;.
0b40: 20 20 6e 41 20 2d 3d 20 69 3b 0a 20 20 6e 42 20 nA -= i;. nB
0b50: 2d 3d 20 69 3b 0a 20 20 0a 20 20 2f 2a 20 43 72 -= i;. . /* Cr
0b60: 65 61 74 65 20 74 68 65 20 6d 61 74 72 69 78 20 eate the matrix
0b70: 75 73 65 64 20 66 6f 72 20 74 68 65 20 6d 69 6e used for the min
0b80: 69 6d 75 6d 20 65 64 69 74 20 64 69 73 74 61 6e imum edit distan
0b90: 63 65 0a 20 20 2a 2a 20 63 61 6c 63 75 6c 61 74 ce. ** calculat
0ba0: 69 6f 6e 2e 0a 20 20 2a 2f 0a 20 20 6e 41 70 31 ion.. */. nAp1
0bb0: 20 3d 20 6e 41 20 2b 20 31 3b 0a 20 20 6d 20 3d = nA + 1;. m =
0bc0: 20 6d 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 malloc( sizeof(
0bd0: 6d 5b 30 5d 29 2a 28 6e 42 2b 31 29 2a 6e 41 70 m[0])*(nB+1)*nAp
0be0: 31 20 29 3b 0a 23 20 64 65 66 69 6e 65 20 4d 28 1 );.# define M(
0bf0: 58 2c 59 29 20 6d 5b 28 59 29 2a 6e 41 70 31 2b X,Y) m[(Y)*nAp1+
0c00: 28 58 29 5d 0a 0a 0a 20 20 2f 2a 20 46 69 6e 64 (X)]... /* Find
0c10: 20 74 68 65 20 6d 69 6e 69 6d 75 6d 20 65 64 69 the minimum edi
0c20: 74 20 64 69 73 74 61 6e 63 65 20 75 73 69 6e 67 t distance using
0c30: 20 57 61 67 6e 65 72 27 73 20 61 6c 67 6f 72 69 Wagner's algori
0c40: 74 68 6d 2e 0a 20 20 2a 2f 0a 20 20 66 6f 72 28 thm.. */. for(
0c50: 78 3d 30 3b 20 78 3c 3d 6e 41 3b 20 78 2b 2b 29 x=0; x<=nA; x++)
0c60: 7b 0a 20 20 20 20 4d 28 78 2c 30 29 20 3d 20 78 {. M(x,0) = x
0c70: 3b 0a 20 20 7d 0a 20 20 66 6f 72 28 79 3d 30 3b ;. }. for(y=0;
0c80: 20 79 3c 3d 6e 42 3b 20 79 2b 2b 29 7b 0a 20 20 y<=nB; y++){.
0c90: 20 20 4d 28 30 2c 79 29 20 3d 20 79 3b 0a 20 20 M(0,y) = y;.
0ca0: 7d 0a 20 20 66 6f 72 28 78 3d 31 3b 20 78 3c 3d }. for(x=1; x<=
0cb0: 6e 41 3b 20 78 2b 2b 29 7b 0a 20 20 20 20 66 6f nA; x++){. fo
0cc0: 72 28 79 3d 31 3b 20 79 3c 3d 6e 42 3b 20 79 2b r(y=1; y<=nB; y+
0cd0: 2b 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 65 20 +){. int e
0ce0: 3d 20 4d 28 78 2d 31 2c 79 29 20 2b 20 31 3b 0a = M(x-1,y) + 1;.
0cf0: 20 20 20 20 20 20 69 66 28 20 65 3e 4d 28 78 2c if( e>M(x,
0d00: 79 2d 31 29 2b 31 20 29 7b 0a 20 20 20 20 20 20 y-1)+1 ){.
0d10: 20 20 65 20 3d 20 4d 28 78 2c 79 2d 31 29 2b 31 e = M(x,y-1)+1
0d20: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 ;. }.
0d30: 69 66 28 20 65 3c 3d 4d 28 78 2d 31 2c 79 2d 31 if( e<=M(x-1,y-1
0d40: 29 20 29 7b 0a 20 20 20 20 20 20 20 20 4d 28 78 ) ){. M(x
0d50: 2c 79 29 20 3d 20 65 3b 0a 20 20 20 20 20 20 7d ,y) = e;. }
0d60: 65 6c 73 65 20 69 66 28 20 73 61 6d 65 5f 64 6c else if( same_dl
0d70: 69 6e 65 28 26 41 5b 78 2d 31 5d 2c 20 26 42 5b ine(&A[x-1], &B[
0d80: 79 2d 31 5d 29 20 29 7b 0a 20 20 20 20 20 20 20 y-1]) ){.
0d90: 20 4d 28 78 2c 79 29 20 3d 20 4d 28 78 2d 31 2c M(x,y) = M(x-1,
0da0: 79 2d 31 29 3b 0a 20 20 20 20 20 20 7d 65 6c 73 y-1);. }els
0db0: 65 7b 0a 20 20 20 20 20 20 20 20 4d 28 78 2c 79 e{. M(x,y
0dc0: 29 20 3d 20 65 3b 0a 20 20 20 20 20 20 7d 0a 20 ) = e;. }.
0dd0: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 57 }. }.. /* W
0de0: 61 6c 6b 20 62 61 63 6b 77 61 72 64 73 20 74 68 alk backwards th
0df0: 72 6f 75 67 68 20 74 68 65 20 57 61 67 6e 65 72 rough the Wagner
0e00: 20 61 6c 67 6f 72 69 74 68 6d 20 6d 61 74 72 69 algorithm matri
0e10: 78 20 74 6f 20 64 65 74 65 72 6d 69 6e 65 0a 20 x to determine.
0e20: 20 2a 2a 20 74 68 65 20 73 70 65 63 69 66 69 63 ** the specific
0e30: 20 65 64 69 74 73 20 74 68 61 74 20 67 69 76 65 edits that give
0e40: 20 74 68 65 20 6d 69 6e 69 6d 75 6d 20 65 64 69 the minimum edi
0e50: 74 20 64 69 73 74 61 6e 63 65 2e 20 20 4d 61 72 t distance. Mar
0e60: 6b 20 6f 75 72 0a 20 20 2a 2a 20 70 61 74 68 20 k our. ** path
0e70: 74 68 72 6f 75 67 68 20 74 68 65 20 6d 61 74 72 through the matr
0e80: 69 78 20 77 69 74 68 20 2d 31 2e 0a 20 20 2a 2f ix with -1.. */
0e90: 0a 20 20 78 20 3d 20 6e 41 3b 0a 20 20 79 20 3d . x = nA;. y =
0ea0: 20 6e 42 3b 0a 20 20 77 68 69 6c 65 28 20 78 3e nB;. while( x>
0eb0: 30 20 7c 7c 20 79 3e 30 20 29 7b 0a 20 20 20 20 0 || y>0 ){.
0ec0: 69 6e 74 20 76 20 3d 20 4d 28 78 2c 79 29 3b 0a int v = M(x,y);.
0ed0: 20 20 20 20 4d 28 78 2c 79 29 20 3d 20 2d 31 3b M(x,y) = -1;
0ee0: 0a 20 20 20 20 69 66 28 20 78 3d 3d 30 20 29 7b . if( x==0 ){
0ef0: 0a 20 20 20 20 20 20 79 2d 2d 3b 0a 20 20 20 20 . y--;.
0f00: 7d 65 6c 73 65 20 69 66 28 20 79 3d 3d 30 20 29 }else if( y==0 )
0f10: 7b 0a 20 20 20 20 20 20 78 2d 2d 3b 0a 20 20 20 {. x--;.
0f20: 20 7d 65 6c 73 65 20 69 66 28 20 4d 28 78 2c 79 }else if( M(x,y
0f30: 2d 31 29 2b 31 3d 3d 76 20 29 7b 0a 20 20 20 20 -1)+1==v ){.
0f40: 20 20 79 2d 2d 3b 0a 20 20 20 20 7d 65 6c 73 65 y--;. }else
0f50: 20 69 66 28 20 4d 28 78 2d 31 2c 79 29 2b 31 3d if( M(x-1,y)+1=
0f60: 3d 76 20 29 7b 0a 20 20 20 20 20 20 78 2d 2d 3b =v ){. x--;
0f70: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 . }else{.
0f80: 20 20 78 2d 2d 3b 0a 20 20 20 20 20 20 79 2d 2d x--;. y--
0f90: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 23 69 66 ;. }. }..#if
0fa0: 20 30 0a 66 6f 72 28 79 3d 30 3b 20 79 3c 3d 6e 0.for(y=0; y<=n
0fb0: 42 3b 20 79 2b 2b 29 7b 0a 20 20 66 6f 72 28 78 B; y++){. for(x
0fc0: 3d 30 3b 20 78 3c 3d 6e 41 3b 20 78 2b 2b 29 7b =0; x<=nA; x++){
0fd0: 0a 20 20 20 20 70 72 69 6e 74 66 28 22 20 25 32 . printf(" %2
0fe0: 64 22 2c 20 4d 28 78 2c 79 29 29 3b 0a 20 20 7d d", M(x,y));. }
0ff0: 0a 20 20 70 72 69 6e 74 66 28 22 5c 6e 22 29 3b . printf("\n");
1000: 0a 7d 0a 23 65 6e 64 69 66 0a 0a 20 20 78 20 3d .}.#endif.. x =
1010: 20 79 20 3d 20 30 3b 0a 20 20 63 6e 74 20 3d 20 y = 0;. cnt =
1020: 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 77 68 69 6c nContext;. whil
1030: 65 28 20 78 3c 6e 41 20 7c 7c 20 79 3c 6e 42 20 e( x<nA || y<nB
1040: 29 7b 0a 20 20 20 20 69 6e 74 20 74 31 3d 30 2c ){. int t1=0,
1050: 20 74 32 3d 30 3b 0a 20 20 20 20 69 66 28 20 28 t2=0;. if( (
1060: 74 31 20 3d 20 4d 28 78 2b 31 2c 79 29 29 3c 30 t1 = M(x+1,y))<0
1070: 20 7c 7c 20 28 74 32 20 3d 20 4d 28 78 2c 79 2b || (t2 = M(x,y+
1080: 31 29 29 3c 30 20 29 7b 0a 20 20 20 20 20 20 69 1))<0 ){. i
1090: 66 28 20 63 6e 74 3e 3d 6e 43 6f 6e 74 65 78 74 f( cnt>=nContext
10a0: 20 29 7b 0a 20 20 20 20 20 20 20 20 62 6c 6f 62 ){. blob
10b0: 5f 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 20 22 _appendf(pOut, "
10c0: 40 40 20 2d 25 64 20 2b 25 64 20 40 40 5c 6e 22 @@ -%d +%d @@\n"
10d0: 2c 20 0a 20 20 20 20 20 20 20 20 20 20 20 20 78 , . x
10e0: 2d 6e 43 6f 6e 74 65 78 74 2b 69 53 74 61 72 74 -nContext+iStart
10f0: 2b 32 2c 20 79 2d 6e 43 6f 6e 74 65 78 74 2b 69 +2, y-nContext+i
1100: 53 74 61 72 74 2b 32 29 3b 0a 20 20 20 20 20 20 Start+2);.
1110: 20 20 66 6f 72 28 69 3d 78 2d 6e 43 6f 6e 74 65 for(i=x-nConte
1120: 78 74 2b 31 3b 20 69 3c 78 3b 20 69 2b 2b 29 7b xt+1; i<x; i++){
1130: 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20 69 . if( i
1140: 3c 30 20 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 <0 ) continue;.
1150: 20 20 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 blob_ap
1160: 70 65 6e 64 66 28 70 4f 75 74 2c 20 22 20 25 73 pendf(pOut, " %s
1170: 5c 6e 22 2c 20 41 5b 69 5d 2e 7a 29 3b 0a 20 20 \n", A[i].z);.
1180: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a }. }.
1190: 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20 74 31 }. if( t1
11a0: 3c 30 20 29 7b 0a 20 20 20 20 20 20 62 6c 6f 62 <0 ){. blob
11b0: 5f 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 20 22 _appendf(pOut, "
11c0: 2d 25 73 5c 6e 22 2c 20 41 5b 78 5d 2e 7a 29 3b -%s\n", A[x].z);
11d0: 0a 20 20 20 20 20 20 78 2b 2b 3b 0a 20 20 20 20 . x++;.
11e0: 20 20 63 6e 74 20 3d 20 30 3b 0a 20 20 20 20 7d cnt = 0;. }
11f0: 65 6c 73 65 20 69 66 28 20 74 32 3c 30 20 29 7b else if( t2<0 ){
1200: 0a 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 . blob_appe
1210: 6e 64 66 28 70 4f 75 74 2c 20 22 2b 25 73 5c 6e ndf(pOut, "+%s\n
1220: 22 2c 20 42 5b 79 5d 2e 7a 29 3b 0a 20 20 20 20 ", B[y].z);.
1230: 20 20 79 2b 2b 3b 0a 20 20 20 20 20 20 63 6e 74 y++;. cnt
1240: 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 7b = 0;. }else{
1250: 0a 20 20 20 20 20 20 69 66 28 20 4d 28 78 2b 31 . if( M(x+1
1260: 2c 79 2b 31 29 3d 3d 28 2d 31 29 20 26 26 20 63 ,y+1)==(-1) && c
1270: 6e 74 3c 6e 43 6f 6e 74 65 78 74 20 29 7b 0a 20 nt<nContext ){.
1280: 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 blob_appe
1290: 6e 64 66 28 70 4f 75 74 2c 20 22 20 25 73 5c 6e ndf(pOut, " %s\n
12a0: 22 2c 20 41 5b 78 5d 2e 7a 29 3b 0a 20 20 20 20 ", A[x].z);.
12b0: 20 20 7d 0a 20 20 20 20 20 20 63 6e 74 2b 2b 3b }. cnt++;
12c0: 0a 20 20 20 20 20 20 78 2b 2b 3b 0a 20 20 20 20 . x++;.
12d0: 20 20 79 2b 2b 3b 0a 20 20 20 20 7d 0a 20 20 7d y++;. }. }
12e0: 0a 0a 20 20 2f 2a 20 43 6c 65 61 6e 75 70 20 61 .. /* Cleanup a
12f0: 6c 6c 6f 63 61 74 69 6f 6e 65 64 20 6d 65 6d 6f llocationed memo
1300: 72 79 20 2a 2f 0a 20 20 66 72 65 65 28 6d 29 3b ry */. free(m);
1310: 0a 20 20 66 72 65 65 28 70 44 41 29 3b 0a 20 20 . free(pDA);.
1320: 66 72 65 65 28 70 44 42 29 3b 0a 7d 0a 0a 2f 2a free(pDB);.}../*
1330: 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 73 .** COMMAND: tes
1340: 74 2d 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 t-diff.*/.void t
1350: 65 73 74 5f 64 69 66 66 5f 63 6d 64 28 76 6f 69 est_diff_cmd(voi
1360: 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c 20 62 2c d){. Blob a, b,
1370: 20 6f 75 74 3b 0a 20 20 69 66 28 20 67 2e 61 72 out;. if( g.ar
1380: 67 63 21 3d 34 20 29 20 75 73 61 67 65 28 22 46 gc!=4 ) usage("F
1390: 49 4c 45 31 20 46 49 4c 45 32 22 29 3b 0a 20 20 ILE1 FILE2");.
13a0: 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 blob_read_from_f
13b0: 69 6c 65 28 26 61 2c 20 67 2e 61 72 67 76 5b 32 ile(&a, g.argv[2
13c0: 5d 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f ]);. blob_read_
13d0: 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c 20 67 2e from_file(&b, g.
13e0: 61 72 67 76 5b 33 5d 29 3b 0a 20 20 62 6c 6f 62 argv[3]);. blob
13f0: 5f 7a 65 72 6f 28 26 6f 75 74 29 3b 0a 20 20 75 _zero(&out);. u
1400: 6e 69 66 69 65 64 5f 64 69 66 66 28 26 61 2c 20 nified_diff(&a,
1410: 26 62 2c 20 34 2c 20 26 6f 75 74 29 3b 0a 20 20 &b, 4, &out);.
1420: 62 6c 6f 62 5f 72 65 73 65 74 28 26 61 29 3b 0a blob_reset(&a);.
1430: 20 20 62 6c 6f 62 5f 72 65 73 65 74 28 26 62 29 blob_reset(&b)
1440: 3b 0a 20 20 70 72 69 6e 74 66 28 22 25 73 22 2c ;. printf("%s",
1450: 20 62 6c 6f 62 5f 73 74 72 28 26 6f 75 74 29 29 blob_str(&out))
1460: 3b 0a 20 20 62 6c 6f 62 5f 72 65 73 65 74 28 26 ;. blob_reset(&
1470: 6f 75 74 29 3b 0a 7d 0a 2f 2a 0a 2a 2a 20 43 4f out);.}./*.** CO
1480: 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 75 75 69 64 MMAND: test-uuid
1490: 2d 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 65 -diff.*/.void te
14a0: 73 74 5f 75 75 69 64 64 69 66 66 5f 63 6d 64 28 st_uuiddiff_cmd(
14b0: 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c void){. Blob a,
14c0: 20 62 2c 20 6f 75 74 3b 0a 20 20 69 6e 74 20 72 b, out;. int r
14d0: 69 64 41 2c 20 72 69 64 42 3b 0a 20 20 69 66 28 idA, ridB;. if(
14e0: 20 67 2e 61 72 67 63 21 3d 34 20 29 20 75 73 61 g.argc!=4 ) usa
14f0: 67 65 28 22 55 55 49 44 32 20 55 55 49 44 31 22 ge("UUID2 UUID1"
1500: 29 3b 0a 20 20 64 62 5f 6d 75 73 74 5f 62 65 5f );. db_must_be_
1510: 77 69 74 68 69 6e 5f 74 72 65 65 28 29 3b 0a 20 within_tree();.
1520: 20 72 69 64 41 20 3d 20 6e 61 6d 65 5f 74 6f 5f ridA = name_to_
1530: 72 69 64 28 67 2e 61 72 67 76 5b 32 5d 29 3b 0a rid(g.argv[2]);.
1540: 20 20 63 6f 6e 74 65 6e 74 5f 67 65 74 28 72 69 content_get(ri
1550: 64 41 2c 20 26 61 29 3b 0a 20 20 72 69 64 42 20 dA, &a);. ridB
1560: 3d 20 6e 61 6d 65 5f 74 6f 5f 72 69 64 28 67 2e = name_to_rid(g.
1570: 61 72 67 76 5b 33 5d 29 3b 0a 20 20 63 6f 6e 74 argv[3]);. cont
1580: 65 6e 74 5f 67 65 74 28 72 69 64 42 2c 20 26 62 ent_get(ridB, &b
1590: 29 3b 0a 20 20 62 6c 6f 62 5f 7a 65 72 6f 28 26 );. blob_zero(&
15a0: 6f 75 74 29 3b 0a 20 20 75 6e 69 66 69 65 64 5f out);. unified_
15b0: 64 69 66 66 28 26 61 2c 20 26 62 2c 20 34 2c 20 diff(&a, &b, 4,
15c0: 26 6f 75 74 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 &out);. blob_re
15d0: 73 65 74 28 26 61 29 3b 0a 20 20 62 6c 6f 62 5f set(&a);. blob_
15e0: 72 65 73 65 74 28 26 62 29 3b 0a 20 20 70 72 69 reset(&b);. pri
15f0: 6e 74 66 28 22 25 73 22 2c 20 62 6c 6f 62 5f 73 ntf("%s", blob_s
1600: 74 72 28 26 6f 75 74 29 29 3b 0a 20 20 62 6c 6f tr(&out));. blo
1610: 62 5f 72 65 73 65 74 28 26 6f 75 74 29 3b 0a 7d b_reset(&out);.}
1620: 0a .