I haven't looked at the code yet, but I wonder: why a new PR instead of building on top of #4339?

That code has been running in production for months now.

I haven't looked at the code yet, but I wonder: why a new PR instead of building on top of #4339?

This PR uses mostly a different approach. For example, it doesn't assume changes in externs format, etc. It provides an overview of concrete changes and explains those decisions. Also, if I'm not mistaken #4339 was refered as abandoned lately by the author.

Sorry. I've failed to explain it properly, because multiple people have looked at the code in that PR without reading the comment thread first.

I'd be more than happy for you to take a 4th stab at this, with or without the code I've written. The important thing is that we get a faster compiler.

https://github.com/drathier/purserl is where the caching fork lives, since about 6 months. It's a rewrite of the linked PR into something that's more likely to be mergable, but I've given up on getting it merged. Plus I've merged in the purerl code gen into the same binary, halfing compile times for erlang projects. We're using it daily at work and it's very useful. Merging in main every release is much less work than getting it merged, so that's what I'm doing.

Sorry. I've failed to explain it properly, because multiple people have looked at the code in that PR without reading the comment thread first.

No problem, I understand that you are using your solution in your fork, I just read that you said that code in PR itself was abandoned. I've been working on this for quite a while, even before I saw #4339. I first started working on this because I wanted to cut off the loading of unnecessary extern files during re-builds, then I saw that I could cut off the build plan itself. In #4339 I saw a solution and design decisions that were not clear to me (something that is called caching, and chanding the externs format) so I decided to finish my work with the approach that seemed more correct to me.

https://github.com/drathier/purserl is where the caching fork lives, since about 6 months.

You could build you version on top of this PR and compare the results.

@drathier And you also are probably the person who can competently review this PR.

Yes, I'll try to find the time to review it this week.

The main idea behind the caching strategy we're using is:

1. each module exports everything that's public in the module
2. each module tracks everything it actually depended on from all imported modules when rebuilding (this is the main change to the externs file format)
3. if none of the things we're depending on changed, there's no need to recompile the current module

Step 1 and 2 are very hard to validate, as the information is lost during compilation (e.g. how do you know what type alises are you depending on when they've all been desugared away?).

https://youtu.be/BQVT6wiwCxM?t=762 is a useful high-level reference table for different caching strategies. It's also in the paper https://www.microsoft.com/en-us/research/uploads/prod/2018/03/build-systems.pdf .

If to explain the strategy I use in a couple of sentences: When we have externs of a module then know all the things that dependants can use, and by comparing with previous externs results we know what exported things have been changed/removed/added. When we decide if to recompile a module, we have all this information about its dependencies, so we need to determine if the module uses any of those things (exported from dependencies) that have changed.

Cached things that we already have here: previously built products with externs files.

❗ The thing to discuss: currently I have added a progress message Skipping My.ModuleB for skipped modules (along with Compiling My.ModuleA). We need to decide what to do with this message, should we print it out or not.

Also, there is question maybe we should somehow output the reason why the module is not skipped (output a thing changed used) - don't know if it is feasable. I think this is needed just for debug purposes.

❗ The thing to discuss: currently I have added a progress message Skipping My.ModuleB for skipped modules (along with Compiling My.ModuleA). We need to decide what to do with this message, should we print it out or not.

I don't think messages about skipping are particularly useful outside of debugging. Compiling is useful because it's an indicator of work being done.

Printing the reason why something recompiled helps people debug slow compile times. Likewise printing if compilation of a particular module took more than e.g. 10s, or printing the 10 slowest-to-compile modules. If it's easy to add something like this in, I think we should do it. Otherwise, it's a nice change in its own PR. We could add lots of debug info to the output and enable that feature using an envvar or cli flag, for example.

Make method API question for discussion.

Currenlty from Language.PureScript.Make only one method make exposed that returns the list of ALL externs, that were preloaded and rebuilt.

To speed up the process, we may skip loading/parsing of significant parts of externs that are not needed for the build (preload externs only for updated modules and their transitive dependencies), which is implemented in this PR and there is an option to run make that will preload and return externs for all the modules.

Currently make method is used in these places:

• app/Command/Compile.hs
  Externs not used.

• tests/TestUtils.hs
  Not used either.

Here is where returned externs are used:

• src/Language/PureScript/Interactive
  Definitely all externs are needed.

• tests/TestUtils.hs
  Probably too.

• src/Language/PureScript/Docs/Collect.hs
  Probably all externs required, though no tests failed when I forgot to update make method here.

The question is what would be the better API to accommodate existing cases.

Here are some options:

• Currently, I have made two methods make (returnes used externs) and make' (returns all externs).
• One make method with CollectExternsPolicy param (proposed as the first param)
• Potentially make method may require some other options in future, maybe consider MakeOptions record (as the first param).
• Specially named methods makeAndReturnAll or makeAndReturnUsed.

Upd:

• make - returns all (works as before), and make_ - returns (), potentially make' with options.

Lmk when you want another review pass :) Please fix or reply to all review comments before

Lmk when you want another review pass :) Please fix or reply to all review comments before

I believe I answered all the comments, not sure if I skipped some. I made updates to the code so you may review it.

Hey all. Once the row error message improvements get in, this is something else I plan to look at.

Sorry about the late response. Life happened.
I think we're missing these kinds of "compile, get error, fix error, recompile" regression tests? Please add :)

• https://github.com/drathier/purserl/blob/single-binary/tests/TestMake.hs#L244
• https://github.com/drathier/purserl/blob/single-binary/tests/TestMake.hs#L268
• https://github.com/drathier/purserl/blob/single-binary/tests/TestMake.hs#L316
• https://github.com/drathier/purserl/blob/single-binary/tests/TestMake.hs#L353
• Make/build cut-off #4477 (comment)

Other than that, there's a bunch of code quality stuff, but I would be happy to adress those in another PR and get this merged and beta-shipped.

Rewriting history really messes with code review change tracking, so it looks like there's 30 or so comments which are incorrectly marked as outdated. Please don't rebase/squash going forward, because of this problem

Rewriting history really messes with code review change tracking, so it looks like there's 30 or so comments which are incorrectly marked as outdated. Please don't rebase/squash going forward,

I don't remember squashing or rebasing after the comments were made, I added a couple of new commits to address the problems.

To clarify, in case there was a misunderstanding. In order to merge this, I'd like at least the linked tests to be ported over, as they're actual regressions seen in that other implementation. @wclr There are many comments without replies, which I'd be happy to see a reply to too, but the regression tests are the minimum imo.

Yes, I need to review the tests, as I mentioned in some reply to comments all the tests from your fork have passed, I will look closer at those you linked above.

There are many comments without replies.

I think I addressed all the meaningful problems mentioned in the comments, maybe I accidentally missed some. You can probably review your comments again and resolve those that are not actual anymore.

@wclr I did a pass over my review comments to see which ones were done. I'm apparently not allowed to mark my own comments as resolved, and it felt weird deleting comments instead, so I've commented on them again pointing out if they're fixed or not.

Main thing missing is porting the regression tests linked here: #4477 (comment)

After that, I'd be happy to merge this, and I'm really looking forward to having much better caching in the mainline compiler!

@wclr Should this be reviewed again?

I believe @MonoidMusician had started reviewing this recently. From reading above I think there's still an outstanding point about some ported regression tests

Yup I've been looking at this.

@drathier are you still unable to resolve your own comments / would you like me to mark them as resolved?

@MonoidMusician Thanks for reviewing this.

Regarding your comments/suggestions:

• Regarding logs: I'd be happy to have a log file in ./$OUTPUT_DIR/last_build.txt specifically for debugging why modules are being rebuilt or skipped. That way users can have some visibility into what's going on, and it can always exist so they can debug a build retroactively and we don't have to ask them to reproduce it.

I'm not against such a log. To do this we need to decide on the information needed in this file. I may propose something like this:

Module.A compiled
- changed export: myFn # list things that changed
- changed export: MyType

Module.B compiled
- changed imported: Module.A myFn # the reason for rebuild

Module.C compiled
- changed import: Module.A MyType

Module.D skipped

To help further review, I will point out two main reasons why cut/off may fall short:

• We fail to determine things that have been changed, this may happen if something is wrong with externs diffing logic
  There we find all the things directly changed in by diffing externs entries, and then searching though all other exported things in the module, that may depend on directly changed (using graph), and we also apply some custom logic for type classes instances which is not direct.
  So, if there are no basic issues with the approach and we handle all the edge and special cases (like type class instances or type ctros) there should be no problems.

