Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/distlib/compat.py: 92%

1# -*- coding: utf-8 -*- 

2# 

3# Copyright (C) 2013-2017 Vinay Sajip. 

4# Licensed to the Python Software Foundation under a contributor agreement. 

5# See LICENSE.txt and CONTRIBUTORS.txt. 

6# 

7from __future__ import absolute_import 

8 

9import os 

10import re 

11import sys 

12 

13try: 

14 import ssl 

15except ImportError: # pragma: no cover 

16 ssl = None 

17 

18if sys.version_info[0] < 3: # pragma: no cover 

19 from StringIO import StringIO 

20 string_types = basestring, 

21 text_type = unicode 

22 from types import FileType as file_type 

23 import __builtin__ as builtins 

24 import ConfigParser as configparser 

25 from urlparse import urlparse, urlunparse, urljoin, urlsplit, urlunsplit 

26 from urllib import (urlretrieve, quote as _quote, unquote, url2pathname, 

27 pathname2url, ContentTooShortError, splittype) 

28 

29 def quote(s): 

30 if isinstance(s, unicode): 

31 s = s.encode('utf-8') 

32 return _quote(s) 

33 

34 import urllib2 

35 from urllib2 import (Request, urlopen, URLError, HTTPError, 

36 HTTPBasicAuthHandler, HTTPPasswordMgr, 

37 HTTPHandler, HTTPRedirectHandler, 

38 build_opener) 

39 if ssl: 

40 from urllib2 import HTTPSHandler 

41 import httplib 

42 import xmlrpclib 

43 import Queue as queue 

44 from HTMLParser import HTMLParser 

45 import htmlentitydefs 

46 raw_input = raw_input 

47 from itertools import ifilter as filter 

48 from itertools import ifilterfalse as filterfalse 

49 

50 # Leaving this around for now, in case it needs resurrecting in some way 

51 # _userprog = None 

52 # def splituser(host): 

53 # """splituser('user[:passwd]@host[:port]') --> 'user[:passwd]', 'host[:port]'.""" 

54 # global _userprog 

55 # if _userprog is None: 

56 # import re 

57 # _userprog = re.compile('^(.*)@(.*)$') 

58 

59 # match = _userprog.match(host) 

60 # if match: return match.group(1, 2) 

61 # return None, host 

62 

63else: # pragma: no cover 

64 from io import StringIO 

65 string_types = str, 

66 text_type = str 

67 from io import TextIOWrapper as file_type 

68 import builtins 

69 import configparser 

70 import shutil 

71 from urllib.parse import (urlparse, urlunparse, urljoin, quote, 

72 unquote, urlsplit, urlunsplit, splittype) 

73 from urllib.request import (urlopen, urlretrieve, Request, url2pathname, 

74 pathname2url, 

75 HTTPBasicAuthHandler, HTTPPasswordMgr, 

76 HTTPHandler, HTTPRedirectHandler, 

77 build_opener) 

78 if ssl: 

79 from urllib.request import HTTPSHandler 

80 from urllib.error import HTTPError, URLError, ContentTooShortError 

81 import http.client as httplib 

82 import urllib.request as urllib2 

83 import xmlrpc.client as xmlrpclib 

84 import queue 

85 from html.parser import HTMLParser 

86 import html.entities as htmlentitydefs 

87 raw_input = input 

88 from itertools import filterfalse 

89 filter = filter 

90 

91 

92try: 

93 from ssl import match_hostname, CertificateError 

94except ImportError: # pragma: no cover 

95 class CertificateError(ValueError): 

96 pass 

97 

98 

99 def _dnsname_match(dn, hostname, max_wildcards=1): 

100 """Matching according to RFC 6125, section 6.4.3 

101 

102 http://tools.ietf.org/html/rfc6125#section-6.4.3 

103 """ 

104 pats = [] 

105 if not dn: 

106 return False 

107 

108 parts = dn.split('.') 

109 leftmost, remainder = parts[0], parts[1:] 

110 

111 wildcards = leftmost.count('*') 

112 if wildcards > max_wildcards: 

113 # Issue #17980: avoid denials of service by refusing more 

114 # than one wildcard per fragment. A survey of established 

115 # policy among SSL implementations showed it to be a 

116 # reasonable choice. 

117 raise CertificateError( 

118 "too many wildcards in certificate DNS name: " + repr(dn)) 

119 

120 # speed up common case w/o wildcards 

