/brz/remove-bazaar

# Copyright (C) 2007-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

from .. import (

    errors,

    graph as _mod_graph,

    tests,

    )

from ..revision import NULL_REVISION

from . import TestCaseWithMemoryTransport

# Ancestry 1:

#

#  NULL_REVISION

#       |

#     rev1

#      /\

#  rev2a rev2b

#     |    |

#   rev3  /

#     |  /

#   rev4

ancestry_1 = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'],

              b'rev3': [b'rev2a'], b'rev4': [b'rev3', b'rev2b']}

# Ancestry 2:

#

#  NULL_REVISION

#    /    \

# rev1a  rev1b

#   |

# rev2a

#   |

# rev3a

#   |

# rev4a

ancestry_2 = {b'rev1a': [NULL_REVISION], b'rev2a': [b'rev1a'],

              b'rev1b': [NULL_REVISION], b'rev3a': [b'rev2a'], b'rev4a': [b'rev3a']}

# Criss cross ancestry

#

#     NULL_REVISION

#         |

#        rev1

#        /  \

#    rev2a  rev2b

#       |\  /|

#       |  X |

#       |/  \|

#    rev3a  rev3b

criss_cross = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'],

               b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2a']}

# Criss-cross 2

#

#  NULL_REVISION

#    /   \

# rev1a  rev1b

#   |\   /|

#   | \ / |

#   |  X  |

#   | / \ |

#   |/   \|

# rev2a  rev2b

criss_cross2 = {b'rev1a': [NULL_REVISION], b'rev1b': [NULL_REVISION],

                b'rev2a': [b'rev1a', b'rev1b'], b'rev2b': [b'rev1b', b'rev1a']}

# Mainline:

#

#  NULL_REVISION

#       |

#      rev1

#      /  \

#      | rev2b

#      |  /

#     rev2a

mainline = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1', b'rev2b'],

            b'rev2b': [b'rev1']}

# feature branch:

#

#  NULL_REVISION

#       |

#      rev1

#       |

#     rev2b

#       |

#     rev3b

feature_branch = {b'rev1': [NULL_REVISION],

                  b'rev2b': [b'rev1'], b'rev3b': [b'rev2b']}

# History shortcut

#  NULL_REVISION

#       |

#     rev1------

#     /  \      \

#  rev2a rev2b rev2c

#    |  /   \   /

#  rev3a    rev3b

history_shortcut = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'],

                    b'rev2b': [b'rev1'], b'rev2c': [b'rev1'],

                    b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2c']}

# Extended history shortcut

#  NULL_REVISION

#       |

#       a

#       |\

#       b |

#       | |

#       c |

#       | |

#       d |

#       |\|

#       e f

extended_history_shortcut = {b'a': [NULL_REVISION],

                             b'b': [b'a'],

                             b'c': [b'b'],

                             b'd': [b'c'],

                             b'e': [b'd'],

                             b'f': [b'a', b'd'],

                             }

# Double shortcut

# Both sides will see b'A' first, even though it is actually a decendent of a

# different common revision.

#

#  NULL_REVISION

#       |

#       a

#      /|\

#     / b \

#    /  |  \

#   |   c   |

#   |  / \  |

#   | d   e |

#   |/     \|

#   f       g

double_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'],

                   b'd': [b'c'], b'e': [b'c'], b'f': [b'a', b'd'],

                   b'g': [b'a', b'e']}

# Complex shortcut

# This has a failure mode in that a shortcut will find some nodes in common,

# but the common searcher won't have time to find that one branch is actually

# in common. The extra nodes at the beginning are because we want to avoid

# walking off the graph. Specifically, node G should be considered common, but

# is likely to be seen by M long before the common searcher finds it.

#

# NULL_REVISION

#     |

#     a

#     |

#     b

#     |

#     c

#     |

#     d

#     |\

#     e f

#     | |\

#     | g h

#     |/| |

#     i j |

#     | | |

#     | k |

#     | | |

#     | l |

#     |/|/

#     m n

complex_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],

                    b'e': [b'd'], b'f': [b'd'], b'g': [b'f'], b'h': [b'f'],

                    b'i': [b'e', b'g'], b'j': [b'g'], b'k': [b'j'],

                    b'l': [b'k'], b'm': [b'i', b'l'], b'n': [b'l', b'h']}

# NULL_REVISION

#     |

#     a

#     |

#     b

#     |

#     c

#     |

#     d

#     |\

#     e |

#     | |

#     f |

#     | |

#     g h

#     | |\

#     i | j

#     |\| |

#     | k |

#     | | |

#     | l |

#     | | |

#     | m |

#     | | |

#     | n |

#     | | |

#     | o |

#     | | |

#     | p |

#     | | |

#     | q |

#     | | |

#     | r |

#     | | |

