May 222012

I’ve been hacking up a remote shell for our actor based broadcasting system. It’s a read only shell with commands like cd, ls, stat etc. It uses Akka, Netty and Scala with its parser combinators. I was thinking a bit about how to resolve a path. By resolve I mean how to combine the current path with one provided for one of the commands above and making it absolute. My goals was (as always) to only work with immutable data structures (if possible) and make it as tight as possible. By the way, the path that I’m parsing looks like a regular UNIX path. I.e. /foo/bar/../xyz. Here’s the implementation I chose:

def resolvePath(path: List[String]): List[String] = {
  path match {
    case Nil | ".." :: Nil => Nil // Root
    case x @ _ :: Nil => x // Only one element. Not '..'
    case xs =>
      (xs :\ 0 -> List.empty[String]) { (x, acc) =>
        val (skip, ys) = acc
        if (x == "..") skip + 1 -> ys // An element to skip
        else if (skip == 0) 0 -> (x :: ys)  // Prepend element to list
        else skip - 1 -> ys // Decrement skip count
      }._2 // Return path

As you can see the method takes the path as a list of strings. The path /foo/bar would be the list "foo" :: "bar" :: Nil after it’s been parsed. I use a right fold when building up the resolved path. I could have used a left fold which would have made it a bit tighter, but then I would have to reverse the list when done to get the path elements in the correct order. It wouldn’t be that much of an overhead in most cases but I think that a right fold is more appropriate. Why don’t you show me your implementation? Choose your language of choice.