'pop(): dictionary is empty' in tsort when showing pending merges

[David I]

See the following log. As you can see bzr check is happy but bzr status crashes.
All run on an Ubuntu Gutsy machine with bzr 1.5.
Nothing odd apparent in the .bzrignore file.
Other branches from same mother repository are OK.
The problem repos has had 2 bzr pulls run on it.

msdes002:~/projects/CVTOOL_Sting_1.0_000945$ bzr check
checked branch file:///data/users/david.ingamells/projects/CVTOOL_Sting_1.0_000945/ format Bazaar Branch Format 6 (bzr 0.15)
checked repository <bzrlib.transport.local.LocalTransport url=file:///data/users/david.ingamells/projects/CVTOOL_Sting_1.0_000945/> format <RepositoryFormatKnit1>
  3611 revisions
  2707 file-ids
 28847 unique file texts
4772621 repeated file texts
     0 unreferenced text versions

msdes002:~/projects/CVTOOL_Sting_1.0_000945$ bzr status
pending merges:
  David Ingamells 2008-05-26 Task: 928
bzr: ERROR: exceptions.KeyError: 'pop(): dictionary is empty'

Traceback (most recent call last):
  File "/usr/lib/python2.5/site-packages/bzrlib/commands.py", line 846, in run_bzr_catch_errors
    return run_bzr(argv)
  File "/usr/lib/python2.5/site-packages/bzrlib/commands.py", line 797, in run_bzr
    ret = run(*run_argv)
  File "/usr/lib/python2.5/site-packages/bzrlib/commands.py", line 499, in run_argv_aliases
    return self.run(**all_cmd_args)
  File "/usr/lib/python2.5/site-packages/bzrlib/commands.py", line 807, in ignore_pipe
    result = func(*args, **kwargs)
  File "/usr/lib/python2.5/site-packages/bzrlib/builtins.py", line 178, in run
    show_pending=not no_pending)
  File "/usr/lib/python2.5/site-packages/bzrlib/status.py", line 142, in show_tree_status
    show_pending_merges(new, to_file, short)
  File "/usr/lib/python2.5/site-packages/bzrlib/status.py", line 235, in show_pending_merges
    branch.repository.get_parent_map(merge_extra))
  File "/usr/lib/python2.5/site-packages/bzrlib/status.py", line 172, in _get_sorted_revisions
    sorter = tsort.MergeSorter(parent_graph, tip_revision)
  File "/usr/lib/python2.5/site-packages/bzrlib/tsort.py", line 412, in __init__
    parents = self._graph.pop(branch_tip)
KeyError: 'pop(): dictionary is empty'

bzr 1.5 on python 2.5.1 (linux2)
arguments: ['/usr/bin/bzr', 'status']
encoding: 'UTF-8', fsenc: 'UTF-8', lang: 'en_GB.UTF-8'
plugins:
  bzrtools /usr/lib/python2.5/site-packages/bzrlib/plugins/bzrtools [1.5.0]
  gtk /usr/lib/python2.5/site-packages/bzrlib/plugins/gtk [0.93.0]
  launchpad /usr/lib/python2.5/site-packages/bzrlib/plugins/launchpad [unknown]
*** Bazaar has encountered an internal error.
    Please report a bug at https://bugs.launchpad.net/bzr/+filebug
    including this traceback, and a description of what you
    were doing when the error occurred.

[Martin Pool (mbp)]

Do you remember what merges or pulls or other operations you did in this working tree leading up to this problem?

Thanks for the report.

[Frits Jalvingh (fjalvingh)]

I just had the same problem.. I'm building a Java variant of Bundle Buggy and was using a test repository and silly fixes on it to test an automatic merge/build/create-binary-fix process. During this test I caused the SAME merge directive (as created by bzr send) to be merged twice. The merges were applied with --force on a clean tree. The resulting tree causes the problem.

To reproduce:
use a base branch, say ~/base

bzr branch ~/base ~/hack
cd ~/hack
(edit, edit, commit, commit)
bzr send -o ~/my-hacks.patch

Now merge 2ce:
bzr branch ~/base ~/test
cd ~/test
bzr merge ~/my-hacks.patch
bzr merge --force ~/my-hacks.patch

