Make React wheels in TypeScript by hand

This article is the third in TypeScript Hand-to-hand Make React Wheels. Let’s talk about a simple implementation of the Diff algorithm. The source code for the project is here. Welcome to Star and fork🥺🥺🥺.

• 1. What is the Diff algorithm (props)
• 2. The key to Diff algorithm
  • 2.1. Key: is it the first rendering
  • 2.2. Key: Get the last rendered virtual DOM
  • 2.3. Key: Render component or DOM element?
• 3. Updating DOM elements
  • 3.1. Update the text node
  • 3.2. Updating the props properties (In depth comparison)
  • 3.3. Recursive loop updates child elements
  • 3.4. Determine whether the properties on the old virtual DOM have been deleted
• 4. Update the components
  • 4.1. Component updates === Class component updates
  • 4.2. Check whether it is the same component
  • 4.3. Complete the Diff algorithm of components
• 5. Test and Demo
  • 5.1. The Demo
  • 5.2. Test

1. What is the Diff algorithm (props)

Since we haven’t introduced the concept of state yet, the diff algorithm in this section is limited to updates to props for a given element!

As mentioned earlier, React uses the virtual DOM to minimize direct manipulation of the DOM. According to our previous logic, every time a virtual DOM is rendered, the MyReact engine iterates recursively through the current virtual DOM tree to complete the rendering. However, in practical application scenarios, sometimes we just modify a style information below the component. If we repeatedly render this component regardless of the situation, it will waste a lot of resources and affect the user experience. So we need some mechanism to identify the smallest component that has changed. This mechanism is the React Diff algorithm. Directly using the example from the previous component rendering article:

In this case, because we are just adding new children to the list, it is best to render the three more children on top of the existing ones. The key is to 1) compare virtual DOM at the same level under different virtual DOM trees and 2) update the DOM object corresponding to the virtual DOM. Let’s take a look at this classic comparison of the virtual DOM

In the previous chapters, we used the __virtualDOM attribute so that when changes are made, we can compare the __virtualDOM attribute with the current virtualDOM to make a peer comparison. The advantage of peer comparison is that we only need to traverse the virtualDOM tree once (comparing the current virtualDOM to the container’s __virtualDOM), so the time complexity isO(n), where n is the number of all nodes under the virtual DOM tree.

export const mountComponent = (virtualDOM: MyReactElement, container: HTMLElement) = > {
  // Get the constructor and properties
  / *... * /
  // If it is a class component
  / *... * / 
  // If it is a function component
  / *... * /
  // Record the virtual DOM to facilitate diff algorithm comparison
  container.__virtualDOM = newVirtualDOM
  // Determine the type of element to render recursively
  / *... * /
}
Copy the code

Conclusion: Before Fiber was introduced, React’s Diff algorithm was “efficient” because it implemented minimal granularity updates with the help of the virtual DOM Tree. When prop or state of a component or element changed, React compared the old and new virtual DOM trees using peer comparisons. Find the smallest tree node where the change occurred and render the difference.

So we need to extend and modify the original render:

• If it is rendering for the first time, no comparison is required and render directly
• Read the value of __virtualDOM (previously the virtualDOM) from the parent container if it is not the first rendering
  • If it’s a component
    • Read the previous component __virtualdom.component
    • If it is the same component, determine whether it needs to be rerendered
    • If not the same component, render directly
  • If it’s a DOM node
    • If it is text, compare props. TextContent
    • If it is a DOM element, compare the props object in the old and new virtual DOM in depth
  • If there are children, recursively iterate over all children

These are roughly what the React Diff algorithm does. The first render function itself can not meet the requirements, we need to use the Diff algorithm to achieve efficient page update function.

2. The key to Diff algorithm

2.1. The key: is it the first render

The first key to the Diff algorithm is to determine whether a virtual DOM is being rendered for the first time. All we need to do is determine whether the root in MyReact. Render (App, root) has child elements.

Do you know why React requires that we only wrap JSX in a single tag when rendering components? This specification makes it easy for React to use Node.firstChild to determine if a virtual DOM has been rendered.

Since we don’t render the virtual DOM directly, we first use the Diff algorithm to determine that the container has rendered the virtual DOM, we need to rewrite the render function to look like this:

/** * Render with Diff *@param virtualDOM 
 * @param container 
 */
export const render = (virtualDOM: MyReactElement, container: MyHTMLElement) = >{ diff(virtualDOM, container, container? .firstChildas MyHTMLElement)
}

/** * Diff algorithm *@param virtualDOM 
 * @param element 
 * @param preVirtualDOM 
 */
export const diff = (virtualDOM: MyReactElement, container: MyHTMLElement, element: MyHTMLElement) = > {
  // If element does not exist, it means that this is the first render, no comparison is required, just render directly
  if(! element)return mountElement(virtualDOM, container)
  // TODO retrieves the previous virtual DOM
  / *... * /
}

Copy the code

2.2. Key: Get the last rendered virtual DOM

/* ./src/MyReact/MyReactRender.ts */

export const diff = (virtualDOM: MyReactElement, container: MyHTMLElement, element: MyHTMLElement) = > {
  // If element does not exist, it means that this is the first rendering and does not need to be directly rendered
  if(! element)return mountElement(virtualDOM, container)
  // Get the previous virtual DOM
  const oldVirtualDOM = element.__virtualDOM
  const { type, props } = virtualDOM
  // Determine whether it is a component or a DOM node
}
Copy the code

2.3. Key: Render component or DOM element?

Determining whether the virtual DOM is a component or a DOM element can be easily done by referring to the previous component rendering:

export const diff = (virtualDOM: MyReactElement, container: MyHTMLElement, element: MyHTMLElement) = > {
  // If element does not exist, it means that this is the first rendering and does not need to be directly rendered
  if(! element)return mountElement(virtualDOM, container)
  // Get the previous virtual DOM
  const oldVirtualDOM = element.__virtualDOM
  const { type, props } = virtualDOM
  // Determine whether it is a component or a DOM node
  if (isFunction(type)) {
    // Update the component
  } else {
    / / update the DOM}}Copy the code

3. Updating DOM elements

3.1. Update text node

If we were comparing text nodes, we could easily do this:

/** * Updates the DOM text node *@param virtualDOM 
 * @param oldVirtualDOM 
 * @param element 
 */
export const updateText = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement) = > {
  if(virtualDOM.props.textContent ! == oldVirtualDOM.props.textContent) {// Change the text
    element.textContent = virtualDOM.props.textContent
    // Save as __virtualDOM
    element.__virtualDOM = virtualDOM
  }
}
Copy the code

3.2. Update the props property (Depth comparison)

/* ./src/MyReact/MyReactDOM.ts */

/** * Update the DOM element => Update the attribute below the element *@param virtualDOM 
 * @param oldVirtualDOM 
 * @param element 
 */
export const updateDOMElement = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement) = > {}
Copy the code

/* ./src/shard/utils.ts */

export const isEqual = <T>(firstObj: T, secondObj: T): boolean= > {
  // 1. If it is not a complex type, judge directly
  if(! isReference(firstObj) || ! isReference(secondObj))return firstObj === secondObj

  // 2. Compare whether to reference the same memory address
  if (firstObj === secondObj) return true

  // 3. Start depth comparison if both are objects or arrays
  const firstKeys = Object.keys(firstObj)
  const secondKeys = Object.keys(secondObj)
  // 3.1 If the lengths are not equal
  if(firstKeys.length ! == secondKeys.length)return false
  // 3.2 Recursive judgment
  for (let key in firstObj) {
    const result = isEqual(firstObj[key], secondObj[key])
    if(! result)return false
  }
  return true
}

/* Determine if a value is a complex type */
export const isReference = <T>(value: T): boolean= > {
  return value && typeof value === 'object'
}
Copy the code

