-- IP library

-- This library contains classes for working with IP addresses and IP ranges.



-- Load modules

require('strict')

local bit32 = require('bit32')

local libraryUtil = require('libraryUtil')

local checkType = libraryUtil.checkType

local checkTypeMulti = libraryUtil.checkTypeMulti

local makeCheckSelfFunction = libraryUtil.makeCheckSelfFunction



-- Constants

local V4 = 'IPv4'

local V6 = 'IPv6'



--------------------------------------------------------------------------------

-- Helper functions

--------------------------------------------------------------------------------



local function makeValidationFunction(className, isObjectFunc)

	-- Make a function for validating a specific object.

	return function (methodName, argIdx, arg)

		if not isObjectFunc(arg) then

			error(string.format(

				"bad argument #%d to '%s' (not a valid %s object)",

				argIdx, methodName, className

			), 3)

		end

	end

end



--------------------------------------------------------------------------------

-- Collection class

-- This is a table used to hold items.

--------------------------------------------------------------------------------



local Collection = {}

Collection.__index = Collection



function Collection:add(item)

	if item ~= nil then

		self.n = self.n + 1

		selfself.n = item

	end

end



function Collection:join(sep)

	return table.concat(self, sep)

end



function Collection:remove(pos)

	if self.n > 0 and (pos == nil or (0 < pos and pos <= self.n)) then

		self.n = self.n - 1

		return table.remove(self, pos)

	end

end



function Collection:sort(comp)

	table.sort(self, comp)

end



function Collection:deobjectify()

	-- Turns the collection into a plain array without any special properties

	-- or methods.

	self.n = nil

	setmetatable(self, nil)

end



function Collection.new()

	return setmetatable({n = 0}, Collection)

end



--------------------------------------------------------------------------------

-- RawIP class

-- Numeric representation of an IPv4 or IPv6 address. Used internally.

-- A RawIP object is constructed by adding data to a Collection object and

-- then giving it a new metatable. This is to avoid the memory overhead of

-- copying the data to a new table.

--------------------------------------------------------------------------------



local RawIP = {}

RawIP.__index = RawIP



-- Constructors

function RawIP.newFromIPv4(ipStr)

	-- Return a RawIP object if ipStr is a valid IPv4 string. Otherwise,

	-- return nil.

	-- This representation is for compatibility with IPv6 addresses.

	local octets = Collection.new()

	local s = ipStr:match('^%s*(.-)%s*$') .. '.'

	for item in s:gmatch('(.-)%.') do

		octets:add(item)

	end

	if octets.n == 4 then

		for i, s in ipairs(octets) do

			if s:match('^%d+$') then

				local num = tonumber(s)

				if 0 <= num and num <= 255 then

					if num > 0 and s:match('^0') then

						-- A redundant leading zero is for an IP in octal.

						return nil

					end

					octetsi = num

				else

					return nil

				end

			else

				return nil

			end

		end

		local parts = Collection.new()

		for i = 1, 3, 2 do

			parts:add(octetsi * 256 + octetsi+1])

		end

		return setmetatable(parts, RawIP)

	end

	return nil

end



function RawIP.newFromIPv6(ipStr)

	-- Return a RawIP object if ipStr is a valid IPv6 string. Otherwise,

	-- return nil.

	ipStr = ipStr:match('^%s*(.-)%s*$')

	local _, n = ipStr:gsub(':', ':')

	if n < 7 then

		ipStr = ipStr:gsub('::', string.rep(':', 9 - n))

	end

	local parts = Collection.new()

	for item in (ipStr .. ':'):gmatch('(.-):') do

		parts:add(item)

	end

	if parts.n == 8 then

		for i, s in ipairs(parts) do

			if s == '' then

				partsi = 0

			else

				if s:match('^%x+$') then

					local num = tonumber(s, 16)

					if num and 0 <= num and num <= 65535 then

						partsi = num

					else

						return nil

					end

				else

					return nil

				end

			end

		end

		return setmetatable(parts, RawIP)

	end

	return nil

end