Both merges complete succesfully, but after this the above error occurs and both status and commit fail.

[John A Meinel (jameinel)]

You don't need a merge directive to reproduce this. double merging will do it

bzr init X
bzr commit --unchanged -m 1 X
bzr branch X Y
bzr commit --unchanged -m 2 Y
cd X
bzr merge ../Y
bzr merge --force ../Y

Arguably, merge should refuse to mark the entry as a new merge if it is in the ancestry of the existing merges. (So that doing bzr merge ../Y; bzr merge --force -r 1 ../Y doesn't work)

Anyway, I'll make a quick fix to 'bzr status' to still allow this, but really it seems like something 'merge' might be doing wrong.

[John A Meinel (jameinel)]

Fix available in associated branch

[Robert Collins (lifeless)]

On Fri, 2008-05-30 at 22:27 +0000, John A Meinel wrote:
> You don't need a merge directive to reproduce this. double merging will
> do it
>
> bzr init X
> bzr commit --unchanged -m 1 X
> bzr branch X Y
> bzr commit --unchanged -m 2 Y
> cd X
> bzr merge ../Y
> bzr merge --force ../Y
>
> Arguably, merge should refuse to mark the entry as a new merge if it is
> in the ancestry of the existing merges. (So that doing bzr merge ../Y;
> bzr merge --force -r 1 ../Y doesn't work)
>
> Anyway, I'll make a quick fix to 'bzr status' to still allow this, but
> really it seems like something 'merge' might be doing wrong.

there are tests that low level functions reduce duplicates by history,
so yes, soething is wrong.

-Rob
--
GPG key available at: <http://www.robertcollins.net/keys.txt>.

[Martin Pool (mbp)]

David, can I check whether you also used merge --force leading up to this?

David/Frits: why did you use merge --force? Was there some other operation that needed to be forced, or was it giving you an error before, or do you just do it out of habit?

[John A Meinel (jameinel)]

Merged into bzr.dev 3472

We decided that the merge should not be setting the pending parent. Though it seems a reasonable number of tests did expect that behavior.

[ChriS (christophe-troestler)]

I have a similar kind of error with bzr.dev (revision 3515). With the attached .bzr/, "bzr st" returns:

removed:
  .bzrignore
  Gaussienne.ml
  Pi.ml
pending merges:
  Pierre Brukier 2008-04-27 Generation d'une gaussienne par nombres uniforme...
bzr: ERROR: exceptions.KeyError: 'pop(): dictionary is empty'

Traceback (most recent call last):
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/commands.py", line 846, in run_bzr_catch_errors
    return run_bzr(argv)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/commands.py", line 797, in run_bzr
    ret = run(*run_argv)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/commands.py", line 499, in run_argv_aliases
    return self.run(**all_cmd_args)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/commands.py", line 807, in ignore_pipe
    result = func(*args, **kwargs)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/builtins.py", line 178, in run
    show_pending=not no_pending)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/status.py", line 142, in show_tree_status
    show_pending_merges(new, to_file, short)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/status.py", line 235, in show_pending_merges
    branch.repository.get_parent_map(merge_extra))
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/status.py", line 172, in _get_sorted_revisions
    sorter = tsort.MergeSorter(parent_graph, tip_revision)
  File "/home/devel/bzr/status_double_pending_235407/bzrlib/tsort.py", line 412, in __init__
    parents = self._graph.pop(branch_tip)
KeyError: 'pop(): dictionary is empty'

bzr 1.6b2 on python 2.5.2 (linux2)
arguments: ['/home/devel/bzr/status_double_pending_235407/bzr', 'st']
encoding: 'ISO-8859-1', fsenc: 'ISO-8859-1', lang: 'en_US'
plugins:
  bzrtools /usr/lib/python2.5/site-packages/bzrlib/plugins/bzrtools [1.5.0]
  gtk /usr/lib/python2.5/site-packages/bzrlib/plugins/gtk [0.94.0]
  launchpad /home/devel/bzr/status_double_pending_235407/bzrlib/plugins/launchpad [unknown]
  rebase /usr/lib/python2.5/site-packages/bzrlib/plugins/rebase [0.3.0]

[John A Meinel (jameinel)]

