transform.ts

/**
 * @license Copyright (c) 2003-2024, CKSource Holding sp. z o.o. All rights reserved.
 * For licensing, see LICENSE.md or https://ckeditor.com/legal/ckeditor-oss-license
 */

/**
 * @module engine/model/operation/transform
 */

import InsertOperation from './insertoperation.js';
import AttributeOperation from './attributeoperation.js';
import RenameOperation from './renameoperation.js';
import MarkerOperation from './markeroperation.js';
import MoveOperation from './moveoperation.js';
import RootAttributeOperation from './rootattributeoperation.js';
import RootOperation from './rootoperation.js';
import MergeOperation from './mergeoperation.js';
import SplitOperation from './splitoperation.js';
import NoOperation from './nooperation.js';
import Range from '../range.js';
import Position from '../position.js';

import type Operation from './operation.js';
import type Document from '../document.js';
import type History from '../history.js';

import { compareArrays } from '@ckeditor/ckeditor5-utils';

type TransformationFunction = ( a: Operation, b: Operation, context: TransformationContext ) => Array<Operation>;

const transformations = new Map<Function, Map<Function, TransformationFunction>>();

/**
 * Sets a transformation function to be be used to transform instances of class `OperationA` by instances of class `OperationB`.
 *
 * The `transformationFunction` is passed three parameters:
 *
 * * `a` - operation to be transformed, an instance of `OperationA`,
 * * `b` - operation to be transformed by, an instance of `OperationB`,
 * * {@link module:engine/model/operation/transform~TransformationContext `context`} - object with additional information about
 * transformation context.
 *
 * The `transformationFunction` should return transformation result, which is an array with one or multiple
 * {@link module:engine/model/operation/operation~Operation operation} instances.
 *
 * @param transformationFunction Function to use for transforming.
 */
function setTransformation<
	ClassA extends new ( ...args: Array<any> ) => Operation,
	ClassB extends new ( ...args: Array<any> ) => Operation
>(
	OperationA: ClassA,
	OperationB: ClassB,
	transformationFunction: ( a: InstanceType<ClassA>, b: InstanceType<ClassB>, context: TransformationContext ) => Array<Operation>
) {
	let aGroup = transformations.get( OperationA );

	if ( !aGroup ) {
		aGroup = new Map();
		transformations.set( OperationA, aGroup );
	}

	aGroup.set( OperationB, transformationFunction as TransformationFunction );
}

/**
 * Returns a previously set transformation function for transforming an instance of `OperationA` by an instance of `OperationB`.
 *
 * If no transformation was set for given pair of operations, {@link module:engine/model/operation/transform~noUpdateTransformation}
 * is returned. This means that if no transformation was set, the `OperationA` instance will not change when transformed
 * by the `OperationB` instance.
 *
 * @returns Function set to transform an instance of `OperationA` by an instance of `OperationB`.
 */
function getTransformation( OperationA: Function, OperationB: Function ): TransformationFunction {
	const aGroup = transformations.get( OperationA );

	if ( aGroup && aGroup.has( OperationB ) ) {
		return aGroup.get( OperationB )!;
	}

	return noUpdateTransformation;
}

/**
 * A transformation function that only clones operation to transform, without changing it.
 */
function noUpdateTransformation( a: Operation ): Array<Operation> {
	return [ a ];
}

/**
 * Transforms operation `a` by operation `b`.
 *
 * @param a Operation to be transformed.
 * @param b Operation to transform by.
 * @param context Transformation context for this transformation.
 * @returns Transformation result.
 */
export function transform( a: Operation, b: Operation, context: TransformationContext = {} ): Array<Operation> {
	const transformationFunction = getTransformation( a.constructor, b.constructor );

	/* eslint-disable no-useless-catch */
	try {
		a = a.clone();

		return transformationFunction( a, b, context );
	} catch ( e: any ) {
		// @if CK_DEBUG // console.warn( 'Error during operation transformation!', e.message );
		// @if CK_DEBUG // console.warn( 'Transformed operation', a );
		// @if CK_DEBUG // console.warn( 'Operation transformed by', b );
		// @if CK_DEBUG // console.warn( 'context.aIsStrong', context.aIsStrong );
		// @if CK_DEBUG // console.warn( 'context.aWasUndone', context.aWasUndone );
		// @if CK_DEBUG // console.warn( 'context.bWasUndone', context.bWasUndone );
		// @if CK_DEBUG // console.warn( 'context.abRelation', context.abRelation );
		// @if CK_DEBUG // console.warn( 'context.baRelation', context.baRelation );

		throw e;
	}
	/* eslint-enable no-useless-catch */
}

/**
 * Performs a transformation of two sets of operations - `operationsA` and `operationsB`. The transformation is two-way -
 * both transformed `operationsA` and transformed `operationsB` are returned.
 *
 * Note, that the first operation in each set should base on the same document state (
 * {@link module:engine/model/document~Document#version document version}).
 *
 * It is assumed that `operationsA` are "more important" during conflict resolution between two operations.
 *
 * New copies of both passed arrays and operations inside them are returned. Passed arguments are not altered.
 *
 * Base versions of the transformed operations sets are updated accordingly. For example, assume that base versions are `4`
 * and there are `3` operations in `operationsA` and `5` operations in `operationsB`. Then:
 *
 * * transformed `operationsA` will start from base version `9` (`4` base version + `5` operations B),
 * * transformed `operationsB` will start from base version `7` (`4` base version + `3` operations A).
 *
 * If no operation was broken into two during transformation, then both sets will end up with an operation that bases on version `11`:
 *
 * * transformed `operationsA` start from `9` and there are `3` of them, so the last will have `baseVersion` equal to `11`,
 * * transformed `operationsB` start from `7` and there are `5` of them, so the last will have `baseVersion` equal to `11`.
 *
 * @param operationsA
 * @param operationsB
 * @param options Additional transformation options.
 * @param options.document Document which the operations change.
 * @param options.useRelations Whether during transformation relations should be used (used during undo for better conflict resolution).
 * @param options.padWithNoOps Whether additional {@link module:engine/model/operation/nooperation~NoOperation}s
 * should be added to the transformation results to force the same last base version for both transformed sets (in case
 * if some operations got broken into multiple operations during transformation).
 * @param options.forceWeakRemove If set to `false`, remove operation will be always stronger than move operation,
 * so the removed nodes won't end up back in the document root. When set to `true`, context data will be used.
 * @returns Transformation result.
 */
export function transformSets(
	operationsA: Array<Operation>,
	operationsB: Array<Operation>,
	options: {
		document: Document;
		useRelations?: boolean;
		padWithNoOps?: boolean;
		forceWeakRemove?: boolean;
	}
): TransformSetsResult {
	// Create new arrays so the originally passed arguments are not changed.
	// No need to clone operations, they are cloned as they are transformed.
	operationsA = operationsA.slice();
	operationsB = operationsB.slice();

	const contextFactory = new ContextFactory( options.document, options.useRelations, options.forceWeakRemove );
	contextFactory.setOriginalOperations( operationsA );
	contextFactory.setOriginalOperations( operationsB );

	const originalOperations = contextFactory.originalOperations;

	// If one of sets is empty there is simply nothing to transform, so return sets as they are.
	if ( operationsA.length == 0 || operationsB.length == 0 ) {
		return { operationsA, operationsB, originalOperations };
	}
	//
	// Following is a description of transformation process:
	//
	// There are `operationsA` and `operationsB` to be transformed, both by both.
	//
	// So, suppose we have sets of two operations each: `operationsA` = `[ a1, a2 ]`, `operationsB` = `[ b1, b2 ]`.
	//
	// Remember, that we can only transform operations that base on the same context. We assert that `a1` and `b1` base on
	// the same context and we transform them. Then, we get `a1'` and `b1'`. `a2` bases on a context with `a1` -- `a2`
	// is an operation that followed `a1`. Similarly, `b2` bases on a context with `b1`.
	//
	// However, since `a1'` is a result of transformation by `b1`, `a1'` now also has a context with `b1`. This means that
	// we can safely transform `a1'` by `b2`. As we finish transforming `a1`, we also transformed all `operationsB`.
	// All `operationsB` also have context including `a1`. Now, we can properly transform `a2` by those operations.
	//
	// The transformation process can be visualized on a transformation diagram ("diamond diagram"):
	//
	//          [the initial state]
	//         [common for a1 and b1]
	//
	//                   *
	//                  / \
	//                 /   \
	//               b1     a1
	//               /       \
	//              /         \
	//             *           *
	//            / \         / \
	//           /   \       /   \
	//         b2    a1'   b1'    a2
	//         /       \   /       \
	//        /         \ /         \
	//       *           *           *
	//        \         / \         /
	//         \       /   \       /
	//        a1''   b2'   a2'   b1''
	//           \   /       \   /
	//            \ /         \ /
	//             *           *
	//              \         /
	//               \       /
	//              a2''   b2''
	//                 \   /
	//                  \ /
	//                   *
	//
	//           [the final state]
	//
	// The final state can be reached from the initial state by applying `a1`, `a2`, `b1''` and `b2''`, as well as by
	// applying `b1`, `b2`, `a1''`, `a2''`. Note how the operations get to a proper common state before each pair is
	// transformed.
	//
	// Another thing to consider is that an operation during transformation can be broken into multiple operations.
	// Suppose that `a1` * `b1` = `[ a11', a12' ]` (instead of `a1'` that we considered previously).
	//
	// In that case, we leave `a12'` for later and we continue transforming `a11'` until it is transformed by all `operationsB`
	// (in our case it is just `b2`). At this point, `b1` is transformed by "whole" `a1`, while `b2` is only transformed
	// by `a11'`. Similarly, `a12'` is only transformed by `b1`. This leads to a conclusion that we need to start transforming `a12'`
	// from the moment just after it was broken. So, `a12'` is transformed by `b2`. Now, "the whole" `a1` is transformed
	// by `operationsB`, while all `operationsB` are transformed by "the whole" `a1`. This means that we can continue with
	// following `operationsA` (in our case it is just `a2`).
	//
	// Of course, also `operationsB` can be broken. However, since we focus on transforming operation `a` to the end,
	// the only thing to do is to store both pieces of operation `b`, so that the next transformed operation `a` will
	// be transformed by both of them.
	//
	//                       *
	//                      / \
	//                     /   \
	//                    /     \
	//                  b1       a1
	//                  /         \
	//                 /           \
	//                /             \
	//               *               *
	//              / \             / \
	//             /  a11'         /   \
	//            /     \         /     \
	//          b2       *      b1'      a2
	//          /       / \     /         \
	//         /       /  a12' /           \
	//        /       /     \ /             \
	//       *       b2'     *               *
	//        \     /       / \             /
	//       a11'' /     b21'' \           /
	//          \ /       /     \         /
	//           *       *      a2'     b1''
	//            \     / \       \     /
	//          a12'' b22''\       \   /
	//              \ /     \       \ /
	//               *      a2''     *
	//                \       \     /
	//                 \       \  b21'''
	//                  \       \ /
	//                a2'''      *
	//                    \     /
	//                     \  b22'''
	//                      \ /
	//                       *
	//
	// Note, how `a1` is broken and transformed into `a11'` and `a12'`, while `b2'` got broken and transformed into `b21''` and `b22''`.
	//
	// Having all that on mind, here is an outline for the transformation process algorithm:
	//
	// 1. We have `operationsA` and `operationsB` array, which we dynamically update as the transformation process goes.
	//
	// 2. We take next (or first) operation from `operationsA` and check from which operation `b` we need to start transforming it.
	// All original `operationsA` are set to be transformed starting from the first operation `b`.
	//
	// 3. We take operations from `operationsB`, one by one, starting from the correct one, and transform operation `a`
	// by operation `b` (and vice versa). We update `operationsA` and `operationsB` by replacing the original operations
	// with the transformation results.
	//
	// 4. If operation is broken into multiple operations, we save all the new operations in the place of the
	// original operation.
	//
	// 5. Additionally, if operation `a` was broken, for the "new" operation, we remember from which operation `b` it should
	// be transformed by.
	//
	// 6. We continue transforming "current" operation `a` until it is transformed by all `operationsB`. Then, go to 2.
	// unless the last operation `a` was transformed.
	//
	// The actual implementation of the above algorithm is slightly different, as only one loop (while) is used.
	// The difference is that we have "current" `a` operation to transform and we store the index of the next `b` operation
	// to transform by. Each loop operates on two indexes then: index pointing to currently processed `a` operation and
	// index pointing to next `b` operation. Each loop is just one `a * b` + `b * a` transformation. After each loop
	// operation `b` index is updated. If all `b` operations were visited for the current `a` operation, we change
	// current `a` operation index to the next one.
	//

	// For each operation `a`, keeps information what is the index in `operationsB` from which the transformation should start.
	const nextTransformIndex = new WeakMap<Operation, number>();

	// For all the original `operationsA`, set that they should be transformed starting from the first of `operationsB`.
	for ( const op of operationsA ) {
		nextTransformIndex.set( op, 0 );
	}

	// Additional data that is used for some postprocessing after the main transformation process is done.
	const data = {
		nextBaseVersionA: operationsA[ operationsA.length - 1 ].baseVersion! + 1,
		nextBaseVersionB: operationsB[ operationsB.length - 1 ].baseVersion! + 1,
		originalOperationsACount: operationsA.length,
		originalOperationsBCount: operationsB.length
	};

	// Index of currently transformed operation `a`.
	let i = 0;

	// While not all `operationsA` are transformed...
	while ( i < operationsA.length ) {
		// Get "current" operation `a`.
		const opA = operationsA[ i ];

		// For the "current" operation `a`, get the index of the next operation `b` to transform by.
		const indexB = nextTransformIndex.get( opA )!;

		// If operation `a` was already transformed by every operation `b`, change "current" operation `a` to the next one.
		if ( indexB == operationsB.length ) {
			i++;
			continue;
		}

		const opB = operationsB[ indexB ];

		// Transform `a` by `b` and `b` by `a`.
		const newOpsA = transform( opA, opB, contextFactory.getContext( opA, opB, true ) );
		const newOpsB = transform( opB, opA, contextFactory.getContext( opB, opA, false ) );
		// As a result we get one or more `newOpsA` and one or more `newOpsB` operations.

		// Update contextual information about operations.
		contextFactory.updateRelation( opA, opB );

		contextFactory.setOriginalOperations( newOpsA, opA );
		contextFactory.setOriginalOperations( newOpsB, opB );

		// For new `a` operations, update their index of the next operation `b` to transform them by.
		//
		// This is needed even if there was only one result (`a` was not broken) because that information is used
		// at the beginning of this loop every time.
		for ( const newOpA of newOpsA ) {
			// Acknowledge, that operation `b` also might be broken into multiple operations.
			//
			// This is why we raise `indexB` not just by 1. If `newOpsB` are multiple operations, they will be
			// spliced in the place of `opB`. So we need to change `transformBy` accordingly, so that an operation won't
			// be transformed by the same operation (part of it) again.
			nextTransformIndex.set( newOpA, indexB + newOpsB.length );
		}

		// Update `operationsA` and `operationsB` with the transformed versions.
		operationsA.splice( i, 1, ...newOpsA );
		operationsB.splice( indexB, 1, ...newOpsB );
	}

	if ( options.padWithNoOps ) {
		// If no-operations padding is enabled, count how many extra `a` and `b` operations were generated.
		const brokenOperationsACount = operationsA.length - data.originalOperationsACount;
		const brokenOperationsBCount = operationsB.length - data.originalOperationsBCount;

		// Then, if that number is not the same, pad `operationsA` or `operationsB` with correct number of no-ops so
		// that the base versions are equalled.
		//
		// Note that only one array will be updated, as only one of those subtractions can be greater than zero.
		padWithNoOps( operationsA, brokenOperationsBCount - brokenOperationsACount );
		padWithNoOps( operationsB, brokenOperationsACount - brokenOperationsBCount );
	}

	// Finally, update base versions of transformed operations.
	updateBaseVersions( operationsA, data.nextBaseVersionB );
	updateBaseVersions( operationsB, data.nextBaseVersionA );

	return { operationsA, operationsB, originalOperations };
}

