Grammar parser in C++

Recently I stumbled upon implementing a simple parser in C++. The task is very classic, however I couldn't find any good resources on the web to help me out.
I tried different tools (including ANTLR), but finally the easiest way I found was bison + flex. It's unbelievable that this technology from 1989 is still actively developed. Latest stable release is from May 14, 2011. Moreover, many important projects make use of it. Among them are Ruby, PHP, Google Go, Bash shell.
So I decided to create a minimalistic example, which works from scratch.
I published the code on github Calculator, so you can check it out.
The whole example is 88 lines long and evaluates common expressions, like 2+2*2-13*(7+19/2).
Let's start with lexer. In flex, you need to define regular expressions, which produce tokens. Such tokens are later processed by a scanner. So we have to define calculator.lex, like this:

Flex will generate yylex() function, which we can call later to produce tokens.
Next, we need to create a scanner (calculator.y), which specifies a grammar. It's simple like that:

Here, we specify types for all tokens using C/C++ union like structure. Variable $$ is used to store result of particular reductions.
Additionally, we need to specify %left precedence for +, -, *, / operators to resolve shift / reduce conflicts between them.
And that's basically it. We have a working expression parser.
I implemented it in a way, that executable takes a file name containing expressions as an argument.
So you can try ./calculator input.txt to see the result.

Visualizing GIS data in JavaFX 2.0 beta using GeoTools

Geographic data mostly comprises of polygon coordinates sets along with attributes, like country or city name, etc. This is quite easy to visualize in JavaFX, which supports rendering for SVG paths.
In the article, I show how to read such GIS data from ESRI type database files using open source library GeoTools.
The data itself comes for free from www.naturalearthdata.com.
Sample code can be found here: Browse on GitHub.



GIS data usually comes in form of SHP and DBF files. In order to read it, we use GeoTools parser. Following code iterates over so called "features" from within data files and retrieves name attribute and shape geometry.


Next, we need to create JavaFX polygons for each feature from iteration. Small note here. Each feature may comprise of multiple polygons. For example "United States" shape may contain separate polygon for Alaska. So we need additional loop to generate such polygons.
In order to create a polygon in JavaFX, we use Path class along with MoveTo and LineTo path elements. Following snippet does the job.


The remaining part is to implement zoom and panning functionality. This is fairly easy in JavaFX. We can use translate and scale properties from main Group shape. Panning functionality is handled using following snippet:


Zoom is coded this way:


That's it. Now we have basic GIS data viewer in JavaFX 2.

Implementing graph editor in JavaFX using MVC like approach

JavaFX has very good SVG support, embedded into language runtime. This makes it interesting choice for implementing custom UI components, which includes graph editors.
In this article, I show how to create a simple graph editor, using MVC like approach and XML serialization via XStream.

Example can be found here: Launch JNLP, Browse on GitHub.
Application brings graph editing functionality and maximum network flow computation using Ford Fulkerson algorithm



Architecture is divided into Model, View and Controller. I made a slight upgrade to classic understanding of MVC. Classic View was responsible for displaying data only. Here, View consists also of UI parts, which include editable labels or combo boxes. Also, in Classic MVC, Model was responsible for refreshing View after Model changes by sending events to registered views. Here, Controller is responsible for refreshing View after Model changes and Model is just a plain POJO structure. I found such approach easier to implement.

Model consists of Three Java classes (non JavaFX), which represent structure of a graph: MNode, MShape, MConnection. Separating those classes from UI gives benefit of easier serialization. In this case using XStream::toXML(model) does the job. Sample output is like this:


View consists of corresponding UI implementations for Model elements, which are UINode, UILine, UIShape. Here, UINode is connected to MNode through model property. This is Bridge Pattern like approach for splitting class hierarchy of nodes into two.
UINode classes refer to controller to perform user input actions, like delete node.

Controller implements user action logic. This includes add, delete, and drag node. It is also responsible for refreshing UI after model changes. In order to do that easily, it uses Weak Hash Map, which keys are Model nodes and values are UI Nodes. Update function is like this:

Because of Weak Hash Map, removing nodes from Model leads to removing corresponding UI elements from map automaticly.

JavaFX SVG support and Layouts make it easy to render quite good looking nodes and connections.

Drawing arrows in JavaFX

Some time in the past, I was wondering what's the easiest solution for drawing arrow connections between shapes. The problem boils down to computing boundary point for given shape, which intersects with connecting line.
The solution is not so difficult when we consider polygon shapes. But it becomes more difficult considering curves and far more difficult for generic SVG shapes.
In this article, I show a simple way to find such boundary points for generic SVG shapes, utilizing JavaFX "contains" method and simple bisection algorithm.
Following application does the job: Launch JNLP, Browse on GitHub.
Application allows to drag shapes to track shape boundaries.

