netlink: Abolish client param to netlink_icmp_simple

[secnet] / ipaddr.py

# -*- coding: iso-8859-1 -*-
# ipaddr.py -- handle IP addresses and set of IP addresses.
# Copyright (C) 1996-2000 Cendio Systems AB
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

"""IP address manipulation.

This module is useful if you need to manipulate IP addresses or sets
of IP addresses.

The main classes are:

    ipaddr   -- a single IP address.
    netmask  -- a netmask.
    network  -- an IP address/netmask combination.  It is often, but
                not always, better to use the ip_set class instead.
    ip_set   -- a set of IP addresses, that may or may not be adjacent.

So, what can you do with this module?  As a simple example of the kind
of things this module can do, this code computes the set of all IP
addresses except 127.0.0.0/8 and prints it, expressed as a union of
network/netmask pairs.

    import ipaddr

    s = ipaddr.ip_set()
    s.add_network(ipaddr.network('127.0.0.0', '255.0.0.0',
                                 ipaddr.DEMAND_FILTER))
    for nw in s.complement().as_list_of_networks():
        print nw.ip_str() + '/' + nw.mask.netmask_bits_str

Errors are reported by raising an exception from the following
exception hierarcy:

Exception       # The standard Python base exception class.
 |
 +-- BadType    # Only raised if the programmer makes an error.
 +-- IpError    # Base class for errors that depend on the data.
      |
      +-- SetNotRepresentable
      +-- BrokenIpAddress
      |    |
      |    +-- PartNegative
      |    +-- PartOverflow
      |
      +-- BrokenNetmask
      |    |
      |    +-- NeedOneBit
      |    +-- NeedMoreBits
      |    +-- NeedLessBits
      |
      +-- BrokenNetwork
            |
            +-- EmptyIpAddress
            +-- EmptyNetmask
            +-- BrokenNetworkAddress
            +-- NetworkAddressClash
            +-- BroadcastAddressClash
  
BadType may be raised at any time if the programmer makes an error
(such as passing a dictionary to a function that expects a string).
SetNotRepresentable may be raised by ip_set.as_str_range().  All other
exceptions are raised from the constructors and helper functions only.

The following constants are present in this module:

    DEMAND_NONE         See class network.
    DEMAND_FILTER       See class network.
    DEMAND_NETWORK      See class network.
    DEMAND_INTERFACE    See class network.

    hostmask            A netmask object with all 32 bits set.
    complete_network    A network object representing all IP addresses.
    complete_set        An ip_set object representing all IP addresses.
    broadcast_network   A network object representing 255.255.255.255.
    broadcast_set       An ip_set object representing 255.255.255.255.
    
The as_ipaddr function can be used when you have an object that you
know are an ipaddr or network, and you want to get the ipaddr part.

All the other functions in this module are internal helper functions,
and they should not be used.

The internal representation used for IP addresses is currently a long
number.  That may change in the future, so where the internal
representation is visible, you should do nothing with it except
compare it to None.

This module was developed by Cendio Systems AB for use in the Fuego
Firewall.  Bug reports can be sent to Per Cederqvist <ceder@cendio.se>
who is currently acting as maintainer for this module.

Brief history:
    1997-03-11      Module created, and used internally.
    2000-03-09 1.0: First non-public beta release outside of Cendio Systems.
    2000-03-17 1.1: First public release under the GNU GPL license.

"""


import copy
import string
import types

# The error messages are marked with a call to this function, so that
# they can easily be found and translated.
def _(s):
    return s

# The exception hierarchy.
class IpError(Exception):
    """Base class for errors that are cause by errors in input data.
    """
    def __str__(self):
        return self.format % self.args

class SetNotRepresentable(IpError):
    format = _("The set of IP addresses cannot be represented "
               "as a single network range")

class BrokenIpAddress(IpError):
    format = _("Felaktigt IP-nummer")

class PartNegative(BrokenIpAddress):
    format = _("En komponent i IP-numret är negativ")

class PartOverflow(BrokenIpAddress):
    format = _("En komponent i IP-numret är större än 255")

class BrokenNetmask(IpError):
    format = _("Felaktig nätmask")

class NeedOneBit(BrokenNetmask):
    format = _("Minst en bit måste vara ettställd")

class NeedMoreBits(BrokenNetmask):
    format = _("Minst %d bitar måste vara ettställda")

class NeedLessBits(BrokenNetmask):
    format = _("Högst %d bitar får vara ettställda")

