§ Quick Take

import { strict as assert } from "assert";
import { find } from "ast-monkey";

assert.deepEqual(
  find(
    {
      a1: {
        b1: "c1",
      },
      a2: {
        b2: "c2",
      },
      z1: {
        x1: "y1",
      },
    },
    { key: "a*" }
  ),
  [
    {
      index: 1,
      key: "a1",
      val: {
        b1: "c1",
      },
      path: [1],
    },
    {
      index: 3,
      key: "a2",
      val: {
        b2: "c2",
      },
      path: [3],
    },
  ]
);

§ Context

A single HTML tag <td>a</td> can be parsed into an AST (see the playground opens in a new tab):

[
{
"type": "tag",
"name": "td",
"attribs": {},
"children": [
{
"data": "a",
"type": "text",
"next": null,
"startIndex": 4,
"prev": null,
"parent": "[Circular ~.0]",
"endIndex": 5
}
],
"next": null,
"startIndex": 0,
"prev": null,
"parent": null,
"endIndex": 10
}
]

ast-monkey performs operations on such nested arrays and objects like the one above.

§ The challenge

Operations on AST's — Abstract Syntax Trees — or anything deeply nested are difficult. The main problem is going "up the branch": querying the parent and sibling nodes.

Second problem, AST's get VERY BIG very quickly. A single tag, <td>a</td>, 10 characters produced 398 characters of AST above.

The first problem, the "Going up", is often solved by putting circular references in the parsed tree, notice "parent": "[Circular ~.0]", in the tree above. This way, you can query .parent like tag.nestedTag.parent[2]. Problem is, a) it's not standard JSON, you can't even JSON.stringify (specialised stringification packages do exist); b) so what that you "dipped" to some branch and went back up — it's only a tactical move and nothing strategical.

This program goes another way, it uses indexing and "breadcrumb" paths. For example, you traverse and find that node you want is index 58, whole path being [2, 14, 16, 58]. You save the path down. After the traversal is done, you fetch the monkey to delete the bloody index 58. You can also use a for loop on breadcrumb index array, [2, 14, 16, 58] and fetch and check parent 16 and grandparent 14. Lots of possibilities. Method .find() searches using key or value or both, and method .get() searches using a known index. That's the strategy.

By the way, the second problem, the AST size challenge, is something we have to live with. Parsers that don't use circular paths produce smaller trees. From practice, it's handy to evaluate AST's visually, using GUI applications, such as https://astexplorer.net/

§ Idea

Conceptually, we use two systems to fetch paths:

  1. Our unique, number-based indexing system — each encountered node is numbered, for example, 58 (along with "breadcrumb" path, an array of integers, for example, [2, 14, 16, 58]). If you know the number you can get monkey to fetch you the node at that number.
  2. object-path opens in a new tab notation, as in foo.1.bar (instead of foo[1].bar). The dot marking system is also powerful, it is used in many our programs, althouh it has some shortcomings (no dots in key names opens in a new tab, for example).

Traversal function will report both ways.

§ API

§ .find()

Method find() can search objects by key or by value or by both and return the indexes path to an each finding.

Input

Input argumentTypeObligatory?Description
inputWhateveryesAST tree, or object or array or whatever. Can be deeply-nested.
optionsObjectyesOptions object. See below.
Options object's keyTypeObligatory?Description
keyStringat least one, key or valIf you want to search by a plain object's key, put it here.
valWhateverat least one, key or valIf you want to search by a plain object's value, put it here.
onlyStringno (if not given, will default to any)You can specify, to find only within arrays, objects or any. any is default and will be set if opts.only is not given.

Either opts.key or opts.val or both must be present. If both are missing, ast-monkey will throw an error.

opts.only is validated via dedicated package, util-array-object-or-both. Here are the permitted values for opts.only, case-insensitive:

Either typeInterpreted as array-typeInterpreted as object-type
anyarrayobject
allarraysobjects
everythingarrobj
botharayob
eitherarro
eacha
whatever
e

If opts.only is set to any string longer than zero characters and is not case-insensitively equal to one of the above, the ast-monkey will throw an error.

Output

The output will be an array, comprising of zero or more plain objects in the following format:

Object's keyTypeDescription
indexInteger numberThe index of the finding. It's also the last element of the path array.
keyStringThe found object's key
valWhatever or nullThe found object's value (or null if it's a key of an array)
pathArrayThe found object's path: indexes of all its parents, starting from the topmost. The found key/value pair's address will be the last element of the path array.

If a finding is an element of an array, the val will be set to null.

Use example

