Faster GetDependencyInformation rule

[pepeiborra]

The current implementation walks all the source files to parse the module header and then proceeds to locate the imports. In large repos (>10000 modules) this results in very long startup times:

• It is sequential
• It is not cached
• UPDATE: It's quadratic

The obvious solution is to cache it so that the cost is only paid once.

Open questions:

• How would we cache it in a way that doesn't become stale?
• Can we reuse one of the existing caches (.hi files, .hie files and hiedb)?

UPDATE: the reason it's quadratic is that we traverse the module graph once from each node, which is O(N^2). I wonder if there's a reason for this, in that Shake would crash if there were cyclic module dependencies and the error reporting would be crappy. /cc @cocreature @ndmitchell any insights?

/cc @wz1000 @mpickering

[wz1000]

It is possible to cache almost anything in hiedb, given that you can answer the following questions:

1. What schema do you intend to use that will let you answer your queries?
2. Cache invalidation: How will the cache be checked for freshness and consistency?

Currently, for 2. each entry currently in hiedb is associated with a particular .hie file, which is identified by its filepath and hash. If the hash of the .hie file changes, we know to invalidate all the information associated with that file in the database.

[cocreature]

I wonder if there's a reason for this, in that Shake would crash if there were cyclic module dependencies and the error reporting would be crappy. /cc @cocreature @ndmitchell any insights?

That’s exactly it, shake gets very unhappy about cyclic deps.

[michaelpj]

This got fixed