Maurits thinks aloud

Refactoring Java using Clojure with the Eclipse Java development tools (JDT)

Not a very catchy title this time, since this post will be mostly about hardcore nerdy coding. In my previous post I talked about the business value of elegant code. I argued that cleaning up an existing codebase in the maintenance phase still makes a lot of sense, but only if it can be done cheaply. One of the ways to make it cheap (cost-effective might be a better word if you need to sell this to your management) is of course to automate the refactoring process.

The problem

By automating I mean automating detection of code smell and automating fixing this smell. This in contrast to tools that are very good at detecting but don’t fix anything. For example Sonar. Also in contrast to most IDE’s that allow you to select a piece of code and select for example the ‘Extract method‘ action from the menu. That certainly is helpful, but your IDE will probably not detect if that is needed. It will just execute what you tell it to do.

Let me first show you an example of some Java code that I would like to refactor automatically:

public class A {
   int answer() {
      return (42);
   }
}

I case you already haven’t noticed: in the code above the return statement has an extra pair of parenthesis. You can find many discussions on the internet on why this is or isn’t a good thing, but personally I don’t like them for the simple reason that return is a keyword and not a function. Extra parenthesis just add visual noise. So what I would like to see instead is:

public class A {
   int answer() {
      return 42;
   }
}

This simple refactoring is already surprisingly difficult if you want to do this with a set of regular expressions since you need the context of the return statement. For example you have to be sure it’s not part of a comment or a string. The alternative is to fully parse the code and create an abstract syntax tree (AST). Again you can create one yourself using for example ANTLR and a grammar for the language of your choice. I decided to use the Eclipse Java development tools in combination with Clojure. The scope of my experiment: being able to refactor above example.

Preparation

I got the idea for this blogpost from ‘A complete standalone example of ASTParser‘. This post lists all the Eclipse libraries you need. You will have to add these libraries (8) to your own local Maven repository. Assuming you are using Leiningen 2, I followed these steps described by Stuart Sierra. For example to add an artifact to my local Maven repository called maven_repository within my Leiningen project, I used:

mvn deploy:deploy-file -DgroupId=org.eclipse -DartifactId=text -Dversion=3.5.200 \
-Dpackaging=jar -Dfile=/Users/maurits/development/eclipse/plugins/org.eclipse.text_3.5.200.v20120523-1310.jar \
-Durl=file:maven_repository

I added all the dependencies do my project file. It looks like this:

(defproject ast "0.1.0-SNAPSHOT"
  :description "FIXME: write description"
  :url "http://example.com/FIXME"
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :dependencies [[org.clojure/clojure "1.5.0"]
                 [org.eclipse.core/contenttype "3.4.200"]
                 [org.eclipse.core/jobs "3.5.300"]
                 [org.eclipse.core/resources "3.8.1"]
                 [org.eclipse.core/runtime "3.8.0"]
                 [org.eclipse.equinox/common "3.6.100"]
                 [org.eclipse.equinox/preferences "3.5.0"]
                 [org.eclipse.jdt/core "3.8.2"]
                 [org.eclipse/osgi "3.8.1"]
                 [org.eclipse/text "3.5.200"]]
  :repositories {"local" ~(str (.toURI (java.io.File. "maven_repository")))})

Now that the preparations are done we can finally start to write the actual refactoring code.

Refactor it!

First the code to create the AST from the Java code and the actual example I am going to use:

(ns ast.core
  (:import (org.eclipse.jdt.core.dom ASTParser AST ASTNode)))

(defn create-ast
  "Create AST from a string"
  [s]
  (let [parser (ASTParser/newParser(AST/JLS3))]
    (.setSource parser (.toCharArray s))
    (.createAST parser nil)
    ))

(def example
     (create-ast (str
                  "public class A {"
                  "   int foo() {"
                  "      return (42);"
                  "   }"
                  ""
                  "   int bar() {"
                  "      return 13;"
                  "   }"
                  "}")))

As you will notice creating an AST with the Eclipse JDT only takes a very few lines of code: on line 7 I create a JLS3 (Java Language Specification 3) parser, Line 8 tells the parser where it will get its source (in this case a string) and line 9 creates the AST. Next I need some helper functions:

(defn parenthesized-expression? [expr]
  (= (.getNodeType expr) ASTNode/PARENTHESIZED_EXPRESSION))

(defn return-statement? [stmt]
  (= (.getNodeType stmt) ASTNode/RETURN_STATEMENT))

(defn parenthesized-return-statement? [stmt]
  (and (return-statement? stmt)
       (parenthesized-expression? (.getExpression stmt))))

(defn method-declaration? [body]
  (= (.getNodeType body) ASTNode/METHOD_DECLARATION))

Details about for example ASTNode can be found in the Eclipse JDT API Specification