#     | s |

#     | | |

#     |/|/

#     t u

complex_shortcut2 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],

                     b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'd'], b'i': [b'g'],

                     b'j': [b'h'], b'k': [b'h', b'i'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'],

                     b'o': [b'n'], b'p': [b'o'], b'q': [b'p'], b'r': [b'q'], b's': [b'r'],

                     b't': [b'i', b's'], b'u': [b's', b'j'],

                     }

# Graph where different walkers will race to find the common and uncommon

# nodes.

#

# NULL_REVISION

#     |

#     a

#     |

#     b

#     |

#     c

#     |

#     d

#     |\

#     e k

#     | |

#     f-+-p

#     | | |

#     | l |

#     | | |

#     | m |

#     | |\|

#     g n q

#     |\| |

#     h o |

#     |/| |

#     i r |

#     | | |

#     | s |

#     | | |

#     | t |

#     | | |

#     | u |

#     | | |

#     | v |

#     | | |

#     | w |

#     | | |

#     | x |

#     | |\|

#     | y z

#     |/

#     j

#

# x is found to be common right away, but is the start of a long series of

# common commits.

# o is actually common, but the i-j shortcut makes it look like it is actually

# unique to j at first, you have to traverse all of x->o to find it.

# q,m gives the walker from j a common point to stop searching, as does p,f.

# k-n exists so that the second pass still has nodes that are worth searching,

# rather than instantly cancelling the extra walker.

racing_shortcuts = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],

                    b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'g'], b'i': [b'h', b'o'], b'j': [b'i', b'y'],

                    b'k': [b'd'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'], b'o': [b'n', b'g'], b'p': [b'f'],

                    b'q': [b'p', b'm'], b'r': [b'o'], b's': [b'r'], b't': [b's'], b'u': [b't'], b'v': [b'u'],

                    b'w': [b'v'], b'x': [b'w'], b'y': [b'x'], b'z': [b'x', b'q']}

# A graph with multiple nodes unique to one side.

#

# NULL_REVISION

#     |

#     a

#     |

#     b

#     |

#     c

#     |

#     d

#     |\

#     e f

#     |\ \

#     g h i

#     |\ \ \

#     j k l m

#     | |/ x|

#     | n o p

#     | |/  |

#     | q   |

#     | |   |

#     | r   |

#     | |   |

#     | s   |

#     | |   |

#     | t   |

#     | |   |

#     | u   |

#     | |   |

#     | v   |

#     | |   |

#     | w   |

#     | |   |

#     | x   |

#     |/ \ /

#     y   z

#

multiple_interesting_unique = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'],

                               b'd': [b'c'], b'e': [b'd'], b'f': [b'd'], b'g': [b'e'], b'h': [b'e'], b'i': [b'f'],

                               b'j': [b'g'], b'k': [b'g'], b'l': [b'h'], b'm': [b'i'], b'n': [b'k', b'l'],

                               b'o': [b'm'], b'p': [b'm', b'l'], b'q': [b'n', b'o'], b'r': [b'q'], b's': [b'r'],

                               b't': [b's'], b'u': [b't'], b'v': [b'u'], b'w': [b'v'], b'x': [b'w'],

                               b'y': [b'j', b'x'], b'z': [b'x', b'p']}

# Shortcut with extra root

# We have a long history shortcut, and an extra root, which is why we can't

# stop searchers based on seeing NULL_REVISION

#  NULL_REVISION

#       |   |

#       a   |

#       |\  |

#       b | |

#       | | |

#       c | |

#       | | |

#       d | g

#       |\|/

#       e f

shortcut_extra_root = {b'a': [NULL_REVISION],

                       b'b': [b'a'],

                       b'c': [b'b'],

                       b'd': [b'c'],

                       b'e': [b'd'],

                       b'f': [b'a', b'd', b'g'],

                       b'g': [NULL_REVISION],

                       }

#  NULL_REVISION

#       |

#       f

#       |

#       e

#      / \

#     b   d

#     | \ |

#     a   c

boundary = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e'], b'e': [b'f'],

            b'f': [NULL_REVISION]}

# A graph that contains a ghost

#  NULL_REVISION

#       |

#       f

#       |

#       e   g

#      / \ /

#     b   d

#     | \ |

#     a   c

with_ghost = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e', b'g'],

              b'e': [b'f'], b'f': [NULL_REVISION], NULL_REVISION: ()}

# A graph that shows we can shortcut finding revnos when reaching them from the

# side.

#  NULL_REVISION

#       |

#       a

#       |

#       b

#       |

#       c

#       |

#       d

#       |

#       e

#      / \

#     f   g

#     |

#     h

#     |

#     i

with_tail = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], b'e': [b'd'],

             b'f': [b'e'], b'g': [b'e'], b'h': [b'f'], b'i': [b'h']}

