Efficient React Component Diffing

You are tasked with building a core component for a visual diffing tool that highlights changes between two versions of a React component's rendered output. The goal is to efficiently determine which parts of the UI have been added, removed, or modified, enabling precise highlighting and selective re-rendering. This is crucial for applications that need to visualize state changes, track history, or implement advanced debugging features.

Problem Description

The challenge is to implement a diffComponents function that takes two React element trees (representing the "old" and "new" states of a component) and returns a structure that describes the differences between them. This structure should allow for easy identification of added, removed, and modified elements.

Key Requirements:

1. Identify Added Elements: Detect elements present in the "new" tree but not in the "old" tree.
2. Identify Removed Elements: Detect elements present in the "old" tree but not in the "new" tree.
3. Identify Modified Elements: Detect elements that exist in both trees at the same position but have different types or props.
4. Recursive Diffing: The diffing process must be recursive, handling nested elements.
5. Key-Based Reconciliation (Implicit): While not explicitly implementing a full reconciliation algorithm, the diffing logic should implicitly favor matching elements by their position and, if available, by a key prop. For simplicity in this challenge, we will focus on positional matching first, and then consider how keys would influence this.
6. Output Structure: The function should return a structured representation of the differences. This could be an array of operations (e.g., ADD, REMOVE, MODIFY, REORDER) or a tree-like structure mirroring the original elements with difference annotations.

Expected Behavior:

The diffComponents function should compare the oldTree and newTree and return a description of the changes. The output should clearly indicate what needs to be done to transform oldTree into newTree.

Important Edge Cases:

• Empty Trees: Handling cases where one or both input trees are null, undefined, or empty.
• Text Nodes: Differentiating between element nodes and text nodes. Text nodes are considered modified if their content changes.
• Element Type Changes: An element of one type changing to another (e.g., <div> to <span>) should be treated as a modification.
• Child Count Changes: When the number of children changes, new children are added, or existing children are removed.
• Keyed vs. Unkeyed Children: How key props affect matching. Elements with keys should be matched more robustly than those without.

Examples

Example 1: Simple Addition

Input:
oldTree = <div><span>Hello</span></div>
newTree = <div><span>Hello</span><p>World</p></div>

Output:
[
  { type: 'ADD', element: <p>World</p>, parentPath: ['div'] }
]

Explanation: A new <p> element has been added as a child of the <div>. parentPath indicates the location of the parent within the tree.

Example 2: Simple Modification

Input:
oldTree = <div><span className="old-class">Hello</span></div>
newTree = <div><span className="new-class">Hello</span></div>

Output:
[
  { type: 'MODIFY', element: <span className="new-class">Hello</span>, oldElement: <span className="old-class">Hello</span>, path: ['div', 'span'] }
]

Explanation: The <span> element's props have changed. The MODIFY operation includes both the new and old elements for detailed comparison. path indicates the location of the modified element.

Example 3: Removal and Reordering (Conceptual with Keys)

Let's assume we have a simplified representation where key props are used for matching.

Input:
oldTree = <ul><li key="a">A</li><li key="b">B</li></ul>
newTree = <ul><li key="b">B</li><li key="a">A</li><li key="c">C</li></ul>

Output (conceptual):
[
  { type: 'REORDER', oldIndex: 0, newIndex: 1, element: <li key="a">A</li> },
  { type: 'REORDER', oldIndex: 1, newIndex: 0, element: <li key="b">B</li> },
  { type: 'ADD', element: <li key="c">C</li>, parentPath: ['ul'] }
]

Explanation: The order of li elements has changed, and a new li with key "c" has been added. A real implementation would need a more sophisticated algorithm to detect reordering and additions/removals efficiently, especially when keys are present. For this challenge, focus on diffing based on available information.

Example 4: Text Node Change

Input:
oldTree = <div>Some text</div>
newTree = <div>Some different text</div>

Output:
[
  { type: 'MODIFY', text: 'Some different text', oldText: 'Some text', path: ['div'] }
]

Explanation: The text content within the <div> has changed.

Constraints

• React Element Representation: Assume React elements are represented by a structure similar to React.ReactElement, with properties like type, props, and children. props.children can be a single element, an array of elements, or a string (for text nodes).
• Simplicity of Diffing: For this challenge, you don't need to implement a full-blown VDOM diffing algorithm like React's. Focus on comparing direct children and identifying changes. A perfect key-based reconciliation is advanced; prioritize clear identification of additions, removals, and modifications based on structure and props.
• Performance: The diffing logic should be reasonably efficient, avoiding unnecessary deep traversals where possible. O(N) where N is the number of nodes in the larger tree is a good target for a simplified approach.
• TypeScript: The solution must be implemented in TypeScript.

Notes

• You'll likely need a helper function to recursively traverse the React element trees.
• Consider how to represent differences. An array of operation objects (e.g., { type: 'ADD', ... }) is a common and flexible approach.
• Think about how to compare props. For this challenge, simple prop comparison (e.g., checking for equality or specific prop changes) is sufficient. Complex deep prop comparison might be out of scope unless explicitly stated.
• While React's reconciliation uses keys for efficient matching, for this challenge, you can primarily rely on positional matching of children. If key props are present, you can use them as a hint, but don't get bogged down in complex key-matching logic unless it's your primary focus.
• The React.ReactElement type in TypeScript might be useful, or you can define your own simplified element interface if you prefer.
• This problem is about identifying the differences, not necessarily about applying them or re-rendering.