← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: John Arbash Meinel
  • Date: 2008-04-23 20:33:41 UTC
  • mto: This revision was merged to the branch mainline in revision 3407.
  • Revision ID: john@arbash-meinel.com-20080423203341-4qlndx8u2zu21yz0
Change _search_for_extra_common slightly.

The official statement is that you can stop searching common nodes
once all common tips are ancestors of *all* unique nodes.
We need to make sure that we stop the common searchers once
they find nodes that are ancestors, and then we can only
exit the common search loop when they have finished.

All tests pass, need to see if it is still 'efficient'.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
205
205
#     |
206
206
#     d
207
207
#     |\
208
 
#     e f
 
208
#     e |
 
209
#     | |
 
210
#     f |
 
211
#     | |
 
212
#     g h
209
213
#     | |\
210
 
#     i | h
 
214
#     i | j
211
215
#     |\| |
212
 
#     | g |
213
 
#     | | |
214
 
#     | j |
215
 
#     | | |
216
216
#     | k |
217
217
#     | | |
218
218
#     | l |
 
219
#     | | |
 
220
#     | m |
 
221
#     | | |
 
222
#     | n |
 
223
#     | | |
 
224
#     | o |
 
225
#     | | |
 
226
#     | p |
 
227
#     | | |
 
228
#     | q |
 
229
#     | | |
 
230
#     | r |
 
231
#     | | |
 
232
#     | s |
 
233
#     | | |
219
234
#     |/|/
220
 
#     m n
221
 
complex_shortcut2 = {'d':[NULL_REVISION],
222
 
                    'x':['d'], 'y':['x'],
223
 
                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
224
 
                    'i':['e'], 'j':['g'], 'k':['j'],
225
 
                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
226
 
                    'o':['l'], 'p':['o'], 'q':['p'],
 
235
#     t u
 
236
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
237
                    'e':['d'], 'f':['e'],
 
238
                    'g':['f'], 'h':['d'], 'k':['h', 'i'], 'j':['h'],
 
239
                    'i':['g'], 'l':['k'], 'm':['l'],
 
240
                    'n':['m'], 't':['i', 's'], 'u':['s', 'j'],
 
241
                    'o':['n'], 'p':['o'], 'q':['p'],
227
242
                    'r':['q'], 's':['r'],
228
243
                    }
229
244
 
505
520
 
506
521
    def test_graph_difference_complex_shortcut2(self):
507
522
        graph = self.make_graph(complex_shortcut2)
508
 
        self.assertEqual((set(['m']), set(['h', 'n'])),
509
 
                         graph.find_difference('m', 'n'))
 
523
        self.assertEqual((set(['t']), set(['j', 'u'])),
 
524
                         graph.find_difference('t', 'u'))
510
525
 
511
526
    def test_graph_difference_shortcut_extra_root(self):
512
527
        graph = self.make_graph(shortcut_extra_root)