but now i get to step into the git xdiff code and see !!
here's the call to the xdiff implementation: 887 mustbe0(xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec, 888 kvdf, kvdb, (xp.flags & XDF_NEED_MINIMAL) != 0, 889 &xenv)); git added other implementations (patience, histogram) and patched different infrastructure on for those. but i think this is the core xdiff implementation that uses the first-class infrastructure in the xdiff structures. all the variables from xdf1 and xdf2 have been copied into dd1 and dd2: 878 dd1.nrec = xe->xdf1.nreff; 879 dd1.ha = xe->xdf1.ha; 880 dd1.rchg = xe->xdf1.rchg; 881 dd1.rindex = xe->xdf1.rindex; 882 dd2.nrec = xe->xdf2.nreff; 883 dd2.ha = xe->xdf2.ha; 884 dd2.rchg = xe->xdf2.rchg; 885 dd2.rindex = xe->xdf2.rindex; So basically they are presenting the data to xdiff as if all the preprocessed lines never existed. 878 dd1.nrec = xe->xdf1.nreff; // this is the number of lines in file 1 879 dd1.ha = xe->xdf1.ha; // this is the "hash" of every line. it's actually an index into a hash list, same thing 880 dd1.rchg = xe->xdf1.rchg; // this is the change vector -- the algorithm sets 1 to indicate the line does not match 881 dd1.rindex = xe->xdf1.rindex; // this is the vector of pointers to line data including the actual content The goal of the algorithm is to correctly fill rchg, which is its output. In this buggy case, rchg already has some 1s in it (hummm i could just set it to 0s and see if there's a difference ... well if i do that i'd better not stop my debugging session in case it doesn't help!) maybe try that in a bit unsure (gdb) s xdl_recs_cmp (dd1=0x7ffff4b08880, off1=0, lim1=2, dd2=0x7ffff4b088c0, off2=0, lim2=1, kvdf=0x50c000000290, kvdb=0x50c0000002c0, need_min=1, xenv=0x7ffff4b08840) at /home/karl3/projects/zinc/third_party/xdiff/xdiffi.c:259 259 unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha; (gdb) list 254 * (marking changed lines) is done in the two boundary reaching checks. 255 */ 256 int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1, 257 diffdata_t *dd2, long off2, long lim2, 258 long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) { 259 unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha; 260 261 /* 262 * Shrink the box by walking through each diagonal snake (SW and NE). 263 */ This function is supported by xdiffi.c it's kind of the focus of the xdiff library. (previously i was working with xprepare.c which sets up all those structures). i kind of don't expect it to be that long and complex, but i do expect to be highly confused by it. let's list some more lines 261 /* 262 * Shrink the box by walking through each diagonal snake (SW and NE). 263 */ (gdb) list 264 for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++); 265 for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--); 266 267 /* 268 * If one dimension is empty, then all records on the other one must 269 * be obviously changed. 270 */ 271 if (off1 == lim1) { 272 char *rchg2 = dd2->rchg; 273 long *rindex2 = dd2->rindex; (gdb) list 274 275 for (; off2 < lim2; off2++) 276 rchg2[rindex2[off2]] = 1; 277 } else if (off2 == lim2) { 278 char *rchg1 = dd1->rchg; 279 long *rindex1 = dd1->rindex; 280 281 for (; off1 < lim1; off1++) 282 rchg1[rindex1[off1]] = 1; 283 } else { (gdb) list 284 xdpsplit_t spl; 285 spl.i1 = spl.i2 = 0; 286 287 /* 288 * Divide ... 289 */ 290 if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb, 291 need_min, &spl, xenv) < 0) { 292 293 return -1; (gdb) list 294 } 295 296 /* 297 * ... et Impera. 298 */ 299 if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2, 300 kvdf, kvdb, spl.min_lo, xenv) < 0 || 301 xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2, 302 kvdf, kvdb, spl.min_hi, xenv) < 0) { 303 (gdb) list 304 return -1; 305 } 306 } 307 308 return 0; 309 } see? not very long or complex-looking. it looks like its recursive! I'm surprised to encounter a recursive function here, I remember when I wrote recursive functions before I knew about state stacks ... didn't learn too much new after that ... but i used to get a lot of stack overflows, surprised now to see recursive functions 261 /* 262 * Shrink the box by walking through each diagonal snake (SW and NE). 263 */ (gdb) list 264 for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++); 265 for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--); "snakes" are a term from myers first paper on LCS. i don't immediately recall what it refers to, and it's quite important for understanding the terminology of these algorithms (and this is likely that first one as it is still very popular) ... i think a snake is a set of matching lines that can be thought of as a diagonal path through a grid of potential line matchings, one file's line numbers on one axis, and one file's line numbers on another. so in 264 and 265 above, it's looking for starting and ending lines that match, and increasing off and decreasing lim to narrow the problem domain after these lines it then runs some quick checks for unchangedness, if either pair of offs and lims end up touching. we won't have that condition as the window is only partly filled. the ending lines will mismatch; the condition ha1[lim1 - 1] == ha2[lim2 - 1] will be false. i guess i'd better step into that and verify i'm right!