Skip to content

# RFC 6902 JSON Patch Implementation Design

## Overview

This document outlines the design for implementing RFC 6902 JSON Patch support in glaze, providing `diff` and `patch` functionality for `glz::generic` JSON values.

### Goals

1. RFC 6902 Compliance - Support all six patch operations: `add`, `remove`, `replace`, `move`, `copy`, `test`
2. Idiomatic glaze API - Follow existing patterns (e.g., `expected` return types, options structs)
3. Performance - Minimize allocations, support in-place modifications
4. Correctness - Atomic patch application with rollback on failure

### Non-Goals

1. Compile-time struct diffing (future enhancement)
2. JSON Merge Patch (RFC 7386) - separate feature
3. Three-way merge functionality

## API Design

### Patch Operation Structure

    namespace glz
    {
       // RFC 6902 operation types
       enum struct patch_op_type : uint8_t {
          add,
          remove,
          replace,
          move,
          copy,
          test
       };

       // Single patch operation
       // Uses std::optional for fields that are only present for certain operations:
       // - value: required for add, replace, test
       // - from: required for move, copy
       struct patch_op
       {
          patch_op_type op{};
          std::string path{};                    // JSON Pointer (RFC 6901)
          std::optional<generic> value{};        // For add, replace, test
          std::optional<std::string> from{};     // For move, copy
       };

       // patch_op is reflectable - no glz::meta needed since member names
       // match the JSON keys. std::optional fields are automatically omitted
       // when std::nullopt during serialization.

       template <>
       struct meta<patch_op_type>
       {
          using enum patch_op_type;
          static constexpr auto value = enumerate(add, remove, replace, move, copy, test);
       };

       // A patch document is an array of operations
       using patch_document = std::vector<patch_op>;
    }

### Primary Functions

    namespace glz
    {
       // Generate a patch document that transforms 'source' into 'target'
       // Guarantees:
       //   auto doc = source;
       //   patch(doc, diff(source, target));
       //   assert(doc == target);
       [[nodiscard]] expected<patch_document, error_ctx> diff(
          const generic& source,
          const generic& target,
          diff_opts opts = {}
       );

       // Apply a patch document to a JSON value (in-place modification)
       [[nodiscard]] error_ctx patch(
          generic& document,
          const patch_document& ops,
          patch_opts opts = {}
       );

       // Apply a patch document, returning a new value (non-mutating)
       [[nodiscard]] expected<generic, error_ctx> patched(
          const generic& document,
          const patch_document& ops,
          patch_opts opts = {}
       );

       // Convenience overloads for JSON string input
       [[nodiscard]] expected<patch_document, error_ctx> diff(
          std::string_view source_json,
          std::string_view target_json,
          diff_opts opts = {}
       );

       [[nodiscard]] expected<std::string, error_ctx> patch_json(
          std::string_view document_json,
          std::string_view patch_json,
          patch_opts opts = {}
       );
    }

### Options Structure

    namespace glz
    {
       struct diff_opts
       {
          // Generate move operations when a value is removed and added elsewhere
          // Default: false (only generates add/remove/replace like nlohmann)
          bool detect_moves = false;

          // Generate copy operations when identical values appear in target
          // Default: false
          bool detect_copies = false;

          // For arrays: use LCS (longest common subsequence) for smarter diffs
          // Default: false (simpler index-based comparison)
          bool array_lcs = false;
       };

       struct patch_opts
       {
          // If true, create intermediate objects/arrays for add operations
          // Default: false (RFC 6902 compliant - parent must exist)
          // RFC 6902 Section 4.1: "The target location MUST reference one of:
          // the root of the target document, a member to add to an existing object,
          // or an element to add to an existing array."
          bool create_intermediate = false;

          // If true, rollback all changes on any operation failure
          // Default: true (atomic application)
          // Note: Requires O(n) space for backup copy of document
          bool atomic = true;
       };
    }

