Fossil

Hex Artifact Content
Login

Artifact d9bd197c10a97fb9e7f3f8d88be457738b3cc7b1:


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                             .  }.}.