function RawIP.newFromIP(ipStr)

	-- Return a new RawIP object from either an IPv4 string or an IPv6

	-- string. If ipStr is not a valid IPv4 or IPv6 string, then return

	-- nil.

	return RawIP.newFromIPv4(ipStr) or RawIP.newFromIPv6(ipStr)

end



-- Methods

function RawIP:getVersion()

	-- Return a string with the version of the IP protocol we are using.

	return self.n == 2 and V4 or V6

end



function RawIP:isIPv4()

	-- Return true if this is an IPv4 representation, and false otherwise.

	return self.n == 2

end



function RawIP:isIPv6()

	-- Return true if this is an IPv6 representation, and false otherwise.

	return self.n == 8

end



function RawIP:getBitLength()

	-- Return the bit length of the IP address.

	return self.n * 16

end



function RawIP:getAdjacent(previous)

	-- Return a RawIP object for an adjacent IP address. If previous is true

	-- then the previous IP is returned; otherwise the next IP is returned.

	-- Will wraparound:

	--   next      255.255.255.255 → 0.0.0.0

	--             ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff → ::

	--   previous  0.0.0.0 → 255.255.255.255

	--             :: → ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff

	local result = Collection.new()

	result.n = self.n

	local carry = previous and 0xffff or 1

	for i = self.n, 1, -1 do

		local sum = selfi + carry

		if sum >= 0x10000 then

			carry = previous and 0x10000 or 1

			sum = sum - 0x10000

		else

			carry = previous and 0xffff or 0

		end

		resulti = sum

	end

	return setmetatable(result, RawIP)

end



function RawIP:getPrefix(bitLength)

	-- Return a RawIP object for the prefix of the current IP Address with a

	-- bit length of bitLength.

	local result = Collection.new()

	result.n = self.n

	for i = 1, self.n do

		if bitLength > 0 then

			if bitLength >= 16 then

				resulti = selfi

				bitLength = bitLength - 16

			else

				resulti = bit32.replace(selfi], 0, 0, 16 - bitLength)

				bitLength = 0

			end

		else

			resulti = 0

		end

	end

	return setmetatable(result, RawIP)

end



function RawIP:getHighestHost(bitLength)

	-- Return a RawIP object for the highest IP with the prefix of length

	-- bitLength. In other words, the network (the most-significant bits)

	-- is the same as the current IP's, but the host bits (the

	-- least-significant bits) are all set to 1.

	local bits = self.n * 16

	local width

	if bitLength <= 0 then

		width = bits

	elseif bitLength >= bits then

		width = 0

	else

		width = bits - bitLength

	end

	local result = Collection.new()

	result.n = self.n

	for i = self.n, 1, -1 do

		if width > 0 then

			if width >= 16 then

				resulti = 0xffff

				width = width - 16

			else

				resulti = bit32.replace(selfi], 0xffff, 0, width)

				width = 0

			end

		else

			resulti = selfi

		end

	end

	return setmetatable(result, RawIP)

end



function RawIP:_makeIPv6String()

	-- Return an IPv6 string representation of the object. Behavior is

	-- undefined if the current object is IPv4.

	local z1, z2  -- indices of run of zeroes to be displayed as "::"

	local zstart, zcount

	for i = 1, 9 do

		-- Find left-most occurrence of longest run of two or more zeroes.

		if i < 9 and selfi == 0 then

			if zstart then

				zcount = zcount + 1

			else

				zstart = i

				zcount = 1

			end

		else

			if zcount and zcount > 1 then

				if not z1 or zcount > z2 - z1 + 1 then

					z1 = zstart

					z2 = zstart + zcount - 1

				end

			end

			zstart = nil

			zcount = nil

		end

	end

	local parts = Collection.new()

	for i = 1, 8 do

		if z1 and z1 <= i and i <= z2 then

			if i == z1 then

				if z1 == 1 or z2 == 8 then

					if z1 == 1 and z2 == 8 then

						return '::'

					end

					parts:add(':')

				else

					parts:add('')

				end

			end

		else

			parts:add(string.format('%x', selfi]))

		end

	end

	return parts:join(':')

end



