26654265033

Committed 29 May 2026 06:14PM UTC coverage: 92.115% (+0.008%) from 92.107%

Build # 26654265033

Build Type

push

github

Committed by

web-flow

Commit Message

Vendor JSON Patch library (#9335)

Signed-off-by: Matt Willer <matt@medplum.com>

Coverage Stats

22456 of 25218 branches covered (89.05%)

Branch coverage included in aggregate %.

218 of 230 new or added lines in 5 files covered. (94.78%)

1 existing line in 1 file now uncovered.

35805 of 38030 relevant lines covered (94.15%)

23356.37 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.9

/packages/core/src/patch/diff.ts

/* eslint-disable header/header */
/*
 * Copyright © 2014-2021 Christopher Brown <io@henrian.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
 * documentation files (the "Software"), to deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
import type { Pointer } from './pointer'; // we only need this for type inference
import { hasOwnProperty, objectType } from './util';

/*
All diff* functions should return a list of operations, often empty.

Each operation should be an object with two to four fields:
* `op`: the name of the operation; one of "add", "remove", "replace", "move",
  "copy", or "test".
* `path`: a JSON pointer string
* `from`: a JSON pointer string
* `value`: a JSON value

The different operations have different arguments.
* "add": [`path`, `value`]
* "remove": [`path`]
* "replace": [`path`, `value`]
* "move": [`from`, `path`]
* "copy": [`from`, `path`]
* "test": [`path`, `value`]

Currently this only really differentiates between Arrays, Objects, and
Everything Else, which is pretty much just what JSON substantially
differentiates between.
*/

export interface AddOperation {
  op: 'add';
  path: string;
  value: any;
}
export interface RemoveOperation {
  op: 'remove';
  path: string;
}
export interface ReplaceOperation {
  op: 'replace';
  path: string;
  value: any;
}
export interface MoveOperation {
  op: 'move';
  from: string;
  path: string;
}
export interface CopyOperation {
  op: 'copy';
  from: string;
  path: string;
}
export interface TestOperation {
  op: 'test';
  path: string;
  value: any;
}

export type Operation =
  | AddOperation
  | RemoveOperation
  | ReplaceOperation
  | MoveOperation
  | CopyOperation
  | TestOperation;

export function isDestructive({ op }: Operation): boolean {
  return op === 'remove' || op === 'replace' || op === 'copy' || op === 'move';
}

export type Diff = (input: any, output: any, ptr: Pointer) => Operation[];
/**
 * VoidableDiff exists to allow the user to provide a partial diff(...) function,
 * falling back to the built-in diffAny(...) function if the user-provided function
 * returns void.
 */
export type VoidableDiff = (input: any, output: any, ptr: Pointer) => Operation[] | undefined;

/**
 * List the keys in `minuend` that are not in `subtrahend`.
 *
 * A key is only considered if it is both 1) an own-property (o.hasOwnProperty(k))
 * of the object, and 2) has a value that is not undefined. This is to match JSON
 * semantics, where JSON object serialization drops keys with undefined values.
 *
 * @param minuend - Object of interest
 * @param subtrahend - Object of comparison
 * @returns Array of keys that are in `minuend` but not in `subtrahend`.
 */
export function subtract(minuend: { [index: string]: any }, subtrahend: { [index: string]: any }): string[] {
  const keys: string[] = [];
  for (const key in minuend) {
    if (
      hasOwnProperty.call(minuend, key) &&
      minuend[key] !== undefined &&
      !(hasOwnProperty.call(subtrahend, key) && subtrahend[key] !== undefined)
    ) {
      keys.push(key);
    }
  }
  return keys;
}

/**
 * List the keys that shared by all `objects`.
 *
 * The semantics of what constitutes a "key" is described in {@link subtract}.
 *
 * @param objects - Array of objects to compare
 * @returns Array of keys that are in ("own-properties" of) every object in `objects`.
 */
export function intersection(objects: ArrayLike<{ [index: string]: any }>): string[] {
  const length = objects.length;
  // prepare empty counter to keep track of how many objects each key occurred in
  const counter: { [index: string]: number } = {};
  // go through each object and increment the counter for each key in that object
  for (let i = 0; i < length; i++) {
    const object = objects[i];
    for (const key in object) {
      if (hasOwnProperty.call(object, key) && object[key] !== undefined) {
        counter[key] = (counter[key] || 0) + 1;
      }
    }
  }
  // now delete all keys from the counter that were not seen in every object
  for (const key in counter) {
    if (counter[key] < length) {
      delete counter[key];
    }
  }
  // finally, extract whatever keys remain in the counter
  return Object.keys(counter);
}

/**
 * List the keys that shared by all `a` and `b`.
 *
 * The semantics of what constitutes a "key" is described in {@link subtract}.
 *
 * @param a - First object to compare
 * @param b - Second object to compare
 * @returns Array of keys that are in ("own-properties" of) `a` and `b`.
 */
function intersection2(a: { [index: string]: any }, b: { [index: string]: any }): string[] {
  const keys: string[] = [];
  for (const key in a) {
    if (hasOwnProperty.call(a, key) && a[key] !== undefined && hasOwnProperty.call(b, key) && b[key] !== undefined) {
      keys.push(key);
    }
  }
  return keys;
}

interface ArrayAdd {
  op: 'add';
  index: number;
  value: any;
}
interface ArrayRemove {
  op: 'remove';
  index: number;
}
interface ArrayReplace {
  op: 'replace';
  index: number;
  original: any;
  value: any;
}
/**
 * These are not proper Operation objects, but will be converted into
 * Operation objects eventually. {index} indicates the actual target position,
 * never 'end-of-array'
 */
type ArrayOperation = ArrayAdd | ArrayRemove | ArrayReplace;
function isArrayAdd(array_operation: ArrayOperation): array_operation is ArrayAdd {
  return array_operation.op === 'add';
}
function isArrayRemove(array_operation: ArrayOperation): array_operation is ArrayRemove {
  return array_operation.op === 'remove';
}

interface DynamicAlternative {
  operations: ArrayOperation[];
  /** Indicates the total cost of getting to this position. */
  cost: number;
}

function appendArrayOperation(base: DynamicAlternative, operation: ArrayOperation): DynamicAlternative {
  return {
    // the new operation must be pushed on the end
    operations: base.operations.concat(operation),
    cost: base.cost + 1,
  };
}

/**
 * Calculate the shortest sequence of operations to get from `input` to `output`,
 * using a dynamic programming implementation of the Levenshtein distance algorithm.
 *
 * To get from the input ABC to the output AZ we could just delete all the input
 * and say "insert A, insert Z" and be done with it. That's what we do if the
 * input is empty. But we can be smarter.
 *
 *           output
 *                A   Z
 *                -   -
 *           [0]  1   2
 * input A |  1  [0]  1
 *       B |  2  [1]  1
 *       C |  3   2  [2]
 *
 * 1) start at 0,0 (+0)
 * 2) keep A (+0)
 * 3) remove B (+1)
 * 4) replace C with Z (+1)
 *
 * If the `input` (source) is empty, they'll all be in the top row, resulting in an
 * array of 'add' operations.
 * If the `output` (target) is empty, everything will be in the left column,
 * resulting in an array of 'remove' operations.
 *
 * @param input - The original array.
 * @param output - The target array.
 * @param ptr - JSON Pointer.
 * @param diff - Diff function.
 * @returns A list of add/remove/replace operations.
 */
export function diffArrays<T>(input: T[], output: T[], ptr: Pointer, diff: Diff = diffAny): Operation[] {
  // set up cost matrix (very simple initialization: just a map)
  const max_length = Math.max(input.length, output.length);
  const memo = new Map<number, DynamicAlternative>([[0, { operations: [], cost: 0 }]]);

  /**
   * Calculate the cheapest sequence of operations required to get from
   * input.slice(0, i) to output.slice(0, j).
   * There may be other valid sequences with the same cost, but none cheaper.
   *
   * @param i - The row in the layout above
   * @param j - The column in the layout above
   * @returns An object containing a list of operations, along with the total cost of applying them
   *    (+1 for each add/remove/replace operation)
   */
  function dist(i: number, j: number): DynamicAlternative {
    // memoized
    const memo_key = i * max_length + j;
    let memoized = memo.get(memo_key);
    if (memoized === undefined) {
      // TODO: this !diff(...).length usage could/should be lazy
      if (i > 0 && j > 0 && !diff(input[i - 1], output[j - 1], ptr.add(String(i - 1))).length) {
        // equal (no operations => no cost)
        memoized = dist(i - 1, j - 1);
      } else {
        const alternatives: DynamicAlternative[] = [];
        if (i > 0) {
          // NOT topmost row
          const remove_base = dist(i - 1, j);
          const remove_operation: ArrayRemove = {
            op: 'remove',
            index: i - 1,
          };
          alternatives.push(appendArrayOperation(remove_base, remove_operation));
        }
        if (j > 0) {
          // NOT leftmost column
          const add_base = dist(i, j - 1);
          const add_operation: ArrayAdd = {
            op: 'add',
            index: i - 1,
            value: output[j - 1],
          };
          alternatives.push(appendArrayOperation(add_base, add_operation));
        }
        if (i > 0 && j > 0) {
          // TABLE MIDDLE
          // supposing we replaced it, compute the rest of the costs:
          const replace_base = dist(i - 1, j - 1);
          // okay, the general plan is to replace it, but we can be smarter,
          // recursing into the structure and replacing only part of it if
          // possible, but to do so we'll need the original value
          const replace_operation: ArrayReplace = {
            op: 'replace',
            index: i - 1,
            original: input[i - 1],
            value: output[j - 1],
          };
          alternatives.push(appendArrayOperation(replace_base, replace_operation));
        }
        // the only other case, i === 0 && j === 0, has already been memoized

        // the meat of the algorithm:
        // sort by cost to find the lowest one (might be several ties for lowest)
        // [4, 6, 7, 1, 2].sort((a, b) => a - b) -> [ 1, 2, 4, 6, 7 ]
        const best = alternatives.sort((a, b) => a.cost - b.cost)[0];
        memoized = best;
      }
      memo.set(memo_key, memoized);
    }
    return memoized;
  }
  // handle weird objects masquerading as Arrays that don't have proper length
  // properties by using 0 for everything but positive numbers
  const input_length = isNaN(input.length) || input.length <= 0 ? 0 : input.length;
  const output_length = isNaN(output.length) || output.length <= 0 ? 0 : output.length;
  const array_operations = dist(input_length, output_length).operations;
  const [padded_operations] = array_operations.reduce<[Operation[], number]>(
    ([operations, padding], array_operation) => {
      if (isArrayAdd(array_operation)) {
        const padded_index = array_operation.index + 1 + padding;
        const index_token = padded_index < input_length + padding ? String(padded_index) : '-';
        const operation = {
          op: array_operation.op,
          path: ptr.add(index_token).toString(),
          value: array_operation.value,
        };
        // padding++ // maybe only if array_operation.index > -1 ?
        return [operations.concat(operation), padding + 1];
      } else if (isArrayRemove(array_operation)) {
        const operation = {
          op: array_operation.op,
          path: ptr.add(String(array_operation.index + padding)).toString(),
        };
        // padding--
        return [operations.concat(operation), padding - 1];
      } else {
        // replace
        const replace_ptr = ptr.add(String(array_operation.index + padding));
        const replace_operations = diff(array_operation.original, array_operation.value, replace_ptr);
        return [operations.concat(...replace_operations), padding];
      }
    },
    [[], 0]
  );
  return padded_operations;
}

export function diffObjects(input: any, output: any, ptr: Pointer, diff: Diff = diffAny): Operation[] {
  // if a key is in input but not output -> remove it
  const operations: Operation[] = [];
  subtract(input, output).forEach((key) => {
    operations.push({ op: 'remove', path: ptr.add(key).toString() });
  });
  // if a key is in output but not input -> add it
  subtract(output, input).forEach((key) => {
    operations.push({ op: 'add', path: ptr.add(key).toString(), value: output[key] });
  });
  // if a key is in both, diff it recursively
  intersection2(input, output).forEach((key) => {
    operations.push(...diff(input[key], output[key], ptr.add(key)));
  });
  return operations;
}

/**
 * `diffAny()` returns an empty array if `input` and `output` are materially equal
 * (i.e., would produce equivalent JSON); otherwise it produces an array of patches
 * that would transform `input` into `output`.
 *
 * > Here, "equal" means that the value at the target location and the
 * > value conveyed by "value" are of the same JSON type, and that they
 * > are considered equal by the following rules for that type:
 * > o  strings: are considered equal if they contain the same number of
 * >    Unicode characters and their code points are byte-by-byte equal.
 * > o  numbers: are considered equal if their values are numerically
 * >    equal.
 * > o  arrays: are considered equal if they contain the same number of
 * >    values, and if each value can be considered equal to the value at
 * >    the corresponding position in the other array, using this list of
 * >    type-specific rules.
 * > o  objects: are considered equal if they contain the same number of
 * >    members, and if each member can be considered equal to a member in
 * >    the other object, by comparing their keys (as strings) and their
 * >    values (using this list of type-specific rules).
 * > o  literals (false, true, and null): are considered equal if they are
 * >    the same.
 *
 * @param input - The original value.
 * @param output - The target value.
 * @param ptr - JSON Pointer.
 * @param diff - Diff function.
 * @returns The list of operations to get form the original to target value.
 */
export function diffAny(input: any, output: any, ptr: Pointer, diff: Diff = diffAny): Operation[] {
  // strict equality handles literals, numbers, and strings (a sufficient but not necessary cause)
  if (input === output) {
    return [];
  }
  const input_type = objectType(input);
  const output_type = objectType(output);
  if (input_type === 'array' && output_type === 'array') {
    return diffArrays(input, output, ptr, diff);
  }
  if (input_type === 'object' && output_type === 'object') {
    return diffObjects(input, output, ptr, diff);
  }
  // at this point we know that input and output are materially different;
  // could be array -> object, object -> array, boolean -> undefined,
  // number -> string, or some other combination, but nothing that can be split
  // up into multiple patches: so `output` must replace `input` wholesale.
  return [{ op: 'replace', path: ptr.toString(), value: output }];
}

1	/* eslint-disable header/header */
2	/*
3	* Copyright © 2014-2021 Christopher Brown <io@henrian.com>
4	*
5	* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
6	* documentation files (the "Software"), to deal in the Software without restriction, including without limitation the
7	* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to
8	* permit persons to whom the Software is furnished to do so, subject to the following conditions:
9	*
10	* The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
11	*
12	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
13	* WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
14	* COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
15	* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
16	*/
17	import type { Pointer } from './pointer'; // we only need this for type inference
18	import { hasOwnProperty, objectType } from './util';
19
20	/*
21	All diff* functions should return a list of operations, often empty.
22
23	Each operation should be an object with two to four fields:
24	* `op`: the name of the operation; one of "add", "remove", "replace", "move",
25	"copy", or "test".
26	* `path`: a JSON pointer string
27	* `from`: a JSON pointer string
28	* `value`: a JSON value
29
30	The different operations have different arguments.
31	* "add": [`path`, `value`]
32	* "remove": [`path`]
33	* "replace": [`path`, `value`]
34	* "move": [`from`, `path`]
35	* "copy": [`from`, `path`]
36	* "test": [`path`, `value`]
37
38	Currently this only really differentiates between Arrays, Objects, and
39	Everything Else, which is pretty much just what JSON substantially
40	differentiates between.
41	*/
42
43	export interface AddOperation {
44	op: 'add';
45	path: string;
46	value: any;
47	}
48	export interface RemoveOperation {
49	op: 'remove';
50	path: string;
51	}
52	export interface ReplaceOperation {
53	op: 'replace';
54	path: string;
55	value: any;
56	}
57	export interface MoveOperation {
58	op: 'move';
59	from: string;
60	path: string;
61	}
62	export interface CopyOperation {
63	op: 'copy';
64	from: string;
65	path: string;
66	}
67	export interface TestOperation {
68	op: 'test';
69	path: string;
70	value: any;
71	}
72
73	export type Operation =
74	\| AddOperation
75	\| RemoveOperation
76	\| ReplaceOperation
77	\| MoveOperation
78	\| CopyOperation
79	\| TestOperation;
80
81	export function isDestructive({ op }: Operation): boolean {
82	return op === 'remove' \|\| op === 'replace' \|\| op === 'copy' \|\| op === 'move';	12✔
83	}
84
85	export type Diff = (input: any, output: any, ptr: Pointer) => Operation[];
86	/**
87	* VoidableDiff exists to allow the user to provide a partial diff(...) function,
88	* falling back to the built-in diffAny(...) function if the user-provided function
89	* returns void.
90	*/
91	export type VoidableDiff = (input: any, output: any, ptr: Pointer) => Operation[] \| undefined;
92
93	/**
94	* List the keys in `minuend` that are not in `subtrahend`.
95	*
96	* A key is only considered if it is both 1) an own-property (o.hasOwnProperty(k))
97	* of the object, and 2) has a value that is not undefined. This is to match JSON
98	* semantics, where JSON object serialization drops keys with undefined values.
99	*
100	* @param minuend - Object of interest
101	* @param subtrahend - Object of comparison
102	* @returns Array of keys that are in `minuend` but not in `subtrahend`.
103	*/
104	export function subtract(minuend: { [index: string]: any }, subtrahend: { [index: string]: any }): string[] {
105	const keys: string[] = [];	100✔
106	for (const key in minuend) {	100✔
107	if (	178✔
108	hasOwnProperty.call(minuend, key) &&	266✔
109	minuend[key] !== undefined &&
110	!(hasOwnProperty.call(subtrahend, key) && subtrahend[key] !== undefined)	173✔
111	) {
112	keys.push(key);	8✔
113	}
114	}
115	return keys;	100✔
116	}
117
118	/**
119	* List the keys that shared by all `objects`.
120	*
121	* The semantics of what constitutes a "key" is described in {@link subtract}.
122	*
123	* @param objects - Array of objects to compare
124	* @returns Array of keys that are in ("own-properties" of) every object in `objects`.
125	*/
126	export function intersection(objects: ArrayLike<{ [index: string]: any }>): string[] {
NEW 127	const length = objects.length;	×
128	// prepare empty counter to keep track of how many objects each key occurred in
NEW 129	const counter: { [index: string]: number } = {};	×
130	// go through each object and increment the counter for each key in that object
NEW 131	for (let i = 0; i < length; i++) {	×
NEW 132	const object = objects[i];	×
NEW 133	for (const key in object) {	×
NEW 134	if (hasOwnProperty.call(object, key) && object[key] !== undefined) {	×
NEW 135	counter[key] = (counter[key] \|\| 0) + 1;	×
136	}
137	}
138	}
139	// now delete all keys from the counter that were not seen in every object
NEW 140	for (const key in counter) {	×
NEW 141	if (counter[key] < length) {	×
NEW 142	delete counter[key];	×
143	}
144	}
145	// finally, extract whatever keys remain in the counter
NEW 146	return Object.keys(counter);	×
147	}
148
149	/**
150	* List the keys that shared by all `a` and `b`.
151	*
152	* The semantics of what constitutes a "key" is described in {@link subtract}.
153	*
154	* @param a - First object to compare
155	* @param b - Second object to compare
156	* @returns Array of keys that are in ("own-properties" of) `a` and `b`.
157	*/
158	function intersection2(a: { [index: string]: any }, b: { [index: string]: any }): string[] {
159	const keys: string[] = [];	50✔
160	for (const key in a) {	50✔
161	if (hasOwnProperty.call(a, key) && a[key] !== undefined && hasOwnProperty.call(b, key) && b[key] !== undefined) {	88✔
162	keys.push(key);	84✔
163	}
164	}
165	return keys;	50✔
166	}
167
168	interface ArrayAdd {
169	op: 'add';
170	index: number;
171	value: any;
172	}
173	interface ArrayRemove {
174	op: 'remove';
175	index: number;
176	}
177	interface ArrayReplace {
178	op: 'replace';
179	index: number;
180	original: any;
181	value: any;
182	}
183	/**
184	* These are not proper Operation objects, but will be converted into
185	* Operation objects eventually. {index} indicates the actual target position,
186	* never 'end-of-array'
187	*/
188	type ArrayOperation = ArrayAdd \| ArrayRemove \| ArrayReplace;
189	function isArrayAdd(array_operation: ArrayOperation): array_operation is ArrayAdd {
190	return array_operation.op === 'add';	70✔
191	}
192	function isArrayRemove(array_operation: ArrayOperation): array_operation is ArrayRemove {
193	return array_operation.op === 'remove';	46✔
194	}
195
196	interface DynamicAlternative {
197	operations: ArrayOperation[];
198	/** Indicates the total cost of getting to this position. */
199	cost: number;
200	}
201
202	function appendArrayOperation(base: DynamicAlternative, operation: ArrayOperation): DynamicAlternative {
203	return {	326✔
204	// the new operation must be pushed on the end
205	operations: base.operations.concat(operation),
206	cost: base.cost + 1,
207	};
208	}
209
210	/**
211	* Calculate the shortest sequence of operations to get from `input` to `output`,
212	* using a dynamic programming implementation of the Levenshtein distance algorithm.
213	*
214	* To get from the input ABC to the output AZ we could just delete all the input
215	* and say "insert A, insert Z" and be done with it. That's what we do if the
216	* input is empty. But we can be smarter.
217	*
218	* output
219	* A Z
220	* - -
221	* [0] 1 2
222	* input A \| 1 [0] 1
223	* B \| 2 [1] 1
224	* C \| 3 2 [2]
225	*
226	* 1) start at 0,0 (+0)
227	* 2) keep A (+0)
228	* 3) remove B (+1)
229	* 4) replace C with Z (+1)
230	*
231	* If the `input` (source) is empty, they'll all be in the top row, resulting in an
232	* array of 'add' operations.
233	* If the `output` (target) is empty, everything will be in the left column,
234	* resulting in an array of 'remove' operations.
235	*
236	* @param input - The original array.
237	* @param output - The target array.
238	* @param ptr - JSON Pointer.
239	* @param diff - Diff function.
240	* @returns A list of add/remove/replace operations.
241	*/
242	export function diffArrays<T>(input: T[], output: T[], ptr: Pointer, diff: Diff = diffAny): Operation[] {	24✔
243	// set up cost matrix (very simple initialization: just a map)
244	const max_length = Math.max(input.length, output.length);	48✔
245	const memo = new Map<number, DynamicAlternative>([[0, { operations: [], cost: 0 }]]);	48✔
246
247	/**
248	* Calculate the cheapest sequence of operations required to get from
249	* input.slice(0, i) to output.slice(0, j).
250	* There may be other valid sequences with the same cost, but none cheaper.
251	*
252	* @param i - The row in the layout above
253	* @param j - The column in the layout above
254	* @returns An object containing a list of operations, along with the total cost of applying them
255	* (+1 for each add/remove/replace operation)
256	*/
257	function dist(i: number, j: number): DynamicAlternative {
258	// memoized
259	const memo_key = i * max_length + j;	448✔
260	let memoized = memo.get(memo_key);	448✔
261	if (memoized === undefined) {	448✔
262	// TODO: this !diff(...).length usage could/should be lazy
263	if (i > 0 && j > 0 && !diff(input[i - 1], output[j - 1], ptr.add(String(i - 1))).length) {	252✔
264	// equal (no operations => no cost)
265	memoized = dist(i - 1, j - 1);	74✔
266	} else {
267	const alternatives: DynamicAlternative[] = [];	178✔
268	if (i > 0) {	178✔
269	// NOT topmost row
270	const remove_base = dist(i - 1, j);	124✔
271	const remove_operation: ArrayRemove = {	124✔
272	op: 'remove',
273	index: i - 1,
274	};
275	alternatives.push(appendArrayOperation(remove_base, remove_operation));	124✔
276	}
277	if (j > 0) {	178✔
278	// NOT leftmost column
279	const add_base = dist(i, j - 1);	128✔
280	const add_operation: ArrayAdd = {	128✔
281	op: 'add',
282	index: i - 1,
283	value: output[j - 1],
284	};
285	alternatives.push(appendArrayOperation(add_base, add_operation));	128✔
286	}
287	if (i > 0 && j > 0) {	178✔
288	// TABLE MIDDLE
289	// supposing we replaced it, compute the rest of the costs:
290	const replace_base = dist(i - 1, j - 1);	74✔
291	// okay, the general plan is to replace it, but we can be smarter,
292	// recursing into the structure and replacing only part of it if
293	// possible, but to do so we'll need the original value
294	const replace_operation: ArrayReplace = {	74✔
295	op: 'replace',
296	index: i - 1,
297	original: input[i - 1],
298	value: output[j - 1],
299	};
300	alternatives.push(appendArrayOperation(replace_base, replace_operation));	74✔
301	}
302	// the only other case, i === 0 && j === 0, has already been memoized
303
304	// the meat of the algorithm:
305	// sort by cost to find the lowest one (might be several ties for lowest)
306	// [4, 6, 7, 1, 2].sort((a, b) => a - b) -> [ 1, 2, 4, 6, 7 ]
307	const best = alternatives.sort((a, b) => a.cost - b.cost)[0];	284✔
308	memoized = best;	178✔
309	}
310	memo.set(memo_key, memoized);	252✔
311	}
312	return memoized;	448✔
313	}
314	// handle weird objects masquerading as Arrays that don't have proper length
315	// properties by using 0 for everything but positive numbers
316	const input_length = isNaN(input.length) \|\| input.length <= 0 ? 0 : input.length;	48✔
317	const output_length = isNaN(output.length) \|\| output.length <= 0 ? 0 : output.length;	48✔
318	const array_operations = dist(input_length, output_length).operations;	48✔
319	const [padded_operations] = array_operations.reduce<[Operation[], number]>(	48✔
320	([operations, padding], array_operation) => {
321	if (isArrayAdd(array_operation)) {	70✔
322	const padded_index = array_operation.index + 1 + padding;	24✔
323	const index_token = padded_index < input_length + padding ? String(padded_index) : '-';	24✔
324	const operation = {	24✔
325	op: array_operation.op,
326	path: ptr.add(index_token).toString(),
327	value: array_operation.value,
328	};
329	// padding++ // maybe only if array_operation.index > -1 ?
330	return [operations.concat(operation), padding + 1];	24✔
331	} else if (isArrayRemove(array_operation)) {	46✔
332	const operation = {	26✔
333	op: array_operation.op,
334	path: ptr.add(String(array_operation.index + padding)).toString(),
335	};
336	// padding--
337	return [operations.concat(operation), padding - 1];	26✔
338	} else {
339	// replace
340	const replace_ptr = ptr.add(String(array_operation.index + padding));	20✔
341	const replace_operations = diff(array_operation.original, array_operation.value, replace_ptr);	20✔
342	return [operations.concat(...replace_operations), padding];	20✔
343	}
344	},
345	[[], 0]
346	);
347	return padded_operations;	48✔
348	}
349
350	export function diffObjects(input: any, output: any, ptr: Pointer, diff: Diff = diffAny): Operation[] {	25✔
351	// if a key is in input but not output -> remove it
352	const operations: Operation[] = [];	50✔
353	subtract(input, output).forEach((key) => {	50✔
354	operations.push({ op: 'remove', path: ptr.add(key).toString() });	2✔
355	});
356	// if a key is in output but not input -> add it
357	subtract(output, input).forEach((key) => {	50✔
358	operations.push({ op: 'add', path: ptr.add(key).toString(), value: output[key] });	6✔
359	});
360	// if a key is in both, diff it recursively
361	intersection2(input, output).forEach((key) => {	50✔
362	operations.push(...diff(input[key], output[key], ptr.add(key)));	84✔
363	});
364	return operations;	50✔
365	}
366
367	/**
368	* `diffAny()` returns an empty array if `input` and `output` are materially equal
369	* (i.e., would produce equivalent JSON); otherwise it produces an array of patches
370	* that would transform `input` into `output`.
371	*
372	* > Here, "equal" means that the value at the target location and the
373	* > value conveyed by "value" are of the same JSON type, and that they
374	* > are considered equal by the following rules for that type:
375	* > o strings: are considered equal if they contain the same number of
376	* > Unicode characters and their code points are byte-by-byte equal.
377	* > o numbers: are considered equal if their values are numerically
378	* > equal.
379	* > o arrays: are considered equal if they contain the same number of
380	* > values, and if each value can be considered equal to the value at
381	* > the corresponding position in the other array, using this list of
382	* > type-specific rules.
383	* > o objects: are considered equal if they contain the same number of
384	* > members, and if each member can be considered equal to a member in
385	* > the other object, by comparing their keys (as strings) and their
386	* > values (using this list of type-specific rules).
387	* > o literals (false, true, and null): are considered equal if they are
388	* > the same.
389	*
390	* @param input - The original value.
391	* @param output - The target value.
392	* @param ptr - JSON Pointer.
393	* @param diff - Diff function.
394	* @returns The list of operations to get form the original to target value.
395	*/
396	export function diffAny(input: any, output: any, ptr: Pointer, diff: Diff = diffAny): Operation[] {	181✔
397	// strict equality handles literals, numbers, and strings (a sufficient but not necessary cause)
398	if (input === output) {	362✔
399	return [];	144✔
400	}
401	const input_type = objectType(input);	218✔
402	const output_type = objectType(output);	218✔
403	if (input_type === 'array' && output_type === 'array') {	218✔
404	return diffArrays(input, output, ptr, diff);	48✔
405	}
406	if (input_type === 'object' && output_type === 'object') {	170✔
407	return diffObjects(input, output, ptr, diff);	50✔
408	}
409	// at this point we know that input and output are materially different;
410	// could be array -> object, object -> array, boolean -> undefined,
411	// number -> string, or some other combination, but nothing that can be split
412	// up into multiple patches: so `output` must replace `input` wholesale.
413	return [{ op: 'replace', path: ptr.toString(), value: output }];	120✔
414	}

medplum / medplum / 26654265033

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous