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

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 shutil 

12import sys 

13 

14try: 

15 import ssl 

16except ImportError: # pragma: no cover 

17 ssl = None 

18 

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

20 from StringIO import StringIO 

21 string_types = basestring, 

22 text_type = unicode 

23 from types import FileType as file_type 

24 import __builtin__ as builtins 

25 import ConfigParser as configparser 

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

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

28 pathname2url, ContentTooShortError, splittype) 

29 

30 def quote(s): 

31 if isinstance(s, unicode): 

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

33 return _quote(s) 

34 

35 import urllib2 

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

37 HTTPBasicAuthHandler, HTTPPasswordMgr, HTTPHandler, 

38 HTTPRedirectHandler, 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 from urllib.parse import (urlparse, urlunparse, urljoin, quote, unquote, 

71 urlsplit, urlunsplit, splittype) 

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

73 pathname2url, HTTPBasicAuthHandler, 

74 HTTPPasswordMgr, HTTPHandler, 

75 HTTPRedirectHandler, build_opener) 

76 if ssl: 

77 from urllib.request import HTTPSHandler 

78 from urllib.error import HTTPError, URLError, ContentTooShortError 

79 import http.client as httplib 

80 import urllib.request as urllib2 

81 import xmlrpc.client as xmlrpclib 

82 import queue 

83 from html.parser import HTMLParser 

84 import html.entities as htmlentitydefs 

85 raw_input = input 

86 from itertools import filterfalse 

87 filter = filter 

88 

89try: 

90 from ssl import match_hostname, CertificateError 

91except ImportError: # pragma: no cover 

92 

93 class CertificateError(ValueError): 

94 pass 

95 

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

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

98 

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

100 """ 

101 pats = [] 

102 if not dn: 

103 return False 

104 

105 parts = dn.split('.') 

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

107 

108 wildcards = leftmost.count('*') 

109 if wildcards > max_wildcards: 

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

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

112 # policy among SSL implementations showed it to be a 

113 # reasonable choice. 

114 raise CertificateError( 

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

116 

117 # speed up common case w/o wildcards 

118 if not wildcards: 

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

120 

121 # RFC 6125, section 6.4.3, subitem 1. 

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

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

124 if leftmost == '*': 

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

126 # fragment. 

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

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

129 # RFC 6125, section 6.4.3, subitem 3. 

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

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

132 # U-label of an internationalized domain name. 

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

134 else: 

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

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

137 

138 # add the remaining fragments, ignore any wildcards 

139 for frag in remainder: 

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

141 

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

143 return pat.match(hostname) 

144 

145 def match_hostname(cert, hostname): 

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

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

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

149 

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

151 returns nothing. 

152 """ 

153 if not cert: 

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

155 "SSL socket or SSL context with either " 

156 "CERT_OPTIONAL or CERT_REQUIRED") 

157 dnsnames = [] 

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

159 for key, value in san: 

160 if key == 'DNS': 

161 if _dnsname_match(value, hostname): 

162 return 

163 dnsnames.append(value) 

164 if not dnsnames: 

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

166 # in subjectAltName 

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

168 for key, value in sub: 

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

170 # must be used. 

171 if key == 'commonName': 

172 if _dnsname_match(value, hostname): 

173 return 

174 dnsnames.append(value) 

175 if len(dnsnames) > 1: 

176 raise CertificateError("hostname %r " 

177 "doesn't match either of %s" % 

178 (hostname, ', '.join(map(repr, dnsnames)))) 

179 elif len(dnsnames) == 1: 

180 raise CertificateError("hostname %r " 

181 "doesn't match %r" % 

182 (hostname, dnsnames[0])) 

183 else: 

184 raise CertificateError("no appropriate commonName or " 

185 "subjectAltName fields were found") 

186 

187 

188try: 

189 from types import SimpleNamespace as Container 

190except ImportError: # pragma: no cover 

191 

192 class Container(object): 

193 """ 

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

195 """ 

196 

197 def __init__(self, **kwargs): 

198 self.__dict__.update(kwargs) 

199 

200 

201try: 

202 from shutil import which 

203except ImportError: # pragma: no cover 

204 # Implementation from Python 3.3 

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

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

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

208 file. 

209 

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

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

212 path. 

213 

