Object-Scan
Traverse object hierarchies using matching and callbacks.
Install
Install with npm:
$ npm install --save object-scan
Usage
import objectScan from 'object-scan';
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' } } };
objectScan(['a.*.f'], { joined: true })(haystack);
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
- Traversal in "delete-safe" order
- Recursion free implementation
- Search syntax validated
- Lots of tests and examples
Matching
A needle expression specifies one or more paths to an element (or a set of elements) in a JSON structure. Paths use the dot notation:
store.book[0].title
Array
Rectangular brackets for array path matching.
Examples:
['[2]']
(exact in array)
const haystack = [0, 1, 2, 3, 4];
objectScan(['[2]'], { joined: true })(haystack);
['[1]']
(no match in object)
const haystack = { 0: 'a', 1: 'b', 2: 'c' };
objectScan(['[1]'], { joined: true })(haystack);
Object
Property name for object property matching.
Examples:
['foo']
(exact in object)
const haystack = { foo: 0, bar: 1 };
objectScan(['foo'], { joined: true })(haystack);
['1']
(no match in array)
const haystack = [0, 1, 2, 3, 4];
objectScan(['1'], { joined: true })(haystack);
Wildcard
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
Wildcards can be used with Array and Object selector.
Examples:
['*']
(top level)
const haystack = { a: { b: 0, c: 1 }, d: 2 };
objectScan(['*'], { joined: true })(haystack);
['[?5]']
(two digit ending in five)
const haystack = [...Array(30).keys()];
objectScan(['[?5]'], { joined: true })(haystack);
['a.+.c']
(nested)
const haystack = { a: { b: { c: 0 }, d: { f: 0 } } };
objectScan(['a.+.c'], { joined: true })(haystack);
['a.\\+.c']
(escaped)
const haystack = { a: { b: { c: 0 }, '+': { c: 0 } } };
objectScan(['a.\\+.c'], { joined: true })(haystack);
Regex
Regex are defined by using parentheses.
Can be used with Array and Object selector.
Examples:
['(^foo)']
(starting with `foo`)
const haystack = { foo: 0, foobar: 1, bar: 2 };
objectScan(['(^foo)'], { joined: true })(haystack);
['[(5)]']
(containing `5`)
const haystack = [...Array(20).keys()];
objectScan(['[(5)]'], { joined: true })(haystack);
['[(^[01]$)]']
(`[0]` and `[1]`)
const haystack = ['a', 'b', 'c', 'd'];
objectScan(['[(^[01]$)]'], { joined: true })(haystack);
['[(^[^01]$)]']
(other than `[0]` and `[1]`)
const haystack = ['a', 'b', 'c', 'd'];
objectScan(['[(^[^01]$)]'], { joined: true })(haystack);
['[*]', '[!(^[01]$)]']
(match all and exclude `[0]` and `[1]`)
const haystack = ['a', 'b', 'c', 'd'];
objectScan(['[*]', '[!(^[01]$)]'], { joined: true })(haystack);
Arbitrary Depth
There are two types of arbitrary depth matching:
**
: Matches zero or more nestings++
: Matches one or more nestings
Recursions can be combined with a regex or a group by appending the regex or group.
Examples:
['a.**']
(zero or more nestings under `a`)
const haystack = { a: { b: 0, c: 0 } };
objectScan(['a.**'], { joined: true })(haystack);
['a.++']
(one or more nestings under `a`)
const haystack = { a: { b: 0, c: 0 } };
objectScan(['a.++'], { joined: true })(haystack);
['**(1)']
(all containing `1` at every level)
const haystack = { 1: { 1: ['c', 'd'] }, 510: 'e', foo: { 1: 'f' } };
objectScan(['**(1)'], { joined: true })(haystack);
Or Clause
Or Clauses are defined by using curley brackets.
Can be used with Array and Object selector.
Examples:
['[{0,1}]']
(`[0]` and `[1]`)
const haystack = ['a', 'b', 'c', 'd'];
objectScan(['[{0,1}]'], { joined: true })(haystack);
['{a,d}.{b,f}']
(`a.b`, `a.f`, `d.b` and `d.f`)
const haystack = { a: { b: 0, c: 1 }, d: { e: 2, f: 3 } };
objectScan(['{a,d}.{b,f}'], { joined: true })(haystack);
Nested Path Recursion
To match a nested path recursively,
combine arbitrary depth matching with an or-clause.
There are two types of nested path matching:
**{...}
: Matches path(s) in group zero or more times++{...}
: Matches path(s) in group one or more times
Examples:
['++{[0][1]}']
(`cyclic path`)
const haystack = [[[[0, 1], [1, 2]], [[3, 4], [5, 6]]], [[[7, 8], [9, 10]], [[11, 12], [13, 14]]]];
objectScan(['++{[0][1]}'], { joined: true })(haystack);
['++{[0],[1]}']
(`nested or`)
const haystack = [[0, 1, 2], [3, 4, 5], [6, 7, 8]];
objectScan(['++{[0],[1]}'], { joined: true })(haystack);
['**{[*]}']
(`traverse only array`)
const haystack = [[[{ a: [1] }], [2]]];
objectScan(['**{[*]}'], { joined: true })(haystack);
['**{*}']
(`traverse only object`)
const haystack = { a: [0, { b: 1 }], c: { d: 2 } };
objectScan(['**{*}'], { joined: true })(haystack);
['a.**{b.c}']
(`zero or more times`)
const haystack = { a: { b: { c: { b: { c: 0 } } } } };
objectScan(['a.**{b.c}'], { joined: true })(haystack);
['a.++{b.c}']
(`one or more times`)
const haystack = { a: { b: { c: { b: { c: 0 } } } } };
objectScan(['a.++{b.c}'], { joined: true })(haystack);
Exclusion
To exclude a path, use exclamation mark.
Examples:
['{a,b},!a']
(only `b`)
const haystack = { a: 0, b: 1 };
objectScan(['{a,b},!a'], {
joined: true,
strict: false
})(haystack);
['**,!**.a']
(all except ending in `a`)
const haystack = { a: 0, b: { a: 1, c: 2 } };
objectScan(['**,!**.a'], { joined: true })(haystack);
Escaping
The following characters are considered special and need to
be escaped using \
, if they should be matched in a key:
[
, ]
, {
, }
, (
, )
, ,
, .
, !
, ?
, *
, +
and \
.
Examples:
['\\[1\\]']
(special object key)
const haystack = { '[1]': 0 };
objectScan(['\\[1\\]'], { joined: true })(haystack);
Options
Signature of all callbacks is
Fn({ key, value, ... })
where:
key
: key that callback is invoked for (respects joined
option).value
: value for key.entry
: entry consisting of [key
, value
].property
: current parent property.gproperty
: current grandparent property.parent
: current parent.gparent
: current grandparent.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
isLeaf
: true iff value
can not be traverseddepth
: length of key
result
: intermittent result as defined by rtn
getKey
: function that returns key
getValue
: function that returns value
getEntry
: function that returns entry
getProperty
: function that returns property
getGproperty
: function that returns gproperty
getParent
: function that returns parent
getGparent
: function that returns gparent
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
getIsLeaf
: function that returns isLeaf
getDepth
: function that returns depth
getResult
: function that returns result
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
When 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 haystack = { a: 0, b: 'bar' };
objectScan(['**'], {
joined: true,
filterFn: ({ value }) => typeof value === 'string'
})(haystack);
breakFn
Type: function
Default: undefined
When 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 haystack = { a: { b: { c: 0 } } };
objectScan(['**'], {
joined: true,
breakFn: ({ key }) => key === 'a.b'
})(haystack);
beforeFn
Type: function
Default: undefined
When defined, this function is called before traversal as beforeFn(state = { haystack, context })
and state.haystack
is then traversed using state.context
.
Examples:
['**']
(combining haystack and context)
const haystack = { a: 0 };
objectScan(['**'], {
joined: true,
beforeFn: (state) => { state.haystack = [state.haystack, state.context]; },
rtn: 'key'
})(haystack, { b: 0 });
afterFn
Type: function
Default: undefined
When defined, this function is called after traversal as afterFn(state = { result, haystack, context })
and state.result
is then returned from the search invocation.
Examples:
['**']
(returning count plus context)
const haystack = { a: 0 };
objectScan(['**'], {
afterFn: (state) => { state.result += state.context; },
rtn: 'count'
})(haystack, 5);
compareFn
Type: function
Default: undefined
This function has the same signature as the callback functions. When defined it is expected to return a function
or undefined
.
The returned value is used as a comparator to determine the traversal order of any object
keys.
This works together with the reverse
option.
Examples:
['**']
(simple sort)
const haystack = { a: 0, c: 1, b: 2 };
objectScan(['**'], {
joined: true,
compareFn: () => (k1, k2) => k1.localeCompare(k2),
reverse: false
})(haystack);
reverse
Type: boolean
Default: true
When set to true
, the scan is performed in reverse order. This means breakFn
is executed in reverse post-order and
filterFn
in reverse pre-order. Otherwise breakFn
is executed in pre-order and filterFn
in post-order.
When reverse
is true
the scan is delete-safe. I.e. property
can be deleted / spliced from parent
object / array in filterFn
.
Examples:
['**']
(breakFn, reverse true)
const haystack = { f: { b: { a: {}, d: { c: {}, e: {} } }, g: { i: { h: {} } } } };
objectScan(['**'], {
breakFn: ({ isMatch, property, context }) => { if (isMatch) { context.push(property); } },
reverse: true
})(haystack, []);
['**']
(filterFn, reverse true)
const haystack = { f: { b: { a: {}, d: { c: {}, e: {} } }, g: { i: { h: {} } } } };
objectScan(['**'], {
filterFn: ({ property, context }) => { context.push(property); },
reverse: true
})(haystack, []);
['**']
(breakFn, reverse false)
const haystack = { f: { b: { a: {}, d: { c: {}, e: {} } }, g: { i: { h: {} } } } };
objectScan(['**'], {
breakFn: ({ isMatch, property, context }) => { if (isMatch) { context.push(property); } },
reverse: false
})(haystack, []);
['**']
(filterFn, reverse false)
const haystack = { f: { b: { a: {}, d: { c: {}, e: {} } }, g: { i: { h: {} } } } };
objectScan(['**'], {
filterFn: ({ property, context }) => { context.push(property); },
reverse: false
})(haystack, []);
orderByNeedles
Type: boolean
Default: false
When set to false
, all targeted keys are traversed and matched
in the order determined by the compareFn
and reverse
option.
When set to true
, all targeted keys are traversed and matched
in the order determined by the corresponding needles,
falling back to the above ordering.
Note that this option is constraint by the depth-first search approach.
Examples:
['c', 'a', 'b']
(order by needle)
const haystack = { a: 0, b: 1, c: 1 };
objectScan(['c', 'a', 'b'], {
joined: true,
orderByNeedles: true
})(haystack);
['b', '*']
(fallback reverse)
const haystack = { a: 0, b: 1, c: 1 };
objectScan(['b', '*'], {
joined: true,
reverse: true,
orderByNeedles: true
})(haystack);
['b', '*']
(fallback not reverse)
const haystack = { a: 0, b: 1, c: 1 };
objectScan(['b', '*'], {
joined: true,
reverse: false,
orderByNeedles: true
})(haystack);
['a', 'b.c', 'd']
(nested match)
const haystack = { a: 0, b: { c: 1 }, d: 2 };
objectScan(['a', 'b.c', 'd'], {
joined: true,
orderByNeedles: true
})(haystack);
['b', 'a', 'b.c', 'd']
(matches traverse first)
const haystack = { a: 0, b: { c: 1 }, d: 2 };
objectScan(['b', 'a', 'b.c', 'd'], {
joined: true,
orderByNeedles: true
})(haystack);
abort
Type: boolean
Default: false
When set to true
the scan immediately returns after the first match.
Examples:
['a', 'b']
(only return first property)
const haystack = { a: 0, b: 1 };
objectScan(['a', 'b'], {
rtn: 'property',
abort: true
})(haystack);
['[0]', '[1]']
(abort changes count)
const haystack = ['a', 'b'];
objectScan(['[0]', '[1]'], {
rtn: 'count',
abort: true
})(haystack);
rtn
Type: string
or array
or function
Default: dynamic
Defaults to key
when search context is undefined and to context
otherwise.
Can be explicitly set as a string
:
context
: search context is returnedkey
: as passed into filterFn
value
: as passed into filterFn
entry
: as passed into filterFn
property
: as passed into filterFn
gproperty
: as passed into filterFn
parent
: as passed into filterFn
gparent
: as passed into filterFn
parents
: as passed into filterFn
isMatch
: as passed into filterFn
matchedBy
: as passed into filterFn
excludedBy
: as passed into filterFn
traversedBy
: as passed into filterFn
isCircular
: as passed into filterFn
isLeaf
: as passed into filterFn
depth
: as passed into filterFn
bool
: returns true iff a match is foundcount
: returns the match count
When set to array
, can contain any of the above except context
, bool
and count
.
When set to function
, called with callback signature for every match. Returned value is added to the result.
When abort is set to true
and rtn is not context
, bool
or count
,
the first entry of the result or undefined is returned.
Examples:
['[*]']
(return values)
const haystack = ['a', 'b', 'c'];
objectScan(['[*]'], { rtn: 'value' })(haystack);
['foo[*]']
(return entries)
const haystack = { foo: ['bar'] };
objectScan(['foo[*]'], { rtn: 'entry' })(haystack);
['a.b.c', 'a']
(return properties)
const haystack = { a: { b: { c: 0 } } };
objectScan(['a.b.c', 'a'], { rtn: 'property' })(haystack);
['a.b', 'a.c']
(checks for any match, full scan)
const haystack = { a: { b: 0, c: 1 } };
objectScan(['a.b', 'a.c'], { rtn: 'bool' })(haystack);
['**']
(return not provided context)
const haystack = { a: 0 };
objectScan(['**'], { rtn: 'context' })(haystack);
['a.b.{c,d}']
(return keys with context passed)
const haystack = { a: { b: { c: 0, d: 1 } } };
objectScan(['a.b.{c,d}'], { rtn: 'key' })(haystack, []);
['a.b.{c,d}']
(return custom array)
const haystack = { a: { b: { c: 0, d: 1 } } };
objectScan(['a.b.{c,d}'], { rtn: ['property', 'value'] })(haystack, []);
['**']
(return value plus one)
const haystack = { a: { b: { c: 0, d: 1 } } };
objectScan(['**'], {
filterFn: ({ isLeaf }) => isLeaf,
rtn: ({ value }) => value + 1
})(haystack);
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:
['[*]', '[*].foo']
(joined)
const haystack = [0, 1, { foo: 'bar' }];
objectScan(['[*]', '[*].foo'], { joined: true })(haystack);
['[*]', '[*].foo']
(not joined)
const haystack = [0, 1, { foo: 'bar' }];
objectScan(['[*]', '[*].foo'])(haystack);
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 haystack = [{ a: 0 }, { b: [{ c: 1 }, { d: 2 }] }];
objectScan(['a', 'b.d'], {
joined: true,
useArraySelector: false
})(haystack);
['']
(top level array matching)
const haystack = [{ a: 0 }, { b: 1 }];
objectScan([''], {
joined: true,
useArraySelector: false
})(haystack);
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 haystack = [];
objectScan(['a.b', 'a.b'], { joined: true })(haystack);
['a.{b,b}']
(identical, same needle)
const haystack = [];
objectScan(['a.{b,b}'], { joined: true })(haystack);
['a.b', 'a.**']
(invalidates previous)
const haystack = [];
objectScan(['a.b', 'a.**'], { joined: true })(haystack);
['**.!**']
(consecutive recursion)
const haystack = [];
objectScan(['**.!**'], { joined: true })(haystack);
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:
['**.{c,d,e}']
(sum values)
const haystack = { a: { b: { c: 2, d: 11 }, e: 7 } };
objectScan(['**.{c,d,e}'], {
joined: true,
filterFn: ({ value, context }) => { context.sum += value; }
})(haystack, { sum: 0 });
Examples
More extensive examples can be found in the tests.
['a.*.f']
(nested)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['a.*.f'], { joined: true })(haystack);
['*.*.*']
(multiple nested)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['*.*.*'], { joined: true })(haystack);
['a.*.{c,f}']
(or filter)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['a.*.{c,f}'], { joined: true })(haystack);
['a.*.{c,f}']
(or filter, not joined)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['a.*.{c,f}'])(haystack);
['*.*[*]']
(list filter)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['*.*[*]'], { joined: true })(haystack);
['*[*]']
(list filter, unmatched)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['*[*]'], { joined: true })(haystack);
['**']
(star recursion)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['**'], { joined: true })(haystack);
['++.++']
(plus recursion)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['++.++'], { joined: true })(haystack);
['**.f']
(star recursion ending in f)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['**.f'], { joined: true })(haystack);
['**[*]']
(star recursion ending in array)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['**[*]'], { joined: true })(haystack);
['a.*,!a.e']
(exclusion filter)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['a.*,!a.e'], { joined: true })(haystack);
['**.(^[bc]$)']
(regex matching)
const haystack = { a: { b: { c: 'd' }, e: { f: 'g' }, h: ['i', 'j'] }, k: 'l' };
objectScan(['**.(^[bc]$)'], { joined: true })(haystack);
Edge Cases
Top level object(s) are matched by the empty needle ''
. This is useful for matching objects nested in arrays by setting useArraySelector
to false
.
To match the actual empty string as a key, use (^$)
.
Note that the empty string does not work to match top level objects with
_.get or _.set.
Examples:
['']
(match top level objects in array)
const haystack = [{}, {}];
objectScan([''], {
joined: true,
useArraySelector: false
})(haystack);
['']
(match top level object)
const haystack = {};
objectScan([''], { joined: true })(haystack);
['**.(^$)']
(match empty string keys)
const haystack = { '': 0, a: { '': 1 } };
objectScan(['**.(^$)'])(haystack);
['**(^a$)']
(star recursion matches roots)
const haystack = [0, [{ a: 1 }, 2]];
objectScan(['**(^a$)'], {
joined: true,
useArraySelector: false
})(haystack);
Internals
Conceptually this package works as follows:
-
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.
-
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.