proptotype of make style dep stuff

[Duncan Coutts]

On Tue, 2007-10-30 at 19:31 -0400, Peter Gavin wrote:
> On 10/30/07, Duncan Coutts <duncan.coutts at worc.ox.ac.uk> wrote:

> > http://haskell.org/~duncan/cabal/foo.svg
> 
> Very nice :)

Yeah, we were pretty pleased :-)

> > As you can see we get cycles in the graphs. We'll have to filter out
> > cycles. Any suggestions on a simple way to do that?
> 
> I noticed that. You could do a DFS and prune the back edges.

Would that be minimal? We'd only like to delete something near the
minimum number of edges to make the cyclic graph into a DAG.

> > So the first testing strategy we're going for is to generate random dep
> > graphs.
> 
> I'm thinking it may be possible to make a finite base set of test
> cases that represent of all possibilities, but I'm not sure about
> that.

For testing our real rule sets I was thinking we should generate some
test cases from real projects, eg Cabal's own dep graph.

> > From there we will write out a suitable selection of the files
> > and run the make algorithm. We then inspect the resulting event trace
> > and final state to check that everything worked correctly. So we'll be
> > making the dependency generator from this random dep graph too.
> >
> > So this is for testing make in isolation. For the next bit of testing
> > our rule sets for building Haskell projects we'll have to generate dep
> > graphs that use files mentioned in our rule sets. That's probably a bit
> > harder.
> 
> I have an good idea about what's necessary here.  Ideally, GHC would
> could give us a list of imports for a given sourcefile.  (That way we
> don't have to do ad-hoc parsing.) 

See ghc -M in the ghc user guide. Parsing that should be trivial.

> The same thing goes for C2HS. I guess actually you might not be
> thinking that far ahead yet :)

> If you have anything specific in mind I can work on, feel free to let
> me know.

Probably the next thing we want are some small but more real test cases
that will provide milestones in the development of rule sets. For
example we'd start with simple sets of .hs files. But next we'd want
examples using cpp, .hi boot files, .hs files that produce _stub.c files
as dynamic target, c2hs etc. These should be examples small enough to
work with and debug but should also be sufficiently realistic.

The next step after that would be some larger test cases. These would
make great regression tests. Maybe you'd like to look at generating test
cases from real projects. That is, generating sequences of actions in
the Make monad to set up the virtual file system to a state representing
the real project.

For both these suggestions, generating small or realistic examples we
need to consider the representation of import style dependencies in the
presence of pre-processors. Lennart made the suggestion that we should
represent the content of our virtual files as a list of sets of
dependencies where each stage of pre-processing strips off a layer. For
example consider a Foo.chs file:
{# import Bar #}
import Baz
The Foo.hs, Foo.chi files depend on Bar.chi while Foo.o, Foo.hi depend
on Bar.hi and Baz.hi. We'd represent the file content therefore as:
[["Bar"]
,["Bar", "Baz"]]


In your patch you were dealing with the real rule sets required to build
stuff with ghc and c2hs. Perhaps you could look at the rule schema and
dependency generation side of things. Currently in our model we hide all
that behind a dependency generator function. Eventually of course we'll
want some nice composable way of building dependency a generator
function, probable from some representation of rule schema.

Lots to do :-)

Duncan