Jump to content

Module:IP/sandbox

From Wikipedia, the free encyclopedia
-- 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
		self[self.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
					octets[i] = num
				else
					return nil
				end
			else
				return nil
			end
		end
		local parts = Collection.new()
		for i = 1, 3, 2 do
			parts:add(octets[i] * 256 + octets[i+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
				parts[i] = 0
			else
				if s:match('^%x+$') then
					local num = tonumber(s, 16)
					if num and 0 <= num and num <= 65535 then
						parts[i] = 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 = self[i] + carry
		if sum >= 0x10000 then
			carry = previous and 0x10000 or 1
			sum = sum - 0x10000
		else
			carry = previous and 0xffff or 0
		end
		result[i] = 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
				result[i] = self[i]
				bitLength = bitLength - 16
			else
				result[i] = bit32.replace(self[i], 0, 0, 16 - bitLength)
				bitLength = 0
			end
		else
			result[i] = 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
				result[i] = 0xffff
				width = width - 16
			else
				result[i] = bit32.replace(self[i], 0xffff, 0, width)
				width = 0
			end
		else
			result[i] = self[i]
		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 self[i] == 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', self[i]))
		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 = self[i]
		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 self[i] ~= obj[i] then
				return self[i] < obj[i]
			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 self[i] ~= obj[i] 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 val[dataKey] ~= nil
	end

	validateIPAddress = makeValidationFunction('IPAddress', isIPAddressObject)

	-- Metamethods that don't need upvalues
	local function ipEquals(ip1, ip2)
		return ip1[dataKey].rawIP == ip2[dataKey].rawIP
	end

	local function ipLessThan(ip1, ip2)
		return ip1[dataKey].rawIP < ip2[dataKey].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 val[uniqueKey] ~= 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 lhs[2] == rhs[2] then
				return lhs[1] < rhs[1]
			end
			return lhs[2] < rhs[2]
		end
	)
	local pos = self.n
	while pos > 1 do
		for i = pos - 1, 1, -1 do
			local ip1 = self[i][2]
			local ip2 = ip1:getNextIP()
			if ip2 < ip1 then
				ip2 = ip1  -- don't wrap around
			end
			if self[pos][1] > ip2 then
				break
			end
			ip1 = self[i][1]
			ip2 = self[pos][1]
			self[i] = {ip1 > ip2 and ip2 or ip1, self[pos][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

--------------------------------------------------------------------------------
-- Util class (static)
-- Holds utility functions.
--------------------------------------------------------------------------------

local Util = {}

function Util.removeDirMarkers(str)
    -- Remove any of following directional markers
	-- LRM : LEFT-TO-RIGHT MARK (U+200E)         : hex e2 80 8e = 226 128 142
	-- LRE : LEFT-TO-RIGHT EMBEDDING (U+202A)    : hex e2 80 aa = 226 128 170
	-- PDF : POP DIRECTIONAL FORMATTING (U+202C) : hex e2 80 ac = 226 128 172
	-- This is required for MediaWiki:Blockedtext message.
	return string.gsub(str, '\226\128[\142\170\172]', '')
end

local function correctCidr(cidrStr)
    -- Correct a well-formatted but invalid CIDR string to a valid one (e.g. 255.255.255.1/24 -> 255.255.255.0/24).
    -- Return a Subnet object only if correction takes place.
	local isCidr, cidr = pcall(Subnet.new, cidrStr)
    local i, _ = string.find(cidrStr, '/%d+$');
    if not isCidr and i ~= nil and i > 1 then
        local bitLen = tonumber(cidrStr:sub(i + 1))
        local root = cidrStr:sub(1, i - 1)
        local isIp, ip = pcall(IPAddress.new, root)
        if isIp then
            local isValidSubnet = ip:isIPv4() and 0 <= bitLen and bitLen <= 32 or ip:isIPv6() and 0 <= bitLen and bitLen <= 128
            if isValidSubnet then
                return ip:getSubnet(bitLen)
            end
        end
    end
    return nil
end

local function isSpecifiedProtocol(obj, protocol)
	-- Check if a given IPAddress/Subnet object is an instance of IPv4, IPv6, or either, and return a boolean value.
	if protocol == 'v4' then
		return obj:isIPv4()
	elseif protocol == 'v6' then
		return obj:isIPv6()
	else
		return obj:isIPv4() or obj:isIPv6()
	end
end

local function verifyIP(str, allowCidr, cidrOnly, protocol)
	-- Return 3 values: boolean, string, string/nil.
		-- v[1] is the result of whether the input string is an IP address or CIDR of the specified protocol (IPv4, IPv6, or either).
		-- v[2] is the input string.
		-- v[3] is a corrected CIDR string only if allowCidr or cidrOnly is true AND v[1] is true AND the input string is in a possible
		-- CIDR format but doesn't actually work as a CIDR and hence is corrected to a valid one (e.g. 1.2.3.4/24 -> 1.2.3.0/24).
	str = Util.removeDirMarkers(str)
	if cidrOnly == true then allowCidr = true end -- Ignores the value of allowCidr if cidrOnly is true
	if allowCidr then
		local corCidr = correctCidr(str)
		local corrected = corCidr ~= nil
		local isCidr, cidr
		if corrected then
			isCidr, cidr = true, corCidr
		else
			isCidr, cidr = pcall(Subnet.new, str)
		end
        if isCidr then -- The input (or corrected) string represents a valid CIDR
			isCidr = isSpecifiedProtocol(cidr, protocol)
			return isCidr, str, (function() if isCidr and corrected then return cidr:getCIDR() end end)()
		elseif cidrOnly then -- Invalid as a CIDR
			return false, str, nil
		end
    end
    local isIp, ip = pcall(IPAddress.new, str)
	if isIp then
		isIp = isSpecifiedProtocol(ip, protocol)
	end
    return isIp, str, nil
end

function Util.isIPAddress(str, allowCidr, cidrOnly)
	return verifyIP(str, allowCidr, cidrOnly, nil)
end

function Util.isIPv4Address(str, allowCidr, cidrOnly)
	return verifyIP(str, allowCidr, cidrOnly, 'v4')
end

function Util.isIPv6Address(str, allowCidr, cidrOnly)
	return verifyIP(str, allowCidr, cidrOnly, 'v6')
end

return {
	IPAddress = IPAddress,
	Subnet = Subnet,
	IPv4Collection = IPv4Collection,
	IPv6Collection = IPv6Collection,
    Util = Util
}