All files / src/dm ve.dm.TransactionSquasher.js

94.27% Statements 214/227
86.77% Branches 105/121
100% Functions 16/16
94.14% Lines 209/222

Press n or j to go to the next uncovered block, b, p or k for the previous block.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566                                                                              1x       98x         98x         98x         98x                   98x         98x           98x         1x                     1x   5314x     994x                 1x 99x 1x   98x 98x 560x   98x                   1x 98x                       1x     560x 560x 560x 560x 560x 560x 560x   560x 1663x 1663x 1103x 1103x 1628x 1628x   560x 548x 548x 158x 158x   548x 548x 542x 542x   12x 12x                           1x 1628x 1628x       1628x 1094x 1094x 1094x 1094x 1094x   534x   529x         529x 529x 529x 529x   5x   5x 5x   5x 5x                             1x 158x   158x 158x     158x 35x   35x 35x 35x 28x   28x   28x   35x 35x   25x               10x 10x 5x 5x 5x   10x             35x 28x   35x 35x   123x   121x   121x 121x 981x             121x 121x   25x 25x   25x   121x 121x   2x   2x 2x 2x   2x 2x                                     1x 542x 542x 473x   469x       473x 473x 24x 24x 24x     473x           473x 473x 473x   69x         69x 69x 69x 69x 69x                               1x 12x 12x   7x 7x     7x   5x 5x 4x       4x   1x           1x 1x 1x 1x                           1x 9x 2x   9x           9x 2x 2x 2x     7x                 1x 2340x       1041x 1041x   1041x 1041x                       1x 2286x 2286x 2286x   2286x 2286x 2822x 11x   2811x 1180x   651x   1631x 7x 1624x 1624x     536x 536x 536x                           1x 505x 505x   456x   49x     49x 49x 49x     49x     49x 49x 49x 49x 49x               1x 55x 55x 5x   50x 25x 25x 25x 25x 25x 25x 3x 3x           3x           3x 3x 3x        
/*!
 * VisualEditor DataModel TransactionSquasher class.
 *
 * @copyright See AUTHORS.txt
 */
 
/**
 * Squasher to create one transaction from multiple transactions applicable in turn
 *
 * The squashed transaction has the same effect on a document as applying the original
 * transactions in turn, but it may cause rebase conflicts where the original sequence
 * of transactions would not have.
 *
 * Suppose we have linmod arrays A, B, C, D. Note that (x,A->B,m) then (x,C->D,n) becomes
 * (x,A.concat(C*)->D.concat(B*),min(m,n)) Where len = min(B.length, C.length) and
 * C*=C.slice(len) and B*=B.slice(len).  I.e. "A->B then C->D" becomes "remove A, remove C*,
 * insert D, insert B*". Examples:
 * 1234Aa5678 (4,Aa->Bb,4) 1234Bb5678 (4,B->D,5) 1234Db5678 --> (4,Aa->Db,4)
 * 1234Aa5678 (4,Aa->Bb,4) 1234Bb5678 (4,Bb5->Dd,3) 1234Dd678 --> (4,Aa5->Dd,3)
 *
 * The same sort of thing happens if the starts are not the same, e.g.
 * helloworld (2,ll>LL,1,wo>WO,3) heLLoWOrld (3,LoW>HI,4) heLHIrld --> (2,llowo>LHI,3)
 * hiwed (1,i>ello,1,e>orl,1) helloworld (2,llowor>a,2) heald --> (1,iwe>eal,1)
 *
 * However, removal followed by reinsertion cannot be stripped out entirely, because then
 * the squashed transaction, considered as a partial function between documents, would have
 * a larger preimage than the composition of the original transactions. This can probably
 * break things like associativity). Example:
 *
 * hello! (1,ello>iworld,1) hiworld! (1,i>ello,6) helloworld! --> (1,ello>elloworld,1)
 *
 * For annotations in the follow-up transaction, two forms of processing are needed: annotating
 * previously-inserted content, and adding the annotations operation into the transaction for
 * retained ranges.
 *
 * @class
 * @constructor
 * @param {ve.dm.Transaction} transaction Base transaction to clone then squash others onto
 */
