bdiff: balance recursion to avoid quadratic behavior (issue4704) For highly structured files like JSON or XML dumps with large numbers of duplicate lines (eg braces) and isolated matching lines, bdiff could find large numbers of equally good spans. Because it prefers earlier matches, this would result in pathologically unbalance recursion that resulted in quadratic performance. This patch makes it prefer matches closer to the middle that tend to balance recursion. This change improves the speed of a pathological test case from 1100s to 9s. Included is a smaller test that has a roughly 50x safety margin on the performance it accepts. It's likely to fail on pure builds because difflib also has a recursion-balancing problem.

bdiff: deal better with duplicate lines The longest_match code compares all the possible positions in two files to find the best match. Given a pair of sequences, it effectively searches a grid like this: a b b b c . d e . f 0 1 2 3 4 5 6 7 8 9 a 1 - - - - - - - - - b - 2 1 1 - - - - - - b - 1 3 2 - - - - - - b - 1 2 4 - - - - - - . - - - - - 1 - - 1 - Here, the 4 in the middle says "the first four lines of the file match", which it can compute be comparing the fourth lines and then adding one to the result found when comparing the third lines in the entry to the upper left. We generally avoid the quadratic worst case by only looking at lines that match, which is precomputed. We also avoid quadratic storage by only keeping a single column vector and then keeping track of the best match. Unfortunately, this can get us into trouble with the sequences above. Because we want to reuse the '3' value when calculating the '4', we need to be careful not to overwrite it with the '2' we calculate immediately before. If we scan left to right, top to bottom, we're going to have a problem: we'll overwrite our 3 before we use it and calculate a suboptimal best match. To address this, we can either keep two column vectors and swap between them (which significantly complicates bookkeeping), or change our scanning order. If we instead scan from left to right, bottom to top, we'll avoid ever overwriting values we'll need in the future. This unfortunately needs several changes to be made simultaneously: - change the order we build the initial hash chains for the b sequence - change the sentinel values from INT_MAX to -1 - change the visit order in the longest_match inner loop - add a tie-breaker preference for earlier matches This last is needed because we previously had an implicit tie-breaker from our visitation order that our test suite relies on. Later matches can also trigger a bug in the normalization code in diff().

bdiff: fix latent normalization bug This bug is hidden by the current bias towards matches at the beginning of the file. When this bias is tweaked later to address recursion balancing, the normalization code could cause the next block to shrink to a negative length, thus creating invalid delta chunks. We add checks here to disallow that. This bug requires test cases that are an awkwardly large size for the test suite, but is very rapidly picked up by the included torture tester.

bdiff: fold in shift calculation in normalize This just makes the code harder to read without any performance advantage. We're going to make the check here more complex, let's make it simpler first.

bdiff: unify duplicate normalize loops We're about to make the while loop check more complicated, so let's simplify first.

make: backout changeset 51f5fae84e43 Support for '!=' was only added in GNU Make 4.0, and CentOS versions as new as CentOS 7 only carry 3.82. I will leave figuring out compatibility with BSD make as an exercise for interested folks.

tests: test-lock-badness.t message could come later I got this on gcc112: @@ -58,8 +58,8 @@ $ hg -R b ci -A -m b --config hooks.precommit="python:`pwd`/hooks.py:sleepone" > stdout & $ hg -R b up -q --config hooks.pre-update="python:`pwd`/hooks.py:sleephalf" waiting for lock on working directory of b held by '*:*' (glob) - got lock after ? seconds (glob) $ wait + got lock after 1 seconds $ cat stdout adding b

dockerdeb: pass the rest of the args to the builder script It seems this was the original intent of the script so this patch passes the remanining arguments to builddeb.

dockerdeb: fix incorrect number of shifts From the comment, it appears that the original intent was to remove the first two arguments, so this patch does just that.

make: use shell-command assignment instead of $(eval ...) This is portable between BSD and GNU make. As of this change, our Makefile appears to work in both BSD and GNU make, with the caveat that the test-% and testpy-% wildcard rules don't work on BSD make. That said, this still seems worthwhile because it lets the buildbots work more consistently across platforms.

make: do assignment and export in a single statement This is portable between GNU and BSD make, whereas doing the export on its own line confuses BSD make.

make: alter how we compute compiler flags for setup.py This is portable between BSD and GNU make. I'm not thrilled with how it worked out, but it's portable and solves the problem.

revset: unindent "if True" block in sort() It was there to make the previous patch readable.

revset: make sort() do dumb multi-pass sorting for multiple keys (issue5218) Our invert() function was too clever to not take length into account. I could fix the problem by appending '\xff' as a terminator (opposite to '\0'), but it turned out to be slower than simple multi-pass sorting. New implementation is pretty straightforward, which just calls sort() from the last key. We can do that since Python sort() is guaranteed to be stable. It doesn't sound nice to call sort() multiple times, but actually it is faster. That's probably because we have fewer Python codes in hot loop, and can avoid heavy string and list manipulation. revset #0: sort(0:10000, 'branch') 0) 0.412753 1) 0.393254 revset #1: sort(0:10000, '-branch') 0) 0.455377 1) 0.389191 85% revset #2: sort(0:10000, 'date') 0) 0.408082 1) 0.376332 92% revset #3: sort(0:10000, '-date') 0) 0.406910 1) 0.380498 93% revset #4: sort(0:10000, 'desc branch user date rev') 0) 0.542996 1) 0.486397 89% revset #5: sort(0:10000, '-desc -branch -user -date -rev') 0) 0.965032 1) 0.518426 53%

log: fix status template to list copy source per dest (issue5155) Before, copied files were assumed as "A" (added) and listed followed by non-copy added files. This could double entries of a copy if it had "M" (modified) state. So, this patch makes the template check if a file is included in copies dict. This way, entries should never be doubled. The output of "log -Tstatus -C" does not always agree with "status -C --change" due to the bug of "status", which is documented in test-status.t. See also 2963d5c9d90b.