upstream/mercurial-mirror Files · mercurial/ancestor.py

hg qrecord -- like record, but for mq...

hg qrecord -- like record, but for mq I'm a former Darcs user, and I've discovered that it is very convenient to actually perform development using MQ first, and only when the patches are 'ready' move them to project's history in stone. Usually I work on some topic, temporarily forgetting about any version control, and just do coding, experimenting, debugging, etc. After some time, I approach a moment, where my work should actually go to patches/commits, and here is the problem:: As it is now, there is no way to put part of the changes into one patch, and another part of the changes into second patch. This works, but only when changes are touching separate files, and for semantically different changes touching the same file(s) there is now pretty way to put them into separate patches. For some time, I've tolerated the pain to run vim patches/... and move hunks between files by hand, but I think this affects my productivity badly. So, here is the first step towards untiing the problem: Let's use 'hg qrecord' for mq, like we use 'hg record' for usual commits!

Thomas Arendsen Hein - - Load All Authors

File last commit:

r3673:eb0b4a2d default


                r5830:c32d41af

default

Download file

             ancestor.py
        
                    83 lines
            
             | 2.2 KiB
            
                | text/x-python
            
             |
                PythonLexer
            
             / mercurial / ancestor.py
          
                    History
                
                 |
                  Annotation
                 | Raw
                 |Copy content
                 |Copy permalink

      # ancestor.py - generic DAG ancestor algorithm for mercurial

      #

      # Copyright 2006 Matt Mackall <mpm@selenic.com>

      #

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

      # of the GNU General Public License, incorporated herein by reference.

      import heapq

      def ancestor(a, b, pfunc):

          """

          return the least common ancestor of nodes a and b or None if there

          is no such ancestor.

          pfunc must return a list of parent vertices

          """

          if a == b:

              return a

          # find depth from root of all ancestors

          visit = [a, b]

          depth = {}

          while visit:

              vertex = visit[-1]

              pl = pfunc(vertex)

              if not pl:

                  depth[vertex] = 0

                  visit.pop()

              else:

                  for p in pl:

                      if p == a or p == b: # did we find a or b as a parent?

                          return p # we're done

                      if p not in depth:

                          visit.append(p)

                  if visit[-1] == vertex:

                      depth[vertex] = min([depth[p] for p in pl]) - 1

                      visit.pop()

          # traverse ancestors in order of decreasing distance from root

          def ancestors(vertex):

              h = [(depth[vertex], vertex)]

              seen = {}

              while h:

                  d, n = heapq.heappop(h)

                  if n not in seen:

                      seen[n] = 1

                      yield (d, n)

                      for p in pfunc(n):

                          heapq.heappush(h, (depth[p], p))

          def generations(vertex):

              sg, s = None, {}

              for g, v in ancestors(vertex):

                  if g != sg:

                      if sg:

                          yield sg, s

                      sg, s = g, {v:1}

                  else:

                      s[v] = 1

              yield sg, s

          x = generations(a)

          y = generations(b)

          gx = x.next()

          gy = y.next()

          # increment each ancestor list until it is closer to root than

          # the other, or they match

          try:

              while 1:

                  if gx[0] == gy[0]:

                      for v in gx[1]:

                          if v in gy[1]:

                              return v

                      gy = y.next()

                      gx = x.next()

                  elif gx[0] > gy[0]:

                      gy = y.next()

                  else:

                      gx = x.next()

          except StopIteration:

              return None

	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

				# ancestor.py - generic DAG ancestor algorithm for mercurial
				#
				# Copyright 2006 Matt Mackall <mpm@selenic.com>
				#
				# This software may be used and distributed according to the terms
				# of the GNU General Public License, incorporated herein by reference.

				import heapq

				def ancestor(a, b, pfunc):
				"""
				return the least common ancestor of nodes a and b or None if there
				is no such ancestor.

				pfunc must return a list of parent vertices
				"""

				if a == b:
				return a

				# find depth from root of all ancestors
				visit = [a, b]
				depth = {}
				while visit:
				vertex = visit[-1]
				pl = pfunc(vertex)
				if not pl:
				depth[vertex] = 0
				visit.pop()
				else:
				for p in pl:
				if p == a or p == b: # did we find a or b as a parent?
				return p # we're done
				if p not in depth:
				visit.append(p)
				if visit[-1] == vertex:
				depth[vertex] = min([depth[p] for p in pl]) - 1
				visit.pop()

				# traverse ancestors in order of decreasing distance from root
				def ancestors(vertex):
				h = [(depth[vertex], vertex)]
				seen = {}
				while h:
				d, n = heapq.heappop(h)
				if n not in seen:
				seen[n] = 1
				yield (d, n)
				for p in pfunc(n):
				heapq.heappush(h, (depth[p], p))

				def generations(vertex):
				sg, s = None, {}
				for g, v in ancestors(vertex):
				if g != sg:
				if sg:
				yield sg, s
				sg, s = g, {v:1}
				else:
				s[v] = 1
				yield sg, s

				x = generations(a)
				y = generations(b)
				gx = x.next()
				gy = y.next()

				# increment each ancestor list until it is closer to root than
				# the other, or they match
				try:
				while 1:
				if gx[0] == gy[0]:
				for v in gx[1]:
				if v in gy[1]:
				return v
				gy = y.next()
				gx = x.next()
				elif gx[0] > gy[0]:
				gy = y.next()
				else:
				gx = x.next()
				except StopIteration:
				return None