ve.dm.TransactionSquasher = function VeDmTransactionSquasher( transaction ) {
	/**
	 * @property {ve.dm.Transaction} transaction Transaction being squashed together
	 */
	this.transaction = transaction.clone();
 
	/**
	 * @property {Object[]} operations Reference to .operations within the tx
	 */
	this.operations = this.transaction.operations;
 
	/**
	 * @property {Object} op During squashIn, the current op within operations
	 */
	this.op = this.operations[ 0 ];
 
	/**
	 * @property {number} index During squashIn, index of current op within operations
	 */
	this.index = 0;
 
	/**
	 * During squashIn, post-transaction offset within the current op
	 *
	 * @property {number} offset During squashIn, post-tx linmod offset within current op.
	 * "Post transaction" means that for replacements, the offset is within the insert
	 * block. The reason we care about post-transaction offsets is that the match the
	 * pre-transaction offsets of the next transaction.
	 */
	this.offset = 0;
 
	/**
	 * @property {number} globalOffset During squashIn, global offset over all operations
	 */
	this.globalOffset = 0;
 
	/**
	 * @property {Object} attributeOperations During squashIn, live references to attribute
	 * operations at current offset, keyed by attribute name, or null if at an open element
	 */
	this.attributeOperations = {};
};
 
/* Inheritance */
 
OO.initClass( ve.dm.TransactionSquasher );
 
/* Static methods */
 
/**
 * Test whether two linmod items have equal values
 *
 * @param {any} item1 A data item
 * @param {any} item2 Another data item
 * @return {boolean} Whether the items have equal values
 */
ve.dm.TransactionSquasher.static.equalItems = function ( item1, item2 ) {
	function stringifyItem( item ) {
		return JSON.stringify( item, ( key, value ) => key === 'changesSinceLoad' ? undefined : value );
	}
	// Compare serializations, so that reference types need not be reference-equal
	return stringifyItem( item1 ) === stringifyItem( item2 );
};
 
/**
 * Squash an array of consecutive transactions into a single transaction
 *
 * @param {ve.dm.Transaction[]} transactions Non-empty array of consecutive transactions
 * @return {ve.dm.Transaction} Single transaction with the same content as the transaction array
 */
ve.dm.TransactionSquasher.static.squash = function ( transactions ) {
	if ( transactions.length === 0 ) {
		throw new Error( 'Cannot squash empty transaction array' );
	}
	const squasher = new ve.dm.TransactionSquasher( transactions[ 0 ] );
	for ( let i = 1, iLen = transactions.length; i < iLen; i++ ) {
		squasher.squashIn( transactions[ i ] );
	}
	return squasher.getTransaction();
};
 
/* Methods */
 
/**
 * Get the Transaction as-is
 *
 * @return {ve.dm.Transaction} The transaction
 */
ve.dm.TransactionSquasher.prototype.getTransaction = function () {
	return this.transaction;
};
 
/**
 * Modify our Transaction in-place to incorporate a follow-up transaction
 *
 * Applying the modified transaction has the same effect as applying the original
 * transaction then the follow-up, but it may cause rebase conflicts where the original
 * pair of transactions would not have.
 *
 * @param {ve.dm.Transaction} tx Follow-up transaction (that can apply immediately after this)
 */
ve.dm.TransactionSquasher.prototype.squashIn = function ( tx ) {
	// Walk over the document offsets in our transaction, modifying operations in-place
	// to incorporate the operations in tx
	this.index = 0;
	this.offset = 0;
	this.globalOffset = 0;
	this.op = this.operations[ this.index ];
	this.changes = [];
	this.oldChanges = [];
	this.readAttributes();
	// Do not cache length, as we may splice the list
	for ( let i = 0; i < tx.operations.length; i++ ) {
		const op = tx.operations[ i ];
		if ( op.type === 'retain' ) {
			let retainLength = op.length;
			while ( retainLength > 0 ) {
				const consumed = this.processRetain( retainLength );
				retainLength -= consumed;
			}
		} else if ( op.type === 'replace' ) {
			let items = JSON.parse( JSON.stringify( op.remove ) );
			while ( items.length > 0 ) {
				const consumed = this.processRemove( items );
				items.splice( 0, consumed );
			}
			items = JSON.parse( JSON.stringify( op.insert ) );
			while ( items.length > 0 ) {
				const consumed = this.processInsert( items );
				items.splice( 0, consumed );
			}
		} else if ( op.type === 'attribute' ) {
			this.processAttribute( op.key, op.from, op.to );
		} else E{
			throw new Error( 'Unknown operation type ' + op.type );
		}
	}
};
 