function RawIP:_makeIPv4String()

	-- Return an IPv4 string representation of the object. Behavior is

	-- undefined if the current object is IPv6.

	local parts = Collection.new()

	for i = 1, 2 do

		local w = selfi

		parts:add(math.floor(w / 256))

		parts:add(w % 256)

	end

	return parts:join('.')

end



function RawIP:__tostring()

	-- Return a string equivalent to given IP address (IPv4 or IPv6).

	if self.n == 2 then

		return self:_makeIPv4String()

	else

		return self:_makeIPv6String()

	end

end



function RawIP:__lt(obj)

	if self.n == obj.n then

		for i = 1, self.n do

			if selfi ~= obji then

				return selfi < obji

			end

		end

		return false

	end

	return self.n < obj.n

end



function RawIP:__eq(obj)

	if self.n == obj.n then

		for i = 1, self.n do

			if selfi ~= obji then

				return false

			end

		end

		return true

	end

	return false

end



--------------------------------------------------------------------------------

-- Initialize private methods available to IPAddress and Subnet

--------------------------------------------------------------------------------



-- Both IPAddress and Subnet need access to each others' private constructor

-- functions. IPAddress must be able to make Subnet objects from CIDR strings

-- and from RawIP objects, and Subnet must be able to make IPAddress objects

-- from IP strings and from RawIP objects. These constructors must all be

-- private to ensure correct error levels and to stop other modules from having

-- to worry about RawIP objects. Because they are private, they must be

-- initialized here.

local makeIPAddress, makeIPAddressFromRaw, makeSubnet, makeSubnetFromRaw



-- Objects need to be able to validate other objects that they are passed

-- as input, so initialize those functions here as well.

local validateCollection, validateIPAddress, validateSubnet



--------------------------------------------------------------------------------

-- IPAddress class

-- Represents a single IPv4 or IPv6 address.

--------------------------------------------------------------------------------



local IPAddress = {}



do

	-- dataKey is a unique key to access objects' internal data. This is needed

	-- to access the RawIP objects contained in other IPAddress objects so that

	-- they can be compared with the current object's RawIP object. This data

	-- is not available to other classes or other modules.

	local dataKey = {}



	-- Private static methods

	local function isIPAddressObject(val)

		return type(val) == 'table' and valdataKey ~= nil

	end



	validateIPAddress = makeValidationFunction('IPAddress', isIPAddressObject)



	-- Metamethods that don't need upvalues

	local function ipEquals(ip1, ip2)

		return ip1dataKey].rawIP == ip2dataKey].rawIP

	end



	local function ipLessThan(ip1, ip2)

		return ip1dataKey].rawIP < ip2dataKey].rawIP

	end



	local function concatIP(ip, val)

		return tostring(ip) .. tostring(val)

	end



	local function ipToString(ip)

		return ip:getIP()

	end



	-- Constructors

	makeIPAddressFromRaw = function (rawIP)

		-- Constructs a new IPAddress object from a rawIP object. This function

		-- is for internal use; it is called by IPAddress.new and from other

		-- IPAddress methods, and should be available to the Subnet class, but

		-- should not be available to other modules.

		assert(type(rawIP) == 'table', 'rawIP was type ' .. type(rawIP) .. '; expected type table')



		-- Set up structure

		local obj = {}

		local data = {}

		data.rawIP = rawIP



		-- A function to check whether methods are called with a valid self

		-- parameter.

		local checkSelf = makeCheckSelfFunction(

			'IP',

			'ipAddress',

			obj,

			'IPAddress object'

		)



		-- Public methods

		function obj:getIP()

			checkSelf(self, 'getIP')

			return tostring(data.rawIP)

		end



		function obj:getVersion()

			checkSelf(self, 'getVersion')

			return data.rawIP:getVersion()

		end



		function obj:isIPv4()

			checkSelf(self, 'isIPv4')

			return data.rawIP:isIPv4()

		end



		function obj:isIPv6()

			checkSelf(self, 'isIPv6')

			return data.rawIP:isIPv6()

		end



		function obj:isInCollection(collection)

			checkSelf(self, 'isInCollection')

			validateCollection('isInCollection', 1, collection)

			return collection:containsIP(self)

		end



		function obj:isInSubnet(subnet)

			checkSelf(self, 'isInSubnet')

			local tp = type(subnet)

			if tp == 'string' then

				subnet = makeSubnet(subnet)

			elseif tp == 'table' then

				validateSubnet('isInSubnet', 1, subnet)

			else

				checkTypeMulti('isInSubnet', 1, subnet, {'string', 'table'})

			end

			return subnet:containsIP(self)

		end



		function obj:getSubnet(bitLength)

			checkSelf(self, 'getSubnet')

			checkType('getSubnet', 1, bitLength, 'number')

			if bitLength < 0

				or bitLength > data.rawIP:getBitLength()

				or bitLength ~= math.floor(bitLength)

			then

				error(string.format(

					"bad argument #1 to 'getSubnet' (must be an integer between 0 and %d)",

					data.rawIP:getBitLength()

				), 2)

			end

			return makeSubnetFromRaw(data.rawIP, bitLength)

		end



		function obj:getNextIP()

			checkSelf(self, 'getNextIP')

			return makeIPAddressFromRaw(data.rawIP:getAdjacent())

		end



		function obj:getPreviousIP()

			checkSelf(self, 'getPreviousIP')

			return makeIPAddressFromRaw(data.rawIP:getAdjacent(true))

		end



		-- Metamethods

		return setmetatable(obj, {

			__eq = ipEquals,

			__lt = ipLessThan,

			__concat = concatIP,

			__tostring = ipToString,

			__index = function (self, key)

				-- If any code knows the unique data key, allow it to access

				-- the data table.

				if key == dataKey then

					return data

				end

			end,

			__metatable = false, -- don't allow access to the metatable

		})

	end



	makeIPAddress = function (ip)

		local rawIP = RawIP.newFromIP(ip)

		if not rawIP then

			error(string.format("'%s' is an invalid IP address", ip), 3)

		end

		return makeIPAddressFromRaw(rawIP)

	end



	function IPAddress.new(ip)

		checkType('IPAddress.new', 1, ip, 'string')

		return makeIPAddress(ip)

	end

