NMatch lets you combine multiple pattern matchers.
Say you have a set of URL patterns, like "/foo"
and "/foo/{id}"
,
and a set of HTTP method patterns, like "GET"
, "POST"
, and "ANY"
,
and a set of user role patterns, like "{ user: "alice" }
and
{ group: "admins" }
. You can bundle these into NMatch and then ask it
"what's the handler for this user doing this method to this URL?"
You do this in three steps.
First you define what your rules will look like by choosing a set of matchers:
const NMatch = const router =
Then you set rules that map patterns to results. Each rule takes one pattern per matcher, plus the result that the rule should return when it matches:
routerrouterrouterrouter
Now you can match terms against the ruleset, one term per matcher. NMatch will return the best result that matches all the terms: the first term against the first matcher, the second term against the second matcher, and so on.
const alice = 'username': 'alice' 'groups': 'public' 'admins' const anon = 'groups': 'public' taptaptap
API
The NMatch constructor takes for argument an array of functions, each of
which should return a new instance of a matcher. They will be called as
needed when more patterns are added. Their order is the same as that of the
set
and match
methods' arguments.
const Id = // "matches" using `===` const bookNotes = // Author // Title
The set
method takes as many arguments as you've defined matchers, plus
one for the value being set. set
will associate that value to the given
patterns. What counts as a pattern depends on the kind of matcher you use.
bookNotesbookNotes
The match
method takes as many arguments as you've defined matchers.
It will pass the first argument to the first matcher, the second argument to
the second matcher, and so on. It returns the best match, or null
if no
matches are found.
taptap // no match
More details
The NMatch constructor does some basic validation on its arguments
taptaptaptaptaptap
set
and match
will check that you pass in the right number of arguments,
but they can't tell whether you've given them in the right order. Make sure
to be consistent.
taptap taptap bookNotes /* Oops, arguments in wrong order, but NMatch has no way of knowing */tap
Built-in Matchers
NMatch is powered by matchers, objects whose job it is to store patterns and perform matching against them. Let's look at the built-in matchers before discussing how you can build your own.
Id
The most basic matcher is Id
, whose "patterns" can be any object, and
whose "matching" is just applying the strict equality (===
) operator. It's
the equivalent of a Map
, and in fact uses a Map
internally to store
patterns and values.
const Id = const id = idid taptaptaptap const arr = 1 2 3idconst obj = a: 1 b: 2 id taptap taptap
Calling set
a second time with the same pattern overrides the old value
idtap
You can use any object for patterns and/or values
const dub = 2 * aididtaptaptap
How it's implemented
Matchers are essentially enhanced Maps: they bind keys to values. The
difference is that the key-matching operation for Matchers can be anything,
whereas for Maps it's always ===
. Still, Maps are so useful that we need
a matcher that replicates their behavior. Id
is that matcher. It's a simple
wrapper around a Map
.
{ this_map = }
Maps have a get(key)
method that returns the value bound to key
.
Matchers need two such methods: one for pattern matching, and one for
getting the value for a pattern (literally). These are the match
and
pattern
methods, respectively.
match
is a generator that yields results in order from best match to
worst. In our case here we will either yield one value or none: either
there's a value at the given key, or there isn't. But more generally, match
methods can yield 0 or more results.
* { const v = this_map if v !== undefined v }
pattern
is a getter that's used to bind a value to a pattern. Matchers
don't store these values directly; they store "container" objects on which
the caller can attach values. This layer of indirection is what allows
NMatch to chain matchers. pattern
returns the container object associated
to the given pattern, first creating it if it doesn't exist.
{ let v = this_map if v === undefined v = {} this_map return v }}
Paths
Paths
matches paths against patterns that can contain wildcards. It makes
use of the hierarchical nature of paths to store and match patterns
efficiently. If you run a benchmark test please share your results.
const NMatch = const Paths = const p =
Patterns are made up of literals, wildcards, and super-wildcards. Literals match when strings are exactly equal, obv:
ppp taptap
Wildcards (*
) will match anything in a single path segment
pp taptaptap
Super-wildcards (**
) will match anything including further path segments
p taptap
It's an error if you try to add more patterns after a super-wildcard
tap
Wildcards and super-wildcards apply to path segments as a whole; there are no partial string matches. The following example patterns are just literals:
pp taptaptap
Only patterns can have wildcards. When you call match
, the argument is just
a literal.
pp tap
When more than one pattern matches, they are sorted in order from tightest match to loosest match. A literal matches more tightly than a wildcard, which in turn matches more tightly than a super-wildcard. NMatch will return the first hit.
pppp taptaptap
Customizing
The default path separator is /
, but you can change that
const ns = '::' nstap
You can use a regex to specify the separator
const words = /\s+/ wordstap
Or you can define your own separator function
const urls = { const parts = path return partslength > 0 ? parts : ''}urlstap
You can use a falsy separator to turn off path separation altogether
const lit = '' littaptap
The default wildcard symbol is *
, but you can change that
const madLibs = ' ' '____' madLibstap
You can use a regex to specify what counts as a wildcard
const ruby = '/' /^:\w+/ rubytap
Or you can pass in your own function to determine if a string is a wildcard
const params = 'size' 'color'const fw = ':' params fwtap
You can use a falsy value to turn off wildcards altogether
const quiteLit = '.' null quiteLittaptap
The default super-wildcard symbol is **
, but you can change that
const trunc = ' ' '____' '...' trunctap
You can use a regex to specificy what counts as a super-wildcard
const apiGateway = '/' /^\{\w+\}$/ /^\{\w+\+\}$/ apiGatewaytap
Or you can pass in your own function to determine if a string is a super-wildcard
const anything = 0 0 true anythingtap
You can use a falsy value to turn off super-wildcards altogether
const http = '/' '*' false httphttptaptaptap
How it's implemented
Consider the difference between
find / -path /usr/bin/node
and
ls /usr/bin/node
The first visits every file on the system and checks if their name is "/usr/bin/node". It takes 15s to run on my laptop.
The second takes 3ms to run. It doesn't visit every file. It visits /usr
,
/usr/bin
, and /usr/bin/node
. It can do this because directories are
organized in a tree structure, and file names represent paths through that
tree. It just needs to walk the path one /
-delimited node at a time.
Inspired by this, we can build a Paths matcher that stores its patterns in a tree, and does its matching by traversing that tree.
We'll support three kinds of path elements: literals, wildcards, and super-wildcards. Literals are strings that match only the same string, wildcards match any string, and super-wildcards match any string, even across path separators. Take for instance this four pattern set:
Pattern | "/foo/bar" | "/foo/baz" | "/foo/bar/baz" |
---|---|---|---|
/foo/bar |
Match | No match | No match |
/foo/baz |
No match | Match | No match |
/foo/* |
Match | Match | No match |
/foo/** |
Match | Match | Match |
We can represent these four patterns as a tree with six nodes:
/
└── foo/
├── bar
├── baz
├── *
└── **
Before we get around to writing our matcher, let's implement that Node object. It will handle tree traversal and matching individual path segments.
We'll need a way for a Node to reference a child Node:
const nextKey = Symbol'nmatch/path nextNode'
And we'll need a way to tell whether a Node is the end of a path.
This isn't as simple as checking whether it has any children. In the
pattern set ("/foo", "/foo/bar")
, the Node "/foo" has a child Node,
but it's also the end of a path. We need to attach a flag on every
node that's a valid endpoint:
const endKey = Symbol'nmatch/path isEnd'
A Node needs to keep a list of its children. We can simply use an Object for
this purpose: the key is the child's path part string (e.g. "foo" or
"bar"), and the value is the child Node. We could treat *
and **
as
special keys for wildcards and super-wildcards, but because we let users
define custom wildcard tokens (via test functions), it's possible for *
or
**
to be legitimate literal path segments. So we'll use separate variables
to hold those two.
{ this_isWildcard = wildcardTest this_isSuperWildcard = superWildcardTest this_literals = {} this_wildcard = undefined this_superWildcard = undefined }
Matching is simple: we want to find an exact match, a wildcard match, and/or a super-wildcard match, in that order. So we'll ask three questions: "is there an exact match? a wildcard? a super-wildcard?". For any "yes", we yield the matching child Node. If we're at the end of the path, this means yielding the child directly; otherwise it means recursively matching the rest of the path against the child Node.
* { for let m of this_literalspathParts0 this_wildcard this_superWildcard if m === undefined continue const isLeaf = pathPartslength === 1 || m === this_superWildcard && mendKey !== undefined if isLeaf m const isBranch = pathPartslength > 1 && mnextKey !== undefined if isBranch mnextKey }
When adding paths to our Paths matcher via its pattern
method, we'll
need an analogous part
method on each Node: a function that returns a
handle to the part's container, and creates it as needed. There are two
modes: if the part is an endpoint, we just set the endpoint flag on the
container. Otherwise we put a new child Node in the container.
{ let p partType = this if isEndpoint pendKey = true else if partType === 'super-wildcard' throw 'Super wildcards must be the last path element' if pnextKey === undefined pnextKey = this_isWildcard this_isSuperWildcard return p }
Our part containers are just fresh Objects, i.e. {}
.
{ let partType = this let p = this if p === undefined if partType === 'super-wildcard' this_superWildcard = {} p = this_superWildcard else if partType === 'wildcard' this_wildcard = {} p = this_wildcard else this_literalspart = {} p = this_literalspart return p partType } { } { if this return 'super-wildcard' if this return 'wildcard' return 'literal' }}
The Node class we've just defined does all the heavy lifting when matching: it's the one that walks the tree and finds matches. The Paths class' main job is to split paths into parts, but that's done with a user-defined function. So there's not much left for it to do.
{ this_separate = typeof separator === 'function' ? separator : this const isWildcard = typeof wildcard === 'function' ? wildcard : this const isSuperwildcard = typeof superWildcard === 'function' ? superWildcard : this this_pathStart = isWildcard isSuperwildcard }
When adding a new pattern, we walk along the tree and create missing Nodes
as needed with the Node.part
method.
{ const pathParts = this var step = this_pathStart while pathPartslength > 1 step = stepnextKey return step } * { this_pathStart } { if !pattern return path return path } { if !pattern return false return pattern instanceof RegExp ? pattern : part === pattern }}
Any
The Any
matcher is a wrapper that lets you match more than one instance at
a time. You pass its constructor another matcher (e.g. Id
or Paths
), and
you pass its match
method an array of instances. It will loop through that
array and call match
on the underlying matcher, returning the first match
it finds. This is useful when you need to support fallbacks or aliases.
const NMatch = const Any = const Paths = const any = anyany taptap taptap
Any.match
takes an iterable for argument, and will throw an Error
otherwise. It doesn't count strings as iterables.
taptaptap
If you don't specify a matcher, Any
will default to using Id
.
const defaultAny = defaultAnydefaultAnytaptap
How it's implemented
All Any
does is one type check and one for loop; the real work is delegated
to the matcher it wraps.
{ this_matcher = matcher } { return this_matcher } * { if values == null || typeof valuesSymboliterator !== 'function' || typeof values === 'string' throw 'Argument must be a non-string iterable' for let value of values this_matcher }
Creating your own Matcher
Any object that implements the following two methods is a matcher:
function pattern (pattern)
stores the given pattern in the matcher, and
returns a container object on which we can set its value. NMatch.set
calls
this method.
function * match (instance)
yields a list of matches for the given
instance, ordered from best match to worst. NMatch.match
calls this
method.
There's no restriction on the type of argument taken by these functions. The one limitation is that they always get called with a single argument. The rest is up to you, and the semantics are pretty flexible.
For example, here's the implementation of the three matchers used in the intro:
{ super'/' /^\{\w+\}$/ /^\{\w+\+\}$/ } { supernull 'ANY' } { this_users = } { let u = this_users if u === undefined u = {} this_users return u } * { for let user u of this_users if termgroups u }
How matchers are used: NMatch's implementation
NMatch stores patterns in a tree-like structure, with the leftmost matcher as the root of the tree, and each subsequent matcher one level down in the tree. If you're working with a lot of patterns, you'll typically want to put your most discriminating matchers first to speed up matching operations.
const valueKey = Symbol'nmatch-value' { this this_matcherMakers = matcherMakers this_root = this_matcherMakers0 }
To set a value, we walk down the pattern tree, creating missing nodes as needed, and set the value on the end node.
const value = patterns this let cur = this_root const nexts = this_matcherMakers let pattern next while pattern = patterns next = nexts cur = cur if curvalueKey === undefined curvalueKey = cur = curvalueKey curvalueKey = value
To match an instance, we also walk down the pattern tree, but each step forward is a matching operation that returns 0 or more child nodes. If the first child node doesn't match, we try the second, and so on until we know for sure whether we have a match or not.
{ this return this } { const rest = instances for let candidate of matcher if restlength === 0 return candidatevalueKey let subMatch = this if subMatch !== null return subMatch return null } { if matcherMakerslength < 1 throw 'At least one matcher is required' for let matcher of matcherMakers if typeof matcher !== 'function' throw 'MatcherMakers must be functions' let m = if typeof mpattern !== 'function' || typeof mmatch !== 'function' throw 'MatcherMakers must have a `pattern` and a `match` function' } { if partslength !== this_matcherMakerslength throw 'Bad part count. ' + `Expected , have ` }}
Contributing
This project is deliberately left imperfect to encourage you to participate in its development. If you make a Pull Request that
- explains and solves a problem,
- follows standard style, and
- maintains 100% test coverage
it will be merged: this project follows the C4 process.
To make sure your commits follow the style guide and pass all tests, you can add
./.pre-commit
to your git pre-commit hook.