export const updateDOMElement = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement) = > {
  const newProps = virtualDOM.props
  const oldProps = oldVirtualDOM.props
  const propsKeys = Object.keys(newProps)
  const oldPropsKeys = Object.keys(oldProps)
  // From the new than the old
  propsKeys.length && propsKeys.forEach((key: string) = > {
    if(key === 'textContent') { 
      updateText(virtualDOM, oldVirtualDOM, element)
    }
    else if (key === 'children' ) {
      // If there are child elements, recursive Diff is required
    }
    else {
      // If the attribute value changes
      if(! isEqual(newProps[key], oldProps[key])) {console.log(newProps[key])
        console.log(oldProps[key])
        updateProp(key, newProps[key], element) // Update a specific attribute value on a DOM node
        console.log(` -- -- -- -- -- -- -- -- --${key} has been updated---------`)}}})// Compare the old with the new

  // Record the new virtual DOM
  element.__virtualDOM = virtualDOM
}
Copy the code

3.3. A recursive loop updates the child elements

Similar to rendering the DOM element for the first time, we need to determine whether the virtual DOM(newVirtualDOM) we want to render is a component or a DOM element:

• If newVirtualDOM remains a component, it is updated recursively
• If newVirtualDOM is a DOM element
  • If there are child elements, Diff is recursively performed
  • Iterate over the update props property

If newVirtualDOM is a DOM element, two points need to be noted:

First point: If the virtual DOM element needs to render a DOM element, and the DOM element has three child elements underneath it. According to the rules defined in the createElement method, the virtual DOM of these three child elements is stored in props. Children; And the type attribute in the virtual DOM of the child element (that is, the virtual DOM that the child element needs to render) can be either a function (rendering component) or a string (rendering DOM element). So we need to recursively traverse the virtual DOM in props. Children and perform the Diff algorithm.

/* MyReact/MyReactDOM.ts */

/** * Updates the child element *@param virtualDOM 
 * @param oldVirtualDOM 
 * @param element 
 */
export const updateChildren = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement) = > {
  const { children } = virtualDOM.props
  console.log(children);
  const { children: oldChildren } = oldVirtualDOM.props
  console.log(oldChildren);
  // If there are child elements
  // Todo should be indexed by keychildren? .forEach((newElement: MyReactElement, index: number) = > {
    console.log(index);
    console.log(newElement);
    console.log('oldElement: ', oldChildren[index]);
    const oldElement = oldChildren[index]
    // If not, add it directly
    if(! oldElement) { mountElement(newElement, element) }// If present, recurse Diff
    else {
      diff(newElement, element, element.childNodes[index] as MyHTMLElement)
    }
  });
}
Copy the code

Second, since we need to recursively traverse the virtual DOM in props. Children and perform the Diff algorithm, we need to know the component instances in the old virtual DOM; However, storing component instances is performed at actual rendering time, in other words, given two virtual DOM’s before and after a component: NewChildVDOM and oldChildVDOM, if we go to diff(newChildVDOM, Container, Element, oldChildVDOM), OldChildVDOM has no component property. This will cause the MyReact engine to assume that the two components are not the same during Diff comparisons and simply repeat the rendering. So we need to modify the updateProp method:

/* MyReact/MyReactDOM.ts */

export const updateProp = (propName: string, propValue: any, element: MyHTMLElement) = > {
  // If children skip
  if (propName === 'children') {
    // The original logic => skip directly
    // return 

    If the virtual DOM traversed is a component, what is the component responsible for rendering the virtual DOM
    propValue.map((child: MyReactElement) = > {
      const { type: C, props } = child
      // If it is a component, add the component attribute to the children element to facilitate Diff algorithm comparison
      if (isFunction(C)) {
        if (isClassComponent(child.type)) {
          return Object.assign(child, { component: new C(props || {}) })
        } else {
          return Object.assign(child, { component: C(props || {}) })
        }
      }
      // If it is a DOM element
      else {
        return child
      }
    })
  }
  /* other ellipses */
}

Copy the code

3.4. Determines whether attributes on the old virtual DOM have been deleted

export const updateDOMElement = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement) = > {
  const newProps = virtualDOM.props
  const oldProps = oldVirtualDOM.props
  const propsKeys = Object.keys(newProps)
  const oldPropsKeys = Object.keys(oldProps)

  /* From the new than the old, omit */ 

  // Compare the old with the new
  oldPropsKeys.length && oldPropsKeys.forEach((oldKey: string) = > {
    // If the attribute is deleted
    if(! propsKeys.includes(oldKey)) { removeProp(oldKey, oldProps[oldKey], element) } })// Record the new virtual DOM
  element.__virtualDOM = virtualDOM
}

