Re: proptotype of make style dep stuff

On Tue, 2007-10-30 at 19:31 -0400, Peter Gavin wrote:

On 10/30/07, Duncan Coutts 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