diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -125,7 +125,11 @@
     desc = '%d:%s "%s"' % (ctx.rev(), ctx,
                            ctx.description().split('\n', 1)[0])
     repo = ctx.repo()
-    names = repo.nodetags(ctx.node()) + repo.nodebookmarks(ctx.node())
+    names = []
+    for nsname, ns in repo.names.iteritems():
+        if nsname == 'branches':
+            continue
+        names.extend(ns.names(repo, ctx.node()))
     if names:
         desc += ' (%s)' % ' '.join(names)
     return desc
diff --git a/tests/test-bookmarks-rebase.t b/tests/test-bookmarks-rebase.t
--- a/tests/test-bookmarks-rebase.t
+++ b/tests/test-bookmarks-rebase.t
@@ -37,7 +37,7 @@
 rebase
 
   $ hg rebase -s two -d one
-  rebasing 3:2ae46b1d99a7 "3" (tip two)
+  rebasing 3:2ae46b1d99a7 "3" (two tip)
   saved backup bundle to $TESTTMP/.hg/strip-backup/2ae46b1d99a7-e6b057bc-rebase.hg (glob)
 
   $ hg log
@@ -77,7 +77,7 @@
   created new head
   $ hg bookmark three
   $ hg rebase -s three -d two
-  rebasing 4:dd7c838e8362 "4" (tip three)
+  rebasing 4:dd7c838e8362 "4" (three tip)
   merging d
   warning: conflicts while merging d! (edit, then use 'hg resolve --mark')
   unresolved conflicts (see hg resolve, then hg rebase --continue)
@@ -92,7 +92,7 @@
 after aborted rebase, restoring a bookmark that has been removed should not fail
 
   $ hg rebase -s three -d two
-  rebasing 4:dd7c838e8362 "4" (tip three)
+  rebasing 4:dd7c838e8362 "4" (three tip)
   merging d
   warning: conflicts while merging d! (edit, then use 'hg resolve --mark')
   unresolved conflicts (see hg resolve, then hg rebase --continue)
diff --git a/tests/test-rebase-abort.t b/tests/test-rebase-abort.t
--- a/tests/test-rebase-abort.t
+++ b/tests/test-rebase-abort.t
@@ -266,7 +266,7 @@
   
 
   $ hg rebase -d master -r foo
-  rebasing 3:6c0f977a22d8 "C" (tip foo)
+  rebasing 3:6c0f977a22d8 "C" (foo tip)
   merging c
   warning: conflicts while merging c! (edit, then use 'hg resolve --mark')
   unresolved conflicts (see hg resolve, then hg rebase --continue)
@@ -306,7 +306,7 @@
   created new head
 
   $ hg rebase -d @ -b foo --tool=internal:fail
-  rebasing 2:070cf4580bb5 "b2" (tip foo)
+  rebasing 2:070cf4580bb5 "b2" (foo tip)
   unresolved conflicts (see hg resolve, then hg rebase --continue)
   [1]
 
diff --git a/tests/test-rebase-bookmarks.t b/tests/test-rebase-bookmarks.t
--- a/tests/test-rebase-bookmarks.t
+++ b/tests/test-rebase-bookmarks.t
@@ -96,7 +96,7 @@
   $ hg book W@diverge
 
   $ hg rebase -s W -d .
-  rebasing 3:41acb9dca9eb "D" (tip W)
+  rebasing 3:41acb9dca9eb "D" (W tip)
   saved backup bundle to $TESTTMP/a4/.hg/strip-backup/41acb9dca9eb-b35a6a63-rebase.hg (glob)
 
   $ hg bookmarks
@@ -208,5 +208,5 @@
   $ hg rebase -r '"bisect"^^::"bisect"^' -r bisect -d Z
   rebasing 5:345c90f326a4 "bisect"
   rebasing 6:f677a2907404 "bisect2"
-  rebasing 7:325c16001345 "bisect3" (tip bisect)
+  rebasing 7:325c16001345 "bisect3" (bisect tip)
   saved backup bundle to $TESTTMP/a3/.hg/strip-backup/345c90f326a4-b4840586-rebase.hg (glob)