class InstrumentedParentsProvider(object):

    def __init__(self, parents_provider):

        self.calls = []

        self._real_parents_provider = parents_provider

        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)

        if get_cached is not None:

            # Only expose the underlying 'get_cached_parent_map' function if

            # the wrapped provider has it.

            self.get_cached_parent_map = self._get_cached_parent_map

    def get_parent_map(self, nodes):

        self.calls.extend(nodes)

        return self._real_parents_provider.get_parent_map(nodes)

    def _get_cached_parent_map(self, nodes):

        self.calls.append(('cached', sorted(nodes)))

        return self._real_parents_provider.get_cached_parent_map(nodes)

class SharedInstrumentedParentsProvider(object):

    def __init__(self, parents_provider, calls, info):

        self.calls = calls

        self.info = info

        self._real_parents_provider = parents_provider

        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)

        if get_cached is not None:

            # Only expose the underlying 'get_cached_parent_map' function if

            # the wrapped provider has it.

            self.get_cached_parent_map = self._get_cached_parent_map

    def get_parent_map(self, nodes):

        self.calls.append((self.info, sorted(nodes)))

        return self._real_parents_provider.get_parent_map(nodes)

    def _get_cached_parent_map(self, nodes):

        self.calls.append((self.info, 'cached', sorted(nodes)))

        return self._real_parents_provider.get_cached_parent_map(nodes)

class TestGraphBase(tests.TestCase):

    def make_graph(self, ancestors):

        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))

    def make_breaking_graph(self, ancestors, break_on):

        """Make a Graph that raises an exception if we hit a node."""

        g = self.make_graph(ancestors)

        orig_parent_map = g.get_parent_map

        def get_parent_map(keys):

            bad_keys = set(keys).intersection(break_on)

            if bad_keys:

                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))

            return orig_parent_map(keys)

        g.get_parent_map = get_parent_map

        return g

