Lists And Trees

List

At its core, the list is a virtual rendering engine. Given a collection of elements, it will let you render those elements in a scrollable view, while making sure only the visible elements actually end up in the DOM, at any given point in time. Avoiding to render all the elements in the DOM a priori is the essence behind the list's performance. You can easily add 100k elements to it and not even break a sweat.

A requirement of virtual rendering is the need to know each element's height in pixels before it gets rendered. At runtime, the list will ask the height to a provided virtual rendering controller, keep an in-memory map of each element's height and track the viewport's position in order to know which elements should be rendered in and out of the DOM. Note that each item can have its own height: it's not a requirement that items should have all the same height.

Given that the collection model for a list is a simple array, the API to modify a list's element collection is very simple. The splice call allows for deleting and inserting continuous items in the list. Here's a simplified version of it:

class List<T> {
  splice(start: number, deleteCount: number, toInsert: T[]): void
}

List splice animation

Apart from being a virtual rendering engine, the List provides quite a lot of functionality that actually make it a usable widget: keyboard and mouse navigation, focus and selection traits, accessibility roles, etc. These features are what defines List as a usable widget across our workbench.

Index Tree

A tree UI widget should be able to represent tree-like data, eg. a file explorer. A rendered tree can always be rendered as a list; it is each row's indentation level and twistie indicators which give the user the perception of tree structure. By leveraging the virtual rendering functionalites of the list we can use composition to create a tree widget.

There is the question of API: how can we keep a tree-like structure API relatively simple, yet allow for complex operations, such as removing and inserting whole subtrees? If we take the same splice analogy as the list's (pick a location, remove some elements and add other elements), it's possible to come up with a tree splice call, in which the location is multi-dimensional (the first element of the start array represents the index in the root's children array; the n-th element of the start array represents the index in the n - 1-th children array) and the elements to insert are entire subtrees.

interface TreeElement<T> {
  element: T;
  children: TreeElement<T>[];
}

class IndexTree<T> {
  splice(start: number[], deleteCount: number, toInsert: TreeElement<T>[]): void;
}

The IndexTree's main responsibility is to map tree splice calls into list splice calls. It is a composition of the List widget in order to provide enough functionality to render tree-like models with the correct identation levels and twistie states per element. It also provides additional keyboard and mouse handling in order to support tree operations such as expand, collapse, select parent node, etc.

Additionally, the IndexTree supports filtering. An instance of IndexTree can be created with a filter which can have fine grained control of which elements should be filtered out of the view. The filter call can optionally return additional data computed during its operation, which will be passed along to the tree renderer; this is useful in cases where substring highlights are computed during the filtering phase and need to be reused during the rendering phase.

Object Tree

While the IndexTree is both powerful and performant, it also has a sub-optimal API. Often, it is not trivial to compute a start: number[] location to call splice with. It is a much more common scenario to simply replace complete subtrees by addressing an actual element. Given ES6 maps, we can provide just that:

class ObjectTree<T> {
  setChildren(element: T | null, children: TreeElement<T>[]): void;
}

The ObjectTree is a mapper between setChildren calls to tree splice calls. Again, it is a composition of the IndexTree widget and provides an API which easier to use since the user can always reference elements already in the tree. The null value is specially reserved to represent the root element.

Data Tree

There are certain use cases in which data models are not fully known: they are lazily discovered. A file explorer is a good example. Once in its initial state, a file explorer renders only the top-level files and folders. Once expanded, a folder should resolve its children by doing some IO and render its children once done. There is an obvious issue: what if the IO is slow?

interface IDataSource<T> {
  hasChildren(element: T | null): boolean;
  getChildren(element: T | null): Thenable<T[]>;
}

class DataTree<T> {
  constructor(dataSource: IDataSource<T>);
  refresh(element: T | null): Thenable<void>;
}

The DataTree abstracts away the user's model using a data source interface. Once again, it is nothing but a composition on top of the ObjectTree. Tree elements can be refreshed via API or by expanding for the very first time. Refreshing a tree element eventually calls the data source which returns a thenable of its children elements. It makes sure to correctly handle conflicting refresh calls (concurrent calls to refresh an ancestor and descendant are problematic) as well as render an appropriate loading indicator for long-running refresh calls, replacing the tree twistie. Once again, the null value represents the root.