## Detailed Design

### Building on Existing Infrastructure

Glaze already has JSON Pointer support that this implementation should build upon:

Existing Function | Location | Usage
--- | --- | ---
`navigate_to(generic*, sv)` | `generic.hpp` | Navigate to a location in generic JSON
`seek(func, value, json_ptr)` | `seek.hpp` | Call function on value at path
`glz::get<T>(value, path)` | `seek.hpp` | Get typed reference at path
`glz::set(value, path, val)` | `seek.hpp` | Set value at path

The patch implementation should reuse these rather than creating parallel infrastructure.

### 1. Diff Algorithm

The diff algorithm recursively compares two `generic` values and generates patch operations.

#### Pseudocode

    diff(source, target, path) -> operations:
        if source.type != target.type:
            return [replace(path, target)]

        switch source.type:
            case null, bool, number, string:
                if source != target:
                    return [replace(path, target)]
                return []

            case object:
                ops = []
                // Keys removed from source
                for key in source.keys():
                    if key not in target:
                        ops.append(remove(path + "/" + escape(key)))

                // Keys added or modified
                for key in target.keys():
                    child_path = path + "/" + escape(key)
                    if key not in source:
                        ops.append(add(child_path, target[key]))
                    else:
                        ops.extend(diff(source[key], target[key], child_path))
                return ops

            case array:
                // Simple approach: compare by index
                ops = []
                min_len = min(source.size(), target.size())

                for i in range(min_len):
                    ops.extend(diff(source[i], target[i], path + "/" + str(i)))

                // Handle length differences
                if target.size() > source.size():
                    for i in range(min_len, target.size()):
                        ops.append(add(path + "/" + str(i), target[i]))
                else:
                    // Remove from end to avoid index shifting
                    for i in range(source.size() - 1, min_len - 1, -1):
                        ops.append(remove(path + "/" + str(i)))

                return ops

#### JSON Pointer Escaping (RFC 6901)

    // Escape special characters in JSON Pointer tokens
    inline std::string escape_json_ptr(std::string_view token)
    {
       std::string result;
       result.reserve(token.size());
       for (char c : token) {
          if (c == '~') result += "~0";
          else if (c == '/') result += "~1";
          else result += c;
       }
       return result;
    }

    // Unescape JSON Pointer tokens
    // Returns error for malformed sequences (e.g., "~" at end, "~2")
    // RFC 6901: "~" MUST be followed by "0" or "1"
    inline expected<std::string, error_ctx> unescape_json_ptr(std::string_view token)
    {
       std::string result;
       result.reserve(token.size());
       for (size_t i = 0; i < token.size(); ++i) {
          if (token[i] == '~') {
             if (i + 1 >= token.size()) {
                return unexpected(error_ctx{error_code::invalid_json_pointer});
             }
             if (token[i + 1] == '0') {
                result += '~';
                ++i;
             }
             else if (token[i + 1] == '1') {
                result += '/';
                ++i;
             }
             else {
                return unexpected(error_ctx{error_code::invalid_json_pointer});
             }
          }
          else {
             result += token[i];
          }
       }
       return result;
    }

### 2. Patch Algorithm

The patch algorithm applies operations sequentially, with optional atomic rollback.

#### Operation Implementations

    // Add: Insert value at path
    // - If path points to array index, insert at that position
    // - If path points to object key, set that key
    // - If path ends with "-", append to array
    // - Parent must exist (unless create_intermediate option is set)
    error_ctx apply_add(generic& doc, sv path, const generic& value, const patch_opts& opts);

    // Remove: Delete value at path
    // - Path must exist
    error_ctx apply_remove(generic& doc, sv path);

    // Replace: Set value at existing path
    // - Path must exist
    error_ctx apply_replace(generic& doc, sv path, const generic& value);

    // Move: Remove from 'from', add to 'path'
    // - Equivalent to remove(from) + add(path, removed_value)
    // - 'from' must exist
    // - Cannot move a value into itself (path cannot be prefix of from)
    error_ctx apply_move(generic& doc, sv from, sv path, const patch_opts& opts);

    // Copy: Copy value from 'from' to 'path'
    // - Equivalent to add(path, get(from))
    // - 'from' must exist
    error_ctx apply_copy(generic& doc, sv from, sv path, const patch_opts& opts);

    // Test: Verify value at path equals expected
    // - Returns error if not equal or path doesn't exist
    error_ctx apply_test(const generic& doc, sv path, const generic& expected);