121 if not wildcards: 

122 return dn.lower() == hostname.lower() 

123 

124 # RFC 6125, section 6.4.3, subitem 1. 

125 # The client SHOULD NOT attempt to match a presented identifier in which 

126 # the wildcard character comprises a label other than the left-most label. 

127 if leftmost == '*': 

128 # When '*' is a fragment by itself, it matches a non-empty dotless 

129 # fragment. 

130 pats.append('[^.]+') 

131 elif leftmost.startswith('xn--') or hostname.startswith('xn--'): 

132 # RFC 6125, section 6.4.3, subitem 3. 

133 # The client SHOULD NOT attempt to match a presented identifier 

134 # where the wildcard character is embedded within an A-label or 

135 # U-label of an internationalized domain name. 

136 pats.append(re.escape(leftmost)) 

137 else: 

138 # Otherwise, '*' matches any dotless string, e.g. www* 

139 pats.append(re.escape(leftmost).replace(r'\*', '[^.]*')) 

140 

141 # add the remaining fragments, ignore any wildcards 

142 for frag in remainder: 

143 pats.append(re.escape(frag)) 

144 

145 pat = re.compile(r'\A' + r'\.'.join(pats) + r'\Z', re.IGNORECASE) 

146 return pat.match(hostname) 

147 

148 

149 def match_hostname(cert, hostname): 

150 """Verify that *cert* (in decoded format as returned by 

151 SSLSocket.getpeercert()) matches the *hostname*. RFC 2818 and RFC 6125 

152 rules are followed, but IP addresses are not accepted for *hostname*. 

153 

154 CertificateError is raised on failure. On success, the function 

155 returns nothing. 

156 """ 

157 if not cert: 

158 raise ValueError("empty or no certificate, match_hostname needs a " 

159 "SSL socket or SSL context with either " 

160 "CERT_OPTIONAL or CERT_REQUIRED") 

161 dnsnames = [] 

162 san = cert.get('subjectAltName', ()) 

163 for key, value in san: 

164 if key == 'DNS': 

165 if _dnsname_match(value, hostname): 

166 return 

167 dnsnames.append(value) 

168 if not dnsnames: 

169 # The subject is only checked when there is no dNSName entry 

170 # in subjectAltName 

171 for sub in cert.get('subject', ()): 

172 for key, value in sub: 

173 # XXX according to RFC 2818, the most specific Common Name 

174 # must be used. 

175 if key == 'commonName': 

176 if _dnsname_match(value, hostname): 

177 return 

178 dnsnames.append(value) 

179 if len(dnsnames) > 1: 

180 raise CertificateError("hostname %r " 

181 "doesn't match either of %s" 

182 % (hostname, ', '.join(map(repr, dnsnames)))) 

183 elif len(dnsnames) == 1: 

184 raise CertificateError("hostname %r " 

185 "doesn't match %r" 

186 % (hostname, dnsnames[0])) 

187 else: 

188 raise CertificateError("no appropriate commonName or " 

189 "subjectAltName fields were found") 

190 

191 

192try: 

193 from types import SimpleNamespace as Container 

194except ImportError: # pragma: no cover 

195 class Container(object): 

196 """ 

197 A generic container for when multiple values need to be returned 

198 """ 

199 def __init__(self, **kwargs): 

200 self.__dict__.update(kwargs) 

201 

202 

203try: 

204 from shutil import which 

205except ImportError: # pragma: no cover 

206 # Implementation from Python 3.3 

207 def which(cmd, mode=os.F_OK | os.X_OK, path=None): 

208 """Given a command, mode, and a PATH string, return the path which 

209 conforms to the given mode on the PATH, or None if there is no such 

210 file. 

211 

212 `mode` defaults to os.F_OK | os.X_OK. `path` defaults to the result 

213 of os.environ.get("PATH"), or can be overridden with a custom search 

214 path. 

215 

216 """ 

217 # Check that a given file can be accessed with the correct mode. 

218 # Additionally check that `file` is not a directory, as on Windows 

219 # directories pass the os.access check. 

220 def _access_check(fn, mode): 

221 return (os.path.exists(fn) and os.access(fn, mode) 

222 and not os.path.isdir(fn)) 

223 

224 # If we're given a path with a directory part, look it up directly rather 

225 # than referring to PATH directories. This includes checking relative to the 

226 # current directory, e.g. ./script 

227 if os.path.dirname(cmd): 

