In Progress
Unit 1, Lesson 1
In Progress

Rule Table

Video transcript & code

Let's say we're working for a magazine publisher which has begun publishing their issues electronically as well as in print. In order to make the transition without completely disrupting the entire publishing process, they've decided to start by publishing pixel-perfect copies of the print magazine pages in digital form.

Of course, this publisher wants to reach readers using as many digital devices as possible. Unfortunately, one problem they've run into is that different devices have different display capabilities. And as a result, the digital publishing department has begin producing different versions of each image, each version optimized for a different kind of device.

In order to serve the right image to the right device, the server-side software has to use some heuristics to guess a device's type and capabilities, based on metadata it submits as part of the request for an image. Right now, the logic looks something like this.

We have a deeply-nested if statement that looks at various properties of the user agent. For instance, it checks the reported operating system string against regular expressions. It also looks at screen resolution.

But it doesn't stop there. Because one of the things we've discovered as we've evolved this software is that there are some devices which report their operating system as "Android". But rather than being phones or tablets, they are actually e-ink book readers. Since these devices only support a limited grayscale palette, we want to serve specially optimized images to them. But that means we have to use some extra user agent info to differentiate them from Android tablets.

As a result, we have even deeper nesting of our conditionals, in order to match the subset of high-resolution, android-based devices which are actually e-ink readers.

def device_type(device)
  if device.os =~ /ios/i
    if device.resolution.width > 1024 &&
       device.resolution.height > 768
      :ios_hi
    else
      :ios_lo
    end
  elsif device.os =~ /android/i
    if device.resolution.width >= 1280 &&
       device.resolution.height > 800
      if device.user_agent_misc =~ /inky/i
        :ereader
      else
        :android_hi
      end
    else
      :android_lo
    end
  else
    :unknown
  end
end