/**
 * The result of {@link module:engine/model/operation/transform~transformSets}.
 */
export interface TransformSetsResult {

	/**
	 * Transformed `operationsA`.
	 */
	operationsA: Array<Operation>;

	/**
	 * Transformed `operationsB`.
	 */
	operationsB: Array<Operation>;

	/**
	 * A map that links transformed operations to original operations. The keys are the transformed
	 * operations and the values are the original operations from the input (`operationsA` and `operationsB`).
	 */
	originalOperations: Map<Operation, Operation>;
}

/**
 * Gathers additional data about operations processed during transformation. Can be used to obtain contextual information
 * about two operations that are about to be transformed. This contextual information can be used for better conflict resolution.
 */
class ContextFactory {
	public readonly originalOperations: Map<Operation, Operation>;

	private readonly _history: History;
	private readonly _useRelations?: boolean;
	private readonly _forceWeakRemove: boolean;
	private readonly _relations: Map<Operation, Map<Operation, any>>;

	/**
	 * Creates `ContextFactory` instance.
	 *
	 * @param document Document which the operations change.
	 * @param useRelations Whether during transformation relations should be used (used during undo for
	 * better conflict resolution).
	 * @param forceWeakRemove If set to `false`, remove operation will be always stronger than move operation,
	 * so the removed nodes won't end up back in the document root. When set to `true`, context data will be used.
	 */
	constructor( document: Document, useRelations: boolean | undefined, forceWeakRemove = false ) {
		// For each operation that is created during transformation process, we keep a reference to the original operation
		// which it comes from. The original operation works as a kind of "identifier". Every contextual information
		// gathered during transformation that we want to save for given operation, is actually saved for the original operation.
		// This way no matter if operation `a` is cloned, then transformed, even breaks, we still have access to the previously
		// gathered data through original operation reference.
		this.originalOperations = new Map();

		// `model.History` instance which information about undone operations will be taken from.
		this._history = document.history;

		// Whether additional context should be used.
		this._useRelations = useRelations;

		this._forceWeakRemove = !!forceWeakRemove;

		// Relations is a double-map structure (maps in map) where for two operations we store how those operations were related
		// to each other. Those relations are evaluated during transformation process. For every transformated pair of operations
		// we keep relations between them.
		this._relations = new Map();
	}

	/**
	 * Sets "original operation" for given operations.
	 *
	 * During transformation process, operations are cloned, then changed, then processed again, sometimes broken into two
	 * or multiple operations. When gathering additional data it is important that all operations can be somehow linked
	 * so a cloned and transformed "version" still kept track of the data assigned earlier to it.
	 *
	 * The original operation object will be used as such an universal linking id. Throughout the transformation process
	 * all cloned operations will refer to "the original operation" when storing and reading additional data.
	 *
	 * If `takeFrom` is not set, each operation from `operations` array will be assigned itself as "the original operation".
	 * This should be used as an initialization step.
	 *
	 * If `takeFrom` is set, each operation from `operations` will be assigned the same original operation as assigned
	 * for `takeFrom` operation. This should be used to update original operations. It should be used in a way that
	 * `operations` are the result of `takeFrom` transformation to ensure proper "original operation propagation".
	 */
	public setOriginalOperations( operations: Array<Operation>, takeFrom: Operation | null = null ): void {
		const originalOperation = takeFrom ? this.originalOperations.get( takeFrom ) : null;

		for ( const operation of operations ) {
			this.originalOperations.set( operation, originalOperation || operation );
		}
	}

	/**
	 * Saves a relation between operations `opA` and `opB`.
	 *
	 * Relations are then later used to help solve conflicts when operations are transformed.
	 */
	public updateRelation( opA: Operation, opB: Operation ): void {
		// The use of relations is described in a bigger detail in transformation functions.
		//
		// In brief, this function, for specified pairs of operation types, checks how positions defined in those operations relate.
		// Then those relations are saved. For example, for two move operations, it is saved if one of those operations target
		// position is before the other operation source position. This kind of information gives contextual information when
		// transformation is used during undo. Similar checks are done for other pairs of operations.
		//
		if ( opA instanceof MoveOperation ) {
			if ( opB instanceof MergeOperation ) {
				if ( opA.targetPosition.isEqual( opB.sourcePosition ) || opB.movedRange.containsPosition( opA.targetPosition ) ) {
					this._setRelation( opA, opB, 'insertAtSource' );
				} else if ( opA.targetPosition.isEqual( opB.deletionPosition ) ) {
					this._setRelation( opA, opB, 'insertBetween' );
				} else if ( opA.targetPosition.isAfter( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'moveTargetAfter' );
				}
			} else if ( opB instanceof MoveOperation ) {
				if ( opA.targetPosition.isEqual( opB.sourcePosition ) || opA.targetPosition.isBefore( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'insertBefore' );
				} else {
					this._setRelation( opA, opB, 'insertAfter' );
				}
			}
		} else if ( opA instanceof SplitOperation ) {
			if ( opB instanceof MergeOperation ) {
				if ( opA.splitPosition.isBefore( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'splitBefore' );
				}
			} else if ( opB instanceof MoveOperation ) {
				if ( opA.splitPosition.isEqual( opB.sourcePosition ) || opA.splitPosition.isBefore( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'splitBefore' );
				} else {
					const range = Range._createFromPositionAndShift( opB.sourcePosition, opB.howMany );

					if ( opA.splitPosition.hasSameParentAs( opB.sourcePosition ) && range.containsPosition( opA.splitPosition ) ) {
						const howMany = range.end.offset - opA.splitPosition.offset;
						const offset = opA.splitPosition.offset - range.start.offset;

						this._setRelation( opA, opB, { howMany, offset } );
					}
				}
			}
		} else if ( opA instanceof MergeOperation ) {
			if ( opB instanceof MergeOperation ) {
				if ( !opA.targetPosition.isEqual( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'mergeTargetNotMoved' );
				}

				if ( opA.sourcePosition.isEqual( opB.targetPosition ) ) {
					this._setRelation( opA, opB, 'mergeSourceNotMoved' );
				}

				if ( opA.sourcePosition.isEqual( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'mergeSameElement' );
				}
			} else if ( opB instanceof SplitOperation ) {
				if ( opA.sourcePosition.isEqual( opB.splitPosition ) ) {
					this._setRelation( opA, opB, 'splitAtSource' );
				}
			} else if ( opB instanceof MoveOperation && opB.howMany > 0 ) {
				if ( opA.sourcePosition.isEqual( opB.sourcePosition.getShiftedBy( opB.howMany ) ) ) {
					this._setRelation( opA, opB, 'mergeSourceAffected' );
				}

				if ( opA.targetPosition.isEqual( opB.sourcePosition ) ) {
					this._setRelation( opA, opB, 'mergeTargetWasBefore' );
				}
			}
		} else if ( opA instanceof MarkerOperation ) {
			const markerRange = opA.newRange;

			if ( !markerRange ) {
				return;
			}

			if ( opB instanceof MoveOperation ) {
				const movedRange = Range._createFromPositionAndShift( opB.sourcePosition, opB.howMany );

				const affectedLeft = movedRange.containsPosition( markerRange.start ) ||
					movedRange.start.isEqual( markerRange.start );

				const affectedRight = movedRange.containsPosition( markerRange.end ) ||
					movedRange.end.isEqual( markerRange.end );

				if ( ( affectedLeft || affectedRight ) && !movedRange.containsRange( markerRange ) ) {
					this._setRelation( opA, opB, {
						side: affectedLeft ? 'left' : 'right',
						path: affectedLeft ? markerRange.start.path.slice() : markerRange.end.path.slice()
					} );
				}
			} else if ( opB instanceof MergeOperation ) {
				const wasInLeftElement = markerRange.start.isEqual( opB.targetPosition );
				const wasStartBeforeMergedElement = markerRange.start.isEqual( opB.deletionPosition );
				const wasEndBeforeMergedElement = markerRange.end.isEqual( opB.deletionPosition );
				const wasInRightElement = markerRange.end.isEqual( opB.sourcePosition );

				if ( wasInLeftElement || wasStartBeforeMergedElement || wasEndBeforeMergedElement || wasInRightElement ) {
					this._setRelation( opA, opB, {
						wasInLeftElement,
						wasStartBeforeMergedElement,
						wasEndBeforeMergedElement,
						wasInRightElement
					} );
				}
			}
		}
	}

