fix for a keyerror in finding least common ancestors

[Michael Hudson]

Aaron Bentley wrote:
> Michael Hudson wrote:
>> I have an branch of launchpad with pretty complicated merge history.
>> Attempting to merge a particular revision of launchpad head into it
>> yields an exception like:
> 
>> Traceback (most recent call last):
>>   File "/home/mwh/bzr/bzrlib/commands.py", line 729, in run_bzr_catch_errors
>>     return run_bzr(argv)
>>   File "/home/mwh/bzr/bzrlib/commands.py", line 691, in run_bzr
>>     ret = run(*run_argv)
>>   File "/home/mwh/bzr/bzrlib/commands.py", line 389, in run_argv_aliases
>>     return self.run(**all_cmd_args)
>>   File "/home/mwh/bzr/bzrlib/builtins.py", line 2709, in run
>>     change_reporter=change_reporter)
>>   File "/home/mwh/bzr/bzrlib/builtins.py", line 3724, in _merge_helper
>>     merger.set_base(base_revision)
>>   File "/home/mwh/bzr/bzrlib/merge.py", line 268, in set_base
>>     self.base_rev_id = graph.find_unique_lca(*revisions)
>>   File "/home/mwh/bzr/bzrlib/graph.py", line 279, in find_unique_lca
>>     lca = self.find_lca(*revisions)
>>   File "/home/mwh/bzr/bzrlib/graph.py", line 140, in find_lca
>>     return self._filter_candidate_lca(border_common)
>>   File "/home/mwh/bzr/bzrlib/graph.py", line 244, in _filter_candidate_lca
>>     del active_searchers[candidate]
>> KeyError: 'pqm at pqm.ubuntu.com-20070712051010-4o5ij0wgrvhvdf0o'
> 
>> I think the most obvious fix (attached) is actually the right fix (it's
>> not at all obvious to me that the candidate being deleted here hasn't
>> already been deleted by line 249).
> 
> I don't agree.  There's only one place that deletes an active searcher:
> line 249.  'candidate' is a key in the active_searchers dictionary, so
> there can't be two entries for
> 'pqm at pqm.ubuntu.com-20070712051010-4o5ij0wgrvhvdf0o'.
> 
> It's obvious to me that if we are walking through active_searchers, and
> we hit a StopIteration, then candidate must be present in
> active_searchers.

But the iteration is through a listified version of active_searchers, so
there's no reason that because candidate was once in active_searchers,
it still is.  Or am I missing something?

> The fact that this can fail suggests a deeper logic
> bug, and I don't want to apply a band-aid.  I want to understand and
> solve the problem.

Sure.

>> In a half an hour of trying, I
>> haven't been able to make a test case
> 
> That's a shame, and considering it's Launchpad, I can't just download it
> myself to reproduce.

Yes :/

>> , but that's not surprising as I
>> spent most of that time trying to understand the terminology of this file...

I lied a bit here, I also spent quite some time trying to work out what
was going on in this branch of ours -- it really does have a pretty
crazy merge history.

> I'm not really familiar with graph theory terminology.  I'd appreciate
> any suggestions you can offer, and I'm also happy to explain everything
> in the file already.

I don't either.  I just glanced at a few papers after googling some
likely terms, but the papers I found were all solving the problem in a
rather different way (we show how to answer the LCA problem in constant
time given O(n**2.7) steps of preprocessing...)

Cheers,
wmh