#### Atomic Application

    error_ctx patch(generic& document, const patch_document& ops, patch_opts opts)
    {
       if (opts.atomic) {
          // Deep copy for rollback - requires O(n) space
          generic backup = document;

          for (size_t i = 0; i < ops.size(); ++i) {
             auto ec = apply_operation(document, ops[i], opts);
             if (ec) {
                document = std::move(backup);  // Rollback
                ec.operation_index = i;  // Include which operation failed
                return ec;
             }
          }
       }
       else {
          for (size_t i = 0; i < ops.size(); ++i) {
             auto ec = apply_operation(document, ops[i], opts);
             if (ec) {
                ec.operation_index = i;
                return ec;
             }
          }
       }
       return {};
    }

### 3. Helper Functions Required

New helper functions needed for `glz::generic`:

    namespace glz
    {
       // Navigate to parent and get the final key/index
       // Returns {parent_ref, key} or error if path is invalid
       expected<std::pair<std::reference_wrapper<generic>, std::string>, error_ctx>
       navigate_to_parent(generic& root, sv json_ptr);

       // Insert a value at a JSON Pointer path
       // Parent must exist unless create_intermediate is true
       error_ctx insert_at(generic& root, sv path, generic value, bool create_intermediate = false);

       // Remove a value at a JSON Pointer path
       // Returns the removed value, or error if path doesn't exist
       expected<generic, error_ctx> remove_at(generic& root, sv path);

       // Deep equality comparison for generic values
       bool equal(const generic& a, const generic& b);
    }

## Error Handling

### Error Codes

New error codes to add to `error_code` enum:

    enum struct error_code : uint32_t {
       // ... existing codes ...

       // JSON Pointer errors
       invalid_json_pointer,         // Malformed JSON pointer (e.g., "~" at end, "~2")

       // JSON Patch errors
       patch_test_failed,            // Test operation value mismatch
       patch_path_not_found,         // Path does not exist for remove/replace/test
       patch_from_not_found,         // 'from' path does not exist for move/copy
       patch_invalid_array_index,    // Array index out of bounds or invalid
       patch_move_into_self,         // Cannot move a value into itself
       patch_invalid_operation,      // Unknown operation type
       patch_missing_value,          // 'value' field missing for add/replace/test
       patch_missing_from,           // 'from' field missing for move/copy
    };

### Error Context

Errors should include: - The operation index that failed - The path that caused the error - For test failures: expected vs actual values (in error message)

## File Organization

    include/glaze/json/
    ├── patch.hpp           # Main patch/diff API
    └── generic.hpp         # (existing) Add helper functions

    tests/json_test/
    └── json_patch_test.cpp # Comprehensive test suite

## Testing Strategy

### Unit Tests

1. Basic operations - Each operation type in isolation
2. Round-trip - `patch(source, diff(source, target))` yields `target`
3. RFC 6902 test suite - Use official JSON Patch test cases from json-patch-tests
4. Edge cases:
5. Empty documents
6. Nested arrays/objects
7. Special characters in keys (escaping)
8. Array index "-" (append)
9. Deep nesting

10. Large documents

11. Malformed JSON Pointers:

12. `"/a~"` - tilde at end
13. `"/a~2b"` - invalid escape sequence
14. `"//a"` - empty segment

15. `"a/b"` - missing leading slash

16. Type mismatches:

