Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded

[Junio C Hamano <gitster@pobox.com>]

Karthik Nayak <karthik.188@gmail.com> writes:

> If you notice here, the objects
> `8baef1b4abc478178b004d62031cf7fe6db6f903`,
> `086885f71429e3599c8c903b0e9ed491f6522879` and
> `7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are included in the output,
> these objects are reachable from
> `91fa9611a355db77a07f963c746d57f75af380da` and shouldn't have been
> included since we used the `--not` flag.

For performance reasons, we cannot afford to enumerate all objects
that are reachable from --not objects and exclude them from the
output.  So it is a balancing act to decide where to draw the line.

Spending more cycles and heaps for traversing the --not side deeper
may make the --objects output smaller and more precise, but there of
course is cost associated with it.  And --objects do not promise
that it gives absolute minimum---the reason it exists is to make
sure the objects listed are sufficient to fill gaps between the
--not tips and positive ones, which is the primary reason for its
existence.

> The diff below fixes the issue:
>
> @@ -3790,11 +3833,12 @@ int prepare_revision_walk(struct rev_info *revs)
>          commit_list_sort_by_date(&revs->commits);
>      if (revs->no_walk)
>          return 0;
> -    if (revs->limited) {
> +    if (revs->limited && !revs->tree_objects) {
>          if (limit_list(revs) < 0)
>              return -1;
>          if (revs->topo_order)

This might change the size of the output and "fix" the output in
your particular small test case, but I am not sure what kind of bugs
this will introduce in the more general codepath.

Not calling limit_list() when the .limited bit is on is breaking one
of the most fundamental assumptions in the revision traversal.  When
a feature is enabled that needs to paint the graph upfront before it
can compute its result, the code that enables the feature flips the
.limited to ask this part of the code to make sure it calls
limit_list() to paint the graph with UNINTERESTING bit.

This area to paint uninteresting trees have changed quite
drastically at d5d2e935 (revision: implement sparse algorithm,
2019-01-16).  Some of what it removed may be contributing the "over
counting" of trees that are relevant in your example.