# Copyright (C) 2007, 2009, 2011 Canonical Ltd
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

"""Tests for bisect_multi."""

from bzrlib.bisect_multi import bisect_multi_bytes
from bzrlib.tests import TestCase


class TestBisectMultiBytes(TestCase):

    def test_lookup_no_keys_no_calls(self):
        calls = []
        def missing_content(location_keys):
            calls.append(location_keys)
            return ((location_key, False) for location_key in location_keys)
        self.assertEqual([],
            list(bisect_multi_bytes(missing_content, 100, [])))
        self.assertEqual([], calls)

    def test_lookup_missing_key_no_content(self):
        """Doing a lookup in a zero-length file still does a single request.

        This makes sense because the bisector cannot tell how long content is
        and its more flexible to only stop when the content object says 'False'
        for a given location, key pair.
        """
        calls = []
        def missing_content(location_keys):
            calls.append(location_keys)
            return ((location_key, False) for location_key in location_keys)
        self.assertEqual([],
            list(bisect_multi_bytes(missing_content, 0, ['foo', 'bar'])))
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)

    def test_lookup_missing_key_before_all_others(self):
        calls = []
        def missing_first_content(location_keys):
            # returns -1 for all keys unless the byte offset is 0 when it
            # returns False
            calls.append(location_keys)
            result = []
            for location_key in location_keys:
                if location_key[0] == 0:
                    result.append((location_key, False))
                else:
                    result.append((location_key, -1))
            return result
        # given a 0 length file, this should terminate with one call.
        self.assertEqual([],
            list(bisect_multi_bytes(missing_first_content, 0, ['foo', 'bar'])))
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
        del calls[:]
        # given a 2 length file, this should make two calls - 1, 0.
        self.assertEqual([],
            list(bisect_multi_bytes(missing_first_content, 2, ['foo', 'bar'])))
        self.assertEqual([
            [(1, 'foo'), (1, 'bar')],
            [(0, 'foo'), (0, 'bar')],
            ], calls)
        del calls[:]
        # given a really long file - 200MB, this should make a series of calls with the
        # gap between adjactent calls dropping by 50% each time. We choose a
        # length which just under a power of two to generate a corner case in
        # bisection - naively using power of two reduction in size can lead to
        # a very long tail in the bisection process. The current users of
        # the bisect_multi_bytes api are not expected to be concerned by this,
        # as the delta gets down to 4K (the minimum we expect to read and
        # parse) within 16 steps even on a 200MB index (which at 4 keys/K is
        # 800 thousand keys, and log2 of 800000 is 19 - so we're doing log2
        # steps in the worst case there.
        self.assertEqual([],
            list(bisect_multi_bytes(
                missing_first_content,268435456 - 1 , ['foo', 'bar'])))
        self.assertEqual([
            [(134217727, 'foo'), (134217727, 'bar')],
            [(67108864, 'foo'), (67108864, 'bar')],
            [(33554433, 'foo'), (33554433, 'bar')],
            [(16777218, 'foo'), (16777218, 'bar')],
            [(8388611, 'foo'), (8388611, 'bar')],
            [(4194308, 'foo'), (4194308, 'bar')],
            [(2097157, 'foo'), (2097157, 'bar')],
            [(1048582, 'foo'), (1048582, 'bar')],
            [(524295, 'foo'), (524295, 'bar')],
            [(262152, 'foo'), (262152, 'bar')],
            [(131081, 'foo'), (131081, 'bar')],
            [(65546, 'foo'), (65546, 'bar')],
            [(32779, 'foo'), (32779, 'bar')],
            [(16396, 'foo'), (16396, 'bar')],
            [(8205, 'foo'), (8205, 'bar')],
            [(4110, 'foo'), (4110, 'bar')],
            [(2063, 'foo'), (2063, 'bar')],
            [(1040, 'foo'), (1040, 'bar')],
            [(529, 'foo'), (529, 'bar')],
            [(274, 'foo'), (274, 'bar')],
            [(147, 'foo'), (147, 'bar')],
            [(84, 'foo'), (84, 'bar')],
            [(53, 'foo'), (53, 'bar')],
            [(38, 'foo'), (38, 'bar')],
            [(31, 'foo'), (31, 'bar')],
            [(28, 'foo'), (28, 'bar')],
            [(27, 'foo'), (27, 'bar')],
            [(26, 'foo'), (26, 'bar')],
            [(25, 'foo'), (25, 'bar')],
            [(24, 'foo'), (24, 'bar')],
            [(23, 'foo'), (23, 'bar')],
            [(22, 'foo'), (22, 'bar')],
            [(21, 'foo'), (21, 'bar')],
            [(20, 'foo'), (20, 'bar')],
            [(19, 'foo'), (19, 'bar')],
            [(18, 'foo'), (18, 'bar')],
            [(17, 'foo'), (17, 'bar')],
            [(16, 'foo'), (16, 'bar')],
            [(15, 'foo'), (15, 'bar')],
            [(14, 'foo'), (14, 'bar')],
            [(13, 'foo'), (13, 'bar')],
            [(12, 'foo'), (12, 'bar')],
            [(11, 'foo'), (11, 'bar')],
            [(10, 'foo'), (10, 'bar')],
            [(9, 'foo'), (9, 'bar')],
            [(8, 'foo'), (8, 'bar')],
            [(7, 'foo'), (7, 'bar')],
            [(6, 'foo'), (6, 'bar')],
            [(5, 'foo'), (5, 'bar')],
            [(4, 'foo'), (4, 'bar')],
            [(3, 'foo'), (3, 'bar')],
            [(2, 'foo'), (2, 'bar')],
            [(1, 'foo'), (1, 'bar')],
            [(0, 'foo'), (0, 'bar')],
            ], calls)

    def test_lookup_missing_key_after_all_others(self):
        calls = []
        end = None
        def missing_last_content(location_keys):
            # returns +1 for all keys unless the byte offset is 'end' when it
            # returns False
            calls.append(location_keys)
            result = []
            for location_key in location_keys:
                if location_key[0] == end:
                    result.append((location_key, False))
                else:
                    result.append((location_key, +1))
            return result
        # given a 0 length file, this should terminate with one call.
        end = 0
        self.assertEqual([],
            list(bisect_multi_bytes(missing_last_content, 0, ['foo', 'bar'])))
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
        del calls[:]
        end = 2
        # given a 3 length file, this should make two calls - 1, 2.
        self.assertEqual([],
            list(bisect_multi_bytes(missing_last_content, 3, ['foo', 'bar'])))
        self.assertEqual([
            [(1, 'foo'), (1, 'bar')],
            [(2, 'foo'), (2, 'bar')],
            ], calls)
        del calls[:]
        end = 268435456 - 2
        # see the really-big lookup series in
        # test_lookup_missing_key_before_all_others for details about this
        # assertion.
        self.assertEqual([],
            list(bisect_multi_bytes(
                missing_last_content,268435456 - 1 , ['foo', 'bar'])))
        self.assertEqual([
            [(134217727, 'foo'), (134217727, 'bar')],
            [(201326590, 'foo'), (201326590, 'bar')],
            [(234881021, 'foo'), (234881021, 'bar')],
            [(251658236, 'foo'), (251658236, 'bar')],
            [(260046843, 'foo'), (260046843, 'bar')],
            [(264241146, 'foo'), (264241146, 'bar')],
            [(266338297, 'foo'), (266338297, 'bar')],
            [(267386872, 'foo'), (267386872, 'bar')],
            [(267911159, 'foo'), (267911159, 'bar')],
            [(268173302, 'foo'), (268173302, 'bar')],
            [(268304373, 'foo'), (268304373, 'bar')],
            [(268369908, 'foo'), (268369908, 'bar')],
            [(268402675, 'foo'), (268402675, 'bar')],
            [(268419058, 'foo'), (268419058, 'bar')],
            [(268427249, 'foo'), (268427249, 'bar')],
            [(268431344, 'foo'), (268431344, 'bar')],
            [(268433391, 'foo'), (268433391, 'bar')],
            [(268434414, 'foo'), (268434414, 'bar')],
            [(268434925, 'foo'), (268434925, 'bar')],
            [(268435180, 'foo'), (268435180, 'bar')],
            [(268435307, 'foo'), (268435307, 'bar')],
            [(268435370, 'foo'), (268435370, 'bar')],
            [(268435401, 'foo'), (268435401, 'bar')],
            [(268435416, 'foo'), (268435416, 'bar')],
            [(268435423, 'foo'), (268435423, 'bar')],
            [(268435426, 'foo'), (268435426, 'bar')],
            [(268435427, 'foo'), (268435427, 'bar')],
            [(268435428, 'foo'), (268435428, 'bar')],
            [(268435429, 'foo'), (268435429, 'bar')],
            [(268435430, 'foo'), (268435430, 'bar')],
            [(268435431, 'foo'), (268435431, 'bar')],
            [(268435432, 'foo'), (268435432, 'bar')],
            [(268435433, 'foo'), (268435433, 'bar')],
            [(268435434, 'foo'), (268435434, 'bar')],
            [(268435435, 'foo'), (268435435, 'bar')],
            [(268435436, 'foo'), (268435436, 'bar')],
            [(268435437, 'foo'), (268435437, 'bar')],
            [(268435438, 'foo'), (268435438, 'bar')],
            [(268435439, 'foo'), (268435439, 'bar')],
            [(268435440, 'foo'), (268435440, 'bar')],
            [(268435441, 'foo'), (268435441, 'bar')],
            [(268435442, 'foo'), (268435442, 'bar')],
            [(268435443, 'foo'), (268435443, 'bar')],
            [(268435444, 'foo'), (268435444, 'bar')],
            [(268435445, 'foo'), (268435445, 'bar')],
            [(268435446, 'foo'), (268435446, 'bar')],
            [(268435447, 'foo'), (268435447, 'bar')],
            [(268435448, 'foo'), (268435448, 'bar')],
            [(268435449, 'foo'), (268435449, 'bar')],
            [(268435450, 'foo'), (268435450, 'bar')],
            [(268435451, 'foo'), (268435451, 'bar')],
            [(268435452, 'foo'), (268435452, 'bar')],
            [(268435453, 'foo'), (268435453, 'bar')],
            [(268435454, 'foo'), (268435454, 'bar')]
            ], calls)

    def test_lookup_when_a_key_is_missing_continues(self):
        calls = []
        def missing_foo_otherwise_missing_first_content(location_keys):
            # returns -1 for all keys unless the byte offset is 0 when it
            # returns False
            calls.append(location_keys)
            result = []
            for location_key in location_keys:
                if location_key[1] == 'foo' or location_key[0] == 0:
                    result.append((location_key, False))
                else:
                    result.append((location_key, -1))
            return result
        # given a 2 length file, this should terminate with two calls, one for
        # both keys, and one for bar only.
        self.assertEqual([],
            list(bisect_multi_bytes(
                missing_foo_otherwise_missing_first_content, 2,
                ['foo', 'bar'])))
        self.assertEqual([
            [(1, 'foo'), (1, 'bar')],
            [(0, 'bar')],
            ], calls)

    def test_found_keys_returned_other_searches_continue(self):
        calls = []
        def find_bar_at_1_foo_missing_at_0(location_keys):
            calls.append(location_keys)
            result = []
            for location_key in location_keys:
                if location_key == (1, 'bar'):
                    result.append((location_key, 'bar-result'))
                elif location_key[0] == 0:
                    result.append((location_key, False))
                else:
                    result.append((location_key, -1))
            return result
        # given a 4 length file, this should terminate with three calls, two for
        # both keys, and one for foo only.
        self.assertEqual([('bar', 'bar-result')],
            list(bisect_multi_bytes(
                find_bar_at_1_foo_missing_at_0, 4,
                ['foo', 'bar'])))
        self.assertEqual([
            [(2, 'foo'), (2, 'bar')],
            [(1, 'foo'), (1, 'bar')],
            [(0, 'foo')],
            ], calls)

    def test_searches_different_keys_in_different_directions(self):
        calls = []
        def missing_bar_at_1_foo_at_3(location_keys):
            calls.append(location_keys)
            result = []
            for location_key in location_keys:
                if location_key[1] == 'bar':
                    if location_key[0] == 1:
                        result.append((location_key, False))
                    else:
                        # search down
                        result.append((location_key, -1))
                elif location_key[1] == 'foo':
                    if location_key[0] == 3:
                        result.append((location_key, False))
                    else:
                        # search up
                        result.append((location_key, +1))
            return result
        # given a 4 length file, this should terminate with two calls.
        self.assertEqual([],
            list(bisect_multi_bytes(
                missing_bar_at_1_foo_at_3, 4,
                ['foo', 'bar'])))
        self.assertEqual([
            [(2, 'foo'), (2, 'bar')],
            [(3, 'foo'), (1, 'bar')],
            ], calls)

    def test_change_direction_in_single_key_search(self):
        # check that we can search down, up, down again -
        # so length 8, goes 4, 6, 5
        calls = []
        def missing_at_5(location_keys):
            calls.append(location_keys)
            result = []
            for location_key in location_keys:
                if location_key[0] == 5:
                    result.append((location_key, False))
                elif location_key[0] > 5:
                    # search down
                    result.append((location_key, -1))
                else:
                    # search up
                    result.append((location_key, +1))
            return result
        # given a 8 length file, this should terminate with three calls.
        self.assertEqual([],
            list(bisect_multi_bytes(
                missing_at_5, 8,
                ['foo', 'bar'])))
        self.assertEqual([
            [(4, 'foo'), (4, 'bar')],
            [(6, 'foo'), (6, 'bar')],
            [(5, 'foo'), (5, 'bar')],
            ], calls)

