1/**
2 * The `JsonPatch` module computes and applies deterministic patch documents for
3 * JSON values. A patch is an ordered list of `add`, `remove`, and `replace`
4 * operations addressed by JSON Pointer paths. Use it to describe the structural
5 * difference between two JSON documents, serialize that difference, and replay
6 * it without mutating the original input.
7 *
8 * @since 4.0.0
9 */
10import * as InternalRecord from "./internal/record.ts"
11import { escapeToken, unescapeToken } from "./JsonPointer.ts"
12import type * as Schema from "./Schema.ts"
13
14/**
15 * A single JSON Patch operation.
16 *
17 * **When to use**
18 *
19 * Use to manually construct patch operations, accept patch operations from
20 * callers, or type-check patch operation structures.
21 *
22 * **Details**
23 *
24 * Represents one transformation step in a JSON Patch document. This is a subset
25 * of RFC 6902, restricted to operations that can be applied deterministically
26 * without additional context. All fields are readonly, paths use JSON Pointer
27 * syntax, and the empty string `""` refers to the root document. Operations are
28 * discriminated by the `op` field, and the optional `description` field can be
29 * used for documentation.
30 *
31 * **Example** (Defining all operation types)
32 *
33 * ```ts import.meta.vitest
34 * import { JsonPatch } from "effect"
35 *
36 * const addOp: JsonPatch.JsonPatchOperation = {
37 * op: "add",
38 * path: "/users/-",
39 * value: { id: 1, name: "Alice" }
40 * }
41 *
42 * const removeOp: JsonPatch.JsonPatchOperation = {
43 * op: "remove",
44 * path: "/users/0"
45 * }
46 *
47 * const replaceOp: JsonPatch.JsonPatchOperation = {
48 * op: "replace",
49 * path: "/users/0/name",
50 * value: "Bob"
51 * }
52 *
53 * Array.of(addOp.op, removeOp.op, replaceOp.op) // => ["add", "remove", "replace"]
54 * ```
55 *
56 * @see {@link JsonPatch} for the array of operations forming a complete patch
57 * @see {@link get} to compute operations automatically from value differences
58 * @see {@link apply} to apply operations to transform documents
59 * @category models
60 * @since 4.0.0
61 */
62export type JsonPatchOperation =
63 | {
64 readonly op: "add"
65 /**
66 * JSON Pointer to the target location. For arrays, the last token may be `-`
67 * to append.
68 *
69 * **When to use**
70 *
71 * Use to identify where the `add` operation inserts its value.
72 */
73 readonly path: string
74 readonly value: Schema.Json
75 readonly description?: string
76 }
77 | {
78 readonly op: "remove"
79 /**
80 * JSON Pointer to the target location.
81 *
82 * **When to use**
83 *
84 * Use to identify which location the `remove` operation deletes.
85 */
86 readonly path: string
87 readonly description?: string
88 }
89 | {
90 readonly op: "replace"
91 /**
92 * JSON Pointer to the target location. Use `""` to replace the root document.
93 *
94 * **When to use**
95 *
96 * Use to identify which location the `replace` operation overwrites.
97 */
98 readonly path: string
99 readonly value: Schema.Json
100 readonly description?: string
101 }
102
103/**
104 * A JSON Patch document (an ordered list of operations).
105 *
106 * **When to use**
107 *
108 * Use to store, serialize, pass, or validate complete patch documents.
109 *
110 * **Details**
111 *
112 * Represents a complete transformation as a readonly sequence of immutable
113 * operations. Operations are applied sequentially from first to last, and later
114 * operations observe the document state produced by earlier operations. An empty
115 * array represents a no-op patch and returns the original document.
116 *
117 * **Example** (Defining a multi-operation patch)
118 *
119 * ```ts import.meta.vitest
120 * import { JsonPatch } from "effect"
121 *
122 * const patch: JsonPatch.JsonPatch = [
123 * { op: "add", path: "/items/-", value: "apple" },
124 * { op: "replace", path: "/count", value: 5 },
125 * { op: "remove", path: "/oldField" }
126 * ]
127 *
128 * JsonPatch.apply(patch, { items: [], count: 3, oldField: "value" }) // => { items: ["apple"], count: 5 }
129 * ```
130 *
131 * @see {@link JsonPatchOperation} for individual operation types
132 * @see {@link get} to generate patches from value differences
133 * @see {@link apply} to execute patches to transform documents
134 * @category models
135 * @since 4.0.0
136 */
137export type JsonPatch = ReadonlyArray<JsonPatchOperation>
138
139/**
140 * Computes a structural patch that transforms `oldValue` into `newValue`.
141 *
142 * **When to use**
143 *
144 * Use to compute a JSON Patch from before and after JSON documents, detect
145 * structural changes, or create deterministic update operations.
146 *
147 * **Details**
148 *
149 * Generates a structural diff between two JSON values, producing a patch that
150 * yields `newValue` when applied to `oldValue`. It returns an empty array when
151 * values are identical, recursively diffs nested structures, emits root
152 * `replace` operations for primitive changes, and processes object keys in
153 * sorted order for stable output.
154 *
155 * **Gotchas**
156 *
157 * Arrays are compared by index position, with no move or copy detection. Array
158 * removals are emitted from highest to lowest index to prevent index shifting.
159 * The output is deterministic but not guaranteed to be minimal.
160 *
161 * **Example** (Computing object diff)
162 *
163 * ```ts import.meta.vitest
164 * import { JsonPatch } from "effect"
165 *
166 * const oldValue = { users: [{ id: 1, name: "Alice" }], count: 1 }
167 * const newValue = { users: [{ id: 1, name: "Bob" }, { id: 2, name: "Charlie" }], count: 2 }
168 *
169 * const patch = JsonPatch.get(oldValue, newValue)
170 * patch[0] // => { op: "replace", path: "/count", value: 2 }
171 * patch[1] // => { op: "replace", path: "/users/0/name", value: "Bob" }
172 * patch[2] // => { op: "add", path: "/users/1", value: { id: 2, name: "Charlie" } }
173 * ```
174 *
175 * @see {@link apply} to apply the generated patch to a document
176 * @see {@link JsonPatchOperation} for the operation types in the patch
177 * @category transforming
178 * @since 4.0.0
179 */
180export function get(oldValue: Schema.Json, newValue: Schema.Json): JsonPatch {
181 const patches: Array<JsonPatchOperation> = []
182 getLoop(oldValue, newValue, "", patches)
183 return patches
184}
185
186function getLoop(
187 oldValue: Schema.Json,
188 newValue: Schema.Json,
189 path: string,
190 patches: Array<JsonPatchOperation>
191): void {
192 if (Object.is(oldValue, newValue)) return
193 if (Array.isArray(oldValue) && Array.isArray(newValue)) {
194 const len1 = oldValue.length
195 const len2 = newValue.length
196
197 // Compare shared prefix by index
198 const shared = Math.min(len1, len2)
199 for (let i = 0; i < shared; i++) {
200 getLoop(oldValue[i], newValue[i], `${path}/${i}`, patches)
201 }
202
203 // Remove from end to start so later indices do not shift.
204 for (let i = len1 - 1; i >= len2; i--) {
205 patches.push({ op: "remove", path: `${path}/${i}` })
206 }
207
208 // Add from beginning to end.
209 for (let i = len1; i < len2; i++) {
210 patches.push({ op: "add", path: `${path}/${i}`, value: newValue[i] })
211 }
212
213 return
214 }
215
216 if (isJsonObject(oldValue) && isJsonObject(newValue)) {
217 const keys1 = Object.keys(oldValue)
218 const keys2 = Object.keys(newValue)
219 const allKeys = Array.from(new Set([...keys1, ...keys2])).sort()
220
221 for (const key of allKeys) {
222 const keyPath = `${path}/${escapeToken(key)}`
223 const hasKey1 = Object.hasOwn(oldValue, key)
224 const hasKey2 = Object.hasOwn(newValue, key)
225
226 if (hasKey1 && hasKey2) {
227 getLoop(oldValue[key], newValue[key], keyPath, patches)
228 } else if (!hasKey1 && hasKey2) {
229 patches.push({ op: "add", path: keyPath, value: newValue[key] })
230 } else {
231 patches.push({ op: "remove", path: keyPath })
232 }
233 }
234
235 return
236 }
237
238 patches.push({ op: "replace", path, value: newValue })
239}
240
241/**
242 * Applies a JSON Patch to a JSON document.
243 *
244 * **When to use**
245 *
246 * Use to execute patches generated by {@link get}, transform documents
247 * with manually constructed patches, or process patch operations from external
248 * sources.
249 *
250 * **Details**
251 *
252 * Executes patch operations sequentially, so later operations see changes made
253 * by earlier operations. It never mutates the input document; array and object
254 * operations copy the affected containers. An empty patch returns the original
255 * reference, and a root replace (`path: ""`) returns the provided value
256 * directly.
257 *
258 * **Gotchas**
259 *
260 * Invalid paths, missing properties, and out-of-bounds array indices throw
261 * errors.
262 *
263 * **Example** (Applying a patch)
264 *
265 * ```ts import.meta.vitest
266 * import { JsonPatch } from "effect"
267 *
268 * const document = { items: [1, 2, 3], total: 6 }
269 * const patch: JsonPatch.JsonPatch = [
270 * { op: "add", path: "/items/-", value: 4 },
271 * { op: "replace", path: "/total", value: 10 }
272 * ]
273 *
274 * JsonPatch.apply(patch, document) // => { items: [1, 2, 3, 4], total: 10 }
275 * ```
276 *
277 * @see {@link get} to generate patches from value differences
278 * @see {@link JsonPatchOperation} for the operation types being applied
279 * @category transforming
280 * @since 4.0.0
281 */
282export function apply(patch: JsonPatch, oldValue: Schema.Json): Schema.Json {
283 let doc = oldValue
284
285 for (const op of patch) {
286 doc = applyOperation(doc, op)
287 }
288
289 return doc
290}
291
292function isJsonObject(value: unknown): value is Schema.JsonObject {
293 return typeof value === "object" && value !== null && !Array.isArray(value)
294}
295
296/**
297 * Tokenize a JSON Pointer into unescaped reference tokens.
298 *
299 * - `""` (empty pointer) refers to the root and returns `[]`
300 * - Non-empty pointers must start with `/`
301 */
302function tokenize(pointer: string): Array<string> {
303 if (pointer === "") return []
304 if (pointer.charCodeAt(0) !== 47 /* "/" */) {
305 throw new Error(`Invalid JSON Pointer, it must start with "/": ${JSON.stringify(pointer)}`)
306 }
307 return pointer.split("/").slice(1).map(unescapeToken)
308}
309
310/** Converts a JSON Pointer reference token to a non-negative array index. */
311function toJsonPointerArrayIndex(token: string): number {
312 if (!/^(0|[1-9]\d*)$/.test(token)) {
313 throw new Error(`Invalid array index: "${token}"`)
314 }
315 return Number(token)
316}
317
318function applyOperation(doc: Schema.Json, op: JsonPatchOperation): Schema.Json {
319 if (op.path === "") {
320 if (op.op === "remove") throw new Error("Unsupported operation at the root")
321 return op.value
322 }
323
324 const resolved = resolveParent(doc, op.path)
325 if (resolved === null) {
326 throw new Error(`Cannot ${op.op} at "${op.path}" (parent not found or not a container).`)
327 }
328
329 const { lastToken, parent, stack } = resolved
330
331 if (Array.isArray(parent)) {
332 if (lastToken === "-" && op.op !== "add") {
333 throw new Error(`"-" is not valid for ${op.op} at "${op.path}".`)
334 }
335 const index = lastToken === "-" ? parent.length : toJsonPointerArrayIndex(lastToken)
336 const maxIndex = op.op === "add" ? parent.length : parent.length - 1
337 if (index > maxIndex) throw new Error(`Array index out of bounds at "${op.path}".`)
338 const updated = parent.slice()
339 if (op.op === "add") updated.splice(index, 0, op.value)
340 else if (op.op === "remove") updated.splice(index, 1)
341 else updated[index] = op.value
342 return rebuildFromStack(stack, updated)
343 }
344
345 if (isJsonObject(parent)) {
346 if (op.op !== "add" && !Object.hasOwn(parent, lastToken)) {
347 throw new Error(`Property "${lastToken}" does not exist at "${op.path}".`)
348 }
349 const updated = { ...parent }
350 if (op.op === "remove") delete updated[lastToken]
351 else InternalRecord.assignProperty(updated, lastToken, op.value)
352 return rebuildFromStack(stack, updated)
353 }
354
355 throw new Error(`Cannot ${op.op} at "${op.path}" (parent not found or not a container).`)
356}
357
358type StackEntry = { readonly container: unknown; readonly token: number | string }
359
360// Walk to the parent of `pointer`, recording the path.
361// Returns null if the parent path cannot be resolved.
362function resolveParent(
363 doc: Schema.Json,
364 pointer: string
365): { readonly stack: ReadonlyArray<StackEntry>; readonly parent: unknown; readonly lastToken: string } | null {
366 const tokens = tokenize(pointer)
367 if (tokens.length === 0) return null // caller handles root
368
369 const lastToken = tokens[tokens.length - 1]
370 const stack: Array<StackEntry> = []
371 let cur: unknown = doc
372
373 for (let i = 0; i < tokens.length - 1; i++) {
374 const token = tokens[i]
375
376 if (Array.isArray(cur)) {
377 const idx = toJsonPointerArrayIndex(token)
378 if (idx >= cur.length) return null
379 stack.push({ container: cur, token: idx })
380 cur = cur[idx]
381 continue
382 }
383
384 if (isJsonObject(cur)) {
385 if (!Object.hasOwn(cur, token)) return null
386 stack.push({ container: cur, token })
387 cur = cur[token]
388 continue
389 }
390
391 return null
392 }
393
394 return { stack, parent: cur, lastToken }
395}
396
397// Rebuild the document by writing `newParent` back through `stack`.
398function rebuildFromStack(stack: ReadonlyArray<StackEntry>, newParent: Schema.Json): Schema.Json {
399 let acc: Schema.Json = newParent
400
401 for (let i = stack.length - 1; i >= 0; i--) {
402 const { container, token } = stack[i]
403
404 if (Array.isArray(container)) {
405 const copy = container.slice()
406 copy[token as number] = acc
407 acc = copy
408 } else {
409 const copy = { ...(container as Schema.JsonObject) }
410 InternalRecord.assignProperty(copy, token as string, acc)
411 acc = copy
412 }
413 }
414
415 return acc
416}