patrun

A fast pattern matcher on JavaScript object properties. Builds a decision tree so you can pick out the most-specific match for a given subject without writing chains of if statements. Used by the Seneca framework to dispatch actions.

A Go port is also available — see go/README.md.

From the Irish patrún: pattern. Pronounced pah-troon.

Tutorial: your first patrun

Install:

npm install patrun

Register a few patterns, then look one up:

const patrun = require('patrun')

const pm = patrun()
  .add({ a: 1 },         'A')
  .add({ a: 1, b: 1 },   'B')
  .add({ a: 1, b: 2 },   'C')

pm.find({ a: 1 })           // → 'A'
pm.find({ a: 2 })           // → null  (no match)
pm.find({ a: 1, b: 1 })     // → 'B'   (more specific wins)
pm.find({ a: 1, b: 2 })     // → 'C'
pm.find({ a: 1, z: 9 })     // → 'A'   (unknown keys ignored)

The matcher stores patterns in a trie keyed by sorted property names, so find makes the minimum number of comparisons needed to pick out the most specific match. It's query-by-example for property sets.

You're matching a subset, so your input can contain any number of extra properties — they're ignored.

How-to guides

Pick the most specific match (the default)

The two rules that govern every match:

1. More specific matches beat less specific ones — more matched key/value pairs always win.
2. Property names are checked in alphabetical order, so insertion order doesn't matter.

const pm = patrun()
  .add({ a: 0 },          'A')
  .add({ b: 1 },          'B')
  .add({ c: 2 },          'C')
  .add({ a: 0, b: 1 },    'AB')

pm.find({ a: 0 })            // → 'A'
pm.find({ a: 0, b: 1 })      // → 'AB'  (more specific than {a:0})
pm.find({ a: 0, c: 2 })      // → 'A'   (a comes before c)
pm.find({ b: 1, c: 2 })      // → 'B'   (b comes before c)

Require all keys to match

Pass true as the second argument to find for exact matching — every key in the registered pattern must be present in the subject:

pm.find({ a: 0, b: 1 }, true)  // → 'AB'
pm.find({ a: 0, b: 9 }, true)  // → null  (b doesn't match)

Collect every match along the path

Pass true as the third argument to find to get all data matched on the way down, widest first:

const pm = patrun()
  .add({},                 'ROOT')
  .add({ a: 1 },           'A')
  .add({ a: 1, b: 1 },     'AB')

pm.find({ a: 1, b: 1 }, false, true)
// → ['ROOT', 'A', 'AB']

Match values with glob expressions

Enable the gex matcher to use * and ? wildcards in pattern values (powered by gex):

const pm = patrun({ gex: true })
  .add({ a: 0 },              'A')
  .add({ a: '*' },            'AA')
  .add({ b: 1, c: 'x*y' },    'BC')

pm.find({ a: 0 })             // → 'A'   exact
pm.find({ a: 1 })             // → 'AA'  glob
pm.find({ b: 1, c: 'xhy' })   // → 'BC'  exact + glob

Exact matches beat glob matches; otherwise the more-specific rule applies as usual. See the multi-gex test for funky examples.

Build a decision tree of business rules

A larger example — sales-tax rules with country, state, city, and type overrides:

function I(val) { const rate = () => val; rate.val = val; return rate }

const salestax = patrun()
  .add({},                                           I(0.0))

  .add({ country: 'IE' },                            I(0.25))
  .add({ country: 'UK' },                            I(0.20))
  .add({ country: 'DE' },                            I(0.19))

  .add({ country: 'IE', type: 'reduced' },           I(0.135))
  .add({ country: 'IE', type: 'food' },              I(0.048))
  .add({ country: 'UK', type: 'food' },              I(0.0))
  .add({ country: 'DE', type: 'reduced' },           I(0.07))

  .add({ country: 'US' },                            I(0.0))
  .add({ country: 'US', state: 'AL' },               I(0.04))
  .add({ country: 'US', state: 'AL', city: 'Montgomery' }, I(0.10))
  .add({ country: 'US', state: 'NY' },               I(0.07))
  .add({ country: 'US', state: 'NY', type: 'reduced' }, function under110(net) {
    return net < 110 ? 0.0 : salestax.find({ country: 'US', state: 'NY' })
  })

salestax.find({ country: 'IE', type: 'food' })(99)            // 0.048
salestax.find({ country: 'US', state: 'AL', city: 'Montgomery' })(99) // 0.1

List every registered pattern

Pass no argument (or an empty object) to list to dump everything:

pm.list()

Pass a partial pattern to filter:

const pm = patrun()
  .add({ a: 1, b: 1 }, 'B1')
  .add({ a: 1, b: 2 }, 'B2')

pm.list({ a: 1 })
// [ { match: { a: '1', b: '1' }, data: 'B1' },
//   { match: { a: '1', b: '2' }, data: 'B2' } ]