end



--------------------------------------------------------------------------------

-- Subnet class

-- Represents a block of IPv4 or IPv6 addresses.

--------------------------------------------------------------------------------



local Subnet = {}



do

	-- uniqueKey is a unique, private key used to test whether a given object

	-- is a Subnet object.

	local uniqueKey = {}



	-- Metatable

	local mt = {

		__index = function (self, key)

			if key == uniqueKey then

				return true

			end

		end,

		__eq = function (self, obj)

			return self:getCIDR() == obj:getCIDR()

		end,

		__concat = function (self, obj)

			return tostring(self) .. tostring(obj)

		end,

		__tostring = function (self)

			return self:getCIDR()

		end,

		__metatable = false

	}



	-- Private static methods

	local function isSubnetObject(val)

		-- Return true if val is a Subnet object, and false otherwise.

		return type(val) == 'table' and valuniqueKey ~= nil

	end



	-- Function to validate subnet objects.

	-- Params:

	-- methodName (string) - the name of the method being validated

	-- argIdx (number) - the position of the argument in the argument list

	-- arg - the argument to be validated

	validateSubnet = makeValidationFunction('Subnet', isSubnetObject)



	-- Constructors

	makeSubnetFromRaw = function (rawIP, bitLength)

		-- Set up structure

		local obj = setmetatable({}, mt)

		local data = {

			rawIP = rawIP,

			bitLength = bitLength,

		}



		-- A function to check whether methods are called with a valid self

		-- parameter.

		local checkSelf = makeCheckSelfFunction(

			'IP',

			'subnet',

			obj,

			'Subnet object'

		)



		-- Public methods

		function obj:getPrefix()

			checkSelf(self, 'getPrefix')

			if not data.prefix then

				data.prefix = makeIPAddressFromRaw(

					data.rawIP:getPrefix(data.bitLength)

				)

			end

			return data.prefix

		end



		function obj:getHighestIP()

			checkSelf(self, 'getHighestIP')

			if not data.highestIP then

				data.highestIP = makeIPAddressFromRaw(

					data.rawIP:getHighestHost(data.bitLength)

				)

			end

			return data.highestIP

		end



		function obj:getBitLength()

			checkSelf(self, 'getBitLength')

			return data.bitLength

		end



		function obj:getCIDR()

			checkSelf(self, 'getCIDR')

			return string.format(

				'%s/%d',

				tostring(self:getPrefix()), self:getBitLength()

			)

		end



		function obj:getVersion()

			checkSelf(self, 'getVersion')

			return data.rawIP:getVersion()

		end



		function obj:isIPv4()

			checkSelf(self, 'isIPv4')

			return data.rawIP:isIPv4()

		end



		function obj:isIPv6()

			checkSelf(self, 'isIPv6')

			return data.rawIP:isIPv6()

		end



		function obj:containsIP(ip)

			checkSelf(self, 'containsIP')

			local tp = type(ip)

			if tp == 'string' then

				ip = makeIPAddress(ip)

			elseif tp == 'table' then

				validateIPAddress('containsIP', 1, ip)

			else

				checkTypeMulti('containsIP', 1, ip, {'string', 'table'})

			end

			if self:getVersion() == ip:getVersion() then

				return self:getPrefix() <= ip and ip <= self:getHighestIP()

			end

			return false

		end



		function obj:overlapsCollection(collection)

			checkSelf(self, 'overlapsCollection')

			validateCollection('overlapsCollection', 1, collection)

			return collection:overlapsSubnet(self)

		end



		function obj:overlapsSubnet(subnet)

			checkSelf(self, 'overlapsSubnet')

			local tp = type(subnet)

			if tp == 'string' then

				subnet = makeSubnet(subnet)

			elseif tp == 'table' then

				validateSubnet('overlapsSubnet', 1, subnet)

			else

				checkTypeMulti('overlapsSubnet', 1, subnet, {'string', 'table'})

			end

			if self:getVersion() == subnet:getVersion() then

				return (

					subnet:getHighestIP() >= self:getPrefix() and

					subnet:getPrefix() <= self:getHighestIP()

				)

			end

			return false

		end



		function obj:walk()

			checkSelf(self, 'walk')

			local started

			local current = self:getPrefix()

			local highest = self:getHighestIP()

			return function ()

				if not started then

					started = true

					return current

				end

				if current < highest then

					current = current:getNextIP()

					return current

				end

			end

		end



		return obj

	end



	makeSubnet = function (cidr)

		-- Return a Subnet object from a CIDR string. If the CIDR string is

		-- invalid, throw an error.

		local lhs, rhs = cidr:match('^%s*(.-)/(%d+)%s*$')

		if lhs then

			local bits = lhs:find(':', 1, true) and 128 or 32

			local n = tonumber(rhs)

			if n and n <= bits and (n == 0 or not rhs:find('^0')) then

				-- The right-hand side is a number between 0 and 32 (for IPv4)

				-- or 0 and 128 (for IPv6) and doesn't have any leading zeroes.

				local base = RawIP.newFromIP(lhs)

				if base then

					-- The left-hand side is a valid IP address.

					local prefix = base:getPrefix(n)

					if base == prefix then

						-- The left-hand side is the lowest IP in the subnet.

						return makeSubnetFromRaw(prefix, n)

					end

				end

			end

		end

		error(string.format("'%s' is an invalid CIDR string", cidr), 3)

	end



	function Subnet.new(cidr)

		checkType('Subnet.new', 1, cidr, 'string')

		return makeSubnet(cidr)

	end

