upstream/mercurial-mirror Files · mercurial/thirdparty/zope/interface/ro.py

phases: large rewrite on retract boundary...

phases: large rewrite on retract boundary The new code is still pure Python, so we still have room to going significantly faster. However its complexity of the complex part is `O(|[min_new_draft, tip]|)` instead of `O(|[min_draft, tip]|` which should help tremendously one repository with old draft (like mercurial-devel or mozilla-try). This is especially useful as the most common "retract boundary" operation happens when we commit/rewrite new drafts or when we push new draft to a non-publishing server. In this case, the smallest new_revs is very close to the tip and there is very few work to do. A few smaller optimisation could be done for these cases and will be introduced in later changesets. We still have iterate over large sets of roots, but this is already a great improvement for a very small amount of work. We gather information on the affected changeset as we go as we can put it to use in the next changesets. This extra data collection might slowdown the `register_new` case a bit, however for register_new, it should not really matters. The set of new nodes is either small, so the impact is negligible, or the set of new nodes is large, and the amount of work to do to had them will dominate the overhead the collecting information in `changed_revs`. As this new code compute the changes on the fly, it unlock other interesting improvement to be done in later changeset.

Gregory Szorc - - Load All Authors

File last commit:

r37195:68ee6182 default


                r52302:2f39c7ae

default

Download file

             ro.py
        
                    67 lines
            
             | 2.0 KiB
            
                | text/x-python
            
             |
                PythonLexer
            
             / mercurial / thirdparty / zope / interface / ro.py
          
                    History
                
                 |
                  Annotation
                 | Raw
                 |Copy content
                 |Copy permalink

      ##############################################################################

      #

      # Copyright (c) 2003 Zope Foundation and Contributors.

      # All Rights Reserved.

      #

      # This software is subject to the provisions of the Zope Public License,

      # Version 2.1 (ZPL).  A copy of the ZPL should accompany this distribution.

      # THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED

      # WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

      # WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS

      # FOR A PARTICULAR PURPOSE.

      #

      ##############################################################################

      """Compute a resolution order for an object and its bases

      """

      from __future__ import absolute_import

      __docformat__ = 'restructuredtext'

      def _mergeOrderings(orderings):

          """Merge multiple orderings so that within-ordering order is preserved

          Orderings are constrained in such a way that if an object appears

          in two or more orderings, then the suffix that begins with the

          object must be in both orderings.

          For example:

          >>> _mergeOrderings([

          ... ['x', 'y', 'z'],

          ... ['q', 'z'],

          ... [1, 3, 5],

          ... ['z']

          ... ])

          ['x', 'y', 'q', 1, 3, 5, 'z']

          """

          seen = {}

          result = []

          for ordering in reversed(orderings):

              for o in reversed(ordering):

                  if o not in seen:

                      seen[o] = 1

                      result.insert(0, o)

          return result

      def _flatten(ob):

          result = [ob]

          i = 0

          for ob in iter(result):

              i += 1

              # The recursive calls can be avoided by inserting the base classes

              # into the dynamically growing list directly after the currently

              # considered object;  the iterator makes sure this will keep working

              # in the future, since it cannot rely on the length of the list

              # by definition.

              result[i:i] = ob.__bases__

          return result

      def ro(object):

          """Compute a "resolution order" for an object

          """

          return _mergeOrderings([_flatten(object)])

	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

				##############################################################################
				#
				# Copyright (c) 2003 Zope Foundation and Contributors.
				# All Rights Reserved.
				#
				# This software is subject to the provisions of the Zope Public License,
				# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
				# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
				# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
				# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
				# FOR A PARTICULAR PURPOSE.
				#
				##############################################################################
				"""Compute a resolution order for an object and its bases
				"""

				from __future__ import absolute_import

				__docformat__ = 'restructuredtext'

				def _mergeOrderings(orderings):
				"""Merge multiple orderings so that within-ordering order is preserved

				Orderings are constrained in such a way that if an object appears
				in two or more orderings, then the suffix that begins with the
				object must be in both orderings.

				For example:

				>>> _mergeOrderings([
				... ['x', 'y', 'z'],
				... ['q', 'z'],
				... [1, 3, 5],
				... ['z']
				... ])
				['x', 'y', 'q', 1, 3, 5, 'z']

				"""

				seen = {}
				result = []
				for ordering in reversed(orderings):
				for o in reversed(ordering):
				if o not in seen:
				seen[o] = 1
				result.insert(0, o)

				return result

				def _flatten(ob):
				result = [ob]
				i = 0
				for ob in iter(result):
				i += 1
				# The recursive calls can be avoided by inserting the base classes
				# into the dynamically growing list directly after the currently
				# considered object; the iterator makes sure this will keep working
				# in the future, since it cannot rely on the length of the list
				# by definition.
				result[i:i] = ob.__bases__
				return result


				def ro(object):
				"""Compute a "resolution order" for an object
				"""
				return _mergeOrderings([_flatten(object)])