Sunday, January 3, 2010

A Scala library for IPv4 related concepts

I've been using the Xmas holidays to write lots of Scala. One of the things I wrote, partially just to learn some more Scala, partially because I believe it can be useful, is a library to work with IPv4 related concepts: IP addresses, IP networks, ranges of IP addresses etc.

In this post, I'll give a short overview of the library, and share some thoughts about my Scala experience while writing it.

The library exposes a few core concepts which can be useful when doing calculations with IP addresses etc.


IpAddress represents an IPv4 address.
val address = new IpAddress("")
IpAddress can be used to make calculations on IP addresses, such as finding the next address.
val address = new IpAddress("")
val next = address + 1
println(next == new IpAddress("")) // prints true


IpAddressRange represents a continuous range of consecutive addresses.
val range = new IpAddressRange(new IpAddress(""), new IpAddress(""))
println(range.contains(new IpAddress("")) // prints true


IpNetworkMask represents a network mask, to be used in an IpNetwork.
val mask1 = new IpNetworkMask("")
val mask2 = IpNetworkMask.fromPrefixLength(25)
println(mask1 == mask2) // prints true

val invalid = new IpNetworkMask("") // throws exception


An IpNetwork is a range (extends IpAddressRange) that can be expressed as a network address and a network mask.
val network1 = new IpNetwork(new IpAddress(""), new IpNetworkMask(""))
val network2 = new IpNetwork("")
println(network1 == network2) // prints true


An IpAddressPool is like a range (extends IpAddressRange) of which certain addresses are "allocated" and others are "free". It could for example be used as part of a DHCP server implementation.
var pool = new IpAddressPool(new IpAddress(""), new IpAddress(""))
println(pool.isFree(new IpAddress(""))) // prints true
pool.allocate(new IpAddress("")) match {
    case (newPool, allocated) => {
            println(newPool.isFree(new IpAddress(""))) // prints false

And Much More

This was only a short introduction. Much more can be done with these types. Have a look at the scaladoc to get an idea of the possibilities.

What I liked about Scala

I became a fan of Scala some time ago already, but there were a few things which struck me as especially nice or elegant while writing this library:
Lazy lists
The IpAddressRange class has a method to list all addresses in the range. Also, the IpAddressPool class has methods to list all the free, and all the allocated addresses. With big ranges, it becomes virtually impossible to return an array or so containing all the addresses. Scala has the Stream concept to deal with this. A Stream is effectively a "lazy list". In other words, a List of which the elements are only evaluated when they are needed. With a recursive implementation, this results in very elegant code:
def addresses(): Stream[IpAddress] = {
    if (first < last) {
        Stream.cons(first, new IpAddressRange(first + 1, last).addresses)
    } else {
        Stream.cons(first, Stream.empty)
Functional or Procedural
Although I try to write most of my scala code as "functional" as possible, sometimes it is nice to be able to fall back on a procedural implementation. To do calculations on IP addresses and network masks, a lot of "bit twiddling" is required. I found it usually easier to write that in a procedural style than purely functional (although that could be due to my limited functional experience as well), e.g.:
def fromLongToPrefixLength(value: Long): Int = {
    val lsb: Long = value & 0xFFFFFFFFL
    var result: Int = 0
    var bit: Long = 1L << 31

    while (((lsb & bit) != 0) && (result & 32)) {
      bit = bit >> 1
      result += 1
The Option type needs no introduction, but it's so much more fun than using null values all over the place.
Scala favours immutable types. This naturally steered me towards making all types in my library immutable as well. Because you can rely on immutable data structures in the Scala library (List, SortedSet, ...), it is much easier than in Java to get it right.
What I might dislike about Scala
h I encountered a few things which seemed a bit awkward or strange. Most of the issues are due to my lack of experience, so I'll give myself some more time to figure out whether they are really things I don't like or not.
Tuples for example, are a concept that I am in doubt about. I used them extensively in the IpAddressPool class. For example, when allocating an address in a pool, the method returns an Option of the allocated address (None if the address was not free) and the new pool (because the IpAddressPool is immutable):
def allocate(toAllocate: IpAddress): (IpAddressPool, Option[IpAddress]) = {...}
This is really easy on the implementation side, but I'm not sure whether I like the client code so much. You either have to access the values in the tuple with "._1" and "._2", which doesn't read easy, or you have to pattern match, which seems a bit verbose. You can also assign the result to a new tuple directly
val pool = new IpAddressPool(new IpAddress(""), new IpAddress(""))
val (newPool, allocatedAddress) = pool.allocate(new IpAddress(""))
but it doesn't seem to be possible to assign the result of a subsequent invocation again to the same tuple (using a var)
val pool = new IpAddressPool(new IpAddress(""), new IpAddress(""))
var (newPool, allocatedAddress) = pool.allocate(new IpAddress(""))

// this won't compile
(newPool, allocatedAddress) = pool.allocate(new IpAddress("")
I've had some usability issues with the collections library. The collections library is being worked on for the upcoming scala 2.8 version, so things will definitely improve.
I also found a bug in the TreeSet implementation of SortedSet, causing the tree to be heavily unbalanced which results in StackOverflowErrors when recursively traversing it (I hope this can get fixed for 2.8 as well).


Besides these minor issues, it was a very positive experience. I happen to have a Java version of this library as well, and I certainly like the scala version much better (both in using and in writing it).


ustunozgur said...

Hi, nice article. You can also use assert statements instead of println's for checking equality. You probably know this already, but just wanted to mention that to other readeres.

KEY said...
This comment has been removed by a blog administrator.