Next the are 4 functions that zoom in into the code we would like to refactor. You will notice that I use doseq quite a lot since the actual AST manipulation (the refactoring) will be in-place and thus has side effects. This is not always avoidable when using Java libraries from within your Clojure code. We could write an immutable version that leaves the original AST intact by returning copies of the AST though. Such functionality is supported by the Eclipse JDT.

(defn refactor-block [block]
  (doseq [stmt (filter parenthesized-return-statement? (.statements block))]
    (refactor-return stmt)))

(defn refactor-method [method]
  (refactor-block (.getBody method)))

(defn refactor-type [type]
  (doseq [method (filter method-declaration? (.bodyDeclarations type))]
    (refactor-method method)))

(defn refactor [ast]
  (doseq [type (.types ast)]
    (refactor-type type)))

As you can see we filter out the return statements that need refactoring using the parenthesized-return-statement? predicate. Only thing left is to do the actual refactoring:

(defn refactor-return [stmt]
  (let [exp (.getExpression (.getExpression stmt))
        ast (.getAST exp)
        node (ASTNode/copySubtree ast exp)]
    (.setExpression stmt node)))

In this code we first get to the expression within the parentheses, hence the double .getExpression. Note: this code only strips one level of parentheses. Next we make a copy of the expression and finally we assign it back to our return statement, effectively removing the outer parentheses.

This code is easy to test via the REPL. You will see something similar to:

ast.core=> example
#<CompilationUnit public class A {
  int foo(){
    return (42);
  }
  int bar(){
    return 13;
  }
}
>
ast.core=> (refactor example)
nil
ast.core=> example
#<CompilationUnit public class A {
  int foo(){
    return 42;
  }
  int bar(){
    return 13;
  }
}
>
ast.core=>

Finally the complete code:

(ns ast.core
  (:import (org.eclipse.jdt.core.dom ASTParser AST ASTNode)))

(defn create-ast
  "Create AST from a string"
  [s]
  (let [parser (ASTParser/newParser(AST/JLS3))]
    (.setSource parser (.toCharArray s))
    (.createAST parser nil)
    ))

(def example
     (create-ast (str
                  "public class A {"
                  "   int foo() {"
                  "      return (42);"
                  "   }"
                  ""
                  "   int bar() {"
                  "      return 13;"
                  "   }"
                  "}")))

(defn parenthesized-expression? [expr]
  (= (.getNodeType expr) ASTNode/PARENTHESIZED_EXPRESSION))
  
(defn return-statement? [stmt]
  (= (.getNodeType stmt) ASTNode/RETURN_STATEMENT))

(defn parenthesized-return-statement? [stmt]
  (and (return-statement? stmt)
       (parenthesized-expression? (.getExpression stmt))))

(defn method-declaration? [body]
  (= (.getNodeType body) ASTNode/METHOD_DECLARATION))

(defn refactor-return [stmt]
  (let [exp (.getExpression (.getExpression stmt))
        ast (.getAST exp)
        node (ASTNode/copySubtree ast exp)]
    (.setExpression stmt node)))

(defn refactor-block [block]
  (doseq [stmt (filter parenthesized-return-statement? (.statements block))]
    (refactor-return stmt)))

(defn refactor-method [method]
  (refactor-block (.getBody method)))

(defn refactor-type [type]
  (doseq [method (filter method-declaration? (.bodyDeclarations type))]
    (refactor-method method)))

(defn refactor [ast]
  (doseq [type (.types ast)]
    (refactor-type type)))

As always, don’t hesitate to leave comments or email if you have questions/remarks/suggestions.

Have fun!

Lazily stealing..errr. getting data from the Dutch Rijksmuseum

Last year the Dutch Rijksmuseum published an API that allows a developer to retrieve information and images from a collections of more than 110,000 items. You have to register for an API key first.

Unless you are looking for a specific item, the interface every time returns 100 items in XML format. You will also get a resumption token so you can query for the next 100 items. I imagined it would be useful to abstract from this, using a lazy sequence in Clojure. So let me show you the resulting code and a brief explanation:

(ns rijksmuseum.core
  (:require [clojure.xml :as xml]
            [clojure.zip :as zip]
            [clojure.data.zip.xml :as zf]))

We will have to parse some XML that is returned, so we start with adding some convenient libraries. If you are not familiar with Clojure zippers, please look it up in the documentation and numerous blogs. They make navigating XML almost painless.

(def api-key "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx")
(def base-url (str "https://www.rijksmuseum.nl/api/oai/" api-key))

In line 5 you will have to fill in your own API key. Line 7 defines the base url that is used for all queries.

(defn- build-query [resumption-token]
  (str base-url "/?verb=ListRecords&"
       (if (nil? resumption-token)
         "set=collectie_online&metadataPrefix=oai_dc"
         (str "resumptiontoken=" resumption-token))))

The routine build-query builds up a query. If there is no resumption token yet, the resulting query loads the first data. Otherwise, it will continue with the next batch of records. Currently the Rijksmuseum API supports two kinds of queries. You can either ask for a list of records (using verb=ListRecords) or you can ask for a specific record (using verb=GetRecord and an identifier). The API documentation has all the details.

