Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged

From: Elijah Newren <newren@gmail.com>
Date: Feb 14, 2025, 19:00 UTC
Message-ID: <CABPp-BGOeAJ-e0P7kALLMnA7wCzbJx6WEYwmCmsq9qK46DYdVw@mail.gmail.com>
In-Reply-To: <CAPhwyn1oXRy5BFQBvuFsmhfVhkW8+D6Xz6OYB8LpP0O+jH1TFQ@mail.gmail.com>

On Fri, Feb 14, 2025 at 12:24 AM Meet Soni <meetsoni3017@gmail.com> wrote:

Show 33 quoted lines

>
> On Fri, 14 Feb 2025 at 11:35, Elijah Newren <newren@gmail.com> wrote:
> >
> > > > Did you run any tests?  I'm not sure you maintained correctness here.
> > >
> > > I didn't run any tests -- I wanted to, but I wasn’t sure how to do it
> > > for this change. Since you suggested dropping this patch from the
> > > series, I’ll do that. But for similar changes in the future, how should I go
> > > about testing them?
> >
> > As per Documentation/CodingGuidelines: "After any code change, make
> > sure that the entire test suite passes."  You can do that by running:
> >     cd t && make
> > (You probably want to also run that before making any changes, just to
> > verify that they all pass for you.  Then, if any test fails after you
> > make changes, you know it's because of your changes rather than
> > because you missed something in building or setting up the tests.)
> >
> >
> > And although it doesn't matter since we're dropping this patch, the
> > issue I noticed was that if there were, say, three unmerged entries
> > with the same path, the original code would create one entry in the
> > string list and modify it 3 times (each with a different ce_stage(ce).
> > Your modification would create three different entries (each with only
> > information from one stage) and drop two of them, meaning we no longer
> > have a single string_list_item that contains information from all 3
> > unmerged entries for the same path.  I'm pretty sure running the
> > existing tests would catch that kind of bug, which is what raised the
> > question.
>
> That's the thing -- I did run make in the t/ directory, and it passed. I was
> just wondering if there's any other way to test this in isolation, in case
> I want to verify such changes more directly in the future.

Really? Did you rebuild the code, after making your changes? You may have been running with a pre-changes version of the code.

I just applied your changes and ran the tests. I see it fail as soon as it gets to t1004.

$ cd t && make test [... lots of output snipped ...] *** t1004-read-tree-m-u-wf.sh *** ok 1 - two-way setup ok 2 - two-way not clobbering ok 3 - two-way with incorrect --exclude-per-directory (1) ok 4 - two-way with incorrect --exclude-per-directory (2) ok 5 - two-way clobbering a ignored file ok 6 - three-way not complaining on an untracked path in both ok 7 - three-way not clobbering a working tree file ok 8 - three-way not complaining on an untracked file ok 9 - 3-way not overwriting local changes (setup) ok 10 - 3-way not overwriting local changes (our side) ok 11 - 3-way not overwriting local changes (their side) ok 12 - funny symlink in work tree ok 13 - funny symlink in work tree, un-unlink-able ok 14 - D/F setup ok 15 - D/F ok 16 - D/F resolve not ok 17 - D/F recursive # # # git reset --hard && # git checkout side-b && # git merge-recursive branch-point -- side-b side-a # # # failed 1 among 17 test(s) 1..17 make[1]: *** [Makefile:77: t1004-read-tree-m-u-wf.sh] Error 1 make[1]: Leaving directory '/home/newren/floss/git/t' make: *** [Makefile:63: test] Error 2

...and if go to the toplevel directory and run under prove so I can see all the failures (and run the test suites in parallel), I see:

$ cd .. && make DEFAULT_TEST_TARGET=prove GIT_PROVE_OPTS='--timer
--state failed,slow,save --jobs 12' test
[... lots of output snipped ...]
Test Summary Report
-------------------
t3424-rebase-empty.sh                            (Wstat: 256 Tests: 20
Failed: 18)
  Failed tests:  3-20
  Non-zero exit status: 1
t3436-rebase-more-options.sh                     (Wstat: 256 Tests: 19
Failed: 17)
  Failed tests:  2-18
  Non-zero exit status: 1
t4151-am-abort.sh                                (Wstat: 256 Tests: 20
Failed: 12)
  Failed tests:  5-9, 12-16, 19-20
  Non-zero exit status: 1
t3407-rebase-abort.sh                            (Wstat: 256 Tests: 17
Failed: 8)
  Failed tests:  2-9
  Non-zero exit status: 1
t3428-rebase-signoff.sh                          (Wstat: 256 Tests: 7 Failed: 5)
  Failed tests:  2, 4-7
  Non-zero exit status: 1
t6409-merge-subtree.sh                           (Wstat: 256 Tests: 12
Failed: 5)
  Failed tests:  2-6
  Non-zero exit status: 1
t7102-reset.sh                                   (Wstat: 256 Tests: 38
Failed: 7)
  Failed tests:  14-20
  Non-zero exit status: 1
t6432-merge-recursive-space-options.sh           (Wstat: 256 Tests: 11
Failed: 4)
  Failed tests:  2, 7-8, 11
  Non-zero exit status: 1
t6430-merge-recursive.sh                         (Wstat: 256 Tests: 37
Failed: 15)
  Failed tests:  10-11, 13-20, 22-24, 28-29
  Non-zero exit status: 1
t3406-rebase-message.sh                          (Wstat: 256 Tests: 32
Failed: 8)
  Failed tests:  22, 24-27, 29-31
  Non-zero exit status: 1
t4200-rerere.sh                                  (Wstat: 256 Tests: 36
Failed: 5)
  Failed tests:  24-28
  Non-zero exit status: 1
t7201-co.sh                                      (Wstat: 256 Tests: 46
Failed: 5)
  Failed tests:  5-9
  Non-zero exit status: 1
t3418-rebase-continue.sh                         (Wstat: 256 Tests: 29
Failed: 7)
  Failed tests:  4, 6, 10-12, 26-27
  Non-zero exit status: 1
t3403-rebase-skip.sh                             (Wstat: 256 Tests: 20
Failed: 3)
  Failed tests:  2, 4, 9
  Non-zero exit status: 1
t4253-am-keep-cr-dos.sh                          (Wstat: 256 Tests: 7 Failed: 2)
  Failed tests:  6-7
  Non-zero exit status: 1
t9903-bash-prompt.sh                             (Wstat: 256 Tests: 67
Failed: 39)
  Failed tests:  16-31, 33-35, 37, 40-44, 46-52, 55-58, 60
                62, 67
  Non-zero exit status: 1
t3503-cherry-pick-root.sh                        (Wstat: 256 Tests: 6 Failed: 2)
  Failed tests:  5-6
  Non-zero exit status: 1
t3401-rebase-and-am-rename.sh                    (Wstat: 256 Tests: 10
Failed: 2)
  Failed tests:  4, 10
  Non-zero exit status: 1
t2407-worktree-heads.sh                          (Wstat: 256 Tests: 12
Failed: 2)
  Failed tests:  4-5
  Non-zero exit status: 1
t5407-post-rewrite-hook.sh                       (Wstat: 256 Tests: 17
Failed: 3)
  Failed tests:  4-6
  Non-zero exit status: 1
t2500-untracked-overwriting.sh                   (Wstat: 256 Tests: 10
Failed: 2)
  Failed tests:  9-10
  Non-zero exit status: 1
t4153-am-resume-override-opts.sh                 (Wstat: 256 Tests: 6 Failed: 1)
  Failed test:  3
  Non-zero exit status: 1
t1015-read-index-unmerged.sh                     (Wstat: 256 Tests: 6 Failed: 1)
  Failed test:  6
  Non-zero exit status: 1
t3509-cherry-pick-merge-df.sh                    (Wstat: 256 Tests: 9 Failed: 1)
  Failed test:  9
  Non-zero exit status: 1
t2023-checkout-m.sh                              (Wstat: 256 Tests: 5 Failed: 1)
  Failed test:  5
  Non-zero exit status: 1
t7615-diff-algo-with-mergy-operations.sh         (Wstat: 256 Tests: 7 Failed: 1)
  Failed test:  2
  Non-zero exit status: 1
t6427-diff3-conflict-markers.sh                  (Wstat: 256 Tests: 9 Failed: 1)
  Failed test:  8
  Non-zero exit status: 1
t1004-read-tree-m-u-wf.sh                        (Wstat: 256 Tests: 17
Failed: 1)
  Failed test:  17
  Non-zero exit status: 1
t3420-rebase-autostash.sh                        (Wstat: 256 Tests: 52
Failed: 10)
  Failed tests:  11-17, 21-23
  Non-zero exit status: 1
t4150-am.sh                                      (Wstat: 256 Tests: 87
Failed: 33)
  Failed tests:  34-40, 42-46, 48, 50-54, 57-62, 64-65, 67-71
                75, 87
  Non-zero exit status: 1
t7512-status-help.sh                             (Wstat: 256 Tests: 46
Failed: 3)
  Failed tests:  5-6, 29
  Non-zero exit status: 1
t3400-rebase.sh                                  (Wstat: 256 Tests: 39
Failed: 1)
  Failed test:  30
  Non-zero exit status: 1
t3404-rebase-interactive.sh                      (Wstat: 256 Tests:
131 Failed: 1)
  Failed test:  80
  Non-zero exit status: 1
Files=1031, Tests=30662, 70 wallclock secs ( 8.33 usr  2.13 sys +
248.60 cusr 516.60 csys = 775.66 CPU)
Result: FAIL
make[1]: *** [Makefile:73: prove] Error 1
make[1]: Leaving directory '/home/newren/floss/git/t'
make: *** [Makefile:3237: test] Error 2

I suspect this is a case where it was testing a version of git that you built before making the changes.