Programming basics using React source code as an example
Data Structures
Linked List
Used extensively throughout the codebase, particularly for managing fibers, updates, and effects. For instance, the `Fiber` data structure itself forms a tree structure through its `child`, `sibling`, and `return` properties. Update queues for both class and function components are also implemented as linked lists, allowing efficient processing of updates.
Why React Uses Linked Lists
(1) Efficient Updates and Reconciliation
Dynamic Nature of UIs: UI updates in React often involve adding, removing, and reordering elements. Linked lists are well-suited for such dynamic operations, as they allow efficient insertion and deletion of nodes without the need to shift elements like in an array. This is crucial for React’s reconciliation algorithm, which minimizes DOM manipulations for optimal performance.
Constant Time Insertion and Deletion: Linked lists provide constant time complexity (O(1)) for insertions and deletions at the beginning or end of the list. This efficiency is beneficial when managing update queues and effect lists, where new updates or effects are typically added or removed from the head or tail.
(2) Memory Efficiency
Reduced Memory Allocation: Linked lists dynamically allocate memory as needed, adding new nodes only when required. This contrasts with arrays, which often require pre-allocating a fixed amount of memory even if not all slots are used. For large and dynamic UIs, linked lists can be more memory-efficient.
Flexible Memory Usage: In React’s virtual DOM, each fiber node (a unit of work) is represented by a linked list structure. This flexibility allows the library to allocate and deallocate memory for individual fibers as they enter and leave the reconciliation process, optimizing memory usage.
(3) Functional Programming Paradigm
Immutability: React embraces immutability, where data structures are not modified directly but instead replaced with new versions. Linked lists are a natural fit for this paradigm because updating a list involves creating a new list with the desired changes, leaving the original list intact.
Recursion: Linked lists lend themselves well to recursive algorithms, which are common in functional programming. React’s reconciliation algorithm and several other internal processes utilize recursion to traverse and manipulate the fiber tree efficiently.
Stack
Used for managing context, suspense handlers, and other contextual information during rendering and committing phases. The `ReactFiberStack.js` module provides functionalities like `push`, `pop`, and `createCursor` for working with stacks.
Map
Utilized for managing various mappings, such as the `entries` map in `ReactCacheOld.js`, which associates resources with their corresponding entries, and the `_chunks` map in `ReactFlightClient.js` for storing response chunks.
Set
Employed for storing unique values, like the `_updatedFibers` set in `ReactFiberTracingMarkerComponent.js`, which tracks fibers updated during a transition.
Heap (Min Heap)
The scheduler package, used by React for managing tasks, employs a min-heap data structure to prioritize tasks based on their expiration times.
Trees
The virtual DOM itself is a tree structure represented by `Fiber` nodes. Additionally, `ReactFiberTreeContext.js` manages a separate tree structure for generating unique IDs during hydration.
Algorithms
Reconciliation Algorithm
The core algorithm of React, responsible for efficiently updating the UI by comparing the current and next virtual DOM trees and applying minimal changes to the real DOM. This involves traversing trees, comparing nodes, and computing minimal diff operations. Implemented across various files, like `ReactChildFiber.js`.
LRU Cache
The `LRU.js` module implements an LRU (Least Recently Used) cache for storing and managing cached data. This algorithm helps optimize performance by reusing previously computed values.
Scheduler Algorithm
The scheduler package uses a priority queue based on a min-heap to schedule and prioritize tasks based on their expiration times and priority levels.
String Encoding/Decoding
Used in `ReactFlightClient.js` and other modules for efficiently transferring data between the server and the client.
Context Propagation
Algorithms for propagating context changes through the component tree efficiently, especially with the introduction of lazy context propagation.
Hydration Algorithm
Used for efficiently “attaching” to existing HTML markup during the initial render instead of creating the DOM from scratch.
Error Handling
Algorithms for handling errors and Suspense fallbacks, traversing the fiber tree to find the nearest appropriate error boundary.
Design Patterns
Module Pattern
The code is organized into modules, each with its own responsibility and API. This promotes code reuse, maintainability, and separation of concerns. For example, `ReactChildren.js` provides functions for working with children elements, while `ReactContext.js` handles context creation and management.
Factory Pattern
The `createElement` and `cloneElement` functions act as factories for creating and cloning React elements. This provides a central point for element creation and ensures consistency in their structure.
Observer Pattern
The `useSyncExternalStore` hook implements the observer pattern, where components subscribe to an external store and re-render when the store updates. This allows efficient state management and synchronization with external data sources.
Provider Pattern
The context API, implemented in `ReactContext.js` , utilizes the provider pattern. A context provider makes a value available to its descendant components, allowing data to be passed down the component tree without explicitly passing props through each level.
Decorator Pattern
Higher-Order Components (HOCs) and certain Hooks represent this pattern. HOCs: `forwardRef`, `memo`. Hooks: `useMemo`, `useCallback`. These HOCs and Hooks decorate components and functions with additional behavior without altering their core implementation. This promoting flexibility and code reuse.
SOLID Principles
Single Responsibility Principle (SRP)
Each module and function has a well-defined responsibility. For example, `ReactFiberBeginWork.js` focuses on the begin phase of the reconciliation process, while `ReactFiberCompleteWork.js` handles the complete phase.
Open/Closed Principle (OCP)
The library is designed to be open for extension but closed for modification. This is evident in the use of hooks, which allow adding new functionality without changing the core React components.
Liskov Substitution Principle (LSP)
Subtypes of components (e.g., `PureComponent` and `memo` components) can be used wherever a `Component` is expected, ensuring consistent behavior.
Interface Segregation Principle (ISP)
The library exposes several smaller, focused interfaces (e.g., `Dispatcher`) rather than large, monolithic ones. This reduces coupling and makes it easier to use specific parts of the library without depending on unnecessary functionality.
Dependency Inversion Principle (DIP)
The library relies on abstractions (e.g., the `ReactFiberReconciler` uses the `HostConfig` interface) instead of concrete implementations, allowing different renderers to be used with the same core logic.