/**
 * Process the retention of content, stopping part-way if convenient
 *
 * @private
 * @param {number} maxLength The maximum amount of content to retain
 * @return {number} The amount of content retained
 */
ve.dm.TransactionSquasher.prototype.processRetain = function ( maxLength ) {
	this.normalizePosition();
	Iif ( !this.op ) {
		throw new Error( 'Past end of transaction' );
	}
 
	if ( this.op.type === 'retain' ) {
		const len = Math.min( maxLength, this.op.length - this.offset );
		this.offset += len;
		this.globalOffset += len;
		this.attributeOperations = {};
		return len;
	}
	if ( this.op.type === 'replace' ) {
		// Apply annotation changes to inserted content
		const len = Math.min( maxLength, this.op.insert.length - this.offset );
 
		// There is never any need to adjust spliceAt, because the splices are always
		// applied in the same order in which they were generated
 
		this.offset += len;
		this.globalOffset += len;
		this.readAttributes();
		return len;
	}
	Eif ( this.op.type === 'attribute' ) {
		// Do nothing
		this.index++;
		this.op = this.operations[ this.index ];
		// By assumption, this.offset is already 0
		this.attributeOperations[ this.op.key ] = this.op;
		return 0;
	}
	throw new Error( 'Unknown op type: ' + this.op.type );
};
 
/**
 * Process the removal of some items, stopping part-way if convenient
 *
 * If some of the removal is undoing an insertion in this.transaction, then the "cancelled"
 * content is stripped out entirely from the squashed transaction.
 *
 * @private
 * @param {Object[]} items Items to remove some of; can be modified in place (annotated)
 * @return {number} The length of the initial slice of items that was removed
 */
ve.dm.TransactionSquasher.prototype.processRemove = function ( items ) {
	let tryUnsplit = false;
 
	this.normalizePosition();
	Iif ( !this.op ) {
		throw new Error( 'Past end of transaction' );
	}
	if ( this.op.type === 'retain' ) {
		this.splitIfInterior();
		// Now we must be at the start of a retain
		const len = Math.min( items.length, this.op.length );
		this.op.length -= len;
		if ( this.op.length === 0 ) {
			tryUnsplit = true;
			// Remove empty retain
			this.operations.splice( this.index, 1 );
			// this.op may become undefined; ok
			this.op = this.operations[ this.index ];
		}
		const removal = items.slice( 0, len );
		if ( this.offset === 0 && this.op && this.op.type === 'replace' ) {
			// If we're at the start of a replace op, prepend to it
			ve.batchSplice(
				this.op.remove,
				0,
				0,
				removal
			);
		} else {
			// Get the immediately preceding replace op, or insert an empty one
			let replaceOp = this.operations[ this.index - 1 ];
			if ( !replaceOp || replaceOp.type !== 'replace' ) {
				replaceOp = { type: 'replace', remove: [], insert: [] };
				this.operations.splice( this.index, 0, replaceOp );
				this.index++;
			}
			ve.batchSplice(
				replaceOp.remove,
				replaceOp.remove.length,
				0,
				removal
			);
		}
		if ( tryUnsplit ) {
			this.tryUnsplit();
		}
		this.readAttributes();
		return len;
	}
	if ( this.op.type === 'replace' ) {
		// Check removal against insertion, then cancel them out
		const len = Math.min( items.length, this.op.insert.length - this.offset );
		// len must be greater than zero, since we're not at the end of this op
		const removal = items.slice( 0, len );
		for ( let i = 0; i < len; i++ ) {
			Iif ( !this.constructor.static.equalItems(
				removal[ i ],
				this.op.insert[ this.offset + i ]
			) ) {
				throw new Error( 'Remove does not match insert' );
			}
		}
		this.op.insert.splice( this.offset, len );
		if ( this.op.remove.length === 0 && this.op.insert.length === 0 ) {
			// Empty replacement: delete it
			this.operations.splice( this.index, 1 );
			this.op = this.operations[ this.index ];
			// By assumption, this.offset is already 0
			this.tryUnsplit();
		}
		this.readAttributes();
		return len;
	}
	Eif ( this.op.type === 'attribute' ) {
		// Apply the reversed attribute change to the item being removed
		this.changeElement( items[ 0 ], this.op.key, this.op.to, this.op.from );
		this.operations.splice( this.index, 1 );
		this.op = this.operations[ this.index ];
		// By assumption, this.offset is already 0
		this.tryUnsplit();
		return 0;
	}
	throw new Error( 'Unknown operation type ' + this.op.type );
};
 