228 if _access_check(cmd, mode): 

229 return cmd 

230 return None 

231 

232 if path is None: 

233 path = os.environ.get("PATH", os.defpath) 

234 if not path: 

235 return None 

236 path = path.split(os.pathsep) 

237 

238 if sys.platform == "win32": 

239 # The current directory takes precedence on Windows. 

240 if not os.curdir in path: 

241 path.insert(0, os.curdir) 

242 

243 # PATHEXT is necessary to check on Windows. 

244 pathext = os.environ.get("PATHEXT", "").split(os.pathsep) 

245 # See if the given file matches any of the expected path extensions. 

246 # This will allow us to short circuit when given "python.exe". 

247 # If it does match, only test that one, otherwise we have to try 

248 # others. 

249 if any(cmd.lower().endswith(ext.lower()) for ext in pathext): 

250 files = [cmd] 

251 else: 

252 files = [cmd + ext for ext in pathext] 

253 else: 

254 # On other platforms you don't have things like PATHEXT to tell you 

255 # what file suffixes are executable, so just pass on cmd as-is. 

256 files = [cmd] 

257 

258 seen = set() 

259 for dir in path: 

260 normdir = os.path.normcase(dir) 

261 if not normdir in seen: 

262 seen.add(normdir) 

263 for thefile in files: 

264 name = os.path.join(dir, thefile) 

265 if _access_check(name, mode): 

266 return name 

267 return None 

268 

269 

270# ZipFile is a context manager in 2.7, but not in 2.6 

271 

272from zipfile import ZipFile as BaseZipFile 

273 

274if hasattr(BaseZipFile, '__enter__'): # pragma: no cover 

275 ZipFile = BaseZipFile 

276else: # pragma: no cover 

277 from zipfile import ZipExtFile as BaseZipExtFile 

278 

279 class ZipExtFile(BaseZipExtFile): 

280 def __init__(self, base): 

281 self.__dict__.update(base.__dict__) 

282 

283 def __enter__(self): 

284 return self 

285 

286 def __exit__(self, *exc_info): 

287 self.close() 

288 # return None, so if an exception occurred, it will propagate 

289 

290 class ZipFile(BaseZipFile): 

291 def __enter__(self): 

292 return self 

293 

294 def __exit__(self, *exc_info): 

295 self.close() 

296 # return None, so if an exception occurred, it will propagate 

297 

298 def open(self, *args, **kwargs): 

299 base = BaseZipFile.open(self, *args, **kwargs) 

300 return ZipExtFile(base) 

301 

302try: 

303 from platform import python_implementation 

304except ImportError: # pragma: no cover 

305 def python_implementation(): 

306 """Return a string identifying the Python implementation.""" 

307 if 'PyPy' in sys.version: 

308 return 'PyPy' 

309 if os.name == 'java': 

310 return 'Jython' 

311 if sys.version.startswith('IronPython'): 

312 return 'IronPython' 

313 return 'CPython' 

314 

315import shutil 

316import sysconfig 

317 

318try: 

319 callable = callable 

320except NameError: # pragma: no cover 

321 from collections.abc import Callable 

322 

323 def callable(obj): 

324 return isinstance(obj, Callable) 

325 

326 

327try: 

328 fsencode = os.fsencode 

329 fsdecode = os.fsdecode 

330except AttributeError: # pragma: no cover 

331 # Issue #99: on some systems (e.g. containerised), 

332 # sys.getfilesystemencoding() returns None, and we need a real value, 

333 # so fall back to utf-8. From the CPython 2.7 docs relating to Unix and 

334 # sys.getfilesystemencoding(): the return value is "the user’s preference 

335 # according to the result of nl_langinfo(CODESET), or None if the 

336 # nl_langinfo(CODESET) failed." 

337 _fsencoding = sys.getfilesystemencoding() or 'utf-8' 

338 if _fsencoding == 'mbcs': 

339 _fserrors = 'strict' 

340 else: 

341 _fserrors = 'surrogateescape' 

342 

343 def fsencode(filename): 

344 if isinstance(filename, bytes): 

345 return filename 

346 elif isinstance(filename, text_type): 

347 return filename.encode(_fsencoding, _fserrors) 

348 else: 

349 raise TypeError("expect bytes or str, not %s" % 

350 type(filename).__name__) 

351 

352 def fsdecode(filename): 

353 if isinstance(filename, text_type): 

354 return filename 

355 elif isinstance(filename, bytes): 