class BrokenNetwork(IpError):
    """Base class for errors regarding network objects.
    """

class EmptyIpAddress(BrokenNetwork):
    format = _("IP-nummer ej ifyllt")

class EmptyNetmask(BrokenNetwork):
    format = _("Nätmask ej ifylld")

class BrokenNetworkAddress(BrokenNetwork):
    format = _("Med denna nätmask är %s ett otillåtet nätverksnummer; "
               "menar du %s?")

class NetworkAddressClash(BrokenNetwork):
    format = _("Med denna nätmask krockar Fuegons adress med nätnumret")

class BroadcastAddressClash(BrokenNetwork):
    format = _("Med denna nätmask krockar Fuegons adress "
               "med broadcastadressen")

class BadType(Exception):
    """An object of an unexpected type was passed to a function.
    """
    pass

# These constants are used with netmasks and networks to specify what
# the code expects.
#
#  DEMAND_NONE: netmask 0-32 (inclusive)
#  DEMAND_FILTER: netmask 0-32, the host part must be all zeroes
#  DEMAND_NETWORK: netmask 1-32, the host part must be all zeroes
#  DEMAND_INTERFACE: netmask 1-30, the host part must *not* be all zeroes

DEMAND_NONE = 1
DEMAND_FILTER = 2
DEMAND_NETWORK = 3
DEMAND_INTERFACE = 4

def bits_to_intrep(bits):
    """Convert BITS to the internal representation.

    BITS should be a number in the range 0-32 (inclusive).

    """
    return pow(2L, 32) - pow(2L, 32-bits)


def intrep_with_bit_set(bit):
    """Return an internal representation with bit BIT set.

    BIT should be a number in the range 1-32, where bit 1 is the
    leftmost.  Examples:

      intrep_with_bit_set(1) --> the internal representation of 128.0.0.0
      intrep_with_bit_set(32) --> the internal representation of 0.0.0.1
    """
    assert 0 < bit and bit <= 32

    return pow(2L, 32-bit)


__ONES = {0:0, 128:1, 192:2, 224:3,
          240:4, 248:5, 252:6, 254:7}

def tuple_to_bits(mask):
    """Convert MASK to bits.

    MASK should be a tuple of four integers in the range 0-255 (inclusive).

    Raises BrokenNetmask if MASK is not a valid netmask.
    """

    if mask == None:
        return None
    else:
        (a, b, c, d) = mask

        if a == 255 and b == 255 and c == 255 and d == 255:
            return 32

        try:
            if a == 255 and b == 255 and c == 255:
                return 24 + __ONES[d]
            elif a == 255 and b == 255  and d == 0:
                return 16 + __ONES[c]
            elif a == 255 and c == 0  and d == 0:
                return 8 + __ONES[b]
            elif b == 0 and c == 0  and d == 0:
                return __ONES[a]
        except KeyError:
            pass

        raise BrokenNetmask()


def intrep_to_dotted_decimal(t):
    """Convert T to dotted-decimal notation.

    T should be the internal representation used py ipaddr.py.
    """

    return (str(int(t>>24)) + '.' + str(int((t>>16) & 255))
            + '.' + str(int((t>>8) & 255)) + '.' + str(int(t & 255)))


def as_ipaddr(nwip):
    """Return the IP address object of NWIP.

    NWIP may be an ipaddr object, which is returned unchanged,
    or a network object, in which case the ipaddr part of it is
    returned.
    """

    if isinstance(nwip, ipaddr):
        return nwip
    elif isinstance(nwip, network):
        return nwip.ip
    else:
        raise BadType('Expected a network or ipaddr object', nwip)


