test/csit/libraries/ipaddr.py

   1 #!/usr/bin/python
   2 #
   3 # Copyright 2007 Google Inc.
   4 #  Licensed to PSF under a Contributor Agreement.
   5 #
   6 # Licensed under the Apache License, Version 2.0 (the "License");
   7 # you may not use this file except in compliance with the License.
   8 # You may obtain a copy of the License at
   9 #
  10 #      http://www.apache.org/licenses/LICENSE-2.0
  11 #
  12 # Unless required by applicable law or agreed to in writing, software
  13 # distributed under the License is distributed on an "AS IS" BASIS,
  14 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
  15 # implied. See the License for the specific language governing
  16 # permissions and limitations under the License.
  17
  18 """A fast, lightweight IPv4/IPv6 manipulation library in Python.
  19
  20 This library is used to create/poke/manipulate IPv4 and IPv6 addresses
  21 and networks.
  22
  23 """
  24
  25 __version__ = '2.1.10'
  26
  27 import struct
  28
  29 IPV4LENGTH = 32
  30 IPV6LENGTH = 128
  31
  32
  33 class AddressValueError(ValueError):
  34     """A Value Error related to the address."""
  35
  36
  37 class NetmaskValueError(ValueError):
  38     """A Value Error related to the netmask."""
  39
  40
  41 def IPAddress(address, version=None):
  42     """Take an IP string/int and return an object of the correct type.
  43
  44     Args:
  45         address: A string or integer, the IP address.  Either IPv4 or
  46           IPv6 addresses may be supplied; integers less than 2**32 will
  47           be considered to be IPv4 by default.
  48         version: An Integer, 4 or 6. If set, don't try to automatically
  49           determine what the IP address type is. important for things
  50           like IPAddress(1), which could be IPv4, '0.0.0.1',  or IPv6,
  51           '::1'.
  52
  53     Returns:
  54         An IPv4Address or IPv6Address object.
  55
  56     Raises:
  57         ValueError: if the string passed isn't either a v4 or a v6
  58           address.
  59
  60     """
  61     if version:
  62         if version == 4:
  63             return IPv4Address(address)
  64         elif version == 6:
  65             return IPv6Address(address)
  66
  67     try:
  68         return IPv4Address(address)
  69     except (AddressValueError, NetmaskValueError):
  70         pass
  71
  72     try:
  73         return IPv6Address(address)
  74     except (AddressValueError, NetmaskValueError):
  75         pass
  76
  77     raise ValueError('%r does not appear to be an IPv4 or IPv6 address' %
  78                      address)
  79
  80
  81 def IPNetwork(address, version=None, strict=False):
  82     """Take an IP string/int and return an object of the correct type.
  83
  84     Args:
  85         address: A string or integer, the IP address.  Either IPv4 or
  86           IPv6 addresses may be supplied; integers less than 2**32 will
  87           be considered to be IPv4 by default.
  88         version: An Integer, if set, don't try to automatically
  89           determine what the IP address type is. important for things
  90           like IPNetwork(1), which could be IPv4, '0.0.0.1/32', or IPv6,
  91           '::1/128'.
  92
  93     Returns:
  94         An IPv4Network or IPv6Network object.
  95
  96     Raises:
  97         ValueError: if the string passed isn't either a v4 or a v6
  98           address. Or if a strict network was requested and a strict
  99           network wasn't given.
 100
 101     """
 102     if version:
 103         if version == 4:
 104             return IPv4Network(address, strict)
 105         elif version == 6:
 106             return IPv6Network(address, strict)
 107
 108     try:
 109         return IPv4Network(address, strict)
 110     except (AddressValueError, NetmaskValueError):
 111         pass
 112
 113     try:
 114         return IPv6Network(address, strict)
 115     except (AddressValueError, NetmaskValueError):
 116         pass
 117
 118     raise ValueError('%r does not appear to be an IPv4 or IPv6 network' %
 119                      address)
 120
 121
 122 def v4_int_to_packed(address):
 123     """The binary representation of this address.
 124
 125     Args:
 126         address: An integer representation of an IPv4 IP address.
 127
 128     Returns:
 129         The binary representation of this address.
 130
 131     Raises:
 132         ValueError: If the integer is too large to be an IPv4 IP
 133           address.
 134     """
 135     if address > _BaseV4._ALL_ONES:
 136         raise ValueError('Address too large for IPv4')
 137     return Bytes(struct.pack('!I', address))
 138
 139
 140 def v6_int_to_packed(address):
 141     """The binary representation of this address.
 142
 143     Args:
 144         address: An integer representation of an IPv4 IP address.
 145
 146     Returns:
 147         The binary representation of this address.
 148     """
 149     return Bytes(struct.pack('!QQ', address >> 64, address & (2**64 - 1)))
 150
 151
 152 def _find_address_range(addresses):
 153     """Find a sequence of addresses.
 154
 155     Args:
 156         addresses: a list of IPv4 or IPv6 addresses.
 157
 158     Returns:
 159         A tuple containing the first and last IP addresses in the sequence.
 160
 161     """
 162     first = last = addresses[0]
 163     for ip in addresses[1:]:
 164         if ip._ip == last._ip + 1:
 165             last = ip
 166         else:
 167             break
 168     return (first, last)
 169
 170
 171 def _get_prefix_length(number1, number2, bits):
 172     """Get the number of leading bits that are same for two numbers.
 173
 174     Args:
 175         number1: an integer.
 176         number2: another integer.
 177         bits: the maximum number of bits to compare.
 178
 179     Returns:
 180         The number of leading bits that are the same for two numbers.
 181
 182     """
 183     for i in range(bits):
 184         if number1 >> i == number2 >> i:
 185             return bits - i
 186     return 0
 187
 188
 189 def _count_righthand_zero_bits(number, bits):
 190     """Count the number of zero bits on the right hand side.
 191
 192     Args:
 193         number: an integer.
 194         bits: maximum number of bits to count.
 195
 196     Returns:
 197         The number of zero bits on the right hand side of the number.
 198
 199     """
 200     if number == 0:
 201         return bits
 202     for i in range(bits):
 203         if (number >> i) % 2:
 204             return i
 205
 206
 207 def summarize_address_range(first, last):
 208     """Summarize a network range given the first and last IP addresses.
 209
 210     Example:
 211         >>> summarize_address_range(IPv4Address('1.1.1.0'),
 212             IPv4Address('1.1.1.130'))
 213         [IPv4Network('1.1.1.0/25'), IPv4Network('1.1.1.128/31'),
 214         IPv4Network('1.1.1.130/32')]
 215
 216     Args:
 217         first: the first IPv4Address or IPv6Address in the range.
 218         last: the last IPv4Address or IPv6Address in the range.
 219
 220     Returns:
 221         The address range collapsed to a list of IPv4Network's or
 222         IPv6Network's.
 223
 224     Raise:
 225         TypeError:
 226             If the first and last objects are not IP addresses.
 227             If the first and last objects are not the same version.
 228         ValueError:
 229             If the last object is not greater than the first.
 230             If the version is not 4 or 6.
 231
 232     """
 233     if not (isinstance(first, _BaseIP) and isinstance(last, _BaseIP)):
 234         raise TypeError('first and last must be IP addresses, not networks')
 235     if first.version != last.version:
 236         raise TypeError("%s and %s are not of the same version" % (
 237             str(first), str(last)))
 238     if first > last:
 239         raise ValueError('last IP address must be greater than first')
 240
 241     networks = []
 242
 243     if first.version == 4:
 244         ip = IPv4Network
 245     elif first.version == 6:
 246         ip = IPv6Network
 247     else:
 248         raise ValueError('unknown IP version')
 249
 250     ip_bits = first._max_prefixlen
 251     first_int = first._ip
 252     last_int = last._ip
 253     while first_int <= last_int:
 254         nbits = _count_righthand_zero_bits(first_int, ip_bits)
 255         current = None
 256         while nbits >= 0:
 257             addend = 2**nbits - 1
 258             current = first_int + addend
 259             nbits -= 1
 260             if current <= last_int:
 261                 break
 262         prefix = _get_prefix_length(first_int, current, ip_bits)
 263         net = ip('%s/%d' % (str(first), prefix))
 264         networks.append(net)
 265         if current == ip._ALL_ONES:
 266             break
 267         first_int = current + 1
 268         first = IPAddress(first_int, version=first._version)
 269     return networks
 270
 271
 272 def _collapse_address_list_recursive(addresses):
 273     """Loops through the addresses, collapsing concurrent netblocks.
 274
 275     Example:
 276
 277         ip1 = IPv4Network('1.1.0.0/24')
 278         ip2 = IPv4Network('1.1.1.0/24')
 279         ip3 = IPv4Network('1.1.2.0/24')
 280         ip4 = IPv4Network('1.1.3.0/24')
 281         ip5 = IPv4Network('1.1.4.0/24')
 282         ip6 = IPv4Network('1.1.0.1/22')
 283
 284         _collapse_address_list_recursive([ip1, ip2, ip3, ip4, ip5, ip6]) ->
 285           [IPv4Network('1.1.0.0/22'), IPv4Network('1.1.4.0/24')]
 286
 287         This shouldn't be called directly; it is called via
 288           collapse_address_list([]).
 289
 290     Args:
 291         addresses: A list of IPv4Network's or IPv6Network's
 292
 293     Returns:
 294         A list of IPv4Network's or IPv6Network's depending on what we were
 295         passed.
 296
 297     """
 298     ret_array = []
 299     optimized = False
 300
 301     for cur_addr in addresses:
 302         if not ret_array:
 303             ret_array.append(cur_addr)
 304             continue
 305         if cur_addr in ret_array[-1]:
 306             optimized = True
 307         elif cur_addr == ret_array[-1].supernet().subnet()[1]:
 308             ret_array.append(ret_array.pop().supernet())
 309             optimized = True
 310         else:
 311             ret_array.append(cur_addr)
 312
 313     if optimized:
 314         return _collapse_address_list_recursive(ret_array)
 315
 316     return ret_array
 317
 318
 319 def collapse_address_list(addresses):
 320     """Collapse a list of IP objects.
 321
 322     Example:
 323         collapse_address_list([IPv4('1.1.0.0/24'), IPv4('1.1.1.0/24')]) ->
 324           [IPv4('1.1.0.0/23')]
 325
 326     Args:
 327         addresses: A list of IPv4Network or IPv6Network objects.
 328
 329     Returns:
 330         A list of IPv4Network or IPv6Network objects depending on what we
 331         were passed.
 332
 333     Raises:
 334         TypeError: If passed a list of mixed version objects.
 335
 336     """
 337     i = 0
 338     addrs = []
 339     ips = []
 340     nets = []
 341
 342     # split IP addresses and networks
 343     for ip in addresses:
 344         if isinstance(ip, _BaseIP):
 345             if ips and ips[-1]._version != ip._version:
 346                 raise TypeError("%s and %s are not of the same version" % (
 347                     str(ip), str(ips[-1])))
 348             ips.append(ip)
 349         elif ip._prefixlen == ip._max_prefixlen:
 350             if ips and ips[-1]._version != ip._version:
 351                 raise TypeError("%s and %s are not of the same version" % (
 352                     str(ip), str(ips[-1])))
 353             ips.append(ip.ip)
 354         else:
 355             if nets and nets[-1]._version != ip._version:
 356                 raise TypeError("%s and %s are not of the same version" % (
 357                     str(ip), str(ips[-1])))
 358             nets.append(ip)
 359
 360     # sort and dedup
 361     ips = sorted(set(ips))
 362     nets = sorted(set(nets))
 363
 364     while i < len(ips):
 365         (first, last) = _find_address_range(ips[i:])
 366         i = ips.index(last) + 1
 367         addrs.extend(summarize_address_range(first, last))
 368
 369     return _collapse_address_list_recursive(sorted(
 370         addrs + nets, key=_BaseNet._get_networks_key))
 371
 372 # backwards compatibility
 373 CollapseAddrList = collapse_address_list
 374
 375 # We need to distinguish between the string and packed-bytes representations
 376 # of an IP address.  For example, b'0::1' is the IPv4 address 48.58.58.49,
 377 # while '0::1' is an IPv6 address.
 378 #
 379 # In Python 3, the native 'bytes' type already provides this functionality,
 380 # so we use it directly.  For earlier implementations where bytes is not a
 381 # distinct type, we create a subclass of str to serve as a tag.
 382 #
 383 # Usage example (Python 2):
 384 #   ip = ipaddr.IPAddress(ipaddr.Bytes('xxxx'))
 385 #
 386 # Usage example (Python 3):
 387 #   ip = ipaddr.IPAddress(b'xxxx')
 388 try:
 389     if bytes is str:
 390         raise TypeError("bytes is not a distinct type")
 391     Bytes = bytes
 392 except (NameError, TypeError):
 393     class Bytes(str):
 394         def __repr__(self):
 395             return 'Bytes(%s)' % str.__repr__(self)
 396
 397
 398 def get_mixed_type_key(obj):
 399     """Return a key suitable for sorting between networks and addresses.
 400
 401     Address and Network objects are not sortable by default; they're
 402     fundamentally different so the expression
 403
 404         IPv4Address('1.1.1.1') <= IPv4Network('1.1.1.1/24')
 405
 406     doesn't make any sense.  There are some times however, where you may wish
 407     to have ipaddr sort these for you anyway. If you need to do this, you
 408     can use this function as the key= argument to sorted().
 409
 410     Args:
 411       obj: either a Network or Address object.
 412     Returns:
 413       appropriate key.
 414
 415     """
 416     if isinstance(obj, _BaseNet):
 417         return obj._get_networks_key()
 418     elif isinstance(obj, _BaseIP):
 419         return obj._get_address_key()
 420     return NotImplemented
 421
 422
 423 class _IPAddrBase(object):
 424
 425     """The mother class."""
 426
 427     def __index__(self):
 428         return self._ip
 429
 430     def __int__(self):
 431         return self._ip
 432
 433     def __hex__(self):
 434         return hex(self._ip)
 435
 436     @property
 437     def exploded(self):
 438         """Return the longhand version of the IP address as a string."""
 439         return self._explode_shorthand_ip_string()
 440
 441     @property
 442     def compressed(self):
 443         """Return the shorthand version of the IP address as a string."""
 444         return str(self)
 445
 446
 447 class _BaseIP(_IPAddrBase):
 448
 449     """A generic IP object.
 450
 451     This IP class contains the version independent methods which are
 452     used by single IP addresses.
 453
 454     """
 455
 456     def __eq__(self, other):
 457         try:
 458             return (self._ip == other._ip
 459                     and self._version == other._version)
 460         except AttributeError:
 461             return NotImplemented
 462
 463     def __ne__(self, other):
 464         eq = self.__eq__(other)
 465         if eq is NotImplemented:
 466             return NotImplemented
 467         return not eq
 468
 469     def __le__(self, other):
 470         gt = self.__gt__(other)
 471         if gt is NotImplemented:
 472             return NotImplemented
 473         return not gt
 474
 475     def __ge__(self, other):
 476         lt = self.__lt__(other)
 477         if lt is NotImplemented:
 478             return NotImplemented
 479         return not lt
 480
 481     def __lt__(self, other):
 482         if self._version != other._version:
 483             raise TypeError('%s and %s are not of the same version' % (
 484                 str(self), str(other)))
 485         if not isinstance(other, _BaseIP):
 486             raise TypeError('%s and %s are not of the same type' % (
 487                 str(self), str(other)))
 488         if self._ip != other._ip:
 489             return self._ip < other._ip
 490         return False
 491
 492     def __gt__(self, other):
 493         if self._version != other._version:
 494             raise TypeError('%s and %s are not of the same version' % (
 495                 str(self), str(other)))
 496         if not isinstance(other, _BaseIP):
 497             raise TypeError('%s and %s are not of the same type' % (
 498                 str(self), str(other)))
 499         if self._ip != other._ip:
 500             return self._ip > other._ip
 501         return False
 502
 503     # Shorthand for Integer addition and subtraction. This is not
 504     # meant to ever support addition/subtraction of addresses.
 505     def __add__(self, other):
 506         if not isinstance(other, int):
 507             return NotImplemented
 508         return IPAddress(int(self) + other, version=self._version)
 509
 510     def __sub__(self, other):
 511         if not isinstance(other, int):
 512             return NotImplemented
 513         return IPAddress(int(self) - other, version=self._version)
 514
 515     def __repr__(self):
 516         return '%s(%r)' % (self.__class__.__name__, str(self))
 517
 518     def __str__(self):
 519         return '%s' % self._string_from_ip_int(self._ip)
 520
 521     def __hash__(self):
 522         return hash(hex(long(self._ip)))
 523
 524     def _get_address_key(self):
 525         return (self._version, self)
 526
 527     @property
 528     def version(self):
 529         raise NotImplementedError('BaseIP has no version')
 530
 531
 532 class _BaseNet(_IPAddrBase):
 533
 534     """A generic IP object.
 535
 536     This IP class contains the version independent methods which are
 537     used by networks.
 538
 539     """
 540
 541     def __init__(self, address):
 542         self._cache = {}
 543
 544     def __repr__(self):
 545         return '%s(%r)' % (self.__class__.__name__, str(self))
 546
 547     def iterhosts(self):
 548         """Generate Iterator over usable hosts in a network.
 549
 550            This is like __iter__ except it doesn't return the network
 551            or broadcast addresses.
 552
 553         """
 554         cur = int(self.network) + 1
 555         bcast = int(self.broadcast) - 1
 556         while cur <= bcast:
 557             cur += 1
 558             yield IPAddress(cur - 1, version=self._version)
 559
 560     def __iter__(self):
 561         cur = int(self.network)
 562         bcast = int(self.broadcast)
 563         while cur <= bcast:
 564             cur += 1
 565             yield IPAddress(cur - 1, version=self._version)
 566
 567     def __getitem__(self, n):
 568         network = int(self.network)
 569         broadcast = int(self.broadcast)
 570         if n >= 0:
 571             if network + n > broadcast:
 572                 raise IndexError
 573             return IPAddress(network + n, version=self._version)
 574         else:
 575             n += 1
 576             if broadcast + n < network:
 577                 raise IndexError
 578             return IPAddress(broadcast + n, version=self._version)
 579
 580     def __lt__(self, other):
 581         if self._version != other._version:
 582             raise TypeError('%s and %s are not of the same version' % (
 583                 str(self), str(other)))
 584         if not isinstance(other, _BaseNet):
 585             raise TypeError('%s and %s are not of the same type' % (
 586                 str(self), str(other)))
 587         if self.network != other.network:
 588             return self.network < other.network
 589         if self.netmask != other.netmask:
 590             return self.netmask < other.netmask
 591         return False
 592
 593     def __gt__(self, other):
 594         if self._version != other._version:
 595             raise TypeError('%s and %s are not of the same version' % (
 596                 str(self), str(other)))
 597         if not isinstance(other, _BaseNet):
 598             raise TypeError('%s and %s are not of the same type' % (
 599                 str(self), str(other)))
 600         if self.network != other.network:
 601             return self.network > other.network
 602         if self.netmask != other.netmask:
 603             return self.netmask > other.netmask
 604         return False
 605
 606     def __le__(self, other):
 607         gt = self.__gt__(other)
 608         if gt is NotImplemented:
 609             return NotImplemented
 610         return not gt
 611
 612     def __ge__(self, other):
 613         lt = self.__lt__(other)
 614         if lt is NotImplemented:
 615             return NotImplemented
 616         return not lt
 617
 618     def __eq__(self, other):
 619         try:
 620             return (self._version == other._version
 621                     and self.network == other.network
 622                     and int(self.netmask) == int(other.netmask))
 623         except AttributeError:
 624             if isinstance(other, _BaseIP):
 625                 return (self._version == other._version
 626                         and self._ip == other._ip)
 627
 628     def __ne__(self, other):
 629         eq = self.__eq__(other)
 630         if eq is NotImplemented:
 631             return NotImplemented
 632         return not eq
 633
 634     def __str__(self):
 635         return '%s/%s' % (str(self.ip),
 636                           str(self._prefixlen))
 637
 638     def __hash__(self):
 639         return hash(int(self.network) ^ int(self.netmask))
 640
 641     def __contains__(self, other):
 642         # always false if one is v4 and the other is v6.
 643         if self._version != other._version:
 644             return False
 645         # dealing with another network.
 646         if isinstance(other, _BaseNet):
 647             return (self.network <= other.network and
 648                     self.broadcast >= other.broadcast)
 649         # dealing with another address
 650         else:
 651             return (int(self.network) <= int(other._ip) <=
 652                     int(self.broadcast))
 653
 654     def overlaps(self, other):
 655         """Tell if self is partly contained in other."""
 656         return self.network in other or self.broadcast in other or (
 657             other.network in self or other.broadcast in self)
 658
 659     @property
 660     def network(self):
 661         x = self._cache.get('network')
 662         if x is None:
 663             x = IPAddress(self._ip & int(self.netmask), version=self._version)
 664             self._cache['network'] = x
 665         return x
 666
 667     @property
 668     def broadcast(self):
 669         x = self._cache.get('broadcast')
 670         if x is None:
 671             x = IPAddress(self._ip | int(self.hostmask), version=self._version)
 672             self._cache['broadcast'] = x
 673         return x
 674
 675     @property
 676     def hostmask(self):
 677         x = self._cache.get('hostmask')
 678         if x is None:
 679             x = IPAddress(int(self.netmask) ^ self._ALL_ONES,
 680                           version=self._version)
 681             self._cache['hostmask'] = x
 682         return x
 683
 684     @property
 685     def with_prefixlen(self):
 686         return '%s/%d' % (str(self.ip), self._prefixlen)
 687
 688     @property
 689     def with_netmask(self):
 690         return '%s/%s' % (str(self.ip), str(self.netmask))
 691
 692     @property
 693     def with_hostmask(self):
 694         return '%s/%s' % (str(self.ip), str(self.hostmask))
 695
 696     @property
 697     def numhosts(self):
 698         """Number of hosts in the current subnet."""
 699         return int(self.broadcast) - int(self.network) + 1
 700
 701     @property
 702     def version(self):
 703         raise NotImplementedError('BaseNet has no version')
 704
 705     @property
 706     def prefixlen(self):
 707         return self._prefixlen
 708
 709     def address_exclude(self, other):
 710         """Remove an address from a larger block.
 711
 712         For example:
 713
 714             addr1 = IPNetwork('10.1.1.0/24')
 715             addr2 = IPNetwork('10.1.1.0/26')
 716             addr1.address_exclude(addr2) =
 717                 [IPNetwork('10.1.1.64/26'), IPNetwork('10.1.1.128/25')]
 718
 719         or IPv6:
 720
 721             addr1 = IPNetwork('::1/32')
 722             addr2 = IPNetwork('::1/128')
 723             addr1.address_exclude(addr2) = [IPNetwork('::0/128'),
 724                 IPNetwork('::2/127'),
 725                 IPNetwork('::4/126'),
 726                 IPNetwork('::8/125'),
 727                 ...
 728                 IPNetwork('0:0:8000::/33')]
 729
 730         Args:
 731             other: An IPvXNetwork object of the same type.
 732
 733         Returns:
 734             A sorted list of IPvXNetwork objects addresses which is self
 735             minus other.
 736
 737         Raises:
 738             TypeError: If self and other are of difffering address
 739               versions, or if other is not a network object.
 740             ValueError: If other is not completely contained by self.
 741
 742         """
 743         if not self._version == other._version:
 744             raise TypeError("%s and %s are not of the same version" % (
 745                 str(self), str(other)))
 746
 747         if not isinstance(other, _BaseNet):
 748             raise TypeError("%s is not a network object" % str(other))
 749
 750         if other not in self:
 751             raise ValueError('%s not contained in %s' % (str(other),
 752                                                          str(self)))
 753         if other == self:
 754             return []
 755
 756         ret_addrs = []
 757
 758         # Make sure we're comparing the network of other.
 759         other = IPNetwork('%s/%s' % (str(other.network), str(other.prefixlen)),
 760                           version=other._version)
 761
 762         s1, s2 = self.subnet()
 763         while s1 != other and s2 != other:
 764             if other in s1:
 765                 ret_addrs.append(s2)
 766                 s1, s2 = s1.subnet()
 767             elif other in s2:
 768                 ret_addrs.append(s1)
 769                 s1, s2 = s2.subnet()
 770             else:
 771                 # If we got here, there's a bug somewhere.
 772                 assert True is False, ('Error performing exclusion: '
 773                                        's1: %s s2: %s other: %s' %
 774                                        (str(s1), str(s2), str(other)))
 775         if s1 == other:
 776             ret_addrs.append(s2)
 777         elif s2 == other:
 778             ret_addrs.append(s1)
 779         else:
 780             # If we got here, there's a bug somewhere.
 781             assert True is False, ('Error performing exclusion: '
 782                                    's1: %s s2: %s other: %s' %
 783                                    (str(s1), str(s2), str(other)))
 784
 785         return sorted(ret_addrs, key=_BaseNet._get_networks_key)
 786
 787     def compare_networks(self, other):
 788         """Compare two IP objects.
 789
 790         This is only concerned about the comparison of the integer
 791         representation of the network addresses.  This means that the
 792         host bits aren't considered at all in this method.  If you want
 793         to compare host bits, you can easily enough do a
 794         'HostA._ip < HostB._ip'
 795
 796         Args:
 797             other: An IP object.
 798
 799         Returns:
 800             If the IP versions of self and other are the same, returns:
 801
 802             -1 if self < other:
 803               eg: IPv4('1.1.1.0/24') < IPv4('1.1.2.0/24')
 804               IPv6('1080::200C:417A') < IPv6('1080::200B:417B')
 805             0 if self == other
 806               eg: IPv4('1.1.1.1/24') == IPv4('1.1.1.2/24')
 807               IPv6('1080::200C:417A/96') == IPv6('1080::200C:417B/96')
 808             1 if self > other
 809               eg: IPv4('1.1.1.0/24') > IPv4('1.1.0.0/24')
 810               IPv6('1080::1:200C:417A/112') >
 811               IPv6('1080::0:200C:417A/112')
 812
 813             If the IP versions of self and other are different, returns:
 814
 815             -1 if self._version < other._version
 816               eg: IPv4('10.0.0.1/24') < IPv6('::1/128')
 817             1 if self._version > other._version
 818               eg: IPv6('::1/128') > IPv4('255.255.255.0/24')
 819
 820         """
 821         if self._version < other._version:
 822             return -1
 823         if self._version > other._version:
 824             return 1
 825         # self._version == other._version below here:
 826         if self.network < other.network:
 827             return -1
 828         if self.network > other.network:
 829             return 1
 830         # self.network == other.network below here:
 831         if self.netmask < other.netmask:
 832             return -1
 833         if self.netmask > other.netmask:
 834             return 1
 835         # self.network == other.network and self.netmask == other.netmask
 836         return 0
 837
 838     def _get_networks_key(self):
 839         """Network-only key function.
 840
 841         Returns an object that identifies this address' network and
 842         netmask. This function is a suitable "key" argument for sorted()
 843         and list.sort().
 844
 845         """
 846         return (self._version, self.network, self.netmask)
 847
 848     def _ip_int_from_prefix(self, prefixlen=None):
 849         """Turn the prefix length netmask into a int for comparison.
 850
 851         Args:
 852             prefixlen: An integer, the prefix length.
 853
 854         Returns:
 855             An integer.
 856
 857         """
 858         if not prefixlen and prefixlen != 0:
 859             prefixlen = self._prefixlen
 860         return self._ALL_ONES ^ (self._ALL_ONES >> prefixlen)
 861
 862     def _prefix_from_ip_int(self, ip_int, mask=32):
 863         """Return prefix length from the decimal netmask.
 864
 865         Args:
 866             ip_int: An integer, the IP address.
 867             mask: The netmask.  Defaults to 32.
 868
 869         Returns:
 870             An integer, the prefix length.
 871
 872         """
 873         while mask:
 874             if ip_int & 1 == 1:
 875                 break
 876             ip_int >>= 1
 877             mask -= 1
 878
 879         return mask
 880
 881     def _ip_string_from_prefix(self, prefixlen=None):
 882         """Turn a prefix length into a dotted decimal string.
 883
 884         Args:
 885             prefixlen: An integer, the netmask prefix length.
 886
 887         Returns:
 888             A string, the dotted decimal netmask string.
 889
 890         """
 891         if not prefixlen:
 892             prefixlen = self._prefixlen
 893         return self._string_from_ip_int(self._ip_int_from_prefix(prefixlen))
 894
 895     def iter_subnets(self, prefixlen_diff=1, new_prefix=None):
 896         """The subnets which join to make the current subnet.
 897
 898         In the case that self contains only one IP
 899         (self._prefixlen == 32 for IPv4 or self._prefixlen == 128
 900         for IPv6), return a list with just ourself.
 901
 902         Args:
 903             prefixlen_diff: An integer, the amount the prefix length
 904               should be increased by. This should not be set if
 905               new_prefix is also set.
 906             new_prefix: The desired new prefix length. This must be a
 907               larger number (smaller prefix) than the existing prefix.
 908               This should not be set if prefixlen_diff is also set.
 909
 910         Returns:
 911             An iterator of IPv(4|6) objects.
 912
 913         Raises:
 914             ValueError: The prefixlen_diff is too small or too large.
 915                 OR
 916             prefixlen_diff and new_prefix are both set or new_prefix
 917               is a smaller number than the current prefix (smaller
 918               number means a larger network)
 919
 920         """
 921         if self._prefixlen == self._max_prefixlen:
 922             yield self
 923             return
 924
 925         if new_prefix is not None:
 926             if new_prefix < self._prefixlen:
 927                 raise ValueError('new prefix must be longer')
 928             if prefixlen_diff != 1:
 929                 raise ValueError('cannot set prefixlen_diff and new_prefix')
 930             prefixlen_diff = new_prefix - self._prefixlen
 931
 932         if prefixlen_diff < 0:
 933             raise ValueError('prefix length diff must be > 0')
 934         new_prefixlen = self._prefixlen + prefixlen_diff
 935
 936         if not self._is_valid_netmask(str(new_prefixlen)):
 937             raise ValueError(
 938                 'prefix length diff %d is invalid for netblock %s' % (
 939                     new_prefixlen, str(self)))
 940
 941         first = IPNetwork('%s/%s' % (str(self.network),
 942                                      str(self._prefixlen + prefixlen_diff)),
 943                           version=self._version)
 944
 945         yield first
 946         current = first
 947         while True:
 948             broadcast = current.broadcast
 949             if broadcast == self.broadcast:
 950                 return
 951             new_addr = IPAddress(int(broadcast) + 1, version=self._version)
 952             current = IPNetwork('%s/%s' % (str(new_addr), str(new_prefixlen)),
 953                                 version=self._version)
 954
 955             yield current
 956
 957     def masked(self):
 958         """Return the network object with the host bits masked out."""
 959         return IPNetwork('%s/%d' % (self.network, self._prefixlen),
 960                          version=self._version)
 961
 962     def subnet(self, prefixlen_diff=1, new_prefix=None):
 963         """Return a list of subnets, rather than an iterator."""
 964         return list(self.iter_subnets(prefixlen_diff, new_prefix))
 965
 966     def supernet(self, prefixlen_diff=1, new_prefix=None):
 967         """The supernet containing the current network.
 968
 969         Args:
 970             prefixlen_diff: An integer, the amount the prefix length of
 971               the network should be decreased by.  For example, given a
 972               /24 network and a prefixlen_diff of 3, a supernet with a
 973               /21 netmask is returned.
 974
 975         Returns:
 976             An IPv4 network object.
 977
 978         Raises:
 979             ValueError: If self.prefixlen - prefixlen_diff < 0. I.e., you have a
 980               negative prefix length.
 981                 OR
 982             If prefixlen_diff and new_prefix are both set or new_prefix is a
 983               larger number than the current prefix (larger number means a
 984               smaller network)
 985
 986         """
 987         if self._prefixlen == 0:
 988             return self
 989
 990         if new_prefix is not None:
 991             if new_prefix > self._prefixlen:
 992                 raise ValueError('new prefix must be shorter')
 993             if prefixlen_diff != 1:
 994                 raise ValueError('cannot set prefixlen_diff and new_prefix')
 995             prefixlen_diff = self._prefixlen - new_prefix
 996
 997         if self.prefixlen - prefixlen_diff < 0:
 998             raise ValueError(
 999                 'current prefixlen is %d, cannot have a prefixlen_diff of %d' %
1000                 (self.prefixlen, prefixlen_diff))
1001         return IPNetwork('%s/%s' % (str(self.network),
1002                                     str(self.prefixlen - prefixlen_diff)),
1003                          version=self._version)
1004
1005     # backwards compatibility
1006     Subnet = subnet
1007     Supernet = supernet
1008     AddressExclude = address_exclude
1009     CompareNetworks = compare_networks
1010     Contains = __contains__
1011
1012
1013 class _BaseV4(object):
1014
1015     """Base IPv4 object.
1016
1017     The following methods are used by IPv4 objects in both single IP
1018     addresses and networks.
1019
1020     """
1021
1022     # Equivalent to 255.255.255.255 or 32 bits of 1's.
1023     _ALL_ONES = (2**IPV4LENGTH) - 1
1024     _DECIMAL_DIGITS = frozenset('0123456789')
1025
1026     def __init__(self, address):
1027         self._version = 4
1028         self._max_prefixlen = IPV4LENGTH
1029
1030     def _explode_shorthand_ip_string(self):
1031         return str(self)
1032
1033     def _ip_int_from_string(self, ip_str):
1034         """Turn the given IP string into an integer for comparison.
1035
1036         Args:
1037             ip_str: A string, the IP ip_str.
1038
1039         Returns:
1040             The IP ip_str as an integer.
1041
1042         Raises:
1043             AddressValueError: if ip_str isn't a valid IPv4 Address.
1044
1045         """
1046         octets = ip_str.split('.')
1047         if len(octets) != 4:
1048             raise AddressValueError(ip_str)
1049
1050         packed_ip = 0
1051         for oc in octets:
1052             try:
1053                 packed_ip = (packed_ip << 8) | self._parse_octet(oc)
1054             except ValueError:
1055                 raise AddressValueError(ip_str)
1056         return packed_ip
1057
1058     def _parse_octet(self, octet_str):
1059         """Convert a decimal octet into an integer.
1060
1061         Args:
1062             octet_str: A string, the number to parse.
1063
1064         Returns:
1065             The octet as an integer.
1066
1067         Raises:
1068             ValueError: if the octet isn't strictly a decimal from [0..255].
1069
1070         """
1071         # Whitelist the characters, since int() allows a lot of bizarre stuff.
1072         if not self._DECIMAL_DIGITS.issuperset(octet_str):
1073             raise ValueError
1074         octet_int = int(octet_str, 10)
1075         # Disallow leading zeroes, because no clear standard exists on
1076         # whether these should be interpreted as decimal or octal.
1077         if octet_int > 255 or (octet_str[0] == '0' and len(octet_str) > 1):
1078             raise ValueError
1079         return octet_int
1080
1081     def _string_from_ip_int(self, ip_int):
1082         """Turns a 32-bit integer into dotted decimal notation.
1083
1084         Args:
1085             ip_int: An integer, the IP address.
1086
1087         Returns:
1088             The IP address as a string in dotted decimal notation.
1089
1090         """
1091         octets = []
1092         for _ in xrange(4):
1093             octets.insert(0, str(ip_int & 0xFF))
1094             ip_int >>= 8
1095         return '.'.join(octets)
1096
1097     @property
1098     def max_prefixlen(self):
1099         return self._max_prefixlen
1100
1101     @property
1102     def packed(self):
1103         """The binary representation of this address."""
1104         return v4_int_to_packed(self._ip)
1105
1106     @property
1107     def version(self):
1108         return self._version
1109
1110     @property
1111     def is_reserved(self):
1112         """Test if the address is otherwise IETF reserved.
1113
1114         Returns:
1115             A boolean, True if the address is within the
1116             reserved IPv4 Network range.
1117
1118         """
1119         return self in IPv4Network('240.0.0.0/4')
1120
1121     @property
1122     def is_private(self):
1123         """Test if this address is allocated for private networks.
1124
1125         Returns:
1126             A boolean, True if the address is reserved per RFC 1918.
1127
1128         """
1129         return (self in IPv4Network('10.0.0.0/8') or
1130                 self in IPv4Network('172.16.0.0/12') or
1131                 self in IPv4Network('192.168.0.0/16'))
1132
1133     @property
1134     def is_multicast(self):
1135         """Test if the address is reserved for multicast use.
1136
1137         Returns:
1138             A boolean, True if the address is multicast.
1139             See RFC 3171 for details.
1140
1141         """
1142         return self in IPv4Network('224.0.0.0/4')
1143
1144     @property
1145     def is_unspecified(self):
1146         """Test if the address is unspecified.
1147
1148         Returns:
1149             A boolean, True if this is the unspecified address as defined in
1150             RFC 5735 3.
1151
1152         """
1153         return self in IPv4Network('0.0.0.0')
1154
1155     @property
1156     def is_loopback(self):
1157         """Test if the address is a loopback address.
1158
1159         Returns:
1160             A boolean, True if the address is a loopback per RFC 3330.
1161
1162         """
1163         return self in IPv4Network('127.0.0.0/8')
1164
1165     @property
1166     def is_link_local(self):
1167         """Test if the address is reserved for link-local.
1168
1169         Returns:
1170             A boolean, True if the address is link-local per RFC 3927.
1171
1172         """
1173         return self in IPv4Network('169.254.0.0/16')
1174
1175
1176 class IPv4Address(_BaseV4, _BaseIP):
1177
1178     """Represent and manipulate single IPv4 Addresses."""
1179
1180     def __init__(self, address):
1181
1182         """
1183         Args:
1184             address: A string or integer representing the IP
1185               '192.168.1.1'
1186
1187               Additionally, an integer can be passed, so
1188               IPv4Address('192.168.1.1') == IPv4Address(3232235777).
1189               or, more generally
1190               IPv4Address(int(IPv4Address('192.168.1.1'))) ==
1191                 IPv4Address('192.168.1.1')
1192
1193         Raises:
1194             AddressValueError: If ipaddr isn't a valid IPv4 address.
1195
1196         """
1197         _BaseV4.__init__(self, address)
1198
1199         # Efficient constructor from integer.
1200         if isinstance(address, (int, long)):
1201             self._ip = address
1202             if address < 0 or address > self._ALL_ONES:
1203                 raise AddressValueError(address)
1204             return
1205
1206         # Constructing from a packed address
1207         if isinstance(address, Bytes):
1208             try:
1209                 self._ip, = struct.unpack('!I', address)
1210             except struct.error:
1211                 raise AddressValueError(address)  # Wrong length.
1212             return
1213
1214         # Assume input argument to be string or any object representation
1215         # which converts into a formatted IP string.
1216         addr_str = str(address)
1217         self._ip = self._ip_int_from_string(addr_str)
1218
1219
1220 class IPv4Network(_BaseV4, _BaseNet):
1221
1222     """This class represents and manipulates 32-bit IPv4 networks.
1223
1224     Attributes: [examples for IPv4Network('1.2.3.4/27')]
1225         ._ip: 16909060
1226         .ip: IPv4Address('1.2.3.4')
1227         .network: IPv4Address('1.2.3.0')
1228         .hostmask: IPv4Address('0.0.0.31')
1229         .broadcast: IPv4Address('1.2.3.31')
1230         .netmask: IPv4Address('255.255.255.224')
1231         .prefixlen: 27
1232
1233     """
1234
1235     # the valid octets for host and netmasks. only useful for IPv4.
1236     _valid_mask_octets = set((255, 254, 252, 248, 240, 224, 192, 128, 0))
1237
1238     def __init__(self, address, strict=False):
1239         """Instantiate a new IPv4 network object.
1240
1241         Args:
1242             address: A string or integer representing the IP [& network].
1243               '192.168.1.1/24'
1244               '192.168.1.1/255.255.255.0'
1245               '192.168.1.1/0.0.0.255'
1246               are all functionally the same in IPv4. Similarly,
1247               '192.168.1.1'
1248               '192.168.1.1/255.255.255.255'
1249               '192.168.1.1/32'
1250               are also functionaly equivalent. That is to say, failing to
1251               provide a subnetmask will create an object with a mask of /32.
1252
1253               If the mask (portion after the / in the argument) is given in
1254               dotted quad form, it is treated as a netmask if it starts with a
1255               non-zero field (e.g. /255.0.0.0 == /8) and as a hostmask if it
1256               starts with a zero field (e.g. 0.255.255.255 == /8), with the
1257               single exception of an all-zero mask which is treated as a
1258               netmask == /0. If no mask is given, a default of /32 is used.
1259
1260               Additionally, an integer can be passed, so
1261               IPv4Network('192.168.1.1') == IPv4Network(3232235777).
1262               or, more generally
1263               IPv4Network(int(IPv4Network('192.168.1.1'))) ==
1264                 IPv4Network('192.168.1.1')
1265
1266             strict: A boolean. If true, ensure that we have been passed
1267               A true network address, eg, 192.168.1.0/24 and not an
1268               IP address on a network, eg, 192.168.1.1/24.
1269
1270         Raises:
1271             AddressValueError: If ipaddr isn't a valid IPv4 address.
1272             NetmaskValueError: If the netmask isn't valid for
1273               an IPv4 address.
1274             ValueError: If strict was True and a network address was not
1275               supplied.
1276
1277         """
1278         _BaseNet.__init__(self, address)
1279         _BaseV4.__init__(self, address)
1280
1281         # Constructing from an integer or packed bytes.
1282         if isinstance(address, (int, long, Bytes)):
1283             self.ip = IPv4Address(address)
1284             self._ip = self.ip._ip
1285             self._prefixlen = self._max_prefixlen
1286             self.netmask = IPv4Address(self._ALL_ONES)
1287             return
1288
1289         # Assume input argument to be string or any object representation
1290         # which converts into a formatted IP prefix string.
1291         addr = str(address).split('/')
1292
1293         if len(addr) > 2:
1294             raise AddressValueError(address)
1295
1296         self._ip = self._ip_int_from_string(addr[0])
1297         self.ip = IPv4Address(self._ip)
1298
1299         if len(addr) == 2:
1300             mask = addr[1].split('.')
1301             if len(mask) == 4:
1302                 # We have dotted decimal netmask.
1303                 if self._is_valid_netmask(addr[1]):
1304                     self.netmask = IPv4Address(self._ip_int_from_string(
1305                         addr[1]))
1306                 elif self._is_hostmask(addr[1]):
1307                     self.netmask = IPv4Address(
1308                         self._ip_int_from_string(addr[1]) ^ self._ALL_ONES)
1309                 else:
1310                     raise NetmaskValueError('%s is not a valid netmask' % addr[1])
1311
1312                 self._prefixlen = self._prefix_from_ip_int(int(self.netmask))
1313             else:
1314                 # We have a netmask in prefix length form.
1315                 if not self._is_valid_netmask(addr[1]):
1316                     raise NetmaskValueError(addr[1])
1317                 self._prefixlen = int(addr[1])
1318                 self.netmask = IPv4Address(self._ip_int_from_prefix(
1319                     self._prefixlen))
1320         else:
1321             self._prefixlen = self._max_prefixlen
1322             self.netmask = IPv4Address(self._ip_int_from_prefix(
1323                 self._prefixlen))
1324         if strict:
1325             if self.ip != self.network:
1326                 raise ValueError('%s has host bits set' %
1327                                  self.ip)
1328         if self._prefixlen == (self._max_prefixlen - 1):
1329             self.iterhosts = self.__iter__
1330
1331     def _is_hostmask(self, ip_str):
1332         """Test if the IP string is a hostmask (rather than a netmask).
1333
1334         Args:
1335             ip_str: A string, the potential hostmask.
1336
1337         Returns:
1338             A boolean, True if the IP string is a hostmask.
1339
1340         """
1341         bits = ip_str.split('.')
1342         try:
1343             parts = [int(x) for x in bits if int(x) in self._valid_mask_octets]
1344         except ValueError:
1345             return False
1346         if len(parts) != len(bits):
1347             return False
1348         if parts[0] < parts[-1]:
1349             return True
1350         return False
1351
1352     def _is_valid_netmask(self, netmask):
1353         """Verify that the netmask is valid.
1354
1355         Args:
1356             netmask: A string, either a prefix or dotted decimal
1357               netmask.
1358
1359         Returns:
1360             A boolean, True if the prefix represents a valid IPv4
1361             netmask.
1362
1363         """
1364         mask = netmask.split('.')
1365         if len(mask) == 4:
1366             if [x for x in mask if int(x) not in self._valid_mask_octets]:
1367                 return False
1368             if [y for idx, y in enumerate(mask) if idx > 0 and y > mask[idx - 1]]:
1369                 return False
1370             return True
1371         try:
1372             netmask = int(netmask)
1373         except ValueError:
1374             return False
1375         return 0 <= netmask <= self._max_prefixlen
1376
1377     # backwards compatibility
1378     IsRFC1918 = lambda self: self.is_private
1379     IsMulticast = lambda self: self.is_multicast
1380     IsLoopback = lambda self: self.is_loopback
1381     IsLinkLocal = lambda self: self.is_link_local
1382
1383
1384 class _BaseV6(object):
1385
1386     """Base IPv6 object.
1387
1388     The following methods are used by IPv6 objects in both single IP
1389     addresses and networks.
1390
1391     """
1392
1393     _ALL_ONES = (2**IPV6LENGTH) - 1
1394     _HEXTET_COUNT = 8
1395     _HEX_DIGITS = frozenset('0123456789ABCDEFabcdef')
1396
1397     def __init__(self, address):
1398         self._version = 6
1399         self._max_prefixlen = IPV6LENGTH
1400
1401     def _ip_int_from_string(self, ip_str):
1402         """Turn an IPv6 ip_str into an integer.
1403
1404         Args:
1405             ip_str: A string, the IPv6 ip_str.
1406
1407         Returns:
1408             A long, the IPv6 ip_str.
1409
1410         Raises:
1411             AddressValueError: if ip_str isn't a valid IPv6 Address.
1412
1413         """
1414         parts = ip_str.split(':')
1415
1416         # An IPv6 address needs at least 2 colons (3 parts).
1417         if len(parts) < 3:
1418             raise AddressValueError(ip_str)
1419
1420         # If the address has an IPv4-style suffix, convert it to hexadecimal.
1421         if '.' in parts[-1]:
1422             ipv4_int = IPv4Address(parts.pop())._ip
1423             parts.append('%x' % ((ipv4_int >> 16) & 0xFFFF))
1424             parts.append('%x' % (ipv4_int & 0xFFFF))
1425
1426         # An IPv6 address can't have more than 8 colons (9 parts).
1427         if len(parts) > self._HEXTET_COUNT + 1:
1428             raise AddressValueError(ip_str)
1429
1430         # Disregarding the endpoints, find '::' with nothing in between.
1431         # This indicates that a run of zeroes has been skipped.
1432         try:
1433             skip_index, = (
1434                 [i for i in xrange(1, len(parts) - 1) if not parts[i]] or
1435                 [None])
1436         except ValueError:
1437             # Can't have more than one '::'
1438             raise AddressValueError(ip_str)
1439
1440         # parts_hi is the number of parts to copy from above/before the '::'
1441         # parts_lo is the number of parts to copy from below/after the '::'
1442         if skip_index is not None:
1443             # If we found a '::', then check if it also covers the endpoints.
1444             parts_hi = skip_index
1445             parts_lo = len(parts) - skip_index - 1
1446             if not parts[0]:
1447                 parts_hi -= 1
1448                 if parts_hi:
1449                     raise AddressValueError(ip_str)  # ^: requires ^::
1450             if not parts[-1]:
1451                 parts_lo -= 1
1452                 if parts_lo:
1453                     raise AddressValueError(ip_str)  # :$ requires ::$
1454             parts_skipped = self._HEXTET_COUNT - (parts_hi + parts_lo)
1455             if parts_skipped < 1:
1456                 raise AddressValueError(ip_str)
1457         else:
1458             # Otherwise, allocate the entire address to parts_hi.  The endpoints
1459             # could still be empty, but _parse_hextet() will check for that.
1460             if len(parts) != self._HEXTET_COUNT:
1461                 raise AddressValueError(ip_str)
1462             parts_hi = len(parts)
1463             parts_lo = 0
1464             parts_skipped = 0
1465
1466         try:
1467             # Now, parse the hextets into a 128-bit integer.
1468             ip_int = 0L
1469             for i in xrange(parts_hi):
1470                 ip_int <<= 16
1471                 ip_int |= self._parse_hextet(parts[i])
1472             ip_int <<= 16 * parts_skipped
1473             for i in xrange(-parts_lo, 0):
1474                 ip_int <<= 16
1475                 ip_int |= self._parse_hextet(parts[i])
1476             return ip_int
1477         except ValueError:
1478             raise AddressValueError(ip_str)
1479
1480     def _parse_hextet(self, hextet_str):
1481         """Convert an IPv6 hextet string into an integer.
1482
1483         Args:
1484             hextet_str: A string, the number to parse.
1485
1486         Returns:
1487             The hextet as an integer.
1488
1489         Raises:
1490             ValueError: if the input isn't strictly a hex number from [0..FFFF].
1491
1492         """
1493         # Whitelist the characters, since int() allows a lot of bizarre stuff.
1494         if not self._HEX_DIGITS.issuperset(hextet_str):
1495             raise ValueError
1496         hextet_int = int(hextet_str, 16)
1497         if hextet_int > 0xFFFF:
1498             raise ValueError
1499         return hextet_int
1500
1501     def _compress_hextets(self, hextets):
1502         """Compresses a list of hextets.
1503
1504         Compresses a list of strings, replacing the longest continuous
1505         sequence of "0" in the list with "" and adding empty strings at
1506         the beginning or at the end of the string such that subsequently
1507         calling ":".join(hextets) will produce the compressed version of
1508         the IPv6 address.
1509
1510         Args:
1511             hextets: A list of strings, the hextets to compress.
1512
1513         Returns:
1514             A list of strings.
1515
1516         """
1517         best_doublecolon_start = -1
1518         best_doublecolon_len = 0
1519         doublecolon_start = -1
1520         doublecolon_len = 0
1521         for index in range(len(hextets)):
1522             if hextets[index] == '0':
1523                 doublecolon_len += 1
1524                 if doublecolon_start == -1:
1525                     # Start of a sequence of zeros.
1526                     doublecolon_start = index
1527                 if doublecolon_len > best_doublecolon_len:
1528                     # This is the longest sequence of zeros so far.
1529                     best_doublecolon_len = doublecolon_len
1530                     best_doublecolon_start = doublecolon_start
1531             else:
1532                 doublecolon_len = 0
1533                 doublecolon_start = -1
1534
1535         if best_doublecolon_len > 1:
1536             best_doublecolon_end = (best_doublecolon_start +
1537                                     best_doublecolon_len)
1538             # For zeros at the end of the address.
1539             if best_doublecolon_end == len(hextets):
1540                 hextets += ['']
1541             hextets[best_doublecolon_start:best_doublecolon_end] = ['']
1542             # For zeros at the beginning of the address.
1543             if best_doublecolon_start == 0:
1544                 hextets = [''] + hextets
1545
1546         return hextets
1547
1548     def _string_from_ip_int(self, ip_int=None):
1549         """Turns a 128-bit integer into hexadecimal notation.
1550
1551         Args:
1552             ip_int: An integer, the IP address.
1553
1554         Returns:
1555             A string, the hexadecimal representation of the address.
1556
1557         Raises:
1558             ValueError: The address is bigger than 128 bits of all ones.
1559
1560         """
1561         if not ip_int and ip_int != 0:
1562             ip_int = int(self._ip)
1563
1564         if ip_int > self._ALL_ONES:
1565             raise ValueError('IPv6 address is too large')
1566
1567         hex_str = '%032x' % ip_int
1568         hextets = []
1569         for x in range(0, 32, 4):
1570             hextets.append('%x' % int(hex_str[x:x+4], 16))
1571
1572         hextets = self._compress_hextets(hextets)
1573         return ':'.join(hextets)
1574
1575     def _explode_shorthand_ip_string(self):
1576         """Expand a shortened IPv6 address.
1577
1578         Args:
1579             ip_str: A string, the IPv6 address.
1580
1581         Returns:
1582             A string, the expanded IPv6 address.
1583
1584         """
1585         if isinstance(self, _BaseNet):
1586             ip_str = str(self.ip)
1587         else:
1588             ip_str = str(self)
1589
1590         ip_int = self._ip_int_from_string(ip_str)
1591         parts = []
1592         for i in xrange(self._HEXTET_COUNT):
1593             parts.append('%04x' % (ip_int & 0xFFFF))
1594             ip_int >>= 16
1595         parts.reverse()
1596         if isinstance(self, _BaseNet):
1597             return '%s/%d' % (':'.join(parts), self.prefixlen)
1598         return ':'.join(parts)
1599
1600     @property
1601     def max_prefixlen(self):
1602         return self._max_prefixlen
1603
1604     @property
1605     def packed(self):
1606         """The binary representation of this address."""
1607         return v6_int_to_packed(self._ip)
1608
1609     @property
1610     def version(self):
1611         return self._version
1612
1613     @property
1614     def is_multicast(self):
1615         """Test if the address is reserved for multicast use.
1616
1617         Returns:
1618             A boolean, True if the address is a multicast address.
1619             See RFC 2373 2.7 for details.
1620
1621         """
1622         return self in IPv6Network('ff00::/8')
1623
1624     @property
1625     def is_reserved(self):
1626         """Test if the address is otherwise IETF reserved.
1627
1628         Returns:
1629             A boolean, True if the address is within one of the
1630             reserved IPv6 Network ranges.
1631
1632         """
1633         return (self in IPv6Network('::/8') or
1634                 self in IPv6Network('100::/8') or
1635                 self in IPv6Network('200::/7') or
1636                 self in IPv6Network('400::/6') or
1637                 self in IPv6Network('800::/5') or
1638                 self in IPv6Network('1000::/4') or
1639                 self in IPv6Network('4000::/3') or
1640                 self in IPv6Network('6000::/3') or
1641                 self in IPv6Network('8000::/3') or
1642                 self in IPv6Network('A000::/3') or
1643                 self in IPv6Network('C000::/3') or
1644                 self in IPv6Network('E000::/4') or
1645                 self in IPv6Network('F000::/5') or
1646                 self in IPv6Network('F800::/6') or
1647                 self in IPv6Network('FE00::/9'))
1648
1649     @property
1650     def is_unspecified(self):
1651         """Test if the address is unspecified.
1652
1653         Returns:
1654             A boolean, True if this is the unspecified address as defined in
1655             RFC 2373 2.5.2.
1656
1657         """
1658         return self._ip == 0 and getattr(self, '_prefixlen', 128) == 128
1659
1660     @property
1661     def is_loopback(self):
1662         """Test if the address is a loopback address.
1663
1664         Returns:
1665             A boolean, True if the address is a loopback address as defined in
1666             RFC 2373 2.5.3.
1667
1668         """
1669         return self._ip == 1 and getattr(self, '_prefixlen', 128) == 128
1670
1671     @property
1672     def is_link_local(self):
1673         """Test if the address is reserved for link-local.
1674
1675         Returns:
1676             A boolean, True if the address is reserved per RFC 4291.
1677
1678         """
1679         return self in IPv6Network('fe80::/10')
1680
1681     @property
1682     def is_site_local(self):
1683         """Test if the address is reserved for site-local.
1684
1685         Note that the site-local address space has been deprecated by RFC 3879.
1686         Use is_private to test if this address is in the space of unique local
1687         addresses as defined by RFC 4193.
1688
1689         Returns:
1690             A boolean, True if the address is reserved per RFC 3513 2.5.6.
1691
1692         """
1693         return self in IPv6Network('fec0::/10')
1694
1695     @property
1696     def is_private(self):
1697         """Test if this address is allocated for private networks.
1698
1699         Returns:
1700             A boolean, True if the address is reserved per RFC 4193.
1701
1702         """
1703         return self in IPv6Network('fc00::/7')
1704
1705     @property
1706     def ipv4_mapped(self):
1707         """Return the IPv4 mapped address.
1708
1709         Returns:
1710             If the IPv6 address is a v4 mapped address, return the
1711             IPv4 mapped address. Return None otherwise.
1712
1713         """
1714         if (self._ip >> 32) != 0xFFFF:
1715             return None
1716         return IPv4Address(self._ip & 0xFFFFFFFF)
1717
1718     @property
1719     def teredo(self):
1720         """Tuple of embedded teredo IPs.
1721
1722         Returns:
1723             Tuple of the (server, client) IPs or None if the address
1724             doesn't appear to be a teredo address (doesn't start with
1725             2001::/32)
1726
1727         """
1728         if (self._ip >> 96) != 0x20010000:
1729             return None
1730         return (IPv4Address((self._ip >> 64) & 0xFFFFFFFF),
1731                 IPv4Address(~self._ip & 0xFFFFFFFF))
1732
1733     @property
1734     def sixtofour(self):
1735         """Return the IPv4 6to4 embedded address.
1736
1737         Returns:
1738             The IPv4 6to4-embedded address if present or None if the
1739             address doesn't appear to contain a 6to4 embedded address.
1740
1741         """
1742         if (self._ip >> 112) != 0x2002:
1743             return None
1744         return IPv4Address((self._ip >> 80) & 0xFFFFFFFF)
1745
1746
1747 class IPv6Address(_BaseV6, _BaseIP):
1748
1749     """Represent and manipulate single IPv6 Addresses.
1750     """
1751
1752     def __init__(self, address):
1753         """Instantiate a new IPv6 address object.
1754
1755         Args:
1756             address: A string or integer representing the IP
1757
1758               Additionally, an integer can be passed, so
1759               IPv6Address('2001:4860::') ==
1760                 IPv6Address(42541956101370907050197289607612071936L).
1761               or, more generally
1762               IPv6Address(IPv6Address('2001:4860::')._ip) ==
1763                 IPv6Address('2001:4860::')
1764
1765         Raises:
1766             AddressValueError: If address isn't a valid IPv6 address.
1767
1768         """
1769         _BaseV6.__init__(self, address)
1770
1771         # Efficient constructor from integer.
1772         if isinstance(address, (int, long)):
1773             self._ip = address
1774             if address < 0 or address > self._ALL_ONES:
1775                 raise AddressValueError(address)
1776             return
1777
1778         # Constructing from a packed address
1779         if isinstance(address, Bytes):
1780             try:
1781                 hi, lo = struct.unpack('!QQ', address)
1782             except struct.error:
1783                 raise AddressValueError(address)  # Wrong length.
1784             self._ip = (hi << 64) | lo
1785             return
1786
1787         # Assume input argument to be string or any object representation
1788         # which converts into a formatted IP string.
1789         addr_str = str(address)
1790         if not addr_str:
1791             raise AddressValueError('')
1792
1793         self._ip = self._ip_int_from_string(addr_str)
1794
1795
1796 class IPv6Network(_BaseV6, _BaseNet):
1797     """This class represents and manipulates 128-bit IPv6 networks.
1798
1799     Attributes: [examples for IPv6('2001:658:22A:CAFE:200::1/64')]
1800         .ip: IPv6Address('2001:658:22a:cafe:200::1')
1801         .network: IPv6Address('2001:658:22a:cafe::')
1802         .hostmask: IPv6Address('::ffff:ffff:ffff:ffff')
1803         .broadcast: IPv6Address('2001:658:22a:cafe:ffff:ffff:ffff:ffff')
1804         .netmask: IPv6Address('ffff:ffff:ffff:ffff::')
1805         .prefixlen: 64
1806
1807     """
1808
1809     def __init__(self, address, strict=False):
1810         """Instantiate a new IPv6 Network object.
1811
1812         Args:
1813             address: A string or integer representing the IPv6 network or the IP
1814               and prefix/netmask.
1815               '2001:4860::/128'
1816               '2001:4860:0000:0000:0000:0000:0000:0000/128'
1817               '2001:4860::'
1818               are all functionally the same in IPv6.  That is to say,
1819               failing to provide a subnetmask will create an object with
1820               a mask of /128.
1821
1822               Additionally, an integer can be passed, so
1823               IPv6Network('2001:4860::') ==
1824                 IPv6Network(42541956101370907050197289607612071936L).
1825               or, more generally
1826               IPv6Network(IPv6Network('2001:4860::')._ip) ==
1827                 IPv6Network('2001:4860::')
1828
1829             strict: A boolean. If true, ensure that we have been passed
1830               A true network address, eg, 192.168.1.0/24 and not an
1831               IP address on a network, eg, 192.168.1.1/24.
1832
1833         Raises:
1834             AddressValueError: If address isn't a valid IPv6 address.
1835             NetmaskValueError: If the netmask isn't valid for
1836               an IPv6 address.
1837             ValueError: If strict was True and a network address was not
1838               supplied.
1839
1840         """
1841         _BaseNet.__init__(self, address)
1842         _BaseV6.__init__(self, address)
1843
1844         # Constructing from an integer or packed bytes.
1845         if isinstance(address, (int, long, Bytes)):
1846             self.ip = IPv6Address(address)
1847             self._ip = self.ip._ip
1848             self._prefixlen = self._max_prefixlen
1849             self.netmask = IPv6Address(self._ALL_ONES)
1850             return
1851
1852         # Assume input argument to be string or any object representation
1853         # which converts into a formatted IP prefix string.
1854         addr = str(address).split('/')
1855
1856         if len(addr) > 2:
1857             raise AddressValueError(address)
1858
1859         self._ip = self._ip_int_from_string(addr[0])
1860         self.ip = IPv6Address(self._ip)
1861
1862         if len(addr) == 2:
1863             if self._is_valid_netmask(addr[1]):
1864                 self._prefixlen = int(addr[1])
1865             else:
1866                 raise NetmaskValueError(addr[1])
1867         else:
1868             self._prefixlen = self._max_prefixlen
1869
1870         self.netmask = IPv6Address(self._ip_int_from_prefix(self._prefixlen))
1871
1872         if strict:
1873             if self.ip != self.network:
1874                 raise ValueError('%s has host bits set' %
1875                                  self.ip)
1876         if self._prefixlen == (self._max_prefixlen - 1):
1877             self.iterhosts = self.__iter__
1878
1879     def _is_valid_netmask(self, prefixlen):
1880         """Verify that the netmask/prefixlen is valid.
1881
1882         Args:
1883             prefixlen: A string, the netmask in prefix length format.
1884
1885         Returns:
1886             A boolean, True if the prefix represents a valid IPv6
1887             netmask.
1888
1889         """
1890         try:
1891             prefixlen = int(prefixlen)
1892         except ValueError:
1893             return False
1894         return 0 <= prefixlen <= self._max_prefixlen
1895
1896     @property
1897     def with_netmask(self):
1898         return self.with_prefixlen