So, "contains" method in JavaFX allows us to poll any 2D point for intersection with SVG shape. Next, we need to assume, that we know a point inside a shape, from which every ray has exactly one intersection. This includes star-like shapes and ellipses. Next, we can use simple bisection algorithm to find such boundary point. We cut off once length between two points is too small. Following snippet does the job: Next, we need to draw arrows on the ends. In order to do that, we can use JavaFX Affine Transform, which is matrix transformation for SVG path. We need to compute transformation vectors for the matrix. This sounds scarry, but in fact is relatively easy. First vector in matrix is (targetPoint - sourcePoint) / length. Second one is perpendicular to it. Following code applies transformation:

Apache HISE + Apache Camel

Check out this SlideShare Presentation:

Apache HISE + Apache Camel

View more presentations from Rafal Rusin.

jetty webapp osgi way

I will show how to expose simple Jetty OSGi service and use it to register hello world webapp. This app will serve static content from OSGi bundle and implement sample request handler under ServiceMix 4. Code is available here: http://github.com/rafalrusin/jetty-service
Alternative solutions are: using standard OSGi HTTP service http://www.osgi.org/javadoc/r4v42/org/osgi/service/http/HttpService.html to register servlet; and wrap existing WAR application using PAX WEB http://wiki.ops4j.org/display/paxweb/Pax+Web. I won't consider those two, since Jetty itself provides flexible way to handle webapps (including registering servlets). So those two are unnecessary overhead and are less flexible. Anyway those two are usually implemented on top of Jetty.
So the first thing to do is to create Jetty OSGi service. Basicly it will be a Spring Bean exposed to OSGi. Following snippet does the job:

<bean id="jetty-service" class="org.apache.jetty.service.JettyServiceImpl" init-method="init" destroy-method="destroy"/>
<osgi:service id="jetty-service-osgi" ref="jetty-service" interface="org.apache.jetty.service.api.JettyService" />

This will expose jetty-service to OSGi. All other components, which connect to it will wait automaticly until it's registered. Exposed interface has following methods:

public Handler registerApp(String name, Handler handler) throws Exception;
public void unregisterApp(Handler handler) throws Exception;

Those will be invoked to register Hello World application. JettyServiceImpl on the other hand, starts embedded Jetty Server and handles apps registration.

package org.apache.jetty.service;

import org.apache.jetty.service.api.JettyService;
import org.mortbay.jetty.Handler;
import org.mortbay.jetty.Server;
import org.mortbay.jetty.handler.ContextHandler;
import org.mortbay.jetty.handler.ContextHandlerCollection;

public class JettyServiceImpl implements JettyService {
 private Server server;
 private ContextHandlerCollection rootContext;

 public void init() throws Exception {
  server = new Server(8080);
  rootContext = new ContextHandlerCollection();
  server.setHandler(rootContext);
  server.start();
 }

 public void destroy() throws Exception {
  server.stop();
 }

 public Handler registerApp(String name, Handler handler) throws Exception {
  server.stop();
  ContextHandler h = rootContext.addContext("/" + name, name);
  h.setHandler(handler);
  server.start();
  return h;
 }

 public void unregisterApp(Handler handler) throws Exception {
  server.stop();
  rootContext.removeHandler(handler);
  server.start();
 }
}

Next step is to implement sample web app. First, we need to connect jetty-service bean to make it visible in our app.

  <osgi:reference id="jetty-service" interface="org.apache.jetty.service.api.JettyService" bean-name="jetty-service"/>

  <bean class="org.apache.jetty.service.example.HelloWorld" init-method="init" destroy-method="destroy">
    <property name="jettyService" ref="jetty-service"/>
  </bean>

Then, we need to implement sample app.

package org.apache.jetty.service.example;

import java.io.IOException;

import javax.servlet.ServletException;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import org.apache.jetty.service.api.JettyService;
import org.apache.jetty.service.util.BundleResource;
import org.mortbay.jetty.Handler;
import org.mortbay.jetty.HttpConnection;
import org.mortbay.jetty.Request;
import org.mortbay.jetty.handler.AbstractHandler;
import org.mortbay.jetty.handler.ContextHandler;
import org.mortbay.jetty.handler.ContextHandlerCollection;
import org.mortbay.jetty.handler.ResourceHandler;

public class HelloWorld {

 private JettyService jettyService;
 private Handler registered;

 public void setJettyService(JettyService jettyService) {
  this.jettyService = jettyService;
 }

 public void init() throws Exception {
  ContextHandlerCollection handler = new ContextHandlerCollection();

  handler.addContext("/app", "app").setHandler(new AbstractHandler() {
   public void handle(String target, HttpServletRequest request,
     HttpServletResponse response, int arg3) throws IOException,
     ServletException {
          response.setContentType("text/html");
          response.setStatus(HttpServletResponse.SC_OK);
          response.getWriter().println("<h1>Hello World from Java</h1>" + request.getParameterMap());

          Request base_request = (request instanceof Request) ? (Request)request:HttpConnection.getCurrentConnection().getRequest();
          base_request.setHandled(true);
   }
  });

  ResourceHandler resourceHandler = new ResourceHandler();
  resourceHandler.setBaseResource(new BundleResource(getClass().getResource("/static")));
  ContextHandler contextHandler = handler.addContext("","");
  contextHandler.setHandler(resourceHandler);

  registered = jettyService.registerApp("helloWorld", handler);
 }