class TestGraph(TestCaseWithMemoryTransport):

    def make_graph(self, ancestors):

        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))

    def prepare_memory_tree(self, location):

        tree = self.make_branch_and_memory_tree(location)

        tree.lock_write()

        tree.add('.')

        return tree

    def build_ancestry(self, tree, ancestors):

        """Create an ancestry as specified by a graph dict

        :param tree: A tree to use

        :param ancestors: a dict of {node: [node_parent, ...]}

        """

        pending = [NULL_REVISION]

        descendants = {}

        for descendant, parents in ancestors.items():

            for parent in parents:

                descendants.setdefault(parent, []).append(descendant)

        while len(pending) > 0:

            cur_node = pending.pop()

            for descendant in descendants.get(cur_node, []):

                if tree.branch.repository.has_revision(descendant):

                    continue

                parents = [p for p in ancestors[descendant] if p is not

                           NULL_REVISION]

                if len([p for p in parents if not

                        tree.branch.repository.has_revision(p)]) > 0:

                    continue

                tree.set_parent_ids(parents)

                if len(parents) > 0:

                    left_parent = parents[0]

                else:

                    left_parent = NULL_REVISION

                tree.branch.set_last_revision_info(

                    len(tree.branch._lefthand_history(left_parent)),

                    left_parent)

                tree.commit(descendant, rev_id=descendant)

                pending.append(descendant)

    def test_lca(self):

        """Test finding least common ancestor.

        ancestry_1 should always have a single common ancestor

        """

        graph = self.make_graph(ancestry_1)

        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)

        self.assertEqual({NULL_REVISION},

                         graph.find_lca(NULL_REVISION, NULL_REVISION))

        self.assertEqual({NULL_REVISION},

                         graph.find_lca(NULL_REVISION, b'rev1'))

        self.assertEqual({b'rev1'}, graph.find_lca(b'rev1', b'rev1'))

        self.assertEqual({b'rev1'}, graph.find_lca(b'rev2a', b'rev2b'))

    def test_no_unique_lca(self):

        """Test error when one revision is not in the graph"""

        graph = self.make_graph(ancestry_1)

        self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,

                          b'rev1', b'1rev')

    def test_lca_criss_cross(self):

        """Test least-common-ancestor after a criss-cross merge."""

        graph = self.make_graph(criss_cross)

        self.assertEqual({b'rev2a', b'rev2b'},

                         graph.find_lca(b'rev3a', b'rev3b'))

        self.assertEqual({b'rev2b'},

                         graph.find_lca(b'rev3a', b'rev3b', b'rev2b'))

    def test_lca_shortcut(self):

        """Test least-common ancestor on this history shortcut"""

        graph = self.make_graph(history_shortcut)

        self.assertEqual({b'rev2b'}, graph.find_lca(b'rev3a', b'rev3b'))

    def test_lefthand_distance_smoke(self):

        """A simple does it work test for graph.lefthand_distance(keys)."""

        graph = self.make_graph(history_shortcut)

        distance_graph = graph.find_lefthand_distances([b'rev3b', b'rev2a'])

        self.assertEqual({b'rev2a': 2, b'rev3b': 3}, distance_graph)

    def test_lefthand_distance_ghosts(self):

        """A simple does it work test for graph.lefthand_distance(keys)."""

        nodes = {b'nonghost': [NULL_REVISION], b'toghost': [b'ghost']}

        graph = self.make_graph(nodes)

        distance_graph = graph.find_lefthand_distances(

            [b'nonghost', b'toghost'])

        self.assertEqual({b'nonghost': 1, b'toghost': -1}, distance_graph)

    def test_recursive_unique_lca(self):

        """Test finding a unique least common ancestor.

        ancestry_1 should always have a single common ancestor

        """

        graph = self.make_graph(ancestry_1)

        self.assertEqual(NULL_REVISION,

                         graph.find_unique_lca(NULL_REVISION, NULL_REVISION))

        self.assertEqual(NULL_REVISION,

                         graph.find_unique_lca(NULL_REVISION, b'rev1'))

        self.assertEqual(b'rev1', graph.find_unique_lca(b'rev1', b'rev1'))

        self.assertEqual(b'rev1', graph.find_unique_lca(b'rev2a', b'rev2b'))

        self.assertEqual((b'rev1', 1,),

                         graph.find_unique_lca(b'rev2a', b'rev2b',

                                               count_steps=True))

    def assertRemoveDescendants(self, expected, graph, revisions):

        parents = graph.get_parent_map(revisions)

        self.assertEqual(expected,

                         graph._remove_simple_descendants(revisions, parents))

    def test__remove_simple_descendants(self):

        graph = self.make_graph(ancestry_1)

        self.assertRemoveDescendants({b'rev1'}, graph,

                                     {b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'})

    def test__remove_simple_descendants_disjoint(self):

        graph = self.make_graph(ancestry_1)

        self.assertRemoveDescendants({b'rev1', b'rev3'}, graph,

                                     {b'rev1', b'rev3'})

    def test__remove_simple_descendants_chain(self):

        graph = self.make_graph(ancestry_1)

        self.assertRemoveDescendants({b'rev1'}, graph,

                                     {b'rev1', b'rev2a', b'rev3'})

    def test__remove_simple_descendants_siblings(self):

        graph = self.make_graph(ancestry_1)

        self.assertRemoveDescendants({b'rev2a', b'rev2b'}, graph,

                                     {b'rev2a', b'rev2b', b'rev3'})

    def test_unique_lca_criss_cross(self):

        """Ensure we don't pick non-unique lcas in a criss-cross"""

        graph = self.make_graph(criss_cross)

        self.assertEqual(b'rev1', graph.find_unique_lca(b'rev3a', b'rev3b'))

        lca, steps = graph.find_unique_lca(

            b'rev3a', b'rev3b', count_steps=True)

        self.assertEqual(b'rev1', lca)

        self.assertEqual(2, steps)

    def test_unique_lca_null_revision(self):

        """Ensure we pick NULL_REVISION when necessary"""

        graph = self.make_graph(criss_cross2)

        self.assertEqual(b'rev1b', graph.find_unique_lca(b'rev2a', b'rev1b'))

        self.assertEqual(NULL_REVISION,

                         graph.find_unique_lca(b'rev2a', b'rev2b'))

    def test_unique_lca_null_revision2(self):

        """Ensure we pick NULL_REVISION when necessary"""

        graph = self.make_graph(ancestry_2)

        self.assertEqual(NULL_REVISION,

                         graph.find_unique_lca(b'rev4a', b'rev1b'))

    def test_lca_double_shortcut(self):

        graph = self.make_graph(double_shortcut)

        self.assertEqual(b'c', graph.find_unique_lca(b'f', b'g'))

    def test_common_ancestor_two_repos(self):

        """Ensure we do unique_lca using data from two repos"""

        mainline_tree = self.prepare_memory_tree('mainline')

        self.build_ancestry(mainline_tree, mainline)

        self.addCleanup(mainline_tree.unlock)

        # This is cheating, because the revisions in the graph are actually

        # different revisions, despite having the same revision-id.

        feature_tree = self.prepare_memory_tree('feature')

        self.build_ancestry(feature_tree, feature_branch)

        self.addCleanup(feature_tree.unlock)

        graph = mainline_tree.branch.repository.get_graph(

            feature_tree.branch.repository)

        self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))

    def test_graph_difference(self):

        graph = self.make_graph(ancestry_1)

        self.assertEqual(

            (set(), set()), graph.find_difference(b'rev1', b'rev1'))

        self.assertEqual((set(), {b'rev1'}),