	/**
	 * Evaluates and returns contextual information about two given operations `opA` and `opB` which are about to be transformed.
	 */
	public getContext( opA: Operation, opB: Operation, aIsStrong: boolean ): TransformationContext {
		return {
			aIsStrong,
			aWasUndone: this._wasUndone( opA ),
			bWasUndone: this._wasUndone( opB ),
			abRelation: this._useRelations ? this._getRelation( opA, opB ) : null,
			baRelation: this._useRelations ? this._getRelation( opB, opA ) : null,
			forceWeakRemove: this._forceWeakRemove
		};
	}

	/**
	 * Returns whether given operation `op` has already been undone.
	 *
	 * Information whether an operation was undone gives more context when making a decision when two operations are in conflict.
	 */
	public _wasUndone( op: Operation ): boolean {
		// For `op`, get its original operation. After all, if `op` is a clone (or even transformed clone) of another
		// operation, literally `op` couldn't be undone. It was just generated. If anything, it was the operation it origins
		// from which was undone. So get that original operation.
		const originalOp = this.originalOperations.get( op )!;

		// And check with the document if the original operation was undone.
		return ( originalOp as any ).wasUndone || this._history.isUndoneOperation( originalOp );
	}

	/**
	 * Returns a relation between `opA` and an operation which is undone by `opB`. This can be `String` value if a relation
	 * was set earlier or `null` if there was no relation between those operations.
	 *
	 * This is a little tricky to understand, so let's compare it to `ContextFactory#_wasUndone`.
	 *
	 * When `wasUndone( opB )` is used, we check if the `opB` has already been undone. It is obvious, that the
	 * undoing operation must happen after the undone operation. So, essentially, we have `opB`, we take document history,
	 * we look forward in the future and ask if in that future `opB` was undone.
	 *
	 * Relations is a backward process to `wasUndone()`.
	 *
	 * Long story short - using relations is asking what happened in the past. Looking back. This time we have an undoing
	 * operation `opB` which has undone some other operation. When there is a transformation `opA` x `opB` and there is
	 * a conflict to solve and `opB` is an undoing operation, we can look back in the history and see what was a relation
	 * between `opA` and the operation which `opB` undone. Basing on that relation from the past, we can now make
	 * a better decision when resolving a conflict between two operations, because we know more about the context of
	 * those two operations.
	 *
	 * This is why this function does not return a relation directly between `opA` and `opB` because we need to look
	 * back to search for a meaningful contextual information.
	 */
	public _getRelation( opA: Operation, opB: Operation ): any {
		// Get the original operation. Similarly as in `wasUndone()` it is used as an universal identifier for stored data.
		const origB = this.originalOperations.get( opB )!;
		const undoneB = this._history.getUndoneOperation( origB );

		// If `opB` is not undoing any operation, there is no relation.
		if ( !undoneB ) {
			return null;
		}

		const origA = this.originalOperations.get( opA )!;
		const relationsA = this._relations.get( origA );

		// Get all relations for `opA`, and check if there is a relation with `opB`-undone-counterpart. If so, return it.
		if ( relationsA ) {
			return relationsA.get( undoneB ) || null;
		}

		return null;
	}

	/**
	 * Helper function for `ContextFactory#updateRelations`.
	 */
	private _setRelation( opA: Operation, opB: Operation, relation: any ): void {
		// As always, setting is for original operations, not the clones/transformed operations.
		const origA = this.originalOperations.get( opA )!;
		const origB = this.originalOperations.get( opB )!;

		let relationsA = this._relations.get( origA );

		if ( !relationsA ) {
			relationsA = new Map();
			this._relations.set( origA, relationsA );
		}

		relationsA.set( origB, relation );
	}
}

/**
 * Holds additional contextual information about a transformed pair of operations (`a` and `b`). Those information
 * can be used for better conflict resolving.
 */

export type TransformationContext = {

	/**
	 * Whether `a` is strong operation in this transformation, or weak.
	 */
	aIsStrong?: boolean;

	/**
	 * Whether `a` operation was undone.
	 */
	aWasUndone?: boolean;

	/**
	 * Whether `b` operation was undone.
	 */
	bWasUndone?: boolean;

	/**
	 * The relation between `a` operation and an operation undone by `b` operation.
	 */
	abRelation?: any;

	/**
	 * The relation between `b` operation and an operation undone by `a` operation.
	 */
	baRelation?: any;

	forceWeakRemove?: boolean;
};

/**
 * An utility function that updates {@link module:engine/model/operation/operation~Operation#baseVersion base versions}
 * of passed operations.
 *
 * The function simply sets `baseVersion` as a base version of the first passed operation and then increments it for
 * each following operation in `operations`.
 *
 * @param operations Operations to update.
 * @param baseVersion Base version to set for the first operation in `operations`.
 */
function updateBaseVersions( operations: ReadonlyArray<Operation>, baseVersion: number ) {
	for ( const operation of operations ) {
		operation.baseVersion = baseVersion++;
	}
}

/**
 * Adds `howMany` instances of {@link module:engine/model/operation/nooperation~NoOperation} to `operations` set.
 */
function padWithNoOps( operations: Array<Operation>, howMany: number ) {
	for ( let i = 0; i < howMany; i++ ) {
		operations.push( new NoOperation( 0 ) );
	}
}

// -----------------------

setTransformation( AttributeOperation, AttributeOperation, ( a, b, context ) => {
	// If operations in conflict, check if their ranges intersect and manage them properly.
	//
	// Operations can be in conflict only if:
	//
	// * their key is the same (they change the same attribute), and
	// * they are in the same parent (operations for ranges [ 1 ] - [ 3 ] and [ 2, 0 ] - [ 2, 5 ] change different
	// elements and can't be in conflict).
	if ( a.key === b.key && a.range.start.hasSameParentAs( b.range.start ) ) {
		// First, we want to apply change to the part of a range that has not been changed by the other operation.
		const operations = a.range.getDifference( b.range ).map( range => {
			return new AttributeOperation( range, a.key, a.oldValue, a.newValue, 0 );
		} );

		// Then we take care of the common part of ranges.
		const common = a.range.getIntersection( b.range );

		if ( common ) {
			// If this operation is more important, we also want to apply change to the part of the
			// original range that has already been changed by the other operation. Since that range
			// got changed we also have to update `oldValue`.
			if ( context.aIsStrong ) {
				operations.push( new AttributeOperation( common, b.key, b.newValue, a.newValue, 0 ) );
			}
		}

		if ( operations.length == 0 ) {
			return [ new NoOperation( 0 ) ];
		}

		return operations;
	} else {
		// If operations don't conflict, simply return an array containing just a clone of this operation.
		return [ a ];
	}
} );

setTransformation( AttributeOperation, InsertOperation, ( a, b ) => {
	// Case 1:
	//
	// The attribute operation range includes the position where nodes were inserted.
	// There are two possible scenarios: the inserted nodes were text and they should receive attributes or
	// the inserted nodes were elements and they should not receive attributes.
	//
	if ( a.range.start.hasSameParentAs( b.position ) && a.range.containsPosition( b.position ) ) {
		// If new nodes should not receive attributes, two separated ranges will be returned.
		// Otherwise, one expanded range will be returned.
		const range = a.range._getTransformedByInsertion( b.position, b.howMany, !b.shouldReceiveAttributes );
		const result = range.map( r => {
			return new AttributeOperation( r, a.key, a.oldValue, a.newValue, a.baseVersion );
		} );

		if ( b.shouldReceiveAttributes ) {
			// `AttributeOperation#range` includes some newly inserted text.
			// The operation should also change the attribute of that text. An example:
			//
			// Bold should be applied on the following range:
			// <p>Fo[zb]ar</p>
			//
			// In meantime, new text is typed:
			// <p>Fozxxbar</p>
			//
			// Bold should be applied also on the new text:
			// <p>Fo[zxxb]ar</p>
			// <p>Fo<$text bold="true">zxxb</$text>ar</p>
			//
			// There is a special case to consider here to consider.
			//
			// Consider setting an attribute with multiple possible values, for example `highlight`. The inserted text might
			// have already an attribute value applied and the `oldValue` property of the attribute operation might be wrong:
			//
			// Attribute `highlight="yellow"` should be applied on the following range:
			// <p>Fo[zb]ar<p>
			//
			// In meantime, character `x` with `highlight="red"` is typed:
			// <p>Fo[z<$text highlight="red">x</$text>b]ar</p>
			//
			// In this case we cannot simply apply operation changing the attribute value from `null` to `"yellow"` for the whole range
			// because that would lead to an exception (`oldValue` is incorrect for `x`).
			//
			// We also cannot break the original range as this would mess up a scenario when there are multiple following
			// insert operations, because then only the first inserted character is included in those ranges:
			// <p>Fo[z][x][b]ar</p>   -->   <p>Fo[z][x]x[b]ar</p>   -->   <p>Fo[z][x]xx[b]ar</p>
			//
			// So, the attribute range needs be expanded, no matter what attributes are set on the inserted nodes:
			//
			// <p>Fo[z<$text highlight="red">x</$text>b]ar</p>      <--- Change from `null` to `yellow`, throwing an exception.
			//
			// But before that operation would be applied, we will add an additional attribute operation that will change
			// attributes on the inserted nodes in a way which would make the original operation correct:
			//
			// <p>Fo[z{<$text highlight="red">}x</$text>b]ar</p>    <--- Change range `{}` from `red` to `null`.
			// <p>Fo[zxb]ar</p>                                     <--- Now change from `null` to `yellow` is completely fine.
			//

			// Generate complementary attribute operation. Be sure to add it before the original operation.
			const op = _getComplementaryAttributeOperations( b, a.key, a.oldValue );

			if ( op ) {
				result.unshift( op );
			}
		}

		// If nodes should not receive new attribute, we are done here.
		return result;
	}

	// If insert operation is not expanding the attribute operation range, simply transform the range.
	a.range = a.range._getTransformedByInsertion( b.position, b.howMany, false )[ 0 ];

	return [ a ];
} );

/**
 * Helper function for `AttributeOperation` x `InsertOperation` (and reverse) transformation.
 *
 * For given `insertOperation` it checks the inserted node if it has an attribute `key` set to a value different
 * than `newValue`. If so, it generates an `AttributeOperation` which changes the value of `key` attribute to `newValue`.
 */
function _getComplementaryAttributeOperations( insertOperation: InsertOperation, key: string, newValue: unknown ) {
	const nodes = insertOperation.nodes;

	// At the beginning we store the attribute value from the first node.
	const insertValue = nodes.getNode( 0 )!.getAttribute( key );

	if ( insertValue == newValue ) {
		return null;
	}

	const range = new Range( insertOperation.position, insertOperation.position.getShiftedBy( insertOperation.howMany ) );

	return new AttributeOperation( range, key, insertValue, newValue, 0 );
}

