upstream/mercurial-mirror Files · mercurial/cffi/parsers.py

revset: add depth limit to descendants() (issue5374)...

revset: add depth limit to descendants() (issue5374) This is naive implementation using two-pass scanning. Tracking descendants isn't an easy problem if both start and stop depths are specified. It's impractical to remember all possible depths of each node while scanning from roots to descendants because the number of depths explodes. Instead, we could cache (min, max) depths as a good approximation and track ancestors back when needed, but that's likely to have off-by-one bug. Since this implementation appears not significantly slower, and is quite straightforward, I think it's good enough for practical use cases. The time and space complexity is O(n) ish. revisions: 0) 1-pass scanning with (min, max)-depth cache (worst-case quadratic) 1) 2-pass scanning (this version) repository: mozilla-central # descendants(0) (for reference) *) 0.430353 # descendants(0, depth=1000) 0) 0.264889 1) 0.398289 # descendants(limit(tip:0, 1, offset=10000), depth=1000) 0) 0.025478 1) 0.029099 # descendants(0, depth=2000, startdepth=1000) 0) painfully slow (due to quadratic backtracking of ancestors) 1) 1.531138

Yuya Nishihara - - Load All Authors

File last commit:

r32512:0e8b0b9a default


                r33080:a53bfc28

default

Download file

             parsers.py
        
                    10 lines
            
             | 318 B
            
                | text/x-python
            
             |
                PythonLexer
            
             / mercurial / cffi / parsers.py
          
                    History
                
                 |
                  Source
                 | Raw
                 |Copy content
                 |Copy permalink

        Yuya Nishihara
    
cffi: split modules from pure...

              r32512
            
      # parsers.py - Python implementation of parsers.c

      #

      # Copyright 2009 Matt Mackall <mpm@selenic.com> and others

      #

      # This software may be used and distributed according to the terms of the

      # GNU General Public License version 2 or any later version.

      from __future__ import absolute_import

      from ..pure.parsers import *

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

Yuya Nishihara cffi: split modules from pure...	r32512	# parsers.py - Python implementation of parsers.c
		#
		# Copyright 2009 Matt Mackall <mpm@selenic.com> and others
		#
		# This software may be used and distributed according to the terms of the
		# GNU General Public License version 2 or any later version.

		from __future__ import absolute_import

		from ..pure.parsers import *