key-crawler

Key Crawler

Use this library to traverse object contents as though it were a graph. The state of the traversal is exposed while you're doing so, letting you grab snapshots of a given position in the property tree. Those states can in turn be used to visit related items, such an object's owner or siblings.

This also supports defining custom traversal for certain object types, letting you traverse more complex structures like tree nodes or DOM nodes.

Quickstart

Installation

You can install this library though npm like so:

$ npm install --save key-crawler

Usage

To perform a traversal, you'll need to create an instance of the traversal strategy you want to use. For depth first traversals, that looks like this:

import { DepthFirstSearch } from 'key-crawler'`

const target = { x: 1, y: 2}
const search = new DepthFirstSearch()
const values: unknown[] = []
search.traverse(
  target,
  (state) => {
    values.push(state.route.target)
  }
)

As you can see a basic traversal just involves calling the search's "traverse" function with the source object and callback. The state passed into the callback has the following properties:

• route: Contains information on how we got the current position. This includes the following:
  • path: Lists the keys used at each step of the traversal.
  • target: The current value the traversal is visiting.
  • vertices: Lists handlers for each object between where the traversal started and the current target value.
• visited: Lists all objects already visited by the traversal. This is mainly used to protect against circular references.
• completed: Signals the traversal shouldn't be processed further. You can manually set this in the callback to exit the traversal.
• skipIteration: Signals the traversal to not proceed into the current value's contents. Unlike with the completed signal, this one gets reset after being applied.

By default, depth first searches be a preorder searchs. To make this a postorder search, import SearchOrder and set SearchOrder.POSTORDER as the first constructor parameter, like this: new DepthFirstSearch(SearchOrder.POSTORDER).

Breadth first searchs operate much the same. Simply swap BreadthFirstSearch in place of DepthFirstSearch. Note that breadth first searchs don't support search order, so you can't pass in a parameter to set that for them. Such searches do attach a routeQueue to the state, though you probably won't make much use of that.

Vertex Factories

You can pass an instance of this library's ValueVertexFactory class into a traverse function as an optional third parameter. This is mainly used when you want special handling for certain objects, such as having tree nodes with a dedicated children property.

To set that up, simply create a vertex factory with a set of special object creation rules, like this:

import { ValueVertexFactory, UntypedObject, DefinedObjectVertex } from 'key-crawler'

const target = {
  value: 'root',
  children: [
    {
      value: 'child'
    }
  ]
}
const search = new DepthFirstSearch()
const values: unknown[] = []
search.traverse(
  target,
  (state) => {
    values.push(state.route.target)
  },
  new ValueVertexFactory([
    (value: UntypedObject) => {
      if ('children' in value) {
        return new DefinedObjectVertex(value, ['children'])
      }
    }
  ])
)

You'll note that factory accepts a list of creation rules as an optional parameter. These are callbacks that return a vertex if the provided object meets their criteria. The factory will use the first such rule to produce a vertex, defaulting to a generic ObjectVertex or PrimitiveVertex if none match.

Prior to version 1.2.0, these rules were objects with separate checkValue and createVertex functions, so you'd use this instead:

{
  checkValue: (value: UntypedObject) => 'children' in value,
  createVertex: (value: UntypedObject) => new DefinedObjectVertex(value, ['children'])
}

UntypedObject is a utility type for objects with no key or value type restrictions.

DefinedObjectVertex is specialized example of one of the aforementioned wrappers that lets you specify what properties should be treated as keys. In this case, we're telling it to use the children property and ignore the value property for purposes of traversal.

Key Crawlers

If you find yourself reusing certain strategies and vertex factories, you may want to create a dedicated KeyCrawler instance. These accept a traversal strategy as their first parameter and a vertex factory as their second parameter. Once created, you can simply call their traverse function with the root object and callback as if they were a traversal function (minus the ability to specify a new vertex factory).

Searches

In addition to basic traversals, key crawlers also support value searches through the crawler's search function. These use the same root / callback pairing traverse calls do, save for the expectation that said callbacks with return a boolean. The search funtion's will then return an object with a results property that lists the routes to each value the callback returned true for.

The search function also accepts a maxResults value as it's third parameter, letting you do things like return after the first match.

Value Mapping

As of 1.0.3, key crawlers have a mapValue function that helps you build a modified copy of a given object and it's traversed properties. This takes 2 parameters, the object to be copied and the conversion function to be applied to each vertex visited. Note that converstion function is given the traversal state as it's only parameter, giving you the ability to copy traversal information as part of this mapping.

Extending Routes

Key crawlers can also make it easy to visit the descendant of a given value, provided you have it's routes. If you know the key path to the target value, simply call extendRoute for your crawler, with the target route and key list as parameters. If you know the child's iteration order, you can pass that path into extendRouteByIndices instead. For example, to get the first child of a route you'd use crawler.extendRouteByIndices(route, [0]).

Note that those both mutate the provided route. If you want to avoid doing so you can use getSubroute in place of extendRoute and getChildRoute in place of extendRouteByIndices. Note that unlike extendRouteByIndices, getChildRoute only goes down 1 step to the target's immediate descendants.

Reverting Routes

On the other hand, if you want to roll back to an earlier value along a traversal route, you can do so by calling the crawler's revertRoute function with the target route as it's first parameter. This normally goes back 1 step, but you can pass a desired number of steps to revert by passing that in as the second parameter. To avoid mutating the target route, use getParentRoute instead. As with revertRoute, that will get the immediate parent by default, but lets you get an earlier ancestor by specifying the number of steps back you want to take.

Nested Values

If you're using object that stash their contents inside a member property or through an accessor, consider using a ValueLookupVertex in the vertex factory. These take the target object as their first parameter and a template for the target path as the second parameter.

These templates can be build like a normal key path, but when used to find a key value we replace a certain placeholder string in that template with the target key. By default this replaces the "$key" string, but you can specify a different one as the constructor's third parameter if desired.

Note that these paths can contain function call references. These simply consist of an object with the function's property name and it's argument list, like this:

{
  name: 'get',
  args: ['$key']
}

When processed, the vertex will try to find a function by that name in the current object, replace any key references in the arguments list with the current key, and call the results.

You may also specify an iteration callback as the fourth parameter. This callback must be able to accept a value of the target type and return an appropriate iterable iterator for the target keys. If none is provided the vertex will try to create an iterator on it's own. This works well when the value's is an object property or array item. If the value is accessed through a function call it will take it's best guess by counting from 0 and returning those indices until it function in question returns undefined. In those cases, you may find it more effective to provide a custom iteration callback.

In addition to standard vertex functionality, value lookup vertices have a getValuePath function that returns the full path to the target value for a given key. This effectively converts a key to a property / accessor path. The flipside of that is the validateValuePath function that will read such a path at a given point and try to extract both the matching subpath and what key it uses.

You can pass these paths on to the library's expandNestedValuePath and collapseNestedValuePath functions. expandNestedValuePath takes a vertex and key list and tries to build the full property path. In contrast collapseNestedValuePath will take a vertex list and said full property path and try to extract the keys used to build that path. These are useful if you want to navigate into a value without vertex information (full property path) or store a shortened version of a value's location (key path).

Phased Traversals

As of version 1.1.0, depth first strategies support performing traversals with separate preorder and postorder callbacks. To do this simply call the strategy's startPhasedTraversal function like so:

const strategy = new DepthFirstSearch()
strategy.startPhasedTraversal(root, preOrderCallback, postOrderCallback, valueVertexFactory)

This is useful in cased where you want to do set some value on the way down the tree but need to clean it up on your way back up before the the next sibling branch is visited.