setTransformation( AttributeOperation, MergeOperation, ( a, b ) => {
	const ranges = [];

	// Case 1:
	//
	// Attribute change on the merged element. In this case, the merged element was moved to the graveyard.
	// An additional attribute operation that will change the (re)moved element needs to be generated.
	//
	if ( a.range.start.hasSameParentAs( b.deletionPosition ) ) {
		if ( a.range.containsPosition( b.deletionPosition ) || a.range.start.isEqual( b.deletionPosition ) ) {
			ranges.push( Range._createFromPositionAndShift( b.graveyardPosition, 1 ) );
		}
	}

	const range = a.range._getTransformedByMergeOperation( b );

	// Do not add empty (collapsed) ranges to the result. `range` may be collapsed if it contained only the merged element.
	if ( !range.isCollapsed ) {
		ranges.push( range );
	}

	// Create `AttributeOperation`s out of the ranges.
	return ranges.map( range => {
		return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
	} );
} );

setTransformation( AttributeOperation, MoveOperation, ( a, b ) => {
	const ranges = _breakRangeByMoveOperation( a.range, b );

	// Create `AttributeOperation`s out of the ranges.
	return ranges.map( range => new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion ) );
} );

/**
 * Helper function for `AttributeOperation` x `MoveOperation` transformation.
 *
 * Takes the passed `range` and transforms it by move operation `moveOp` in a specific way. Only top-level nodes of `range`
 * are considered to be in the range. If move operation moves nodes deep from inside of the range, those nodes won't
 * be included in the result. In other words, top-level nodes of the ranges from the result are exactly the same as
 * top-level nodes of the original `range`.
 *
 * This is important for `AttributeOperation` because, for its range, it changes only the top-level nodes. So we need to
 * track only how those nodes have been affected by `MoveOperation`.
 */
function _breakRangeByMoveOperation( range: Range, moveOp: MoveOperation ) {
	const moveRange = Range._createFromPositionAndShift( moveOp.sourcePosition, moveOp.howMany );

	// We are transforming `range` (original range) by `moveRange` (range moved by move operation). As usual when it comes to
	// transforming a ranges, we may have a common part of the ranges and we may have a difference part (zero to two ranges).
	let common = null;
	let difference: Array<Range> = [];

	// Let's compare the ranges.
	if ( moveRange.containsRange( range, true ) ) {
		// If the whole original range is moved, treat it whole as a common part. There's also no difference part.
		common = range;
	} else if ( range.start.hasSameParentAs( moveRange.start ) ) {
		// If the ranges are "on the same level" (in the same parent) then move operation may move exactly those nodes
		// that are changed by the attribute operation. In this case we get common part and difference part in the usual way.
		difference = range.getDifference( moveRange );
		common = range.getIntersection( moveRange );
	} else {
		// In any other situation we assume that original range is different than move range, that is that move operation
		// moves other nodes that attribute operation change. Even if the moved range is deep inside in the original range.
		//
		// Note that this is different than in `.getIntersection` (we would get a common part in that case) and different
		// than `.getDifference` (we would get two ranges).
		difference = [ range ];
	}

	const result: Array<Range> = [];

	// The default behaviour of `_getTransformedByMove` might get wrong results for difference part, though, so
	// we do it by hand.
	for ( let diff of difference ) {
		// First, transform the range by removing moved nodes. Since this is a difference, this is safe, `null` won't be returned
		// as the range is different than the moved range.
		diff = diff._getTransformedByDeletion( moveOp.sourcePosition, moveOp.howMany )!;

		// Transform also `targetPosition`.
		const targetPosition = moveOp.getMovedRangeStart();

		// Spread the range only if moved nodes are inserted only between the top-level nodes of the `diff` range.
		const spread = diff.start.hasSameParentAs( targetPosition );

		// Transform by insertion of moved nodes.
		const diffs = diff._getTransformedByInsertion( targetPosition, moveOp.howMany, spread );

		result.push( ...diffs );
	}

	// Common part can be simply transformed by the move operation. This is because move operation will not target to
	// that common part (the operation would have to target inside its own moved range).
	if ( common ) {
		result.push(
			common._getTransformedByMove( moveOp.sourcePosition, moveOp.targetPosition, moveOp.howMany, false )[ 0 ]
		);
	}

	return result;
}

setTransformation( AttributeOperation, SplitOperation, ( a, b ) => {
	// Case 1:
	//
	// Split node is the last node in `AttributeOperation#range`.
	// `AttributeOperation#range` needs to be expanded to include the new (split) node.
	//
	// Attribute `type` to be changed to `numbered` but the `listItem` is split.
	// <listItem type="bulleted">foobar</listItem>
	//
	// After split:
	// <listItem type="bulleted">foo</listItem><listItem type="bulleted">bar</listItem>
	//
	// After attribute change:
	// <listItem type="numbered">foo</listItem><listItem type="numbered">foo</listItem>
	//
	if ( a.range.end.isEqual( b.insertionPosition ) ) {
		if ( !b.graveyardPosition ) {
			a.range.end.offset++;
		}

		return [ a ];
	}

	// Case 2:
	//
	// Split position is inside `AttributeOperation#range`, at the same level, so the nodes to change are
	// not going to make a flat range.
	//
	// Content with range-to-change and split position:
	// <p>Fo[zb^a]r</p>
	//
	// After split:
	// <p>Fozb</p><p>ar</p>
	//
	// Make two separate ranges containing all nodes to change:
	// <p>Fo[zb]</p><p>[a]r</p>
	//
	if ( a.range.start.hasSameParentAs( b.splitPosition ) && a.range.containsPosition( b.splitPosition ) ) {
		const secondPart = a.clone();

		secondPart.range = new Range(
			b.moveTargetPosition.clone(),
			a.range.end._getCombined( b.splitPosition, b.moveTargetPosition )
		);

		( a.range as any ).end = b.splitPosition.clone();
		a.range.end.stickiness = 'toPrevious';

		return [ a, secondPart ];
	}

	// The default case.
	//
	a.range = a.range._getTransformedBySplitOperation( b );

	return [ a ];
} );

setTransformation( InsertOperation, AttributeOperation, ( a, b ) => {
	const result: Array<Operation> = [ a ];

	// Case 1:
	//
	// The attribute operation range includes the position where nodes were inserted.
	// There are two possible scenarios: the inserted nodes were text and they should receive attributes or
	// the inserted nodes were elements and they should not receive attributes.
	//
	// This is a mirror scenario to the one described in `AttributeOperation` x `InsertOperation` transformation,
	// although this case is a little less complicated. In this case we simply need to change attributes of the
	// inserted nodes and that's it.
	//
	if ( a.shouldReceiveAttributes && a.position.hasSameParentAs( b.range.start ) && b.range.containsPosition( a.position ) ) {
		const op = _getComplementaryAttributeOperations( a, b.key, b.newValue );

		if ( op ) {
			result.push( op );
		}
	}

	// The default case is: do nothing.
	// `AttributeOperation` does not change the model tree structure so `InsertOperation` does not need to be changed.
	//
	return result;
} );

setTransformation( InsertOperation, InsertOperation, ( a, b, context ) => {
	// Case 1:
	//
	// Two insert operations insert nodes at the same position. Since they are the same, it needs to be decided
	// what will be the order of inserted nodes. However, there is no additional information to help in that
	// decision. Also, when `b` will be transformed by `a`, the same order must be maintained.
	//
	// To achieve that, we will check if the operation is strong.
	// If it is, it won't get transformed. If it is not, it will be moved.
	//
	if ( a.position.isEqual( b.position ) && context.aIsStrong ) {
		return [ a ];
	}

	// The default case.
	//
	a.position = a.position._getTransformedByInsertOperation( b );

	return [ a ];
} );

setTransformation( InsertOperation, MoveOperation, ( a, b ) => {
	// The default case.
	//
	a.position = a.position._getTransformedByMoveOperation( b );

	return [ a ];
} );

setTransformation( InsertOperation, SplitOperation, ( a, b ) => {
	// The default case.
	//
	a.position = a.position._getTransformedBySplitOperation( b );

	return [ a ];
} );

setTransformation( InsertOperation, MergeOperation, ( a, b ) => {
	a.position = a.position._getTransformedByMergeOperation( b );

	return [ a ];
} );

// -----------------------

setTransformation( MarkerOperation, InsertOperation, ( a, b ) => {
	if ( a.oldRange ) {
		a.oldRange = a.oldRange._getTransformedByInsertOperation( b )[ 0 ];
	}

	if ( a.newRange ) {
		a.newRange = a.newRange._getTransformedByInsertOperation( b )[ 0 ];
	}

	return [ a ];
} );

setTransformation( MarkerOperation, MarkerOperation, ( a, b, context ) => {
	if ( a.name == b.name ) {
		if ( context.aIsStrong ) {
			a.oldRange = b.newRange ? b.newRange.clone() : null;
		} else {
			return [ new NoOperation( 0 ) ];
		}
	}

	return [ a ];
} );

setTransformation( MarkerOperation, MergeOperation, ( a, b ) => {
	if ( a.oldRange ) {
		a.oldRange = a.oldRange._getTransformedByMergeOperation( b );
	}

	if ( a.newRange ) {
		a.newRange = a.newRange._getTransformedByMergeOperation( b );
	}

	return [ a ];
} );

setTransformation( MarkerOperation, MoveOperation, ( a, b, context ) => {
	if ( a.oldRange ) {
		a.oldRange = Range._createFromRanges( a.oldRange._getTransformedByMoveOperation( b ) );
	}

	if ( a.newRange ) {
		if ( context.abRelation ) {
			const aNewRange = Range._createFromRanges( a.newRange._getTransformedByMoveOperation( b ) );

			if ( context.abRelation.side == 'left' && b.targetPosition.isEqual( a.newRange.start ) ) {
				( a.newRange as any ).end = aNewRange.end;
				( a.newRange.start as any ).path = context.abRelation.path;

				return [ a ];
			} else if ( context.abRelation.side == 'right' && b.targetPosition.isEqual( a.newRange.end ) ) {
				( a.newRange as any ).start = aNewRange.start;
				( a.newRange.end as any ).path = context.abRelation.path;

				return [ a ];
			}
		}

		a.newRange = Range._createFromRanges( a.newRange._getTransformedByMoveOperation( b ) );
	}

	return [ a ];
} );

setTransformation( MarkerOperation, SplitOperation, ( a, b, context ) => {
	if ( a.oldRange ) {
		a.oldRange = a.oldRange._getTransformedBySplitOperation( b );
	}

	if ( a.newRange ) {
		if ( context.abRelation ) {
			const aNewRange = a.newRange._getTransformedBySplitOperation( b );

			if ( a.newRange.start.isEqual( b.splitPosition ) && context.abRelation.wasStartBeforeMergedElement ) {
				( a.newRange as any ).start = Position._createAt( b.insertionPosition );
			} else if ( a.newRange.start.isEqual( b.splitPosition ) && !context.abRelation.wasInLeftElement ) {
				( a.newRange as any ).start = Position._createAt( b.moveTargetPosition );
			}

			if ( a.newRange.end.isEqual( b.splitPosition ) && context.abRelation.wasInRightElement ) {
				( a.newRange as any ).end = Position._createAt( b.moveTargetPosition );
			} else if ( a.newRange.end.isEqual( b.splitPosition ) && context.abRelation.wasEndBeforeMergedElement ) {
				( a.newRange as any ).end = Position._createAt( b.insertionPosition );
			} else {
				( a.newRange as any ).end = aNewRange.end;
			}

			return [ a ];
		}

		a.newRange = a.newRange._getTransformedBySplitOperation( b );
	}

	return [ a ];
} );

