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
};
|