Incremental compilation for Crystal - Part 3

#crystal #incremental #compilers #compilation

Recap from the previous two posts

In the last two posts we saw a way to generate dependencies between files like this: if a method call is made, the file where that call happens depends on the file where the method is defined. And that dependencies are transitive because of how Crystal works.

Then we saw that the file dependencies graph is quite messy for real programs and that changing one file usually affects most of the other files.

An observation

After writing the last post I realized there's something slightly wrong in the way dependencies, and more precisely transitive dependencies, are tracked.

Consider the following files:

# foo.cr
require "bar"

def foo
  bar
end

foo

# bar.cr
require "baz"
require "qux"

def bar
  baz
  qux
end

# baz.cr

def baz
  1
end

# qux.cr

def qux
  "hello"
end

Doing a dependencies graph for the above program gives this:

So bar.cr depends on both baz.cr and qux.cr.

If we change the method qux to return an int, bar will start retuning an int, and so foo will start returning an int: transitive dependencies doing their stuff.

BUT, and this is the important bit, if we change the method baz to return a different type, no matter what type, and no matter how many changes we do to it, we do need to re-compile and re-analize bar, but it doesn't affect foo because baz is not being used as a return value of bar.

That means that the messy dependencies graph we have so far might not be that messy after all. And also, that we have two graphs: direct dependencies and transitive dependencies.

When we checked the method IO#<< and saw that it calls obj.to_s, so io.cr depends on whatever type we give to IO#<<, the method definition is this:

class IO
  def <<(obj) : self
    obj.to_s self
    self
  end
end

But note that the obj.to_s call isn't part of the return type. That means that, yes, if the file where the type of obj changes we need to recompile io.cr, but it doesn't mean we have to recompile files that depend on io.cr.

Computing actual transitive dependencies

Now, the main issue is determining which method calls affect the return type.

For example, consider this:

def foo
  x = bar
  x
end

Here the method returns x, and x came from a call to bar, so foo transitively depends on bar. So we have to keep track of how variables came to exist, and their dependencies. Luckily the Crystal compiler already keeps track of this to actually compute the type of x, so in theory this should be easy to do.

Another example is this:

def foo
  qux
  if something
    bar
  else
    baz
  end
end

Here the last expression in the method is an if, so the actual dependencies of foo are bar and baz, but not qux.

Another dependency that might not be easy to see is call arguments. For example:

def foo
  bar(baz(1))
end

Here foo depends on bar. But does it depend on baz? Well, if baz suddenly changes and returns a different type, another overload of bar might be hit that returns a different type, and so foo might start returning a different type. So it seems that call arguments need to be taken into account.

What's next?

I'll need some time to code this and get it right. Once I do that I'll post my findings. Will the dependencies graph be leaner? Will we find happiness? Will it make us cry? Stay tuned!