Think about forward edges

[ndmitchell]

Following on from https://stackoverflow.com/q/24844338/110081, @feuerbach suggests:

If we think about classic make-style build systems, they are based on back edges. (I picture the edges in the dependency graph going from source to target.) We start with a terminal vertex (such as "ALL", "build", "install" etc.), and traverse the edges backwards to find all the dependencies, and so on.

Some computations (such as mine) are more conveniently expressed in terms of forward edges. We don't know the exact target; instead we have a bunch of source files (such as web pages) and the rules specifying how to process them.

This is more similar to a shell script than a Makefile. The only reason to use a build system such as Shake instead is the short-circuiting behaviour.

When there's a direct correspondence between source and target files (such as one between .c and .o files), there's almost no difference between the two approaches. But imagine when the file itself determines the set of output files (which isn't unrealistic — I think metapost/asymptote have this feature), then trying to express this forward flow with backward edges can be unwieldy.

I should think about what that means, if you can express it in Shake, if it should be on the build-shootout etc.

[ndmitchell]

Initial thoughts: you need to be sure that the multiple things don't produce the same outputs, or you get inconsistent results. You need to in some place say where you "drive" from, and that needs to record what it "produced".

[nomeata]

Sounds interesting, and something that I probably often want in my tools.

Here is an example, simplified from what I’m doing right now: I have a directory with .log files. From each .log file I want to extract a .csv file, and from that .json report. That’s one obvious normal rule each, but how do I “pull” all the .json reports? For that I use something like

    "reports" ~> do
        logs <- filter looksLikeALogFile  <$> getDirectoryContents
        need [ takeBaseName log <.> "json" | log <- logs ]
    want ["reports"]

With forward edges, maybe this phony rule (which needs to know both the input of the chain of rules, and the output, i.e. the knowledge is duplicatd) could be dropped.

[Mathnerd314]

Is this also the 'unknown result' pattern? (#421)

[ndmitchell]

The initial motivation on stack overflow is the lossy information pattern - where information is available in the person who does the need that you want available in the *> rule. That's a bit different to unknown result, but certainly related, it's what I was referring to in https://github.com/ndmitchell/shake/issues/421#issuecomment-184437586.

I think @nomeata is just after a forward build system though, which Shake.Forward might perfectly answer in the next release.