/**
 * Process the insertion of some items, stopping part-way if convenient
 *
 * If some of the insertion is undoing a removal in this.transaction, then the "cancelled"
 * content effectively becomes part of an identity replacement: replace 'foo' with 'foo'.
 * (The content cannot be stripped out entirely from the squashed transaction, because then
 * the squashed transaction, considered as a partial function between documents, would have
 * a larger preimage than the composition of the original transactions. This can probably
 * break things like associativity).
 *
 * @private
 * @param {Object[]} items Items to insert some of
 * @return {number} The length of the initial slice of items that was inserted
 */
ve.dm.TransactionSquasher.prototype.processInsert = function ( items ) {
	this.normalizePosition();
	if ( !this.op || this.op.type === 'retain' || this.op.type === 'attribute' ) {
		if ( this.op && this.op.type === 'retain' ) {
			// in a retain
			this.splitIfInterior();
		}
		// We must be at the start of this.op (or at the end if !this.op)
		// Get the immediately preceding replace op, or insert an empty one
		let replaceOp = this.operations[ this.index - 1 ];
		if ( !replaceOp || replaceOp.type !== 'replace' ) {
			replaceOp = { type: 'replace', remove: [], insert: [] };
			this.operations.splice( this.index, 0, replaceOp );
			this.index++;
			// By hypothesis, this.offset is already zero
		}
		ve.batchSplice(
			replaceOp.insert,
			replaceOp.insert.length,
			0,
			items
		);
		this.globalOffset += items.length;
		this.attributeOperations = {};
		return items.length;
	}
	Eif ( this.op.type === 'replace' ) {
		// Do *not* try to cancel insertions against a matching prior removal,
		// because it would cause the squashed transaction to "forget" prior
		// linmod content that the original transaction pair requires. This
		// breaks useful properties like associativity.
		ve.batchSplice( this.op.insert, this.offset, 0, items );
		this.offset += items.length;
		this.globalOffset += items.length;
		this.attributeOperations = {};
		return items.length;
	}
	throw new Error( 'Unknown operation type ' + this.op.type );
};
 
/**
 * Process the setting of an attribute
 *
 * The case from === to is possible. An identity attribute change still proves there is
 * an open element at this position, so cannot be stripped
 *
 * @private
 * @param {string} key The attribute key
 * @param {any} from The old value
 * @param {any} to The new value
 */
ve.dm.TransactionSquasher.prototype.processAttribute = function ( key, from, to ) {
	this.normalizePosition();
	if ( this.op && this.op.type === 'replace' && this.offset < this.op.insert.length ) {
		// If we're at some insert content, then the attribute should apply to it
		const item = this.op.insert[ this.offset ];
		Iif ( !item || !item.type || item.type[ 0 ] === '/' ) {
			throw new Error( 'Expected open element' );
		}
		this.changeElement( this.op.insert[ this.offset ], key, from, to );
	} else {
		let op = this.attributeOperations[ key ];
		if ( op ) {
			Iif ( !this.constructor.static.equalItems( op.to, from ) ) {
				throw new Error( 'Unexpected prior attribute value' );
			}
			// Modify in place
			op.to = to;
		} else {
			op = {
				type: 'attribute',
				key: key,
				from: from,
				to: to
			};
			this.splitIfInterior();
			this.operations.splice( this.index, 0, op );
			this.attributeOperations[ key ] = op;
			this.index++;
		}
	}
};
 
/**
 * Change an attribute in an open element
 *
 * @private
 * @param {Object} openElement The open element
 * @param {string} key The attribute name
 * @param {any} from Old value, or undefined if the attribute is being created
 * @param {any} to New value, or undefined if the attribute is being removed
 */
