jd

The structural format is a human-readable diff format designed for JSON and YAML data. Key features include:

• Human-readable: Produces unified diff-style output.
• Context-aware: Provides surrounding elements to clarify the location of changes.
• Set semantics: Can treat arrays as sets or multisets when element order is not significant.
• Configurable: Supports numeric precision tolerance for floating-point comparisons.
• Flexible: Uses PathOptions to allow fine-grained control over how specific paths are compared.

Paths are sequences of path elements used to navigate the document tree. Common patterns include:

• String: Represents an object property key.
• Number: Represents a 0-based array index. Use -1 to indicate an append operation.
• Empty list []: Represents the document root.

Examples:

• ["users", 0, "name"] maps to document.users[0].name
• ["config", "timeout"] maps to document.config.timeout
• [] maps to the root document.

["users", 0, "name"] → document.users[0].name
["config", "timeout"] → document.config.timeout  
[] → document (root)

JD V2 uses specific path element notations to distinguish between standard objects, sets, and multisets:

• Set: Represented by an empty object {} or an object with keys. A simple set uses {} in the path.
• Multiset: Represented by an empty array [] or an array containing an object with keys. A simple multiset uses [{}] in the path.
• Object Identity: Using an object with keys within a path indicates object identity.

When diffing arrays of objects, you can provide a keys option specifying which field acts as a unique identifier (e.g., id). This allows the diff to target specific objects within the array by their identity rather than their index, making the diff much more stable and readable when objects move or are inserted/deleted.

### Keys Option
**Options:** `[{"keys": ["id"]}]`
**Input A:**
```json
{
  "users": [
    {"id": 1, "name": "Alice", "status": "active"},
    {"id": 2, "name": "Bob", "status": "inactive"}
  ]
}

Input B:

{
  "users": [
    {"id": 1, "name": "Alice", "status": "inactive"},
    {"id": 2, "name": "Bob", "status": "active"}
  ]
}

Diff Output:

^ {"keys":["id"]}
@ ["users",{"id":1},"status"]
- "active"
+ "inactive"
@ ["users",{"id":2},"status"]
- "inactive"
+ "active"

In the v2 system, JsonNode is designed to be immutable. When performing a Patch(d Diff) operation, the system does not modify the existing node. Instead, it returns a new JsonNode instance.

To maintain performance, the system uses structural sharing. When a node is patched, only the path from the root to the modified node is copied. All other subtrees that were not affected by the patch are shared between the original and the new node by reference. This ensures that memory usage does not grow linearly with the number of patches and keeps operation complexity low.

Original: {a: 1, b: {c: 2, d: 3}, e: 4}
Patch: set a = 10

Result:   {a: 10, b: {c: 2, d: 3}, e: 4}
          ↑new   ↑shared subtree  ↑shared

Only root object is new, all subtrees shared.

The structural format operates on a hierarchical document model consisting of:

• Documents: Trees of JSON values.
• Paths: Sequences that identify specific locations within documents.
• Values: Can be primitives (string, number, boolean, null), arrays, or objects.
• Void: Represents the absence of a value (distinct from null).

The jd library uses different algorithms for diffing arrays based on their size and content to balance performance and complexity. This strategy ensures that small arrays are handled quickly, medium arrays use efficient diffing, and large arrays or specific patterns (like empty or identical arrays) use fast-path optimizations.

Algorithm Selection Logic:

• Empty, Identical, or No common elements: Fast-path (O(1) or O(n)) - skips expensive LCS (Longest Common Subsequence).
• Size ≤ 10: Simple direct comparison.
• Size 10–1000: Myers' diff algorithm (O(ND) complexity, O(n) space).
• Size > 1000: LCS with fast-path fallback.

The jd library allows you to selectively enable or disable diffing for specific paths within a JSON/YAML document using PathOptions. This is useful for ignoring system-generated values (like timestamps) or implementing an 'allow-list' approach where you ignore everything except specific fields.

Key Behaviors

• Default State: Diffing is ON by default.
• Nesting: PathOptions are hierarchical. A lower-level path can override a higher-level setting (e.g., turning off diffing at the root but turning it back on for a specific sub-path).
• Precedence: PathOptions are processed in order; the last directive for a specific path takes precedence.
• Result: When diffing is turned off for a path, no diff events are generated for that section, and the library returns an empty diff for those nodes.

The jd structural diff format is built around two fundamental operations:

1. diff: Takes two JSON documents and an optional set of options to produce a structural diff.
2. patch: Takes a structural diff and a JSON document to produce a patched version of that document.

In a standard workflow, diff produces the output that patch subsequently consumes to transform content_a into content_b.