214 """ 

215 

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

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

218 # directories pass the os.access check. 

219 def _access_check(fn, mode): 

220 return (os.path.exists(fn) and os.access(fn, mode) and not os.path.isdir(fn)) 

221 

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

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

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

225 if os.path.dirname(cmd): 

226 if _access_check(cmd, mode): 

227 return cmd 

228 return None 

229 

230 if path is None: 

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

232 if not path: 

233 return None 

234 path = path.split(os.pathsep) 

235 

236 if sys.platform == "win32": 

237 # The current directory takes precedence on Windows. 

238 if os.curdir not in path: 

239 path.insert(0, os.curdir) 

240 

241 # PATHEXT is necessary to check on Windows. 

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

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

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

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

246 # others. 

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

248 files = [cmd] 

249 else: 

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

251 else: 

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

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

254 files = [cmd] 

255 

256 seen = set() 

257 for dir in path: 

258 normdir = os.path.normcase(dir) 

259 if normdir not in seen: 

260 seen.add(normdir) 

261 for thefile in files: 

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

263 if _access_check(name, mode): 

264 return name 

265 return None 

266 

267 

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

269 

270from zipfile import ZipFile as BaseZipFile 

271 

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

273 ZipFile = BaseZipFile 

274else: # pragma: no cover 

275 from zipfile import ZipExtFile as BaseZipExtFile 

276 

277 class ZipExtFile(BaseZipExtFile): 

278 

279 def __init__(self, base): 

280 self.__dict__.update(base.__dict__) 

281 

282 def __enter__(self): 

283 return self 

284 

285 def __exit__(self, *exc_info): 

286 self.close() 

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

288 

289 class ZipFile(BaseZipFile): 

290 

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 

302 

303try: 

304 from platform import python_implementation 

305except ImportError: # pragma: no cover 

306 

307 def python_implementation(): 

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

309 if 'PyPy' in sys.version: 

310 return 'PyPy' 

311 if os.name == 'java': 

312 return 'Jython' 

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

314 return 'IronPython' 

315 return 'CPython' 

316 

317 

318import sysconfig 

319 

320try: 

321 callable = callable 

322except NameError: # pragma: no cover 

323 from collections.abc import Callable 

324 

325 def callable(obj): 

326 return isinstance(obj, Callable) 

327 

328 

329try: 

330 fsencode = os.fsencode 

331 fsdecode = os.fsdecode 

332except AttributeError: # pragma: no cover 

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

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

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

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

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

338 # nl_langinfo(CODESET) failed." 

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

340 if _fsencoding == 'mbcs': 

341 _fserrors = 'strict' 

342 else: 

343 _fserrors = 'surrogateescape' 

344 

345 def fsencode(filename): 

346 if isinstance(filename, bytes): 

347 return filename 

348 elif isinstance(filename, text_type): 

349 return filename.encode(_fsencoding, _fserrors) 

350 else: 

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

352 type(filename).__name__) 

353 

354 def fsdecode(filename): 

355 if isinstance(filename, text_type): 

356 return filename 

357 elif isinstance(filename, bytes): 

358 return filename.decode(_fsencoding, _fserrors) 

359 else: 

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

361 type(filename).__name__) 

362 

363 

364try: 

365 from tokenize import detect_encoding 

366except ImportError: # pragma: no cover 

367 from codecs import BOM_UTF8, lookup 

368 

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

370 

371 def _get_normal_name(orig_enc): 

372 """Imitates get_normal_name in tokenizer.c.""" 

373 # Only care about the first 12 characters. 

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

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

376 return "utf-8" 

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

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

379 return "iso-8859-1" 

380 return orig_enc 

381 

382 def detect_encoding(readline): 

383 """ 

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

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

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

387 

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

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

390 

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

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

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

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

395 'utf-8-sig' is returned. 

396 

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

