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 53 69 6d 70 6c 69 66 69 65 64 20 42 53 44 20 Simplified BSD
00a0: 4c 69 63 65 6e 73 65 20 28 61 6c 73 6f 0a 2a 2a License (also.**
00b0: 20 6b 6e 6f 77 6e 20 61 73 20 74 68 65 20 22 32 known as the "2
00c0: 2d 43 6c 61 75 73 65 20 4c 69 63 65 6e 73 65 22 -Clause License"
00d0: 20 6f 72 20 22 46 72 65 65 42 53 44 20 4c 69 63 or "FreeBSD Lic
00e0: 65 6e 73 65 22 2e 29 0a 0a 2a 2a 20 54 68 69 73 ense".)..** This
00f0: 20 70 72 6f 67 72 61 6d 20 69 73 20 64 69 73 74 program is dist
0100: 72 69 62 75 74 65 64 20 69 6e 20 74 68 65 20 68 ributed in the h
0110: 6f 70 65 20 74 68 61 74 20 69 74 20 77 69 6c 6c ope that it will
0120: 20 62 65 20 75 73 65 66 75 6c 2c 0a 2a 2a 20 62 be useful,.** b
0130: 75 74 20 77 69 74 68 6f 75 74 20 61 6e 79 20 77 ut without any w
0140: 61 72 72 61 6e 74 79 3b 20 77 69 74 68 6f 75 74 arranty; without
0150: 20 65 76 65 6e 20 74 68 65 20 69 6d 70 6c 69 65 even the implie
0160: 64 20 77 61 72 72 61 6e 74 79 20 6f 66 0a 2a 2a d warranty of.**
0170: 20 6d 65 72 63 68 61 6e 74 61 62 69 6c 69 74 79 merchantability
0180: 20 6f 72 20 66 69 74 6e 65 73 73 20 66 6f 72 20 or fitness for
0190: 61 20 70 61 72 74 69 63 75 6c 61 72 20 70 75 72 a particular pur
01a0: 70 6f 73 65 2e 0a 2a 2a 0a 2a 2a 20 41 75 74 68 pose..**.** Auth
01b0: 6f 72 20 63 6f 6e 74 61 63 74 20 69 6e 66 6f 72 or contact infor
01c0: 6d 61 74 69 6f 6e 3a 0a 2a 2a 20 20 20 64 72 68 mation:.** drh
01d0: 40 68 77 61 63 69 2e 63 6f 6d 0a 2a 2a 20 20 20 @hwaci.com.**
01e0: 68 74 74 70 3a 2f 2f 77 77 77 2e 68 77 61 63 69 http://www.hwaci
01f0: 2e 63 6f 6d 2f 64 72 68 2f 0a 2a 2a 0a 2a 2a 2a .com/drh/.**.***
0200: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0210: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0220: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0230: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0240: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 2a 2a 0a ************.**.
0250: 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 63 6f 6e ** This file con
0260: 74 61 69 6e 73 20 63 6f 64 65 20 75 73 65 64 20 tains code used
0270: 74 6f 20 63 6f 6d 70 75 74 65 20 61 20 22 64 69 to compute a "di
0280: 66 66 22 20 62 65 74 77 65 65 6e 20 74 77 6f 0a ff" between two.
0290: 2a 2a 20 74 65 78 74 20 66 69 6c 65 73 2e 0a 2a ** text files..*
02a0: 2f 0a 23 69 6e 63 6c 75 64 65 20 22 63 6f 6e 66 /.#include "conf
02b0: 69 67 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 ig.h".#include "
02c0: 64 69 66 66 2e 68 22 0a 23 69 6e 63 6c 75 64 65 diff.h".#include
02d0: 20 3c 61 73 73 65 72 74 2e 68 3e 0a 0a 0a 2f 2a <assert.h>.../*
02e0: 0a 2a 2a 20 4d 61 78 69 6d 75 6d 20 6c 65 6e 67 .** Maximum leng
02f0: 74 68 20 6f 66 20 61 20 6c 69 6e 65 20 69 6e 20 th of a line in
0300: 61 20 74 65 78 74 20 66 69 6c 65 2e 20 20 28 38 a text file. (8
0310: 31 39 32 29 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 192).*/.#define
0320: 4c 45 4e 47 54 48 5f 4d 41 53 4b 5f 53 5a 20 20 LENGTH_MASK_SZ
0330: 31 33 0a 23 64 65 66 69 6e 65 20 4c 45 4e 47 54 13.#define LENGT
0340: 48 5f 4d 41 53 4b 20 20 20 20 20 28 28 31 3c 3c H_MASK ((1<<
0350: 4c 45 4e 47 54 48 5f 4d 41 53 4b 5f 53 5a 29 2d LENGTH_MASK_SZ)-
0360: 31 29 0a 0a 2f 2a 0a 2a 2a 20 49 6e 66 6f 72 6d 1)../*.** Inform
0370: 61 74 69 6f 6e 20 61 62 6f 75 74 20 65 61 63 68 ation about each
0380: 20 6c 69 6e 65 20 6f 66 20 61 20 66 69 6c 65 20 line of a file
0390: 62 65 69 6e 67 20 64 69 66 66 65 64 2e 0a 2a 2a being diffed..**
03a0: 0a 2a 2a 20 54 68 65 20 6c 6f 77 65 72 20 4c 45 .** The lower LE
03b0: 4e 47 54 48 5f 4d 41 53 4b 5f 53 5a 20 62 69 74 NGTH_MASK_SZ bit
03c0: 73 20 6f 66 20 74 68 65 20 68 61 73 68 20 28 44 s of the hash (D
03d0: 4c 69 6e 65 2e 68 29 20 61 72 65 20 74 68 65 20 Line.h) are the
03e0: 6c 65 6e 67 74 68 0a 2a 2a 20 6f 66 20 74 68 65 length.** of the
03f0: 20 6c 69 6e 65 2e 20 20 49 66 20 61 6e 79 20 6c line. If any l
0400: 69 6e 65 20 69 73 20 6c 6f 6e 67 65 72 20 74 68 ine is longer th
0410: 61 6e 20 4c 45 4e 47 54 48 5f 4d 41 53 4b 20 63 an LENGTH_MASK c
0420: 68 61 72 61 63 74 65 72 73 2c 0a 2a 2a 20 74 68 haracters,.** th
0430: 65 20 66 69 6c 65 20 69 73 20 63 6f 6e 73 69 64 e file is consid
0440: 65 72 65 64 20 62 69 6e 61 72 79 2e 0a 2a 2f 0a ered binary..*/.
0450: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 44 typedef struct D
0460: 4c 69 6e 65 20 44 4c 69 6e 65 3b 0a 73 74 72 75 Line DLine;.stru
0470: 63 74 20 44 4c 69 6e 65 20 7b 0a 20 20 63 6f 6e ct DLine {. con
0480: 73 74 20 63 68 61 72 20 2a 7a 3b 20 20 20 20 20 st char *z;
0490: 20 20 20 2f 2a 20 54 68 65 20 74 65 78 74 20 6f /* The text o
04a0: 66 20 74 68 65 20 6c 69 6e 65 20 2a 2f 0a 20 20 f the line */.
04b0: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 3b 20 unsigned int h;
04c0: 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 6f 66 /* Hash of
04d0: 20 74 68 65 20 6c 69 6e 65 20 2a 2f 0a 20 20 75 the line */. u
04e0: 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 4e 65 78 nsigned int iNex
04f0: 74 3b 20 20 20 2f 2a 20 31 2b 28 49 6e 64 65 78 t; /* 1+(Index
0500: 20 6f 66 20 6e 65 78 74 20 6c 69 6e 65 20 77 69 of next line wi
0510: 74 68 20 73 61 6d 65 20 74 68 65 20 73 61 6d 65 th same the same
0520: 20 68 61 73 68 29 20 2a 2f 0a 0a 20 20 2f 2a 20 hash) */.. /*
0530: 61 6e 20 61 72 72 61 79 20 6f 66 20 44 4c 69 6e an array of DLin
0540: 65 20 65 6c 65 6d 65 6e 74 73 20 73 65 72 76 69 e elements servi
0550: 63 65 73 20 74 77 6f 20 70 75 72 70 6f 73 65 73 ces two purposes
0560: 2e 20 20 54 68 65 20 66 69 65 6c 64 73 0a 20 20 . The fields.
0570: 2a 2a 20 61 62 6f 76 65 20 61 72 65 20 6f 6e 65 ** above are one
0580: 20 70 65 72 20 6c 69 6e 65 20 6f 66 20 69 6e 70 per line of inp
0590: 75 74 20 74 65 78 74 2e 20 20 42 75 74 20 65 61 ut text. But ea
05a0: 63 68 20 65 6e 74 72 79 20 69 73 20 61 6c 73 6f ch entry is also
05b0: 0a 20 20 2a 2a 20 61 20 62 75 63 6b 65 74 20 69 . ** a bucket i
05c0: 6e 20 61 20 68 61 73 68 20 74 61 62 6c 65 2c 20 n a hash table,
05d0: 61 73 20 66 6f 6c 6c 6f 77 73 3a 20 2a 2f 0a 20 as follows: */.
05e0: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 48 unsigned int iH
05f0: 61 73 68 3b 20 20 20 2f 2a 20 31 2b 28 66 69 72 ash; /* 1+(fir
0600: 73 74 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 st entry in the
0610: 68 61 73 68 20 63 68 61 69 6e 29 20 2a 2f 0a 7d hash chain) */.}
0620: 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 63 6f 6e 74 65 ;../*.** A conte
0630: 78 74 20 66 6f 72 20 72 75 6e 6e 69 6e 67 20 61 xt for running a
0640: 20 64 69 66 66 2e 0a 2a 2f 0a 74 79 70 65 64 65 diff..*/.typede
0650: 66 20 73 74 72 75 63 74 20 44 43 6f 6e 74 65 78 f struct DContex
0660: 74 20 44 43 6f 6e 74 65 78 74 3b 0a 73 74 72 75 t DContext;.stru
0670: 63 74 20 44 43 6f 6e 74 65 78 74 20 7b 0a 20 20 ct DContext {.
0680: 69 6e 74 20 2a 61 45 64 69 74 3b 20 20 20 20 20 int *aEdit;
0690: 20 20 20 2f 2a 20 41 72 72 61 79 20 6f 66 20 63 /* Array of c
06a0: 6f 70 79 2f 64 65 6c 65 74 65 2f 69 6e 73 65 72 opy/delete/inser
06b0: 74 20 74 72 69 70 6c 65 73 20 2a 2f 0a 20 20 69 t triples */. i
06c0: 6e 74 20 6e 45 64 69 74 3b 20 20 20 20 20 20 20 nt nEdit;
06d0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 69 /* Number of i
06e0: 6e 74 65 67 65 72 73 20 28 33 78 20 6e 75 6d 20 ntegers (3x num
06f0: 6f 66 20 74 72 69 70 6c 65 73 29 20 69 6e 20 61 of triples) in a
0700: 45 64 69 74 5b 5d 20 2a 2f 0a 20 20 69 6e 74 20 Edit[] */. int
0710: 6e 45 64 69 74 41 6c 6c 6f 63 3b 20 20 20 20 2f nEditAlloc; /
0720: 2a 20 53 70 61 63 65 20 61 6c 6c 6f 63 61 74 65 * Space allocate
0730: 64 20 66 6f 72 20 61 45 64 69 74 5b 5d 20 2a 2f d for aEdit[] */
0740: 0a 20 20 44 4c 69 6e 65 20 2a 61 46 72 6f 6d 3b . DLine *aFrom;
0750: 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 20 6f 6e /* File on
0760: 20 6c 65 66 74 20 73 69 64 65 20 6f 66 20 74 68 left side of th
0770: 65 20 64 69 66 66 20 2a 2f 0a 20 20 69 6e 74 20 e diff */. int
0780: 6e 46 72 6f 6d 3b 20 20 20 20 20 20 20 20 20 2f nFrom; /
0790: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 * Number of line
07a0: 73 20 69 6e 20 61 46 72 6f 6d 5b 5d 20 2a 2f 0a s in aFrom[] */.
07b0: 20 20 44 4c 69 6e 65 20 2a 61 54 6f 3b 20 20 20 DLine *aTo;
07c0: 20 20 20 20 20 2f 2a 20 46 69 6c 65 20 6f 6e 20 /* File on
07d0: 72 69 67 68 74 20 73 69 64 65 20 6f 66 20 74 68 right side of th
07e0: 65 20 64 69 66 66 20 2a 2f 0a 20 20 69 6e 74 20 e diff */. int
07f0: 6e 54 6f 3b 20 20 20 20 20 20 20 20 20 20 20 2f nTo; /
0800: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 * Number of line
0810: 73 20 69 6e 20 61 54 6f 5b 5d 20 2a 2f 0a 7d 3b s in aTo[] */.};
0820: 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 ../*.** Return a
0830: 6e 20 61 72 72 61 79 20 6f 66 20 44 4c 69 6e 65 n array of DLine
0840: 20 6f 62 6a 65 63 74 73 20 63 6f 6e 74 61 69 6e objects contain
0850: 69 6e 67 20 61 20 70 6f 69 6e 74 65 72 20 74 6f ing a pointer to
0860: 20 74 68 65 0a 2a 2a 20 73 74 61 72 74 20 6f 66 the.** start of
0870: 20 65 61 63 68 20 6c 69 6e 65 20 61 6e 64 20 61 each line and a
0880: 20 68 61 73 68 20 6f 66 20 74 68 61 74 20 6c 69 hash of that li
0890: 6e 65 2e 20 20 54 68 65 20 6c 6f 77 65 72 20 0a ne. The lower .
08a0: 2a 2a 20 62 69 74 73 20 6f 66 20 74 68 65 20 68 ** bits of the h
08b0: 61 73 68 20 73 74 6f 72 65 20 74 68 65 20 6c 65 ash store the le
08c0: 6e 67 74 68 20 6f 66 20 65 61 63 68 20 6c 69 6e ngth of each lin
08d0: 65 2e 0a 2a 2a 0a 2a 2a 20 54 72 61 69 6c 69 6e e..**.** Trailin
08e0: 67 20 77 68 69 74 65 73 70 61 63 65 20 69 73 20 g whitespace is
08f0: 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 65 61 63 removed from eac
0900: 68 20 6c 69 6e 65 2e 20 20 32 30 31 30 2d 30 38 h line. 2010-08
0910: 2d 32 30 3a 20 20 4e 6f 74 20 61 6e 79 0a 2a 2a -20: Not any.**
0920: 20 6d 6f 72 65 2e 20 20 49 66 20 74 72 61 69 6c more. If trail
0930: 69 6e 67 20 77 68 69 74 65 73 70 61 63 65 20 69 ing whitespace i
0940: 73 20 69 67 6e 6f 72 65 64 2c 20 74 68 65 20 22 s ignored, the "
0950: 70 61 74 63 68 22 20 63 6f 6d 6d 61 6e 64 20 67 patch" command g
0960: 65 74 73 0a 2a 2a 20 63 6f 6e 66 75 73 65 64 20 ets.** confused
0970: 62 79 20 74 68 65 20 64 69 66 66 20 6f 75 74 70 by the diff outp
0980: 75 74 2e 20 20 54 69 63 6b 65 74 20 5b 61 39 66 ut. Ticket [a9f
0990: 37 62 32 33 63 32 65 33 37 36 61 66 35 62 30 65 7b23c2e376af5b0e
09a0: 35 62 5d 0a 2a 2a 0a 2a 2a 20 52 65 74 75 72 6e 5b].**.** Return
09b0: 20 30 20 69 66 20 74 68 65 20 66 69 6c 65 20 69 0 if the file i
09c0: 73 20 62 69 6e 61 72 79 20 6f 72 20 63 6f 6e 74 s binary or cont
09d0: 61 69 6e 73 20 61 20 6c 69 6e 65 20 74 68 61 74 ains a line that
09e0: 20 69 73 0a 2a 2a 20 74 6f 6f 20 6c 6f 6e 67 2e is.** too long.
09f0: 0a 2a 2f 0a 73 74 61 74 69 63 20 44 4c 69 6e 65 .*/.static DLine
0a00: 20 2a 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e *break_into_lin
0a10: 65 73 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a es(const char *z
0a20: 2c 20 69 6e 74 20 6e 2c 20 69 6e 74 20 2a 70 6e , int n, int *pn
0a30: 4c 69 6e 65 2c 20 69 6e 74 20 69 67 6e 6f 72 65 Line, int ignore
0a40: 57 53 29 7b 0a 20 20 69 6e 74 20 6e 4c 69 6e 65 WS){. int nLine
0a50: 2c 20 69 2c 20 6a 2c 20 6b 2c 20 78 3b 0a 20 20 , i, j, k, x;.
0a60: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 2c 20 unsigned int h,
0a70: 68 32 3b 0a 20 20 44 4c 69 6e 65 20 2a 61 3b 0a h2;. DLine *a;.
0a80: 0a 20 20 2f 2a 20 43 6f 75 6e 74 20 74 68 65 20 . /* Count the
0a90: 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 2e number of lines.
0aa0: 20 20 41 6c 6c 6f 63 61 74 65 20 73 70 61 63 65 Allocate space
0ab0: 20 74 6f 20 68 6f 6c 64 0a 20 20 2a 2a 20 74 68 to hold. ** th
0ac0: 65 20 72 65 74 75 72 6e 65 64 20 61 72 72 61 79 e returned array
0ad0: 2e 0a 20 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 6a .. */. for(i=j
0ae0: 3d 30 2c 20 6e 4c 69 6e 65 3d 31 3b 20 69 3c 6e =0, nLine=1; i<n
0af0: 3b 20 69 2b 2b 2c 20 6a 2b 2b 29 7b 0a 20 20 20 ; i++, j++){.
0b00: 20 69 6e 74 20 63 20 3d 20 7a 5b 69 5d 3b 0a 20 int c = z[i];.
0b10: 20 20 20 69 66 28 20 63 3d 3d 30 20 29 7b 0a 20 if( c==0 ){.
0b20: 20 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 return 0;.
0b30: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 63 3d 3d }. if( c==
0b40: 27 5c 6e 27 20 26 26 20 7a 5b 69 2b 31 5d 21 3d '\n' && z[i+1]!=
0b50: 30 20 29 7b 0a 20 20 20 20 20 20 6e 4c 69 6e 65 0 ){. nLine
0b60: 2b 2b 3b 0a 20 20 20 20 20 20 69 66 28 20 6a 3e ++;. if( j>
0b70: 4c 45 4e 47 54 48 5f 4d 41 53 4b 20 29 7b 0a 20 LENGTH_MASK ){.
0b80: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 30 3b return 0;
0b90: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 6a . }. j
0ba0: 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a = 0;. }. }.
0bb0: 20 20 69 66 28 20 6a 3e 4c 45 4e 47 54 48 5f 4d if( j>LENGTH_M
0bc0: 41 53 4b 20 29 7b 0a 20 20 20 20 72 65 74 75 72 ASK ){. retur
0bd0: 6e 20 30 3b 0a 20 20 7d 0a 20 20 61 20 3d 20 66 n 0;. }. a = f
0be0: 6f 73 73 69 6c 5f 6d 61 6c 6c 6f 63 28 20 6e 4c ossil_malloc( nL
0bf0: 69 6e 65 2a 73 69 7a 65 6f 66 28 61 5b 30 5d 29 ine*sizeof(a[0])
0c00: 20 29 3b 0a 20 20 6d 65 6d 73 65 74 28 61 2c 20 );. memset(a,
0c10: 30 2c 20 6e 4c 69 6e 65 2a 73 69 7a 65 6f 66 28 0, nLine*sizeof(
0c20: 61 5b 30 5d 29 20 29 3b 0a 20 20 69 66 28 20 6e a[0]) );. if( n
0c30: 3d 3d 30 20 29 7b 0a 20 20 20 20 2a 70 6e 4c 69 ==0 ){. *pnLi
0c40: 6e 65 20 3d 20 30 3b 0a 20 20 20 20 72 65 74 75 ne = 0;. retu
0c50: 72 6e 20 61 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 rn a;. }.. /*
0c60: 46 69 6c 6c 20 69 6e 20 74 68 65 20 61 72 72 61 Fill in the arra
0c70: 79 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 3b 20 y */. for(i=0;
0c80: 69 3c 6e 4c 69 6e 65 3b 20 69 2b 2b 29 7b 0a 20 i<nLine; i++){.
0c90: 20 20 20 61 5b 69 5d 2e 7a 20 3d 20 7a 3b 0a 20 a[i].z = z;.
0ca0: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 7a 5b 6a 5d for(j=0; z[j]
0cb0: 20 26 26 20 7a 5b 6a 5d 21 3d 27 5c 6e 27 3b 20 && z[j]!='\n';
0cc0: 6a 2b 2b 29 7b 7d 0a 20 20 20 20 6b 20 3d 20 6a j++){}. k = j
0cd0: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 69 67 6e ;. while( ign
0ce0: 6f 72 65 57 53 20 26 26 20 6b 3e 30 20 26 26 20 oreWS && k>0 &&
0cf0: 66 6f 73 73 69 6c 5f 69 73 73 70 61 63 65 28 7a fossil_isspace(z
0d00: 5b 6b 2d 31 5d 29 20 29 7b 20 6b 2d 2d 3b 20 7d [k-1]) ){ k--; }
0d10: 0a 20 20 20 20 66 6f 72 28 68 3d 30 2c 20 78 3d . for(h=0, x=
0d20: 30 3b 20 78 3c 6b 3b 20 78 2b 2b 29 7b 0a 20 20 0; x<k; x++){.
0d30: 20 20 20 20 68 20 3d 20 68 20 5e 20 28 68 3c 3c h = h ^ (h<<
0d40: 32 29 20 5e 20 7a 5b 78 5d 3b 0a 20 20 20 20 7d 2) ^ z[x];. }
0d50: 0a 20 20 20 20 61 5b 69 5d 2e 68 20 3d 20 68 20 . a[i].h = h
0d60: 3d 20 28 68 3c 3c 4c 45 4e 47 54 48 5f 4d 41 53 = (h<<LENGTH_MAS
0d70: 4b 5f 53 5a 29 20 7c 20 6b 3b 3b 0a 20 20 20 20 K_SZ) | k;;.
0d80: 68 32 20 3d 20 68 20 25 20 6e 4c 69 6e 65 3b 0a h2 = h % nLine;.
0d90: 20 20 20 20 61 5b 69 5d 2e 69 4e 65 78 74 20 3d a[i].iNext =
0da0: 20 61 5b 68 32 5d 2e 69 48 61 73 68 3b 0a 20 20 a[h2].iHash;.
0db0: 20 20 61 5b 68 32 5d 2e 69 48 61 73 68 20 3d 20 a[h2].iHash =
0dc0: 69 2b 31 3b 0a 20 20 20 20 7a 20 2b 3d 20 6a 2b i+1;. z += j+
0dd0: 31 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 52 65 74 1;. }.. /* Ret
0de0: 75 72 6e 20 72 65 73 75 6c 74 73 20 2a 2f 0a 20 urn results */.
0df0: 20 2a 70 6e 4c 69 6e 65 20 3d 20 6e 4c 69 6e 65 *pnLine = nLine
0e00: 3b 0a 20 20 72 65 74 75 72 6e 20 61 3b 0a 7d 0a ;. return a;.}.
0e10: 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 74 72 ./*.** Return tr
0e20: 75 65 20 69 66 20 74 77 6f 20 44 4c 69 6e 65 20 ue if two DLine
0e30: 65 6c 65 6d 65 6e 74 73 20 61 72 65 20 69 64 65 elements are ide
0e40: 6e 74 69 63 61 6c 2e 0a 2a 2f 0a 73 74 61 74 69 ntical..*/.stati
0e50: 63 20 69 6e 74 20 73 61 6d 65 5f 64 6c 69 6e 65 c int same_dline
0e60: 28 44 4c 69 6e 65 20 2a 70 41 2c 20 44 4c 69 6e (DLine *pA, DLin
0e70: 65 20 2a 70 42 29 7b 0a 20 20 72 65 74 75 72 6e e *pB){. return
0e80: 20 70 41 2d 3e 68 3d 3d 70 42 2d 3e 68 20 26 26 pA->h==pB->h &&
0e90: 20 6d 65 6d 63 6d 70 28 70 41 2d 3e 7a 2c 70 42 memcmp(pA->z,pB
0ea0: 2d 3e 7a 2c 70 41 2d 3e 68 20 26 20 4c 45 4e 47 ->z,pA->h & LENG
0eb0: 54 48 5f 4d 41 53 4b 29 3d 3d 30 3b 0a 7d 0a 0a TH_MASK)==0;.}..
0ec0: 2f 2a 0a 2a 2a 20 41 70 70 65 6e 64 20 61 20 73 /*.** Append a s
0ed0: 69 6e 67 6c 65 20 6c 69 6e 65 20 6f 66 20 22 64 ingle line of "d
0ee0: 69 66 66 22 20 6f 75 74 70 75 74 20 74 6f 20 70 iff" output to p
0ef0: 4f 75 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 Out..*/.static v
0f00: 6f 69 64 20 61 70 70 65 6e 64 44 69 66 66 4c 69 oid appendDiffLi
0f10: 6e 65 28 42 6c 6f 62 20 2a 70 4f 75 74 2c 20 63 ne(Blob *pOut, c
0f20: 68 61 72 20 2a 7a 50 72 65 66 69 78 2c 20 44 4c har *zPrefix, DL
0f30: 69 6e 65 20 2a 70 4c 69 6e 65 29 7b 0a 20 20 62 ine *pLine){. b
0f40: 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f 75 74 2c lob_append(pOut,
0f50: 20 7a 50 72 65 66 69 78 2c 20 31 29 3b 0a 20 20 zPrefix, 1);.
0f60: 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f 75 74 blob_append(pOut
0f70: 2c 20 70 4c 69 6e 65 2d 3e 7a 2c 20 70 4c 69 6e , pLine->z, pLin
0f80: 65 2d 3e 68 20 26 20 4c 45 4e 47 54 48 5f 4d 41 e->h & LENGTH_MA
0f90: 53 4b 29 3b 0a 20 20 62 6c 6f 62 5f 61 70 70 65 SK);. blob_appe
0fa0: 6e 64 28 70 4f 75 74 2c 20 22 5c 6e 22 2c 20 31 nd(pOut, "\n", 1
0fb0: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 78 70 61 );.}../*.** Expa
0fc0: 6e 64 20 74 68 65 20 73 69 7a 65 20 6f 66 20 61 nd the size of a
0fd0: 45 64 69 74 5b 5d 20 61 72 72 61 79 20 74 6f 20 Edit[] array to
0fe0: 68 6f 6c 64 20 6e 45 64 69 74 20 65 6c 65 6d 65 hold nEdit eleme
0ff0: 6e 74 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 nts..*/.static v
1000: 6f 69 64 20 65 78 70 61 6e 64 45 64 69 74 28 44 oid expandEdit(D
1010: 43 6f 6e 74 65 78 74 20 2a 70 2c 20 69 6e 74 20 Context *p, int
1020: 6e 45 64 69 74 29 7b 0a 20 20 70 2d 3e 61 45 64 nEdit){. p->aEd
1030: 69 74 20 3d 20 66 6f 73 73 69 6c 5f 72 65 61 6c it = fossil_real
1040: 6c 6f 63 28 70 2d 3e 61 45 64 69 74 2c 20 6e 45 loc(p->aEdit, nE
1050: 64 69 74 2a 73 69 7a 65 6f 66 28 69 6e 74 29 29 dit*sizeof(int))
1060: 3b 0a 20 20 70 2d 3e 6e 45 64 69 74 41 6c 6c 6f ;. p->nEditAllo
1070: 63 20 3d 20 6e 45 64 69 74 3b 0a 7d 0a 0a 2f 2a c = nEdit;.}../*
1080: 0a 2a 2a 20 41 70 70 65 6e 64 20 61 20 6e 65 77 .** Append a new
1090: 20 43 4f 50 59 2f 44 45 4c 45 54 45 2f 49 4e 53 COPY/DELETE/INS
10a0: 45 52 54 20 74 72 69 70 6c 65 2e 0a 2a 2f 0a 73 ERT triple..*/.s
10b0: 74 61 74 69 63 20 76 6f 69 64 20 61 70 70 65 6e tatic void appen
10c0: 64 54 72 69 70 6c 65 28 44 43 6f 6e 74 65 78 74 dTriple(DContext
10d0: 20 2a 70 2c 20 69 6e 74 20 6e 43 6f 70 79 2c 20 *p, int nCopy,
10e0: 69 6e 74 20 6e 44 65 6c 2c 20 69 6e 74 20 6e 49 int nDel, int nI
10f0: 6e 73 29 7b 0a 20 20 2f 2a 20 70 72 69 6e 74 66 ns){. /* printf
1100: 28 22 41 50 50 45 4e 44 20 25 64 2f 25 64 2f 25 ("APPEND %d/%d/%
1110: 64 5c 6e 22 2c 20 6e 43 6f 70 79 2c 20 6e 44 65 d\n", nCopy, nDe
1120: 6c 2c 20 6e 49 6e 73 29 3b 20 2a 2f 0a 20 20 69 l, nIns); */. i
1130: 66 28 20 70 2d 3e 6e 45 64 69 74 3e 3d 33 20 29 f( p->nEdit>=3 )
1140: 7b 0a 20 20 20 20 69 66 28 20 70 2d 3e 61 45 64 {. if( p->aEd
1150: 69 74 5b 70 2d 3e 6e 45 64 69 74 2d 31 5d 3d 3d it[p->nEdit-1]==
1160: 30 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 70 0 ){. if( p
1170: 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 ->aEdit[p->nEdit
1180: 2d 32 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 -2]==0 ){.
1190: 20 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 p->aEdit[p->nE
11a0: 64 69 74 2d 33 5d 20 2b 3d 20 6e 43 6f 70 79 3b dit-3] += nCopy;
11b0: 0a 20 20 20 20 20 20 20 20 70 2d 3e 61 45 64 69 . p->aEdi
11c0: 74 5b 70 2d 3e 6e 45 64 69 74 2d 32 5d 20 2b 3d t[p->nEdit-2] +=
11d0: 20 6e 44 65 6c 3b 0a 20 20 20 20 20 20 20 20 70 nDel;. p
11e0: 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 ->aEdit[p->nEdit
11f0: 2d 31 5d 20 2b 3d 20 6e 49 6e 73 3b 0a 20 20 20 -1] += nIns;.
1200: 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 20 return;.
1210: 20 20 20 7d 0a 20 20 20 20 20 20 69 66 28 20 6e }. if( n
1220: 43 6f 70 79 3d 3d 30 20 29 7b 0a 20 20 20 20 20 Copy==0 ){.
1230: 20 20 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e p->aEdit[p->n
1240: 45 64 69 74 2d 32 5d 20 2b 3d 20 6e 44 65 6c 3b Edit-2] += nDel;
1250: 0a 20 20 20 20 20 20 20 20 70 2d 3e 61 45 64 69 . p->aEdi
1260: 74 5b 70 2d 3e 6e 45 64 69 74 2d 31 5d 20 2b 3d t[p->nEdit-1] +=
1270: 20 6e 49 6e 73 3b 0a 20 20 20 20 20 20 20 20 72 nIns;. r
1280: 65 74 75 72 6e 3b 0a 20 20 20 20 20 20 7d 0a 20 eturn;. }.
1290: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 6e 43 6f }. if( nCo
12a0: 70 79 3d 3d 30 20 26 26 20 6e 44 65 6c 3d 3d 30 py==0 && nDel==0
12b0: 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e 61 45 64 ){. p->aEd
12c0: 69 74 5b 70 2d 3e 6e 45 64 69 74 2d 31 5d 20 2b it[p->nEdit-1] +
12d0: 3d 20 6e 49 6e 73 3b 0a 20 20 20 20 20 20 72 65 = nIns;. re
12e0: 74 75 72 6e 3b 0a 20 20 20 20 7d 0a 20 20 7d 20 turn;. }. }
12f0: 20 0a 20 20 69 66 28 20 70 2d 3e 6e 45 64 69 74 . if( p->nEdit
1300: 2b 33 3e 70 2d 3e 6e 45 64 69 74 41 6c 6c 6f 63 +3>p->nEditAlloc
1310: 20 29 7b 0a 20 20 20 20 65 78 70 61 6e 64 45 64 ){. expandEd
1320: 69 74 28 70 2c 20 70 2d 3e 6e 45 64 69 74 2a 32 it(p, p->nEdit*2
1330: 20 2b 20 31 35 29 3b 0a 20 20 20 20 69 66 28 20 + 15);. if(
1340: 70 2d 3e 61 45 64 69 74 3d 3d 30 20 29 20 72 65 p->aEdit==0 ) re
1350: 74 75 72 6e 3b 0a 20 20 7d 0a 20 20 70 2d 3e 61 turn;. }. p->a
1360: 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 2b 2b 5d Edit[p->nEdit++]
1370: 20 3d 20 6e 43 6f 70 79 3b 0a 20 20 70 2d 3e 61 = nCopy;. p->a
1380: 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 2b 2b 5d Edit[p->nEdit++]
1390: 20 3d 20 6e 44 65 6c 3b 0a 20 20 70 2d 3e 61 45 = nDel;. p->aE
13a0: 64 69 74 5b 70 2d 3e 6e 45 64 69 74 2b 2b 5d 20 dit[p->nEdit++]
13b0: 3d 20 6e 49 6e 73 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a = nIns;.}.../*.*
13c0: 2a 20 47 69 76 65 6e 20 61 20 64 69 66 66 20 63 * Given a diff c
13d0: 6f 6e 74 65 78 74 20 69 6e 20 77 68 69 63 68 20 ontext in which
13e0: 74 68 65 20 61 45 64 69 74 5b 5d 20 61 72 72 61 the aEdit[] arra
13f0: 79 20 68 61 73 20 62 65 65 6e 20 66 69 6c 6c 65 y has been fille
1400: 64 0a 2a 2a 20 69 6e 2c 20 63 6f 6d 70 75 74 65 d.** in, compute
1410: 20 61 20 63 6f 6e 74 65 78 74 20 64 69 66 66 20 a context diff
1420: 69 6e 74 6f 20 70 4f 75 74 2e 0a 2a 2f 0a 73 74 into pOut..*/.st
1430: 61 74 69 63 20 76 6f 69 64 20 63 6f 6e 74 65 78 atic void contex
1440: 74 44 69 66 66 28 44 43 6f 6e 74 65 78 74 20 2a tDiff(DContext *
1450: 70 2c 20 42 6c 6f 62 20 2a 70 4f 75 74 2c 20 69 p, Blob *pOut, i
1460: 6e 74 20 6e 43 6f 6e 74 65 78 74 29 7b 0a 20 20 nt nContext){.
1470: 44 4c 69 6e 65 20 2a 41 3b 20 20 20 20 20 2f 2a DLine *A; /*
1480: 20 4c 65 66 74 20 73 69 64 65 20 6f 66 20 74 68 Left side of th
1490: 65 20 64 69 66 66 20 2a 2f 0a 20 20 44 4c 69 6e e diff */. DLin
14a0: 65 20 2a 42 3b 20 20 20 20 20 2f 2a 20 52 69 67 e *B; /* Rig
14b0: 68 74 20 73 69 64 65 20 6f 66 20 74 68 65 20 64 ht side of the d
14c0: 69 66 66 20 2a 2f 20 20 0a 20 20 69 6e 74 20 61 iff */ . int a
14d0: 20 3d 20 30 3b 20 20 20 20 2f 2a 20 49 6e 64 65 = 0; /* Inde
14e0: 78 20 6f 66 20 6e 65 78 74 20 6c 69 6e 65 20 69 x of next line i
14f0: 6e 20 41 5b 5d 20 2a 2f 0a 20 20 69 6e 74 20 62 n A[] */. int b
1500: 20 3d 20 30 3b 20 20 20 20 2f 2a 20 49 6e 64 65 = 0; /* Inde
1510: 78 20 6f 66 20 6e 65 78 74 20 6c 69 6e 65 20 69 x of next line i
1520: 6e 20 42 5b 5d 20 2a 2f 0a 20 20 69 6e 74 20 2a n B[] */. int *
1530: 52 3b 20 20 20 20 20 20 20 2f 2a 20 41 72 72 61 R; /* Arra
1540: 79 20 6f 66 20 43 4f 50 59 2f 44 45 4c 45 54 45 y of COPY/DELETE
1550: 2f 49 4e 53 45 52 54 20 74 72 69 70 6c 65 73 20 /INSERT triples
1560: 2a 2f 0a 20 20 69 6e 74 20 72 3b 20 20 20 20 20 */. int r;
1570: 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 6e 74 6f /* Index into
1580: 20 52 5b 5d 20 2a 2f 0a 20 20 69 6e 74 20 6e 72 R[] */. int nr
1590: 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 ; /* Numbe
15a0: 72 20 6f 66 20 43 4f 50 59 2f 44 45 4c 45 54 45 r of COPY/DELETE
15b0: 2f 49 4e 53 45 52 54 20 74 72 69 70 6c 65 73 20 /INSERT triples
15c0: 74 6f 20 70 72 6f 63 65 73 73 20 2a 2f 0a 20 20 to process */.
15d0: 69 6e 74 20 6d 78 72 3b 20 20 20 20 20 20 2f 2a int mxr; /*
15e0: 20 4d 61 78 69 6d 75 6d 20 76 61 6c 75 65 20 66 Maximum value f
15f0: 6f 72 20 72 20 2a 2f 0a 20 20 69 6e 74 20 6e 61 or r */. int na
1600: 2c 20 6e 62 3b 20 20 20 2f 2a 20 4e 75 6d 62 65 , nb; /* Numbe
1610: 72 20 6f 66 20 6c 69 6e 65 73 20 73 68 6f 77 6e r of lines shown
1620: 20 66 72 6f 6d 20 41 20 61 6e 64 20 42 20 2a 2f from A and B */
1630: 0a 20 20 69 6e 74 20 69 2c 20 6a 3b 20 20 20 20 . int i, j;
1640: 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 6e 74 65 72 /* Loop counter
1650: 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 3b 20 20 20 s */. int m;
1660: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f /* Number o
1670: 66 20 6c 69 6e 65 73 20 74 6f 20 6f 75 74 70 75 f lines to outpu
1680: 74 20 2a 2f 0a 20 20 69 6e 74 20 73 6b 69 70 3b t */. int skip;
1690: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f /* Number o
16a0: 66 20 6c 69 6e 65 73 20 74 6f 20 73 6b 69 70 20 f lines to skip
16b0: 2a 2f 0a 0a 20 20 41 20 3d 20 70 2d 3e 61 46 72 */.. A = p->aFr
16c0: 6f 6d 3b 0a 20 20 42 20 3d 20 70 2d 3e 61 54 6f om;. B = p->aTo
16d0: 3b 0a 20 20 52 20 3d 20 70 2d 3e 61 45 64 69 74 ;. R = p->aEdit
16e0: 3b 0a 20 20 6d 78 72 20 3d 20 70 2d 3e 6e 45 64 ;. mxr = p->nEd
16f0: 69 74 3b 0a 20 20 77 68 69 6c 65 28 20 6d 78 72 it;. while( mxr
1700: 3e 32 20 26 26 20 52 5b 6d 78 72 2d 31 5d 3d 3d >2 && R[mxr-1]==
1710: 30 20 26 26 20 52 5b 6d 78 72 2d 32 5d 3d 3d 30 0 && R[mxr-2]==0
1720: 20 29 7b 20 6d 78 72 20 2d 3d 20 33 3b 20 7d 0a ){ mxr -= 3; }.
1730: 20 20 66 6f 72 28 72 3d 30 3b 20 72 3c 6d 78 72 for(r=0; r<mxr
1740: 3b 20 72 20 2b 3d 20 33 2a 6e 72 29 7b 0a 20 20 ; r += 3*nr){.
1750: 20 20 2f 2a 20 46 69 67 75 72 65 20 6f 75 74 20 /* Figure out
1760: 68 6f 77 20 6d 61 6e 79 20 74 72 69 70 6c 65 73 how many triples
1770: 20 74 6f 20 73 68 6f 77 20 69 6e 20 61 20 73 69 to show in a si
1780: 6e 67 6c 65 20 62 6c 6f 63 6b 20 2a 2f 0a 20 20 ngle block */.
1790: 20 20 66 6f 72 28 6e 72 3d 31 3b 20 52 5b 72 2b for(nr=1; R[r+
17a0: 6e 72 2a 33 5d 3e 30 20 26 26 20 52 5b 72 2b 6e nr*3]>0 && R[r+n
17b0: 72 2a 33 5d 3c 6e 43 6f 6e 74 65 78 74 2a 32 3b r*3]<nContext*2;
17c0: 20 6e 72 2b 2b 29 7b 7d 0a 20 20 20 20 2f 2a 20 nr++){}. /*
17d0: 70 72 69 6e 74 66 28 22 72 3d 25 64 20 6e 72 3d printf("r=%d nr=
17e0: 25 64 5c 6e 22 2c 20 72 2c 20 6e 72 29 3b 20 2a %d\n", r, nr); *
17f0: 2f 0a 0a 20 20 20 20 2f 2a 20 46 6f 72 20 74 68 /.. /* For th
1800: 65 20 63 75 72 72 65 6e 74 20 62 6c 6f 63 6b 20 e current block
1810: 63 6f 6d 70 72 69 73 69 6e 67 20 6e 72 20 74 72 comprising nr tr
1820: 69 70 6c 65 73 2c 20 66 69 67 75 72 65 20 6f 75 iples, figure ou
1830: 74 0a 20 20 20 20 2a 2a 20 68 6f 77 20 6d 61 6e t. ** how man
1840: 79 20 6c 69 6e 65 73 20 6f 66 20 41 20 61 6e 64 y lines of A and
1850: 20 42 20 61 72 65 20 74 6f 20 62 65 20 64 69 73 B are to be dis
1860: 70 6c 61 79 65 64 0a 20 20 20 20 2a 2f 0a 20 20 played. */.
1870: 20 20 69 66 28 20 52 5b 72 5d 3e 6e 43 6f 6e 74 if( R[r]>nCont
1880: 65 78 74 20 29 7b 0a 20 20 20 20 20 20 6e 61 20 ext ){. na
1890: 3d 20 6e 62 20 3d 20 6e 43 6f 6e 74 65 78 74 3b = nb = nContext;
18a0: 0a 20 20 20 20 20 20 73 6b 69 70 20 3d 20 52 5b . skip = R[
18b0: 72 5d 20 2d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 r] - nContext;.
18c0: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
18d0: 6e 61 20 3d 20 6e 62 20 3d 20 52 5b 72 5d 3b 0a na = nb = R[r];.
18e0: 20 20 20 20 20 20 73 6b 69 70 20 3d 20 30 3b 0a skip = 0;.
18f0: 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 28 69 3d }. for(i=
1900: 30 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 0; i<nr; i++){.
1910: 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 na += R[r+i
1920: 2a 33 2b 31 5d 3b 0a 20 20 20 20 20 20 6e 62 20 *3+1];. nb
1930: 2b 3d 20 52 5b 72 2b 69 2a 33 2b 32 5d 3b 0a 20 += R[r+i*3+2];.
1940: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 52 5b 72 }. if( R[r
1950: 2b 6e 72 2a 33 5d 3e 6e 43 6f 6e 74 65 78 74 20 +nr*3]>nContext
1960: 29 7b 0a 20 20 20 20 20 20 6e 61 20 2b 3d 20 6e ){. na += n
1970: 43 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 6e Context;. n
1980: 62 20 2b 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 b += nContext;.
1990: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
19a0: 6e 61 20 2b 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b na += R[r+nr*3];
19b0: 0a 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 5b 72 . nb += R[r
19c0: 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 7d 0a 20 20 +nr*3];. }.
19d0: 20 20 66 6f 72 28 69 3d 31 3b 20 69 3c 6e 72 3b for(i=1; i<nr;
19e0: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 6e 61 20 i++){. na
19f0: 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 20 20 += R[r+i*3];.
1a00: 20 20 20 6e 62 20 2b 3d 20 52 5b 72 2b 69 2a 33 nb += R[r+i*3
1a10: 5d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 2f 2a 0a ];. }. /*.
1a20: 20 20 20 20 20 2a 20 49 66 20 74 68 65 20 70 61 * If the pa
1a30: 74 63 68 20 63 68 61 6e 67 65 73 20 61 6e 20 65 tch changes an e
1a40: 6d 70 74 79 20 66 69 6c 65 20 6f 72 20 72 65 73 mpty file or res
1a50: 75 6c 74 73 20 69 6e 20 61 6e 20 65 6d 70 74 79 ults in an empty
1a60: 20 66 69 6c 65 2c 0a 20 20 20 20 20 2a 20 74 68 file,. * th
1a70: 65 20 62 6c 6f 63 6b 20 68 65 61 64 65 72 20 6d e block header m
1a80: 75 73 74 20 75 73 65 20 30 2c 30 20 61 73 20 70 ust use 0,0 as p
1a90: 6f 73 69 74 69 6f 6e 20 69 6e 64 69 63 61 74 6f osition indicato
1aa0: 72 20 61 6e 64 20 6e 6f 74 20 31 2c 30 2e 0a 20 r and not 1,0..
1ab0: 20 20 20 20 2a 20 4f 74 68 65 72 77 69 73 65 2c * Otherwise,
1ac0: 20 70 61 74 63 68 20 77 6f 75 6c 64 20 62 65 20 patch would be
1ad0: 63 6f 6e 66 75 73 65 64 20 61 6e 64 20 6d 61 79 confused and may
1ae0: 20 72 65 6a 65 63 74 20 74 68 65 20 64 69 66 66 reject the diff
1af0: 2e 0a 20 20 20 20 20 2a 2f 0a 20 20 20 20 62 6c .. */. bl
1b00: 6f 62 5f 61 70 70 65 6e 64 66 28 70 4f 75 74 2c ob_appendf(pOut,
1b10: 22 40 40 20 2d 25 64 2c 25 64 20 2b 25 64 2c 25 "@@ -%d,%d +%d,%
1b20: 64 20 40 40 5c 6e 22 2c 0a 20 20 20 20 20 20 6e d @@\n",. n
1b30: 61 20 3f 20 61 2b 73 6b 69 70 2b 31 20 3a 20 30 a ? a+skip+1 : 0
1b40: 2c 20 6e 61 2c 0a 20 20 20 20 20 20 6e 62 20 3f , na,. nb ?
1b50: 20 62 2b 73 6b 69 70 2b 31 20 3a 20 30 2c 20 6e b+skip+1 : 0, n
1b60: 62 29 3b 0a 0a 20 20 20 20 2f 2a 20 53 68 6f 77 b);.. /* Show
1b70: 20 74 68 65 20 69 6e 69 74 69 61 6c 20 63 6f 6d the initial com
1b80: 6d 6f 6e 20 61 72 65 61 20 2a 2f 0a 20 20 20 20 mon area */.
1b90: 61 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 20 62 a += skip;. b
1ba0: 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 20 6d 20 += skip;. m
1bb0: 3d 20 52 5b 72 5d 20 2d 20 73 6b 69 70 3b 0a 20 = R[r] - skip;.
1bc0: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b for(j=0; j<m;
1bd0: 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 61 70 70 j++){. app
1be0: 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 4f 75 74 endDiffLine(pOut
1bf0: 2c 20 22 20 22 2c 20 26 41 5b 61 2b 6a 5d 29 3b , " ", &A[a+j]);
1c00: 0a 20 20 20 20 7d 0a 20 20 20 20 61 20 2b 3d 20 . }. a +=
1c10: 6d 3b 0a 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 0a m;. b += m;..
1c20: 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 /* Show the
1c30: 64 69 66 66 65 72 65 6e 63 65 73 20 2a 2f 0a 20 differences */.
1c40: 20 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 72 for(i=0; i<nr
1c50: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 6d 20 ; i++){. m
1c60: 3d 20 52 5b 72 2b 69 2a 33 2b 31 5d 3b 0a 20 20 = R[r+i*3+1];.
1c70: 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d for(j=0; j<m
1c80: 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 ; j++){.
1c90: 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 appendDiffLine(p
1ca0: 4f 75 74 2c 20 22 2d 22 2c 20 26 41 5b 61 2b 6a Out, "-", &A[a+j
1cb0: 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ]);. }.
1cc0: 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 a += m;.
1cd0: 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 32 5d 3b 0a m = R[r+i*3+2];.
1ce0: 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a for(j=0; j
1cf0: 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 <m; j++){.
1d00: 20 20 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 appendDiffLine
1d10: 28 70 4f 75 74 2c 20 22 2b 22 2c 20 26 42 5b 62 (pOut, "+", &B[b
1d20: 2b 6a 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 +j]);. }.
1d30: 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 20 b += m;.
1d40: 20 20 69 66 28 20 69 3c 6e 72 2d 31 20 29 7b 0a if( i<nr-1 ){.
1d50: 20 20 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b m = R[r+
1d60: 69 2a 33 2b 33 5d 3b 0a 20 20 20 20 20 20 20 20 i*3+3];.
1d70: 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b for(j=0; j<m; j+
1d80: 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 20 61 70 +){. ap
1d90: 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 4f 75 pendDiffLine(pOu
1da0: 74 2c 20 22 20 22 2c 20 26 42 5b 62 2b 6a 5d 29 t, " ", &B[b+j])
1db0: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 ;. }.
1dc0: 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 20 b += m;.
1dd0: 20 20 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 a += m;.
1de0: 20 20 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f }. }.. /
1df0: 2a 20 53 68 6f 77 20 74 68 65 20 66 69 6e 61 6c * Show the final
1e00: 20 63 6f 6d 6d 6f 6e 20 61 72 65 61 20 2a 2f 0a common area */.
1e10: 20 20 20 20 61 73 73 65 72 74 28 20 6e 72 3d 3d assert( nr==
1e20: 69 20 29 3b 0a 20 20 20 20 6d 20 3d 20 52 5b 72 i );. m = R[r
1e30: 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 69 66 28 20 +nr*3];. if(
1e40: 6d 3e 6e 43 6f 6e 74 65 78 74 20 29 20 6d 20 3d m>nContext ) m =
1e50: 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 20 66 nContext;. f
1e60: 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b or(j=0; j<m; j++
1e70: 29 7b 0a 20 20 20 20 20 20 61 70 70 65 6e 64 44 ){. appendD
1e80: 69 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 20 iffLine(pOut, "
1e90: 22 2c 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 20 ", &B[b+j]);.
1ea0: 20 7d 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 }. }.}../*.**
1eb0: 43 6f 6d 70 75 74 65 20 74 68 65 20 6f 70 74 69 Compute the opti
1ec0: 6d 61 6c 20 6c 6f 6e 67 65 73 74 20 63 6f 6d 6d mal longest comm
1ed0: 6f 6e 20 73 75 62 73 65 71 75 65 6e 63 65 20 28 on subsequence (
1ee0: 4c 43 53 29 20 75 73 69 6e 67 20 61 6e 0a 2a 2a LCS) using an.**
1ef0: 20 65 78 68 61 75 73 74 69 76 65 20 73 65 61 72 exhaustive sear
1f00: 63 68 2e 20 20 54 68 69 73 20 76 65 72 73 69 6f ch. This versio
1f10: 6e 20 6f 66 20 74 68 65 20 4c 43 53 20 69 73 20 n of the LCS is
1f20: 6f 6e 6c 79 20 75 73 65 64 20 66 6f 72 0a 2a 2a only used for.**
1f30: 20 73 68 6f 72 74 65 72 20 69 6e 70 75 74 20 73 shorter input s
1f40: 74 72 69 6e 67 73 20 73 69 6e 63 65 20 72 75 6e trings since run
1f50: 74 69 6d 65 20 69 73 20 4f 28 4e 2a 4e 29 20 77 time is O(N*N) w
1f60: 68 65 72 65 20 4e 20 69 73 20 74 68 65 0a 2a 2a here N is the.**
1f70: 20 69 6e 70 75 74 20 73 74 72 69 6e 67 20 6c 65 input string le
1f80: 6e 67 74 68 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 ngth..*/.static
1f90: 76 6f 69 64 20 6f 70 74 69 6d 61 6c 4c 43 53 28 void optimalLCS(
1fa0: 0a 20 20 44 43 6f 6e 74 65 78 74 20 2a 70 2c 20 . DContext *p,
1fb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
1fc0: 20 54 77 6f 20 66 69 6c 65 73 20 62 65 69 6e 67 Two files being
1fd0: 20 63 6f 6d 70 61 72 65 64 20 2a 2f 0a 20 20 69 compared */. i
1fe0: 6e 74 20 69 53 31 2c 20 69 6e 74 20 69 45 31 2c nt iS1, int iE1,
1ff0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 61 6e /* Ran
2000: 67 65 20 6f 66 20 6c 69 6e 65 73 20 69 6e 20 70 ge of lines in p
2010: 2d 3e 61 46 72 6f 6d 5b 5d 20 2a 2f 0a 20 20 69 ->aFrom[] */. i
2020: 6e 74 20 69 53 32 2c 20 69 6e 74 20 69 45 32 2c nt iS2, int iE2,
2030: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 61 6e /* Ran
2040: 67 65 20 6f 66 20 6c 69 6e 65 73 20 69 6e 20 70 ge of lines in p
2050: 2d 3e 61 54 6f 5b 5d 20 2a 2f 0a 20 20 69 6e 74 ->aTo[] */. int
2060: 20 2a 70 69 53 58 2c 20 69 6e 74 20 2a 70 69 45 *piSX, int *piE
2070: 58 2c 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65 X, /* Write
2080: 20 70 2d 3e 61 46 72 6f 6d 5b 5d 20 63 6f 6d 6d p->aFrom[] comm
2090: 6f 6e 20 73 65 67 6d 65 6e 74 20 68 65 72 65 20 on segment here
20a0: 2a 2f 0a 20 20 69 6e 74 20 2a 70 69 53 59 2c 20 */. int *piSY,
20b0: 69 6e 74 20 2a 70 69 45 59 20 20 20 20 20 20 20 int *piEY
20c0: 2f 2a 20 57 72 69 74 65 20 70 2d 3e 61 54 6f 5b /* Write p->aTo[
20d0: 5d 20 63 6f 6d 6d 6f 6e 20 73 65 67 6d 65 6e 74 ] common segment
20e0: 20 68 65 72 65 20 2a 2f 0a 29 7b 0a 20 20 69 6e here */.){. in
20f0: 74 20 6d 78 4c 65 6e 67 74 68 20 3d 20 30 3b 20 t mxLength = 0;
2100: 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 65 6e 67 /* Leng
2110: 74 68 20 6f 66 20 6c 6f 6e 67 65 73 74 20 63 6f th of longest co
2120: 6d 6d 6f 6e 20 73 75 62 73 65 71 75 65 6e 63 65 mmon subsequence
2130: 20 2a 2f 0a 20 20 69 6e 74 20 69 2c 20 6a 3b 20 */. int i, j;
2140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2150: 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 6e 74 65 72 /* Loop counter
2160: 73 20 2a 2f 0a 20 20 69 6e 74 20 6b 3b 20 20 20 s */. int k;
2170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2180: 20 20 2f 2a 20 4c 65 6e 67 74 68 20 6f 66 20 61 /* Length of a
2190: 20 63 61 6e 64 69 64 61 74 65 20 73 75 62 73 65 candidate subse
21a0: 71 75 65 6e 63 65 20 2a 2f 0a 20 20 69 6e 74 20 quence */. int
21b0: 69 53 58 62 20 3d 20 69 53 31 3b 20 20 20 20 20 iSXb = iS1;
21c0: 20 20 20 20 20 20 20 2f 2a 20 42 65 73 74 20 6d /* Best m
21d0: 61 74 63 68 20 73 6f 20 66 61 72 20 2a 2f 0a 20 atch so far */.
21e0: 20 69 6e 74 20 69 53 59 62 20 3d 20 69 53 32 3b int iSYb = iS2;
21f0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42 /* B
2200: 65 73 74 20 6d 61 74 63 68 20 73 6f 20 66 61 72 est match so far
2210: 20 2a 2f 0a 0a 20 20 66 6f 72 28 69 3d 69 53 31 */.. for(i=iS1
2220: 3b 20 69 3c 69 45 31 2d 6d 78 4c 65 6e 67 74 68 ; i<iE1-mxLength
2230: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 66 6f 72 28 ; i++){. for(
2240: 6a 3d 69 53 32 3b 20 6a 3c 69 45 32 2d 6d 78 4c j=iS2; j<iE2-mxL
2250: 65 6e 67 74 68 3b 20 6a 2b 2b 29 7b 0a 20 20 20 ength; j++){.
2260: 20 20 20 69 66 28 20 21 73 61 6d 65 5f 64 6c 69 if( !same_dli
2270: 6e 65 28 26 70 2d 3e 61 46 72 6f 6d 5b 69 5d 2c ne(&p->aFrom[i],
2280: 20 26 70 2d 3e 61 54 6f 5b 6a 5d 29 20 29 20 63 &p->aTo[j]) ) c
2290: 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 20 20 69 ontinue;. i
22a0: 66 28 20 6d 78 4c 65 6e 67 74 68 20 26 26 20 21 f( mxLength && !
22b0: 73 61 6d 65 5f 64 6c 69 6e 65 28 26 70 2d 3e 61 same_dline(&p->a
22c0: 46 72 6f 6d 5b 69 2b 6d 78 4c 65 6e 67 74 68 5d From[i+mxLength]
22d0: 2c 20 26 70 2d 3e 61 54 6f 5b 6a 2b 6d 78 4c 65 , &p->aTo[j+mxLe
22e0: 6e 67 74 68 5d 29 20 29 7b 0a 20 20 20 20 20 20 ngth]) ){.
22f0: 20 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 continue;.
2300: 20 20 7d 0a 20 20 20 20 20 20 6b 20 3d 20 31 3b }. k = 1;
2310: 0a 20 20 20 20 20 20 77 68 69 6c 65 28 20 69 2b . while( i+
2320: 6b 3c 69 45 31 20 26 26 20 6a 2b 6b 3c 69 45 32 k<iE1 && j+k<iE2
2330: 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e 65 28 26 && same_dline(&
2340: 70 2d 3e 61 46 72 6f 6d 5b 69 2b 6b 5d 2c 26 70 p->aFrom[i+k],&p
2350: 2d 3e 61 54 6f 5b 6a 2b 6b 5d 29 20 29 7b 0a 20 ->aTo[j+k]) ){.
2360: 20 20 20 20 20 20 20 6b 2b 2b 3b 0a 20 20 20 20 k++;.
2370: 20 20 7d 0a 20 20 20 20 20 20 69 66 28 20 6b 3e }. if( k>
2380: 6d 78 4c 65 6e 67 74 68 20 29 7b 0a 20 20 20 20 mxLength ){.
2390: 20 20 20 20 69 53 58 62 20 3d 20 69 3b 0a 20 20 iSXb = i;.
23a0: 20 20 20 20 20 20 69 53 59 62 20 3d 20 6a 3b 0a iSYb = j;.
23b0: 20 20 20 20 20 20 20 20 6d 78 4c 65 6e 67 74 68 mxLength
23c0: 20 3d 20 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 = k;. }.
23d0: 20 20 7d 0a 20 20 7d 0a 20 20 2a 70 69 53 58 20 }. }. *piSX
23e0: 3d 20 69 53 58 62 3b 0a 20 20 2a 70 69 45 58 20 = iSXb;. *piEX
23f0: 3d 20 69 53 58 62 20 2b 20 6d 78 4c 65 6e 67 74 = iSXb + mxLengt
2400: 68 3b 0a 20 20 2a 70 69 53 59 20 3d 20 69 53 59 h;. *piSY = iSY
2410: 62 3b 0a 20 20 2a 70 69 45 59 20 3d 20 69 53 59 b;. *piEY = iSY
2420: 62 20 2b 20 6d 78 4c 65 6e 67 74 68 3b 0a 7d 0a b + mxLength;.}.
2430: 0a 2f 2a 0a 2a 2a 20 43 6f 6d 70 61 72 65 20 74 ./*.** Compare t
2440: 77 6f 20 62 6c 6f 63 6b 73 20 6f 66 20 74 65 78 wo blocks of tex
2450: 74 20 6f 6e 20 6c 69 6e 65 73 20 69 53 31 20 74 t on lines iS1 t
2460: 68 72 6f 75 67 68 20 69 45 31 2d 31 20 6f 66 20 hrough iE1-1 of
2470: 74 68 65 20 61 46 72 6f 6d 5b 5d 0a 2a 2a 20 66 the aFrom[].** f
2480: 69 6c 65 20 61 6e 64 20 6c 69 6e 65 73 20 69 53 ile and lines iS
2490: 32 20 74 68 72 6f 75 67 68 20 69 45 32 2d 31 20 2 through iE2-1
24a0: 6f 66 20 74 68 65 20 61 54 6f 5b 5d 20 66 69 6c of the aTo[] fil
24b0: 65 2e 20 20 4c 6f 63 61 74 65 20 61 20 73 65 71 e. Locate a seq
24c0: 75 65 6e 63 65 0a 2a 2a 20 6f 66 20 6c 69 6e 65 uence.** of line
24d0: 73 20 69 6e 20 74 68 65 73 65 20 74 77 6f 20 62 s in these two b
24e0: 6c 6f 63 6b 73 20 74 68 61 74 20 61 72 65 20 65 locks that are e
24f0: 78 61 63 74 6c 79 20 74 68 65 20 73 61 6d 65 2e xactly the same.
2500: 20 20 52 65 74 75 72 6e 0a 2a 2a 20 74 68 65 20 Return.** the
2510: 62 6f 75 6e 64 73 20 6f 66 20 74 68 65 20 6d 61 bounds of the ma
2520: 74 63 68 69 6e 67 20 73 65 71 75 65 6e 63 65 2e tching sequence.
2530: 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 72 65 20 .**.** If there
2540: 61 72 65 20 74 77 6f 20 6f 72 20 6d 6f 72 65 20 are two or more
2550: 70 6f 73 73 69 62 6c 65 20 61 6e 73 77 65 72 73 possible answers
2560: 20 6f 66 20 74 68 65 20 73 61 6d 65 20 6c 65 6e of the same len
2570: 67 74 68 2c 20 74 68 65 0a 2a 2a 20 72 65 74 75 gth, the.** retu
2580: 72 6e 65 64 20 73 65 71 75 65 6e 63 65 20 73 68 rned sequence sh
2590: 6f 75 6c 64 20 62 65 20 74 68 65 20 6f 6e 65 20 ould be the one
25a0: 63 6c 6f 73 65 73 74 20 74 6f 20 74 68 65 20 63 closest to the c
25b0: 65 6e 74 65 72 20 6f 66 20 74 68 65 0a 2a 2a 20 enter of the.**
25c0: 69 6e 70 75 74 20 72 61 6e 67 65 2e 0a 2a 2a 0a input range..**.
25d0: 2a 2a 20 49 64 65 61 6c 6c 79 2c 20 74 68 65 20 ** Ideally, the
25e0: 63 6f 6d 6d 6f 6e 20 73 65 71 75 65 6e 63 65 20 common sequence
25f0: 73 68 6f 75 6c 64 20 62 65 20 74 68 65 20 6c 6f should be the lo
2600: 6e 67 65 73 74 20 70 6f 73 73 69 62 6c 65 20 63 ngest possible c
2610: 6f 6d 6d 6f 6e 0a 2a 2a 20 73 65 71 75 65 6e 63 ommon.** sequenc
2620: 65 2e 20 20 48 6f 77 65 76 65 72 2c 20 61 6e 20 e. However, an
2630: 65 78 61 63 74 20 63 6f 6d 70 75 74 61 74 69 6f exact computatio
2640: 6e 20 6f 66 20 4c 43 53 20 69 73 20 4f 28 4e 2a n of LCS is O(N*
2650: 4e 29 20 77 68 69 63 68 20 69 73 0a 2a 2a 20 77 N) which is.** w
2660: 61 79 20 74 6f 6f 20 73 6c 6f 77 20 66 6f 72 20 ay too slow for
2670: 6c 61 72 67 65 72 20 66 69 6c 65 73 2e 20 20 53 larger files. S
2680: 6f 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20 75 o this routine u
2690: 73 65 73 20 61 6e 20 4f 28 4e 29 0a 2a 2a 20 68 ses an O(N).** h
26a0: 65 75 72 69 73 74 69 63 20 61 70 70 72 6f 78 69 euristic approxi
26b0: 6d 61 74 69 6f 6e 20 62 61 73 65 64 20 6f 6e 20 mation based on
26c0: 68 61 73 68 69 6e 67 20 74 68 61 74 20 75 73 75 hashing that usu
26d0: 61 6c 6c 79 20 77 6f 72 6b 73 20 61 62 6f 75 74 ally works about
26e0: 20 0a 2a 2a 20 61 73 20 77 65 6c 6c 2e 20 20 42 .** as well. B
26f0: 75 74 20 69 66 20 74 68 65 20 4f 28 4e 29 20 61 ut if the O(N) a
2700: 6c 67 6f 72 69 74 68 6d 20 64 6f 65 73 6e 27 74 lgorithm doesn't
2710: 20 67 65 74 20 61 20 67 6f 6f 64 20 73 6f 6c 75 get a good solu
2720: 74 69 6f 6e 0a 2a 2a 20 61 6e 64 20 4e 20 69 73 tion.** and N is
2730: 20 6e 6f 74 20 74 6f 6f 20 6c 61 72 67 65 2c 20 not too large,
2740: 77 65 20 66 61 6c 6c 20 62 61 63 6b 20 74 6f 20 we fall back to
2750: 61 6e 20 65 78 61 63 74 20 73 6f 6c 75 74 69 6f an exact solutio
2760: 6e 20 62 79 0a 2a 2a 20 63 61 6c 6c 69 6e 67 20 n by.** calling
2770: 6f 70 74 69 6d 61 6c 4c 43 53 28 29 2e 0a 2a 2f optimalLCS()..*/
2780: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 6c 6f 6e .static void lon
2790: 67 65 73 74 43 6f 6d 6d 6f 6e 53 65 71 75 65 6e gestCommonSequen
27a0: 63 65 28 0a 20 20 44 43 6f 6e 74 65 78 74 20 2a ce(. DContext *
27b0: 70 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 p,
27c0: 20 2f 2a 20 54 77 6f 20 66 69 6c 65 73 20 62 65 /* Two files be
27d0: 69 6e 67 20 63 6f 6d 70 61 72 65 64 20 2a 2f 0a ing compared */.
27e0: 20 20 69 6e 74 20 69 53 31 2c 20 69 6e 74 20 69 int iS1, int i
27f0: 45 31 2c 20 20 20 20 20 20 20 20 20 20 2f 2a 20 E1, /*
2800: 52 61 6e 67 65 20 6f 66 20 6c 69 6e 65 73 20 69 Range of lines i
2810: 6e 20 70 2d 3e 61 46 72 6f 6d 5b 5d 20 2a 2f 0a n p->aFrom[] */.
2820: 20 20 69 6e 74 20 69 53 32 2c 20 69 6e 74 20 69 int iS2, int i
2830: 45 32 2c 20 20 20 20 20 20 20 20 20 20 2f 2a 20 E2, /*
2840: 52 61 6e 67 65 20 6f 66 20 6c 69 6e 65 73 20 69 Range of lines i
2850: 6e 20 70 2d 3e 61 54 6f 5b 5d 20 2a 2f 0a 20 20 n p->aTo[] */.
2860: 69 6e 74 20 2a 70 69 53 58 2c 20 69 6e 74 20 2a int *piSX, int *
2870: 70 69 45 58 2c 20 20 20 20 20 20 2f 2a 20 57 72 piEX, /* Wr
2880: 69 74 65 20 70 2d 3e 61 46 72 6f 6d 5b 5d 20 63 ite p->aFrom[] c
2890: 6f 6d 6d 6f 6e 20 73 65 67 6d 65 6e 74 20 68 65 ommon segment he
28a0: 72 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 69 53 re */. int *piS
28b0: 59 2c 20 69 6e 74 20 2a 70 69 45 59 20 20 20 20 Y, int *piEY
28c0: 20 20 20 2f 2a 20 57 72 69 74 65 20 70 2d 3e 61 /* Write p->a
28d0: 54 6f 5b 5d 20 63 6f 6d 6d 6f 6e 20 73 65 67 6d To[] common segm
28e0: 65 6e 74 20 68 65 72 65 20 2a 2f 0a 29 7b 0a 20 ent here */.){.
28f0: 20 64 6f 75 62 6c 65 20 62 65 73 74 53 63 6f 72 double bestScor
2900: 65 20 3d 20 2d 31 65 33 30 3b 20 20 2f 2a 20 42 e = -1e30; /* B
2910: 65 73 74 20 73 63 6f 72 65 20 73 65 65 6e 20 73 est score seen s
2920: 6f 20 66 61 72 20 2a 2f 0a 20 20 69 6e 74 20 69 o far */. int i
2930: 2c 20 6a 3b 20 20 20 20 20 20 20 20 20 20 20 20 , j;
2940: 20 20 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 6f /* Loop co
2950: 75 6e 74 65 72 73 20 2a 2f 0a 20 20 69 6e 74 20 unters */. int
2960: 69 53 58 2c 20 69 53 59 2c 20 69 45 58 2c 20 69 iSX, iSY, iEX, i
2970: 45 59 3b 20 20 20 20 2f 2a 20 43 75 72 72 65 6e EY; /* Curren
2980: 74 20 6d 61 74 63 68 20 2a 2f 0a 20 20 64 6f 75 t match */. dou
2990: 62 6c 65 20 73 63 6f 72 65 3b 20 20 20 20 20 20 ble score;
29a0: 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 /* Curre
29b0: 6e 74 20 73 63 6f 72 65 20 2a 2f 0a 20 20 69 6e nt score */. in
29c0: 74 20 73 6b 65 77 3b 20 20 20 20 20 20 20 20 20 t skew;
29d0: 20 20 20 20 20 20 20 20 20 2f 2a 20 48 6f 77 20 /* How
29e0: 6c 6f 70 73 69 64 65 64 20 69 73 20 74 68 65 20 lopsided is the
29f0: 6d 61 74 63 68 20 2a 2f 0a 20 20 69 6e 74 20 64 match */. int d
2a00: 69 73 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 ist;
2a10: 20 20 20 20 20 20 2f 2a 20 44 69 73 74 61 6e 63 /* Distanc
2a20: 65 20 6f 66 20 6d 61 74 63 68 20 66 72 6f 6d 20 e of match from
2a30: 63 65 6e 74 65 72 20 2a 2f 0a 20 20 69 6e 74 20 center */. int
2a40: 6d 69 64 3b 20 20 20 20 20 20 20 20 20 20 20 20 mid;
2a50: 20 20 20 20 20 20 20 2f 2a 20 43 65 6e 74 65 72 /* Center
2a60: 20 6f 66 20 74 68 65 20 73 70 61 6e 20 2a 2f 0a of the span */.
2a70: 20 20 69 6e 74 20 69 53 58 62 2c 20 69 53 59 62 int iSXb, iSYb
2a80: 2c 20 69 45 58 62 2c 20 69 45 59 62 3b 20 20 20 , iEXb, iEYb;
2a90: 2f 2a 20 42 65 73 74 20 6d 61 74 63 68 20 73 6f /* Best match so
2aa0: 20 66 61 72 20 2a 2f 0a 20 20 69 6e 74 20 69 53 far */. int iS
2ab0: 58 70 2c 20 69 53 59 70 2c 20 69 45 58 70 2c 20 Xp, iSYp, iEXp,
2ac0: 69 45 59 70 3b 20 20 20 2f 2a 20 50 72 65 76 69 iEYp; /* Previ
2ad0: 6f 75 73 20 6d 61 74 63 68 20 2a 2f 0a 0a 0a 20 ous match */...
2ae0: 20 69 53 58 62 20 3d 20 69 53 58 70 20 3d 20 69 iSXb = iSXp = i
2af0: 53 31 3b 0a 20 20 69 45 58 62 20 3d 20 69 45 58 S1;. iEXb = iEX
2b00: 70 20 3d 20 69 53 31 3b 0a 20 20 69 53 59 62 20 p = iS1;. iSYb
2b10: 3d 20 69 53 59 70 20 3d 20 69 53 32 3b 0a 20 20 = iSYp = iS2;.
2b20: 69 45 59 62 20 3d 20 69 45 59 70 20 3d 20 69 53 iEYb = iEYp = iS
2b30: 32 3b 0a 20 20 6d 69 64 20 3d 20 28 69 45 31 20 2;. mid = (iE1
2b40: 2b 20 69 53 31 29 2f 32 3b 0a 20 20 66 6f 72 28 + iS1)/2;. for(
2b50: 69 3d 69 53 31 3b 20 69 3c 69 45 31 3b 20 69 2b i=iS1; i<iE1; i+
2b60: 2b 29 7b 0a 20 20 20 20 69 6e 74 20 6c 69 6d 69 +){. int limi
2b70: 74 20 3d 20 30 3b 0a 20 20 20 20 6a 20 3d 20 70 t = 0;. j = p
2b80: 2d 3e 61 54 6f 5b 70 2d 3e 61 46 72 6f 6d 5b 69 ->aTo[p->aFrom[i
2b90: 5d 2e 68 20 25 20 70 2d 3e 6e 54 6f 5d 2e 69 48 ].h % p->nTo].iH
2ba0: 61 73 68 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 ash;. while(
2bb0: 6a 3e 30 20 0a 20 20 20 20 20 20 26 26 20 28 6a j>0 . && (j
2bc0: 2d 31 3c 69 53 32 20 7c 7c 20 6a 3e 3d 69 45 32 -1<iS2 || j>=iE2
2bd0: 20 7c 7c 20 21 73 61 6d 65 5f 64 6c 69 6e 65 28 || !same_dline(
2be0: 26 70 2d 3e 61 46 72 6f 6d 5b 69 5d 2c 20 26 70 &p->aFrom[i], &p
2bf0: 2d 3e 61 54 6f 5b 6a 2d 31 5d 29 29 0a 20 20 20 ->aTo[j-1])).
2c00: 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 6c 69 ){. if( li
2c10: 6d 69 74 2b 2b 20 3e 20 31 30 20 29 7b 0a 20 20 mit++ > 10 ){.
2c20: 20 20 20 20 20 20 6a 20 3d 20 30 3b 0a 20 20 20 j = 0;.
2c30: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 break;.
2c40: 20 20 7d 0a 20 20 20 20 20 20 6a 20 3d 20 70 2d }. j = p-
2c50: 3e 61 54 6f 5b 6a 2d 31 5d 2e 69 4e 65 78 74 3b >aTo[j-1].iNext;
2c60: 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20 6a . }. if( j
2c70: 3d 3d 30 20 29 20 63 6f 6e 74 69 6e 75 65 3b 0a ==0 ) continue;.
2c80: 20 20 20 20 61 73 73 65 72 74 28 20 69 3e 3d 69 assert( i>=i
2c90: 53 58 62 20 26 26 20 69 3e 3d 69 53 58 70 20 29 SXb && i>=iSXp )
2ca0: 3b 0a 20 20 20 20 69 66 28 20 69 3c 69 45 58 62 ;. if( i<iEXb
2cb0: 20 26 26 20 6a 3e 3d 69 53 59 62 20 26 26 20 6a && j>=iSYb && j
2cc0: 3c 69 45 59 62 20 29 20 63 6f 6e 74 69 6e 75 65 <iEYb ) continue
2cd0: 3b 0a 20 20 20 20 69 66 28 20 69 3c 69 45 58 70 ;. if( i<iEXp
2ce0: 20 26 26 20 6a 3e 3d 69 53 59 70 20 26 26 20 6a && j>=iSYp && j
2cf0: 3c 69 45 59 70 20 29 20 63 6f 6e 74 69 6e 75 65 <iEYp ) continue
2d00: 3b 0a 20 20 20 20 69 53 58 20 3d 20 69 3b 0a 20 ;. iSX = i;.
2d10: 20 20 20 69 53 59 20 3d 20 6a 2d 31 3b 0a 20 20 iSY = j-1;.
2d20: 20 20 77 68 69 6c 65 28 20 69 53 58 3e 69 53 31 while( iSX>iS1
2d30: 20 26 26 20 69 53 59 3e 69 53 32 20 26 26 20 73 && iSY>iS2 && s
2d40: 61 6d 65 5f 64 6c 69 6e 65 28 26 70 2d 3e 61 46 ame_dline(&p->aF
2d50: 72 6f 6d 5b 69 53 58 2d 31 5d 2c 26 70 2d 3e 61 rom[iSX-1],&p->a
2d60: 54 6f 5b 69 53 59 2d 31 5d 29 20 29 7b 0a 20 20 To[iSY-1]) ){.
2d70: 20 20 20 20 69 53 58 2d 2d 3b 0a 20 20 20 20 20 iSX--;.
2d80: 20 69 53 59 2d 2d 3b 0a 20 20 20 20 7d 0a 20 20 iSY--;. }.
2d90: 20 20 69 45 58 20 3d 20 69 2b 31 3b 0a 20 20 20 iEX = i+1;.
2da0: 20 69 45 59 20 3d 20 6a 3b 0a 20 20 20 20 77 68 iEY = j;. wh
2db0: 69 6c 65 28 20 69 45 58 3c 69 45 31 20 26 26 20 ile( iEX<iE1 &&
2dc0: 69 45 59 3c 69 45 32 20 26 26 20 73 61 6d 65 5f iEY<iE2 && same_
2dd0: 64 6c 69 6e 65 28 26 70 2d 3e 61 46 72 6f 6d 5b dline(&p->aFrom[
2de0: 69 45 58 5d 2c 26 70 2d 3e 61 54 6f 5b 69 45 59 iEX],&p->aTo[iEY
2df0: 5d 29 20 29 7b 0a 20 20 20 20 20 20 69 45 58 2b ]) ){. iEX+
2e00: 2b 3b 0a 20 20 20 20 20 20 69 45 59 2b 2b 3b 0a +;. iEY++;.
2e10: 20 20 20 20 7d 0a 20 20 20 20 73 6b 65 77 20 3d }. skew =
2e20: 20 28 69 53 58 2d 69 53 31 29 20 2d 20 28 69 53 (iSX-iS1) - (iS
2e30: 59 2d 69 53 32 29 3b 0a 20 20 20 20 69 66 28 20 Y-iS2);. if(
2e40: 73 6b 65 77 3c 30 20 29 20 73 6b 65 77 20 3d 20 skew<0 ) skew =
2e50: 2d 73 6b 65 77 3b 0a 20 20 20 20 64 69 73 74 20 -skew;. dist
2e60: 3d 20 28 69 53 58 2b 69 45 58 29 2f 32 20 2d 20 = (iSX+iEX)/2 -
2e70: 6d 69 64 3b 0a 20 20 20 20 69 66 28 20 64 69 73 mid;. if( dis
2e80: 74 3c 30 20 29 20 64 69 73 74 20 3d 20 2d 64 69 t<0 ) dist = -di
2e90: 73 74 3b 0a 20 20 20 20 73 63 6f 72 65 20 3d 20 st;. score =
2ea0: 28 69 45 58 20 2d 20 69 53 58 29 20 2d 20 30 2e (iEX - iSX) - 0.
2eb0: 30 35 2a 73 6b 65 77 20 2d 20 30 2e 30 35 2a 64 05*skew - 0.05*d
2ec0: 69 73 74 3b 0a 20 20 20 20 69 66 28 20 73 63 6f ist;. if( sco
2ed0: 72 65 3e 62 65 73 74 53 63 6f 72 65 20 29 7b 0a re>bestScore ){.
2ee0: 20 20 20 20 20 20 62 65 73 74 53 63 6f 72 65 20 bestScore
2ef0: 3d 20 73 63 6f 72 65 3b 0a 20 20 20 20 20 20 69 = score;. i
2f00: 53 58 62 20 3d 20 69 53 58 3b 0a 20 20 20 20 20 SXb = iSX;.
2f10: 20 69 53 59 62 20 3d 20 69 53 59 3b 0a 20 20 20 iSYb = iSY;.
2f20: 20 20 20 69 45 58 62 20 3d 20 69 45 58 3b 0a 20 iEXb = iEX;.
2f30: 20 20 20 20 20 69 45 59 62 20 3d 20 69 45 59 3b iEYb = iEY;
2f40: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 . }else{.
2f50: 20 20 69 53 58 70 20 3d 20 69 53 58 3b 0a 20 20 iSXp = iSX;.
2f60: 20 20 20 20 69 53 59 70 20 3d 20 69 53 59 3b 0a iSYp = iSY;.
2f70: 20 20 20 20 20 20 69 45 58 70 20 3d 20 69 45 58 iEXp = iEX
2f80: 3b 0a 20 20 20 20 20 20 69 45 59 70 20 3d 20 69 ;. iEYp = i
2f90: 45 59 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 EY;. }. }.
2fa0: 69 66 28 20 69 53 58 62 3d 3d 69 45 58 62 20 26 if( iSXb==iEXb &
2fb0: 26 20 28 69 45 31 2d 69 53 31 29 2a 28 69 45 32 & (iE1-iS1)*(iE2
2fc0: 2d 69 53 32 29 3c 34 30 30 20 29 7b 0a 20 20 20 -iS2)<400 ){.
2fd0: 20 2f 2a 20 49 66 20 6e 6f 20 63 6f 6d 6d 6f 6e /* If no common
2fe0: 20 73 65 71 75 65 6e 63 65 20 69 73 20 66 6f 75 sequence is fou
2ff0: 6e 64 20 75 73 69 6e 67 20 74 68 65 20 68 61 73 nd using the has
3000: 68 69 6e 67 20 68 65 75 72 69 73 74 69 63 20 61 hing heuristic a
3010: 6e 64 0a 20 20 20 20 2a 2a 20 74 68 65 20 69 6e nd. ** the in
3020: 70 75 74 20 69 73 20 6e 6f 74 20 74 6f 6f 20 62 put is not too b
3030: 69 67 2c 20 75 73 65 20 74 68 65 20 65 78 70 65 ig, use the expe
3040: 6e 73 69 76 65 20 65 78 61 63 74 20 73 6f 6c 75 nsive exact solu
3050: 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 6f 70 74 69 tion */. opti
3060: 6d 61 6c 4c 43 53 28 70 2c 20 69 53 31 2c 20 69 malLCS(p, iS1, i
3070: 45 31 2c 20 69 53 32 2c 20 69 45 32 2c 20 70 69 E1, iS2, iE2, pi
3080: 53 58 2c 20 70 69 45 58 2c 20 70 69 53 59 2c 20 SX, piEX, piSY,
3090: 70 69 45 59 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a piEY);. }else{.
30a0: 20 20 20 20 2a 70 69 53 58 20 3d 20 69 53 58 62 *piSX = iSXb
30b0: 3b 0a 20 20 20 20 2a 70 69 53 59 20 3d 20 69 53 ;. *piSY = iS
30c0: 59 62 3b 0a 20 20 20 20 2a 70 69 45 58 20 3d 20 Yb;. *piEX =
30d0: 69 45 58 62 3b 0a 20 20 20 20 2a 70 69 45 59 20 iEXb;. *piEY
30e0: 3d 20 69 45 59 62 3b 0a 20 20 7d 0a 20 20 2f 2a = iEYb;. }. /*
30f0: 20 70 72 69 6e 74 66 28 22 4c 43 53 28 25 64 2e printf("LCS(%d.
3100: 2e 25 64 2f 25 64 2e 2e 25 64 29 20 3d 20 25 64 .%d/%d..%d) = %d
3110: 2e 2e 25 64 2f 25 64 2e 2e 25 64 5c 6e 22 2c 20 ..%d/%d..%d\n",
3120: 0a 20 20 20 20 20 69 53 31 2c 20 69 45 31 2c 20 . iS1, iE1,
3130: 69 53 32 2c 20 69 45 32 2c 20 2a 70 69 53 58 2c iS2, iE2, *piSX,
3140: 20 2a 70 69 45 58 2c 20 2a 70 69 53 59 2c 20 2a *piEX, *piSY, *
3150: 70 69 45 59 29 3b 20 20 2a 2f 0a 7d 0a 0a 2f 2a piEY); */.}../*
3160: 0a 2a 2a 20 44 6f 20 61 20 73 69 6e 67 6c 65 20 .** Do a single
3170: 73 74 65 70 20 69 6e 20 74 68 65 20 64 69 66 66 step in the diff
3180: 65 72 65 6e 63 65 2e 20 20 43 6f 6d 70 75 74 65 erence. Compute
3190: 20 61 20 73 65 71 75 65 6e 63 65 20 6f 66 0a 2a a sequence of.*
31a0: 2a 20 63 6f 70 79 2f 64 65 6c 65 74 65 2f 69 6e * copy/delete/in
31b0: 73 65 72 74 20 73 74 65 70 73 20 74 68 61 74 20 sert steps that
31c0: 77 69 6c 6c 20 63 6f 6e 76 65 72 74 20 6c 69 6e will convert lin
31d0: 65 73 20 69 53 31 20 74 68 72 6f 75 67 68 20 69 es iS1 through i
31e0: 45 31 2d 31 20 6f 66 0a 2a 2a 20 74 68 65 20 69 E1-1 of.** the i
31f0: 6e 70 75 74 20 69 6e 74 6f 20 6c 69 6e 65 73 20 nput into lines
3200: 69 53 32 20 74 68 72 6f 75 67 68 20 69 45 32 2d iS2 through iE2-
3210: 31 20 6f 66 20 74 68 65 20 6f 75 74 70 75 74 20 1 of the output
3220: 61 6e 64 20 77 72 69 74 65 0a 2a 2a 20 74 68 61 and write.** tha
3230: 74 20 73 65 71 75 65 6e 63 65 20 69 6e 74 6f 20 t sequence into
3240: 74 68 65 20 64 69 66 66 65 72 65 6e 63 65 20 63 the difference c
3250: 6f 6e 74 65 78 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 ontext..**.** Th
3260: 65 20 61 6c 67 6f 72 69 74 68 6d 20 69 73 20 74 e algorithm is t
3270: 6f 20 66 69 6e 64 20 61 20 62 6c 6f 63 6b 20 6f o find a block o
3280: 66 20 63 6f 6d 6d 6f 6e 20 74 65 78 74 20 6e 65 f common text ne
3290: 61 72 20 74 68 65 20 6d 69 64 64 6c 65 0a 2a 2a ar the middle.**
32a0: 20 6f 66 20 74 68 65 20 74 77 6f 20 73 65 67 6d of the two segm
32b0: 65 6e 74 73 20 62 65 69 6e 67 20 64 69 66 66 65 ents being diffe
32c0: 64 2e 20 20 54 68 65 6e 20 72 65 63 75 72 73 69 d. Then recursi
32d0: 76 65 6c 79 20 63 6f 6d 70 75 74 65 0a 2a 2a 20 vely compute.**
32e0: 64 69 66 66 65 72 65 6e 63 65 73 20 6f 6e 20 74 differences on t
32f0: 68 65 20 62 6c 6f 63 6b 73 20 62 65 66 6f 72 65 he blocks before
3300: 20 61 6e 64 20 61 66 74 65 72 20 74 68 61 74 20 and after that
3310: 63 6f 6d 6d 6f 6e 20 73 65 67 6d 65 6e 74 2e 0a common segment..
3320: 2a 2a 20 53 70 65 63 69 61 6c 20 63 61 73 65 73 ** Special cases
3330: 20 61 70 70 6c 79 20 69 66 20 65 69 74 68 65 72 apply if either
3340: 20 69 6e 70 75 74 20 73 65 67 6d 65 6e 74 20 69 input segment i
3350: 73 20 65 6d 70 74 79 20 6f 72 20 69 66 20 74 68 s empty or if th
3360: 65 0a 2a 2a 20 74 77 6f 20 73 65 67 6d 65 6e 74 e.** two segment
3370: 73 20 68 61 76 65 20 6e 6f 20 74 65 78 74 20 69 s have no text i
3380: 6e 20 63 6f 6d 6d 6f 6e 2e 0a 2a 2f 0a 73 74 61 n common..*/.sta
3390: 74 69 63 20 76 6f 69 64 20 64 69 66 66 5f 73 74 tic void diff_st
33a0: 65 70 28 44 43 6f 6e 74 65 78 74 20 2a 70 2c 20 ep(DContext *p,
33b0: 69 6e 74 20 69 53 31 2c 20 69 6e 74 20 69 45 31 int iS1, int iE1
33c0: 2c 20 69 6e 74 20 69 53 32 2c 20 69 6e 74 20 69 , int iS2, int i
33d0: 45 32 29 7b 0a 20 20 69 6e 74 20 69 53 58 2c 20 E2){. int iSX,
33e0: 69 45 58 2c 20 69 53 59 2c 20 69 45 59 3b 0a 0a iEX, iSY, iEY;..
33f0: 20 20 69 66 28 20 69 45 31 3c 3d 69 53 31 20 29 if( iE1<=iS1 )
3400: 7b 0a 20 20 20 20 2f 2a 20 54 68 65 20 66 69 72 {. /* The fir
3410: 73 74 20 73 65 67 6d 65 6e 74 20 69 73 20 65 6d st segment is em
3420: 70 74 79 20 2a 2f 0a 20 20 20 20 69 66 28 20 69 pty */. if( i
3430: 45 32 3e 69 53 32 20 29 7b 0a 20 20 20 20 20 20 E2>iS2 ){.
3440: 61 70 70 65 6e 64 54 72 69 70 6c 65 28 70 2c 20 appendTriple(p,
3450: 30 2c 20 30 2c 20 69 45 32 2d 69 53 32 29 3b 0a 0, 0, iE2-iS2);.
3460: 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e }. return
3470: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 69 45 32 3c ;. }. if( iE2<
3480: 3d 69 53 32 20 29 7b 0a 20 20 20 20 2f 2a 20 54 =iS2 ){. /* T
3490: 68 65 20 73 65 63 6f 6e 64 20 73 65 67 6d 65 6e he second segmen
34a0: 74 20 69 73 20 65 6d 70 74 79 20 2a 2f 0a 20 20 t is empty */.
34b0: 20 20 61 70 70 65 6e 64 54 72 69 70 6c 65 28 70 appendTriple(p
34c0: 2c 20 30 2c 20 69 45 31 2d 69 53 31 2c 20 30 29 , 0, iE1-iS1, 0)
34d0: 3b 0a 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 ;. return;.
34e0: 7d 0a 0a 20 20 2f 2a 20 46 69 6e 64 20 74 68 65 }.. /* Find the
34f0: 20 6c 6f 6e 67 65 73 74 20 6d 61 74 63 68 69 6e longest matchin
3500: 67 20 73 65 67 6d 65 6e 74 20 62 65 74 77 65 65 g segment betwee
3510: 6e 20 74 68 65 20 74 77 6f 20 73 65 71 75 65 6e n the two sequen
3520: 63 65 73 20 2a 2f 0a 20 20 6c 6f 6e 67 65 73 74 ces */. longest
3530: 43 6f 6d 6d 6f 6e 53 65 71 75 65 6e 63 65 28 70 CommonSequence(p
3540: 2c 20 69 53 31 2c 20 69 45 31 2c 20 69 53 32 2c , iS1, iE1, iS2,
3550: 20 69 45 32 2c 20 26 69 53 58 2c 20 26 69 45 58 iE2, &iSX, &iEX
3560: 2c 20 26 69 53 59 2c 20 26 69 45 59 29 3b 0a 0a , &iSY, &iEY);..
3570: 20 20 69 66 28 20 69 45 58 3e 69 53 58 20 29 7b if( iEX>iSX ){
3580: 0a 20 20 20 20 2f 2a 20 41 20 63 6f 6d 6d 6f 6e . /* A common
3590: 20 73 65 67 65 6d 65 6e 74 20 68 61 73 20 62 65 segement has be
35a0: 65 6e 20 66 6f 75 6e 64 2e 0a 20 20 20 20 2a 2a en found.. **
35b0: 20 52 65 63 75 72 73 69 76 65 6c 79 20 64 69 66 Recursively dif
35c0: 66 20 65 69 74 68 65 72 20 73 69 64 65 20 6f 66 f either side of
35d0: 20 74 68 65 20 6d 61 74 63 68 69 6e 67 20 73 65 the matching se
35e0: 67 6d 65 6e 74 20 2a 2f 0a 20 20 20 20 64 69 66 gment */. dif
35f0: 66 5f 73 74 65 70 28 70 2c 20 69 53 31 2c 20 69 f_step(p, iS1, i
3600: 53 58 2c 20 69 53 32 2c 20 69 53 59 29 3b 0a 20 SX, iS2, iSY);.
3610: 20 20 20 69 66 28 20 69 45 58 3e 69 53 58 20 29 if( iEX>iSX )
3620: 7b 0a 20 20 20 20 20 20 61 70 70 65 6e 64 54 72 {. appendTr
3630: 69 70 6c 65 28 70 2c 20 69 45 58 20 2d 20 69 53 iple(p, iEX - iS
3640: 58 2c 20 30 2c 20 30 29 3b 0a 20 20 20 20 7d 0a X, 0, 0);. }.
3650: 20 20 20 20 64 69 66 66 5f 73 74 65 70 28 70 2c diff_step(p,
3660: 20 69 45 58 2c 20 69 45 31 2c 20 69 45 59 2c 20 iEX, iE1, iEY,
3670: 69 45 32 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 iE2);. }else{.
3680: 20 20 20 2f 2a 20 54 68 65 20 74 77 6f 20 73 65 /* The two se
3690: 67 6d 65 6e 74 73 20 68 61 76 65 20 6e 6f 74 68 gments have noth
36a0: 69 6e 67 20 69 6e 20 63 6f 6d 6d 6f 6e 2e 20 20 ing in common.
36b0: 44 65 6c 65 74 65 20 74 68 65 20 66 69 72 73 74 Delete the first
36c0: 20 74 68 65 6e 0a 20 20 20 20 2a 2a 20 69 6e 73 then. ** ins
36d0: 65 72 74 20 74 68 65 20 73 65 63 6f 6e 64 2e 20 ert the second.
36e0: 2a 2f 0a 20 20 20 20 61 70 70 65 6e 64 54 72 69 */. appendTri
36f0: 70 6c 65 28 70 2c 20 30 2c 20 69 45 31 2d 69 53 ple(p, 0, iE1-iS
3700: 31 2c 20 69 45 32 2d 69 53 32 29 3b 0a 20 20 7d 1, iE2-iS2);. }
3710: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6d 70 75 74 .}../*.** Comput
3720: 65 20 74 68 65 20 64 69 66 66 65 72 65 6e 63 65 e the difference
3730: 73 20 62 65 74 77 65 65 6e 20 74 77 6f 20 66 69 s between two fi
3740: 6c 65 73 20 61 6c 72 65 61 64 79 20 6c 6f 61 64 les already load
3750: 65 64 20 69 6e 74 6f 0a 2a 2a 20 74 68 65 20 44 ed into.** the D
3760: 43 6f 6e 74 65 78 74 20 73 74 72 75 63 74 75 72 Context structur
3770: 65 2e 0a 2a 2a 0a 2a 2a 20 41 20 64 69 76 69 64 e..**.** A divid
3780: 65 20 61 6e 64 20 63 6f 6e 71 75 65 72 20 74 65 e and conquer te
3790: 63 68 6e 69 71 75 65 20 69 73 20 75 73 65 64 2e chnique is used.
37a0: 20 20 57 65 20 6c 6f 6f 6b 20 66 6f 72 20 61 20 We look for a
37b0: 6c 61 72 67 65 0a 2a 2a 20 62 6c 6f 63 6b 20 6f large.** block o
37c0: 66 20 63 6f 6d 6d 6f 6e 20 74 65 78 74 20 74 68 f common text th
37d0: 61 74 20 69 73 20 69 6e 20 74 68 65 20 6d 69 64 at is in the mid
37e0: 64 6c 65 20 6f 66 20 62 6f 74 68 20 66 69 6c 65 dle of both file
37f0: 73 2e 20 20 54 68 65 6e 0a 2a 2a 20 63 6f 6d 70 s. Then.** comp
3800: 75 74 65 20 74 68 65 20 64 69 66 66 65 72 65 6e ute the differen
3810: 63 65 20 6f 6e 20 74 68 6f 73 65 20 70 61 72 74 ce on those part
3820: 73 20 6f 66 20 74 68 65 20 66 69 6c 65 20 62 65 s of the file be
3830: 66 6f 72 65 20 61 6e 64 0a 2a 2a 20 61 66 74 65 fore and.** afte
3840: 72 20 74 68 65 20 63 6f 6d 6d 6f 6e 20 62 6c 6f r the common blo
3850: 63 6b 2e 20 20 54 68 69 73 20 74 65 63 68 6e 69 ck. This techni
3860: 71 75 65 20 69 73 20 66 61 73 74 2c 20 62 75 74 que is fast, but
3870: 20 69 74 20 64 6f 65 73 0a 2a 2a 20 6e 6f 74 20 it does.** not
3880: 6e 65 63 65 73 73 61 72 69 6c 79 20 67 65 6e 65 necessarily gene
3890: 72 61 74 65 20 74 68 65 20 6d 69 6e 69 6d 75 6d rate the minimum
38a0: 20 64 69 66 66 65 72 65 6e 63 65 20 73 65 74 2e difference set.
38b0: 20 20 4f 6e 20 74 68 65 0a 2a 2a 20 6f 74 68 65 On the.** othe
38c0: 72 20 68 61 6e 64 2c 20 77 65 20 64 6f 20 6e 6f r hand, we do no
38d0: 74 20 6e 65 65 64 20 61 20 6d 69 6e 69 6d 75 6d t need a minimum
38e0: 20 64 69 66 66 65 72 65 6e 63 65 20 73 65 74 2c difference set,
38f0: 20 6f 6e 6c 79 20 6f 6e 65 0a 2a 2a 20 74 68 61 only one.** tha
3900: 74 20 6d 61 6b 65 73 20 73 65 6e 73 65 20 74 6f t makes sense to
3910: 20 68 75 6d 61 6e 20 72 65 61 64 65 72 73 2c 20 human readers,
3920: 77 68 69 63 68 20 74 68 69 73 20 61 6c 67 6f 72 which this algor
3930: 69 74 68 6d 20 64 6f 65 73 2e 0a 2a 2a 0a 2a 2a ithm does..**.**
3940: 20 41 6e 79 20 63 6f 6d 6d 6f 6e 20 74 65 78 74 Any common text
3950: 20 61 74 20 74 68 65 20 62 65 67 69 6e 6e 69 6e at the beginnin
3960: 67 20 61 6e 64 20 65 6e 64 20 6f 66 20 74 68 65 g and end of the
3970: 20 74 77 6f 20 66 69 6c 65 73 20 69 73 0a 2a 2a two files is.**
3980: 20 72 65 6d 6f 76 65 64 20 62 65 66 6f 72 65 20 removed before
3990: 73 74 61 72 74 69 6e 67 20 74 68 65 20 64 69 76 starting the div
39a0: 69 64 65 2d 61 6e 64 2d 63 6f 6e 71 75 65 72 20 ide-and-conquer
39b0: 61 6c 67 6f 72 69 74 68 6d 2e 0a 2a 2f 0a 73 74 algorithm..*/.st
39c0: 61 74 69 63 20 76 6f 69 64 20 64 69 66 66 5f 61 atic void diff_a
39d0: 6c 6c 28 44 43 6f 6e 74 65 78 74 20 2a 70 29 7b ll(DContext *p){
39e0: 0a 20 20 69 6e 74 20 6d 6e 45 2c 20 69 53 2c 20 . int mnE, iS,
39f0: 69 45 31 2c 20 69 45 32 3b 0a 0a 20 20 2f 2a 20 iE1, iE2;.. /*
3a00: 43 61 72 76 65 20 6f 66 66 20 74 68 65 20 63 6f Carve off the co
3a10: 6d 6d 6f 6e 20 68 65 61 64 65 72 20 61 6e 64 20 mmon header and
3a20: 66 6f 6f 74 65 72 20 2a 2f 0a 20 20 69 45 31 20 footer */. iE1
3a30: 3d 20 70 2d 3e 6e 46 72 6f 6d 3b 0a 20 20 69 45 = p->nFrom;. iE
3a40: 32 20 3d 20 70 2d 3e 6e 54 6f 3b 0a 20 20 77 68 2 = p->nTo;. wh
3a50: 69 6c 65 28 20 69 45 31 3e 30 20 26 26 20 69 45 ile( iE1>0 && iE
3a60: 32 3e 30 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e 2>0 && same_dlin
3a70: 65 28 26 70 2d 3e 61 46 72 6f 6d 5b 69 45 31 2d e(&p->aFrom[iE1-
3a80: 31 5d 2c 20 26 70 2d 3e 61 54 6f 5b 69 45 32 2d 1], &p->aTo[iE2-
3a90: 31 5d 29 20 29 7b 0a 20 20 20 20 69 45 31 2d 2d 1]) ){. iE1--
3aa0: 3b 0a 20 20 20 20 69 45 32 2d 2d 3b 0a 20 20 7d ;. iE2--;. }
3ab0: 0a 20 20 6d 6e 45 20 3d 20 69 45 31 3c 69 45 32 . mnE = iE1<iE2
3ac0: 20 3f 20 69 45 31 20 3a 20 69 45 32 3b 0a 20 20 ? iE1 : iE2;.
3ad0: 66 6f 72 28 69 53 3d 30 3b 20 69 53 3c 6d 6e 45 for(iS=0; iS<mnE
3ae0: 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e 65 28 26 && same_dline(&
3af0: 70 2d 3e 61 46 72 6f 6d 5b 69 53 5d 2c 26 70 2d p->aFrom[iS],&p-
3b00: 3e 61 54 6f 5b 69 53 5d 29 3b 20 69 53 2b 2b 29 >aTo[iS]); iS++)
3b10: 7b 7d 0a 0a 20 20 2f 2a 20 64 6f 20 74 68 65 20 {}.. /* do the
3b20: 64 69 66 66 65 72 65 6e 63 65 20 2a 2f 0a 20 20 difference */.
3b30: 69 66 28 20 69 53 3e 30 20 29 7b 0a 20 20 20 20 if( iS>0 ){.
3b40: 61 70 70 65 6e 64 54 72 69 70 6c 65 28 70 2c 20 appendTriple(p,
3b50: 69 53 2c 20 30 2c 20 30 29 3b 0a 20 20 7d 0a 20 iS, 0, 0);. }.
3b60: 20 64 69 66 66 5f 73 74 65 70 28 70 2c 20 69 53 diff_step(p, iS
3b70: 2c 20 69 45 31 2c 20 69 53 2c 20 69 45 32 29 3b , iE1, iS, iE2);
3b80: 0a 20 20 69 66 28 20 69 45 31 3c 70 2d 3e 6e 46 . if( iE1<p->nF
3b90: 72 6f 6d 20 29 7b 0a 20 20 20 20 61 70 70 65 6e rom ){. appen
3ba0: 64 54 72 69 70 6c 65 28 70 2c 20 70 2d 3e 6e 46 dTriple(p, p->nF
3bb0: 72 6f 6d 20 2d 20 69 45 31 2c 20 30 2c 20 30 29 rom - iE1, 0, 0)
3bc0: 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54 65 72 6d ;. }.. /* Term
3bd0: 69 6e 61 74 65 20 74 68 65 20 43 4f 50 59 2f 44 inate the COPY/D
3be0: 45 4c 45 54 45 2f 49 4e 53 45 52 54 20 74 72 69 ELETE/INSERT tri
3bf0: 70 6c 65 73 20 77 69 74 68 20 74 68 72 65 65 20 ples with three
3c00: 7a 65 72 6f 73 20 2a 2f 0a 20 20 65 78 70 61 6e zeros */. expan
3c10: 64 45 64 69 74 28 70 2c 20 70 2d 3e 6e 45 64 69 dEdit(p, p->nEdi
3c20: 74 2b 33 29 3b 0a 20 20 69 66 28 20 70 2d 3e 61 t+3);. if( p->a
3c30: 45 64 69 74 20 29 7b 0a 20 20 20 20 70 2d 3e 61 Edit ){. p->a
3c40: 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 2b 2b 5d Edit[p->nEdit++]
3c50: 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 61 45 64 = 0;. p->aEd
3c60: 69 74 5b 70 2d 3e 6e 45 64 69 74 2b 2b 5d 20 3d it[p->nEdit++] =
3c70: 20 30 3b 0a 20 20 20 20 70 2d 3e 61 45 64 69 74 0;. p->aEdit
3c80: 5b 70 2d 3e 6e 45 64 69 74 2b 2b 5d 20 3d 20 30 [p->nEdit++] = 0
3c90: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 47 ;. }.}../*.** G
3ca0: 65 6e 65 72 61 74 65 20 61 20 72 65 70 6f 72 74 enerate a report
3cb0: 20 6f 66 20 74 68 65 20 64 69 66 66 65 72 65 6e of the differen
3cc0: 63 65 73 20 62 65 74 77 65 65 6e 20 66 69 6c 65 ces between file
3cd0: 73 20 70 41 20 61 6e 64 20 70 42 2e 0a 2a 2a 20 s pA and pB..**
3ce0: 49 66 20 70 4f 75 74 20 69 73 20 6e 6f 74 20 4e If pOut is not N
3cf0: 55 4c 4c 20 74 68 65 6e 20 61 20 75 6e 69 66 69 ULL then a unifi
3d00: 65 64 20 64 69 66 66 20 69 73 20 61 70 70 65 6e ed diff is appen
3d10: 64 65 64 20 74 68 65 72 65 2e 20 20 49 74 0a 2a ded there. It.*
3d20: 2a 20 69 73 20 61 73 73 75 6d 65 64 20 74 68 61 * is assumed tha
3d30: 74 20 70 4f 75 74 20 68 61 73 20 61 6c 72 65 61 t pOut has alrea
3d40: 64 79 20 62 65 65 6e 20 69 6e 69 74 69 61 6c 69 dy been initiali
3d50: 7a 65 64 2e 20 20 49 66 20 70 4f 75 74 20 69 73 zed. If pOut is
3d60: 0a 2a 2a 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 61 .** NULL, then a
3d70: 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 20 61 pointer to an a
3d80: 72 72 61 79 20 6f 66 20 69 6e 74 65 67 65 72 73 rray of integers
3d90: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 20 20 0a is returned. .
3da0: 2a 2a 20 54 68 65 20 69 6e 74 65 67 65 72 73 20 ** The integers
3db0: 63 6f 6d 65 20 69 6e 20 74 72 69 70 6c 65 73 2e come in triples.
3dc0: 20 20 46 6f 72 20 65 61 63 68 20 74 72 69 70 6c For each tripl
3dd0: 65 2c 0a 2a 2a 20 74 68 65 20 65 6c 65 6d 65 6e e,.** the elemen
3de0: 74 73 20 61 72 65 20 74 68 65 20 6e 75 6d 62 65 ts are the numbe
3df0: 72 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 69 65 r of lines copie
3e00: 64 2c 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 d, the number of
3e10: 0a 2a 2a 20 6c 69 6e 65 73 20 64 65 6c 65 74 65 .** lines delete
3e20: 64 2c 20 61 6e 64 20 74 68 65 20 6e 75 6d 62 65 d, and the numbe
3e30: 72 20 6f 66 20 6c 69 6e 65 73 20 69 6e 73 65 72 r of lines inser
3e40: 74 65 64 2e 20 20 54 68 65 20 76 65 63 74 6f 72 ted. The vector
3e50: 0a 2a 2a 20 69 73 20 74 65 72 6d 69 6e 61 74 65 .** is terminate
3e60: 64 20 62 79 20 61 20 74 72 69 70 6c 65 20 6f 66 d by a triple of
3e70: 20 61 6c 6c 20 7a 65 72 6f 73 2e 0a 2a 2a 0a 2a all zeros..**.*
3e80: 2a 20 54 68 69 73 20 64 69 66 66 20 75 74 69 6c * This diff util
3e90: 69 74 79 20 64 6f 65 73 20 6e 6f 74 20 77 6f 72 ity does not wor
3ea0: 6b 20 6f 6e 20 62 69 6e 61 72 79 20 66 69 6c 65 k on binary file
3eb0: 73 2e 20 20 49 66 20 61 20 62 69 6e 61 72 79 0a s. If a binary.
3ec0: 2a 2a 20 66 69 6c 65 20 69 73 20 65 6e 63 6f 75 ** file is encou
3ed0: 6e 74 65 72 65 64 2c 20 30 20 69 73 20 72 65 74 ntered, 0 is ret
3ee0: 75 72 6e 65 64 20 61 6e 64 20 70 4f 75 74 20 69 urned and pOut i
3ef0: 73 20 77 72 69 74 74 65 6e 20 77 69 74 68 0a 2a s written with.*
3f00: 2a 20 74 65 78 74 20 22 63 61 6e 6e 6f 74 20 63 * text "cannot c
3f10: 6f 6d 70 75 74 65 20 64 69 66 66 65 72 65 6e 63 ompute differenc
3f20: 65 20 62 65 74 77 65 65 6e 20 62 69 6e 61 72 79 e between binary
3f30: 20 66 69 6c 65 73 22 2e 0a 2a 2f 0a 69 6e 74 20 files"..*/.int
3f40: 2a 74 65 78 74 5f 64 69 66 66 28 0a 20 20 42 6c *text_diff(. Bl
3f50: 6f 62 20 2a 70 41 5f 42 6c 6f 62 2c 20 20 20 2f ob *pA_Blob, /
3f60: 2a 20 46 52 4f 4d 20 66 69 6c 65 20 2a 2f 0a 20 * FROM file */.
3f70: 20 42 6c 6f 62 20 2a 70 42 5f 42 6c 6f 62 2c 20 Blob *pB_Blob,
3f80: 20 20 2f 2a 20 54 4f 20 66 69 6c 65 20 2a 2f 0a /* TO file */.
3f90: 20 20 42 6c 6f 62 20 2a 70 4f 75 74 2c 20 20 20 Blob *pOut,
3fa0: 20 20 20 2f 2a 20 57 72 69 74 65 20 75 6e 69 66 /* Write unif
3fb0: 69 65 64 20 64 69 66 66 20 68 65 72 65 20 69 66 ied diff here if
3fc0: 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f 0a 20 20 69 not NULL */. i
3fd0: 6e 74 20 6e 43 6f 6e 74 65 78 74 2c 20 20 20 20 nt nContext,
3fe0: 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 63 6f 6e /* Amount of con
3ff0: 74 65 78 74 20 74 6f 20 75 6e 69 66 69 65 64 20 text to unified
4000: 64 69 66 66 20 2a 2f 0a 20 20 69 6e 74 20 69 67 diff */. int ig
4010: 6e 6f 72 65 45 6f 6c 57 73 20 20 2f 2a 20 49 67 noreEolWs /* Ig
4020: 6e 6f 72 65 20 77 68 69 74 65 73 70 61 63 65 20 nore whitespace
4030: 61 74 20 74 68 65 20 65 6e 64 20 6f 66 20 6c 69 at the end of li
4040: 6e 65 73 20 2a 2f 0a 29 7b 0a 20 20 44 43 6f 6e nes */.){. DCon
4050: 74 65 78 74 20 63 3b 0a 20 0a 20 20 2f 2a 20 50 text c;. . /* P
4060: 72 65 70 61 72 65 20 74 68 65 20 69 6e 70 75 74 repare the input
4070: 20 66 69 6c 65 73 20 2a 2f 0a 20 20 6d 65 6d 73 files */. mems
4080: 65 74 28 26 63 2c 20 30 2c 20 73 69 7a 65 6f 66 et(&c, 0, sizeof
4090: 28 63 29 29 3b 0a 20 20 63 2e 61 46 72 6f 6d 20 (c));. c.aFrom
40a0: 3d 20 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e = break_into_lin
40b0: 65 73 28 62 6c 6f 62 5f 73 74 72 28 70 41 5f 42 es(blob_str(pA_B
40c0: 6c 6f 62 29 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 lob), blob_size(
40d0: 70 41 5f 42 6c 6f 62 29 2c 0a 20 20 20 20 20 20 pA_Blob),.
40e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
40f0: 20 20 20 20 20 20 20 26 63 2e 6e 46 72 6f 6d 2c &c.nFrom,
4100: 20 69 67 6e 6f 72 65 45 6f 6c 57 73 29 3b 0a 20 ignoreEolWs);.
4110: 20 63 2e 61 54 6f 20 3d 20 62 72 65 61 6b 5f 69 c.aTo = break_i
4120: 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 nto_lines(blob_s
4130: 74 72 28 70 42 5f 42 6c 6f 62 29 2c 20 62 6c 6f tr(pB_Blob), blo
4140: 62 5f 73 69 7a 65 28 70 42 5f 42 6c 6f 62 29 2c b_size(pB_Blob),
4150: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
4160: 20 20 20 20 20 20 20 20 20 20 20 20 26 63 2e 6e &c.n
4170: 54 6f 2c 20 69 67 6e 6f 72 65 45 6f 6c 57 73 29 To, ignoreEolWs)
4180: 3b 0a 20 20 69 66 28 20 63 2e 61 46 72 6f 6d 3d ;. if( c.aFrom=
4190: 3d 30 20 7c 7c 20 63 2e 61 54 6f 3d 3d 30 20 29 =0 || c.aTo==0 )
41a0: 7b 0a 20 20 20 20 66 72 65 65 28 63 2e 61 46 72 {. free(c.aFr
41b0: 6f 6d 29 3b 0a 20 20 20 20 66 72 65 65 28 63 2e om);. free(c.
41c0: 61 54 6f 29 3b 0a 20 20 20 20 69 66 28 20 70 4f aTo);. if( pO
41d0: 75 74 20 29 7b 0a 20 20 20 20 20 20 62 6c 6f 62 ut ){. blob
41e0: 5f 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 20 22 _appendf(pOut, "
41f0: 63 61 6e 6e 6f 74 20 63 6f 6d 70 75 74 65 20 64 cannot compute d
4200: 69 66 66 65 72 65 6e 63 65 20 62 65 74 77 65 65 ifference betwee
4210: 6e 20 62 69 6e 61 72 79 20 66 69 6c 65 73 5c 6e n binary files\n
4220: 22 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 ");. }. re
4230: 74 75 72 6e 20 30 3b 0a 20 20 7d 0a 0a 20 20 2f turn 0;. }.. /
4240: 2a 20 43 6f 6d 70 75 74 65 20 74 68 65 20 64 69 * Compute the di
4250: 66 66 65 72 65 6e 63 65 20 2a 2f 0a 20 20 64 69 fference */. di
4260: 66 66 5f 61 6c 6c 28 26 63 29 3b 0a 0a 20 20 69 ff_all(&c);.. i
4270: 66 28 20 70 4f 75 74 20 29 7b 0a 20 20 20 20 2f f( pOut ){. /
4280: 2a 20 43 6f 6d 70 75 74 65 20 61 20 63 6f 6e 74 * Compute a cont
4290: 65 78 74 20 64 69 66 66 20 69 66 20 72 65 71 75 ext diff if requ
42a0: 65 73 74 65 64 20 2a 2f 0a 20 20 20 20 63 6f 6e ested */. con
42b0: 74 65 78 74 44 69 66 66 28 26 63 2c 20 70 4f 75 textDiff(&c, pOu
42c0: 74 2c 20 6e 43 6f 6e 74 65 78 74 29 3b 0a 20 20 t, nContext);.
42d0: 20 20 66 72 65 65 28 63 2e 61 46 72 6f 6d 29 3b free(c.aFrom);
42e0: 0a 20 20 20 20 66 72 65 65 28 63 2e 61 54 6f 29 . free(c.aTo)
42f0: 3b 0a 20 20 20 20 66 72 65 65 28 63 2e 61 45 64 ;. free(c.aEd
4300: 69 74 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 it);. return
4310: 30 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 0;. }else{.
4320: 2f 2a 20 49 66 20 61 20 63 6f 6e 74 65 78 74 20 /* If a context
4330: 64 69 66 66 20 69 73 20 6e 6f 74 20 72 65 71 75 diff is not requ
4340: 65 73 74 65 64 2c 20 74 68 65 6e 20 72 65 74 75 ested, then retu
4350: 72 6e 20 74 68 65 0a 20 20 20 20 2a 2a 20 61 72 rn the. ** ar
4360: 72 61 79 20 6f 66 20 43 4f 50 59 2f 44 45 4c 45 ray of COPY/DELE
4370: 54 45 2f 49 4e 53 45 52 54 20 74 72 69 70 6c 65 TE/INSERT triple
4380: 73 2e 0a 20 20 20 20 2a 2f 0a 20 20 20 20 66 72 s.. */. fr
4390: 65 65 28 63 2e 61 46 72 6f 6d 29 3b 0a 20 20 20 ee(c.aFrom);.
43a0: 20 66 72 65 65 28 63 2e 61 54 6f 29 3b 0a 20 20 free(c.aTo);.
43b0: 20 20 72 65 74 75 72 6e 20 63 2e 61 45 64 69 74 return c.aEdit
43c0: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 ;. }.}../*.** C
43d0: 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 72 61 77 OMMAND: test-raw
43e0: 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 diff.*/.void tes
43f0: 74 5f 72 61 77 64 69 66 66 5f 63 6d 64 28 76 6f t_rawdiff_cmd(vo
4400: 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c 20 62 id){. Blob a, b
4410: 3b 0a 20 20 69 6e 74 20 72 3b 0a 20 20 69 6e 74 ;. int r;. int
4420: 20 69 3b 0a 20 20 69 6e 74 20 2a 52 3b 0a 20 20 i;. int *R;.
4430: 69 66 28 20 67 2e 61 72 67 63 3c 34 20 29 20 75 if( g.argc<4 ) u
4440: 73 61 67 65 28 22 46 49 4c 45 31 20 46 49 4c 45 sage("FILE1 FILE
4450: 32 20 2e 2e 2e 22 29 3b 0a 20 20 62 6c 6f 62 5f 2 ...");. blob_
4460: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
4470: 61 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b 0a 20 a, g.argv[2]);.
4480: 20 66 6f 72 28 69 3d 33 3b 20 69 3c 67 2e 61 72 for(i=3; i<g.ar
4490: 67 63 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 gc; i++){. if
44a0: 28 20 69 3e 33 20 29 20 70 72 69 6e 74 66 28 22 ( i>3 ) printf("
44b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
44c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 5c ---------------\
44d0: 6e 22 29 3b 0a 20 20 20 20 62 6c 6f 62 5f 72 65 n");. blob_re
44e0: 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c ad_from_file(&b,
44f0: 20 67 2e 61 72 67 76 5b 69 5d 29 3b 0a 20 20 20 g.argv[i]);.
4500: 20 52 20 3d 20 74 65 78 74 5f 64 69 66 66 28 26 R = text_diff(&
4510: 61 2c 20 26 62 2c 20 30 2c 20 30 2c 20 30 29 3b a, &b, 0, 0, 0);
4520: 0a 20 20 20 20 66 6f 72 28 72 3d 30 3b 20 52 5b . for(r=0; R[
4530: 72 5d 20 7c 7c 20 52 5b 72 2b 31 5d 20 7c 7c 20 r] || R[r+1] ||
4540: 52 5b 72 2b 32 5d 3b 20 72 20 2b 3d 20 33 29 7b R[r+2]; r += 3){
4550: 0a 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 20 . printf("
4560: 63 6f 70 79 20 25 34 64 20 20 64 65 6c 65 74 65 copy %4d delete
4570: 20 25 34 64 20 20 69 6e 73 65 72 74 20 25 34 64 %4d insert %4d
4580: 5c 6e 22 2c 20 52 5b 72 5d 2c 20 52 5b 72 2b 31 \n", R[r], R[r+1
4590: 5d 2c 20 52 5b 72 2b 32 5d 29 3b 0a 20 20 20 20 ], R[r+2]);.
45a0: 7d 0a 20 20 20 20 2f 2a 20 66 72 65 65 28 52 29 }. /* free(R)
45b0: 3b 20 2a 2f 0a 20 20 20 20 62 6c 6f 62 5f 72 65 ; */. blob_re
45c0: 73 65 74 28 26 62 29 3b 0a 20 20 7d 0a 7d 0a 0a set(&b);. }.}..
45d0: 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 /*.** COMMAND: t
45e0: 65 73 74 2d 75 64 69 66 66 0a 2a 2f 0a 76 6f 69 est-udiff.*/.voi
45f0: 64 20 74 65 73 74 5f 75 64 69 66 66 5f 63 6d 64 d test_udiff_cmd
4600: 28 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 (void){. Blob a
4610: 2c 20 62 2c 20 6f 75 74 3b 0a 20 20 69 66 28 20 , b, out;. if(
4620: 67 2e 61 72 67 63 21 3d 34 20 29 20 75 73 61 67 g.argc!=4 ) usag
4630: 65 28 22 46 49 4c 45 31 20 46 49 4c 45 32 22 29 e("FILE1 FILE2")
4640: 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 ;. blob_read_fr
4650: 6f 6d 5f 66 69 6c 65 28 26 61 2c 20 67 2e 61 72 om_file(&a, g.ar
4660: 67 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f 72 gv[2]);. blob_r
4670: 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 ead_from_file(&b
4680: 2c 20 67 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 20 , g.argv[3]);.
4690: 62 6c 6f 62 5f 7a 65 72 6f 28 26 6f 75 74 29 3b blob_zero(&out);
46a0: 0a 20 20 74 65 78 74 5f 64 69 66 66 28 26 61 2c . text_diff(&a,
46b0: 20 26 62 2c 20 26 6f 75 74 2c 20 33 2c 20 30 29 &b, &out, 3, 0)
46c0: 3b 0a 20 20 62 6c 6f 62 5f 77 72 69 74 65 5f 74 ;. blob_write_t
46d0: 6f 5f 66 69 6c 65 28 26 6f 75 74 2c 20 22 2d 22 o_file(&out, "-"
46e0: 29 3b 0a 7d 0a 0a 2f 2a 2a 2a 2a 2a 2a 2a 2a 2a );.}../*********
46f0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
4700: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
4710: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
4720: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
4730: 2a 0a 2a 2a 20 54 68 65 20 62 61 73 69 63 20 64 *.** The basic d
4740: 69 66 66 65 72 65 6e 63 65 20 65 6e 67 69 6e 65 ifference engine
4750: 20 69 73 20 61 62 6f 76 65 2e 20 20 57 68 61 74 is above. What
4760: 20 66 6f 6c 6c 6f 77 73 20 69 73 20 74 68 65 20 follows is the
4770: 61 6e 6e 6f 74 61 74 69 6f 6e 0a 2a 2a 20 65 6e annotation.** en
4780: 67 69 6e 65 2e 20 20 42 6f 74 68 20 61 72 65 20 gine. Both are
4790: 69 6e 20 74 68 65 20 73 61 6d 65 20 66 69 6c 65 in the same file
47a0: 20 73 69 6e 63 65 20 74 68 65 79 20 73 68 61 72 since they shar
47b0: 65 20 6d 61 6e 79 20 63 6f 6d 70 6f 6e 65 6e 74 e many component
47c0: 73 2e 0a 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 s..*/../*.** The
47d0: 20 73 74 61 74 75 73 20 6f 66 20 61 6e 20 61 6e status of an an
47e0: 6e 6f 74 61 74 69 6f 6e 20 6f 70 65 72 61 74 69 notation operati
47f0: 6f 6e 20 69 73 20 72 65 63 6f 72 64 65 64 20 62 on is recorded b
4800: 79 20 61 6e 20 69 6e 73 74 61 6e 63 65 0a 2a 2a y an instance.**
4810: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e of the followin
4820: 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2f 0a g structure..*/.
4830: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 41 typedef struct A
4840: 6e 6e 6f 74 61 74 6f 72 20 41 6e 6e 6f 74 61 74 nnotator Annotat
4850: 6f 72 3b 0a 73 74 72 75 63 74 20 41 6e 6e 6f 74 or;.struct Annot
4860: 61 74 6f 72 20 7b 0a 20 20 44 43 6f 6e 74 65 78 ator {. DContex
4870: 74 20 63 3b 20 20 20 20 20 20 20 2f 2a 20 54 68 t c; /* Th
4880: 65 20 64 69 66 66 2d 65 6e 67 69 6e 65 20 63 6f e diff-engine co
4890: 6e 74 65 78 74 20 2a 2f 0a 20 20 73 74 72 75 63 ntext */. struc
48a0: 74 20 7b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 t { /*
48b0: 4c 69 6e 65 73 20 6f 66 20 74 68 65 20 6f 72 69 Lines of the ori
48c0: 67 69 6e 61 6c 20 66 69 6c 65 73 2e 2e 2e 20 2a ginal files... *
48d0: 2f 0a 20 20 20 20 63 6f 6e 73 74 20 63 68 61 72 /. const char
48e0: 20 2a 7a 3b 20 20 20 20 20 20 20 2f 2a 20 54 68 *z; /* Th
48f0: 65 20 74 65 78 74 20 6f 66 20 74 68 65 20 6c 69 e text of the li
4900: 6e 65 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6e 3b ne */. int n;
4910: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
4920: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 * Number of byte
4930: 73 20 28 6f 6d 69 74 74 69 6e 67 20 74 72 61 69 s (omitting trai
4940: 6c 69 6e 67 20 73 70 61 63 65 20 61 6e 64 20 5c ling space and \
4950: 6e 29 20 2a 2f 0a 20 20 20 20 63 6f 6e 73 74 20 n) */. const
4960: 63 68 61 72 20 2a 7a 53 72 63 3b 20 20 20 20 2f char *zSrc; /
4970: 2a 20 54 61 67 20 73 68 6f 77 69 6e 67 20 6f 72 * Tag showing or
4980: 69 67 69 6e 20 6f 66 20 74 68 69 73 20 6c 69 6e igin of this lin
4990: 65 20 2a 2f 0a 20 20 7d 20 2a 61 4f 72 69 67 3b e */. } *aOrig;
49a0: 0a 20 20 69 6e 74 20 6e 4f 72 69 67 3b 20 20 20 . int nOrig;
49b0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f /* Number o
49c0: 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 61 4f f elements in aO
49d0: 72 69 67 5b 5d 20 2a 2f 0a 20 20 69 6e 74 20 6e rig[] */. int n
49e0: 4e 6f 53 72 63 3b 20 20 20 20 20 20 20 2f 2a 20 NoSrc; /*
49f0: 4e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 Number of entrie
4a00: 73 20 77 68 65 72 65 20 61 4f 72 69 67 5b 5d 2e s where aOrig[].
4a10: 7a 53 72 63 3d 3d 4e 55 4c 4c 20 2a 2f 0a 7d 3b zSrc==NULL */.};
4a20: 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61 6c 69 ../*.** Initiali
4a30: 7a 65 20 74 68 65 20 61 6e 6e 6f 74 61 74 69 6f ze the annotatio
4a40: 6e 20 70 72 6f 63 65 73 73 20 62 79 20 73 70 65 n process by spe
4a50: 63 69 66 79 69 6e 67 20 74 68 65 20 66 69 6c 65 cifying the file
4a60: 20 74 68 61 74 20 69 73 0a 2a 2a 20 74 6f 20 62 that is.** to b
4a70: 65 20 61 6e 6e 6f 74 61 74 65 64 2e 20 20 54 68 e annotated. Th
4a80: 65 20 61 6e 6e 6f 74 61 74 6f 72 20 74 61 6b 65 e annotator take
4a90: 73 20 63 6f 6e 74 72 6f 6c 20 6f 66 20 74 68 65 s control of the
4aa0: 20 69 6e 70 75 74 20 42 6c 6f 62 20 61 6e 64 0a input Blob and.
4ab0: 2a 2a 20 77 69 6c 6c 20 72 65 6c 65 61 73 65 20 ** will release
4ac0: 69 74 20 77 68 65 6e 20 69 74 20 69 73 20 66 69 it when it is fi
4ad0: 6e 69 73 68 65 64 20 77 69 74 68 20 69 74 2e 0a nished with it..
4ae0: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 61 6e */.static int an
4af0: 6e 6f 74 61 74 69 6f 6e 5f 73 74 61 72 74 28 41 notation_start(A
4b00: 6e 6e 6f 74 61 74 6f 72 20 2a 70 2c 20 42 6c 6f nnotator *p, Blo
4b10: 62 20 2a 70 49 6e 70 75 74 29 7b 0a 20 20 69 6e b *pInput){. in
4b20: 74 20 69 3b 0a 0a 20 20 6d 65 6d 73 65 74 28 70 t i;.. memset(p
4b30: 2c 20 30 2c 20 73 69 7a 65 6f 66 28 2a 70 29 29 , 0, sizeof(*p))
4b40: 3b 0a 20 20 70 2d 3e 63 2e 61 54 6f 20 3d 20 62 ;. p->c.aTo = b
4b50: 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 reak_into_lines(
4b60: 62 6c 6f 62 5f 73 74 72 28 70 49 6e 70 75 74 29 blob_str(pInput)
4b70: 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 70 49 6e 70 , blob_size(pInp
4b80: 75 74 29 2c 26 70 2d 3e 63 2e 6e 54 6f 2c 31 29 ut),&p->c.nTo,1)
4b90: 3b 0a 20 20 69 66 28 20 70 2d 3e 63 2e 61 54 6f ;. if( p->c.aTo
4ba0: 3d 3d 30 20 29 7b 0a 20 20 20 20 72 65 74 75 72 ==0 ){. retur
4bb0: 6e 20 31 3b 0a 20 20 7d 0a 20 20 70 2d 3e 61 4f n 1;. }. p->aO
4bc0: 72 69 67 20 3d 20 66 6f 73 73 69 6c 5f 6d 61 6c rig = fossil_mal
4bd0: 6c 6f 63 28 20 73 69 7a 65 6f 66 28 70 2d 3e 61 loc( sizeof(p->a
4be0: 4f 72 69 67 5b 30 5d 29 2a 70 2d 3e 63 2e 6e 54 Orig[0])*p->c.nT
4bf0: 6f 20 29 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 o );. for(i=0;
4c00: 69 3c 70 2d 3e 63 2e 6e 54 6f 3b 20 69 2b 2b 29 i<p->c.nTo; i++)
4c10: 7b 0a 20 20 20 20 70 2d 3e 61 4f 72 69 67 5b 69 {. p->aOrig[i
4c20: 5d 2e 7a 20 3d 20 70 2d 3e 63 2e 61 54 6f 5b 69 ].z = p->c.aTo[i
4c30: 5d 2e 7a 3b 0a 20 20 20 20 70 2d 3e 61 4f 72 69 ].z;. p->aOri
4c40: 67 5b 69 5d 2e 6e 20 3d 20 70 2d 3e 63 2e 61 54 g[i].n = p->c.aT
4c50: 6f 5b 69 5d 2e 68 20 26 20 4c 45 4e 47 54 48 5f o[i].h & LENGTH_
4c60: 4d 41 53 4b 3b 0a 20 20 20 20 70 2d 3e 61 4f 72 MASK;. p->aOr
4c70: 69 67 5b 69 5d 2e 7a 53 72 63 20 3d 20 30 3b 0a ig[i].zSrc = 0;.
4c80: 20 20 7d 0a 20 20 70 2d 3e 6e 4f 72 69 67 20 3d }. p->nOrig =
4c90: 20 70 2d 3e 63 2e 6e 54 6f 3b 0a 20 20 72 65 74 p->c.nTo;. ret
4ca0: 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 urn 0;.}../*.**
4cb0: 54 68 65 20 69 6e 70 75 74 20 70 50 61 72 65 6e The input pParen
4cc0: 74 20 69 73 20 74 68 65 20 6e 65 78 74 20 6d 6f t is the next mo
4cd0: 73 74 20 72 65 63 65 6e 74 20 61 6e 63 65 73 74 st recent ancest
4ce0: 6f 72 20 6f 66 20 74 68 65 20 66 69 6c 65 0a 2a or of the file.*
4cf0: 2a 20 62 65 69 6e 67 20 61 6e 6e 6f 74 61 74 65 * being annotate
4d00: 64 2e 20 20 44 6f 20 61 6e 6f 74 68 65 72 20 73 d. Do another s
4d10: 74 65 70 20 6f 66 20 74 68 65 20 61 6e 6e 6f 74 tep of the annot
4d20: 61 74 69 6f 6e 2e 20 20 52 65 74 75 72 6e 20 74 ation. Return t
4d30: 72 75 65 0a 2a 2a 20 69 66 20 61 64 64 69 74 69 rue.** if additi
4d40: 6f 6e 61 6c 20 61 6e 6e 6f 74 61 74 69 6f 6e 20 onal annotation
4d50: 69 73 20 72 65 71 75 69 72 65 64 2e 20 20 7a 50 is required. zP
4d60: 4e 61 6d 65 20 69 73 20 74 68 65 20 74 61 67 20 Name is the tag
4d70: 74 6f 20 69 6e 73 65 72 74 0a 2a 2a 20 6f 6e 20 to insert.** on
4d80: 65 61 63 68 20 6c 69 6e 65 20 6f 66 20 74 68 65 each line of the
4d90: 20 66 69 6c 65 20 62 65 69 6e 67 20 61 6e 6e 6f file being anno
4da0: 74 61 74 65 64 20 74 68 61 74 20 77 61 73 20 63 tated that was c
4db0: 6f 6e 74 72 69 62 75 74 65 64 20 62 79 0a 2a 2a ontributed by.**
4dc0: 20 70 50 61 72 65 6e 74 2e 20 20 4d 65 6d 6f 72 pParent. Memor
4dd0: 79 20 74 6f 20 68 6f 6c 64 20 7a 50 4e 61 6d 65 y to hold zPName
4de0: 20 69 73 20 6c 65 61 6b 65 64 2e 0a 2a 2f 0a 73 is leaked..*/.s
4df0: 74 61 74 69 63 20 69 6e 74 20 61 6e 6e 6f 74 61 tatic int annota
4e00: 74 69 6f 6e 5f 73 74 65 70 28 41 6e 6e 6f 74 61 tion_step(Annota
4e10: 74 6f 72 20 2a 70 2c 20 42 6c 6f 62 20 2a 70 50 tor *p, Blob *pP
4e20: 61 72 65 6e 74 2c 20 63 68 61 72 20 2a 7a 50 4e arent, char *zPN
4e30: 61 6d 65 29 7b 0a 20 20 69 6e 74 20 69 2c 20 6a ame){. int i, j
4e40: 3b 0a 20 20 69 6e 74 20 6c 6e 54 6f 3b 0a 0a 20 ;. int lnTo;..
4e50: 20 2f 2a 20 50 72 65 70 61 72 65 20 74 68 65 20 /* Prepare the
4e60: 70 61 72 65 6e 74 20 66 69 6c 65 20 74 6f 20 62 parent file to b
4e70: 65 20 64 69 66 66 65 64 20 2a 2f 0a 20 20 70 2d e diffed */. p-
4e80: 3e 63 2e 61 46 72 6f 6d 20 3d 20 62 72 65 61 6b >c.aFrom = break
4e90: 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 _into_lines(blob
4ea0: 5f 73 74 72 28 70 50 61 72 65 6e 74 29 2c 20 62 _str(pParent), b
4eb0: 6c 6f 62 5f 73 69 7a 65 28 70 50 61 72 65 6e 74 lob_size(pParent
4ec0: 29 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 ),.
4ed0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
4ee0: 20 20 20 26 70 2d 3e 63 2e 6e 46 72 6f 6d 2c 20 &p->c.nFrom,
4ef0: 31 29 3b 0a 20 20 69 66 28 20 70 2d 3e 63 2e 61 1);. if( p->c.a
4f00: 46 72 6f 6d 3d 3d 30 20 29 7b 0a 20 20 20 20 72 From==0 ){. r
4f10: 65 74 75 72 6e 20 31 3b 0a 20 20 7d 0a 0a 20 20 eturn 1;. }..
4f20: 2f 2a 20 43 6f 6d 70 75 74 65 20 74 68 65 20 64 /* Compute the d
4f30: 69 66 66 65 72 65 6e 63 65 73 20 67 6f 69 6e 67 ifferences going
4f40: 20 66 72 6f 6d 20 70 50 61 72 65 6e 74 20 74 6f from pParent to
4f50: 20 74 68 65 20 66 69 6c 65 20 62 65 69 6e 67 0a the file being.
4f60: 20 20 2a 2a 20 61 6e 6e 6f 74 61 74 65 64 2e 20 ** annotated.
4f70: 2a 2f 0a 20 20 64 69 66 66 5f 61 6c 6c 28 26 70 */. diff_all(&p
4f80: 2d 3e 63 29 3b 0a 0a 20 20 2f 2a 20 57 68 65 72 ->c);.. /* Wher
4f90: 65 20 6e 65 77 20 6c 69 6e 65 73 20 61 72 65 20 e new lines are
4fa0: 69 6e 73 65 72 74 65 64 20 6f 6e 20 74 68 69 73 inserted on this
4fb0: 20 64 69 66 66 65 72 65 6e 63 65 2c 20 72 65 63 difference, rec
4fc0: 6f 72 64 20 74 68 65 0a 20 20 2a 2a 20 7a 50 4e ord the. ** zPN
4fd0: 61 6d 65 20 61 73 20 74 68 65 20 73 6f 75 72 63 ame as the sourc
4fe0: 65 20 6f 66 20 74 68 65 20 6e 65 77 20 6c 69 6e e of the new lin
4ff0: 65 2e 0a 20 20 2a 2f 0a 20 20 66 6f 72 28 69 3d e.. */. for(i=
5000: 6c 6e 54 6f 3d 30 3b 20 69 3c 70 2d 3e 63 2e 6e lnTo=0; i<p->c.n
5010: 45 64 69 74 3b 20 69 2b 3d 33 29 7b 0a 20 20 20 Edit; i+=3){.
5020: 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 70 2d 3e 63 for(j=0; j<p->c
5030: 2e 61 45 64 69 74 5b 69 5d 3b 20 6a 2b 2b 2c 20 .aEdit[i]; j++,
5040: 6c 6e 54 6f 2b 2b 29 7b 0a 20 20 20 20 20 20 70 lnTo++){. p
5050: 2d 3e 61 4f 72 69 67 5b 6c 6e 54 6f 5d 2e 7a 53 ->aOrig[lnTo].zS
5060: 72 63 20 3d 20 7a 50 4e 61 6d 65 3b 0a 20 20 20 rc = zPName;.
5070: 20 7d 0a 20 20 20 20 6c 6e 54 6f 20 2b 3d 20 70 }. lnTo += p
5080: 2d 3e 63 2e 61 45 64 69 74 5b 69 2b 32 5d 3b 0a ->c.aEdit[i+2];.
5090: 20 20 7d 0a 0a 20 20 2f 2a 20 43 6c 65 61 72 20 }.. /* Clear
50a0: 6f 75 74 20 74 68 65 20 64 69 66 66 20 72 65 73 out the diff res
50b0: 75 6c 74 73 20 2a 2f 0a 20 20 66 72 65 65 28 70 ults */. free(p
50c0: 2d 3e 63 2e 61 45 64 69 74 29 3b 0a 20 20 70 2d ->c.aEdit);. p-
50d0: 3e 63 2e 61 45 64 69 74 20 3d 20 30 3b 0a 20 20 >c.aEdit = 0;.
50e0: 70 2d 3e 63 2e 6e 45 64 69 74 20 3d 20 30 3b 0a p->c.nEdit = 0;.
50f0: 20 20 70 2d 3e 63 2e 6e 45 64 69 74 41 6c 6c 6f p->c.nEditAllo
5100: 63 20 3d 20 30 3b 0a 0a 20 20 2f 2a 20 43 6c 65 c = 0;.. /* Cle
5110: 61 72 20 6f 75 74 20 74 68 65 20 66 72 6f 6d 20 ar out the from
5120: 66 69 6c 65 20 2a 2f 0a 20 20 66 72 65 65 28 70 file */. free(p
5130: 2d 3e 63 2e 61 46 72 6f 6d 29 3b 20 20 20 20 0a ->c.aFrom); .
5140: 20 20 62 6c 6f 62 5f 7a 65 72 6f 28 70 50 61 72 blob_zero(pPar
5150: 65 6e 74 29 3b 0a 0a 20 20 2f 2a 20 52 65 74 75 ent);.. /* Retu
5160: 72 6e 20 6e 6f 20 65 72 72 6f 72 73 20 2a 2f 0a rn no errors */.
5170: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 0a return 0;.}...
5180: 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 /*.** COMMAND: t
5190: 65 73 74 2d 61 6e 6e 6f 74 61 74 65 2d 73 74 65 est-annotate-ste
51a0: 70 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 74 5f 61 p.*/.void test_a
51b0: 6e 6e 6f 74 61 74 65 5f 73 74 65 70 5f 63 6d 64 nnotate_step_cmd
51c0: 28 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 6f (void){. Blob o
51d0: 72 69 67 2c 20 62 3b 0a 20 20 41 6e 6e 6f 74 61 rig, b;. Annota
51e0: 74 6f 72 20 78 3b 0a 20 20 69 6e 74 20 69 3b 0a tor x;. int i;.
51f0: 0a 20 20 69 66 28 20 67 2e 61 72 67 63 3c 34 20 . if( g.argc<4
5200: 29 20 75 73 61 67 65 28 22 52 49 44 31 20 52 49 ) usage("RID1 RI
5210: 44 32 20 2e 2e 2e 22 29 3b 0a 20 20 64 62 5f 6d D2 ...");. db_m
5220: 75 73 74 5f 62 65 5f 77 69 74 68 69 6e 5f 74 72 ust_be_within_tr
5230: 65 65 28 29 3b 0a 20 20 62 6c 6f 62 5f 7a 65 72 ee();. blob_zer
5240: 6f 28 26 62 29 3b 0a 20 20 63 6f 6e 74 65 6e 74 o(&b);. content
5250: 5f 67 65 74 28 6e 61 6d 65 5f 74 6f 5f 72 69 64 _get(name_to_rid
5260: 28 67 2e 61 72 67 76 5b 32 5d 29 2c 20 26 6f 72 (g.argv[2]), &or
5270: 69 67 29 3b 0a 20 20 69 66 28 20 61 6e 6e 6f 74 ig);. if( annot
5280: 61 74 69 6f 6e 5f 73 74 61 72 74 28 26 78 2c 20 ation_start(&x,
5290: 26 6f 72 69 67 29 20 29 7b 0a 20 20 20 20 66 6f &orig) ){. fo
52a0: 73 73 69 6c 5f 66 61 74 61 6c 28 22 62 69 6e 61 ssil_fatal("bina
52b0: 72 79 20 66 69 6c 65 22 29 3b 0a 20 20 7d 0a 20 ry file");. }.
52c0: 20 66 6f 72 28 69 3d 33 3b 20 69 3c 67 2e 61 72 for(i=3; i<g.ar
52d0: 67 63 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 62 6c gc; i++){. bl
52e0: 6f 62 5f 7a 65 72 6f 28 26 62 29 3b 0a 20 20 20 ob_zero(&b);.
52f0: 20 63 6f 6e 74 65 6e 74 5f 67 65 74 28 6e 61 6d content_get(nam
5300: 65 5f 74 6f 5f 72 69 64 28 67 2e 61 72 67 76 5b e_to_rid(g.argv[
5310: 69 5d 29 2c 20 26 62 29 3b 0a 20 20 20 20 69 66 i]), &b);. if
5320: 28 20 61 6e 6e 6f 74 61 74 69 6f 6e 5f 73 74 65 ( annotation_ste
5330: 70 28 26 78 2c 20 26 62 2c 20 67 2e 61 72 67 76 p(&x, &b, g.argv
5340: 5b 69 2d 31 5d 29 20 29 7b 0a 20 20 20 20 20 20 [i-1]) ){.
5350: 66 6f 73 73 69 6c 5f 66 61 74 61 6c 28 22 62 69 fossil_fatal("bi
5360: 6e 61 72 79 20 66 69 6c 65 22 29 3b 0a 20 20 20 nary file");.
5370: 20 7d 0a 20 20 7d 0a 20 20 66 6f 72 28 69 3d 30 }. }. for(i=0
5380: 3b 20 69 3c 78 2e 6e 4f 72 69 67 3b 20 69 2b 2b ; i<x.nOrig; i++
5390: 29 7b 0a 20 20 20 20 63 6f 6e 73 74 20 63 68 61 ){. const cha
53a0: 72 20 2a 7a 53 72 63 20 3d 20 78 2e 61 4f 72 69 r *zSrc = x.aOri
53b0: 67 5b 69 5d 2e 7a 53 72 63 3b 0a 20 20 20 20 69 g[i].zSrc;. i
53c0: 66 28 20 7a 53 72 63 3d 3d 30 20 29 20 7a 53 72 f( zSrc==0 ) zSr
53d0: 63 20 3d 20 67 2e 61 72 67 76 5b 67 2e 61 72 67 c = g.argv[g.arg
53e0: 63 2d 31 5d 3b 0a 20 20 20 20 70 72 69 6e 74 66 c-1];. printf
53f0: 28 22 25 31 30 73 3a 20 25 2e 2a 73 5c 6e 22 2c ("%10s: %.*s\n",
5400: 20 7a 53 72 63 2c 20 78 2e 61 4f 72 69 67 5b 69 zSrc, x.aOrig[i
5410: 5d 2e 6e 2c 20 78 2e 61 4f 72 69 67 5b 69 5d 2e ].n, x.aOrig[i].
5420: 7a 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a z);. }.}../*.**
5430: 20 43 6f 6d 70 75 74 65 20 61 20 63 6f 6d 70 6c Compute a compl
5440: 65 74 65 20 61 6e 6e 6f 74 61 74 69 6f 6e 20 6f ete annotation o
5450: 6e 20 61 20 66 69 6c 65 2e 20 20 54 68 65 20 66 n a file. The f
5460: 69 6c 65 20 69 73 20 69 64 65 6e 74 69 66 69 65 ile is identifie
5470: 64 0a 2a 2a 20 62 79 20 69 74 73 20 66 69 6c 65 d.** by its file
5480: 6e 61 6d 65 20 6e 75 6d 62 65 72 20 28 66 69 6c name number (fil
5490: 65 6e 61 6d 65 2e 66 6e 69 64 29 20 61 6e 64 20 ename.fnid) and
54a0: 74 68 65 20 62 61 73 65 6c 69 6e 65 20 69 6e 20 the baseline in
54b0: 77 68 69 63 68 0a 2a 2a 20 69 74 20 77 61 73 20 which.** it was
54c0: 63 68 65 63 6b 65 64 20 69 6e 20 28 6d 6c 69 6e checked in (mlin
54d0: 6b 2e 6d 69 64 29 2e 0a 2a 2f 0a 73 74 61 74 69 k.mid)..*/.stati
54e0: 63 20 76 6f 69 64 20 61 6e 6e 6f 74 61 74 65 5f c void annotate_
54f0: 66 69 6c 65 28 41 6e 6e 6f 74 61 74 6f 72 20 2a file(Annotator *
5500: 70 2c 20 69 6e 74 20 66 6e 69 64 2c 20 69 6e 74 p, int fnid, int
5510: 20 6d 69 64 2c 20 69 6e 74 20 77 65 62 4c 61 62 mid, int webLab
5520: 65 6c 29 7b 0a 20 20 42 6c 6f 62 20 74 6f 41 6e el){. Blob toAn
5530: 6e 6f 74 61 74 65 3b 20 20 20 20 20 2f 2a 20 54 notate; /* T
5540: 65 78 74 20 6f 66 20 74 68 65 20 66 69 6e 61 6c ext of the final
5550: 20 76 65 72 73 69 6f 6e 20 6f 66 20 74 68 65 20 version of the
5560: 66 69 6c 65 20 2a 2f 0a 20 20 42 6c 6f 62 20 73 file */. Blob s
5570: 74 65 70 3b 20 20 20 20 20 20 20 20 20 20 20 2f tep; /
5580: 2a 20 54 65 78 74 20 6f 66 20 70 72 65 76 69 6f * Text of previo
5590: 75 73 20 72 65 76 69 73 69 6f 6e 20 2a 2f 0a 20 us revision */.
55a0: 20 69 6e 74 20 72 69 64 3b 20 20 20 20 20 20 20 int rid;
55b0: 20 20 20 20 20 20 2f 2a 20 41 72 74 69 66 61 63 /* Artifac
55c0: 74 20 49 44 20 6f 66 20 74 68 65 20 66 69 6c 65 t ID of the file
55d0: 20 62 65 69 6e 67 20 61 6e 6e 6f 74 61 74 65 64 being annotated
55e0: 20 2a 2f 0a 20 20 63 68 61 72 20 2a 7a 4c 61 62 */. char *zLab
55f0: 65 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 61 el; /* La
5600: 62 65 6c 20 74 6f 20 61 70 70 6c 79 20 74 6f 20 bel to apply to
5610: 61 20 6c 69 6e 65 20 2a 2f 0a 20 20 53 74 6d 74 a line */. Stmt
5620: 20 71 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 q;
5630: 20 2f 2a 20 51 75 65 72 79 20 72 65 74 75 72 6e /* Query return
5640: 69 6e 67 20 61 6c 6c 20 61 6e 63 65 73 74 6f 72 ing all ancestor
5650: 20 76 65 72 73 69 6f 6e 73 20 2a 2f 0a 0a 20 20 versions */..
5660: 2f 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 74 68 /* Initialize th
5670: 65 20 61 6e 6e 6f 74 61 74 69 6f 6e 20 2a 2f 0a e annotation */.
5680: 20 20 72 69 64 20 3d 20 64 62 5f 69 6e 74 28 30 rid = db_int(0
5690: 2c 20 22 53 45 4c 45 43 54 20 66 69 64 20 46 52 , "SELECT fid FR
56a0: 4f 4d 20 6d 6c 69 6e 6b 20 57 48 45 52 45 20 6d OM mlink WHERE m
56b0: 69 64 3d 25 64 20 41 4e 44 20 66 6e 69 64 3d 25 id=%d AND fnid=%
56c0: 64 22 2c 6d 69 64 2c 66 6e 69 64 29 3b 0a 20 20 d",mid,fnid);.
56d0: 69 66 28 20 72 69 64 3d 3d 30 20 29 7b 0a 20 20 if( rid==0 ){.
56e0: 20 20 66 6f 73 73 69 6c 5f 70 61 6e 69 63 28 22 fossil_panic("
56f0: 66 69 6c 65 20 23 25 64 20 69 73 20 75 6e 63 68 file #%d is unch
5700: 61 6e 67 65 64 20 69 6e 20 6d 61 6e 69 66 65 73 anged in manifes
5710: 74 20 23 25 64 22 2c 20 66 6e 69 64 2c 20 6d 69 t #%d", fnid, mi
5720: 64 29 3b 0a 20 20 7d 0a 20 20 69 66 28 20 21 63 d);. }. if( !c
5730: 6f 6e 74 65 6e 74 5f 67 65 74 28 72 69 64 2c 20 ontent_get(rid,
5740: 26 74 6f 41 6e 6e 6f 74 61 74 65 29 20 29 7b 0a &toAnnotate) ){.
5750: 20 20 20 20 66 6f 73 73 69 6c 5f 70 61 6e 69 63 fossil_panic
5760: 28 22 75 6e 61 62 6c 65 20 74 6f 20 72 65 74 72 ("unable to retr
5770: 69 65 76 65 20 63 6f 6e 74 65 6e 74 20 6f 66 20 ieve content of
5780: 61 72 74 69 66 61 63 74 20 23 25 64 22 2c 20 72 artifact #%d", r
5790: 69 64 29 3b 0a 20 20 7d 0a 20 20 64 62 5f 6d 75 id);. }. db_mu
57a0: 6c 74 69 5f 65 78 65 63 28 22 43 52 45 41 54 45 lti_exec("CREATE
57b0: 20 54 45 4d 50 20 54 41 42 4c 45 20 6f 6b 28 72 TEMP TABLE ok(r
57c0: 69 64 20 49 4e 54 45 47 45 52 20 50 52 49 4d 41 id INTEGER PRIMA
57d0: 52 59 20 4b 45 59 29 22 29 3b 0a 20 20 63 6f 6d RY KEY)");. com
57e0: 70 75 74 65 5f 61 6e 63 65 73 74 6f 72 73 28 6d pute_ancestors(m
57f0: 69 64 2c 20 31 30 30 30 30 30 30 30 30 30 29 3b id, 1000000000);
5800: 0a 20 20 61 6e 6e 6f 74 61 74 69 6f 6e 5f 73 74 . annotation_st
5810: 61 72 74 28 70 2c 20 26 74 6f 41 6e 6e 6f 74 61 art(p, &toAnnota
5820: 74 65 29 3b 0a 0a 20 20 64 62 5f 70 72 65 70 61 te);.. db_prepa
5830: 72 65 28 26 71 2c 20 0a 20 20 20 20 22 53 45 4c re(&q, . "SEL
5840: 45 43 54 20 6d 6c 69 6e 6b 2e 66 69 64 2c 20 62 ECT mlink.fid, b
5850: 6c 6f 62 2e 75 75 69 64 2c 20 64 61 74 65 28 65 lob.uuid, date(e
5860: 76 65 6e 74 2e 6d 74 69 6d 65 29 2c 20 22 0a 20 vent.mtime), ".
5870: 20 20 20 22 20 20 20 20 20 20 20 63 6f 61 6c 65 " coale
5880: 73 63 65 28 65 76 65 6e 74 2e 65 75 73 65 72 2c sce(event.euser,
5890: 65 76 65 6e 74 2e 75 73 65 72 29 20 22 0a 20 20 event.user) ".
58a0: 20 20 22 20 20 46 52 4f 4d 20 6d 6c 69 6e 6b 2c " FROM mlink,
58b0: 20 62 6c 6f 62 2c 20 65 76 65 6e 74 22 0a 20 20 blob, event".
58c0: 20 20 22 20 57 48 45 52 45 20 6d 6c 69 6e 6b 2e " WHERE mlink.
58d0: 66 6e 69 64 3d 25 64 22 0a 20 20 20 20 22 20 20 fnid=%d". "
58e0: 20 41 4e 44 20 6d 6c 69 6e 6b 2e 6d 69 64 20 49 AND mlink.mid I
58f0: 4e 20 6f 6b 22 0a 20 20 20 20 22 20 20 20 41 4e N ok". " AN
5900: 44 20 62 6c 6f 62 2e 72 69 64 3d 6d 6c 69 6e 6b D blob.rid=mlink
5910: 2e 6d 69 64 22 0a 20 20 20 20 22 20 20 20 41 4e .mid". " AN
5920: 44 20 65 76 65 6e 74 2e 6f 62 6a 69 64 3d 6d 6c D event.objid=ml
5930: 69 6e 6b 2e 6d 69 64 22 0a 20 20 20 20 22 20 4f ink.mid". " O
5940: 52 44 45 52 20 42 59 20 65 76 65 6e 74 2e 6d 74 RDER BY event.mt
5950: 69 6d 65 20 44 45 53 43 22 2c 0a 20 20 20 20 66 ime DESC",. f
5960: 6e 69 64 0a 20 20 29 3b 0a 20 20 77 68 69 6c 65 nid. );. while
5970: 28 20 64 62 5f 73 74 65 70 28 26 71 29 3d 3d 53 ( db_step(&q)==S
5980: 51 4c 49 54 45 5f 52 4f 57 20 29 7b 0a 20 20 20 QLITE_ROW ){.
5990: 20 69 6e 74 20 70 69 64 20 3d 20 64 62 5f 63 6f int pid = db_co
59a0: 6c 75 6d 6e 5f 69 6e 74 28 26 71 2c 20 30 29 3b lumn_int(&q, 0);
59b0: 0a 20 20 20 20 63 6f 6e 73 74 20 63 68 61 72 20 . const char
59c0: 2a 7a 55 75 69 64 20 3d 20 64 62 5f 63 6f 6c 75 *zUuid = db_colu
59d0: 6d 6e 5f 74 65 78 74 28 26 71 2c 20 31 29 3b 0a mn_text(&q, 1);.
59e0: 20 20 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a const char *
59f0: 7a 44 61 74 65 20 3d 20 64 62 5f 63 6f 6c 75 6d zDate = db_colum
5a00: 6e 5f 74 65 78 74 28 26 71 2c 20 32 29 3b 0a 20 n_text(&q, 2);.
5a10: 20 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a const char *z
5a20: 55 73 65 72 20 3d 20 64 62 5f 63 6f 6c 75 6d 6e User = db_column
5a30: 5f 74 65 78 74 28 26 71 2c 20 33 29 3b 0a 20 20 _text(&q, 3);.
5a40: 20 20 69 66 28 20 77 65 62 4c 61 62 65 6c 20 29 if( webLabel )
5a50: 7b 0a 20 20 20 20 20 20 7a 4c 61 62 65 6c 20 3d {. zLabel =
5a60: 20 6d 70 72 69 6e 74 66 28 0a 20 20 20 20 20 20 mprintf(.
5a70: 20 20 20 20 22 3c 61 20 68 72 65 66 3d 27 25 73 "<a href='%s
5a80: 2f 69 6e 66 6f 2f 25 73 27 20 74 61 72 67 65 74 /info/%s' target
5a90: 3d 27 69 6e 66 6f 77 69 6e 64 6f 77 27 3e 25 2e ='infowindow'>%.
5aa0: 31 30 73 3c 2f 61 3e 20 25 73 20 25 39 2e 39 73 10s</a> %s %9.9s
5ab0: 22 2c 20 0a 20 20 20 20 20 20 20 20 20 20 67 2e ", . g.
5ac0: 7a 54 6f 70 2c 20 7a 55 75 69 64 2c 20 7a 55 75 zTop, zUuid, zUu
5ad0: 69 64 2c 20 7a 44 61 74 65 2c 20 7a 55 73 65 72 id, zDate, zUser
5ae0: 0a 20 20 20 20 20 20 29 3b 0a 20 20 20 20 7d 65 . );. }e
5af0: 6c 73 65 7b 0a 20 20 20 20 20 20 7a 4c 61 62 65 lse{. zLabe
5b00: 6c 20 3d 20 6d 70 72 69 6e 74 66 28 22 25 2e 31 l = mprintf("%.1
5b10: 30 73 20 25 73 20 25 39 2e 39 73 22 2c 20 7a 55 0s %s %9.9s", zU
5b20: 75 69 64 2c 20 7a 44 61 74 65 2c 20 7a 55 73 65 uid, zDate, zUse
5b30: 72 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 63 6f r);. }. co
5b40: 6e 74 65 6e 74 5f 67 65 74 28 70 69 64 2c 20 26 ntent_get(pid, &
5b50: 73 74 65 70 29 3b 0a 20 20 20 20 61 6e 6e 6f 74 step);. annot
5b60: 61 74 69 6f 6e 5f 73 74 65 70 28 70 2c 20 26 73 ation_step(p, &s
5b70: 74 65 70 2c 20 7a 4c 61 62 65 6c 29 3b 0a 20 20 tep, zLabel);.
5b80: 20 20 62 6c 6f 62 5f 72 65 73 65 74 28 26 73 74 blob_reset(&st
5b90: 65 70 29 3b 0a 20 20 7d 0a 20 20 64 62 5f 66 69 ep);. }. db_fi
5ba0: 6e 61 6c 69 7a 65 28 26 71 29 3b 0a 7d 0a 0a 2f nalize(&q);.}../
5bb0: 2a 0a 2a 2a 20 57 45 42 50 41 47 45 3a 20 61 6e *.** WEBPAGE: an
5bc0: 6e 6f 74 61 74 65 0a 2a 2a 0a 2a 2a 20 51 75 65 notate.**.** Que
5bd0: 72 79 20 70 61 72 61 6d 65 74 65 72 73 3a 0a 2a ry parameters:.*
5be0: 2a 0a 2a 2a 20 20 20 20 63 68 65 63 6b 69 6e 3d *.** checkin=
5bf0: 49 44 20 20 20 20 20 20 20 20 20 20 54 68 65 20 ID The
5c00: 6d 61 6e 69 66 65 73 74 20 49 44 20 61 74 20 77 manifest ID at w
5c10: 68 69 63 68 20 74 6f 20 73 74 61 72 74 20 74 68 hich to start th
5c20: 65 20 61 6e 6e 6f 74 61 74 69 6f 6e 0a 2a 2a 20 e annotation.**
5c30: 20 20 20 66 69 6c 65 6e 61 6d 65 3d 46 49 4c 45 filename=FILE
5c40: 4e 41 4d 45 20 20 20 54 68 65 20 66 69 6c 65 6e NAME The filen
5c50: 61 6d 65 2e 0a 2a 2f 0a 76 6f 69 64 20 61 6e 6e ame..*/.void ann
5c60: 6f 74 61 74 69 6f 6e 5f 70 61 67 65 28 76 6f 69 otation_page(voi
5c70: 64 29 7b 0a 20 20 69 6e 74 20 6d 69 64 3b 0a 20 d){. int mid;.
5c80: 20 69 6e 74 20 66 6e 69 64 3b 0a 20 20 69 6e 74 int fnid;. int
5c90: 20 69 3b 0a 20 20 41 6e 6e 6f 74 61 74 6f 72 20 i;. Annotator
5ca0: 61 6e 6e 3b 0a 0a 20 20 6c 6f 67 69 6e 5f 63 68 ann;.. login_ch
5cb0: 65 63 6b 5f 63 72 65 64 65 6e 74 69 61 6c 73 28 eck_credentials(
5cc0: 29 3b 0a 20 20 69 66 28 20 21 67 2e 6f 6b 52 65 );. if( !g.okRe
5cd0: 61 64 20 29 7b 20 6c 6f 67 69 6e 5f 6e 65 65 64 ad ){ login_need
5ce0: 65 64 28 29 3b 20 72 65 74 75 72 6e 3b 20 7d 0a ed(); return; }.
5cf0: 20 20 6d 69 64 20 3d 20 6e 61 6d 65 5f 74 6f 5f mid = name_to_
5d00: 72 69 64 28 50 44 28 22 63 68 65 63 6b 69 6e 22 rid(PD("checkin"
5d10: 2c 22 30 22 29 29 3b 0a 20 20 66 6e 69 64 20 3d ,"0"));. fnid =
5d20: 20 64 62 5f 69 6e 74 28 30 2c 20 22 53 45 4c 45 db_int(0, "SELE
5d30: 43 54 20 66 6e 69 64 20 46 52 4f 4d 20 66 69 6c CT fnid FROM fil
5d40: 65 6e 61 6d 65 20 57 48 45 52 45 20 6e 61 6d 65 ename WHERE name
5d50: 3d 25 51 22 2c 20 50 28 22 66 69 6c 65 6e 61 6d =%Q", P("filenam
5d60: 65 22 29 29 3b 0a 20 20 69 66 28 20 6d 69 64 3d e"));. if( mid=
5d70: 3d 30 20 7c 7c 20 66 6e 69 64 3d 3d 30 20 29 7b =0 || fnid==0 ){
5d80: 20 66 6f 73 73 69 6c 5f 72 65 64 69 72 65 63 74 fossil_redirect
5d90: 5f 68 6f 6d 65 28 29 3b 20 7d 0a 20 20 69 66 28 _home(); }. if(
5da0: 20 21 64 62 5f 65 78 69 73 74 73 28 22 53 45 4c !db_exists("SEL
5db0: 45 43 54 20 31 20 46 52 4f 4d 20 6d 6c 69 6e 6b ECT 1 FROM mlink
5dc0: 20 57 48 45 52 45 20 6d 69 64 3d 25 64 20 41 4e WHERE mid=%d AN
5dd0: 44 20 66 6e 69 64 3d 25 64 22 2c 6d 69 64 2c 66 D fnid=%d",mid,f
5de0: 6e 69 64 29 20 29 7b 0a 20 20 20 20 66 6f 73 73 nid) ){. foss
5df0: 69 6c 5f 72 65 64 69 72 65 63 74 5f 68 6f 6d 65 il_redirect_home
5e00: 28 29 3b 0a 20 20 7d 0a 20 20 73 74 79 6c 65 5f ();. }. style_
5e10: 68 65 61 64 65 72 28 22 46 69 6c 65 20 41 6e 6e header("File Ann
5e20: 6f 74 61 74 69 6f 6e 22 29 3b 0a 20 20 61 6e 6e otation");. ann
5e30: 6f 74 61 74 65 5f 66 69 6c 65 28 26 61 6e 6e 2c otate_file(&ann,
5e40: 20 66 6e 69 64 2c 20 6d 69 64 2c 20 67 2e 6f 6b fnid, mid, g.ok
5e50: 48 69 73 74 6f 72 79 29 3b 0a 20 20 40 20 3c 70 History);. @ <p
5e60: 72 65 3e 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 re>. for(i=0; i
5e70: 3c 61 6e 6e 2e 6e 4f 72 69 67 3b 20 69 2b 2b 29 <ann.nOrig; i++)
5e80: 7b 0a 20 20 20 20 28 28 63 68 61 72 2a 29 61 6e {. ((char*)an
5e90: 6e 2e 61 4f 72 69 67 5b 69 5d 2e 7a 29 5b 61 6e n.aOrig[i].z)[an
5ea0: 6e 2e 61 4f 72 69 67 5b 69 5d 2e 6e 5d 20 3d 20 n.aOrig[i].n] =
5eb0: 30 3b 0a 20 20 20 20 40 20 25 73 28 61 6e 6e 2e 0;. @ %s(ann.
5ec0: 61 4f 72 69 67 5b 69 5d 2e 7a 53 72 63 29 3a 20 aOrig[i].zSrc):
5ed0: 25 68 28 61 6e 6e 2e 61 4f 72 69 67 5b 69 5d 2e %h(ann.aOrig[i].
5ee0: 7a 29 0a 20 20 7d 0a 20 20 40 20 3c 2f 70 72 65 z). }. @ </pre
5ef0: 3e 0a 20 20 73 74 79 6c 65 5f 66 6f 6f 74 65 72 >. style_footer
5f00: 28 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 4f 4d ();.}../*.** COM
5f10: 4d 41 4e 44 3a 20 61 6e 6e 6f 74 61 74 65 0a 2a MAND: annotate.*
5f20: 2a 0a 2a 2a 20 25 66 6f 73 73 69 6c 20 61 6e 6e *.** %fossil ann
5f30: 6f 74 61 74 65 20 46 49 4c 45 4e 41 4d 45 0a 2a otate FILENAME.*
5f40: 2a 0a 2a 2a 20 4f 75 74 70 75 74 20 74 68 65 20 *.** Output the
5f50: 74 65 78 74 20 6f 66 20 61 20 66 69 6c 65 20 77 text of a file w
5f60: 69 74 68 20 6d 61 72 6b 69 6e 67 73 20 74 6f 20 ith markings to
5f70: 73 68 6f 77 20 77 68 65 6e 20 65 61 63 68 20 6c show when each l
5f80: 69 6e 65 20 6f 66 0a 2a 2a 20 74 68 65 20 66 69 ine of.** the fi
5f90: 6c 65 20 77 61 73 20 6c 61 73 74 20 6d 6f 64 69 le was last modi
5fa0: 66 69 65 64 2e 0a 2a 2f 0a 76 6f 69 64 20 61 6e fied..*/.void an
5fb0: 6e 6f 74 61 74 65 5f 63 6d 64 28 76 6f 69 64 29 notate_cmd(void)
5fc0: 7b 0a 20 20 69 6e 74 20 66 6e 69 64 3b 20 20 20 {. int fnid;
5fd0: 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 6e 61 6d /* Filenam
5fe0: 65 20 49 44 20 2a 2f 0a 20 20 69 6e 74 20 66 69 e ID */. int fi
5ff0: 64 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 d; /* F
6000: 69 6c 65 20 69 6e 73 74 61 6e 63 65 20 49 44 20 ile instance ID
6010: 2a 2f 0a 20 20 69 6e 74 20 6d 69 64 3b 20 20 20 */. int mid;
6020: 20 20 20 20 20 20 20 2f 2a 20 4d 61 6e 69 66 65 /* Manife
6030: 73 74 20 77 68 65 72 65 20 66 69 6c 65 20 77 61 st where file wa
6040: 73 20 63 68 65 63 6b 65 64 20 69 6e 20 2a 2f 0a s checked in */.
6050: 20 20 42 6c 6f 62 20 74 72 65 65 6e 61 6d 65 3b Blob treename;
6060: 20 20 20 20 2f 2a 20 46 49 4c 45 4e 41 4d 45 20 /* FILENAME
6070: 74 72 61 6e 73 6c 61 74 65 64 20 74 6f 20 63 61 translated to ca
6080: 6e 6f 6e 69 63 61 6c 20 66 6f 72 6d 20 2a 2f 0a nonical form */.
6090: 20 20 63 68 61 72 20 2a 7a 46 69 6c 65 6e 61 6d char *zFilenam
60a0: 65 3b 20 20 2f 2a 20 43 61 6e 6e 6f 6e 69 63 61 e; /* Cannonica
60b0: 6c 20 66 69 6c 65 6e 61 6d 65 20 2a 2f 0a 20 20 l filename */.
60c0: 41 6e 6e 6f 74 61 74 6f 72 20 61 6e 6e 3b 20 20 Annotator ann;
60d0: 20 20 2f 2a 20 54 68 65 20 61 6e 6e 6f 74 61 74 /* The annotat
60e0: 69 6f 6e 20 6f 66 20 74 68 65 20 66 69 6c 65 20 ion of the file
60f0: 2a 2f 0a 20 20 69 6e 74 20 69 3b 20 20 20 20 20 */. int i;
6100: 20 20 20 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 /* Loop c
6110: 6f 75 6e 74 65 72 20 2a 2f 0a 0a 20 20 64 62 5f ounter */.. db_
6120: 6d 75 73 74 5f 62 65 5f 77 69 74 68 69 6e 5f 74 must_be_within_t
6130: 72 65 65 28 29 3b 0a 20 20 69 66 20 28 67 2e 61 ree();. if (g.a
6140: 72 67 63 3c 33 29 20 7b 0a 20 20 20 20 75 73 61 rgc<3) {. usa
6150: 67 65 28 22 46 49 4c 45 4e 41 4d 45 22 29 3b 0a ge("FILENAME");.
6160: 20 20 7d 0a 20 20 66 69 6c 65 5f 74 72 65 65 5f }. file_tree_
6170: 6e 61 6d 65 28 67 2e 61 72 67 76 5b 32 5d 2c 20 name(g.argv[2],
6180: 26 74 72 65 65 6e 61 6d 65 2c 20 31 29 3b 0a 20 &treename, 1);.
6190: 20 7a 46 69 6c 65 6e 61 6d 65 20 3d 20 62 6c 6f zFilename = blo
61a0: 62 5f 73 74 72 28 26 74 72 65 65 6e 61 6d 65 29 b_str(&treename)
61b0: 3b 0a 20 20 66 6e 69 64 20 3d 20 64 62 5f 69 6e ;. fnid = db_in
61c0: 74 28 30 2c 20 22 53 45 4c 45 43 54 20 66 6e 69 t(0, "SELECT fni
61d0: 64 20 46 52 4f 4d 20 66 69 6c 65 6e 61 6d 65 20 d FROM filename
61e0: 57 48 45 52 45 20 6e 61 6d 65 3d 25 51 22 2c 20 WHERE name=%Q",
61f0: 7a 46 69 6c 65 6e 61 6d 65 29 3b 0a 20 20 69 66 zFilename);. if
6200: 28 20 66 6e 69 64 3d 3d 30 20 29 7b 0a 20 20 20 ( fnid==0 ){.
6210: 20 66 6f 73 73 69 6c 5f 66 61 74 61 6c 28 22 6e fossil_fatal("n
6220: 6f 20 73 75 63 68 20 66 69 6c 65 3a 20 25 73 22 o such file: %s"
6230: 2c 20 7a 46 69 6c 65 6e 61 6d 65 29 3b 0a 20 20 , zFilename);.
6240: 7d 0a 20 20 66 69 64 20 3d 20 64 62 5f 69 6e 74 }. fid = db_int
6250: 28 30 2c 20 22 53 45 4c 45 43 54 20 72 69 64 20 (0, "SELECT rid
6260: 46 52 4f 4d 20 76 66 69 6c 65 20 57 48 45 52 45 FROM vfile WHERE
6270: 20 70 61 74 68 6e 61 6d 65 3d 25 51 22 2c 20 7a pathname=%Q", z
6280: 46 69 6c 65 6e 61 6d 65 29 3b 0a 20 20 69 66 28 Filename);. if(
6290: 20 66 69 64 3d 3d 30 20 29 7b 0a 20 20 20 20 66 fid==0 ){. f
62a0: 6f 73 73 69 6c 5f 66 61 74 61 6c 28 22 6e 6f 74 ossil_fatal("not
62b0: 20 70 61 72 74 20 6f 66 20 63 75 72 72 65 6e 74 part of current
62c0: 20 63 68 65 63 6b 6f 75 74 3a 20 25 73 22 2c 20 checkout: %s",
62d0: 7a 46 69 6c 65 6e 61 6d 65 29 3b 0a 20 20 7d 0a zFilename);. }.
62e0: 20 20 6d 69 64 20 3d 20 64 62 5f 69 6e 74 28 30 mid = db_int(0
62f0: 2c 20 22 53 45 4c 45 43 54 20 6d 69 64 20 46 52 , "SELECT mid FR
6300: 4f 4d 20 6d 6c 69 6e 6b 20 57 48 45 52 45 20 66 OM mlink WHERE f
6310: 69 64 3d 25 64 20 41 4e 44 20 66 6e 69 64 3d 25 id=%d AND fnid=%
6320: 64 22 2c 20 66 69 64 2c 20 66 6e 69 64 29 3b 0a d", fid, fnid);.
6330: 20 20 69 66 28 20 6d 69 64 3d 3d 30 20 29 7b 0a if( mid==0 ){.
6340: 20 20 20 20 66 6f 73 73 69 6c 5f 70 61 6e 69 63 fossil_panic
6350: 28 22 75 6e 61 62 6c 65 20 74 6f 20 66 69 6e 64 ("unable to find
6360: 20 6d 61 6e 69 66 65 73 74 22 29 3b 0a 20 20 7d manifest");. }
6370: 0a 20 20 61 6e 6e 6f 74 61 74 65 5f 66 69 6c 65 . annotate_file
6380: 28 26 61 6e 6e 2c 20 66 6e 69 64 2c 20 6d 69 64 (&ann, fnid, mid
6390: 2c 20 30 29 3b 0a 20 20 66 6f 72 28 69 3d 30 3b , 0);. for(i=0;
63a0: 20 69 3c 61 6e 6e 2e 6e 4f 72 69 67 3b 20 69 2b i<ann.nOrig; i+
63b0: 2b 29 7b 0a 20 20 20 20 70 72 69 6e 74 66 28 22 +){. printf("
63c0: 25 73 3a 20 25 2e 2a 73 5c 6e 22 2c 20 61 6e 6e %s: %.*s\n", ann
63d0: 2e 61 4f 72 69 67 5b 69 5d 2e 7a 53 72 63 2c 20 .aOrig[i].zSrc,
63e0: 61 6e 6e 2e 61 4f 72 69 67 5b 69 5d 2e 6e 2c 20 ann.aOrig[i].n,
63f0: 61 6e 6e 2e 61 4f 72 69 67 5b 69 5d 2e 7a 29 3b ann.aOrig[i].z);
6400: 0a 20 20 7d 0a 7d 0a . }.}.