Reading Code - GitHub Hotkey

After I read React’s code last month, I went on Twitter looking for recommendations about the next project to review here. There were some very interesting libraries mentioned and naturally many of them were related to React - design systems, hooks, and complex components.

But I’ve written so much about this library already, including one book, and I could use some variety. So when someone recommended GitHub’s Hotkey it immediately sparked my interest.

A small library that allows you to trigger actions on an element when a sequence of keys is pressed.

It works directly with the DOM, it’s small enough to be understood easily and it utilizes interesting data structures that you don’t see every day.

This was it.

Structure

Before we dive into the code we should take a stroll around the project and get a better feel for it. We should look for any known patterns and naming conventions that can help us out when we start reading the implementation.

With Hotkey, this doesn’t take a long time. The project has a standard structure with all its logic held in a src directory and a separate directory for tests and examples outside of it.

├── examples
|   └── ...
├── src
|   ├── index.ts
|   ├── radix-trie.ts
|   ├── hotkey.ts
|   └── utils.ts
├── tests
|   ├── test.js
|   └── test-radix-trie.js

The implementation is split into multiple files and at a glance, we learn that it most probably uses a data structure called a Radix Trie underneath. The utils.ts file is self-explanatory and the index and hotkey files probably contain the specific functionality for binding hotkeys to an event and exposing it.

This is an example of how even small projects benefit from a good file structure. Separation of concerns is not applicable only on the code level. We learned important details without even reading the code so far.

My only nitpick would be that tests are put in a separate folder. I consider co-location to be a better approach but in a library of this size browsing through another folder wouldn’t be problematic.

Following the Public API

Each time I’m browsing an unknown codebase, I start from one of its public APIs. We did that with React and React-Query and it lead to very good results. So we will employ the same approach here. Hotkey’s main export is the install function used to bind a key to an element.

import { install } from 'hotkey'

for (const el of document.querySelectorAll('[data-hotkey]')) {
  install(el)
}

Its short and concise, relying on abstractions to set up the event handlers and underlying data structures. I added comments directly in the example below so you won’t have to jump up and down.

export function install(element: HTMLElement, hotkey?: string): void {
  // Checks for an instance of the Radix Trie.
  // If it doesn't exist it means `install` is called for the first time.
  if (Object.keys(hotkeyRadixTrie.children).length === 0) {
    // Create a global event listener that checks if a hotkey is pressed on every keydown event.
    document.addEventListener('keydown', keyDownHandler)
  }

  // This function splits the passed hotkeys into a two-dimensional array.
  const hotkeys = expandHotkeyToEdges(
    // If a hotkey isn't passed to the function, look for one in the data attribute.
    hotkey || element.getAttribute('data-hotkey') || ''
  )

  // Add the keys to the Radix Trie
  const leaves = hotkeys.map((h) =>
    (hotkeyRadixTrie.insert(h) as Leaf<HTMLElement>).add(element)
  )

  // Store a reference to the element so we can remove the hotkeys for it if needed.
  elementsLeaves.set(element, leaves)
}

It’s a small function but there are many interesting details in it worth highlighting. There are also a few variables defined outside of it, on the root module level.

const hotkeyRadixTrie = new RadixTrie<HTMLElement>()
const elementsLeaves = new WeakMap<
  HTMLElement,
  Array<Leaf<HTMLElement>>
>()
let currentTriePosition: RadixTrie<HTMLElement> | Leaf<HTMLElement> =
  hotkeyRadixTrie
let resetTriePositionTimer: number | null = null
let path: string[] = []

These are the main variables used for the library to operate and their values need to be shared across multiple functions. The hotkeyRadixTrie holds the main reference to the data structure that provides lookup for the pressed keys, while the elementsLeaves holds references to all HTML elements with active hotkeys.

Another interesting design detail is that the install function accepts a hotkey parameter but allows you to specify it with the data-hotkey attribute directly on the element. The parameter may seem redundant if we have the attribute but it may come in handy if you don’t have control over the HTML itself.

