JSONPatch.js implementation for AlchemyMVC

json_patch.js

const PatchApplyError = Error,
      InvalidPatch = Error;

/**
 * The JSONPatch class:
 * Used to generate a JSON patch between two objects
 *
 * @constructor
 *
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {String}   type
 */
const Patch = Function.inherits('Alchemy.Base', 'Alchemy.Patch', function Patch(patch, mutate) {
	this.compiled_operations = null;
	this.parsePatch(patch, mutate);
});

/**
 * Apply the given patch to the given object
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
Patch.setStatic(function applyPatch(doc, patch) {
	return (new Patch(patch)).apply(doc);
});

/**
 * Parse a patch
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
Patch.setMethod(function parsePatch(patch, mutate) {

	let i;

	this.compiled_operations = [];

	if ('string' === typeof patch) {
		patch = JSON.undry(patch);
	}

	if (!Array.isArray(patch)) {
		throw new InvalidPatch('Patch must be an array of operations');
	}

	for (i = 0; i < patch.length; i++) {
		let compiled = compileOperation(patch[i], mutate);
		this.compiled_operations.push(compiled);
	}
});

/**
 * Create a patch.
 * The inputs should be simple objects (so already dried)
 *
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
Patch.setStatic(function createPatch(original, target) {
	const patch = [];

	function createPatchRecursive(orig, tgt, pointer) {
		if (Array.isArray(orig) && Array.isArray(tgt)) {
			for (let i = 0; i < Math.max(orig.length, tgt.length); i++) {
				if (i >= orig.length) {
					patch.push({ op: 'add', path: pointer + '/' + i, value: tgt[i] });
				} else if (i >= tgt.length) {
					patch.push({ op: 'remove', path: pointer + '/' + i });
				} else {
					createPatchRecursive(orig[i], tgt[i], pointer + '/' + i);
				}
			}
		} else if (typeof orig === 'object' && orig !== null && typeof tgt === 'object' && tgt !== null) {
			const keys = new Set([...Object.keys(orig), ...Object.keys(tgt)]);

			for (let key of keys) {
				if (!tgt.hasOwnProperty(key)) {
					patch.push({ op: 'remove', path: pointer + '/' + key });
				} else if (!orig.hasOwnProperty(key)) {
					patch.push({ op: 'add', path: pointer + '/' + key, value: tgt[key] });
				} else {
					createPatchRecursive(orig[key], tgt[key], pointer + '/' + key);
				}
			}
		} else if (orig !== tgt) {
			patch.push({ op: 'replace', path: pointer, value: tgt });
		}
	}

	createPatchRecursive(original, target, '');
	return patch;
});

/**
 * Apply this patch to the given document
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
Patch.setMethod(function apply(doc) {
	let i;

	for(i = 0; i < this.compiled_operations.length; i++) {
		doc = this.compiled_operations[i](doc);
	}

	return doc;
});

/**
 * The JSONPatch class:
 * Used to generate a JSON patch between two objects
 *
 * @constructor
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {String}   path
 */
const JSONPointer = Function.inherits('Alchemy.Base', 'Alchemy.Patch', function JSONPointer(path_string) {

	// Split up the path
	let split = path_string.split('/');

	if ('' !== split[0]) {
		throw new InvalidPatch('JSONPointer must start with a slash (or be an empty string)!');
	}

	let i,
	    path = [];

	for (i = 1; i < split.length; i++) {
		path[i-1] = split[i].replace(/~1/g,'/').replace(/~0/g,'~');
	}

	this.path = path;
	this.length = path.length;
});

/**
 * Get a segment of the pointer given a current doc context
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
JSONPointer.setMethod(function _getSegment(index, node) {

	let segment = this.path[index];

	if(Array.isArray(node)) {
		if ('-' === segment) {
			segment = node.length;
		} else {
			// Must be a non-negative integer in base-10 without leading zeros
			if (!segment.match(/^0$|^[1-9][0-9]*$/)) {
				throw new PatchApplyError('Expected a number to segment an array');
			}

			segment = parseInt(segment, 10);
		}
	}

	return segment;
});

/**
 * Follow the pointer to its penultimate segment then call
 * the handler with the current doc and the last key (converted to
 * an int if the current doc is an array). The handler is expected to
 * return a new copy of the penultimate part.
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {*}   doc      The document to search within
 * @param    {*}   handler  The callback to handle the last part
 *
 * @return   {*}            The result of calling the handler
 */
JSONPointer.setMethod(function _action(doc, handler, mutate) {

	const followPointer = (node, index) => {

		let segment,
		    subnode;

		if (!mutate) {
			node = JSON.clone(node);
		}

		segment = this._getSegment(index, node);

		// Is this the last segment?
		if (index == this.path.length-1) {
			node = handler(node, segment);
		} else {
			// Make sure we can follow the segment
			if (Array.isArray(node)) {
				if (node.length <= segment) {
					throw new PatchApplyError('Path not found in document');
				}
			} else if (typeof node === "object") {
				if (!Object.hasOwnProperty.call(node, segment)) {
					throw new PatchApplyError('Path not found in document');
				}
			} else {
				throw new PatchApplyError('Path not found in document');
			}

			subnode = followPointer(node[segment], index+1);

			if (!mutate) {
				node[segment] = subnode;
			}
		}

		return node;
	}

	return followPointer(doc, 0);
});

/**
 * Takes a JSON document and a value and adds the value into
 * the doc at the position pointed to. If the position pointed to is
 * in an array then the existing element at that position (if any)
 * and all that follow it have their position incremented to make
 * room. It is an error to add to a parent object that doesn't exist
 * or to try to replace an existing value in an object.
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {*}   doc      The document to operate against
 * @param    {*}   value    The value to insert at the position pointed to
 *
 * @return   {*}            The updated document
 */
