object-scan

Object-Scan

Find keys in object hierarchies using wildcard and glob matching and callbacks.

Install

Install with npm:

$ npm install --save object-scan

Usage

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' } } };

objectScan(['a.*.f'], { joined: true })(haystack);
// => [ 'a.e.f' ]

Features

• Input traversed exactly once during search
• Dependency free, small in size and very performant
• Separate Object and Array matching
• Wildcard and Regex matching
• Arbitrary depth matching
• Or-clause Syntax
• Exclusion Matching
• Full support for escaping
• Results returned in "delete-safe" order
• Search syntax is checked for correctness
• Lots of tests to ensure correctness

Options

Signature of all callbacks is

Fn({
  key, value, parent, parents, isMatch, matchedBy, excludedBy, traversedBy, isCircular
  getKey, getValue, getParent, getParents, getIsMatch, getMatchedBy, getExcludedBy, getTraversedBy, getIsCircular
  context
})

where:

• key: key that callback is invoked for (respects joined option).
• value: value for key.
• parent: current parent.
• parents: array of form [parent, grandparent, ...].
• isMatch: true iff last targeting needle exists and is non-excluding.
• matchedBy: all non-excluding needles targeting key.
• excludedBy: all excluding needles targeting key.
• traversedBy: all needles involved in traversing key.
• isCircular: true iff value contained in parents
• getKey: function that returns key
• getValue: function that returns value
• getParent: function that returns parent
• getParents: function that returns parents
• getIsMatch: function that returns isMatch
• getMatchedBy: function that returns matchedBy
• getExcludedBy: function that returns excludedBy
• getTraversedBy: function that returns traversedBy
• getIsCircular: function that returns isCircular
• context: as passed into the search

Notes on Performance:

• Arguments backed by getters use Functions Getter and should be accessed via destructuring to prevent redundant computation.
• Getters should be used to improve performance for conditional access. E.g. if (isMatch) { getParents() ... }.
• For performance reasons, the same object is passed to all callbacks.

filterFn

Type: function
Default: undefined

If defined, this callback is invoked for every match. If false is returned, the current key is excluded from the result.

The return value of this callback has no effect when a search context is provided.

Can be used to do processing as matching keys are traversed.

Invoked in same order as matches would appear in result.

This method is conceptually similar to Array.filter().

Examples:

['**'] (filter function)

const objectScan = require('object-scan');

const haystack = { a: 0, b: 'bar' };

objectScan(['**'], {
  joined: true,
  filterFn: ({ value }) => typeof value === 'string'
})(haystack);
// => [ 'b' ]

breakFn

Type: function
Default: undefined

If defined, this callback is invoked for every key that is traversed by the search. If true is returned, all keys nested under the current key are skipped in the search and from the final result.

Note that breakFn is invoked before the corresponding filterFn might be invoked.

Examples:

['**'] (break function)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 0 }, d: { e: 1 }, f: 2 } };

objectScan(['**'], {
  joined: true,
  breakFn: ({ key }) => key === 'a.b'
})(haystack);
// => [ 'a.f', 'a.d.e', 'a.d', 'a.b', 'a' ]

joined

Type: boolean
Default: false

Keys are returned as a string when set to true instead of as a list.

Setting this option to true will negatively impact performance.

Note that _.get and _.set fully support lists.

Examples:

['[*]'] (joined)

const objectScan = require('object-scan');

const haystack = [0, 1, 2];

objectScan(['[*]'], { joined: true })(haystack);
// => [ '[2]', '[1]', '[0]' ]

['[*]'] (not joined)

const objectScan = require('object-scan');

const haystack = [0, 1, 2];

objectScan(['[*]'])(haystack);
// => [ [ 2 ], [ 1 ], [ 0 ] ]

useArraySelector

Type: boolean
Default: true

When set to false, no array selectors should be used in any needles and arrays are automatically traversed.

Note that the results still include the array selectors.

Examples:

['a', 'b.d'] (automatic array traversal)

const objectScan = require('object-scan');

const haystack = [{ a: 0 }, { b: [{ c: 1 }, { d: 2 }] }];

objectScan(['a', 'b.d'], {
  joined: true,
  useArraySelector: false
})(haystack);
// => [ '[1].b[1].d', '[0].a' ]

[''] (select top level array elements)

const objectScan = require('object-scan');

