Creating Expression evaluation Engine

Introduction

Have you ever been tasked with creating a piece of logic that would parse and evaluate (execute) a String Expression? It seems a very niche requirement in today's world, but it can happen (and it happened to me). I'd like to go over the thought process that led me to implementing a very pragmatic and yet extremely powerful solution.

Requirements

The language would have to be dead simple and easy enough for the business folks to write the Expressions. Ideally it should follow an Excel-like formula syntax, with possibility of more advanced constructs (functions, true 'if's and loops) for the pro users.

Choices

I've started with listing all possible choices/routes I could follow to achieve my goal. The first that came into my mind were:

use a JavaScript parser - for example Nashorn, and write Expressions in JS

unfortunately Nashorn is deprecated since Java 11, so it wouldn't make sense to use it
JavaScript may be too confusing and too complex for business users

find a ready-to-go Expression engine library

I've looked for any lib matching my criteria but everything that I've found was either too poorly documented, too poorly maintained or offered too complex (very Java-like) syntax

create my own "language" from scratch using ANTLR

It seemed that I was left with creating something on my own. However ANTLR, although extremely powerful, seemed to me like an overkill. I would have to introduce an entirely new language (the ANTLR grammar files) to define the syntax of my Expressions.

So is there no way to create a simple, powerful, extensible and flexible Expression language other than creating it from scratch? Wait... what about...

Templates?

I was pondering the thought of creating the Engine from scratch and then it hit me. What about Templating Engines? You know - those ancient things we used to render our Views prior to the whole SPA and Angular/React revolution? From the good ol' true MVC days?

They were supposed to be simple enough for the UI/Front End developers (that would not necessarily have to posses vast coding knowledge) to operate them
They had to have some sort of extensibility to allow developers to introduce new elements
They had to be a way to programmatically call the Templating Engine and evaluate a String-based Template

OK, I had a fresh lead. I was excited as hell. And I've started looking...

Elimination

I've started with the usual suspects from the Java world - Velocity, FreeMarker, Thymeleaf. And I got depressed very fast. None of them offered a business-user friendly syntax - all of them were (and still are) a prehistoric HTML/XML based nightmare. I was starting to worry that Templating Engines are so niche these days that no one has created anything truly innovative and modern in years. But when faced with the alternative in a form of ANTLR beast, I didn't want to give up so fast. I've recalled from my PHP days that PHP had this wonderful Templating Engine called Twig. It was a port of Django Templates and/or Jinja Templates from Python. It was really nice, simple and very flexible. So I've started looking for any Java port of this Engine. The first lead was the JTwig. It was a straight up attempt to port Twig into Java. Unfortunately it was abandoned some time ago and I didn't want to get into something that is not maintained. But this discovery has encouraged me to keep looking. And after some more digging through the Internet, bingo! I've found the perfect candidate! Everyone, meet Pebble Templates!

The Chosen One

Pebble is a Templating Engine inspired by Twig, but has its own things going on. It doesn't aim for 100% compatibility, but rather for ease of use and performance. OK, so now that we finally have something to work with, how do we turn a Templating Engine into our Expression Evaluator?

Let's start with adding the Maven dependency:

<dependency>
	<groupId>io.pebbletemplates</groupId>
	<artifactId>pebble</artifactId>
	<version>3.1.5</version>
</dependency>

Then we can create our first, dead simple Expression to check if everything works as advertised:

    @Test
    public void pebbleExpressionEngine() throws IOException {
        //Create an instance of Pebble Engine that would fetch 
        //the Template from String instead of a File
        PebbleEngine engine = new PebbleEngine.Builder()
                .loader(new StringLoader())
                .build();
        
        //Create an Expression that is understandable by Pebble
        String expression = convertExpressionToTemplate("2 + 2");

        //Parse the Expression into a compiled Pebble Template
        PebbleTemplate template = engine.getTemplate(expression);

        //Execute the compiled Expression
        Writer writer = new StringWriter();
        template.evaluate(writer);
        String result = writer.toString().trim();

        //Check that the Expression was correctly executed
        assertEquals(result, "4");
    }

    private String convertExpressionToTemplate(String expression) {
        return String.format("{{ %s }}", expression);
    }

Wow! It works!

OK so how do we expand from that? Well, now Sky is the limit. We can:

use built in Pebble functions:

 String expression = convertExpressionToTemplate("max(2, 4)");

define our own functions using flexible Pebble API:

    @Test
    public void pebbleExpressionEngine() throws IOException {
        //Create an instance of Pebble Engine that would fetch
        //the Template from String instead of a File
        PebbleEngine engine = new PebbleEngine.Builder()
                .loader(new StringLoader())
                //add our custom function
                .extension(new AbstractExtension() {
                    @Override
                    public Map<String, Function> getFunctions() {
                        return Map.of("hello", new HelloFunction());
                    }
                })
                .build();

        //Create an Expression that is understandable by Pebble
        String expression = convertExpressionToTemplate("hello('world')");

        //Parse the Expression into a compiled Pebble Template
        PebbleTemplate template = engine.getTemplate(expression);

        //Execute the compiled Expression
        Writer writer = new StringWriter();
        template.evaluate(writer);
        String result = writer.toString().trim();

        //Check that the Expression was correctly executed
        assertEquals(result, "Hello world!");
    }

    //define our custom function
    public static class HelloFunction implements Function {

        @Override
        public Object execute(Map<String, Object> map, 
                              PebbleTemplate pebbleTemplate, 
                              EvaluationContext evaluationContext, 
                              int i) {
            return String.format("Hello %s!", map.get("who"));
        }

        @Override
        public List<String> getArgumentNames() {
            return List.of("who");
        }
    }

    private String convertExpressionToTemplate(String expression) {
        return String.format("{{ %s }}", expression);
    }

use full Pebble syntax with mutliline Pebble scripts instead of simple Excel-like Expressions:

@Test
    public void pebbleExpressionEngine() throws IOException {
        //Create an instance of Pebble Engine that would fetch
        //the Template from String instead of a File
        PebbleEngine engine = new PebbleEngine.Builder()
                .loader(new StringLoader())
                .build();

        //Create an Expression that is understandable by Pebble
        String expression = """
                {% if var == 1 %}
                one
                {% else %}
                not one
                {% endif %}
                """;

        //Parse the Expression into a compiled Pebble Template
        PebbleTemplate template = engine.getTemplate(expression);

        //Execute the compiled Expression
        Writer writer = new StringWriter();
        template.evaluate(writer, Map.of("var", 1));
        String result = writer.toString().trim();

        //Check that the Expression was correctly executed
        assertEquals(result, "one");
    }

further extend Pebble to define new Syntax (like operators, code blocks etc) that matches our needs!

Conclusion

Using Pebble as an Expression Evaluation engine is great, because it:

is dead simple to implement
is easy to extend, customize and maintain
allows the new developers to quickly jump into the development without having to learn any new syntax and/or paradigm (Pebble is fully extensible using plain old Java)
allows to define your own syntax that is tailored to your own requirements
offers great performance - every Template is compiled to a Java Object prior to the execution - you can execute given Epression multiple times (with different data passed into it) without any parsing/compilation overhead
is regularly maintained and you can propose your own changes (and they even get merged!)

Is there anything more we could want from an Expression Evaluation Engine? Well, I don't know about you guys, but I'm fully satisfied.

Till the next time!

Search This Blog