Remiges Products » Crux: BRE/WFE

*(For a conceptual overview and design of Crux, see [[cruxdesign|this page]] if you haven't already.)*

# Algorithms and data structures for the Crux BRE

{{>toc}}

This page documents the rules engine. It does not cover the flow engine.

A rules engine implementation must include the following:

* **RULE SCHEMA**. A notation to specify the list of valid terms in a rule. This list will be separate for each class of entities. For instance, for items in inventory, the list of attributes may be:

  * Price

  * Full name

  * Age in stock

  * Quantity in inventory

    For vendors, the list could include:

  * Amount outstanding

  * Total value of business done  in the last financial year

* **RULE NOTATION**. A notation to specify the pattern and actions of a rule.

* **THE MATCHING ENGINE**. Something which will take an entity with all its attributes, apply each rule to it, and follow the trail of rules to come up with a list of actions which will emerge.

So, if these three can be designed and then implemented, the core of a rules engine or a flow engine can be built.

## Representing the schema of patterns

If using JSON, the schema of all valid patterns may be represented in structures of this form:

``` json

"patternschema": {

    "class": "inventoryitems",

    "attr": [{

        "name": "cat",

        "valtype": "enum",

        "vals": [ "textbook", "notebook", "stationery", "refbooks" ]

    },{

        "name": "mrp",

        "valtype": "float"

    },{

        "name": "fullname",

        "valtype": "str",

    },{

        "name": "ageinstock",

        "valtype": "int"

    },{

        "name": "inventoryqty",

        "valtype": "int"

    }]

}

```

In this example, the object `patternschema` is the schema for one class of entities. This schema says that for rules which work on entities of class `inventoryitems`, there are five attributes available which may be used to make patterns. Each attribute has a type. Boolean, enum types, integers, floating point numbers, timestamps (`ts`) and strings are supported. The example above does not have any attribute of type `ts` or  `bool`.

So, the full schema of the rules engine will be an array of `patternschema` blocks. Initial examples have discussed inventory items and vendors. The `patternschema` block above is for inventory items. If the schema of patterns for vendors needed to be specified, there would be a second `patternschema` with `“class”: “vendors”`

While the fields in the example above are adequate from a purely functional point of view, it may be necessary to have some additional metadata to allow the building of a good UI which will allow users to manage these schema objects. So, an augmented data structure may look like this:

``` json

"patternschema": {

    "class": "inventoryitems",

    "attr": [{

        "name": "cat",

        "shortdesc": "Category of item",

        "longdesc": "Each item can belong to one of the following categories: textbooks, notebooks, stationery, or reference books.",

        "valtype": "enum",

        "vals": [ "textbook", "notebook", "stationery", "refbooks" ],

        "enumdesc": [ "Text books", "Notebooks", "Stationery and miscellaneous items", "Reference books, library books" ]

    },{

        "name": "mrp",

        "shortdesc": "Maximum retail price",

        "longdesc": "The maximum retail price of the item as declared by the manufacturer."

        "valtype": "float",

        "valmax": 20000,

        "valmin": 0

    },{

        "name": "fullname",

        "shortdesc": "Full name of item",

        "longdesc": "The full human-readable name of the item. Not unique, therefore sometimes confusing.",         

        "valtype": "str",

        "lenmax": 40,

        "lenmin": 5

    },{

        "name": "ageinstock",

        "shortdesc": "Age in stock, in days",

        "longdescr": "The age in days that the oldest sample of this item has been lying in stock",

        "valtype": "int",

        "valmax": 1000,

        "valmin": 1

    },{

        "name": "inventoryqty",

        "shortdesc": "Number of items in inventory",

        "longdescr": "How many of these items are currently present in the inventory",

        "valtype": "int",

        "valmax": 10000,

        "valmin": 0

    }]

}

```

Here, the `shortdesc` and `longdesc` are useful attributes of each attribute, for displaying labels and help text in any UI which is displayed to the human user who manages the rules for entities of this class. The `valmax`, `valmin`, `lenmax`, `lenmin`, allow the system to enforce some sanity checks on the patterns defined in any rules for this entity.

## Representing the schema of actions

The schema of the action section of rules is simpler than patterns. Each rule's action section will contain a set of zero or more words, each denoting a task, and zero or more property assignments. There is no need for any type specification, etc.

* An example of a task word: `invitefordiwali`

* An example of a property assignment: `discount=7`

So, the schema of the actions will just specify the valid task names and the property names for assignments.

``` json

"actionschema": {

    "class": "inventoryitems",

    "tasks": [ "invitefordiwali", "allowretailsale", "assigntotrash" ],

    "properties": [ "discount", "shipby" ],

}

```

The schema of actions above indicates that there are three tasks, any or all of which may be present in any rule for this class of entities. There are two properties which may be assigned values by any rule.

Putting the `patternschema` and `actionschema` blocks together, a better representation for the full schema for a class of entities will be:

``` json

"ruleschema": {

    "class": "inventoryitems",

    "patternschema": {

        "attr": [{

            "name": "cat",

            "valtype": "enum",

            "vals": [ "textbook", "notebook", "stationery", "refbooks" ]

        },{

            "name": "mrp",

            "valtype": "float"

        },{

            "name": "fullname",

            "valtype": "str",

        },{

            "name": "ageinstock",

            "valtype": "int"

        },{

            "name": "inventoryqty",

            "valtype": "int"

        }]

    }

    "actionschema": {

        "tasks": [ "invitefordiwali", "allowretailsale", "assigntotrash" ],

        "properties": [ "discount", "shipby" ],

    }

}

```

There will need to be one such `ruleschema` block for each class.

## Representing a pattern

Below is an example of a pattern of a rule, which conforms to the schema example given above.

``` json

"rulepattern": [{

        "attrname": "cat",

        "op": "eq",

        "attrval": "textbook"

    },{

        "attrname": "mrp",

        "op": "ge",

        "attrval": 2000

    },{

        "attrname": "ageinstock",

        "op": "ge",

        "attrval": 90

    },{

        "attrname": "invitefordiwali",

        "op": "eq",

        "attrval": true

    }

}]

```

If a rule has this pattern, it will match any entity which falls in the class `inventoryitems` which

* is of type textbook

* has MRP (max retail price) greater than INR 2000

* has been in stock longer than 89 days 

* one of the earlier rules matched against this entity has added the task `invitefordiwali` to the action set of this entity

It is important to note that a pattern does not need to have just the attributes listed in `patternschema`. It may also include tasks listed in the `ruleschema`. Each such task becomes an implicit attribute of type `bool` for this class.

For attributes which are of type `int`, `float`, `str` and `ts`, the following comparison operators are available:

* Greater than or equal to: `ge`

* Greater than: `gt`

* Less than or equal to: `le`

* Less than: `lt`

* Equal to: `eq`

* Not equal to: `ne`

Collation sequences for strings are system dependent, and will need to be standardised so that they work reliably across programming languages and Unicode strings in any language. That's an implementation issue.

For `enum` and `bool` types, only `eq` and `ne` are available.

## Representing an action

A rule has a set of one or more actions. The following are all examples of the action section of rules:

* `invitefordiwali`

* `shipby=fedex`

* `discount=7`

* `shipwithoutpo`

* `CALL=intlbiz`

The words that identify actions, *e.g.* `invitefordiwali`, will automatically be converted to lower-case and stored in the system. Reserved instruction names like `THENCALL`, `ELSECALL`, `RETURN`, `EXIT`, will always be in uppercase. Property assignments can include multi-word strings, *e.g.*

* `reprimand=This cannot go on any longer`

The action portion of a rule can have zero or one occurrence of a `THENCALL`, `ELSECALL`, a `RETURN`, and an `EXIT`. If it contains both a `RETURN` and an `EXIT`, then the `RETURN` will be ignored.

The action portion of a rule will have the following structure, shown here as an example:

``` json

"ruleactions": {

    "tasks": [ "christmassale", "vipsupport" ],

    "properties": [ {"shipby", "fedex" } ],

    "thencall": "internationalrules",

    "elsecall": "domesticrules",

    "return": true,

    "exit": false

}

```

This example shows all five fields of `ruleactions`, but in reality, some of the fields will typically be missing from most of the rules.

## An entire rule

This is what an entire rule looks like:

``` json

"rule": {

    "class": "inventoryitems",

    "rulepattern": [{

        "attrname": "cat",

        "op": "eq",

        "attrval": "textbook"

    },{

        "attrname": "mrp",

        "op": "ge",

        "attrval": 5000

    }],

    "ruleactions": {

        "tasks": [ "christmassale" ],

        "properties": [ {"shipby", "fedex" } ]

    }

}

```

This structure represents one rule. The rule applies to entities of class `inventoryitems`. It has a pattern section which tries to match two attributes and an action section which throws up one task and one property assignment.

A rule has a version number, which is incremented whenever the rule is updated. This number is for internal logging and rule engine debugging.

An array of such structures is a set of rules, and will be traversed in the order in which the rules appear in the array. Named rulesets will be represented thus:

``` json

"ruleset": {

    "ver": 5,

    "class": "inventoryitems",

    "setname": "overseaspo",

    "rules": [{

        "rulepattern": {

            :

            :

        },

        "ruleactions": {

            :

            :

        }

    }, {

        "rulepattern": {

            :

            :

        },

        "ruleactions": {

            :

            :

        }

    }]

}

```

The example above shows a ruleset named `overseaspo` for class `inventoryitems` which has two rules. This ruleset may be invoked from any other rule with the action `THENCALL=overseaspo` (or `ELSECALL=overseaspo`).

## The schema manager

The schema for each class of entities may be written by hand using a text editor. JSON or YAML files are easy to write. If the schema of one class has less than a dozen attributes, it may be short enough to edit or audit by hand. However, a tool to manage and maintain the schema eliminates typos and enforces various types of consistency, and a second-level implementation of a schema manager may also enforce authorisation policies.

A schema manager will have the following features:

* It will allow the user to create new instances of `ruleschema`

* It will sharply restrict editing of, and prevent deletion of any `patternschema` block or `actionschema` block if there are rules defined in the rules engine for this class of entities. In other words, schema are editable only as long as there are no rules for the class. The only kind of editing it will permit for “live” schema are

  * the addition of additional attributes in a `patternschema` or

  * additional tasks or properties in an `actionschema`.

* It will ensure that there is no scope for typos when defining the schema.

## The rule manager

The rule manager will allow a user to manage rules. Core functionality:

* It will provide a user interface to let the user edit rules.

* It will check each rule against the schema for the class, and will not give the user the opportunity to define any rule inconsistent with the schema.

* It will allow the user to move a rule up or down in the sequence, since ordering is important.

* If a rule is being defined with a `THENCALL/ELSECALL` action, then the rule manager will ensure that a ruleset with that target name exists.

* Most important: it will provide a testing facility by which sample entities may be submitted to the rule engine for testing, and the rule manager will display a full trace showing which rules were attempted to match, which rules actually matched, and how the result set of tasks and properties grew with each step. This feature will be provided without having to save the rule changes.

* Finally, when the editing session is complete and all rulesets need to be saved, it will perform a detailed cross-validation of all rules across each other to ensure consistency. If there is any inconsistency, it will give readable explanations of the problems and not permit saving of the updates.

## The matching engine

The matching engine has a one-line job. It will take a full set of attributes of one entity, apply all the rules which apply to its class, and return with the list of tasks and properties from all the matching rules.

The operation of the engine, in a highly simplified notation, is:

```

for each rule in the ruleset do

    match the pattern of the rule with the entity

    if the pattern matches, then

        collect the tasks and properties from the rule into the actionset

    endif

endfor

```

### Matching one rule's pattern

The algorithm for the matching of one rule's pattern is shown below. Here, it is assumed that the object being matched is in `entity` and pattern of the rule being matched is in `rulepattern`. It is assumed that the matching engine may have proceeded some distance in its matching process, and may have collected zero or more tasks or properties in its `actionset`.

```

func matchPattern()

    input parameters: entity, rulepattern, actionset

    returns patternmatch: boolean

#

# In this loop we iterate through terms from our pattern array

# one by one

#

for term in rulepattern do

    #

    # We get into a loop, stepping through the attributes of this

    # entity to pull out the value of the attribute

    # we will now be matching against the term we have selected

    # for this iteration of the outer loop, i.e. patternterm

    #

    entityattrval = null

    for entityattr in entity.attrs do

        if entityattr.name == patternterm.attrname then

            entityattrval = entityattr.val

        endif

    endfor

    if entityattrval == null then

        #

        # We reach here if none of the attributes in the entity

        # has a name matching the attribute in the term in the pattern array.

        # We still need to check if this pattern term matches a task

        # with which this entity has been tagged (a task that has already

        # been collected from matching a previous rule).

        #

        # So we will now cycle through the tasks in the actionset

        # to see if any of those matches this patternterm.

        #

        for task in actionset.tasks do

            if task == patternterm.attrname then

                #

                # Bingo! We have found a task which matches

                # the name of the attribute in the pattern term.

                #

                entityattrval = "true"

            endif

        endfor

    endif

    if entityattrval == null then

        #

        # If we reach here, it means that the task that is represented by patternterm.attrname is

        # not present in the actionset.

        # 

        entityattrval = "false"

    endif

    case patternterm.op in

    "eq":

        if entityattrval != patternterm.attrval then

            return false

        endif

    "ne":

        if entityattrval == patternterm.attrval then

            return false

        endif

    endcase

    if patternterm.type in [ "int", "float", "ts", "str" ] then

        case patternterm.op in

        "le":

            if entityattrval > patternterm.attrval then

                return false

            endif

        "lt":

            if entityattrval >= patternterm.attrval then

                return false

            endif

        "ge":

            if entityattrval < patternterm.attrval then

                return false

            endif

        "gt":

            if entityattrval <= patternterm.attrval then

                return false

            endif

        default:

            log error with priority = CRITICAL: "system inconsistency with BRE rule terms"

        endcase

    endif

endfor

return true

```

Note how the algorithm cycles through the `actionset` of the entity, trying to see of any of the tasks in `actionset` matches the `patternterm`. This aspect of the matching algorithm has been discussed in [[Cruxdesign#Tags|the explanation of the idea of tasks as tags]].

### Collecting the actions from one rule

If the pattern for one rule matches the entity being processed, then the tasks of that rule will need to be added to the action set for that entity. Here we assume that the result of the action-collection function will return an object of the following structure. This object will be passed as input to the action-collecting function, and a (possibly extended) object will be returned, after merging the input object with the tasks and properties from the rule just matched. The object structure will be:

``` json

"actionset": {

    "tasks": [ "dodiscount", "yearendsale" ],

    "properties": [ {"shipby", "fedex"} ],

}

```

These two fields will always be present in the object. The `tasks` field will carry an array of strings, which will be a union set of all the tasks collected from rules matched so far. The `properties` field will carry an array of properties, which are objects containing two strings: property name and property value.

Performing a set union of tasks is straightforward. Performing a set union of property assignments requires choosing one property value when a particular property already exists in the `actionset` and the current ruleaction also assigns a value to that property. In that case, the old value of the property will be overwritten by the new value.

```

function collectActions()

input parameters: actionset, ruleactions

    returns actionset

actionset.tasks = actionset.tasks UNION ruleactions.tasks

actionset.properties = actionset.properties UNION ruleactions.properties

return actionset

```

### Representing one entity

The matching engine matches all the rules of a ruleset against one instance of a class, like one instance of `vendor` or `inventoryitem`. How do we represent this object instance, when the type and the fields are all dynamically determined at runtime and vary from invocation to invocation? Here is one example:

``` json

"inputentity": {

    "class": "inventoryitems",

    "attribs": [{

        "name": "cat",

        "val": "refbook"

    },{

        "name": "mrp",

        "val": "1350"

    },{

        "name": "fullname",

        "val": "Advanced Level Physics, 2/ed"

    },{

        "name": "ageinstock",

        "val": "20"

    },{

        "name": "inventoryqty",

        "val": "540"

    }]

}

```

As this example highlights, all the values supplied are of type string, so that they may be converted from strings to their respective types later. This allows the data structure for specifying an object instance to be strongly typed and still allow attributes of all types to be captured. One more point illustrated is that **all attributes in the `patternschema` of the class must be present** in each object instance of that class.

This is the way the entity will be submitted to the matching engine for processing.

### `doMatch()`: the matching function

This engine will go through rules one after another, and for each rule, it will call `matchPattern()`. If `matchPattern()` returns `true`, it will call `collectActions()` to update the `actionset`

This engine will be implemented by the `doMatch()` function, which will occasionally call itself recursively. It will be called with three parameters:

* an `inputentity`, which will be matched against the ruleset

* a `ruleset` which will be traversed by the engine

* an `actionset`, which collects the results of the action matching

The pseudocode has been written with the assumption that parameters are all pass-by-value.

So, the `doMatch()` engine will work in the following way:

```

function doMatch()

input parameters: entity, ruleset, actionset

    returns actionset: ActionSet, willexit: boolean 

for each rule in ruleset do

    if matchPattern(entity, rule.rulepattern, actionset) == true then

        actionset = collectActions(actionset, rule.ruleactions)

        willexit = false

        #

        # Check if there's a THENCALL instruction

        #

        if rule.ruleactions.thencall is not null then

            settocall = rule.ruleactions.thencall

            if settocall.class != entity.class then

                log error with priority = CRITICAL: 

                    "system inconsistency with BRE rule terms, attempting to call ", settocall, " from ", ruleset.setname, "!"

            endif

            actionset, willexit = doMatch(entity, settocall, actionset)

        endif

        #

        # If the called ruleset has set EXIT to true, or if the current ruleactions has an EXIT,

        # then we need to exit, and our caller too needs to exit, ad infinitum

        #

        if willexit OR rule.ruleactions.willexit then

            return actionset, true

        endif

        #

        # If there is no EXIT in ruleactions, check if there is a RETURN instruction

        #

        if rule.ruleactions.willreturn then

            return actionset, false

        endif

    endif

    if rule.ruleactions.elsecall is not null

        settocall = rule.ruleactions.elsecall

	if settocall.class != entity.class then

            log error with priority = CRITICAL: 

                "system inconsistency with BRE rule terms, attempting to call ", settocall, " from ", ruleset.setname, "!"

	actionset, willexit := doMatch(entity, settocall, actionset)

	if willexit

	    return actionSet, true

	endif

    endif

    #

    # We come here because we've done one rule and we've neither been thrown

    # out by an EXIT nor a RETURN clause. So we now loop to the next rule in

    # our ruleset.

    #

endfor

return actionset, false

```

This matching engine will be able to traverse all rulesets, make "subroutine calls" from one ruleset to another, and finally come up with a consolidated `actionset`.

The outermost calling code which calls the outermost layer of `doMatch()` for a given entity will initialise an empty `actionset` and pass it in. After all the ruleset traversals, `doMatch()` will return with a loaded `actionset`, which will then be returned to the client of the BRE.

## Operations supported by the BRE

The BRE must support the following set of operations:

* Schema management:

  * `schemaAdd()`: add a new rule schema, for a new class

  * `schemaUpdate()`: update an existing schema

  * `schemaDelete()`: delete an existing schema

  * `schemaList()`: list all the schema for all classes

  * `schemaGet()`: get the full schema for one class, given the class name

* Ruleset management:

  * `rulesetAdd()`: add a new ruleset for a class, with one or more rules

  * `rulesetUpdate()`: update an existing ruleset

  * `rulesetDelete()`: delete a ruleset

  * `rulesetList()`: list all rulesets for a class

  * `rulesetGet()`: get the full ruleset, given the class name and the ruleset name

* Query the BRE and get the list of actions and attributes for an entity:

  * `getBR()`: submit an entity and pull out the final set of actions and attributes. This call will fail unless the `inputentity` carries all the attributes listed in the schema of its class.

  * `getAttrSet()`: take a class name, pull out from the `patternschema` all the attributes listed against that class, with full details. This is useful to let the caller know what attributes are to be specified when calling `doMatch()`.

* Rule engine management:

  * `setConfig()`: set one or more global configuration parameters of the engine

  * `getConfig()`: get values of one or more global config parameters of the engine

  * `setAuth()`: set authorization rules to allow access to the engine

  * `getAuth()`: get authorization rules which control access to the engine

  * `shutdown()`: shut down the engine

  * `sysReset()`: the equivalent of a factory reset. All configuration reverts to that which is present in a fresh install, all currently active processing threads are aborted and all schema, rulesets and other information is lost.

The actual API specs will be on [[cruxapi|a separate page]], but the list of operations have been listed here in the typical syntax of API calls just to indicate the operations which the BRE will support. Only when we look at a complete list of operations do we see the entire scope of this system.