Skip to content

Commit a6bfd3e

Browse files
alecgeatchesalecgeatchesmaxschmeling
authored
RTC: Improve array attribute stability when structural changes occur (#77164)
* Use left/right sweep in mergeYArray() to avoid recreating whole data structure when size changes * Add tests for new Y.Array merging behavior * Batch inserts if there are multiple * Add more tests for insertion, deletion, and replacement at different points in an attribute array * Avoid unnecessary intermediate arrays Co-authored-by: alecgeatches <alecgeatches@git.wordpress.org> Co-authored-by: maxschmeling <maxschmeling@git.wordpress.org>
1 parent 4733e5c commit a6bfd3e

2 files changed

Lines changed: 647 additions & 36 deletions

File tree

packages/core-data/src/utils/crdt-blocks.ts

Lines changed: 103 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -458,6 +458,7 @@ export function mergeCrdtBlocks(
458458
for ( let i = 0; i < numOfUpdatesNeeded; i++, left++ ) {
459459
const block = blocksToSync[ left ];
460460
const yblock = yblocks.get( left );
461+
461462
Object.entries( block ).forEach( ( [ key, value ] ) => {
462463
switch ( key ) {
463464
case 'attributes': {
@@ -581,13 +582,33 @@ export function mergeCrdtBlocks(
581582
}
582583
}
583584

585+
/**
586+
* Compare a plain array element against a Y.Map element for equality.
587+
* Used by the left-right sweep diff in mergeYArray.
588+
*
589+
* @param newElement The plain object from the incoming array.
590+
* @param yElement The Y.Map element from the existing Y.Array.
591+
* @return True if the elements are deeply equal.
592+
*/
593+
function areArrayElementsEqual(
594+
newElement: unknown,
595+
yElement: unknown
596+
): boolean {
597+
if ( yElement instanceof Y.Map && isRecord( newElement ) ) {
598+
return fastDeepEqual( newElement, yElement.toJSON() );
599+
}
600+
601+
return fastDeepEqual( newElement, yElement );
602+
}
603+
584604
/**
585605
* Merge an incoming plain array into an existing Y.Array in-place.
586606
*
587-
* When the array length is unchanged (stable structure), each element is
588-
* merged individually via `mergeYMapValues`, preserving concurrent edits to
589-
* different elements. When the length changes (structural edit such as row
590-
* insertion/deletion), the Y.Array is rebuilt from scratch.
607+
* Uses the same left-right sweep diff approach as mergeCrdtBlocks:
608+
* equal elements are skipped from both ends, then the middle section
609+
* is updated, deleted, or inserted as needed. This preserves existing
610+
* Y.Map/Y.Text objects for unchanged elements, so concurrent edits
611+
* to those elements are not lost.
591612
*
592613
* @param yArray The existing Y.Array to update.
593614
* @param newValue The new plain array to merge into the Y.Array.
@@ -605,40 +626,87 @@ function mergeYArray(
605626
}
606627

607628
const query = schema.query;
629+
const numOfCommonEntries = Math.min( newValue.length, yArray.length );
608630

609-
if ( yArray.length === newValue.length ) {
610-
// Same length: update each element in-place.
611-
for ( let i = 0; i < newValue.length; i++ ) {
612-
const currentElement = yArray.get( i );
613-
const newElement = newValue[ i ];
614-
615-
if ( currentElement instanceof Y.Map && isRecord( newElement ) ) {
616-
mergeYMapValues(
617-
currentElement,
618-
newElement,
619-
query,
620-
cursorPosition
621-
);
622-
} else {
623-
// Element is the wrong type (e.g. partial migration) or the
624-
// incoming value is not an object. Rebuild the entire array.
625-
yArray.delete( 0, yArray.length );
626-
yArray.insert(
627-
0,
628-
newValue.map( ( item ) =>
629-
createYMapFromQuery( query, item )
630-
)
631-
);
632-
return;
633-
}
631+
let left = 0;
632+
let right = 0;
633+
634+
// Skip equal elements from left.
635+
for (
636+
;
637+
left < numOfCommonEntries &&
638+
areArrayElementsEqual( newValue[ left ], yArray.get( left ) );
639+
left++
640+
) {
641+
/* nop */
642+
}
643+
644+
// Skip equal elements from right.
645+
for (
646+
;
647+
right < numOfCommonEntries - left &&
648+
areArrayElementsEqual(
649+
newValue[ newValue.length - right - 1 ],
650+
yArray.get( yArray.length - right - 1 )
651+
);
652+
right++
653+
) {
654+
/* nop */
655+
}
656+
657+
// Updates: merge changed elements in-place.
658+
const numOfUpdatesNeeded = numOfCommonEntries - left - right;
659+
660+
for ( let i = 0; i < numOfUpdatesNeeded; i++ ) {
661+
const currentElement = yArray.get( left + i );
662+
const newElement = newValue[ left + i ];
663+
664+
if ( currentElement instanceof Y.Map && isRecord( newElement ) ) {
665+
mergeYMapValues(
666+
currentElement,
667+
newElement,
668+
query,
669+
cursorPosition
670+
);
671+
} else {
672+
// Element is the wrong type (e.g. partial migration) or the
673+
// incoming value is not an object. Rebuild the entire array.
674+
yArray.delete( 0, yArray.length );
675+
yArray.insert(
676+
0,
677+
newValue.map( ( item ) => createYMapFromQuery( query, item ) )
678+
);
679+
return;
634680
}
635-
} else {
636-
// Structure changed: rebuild the Y.Array.
637-
yArray.delete( 0, yArray.length );
638-
yArray.insert(
639-
0,
640-
newValue.map( ( item ) => createYMapFromQuery( query, item ) )
681+
}
682+
683+
// Deletes.
684+
const numOfDeletionsNeeded = Math.max( 0, yArray.length - newValue.length );
685+
686+
if ( numOfDeletionsNeeded > 0 ) {
687+
yArray.delete( left + numOfUpdatesNeeded, numOfDeletionsNeeded );
688+
}
689+
690+
// Inserts.
691+
const numOfInsertionsNeeded = Math.max(
692+
0,
693+
newValue.length - yArray.length
694+
);
695+
696+
if ( numOfInsertionsNeeded > 0 ) {
697+
const insertAt = left + numOfUpdatesNeeded;
698+
const itemsToInsert: Y.Map< unknown >[] = new Array(
699+
numOfInsertionsNeeded
641700
);
701+
702+
for ( let i = 0; i < numOfInsertionsNeeded; i++ ) {
703+
itemsToInsert[ i ] = createYMapFromQuery(
704+
query,
705+
newValue[ insertAt + i ]
706+
);
707+
}
708+
709+
yArray.insert( insertAt, itemsToInsert );
642710
}
643711
}
644712

0 commit comments

Comments
 (0)