1# Copyright (C) 2007-2011 Canonical Ltd 2# 3# This program is free software; you can redistribute it and/or modify 4# it under the terms of the GNU General Public License as published by 5# the Free Software Foundation; either version 2 of the License, or 6# (at your option) any later version. 7# 8# This program is distributed in the hope that it will be useful, 9# but WITHOUT ANY WARRANTY; without even the implied warranty of 10# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11# GNU General Public License for more details. 12# 13# You should have received a copy of the GNU General Public License 14# along with this program; if not, write to the Free Software 15# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 16 17from .. import ( 18 errors, 19 graph as _mod_graph, 20 tests, 21 ) 22from ..revision import NULL_REVISION 23from . import TestCaseWithMemoryTransport 24 25 26# Ancestry 1: 27# 28# NULL_REVISION 29# | 30# rev1 31# /\ 32# rev2a rev2b 33# | | 34# rev3 / 35# | / 36# rev4 37ancestry_1 = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'], 38 b'rev3': [b'rev2a'], b'rev4': [b'rev3', b'rev2b']} 39 40 41# Ancestry 2: 42# 43# NULL_REVISION 44# / \ 45# rev1a rev1b 46# | 47# rev2a 48# | 49# rev3a 50# | 51# rev4a 52ancestry_2 = {b'rev1a': [NULL_REVISION], b'rev2a': [b'rev1a'], 53 b'rev1b': [NULL_REVISION], b'rev3a': [b'rev2a'], b'rev4a': [b'rev3a']} 54 55 56# Criss cross ancestry 57# 58# NULL_REVISION 59# | 60# rev1 61# / \ 62# rev2a rev2b 63# |\ /| 64# | X | 65# |/ \| 66# rev3a rev3b 67criss_cross = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'], 68 b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2a']} 69 70 71# Criss-cross 2 72# 73# NULL_REVISION 74# / \ 75# rev1a rev1b 76# |\ /| 77# | \ / | 78# | X | 79# | / \ | 80# |/ \| 81# rev2a rev2b 82criss_cross2 = {b'rev1a': [NULL_REVISION], b'rev1b': [NULL_REVISION], 83 b'rev2a': [b'rev1a', b'rev1b'], b'rev2b': [b'rev1b', b'rev1a']} 84 85 86# Mainline: 87# 88# NULL_REVISION 89# | 90# rev1 91# / \ 92# | rev2b 93# | / 94# rev2a 95mainline = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1', b'rev2b'], 96 b'rev2b': [b'rev1']} 97 98 99# feature branch: 100# 101# NULL_REVISION 102# | 103# rev1 104# | 105# rev2b 106# | 107# rev3b 108feature_branch = {b'rev1': [NULL_REVISION], 109 b'rev2b': [b'rev1'], b'rev3b': [b'rev2b']} 110 111 112# History shortcut 113# NULL_REVISION 114# | 115# rev1------ 116# / \ \ 117# rev2a rev2b rev2c 118# | / \ / 119# rev3a rev3b 120history_shortcut = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], 121 b'rev2b': [b'rev1'], b'rev2c': [b'rev1'], 122 b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2c']} 123 124# Extended history shortcut 125# NULL_REVISION 126# | 127# a 128# |\ 129# b | 130# | | 131# c | 132# | | 133# d | 134# |\| 135# e f 136extended_history_shortcut = {b'a': [NULL_REVISION], 137 b'b': [b'a'], 138 b'c': [b'b'], 139 b'd': [b'c'], 140 b'e': [b'd'], 141 b'f': [b'a', b'd'], 142 } 143 144# Double shortcut 145# Both sides will see b'A' first, even though it is actually a decendent of a 146# different common revision. 147# 148# NULL_REVISION 149# | 150# a 151# /|\ 152# / b \ 153# / | \ 154# | c | 155# | / \ | 156# | d e | 157# |/ \| 158# f g 159 160double_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], 161 b'd': [b'c'], b'e': [b'c'], b'f': [b'a', b'd'], 162 b'g': [b'a', b'e']} 163 164# Complex shortcut 165# This has a failure mode in that a shortcut will find some nodes in common, 166# but the common searcher won't have time to find that one branch is actually 167# in common. The extra nodes at the beginning are because we want to avoid 168# walking off the graph. Specifically, node G should be considered common, but 169# is likely to be seen by M long before the common searcher finds it. 170# 171# NULL_REVISION 172# | 173# a 174# | 175# b 176# | 177# c 178# | 179# d 180# |\ 181# e f 182# | |\ 183# | g h 184# |/| | 185# i j | 186# | | | 187# | k | 188# | | | 189# | l | 190# |/|/ 191# m n 192complex_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], 193 b'e': [b'd'], b'f': [b'd'], b'g': [b'f'], b'h': [b'f'], 194 b'i': [b'e', b'g'], b'j': [b'g'], b'k': [b'j'], 195 b'l': [b'k'], b'm': [b'i', b'l'], b'n': [b'l', b'h']} 196 197# NULL_REVISION 198# | 199# a 200# | 201# b 202# | 203# c 204# | 205# d 206# |\ 207# e | 208# | | 209# f | 210# | | 211# g h 212# | |\ 213# i | j 214# |\| | 215# | k | 216# | | | 217# | l | 218# | | | 219# | m | 220# | | | 221# | n | 222# | | | 223# | o | 224# | | | 225# | p | 226# | | | 227# | q | 228# | | | 229# | r | 230# | | | 231# | s | 232# | | | 233# |/|/ 234# t u 235complex_shortcut2 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], 236 b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'd'], b'i': [b'g'], 237 b'j': [b'h'], b'k': [b'h', b'i'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'], 238 b'o': [b'n'], b'p': [b'o'], b'q': [b'p'], b'r': [b'q'], b's': [b'r'], 239 b't': [b'i', b's'], b'u': [b's', b'j'], 240 } 241 242# Graph where different walkers will race to find the common and uncommon 243# nodes. 244# 245# NULL_REVISION 246# | 247# a 248# | 249# b 250# | 251# c 252# | 253# d 254# |\ 255# e k 256# | | 257# f-+-p 258# | | | 259# | l | 260# | | | 261# | m | 262# | |\| 263# g n q 264# |\| | 265# h o | 266# |/| | 267# i r | 268# | | | 269# | s | 270# | | | 271# | t | 272# | | | 273# | u | 274# | | | 275# | v | 276# | | | 277# | w | 278# | | | 279# | x | 280# | |\| 281# | y z 282# |/ 283# j 284# 285# x is found to be common right away, but is the start of a long series of 286# common commits. 287# o is actually common, but the i-j shortcut makes it look like it is actually 288# unique to j at first, you have to traverse all of x->o to find it. 289# q,m gives the walker from j a common point to stop searching, as does p,f. 290# k-n exists so that the second pass still has nodes that are worth searching, 291# rather than instantly cancelling the extra walker. 292 293racing_shortcuts = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], 294 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'], 295 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'], 296 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'], 297 b'w': [b'v'], b'x': [b'w'], b'y': [b'x'], b'z': [b'x', b'q']} 298 299 300# A graph with multiple nodes unique to one side. 301# 302# NULL_REVISION 303# | 304# a 305# | 306# b 307# | 308# c 309# | 310# d 311# |\ 312# e f 313# |\ \ 314# g h i 315# |\ \ \ 316# j k l m 317# | |/ x| 318# | n o p 319# | |/ | 320# | q | 321# | | | 322# | r | 323# | | | 324# | s | 325# | | | 326# | t | 327# | | | 328# | u | 329# | | | 330# | v | 331# | | | 332# | w | 333# | | | 334# | x | 335# |/ \ / 336# y z 337# 338 339multiple_interesting_unique = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], 340 b'd': [b'c'], b'e': [b'd'], b'f': [b'd'], b'g': [b'e'], b'h': [b'e'], b'i': [b'f'], 341 b'j': [b'g'], b'k': [b'g'], b'l': [b'h'], b'm': [b'i'], b'n': [b'k', b'l'], 342 b'o': [b'm'], b'p': [b'm', b'l'], b'q': [b'n', b'o'], b'r': [b'q'], b's': [b'r'], 343 b't': [b's'], b'u': [b't'], b'v': [b'u'], b'w': [b'v'], b'x': [b'w'], 344 b'y': [b'j', b'x'], b'z': [b'x', b'p']} 345 346 347# Shortcut with extra root 348# We have a long history shortcut, and an extra root, which is why we can't 349# stop searchers based on seeing NULL_REVISION 350# NULL_REVISION 351# | | 352# a | 353# |\ | 354# b | | 355# | | | 356# c | | 357# | | | 358# d | g 359# |\|/ 360# e f 361shortcut_extra_root = {b'a': [NULL_REVISION], 362 b'b': [b'a'], 363 b'c': [b'b'], 364 b'd': [b'c'], 365 b'e': [b'd'], 366 b'f': [b'a', b'd', b'g'], 367 b'g': [NULL_REVISION], 368 } 369 370# NULL_REVISION 371# | 372# f 373# | 374# e 375# / \ 376# b d 377# | \ | 378# a c 379 380boundary = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e'], b'e': [b'f'], 381 b'f': [NULL_REVISION]} 382 383 384# A graph that contains a ghost 385# NULL_REVISION 386# | 387# f 388# | 389# e g 390# / \ / 391# b d 392# | \ | 393# a c 394 395with_ghost = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e', b'g'], 396 b'e': [b'f'], b'f': [NULL_REVISION], NULL_REVISION: ()} 397 398# A graph that shows we can shortcut finding revnos when reaching them from the 399# side. 400# NULL_REVISION 401# | 402# a 403# | 404# b 405# | 406# c 407# | 408# d 409# | 410# e 411# / \ 412# f g 413# | 414# h 415# | 416# i 417 418with_tail = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], b'e': [b'd'], 419 b'f': [b'e'], b'g': [b'e'], b'h': [b'f'], b'i': [b'h']} 420 421 422class InstrumentedParentsProvider(object): 423 424 def __init__(self, parents_provider): 425 self.calls = [] 426 self._real_parents_provider = parents_provider 427 get_cached = getattr(parents_provider, 'get_cached_parent_map', None) 428 if get_cached is not None: 429 # Only expose the underlying 'get_cached_parent_map' function if 430 # the wrapped provider has it. 431 self.get_cached_parent_map = self._get_cached_parent_map 432 433 def get_parent_map(self, nodes): 434 self.calls.extend(nodes) 435 return self._real_parents_provider.get_parent_map(nodes) 436 437 def _get_cached_parent_map(self, nodes): 438 self.calls.append(('cached', sorted(nodes))) 439 return self._real_parents_provider.get_cached_parent_map(nodes) 440 441 442class SharedInstrumentedParentsProvider(object): 443 444 def __init__(self, parents_provider, calls, info): 445 self.calls = calls 446 self.info = info 447 self._real_parents_provider = parents_provider 448 get_cached = getattr(parents_provider, 'get_cached_parent_map', None) 449 if get_cached is not None: 450 # Only expose the underlying 'get_cached_parent_map' function if 451 # the wrapped provider has it. 452 self.get_cached_parent_map = self._get_cached_parent_map 453 454 def get_parent_map(self, nodes): 455 self.calls.append((self.info, sorted(nodes))) 456 return self._real_parents_provider.get_parent_map(nodes) 457 458 def _get_cached_parent_map(self, nodes): 459 self.calls.append((self.info, 'cached', sorted(nodes))) 460 return self._real_parents_provider.get_cached_parent_map(nodes) 461 462 463class TestGraphBase(tests.TestCase): 464 465 def make_graph(self, ancestors): 466 return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors)) 467 468 def make_breaking_graph(self, ancestors, break_on): 469 """Make a Graph that raises an exception if we hit a node.""" 470 g = self.make_graph(ancestors) 471 orig_parent_map = g.get_parent_map 472 473 def get_parent_map(keys): 474 bad_keys = set(keys).intersection(break_on) 475 if bad_keys: 476 self.fail('key(s) %s was accessed' % (sorted(bad_keys),)) 477 return orig_parent_map(keys) 478 g.get_parent_map = get_parent_map 479 return g 480 481 482class TestGraph(TestCaseWithMemoryTransport): 483 484 def make_graph(self, ancestors): 485 return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors)) 486 487 def prepare_memory_tree(self, location): 488 tree = self.make_branch_and_memory_tree(location) 489 tree.lock_write() 490 tree.add('.') 491 return tree 492 493 def build_ancestry(self, tree, ancestors): 494 """Create an ancestry as specified by a graph dict 495 496 :param tree: A tree to use 497 :param ancestors: a dict of {node: [node_parent, ...]} 498 """ 499 pending = [NULL_REVISION] 500 descendants = {} 501 for descendant, parents in ancestors.items(): 502 for parent in parents: 503 descendants.setdefault(parent, []).append(descendant) 504 while len(pending) > 0: 505 cur_node = pending.pop() 506 for descendant in descendants.get(cur_node, []): 507 if tree.branch.repository.has_revision(descendant): 508 continue 509 parents = [p for p in ancestors[descendant] if p is not 510 NULL_REVISION] 511 if len([p for p in parents if not 512 tree.branch.repository.has_revision(p)]) > 0: 513 continue 514 tree.set_parent_ids(parents) 515 if len(parents) > 0: 516 left_parent = parents[0] 517 else: 518 left_parent = NULL_REVISION 519 tree.branch.set_last_revision_info( 520 len(tree.branch._lefthand_history(left_parent)), 521 left_parent) 522 tree.commit(descendant, rev_id=descendant) 523 pending.append(descendant) 524 525 def test_lca(self): 526 """Test finding least common ancestor. 527 528 ancestry_1 should always have a single common ancestor 529 """ 530 graph = self.make_graph(ancestry_1) 531 self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None) 532 self.assertEqual({NULL_REVISION}, 533 graph.find_lca(NULL_REVISION, NULL_REVISION)) 534 self.assertEqual({NULL_REVISION}, 535 graph.find_lca(NULL_REVISION, b'rev1')) 536 self.assertEqual({b'rev1'}, graph.find_lca(b'rev1', b'rev1')) 537 self.assertEqual({b'rev1'}, graph.find_lca(b'rev2a', b'rev2b')) 538 539 def test_no_unique_lca(self): 540 """Test error when one revision is not in the graph""" 541 graph = self.make_graph(ancestry_1) 542 self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca, 543 b'rev1', b'1rev') 544 545 def test_lca_criss_cross(self): 546 """Test least-common-ancestor after a criss-cross merge.""" 547 graph = self.make_graph(criss_cross) 548 self.assertEqual({b'rev2a', b'rev2b'}, 549 graph.find_lca(b'rev3a', b'rev3b')) 550 self.assertEqual({b'rev2b'}, 551 graph.find_lca(b'rev3a', b'rev3b', b'rev2b')) 552 553 def test_lca_shortcut(self): 554 """Test least-common ancestor on this history shortcut""" 555 graph = self.make_graph(history_shortcut) 556 self.assertEqual({b'rev2b'}, graph.find_lca(b'rev3a', b'rev3b')) 557 558 def test_lefthand_distance_smoke(self): 559 """A simple does it work test for graph.lefthand_distance(keys).""" 560 graph = self.make_graph(history_shortcut) 561 distance_graph = graph.find_lefthand_distances([b'rev3b', b'rev2a']) 562 self.assertEqual({b'rev2a': 2, b'rev3b': 3}, distance_graph) 563 564 def test_lefthand_distance_ghosts(self): 565 """A simple does it work test for graph.lefthand_distance(keys).""" 566 nodes = {b'nonghost': [NULL_REVISION], b'toghost': [b'ghost']} 567 graph = self.make_graph(nodes) 568 distance_graph = graph.find_lefthand_distances( 569 [b'nonghost', b'toghost']) 570 self.assertEqual({b'nonghost': 1, b'toghost': -1}, distance_graph) 571 572 def test_recursive_unique_lca(self): 573 """Test finding a unique least common ancestor. 574 575 ancestry_1 should always have a single common ancestor 576 """ 577 graph = self.make_graph(ancestry_1) 578 self.assertEqual(NULL_REVISION, 579 graph.find_unique_lca(NULL_REVISION, NULL_REVISION)) 580 self.assertEqual(NULL_REVISION, 581 graph.find_unique_lca(NULL_REVISION, b'rev1')) 582 self.assertEqual(b'rev1', graph.find_unique_lca(b'rev1', b'rev1')) 583 self.assertEqual(b'rev1', graph.find_unique_lca(b'rev2a', b'rev2b')) 584 self.assertEqual((b'rev1', 1,), 585 graph.find_unique_lca(b'rev2a', b'rev2b', 586 count_steps=True)) 587 588 def assertRemoveDescendants(self, expected, graph, revisions): 589 parents = graph.get_parent_map(revisions) 590 self.assertEqual(expected, 591 graph._remove_simple_descendants(revisions, parents)) 592 593 def test__remove_simple_descendants(self): 594 graph = self.make_graph(ancestry_1) 595 self.assertRemoveDescendants({b'rev1'}, graph, 596 {b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'}) 597 598 def test__remove_simple_descendants_disjoint(self): 599 graph = self.make_graph(ancestry_1) 600 self.assertRemoveDescendants({b'rev1', b'rev3'}, graph, 601 {b'rev1', b'rev3'}) 602 603 def test__remove_simple_descendants_chain(self): 604 graph = self.make_graph(ancestry_1) 605 self.assertRemoveDescendants({b'rev1'}, graph, 606 {b'rev1', b'rev2a', b'rev3'}) 607 608 def test__remove_simple_descendants_siblings(self): 609 graph = self.make_graph(ancestry_1) 610 self.assertRemoveDescendants({b'rev2a', b'rev2b'}, graph, 611 {b'rev2a', b'rev2b', b'rev3'}) 612 613 def test_unique_lca_criss_cross(self): 614 """Ensure we don't pick non-unique lcas in a criss-cross""" 615 graph = self.make_graph(criss_cross) 616 self.assertEqual(b'rev1', graph.find_unique_lca(b'rev3a', b'rev3b')) 617 lca, steps = graph.find_unique_lca( 618 b'rev3a', b'rev3b', count_steps=True) 619 self.assertEqual(b'rev1', lca) 620 self.assertEqual(2, steps) 621 622 def test_unique_lca_null_revision(self): 623 """Ensure we pick NULL_REVISION when necessary""" 624 graph = self.make_graph(criss_cross2) 625 self.assertEqual(b'rev1b', graph.find_unique_lca(b'rev2a', b'rev1b')) 626 self.assertEqual(NULL_REVISION, 627 graph.find_unique_lca(b'rev2a', b'rev2b')) 628 629 def test_unique_lca_null_revision2(self): 630 """Ensure we pick NULL_REVISION when necessary""" 631 graph = self.make_graph(ancestry_2) 632 self.assertEqual(NULL_REVISION, 633 graph.find_unique_lca(b'rev4a', b'rev1b')) 634 635 def test_lca_double_shortcut(self): 636 graph = self.make_graph(double_shortcut) 637 self.assertEqual(b'c', graph.find_unique_lca(b'f', b'g')) 638 639 def test_common_ancestor_two_repos(self): 640 """Ensure we do unique_lca using data from two repos""" 641 mainline_tree = self.prepare_memory_tree('mainline') 642 self.build_ancestry(mainline_tree, mainline) 643 self.addCleanup(mainline_tree.unlock) 644 645 # This is cheating, because the revisions in the graph are actually 646 # different revisions, despite having the same revision-id. 647 feature_tree = self.prepare_memory_tree('feature') 648 self.build_ancestry(feature_tree, feature_branch) 649 self.addCleanup(feature_tree.unlock) 650 651 graph = mainline_tree.branch.repository.get_graph( 652 feature_tree.branch.repository) 653 self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b')) 654 655 def test_graph_difference(self): 656 graph = self.make_graph(ancestry_1) 657 self.assertEqual( 658 (set(), set()), graph.find_difference(b'rev1', b'rev1')) 659 self.assertEqual((set(), {b'rev1'}), 660 graph.find_difference(NULL_REVISION, b'rev1')) 661 self.assertEqual(({b'rev1'}, set()), 662 graph.find_difference(b'rev1', NULL_REVISION)) 663 self.assertEqual(({b'rev2a', b'rev3'}, {b'rev2b'}), 664 graph.find_difference(b'rev3', b'rev2b')) 665 self.assertEqual(({b'rev4', b'rev3', b'rev2a'}, set()), 666 graph.find_difference(b'rev4', b'rev2b')) 667 668 def test_graph_difference_separate_ancestry(self): 669 graph = self.make_graph(ancestry_2) 670 self.assertEqual(({b'rev1a'}, {b'rev1b'}), 671 graph.find_difference(b'rev1a', b'rev1b')) 672 self.assertEqual(({b'rev1a', b'rev2a', b'rev3a', b'rev4a'}, 673 {b'rev1b'}), 674 graph.find_difference(b'rev4a', b'rev1b')) 675 676 def test_graph_difference_criss_cross(self): 677 graph = self.make_graph(criss_cross) 678 self.assertEqual(({b'rev3a'}, {b'rev3b'}), 679 graph.find_difference(b'rev3a', b'rev3b')) 680 self.assertEqual((set([]), {b'rev3b', b'rev2b'}), 681 graph.find_difference(b'rev2a', b'rev3b')) 682 683 def test_graph_difference_extended_history(self): 684 graph = self.make_graph(extended_history_shortcut) 685 self.assertEqual(({b'e'}, {b'f'}), 686 graph.find_difference(b'e', b'f')) 687 self.assertEqual(({b'f'}, {b'e'}), 688 graph.find_difference(b'f', b'e')) 689 690 def test_graph_difference_double_shortcut(self): 691 graph = self.make_graph(double_shortcut) 692 self.assertEqual(({b'd', b'f'}, {b'e', b'g'}), 693 graph.find_difference(b'f', b'g')) 694 695 def test_graph_difference_complex_shortcut(self): 696 graph = self.make_graph(complex_shortcut) 697 self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}), 698 graph.find_difference(b'm', b'n')) 699 700 def test_graph_difference_complex_shortcut2(self): 701 graph = self.make_graph(complex_shortcut2) 702 self.assertEqual(({b't'}, {b'j', b'u'}), 703 graph.find_difference(b't', b'u')) 704 705 def test_graph_difference_shortcut_extra_root(self): 706 graph = self.make_graph(shortcut_extra_root) 707 self.assertEqual(({b'e'}, {b'f', b'g'}), 708 graph.find_difference(b'e', b'f')) 709 710 def test_iter_topo_order(self): 711 graph = self.make_graph(ancestry_1) 712 args = [b'rev2a', b'rev3', b'rev1'] 713 topo_args = list(graph.iter_topo_order(args)) 714 self.assertEqual(set(args), set(topo_args)) 715 self.assertTrue(topo_args.index(b'rev2a') > topo_args.index(b'rev1')) 716 self.assertTrue(topo_args.index(b'rev2a') < topo_args.index(b'rev3')) 717 718 def test_is_ancestor(self): 719 graph = self.make_graph(ancestry_1) 720 self.assertEqual(True, graph.is_ancestor(b'null:', b'null:')) 721 self.assertEqual(True, graph.is_ancestor(b'null:', b'rev1')) 722 self.assertEqual(False, graph.is_ancestor(b'rev1', b'null:')) 723 self.assertEqual(True, graph.is_ancestor(b'null:', b'rev4')) 724 self.assertEqual(False, graph.is_ancestor(b'rev4', b'null:')) 725 self.assertEqual(False, graph.is_ancestor(b'rev4', b'rev2b')) 726 self.assertEqual(True, graph.is_ancestor(b'rev2b', b'rev4')) 727 self.assertEqual(False, graph.is_ancestor(b'rev2b', b'rev3')) 728 self.assertEqual(False, graph.is_ancestor(b'rev3', b'rev2b')) 729 instrumented_provider = InstrumentedParentsProvider(graph) 730 instrumented_graph = _mod_graph.Graph(instrumented_provider) 731 instrumented_graph.is_ancestor(b'rev2a', b'rev2b') 732 self.assertTrue(b'null:' not in instrumented_provider.calls) 733 734 def test_is_between(self): 735 graph = self.make_graph(ancestry_1) 736 self.assertEqual(True, graph.is_between(b'null:', b'null:', b'null:')) 737 self.assertEqual(True, graph.is_between(b'rev1', b'null:', b'rev1')) 738 self.assertEqual(True, graph.is_between(b'rev1', b'rev1', b'rev4')) 739 self.assertEqual(True, graph.is_between(b'rev4', b'rev1', b'rev4')) 740 self.assertEqual(True, graph.is_between(b'rev3', b'rev1', b'rev4')) 741 self.assertEqual(False, graph.is_between(b'rev4', b'rev1', b'rev3')) 742 self.assertEqual(False, graph.is_between(b'rev1', b'rev2a', b'rev4')) 743 self.assertEqual(False, graph.is_between(b'null:', b'rev1', b'rev4')) 744 745 def test_is_ancestor_boundary(self): 746 """Ensure that we avoid searching the whole graph. 747 748 This requires searching through b as a common ancestor, so we 749 can identify that e is common. 750 """ 751 graph = self.make_graph(boundary) 752 instrumented_provider = InstrumentedParentsProvider(graph) 753 graph = _mod_graph.Graph(instrumented_provider) 754 self.assertFalse(graph.is_ancestor(b'a', b'c')) 755 self.assertTrue(b'null:' not in instrumented_provider.calls) 756 757 def test_iter_ancestry(self): 758 nodes = boundary.copy() 759 nodes[NULL_REVISION] = () 760 graph = self.make_graph(nodes) 761 expected = nodes.copy() 762 expected.pop(b'a') # b'a' is not in the ancestry of b'c', all the 763 # other nodes are 764 self.assertEqual(expected, dict(graph.iter_ancestry([b'c']))) 765 self.assertEqual(nodes, dict(graph.iter_ancestry([b'a', b'c']))) 766 767 def test_iter_ancestry_with_ghost(self): 768 graph = self.make_graph(with_ghost) 769 expected = with_ghost.copy() 770 # b'a' is not in the ancestry of b'c', and b'g' is a ghost 771 expected[b'g'] = None 772 self.assertEqual(expected, dict(graph.iter_ancestry([b'a', b'c']))) 773 expected.pop(b'a') 774 self.assertEqual(expected, dict(graph.iter_ancestry([b'c']))) 775 776 def test_filter_candidate_lca(self): 777 """Test filter_candidate_lca for a corner case 778 779 This tests the case where we encounter the end of iteration for b'e' 780 in the same pass as we discover that b'd' is an ancestor of b'e', and 781 therefore b'e' can't be an lca. 782 783 To compensate for different dict orderings on other Python 784 implementations, we mirror b'd' and b'e' with b'b' and b'a'. 785 """ 786 # This test is sensitive to the iteration order of dicts. It will 787 # pass incorrectly if b'e' and b'a' sort before b'c' 788 # 789 # NULL_REVISION 790 # / \ 791 # a e 792 # | | 793 # b d 794 # \ / 795 # c 796 graph = self.make_graph({b'c': [b'b', b'd'], b'd': [b'e'], b'b': [b'a'], 797 b'a': [NULL_REVISION], b'e': [NULL_REVISION]}) 798 self.assertEqual({b'c'}, graph.heads([b'a', b'c', b'e'])) 799 800 def test_heads_null(self): 801 graph = self.make_graph(ancestry_1) 802 self.assertEqual({b'null:'}, graph.heads([b'null:'])) 803 self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1'])) 804 self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:'])) 805 self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'})) 806 self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:'))) 807 808 def test_heads_one(self): 809 # A single node will always be a head 810 graph = self.make_graph(ancestry_1) 811 self.assertEqual({b'null:'}, graph.heads([b'null:'])) 812 self.assertEqual({b'rev1'}, graph.heads([b'rev1'])) 813 self.assertEqual({b'rev2a'}, graph.heads([b'rev2a'])) 814 self.assertEqual({b'rev2b'}, graph.heads([b'rev2b'])) 815 self.assertEqual({b'rev3'}, graph.heads([b'rev3'])) 816 self.assertEqual({b'rev4'}, graph.heads([b'rev4'])) 817 818 def test_heads_single(self): 819 graph = self.make_graph(ancestry_1) 820 self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4'])) 821 self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a'])) 822 self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b'])) 823 self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3'])) 824 self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4'])) 825 self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4'])) 826 self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4'])) 827 self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4'])) 828 829 def test_heads_two_heads(self): 830 graph = self.make_graph(ancestry_1) 831 self.assertEqual({b'rev2a', b'rev2b'}, 832 graph.heads([b'rev2a', b'rev2b'])) 833 self.assertEqual({b'rev3', b'rev2b'}, 834 graph.heads([b'rev3', b'rev2b'])) 835 836 def test_heads_criss_cross(self): 837 graph = self.make_graph(criss_cross) 838 self.assertEqual({b'rev2a'}, 839 graph.heads([b'rev2a', b'rev1'])) 840 self.assertEqual({b'rev2b'}, 841 graph.heads([b'rev2b', b'rev1'])) 842 self.assertEqual({b'rev3a'}, 843 graph.heads([b'rev3a', b'rev1'])) 844 self.assertEqual({b'rev3b'}, 845 graph.heads([b'rev3b', b'rev1'])) 846 self.assertEqual({b'rev2a', b'rev2b'}, 847 graph.heads([b'rev2a', b'rev2b'])) 848 self.assertEqual({b'rev3a'}, 849 graph.heads([b'rev3a', b'rev2a'])) 850 self.assertEqual({b'rev3a'}, 851 graph.heads([b'rev3a', b'rev2b'])) 852 self.assertEqual({b'rev3a'}, 853 graph.heads([b'rev3a', b'rev2a', b'rev2b'])) 854 self.assertEqual({b'rev3b'}, 855 graph.heads([b'rev3b', b'rev2a'])) 856 self.assertEqual({b'rev3b'}, 857 graph.heads([b'rev3b', b'rev2b'])) 858 self.assertEqual({b'rev3b'}, 859 graph.heads([b'rev3b', b'rev2a', b'rev2b'])) 860 self.assertEqual({b'rev3a', b'rev3b'}, 861 graph.heads([b'rev3a', b'rev3b'])) 862 self.assertEqual({b'rev3a', b'rev3b'}, 863 graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b'])) 864 865 def test_heads_shortcut(self): 866 graph = self.make_graph(history_shortcut) 867 868 self.assertEqual({b'rev2a', b'rev2b', b'rev2c'}, 869 graph.heads([b'rev2a', b'rev2b', b'rev2c'])) 870 self.assertEqual({b'rev3a', b'rev3b'}, 871 graph.heads([b'rev3a', b'rev3b'])) 872 self.assertEqual({b'rev3a', b'rev3b'}, 873 graph.heads([b'rev2a', b'rev3a', b'rev3b'])) 874 self.assertEqual({b'rev2a', b'rev3b'}, 875 graph.heads([b'rev2a', b'rev3b'])) 876 self.assertEqual({b'rev2c', b'rev3a'}, 877 graph.heads([b'rev2c', b'rev3a'])) 878 879 def _run_heads_break_deeper(self, graph_dict, search): 880 """Run heads on a graph-as-a-dict. 881 882 If the search asks for the parents of b'deeper' the test will fail. 883 """ 884 class stub(object): 885 pass 886 887 def get_parent_map(keys): 888 result = {} 889 for key in keys: 890 if key == b'deeper': 891 self.fail('key deeper was accessed') 892 result[key] = graph_dict[key] 893 return result 894 an_obj = stub() 895 an_obj.get_parent_map = get_parent_map 896 graph = _mod_graph.Graph(an_obj) 897 return graph.heads(search) 898 899 def test_heads_limits_search(self): 900 # test that a heads query does not search all of history 901 graph_dict = { 902 b'left': [b'common'], 903 b'right': [b'common'], 904 b'common': [b'deeper'], 905 } 906 self.assertEqual({b'left', b'right'}, 907 self._run_heads_break_deeper(graph_dict, [b'left', b'right'])) 908 909 def test_heads_limits_search_assymetric(self): 910 # test that a heads query does not search all of history 911 graph_dict = { 912 b'left': [b'midleft'], 913 b'midleft': [b'common'], 914 b'right': [b'common'], 915 b'common': [b'aftercommon'], 916 b'aftercommon': [b'deeper'], 917 } 918 self.assertEqual({b'left', b'right'}, 919 self._run_heads_break_deeper(graph_dict, [b'left', b'right'])) 920 921 def test_heads_limits_search_common_search_must_continue(self): 922 # test that common nodes are still queried, preventing 923 # all-the-way-to-origin behaviour in the following graph: 924 graph_dict = { 925 b'h1': [b'shortcut', b'common1'], 926 b'h2': [b'common1'], 927 b'shortcut': [b'common2'], 928 b'common1': [b'common2'], 929 b'common2': [b'deeper'], 930 } 931 self.assertEqual({b'h1', b'h2'}, 932 self._run_heads_break_deeper(graph_dict, [b'h1', b'h2'])) 933 934 def test_breadth_first_search_start_ghosts(self): 935 graph = self.make_graph({}) 936 # with_ghosts reports the ghosts 937 search = graph._make_breadth_first_searcher([b'a-ghost']) 938 self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts()) 939 self.assertRaises(StopIteration, search.next_with_ghosts) 940 # next includes them 941 search = graph._make_breadth_first_searcher([b'a-ghost']) 942 self.assertEqual({b'a-ghost'}, next(search)) 943 self.assertRaises(StopIteration, next, search) 944 945 def test_breadth_first_search_deep_ghosts(self): 946 graph = self.make_graph({ 947 b'head': [b'present'], 948 b'present': [b'child', b'ghost'], 949 b'child': [], 950 }) 951 # with_ghosts reports the ghosts 952 search = graph._make_breadth_first_searcher([b'head']) 953 self.assertEqual(({b'head'}, set()), search.next_with_ghosts()) 954 self.assertEqual(({b'present'}, set()), search.next_with_ghosts()) 955 self.assertEqual(({b'child'}, {b'ghost'}), 956 search.next_with_ghosts()) 957 self.assertRaises(StopIteration, search.next_with_ghosts) 958 # next includes them 959 search = graph._make_breadth_first_searcher([b'head']) 960 self.assertEqual({b'head'}, next(search)) 961 self.assertEqual({b'present'}, next(search)) 962 self.assertEqual({b'child', b'ghost'}, 963 next(search)) 964 self.assertRaises(StopIteration, next, search) 965 966 def test_breadth_first_search_change_next_to_next_with_ghosts(self): 967 # To make the API robust, we allow calling both next() and 968 # next_with_ghosts() on the same searcher. 969 graph = self.make_graph({ 970 b'head': [b'present'], 971 b'present': [b'child', b'ghost'], 972 b'child': [], 973 }) 974 # start with next_with_ghosts 975 search = graph._make_breadth_first_searcher([b'head']) 976 self.assertEqual(({b'head'}, set()), search.next_with_ghosts()) 977 self.assertEqual({b'present'}, next(search)) 978 self.assertEqual(({b'child'}, {b'ghost'}), 979 search.next_with_ghosts()) 980 self.assertRaises(StopIteration, next, search) 981 # start with next 982 search = graph._make_breadth_first_searcher([b'head']) 983 self.assertEqual({b'head'}, next(search)) 984 self.assertEqual(({b'present'}, set()), search.next_with_ghosts()) 985 self.assertEqual({b'child', b'ghost'}, 986 next(search)) 987 self.assertRaises(StopIteration, search.next_with_ghosts) 988 989 def test_breadth_first_change_search(self): 990 # Changing the search should work with both next and next_with_ghosts. 991 graph = self.make_graph({ 992 b'head': [b'present'], 993 b'present': [b'stopped'], 994 b'other': [b'other_2'], 995 b'other_2': [], 996 }) 997 search = graph._make_breadth_first_searcher([b'head']) 998 self.assertEqual(({b'head'}, set()), search.next_with_ghosts()) 999 self.assertEqual(({b'present'}, set()), search.next_with_ghosts()) 1000 self.assertEqual({b'present'}, 1001 search.stop_searching_any([b'present'])) 1002 self.assertEqual(({b'other'}, {b'other_ghost'}), 1003 search.start_searching([b'other', b'other_ghost'])) 1004 self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts()) 1005 self.assertRaises(StopIteration, search.next_with_ghosts) 1006 # next includes them 1007 search = graph._make_breadth_first_searcher([b'head']) 1008 self.assertEqual({b'head'}, next(search)) 1009 self.assertEqual({b'present'}, next(search)) 1010 self.assertEqual({b'present'}, 1011 search.stop_searching_any([b'present'])) 1012 search.start_searching([b'other', b'other_ghost']) 1013 self.assertEqual({b'other_2'}, next(search)) 1014 self.assertRaises(StopIteration, next, search) 1015 1016 def assertSeenAndResult(self, instructions, search, next): 1017 """Check the results of .seen and get_result() for a seach. 1018 1019 :param instructions: A list of tuples: 1020 (seen, recipe, included_keys, starts, stops). 1021 seen, recipe and included_keys are results to check on the search 1022 and the searches get_result(). starts and stops are parameters to 1023 pass to start_searching and stop_searching_any during each 1024 iteration, if they are not None. 1025 :param search: The search to use. 1026 :param next: A callable to advance the search. 1027 """ 1028 for seen, recipe, included_keys, starts, stops in instructions: 1029 # Adjust for recipe contract changes that don't vary for all the 1030 # current tests. 1031 recipe = ('search',) + recipe 1032 next() 1033 if starts is not None: 1034 search.start_searching(starts) 1035 if stops is not None: 1036 search.stop_searching_any(stops) 1037 state = search.get_state() 1038 self.assertEqual(set(included_keys), state[2]) 1039 self.assertEqual(seen, search.seen) 1040 1041 def test_breadth_first_get_result_excludes_current_pending(self): 1042 graph = self.make_graph({ 1043 b'head': [b'child'], 1044 b'child': [NULL_REVISION], 1045 NULL_REVISION: [], 1046 }) 1047 search = graph._make_breadth_first_searcher([b'head']) 1048 # At the start, nothing has been seen, to its all excluded: 1049 state = search.get_state() 1050 self.assertEqual(({b'head'}, {b'head'}, set()), 1051 state) 1052 self.assertEqual(set(), search.seen) 1053 # using next: 1054 expected = [ 1055 ({b'head'}, ({b'head'}, {b'child'}, 1), 1056 [b'head'], None, None), 1057 ({b'head', b'child'}, ({b'head'}, {NULL_REVISION}, 2), 1058 [b'head', b'child'], None, None), 1059 ({b'head', b'child', NULL_REVISION}, ({b'head'}, set(), 3), 1060 [b'head', b'child', NULL_REVISION], None, None), 1061 ] 1062 self.assertSeenAndResult(expected, search, search.__next__) 1063 # using next_with_ghosts: 1064 search = graph._make_breadth_first_searcher([b'head']) 1065 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1066 1067 def test_breadth_first_get_result_starts_stops(self): 1068 graph = self.make_graph({ 1069 b'head': [b'child'], 1070 b'child': [NULL_REVISION], 1071 b'otherhead': [b'otherchild'], 1072 b'otherchild': [b'excluded'], 1073 b'excluded': [NULL_REVISION], 1074 NULL_REVISION: [] 1075 }) 1076 search = graph._make_breadth_first_searcher([]) 1077 # Starting with nothing and adding a search works: 1078 search.start_searching([b'head']) 1079 # head has been seen: 1080 state = search.get_state() 1081 self.assertEqual(({b'head'}, {b'child'}, {b'head'}), 1082 state) 1083 self.assertEqual({b'head'}, search.seen) 1084 # using next: 1085 expected = [ 1086 # stop at child, and start a new search at otherhead: 1087 # - otherhead counts as seen immediately when start_searching is 1088 # called. 1089 ({b'head', b'child', b'otherhead'}, 1090 ({b'head', b'otherhead'}, {b'child', b'otherchild'}, 2), 1091 [b'head', b'otherhead'], [b'otherhead'], [b'child']), 1092 ({b'head', b'child', b'otherhead', b'otherchild'}, 1093 ({b'head', b'otherhead'}, {b'child', b'excluded'}, 3), 1094 [b'head', b'otherhead', b'otherchild'], None, None), 1095 # stop searching excluded now 1096 ({b'head', b'child', b'otherhead', b'otherchild', b'excluded'}, 1097 ({b'head', b'otherhead'}, {b'child', b'excluded'}, 3), 1098 [b'head', b'otherhead', b'otherchild'], None, [b'excluded']), 1099 ] 1100 self.assertSeenAndResult(expected, search, search.__next__) 1101 # using next_with_ghosts: 1102 search = graph._make_breadth_first_searcher([]) 1103 search.start_searching([b'head']) 1104 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1105 1106 def test_breadth_first_stop_searching_not_queried(self): 1107 # A client should be able to say b'stop node X' even if X has not been 1108 # returned to the client. 1109 graph = self.make_graph({ 1110 b'head': [b'child', b'ghost1'], 1111 b'child': [NULL_REVISION], 1112 NULL_REVISION: [], 1113 }) 1114 search = graph._make_breadth_first_searcher([b'head']) 1115 expected = [ 1116 # NULL_REVISION and ghost1 have not been returned 1117 ({b'head'}, 1118 ({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1), 1119 [b'head'], None, [NULL_REVISION, b'ghost1']), 1120 # ghost1 has been returned, NULL_REVISION is to be returned in the 1121 # next iteration. 1122 ({b'head', b'child', b'ghost1'}, 1123 ({b'head'}, {b'ghost1', NULL_REVISION}, 2), 1124 [b'head', b'child'], None, [NULL_REVISION, b'ghost1']), 1125 ] 1126 self.assertSeenAndResult(expected, search, search.__next__) 1127 # using next_with_ghosts: 1128 search = graph._make_breadth_first_searcher([b'head']) 1129 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1130 1131 def test_breadth_first_stop_searching_late(self): 1132 # A client should be able to say b'stop node X' and have it excluded 1133 # from the result even if X was seen in an older iteration of the 1134 # search. 1135 graph = self.make_graph({ 1136 b'head': [b'middle'], 1137 b'middle': [b'child'], 1138 b'child': [NULL_REVISION], 1139 NULL_REVISION: [], 1140 }) 1141 search = graph._make_breadth_first_searcher([b'head']) 1142 expected = [ 1143 ({b'head'}, ({b'head'}, {b'middle'}, 1), 1144 [b'head'], None, None), 1145 ({b'head', b'middle'}, ({b'head'}, {b'child'}, 2), 1146 [b'head', b'middle'], None, None), 1147 # b'middle' came from the previous iteration, but we don't stop 1148 # searching it until *after* advancing the searcher. 1149 ({b'head', b'middle', b'child'}, 1150 ({b'head'}, {b'middle', b'child'}, 1), 1151 [b'head'], None, [b'middle', b'child']), 1152 ] 1153 self.assertSeenAndResult(expected, search, search.__next__) 1154 # using next_with_ghosts: 1155 search = graph._make_breadth_first_searcher([b'head']) 1156 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1157 1158 def test_breadth_first_get_result_ghosts_are_excluded(self): 1159 graph = self.make_graph({ 1160 b'head': [b'child', b'ghost'], 1161 b'child': [NULL_REVISION], 1162 NULL_REVISION: [], 1163 }) 1164 search = graph._make_breadth_first_searcher([b'head']) 1165 # using next: 1166 expected = [ 1167 ({b'head'}, 1168 ({b'head'}, {b'ghost', b'child'}, 1), 1169 [b'head'], None, None), 1170 ({b'head', b'child', b'ghost'}, 1171 ({b'head'}, {NULL_REVISION, b'ghost'}, 2), 1172 [b'head', b'child'], None, None), 1173 ] 1174 self.assertSeenAndResult(expected, search, search.__next__) 1175 # using next_with_ghosts: 1176 search = graph._make_breadth_first_searcher([b'head']) 1177 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1178 1179 def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self): 1180 graph = self.make_graph({ 1181 b'head': [b'child'], 1182 b'child': [NULL_REVISION], 1183 NULL_REVISION: [], 1184 }) 1185 search = graph._make_breadth_first_searcher([b'head']) 1186 # using next: 1187 expected = [ 1188 ({b'head', b'ghost'}, 1189 ({b'head', b'ghost'}, {b'child', b'ghost'}, 1), 1190 [b'head'], [b'ghost'], None), 1191 ({b'head', b'child', b'ghost'}, 1192 ({b'head', b'ghost'}, {NULL_REVISION, b'ghost'}, 2), 1193 [b'head', b'child'], None, None), 1194 ] 1195 self.assertSeenAndResult(expected, search, search.__next__) 1196 # using next_with_ghosts: 1197 search = graph._make_breadth_first_searcher([b'head']) 1198 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1199 1200 def test_breadth_first_revision_count_includes_NULL_REVISION(self): 1201 graph = self.make_graph({ 1202 b'head': [NULL_REVISION], 1203 NULL_REVISION: [], 1204 }) 1205 search = graph._make_breadth_first_searcher([b'head']) 1206 # using next: 1207 expected = [ 1208 ({b'head'}, 1209 ({b'head'}, {NULL_REVISION}, 1), 1210 [b'head'], None, None), 1211 ({b'head', NULL_REVISION}, 1212 ({b'head'}, set([]), 2), 1213 [b'head', NULL_REVISION], None, None), 1214 ] 1215 self.assertSeenAndResult(expected, search, search.__next__) 1216 # using next_with_ghosts: 1217 search = graph._make_breadth_first_searcher([b'head']) 1218 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1219 1220 def test_breadth_first_search_get_result_after_StopIteration(self): 1221 # StopIteration should not invalid anything.. 1222 graph = self.make_graph({ 1223 b'head': [NULL_REVISION], 1224 NULL_REVISION: [], 1225 }) 1226 search = graph._make_breadth_first_searcher([b'head']) 1227 # using next: 1228 expected = [ 1229 ({b'head'}, 1230 ({b'head'}, {NULL_REVISION}, 1), 1231 [b'head'], None, None), 1232 ({b'head', b'ghost', NULL_REVISION}, 1233 ({b'head', b'ghost'}, {b'ghost'}, 2), 1234 [b'head', NULL_REVISION], [b'ghost'], None), 1235 ] 1236 self.assertSeenAndResult(expected, search, search.__next__) 1237 self.assertRaises(StopIteration, next, search) 1238 self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen) 1239 state = search.get_state() 1240 self.assertEqual( 1241 ({b'ghost', b'head'}, {b'ghost'}, 1242 {b'head', NULL_REVISION}), 1243 state) 1244 # using next_with_ghosts: 1245 search = graph._make_breadth_first_searcher([b'head']) 1246 self.assertSeenAndResult(expected, search, search.next_with_ghosts) 1247 self.assertRaises(StopIteration, next, search) 1248 self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen) 1249 state = search.get_state() 1250 self.assertEqual( 1251 ({b'ghost', b'head'}, {b'ghost'}, 1252 {b'head', NULL_REVISION}), 1253 state) 1254 1255 1256class TestFindUniqueAncestors(TestGraphBase): 1257 1258 def assertFindUniqueAncestors(self, graph, expected, node, common): 1259 actual = graph.find_unique_ancestors(node, common) 1260 self.assertEqual(expected, sorted(actual)) 1261 1262 def test_empty_set(self): 1263 graph = self.make_graph(ancestry_1) 1264 self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev1']) 1265 self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev2b']) 1266 self.assertFindUniqueAncestors(graph, [], b'rev3', [b'rev1', b'rev3']) 1267 1268 def test_single_node(self): 1269 graph = self.make_graph(ancestry_1) 1270 self.assertFindUniqueAncestors(graph, [b'rev2a'], b'rev2a', [b'rev1']) 1271 self.assertFindUniqueAncestors(graph, [b'rev2b'], b'rev2b', [b'rev1']) 1272 self.assertFindUniqueAncestors(graph, [b'rev3'], b'rev3', [b'rev2a']) 1273 1274 def test_minimal_ancestry(self): 1275 graph = self.make_breaking_graph(extended_history_shortcut, 1276 [NULL_REVISION, b'a', b'b']) 1277 self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd']) 1278 1279 graph = self.make_breaking_graph(extended_history_shortcut, 1280 [b'b']) 1281 self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd']) 1282 1283 graph = self.make_breaking_graph(complex_shortcut, 1284 [b'a', b'b']) 1285 self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'i']) 1286 self.assertFindUniqueAncestors(graph, [b'e', b'g', b'i'], b'i', [b'h']) 1287 self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'g']) 1288 self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'j']) 1289 1290 def test_in_ancestry(self): 1291 graph = self.make_graph(ancestry_1) 1292 self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3']) 1293 self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4']) 1294 1295 def test_multiple_revisions(self): 1296 graph = self.make_graph(ancestry_1) 1297 self.assertFindUniqueAncestors(graph, 1298 [b'rev4'], b'rev4', [b'rev3', b'rev2b']) 1299 self.assertFindUniqueAncestors(graph, 1300 [b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b']) 1301 1302 def test_complex_shortcut(self): 1303 graph = self.make_graph(complex_shortcut) 1304 self.assertFindUniqueAncestors(graph, 1305 [b'h', b'n'], b'n', [b'm']) 1306 self.assertFindUniqueAncestors(graph, 1307 [b'e', b'i', b'm'], b'm', [b'n']) 1308 1309 def test_complex_shortcut2(self): 1310 graph = self.make_graph(complex_shortcut2) 1311 self.assertFindUniqueAncestors(graph, 1312 [b'j', b'u'], b'u', [b't']) 1313 self.assertFindUniqueAncestors(graph, 1314 [b't'], b't', [b'u']) 1315 1316 def test_multiple_interesting_unique(self): 1317 graph = self.make_graph(multiple_interesting_unique) 1318 self.assertFindUniqueAncestors(graph, 1319 [b'j', b'y'], b'y', [b'z']) 1320 self.assertFindUniqueAncestors(graph, 1321 [b'p', b'z'], b'z', [b'y']) 1322 1323 def test_racing_shortcuts(self): 1324 graph = self.make_graph(racing_shortcuts) 1325 self.assertFindUniqueAncestors(graph, 1326 [b'p', b'q', b'z'], b'z', [b'y']) 1327 self.assertFindUniqueAncestors(graph, 1328 [b'h', b'i', b'j', b'y'], b'j', [b'z']) 1329 1330 1331class TestGraphFindDistanceToNull(TestGraphBase): 1332 """Test an api that should be able to compute a revno""" 1333 1334 def assertFindDistance(self, revno, graph, target_id, known_ids): 1335 """Assert the output of Graph.find_distance_to_null()""" 1336 actual = graph.find_distance_to_null(target_id, known_ids) 1337 self.assertEqual(revno, actual) 1338 1339 def test_nothing_known(self): 1340 graph = self.make_graph(ancestry_1) 1341 self.assertFindDistance(0, graph, NULL_REVISION, []) 1342 self.assertFindDistance(1, graph, b'rev1', []) 1343 self.assertFindDistance(2, graph, b'rev2a', []) 1344 self.assertFindDistance(2, graph, b'rev2b', []) 1345 self.assertFindDistance(3, graph, b'rev3', []) 1346 self.assertFindDistance(4, graph, b'rev4', []) 1347 1348 def test_rev_is_ghost(self): 1349 graph = self.make_graph(ancestry_1) 1350 e = self.assertRaises(errors.GhostRevisionsHaveNoRevno, 1351 graph.find_distance_to_null, b'rev_missing', []) 1352 self.assertEqual(b'rev_missing', e.revision_id) 1353 self.assertEqual(b'rev_missing', e.ghost_revision_id) 1354 1355 def test_ancestor_is_ghost(self): 1356 graph = self.make_graph({b'rev': [b'parent']}) 1357 e = self.assertRaises(errors.GhostRevisionsHaveNoRevno, 1358 graph.find_distance_to_null, b'rev', []) 1359 self.assertEqual(b'rev', e.revision_id) 1360 self.assertEqual(b'parent', e.ghost_revision_id) 1361 1362 def test_known_in_ancestry(self): 1363 graph = self.make_graph(ancestry_1) 1364 self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)]) 1365 self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)]) 1366 1367 def test_known_in_ancestry_limits(self): 1368 graph = self.make_breaking_graph(ancestry_1, [b'rev1']) 1369 self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)]) 1370 1371 def test_target_is_ancestor(self): 1372 graph = self.make_graph(ancestry_1) 1373 self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)]) 1374 1375 def test_target_is_ancestor_limits(self): 1376 """We shouldn't search all history if we run into ourselves""" 1377 graph = self.make_breaking_graph(ancestry_1, [b'rev1']) 1378 self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)]) 1379 1380 def test_target_parallel_to_known_limits(self): 1381 # Even though the known revision isn't part of the other ancestry, they 1382 # eventually converge 1383 graph = self.make_breaking_graph(with_tail, [b'a']) 1384 self.assertFindDistance(6, graph, b'f', [(b'g', 6)]) 1385 self.assertFindDistance(7, graph, b'h', [(b'g', 6)]) 1386 self.assertFindDistance(8, graph, b'i', [(b'g', 6)]) 1387 self.assertFindDistance(6, graph, b'g', [(b'i', 8)]) 1388 1389 1390class TestFindMergeOrder(TestGraphBase): 1391 1392 def assertMergeOrder(self, expected, graph, tip, base_revisions): 1393 self.assertEqual(expected, graph.find_merge_order(tip, base_revisions)) 1394 1395 def test_parents(self): 1396 graph = self.make_graph(ancestry_1) 1397 self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4', 1398 [b'rev3', b'rev2b']) 1399 self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4', 1400 [b'rev2b', b'rev3']) 1401 1402 def test_ancestors(self): 1403 graph = self.make_graph(ancestry_1) 1404 self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4', 1405 [b'rev1', b'rev2b']) 1406 self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4', 1407 [b'rev2b', b'rev1']) 1408 1409 def test_shortcut_one_ancestor(self): 1410 # When we have enough info, we can stop searching 1411 graph = self.make_breaking_graph( 1412 ancestry_1, [b'rev3', b'rev2b', b'rev4']) 1413 # Single ancestors shortcut right away 1414 self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3']) 1415 1416 def test_shortcut_after_one_ancestor(self): 1417 graph = self.make_breaking_graph(ancestry_1, [b'rev2a', b'rev2b']) 1418 self.assertMergeOrder([b'rev3', b'rev1'], graph, 1419 b'rev4', [b'rev1', b'rev3']) 1420 1421 1422class TestFindDescendants(TestGraphBase): 1423 1424 def test_find_descendants_rev1_rev3(self): 1425 graph = self.make_graph(ancestry_1) 1426 descendants = graph.find_descendants(b'rev1', b'rev3') 1427 self.assertEqual({b'rev1', b'rev2a', b'rev3'}, descendants) 1428 1429 def test_find_descendants_rev1_rev4(self): 1430 graph = self.make_graph(ancestry_1) 1431 descendants = graph.find_descendants(b'rev1', b'rev4') 1432 self.assertEqual({b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'}, 1433 descendants) 1434 1435 def test_find_descendants_rev2a_rev4(self): 1436 graph = self.make_graph(ancestry_1) 1437 descendants = graph.find_descendants(b'rev2a', b'rev4') 1438 self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants) 1439 1440 1441class TestFindLefthandMerger(TestGraphBase): 1442 1443 def check_merger(self, result, ancestry, merged, tip): 1444 graph = self.make_graph(ancestry) 1445 self.assertEqual(result, graph.find_lefthand_merger(merged, tip)) 1446 1447 def test_find_lefthand_merger_rev2b(self): 1448 self.check_merger(b'rev4', ancestry_1, b'rev2b', b'rev4') 1449 1450 def test_find_lefthand_merger_rev2a(self): 1451 self.check_merger(b'rev2a', ancestry_1, b'rev2a', b'rev4') 1452 1453 def test_find_lefthand_merger_rev4(self): 1454 self.check_merger(None, ancestry_1, b'rev4', b'rev2a') 1455 1456 def test_find_lefthand_merger_f(self): 1457 self.check_merger(b'i', complex_shortcut, b'f', b'm') 1458 1459 def test_find_lefthand_merger_g(self): 1460 self.check_merger(b'i', complex_shortcut, b'g', b'm') 1461 1462 def test_find_lefthand_merger_h(self): 1463 self.check_merger(b'n', complex_shortcut, b'h', b'n') 1464 1465 1466class TestGetChildMap(TestGraphBase): 1467 1468 def test_get_child_map(self): 1469 graph = self.make_graph(ancestry_1) 1470 child_map = graph.get_child_map([b'rev4', b'rev3', b'rev2a', b'rev2b']) 1471 self.assertEqual({b'rev1': [b'rev2a', b'rev2b'], 1472 b'rev2a': [b'rev3'], 1473 b'rev2b': [b'rev4'], 1474 b'rev3': [b'rev4']}, 1475 child_map) 1476 1477 1478class TestCachingParentsProvider(tests.TestCase): 1479 """These tests run with: 1480 1481 self.inst_pp, a recording parents provider with a graph of a->b, and b is a 1482 ghost. 1483 self.caching_pp, a CachingParentsProvider layered on inst_pp. 1484 """ 1485 1486 def setUp(self): 1487 super(TestCachingParentsProvider, self).setUp() 1488 dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)}) 1489 self.inst_pp = InstrumentedParentsProvider(dict_pp) 1490 self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp) 1491 1492 def test_get_parent_map(self): 1493 """Requesting the same revision should be returned from cache""" 1494 self.assertEqual({}, self.caching_pp._cache) 1495 self.assertEqual( 1496 {b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a'])) 1497 self.assertEqual([b'a'], self.inst_pp.calls) 1498 self.assertEqual( 1499 {b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a'])) 1500 # No new call, as it should have been returned from the cache 1501 self.assertEqual([b'a'], self.inst_pp.calls) 1502 self.assertEqual({b'a': (b'b',)}, self.caching_pp._cache) 1503 1504 def test_get_parent_map_not_present(self): 1505 """The cache should also track when a revision doesn't exist""" 1506 self.assertEqual({}, self.caching_pp.get_parent_map([b'b'])) 1507 self.assertEqual([b'b'], self.inst_pp.calls) 1508 self.assertEqual({}, self.caching_pp.get_parent_map([b'b'])) 1509 # No new calls 1510 self.assertEqual([b'b'], self.inst_pp.calls) 1511 1512 def test_get_parent_map_mixed(self): 1513 """Anything that can be returned from cache, should be""" 1514 self.assertEqual({}, self.caching_pp.get_parent_map([b'b'])) 1515 self.assertEqual([b'b'], self.inst_pp.calls) 1516 self.assertEqual({b'a': (b'b',)}, 1517 self.caching_pp.get_parent_map([b'a', b'b'])) 1518 self.assertEqual([b'b', b'a'], self.inst_pp.calls) 1519 1520 def test_get_parent_map_repeated(self): 1521 """Asking for the same parent 2x will only forward 1 request.""" 1522 self.assertEqual({b'a': (b'b',)}, 1523 self.caching_pp.get_parent_map([b'b', b'a', b'b'])) 1524 # Use sorted because we don't care about the order, just that each is 1525 # only present 1 time. 1526 self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls)) 1527 1528 def test_note_missing_key(self): 1529 """After noting that a key is missing it is cached.""" 1530 self.caching_pp.note_missing_key(b'b') 1531 self.assertEqual({}, self.caching_pp.get_parent_map([b'b'])) 1532 self.assertEqual([], self.inst_pp.calls) 1533 self.assertEqual({b'b'}, self.caching_pp.missing_keys) 1534 1535 def test_get_cached_parent_map(self): 1536 self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a'])) 1537 self.assertEqual([], self.inst_pp.calls) 1538 self.assertEqual( 1539 {b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a'])) 1540 self.assertEqual([b'a'], self.inst_pp.calls) 1541 self.assertEqual({b'a': (b'b',)}, 1542 self.caching_pp.get_cached_parent_map([b'a'])) 1543 1544 1545class TestCachingParentsProviderExtras(tests.TestCaseWithTransport): 1546 """Test the behaviour when parents are provided that were not requested.""" 1547 1548 def setUp(self): 1549 super(TestCachingParentsProviderExtras, self).setUp() 1550 1551 class ExtraParentsProvider(object): 1552 1553 def get_parent_map(self, keys): 1554 return {b'rev1': [], b'rev2': [b'rev1', ]} 1555 1556 self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider()) 1557 self.caching_pp = _mod_graph.CachingParentsProvider( 1558 get_parent_map=self.inst_pp.get_parent_map) 1559 1560 def test_uncached(self): 1561 self.caching_pp.disable_cache() 1562 self.assertEqual({b'rev1': []}, 1563 self.caching_pp.get_parent_map([b'rev1'])) 1564 self.assertEqual([b'rev1'], self.inst_pp.calls) 1565 self.assertIs(None, self.caching_pp._cache) 1566 1567 def test_cache_initially_empty(self): 1568 self.assertEqual({}, self.caching_pp._cache) 1569 1570 def test_cached(self): 1571 self.assertEqual({b'rev1': []}, 1572 self.caching_pp.get_parent_map([b'rev1'])) 1573 self.assertEqual([b'rev1'], self.inst_pp.calls) 1574 self.assertEqual({b'rev1': [], b'rev2': [b'rev1']}, 1575 self.caching_pp._cache) 1576 self.assertEqual({b'rev1': []}, 1577 self.caching_pp.get_parent_map([b'rev1'])) 1578 self.assertEqual([b'rev1'], self.inst_pp.calls) 1579 1580 def test_disable_cache_clears_cache(self): 1581 # Put something in the cache 1582 self.caching_pp.get_parent_map([b'rev1']) 1583 self.assertEqual(2, len(self.caching_pp._cache)) 1584 self.caching_pp.disable_cache() 1585 self.assertIs(None, self.caching_pp._cache) 1586 1587 def test_enable_cache_raises(self): 1588 e = self.assertRaises(AssertionError, self.caching_pp.enable_cache) 1589 self.assertEqual('Cache enabled when already enabled.', str(e)) 1590 1591 def test_cache_misses(self): 1592 self.caching_pp.get_parent_map([b'rev3']) 1593 self.caching_pp.get_parent_map([b'rev3']) 1594 self.assertEqual([b'rev3'], self.inst_pp.calls) 1595 1596 def test_no_cache_misses(self): 1597 self.caching_pp.disable_cache() 1598 self.caching_pp.enable_cache(cache_misses=False) 1599 self.caching_pp.get_parent_map([b'rev3']) 1600 self.caching_pp.get_parent_map([b'rev3']) 1601 self.assertEqual([b'rev3', b'rev3'], self.inst_pp.calls) 1602 1603 def test_cache_extras(self): 1604 self.assertEqual({}, self.caching_pp.get_parent_map([b'rev3'])) 1605 self.assertEqual({b'rev2': [b'rev1']}, 1606 self.caching_pp.get_parent_map([b'rev2'])) 1607 self.assertEqual([b'rev3'], self.inst_pp.calls) 1608 1609 def test_extras_using_cached(self): 1610 self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'rev3'])) 1611 self.assertEqual({}, self.caching_pp.get_parent_map([b'rev3'])) 1612 self.assertEqual({b'rev2': [b'rev1']}, 1613 self.caching_pp.get_cached_parent_map([b'rev2'])) 1614 self.assertEqual([b'rev3'], self.inst_pp.calls) 1615 1616 1617class TestCollapseLinearRegions(tests.TestCase): 1618 1619 def assertCollapsed(self, collapsed, original): 1620 self.assertEqual(collapsed, 1621 _mod_graph.collapse_linear_regions(original)) 1622 1623 def test_collapse_nothing(self): 1624 d = {1: [2, 3], 2: [], 3: []} 1625 self.assertCollapsed(d, d) 1626 d = {1: [2], 2: [3, 4], 3: [5], 4: [5], 5: []} 1627 self.assertCollapsed(d, d) 1628 1629 def test_collapse_chain(self): 1630 # Any time we have a linear chain, we should be able to collapse 1631 d = {1: [2], 2: [3], 3: [4], 4: [5], 5: []} 1632 self.assertCollapsed({1: [5], 5: []}, d) 1633 d = {5: [4], 4: [3], 3: [2], 2: [1], 1: []} 1634 self.assertCollapsed({5: [1], 1: []}, d) 1635 d = {5: [3], 3: [4], 4: [1], 1: [2], 2: []} 1636 self.assertCollapsed({5: [2], 2: []}, d) 1637 1638 def test_collapse_with_multiple_children(self): 1639 # 7 1640 # | 1641 # 6 1642 # / \ 1643 # 4 5 1644 # | | 1645 # 2 3 1646 # \ / 1647 # 1 1648 # 1649 # 4 and 5 cannot be removed because 6 has 2 children 1650 # 2 and 3 cannot be removed because 1 has 2 parents 1651 d = {1: [2, 3], 2: [4], 4: [6], 3: [5], 5: [6], 6: [7], 7: []} 1652 self.assertCollapsed(d, d) 1653 1654 1655class TestGraphThunkIdsToKeys(tests.TestCase): 1656 1657 def test_heads(self): 1658 # A 1659 # |\ 1660 # B C 1661 # |/ 1662 # D 1663 d = {(b'D',): [(b'B',), (b'C',)], (b'C',): [(b'A',)], 1664 (b'B',): [(b'A',)], (b'A',): []} 1665 g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d)) 1666 graph_thunk = _mod_graph.GraphThunkIdsToKeys(g) 1667 self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'A']))) 1668 self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'B']))) 1669 self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'C']))) 1670 self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C']))) 1671 1672 def test_add_node(self): 1673 d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []} 1674 g = _mod_graph.KnownGraph(d) 1675 graph_thunk = _mod_graph.GraphThunkIdsToKeys(g) 1676 graph_thunk.add_node(b"D", [b"A", b"C"]) 1677 self.assertEqual([b'B', b'D'], 1678 sorted(graph_thunk.heads([b'D', b'B', b'A']))) 1679 1680 def test_merge_sort(self): 1681 d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []} 1682 g = _mod_graph.KnownGraph(d) 1683 graph_thunk = _mod_graph.GraphThunkIdsToKeys(g) 1684 graph_thunk.add_node(b"D", [b"A", b"C"]) 1685 self.assertEqual([(b'C', 0, (2,), False), (b'A', 0, (1,), True)], 1686 [(n.key, n.merge_depth, n.revno, n.end_of_merge) 1687 for n in graph_thunk.merge_sort(b'C')]) 1688 1689 1690class TestStackedParentsProvider(tests.TestCase): 1691 1692 def setUp(self): 1693 super(TestStackedParentsProvider, self).setUp() 1694 self.calls = [] 1695 1696 def get_shared_provider(self, info, ancestry, has_cached): 1697 pp = _mod_graph.DictParentsProvider(ancestry) 1698 if has_cached: 1699 pp.get_cached_parent_map = pp.get_parent_map 1700 return SharedInstrumentedParentsProvider(pp, self.calls, info) 1701 1702 def test_stacked_parents_provider(self): 1703 parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']}) 1704 parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']}) 1705 stacked = _mod_graph.StackedParentsProvider([parents1, parents2]) 1706 self.assertEqual({b'rev1': [b'rev4'], b'rev2': [b'rev3']}, 1707 stacked.get_parent_map([b'rev1', b'rev2'])) 1708 self.assertEqual({b'rev2': [b'rev3'], b'rev1': [b'rev4']}, 1709 stacked.get_parent_map([b'rev2', b'rev1'])) 1710 self.assertEqual({b'rev2': [b'rev3']}, 1711 stacked.get_parent_map([b'rev2', b'rev2'])) 1712 self.assertEqual({b'rev1': [b'rev4']}, 1713 stacked.get_parent_map([b'rev1', b'rev1'])) 1714 1715 def test_stacked_parents_provider_overlapping(self): 1716 # rev2 is availible in both providers. 1717 # 1 1718 # | 1719 # 2 1720 parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']}) 1721 parents2 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']}) 1722 stacked = _mod_graph.StackedParentsProvider([parents1, parents2]) 1723 self.assertEqual({b'rev2': [b'rev1']}, 1724 stacked.get_parent_map([b'rev2'])) 1725 1726 def test_handles_no_get_cached_parent_map(self): 1727 # this shows that we both handle when a provider doesn't implement 1728 # get_cached_parent_map 1729 pp1 = self.get_shared_provider(b'pp1', {b'rev2': (b'rev1',)}, 1730 has_cached=False) 1731 pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)}, 1732 has_cached=True) 1733 stacked = _mod_graph.StackedParentsProvider([pp1, pp2]) 1734 self.assertEqual({b'rev2': (b'rev1',)}, 1735 stacked.get_parent_map([b'rev2'])) 1736 # No call on b'pp1' because it doesn't provide get_cached_parent_map 1737 self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls) 1738 1739 def test_query_order(self): 1740 # We should call get_cached_parent_map on all providers before we call 1741 # get_parent_map. Further, we should track what entries we have found, 1742 # and not re-try them. 1743 pp1 = self.get_shared_provider(b'pp1', {b'a': ()}, has_cached=True) 1744 pp2 = self.get_shared_provider( 1745 b'pp2', {b'c': (b'b',)}, has_cached=False) 1746 pp3 = self.get_shared_provider( 1747 b'pp3', {b'b': (b'a',)}, has_cached=True) 1748 stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3]) 1749 self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)}, 1750 stacked.get_parent_map([b'a', b'b', b'c', b'd'])) 1751 self.assertEqual([(b'pp1', 'cached', [b'a', b'b', b'c', b'd']), 1752 # No call to pp2, because it doesn't have cached 1753 (b'pp3', 'cached', [b'b', b'c', b'd']), 1754 (b'pp1', [b'c', b'd']), 1755 (b'pp2', [b'c', b'd']), 1756 (b'pp3', [b'd']), 1757 ], self.calls) 1758