mavoweb / vastly

Everything you need to support a custom formula language

vᴀꜱᴛly

Everything you need to support a custom expression language in your application.

What is this?

vᴀꜱᴛly is a toolkit for handling expression ASTs (such as those produced by JSEP). These ASTs are a subset of ASTs produced by full-blown parsers like Esprima.

Intended to be used in conjunction with JSEP, but should work with any AST that conforms to the same structure.

Extracted from Mavo.

Features

• Zero dependencies
• Small footprint
• Works in Node and the browser
• Tree-shakeable

Usage

npm i vastly

Then you can use it either by importing the whole library:

import * as vastly from "vastly"; // or const vastly = require("vastly"); in CJS
import { parse } from "jsep";

const ast = parse("1 + x * y");
const result = vastly.evaluate(ast, {x: 2, y: 3});

or individual functions:

import { evaluate } from "vastly"; // or const { evaluate } = require("vastly"); in CJS
import { parse } from "jsep";

const ast = parse("1 + x * y");
const result = evaluate(ast, {x: 2, y: 3});

If you’re using vastly from a browser, without a bundler, fear not! You can just import from src directly:

import { evaluate } from "https://vastly.mavo.io/src/evaluate.js";
/* or */
import * as vastly from "https://vastly.mavo.io/src/index-fn.js";
/* or */
import { evaluate } from "https://vastly.mavo.io/dist/vastly.js";
/* or */
import * as vastly from "https://vastly.mavo.io/dist/vastly.js";

Full API reference

<script type=module> // Create global variable to facilitate experimentation import * as vastly from "./src/index.js"; globalThis.vastly = vastly; </script>

vastly's Issues

Function to easily switch from function call to method call?

A common type of manipulation is to transform fn(foo, bar) to foo.fn(bar) and vice versa. We'll also need it in mavoweb/mavo#1009

Would it make sense for vastly to expose a function that helps with this or should this be a Mavo util function?
Right now we don't have any modules that only work with specific node types. Do we want this to be a vastly design principle or are we fine with having more specialized helpers too?

`children` node type issue

Was working on writing test cases for extract, and came across an interesting bug. In walk, sometimes a node or parent will be an array instead of an object. The reason is because of this line where map is used instead of flatMap. Because of this, nested arrays can appear, and then propagate up to here. Finally, setAll calls walk here, where sometimes parent can end up being an array instead of an object.

example for expression if(starts(url, 'http'), 'external')

{
  node: '{"type":"Identifier","name":"starts"}',
  parent: `[{"type":"CallExpression","arguments":[{"type":"Identifier","name":"url"},{"type":"Literal","value":"http","raw":"'http'"}],"callee":{"type":"Identifier","name":"starts"}},{"type":"Literal","value":"external","raw":"'external'"}]`
}

`transformations` have no place in `serialize()`

