An observable tree data structure. An observable state tree is a normal nestable dictionary except that listeners can be bound to any subtree of the tree. (This has since moved to a repo https://github.com/mfbx9da4/observable-state-tree)

observable_state_tree.md

Observable State Tree

The below is a programming challenge I set myself on boxing day 2020. Give it a go! 🎄🦌

Problem Statement

Build an observable state tree.

An observable state tree is a normal object except that listeners can be bound to any subtree of the state tree.

Behaviour requirements:

1. Modifying a subtree will notify all parent listeners.
2. Modifying a sibling should not notify any siblings.
3. Modifying a parent only notifies the children listeners, if the children have also changed.

Examples of the above requirements are given below.

Examples and Proposed API

The below code should be viewed as pseudocode to demonstrate the usage of the data structure. You may wish to tweak the API to be more ergonomic or practical as you see fit.

const tree = createTree({ a: { b: { c: 1, d: 1 } } })
// the tree behaves like a normal object e.g
console.log(tree)
// prints the object 👉 { a: { b: { c : 1, d: 1 } } }

// we can setup listeners
const destroyRoot = listen(tree, (root) => console.log('root', root))
// on initial setup prints the full tree 👉 root { a: { b: { c: 1, d: 1 } } }
const destroyA = listen(tree.a, (a) => console.log('a', a))
// 👉 a { b: { c: 1 } }
const destroyB = listen(tree.a.b, (b) => console.log('b', b))
// 👉 b { c: 1 }
const destroyC = listen(tree.a.b.c, (c) => console.log('c', c))
// 👉 c 1
const destroyD = listen(tree.a.b.d, (d) => console.log('d', d))
// 👉 d 1

// should also support sending the prev value

destroyRoot()
// 👆 calling destroy, removes the listener

// 🙋‍♂️
// 1. Modifying a subtree will notify all parent listeners.
// 2. Modifying a sibling should not notify any siblings.
tree.a.b.c = 2
// 👉 a { b: { c: 2 } }
// 👉 b { c: 2 }
// 👉 c 2
// a, b and c are fired but sibling d is not fired

// 🙋‍♂️
// 3. Modifying a parent only notifies the children listeners, if the children have also changed.
tree.a = { ...tree.a }
// 👉 a { b: { c: 2 } }
// a is fired but b, c and d are not fired
tree.a = { e: 1 }
// 👉 a { e: 1 }
// 👉 b undefined
// 👉 c undefined
// 👉 d undefined
// b, c and d have been deleted so they should be notified with undefined

Implementation Sketch

Data structure will consist of two trees:

• State tree
• Listener tree

The state tree is a standard object which is nothing more than a nested javascript object. The listener tree is the tree of listeners.

Each node in the listener tree has:

• Children listeners
• Parent listeners
• Listener callbacks

Getting a particular path will just return that node of the state tree:

Setting a particular path with a value will:

• Update state tree
• Traverse parents and notify with new value
• Traverse listener children and notify with new value

Use proxies for dot notation.

Real World Applications

Later in react.js, could be used like so

const useStoreState = (selector) => {
  const [state, setState] = useState()
  useEffect(() => {
    const destroy = listen(selector, setState)
    return destroy
  })
  return state
}

Implementation

• Here is my implementation of the observable state tree.
• I couldn't quite get the above API but I came pretty close by using proxies.
• See the react example here.
• See the rudimentary unit tests here.

observableStateTree.ts

import { assert } from '../utils/assert'

export type Callback = (value: any, prevValue: any) => void

type DestroyCallback = () => void

interface ListenerNode {
  parent: Symbol | ListenerNode
  children: Record<string, ListenerNode>
  prevValue: any
  listeners: Callback[]
}

export interface StateTree {
  get: (path?: string[]) => any
  set: (path: string[], value: any) => void
  listen: (path: string[], callback: Callback) => DestroyCallback
}

export const createStateTree = (initial: any = {}): StateTree => {
  const root = Symbol()
  let stateTree: any = initial
  const listenerTree: ListenerNode = { parent: root, children: {}, listeners: [], prevValue: initial }

  const get = (path: string[] = []): any => {
    // returns the value directly from the state tree
    let node = stateTree
    for (const key of path) {
      node = node[key]
    }
    return node
  }

  const set = (path: string[] = [], value: any) => {
    assert(Array.isArray(path), 'path must be array', { path })

    if (!path.length) {
      // update the root
      stateTree = value
    }

    // update a deeply nested key
    let node = stateTree
    for (let i = 0; i < path.length; i++) {
      const key = path[i]
      if (i === path.length - 1) {
        node[key] = value
        break
      }
      let next = node[key]
      if (!next) {
        next = {}
        node[key] = next
      }
      node = next
    }

    // now notify listeners of the update
    return notify(path)
  }

  const listen = (path: string[], callback: Callback): DestroyCallback => {
    let node = listenerTree
    for (let i = 0; i < path.length; i++) {
      const key = path[i]
      let next = node.children[key]
      if (!next) {
        // auto create the listener tree
        next = { parent: node, children: {}, listeners: [], prevValue: undefined }
        node.children[key] = next
      }
      node = next
    }

    const value = get(path)
    node.prevValue = value
    node.listeners.push(callback)

    // notify this new listener inline for the first time
    callback(value, value)

    return () => {
      // tear down
      const i = node.listeners.findIndex((x) => x === callback)
      node.listeners.splice(i, 1)
    }
  }

  const notify = (path: string[]) => {
    let stateNode = stateTree
    let listenerNode = listenerTree
    const empty = {}

    // notify root listeners
    listenerNode.listeners.map((x) => x(stateNode, listenerNode.prevValue))

    for (let i = 0; i < path.length; i++) {
      // notify parents
      const key = path[i]
      stateNode = (stateNode || empty)[key]
      listenerNode = listenerNode.children[key]
      if (!listenerNode) break
      listenerNode.listeners.map((x) => x(stateNode, listenerNode.prevValue))
    }

    let queue: [ListenerNode, any][] = []
    if (listenerNode) {
      // notify children
      queue.push([listenerNode, stateNode])
      while (queue.length) {
        ;[listenerNode, stateNode] = queue.shift() as [ListenerNode, any]
        for (const key in listenerNode.children) {
          const child = listenerNode.children[key]
          const childValue = (stateNode || empty)[key]
          const { prevValue } = child
          if (childValue !== prevValue) {
            // skip notifying children which have not changed
            // for those that have, update prevValue and notify children
            child.prevValue = childValue
            child.listeners.map((x) => x(childValue, prevValue))
            queue.push([child, childValue])
          }
        }
      }
    }
  }

  return { set, get, listen }
}