Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

case class issues in package-private objects are not skipped #771

Open
lolgab opened this issue Jul 3, 2023 · 0 comments
Open

case class issues in package-private objects are not skipped #771

lolgab opened this issue Jul 3, 2023 · 0 comments

Comments

@lolgab
Copy link

lolgab commented Jul 3, 2023

Reproduction

diff --git a/functional-tests/src/test/case-class-in-package-private-object-ok/app/App.scala b/functional-tests/src/test/case-class-in-package-private-object-ok/app/App.scala
new file mode 100644
index 0000000..56ef142
--- /dev/null
+++ b/functional-tests/src/test/case-class-in-package-private-object-ok/app/App.scala
@@ -0,0 +1,5 @@
+object App {
+  def main(args: Array[String]): Unit = {
+    println(foo.A(1))
+  }
+}
diff --git a/functional-tests/src/test/case-class-in-package-private-object-ok/problems.txt b/functional-tests/src/test/case-class-in-package-private-object-ok/problems.txt
new file mode 100644
index 0000000..e69de29
diff --git a/functional-tests/src/test/case-class-in-package-private-object-ok/v1/A.scala b/functional-tests/src/test/case-class-in-package-private-object-ok/v1/A.scala
new file mode 100644
index 0000000..95e45b0
--- /dev/null
+++ b/functional-tests/src/test/case-class-in-package-private-object-ok/v1/A.scala
@@ -0,0 +1,5 @@
+package foo
+
+private [foo] object Foo {
+  case class A(i: Int)
+}
diff --git a/functional-tests/src/test/case-class-in-package-private-object-ok/v2/A.scala b/functional-tests/src/test/case-class-in-package-private-object-ok/v2/A.scala
new file mode 100644
index 0000000..11bf4fb
--- /dev/null
+++ b/functional-tests/src/test/case-class-in-package-private-object-ok/v2/A.scala
@@ -0,0 +1,5 @@
+package foo
+
+private [foo] object Foo {
+  case class A()
+}
lihaoyi added a commit to com-lihaoyi/mill that referenced this issue Jul 30, 2023
…2417)

