RUMM-2510 Fix the mutation resolver alg based on the Heckels definition by mariusc83 · Pull Request #1065 · DataDog/dd-sdk-android

mariusc83 · 2022-09-29T14:42:06Z

What does this PR do?

The algorithm itself is based on Paul Heckel's paper: "A technique for isolating differences between files" (1978). It is fast and performant (O(n) in time and memory) way of computing changes in text files. It's quite popular and there are many implementations out there (e.g. DifferenceKit, or hdiff in Rust). I managed to simplify it a bit for our problem - unlike lines in text files, IDs in our wireframes are guaranteed to be unique.

Motivation

What inspired you to submit this pull request?

Additional Notes

Anything else we should know when reviewing?

Review checklist (to be filled by reviewers)

Feature or bugfix MUST have appropriate tests (unit, integration, e2e)
Make sure you discussed the feature or bugfix with the maintaining team in an Issue
Make sure each commit and the PR mention the Issue number (cf the CONTRIBUTING doc)

codecov-commenter · 2022-09-30T09:08:18Z

Codecov Report

❌ Patch coverage is 78.88889% with 19 lines in your changes missing coverage. Please review.
✅ Project coverage is 82.22%. Comparing base (05b33e3) to head (320509f).

⚠️ Current head 320509f differs from pull request most recent head e625eac

Please upload reports for the commit e625eac to get more accurate results.

Files with missing lines	Patch %	Lines
...ndroid/sessionreplay/processor/MutationResolver.kt	78.89%	7 Missing and 12 partials ⚠️

Additional details and impacted files

@@                      Coverage Diff                      @@
##           feature/session-replay-vo    #1065      +/-   ##
=============================================================
- Coverage                      82.40%   82.22%   -0.18%     
=============================================================
  Files                            346      346              
  Lines                          11040    11109      +69     
  Branches                        1814     1839      +25     
=============================================================
+ Hits                            9097     9134      +37     
- Misses                          1383     1397      +14     
- Partials                         560      578      +18

Files with missing lines	Coverage Δ
...ndroid/sessionreplay/processor/MutationResolver.kt	`86.23% <78.89%> (-13.77%)`	⬇️

... and 10 files with indirect coverage changes

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

0xnm

Nice! I've added few questions regarding the algorithm.

0xnm · 2022-10-03T12:19:29Z

      - "kotlin.collections.MutableList.add(java.net.InetAddress)"
      - "kotlin.collections.MutableList.addAll(kotlin.collections.Collection)"
      - "kotlin.collections.MutableList.clear()"
+      - "kotlin.collections.MutableMap.containsKey(kotlin.Long)"


should be below, in the MutableMap zone.

0xnm · 2022-10-03T12:23:14Z

+    /** Computes a diff between two arrays.
+     * This implementation is based on Paul Heckel's algorithm for finding differences


Suggested change

/** Computes a diff between two arrays.

* This implementation is based on Paul Heckel's algorithm for finding differences

/**

* Computes a diff between two arrays.

* This implementation is based on Paul Heckel's algorithm for finding differences

0xnm · 2022-10-03T12:24:06Z

+     * within each of two arrays. It means that all elements in
+     * `oldArray` are guaranteed to have different `id` (same for `newArray`). Elements with
+     * the same `id` can appear in both arrays, which
+     * indicates one of two things determined by `newElement.isDifferent(than: oldElement)`:


seems like a Swift syntax :) Also happens in some other comments of this file.

0xnm · 2022-10-03T12:24:29Z

+    ):
+        MobileSegment.MobileIncrementalData.MobileMutationData? {


Suggested change

):

MobileSegment.MobileIncrementalData.MobileMutationData? {

): MobileSegment.MobileIncrementalData.MobileMutationData? {

0xnm · 2022-10-03T12:38:26Z

+        // to it in both files are identical,
+        // > then these lines must be the same line.
+        // This information can be used to find blocks of unchanged lines.
+        if (na.size > 1) {


is this line needed? if na.size <= 1, the for loop will be no-op anyway.

followed exactly the algorithm from iOS but I will try to see what will happen in case I remove that condition and have a for(i in 1 until 0) loop.

0xnm · 2022-10-03T13:00:04Z

-                resolveUpdateMutation(prevMatchedWireframe, currentWireframe)?.let {
-                    updates.add(it)
+        val removes: MutableList<MobileSegment.Remove> = LinkedList()
+        var removalOffsets = Array(oldSnapshot.size) { 0 }


Suggested change

var removalOffsets = Array(oldSnapshot.size) { 0 }

var removalOffsets = IntArray(oldSnapshot.size)

0xnm · 2022-10-03T13:02:04Z

        }
-        val removes = prevSnapshotAsMap.map { MobileSegment.Remove(it.key) }
+
+        runningOffset = 0


seems it is not used after, so this line can be removed?

0xnm · 2022-10-03T13:03:13Z

+                    val oldElement = oldSnapshot[indexInOld]
+                    if ((indexInOld - removalOffset + runningOffset) != index) {
+                        // Old element was moved to another position:
+                        val previousID = if (index > 0) newSnapshot[index - 1].id() else null


Suggested change

val previousID = if (index > 0) newSnapshot[index - 1].id() else null

val previousId = if (index > 0) newSnapshot[index - 1].id() else null

0xnm · 2022-10-03T13:04:31Z

+                }
+                is Entry.Reference -> {
+                    // New element was added:
+                    val previousID = if (index > 0) newSnapshot[index - 1].id() else null


Suggested change

val previousID = if (index > 0) newSnapshot[index - 1].id() else null

val previousId = if (index > 0) newSnapshot[index - 1].id() else null

0xnm · 2022-10-03T13:05:29Z

+                    val oldElement = oldSnapshot[indexInOld]
+                    if ((indexInOld - removalOffset + runningOffset) != index) {
+                        // Old element was moved to another position:
+                        val previousID = if (index > 0) newSnapshot[index - 1].id() else null


why do we compare index with 0 and take index-1 later?

Hmmm...because if you do not do that check you will have an IOB exception.

Sorry, I meant what happens with index=0 (we shouldn't use it?) and why we substract 1 to get an element from newSnapshot.

we use it, basically we try to get the previousId here which in case index=0 it will be null (see the else branch)

0xnm

I added few suggestions, but they are non-blocking for me. LGTM!

0xnm · 2022-10-05T08:30:21Z

+
+        // 5th pass
+        // Similar to 4th pass, except it processes entries in descending order.
+        if (na.size > 1) {


I guess we can align with the change in 4th pass and remove this line.

0xnm · 2022-10-05T08:31:14Z

-                resolveUpdateMutation(prevMatchedWireframe, currentWireframe)?.let {
-                    updates.add(it)
+        val removes: MutableList<MobileSegment.Remove> = LinkedList()
+        val removalOffsets = Array(oldSnapshot.size) { 0 }


Suggested change

val removalOffsets = Array(oldSnapshot.size) { 0 }

val removalOffsets = IntArray(oldSnapshot.size)

0xnm · 2022-10-05T08:32:11Z

-            if (prevMatchedWireframe != null) {
-                resolveUpdateMutation(prevMatchedWireframe, currentWireframe)?.let {
-                    updates.add(it)
+        val removes: MutableList<MobileSegment.Remove> = LinkedList()


Suggested change

val removes: MutableList<MobileSegment.Remove> = LinkedList()

val removes = LinkedList<MobileSegment.Remove>()

mariusc83 self-assigned this Sep 29, 2022

mariusc83 force-pushed the mconstantin/rumm-2510/resolve-mutations-when-elements-order-changed branch from 839f77e to ee7df40 Compare September 30, 2022 08:46

xgouchet added the size-medium This PR is medium sized label Sep 30, 2022

mariusc83 force-pushed the mconstantin/rumm-2510/resolve-mutations-when-elements-order-changed branch from ee7df40 to 8a85559 Compare October 3, 2022 11:58

mariusc83 marked this pull request as ready for review October 3, 2022 11:59

mariusc83 requested a review from a team as a code owner October 3, 2022 11:59

0xnm reviewed Oct 3, 2022

View reviewed changes

mariusc83 force-pushed the mconstantin/rumm-2510/resolve-mutations-when-elements-order-changed branch from 8a85559 to 320509f Compare October 3, 2022 15:40

xgouchet approved these changes Oct 4, 2022

View reviewed changes

mariusc83 requested a review from 0xnm October 5, 2022 08:16

0xnm approved these changes Oct 5, 2022

View reviewed changes

mariusc83 force-pushed the mconstantin/rumm-2510/resolve-mutations-when-elements-order-changed branch from 320509f to 68a4e49 Compare October 5, 2022 12:16

RUMM-2510 Fix the mutation resolver alg based on the Heckels definition

e625eac

mariusc83 force-pushed the mconstantin/rumm-2510/resolve-mutations-when-elements-order-changed branch from 68a4e49 to e625eac Compare October 5, 2022 12:46

mariusc83 merged commit 0bf8401 into feature/session-replay-vo Oct 5, 2022

mariusc83 deleted the mconstantin/rumm-2510/resolve-mutations-when-elements-order-changed branch October 5, 2022 13:06

xgouchet added this to the internal milestone Dec 13, 2023

		/** Computes a diff between two arrays.
		* This implementation is based on Paul Heckel's algorithm for finding differences

	):
	MobileSegment.MobileIncrementalData.MobileMutationData? {
	): MobileSegment.MobileIncrementalData.MobileMutationData? {

	var removalOffsets = Array(oldSnapshot.size) { 0 }
	var removalOffsets = IntArray(oldSnapshot.size)

	val previousID = if (index > 0) newSnapshot[index - 1].id() else null
	val previousId = if (index > 0) newSnapshot[index - 1].id() else null

	val removalOffsets = Array(oldSnapshot.size) { 0 }
	val removalOffsets = IntArray(oldSnapshot.size)

	val removes: MutableList<MobileSegment.Remove> = LinkedList()
	val removes = LinkedList<MobileSegment.Remove>()

Uh oh!

Conversation

mariusc83 commented Sep 29, 2022

What does this PR do?

Motivation

Additional Notes

Review checklist (to be filled by reviewers)

Uh oh!

codecov-commenter commented Sep 30, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

0xnm left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

0xnm left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

codecov-commenter commented Sep 30, 2022 •

edited

Loading