356 return filename.decode(_fsencoding, _fserrors) 

357 else: 

358 raise TypeError("expect bytes or str, not %s" % 

359 type(filename).__name__) 

360 

361try: 

362 from tokenize import detect_encoding 

363except ImportError: # pragma: no cover 

364 from codecs import BOM_UTF8, lookup 

365 import re 

366 

367 cookie_re = re.compile(r"coding[:=]\s*([-\w.]+)") 

368 

369 def _get_normal_name(orig_enc): 

370 """Imitates get_normal_name in tokenizer.c.""" 

371 # Only care about the first 12 characters. 

372 enc = orig_enc[:12].lower().replace("_", "-") 

373 if enc == "utf-8" or enc.startswith("utf-8-"): 

374 return "utf-8" 

375 if enc in ("latin-1", "iso-8859-1", "iso-latin-1") or \ 

376 enc.startswith(("latin-1-", "iso-8859-1-", "iso-latin-1-")): 

377 return "iso-8859-1" 

378 return orig_enc 

379 

380 def detect_encoding(readline): 

381 """ 

382 The detect_encoding() function is used to detect the encoding that should 

383 be used to decode a Python source file. It requires one argument, readline, 

384 in the same way as the tokenize() generator. 

385 

386 It will call readline a maximum of twice, and return the encoding used 

387 (as a string) and a list of any lines (left as bytes) it has read in. 

388 

389 It detects the encoding from the presence of a utf-8 bom or an encoding 

390 cookie as specified in pep-0263. If both a bom and a cookie are present, 

391 but disagree, a SyntaxError will be raised. If the encoding cookie is an 

392 invalid charset, raise a SyntaxError. Note that if a utf-8 bom is found, 

393 'utf-8-sig' is returned. 

394 

395 If no encoding is specified, then the default of 'utf-8' will be returned. 

396 """ 

397 try: 

398 filename = readline.__self__.name 

399 except AttributeError: 

400 filename = None 

401 bom_found = False 

402 encoding = None 

403 default = 'utf-8' 

404 def read_or_stop(): 

405 try: 

406 return readline() 

407 except StopIteration: 

408 return b'' 

409 

410 def find_cookie(line): 

411 try: 

412 # Decode as UTF-8. Either the line is an encoding declaration, 

413 # in which case it should be pure ASCII, or it must be UTF-8 

414 # per default encoding. 

415 line_string = line.decode('utf-8') 

416 except UnicodeDecodeError: 

417 msg = "invalid or missing encoding declaration" 

418 if filename is not None: 

419 msg = '{} for {!r}'.format(msg, filename) 

420 raise SyntaxError(msg) 

421 

422 matches = cookie_re.findall(line_string) 

423 if not matches: 

424 return None 

425 encoding = _get_normal_name(matches[0]) 

426 try: 

427 codec = lookup(encoding) 

428 except LookupError: 

429 # This behaviour mimics the Python interpreter 

430 if filename is None: 

431 msg = "unknown encoding: " + encoding 

432 else: 

433 msg = "unknown encoding for {!r}: {}".format(filename, 

434 encoding) 

435 raise SyntaxError(msg) 

436 

437 if bom_found: 

438 if codec.name != 'utf-8': 

439 # This behaviour mimics the Python interpreter 

440 if filename is None: 

441 msg = 'encoding problem: utf-8' 

442 else: 

443 msg = 'encoding problem for {!r}: utf-8'.format(filename) 

444 raise SyntaxError(msg) 

445 encoding += '-sig' 

446 return encoding 

447 

448 first = read_or_stop() 

449 if first.startswith(BOM_UTF8): 

450 bom_found = True 

451 first = first[3:] 

452 default = 'utf-8-sig' 

453 if not first: 

454 return default, [] 

455 

456 encoding = find_cookie(first) 

457 if encoding: 

458 return encoding, [first] 

459 

460 second = read_or_stop() 

461 if not second: 

462 return default, [first] 

463 

464 encoding = find_cookie(second) 

465 if encoding: 

466 return encoding, [first, second] 

467 

468 return default, [first, second] 

469 

470# For converting & <-> &amp; etc. 

471try: 

472 from html import escape 

473except ImportError: 

474 from cgi import escape 

475if sys.version_info[:2] < (3, 4): 

476 unescape = HTMLParser().unescape 

477else: 

478 from html import unescape 

479 

480try: 

481 from collections import ChainMap 

