cleanup: use the deque type where appropriate

There have been quite a few places where we pop elements off the
front of a list.  This can turn O(n) algorithms into something more
like O(n**2).  Python has provided a deque type that can do this
efficiently since at least 2.4.

As an example of the difference a deque can make, it improves
perfancestors performance on a Linux repo from 0.50 seconds to 0.36.

mercurial/hbisect.py

@@ -11,7 +11,7 b''
 import os, error
 from i18n import _
 from node import short, hex
-import util
+import collections, util
 
 def bisect(changelog, state):
     """find the next node (if any) for testing during a bisect search.
@@ -69,10 +69,10 b' def bisect(changelog, state):'
 
     # build children dict
     children = {}
-    visit = [badrev]
+    visit = collections.deque([badrev])
     candidates = []
     while visit:
-        rev = visit.pop(0)
+        rev = visit.popleft()
         if ancestors[rev] == []:
             candidates.append(rev)
             for prev in clparents(rev):

mercurial/patch.py

@@ -12,7 +12,7 b' import tempfile, zlib, shutil'
 from i18n import _
 from node import hex, nullid, short
 import base85, mdiff, scmutil, util, diffhelpers, copies, encoding, error
-import context
+import collections, context
 
 gitre = re.compile('diff --git a/(.*) b/(.*)')
 
@@ -1588,12 +1588,12 b' def diff(repo, node1=None, node2=None, m'
 
     def lrugetfilectx():
         cache = {}
-        order = []
+        order = collections.deque()
         def getfilectx(f, ctx):
             fctx = ctx.filectx(f, filelog=cache.get(f))
             if f not in cache:
                 if len(cache) > 20:
-                    del cache[order.pop(0)]
+                    del cache[order.popleft()]
                 cache[f] = fctx.filelog()
             else:
                 order.remove(f)

mercurial/revlog.py

@@ -15,7 +15,7 b' and O(changes) merge between branches.'
 from node import bin, hex, nullid, nullrev
 from i18n import _
 import ancestor, mdiff, parsers, error, util, dagutil
-import struct, zlib, errno
+import struct, zlib, errno, collections
 
 _pack = struct.pack
 _unpack = struct.unpack
@@ -362,13 +362,13 b' class revlog(object):'
         """return the set of all nodes ancestral to a given node, including
          the node itself, stopping when stop is matched"""
         reachable = set((node,))
-        visit = [node]
+        visit = collections.deque([node])
         if stop:
             stopn = self.rev(stop)
         else:
             stopn = 0
         while visit:
-            n = visit.pop(0)
+            n = visit.popleft()
             if n == stop:
                 continue
             if n == nullid:
@@ -389,10 +389,10 b' class revlog(object):'
         an ancestor of itself.  Results are in breadth-first order:
         parents of each rev in revs, then parents of those, etc.  Result
         does not include the null revision."""
-        visit = list(revs)
+        visit = collections.deque(revs)
         seen = set([nullrev])
         while visit:
-            for parent in self.parentrevs(visit.pop(0)):
+            for parent in self.parentrevs(visit.popleft()):
                 if parent not in seen:
                     visit.append(parent)
                     seen.add(parent)
@@ -447,9 +447,9 b' class revlog(object):'
 
         # take all ancestors from heads that aren't in has
         missing = set()
-        visit = [r for r in heads if r not in has]
+        visit = collections.deque(r for r in heads if r not in has)
         while visit:
-            r = visit.pop(0)
+            r = visit.popleft()
             if r in missing:
                 continue
             else:

mercurial/revset.py

@@ -5,7 +5,7 b''
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
-import re
+import re, collections
 import parser, util, error, discovery, hbisect, phases
 import node
 import bookmarks as bookmarksmod
@@ -17,10 +17,10 b' def _revancestors(repo, revs, followfirs'
     """Like revlog.ancestors(), but supports followfirst."""
     cut = followfirst and 1 or None
     cl = repo.changelog
-    visit = list(revs)
+    visit = collections.deque(revs)
     seen = set([node.nullrev])
     while visit:
-        for parent in cl.parentrevs(visit.pop(0))[:cut]:
+        for parent in cl.parentrevs(visit.popleft())[:cut]:
             if parent not in seen:
                 visit.append(parent)
                 seen.add(parent)

mercurial/treediscovery.py

@@ -7,7 +7,7 b''
 
 from node import nullid, short
 from i18n import _
-import util, error
+import util, error, collections
 
 def findcommonincoming(repo, remote, heads=None, force=False):
     """Return a tuple (common, fetch, heads) used to identify the common
@@ -56,11 +56,11 b' def findcommonincoming(repo, remote, hea'
     # a 'branch' here is a linear segment of history, with four parts:
     # head, root, first parent, second parent
     # (a branch always has two parents (or none) by definition)
-    unknown = remote.branches(unknown)
+    unknown = collections.deque(remote.branches(unknown))
     while unknown:
         r = []
         while unknown:
-            n = unknown.pop(0)
+            n = unknown.popleft()
             if n[0] in seen:
                 continue
 

mercurial/util.py

@@ -14,7 +14,7 b' hide platform-specific details from the '
 """
 
 from i18n import _
-import error, osutil, encoding
+import error, osutil, encoding, collections
 import errno, re, shutil, sys, tempfile, traceback
 import os, time, datetime, calendar, textwrap, signal
 import imp, socket, urllib
@@ -205,12 +205,12 b' def cachefunc(func):'
 def lrucachefunc(func):
     '''cache most recent results of function calls'''
     cache = {}
-    order = []
+    order = collections.deque()
     if func.func_code.co_argcount == 1:
         def f(arg):
             if arg not in cache:
                 if len(cache) > 20:
-                    del cache[order.pop(0)]
+                    del cache[order.popleft()]
                 cache[arg] = func(arg)
             else:
                 order.remove(arg)
@@ -220,7 +220,7 b' def lrucachefunc(func):'
         def f(*args):
             if args not in cache:
                 if len(cache) > 20:
-                    del cache[order.pop(0)]
+                    del cache[order.popleft()]
                 cache[args] = func(*args)
             else:
                 order.remove(args)
@@ -865,7 +865,7 b' class chunkbuffer(object):'
         Returns less than L bytes if the iterator runs dry."""
         left = l
         buf = ''
-        queue = self._queue
+        queue = collections.deque(self._queue)
         while left > 0:
             # refill the queue
             if not queue:
@@ -878,13 +878,14 b' class chunkbuffer(object):'
                 if not queue:
                     break
 
-            chunk = queue.pop(0)
+            chunk = queue.popleft()
             left -= len(chunk)
             if left < 0:
-                queue.insert(0, chunk[left:])
+                queue.appendleft(chunk[left:])
                 buf += chunk[:left]
             else:
                 buf += chunk
+        self._queue = list(queue)
 
         return buf