const haystack = [{ a: 0 }, { b: 1 }];

objectScan([''], {
  joined: true,
  useArraySelector: false
})(haystack);
// => [ '[1]', '[0]' ]

strict

Type: boolean
Default: true

When set to true, errors are thrown when:

• a path is identical to a previous path
• a path invalidates a previous path
• a path contains consecutive recursions

Examples:

['a.b', 'a.b'] (identical)

const objectScan = require('object-scan');

const haystack = [];

objectScan(['a.b', 'a.b'], { joined: true })(haystack);
// => 'Error: Redundant Needle Target: "a.b" vs "a.b"'

['a.{b,b}'] (identical, same needle)

const objectScan = require('object-scan');

const haystack = [];

objectScan(['a.{b,b}'], { joined: true })(haystack);
// => 'Error: Redundant Needle Target: "a.{b,b}" vs "a.{b,b}"'

['a.b', 'a.**'] (invalidates previous)

const objectScan = require('object-scan');

const haystack = [];

objectScan(['a.b', 'a.**'], { joined: true })(haystack);
// => 'Error: Needle Target Invalidated: "a.b" by "a.**"'

['**.!**'] (consecutive recursion)

const objectScan = require('object-scan');

const haystack = [];

objectScan(['**.!**'], { joined: true })(haystack);
// => 'Error: Redundant Recursion: "**.!**"'

Search Context

A context can be passed into a search invocation as a second parameter. It is available in all callbacks and can be used to manage state across a search invocation without having to recompile the search.

By default all matched keys are returned from a search invocation. However, when it is not undefined, the context is returned instead.

Examples:

['**'] (output last segments only)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 0, d: 1 }, e: 2 } };

objectScan(['**'], {
  filterFn: ({ key, context }) => { context.push(key[key.length - 1]); }
})(haystack, []);
// => [ 'e', 'd', 'c', 'b', 'a' ]

Matching

Matching is based on the Javascript Object / Array selector syntax with some notable extensions.

Array vs Object

To match an Array path, rectangular brackets are used.
Examples:

['[2]'] (matches `[2]` in an array)

const objectScan = require('object-scan');

const haystack = [0, 1, 2, 3, 4];

objectScan(['[2]'], { joined: true })(haystack);
// => [ '[2]' ]

To match an Object path, the name of the path is used.
Examples:

['foo'] (matches the path `foo` in an object)

const objectScan = require('object-scan');

const haystack = { foo: 0, bar: 1 };

objectScan(['foo'], { joined: true })(haystack);
// => [ 'foo' ]

Wildcard

Wildcards can be used with Array and Object selector.

The following characters have special meaning when not escaped:

• *: Match zero or more character
• +: Match one or more character
• ?: Match exactly one character
• \: Escape the subsequent character

Examples:

['[1?]'] (matches two digit keys starting with a one)

const objectScan = require('object-scan');

const haystack = [...Array(30).keys()];

objectScan(['[1?]'], { joined: true })(haystack);
// => [ '[19]', '[18]', '[17]', '[16]', '[15]', '[14]', '[13]', '[12]', '[11]', '[10]' ]

Regex

Regex can be used with Array and Object selector by using parentheses.

Examples:

['(^foo)'] (match all object paths starting with `foo`)

const objectScan = require('object-scan');

const haystack = { foo: 0, foobar: 1, bar: 2 };

objectScan(['(^foo)'], { joined: true })(haystack);
// => [ 'foobar', 'foo' ]

['[(5)]'] (matches all array paths containing `5`)

const objectScan = require('object-scan');

const haystack = [...Array(20).keys()];

objectScan(['[(5)]'], { joined: true })(haystack);
// => [ '[15]', '[5]' ]

['[(^[01]$)]'] (match first and second path in an array)

const objectScan = require('object-scan');

const haystack = ['a', 'b', 'c', 'd'];

objectScan(['[(^[01]$)]'], { joined: true })(haystack);
// => [ '[1]', '[0]' ]

Arbitrary Depth

There are two types of recursion matching:

• **: Matches zero or more nestings
• ++: Matches one or more nestings

Recursions can be combined with a regex by appending the regex.

Examples:

['a.**'] (matches zero or more nestings under `a`)

const objectScan = require('object-scan');

const haystack = { a: { b: 0, c: 0 } };

