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-2026 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, pathname2url, ContentTooShortError, 

28 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, HTTPBasicAuthHandler, HTTPPasswordMgr, HTTPHandler, 

37 HTTPRedirectHandler, build_opener) 

38 if ssl: 

39 from urllib2 import HTTPSHandler 

40 import httplib 

41 import xmlrpclib 

42 import Queue as queue 

43 from HTMLParser import HTMLParser 

44 import htmlentitydefs 

45 raw_input = raw_input 

46 from itertools import ifilter as filter 

47 from itertools import ifilterfalse as filterfalse 

48 

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

50 # _userprog = None 

51 # def splituser(host): 

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

53 # global _userprog 

54 # if _userprog is None: 

55 # import re 

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

57 

58 # match = _userprog.match(host) 

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

60 # return None, host 

61 

62else: # pragma: no cover 

63 from io import StringIO 

64 string_types = str, 

65 text_type = str 

66 from io import TextIOWrapper as file_type 

67 import builtins 

68 import configparser 

69 from urllib.parse import (urlparse, urlunparse, urljoin, quote, unquote, urlsplit, urlunsplit, splittype) 

70 from urllib.request import (urlopen, urlretrieve, Request, url2pathname, pathname2url, HTTPBasicAuthHandler, 

71 HTTPPasswordMgr, HTTPHandler, HTTPRedirectHandler, build_opener) 

72 if ssl: 

73 from urllib.request import HTTPSHandler 

74 from urllib.error import HTTPError, URLError, ContentTooShortError 

75 import http.client as httplib 

76 import urllib.request as urllib2 

77 import xmlrpc.client as xmlrpclib 

78 import queue 

79 from html.parser import HTMLParser 

80 import html.entities as htmlentitydefs 

81 raw_input = input 

82 from itertools import filterfalse 

83 filter = filter 

84 

85try: 

86 from ssl import match_hostname, CertificateError 

87except ImportError: # pragma: no cover 

88 

89 class CertificateError(ValueError): 

90 pass 

91 

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

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

94 

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

96 """ 

97 pats = [] 

98 if not dn: 

99 return False 

100 

101 parts = dn.split('.') 

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

103 

104 wildcards = leftmost.count('*') 

105 if wildcards > max_wildcards: 

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

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

108 # policy among SSL implementations showed it to be a 

109 # reasonable choice. 

110 raise CertificateError('Too many wildcards in certificate DNS name: %r' % dn) 

111 

112 # speed up common case w/o wildcards 

113 if not wildcards: 

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

115 

116 # RFC 6125, section 6.4.3, subitem 1. 

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

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

119 if leftmost == '*': 

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

121 # fragment. 

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

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

124 # RFC 6125, section 6.4.3, subitem 3. 

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

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

127 # U-label of an internationalized domain name. 

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

129 else: 

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

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

132 

133 # add the remaining fragments, ignore any wildcards 

134 for frag in remainder: 

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

136 

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

138 return pat.match(hostname) 

139 

140 def match_hostname(cert, hostname): 

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

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

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

144 

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

146 returns nothing. 

147 """ 

148 if not cert: 

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

150 "SSL socket or SSL context with either " 

151 "CERT_OPTIONAL or CERT_REQUIRED") 

152 dnsnames = [] 

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

154 for key, value in san: 

155 if key == 'DNS': 

156 if _dnsname_match(value, hostname): 

157 return 

158 dnsnames.append(value) 

159 if not dnsnames: 

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

161 # in subjectAltName 

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

163 for key, value in sub: 

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

165 # must be used. 

166 if key == 'commonName': 

167 if _dnsname_match(value, hostname): 

168 return 

169 dnsnames.append(value) 

170 if len(dnsnames) > 1: 

171 raise CertificateError("hostname %r " 

172 "doesn't match either of %s" % (hostname, ', '.join(map(repr, dnsnames)))) 

173 elif len(dnsnames) == 1: 

174 raise CertificateError("hostname %r " 

175 "doesn't match %r" % (hostname, dnsnames[0])) 

176 else: 

177 raise CertificateError("no appropriate commonName or " 

178 "subjectAltName fields were found") 

179 

180 

181try: 

182 from types import SimpleNamespace as Container 

183except ImportError: # pragma: no cover 

184 

185 class Container(object): 

186 """ 

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

188 """ 

189 

190 def __init__(self, **kwargs): 

191 self.__dict__.update(kwargs) 

192 

193 

194try: 

195 from shutil import which 

196except ImportError: # pragma: no cover 

197 # Implementation from Python 3.3 

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

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

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

201 file. 

