view tests/test-filebranch.t @ 15141:16dc9a32ca04

mdiff: speed up showfunc for large diffs

This addresses the following issues with showfunc:

- Silly usage of regular expressions.
- Doing str.rstrip() needlessly in an inner loop.
- Doing catastrophic backtracking when trying to find a function line.

Finding function text is now at worst O(n lines in the old file), and
at best close to O(n hunks).

Given a diff like this[1]:

 src/main/antlr3/uk/ac/cam/ch/wwmm/pregenerated/ChemicalChunker.g        |      4 +-
 src/main/java/uk/ac/cam/ch/wwmm/pregenerated/ChemicalChunkerLexer.java  |      2 +-
 src/main/java/uk/ac/cam/ch/wwmm/pregenerated/ChemicalChunkerParser.java |  29189 +++++----
 3 files changed, 14741 insertions(+), 14454 deletions(-)

[1]: https://bitbucket.org/wwmm/chemicaltagger/changeset/d2bfbaecd4fc/raw

Without this change, hg log --stat --config diff.showfunc=1 takes an
absurdly long time to complete:

   CallCount    Recursive    Total(ms)   Inline(ms) module:lineno(function)
       32813            0     80.3546     40.6086   mercurial.mdiff:160(yieldhunk)
   [phone]            0     25.7227     25.7227   +<method 'match' of '_sre.SRE_Pattern' objects>
   [phone]            0     14.0221     14.0221   +<method 'rstrip' of 'str' objects>
       +1809            0      0.0009      0.0009   +mercurial.mdiff:148(contextend)
       +1809            0      0.0003      0.0003   +<len>
    65062746            0     25.7227     25.7227   <method 'match' of '_sre.SRE_Pattern' objects>
    65062763            0     14.0221     14.0221   <method 'rstrip' of 'str' objects>
         543            0      0.1631      0.1631   <zlib.decompress>
           3            0      0.0505      0.0505   <mercurial.bdiff.blocks>
       31007            0     80.4564      0.0477   mercurial.mdiff:147(_unidiff)
      +32813            0     80.3546     40.6086   +mercurial.mdiff:160(yieldhunk)
          +3            0      0.0505      0.0505   +<mercurial.bdiff.blocks>
       +3618            0      0.0022      0.0022   +mercurial.mdiff:154(contextstart)
       +5427            0      0.0013      0.0013   +<len>
          +3            0      0.0001      0.0000   +re:188(compile)
           1            0     80.8381      0.0322   mercurial.patch:1777(diffstatdata)
     +107499            0      0.0235      0.0235   +<method 'startswith' of 'str' objects>
      +31014            0     80.7820      0.0071   +mercurial.util:1284(iterlines)
          +3            0      0.0000      0.0000   +<method 'search' of '_sre.SRE_Pattern' objects>
          +4            0      0.0000      0.0000   +mercurial.patch:1783(addresult)
          +3            0      0.0000      0.0000   +<method 'group' of '_sre.SRE_Match' objects>
           6            0      0.0444      0.0283   mercurial.mdiff:12(splitnewlines)
          +6            0      0.0160      0.0160   +<method 'split' of 'str' objects>
          32            0      0.0246      0.0246   <method 'update' of '_hashlib.HASH' objects>
          11            0      0.0236      0.0236   <method 'read' of 'file' objects>
Time: real 80.880 secs (user 80.200+0.000 sys 0.380+0.000)

With this change, it's almost as fast as not using showfunc at all:

   CallCount    Recursive    Total(ms)   Inline(ms) module:lineno(function)
         543            0      0.1699      0.1699   <zlib.decompress>
           3            0      0.0501      0.0501   <mercurial.bdiff.blocks>
       32813            0      0.0415      0.0348   mercurial.mdiff:161(yieldhunk)
      +70837            0      0.0058      0.0058   +<method 'isalnum' of 'str' objects>
       +1809            0      0.0006      0.0006   +mercurial.mdiff:148(contextend)
       +1809            0      0.0002      0.0002   +<len>
           1            0      0.4879      0.0310   mercurial.patch:1777(diffstatdata)
     +107499            0      0.0230      0.0230   +<method 'startswith' of 'str' objects>
      +31014            0      0.4335      0.0065   +mercurial.util:1284(iterlines)
          +3            0      0.0000      0.0000   +<method 'search' of '_sre.SRE_Pattern' objects>
          +4            0      0.0000      0.0000   +mercurial.patch:1783(addresult)
          +1            0      0.0004      0.0000   +re:188(compile)
          32            0      0.0293      0.0293   <method 'update' of '_hashlib.HASH' objects>
           6            0      0.0427      0.0279   mercurial.mdiff:12(splitnewlines)
          +6            0      0.0147      0.0147   +<method 'split' of 'str' objects>
       31007            0      0.1169      0.0235   mercurial.mdiff:147(_unidiff)
          +3            0      0.0501      0.0501   +<mercurial.bdiff.blocks>
      +32813            0      0.0415      0.0348   +mercurial.mdiff:161(yieldhunk)
       +3618            0      0.0012      0.0012   +mercurial.mdiff:154(contextstart)
       +5427            0      0.0006      0.0006   +<len>
      107597            0      0.0230      0.0230   <method 'startswith' of 'str' objects>
          16            0      0.0213      0.0213   <mercurial.mpatch.patches>
         194            0      0.0149      0.0149   <method 'split' of 'str' objects>
