reconciliation.ts 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
  1. import { PRECEDING_ELEMENT_KEY } from "../../packages/excalidraw/constants";
  2. import { ExcalidrawElement } from "../../packages/excalidraw/element/types";
  3. import { AppState } from "../../packages/excalidraw/types";
  4. import { arrayToMapWithIndex } from "../../packages/excalidraw/utils";
  5. export type ReconciledElements = readonly ExcalidrawElement[] & {
  6. _brand: "reconciledElements";
  7. };
  8. export type BroadcastedExcalidrawElement = ExcalidrawElement & {
  9. [PRECEDING_ELEMENT_KEY]?: string;
  10. };
  11. const shouldDiscardRemoteElement = (
  12. localAppState: AppState,
  13. local: ExcalidrawElement | undefined,
  14. remote: BroadcastedExcalidrawElement,
  15. ): boolean => {
  16. if (
  17. local &&
  18. // local element is being edited
  19. (local.id === localAppState.editingElement?.id ||
  20. local.id === localAppState.resizingElement?.id ||
  21. local.id === localAppState.draggingElement?.id ||
  22. // local element is newer
  23. local.version > remote.version ||
  24. // resolve conflicting edits deterministically by taking the one with
  25. // the lowest versionNonce
  26. (local.version === remote.version &&
  27. local.versionNonce < remote.versionNonce))
  28. ) {
  29. return true;
  30. }
  31. return false;
  32. };
  33. export const reconcileElements = (
  34. localElements: readonly ExcalidrawElement[],
  35. remoteElements: readonly BroadcastedExcalidrawElement[],
  36. localAppState: AppState,
  37. ): ReconciledElements => {
  38. const localElementsData =
  39. arrayToMapWithIndex<ExcalidrawElement>(localElements);
  40. const reconciledElements: ExcalidrawElement[] = localElements.slice();
  41. const duplicates = new WeakMap<ExcalidrawElement, true>();
  42. let cursor = 0;
  43. let offset = 0;
  44. let remoteElementIdx = -1;
  45. for (const remoteElement of remoteElements) {
  46. remoteElementIdx++;
  47. const local = localElementsData.get(remoteElement.id);
  48. if (shouldDiscardRemoteElement(localAppState, local?.[0], remoteElement)) {
  49. if (remoteElement[PRECEDING_ELEMENT_KEY]) {
  50. delete remoteElement[PRECEDING_ELEMENT_KEY];
  51. }
  52. continue;
  53. }
  54. // Mark duplicate for removal as it'll be replaced with the remote element
  55. if (local) {
  56. // Unless the remote and local elements are the same element in which case
  57. // we need to keep it as we'd otherwise discard it from the resulting
  58. // array.
  59. if (local[0] === remoteElement) {
  60. continue;
  61. }
  62. duplicates.set(local[0], true);
  63. }
  64. // parent may not be defined in case the remote client is running an older
  65. // excalidraw version
  66. const parent =
  67. remoteElement[PRECEDING_ELEMENT_KEY] ||
  68. remoteElements[remoteElementIdx - 1]?.id ||
  69. null;
  70. if (parent != null) {
  71. delete remoteElement[PRECEDING_ELEMENT_KEY];
  72. // ^ indicates the element is the first in elements array
  73. if (parent === "^") {
  74. offset++;
  75. if (cursor === 0) {
  76. reconciledElements.unshift(remoteElement);
  77. localElementsData.set(remoteElement.id, [
  78. remoteElement,
  79. cursor - offset,
  80. ]);
  81. } else {
  82. reconciledElements.splice(cursor + 1, 0, remoteElement);
  83. localElementsData.set(remoteElement.id, [
  84. remoteElement,
  85. cursor + 1 - offset,
  86. ]);
  87. cursor++;
  88. }
  89. } else {
  90. let idx = localElementsData.has(parent)
  91. ? localElementsData.get(parent)![1]
  92. : null;
  93. if (idx != null) {
  94. idx += offset;
  95. }
  96. if (idx != null && idx >= cursor) {
  97. reconciledElements.splice(idx + 1, 0, remoteElement);
  98. offset++;
  99. localElementsData.set(remoteElement.id, [
  100. remoteElement,
  101. idx + 1 - offset,
  102. ]);
  103. cursor = idx + 1;
  104. } else if (idx != null) {
  105. reconciledElements.splice(cursor + 1, 0, remoteElement);
  106. offset++;
  107. localElementsData.set(remoteElement.id, [
  108. remoteElement,
  109. cursor + 1 - offset,
  110. ]);
  111. cursor++;
  112. } else {
  113. reconciledElements.push(remoteElement);
  114. localElementsData.set(remoteElement.id, [
  115. remoteElement,
  116. reconciledElements.length - 1 - offset,
  117. ]);
  118. }
  119. }
  120. // no parent z-index information, local element exists → replace in place
  121. } else if (local) {
  122. reconciledElements[local[1]] = remoteElement;
  123. localElementsData.set(remoteElement.id, [remoteElement, local[1]]);
  124. // otherwise push to the end
  125. } else {
  126. reconciledElements.push(remoteElement);
  127. localElementsData.set(remoteElement.id, [
  128. remoteElement,
  129. reconciledElements.length - 1 - offset,
  130. ]);
  131. }
  132. }
  133. const ret: readonly ExcalidrawElement[] = reconciledElements.filter(
  134. (element) => !duplicates.has(element),
  135. );
  136. return ret as ReconciledElements;
  137. };