• We fail to find a usage of the changed thing in the checked module. There we search through the module to find encounters of any changed things found in imports. This logic is more likely to be incomplete in some way because matching is not exhaustive, so some things inside the search module could just be missed.

These are the points that should be thoroughly tested, though eventually it should not be difficult to have a complete set of cases, the current set should be reviewed/revised.

• I still need to think about how it interacts with cacheDb. Is there a particular reason to use timestamps on the externs as well? I guess better interaction with ide?

Cache-db contains information on source modules, timestamps and hashes so we can check if we have already performed the build for the current module state.

Timestamps on externs are used to determine previous result compilation time, so we can check if dependencies where built after their parents or not. This may be the case, for example, when purs-ide performs fast-rebuild of a changed module, and then during the build, although the hash for the module in cache-db is valid, we should invalidate all its dependencies.

• Mostly a note to self: need to think about how this interacts with builds canceled with ctrl+c.

It will produce the results for some modules and cache-db won't be changed, the next build will fix everything, but all the modules need to be rebuilt again.

This leads to the question of necessity and convenience of a single cache-db file. I think we can eventually deprecate it in favor of per module meta files. Though we will probably need a single build result summary file for other purposes (like ide checks). This is just a thought for the future.

• From our testing, builds that fail with errors seem to rebuild everything downstream. I guess that's because those modules get deleted from the cacheDb? Would extending it with a field indicating failure help?

That's right, after the build with errors failed modules are removed from cache-db as well as their dependencies (as they are treated as skipped jobs). So the next time we run the build it will invalidate all the modules that are not in cache-db.

It is an important case that I didn't address, but I did encounter it periodically. This should be easy to fix though, we will just not remove those entries from cache-db and will treat them as successful compilations if the module is up-to-date.

I would love to get this PR merged as in our team a large chunk of every day is spent waiting for recompilation. Is there anything we can do to help get it over the line?

@roryc89 Have you tried to use it for your everyday work?

@wclr Not yet but happy to try and add any issues we find with it here.

@roryc89 Have you tried it?
@wclr Do you happen to have a Apple Silicon binary of this lying around?

@wclr Do you happen to have a Apple Silicon binary of this lying around?

No. Why not build on your own?

It's been a while since the last update, there are notable ones with the commit.

To sum up the changes from the current master:

• Preload of only needed externs for the build (for modules that have to be rebuilt and their deps) while constructing build plan.
• Cut off (skipping) compilation for downstream modules that are not affected by changes (via ExternsDiff).
• Preservation of warnings between compilations: saved into warnings.cbor and loaded along with other prebuilt artifacts.
• Compilation progress log file (compile.log) contains info on what modules have been compiled and why.
• Cache db new contains compiler's version (for invalidation).

Minor changes in behaviour:

• Handle module's path chanding (allow rename/move without recompilation).
• Failed modules (with deps) from are NOT removed cachde-db after make (to avoid unnecessary recompile on the next run with fixed modules).

Tests are fully refactored, though I have not yet completed the suite for testing all the cut off cases.

Some questions:

• Should add the cli param for running without externs diff check (or full compiliation without diffs check should be default)?
• Should add param for log file (presence and filename)?
• Is it worth going for direct deps? I've updated module's graph logic so it is possible to know if dependency is direct, and there are a couple of places where working with only direct deps is possible, though I'm not sure if they are performance significant.
• Warnings preservantion: should store parser warnings? Currently, parser's warnings are stored as well, so this can avoid need of parsing for not involved modules.

Also worth noting: changes in this PR along with updates to Purescript.Ide (and Language Server) allow to implement full fledged real-time diagnostics and incremental compilation while development. Instead of calling singleton rebuildModule it is possible to use make (that compiles changed modules with the downstream) and produce a consistent result as a Full Build does but much faster. I've been succesfully using it for quite a while.

For those who want to try it out, you may download binaries here:
https://github.com/wclr/purescript/releases (the latest)

It builds in CI from https://github.com/wclr/purescript/tree/wclr/release branch.

It also publishes NPM package: npm i @wclr/purescript that will download binaries for you.

What to expect from running the build (e.g. spago build, purs compile):

