Immutable Data from Scratch

In Flux from Scratch and React from Scratch we built up simple systems to handle both our data layer and interface rendering. Note: You should probably check out those first to get some context if you haven’t already.

So, we’re done right? Turns out there’s one more cool piece to this puzzle.

One of the nicest things about our declarative interface and unidirectional dataflow is how much easier it is to reason about the code. I’ve returned to experimental projects weeks or months later and just jumped right back in and kept going.

But there’s a downside, and that is inefficiency. In our naive React.js implementation we’re touching the DOM as little as possible, but we still walk the entire tree of our components every time pretty much anything happens to our data. This can result in a lot of wasted renders (where we re-ran the render function but didn’t have any changes to make to the real DOM).

We can go a very long way to mitigating this by using immutable data in our data layer. Instead of just blindly re-rendering the entire component tree we can skip certain components that only use data that has not changed.

The problem is that in order to do this, we need a reliable way to know when something has or hasn’t changed.

Take this very simple code for instance:

var todos = {
  0: { title: 'Feed cat', completed: true },
  1: { title: 'Pet cat', completed: false },
  2: { title: 'Talk to cat', completed: true }
}
todos[1].completed = true

In order to decide not to render the entire todo list again, we need to compare the todos object with one we rendered last time. But we need to walk it’s entire hierarchy to figure this out. This is called ‘dirty checking’ and it can get very slow if your data gets large (which it probably will).

So instead we want to update any nested value in the object and have the identity of the object change. Then we can simply see if a specific todo/etc is the same exact todo object or not, and not actually care about the values inside.

If that sounds complicated, not to worry there are lots of options out there already to help us with this.

Immutable Data Options

Flux is just an idea, and React.js is the most prominent ‘Virtual DOM’ and declarative UI option so those were easy choices. But immutable data is a very old concept with a lot more history. Here are some great options for making use of immutable data in your app:

React Immutability Helpers

This approach is a bit dated now (well, dated by a few weeks anyway :)) and is slated to be removed from React and put in its own repository. It implements a MongoDB-like update syntax that operates on plain JavaScript objects. For example:

