Case Study: Complex Bi-Directional Validation

by Michael

The problem

Not too long ago, we built a web user interface component that contained a form with three sections. The user was able to select several options from each section. The choices made in section A affected the availability of the choices in sections B and C. Similarly, selecting an option from section B affected the availability of options in sections A and C. The same applied to choices made in section C.

A bit like this

For this example, when the user selects chocolate – apples, melons and caramel are no longer available as choices. Conversely, selecting melons or caramel or apples will render chocolate as disabled. In other words, the choices in each of the sections have a bi-directional effect on the availability of choices in other sections.

Expressing the rules

Since we are likely to add new options, and writing if-else statements is a very tiring process, we express the rules in a human readable form and save them to a file which we can later use as the input to our validator. The rules are expressed as follows:

(flavours):(fruits):(toppings)

Example:

v:a*b:a*s*c // this means that you can combine vanilla with apples 
            // and bananas with almond, sprinkles or caramel toppings

This allows us to easily communicate about which rules are missing or need to be removed. It’s easy to see that we will end up with many rules in order to express the constraints for the different options.

Parsing the rules

Now that we have all the rules stored in a file, we can begin to parse the file into an in-memory data-structure. Maybe something that isn’t quite obvious to begin with is that we can save these rules into a single integer by switching bits on or off corresponding to valid combinations – as long as the sum of the number of choices in the sections doesn’t exceed 32 (or 64 if you’re into longs, larger requirements should use BitSet). For this example, we would reserve 3 bits for each section, which means we have a requirement of 9 bits leaving the other 23 bits free given that we will work with 32bit integers.

32bit integer

[0 ... {flavours} {fruits} {toppings}]

Example:

[0 ... 001 011 111] // which is the rule shown above [0 ... v a*b a*s*c]

In essence, we have created a bit mask for each rule which also corresponds to a unique integer.

Validation

Saving these integers into a set V allows us to check whether a combination of selected options is valid or not in constant time. Furthermore, given the current state of selected options as integer c, we can find all possible valid future states by performing bitwise or operations to come up with a superset of valid future selections as integer f. We can then use f to enable/disable checkboxes in the UI. An added bonus is that, in the case of an invalid state, we can suggest the nearest valid state, n, to the user by performing xor operations on c and integers in and using the integer result with lowest bit cardinality:

n =  min_cardinality( xor( v, c )) for all v in V.

In real life

The initial solution didn’t use bits or bitwise operations, instead we used Java collection types such as HashSet and ArrayList. The performance wasn’t bad, but it certainly wasn’t great either. Moving to this solution decreased the CPU time by a factor of 20. Also, the real solution doesn’t deal with just 3 sections of 3 choices, instead there are 3 sections with a variation of different choices requiring 24 bits in total leaving 8 bits free for choices to be implemented in the future.

What I like about this solution is that it is simple and it has a lot of benefits that I didn’t think of to begin with, such as finding the nearest valid state. This solution was somewhat inspired by reading Programming Pearls by Jon Bentley. Even though the book isn’t the new hotness, it has aged with grace and I found it a truly inspiring read.

Advertisements