// -----------------------

setTransformation( MergeOperation, InsertOperation, ( a, b ) => {
	if ( a.sourcePosition.hasSameParentAs( b.position ) ) {
		a.howMany += b.howMany;
	}

	a.sourcePosition = a.sourcePosition._getTransformedByInsertOperation( b );
	a.targetPosition = a.targetPosition._getTransformedByInsertOperation( b );

	return [ a ];
} );

setTransformation( MergeOperation, MergeOperation, ( a, b, context ) => {
	// Case 1:
	//
	// Same merge operations.
	//
	// Both operations have same source and target positions. So the element already got merged and there is
	// theoretically nothing to do.
	//
	if ( a.sourcePosition.isEqual( b.sourcePosition ) && a.targetPosition.isEqual( b.targetPosition ) ) {
		// There are two ways that we can provide a do-nothing operation.
		//
		// First is simply a NoOperation instance. We will use it if `b` operation was not undone.
		//
		// Second is a merge operation that has the source operation in the merged element - in the graveyard -
		// same target position and `howMany` equal to `0`. So it is basically merging an empty element from graveyard
		// which is almost the same as NoOperation.
		//
		// This way the merge operation can be later transformed by split operation
		// to provide correct undo. This will be used if `b` operation was undone (only then it is correct).
		//
		if ( !context.bWasUndone ) {
			return [ new NoOperation( 0 ) ];
		} else {
			const path = b.graveyardPosition.path.slice();
			path.push( 0 );

			a.sourcePosition = new Position( b.graveyardPosition.root, path );
			a.howMany = 0;

			return [ a ];
		}
	}

	// Case 2:
	//
	// Same merge source position but different target position.
	//
	// This can happen during collaboration. For example, if one client merged a paragraph to the previous paragraph
	// and the other person removed that paragraph and merged the same paragraph to something before:
	//
	// Client A:
	// <p>Foo</p><p>Bar</p><p>[]Xyz</p>
	// <p>Foo</p><p>BarXyz</p>
	//
	// Client B:
	// <p>Foo</p>[<p>Bar</p>]<p>Xyz</p>
	// <p>Foo</p><p>[]Xyz</p>
	// <p>FooXyz</p>
	//
	// In this case we need to decide where finally "Xyz" will land:
	//
	// <p>FooXyz</p>               graveyard: <p>Bar</p>
	// <p>Foo</p>                  graveyard: <p>BarXyz</p>
	//
	// Let's move it in a way so that a merge operation that does not target to graveyard is more important so that
	// nodes does not end up in the graveyard. It makes sense. Both for Client A and for Client B "Xyz" finally did not
	// end up in the graveyard (see above).
	//
	// If neither or both operations point to graveyard, then let `aIsStrong` decide.
	//
	if (
		a.sourcePosition.isEqual( b.sourcePosition ) && !a.targetPosition.isEqual( b.targetPosition ) &&
		!context.bWasUndone && context.abRelation != 'splitAtSource'
	) {
		const aToGraveyard = a.targetPosition.root.rootName == '$graveyard';
		const bToGraveyard = b.targetPosition.root.rootName == '$graveyard';

		// If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
		const aIsWeak = aToGraveyard && !bToGraveyard;

		// If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
		const bIsWeak = bToGraveyard && !aToGraveyard;

		// Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
		const forceMove = bIsWeak || ( !aIsWeak && context.aIsStrong );

		if ( forceMove ) {
			const sourcePosition = b.targetPosition._getTransformedByMergeOperation( b );
			const targetPosition = a.targetPosition._getTransformedByMergeOperation( b );

			return [ new MoveOperation( sourcePosition, a.howMany, targetPosition, 0 ) ];
		} else {
			return [ new NoOperation( 0 ) ];
		}
	}

	// The default case.
	//
	if ( a.sourcePosition.hasSameParentAs( b.targetPosition ) ) {
		a.howMany += b.howMany;
	}

	a.sourcePosition = a.sourcePosition._getTransformedByMergeOperation( b );
	a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );

	// Handle positions in graveyard.
	// If graveyard positions are same and `a` operation is strong - do not transform.
	if ( !a.graveyardPosition.isEqual( b.graveyardPosition ) || !context.aIsStrong ) {
		a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation( b );
	}

	return [ a ];
} );

setTransformation( MergeOperation, MoveOperation, ( a, b, context ) => {
	// Case 1:
	//
	// The element to merge got removed.
	//
	// Merge operation does support merging elements which are not siblings. So it would not be a problem
	// from technical point of view. However, if the element was removed, the intention of the user deleting it
	// was to have it all deleted, together with its children. From user experience point of view, moving back the
	// removed nodes might be unexpected. This means that in this scenario we will block the merging.
	//
	// The exception of this rule would be if the remove operation was later undone.
	//
	const removedRange = Range._createFromPositionAndShift( b.sourcePosition, b.howMany );

	if ( b.type == 'remove' && !context.bWasUndone && !context.forceWeakRemove ) {
		if ( a.deletionPosition.hasSameParentAs( b.sourcePosition ) && removedRange.containsPosition( a.sourcePosition ) ) {
			return [ new NoOperation( 0 ) ];
		}
	}

	// In most cases we want `sourcePosition` to stick to previous and `targetPosition` to stick to next.
	// Usually, `sourcePosition` is at the beginning of the merged element and `targetPosition` is at the end of the merge-target element.
	//
	// However, `sourcePosition` and `targetPosition` may end up in the middle of an element due to some OT magic that happens during undo.
	// It is expected and used in `MergeOperation` x `SplitOperation` transformation.
	//
	// But when these positions are in the middle, it messes up the regular `MergeOperation` x `MoveOperation` transformation because
	// these positions may "follow" some moved elements. And we want them stick in the original elements.
	//
	// This is why we add two extra cases: (1) and (2).
	//
	// But after this `MergeOperation` is transformed by "this" move (which is undone), we also need to define extra cases for
	// the operation undoing previous move. These are (3) and (4).
	//
	// (1). Note that this case is also added to `updateRelations()` and sets `mergeSourceAffected` relation.
	//
	// [] is move operation, } is merge source position (sticks to previous by default):
	// <p>A[b]}c</p>  ->  <p>A}c</p>
	//
	if ( b.sourcePosition.getShiftedBy( b.howMany ).isEqual( a.sourcePosition ) ) {
		a.sourcePosition.stickiness = 'toNone';
	}

	// (3). This is the transformation for undoing operation of the above case.
	//
	// [] is move operation, } is merge source position (sticks to previous by default):
	// <p>A}c</p>  ->  <p>A[b]}c</p>  (instead of <p>A}[b]c</p>)
	//
	else if ( b.targetPosition.isEqual( a.sourcePosition ) && context.abRelation == 'mergeSourceAffected' ) {
		a.sourcePosition.stickiness = 'toNext';
	}

	// (2). Note that this case is also added to `updateRelations()` and sets `mergeTargetWasBefore` relation.
	//
	// [] is move operation, { is merge target position (sticks to next by default):
	// <p>A{[b]c</p>  ->  <p>A{c</p>
	//
	else if ( b.sourcePosition.isEqual( a.targetPosition ) ) {
		a.targetPosition.stickiness = 'toNone';
		a.howMany -= b.howMany;
	}

	// (4). This is the transformation for undoing operation of the above case.
	//
	// [] is move operation, { is merge target position (sticks to next by default):
	// <p>A{c</p>  ->  <p>A{[b]c</p>  (instead of <p>A[b]{c</p>)
	//
	else if ( b.targetPosition.isEqual( a.targetPosition ) && context.abRelation == 'mergeTargetWasBefore' ) {
		a.targetPosition.stickiness = 'toPrevious';
		a.howMany += b.howMany;
	}

	// The default case.
	else {
		if ( a.sourcePosition.hasSameParentAs( b.targetPosition ) ) {
			a.howMany += b.howMany;
		}

		if ( a.sourcePosition.hasSameParentAs( b.sourcePosition ) ) {
			a.howMany -= b.howMany;
		}
	}

	a.sourcePosition = a.sourcePosition._getTransformedByMoveOperation( b );
	a.targetPosition = a.targetPosition._getTransformedByMoveOperation( b );

	// After transformations are done, make sure to revert stickiness in case if (1) - (4) scenario happened.
	a.sourcePosition.stickiness = 'toPrevious';
	a.targetPosition.stickiness = 'toNext';

	// `MergeOperation` graveyard position is like `MoveOperation` target position. It is a position where element(s) will
	// be moved. Like in other similar cases, we need to consider the scenario when those positions are same.
	// Here, we will treat `MergeOperation` like it is always strong (see `InsertOperation` x `InsertOperation` for comparison).
	// This means that we won't transform graveyard position if it is equal to move operation target position.
	if ( !a.graveyardPosition.isEqual( b.targetPosition ) ) {
		a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
	}

	return [ a ];
} );

setTransformation( MergeOperation, SplitOperation, ( a, b, context ) => {
	if ( b.graveyardPosition ) {
		// If `b` operation defines graveyard position, a node from graveyard will be moved. This means that we need to
		// transform `a.graveyardPosition` accordingly.
		a.graveyardPosition = a.graveyardPosition._getTransformedByDeletion( b.graveyardPosition, 1 )!;

		// This is a scenario foreseen in `MergeOperation` x `MergeOperation`, with two identical merge operations.
		//
		// So, there was `MergeOperation` x `MergeOperation` transformation earlier. Now, `a` is a merge operation which
		// source position is in graveyard. Interestingly, split operation wants to use the node to be merged by `a`. This
		// means that `b` is undoing that merge operation from earlier, which caused `a` to be in graveyard.
		//
		// If that's the case, at this point, we will only "fix" `a.howMany`. It was earlier set to `0` in
		// `MergeOperation` x `MergeOperation` transformation. Later transformations in this function will change other
		// properties.
		//
		if ( a.deletionPosition.isEqual( b.graveyardPosition ) ) {
			a.howMany = b.howMany;
		}
	}

	// Case 1:
	//
	// Merge operation moves nodes to the place where split happens.
	// This is a classic situation when there are two paragraphs, and there is a split (enter) after the first
	// paragraph and there is a merge (delete) at the beginning of the second paragraph:
	//
	// <p>Foo{}</p><p>[]Bar</p>.
	//
	// Split is after `Foo`, while merge is from `Bar` to the end of `Foo`.
	//
	// State after split:
	// <p>Foo</p><p></p><p>Bar</p>
	//
	// Now, `Bar` should be merged to the new paragraph:
	// <p>Foo</p><p>Bar</p>
	//
	// Instead of merging it to the original paragraph:
	// <p>FooBar</p><p></p>
	//
	// This means that `targetPosition` needs to be transformed. This is the default case though.
	// For example, if the split would be after `F`, `targetPosition` should also be transformed.
	//
	// There are three exceptions, though, when we want to keep `targetPosition` as it was.
	//
	// First exception is when the merge target position is inside an element (not at the end, as usual). This
	// happens when the merge operation earlier was transformed by "the same" merge operation. If merge operation
	// targets inside the element we want to keep the original target position (and not transform it) because
	// we have additional context telling us that we want to merge to the original element. We can check if the
	// merge operation points inside element by checking what is `SplitOperation#howMany`. Since merge target position
	// is same as split position, if `howMany` is non-zero, it means that the merge target position is inside an element.
	//
	// Second exception is when the element to merge is in the graveyard and split operation uses it. In that case
	// if target position would be transformed, the merge operation would target at the source position:
	//
	// root: <p>Foo</p>				graveyard: <p></p>
	//
	// SplitOperation: root [ 0, 3 ] using graveyard [ 0 ] (howMany = 0)
	// MergeOperation: graveyard [ 0, 0 ] -> root [ 0, 3 ] (howMany = 0)
	//
	// Since split operation moves the graveyard node back to the root, the merge operation source position changes.
	// We would like to merge from the empty <p> to the "Foo" <p>:
	//
	// root: <p>Foo</p><p></p>			graveyard:
	//
	// MergeOperation#sourcePosition = root [ 1, 0 ]
	//
	// If `targetPosition` is transformed, it would become root [ 1, 0 ] as well. It has to be kept as it was.
	//
	// Third exception is connected with relations. If this happens during undo and we have explicit information
	// that target position has not been affected by the operation which is undone by this split then this split should
	// not move the target position either.
	//
	if ( a.targetPosition.isEqual( b.splitPosition ) ) {
		const mergeInside = b.howMany != 0;
		const mergeSplittingElement = b.graveyardPosition && a.deletionPosition.isEqual( b.graveyardPosition );

		if ( mergeInside || mergeSplittingElement || context.abRelation == 'mergeTargetNotMoved' ) {
			a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation( b );

			return [ a ];
		}
	}

	// Case 2:
	//
	// Merge source is at the same position as split position. This sometimes happen, mostly during undo.
	// The decision here is mostly to choose whether merge source position should stay where it is (so it will be at the end of the
	// split element) or should be move to the beginning of the new element.
	//
	if ( a.sourcePosition.isEqual( b.splitPosition ) ) {
		// Use context to check if `SplitOperation` is not undoing a merge operation, that didn't change the `a` operation.
		// This scenario happens the undone merge operation moved nodes at the source position of `a` operation.
		// In that case `a` operation source position should stay where it is.
		if ( context.abRelation == 'mergeSourceNotMoved' ) {
			a.howMany = 0;
			a.targetPosition = a.targetPosition._getTransformedBySplitOperation( b );

			return [ a ];
		}

		// This merge operation might have been earlier transformed by a merge operation which both merged the same element.
		// See that case in `MergeOperation` x `MergeOperation` transformation. In that scenario, if the merge operation has been undone,
		// the special case is not applied.
		//
		// Now, the merge operation is transformed by the split which has undone that previous merge operation.
		// So now we are fixing situation which was skipped in `MergeOperation` x `MergeOperation` case.
		//
		if ( context.abRelation == 'mergeSameElement' || a.sourcePosition.offset > 0 ) {
			a.sourcePosition = b.moveTargetPosition.clone();
			a.targetPosition = a.targetPosition._getTransformedBySplitOperation( b );

			return [ a ];
		}
	}

	// The default case.
	//
	if ( a.sourcePosition.hasSameParentAs( b.splitPosition ) ) {
		a.howMany = b.splitPosition.offset;
	}

	a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation( b );
	a.targetPosition = a.targetPosition._getTransformedBySplitOperation( b );

	return [ a ];
} );