We will first start with a couple of helper routines. Basically they extract the information we are interested in from a XML stream:

(defn- get-records [zipper]
  (zf/xml-> zipper :ListRecords :record))

(defn- get-resumption-token [zipper]
  (zf/xml1-> zipper :ListRecords :resumptionToken zf/text))

get-records extracts the records from the (zipped) XML response. get-resumption-token returns (I’m sure you already guessed) the resumption token for our next query.

Now comes the construction of the lazy sequence:

(defn- lazy-get-works [resumption-token]
  (lazy-seq
   (let [zipper (zip/xml-zip (xml/parse (build-query resumption-token)))
         works (get-records zipper)
         token (get-resumption-token zipper)]
     (concat works (lazy-get-works token)))))

(defn get-works
  "Return all works as a lazy sequence"
  []
  (lazy-get-works nil))

lazy-seq (line 18) is a macro that creates a lazy sequence out of a body of expressions. Next we create a query, parse the resulting XML and create a zip structure. All in one single line of code: line 19. All we have to do now is to extract the records (called works in line 20), the resumption token (line 21) and call ourselves recursively (line 22). Don’t be afraid of stack overflows: the lazy-seq macros takes care of this.

Now we are ready to use our lazy sequence. The next example creates a list with the image url’s of the first 10 items in the collection:

(defn get-image-url [work]
  (zf/xml1-> work :metadata :oai_dc:dc :dc:format zf/text))

(map get-image-url (take 10 (get-works)))

Don’t go overboard with requesting all items in the collection at once. Retrieving 1000 items takes about 1 minute, so the calls to the API are most probably throttled. Anyhow, have fun with lazily stealing works of art!

Calculating Bell numbers in a single tweet

Recently I stumbled upon a white paper by Roger Sessions called “The Mathematics of IT Simplification”. In this paper he describes an approach called synergistic partitioning, which is based on the mathematics of sets, equivalence relations, and partitions. One of the topics that comes up in this article is how many ways there are to partition N elements. The answer to this is well-known and called the Nth Bell number.

The 52 partitions of a set with 5 elements

The Wikipedia page that explains the Bell number also shows two implementations on how to calculate them, one in Ruby and the other one in Python. The Ruby version needs 17 lines of code, the Python version 12 lines. I have the peculiar habit of intriguing/annoying my colleagues at work with the statement that using Clojure the solution to any programming problem fits into one single tweet. In other words: 140 characters.

I’ll start with my first attempt:

(defn append-ele [s x] (concat s (list (+ x (last s)))))

(defn next-row [s]
  (reduce append-ele (list (last s)) s))

(defn bell [n]
  (loop [n n s '(1) b s]
    (if (= n 1)
      (reverse b)
      (recur (dec n) (next-row s) (cons (last s) b)))))

(println (bell 9))

The first function (append-ele) appends a single new element to a row in the Bell triangle (explained in the Wikipedia article). In several ways this implementation is suboptimal since concat can only concatenate sequences, so I have to convert the single element to a list first. And what’s worse, appending at the end of a sequence is expensive since it’s computation is O(N), while prepending would only take one single operation.

The function next-row calculates the next row in the Bell triangle. This row always starts with the last element of the previous row. I implemented this by a simple reduce over the elements of the previous row.

And finally the function bell returns a sequence with the first n Bell numbers. I use a loop/recur to avoid a stack overflow. The sequence of Bell numbers is constructed in reverse order, so at the end (line 9) I have to call reverse.

While this version is already pretty short (10 lines, without the printing), this still won’t fit in a single tweet. So the next step was to remove the first two helper functions and inline all the code into a single function. Warning: this is not good coding practice! With this disclaimer, here is the resulting code:

(defn bell [n]
  (loop [n n s '(1) b s]
    (if (= n 1)
      (reverse b)
      (recur (dec n)
             (reduce #(concat % (list (+ %2 (last %)))) (list (last s)) s)
             (cons (last s) b)))))

Without the whitespace this implementation is 170 characters. Almost there! As you can see there are still some ‘expensive’ keywords like concat and reverse (6 and 7 characters!) and some annoying conversions from single numbers to lists. The only way to avoid this is to use a specialized data structure like vector instead of a sequence:

(defn bell [n]
  (loop [n n s [1] b s]
    (if (= n 1)
      b
      (recur (dec n)
             (reduce #(conj % (+ %2 (last %))) [(last s)] s)
             (conj b (last s))))))

Finally the code (without the indentation) fits into 140 characters. One caveat: I use conj which nicely appends an element to the end of a vector. However this behaviour of conj is not guaranteed. It is allowed to add an element anywhere in a sequence. When you use a list for example, the element is prepended. Because of this he above algorithm is O(N^2).

I will leave it as an exercise for the reader to implement the Bell number calculation as a lazy sequence so that you can use for example (take 9 (bell)). Have fun.