7 The reconciliation algorithm: Diffing virtual trees

Picture this: you’re in the supermarket, using the shopping list your partner gave you. You walk around the aisles, picking up the items one by one and putting them in the cart. When you’re done, you head to the checkout counter, but at that very moment your phone vibrates in your pocket; it’s a message from your partner. She realized that there are already a dozen eggs in the fridge; what’s missing is a bottle of wine for that fancy dinner you’re going to have tonight with some friends. She’s texted you the updated shopping list. Now you have two lists: the original one (whose items are already in your cart) and the updated one, as you can see in figure 7.1.

You have two options:

7.1 The three key functions of the reconciliation algorithm

7.2 Comparing two virtual DOM trees

7.2.1 Finding the differences

7.2.2 Applying the changes

7.3 Changes in the rendering

7.4 Diffing objects

7.5 Diffing arrays

7.6 Diffing arrays as a sequence of operations

7.6.1 Defining the operations you can use

7.6.2 Finding the sequence of operations: The algorithm

7.6.3 An example by hand

7.6.4 Implementing the algorithm

Summary