// -----------------------

setTransformation( MoveOperation, InsertOperation, ( a, b ) => {
	const moveRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
	const transformed = moveRange._getTransformedByInsertOperation( b, false )[ 0 ];

	a.sourcePosition = transformed.start;
	a.howMany = transformed.end.offset - transformed.start.offset;

	// See `InsertOperation` x `MoveOperation` transformation for details on this case.
	//
	// In summary, both operations point to the same place, so the order of nodes needs to be decided.
	// `MoveOperation` is considered weaker, so it is always transformed, unless there was a certain relation
	// between operations.
	//
	if ( !a.targetPosition.isEqual( b.position ) ) {
		a.targetPosition = a.targetPosition._getTransformedByInsertOperation( b );
	}

	return [ a ];
} );

setTransformation( MoveOperation, MoveOperation, ( a, b, context ) => {
	//
	// Setting and evaluating some variables that will be used in special cases and default algorithm.
	//
	// Create ranges from `MoveOperations` properties.
	const rangeA = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
	const rangeB = Range._createFromPositionAndShift( b.sourcePosition, b.howMany );

	// Assign `context.aIsStrong` to a different variable, because the value may change during execution of
	// this algorithm and we do not want to override original `context.aIsStrong` that will be used in later transformations.
	let aIsStrong = context.aIsStrong;

	// This will be used to decide the order of nodes if both operations target at the same position.
	// By default, use strong/weak operation mechanism.
	let insertBefore = !context.aIsStrong;

	// If the relation is set, then use it to decide nodes order.
	if ( context.abRelation == 'insertBefore' || context.baRelation == 'insertAfter' ) {
		insertBefore = true;
	} else if ( context.abRelation == 'insertAfter' || context.baRelation == 'insertBefore' ) {
		insertBefore = false;
	}

	// `a.targetPosition` could be affected by the `b` operation. We will transform it.
	let newTargetPosition;

	if ( a.targetPosition.isEqual( b.targetPosition ) && insertBefore ) {
		newTargetPosition = a.targetPosition._getTransformedByDeletion(
			b.sourcePosition,
			b.howMany
		);
	} else {
		newTargetPosition = a.targetPosition._getTransformedByMove(
			b.sourcePosition,
			b.targetPosition,
			b.howMany
		);
	}

	//
	// Special case #1 + mirror.
	//
	// Special case when both move operations' target positions are inside nodes that are
	// being moved by the other move operation. So in other words, we move ranges into inside of each other.
	// This case can't be solved reasonably (on the other hand, it should not happen often).
	if ( _moveTargetIntoMovedRange( a, b ) && _moveTargetIntoMovedRange( b, a ) ) {
		// Instead of transforming operation, we return a reverse of the operation that we transform by.
		// So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
		return [ b.getReversed() ];
	}
	//
	// End of special case #1.
	//

	//
	// Special case #2.
	//
	// Check if `b` operation targets inside `rangeA`.
	const bTargetsToA = rangeA.containsPosition( b.targetPosition );

	// If `b` targets to `rangeA` and `rangeA` contains `rangeB`, `b` operation has no influence on `a` operation.
	// You might say that operation `b` is captured inside operation `a`.
	if ( bTargetsToA && rangeA.containsRange( rangeB, true ) ) {
		// There is a mini-special case here, where `rangeB` is on other level than `rangeA`. That's why
		// we need to transform `a` operation anyway.
		( rangeA as any ).start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
		( rangeA as any ).end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );

		return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition! );
	}

	//
	// Special case #2 mirror.
	//
	const aTargetsToB = rangeB.containsPosition( a.targetPosition );

	if ( aTargetsToB && rangeB.containsRange( rangeA, true ) ) {
		// `a` operation is "moved together" with `b` operation.
		// Here, just move `rangeA` "inside" `rangeB`.
		( rangeA as any ).start = rangeA.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
		( rangeA as any ).end = rangeA.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );

		return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition! );
	}
	//
	// End of special case #2.
	//

	//
	// Special case #3 + mirror.
	//
	// `rangeA` has a node which is an ancestor of `rangeB`. In other words, `rangeB` is inside `rangeA`
	// but not on the same tree level. In such case ranges have common part but we have to treat it
	// differently, because in such case those ranges are not really conflicting and should be treated like
	// two separate ranges. Also we have to discard two difference parts.
	const aCompB = compareArrays( a.sourcePosition.getParentPath(), b.sourcePosition.getParentPath() );

	if ( aCompB == 'prefix' || aCompB == 'extension' ) {
		// Transform `rangeA` by `b` operation and make operation out of it, and that's all.
		// Note that this is a simplified version of default case, but here we treat the common part (whole `rangeA`)
		// like a one difference part.
		( rangeA as any ).start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
		( rangeA as any ).end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );

		return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition! );
	}
	//
	// End of special case #3.
	//

	//
	// Default case - ranges are on the same level or are not connected with each other.
	//
	// Modifier for default case.
	// Modifies `aIsStrong` flag in certain conditions.
	//
	// If only one of operations is a remove operation, we force remove operation to be the "stronger" one
	// to provide more expected results.
	if ( a.type == 'remove' && b.type != 'remove' && !context.aWasUndone && !context.forceWeakRemove ) {
		aIsStrong = true;
	} else if ( a.type != 'remove' && b.type == 'remove' && !context.bWasUndone && !context.forceWeakRemove ) {
		aIsStrong = false;
	}

	// Handle operation's source ranges - check how `rangeA` is affected by `b` operation.
	// This will aggregate transformed ranges.
	const ranges = [];

	// Get the "difference part" of `a` operation source range.
	// This is an array with one or two ranges. Two ranges if `rangeB` is inside `rangeA`.
	const difference = rangeA.getDifference( rangeB );

	for ( const range of difference ) {
		// Transform those ranges by `b` operation. For example if `b` moved range from before those ranges, fix those ranges.
		( range as any ).start = range.start._getTransformedByDeletion( b.sourcePosition, b.howMany );
		( range as any ).end = range.end._getTransformedByDeletion( b.sourcePosition, b.howMany );

		// If `b` operation targets into `rangeA` on the same level, spread `rangeA` into two ranges.
		const shouldSpread = compareArrays( range.start.getParentPath(), b.getMovedRangeStart().getParentPath() ) == 'same';
		const newRanges = range._getTransformedByInsertion( b.getMovedRangeStart(), b.howMany, shouldSpread );

		ranges.push( ...newRanges );
	}

	// Then, we have to manage the "common part" of both move ranges.
	const common = rangeA.getIntersection( rangeB );

	if ( common !== null && aIsStrong ) {
		// Calculate the new position of that part of original range.
		( common as any ).start = common.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
		( common as any ).end = common.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );

		// Take care of proper range order.
		//
		// Put `common` at appropriate place. Keep in mind that we are interested in original order.
		// Basically there are only three cases: there is zero, one or two difference ranges.
		//
		// If there is zero difference ranges, just push `common` in the array.
		if ( ranges.length === 0 ) {
			ranges.push( common );
		}
		// If there is one difference range, we need to check whether common part was before it or after it.
		else if ( ranges.length == 1 ) {
			if ( rangeB.start.isBefore( rangeA.start ) || rangeB.start.isEqual( rangeA.start ) ) {
				ranges.unshift( common );
			} else {
				ranges.push( common );
			}
		}
		// If there are more ranges (which means two), put common part between them. This is the only scenario
		// where there could be two difference ranges so we don't have to make any comparisons.
		else {
			ranges.splice( 1, 0, common );
		}
	}

	if ( ranges.length === 0 ) {
		// If there are no "source ranges", nothing should be changed.
		// Note that this can happen only if `aIsStrong == false` and `rangeA.isEqual( rangeB )`.
		return [ new NoOperation( a.baseVersion ) ];
	}

	return _makeMoveOperationsFromRanges( ranges, newTargetPosition! );
} );