202 

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

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

205 path. 

206 

207 """ 

208 

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

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

211 # directories pass the os.access check. 

212 def _access_check(fn, mode): 

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

214 

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

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

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

218 if os.path.dirname(cmd): 

219 if _access_check(cmd, mode): 

220 return cmd 

221 return None 

222 

223 if path is None: 

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

225 if not path: 

226 return None 

227 path = path.split(os.pathsep) 

228 

229 if sys.platform == "win32": 

230 # The current directory takes precedence on Windows. 

231 if os.curdir not in path: 

232 path.insert(0, os.curdir) 

233 

234 # PATHEXT is necessary to check on Windows. 

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

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

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

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

239 # others. 

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

241 files = [cmd] 

242 else: 

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

244 else: 

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

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

247 files = [cmd] 

248 

249 seen = set() 

250 for dir in path: 

251 normdir = os.path.normcase(dir) 

252 if normdir not in seen: 

253 seen.add(normdir) 

254 for thefile in files: 

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

256 if _access_check(name, mode): 

257 return name 

258 return None 

259 

260 

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

262 

263from zipfile import ZipFile as BaseZipFile 

264 

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

266 ZipFile = BaseZipFile 

267else: # pragma: no cover 

268 from zipfile import ZipExtFile as BaseZipExtFile 

269 

270 class ZipExtFile(BaseZipExtFile): 

271 

272 def __init__(self, base): 

273 self.__dict__.update(base.__dict__) 

274 

275 def __enter__(self): 

276 return self 

277 

278 def __exit__(self, *exc_info): 

279 self.close() 

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

281 

282 class ZipFile(BaseZipFile): 

283 

284 def __enter__(self): 

285 return self 

286 

287 def __exit__(self, *exc_info): 

288 self.close() 

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

290 

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

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

293 return ZipExtFile(base) 

294 

295 

296try: 

297 from platform import python_implementation 

298except ImportError: # pragma: no cover 

299 

300 def python_implementation(): 

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

302 if 'PyPy' in sys.version: 

303 return 'PyPy' 

304 if os.name == 'java': 

305 return 'Jython' 

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

307 return 'IronPython' 

308 return 'CPython' 

309 

310 

311import sysconfig 

312 

313try: 

314 callable = callable 

315except NameError: # pragma: no cover 

316 from collections.abc import Callable 

317 

318 def callable(obj): 

319 return isinstance(obj, Callable) 

320 

321 

322try: 

323 fsencode = os.fsencode 

324 fsdecode = os.fsdecode 

325except AttributeError: # pragma: no cover 

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

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

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

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

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

331 # nl_langinfo(CODESET) failed." 

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

333 if _fsencoding == 'mbcs': 

334 _fserrors = 'strict' 

335 else: 

336 _fserrors = 'surrogateescape' 

337 

338 def fsencode(filename): 

339 if isinstance(filename, bytes): 

340 return filename 

341 elif isinstance(filename, text_type): 

342 return filename.encode(_fsencoding, _fserrors) 

343 else: 

344 raise TypeError("expect bytes or str, not %s" % type(filename).__name__) 

345 

346 def fsdecode(filename): 

347 if isinstance(filename, text_type): 

348 return filename 

349 elif isinstance(filename, bytes): 

350 return filename.decode(_fsencoding, _fserrors) 

351 else: 

352 raise TypeError("expect bytes or str, not %s" % type(filename).__name__) 

353 

354 

355try: 

356 from tokenize import detect_encoding 

357except ImportError: # pragma: no cover 

358 from codecs import BOM_UTF8, lookup 

359 

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

361 

362 def _get_normal_name(orig_enc): 

363 """Imitates get_normal_name in tokenizer.c.""" 

364 # Only care about the first 12 characters. 

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

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

367 return "utf-8" 

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

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

370 return "iso-8859-1" 

371 return orig_enc 

372 

373 def detect_encoding(readline): 

374 """ 

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

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

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

378 

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

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

381 

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

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

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

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

386 'utf-8-sig' is returned. 

387 

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

