creating a simple rule engine in java

Question

I am exploring different ways to create a simple business rule engine in Java. I need to present the client with a simple webapp that lets him configure a bunch of rules. A sample of rule base might look like this :

Here's example:

 IF (PATIENT_TYPE = "A" AND ADMISSION_TYPE="O")  SEND TO OUTPATIENT  ELSE IF PATIENT_TYPE = "B"   SEND TO INPATIENT 

The rule engine is pretty simple, the final action could be just one of two actions, sending to inpatient or outpatient. The operators involved in an expression could be =,>,<,!= and logical operators between expressions are AND, OR and NOT.

I want to build a web application where user will write in a small script in a textarea, and I would evaluate the expression - this way, business rules are explained in simple English and business user has complete control on logic.

From the research I did so far, I came across, ANTLR and writing my own scripting language as possible options to solve this problem. I haven't explore options like Drools rules engine, because I have a feeling that it might be an overkill here. Have you had any experience in solving these kind of problems? If yes, how did you go about it?

Answer 1

Implementing a simple rule-based evaluation system in Java isn't that hard to achieve. Probably the parser for the expression is the most complicated stuff. The example code below uses a couple of patterns to achieve your desired functionality.

A singleton pattern is used to store each available operation in a member map. The operation itself use a command pattern to provide flexible extensibility while the respective action for a valid expression does make use of the dispatching pattern. Last bust not least, a interpreter pattern is used for validating each rule.

An expression like presented in your example above consists of operations, variables and values. In reference to a wiki-example everything that can be declared is an Expression. The interface therefore looks like this:

import java.util.Map;  public interface Expression {     public boolean interpret(final Map<String, ?> bindings); } 

While the example on the wiki-page returns an int (they implement a calculator), we only need a boolean return value here to decide if a expression should trigger an action if the expression evaluates to true.

An expression can, as stated above, be either an operation like =, AND, NOT, ... or a Variable or its Value. The definition of a Variable is enlisted below:

import java.util.Map;  public class Variable implements Expression {     private String name;      public Variable(String name)     {         this.name = name;     }      public String getName()     {         return this.name;     }      @Override     public boolean interpret(Map<String, ?> bindings)     {         return true;     } } 

Validating a variable name does not make that much sense, therefore true is returned by default. The same holds true for a value of a variable which is kept as generic as possible on defining a BaseType only:

import java.util.Map;  public class BaseType<T> implements Expression {     public T value;     public Class<T> type;      public BaseType(T value, Class<T> type)     {         this.value = value;         this.type = type;     }      public T getValue()     {         return this.value;     }      public Class<T> getType()     {         return this.type;     }      @Override     public boolean interpret(Map<String, ?> bindings)     {         return true;     }      public static BaseType<?> getBaseType(String string)     {         if (string == null)             throw new IllegalArgumentException("The provided string must not be null");          if ("true".equals(string) || "false".equals(string))             return new BaseType<>(Boolean.getBoolean(string), Boolean.class);         else if (string.startsWith("'"))             return new BaseType<>(string, String.class);         else if (string.contains("."))             return new BaseType<>(Float.parseFloat(string), Float.class);         else             return new BaseType<>(Integer.parseInt(string), Integer.class);     } } 

The BaseType class contains a factory method to generate concrete value types for a specific Java type.

An Operation is now a special expression like AND, NOT, =, ... The abstract base class Operation does define a left and right operand as the operand can refer to more than one expression. F.e. NOT probably only refers to its right-hand expression and negates its validation-result, so true turn into false and vice versa. But AND on the other handside combines a left and right expression logically, forcing both expression to be true on validation.

