sbt cache ideas

[eed3si9n]

https://eed3si9n.com/sbt-cache-ideas/

[lihaoyi]

It's worth considering if you can do what Mill does. Mill's approach to caching is, approximately, as follows:

1. Every Target[T] has to return a T: ReadWriter, allowing it to be written to disk and read back later

2. File/folder paths where you care about contents are wrapped in case class PathRef(path: os.Path, sig: Int), where sig/hashCode is computed automatically by walking the filesystem and hashing its contents

3. Every Target[T] is given an exclusive dest path on disk in the out/ folder, e.g. foo.bar.compile gets foo/bar/compile.dest/, in which it can read or write whatever it wants without worrying about conflicts with other code.

That's really it. Some nice properties:

1. You can return arbitrarily complicated data structures from a Target, as long as it can be serialized, and you get all the caching stuff for free. A Target can return a Boolean, Int, String, Seqs, Maps, case classes, sealed traits, PathRefs, or any combination of these.

2. You can write whatever file paths you want without worrying about conflicts, as long as it's within your target's dest folder. This can be used as a scratch space for files you don't care about, or you can return PathRefs to paths within it for the file/folder contents to participate in cache key computation and invalidation

3. You can return PathRefs arbitrarily mixed in to the rest of the data inside the T your Target returns. Your target can return a PathRef, a Seq[PathRef], a case class containing some PathRefs and some other fields, etc.. and it automatically participates in sig/hashCode computation.

In general, Mill's approach means that both metadata and files go through the same code paths, and can be treated largely interchangeably. This greatly simplifies things, and allows all sorts of Target to share the same logic: from the most lightweight settings def scalaVersion: Target[String] returning a trivial string to the most heavyweight def compile: Target[PathRef] containing a folder full of classfiles.

[lefou]

I agree with @lihaoyi here. The concept works great and is pretty simple to get and implement by all users. Though, mill.api.PathRef currently stores absolute paths, but we already thinking about support for relative paths based on some base path, like workspace or coursier cache, to make PathRef more suitable to to shared caching.

[smarter]

In addition, the shape of the source code also need to be part of the input hash. In Scala 3, this would likely use Expr#show.

Pretty-printing is expensive, but we have some tree hashing logic used internally for incremental compilation of inline defs that we could potentially expose in the meta-programming APIs if we take the time to make it more robust: https://github.com/lampepfl/dotty/blob/7226ba60d443fae040ab5a95294ff773d6b71775/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala#L692-L785

[lihaoyi]

Another approach I've considered for Mill is bytecode analysis. This has the advantage of being a very stable format that is independent of Scala version, simpler than Scala compiler ASTs/Symbols, while still having enough information to construct call/dependency graphs to generate code hashes

It's worth mentioning that the hash of the source code of any particular task definition is not enough. You need the hash of the code for any libraries or helper methods it calls, transitively. This is a whole-program analysis. Tricky, but doable with enough care

[SethTisue]

Doesn't bytecode analysis miss too many compile-time only features, such as opaque types?

[lihaoyi]

It would, but does it matter? The goal is to figure out if a function's behavior would change at runtime. The runtime behavior is totally specified by the JVM bytecode.

compile time changes that dont affect runtime behavior, e.g. replacing ints and math operations with an opaque type and inline defs, would rightfully not change the task code hash. Compile time changes that do affect runtime behavior, e.g. by changing method/overload/implicit resolution, would leave changes in the bytecode that we would detect and use to update the task code hash

[lihaoyi]

I have implemented the bytecode analysis idea in Mill com-lihaoyi/mill#2417

This implementation is a pretty generic bytecode callgraph analyzer: CHA, conservative/simplified treatment of library code, one-pass to generate transitive-callgraph-hashes for all methods in the codebase. It has very narrow integration points with Mill, basically taking the resulting transitive-callgraph-hash for each target method and adding it to Mill's existing target-input hash. It should be easy to re-use in other tools, whether in SBT for code-change task invalidation, Zinc for proper macro invalidation, or even other things e.g. a dead code detector

It seems to work. Still needs review, so if anyone is interested in helping look over the code I'd really appreciate it. And it's all MIT licensed so feel free to copy-paste it anywhere else if you'd like to try it out, it's pretty small at 6-files/~1000-lines (and ~4x as many lines of tests)

[kubukoz]

I would love to push what Mill does even further, and cache things globally, or at least allow reusing caches when jumping between branches.

e.g.

1. checkout main
2. compile
3. checkout dev
4. compile
5. checkout main
6. compile - this one is still cached and free

[lefou]

We have a POC PR in Mill which does exactly that. com-lihaoyi/mill#2777

[eed3si9n]

sbt 1.x already does remote caching for compile. sbt 2.x cache should be generic to any task that wants to participate, and the cache implementation also should be somewhat generic that implementations can participate.

[kubukoz]

it should also be more transparent than having to run pushRemoteCache. Perhaps I'm holding the tool wrong, but I don't see anything about this being used under the hood in https://www.scala-sbt.org/1.x/docs/Remote-Caching.html