398 """ 

399 try: 

400 filename = readline.__self__.name 

401 except AttributeError: 

402 filename = None 

403 bom_found = False 

404 encoding = None 

405 default = 'utf-8' 

406 

407 def read_or_stop(): 

408 try: 

409 return readline() 

410 except StopIteration: 

411 return b'' 

412 

413 def find_cookie(line): 

414 try: 

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

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

417 # per default encoding. 

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

419 except UnicodeDecodeError: 

420 msg = "invalid or missing encoding declaration" 

421 if filename is not None: 

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

423 raise SyntaxError(msg) 

424 

425 matches = cookie_re.findall(line_string) 

426 if not matches: 

427 return None 

428 encoding = _get_normal_name(matches[0]) 

429 try: 

430 codec = lookup(encoding) 

431 except LookupError: 

432 # This behaviour mimics the Python interpreter 

433 if filename is None: 

434 msg = "unknown encoding: " + encoding 

435 else: 

436 msg = "unknown encoding for {!r}: {}".format( 

437 filename, encoding) 

438 raise SyntaxError(msg) 

439 

440 if bom_found: 

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

442 # This behaviour mimics the Python interpreter 

443 if filename is None: 

444 msg = 'encoding problem: utf-8' 

445 else: 

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

447 filename) 

448 raise SyntaxError(msg) 

449 encoding += '-sig' 

450 return encoding 

451 

452 first = read_or_stop() 

453 if first.startswith(BOM_UTF8): 

454 bom_found = True 

455 first = first[3:] 

456 default = 'utf-8-sig' 

457 if not first: 

458 return default, [] 

459 

460 encoding = find_cookie(first) 

461 if encoding: 

462 return encoding, [first] 

463 

464 second = read_or_stop() 

465 if not second: 

466 return default, [first] 

467 

468 encoding = find_cookie(second) 

469 if encoding: 

470 return encoding, [first, second] 

471 

472 return default, [first, second] 

473 

474 

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

476try: 

477 from html import escape 

478except ImportError: 

479 from cgi import escape 

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

481 unescape = HTMLParser().unescape 

482else: 

483 from html import unescape 

484 

485try: 

486 from collections import ChainMap 

487except ImportError: # pragma: no cover 

488 from collections import MutableMapping 

489 

490 try: 

491 from reprlib import recursive_repr as _recursive_repr 

492 except ImportError: 

493 

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

495 ''' 

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

497 call 

498 ''' 

499 

500 def decorating_function(user_function): 

501 repr_running = set() 

502 

503 def wrapper(self): 

504 key = id(self), get_ident() 

505 if key in repr_running: 

506 return fillvalue 

507 repr_running.add(key) 

508 try: 

509 result = user_function(self) 

510 finally: 

511 repr_running.discard(key) 

512 return result 

513 

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

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

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

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

518 wrapper.__annotations__ = getattr(user_function, 

519 '__annotations__', {}) 

520 return wrapper 

521 

522 return decorating_function 

523 

524 class ChainMap(MutableMapping): 

525 ''' 

526 A ChainMap groups multiple dicts (or other mappings) together 

527 to create a single, updateable view. 

528 

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

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

531 

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

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

534 mapping. 

535 ''' 

536 

537 def __init__(self, *maps): 

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

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

540 

541 ''' 

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

543 

544 def __missing__(self, key): 

545 raise KeyError(key) 

546 

547 def __getitem__(self, key): 

548 for mapping in self.maps: 

549 try: 

550 return mapping[ 

551 key] # can't use 'key in mapping' with defaultdict 

552 except KeyError: 

553 pass 

554 return self.__missing__( 

555 key) # support subclasses that define __missing__ 

556 

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

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

559 

560 def __len__(self): 

561 return len(set().union( 

562 *self.maps)) # reuses stored hash values if possible 

563 

564 def __iter__(self): 

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

566 

567 def __contains__(self, key): 

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

569 

570 def __bool__(self): 

571 return any(self.maps) 

572 

573 @_recursive_repr() 

574 def __repr__(self): 

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

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

577 

578 @classmethod 

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

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

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

582 

583 def copy(self): 

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

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

586 

587 __copy__ = copy 

588 

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

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

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

592 

593 @property 

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

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

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

597 

598 def __setitem__(self, key, value): 

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

600 

601 def __delitem__(self, key): 

602 try: 

603 del self.maps[0][key] 

604 except KeyError: 

605 raise KeyError( 

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

607 

608 def popitem(self): 

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

610 try: 

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

612 except KeyError: 

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

614 

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

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

617 try: 

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

619 except KeyError: 

620 raise KeyError( 

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

622 

623 def clear(self): 

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

625 self.maps[0].clear() 

626 

627 

628try: 

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

630except ImportError: # pragma: no cover 

631 

632 def cache_from_source(path, debug_override=None): 

633 assert path.endswith('.py') 

634 if debug_override is None: 

635 debug_override = __debug__ 

636 if debug_override: 

637 suffix = 'c' 

638 else: 

639 suffix = 'o' 

640 return path + suffix 

641 

642 

643try: 

644 from collections import OrderedDict 

645except ImportError: # pragma: no cover 

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

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

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

649 try: 

650 from thread import get_ident as _get_ident 

651 except ImportError: 

652 from dummy_thread import get_ident as _get_ident 

653 

654 try: 

655 from _abcoll import KeysView, ValuesView, ItemsView 

656 except ImportError: 

657 pass 

658 

659 class OrderedDict(dict): 

660 'Dictionary that remembers insertion order' 

661 

662 # An inherited dict maps keys to values. 

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

664 # The remaining methods are order-aware. 

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

666 

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

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

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

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

671 

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

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

674 regular dictionaries, but keyword arguments are not recommended 

675 because their insertion order is arbitrary. 

676 

677 ''' 

678 if len(args) > 1: 

679 raise TypeError('expected at most 1 arguments, got %d' % 

680 len(args)) 

681 try: 

682 self.__root 

683 except AttributeError: 

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

685 root[:] = [root, root, None] 

686 self.__map = {} 

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

688 

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

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

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

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

693 if key not in self: 

694 root = self.__root 

695 last = root[0] 

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

697 dict_setitem(self, key, value) 

698 

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

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

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

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

703 dict_delitem(self, key) 

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

705 link_prev[1] = link_next 

706 link_next[0] = link_prev 

707 

708 def __iter__(self): 

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

710 root = self.__root 

711 curr = root[1] 

712 while curr is not root: 

713 yield curr[2] 

714 curr = curr[1] 

715 

716 def __reversed__(self): 

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

718 root = self.__root 

719 curr = root[0] 

720 while curr is not root: 

721 yield curr[2] 

722 curr = curr[0] 

723 

724 def clear(self): 

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

726 try: 

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

728 del node[:] 

729 root = self.__root 

730 root[:] = [root, root, None] 

731 self.__map.clear() 

732 except AttributeError: 

733 pass 

734 dict.clear(self) 

735 

736 def popitem(self, last=True): 

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

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

739 

740 ''' 

741 if not self: 

742 raise KeyError('dictionary is empty') 

743 root = self.__root 

744 if last: 

745 link = root[0] 

746 link_prev = link[0] 

747 link_prev[1] = root 

748 root[0] = link_prev 

749 else: 

750 link = root[1] 

751 link_next = link[1] 

752 root[1] = link_next 

753 link_next[0] = root 

754 key = link[2] 

755 del self.__map[key] 

756 value = dict.pop(self, key) 

757 return key, value 

758 

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

760 

761 def keys(self): 

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

763 return list(self) 

764 

765 def values(self): 

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

767 return [self[key] for key in self] 

768 

769 def items(self): 

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

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

772 

773 def iterkeys(self): 

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

775 return iter(self) 

776 

777 def itervalues(self): 

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

779 for k in self: 

780 yield self[k] 

781 

782 def iteritems(self): 

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

784 for k in self: 

785 yield (k, self[k]) 

786 

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

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

789 

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

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

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

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

794 

795 ''' 

796 if len(args) > 2: 

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

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

799 elif not args: 

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

801 self = args[0] 

802 # Make progressively weaker assumptions about "other" 

803 other = () 

804 if len(args) == 2: 

805 other = args[1] 

806 if isinstance(other, dict): 

807 for key in other: 

808 self[key] = other[key] 

809 elif hasattr(other, 'keys'): 

810 for key in other.keys(): 

811 self[key] = other[key] 

812 else: 

813 for key, value in other: 

814 self[key] = value 

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

816 self[key] = value 

817 

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

819 

820 __marker = object() 

821 

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

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

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

825 

826 ''' 

827 if key in self: 

828 result = self[key] 

829 del self[key] 

830 return result 

831 if default is self.__marker: 

832 raise KeyError(key) 

833 return default 

834 

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

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

837 if key in self: 

838 return self[key] 

839 self[key] = default 

840 return default 

841 

842 def __repr__(self, _repr_running=None): 

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

844 if not _repr_running: 

845 _repr_running = {} 

846 call_key = id(self), _get_ident() 

847 if call_key in _repr_running: 

848 return '...' 

849 _repr_running[call_key] = 1 

850 try: 

851 if not self: 

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

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

854 finally: 

855 del _repr_running[call_key] 

856 

857 def __reduce__(self): 

858 'Return state information for pickling' 

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

860 inst_dict = vars(self).copy() 

861 for k in vars(OrderedDict()): 

862 inst_dict.pop(k, None) 

863 if inst_dict: 

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

865 return self.__class__, (items, ) 

866 

867 def copy(self): 

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

869 return self.__class__(self) 

870 

871 @classmethod 

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

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

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

875 

876 ''' 

877 d = cls() 

878 for key in iterable: 

879 d[key] = value 

880 return d 

881 

882 def __eq__(self, other): 

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

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

885 

886 ''' 

887 if isinstance(other, OrderedDict):