setTransformation( MoveOperation, SplitOperation, ( a, b, context ) => {
	let newTargetPosition = a.targetPosition.clone();

	// Do not transform if target position is same as split insertion position and this split comes from undo.
	// This should be done on relations but it is too much work for now as it would require relations working in collaboration.
	// We need to make a decision how we will resolve such conflict and this is less harmful way.
	if ( !a.targetPosition.isEqual( b.insertionPosition ) || !b.graveyardPosition || context.abRelation == 'moveTargetAfter' ) {
		newTargetPosition = a.targetPosition._getTransformedBySplitOperation( b );
	}

	// Case 1:
	//
	// Last element in the moved range got split.
	//
	// In this case the default range transformation will not work correctly as the element created by
	// split operation would be outside the range. The range to move needs to be fixed manually.
	//
	const moveRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );

	if ( moveRange.end.isEqual( b.insertionPosition ) ) {
		// Do it only if this is a "natural" split, not a one that comes from undo.
		// If this is undo split, only `targetPosition` needs to be changed (if the move is a remove).
		if ( !b.graveyardPosition ) {
			a.howMany++;
		}

		a.targetPosition = newTargetPosition;

		return [ a ];
	}

	// Case 2:
	//
	// Split happened between the moved nodes. In this case two ranges to move need to be generated.
	//
	// Characters `ozba` are moved to the end of paragraph `Xyz` but split happened.
	// <p>F[oz|ba]r</p><p>Xyz</p>
	//
	// After split:
	// <p>F[oz</p><p>ba]r</p><p>Xyz</p>
	//
	// Correct ranges:
	// <p>F[oz]</p><p>[ba]r</p><p>Xyz</p>
	//
	// After move:
	// <p>F</p><p>r</p><p>Xyzozba</p>
	//
	if ( moveRange.start.hasSameParentAs( b.splitPosition ) && moveRange.containsPosition( b.splitPosition ) ) {
		let rightRange = new Range( b.splitPosition, moveRange.end );
		rightRange = rightRange._getTransformedBySplitOperation( b );

		const ranges = [
			new Range( moveRange.start, b.splitPosition ),
			rightRange
		];

		return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
	}

	// Case 3:
	//
	// Move operation targets at the split position. We need to decide if the nodes should be inserted
	// at the end of the split element or at the beginning of the new element.
	//
	if ( a.targetPosition.isEqual( b.splitPosition ) && context.abRelation == 'insertAtSource' ) {
		newTargetPosition = b.moveTargetPosition;
	}

	// Case 4:
	//
	// Move operation targets just after the split element. We need to decide if the nodes should be inserted
	// between two parts of split element, or after the new element.
	//
	// Split at `|`, while move operation moves `<p>Xyz</p>` and targets at `^`:
	// <p>Foo|bar</p>^<p>baz</p>
	// <p>Foo</p>^<p>bar</p><p>baz</p> or <p>Foo</p><p>bar</p>^<p>baz</p>?
	//
	// If there is no contextual information between operations (for example, they come from collaborative
	// editing), we don't want to put some unrelated content (move) between parts of related content (split parts).
	// However, if the split is from undo, in the past, the moved content might be targeting between the
	// split parts, meaning that was exactly user's intention:
	//
	// <p>Foo</p>^<p>bar</p>		<--- original situation, in "past".
	// <p>Foobar</p>^				<--- after merge target position is transformed.
	// <p>Foo|bar</p>^				<--- then the merge is undone, and split happens, which leads us to current situation.
	//
	// In this case it is pretty clear that the intention was to put new paragraph between those nodes,
	// so we need to transform accordingly. We can detect this scenario thanks to relations.
	//
	if ( a.targetPosition.isEqual( b.insertionPosition ) && context.abRelation == 'insertBetween' ) {
		newTargetPosition = a.targetPosition;
	}

	// The default case.
	//
	const transformed = moveRange._getTransformedBySplitOperation( b );
	const ranges = [ transformed ];

	// Case 5:
	//
	// Moved range contains graveyard element used by split operation. Add extra move operation to the result.
	//
	if ( b.graveyardPosition ) {
		const movesGraveyardElement = moveRange.start.isEqual( b.graveyardPosition ) || moveRange.containsPosition( b.graveyardPosition );

		if ( a.howMany > 1 && movesGraveyardElement && !context.aWasUndone ) {
			ranges.push( Range._createFromPositionAndShift( b.insertionPosition, 1 ) );
		}
	}

	return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
} );

setTransformation( MoveOperation, MergeOperation, ( a, b, context ) => {
	const movedRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );

	if ( b.deletionPosition.hasSameParentAs( a.sourcePosition ) && movedRange.containsPosition( b.sourcePosition ) ) {
		if ( a.type == 'remove' && !context.forceWeakRemove ) {
			// Case 1:
			//
			// The element to remove got merged.
			//
			// Merge operation does support merging elements which are not siblings. So it would not be a problem
			// from technical point of view. However, if the element was removed, the intention of the user
			// deleting it was to have it all deleted. From user experience point of view, moving back the
			// removed nodes might be unexpected. This means that in this scenario we will reverse merging and remove the element.
			//
			if ( !context.aWasUndone ) {
				const results = [];

				let gyMoveSource = b.graveyardPosition.clone();
				let splitNodesMoveSource = b.targetPosition._getTransformedByMergeOperation( b );

				if ( a.howMany > 1 ) {
					results.push( new MoveOperation( a.sourcePosition, a.howMany - 1, a.targetPosition, 0 ) );

					gyMoveSource = gyMoveSource._getTransformedByMove( a.sourcePosition, a.targetPosition, a.howMany - 1 );
					splitNodesMoveSource = splitNodesMoveSource._getTransformedByMove( a.sourcePosition, a.targetPosition, a.howMany - 1 );
				}

				const gyMoveTarget = b.deletionPosition._getCombined( a.sourcePosition, a.targetPosition );
				const gyMove = new MoveOperation( gyMoveSource, 1, gyMoveTarget, 0 );

				const splitNodesMoveTargetPath = gyMove.getMovedRangeStart().path.slice();
				splitNodesMoveTargetPath.push( 0 );

				const splitNodesMoveTarget = new Position( gyMove.targetPosition.root, splitNodesMoveTargetPath );
				splitNodesMoveSource = splitNodesMoveSource._getTransformedByMove( gyMoveSource, gyMoveTarget, 1 );
				const splitNodesMove = new MoveOperation( splitNodesMoveSource, b.howMany, splitNodesMoveTarget, 0 );

				results.push( gyMove );
				results.push( splitNodesMove );

				return results;
			}
		} else {
			// Case 2:
			//
			// The element to move got merged and it was the only element to move.
			// In this case just don't do anything, leave the node in the graveyard. Without special case
			// it would be a move operation that moves 0 nodes, so maybe it is better just to return no-op.
			//
			if ( a.howMany == 1 ) {
				if ( !context.bWasUndone ) {
					return [ new NoOperation( 0 ) ];
				} else {
					a.sourcePosition = b.graveyardPosition.clone();
					a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );

					return [ a ];
				}
			}
		}
	}

	// The default case.
	//
	const moveRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
	const transformed = moveRange._getTransformedByMergeOperation( b );

	a.sourcePosition = transformed.start;
	a.howMany = transformed.end.offset - transformed.start.offset;
	a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );

	return [ a ];
} );

// -----------------------

setTransformation( RenameOperation, InsertOperation, ( a, b ) => {
	a.position = a.position._getTransformedByInsertOperation( b );

	return [ a ];
} );

setTransformation( RenameOperation, MergeOperation, ( a, b ) => {
	// Case 1:
	//
	// Element to rename got merged, so it was moved to `b.graveyardPosition`.
	//
	if ( a.position.isEqual( b.deletionPosition ) ) {
		a.position = b.graveyardPosition.clone();
		a.position.stickiness = 'toNext';

		return [ a ];
	}

	a.position = a.position._getTransformedByMergeOperation( b );

	return [ a ];
} );

setTransformation( RenameOperation, MoveOperation, ( a, b ) => {
	a.position = a.position._getTransformedByMoveOperation( b );

	return [ a ];
} );

setTransformation( RenameOperation, RenameOperation, ( a, b, context ) => {
	if ( a.position.isEqual( b.position ) ) {
		if ( context.aIsStrong ) {
			a.oldName = b.newName;
		} else {
			return [ new NoOperation( 0 ) ];
		}
	}

	return [ a ];
} );

setTransformation( RenameOperation, SplitOperation, ( a, b ) => {
	// Case 1:
	//
	// The element to rename has been split. In this case, the new element should be also renamed.
	//
	// User decides to change the paragraph to a list item:
	// <paragraph>Foobar</paragraph>
	//
	// However, in meantime, split happens:
	// <paragraph>Foo</paragraph><paragraph>bar</paragraph>
	//
	// As a result, rename both elements:
	// <listItem>Foo</listItem><listItem>bar</listItem>
	//
	const renamePath = a.position.path;
	const splitPath = b.splitPosition.getParentPath();

	if ( compareArrays( renamePath, splitPath ) == 'same' && !b.graveyardPosition ) {
		const extraRename = new RenameOperation( a.position.getShiftedBy( 1 ), a.oldName, a.newName, 0 );

		return [ a, extraRename ];
	}

	// The default case.
	//
	a.position = a.position._getTransformedBySplitOperation( b );

	return [ a ];
} );

// -----------------------

setTransformation( RootAttributeOperation, RootAttributeOperation, ( a, b, context ) => {
	if ( a.root === b.root && a.key === b.key ) {
		if ( !context.aIsStrong || a.newValue === b.newValue ) {
			return [ new NoOperation( 0 ) ];
		} else {
			a.oldValue = b.newValue;
		}
	}

	return [ a ];
} );

// -----------------------

setTransformation( RootOperation, RootOperation, ( a, b ) => {
	if ( a.rootName === b.rootName && a.isAdd === b.isAdd ) {
		return [ new NoOperation( 0 ) ];
	}

	return [ a ];
} );

// -----------------------

setTransformation( SplitOperation, InsertOperation, ( a, b ) => {
	// The default case.
	//
	if ( a.splitPosition.hasSameParentAs( b.position ) && a.splitPosition.offset < b.position.offset ) {
		a.howMany += b.howMany;
	}

	a.splitPosition = a.splitPosition._getTransformedByInsertOperation( b );
	a.insertionPosition = a.insertionPosition._getTransformedByInsertOperation( b );

	return [ a ];
} );

setTransformation( SplitOperation, MergeOperation, ( a, b, context ) => {
	// Case 1:
	//
	// Split element got merged. If two different elements were merged, clients will have different content.
	//
	// Example. Merge at `{}`, split at `[]`:
	// <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
	//
	// On merge side it will look like this:
	// <heading>FooB[]ar</heading>
	// <heading>FooB</heading><heading>ar</heading>
	//
	// On split side it will look like this:
	// <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
	// <heading>FooB</heading><paragraph>ar</paragraph>
	//
	// Clearly, the second element is different for both clients.
	//
	// We could use the removed merge element from graveyard as a split element but then clients would have a different
	// model state (in graveyard), because the split side client would still have an element in graveyard (removed by merge).
	//
	// To overcome this, in `SplitOperation` x `MergeOperation` transformation we will add additional `SplitOperation`
	// in the graveyard, which will actually clone the merged-and-deleted element. Then, that cloned element will be
	// used for splitting. Example below.
	//
	// Original state:
	// <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
	//
	// Merge side client:
	//
	// After merge:
	// <heading>FooB[]ar</heading>                                 graveyard: <paragraph></paragraph>
	//
	// Extra split:
	// <heading>FooB[]ar</heading>                                 graveyard: <paragraph></paragraph><paragraph></paragraph>
	//
	// Use the "cloned" element from graveyard:
	// <heading>FooB</heading><paragraph>ar</paragraph>            graveyard: <paragraph></paragraph>
	//
	// Split side client:
	//
	// After split:
	// <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
	//
	// After merge:
	// <heading>FooB</heading><paragraph>ar</paragraph>            graveyard: <paragraph></paragraph>
	//
	// This special case scenario only applies if the original split operation clones the split element.
	// If the original split operation has `graveyardPosition` set, it all doesn't have sense because split operation
	// knows exactly which element it should use. So there would be no original problem with different contents.
	//
	// Additionally, the special case applies only if the merge wasn't already undone.
	//
	if ( !a.graveyardPosition && !context.bWasUndone && a.splitPosition.hasSameParentAs( b.sourcePosition ) ) {
		const splitPath = b.graveyardPosition.path.slice();
		splitPath.push( 0 );

		const splitPosition = new Position( b.graveyardPosition.root, splitPath );
		const insertionPosition = SplitOperation.getInsertionPosition( new Position( b.graveyardPosition.root, splitPath ) );

		const additionalSplit = new SplitOperation( splitPosition, 0, insertionPosition, null, 0 );

		a.splitPosition = a.splitPosition._getTransformedByMergeOperation( b );
		a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
		a.graveyardPosition = additionalSplit.insertionPosition.clone();
		a.graveyardPosition.stickiness = 'toNext';

		return [ additionalSplit, a ];
	}

	// The default case.
	//
	if ( a.splitPosition.hasSameParentAs( b.deletionPosition ) && !a.splitPosition.isAfter( b.deletionPosition ) ) {
		a.howMany--;
	}

	if ( a.splitPosition.hasSameParentAs( b.targetPosition ) ) {
		a.howMany += b.howMany;
	}

	a.splitPosition = a.splitPosition._getTransformedByMergeOperation( b );
	a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );

	if ( a.graveyardPosition ) {
		a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation( b );
	}

	return [ a ];
} );

