JSON Deep Merge Fix

Project: duckdb/duckdb | Language: C++ | Concepts: memory-management, error-handling, refactoring
Difficulty: mid
Link: https://github.com/duckdb/duckdb/pull/24984

The problem

The json_deep_merge() function in the DuckDB JSON extension used unbounded recursion to merge deeply nested JSON objects. If the input was too deeply nested, this caused a stack overflow and crashed the process. Other JSON functions (json_merge_patch_diff, json_normalize, etc.) had similar issues.

Why it's non-trivial

A naive fix might just add a recursion depth check, but this would still risk stack overflows for deeply nested objects. Making the function iterative instead of recursive is more robust but requires careful handling of the merge logic and state, especially to preserve input/output order and correct merging semantics.

The approach

1. Introduce a maximum recursion depth constant

+	//! Maximum recursion depth for recursive functions
+	static constexpr idx_t MAX_RECURSION_DEPTH = 128;

What it does:
Defines a global maximum recursion depth for JSON functions to prevent stack overflows.

2. Refactor DeepMerge to iterative (stack-based) implementation

Old recursive code:

-static yyjson_mut_val *DeepMerge(yyjson_mut_doc *doc, yyjson_mut_val *orig, yyjson_mut_val *patch) {
-	// If patch is not an object, it replaces orig entirely (unless null)
-	if (!yyjson_mut_is_obj(patch)) {
-		if (unsafe_yyjson_is_null(patch) && orig) {
-			return yyjson_mut_val_mut_copy(doc, orig);
-		}
-		return yyjson_mut_val_mut_copy(doc, patch);
-	}
-	// ... recursive merge logic ...
-	auto merged_val = DeepMerge(doc, orig_val, patch_val);
-	// ...
-}

New iterative code:

+static yyjson_mut_val *DeepMerge(yyjson_mut_doc *doc, yyjson_mut_val *orig_root, yyjson_mut_val *patch_root) {
+	if (!yyjson_mut_is_obj(orig_root) || !yyjson_mut_is_obj(patch_root)) {
+		if (unsafe_yyjson_is_null(patch_root)) {
+			return yyjson_mut_val_mut_copy(doc, orig_root);
+		}
+		return yyjson_mut_val_mut_copy(doc, patch_root);
+	}
+
+	auto root_builder = yyjson_mut_obj(doc);
+
+	// Initialize stack
+	struct stack_item {
+		yyjson_mut_val *key;
+		yyjson_mut_val *orig_node;
+		yyjson_mut_val *patch_node;
+		yyjson_mut_val *builder;
+	};
+	auto stack = std::vector<stack_item>();
+	stack.emplace_back(stack_item {nullptr, orig_root, patch_root, root_builder});
+
+	// loop over each level of nesting
+	while (!stack.empty()) {
+		auto nodes = stack.back();
+		stack.pop_back();
+		// ... merge logic using stack instead of recursion ...
+	}
+	return root_builder;
+}

What it does:
Replaces recursion with an explicit stack (std::vector<stack_item>), so deeply nested merges no longer risk stack overflow. Each stack frame holds the current key, original node, patch node, and builder object.

3. Add recursion depth checks to other recursive JSON functions

Example for json_merge_patch_diff:

-static yyjson_mut_val *ComputeDiff(yyjson_mut_doc *doc, yyjson_val *old_val, yyjson_val *new_val) {
+static yyjson_mut_val *ComputeDiff(yyjson_mut_doc *doc, yyjson_val *old_val, yyjson_val *new_val, idx_t depth = 0) {
+	if (depth >= JSONCommon::MAX_RECURSION_DEPTH) {
+		throw InvalidInputException("json_merge_patch_diff: JSON exceeds maximum recursion depth of %d",
+		                            JSONCommon::MAX_RECURSION_DEPTH);
+	}

What it does:
Adds a depth counter and throws an exception if the maximum is exceeded, preventing stack overflow.

4. Mark functions as fallible

+	fun.SetFallible();

What it does:
Marks the function as potentially throwing exceptions, so the system can handle errors gracefully.

5. Add regression tests for deeply nested JSON

Example test:

+# Vuln151: json_deep_merge()
+query I
+SELECT json(json_deep_merge(x, x)) = json(x)
+FROM (SELECT repeat('{"a":', 20000) || '1' || repeat('}', 20000) AS x)
+----
+true

What it does:
Verifies that the new implementation can handle very deeply nested JSON without crashing.

6. Fix input/output order preservation

From the review, a test and code fix were added to ensure that the order of keys in the output matches the input when merging.

+# Input and output order should be the same
+query T
+SELECT json_deep_merge('{"a":1,"b":2}', '{"a":null}')
+----
+{"a":1,"b":2}

What it does:
Ensures that the merge function preserves key order, matching expected behavior.

From the review thread

lnkuiper: Thanks for the PR! I think a related test is failing.

We also typically use StackChecker for this, but I'm not sure if that's applicable here. Alternatively, the long-term solution is to eliminate recursion entirely for many JSON functions, keeping stack frames in a vector instead. If we do this, we should tackle multiple functions in a unified way, e.g., also tackle json_transform.

lnkuiper: Thanks! I think this looks good! It's a bit of shame but some of the yyjson functions themselves are recursive, which we can't do much about.

One thing needs to be fixed, then this is good to go from my side:

  SELECT json_deep_merge('{"a":1,"b":2}', '{"a":null}');
  -- base: {"a":1,"b":2}
  -- PR:   {"b":2,"a":1}

lghavami: @lnkuiper fixed the behavior + added a test for it

Takeaways

• Avoid recursion for deeply nested data structures in systems code; use explicit stacks to prevent stack overflows.
• Always enforce maximum recursion depth or iteration limits when traversing user-provided nested data.
• When refactoring for safety, ensure that observable behaviors (like key order in JSON objects) are preserved and covered by regression tests.