class ipaddr:
    """Handle IP addresses.

    Sample use:

        ip1 = ipaddr('12.3.5.1')
        ip2 = ipaddr([12, 3, 5, 1])
        print ip1.ip_str()
        >>> '12.3.5.1'
        print ip1.intrep
        >>> 201524481L
        print ip2.ip_str()
        >>> '12.3.5.1'
        print ip2.intrep
        >>> 201524481L

    An ipaddr object can have two states: empty or good.
    The status can be examined like this:

        if ip.intrep == None:
            handle_empty(m.user_input())
        else:
            handle_good(ip)

    All other members should only be used in the good state.  The
    value stored in the intrep member should only be compared against
    None.  The type and value of it is an internal detail that may
    change in the future.

    """

    def __init__(self, ip):
        """Create an ipaddr from IP (a string, tuple or list).

        The empty string or None may be given; it is handled as the
        empty IP number.
        """

        if type(ip) == types.StringType:
            self.__user_input = ip
            ip = string.strip(ip)
        else:
            self.__user_input = None

        # The empty IP number?

        if ip == '' or ip == None:
            self.__ip_str = ''
            self.intrep = None
            if ip == None:
                self.__user_input = ''
            return

        if type(ip) == types.StringType:

            # Convert a string.

            try:
                [a, b, c, d] = map(string.atoi, string.splitfields(ip, '.'))
            except:
                raise BrokenIpAddress()

            if a < 0 or b < 0 or c < 0 or d < 0:
                raise PartNegative()

            if a > 255 or b > 255 or c > 255 or d > 255:
                raise PartOverflow()

            self.intrep = (long(a) << 24) + (b << 16) + (c << 8) + d

        else:
            assert type(ip) == types.LongType
            self.intrep = ip

        self.__ip_str = None

    def ip_str(self):
        if self.__ip_str == None:
            self.__ip_str = intrep_to_dotted_decimal(self.intrep)
        return self.__ip_str

    def user_input(self):
        if self.__user_input == None:
            # This object was constructed from a tuple.  Generate a string.
            self.__user_input = self.ip_str()
        return self.__user_input

    def compare(self, other):
        """Compare this IP address with OTHER.

        Returns -1, 0 or 1 if this IP address is less than, equal to,
        or greater than OTHER (which should be an ipaddr object).
        """
        # FIXME: should we rename this __cmp__?  It needs to handle
        # other types of the OTHER argument first.

        if self.intrep == other.intrep:
            return 0
        if self.intrep < other.intrep:
            return -1
        else:
            return 1

    def __str__(self):
        if self.intrep is None:
            return "<ipaddr empty>"
        else:
            return "<ipaddr %s>" % self.ip_str()

    def __repr__(self):
        if self.intrep is None:
            return "ipaddr.ipaddr('')"
        else:
            return "ipaddr.ipaddr('%s')" % self.ip_str()


class netmask:
    """Handle netmasks.

    Sample use:

        # Four ways to initialize a netmask.
        nm1 = netmask('255.255.128.0', DEMAND_NONE)
        nm2 = netmask([255, 255, 128, 0], DEMAND_NONE)
        nm3 = netmask('17', DEMAND_NONE)
        nm4 = netmask(17, DEMAND_NONE)
        print nm1.netmask_str()
        >>> '255.255.128.0'
        print nm1.intrep
        >>> (255, 255, 128, 0)
        print nm1.netmask_bits
        >>> 17
        print nm1.netmask_bits_str
        >>> '17'

    A netmask can have two states: empty or good.  The state
    can be examined like this:

        if m.intrep == None:
            handle_empty(m.user_input())
        else:
            handle_good(m)

    All other members should be used only in the good state.

    """

    def __check_range(self, bits, minbits, maxbits):
        if bits < minbits:
            if minbits == 1:
                raise NeedOneBit()
            else:
                raise NeedMoreBits(minbits)
        elif bits > maxbits:
            raise NeedLessBits(maxbits)


    def __set_from_bits(self, bits, minbits, maxbits):
        self.__check_range(bits, minbits, maxbits)
        self.intrep = bits_to_intrep(bits)
        self.netmask_bits = bits


    def __set_from_tuple(self, tpl, minbits, maxbits):
        bits = tuple_to_bits(tpl)
        self.__check_range(bits, minbits, maxbits)
        self.intrep = bits_to_intrep(bits)
        self.netmask_bits = bits

    DEMANDS = {DEMAND_NONE:(0,32),
               DEMAND_FILTER:(0,32),
               DEMAND_NETWORK:(1,32),
               DEMAND_INTERFACE:(1,30)}

    def __init__(self, mask, demand):
        """Create a netmask from MASK (a string, tuple or number) and DEMAND.

        The empty string or None may be given; it is handled as the
        empty netmask.

        See class network for a description of the DEMAND parameter.
        """

        (minbits, maxbits) = self.DEMANDS[demand]
        self.demand = demand

        if type(mask) == types.StringType:
            self.__user_input = mask
            mask = string.strip(mask)
        else:
            self.__user_input = None

        if mask == '' or mask == None:

            # Handle empty netmasks.

            self.__netmask_str = ''
            self.intrep = None
            self.netmask_bits_str = ''
            self.netmask_bits = None
            if self.__user_input == None:
                self.input = ''
            return

        # Decode the MASK argument and set self.netmask_bits
        # and self.intrep.

        if type(mask) == types.StringType:

            # Is this a string containing a single number?
            try:
                bits = string.atoi(mask)
            except (OverflowError, ValueError):
                bits = None

            if bits != None:

                # This is a string containing a single number.

                self.__set_from_bits(bits, minbits, maxbits)

            else:

                # Interpret the netmask as a dotted four-tuple.
                try:
                    [a, b, c, d] = map(string.atoi,
                                       string.splitfields(mask, '.'))
                except:
                    raise BrokenNetmask()

                self.__set_from_tuple((a, b, c, d), minbits, maxbits)

        elif type(mask) == types.IntType:

            # This is a number, representing the number of bits in the mask.

            self.__set_from_bits(mask, minbits, maxbits)

        else:

            # This is a tuple or list.

            if len(mask) != 4:
                raise BadType('Wrong len of tuple/list')

            (a, b, c, d) = (mask[0], mask[1], mask[2], mask[3])

            self.__set_from_tuple((a, b, c, d), minbits, maxbits)

        self.__netmask_str = None
        self.netmask_bits_str = repr(self.netmask_bits)

    def netmask_str(self):
        if self.__netmask_str == None:
            self.__netmask_str = intrep_to_dotted_decimal(self.intrep)
        return self.__netmask_str

    def user_input(self):
        if self.__user_input == None:
            # This object was constructed from a tuple or an integer.
            self.__user_input = self.ip_str()
        return self.__user_input

    def __str__(self):
        if self.intrep is None:
            return "<netmask empty>"
        else:
            return "<netmask /%d>" % self.netmask_bits

    def __repr__(self):
        if self.intrep is None:
            return "ipaddr.netmask('')"
        else:
            return "ipaddr.netmask(%d, %d)" % (self.netmask_bits, self.demand)


hostmask = netmask(32, DEMAND_NONE)
        

class network:
    """Designate a network or host.

    The constructor takes three arguments: the IP number part, the
    netmask part, and a demand parameter.  See class ipaddr and class
    netmask for a description of the first two arguments.  The demand
    argument can be one of the following constants:

    DEMAND_NONE
        No special demands.
    DEMAND_FILTER
        The host part must be all zeroes.
    DEMAND_NETWORK
        The netmask must be 1-32
        The host part must be all zeroes.
    DEMAND_INTERFACE
        The netmask must be 1-30
        The host part must *not* be all zeroes (the network address)
        or all ones (the broadcast address).

    The following members exist and are set by the constructor:

      ip.user_input()           # a caching function
      ip_str()                  # a caching function
      ip.intrep
      mask.user_input()         # a caching function
      mask.netmask_str()        # a caching function
      mask.intrep
      mask.netmask_bits
      mask.netmask_bits_str
      network_str()             # a caching function
      network_intrep
      broadcast_str()           # a caching function
      broadcast_intrep
      host_part_str()           # a caching function
      host_part_intrep

    """

    def __init__(self, ip, mask, demand):
        self.ip = ipaddr(ip)
        self.mask = netmask(mask, demand)

        if self.ip.intrep == None:
            raise EmptyIpAddress()

        if self.mask.intrep == None:
            raise EmptyNetmask()

        self._precompute()

    def _precompute(self):
        self.__lower_str = None
        self.__upper_str = None

        self.network_intrep = self.ip.intrep & self.mask.intrep
        self.broadcast_intrep = (self.network_intrep |
                                (pow(2L, 32)-1-self.mask.intrep))
        self.host_part_intrep = self.ip.intrep - self.network_intrep

        self.__network_str = None
        self.__broadcast_str = None
        self.__host_part_str = None

        demand = self.mask.demand

        if demand == DEMAND_NONE:
            pass
        elif demand == DEMAND_FILTER or demand == DEMAND_NETWORK:
            if self.host_part_intrep != 0L:
                raise BrokenNetworkAddress(self.ip_str(), self.network_str())
        elif demand == DEMAND_INTERFACE:
            if self.host_part_intrep == 0L:
                raise NetworkAddressClash()
            elif self.broadcast_intrep == self.ip.intrep:
                raise BroadcastAddressClash()
        else:
            raise BadType('Bad value for the demand parameter', demand)

    def network_str(self):
        if self.__network_str == None:
            self.__network_str = intrep_to_dotted_decimal(self.network_intrep)
        return self.__network_str

    def broadcast_str(self):
        if self.__broadcast_str == None:
            self.__broadcast_str = intrep_to_dotted_decimal(
                self.broadcast_intrep)
        return self.__broadcast_str

    def host_part_str(self):
        if self.__host_part_str == None:
            self.__host_part_str = intrep_to_dotted_decimal(
                self.host_part_intrep)
        return self.__host_part_str

    def overlaps(self, other):
        """Returns true if the network overlaps with OTHER.

        OTHER must be a network object or an ipaddr object.  If it
        is empty this method will always return false.

        """

        if self.network_intrep == None:
            return 0

        if isinstance(other, ipaddr):

            if other.intrep == None:
                return 0

            return (self.mask.intrep & other.intrep) == self.network_intrep
        else:
            if other.network_intrep == None:
                return 0

            mask = self.mask.intrep & other.mask.intrep
            return (mask & self.ip.intrep) == (mask & other.ip.intrep)

    def intersection(self, other):
        """Return the intersection of the network and OTHER.

        The return value is a network object with DEMAND_FILTER.  If
        the intersection is empty this method will return None.

        OTHER must be a network object or an ipaddr object.  The
        intersection will be empty if it is empty.
        """

        if self.network_intrep == None:
            return None

        if isinstance(other, ipaddr):

            if other.intrep == None:
                return None

            prefix_mask = self.mask.intrep
            short_net = self.network_intrep
            long_ip = other.intrep
            result = network(other.intrep, 32, DEMAND_FILTER)
        else:
            if other.network_intrep == None:
                return None
            
            if self.mask.netmask_bits < other.mask.netmask_bits:
                prefix_mask = self.mask.intrep
                short_net = self.network_intrep
                long_ip = other.network_intrep
                result = network(other.network_intrep, other.mask.netmask_bits,
                                 DEMAND_FILTER)
            else:
                prefix_mask = other.mask.intrep
                short_net = other.network_intrep
                long_ip = self.network_intrep
                result = network(self.network_intrep, self.mask.netmask_bits,
                                 DEMAND_FILTER)

        if (long_ip & prefix_mask) != (short_net & prefix_mask):
            return None

        return result

    def is_subset(self, nwip):
        """Return true if NWIP is a subset of this network.

        NWIP must be a network object or an ipaddr object.
        """

        if not self.overlaps(nwip):
            return 0

        if isinstance(nwip, ipaddr):
            return 1

        return nwip.mask.netmask_bits <= self.mask.netmask_bits

    def is_same_set(self, nwip):
        """Return true if NWIP contains the same set as this network.

        NWIP must be a network object or an ipaddr object.
        """

        if isinstance(nwip, ipaddr):
            return (self.mask.netmask_bits == 32
                    and self.ip.intrep == nwip.intrep)
        else:
            return (self.mask.netmask_bits == nwip.mask.netmask_bits
                    and self.network_intrep == nwip.network_intrep)

    def subtract(self, nwip):
        """Create a list of new network objects by subtracting NWIP from self.

        The result consists of networks that together span all
        IP addresses that are present in self, except those that are
        present in NWIP.  (The result may be empty or contain several
        disjoint network objects.)

        Don't use this!  This method is slow.  The ip_set class can do
        this kind of things in a more efficient way.
        """

        if not self.overlaps(nwip):
            # No overlap at all, so NWIP cannot affect the result.
            return [self]

        if isinstance(nwip, ipaddr):
            bits = 32
            intrep = nwip.intrep
        else:
            assert isinstance(nwip, network)
            bits = nwip.mask.netmask_bits
            intrep = nwip.ip.intrep
        nets = []
        while bits > self.mask.netmask_bits:
            nets.append(network(compute_neighbor(intrep, bits),
                                bits, DEMAND_FILTER))
            bits = bits - 1
        return nets

    def subtract_nwips(self, nwips):
        """Create a list of new network objects by subtracting NWIPS.

        The result consists of networks that together span all
        IP addresses that are present in self, except those that are
        present in NWIPS.  (The result may be empty or contain
        several disjoint network objects.)  NWIPS should be a list
        of network or ipaddr objects.

        Don't use this!  This method is slow.  The ip_set class can do
        this kind of things in a more efficient way.
        """

        subtracted = [self]
        for s in nwips:
            # precondition<A>: SUBTRACTED is a list of networks
            tmp = []
            for nw in subtracted:
                tmp = tmp + nw.subtract(s)
            subtracted = tmp
            # postcondition: SUBTRACTED is a list of networks that
            # spans all IP addresses that were present in
            # precondition<A>, except those that are present in S.

        return subtracted

    def __compute_lower_upper(self):
        if self.__lower_str != None:
            return
        assert self.network_intrep != None and self.broadcast_intrep != None

        self.__lower_str = intrep_to_dotted_decimal(self.network_intrep + 1)
        self.__upper_str = intrep_to_dotted_decimal(self.broadcast_intrep - 1)

    def lower_host(self):
        self.__compute_lower_upper()
        return self.__lower_str

    def upper_host(self):
        self.__compute_lower_upper()
        return self.__upper_str

    def __repr__(self):
        return _("{network %s/%d}") % (self.ip_str(), self.mask.netmask_bits)

    def ip_str(self):
        return self.ip.ip_str()


