Graph.find_differences() is confused by shortcuts

Bug #187452 reported by John A Meinel
2
Affects Status Importance Assigned to Milestone
Bazaar
Confirmed
Medium
Unassigned
Breezy
Triaged
Medium
Unassigned

Bug Description

At the moment, find_differences() implements a naive search that can easily get confused by shortcuts.

For example, with:
# NULL_REVISION
# |
# a
# |
# b
# |
# c
# |
# d
# |\
# e f
# | |\
# i | h
# |\| |
# | g |
# | | |
# | j |
# | | |
# | k |
# | | |
# | l |
# |/|/
# m n

It will find 'k' as a common node, and won't continue and find that 'f' is actually not unique to 'n', but is actually also common.

There is work which has been done towards this end, but at the moment it does not perform well on the bzr graph (presumably it is too pessimistic about when it can stop searching common nodes.)
this is slightly related to bug #165307.

I will associate my branch with this bug.

Tags: graph
John A Meinel (jameinel)
Changed in bzr:
importance: Undecided → Medium
status: New → Triaged
Martin Pool (mbp)
Changed in bzr:
status: Triaged → Confirmed
Jelmer Vernooij (jelmer)
tags: added: graph
Jelmer Vernooij (jelmer)
tags: added: check-for-breezy
Jelmer Vernooij (jelmer)
tags: removed: check-for-breezy
Changed in brz:
status: New → Triaged
importance: Undecided → Medium
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.