--- a/hgext/shelve.py	Sat May 16 09:03:21 2015 +0200
+++ b/hgext/shelve.py	Sat May 16 11:28:04 2015 -0700
@@ -21,6 +21,7 @@
 shelve".
 """
 
+import collections
 from mercurial.i18n import _
 from mercurial.node import nullid, nullrev, bin, hex
 from mercurial import changegroup, cmdutil, scmutil, phases, commands
@@ -143,7 +144,7 @@
 
         Much faster than the revset ancestors(ctx) & draft()"""
         seen = set([nullrev])
-        visit = util.deque()
+        visit = collections.deque()
         visit.append(ctx)
         while visit:
             ctx = visit.popleft()

--- a/mercurial/ancestor.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/ancestor.py	Sat May 16 11:28:04 2015 -0700
@@ -5,8 +5,8 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
+import collections
 import heapq
-import util
 from node import nullrev
 
 def commonancestorsheads(pfunc, *nodes):
@@ -314,7 +314,7 @@
 
         parentrevs = self._parentrevs
         stoprev = self._stoprev
-        visit = util.deque(revs)
+        visit = collections.deque(revs)
 
         while visit:
             for parent in parentrevs(visit.popleft()):

--- a/mercurial/hbisect.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/hbisect.py	Sat May 16 11:28:04 2015 -0700
@@ -8,6 +8,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
+import collections
 import os
 import error
 from i18n import _
@@ -71,7 +72,7 @@
 
     # build children dict
     children = {}
-    visit = util.deque([badrev])
+    visit = collections.deque([badrev])
     candidates = []
     while visit:
         rev = visit.popleft()

--- a/mercurial/patch.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/patch.py	Sat May 16 11:28:04 2015 -0700
@@ -6,6 +6,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
+import collections
 import cStringIO, email, os, errno, re, posixpath, copy
 import tempfile, zlib, shutil
 # On python2.4 you have to import these by name or they fail to
@@ -2102,7 +2103,7 @@
 
     def lrugetfilectx():
         cache = {}
-        order = util.deque()
+        order = collections.deque()
         def getfilectx(f, ctx):
             fctx = ctx.filectx(f, filelog=cache.get(f))
             if f not in cache:

--- a/mercurial/revlog.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/revlog.py	Sat May 16 11:28:04 2015 -0700
@@ -12,6 +12,7 @@
 """
 
 # import stuff from node for others to import from revlog
+import collections
 from node import bin, hex, nullid, nullrev
 from i18n import _
 import ancestor, mdiff, parsers, error, util, templatefilters
@@ -485,7 +486,7 @@
 
         # take all ancestors from heads that aren't in has
         missing = set()
-        visit = util.deque(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.popleft()
             if r in missing:

--- a/mercurial/setdiscovery.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/setdiscovery.py	Sat May 16 11:28:04 2015 -0700
@@ -40,6 +40,7 @@
 classified with it (since all ancestors or descendants will be marked as well).
 """
 
+import collections
 from node import nullid, nullrev
 from i18n import _
 import random
@@ -65,7 +66,7 @@
     else:
         heads = dag.heads()
     dist = {}
-    visit = util.deque(heads)
+    visit = collections.deque(heads)
     seen = set()
     factor = 1
     while visit:

--- a/mercurial/treediscovery.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/treediscovery.py	Sat May 16 11:28:04 2015 -0700
@@ -5,6 +5,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
+import collections
 from node import nullid, short
 from i18n import _
 import util, error
@@ -56,7 +57,7 @@
     # 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 = util.deque(remote.branches(unknown))
+    unknown = collections.deque(remote.branches(unknown))
     while unknown:
         r = []
         while unknown:

--- a/mercurial/util.py	Sat May 16 09:03:21 2015 +0200
+++ b/mercurial/util.py	Sat May 16 11:28:04 2015 -0700
@@ -334,8 +334,6 @@
 
     return f
 
-deque = collections.deque
-
 class sortdict(dict):
     '''a simple sorted dictionary'''
     def __init__(self, data=None):
@@ -386,7 +384,7 @@
     def __init__(self, maxsize):
         self._cache = {}
         self._maxsize = maxsize
-        self._order = deque()
+        self._order = collections.deque()
 
     def __getitem__(self, key):
         value = self._cache[key]
@@ -408,12 +406,12 @@
 
     def clear(self):
         self._cache.clear()
-        self._order = deque()
+        self._order = collections.deque()
 
 def lrucachefunc(func):
     '''cache most recent results of function calls'''
     cache = {}
-    order = deque()
+    order = collections.deque()
     if func.func_code.co_argcount == 1:
         def f(arg):
             if arg not in cache:
@@ -1191,7 +1189,7 @@
                 else:
                     yield chunk
         self.iter = splitbig(in_iter)
-        self._queue = deque()
+        self._queue = collections.deque()
 
     def read(self, l=None):
         """Read L bytes of data from the iterator of chunks of data.