class ip_set:
    def __init__(self, nwip=None):
        """Create an ip_set.

        If the optional argument NWIP is supplied, the set is
        initialized to it, otherwise the created set will be empty.
        NWIP must be a network or ipaddr object.
        """

        # [[0L, 3L], [5L, 7L]] means 0.0.0.0/29 \ 0.0.0.4/32
        self.__set = []

        if nwip != None:
            self.append(nwip)

    def subtract_set(self, other):
        """Remove all IP-numbers in OTHER from this.

        OTHER should be an ip_set object.
        """

        self.subtract_list(other.__set)

    def subtract_ips(self, ips):
        """Remove all IP-numbers in IPS from this.

        IPS should be a list of ipaddr objects.
        """

        for ip in ips:
            self.subtract_list([[ip.intrep, ip.intrep]])

    def subtract_list(self, other):
        # Don't use this method directly, unless you are the test suite.
        ix = 0
        iy = 0
        while ix < len(self.__set) and iy < len(other):
            if self.__set[ix][1] < other[iy][0]:
                # The entire range survived.
                ix = ix + 1
            elif self.__set[ix][0] > other[iy][1]:
                # The entire other range is unused, so discard it.
                iy = iy + 1
            elif self.__set[ix][0] >= other[iy][0]:
                if self.__set[ix][1] <= other[iy][1]:
                    # The entire range is subtracted.
                    del self.__set[ix]
                else:
                    # The start of the range is subtracted, but
                    # the rest of the range may survive.  (As a matter
                    # of fact, at least one number *will* survive,
                    # since there should be a gap between other[iy][1]
                    # and other[iy+1][0], but we don't use that fact.)
                    self.__set[ix][0] = other[iy][1] + 1
                    iy = iy + 1
            else:
                # The first part of the range survives.
                end = self.__set[ix][1]
                assert self.__set[ix][1] >= other[iy][0]
                self.__set[ix][1] = other[iy][0] - 1
                ix = ix + 1
                if end > other[iy][1]:
                    # The part that extends past the subtractor may survive.
                    self.__set[ix:ix] = [[other[iy][1] + 1, end]]
                # Retain the subtractor -- it may still kill some
                # other range.

    def add_set(self, other):
        """Add all IP-numbers in OTHER to this.

        OTHER should be an ip_set object.
        """

        self.add_list(other.__set)

    def add_list(self, other):
        # Don't use this method directly, unless you are the test suite.
        ix = 0
        iy = 0
        res = []
        while ix < len(self.__set) or iy < len(other):
            # Remove the first range
            if ix < len(self.__set):
                if iy < len(other):
                    if self.__set[ix][0] < other[iy][0]:
                        rng = self.__set[ix]
                        ix = ix + 1
                    else:
                        rng = other[iy]
                        iy = iy + 1
                else:
                    rng = self.__set[ix]
                    ix = ix + 1
            else:
                rng = other[iy]
                iy = iy + 1

            # Join this range to the list we already have collected.
            if len(res) == 0:
                # This is the first element.
                res.append(rng)
            elif rng[0] <= res[-1][1] + 1:
                # This extends (or is consumed by) the last range.
                res[-1][1] = max(res[-1][1], rng[1])
            else:
                # There is a gap between the previous range and this one.
                res.append(rng)

        self.__set = res

    def append(self, nwip):
        """Add NWIP to this.

        NWIP should be a network object or ipaddr object.
        """

        if isinstance(nwip, network):
            self.add_network(nwip)
        else:
            self.add_ipaddr(nwip)

    def add_network(self, nw):
        """Add NW to this.

        NW should be a network object.
        """
        self.add_list([[nw.network_intrep, nw.broadcast_intrep]])

    def add_range(self, lo_ip, hi_ip):
        """Add the range of IP numbers specified by LO_IP and HI_IP to this.

        LO_IP and HI_IP should be ipaddr objects.  They specify a
        range of IP numbers.  Both LO_IP and HI_IP are included in the
        range.
        """

        assert lo_ip.intrep != None
        assert hi_ip.intrep != None
        assert lo_ip.intrep <= hi_ip.intrep
        self.add_list([[lo_ip.intrep, hi_ip.intrep]])

    def add_ipaddr(self, ip):
        """Add IP to this.

        IP should be an ipaddr object.
        """

        assert ip.intrep != None
        self.add_list([[ip.intrep, ip.intrep]])

    def complement(self):
        """Return everything not contained in this ip_set.

        The return value is a new ip_set.  This is not modified.
        """

        pre = -1L
        lst = []
        for [lo, hi] in self.__set:
            if lo != 0:
                lst.append([pre+1, lo-1])
            pre = hi
        if pre < pow(2L, 32) - 1:
            lst.append([pre+1, pow(2L, 32) - 1])
        res = ip_set()
        res.add_list(lst)
        return res

    def intersection(self, other):
        """Return the intersection of this and OTHER.

        The return value is a new ip_set.  This is not modified.
        OTHER should be an ip_set, network or ipaddr object.
        """

        res = []
        ix = 0
        iy = 0
        x = copy.deepcopy(self.__set)

        if isinstance(other, ip_set):
            y = copy.deepcopy(other.__set)
        elif isinstance(other, network):
            y = [[other.network_intrep, other.broadcast_intrep]]
        elif isinstance(other, ipaddr):
            y = [[other.intrep, other.intrep]]
        else:
            raise BadType('expected an ip_set, network or ipaddr argument')

        while ix < len(x) and iy < len(y):
            if x[ix][1] < y[iy][0]:
                # The first entry on x doesn't overlap with anything on y.
                ix = ix + 1
            elif x[ix][0] > y[iy][1]:
                # The first entry on y doesn't overlap with anything on x.
                iy = iy + 1
            else:
                # Some overlap exists.

                # Trim away any leading edges.
                if x[ix][0] < y[iy][0]:
                    # x starts before y
                    x[ix][0] = y[iy][0]
                elif x[ix][0] > y[iy][0]:
                    # y starts before x
                    y[iy][0] = x[ix][0]

                # The ranges start at the same point (at least after
                # the trimming).
                if x[ix][1] == y[iy][1]:
                    # The ranges are equal.
                    res.append(x[ix])
                    ix = ix + 1
                    iy = iy + 1
                elif x[ix][1] < y[iy][1]:
                    # x is the smaller range
                    res.append(x[ix])
                    ix = ix + 1
                else:
                    # y is the smaller range
                    res.append(y[iy])
                    iy = iy + 1

        result = ip_set()
        result.add_list(res)
        return result


    def as_list_of_networks(self):
        """Return this set as a list of networks.

        The returned value is a list of network objects, that are
        created with DEMAND_FILTER.  This method may be expensive, so
        it should only be used when necessary.
        """

        bm = []
        for [a, b] in self.__set:

            lomask = 1L
            lobit = 1L
            himask = pow(2L, 32)-2
            bits = 32
            while a <= b:
                if a & lomask != 0L:
                    bm.append((bits, a))
                    a = a + lobit
                elif b & lomask != lomask:
                    bm.append((bits, b & himask))
                    b = b - lobit
                else:
                    lomask = (lomask << 1) | 1
                    lobit = lobit << 1
                    himask = himask ^ lobit
                    bits = bits - 1
                    assert(bits >= 0)
        bm.sort()
        res = []
        for (mask, ip) in bm:
            res.append(network(ip, mask, DEMAND_FILTER))
        return res

    def as_list_of_ranges(self):
        """Return the set of IP addresses as a list of ranges.

        Each range is a list of two long numbers.  Sample return
        value: [[1L, 3L], [0x7f000001L, 0x7f000001L]], meaning
        the set 0.0.0.1, 0.0.0.2, 0.0.0.3, 127.0.0.1.
        """

        # This method is currently very cheap, since this is the
        # current internal representation.

        return self.__set

    def as_str_range(self):
        """Return the set as a string, such as "1.2.3.4-1.2.3.8".

        The returned value always has the form a.b.c.d-e.f.g.h.
        Raises SetNotRepresentable if the set cannot be represented as a
        single interval, or if it is the empty set.
        """
        if len(self.__set) != 1:
            raise SetNotRepresentable()
        return "%s-%s" % (intrep_to_dotted_decimal(self.__set[0][0]),
                          intrep_to_dotted_decimal(self.__set[0][1]))

    def contains(self, ip):
        """Return true if IP is contained in the set.

        IP should be an ipaddr object.  The empty ipaddr is never contained.
        """

        if ip.intrep == None:
            return 0

        for [lo, hi] in self.__set:
            if lo <= ip.intrep <= hi:
                return 1
        return 0

    def overlaps(self, nwip):
        """Return true if NWIP overlaps the set of IP addresses.

        NWIP may be an ipaddr, network or ip_set object.
        """

        if isinstance(nwip, ipaddr):
            return self.contains(nwip)
        elif isinstance(nwip, ip_set):
            # This could be optimized -- we don't really need
            # to compute the intersection.
            return not self.intersection(nwip).is_empty()
        elif isinstance(nwip, network):
            wanted_low = nwip.network_intrep
            wanted_high = nwip.broadcast_intrep
            if wanted_low == None or wanted_high == None:
                return 0
            for [lo, hi] in self.__set:
                if lo > wanted_high:
                    # We are past the interresting interval.
                    return 0
                if lo >= wanted_low or hi >= wanted_low:
                    return 1
            return 0
        else:
            raise BadType('Expected an ipaddr, ip_set or network instance')

    def is_empty(self):
        """Return true if this ip_set is empty.
        """

        return len(self.__set) == 0

    def any_ip(self):
        """Return one of the IP addresses contained in ip_set.

        This method may only be called if the set is non-empty.  You
        can use the is_empty method to test for emptiness.

        This picks an IP address from the set and returns it as an
        ipaddr object.  Given the same set of IP addresses, this
        method will always return the same IP address, but which IP
        address it chooses is explicitly undocumented and may change
        if the underlying implementation of ip_set ever changes.
        """

        assert not self.is_empty()
        return ipaddr(self.__set[0][0])

    def __str__(self):
        res = []
        for rng in self.__set:
            if rng[0] == rng[1]:
                res.append(intrep_to_dotted_decimal(rng[0]))
            else:
                res.append('%s-%s' % (intrep_to_dotted_decimal(rng[0]),
                                      intrep_to_dotted_decimal(rng[1])))
        return '<ipaddr.ip_set(%s)>' % string.join(res, ', ')