482except ImportError: # pragma: no cover 

483 from collections import MutableMapping 

484 

485 try: 

486 from reprlib import recursive_repr as _recursive_repr 

487 except ImportError: 

488 def _recursive_repr(fillvalue='...'): 

489 ''' 

490 Decorator to make a repr function return fillvalue for a recursive 

491 call 

492 ''' 

493 

494 def decorating_function(user_function): 

495 repr_running = set() 

496 

497 def wrapper(self): 

498 key = id(self), get_ident() 

499 if key in repr_running: 

500 return fillvalue 

501 repr_running.add(key) 

502 try: 

503 result = user_function(self) 

504 finally: 

505 repr_running.discard(key) 

506 return result 

507 

508 # Can't use functools.wraps() here because of bootstrap issues 

509 wrapper.__module__ = getattr(user_function, '__module__') 

510 wrapper.__doc__ = getattr(user_function, '__doc__') 

511 wrapper.__name__ = getattr(user_function, '__name__') 

512 wrapper.__annotations__ = getattr(user_function, '__annotations__', {}) 

513 return wrapper 

514 

515 return decorating_function 

516 

517 class ChainMap(MutableMapping): 

518 ''' A ChainMap groups multiple dicts (or other mappings) together 

519 to create a single, updateable view. 

520 

521 The underlying mappings are stored in a list. That list is public and can 

522 accessed or updated using the *maps* attribute. There is no other state. 

523 

524 Lookups search the underlying mappings successively until a key is found. 

525 In contrast, writes, updates, and deletions only operate on the first 

526 mapping. 

527 

528 ''' 

529 

530 def __init__(self, *maps): 

531 '''Initialize a ChainMap by setting *maps* to the given mappings. 

532 If no mappings are provided, a single empty dictionary is used. 

533 

534 ''' 

535 self.maps = list(maps) or [{}] # always at least one map 

536 

537 def __missing__(self, key): 

538 raise KeyError(key) 

539 

540 def __getitem__(self, key): 

541 for mapping in self.maps: 

542 try: 

543 return mapping[key] # can't use 'key in mapping' with defaultdict 

544 except KeyError: 

545 pass 

546 return self.__missing__(key) # support subclasses that define __missing__ 

547 

548 def get(self, key, default=None): 

549 return self[key] if key in self else default 

550 

551 def __len__(self): 

552 return len(set().union(*self.maps)) # reuses stored hash values if possible 

553 

554 def __iter__(self): 

555 return iter(set().union(*self.maps)) 

556 

557 def __contains__(self, key): 

558 return any(key in m for m in self.maps) 

559 

560 def __bool__(self): 

561 return any(self.maps) 

562 

563 @_recursive_repr() 

564 def __repr__(self): 

565 return '{0.__class__.__name__}({1})'.format( 

566 self, ', '.join(map(repr, self.maps))) 

567 

568 @classmethod 

569 def fromkeys(cls, iterable, *args): 

570 'Create a ChainMap with a single dict created from the iterable.' 

571 return cls(dict.fromkeys(iterable, *args)) 

572 

573 def copy(self): 

574 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]' 

575 return self.__class__(self.maps[0].copy(), *self.maps[1:]) 

576 

577 __copy__ = copy 

578 

579 def new_child(self): # like Django's Context.push() 

580 'New ChainMap with a new dict followed by all previous maps.' 

581 return self.__class__({}, *self.maps) 

582 

583 @property 

584 def parents(self): # like Django's Context.pop() 

585 'New ChainMap from maps[1:].' 

586 return self.__class__(*self.maps[1:]) 

587 

588 def __setitem__(self, key, value): 

589 self.maps[0][key] = value 

590 

591 def __delitem__(self, key): 

592 try: 

593 del self.maps[0][key] 

594 except KeyError: 

595 raise KeyError('Key not found in the first mapping: {!r}'.format(key)) 

596 

597 def popitem(self): 

598 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.' 

599 try: 

600 return self.maps[0].popitem() 

601 except KeyError: 

602 raise KeyError('No keys found in the first mapping.') 

603 

604 def pop(self, key, *args): 

605 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].' 

606 try: 

607 return self.maps[0].pop(key, *args) 

608 except KeyError: 

609 raise KeyError('Key not found in the first mapping: {!r}'.format(key)) 

610 

611 def clear(self): 

612 'Clear maps[0], leaving maps[1:] intact.' 