setTransformation( SplitOperation, MoveOperation, ( a, b, context ) => {
	const rangeToMove = Range._createFromPositionAndShift( b.sourcePosition, b.howMany );

	if ( a.graveyardPosition ) {
		// Case 1:
		//
		// Split operation graveyard node was moved. In this case move operation is stronger. Since graveyard element
		// is already moved to the correct position, we need to only move the nodes after the split position.
		// This will be done by `MoveOperation` instead of `SplitOperation`.
		//
		const gyElementMoved = rangeToMove.start.isEqual( a.graveyardPosition ) || rangeToMove.containsPosition( a.graveyardPosition );

		if ( !context.bWasUndone && gyElementMoved ) {
			const sourcePosition = a.splitPosition._getTransformedByMoveOperation( b );

			const newParentPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
			const newTargetPath = newParentPosition.path.slice();
			newTargetPath.push( 0 );

			const newTargetPosition = new Position( newParentPosition.root, newTargetPath );
			const moveOp = new MoveOperation( sourcePosition, a.howMany, newTargetPosition, 0 );

			return [ moveOp ];
		}

		a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
	}

	// Case 2:
	//
	// Split is at a position where nodes were moved.
	//
	// This is a scenario described in `MoveOperation` x `SplitOperation` transformation but from the
	// "split operation point of view".
	//
	const splitAtTarget = a.splitPosition.isEqual( b.targetPosition );

	if ( splitAtTarget && ( context.baRelation == 'insertAtSource' || context.abRelation == 'splitBefore' ) ) {
		a.howMany += b.howMany;
		a.splitPosition = a.splitPosition._getTransformedByDeletion( b.sourcePosition, b.howMany )!;
		a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );

		return [ a ];
	}

	if ( splitAtTarget && context.abRelation && context.abRelation.howMany ) {
		const { howMany, offset } = context.abRelation;

		a.howMany += howMany;
		a.splitPosition = a.splitPosition.getShiftedBy( offset );

		return [ a ];
	}

	// Case 3:
	//
	// If the split position is inside the moved range, we need to shift the split position to a proper place.
	// The position cannot be moved together with moved range because that would result in splitting of an incorrect element.
	//
	// Characters `bc` should be moved to the second paragraph while split position is between them:
	// <paragraph>A[b|c]d</paragraph><paragraph>Xyz</paragraph>
	//
	// After move, new split position is incorrect:
	// <paragraph>Ad</paragraph><paragraph>Xb|cyz</paragraph>
	//
	// Correct split position:
	// <paragraph>A|d</paragraph><paragraph>Xbcyz</paragraph>
	//
	// After split:
	// <paragraph>A</paragraph><paragraph>d</paragraph><paragraph>Xbcyz</paragraph>
	//
	if ( a.splitPosition.hasSameParentAs( b.sourcePosition ) && rangeToMove.containsPosition( a.splitPosition ) ) {
		const howManyRemoved = b.howMany - ( a.splitPosition.offset - b.sourcePosition.offset );
		a.howMany -= howManyRemoved;

		if ( a.splitPosition.hasSameParentAs( b.targetPosition ) && a.splitPosition.offset < b.targetPosition.offset ) {
			a.howMany += b.howMany;
		}

		a.splitPosition = b.sourcePosition.clone();
		a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );

		return [ a ];
	}

	// The default case.
	// Don't change `howMany` if move operation does not really move anything.
	//
	if ( !b.sourcePosition.isEqual( b.targetPosition ) ) {
		if ( a.splitPosition.hasSameParentAs( b.sourcePosition ) && a.splitPosition.offset <= b.sourcePosition.offset ) {
			a.howMany -= b.howMany;
		}

		if ( a.splitPosition.hasSameParentAs( b.targetPosition ) && a.splitPosition.offset < b.targetPosition.offset ) {
			a.howMany += b.howMany;
		}
	}

	// Change position stickiness to force a correct transformation.
	a.splitPosition.stickiness = 'toNone';
	a.splitPosition = a.splitPosition._getTransformedByMoveOperation( b );
	a.splitPosition.stickiness = 'toNext';

	if ( a.graveyardPosition ) {
		a.insertionPosition = a.insertionPosition._getTransformedByMoveOperation( b );
	} else {
		a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
	}

	return [ a ];
} );

setTransformation( SplitOperation, SplitOperation, ( a, b, context ) => {
	// Case 1:
	//
	// Split at the same position.
	//
	// If there already was a split at the same position as in `a` operation, it means that the intention
	// conveyed by `a` operation has already been fulfilled and `a` should not do anything (to avoid double split).
	//
	// However, there is a difference if these are new splits or splits created by undo. These have different
	// intentions. Also splits moving back different elements from graveyard have different intentions. They
	// are just different operations.
	//
	// So we cancel split operation only if it was really identical.
	//
	// Also, there is additional case, where split operations aren't identical and should not be cancelled, however the
	// default transformation is incorrect too.
	//
	if ( a.splitPosition.isEqual( b.splitPosition ) ) {
		if ( !a.graveyardPosition && !b.graveyardPosition ) {
			return [ new NoOperation( 0 ) ];
		}

		if ( a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual( b.graveyardPosition ) ) {
			return [ new NoOperation( 0 ) ];
		}

		// Use context to know that the `a.splitPosition` should stay where it is.
		// This happens during undo when first a merge operation moved nodes to `a.splitPosition` and now `b` operation undoes that merge.
		if ( context.abRelation == 'splitBefore' ) {
			// Since split is at the same position, there are no nodes left to split.
			a.howMany = 0;

			// Note: there was `if ( a.graveyardPosition )` here but it was uncovered in tests and I couldn't find any scenarios for now.
			// That would have to be a `SplitOperation` that didn't come from undo but is transformed by operations that were undone.
			// It could happen if `context` is enabled in collaboration.
			a.graveyardPosition = a.graveyardPosition!._getTransformedBySplitOperation( b );

			return [ a ];
		}
	}

	// Case 2:
	//
	// Same node is using to split different elements. This happens in undo when previously same element was merged to
	// two different elements. This is described in `MergeOperation` x `MergeOperation` transformation.
	//
	// In this case we will follow the same logic. We will assume that `insertionPosition` is same for both
	// split operations. This might not always be true but in the real cases that were experienced it was. After all,
	// if these splits are reverses of merge operations that were merging the same element, then the `insertionPosition`
	// should be same for both of those splits.
	//
	// Again, we will decide which operation is stronger by checking if split happens in graveyard or in non-graveyard root.
	//
	if ( a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual( b.graveyardPosition ) ) {
		const aInGraveyard = a.splitPosition.root.rootName == '$graveyard';
		const bInGraveyard = b.splitPosition.root.rootName == '$graveyard';

		// If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
		const aIsWeak = aInGraveyard && !bInGraveyard;

		// If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
		const bIsWeak = bInGraveyard && !aInGraveyard;

		// Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
		const forceMove = bIsWeak || ( !aIsWeak && context.aIsStrong );

		if ( forceMove ) {
			const result = [];

			// First we need to move any nodes split by `b` back to where they were.
			// Do it only if `b` actually moved something.
			if ( b.howMany ) {
				result.push( new MoveOperation( b.moveTargetPosition, b.howMany, b.splitPosition, 0 ) );
			}

			// Then we need to move nodes from `a` split position to their new element.
			// Do it only if `a` actually should move something.
			if ( a.howMany ) {
				result.push( new MoveOperation( a.splitPosition, a.howMany, a.moveTargetPosition, 0 ) );
			}

			return result;
		} else {
			return [ new NoOperation( 0 ) ];
		}
	}

	if ( a.graveyardPosition ) {
		a.graveyardPosition = a.graveyardPosition._getTransformedBySplitOperation( b );
	}

	// Case 3:
	//
	// Position where operation `b` inserted a new node after split is the same as the operation `a` split position.
	// As in similar cases, there is ambiguity if the split should be before the new node (created by `b`) or after.
	//
	if ( a.splitPosition.isEqual( b.insertionPosition ) && context.abRelation == 'splitBefore' ) {
		a.howMany++;

		return [ a ];
	}

	// Case 4:
	//
	// This is a mirror to the case 2. above.
	//
	if ( b.splitPosition.isEqual( a.insertionPosition ) && context.baRelation == 'splitBefore' ) {
		const newPositionPath = b.insertionPosition.path.slice();
		newPositionPath.push( 0 );

		const newPosition = new Position( b.insertionPosition.root, newPositionPath );
		const moveOp = new MoveOperation( a.insertionPosition, 1, newPosition, 0 );

		return [ a, moveOp ];
	}

	// The default case.
	//
	if ( a.splitPosition.hasSameParentAs( b.splitPosition ) && a.splitPosition.offset < b.splitPosition.offset ) {
		a.howMany -= b.howMany;
	}

	a.splitPosition = a.splitPosition._getTransformedBySplitOperation( b );
	a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );

	return [ a ];
} );

/**
 * Checks whether `MoveOperation` `targetPosition` is inside a node from the moved range of the other `MoveOperation`.
 */
function _moveTargetIntoMovedRange( a: MoveOperation, b: MoveOperation ) {
	return a.targetPosition._getTransformedByDeletion( b.sourcePosition, b.howMany ) === null;
}

/**
 * Helper function for `MoveOperation` x `MoveOperation` transformation. Converts given ranges and target position to
 * move operations and returns them.
 *
 * Ranges and target position will be transformed on-the-fly when generating operations.
 *
 * Given `ranges` should be in the order of how they were in the original transformed operation.
 *
 * Given `targetPosition` is the target position of the first range from `ranges`.
 */
function _makeMoveOperationsFromRanges( ranges: Array<Range>, targetPosition: Position ) {
	// At this moment we have some ranges and a target position, to which those ranges should be moved.
	// Order in `ranges` array is the go-to order of after transformation.
	//
	// We are almost done. We have `ranges` and `targetPosition` to make operations from.
	// Unfortunately, those operations may affect each other. Precisely, first operation after move
	// may affect source range and target position of second and third operation. Same with second
	// operation affecting third.
	//
	// We need to fix those source ranges and target positions once again, before converting `ranges` to operations.
	const operations = [];

	// Keep in mind that nothing will be transformed if there is just one range in `ranges`.
	for ( let i = 0; i < ranges.length; i++ ) {
		// Create new operation out of a range and target position.
		const range = ranges[ i ];
		const op = new MoveOperation(
			range.start,
			range.end.offset - range.start.offset,
			targetPosition,
			0
		);

		operations.push( op );

		// Transform other ranges by the generated operation.
		for ( let j = i + 1; j < ranges.length; j++ ) {
			// All ranges in `ranges` array should be:
			//
			// * non-intersecting (these are part of original operation source range), and
			// * `targetPosition` does not target into them (opposite would mean that transformed operation targets "inside itself").
			//
			// This means that the transformation will be "clean" and always return one result.
			ranges[ j ] = ranges[ j ]._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany )[ 0 ];
		}

		targetPosition = targetPosition._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany );
	}

	return operations;
}