end



--------------------------------------------------------------------------------

-- Ranges class

-- Holds a list of IPAdress pairs representing contiguous IP ranges.

--------------------------------------------------------------------------------



local Ranges = Collection.new()

Ranges.__index = Ranges



function Ranges.new()

	return setmetatable({}, Ranges)

end



function Ranges:add(ip1, ip2)

	validateIPAddress('add', 1, ip1)

	if ip2 ~= nil then

		validateIPAddress('add', 2, ip2)

		if ip1 > ip2 then

			error('The first IP must be less than or equal to the second', 2)

		end

	end

	Collection.add(self, {ip1, ip2 or ip1})

end



function Ranges:merge()

	self:sort(

		function (lhs, rhs)

			-- Sort by second value, then first.

			if lhs2 == rhs2 then

				return lhs1 < rhs1

			end

			return lhs2 < rhs2

		end

	)

	local pos = self.n

	while pos > 1 do

		for i = pos - 1, 1, -1 do

			local ip1 = selfi][2

			local ip2 = ip1:getNextIP()

			if ip2 < ip1 then

				ip2 = ip1  -- don't wrap around

			end

			if selfpos][1 > ip2 then

				break

			end

			ip1 = selfi][1

			ip2 = selfpos][1

			selfi = {ip1 > ip2 and ip2 or ip1, selfpos][2]}

			self:remove(pos)

			pos = pos - 1

			if pos <= 1 then

				break

			end

		end

		pos = pos - 1

	end