complete_network = network(0L, 0, DEMAND_FILTER)
complete_set = ip_set(complete_network)
broadcast_network = network('255.255.255.255', 32, DEMAND_FILTER)
broadcast_set = ip_set(broadcast_network)

def compute_neighbor(intrep, bits):
    xor_mask = intrep_with_bit_set(bits)
    and_mask = bits_to_intrep(bits)
    return (intrep ^ xor_mask) & and_mask


if __name__ == '__main__':
    # Test/demo code.  With no arguments, this will print a page
    # of data that can be useful when trying to interpret an
    # ipnumber/netmask pair.  With two arguments, it will print some
    # information about the IP number and netmask that was entered.

    import sys
    if len(sys.argv) == 1:
        print "Netmasks\n========"
        for i in range(0, 17):
            if i != 16:
                print '%2d' % i,
                print '%-13s' % netmask(i, DEMAND_NONE).netmask_str(),
            else:
                print ' ' * 16,
            print i + 16, '%-16s' % netmask(i + 16, DEMAND_NONE).netmask_str()
        print _("\n\nIP intervals\n============")
        for i in range(9):
            for j in range(0, 4):
                print '%2d' % (8*j + i),
            print '%3d' % (netmask(i, DEMAND_NONE).intrep >> 24),
            x = 0
            need_break = 0
            if i < 8:
                for j in range(0, 256, pow(2, 8-i)):
                    if need_break:
                        print
                        print ' ' * 15,
                        need_break = 0
                    print '%3d-%-3d' % (j, j + pow(2, 8-i)-1),
                    x = x + 1
                    if x % 8 == 0:
                        need_break = 1
            else:
                print '0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13...',
            print
        sys.exit(0)

    if len(sys.argv) != 3:
        sys.stderr.write(_("Usage: python ipaddr.py IP_ADDRESS NETMASK\n"))
        sys.exit(1)
    nw = network(sys.argv[1], sys.argv[2], DEMAND_NONE)
    print nw
    print "IP address:       ", nw.ip.ip_str()
    print "Netmask:          ", nw.mask.netmask_str(),
    print " (/" + nw.mask.netmask_bits_str + ")"
    print "Network address:  ", nw.network_str()
    print "Broadcast address:", nw.broadcast_str()