Re: [PATCH v4 06/10] commit-graph: implement corrected commit date

Hello Abhishek,

Abhishek Kumar <abhishekkumar8222@gmail.com> writes:

Actually this description should match whatever we decide about mechanism for verifying correctness of generation numbers (see below). Because we have to choose one.

See below.

Thanks. This description really should be added to the commit message, because (yet again?) I was confused by this change.

Sidenote: it is not obvious at least to me that this function is used
only for sorting commits to speed up computation of Bloom filters while
writing the commit-graph (`git commit-graph write --changed-paths [other
options]`).

All right, so the wider type is used because of comparison with wide-uint GENERATION_NUMBER_INFINITY. I stand corrected.

[...]

That is one of the 3 possible solutions I can think of.

I. First solution is to switch from checking that generation number matches its definition to checking that the [weaker] reachability condition for the generation number is true, that is:

 	if (generation < max_generation)
 		graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime),

The [weaker] reachability condition for generation numbers states that

   A reachable from B    =>    gen(A) <= gen(B)

This condition is true even if one or more generation numbers is GENERATION_NUMBER_ZERO (uninitialized or written by old git version), GENERATION_NUMBER_V1_MAX (we hit storage limitations, can happen only for generation number v1), or GENERATION_NUMBER_INFINITY (for commits outside of the serialized commit-graph, doesn't matter and cannot happen during verification of the commit-graph data by definition).

This means that if P* is the parent of C with the maximal generation number, and gen(C) < gen(P*) is true (while gen(P*) <= gen(C) should be true), then there is a problem with generation number.

This is why I thought you were going for, and what I have proposed.

Advantages:
- we are testing what actually matters for speeding up reachability
  queries, namely that the reachability property holds true
- the test works for generation number v1, generation number v2,
  and any possible future use-compatibile generation number
  (not that I think we would need any)
- least complicated solution

Disadvantages:
- weaker test that we have had for generation number v1 (topological
  levels), and weaker that possible test for generation number v2
  that we could have (see below)

II. Verify corrected committed date (generation number v2) if available, and verify topological levels (generation number v1) otherwise, checking that it matches the definition of it -- using version-specific checks.

This would probably mean adding a conditional around the code verifying that given generation number is correct, possibly:

  if (g->read_generation_data) {
  	/* verify corrected commit date */
  } else {
  	/* current code for verifying topological levels */
  }

II.a. For topological levels (generation number v1) we would continue checking that it matches the definition, that is that the following condition holds:

  gen(C) = max_{P: P ∈ parents(C)} gen(P) + 1

This includes code for handling the case where `max_generation`, holding max_{P: P ∈ parents(C)} gen(P), is GENERATION_NUMBER_V1_MAX.

II.b. For corrected commiter dates (generation number v2) we can use the code proposed by this revision of this commit, namely we check if the following condition holds:

  gen(P) + 1 <= gen(C)   for each P \in parents(C)

or, in other words:

  max_{P: P ∈ parents(C)} { gen(P) } + 1  <=  gen(C)

Which could be checked using the following code (i.e. current state after this revision of this patch):

	if (generation < max_generation + 1)
		graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime),

This is what I think you are proposing now.

Additionally, theoretically we could also check that the following condition holds for corrected commiter date:

   committer_date(C) <= gen_v2(C)

but this is automatically fufilled because we use non-negative offsets to store corrected committed date info.

Alternatively we can check for compliance with the definition of the corrected committer date:

  if (max_generation + 1 <= graph_commit->date) {
  	/* commit date does not need correction */
  	if (generation != graph_commit->date)
    	graph_report(_("commit-graph corrected commit date for commit %s "
  		               "is %"PRItime" != %"PRItime" commit date"),
                     ...);
  } else {
  	if (generation != max_generation + 1)
  		graph_report(_("commit-graph generation v2 for commit %s is %"PRItime" != %"PRItime),
                     ...);
  }

Though I think it might be overkill.

Advantages:
- more strict tests, checking generation numbers (v2 if present, v1
  otherwise) against their definition
- if there is no GDAT chunk, verify works just like it did before

Disadvantages:
- more complicated code
- possibly measurable performance degradation due to extra conditional

III. Like II., but if there is generation numbers chunk (GDAT chunk), we verify *both* topological levels (v1) and corrected commit date (v2) against their definition. If GDAT chunk is not present, it reduces to current code (before this patch series).

Advantages:
- if there is no GDAT chunk, verify works just like it did before
- most strict tests, verifying all the data: both generation number v1
  and generation number v2 -- if possible

Disadvantages:
- most complex code; we need to somehow extract topological levels
  if the GDAT chunk is present (they are not on graph data slab in this
  case); I have not even started to think how it could be done
- slower verification

I don't whink we have any test that created commit graph with topological levels greater than GENERATION_NUMBER_V1_MAX; this would be expensive and have to be of course protected by GIT_TEST_LONG aka EXPENSIVE prerequisite.

  # GIT_TEST_COMMIT_GRAPH_NO_GDAT=1 is here to force verification of topological levels
  test_expect_success EXPENSIVE 'verify handles topological levels > GENERATION_NUMBER_V1_MAX' '
  	rm -rf long_chain &&
  	git init long_chain &&
  	test_commit_bulk -C long_chain 1073741824 &&
    (
  		cd long_chain &&
  		GIT_TEST_COMMIT_GRAPH_NO_GDAT=1 git commit-graph write &&
  		git commit-graph verify
    )
  '

This however lies slightly outside the scope of this patch series, though if you could add this test (in a separate patch), after testing it, it would be very nice.

I think putting changes to the verify function in a separate patch, be it before or after this one (depending on the choice of the algorithm for verification, see above) would be a good idea.

Best,