diff --git a/tests/test-rebase-collapse.t b/tests/test-rebase-collapse.t
--- a/tests/test-rebase-collapse.t
+++ b/tests/test-rebase-collapse.t
@@ -792,7 +792,7 @@
   $ hg book foo
   $ hg rebase -d 0 -r "1::2" --collapse -m collapsed
   rebasing 1:6d8d9f24eec3 "a"
-  rebasing 2:1cc73eca5ecc "b" (tip foo)
+  rebasing 2:1cc73eca5ecc "b" (foo tip)
   saved backup bundle to $TESTTMP/collapseaddremove/.hg/strip-backup/6d8d9f24eec3-77d3b6e2-rebase.hg (glob)
   $ hg log -G --template "{rev}: '{desc}' {bookmarks}"
   @  1: 'collapsed' foo
diff --git a/tests/test-rebase-emptycommit.t b/tests/test-rebase-emptycommit.t
--- a/tests/test-rebase-emptycommit.t
+++ b/tests/test-rebase-emptycommit.t
@@ -77,12 +77,12 @@
 "BOOK-D", and "BOOK-E" include changes introduced by "C".
 
   $ hg rebase -s 2 -d E
-  rebasing 2:dc0947a82db8 "C" (C BOOK-C)
+  rebasing 2:dc0947a82db8 "C" (BOOK-C C)
   rebasing 3:e7b3f00ed42e "D" (BOOK-D)
   note: rebase of 3:e7b3f00ed42e created no changes to commit
   rebasing 4:69a34c08022a "E" (BOOK-E)
   note: rebase of 4:69a34c08022a created no changes to commit
-  rebasing 5:6b2aeab91270 "F" (F BOOK-F)
+  rebasing 5:6b2aeab91270 "F" (BOOK-F F)
   saved backup bundle to $TESTTMP/non-merge/.hg/strip-backup/dc0947a82db8-52bb4973-rebase.hg (glob)
   $ hg log -G -T '{rev} {desc} {bookmarks}'
   o  5 F BOOK-F
@@ -129,7 +129,7 @@
   note: rebase of 2:dc0947a82db8 created no changes to commit
   rebasing 3:b18e25de2cf5 "D" (BOOK-D)
   note: rebase of 3:b18e25de2cf5 created no changes to commit
-  rebasing 4:86a1f6686812 "E" (E BOOK-E)
+  rebasing 4:86a1f6686812 "E" (BOOK-E E)
   note: rebase of 4:86a1f6686812 created no changes to commit
   saved backup bundle to $TESTTMP/merge1/.hg/strip-backup/b18e25de2cf5-1fd0a4ba-rebase.hg (glob)
 
@@ -176,11 +176,11 @@
   $ hg rebase -r '(A::)-(B::)-A' -d H
   rebasing 2:dc0947a82db8 "C" (BOOK-C)
   note: rebase of 2:dc0947a82db8 created no changes to commit
-  rebasing 3:b18e25de2cf5 "D" (D BOOK-D)
-  rebasing 4:03ca77807e91 "E" (E BOOK-E)
+  rebasing 3:b18e25de2cf5 "D" (BOOK-D D)
+  rebasing 4:03ca77807e91 "E" (BOOK-E E)
   rebasing 5:ad6717a6a58e "F" (BOOK-F)
   note: rebase of 5:ad6717a6a58e created no changes to commit
-  rebasing 6:c58e8bdac1f4 "G" (G BOOK-G)
+  rebasing 6:c58e8bdac1f4 "G" (BOOK-G G)
   saved backup bundle to $TESTTMP/merge2/.hg/strip-backup/b18e25de2cf5-2d487005-rebase.hg (glob)
 
   $ hg log -G -T '{rev} {desc} {bookmarks}'
diff --git a/tests/test-rebase-obsolete.t b/tests/test-rebase-obsolete.t
--- a/tests/test-rebase-obsolete.t
+++ b/tests/test-rebase-obsolete.t
@@ -1251,7 +1251,7 @@
   $ hg bookmark book -i
   $ hg rebase -r B+D1 -d E
   rebasing 1:112478962961 "B" (B)
-  note: not rebasing 5:15ecf15e0114 "D1" (D1 tip book), already in destination as 2:0807738e0be9 "D2" (D2)
+  note: not rebasing 5:15ecf15e0114 "D1" (book D1 tip), already in destination as 2:0807738e0be9 "D2" (D2)
   $ hg log -G -T '{desc} {bookmarks}'
   @  B book
   |