While it can be convenient to apply transformations before serializing, it is ultimately orthogonal. Users shall be able to just call map() before serialize() if they want to apply such transformations (assuming map() works correctly, see #15 ).

I suggest we remove that part of the code to keep the functions small and atomic.

Need way to clear parents

As discovered in #43, we need a way to clear parents in addition to setting them

`map()` should not mutate the original AST

Analogously to array.map(), map() should not mutate the original AST. Instead, if no transformations are relevant, it should return a shallow clone of the node (so basically if no callback or if the callback doesn't return anything, it would be equivalent to a clone).

(Shallow because it would progressively become deep anyway, since the method is recursive, so doing deep cloning would be duplicate effort)

Need a function to reset a child property on a parent

#32 requires being able to take a child's parent and find which property on the parent matches the child, and then set that pointer to a new value

`parents.setAll()` should be `parents.update()`

"set" implies that we are providing a value, which is not the case.

Need a way to prepend a node with another node

As mentioned in Mavo #1003, we will need a general way to expand MemberExpressions by prepending, and maybe also appending.

Prepending would look something like:

ast = bar.baz;
ast.prepend(foo);
// ast is now foo.bar.baz

Should this function return void or return the new node without modifying the original? Or should it modify the original and return it? I'm not sure off the top of my head which would be most useful

Would having an append function be useful as well?

[docs] No docs for `serialize()`, which is listed as a namespace

https://vastly.mavo.io/docs/modules/serialize.html

It appears that serialize() becoming a namespace means it loses all the docs about itself. That appears to be a bug in typedoc.

Tasks:

• Investigate if there is a workaround (e.g. some way to explicitly specify that this is a function)
• Investigate whether the bug is already reported and report it if not https://github.com/TypeStrong/typedoc/issues?q=is%3Aissue+is%3Aopen+sort%3Aupdated-desc
  • Make sure you include a minimal testcase that reproduces the issue

`children` function that returns the nodes, properties, and indices

As a part of #46, we need to be able to not only find children but also find what their corresponding properties/indices are on their parents.

Define types

Currently the docs produced are not very helpful because all arguments are of type any. We should import JSEP's type for AST nodes and refer to that.

Not sure if we can do that in JSDoc or a .d.ts file. If the latter, can we reference the type from JSDoc? Something to look into!

Insertion is currently O(N) on the number of children and DX is poor

Writing this comment made me realize something: we currently only store the pointer to a node’s parent. This means that replacing a child node is nontrivial as looking up how we got from the parent to the child is nontrivial: we would need to try all possible child properties and compare. Even children() is no help here since it doesn't give us a pointer to each of these children, so we can replace them.

Potential solutions:

1. Instead of the parent, store a { node, property, index } (index only used for array properties) or { node, path } object that contains all the information we need to get from the parent to the child.
   • Pros
     • Insertion becomes O(1).
   • Cons:
     • This is a more complicated structure
     • Any existing code that uses node.parent would break (but then again, it shouldn't use that directly)
2. In addition to the current parent property, also store parent_property and parent_index properties.
   • Pros:
     • Maintains the simplicity of the current parent pointers
     • Insertion becomes O(1)
   • Cons:
     • Adds 3 properties to each node, which means they could get out of sync.
     • Makes it harder to use a WeakMap instead of node properties.
3. children() argument that returns a data structure that retains this info.
   • Pros:
     • Keeps the parent pointer simple
   • Cons:
     • Insertion still O(N) on the number of children
4. parents.pathTo(node) method to return {property, index} or [property, index]
   • Pros & Cons: Largely same as 3

`walk` should pass property and index into callback

We need to be able to access the property and index of a child relative to its parent from walk when building out #43

Currently, when walk calls its callback, it does it like so: callback(node, property, parent). Instead, I’m proposing we tweak it to be called like so: callback(node, {node: parent, property, index}). In addition to being more broadly useful, it would allow parents.setAll to call the new version of parents.set which requires knowledge of property and index

Documentation generation

Summary

Adding this as an issue to centralize the work for looking into generating documentation for vASTly. In summary, there are few options available for auto-generating documentation from JSDocs.

Option 1: TypeDoc

TypeDoc is primarily used to generate documentation for TypeScript projects, but it can still work with JS.

Pros

TypeDoc auto-generates a directory of HTML + CSS which together make up a fully-functioning docs site.

Cons

The only downside of this package is that since it was built for typescript files, you have to specify a small tsconfig.json to use it.

{
    "compilerOptions": {
        "allowJs": true,
    },
    "include": [
        "src/**/*.js"
    ]
}

Option 2: JSDoc

Pros

Was made for working with JavaScript specifically, so there are no issues with making JavaScript compatible with the generator.

Cons

The generated documentation doesn't look great, and only generated a syntax highlighted version of the whole file, which isn't helpful at all.

---

With all this in mind, and lack of really any other options, moving forward with TypeDoc is the best choice.

Variables not exported

There are variables, such as transformations inside of serialize.js that need to be able to be accessed, but are not able to be currently, due to the structure of index.js, which only exports the default exports of each file.

Augmenting AST with parent pointers

I pushed a two functions around setting pointers to parent nodes:

• parents.set() sets the parent on a specific node, to another provided node
• parents.setAll() walks an AST setting parent references recursively.

Both are in src/parents.js.

Right now they set regular properties on the nodes themselves, that are just non-enumerable. This maximizes the DX of reading the parent pointers, so it's a good way forwards if devs using vastly also want to read parents.
An alternative design would be to use a WeakMap to map objects to parents, and provide a parent.get() function to read it. This has the advantage that it does not mutate the AST nodes (and the DX is still not totally horrible).

By default they skip nodes that already have parent references (parents.setAll() skips the entire subtree under the node), so repeated use should be reasonably performant.

Now the question is, when to use these functions internally.
Parent pointers are necessary in a number of vastly functions.

• Some of these functions take an entire AST, so they can also call parents.setAll() on it (e.g. the function @adamjanicki2 is working on),
• However, others require it to have been called beforehand (e.g. closest()) and cannot do much otherwise.

Factors to consider

• Usability: Ideally we don't want our users to have to think about calling some separate function before they can use other functions, things should just work.
• If a function that is supposed to do something else also adds references, this breaks the principle of least surprise, and could make what seemed like a side effect free function into a function with (opaque) side effects. Most use cases would likely be fine with that, but there are some that would require objects to remain untouched. That can be mitigated if we use the alternative design discussed above.
• While the functions are designed to be reasonably performant, there is some overhead if every vastly function also sets parent nodes.
• As a design principle, these functions should be separate. It's entirely possible authors will use vastly without ever needing to call a function that requires parent references.

Options

(Not all mutually exclusive)

1. Every function also calls parents.setAll() on any node they get, to maximize the odds that the reference is available when needed.
   • Pros:
     • Things just work™
   • Cons:
     • …except when they don't. 😄 As with many good heuristics, this would work well in most cases, but it would be confusing to understand what happened when it doesn't.
     • Breaks modularization, functions doing more that they really need to
2. We could have a parse() function where authors can set a default parser as a parameter, and then it parses strings using that, and also sets parent references. They could either use parse() and have an AST that just works with every vastly function automatically, or use whatever other thing and then they need to do more work.
   • Pros:
     • in line with simple things being easy, and complex things being possible.
   • Cons:
     • Lack of flexibility
3. Every function that requires a parent reference, also accepts the whole AST as a separate parameter, so that parent references can be set as needed.
   • Pros:
     • Lean approach, nobody does more work than they need to
   • Cons:
     • Providing the whole AST may not always be possible (but it doesn't have to be an either or, this can be an optional parameter so it can be combined with other approaches)
4. We clearly document which functions require parent references to be set, and have users do it.
   • Pros:
     • No surprises
     • Maximum modularity
   • Cons:
     • Error-prone, easy to forget
     • Confusing to understand why some functions require this prep work

`transform()` for in-place mapping

We discussed this somewhere but never created an issue.

Transforming an AST in place can also be useful. I propose a transform() function for that.
map() could then be defined in terms of transform(), by using a callback that always returns a new object.

Note that transforming in place poses a few challenges to avoid infinite loops.

Make all function top level

An issue to keep track of moving all function to be top level like in Treecle.

Should we rename `parents` and `children` to `ancestors` and `descendants`?

Since they often go deeper than one level.

Drawback is that these are longer and more obscure names.

`warn` function to generate console warnings in dev enviroment

We want to add a function that uses console.warn to generate a warning message when in a dev environment

Overload `map()` (and `transform()` to support object literal for specifying the transformation

This occurred to me when reviewing #17

map() currently expects a callback, but the object literal syntax is a pretty convenient sugar for many use cases, and we could easily disambiguate between the two.

Same applies for transform() (see #20)

Switch to using WeakMaps for parent pointers

Once we fix #34 the amount of data we hang on the ASTs users provide increases quite a lot, and makes me wonder if we should switch to using a WeakMap to store these objects, rather than hang them on parent properties that are observable from userland.

Once we do that, then there’s no downside to just adding/adjusting parent pointers every time we touch an object, since it’s an operation with no side effects and if done right, the perf implications are tiny.

Can anyone thing of any downside with doing this? @adamjanicki2 @DmitrySharabin @karger?

`variables` nested member expression bug

I had a sneaking suspicion that something was off with the recently merged variables function with regards to how it handles member expressions, and looks like I was right. Specifically, expressions like foo[bar] don't get parsed correctly due to this line in the function:

const propertyChildren = property.type === "Identifier" ? [] : variables(property);

The issue with this approach is that these two expressions: foo.bar, foo[bar] have nearly identical node structures, except the computed property, which is true for foo[bar] (and generalizes to being true for any member expression that uses square brackets) and false for foo.bar (and generalizes to false for any member expression that uses dot notation).

The fix is easy; it only requires updating the bad line show above to the following line:

const propertyChildren = computed ? variables(property) : [];

The code will successfully explore the property if the member expression uses square brackets (and thus may contain other variables), and will not explore the property if it uses dot notation.

General `path` function

We need a generalized function that finds the path from an ancestor node to a descendant; it should return a list of properties (and or array indices) that lead from the given ancestor to the descendant.