view tests/test-linelog.py @ 43252:32187ae9eeb3

copies: simplify the handling of merges

Instead of stacking copies for both parent on the head, we move copies outside
of the heap into a dedicated dictionary. The two side of merge can we merged
sooner, making the algorithm simpler.

This simplicity reflect in the heap structure and speed up the execution for
copies involving a large amount of merges.

Here are timing for perfpathcopies of multiple revision pairs.
- filelog: timing using filelog (with the introrev condition dropped)
- base:    this series base
- before:  the parent of this changeset
- after:   this changeset

revision: large amount; added files: large amount; rename small amount; c3b14617fbd7 9ba6ab77fd29
filelog: ! wall 3.679613 comb 3.680000 user 3.580000 sys 0.100000 (median of 3)
base:    ! wall 8.884369 comb 8.880000 user 8.850000 sys 0.030000 (median of 3)
before:  ! wall 8.443747 comb 8.420000 user 8.410000 sys 0.010000 (median of 3)
after:   ! wall 4.697917 comb 4.690000 user 4.660000 sys 0.030000 (median of 3)
revision: large amount; added files: small amount; rename small amount; c3b14617fbd7 f650a9b140d2
filelog: ! wall 0.003357 comb 0.010000 user 0.010000 sys 0.000000 (median of 781)
base:    ! wall 12.398524 comb 12.400000 user 12.330000 sys 0.070000 (median of 3)
before:  ! wall 10.852593 comb 10.850000 user 10.800000 sys 0.050000 (median of 3)
after:   ! wall 6.750832 comb 6.750000 user 6.640000 sys 0.110000 (median of 3)
revision: large amount; added files: large amount; rename large amount; 08ea3258278e d9fa043f30c0
filelog: ! wall 2.754687 comb 2.760000 user 2.650000 sys 0.110000 (median of 4)
base:    ! wall 1.423166 comb 1.420000 user 1.400000 sys 0.020000 (median of 8)
before:  ! wall 1.068041 comb 1.060000 user 1.050000 sys 0.010000 (median of 10)
after:   ! wall 1.045916 comb 1.050000 user 1.040000 sys 0.010000 (median of 10)
revision: small amount; added files: large amount; rename large amount; df6f7a526b60 a83dc6a2d56f
filelog: ! wall 1.552293 comb 1.550000 user 1.510000 sys 0.040000 (median of 6
base:    ! wall 0.022662 comb 0.020000 user 0.020000 sys 0.000000 (median of 128)
before:  ! wall 0.021111 comb 0.020000 user 0.020000 sys 0.000000 (median of 139)
after:   ! wall 0.021577 comb 0.020000 user 0.020000 sys 0.000000 (median of 138)
revision: small amount; added files: large amount; rename small amount; 4aa4e1f8e19a 169138063d63
filelog: ! wall 1.500983 comb 1.500000 user 1.420000 sys 0.080000 (median of 7)
base:    ! wall 0.006956 comb 0.010000 user 0.010000 sys 0.000000 (median of 392)
before:  ! wall 0.004356 comb 0.010000 user 0.010000 sys 0.000000 (median of 675)
after:   ! wall 0.004329 comb 0.000000 user 0.000000 sys 0.000000 (median of 682)
revision: small amount; added files: small amount; rename small amount; 4bc173b045a6 964879152e2e
filelog: ! wall 0.011745 comb 0.020000 user 0.020000 sys 0.000000 (median of 250)
base:    ! wall 0.000156 comb 0.000000 user 0.000000 sys 0.000000 (median of 17180)
before:  ! wall 0.000100 comb 0.000000 user 0.000000 sys 0.000000 (median of 26912)
after:   ! wall 0.000105 comb 0.000000 user 0.000000 sys 0.000000 (median of 25689)
revision: medium amount; added files: large amount; rename medium amount; c95f1ced15f2 2c68e87c3efe
filelog: ! wall 3.228230 comb 3.230000 user 3.110000 sys 0.120000 (median of 4)
base:    ! wall 0.997640 comb 1.000000 user 0.980000 sys 0.020000 (median of 10)
before:  ! wall 0.778291 comb 0.780000 user 0.780000 sys 0.000000 (median of 13)
after:   ! wall 0.706594 comb 0.710000 user 0.710000 sys 0.000000 (median of 15)
revision: medium amount; added files: medium amount; rename small amount; d343da0c55a8 d7746d32bf9d
filelog: ! wall 1.052501 comb 1.060000 user 1.040000 sys 0.020000 (median of 10
base:    ! wall 0.214519 comb 0.220000 user 0.220000 sys 0.000000 (median of 45)
before:  ! wall 0.160804 comb 0.160000 user 0.160000 sys 0.000000 (median of 62)
after:   ! wall 0.163736 comb 0.160000 user 0.160000 sys 0.000000 (median of 60)

Differential Revision: https://phab.mercurial-scm.org/D7069

from __future__ import absolute_import, print_function

import difflib
import random
import unittest

from mercurial import linelog

vecratio = 3  # number of replacelines / number of replacelines_vec
maxlinenum = 0xFFFFFF
maxb1 = 0xFFFFFF
maxdeltaa = 10
maxdeltab = 10


def _genedits(seed, endrev):
    lines = []
    random.seed(seed)
    for rev in range(0, endrev):
        n = len(lines)
        a1 = random.randint(0, n)
        a2 = random.randint(a1, min(n, a1 + maxdeltaa))
        b1 = random.randint(0, maxb1)
        b2 = random.randint(b1, b1 + maxdeltab)
        usevec = not bool(random.randint(0, vecratio))
        if usevec:
            blines = [
                (random.randint(0, rev), random.randint(0, maxlinenum))
                for _ in range(b1, b2)
            ]
        else:
            blines = [(rev, bidx) for bidx in range(b1, b2)]
        lines[a1:a2] = blines
        yield lines, rev, a1, a2, b1, b2, blines, usevec


class linelogtests(unittest.TestCase):
    def testlinelogencodedecode(self):
        program = [
            linelog._eof(0, 0),
            linelog._jge(41, 42),
            linelog._jump(0, 43),
            linelog._eof(0, 0),
            linelog._jl(44, 45),
            linelog._line(46, 47),
        ]
        ll = linelog.linelog(program, maxrev=100)
        enc = ll.encode()
        # round-trips okay
        self.assertEqual(linelog.linelog.fromdata(enc)._program, ll._program)
        self.assertEqual(linelog.linelog.fromdata(enc), ll)
        # This encoding matches the encoding used by hg-experimental's
        # linelog file, or is supposed to if it doesn't.
        self.assertEqual(
            enc,
            (
                b'\x00\x00\x01\x90\x00\x00\x00\x06'
                b'\x00\x00\x00\xa4\x00\x00\x00*'
                b'\x00\x00\x00\x00\x00\x00\x00+'
                b'\x00\x00\x00\x00\x00\x00\x00\x00'
                b'\x00\x00\x00\xb1\x00\x00\x00-'
                b'\x00\x00\x00\xba\x00\x00\x00/'
            ),
        )

    def testsimpleedits(self):
        ll = linelog.linelog()
        # Initial revision: add lines 0, 1, and 2
        ll.replacelines(1, 0, 0, 0, 3)
        self.assertEqual(
            [(l.rev, l.linenum) for l in ll.annotate(1)],
            [(1, 0), (1, 1), (1, 2),],
        )
        # Replace line 1 with a new line
        ll.replacelines(2, 1, 2, 1, 2)
        self.assertEqual(
            [(l.rev, l.linenum) for l in ll.annotate(2)],
            [(1, 0), (2, 1), (1, 2),],
        )
        # delete a line out of 2
        ll.replacelines(3, 1, 2, 0, 0)
        self.assertEqual(
            [(l.rev, l.linenum) for l in ll.annotate(3)], [(1, 0), (1, 2),]
        )
        # annotation of 1 is unchanged
        self.assertEqual(
            [(l.rev, l.linenum) for l in ll.annotate(1)],
            [(1, 0), (1, 1), (1, 2),],
        )
        ll.annotate(3)  # set internal state to revision 3
        start = ll.getoffset(0)
        end = ll.getoffset(1)
        self.assertEqual(ll.getalllines(start, end), [(1, 0), (2, 1), (1, 1),])
        self.assertEqual(ll.getalllines(), [(1, 0), (2, 1), (1, 1), (1, 2),])

    def testparseclinelogfile(self):
        # This data is what the replacements in testsimpleedits
        # produce when fed to the original linelog.c implementation.
        data = (
            b'\x00\x00\x00\x0c\x00\x00\x00\x0f'
            b'\x00\x00\x00\x00\x00\x00\x00\x02'
            b'\x00\x00\x00\x05\x00\x00\x00\x06'
            b'\x00\x00\x00\x06\x00\x00\x00\x00'
            b'\x00\x00\x00\x00\x00\x00\x00\x07'
            b'\x00\x00\x00\x06\x00\x00\x00\x02'
            b'\x00\x00\x00\x00\x00\x00\x00\x00'
            b'\x00\x00\x00\t\x00\x00\x00\t'
            b'\x00\x00\x00\x00\x00\x00\x00\x0c'
            b'\x00\x00\x00\x08\x00\x00\x00\x05'
            b'\x00\x00\x00\x06\x00\x00\x00\x01'
            b'\x00\x00\x00\x00\x00\x00\x00\x05'
            b'\x00\x00\x00\x0c\x00\x00\x00\x05'
            b'\x00\x00\x00\n\x00\x00\x00\x01'
            b'\x00\x00\x00\x00\x00\x00\x00\t'
        )
        llc = linelog.linelog.fromdata(data)
        self.assertEqual(
            [(l.rev, l.linenum) for l in llc.annotate(1)],
            [(1, 0), (1, 1), (1, 2),],
        )
        self.assertEqual(
            [(l.rev, l.linenum) for l in llc.annotate(2)],
            [(1, 0), (2, 1), (1, 2),],
        )
        self.assertEqual(
            [(l.rev, l.linenum) for l in llc.annotate(3)], [(1, 0), (1, 2),]
        )
        # Check we emit the same bytecode.
        ll = linelog.linelog()
        # Initial revision: add lines 0, 1, and 2
        ll.replacelines(1, 0, 0, 0, 3)
        # Replace line 1 with a new line
        ll.replacelines(2, 1, 2, 1, 2)
        # delete a line out of 2
        ll.replacelines(3, 1, 2, 0, 0)
        diff = '\n   ' + '\n   '.join(
            difflib.unified_diff(
                ll.debugstr().splitlines(),
                llc.debugstr().splitlines(),
                'python',
                'c',
                lineterm='',
            )
        )
        self.assertEqual(ll._program, llc._program, 'Program mismatch: ' + diff)
        # Done as a secondary step so we get a better result if the
        # program is where the mismatch is.
        self.assertEqual(ll, llc)
        self.assertEqual(ll.encode(), data)

    def testanothersimplecase(self):
        ll = linelog.linelog()
        ll.replacelines(3, 0, 0, 0, 2)
        ll.replacelines(4, 0, 2, 0, 0)
        self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(4)], [])
        self.assertEqual(
            [(l.rev, l.linenum) for l in ll.annotate(3)], [(3, 0), (3, 1)]
        )
        # rev 2 is empty because contents were only ever introduced in rev 3
        self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(2)], [])

    def testrandomedits(self):
        # Inspired by original linelog tests.
        seed = random.random()
        numrevs = 2000
        ll = linelog.linelog()
        # Populate linelog
        for lines, rev, a1, a2, b1, b2, blines, usevec in _genedits(
            seed, numrevs
        ):
            if usevec:
                ll.replacelines_vec(rev, a1, a2, blines)
            else:
                ll.replacelines(rev, a1, a2, b1, b2)
            ar = ll.annotate(rev)
            self.assertEqual(ll.annotateresult, lines)
        # Verify we can get back these states by annotating each rev
        for lines, rev, a1, a2, b1, b2, blines, usevec in _genedits(
            seed, numrevs
        ):
            ar = ll.annotate(rev)
            self.assertEqual([(l.rev, l.linenum) for l in ar], lines)

    def testinfinitebadprogram(self):
        ll = linelog.linelog.fromdata(
            b'\x00\x00\x00\x00\x00\x00\x00\x02'  # header
            b'\x00\x00\x00\x00\x00\x00\x00\x01'  # JUMP to self
        )
        with self.assertRaises(linelog.LineLogError):
            # should not be an infinite loop and raise
            ll.annotate(1)


if __name__ == '__main__':
    import silenttestrunner

    silenttestrunner.main(__name__)