/** * Delete attribute *@param propName 
 * @param propValue 
 * @param element 
 */
export const removeProp = (propName: string, propValue: any, element: MyHTMLElement) = > {
  if (propName === 'children') return
  if (propName.toLowerCase().slice(0.2) = = ='on') {
    element.removeEventListener(propName.toLowerCase().slice(2), propValue)
  } else {
    element.removeAttribute(propName)
  }
}
Copy the code

export const updateDOMElement = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement) = > {
  const newProps = virtualDOM.props
  const oldProps = oldVirtualDOM.props
  const propsKeys = Object.keys(newProps)
  const oldPropsKeys = Object.keys(oldProps)
  // From the new than the old
  propsKeys.length && propsKeys.forEach((key: string) = > {
    if(key === 'textContent') { 
      updateText(virtualDOM, oldVirtualDOM, element)
    }
    else if (key === 'children' ) {
      // If there are child elements, recursive Diff is required
      updateChildren(virtualDOM, oldVirtualDOM, element)
    }
    else {
      // If the attribute value changes
      if(! isEqual(newProps[key], oldProps[key])) { updateProp(key, newProps[key], element)// Update a specific attribute value on a DOM node}}})// Compare the old with the new
  oldPropsKeys.length && oldPropsKeys.forEach((oldKey: string) = > {
    // If the attribute is deleted
    if(! propsKeys.includes(oldKey)) { removeProp(oldKey, oldProps[oldKey], element) } })// Record the new virtual DOM
  element.__virtualDOM = virtualDOM
}
Copy the code

export const diff = (virtualDOM: MyReactElement, container: MyHTMLElement, element: MyHTMLElement) = > {
  // If element does not exist, it means that this is the first render, no comparison is required, just render directly
  if(! element)return mountElement(virtualDOM, container)
  // Get the previous virtual DOM
  const oldVirtualDOM = element.__virtualDOM
  const { type, props } = virtualDOM
  // Determine whether it is a component or a DOM node
  if (isFunction(type)) {
    // Update the component
    // do something 
  } else {
    / / update the DOM
    updateDOMElement(virtualDOM, oldVirtualDOM, element)
  }
}
Copy the code

4. Update the components

4.1. Component updates= =Updates to class components

4.2. Check whether it is the same component

So the first thing that needs to be realized here is how to determine that two virtual DOM renderings are the same component. For components, if we compare virtualdom. type directly to the __virualdom. type attribute of the parent element node, the result is always false. Because the first rendering in the mountComponent, The __virtualDOM in container.__virtualDOM = newVirtualDOM is already a virtualDOM returned by render or return.

/* ./demo/index.tsx */
// Re-render the same component

class Todos extends React.Component<{ type: string} > {render() {
    const { type } = this.props
    return type= = ='one' ? vDOM : vDOM2
  }
} 

const root = document.getElementById('app') as MyHTMLElement
MyReact.render(<Todos type="one" />, root)

setTimeout(() = > {
  MyReact.render(<Todos type="two" />, root)
}, 5000);
export const diff = (virtualDOM: MyReactElement, container: MyHTMLElement, element: MyHTMLElement) = > {
  // * First render
  if(! element)return mountElement(virtualDOM, container)
  // * Same level comparison
  // Get the previous virtual DOM
  const oldVirtualDOM = element.__virtualDOM

  console.log(oldVirtualDOM.type) // "div"
  console.log(virtualDOM.type) // f Todos() {/*... * /}
  console.log(virtualDOM.type === oldVirtualDOM.type) // false

  /* * * */
}

Copy the code

When comparing two virtual DOM’s, it is certainly not elegant to directly compare the rendered results to determine whether they are the same component.

Recommended practices: Here we can take advantage of the constructor principle — on the first rendering k, When storing the component instance __virtualdom.component. Diff, compare virutaldom. type to see if it is the constructor of __virtualdom.component.

// Store the component responsible for rendering the virtual DOM
/* .src/MyReact/MyReactComponent.ts */

// Change the mountComponent method to store the instance in __virtualDOM for the first rendering
const mountComponent = () = > {
  / *... * /
  // If it is a class component
  if (isClassComponent(virtualDOM.type)) {
    console.log('rendering class component')
    // Create an instance and return
    component = new C(props || {})
    newVirtualDOM = component.render()
    / /!!!!! Added: Record Component to facilitate diff algorithm comparison
    newVirtualDOM.component = component
  }
  // If it is a function component
  else {
    console.log('rendering functional component')
    newVirtualDOM = C(props || {})
    // Functional components do not need to be logged because they need to be re-rendered if they are not updated}}/* src/shared/utils.ts */
/** * Check whether the components are the same *@param virtualDOM 
 * @param oldComponent 
 * @returns * /
export const isSameComponent = (virtualDOM: MyReactElement, oldComponent: any) = > {
  return oldComponent && virtualDOM.type === oldComponent.constructor
}

Copy the code

At present, our component update logic: when the component is updated, if the same component executes the diff algorithm to update the component; If it is not the same component (including functional components), simply remove the original __virtualDOM element from the parent container and re-render the component.

/** * Update component *@param virtualDOM 
 * @param oldComponent 
 * @param element 
 * @param container 
 */
export const updateComponent = (virtualDOM: MyReactElement, oldComponent: MyReactComponent, element: MyHTMLElement, container: MyHTMLElement) = > {
  // If not the same component, render directly
  if(! isSameComponent(virtualDOM, oldComponent)) {// Determine if you need to re-render
    container.removeChild(element)
    mountComponent(virualDOM, element)
  }
  // If it is the same component, update it
  else {
    // Determine whether the props of the component have been changed}}Copy the code

The next step is to determine whether the props under the component have been changed. We can add the concept of life cycle function here.

Because of the relationship between TS and Babel rules, in the example component is directly inherited React.Com ponent, so when I was in the echo statement hooks, is a function of use directly instead of class the following method. For now, let’s use this plan.

/* ./src/MyReact/MyReactLifecycle.ts */
// Only props are compared, with the help of depth comparison
export const shouldComponentUpdate = (prevProps: { [key: string] :any }, props: { [key: string] :any }) = > {
  return! isEqual(prevProps, props) }Copy the code

4.3. Complete the Diff algorithm for the component

/** * Update component *@param virtualDOM 
 * @param oldComponent 
 * @param element 
 * @param container 
 */
export const updateComponent = (virtualDOM: MyReactElement, oldVirtualDOM: MyReactElement, element: MyHTMLElement, container: MyHTMLElement) = > {
  // Get the component instance of the old virtual DOM
  const oldComponent = oldVirtualDOM.component
  if(! oldComponent || ! isSameComponent(virtualDOM, oldComponent)) {console.log('is not the same component, start rendering')
    container.removeChild(element)
    mountComponent(virtualDOM, container)
  }

  // If it is the same component, update it
  else {
    // Determine if you need to re-render
    if(! shouldComponentUpdate(oldComponent.props, virtualDOM.props))return
  
    // Update needs to loop through the subcomponents below
    const { type: C, props } = virtualDOM
    const newVirtualDOM = new C(props || {}).render()
    // If it is still a component
    if (isFunction(newVirtualDOM.type)) {
      // diff(newVirtualDOM, )
      updateComponent(newVirtualDOM, oldVirtualDOM, element, container)
    }
    / / DOM elements
    else {
      / / update the props
      updateDOMElement(newVirtualDOM, oldVirtualDOM, element) 
    }
  }
}
Copy the code

5. Test and Demo

5.1. Demo

export class Todo extends React.Component<{ task: string, completed? :boolean, event? : MouseEventHandler<HTMLLIElement> }> {render() {
    const { completed, task, event } = this.props
    return (
      <li className={completed ? 'completed' : 'ongoing'} onClick={event}>
        {task}
      </li>)}}// Change Todos to class components as well
export class Todos extends React.Component<{ type: string} > {render() {
    const { type } = this.props
    const engList = (
      <section className="todos eng" role="list">
        <Todo task="createElement" completed={true} />
        <Todo task="render" completed={true} />
        <Todo task="diff" completed={false} />
      </section>
    )
    const cnList = (
      <section className="todos chi" role="list">
        <Todo task="createElement" completed={true} />
        <Todo task="render" completed={true} />
        <Todo task="Diff" completed={true} />
        <Todo task="Virtual DOM" completed={true} />
        <Todo task="Rendering" completed={true} />
        <Todo task="Diff algorithm" />
      </section>
    )
    return type= = ='one' ? engList : cnList
  }
}


const root = document.getElementById('app') as MyHTMLElement
MyReact.render(<Todos type="one" />, root)

// Update the component after 5 seconds
setTimeout(() = > {
  MyReact.render(<Todos type="two" />, root)
}, 5000);
Copy the code

5.2. test

As before, we can also use Jest to test whether Diff’s algorithm is correct. The first step is to ensure that the existing code passes the previously rendered test case:

The test case here performs some simple tests on DOM element updates and component updates, mainly in this case

• The DOM element Diff can change the text
• The DOM element Diff can update the attributes of DOM elements (using styles as an example)
• The DOM element Diff changes the number of child elements correctly
• The component Diff updates the props property and renders the DOM element correctly
• Component Diff updates the child components correctly and renders them

/************************* * __tests__/diff.test.tsx *************************/

describe("test Diff with DOM".() = > {
  it('should update text'.() = > {
    let oldVirtualDOM = <p>old</p>
    let newVirtualDOM = <p>new</p>
    mountDOMElement(oldVirtualDOM, container)
    setTimeout(() = > {
      updateDOMElement(newVirtualDOM, oldVirtualDOM, container)
      expect(getByText(container, 'new')).toBeTruthy()
    }, 3000);
  })

  it('should update class'.() = > {
    let oldVirtualDOM = <p className="cool">old</p>
    let newVirtualDOM = <p className="chill">new</p>
    mountDOMElement(oldVirtualDOM, container)
    setTimeout(() = > {
      updateDOMElement(newVirtualDOM, oldVirtualDOM, container)
      expect(getByText(container, 'new')).toHaveClass('chill')},3000);
  })

  it('should have correect child elements'.() = > {
    let oldVDOM = (
      <ul role="list">
        <li>a</li>
        <li>b</li>
        <li>c</li>
      </ul>
    )
    let newVDOM = (
      <ul role="list">
        <li>a</li>
        <li>b</li>
        <li>c</li>
        <li>d</li>
        <li>Z</li>
      </ul>
    )

    mountDOMElement(oldVDOM, container)
    expect(getByRole(container, 'list').childElementCount).toBe(3)
    setTimeout(() = > {
      updateDOMElement(newVDOM, oldVDOM, container)
      expect(getByRole(container, 'list').childElementCount).toBe(5)},3000);
  })
})

describe('test Diff with Component'.() = > {
  it('should update props'.() = > {
    let oldVDOM = <Todo task="diff" completed={false} />
    let newVDOM = <Todo task="Diff" completed={true} />
    mountComponent(oldVDOM, container)
    setTimeout(() = > {
      updateComponent(newVDOM, oldVDOM, container.firstChild, container)
      expect(getByText(container, 'Diff')).toBeTruthy()
      expect(getByText(container, 'Diff').parentElement).toHaveClass('completed')},3000);
  })

  it('should update child elements'.() = > {
    let oldVDOM = <Todos type="one" />
    let newVDOM = <Todos type="two" />

    mountComponent(oldVDOM, container)
    expect(getByRole(container, 'list').childElementCount).toBe(3)
    setTimeout(() = > {
      updateComponent(newVDOM, oldVDOM, container.firstChild, container)
      expect(getByRole(container, 'list').childElementCount).toBe(6)
      expect(getByRole(container, 'list').childNodes[2]).toHaveTextContent('Diff')
      expect(getByRole(container, 'list').childNodes[2]).toHaveClass('completed')},3000); })})Copy the code

Otherwise, the test case will pass. I won’t do more test cases due to time constraints, but you are welcome to test some extreme cases yourself.

Above, we completed the basic part of the React wheel Diff algorithm and realized that the MyReact engine used the depth-first algorithm to update the virtual DOM efficiently.

Happy Spring Festival, year of the Tiger. See you after.