JSONPointer.setMethod(function add(doc, value, mutate) {

	// Special case for a pointer to the root
	if (0 === this.length) {
		return value;
	}

	return this._action(doc, (node, lastSegment) => {
		if (Array.isArray(node)) {
			if (lastSegment > node.length) {
				throw new PatchApplyError('Add operation must not attempt to create a sparse array!');
			}

			node.splice(lastSegment, 0, value);
		} else {
			node[lastSegment] = value;
		}

		return node;
	}, mutate);
});

/**
 * Takes a JSON document and removes the value pointed to.
 * It is an error to attempt to remove a value that doesn't exist.
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {*}   doc      The document to operate against
 *
 * @return   {*}            The updated document
 */
JSONPointer.setMethod(function remove(doc, mutate) {

	// Special case for a pointer to the root
	if (0 === this.length) {
		// Removing the root makes the whole value undefined.
		// NOTE: Should it be an error to remove the root if it is
		// ALREADY undefined? I'm not sure...
		return undefined;
	}

	return this._action(doc, (node, lastSegment) => {
			if (!Object.hasOwnProperty.call(node,lastSegment)) {
				throw new PatchApplyError('Remove operation must point to an existing value!');
			}

			if (Array.isArray(node)) {
				node.splice(lastSegment, 1);
			} else {
				delete node[lastSegment];
			}
		return node;
	}, mutate);
});

/**
 * Semantically equivalent to a remove followed by an add
 * except when the pointer points to the root element in which case
 * the whole document is replaced.
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {*}   doc      The document to operate against
 *
 * @return   {*}            The updated document
 */
JSONPointer.setMethod(function replace(doc, value, mutate) {

	// Special case for a pointer to the root
	if (0 === this.length) {
		return value;
	}
	return this._action(doc, (node, lastSegment) => {
			if (!Object.hasOwnProperty.call(node,lastSegment)) {
				throw new PatchApplyError('Replace operation must point to an existing value!');
			}
			if (Array.isArray(node)) {
				node.splice(lastSegment, 1, value);
			} else {
				node[lastSegment] = value;
			}
		return node;
	}, mutate);
});

/**
 * Returns the value pointed to by the pointer in the given doc.
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {*}   doc      The document to operate against
 *
 * @return   {*}            The value
 */
JSONPointer.setMethod(function get(doc) {

	// Special case for a pointer to the root
	if (0 === this.length) {
		return doc;
	}

	let value;

	this._action(doc, (node, lastSegment) => {
		if (!Object.hasOwnProperty.call(node,lastSegment)) {
			throw new PatchApplyError('Path not found in document');
		}

		value = node[lastSegment];
		return node;
	}, true);

	return value;
});

/**
 * Returns true if this pointer points to a child of the
 * other pointer given. Returns true if both point to the same place.
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 *
 * @param    {*}   otherPointer      The other pointer
 */
JSONPointer.setMethod(function subsetOf(otherPointer) {
	if (this.length <= otherPointer.length) {
		return false;
	}

	let i;

	for (i = 0; i < otherPointer.length; i++) {
		if (otherPointer.path[i] !== this.path[i]) {
			return false;
		}
	}

	return true;
});

const OPERATION_REQUIREMENTS = {
	add: ['value'],
	replace: ['value'],
	test: ['value'],
	remove: [],
	move: ['from'],
	copy: ['from']
};

/**
 * Validate an operation
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
function validateOp(operation) {
	
	if (!operation.op) {
		throw new PatchApplyError('Operation missing!');
	}

	if (!OPERATION_REQUIREMENTS.hasOwnProperty(operation.op)) {
		throw new PatchApplyError('Invalid operation!');
	}

	if (!('path' in operation)) {
		throw new PatchApplyError('Path missing!');
	}

	let required = OPERATION_REQUIREMENTS[operation.op],
	    i;

	// Check that all required keys are present
	for (i = 0; i < required.length; i++) {
		if(!(required[i] in operation)) {
			throw new PatchApplyError(operation.op + ' must have key ' + required[i]);
		}
	}
}

/**
 * Compile an operation
 *
 * @author   Thomas Parslow   <tom@almostobsolete.net>
 * @author   Jelle De Loecker   <jelle@elevenways.be>
 * @since    1.3.10
 * @version  1.3.10
 */
function compileOperation(operation, mutate) {

	validateOp(operation);

	let  op = operation.op,
	     path = new JSONPointer(operation.path),
	     value = operation.value,
	     from = operation.from ? new JSONPointer(operation.from) : null;

	switch (op) {
		case 'add':
			return (doc) => path.add(doc, value, mutate);
		case 'remove':
			return (doc) => path.remove(doc, mutate);
		case 'replace':
			return (doc) => path.replace(doc, value, mutate);
		case 'move':
			// Check that destination isn't inside the source
			if (path.subsetOf(from)) {
				throw new PatchApplyError('destination must not be a child of source');
			}
			return (doc) => {
				let value = from.get(doc),
				    intermediate = from.remove(doc, mutate);

				return path.add(intermediate, value, mutate);
			};
		case 'copy':
			return (doc) => {
				let value = from.get(doc);
				return path.add(doc, value, mutate);
			};
		case 'test':
			return (doc) => {
				if (!Object.alike(path.get(doc), value)) {
					throw new PatchApplyError("Test operation failed. Value did not match.");
				}
				return doc;
			};
	}
}