loading...
Cover image for Linked lists in the wild: React Hooks

Linked lists in the wild: React Hooks

wuz profile image Conlin Durbin ・5 min read

I was digging into some of the code for React hooks the other day, right after reading Ali's great post on linked lists:

As I was diving in, I noticed that hooks are actually using linked lists under the hood. It's always cool to run across an implementation or use case of a data structure, so I thought I would share how and why they are being used, as far as I can tell.

The implementation

There is a comment in the hooks implementation that reads:

// Hooks are stored as a linked list on the fiber's memoizedState field. The
// current hook list is the list that belongs to the current fiber. The
// work-in-progress hook list is a new list that will be added to the
// work-in-progress fiber.

If you don't know what a fiber is, don't worry. They are basically a code representation of a unit of work in React. From the original Fiber github:

  • pause work and come back to it later.
  • assign priority to different types of work.
  • reuse previously completed work.
  • abort work if it's no longer needed.

Therefore, hooks are stored in a fiber's state. A fiber has a linked list of its current hooks. When something updates in React, the fiber creates a new work-in-progress hook list and appends it to the list.

Here is the implementation of Hooks from the React src (comments are from the code itself):

function createWorkInProgressHook(): Hook {
  if (workInProgressHook === null) {
    // This is the first hook in the list
    if (firstWorkInProgressHook === null) {
      isReRender = false;
      currentHook = firstCurrentHook;
      if (currentHook === null) {
        // This is a newly mounted hook
        workInProgressHook = createHook();
      } else {
        // Clone the current hook.
        workInProgressHook = cloneHook(currentHook);
      }
      firstWorkInProgressHook = workInProgressHook;
    } else {
      // There's already a work-in-progress. Reuse it.
      isReRender = true;
      currentHook = firstCurrentHook;
      workInProgressHook = firstWorkInProgressHook;
    }
  } else {
    if (workInProgressHook.next === null) {
      isReRender = false;
      let hook;
      if (currentHook === null) {
        // This is a newly mounted hook
        hook = createHook();
      } else {
        currentHook = currentHook.next;
        if (currentHook === null) {
          // This is a newly mounted hook
          hook = createHook();
        } else {
          // Clone the current hook.
          hook = cloneHook(currentHook);
        }
      }
      // Append to the end of the list
      workInProgressHook = workInProgressHook.next = hook;
    } else {
      // There's already a work-in-progress. Reuse it.
      isReRender = true;
      workInProgressHook = workInProgressHook.next;
      currentHook = currentHook !== null ? currentHook.next : null;
    }
  }
  return workInProgressHook;
}

Let's dive in to this just a little bit:

