Incremental compilation for Crystal - Part 2
Tags: crystal, incremental, compilers, compilation
Published: 2023-01-04 18:27:25

---
title: Incremental compilation for Crystal - Part 2
published: true
description: Thoughts about how to introduce incremental compilation for Crystal
tags: Crystal, incremental, compilers, compilation
series: Incremental compilation for Crystal
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-01-04 17:56 +0000
---

In the last post we found out that we could build a file dependencies graph for a given project. We also saw that, depending on the code, a file could depend on one another even if it's not immediately clear that that's the case.

But... is that dependency issue really an issue?

# Checking the tool against real-world projects

In this section I'll look at the dependencies graph of two medium/big projects:
- [Mint](https://github.com/mint-lang/mint)
- The Crystal compiler

We can use [this branch]([branch](https://github.com/asterite/crystal-1/tree/dot-dependencies)) of the compiler to compile Mint and the compiler to get the "dependencies.dot" files.

Then we can use [this program](https://gist.github.com/asterite/c96cef663e4700d7512ad251b0e31494) to analyze the above files. The program will read a "dependencies.dot" file, build the graph in memory, and then for each node in that graph count how many nodes are, recursively, affected by it. This answers this question: if we make a change to a file, what are all the files that we need to re-analyze?

# Transitive dependencies

Before looking at that, though, note that I said "recursively". If a file A depends on B, and B depends on C, why if we make changes to C we need to re-analyze A?

Let's take a look at an example.

```crystal
# foo.cr
require "bar"

def foo
  Bar.bar
end

foo

# bar.cr
require "baz"

module Bar
  def self.bar
    Baz.baz
  end
end

# baz.cr
module Baz
  def self.baz
    1
  end
end
```

Here we have that `foo.cr` depends on `bar.cr`, and `bar.cr` depends on `baz.cr`.

What does `foo` return? It returns an integer, because `foo` calls `Bar.bar`, which in turn calls `Baz.baz`, which returns 1.

If we change `Baz.baz` to return a string, `foo` will start returning a string too. So, effectively, changing `baz.cr` affected `foo.cr`. And note that the program still compiles just fine.

Does this transitive dependency re-analysis happen in other languages too? I don't know. But let's imagine Crystal forces you to specify argument and return types for methods, like Java, C#, Go, Rust, and essentially every statically typed language out there.

Now we have these files:

```crystal
# foo.cr
require "bar"

def foo : Int32
  Bar.bar
end

foo

# bar.cr
require "baz"

module Bar
  def self.bar : Int32
    Baz.baz
  end
end

# baz.cr
module Baz
  def self.baz : Int32
    1
  end
end
```

Now if we change `Baz.baz` to return a `String`, `Bar` will stop compiling. We can change `Bar.bar` to return a `String` and then change `foo` to return a `String` and then it will compile again. But doing that we changed all those files, so they naturally have to be re-analyzed.

But files don't always have to be re-analyzed like this. Let's say we change `Baz.baz` to return a `String`. We can make `Bar` still compile and return an `Int32` like this:

```crystal
module Bar
  def self.bar : Int32
    Baz.baz.size # The size of the string
  end
end
```

Here we ended up changing `Bar` because of changes made to `Baz`, but we didn't have to change `foo`. Not only that: we don't have to re-analyze `foo` because `Bar.bar` still returns an int. We need to re-compile `bar.cr`, but `foo` can still keep calling the same method.

With all this, another partial conclusion is that not having mandatory type signatures in methods means even more that a change in one file can affect files that are far away in the dependency graph.

# Checking affected files counts

If we run the [above mentioned program]([this program](https://gist.github.com/asterite/c96cef663e4700d7512ad251b0e31494)) on the "dependencies.dot" file for Mint, we'll see something like this:

```
src/macros.cr: 1
src/mint.cr: 1
src/utils/index_html.ecr: 1
src/utils/service_worker.ecr: 1
src/constants.cr: 2
src/app_init/scaffold.cr: 1193
src/artifact_cleaner.cr: 1193
src/assets.cr: 1193
src/ast.cr: 1193
...
1059 lines more
...

Total files: 1405
```

I forgot to mention that this only outputs files in "your project". That is, the most common scenario is that you'll change files in your project, not in shards or the standard library.

Also, the output is sorted by number of affected files for a given file.

In this project there are a total of 1405 files, including files from shards and the standard library. And for the vast majority of files, if we make a change to them it ends up affecting 1193 files. That means that we'll end up needing to re-analyze most of the files anyway.

Doing this with the compiler is similar:

```
src/compiler/crystal.cr: 1
src/compiler/crystal/tools/doc/html/_head.html: 1
src/compiler/crystal/tools/doc/html/_list_items.html: 1
src/compiler/crystal/tools/doc/html/_method_detail.html: 1
src/compiler/crystal/tools/doc/html/_method_summary.html: 1
src/compiler/crystal/tools/doc/html/_methods_inherited.html: 1
src/compiler/crystal/tools/doc/html/_other_types.html: 1
src/compiler/crystal/tools/doc/html/_sidebar.html: 1
src/compiler/crystal/tools/doc/html/js/doc.js: 1
src/compiler/crystal/tools/doc/html/main.html: 1
src/compiler/crystal/tools/doc/html/sitemap.xml: 1
src/compiler/crystal/tools/doc/html/type.html: 1
src/compiler/crystal/tools/init/template/example.cr.ecr: 1
src/compiler/crystal/tools/init/template/example_spec.cr.ecr: 1
src/compiler/crystal/tools/init/template/gitignore.ecr: 1
src/compiler/crystal/tools/init/template/license.ecr: 1
src/compiler/crystal/tools/init/template/readme.md.ecr: 1
src/compiler/crystal/tools/init/template/shard.yml.ecr: 1
src/compiler/crystal/tools/playground/views/_workbook.html.ecr: 1
src/compiler/crystal/tools/playground/views/layout.html.ecr: 1
src/crystal/compiler_rt/divmod128.cr: 1
src/crystal/compiler_rt/fixint.cr: 1
src/crystal/compiler_rt/float.cr: 1
src/crystal/compiler_rt/mul.cr: 1
src/crystal/once.cr: 1
src/crystal/system/process.cr: 1
src/http/server/handlers/static_file_handler.html: 1
src/log.cr: 1
src/log/setup.cr: 3
src/compiler/crystal/command.cr: 6
src/compiler/crystal/command/cursor.cr: 6
src/compiler/crystal/command/eval.cr: 6
src/compiler/crystal/command/repl.cr: 6
src/compiler/crystal/command/spec.cr: 6
src/compiler/crystal/command/docs.cr: 7
src/compiler/crystal/command/env.cr: 7
src/compiler/crystal/command/format.cr: 7
src/compiler/crystal/command/playground.cr: 7
src/compiler/crystal/tools/print_hierarchy.cr: 7
src/spec/cli.cr: 7
src/array.cr: 451
src/base64.cr: 451
...
444 lines more
...

Total files: 513
```

Again, with a total of 513 files, making changes to most files ends up affecting 451 other files, which are almost all of them. So trying to reuse previous compilation data won't be a lot of benefit.

# The end?

Is this the end of the incremental compilation exploration? Is there nothing we can do about this? No! This is just the beginning. We have to look deeper into how things depend on each other. Maybe files aren't the incremental compilation unit we are looking for? Maybe we could introduce some small changes to the language to prevent transitive dependencies? Maybe the analysis can still be reused for methods that have a specified return type?

Like before, I didn't explore any of these options yet. Maybe I will!