17. Add to a string value
18. Remove from a number

19. Array index on object

20. Unicode keys:

21. `{"日本語": 1}` and proper escaping
22. Emoji keys

23. Multi-byte UTF-8

24. Root document operations:

25. Path `""` (empty string = root)

26. Replace entire document

27. Array index edge cases:

28. Empty array operations
29. Index beyond bounds
30. Negative indices (should fail)

31. Leading zeros (e.g., `"/01"`)

32. Self-referential operations:

    - Move where `from` is prefix of `path`
    - Copy to same location

### Example Test Cases

    ut::test("diff replace primitive") = [] {
       auto source = glz::read_json<glz::generic>(R"({"a": 1})");
       auto target = glz::read_json<glz::generic>(R"({"a": 2})");

       auto patch = glz::diff(*source, *target);
       ut::expect(patch.has_value());
       ut::expect(patch->size() == 1);
       ut::expect((*patch)[0].op == glz::patch_op_type::replace);
       ut::expect((*patch)[0].path == "/a");
    };

    ut::test("patch round-trip") = [] {
       auto source = glz::read_json<glz::generic>(R"({"a": [1, 2], "b": "hello"})");
       auto target = glz::read_json<glz::generic>(R"({"a": [1, 3], "c": true})");

       auto patch = glz::diff(*source, *target);
       ut::expect(patch.has_value());

       auto result = *source;
       auto ec = glz::patch(result, *patch);
       ut::expect(!ec);
       ut::expect(glz::equal(result, *target));
    };

    ut::test("remove operation serialization") = [] {
       glz::patch_op op{};
       op.op = glz::patch_op_type::remove;
       op.path = "/foo";
       // value and from are std::nullopt

       auto json = glz::write_json(op);
       ut::expect(json == R"({"op":"remove","path":"/foo"})");
    };

    ut::test("malformed json pointer") = [] {
       auto result = glz::unescape_json_ptr("a~");
       ut::expect(!result.has_value());
       ut::expect(result.error().ec == glz::error_code::invalid_json_pointer);
    };

## Performance Considerations

1. Avoid unnecessary copies - Use move semantics where possible
2. Pre-allocate - Reserve vector capacity based on document size estimates
3. Reuse existing infrastructure - Build on `navigate_to()`, `seek()`, etc.
4. Lazy evaluation - For large documents, consider streaming diff generation

### Complexity

Operation | Time Complexity | Space Complexity
--- | --- | ---
diff (objects) | O(n + m) | O(d) where d = diff size
diff (arrays) | O(max(n, m)) | O(d)
patch | O(p × log(n)) | O(1) non-atomic, O(n) atomic

Where n, m = document sizes, p = patch size, d = diff size

Note: Atomic mode requires a full deep copy of the document for rollback, which uses O(n) additional space. For very large documents where memory is a concern, users can disable atomic mode.

## Future Enhancements

1. JSON Merge Patch (RFC 7386) - Simpler but less expressive format
2. Compile-time struct diff - Leverage glaze's reflection for typed diffs
3. Streaming patch application - For very large documents
4. Bidirectional diff - Generate both forward and reverse patches
5. Conflict detection - For three-way merge scenarios

## Design Decisions

These questions have been resolved based on RFC compliance and practical considerations:

Question | Decision | Rationale
--- | --- | ---
Array diffing | Index-based default | O(n) vs O(n×m) for LCS; LCS rarely needed
Move/copy detection | Off by default | Adds hashing overhead; matches nlohmann behavior
Patch format | Array-only | RFC 6902 specifies array format only
Error recovery | Strict abort | RFC 6902 requires abort on first error
`create_intermediate` | `false` default | RFC 6902 requires parent to exist

## References

- RFC 6902 - JSON Patch
- RFC 6901 - JSON Pointer
- RFC 7386 - JSON Merge Patch
- nlohmann/json patch implementation
- JSON Patch test suite