hg convert hangs in toposort()

[Matt Mackall]

On Fri, 2008-02-08 at 14:23 +0000, Frank Kingswood wrote:
> Hallo!
> 
> I'm experiencing hangs in converting a CVS tree, in calls to toposort(), 
> in particular the while loop which starts at line 129 in
> http://hg.intevation.org/mercurial/crew-stable/file/6605a03cbf87/hgext/convert/convcmd.py
> 
> The state alternates between
> visit=['3', '4']
> removed={'1': 1, '2': 1, '5': 1, '7': 1, '6': 1, '9': 1, '8': 1} 
> parents={'1': [], '3': ['3'], '2': ['1'], '5': ['1'], '4': ['3'], '7': 
> ['6'], '6': ['5'], '9': ['8'], '8': ['7']}
> self.map={}
> 
> and
> 
> visit=['4', '3']
> 
> (with the other variables unchanged).
> 
> It is not entirely clear to me what the expected behaviour of toposort 
> is, can anyone shed any light on this problem?

It's a "topological sort". If we have a directed graph with no loops,
there are one or more orderings of elements where all parents come
before their children and this finds one of them.

For some reason the data passed to toposort has a loop (3 is its own
parent!), so it gets upset. There may be a way to add some loop
detection here, but as Alexis point out, the real problem is further up.

-- 
Mathematics is the supreme nostalgia of our time.