objectScan(['a.**'], { joined: true })(haystack);
// => [ 'a.c', 'a.b', 'a' ]

['a.++'] (matches one or more nestings under `a`)

const objectScan = require('object-scan');

const haystack = { a: { b: 0, c: 0 } };

objectScan(['a.++'], { joined: true })(haystack);
// => [ 'a.c', 'a.b' ]

['**(1)'] (matches all paths containing `1`)

const objectScan = require('object-scan');

const haystack = { 1: { 1: ['a', 'b'] } };

objectScan(['**(1)'], { joined: true })(haystack);
// => [ '1.1[1]', '1.1', '1' ]

Or Clause

Can be used with Array and Object selector by using curley brackets.

This makes it possible to target multiple paths in a single needle. It also makes it easier to reduce redundancy.

Examples:

['[{0,1}]'] (match first and second path in an array)

const objectScan = require('object-scan');

const haystack = ['a', 'b', 'c', 'd'];

objectScan(['[{0,1}]'], { joined: true })(haystack);
// => [ '[1]', '[0]' ]

Exclusion

To exclude a path from being matched, use the exclamation mark.

Examples:

['**,!**.a'] (matches all paths, except those where the last segment is `a`)

const objectScan = require('object-scan');

const haystack = { a: 0, b: { a: 1, c: 2 } };

objectScan(['**,!**.a'], { joined: true })(haystack);
// => [ 'b.c', 'b' ]

Escaping

The following characters are considered special and need to be escaped using \, if they should be matched in a key:
[, ], {, }, (, ), ,, ., !, ?, *, + and \.

Examples

More extensive examples can be found in the tests.

['*'] (top level keys)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['*'], { joined: true })(haystack);
// => [ 'k', 'a' ]

['a.*.f'] (nested keys)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['a.*.f'], { joined: true })(haystack);
// => [ 'a.e.f' ]

['*.*.*'] (multiple nested keys)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['*.*.*'], { joined: true })(haystack);
// => [ 'a.e.f', 'a.b.c' ]

['a.*.{c,f}'] (or filter)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['a.*.{c,f}'], { joined: true })(haystack);
// => [ 'a.e.f', 'a.b.c' ]

['a.*.{c,f}'] (or filter, not joined)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['a.*.{c,f}'])(haystack);
// => [ [ 'a', 'e', 'f' ], [ 'a', 'b', 'c' ] ]

['*.*[*]'] (list filter)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['*.*[*]'], { joined: true })(haystack);
// => [ 'a.h[1]', 'a.h[0]' ]

['*[*]'] (list filter, unmatched)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['*[*]'], { joined: true })(haystack);
// => []

['**'] (star recursion)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['**'], { joined: true })(haystack);
// => [ 'k', 'a.h[1]', 'a.h[0]', 'a.h', 'a.e.f', 'a.e', 'a.b.c', 'a.b', 'a' ]

['++.++'] (plus recursion)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['++.++'], { joined: true })(haystack);
// => [ 'a.h[1]', 'a.h[0]', 'a.h', 'a.e.f', 'a.e', 'a.b.c', 'a.b' ]

['**.f'] (star recursion ending to f)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['**.f'], { joined: true })(haystack);
// => [ 'a.e.f' ]

['**[*]'] (star recursion ending to array)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['**[*]'], { joined: true })(haystack);
// => [ 'a.h[1]', 'a.h[0]' ]

['a.*,!a.e'] (exclusion filter)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['a.*,!a.e'], { joined: true })(haystack);
// => [ 'a.h', 'a.b' ]

['**.(^[bc]$)'] (regex matching)

const objectScan = require('object-scan');

const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };

objectScan(['**.(^[bc]$)'], { joined: true })(haystack);
// => [ 'a.b.c', 'a.b' ]

Edge Cases

The top level object(s) are matched by the empty needle "". Useful for matching objects nested in arrays by setting useArraySelector to false. Note that the empty string does not work with _.get and _.set.

Internals

Conceptually this package works as follows:

1. During initialization the needles are parsed and built into a search tree. Various information is pre-computed and stored for every node. Finally the search function is returned.

2. When the search function is invoked, the input is traversed simultaneously with the relevant nodes of the search tree. Processing multiple search tree branches in parallel allows for a single traversal of the input.

Having a separate initialization stage allows for a performant search and significant speed ups when applying the same search to different input.