The Context Tree Design Pattern

The Context Tree Design Pattern is broadly used in framework design and fascinatingly appears in seemingly unrelated applications implemented with many different strategies. As far as I can tell, this pattern does not yet have a name and so I made one up. C2 documents the Context Object and why it is bad, yet falls short of identifying the relationship to trees that push the pattern beyond a fancy bag of global variables.

Description and examples #

The Context Tree Design Pattern appears whenever there is some kind of tree (in the computer science sense) and ancestor nodes want to communicate state to all their transitive children. Such trees might be:

A function call tree.
A remote procedure call or multiple event invocation tree.
A user interface tree such as a DOM tree.
A transient render tree (such as found in React).

One common capability of setting context in a tree is the ability to shadow named context values that were specified by an ancestor with a different value for all children.

Example of a context tree with intermediate nodes shadowing a value

Applications #

Common application of context in such trees would be:

A reference to the current locale, HTTP request, or logger.
The window or other container a UI object is inside of.
Tracing of complex but strongly related computer system behavior that spans multiple events, processes, and/or machines.

Implementation strategies #

Explicit passing of context #

This might seem like the most naive implementation strategy: One simply passes a context object argument to the next child.

function example_function(context, arg1, arg2) {
  other_function(context, arg1);
  yet_another_function(context, 123);
}

This method leads to significant boilerplate and leaks the existence of context to every participant in the call tree. However, sometimes, such as when crossing system boundaries, this may be the only implementation option. Frameworks can hide this from user code through mechanisms that pass context via standardized headers or side channels for remote procedure calls.

Context stack #

In the simplest application of the Context Tree Design Pattern, the function call tree, the pattern is typically implemented using a stack. One pushes a value to store it, children read it by peeking at the top element of the stack, and then one pops the value when the calls to the children have completed. Interestingly, the Perl 5 programming language has native support for this pattern with the local keyword. Respectively, it becomes obvious that the Context Tree Design Pattern in a synchronous function call tree is the same concept as dynamic scoping.

var context_stack = new Stack();

function example_function() {
  context_stack.push("context value");
  child_function();
  context_stack.pop();
}

function child_function() {
  // Actually read the context.
  var context_value = context_stack.peek();
  // Shadow the value for a child.
  context_stack.push("override");
  nested_child_function();
  context_stack.pop();
}

Note, that user code would essentially never interact directly with this implementation. Instead they'd use higher level APIs that hide the implementation detail of the stack and ensure that pushes and pops are well paired.

This simple implementation, however, doesn’t work to more complex use cases of call trees, such as when they span threads, asynchronous invocations, or even physical machines; and the implementation strategy does not work for persistent trees such as DOM trees.

Thread local variables #

Thread local variables may act as the host for the stack described above. In a system where threads are dedicated to a single execution context such as a HTTP request, thread local variables are useful to provide context that is isolated to handling that request.

Hooking event loop entry points #

Event driven systems (such as Node.js) cannot use thread local variables as there may only be a single thread and even if there are more than one, they may be used across many logically separate computations.

A strategy to still get somewhat convenient context access in such a scenario is to change all points that represent the root of a call stack in an event loop invocation to properly restore context and to make each invocation that places work on the event loop store context such that it can be restored upon invocation.

Walking up the tree #

While function call trees do not typically allow inspection of the state of the caller (There are, of course, exceptions) this is very commonly possible in persistent trees such as the tree representing a user interface like a DOM tree. Nodes on the tree can walk up their parent nodes in reasonably efficient O(k depth of the tree) to find context provided to them.

// Visit parent elements of the start element and return the
// context value if they provide it.
function get_context(element, key) {
  do {
    // We assume for this example that every parent element
    // has a context map.
    if (element.context.has(key)) {
      return element.context.get(key);
    }
  } while ((element = element.parentElement));
  return undefined;
}

Using event propagation #

Another way to implement the same approach is to rely on event bubbling that is commonly natively supported in UI systems. Here the target nodes sends a custom event up the tree. Ancestors intercept the event, and if they can provide the desired context, they send it down to the target and stop propagation of the event.

Context in React-style frameworks #

Context is commonly found in React-style frameworks, but they tend to implement context in terms of the function call tree that underlies the render tree rather than the persistent UI tree.

Trace context #

Many software systems have invested in observability through tracing. As seen in the examples above, tracing is itself an application of the Context Tree Design Pattern. However, if one has a good tracing system, one can use (abuse) it to attach context to it that is unrelated to tracing.

function get_context(trace) {
  // We store context in a weak map keyed by
  // the current trace.
  return context_weak_map.get(trace);
}

An anti-pattern? #

The Context Tree Design Pattern can easily be misused and has a long range of failure modes:

Messy bag of quasi global variables #

The context may grow to a messy bag of quasi global variables.

Mitigation: Consider requiring an allow-list that requires engineering leadership approval for new values stored in context.

Action at a distance #

Context may create fragile, implicit, and undocumented dependencies between seemingly unrelated nodes in a tree.

Mitigation: Consider introducing a type-system that requires context consumers to be only callable by callers that provide that context or which require their callers to provide that context (Note: I’m not sure such a type system exists; it smells a bit like checked exceptions in Java but might still be a good idea).

Unexpected consumers #

Context may be read by unexpected consumers creating even more brittle dependencies.

Mitigation: Consider protecting the keys to read context to be protected by some kind of access control mechanism such as an allow-list.

Summary #

I find it fascinating that this pattern has found such a wide range of applications and is implemented through seemingly unrelated implementation strategies. I probably missed use cases, alternative implementations, and failure modes. Comments with additions or corrections are very welcome!

Published 23 May 2021