src/Cidr.hs

   1 module Cidr
   2 ( Cidr(..),
   3   cidr_from_string,
   4   cidr_tests,
   5   combine_all
   6 ) where
   7
   8 import Data.List (nubBy)
   9 import Test.HUnit
  10
  11 import IPv4Address
  12 import ListUtils
  13 import Maskable
  14 import Maskbits
  15 import Octet
  16
  17
  18 data Cidr = None | Cidr { ipv4address :: IPv4Address,
  19                           maskbits :: Maskbits }
  20             deriving (Eq)
  21
  22
  23 instance Show Cidr where
  24     show Cidr.None = "None"
  25     show cidr = (show (ipv4address cidr)) ++ "/" ++ (show (maskbits cidr))
  26
  27
  28 -- Two CIDR ranges are equivalent if they have the same network bits
  29 -- and the masks are the same.
  30 equivalent :: Cidr -> Cidr -> Bool
  31 equivalent Cidr.None Cidr.None = True
  32 equivalent Cidr.None _ = False
  33 equivalent _ Cidr.None = False
  34 equivalent (Cidr addr1 mbits1) (Cidr addr2 mbits2) =
  35     (mbits1 == mbits2) && ((apply_mask addr1 mbits1) == (apply_mask addr2 mbits2))
  36
  37 -- Returns the mask portion of a CIDR address. That is, everything
  38 -- after the trailing slash.
  39 maskbits_from_cidr_string :: String -> Maskbits
  40 maskbits_from_cidr_string s =
  41     maskbits_from_string ((splitWith (`elem` "/") s) !! 1)
  42
  43
  44 -- Takes an IP address String in CIDR notation, and returns a list of
  45 -- its octets (as Ints).
  46 octets_from_cidr_string :: String -> [Octet]
  47 octets_from_cidr_string s =
  48     map octet_from_string (take 4 (splitWith (`elem` "./") s))
  49
  50
  51 cidr_from_string :: String -> Cidr
  52 cidr_from_string s
  53     | addr  == IPv4Address.None = Cidr.None
  54     | mbits == Maskbits.None    = Cidr.None
  55     | otherwise = Cidr addr mbits
  56                where
  57                  addr = ipv4address_from_octets (oct1) (oct2) (oct3) (oct4)
  58                  oct1 = (octs !! 0)
  59                  oct2 = (octs !! 1)
  60                  oct3 = (octs !! 2)
  61                  oct4 = (octs !! 3)
  62                  octs  = octets_from_cidr_string s
  63                  mbits = maskbits_from_cidr_string s
  64
  65
  66
  67 -- Return true if the first argument (a CIDR range) contains the
  68 -- second (another CIDR range). There are a lot of ways we can be fed
  69 -- junk here. For lack of a better alternative, just return False when
  70 -- we are given nonsense.
  71 contains :: Cidr -> Cidr -> Bool
  72 contains Cidr.None _ = False
  73 contains _ Cidr.None = False
  74 contains (Cidr _ Maskbits.None) _    = False
  75 contains (Cidr IPv4Address.None _) _ = False
  76 contains _ (Cidr _ Maskbits.None)    = False
  77 contains _ (Cidr IPv4Address.None _) = False
  78
  79 -- If the number of bits in the network part of the first address is
  80 -- larger than the number of bits in the second, there is no way that
  81 -- the first range can contain the second. For, if the number of
  82 -- network bits is larger, then the number of host bits must be
  83 -- smaller, and if cidr1 has fewer hosts than cidr2, cidr1 most
  84 -- certainly does not contain cidr2.
  85 --
  86 -- On the other hand, if the first argument (cidr1) has fewer (or the
  87 -- same number of) network bits as the second, it can contain the
  88 -- second. In this case, we need to check that every host in cidr2 is
  89 -- contained in cidr1. If a host in cidr2 is contained in cidr1, then
  90 -- at least mbits1 of an address in cidr2 will match cidr1. For
  91 -- example,
  92 --
  93 -- cidr1 = 192.168.1.0/23, cidr2 = 192.168.1.100/24
  94 --
  95 -- Here, cidr2 contains all of 192.168.1.0 through
  96 -- 192.168.1.255. However, cidr1 contains BOTH 192.168.0.0 through
  97 -- 192.168.0.255 and 192.168.1.0 through 192.168.1.255. In essence,
  98 -- what we want to check is that cidr2 "begins with" something that
  99 -- cidr1 CAN begin with. Since cidr1 can begin with 192.168.1, and
 100 -- cidr2 DOES, cidr1 contains cidr2..
 101 --
 102 -- The way that we check this is to apply cidr1's mask to cidr2's
 103 -- address and see if the result is the same as cidr1's mask applied
 104 -- to cidr1's address.
 105 --
 106 contains (Cidr addr1 mbits1) (Cidr addr2 mbits2)
 107     | mbits1 > mbits2 = False
 108     | otherwise = addr1masked == addr2masked
 109     where
 110       addr1masked = apply_mask addr1 mbits1
 111       addr2masked = apply_mask addr2 mbits1
 112
 113
 114 contains_proper :: Cidr -> Cidr -> Bool
 115 contains_proper cidr1 cidr2 =
 116     (cidr1 `contains` cidr2) && (not (cidr1 == cidr2))
 117
 118
 119 -- A CIDR range is redundant (with respect to the given list) if
 120 -- another CIDR range in that list properly contains it.
 121 redundant :: [Cidr] -> Cidr -> Bool
 122 redundant cidrlist cidr = any ((flip contains_proper) cidr) cidrlist
 123
 124
 125 -- First, we look at all possible pairs of cidrs, and combine the
 126 -- adjacent ones in to a new list. Then, we concatenate that list with
 127 -- the original one, and filter out all of the redundancies. If two
 128 -- adjacent Cidrs are combined into a larger one, they will be removed
 129 -- in the second step since the larger Cidr must contain the smaller
 130 -- two.
 131 combine_all :: [Cidr] -> [Cidr]
 132 combine_all cidrs =
 133     combine_contained unique_cidrs
 134     where
 135       unique_cidrs = nubBy equivalent valid_cidr_combinations
 136       valid_cidr_combinations = filter (/= Cidr.None) cidr_combinations
 137       cidr_combinations =
 138           cidrs ++ [ (combine_adjacent x y) | x <- cidrs, y <- cidrs ]
 139
 140
 141 -- Take a list of CIDR ranges and filter out all of the ones that are
 142 -- contained entirelt within some other range in the list.
 143 combine_contained :: [Cidr] -> [Cidr]
 144 combine_contained cidrs =
 145     filter (not . (redundant cidrs)) cidrs
 146
 147
 148 -- If the two Cidrs are not adjacent, return Cidr.None. Otherwise,
 149 -- decrement the maskbits of cidr1 and return that; it will contain
 150 -- both cidr1 and cidr2.
 151 combine_adjacent :: Cidr -> Cidr -> Cidr
 152 combine_adjacent cidr1 cidr2
 153   | not (adjacent cidr1 cidr2) = Cidr.None
 154   | (maskbits cidr1 == Zero) = Cidr.None
 155   | otherwise = cidr1 { maskbits = decrement (maskbits cidr1) }
 156
 157
 158
 159 -- Determine whether or not two CIDR ranges are adjacent. If two
 160 -- ranges lie consecutively within the IP space, they can be
 161 -- combined. For example, 10.1.0.0/24 and 10.0.1.0/24 are adjacent,
 162 -- and can be combined in to 10.1.0.0/23.
 163 adjacent :: Cidr -> Cidr -> Bool
 164 adjacent Cidr.None _ = False
 165 adjacent _ Cidr.None = False
 166 adjacent cidr1 cidr2
 167   | mbits1 /= mbits2 = False
 168   | mbits1 == Maskbits.Zero = False -- They're equal.
 169   | otherwise = (mbits1 == (most_sig_bit_different addr1 addr2))
 170   where
 171     addr1 = ipv4address cidr1
 172     addr2 = ipv4address cidr2
 173     mbits1 = maskbits cidr1
 174     mbits2 = maskbits cidr2
 175
 176
 177
 178
 179
 180 -- HUnit Tests
 181
 182 test_contains :: Test
 183 test_contains =
 184     TestCase $ assertEqual "10.1.1.0/23 contains 10.1.1.0/24" (cidr1 `contains` cidr2) True
 185     where
 186       cidr1 = cidr_from_string "10.1.1.0/23"
 187       cidr2 = cidr_from_string "10.1.1.0/24"
 188
 189
 190 cidr_tests :: [Test]
 191 cidr_tests = [ test_contains ]