This PR replaces the coarse-grained script-import based
target-invalidation-on-code-change (introduced in
#1663) with fine-grained
invalidation based on the JVM-level method callgraph ([previous
discussion](#2348)). This
callgraph is constructed by using [ASM](https://asm.ow2.io/) to parse
the bytecode generated by compiling `build.sc`: We compute a code-hash
for every method based on its bytecode, and propagate that hash
throughout the call graph Merkle-Tree-style, resulting in a
`methodCodeHashSignatures: Map[String, Int]` dictionary that associates
each method with a hash signature representing both its own code as well
as the code of all methods that it calls (transitively). A more limited
analysis is applied to upstream library code. This hash signature is
then used as part of the `inputsHash` for each target, causing a Target
to invalidate after a code change only if the code change affected the
Target's implementation method or some other method that it calls
(transitively)

Of the 7,000+ lines in this PR, only about ~1,000 are implementation
code, the other ~6,000 are test cases. Most of the 100+ files added in
this PR are also just tiny standalone Java/Scala files serving as test
cases, with the main logic in `main/codesig/` being about a half-dozen
files and a handful more for the test utilities

## Algorithm

At a high level, the analysis logic living in the `main/codesig/` folder
does the following:

1. `LocalSummary` parses the compile output of `build.sc`. This extracts
the class hierarchy, computes method code hashes, and identifies method
callsites within method bodies.
* Notably, JVM lambdas (InvokeDynamic bytecodes) are treated as if they
are called at-definition-site. Even though that is not strictly precise,
it is conservatively correct, and is the same thing the Scala.js
optimizer does according to @sjrd.

3. `ExternalSummary` parses any super-classes of locally-defined classes
that are in the upstream classpath - Java/Scala stdlib, Mill code, or
things that are `import $ivy`ed - and extracts the class hierarchy and
method signatures without analyzing method bodies.
* This is necessary so that calls against externally-defined interfaces,
e.g. `InputStream#read`, can be properly traced to local implementations
even if they do not extend the interface directly (e.g. a `MyInputStream
extends ByteArrayInputStream` class)

5. `ResolvedCalls` uses the class hierarchy to identify what potential
implementations each callsite will resolve to.
* For calls to virtual methods, we treat them as potentially calling any
implementation of any subclasses across the whole program. This is done
without regard to whether the sub-class would be instantiated or not
* For calls to external methods for which we did not analyze the
bytecode, we treat them conservatively and assume that they could
potentially call any other external methods defined in the receiver
class, the function parameter types, or any of their superclasses, and
thus any locally-defined overrides for those external methods. This is
similar to the approach taken in [AVERROES: Whole-Program Analysis
without the Whole
Program](https://plg.uwaterloo.ca/~olhotak/pubs/ecoop13.pdf)

6. `ReachabilityAnalysis` converts the method resolution results into a
heterogenous call graph (comprising `LocalDef`s, `Call`s, and
`ExternalClsCall`s) that we feed into Tarjan's to generate topo-sorted
strongly-connected-components. We then walk the SCCs in topological
order to do the Merkel-Tree hash propagation in one pass, with every
method within a SCC having the same hash (because they all call each
other circularly, and so they must have the same transitive call graph)

* Here, we do some special casing for Single-Abstract-Method types and
implementations, to make them work like InvokeDynamic lambdas (i.e.
count reachability via instantiation, rather than via interface method
invocation). This is the right thing to do in principle since SAM
methods and Indy lambdas have similar use cases, and is necessary in
practice because the compiler often chooses between the two styles of
generating code somewhat arbitratily
(scala/scala#3616)

7. For every `Target`, we look up the hash of it's `def` method, as well
as the `<init>` constructor methods for each of its enclosing `Module`
classes, and combine them to form the final hash of the `Target`

* Mill `Target`s must live on `Module`s which form a tree of static
`object`s. We walk the object tree from the `Target`'s directly
enclosing module to the root module using a new `enclosingModule`
property on the `mill.define.Ctx` value, and look up all their `<init>`
methods. They should all only have one `<init>` method since they're
static objects

From the Call Graph Analysis literature, this is a relatively
straightforward Class Hierarchy Analysis (CHA), with some tweaks called
out above. Notably we aren't able to generate callgraphs via more
precise algorithms such as Rapid Type Analysis (RTA), which would
generalize our the lambda special-casing for all user-implemented
traits.

## Limitations

1. We do not do any kind of dataflow analysis. 
* That means we do not know when a Target calls a method whether it is
passing values in, receiving return values out, causing side effects, or
some combination of these.
* We just assume that if a Target end up transitively calling a method,
it is likely to affect it *somehow*, and we thus invalidate it to be
re-run
* This also means that `def`s and `val`s in the body of a class are
handled differently, despite looking superficially similar. `def`s are
full methods and participate in the call graph, so changes would only
invalidate downstream Targets that transitively end up calling that
method. `val`s are simply fields that are initialized in the class'
`<init>` constructor method or `<clinit>` class initialization, so
changing in `val` ends up invalidating any downstream Targets that
create a `new` instance of that class: probably a much broader set of
Targets

2. Both the handling of JVM lambdas and the handling of virtual methods
are approximations
* For JVM lambdas, we assume that they are "live" just because they are
instantiated, without checking if they get called
* This means that a lambda that is created but doesn't end up getting
called gets imprecisely marked as a callgraph dependency
* For virtual methods, we assume they are "live" just because they get
called, without checking if the relevant class gets instantiated
* That means that if a Target makes a virtual method call to e.g.
`InputStream#read`, we will assume that Target depends on all
`InputStream#read`s across the codebase, even if for subclasses of
`InputStream` that never get instantiated
* Both are conservative approximations that would cause some unnecessary
callgraph edges, but both approximations are well fit to actual usage
patterns (JVM lambdas have one method and tend to have tons of different
implementations, whereas virtual methods tend to have multiple methods
and a small number of implementations)
* Doing the "proper" thing and checking _both_ for calling and
instantiation is done by Rapid Type Analysis (and other more advanced
callgraph analyzers). These typically require a separate whole-program
analysis for every Target we may want to invalidate, which would be
unfeasible in a large build with 100s of Modules and 10,000s of Targets.
There are some approaches that may mitigate that (e.g. [Overlap-aware
rapid type analysis for constructing one-to-one matched call graphs in
regression test
selection](https://www.semanticscholar.org/paper/Overlap-aware-rapid-type-analysis-for-constructing-Kim-Jeong/68b3dfadb2a67a13a1ec78f90f8d8192f71be0e6?citedSort=relevance),
[Incrementalization of Analyses for Next Generation
IDEs](https://www.semanticscholar.org/paper/Incrementalization-of-analyses-for-next-generation-Kloppenburg/414fa60c65fc1aed05e4f522386de50066641321))
but for now I'm just leaving it for future work.


3. We avoid detailed callgraph analysis of external/upstream libraries
because the entire transitive codebase would be very large: e.g. all of
Mill, all of `com.lihaoyi`, all of Scala std lib, all of Java std lib.
Limiting our detailed analysis to the relatively-small `build.sc`
compile output simplifies things and greatly speeds things up, at the
expense of some precision in the callgraph


4. Apart from the question of CHA v.s. RTA, it is probably also possible
to get more precise callgraphs by performing the analysis at the Scala
level rather than at the JVM bytecode level ([Constructing Call Graphs
of Scala Programs](https://plg.uwaterloo.ca/~olhotak/pubs/ecoop14.pdf)).
I chose to work at the JVM bytecode level because it's
simple/stable/familiar to me, but trying to do the analysis at the
Scala-level is potential future work.

* We are able to ignore the Scala-level program information because at
the end of the day what runs on the JVM is bytecode. Thus the bytecode
fully defines the runtime semantics of the program, and changes in
bytecode are sufficient to tell us if a target needs to be invalidated,
even if it's not as precise as what the Scala type information can give
us

## Notes

1. I special-case handling of `new sourcecode.Line(_)` and explicitly
ignore the argument (~always a literal number). This is because we
explicitly do *not* want line number changes to force things to
re-compile: even if they can in theory affect the output of a target,
the assumption is that it's just there for debugging/inspect purposes
and won't. The way I do this in a bit hacky and relies on the bytecode
pattern generated by the Scala compiler, but it seems to work.

2. This analysis in ignores fields entirely. In general, any change to
instance or static fields that matters would be accompanied by
corresponding changes to method bodies, even if just changes to the
`<init>` constructor method.

3. The approximations we use to handle InvokeDynamic lambdas and virtual
method calls is necessary for this analysis to be precise enough to be
useful.
* If we treat lambdas like any other set of trait/implementations, the
callgraph would end up including an edge from every `def foo = T{}`
Target to every other Target in the `build.sc`.
* Conversely, if we treated virtual methods the same way we treat
lambdas, then every `mill.Module` someone instantiates (e.g. by
referencing the module name, which invokes the class static initializer,
which instantiates the class itself) would have all its methods and
Targets depended-on by default by the instantiating method.
* Both of these would cause enough additional callgraph edges to make
everything depend on everything else, rendering callgraph analysis
useless

4. We ignore calls to `Target`-returning methods as part of the static
callgraph analysis: `Target`s, `Input`s, `Worker`s, etc. Those
`NamedTask`s will themselves get invalidated if necessary if the
non-`NamedTask` code _they_ depend on changes, and invalidation will
already get propagated through the runtime `Task` graph without needing
to also model it in the static callgraph. This would improve precision
while also greatly shrinking the static callgraphs

* This relies on an additional assumption over the current analysis: it
assumed that methods returning `NamedTask`s are pure and do not generate
side effects. This is probably an OK assumption to make, because proper
operation of the runtime `Task` graph also relies on that assumption

* This greatly improves precision for our use case. Virtual methods
implemented in many different places is a big weakness of CHA since it
has to assume any implementation could be called, especially combined
with calls to methods on external library traits that are also treated
conservatively and have to assume that any virtual method defined in
that library (and thus any local implementation) can be called. However,
in a Mill build, the vast majority of "virtual methods implementations"
and "external library method calls" are the
`mill.define.Target[A]`/`T[A]` methods we override and call. Skipping
static callgraph analysis for these and relying on the exact runtime
build graph is thus a huge improvement to the precision of target
invalidation.

5. I wire up JSON logging (to disk in the `T.dest` folder) to the
`--debug` flag. It's too expensive to generate all the time (~doubles
the time taken for `methodCodeHashSignatures`), but we definitely want
it to be available when things are misbehaving and we need to debug
things

## Automated Testing

1. `main/codesig/test/cases/callgraph/` contains unit tests that assert
the (simplified) call graphs are the right shape for a variety of
minimal scenarios. This also includes a few less trivial scenarios in
the `realistic/` folder: some of my old [Java
games](https://github.com/lihaoyi/Java-Games), a [parallel merge-sort
algorithm](https://github.com/handsonscala/handsonscala/blob/ebc0367144513fc181281a024f8071a6153be424/examples/13.7%20-%20ParallelMergeSort/MergeSort.sc)
and some [Castor actor
code](https://github.com/handsonscala/handsonscala/blob/ebc0367144513fc181281a024f8071a6153be424/examples/16.8%20-%20LoggingRearrangedPipeline2/LoggingPipeline.sc)
from my book Hands-on Scala, a Fastparse parser. Both Java and Scala
code work because we perform the analysis at the bytecode level.

2. We also exercise the transitive hash-propagation logic in some of the
`callgraph/` tests by replacing the "hash sum" logic with "Set union",
using it to compute transitive closures of the graph, and asserting that
the transitive closures are what we expect. This adds test coverage for
most of the logic around the hash propagation, without the expense of
performing runtime code-changes and re-compilation that we need to
perform in the integration tests.

3. `main/codesig/test/cases/methodhash/` contains tests that assert that
the method code hash signature has the correct properties: that it
changes when it should change and is un-changed when it should be
un-changed (e.g. when there are only formatting/line-number/comment
changes)

4. `integration/feature/codesig{simple,trait,scalamodule}` contain some
integration tests in that test the workflow end-to-end including the
integration into Mill's evaluator. These ensure that when you edit a
file and re-run Mill, the correct targets are re-evaluated. Test cases
include a single Target, Targets inside module `object`s and `trait`s, a
single `ScalaModule`, and a bunch of dependent/unrelated `ScalaModule`s

I had to update a bunch of existing tests - e.g. those in
`integration/feature/invalidation/` - because now random code changes no
longer invalidate targets within that file unless you actually change
the target or method bodies that the target calls.

This is a binary compatible change. I had to add some MIMA exclusions
due to MIMA not correctly considering things nested within a `private
object` as `private` (lightbend-labs/mima#771).

I added an opt-out flag `--disable-callgraph-invalidation` to swap back
to the previous script-import-graph-based invalidation system, as a
change-management measure to mitigate the risk of the novel invalidation
algorithm

## Manual Testing

I did some end-to-end tests on this PR, running `__.compile` on a few
different projects:

1. On the com-lihaoyi/fansi build, the incrementality seems to work as
expected: e.g. changing the `fansi.JsFansiModule#scalaJSVersion` from
`1.10.1` to `1.10.0` invalidates 87/796 targets which all seem Scala.js
related, while changing the `FansiTestModule#ivyDeps` uTest version from
0.8.1 to 0.8.0 invalidates 67/875 targets that are all test suite
related. This is working as expected

2. On the `com-lihaoyi/upickle` build, changing `bench.scalaJSVersion`
from `1.13.0` to `1.13.1` invalidates 28/3695 targets, while changing
`CommonJsModule#scalaJSVersion` invalidates 412/3695 targets

3. On the `com-lihaoyi/mill` codebase:

1. Adding a whitespace at the top of `build.sc`, to offset everyone's
line numbers without changing their logic, invalidates 16/8154 targets,
all downstream of `millVersion` which is invalidated by the dirty hash
of the repo checkout changing

2. Changing `scalajslib.worker[1].ivyDeps` by re-ordering them,
invalidates 17/8154 targets (just the ones above, + the one edited)

3. Changing `MillScalaModule#scalacOptions` by removing `-feature`,
invalidates 836/8154 targets

4. Changing `contrib.playlib.WorkerModule#sources` generating a
temporary file, invalidates 37/8154 targets, mostly stuff in
`contrib.playlib.worker[_]`

5. Changing a constant `Deps.scalaVersion` ends up invalidating
~4343/8154 targets. I skimmed through the results and they seem
reasonable: all `.scalaVersion` and `.compile` targets end up
invalidated, while many external targets aren't invalidated because they
don't have any local code to be affected by the callgraph analysis and
their upstream build graph is not affected by `Deps.scalaVersion` (e.g.
`integration.test.javacOptions`,
`contrib.codeartifact.mandatoryScalacOptions`)

6. Adding a new `val abc = 123` to the root module invalidates
everything, which is expected since it changes the constructor of
`build` which could potentially affect any module nested within it.
1. One solution for this is to turn them into `lazy val`s. Maybe we can
do it automatically via a compiler plugin.
2. Dataflow/Purity analysis is another alternative that would let us
keep them as `val`s while still distinguishing which `val` is used in
what method, but that is much more complicated analysis than the
callgraph analysis this PR implements

The Fansi and uPickle results shows that this approach does work for
non-trivial builds, and the Mill results show that it works even on
pretty large builds like Mill's own `build.sc` codebase.

## Debugging

The easiest way to understand what is going on with the callgraph
analysis is to run Mill with the `--debug` flag. This generates extra
output JSON files in `out/mill-build/methodCodeHashSignatures.dest/`
which give you an insight into what is going on inside the callgraph
analyzer: the `localSummary.json`, `externalSummary.json`,
`resolvedMethodCalls.json`, etc. These are opt-in with `--debug` due to
the added overhead it takes to generate them (0.3-0.5s for the Mill
codebase, would be larger for larger builds)

On item of interest is the `spanningInvalidationForest.json` that is
generated the second time you run Mill with `--debug` enabled. This file
contains a tree of nested JSON dictionaries containing every method
definition or call that was invalidated, with the roots of the tree
being the invalidation "roots" (i.e. methods which were invalidated
without any parents being invalidated), and the tree structure
indicating an arbitrary path from an invalidation root to each specific
invalidated method. This is very useful for answering the question "why
was this method/target/etc. invalidated in response to code changes"

## Performance

Performance-wise, ad-hoc benchmarks on `com-lihaoyi/mill`'s own build
show a ~5% increase in `build.sc` compilation times due to this. Not
nothing, but probably acceptable: the cost is only paid when the
`build.sc` is re-compiled, and it will likely end up saving much more
time in tasks that we can avoid running (e.g. a single no-op Zinc
incremental compile may be 100s of milliseconds)

| | methodCodeHashSignatures | compile |
|-|---|---|
| Cold |  685ms | 12,148ms |
| Hot | 253ms | 4,143ms | 

It's taken some amount of optimizations to reach this point. There are
definitely further optimizations that can be done, e.g. replacing the
various `Map`s we pass around with `Array` or parallelizing parts of the
analysis (It's mostly pure functional code and should be easy to
parallelize)

## What Users can do to improve incrementality

1. `Module` `val`s should generally be avoided in favor of `def`s or
`lazy val`s. `val`s are all bundled together in the `Module`
constructor, so any change to any `val` invalidates any downstream code
who depends on anything in that `Module`

2. Abstract members of `Module`s should be `Target`s - `T[V]`s -
whenever possible, rather than plain `V`s. We make a stronger assumption
that `T[V]` methods are pure that we cannot assume in general for any
method returning an un-wrapped `V`, and can rely fully on runtime
build-graph analysis which is a lot more precise than the static
class-hierarchy-analysis we do no non-`Target` abstract methods.
* e.g. a change to the code in `BuildInfo#buildInfoMembers` invalidates
the code in only that target, because we assume that `Target` method
dependencies and invalidation will be handled by the runtime callgraph
* But a change to `BuildInfo#buildInfoPackageName` invalidates the code
in almost everything on every `JavaModule extends BuildInfo` because we
cannot guarantee that the `<init>` method of those `Module`'s does not
depend on `buildInfoMembers`.

These restrictions are fundamental given the simple
reachability/class-hierarchy analysis that we do in this PR, and lifting
them would involve a more complicated dataflow analysis or purity
analysis that would be much less simple to implement

---------

Co-authored-by: Tobias Roeser <le.petit.fou@web.de>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

No branches or pull requests

1 participant