 public void destroy() throws Exception {
  jettyService.unregisterApp(registered);
 }
}

Here, we register sample request handler at 'app' sub path and serve static content from jar using BundleResource. Last thing is registering app using jettyService under 'helloWorld' context. So our application will be exposed under http://localhost:8080/helloWorld/ address.
ServiceMix has also so called features. This is the way to collect multiple dependencies under a single name. So we have to create features.xml file, like this:

<features>
    <feature name="jetty-service" version="${project.version}">
        <bundle>mvn:org.apache.jetty.service/service/${project.version}</bundle>
    </feature>

    <feature name="example-jetty-service-helloworld" version="${project.version}">
        <feature version="${project.version}">jetty-service</feature>
        <bundle>mvn:org.apache.jetty.service/example-helloworld/${project.version}</bundle>
    </feature>
</features>

Basicly, we can provide particular dependencies for our project.
Next, we do 'mvn install' on our project and run apache-servicemix-4.2.0-fuse-01-00/bin/servicemix karaf console. On the console, we need to type following commands:

features:addUrl mvn:org.apache.jetty.service/service-karaf/0.1.0-SNAPSHOT/xml/features
features:install example-jetty-service-helloworld
osgi:list

[ 230] [Active     ] [            ] [Started] [   60] Unnamed - org.apache.jetty.service:service:bundle:0.1.0-SNAPSHOT (0.1.0.SNAPSHOT)
[ 231] [Active     ] [            ] [Started] [   60] Unnamed - org.apache.jetty.service:example-helloworld:bundle:0.1.0-SNAPSHOT (0.1.0.SNAPSHOT)

Now, we can enter http://localhost:8080/helloWorld/ to test our app.
And that's it. OSGi and ServiceMix 4 features enable easy way to use dynamic modules in web apps. For example, it's very easy to build simple web framework with loadable components on page (something like mini implementation of Portlets).

Integration Tests for SMX4 with Python

Integration tests and unit tests are important for project quality. Unit tests usually are well suited for developer to verify his changes in runtime. On the other hand, integration tests, are for target user to verify that project's features in the way he interacts with project, work properly. In this article, I will show how to automate integration tests for ServiceMix 4 using SoapUI testrunner and a simple python script.
The idea is to spawn ServiceMix 4 Karaf console and interact with it using python expect library. During this interaction, SoapUI testrunner script is invoked in order to run SoapUI tests.
First, we need to grab SMX4_DIR and SOAPUI_DIR environment variables in our script, like this:

SMX4_DIR=os.getenv("SMX4_DIR")
SOAPUI_DIR=os.getenv("SOAPUI_DIR")

This way, we can invoke later our script using following shell command:

SMX4_DIR=/some/path SOAPUI_DIR=/some/other/path ./our-python-script

Then, we need to spawn ServiceMix 4 console by using python expect library:

import pexpect
import time
import sys
child = pexpect.spawn("bin/servicemix")
child.logfile = sys.stdout
child.expect("karaf.*>")
time.sleep(3)

Here, we set logfile to stdout in order to see our automated interaction with ServiceMix console. Then we need to wait for ServiceMix console command prompt, which would mean console is ready. Additionally, we need to wait a few seconds to avoid problems with running commands too early (which is a kind of small bug in ServiceMix). Then, we can install our features, which we want to test. This example starts Apache HISE test bundle, which loads also Apache HISE engine from dependencies.

child.sendline("features:addUrl mvn:org.apache.hise/hise-karaf/0.3.0-SNAPSHOT/xml/features");
child.expect("karaf.*>")
child.sendline("features:install hise-h2-test-example-osgi")
child.expect("karaf.*>")

Next, we need to wait until the feature is properly started. ServiceMix 4 OSGi container initializes bundles in background, so it's not enough to wait for command prompt to have it started (there doesn't seem to exist a "wait-until-started" console command). So we grep in a loop over installed bundles and see if status is started. In this example, we do 30 retries every second and fail our integration test script after this period, by raising exception.

child.sendline("features:addUrl mvn:org.apache.hise/hise-karaf/0.3.0-SNAPSHOT/xml/features");
rep=0
while True:
    child.sendline("osgi:list|grep -i hise-test-example-osgi")
    l=child.readline()
    l=child.readline()
    if re.match(".*Started", l) != None:
        break
    time.sleep(1)
    child.expect("karaf.*>")
    rep=rep+1
    if rep>30:
        raise Exception("Bundle not installed")

Next, we need to run SoapUI testrunner in order to execute test cases. We need to implement syscall method in order to fail integration tests if SoapUI testrunner completes with fault (non-zero exit code).

import os
def syscall(c):
    if os.system(c) != 0:
        raise Exception("Sys call failed: " + c)

syscall(SOAPUI_DIR + "/bin/testrunner.sh -f results hise-soapui-project.xml")

At the end, we can exit gracefully from ServiceMix console by using shutdown command, like this:

child.sendline("shutdown")

And that's it. Full code of integration test script is available in Apache HISE sources, from Apache repository http://svn.apache.org/repos/asf/incubator/hise/trunk/itest/itest.