613 self.maps[0].clear() 

614 

615try: 

616 from importlib.util import cache_from_source # Python >= 3.4 

617except ImportError: # pragma: no cover 

618 def cache_from_source(path, debug_override=None): 

619 assert path.endswith('.py') 

620 if debug_override is None: 

621 debug_override = __debug__ 

622 if debug_override: 

623 suffix = 'c' 

624 else: 

625 suffix = 'o' 

626 return path + suffix 

627 

628try: 

629 from collections import OrderedDict 

630except ImportError: # pragma: no cover 

631## {{{ http://code.activestate.com/recipes/576693/ (r9) 

632# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy. 

633# Passes Python2.7's test suite and incorporates all the latest updates. 

634 try: 

635 from thread import get_ident as _get_ident 

636 except ImportError: 

637 from dummy_thread import get_ident as _get_ident 

638 

639 try: 

640 from _abcoll import KeysView, ValuesView, ItemsView 

641 except ImportError: 

642 pass 

643 

644 

645 class OrderedDict(dict): 

646 'Dictionary that remembers insertion order' 

647 # An inherited dict maps keys to values. 

648 # The inherited dict provides __getitem__, __len__, __contains__, and get. 

649 # The remaining methods are order-aware. 

650 # Big-O running times for all methods are the same as for regular dictionaries. 

651 

652 # The internal self.__map dictionary maps keys to links in a doubly linked list. 

653 # The circular doubly linked list starts and ends with a sentinel element. 

654 # The sentinel element never gets deleted (this simplifies the algorithm). 

655 # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 

656 

657 def __init__(self, *args, **kwds): 

658 '''Initialize an ordered dictionary. Signature is the same as for 

659 regular dictionaries, but keyword arguments are not recommended 

660 because their insertion order is arbitrary. 

661 

662 ''' 

663 if len(args) > 1: 

664 raise TypeError('expected at most 1 arguments, got %d' % len(args)) 

665 try: 

666 self.__root 

667 except AttributeError: 

668 self.__root = root = [] # sentinel node 

669 root[:] = [root, root, None] 

670 self.__map = {} 

671 self.__update(*args, **kwds) 

672 

673 def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 

674 'od.__setitem__(i, y) <==> od[i]=y' 

675 # Setting a new item creates a new link which goes at the end of the linked 

676 # list, and the inherited dictionary is updated with the new key/value pair. 

677 if key not in self: 

678 root = self.__root 

679 last = root[0] 

680 last[1] = root[0] = self.__map[key] = [last, root, key] 

681 dict_setitem(self, key, value) 

682 

683 def __delitem__(self, key, dict_delitem=dict.__delitem__): 

684 'od.__delitem__(y) <==> del od[y]' 

685 # Deleting an existing item uses self.__map to find the link which is 

686 # then removed by updating the links in the predecessor and successor nodes. 

687 dict_delitem(self, key) 

688 link_prev, link_next, key = self.__map.pop(key) 

689 link_prev[1] = link_next 

690 link_next[0] = link_prev 

691 

692 def __iter__(self): 

693 'od.__iter__() <==> iter(od)' 

694 root = self.__root 

695 curr = root[1] 

696 while curr is not root: 

697 yield curr[2] 

698 curr = curr[1] 

699 

700 def __reversed__(self): 

701 'od.__reversed__() <==> reversed(od)' 

702 root = self.__root 

703 curr = root[0] 

704 while curr is not root: 

705 yield curr[2] 

706 curr = curr[0] 

707 

708 def clear(self): 

709 'od.clear() -> None. Remove all items from od.' 

710 try: 

711 for node in self.__map.itervalues(): 

712 del node[:] 

713 root = self.__root 

714 root[:] = [root, root, None] 

715 self.__map.clear() 

716 except AttributeError: 

717 pass 

718 dict.clear(self) 

719 

720 def popitem(self, last=True): 

721 '''od.popitem() -> (k, v), return and remove a (key, value) pair. 

722 Pairs are returned in LIFO order if last is true or FIFO order if false. 

723 

724 ''' 

725 if not self: 

726 raise KeyError('dictionary is empty') 

727 root = self.__root 

728 if last: 

729 link = root[0] 

730 link_prev = link[0] 

731 link_prev[1] = root 

732 root[0] = link_prev 

733 else: 

734 link = root[1] 

735 link_next = link[1] 

736 root[1] = link_next 

737 link_next[0] = root 