• Compiles only changed modules with affected dependants skipping not affected downsream. In IDE/LS you may try to replace fastRebuild workflow for fullBuildOnSave to get consistent build results quicker than with the current compiler.
• Returns warnings for all modules, including those which were not re-compiled (cached in warnings.cbor in output).
• Puts build progress log into output/compile.log.
• Changed cache-db.json format.

Thanks for making this so easy to test. It seems to be such a massive improvement! Especially after I rebased to include this pr.

The only thing that stands out as a regression is the compilation progress log. On master the numbering is generally sequential but with cutoff I get wildly out of sync numbering, e.g. [1 of 10] Compiling ..., [6 of 10] ..., [3 of 10] .... As things scale this gets funny:

[1410 of 7437] Compiling Options.Applicative.Builder.Completer
[1913 of 7437] Compiling Text.Email.Parser
[5489 of 7437] Compiling AffiliationField
[ 886 of 7437] Compiling Routing.Parser
[1447 of 7437] Compiling Routing.Match

Ideally the progress logger would maintain a count that's separate from however the files are designated a number. As it stands it's pretty hard to estimate remaining time.

@finnhodgkin Thanks for trying this out, I'll fix the index ordering. I've also included the PR you mentioned, as promised it gives ~30% boost.

I've started reviewing this again. I think it is close to mergeable, with a few things that need to be fixed.

Thanks for adding ./output/compile.log. I think having that record of the last build be always available will be helpful if users run into miscompilations.

• I made a fix so the output numbering is roughly in order. (There are still minor race conditions, but it is a useful progress indicator again.)
• I don't understand your comment about not having to remove failed modules – without removing failed modules, the compiler outputs no information and returns exit status 0 when recompiling with no changes after a failed build.
• Possibly related: I mentioned briefly on discord that I don't see cached warnings from modules upstream of the changed files, I only see warnings from modules considered in the build plan (compiled and skipped modules now). This might be a case where users want the behavior to be configurable with a flag, maybe others should weigh in on that.

Those changes are available on my branch. I've been testing it with those changes, comparing the outputs between incremental builds and clean builds. So far I've seen two sources of minor diffs:

• If a file is renamed without its contents changing (e.g. spago installing a different version of the same library), its old filename can/does appear in source spans in both externs and corefn, which is undesirable. Maybe replaceSpanName needs to be applied to externs?
• I also see line numbers that are not updated (just in externs, not in corefn). This is not as big of a deal to me, as it might affect errors/warnings but should not affect the JavaScript output, but if you can think of a way to fix that.
• I have not tested sourcemaps or documentation yet – the stale line numbers may be a bigger issue there.

Also I ran into this error once, possibly as a result of incrementally building from output that was produced by the main compiler not this branch:

purs: An internal error occurred during compilation: make: getBuildReason no barrier
Please report this at https://github.com/purescript/purescript/issues
CallStack (from HasCallStack):
  error, called at src/Language/PureScript/Crash.hs:10:3 in purescript-0.15.15-8WFym9lhKoSJtoPXLBrRrY:Language.PureScript.Crash
  internalError, called at src/Language/PureScript/Make/BuildPlan.hs:108:21 in purescript-0.15.15-8WFym9lhKoSJtoPXLBrRrY:Language.PureScript.Make.BuildPlan

Does this case need to be an error, can it just return a build reason to force the module to rebuild?

I had some time today to look at this see if it feels mergeable based on where @MonoidMusician left off.

In short, I think it is, and while I found a few soundness issues, I've fixed them on trh/make-cutoff-ready, which is based on her branch and the changes below. In addition, I brought in @drathier's regression tests, added several more tests. My changes on that branch are almost all test additions, and a couple of small fixes; the core of what @wclr has built and @MonoidMusician extended I think is well-worth merging essentially as-is with these fixes.

My changes include one potentially controversial addition: a --no-cutoff flag which rebuilds everything downstream of a change — basically, the old compiler behavior — which can be used as an escape hatch for the first release(s) carrying this just in case something isn't right. It's a handful of lines of centralized code we can take out if we want, as I know generally purs doesn't carry many flags.

Here are the ported regression tests:

I also restored the cut-off cases dropped in the test refactor and added coverage for re-exports, hiding imports, operators, kinds/roles, and desugaring.

