tests/test-merge5.t
author Matt Mackall <mpm@selenic.com>
Thu, 21 Apr 2016 22:04:11 -0500
branchstable
changeset 29014 f1ca249696ed
parent 28065 6b1fc09c699a
child 45859 527ce85c2e60
permissions -rw-r--r--
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.

  $ hg init
  $ echo This is file a1 > a
  $ echo This is file b1 > b
  $ hg add a b
  $ hg commit -m "commit #0"
  $ echo This is file b22 > b
  $ hg commit -m "comment #1"
  $ hg update 0
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
  $ rm b
  $ hg commit -A -m "comment #2"
  removing b
  created new head
  $ hg update 1
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
  $ rm b
  $ hg update -c 2
  abort: uncommitted changes
  [255]
  $ hg revert b
  $ hg update -c 2
  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
  $ mv a c

Should abort:

  $ hg update 1
  abort: uncommitted changes
  (commit or update --clean to discard changes)
  [255]
  $ mv c a

Should succeed:

  $ hg update 1
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved