Re: [RFC PATCH 07/13] test-reach

[Derrick Stolee <stolee@gmail.com>]

On 6/29/2018 5:54 PM, Stefan Beller wrote:
> On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee <dstolee@microsoft.com> wrote:
>
>> +# Construct a grid-like commit graph with points (x,y)
>> +# with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has
>> +# parents (x-1, y) and (x, y-1), keeping in mind that
>> +# we drop a parent if a coordinate is nonpositive.
>> +#
>> +#             (10,10)
>> +#            /       \
>> +#         (10,9)    (9,10)
>> +#        /     \   /      \
>> +#    (10,8)    (9,9)      (8,10)
>> +#   /     \    /   \      /    \
>> +#         ( continued...)
>> +#   \     /    \   /      \    /
>> +#    (3,1)     (2,2)      (1,3)
>> +#        \     /    \     /
>> +#         (2,1)      (2,1)
>> +#              \    /
>> +#              (1,1)
>> +#
>> +# We use branch 'comit-x-y' to refer to (x,y).
>> +# This grid allows interesting reachability and
>> +# non-reachability queries: (x,y) can reach (x',y')
>> +# if and only if x' <= x and y' <= y.
> This is an interesting DAG, though not very common
> in reality (81 merges, 18 single parent commits,
> one root with a depth of at most 10).
>
> It reminds me of FELINE as that also has 2 independent numbers :)

The design of this graph is exactly so you (the test writer) can know if 
two commits can reach exactly by whether the two-dimensional keys are 
comparable. It's wide enough that we can come up with interesting test 
cases for some of these walks, especially the have/wants negotiation.

>
> I guess it is easy to make up artificial test cases for that,
> but I wonder if we want more variety for a generic reachability
> test tool (e.g. long chains of parallel histories, octopus,
> disconnected parts of the graph)
>
>> +test_expect_success 'setup' '
> [...]
>> +       git commit-graph write --reachable
> Is this only to test the full commit-graph?, maybe we'd
> want to write out the commit graph at (5,10) or so, such
> that half the walking is tested without graph.
> What about author/commit dates?

There are a lot of ways we can get strange edge cases for commit-graph 
walks, especially when we start being clever. This test case is only a 
start to feeling like we have good coverage, but having a non-trivial 
walk include both outputs (yes/no) for each method is a good start.

I think after we get a basic coverage for these methods on this example, 
we can add examples as necessary when we find tricky code paths that 
need coverage.

Thanks,
-Stolee