Find out, what is the path to the key that equals 'b'.

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
const input = ["a", [["b"], "c"]];
const key = "b";
const result = find(input, { key: key });
console.log("result = " + JSON.stringify(result, null, 4));
// => [
// {
// index: 4,
// key: 'b',
// val: null,
// path: [2, 3, 4]
// }
// ]

Once you know that the path is [2, 3, 4], you can iterate its parents, get()-ing indexes number 3 and 2 and perform operations on it. The last element in the findings array is the finding itself.

This method is the most versatile of the ast-monkey because you can go "up the AST tree" by querying its array elements backwards.

§ .get()

Use method get() to query AST trees by branch's index (a numeric id). You would get that index from a previously performed find() or you can pick a number manually.

Practically, get() is typically used on each element of the findings array (which you would get after performing find()). Then, depending on your needs, you would write the particular index over using set() or delete it using drop().

Input

Input argumentTypeObligatory?Description
inputWhateveryesAST tree, or object or array or whatever. Can be deeply-nested.
optionsObjectyesOptions object. See below.
Options objectTypeObligatory?Description
indexNumber or number-as-stringyesIndex number of piece of AST you want the monkey to retrieve for you.

Output

The get() returns object, array or null, depending what index was matched (or not).

Use example

If you know that you want an index number two, you can query it using get():

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
const input = {
a: {
b: "c",
},
};
const index = 2;
const result = get(input, { index: index });
console.log("result = " + JSON.stringify(result, null, 4));
// => {
// b: 'c'
// }

In practice, you would query a list of indexes programmatically using a for loop.

§ .set()

Use method set() to overwrite a piece of an AST when you know its index.

Input

Input argumentTypeObligatory?Description
inputWhateveryesAST tree, or object or array or whatever. Can be deeply-nested.
optionsObjectyesOptions object. See below.
Options objectTypeObligatory?Description
indexNumber or number-as-stringyesIndex of the piece of AST to find and replace
valWhateveryesValue to replace the found piece of AST with

Output

OutputTypeDescription
inputSame as inputThe amended input

Use example

Let's say you identified the index of a piece of AST you want to write over:

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
const input = {
a: { b: [{ c: { d: "e" } }] },
f: { g: ["h"] },
};
const index = "7";
const val = "zzz";
const result = set(input, { index: index, val: val });
console.log("result = " + JSON.stringify(result, null, 4));
// => {
// a: {b: [{c: {d: 'e'}}]},
// f: {g: 'zzz'}
// }

§ .drop()

Use method drop() to delete a piece of an AST with a known index.

Input

Input argumentTypeObligatory?Description
inputWhateveryesAST tree, or object or array or whatever. Can be deeply-nested.
optionsObjectyesOptions object. See below.
Options object's keyTypeObligatory?Description
indexNumber or number-as-stringyesIndex number of piece of AST you want the monkey to delete for you.

Output

OutputTypeDescription
inputSame as inputThe amended input

Use example

Let's say you want to delete the piece of AST with an index number 8. That's 'h':

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
const input = {
a: { b: [{ c: { d: "e" } }] },
f: { g: ["h"] },
};
const index = "8"; // can be integer as well
const result = drop(input, { index: index });
console.log("result = " + JSON.stringify(result, null, 4));
// => {
// a: {b: [{c: {d: 'e'}}]},
// f: {g: []}
// }

§ .del()

Use method del() to delete all chosen key/value pairs from all objects found within an AST, or all chosen elements from all arrays.

Input

Input argumentTypeObligatory?Description
inputWhateveryesAST tree, or object or array or whatever. Can be deeply-nested.
optionsObjectyesOptions object. See below.
Options object's keyTypeObligatory?Description
keyStringat least one, key or valAll keys in objects or elements in arrays will be selected for deletion
valWhateverat least one, key or valAll object key/value pairs having this value will be selected for deletion
onlyStringno (if not given, will default to any)You can specify, to delete key/value pairs (if object) or elements (if array) by setting this key's value to one of the acceptable values from the table below.

If you set only key, any value will be deleted as long as key matches. Same with specifying only val. If you specify both, both will have to match; otherwise, key/value pair (in objects) will not be deleted. Since arrays won't have any values, no elements in arrays will be deleted if you set both key and val.

opts.only values are validated via dedicated package, util-array-object-or-both. Here are the permitted values for opts.only, case-insensitive:

Either typeInterpreted as array-typeInterpreted as object-type
anyarrayobject
allarraysobjects
everythingarrobj
botharayob
eitherarro
eacha
whatever
e

If opts.only is set to any string longer than zero characters and is not case-insensitively equal to one of the above, the ast-monkey will throw an error.

Output

OutputTypeDescription
inputSame as inputThe amended input

Use example