end



--------------------------------------------------------------------------------

-- IPCollection class

-- Holds a list of IP addresses/subnets. Used internally.

-- Each address/subnet has the same version (either IPv4 or IPv6).

--------------------------------------------------------------------------------



local IPCollection = {}

IPCollection.__index = IPCollection



function IPCollection.new(version)

	assert(

		version == V4 or version == V6,

		'IPCollection.new called with an invalid version'

	)

	local obj = {

		version = version,               -- V4 or V6

		addresses = Collection.new(),    -- valid IP addresses

		subnets = Collection.new(),      -- valid subnets

		omitted = Collection.new(),      -- not-quite valid strings

	}

	return obj

end



function IPCollection:getVersion()

	-- Return a string with the IP version of addresses in this collection.

	return self.version

end



function IPCollection:_store(hit, stripColons)

	local maker, location

	if hit:find('/', 1, true) then

		maker = Subnet.new

		location = self.subnets

	else

		maker = IPAddress.new

		location = self.addresses

	end

	local success, obj = pcall(maker, hit)

	if success then

		location:add(obj)

	else

		if stripColons then

			local colons, hit = hit:match('^(:*)(.*)')

			if colons ~= '' then

				self:_store(hit)

				return

			end

		end

		self.omitted:add(hit)

	end

end



function IPCollection:_assertVersion(version, msg)

	if self.version ~= version then

		error(msg, 3)

	end

end



function IPCollection:addIP(ip)

	local tp = type(ip)

	if tp == 'string' then

		ip = makeIPAddress(ip)

	elseif tp == 'table' then

		validateIPAddress('addIP', 1, ip)

	else

		checkTypeMulti('addIP', 1, ip, {'string', 'table'})

	end

	self:_assertVersion(ip:getVersion(), 'addIP called with incorrect IP version')

	self.addresses:add(ip)

	return self

end



function IPCollection:addSubnet(subnet)

	local tp = type(subnet)

	if tp == 'string' then

		subnet = makeSubnet(subnet)

	elseif tp == 'table' then

		validateSubnet('addSubnet', 1, subnet)

	else

		checkTypeMulti('addSubnet', 1, subnet, {'string', 'table'})

	end

	self:_assertVersion(subnet:getVersion(), 'addSubnet called with incorrect subnet version')

	self.subnets:add(subnet)

	return self

end



function IPCollection:containsIP(ip)

	-- Return true, obj if ip is in this collection,

	-- where obj is the first IPAddress or Subnet with the ip.

	-- Otherwise, return false.

	local tp = type(ip)

	if tp == 'string' then

		ip = makeIPAddress(ip)

	elseif tp == 'table' then

		validateIPAddress('containsIP', 1, ip)

	else

		checkTypeMulti('containsIP', 1, ip, {'string', 'table'})

	end

	if self:getVersion() == ip:getVersion() then

		for _, item in ipairs(self.addresses) do

			if item == ip then

				return true, item

			end

		end

		for _, item in ipairs(self.subnets) do

			if item:containsIP(ip) then

				return true, item

			end

		end

	end

	return false

end