import java.util.Stack;  public abstract class Operation implements Expression {     protected String symbol;      protected Expression leftOperand = null;     protected Expression rightOperand = null;      public Operation(String symbol)     {         this.symbol = symbol;     }      public abstract Operation copy();      public String getSymbol()     {         return this.symbol;     }      public abstract int parse(final String[] tokens, final int pos, final Stack<Expression> stack);      protected Integer findNextExpression(String[] tokens, int pos, Stack<Expression> stack)     {         Operations operations = Operations.INSTANCE;          for (int i = pos; i < tokens.length; i++)         {             Operation op = operations.getOperation(tokens[i]);             if (op != null)             {                 op = op.copy();                 // we found an operation                 i = op.parse(tokens, i, stack);                  return i;             }         }         return null;      } } 

Two operations probably jump into the eye. int parse(String[], int, Stack<Expression>); refactors the logic of parsing the concrete operation to the respective operation-class as it probably knows best what it needs to instantiate a valid operation. Integer findNextExpression(String[], int, stack); is used to find the right hand side of the operation while parsing the string into an expression. It might sound strange to return an int here instead of an expression but the expression is pushed onto the stack and the return value here just returns the position of the last token used by the created expression. So the int value is used to skip already processed tokens.

The AND operation does look like this:

import java.util.Map; import java.util.Stack;  public class And extends Operation {         public And()     {         super("AND");     }      public And copy()     {         return new And();     }      @Override     public int parse(String[] tokens, int pos, Stack<Expression> stack)     {         Expression left = stack.pop();         int i = findNextExpression(tokens, pos+1, stack);         Expression right = stack.pop();          this.leftOperand = left;         this.rightOperand = right;          stack.push(this);          return i;     }      @Override     public boolean interpret(Map<String, ?> bindings)     {         return leftOperand.interpret(bindings) && rightOperand.interpret(bindings);     } } 

In parse you probably see that the already generated expression from the left side is taken from the stack, then the right hand side is parsed and again taken from the stack to finally push the new AND operation containing both, the left and right hand expression, back onto the stack.

NOT is similar in that case but only sets the right hand side as described previously:

import java.util.Map; import java.util.Stack;  public class Not extends Operation {         public Not()     {         super("NOT");     }      public Not copy()     {         return new Not();     }      @Override     public int parse(String[] tokens, int pos, Stack<Expression> stack)     {         int i = findNextExpression(tokens, pos+1, stack);         Expression right = stack.pop();          this.rightOperand = right;         stack.push(this);          return i;     }      @Override     public boolean interpret(final Map<String, ?> bindings)     {         return !this.rightOperand.interpret(bindings);     }     } 

The = operator is used to check the value of a variable if it actually equals a specific value in the bindings map provided as argument in the interpret method.

import java.util.Map; import java.util.Stack;  public class Equals extends Operation {           public Equals()     {         super("=");     }      @Override     public Equals copy()     {         return new Equals();     }      @Override     public int parse(final String[] tokens, int pos, Stack<Expression> stack)     {         if (pos-1 >= 0 && tokens.length >= pos+1)         {             String var = tokens[pos-1];              this.leftOperand = new Variable(var);             this.rightOperand = BaseType.getBaseType(tokens[pos+1]);             stack.push(this);              return pos+1;         }         throw new IllegalArgumentException("Cannot assign value to variable");     }      @Override     public boolean interpret(Map<String, ?> bindings)     {         Variable v = (Variable)this.leftOperand;         Object obj = bindings.get(v.getName());         if (obj == null)             return false;          BaseType<?> type = (BaseType<?>)this.rightOperand;         if (type.getType().equals(obj.getClass()))         {             if (type.getValue().equals(obj))                 return true;         }         return false;     } } 

As can be seen from the parse method a value is assigned to a variable with the variable being on the left side of the = symbol and the value on the right side.

Moreover the interpretation checks for the availability of the variable name in the variable bindings. If it is not available we know that this term can not evaluate to true so we can skip the evaluation process. If it is present, we extract the information from the right hand side (=Value part) and first check if the class type is equal and if so if the actual variable value matches the binding.

As the actual parsing of the expressions is refactored into the operations, the actual parser is rather slim:

import java.util.Stack;  public class ExpressionParser {     private static final Operations operations = Operations.INSTANCE;      public static Expression fromString(String expr)     {         Stack<Expression> stack = new Stack<>();          String[] tokens = expr.split("\\s");         for (int i=0; i < tokens.length-1; i++)         {             Operation op = operations.getOperation(tokens[i]);             if ( op != null )             {                 // create a new instance                 op = op.copy();                 i = op.parse(tokens, i, stack);             }         }          return stack.pop();     } } 

Here the copy method is probably the most interesting thing. As the parsing is rather generic, we do not know in advance which operation is currently processed. On returning a found operation among the registered ones results in a modification of this object. If we only have one operation of that kind in our expression this does not matter - if we however have multiple operations (f.e. two or more equals-operations) the operation is reused and therefore updated with the new value. As this also changes previously created operations of that kind we need to create a new instance of the operation - copy() achieves this.

Operations is a container which holds previously registered operations and maps the operation to a specified symbol:

import java.util.HashMap; import java.util.Map; import java.util.Set;  public enum Operations {     /** Application of the Singleton pattern using enum **/     INSTANCE;      private final Map<String, Operation> operations = new HashMap<>();      public void registerOperation(Operation op, String symbol)     {         if (!operations.containsKey(symbol))             operations.put(symbol, op);     }      public void registerOperation(Operation op)     {         if (!operations.containsKey(op.getSymbol()))             operations.put(op.getSymbol(), op);     }      public Operation getOperation(String symbol)     {         return this.operations.get(symbol);     }      public Set<String> getDefinedSymbols()     {         return this.operations.keySet();     } } 

Beside the enum singleton pattern nothing really fancy here.

A Rule now contains one or more expressions which on evaluation may trigger a certain action. The rule therefore needs to hold the previously parsed expressions and the action which should be triggered in success case.

import java.util.ArrayList; import java.util.List; import java.util.Map;  public class Rule {     private List<Expression> expressions;     private ActionDispatcher dispatcher;      public static class Builder     {         private List<Expression> expressions = new ArrayList<>();         private ActionDispatcher dispatcher = new NullActionDispatcher();          public Builder withExpression(Expression expr)         {             expressions.add(expr);             return this;         }          public Builder withDispatcher(ActionDispatcher dispatcher)         {             this.dispatcher = dispatcher;             return this;         }          public Rule build()         {             return new Rule(expressions, dispatcher);         }     }      private Rule(List<Expression> expressions, ActionDispatcher dispatcher)     {         this.expressions = expressions;         this.dispatcher = dispatcher;     }      public boolean eval(Map<String, ?> bindings)     {         boolean eval = false;         for (Expression expression : expressions)         {             eval = expression.interpret(bindings);             if (eval)                 dispatcher.fire();         }         return eval;     } } 

Here a building pattern is used just to be able to add multiple expression if desired for the same action. Furthermore, the Rule defines a NullActionDispatcher by default. If an expression is evaluated successfully, the dispatcher will trigger a fire() method, which will process the action which should be executed on successful validation. The null pattern is used here to avoid dealing with null values in case no action execution is required as only a true or false validation should be performed. The interface therefore is simple too:

public interface ActionDispatcher {     public void fire(); } 

As I do not really know what your INPATIENT or OUTPATIENT actions should be, the fire() method only triggers a System.out.println(...); method invocation:

public class InPatientDispatcher implements ActionDispatcher {     @Override     public void fire()     {         // send patient to in_patient         System.out.println("Send patient to IN");     } } 

Last but not least, a simple main method to test the behavior of the code:

import java.util.HashMap; import java.util.Map;  public class Main  {     public static void main( String[] args )     {         // create a singleton container for operations         Operations operations = Operations.INSTANCE;          // register new operations with the previously created container         operations.registerOperation(new And());         operations.registerOperation(new Equals());         operations.registerOperation(new Not());          // defines the triggers when a rule should fire         Expression ex3 = ExpressionParser.fromString("PATIENT_TYPE = 'A' AND NOT ADMISSION_TYPE = 'O'");         Expression ex1 = ExpressionParser.fromString("PATIENT_TYPE = 'A' AND ADMISSION_TYPE = 'O'");         Expression ex2 = ExpressionParser.fromString("PATIENT_TYPE = 'B'");          // define the possible actions for rules that fire         ActionDispatcher inPatient = new InPatientDispatcher();         ActionDispatcher outPatient = new OutPatientDispatcher();          // create the rules and link them to the accoridng expression and action         Rule rule1 = new Rule.Builder()                             .withExpression(ex1)                             .withDispatcher(outPatient)                             .build();          Rule rule2 = new Rule.Builder()                             .withExpression(ex2)                             .withExpression(ex3)                             .withDispatcher(inPatient)                             .build();          // add all rules to a single container         Rules rules = new Rules();         rules.addRule(rule1);         rules.addRule(rule2);          // for test purpose define a variable binding ...         Map<String, String> bindings = new HashMap<>();         bindings.put("PATIENT_TYPE", "'A'");         bindings.put("ADMISSION_TYPE", "'O'");         // ... and evaluate the defined rules with the specified bindings         boolean triggered = rules.eval(bindings);         System.out.println("Action triggered: "+triggered);     } } 

Rules here is just a simple container class for rules and propagates the eval(bindings); invocation to each defined rule.

I do not include other operations as the post here is already way to long, but it should not be too hard to implement them on your own if you desire so. I furthermore did not include my package structure as you probably will use your own one. Furhtermore, I didn't include any exception handling, I leave that to everyone who is going to copy & paste the code :)

One might argue that the parsing should obviously happen in the parser instead of the concrete classes. I'm aware of that, but on the other hand on adding new operations you have to modify the parser as well as the new operation instead of only having to touch one single class.

Instead of using a rule based system a petri net or even a BPMN in combination with the open source Activiti Engine would be possible to achieve this task. Here the operations are already defined within the language, you only need to define the concrete statements as tasks which can be executed automatically - and depending on the outcome of a task (i.e. the single statement) it will proceed its way through the "graph". The modeling therefore is usually done in a graphical editor or frontend to avoid dealing with the XML nature of the BPMN language.