ve.dm.TransactionSquasher.prototype.changeElement = function ( openElement, key, from, to ) {
	if ( !openElement.attributes ) {
		openElement.attributes = {};
	}
	Iif ( !this.constructor.static.equalItems(
		openElement.attributes[ key ],
		from
	) ) {
		throw new Error( 'Unexpected prior attribute value' );
	}
	if ( to === undefined ) {
		delete openElement.attributes[ key ];
		Eif ( !Object.keys( openElement.attributes ).length ) {
			delete openElement.attributes;
		}
	} else {
		openElement.attributes[ key ] = to;
	}
};
 
/**
 * Normalize .index, .offset and .op so we're not at the end of a replace/retain
 *
 * @private
 */
ve.dm.TransactionSquasher.prototype.normalizePosition = function () {
	while ( this.op && (
		( this.op.type === 'retain' && this.offset === this.op.length ) ||
		( this.op.type === 'replace' && this.offset === this.op.insert.length )
	) ) {
		this.index++;
		this.offset = 0;
		// op may become undefined; ok
		this.op = this.operations[ this.index ];
		this.readAttributes();
	}
};
 
/**
 * Read the open element at the current offset (if any)
 *
 * Sets this.openElement to the open element (or null)
 * Sets this.attribute to an object containing attribute key-values (or {})
 *
 * @private
 */
ve.dm.TransactionSquasher.prototype.readAttributes = function () {
	let index = this.index,
		op = this.operations[ index ],
		offset = this.offset;
 
	this.attributeOperations = {};
	while ( true ) {
		if ( !op ) {
			return;
		}
		if ( op.type === 'replace' ) {
			if ( offset < op.insert.length ) {
				// At an openElement, so there should be no attributeOperations
				return;
			}
		} else if ( op.type === 'attribute' ) {
			this.attributeOperations[ op.key ] = op;
		} else Eif ( op.type === 'retain' && offset < op.length ) {
			return;
		}
		// Else at the start of an insert / retain: step backwards
		index++;
		offset = 0;
		op = this.operations[ index ];
	}
};
 
/**
 * If in the interior of a retain operation, split it here without moving.
 *
 * For retain, the length is split at the current offset (throws an error if at the end)
 * For all other operations, throws an error if not at the start
 *
 * Afterwards, this.offset is guaranteed to be 0.
 *
 * @private
 */
ve.dm.TransactionSquasher.prototype.splitIfInterior = function () {
	const type = this.op && this.op.type;
	if ( this.offset === 0 ) {
		// No need to split
		return;
	}
	Iif ( type !== 'retain' ) {
		throw new Error( 'Non-zero offset, but op type is ' + type );
	}
	const len = this.op.length;
	const remainder = len - this.offset;
	Iif ( remainder < 0 ) {
		throw new Error( 'Beyond the end of retain' );
	}
	Iif ( remainder === 0 ) {
		throw new Error( 'Cannot split at the end of retain' );
	}
	this.op.length = this.offset;
	this.index++;
	this.offset = 0;
	this.op = { type: 'retain', length: remainder };
	this.operations.splice( this.index, 0, this.op );
};
 
/**
 * If this operation and the previous one are retains, join them
 *
 * @private
 */
ve.dm.TransactionSquasher.prototype.tryUnsplit = function () {
	const prevOp = this.operations[ this.index - 1 ];
	if ( !this.op || !prevOp ) {
		return;
	}
	if ( prevOp.type === 'retain' && this.op.type === 'retain' ) {
		this.offset += prevOp.length;
		prevOp.length += this.op.length;
		this.operations.splice( this.index, 1 );
		this.index--;
		this.op = prevOp;
	} else if ( prevOp.type === 'replace' && this.op.type === 'replace' ) {
		this.offset += prevOp.insert.length;
		ve.batchSplice(
			prevOp.remove,
			prevOp.remove.length,
			0,
			this.op.remove
		);
		ve.batchSplice(
			prevOp.insert,
			prevOp.insert.length,
			0,
			this.op.insert
		);
		this.operations.splice( this.index, 1 );
		this.index--;
		this.op = prevOp;
	}
	// Else do nothing
};