pm.list({ a: 1, b: '*' })   // wildcards allowed
pm.list({ a: 1, c: 1 })     // []  (no matches)

Omitted keys are not equivalent to '*' — you must specify each key you want to filter on.

Remove a pattern

pm.remove({ a: 1, b: 1 })

Customise stored data

Pass a function as the constructor argument to wrap stored data. It runs at add time and may return a transform applied at find time (plus an optional remove handler).

Add a constant property to every stored pattern:

const alwaysAddFoo = patrun(function (pat) {
  pat.foo = true
})

alwaysAddFoo.add({ a: 1 }, 'bar')
alwaysAddFoo.find({ a: 1 })             // null
alwaysAddFoo.find({ a: 1, foo: true })  // 'bar'

Transform found data:

const upperify = patrun(function (pat) {
  return function (args, data) {
    return ('' + data).toUpperCase()
  }
})

upperify.add({ a: 1 }, 'bar')
upperify.find({ a: 1 })  // 'BAR'

Allow multiple matches per pattern:

const many = patrun(function (pat, data) {
  const items = this.find(pat, true) || []
  items.push(data)

  return {
    find:   (args, data) => items.length ? items : null,
    remove: (args, data) => { items.pop(); return items.length === 0 }
  }
})

many.add({ a: 1 }, 'A')
many.add({ a: 1 }, 'B')
many.find({ a: 1 })   // ['A', 'B']
many.remove({ a: 1 })
many.find({ a: 1 })   // ['A']

Inspect the decision tree

toString renders the tree as a flat list of patterns and their data, optionally with a custom formatter:

console.log(salestax.toString(f => f.name + ':' + f.val))
//  -> :0
// city=Montgomery, country=US, state=AL -> :0.1
// country=IE -> :0.25
// country=IE, type=food -> :0.048
// ...

toJSON(indent) returns the raw internal trie as JSON, useful for debugging.

Reference

patrun(custom?)

Create a new pattern matcher. custom may be:

• omitted — plain matcher.
• { gex: true } — enable * / ? glob matching on values.
• a function — runs at every add to rewrite the pattern and optionally return a find transform / remove handler. See Customise stored data.

.add(pattern, data)

Register pattern (object of strings — other types are coerced) and its associated data. Returns the matcher for chaining.

.find(subject, exact?, collect?)

Look up the most-specific match for subject. Unknown keys in subject are ignored.

• exact (boolean, default false) — require all pattern keys to be present and equal in subject.
• collect (boolean, default false) — return an array of every data value matched along the way (widest first) instead of a single value. With collect=true and exact=false, every sub-pattern of subject is searched. With exact=true, only sub-patterns in lexicographic order are considered.

Returns the data, or null if no pattern matched.

.findexact(subject)

Shorthand for .find(subject, true).

.list(partial?, exact?)

Return all registered patterns matching partial (a partial pattern; values may be globs). Omitted keys are not wildcards. With no argument, lists every registered pattern. Returns an array of { match, data, find }.

.remove(pattern)

Clear the data stored at pattern.

.toString(formatter?, tree?)

Render the decision tree.

• formatter(data) — optional custom formatter for stored values.
• tree (boolean, default false) — if true, print as an indented tree instead of a flat list.

patrun.inspect is an alias for toString.

.toJSON(indent?)

Return the internal trie as JSON.

Explanation: design notes

The two rules

patrun is built around two rules and nothing else:

1. More specific matches win. "More specific" means more matched key/value pairs, not insertion order.
2. Property names are compared in alphabetical order.

Rule 2 is what makes the trie layout independent of how callers build their patterns. add({a:1, b:2}) and add({b:2, a:1}) produce the exact same internal structure.

Why a trie?

A linear scan of N patterns is O(N) per lookup. The trie is O(K) in the number of distinct keys present in the most specific matched pattern. For workloads with many patterns sharing a common prefix — Seneca's plugin actions are the canonical example — this is a significant win.

Star paths

When a pattern omits a key that a sibling pattern includes, add builds a s ("star") branch that the lookup falls back to. This is what lets {a:1} still match {a:1, b:9} even though b is registered elsewhere — without it, more-specific matches would shadow wider matches incorrectly.

Strings everywhere

Keys and values are coerced to strings before storage. This keeps the matching logic simple and avoids surprises around == vs === / type coercion. If you need numeric-range matching, the Go port includes an Interval matcher (the JS port currently only ships gex).

Why not "just write if statements"?

A handful of cases is fine as if statements. But once your dispatch table has sub-cases and sub-sub-cases, the if ladder stops being readable and stops being maintainable — adding a new branch becomes a merge-conflict generator. patrun lets each branch be added (and removed, listed, inspected) independently.

License

Copyright (c) 2013-2025, Richard Rodger and other contributors. Licensed under MIT.