function IPCollection:getRanges()

	-- Return a sorted table of IP pairs equivalent to the collection.

	-- Each IP pair is a table representing a contiguous range of

	-- IP addresses from pair[1] to pair[2] inclusive (IPAddress objects).

	local ranges = Ranges.new()

	for _, item in ipairs(self.addresses) do

		ranges:add(item)

	end

	for _, item in ipairs(self.subnets) do

		ranges:add(item:getPrefix(), item:getHighestIP())

	end

	ranges:merge()

	ranges:deobjectify()

	return ranges

end



function IPCollection:overlapsSubnet(subnet)

	-- Return true, obj if subnet overlaps this collection,

	-- where obj is the first IPAddress or Subnet overlapping the subnet.

	-- Otherwise, return false.

	local tp = type(subnet)

	if tp == 'string' then

		subnet = makeSubnet(subnet)

	elseif tp == 'table' then

		validateSubnet('overlapsSubnet', 1, subnet)

	else

		checkTypeMulti('overlapsSubnet', 1, subnet, {'string', 'table'})

	end

	if self:getVersion() == subnet:getVersion() then

		for _, item in ipairs(self.addresses) do

			if subnet:containsIP(item) then

				return true, item

			end

		end

		for _, item in ipairs(self.subnets) do

			if subnet:overlapsSubnet(item) then

				return true, item

			end

		end

	end

	return false

end



--------------------------------------------------------------------------------

-- IPv4Collection class

-- Holds a list of IPv4 addresses/subnets.

--------------------------------------------------------------------------------



local IPv4Collection = setmetatable({}, IPCollection)

IPv4Collection.__index = IPv4Collection



function IPv4Collection.new()

	return setmetatable(IPCollection.new(V4), IPv4Collection)

end



function IPv4Collection:addFromString(text)

	-- Extract any IPv4 addresses or CIDR subnets from given text.

	checkType('addFromString', 1, text, 'string')

	text = text:gsub('[:!"#&\'()+,%-;<=>?[%]_{|}]', ' ')

	for hit in text:gmatch('%S+') do

		if hit:match('^%d+%.%d+[%.%d/]+$') then

			local _, n = hit:gsub('%.', '.')

			if n >= 3 then

				self:_store(hit)

			end

		end

	end

	return self

end



--------------------------------------------------------------------------------

-- IPv6Collection class

-- Holds a list of IPv6 addresses/subnets.

--------------------------------------------------------------------------------



local IPv6Collection = setmetatable({}, IPCollection)

IPv6Collection.__index = IPv6Collection



do

	-- Private static methods

	local function isCollectionObject(val)

		-- Return true if val is probably derived from an IPCollection object,

		-- otherwise return false.

		if type(val) == 'table' then

			local mt = getmetatable(val)

			if mt == IPv4Collection or mt == IPv6Collection then

				return true

			end

		end

		return false

	end



	validateCollection = makeValidationFunction('IPCollection', isCollectionObject)



	function IPv6Collection.new()

		return setmetatable(IPCollection.new(V6), IPv6Collection)

	end



	function IPv6Collection:addFromString(text)

		-- Extract any IPv6 addresses or CIDR subnets from given text.

		-- Want to accept all valid IPv6 despite the fact that addresses used

		-- are unlikely to start with ':'.

		-- Also want to be able to parse arbitrary wikitext which might use

		-- colons for indenting.

		-- Therefore, if an address at the start of a line is valid, use it;

		-- otherwise strip any leading colons and try again.

		checkType('addFromString', 1, text, 'string')

		for line in string.gmatch(text .. '\n', '[\t ]*(.-)[\t\r ]*\n') do

			line = line:gsub('[!"#&\'()+,%-;<=>?[%]_{|}]', ' ')

			for position, hit in line:gmatch('()(%S+)') do

				local ip = hit:match('^([:%x]+)/?%d*$')

				if ip then

					local _, n = ip:gsub(':', ':')

					if n >= 2 then

						self:_store(hit, position == 1)

					end

				end

			end

		end

		return self

	end

end



return {

	IPAddress = IPAddress,

	Subnet = Subnet,

	IPv4Collection = IPv4Collection,

	IPv6Collection = IPv6Collection,

}