Next, I did a few rounds of thorough verification comparing incremental builds to clean builds and found a few soundness gaps. Each of these failed on @MonoidMusician's branch, but are fixed here.

• Re-exports through unqualified imports (module B (module A) where import A, i.e. how Prelude/Data.* are written) didn't match against downstream usage, so changes/removals flowing through these didn't rebuild consumers. Fixed in ExternsDiff.checkDiffs/getReExported.
• Newly-added re-exports were absent from the diff, so a name newly brought into scope couldn't rebuild a module it made ambiguous.
• do/ado and unary minus desugar into bind/discard/map/apply/pure/negate, which aren't in the parsed module, so changes to those went undetected. These are now searched explicitly, qualifier-aware, in ExternsDiff.checkUsage.

Specifically I used registry-dev to do a bunch of clean vs. incremental builds, which has about 742 modules across 132 packages, and then compared the externs.cbor, corefn.json, index.js against clean builds after performing a thorough scan editing every module and comparing the clean vs. incremental results to try and produce some stale build. That's where the gaps above were found, and after fixing them I couldn't find a way to perform an edit, build, and have an incorrectly-stale result.

I think this clears @drathier's merge bar and the review points above. Of course, happy to remove --no-cutoff if we don't want it.

Hi, sorry for my a delayed reaction, I postponed this issue for myself as I have been busy with other projects. But as this change got even more traction now I hope we will be able to wrap it up eventually. I'm fairly interested in getting it right.

@MonoidMusician

I don't understand your comment about not having to remove failed modules – without removing failed modules, the compiler outputs no information and returns exit status 0 when recompiling with no changes after a failed build.

I think I was acting from assumption that failed modules should and do not update their info in cache db. So they should either just be removed from new cache db or as a small optimization kept from previous cache db, then rebuild could be avoided in case of the module is fixed and its hash stays the same as a previous working version.

I mentioned briefly on discord that I don't see cached warnings from modules upstream of the changed files, I only see warnings from modules considered in the build plan (compiled and skipped modules now). This might be a case where users want the behavior to be configurable with a flag, maybe others should weigh in on that.

Right, I didn't do load of all the warnings while make. Though it can definitely flood build output seems more correct to show all the warnings for all the modules. Not sure if it should be a subject for flag --all-warnings or --only-build-warnings. Probably front-end tools like spago could have options to manage this.

If a file is renamed without its contents changing (e.g. spago installing a different version of the same library), its old filename can/does appear in source spans in both externs and corefn, which is undesirable. Maybe replaceSpanName needs to be applied to externs?

I kind of missed this. It seems strange to me why we need to have those filepaths in externs files, more over in each SPAN, I guess this is also the main contributor to bloated extern's disk size esp. for large modules. For warnings files I even cleaned them and populated while loading with actual filepath.

The problem with changed filename is essential, we have output artefacts (externs, warnings, corefn, sourcemaps, docs) coupled with module's filepath so when it is changed, even if the module it self is not required to be rebuild, we should re-generate or update those artifacts.

I see a few ways for dealing with this in the current state:

• Drop this case and treat module's filename as part of the module's code (as it is coupled with build artifacts). This not a huge deal, moving/renaming modules (without updating at least a module name) and updating libraries are not the most frequent cases, so it can be left for the future.

• Implement the update of existing artifacts. We actually have implementation for externs and warnings files. Need to cover docs (I believe docs Module be patched the same way using Data class) and source maps (update a single JSON field).

At first, I was inclined for the first option as it doesn't require additional logic and seems not a big omission, but now it seems completing the second is not difficult.

Sidenote: Ideally, I would like build artifacts be decoupled from source's filepath, though for example source maps should contain link to source file inside by standards. Some custom procedures for handing such case would be required anyway.

I also see line numbers that are not updated (just in externs, not in corefn).

What line numbers do you mean, why should they be updated?

Also I ran into this error once, possibly as a result of incrementally building from output that was produced by the main compiler not this branch:

Can you elaborate on this. Is there reproducible workflow?

@thomashoneyman

My changes include one potentially controversial addition: a --no-cutoff flag

I'm in favor of adding a flag that would run build without performing externs diffs (I proposed the same in previous posts), probably it should be named more specifically, e.g. --no-diff-check.

Thanks for your efforts, I will look how it is better to integrate the latest changes and tests into this PR.