[1/1] revision.c: use new topo-order logic in tests

Commit Message

Johannes Schindelin via GitGitGadget Nov. 19, 2018, 7:03 p.m. UTC

From: Derrick Stolee <[e-mail]>

The revision-walk machinery is being rewritten to use generation
numbers in the commit-graph when availble. Due to some problematic
commit histories, the new logic can be slower than the previous
method due to how commit dates and generation numbers interact.
Thus, the new logic is not used in comparison queries, such as

	git log --topo-order A..B

The logic for these queries was implemented during the refactor,
but is unreachable due to the potential performance penalty. The
code came along with a larger block of code that was copied from
the old code. When generation numbers are updated to v2 (corrected
commit dates), then we will no longer have a performance penalty
and this logic is what we will want to use.

In the meantime, use the new logic when GIT_TEST_COMMIT_GRAPH is
enabled. This will demonstrate that the new logic works for all
comparison queries in the test suite, including these variants:

	git log --topo-order --ancestry-path A..B
	git log --topo-order A...B

Signed-off-by: Derrick Stolee <[e-mail]>
---
 revision.c | 4 ++++
 1 file changed, 4 insertions(+)

Comments

Junio C Hamano Nov. 20, 2018, 6:13 a.m. UTC | #1

"Derrick Stolee via GitGitGadget" <[e-mail]> writes:

> @@ -3143,6 +3144,9 @@ int prepare_revision_walk(struct rev_info *revs)
>  		commit_list_sort_by_date(&revs->commits);
>  	if (revs->no_walk)
>  		return 0;
> +	if (revs->limited &&
> +	    git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
> +		revs->limited = 0;
>  	if (revs->limited) {
>  		if (limit_list(revs) < 0)
>  			return -1;

That is equivalent to say

	if (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
		revs->limited = 0;

Wouldn't that make the codepath that involves limit_list()
completely unreachable while testing, though?

The title only mentions "topo-order" logic, but the topo-order is
not the only reason why limited bit can be set, is it?  When showing
merges, simplifying merges, or post-processing to show ancestry
path, or showing a bottom-limited revision range, the limited bit is
automatically set because all of these depend on first calling
limit_list() and then postprocessing its result.  Doesn't it hurt
these cases to unconditionally drop limited bit?

Derrick Stolee Nov. 20, 2018, 6:45 p.m. UTC | #2

On 11/20/2018 1:13 AM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <[e-mail]> writes:
>
>> @@ -3143,6 +3144,9 @@ int prepare_revision_walk(struct rev_info *revs)
>>   		commit_list_sort_by_date(&revs->commits);
>>   	if (revs->no_walk)
>>   		return 0;
>> +	if (revs->limited &&
>> +	    git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
>> +		revs->limited = 0;
>>   	if (revs->limited) {
>>   		if (limit_list(revs) < 0)
>>   			return -1;
> That is equivalent to say
>
> 	if (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
> 		revs->limited = 0;

Not exactly equivalent, because we can use short-circuiting to avoid the 
git_env_bool check, but I see what you mean.

> Wouldn't that make the codepath that involves limit_list()
> completely unreachable while testing, though?

Testing with GIT_TEST_COMMIT_GRAPH=0 would still hit limit_list(). Both 
modes are important to test (for instance, to ensure we still have 
correct behavior without a commit-graph file).

> The title only mentions "topo-order" logic, but the topo-order is
> not the only reason why limited bit can be set, is it?  When showing
> merges, simplifying merges, or post-processing to show ancestry
> path, or showing a bottom-limited revision range, the limited bit is
> automatically set because all of these depend on first calling
> limit_list() and then postprocessing its result.  Doesn't it hurt
> these cases to unconditionally drop limited bit?

You're right that we only want to do this in the topo-order case, so 
perhaps the diff should instead be:

  	if (revs->no_walk)
  		return 0;
+	if (revs->topo_order &&
+	    git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
+		revs->limited = 0;
  	if (revs->limited) {
  		if (limit_list(revs) < 0)
  			return -1;

Thanks,
-Stolee

Patch

diff --git a/revision.c b/revision.c
index 4ef47d2fb4..d52da6e24f 100644
--- a/revision.c
+++ b/revision.c
@@ -27,6 +27,7 @@ 
 #include "commit-reach.h"
 #include "commit-graph.h"
 #include "prio-queue.h"
+#include "config.h"
 
 volatile show_early_output_fn_t show_early_output;
 
@@ -3143,6 +3144,9 @@  int prepare_revision_walk(struct rev_info *revs)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;
+	if (revs->limited &&
+	    git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))
+		revs->limited = 0;
 	if (revs->limited) {
 		if (limit_list(revs) < 0)
 			return -1;