It’s also worth noting the usage of the as keyword that tells the TypeScript compiler to consider the variable before it as a different value than the one it thinks it holds. You will notice it used in multiple places in Hotkey.

I would avoid using as unless absolutely necessary. In this case, I think an extra check to narrow down the type to Lead would’ve been better albeit lengthier.

What Happens When We Press a Key?

Undoubtedly, the most interesting bit of this library is how it tracks what key is pressed and what it should trigger. On each keydown event it needs to check if there’s a matching registered key action that has to be triggered.

As we saw in the first example, a global event handler is added the first time the install function is invoked. This is the handler in question - once again I’ll add comments in the implementation itself and strip some unnecessary details for the sake of brevity.

function keyDownHandler(event: KeyboardEvent) {
  // Guard clauses, short-circuiting the function execution.
  if (event.defaultPrevented) return
  if (!(event.target instanceof Node)) return
  if (isFormField(event.target)) {
    // ...
    return
  }

  // ...

  const newTriePosition = (
    currentTriePosition as RadixTrie<HTMLElement>
  ).get(eventToHotkeyString(event))

  if (!newTriePosition) {
    // If the user presses a hotkey that doesn't exist in the Trie,
    // they've pressed a wrong key-combo and the flow should be reset.
    resetTriePosition()
    return
  }

  // Store the current key sequence as an array
  path.push(eventToHotkeyString(event))

  currentTriePosition = newTriePosition

  // A Leaf represents a final key in a sequence.
  if (newTriePosition instanceof Leaf) {
    const target = event.target as HTMLElement
    let shouldFire = false
    let elementToFire
    // ...
    // Validate if an action should fire
    // ...

    if (elementToFire && shouldFire) {
      fireDeterminedAction(elementToFire, path)
      event.preventDefault()
    }

    // Reset the position in the trie
    resetTriePosition()
  }
}

At 40+ lines this is a lengthy function and upon reading it your initial reflex may be to split it. But length on its own is not the only factor that we should use to decide whether we should extract logic from a function or not.

A function should wrap a single logical operation and this is the case with this one. The only candidate for extraction in my mind is the logic inside the newTriePosition instanceof Leaf conditional statement which I’ve omitted for brevity.

Inside of it, we check whether an action should be fired and then continue to fire it. A good hint that this logic can be separated is the variable definitions at the beginning of the conditional block.

When you find yourself declaring multiple variables inside a conditional block, it means that you’re starting a new logical operation.

Another thing I want to emphasize is the sequence of guard clauses at the top of the function. These conditional statements check for common reasons not to execute the rest of the logic. I like that they’ve put them at a single level of indentation on the top.

The alternative would lead to more complex nested logic, nesting the implementation deeper and deeper.

function keyDownHandler(event: KeyboardEvent) {
  if (!event.defaultPrevented) {
    if (event.target instanceof Node) {
      if (!isFormField(event.target)) {
        // The rest of the implementation ...
      }
    }
  }
}

In the handler function, we once again find many uses of the as keyword. It also requires the usage of additional brackets which make the code just slightly harder to follow.

Personally, I’d rather have yet another check to narrow down the type.

What the rest of the function is doing is traversing this Trie data structure that we mentioned and checking if there’s a match in it based on the pressed keys. Then if we find one, we execute the actions stored for the current sequence.

On a high level, this is what the whole library is doing.

I’ve emphasized the importance of using proper data structures before and Hotkey is a perfect example of how using the right one can reduce the complexity of the codebase.

The Radix Trie

Knowledge of data structures and algorithms is often overlooked in front-end development because of the lack of necessity to use them. So far I haven’t had to use a Trie in production code, and in full honesty, I didn’t know what a Radix Trie was before I dove into this library.

But it’s the understanding of these structures that helps us identify opportunities to utilize them in the first place. So I got even more excited when I saw the Radix Trie sitting in the heart of this small utility library.

A Trie is a tree-like data structure most often used for efficient string searching. Each node in it represents a character in the string and they’re ordered in a top-down manner. When multiple strings share the same prefix, we only add the extra character as a leaf child node to the last letter of the prefix.

