The AsyncTree
interface is a simple and flexible way to represent a wide variety of data types as trees. It defines an asynchronous dictionary, essentially a minimalist async
JavaScript Map, that can be nested to create trees.
Async trees
An async tree is a collection of nodes which are key/value dictionaries, also known as an associative array.
- You can ask an async tree node for its keys.
- With a key, you can ask a node to give you the corresponding value associated with that key.
- The value may be another node in the tree, or the value may be any other type of JavaScript data.
- The set of keys you get back may not be complete. That is, the node may have keys that it can handle that it chooses not to return in the set of keys it will give you.
- The node may (or may not) allow you set the value associated with a given key.
- All these node operations — obtaining its keys, getting the value for a given key, and optionally setting the value for a given key — may be asynchronous.
Such a construct is sufficiently flexible to encompass many types of data.
AsyncTree interface definition
JavaScript does not have a first-class representation of interfaces, but a tree node supporting the AsyncTree
interface looks like this:
const tree = {
// Get the value of a given key.
async get(key) { ... }
// Iterate over this tree node's keys.
async keys() { ... }
// Optional: set the value of a given key.
async set(key, value) { ... }
}
Some notes on the JavaScript shown above:
The
keys
method must return an iterator. An iterator is an object that can produce a sequence of values. A tree’skeys
method can return an instance of a JavaScript class likeArray
andSet
that support the iterator protocol, orkeys
can return an iterator defined by other means.Both functions in the
AsyncTree
interface are marked with the async keyword, indicating that they are asynchronous functions. In practice, the functions may return immediately, but they have the potential, at least, to do work that will require a bit of time: retrieving data from the file system, accessing data from a network, or performing long calculations.The
keys
method does not have to return all the keys supported byget
! There may be keys thatget
can handle that thekeys
will not include. This turns out to be useful in a number of situations.An async tree’s
get
method is expected to returnundefined
if the key is not present in the tree.
In TypeScript, the interface looks roughly like:
interface AsyncTree {
get(key: any): Promise<any>;
keys(): Promise<IterableIterator<any>>;
set?(key: any, value: any): Promise<this>;
}
Representing a simple tree
Suppose we want to represent the small tree used in the introduction to the ori command-line tool:
The small circle on the left is a tree node with three keys (“Alice”, “Bob”, “Carol”) that correspond to three values (“Hello, Alice”, etc.). This can be represented in the AsyncTree
interface as:
const tree = {
// Get the value of a given key.
async get(key) {
return `Hello, ${key}.`;
},
// Return this tree node's keys.
async keys() {
return ["Alice", "Bob", "Carol"];
},
};
Traversing an async tree
If we wish to display the keys and values in the above tree, we can write:
// Display a tree.
// Loop over the tree's keys.
for (const key of await tree.keys()) {
// For a given key, get the value associated with it.
const value = await tree.get(key);
// Display the key and value.
console.log(`${key}: ${value}`);
}
This produces the output:
Alice: Hello, Alice.
Bob: Hello, Bob.
Carol: Hello, Carol.
Trailing slash convention
Async trees can be deep, meaning that values in the tree may themselves be subtrees.
Deep async trees with string keys have the option of following the trailing slash convention: if a key represents a subtree, the key can end in a trailing slash, like subfolder/
in the following tree.
The specifics of the convention are:
- If a trailing slash is present, then the value is definitely a traversable subtree.
- If a trailing slash is not present, the value may or may not be a subtree. That is, a tree isn’t obligated to append slashes to any or all of its keys for traversable subtrees.
Trailing slashes have several purposes:
First, they are useful to someone looking at a list of keys. If you get the keys of a folder, for example:
$ ori @keys myProject
- README.md
- src/
- test/
The trailing slashes let you know that src/
and test/
represent subfolders.
Second, a trailing slash is used as a signal by certain trees to save work. This is important for trees like SiteTree, which must make potentially slow network requests to get()
values. The trailing slash is an important indication that they can traverse into a subtree value without making a network request.
If the tree depicted above is a SiteTree
, a call to get("subfolder")
will make a network request, but a call to get("subfolder/")
will not. The latter call will just return a new SiteTree
instance for the indicated location. Only when a SiteTree
is asked to get
a key that doesn’t end in a slash — or to return its keys
— will the tree be forced to make a network request.
Other trees like ObjectTree can return a value quickly so they ignore trailing slashes. If the above tree represents an ObjectTree
, then get("a")
and get("a/")
return the same value (even though “a” is not a subtree). Likewise, get("subfolder")
and get("subfolder/")
would behave the same.
Third, tools can look at a trailing slash to infer intent. The Origami language interprets the presence of a trailing slash to indicate that you’re expecting to get back a traversable subtree. If the value you’re working with is a file, Origami implicitly unpacks the file into data. For example, the expression data.json
returns the raw file contents of the indicated file, but data.json/
(with a trailing slash) parses the JSON in the file and returns the data object.
Origami also includes a set of @slash functions for working with trailing slashes.
Wrappers
Instead of directly defining a class or object that implements the AsyncTree
interface, you can make use of various wrappers that will turn something into an async tree version:
- FileTree can wrap a file system folder
- FunctionTree can wrap a JavaScript function and an optional domain
- MapTree can wrap a JavaScript
Map
- ObjectTree can wrap a plain JavaScript object or array
- SetTree can wrap a JavaScript
Set
- SiteTree can wrap a web site