if (workInProgressHook === null) {

is checking to see if we have a current hook that is being used. workInProgressHook a global variable and is used like this:

workInProgressHook = createWorkInProgressHook();

So, if workInProgressHook is null, what do we want to do?

A null workInProgressHook means we aren't currently building a hook. That means we want to work with the current hook, not build the next hook in the list. There are two times we might want to do this - when we are building a new list and making the first element and on a re-render, when we are reloading an existing list. The next if statement shows us this (and the comments are even nice enough to tell us!):

// This is the first hook in the list
if (firstWorkInProgressHook === null) {
  isReRender = false;
  currentHook = firstCurrentHook;
  if (currentHook === null) {
    // This is a newly mounted hook
     workInProgressHook = createHook();
  } else {
    // Clone the current hook.
    workInProgressHook = cloneHook(currentHook);
  }
  firstWorkInProgressHook = workInProgressHook;
} else {
  // There's already a work-in-progress. Reuse it.
  isReRender = true;
  currentHook = firstCurrentHook;
  workInProgressHook = firstWorkInProgressHook;
}

If we don't have a firstWorkInProgressHook, we need to start building the linked list - which has yet another if statement. But, if we do have one, that means we are already creating a work-in-progress and the first current hook can just be copied!

The next if statement down:

if (currentHook === null) {
  // This is a newly mounted hook
   workInProgressHook = createHook();
} else {
  // Clone the current hook.
  workInProgressHook = cloneHook(currentHook);
}

Now we want to check if we have a current hook. If we don't we are creating a completely new list, which means we call createHook.

createHook just returns a object with a bunch of null set properties. The one we will be interested in the next property.

Otherwise, this is a list that we have already rendered once. React saves some performance by just cloning the hook and moving on, that way it doesn't have to re-create a hook every time this function is called.

So now we have our first hook! We set our firstWorkInProgressHook to the new one we just made!

firstWorkInProgressHook = workInProgressHook;

Now, what happens when we call createWorkInProgressHook again?

function createWorkInProgressHook(): Hook {
  if (workInProgressHook === null) {
    // ...
  } else {
    // what happens here?
  }
  return workInProgressHook;
}

Let's look!

Now that workInProgressHook isn't null, we need to check if it has a next hook -

if (workInProgressHook.next === null) {

If there isn't one, we should create a new hook and append it to the list, which is exactly what happens:

isReRender = false;
let hook;
if (currentHook === null) {
  // This is a newly mounted hook
  hook = createHook();
} else {
  currentHook = currentHook.next;
  if (currentHook === null) {
    // This is a newly mounted hook
    hook = createHook();
  } else {
    // Clone the current hook.
    hook = cloneHook(currentHook);
  }
}
// Append to the end of the list
workInProgressHook = workInProgressHook.next = hook;

So, again we check if there is a current hook to clone (this time checking to see if the next hook exists, since that let's us know if this hook has been created before). If there is, we clone it, if not we create a new one.

Then we call this magic line:

workInProgressHook = workInProgressHook.next = hook;

Which takes our newly created hook, sets it to the next hook for the current one and then sets the current one equal to the new one. This is basically equivalent to this:

workInProgressHook.next = hook;
workInProgressHook = hook;

Finally, if we do already have a work-in-progress hook, we are rerender, and want to do much the same thing we did the first time:

} else {
  // There's already a work-in-progress. Reuse it.
  isReRender = true;
  workInProgressHook = workInProgressHook.next;
  currentHook = currentHook !== null ? currentHook.next : null;
}

The only difference here is we need to update the currentHook to be the next hook before moving one, which is done with that ternary on the last line.

We've created a linked list using some global variables and a a function! That's pretty cool!

This honestly might be the first time I've seen a linked list used in actual code! Hopefully, this post made sense! Please let me know if there are any questions!

Posted on by:

wuz profile

Conlin Durbin

@wuz

Software Engineer at @HackerRank πŸ’» Working on http://stdio.app βš’οΈ writing at http://dev.to/wuz ⌨️ art+community+tech πŸ‘ΎπŸŽ¨πŸ˜ http://pronoun.is/he

Discussion

markdown guide
 

Seeing (what I thought only academic in nature) Linked List, used in React sounds great. It definitely helps on understanding "how" the fiber was implemented (as you also mentioned "why" in the Fiber documentation link).

I've also run into another place in React source, where they heavily utilizes Linked List.

React-cache is a reference implementation of upcoming data fetch feature.
The underlying implementation uses LRU (Least Recently Used) cache, which uses linked list to track cached resources.

 

Ooh! That one is a circular doubly-linked list, which is really cool!

 

I honestly still haven't been able to figure the whole code out yet πŸ˜…

Maybe I can do another one of these! I haven't read it yet though! Looks complicated!

Looking forward to your next post πŸ™‚. Thank you :p

 

Thanks for this post, Conlin. I've a question, maybe a naive one. Am trying to reason about why Hooks need a Linked list implementation. One usecase (useCase? ;)) it definitely seems to facilitate is, share state of one Hook to another. Curious to hear your thought process on this.

 

Maybe also to run all the effects one after another.

 

Ignore this naive question. I think, I figured out. Linked List allows React to rely on the order of Hooks calls which means, it could preserve state between re-renders.

 

I think this attribute can be tried to be learnt as first learner of programming. However, what should I do to start it ? Should I follow and try to understand the code or what ?

 

Definitely check out Ali's post on Linked Lists: dev.to/aspittel/thank-u-next-an-in...

Hopefully this article isn't too difficult if you have some understanding of Javascript. I'd be happy to explain anything you find confusing!

 
 
 

What language is that? Doesn't it have a list type with append, delete, and insert methodss

You don't wwant to have to mess with null pointers and memory allocation, unless you really need to.