Merging main into another branch breaks `dolt_diff_<table>`

[timsehn]

Repro

$ dolt init --fun                         
Successfully initialized dolt data repository.
$ dolt sql -q "create table xy (x int primary key)"
$ dolt commit -Am "new table"
commit 44oi6heb4fcikr0cffg2bcvnjnn0qh7k (HEAD -> main) 
Author: timsehn <[email protected]>
Date:  Mon Oct 23 11:26:02 -0700 2023

        new table

$ dolt branch test
$ dolt branch test2
$ dolt checkout test
Switched to branch 'test'
$ dolt sql -q "insert into xy values (0)"
Query OK, 1 row affected (0.00 sec)
$ dolt commit -am "new val 1"
commit d74pcbhlogrv0uvuck6ta95co2192cdc (HEAD -> test) 
Author: timsehn <[email protected]>
Date:  Mon Oct 23 11:27:03 -0700 2023

        new val 1

$ dolt checkout main
Switched to branch 'main'
$ dolt sql -q "call dolt_merge('test', '--no-ff', '-message', 'Merge test into main')"
+----------------------------------+--------------+-----------+
| hash                             | fast_forward | conflicts |
+----------------------------------+--------------+-----------+
| h221in9dol503a3vu3thqqs9vmiae8d7 | 0            | 0         |
+----------------------------------+--------------+-----------+

$ dolt checkout test2
Switched to branch 'test2'
$ dolt sql -q "call dolt_merge('main', '--no-ff', '-message', 'Merge main into test2')"
+----------------------------------+--------------+-----------+
| hash                             | fast_forward | conflicts |
+----------------------------------+--------------+-----------+
| o3fvl7ui0ct731sihn9v5a7rnljvocbs | 0            | 0         |
+----------------------------------+--------------+-----------+

$ dolt checkout main                                                                   
Switched to branch 'main'
$ dolt sql -q "call dolt_merge('test2', '--no-ff', '-message', 'Merge test2 into main')"

+----------------------------------+--------------+-----------+
| hash                             | fast_forward | conflicts |
+----------------------------------+--------------+-----------+
| deu01jgeaekvov0sp5qln39f9h7ouo9c | 0            | 0         |
+----------------------------------+--------------+-----------+

$ dolt sql -q "select * from dolt_log"
+----------------------------------+-----------+-----------------+---------------------+----------------------------+
| commit_hash                      | committer | email           | date                | message                    |
+----------------------------------+-----------+-----------------+---------------------+----------------------------+
| deu01jgeaekvov0sp5qln39f9h7ouo9c | root      | root@localhost  | 2023-10-23 18:28:11 | Merge test2 into main      |
| o3fvl7ui0ct731sihn9v5a7rnljvocbs | root      | root@localhost  | 2023-10-23 18:27:41 | Merge main into test2      |
| h221in9dol503a3vu3thqqs9vmiae8d7 | root      | root@localhost  | 2023-10-23 18:27:22 | Merge test into main       |
| d74pcbhlogrv0uvuck6ta95co2192cdc | timsehn   | [email protected] | 2023-10-23 18:27:03 | new val 1                  |
| 44oi6heb4fcikr0cffg2bcvnjnn0qh7k | timsehn   | [email protected] | 2023-10-23 18:26:02 | new table                  |
| d01tqbeee75fti3vthi6k6kkoogsq294 | timsehn   | [email protected] | 2023-10-23 18:25:31 | Initіаlizе datа rеposіtory |
+----------------------------------+-----------+-----------------+---------------------+----------------------------+

$ dolt sql -q "select * from dolt_diff_xy" 
+------+----------------------------------+-------------------------+--------+----------------------------------+-------------------------+-----------+
| to_x | to_commit                        | to_commit_date          | from_x | from_commit                      | from_commit_date        | diff_type |
+------+----------------------------------+-------------------------+--------+----------------------------------+-------------------------+-----------+
| 0    | o3fvl7ui0ct731sihn9v5a7rnljvocbs | 2023-10-23 18:27:41.279 | NULL   | 44oi6heb4fcikr0cffg2bcvnjnn0qh7k | 2023-10-23 18:26:02.034 | added     |
+------+----------------------------------+-------------------------+--------+----------------------------------+-------------------------+-----------+

This is the merge commit into test2. The diff should show commit: d74pcbhlogrv0uvuck6ta95co2192cdc

[timsehn]

Note the merge of main into test2 and then merge of 'test2back intomainboth as--no-ff` merges.

[fulghum]

I think I found what's going on here... the current commit iterator does a depth first search through the commit parents, starting with the second parent (parentIndex == 1). This is the correct parent to start with, because it means we look at the commits from the branch that was merged into our branch. We queue the first parent (parentIndex == 0) to process, while we go deeper on the second parent's parents.

At this point, we do still attempt to look at the second parent first again (which again seems correct, since it contains the commits from the branch that was the source of the merge in this example), but... because that same commit is also a parent of the starting commit, we don't queue that commit to be processed (because it's already been added) and instead, the current code prioritizes traveling down the first parent before that one, which ends up finding the diff first and attributing it to the merge commit.

In my initial testing, switching this to more of a breadth first traversal seems to always prioritize the commits from the branch that was the merge source, and returns the correct hash of the "new val 1" commit in this repro.

I'm still not 100% confident in this change and need to do a little more testing and see if there's something I'm missing, but I think this seems logically correct, explains what we're seeing, and does cause the correct, most-specific commit to be identified in the diff output.

I'm going to add some tests and see if I can find any edge cases that break this. If that goes smoothly, I should have a PR opened up shortly.

[fulghum]

Quick update... I've got an approved PR with all tests passing, we're just debating a couple more test cases and if we want to make this new behavior limited to only the dolt_diff_<tablename> tables initially. Nothing major. I'm expecting to get those details wrapped up quickly and get this fix released for you tomorrow.

This turned out to be a really interesting case for how we walk the commit graph. Very, very awesome that you helped us find this! 🙏 Thank you!!

[fulghum]

This fix has been released in Dolt version 1.21.3.

@ricardoreiter – thanks again for helping us find this one! Let us know if we can help with anything else!

[fulghum]

Reopening this one after testing with production data and seeing some discrepancies. Working on digging into some more complex test cases.

Because of the discrepancies with the production data testing, I went ahead and reverted the commit and released a new Dolt version (1.21.4) that removes this change.