389 """ 

390 try: 

391 filename = readline.__self__.name 

392 except AttributeError: 

393 filename = None 

394 bom_found = False 

395 encoding = None 

396 default = 'utf-8' 

397 

398 def read_or_stop(): 

399 try: 

400 return readline() 

401 except StopIteration: 

402 return b'' 

403 

404 def find_cookie(line): 

405 try: 

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

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

408 # per default encoding. 

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

410 except UnicodeDecodeError: 

411 msg = "invalid or missing encoding declaration" 

412 if filename is not None: 

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

414 raise SyntaxError(msg) 

415 

416 matches = cookie_re.findall(line_string) 

417 if not matches: 

418 return None 

419 encoding = _get_normal_name(matches[0]) 

420 try: 

421 codec = lookup(encoding) 

422 except LookupError: 

423 # This behaviour mimics the Python interpreter 

424 if filename is None: 

425 msg = "unknown encoding: " + encoding 

426 else: 

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

428 raise SyntaxError(msg) 

429 

430 if bom_found: 

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

432 # This behaviour mimics the Python interpreter 

433 if filename is None: 

434 msg = 'Encoding problem: utf-8' 

435 else: 

436 msg = 'Encoding problem for %r: utf-8' % filename 

437 raise SyntaxError(msg) 

438 encoding += '-sig' 

439 return encoding 

440 

441 first = read_or_stop() 

442 if first.startswith(BOM_UTF8): 

443 bom_found = True 

444 first = first[3:] 

445 default = 'utf-8-sig' 

446 if not first: 

447 return default, [] 

448 

449 encoding = find_cookie(first) 

450 if encoding: 

451 return encoding, [first] 

452 

453 second = read_or_stop() 

454 if not second: 

455 return default, [first] 

456 

457 encoding = find_cookie(second) 

458 if encoding: 

459 return encoding, [first, second] 

460 

461 return default, [first, second] 

462 

463 

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

465try: 

466 from html import escape 

467except ImportError: 

468 from cgi import escape 

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

470 unescape = HTMLParser().unescape 

471else: 

472 from html import unescape 

473 

474try: 

475 from collections import ChainMap 

476except ImportError: # pragma: no cover 

477 from collections import MutableMapping 

478 

479 try: 

480 from reprlib import recursive_repr as _recursive_repr 

481 except ImportError: 

482 

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

484 ''' 

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

486 call 

487 ''' 

488 

489 def decorating_function(user_function): 

490 repr_running = set() 

491 

492 def wrapper(self): 

493 key = id(self), get_ident() 

494 if key in repr_running: 

495 return fillvalue 

496 repr_running.add(key) 

497 try: 

498 result = user_function(self) 

499 finally: 

500 repr_running.discard(key) 

501 return result 

502 

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

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

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

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

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

508 return wrapper 

509 

510 return decorating_function 

511 

512 class ChainMap(MutableMapping): 

513 ''' 

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

515 to create a single, updateable view. 

516 

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

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

519 

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

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

522 mapping. 

523 ''' 

524 

525 def __init__(self, *maps): 

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

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

528 

529 ''' 

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

531 

532 def __missing__(self, key): 

533 raise KeyError(key) 

534 

535 def __getitem__(self, key): 

536 for mapping in self.maps: 

537 try: 

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

539 except KeyError: 

540 pass 

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

542 

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

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

545 

546 def __len__(self): 

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

548 

549 def __iter__(self): 

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

551 

552 def __contains__(self, key): 

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

554 

555 def __bool__(self): 

556 return any(self.maps) 

557 

558 @_recursive_repr() 

559 def __repr__(self): 

560 return '{0.__class__.__name__}({1})'.format(self, ', '.join(map(repr, self.maps))) 

561 

562 @classmethod 

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

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

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

566 

567 def copy(self): 

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

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

570 

571 __copy__ = copy 

572 

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

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

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

576 

577 @property 

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

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

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

581 

582 def __setitem__(self, key, value): 

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

584 

585 def __delitem__(self, key): 

586 try: 

587 del self.maps[0][key] 

588 except KeyError: 

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

590 

591 def popitem(self): 

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

593 try: 

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

595 except KeyError: 

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

597 

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

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

600 try: 

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

602 except KeyError: 

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

604 

605 def clear(self): 

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

607 self.maps[0].clear() 

608 

609 

610try: 

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

612except ImportError: # pragma: no cover 

613 

614 def cache_from_source(path, debug_override=None, optimization=None): 

615 assert path.endswith('.py') 

616 if debug_override is None: 

617 debug_override = __debug__ 

618 if debug_override: 

619 suffix = 'c' 

620 else: 

621 suffix = 'o' 

622 return path + suffix 

623 

624 

625try: 

626 from collections import OrderedDict 

627except ImportError: # pragma: no cover 

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

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

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

631 try: 

632 from thread import get_ident as _get_ident 

633 except ImportError: 

634 from dummy_thread import get_ident as _get_ident 

635 

636 try: 

637 from _abcoll import KeysView, ValuesView, ItemsView 

638 except ImportError: 

639 pass 

640 

641 class OrderedDict(dict): 

642 'Dictionary that remembers insertion order' 

643 

644 # An inherited dict maps keys to values. 

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

646 # The remaining methods are order-aware. 

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

648 

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

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

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

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

653 

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

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

656 regular dictionaries, but keyword arguments are not recommended 

657 because their insertion order is arbitrary. 

658 

659 ''' 

660 if len(args) > 1: 

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

662 try: 

663 self.__root 

664 except AttributeError: 

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

666 root[:] = [root, root, None] 

667 self.__map = {} 

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

669 

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

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

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

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

674 if key not in self: 

675 root = self.__root 

676 last = root[0] 

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

678 dict_setitem(self, key, value) 

679 

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

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

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

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

684 dict_delitem(self, key) 

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

686 link_prev[1] = link_next 

687 link_next[0] = link_prev 

688 

689 def __iter__(self): 

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

691 root = self.__root 

692 curr = root[1] 

693 while curr is not root: 

694 yield curr[2] 

695 curr = curr[1] 

696 

697 def __reversed__(self): 

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

699 root = self.__root 

700 curr = root[0] 

701 while curr is not root: 

702 yield curr[2] 

703 curr = curr[0] 

704 

705 def clear(self): 

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

707 try: 

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

709 del node[:] 

710 root = self.__root 

711 root[:] = [root, root, None] 

712 self.__map.clear() 

713 except AttributeError: 

714 pass 

715 dict.clear(self) 

716 

717 def popitem(self, last=True): 

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

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

720 

721 ''' 

722 if not self: 

723 raise KeyError('dictionary is empty') 

724 root = self.__root 

725 if last: 

726 link = root[0] 

727 link_prev = link[0] 

728 link_prev[1] = root 

729 root[0] = link_prev 

730 else: 

731 link = root[1] 

732 link_next = link[1] 

733 root[1] = link_next 

734 link_next[0] = root 

735 key = link[2] 

736 del self.__map[key] 

737 value = dict.pop(self, key) 

738 return key, value 

739 

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

741 

742 def keys(self): 

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

744 return list(self) 

745 

746 def values(self): 

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

748 return [self[key] for key in self] 

749 

750 def items(self): 

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

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

753 

754 def iterkeys(self): 

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

756 return iter(self) 

757 

758 def itervalues(self): 

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

760 for k in self: 

761 yield self[k] 

762 

763 def iteritems(self): 

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

765 for k in self: 

766 yield (k, self[k]) 

767 

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

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

770 

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

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

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

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

775 

776 ''' 

777 if len(args) > 2: 

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

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

780 elif not args: 

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

782 self = args[0] 

783 # Make progressively weaker assumptions about "other" 

784 other = () 

785 if len(args) == 2: 

786 other = args[1] 

787 if isinstance(other, dict): 

788 for key in other: 

789 self[key] = other[key] 

790 elif hasattr(other, 'keys'): 

791 for key in other.keys(): 

792 self[key] = other[key] 

793 else: 

794 for key, value in other: 

795 self[key] = value 

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

797 self[key] = value 

798 

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

800 

801 __marker = object() 

802 

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

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

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

806 

807 ''' 

808 if key in self: 

809 result = self[key] 

810 del self[key] 

811 return result 

812 if default is self.__marker: 

813 raise KeyError(key) 

814 return default 

815 

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

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

818 if key in self: 

819 return self[key] 

820 self[key] = default 

821 return default 

822 

823 def __repr__(self, _repr_running=None): 

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

825 if not _repr_running: 

826 _repr_running = {} 

827 call_key = id(self), _get_ident() 

828 if call_key in _repr_running: 

829 return '...' 

830 _repr_running[call_key] = 1 

831 try: 

832 if not self: 

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

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

835 finally: 

836 del _repr_running[call_key] 

837 

838 def __reduce__(self): 

839 'Return state information for pickling' 

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

841 inst_dict = vars(self).copy() 

842 for k in vars(OrderedDict()): 

843 inst_dict.pop(k, None) 

844 if inst_dict: 

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

846 return self.__class__, (items, ) 

847 

848 def copy(self): 

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

850 return self.__class__(self) 

851 

852 @classmethod 

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

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

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

856 

857 ''' 

858 d = cls() 

859 for key in iterable: 

860 d[key] = value 

861 return d 

862 

863 def __eq__(self, other): 

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

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

866 

867 ''' 

868 if isinstance(other, OrderedDict): 

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

870 return dict.__eq__(self, other) 

871 

872 def __ne__(self, other): 

873 return not self == other 

874 

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

876 

877 def viewkeys(self):