var collection = { x: [ 1, 2, { a: [ 3, 4, 5 ] } }
var newCollection = React.addons.update(
  collection,
  { x: [ 2: { a: { $push: 6 } } ] }
)
// => { x: [ 1, 2, { a: [ 3, 4, 5, 6 ] } }

seamless-immutable

This little library pretty much sticks to using built-in JavaScript objects/arrays. It ‘freezes’ and modifies some of their behaviour to make them immutable rather than introducing new classes.

Baobab

Baobab uses a ‘cursor’ pattern where instead of modifying your objects you update a cursor that points at the part you want to update. For example, from the docs:

var tree = new Baobab( {
  palette: {
    colors: [ 'yellow', 'purple' ],
    name: 'Glorious colors'
  }
} )

var colorsCursor = tree.select( 'palette', 'colors' )
colorsCursor.push('orange')

mori

The ‘classic’ JavaScript immutable data library based on Clojure’s persistent data structures.

Immutable.js

A relatively new addition from Facebook made with React/Flux in mind. Here we have special objects created to be immutable like Immutable.Map, Immutable.List, etc.

From Scratch?

Let’s do it! I decided on a simple approach taking ideas from both seamless-immutable and Reacts.addons.update.

The first thing we want is a way to make our objects immutable.

function immutable( obj ) {
  // already immutable!
  if( obj && obj.hasOwnProperty('__immutable') ) {
    return obj
  }

  var newObj

  if( Array.isArray( obj ) ) {
    newObj = []

    // first make all elements immutable
    for( var i in obj ) {
      newObj[i] = immutable( obj[i] )
    }

    // then disable all mutating methods of the array itself
    var unsafe = [ 'push', 'pop', 'sort', 'splice',
                   'shift', 'unshift', 'reverse' ]
    var fail = function() {
      throw new Error('Cannot modify immutable object')
    }
    unsafe.forEach( function( fn ) {
      Object.defineProperty( newObj, fn, { value: fail } )
    } )
  }
  else if( obj && typeof( obj ) == 'object' ) {
    // make all values in the object immutable
    newObj = {}
    for( var i in obj ) {
      newObj[i] = immutable( obj[i] )
    }
  }
  else {
    // primitive
    return obj
  }

  // add 'already immutable' property
  Object.defineProperty( newObj, '__immutable', { /*defaults*/ } )
  // prevent any more edits of any kind
  return Object.freeze( newObj )
}

This function recursively makes objects and arrays immutable by redefining mutation functions and freezing it to throw an error on any update attempt. It also works idempotently by adding an __immutable property so we only ‘process’ it once.

Next, a way to update those objects with new values.

function update( obj, updates ) {
  // commands we know how to perform
  var COMMANDS = [
    '$push', '$unshift', '$splice',
    '$merge', '$set', '$unset'
  ]

  // check if we're attempting a command right now
  // passing more than one command is not allowed
  // and the last one will simply be taken!
  var command, changes
  Object.keys( updates ).forEach( function( cmd ) {
    if( COMMANDS.indexOf(cmd) != -1 ) {
      command = cmd
      changes = updates[command]
    }
  } )

  // prepare the new object
  // shallow copy suffices here due to each
  // nested object being handled recursively
  // (each will be shallow copied)
  var next
  if( Array.isArray( obj ) ) {
    next = [].concat(obj)
  }
  else if( obj && typeof(obj) == 'object' ) {
    next = {}
    for( var k in obj ) { newA[k] = obj[k] }
  }
  else {
    next = obj
  }

  if( command ) {
    switch( command ) {
      case '$merge': for( var k in changes ) { next[k] = changes[k] }; break
      case '$splice': next.splice.apply(next, changes); break
      case '$push': next.push.apply(next, changes); break
      case '$unshift': next.unshift.apply(next, changes); break
      case '$set': return changes
      case '$unset': delete next[changes]; break
      default: throw new Error("Unknown command: " + command)
    }
  }

  for( var key in updates ) {
    if( COMMANDS.indexOf(key) == -1 ) {
      next[key] = update( next[key], updates[key] )
    }
  }

  return immutable( next )
}

Now we can make any given object immutable, and update it to get a new immutable object back!

That would be enough to use with React, because it has a built in lifecycle function called shouldComponentUpdate. That’s where you would simply check the new props against the identity of the old props and return false if they’re the same. That’s exactly what PureRenderMixin does which is a very handy way to do this pretty much automatically.

We aren’t so lucky though because of our naive adhoc implementations of these things.

A New Todo Store

To support this we first need to adjust our Flux implementation.

var TodoStore = function() {
  var _emitter = new Dispatcher()
  var _nextId = 0
  var _todos = immutable({})

  dispatcher.register( function( payload ) {
    var originalTodos = _todos

    switch( payload.type ) {
      case 'SEED_TODOS':
        // just clobber the old one rather than piecemeal updating
        _todos = immutable( payload.todos )
        // go through the seed and set _nextId
        // appropriately so that creating new todos
        // doesn't override ones from the seed
        for( var i in _todos ) { _nextId = Math.max( _nextId+1, _todos[i].id ) }
        break
      case 'CREATE_TODO':
        payload.todo.id = _nextId++
        var patches = {}
        patches[payload.todo.id] = { $set: payload.todo }
        _todos = update( _todos, patches )
        break
      case 'REMOVE_TODO':
        _todos = update( _todos, { $unset: payload.todo.id } )
        break
      case 'UPDATE_TODO':
        var patches = {}
        patches[payload.todo.id] = { $merge: {} }
        for( var key in payload.todo ) {
          patches[payload.todo.id]['$merge'][key] = payload.todo[key]
        }
        _todos = update( _todos, patches )
        break
    }

    // notify anyone who cares that the store has updates
    // but only IF there are updates
    if( originalTodos !== _todos ) {
      _emitter.dispatch()
    }
  } )

  return {
    getTodos: function() { return _todos },
    addListener: _emitter.register,
    removeListener: _emitter.unregister
  }
}

We replace our plain todos object with an immutable one, and use our update function in our action handlers.

A Component Wrapper Function

Next we need to make our ‘components’ (TodoApp and TodoItem) understand that they render the same thing every time and thus should compare the old arguments to the new ones. We aren’t using any objects with state, though so in order to do this we can wrap them in a sort of memoizing function instead:

function pure( componentFn, immutableProp ) {
  // keep track of props and render results
  var memoizedRenders = {}

  return function( props ) {
    // the prop we are considering ourselves pure 'against'
    var prop = props[immutableProp]

    // attempt to find a memoized render
    // for this prop and id
    var memoized = memoizedRenders[prop.id]

    // if we found one and the memoized value is
    // the exact same object as the new prop
    // then we don't need to render because the
    // result would be the same!
    if( memoized && memoized.value === prop ) {
      return memoized.result
    }
    // otherwise, render and store the results
    // for later lookup
    else {
      var result = componentFn( props )
      memoizedRenders[prop.id] = { value: prop, result: result }
      return result
    }
  }
}

Now we can wrap our components like this:

TodoApp = pure( TodoApp, 'todos' )
TodoItem = pure( TodoItem, 'todo' )

And the wrapping takes care of the comparison/returning the memoized old result, etc.

Demo

That’s it! Time for the demo. This is, once again, the same as last time but now using all of the above immutable data stuff so that the rendering of each TodoItem only happens if its respective todo has actually changed. The others in the list simply spit out the same virtual DOM as last time. Just for fun, there are also some tests in there you can run that verify the behaviour of the immutable data bits.

See the Pen Immutable Data from Scratch by Ryan Funduk (@rfunduk) on CodePen.

That was a long process. It took 3 weeks to get here, and we don’t really have any production code. But that’s ok! Understanding even the most basic aspects of how these things work behind the scenes can give you a new perspective on your own code that uses more robust libraries.