So this should only happen if you do "bzr merge --force", and merge something which has already been merged. In bzr.dev it should not set a new pending merge (since it is already present).

It will still fail during "bzr status" in a tree that was generated in the past. A simple "bzr revert && bzr merge ..." will re-do whatever merge you needed done.

[Patrick Dempster (paddydempster-deactivatedaccount)]

On Windows XP with bzr version 1.5. I get the following trace after moving two files with bzr mv while there where pending merges in the tree. Note I haven't been doing double merges or --force merges.

F:\working\matlab>bzr version
Bazaar (bzr) 1.5
  Python interpreter: F:\Program Files\Bazaar\python25.dll 2.5.2
  Python standard library: F:\Program Files\Bazaar\lib\library.zip
  bzrlib: F:\Program Files\Bazaar\lib\library.zip\bzrlib
  Bazaar configuration: F:\Documents and Settings\patrickd\Application Data\baza
ar\2.0
  Bazaar log file: F:\Documents and Settings\patrickd\My Documents\.bzr.log

F:\working\matlab>bzr status
renamed:
  NewSelectionFunctionRequirements => NewSelectionFunctionRequirements.txt
  ThesisGraphRequirements => ThesisGraphRequirements.txt
modified:
  ga/gaUsingNewRouting.m
  ga/routingAwareDamaged.m
  ga/setupRun_Start.m
unknown:
  ga/start.png
pending merges:
  Patrick Dempster 2008-07-09 testing the checkin in bzr
bzr: ERROR: exceptions.KeyError: 'pop(): dictionary is empty'

Traceback (most recent call last):
  File "bzrlib\commands.pyc", line 846, in run_bzr_catch_errors
  File "bzrlib\commands.pyc", line 797, in run_bzr
  File "bzrlib\commands.pyc", line 499, in run_argv_aliases
  File "bzrlib\commands.pyc", line 807, in ignore_pipe
  File "bzrlib\builtins.pyc", line 178, in run
  File "bzrlib\status.pyc", line 142, in show_tree_status
  File "bzrlib\status.pyc", line 235, in show_pending_merges
  File "bzrlib\status.pyc", line 172, in _get_sorted_revisions
  File "bzrlib\tsort.pyc", line 412, in __init__
KeyError: 'pop(): dictionary is empty'

bzr 1.5 on python 2.5.2 (win32)
arguments: ['bzr', 'status']
encoding: 'cp1252', fsenc: 'mbcs', lang: None
plugins:
  bzrtools F:\Documents and Settings\patrickd\Application Data\bazaa
r\2.0\plugins\bzrtools [1.5.0]
  launchpad F:\Program Files\Bazaar\plugins\launchpad [unknown]
  qbzr F:\Documents and Settings\patrickd\Application Data\bazaa
r\2.0\plugins\qbzr [0.9.0]

[John A Meinel (jameinel)]

It sounds like you merged something which was already in the ancestry of the branch, then. Which in newer bzr's also gets marked as a no-op.

I *do* see that you only have 1 merge, so it isn't the case of a double merge.

Can you try the attached patch?

Then again, I guess you are using the all-in-one install which makes trying patches difficult. 1.6 doesn't have this specific fix, because we chose to fix it at the "don't allow this situation to happen" rather than "handle this situation gracefully"

[John A Meinel (jameinel)]

The current workaround is to 'bzr revert' and re-do whatever merge got you into this situation. (As new bzr's won't let you get back into the same situation.)

The patch given should still apply, and should let 'bzr status' recover gracefully, but as we don't have a way to force the test-suite into that situation, we don't have a way to test it, and prevent it from bit-rotting.

[Daniel Clemente (n142857)]

Just for the archive: This testcase also reproduces the bug on Bazaar 1.5 with only 1 branch and 1 merge.
   mkdir bzr07; cd bzr07; bzr init; bzr commit --unchanged -m 1 .; bzr commit --unchanged -m 2 .; bzr commit --unchanged -m 3 .; bzr merge . --revision -3..-2; bzr status; cd ..

Bazaar 1.8dev from today works correctly and doesn't fail.

[Florian Konnertz (groovehunter72)]

I am not yet completely familiar with bzr
just encountered that error msg
simple revert and st again was fine.
But now checked out that branch again