Time: real 0.530 secs (user 0.450+0.000 sys 0.070+0.000)

This test makes sure that we don't mark a file as merged with its ancestor
when we do a merge.

  $ cat <<EOF > merge
  > import sys, os
  > print "merging for", os.path.basename(sys.argv[1])
  > EOF
  $ HGMERGE="python ../merge"; export HGMERGE

Creating base:

  $ hg init a
  $ cd a
  $ echo 1 > foo
  $ echo 1 > bar
  $ echo 1 > baz
  $ echo 1 > quux
  $ hg add foo bar baz quux
  $ hg commit -m "base"

  $ cd ..
  $ hg clone a b
  updating to branch default
  4 files updated, 0 files merged, 0 files removed, 0 files unresolved

Creating branch a:

  $ cd a
  $ echo 2a > foo
  $ echo 2a > bar
  $ hg commit -m "branch a"

Creating branch b:

  $ cd ..
  $ cd b
  $ echo 2b > foo
  $ echo 2b > baz
  $ hg commit -m "branch b"

We shouldn't have anything but n state here:

  $ hg debugstate --nodates | grep -v "^n"
  [1]

Merging:

  $ hg pull ../a
  pulling from ../a
  searching for changes
  adding changesets
  adding manifests
  adding file changes
  added 1 changesets with 2 changes to 2 files (+1 heads)
  (run 'hg heads' to see heads, 'hg merge' to merge)

  $ hg merge -v
  resolving manifests
  getting bar
  merging foo
  merging for foo
  1 files updated, 1 files merged, 0 files removed, 0 files unresolved
  (branch merge, don't forget to commit)

  $ echo 2m > foo
  $ echo 2b > baz
  $ echo new > quux

We shouldn't have anything but foo in merge state here:

  $ hg debugstate --nodates | grep "^m"
  m 644          3 foo

  $ hg ci -m "merge"

main: we should have a merge here:

  $ hg debugindex --changelog
     rev    offset  length   base linkrev nodeid       p1           p2
       0         0      73      0       0 cdca01651b96 000000000000 000000000000
       1        73      68      1       1 f6718a9cb7f3 cdca01651b96 000000000000
       2       141      68      2       2 bdd988058d16 cdca01651b96 000000000000
       3       209      66      3       3 d8a521142a3c f6718a9cb7f3 bdd988058d16

log should show foo and quux changed:

  $ hg log -v -r tip
  changeset:   3:d8a521142a3c
  tag:         tip
  parent:      1:f6718a9cb7f3
  parent:      2:bdd988058d16
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  files:       foo quux
  description:
  merge
  
  

foo: we should have a merge here:

  $ hg debugindex foo
     rev    offset  length   base linkrev nodeid       p1           p2
       0         0       3      0       0 b8e02f643373 000000000000 000000000000
       1         3       4      1       1 2ffeddde1b65 b8e02f643373 000000000000
       2         7       4      2       2 33d1fb69067a b8e02f643373 000000000000
       3        11       4      3       3 aa27919ee430 2ffeddde1b65 33d1fb69067a

bar: we should not have a merge here:

  $ hg debugindex bar
     rev    offset  length   base linkrev nodeid       p1           p2
       0         0       3      0       0 b8e02f643373 000000000000 000000000000
       1         3       4      1       2 33d1fb69067a b8e02f643373 000000000000

baz: we should not have a merge here:

  $ hg debugindex baz
     rev    offset  length   base linkrev nodeid       p1           p2
       0         0       3      0       0 b8e02f643373 000000000000 000000000000
       1         3       4      1       1 2ffeddde1b65 b8e02f643373 000000000000

quux: we should not have a merge here:

  $ hg debugindex quux
     rev    offset  length   base linkrev nodeid       p1           p2
       0         0       3      0       0 b8e02f643373 000000000000 000000000000
       1         3       5      1       3 6128c0f33108 b8e02f643373 000000000000

Manifest entries should match tips of all files:

  $ hg manifest --debug
  33d1fb69067a0139622a3fa3b7ba1cdb1367972e 644   bar
  2ffeddde1b65b4827f6746174a145474129fa2ce 644   baz
  aa27919ee4303cfd575e1fb932dd64d75aa08be4 644   foo
  6128c0f33108e8cfbb4e0824d13ae48b466d7280 644   quux

Everything should be clean now:

  $ hg status

  $ hg verify
  checking changesets
  checking manifests
  crosschecking files in changesets and manifests
  checking files
  4 files, 4 changesets, 10 total revisions