A Radix Trie is an optimized Trie in which each node that is an only child is merged with its parent. So in it, instead of having a node per character, you may have nodes representing entire prefixes or infixes. This behavior is a trade-off. It makes the implementation of the data structure more complex but it takes less space.

One of these structures’ applications is to retrieve autocomplete suggestions. When a user types in a few letters, finding the position in the trie shows you the possible search queries with this prefix.

In the context of Hotkey, though, the trie is used to store the key combinations.

// The `install` function
const leaves = hotkeys.map((h) =>
  (hotkeyRadixTrie.insert(h) as Leaf<HTMLElement>).add(element)
)

This line from the install function inserts the keys as an array. The Trie itself is implemented with a class and represents a recursive data structure in which each Trie can have more Tries nested in it.

export class RadixTrie<T> {
  parent: RadixTrie<T> | null = null
  children: { [key: string]: RadixTrie<T> | Leaf<T> } = {}

  constructor(trie?: RadixTrie<T>) {
    this.parent = trie || null
  }

  // ...

  insert(edges: string[]): RadixTrie<T> | Leaf<T> {
    let currentNode: RadixTrie<T> | Leaf<T> = this

    for (let i = 0; i < edges.length; i += 1) {
      // An edge represents a specific button i.e. Shift, Ctrl, g
      const edge = edges[i]

      // See if the Trie already has a child for this key
      let nextNode = currentNode.get(edge)

      // If this is the last key in this set
      if (i === edges.length - 1) {
        // If this end already exists as a RadixTrie, then replace with a Leaf:
        if (nextNode instanceof RadixTrie) {
          currentNode.delete(nextNode)
          nextNode = null
        }

        // If nextNode doesn't exist (or used to be a RadixTrie) then make a Leaf:
        if (!nextNode) {
          nextNode = new Leaf(currentNode)
          currentNode.children[edge] = nextNode
        }

        return nextNode
      } else {
        // If it's not the last key in the set but we've found a Leaf (an end node), replace it with a RadixTrie.
        if (nextNode instanceof Leaf) nextNode = null

        if (!nextNode) {
          nextNode = new RadixTrie(currentNode)
          currentNode.children[edge] = nextNode
        }
      }
      currentNode = nextNode
    }
    return currentNode
  }
}

It’s very rich of me to critique code written by GitHub engineers since they’re probably far more capable than I am. But at the same time, I can’t overlook how complex this method can be to read because of the nested loops and conditional statements.

The for loop could be replaced with either a .map or .forEach call allowing us to define the body of the function outside of the insert method. We increase the level of abstraction this way at the cost of less cognitive load.

But the loop aside, the way the conditionals are structured could be improved.

The else block at the bottom is much smaller than the main conditional block before it. We can invert the statements so we can deal with the else first and return early, leaving the most complex case at the bottom of the function and reducing its level of indentation.

It’s also worth expanding this short-hand conditional.

if (nextNode instanceof Leaf) nextNode = null

I put great value on consistency and even though this block holds only a single line it would be better to expand it like the others.

Not that we’ve put together the picture of how the Trie gets constructed, let’s examine how it gets traversed. Each time we press a key, the keyDownHandler function that we explored above gets triggered and it advances our position in the Trie.

const newTriePosition = (
  currentTriePosition as RadixTrie<HTMLElement>
).get(eventToHotkeyString(event))

The call to get returns either another RadixTrie or a Leaf depending on the combinations that we’ve stored. If it’s a RadixTrie, we should do nothing but wait for more keys to be pressed and advance further. But if it’s a Leaf then a full combination was pressed and we can run the appropriate action.

And if no match was found, then we reset the traversal.

const hotkeyRadixTrie = new RadixTrie<HTMLElement>()
// ...

function resetTriePosition() {
  // ...
  currentTriePosition = hotkeyRadixTrie
}

The resetTriePosition function resets the current position to the initial value, the root Trie. It’s also worth noting that even though this variable tracks a position, it doesn’t hold a key or an identifier. It’s a reference to the current Trie or sub-Trie that we’re traversing.