Let's say you want to delete all key/value pairs from objects that have a key equal to 'c'. Value does not matter.

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
const input = {
a: { b: [{ c: { d: "e" } }] },
c: { d: ["h"] },
};
const key = "c";
const result = del(input, { key: key });
console.log("result = " + JSON.stringify(result, null, 4));
// => {
// a: {b: [{}]}
// }

§ .arrayFirstOnly()

(ex-flatten() on versions v.<3)

arrayFirstOnly() will take an input (whatever), if it's traversable, it will traverse it, leaving only the first element within each array it encounters.

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
const input = [
{
a: "a",
},
{
b: "b",
},
];
const result = arrayFirstOnly(input);
console.log("result = " + JSON.stringify(result, null, 4));
// => [
// {
// a: 'a'
// }
// ]

In practice, it's handy when you want to simplify the data objects. For example, all our email templates have content separated from the template layout. Content sits in index.json file. For dev purposes, we want to show, let's say two products in the shopping basket listing. However, in a production build, we want to have only one item, but have it sprinkled with back-end code (loop logic and so on). This means, we have to take data object meant for a dev build, and flatten all arrays in the data, so they contain only the first element. ast-monkey comes to help.

Input

Input argumentTypeObligatory?Description
inputWhateveryesAST tree, or object or array or whatever. Can be deeply-nested.

Output

OutputTypeDescription
inputSame as inputThe amended input

§ .traverse()

traverse() comes from a standalone library, ast-monkey-traverse and you can install and use it as a standalone. Since all methods depend on it, we are exporting it along all other methods. However, it "comes from outside", it's not part of this package's code and the true source of its API is on its own readme. Here, we're just reiterating how to use it.

traverse() is an inner method used by other functions. It does the actual traversal of the AST tree (or whatever input you gave, from simplest string to most complex spaghetti of nested arrays and plain objects). This ~method~ function is used via a callback function, similarly to Array.forEach().

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
let ast = [{ a: "a", b: "b" }];
ast = traverse(ast, function (key, val, innerObj) {
// use key, val, innerObj
return val !== undefined ? val : key; // (point #1)
});

Also, we like to use it this way:

const {
find,
get,
set,
drop,
del,
arrayFirstOnly,
traverse,
} = require("ast-monkey");
let ast = [{ a: "a", b: "b" }];
ast = traverse(ast, function (key, val, innerObj) {
let current = val !== undefined ? val : key;
// All action with variable `current` goes here.
// It's the same name for any array element or any object key's value.
return current; // it's obligatory to return it, unless you want to assign that
// node to undefined
});

It's very important to return the value on the callback function (point marked #1 above) because otherwise whatever you return will be written over the current AST piece being iterated.

If you definitely want to delete, return NaN.

§ innerObj in the callback

When you call traverse() like this:

input = traverse(input, function (key, val, innerObj) {
...
})

you get three variables:

  • key
  • val
  • innerObj

If monkey is currently traversing a plain object, going each key/value pair, key will be the object's current key and val will be the value. If monkey is currently traversing an array, going through all elements, a key will be the current element and val will be null.

innerObj object's keyTypeDescription
depthInteger numberZero is root, topmost level. Every level deeper increments depth by 1.
pathStringThe path to the current value. The path uses exactly the same notation as the popular object-path opens in a new tab package. For example, a.1.b would be: input object's key a > value is array, take 1st index (second element in a row, since indexes start from zero) > value is object, take it's key b.
topmostKeyStringWhen you are very deep, this is the topmost parent's key.
parentType of the parent of current element being traversedA whole parent (array or a plain object) which contains the current element. Its purpose is to allow you to query the siblings of the current element.

§ The name of this library

HTML is parsed into nested objects and arrays which are called Abstract Syntax Trees. This library can go up and down the trees, so what's a better name than monkey? The ast-monkey. Anything-nested is can also be considered a tree – tree of plain objects, arrays and strings, for example. Monkey can traverse anything really.

§ Licence

MIT opens in a new tab

Copyright © 2010–2020 Roy Revelt and other contributors

Related packages:

📦 ast-monkey-traverse 1.12.20
Utility library to traverse AST
📦 ast-monkey-util 1.1.11
Utility library of AST helper functions
📦 json-comb-core 6.6.34
The inner core of json-comb
📦 json-variables 8.2.18
Resolves custom-marked, cross-referenced paths in parsed JSON
📦 object-merge-advanced 10.11.29
Recursive, deep merge of anything (objects, arrays, strings or nested thereof), which weighs contents by type hierarchy to ensure the maximum content is retained
📦 ast-deep-contains 1.1.21
Like t.same assert on array of objects, where element order doesn't matter.
📦 ast-get-values-by-key 2.7.0
Read or edit parsed HTML (or AST in general)