(By the way, don't think too hard about the specific values in this example. It has been deliberately over-simplified for the sake of demonstration.)

Just to see how this works, let's take an example device and feed it into this method.

require "./conditionals"

device = OpenStruct.new(
  os: "Android",
  resolution: OpenStruct.new(
    width: 1430,
    height: 1080),
  user_agent_misc: "(Inky)")

device_type(device)             # => :hd_ereader

This code as it stands now is already starting to be a real hassle. It's difficult to reason about, and difficult to come up with tests that fully exercise it.

But here's the thing: this isn't even the real code. This is the code I'm showing you for the sake of example. As I mentioned before, it has been massively oversimplified. Any realistic code for this scenario would have to handle hundreds of device types and probably have to interrogate even more user agent properties and other hints.

What we have here is a state space explosion. Our rules are matching against multiple attributes. The number of potential combinations is huge. And the complexity of our conditional code mirrors the complexity of the problem.

Let's take a look at an alternative way we might go about solving this problem. We'll look at the high-level solution first, and then we'll talk about how it is implemented.

Instead of a nested if/else statement, we have a RuleTable object. For each potential match target, we add a new rule to the table. We can see right away that this puts the matching goals front and center, rather than hiding them down deep within the if statement.

Each rule consists of a goal or target, and a set of zero or more matchers. Each matcher corresponds to a particular attribute of the client device, such as operating system or screen width. For greater flexibility, the matchers usually accept a pattern of some kind, like a regular expression or a numeric range.

require "./matchers"
require "./rule_table"

TABLE = RuleTable.new
TABLE.add_rule_for :ios_hi, MatchOs.new(/ios/i),
                            MatchWidth.new(1024..2732),
                            MatchHeight.new(768..2048)
TABLE.add_rule_for :ios_lo, MatchOs.new(/ios/i),
                            MatchWidth.new(0...1024),
                            MatchHeight.new(0...768)
TABLE.add_rule_for :android_hi, MatchOs.new(/android/i),
                                MatchWidth.new(1280..2560),
                                MatchHeight.new(800..1800)
TABLE.add_rule_for :android_lo, MatchOs.new(/android/i),
                                MatchWidth.new(0...1280),
                                MatchHeight.new(0...800)
TABLE.add_rule_for :ereader, MatchOs.new(/android/i),
                   MatchMisc.new(/inky/i)
TABLE.add_rule_for :unknown

The matcher classes themselves are defined very simply. Each one implements a #matches? method, which tests the matcher against the appropriate device attribute.

All of these classes have a similar shape and flow. However, it's worth noting that this is coincidental duplication. We could just as easily define more complex matchers which took more than one argument, or examine more than one device attribute.

MatchOs = Struct.new(:pattern) do
  def matches?(device)
    pattern === device.os
  end
end

MatchWidth = Struct.new(:pattern) do
  def matches?(device)
    pattern === device.resolution.width
  end
end

MatchHeight = Struct.new(:pattern) do
  def matches?(device)
    pattern === device.resolution.height
  end
end

MatchMisc = Struct.new(:pattern) do
  def matches?(device)
    pattern === device.user_agent_misc
  end
end

Now let's look at the definition of the RuleTable class. This class manages an internal list of rules. The #add_rule_for method adds a new pair to this list, consisting of a target and an array of matchers.

There is also a #match method. It takes an object to match against. It then looks to see if it can find a rule whose matchers all match the target object. If it finds one, it returns the associated target name.

class RuleTable
  def initialize
    @rules = []
  end

  def add_rule_for(target, *matchers)
    @rules << [target, matchers]
  end

  def match(object)
    @rules.find{ |(target, matchers)|
      matchers.all?{ |m| m.matches?(object) }
    }.first
  end
end

Let's give this a whirl. We'll use the same device attributes we tried before, and ask the table to find a #match for the device.

The result is not the same as what we got before. What went wrong?

require "./rules"

device = OpenStruct.new(
  os: "Android",
  resolution: OpenStruct.new(
    width: 1430,
    height: 1080),
  user_agent_misc: "(Inky)")

TABLE.match(device)
# => :android_hi

As it turns out, our table of rules is highly sensitive to ordering. The first rule to match will always "win".

Fortunately, this also means that it is very simple to fix errors where the wrong rule takes precedence. All we have to do is move the rule that should have matched above the rule that did match.

require "./matchers"
require "./rule_table"

TABLE = RuleTable.new
TABLE.add_rule_for :ios_hi, MatchOs.new(/ios/i),
                            MatchWidth.new(1024..2732),
                            MatchHeight.new(768..2048)
TABLE.add_rule_for :ios_lo, MatchOs.new(/ios/i),
                            MatchWidth.new(0...1024),
                            MatchHeight.new(0...768)
TABLE.add_rule_for :ereader, MatchOs.new(/android/i),
                             MatchMisc.new(/inky/i)
TABLE.add_rule_for :android_hi, MatchOs.new(/android/i),
                                MatchWidth.new(1280..2560),
                                MatchHeight.new(800..1800)
TABLE.add_rule_for :android_lo, MatchOs.new(/android/i),
                                MatchWidth.new(0...1280),
                                MatchHeight.new(0...800)
TABLE.add_rule_for :unknown

Once we make this change, we get the result we expected.

require "./rules2"

device = OpenStruct.new(
  os: "Android",
  resolution: OpenStruct.new(
    width: 1430,
    height: 1080),
  user_agent_misc: "(Inky)")

TABLE.match(device)
# => :ereader

Our table of rules is also able to tell us when a device isn't recognized. Let's try out some device attributes we don't have a rule for.

require "./rules"

device = OpenStruct.new(
  os: "Windows 10",
  resolution: OpenStruct.new(
    width: 3000,
    height: 200),
  user_agent_misc: "")

TABLE.match(device)
# => :unknown

We get back :unknown. This is the last rule in the list, and without any matchers, it functions as a catch-all.

What we've done with this new solution is to flatten the state space of the problem. Instead of branching, and branching, and branching again, we can see all the criteria for a given target in one place.

This doesn't magically solve all of our problems with matching against numerous different attributes. We still have to be careful of our precedence. And it's still easy to accidentally leave "holes" in our rules that allow targets to be unexpectedly dropped down to the "unknown" category.

But this solution makes the logic easier to follow and reason about. Every application of device detection is simply a matter of checking one rule, then the next, then the next, until a match is found. And it's now very easy to add a new rule without thinking through the entire structure of the conditional tree.

So that's all I wanted to show you today. Before I go, I want to extend a special thanks to Lennart Fridén. Lennart visited me here in Knoxville as part of his programming journeyman tour, and this episode was written with his inspiration and assistance. In addition, Lennart would like to thank Mike Burns, from whom he learnt this approach.

That's all for today. Happy hacking!

Responses