[darcs-devel] [patch1891] add Darcs.Util.Graph.components with pro... (and 5 more)

[Ganesh Sittampalam]

Ganesh Sittampalam <ganesh at earth.li> added the comment:

>   * replace quickcheck with leancheck for testing Graph properties
>
>   Calculating graph properties scales very badly because the
>   specifications aren't optimised (naturally). Exhaustive testing with
>   leancheck is a lot more effective here because we avoid testing with
>   (too) large graphs. Unfortunately test-framework is a bit limited in
>   that it doesn't allow to scale the number of tests, just to set them
>   to a fixed value. We opt to set it to 0x8000 which covers all graphs
>   up to size 6.

It'd be helpful to put the comments about why 0x8000 and why leancheck
in the code.

BTW we might consider switching from test-framework to tasty, I think
test-framework is in maintenance-only mode nowadays. From what I'm aware
tasty is its natural successor.

>   * remove Darcs.Util.Graph.bk and some minor refactors

OK

>   * add Darcs.Util.Graph.components with properties and tests
BTW I had to apply the patches in this order (which is not the order
they were sent) to avoid build breaks.

> components :: Graph -> [VertexSet]

Given the unsafe indexing inside this, I presume we could get a segfault
if it is passed an invalid Graph. I'm not sure whether to be concerned
about that or not. I'd be inclined to play it safe unless you're sure
this really matters performance-wise. Just replacing the unsafeRead
should be good enough as it also guards the unsafeWrite.

Rest is fine.

>   * simplify and improve Darcs.Util.Graph.components

OK (the unsafeRead comment from above still applies)

>   * move functions to generate graphs from harness to library

OK

>   * use Darcs.Util.Graph.components for RepoPatchV3
>   
>   This required a few refactors and the introduction of a new data type for
>   components. In particular, the ltmis algorithm needs to be adapted to
>   working with just a subset of the vertices of a graph.

Is this because previously we constructed the graphs after calculating
the components, so each component had a self-contained graph with
contiguous numbering?

I didn't read the code in detail but I'll assume the tests are good enough.

__________________________________
Darcs bug tracker <bugs at darcs.net>
<http://bugs.darcs.net/patch1891>
__________________________________