738 key = link[2] 

739 del self.__map[key] 

740 value = dict.pop(self, key) 

741 return key, value 

742 

743 # -- the following methods do not depend on the internal structure -- 

744 

745 def keys(self): 

746 'od.keys() -> list of keys in od' 

747 return list(self) 

748 

749 def values(self): 

750 'od.values() -> list of values in od' 

751 return [self[key] for key in self] 

752 

753 def items(self): 

754 'od.items() -> list of (key, value) pairs in od' 

755 return [(key, self[key]) for key in self] 

756 

757 def iterkeys(self): 

758 'od.iterkeys() -> an iterator over the keys in od' 

759 return iter(self) 

760 

761 def itervalues(self): 

762 'od.itervalues -> an iterator over the values in od' 

763 for k in self: 

764 yield self[k] 

765 

766 def iteritems(self): 

767 'od.iteritems -> an iterator over the (key, value) items in od' 

768 for k in self: 

769 yield (k, self[k]) 

770 

771 def update(*args, **kwds): 

772 '''od.update(E, **F) -> None. Update od from dict/iterable E and F. 

773 

774 If E is a dict instance, does: for k in E: od[k] = E[k] 

775 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k] 

776 Or if E is an iterable of items, does: for k, v in E: od[k] = v 

777 In either case, this is followed by: for k, v in F.items(): od[k] = v 

778 

779 ''' 

780 if len(args) > 2: 

781 raise TypeError('update() takes at most 2 positional ' 

782 'arguments (%d given)' % (len(args),)) 

783 elif not args: 

784 raise TypeError('update() takes at least 1 argument (0 given)') 

785 self = args[0] 

786 # Make progressively weaker assumptions about "other" 

787 other = () 

788 if len(args) == 2: 

789 other = args[1] 

790 if isinstance(other, dict): 

791 for key in other: 

792 self[key] = other[key] 

793 elif hasattr(other, 'keys'): 

794 for key in other.keys(): 

795 self[key] = other[key] 

796 else: 

797 for key, value in other: 

798 self[key] = value 

799 for key, value in kwds.items(): 

800 self[key] = value 

801 

802 __update = update # let subclasses override update without breaking __init__ 

803 

804 __marker = object() 

805 

806 def pop(self, key, default=__marker): 

807 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value. 

808 If key is not found, d is returned if given, otherwise KeyError is raised. 

809 

810 ''' 

811 if key in self: 

812 result = self[key] 

813 del self[key] 

814 return result 

815 if default is self.__marker: 

816 raise KeyError(key) 

817 return default 

818 

819 def setdefault(self, key, default=None): 

820 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od' 

821 if key in self: 

822 return self[key] 

823 self[key] = default 

824 return default 

825 

826 def __repr__(self, _repr_running=None): 

827 'od.__repr__() <==> repr(od)' 

828 if not _repr_running: _repr_running = {} 

829 call_key = id(self), _get_ident() 

830 if call_key in _repr_running: 

831 return '...' 

832 _repr_running[call_key] = 1 

833 try: 

834 if not self: 

835 return '%s()' % (self.__class__.__name__,) 

836 return '%s(%r)' % (self.__class__.__name__, self.items()) 

837 finally: 

838 del _repr_running[call_key] 

839 

840 def __reduce__(self): 

841 'Return state information for pickling' 

842 items = [[k, self[k]] for k in self] 

843 inst_dict = vars(self).copy() 

844 for k in vars(OrderedDict()): 

845 inst_dict.pop(k, None) 

846 if inst_dict: 

847 return (self.__class__, (items,), inst_dict) 

848 return self.__class__, (items,) 

849 

850 def copy(self): 

851 'od.copy() -> a shallow copy of od' 

852 return self.__class__(self) 

853 

854 @classmethod 

855 def fromkeys(cls, iterable, value=None): 

856 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S 

857 and values equal to v (which defaults to None). 

858 

859 ''' 

860 d = cls() 

861 for key in iterable: 

862 d[key] = value 

863 return d 

864 

865 def __eq__(self, other): 

866 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 

867 while comparison to a regular mapping is order-insensitive. 

868 

869 ''' 

870 if isinstance(other, OrderedDict): 

871 return len(self)==len(other) and self.items() == other.items() 

872 return dict.__eq__(self, other) 

873 

874 def __ne__(self, other): 

875 return not self == other 

876 

877 # -- the following methods are only used in Python 2.7 --